随机取样与洗牌算法

洗牌算法

在一些场景下,我们需要抽样一个序列的部分,一般来说,我们会需要抽样过程是随机的,假定样本容量为 ,序列下标为 ,且 ,那么我们这样完成抽样过程 1. 随机生成 个序号 2. 根据序号,逐个从序列中取出元素

可以看到,过程很简单,唯一需要被设计的地方就是 -- 如何均匀地生成随机序号,这样才有助于我们获得一个高质量的样本。换一种视角,我们获得的样本集合就是原集合的部分乱序结果。例如:

原集合:[1, 2, 3, 4, 5]

乱序结合(假设 ): [5, 2, 1, 3, 4]

样本直接就可以来自于乱序集合的前三个: [5, 2, 1]

这就是最常见的乱序数组的算法 -- 洗牌算法

算法的思路在宏观上可以概括为:将集合视为牌堆,不停地从牌堆中抽牌构成新的牌堆,直至新牌堆的牌数到达预设数量。我们尝试用 JavaScript 模拟一下这个算法:

// 洗牌算法
function shuffle(set, n) {
  var length = set.length;
  var i;
  // 初始化sample
  var sample = set.map(function(elem){
    return elem;
  });
  // 最后一个元素的位置
  var last = length - 1;
  // 洗到第n个就可以停止
  for(i=0; i<n; i++) {
    // 从剩余未乱序的集合中选出一个随机位置
    var randIndex = Math.floor(Math.random()*(last-i+1)+i);
    // 交换随机位置上与当前位置的值,完成乱序
    var tmp = sample[i];
    sample[i] = sample[randIndex];
    sample[randIndex] = tmp;
  }
  // 返回前n个样本
  return sample.slice(0, n);
}

// 测试
var set = [1,2,3,4,5,7,8,9,10];

var newSet = shuffle(set4);
// => [2, 8, 3, 5]

_.sample

_.sample(coll, n):从 coll 随机取出 n 个样本。

underscore 中的抽样函数正基于洗牌算法的,我们看到源码:

_.sample = function (obj, n, guard) {
    if (n == null || guard) {
        if (!isArrayLike(obj)) obj = _.values(obj);
        return obj[_.random(obj.length - 1)];
    }
    // 如果是对象,乱序key的排列
    var sample = isArrayLike(obj) ? _.clone(obj) : _.values(obj);
    var length = getLength(sample);
    // 校正参数n,使得0<=n<length
    n = Math.max(Math.min(n, length), 0);
    var last = length - 1;
    // 开始洗牌算法, 洗出来n个就停止了
    for (var index = 0; index < n; index++) {
        // 从[index, last]即剩余未乱序部分获得一个随机位置
        var rand = _.random(index, last);
        // 交换当前值与随机位置上的值
        var temp = sample[index];
        sample[index] = sample[rand];
        sample[rand] = temp;
        // 此时,排序后的第一个数据sample[0]已经确定
    }
    return sample.slice(0, n);
};

有两点值得注意:

  • 如果是对一个对象进行抽样,那么是对这个对象的值集合进行抽样。
  • 如果没有设置 n,则随机返回一个元素,不进行集合乱序。

用例

_.sample([1, 2, 3, 4, 5, 6], 3);
// => [1, 6, 2]

_.sample([1, 2, 3, 4, 5, 6]);
// => 4

_.sample({name: 'wxj', age: 13, sex: 'male'}, 2);
// [13, "wxj"]

_.shuffle

_.shuffle(coll): 获得 coll 乱序副本。

基于 _.sample,underscore 还提供了一个函数用来直接返回一个乱序后的集合副本,这也体现了 _.sample 不直接返回元素,而是乱序数组的带来的复用好处:

源码

_.shuffle = function (obj) {
    return _.sample(obj, Infinity);
};

用例

_.shuffle([1, 2, 3, 4, 5, 6]);
// => [2, 4, 3, 5, 6, 1]

_.shuffle({name: 'wxj', age: 13, sex: 'male'});
// => ["wxj", "male", 13]

results matching ""

    No results matching ""