从数组中随机采样子集
Sampling a random subset from an array
什么是
随机抽样的干净方法，而无需从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);
}
如果包括slice方法，则此算法仅2*size步骤来选择随机样本。
更多随机
为了使样本更加随机，我们可以随机选择样本的起点。但是获得样品的成本要高一些。
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;
}
更快。。。
像所有这些帖子一样，这使用了费舍尔-耶茨洗牌。但是，我删除了复制数组的开销。
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 = [];
您可以通过以下方式获得 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.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); };
或者... 如果您使用下划线.js...
_und = require('underscore');
...
function sample(a, n) {
return _und.take(_und.shuffle(a), n);
}
足够简单。
虽然我强烈支持使用 Fisher-Yates Shuffle，正如 Tim Down 所建议的那样，这里有一个非常简短的方法，用于根据请求实现随机子集，数学上正确，包括空集和给定集本身。
注意解决方案取决于 lodash/下划线：
洛达什 v4
const _ = require('loadsh')
function subset(arr) {
return _.sampleSize(arr, _.random(arr.length))
}
洛达什 v3
const _ = require('loadsh')
function subset(arr) {
return _.sample(arr, _.random(arr.length));
}
如果您使用的是 lodash，则 API 在 4.x 中发生了更改：
const oneItem = _.sample(arr);
const nItems = _.sampleSize(arr, n);
https://lodash.com/docs#sampleSize
很多答案都谈到了克隆、洗牌、切片原始数组。我很好奇为什么从熵/分布的角度来看这有帮助。
我不是专家，但我确实使用索引编写了一个示例函数以避免任何数组突变——不过它确实添加到了 Set 中。我也不知道这个随机分布是如何的，但代码很简单，我认为在这里需要答案。
function sample(array, size = 1) {
const { floor, random } = Math;
let sampleSet = new Set();
for (let i = 0; i < size; i++) {
let index;
do { index = floor(random() * array.length); }
while (sampleSet.has(index));
sampleSet.add(index);
}
return [...sampleSet].map(i => array[i]);
}
const words = [
'confused', 'astonishing', 'mint', 'engine', 'team', 'cowardly', 'cooperative',
'repair', 'unwritten', 'detailed', 'fortunate', 'value', 'dogs', 'air', 'found',
'crooked', 'useless', 'treatment', 'surprise', 'hill', 'finger', 'pet',
'adjustment', 'alleged', 'income'
];
console.log(sample(words, 4));也许我错过了一些东西，但似乎有一个解决方案不需要洗牌的复杂性或潜在开销：
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;
}
这是另一个基于Fisher-Yates 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;
}
您可以在选择元素时从数组的副本中删除元素。性能可能并不理想，但对于您的需求来说可能没问题：
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;
}
对于非常大的数组，使用索引而不是数组成员更有效。
这就是我在此页面上找不到我喜欢的任何内容后最终得到的结果。
/**
* Get a random subset of an array
* @param {Array} arr - Array to take a smaple of.
* @param {Number} sample_size - Size of sample to pull.
* @param {Boolean} return_indexes - If true, return indexes rather than members
* @returns {Array|Boolean} - An array containing random a subset of the members or indexes.
*/
function getArraySample(arr, sample_size, return_indexes = false) {
if(sample_size > arr.length) return false;
const sample_idxs = [];
const randomIndex = () => Math.floor(Math.random() * arr.length);
while(sample_size > sample_idxs.length){
let idx = randomIndex();
while(sample_idxs.includes(idx)) idx = randomIndex();
sample_idxs.push(idx);
}
sample_idxs.sort((a, b) => a > b ? 1 : -1);
if(return_indexes) return sample_idxs;
return sample_idxs.map(i => arr[i]);
}
我的方法是创建一个getRandomIndexes方法，您可以使用该方法创建将从主数组中提取的索引数组。在本例中，我添加了一个简单的逻辑来避免示例中出现相同的索引。这就是它的工作原理
const getRandomIndexes = (length, size) => {
const indexes = [];
const created = {};
while (indexes.length < size) {
const random = Math.floor(Math.random() * length);
if (!created[random]) {
indexes.push(random);
created[random] = true;
}
}
return indexes;
};
这个函数独立于你所拥有的任何东西，将给你一个索引数组，你可以用它来从你的长度数组中提取值 length ，所以可以采样
const myArray = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
getRandomIndexes(myArray.length, 3).map(i => myArray[i])
每次调用该方法时，您都会得到不同的myArray样本。 在这一点上，这个解决方案很酷，但对不同尺寸的样本可能更好。 如果你想这样做，你可以使用
getRandomIndexes(myArray.length, Math.ceil(Math.random() * 6)).map(i => myArray[i])
每次调用时都会给您一个从 1-6 不同的样本量。
我希望这对:D有所帮助
下划线.js大约是 70kb。 如果你不需要所有额外的废话，Rando.js只有大约 2kb（小 97%），它的工作原理是这样的：
console.log(randoSequence([8, 6, 7, 5, 3, 0, 9]).slice(-5));<script src="https://randojs.com/2.0.0.js"></script>您可以看到它默认跟踪原始索引，以防两个值相同，但您仍然关心选择了哪一个。如果您不需要这些，您可以添加地图，如下所示：
console.log(randoSequence([8, 6, 7, 5, 3, 0, 9]).slice(-5).map((i) => i.value));<script src="https://randojs.com/2.0.0.js"></script>D3-array的洗牌使用费舍尔-叶茨洗牌算法随机重新排序数组。这是一个变异函数 - 这意味着原始数组被重新排序到位，这对性能有好处。
D3 适用于浏览器 - 与 node 一起使用更复杂。
https://github.com/d3/d3-array#shuffle
npm install d3-array
//import {shuffle} from "d3-array"
let x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
d3.shuffle(x)
console.log(x) // it is shuffled<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.0.0/d3.min.js"></script>如果您不想改变原始数组
let x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
let shuffled_x = d3.shuffle(x.slice()) //calling slice with no parameters returns a copy of the original array
console.log(x) // not shuffled
console.log(shuffled_x) <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.0.0/d3.min.js"></script>相关文章：
- 在Javascript中列出顺序子集元素
- Javascript-分层采样
- 根据屏幕大小显示主干.js集合的子集
- 修改 html 的子集并使用 jquery 附加它
- 是否可以创建一个对象，该对象是另一个对象的子集，而不会丢失javascript中的引用
- 从数组中随机采样子集
- 使用 D3 选择圆的子集
- 仅在引导程序表单助手国家/地区选取器中显示国家/地区子集文本
- Javascript:尝试从多个没有匹配的数组中采样，在不应该的时候循环递增
- jQuery:一旦加载了图像的子集，就执行函数
- 将JSON解析为子集
- 将数组分解为子集
- 转换Web音频API中的采样率
- 我可以发布谷歌分析数据的有限子集吗
- 如何运行单元测试子集与因果报应成角度
- PHP/JavaScript MP3播放器，用于采样和销售歌曲
- 当我在jmeter中使用带有脚本的Beanshell采样器时，我遇到了错误
- 使用数组的随机子集生成表
- 如何检查子集数组是否包含超集数组之一
- 玩框架如何获取JPA对象中字段的子集并在模板中处理它
