在C++中寻找搜索和替换的圣杯

Question

最近，我正在寻找一种方法来替换字符串中的令牌，这种方法本质上是查找和替换(但至少有一种额外的方法来解决这个问题)，而且看起来非常乏味。我附带了几个可能的实现，但从性能的角度来看，没有一个是令人满意的。最佳成绩为每次迭代50 was。情况很理想，字符串的大小从未增加，最初我省略了不区分大小写的要求

这是柯尔鲁的代码

我的机器的结果：

Boost.Spirit符号结果: 3421?=3421

100000次周期为6060。

波耶-摩尔results:3421?=3421

100000次周期为5959。

博耶·摩尔·霍斯普尔result:3421?=3421

100000次周期花费了5008ms。

Knuth结果: 3421?=3421

100000次周期为12451。

朴素的STL搜索和替换结果: 3421?=3421

100000个周期为5532。

Boost replace_all result:3421?=3421

100000次周期为4860。

那么问题是，为什么这么简单的任务要花这么长时间呢？我们可以说，好的，简单的任务，继续，更好地实现它。但实际情况是，15年前的MFC朴素实现使任务的量级更快：

CString FillTokenParams(const CString& input, const std::unordered_map<std::string, std::string>& tokens)
{
    CString tmpInput = input;
    for(const auto& token : tokens)
    {
        int pos = 0;
        while(pos != -1)
        {
            pos = tmpInput.Find(token.first.c_str(), pos);
            if(pos != -1)
            {
                int tokenLength = token.first.size();
                tmpInput.Delete(pos, tokenLength);
                tmpInput.Insert(pos, token.second.c_str());
                pos += 1;
            }
        }
    }

    return tmpInput;
}

结果：

MFC朴素搜索和替换result:3421?=3421

100000次周期为516。

为什么这种笨拙的代码性能优于现代C++？为什么其他实现如此缓慢？我是不是错过了一些最基本的东西？

EDIT001:我在这个问题上进行了投资，代码被描述为并进行了三次检查。您可能对这个和那个不满意，但是std：：string：：替换并不需要时间。在任何STL的实现搜索中，大部分时间都会占用时间，提升精神会浪费时间来分配tst (我猜是评估树中的测试节点)。我不希望有人在函数中指出“这是你的问题”，这个问题已经解决了。问题是MFC如何以10倍的速度完成同样的工作。

EDIT002:刚刚钻研MFC实现的查找并编写了一个模拟MFC实现的函数。

namespace mfc
{
std::string::size_type Find(const std::string& input, const std::string& subString, std::string::size_type start)
{
    if(subString.empty())
    {
        return std::string::npos;
    }

    if(start < 0 || start > input.size())
    {
        return std::string::npos;
    }

    auto found = strstr(input.c_str() + start, subString.c_str());
    return ((found == nullptr) ? std::string::npos : std::string::size_type(found - input.c_str()));
}
}

std::string MFCMimicking(const std::string& input, const std::unordered_map<std::string, std::string>& tokens)
{
    auto tmpInput = input;
    for(const auto& token : tokens)
    {
        auto pos = 0;
        while(pos != std::string::npos)
        {
            pos = mfc::Find(tmpInput, token.first, pos);
            if(pos != std::string::npos)
            {
                auto tokenLength = token.first.size();
                tmpInput.replace(pos, tokenLength, token.second.c_str());
                pos += 1;
            }
        }
    }

    return tmpInput;
}

结果：

MFC模拟扩展result:3421?=3421

100000个周期花费411。

意思是4 4us。每打一次电话，去打败那个C strstr

EDIT003:用-Ox编译和运行

MFC模拟扩展result:3421?=3421100000周期花费660 MFC。 MFC朴素搜索和替换result:3421?=3421 100000次周期采用856ms.Manual展开result:3421?=3421 100000个周期为1995年。 波耶-摩尔results:3421?=3421 100000次周期为6911。 博耶·摩尔·霍斯普尔result:3421?=3421 100000次周期为5670。 Knuth结果: 3421?=3421 100000次周期为13825。 朴素的STL搜索和替换结果: 3421?=3421 100000次周期为9531。 Boost replace_all result:3421?=3421 100000次周期为8996。

