The power of C, the power of MD

A problem is a chance to do your best
posts - 11, comments - 22, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

strcat在某种特定条件下的优化

Posted on 2010-07-28 21:46 roy 阅读(2124) 评论(10)  编辑 收藏 引用 所属分类: C/C++
strcatC语言一个基本的字符串操作函数,它的源代码一般是这样的。

char *strcat(char *dest, const char *src)   
{   
    
char *tmp = dest;   
    
while (*dest) dest++;   
    
while ((*dest++ = *src++!= '\0');   
    
return tmp;   
}
  


由此可见,strcat调用时,先移动目标字符串的指针到其尾部,再进行复制。这种做法对于下标比较大的数组重复调用时,效率比较低。想象一下,第一次调用strcat时,指针由0数到100,只不过复制了几个字符,第二次调用strcat时,指针又从0数到108,无论调用多少次,指针总是从0数起,就会知道这个时候是多么浪费系统资源了!

我找到一个办法,字符串追加时,事先给出目标字符串结尾所在的位置,追加时,也就不用从头开始计算其长度了,复制的过程中,目标字符串的结尾也随之移动,下一次再追加也就可以使用它了。以下就是优化过的string_append,与strcat相比,增加了一个整形指针以传递目标字符串长度的地址。

/*
 * optimizer for strcat when appending to a large array again and again
 
*/

char *string_append(char *dest, int *end, const char *src) {
    
if ( *end >= 0 && dest && src ) {
        
char *= dest + *end;
        
while ( *p++ = *src++ ) (*end)++;
    }

    
return dest;
}


经试验,string_append在大数组重复追加内容的情形下,优势非常明显。其它情形下,使用原来的strcat也就足够了。

#include <stdio.h>
#include 
<string.h>
#include 
<time.h>

#define BUFF_SIZE 4096

/*
 * optimizer for strcat when appending to a large array again and again
 
*/

char *string_append(char *dest, int *end, const char *src) {
    
if ( *end >= 0 && dest && src ) {
        
char *= dest + *end;
        
while ( *p++ = *src++ ) (*end)++;
    }

    
return dest;
}


int main() {
    
int i = 0, j = 0;
    
int retry = 100000;
    
int field = 100;
    
char output1[BUFF_SIZE], output2[BUFF_SIZE];
    time_t time1 
= time(NULL);
    
for ( i = 0; i < retry; i++ ) {
        memset(output1, 
0, BUFF_SIZE);
        
int length = 0;
        string_append(output1, 
&length, "header\n");
        
for ( j = 0; j < field; j++ ) {
            string_append(output1, 
&length, "\tcall detail record ");
            
char c[8];
            sprintf(c, 
"%d", j);
            string_append(output1, 
&length, c);
            string_append(output1, 
&length, "\n");
        }

        string_append(output1, 
&length, "trailer\n");
    }

    time_t time2 
= time(NULL);
    printf(
"It takes %d seconds to show the performance of string_append()\n", time2 - time1);

    time1 
= time(NULL);
    
for ( i = 0; i < retry; i++ ) {
        memset(output2, 
0, BUFF_SIZE);
        strcat(output2, 
"header\n");
        
for ( j = 0; j < field; j++ ) {
            strcat(output2, 
"\tcall detail record ");
            
char c[8];
            sprintf(c, 
"%d", j);
            strcat(output2, c);
            strcat(output2, 
"\n");
        }

        strcat(output2, 
"trailer\n");
    }

    time2 
= time(NULL);
    printf(
"It takes %d seconds to show the performance of strcat()\n", time2 - time1);
    
if ( strcmp(output1, output2) )
        printf(
"They are NOT equal\n");
    
else
        printf(
"They are equal\n");
    
return 0;
}

 

-bash-3.2$ ./string_append_demo

It takes 2 seconds to show the performance of string_append()

It takes 11 seconds to show the performance of strcat()

They are equal


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/yui/archive/2010/05/22/5616455.aspx

Feedback

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-07-28 23:55 by 陈梓瀚(vczh)
所以C++的string类都有记录长度的。

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-07-29 00:57 by lwch
没有检查缓冲区长度...
会造成溢出

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-07-29 09:03 by roy
@lwch

原始的strcat一样会溢出,这个问题应该由调用者负责

# re: strcat在某种特定条件下的优化[未登录]  回复  更多评论   

2010-07-29 12:04 by c++
我的程序里一直在strlen(name)。我想是该考虑string的记录len。

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-07-30 06:10 by hoodlum1980
在现实应用里,都是随机化的处理,使用你的方法,实际上还需要求一次strlen,这样也就没有什么优势(和实用性)可言了。
这是C字符串模型的一种特点(在这里体现出是缺点,但在其他大部分地方都体现的是高效和灵活性)导致的,例如其他有些语言的字符串是在前面存储字符串长度的,但是这样相对而言对字符串处理库函数会提高一些维护难度,因为总是要同时照顾这个长度信息。

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-08-02 09:24 by roy
@hoodlum1980

这个例子中,从来没用到strlen,而且,这是在某种特定条件下的优化,初始值是空串,长度为0,请看清楚

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-08-04 09:16 by roy
@hoodlum1980

唉,我反而觉得你没理解好,你是说每次调用string_append都要先调用strlen吗?根本不需要,每次string_append就已经计算了下一次执行时的偏移量了

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-08-06 02:55 by hoodlum1980
如果是每次你能知道是从哪里连接的场合,你只需要strcpy(s+length, src); 就好了呀。我的意思就是那个本来就是在常规场合使用的。也就是说,在你自己维护的上下文内,你当然能够尽可能的达到最精确的控制。但在各种交叉处理之中,strcat相对而言就是一种最通用和恰当的库函数之一。同时C字符串在效率上给了你充分的自由度。我说的就是在特定的应用场合当然可以根据其背景做出特定的优化,但是要做通用性的实现,因为考虑到通用性,不是所有的假设都能成立,特定的优化可能因而不宜提供,这也是C字符串库函数形成现在这个系列的原因了。

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-08-06 03:02 by hoodlum1980
简单说,strcat可以说是strlen和strcpy的功能叠加。如果使用strcat,通常也就是不知道字符串长度(但是要保证原来的空间足够容纳连接的字符串)或者不想关注这个信息的场合。如果你自己精确的知道或者已经维护了这个信息,那么你当然可以直接使用strcpy,是不是呢?这样表达可能有点绕,如有不妥,当我没说把。

# re: strcat在某种特定条件下的优化  回复  更多评论   

2010-08-06 10:09 by roy
@hoodlum1980

首先感谢你一直关心拙作,我们都是技术人员,关于技术问题没什么不能谈的,是吗?

其次,我并没有用string_append代替strcat的意思,事实上,通常情况下,我都只用strcat,只有在strcat对效率影响实在太大的时候,才考虑string_append。这个例子中直接用strcpy当然可以,但还是需要strlen计算附加串的长度。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理