首页 > 试题广场 >

搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超

[问答题]
搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万
要统计最热门的10条查询串. 内存<1G. 字符串长 0-255
(1) 主要解决思路
(2) 算法及其复杂度分析
不重复的不超过三百万,三百万条记录可以存放在1G的内存中,每次取出3百万条记录,每次统计出各记录出现的次数,取完所有的记录后,各记录出现的次数也就统计出来了,此时可以采用包含十个元素的最小堆,若大于堆顶元素则插入堆中,则将所有记录出现次数的数据插入堆中后,堆中最后剩下的便是10条最热门的查询条。
发表于 2015-07-29 15:17:42 回复(4)
(1)主要解决思路:
1)因为只有1千万条查询,每条查询占最多255个字节,也就是2.55G,1G内存显然不够,用一致性hash的思想,将查询串分到3个子文件,尽量均衡。
2)然后在每个子文件中,创建hash表,统计每个串出现的次数,再创建一个大小为10的小根堆,如果串比堆头大,堆头扔掉,串进堆,调整;如果串比堆头小,串扔掉,堆不变;
3)然后再将三个子文件中每个的前10名进行比较,最后选出最后的前10名

(2)算法及其复杂度分析:
1)第一步:时间复杂度O(N)
2)第二步:时间复杂度O(NlogN),空间复杂度O(N)
3)第三步:得出结果
发表于 2016-08-28 10:10:31 回复(0)
(1)首先一千万条查询记录,每条字符串长0~255,而限制内存< 1G,所以不能把一千万条记录全部放进内存中处理,经计算,1千万条记录的最大占用空间大小为256Byte*10^8=0.25KB * 10^8=2.5*10^7KB,而1G = 1024M = 1024*1024KB = 1.024*1.024*10^6KB,从这可看出内存一次性读取的最大记录数是40万条,所以使用hash分割将1千万条记录分成25个记录块,Hash(字符串记录)%25,使得相同的字符串记录在相同的记录块中,再使用哈希表来计算出40万条记录重复次数最大的前10条记录,哈希表的key是记录字符串,值是重复次数。这样25次访问完1千万条记录,将会得到250条记录,然后使用Map存储这250条记录,key是重复次数,值是记录字符串,比较函数是greater函数对象,从大到小存储在Map中,前10条即是最热门的10条查询串。 </div> <div> (2)复杂度分析:2N + klogk ~ O(N)。但是有个问题是,假如有些查询记录重复次数大于40万次,则还有可能相同记录不在同一个记录块中的情况,还是会有问题,希望大神能给出好的想法。
编辑于 2015-09-10 22:10:49 回复(8)
       300万个字符串最多(假设没有重复,都是最大长度)占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理。
可以使用key为字符串(事实上是字符串的hash值),值为字符串出现次数的hash来统计每个每个字符串出现的次数。并用一个长度为10的数组/链表来存储目前出现次数最多的10个字符串。
这样空间和时间的复杂度都是O(n)。
发表于 2015-09-02 14:24:46 回复(0)
分俩部门,第一部分建立 索引树,数据遍历索引树,数据在树中存在的话,count++,数据不存在 就加到索引树上,第二部分建立个含有十个数据的最小堆,将数据的count与堆顶比较,大于堆顶的话,将其加入,同时删除堆顶元素,加入后重新调整堆的位置。
发表于 2015-07-20 14:58:18 回复(1)
hash后剩余300w条不重复数据。
分成3份文件,建立一个10个数的大根堆,三次遍历后得到前十个查询串。
复杂度为nlog(10)
发表于 2017-04-03 15:31:26 回复(0)
因为一千万条记录在内存1G的情况下是不可能完全放在内存中的,所以首先要大而化小,将问题拆分。 
利用hash函数,将一千万条记录映射到10个文件中,这样每个文件大概在一百万条记录,最大占用空间在0.4G。
对每个文件利用hash_map统计字符串出现的次数,按照次数的高低排序。  
最后分别取出10个文件中的前10个出现最多的字符串,一共就100个,快速排序输出最大的10条记录。

发表于 2015-09-06 15:13:55 回复(0)


我看到的关键词是topk
既然是topk,那么复杂度就是O(n*logn)。


其他方案参考:
github 系统参考:
https://github.com/hellojinjie/storm-esper-example
Storm 和 esper 整合的例子。演示数据流处理引擎在日志实时处理中的应用

spark博士论文参考:
https://code.csdn.net/flycutter/spark_matei_phd/file/04.md#%E4%BB%A5%E5%BE%80%E7%9A%84%E5%A4%84%E7%90%86%E6%A8%A1%E5%9E%8B

发表于 2015-01-28 22:40:39 回复(1)
1.建立索引。(字符串255显过长,需要建索引,可以用树或者暴力一点直接用hash表)
2.查询串到达时,进行hash,将对应表项cnt++
3.10个变量,遍历hash,找出cnt前10大。(10个元素,为啥要用堆?直接10个变量搞定,又不是算法题的求第K大问题,实际问题实际解决)
发表于 2015-09-11 10:15:34 回复(0)
Ze头像 Ze
关键是hash,堆(字典树),归并就OK了
发表于 2015-09-06 01:17:15 回复(0)
将日志文件映射到内存,使用hash表确定出top10。复杂度o(n)。
发表于 2015-09-05 16:15:50 回复(0)
大神!崇拜

发表于 2015-09-04 23:30:13 回复(0)
1g大概10亿字节。不重复的不超过300万字符串。也就是说字符串最大内存空间<(300+700/2)万*255=165750万=16亿。
因此,内存空间可能不够!!不能直接先把所有数据放到内存树中!!
推荐使用mapreduce wordcount第一遍统计出单词频率。第二遍把频率作为key,进行统计,找出频率最高的10个值(可能需要修改比较法则,默认从小到大)。
发表于 2015-07-20 17:36:30 回复(2)
hash  + 堆
发表于 2015-07-20 09:13:57 回复(1)
可以用storm+esper做实时分析
发表于 2014-12-04 11:54:59 回复(1)