2,760
社区成员
发帖
与我相关
我的任务
分享海量数据处理的问题！
1. 给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。
2. 有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序
3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词
4.海量日志数据，提取出某日访问百度次数最多的那个IP。
5.2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。
6.海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
7.怎么在海量数据中找出重复次数最多的一个
8.上千万or亿数据（有重复），统计其中出现次数最多的前N个数据。
统计可以用hash,二叉数,trie树。对统计结果用堆求出现的前n大数据。增加点限制可以提高效率，比如 出现次数>数据总数／N的一定是在前N个之内
9.1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？
10.一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前十个词。请给出思想，给时间复杂度分析。
11.一个文本文件，也是找出前十个最经常出现的词，但这次文件比较长，说是上亿行或者十亿行，总之无法一次读入内存，问最优解。
12.有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复要按照query的频度排序
13.100w个数中找最大的前100个数
14.寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，
这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，
也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。
15.一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。
如何找到N^2个数的中数(median)？
2. 有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序
3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词
4.海量日志数据，提取出某日访问百度次数最多的那个IP。
5.2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。
6.海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
7.怎么在海量数据中找出重复次数最多的一个
8.上千万or亿数据（有重复），统计其中出现次数最多的前N个数据。
统计可以用hash,二叉数,trie树。对统计结果用堆求出现的前n大数据。增加点限制可以提高效率，比如 出现次数>数据总数／N的一定是在前N个之内
9.1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？
10.一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前十个词。请给出思想，给时间复杂度分析。
11.一个文本文件，也是找出前十个最经常出现的词，但这次文件比较长，说是上亿行或者十亿行，总之无法一次读入内存，问最优解。
12.有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复要按照query的频度排序
13.100w个数中找最大的前100个数
14.寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，
这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，
也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。
15.一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。
如何找到N^2个数的中数(median)？
...全文
请发表友善的回复…
发表回复
freecodeMAN 2011-01-01
- 打赏
- 举报
[Quote=引用 5 楼 wmpact518 的回复:]
引用 3 楼 onmywayhong 的回复:
海量数据的处理，基本思路就是分布式。
比如 2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。
比如 告诉你的整数的范围 是 1 到 10亿。
那么如果有100台电脑，就可以把10亿的范围 分配到每台电脑上，每一台电脑只需要统计1千万的数据范围。 如果有1000台电脑，那么每台其实只有 1百万的范围，那样……
[/Quote]
这个不是思路,,已经是框架了,云计算框架> hadoop相关资料可以看下,应该是干这个的.
引用 3 楼 onmywayhong 的回复:
海量数据的处理，基本思路就是分布式。
比如 2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。
比如 告诉你的整数的范围 是 1 到 10亿。
那么如果有100台电脑，就可以把10亿的范围 分配到每台电脑上，每一台电脑只需要统计1千万的数据范围。 如果有1000台电脑，那么每台其实只有 1百万的范围，那样……
[/Quote]
这个不是思路,,已经是框架了,云计算框架> hadoop相关资料可以看下,应该是干这个的.
lay_1980 2010-12-20
- 打赏
- 举报
简单的想：
1.
a.对A建图O(N)直到内存限制
b.用B遍历A图O(N)，记录结果
重复a
2.
a.每个文件,N = UID(query stmt)（可以hash），合并后得到可排序数组 : 次数<<32 | N
b.std::partial_sort(100)
c.对每个文件的top100,也就是1000个，std::partial_sort(10)
因为合并的原因，上面这个结果是近似值
3.无病呻吟
4.5.6.7.8.11
a.分块top
b.top各块的top
9.1-2级索引+图
13.std::partial_sort(100)
partial_sort是heap排序，当top数>1/2数组长的时候，partial_sort性能不如sort
可以自己写混合partial_sort，32以下用insert,某些情况下用quick sort
std::_Unguarded_partition的八分取了中值，要partition这里就需要根据情况改变取值范围
基本都是分块取top，获得近似值
std::sort可以排序逻辑上连续的数组，只要你重载了迭代子，使得不同文件的元素对于sort看起来像数组，也可以直接排，这样排出来的结果是不会错的
应该需要自己写sort函数，在排序的时候进行合并处理
不过，跳跃读写文件的代价是很大
1.
a.对A建图O(N)直到内存限制
b.用B遍历A图O(N)，记录结果
重复a
2.
a.每个文件,N = UID(query stmt)（可以hash），合并后得到可排序数组 : 次数<<32 | N
b.std::partial_sort(100)
c.对每个文件的top100,也就是1000个，std::partial_sort(10)
因为合并的原因，上面这个结果是近似值
3.无病呻吟
4.5.6.7.8.11
a.分块top
b.top各块的top
9.1-2级索引+图
13.std::partial_sort(100)
partial_sort是heap排序，当top数>1/2数组长的时候，partial_sort性能不如sort
可以自己写混合partial_sort，32以下用insert,某些情况下用quick sort
std::_Unguarded_partition的八分取了中值，要partition这里就需要根据情况改变取值范围
基本都是分块取top，获得近似值
std::sort可以排序逻辑上连续的数组，只要你重载了迭代子，使得不同文件的元素对于sort看起来像数组，也可以直接排，这样排出来的结果是不会错的
应该需要自己写sort函数，在排序的时候进行合并处理
不过，跳跃读写文件的代价是很大
libobo5954451 2010-10-19
- 打赏
- 举报
bloom filter
hash
bit-map
堆
双层桶划分
db index
倒排
外排
trie树
mr
自己找吧
hash
bit-map
堆
双层桶划分
db index
倒排
外排
trie树
mr
自己找吧
kannju 2010-10-15
- 打赏
- 举报
这样的题目主要还是考算法吧
而不是考察什么分布式mapreduce hadoop之类的分布式处理
第一题分快排序，再分别取块最小的项进行比较
而不是考察什么分布式mapreduce hadoop之类的分布式处理
第一题分快排序，再分别取块最小的项进行比较
hwbox 2010-07-12
- 打赏
- 举报
第一题：（先不考虑内存限制），50亿的数据，可以做Dictionary（一级不行就二级）。A,B各自建立Dictionary，Dictionary是有序的，所以取A第一条，在B中查找，未找到，删除A第一条。根据Dictionary的计算复杂度Olog(n)（好象是这个复杂度吧，记不清了）,要交错删除可以让查找变的越来越快。也就是说第二次从B中取第一个，在A中查，找不到删除B中的，找到了就继续在A中查B中的下一个。
JJ8582 2010-06-17
- 打赏
- 举报
hadoop 试试
Wyhshp 2010-06-14
- 打赏
- 举报
搜索引擎多考虑和数据库结合。
很多问题用数据库很容易解决，不要受内存、空间限制提示的误导。
很多问题用数据库很容易解决，不要受内存、空间限制提示的误导。
hxbr110 2010-06-10
- 打赏
- 举报
先收藏
j2eeoriented 2010-05-27
- 打赏
- 举报
andy_713 2010-05-24
- 打赏
- 举报
楼主真是厉害，若解决这样的难题，可以进微软，Google……了
lingjoin 2010-03-29
- 打赏
- 举报
建议思路：尽可能采用云计算的架构，MapReduce的策略会比较好。
哈特比尔波 2010-02-04
- 打赏
- 举报
在回帖中，又看到了狂人的回复了。呵呵。无处不在哈。
哈特比尔波 2010-02-04
- 打赏
- 举报
在回帖中，又看到了狂人的回复了。呵呵。无处不在哈。
哈特比尔波 2010-02-04
- 打赏
- 举报
在回帖中，又看到了狂人的回复了。呵呵。无处不在哈。
scfans 2009-11-22
- 打赏
- 举报
学习中。。。。
给思维做按摩 2009-11-19
- 打赏
- 举报
jobs24 2009-11-16
- 打赏
- 举报
用索引库，倒排表了。
广州达梦网络科技有限公司是一家致力于为提供各行业垂直搜索和元搜索服务的专业化公司。公司坚持以服务客户为中心，以技术创新为手段，为客户提供各个行业、任意搜索源精确搜索的解决方案，以及中个小企业信息服务的解决方案！
主要的搜索引擎案例有：万帮生活搜索，114soso网，万帮知识经验搜索，佛教新闻、网页、图片、视频、经典、词典、mp3等十个搜索引擎，还有各个行业的搜索引擎，目标是打造100个行业的百度。
能为您快速定制各类搜索引擎，如果您各类搜索引擎需求，请联系我们：020-22174900，QQ：46244150。
广州达梦网络科技有限公司是一家致力于为提供各行业垂直搜索和元搜索服务的专业化公司。公司坚持以服务客户为中心，以技术创新为手段，为客户提供各个行业、任意搜索源精确搜索的解决方案，以及中个小企业信息服务的解决方案！
主要的搜索引擎案例有：万帮生活搜索，114soso网，万帮知识经验搜索，佛教新闻、网页、图片、视频、经典、词典、mp3等十个搜索引擎，还有各个行业的搜索引擎，目标是打造100个行业的百度。
能为您快速定制各类搜索引擎，如果您各类搜索引擎需求，请联系我们：020-22174900，QQ：46244150。
gonxi 2009-11-16
- 打赏
- 举报
可以用内存hash的,就直接做hash,
内存不够的就分布处理,然后合并
快速查询可以使用多级索引
缓存提高性能
基本上就这些手段,
内存不够的就分布处理,然后合并
快速查询可以使用多级索引
缓存提高性能
基本上就这些手段,
erp2 2009-10-15
- 打赏
- 举报
度的题?
这么弱智的题目是百度出的吗?
太搞笑了吧?
即便做搜索,也不可能会出现上面题目中那么弱智的问题,更谈不上解决了!
就拿第一个问题来说:
1. 给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。
就算有 500亿的url,要寻找一个重复的,也不可能这么存储,换我的方案,就算5000亿个url要判断是否某个url已经存在也不会超过 0.001秒的时间!
总之这么弱智的问题只能是某个白痴出的,我不相信是百度出的!
不服的可以过来交流 QQ 99923309
个人博客: http://hi.baidu.com/earthsearch
这么弱智的题目是百度出的吗?
太搞笑了吧?
即便做搜索,也不可能会出现上面题目中那么弱智的问题,更谈不上解决了!
就拿第一个问题来说:
1. 给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。
就算有 500亿的url,要寻找一个重复的,也不可能这么存储,换我的方案,就算5000亿个url要判断是否某个url已经存在也不会超过 0.001秒的时间!
总之这么弱智的问题只能是某个白痴出的,我不相信是百度出的!
不服的可以过来交流 QQ 99923309
个人博客: http://hi.baidu.com/earthsearch
wmpact518 2009-10-13
- 打赏
- 举报
[Quote=引用 3 楼 onmywayhong 的回复:]
海量数据的处理，基本思路就是分布式。
比如 2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。
比如 告诉你的整数的范围 是 1 到 10亿。
那么如果有100台电脑，就可以把10亿的范围 分配到每台电脑上，每一台电脑只需要统计1千万的数据范围。 如果有1000台电脑，那么每台其实只有 1百万的范围，那样的话，每台处理的时间都会比较少。
然后把 每台电脑上返回的不同的数的数目加起来就是答案。
[/Quote]
这个思路很好，受教了。
但是这样的就不知道该怎么做了
海量数据分布在100台电脑中，想个办法高效统计出这批数据中出现频率最高的10个。
海量数据的处理，基本思路就是分布式。
比如 2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。
比如 告诉你的整数的范围 是 1 到 10亿。
那么如果有100台电脑，就可以把10亿的范围 分配到每台电脑上，每一台电脑只需要统计1千万的数据范围。 如果有1000台电脑，那么每台其实只有 1百万的范围，那样的话，每台处理的时间都会比较少。
然后把 每台电脑上返回的不同的数的数目加起来就是答案。
[/Quote]
这个思路很好，受教了。
但是这样的就不知道该怎么做了
海量数据分布在100台电脑中，想个办法高效统计出这批数据中出现频率最高的10个。
加载更多回复（2）
