Sampel acak berbobot dari item array * tanpa penggantian *

Question

Solusi spesifik Javascript / ECMAScript 6 yang diinginkan.

Saya ingin menghasilkan sampel acak dari array objek menggunakan array nilai tertimbang untuk setiap objek. Daftar populasi berisi anggota populasi yang sebenarnya - bukan jenis anggotanya. Setelah satu dipilih untuk sampel, itu tidak dapat dipilih lagi.

Masalah serupa dengan masalah yang sedang saya tangani adalah mensimulasikan kemungkinan hasil untuk turnamen catur. Peringkat setiap pemain akan menjadi bobot mereka. Seorang pemain hanya dapat menempatkan satu kali (juara 1, 2, atau 3) per turnamen.

Untuk memilih daftar 3 pemenang teratas yang mungkin terlihat seperti:

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

Daftar berbobot mungkin, atau mungkin tidak, berupa nilai integer. Ini bisa berupa float [0.2, 0.1, 0.7, 0.3], atau bisa juga seperti integer [20, 10, 70, 30]. Bobot tidak harus berjumlah sampai nilai yang mewakili 100%.

Peter di bawah ini memberi saya referensi yang bagus tentang algoritme umum, namun ini tidak spesifik untuk JS: https://stackoverflow.com/a/62459274/7915759 ini mungkin titik referensi yang bagus.

Solusi untuk masalah yang bergantung pada pembuatan daftar populasi kedua dengan setiap anggota jumlah berat yang disalin beberapa kali mungkin bukan solusi praktis. Setiap bobot dalam larik bobot bisa berupa angka yang sangat tinggi, atau bisa juga pecahan; pada dasarnya, nilai non-negatif apa pun.

Beberapa pertanyaan tambahan:

• Apakah sudah ada accumulate()fungsi yang tersedia di JS?
• Apakah ada bisect()fungsi tipe di JS yang melakukan pencarian biner dari daftar yang diurutkan?
• Adakah modul JS footprint memori yang efisien dan rendah yang tersedia dengan fungsi statistik yang mencakup solusi untuk hal di atas?

Answer 1

Implementasi berikut memilih kdari nelemen, tanpa penggantian, dengan probabilitas tertimbang, di O (n + k log n) dengan menjaga akumulasi bobot dari elemen yang tersisa dalam jumlah heap :

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

Kode tersebut ditulis dalam TypeScript. Anda dapat memindahkannya ke versi EcmaScript apa pun yang Anda butuhkan di taman bermain TypeScript .

Kode tes:

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

Dieksekusi di Chrome, ini mengambil sampel 5.000.000 dari 10.000.000 entri dalam waktu sekitar 10 detik.

Answer 2

Ini adalah satu pendekatan, tetapi bukan yang paling efisien.

Fungsi level tertinggi. Ini berulang kkali, menelepon wchoice()setiap kali. Untuk menghapus anggota yang saat ini dipilih dari populasi, saya hanya mengatur bobotnya menjadi 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];
}

Bagian kode di atas yang memperbarui larik bobot yang terakumulasi adalah titik inefisiensi dalam algoritme. Kasus terburuk adalah O(n - ?)memperbarui setiap kali lulus. Solusi lain di sini mengikuti algoritme yang mirip dengan ini, tetapi menggunakan heap untuk mengurangi pekerjaan yang diperlukan untuk mempertahankan array bobot yang terakumulasi di O(log n).

wsample()panggilan wchoice()yang memilih satu anggota dari daftar berbobot. wchoice()menghasilkan larik bobot kumulatif, menghasilkan angka acak dari 0 hingga jumlah total bobot (item terakhir dalam daftar bobot kumulatif). Kemudian temukan titik penyisipannya dalam bobot kumulatif; yang mana pemenangnya:

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

Berikut adalah implementasi JS yang saya adaptasi dari algoritma pencarian biner 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;
}

Saya tidak dapat menemukan fungsi akumulator yang siap pakai untuk JS, jadi saya menulis yang sederhana sendiri.

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