13

私の C プログラムには、多くの strstr 関数呼び出しがありました。標準ライブラリ strstr はすでに高速ですが、私の場合、検索文字列の長さは常に 5 文字です。速度を上げるために、特別なバージョンに置き換えました。

int strstr5(const char *cs, const char *ct)
{
    ながら (cs[4]) {

        if (cs[0] == ct[0] && cs[1] == ct[1] && cs[2] == ct[2] && cs[3] == ct[3] && cs[4] == ct[4])
            1 を返します。

        cs++;
    }

    0 を返します。
}

ct が cs で発生するかどうかを知るには十分であるため、この関数は整数を返します。この特殊なケースでは、私の関数は標準の strstr よりもシンプルで高速ですが、適用できるパフォーマンスの改善があるかどうかを知りたいです。小さな改善でも大歓迎です。

概要：

  • cs の長さは >=10 ですが、それ以外の場合は変わる可能性があります。長さは以前にわかっています（私の機能では使用されていません）。cs の長さは通常 100 から 200 です。
  • ct の長さは 5
  • 文字列の内容は何でもかまいません

編集：すべての回答とコメントに感謝します。アイデアを研究してテストし、何が最も効果的かを確認する必要があります。サフィックス trie に関する MAK のアイデアから始めます。

4

5 に答える 5

15

いくつかの高速文字列検索アルゴリズムがあります。Boyer-Moore (Greg Hewgill によって既に提案されているように)、Rabin-Karp、およびKMPアルゴリズムを調べてみてください。

同じ大きなテキスト本文で多くの小さなパターンを検索する必要がある場合は、接尾辞ツリーまたは接尾辞配列の実装を試すこともできます。しかし、これらは理解して正しく実装するのがやや難しいです。

ただし、これらの手法は非常に高速ですが、関連する文字列が非常に大きい場合にのみかなりの速度向上が得られることに注意してください。1000 文字未満の長さの文字列では、それほど高速化されない場合があります。

編集：

同じテキストを何度も検索する場合 (つまり、 の値がcs呼び出し間で常に/しばしば同じである場合)、接尾辞 trie (基本的には接尾辞の trie) を使用すると、大幅な高速化が得られます。テキストは 100 文字または 200 文字と小さいため、より単純な O(n^2) メソッドを使用してトライを構築し、それに対して複数の高速検索を実行できます。各検索では、通常の 5*200 ではなく、5 回の比較のみが必要になります。

編集2：

caf のコメントで述べたように、C のstrstrアルゴリズムは実装に依存します。glibc は線形時間アルゴリズムを使用しますが、これは実際には、私が言及したどの方法よりも多かれ少なかれ高速である必要があります。OPの方法は漸近的に遅くなりますが（ O(n) ではなく O(N*m) ）、おそらく n と m （パターンとテキストの長さ）の両方が非常に小さく、 glibc バージョンでは長い前処理を行う必要はありません。

于 2010-06-27T19:34:12.330 に答える
12

比較の数を減らすと、検索の速度が上がります。文字列の実行中の int を保持し、検索語の固定 int と比較します。一致する場合は、最後の文字を比較します。

uint32_t term = ct[0] << 24 | ct[1] << 16 | ct[2] << 8 | ct[3];
uint32_t walk = cs[0] << 24 | cs[1] << 16 | cs[2] << 8 | cs[3];
int i = 0;

do {
  if ( term == walk && ct[4] == cs[4] ) { return i; } // or return cs or 1
  walk = ( walk << 8 ) | cs[4];
  cs += 1;
  i += 1;
} while ( cs[4] ); // assumes original cs was longer than ct
// return failure

短い cs のチェックを追加します。

編集：

コメントからの修正を追加しました。ありがとう。

これは、64 ビット値を使用するために簡単に採用できます。cs[4] と ct[4] をローカル変数に格納することもできますが、コンパイラがそれを行うと想定する必要はありません。ループの前に cs と ct に 4 を追加し、ループで cs[0] と ct[0] を使用できます。

于 2010-06-27T19:46:50.563 に答える
5

strstr のインターフェイスは、打ち負かすことができるいくつかの制約を課します。null で終わる文字列を取り、ターゲットの「strlen」を最初に実行した競合他社は負けます。「状態」引数を必要としないため、セットアップ コストは、(たとえば) 同じターゲットまたはパターンを使用した多くの呼び出しで償却できません。非常に短いターゲット/パターン、および病理学的データ (「ABABABABAB...C」の文字列で「ABABAC」を検索することを検討してください) を含む、幅広い入力で動作することが期待されます。libc もプラットフォームに依存するようになりました。x86-64 の世界では、SSE2 は 7 年前のものであり、SSE2 を使用する libc の strlen および strchr は、単純なアルゴリズムよりも 6 ～ 8 倍高速です。SSE4.2 をサポートする Intel プラットフォームでは、strstr は PCMPESTRI 命令を使用します。しかし、あなたもそれを打ち負かすことができます。

Boyer-Moore の (および Turbo BM と Backward Oracle Matching などの) セットアップ時間は、ヌル終端文字列の問題を考慮に入れなくても、実行からほとんどノックアウトされます。Horspool は制限付きの BM であり、実際にはうまく機能しますが、エッジ ケースはうまく機能しません。その分野で私が見つけた最高のものはBNDM（「Backward Nondeterministic Directed-Acyclic-Word-Graph Matching」）であり、その実装はその名前よりも小さい:-)

興味深いと思われるいくつかのコード スニペットを次に示します。 インテリジェント SSE2 はナイーブ SSE4.2を打ち負かし、ヌル終了の問題を処理します。 BNDM の実装は、セットアップ コストを維持する 1 つの方法を示しています。Horspool に精通している場合は、BNDM がスキップ オフセットの代わりにビットマスクを使用することを除いて、類似性に気付くでしょう。Horspool や BNDM などのサフィックス アルゴリズムのヌル ターミネータの問題を (効率的に) 解決する方法を投稿しようとしています。

すべての優れたソリューションに共通する属性は、異なる引数の長さに対して異なるアルゴリズムに分割することです。その一例がサンメイスの「レールガン」機能。

于 2012-02-05T18:06:33.147 に答える
3

最新の x86 コンピューターでの適切な実装に勝るものはありません。

新しい Intel プロセッサには、調べている文字列の 16 バイト、最大 16 バイトの検索文字列を取得する命令があり、1 つの命令で、検索文字列が存在する可能性のある最初のバイト位置 (または検索文字列がない場合) を返します。 ）。たとえば、文字列「abcdefghijklmnHexyz」で「Hello」を検索すると、最初の命令で、文字列「Hello」がオフセット 14 から始まる可能性があることがわかります (16 バイトを読み取るため、プロセッサにはバイト H、e、未知のバイトがある可能性があります)。オフセット 14 から始まる次の命令は、文字列がそこにないことを伝えます。もちろん、末尾のゼロ バイトについても認識しています。

これは、19 文字の文字列に 5 文字の文字列が存在しないことを検出するための2 つの命令です。特別なケースコードでそれを打ち負かしてみてください。(明らかに、これは strstr、strcmp および同様の命令用に特別に構築されています)。

于 2015-12-02T17:25:52.517 に答える
3

が 4 文字未満の場合、コードはcsその割り当ての境界を超えてアクセスする可能性があります。cs

文字列検索の一般的な最適化は、Boyer-Mooreアルゴリズムを使用してcs、. アルゴリズムの完全な説明については、リンク先のページを参照してください。ct

于 2010-06-27T19:14:47.223 に答える