如果我有一個 10K 元素的串列，并且我想隨機遍歷所有元素，是否有一種演算法可以讓我隨機訪問每個元素，而不僅僅是先隨機排序它們？
換句話說，這并不理想：
const sorted = list
.map(v => [math.random(), v])
.sort((a,b) => a[0]- b[0]);
避免排序呼叫和映射呼叫會很好。我唯一的想法是將所有內容存盤在哈希圖中并以某種方式隨機訪問哈希鍵？雖然這只是回到同樣的問題，但 afaict。
uj5u.com熱心網友回復：
剛剛玩過這個游戲并意識到Fisher-Yates shuffle “在線”效果很好。例如，如果您有一個大串列，則無需在開始迭代專案之前花時間對整個事物進行洗牌，或者等效地，您可能只需要大串列中的幾個專案。
我沒有在問題中看到語言標簽，所以我會選擇 Python。
from random import randint
def iterrand(a):
"""Iterate over items of a list in a random order.
Additional items can be .append()ed arbitrarily at runtime."""
for i, ai in enumerate(a):
j = randint(i, len(a)-1)
a[i], a[j] = a[j], ai
yield a[i]
這是串列長度的 O(n) 并且通過允許.append()s (Python 中的 O(1)) 可以在后臺構建串列。
一個示例用法是：
l = [0, 1, 2]
for i, v in enumerate(iterrand(l)):
print(f"{i:3}: {v:<5} {l}")
if v < 4:
l.append(randint(1, 9))
這可能會產生如下輸出：
0: 2 [2, 1, 0]
1: 3 [2, 3, 0, 1]
2: 1 [2, 3, 1, 1, 0]
3: 0 [2, 3, 1, 0, 1, 3]
4: 1 [2, 3, 1, 0, 1, 3, 7]
5: 7 [2, 3, 1, 0, 1, 7, 7, 3]
6: 7 [2, 3, 1, 0, 1, 7, 7, 3]
7: 3 [2, 3, 1, 0, 1, 7, 7, 3]
8: 2 [2, 3, 1, 0, 1, 7, 7, 3, 2]
9: 3 [2, 3, 1, 0, 1, 7, 7, 3, 2, 3]
10: 2 [2, 3, 1, 0, 1, 7, 7, 3, 2, 3, 2]
11: 7 [2, 3, 1, 0, 1, 7, 7, 3, 2, 3, 2, 7]
更新：為了測驗正確性，我會這樣做：
# trivial tests
assert list(iterrand([])) == []
assert list(iterrand([1])) == [1]
# bigger uniformity test
from collections import Counter
# tally 1M draws
c = Counter()
for _ in range(10**6):
c[tuple(iterrand([1, 2, 3, 4, 5]))] = 1
# ensure it's uniform
assert all(7945 < v < 8728 for v in c.values())
# above constants calculated in R via:
# k<-120;p<-0.001/k;qbinom(c(p,1-p), 1e6, 1/k))
uj5u.com熱心網友回復：
Fisher-Yates 應該像其他人一樣做得好，這篇文章非常好： https ://medium.com/@oldwestaction/randomness-is-hard-e085decbcbb2
相關的 JS 代碼非常短小精悍：
const fisherYatesShuffle = (deck) => {
for (let i = deck.length - 1; i >= 0; i--) {
const swapIndex = Math.floor(Math.random() * (i 1));
[deck[i], deck[swapIndex]] = [deck[swapIndex], deck[i]];
}
return deck
}
要隨時產生結果，因此您不必遍歷串列兩次，請使用生成器函式，如下所示：
const fisherYatesShuffle = function* (deck) {
for (let i = deck.length - 1; i >= 0; i--) {
const swapIndex = Math.floor(Math.random() * (i 1)); // * use ;
[deck[i], deck[swapIndex]] = [deck[swapIndex], deck[i]];
yield deck[i];
}
};
（注意，當下一行是括號符號時，不要忘記其中的一些分號）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/530676.html
標籤：排序随机的随机访问
下一篇：如何配對串列中的值