使用-O2运行(如在原始测量中)，但10k周期

MFC模拟扩展result:3421?=3421 10000次周期花费104。 MFC朴素搜索和替换result:3421?=3421 10000次周期花费105。 手动扩展result:3421?=3421 10000次周期为356。 波耶-摩尔results:3421?=3421 10000个周期花费了1355。 博耶·摩尔·霍斯普尔result:3421?=3421 10000个周期花费了1101。 Knuth结果: 3421?=342110000周期为1973 Morris。 朴素的STL搜索和替换结果: 3421?=3421 10000次周期为923。 Boost replace_all result:3421?=3421 10000次周期为880。

Answer 1

所以，我有一些关于齐版本的观察。

还创建了一个X3版本。

最后，编写了一个手动扩展函数，它击败了所有其他候选程序(我希望它比MFC更快，因为它不需要重复删除/插入)。

如果愿意，跳到基准图表。

关于气版

1. 是的，符号表存在基于节点的容器的局部性问题。它们可能不是你能用的最好的匹配物。
2. 没有必要重新构建每个循环的符号：
3. 而不是按字符跳过非符号，扫描直到下一个： +(bsq::char_ -符号)

inline std::string spirit_qi(const std::string& input, bsq::symbols<char, std::string> const& symbols)
{
    std::string retVal;
    retVal.reserve(input.size() * 2);

    auto beg = input.cbegin();
    auto end = input.cend();

    if(!bsq::parse(beg, end, *(symbols | +(bsq::char_ - symbols)), retVal))
        retVal = input;

    return retVal;
}

这已经快得多了。但是：

手动圈

在这个简单的例子中，为什么不直接手动进行解析呢？

inline std::string manual_expand(const std::string& input, TokenMap const& tokens)
{
    std::ostringstream builder;
    auto expand = [&](auto const& key) {
        auto match = tokens.find(key);
        if (match == tokens.end())
            builder << "$(" << key << ")";
        else
            builder << match->second;
    };

    builder.str().reserve(input.size()*2);

    builder.str("");
    std::ostreambuf_iterator<char> out(builder);

    for(auto f(input.begin()), l(input.end()); f != l;) {
        switch(*f) {
            case '$' : {
                    if (++f==l || *f!='(') {
                        *out++ = '$';
                        break;
                    }
                    else {
                        auto s = ++f;
                        size_t n = 0;

                        while (f!=l && *f != ')')
                            ++f, ++n;

                        // key is [s,f] now
                        expand(std::string(&*s, &*s+n));

                        if (f!=l)
                            ++f; // skip '}'
                    }
                }
            default:
                *out++ = *f++;
        }
    }
    return builder.str();
}

这在我的机器上的性能要好得多。

其他想法

您可以使用静态生成的令牌表：model.html来查看Boost generated。不过我不太喜欢莱克斯。

比较：

​

​

见http://stackoverflow-sehe.s3.amazonaws.com/474bf790-9b9f-44a1-969d-e64d24fc30c9/stats.html

这是使用诺尼乌斯进行基准测试统计。

完整基准代码：http://paste.ubuntu.com/14133072/

#include <boost/container/flat_map.hpp>

#define USE_X3
#ifdef USE_X3
#   include <boost/spirit/home/x3.hpp>
#else
#   include <boost/spirit/include/qi.hpp>
#endif

#include <boost/algorithm/string.hpp>
#include <boost/algorithm/searching/boyer_moore.hpp>
#include <boost/algorithm/searching/boyer_moore_horspool.hpp>
#include <boost/algorithm/searching/knuth_morris_pratt.hpp>
#include <string>
#include <unordered_map>
#include <iostream>
#include <fstream>
#include <nonius/benchmark.h++>
#include <nonius/main.h++>

using TokenMap = boost::container::flat_map<std::string, std::string>;

#ifdef USE_X3
    namespace x3  = boost::spirit::x3;

    struct append {
        std::string& out;
        void do_append(char const ch) const                       { out += ch;                      } 
        void do_append(std::string const& s)  const               { out += s;                       } 
        template<typename It>
        void do_append(boost::iterator_range<It> const& r)  const { out.append(r.begin(), r.end()); } 
        template<typename Ctx>
        void operator()(Ctx& ctx) const                           { do_append(_attr(ctx));          } 
    };

    inline std::string spirit_x3(const std::string& input, x3::symbols<char const*> const& symbols)
    {
        std::string retVal;
        retVal.reserve(input.size() * 2);
        append appender { retVal };

        auto beg = input.cbegin();
        auto end = input.cend();

        auto rule = *(symbols[appender] | x3::char_ [appender]);

        if(!x3::parse(beg, end, rule))
            retVal = input;

        return retVal;
    }
#else
    namespace bsq = boost::spirit::qi;

    inline std::string spirit_qi_old(const std::string& input, TokenMap const& tokens)
    {
        std::string retVal;
        retVal.reserve(input.size() * 2);
        bsq::symbols<char const, char const*> symbols;
        for(const auto& token : tokens) {
            symbols.add(token.first.c_str(), token.second.c_str());
        }

        auto beg = input.cbegin();
        auto end = input.cend();

        if(!bsq::parse(beg, end, *(symbols | bsq::char_), retVal))
            retVal = input;

        return retVal;
    }

    inline std::string spirit_qi(const std::string& input, bsq::symbols<char, std::string> const& symbols)
    {
        std::string retVal;
        retVal.reserve(input.size() * 2);

        auto beg = input.cbegin();
        auto end = input.cend();

        if(!bsq::parse(beg, end, *(symbols | +(bsq::char_ - symbols)), retVal))
            retVal = input;

        return retVal;
    }
#endif

inline std::string manual_expand(const std::string& input, TokenMap const& tokens) {
    std::ostringstream builder;
    auto expand = [&](auto const& key) {
        auto match = tokens.find(key);

        if (match == tokens.end())
            builder << "$(" << key << ")";
        else
            builder << match->second;
    };

    builder.str().reserve(input.size()*2);
    std::ostreambuf_iterator<char> out(builder);

    for(auto f(input.begin()), l(input.end()); f != l;) {
        switch(*f) {
            case '$' : {
                    if (++f==l || *f!='(') {
                        *out++ = '$';
                        break;
                    }
                    else {
                        auto s = ++f;
                        size_t n = 0;

                        while (f!=l && *f != ')')
                            ++f, ++n;

                        // key is [s,f] now
                        expand(std::string(&*s, &*s+n));

                        if (f!=l)
                            ++f; // skip '}'
                    }
                }
            default:
                *out++ = *f++;
        }
    }
    return builder.str();
}

inline std::string boost_replace_all(const std::string& input, TokenMap const& tokens)
{
    std::string retVal(input);
    retVal.reserve(input.size() * 2);

    for(const auto& token : tokens)
    {
        boost::replace_all(retVal, token.first, token.second);
    }
    return retVal;
}

inline void naive_stl(std::string& input, TokenMap const& tokens)
{
    input.reserve(input.size() * 2);
    for(const auto& token : tokens)
    {
        auto next = std::search(input.cbegin(), input.cend(), token.first.begin(), token.first.end());
        while(next != input.cend())
        {
            input.replace(next, next + token.first.size(), token.second);
            next = std::search(input.cbegin(), input.cend(), token.first.begin(), token.first.end());
        }
    }
}

inline void boyer_more(std::string& input, TokenMap const& tokens)
{
    input.reserve(input.size() * 2);
    for(const auto& token : tokens)
    {
        auto next =
            boost::algorithm::boyer_moore_search(input.cbegin(), input.cend(), token.first.begin(), token.first.end());
        while(next != input.cend())
        {
            input.replace(next, next + token.first.size(), token.second);
            next = boost::algorithm::boyer_moore_search(input.cbegin(), input.cend(), token.first.begin(),
                                                        token.first.end());
        }
    }
}

