【原创】超强版 Trim 横空出世！

forest077

FH的代码和楼主的区别在于，用c=*str和*copied++=c来代替了*copied++=*str这一步，这实际上比起原来的代码反而多了一次赋值，而引用指针的次数却并不少。所以这段改过的代码效率不见得提高，反而降低了。
以前的帖子用到算法中有指针扫描到字符串结尾后又回溯的方式，这样对于最后一个非空字符后面的每个字符都做了一遍＋＋和--运算。而楼主的帖子是做了一遍＋＋和一遍赋值运算，效率应该都差不太多。
strlen和memmove我没研究过，不知效率如何，不敢妄言。

FH

我说一下我的意见：

用c来代替*str，是因为从汇编的角度判断*str需要至少两条指令，而直接判c的指令数要少，正因为有两次的*str判断和两次的*str赋值，况且如果做的再完善些，判断还远不止两个，所以才值得用c来替换*str。不服气的人可以把两段代码都执行一百万次，比较一下时间。

考虑C程序的效率，不能以C语句的多少来判断，要从汇编和指令周期的角度考虑问题，这是我的一点看法。

串处理指令的效率远远高于C的循环语句，我在自己的代码里使用的就是strlen和memmove、memcpy，其中memcpy的效率要高于memmove，这在man里面都有说明。

strlen的代码用串指令很容易实现：
xor ecx, ecx
repnz testsb
neg ecx
就这么简单！至于memcpy，我就不多说了。

FH

要不先把两段代码编译出来，看看目标文件的长度？

win_hate

1. 
   
2. #include <stdio.h>;
   
3. #include <ctype.h>;
   
4. 
   
5. void str_trim ();
   
6. 
   
7. int
   
8. main ()
   
9. {
   
10.         char buf[1024] = "ab                cd         ";
    
11.         str_trim (buf);
    
12.         puts (buf);
    
13.         return 0;
    
14. }
    
15. 
    
16. void
    
17. str_trim (char *str)
    
18. {
    
19.         char *save = str;
    
20.         char *b;
    
21. 
    
22.         if (str == NULL)
    
23.                 return;
    
24. 
    
25.         if (isspace (*(b = str)))
    
26.           {
    
27.                   while (*b)
    
28.                     {
    
29.                             if (isspace (*b))
    
30.                                     b++;
    
31.                             else
    
32.                                     break;
    
33.                     }
    
34. 
    
35.                   while (*b)
    
36.                             *str++ = *b++;
    
37. 
    
38.                   str--;
    
39.                   while (isspace (*str))
    
40.                         str--;
    
41. 
    
42.                   str[1] = '\0';
    
43.           }
    
44.         else
    
45.           {
    
46.                   while (*b)
    
47.                           b++;
    
48. 
    
49.                   b--;
    
50.                   while (isspace (*b))
    
51.                           b--;
    
52.                   b[1] = '\0';
    
53.           }
    
54.           return;
    
55. }
    
56. 
    

复制代码

实现特点：
1、 采用 ansi c 中的宏 isspace
2、 处理了开始字节非"space" 的情况。
3、 仍然采用"回溯"的方式。优点是只对 开始的空白和最后的空白进行 isspace 判断。
4、 后面有很多空格的时候， 这个算法的效率仍值得推敲。

win_hate

BinBinNorth 与 FH 兄对 strlen 和 memcpy  的看法是有道理的。其实我很久以前就想做个测试， 不过要么没时间，要么就太懒，x86 不同指令的效率，总是使我很头疼)。先这么写了。

至于 c = *str 的优化，我把希望寄托在编译器的优化上了。

FH

呵呵，刚测了一百万次，没什么差别，分别是18秒和19秒，一千万次差别还稍微大一点。
测试用代码如下，编译时使用了-O选项：

1. 
   
2. #include        <string.h>;
   
3. 
   
4. #define        STRSZ        4096
   
5. #define        TIMES        10000000
   
6. 
   
7. extern void trim( char *str );
   
8. 
   
9. main()
   
10. {
    
11.         int        i;
    
12.         char        s[STRSZ];
    
13. 
    
14.         for ( i = 0; i < TIMES; i ++ ) {
    
15.                 memset( s, ' ', STRSZ - 1 );
    
16.                 s[STRSZ - 1] = 0;
    
17.                 trim( s );
    
18.         }
    
19. }
    

