如何在上亿条记录中查找第排在第100万位的数?

石油工人干IT

考虑这样一个问题：
          假设有一个海量的log记录库，例如，有上亿条记录，并且它是完全无序的。为了简化问题，我们再假设每条log的数据结构仅仅是一个浮点数，并且整个log库中无重复的记录。现在我们想寻找大小排在第100万个位置的数（假设顺序是从小到大），大家有什么好算法，能提供怎么样的优化呢？

谢谢大家!

tyc611

如果原文件是无序的话，选择排序查找？
这么大的数据应该维护成有序的，如果需要经常查找的话，再说这应该是数据库的事了

[ 本帖最后由 tyc611 于 2006-12-18 12:33 编辑 ]

三省吾身

nth_element？？？？？？？？？
记录太多

broadoceans

假设知道最大值和最小值范围。
首先取center = （max + min) / 2
然后 > center的放入一边， < center 的放入一边。
统计两边的个数，然后修改max和min,重新做。

像你说的，如果固定的100万，可以把center 设置为靠近100万的值。

sunlan

先排序，再定位

susesuse

在n个数中找出第k大的数，这是个经典问题，应该采用快速选择排序，其实是借鉴快速排序的思想。
你可以到网上去搜索解答方案。

converse

nth_element,stl里面自带的算法,我的博客里面也有这样的算法,记得没有错的是借助堆排序算法写的.

converse

http://www.cppblog.com/converse/archive/2006/07/08/9564.html

emacsnw

原帖由 susesuse 于 2006-12-17 21:47 发表
在n个数中找出第k大的数，这是个经典问题，应该采用快速选择排序，其实是借鉴快速排序的思想。
你可以到网上去搜索解答方案。

这个要求数据都放入内存的。上亿条记录，400来兆内存，应该可以吧。。
我觉得还是不能假设数据一下子读入内存再处理，比如可以在内存里维持一个k个数组成的堆，每次读入一个新的数据x，就和堆里的最小数y比较，如果x>y则把y去掉，x入堆。最后扫完所有数据后，堆里的最小数就是需要的第k大的元素。复杂度 n log (k)。

softsongs

这个问题的关键在于数据库如何保存这上亿条记录，如果采用适当的结构，比如B+树或AVL树，那么查找第100万个数log(n)就能找到了。