摘要：隨機(jī)洗牌算法說實(shí)話，以前理解數(shù)組的排序，都是將數(shù)組按照一定的邏輯由大到小或者由小到大排序，我自己是沒有碰到過隨機(jī)打亂數(shù)組排序的問題。然后里用的是所謂的洗牌算法，很高效。總結(jié)又是三個知識點(diǎn)，分別是隨機(jī)洗牌分組和函數(shù)的實(shí)現(xiàn)，沒什么復(fù)雜的。

這是第三篇關(guān)于 Underscore 的源碼解讀，最近一段時間學(xué)的東西很少，自己太忙了，一方面忙著找實(shí)習(xí)，晚上回去還要寫畢業(yè)論文。畢業(yè)論文真的很憂傷，因?yàn)槭莾赡臧?，九月份就要交一個初稿，一般都是暑假寫，如果暑假出去實(shí)習(xí)，是沒時間點(diǎn)，所以要現(xiàn)在寫一個版本出來。

說實(shí)話，以前理解數(shù)組的排序，都是將數(shù)組按照一定的邏輯（由大到小或者由小到大）排序，我自己是沒有碰到過隨機(jī)打亂數(shù)組排序的問題。今天看到這個問題，先是一愣，為什么要把一個數(shù)組給隨機(jī)亂序，仔細(xì)想想這種應(yīng)用場合還是很多的，比如隨機(jī)地圖、隨機(jī)洗牌等等，都是隨機(jī)亂序的應(yīng)用。

如果這是一個面試題，將一個數(shù)組隨機(jī)亂序，我的解決辦法如下：

function randomArr( arr ){
  var ret = [],
    rand,
    len,
    newA = arr.slice(); // 為了不破壞原數(shù)組
  while(len = newA.length){
    rand = Math.floor(Math.random() * len);
    ret.push(newA.splice(rand, 1)[0]);
  }
  return ret;
}

這是一個解決辦法，但是卻不是一個高效的解決辦法，首先，空間復(fù)雜度來講，新建了兩個數(shù)組（若不考慮對原數(shù)組的改變，可以只用一個返回?cái)?shù)組），如果能在原數(shù)組上直接操作，那真的是太好了，其次時間復(fù)雜度來講，splice 函數(shù)要對數(shù)組進(jìn)行改變，復(fù)雜度可以算作 n，所以總的時間復(fù)雜度應(yīng)該為 O(n^2)。

然后 _ 里用的是所謂的洗牌算法，很高效。洗牌算法的思路有個很大的不同，用交換數(shù)組元素的方式替換原來的 splice，因?yàn)?splice 太坑了，然后對上面的代碼進(jìn)行改進(jìn)：

function randomArr2( arr ){
  var rand, temp;
  for(var i = arr.length - 1; i >= 0; i--){
    rand = Math.floor(Math.random() * ( i + 1 ));

    // 交互 i 和 rand 位置的元素
    temp = arr[i];
    arr[i] = arr[rand];
    arr[rand] = temp;
  }
  return arr;
}

改進(jìn)后看起來就好多了，也比較好理解，還有一個循環(huán)的方式是從 0 到 n，randmo 函數(shù)沒次取值到范圍為 i~n，方法也大體是相同的。然而在 _ 中的 shuffle 方法的循環(huán)卻是從左到右，看了半天才明白，代碼如下：

  // [Fisher-Yates shuffle](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
  _.shuffle = function(obj) {
    var set = isArrayLike(obj) ? obj : _.values(obj);
    var length = set.length;
    var shuffled = Array(length); // 新建一個 kength 長度的空數(shù)組
    for (var index = 0, rand; index < length; index++) {
      rand = _.random(0, index); // 獲取 0～index 之間的隨機(jī)數(shù)

      // shuffled[index] 是 undefined 的，先將 index 處的值替換成 rand 處的值
      // 再將 rand 處的值替換成 set 集合處的 index
      if (rand !== index) shuffled[index] = shuffled[rand];
      shuffled[rand] = set[index];
    }
    return shuffled;
  };

_.shuffle 使用的是從左到右的思路，以至于我都無法判斷出這是不是隨機(jī)數(shù)組，向右前進(jìn)一位，找到 0 ~ index 之間的一個隨機(jī)數(shù)，插入新元素，如果還按照之前的解題思路，在原數(shù)組的基礎(chǔ)上進(jìn)行修改，則可以得到：

function randomArr3(arr){
  var rand, temp;
  for(var i = 0; i < arr.length; i++){
    // 這里的 random 方法和 _.random 略有不同
    rand = Math.floor(Math.random() * ( i + 1 ));
    if(rand !== i){
      temp = arr[i];
      arr[i] = arr[rand];
      arr[rand] = temp;
    }
  }
  return arr;
}

_.random 方法是一個非常實(shí)用的方法，而我在構(gòu)造 randomArr3 函數(shù)的時候，是想得到一個 0 ~ i 之間的一個隨機(jī)數(shù)，來看看 _.random 是如何方便的實(shí)現(xiàn)的：

_.random = function(min, max) {
  if (max == null) {
    max = min;
    min = 0;
  }
  // 和我最終的思路是一樣的
  return min + Math.floor(Math.random() * (max - min + 1));
};

有時候需要對從服務(wù)器獲得的 ajax 數(shù)據(jù)進(jìn)行統(tǒng)計(jì)、分組，這個時候就用到了 _ 中的 group 函數(shù)。

與 group 相關(guān)的函數(shù)有三個，它們分別是 groupBy，indexBy，countBy，具體使用可以參考下面的代碼：