复制代码

测试结果如下（一千万次）：

1. 
   
2. c:
   
3. real    2m49.856s
   
4. user    2m49.838s
   
5. sys     0m0.020s
   
6. *str:
   
7. real    3m7.069s
   
8. user    3m7.059s
   
9. sys     0m0.008s
   

复制代码

测试环境为：Red Hat Linux 8.0 on VMware 4.5.0-build 7174

guixin

这是我去两头空格的trim，欢迎大家指正：
void trim(char *chr)
{
               int len;
               len = strlen(chr);
               while(chr[0] == ' ')
              {
                     for(int i=0;i<len;i++)
                          chr=chr[i+1];
                     len -= 1;
               }

               for(int i=len-1;chr == ' ';i--)
                    chr=0;
}

BingbingNorth

我写的一个trim，带测试代码。
在sco unix,ibm aix4.3.windows上测试，效果比flw兄的好一点，尤其是在aix上。在sco上就很奇怪，优化比不优化还要慢，足见sco的烂。
缺点是对库函数的实现依赖太大。

1. #include <stdio.h>;
   
2. #include <string.h>;
   
3. #include <memory.h>;
   
4. #include <time.h>;
   
5. 
   
6. void trim1( char *str )
   
7. {
   
8.         char *copied, *tail = NULL;
   
9. 
   
10.         if ( str == NULL )
    
11.                 return;
    
12. 
    
13.         for( copied = str; *str; str++ )
    
14.         {
    
15.                 if ( *str != ' ' && *str != '\t' )
    
16.                 {
    
17.                         *copied++ = *str;
    
18.                          tail = copied;
    
19.                 }
    
20.                 else
    
21.                 {
    
22.                          if ( tail )
    
23.                                  *copied++ = *str;
    
24.                 }
    
25.         }
    
26. 
    
27.         if ( tail )
    
28.              *tail = 0;
    
29.         else
    
30.              *copied = 0;
    
31. 
    
32.         return;
    
33. }
    
34. 
    
35. void trim2(char * str)
    
36. {
    
37.         char * start, * end;
    
38.        
    
39.         end=str + strlen(str)-1;
    
40.         start=str;
    
41.         for(; ((end>;=start)&&((*end==' ')||(*end=='\t'))); end--);
    
42.         *(end+1)='\0';
    
43.         for(; (start<=end)&&((*start==' ')||(*start=='\t')); start++);
    
44.         if(start!=str)
    
45.                 memmove(str, start, end-start+2);
    
46. }
    
47. 
    
48. int main()
    
49. {
    
50.         char buff[10000];
    
51.         time_t time1, time2;
    
52.         int i;
    
53.        
    
54.        
    
55.         memset(buff, 'a', sizeof(buff));
    
56.         buff[0]=' ';
    
57.         buff[9998]=' ';
    
58.         buff[9999]='\0';
    
59.        
    
60.        
    
61.         time(&time1);
    
62.         for(i=0; i<50000; i++)
    
63.         {
    
64.                 buff[0]=' ';
    
65.                 buff[9997]='a';
    
66.                 buff[9998]=' ';
    
67.                 buff[9999]='\0';
    
68.                 trim1(buff);
    
69.         }
    
70.         time(&time2);
    
71.         printf("%d\n", time2-time1);
    
72.        
    
73.         time(&time1);
    
74.         for(i=0; i<50000; i++)
    
75.         {
    
76.                 buff[0]=' ';
    
77.                 buff[9997]='a';
    
78.                 buff[9998]=' ';
    
79.                 buff[9999]='\0';
    
80.                 trim2(buff);
    
81.         }
    
82.         time(&time2);
    
83.         printf("%d\n", time2-time1);
    
84.        
    
85.         getchar();
    
86. 
    
87.         return 0;
    
88. }

复制代码

FH

[quote="guixin"][/quote]
用chr[i]这种方式效率肯定比用指针慢很多。

converse

库函数的实现各个编译器可能不同，比如strlen这样的字符串操作，可能是在底层用汇编的串操作实现的，所以效率高也不足为奇，另外如果真的是用汇编实现的话，这么比较似乎也不公平，总而言之，flw的算法思想是很不错的