Chinaunix

标题: 【原创】超强版 Trim 横空出世！ [打印本页]
作者: flw    时间: 2004-03-02 15:04
标题: 【原创】超强版 Trim 横空出世！
昨天给一个同事讲 trim，一时豪情大发，一不小心编出了这段代码，后来仔细看看，确实是堪称精品，不过又怕有什么遗漏的地方，所以赶紧发到这里让大家帮我参详参详。

  1. void trim( char *str )
  2. {
  3.         char *copied, *tail = NULL;

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

  8.         for( copied = str; *str; str++ )
  9.         {
  10.                 if ( *str != ' ' && *str != '\t' )
  11.                 {
  12.                         *copied++ = *str;
  13.                          tail = copied;
  14.                 }
  15.                 else
  16.                 {
  17.                          if ( tail )
  18.                                  *copied++ = *str;
  19.                 }
  20.         }

  22.         if ( tail )
  23.              *tail = 0;
  24.         else
  25.              *copied = 0;

  27.         return;
  28. }
复制代码
作者: lenovo    时间: 2004-03-02 15:22
标题: 【原创】超强版 Trim 横空出世！
if ( str == NULL )
                return NULL;
原型是返回void哦。
作者: flw    时间: 2004-03-02 15:28
标题: 【原创】超强版 Trim 横空出世！
原帖由 "lenovo" 发表：
if ( str == NULL )
                return NULL;
原型是返回void哦。

哦，粗心了，改过。
作者: lenovo    时间: 2004-03-02 15:43
标题: 【原创】超强版 Trim 横空出世！
还有else
             *copied = 0;
是否也可以去掉。
因为你for循环结束时的条件就是*copied =＝ 0
还有应该是*str != 32 && *str != 9吧？
作者: flw    时间: 2004-03-02 15:51
标题: 【原创】超强版 Trim 横空出世！
原帖由 "lenovo" 发表：
还有else
             *copied = 0;
是否也可以去掉。
因为你for循环结束时的条件就是*copied =＝ 0
还有应该是*str != 32 && *str != 9吧？

真的是太不好意思了。
今天没有带电脑，刚才的这段代码是默写出来的，所以有很多错误。
刚才又改了一下，循环的条件改正确了。

另：TAB 的键值我可能的确是记错了。
但是程序中不建议直接写 ASCII 码，我是因为怕空格看不清楚才这么写的，现在改回去了。
作者: w25    时间: 2004-03-02 15:54
标题: 【原创】超强版 Trim 横空出世！
从那说起这个是超强的trim阿，它能去掉中间的空格，前面的空格，后面的空格，是全部还是部分阿。
还有，str！等于8或9有什么区别么？我看只要不等于32就算满足要求了！
作者: flw    时间: 2004-03-02 15:59
标题: 【原创】超强版 Trim 横空出世！
原帖由 "w25" 发表：
从那说起这个是超强的trim阿，它能去掉中间的空格，前面的空格，后面的空格，是全部还是部分阿。
还有，str！等于8或9有什么区别么？我看只要不等于32就算满足要求了！

它能去掉前面的和后面的空格，中间的不会去掉。网络通讯中经常用到。

9 是 TAB，TAB 一般和空格做同样的解释。所以也要去掉。

之所以说“超强”是因为只用了一个循环两个变量，估计也不能更简洁了。
作者: lenovo    时间: 2004-03-02 16:01
标题: 【原创】超强版 Trim 横空出世！
原帖由 "w25" 发表：
从那说起这个是超强的trim阿，它能去掉中间的空格，前面的空格，后面的空格，是全部还是部分阿。
还有，str！等于8或9有什么区别么？我看只要不等于32就算满足要求了！

它是去掉字符串两端的空格。
ascii码是TAB键。
这个算法已经很不错了。
要不你也写一个出来。
作者: aero    时间: 2004-03-02 16:23
标题: 【原创】超强版 Trim 横空出世！
斑竹的确很负责，码了很多字出来。这段代码也非常好。
W25兄表老激动哦。
作者: FH    时间: 2004-03-02 16:23
标题: 【原创】超强版 Trim 横空出世！
不错！

但我觉得应该把所有控制符都去掉，举个例子：BS也应该处理吧？而且处理起来还很复杂。STX，ACK等等有意义吗？
我都是判<=空格的，又干净效率还高。
作者: flw    时间: 2004-03-02 16:43
标题: 【原创】超强版 Trim 横空出世！
原帖由 "FH" 发表：
不错！

但我觉得应该把所有控制符都去掉，举个例子：BS也应该处理吧？而且处理起来还很复杂。STX，ACK等等有意义吗？
我都是判<=空格的，又干净效率还高。


呵呵，这个就不好说了，比如我们公司的接口中，都用 \1 来当做字段的分隔符，所以是不能去掉的。
通常情况下，<32 的字符由于大多是不可见字符，实际应用中用不着，所以恰恰被很多接口采用为转义字符、分隔符、类型符、控制符等等，所以绝对是不可以去掉的。


再说了，要是想去掉，改一下我这个代码就可以了。
反正又不影响算法的效率：“时间复杂度”和“空间复杂度”，
所以我不会在意的。

