海量数据有限内存系列问题解决方案

🕗 发布于 2024-11-17 16:08 算法

1. 排序问题

有限数据充足内存：内存中有十万整数，对所有数据进行排序。

内部排序即可

单节点海量数据有限内存：某台机器有一个文件，文件中包含六十亿整数，一个整数一行，可用内存1G，对所有数据进行排序。

60 * 10 ^ 8 * 4 byte 约为 22.35 gb，无法直接加载至内存进行内部排序，需要采用外部排序方式。

读取该文件，每读取64MB数据就进行一次内部排序（如快排），然后将有序的64MB数据写入一个新的文件，依次类推，到最后会获得n个有序片段，其中前n-1个为64M数据，最后一个有可能不够64MB。
对上面的n个有序片段采用归并排序的思路进行归并，同时打开k个有序片段，分别从k个归并片段各读取一个整数，从中选择最小的整数，写入一个新文件，假设是第1个有序片段的整数被写入新文件，则该片段读取下一个整数，其他片段不读新的整数，再次比较获取新一个最小的整数，直到新文件写入128M大小后完成一个文件，然后新开一个文件，如果某个有序片段被读完了，那么读新的有序片段即可。
重复以上步骤直到归并为一个大文件。

多节点海量数据有限内存：64台机器，每台机器一个文件，文件中包含六十亿整数，一个整数一行，每台机器可用内存1G，对所有数据进行排序。

每台机器各自排序，参考上述单节点排序
跨节点归并，两两节点归并，2号节点将数据传输给1号节点，1号节点做本地排序，然后1号节点将排序的后半段数据传输给2号节点，以此类推，3号与4号节点等都可以同时操作
然后第二趟计算，1号和2号两者有序，3号和4号两者有序，可以以如下流程进行四个节点的排序，3号节点数据传输给1号节点，此时1号节点有两段数据的两个前半部分，基于双指针的思路从两部分数据中不断提取最小的数据到一个新的文件中，若其中一部分数据用完，取对应的后半段，例如，3号节点传输给1号节点的数据用完，就从4号节点传输数据到1号节点，由于现在是4个节点排序，故此时每完成1/4数据排序，要将这部分数据回传到对应节点，例如第一个1/4数据要存储到1号接待你，第二个1/4数据传输到2号节点，直到四个节点数据排序完成。
其余合并流程同理，直到分布式集群数据排序完成

2. 中位数问题

有限数据充足内存：内存中有十万整数，获取所有数据的中位数。

排序取中位数即可

单节点海量数据有限内存：某台机器有一个文件，文件中包含六十亿整数，一个整数一行，可用内存1G，获取所有数据的中位数。

方案一：外部排序后直接取中位数
方案二：分区，在某一个区中做内部排序然后取中位数

[0,1000)属于一个区间，[1000, 2000)属于一个区间，依次类推，将所有的数分到每一个区间中，每个区间一个文件
由此，根据数据总量以及每一个分区的数据总量，可以定位到中位数所在区间以及中位数在这个区间中的位置（是指该区间排序完成后的位置）
对该区间进行排序，直接获取中位数
方案二相比于方案一优化的点在于通过有序的区间减少了排序开销

多节点海量数据有限内存：64台机器，每台机器一个文件，文件中包含六十亿整数，一个整数一行，每台机器可用内存1G，，获取所有数据的中位数。

方案一：分布式排序，直接取中位数
方案二：？？？

3. Top-K问题

什么是TopK问题
从n个元素中，找到最大的k个元素。
例如，有数组 nums = [5,3,7,1,8,2,9,4,7,2,6,6]，找出其中最大的5个数
TopK问题的应用场景

搜索引擎：在搜索引擎中，Top-K问题可以用于返回用户查询的前K个最相关的搜索结果。
推荐系统：在电子商务网站或媒体流推荐中，可以使用Top-K问题来提供用户最感兴趣的产品或内容。
数据分析：在大数据分析中，Top-K问题可用于查找最频繁出现的元素或最高价值的数据点。
数据挖掘：在聚类和分类问题中，可以使用Top-K问题来选择具有最高重要性的特征或数据点。
排行榜：例如在美团店面排行、软件排行榜、富豪榜等场景中，需要用到Top-K问题来确定排名。
数据库查询优化：在数据库查询中，Top-K查询可以用来实现分页展示，例如在购物平台上搜索价格在一定范围内的衣服，系统会从价格最低开始扫描，一旦价格超过范围，查询就会终止。
机器学习模型：在处理预测结果时提取最可能的候选项，例如在分类问题中，找出概率最高的几个类别。
数据处理：在深度学习和数据处理中，经常需要对数据进行排序并提取最重要的部分，torch.topk函数能够快速找到给定张量中的最大或最小的K个元素。

有限数据充足内存：内存中有十万整数，获取所有数据中最大的一万个数且按照从大到小顺序返回。

方案一：快排后取k个元素

对n个元素从大到小排序，然后取出前k个元素即可

时间复杂度： $O (n l o g n)$

方案二：k趟冒泡

基于冒泡思想，从后往前冒泡，每趟冒泡将最大的元素移动到数组前面，k趟冒泡完成topk查找。

时间复杂度： $O (kn)$

方案三：容量为k的堆

先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的k个元素。
接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。
扫描完所有n-k个元素，最终堆中的k个元素，就是求的TopK。
时间复杂度： $O (n l o g k)$

