DIV CSS 佈局教程網

詳解 JS 陣列的完全隨機排列:為何 sort 洗牌是錯的
編輯:關於JavaScript     

Array.prototype.sort 常被誤用來做陣列隨機排列。近期在前端挑戰專案中實作 blackjack 遊戲時,就發現不少同學直接用 sort 來洗牌。這其實是個徹底錯誤的做法。

常見的錯誤洗牌寫法

 function shuffle(arr){ return arr.sort(function(){ return Math.random() - 0.5; }); }

這段程式看似巧妙地利用了 sort,但問題非常嚴重。

如何證明它是錯的

設計一個可驗證的測試:如果這個隨機演算法正確,那麼把它作用於 [0,1,2,3,4,5,6,7,8,9],每個數字出現在每一個位置上的機率應該相等。因此重複洗牌足夠多次後,把每次結果在該位相加再取平均,每個位置的平均值都應該趨近 (0+9)/2 = 4.5,且測試次數越多越明顯。

 var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0]; var t = 10000; for(var i = 0; i < t; i++){ var sorted = shuffle(arr.slice(0)); sorted.forEach(function(o,i){ res[i] += o; }); } res = res.map(function(o){ return o / t; }); console.log(res); 

在 Chrome 中跑一下會發現,結果並未均勻分布,越往後的位置平均值越大,也就是越大的數字出現在越後面的機率越高。

要理解原因,得先知道 sort 到底做了什麼。ECMAScript 並未規定 Array.prototype.sort 必須採用哪一種排序演算法,而任何排序都離不開兩兩比較與交換,其效率與比較次數直接相關。

最基礎的氣泡排序與插入排序,原版都會比較 n(n-1)/2 次,也就是任意兩個位置都恰好比較過一次。在這種前提下,若每次比較都有 50% 機率交換,結果會均勻嗎?

 function bubbleSort(arr, compare){ var len = arr.length; for(var i = 0; i < len - 1; i++){ for(var j = 0; j < len - 1 - i; j++){ var k = j + 1; if(compare(arr[j], arr[k]) > 0){ var tmp = arr[j]; arr[j] = arr[k]; arr[k] = tmp; } } } return arr; } function shuffle(arr){ return bubbleSort(arr, function(){ return Math.random() - 0.5; }); } var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0]; var t = 10000; for(var i = 0; i < t; i++){ var sorted = shuffle(arr.slice(0)); sorted.forEach(function(o,i){ res[i] += o; }); } res = res.map(function(o){ return o / t; }); console.log(res); 

結果依然不均勻,平均值越往後越大。(早期版本因為忘了複製原陣列而誤判為均勻,此處已更正。)

原因不難推敲:氣泡排序只會把較小的元素往前換,越靠後的元素要「冒」到前面的機率越低(每次只有 50% 機會),而原始陣列是遞增的,所以後段的大數留在後面的比例自然偏高。

換成插入排序看看:

 function insertionSort(arr, compare){ var len = arr.length; for(var i = 0; i < len; i++){ for(var j = i + 1; j < len; j++){ if(compare(arr[i], arr[j]) > 0){ var tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } } return arr; } function shuffle(arr){ return insertionSort(arr, function(){ return Math.random() - 0.5; }); } var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0]; var t = 10000; for(var i = 0; i < t; i++){ var sorted = shuffle(arr.slice(0)); sorted.forEach(function(o,i){ res[i] += o; }); } res = res.map(function(o){ return o / t; }); console.log(res); 

這次是後段的大數往前換,因此結果與氣泡排序相反:平均值越往後越小。

可見即使是「兩兩都比一次」的排序,隨機分布的偏差也相當明顯。而大多數排序演算法的時間複雜度介於 O(n) 到 O(n²) 之間,比較次數遠小於 n(n-1)/2,意味著有些元素之間根本沒機會比較,自然也沒有隨機交換的可能。

