从underscore源码看数组乱序

[webproblem]

前言

前段时间看到过一道实现数组乱序的面试题，也在《如何轻松拿到淘宝前端 offer》一文中看到作者提到数组乱序的问题，竟然还涉及到 v8 引擎方面的知识，正好近期在拜读 underscore 的源码，自己也没有了解过这方面的知识点，在此就总结下关于数组乱序的知识。

面试题

看到的面试题大致是这样的：var arr = ['a', 'b', 'c', 'd', 'c']; 实现数组乱序 。

首先，通过题目可以看出，可能存在一个小陷阱，数组中存在两个 'c' 元素，我想这并不是面试官或者出题人无意打错字，可能是想顺便考察下面试者对数组去重的掌握情况。当然了，这个小细节也可以忽略直接进入实现乱序功能。

对于有代码洁癖的开发人员来说，是不允许自己的程序中出现相同的元素数组值的，所以我们先把数组去重好了。

arr = [...new Set(arr)]; // ["a", "b", "c", "d"]

去重之后，就可以思考如何实现乱序了。所谓乱序就是打乱原数组元素之间的位置，使之与原数组之间的结构不一致。一开始想的方案是随意交换两个相邻元素的位置使得与原数组不一致就好了。

function shuffle(array) {
    array = array.concat();
    var rand = Math.floor(Math.random() * Number(array.length));
    var temp = array[rand];
    if(array[rand - 1] !== void 0) {
        array[rand] = array[rand - 1];
    	array[rand - 1] = temp;
    }else if(arr[rand + 1] !== void 0) {
        array[rand] = array[rand + 1];
    	array[rand + 1] = temp;
    }
    return array;
}

但后来一想，发现这只是达到了部分乱序的效果而已，要如何才能达到全部元素随机乱序的效果呢？

sort + Math.random

常见的一种实现方案就是使用数组的 sort 排序方法，原理就是 sort 的 compareFunction 匿名函数的返回值小于 0 则升序排列，大于 0 则降序排列，由于 Math.random() 得到的是 0-1 区间的数，Math.random() - 0.5 有 50% 的概率大于 0，50% 的概率小于 0。

function shuffle(arr) {
    return arr.concat().sort(function() {
        return Math.random() - 0.5;
    })
}

但是这并不是最好的解决方案，sort 排序存在的问题就是元素位置概率不均，某个元素排序后位置不变或者调换在相邻位置的概率更高，测试如下：

var count = new Array(7).fill(0);

for(var i=0; i<10000; i++) {
    var arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
    arr = shuffle(arr);
    count[arr.indexOf('a')]++;
}

console.log(count); // 一次随机乱序的结果 => [3033, 2927, 1899, 1143, 585, 284, 129]

测试进行了 10000 次的乱序排序，可以看出 'a' 元素出现在第一个位置的次数远高于出现在其他位置的次数，也就是说本应当出现在每个位置的次数应该是差不多的，实际上却差别很大，这种差异大或者不公平的结果的出现，说明这种方案并不是一个很好的解决方案。

v8 对 sort 的实现

想要知道为什么 sort 排序会出现元素分布不均的情况，就要了解底层的实现方式。v8 源码中对 sort 的实现，出于性能考虑，对于短数组（数组长度小于等于10）使用的是插入排序，长数组（数组长度大于10）使用的是快速排序和插入排序的混合排序。v8源码地址。

插入排序的源码：

function InsertionSort(a, from, to) {
	for (var i = from + 1; i < to; i++) {
		var element = a[i];
		for (var j = i - 1; j >= from; j--) {
			var tmp = a[j];
			var order = comparefn(tmp, element);
			if (order > 0) {
				a[j + 1] = tmp;
			} else {
				break;
			}
		}
		a[j + 1] = element;
	}
};

简单来说就是将第一个元素视为有序序列，遍历数组，将之后的元素依次插入这个构建的有序序列中。其中 comparefn() 是关键， comparefn 部分：

具体分析 sort 的分布不均的情况，可参考冴羽的JavaScript专题之乱序。

关于 underscore 源码的解读，解读地址： Underscore.analysis.js。

Fisher–Yates shuffle

