文档章节

给定100亿个网址,如何检测出重复的文件。

一贱书生
 一贱书生
发布于 2016/11/25 08:55
字数 807
阅读 34
收藏 0

给定100亿个网址,如何检测出重复的文件?这里所谓的“重复”是指两个URL完全相同。

或者:

使用hash将所有整数映射到1000个文件中,在每个文件中使用 bitmap,用两个bit表示出现次数,00表示没出现过,01表示出现过1次,10表示出现过多次,11舍弃,最后归并每个文件中出现只有1次的数即为所求。

如果是有符号整数的话,范围为-2147483648~2147483647 无符号整数为0~4294967296 有符号的使用两个bitset,一个存放正数,一个负数。 每个数使用两个位来判断其出现几次。00表示出现0词,01出现1次,10出现大于一次。 比如说存放整数100,就将bitset的第100*2位设置为+1,当所有数放完之后,对每两位进行测试看其值为多少?若是第i为与i+1为的值为 01,则这个整数:i*2,在集合中只出现了1次。需要总共用bitnun=(2^31*2)个位表示,需空间为int[bitnum],即512M.

将文件通过哈希函数成多个小的文件,由于哈希函数所有重复的URL只可能在同一个文件中,在每个文件中利用一个哈希表做次数统计。就能找到重复的URL。这时候要注意的就是给了多少内存,我们要根据文件大小结合内存大小决定要分割多少文件

topK问题和重复URL其实是一样的重复的多了才会变成topK,其实就是在上述方法后获得所有的重复URL排个序,但是有点没必要,因为我们要 找topK时,最极端的情况也就是topK在用一个文件中,所以我们只需要每个文件的topK个URL,之后再进行排序,这样就比找出全部的URL在排序 方法优秀。还有一个topK个URL到最后还是需要排序,所以我们在找每个文件的topK时,是否只需要找到topK个,其中顺序不用管,那么我们就可以 用大小为K的小根堆遍历哈希表。这样又可以降低查找的时间。

这里我来讲一下为什么用小根堆。
小根堆是一棵完全二叉树存在如下特性
(1)若树根结点存在左孩子,则根结点的值(或某个域的值)小于等于左孩子结点的值(或某个域的值);
(2)若树根结点存在右孩子,则根结点的值(或某个域的值)小于等于右孩子结点的值(或某个域的值);
(3)以左、右孩子为根的子树又各是一个堆。
建最小堆的过程,从最后一个叶节点的父节点开始,往前逐个检查各个节点,看其是不是符合父节点小于它的子节点,如果不小于,则将它的 子节点中最小的那个节点与父节点对换;否则,不交换,
这里写图片描述
 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
大数据处理面试题

给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 方an1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将...

zyt_1978
2016/04/14
130
0
海量数据面试题整理1.给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是

海量数据面试题整理   1. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?   方案1:可以估计每个文件安的大小为50G×64=320G,远远...

今幕明
2015/01/30
0
0
ToolGood/ToolGood.Words

ToolGood.Words 一款高性能非法词(敏感词)检测组件,附带繁体简体互换,支持全角半角互换,获取拼音首字母,获取拼音字母,拼音模糊搜索等功能。 文件夹说明: ToolGood.PinYin.Build: 生成词...

ToolGood
2017/01/14
0
0
opencv-python学习一--人脸检测

简略的介绍一下 : opencv是什么? , 人脸检测是什么? 最近对机器学习有点感兴趣,想直接从图像识别入手,这里选择了鼎鼎有名的 opencv ,一开始想直接调用opencv的api进行人脸的检测,功能也特简单...

L很失败L
2015/10/22
5.4K
0
hamsterdb 1.1.9 发布,嵌入式数据库

hamsterdb是一个采用C开发,非常快,轻量级的嵌入式数据库引擎。 hamsterdb是一个嵌入式数据库引擎撰写的ANSI - C 。它包括的B +树变长密钥和记录。它支持内存中的数据库和字节独立的文件,数...

红薯
2011/02/19
453
0

没有更多内容

加载失败,请刷新页面

加载更多

mybatis学习(2)

http://www.mybatis.org/spring/zh/factorybean.html 参考mybatis官网 Mybatis集成Spring: 使用Spring的IOC,将sqlSession(存在事物),交给Spring管理。 1.依赖jar包 <dependency> <g......

杨健-YJ
8分钟前
1
0
ES的性能优化

我们在很多场景下会用到ES帮助我们解决搜索问题,但是很多人了解只是停留在表面,如何深入的使用ES,并做针对性的性能优化呢? 批量提交 当大量的写任务时,可以采用批量提交的方案,但是需要...

春哥大魔王的博客
9分钟前
1
0
Linux下实现 OpenSSL 简单加密与解密字符串

场景 shell脚本中存在明文密码 客户要求禁止使用明文密码,密码做加密处理. 方案 在网上了解到了Linux OpenSSL加密解密工具 可以指定各种加密算法为字符,文件做加密处理. 加密的案例比较多,解...

linuxprobe16
12分钟前
1
0
解析Sharding-Sphere的SQL执行引擎

一、前言 Sharding-JDBC 是一款优秀的分库分表框架,从3.0开始,Sharding-JDBC更名为Sharding-Sphere,之前用Sharding-JDBC 2时,对于同库分表而言,sql执行是串行的,因为同数据源的connect...

冷血狂魔
14分钟前
1
0
Spring Cloud Stream消费失败后的处理策略(二):自定义错误处理逻辑

应用场景 上一篇《Spring Cloud Stream消费失败后的处理策略(一):自动重试》介绍了默认就会生效的消息重试功能。对于一些因环境原因、网络抖动等不稳定因素引发的问题可以起到比较好的作用...

程序猿DD
28分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部