12

たとえば、1 から 4、5 から 15、16 から 21、22 から 34 などの数字のバケットがあります。このようなバケットは約 600,000 あります。各バケットに含まれる数値の範囲は異なります。これらのバケットを適切なデータ構造に格納して、数値の検索ができるだけ高速になるようにする必要があります。

したがって、私の質問は、この種の問題に適したデータ構造と並べ替えメカニズムは何かということです。

前もって感謝します

4

6 に答える 6

8

あなたの例のように、バケットが連続していてばらばらである場合、各バケットの左境界（つまり、1、5、16、22）に加えて、最後の要素として、そうでない最初の数値をベクトルに格納する必要があります。 t はどのバケットにも分類されます (35)。（もちろん、整数について話していると思います。）

ベクトルをソートしたままにします。バイナリ検索のような方法で、O(log n) でバケットを検索できます。番号 x がどのバケットに属しているかを検索するには、ベクトル [i] <= x < ベクトル [i+1] となる唯一のインデックス i を探します。x が厳密に vector[0] より小さい場合、または vector の最後の要素以上である場合、それを含むバケットはありません。

編集。これが私が意味することです：

#include <stdio.h>

// ~ Binary search. Should be O(log n)
int findBucket(int aNumber, int *leftBounds, int left, int right)
{
    int middle;

    if(aNumber < leftBounds[left] || leftBounds[right] <= aNumber) // cannot find
        return -1;
    if(left + 1 == right) // found
        return left;

    middle = left + (right - left)/2;

    if( leftBounds[left] <= aNumber && aNumber < leftBounds[middle] )
        return findBucket(aNumber, leftBounds, left, middle);
    else
        return findBucket(aNumber, leftBounds, middle, right);
}


#define NBUCKETS 12
int main(void)
{
    int leftBounds[NBUCKETS+1] = {1, 4, 7, 15, 32, 36, 44, 55, 67, 68, 79, 99, 101};
    // The buckets are 1-3, 4-6, 7-14, 15-31, ...

    int aNumber;
    for(aNumber = -3; aNumber < 103; aNumber++)
    {
        int index = findBucket(aNumber, leftBounds, 0, NBUCKETS);
        if(index < 0)
            printf("%d: Bucket not found\n", aNumber);
        else
            printf("%d belongs to the bucket %d-%d\n", aNumber, leftBounds[index], leftBounds[index+1]-1);
    }   
    return 0;
}
于 2010-04-09T22:26:17.533 に答える
2

おそらく、B-Tree、B + Tree、またはBinarySearchツリーなどのソートされたツリーが必要になるでしょう。

于 2010-04-09T22:08:26.447 に答える
2

私があなたを正しく理解しているなら、あなたはバケットのリストを持っていて、任意の整数を与えられて、それがどのバケットに入るのかを見つけたいと思うでしょう。

バケット範囲のいずれも重複していないと仮定すると、これを二分探索木に実装できると思います。これにより、O（logn）でのルックアップが可能になります（n =バケットの数の場合）。

これを行うのは簡単です。左のブランチをバケットの下端より小さく、右のブランチを右端より大きく定義するだけです。したがって、あなたの例では、次のようなツリーになります。

    16-21
    /    \
  5-15  22-34
  /
1-4

たとえば7を検索するには、ルートを確認するだけです。16未満ですか？はい、左に行きます。5未満？いいえ。15より大きいですか？いいえ、完了です。

最悪の場合のパフォーマンスを抑えるには、ツリーのバランスをとる（または自己バランスツリーを使用する）ように注意する必要があります。入力（バケットリスト）がすでにソートされている場合、これは非常に重要です。

于 2010-04-09T22:12:50.260 に答える
0

これらを C++ で格納して並べ替える簡単な方法は、各バケットの下限と上限を表す並べ替えられた配列のペアを使用することです。次に、 を使用して、int bucket_index= std::distance(lower_bounds.begin(), std::lower_bound(lower_bounds, value))値が一致するバケットを見つけることができます。 は目的のバケットです。if (upper_bounds[bucket_index]>=value)bucket_index

これをバケットを保持する単一の構造体に置き換えることができますが、原則は同じです。

于 2010-04-09T22:26:57.877 に答える
0

