Ważona losowa próbka elementów tablicy * bez wymiany *

Question

Pożądane jest specyficzne rozwiązanie Javascript / ECMAScript 6.

Chcę wygenerować losową próbkę z tablicy obiektów przy użyciu tablicy wartości ważonych dla każdego obiektu. Lista populacji zawiera rzeczywistych członków populacji, a nie typy członków. Po wybraniu jednego z próbek nie można go ponownie wybrać.

Analogicznym problemem do tego, nad którym pracuję, byłaby symulacja prawdopodobnego wyniku turnieju szachowego. Ocena każdego gracza byłaby jego wagą. Gracz może zająć tylko raz (1., 2. lub 3. miejsce) w turnieju.

Aby wybrać prawdopodobną listę 3 najlepszych zwycięzców, może wyglądać następująco:

let winners = wsample(chessPlayers,  // population
                      playerRatings, // weights
                      3);            // sample size

Lista ważona może, ale nie musi, być wartościami całkowitymi. Mogą [0.2, 0.1, 0.7, 0.3]to być liczby zmiennoprzecinkowe lub liczby całkowite, takie jak [20, 10, 70, 30]. Wagi nie muszą sumować się do wartości reprezentującej 100%.

Peter poniżej dał mi dobre odniesienie do ogólnego algorytmu, jednak nie jest on specyficzny dla JS: https://stackoverflow.com/a/62459274/7915759 może to być dobry punkt odniesienia.

Rozwiązania problemu, które polegają na generowaniu drugą listę ludności w każdym państwie kopiowane wagi , ile razy może być praktycznym rozwiązaniem. Każda waga w tablicy wag może być bardzo dużą liczbą lub może być ułamkowa; w zasadzie każda nieujemna wartość.

Kilka dodatkowych pytań:

• Czy accumulate()w JS jest już dostępna funkcja?
• Czy bisect()w JS istnieje funkcja typu, która wyszukuje binarnie posortowane listy?
• Czy są dostępne jakieś wydajne i zajmujące mało pamięci moduły JS z funkcjami statystycznymi, które obejmują rozwiązania dla powyższych?

Answer 1

Następująca implementacja wybiera kz nelementów, bez zamiany, z ważonymi prawdopodobieństwami, w O (n + k log n), zachowując skumulowane wagi pozostałych elementów w stosie sumarycznym :

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;
}

Kod jest napisany w języku TypeScript. Możesz transponować go do dowolnej wersji EcmaScript, której potrzebujesz na placu zabaw TypeScript .

Kod testowy:

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")

Wykonany w przeglądarce Chrome, pobiera 5 000 000 z 10 000 000 wpisów w około 10 sekund.

Answer 2

To jedno podejście, ale nie najbardziej wydajne.

Funkcja na najwyższym poziomie. Iteruje krazy, wywołując za wchoice()każdym razem. Aby usunąć aktualnie wybranego członka z populacji, ustawiam jego wagę na 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];
}

Sekcja powyższego kodu, która aktualizuje skumulowaną tablicę wag, jest punktem nieefektywności algorytmu. W najgorszym przypadku jest to O(n - ?)aktualizacja przy każdym przejściu. Inne rozwiązanie stosuje podobny algorytm do tego, ale używa sterty w celu zmniejszenia pracy potrzebnej do utrzymania skumulowanej tablicy wag na poziomie O(log n).

wsample()wywołania, wchoice()które wybierają jednego członka z listy ważonej. wchoice()generuje tablicę skumulowanych wag, generuje liczbę losową od 0 do sumy łącznej wag (ostatnia pozycja na liście wag skumulowanych). Następnie znajduje punkt wstawienia w skumulowanych wagach; który jest zwycięzcą:

/**
 * 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]];
}

Oto implementacja JS, którą zaadaptowałem z algorytmu wyszukiwania binarnego z 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;
}

Nie mogłem znaleźć gotowej funkcji akumulatora dla JS, więc sam napisałem prostą.

/**
 * 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;
}