文档章节

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

一贱书生
 一贱书生
发布于 2016/11/25 08:55
字数 807
阅读 31
收藏 0
点赞 0
评论 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
博文 722
码字总数 600072
作品 0
大数据处理面试题

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

zyt_1978 ⋅ 2016/04/14 ⋅ 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

海量数据题

1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射...

GM_LV ⋅ 2012/10/22 ⋅ 0

面试中思路性质问题

千万级的用户,提供一个服务,该服务有很多模块,现在有一个底层模块需要优化,问怎么实现,在不影响其他服务模块以及用户体验的情况下。(面IEG) http://taop.marchtea.com/09.03.html 未知...

momo李 ⋅ 2017/09/18 ⋅ 0

万变不离其宗之海量数据下的算法问题处理思路

本文介绍 万变不离其宗之海量数据下的算法问题处理思路 万变不离其宗之海量数据下的算法问题处理思路 本文由在当地较为英俊的男子金天大神原创,版权所有,欢迎转载,但请保留这段版权信息,...

Nicholas_Jela ⋅ 2017/09/06 ⋅ 0

[转]海量数据处理的面试题的方法总结

处理海量数据问题,无非就是: 分而治之/hash映射 + hash统计 + 堆/快速/归并排序; Bloom filter/Bitmap; Trie树/数据库/倒排索引; 外排序; 分布式处理之hadoop/mapreduce。 本文接下来的...

十一11 ⋅ 2016/03/11 ⋅ 0

海量数据处理:十道面试题与十个海量数据处理方法总结

1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射...

ahucsxl ⋅ 2015/10/08 ⋅ 0

十道海量数据处理面试题与十个方法大总结

海量数据处理:十道面试题与十个海量数据处理方法总结 本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。 出处:http://blog.csdn.net/vJULYv。 第一部分、十道海量数据处理面试题...

吟啸_徐行 ⋅ 2014/04/02 ⋅ 2

链接测试工具小汇

在Web测试中,经常测试整个网站的链接是否正确,特别是在发布新的网站或是网站大的改版时,常用的链接测试工具有: 1、Xenu Link Sleuth http://home.snafu.de/tilman/xenulink.html 可以打开...

Yason_Luo ⋅ 2015/03/30 ⋅ 0

ToolGood/ToolGood.Words

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

ToolGood ⋅ 2017/01/14 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

知乎Java数据结构

作者:匿名用户 链接:https://www.zhihu.com/question/35947829/answer/66113038 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 感觉知乎上嘲讽题主简...

颖伙虫 ⋅ 今天 ⋅ 0

Confluence 6 恢复一个站点有关使用站点导出为备份的说明

推荐使用生产备份策略。我们推荐你针对你的生产环境中使用的 Confluence 参考 Production Backup Strategy 页面中的内容进行备份和恢复(这个需要你备份你的数据库和 home 目录)。XML 导出备...

honeymose ⋅ 今天 ⋅ 0

JavaScript零基础入门——(九)JavaScript的函数

JavaScript零基础入门——(九)JavaScript的函数 欢迎回到我们的JavaScript零基础入门,上一节课我们了解了有关JS中数组的相关知识点,不知道大家有没有自己去敲一敲,消化一下?这一节课,...

JandenMa ⋅ 今天 ⋅ 0

火狐浏览器各版本下载及插件httprequest

各版本下载地址:http://ftp.mozilla.org/pub/mozilla.org//firefox/releases/ httprequest插件截至57版本可用

xiaoge2016 ⋅ 今天 ⋅ 0

Docker系列教程28-实战:使用Docker Compose运行ELK

原文:http://www.itmuch.com/docker/28-docker-compose-in-action-elk/,转载请说明出处。 ElasticSearch【存储】 Logtash【日志聚合器】 Kibana【界面】 答案: version: '2'services: ...

周立_ITMuch ⋅ 今天 ⋅ 0

使用快嘉sdkg极速搭建接口模拟系统

在具体项目研发过程中,一旦前后端双方约定好接口,前端和app同事就会希望后台同事可以尽快提供可供对接的接口方便调试,而对后台同事来说定好接口还仅是个开始、设计流程,实现业务逻辑,编...

fastjrun ⋅ 今天 ⋅ 0

PXE/KickStart 无人值守安装

导言 作为中小公司的运维,经常会遇到一些机械式的重复工作,例如:有时公司同时上线几十甚至上百台服务器,而且需要我们在短时间内完成系统安装。 常规的办法有什么? 光盘安装系统 ===> 一...

kangvcar ⋅ 昨天 ⋅ 0

使用Puppeteer撸一个爬虫

Puppeteer是什么 puppeteer是谷歌chrome团队官方开发的一个无界面(Headless)chrome工具。Chrome Headless将成为web应用自动化测试的行业标杆。所以我们很有必要来了解一下它。所谓的无头浏...

小草先森 ⋅ 昨天 ⋅ 0

Java Done Right

* 表示难度较大或理论性较强。 ** 表示难度更大或理论性更强。 【Java语言本身】 基础语法,面向对象,顺序编程,并发编程,网络编程,泛型,注解,lambda(Java8),module(Java9),var(...

风华神使 ⋅ 昨天 ⋅ 0

Linux系统日志

linux 系统日志 /var/log/messages /etc/logrotate.conf 日志切割配置文件 https://my.oschina.net/u/2000675/blog/908189 logrotate 使用详解 dmesg 命令 /var/log/dmesg 日志 last命令,调......

Linux学习笔记 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部