应该是目前最快的Trim函数

linux_newbie

昨天看了下面的帖子：

超强 Trim 横空出世！

http://bbs.chinaunix.net/forum/23/20040302/271575.html

感觉好像还是有一些优化的地方。自己写了一个fasttrim函数，结果速度有较大的提高。


先说结果，VC6，Release编译，WinXP English SP1，PM1.5G， 768内存，扫描一个前后都没有任何空格的1000字节长的字符串，（即实际上不需要trim）循环10万次，我的算法大概1.3s，而超强 Trim大概需要2s，就这个特定的情况，快了将近40%。

如果需要trim的情况，如果头部包含空格字符的话，由于每次trim以后，字符串内容已经改变，需要重新初始化string，在一个多次循环中，可能初始化string的时间对trim函数的时间干扰较大，因此采用了下面特定的测试数据：1000字节长的数据，头900都不为空格，尾部的100个字符为空格，这样每次重新初始化string的时候，只要将str的第900位由‘\0'改为一个空格字符就可以重新测试了。测试结果如下：我的算法大概1.2s，超强 Trim大概需要1.7s。

头尾都有空格的情况，由于每次都有初始化string，结果差别不大。

下面是我的程序的一些修改：

程序的return由void改为char ×，返回起始位置，这样就不必进行任何拷贝，这也是我函数比较快的原因之一，不过用法上有些区别， 其次，高效的感知end的位置。

下面是程序的代码

1. //一个简单的宏，为了方便阅读
   
2. #define IS_SPACE(c)  (c == ' ' || c == '\t')
   
3. 
   
4. char * fasttrim(char * str)
   
5. {
   
6.         char * start, * end = NULL;
   
7. 
   
8.         if(str == NULL)
   
9.                 return NULL;
   
10. 
    
11.         //去掉头部的空格字符
    
12.         while( IS_SPACE(*str) ) str++;
    
13.        
    
14.         //start赋值，循环
    
15.         for(start = str; *str != '\0'; str++)
    
16.         {
    
17.                 if ( IS_SPACE(*str) )
    
18.                 {
    
19.                         //遇到非连续的第一个空格，上个位置就是可能的尾部
    
20.                         end = str++;
    
21. 
    
22.                         //去掉接下来连续的空格
    
23.                         while( IS_SPACE(*str) ) str++;
    
24. 
    
25.                         //没有到尾，还有其他的字符，上次记录的尾部无效
    
26.                         if(*str != '\0')
    
27.                                 end = NULL;                //invalid end
    
28.                 }
    
29.         }
    
30. 
    
31.         if(end) *end = '\0';
    
32. 
    
33.         return start;
    
34. }

复制代码

[/url]

foxmanzj

牛B轰轰的。我就不回了。

linux_newbie

呵呵。等着挨扁。

自己研究了一下，某些情况下（头部没有空格，而且尾部空格比例不大），比我这个函数快的有win_hate写的void str_trim (char *str) ，不过当字符如果尾部有很多空格的时候，win_hate的函数就比较慢了，因为回溯的次数多了。另外，头部有空格的时候，由于win_hate的函数进行了移位，因此也要慢一些。