我在意的是：我的这个算法有没有漏洞？有没有人能写出比我这个更好的算法？
作者: converse    时间: 2004-03-02 16:49
标题: 【原创】超强版 Trim 横空出世！
不错不错，用了两个指针记录位置，tail只有在不是空格的情况下才写入，这样在tail不为空的时候就记录下了最后的空格出现的位置。
作者: forest077    时间: 2004-03-02 16:53
标题: 【原创】超强版 Trim 横空出世！
不错，我觉得从算法而言，确实没有简化的余地了。
作者: FH    时间: 2004-03-02 17:12
标题: 【原创】超强版 Trim 横空出世！
算法不错！
但对用STX来做分隔符不赞同，控制码里也有专门的符号的，FS就是嘛！
这个算法在尾部空格较多时有损失。
我再给你简化一下，主要是从效率角度考虑：

  2. void trim( char *str )
  3. {
  4.         char *copied;
  5.         char *tail;
  6.         char c;

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

  11.         for ( copied = str, tail = NULL; ( c = *str ) != 0; str ++ )
  12.         {
  13.                 if ( c != ' ' && c != '\t' )
  14.                 {
  15.                         *copied ++ = c;
  16.                          tail = copied;
  17.                 }
  18.                 else
  19.                 {
  20.                          if ( tail != NULL )
  21.                                  *copied ++ = c;
  22.                 }
  23.         }

  25.         if ( tail != NULL )
  26.              *tail = 0;
  27.         else
  28.              *str = 0;
  29. }
复制代码
作者: w25    时间: 2004-03-02 17:21
标题: 【原创】超强版 Trim 横空出世！
不好意思刚才出去吃饭了，刚回来，我根本没激动，只不过我觉得tail的指针处理上有问题，手里没有编译器，这段代码考一下，回去调试调试。
作者: w25    时间: 2004-03-02 17:22
标题: 【原创】超强版 Trim 横空出世！
现在想找楼主研究一下，遗憾！晚了！！！555
作者: BingbingNorth    时间: 2004-03-02 17:32
标题: 【原创】超强版 Trim 横空出世！
flw老兄的代码写得非常好，我是绝对写不出来的，在这个问题上，我只发表过一次代码，而且效率不高，剩下的帖子，倒像个批评家。
不过，这次我还是想做一次批评家，请大家不要介意。
1。如果该字符串前部没有空格（或空格串），只有尾部有，那么，if ( tail )这个条件判断就要进行O(n)次，这完全可以用分情况的办法解决，当然，大家会说，如果分情况的话，源代码就不会这么简洁了，那么*copied++ = *str出现过两次，也不简洁，但是效率比提到条件语句外稍高一点。
2。在《如何又简洁又安全地去掉字符串前面和后面的空符号？》中，大家降低时间复杂性的方法是在到达字符串结尾后又折回来。flw兄的是利用了tail变量来记住应该赋'\0'值的位置，但是这样一来，每次都要进行tail = copied; 赋值操作或者是if ( tail )比较+转跳操作，时间复杂性一下子加了一倍，在具有超流水线的机器中效率将会更低。
3。用strlen()或者memmove()的算法实际执行效率可能最高
大家可以试试用for循环来实现strlen()和memmove(),看看运行效率比它们低多少，稍微用心一点的strlen()等函数的实现都会用串处理指令，其运行效率，比用for循环高多了，但是高多少又无法像美国1787年宪法规定的“黑人人口按实际的四分之三折算”那样加以量化，因此是“可能”最高。
请大家多对我的看法提宝贵意见。
作者: Wangwen    时间: 2004-03-02 18:05
标题: 【原创】超强版 Trim 横空出世！
tail 用的精妙
作者: flw    时间: 2004-03-02 19:16
标题: 【原创】超强版 Trim 横空出世！
[quote]原帖由 "FH"]这个算法在尾部空格较多时有损失。 [/quote 发表：

有什么损失？这个损失可以避免吗？
要想知道字符串中有没有空格、有多少空格，至少要将字符串扫描一遍，
而我的程序就只扫描了一遍。
我想，还不至于有一种算法可以扫描一半就知道用不用去空格吧？

[quote]原帖由 "FH"]我再给你简化一下，主要是从效率角度考虑[/quote 发表：

你说的“简化”“效率”指的是“尽量少引用指针”吗？
我实在想不通，用 c 来代替 *str 有什么好。
作者: flw    时间: 2004-03-02 19:32
标题: 【原创】超强版 Trim 横空出世！
[quote]原帖由 "BingbingNorth"]如果该字符串前部没有空格（或空格串），只有尾部有，那么，if ( tail )这个条件判断就要进行O(n)次，这完全可以用分情况的办法解决[/quote 发表：

请问，如何“分情况”？
咱们先不考虑简洁不简洁的因素，就看效率。

[quote]原帖由 "BingbingNorth"]大家降低时间复杂性的方法是在到达字符串结尾后又折回来。flw兄的是利用了tail变量来记住应该赋'\0'值的位置，但是这样一来，每次都要进行tail = copied[/quote 发表：

这个不然，好象“赋值”运算似乎的确要比“循环碰到结尾再退回来”时的指针“减减”的效率要低些？不过，若是“循环碰到结尾再退回来”，还需要判断循环条件，按照平均情况来考虑，难道一个赋值语句的执行效率尚不如“减减”加上“判断循环条件”两个运算的效率？何况，我又不是每次都要赋值，只是当 *str 所指为“黑字符”时才赋值。卿之所言，甚难服众。

[quote]原帖由 "BingbingNorth"]串处理指令[/quote 发表：

愿闻其详，望不吝赐教！
作者: forest077    时间: 2004-03-02 20:39
标题: 【原创】超强版 Trim 横空出世！
FH的代码和楼主的区别在于，用c=*str和*copied++=c来代替了*copied++=*str这一步，这实际上比起原来的代码反而多了一次赋值，而引用指针的次数却并不少。所以这段改过的代码效率不见得提高，反而降低了。
以前的帖子用到算法中有指针扫描到字符串结尾后又回溯的方式，这样对于最后一个非空字符后面的每个字符都做了一遍＋＋和--运算。而楼主的帖子是做了一遍＋＋和一遍赋值运算，效率应该都差不太多。
strlen和memmove我没研究过，不知效率如何，不敢妄言。
作者: FH    时间: 2004-03-02 22:04
标题: 【原创】超强版 Trim 横空出世！
我说一下我的意见：

用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    时间: 2004-03-02 22:08
标题: 【原创】超强版 Trim 横空出世！
要不先把两段代码编译出来，看看目标文件的长度？
作者: win_hate    时间: 2004-03-02 22:13
标题: 【原创】超强版 Trim 横空出世！

  2. #include <stdio.h>;
  3. #include <ctype.h>;

  5. void str_trim ();

  7. int
  8. main ()
  9. {
  10.         char buf[1024] = "ab                cd         ";
  11.         str_trim (buf);
  12.         puts (buf);
  13.         return 0;
  14. }

  16. void
  17. str_trim (char *str)
  18. {
  19.         char *save = str;
  20.         char *b;

  22.         if (str == NULL)
  23.                 return;

  25.         if (isspace (*(b = str)))
  26.           {
  27.                   while (*b)
  28.                     {
  29.                             if (isspace (*b))
  30.                                     b++;
  31.                             else
  32.                                     break;
  33.                     }

  35.                   while (*b)
  36.                             *str++ = *b++;

  38.                   str--;
  39.                   while (isspace (*str))
  40.                         str--;

  42.                   str[1] = '\0';
  43.           }
  44.         else
  45.           {
  46.                   while (*b)
  47.                           b++;

  49.                   b--;
  50.                   while (isspace (*b))
  51.                           b--;
  52.                   b[1] = '\0';
  53.           }
  54.           return;
  55. }

复制代码


实现特点：
1、 采用 ansi c 中的宏 isspace
2、 处理了开始字节非"space" 的情况。
3、 仍然采用"回溯"的方式。优点是只对 开始的空白和最后的空白进行 isspace 判断。
4、 后面有很多空格的时候， 这个算法的效率仍值得推敲。
作者: win_hate    时间: 2004-03-02 22:30
标题: 【原创】超强版 Trim 横空出世！
BinBinNorth 与 FH 兄对 strlen 和 memcpy  的看法是有道理的。其实我很久以前就想做个测试， 不过要么没时间，要么就太懒，x86 不同指令的效率，总是使我很头疼)。先这么写了。

