2

連続する整数値のセットと、それに対応する非連続値のセットがあります。次に例を示します。

0 -> 22
1 -> 712
2 -> 53
3 -> 12323
...

等々。

項目の量が非常に多い (約 10^9...10^10) ため、単純な配列だけを使用することはできません。

中程度のメモリ要件で最初の値から別の値に高速にマッピングできるデータ構造はありますか? 例えば：

ret = map(0); // returns 22
ret = map(3); // returns 12323

編集: このセットの値は実際には疑似乱数ジェネレーターを使用して生成されるため、特定の分布を示唆することはできません。質問は - メモリ要件を下げることは可能ですか (検索速度が犠牲になる可能性があります)? 「完全なハッシュ」のようなものを使用することを意味します-そのような「完全なハッシュ」を生成するのに必要な時間は問題ではありません。

4

4 に答える 4

2

範囲が連続しているため、明らかな解決策は、値を連続した int[] に格納することです。値 i はarr[i]です。PRNG によって生成された値として、それ以上の圧縮を適用することは困難です。

時間とスペースを交換する別の解決策は、RNG のシードを保存し、その場で再計算することです。このアプローチは、中間シードを保存することで、時間の経過とともに改善され、空間的に悪化する可能性があります。つまり、キー 1000、2000 などのシードです。

于 2012-08-17T12:52:55.603 に答える
0

さて、その意図は、より少ないメモリ使用量と速度を交換することです。

配列を満たすある種のループがあると想像してください。

int array[intendedArraySize];

seed = 3;
for (size_t z = 0; z < intendedArraySize; z++)
{
     array[z] = some_int_psn_generator(seed);
}

その後、値を表示できます。

for (size_t z = 0; z < intendedArraySize; z++)
{
    std::cout << z << " " << array[z] << std::endl;
}

それが実際に当てはまる場合は、毎回値を再計算するだけで、配列を完全に破棄することを検討してください。

for (size_t z = 0; z < intendedArraySize; z++)
{
    std::cout << z << " " << some_int_psn_generator(z) << std::endl;
}
于 2012-08-17T15:35:23.270 に答える
0

各値に必要なビット数を正確に使用することで、スペースを節約できる場合があります。たとえば、値が 24 ビットのみの場合、32 ビット整数よりも 1 バイト節約できます。とはいえ、節約できるメモリは限られています。

64 ビット マシンではmmap()、ファイルをメモリ アドレスに変換することが可能であり、ディスク ストレージを使用することで、パフォーマンスを犠牲にして物理メモリの制限を超えることができます。

しかし、疑似乱数ジェネレーターを使用して値を生成することについて言及したので、特定のインデックスの RNG シードを格納し、必要に応じて残りの値を計算するだけではどうですか? たとえば、インデックス 0、100、200、... のシードを格納し、100 の RNG を再シードしてジェネレータ関数を 3 回呼び出すことで、たとえば 102 を計算できます。

このようなアプローチでは、必要なメモリが大幅に (この場合は 100) 削減され、クエリをまとめたりキャッシュしたりすることでパフォーマンス コストを削減できます。

于 2012-08-17T12:52:06.850 に答える
0

関数の範囲が疑似乱数ジェネレーターによって順番に生成される数値のセットである場合、シリーズを圧縮して、シーケンスと開始前の PRNG の状態を生成するコードに圧縮できます。たとえば、pi の 10 進展開を構成する (無限の) 一連の数字は、その一連を生成するコードに簡単に (技術的には無限に) 圧縮されます。あなたのシリーズは、ほぼ同じものの例と見なすことができます.

したがって、シリーズの最後の要素を取得するために長時間待機する場合は、シリーズをデータ構造ではなく関数から書き出すことで、非常に優れた圧縮を実現できます。これは、時間と空間のトレードオフ スペクトルの一端にあります。

スペクトルの反対側には、すべての数値の配列があります。O(1)これは多くのスペースを使用しますが、セット内の任意の要素に非常にすばやく ( ) アクセスできます。これはさまざまな理由であなたには魅力的ではないようですが、配列よりも賢いデータ構造が多くのスペースの節約、さらに言えば時間の節約になるかどうかはわかりません。

私が見る明らかな解決策の1つは、PRNGの一連の中間状態を間隔を置いて保存することです。そのため、「データ」構造は次のようになります。

ret(0) = prng(seed, other_parameters, ...)
ret(10^5-1)  = prng(seed', other_parameters, ...)
ret(2*(10^5)-1) = prng(seed'', other_parameters, ...)

次に、要素 9765 を取得するには、(PRNG の状態) を読み取り、ret(0)その後 9765 番目の疑似乱数を生成します。

于 2012-08-17T12:52:40.770 に答える