首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超
[问答题]
搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万
要统计最热门的10条查询串. 内存<1G. 字符串长 0-255
(1) 主要解决思路
(2) 算法及其复杂度分析
添加笔记
求解答(19)
邀请回答
收藏(199)
分享
纠错
15个回答
添加回答
1
黄小斜
hash后剩余300w条不重复数据。
分成3份文件,建立一个10个数的大根堆,三次遍历后得到前十个查询串。
复杂度为nlog(10)
发表于 2017-04-03 15:31:26
回复(0)
更多回答
15
fengniumaxuwei
不重复的不超过三百万,三百万条记录可以存放在1G的内存中,每次取出3百万条记录,每次统计出各记录出现的次数,取完所有的记录后,各记录出现的次数也就统计出来了,此时可以采用包含十个元素的最小堆,若大于堆顶元素则插入堆中,则将所有记录出现次数的数据插入堆中后,堆中最后剩下的便是10条最热门的查询条。
发表于 2015-07-29 15:17:42
回复(4)
3
张立超
(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)
9
牛里格村
(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)
2
探寻的脚步
300万个字符串最多(假设没有重复,都是最大长度)占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理。
可以使用key为字符串(事实上是字符串的hash值),值为字符串出现次数的hash来统计每个每个字符串出现的次数。并用一个长度为10的数组/链表来存储目前出现次数最多的10个字符串。
这样空间和时间的复杂度都是O(n)。
发表于 2015-09-02 14:24:46
回复(0)
3
得得小泽
分俩部门,第一部分建立 索引树,数据遍历索引树,数据在树中存在的话,count++,数据不存在 就加到索引树上,第二部分建立个含有十个数据的最小堆,将数据的count与堆顶比较,大于堆顶的话,将其加入,同时删除堆顶元素,加入后重新调整堆的位置。
发表于 2015-07-20 14:58:18
回复(1)
1
FFF乔碧罗
因为一千万条记录在内存1G的情况下是不可能完全放在内存中的,所以首先要大而化小,将问题拆分。
利用hash函数,将一千万条记录映射到10个文件中,这样每个文件大概在一百万条记录,最大占用空间在0.4G。
对每个文件利用hash_map统计字符串出现的次数,按照次数的高低排序。
最后分别取出10个文件中的前10个出现最多的字符串,一共就100个,快速排序输出最大的10条记录。
发表于 2015-09-06 15:13:55
回复(0)
1
有pp才有真相
我看到的关键词是topk
既然是topk,那么复杂度就是
O(n*logn)。
其他方案参考:
Pig、Hive、MapReduce 解决分组 Top K 问题(转)
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)
0
树枝
1.建立索引。(字符串255显过长,需要建索引,可以用树或者暴力一点直接用hash表)
2.查询串到达时,进行hash,将对应表项cnt++
3.10个变量,遍历hash,找出cnt前10大。(10个元素,为啥要用堆?直接10个变量搞定,又不是算法题的求第K大问题,实际问题实际解决)
发表于 2015-09-11 10:15:34
回复(0)
0
Ze
关键是hash,堆(字典树),归并就OK了
发表于 2015-09-06 01:17:15
回复(0)
0
登疯作极
将日志文件映射到内存,使用hash表确定出top10。复杂度o(n)。
发表于 2015-09-05 16:15:50
回复(0)
0
牛客_练习
大神!崇拜
发表于 2015-09-04 23:30:13
回复(0)
0
shiawang
1g大概10亿字节。不重复的不超过300万字符串。也就是说字符串最大内存空间<(300+700/2)万*255=165750万=16亿。
因此,内存空间
可能不够
!!不能直接先把所有数据放到内存树中!!
推荐使用mapreduce wordcount第一遍统计出单词频率。第二遍把频率作为key,进行统计,找出频率最高的10个值(可能需要修改比较法则,默认从小到大)。
发表于 2015-07-20 17:36:30
回复(2)
0
慈慈乱了
hash + 堆
发表于 2015-07-20 09:13:57
回复(1)
0
小小
可以用storm+esper做实时分析
发表于 2014-12-04 11:54:59
回复(1)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
哈希
腾讯
百度
查找
来自:
腾讯2014校招研发工...
上传者:
Callllll
难度:
15条回答
199收藏
18838浏览
热门推荐
相关试题
百度Spider如何在不超过抓取限...
百度
2011
系统设计
Java工程师
C++工程师
评论
(7)
来自
百度2011研发工程师笔试卷
判断一个括号字符串是否匹配正确,如...
百度
2011
栈
Java工程师
C++工程师
评论
(34)
来自
百度2011研发工程师笔试卷
仅用O(1)的空间,将整数数组按奇...
百度
2011
C++
Java
编程基础
Java工程师
C++工程师
评论
(25)
来自
百度2011研发工程师笔试卷
static全局变量与普通的全局变...
腾讯
C++
评论
(8)
来自
腾讯2014校招研发工程...
写出下列代码的输出内容() ...
腾讯
C++
评论
(22)
来自
腾讯2014校招研发工程...
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题