Gewichtete Zufallsstichprobe von Array-Elementen * ohne Ersatz *
Javascript / ECMAScript 6 spezifische Lösung gewünscht.
Ich möchte eine Zufallsstichprobe aus einem Array von Objekten unter Verwendung eines Arrays gewichteter Werte für jedes Objekt generieren. Die Bevölkerungsliste enthält die tatsächlichen Mitglieder der Bevölkerung - nicht die Arten von Mitgliedern. Sobald eine für eine Probe ausgewählt wurde, kann sie nicht mehr ausgewählt werden.
Ein analoges Problem zu dem, an dem ich arbeite, wäre die Simulation eines wahrscheinlichen Ergebnisses für ein Schachturnier. Die Bewertung jedes Spielers wäre sein Gewicht. Ein Spieler kann nur einmal (1., 2. oder 3. Platz) pro Turnier platzieren.
Eine wahrscheinliche Liste der drei besten Gewinner könnte folgendermaßen aussehen:
let winners = wsample(chessPlayers, // population
playerRatings, // weights
3); // sample size
Die gewichtete Liste kann ganzzahlige Werte sein oder nicht. Es könnten Floats wie [0.2, 0.1, 0.7, 0.3]
oder Ganzzahlen sein [20, 10, 70, 30]
. Die Gewichte müssen sich nicht zu einem Wert addieren, der 100% darstellt.
Peter unten gab mir eine gute Referenz zu einem allgemeinen Algorithmus, der jedoch nicht spezifisch für JS ist: https://stackoverflow.com/a/62459274/7915759 es kann ein guter Bezugspunkt sein.
Lösungen für das Problem, bei denen eine zweite Bevölkerungsliste erstellt werden muss, bei der jedes Mitglied mehrmals gewichtet wird, sind möglicherweise keine praktische Lösung. Jedes Gewicht in der Gewichtsanordnung kann eine sehr hohe Zahl oder ein Bruchteil sein. Grundsätzlich jeder nicht negative Wert.
Einige zusätzliche Fragen:
- Ist
accumulate()
in JS bereits eine Funktion verfügbar? - Gibt es
bisect()
in JS eine Typfunktion, die eine binäre Suche nach sortierten Listen durchführt? - Gibt es effiziente JS-Module mit geringem Speicherbedarf und statistischen Funktionen, die Lösungen für die oben genannten Probleme enthalten?
Antworten
Die folgende Implementierung wählt ersatzlos k
aus n
Elementen mit gewichteten Wahrscheinlichkeiten in O (n + k log n) aus, indem die akkumulierten Gewichte der verbleibenden Elemente in einem Summenhaufen gehalten werden :
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;
}
Der Code ist in TypeScript geschrieben. Sie können es auf eine beliebige Version von EcmaScript übertragen, die Sie auf dem TypeScript-Spielplatz benötigen .
Testcode:
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")
In Chrome ausgeführt, werden in etwa 10 Sekunden 5 000 000 von 10 000 000 Einträgen abgetastet.
Dies ist ein Ansatz, aber nicht der effizienteste.
Die Funktion der höchsten Ebene. Es iteriert k
mal und ruft wchoice()
jedes Mal auf. Um das aktuell ausgewählte Mitglied aus der Population zu entfernen, habe ich nur sein Gewicht auf 0 gesetzt.
/**
* 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];
}
Der obige Codeabschnitt, der das Array der akkumulierten Gewichte aktualisiert, ist der Punkt der Ineffizienz im Algorithmus. Im schlimmsten Fall ist es O(n - ?)
bei jedem Durchgang zu aktualisieren. Eine andere Lösung folgt hier einem ähnlichen Algorithmus, verwendet jedoch einen Heap, um die Arbeit zu reduzieren, die erforderlich ist, um das Array mit akkumulierten Gewichten bei zu halten O(log n)
.
wsample()
Anrufe, bei wchoice()
denen ein Mitglied aus der gewichteten Liste ausgewählt wird. wchoice()
generiert ein Array von kumulativen Gewichten, generiert eine Zufallszahl von 0 bis zur Gesamtsumme der Gewichte (letztes Element in der Liste der kumulativen Gewichte). Findet dann seine Einfügemarke in den kumulativen Gewichten; Welches ist der Gewinner:
/**
* 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]];
}
Hier ist eine JS-Implementierung, die ich aus dem binären Suchalgorithmus von angepasst habe 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;
}
Ich konnte keine für JS vorgefertigte Akkumulatorfunktion finden, also habe ich selbst eine einfache geschrieben.
/**
* 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;
}