那么有没有更好的实现方案呢？答案是肯定是有的。先来看看 underscore 源码对数组乱序的实现。

PS：自己研读 underscore 源码时加的注释。

  /**
   * 得到一个随机乱序的集合副本
   * var arr = ['a', 'b', 'c', 'd'];
   * _.shuffle(arr); // 一次随机的结果 => ["b", "c", "d", "a"]
   */
  _.shuffle = function(obj) {
    // 传入 Infinity 参数是为了一次性返回乱序的结果，如果不传，每次执行都会返回一个单一的随机项
    return _.sample(obj, Infinity);
  };

  /**
   * 从集合中产生一个随机样本
   * 原理是遍历对象元素，将当前元素与另一个随机元素调换位置，直到遍历结束
   * 数组乱序讲解参考文章：
   * https://github.com/mqyqingfeng/Blog/issues/51
   * https://github.com/hanzichi/underscore-analysis/issues/15
   * @param obj    需要乱序的对象
   * @param n      返回的随机元素个数，如果值为空，会返回一个单一的随机项
   * @param guard  暂没发现这个参数的作用
   */
  _.sample = function(obj, n, guard) {
    // 返回单一的随机项
    if (n == null || guard) {
      if (!isArrayLike(obj)) obj = _.values(obj);
      return obj[_.random(obj.length - 1)];
    }
    var sample = isArrayLike(obj) ? _.clone(obj) : _.values(obj);
    var length = getLength(sample);
    // 防止 n 的值为负数，且 n 的值不能超过对象元素的数量，确保下面的 for 循环正常遍历
    n = Math.max(Math.min(n, length), 0);
    var last = length - 1;
    for (var index = 0; index < n; index++) {
      // 获取随机调换位置元素的下标
      var rand = _.random(index, last);
      var temp = sample[index];
      sample[index] = sample[rand];
      sample[rand] = temp;
    }
    return sample.slice(0, n);
  };

underscore 实现的大致思路就是遍历数组元素时，将当前元素随机与后面的另一个数组元素的位置进行互换，直到遍历结束。

这种实现思路就是所谓的 Fisher–Yates shuffle 算法，且时间复杂度为 O(n) ，性能上是最优的。

按照这个思路再次实现如下：

function shuffle(arr) {
    var rand, temp;
    for(var i=0; i<arr.length; i++) {
        rand = i + Math.floor(Math.random() * (arr.length - i));
        temp = arr[i];
        arr[i] = arr[rand];
        arr[rand] = temp;
    }
    return arr;
}

再来测试这个方案的效果：

var count = new Array(7).fill(0);

for(var i=0; i<10000; i++) {
    var arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
    arr = shuffle(arr);
    count[arr.indexOf('b')]++;
}
console.log(count); // 一次随机乱序排序的结果 => [1403, 1413, 1448, 1464, 1451, 1456, 1365]

可以看到 ‘b’ 元素出现在各个位置的次数大致是均匀的，达到了真正的乱序效果。

其他实现方案

还有一种实现思路，可能不是最优的方案。 大致思路就是随机挑选数组中的任意一个元素存放到新数组中，且该元素从原数组中移出，重复这样的操作直到原数组中的元素为空，新数组就是乱序后的结果。

function shuffle(arr) {
    var newArr = [], rand;
    arr = arr.concat();
    while(arr.length) {
        rand = Math.floor(Math.random() * arr.length);
        newArr.push(arr[rand]);
        arr.splice(rand, 1);
    }
    return newArr;
}

总结

• 常见的 sort + Math.random 方式乱序其实也是属于局部乱序，并没有达到所有元素都打乱顺序的效果。原因是因为 v8 底层对于短数组使用的是插入排序，长数组使用的是混合排序。
• Fisher–Yates shuffle 算法应该是最优的实现方案，原理是遍历数组，将当前元素与在它后面的任意一个元素交换位置，直到遍历结束。

参考

• JavaScript专题之乱序 mqyqingfeng/Blog#51
• JavaScript 数组乱序 lessfish/underscore-analysis#15
• https://blog.oldj.net/2017/01/23/shuffle-an-array-in-javascript/
• https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle