什么是随机抽样的干净方法,而不用从 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)];
但如果多次执行此操作,则存在多次抓取同一个条目的风险。
什么是随机抽样的干净方法,而不用从 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)];
但如果多次执行此操作,则存在多次抓取同一个条目的风险。
我建议使用Fisher-Yates shuffle对数组的副本进行洗牌并取一个切片:
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);
}
聚会有点晚了,但这可以通过下划线的新示例 方法解决(下划线 1.5.2 - 2013 年 9 月):
var x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
var randomFiveNumbers = _.sample(x, 5);
在我看来,我认为没有必要洗整整个套牌。你只需要确保你的样本是随机的,而不是你的牌组。您可以做的是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
与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;
}
像所有这些帖子一样,这使用了 Fisher-Yates Shuffle。但是,我删除了复制数组的开销。
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 = [];
或者...如果你使用 underscore.js...
_und = require('underscore');
...
function sample(a, n) {
return _und.take(_und.shuffle(a), n);
}
足够简单。
您可以通过这种方式获得 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 个功能(Shuffle 和 Sample):
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); };