关于一个运算优化的问题

litaoye

肯定会慢不少，尤其是运算量较大的时候。所以我的目标就是超过前面的JAVA就行了！呵呵！ （我C++的水平不行，所以干啥都用c#） 如果我的程序能比以前有较大的提高的话，相信转化为C++的会更快！

litaoye

终于找到BUG了!都快疯了!主要是一般数据测试起来全是正确的,可偏偏Test 10#过不去! 程序一长了,就不容易找错了! (快300行了,其中有个120多行的大数类,再加上求10的0-38次方,也有20-30行) 现在用C#的成绩是0.312! liangbch同志,不好意思了,昨天第1次提交成功的时候0.326,正好是第42,呵呵! 这下JAVA们再也赶不上了!很有成就感......

无心人

汗， 你没事用大数类做什么啊？？？？ 好像用不到诶

litaoye

原帖由 无心人 于 2009-3-14 13:45 发表 汗， 你没事用大数类做什么啊？？？？ 好像用不到诶

我自己写的挺简单的，就是包括XOR， 比较大小，付初始值，加法和乘法。 又想了一下，现在的算法还有可以优化的地方，晚上再试试！

无心人

这个似乎 1、排序， 基数排序就可以了，用16位为单位 2、确定每个数的最高位 3、如果m不和某个10^n的最高位相等 只要计算最高位等于m的最高位的n的logXOR(m, n) 4，如果和某个10^n的最高位相等，需要计算小于该数的全部logXOR， gxq的算法可以参考 好像目前就只能这么优化了

无心人

好像用不到加法乘法诶

litaoye

原帖由 无心人 于 2009-3-14 15:46 发表 好像用不到加法乘法诶

算10的幂的时候用了个乘法，其实可以先算出来直接保存的，可能还快一点，不过觉得挺麻烦的，加法是当时觉得有用就写了，现在也没有用上

无心人

我下载了宝宝的代码 打算在里面加排序 哈哈 用宝宝的代码修改提交后打败宝宝

litaoye

等我的程序优化完了，也贴上来，看有没有什么用！

liangbch

将求128bit的常用对数程序，完全用汇编写了，速度却没有改进多少。从0.343改进到0.328. 仔细查看了编译后的 logSum 函数（见下），发现指令数很多，遂重写循环，速度一下子就提到了0.171。 代码改进前的速度0.328

1. int logSum( UINT128 *data,int count)
2. {
3. int i,j;
4. UINT128 t;
5. DWORD r;
7. for (r=0,i=0;i<count;i++)
8. {
9. for (j=i+1;j<count;j++)
10. {
11. t=data[i];
12. t.U[0] ^= data[j].U[0];
13. t.U[1] ^= data[j].U[1];
14. t.U[2] ^= data[j].U[2];
15. t.U[3] ^= data[j].U[3];
16. r += log10(&t);
17. }
18. }
20. return r*2;
21. }

复制代码

代码改进后的速度0.171

1. int logSum( UINT128 *data,int count)
2. {
3. DWORD r;
4. UINT128 t;
5. UINT128 *p1,*p2,*pEnd;
7. p1= data;
8. pEnd=(data+count-1);
10. r=0;
11. for (;p1<=pEnd;p1++)
12. {
13. for (p2=p1+1;p2<=pEnd;p2++)
14. {
15. t.U[0] = p1->U[0] ^ p2->U[0];
16. t.U[1] = p1->U[1] ^ p2->U[1];
17. t.U[2] = p1->U[2] ^ p2->U[2];
18. t.U[3] = p1->U[3] ^ p2->U[3];
19. r += log10(&t);
20. }
21. }
23. return r*2;
24. }

复制代码

看来计算log10所占的比重很小，速度很难提高了，下面是我的log 10函数的原型

1. __declspec(naked)
2. DWORD __fastcall log10( UINT128 *n)
3. {
4. __asm
5. {
6. push ecx
7. push esi
8. mov esi,ecx
10. ......

复制代码

by the way, 楼主用C# 做到0.312，确实不易。