关于一个运算优化的问题

wayne

才一个主题贴，就奉上这么长的代码，着实让我吃惊。。虽然我能看得懂代码，但毕竟内功远远不够，

wayne

我开始醒悟，我既非理科，又非计算机专业的，进了这地方，是一个很大的冒失啊。

向你们致敬，想你们学习了！

无心人

用我给出的表，直接查表，似乎还能加速
你的代码已经比我给出的表数据多了

liangbch

我从0.342优化到0.171,如果优化后速度再提高一倍，就是第一名了。按照楼主的思路，将XOR和log10这2步操作合在一起，用汇编语言写成一个函数，速度应该可以更快。等有时间我将尝试一下。

无心人

呵呵

我第一次是0.468， 普通算法
不如shshsh_0510的普通算法

按照楼主的思路写的代码
现在是0.234

看来还需要优化啊

无心人

目前的笨代码
和各位无法比啊

1. 
   
2. #include <stdlib.h>
   
3. #include <stdio.h>
   
4. #include <string.h>
   
5. 
   
6. typedef struct
   
7. {
   
8.   unsigned int d[4];
   
9. } UINT128;
   
10. 
    
11. unsigned int CompTable[128][2] =  {0,0, 0,0, 0,0, 0,1, 1,0, 1,0, 1,1, 2,0, 2,0, 2,1, 3,0, 3,0, 3,0, 3,1,
    
12.                       4,0,4,0,4,1,5,0,5,0,5,1,6,0,6,0,6,0,6,1,7,0,7,0,7,1,8,0,8,0,
    
13.    8,1,9,0,9,0,9,0,9,1,10,0,10,0,10,1,11,0,11,0,11,1,12,0,12,
    
14.    0,12,0,12,1,13,0,13,0,13,1,14,0,14,0,14,1,15,0,15,0,15,0,15,
    
15.    1,16,0,16,0,16,1,17,0,17,0,17,1,18,0,18,0,18,0,18,1,19,0,19,
    
16.    0,19,1,20,0,20,0,20,1,21,0,21,0,21,0,21,1,22,0,22,0,22,1,23,
    
17.    0,23,0,23,1,24,0,24,0,24,0,24,1,25,0,25,0,25,1,26,0,26,0,26,
    
18.    1,27,0,27,0,27,0,27,1,28,0,28,0,28,1,29,0,29,0,29,1,30,0,30,
    
19.    0,30,1,31,0,31,0,31,0,31,1,32,0,32,0,32,1,33,0,33,0,33,1,34,
    
20.    0,34,0,34,0,34,1,35,0,35,0,35,1,36,0,36,0,36,1,37,0,37,0,37,0,37,1,38,0};
    
21. 
    
22. UINT128 pow10[40] = {1,0,0,0,
    
23.                     10,0,0,0,
    
24. 100,0,0,0,
    
25. 1000,0,0,0,
    
26.                     10000,0,0,0,
    
27. 100000,0,0,0,
    
28. 1000000,0,0,0,
    
29. 10000000,0,0,0,
    
30. 100000000,0,0,0,
    
31. 1000000000,0,0,0,
    
32. 1410065408,2,0,0,
    
33. 1215752192,23,0,0,
    
34. 3567587328,232,0,0,
    
35. 1316134912,2328,0,0,
    
36. 276447232,23283,0,0,
    
37. 2764472320,232830,0,0,
    
38. 1874919424,2328306,0,0,
    
39. 1569325056,23283064,0,0,
    
40. 2808348672,232830643,0,0,
    
41. 2313682944,2328306436,0,0,
    
42. 1661992960,1808227885,5,0,
    
43. 3735027712,902409669,54,0,
    
44. 2990538752,434162106,542,0,
    
45. 4135583744,46653770,5421,0,
    
46.      2701131776,466537709,54210,0,
    
47. 1241513984,370409800,542101,0,
    
48. 3825205248,3704098002,5421010,0,
    
49. 3892314112,2681241660,54210108,0,
    
50. 268435456,1042612833,542101086,0,
    
51. 2684354560,1836193738,1126043566,1,
    
52. 1073741824,1182068202,2670501072,12,
    
53. 2147483648,3230747430,935206946,126,
    
54. 0,2242703233,762134875,1262,
    
55. 0,952195850,3326381459,12621,
    
56. 0,932023908,3199043520,126217,
    
57. 0,730304488,1925664130,1262177,
    
58. 0,3008077584,2076772117,12621774,
    
59. 0,16004768,3587851993,126217744,
    
60. 0,160047680,1518781562,1262177448,
    
61. 0, 0, 0, 0};
    
62. 
    
63. 
    
64. inline int _log2(unsigned int r)
    
