2

各項目は、17 個の 32 ビット整数の配列です。おそらく、120 ビットの一意のハッシュを生成できます。

私はこれらのアイテムを 9,731,643,264 個生成するアルゴリズムを持っており、そのうちのいくつが一意であるかを確認したいと考えています。これらの最大 36 分の 1 が一意であると推測しますが、確実ではありません。

このサイズでは、メモリ内でこれを実際に行うことはできません (ギグが 4 つしかないため)。そのため、これらのリストを保持し、メンバーシップ テストを行い、まだ存在しない場合は新しいものをそれぞれ追加する方法が必要です。

私は Linux の C(gcc) で作業しているので、ソリューションがそこから機能する場合は良いでしょう。

何か案は？

4

2 に答える 2

2

これは、何年も前に「Knight's Tour」の解決に取り組んでいたときに直面したいくつかの問題を思い出させます。（現在解決されている数学の問題ですが、私ではありません。）

あなたのハッシュでさえ、それほど役に立ちません。. . ほぼ GUID のサイズで、既知の宇宙全体で簡単に一意にすることができます。

リストをディスクに保持するだけでも、約 0.75 テラバイトかかります。. . 4ギガのメモリであろうとなかろうと、それらを保持するためだけに巨大なディスクが必要になります. また、以下で説明するソート/マージ ソリューションを実行するには、その 2 倍以上のディスクが必要になります。

そのリストを並べ替えることができれば、一度に 1 つずつリストを投げて、隣り合った一意のコピーを探すことができます。もちろん、それだけの量のデータを並べ替えるには、バイナリであるため、カスタムの並べ替えルーチン (作成したもの) が必要になります (16 進数に変換すると、データのサイズが 2 倍になりますが、標準のルーチンを使用できるようになります)。. . おそらくそこにいても、おそらくそれだけの量のデータで窒息するでしょう。. . 独自のカスタム ルーチンに戻ります。

考慮すべき点:

  1. それだけの量のデータを並べ替えるには、数週間、数か月、あるいは数年かかるでしょう。メモリ内で適切なヒープ ソートなどを行うことができますが、ディスク領域が非常に限られているため、メモリ内で何を行うかに関係なく、ファイルの「バブル」ソートを行う可能性があります。

  2. 生成アルゴリズムがどのように見えるかに応じて、「1 メモリ ロード」相当のデータを生成し、その場所で並べ替えてから、ファイル (並べ替え済み) でディスクに書き出すことができます。それが完了したら、ソートされた個々のファイルをすべて「マージ」する必要があります。これは、はるかに簡単な作業です (数千のファイルがあるとしても、比較的簡単な作業です)。

  3. ジェネレーターがデータについて何でも教えてくれる場合は、それを有利に利用してください。たとえば、私の場合、Knight's Moves を処理していると、出力値が常に大きくなっていることがわかりました (常に移動ごとに 1 ビットを追加していたため)。その小さな知識により、独自の方法でソートを最適化することができました。データを見て、似たようなことを知っているかどうかを確認してください。

  4. もちろん、データを小さくすることは常に良いことです。たとえば、120 ハッシュについて話していますが、それは可逆的ですか? その場合、ハッシュが小さいのでソートします。そうでない場合、ハッシュはあまり役に立たない可能性があります（少なくとも私のソートソリューションでは）。

私はこのような問題の仕組みに興味があります。アイデアや考えられる解決策について意見を交換したいだけでも、このテーマについてメールを交換できれば幸いです。

于 2011-01-15T17:00:37.810 に答える
1

入力データにいくつかの制限を加えることができれば、おそらくあなたの生活はずっと楽になります: 有効ビット数が 120 だけであると仮定しても、重複値の数が多いということは、分布が不均一であることを示唆しています。のサイズ10^10:

2^120 = (2^10)^12 > (10^3)^12 = 10^36 >> 10^10

連続したクラスターがある場合 (スパースではなく反復値ではなく)、原子値の代わりに範囲を操作することで多くのことを得ることができます。

私がすること：

  • 生成された値のバッチでバッファを埋める
  • メモリ内のバッファをソートする
  • 範囲をディスクに書き込みます。つまり、ファイル内の各エントリは、値の連続グループの開始値と終了値で構成されます

次に、個々のファイルをマージする必要があります。これは、オンラインで実行できます。つまり、ファイルが利用可能になったときに、スタックベースのマージソートと同じ方法で実行できます。ファイル内の範囲の数に等しいカウンターを各ファイルに関連付けてプッシュします。スタック上の各新しいファイル。スタックの一番上にあるファイルのカウンターが前のファイル以上の場合、ファイルを新しいファイルにマージします。カウンターは、マージされたファイル内の範囲の数です。

于 2011-01-15T18:39:55.093 に答える