面试所需的海量数据处理

关于海量数据处理问题，从最近的采访中可以看出，这是一个经常被问到的问题. 本文基于实际的采访问题，总结了用于海量数据处理的常用算法，并提出了解决这些实际采访问题的方法.

所谓的海量数据处理无非就是基于海量数据的存储，处理和操作. 重要的是数据量太大，因此要么无法在短时间内快速解决，要么数据太大而无法一次加载到内存中.

在时间上，我们可以使用具有适当数据结构的巧妙算法，例如Bloom过滤器/哈希/位图/堆/三叉树.

对于空间，只有一种方法: 大大小小的，分而治之（哈希映射）.

布鲁姆过滤器（BF）是具有高空间效率的随机数据结构. 它使用位数组非常简洁地表示集合，并可以确定元素是否属于此集合. 这是一种用于判断元素是否存在于集合中的快速概率算法. Bloom Filter可能有错误的判断，但不会错过判断. 也就是说，Bloom Filter判断元素不再聚合，绝对不存在. 如果集合中存在判断元素，则存在判断错误的可能性. 因此，Bloom Filter不适合那些“零错误”应用程序.

在可以容忍低错误率的应用程序中，与其他常见算法（例如哈希，半搜索）相比，Bloom Filter大大节省了空间.

它可用于实现数据字典，判断数据权重或找到集合的交集

具体参考: 用于数据处理的Bloom Filter的详细说明

哈希，一般翻译为“哈希”，也有直接音译为“哈希”，即任何长度的输入（也称为预映射，前映像），通过哈希算法转换成一个固定长度的输出是哈希值. 这种转换是一种压缩映射，也就是说，哈希值的空间通常比输入的空间小得多. 可以将不同的输入散列到相同的输出中，并且不可能从散列值唯一地确定输入值. 简而言之，它是一种将任意长度的消息压缩为一定长度的消息摘要的功能.

具体参考文献: XI. 从头到尾分析哈希表算法

所谓的位图是使用位标记与元素相对应的值. 由于使用Bit作为存储数据的单位，因此可以大大节省存储空间.

如果尚未了解什么是位图，那么让我们看一个具体的示例，假设我们要在0-7（It，it）中对5个元素（4,7,2,5,3）进行排序此处假定这些元素不再重复）. 然后我们可以使用位图的方法来达到排序的目的. 表示8个数字，我们只需要8位（1字节）. 首先，我们打开1Byte空间并将这些空间中的所有Bits设置为0（如下所示）:

然后遍历这5个元素，首先第一个元素为4，然后对应于4的位置为1（当然，您可以操作p +（i / 8）|（0x01 <<（i％8））涉及大端和小端的情况，默认情况下为大端），因为它从零开始，所以第五个位置应该是一个（如下所示）:

然后处理第二个元素7，将第八个位置设置为1，然后处理第三个元素，直到最终处理完所有元素，并将对应位置设置为1，将这次位的状态如下:

具体参考: 数据结构: 位图方法

堆是一种特殊的二叉树海量数据处理方案，具有以下两个属性

1）每个节点的值大于（或小于其最小堆）其子节点的值

2）树完全平衡，最后一层的叶子都在最左边. 这定义了最大堆.

下图使用数组表示堆:

下面有诸如at，cn和com之类的关键字，如何构建特里树？

从上图中，我们或多或少可以找到一些更有趣的功能.

首先: 根节点不包含字符，除根节点之外的每个子节点都包含一个字符.

第二个: 从根节点到某个节点，路径上传递的字符连接在一起，这是与该节点相对应的字符串.

第三: 每个单词的公共前缀另存为字符节点.

适用范围:

前缀统计信息，词频统计信息.

具体参考: 6天吃树的结构-第五天的特里树

适用范围:

大数据排序，重复数据删除

**基本原理和要点: **

两个独立的外部排序阶段:

1）首先，根据存储器的大小，外部存储器上包含n条记录的文件被分为几个子文件或长度为L的段. 将它们依次读入存储器并使用有效的内部排序来对它们进行排序，然后重写将排序后的单词文件存储到外部存储器中. 这些子文件通常称为合并段.

2）逐段合并合并的段，以便合并的段从小到大逐渐增加，直到获得整个有序文件.

外部排序的优化方法: 排列选择，失败者树原理，最优合并树

具体参考: 选择替换+失败者树以进行外部排序

算法: 分而治之+哈希

1. 该IP地址最多具有2 ^ 32 = 4G的值，因此无法完全加载到内存中进行处理；

2. 您可以考虑“分而治之”的思想，根据IP地址的Hash（IP）24值，将大量IP日志存储到1024个小文件中. 这样，每个小文件最多包含4MB IP地址；

3. 对于每个小文件，您可以建立一个哈希表，以IP为键，出现次数为值，并同时记录出现次数最多的IP地址；

4. 可以得到1024个小文件中出现次数最多的IP，然后按照常规的排序算法获得出现次数最多的IP.

