DIV CSS 佈局教程網

用 sort 隨機打亂陣列:一行程式碼的原理與陷阱
編輯:關於JavaScript     

要把陣列洗牌,流傳最廣的寫法只有一行:

var arr = [];
for(var i = 0; i < 100; i++){
  arr[i] = i;
}
arr.sort(function(){ return 0.5 - Math.random() })
var str = arr.join();
alert(str);

逐段說明

var arr = [];   // 建立陣列,這是推薦寫法,而非 var arr = new Array();
for(var i = 0; i < 100; i++){ arr[i] = i; }   // 循環賦值

關鍵在這一句:

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

sort 會反覆從陣列中挑兩個元素比較,依比較函式的回傳值決定要不要交換:回傳 0 表示兩者相等、位置不變;回傳小於 0 表示前者排前面;回傳大於 0 表示前者排後面。然後拿較大的那個跟下一個繼續比,這樣一輪輪進行下去。

而 0.5 - Math.random() 的結果必定落在 -0.5 到 0.5 之間,隨機為正或為負,於是每次比較都在「交換」與「不交換」之間擲硬幣,陣列看起來就被打亂了。

但這其實是個有偏的洗牌

這段寫法雖然簡短、跑起來也夠快,卻不是均勻隨機。原因在於比較函式不是一致的:同一組元素在不同階段比較,可能得到不同結果,這違反了排序演算法對「比較結果必須可傳遞」的假設。實測會發現某些排列出現的機率明顯高於其他,元素越多偏差越明顯。

如果要真正均勻的洗牌,應該用 Fisher–Yates 演算法——從後往前,每一輪把當前元素與前面(含自己)隨機挑的一個位置交換:

function shuffle(arr){
  for (var i = arr.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  return arr;
}

它只跑一趟、時間複雜度 O(n),而且每一種排列出現的機率嚴格相等。若是需要密碼學强度的隨機(例如抽獎、產生 token),把 Math.random() 換成 crypto.getRandomValues(),因為前者並非安全隨機源。

所以那行經典寫法適合成不了大局的小場合;正式用途請用 Fisher–Yates。

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