Échantillon aléatoire pondéré d'éléments du tableau * sans remplacement *
Solution spécifique Javascript / ECMAScript 6 souhaitée.
Je souhaite générer un échantillon aléatoire à partir d'un tableau d'objets en utilisant un tableau de valeurs pondérées pour chaque objet. La liste de population contient les membres réels de la population - pas les types de membres. Une fois qu'un échantillon est sélectionné pour un échantillon, il ne peut plus être sélectionné.
Un problème analogue à celui sur lequel je travaille serait de simuler un résultat probable pour un tournoi d'échecs. La cote de chaque joueur serait son poids. Un joueur ne peut se placer qu'une seule fois (1ère, 2ème ou 3ème place) par tournoi.
Pour choisir une liste probable des 3 meilleurs gagnants, cela pourrait ressembler à:
let winners = wsample(chessPlayers, // population
playerRatings, // weights
3); // sample size
La liste pondérée peut être ou non des valeurs entières. Cela peut être des flottants comme [0.2, 0.1, 0.7, 0.3]
ou des entiers comme [20, 10, 70, 30]
. Les pondérations n'ont pas à s'additionner à une valeur qui représente 100%.
Peter ci-dessous m'a donné une bonne référence sur un algorithme général, mais ce n'est pas spécifique à JS: https://stackoverflow.com/a/62459274/7915759 cela peut être un bon point de référence.
Les solutions au problème qui reposent sur la génération d'une deuxième liste de population avec chaque membre copié le nombre de fois de poids peuvent ne pas être une solution pratique. Chaque poids dans le tableau des poids peut être un nombre très élevé ou fractionnaire; fondamentalement, toute valeur non négative.
Quelques questions supplémentaires:
- Existe-t-il déjà une
accumulate()
fonction disponible dans JS? - Existe-t-il une
bisect()
fonction de type dans JS qui effectue une recherche binaire dans les listes triées? - Existe-t-il des modules JS efficaces et à faible encombrement mémoire avec des fonctions statistiques qui incluent des solutions pour ce qui précède?
Réponses
L'implémentation suivante sélectionne k
des n
éléments, sans remplacement, avec des probabilités pondérées, dans O (n + k log n) en conservant les poids cumulés des éléments restants dans un tas de somme :
function sample_without_replacement<T>(population: T[], weights: number[], sampleSize: number) {
let size = 1;
while (size < weights.length) {
size = size << 1;
}
// construct a sum heap for the weights
const root = 1;
const w = [...new Array(size) as number[], ...weights, 0];
for (let index = size - 1; index >= 1; index--) {
const leftChild = index << 1;
const rightChild = leftChild + 1;
w[index] = (w[leftChild] || 0) + (w[rightChild] || 0);
}
// retrieves an element with weight-index r
// from the part of the heap rooted at index
const retrieve = (r: number, index: number): T => {
if (index >= size) {
w[index] = 0;
return population[index - size];
}
const leftChild = index << 1;
const rightChild = leftChild + 1;
try {
if (r <= w[leftChild]) {
return retrieve(r, leftChild);
} else {
return retrieve(r - w[leftChild], rightChild);
}
} finally {
w[index] = w[leftChild] + w[rightChild];
}
}
// and now retrieve sampleSize random elements without replacement
const result: T[] = [];
for (let k = 0; k < sampleSize; k++) {
result.push(retrieve(Math.random() * w[root], root));
}
return result;
}
Le code est écrit en TypeScript. Vous pouvez le transpiler dans la version d'EcmaScript dont vous avez besoin dans le terrain de jeu TypeScript .
Code de test:
const n = 1E7;
const k = n / 2;
const population: number[] = [];
const weight: number[] = [];
for (let i = 0; i < n; i++) {
population[i] = i;
weight[i] = i;
}
console.log(`sampling ${k} of ${n} elments without replacement`);
const sample = sample_without_replacement(population, weight, k);
console.log(sample.slice(0, 100)); // logging everything takes forever on some consoles
console.log("Done")
Exécuté dans Chrome, il échantillonne 5 000 000 entrées sur 10 000 000 en 10 secondes environ.
C'est une approche, mais pas la plus efficace.
La fonction de niveau le plus élevé. Il itère les k
temps, en appelant à wchoice()
chaque fois. Pour supprimer le membre actuellement sélectionné de la population, je viens de définir son poids sur 0.
/**
* Produces a weighted sample from `population` of size `k` without replacement.
*
* @param {Object[]} population The population to select from.
* @param {number[]} weights The weighted values of the population.
* @param {number} k The size of the sample to return.
* @returns {[number[], Object[]]} An array of two arrays. The first holds the
* indices of the members in the sample, and
* the second holds the sample members.
*/
function wsample(population, weights, k) {
let sample = [];
let indices = [];
let index = 0;
let choice = null;
let acmwts = accumulate(weights);
for (let i=0; i < k; i++) {
[index, choice] = wchoice(population, acmwts, true);
sample.push(choice);
indices.push(index);
// The below updates the accumulated weights as if the member
// at `index` has a weight of 0, eliminating it from future draws.
// This portion could be optimized. See note below.
let ndecr = weights[index];
for (; index < acmwts.length; index++) {
acmwts[index] -= ndecr;
}
}
return [indices, sample];
}
La section de code ci-dessus qui met à jour le tableau des poids accumulés est le point d'inefficacité de l'algorithme. Le pire des cas est O(n - ?)
de mettre à jour à chaque passage. Une autre solution ici suit un algorithme similaire à celui-ci, mais utilise un tas pour réduire le travail nécessaire pour maintenir le tableau de poids accumulé à O(log n)
.
wsample()
appels wchoice()
qui sélectionne un membre dans la liste pondérée. wchoice()
génère un tableau de poids cumulés, génère un nombre aléatoire de 0 à la somme totale des poids (dernier élément de la liste des poids cumulés). Trouve ensuite son point d'insertion dans les poids cumulés; qui est le gagnant:
/**
* Randomly selects a member of `population` weighting the probability each
* will be selected using `weights`. `accumulated` indicates whether `weights`
* is pre-accumulated, in which case it will skip its accumulation step.
*
* @param {Object[]} population The population to select from.
* @param {number[]} weights The weights of the population.
* @param {boolean} [accumulated] true if weights are pre-accumulated.
* Treated as false if not provided.
* @returns {[number, Object]} An array with the selected member's index and
* the member itself.
*/
function wchoice(population, weights, accumulated) {
let acm = (accumulated) ? weights : accumulate(weights);
let rnd = Math.random() * acm[acm.length - 1];
let idx = bisect_left(acm, rnd);
return [idx, population[idx]];
}
Voici une implémentation JS que j'ai adaptée de l'algorithme de recherche binaire de https://en.wikipedia.org/wiki/Binary_search_algorithm
/**
* Finds the left insertion point for `target` in array `arr`. Uses a binary
* search algorithm.
*
* @param {number[]} arr A sorted ascending array.
* @param {number} target The target value.
* @returns {number} The index in `arr` where `target` can be inserted to
* preserve the order of the array.
*/
function bisect_left(arr, target) {
let n = arr.length;
let l = 0;
let r = n - 1;
while (l <= r) {
let m = Math.floor((l + r) / 2);
if (arr[m] < target) {
l = m + 1;
} else if (arr[m] >= target) {
r = m - 1;
}
}
return l;
}
Je n'ai pas pu trouver une fonction d'accumulateur prête à l'emploi pour JS, alors j'en ai écrit une simple moi-même.
/**
* Generates an array of accumulated values for `numbers`.
* e.g.: [1, 5, 2, 1, 5] --> [1, 6, 8, 9, 14]
*
* @param {number[]} numbers The numbers to accumulate.
* @returns {number[]} An array of accumulated values.
*/
function accumulate(numbers) {
let accm = [];
let total = 0;
for (let n of numbers) {
total += n;
accm.push(total)
}
return accm;
}