典型的 Top K 算法,还是在这篇文章里头有所阐述,详情请参见:十一、从头到尾彻 底解析 Hash 表算法。 文中,给出的最终算法是: 第一步、先对这批海量数据预处理,在 O(N)的时间内用 Hash 表完成统计(之前写 成了排序,特此订正。July、2011.04.27); 第二步、借助堆这个数据结构,找出 Top K,时间复杂度为 N‘logK。 即,借助堆结构,我们可以在 log 量级的时间内查找和调整/移动。因此,维护一个 K(该 题目中是 10)大小的小根堆,然后遍历 300 万的 Query,分别和根元素进行对比所以,我们 最终的时间复杂度是:O(N) + N'*O(logK),(N 为 1000 万,N’为 300 万)。ok,更多, 详情,请参考原文。 或者:采用 trie 树,关键字域存该查询串出现的次数,没有出现为 0。最后用 10 个元 素的最小推来对出现频率进行排序。 3、有一个 1G 大小的一个文件,里面每一行是一个词,词的大小不超过 16 字节,内存限 制大小是 1M。返回频数最高的 100 个词。 方案:顺序读文件中,对于每个词 x,取 hash(x)%5000,然后按照该值存到 5000 个 小文件(记为 x0,x1,...x4999)中。这样每个文件大概是 200k 左右。 如果其中的有的文件超过了 1M 大小,还可以按照类似的方法继续往下分,直到分解得 到的小文件的大小都不超过 1M。 对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用 trie 树/hash_map 等),并取出出现频率最大的 100 个词(可以用含 100 个结点的最小堆),并把 100 个词及 相应的频率存入文件,这样又得到了 5000 个文件。下一步就是把这 5000 个文件进行归并 (类似与归并排序)的过程了。 4、有 10 个文件,每个文件 1G,每个文件的每一行存放的都是用户的 query,每个文件的 query 都可能重复。要求你按照 query 的频度排序。 还是典型的 TOP K 算法,解决方案如下: 方案 1: 顺序读取 10 个文件,按照 hash(query)%10 的结果将 query 写入到另外 10 个文件(记 为)中。这样新生成的文件每个的大小大约也 1G(假设 hash 函数是随机的)。 找一台内存在 2G 左右的机器,依次对用 hash_map(query, query_count)来统计每个 query 出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的 query 和对
- 粉丝: 25
- 资源: 4215
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助