BFPRT

https://zhuanlan.zhihu.com/p/291206708

单节点海量数据有限内存：某台机器有一个文件，文件中包含六十亿整数，一个整数一行，可用内存1G，获取所有数据中最大的一万个数且按照从大到小顺序返回。

方案一：排序，取前一万
方案二：遍历一万次文件，每次从中获取当前最大的那个数，取过的数不在计算入内
方案三：开一个容量一万的小根堆，不断从文件中读取元素，若该元素大于小根堆堆顶元素，就替换堆顶元素然后调整堆，直到处理完一遍元素。可以做多线程优化，例如开60个线程，每个线程处理一亿数据，每个线程维护一个容量为一万的堆，主线程负责将60个堆结果做合并，获取前一万。

多节点海量数据有限内存：64台机器，每台机器一个文件，文件中包含六十亿整数，一个整数一行，每台机器可用内存1G，获取所有数据中最大的一万个数且按照从大到小顺序返回。

方案一：分布式排序，取前一万
方案二：单节点开堆或者冒泡获取前一万结果，分布式节点将节点的前一万结果传输到集群中的某一个节点做合并出最终结果。

5. 频率Top-K问题

有限数据充足内存：内存中有十万字符串，每个字符串不超过255字节，获取所有数据中出现次数最多的前一万个字符串且按照出现次数从多到少返回。

哈希表、前缀树，适合有限种类数据

单节点海量数据有限内存：某台机器有一个文件，文件中包含六十亿字符串，一个字符串一行，可用内存1G，获取所有数据中出现次数最多的前一万个字符串且按照出现次数从多到少返回。

方案一：对每个字符串求哈希然后根据哈希值切分文件，每个小文件单独求频率，仅返回频率最高的10000个字符串，然后本地每个文件的结果合并获得本机器上的前一万个字符串
方案二：字符串排序，按序统计频率，开容量为10000的堆获取前一万结果。

多节点海量数据有限内存：64台机器，每台机器一个文件，文件中包含六十亿字符串，一个字符串一行，每台机器可用内存1G，获取所有数据中出现次数最多的前一万个字符串且按照出现次数从多到少返回。

方案一：单节点计算结果，多节点传输数据到某一个节点做reduce合并出结果。

6. 数据去重问题

有限数据充足内存：内存中有十万字符串，每个字符串不超过255字节，对所有字符串进行去重，每个重复出现的字符串仅保留一个。

哈希表、前缀树，适合有限种类数据

单节点海量数据有限内存：某台机器有一个文件，文件中包含六十亿字符串，一个字符串一行，可用内存1G，对所有字符串进行去重，每个重复出现的字符串仅保留一个。

方案一：求哈希然后切分文件，每个小文件单独求频率，仅返回频率最高的10000个字符串，然后本地每个文件的结果合并获得本机器上的前一万个字符串

多节点海量数据有限内存：64台机器，每台机器一个文件，文件中包含六十亿字符串，一个字符串一行，每台机器可用内存1G，对所有字符串进行去重，每个重复出现的字符串仅保留一个。

方案一：求哈希，根据哈希分组传输数据到指定节点，每个节点去重即可。

7. 数据求交集问题（并集、差集问题类似）

有限数据充足内存：内存中有两个数据块，每个数据块中包含十万整数且每个数据块各自数据无重复，求两个数据块中都有的元素。

集合结构求交集

单节点海量数据有限内存：某台机器有两个文件，每个文件包含六十亿整数且且每个文件中各自数据无重复，求两个文件中都有的元素。

方案一：哈希值切分文件，第一个文件的某一个哈希切片与第二个文件对应的哈希切片做集合操作

哈希值切分文件。例如对10000取模，第一个文件可以切分成1万个文件，第二个文件同样切分为1万个文件
将第一个文件的第i个片段文件以set结构存储，遍历第二个文件的第i个片段文件中每一个数据，判断是否在第一个文件中即可，依次类推，可以获取两个大文件的并集。
方案二：若允许一定错误率，可以使用布隆过滤器。

多节点海量数据有限内存：64台机器，每台机器两个文件，分别为a、b文件，文件中包含六十亿整数，一个整数一行，每台机器可用内存1G，64个a文件不含重复元素，64个b文件不含重复元素，求64个a文件与64个b文件两大块数据的并集。

方案一：哈希值切分数据，把数据传输到对应节点，分布式问题转化单个节点的问题，走单个节点的逻辑即可。

8. 数据存在性判断

有限数据充足内存：内存中有十万整数，判断某k个数分别是否存在于这十万整数中。

集合判断

单节点海量数据有限内存：某台机器有一个文件，文件中包含六十亿整数，一个整数一行，可用内存1G，判断某k个数分别是否存在于这六十亿数据中。

方案一：遍历查找
方案二：bitmap记录存在的数据
方案三：若允许一定误差，使用布隆过滤器

多节点海量数据有限内存：64台机器，每台机器一个文件，文件中包含六十亿整数，一个整数一行，每台机器可用内存1G，判断某k个数分别是否存在于这六十四*六十亿数据中。

方案一：每个节点遍历查找，每个节点传输存在性结果到某个集群节点做结果汇总。
方案二：单节点建立bitmap，每个节点传输存在性结果到某个集群节点做结果汇总。
方案三：若允许一定误差，使用布隆过滤器，每个节点传输存在性结果到某个集群节点做结果汇总。