寻找最大的K个数——扩展问题！

kon3155

在面试中，有下面的问答：

问：有很多个无序的数，我们姑且假定它们各不相等，怎么选出其中最大的若干个数呢？
答：可以这样写：int array[100] ……
问：好，如果有更多的元素呢？
答：那可以改为：int array[1000] ……
问：如果我们有很多元素，例如1亿个浮点数，怎么办？
答：个，十，百，千，万……那可以写：float array [100 000 000] ……
问：这样的程序能编译运行么？
答：嗯……我从来没写过这么多的0 ……

原问题描述及解答见 http://www.msra.cn/Articles/Arti ... 1-88a1-75a4d4243f0a
pdf版本下载： 寻找最大的K个数.pdf (325.46 KB, 下载次数: 5)

2009-3-10 13:06 上传

点击文件名下载附件

下面是与这个问题相关的几个扩展问题，大家有兴趣讨论一下，如果对原问题的五种官方解答有不同看法也可以一起讨论！

【扩展问题1】.   如果需要找出N个数中最大的K个不同的浮点数呢？比如，含有10个浮点数的数组（1.5, 1.5, 2.5, 2.5, 3.5, 3.5, 5, 0, -1.5, 3.5）中最大的3个不同的浮点数是（5, 3.5, 2.5）。


【扩展问题2】.   如果是找第k到m（0 < k < = m < = n）大的数呢？


【扩展问题3】.   在搜索引擎中，网络上的每个网页都有“权威性”权重，如page rank。如果我们需要寻找权重最大的K个网页，而网页的权重会不断地更新，那么算法要如何变动以达到快速更新（incremental update）并及时返回权重最大的K个网页？
（提示：堆排序？当每一个网页权重更新的时候，更新堆。还有更好的方法吗？）


【扩展问题4】.   在实际应用中，还有一个“精确度”的问题。我们可能并不需要返回严格意义上的最大的K个元素，在边界位置允许出现一些误差。当用户输入一个query的时候，对于每一个文档d 来说，它跟这个query之间都有一个相关性衡量权重f （query, d）。搜索引擎需要返回给用户的就是相关性权重最大的K个网页。如果每页10个网页，用户不会关心第1000页开外搜索结果的“精确度”，稍有误差是可以接受的。比如我们可以返回相关性第10 001大的网页，而不是第9999大的。在这种情况下，算法该如何改进才能更快更有效率呢？网页的数目可能大到一台机器无法容纳得下，这时怎么办呢？
（提示：归并排序？如果每台机器都返回最相关的K个文档，那么所有机器上最相关K个文档的并集肯定包含全集中最相关的K个文档。由于边界情况并不需要非常精确，如果每台机器返回最好的K’个文档，那么K’应该如何取值，以达到我们返回最相关的90%*K个文档是完全精确的，或者最终返回的最相关的K个文档精确度超过90%（最相关的K个文档中90%以上在全集中相关性的确排在前K），或者最终返回的最相关的K个文档最差的相关性排序没有超出110%*K。）



【扩展问题5】.   如第4点所说，对于每个文档d，相对于不同的关键字q1, q2, …, qm，分别有相关性权重f（d, q1），f（d, q2）, …, f（d, qm）。如果用户输入关键字qi之后，我们已经获得了最相关的K个文档，而已知关键字qj跟关键字qi相似，文档跟这两个关键字的权重大小比较靠近，那么关键字qi的最相关的K个文档，对寻找qj最相关的K个文档有没有帮助呢？

[ 本帖最后由 kon3155 于 2009-3-12 10:52 编辑 ]

shshsh_0510

数组下标超过2^32次方时，32位的程序就不行了。当然可以用64位，但一般如果所用内存超过物理内存的60-70%根据系统不同，就有可能发生换页了。所以应该分步的外排序。
此时和内排序差别较大的地方在于，由于io的代价很大，所以主要问题不再是对比较次数的复杂度的细微差别，而是要尽量减小io。也就是希望可以在一次遍历完成。
但如果k足够大，一次遍历不可能完成，于是，但k相当大是就又有些像内排序了

kon3155

大家对于问题5有什么好的想法？

litaoye

用类似桶排的方法,过2次应该可以吧,不行就再过几遍,内存占用也不算很大!

比如第一遍通过除以某数,将所有的数映射到一个2^16的整形范围之内,作统计,然后遍历一下这个2^16的桶,就可以算出第k个数
在哪个桶里,第2次遍历的时候,将属于这个桶里的数放到前头,并且只处理属于这个桶的数据,
把这部分数再次映射到2^16的整形范围之内,然后再求属于哪个桶,以此类推,直到这个桶里只有1个数.

kon3155

楼上回答的是哪个问题？我怎么没看明白！

litaoye

原帖由 kon3155 于 2009-3-12 20:47 发表
楼上回答的是哪个问题？我怎么没看明白！

仔细看了一下PDF,我说的大概跟解法5类似吧!不过应该可以算浮点数。
他给的方法是用位图分成2^32个桶，遍历1次，我说的是分成2^16个桶多遍历几次。可以省一些内存。另外也可以支持浮点。

另外，我的表达能力有问题，总是说不太清自己的想法！呵呵！