如何在很大数量级的数据中（比如1个亿）筛选出前10万个最大值？
程序员文章站
2022-05-12 12:07:56
...
本人大三非计算机专业，自学web开发，前几天找实习面试php的时候面试官问我的算法题，没答上来本来准备最后问一下的，结果最后太紧张忘了问这题，回去之后没想到解法，希望知乎里大牛提供一个思路，什么语言都行＜(。_。)＞
=====================================================================
补充：初始是无序的，内存和磁盘并没说，我自己没有想明白这题的切入点也就没问在内存还是在磁盘，望能得到这两种情况都有的全面解答，多谢
1亿 = 100M 相对于现在的硬件来说是个很小的数，基本上可以都 fit 进内存。内存中找前 k 个数可以用 Quickselect 算法，一个类似 quicksort 的算法，平均复杂度是 O(N)。
如果总数据量更多，或者可用内存更小，可以把所有的数分成内存可以放下的多个部分，每个部分分别找前 k 个，最后把所有的数放在一起再找一次前 k，如果还放不下继续分堆。这个策略还可以让算法可以并行执行，有计算资源的时候降低整体执行时间。
这个算法比建一个大小为 k 的最大堆要快，因为后者最后得到的 k 个数是部分有序的，复杂度会变成 O(N log k)，而前者得到的前 k 个数是完全无序的。 题主学过数据结构否?有个叫最小堆的东西。
------------------------------------------------------------------------
内存有限，可以把1亿个数据放在磁盘上，此外，在内存开辟一个可以容纳10万个数据的最小堆。
每次从磁盘上读取一个数据，若最小堆未满，则直接放入最小堆中，调整堆使其符合最小堆的性质；若最小堆已满，则将这个数与最小堆根结点上的数值进行比较，若比根结点的数值大，则替换掉根结点上的值，然后重新调整最小堆使其符合最小堆的性质。
遍历完1亿个数据后，这个容量为10万的最小堆里面存放的就是前10万个最大值了。 好好回答一下吧。
首先对于1亿的数据量，要求不高的话，大可只使用一个最小堆来维护前10万个最大的数。
不妨设数的总数为N，需要选出的数为M，那么这种方法带来的时间复杂度为：
这个方法最大的缺点是没有并行计算。
如果比1亿数据量再大，比如到100亿这个量级，那么就需要使用并行计算了，下面我详细说一下我的思路。
1) 首先将这些数据随机分成K堆，不妨假设正好平均分配，时间复杂度为
。
2) 使用K个任务并行的选出每一堆的前M大的数，这一步的时间复杂度为
，此时生成了K组长度为M的有序序列。
3) 使用多路归并排序选出这K组序列的前M大的数，这一步的时间复杂度为
因此假设第2步并行完成，那么总体的时间复杂度就是
。至此算法得到了常数级别的优化。
但是还没完，注意到2)中每个序列都选了前M大的数，这个是可以继续改进的。
我们可以想象一种场景：2个桶里总共有10个球，球是随机分布的，规定一种操作可以从这2个桶里拿至多L个球，这时我们怎么确定这个L使得我们能够以一个我们能接受的概率拿到所有的球？
显然当L=10的时候，我们当然可以100%的拿到这全部球，但是开销太大了。由于球是随机分布的，可以知道10个球全部落入落入一个盒子里的概率非常的小，是
。因此我们可以先把这种请当当成一个中彩票的事件，先不管他，直接把L设成9。
既然我们牺牲了一部分可靠性降低了开销，那么为什么不能把L设的在低一点？究竟应该设多低？
这其实是另外的一个问题了，我认为为了解决这个问题不应该从L入手，而是我们设定一个最低能接受的可靠性概率P，找到最小的L满足我们要求的P即可。
因此我们可以使用如上方法优化2)。设我们要求的最低可靠性为P, 优化函数为
2) 使用K个任务并行的选出每一堆的前大的数，这一步的时间复杂度为
, 此时生成了K组长度为的有序序列。
我可以给出一个数
, 可以看出这个函数的威力。所以用这种方法，可以在实际中获得很多倍的速度提升。
但是必须解决的问题是可靠性问题，但这个问题其实很好办，只需要验证一下在3)时有没有把一个序列用尽，如果用尽了并且最后一个数不是这个序列里的最后一个数，那么说明这个序列的第
个数也可能出现在最坏的结果。那么最简单的做法就是再从这个序列中补上一部分数据，使得最后的答案时正确的。
所以这时我们得到了一个以P为成功率的算法，这个算法可能比未优化前快好多倍，但是有(1-P)的中奖概率。欣慰的是我们可以判断中没中奖，再不济就是抛弃这次的结果再跑一次未优化前的算法呗。 堆排序，+ 分而治之 m取前n
以取小为例吧。我喜欢小。
以数据总量，分：小、中、大，三种情况来分析。
1、小：全部读入内存，排序，取前n。
2、中：
2.1：分几次读入（次数为k=总数据/内存大小），分别排序、写回读入点。致全部读一遍。形成k个顺串（称之数据锥）。
2.2：各锥读取一节(量为内存/K)，到内存（称之：锥节）。
2.2：各锥节尖做比较，小的写到另一块内存区（称之输出缓区）。如，某锥缓节空，读该锥的下一节。
2.3：致输出缓存区满。
2.4：写到结果文件。
2.5：结果够，结束。否则，继续2.2。
3、大：
3.1：若干单机，做2.1到2.3，暂停。
3.2：另一单机，做总机。从各单机输出缓存区，读一节到总机内存区（称总锥节）。
3.3：各总锥节尖做比较，小的写到总机的另一块内存区（称之总输出缓存区）。如，某总锥节空，读该锥对应单机输出缓存的下一节。
3.4：总缓存区满，写到结果文件。
3.5：结果够，结束。否则，继续3.3。
对于数据量大的情形。做顺串是免不了的。
以上算法，结果够时，会提前结束。
而锥节，总归比较小。因此，可能用不着 @皆传 的中奖法。
虽然中奖法很好玩。 最小K个数，思路和这个很类似。 很久没有碰数据结构了，只能说下思维框架。
1.先遍历前10万个数字，放到一个有序数据结构中，并且记录下这组数的最小值B；
2.遍历后面1亿-10万个数字，取出一个数字A，和有序结构中的最小值B进行比较，如果大于最小值B，则A进入有序数组，最小值B退出有序数组；
3.重新计算有序数组的最小值B；
4.重复这个过程直到结束。
---------------------
遍历1亿个数字是无法缩短时间的，那么程序的性能就在于如何在10万个数字尽快找到最小值了。
这个是二叉树最擅长的问题，你在遍历的同时也已经完成了二叉树的排序和插入工作。
不好意思的是，我已经基本忘记二叉树怎么写了。o_o||
=====================================================================
补充：初始是无序的，内存和磁盘并没说，我自己没有想明白这题的切入点也就没问在内存还是在磁盘，望能得到这两种情况都有的全面解答，多谢
回复内容：
问题是在 N 个数中，找到前 k 个数。1亿 = 100M 相对于现在的硬件来说是个很小的数，基本上可以都 fit 进内存。内存中找前 k 个数可以用 Quickselect 算法，一个类似 quicksort 的算法，平均复杂度是 O(N)。
如果总数据量更多，或者可用内存更小，可以把所有的数分成内存可以放下的多个部分，每个部分分别找前 k 个，最后把所有的数放在一起再找一次前 k，如果还放不下继续分堆。这个策略还可以让算法可以并行执行，有计算资源的时候降低整体执行时间。
这个算法比建一个大小为 k 的最大堆要快，因为后者最后得到的 k 个数是部分有序的，复杂度会变成 O(N log k)，而前者得到的前 k 个数是完全无序的。 题主学过数据结构否?有个叫最小堆的东西。
------------------------------------------------------------------------
内存有限，可以把1亿个数据放在磁盘上，此外，在内存开辟一个可以容纳10万个数据的最小堆。
每次从磁盘上读取一个数据，若最小堆未满，则直接放入最小堆中，调整堆使其符合最小堆的性质；若最小堆已满，则将这个数与最小堆根结点上的数值进行比较，若比根结点的数值大，则替换掉根结点上的值，然后重新调整最小堆使其符合最小堆的性质。
遍历完1亿个数据后，这个容量为10万的最小堆里面存放的就是前10万个最大值了。 好好回答一下吧。
首先对于1亿的数据量，要求不高的话，大可只使用一个最小堆来维护前10万个最大的数。
不妨设数的总数为N，需要选出的数为M，那么这种方法带来的时间复杂度为：
这个方法最大的缺点是没有并行计算。
如果比1亿数据量再大，比如到100亿这个量级，那么就需要使用并行计算了，下面我详细说一下我的思路。
1) 首先将这些数据随机分成K堆，不妨假设正好平均分配，时间复杂度为
2) 使用K个任务并行的选出每一堆的前M大的数，这一步的时间复杂度为
3) 使用多路归并排序选出这K组序列的前M大的数，这一步的时间复杂度为
因此假设第2步并行完成，那么总体的时间复杂度就是
但是还没完，注意到2)中每个序列都选了前M大的数，这个是可以继续改进的。
我们可以想象一种场景：2个桶里总共有10个球，球是随机分布的，规定一种操作可以从这2个桶里拿至多L个球，这时我们怎么确定这个L使得我们能够以一个我们能接受的概率拿到所有的球？
显然当L=10的时候，我们当然可以100%的拿到这全部球，但是开销太大了。由于球是随机分布的，可以知道10个球全部落入落入一个盒子里的概率非常的小，是
既然我们牺牲了一部分可靠性降低了开销，那么为什么不能把L设的在低一点？究竟应该设多低？
这其实是另外的一个问题了，我认为为了解决这个问题不应该从L入手，而是我们设定一个最低能接受的可靠性概率P，找到最小的L满足我们要求的P即可。
因此我们可以使用如上方法优化2)。设我们要求的最低可靠性为P, 优化函数为
2) 使用K个任务并行的选出每一堆的前
我可以给出一个数
但是必须解决的问题是可靠性问题，但这个问题其实很好办，只需要验证一下在3)时有没有把一个序列用尽，如果用尽了并且最后一个数不是这个序列里的最后一个数，那么说明这个序列的第
所以这时我们得到了一个以P为成功率的算法，这个算法可能比未优化前快好多倍，但是有(1-P)的中奖概率。欣慰的是我们可以判断中没中奖，再不济就是抛弃这次的结果再跑一次未优化前的算法呗。 堆排序，+ 分而治之 m取前n
以取小为例吧。我喜欢小。
以数据总量，分：小、中、大，三种情况来分析。
1、小：全部读入内存，排序，取前n。
2、中：
2.1：分几次读入（次数为k=总数据/内存大小），分别排序、写回读入点。致全部读一遍。形成k个顺串（称之数据锥）。
2.2：各锥读取一节(量为内存/K)，到内存（称之：锥节）。
2.2：各锥节尖做比较，小的写到另一块内存区（称之输出缓区）。如，某锥缓节空，读该锥的下一节。
2.3：致输出缓存区满。
2.4：写到结果文件。
2.5：结果够，结束。否则，继续2.2。
3、大：
3.1：若干单机，做2.1到2.3，暂停。
3.2：另一单机，做总机。从各单机输出缓存区，读一节到总机内存区（称总锥节）。
3.3：各总锥节尖做比较，小的写到总机的另一块内存区（称之总输出缓存区）。如，某总锥节空，读该锥对应单机输出缓存的下一节。
3.4：总缓存区满，写到结果文件。
3.5：结果够，结束。否则，继续3.3。
对于数据量大的情形。做顺串是免不了的。
以上算法，结果够时，会提前结束。
而锥节，总归比较小。因此，可能用不着 @皆传 的中奖法。
虽然中奖法很好玩。 最小K个数，思路和这个很类似。 很久没有碰数据结构了，只能说下思维框架。
1.先遍历前10万个数字，放到一个有序数据结构中，并且记录下这组数的最小值B；
2.遍历后面1亿-10万个数字，取出一个数字A，和有序结构中的最小值B进行比较，如果大于最小值B，则A进入有序数组，最小值B退出有序数组；
3.重新计算有序数组的最小值B；
4.重复这个过程直到结束。
---------------------
遍历1亿个数字是无法缩短时间的，那么程序的性能就在于如何在10万个数字尽快找到最小值了。
这个是二叉树最擅长的问题，你在遍历的同时也已经完成了二叉树的排序和插入工作。
不好意思的是，我已经基本忘记二叉树怎么写了。o_o||
先遍历，然后分堆，比如0-999999为一堆，100000-199999为二堆，
即n堆的范围是（n-1）*100000到n*100000-1
分好后，从最大的堆往前取，直到凑够，
比如，如果第一个堆的数量在10W个以上，那么可以继续分堆，可以继续分堆，缩小范围，也可以用排除法，比如最大的堆的数量在110000.则取这堆最小的10000，排除即可。
如果10W个数分布在几个堆里，那么必然存在前几个堆全取，最后一个堆取部分，最后的临界堆，这时可以继续分堆，也可以用双向循环链表取少量的top N.
当然也可以用一个10W节点的双向循环链表，插入去尾。
时间复杂度是 n log n * m
其中，n=100000,m是数组长度，
年前百度复合搜索部面试php，有个胖子面试官问过取top N问题，回答的是用双向循环链表，节点数就N。不过当时情况是，n很小，只有5.
构建二叉树要好一些，不过，当场写不出二叉树了，所以就没采取二叉树。