至于 c = *str 的优化，我把希望寄托在编译器的优化上了。
作者: FH    时间: 2004-03-02 22:44
标题: 【原创】超强版 Trim 横空出世！
呵呵，刚测了一百万次，没什么差别，分别是18秒和19秒，一千万次差别还稍微大一点。
测试用代码如下，编译时使用了-O选项：

  2. #include        <string.h>;

  4. #define        STRSZ        4096
  5. #define        TIMES        10000000

  7. extern void trim( char *str );

  9. main()
  10. {
  11.         int        i;
  12.         char        s[STRSZ];

  14.         for ( i = 0; i < TIMES; i ++ ) {
  15.                 memset( s, ' ', STRSZ - 1 );
  16.                 s[STRSZ - 1] = 0;
  17.                 trim( s );
  18.         }
  19. }
复制代码


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

  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    时间: 2004-03-03 08:43
标题: 【原创】超强版 Trim 横空出世！
这是我去两头空格的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    时间: 2004-03-03 10:30
标题: 【原创】超强版 Trim 横空出世！
我写的一个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>;

  6. void trim1( char *str )
  7. {
  8.         char *copied, *tail = NULL;

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

  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.         }

  27.         if ( tail )
  28.              *tail = 0;
  29.         else
  30.              *copied = 0;

  32.         return;
  33. }

  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. }

  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();

  87.         return 0;
  88. }
复制代码
作者: FH    时间: 2004-03-03 11:30
标题: 【原创】超强版 Trim 横空出世！
[quote="guixin"][/quote]
用chr[i]这种方式效率肯定比用指针慢很多。
作者: converse    时间: 2004-03-03 11:37
标题: 【原创】超强版 Trim 横空出世！
库函数的实现各个编译器可能不同，比如strlen这样的字符串操作，可能是在底层用汇编的串操作实现的，所以效率高也不足为奇，另外如果真的是用汇编实现的话，这么比较似乎也不公平，总而言之，flw的算法思想是很不错的
作者: w25    时间: 2004-03-03 12:25
标题: 【原创】超强版 Trim 横空出世！
从程序的简练角度讲，楼主的程序确简练到了顶点，不可能在用到更少的指针变量，思路也很不错，但是当输入的数据是"a                。。。 "的情况下，因为只有一个数据，copied指针却从头跑到了尾。在这一点上我认为不是很有效率，str指针要从头检到尾市一定的。而记录最后空格前的地址也是必需的。昨天向调试一下代码，但是喝多了。白天我写了一个程序，但怎么看都是楼主程序的孪生兄弟，看不出有什么特点。我从数据传输的方式上想到了另一个算法，我写出来，linux上我没有试。程序用到了一个指针copy，和3各整形变量，（是不是很浪费？？/）
楼主的数据输入通常使用向前移动字符，我的想法很简单，不用移动数据，只是纪录有效数据的距离初始指针的位置，那样的话一定要有个变量保存他了，还有这个指针是纪录有效数据结尾，处理上和楼主的茶不过。
思路是：处理的数据分为两类，一类是字符等有效数据，另一类是空格等数据（另外我把NULL归为这一类）。这样对数据的处理就简单了，无非是要么有效，要么无效，很像高低电平？？其实程序也正是借助这个思想，当数据读入第一个数据后，第二个数据与第一个数据相同，那么copy不动，因为都是一样的数据，但如果第二个数据与第一个数据不同，那么copy就会向相反的方向变化，这样解决了我说的那种不适合楼主程序的数据输入。copy不会跟在str会面走，只是需要他走的时候才走。
#include <stdio.h>;
int trim(char *str)
{
    char *copy= NULL;
    int changed=0;
    int sum=0;
    int firsttime=1;
   
    if (str==NULL) return 0;

    for(copy=str;*copy;str++)
    {
        if(*str==NULL) break;
        if (*copy!=' ')
        {
            if(*str==NULL) {copy=str;break;}
            if((*str!=' ')&&(*str!=NULL)) {changed=0;firsttime=0;}
            else changed=1;
            if(changed==1) copy=str;
        }
        else
        {
            if(*str==NULL) break;
            if((*str!=' ')&&(*str!=NULL)) changed=1;
            else changed=0;
            if(changed==1) {copy=str;firsttime=0;}
            if((changed==0)&&(firsttime==1)) sum+=1;
        }
    }
    *copy=0x0;
    return sum;
}

