首页 > 试题广场 >

索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来

[问答题]

寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。

姚波

由于重复度比较高，300万*255字节 = 765M，不会超过1G，因此可以用Hash_Map的思路。通过
哈希函数将字符串映射到Hash空间中，哈希模型的Key值为字符串，value值为字符串的出现次数count。之后维护一个k = 10的小根堆，这样能保证在logK的时间内查找和删除元素，因此总体的时间复杂度是O(n) + O(nlogk)

发表于 2015-07-09 14:47:49 回复(0)

onlyspecial

按照字符串长度把字符串分为255组，经计算总的字符串大小，这255组可以分三次进入内存，第一组1~55，第二组56~155，第三组156~255,。长度相同的那一小组可以经过排序从小到大排好，比如堆排序时间复杂度O(NlogN)，空间复杂度O(1)，然后经过一次遍历就可以得到每个字符串的重复次数。再通过10个元素的总的时间复杂度O(Nlog10)的最小堆可以得到重复次数前十名。那么把255个组的前十名全部读入内存，再通过一个最小堆可得到总的前十名。

发表于 2015-08-22 16:08:40 回复(1)