[传输]数据处理中面试问题的方法

百度NeuroIPS全球顶级冠军团队将于7日带领您练习从零开始的强化学习！ >>>

处理海量数据问题时，无非是:

分区和规则/哈希映射+哈希统计+堆/快速/合并排序；

花朵过滤器/位图；

Trie树//反向索引；

外部排序；

Hardoop / mapreduce进行分布式处理.

本文的下一部分将详细介绍这五个方法模式以及相应的海量数据处理面试问题.

键1，划分和征服/哈希映射+哈希统计+堆/快速/合并排序

1. 大量的日志数据，提取出某天访问次数最多的IP.

由于它是海量数据处理，因此可以想象给我们的数据必须是海量数据. 鉴于海量数据，我们该如何进行？是的，无非就是分治制/哈希映射+哈希统计+堆/快速/合并排序. 坦率地说，它首先是映射，然后是统计，最后是排序:

分割和征服/哈希映射: 对于过大且内存有限的数据，智能是: 将大文件转换为（模映射）小文件，即16字策略: 大大小小，分解，缩小规模并一一解决

哈希统计: 将大文件转换为小文件时，我们可以使用常规的哈希图（ip，值）执行频率统计.

堆/快速排序: 完成统计后，进行排序（可以采用堆排序）以获得最多的IP.

具体地说，是: “第一天是今天，将访问百度日志中的IP取出并逐个写入大文件. 请注意，该IP是32位的，有最多2 ^ 32个IP. 您还可以使用映射方法（例如模块1000）将整个大文件映射到1000个小文件，然后在每个小文本中找到频率最高的IP（您可以使用hash_map用于频率统计，然后找出频率最高的IP）和相应的频率. 然后，在这1000个最大的IP中，找到您想要的频率最高的IP. ”-十个海量数据处理访谈问题十余种方法. 总结一下.

但是，如果数据量较小，是否可以立即将其加载到内存中？例如，以下问题说虽然有1000万个查询，但是由于重复率很高，实际上它只有300万个查询，每个Query255Byte，所以我们可以考虑将它们全部存储在内存中，现在只需要合适的数据即可结构，在这里，哈希表绝对是我们的优先选择. 好，请参阅问题2:

2. 搜索引擎通过日志文件记录用户用于每次搜索的所有搜索字符串，每个查询字符串的长度为1-255字节.

假设当前有1000万条记录（这些查询字符串的重复率相对较高，尽管总数为1000万，但是如果删除重复项，则不超过300万. ）一个查询字符串，说明查询的用户越多，它越受欢迎. ）请计算10个最受欢迎的查询字符串，并且所需的内存不能超过1G.

如前所述，数据相对较小，放弃了分而治之/哈希映射方法，直接进行哈希统计，然后进行排序. 所以，

哈希统计信息首先对这批海量数据进行预处理（维护一个哈希表，其键为查询字符串，值为查询的出现次数，即hashmap（Query，Value），如果该字符串，则每次读取一个查询不在表中，则添加字符串并将Value设置为1. 如果字符串在表中，则将字符串的计数加1最后，我们在O（N）时间复杂度以内桌子;

堆排序: 第二步是借助堆的数据结构找到Top K，时间复杂度为N’logK. 也就是说，借助堆结构，我们可以在日志级别的时间内搜索和调整/移动. 因此，请维护一个小的根堆，其大小为K（在本主题中为10），然后遍历3百万个Query，并将其与根元素进行比较. 因此，我们最终的时间复杂度为: O（N）+ N'* O（LogK），（N为1000万，N'为300万）.

不要忘记本文描述的堆排序思想: “保持最小的k个元素堆，即使用容量为k的最小堆存储所遍历的前k个数字，并假设它们是最大的. k的数量，在构建堆之后取O（k），并调整堆（耗时的O（logk）），则有k1> k2> ... kmin（kmin设置为small中的最小元素）继续遍历序列，一次遍历一个元素x，与堆的顶部元素相比，如果x> kmin，则更新堆（时间logk），否则不更新堆. 这样，总时间为O（k * logk +（nk）* logk）= O（n * logk）. 这种方法得益于每个操作的时间复杂性，例如在堆中搜索，即logk. ” 3，找到最小的k数.

当然，您也可以使用特里树. 关键字字段存储查询字符串的出现次数，没有出现为0. 最后，使用最少10个元素的推入来对出现频率进行排序.

从以上两个示例问题开始，除法和征服+哈希统计+堆/快速排序此例程，我们开始感到不舒服. 在下面，多做一些并验证更多. 请参阅问题3:

3. 有一个大小为1G的文件，其中每行是一个单词，该单词的大小不超过16个字节，并且内存限制大小为1M. 返回频率最高的100个单词.

文件很大，内存有限. 我能做什么？我还可以做些什么？没什么

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

哈希统计: 对于每个小文件，请使用trie tree / hash_map计数每个文件中出现的单词和相应的频率.

堆/合并排序: 取出频率最高的100个字（可以使用具有100个节点的最小堆），并将100个字和相应的频率保存到文件中，从而获得5000个文件. 最后一步是合并这5000个文件（类似于合并排序）.

4. 有10个文件，每个文件为1G，每个文件的每一行存储用户的查询，并且每个文件的查询可以重复. 要求您根据查询频率进行排序.

直接:

哈希映射: 依次读取10个文件，并根据hash（query）的结果将查询写入另外10个文件（表示为）. 这样，每个新生成的文件的大小约为1G（假设哈希函数是随机的）.

