找回密码
 欢迎注册
楼主: 毒酒滴冻鸭

[讨论] 织女的六把黄金尺子问题

[复制链接]
发表于 2014-12-18 08:19:46 | 显示全部楼层
本楼是讨论汇编优化的,不喜欢汇编的人请忽略本楼。
在28#的代码中,“if ( g_used [ i ] )      continue” 这句是用来查找一个值为0的元素,这使我立即想起c运行时刻函数strlen,这个函数也是用来查找值为0的元素,不过其数组是char型而不是整型。如果将这段代码改为调用strlen函数,效果如何呢?说干就干 ,于是我又写了一版调用函数strlen的版本。另外,我有加了2个strlen函数的汇编的版本。源代码是来自于丹麦的Anger Fog。下面是调用strlen函数的版本。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <windows.h>

  5. /* 说明:
  6. 我们定义尺子编号为i,(i>=0), 尺子i总是有i+1段。
  7. 我们首先搜索编号最大的尺子,然后搜索编号次小的尺子,最后搜索编号为0的尺子,在本程序尺子编号用rule_idx来表示
  8. */

  9. #define MAX_RULES_COUNT 8                //最多可搜索8把尺子
  10. #define MAX_SEG_COUNT  120                //最多可覆盖120种不同的长度
  11. char g_used[MAX_SEG_COUNT+2];        //used[i]=1表示长度i可被尺子测量
  12. int g_maxSegArr[]={1,4,10,20,35,56,84,120}; //maxSegArr[i]表示尺子i可测量的不同长度的总数
  13. int g_result[MAX_RULES_COUNT][MAX_RULES_COUNT]; // result[i][j]表示尺子i第j+1段的长度
  14. int g_count;

  15. // The asm code is from Anger Fog "optimization_manuals"
  16. _declspec(naked)
  17. int anger_strlen( char *s )
  18. {
  19.         __asm
  20.         {
  21.                 push    ebx
  22.         mov     ecx, [esp+8]           ; get pointer to string
  23.         mov     eax, ecx               ; copy pointer
  24.         and     ecx, 3                 ; lower 2 bits of address, check alignment
  25.         jz      L2                     ; string is aligned by 4. Go to loop
  26.         and     eax, -4                ; align pointer by 4
  27.         mov     ebx, [eax]             ; read from nearest preceding boundary
  28.         shl     ecx, 3                 ; mul by 8 = displacement in bits
  29.         mov     edx, -1
  30.         shl     edx, cl                ; make byte mask
  31.         not     edx                    ; mask = 0FFH for false bytes
  32.         or      ebx, edx               ; mask out false bytes

  33.         ; check first four bytes for zero
  34.         lea     ecx, [ebx-01010101H]   ; subtract 1 from each byte
  35.         not     ebx                    ; invert all bytes
  36.         and     ecx, ebx               ; and these two
  37.         and     ecx, 80808080H         ; test all sign bits
  38.         jnz     L3                     ; zero-byte found
  39.         
  40.         ; Main loop, read 4 bytes aligned
  41. L1:     add     eax, 4                 ; increment pointer by 4
  42. L2:     mov     ebx, [eax]             ; read 4 bytes of string
  43.         lea     ecx, [ebx-01010101H]   ; subtract 1 from each byte
  44.         not     ebx                    ; invert all bytes
  45.         and     ecx, ebx               ; and these two
  46.         and     ecx, 80808080H         ; test all sign bits
  47.         jz      L1                     ; no zero bytes, continue loop
  48.         
  49. L3:     bsf     ecx, ecx               ; find right-most 1-bit
  50.         shr     ecx, 3                 ; divide by 8 = byte index
  51.         sub     eax, [esp+8]           ; subtract start address
  52.         add     eax, ecx               ; add index to byte
  53.         pop     ebx
  54.         ret
  55.         }
  56. }
  57. // The asm code is from Anger Fog "optimization_manuals"
  58. _declspec(naked)
  59. int anger_strlen_sse2( char *s )
  60. {
  61.         __asm
  62.         {
  63.         mov      eax,  [esp+4]         ; get pointer to string
  64.         mov      ecx,  eax             ; copy pointer
  65.         pxor     xmm0, xmm0            ; set to zero
  66.         and      ecx,  15              ; lower 4 bits indicate misalignment
  67.         and      eax,  -16             ; align pointer by 16
  68.         movdqa   xmm1, [eax]           ; read from nearest preceding boundary
  69.         pcmpeqb  xmm1, xmm0            ; compare 16 bytes with zero
  70.         pmovmskb edx,  xmm1            ; get one bit for each byte result
  71.         shr      edx,  cl              ; shift out false bits
  72.         shl      edx,  cl              ; shift back again
  73.         bsf      edx,  edx             ; find first 1-bit
  74.         jnz      L2                    ; found
  75.         
  76.         ; Main loop, search 16 bytes at a time
  77. L1:     add      eax,  16              ; increment pointer by 16
  78.         movdqa   xmm1, [eax]           ; read 16 bytes aligned
  79.         pcmpeqb  xmm1, xmm0            ; compare 16 bytes with zero
  80.         pmovmskb edx,  xmm1            ; get one bit for each byte result
  81.         bsf      edx,  edx             ; find first 1-bit
  82.         jz       L1                    ; loop if not found
  83.         
  84. L2:     ; Zero-byte found. Compute string length        
  85.         sub      eax,  [esp+4]         ; subtract start address
  86.         add      eax,  edx             ; add byte index
  87.         ret
  88.         }
  89. }

  90. void output_result( int rule_count)
  91. {
  92.         int i,j;
  93.         for(i=0;i<rule_count;i++)
  94.         {
  95.                 printf("(");
  96.                 for(j=0;j<=i;j++)
  97.                         printf("%d,",g_result[i][j]);
  98.                 printf(")\n");     
  99.         }
  100.         printf("\n");
  101.         g_count++;
  102. }

  103. int check(int rule_idx, int deep, int *pNewSegCount, int newSegs[] )
  104. {
  105.         int i,c,sum;
  106.         for (c=0,sum=0,i=deep-1;i>=0;i--)
  107.         {
  108.                 sum += g_result[rule_idx][i];
  109.                 if ( g_used[sum] )
  110.                         return 0;
  111.                 g_used[sum]=32;
  112.                 newSegs[c++]=sum;
  113.                 *pNewSegCount=c;
  114.         }
  115.         return 1;
  116. }

  117. //deep: 表示将要确定尺子第deep+1段的长度
  118. void new_mark(int rule_count,int seg_count,int rule_idx, int deep)
  119. {
  120.         int i,j,mid,flag,sum,new_used_count;
  121.         int new_used[MAX_SEG_COUNT+1];

  122.         mid=rule_idx/2; //第rule_idx+1把尺子中间段的编号
  123.         for (sum=0,i=0;i<deep;i++)
  124.                 sum += g_result[rule_idx][i];

  125.         for (i=1;i<=seg_count;i++)
  126.         {
  127.                 //i+= strlen(g_used+i);
  128.                 //i+= anger_strlen(g_used+i);
  129.                 i+= anger_strlen_sse2(g_used+i);
  130.                 if ( i + sum > seg_count)
  131.                         break;

  132.                 if ( deep==mid+1 && i< g_result[rule_idx][rule_idx-deep] )
  133.                         continue;  //消除重复的结果

  134.                 g_result[rule_idx][deep]=i;
  135.                 flag=check(rule_idx,deep+1,&new_used_count,new_used);
  136.                 if (flag )
  137.                 {
  138.                         if ( rule_idx==0)
  139.                                 output_result(rule_count);
  140.                         if ( deep==rule_idx)
  141.                                 new_mark(rule_count,seg_count,rule_idx-1,0);
  142.                         else
  143.                                 new_mark(rule_count,seg_count,rule_idx,deep+1);
  144.                 }
  145.                 for ( j=0;j<new_used_count;j++)
  146.                         g_used[new_used[j]]=0;
  147.         }
  148. }

  149. void search(int n)
  150. {
  151.         DWORD t;
  152.         printf("\nIs searching the soultion when rule count is %d\n",n);
  153.         t=::GetTickCount();
  154.         g_count=0;memset(g_result,0,sizeof(g_result));
  155.         new_mark(n,g_maxSegArr[n-1],n-1,0);
  156.         t=::GetTickCount()-t;
  157.         printf("It take %d ms and find %d solution\n",t,g_count);
  158. }

  159. //int main(int argc, char* argv[])
  160. //{
  161. //        int i;
  162. //        for (i=1;i<=6;i++ ) search(i);
  163. //        return 0;
  164. //}
