0

改行で分割された、並べ替えられたデータを含むテキスト ファイルがあります。例えば：

...
abc123
abc124
abd123
abd124
abd125
...

ここで、データセットのインデックスを作成したいと思います。これは、(少なくとも) サポートする必要があります。

  1. getStringByIndex(n) : ソートされたリストの n 番目の項目を返します。

  2. getIndexByString(s) : すべての項目で を検索し、そのインデックス (見つからない場合は -1) を返します。

ハッシュや B ツリーなどのインデックス作成アルゴリズムをいくつか読みました。子サイズの余分なフィールドを持つ B ツリーは、それをうまく行う必要があります。しかし、日付セットはソートされているので、すべての項目を挿入して B ツリーを構築するよりも効率的な解決策があるのではないでしょうか?

4

1 に答える 1

2

データは並べ替えられているため、データの小さなまばらなサブセットをメモリに保持するだけで、コンテンツを非常に迅速かつ効率的に見つけることができます。たとえば、N 番目ごとの要素をメモリに格納するとします。API を効率的に初期化するには、このスパース リストをディスク上の別のファイルにコンパイルして、取得するために 100 GB のデータをストリーミングする必要がないようにする必要があります。

これらのタームごとに、タームが開始するファイルのヘッドに相対的なディスク オフセットを保存する必要があります。次に、スパース リストとオフセットのペアをメモリにロードするだけで、2 つのリクエストの実装が簡単になります。

    getStringByIndex(n):
        Get floor(n/N)-th string/offset pair from list
        Seek offset position in index
        Read/Skip n mod N strings, then return the next one

    getIndexByString(s):
        Binary search over sparse list in memory
            Locate lower and upper bound string/offset pairs
        If a string/offset pair is in the i-th position in our sparse list,
            then the string itself is the (N x i)-th string in our index.
            We can use this information to compute the return value
        If the string we want isn't in memory:
            Seek lower-bound offset in index
            Read strings until we:
                a) Find a match
                b) Reach the high-bound offset
                c) Reach a string which is lexicographically greater than the one we are looking for
        Else
            Just return the index for the matching string in our sparse list

インデックス内の文字列が固定幅の場合は、さらに最適化を行うことができます。

このアルゴリズムを実装する場合は、このアルゴリズムの「N」の選択に注意する必要があります。ディスク上の位置から 10 バイトを読み取るコストは、同じ位置から 10,000 バイトを読み取るコストよりもはるかに低くはないことを思い出してください。一番痛い。

于 2013-04-05T04:03:02.590 に答える