Tag Archives: k最大

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

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

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

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

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

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

这样有两个缺点:
1、内存占用非常大,其实我们只要保留最大的1000个,但这样就要保存N个。在1000万的测试中,它要占用68M[......]

继续阅读