void main()
{
    char ss[]="          fsfdas   ffsa  df   ";
    int i=0;
    i=trim(ss);
    printf("%s!!!\n",ss+i);
}
不知晓率如何，我想可能没有指针快。
作者: win_hate    时间: 2004-03-03 12:30
标题: 【原创】超强版 Trim 横空出世！
BingBingNorth 的测试数据有点问题:

基本没有空格了, 前面一个空格, 后面一个空格,  这个情况很特殊.
BingBingNorth 的算法只对前面的空格和后面的空格采用 isspace, 而 flw 的算法则对每个字符都进行了 isspace, 于是就吃亏了.

如果前后空格很多, 估计情况会有变化.

就 BingBIng 这个例子, 我在 Redhat  AS 2.1上测了一下,  我的代码是最快的.

flw  4.7
BingBing 2.8
me 1.7

测试时间用 clock 比较好, time 只能精确到秒. 或者干脆用 unix 的  time 命令好了
作者: BingbingNorth    时间: 2004-03-03 12:59
标题: 【原创】超强版 Trim 横空出世！
win_hate兄的代码的写法体现我前面说的第一点和第二点，也和《如何又简洁又安全地去掉字符串前面和后面的空符号？》中效率最高的算法不谋而合。
另外，用strlen()和memmove()的究竟效率高不高，这很难说，因为不知道底层究竟是怎么实现的，我原来以为这些操作都是用汇编写的，就像FH兄的帖子里写的那样，可是从结果看，应该是我错了。
作者: FH    时间: 2004-03-03 13:31
标题: 【原创】超强版 Trim 横空出世！
呵呵，刚看了一下Linux的strlen，不是用串指令实现的，可能是为了char的扩展性吧，采用的是逐char比较的方式，而memcpy是使用的串指令。

楼主的算法确实很不错了，建议加精。
作者: win_hate    时间: 2004-03-03 13:38
标题: 【原创】超强版 Trim 横空出世！
[quote]原帖由 "BingbingNorth" 发表：
win_hate兄的代码的写法体现我前面说的第一点和第二点，也和《如何又简洁又安全地去掉字符串前面和后面的空符号？》中效率最高的算法不谋而合。
另外，用strlen()和memmove()的究竟效率高不高，这很难说，因为不知
作者: FH    时间: 2004-03-03 13:41
标题: 【原创】超强版 Trim 横空出世！
isspace的真值条件为：HT，VT，CR，LF，FF五个特殊字符。
作者: flw    时间: 2004-03-03 13:48
标题: 【原创】超强版 Trim 横空出世！
大家争论的结果正好说明了一个问题，
那就是说，简洁的程序未必运行得快，
而繁复的程序未必运行得慢。
而我们程序员们，通常有很多时间都在选择，到底是应该把程序写的更加简练一些，还是写的繁复一些呢？

正所谓仁者见仁，智者见智，不同的情况下，可能需要不同的策略，
比如说在某些受限系统中，可能多浪费一个变量的空间都会带来严重的后果，这时候呢，可能就需要空间复杂度低一些的代码。反过来，在其它的场合，可能需要其它的策略。


需要说明的一点是，由于我这个程序用的是指针来实现，而没有依赖字符串的任何特点（没有使用 strlen、strcpy、memcpy 等等），所以应该是可以移植到任何类似的数据类型中，比如链表。但是就目前而言，我还没有想到有什么其它地方能有类似的需求，所以也只是一句空话罢了。

