search

classicemi / blog

🖋 my personal blog
https://wushuang.name/
32 stars 2 forks source link

随机排列数组在underscore的实现 #6

Open classicemi opened 9 years ago

classicemi commented 9 years ago

在underscore提供的众多工具方法中，有一个叫做shuffle()的方法，它的作用是将一个集合中的所有元素随机排列，作为数组返回。如果传入的是对象，返回的是包含对象所有随机排列后的value值的数组。

  _.shuffle = function(obj) {
    var set = obj && obj.length === +obj.length ? obj : _.values(obj);
    var length = set.length;
    var shuffled = Array(length);
    for (var index = 0, rand; index < length; index++) {
      rand = _.random(0, index);
      if (rand !== index) shuffled[index] = shuffled[rand];
      shuffled[rand] = set[index];
    }
    return shuffled;
  };

这段代码的实现比较有技术含量，和underscore其他的方法相比更有意思一些。

首先对obj类型做判断，通过obj.length === +obj.length的真假判断obj是否是数组，underscore中判断数组基本上都是这么判断。set变量保存的值，如果obj是数组，则set = obj（原数组），如果obj是对象，则set = _.values(obj)（对象所有value值组成的数组）。（shuffle方法中调用的其他工具方法的作用请自行查阅文档）

然后根据set的长度初始化一个定长的空array作为最后的返回值，下面的一个for循环就是对这个数组的关键操作。为了方便描述，现在假设传入的obj是[1, 2, 3, 4, 5]这个数组，下面进入for循环，只用看前两个循环就可以：

// 第一次循环 
index = 0
shuffled = [_, _, _, _, _]
rand = 0到0的一个随机数（就是0）
shuffled[0] = shuffled[0];
shuffled[0] = set[0]; --> [1, _, _, _, _]

// 第二次循环
index = 1
shuffled = [_, _, _, _, _]
rand = 0到1的一个随机数（可能是0也可能是1）
假设是0：
shuffled[1] = shuffled[0]; --> [1, 1, _, _, _]
shuffled[0] = set[1]; --> [2, 1, _, _, _]
假设是1：
shuffled[1] = shuffled[1]; --> [1, _, _, _, _]
shuffled[1] = set[1]; --> [1, 2, _, _, _]

第一次循环，结果是一定的，在shuffled数组中填入第一个元素。 第二次循环，rand是以0到当前索引值为闭区间的一个随机数，不论这个区间有多大，结果只有两类：

第一类：rand为当前索引值，shuffled[rand]位置上为空 这种情况下，新元素直接填充到shuffled数组的下一个空位上，其他元素没有任何变化。 第二类：rand为其他值，shuffled[rand]位置上有元素` 这种情况下，先将shuffled[rand]上的元素复制到shuffled[index]的位置上，再将要填入的新元素覆盖到shuffled[rand]上。

以后的每一步都是这样的逻辑。

源码分析完了，不难理解，但问题的重点是，怎样证明通过这样的操作方法实现的数组是真正随机排列的数组。

此方法中用的算法名为Fisher–Yates shuffle，也是洗牌算法的一种。该算法的时间复杂度为O(n)，性能上还可以。然后对于每一个元素(elemIndex)来说，它在插入shuffled数组时，对于[0, elemIndex]上的所有位置都是等可能的。在后面的循环中，对于[elemIndex, currentIndex]的所有位置也是等可能的。因此，对于任意一个元素来说，出现在任何位置的概率都是相等的。下面我们可以通过一个实验来大致感受一下：
实验对象选用一个1-10的数组。

var count = [[], [], [], [], [], [], [], [], [], []]
var testArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
var temp, i, j

for (i = 0; i < 1000; i++) {
    temp = _.shuffle(testArr)
    for (j = 0; j < 10; j++) {
        count[j][temp[j]] ?
                count[j][temp[j]]++ :
                count[j][temp[j]] = 1
    }
}

for (j = 1; j < 11; j++) {
    console.log(j + '出现在各位置的次数：',
            count[0][j],
            count[1][j],
            count[2][j],
            count[3][j],
            count[4][j],
            count[5][j],
            count[6][j],
            count[7][j],
            count[8][j],
            count[9][j])
}

结果如截图： 多执行几次可以观察到，每个数字在各位置出现的概率大致是相等的，对于前端实现随机打乱数组的需求已经基本满足要求了。

titanew commented 9 years ago

棒棒的