二分探索のアイデアに+1。シンプルで、600000 バケットに対して優れたパフォーマンスを発揮します。そうは言っても、それが十分でない場合は、MAX BUCKET VALUE - MIN BUCKET VALUE = RANGE 要素で配列を作成し、この配列の各要素に適切なバケットを参照させることができます。次に、保証された一定の [O(1)] 時間でルックアップを取得しますが、大量のメモリを使用します。

A) バケットにアクセスする確率が一様ではなく、B) 特定のバケットのセットがアクセスされる可能性を知っていた/把握できた場合、おそらくこれら 2 つのアプローチを組み合わせて、一種のキャッシュを作成できます。たとえば、バケット {0, 3} が常にアクセスされており、{7, 13} もアクセスされていた場合、配列 CACHE を作成できます。. .

int cache_low_value = 0;

int cache_hi_value = 13;

キャッシュ[0] = バケット_1

キャッシュ[1] = バケット_1

...

キャッシュ[6] = バケット_2

キャッシュ[7] = バケット_3

キャッシュ[8] = バケット_3

...

キャッシュ[13] = バケット_3

. . . これにより、値をバケットに関連付けようとしている値が cache_low_value と cache_hi_value の間にあると仮定すると、O(1) 時間でバケットを見つけることができます (Y <= cache_hi_value && Y >= cache_low_value; の場合、BUCKET = CACHE[ Y]))。良い面として、このアプローチはマシンのすべてのメモリを使用しません。欠点としては、キャッシュ内に番号/バケットのペアが見つからない場合に、bsearch に 1 つまたは 2 つの追加操作に相当する操作が追加されます (最初にキャッシュをチェックする必要があったため)。

于 2010-04-09T23:42:42.460 に答える
0

あなたの要求をもう一度述べられるかどうか見てみましょう。これは、たとえば、年間通算日があり、その日が何月に属するかを知りたい場合に似ています。では、1 年が 600,000 日 (興味深い惑星) の場合、"Jan"、"Feb"、"Mar"... "Dec" のいずれかの文字列を返しますか?

最初に取得側に焦点を当てます。データ構造を初期化するときにデータを配置する方法を理解できると思います。

データ構造を作成...

typedef struct {
  int DayOfYear    :20; // an bit-int donating some bits for other uses
  int MonthSS      :4;  // subscript to select months
  int Unused       :8;  // can be used to make MonthSS 12 bits
} BUCKET_LIST;

  char MonthStr[12] = "Jan","Feb","Mar"... "Dec";
.

初期化するには、for{} ループを使用して BUCKET_LIST.MonthSS を MonthStr の 12 か月のいずれかに設定します。

取得時に、BUCKET_LIST.DayOfYear のベクトルでバイナリ検索を実行します (BUCKET_LIST.DayOfYear の簡単な比較関数を作成する必要があります)。結果は、bsearch() からの戻り値を MonthStr... の添え字として使用して取得できます。

pBucket = (BUCKET_LIST *)bsearch( v_bucket_list);
MonthString = MonthStr[pBucket->MonthSS];

ここでの一般的なアプローチは、600,000 のエントリに添付された文字列への「ポインタ」のコレクションを持つことです。バケット内のすべてのポインタは、同じ文字列を指しています。ここでは、600k の 4 バイト ポインターの代わりにビット int を添え字として使用しました。これは、必要なメモリが少なく (4 ビット対 4 バイト)、BUCKET_LIST が int の種としてソートおよび検索するためです。

このスキームを使用すると、単純な int キーを格納する以外にメモリやストレージを使用せず、単純な int キーと同じパフォーマンスを得て、取得時のすべての範囲チェックを不要にできます。IE: if{ } テストはありません。BUCKET_LIST データ構造を初期化するためにこれらの if{ } を保存し、取得時にそれらを忘れます。

私はこの手法を添え字エイリアシングと呼んでいます。これは、多の添え字を 1 の添え字に変換することで多対 1 の関係を解決するためです。非常に効率的に追加できます。

私のアプリケーションは、多くの UCHAR の配列を使用して、倍精度浮動小数点数のはるかに小さい配列にインデックスを付けることでした。サイズの縮小は、ホットスポットのすべてのデータをプロセッサの L1 キャッシュに保持するのに十分でした。このわずかな変更だけで、パフォーマンスが 3 倍向上します。

于 2013-01-15T00:52:15.730 に答える