3

ディスクに保存したいハッシュテーブルがあります。リストは次のようになります。

<16-byte key                   > <1-byte result>
a7b4903def8764941bac7485d97e4f76 04
b859de04f2f2ff76496879bda875aecf 03
etc...

100 万から 500 万のエントリがあります。現在、私はそれらを 1 つのファイルに格納しているだけです。エントリあたり 17 バイト×エントリ数です。そのファイルは数十メガバイトです。私の目標は、最初にディスク上のスペースを最適化し、次に検索時間を最適化する方法でそれらを保存することです。挿入時間は重要ではありません。

これを行う最善の方法は何ですか？ファイルはできるだけ小さくしたい。複数のファイルでもかまいません。パトリシアトライ？基数トライ？

良い提案があれば、実装してテストします。ここに結果を掲載しますので、ぜひご覧ください。

4

6 に答える 6

4

エントリをキーで並べ替えて、バイナリ検索を実行できます。

固定サイズのキーとデータ エントリは、行から行へと非常に迅速にジャンプできることを意味し、キーとデータのみを保存することは、メタ データのスペースを無駄にしないことを意味します。

ディスク容量を節約できるとは思いませんし、ルックアップ時間は O(log(n)) です。挿入時間は非常に長いですが、それは問題ではないとおっしゃいました。

長いアクセス時間を本当に許容できる場合は、テーブルをソートしてから、ある程度のサイズのブロックにチャンクして圧縮します。各ブロックのオフセット*と開始/終了キーを、ファイルの最初のセクションに格納します。このスキームを使用すると、必要なキーを含むブロックを線形時間で見つけて、解凍されたブロック内でバイナリ検索を実行できます。一度にメモリにロードするファイルの量に基づいて、ブロック サイズを選択します。

市販の圧縮方式 (GZIP など) を使用すると、必要に応じて圧縮率を調整できます。ファイルが大きいほど、ルックアップ時間が短縮されると思われます。

あなたの構造はほとんどハッシュであるように見えるので、スペースの節約がそれほど素晴らしいものになるとは思えません。それらが実際にハッシュである場合、それらはランダムであり、ひどく圧縮されません。並べ替えは圧縮率を高めるのに役立ちますが、1トンではありません。

*ヘッダーを使用して、解凍して使用するブロックのオフセットを検索します。

于 2009-12-24T08:39:47.380 に答える
3

500 万レコード、約 81MB です。メモリ内の配列を操作するのに許容されます。

問題について説明したように、ハッシュ値よりも一意のキーです。値にアクセスするためにハッシュ テーブルを使用してみてください (このリンクを見てください)。

私の誤解があり、これが実際のハッシュである場合は、これより上の 2 番目のハッシュ レベルを構築してみてください。

ハッシュテーブルもディスク上でうまく整理できます（たとえば、別のファイルとして）。

添加

検索パフォーマンスが高く、オーバーヘッドが少ないソリューションは次のとおりです。

  1. キーから整数値を生成するハッシュ関数を定義します。
  2. この関数によって生成された値に従って、ファイル内のレコードを並べ替えます
  3. 各ハッシュ値の開始位置にファイル オフセットを保存する
  4. 値を見つけるには:
    4.1.
    関数4.2でハッシュを計算します。ファイル
    4.3 のオフセットのルックアップ。この位置から始まり、キーが見つかるか、次のキーのオフセットに到達しないか、ファイルの終わりまで、ファイルからレコードを読み取ります。

指摘しなければならない追加事項がいくつかあります。

  • ハッシュ関数を有効にするには高速である必要があります
  • ハッシュ関数は、線形分散値またはそれに近い値を生成する必要があります
  • ハッシュ値オフセットのテーブルは、別のファイルに配置できます
  • アプリケーションの開始時にソートされたファイル全体を順次読み取り、メモリに格納することで、ハッシュ値オフセットのテーブルを動的に生成できます。
  • ステップ 4.3 で。レコードを有効にするには、1 つずつではなく、ブロックごとに読み取る必要があります。理想的には、計算されたハッシュを使用してすべての値を一度にメモリに読み取ります。

ここでハッシュ関数の例をいくつか見つけることができます。

于 2009-12-24T09:04:55.397 に答える
1

