[CareerCup] 10.6 Find Duplicate URLs 找重复的URL链接

简介:

10.6 You have 10 billion URLs. How do you detect the duplicate documents? In this case, assume that "duplicate" means that the URLs are identical.

这道题让我们在一百亿个URL链接中寻找相同项,看这数据量简直吓尿了,如果每个URL链接平均100个字符的话,每个字符是4个字节,那么总共需要占4TB的空间,我们无法在内存中导入这么大的数据量。假如我们恩能够把数据全部导入到内存中,那么找重复项就不是一件难事,我们可以使用哈希表来建立每个URL和其是否存在过建立映射,很容易能找到重复项。那么下面来看我们怎么处理这么大的数据量,我们可以有如下两种方法:

1. 硬盘存储

将所有的数据存到一台机子上,我们可以把4TB的数据分为4000份,每份1GB大小,然后我们把每个URL u存在文件x.txt中,其中x=hash(u)%4000,这样具有相同哈希值的URL都被放到一个文件中了。然后我们再把每个文件导入内存,来寻找重复值。

2. 多台机器

另一种方法是使用多台机器,我们不是将数据存在x.txt,而是将URL发给机器x. 使用这种方法有好处也有坏处。好处是可以并行操作,4000个块可以同时进行操作。坏处是我们需要4000台机器,这不太现实,而且还要考虑如何处理失败。

本文转自博客园Grandyang的博客,原文链接:找重复的URL链接[CareerCup] 10.6 Find Duplicate URLs ,如需转载请自行联系原博主。

相关文章
|
编解码
解决Hexo博客导航栏链接URL乱码问题
今年的计划之一是搭建一个博客,开始写博客。于是在网上找了一些博客程序发现用Hexo在gitHub上搭建自己的个人博客是比较简单而且易于维护的做法。 在网上找了一些教程后开始搭建,用自己比较中意的hexo-theme-next模板,发现搭建成功后导航栏链接不对,出现了URL乱码的问题。在网上搜索了一把发现有些网友也碰到了类似的问题不过都还没有解决。
130 0
|
JavaScript 前端开发
JS 下载 URL 链接文件(点击按钮、点击a标签、支持代理与非代理下载)
JS 下载 URL 链接文件(点击按钮、点击a标签、支持代理与非代理下载)
485 0
|
4月前
Jsoup获取url所有链接
Jsoup获取url所有链接
19 1
|
4月前
|
文字识别 算法 API
视觉智能开放平台产品使用合集之在调用接口传入的图片URL参数,文件在本地或者非上海地域OSS链接,该怎么办
视觉智能开放平台是指提供一系列基于视觉识别技术的API和服务的平台,这些服务通常包括图像识别、人脸识别、物体检测、文字识别、场景理解等。企业或开发者可以通过调用这些API,快速将视觉智能功能集成到自己的应用或服务中,而无需从零开始研发相关算法和技术。以下是一些常见的视觉智能开放平台产品及其应用场景的概览。
|
4月前
|
Windows
iis配置http重定向302转发get请求并去掉最后的斜杠/ iis重定向 iis去除url最后的斜杠 iis重定向链接斜杠(已解决)
iis配置http重定向302转发get请求并去掉最后的斜杠/ iis重定向 iis去除url最后的斜杠 iis重定向链接斜杠(已解决)
91 0
|
Web App开发
谷歌直链下载云盘数据集,使用谷歌云盘生成直接下载的url,示例: NeRFStudio-nerfacto默认训练数据集poster下载,nerfstudio 数据集下载链接
谷歌直链下载云盘数据集,使用谷歌云盘生成直接下载的url,示例: NeRFStudio-nerfacto默认训练数据集poster下载,nerfstudio 数据集下载链接
622 0
谷歌直链下载云盘数据集,使用谷歌云盘生成直接下载的url,示例: NeRFStudio-nerfacto默认训练数据集poster下载,nerfstudio 数据集下载链接
|
存储 JavaScript
vue本地存储、获取自定义data-id、获取链接url参数、页面跳转返回、修改页面title
vue本地存储、获取自定义data-id、获取链接url参数、页面跳转返回、修改页面title
|
移动开发 JavaScript
js对H5链接url进行解密实现过程(vue)
js对H5链接url进行解密实现过程(vue)
163 0
下一篇
无影云桌面