再換成快速排序:

 function quickSort(arr, compare){ arr = arr.slice(0); if(arr.length <= 1) return arr; var mid = arr[0], rest = arr.slice(1); var left = [], right = []; for(var i = 0; i < rest.length; i++){ if(compare(rest[i], mid) > 0){ right.push(rest[i]); }else{ left.push(rest[i]); } } return quickSort(left, compare).concat([mid]) .concat(quickSort(right, compare)); } function shuffle(arr){ return quickSort(arr, function(){ return Math.random() - 0.5; }); } var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0]; var t = 10000; for(var i = 0; i < t; i++){ var sorted = shuffle(arr.slice(0)); sorted.forEach(function(o,i){ res[i] += o; }); } res = res.map(function(o){ return o / t; }); console.log(res); 

快速排序不做兩兩比較,分布同樣不隨機。

結論很清楚:用 sort 搭配隨機比較函式來洗牌,結果取決於底層排序實作,用 JavaScript 內建的排序則幾乎必然不是完全隨機的。

經典的隨機排列(Fisher–Yates)

所有空間複雜度 O(1) 的排序演算法,時間複雜度都在 O(n log n) 到 O(n²) 之間,所以就算結果正確,用排序來洗牌也太慢。真正的經典做法是 O(n) 的:

 function shuffle(arr){ var len = arr.length; for(var i = 0; i < len - 1; i++){ var idx = Math.floor(Math.random() * (len - i)); var temp = arr[idx]; arr[idx] = arr[len - i - 1]; arr[len - i -1] = temp; } return arr; }

每一次迴圈從前 len - i 個元素中隨機挑一個位置,與第 len - i 個元素交換,直到 i = len - 1 為止。

同樣用前面的測試驗證:

 function shuffle(arr){ var len = arr.length; for(var i = 0; i < len - 1; i++){ var idx = Math.floor(Math.random() * (len - i)); var temp = arr[idx]; arr[idx] = arr[len - i - 1]; arr[len - i -1] = temp; } return arr; } var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0]; var t = 10000; for(var i = 0; i < t; i++){ var sorted = shuffle(arr.slice(0)); sorted.forEach(function(o,i){ res[i] += o; }); } res = res.map(function(o){ return o / t; }); console.log(res); 

這次各位置的平均值都落在 4.5 附近。不過要提醒的是,我們只驗證了平均值,而平均值接近只是均勻分布的必要條件而非充分條件。真正的隨機性可以從數學上證明。

用數學歸納法證明隨機性

對 n 個數進行隨機:

1. 先看 n = 2。依演算法,兩個數有 1/2 機率交換、1/2 機率不交換,因此每個元素出現在每個位置上的機率都是 1/2,符合要求。

2. 假設對 i 個數(i ≥ 2),演算法已滿足隨機性,即每個數出現在 i 個位置中任一位置的機率都是 1/i。

3. 對於 i + 1 個數,第一次迴圈時每個數都有 1/(i+1) 的機率被換到最末尾,因此出現在末位的機率是 1/(i+1)。同時每個數也有 i/(i+1) 的機率沒被換走;若沒被換走,從第二次迴圈起就退化為 i 個數的隨機問題,依假設出現在前 i 個位置中任一位置的機率是 1/i。兩者相乘:i/(i+1) × 1/i = 1/(i+1),同樣是 1/(i+1)。

綜合 1、2、3,對任意 n ≥ 2,每個元素出現在 n 個位置中任一位置的機率都是 1/n,隨機性得證。

總結

一個好的演算法要同時滿足結果正確與效率。很遺憾,用 Array.prototype.sort 洗牌這兩點都不成立。需要類似洗牌的功能時,還是應該採用經典的 Fisher–Yates 洗牌演算法,它既有完全隨機性,效率也高。

除了收穫這個演算法,更值得帶走的是這種動手驗證、用數學工具支撐結論的思路,以及那些我們學過卻常常忘記的知識(比如數學歸納法)。

以上就是本文的全部內容,希望對你的學習或工作有所幫助。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved