在這個執行緒中，我們看到了這個簡單而漂亮的演算法來對陣列進行洗牌：
function shuffle<T>(array: T[]): T[] {
return array.sort(() => Math.random() - 0.5);
}
我們可以看到評論說這個演算法有偏見。但是我做了一個簡單的腳本來創建一個索引的經驗概率分布，即陣列的最后一個元素在 shuffle 后結束：
function shuffle(array) {
return array.sort(() => Math.random() - 0.5);
}
function generateDistribution(iterations = 10_000, arrayLength = 10) {
const testArray = Array(arrayLength - 1).fill("test");
const testTarget = "target";
testArray.push(testTarget);
const results = {};
for (let index = 0; index < iterations; index ) {
countTargetPosition();
}
return generateResult();
function countTargetPosition() {
const shuffled = shuffle(testArray);
shuffled.forEach((value, index) => {
if (value === testTarget) {
results[index] = results[index] 1 || 1;
}
});
}
function generateResult() {
return Object.entries(results).map(([index, count]) => {
return {
[index]: count / iterations,
};
});
}
}
const result = generateDistribution()
document.write(`<h1>Result</h1>`)
document.write(JSON.stringify(result))我們期望無偏演算法具有均勻分布，結果非常接近，即使對于具有 100 個元素的陣列也是如此。為什么這個演算法有偏見呢？
uj5u.com熱心網友回復：
JavaScript 沒有為 指定特定的演算法sort，并且根據所使用的特定排序演算法，這種改組演算法可能會給出非常有偏差的結果。下面，我將描述一些簡單的、眾所周知的排序演算法，這些演算法會給出非常有偏見的結果；我證明 Firefox 和 Chrome 對于長度為 4 的陣列都給出了非常有偏差的結果；我對為什么任何排序演算法都會給出有偏見的結果給出了一個一般性的論據（盡管不一定像這些明確的例子那樣有偏見）。
示例 #1 -選擇排序。在選擇排序中，我們首先找到最小的元素并將其放在索引 0 處，然后找到第二小的元素并將其放在索引 1 處，以此類推。需要注意的重要一點是，使用比較函式() => Math.random() - 0.5，比較的每個引數都有相等的機會被視為“較少”。因此，如果您通過遍歷陣列并將每個元素與之前最少的元素進行比較來找到最少的元素，那么您有 50% 的機會認為最后一個元素是最少的，25% 的機會您會認為倒數第二個元素最少，有 12.5% 的機會認為倒數第三個元素最少，依此類推，因此給出了哪個元素先行的偏向分布。
示例 2 —插入排序。在插入排序中，我們通過依次取出每個元素并將其插入到該排序部分的正確位置（將所有較大的元素移動一個以為其騰出空間）來構建陣列的“已排序”部分。這意味著最后一個元素有 50% 的機會被認為是最少的，有 25% 的機會被認為是倒數第二，有 12.5% 的機會被認為是倒數第三等。
示例 #3 和 #4 — Firefox 和 Chrome 用于四元素陣列的任何內容。
現在，實際上，我不希望 的任何實作完全sort使用選擇排序或插入排序，因為還有其他演算法對于大輸入更有效。但是復雜的現代排序演算法，例如Timsort，結合了多種不同的排序演算法，根據輸入（或部分輸入，因為它們可以以復雜的方式組合這些演算法）的大小和特征在它們之間進行自適應選擇。因此，作為一項實驗，我在陣列上嘗試了這種 shuffle 演算法——一個足夠短的陣列，似乎實作可能只對整個陣列使用插入排序。[1, 2, 3, 4]sort
這是我使用的代碼：
const counts = {};
for (let i = 0; i < 1_000_000; i) {
const permutation = [1, 2, 3, 4].sort(() => Math.random() - 0.5).join('');
counts[permutation] = (counts[permutation]||0) 1;
}
const result = [];
for (let permutation in counts) {
result.push(permutation ': ' counts[permutation]);
}
result.join('\n')
我在 Firefox 和 Chrome 中都試過這個。
在 Firefox 中，我得到了這樣的結果：
1234: 125747
1243: 62365
1324: 62299
1342: 31003
1423: 31320
1432: 15635
2134: 125380
2143: 62216
2314: 62615
2341: 31255
2413: 31509
2431: 15608
3124: 62377
3142: 31166
3214: 62194
3241: 31293
3412: 15631
3421: 15782
4123: 31056
4132: 15672
4213: 31231
4231: 15319
4312: 15727
4321: 15600
這與我對插入排序的期望不符，所以它必須做一些不同的事情，但無論如何，它顯示出非常明顯的偏見。有些排列發生的時間為 1/64（百萬分之 15,625 次，加上/減去隨機噪聲），有些發生的時間為 1/32 (31,250)，有些發生的時間為 1/16 (62,500)，還有一些發生 1/8 的時間 (125,000)；所以一些排列是其他排列的八倍。
在 Chrome 中，我得到了這樣的結果：
1234: 187029
1243: 62380
1324: 15409
1342: 15679
1423: 62476
1432: 15368
2134: 31280
2143: 31291
2314: 15683
2341: 15482
2413: 31482
2431: 15732
3124: 15786
3142: 15692
3214: 47186
3241: 47092
3412: 15509
3421: 46600
4123: 62825
4132: 15595
4213: 31091
4231: 15763
4312: 15624
4321: 171946
這也是不符合我期望從插入排序想到的，就是有點比Firefox中的分布更加復雜（我想我看到一些3/16份（187,500），并在那里3 / 64ths（46875）？），但實際上偏差更大，最常見和最不常見的排列之間相差十二倍。
Example #5 — any deterministic sorting algorithm. I've given various examples above of fairly extreme biases; but really, any sorting algorithm would be expected to produce some bias, because if the algorithm does worst-case k comparisons on an array of length n, and each comparison has a 50–50 split, then the probability of any given permutation has to be a multiple of 1/2k, whereas an unbiased shuffler has to give each permutation the probability 1/n!, which won't be a multiple of 1/2k if n ≥ 3 (because then n! will be a multiple of 3).
That said, I should acknowledge that these biases might be small enough that they don't matter; after all, even 1.0 / 3.0 doesn't compute exactly 1/3, but rather, rounds it to a binary approximation. Of more direct relevance, a typical implementation of Math.random() holds 64 or 128 bits of internal state, which means that it doesn't even have 21! or 35! distinct internal states, which means that no algorithm that uses Math.random() to shuffle an array of 21 or 35 or more elements can possibly produce each permutation with nonzero probability. So I suppose that some bias is inevitable!
即使您使用的sort實作提供了您認為足夠好的結果，也沒有理由這樣做，因為Fisher–Yates shuffle編碼簡單，并且比任何基于比較的排序演算法都快。
但是我做了一個簡單的腳本來創建一個索引的經驗概率分布，即陣列的最后一個元素在 shuffle 后結束：[…]
請注意，可能存在更微妙的偏差，即使最后一個元素在任何位置結束的可能性相同，也并非所有排列都具有相同的可能性。即使sort實作是固定的，在依賴此改組演算法給出無偏見的結果之前，您也需要進行更徹底的分析（可能包括查看其源代碼）。
uj5u.com熱心網友回復：
原因是比較結果是不連貫的，正如 ruakh 詳細說明的那樣，這可能會使某些排序演算法產生偏差。
正確的解決方案是將隨機鍵與元素相關聯，然后對鍵進行排序。但這需要 O(n) 額外的空間。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/362062.html
標籤：javascript 数组 算法 随机的 洗牌