在10000000个数(int)中求最小的10000个数

jigloo

说实话这个火星不得了的火星题我真的没什么兴趣。
不过， 的确nth_element并不是最快的。
不知道的请google"炒冷饭 从一道笔试题谈算法优化"

醉卧水云间

原帖由 jigloo 于 2007-8-23 11:09 发表
说实话这个火星不得了的火星题我真的没什么兴趣。
不过， 的确nth_element并不是最快的。
不知道的请google"炒冷饭 从一道笔试题谈算法优化"

测试了一下你的solution_4，应该是你最快的算法吧，还是比nth_element慢约1倍，VC6测试的，GCC没测，估计也差不多。所以你说nth_element并不是最快的以你的代码说明不了，找更快的吧。

醉卧水云间

TO converse:

map不可取，速度和空间都是数量级的差别，我没说错，呵呵。

jigloo

看solution_6

ps:非必要请勿quote我的发言，我很不安，觉得是在跟人吵架。

[ 本帖最后由 jigloo 于 2007-8-23 11:53 编辑 ]

zwylinux

原帖由 jigloo 于 2007-8-23 10:06 发表

既然用了stl的话，还可以写得紧凑些

#include
#include
#include
#include
#include
#include
#include

using namespace std;

void main()
{
        vector vecTmp;
        generate_n(back_ins ...

既然用了C++，就不要出现void main()这个情况。

醉卧水云间

solution_6确实更好，但仍比nth_element差约20%，不用测了吧。

buxoman

一千万个整数，找出一万个小的数，
一千万除以一万等于一千。
每次都读取一千个整数，然后找出其中的最小数，这里就很快找到了。

aero

原帖由 jigloo 于 2007-8-23 11:09 发表
说实话这个火星不得了的火星题我真的没什么兴趣。
不过， 的确nth_element并不是最快的。
不知道的请google"炒冷饭 从一道笔试题谈算法优化"

Thanks.

以前真没碰到过这个问题。

jigloo

数量级太小，solution_6与nth谁快看不出来的。

accelerator

原帖由 aero 于 2007-8-22 22:38 发表
^_^，大家有没有啥好算法？

偶今天下午写了一个，可以达到62ms数量级。

简单思路：前10000个数做成一个大顶堆，但不排序，不是堆排序。后面再来的数，直接与堆顶比较，大于的直接continue，小于的替换堆顶 ...

调整堆还得遍历那1000个数以保证最大的在上, 似乎不经济. 我觉得还是要排序. 计数排序是个不错的选择. (10,000,000 * 4Byte) / (1024 * 1024) < 39MB, 空间上可以忍受吧?