大量数据取k个最大值并排序

需求是这样的,我们都知道,在信息检索中,经常要取top-k(一共k,而不是第k)个得分最大的文档,并且从大到小排序。

而且文档规模很大,最少也要上千万。

话说这是一道很可以拿来面试的题啊。

我们不考虑Hadoop神马的,就说说单机怎么搞。

最傻的做法就是把1000万个都存储下来,然后sort,然后取min(k, vec.size())。

这样有两个缺点:
1、内存占用非常大,其实我们只要保留最大的1000个,但这样就要保存N个。在1000万的测试中,它要占用68M内存之多。
2、速度慢虽然是快速排序,但我们实际只要前1000个,后面那些排序都是无用功了。

于是靠谱的做法就是构建一个小顶堆:
(1)当堆中元素数量小于k时, 向堆中加入元素并调整堆
(2)当堆中元素数量大于等于k时 ,将堆顶(显然是当前最小的)和新元素比较:
(a)如果新元素小,丢弃之,我们只要top k 最大的。
(b) 如果新元素比堆顶大,把堆顶用新元素换掉,然后调整堆。

好了,理论是上面这个过程,我们一般就不要裸写堆了,用c++ stl的pop_heap/make_heap/push_heap搞定之。注意它没有调整堆单独的函数,而是第一次make_heap,之后用成对的pop_heap/push_heap来完成堆维护(这两个操作不会改变堆大小)。而堆是构建在vector基础上的。

细节是:上述默认都是构造大顶堆,从小到大排序等。于是我们要子构造一个反向排序函数。

好了,再重复一下堆:

小顶堆:堆顶始终是最小的元素,排序时把最小的换到末尾,类似选择排序的过程。这样拍出来的是从大到小。

大顶堆:排序之后从小到大。

比较一下性能(1kw个数据,值域0~1kw):

算法/内存/时间:

(1)sort topk / 68MB / 11s
(2)heap / 3MB / 6s

内存优势非常明显。时间优势在这个规模可能还显示不出来,也可能是qsort的随机性能。

堆解决代码:

对照组小白鼠(sort topK):

 

One thought on “大量数据取k个最大值并排序

  1. coder4lyman

    构建在 vector 上的堆会不会比较慢?比如从堆中拿掉一个元素这种操作会不会导致 vector 里面的后续元素都被拷贝一遍?如果自己用链表+二分查找模拟一个堆应该是最快了吧。

    Reply

Leave a Reply

Your email address will not be published.