Expose shuffle function of underscore.js

发表于 | 分类于 | | 阅读次数

underscore.js 里有一个数组重新随机排序的函数 _.shuffle：

1
2
3
4
5
6
7
8
9
10
11
12
13
// Shuffle an array.
_.shuffle = function (obj) {
    var rand;
    var index = 0;
    var shuffled = [];
    each(obj, function (value) {
        // _.random函数返回[0, index]之间的随机数
        rand = _.random(index++);
        shuffled[index - 1] = shuffled[rand];
        shuffled[rand] = value;
    });
    return shuffled;
};

函数的算法

  1. 创建 数组 shuffled = []，用于保存随机排序后的数组；
  2. 迭代 待排序数组，设定当前迭代索引 index = 0；
  3. 生成 随机索引 rand。rand 的值介于 [0, index]；
  4. 添加 元素到 shuffled 数组，值为 shuffled[rand]；
  5. 赋予 shuffle[rand] 当前迭代元素的值

运行过程

假定现有待随机排序数组 array = [1, 2, 3, 4, 5]，那么第一次迭代的时候情形如下：

1
2
3
4
5
6
7
8
9
array[index]: 1, index: 0, rand: 0, shuffled: []
    
    rand
    ↓
    ■     □     □     □     □
    ↑
    index
    
shuffled = [1];

此时，rand 的值只能与 index 的值相等，所以 shuffled 第一个元素取值为待排序数组的第一个元素。

第二次迭代时，假定 rand 随机值为 0（ rand 的值只能在 [0, index] 之间）：

1
2
3
4
5
6
7
8
9
array[index]: 2, index: 1, rand: 0, shuffled: [1]
    
    rand(assume)
    ↓
    ■     ■     □     □     □
          ↑
          index
    
shuffled = [2, 1];

shuffle[1] 被赋值为 shuffle[0]，shuffle[0] 被赋值为 array[1]。

最后一次迭代假设此时 rand = 1，shuffled = [2, 4, 1, 5]：

1
2
3
4
5
6
7
8
array[index]: 3, index: 4, rand: 1, shuffled: [2, 4, 1, 5]
    
          rand(assume)
          ↓                  
    ■     ■     ■     ■     ■
                            ↑
                            index
shuffle = [2, 3, 1, 5, 4]

shuffled[4] 将会被赋值为 shuffled[1]，shuffled[1] 被赋值为 3。所以 shuffled 最后为 [2, 3, 1, 5, 4]。

另一种思路

  1. 迭代 待排序数组；
  2. 生成 随机索引 rand，索引的范围为 [0 ~ 待排序数组 - 1]；
  3. 抽取 待排序数组中索引为 rand 的元素，抽取行为改变了待排序数组；
  4. 追加 抽取的元素到结果数组的末尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function shuffle(array) {
    var rand;
    var shuffled = [];
    for (var i = 0, l = array.length; i < l; i++) {
        // 获取随机索引值。
        // 随机索引值的范围为[0 ~ 原始数组的长度 - 1]
        rand = random(array.length - 1);
        // 使用splice方法抽取数组元素
        shuffled[i] = array.splice(rand, 1)[0];
    }
    return shuffled;
}
function random(min, max) {
    (Object.prototype.toString.call(max) !== "[object Number]") && (max = min);
    return min + Math.floor(Math.random() * (max - min + 1));
}

相对于 _.shuffle，这个方法每个元素在每次迭代过程中就确定下来了，而 _.shuffle 结果数组中每个元素在最后一步完成前都可能改变。

0%