獲取10000+獨特的隨機數（性能）

可能重複：
Create Random Number Sequence with No Repeats 獲取10000+獨特的隨機數（性能）

我想編寫只使用數字作爲短字符串的URL縮短。

我不想數了，我希望下一個新號碼是隨機的（或僞隨機）。

在第一個想到的算法則是這樣的（僞代碼）：

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

datastore.store(number, url)

這種實現的問題是：由於數據存儲包含更多的數字，更有可能的是，循環將執行它多次。性能會隨着時間的推移而降低。

沒有更好的方法來獲得一個尚未使用的隨機數字嗎？

來源

2011-11-10 leifg

相關：http://stackoverflow.com/questions/693880/create-random-number-sequence-with-no-repeats – Thilo

看看[唯一隨機數在O（1）？]（http：/ /堆棧溢出。com/questions/196017/unique-random-numbers-in-o1） – Gumbo

另請注意，如果您使用的是短數字而不是較長的UUID，則這些數字會變得可以猜測，即人們可以看到其他人只通過嘗試幾次數字。這可能也可能不是問題。 – Thilo

一些相關的問題：# 2394246，# 54059，# 158716，# 196017和# 1608181。

正確的方法取決於您將生成多少個數字，以及是否需要實時性能。如果您只繪製一個範圍內可用數量的一小部分，則代碼片段的每個數字的平均時間爲O（1），稍後每個數字的時間略有增加，但仍爲O（1）。例如，參見問題#1608181 answer，其中我顯示使用這樣的代碼從大於2*k的數字範圍獲得k號碼是O(k)。（這個答案也有C代碼從一系列N個數的生成M個數字，在O（M），當時間M<N/2，並解釋如何在M>=N/2。使用它的O（M）時間）

如果你想O（1）性能與硬性時間限制，您可以使用剛剛提到的程序預加載數組，或者可以洗牌整個範圍的整數，如賈斯汀所述。在預處理之後，每個訪問都是O（1）。 Buf，如果你知道你不會超過從1 ... 10000範圍內抽取3000個數字，並且沒有硬性時間限制，那麼你的代碼將平均以O（1） k通過遞減爲0.3^k; 即，最壞的情況是1次通過的概率爲70％，2次爲21％，3次爲6％，4次爲2％，5次爲0.6％，等等。

來源

2011-11-10 17:16:32

1）填充順序值

2）shuffle陣列

來源

2011-11-10 11:10:49 justin

使用的加密的陣列。由於加密是可逆的，唯一的輸入產生獨特的輸出。對於64位數字，請使用64位塊大小的密碼。對於較小的塊大小，例如32位或16位，請查看Hasty Pudding Cypher。無論您需要什麼塊大小，只需對數字0,1,2，...（在適當的塊大小）進行加密，就可以根據需要生成儘可能多的獨特非連續數字。

來源

2011-11-10 13:56:31 rossum

如果隨機數必須是唯一的並且範圍爲0到10000，如問題所示，那麼加密不能解決問題。 –

如果您仔細閱讀了Hasty Pudding密碼的描述，那麼您會看到它的確如此。「Hasty Pudding cipher也可以用來加密一個範圍內的值，這些值不會轉換爲具有整數位的字符串;例如，它可以通過產生從0到N的另一個數字來加密從0到N的數字。通過使用能夠將輸入作爲位串處理的最小的解密器，並將其作爲位串應用於輸入，直到輸出處於適當的範圍內。 – rossum

獲取10000+獨特的隨機數（性能）

回答

相關問題