在C++中搜索搜索和替换的圣杯
kre*_*ieg 3 c++ algorithm mfc boost boost-spirit-qi
最近我一直在寻找一种方法来替换字符串中的标记本质上是查找和替换(但至少还有一种方法可以解决这个问题)并且看起来非常平庸.我有几个可能的实现,但从性能的角度来看,它们都没有令人满意.最佳成就是每次迭代约50us.案例是理想的,字符串的大小从未增长,最初我省略了不区分大小写的要求
以下是我机器上的Coliru
结果的代码:
Boost.Spirit符号结果:3421？= 3421
100000个周期需要6060ms.
Boyer-Moore结果:3421？= 3421
100000个周期为5959ms.
Boyer Moore Hospool结果:3421？= 3421
100000个循环耗时5008ms.
Knuth Morris Pratt结果:3421？= 3421
100000个循环耗时12451ms.
天真的STL搜索和替换结果:3421？= 3421
100000个循环需要5532ms.
提升replace_all结果:3421？= 3421
100000个周期需要4860ms.
那么问题是,在如此简单的任务中需要这么长时间？可以说,好的,简单的任务,继续并更好地实施它.但现实是,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天真搜索和替换结果:3421？= 3421
100000个循环花了516ms.
为什么这个笨拙的代码优于现代C++？为什么其他实现如此缓慢？我错过了什么基本的东西？
EDIT001:我已经投入了这个问题,代码被分析和三重检查.你可能对此不满意,但是std :: string :: replace不是花时间的.在任何STL实现中,搜索是占用大部分时间,提升精神浪费时间分配tst(我猜测评估树中的测试节点).我不希望任何人指着函数中的"这是你的问题"和poof,问题就消失了.问题是MFC如何设法以相同的速度提高10倍.
EDIT002:刚刚深入研究了Find的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模拟扩展结果:3421？= 3421
100000个循环耗时411ms.
意思是4us.每次通话,去击败那个C.strstr
EDIT003:使用-Ox编译和运行
MFC模拟扩展结果:3421？= 3421
100000个循环需要660ms.
MFC天真的搜索和替换结果:3421？= 3421
100000个循环需要856ms.
手动扩展结果:3421？= 3421
100000个循环耗时1995ms.
Boyer-Moore结果:3421？= 3421
100000个周期为6911ms.
Boyer Moore Hospool结果:3421？= 3421
100000个循环耗时5670ms.
Knuth Morris Pratt结果:3421？= 3421
100000个循环花了13825ms.
天真的STL搜索和替换结果:3421？= 3421
100000个循环需要9531ms.
提升replace_all结果:3421？= 3421
100000个周期需要8996ms.
与-O2一起运行(如在原始测量中)但是10k周期
MFC模拟扩展结果:3421？= 3421
10000个周期需要104ms.
MFC天真搜索和替换结果:3421？= 3421
10000个周期需要105ms.
手动扩展结果:3421？= 3421
10000个循环耗时356ms.
Boyer-Moore结果:3421？= 3421
10000个周期需要1355ms.
Boyer Moore Hospool结果:3421？= 3421
10000次循环耗时1101ms.
Knuth Morris Pratt结果:3421？= 3421
10000个循环耗时1973ms.
天真的STL搜索和替换结果:3421？= 3421
10000个周期需要923ms.
提升replace_all结果:3421？= 3421
10000个周期需要880ms.
所以,我对Qi版有一些看法.
还创建了X3版本.
最后,写了一个手动扩展函数,击败了所有其他候选者(我希望它比MFC更快,因为它不会因重复的删除/插入而烦恼).
如果需要,请跳至基准图表.
关于齐版
- 是的,符号表遭受基于节点的容器的局部性问题.它们可能不是您在这里可以使用的最佳匹配.
- 没有必要重建每个循环的符号:
而不是按字符顺序跳过非符号,扫描到下一个:
Run Code Online (Sandbox Code Playgroud)+(bsq::char_ - symbols)
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();
}
这在我的机器上的性能非常优越.
其他想法
您可以使用静态生成的令牌表来查看Boost Spirit Lex:http://www.boost.org/doc/libs/1_60_0/libs/spirit/doc/html/spirit/lex/abstracts/lexer_static_model.html.我不是特别喜欢Lex.
COMPARISONS:
请参阅交互式图表
这是使用Nonius进行基准测试统计.
完整的基准代码: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);
})