比的strstr算法快？ [英] strstr faster than algorithms?

问题描述

我有一个文件，该文件是21056字节。

I have a file that's 21056 bytes.

我用C编写一个程序，读取整个文件到缓冲区中，然后使用多个搜索算法来搜索文件中的令牌是82个字符。

I've written a program in C that reads the entire file into a buffer, and then uses multiple search algorithms to search the file for a token that's 82 chars.

我用的算法全部实现从精确字符串匹配算法页。我用：KMP，BM，TBM和Horspool。然后我用的strstr 键，基准的每一个。

I've used all the implementations of the algorithms from the "Exact String Matching Algorithms" page. I've used: KMP, BM, TBM, and Horspool. And then I used strstr and benchmarked each one.

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

What I'm wondering is, each time the strstr outperforms all the other algorithms. The only one that is faster sometimes is BM.

不应该的strstr 是最慢？

下面是我的标杆code标杆BM的例子：

Here's my benchmark code with an example of benchmarking 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 是优于其他搜索算法？如果需要，我会发布更多的code的请求。

Could someone explain to me why strstr is outperforming the other search algorithms? I'll post more code on request if needed.

推荐答案

为什么你认为的strstr 应该是比其他慢？你知道什么算法的strstr 使用？我认为这是很可能的strstr 采用了微调，特定处理器，总成 - codeD的 KMP算法型或更好。在这种情况下，你不站出来表现它 C 对于这样小的基准测试的机会。

Why do you think strstr should be slower than all the others? Do you know what algorithm strstr uses? I think it's quite likely that strstr uses a fine-tuned, processor-specific, assembly-coded algorithm of the KMP type or better. In which case you don't stand a chance of out-performing it in C for such small benchmarks.

（我认为这是有可能的原因是，程序员喜欢来实现这样的事情。）

(The reason I think this is likely is that programmers love to implement such things.)

这篇关于比的strstr算法快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！