欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?

程序员文章站 2022-05-12 12:07:56
...
本人大三非计算机专业,自学web开发,前几天找实习面试php的时候面试官问我的算法题,没答上来本来准备最后问一下的,结果最后太紧张忘了问这题,回去之后没想到解法,希望知乎里大牛提供一个思路,什么语言都行<(。_。)>
=====================================================================
补充:初始是无序的,内存和磁盘并没说,我自己没有想明白这题的切入点也就没问在内存还是在磁盘,望能得到这两种情况都有的全面解答,多谢

回复内容:

问题是在 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个亿)筛选出前10万个最大值?
这个方法最大的缺点是没有并行计算
如果比1亿数据量再大,比如到100亿这个量级,那么就需要使用并行计算了,下面我详细说一下我的思路。
1) 首先将这些数据随机分成K堆,不妨假设正好平均分配,时间复杂度为如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?
2) 使用K个任务并行的选出每一堆的前M大的数,这一步的时间复杂度为如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?,此时生成了K组长度为M的有序序列。
3) 使用多路归并排序选出这K组序列的前M大的数,这一步的时间复杂度为如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?
因此假设第2步并行完成,那么总体的时间复杂度就是如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?。至此算法得到了常数级别的优化。
但是还没完,注意到2)中每个序列都选了前M大的数,这个是可以继续改进的。
我们可以想象一种场景:2个桶里总共有10个球,球是随机分布的,规定一种操作可以从这2个桶里拿至多L个球,这时我们怎么确定这个L使得我们能够以一个我们能接受的概率拿到所有的球?
显然当L=10的时候,我们当然可以100%的拿到这全部球,但是开销太大了。由于球是随机分布的,可以知道10个球全部落入落入一个盒子里的概率非常的小,是如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?。因此我们可以先把这种请当当成一个中彩票的事件,先不管他,直接把L设成9。
既然我们牺牲了一部分可靠性降低了开销,那么为什么不能把L设的在低一点?究竟应该设多低?
这其实是另外的一个问题了,我认为为了解决这个问题不应该从L入手,而是我们设定一个最低能接受的可靠性概率P,找到最小的L满足我们要求的P即可。
因此我们可以使用如上方法优化2)。设我们要求的最低可靠性为P, 优化函数为如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?
2) 使用K个任务并行的选出每一堆的前如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?大的数,这一步的时间复杂度为如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?, 此时生成了K组长度为如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?的有序序列。
我可以给出一个数如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?, 可以看出这个函数的威力。所以用这种方法,可以在实际中获得很多倍的速度提升。
但是必须解决的问题是可靠性问题,但这个问题其实很好办,只需要验证一下在3)时有没有把一个序列用尽,如果用尽了并且最后一个数不是这个序列里的最后一个数,那么说明这个序列的第如何在很大数量级的数据中(比如1个亿)筛选出前10万个最大值?个数也可能出现在最坏的结果。那么最简单的做法就是再从这个序列中补上一部分数据,使得最后的答案时正确的。
所以这时我们得到了一个以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.

构建二叉树要好一些,不过,当场写不出二叉树了,所以就没采取二叉树。

相关标签: php web