关于一个运算优化的问题

无心人

楼主用什么排序算法 似乎，好像用基数排序能在排序 阶段就计算出来二进制位的最高位 不过，可能代码就太复杂了 另外，尝试把我的那个表加入代码， 能提高一点点时间吧

litaoye

已经用了一个类似的表了！记录的数据差不多就是这些！现在排序部分用的都是.net自带的，没有作 更多的优化。晚上再看看吧，又想到了一个可以优化的地方，但估计对效率影响不会太大。时间上估计再难前进了！

原帖由 无心人 于 2009-3-15 14:37 发表 楼主用什么排序算法 似乎，好像用基数排序能在排序 阶段就计算出来二进制位的最高位 不过，可能代码就太复杂了 另外，尝试把我的那个表加入代码， 能提高一点点时间吧

无心人

如果用自带的，估计应该是快速排序 我想是否他数据存在专门反快速排序的例子？？

shshsh_0510

我对那个网站的时间测试值比较令人困惑： 对于1000的A+B，我试了一下，是0.015，但很多人是0.001 起先我以为是人家优化了scanf和printf，但好像不是那么回事，即便我将程序写成： #include int main(int argc, char* argv[]) { putchar('1'); return 0; } 当然结果是错的，但时间依然是0.015！！ 由此可见，其他问题的排名也许是在多年前的不同测试用例下产生的。

liangbch

楼上说的也许有道理。不过就楼上提到的例子，我的理解是， 对于每一道题，需要用多份数据做测试，有的做的是正确性测试，有的做的是性能测试。如果你的结果错了，给出的时间多半是没有意义的。我之前的未通过正确性检查的代码给出的时间也是0.015. 另外，它的测试所有的计时器时间精度很有限。同一个问题的多个测试实例，所用时间值是离散的，要么相同，要么他的差一个相对较大的值。

shshsh_0510

嗯，我猜想0.015是哪个系统产生的测试消耗，现在回答任何问题都不可能超越，不知有没反例

shshsh_0510

我写了几个版本的scanf,printf但没差别，都是0.015 即使有人对他们可以优化的比我快10倍，也不会有这么多人 而且由于这是入门例子，所以大部分人会使用例子的程序。 于是根据problem 1000的数据可以知道，系统在2000.10.和2004.7曾经两次对测试程序做了调整。至于调整是涉及到所有问题还是个别问题，或者还做过其他可以对成绩产生影响的调整没，单从1000的数据就看不出了

liangbch

我查了一下1000成绩排名，结果如下：

成绩	名次	时间
0.001	1-13519	2000-10-27到2008-10-9
0.010	13520-18389	2000-9-22到2004-1-3
0.015	18390	2001-1-3 到现在

从上表可知， 1. 时间值是离散的，从0.001到0.015只有3个值，不存在0.005,0.012等其他值。 2. 直到半年前，仍然有人得到获得0.001秒的成绩，如果系统做了调整，怎么会有这么小的数值呢？想不通。 0.015 之后的成绩为 0.02,0,03,这次时间间隔为0.01,没有发现0.025的数据。 0.02 （14970-26061）2000-4-28 到 2004-1-1 0.03 ( 从26062 开始 [ 本帖最后由 liangbch 于 2009-3-16 13:13 编辑 ]

litaoye

感觉记录时有个最小时间单位，超过了0.001可能就是0.01了。 反正我用c#做过的这些题，没有低于0.125的，我看有些人能够达到0.09左右，也不太清楚是怎么做到的。 另外同样的程序，有时候时间也会有所不同，不过只会相差1个时间单位，不会差更多了！

litaoye

实际上，在我本地测的话，c#和c++并没有这么大的差别，c#虽然会慢一些，但一般同样的算法的话，不会相差超过2倍。