配列アイテムの重み付けされたランダムサンプル置換なし

Nov 28 2020

Javascript / ECMAScript6固有のソリューションが必要です。

各オブジェクトの重み付き値の配列を使用して、オブジェクトの配列からランダムサンプルを生成したいと思います。母集団リストには、メンバーのタイプではなく、母集団の実際のメンバーが含まれています。サンプル用に1つを選択すると、それを再度選択することはできません。

私が取り組んでいる問題に類似した問題は、チェスのトーナメントの予想される結果をシミュレートすることです。各プレイヤーの評価は彼らの体重になります。プレイヤーはトーナメントごとに1回（1位、2位、または3位）しか配置できません。

上位3人の勝者の可能性のあるリストを選択するには、次のようになります。

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

加重リストは整数値である場合とそうでない場合があります。のような浮動小数点数でも[0.2, 0.1, 0.7, 0.3]、のような整数でもかまいません[20, 10, 70, 30]。重みは、100％を表す値まで合計する必要はありません。

以下のPeterは、一般的なアルゴリズムに関する優れたリファレンスを提供してくれましたが、JSに固有のものではありません。 https://stackoverflow.com/a/62459274/7915759 それは参考になるかもしれません。

各メンバーが重みを何度もコピーして2番目の母集団リストを生成することに依存する問題の解決策は、実用的な解決策ではない場合があります。重み配列の各重みは非常に高い数値である場合もあれば、分数である場合もあります。基本的に、負でない値。

いくつかの追加の質問：

accumulate()JSで利用できる機能はもうありますか？
bisect()ソートされたリストのバイナリ検索を行うJSのタイプ関数はありますか？
上記のソリューションを含む統計関数で利用できる効率的でメモリフットプリントの少ないJSモジュールはありますか？

回答

1 meriton Nov 29 2020 at 11:44

次の実装では、残りの要素の累積された重みを合計ヒープに保持することにより、O（n + k log n）で、重み付き確率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;
}

コードはTypeScriptで書かれています。TypeScriptプレイグラウンドで必要なバージョンのEcmaScriptにトランスパイルできます。

テストコード：

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

Chromeで実行すると、約10秒で10 000000エントリから5000000をサンプリングします。

Todd Nov 28 2020 at 12:35

これは1つのアプローチですが、最も効率的ではありません。

最高レベルの機能。それは時間を繰り返し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()加重リストから1つのメンバーを選択する呼び出し。wchoice()累積重みの配列を生成し、0から重みの合計（累積重みリストの最後の項目）までの乱数を生成します。次に、累積重みでその挿入ポイントを見つけます。どちらが勝者です：

配列アイテムの重み付けされたランダムサンプル*置換なし*

回答

配列アイテムの重み付けされたランダムサンプル置換なし