自定义 memstr (strstr) 速度优化

Question

我正在编写一个例程以在嵌入式 (ARM Cortex M0 @16MHz) 应用程序的指定内存块中查找字符串，我想知道为什么我编写的两个不同版本以不同的速度运行。

char* memstr(char* mem, uint32_t n, char* str) {

    if( (str[0] == '\0') || (n == 0) )   return NULL;

    uint32_t i = 0;
    char* max_mem;

    max_mem = mem + n;

    while( mem < max_mem ) {
        if( *mem != str[i] ) {
            mem -= i;
            i = 0;
        } else {
            if(str[i+1] == '\0')   return mem - i;
            i++;
        }
        mem++;
    }

    return NULL;
}


char* memstr2(char* mem, uint32_t n, char* str) {

    if( (str[0] == '\0') || (n == 0) )   return NULL;

    uint32_t c = 0;
    uint32_t i = 0;

    while( c < n ) {
        if( mem[c] != str[i] ) {
            c -= i;
            i = 0;
        } else {
            i++;
            if(str[i] == '\0')   return &mem[c - i + 1];
        }
        c++;
    }

    return NULL;
}

在 20 到 200 字节的内存中查找 7 个字符的字符串时，memstr 始终比 memstr2 快 1us。例如在 110 字节中查找 7 个字符的字符串，memstr 需要 106us，memstr2 需要 107us。 1us 听起来可能没什么大不了的，但在每个滴答声都很重要的嵌入式应用程序中，这是一个缺点。

一个额外的问题:这也促使我编写自己的 strstr，它比标准 strstr 更快(例如，在 207 个字符串中找到一个 7 个字符的字符串需要 my_strstr 236us 和 strstr 274us)。这有什么问题，因为 strstr 必须非常优化？

char* my_strstr(char* str1, char* str2) {
    uint32_t i = 0;

    if( str2[0] == '\0' )   return NULL;

    while( *str1 != '\0' ) {
        if( *str1 != str2[i] ) {
            str1 -= i;
            i = 0;
        } else {
            i++;
            if(str2[i] == '\0')   return (str1 - i - 1);
        }
        str1++;
    }

    return NULL;
}

Answer 1

首先，如果您搜索以两个相同字符开头的字符串，这两个函数都不起作用:如果您搜索 xxabcde 并且该字符串包含 xxxabcde，那么当您注意到 xxabcde 的 a 与第三个 x 不匹配时，您已经跳过了两个 x，因此不会匹配该字符串。

您也不检查是否搜索空字符串，在这种情况下您的代码会产生未定义的行为。

你用内存来比较内存。但是仅仅将内存与单个字符进行比较，你就可以做大量的工作。如果您搜索“abcde”，首先您必须找到字母 a。所以我会先检查一个空字符串，然后读取第一个字符。然后首先循环检查该字符。

char first = str2 [0];
if (first == '\0') return mem;

for (; mem < maxmem; ++mem) if (*mem == first) {
    ... check whether there is a match
}

你应该检查你的数据。如果您希望搜索字符串早点出现与您希望它通常根本不存在，您将编写不同的代码。