可以在内存中进行处理，这是典型的Top K算法

算法: hashmap + heap

1. 首先对这批海量数据进行预处理，并使用哈希表在O（N）时间内完成统计；

2. 使用堆的数据结构查找Top K，时间复杂度为O（N * logK）.

或者: 使用一棵trie树，关键字字段存储查询字符串的出现次数，而没有出现为0. 最后，使用最少10个元素的推入来对出现频率进行排序.

算法思想: 分治+哈希统计+堆排序

1. 顺序读取文件，对于每个单词x，取hash（x）％5000，然后根据此值保存到5000个小文件（标记为x0，x1，... x4999）. 因此，每个文件约为200k. 如果某些文件的大小超过1M，则可以继续进行类似的划分，直到通过分解获得的小文件的大小不超过1M.

2. 对于每个小文件，使用trie tree / hash_map计数每个文件中出现的单词以及相应的频率.

3. 取出出现频率最高的100个单词之后（可以使用具有100个节点的最小堆），然后将100个单词和相应的频率保存到文件中，以便再获得5000个文件. 最后一步是合并这5000个文件（类似于合并排序）.

选项1:

算法思想: 分治+哈希统计+堆排序

顺序读取10个文件，然后根据hash（query）的结果将查询写入另外10个文件中. 这样，每个新生成的文件的大小也大约为1G，并且根据上述思想继续划分大于1G的文件.

找到一台具有大约2G内存的机器，并使用hash_map（query，query_count）来计算每个查询的出现次数. 使用快速/堆/合并排序按出现次数进行排序. 将排序的查询和相应的query_cout输出到文件. 这将产生10个排序文件（标记为）.

合并并排序这10个文件（内部排序和外部排序的组合）.

选项2:

算法: hashmap + heap

通常，查询的总数是有限的，但是重复的次数相对较大. 可以一次将所有查询添加到内存中. 这样，我们可以使用trie tree / hash_map直接计算每个查询的出现次数，然后根据出现的次数进行快速/堆/合并排序.

解决方案1: 可以估计每个文件的大小为5G×64 = 320G，比4G内存限制大得多. 因此，不可能将其完全加载到内存中进行处理. 考虑分而治之的方法.

**算法思想: 分而治之+哈希统计**

遍历文件a，为每个URL找到hash（url）00，然后根据获得的值将URL存储到1000个小文件（表示为a0，a1，...，a999）中. 这样，每个小文件大约为300M.

遍历文件b，并以与a相同的方式将url存储到1000个小文件（表示为b0，b1，...，b999）. 以这种方式处理后海量数据处理方案，所有可能的相同URL都位于相应的小文件（a0vsb0，a1vsb1，...，a999vsb999）中，并且彼此不对应的小文件不能具有相同的URL. 然后，我们只要求在1000对小文件中使用相同的URL.

在每对小文件中查找相同的URL时，可以将其中一个小文件的URL存储在hash_set中. 然后遍历另一个小文件的每个URL，以查看它是否在刚刚构造的hash_set中. 如果是，则为通用网址，可以将其存储在文件中.

选项2: 如果允许一定的错误率，则可以使用Bloom过滤器，并且4G内存可以大致代表340亿位. 使用Bloom过滤器将其中一个文件的url映射到这340亿位，然后一个一个地读取另一个文件的url，并检查它是否与Bloom过滤器相同. 如果是，则该网址应为通用网址（请注意会有一定的错误率）.

使用2位图（每个位分配2位，00表示不存在，01表示出现一次，10表示多次，11表示无意义），总共需要2 ^ 32 * 2位= 1 GB内存，并且可以接受的. 然后扫描这2.5亿个整数以查看位图中的相应位. 如果00更改为01，01更改为10，而10保持不变. 描述完成后，检查位图并输出与01对应的整数.

解决方案1: 申请512M内存，一位代表一个无符号的int值. 读入40亿个数字，设置对应的位，读入要查询的数字，检查对应的位是否为1，其中1表示存在，0表示没有.

选项2: 由于2 ^ 32超过40亿，因此可能包含或可能不包含给定的数字；

在这里，我们用32位二进制数表示40亿个数字中的每个数字

假设这40亿个数字最初放置在文件中.

然后将40亿个数字分为两类:

1. 最高位是0

2. 最高位是1

将这两种类型写入两个文件，其中一个包含<= 20亿，另一个包含> = 20亿（相当于减半）；

与要搜索的号码的最高位数进行比较，然后输入相应的文件并再次搜索

然后将该文件分为两类:

1. 下一个最高位是0

2. 下一个最高位是1

将这两个类别写入两个文件，其中一个包含<= 1十亿，另一个包含> 10亿（相当于减半）；

与要搜索的号码的倒数第二位比较，然后输入相应的文件并再次搜索.

.......

以此类推，您可以找到它.

海量数据处理算法概述

十个海量数据处理面试题和十个方法总结

教您如何快速消除: 99％的海量数据处理面试问题

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-246787-1.html