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;下次抽 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 毫秒,是三者中最快的。
不過要補充一點:方法三的 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)、且分佈均勻,同時避開了方法二尾段重抽的問題——兼得正確性與效能,是這個問題的標準答案。