パフォーマンスのstd :: STD対はstrstr ::文字列::

Question

可能な重複見つける：
C++ string::find complexity

を最近、私は機能std::string::findが遅く大きさの順であること、が分かりましたstd::strstrより - 私の環境では、LinuxのGCC 4.7を使っている。パフォーマンスの違いは、文字列の長さとハードウェアアーキテクチャによって異なります。 は、基本的には、ループの中でを呼び出します（時間の複雑さはO(m * n)です）。対照的に、std::strstrはハードウェアアーキテクチャ（SSE命令など）に高度に最適化されており、より洗練された文字列マッチングアルゴリズム（明らかにKnuth-Morris-Pratt）を使用しています。

私はまた、言語文書（すなわちドラフトN3290とN1570）において、これら2つの機能の時間的複雑さを見出さないことに驚いた。私はchar_traitsの時間複雑さしか見つけませんでした。しかし、それは役に立ちません。char_traitsに部分文字列検索の機能がないためです。

私は、std::strstrとmemmemにはほぼ同じ性能の類似の最適化が含まれていると思います。そして、最近まで私はstd::string::findがmemmemを内部的に使用すると仮定しました。

質問は以下のとおりです。std::string::findはstd::memmemを使用しない理由は何か良い理由、ありますか？これは他の実装とは異なるのでしょうか？

質問はありません：この機能の最適な実装は何ですか？ Cよりも遅い場合、C++について議論するのは本当に難しいです。両方の実装が遅いかどうかは関係ありません。それは本当に痛いパフォーマンスの違いです。

Answer 1

まず、memmemとは何ですか？私はこれをC++標準で見つけられず、 Posix標準（すべての標準C関数を含んでいます）も見つかりませんでした。

第2に、測定値は実際のデータによって異なります。たとえば、 KMPを使用すると、多くの場合ペシミゼーションになります。おそらく のメンバー関数がstd::stringの場合のほとんどの場合が使用されます。 必要なテーブルを設定する時間は、多くの場合、直接アルゴリズムの合計時間である 以上になります。 O(m*n) のようなものは、文字列の一般的な長さが短い場合はあまり意味がありません。