复制代码





毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-18 08:30:42 | 显示全部楼层
效果?
效果不是很明显,调用3种strlen函数的版本的速度区别不大,在忽略误差的情况下,与原始版本差不多,可能的原因有
1. 这段代码不是热点。
2. 值为0的元素相对比较多,函数strlen查找的长度较小;
3. g_used[ i ]的地址在绝大部分情况下不是4字节对齐。汇编版本难以施展其威力。
我们不应怀疑汇编函数的意义。在字符串长度相对较长的情况下,在字符串地址是4字节对齐的情况下。汇编版本的strlen应该具有很大的优势。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-18 18:14:05 | 显示全部楼层
渣机器渣代码跑了半小时……
于是,我想能否转成跳舞链的01矩阵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-12-19 11:02:32 | 显示全部楼层
上次忘了,还有一张把全部56个长度的量法都列出的图。。。

rulers.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-12-28 23:35:59 | 显示全部楼层
非常感谢gxqcn大大的赐精!

有空再多发两道困扰我多时的题目。。。

点评

欢迎多提有价值的问题。。。  发表于 2014-12-29 08:05
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-12-18 11:21:12 | 显示全部楼层
我们好像可以约定每把尺子的长度。
1 把尺子=1
2 把尺子=4, 3
3 把尺子=10, 9, 7
4 把尺子=20, 19, 17, 14
5 把尺子=35, 34, 32, 29,25
6 把尺子=56, 55, 53, 50, 46,41
7 把尺子=84, 83, 81, 78, 74, 69, 63

点评

你可能没有理解题意,建议详细看看其他人的回复。  发表于 2019-12-19 21:51
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 17:59 , Processed in 0.054987 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表