从阵列采样的随机子集(Sampling a random subset from an array)

2019-06-17 17:40发布

站内文章 / 前端开发
69 0 0

什么是与JavaScript中的数组采取随机抽样，无需更换一个干净的方式？ 因此，假设有一个数组 

x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

我想随机样品5个的唯一值; 即产生长度为5的随机子集来生成一个随机样本，一个可以这样做： 

x[Math.floor(Math.random()*x.length)];

但是，如果这样做了多次，有一个相同的入口多次抢夺的风险。

Answer 1:

我建议洗牌使用数组的副本费雪耶茨洗牌 ，并采取切片： 

function getRandomSubarray(arr, size) {
    var shuffled = arr.slice(0), i = arr.length, temp, index;
    while (i--) {
        index = Math.floor((i + 1) * Math.random());
        temp = shuffled[index];
        shuffled[index] = shuffled[i];
        shuffled[i] = temp;
    }
    return shuffled.slice(0, size);
}

var x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
var fiveRandomMembers = getRandomSubarray(x, 5);

请注意，这不会是获得了大阵的一个小随机子集最有效的方法，因为它打乱了整个阵列不必要的。 为了获得更好的性能，你可以做一个部分，而不是洗牌： 

function getRandomSubarray(arr, size) {
    var shuffled = arr.slice(0), i = arr.length, min = i - size, temp, index;
    while (i-- > min) {
        index = Math.floor((i + 1) * Math.random());
        temp = shuffled[index];
        shuffled[index] = shuffled[i];
        shuffled[i] = temp;
    }
    return shuffled.slice(min);
}


Answer 2:

有点迟到了，但是这可能是与下划线的新的需要解决的样品方法（下划线1.5.2日- 9月2013年）： 

var x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

var randomFiveNumbers = _.sample(x, 5);


Answer 3:

或者......如果你使用underscore.js ... 

_und = require('underscore');

...

function sample(a, n) {
    return _und.take(_und.shuffle(a), n);
}

够简单。



Answer 4:

当您选择它们​​时，可以从阵列中的副本中删除的元素。 性能可能不理想，但它可能是你所需要的确定： 

function getRandom(arr, size) {
  var copy = arr.slice(0), rand = [];
  for (var i = 0; i < size && i < copy.length; i++) {
    var index = Math.floor(Math.random() * copy.length);
    rand.push(copy.splice(index, 1)[0]);
  }
  return rand;
}


Answer 5:

虽然我使用费雪耶茨洗牌大力支持，如由Tim唐氏建议 ，这里是实现的要求，数学上正确，包括空集，并给出自己设定一个随机子集在很短的方法。

注意解决方案取决于lodash / 下划线 ： 

function subset(arr) {
    return _.sample(arr, _.random(arr.length));
}


Answer 6:

在我看来，我不认为有必要洗牌整个甲板。 你只需要确保你的样本是随机的不是你的甲板。 你可以做的，就是选择size从正面量然后交换每一个采样阵列，以在它的另一个位。 所以，如果你允许更换你会得到越来越多的洗牌。 

function getRandom(length) { return Math.floor(Math.random()*(length)); }

function getRandomSample(array, size) {
    var length = array.length;

    for(var i = size; i--;) {
        var index = getRandom(length);
        var temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }

    return array.slice(0, size);
}

此算法仅2*size的步骤，如果包括slice方法，来选择随机样本。

更随机

为了使样本更随机，我们可以随机选择样本的起点。 但它是一个更贵一点，以获得样品。 

function getRandomSample(array, size) {
    var length = array.length, start = getRandom(length);

    for(var i = size; i--;) {
        var index = (start + i)%length, rindex = getRandom(length);
        var temp = array[rindex];
        array[rindex] = array[index];
        array[index] = temp;
    }
    var end = start + size, sample = array.slice(start, end);
    if(end > length)
        sample = sample.concat(array.slice(0, end - length));
    return sample;
}

是什么让这个更随机的是，当你永远只是洗牌前的项目，你往往会在样品中没有得到他们很多时候如果采样阵列大，样本较小的事实。 如果数组是不应该始终是相同的，这将不会是一个问题。 那么，究竟这种方法确实是改变了这个位置，洗牌后的区域开始。

无替换

为了不具有复制采样阵列，而不用担心更换，你可以做以下的，但它确实给你3*size VS的2*size 。 