inline void bmh_search(std::string& input, TokenMap const& tokens)
{
    input.reserve(input.size() * 2);
    for(const auto& token : tokens)
    {
        auto next = boost::algorithm::boyer_moore_horspool_search(input.cbegin(), input.cend(), token.first.begin(),
                                                                  token.first.end());
        while(next != input.cend())
        {
            input.replace(next, next + token.first.size(), token.second);
            next = boost::algorithm::boyer_moore_search(input.cbegin(), input.cend(), token.first.begin(),
                                                        token.first.end());
        }
    }
}

inline void kmp_search(std::string& input, TokenMap const& tokens)
{
    input.reserve(input.size() * 2);
    for(const auto& token : tokens)
    {
        auto next = boost::algorithm::knuth_morris_pratt_search(input.cbegin(), input.cend(), token.first.begin(),
                                                                token.first.end());
        while(next != input.cend())
        {
            input.replace(next, next + token.first.size(), token.second);
            next = boost::algorithm::boyer_moore_search(input.cbegin(), input.cend(), token.first.begin(),
                                                        token.first.end());
        }
    }
}

namespace testdata {
    std::string const expected =
        "Five and Seven said nothing, but looked at Two. Two began in a low voice, 'Why the fact is, you see, Miss, "
        "this here ought to have been a red rose-tree, and we put a white one in by mistake; and if the Queen was to "
        "find it out, we should all have our heads cut off, you know. So you see, Miss, we're doing our best, afore "
        "she comes, to—' At this moment Five, who had been anxiously looking across the garden, called out 'The Queen! "
        "The Queen!' and the three gardeners instantly threw themselves flat upon their faces. There was a sound of "
        "many footsteps, and Alice looked round, eager to see the Queen.First came ten soldiers carrying clubs; these "
        "were all shaped like the three gardeners, oblong and flat, with their hands and feet at the corners: next the "
        "ten courtiers; these were ornamented all over with diamonds, and walked two and two, as the soldiers did. "
        "After these came the royal children; there were ten of them, and the little dears came jumping merrily along "
        "hand in hand, in couples: they were all ornamented with hearts. Next came the guests, mostly Kings and "
        "Queens, and among them Alice recognised the White Rabbit: it was talking in a hurried nervous manner, smiling "
        "at everything that was said, and went by without noticing her. Then followed the Knave of Hearts, carrying "
        "the King's crown on a crimson velvet cushion; and, last of all this grand procession, came THE KING AND QUEEN "
        "OF HEARTS.Alice was rather doubtful whether she ought not to lie down on her face like the three gardeners, "
        "but she could not remember ever having heard of such a rule at processions; 'and besides, what would be the "
        "use of a procession,' thought she, 'if people had all to lie down upon their faces, so that they couldn't see "
        "it?' So she stood still where she was, and waited.When the procession came opposite to Alice, they all "
        "stopped and looked at her, and the Queen said severely 'Who is this?' She said it to the Knave of Hearts, who "
        "only bowed and smiled in reply.'Idiot!' said the Queen, tossing her head impatiently; and, turning to Alice, "
        "she went on, 'What's your name, child?''My name is Alice, so please your Majesty,' said Alice very politely; "
        "but she added, to herself, 'Why, they're only a pack of cards, after all. I needn't be afraid of them!''And "
        "who are these?' said the Queen, pointing to the three gardeners who were lying round the rosetree; for, you "
        "see, as they were lying on their faces, and the pattern on their backs was the same as the rest of the pack, "
        "she could not tell whether they were gardeners, or soldiers, or courtiers, or three of her own children.'How "
        "should I know?' said Alice, surprised at her own courage. 'It's no business of mine.'The Queen turned crimson "
        "with fury, and, after glaring at her for a moment like a wild beast, screamed 'Off with her head! "
        "Off—''Nonsense!' said Alice, very loudly and decidedly, and the Queen was silent.The King laid his hand upon "
        "her arm, and timidly said 'Consider, my dear: she is only a child!'The Queen turned angrily away from him, "
        "and said to the Knave 'Turn them over!'The Knave did so, very carefully, with one foot.'Get up!' said the "
        "Queen, in a shrill, loud voice, and the three gardeners instantly jumped up, and began bowing to the King, "
        "the Queen, the royal children, and everybody else.'Leave off that!' screamed the Queen. 'You make me giddy.' "
        "And then, turning to the rose-tree, she went on, 'What have you been doing here?'";
    std::string const inputWithtokens =
        "Five and Seven said nothing, but looked at $(Two). $(Two) began in a low voice, 'Why the fact is, you see, "
        "Miss, "
        "this here ought to have been a red rose-tree, and we put a white one in by mistake; and if the Queen was to "
        "find it out, we should all have our $(heads) cut off, you know. So you see, Miss, we're doing our best, afore "
        "she comes, to—' At this moment Five, who had been anxiously looking across the garden, called out 'The Queen! "
        "The Queen!' and the three gardeners instantly threw themselves flat upon their faces. There was a sound of "
        "many footsteps, and Alice looked round, eager to see the $(Queen).First came ten soldiers carrying clubs; "
        "these "
        "were all shaped like the three gardeners, oblong and flat, with their hands and feet at the corners: next the "
        "ten courtiers; these were ornamented all over with $(diamonds), and walked two and two, as the soldiers did. "
        "After these came the royal children; there were ten of them, and the little dears came jumping merrily along "
        "hand in hand, in couples: they were all ornamented with hearts. Next came the guests, mostly Kings and "
        "Queens, and among them Alice recognised the White Rabbit: it was talking in a hurried nervous manner, smiling "
        "at everything that was said, and went by without noticing her. Then followed the Knave of Hearts, carrying "
        "the King's crown on a crimson velvet cushion; and, last of all this grand procession, came THE KING AND QUEEN "
        "OF HEARTS.Alice was rather doubtful whether she ought not to lie down on her face like the three gardeners, "
        "but she could not remember ever having heard of such a rule at processions; 'and besides, what would be the "
        "use of a procession,' thought she, 'if people had all to lie down upon their faces, so that they couldn't see "
        "it?' So she stood still where she was, and waited.When the procession came opposite to Alice, they all "
        "stopped and looked at her, and the $(Queen) said severely 'Who is this?' She said it to the Knave of Hearts, "
        "who "
        "only bowed and smiled in reply.'Idiot!' said the Queen, tossing her head impatiently; and, turning to Alice, "
        "she went on, 'What's your name, child?''My name is Alice, so please your Majesty,' said Alice very politely; "
        "but she added, to herself, 'Why, they're only a pack of cards, after all. I needn't be afraid of them!''And "
        "who are these?' said the $(Queen), pointing to the three gardeners who were lying round the rosetree; for, "
        "you "
        "see, as they were lying on their faces, and the $(pattern) on their backs was the same as the rest of the "
        "pack, "
        "she could not tell whether they were gardeners, or soldiers, or courtiers, or three of her own children.'How "
        "should I know?' said Alice, surprised at her own courage. 'It's no business of mine.'The Queen turned crimson "
        "with fury, and, after glaring at her for a moment like a wild beast, screamed 'Off with her head! "
        "Off—''Nonsense!' said $(Alice), very loudly and decidedly, and the Queen was silent.The $(King) laid his hand "
        "upon "
        "her arm, and timidly said 'Consider, my dear: she is only a child!'The $(Queen) turned angrily away from him, "
        "and said to the $(Knave) 'Turn them over!'The $(Knave) did so, very carefully, with one foot.'Get up!' said "
        "the "
        "Queen, in a shrill, loud voice, and the three gardeners instantly jumped up, and began bowing to the King, "
        "the Queen, the royal children, and everybody else.'Leave off that!' screamed the Queen. 'You make me giddy.' "
        "And then, turning to the rose-tree, she went on, 'What have you been doing here?'";

