海量数据处理问题

╰+哭是因爲堅強的太久メ 2022-05-26 20:12 275阅读 0赞

## TOP N问题 ##

1.  如何在海量数据中找出重复最多一个。
    
     *  通过hash映射为小文件
     *  通过hash\_map统计各个小文件重读最多的并记录次数
     *  对每个小文件重复最多的进行建立大根堆
2.  上亿有重数据，统计最多前N个。
    
     *  内存存不下
     *  通过hash映射为小文件
     *  通过hash\_map统计各个小文件重读最多的并记录次数
     *  对每个小文件重复最多的进行建立大根堆并重复N次取走堆顶并重建堆操作
     *  内存存得下
     *  直接内存通过hash\_map统计并建大根堆
     *  重复N次取走堆顶并重建堆操作
3.  海量日志数据，提取出某日访问百度次数最多的那个IP（同1）。
    
     *  将IP % 1000映射到1000个小文件中
     *  相同IP会被映射到同一个文件
     *  不会出现累加和更大情况
     *  分1000次在内存处理小文件，得到频率最大IP（使用map统计）
     *  对这1000个IP建立大根堆
4.  1000w查询串统计最热门10个（同2）。
    
     *  同上
5.  1G的文件，里面1行1个不超过16字节的词。内存限制1M，返回频数最高前100（同2）。
    
     *  将单词 % 5000存入5000小文件
     *  平均各文件约200K
     *  对超过1M的文件继续分割直到小于200K
     *  使用map统计各个词出现的频率
     *  对5000词使用堆排序或归并排序

## 分布式TOP N问题 ##

1.  分布在100台电脑的海量数据，统计前十。
    
     *  各数据只出现在一台机器中
     *  先在独立机器得到前十
        
         *  若可以放入内存直接堆排序
         *  若不可全放入内存：哈希分块 -> map统计 -> 归总堆排
     *  再将100台计算机的TOP10组合起来堆排序
     *  同一元素可同时出现在不同机器中
     *  遍历所有数据，重新hash取模，使同一个元素只出现在单独的一台电脑中，然后采用上面方法先统计每台电脑TOP10再汇总起来

## 快速外排序问题 ##

1.  有10个1G文件，每行都是一个可重复用户query，按query频度排序。
    
     *  顺序读取十个文件并采取哈希，将query写入10个文件中
     *  通过hash\_map(query, count)统计每个query出现次数，至少2G内存
     *  通过得到的hash\_map中query和query\_count，对query\_count排序并将重新输出到文件中，得到已排序好的文件
     *  对十个文件进行归并排序（外排序）

## 公共数据问题 ##

1.  A,B两个文件各存放50亿url，每个为64Byte，限制内存4G找出公共url。
    
     *  对A和B两个大文件，先通过url % 1000将数据映射到1000个文件中，单个文件大小约320M（我们只需要检查对应小文件A1 V B1……，不对应小文件不会有相同url）
     *  通过hash\_set统计，把A1的url存储到hash\_set中，再遍历对应的B1小文件，检查是否在hash\_set中，若存在则写入外存。重复循环处理对应的1000个对。
2.  1000w有重字符串，对字符串去重。
    
     *  先hash分为多个文件
     *  逐个文件检查并插入set中
     *  多个set取交集

## 内存内TOP N问题 ##

1.  100w个数字找出最大100个。
    
     *  堆排序法
     *  建大根堆，取走堆顶并重建堆，重复100次
     *  快排法
     *  使用快速排序划分，若某次枢纽元在后10000时（具体情况具体分析），对后10000数据排序后取前100

## 位图法 ##

1.  在2.5亿数字中找出不重复的整数。
    
     *  使用2-Bit位图法，00表示不存在，01表示出现一次，10表示出现多次，11无意义。这样只需要1G内存。
     *  或者hash划分小文件，小文件使用hash\_set检查各个元素，得到的。
2.  如何在40亿数字中快速判断是否有某个数？
    
     *  位图法标记某个数字是否存在，check标记数组。