function getRandomSample(array, size) {
    var length = array.length, swaps = [], i = size, temp;

    while(i--) {
        var rindex = getRandom(length);
        temp = array[rindex];
        array[rindex] = array[i];
        array[i] = temp;
        swaps.push({ from: i, to: rindex });
    }

    var sample = array.slice(0, size);

    // Put everything back.
    i = size;
    while(i--) {
         var pop = swaps.pop();
         temp = array[pop.from];
         array[pop.from] = array[pop.to];
         array[pop.to] = temp;
    }

    return sample;
}

没有更换和更随机

要应用给了一点点随机抽样的没有替换函数算法： 

function getRandomSample(array, size) {
    var length = array.length, start = getRandom(length),
        swaps = [], i = size, temp;

    while(i--) {
        var index = (start + i)%length, rindex = getRandom(length);
        temp = array[rindex];
        array[rindex] = array[index];
        array[index] = temp;
        swaps.push({ from: index, to: rindex });
    }

    var end = start + size, sample = array.slice(start, end);
    if(end > length)
        sample = sample.concat(array.slice(0, end - length));

    // Put everything back.
    i = size;
    while(i--) {
         var pop = swaps.pop();
         temp = array[pop.from];
         array[pop.from] = array[pop.to];
         array[pop.to] = temp;
    }

    return sample;
}

快点...

像所有的这些帖子，这个使用费雪耶茨洗牌。 但是，我删除复制阵列的头顶。 

function getRandomSample(array, size) {
    var r, i = array.length, end = i - size, temp, swaps = getRandomSample.swaps;

    while (i-- > end) {
        r = getRandom(i + 1);
        temp = array[r];
        array[r] = array[i];
        array[i] = temp;
        swaps.push(i);
        swaps.push(r);
    }

    var sample = array.slice(end);

    while(size--) {
        i = swaps.pop();
        r = swaps.pop();
        temp = array[i];
        array[i] = array[r];
        array[r] = temp;
    }

    return sample;
}
getRandomSample.swaps = [];


Answer 7:

如果您使用lodash在API中4.x的改变： 

const oneItem = _.sample(arr);
const nItems = _.sampleSize(arr, n);

https://lodash.com/docs#sampleSize



Answer 8:

这是基于Fisher-Yater Shuffle的另一种实现方式。 但是，这是为其中样品尺寸比所述阵列长度显著小的情况下最优化。 此实现不扫描整个阵列也不分配阵列一样大原始数组。 它采用稀疏矩阵，以减少内存分配。 

function getRandomSample(array, count) {
    var indices = [];
    var result = new Array(count);
    for (let i = 0; i < count; i++ ) {
        let j = Math.floor(Math.random() * (array.length - i) + i);
        result[i] = array[indices[j] === undefined ? j : indices[j]];
        indices[j] = indices[i] === undefined ? i : indices[i];
    }
    return result;
}


Answer 9:

你可以通过这种方式，5个元素示例： 

var sample = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
.map(a => [a,Math.random()])
.sort((a,b) => {return a[1] < b[1] ? -1 : 1;})
.slice(0,5)
.map(a => a[0]);

你可以将其定义为在代码中使用函数： 

var randomSample = function(arr,num){ return arr.map(a => [a,Math.random()]).sort((a,b) => {return a[1] < b[1] ? -1 : 1;}).slice(0,num).map(a => a[0]); }

或将其添加到Array对象本身： 

Array.prototype.sample = function(num){ return this.map(a => [a,Math.random()]).sort((a,b) => {return a[1] < b[1] ? -1 : 1;}).slice(0,num).map(a => a[0]); };

如果你愿意，你可以分开的有2个功能（随机播放和样品）的代码： 

Array.prototype.shuffle = function(){ return this.map(a => [a,Math.random()]).sort((a,b) => {return a[1] < b[1] ? -1 : 1;}).map(a => a[0]); };
Array.prototype.sample = function(num){ return this.shuffle().slice(0,num); };


Answer 10:

也许我失去了一些东西，但似乎是不需要复杂或洗牌的潜在开销的解决方案： 

function sample(array,size) {
  const results = [],
    sampled = {};
  while(results.length<size && results.length<array.length) {
    const index = Math.trunc(Math.random() * array.length);
    if(!sampled[index]) {
      results.push(array[index]);
      sampled[index] = true;
    }
  }
  return results;
}


文章来源: Sampling a random subset from an array
标签： javascript arrays random numerical-methods
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~