    static TokenMap const raw_tokens {
        {"Two", "Two"},           {"heads", "heads"},
        {"diamonds", "diamonds"}, {"Queen", "Queen"},
        {"pattern", "pattern"},   {"Alice", "Alice"},
        {"King", "King"},         {"Knave", "Knave"},
        {"Why", "Why"},           {"glaring", "glaring"},
        {"name", "name"},         {"know", "know"},
        {"Idiot", "Idiot"},       {"children", "children"},
        {"Nonsense", "Nonsense"}, {"procession", "procession"},
    };

    static TokenMap const tokens {
        {"$(Two)", "Two"},           {"$(heads)", "heads"},
        {"$(diamonds)", "diamonds"}, {"$(Queen)", "Queen"},
        {"$(pattern)", "pattern"},   {"$(Alice)", "Alice"},
        {"$(King)", "King"},         {"$(Knave)", "Knave"},
        {"$(Why)", "Why"},           {"$(glaring)", "glaring"},
        {"$(name)", "name"},         {"$(know)", "know"},
        {"$(Idiot)", "Idiot"},       {"$(children)", "children"},
        {"$(Nonsense)", "Nonsense"}, {"$(procession)", "procession"},
    };

}

NONIUS_BENCHMARK("manual_expand", [](nonius::chronometer cm)     {
    std::string const tmp = testdata::inputWithtokens;
    auto& tokens = testdata::raw_tokens;

    std::string result;
    cm.measure([&](int) {
        result = manual_expand(tmp, tokens);
    });
    assert(result == testdata::expected);
})

#ifdef USE_X3
NONIUS_BENCHMARK("spirit_x3", [](nonius::chronometer cm) {
    auto const symbols = [&] {
        x3::symbols<char const*> symbols;
        for(const auto& token : testdata::tokens) {
            symbols.add(token.first.c_str(), token.second.c_str());
        }
        return symbols;
    }();

    std::string result;
    cm.measure([&](int) {
            result = spirit_x3(testdata::inputWithtokens, symbols);
        });
    //std::cout << "====\n" << result << "\n====\n";
    assert(testdata::expected == result);
})
#else
NONIUS_BENCHMARK("spirit_qi", [](nonius::chronometer cm) {
    auto const symbols = [&] {
        bsq::symbols<char, std::string> symbols;
        for(const auto& token : testdata::tokens) {
            symbols.add(token.first.c_str(), token.second.c_str());
        }
        return symbols;
    }();

    std::string result;
    cm.measure([&](int) {
            result = spirit_qi(testdata::inputWithtokens, symbols);
        });
    assert(testdata::expected == result);
})

NONIUS_BENCHMARK("spirit_qi_old", [](nonius::chronometer cm) {
    std::string result;
    cm.measure([&](int) {
            result = spirit_qi_old(testdata::inputWithtokens, testdata::tokens);
        });
    assert(testdata::expected == result);
})
#endif

NONIUS_BENCHMARK("boyer_more", [](nonius::chronometer cm) {
    cm.measure([&](int) {
        std::string tmp = testdata::inputWithtokens;
        boyer_more(tmp, testdata::tokens);
        assert(tmp == testdata::expected);
    });
})

NONIUS_BENCHMARK("bmh_search", [](nonius::chronometer cm) {
    cm.measure([&](int) {
        std::string tmp = testdata::inputWithtokens;
        bmh_search(tmp, testdata::tokens);
        assert(tmp == testdata::expected);
    });
})

NONIUS_BENCHMARK("kmp_search", [](nonius::chronometer cm) {
    cm.measure([&](int) {
        std::string tmp = testdata::inputWithtokens;
        kmp_search(tmp, testdata::tokens);
        assert(tmp == testdata::expected);
    });
})

NONIUS_BENCHMARK("naive_stl", [](nonius::chronometer cm) {
    cm.measure([&](int) {
            std::string tmp = testdata::inputWithtokens;
            naive_stl(tmp, testdata::tokens);
            assert(tmp == testdata::expected);
        });
})

NONIUS_BENCHMARK("boost_replace_all", [](nonius::chronometer cm)     {
    std::string const tmp = testdata::inputWithtokens;

    std::string result;
    cm.measure([&](int) {
        result = boost_replace_all(testdata::inputWithtokens, testdata::tokens);
    });
    assert(result == testdata::expected);
})

Answer 2

EDIT2 for MFCMimicking:从代码中可以看出，MFC版本速度更快的原因很明显:它不会像其他版本那样搜索整个字符串，每个替换版本都会这样做(我仍然无法解释boost：：still )。一旦进行替换，它就会从替换点开始搜索，而不是从字符串的开头开始搜索，因此很明显，搜索速度会更快。

编辑:在做了更多的研究和观察(查找多个字符串匹配的算法)之后，似乎使用好的单字符串匹配算法来查找多个搜索词是这里的实际问题。也许你最好的选择是使用一个适当的算法(这个问题中提到了几个算法)。

为什么MFC更快？我建议将其归结为一个不同的问题：“为什么在CString中删除和插入要比std：：string快得多”，或者诸如此类的问题，并确保您将其标记为C++和MFC，这样具有正确专业知识的人就可以提供帮助(我有使用标准C++的经验，但无法帮助VC++在CString中进行哪些优化)。

原来的答案:好的，由于大量的代码，我只看了expandTokens3，但我假设所有版本都有相同的问题。您的代码有两个潜在的重要性能问题：

• 每次执行替换操作时，都会搜索整个字符串。如果字符串中有10个变量要替换，那么它所需的时间将是所需时间的10倍。
• 您可以在输入字符串中执行每个替换字符串，而不是从每个片段构建结果字符串。这可能会导致为您所做的每一次替换分配和复制内存，可能也会显著增加运行时。

Answer 3

那么问题是，为什么这么简单的任务要花这么长时间呢？我们可以说，好的，简单的任务，继续，更好地实现它。但实际情况是，15年前的MFC朴素实现使任务的大小更快。

答案其实很简单。

首先，我使用苹果clang7.0在我的macbook上编译了您的代码：

$ cc --version
Apple LLVM version 7.0.0 (clang-700.1.76)
Target: x86_64-apple-darwin15.2.0
Thread model: posix

结果似乎和OP的..。

Boost.Spirit symbols result: 3425?=3425
10000 cycles took 8906ms.
Boyer-Moore results:3425?=3425
10000 cycles took 2891ms.
Boyer Moore Hospool result:3425?=3425
10000 cycles took 2392ms.
Knuth Morris Pratt result: 3425?=3425
10000 cycles took 4363ms.
Naive STL search and replace result: 3425?=3425
10000 cycles took 4333ms.
Boost replace_all result:3425?=3425
10000 cycles took 23284ms.
MFCMimicking result:3425?=3425
10000 cycles took 426ms.    <-- seemingly outstanding, no?

然后我添加了-O3标志：

Boost.Spirit symbols result: 3425?=3425
10000 cycles took 675ms.
Boyer-Moore results:3425?=3425
10000 cycles took 788ms.
Boyer Moore Hospool result:3425?=3425
10000 cycles took 623ms.
Knuth Morris Pratt result: 3425?=3425
10000 cycles took 1623ms.

Naive STL search and replace result: 3425?=3425
10000 cycles took 562ms.                    <-- pretty good!!!

Boost replace_all result:3425?=3425
10000 cycles took 748ms.
MFCMimicking result:3425?=3425
10000 cycles took 431ms.                    <-- awesome but not as outstanding as it was!

现在的结果与MFC CString的结果相同。

为什么？

因为当您针对BOOST和/或STL进行编译时，您正在扩展模板，并且库代码与编译单元具有相同的优化设置。

当您链接到MFC时，您将链接到一个共享库，该库是在打开优化后编译的。

当您使用strstr时，您将调用c库，它是预编译、优化的，并且在某些部分是手工编写的。当然会很快的！

已解决:)

10000周期不是100000，不同的机器..。

作为参考，以下是在笔记本电脑上运行的100,000个循环版本的电池电源结果。完全优化(-O3)：

Boost.Spirit symbols result: 3425?=3425
100000 cycles took 6712ms.
Boyer-Moore results:3425?=3425
100000 cycles took 7923ms.
Boyer Moore Hospool result:3425?=3425
100000 cycles took 6091ms.
Knuth Morris Pratt result: 3425?=3425
100000 cycles took 16330ms.

Naive STL search and replace result: 3425?=3425
100000 cycles took 6719ms.

Boost replace_all result:3425?=3425
100000 cycles took 7353ms.

MFCMimicking result:3425?=3425
100000 cycles took 4076ms.