9

可以使用 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;
}
4

10 回答 10

24

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

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

于 2008-08-19T07:33:20.943 回答
2

我认为，这不会有太大的不同。编译器已经朝那个方向优化了它。

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

字符串比较在计算上相当昂贵。

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

于 2008-08-19T07:36:47.863 回答
2

有众所周知的技术作为哨兵方法。要使用哨兵方法，您必须知道“array[]”的长度。您可以使用前哨删除“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;
}
于 2008-08-19T09:19:33.443 回答
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)

祝你好运，这是一本好书！

于 2008-08-19T08:05:16.730 回答
0

要优化该代码，最好的办法是重写 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++;
}
于 2008-08-19T12:46:12.777 回答
0

实际上，将 I 设置为寄存器变量不会做任何编译器不会做的事情。

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

于 2008-08-19T23:33:40.700 回答
0

Mark Harrison：你的 for 循环永远不会终止！（++p 是缩进的，但实际上不在 for 中：-）

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

于 2008-09-16T12:26:39.337 回答
0

匹配字符串的更快方法是将它们存储为 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 和下一个字符串的开始添加内存预取提示。但这太疯狂了。:-)

于 2008-10-31T04:50:58.737 回答
0

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

多想一下，这些 SSE2 匹配函数可能是英特尔和 AMD 加速器库等软件包的一部分。去看一下。

于 2008-10-31T05:09:57.497 回答
-1 
/* 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;
}
于 2013-11-21T09:13:50.693 回答