65. {
    
66.         __asm
    
67.         {
    
68.                 bsr eax,r
    
69.         }
    
70. }
    
71. 
    
72. inline int log2( UINT128 n)
    
73. {
    
74.     if (n.d[3] != 0) return (96 + _log2(n.d[3]));
    
75.     if (n.d[2] != 0) return (64 + _log2(n.d[2]));
    
76.     if (n.d[1] != 0) return (32 + _log2(n.d[1]));
    
77. return (_log2(n.d[0]));
    
78. }
    
79. 
    
80. inline int compare( const void * a, const void * b )
    
81. {
    
82. unsigned int * l, * r;
    
83. l = (unsigned int *)a; r = (unsigned int *)b;
    
84. if (*(l+3) != *(r + 3)) return (*(l + 3) > *(r+3) ? 1 : -1);
    
85. if (*(l+2) != *(r + 2)) return (*(l + 2) > *(r+2) ? 1 : -1);
    
86. if (*(l+1) != *(r + 1)) return (*(l + 1) > *(r+1) ? 1 : -1);
    
87. return (* l > * r ? 1 : (* l == * r ? 0 : -1));
    
88. 
    
89. }
    
90. 
    
91. inline int log_10(UINT128 n)
    
92. {
    
93.    int i = log2(n), j = CompTable[i][0];
    
94.    if (CompTable[i][1] == 0) return (j);
    
95.    if (compare(&n, &pow10[j + 1]) >= 0) return (j + 1); else return j;
    
96. }
    
97. 
    
98. int main(int argc, char* argv[])
    
99. {
    
100.     int count,result,i,j, k;
     
101.     UINT128 data[5000];
     
102. unsigned int l2[5000];
     
103.     unsigned int l10[5000];
     
104. UINT128 r;
     
105. 
     
106.     scanf("%d",&count);
     
107.     result=0;
     
108. i = 0;
     
109.     while (i < count) {
     
110.         scanf("%u", &data[i].d[3]);
     
111.         scanf("%u", &data[i].d[2]);
     
112.         scanf("%u", &data[i].d[1]);
     
113.         scanf("%u", &data[i].d[0]);
     
114.         i++;
     
115.     }
     
116. 
     
117.     qsort( (void *)data, (size_t)count, 16, compare );
     
118. 
     
119. for (i = 0; i < count; i ++)
     
120. {
     
121. l10[i] = log_10(data[i]);
     
122.         l2[i] = log2(data[i]);
     
123. }
     
124. 
     
125.     for (i= count - 1; i > 0; i --)
     
126. {
     
127. k = l2[i];
     
128. if (CompTable[k][1] == 0)
     
129. {
     
130.    j = i - 1;
     
131.           while ((l2[j] == k) && (j >= 0))
     
132.    {
     
133.              r.d[3] = data[i].d[3] ^ data[j].d[3];   
     
134.              r.d[2] = data[i].d[2] ^ data[j].d[2];   
     
135.              r.d[1] = data[i].d[1] ^ data[j].d[1];   
     
136.              r.d[0] = data[i].d[0] ^ data[j].d[0];
     
137.       result += log_10(r);
     
138.   j --;
     
139.           }
     
140.    if (j >= 0)
     
141.    result += l10[i] * (j + 1);
     
142. }
     
143. else
     
144.    for (j = i - 1; j >= 0; j --)
     
145.    {
     
146.    
     
147.              r.d[3] = data[i].d[3] ^ data[j].d[3];   
     
148.              r.d[2] = data[i].d[2] ^ data[j].d[2];   
     
149.              r.d[1] = data[i].d[1] ^ data[j].d[1];   
     
150.              r.d[0] = data[i].d[0] ^ data[j].d[0];
     
151.       result += log_10(r);
     
152.           }
     
153. }
     
154.     printf("%u",result*2);
     
155.     return 0;
     
156. }
     

复制代码

0.203

无心人

__declspec(naked)
int log2(UINT128 * n)
{
   __asm
   {
    mov edx, [esp + 4]
    bsr eax, [edx]
    bsr ecx, [edx + 4]
    add ecx, 32
    cmp [edx + 4], 0
    cmovne eax, ecx
    bsr ecx, [edx + 8]
    add ecx, 64
    cmp [edx + 8], 0
    cmovne eax, ecx
    bsr ecx, [edx + 12]
    add ecx, 96
    cmp [edx + 12], 0
    cmovne eax, ecx
    ret   
   }
}
128位求2的对数非跳转版本！！

wayne

C中内嵌汇编，

liangbch

我将我的101楼代码的阅读权限调低了。现在只有积分达到200分，就可以看我101楼的代码

无心人

147# OK了

下面汇编化 log10和log10xor

呵呵