ファイル設計の場合と同様に、データの分布について知っている (そして私たちに教えてくれる) ほど、より良い結果が得られます。キー値がすべての 16 バイト キーのセット全体に均等に分散されているという前提に基づいて (ハッシュ テーブルを格納している場合はこれが当てはまるはずです)、他の人が既に提案したものの組み合わせを提案します。

  • このようなバイナリ データは、バイナリ ファイルに属します。ハッシュと値の簡単な表現が 16 進数の文字列であるという事実にだまされて、これが文字列データであると考えさせないでください。

  • ファイルサイズは、シバン全体を最新のPCやサーバー、および他の多くのデバイスのメモリに保持できるほどです。

  • キーの先頭の 4 バイトは、可能なキーのセットを 16^4 (= 65536) のサブセットに分割します。キーが均等に分散されていて、5x10^6 のエントリがある場合、サブセットあたり約 76 のエントリになります。たとえば、サブセットごとに 100 エントリのスペースを持つファイルを作成します。それから：

  • オフセット 0 で、先頭の 4 バイト 0x0000 ですべてのエントリの書き込みを開始します。合計 100 エントリ (1700 バイトだと思います) まで 0 で埋めます。

  • オフセット 1700 で、先頭の 4 バイト 0x0001、パッド、

  • すべてのデータを書き込むまで繰り返します。

これで、ルックアップは、ファイルへのオフセットを計算し、その後に最大 100 のエントリをスキャンして目的のエントリを見つける計算になります。これが十分に高速でない場合は、16^5 サブセットを使用して、サブセットごとに約 6 エントリ (6x16^5 = 6291456) を許可します。これは二分探索よりも高速になると思いますが、これは推測にすぎません。

挿入には少し問題があります。新しいエントリが (a) サブセットの再ソートを必要とするか、(b) エントリのリストの最後に単純に追加できるかを判断するのは、データに関する知識を持っているあなた次第です。そのインデックスで (つまり、ルックアップごとにサブセット全体をスキャンします)。

スペースが非常に重要な場合は、もちろんエントリから先頭の 4 バイトを削除できます。これは、ファイルへのオフセットの計算によって計算されるためです。

私が説明しているのは、あまりよくありませんが、hash tableです。

于 2009-12-24T11:16:07.757 に答える
1

キーは 128 ビットですが、最大 10^7 のエントリがある場合、インデックスに 24 ビットしかかかりません。

  1. ハッシュテーブルを作成するか、

  2. 次のように、Bentley スタイルの展開された二分探索 (最大 24 の比較) を使用します。

これが展開されたループです (32 ビットの int を使用)。

int key[4];
int a[1<<24][4];

#define COMPARE(key, i) (key[0]>=a[i][0] && key[1]>=a[i][1] && key[2]>=a[i][2] && key[3]>=a[i][3])

i = 0;
if (COMPARE(key, (i+(1<<23))) >= 0) i += (1<<23);
if (COMPARE(key, (i+(1<<22))) >= 0) i += (1<<22);
if (COMPARE(key, (i+(1<<21))) >= 0) i += (1<<21);
...
if (COMPARE(key, (i+(1<<3))) >= 0) i += (1<<3);
if (COMPARE(key, (i+(1<<2))) >= 0) i += (1<<2);
if (COMPARE(key, (i+(1<<1))) >= 0) i += (1<<3);
于 2009-12-24T16:32:43.000 に答える
1

シンプルなアプローチは機能し、それらをsqlite データベースに保存しますか? これ以上小さくなるとは思いませんが、非常に優れたルックアップ パフォーマンスが得られるはずであり、実装も非常に簡単です。

于 2009-12-24T08:40:36.053 に答える
1

まず第一に、ディスク容量を最適化したい場合、複数のファイルは問題ありません。これはクラスター サイズのためです。サイズが 100 バイト以下のファイルを作成すると、クラスター サイズごとにディスク容量が減少します (たとえば 2kB)。

第二に、あなたの場合、すべてのテーブルを単一のバイナリファイルに保存し、キーのバイト値で単純に ASC に並べます。それはあなたがアーカイブを使用したくない場合は最小であるentriesNumber * 17と正確に等しい長さのファイルを提供します.2番目に、キー分割ファイルを検索するときに、時間〜log2（entriesNumber）で非常に迅速な検索を使用できます。 2 つの部分に分割し、境界のキーを必要なキーと比較します。「境界キー」が大きい場合はファイルの最初の部分を取得し、大きい場合は 2 番目の部分を取得します。そして、再び2つの部分に分割するなどします。したがって、単一のキーを検索するには、約log2(entriesNumber)の読み取り操作が必要になります。

于 2009-12-24T08:46:41.510 に答える