DIV CSS 佈局教程網

JavaScript 陣列亂序:Fisher-Yates 為何比 sort 快十倍
編輯:關於JavaScript     

陣列亂序就是把元素的排列順序打亂。最常見的寫法是給 sort 傳一個隨機比較函式:

arr.sort(function(a, b){ return Math.random() > .5 ? -1 : 1; });

這種寫法很直觀,但效率不佳。實測打亂 10000 個元素,在 Firefox 下約耗時 35ms。

更好的做法

if (!Array.prototype.shuffle) {
  Array.prototype.shuffle = function() {
    for (var j, x, i = this.length; i; j = parseInt(Math.random() * i), x = this[--i], this[i] = this[j], this[j] = x);
    return this;
  };
}
arr.shuffle();

同樣打亂 10000 個元素,這個版本只需 7、8 毫秒。把元素增加到 100000 來測試,sort 版本耗時 500ms 以上,shuffle 版本約 40ms,差距接近十倍。

為什麼 sort 版本又慢又不對

效能面:sort 需要呼叫比較函式 O(n log n) 次,而每次比較都重新呼叫一次 Math.random()。更糟的是,比較函式必須是「一致的」——同樣的兩個元素每次比較都該回傳相同結果。隨機比較函式違反了這個契約,會讓排序演算法的分區邏輯失效,某些引擎甚至可能進入極端分支。

正確性面:即使不管效能,隨機比較函式產生的排列分布也是不均勻的。某些排列出現的機率會明顯高於其他,這是數學上可證的結果。

那個沒有大括號的 for 迴圈

原始程式裡的 for(var j, x, i = this.length; i; j = parseInt(Math.random() * i), x = this[--i], this[i] = this[j], this[j] = x); 看起來很詭異——只有 for(...),後面直接接分號,沒有大括號。這是合法的 JavaScript:單一陳述式的位置放一個空陳述式(就是那個分號),而所有工作都在 for 的第三段(更新運算式)裡完成,用逗號運算子把四個動作串起來。

它其實在做 Fisher-Yates 洗牌演算法:從尾端往前,每次取一個 0 到 i 之間的隨機索引 j,把 this[i] 與 this[j] 互換。

寫成可讀的形式

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

用解構賦值會更短:

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

注意隨機範圍是 i + 1 而非 i。原版用 parseInt(Math.random() * i) 搭配 --i,因為 i 先被遞減,所以範圍剛好正確;自己改寫時若不留意這個細節,會讓最後一個元素永遠沒有機會被選中,分佈就不均勻了。

幾個實務提醒

這個函式會改動原陣列。若需要保留原陣列,先複製:shuffle(arr.slice())。

擴充 Array.prototype 也可能與其他函式庫衝突,特別是它們也用 for...in 遍歷陣列時。匯出成獨立函式是更安全的選擇。

若需要可重現的結果(例如測試),把 Math.random 換成帶种子的偽隨機數生成器(PRNG)即可,Fisher-Yates 演算法本身與隨機來源無關。

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