文档章节

小灰学习大数据——大数据算法探索(1)

阿亮学长123
 阿亮学长123
发布于 2017/01/08 19:36
字数 1255
阅读 53
收藏 1

  小灰学习大数据主要是针对大数据的面试题和笔试题分析,学习来写的。希望能让自己有提示,也能帮助别人。废话不多说,上题了。

  • 问:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

​​​​​​​  首先看到题目开始分析,50亿个url,一个64字节是多大呢?

我们先来计算,64/1024=0.0625bit一个url.     0.0625*50亿约等于320G.这么看挺大的所以不可能将其完全加载到内存中处理,考虑采取分而治之的方法。好有这个思路,我们提出以下方案。

方案1:将大文件分成能够被内存加载的小文件。

前面分析每个文件的大小为50G×64=320G,远远大于内存限制的4G。所以

s 遍历文件a,对每个url求取 ,然后根据所取得的值将url分别存储到1000个小文件(记为 )中。这样每个小文件的大约为300M。

s 遍历文件b,采取和a相同的方式将url分别存储到1000各小文件。这样处理后,所有可能相同的url都在对应的小文件中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

s 求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

方案2:内存映射成BIT最小存储单元。(网上看的,所以我准备弄懂它)

如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。

  首先,我们来看看什么事Bloom filter?

Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。

上过数据结构我们知道,单一哈希函数发生冲突的概率太高。Hash表冲突的各种解决方法,若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。所以我们用Bit-Map方法,建立一个BitSet,将每个URL经过多个哈希函数映射到某一位。下面来看看具体做法

  1. 创建一个m位BitSet,先将所有位初始化为0,然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i,str),且h(i,str)的范围是0到m-1

                       图1.Bloom Filter加入字符串过

 

    

  •    2.检查该bitset字符串是否存在

  对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后检查BitSet的第h(1,str)、h(2,str)…… h(k,str)位是否为1,若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1,则“认为”字符串str存在; 若一个字符串对应的Bit不全为1,则可以肯定该字符串一定没有被Bloom Filter记录过。(这是显然的,因为字符串被记录过,其对应的二进制位肯定全部被设为1了)

  但是若一个字符串对应的Bit全为1,实际上是不能100%的肯定该字符串被Bloom Filter记录过的。(因为有可能该字符串的所有位都刚好是被其他字符串所对应)这种将该字符串划分错的情况,称为false positive 。

  • 3.哈希表和表长参数选择

    (1)哈希函数选择

         哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数。

       (2)Bit数组大小选择 

         哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考文献1。该文献证明了对于给定的m、n,当 k = ln(2)* m/n 时出错的概率是最小的。

参考文献1:http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

 

© 著作权归作者所有

阿亮学长123
粉丝 12
博文 31
码字总数 14762
作品 0
南京
程序员
私信 提问
大数据开发学习的内容介绍,成都大数据培训机构哪里好?

大数据开发培训已经成为了越来越多人的选择,大数据开发工程师也是各公司争相争夺的金领人才之一了,在当今科技发展非常迅速的社会里,越来越多人把职业规划投向了大数据开发。这里为大家整理...

加米谷大数据
2018/07/17
7
0
2018最炙手可热的行业--大数据就业方向和学习路线图详解!

随着国家对大数据政策的倾向们越来越多的人听说过这个名词,但是对它都是可能也是一知半解,今天小编精心为大家整理了大数据相关的所有知识,以及大数据学习的一些资料,希望对大家有所帮助。...

数据分析v
2018/11/06
0
0
2019年最炙手可热的大数据行业学习路线指导

随着国家对大数据政策的倾向越来越多的人听说过这个名词,但对它都可能也是一知半解,今天小编精心为大家整理了大数据相关的所有知识,以及大数据学习的一些资料,希望对大家有所帮助。 什么...

大数据技术
01/10
0
0
大数据开发入门你必须知道的事情

昨天和三个学计算机专业的学生聊天时聊到了大数据开发方面的话题,他们三个人中,有两个已经进入企业开始工作,另外一个还是大二学生,但已经开设了自己的工作室。他们都是从事程序开发方面工...

adnb34g
2018/06/15
0
0
在人工智能爆发前,带你走近它的背后推手

(原标题:在人工智能爆发前,带你走近它的背后推手) 摘要: 很多人认为,经过多年的积累,人工智能技术已处于爆炸式增长的前夕——也许他们的判断没错,但作为信息科技领域的从业者,我和同...

钛媒体
2016/09/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 我,小小编辑,食人族酋长

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享娃娃的单曲《飘洋过海来看你》: #今日歌曲推荐# 《飘洋过海来看你》- 娃娃 手机党少年们想听歌,请使劲儿戳(这里) @宇辰OSC...

小小编辑
今天
525
10
MongoDB系列-- SpringBoot 中对 MongoDB 的 基本操作

SpringBoot 中对 MongoDB 的 基本操作 Database 库的创建 首先 在MongoDB 操作客户端 Robo 3T 中 创建数据库: 增加用户User: 创建 Collections 集合(类似mysql 中的 表): 后面我们大部分都...

TcWong
今天
28
0
spring cloud

一、从面试题入手 1.1、什么事微服务 1.2、微服务之间如何独立通讯的 1.3、springCloud和Dubbo有哪些区别 1.通信机制:DUbbo基于RPC远程过程调用;微服务cloud基于http restFUL API 1.4、spr...

榴莲黑芝麻糊
今天
15
0
Executor线程池原理与源码解读

线程池为线程生命周期的开销和资源不足问题提供了解决方 案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。 线程实现方式 Thread、Runnable、Callable //实现Runnable接口的...

小强的进阶之路
昨天
40
0
maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
昨天
50
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部