प्रतिस्थापन के बिना सरणी आइटम * का भारित यादृच्छिक नमूना *

Nov 28 2020

जावास्क्रिप्ट / ECMAScript 6 विशिष्ट समाधान वांछित।

मैं प्रत्येक वस्तु के लिए भारित मूल्यों की एक सरणी का उपयोग करके वस्तुओं की एक सरणी से एक यादृच्छिक नमूना उत्पन्न करना चाहता हूं। जनसंख्या सूची में जनसंख्या के वास्तविक सदस्य होते हैं - सदस्यों के प्रकार नहीं। एक बार एक नमूने के लिए चुने जाने के बाद, इसे फिर से नहीं चुना जा सकता है।

मैं जिस पर काम कर रहा हूं, उसके अनुरूप समस्या शतरंज के टूर्नामेंट के संभावित परिणाम का अनुकरण करने वाली होगी। प्रत्येक खिलाड़ी की रेटिंग उनका वजन होगी। एक खिलाड़ी प्रति टूर्नामेंट केवल एक बार (प्रथम, द्वितीय या तृतीय स्थान) स्थान पा सकता है।

शीर्ष 3 विजेताओं की एक संभावित सूची लेने के लिए ऐसा देख सकते हैं:

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

भारित सूची पूर्णांक मान हो सकती है, या नहीं भी हो सकती है। यह जैसे तैरता है [0.2, 0.1, 0.7, 0.3], या यह पूर्णांक की तरह हो सकता है [20, 10, 70, 30]। वजन में 100% का प्रतिनिधित्व करने वाले मूल्य को जोड़ना नहीं है।

पीटर ने मुझे एक सामान्य एल्गोरिथ्म पर एक अच्छा संदर्भ दिया, हालाँकि यह JS के लिए विशिष्ट नहीं है: https://stackoverflow.com/a/62459274/7915759 यह संदर्भ का एक अच्छा बिंदु हो सकता है।

समस्या का समाधान जो कि प्रत्येक सदस्य की वजन की संख्या के साथ दूसरी जनसंख्या सूची बनाने पर निर्भर करता है, वह व्यावहारिक समाधान नहीं हो सकता है। वजन सरणी में प्रत्येक वजन बहुत अधिक संख्या में हो सकता है, या वे आंशिक हो सकते हैं; मूल रूप से, कोई भी गैर-नकारात्मक मूल्य।

कुछ अतिरिक्त प्रश्न:

  • क्या accumulate()जेएस में पहले से कोई फंक्शन उपलब्ध है?
  • bisect()जेएस में एक प्रकार का कार्य है जो क्रमबद्ध सूचियों की एक द्विआधारी खोज करता है?
  • क्या कोई कुशल और कम स्मृति पदचिह्न जेएस मॉड्यूल सांख्यिकीय कार्यों के साथ उपलब्ध हैं जिनमें उपरोक्त के लिए समाधान शामिल हैं?

जवाब

1 meriton Nov 29 2020 at 11:44

निम्नलिखित कार्यान्वयन तत्वों से kबाहर का चयन करता है n, प्रतिस्थापन के बिना, भारित संभावनाओं के साथ, ओ (एन + के लॉग एन) में शेष राशि के संचित भार को एक ही ढेर में रखकर :

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

कोड टाइपस्क्रिप्ट में लिखा गया है। आप टाइपमैप खेल के मैदान में एक्मास्क्रिप्ट के जो भी संस्करण की आवश्यकता है, उसे ट्रांसपाइल कर सकते हैं ।

टेस्ट कोड:

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

क्रोम में निष्पादित, यह 10 सेकंड में 10 से 000 प्रविष्टियों में से 5 000 000 का नमूना देता है।

Todd Nov 28 2020 at 12:35

यह एक दृष्टिकोण है, लेकिन सबसे कुशल नहीं है।

उच्चतम स्तर समारोह। यह हर बार kकॉल wchoice()करते समय , पुनरावृति करता है। वर्तमान में चयनित सदस्य को आबादी से हटाने के लिए, मैंने अभी इसका वजन 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];
}

ऊपर के कोड का कोड जो अपडेटेड वेट ऐरे को अपडेट करता है, एल्गोरिथम में अक्षमता का बिंदु है। सबसे खराब स्थिति यह है O(n - ?)कि हर पास को अपडेट किया जाए। यहां एक अन्य समाधान इसी तरह के एल्गोरिथ्म का अनुसरण करता है, लेकिन संचित भार सरणी को बनाए रखने के लिए आवश्यक कार्य को कम करने के लिए एक ढेर का उपयोग करता है O(log n)

wsample()कॉल wchoice()जो भारित सूची से एक सदस्य का चयन करती है। wchoice()संचयी भार की एक सरणी उत्पन्न करता है, वजन के कुल योग से एक यादृच्छिक संख्या उत्पन्न करता है (संचयी भार सूची में अंतिम आइटम)। फिर संचयी भार में इसके सम्मिलन बिंदु को पाता है; विजेता कौन है:

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

यहां एक जेएस कार्यान्वयन है जिसे मैं बाइनरी खोज एल्गोरिदम से अनुकूलित करता हूं 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;
}

मैं जेएस के लिए एक संचयकर्ता फ़ंक्शन तैयार करने में सक्षम नहीं था, इसलिए मैंने खुद को एक सरल लिखा।

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