乱数の長いリスト (おそらく数千) を格納し、それらを効率的に取得するアルゴリズムを探しています。通常、ソリューションではデータの並べ替えは必要ありません。つまり、数値は生成されたときに保存されます。また、必要なストレージ スペースは、そのような数値の配列/ハッシュに必要なスペースよりも小さくする必要があります。新しい番号をリストに追加できます。
3 に答える
2
疑似乱数ジェネレーターのいずれかを実装してみてください。必要なのは、初期シード (ランダムである必要があります) を保存することだけです。しかし、もちろん、疑似乱数シーケンスの任意の要素へのアクセスには複雑さ O(N) があります。それは単なる時空間のトレードオフです。
于 2012-10-08T08:46:14.430 に答える
1
@Stemmは、シードを疑似乱数ジェネレーター（prng）に格納するという非常に優れたアイデアを持っています。番号を取得するためにprngを呼び出す回数を知るために、番号のカウントも必要になります。
シードにアクセスできない場合、または番号がランダムである場合は、別のオプションがある可能性があります。数値が整数で、それほど大きくなく、重複がないことがわかっている場合は、それらをビットとして格納することを検討してください。したがって、たとえば、最長の値が2バイト整数に収まる場合、その値は1ビットを使用して格納できます。いくつかの例：
0=1。
4=10000バイナリまたは1016進数。
10=10000000000バイナリ。
最大値が65535の場合、これは16ビットの符号なし整数内に収まる最大値であり、すべての値を保持するメモリの量は65536/8=8192バイトとして計算できます。Javaを使用している場合は、java.util.BitSetまたはjava.math.BigIntegerクラスを参照してください。
于 2012-10-08T17:48:45.443 に答える
0
数字が本当にランダムである場合、またはシードがわからない十分に優れた RNG からのものである場合でも、それらを圧縮することは不可能です。特定の圧縮方式では、運が良ければ圧縮可能な数値のセットを引き出すことができますが、そのようなイベントが発生する確率は常に非常に小さいです。
これは、counting 引数 (鳩の穴引数とも呼ばれます) に由来しnますn。一般的な圧縮スキームは、入力文字列の小さなサブセットのみが可能性があるという事実を利用して、これを回避します。この小さなセット (英語のテキスト、実行可能なバイナリなど) は、短い文字列で完全にエンコード可能です。
完全にランダムな文字列にはそのようなバックドアがないため、意味のある圧縮は不可能です。
于 2012-10-08T09:48:41.313 に答える