2

動的に増加/減少できる複数の範囲が構成されています。指定された数値が存在するかどうかを見つける最速の方法を見つける必要があります。存在する場合は範囲​​を返しますか? そのような操作を行うための C での最速のアルゴリズムまたはデータ構造を教えてください。

コード スニペットは次のとおりです。

addr = GET_U32BIT(buf);

    /* Search for the corresponding address */
    while(i < addr_table_size)
    {
        if((addr >= ntohl(table->addr_id[i].start_addr)) && \
                (addr <= ntohl(table->addr_id[i].end_addr)))
        {
            addr_present = 1;
            range_id = i;
            break;          
        }
        i++;
    }

上記のコードでは、addr は、実行時に受信したバッファーから派生した 4 バイトの数値です。開始アドレスと終了アドレスが格納されているテーブルで線形検索を実行している間、テーブルは約 50,000 から 100,000 になる可能性があるため、パフォーマンスは非常に低くなります。エントリ。

ありがとう

4

1 に答える 1

0

これは、インターバル ツリーで行うことができます。範囲ごとに、間隔ツリーに 1 つのエントリを挿入します。

ここで、番号「k」が存在する範囲を検索する場合。インターバル ツリーで検索します。また、範囲が変更されるたびに、その範囲を Interval から削除し、新しい値で再挿入します。

于 2012-11-07T09:06:07.873 に答える