优化 C 语言的搜索算法

StackOverflow https://stackoverflow.com/questions/15838

题

这种顺序搜索算法的性能（取自编程实践）可以使用任何 C 的本机实用程序进行改进，例如如果我将 i 变量设置为寄存器变量？

int lookup(char *word, char*array[])
{
    int i

    for (i = 0; array[i] != NULL; i++)
        if (strcmp(word, array[i]) == 0)
            return i;

    return -1;
}
有帮助吗？

解决方案

是的，但只是非常轻微。通过使用更好的算法（例如保持列表排序并进行二分搜索）可以实现更大的性能改进。

一般来说，优化给定的算法只能让你到目前为止。选择更好的算法（即使它没有完全优化）可以给您带来相当大的（数量级）性能改进。

其他提示

我认为，这不会有太大区别。编译器已经在这个方向上对其进行了优化。

此外，变量 i 没有太大影响，word 在整个函数中保持不变，其余部分太大，无法放入任何寄存器。问题仅在于缓存有多大以及整个阵列是否适合其中。

字符串比较的计算量相当大。

您可以在搜索之前对数组使用某种哈希吗？

有一种众所周知的技术作为哨兵方法。要使用sentinal方法，您必须知道“array[]”的长度。您可以通过使用 Sentinal 来删除“array[i] != NULL”比较。

int lookup(char *word, char*array[], int array_len)
{
    int i = 0;
    array[array_len] = word;
    for (;; ++i)
        if (strcmp(word, array[i]) == 0) 
            break;
    array[array_len] = NULL;
    return (i != array_len) ? i : -1;
}

如果您正在阅读 TPOP，接下来您将看到他们如何使用不同的数据结构和算法使搜索速度提高许多倍。

但是你可以通过替换诸如

for (i = 0; i < n; ++i)
    foo(a[i]);

和

char **p = a;
for (i = 0; i < n; ++i)
    foo(*p);
    ++p;

如果数组末尾有一个已知值（例如NULL）你可以消除循环计数器：

for (p = a; *p != NULL; ++p)
    foo(*p)

祝你好运，这是一本很棒的书！

要优化该代码，最好的选择是重写 strcmp 例程，因为您只检查相等性，不需要评估整个单词。

除此之外你不能做太多其他事情。您无法排序，因为您似乎是在较大文本中查找文本。二分搜索也不起作用，因为文本不太可能被排序。

我的 2p（C 伪代码）：

wrd_end = wrd_ptr + wrd_len;
arr_end = arr_ptr - wrd_len;
while (arr_ptr < arr_end)
{
    wrd_beg = wrd_ptr; arr_beg = arr_ptr;
    while (wrd_ptr == arr_ptr)
    {
        wrd_ptr++; arr_ptr++;
        if (wrd_ptr == wrd_en)
            return wrd_beg;
    }
    wrd_ptr++;
}

马克·哈里森：你的 for 循环永远不会终止！（++p 是缩进的，但实际上不在 for 内:-)

此外，指针和索引之间的切换通常不会对性能产生影响，添加寄存器关键字也不会影响性能（正如 mat 已经提到的）——编译器足够聪明，可以在适当的情况下应用这些转换，如果你告诉它足够多的关于你的 cpu 架构的信息，它会比手动伪微优化做得更好。

匹配字符串的更快方法是将它们存储为 Pascal 风格。如果每个字符串不需要超过 255 个字符，请大致像这样存储它们，并将计数放在第一个字节中：

char s[] = "\x05Hello";

然后你可以这样做：

for(i=0; i<len; ++i) {
    s_len = strings[i][0];
    if(
        s_len == match_len
        && strings[i][s_len] == match[s_len-1]
        && 0 == memcmp(strings[i]+1, match, s_len-1)
    ) {
        return 1;
    }
}

为了变得非常快，请为字符串开始 + 64、+ 128 以及下一个字符串的开始添加内存预取提示。但这太疯狂了。:-)

另一种快速方法是让编译器使用 SSE2 优化的 memcmp。使用固定长度的字符数组并对齐，以便字符串以 64 字节对齐方式开始。然后我相信，如果您将 const char match[64] 而不是 const char *match 传递到函数中，或者将 strncpy 匹配到 64,128,256 等字节数组中，您可以获得良好的 memcmp 函数。

进一步思考一下，这些 SSE2 匹配函数可能是 Intel 和 AMD 加速器库等软件包的一部分。去看一下。

实际上，将 I 设置为寄存器变量不会执行编译器尚未执行的任何操作。

如果您愿意花一些时间预先预处理参考数组，您应该搜索“世界上最快的拼字游戏程序”并实现它。剧透：它是针对字符查找优化的 DAG。

/* there is no more quick  */
int lookup(char *word, char*array[])
{
    int i;
    for(i=0; *(array++) != NULL;i++)
        if (strcmp(word, *array) == 0)
            return i;
    return -1;
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top