关于一个运算优化的问题

litaoye

我估计.net应该是用的堆排序，他测试时候的例子有时确实比较极端。不好说！
不过排序在整个程序中所占的时间比重还是比较少的，估计就算优化了提高也有限。

我这里时间上占用最多的应该还是LogXor，昨天对于这个问题作了比较有针对性的优化，终于将时间从0.156优化到了0.171，
所以我决定就这样了，呵呵！

原帖由 无心人 于 2009-3-15 22:05 发表
如果用自带的，估计应该是快速排序

我想是否他数据存在专门反快速排序的例子？？

无心人

终于将时间从0.156优化到了0.171



呵呵

无心人

如果采取高精度计时，是可以获得很高的时间精度的
但必须在一个封闭的且程序顺序进行测试的环境里

如果在Web服务器上，应该存在随机延迟

gxqcn

很想知道这类Web服务如何做到公平性的？
尤其当多用户同时提交时。

还有，硬件若升级又该如何评判？

无心人

是啊

比如最新的Core2其分支预测错误的惩罚变小了很多
算法不同的实现很可能导致Core2上和P4 上截然相反的
时间开销

无心人

他应该有个后台机器光做程序测试的

gxqcn

从未参加过类似 acm 比赛，
问一个比较小白的问题：
它是要求提交源代码吗？
若是，设定编译选项及编译都是由对方负责吗？

skyivben

原帖由 gxqcn 于 2009-3-16 20:11 发表
从未参加过类似 acm 比赛，
问一个比较小白的问题：
它是要求提交源代码吗？
若是，设定编译选项及编译都是由对方负责吗？

是的，它要求提交源代码。
是的，设定编译选项及编译都是由对方负责。

litaoye

这种方式都或多或少存在一些误差，但误差范围一般不会太多，类似在0-2范围之内取一个随机数，
因此只要多提交几次，总有随机到0的时候。关于硬件升级，我觉得他们现在所跑的时间，
可能并不是真正的时间，而是一个经过换算了的时间，一个跟CPU速度无关的时间。

这道题除外，有不少题都是被人用hash的方法解的，如果输入范围不大，比如求费伯纳妾数的某一项，大家一般会用一个O(n)的算法，
有人优化了之后，用个log(n)的算法，效率可能会提高一些。但也会有人直接把int64之内的所有项直接写入一个数组，
然后根据数组下标返回值，这种做法速度虽然很快，但已经偏离了算法本身要达到的目的，反正我是不喜欢这么做的。

ACM题并也不代表编程水平，有许多题也比较无聊，说实话我觉得对测试工程师的要求可能更高。如果每个能通过你的程序测试的，
都能通过ACM测试，那么你确实很牛。而像这道题一样，给你很大空间自由发挥的题，并不是很多。
（如果以后发现，我可以都拿来讨论一下）

原帖由 gxqcn 于 2009-3-16 20:02 发表
很想知道这类Web服务如何做到公平性的？
尤其当多用户同时提交时。

还有，硬件若升级又该如何评判？

gxqcn

谢谢以上两位的回复，对我扫盲了。