10000 +ユニークな乱数（パフォーマンス）

Question

可能性の重複取得：
Create Random Number Sequence with No Repeats

を私は短い文字列として数字を使用してURL短縮サービスを書きたいと思います。

カウントダウンしたくないので、次の新しい番号をランダム（または擬似ランダム）にします。最初に考えたアルゴリズムで

は次のようになります（擬似コード）：

do 
{ 
number = random(0,10000) 
} 
while (datastore.contains(number)) 

datastore.store(number, url) 

この実装に問題がある：データストアがより多くの数字が含まれているとして、より多くの可能性が高いが、それは、ループが実行されますされていること複数回。パフォーマンスは時間の経過と共に減少します。

まだ使用されていない乱数を取得するより良い方法はありませんか？

Answer 1

いくつかの関連質問：# 2394246、# 54059、# 158716、# 196017、および# 1608181。

適切な方法は、リアルタイムパフォーマンスが必要な場合に生成する数値の数によって異なります。ある範囲内で利用可能な数字のうち、ごく一部しか使用しない場合、コードスニペットの1つの数字の平均時間はO（1）ですが、それ以降の数字はわずかに増加しますがO（1）です。たとえば、質問#1608181 answerを参照してください。kの数字が2*k以上の範囲の数字をO(k)とすることを示しています。 （その答えは、M<N/2のO（M）時間にN個の数字の範囲からM個の数字を生成するCコードを持ち、M>=N/2のときO（M）時間に使用する方法を説明しています）

O（1）のパフォーマンスを厳しい制限時間に制限したい場合は、前述のプログラムを使用して配列をあらかじめロードするか、Justinが述べたように整数の範囲全体をシャッフルすることができます。その前処理の後、各アクセスはO（1）です。あなたがあなたの1 ... 10000の範囲から3000の数字を上回らないことを知っていて、厳しい制限がないならば、あなたが持つコードは平均でO（1）時間に確率で実行されますkの値は0.3^kのように減少します。例えば、の場合、、最悪で約70％の確率で1パス、21％が2,3,6％が4,3％、5が0.6％などである。

Answer 2

1）連続した値

2の配列を埋める）shuffleアレイ

Answer 3

暗号化を使用します。暗号化は可逆的なので、固有の入力は固有の出力を生成します。 64ビット数の場合は、64ビットブロックサイズのサイファーを使用します。 32ビットまたは16ビットなどのより小さいブロックサイズの場合は、Hasty Pudding Cypherをご覧ください。

必要なブロックサイズは何でも、0,1,2、...（適切なブロックサイズで）を暗号化するだけで、必要な数だけ一意の非連続番号が生成されます。