DIV CSS 佈局教程網

JS 隨機產生不重複數字的實作與優化
編輯:關於JavaScript     

「隨機抽 N 個不重複的數字」是很常遇到的需求:抽獎名單、隨機出題、打亂順序等等。直覺做法是邊抽邊檢查有沒有重複,但這個做法的效率其實很差。

直覺寫法

// 用來存放已產生的隨機數
var array = [];

// 迴圈直到湊滿 10 個
while (array.length < 10){
    generateRandom(10);
}

// 逐一輸出
for (var i = 0; i < array.length; i++){
    alert(array[i]);
}

// 產生隨機數並去重
function generateRandom(count){
    var rand = parseInt(Math.random() * count);
    for (var i = 0; i < array.length; i++){
        if (array[i] == rand){
            return false;    // 已存在,放棄這次
        }
    }
    array.push(rand);
}

原範例用 for(var i = 0; ; i++) 這種刻意留空的寫法當無限迴圈,改成 while (array.length < 10) 語意更清楚,也不會有未使用變數。

這個做法的問題

每次產生新數字,都要跟已產生的全部比對一次,整體是 O(n²)。更糟的是當 count 接近 array.length 時,碰撞機率急遽升高,迴圈可能空轉很多次。舉例來說,要從 1 到 10 抽 9 個不重複數字,最後一個的平均嘗試次數會是 10 次;若不小心寫成抽 10 個,parseInt(Math.random()*10) 有可能一直取不到剩下那一個,迴圈就永遠停不下來。

另外 parseInt(Math.random() * count) 在多數瀏覽器可正常運作,但 parseInt 少了第二個基数參數是不良習慣,改用 Math.floor() 更明確。

優化方案一:Set 去重

function getRandomUnique(count, max){
    var set = new Set();
    while (set.size < count){
        set.add(Math.floor(Math.random() * max));
    }
    return Array.from(set);
}

用 Set 取代陣列,加入與查詢都是 O(1),省掉了內層的線性搜尋。前提是 count <= max,否則一樣會無限迴圈,記得加上防呆:

if (count > max) throw new RangeError('抽出的數量不能超過範圍大小');

優化方案二:Fisher-Yates 洗牌(推薦)

如果 count 相對於 max 不算太小,最有效率的做法是「先洗牌再取前 N 個」,時間複雜度固定 O(max),完全沒有碰撞問題:

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

function getRandomUnique(count, max){
    var pool = [];
    for (var i = 1; i <= max; i++) pool.push(i);
    return shuffle(pool).slice(0, count);
}

getRandomUnique(5, 10);   // 例如 [7, 2, 9, 1, 5]

Fisher-Yates 是公認最公平的洗牌演算法,每個排列組合出現的機率完全相同。用它來抽不重複隨機數,速度快、結果均勻,也不會有停不下來的風險。

小結

抽少量、範圍大:用 Set 湊數即可。抽很多、範圍不大:直接洗牌取前段。無論哪種,都要記得檢查 count 是否超過範圍上限,這是最常見的無限迴圈元凶。

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