|
锁定老帖子 主题：两个大数据量处理的问题.被鄙视了呜呜
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-09-08
1.场景如下.和某公司哥们聊.
那哥们问了我两个问题.如下 1.1亿个词频率统计..找出top1000 2.判断1亿个整数中是否包含.某个数字 第二题我已经找到答案了.在我的博客里面有 http://ansjsun.iteye.com/admin/blogs/1163037 至于第一个.我还是很纠结...没有很好的处理办法..拿出来讨论讨论吧..... 我的意见是用..key-value数据库做词频统计..数据比较大.所以内存中肯定放不下的.. 如果不吝啬内存.可以用类似分词.起码首字查找的办法也能做到..如果效率再高可以用双数组tire树做词典.. 这么做肯定是可以的..就是怕内存不够..分词的词典一般都是30万左右大小... 想知道有更好的算法没.. 题外话.当时只是被问..连请教的机会都没有..我问那哥们的解决思路.哥们笑而不语..很讨厌这种藏着掖着的.也不是什么内部机密..也不是你自己想的算法..最后还被告知那哥们就做了一年的搜索...哎我也见过不少人..阴沟里翻船了...学无止境啊 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2011-09-09
你确定他问你的前提是单机环境?
|
| 返回顶楼 | |
|
发表时间：2011-09-09
aidirac 写道 你确定他问你的前提是单机环境?
单机环境就算了...就给我16m内存 |
| 返回顶楼 | |
|
发表时间：2011-09-09
而且要求速度
|
| 返回顶楼 | |
|
发表时间：2011-09-09
http://blog.csdn.net/v_JULY_v/article/details/6256463
|
| 返回顶楼 | |
|
发表时间：2011-09-09
谢谢楼上的我看了你给我的地址..
他的思想就是根据query映射成hash映射到一个table中..hash算法和table的size取摸...用以统计...有了统计数据..然后取得top1000 soeasy...不知道我理解的是否正确....我还想弄明白..hash是肯定有重复的...对于这个重复是怎么处理的啊???1000万的数据用hash至少得几千重复吧...是不是这个重复可以忽略? |
| 返回顶楼 | |
|
发表时间：2011-09-10
用最小根堆不知可否：先取出前一千个整数并且构造一个最小根堆，然后顺序从剩下的整数中取数并与堆的最小根比较，若大于根的值者把根的值设为取出的数，并且用较大值下沉的方式调整堆结构使堆满足最小堆的要求。1000个整数构造的最小堆也就10层，第一次构造完堆之后的比较中每次最多比较并交换10次，而且随着顺序取数的增多，这个比较并交换的次数趋于减小的概率更大。
|
| 返回顶楼 | |
|
发表时间：2011-09-10
liupengtao 写道 用最小根堆不知可否：先取出前一千个整数并且构造一个最小根堆，然后顺序从剩下的整数中取数并与堆的最小根比较，若大于根的值者把根的值设为取出的数，并且用较大值下沉的方式调整堆结构使堆满足最小堆的要求。1000个整数构造的最小堆也就10层，第一次构造完堆之后的比较中每次最多比较并交换10次，而且随着顺序取数的增多，这个比较并交换的次数趋于减小的概率更大。
使用堆前，每条记录出现次数要先统计好 |
| 返回顶楼 | |
|
发表时间：2011-09-12
分文件，比如根据首字母或者根据hash取模等，然后分析每个文件得到结果。
|
| 返回顶楼 | |
|
发表时间：2011-09-13
第一题 hash 到小文件，统计到小文件，将小文件归并排序
|
| 返回顶楼 | |
