c - cでのバイナリ検索の最適化?

Question

キーとレコード番号の間にインデックスがあるキーレコードルックアップを作成しています。これはキーでソートされます。速度の最適化のために私が持っているものよりもこれをうまく行う方法はありますか?

typedef struct
{
    char key[MAX_KEYLEN];
    int  rec;
} KeyRecPair;

typedef struct
{
    KeyRecPair *map;
    int         numRecs;
} KeyRecMap;

int GetRecFromKey(char *key, KeyRecMap *theMap)
{
    int cmpValue, bottom = 0;
    int half = theMap->numRecs / 2;
    int top = theMap->numRecs - 1;

    while (bottom != top)
    {
        cmpValue = strncmp(key, theMap->map[half].key, MAX_KEY_LEN); 

        if (cmpValue > 0)
        {
            /*top stays*/
            bottom = half + 1;
            half  = bottom + (top - bottom) / 2;
            continue;
        }
        if (cmpValue < 0)
        {
            /*bottom stays*/
            top = half - 1;
            half  = bottom + (top - bottom) / 2;
            continue;
        }
        return theMap->map[half].rec;
    }

    if (0 == strncmp(key, theMap->map[half].key, MAX_KEY_LEN))
        return theMap->map[half].rec;
    return 0;
}

score 4 · Accepted Answer

ライブラリ関数は、bsearch実装する適切な比較関数を指定して、配列に対してバイナリ検索を実行します。ライブラリ関数であるため、十分に最適化されており、(できれば) バグがありません。

score 4 · Accepted Answer

あなたの時間のかなりの部分が strncmp に費やされます。

関数呼び出しがオーバーヘッドになるのを避けるために、強制的にinlined にするか、インラインで書き直すことをお勧めします。

勇気があれば、ループを 1 回か 2 回アンロールして、パフォーマンスの向上を確認することもできます。

文字列が実際に char の配列の固定長である場合、長さを 4 の倍数にして、一度に 1 バイトではなく、一度に 4 バイトを unsigned int 比較と比較することができます。

プロファイラーを持っていない場合は、取得する必要があります。プロファイラーを使用すると、さまざまな実装の相対的なコストを簡単に確認できます。

別のオプションは、データを整理する別の方法を選択することです。インスピレーションについては、 AVL ツリーを参照してください。言及されている他のものと同様に、ある種のハッシュ関数を選択することは、実行可能なオプションかもしれません

score 2 · Accepted Answer

バイナリ検索を使用してアイテムを見つける代わりに、O(1) ルックアップ特性を持つハッシュマップの方が適している場合があります。ただし、素朴なアプローチでは衝突が多くなると遅くなる可能性があります。ただし、このペーパーでは、O(log(n) / log(32)) のアクセス時間を持つツリーのようなハッシュマップを作成する方法について説明します。これは通常、通常のハッシュマップの実装よりも優れています。(固定配列 + リンクリストの実装)。

score 1 · Accepted Answer

文字列ではないキーを使用できる可能性はありますか? または少なくとも可能な限り短い文字列ですか？(MAX_KEYLEN の値とは) ループのすべての反復で strcmp が実行される可能性が高いのは、検索の遅い部分の 1 つです。

score 1 · Accepted Answer

これを最適化したい理由はありますか？プロファイラーを使用してプログラムを実行し、ルックアップが総実行時間のかなりの部分を占めていると判断しましたか? どれだけ早く取得できるかだけに興味がありますか? （私の意見では、どちらも正当な理由です。）ランダムに最適化するだけなら、しないでください。

また、ベンチマークすることを忘れないでください。関数の 2 つのバージョンのどちらが最新のシステムで高速かを判断するのは困難です (私の Z80 では簡単でした)。キャッシュミスの数は、誤って予測された分岐の数よりも重要である場合もあれば、そうでない場合もあります。

score 0 · Accepted Answer

私が考えることができる唯一の潜在的な最適化はhalf、残りのサブセットを同じ数の要素を持つ2つの半分に分割する代わりに、計算に黄金比に似たものを使用することです。

        if (cmpValue > 0)
        {
                /*top stays*/
                bottom = half + 1;
                half = bottom + (top - bottom) * 3 / 5;
                continue;
        }
        if (cmpValue < 0)
        {
                /*bottom stays*/
                top = half - 1;
                half = bottom + (top - bottom) * 2 / 5;
                continue;
        }

score 0 · Accepted Answer

2 U で除算する代わりに、ビットシフト演算子を利用できます。

=> for /2 u を使用できます >> 1

score 0 · Accepted Answer

ループごとに 1 回計算する必要があるためhalf、使用する直前に 1 回だけ実行しないのはなぜですか? これにより、複雑に見える (少なくとも比較的言えば) 2 行のコードが削減されます。

score 0 · Accepted Answer

まともなオプティマイザーがこれを行うことを期待していますが、アクセスごとに逆参照するのではなく、レジスターに入る可能性が半分になるように、 theMap->map をローカルに配置します。繰り返しますが、オプティマイザーがこれを行うことを期待しているので、アセンブリの出力も確認することをお勧めします。

Visual Studio 2008 のリリースの出力を見たところ、コードはかなりうまく機能しています。たとえば、比較コードは次のようになります。

; 30   :         if (cmpValue > 0)
test    eax, eax
jle SHORT $LN11@GetRecFrom
; 31   :         {
; omitted inner block for > case.
$LN11@GetRecFrom:
; 37   :         if (cmpValue < 0)
jge SHORT $LN2@GetRecFrom

基本的にcmpValueを再テストせずに分岐する分岐です。いい感じです。

theMap->map をローカルに配置することにはわずかな利点がありますが、小さいものです。MAX_KEY_LEN が適切な 4 の倍数ではなく、構造体がパディングされていない場合は、間違いなく int を構造体の最初に配置する必要があります。

c - cでのバイナリ検索の最適化?

9 に答える 9

Related

Reference