// groupBy 用來對數(shù)據(jù)進(jìn)行分組
_.groupBy([3, 4, 5, 1, 8], function(v){ return v % 2 });
// {0:[4,8],1:[3,5,1]}

// 還可以用數(shù)據(jù)的屬性來區(qū)分
_.groupBy(["red", "yellow", "black"], "length");
// {3:["red"],5:["black"],6:["yellow"]}

// 從某一個屬性入手，相同的會替換
_.indexBy([{id: 1,name: "first"}, {id: 2, name: "second"}, {id: 1, name: "1st"}], "id");
// {1:{id:1,name:"1st"},2:{id:2,name:"second"}}

// 用來統(tǒng)計(jì)數(shù)量
_.countBy([3, 4, 5, 1, 8], function(v){ return v % 2 == 0 ? "even" : "odd" });
// {odd: 3, even: 2}

這三個函數(shù)的實(shí)現(xiàn)都非常類似，在 _ 中有進(jìn)行優(yōu)化，即常見的函數(shù)閉包：

var group = function(behavior) {
  return function(obj, iteratee, context) { // 函數(shù)閉包
    var result = {}; // 要返回的對象
    iteratee = cb(iteratee, context);
    _.each(obj, function(value, index) {
      var key = iteratee(value, index, obj);
      // 針對 group、index、count，有不同的 behavior 函數(shù)
      behavior(result, value, key);
    });
    return result;
  };
};

_.groupBy = group(function(result, value, key) {
  // 每個屬性都是一個數(shù)組
  if (_.has(result, key)) result[key].push(value); else result[key] = [value];
});

_.indexBy = group(function(result, value, key) {
  // 對于相同的前者被后者替換
  result[key] = value;
});

_.countBy = group(function(result, value, key) {
  // 每個屬性是數(shù)量
  if (_.has(result, key)) result[key]++; else result[key] = 1;
});

對于 groupBy 和 countBy 處理模式幾乎是一摸一樣的，只是一個返回?cái)?shù)組，一個返回統(tǒng)計(jì)值而已。

關(guān)于統(tǒng)計(jì)，這三個函數(shù)用的還真的不是很多，循環(huán)很好構(gòu)造，處理函數(shù)也很好構(gòu)造，如果數(shù)據(jù)是數(shù)組，直接 forEach 循環(huán)一遍添加一個處理函數(shù)就 ok 了，不過 _ 最大的優(yōu)點(diǎn)就是省事吧，這種重復(fù)利用函數(shù)、函數(shù)閉包的思路，是值的借鑒的。

call、apply、bind 這三個函數(shù)也算是 js 函數(shù)中三劍客，經(jīng)常能看到面試題，讓實(shí)現(xiàn) bind 函數(shù)，我就有一個疑問，難道支持 apply 的瀏覽器，不支持 bind 函數(shù)：

實(shí)現(xiàn) bind 函數(shù)：

Function.prototype.bind = Function.prototype.bind || 
  function(context){
    var slice = Array.prototype.slice
    var args = slice.call(arguments, 1),
      self = this;
    return function(){
      self.apply(context, args.concat(slice.call(arguments)));
    }
  }

有時候也會看到有人這樣寫：

Function.prototype.bind = Function.prototype.bind || 
  function(context){
    var self = this;
    return function(){
      self.apply(context, arguments);
    }
  }

下面這種寫法顯然是低級新手玩家的手準(zhǔn)，因?yàn)閷τ?bind 函數(shù)，有個很大的優(yōu)點(diǎn)就是提前預(yù)定參數(shù)，如果懂了這個，就不會犯這個錯誤。

來看看 _ 里高級玩家的寫法：

_.bind = function(func, context) {
  // 原生 bind 還是好，此函數(shù)總結(jié)
  if (nativeBind && func.bind === nativeBind) return nativeBind.apply(func, slice.call(arguments, 1));
  // 報(bào)個錯
  if (!_.isFunction(func)) throw new TypeError("Bind must be called on a function");
  var args = slice.call(arguments, 2); // 先存變量
  var bound = function() {
    return executeBound(func, bound, context, this, args.concat(slice.call(arguments)));
  };
  return bound;
};

var executeBound = function(sourceFunc, boundFunc, context, callingContext, args) {
  // 還是用 apply 來回調(diào)，args 已經(jīng)是拼接好的
  if (!(callingContext instanceof boundFunc)) return sourceFunc.apply(context, args);
  // 后面好想是針對 constructor 的，表示看不懂
  var self = baseCreate(sourceFunc.prototype);
  var result = sourceFunc.apply(self, args);
  if (_.isObject(result)) return result;
  return self;
};

在 _ 里類似 bind 的函數(shù)還有 _.partial 和 _.bindAll，只是使用的時候大同小異，就不多做介紹了，總之記住一句話，閉包無敵。

又是三個知識點(diǎn)，分別是隨機(jī)洗牌、分組和 bind 函數(shù)的實(shí)現(xiàn)，沒什么復(fù)雜的。

說到閉包，其實(shí)面試的時候問得最多的就是這個問題了，有啥優(yōu)點(diǎn)，有啥缺點(diǎn)，如果是現(xiàn)場面，我直接手寫一串代碼，對面試官說：看，這就是閉包：

function add(m){
  var fn = function(n){
    return add( m + n );
  }
  fn.toString = function(){
    return m;
  }
  return fn;
}

add(2)(3)(4).toString(); //9

好像不對，這不是閉包，是柯里化。

Fisher–Yates shuffle
JavaScript 數(shù)組亂序
Underscore.js (1.8.3) 中文文檔
淺談 underscore 內(nèi)部方法 group 的設(shè)計(jì)原理

歡迎來我的博客交流。