重複の可能性:
C++ string::find complex
最近、Linux で GCC 4.7 を使用している私の環境ではstd::string::find、関数が関数よりも桁違いに遅いことに気付きました。std::strstrパフォーマンスの違いは、文字列の長さとハードウェア アーキテクチャによって異なります。
違いには単純な理由があるようです。std::string::find基本的std::memcmpにはループで呼び出します-時間の複雑さがありO(m * n)ます。対照的にstd::strstr、ハードウェア アーキテクチャ (SSE 命令など) 向けに高度に最適化されており、より洗練された文字列一致アルゴリズム (明らかに Knuth-Morris-Pratt) を使用しています。
また、これら 2 つの関数の時間の複雑さが言語ドキュメント (つまり、ドラフト N3290 と N1570) にないことにも驚きました。の時間の複雑さだけが見つかりましたchar_traits。しかし、 には部分文字列検索の機能がないため、これは役に立ちませんchar_traits。
私は、ほぼ同じパフォーマンスで同様の最適化が含まれていることstd::strstrを期待しています。memmemそして最近まで、私はそれが内部的にstd::string::find使用されていると思っていました。memmem
質問は次のとおりです。正当な理由はありますか、なぜstd::string::find使用しないのstd::memmemですか? また、他の実装では異なりますか?
問題は、この関数の最適な実装は何かということではありません。C++ が C よりも遅い場合、C++ を支持するのは本当に難しいです。両方の実装が遅いかどうかは問題ではありません。本当に痛いのはパフォーマンスの違いです。