您所在位置：主题：第73次编程比赛结果
boxertony [专家分：23030] 发布于 2008-10-07 23:29:00
测试结果如下：
2楼:
k=1 ：耗时110毫秒；
k=10 ：耗时79毫秒；
k=100 ：耗时187毫秒；
k=1000 ：耗时109毫秒；
k=10000 ：耗时31毫秒；
k=100000 ：耗时125毫秒；
k=1000000 ：耗时156毫秒；
k=5000000 ：耗时141毫秒；
总共花费时间938毫秒。
3楼:
k=1 ：耗时15毫秒；
k=10 ：耗时78毫秒；
k=100 ：耗时94毫秒；
k=1000 ：耗时187毫秒；
k=10000 ：耗时141毫秒；
k=100000 ：耗时110毫秒；
k=1000000 ：耗时172毫秒；
k=5000000 ：耗时250毫秒；
总共花费时间1047毫秒。
4楼: (n=100,000) (程序不太符合要求，函数参数顺序不符合我给定的函数原型）
k=1 ：耗时0毫秒；
k=10 ：耗时0毫秒；
k=100 ：耗时15毫秒；
k=1000 ：耗时125毫秒；
k=10000 ：耗时1469毫秒；
总共花费时间1609毫秒。
5楼：基本同4楼，不再测试。
6楼：完全不符合要求，不再测试。
7楼:（严格说来也是不符合我的要求的，函数名不一致）
k=1 ：耗时125毫秒；
k=10 ：耗时141毫秒；
k=100 ：耗时94毫秒；
k=1000 ：耗时172毫秒；
k=10000 ：耗时109毫秒；
k=100000 ：耗时125毫秒；
k=1000000 ：耗时172毫秒；
k=5000000 ：耗时203毫秒；
总共花费时间1141毫秒。
8楼: （错误原因在于由于堆的下标是从0开始的，所以current/2并不一定是parent）
k=1 ：耗时16毫秒；
k=10 ：耗时0毫秒；
k=100 ：耗时16毫秒；
k=1000 ：耗时15毫秒；
k=10000 ：耗时31毫秒；
k=100000 ：耗时125毫秒；
k=1000000 ：结果错误；耗时969毫秒；
k=5000000 ：结果错误；耗时2156毫秒；
总共花费时间3328毫秒。
10楼：程序不完整，无法测试。
12楼:（与我提供的函数原型参数顺序不匹配）
k=1 ：耗时31毫秒；
k=10 ：耗时31毫秒；
k=100 ：耗时31毫秒；
k=1000 ：耗时31毫秒；
k=10000 ：耗时78毫秒；
k=100000 ：耗时141毫秒；
k=1000000 ：耗时94毫秒；
k=5000000 ：耗时218毫秒；
总共花费时间655毫秒。
13-17楼:
k=1 ：耗时15毫秒；
k=10 ：耗时16毫秒；
k=100 ：耗时16毫秒；
k=1000 ：耗时0毫秒；
k=10000 ：耗时31毫秒；
k=100000 ：结果错误；耗时156毫秒；
k=1000000 ：结果错误；耗时78毫秒；
k=5000000 ：结果错误；耗时188毫秒；
总共花费时间500毫秒。
20楼:
k=1 ：耗时16毫秒；
k=10 ：耗时31毫秒；
k=100 ：耗时16毫秒；
k=1000 ：耗时32毫秒；
k=10000 ：结果错误；耗时2000毫秒；
k=100000 ：结果错误；耗时1984毫秒；
k=1000000 ：结果错误；耗时2000毫秒；
k=5000000 ：结果错误；耗时2000毫秒；
总共花费时间8079毫秒。
从测试结果来看，13-17楼Chipset的程序是最快的，他采用的是快速划分+partial_sort（实际上就是堆排序）来实现的（可惜部分结果错误，但应该可以调整正确的）；12楼的程序完全正确速度也非常快，比std::nth_element快40%左右。对于本题来说，我估计是划分+部分堆排序是最快的。我按照Chipset的思路写了一个，测试通过，总耗时在450ms左右。当然了，这个速度还是可以进一步提升的，呵呵
我宣布本次比赛的冠军为天边蓝（12楼），请他主持下次的编程比赛，大家鼓掌，呵呵。
测试环境： 软件 vs2008+winxp+sp3
硬件 Pentium M 3.4g
（ps： 本次比赛存在的问题是：我规定了函数的原型，可大部分人都没有按照我的要求去做。）
2楼:
k=1 ：耗时110毫秒；
k=10 ：耗时79毫秒；
k=100 ：耗时187毫秒；
k=1000 ：耗时109毫秒；
k=10000 ：耗时31毫秒；
k=100000 ：耗时125毫秒；
k=1000000 ：耗时156毫秒；
k=5000000 ：耗时141毫秒；
总共花费时间938毫秒。
3楼:
k=1 ：耗时15毫秒；
k=10 ：耗时78毫秒；
k=100 ：耗时94毫秒；
k=1000 ：耗时187毫秒；
k=10000 ：耗时141毫秒；
k=100000 ：耗时110毫秒；
k=1000000 ：耗时172毫秒；
k=5000000 ：耗时250毫秒；
总共花费时间1047毫秒。
4楼: (n=100,000) (程序不太符合要求，函数参数顺序不符合我给定的函数原型）
k=1 ：耗时0毫秒；
k=10 ：耗时0毫秒；
k=100 ：耗时15毫秒；
k=1000 ：耗时125毫秒；
k=10000 ：耗时1469毫秒；
总共花费时间1609毫秒。
5楼：基本同4楼，不再测试。
6楼：完全不符合要求，不再测试。
7楼:（严格说来也是不符合我的要求的，函数名不一致）
k=1 ：耗时125毫秒；
k=10 ：耗时141毫秒；
k=100 ：耗时94毫秒；
k=1000 ：耗时172毫秒；
k=10000 ：耗时109毫秒；
k=100000 ：耗时125毫秒；
k=1000000 ：耗时172毫秒；
k=5000000 ：耗时203毫秒；
总共花费时间1141毫秒。
8楼: （错误原因在于由于堆的下标是从0开始的，所以current/2并不一定是parent）
k=1 ：耗时16毫秒；
k=10 ：耗时0毫秒；
k=100 ：耗时16毫秒；
k=1000 ：耗时15毫秒；
k=10000 ：耗时31毫秒；
k=100000 ：耗时125毫秒；
k=1000000 ：结果错误；耗时969毫秒；
k=5000000 ：结果错误；耗时2156毫秒；
总共花费时间3328毫秒。
10楼：程序不完整，无法测试。
12楼:（与我提供的函数原型参数顺序不匹配）
k=1 ：耗时31毫秒；
k=10 ：耗时31毫秒；
k=100 ：耗时31毫秒；
k=1000 ：耗时31毫秒；
k=10000 ：耗时78毫秒；
k=100000 ：耗时141毫秒；
k=1000000 ：耗时94毫秒；
k=5000000 ：耗时218毫秒；
总共花费时间655毫秒。
13-17楼:
k=1 ：耗时15毫秒；
k=10 ：耗时16毫秒；
k=100 ：耗时16毫秒；
k=1000 ：耗时0毫秒；
k=10000 ：耗时31毫秒；
k=100000 ：结果错误；耗时156毫秒；
k=1000000 ：结果错误；耗时78毫秒；
k=5000000 ：结果错误；耗时188毫秒；
总共花费时间500毫秒。
20楼:
k=1 ：耗时16毫秒；
k=10 ：耗时31毫秒；
k=100 ：耗时16毫秒；
k=1000 ：耗时32毫秒；
k=10000 ：结果错误；耗时2000毫秒；
k=100000 ：结果错误；耗时1984毫秒；
k=1000000 ：结果错误；耗时2000毫秒；
k=5000000 ：结果错误；耗时2000毫秒；
总共花费时间8079毫秒。
从测试结果来看，13-17楼Chipset的程序是最快的，他采用的是快速划分+partial_sort（实际上就是堆排序）来实现的（可惜部分结果错误，但应该可以调整正确的）；12楼的程序完全正确速度也非常快，比std::nth_element快40%左右。对于本题来说，我估计是划分+部分堆排序是最快的。我按照Chipset的思路写了一个，测试通过，总耗时在450ms左右。当然了，这个速度还是可以进一步提升的，呵呵
我宣布本次比赛的冠军为天边蓝（12楼），请他主持下次的编程比赛，大家鼓掌，呵呵。
测试环境： 软件 vs2008+winxp+sp3
硬件 Pentium M 3.4g
（ps： 本次比赛存在的问题是：我规定了函数的原型，可大部分人都没有按照我的要求去做。）