C中的s_strip(s,del)函数是否还有比这个更优化的版本？

char *s_strip(char *s,const char *del)
{
    char map[256] = { 0 };
    const unsigned char *up1 = (const unsigned char *)del;
    unsigned char *up2 = (unsigned char *)s;
    unsigned char *up3 = (unsigned char *)s;

    while (*up1 != '')
        map[*up1++] = 1;

    for ( ; *up2 != ''; up2++)
    {
        if (map[*up2] == 0)
            *up3++ = *up2;
    }
    *up3 = '';

    return (char *)up3;
}

这将使用简单的数组查找替换函数调用(strpbrk()或strchr()),代价是在函数入口处初始化数组.如果处理过的字符串相当长,这可以很容易地在极大缩短的搜索时间内收回成本.

此版本的代码返回一个指向字符串末尾的null的指针 – 这允许您在不调用strlen()的情况下计算返回时压缩字符串的长度.我发现这比将指针返回到字符串的开头更有用 – 我已经知道字符串的起始位置,但我不知道它的结束位置,但函数s_strip()确实知道这一点. (如果我们能够重新开始,我也会为strcpy()和strcat()设计相同的设计.)

对’unsigned char’的强制确保它在具有有符号和无符号字符的计算机上正常工作.我对施法者的诽谤并不是很满意,但是很难避免它们(好吧,通过复制`up2来避免将施法分配给up3).

您可能会想出一个处理签名字符的设计,其方式如下：

char realmap[256] = { 0 };
char *map = &realmap[128];

然后,您可以依赖范围内的带符号字符,使得[-128] .. map [127]仍然落在realmap数组中.

自首次发布以来,上述功能已经纠正了几次 – 现在它似乎与问题中提出的两种解决方案一致.我将这三个解决方案放入测试工具中来计时,主要是因为我很好奇地图代码将如何执行,过去曾经丢失了汇编代码内联函数.映射解决方案很快就显示出我的测试系统上最快(Mac Mini 2 GHZ Intel Core 2 Duo,MacOS X 10.6.7,GCC 4.1.2).

时间是以秒为单位的平均时间.每个算法给出10次运行.
大小是源字符串的大小;删除字符串是22个字符(小写字母各6个,大写字母和数字加上4个标点符号).数据是由ASCII中的字母,数字和标点符号构建的固定字符串,必要时经常重复以达到规定的大小,这排除了终止空值.请注意,时间包括每次复制源字符串 – “空”列表示复制所花费的时间.

size     map        strchr     strpbrk    null       micro1     micro2
   2     0.000542   0.002292   0.001009   0.000106   0.000639   0.000707
   8     0.000654   0.004125   0.017524   0.000106   0.001012   0.000966
  32     0.001667   0.015815   0.063314   0.000196   0.002549   0.002247
 128     0.006385   0.064513   0.313749   0.000171   0.008455   0.007188
 512     0.022231   0.257910   1.293040   0.000282   0.013284   0.011829
2048     0.089066   1.035052   5.297966   0.000819   0.043391   0.037597

即使使用非常短的源字符串,映射算法也比strchr()或strpbrk()算法快得多(比strchr()算法快5-10倍,并且速度是strpbrk()的5-50倍.算法),随着搜索字符串大小的增加而出现差异. (我没想到这个结果 – 因为地图代码中存在设置开销.)

‘micro1’和’micro2’算法对应于AShelly建议的修改.当字符串足够长(切换在128到512字节之间)时,微优化版本比简单映射更快.

测试代码

如果你想要timer.c,timer.h的源代码,请联系我(参见我的个人资料).我通常将它们构建到库中并与库链接,但这次将文件包含在程序中更简单.

#include <string.h>

extern char *s_strip1(char *s,const char *del);
extern char *s_strip2(char *s,const char *del);
extern char *s_strip3(char *s,const char *del);

char *s_strip3(char *s,const char *del)
{
    char map[256] = { 0 };
    const unsigned char *up1 = (const unsigned char *)del;
    unsigned char *up2 = (unsigned char *)s;
    unsigned char *up3 = (unsigned char *)s;

    while (*up1 != '')
        map[*up1++] = 1;

    for ( ; *up2 != ''; up2++)
    {
        if (map[*up2] == 0)
            *up3++ = *up2;
    }
    *up3 = '';

    return (char *)up3;
}

char *s_strip2(char *s,const char *del)
{
    char *cp1;
    char *cp2;

    for (cp1=s,*cp1) )
            *cp2++ = *cp1;

    *cp2 = 0;
    return s;
}

char *s_strip1(char *s,del) ) {
            *cp2 = *cp1;
            cp2++;
        }

    *cp2 = 0;
    return s;
}

#include <stdio.h>
#include "timer.h"
#include "timer.c"

enum { NUM_REPEATS = 10000 };
typedef char *(*Function)(char *str,const char *del);

static void fill_bytes(char *buffer,size_t buflen)
{
    static const char source[] =
        "abcdefghijklmnopqrstuvwxyz"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "0123456789[]{}|,./?><;:'"=+-_)(*&^%$#@!";
    char *end = buffer + buflen;

    while (buffer < end)
    {
        size_t numbytes = sizeof(source) - 1;
        if ((size_t)(end - buffer) < sizeof(source)-1)
            numbytes = end - buffer;
        memmove(buffer,source,numbytes);
        buffer += numbytes;
    }
}

static void test(Function f,const char *fn,const char *del,size_t numbytes)
{
    Clock clk;
    char refbuf[numbytes];
    char buffer[numbytes];
    char clkbuf[32];
    fill_bytes(refbuf,sizeof(refbuf));
    strcpy(buffer,refbuf);
    clk_init(&clk);
    clk_start(&clk);
    for (size_t i = 0; i < NUM_REPEATS; i++)
    {
        memmove(buffer,refbuf,sizeof(buffer));
        if (f)
            (*f)(buffer,del);
    }
    clk_stop(&clk);
    printf("%-17s (%4zd) = %10s (%.64s)n",fn,numbytes,clk_elapsed_us(&clk,clkbuf,sizeof(clkbuf)),buffer);
}

int main(void)
{
    for (int size = 2; size <= 2048; size = size * 4)
    {
        for (int i = 0; i < 10; i++)
        {
           test(s_strip1,"s_strip1:strpbrk:","AJQRSTajqrst234567=+[]",size);
           test(s_strip2,"s_strip2:strchr:",size);
           test(s_strip3,"s_strip3:map",size);
           test(0,"s_strip4:null",size);
        }
    }
    return 0;
}

微优化

extern char *s_strip4(char *s,const char *del);
extern char *s_strip5(char *s,const char *del);

char *s_strip5(char *s,const char *del)
{
    char map[256];
    const unsigned char *up1 = (const unsigned char *)del;
    unsigned char *up2 = (unsigned char *)s;
    unsigned char *up3 = (unsigned char *)s;

    memset(map,1,sizeof(map));

    while (*up1 != '')
        map[*up1++] = 0;

    for ( ; *up2 != ''; up2++)
    {
        *up3 = *up2;
        up3 += map[*up2];
    }
    *up3 = '';

    return (char *)up3;
}

char *s_strip4(char *s,const char *del)
{
    char map[256] = { 0 };
    const unsigned char *up1 = (const unsigned char *)del;
    unsigned char *up2 = (unsigned char *)s;
    unsigned char *up3 = (unsigned char *)s;

    while (*up1 != '')
        map[*up1++] = 1;

    for ( ; *up2 != ''; up2++)
    {
        *up3 = *up2;
        up3 += !map[*up2];
    }
    *up3 = '';

    return (char *)up3;
}