免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 15946 | 回复: 12

[函数] 应该是目前最快的Trim函数 [复制链接]

论坛徽章:
0
发表于 2004-05-16 15:27 |显示全部楼层
昨天看了下面的帖子:

超强 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. char * fasttrim(char * str)
  4. {
  5.         char * start, * end = NULL;

  6.         if(str == NULL)
  7.                 return NULL;

  8.         //去掉头部的空格字符
  9.         while( IS_SPACE(*str) ) str++;
  10.        
  11.         //start赋值,循环
  12.         for(start = str; *str != '\0'; str++)
  13.         {
  14.                 if ( IS_SPACE(*str) )
  15.                 {
  16.                         //遇到非连续的第一个空格,上个位置就是可能的尾部
  17.                         end = str++;

  18.                         //去掉接下来连续的空格
  19.                         while( IS_SPACE(*str) ) str++;

  20.                         //没有到尾,还有其他的字符,上次记录的尾部无效
  21.                         if(*str != '\0')
  22.                                 end = NULL;                //invalid end
  23.                 }
  24.         }

  25.         if(end) *end = '\0';

  26.         return start;
  27. }
复制代码
[/url]

论坛徽章:
0
发表于 2004-05-16 20:11 |显示全部楼层

应该是目前最快的Trim函数

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

论坛徽章:
0
发表于 2004-05-16 21:05 |显示全部楼层

应该是目前最快的Trim函数

呵呵。等着挨扁。

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

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

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

论坛徽章:
0
发表于 2004-05-16 21:11 |显示全部楼层

应该是目前最快的Trim函数

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

论坛徽章:
0
发表于 2004-05-16 21:27 |显示全部楼层

应该是目前最快的Trim函数

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

论坛徽章:
0
发表于 2004-05-16 21:57 |显示全部楼层

应该是目前最快的Trim函数

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. #include <stdio.h>;
  2. #include <string.h>;
  3. #include <memory.h>;
  4. #include <time.h>;

  5. #define IS_SPACE(c)  (c == ' ' || c == '\t')

  6. char * fasttrim(char * str)
  7. {
  8.         char * start, * end = NULL;

  9.         if(str == NULL)
  10.                 return NULL;

  11.         while( IS_SPACE(*str) ) str++;
  12.        
  13.         for(start = str; *str != '\0'; str++)
  14.         {
  15.                 if ( IS_SPACE(*str) )
  16.                 {
  17.                         end = str++;
  18.                         while( IS_SPACE(*str) ) str++;

  19.                         if(*str != '\0')
  20.                              end = NULL;                                }
  21.         }

  22.         if(end) *end = '\0';

  23.         return start;
  24. }

  25. void flw_trim( char *str )
  26. {
  27.         char *copied, *tail = NULL;

  28.         if ( str == NULL )
  29.                 return;

  30.         for( copied = str; *str; str++ )
  31.         {
  32.                 if ( *str != ' ' && *str != '\t' )
  33.                 {
  34.                         *copied++ = *str;
  35.                          tail = copied;
  36.                 }
  37.                 else
  38.                 {
  39.                          if ( tail )
  40.                                  *copied++ = *str;
  41.                 }
  42.         }

  43.         if ( tail )
  44.              *tail = 0;
  45.         else
  46.              *copied = 0;

  47.         return;
  48. }

  49. //win_hate
  50. void winhate_trim (char *str)
  51. {
  52.    char *save = str;
  53.    char *b;

  54.    if (str == NULL)
  55.       return;

  56.    if (IS_SPACE (*(b = str)))
  57.      {
  58.         while (*b)
  59.           {
  60.              if (IS_SPACE (*b))
  61.                 b++;
  62.              else
  63.                 break;
  64.           }

  65.         while (*b)
  66.              *str++ = *b++;

  67.         str--;
  68.         while (IS_SPACE (*str))
  69.               str--;

  70.         str[1] = '\0';
  71.      }
  72.    else
  73.      {
  74.       while (*b)
  75.            b++;

  76.         b--;

  77.         while (IS_SPACE (*b))
  78.            b--;
  79.         b[1] = '\0';
  80.      }
  81.      return;
  82. }



  83. char   *FH_Trim( char *String )
  84. {
  85.    char   *Tail, *Head;

  86.    for ( Tail = String + strlen( String ) - 1; Tail >;= String; Tail -- )
  87.       if ( !IS_SPACE( *Tail ) )
  88.          break;
  89.    Tail[1] = 0;
  90.    for ( Head = String; Head <= Tail; Head ++ )
  91.       if ( !IS_SPACE( *Head ) )
  92.          break;
  93.    if ( Head != String )
  94.       memcpy( String, Head, ( Tail - Head + 2 ) * sizeof( char ) );
  95.    return String;
  96. }

  97. int main(int argc, char* argv[])
  98. {
  99.         int time;

  100.        
  101.         const int test_len = 100 * 1024 * 1024;
  102.         const int head_space = (int)(test_len * 0.2);
  103.         const int tail_space = (int)(test_len * 0.2);


  104.         char * teststr = new char[test_len];

  105. #define INIT_TESTSTR \
  106.         memset(teststr, 'A', test_len); \
  107.         memset(teststr, ' ', head_space); \
  108.         memset(teststr + test_len - tail_space, ' ', tail_space); \
  109.         teststr[test_len - 1] = '\0';

  110.         INIT_TESTSTR
  111.         time = clock();
  112.         fasttrim(teststr);
  113.         printf("fast_trim time : %d\n", clock() - time);


  114.         INIT_TESTSTR       
  115.         time = clock();
  116.         flw_trim(teststr);
  117.         printf("flw_trim time : %d\n", clock() - time);


  118.         INIT_TESTSTR       
  119.         time = clock();
  120.         winhate_trim(teststr);
  121.         printf("winhate_trim time : %d\n", clock() - time);

  122.        
  123.         INIT_TESTSTR       
  124.         time = clock();
  125.         FH_Trim(teststr);
  126.         printf("FH_trim time : %d\n", clock() - time);


  127.         delete[] teststr;
  128.         return 0;
  129. }
复制代码

论坛徽章:
0
发表于 2004-05-17 09:52 |显示全部楼层

应该是目前最快的Trim函数

??

论坛徽章:
0
发表于 2004-05-17 12:05 |显示全部楼层

应该是目前最快的Trim函数

可以写的更简单些

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

论坛徽章:
0
发表于 2004-05-17 15:22 |显示全部楼层

应该是目前最快的Trim函数

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

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2004-05-17 16:30 |显示全部楼层

应该是目前最快的Trim函数

我想说明四点:

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

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

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

4,你的测试方法不科学。在不同的规模下,各个函数可能表现的效果会不一样。你看看人家是怎么测试的:
http://www-900.ibm.com/developerWorks/cn/linux/sdk/rt/part3/index.shtml
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP