性能std :: strstr vs. std :: string :: find

Question

可能重复:
C++ string :: find complexity

最近我注意到这个函数std::string::find比函数慢了一个数量级std::strstr- 在我的环境中使用Linux上的GCC 4.7.性能差异取决于字符串的长度和硬件架构.

差异似乎有一个简单的原因:std::string::find基本上是std::memcmp在一个循环中调用- 具有时间复杂性O(m * n).相比之下,std::strstr它针对硬件架构进行了高度优化(例如,使用SSE指令),并使用更复杂的字符串匹配算法(显然是Knuth-Morris-Pratt).

我也很惊讶没有在语言文件中找到这两个功能的时间复杂性(即草稿N3290和N1570).我只发现了时间的复杂性char_traits.但这没有用,因为没有子字符串搜索功能char_traits.

我希望,这std::strstr和memmem含有类似优化几乎相同的性能.直到最近,我认为内部std::string::find使用memmem.

问题是:有什么好的理由,为什么std::string::find不使用std::memmem？它在其他实现中有所不同吗？

问题不是:这个功能的最佳实现是什么？如果它比C慢,那么对C++来说真的很难说.如果两个实现都很慢,我就无所谓了.真正伤害的是性能差异.

Answer 1

首先，什么是memmem？我在 C++ 标准和 Posix 标准（包含所有标准 C 函数）中找不到这个。

其次，任何测量值都将取决于实际数据。例如，在很多情况下使用 KMP 会让人感到悲观；可能大多数情况下std::string都会用到 的成员函数；建立必要的表的时间通常会超过简单算法的总时间。当字符串的典型长度很短时，诸如此类的事情O(m*n) 没有多大意义。