c - strstr 比算法快？

Question

我有一个 21056 字节的文件。

我用 C 编写了一个程序，它将整个文件读入缓冲区，然后使用多种搜索算法在文件中搜索 82 个字符的标记。

我已经使用了 “Exact String Matching Algorithms” 中算法的所有实现页。我用过:KMP、BM、TBM 和 Horspool。然后我使用了 strstr 并对每一个进行了基准测试。

我想知道的是，每次 strstr 都优于所有其他算法。唯一有时更快的是 BM。

strstr 不应该是最慢的吗？

这是我的基准测试代码，其中包含对 BM 进行基准测试的示例:

double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}

before = get_time();
BM(token, strlen(token), buffer, len);
after = get_time();
printf("Time: %f\n\n", after - before);

有人可以向我解释为什么 strstr 优于其他搜索算法吗？如果需要，我会根据要求发布更多代码。

Answer 1

为什么你认为 strstr 应该比所有其他的都慢？你知道 strstr 使用什么算法吗？我认为 strstr 很可能使用 KMP 类型或更好的微调、特定于处理器的汇编编码算法。在这种情况下，对于如此小的基准测试，您没有机会在 C 中超越它。

(我认为这可能是因为程序员喜欢实现这些东西。)