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

Question

この逐次検索アルゴリズムはパフォーマンスを発揮できるでしょうか (以下から引用)プログラミングの実践) 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;
}

Answer 1

はい、でもほんのわずかです。より優れたアルゴリズム (リストをソートしたままにし、バイナリ検索を実行するなど) を使用すると、パフォーマンスを大幅に向上させることができます。

一般に、特定のアルゴリズムを最適化しても、限界までしか達成できません。より良いアルゴリズムを選択すると (完全に最適化されていない場合でも)、パフォーマンスが大幅に向上する可能性があります。

Answer 2

それほど大きな違いはないと思います。コンパイラはすでにその方向に最適化しています。

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

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

検索する前に、配列に対してある種のハッシュを使用できますか?

Answer 3

センチナル手法としてよく知られた技術がある。Sentinal メソッドを使用するには、「array[]」の長さを知っておく必要があります。Sentinalを使用すると、「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;
}

Answer 4

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)

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

Answer 5

コードを最適化するには、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++;
}

Answer 6

マーク・ハリソン：for ループは決して終了しません。(++p はインデントされていますが、実際には for 内にありません:-)

また、ポインタとインデックスの切り替えは一般にパフォーマンスに影響を与えず、(すでに述べたように) register キーワードを追加することもありません。コンパイラは、必要に応じてこれらの変換を適用するのに十分賢いので、CPU アーキテクチャについて十分に指示すれば、 、手動による疑似マイクロ最適化よりも、これらの処理がうまくいきます。

Answer 7

文字列を照合するより迅速な方法は、文字列をパスカル スタイルで保存することです。文字列あたり 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、および次の文字列の開始にメモリ プリフェッチ ヒントを追加します。しかし、それは本当にクレイジーです。:-)

Answer 8

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

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

Answer 9

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

事前に参照配列の前処理に時間を費やしたい場合は、「世界最速のスクラブル プログラム」をグーグルで検索して実装する必要があります。ネタバレ：これは、文字検索用に最適化された DAG です。

Answer 10

/* 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;
}