还有一个观点需要说明，考虑到函数调用所需要的入栈、出栈的时间，所以我不习惯在循环中反复调用函数。就 isspace 而言，我虽然并不知道 isspace 内部是如何实现的（是不是又用了什么专用的指令？），但是直觉告诉我，isspace 并不会比直接比较的效率高。可能还会更低也说不定。
作者: win_hate    时间: 2004-03-03 13:56
标题: 【原创】超强版 Trim 横空出世！
原帖由 "flw"]还有一个观点需要说明，考虑到函数调用所需要的入栈、出栈的时间，所以我不习惯在循环中反复调用函数。就 isspace 而言，我虽然并不知道 isspace 内部是如何实现的（是不是又用了什么专用的指令？），但是直觉告诉我，isspace 并不会比直接比较的效率高。可能还会更低也说不定。[/quote 发表：


isspace 是一个宏, 确实要慢一些, 因为如 FH 兄所言:

[quote]
isspace的真值条件为：HT，VT，CR，LF，FF五个特殊字符。


不过也可以用自定义的宏或直接写了, 我觉得 isspace 简洁一些而已.

更正, 我查了查资料,  isspace 应该是个函数.
作者: FH    时间: 2004-03-03 14:15
标题: 【原创】超强版 Trim 横空出世！
我的倾向是尽可能使程序简练一些，尽可能使别人能够容易看懂，对于那些对效率要求严格的场合，直接用汇编精雕细刻。
作者: guixin    时间: 2004-03-03 17:27
标题: 【原创】超强版 Trim 横空出世！
我觉得程序月简单越短越好，
重要的是维护成本低，可以很好的解决问题！
作者: lenovo    时间: 2004-03-03 18:22
标题: 【原创】超强版 Trim 横空出世！
原帖由 "guixin" 发表：
我觉得程序月简单越短越好，
重要的是维护成本低，可以很好的解决问题！

程序越短越容易理解吗？
不一定吧。
作者: ii2004    时间: 2004-03-03 23:39
标题: 【原创】超强版 Trim 横空出世！
工具函数效率越高越好，不需要为读者多考虑，因为会去读它的人都是有能力去读它的。
应用程序越简单越好，易读性越高越好。不需要考虑代码效率，因为CPU会越来越快。
作者: win_hate    时间: 2004-03-04 11:04
标题: 【原创】超强版 Trim 横空出世！
原帖由 "ii2004" 发表：
工具函数效率越高越好，不需要为读者多考虑，因为会去读它的人都是有能力去读它的。
应用程序越简单越好，易读性越高越好。不需要考虑代码效率，因为CPU会越来越快。


ii2004  与 ii2002 是什么关系啊?      
作者: rollingpig    时间: 2004-03-04 13:42
标题: 【原创】超强版 Trim 横空出世！
听诸君几页话
胜读N本书
作者: nicksean    时间: 2004-03-04 16:07
标题: 【原创】超强版 Trim 横空出世！
长见识了！
作者: guixin    时间: 2004-03-04 17:18
标题: 【原创】超强版 Trim 横空出世！
原帖由 "lenovo" 发表：

程序越短越容易理解吗？
不一定吧。


程序越短越容易理解吗？当然不是的

是又简单又短那，没什么其它的
作者: noress    时间: 2004-03-05 13:51
标题: 【原创】超强版 Trim 横空出世！
FH的代码:

  2. void trim( char *str )
  3. {
  4.         char *copied;
  5.         char *tail;
  6.         char c;

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

  11.         for ( copied = str, tail = NULL; ( c = *str ) != 0; str ++ )
  12.         {
  13.                 if ( c != ' ' && c != '\t' )
  14.                 {
  15.                         *copied ++ = c;
  16.                          tail = copied;
  17.                 }
  18.                 else
  19.                 {
  20.                          if ( tail != NULL )
  21.                                  *copied ++ = c;
  22.                 }
  23.         }

  25.         if ( tail != NULL )
  26.              *tail = 0;
  27.         else
  28.              *str = 0;
  29. }
复制代码

似乎没什么改变,反而多用了一个变量,还多了N次赋值,算法都是一样的.
作者: w25    时间: 2004-03-05 15:44
标题: 【原创】超强版 Trim 横空出世！
要说楼主的算法结为只需用*tail = 0;就行了，何必总写那么多。要是这种思路的话，算法无非就是一个指针记录结为。一个指针跟着str走，不可能有更大的提高了。
作者: FH    时间: 2004-03-05 16:27
标题: 【原创】超强版 Trim 横空出世！
[quote="noress"]似乎没什么改变,反而多用了一个变量,还多了N次赋值,算法都是一样的.[/quote]

loop一千万次你会看到差别的，前面有我的实测报告。
本身也不是我的代码，是我稍加修改的。
作者: FH    时间: 2004-03-05 16:31
标题: 【原创】超强版 Trim 横空出世！
[quote="w25"]要说楼主的算法结为只需用*tail = 0;就行了，何必总写那么多。要是这种思路的话，算法无非就是一个指针记录结为。一个指针跟着str走，不可能有更大的提高了。[/quote]

还有潜力的，不要一个字节一个字节地复制，记下首尾位置，用memcpy一次复制。
作者: win_hate    时间: 2004-03-05 20:01
标题: 【原创】超强版 Trim 横空出世！
与本贴相关的连接：

http://www.chinaunix.net/jh/23/230114.html
http://bbs.chinaunix.net/forum/23/20040305/274341.html
http://bbs.chinaunix.net/forum/23/20040309/277036.html
http://bbs.chinaunix.net/forum/23/20040516/326132.html
作者: whyglinux    时间: 2004-03-07 16:33
标题: 【原创】超强版 Trim 横空出世！
原帖由 "FH" 发表：

还有潜力的，不要一个字节一个字节地复制，记下首尾位置，用memcpy一次复制。


看了man里的说明，说当目的和源内存空间有重叠的时候，应该用 memmove ，memcpy 用于没有重叠的情况。可是试了试即使重叠的时候，用 memcpy 也行。真是困惑呀。
作者: improgrammer    时间: 2004-05-21 13:36
标题: 【原创】超强版 Trim 横空出世！
不赞成这种写法。
——虽然少了循环，但循环内加入if分支，对效率又无益了。
不如直白些：

  2. char *trim(char *s)
  3. {
  4.         char *p,*q;
  5.         for(p=s;*p==' '||*p=='\t';++p);
  6.         for(q=s;*q++=*p++;);
  7.         for(;*(q-1)==' '||*(q-1)=='\t';--q);
  8.         *q=0;
  9.         return s;
  10. }
复制代码
作者: win_hate    时间: 2004-05-21 13:41
标题: 【原创】超强版 Trim 横空出世！
哈，还浮上来，又刮台风了。

原帖由 "whyglinux" 发表：


看了man里的说明，说当目的和源内存空间有重叠的时候，应该用 memmove ，memcpy 用于没有重叠的情况。可是试了试即使重叠的时候，用 memcpy 也行。真是困惑呀。




重叠的时候，是否能用 memcpy 取决于 copy 的方向。如果从低地址向高地址copy，就完蛋了。你可以再试一次。
作者: improgrammer    时间: 2004-05-21 13:43
标题: 【原创】超强版 Trim 横空出世！
或者免拷贝：

  2. char *trim2(char *s)
  3. {
  4.         char *p,*q;
  5.         for(;*s==' '||*s=='\t';++s);
  6.         if(*s==0)
  7.                 return s;
  8.         for(p=s;*p;++p);
  9.         for(--p;*p==' '||*p=='\t';--p);
  10.         *(++p)=0;
  11.         return s;
  12. }
复制代码
作者: windflowers1976    时间: 2004-05-21 14:55
标题: 【原创】超强版 Trim 横空出世！
斑竹,评个好的,俺也偷懒下,把它入库吧.呵呵.
作者: jsean    时间: 2004-05-25 14:31
标题: 【原创】超强版 Trim 横空出世！
奇怪，flw版主的程序我在windows下运行怎么报内存访问异常呢？

单步跟踪时发现是运行到
第一个
*copied++ = *str;

语句时报的，真是奇怪，难道是vc用的编译器的问题？
作者: db_info    时间: 2004-05-25 16:07
标题: 【原创】超强版 Trim 横空出世！
我用
char *tmp="     hello     ";
trim(tmp);
程序Segmentation fault
作者: bjf    时间: 2004-05-25 16:18
标题: 【原创】超强版 Trim 横空出世！
不错不错。这类程序在正确的前提下，效率第一，可读性第二。
作者: hanni    时间: 2004-05-27 10:11
标题: 【原创】超强版 Trim 横空出世！
ret hat linux 下运行flw楼主的程序 Segmentation fault (core dumped)
作者: windflowers1976    时间: 2004-05-27 10:19
标题: 【原创】超强版 Trim 横空出世！
原帖由 "db_info" 发表：
我用
char *tmp="     hello     ";
trim(tmp);
程序Segmentation fault

这是你的问题,常量怎么可以trim?
作者: hanni    时间: 2004-05-27 10:52
标题: 【原创】超强版 Trim 横空出世！
char *tmp=" hello ";
这是定义字符型指针变量并初始化，怎么是常量呢？
作者: FH    时间: 2004-05-27 11:37
标题: 【原创】超强版 Trim 横空出世！
你指针指向的地址是在只读空间
作者: windflowers1976    时间: 2004-05-27 11:55
标题: 【原创】超强版 Trim 横空出世！
原帖由 "hanni" 发表：
char *tmp=" hello ";
这是定义字符型指针变量并初始化，怎么是常量呢？

请首先弄明白什么是字符型指针赋值与字符型指针内容初始化.
char szTmp[20] = " hello "; 就可以trim.
char *tmp = " hello"; 则是把tmp 的值赋为常量指针" hello " 的首地址.
不可以trim.
作者: hanni    时间: 2004-05-27 15:33
标题: 【原创】超强版 Trim 横空出世！
原帖由 "windflowers1976" 发表：
hello "; 就可以trim.
char *tmp = " hello"; 则是把tmp 的值赋为常量指针" hello " 的首地址.
不可以trim.

您的说法我认为有误。

char *tmp = " hello";是用初始化赋值的方法写成这样的.
含义是：把存放该字符串"hello"的字符数组的首地址装入指针变量tmp中.
而不能用常量指针" hello "这样的说法。您说呢？

常量在c语言里，用#define定义，在c++中用const或者define定义。
作者: xhl    时间: 2004-05-27 15:45
标题: 【原创】超强版 Trim 横空出世！
windflowers1976  说的很清楚了，
你char *tmp = " hello"; 是想用tmp来操作常量"hello",

如果想用指针，可以给他分配空间，malloc()后，再memcpy(tmp,"hello",6);这样才可以。
作者: windflowers1976    时间: 2004-05-27 15:52
标题: 【原创】超强版 Trim 横空出世！
晕哦,跟我争的淅沥哗啦的,呵呵.
K&R C PROGRAMMING LANGUAGE 第二版 英文版
  1. P104
  2. Then the stattement
  3.     pmessages = "now is the time";
  4. assigned to pmessages a pointer to the character array.This is not a string copy; only pointers are involved.
复制代码

麻烦你也去翻C语言的书,好不好?
const 修饰才叫常量吗?
呵呵.
打住.
作者: hanni    时间: 2004-05-27 16:09
标题: 【原创】超强版 Trim 横空出世！
但是有可能在进行指针操作的时候，对"hello"进行篡改，而这种情况往往是无法预见的哦！c语言就是太灵活了，还是要强定义的好，要不然有c就可以，用不着推c++....等等.
作者: whyglinux    时间: 2004-05-27 16:31
标题: 【原创】超强版 Trim 横空出世！
原帖由 "windflowers1976" 发表：
hello "; 就可以trim.
char *tmp = " hello"; 则是把tmp 的值赋为常量指针" hello " 的首地址.
不可以trim.

说明有误，难怪会引起hanni的误解了。把上面的“常量指针”改为“常量字符串”就可以了。

原帖由 "hanni" 发表：

char *tmp = " hello";是用初始化赋值的方法写成这样的.
含义是：把存放该字符串"hello"的字符数组的首地址装入指针变量tmp中 .

正确的说法是“把存放该字符串"hello"的首地址装入指针变量tmp中. ”，"hello"这个字符串并没有放到一个字符数组中（你没有定义，哪来的字符数组？），它是一个常量（字符型），一般不能对它进行修改操作。

>;>; 但是有可能在进行指针操作的时候，对"hello"进行篡改，而这种情况往往是无法预见的哦！
那是因为 char *tmp = " hello";这样的定义不是太确切，应该这样定义：const char *tmp = " hello";就可避免你说的通过 tmp指针对字符串修改的情况。如果想通过指针变量对字符串进行修改：1. 在字符数组中存储字符串（不能用字符串常量）；2.  指针变量不能声明为const 指针。
作者: 飞灰橙    时间: 2004-06-14 09:08
标题: 【原创】超强版 Trim 横空出世！
原帖由 "whyglinux" 发表：

char *tmp = " hello";这样的定义不是太确切


char *tmp = "hello",
把一个const赋为一个非const
奇怪的是编译器居然连个warning都没有
各位好兄弟能给个解释么？不解啊！（我用的是gcc 3.2）
作者: devia    时间: 2006-03-18 19:43
标题: 回复 1楼 flw 的帖子
对const char *或const char * const类型的调用就是调用者的问题了。

[ 本帖最后由 devia 于 2006-3-18 20:17 编辑 ]
作者: Yarco    时间: 2006-03-18 21:40
提示: 作者被禁止或删除 内容自动屏蔽
作者: pcboyxhy    时间: 2006-03-19 03:25
不知道这个如何

void trim( char *str )
{
    char *s=str, *e=str, p;
    while((*s=='\t') || (*s==' ') ) s++;
    while(p = *str++ = *s++ )
        if( (p!=' ') && (p!='\t') )
            e=str;
    *e = '\0';  
}
作者: xiaonanln    时间: 2006-03-19 08:11
楼主的程序在复制每一个字符时都要做至少一个比较，我觉得性能应该不如先确定两头，然后复制中间的算法
作者: shellone    时间: 2006-03-19 10:31
标题: 俺也来贴一个，稍微改改，就可以去处space,'\n'等等,或者改为trimleft,trimright
extern char * trim(char *s)
{
   int first=0;
   int len;
   int i;
   char *p = s;
   
   if (s == (char *)0) return;

   len = strlen((char *) s);

   {
      while (first<len) {
         if (!isspace((unsigned char)s[first]))
            break;
         first++;
      }
   }

   if (first>=len) {
      *s = '\0';
      return p;
   }
   else
      memmove((char *) s, (char *) s+first, strlen(s+first)+1);

   for (i=(int)strlen((char *) s)-1; i >= 0; i--)
      if (!isspace((unsigned char)s[i])) {
         s[i+1] = '\0';
         return p;
      }
   if (i<0) *s = '\0';
   return p;
}
作者: flw    时间: 2006-03-19 12:17
原帖由 xiaonanln 于 2006-3-19 08:11 发表
楼主的程序在复制每一个字符时都要做至少一个比较，我觉得性能应该不如先确定两头，然后复制中间的算法

问题是，什么叫“两头”？你怎么知道“两头”？
作者: bleem1998    时间: 2006-03-19 12:32
在寻找‘两头’的过程中是需要付出代价的
俺盯着LZ的程序看老半天了始终看不懂
惭愧了我！！！
太缺乏理解别人程序的能力
同事说我好多次了


BTW
两年前的帖都翻出来啦
这个帖子的帖龄比不少人的CU龄都长



总算看懂
确实经典

[ 本帖最后由 bleem1998 于 2006-3-19 12:51 编辑 ]
作者: pcboyxhy    时间: 2006-03-19 16:51
如果是自己封装过的特殊字符串
比如用一个变量记录字符串的长度，并且动态改变
先确定两头 然后memmove倒是不错的
作者: xfly_t    时间: 2006-03-19 19:02
不记得在那看到的,下面的代码还不错,更具通用性吧!

char * trim(char *p, const char *delim)
{
    int len;
    len = strlen(p);
    while ( (len > 0) && strchr(delim, p[len - 1] ) ) {
        p[len - 1] = '\0';
        len--;
    }
    while ( (*p)&&(strchr(delim,*p)) ) p++;

    return(p);
}
作者: shappen    时间: 2006-03-19 23:22
太棒了
感觉要是于优化的话还有一个地方：
if ( tail )
这在第一次对tail进行赋值后直到循环结束就一直为真，是不是可以在这个判断上优化一下，当处理字符串后面的空白时可以减少一些比较，不知道这样对不对
作者: handsome-king    时间: 2006-03-22 20:00
不知道我这个段代码怎么样：
trim( char *s )
{
        char *p=s;

        while (*p) p++;
        while (p>s && ( (*(p-1)==' ') || *(p-1)=='\n' ) ) p--;
        *p='\0';
}
作者: shappen    时间: 2006-03-25 22:23
原帖由 handsome-king 于 2006-3-22 20:00 发表
不知道我这个段代码怎么样：
trim( char *s )
{
        char *p=s;

        while (*p) p++;
        while (p>s && ( (*(p-1)==' ') || *(p-1)=='\n' ) ) p--;
        *p='\0';
}


好像在最好的情况下也只能去掉串后面跟着的空白，一般情况下（开头有空白）那么最后什么都没有了，串被赋值成'\0'了
作者: MackedNice    时间: 2006-06-20 21:39
标题: 我的这个应该是很快的。哈哈哈。。
void trim2(char *str)
{
    char *be, *end, *p;
    int i = 1;
    be = end = NULL;
    for(p = str;*p;p++)
    {
        if(*p != ' ' && *p != '\t')
        {
                if(i == 1)
                {
                  be = p;        // begin
                }
                end = p;         // end
                i++;
        }
    }
    memcpy(str,be,end-be+1);
    *(str+(end-be+1)) = 0;
}
作者: MackedNice    时间: 2006-06-20 21:44
标题: 上面的没有进行错误的检查
void trim2(char *str)
{
    char *be, *end, *p;
    int i = 1;
    if(str == NULL)
        return;
    be = end = NULL;
    for(p = str;*p;p++)
    {
        if(*p != ' ' && *p != '\t')
        {
                if(i == 1)
                {
                  be = p;        // begin
                }
                end = p;         // end
                i++;
        }
    }
    memcpy(str,be,end-be+1);
    *(str+(end-be+1)) = 0;
   
    return;
}

这个是进行输入参数错误检查的。
作者: mik    时间: 2006-06-20 21:47
原帖由 MackedNice 于 2006-6-20 21:39 发表
void trim2(char *str)
{
    char *be, *end, *p;
    int i = 1;
    be = end = NULL;
    for(p = str;*p;p++)
    {
        if(*p != ' ' && *p != '\t')
        {
                if(i ...



你的函数既不能完成任务，又不快

已收回这句话，不好意思地说！

[ 本帖最后由 mik 于 2006-6-21 00:04 编辑 ]
作者: MackedNice    时间: 2006-06-20 21:59
谁说的。我测试过的。。
为什么这么说？
作者: MackedNice    时间: 2006-06-20 22:03
标题: 这是我测试的程序在dev-c++编译通过。。
#include <stdio.h>
#include <string.h>
#include <memory.h>

void trim1( char *str )
{
        char *copied, *tail = NULL;

        if ( str == NULL )
                return;

        for( copied = str; *str; str++ )
        {
                if ( *str != ' ' && *str != '\t' )
                {
                        *copied++ = *str;
                         tail = copied;
                }
                else
                {
                         if ( tail )
                                 *copied++ = *str;
                }
        }

        if ( tail )
             *tail = 0;
        else
             *copied = 0;

        return;
}
void trim2(char *str)
{
    char *be, *end, *p;
    int i = 1;
    if(str == NULL)
        return;
    be = end = NULL;
    for(p = str;*p;p++)
    {
        if(*p != ' ' && *p != '\t')
        {
                if(i == 1)
                {
                  be = p;        // begin
                }
                end = p;         // end
                i++;
        }
    }
    memcpy(str,be,end-be+1);
    *(str+(end-be+1)) = 0;
   
    return;
}

int main()
{
    char buff[50];
    char buff1[50];
    char *p = "    AAAA  BB      ";
    strcpy(buff,p);
    strcpy(buff1,p);
    printf("before buffer = [%s]\n",buff);
    trim1(buff);
    printf("after buffer = [%s]\n",buff);
    printf("before buffer1 = [%s]\n",buff1);
    trim2(buff1);
    printf("after buffer1 = [%s]\n",buff1);
   
    return 0;
}
作者: mik    时间: 2006-06-20 23:01
原帖由 MackedNice 于 2006-6-20 21:59 发表
谁说的。我测试过的。。
为什么这么说？



不好意思，你的代码是对的，我改正！ 我没仔细看lz的贴子，

你的代码也不错啦！

[ 本帖最后由 mik 于 2006-6-21 00:00 编辑 ]
作者: flw    时间: 2006-06-21 08:20
其实就这个问题来讲，57 楼之前已经把所有的细节都讨论清楚了，
当然了，这主要是因为这个帖子发表的时候，
前面还有几篇帖子已经较深入地讨论过这个问题了。

从 57 楼开始，水平就直接下降。
很多人开始讨论一楼的函数是否正确，再或者莫名其妙地附上自己的程序（不知目的何在？）
基本上可以说，从 57 楼开始，这个帖子就只剩下娱乐意义，而失去学术意义了。
作者: MackedNice    时间: 2006-06-21 09:03
不好意思。。
是昨天刚看到这帖子
觉得很不错的一个帖子。
所以就试着写了一下。
没有想到楼主的感觉。
向你道歉了。

没有什么目的，也不是为了娱乐。
就是跟大家。交流一下而已。
作者: deathbravo    时间: 2006-06-21 09:51
挖坟的能力很强啊
作者: liubinbj    时间: 2006-06-21 17:45
这种函数设计上就是错的：void trim(char* s)
应该是这样 char* trim(char* s)
似乎坛子里没人指出这一点，悲哀，大多数的中国程序员就是这么写程序的，还以为很高明。
作者: FH    时间: 2006-06-21 21:36
原帖由 liubinbj 于 2006-6-21 17:45 发表
这种函数设计上就是错的：void trim(char* s)
应该是这样 char* trim(char* s)
似乎坛子里没人指出这一点，悲哀，大多数的中国程序员就是这么写程序的，还以为很高明。


后一种定义用起来方便，但前一种也没有错啊？
作者: liubinbj    时间: 2006-06-22 15:57
原帖由 FH 于 2006-6-21 21:36 发表


后一种定义用起来方便，但前一种也没有错啊？


语法是对的，设计是错的，那就是错的，你看看微软的大牛会这样定义trim吗？你觉得glibc会这么定义trim吗？严重误人子弟。
作者: FH    时间: 2006-06-22 23:00
原帖由 liubinbj 于 2006-6-22 15:57 发表


语法是对的，设计是错的，那就是错的，你看看微软的大牛会这样定义trim吗？你觉得glibc会这么定义trim吗？严重误人子弟。


char *的返回值用途广泛些，但是多了一个return也是开销啊！
侧重点不同罢了。
作者: 流川    时间: 2006-06-23 01:21
这段代码不用太紧张吧
作者: ccjjhua    时间: 2006-07-03 16:47
这是我写的一个剔出前后空格的函数，优点就是没有进行内存的搬移，缺点是要引用函数的返回值，而且对传入参数的内存值有一处修改。
char * my_trim(const char *str)
{
        char *p_str;
        char * head;

        if(str == NULL)
                return NULL;
        head = NULL;

        for(p_str=str;*p_str;p_str++)
        {
                if(*p_str == ' ' || *p_str == '\t')
                        continue;
                else
                {
                        head = p_str;
                        break;
                }
        }

        for(p_str=head+strlen(head)-1;p_str >= head;p_str--)
        {
                if(*p_str == ' ' || *p_str == '\t')
                        continue;
                else
                {
                        *(p_str+1) = 0;
                        break;
                }
        }

        return head;

}

[ 本帖最后由 ccjjhua 于 2006-7-3 16:52 编辑 ]
作者: ccjjhua    时间: 2006-07-03 16:49
本着学习的态度，要了解一下高手们都是怎么想的。
作者: zhugcx    时间: 2009-03-13 16:04
char *strim(char *str)
{
        char *p = str;
        if (NULL == p)
        {
                return NULL;
        }
        char *s = NULL;
        char *e = NULL;
        while(*p != '\0')
        {
                if (' ' == *p)
                {
                        if (NULL != s && NULL == e)
                        {
                                e = p;
                        }
                }
                else
                {
                        if (NULL == s)
                        {
                                s = p;
                        }
                        e = NULL;
                }
                ++p;
        }

        if (NULL != e)
        {
                *e = '\0';
        }
        return s;
}

清晰版
作者: swxlion    时间: 2009-03-13 17:39
好吧。我是十全十美。第100楼



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2