DIV CSS 佈局教程網

JavaScript 陣列隨機化與隨機陣列產生
編輯:關於JavaScript     

「把陣列打亂」聽起來簡單,寫起來卻有高下之別。這個主題在開發社群裡反覆被討論,剛好很適合拿來對照幾種思路的優劣。

起點:一個直覺但沒效率的版本

最初容易想到的做法是:跑「原陣列長度」次的迴圈,每次隨機挑一個索引,檢查有沒有挑過,沒挑過就放進新陣列,挑過就把計數器退回一次重來。

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 值得被記住——它不只是快,而是換了一個更精準的問題描述。

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