问题描述

为什么Boost库的搜索函数明显比std的search慢?

在学习boost的时候测试了一下boost的algorithm中的三个search函数，分别是Boyer-Moore Search，Boyer-Moore-Horspool Search，Knuth-Morris-Pratt Search，同时也测试了std的search函数，测试的结果有点意外，std的search花的时间比前面三个快了两个数量级，问题出在哪儿？测试的代码如下：

#define _CRT_SECURE_NO_WARNINGS

#include <boost/algorithm/searching/boyer_moore.hpp>
#include <boost/algorithm/searching/boyer_moore_horspool.hpp>
#include <boostalgorithmsearchingknuth_morris_pratt.hpp>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <Windows.h>
#include <time.h>
using namespace std;
using namespace boost::algorithm;

void printMessage(char* msg, int startX, int startY)
{
        HANDLE hd;
        COORD pos;
        pos.X = startX;
        pos.Y = startY;
        hd = GetStdHandle(STD_OUTPUT_HANDLE);
        SetConsoleCursorPosition(hd, pos);
        printf("%s", msg);
}

int main(int argc, char ** argv)
{
        printf("Generating test setn");
        vector<int> vec;
        srand(unsigned int(time(NULL)));
        for (int i = 0; i < 10000; i++)
        {
                vec.push_back(rand() % 15000);
                char msg[50];
                sprintf(msg,"%.2f%%n", i*1.0/99.99);

                printMessage(msg, 0, 1);
        }

        LARGE_INTEGER t1, t2, tc;
        QueryPerformanceFrequency(&tc);
        QueryPerformanceCounter(&t1);

        printf("Testing boyer moore searchn");

        int count = 0;
        for (int i = 0; i < 1000; i++)
        {
                vector<int> key;
                key.push_back(rand() % 15000);
                if (boyer_moore_search(vec.begin(), vec.end(), key.begin(), key.end()) != vec.end())
                {
                        count++;
                }
                char msg[50];
                sprintf(msg,"%.2f%%n", i / 9.99);
                printMessage(msg, 0, 3);
        }
        cout << "Hit " << count << "timesn";
        QueryPerformanceCounter(&t2);
        printf("Costing time: %.2f sn", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart);
        system("pause");

        QueryPerformanceCounter(&t1);
        printf("Testing boyer_moore_horspool searchn");
        count = 0;
        for (int i = 0; i < 1000; i++)
        {
                vector<int> key;
                key.push_back(rand() % 15000);
                if (boyer_moore_horspool_search(vec.begin(), vec.end(), key.begin(), key.end()) != vec.end())
                {
                        count++;
                }
                char msg[50];
                sprintf(msg, "%.2f%%n", i / 9.99);
                printMessage(msg, 0, 8);
        }
        cout << "Hit " << count << "timesn";
        QueryPerformanceCounter(&t2);
        printf("Costing time: %.2f sn", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart);
        system("pause");

        QueryPerformanceCounter(&t1);
        printf("Testing knuth_morris_pratt searchn");
        count = 0;
        for (int i = 0; i < 1000; i++)
        {
                vector<int> key;
                key.push_back(rand() % 15000);
                if (knuth_morris_pratt_search(vec.begin(), vec.end(), key.begin(), key.end()) != vec.end())
                {
                        count++;
                }
                char msg[50];
                sprintf(msg, "%.2f%%n", i/ 9.99);
                printMessage(msg, 0, 13);
        }
        cout << "Hit " << count << "timesn";
        QueryPerformanceCounter(&t2);
        printf("Costing time: %.2f sn", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart);
        system("pause");

        QueryPerformanceCounter(&t1);
        printf("Tesing std searchn");
        count = 0;
        for (int i = 0; i < 1000; i++)
        {
                vector<int> key;
                key.push_back(rand() % 15000);
                if (search(vec.begin(), vec.end(), key.begin(), key.end()) != vec.end())
                {
                        count++;
                }
                char msg[50];
                sprintf(msg, "%.2f%%n", i/ 9.99);
                printMessage(msg, 0, 18);
        }
        cout << "Hit " << count << "timesn";
        QueryPerformanceCounter(&t2);
        printf("Costing time: %.2f sn", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart);
        system("pause");

        return 0;
}

测试环境是vs2013，测试结果如下图：

![测试截图](http://img.ask.csdn.net/upload/201506/30/1435626813_549413.png)

是什么导致了这么大的差距？

解决方案

我这不善于表达，说起来太罗嗦。其实就是算法的问题。std中的search是线性的。这样吧。给你贴几个对比的网址你可以看一下，他们的表述都非常好。
关于Boyer-Moore算法的：http://blog.csdn.net/ijuliet/article/details/4200771
关于Knuth Morris Pratt (KMP)算法的：http://blog.csdn.net/todleigh/article/details/2955906
关于std::search与KMP算法的对比：http://www.docin.com/p-198453416.html
希望可以帮到你，我也是初学者，不过对于算法比较感兴趣一些。

解决方案二：

是否编译器都开了优化。这样才好比较