2

構造のような大きな永続配列を実装するためにどのような種類のデータ構造を使用しますか（サイズ> 10 Mio要素）

データ構造のインターフェースは、次の操作をサポートする必要があります。

YType get(IdxType idx) // random access  
void insertIdx(IdxType idx, YType yValue) // random insert   
void deleteIdx(IdxType idx) // random delete

インデックスを、スカラー値または構造体IdxTypeなどのスカラー符号なし値とします。unsigned long longYType

これらの操作の複雑さはO（log n）より大きくなることはなく、ランダムアクセスの複雑さがしばらくしてO（1）に下がると、多くのユースケースで読み取り操作が最も使用されるため、非常に効率的です。

ベクトルの挿入の複雑さはO（n）であり、リストのランダムアクセスもO（n）であるため、これらの要件は、ディスクに書き込むことができるベクトルやリストなどのメモリデータ構造を除外します。

編集：
インデックスキーを持つデータ構造のようなハッシュマップまたはツリーは要件を満たさないことに注意してください。特定のインデックスの値は変更される可能性があります。つまり、インデックスの値を挿入すると、後続のすべてのインデックスの値が変更されます。これは、要素を挿入するときに、配列内の後続のインデックスに起こることとまったく同じです。

4

2 に答える 2

0

O(log n) の挿入、削除、および検索をサポートするツリー データ構造である順序統計ツリーを使用することができます。通常、順序統計ツリーは並べ替えられたデータを格納するために使用されますが、並べ替えられていないシーケンスを格納するように変更するのは比較的簡単です。

直観的に、順序統計ツリーは、各ノードが左側のサブツリーに子の数を格納するバイナリ ツリーです。そうすれば、次のように n 番目の要素を再帰的に検索できます。

  1. ツリーが null の場合、要素はありません。
  2. n が左側の部分木 (I と呼びます) の要素数以下の場合、左側の部分木の要素を再帰的に検索します。
  3. n = k + 1 の場合、ツリーのルートは n 番目の要素です。
  4. それ以外の場合は、右側のサブツリーで n - k - 1 番目の要素を検索します。

ノード n の前に挿入するには、これと同じ手順を使用して n 番目のノードを見つけ、そのノードの順序で先行ノードとして新しい値を挿入します (左に移動し、ツリーから離れてそこにノードを挿入するまで右に移動します)。次に、ツリーを n 番目の要素から上に戻り、更新が必要な挿入パス上のすべてのノードの k の値を調整します。

ツリーが不均衡になりすぎるのを防ぐために、標準的なツリーのバランス スキーム (AVL、赤/黒など) を使用して、高さを O(log n) に保つことができます。これにより、データ構造に対するすべての操作で O(log n) のパフォーマンスが得られます。

お役に立てれば！

于 2013-01-04T17:00:43.133 に答える
0

同時アクセスが必要かどうかによって異なります...

いいえ

任意の時点でアクセスできるクライアント アプリケーションが 1 つだけ必要な場合は、アクセスと変更のバランスがとれたロープなどのメモリ内構造を使用します (または、"配列" インデックスをキーとして持つハッシュ テーブルのみでも構いません)。複雑。作業が完了したら、単純なファイルにシリアル化します。最近の RAM は安価で豊富にあり、各要素が非常に大きい場合を除き、1,000 万個の要素が適切に収まるはずです。

はい

同時アクセスが必要な場合は、トランザクションなど、データベースを使用します。あなたの「配列」は、物理的にキーが配列インデックスである B ツリーになります。DBMS がサポートしている場合は、クラスタリングを使用して「不要な」テーブル ヒープを排除し、すべてを B ツリーに保持します。このようなもの：

CREATE TABLE THE_ARRAY (
    INDEX INT PRIMARY KEY,
    DATA VARCHAR(50) -- Whatever...
) ORGRANIZATION INDEX

(ORGRANIZATION INDEX は、他の DBMS で「クラスタリング」と呼ばれるものに対する Oracle 固有の構文です。使用している DBMS に適した構文を使用してください。)

挿入は O(N) になり (挿入されたインデックスの後にインデックスを更新する必要があるため)、ルックアップは O(log(N)) になります。また、一部の DBMS はハッシュ インデックスをサポートしています。これにより、O(1) ルックアップが可能になりますが、B ツリーよりも挿入が悪化する可能性があります。

于 2013-01-04T17:44:42.330 に答える