「把陣列打亂」聽起來簡單,寫起來卻有高下之別。這個主題在開發社群裡反覆被討論,剛好很適合拿來對照幾種思路的優劣。
最初容易想到的做法是:跑「原陣列長度」次的迴圈,每次隨機挑一個索引,檢查有沒有挑過,沒挑過就放進新陣列,挑過就把計數器退回一次重來。
function randArr(arr) {
var ret = [], obj = {}, i = arr.length, l = i, n;
while (--i >= 0) {
n = Math.floor(Math.random() * l);
if (obj[n] === void 0) {
ret[ret.length] = obj[n] = arr[n];
} else {
i++; // 撞到重複,退回一次
}
}
return ret;
}
它能跑出正確結果,但效能完全取決於運氣。當已挑過的元素越來越多,碰撞就越頻繁,迴圈次數可能遠超陣列長度。看到這個思路,問題其實已經浮現:為什麼要用「重試」來換取隨機性?
換個角度想,如果每次挑出元素後就把它從來源陣列移除,那麼後續就算再抽到同一個索引,取到的也已經是別的值;而且隨機範圍會隨著陣列變短自動收斂。
function randArr(arr) {
var ret = [], i = arr.length, n;
arr = arr.slice(0); // 先複製,不動到原陣列
while (--i >= 0) {
n = Math.floor(Math.random() * i);
ret[ret.length] = arr.splice(n, 1)[0];
}
return ret;
}
這個寫法相當巧妙:固定跑 n 次、絕不空轉,時間複雜度可預期。代價是 splice 每次都要搬移後續元素。
如果在意刪除帶來的搬移成本,可以改用「洗牌」思路:把抽到的元素直接搬到結果陣列,同時用當前尾端位置的值補上空缺。整個過程不需要真正的刪除,對陣列的扰动降到最低。
function randArr(arr) {
var ret = [], i = arr.length, n;
arr = arr.slice(0);
while (--i >= 0) {
n = Math.floor(Math.random() * i);
ret[ret.length] = arr[n];
arr[n] = arr[i]; // 用尾端元素填補被取走的位置
}
return ret;
}
這基本上就是 Fisher–Yates 洗牌算法的變化型,也是實務上最推薦的做法。
同樣的「取出後補位」思維,可以用來生成一段區間內不重複的隨機整數:
function makeRandArr(min, max) {
var ret = [], obj = {}, n;
for (; max >= min; max--) {
n = Math.ceil(Math.random() * (max - min)) + min;
ret[ret.length] = obj[n] || n;
obj[n] = obj[max] || max;
}
return ret;
}
這裡用一個 map 充當「虛擬的已用集合」:obj[n] 存的是原本在位置 n 的值,取用後把尾端的值搬過來,等價於在不實際建立大陣列的情況下模擬了互換。
三個版本一路看下來,可以發現一個共通的教訓:寫功能時為了「直覺」而反覆重試,往往會在資料量變大時付出代價。把「隨機取不重複」重新表述為「取一個、補一個」,問題就從機率遊戲變成了線性走訪。這也是為什麼 Fisher–Yates 值得被記住——它不只是快,而是換了一個更精準的問題描述。