能否执行此顺序搜索算法(取自
使用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影响不大，字在整个函数中保持不变，其余的太大而无法容纳任何寄存器。缓存的大小以及整个数组是否可以放入其中只是一个问题。

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

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

回答

如果我们正在阅读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)

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

回答

作为哨兵法，有众所周知的技术。
要使用哨兵方法，我们必须了解" array []"的长度。
我们可以通过使用sendinal进行比较来删除" 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;
}

回答

要优化该代码，最好的选择是重写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++;
}

回答

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

如果我们愿意花一些时间在预处理参考数组上，则应该在Google上搜索"世界上最快的拼字游戏程序"并实施该程序。剧透：这是针对角色查找而优化的DAG。

回答

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

另外，在指针和索引之间切换通常不会影响性能，也不会添加寄存器关键字(正如已经提到的那样)-编译器足够聪明，可以在适当的情况下应用这些转换，并且如果我们对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。使用固定长度的char数组并对齐，以便字符串以64字节对齐方式开始。然后，我相信如果将const char match [64]而不是const char * match传递给函数，或者将strncpy match传递给64,128,256，无论字节数组如何，我们都可以获得良好的memcmp函数。

再想一想，这些SSE2匹配功能可能是诸如Intel和AMD的加速器库之类的软件包的一部分。去看一下。