DIV CSS 佈局教程網

不重複隨機數的三種解法與效能比較
編輯:關於JavaScript     

JavaScript 的 Math.random() 會產生重複值,但很多情境(抽獎、隨機排序、抽樣出題)要求彼此不重複。以下三種做法,思路各異,效能差距相當明顯。

方法一:取一個就刪一個

先建好 1~3000 的陣列,每次隨機取一個索引,取值後用 splice 把它從陣列移除。因為取過的就不在了,自然永不重複。

<script type="text/javascript">
var count = 3000;
var originalArray = new Array();

for (var i = 0; i < count; i++) {
    originalArray[i] = i + 1;
}

var d1 = new Date().getTime();
for (i = 0; i < count; i++) {
    var index = Math.floor(Math.random() * originalArray.length);
    document.write(index + " , ");
    originalArray.splice(index, 1);      // 取出後移除
}
var d2 = new Date().getTime();
document.write("運算耗時" + (d2 - d1));
</script>

效能:約 1528 毫秒。 慢的原因是 splice 每次都要搬移後面的所有元素,整體是 O(n²)。

方法二:取出來就標記為 null

不改動陣列長度,改把取過的位置設為 null;下次抽 index 時若抽到 null 就重抽。

<script type="text/javascript">
var count = 3000;
var originalArray = new Array();

for (var i = 0; i < count; i++) {
    originalArray[i] = i + 1;
}

var d1 = new Date().getTime();
for (var num, i = 0; i < count; i++) {
    do {
        num = Math.floor(Math.random() * count);
    } while (originalArray[num] == null);    // 撞到已取過的就重來
    document.write(originalArray[num] + " , ");
    originalArray[num] = null;
}
var d2 = new Date().getTime();
document.write("運算耗時" + (d2 - d1));
</script>

效能:約 290 毫秒。 比方法一快五倍以上。但要注意它的尾段會變慢:當陣列快被取光,隨機碰撞的機率急遽上升,最後幾次要重抽很多次。若改成抽 2900 個(接近全滿)以外的比例,差距會更明顯。

方法三:先洗牌,再順序讀出

把陣列打亂之後照順序輸出,同樣能保證不重複,而且直覺。

<script type="text/javascript">
var count = 3000;
var originalArray = new Array();

for (var i = 0; i < count; i++) {
    originalArray[i] = i + 1;
}

var d1 = new Date().getTime();
originalArray.sort(function () { return 0.5 - Math.random(); });
for (var i = 0; i < count; i++) {
    document.write(originalArray[i] + " , ");
}
var d2 = new Date().getTime();
document.write("運算耗時" + (d2 - d1));
</script>

效能:約 229 毫秒,是三者中最快的。

比較與選擇

  • 方法一:語意最直白,但 splice 的搬移成本讓它在大陣列下完全不可行。
  • 方法二:明顯改善,但每次抽取的期望嘗試次數隨剩餘數量下降而上升,尾段效率差。
  • 方法三:一次洗牌搞定,之後讀取是 O(1),總成本最低。

不過要補充一點:方法三的 sort(function(){ return 0.5 - Math.random(); }) 並不是均勻的洗牌。排序演算法依賴比較結果的一致性,而這裡每次比較都回傳隨機值,會導致各種排列的機率不相等,實作也可能因引擎而異。要真正均勻,應該用 Fisher–Yates 洗牌:

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

它和方法三一樣是「先打亂再讀取」的思維,時間複雜度 O(n)、且分佈均勻,同時避開了方法二尾段重抽的問題——兼得正確性與效能,是這個問題的標準答案。

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