关于一个运算优化的问题

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;
   
6. 
   
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.         }
    
19.        
    
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;
   
6.        
   
7.         p1=  data;
   
8.         pEnd=(data+count-1);
   
9.        
   
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.         }
    
22.        
    
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
   
9. 
   
10. ......

复制代码

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