c - C での検索アルゴリズムの最適化

Question

この逐次検索アルゴリズム ( The Practice of Programmingから取得) のパフォーマンスは、C のネイティブユーティリティを使用して改善できますか? たとえば、i 変数をレジスタ変数に設定した場合などです。

int lookup(char *word, char*array[])
{
    int i

    for (i = 0; array[i] != NULL; i++)
        if (strcmp(word, array[i]) == 0)
            return i;

    return -1;
}

score 24 · Accepted Answer

はい、しかしごくわずかです。より優れたアルゴリズムを使用することで、パフォーマンスを大幅に向上させることができます（たとえば、リストを並べ替えたままにして、バイナリ検索を実行するなど）。

一般に、特定のアルゴリズムを最適化することは、これまでのところしか得られません。より優れたアルゴリズムを選択すると（完全に最適化されていなくても）、パフォーマンスが大幅に（桁違いに）向上します。

score 2 · Accepted Answer

あまり違いはないと思います。コンパイラはすでにその方向に最適化しています。

さらに、変数iはあまり影響を与えず、wordは関数全体で一定のままであり、残りは大きすぎてどのレジスタにも収まりません。キャッシュの大きさと、アレイ全体がそこに収まるかどうかだけが問題になります。

文字列の比較は、計算コストがかなり高くなります。

検索する前に、配列に何らかのハッシュを使用できますか？

score 2 · Accepted Answer

センチメンタルメソッドとして有名な手法があります。センティナルメソッドを使用するには、「array[]」の長さを知っている必要があります。センティナルを使用して比較する「array[i] != NULL」を削除できます。

int lookup(char *word, char*array[], int array_len)
{
    int i = 0;
    array[array_len] = word;
    for (;; ++i)
        if (strcmp(word, array[i]) == 0) 
            break;
    array[array_len] = NULL;
    return (i != array_len) ? i : -1;
}

score 1 · Accepted Answer

TPOPを読んでいる場合は、次に、さまざまなデータ構造とアルゴリズムを使用して、この検索が何倍も高速になる方法を確認します。

しかし、次のようなものを置き換えることで、物事を少し速くすることができます

for (i = 0; i < n; ++i)
    foo(a[i]);

と

char **p = a;
for (i = 0; i < n; ++i)
    foo(*p);
    ++p;

配列の最後に既知の値（たとえばNULL）がある場合は、ループカウンターを削除できます。

for (p = a; *p != NULL; ++p)
    foo(*p)

頑張ってください、それは素晴らしい本です！

score 0 · Accepted Answer

現実的には、I をレジスター変数に設定しても、コンパイラーがまだ実行していないことは何も実行されません。

事前に参照配列の前処理に時間を費やしたい場合は、「世界最速のスクラブルプログラム」をググって実装してください。ネタバレ: これは、キャラクタールックアップ用に最適化された DAG です。

score 0 · Accepted Answer

そのコードを最適化するには、strcmp ルーチンを書き直すのが最善の方法です。これは、等価性をチェックするだけで、単語全体を評価する必要がないためです。

それ以外にできることはあまりありません。大きなテキスト内のテキストを探しているように見えるため、並べ替えはできません。テキストがソートされる可能性は低いため、バイナリ検索も機能しません。

私の2p（C疑似コード）：

wrd_end = wrd_ptr + wrd_len;
arr_end = arr_ptr - wrd_len;
while (arr_ptr < arr_end)
{
    wrd_beg = wrd_ptr; arr_beg = arr_ptr;
    while (wrd_ptr == arr_ptr)
    {
        wrd_ptr++; arr_ptr++;
        if (wrd_ptr == wrd_en)
            return wrd_beg;
    }
    wrd_ptr++;
}

score 0 · Accepted Answer

Mark Harrison: あなたの for ループは決して終了しません! (++p はインデントされていますが、実際には for 内にはありません :-)

また、ポインターとインデックス作成の切り替えは、通常、パフォーマンスに影響を与えず、登録キーワードを追加することもありません (mat が既に述べているように)。、手動の疑似マイクロ最適化よりも優れた仕事をします。

score 0 · Accepted Answer

これを行うもう 1 つの手っ取り早い方法は、コンパイラに SSE2 最適化 memcmp を使用させることです。固定長の char 配列を使用して整列し、文字列が 64 バイトの整列で始まるようにします。次に、関数に const char *match の代わりに const char match[64] を渡すか、64,128,256 バイト配列に strncpy match を渡すと、適切な memcmp 関数を取得できると思います。

これについてもう少し考えてみると、これらの SSE2 マッチ関数は、Intel や AMD のアクセラレータライブラリなどのパッケージの一部である可能性があります。それらをチェックしてください。

score 0 · Accepted Answer

文字列を一致させるより高速な方法は、パスカルスタイルで格納することです。文字列ごとに 255 文字を超える必要がない場合は、最初のバイトにカウントを入れて、大まかに次のように格納します。

char s[] = "\x05Hello";

次に、次のことができます。

for(i=0; i<len; ++i) {
    s_len = strings[i][0];
    if(
        s_len == match_len
        && strings[i][s_len] == match[s_len-1]
        && 0 == memcmp(strings[i]+1, match, s_len-1)
    ) {
        return 1;
    }
}

さらに高速化するには、文字列の先頭 + 64、+ 128、および次の文字列の先頭にメモリプリフェッチヒントを追加します。しかし、それはただのクレイジーです。:-)

score -1 · Accepted Answer

/* there is no more quick  */
int lookup(char *word, char*array[])
{
    int i;
    for(i=0; *(array++) != NULL;i++)
        if (strcmp(word, *array) == 0)
            return i;
    return -1;
}

c - C での検索アルゴリズムの最適化

10 に答える 10

Related

Reference