哈希统计信息: 查找内存约为2G的计算机，并使用hash_map（query，query_count）来计算每个查询的出现次数. 注意: hash_map（query，query_count）用于计算每个查询的出现次数，而不是存储其值. 如果出现一次，请计数+1.

堆/快速/合并排序: 使用“快速/堆/合并”排序按出现次数进行排序. 将排序的查询和相应的query_cout输出到文件. 这将产生10个排序的文件（标记为）. 合并并排序了这10个文件（内部排序和外部排序相结合）.

此外，有两种方法可以解决此问题:

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

选项3: 类似于选项1，但是在完成哈希并将其划分为多个文件之后，可以使用分布式体系结构（例如MapReduce）将其移交给多个文件进行处理，最后合并.

5. 给定两个文件a和b，每个文件存储50亿个url，每个url占用64个字节，并且内存限制为4G. 让您找出a和b文件的通用网址吗？

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

分隔和征服/哈希映射: 遍历文件a，找到每个url，然后根据获得的值将url存储到1000个小文件（记录为）中. 这样，每个小文件约为300M. 遍历文件b，并以与a相同的方式将url存储到1000个小文件（表示为）中. 经过此处理后，所有可能的相同URL都位于相应的小文件（）中，并且不对应的小文件不能具有相同的URL. 然后，我们只要求在1000对小文件中使用相同的URL.

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

好吧，这是第一种方法: 划分并征服/哈希映射+哈希统计+堆/快速/合并排序，然后查看最后三个问题，如下所示:

8. 如何在海量数据中找到重复次数最多的数据？

方案1: 首先进行哈希处理，然后找到映射到小文件中的模块，在每个小文件中找到重复次数最多的模块，并记录重复次数. 然后在上一步获得的数据中找到重复次数最多的一个（有关详细信息，请参阅上一个问题）.

9，数千万或数亿的数据（重复），并计数出现次数最多的N个数据.

方案1: 数千万或数亿的数据，当前机器的内存应该能够保存. 因此，请考虑使用hash_map /搜索二叉树/红黑树等来统计统计信息. 然后检索最频繁出现的数据的前N个出现，这可以使用问题2中提到的堆机制来完成.

10. 一个文本文件，大约10,000行，每行一个单词. 需要计算最频繁出现的前10个单词. 请思考并进行时间复杂度分析.

选项1: 此问题考虑时间效率. 特里树用于计算每个单词的出现次数，时间复杂度为O（n * le）（le表示单词的标准长度）. 然后，找到最常出现的前10个单词，可以用堆来实现. 如上一个问题所述，时间复杂度为O（n * lg10）. 因此，总时间复杂度是O（n * le）和O（n * lg10）中的较大者.

接下来海量数据处理方案，让我们看看第二种方法，位图.

有关什么是Bloom过滤器，请参阅本文: 用于数据处理的Bloom过滤器的详细说明.

适用范围: 可用于实现数据字典，判断数据权重或查找集合的交集

基本原理和要点:

对于原理很简单，位数组+ k个独立的哈希函数. 将与哈希函数相对应的值的位数组设置为1，如果在搜索过程中发现与哈希函数相对应的所有位均为1，则很明显，此过程不能保证搜索结果为100％正确. 同时，不支持删除已插入的关键字，因为该关键字的相应位会影响其他关键字. 因此，简单的改进就是计数布隆过滤器，该过滤器使用计数器阵列而不是位阵列来支持删除.

另一个重要的问题是如何根据输入元素的数量n确定位数组m的大小和哈希函数的数量. 当哈希函数的数量为k =（ln2）*（m / n）时，错误率最小. 当错误率不大于E时，m必须至少等于n * lg（1 / E）才能表示n个元素的任何集合. 但是m也应该更大，因为必须保证至少有一半的位数组为0，那么m应该> = nlg（1 / E）* lge大概是nlg（1 / E）1.44倍（lg表示基数2 of log）.

例如，我们假设错误率是0.01，那么m应该约为n的13倍. 所以k大约是8.

请注意，此处的m和n的单位不同，m是位的单位，n是元素数（准确地说，是不同元素数）的单位. 通常，单个元素的长度为许多位. 因此，通常可以节省使用Bloom过滤器内存的情况.

扩展:

布隆过滤器将集合中的元素映射到位数组. k（k是哈希函数的数量）映射位是否全部为1表示元素不在集合中. 计数布隆过滤器（CBF）将位阵列中的每个位扩展为计数器，从而支持元素删除操作. 频谱布隆过滤器（SBF）将其与收集元素的出现次数相关联. SBF使用计数器中的最小值来近似元素的频率.

问题示例: 给您两个文件A和B，每个文件存储50亿个URL，每个URL占用64个字节，并且内存限制为4G，从而使您可以找到A和B文件共有的URL. 那三个甚至n个文件呢？

根据此问题，让我们计算内存使用量. 4G = 2 ^ 32约为40亿* 8约为340亿，n = 50亿. 如果错误率是0.01，则大约需要650亿位. 现在可用的是340亿，相差不大，这可能会增加错误率. 此外，如果这些附加项是一一对应的，则可以将它们转换为ip，这非常简单.

同时，上面的第五个问题: 给定两个文件a和b，每个文件存储50亿个url，每个url占用64个字节，内存限制为4G，让您找到文件a，b共同的url？如果允许一定的错误率，则可以使用Bloom过滤器，4G内存可以代表340亿位. 使用Bloom过滤器将其中一个文件的url映射到这340亿位，然后一个一个地读取另一个文件的url，并检查它是否与Bloom过滤器相同. 如果是，则该网址应为通用网址（请注意会有一定的错误率）.

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