算法之大数据

参考链接

思想

• 哈希函数可以把数据按照种类均匀分流
• 布隆过滤器用于集合的建立与查询，并可以节省大量空间
• 一致性hash解决数据服务器的负载管理问题
• 利用并查集结构做岛问题的并行计算、
• 位图解决某一范围上数字的出现情况，并可以节省大量空间
• 利用分段统计思想、并进一步节省空间
• 利用堆、外排序来做多个处理单元的结果合并

实践

出现次数最多的数字

• 2GB内存，在20亿个整数中找到出现次数最多的数

  • hash分流+hash词频统计

    用哈希表对出现的每一个数做词频统计，哈希表的key是某一个数，value是这个数出现的次数。

    • 20亿的级别，词频统计时，value为int型，最大出现次数20亿级可以存放。key和value一共需要8B，20亿个整数就是大概需要16GB的内存，在最坏情况下，内存是明显不够用的。将20亿个数的大文件用哈希函数分成16个小文件，根据哈希函数的性质，同一个数不可能被哈希到不同的小文件上，同时每个小文件中不同的数一定不会大于2亿种，假设哈希函数足够好。然后对每一个小文件用哈希表来统计其中每种数出现的次数，这样就得到16个小文件中各自出现次数最多的数，还有各自的次数统计。接下来只要选出这16个小文件各自的第一名中谁出现的次数最多。

  • 计数排序

    在一定范围内，参照计数排序，将数字值作为数组的下标，出现次数作为数组的值。

• 40亿个整数

  • hash分流+hash词频统计

    40亿的级别，词频统计时，以-2^31为初始值，最大出现次数40亿级可以存放。

• 80亿个整数

  • hash分流+hash词频统计

    80亿的级别，词频统计时，一边遍历一遍判断，如果在统计的过程中，发现某个 key 出现的次数超过了 40 亿次，直接把这个 key 返回

未出现的数字

• 32位无符号整数的范围是0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数?

  • 位图

    该题无符号整数的范围为0 到 2^32-1，无符号整数的个数为40亿个。
    想要将范围上的所有数字存储在 bit 数组上。所需的数组长度是2^32，需要的内存为232/8（Byte）约等于512M左右，遍历该文件将出现的数所对应的bit 位变成1，剩下为0的位置对应的数就是没有出现过的数。

• 内存限制为3KB，但是只用找到一个没出现过的数即可

  • 无符号整型数组 + 范围统计

    3KB可以生成无符号整型数组为 3*1024/4=768。找到一个最接近这个数的2的某次方，即512.生成长度为512整型数组arr，该数组的每一个索引代表一个范围，范围长度为 2^32/512 = 2^23=8388608。例如，0代表0~8388607，1代表8388608~16777215,…。遍历该文件将每个数出现在对应数组索引范围的数量++，即该范围的词频++，例如有一个数9，9除以8388608 = 0 所以arr[0]++。找到词频出现最少的范围再分成512份继续，最后总能找到一个没有出现的数。

• 使用有限几个变量，但是只用找到一个没出现过的数即可

  • 二分法

    将 2^32 二分，遍历文件 使用变量统计词频，将少于2^32/2的范围再次二分，依次循环总能找到一个未出现的数

出现两次的数字

• 32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。

  • hash分流+hash词频统计

    使用HashTable做词频统计器，一条记录8Byte = key(4字节)+value(4字节)，1GB可以存储102410241024/8 = 227条记录。那么40亿条记录要使用Hash分流为4000000000/227约等于30个小文件，在每个小文件中找到出现两次的数即可。

  • 位图

    使用两个bit位来表示数量 00代表出现过0次 01代表出现过一次 10代表出现过2次 11代表出现过>2次
    总共需要2^32*2bit位 1GB的内存可以实现。

• 可以使用最多10KB的内存，怎么找到这40亿个整数的中位数?

  • 无符号整型数组 + 范围统计

    3KB可以生成无符号整型数组为 3*1024/4=768。找到一个最接近这个数的2的某次方，即512.生成长度为512整型数组arr，该数组的每一个索引代表一个范围，范围长度为 2^32/512 = 2^23=8388608。例如，0代表0~8388607，1代表8388608~16777215,…。遍历该文件将每个数出现在对应数组索引范围的数量++，即该范围的词频++，例如有一个数9，9除以8388608 = 0 所以arr[0]++。从arr[0]开始加，一直加到20亿就可以知道中位数出现在哪一个范围中，将这个范围再分512份，不断缩小范围，最后找到中位数

重复的URL

• 有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL

  • hash分流+hash词频统计

  • 使用布隆过滤器（有失误率，源于hash冲突）

    如果使用布隆过滤器的话，100亿个数据也就是需要100亿长度的bit数组，该数组的大小10000000000/8/1024/1024/1024 大概是1GB多 。遍历文件，每个数据记录hash值取模数组长度，如果当前bit位已经是1，说明重复，记录下来。
    注意：bit数组的长度是根据内存限制条件来的，如果内存大一点的话就可以整的长一点，避免布隆过滤器的失误概率。要是内存足够大完全可以使用词频统计器了(精准寻找)。

  • 使用hash函数分流（有失误率，源于hash冲突）
    计算100亿个数据的hash值并使用1000取模，将这些数据分为1000块，由于hash函数的性质重复的URL一定会分到同一块中，再在每个块中求重复即可。

• 某搜索公司一天的用户搜索词汇是海量的(百亿数据量)，请设计一种求出每天热门Top100词汇的可行办法

  • hash分流+hash词频统计+堆

    先使用hash分流到 n个小文件中。使用hashTable记录每个小文件的词频并根据词频组成大根堆。维护一个包含n个小文件堆顶的总堆。总堆出一个，对应小文件减少一个，将该文件第二大的加入总堆

• 现在有一个100亿条url的黑名单记录，每条 url 平均 64 字节。此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中

  • 位图

    优点：空间不随集合内元素个数的增加而增加。它的存储空间计算方式是找到所有元素里面最大的元素（假设为 N ），因此所占空间为(N/8)Byte,位图中每个位置只占1个bit。

    缺点：空间复杂度随集合内最大元素增大而线性增大。

  • 布隆过滤器

排序

• 2GB内存，对20亿个整数进行排序

  • hash分流+数组排序

    一个int数占4个字节，20亿个需要80亿字节，大概占用8GB的内存，而计算机只有2GB的内存，可以分为4个小文件，内排序后合并

  • hash分流+hash词频统计+堆

    使用HashTable做词频统计器，一条记录8Byte = key(4字节)+value(4字节)，2GB可以存储2^1024 ^1024*1024/16= 2^26条记录（除以16是因为HashTable索引的维护还需要一定空间给足，也可以除以100，200，只要比8大就行），有符号整数的范围是 -2^31 ~ 2^31-1 ，因此可以将整个范围分为2^(32) /2^(26) = 64块。从最小的范围开始使用HashTable做词频统计器并维护一个小根堆并依次输出，把总的文件过24遍就能完成（每次只关注一个范围上的数）

  • 计数排序

Topk问题

• 1g内存，20亿个数字中最大或最小的m个数字
  • hash分流+数组排序
  • 堆排序topk

总结