Эффективная версия / альтернатива методу псевдонима, который выбирает без замены

Question

Я пишу викторину / обучающую игру на HTML5/JS, в которой игроку предлагается набор из 10 вопросов из более широкого набора мастерства. Игра отслеживает оценки игроков с течением времени и с большей вероятностью выбирает вопросы из списка вопросов, с которыми у игрока возникают проблемы.

Чтобы построить список распределения вероятностей, я использую метод псевдонимов, как показано ниже, который выбирает элемент за O(1) время, полностью придерживаясь распределения:

function generate_random_question_selector() {
    // Generates a random selector function using the Alias Method
    // for discrete probability distributions (see
    // https://en.wikipedia.org/wiki/Alias_method for an explanation)
    var i = 0;
    var probabilities = [], aliases = [];
    var probSum = 0;

    /* ... Business logic to fill probabilities array ... */

    // Normalize all probabilities to average to 1
    // and categorize each probability as to where it fits
    // in that scale
    var probMultiplier = probabilities.length / probSum;
    var overFull = [], underFull = [];
    probabilities = probabilities.map(function(p, i) {
        var newP = p * probMultiplier;
        if (newP > 1) overFull.push(i);
        else if (newP < 1) underFull.push(i);
        else if (newP !== 1) {
            throw "Non-numerical value got into scores";
        }
        return newP;
    });
    overFull.sort();
    underFull.sort();

    // Process both queues by having each under-full entry
    // have the rest of its space occupied by the fullest
    // over-full entry, re-categorizing the over-full entry
    // as needed
    while (overFull.length > 0 || underFull.length > 0) {
        if (!(overFull.length > 0 && underFull.length > 0)) {
            // only reached due to rounding errors.
            // Just assign all the remaining probabilities to 1
            var notEmptyArray = overFull.length > 0 ? overFull : underFull;
            notEmptyArray.forEach(function(index) {
                probabilities[index] = 1;
            });
            break; // get out of the while loop
        }

        aliases[underFull[0]] = overFull[0];
        probabilities[overFull[0]] += probabilities[underFull[0]] - 1;
        underFull.shift();
        if (probabilities[overFull[0]] > 1) overFull.push(overFull.shift());
        else if (probabilities[overFull[0]] < 1) underFull.push(overFull.shift());
        else overFull.shift();
    }

    return function() {
        var index = Math.floor(Math.random() * probabilities.length);
        return Math.random() < probabilities[index] ? index : aliases[index];
    }
}

Этот метод работает очень хорошо, но часть моих бизнес-спецификаций заключается в том, что вопросы не повторяются. В настоящее время я использую наивную технику перебора для достижения этой цели, но очевидно, что она сломается, если менее 10 элементов гораздо более вероятны, чем остальные элементы:

var selectQuestion = generate_random_question_selector();   
var questionSet = [];
for (var i = 0; i < num_questions; i++) {
    var question_num;
    do {
        question_num = selectQuestion();
    } while (questionSet.indexOf(question_num) >= 0)
    questionSet.push(question_num);
}

Что можно сделать с этим методом или с этим методом, который позволил бы мне эффективно отбирать вопросы без замены?

Answer 1

Метод псевдонимов плохо подходит для выборки без замены, потому что каждое значение выбирается с использованием различного распределения вероятностей, и при вычислении (или обновлении) таблицы псевдонимов O(n).

Вам нужна структура данных, которая может быть обновлена ​​более эффективно. Например, вы могли бы построить дерево поиска всех значений (где каждый узел хранит общий вес своего поддерева), что позволило бы осуществлять выборку и обновление распределения вероятностей в O(log n).

Если мы удалим записи, установив их вероятность в 0, это дерево никогда не будет структурно изменено и может быть закодировано в массив.

Вот некоторый код:

function prepare() {
    // index i is the parent of indices 2*i and 2*i+1
    // therefore, index 0 is unused, and index 1 the root of the tree
    var i;
    for (i = weights.length - 1; i > 1; i--) {
        weights[i >> 1] += weights[i];
    }
}

function sample() {
    var index = 1;
    var key = Math.random() * weights[index];

    for (;;) {
        var left = index << 1;
        var right = left + 1;
        leftWeight = weights[left] || 0;
        rightWeight = weights[right] || 0;

        if (key < leftWeight) {
            index = left;
        } else {
            key -= leftWeight;
            if (key < rightWeight) {
                index = right;
            } else {
                return index;
            }
        }
    }
}

function remove(index) {
    var left = index << 1;
    var right = left + 1;
    leftWeight = weights[left] || 0;
    rightWeight = weights[right] || 0;

    var w = weights[index] - leftWeight - rightWeight;
    while (index > 0) {
        weights[index] -= w;
        index = index >> 1;
    }
}

Тестовый код:

function retrieve() {
    var index = sample();
    remove(index);
    console.log(index);
    console.log(weights);
}

weights = [0,1,2,3,4];
prepare();
console.log(weights);
retrieve();
retrieve();
retrieve();
retrieve();