其实，如果函数的返回类型是void，那么当字符前面有空格时，都需要进行位移。（不过这样也可以看做是这个算法的要求。但如果只是为了尽快的trim的话，实际上应该没有必要，返回char×不仅效率高，而且可以写成下列的形式：
  if(!strcmp( trim(buffer), "command1")

实话实说，flw的函数，无论在任何情况下，都比我的慢。哈哈，有点大言不惭！不好意思，不好意思。请指教！
[/img]

windflowers1976

唉，写好一个函数而已，不用全国人民都知道吧。

FH

你的IS_SPACE少了好几个判断，当然会快些。
希望也能跟俺那个对比测试一下，呵呵。

linux_newbie

re FH:
哈哈，不瞒你说，你的函数我也测试了。我将所有的trim函数中判断字符是否空格的地方都使用了一个统一的宏来代替，因此在这个上面应该没有误差。

我测试了一个我自己认为比较典型的例子。
分配100M内存，构造一个20%头部空格，60%中间全部是A字符，最后20%为空格的巨大字符串，运行一次（构造大字符串是因为，我认为全部的时间都是用于trim函数本身的执行，受外界干扰比较小）。结果如下：

0.2 - 0.6 - 0.2 分布情况：

fast_trim time : 250
flw_trim time : 450
winhate_trim time : 271
FH_trim time : 361


源程序如下：

1. 
   
2. #include <stdio.h>;
   
3. #include <string.h>;
   
4. #include <memory.h>;
   
5. #include <time.h>;
   
6. 
   
7. #define IS_SPACE(c)  (c == ' ' || c == '\t')
   
8. 
   
9. char * fasttrim(char * str)
   
10. {
    
11.         char * start, * end = NULL;
    
12. 
    
13.         if(str == NULL)
    
14.                 return NULL;
    
15. 
    
16.         while( IS_SPACE(*str) ) str++;
    
17.        
    
18.         for(start = str; *str != '\0'; str++)
    
19.         {
    
20.                 if ( IS_SPACE(*str) )
    
21.                 {
    
22.                         end = str++;
    
23.                         while( IS_SPACE(*str) ) str++;
    
24. 
    
25.                         if(*str != '\0')
    
26.                              end = NULL;                                }
    
27.         }
    
28. 
    
29.         if(end) *end = '\0';
    
30. 
    
31.         return start;
    
32. }
    
33. 
    
34. void flw_trim( char *str )
    
35. {
    
36.         char *copied, *tail = NULL;
    
37. 
    
38.         if ( str == NULL )
    
39.                 return;
    
40. 
    
41.         for( copied = str; *str; str++ )
    
42.         {
    
43.                 if ( *str != ' ' && *str != '\t' )
    
44.                 {
    
45.                         *copied++ = *str;
    
46.                          tail = copied;
    
47.                 }
    
48.                 else
    
49.                 {
    
50.                          if ( tail )
    
51.                                  *copied++ = *str;
    
52.                 }
    
53.         }
    
54. 
    
55.         if ( tail )
    
56.              *tail = 0;
    
57.         else
    
58.              *copied = 0;
    
59. 
    
60.         return;
    
61. }
    
62. 
    
63. //win_hate
    
64. void winhate_trim (char *str)
    
65. {
    
66.    char *save = str;
    
67.    char *b;
    
68. 
    
69.    if (str == NULL)
    
70.       return;
    
71. 
    
72.    if (IS_SPACE (*(b = str)))
    
73.      {
    
74.         while (*b)
    
75.           {
    
76.              if (IS_SPACE (*b))
    
77.                 b++;
    
78.              else
    
79.                 break;
    
80.           }
    
81. 
    
82.         while (*b)
    
83.              *str++ = *b++;
    
84. 
    
85.         str--;
    
86.         while (IS_SPACE (*str))
    
87.               str--;
    
88. 
    
89.         str[1] = '\0';
    
90.      }
    
91.    else
    
92.      {
    
93.       while (*b)
    
94.            b++;
    
95. 
    
96.         b--;
    
97. 
    
98.         while (IS_SPACE (*b))
    
99.            b--;
    
100.         b[1] = '\0';
     
101.      }
     
102.      return;
     
103. }
     
104. 
     
105. 
     
106. 
     
107. char   *FH_Trim( char *String )
     
108. {
     
109.    char   *Tail, *Head;
     
110. 
     
111.    for ( Tail = String + strlen( String ) - 1; Tail >;= String; Tail -- )
     
112.       if ( !IS_SPACE( *Tail ) )
     
113.          break;
     
114.    Tail[1] = 0;
     
115.    for ( Head = String; Head <= Tail; Head ++ )
     
116.       if ( !IS_SPACE( *Head ) )
     
117.          break;
     
118.    if ( Head != String )
     
119.       memcpy( String, Head, ( Tail - Head + 2 ) * sizeof( char ) );
     
120.    return String;
     
121. }
     
122. 
     
123. int main(int argc, char* argv[])
     
124. {
     
125.         int time;
     
126. 
     
127.        
     
128.         const int test_len = 100 * 1024 * 1024;
     
129.         const int head_space = (int)(test_len * 0.2);
     
130.         const int tail_space = (int)(test_len * 0.2);
     
131. 
     
132. 
     
133.         char * teststr = new char[test_len];
     
134. 
     
135. #define INIT_TESTSTR \
     
136.         memset(teststr, 'A', test_len); \
     
137.         memset(teststr, ' ', head_space); \
     
138.         memset(teststr + test_len - tail_space, ' ', tail_space); \
     
139.         teststr[test_len - 1] = '\0';
     
140. 
     
141.         INIT_TESTSTR
     
142.         time = clock();
     
143.         fasttrim(teststr);
     
144.         printf("fast_trim time : %d\n", clock() - time);
     
145. 
     
146. 
     
147.         INIT_TESTSTR       
     
148.         time = clock();
     
149.         flw_trim(teststr);
     
150.         printf("flw_trim time : %d\n", clock() - time);
     
151. 
     
152. 
     
153.         INIT_TESTSTR       
     
154.         time = clock();
     
155.         winhate_trim(teststr);
     
156.         printf("winhate_trim time : %d\n", clock() - time);
     
157. 
     
158.        
     
159.         INIT_TESTSTR       
     
160.         time = clock();
     
161.         FH_Trim(teststr);
     
162.         printf("FH_trim time : %d\n", clock() - time);
     
163. 
     
164. 
     
165.         delete[] teststr;
     
166.         return 0;
     
167. }

复制代码

FH

??

dzho002

可以写的更简单些

1. 
   
2. char* fasttrim(char* str)
   
3. {
   
4.   char* start=NULL, *end=NULL;
   
5.   if(str==NULL) return NULL;
   
6.    while( IS_SPACE(*str) ) str++;
   
7.    for(start=str;(*str)!='\0';++str)
   
8.    {
   
9.       if ( !IS_SPACE(*str) )
   
10.               end=str;
    
11.     }
    
12.     if(end)  *(end+1) = '\0';
    
13.     return start;
    
14. }
    

复制代码

linux_newbie

回dzho002：
确实如此。这样代码更加简洁了。速度也差不多。

flw

我想说明四点：

1，自始至终，我都没有说我的算法是最快的，最初的解释是“之所以说“超强”是因为只用了一个循环两个变量，估计也不能更简洁了。”。

2，你这个函数和我的函数的功能不同，你少做了一件事，所以和我的不能比较。你的和别人的也不能比较，因为我们的功能都一样，唯独你的功能不同，所以没法比较。

3，如果要讲速度的话，想你这样的函数速度肯定不如用 mem* str* 系列的函数快。

4，你的测试方法不科学。在不同的规模下，各个函数可能表现的效果会不一样。你看看人家是怎么测试的：
http://www-900.ibm.com/developerWorks/cn/linux/sdk/rt/part3/index.shtml