JavaScript: более быстрый выбор рулетки

Question

Я реализую алгоритм выбора, который выбирает объект на основе вероятности, пропорциональной его score значение. Это повышает вероятность выбора объектов с более высокой оценкой.

Моя реализация выглядит следующим образом:

var pool = [];
for (var i = 0; i < 100; i++)
    pool.push({ Id: i, Score: Math.random() * 100 << 0 });

const NUM_RUNS = 100000;
var start = new Date();
for( var i = 0; i < NUM_RUNS; i++ )
  rouletteSelection(pool);
var end = new Date();

var runningTime = (end.getTime() - start.getTime()) / 1000;
var avgExecutionTime = ( runningTime / NUM_RUNS ) * Math.pow(10,9);
console.log('Running Time: ' + runningTime + ' seconds');
console.log('Avg. Execution Time: ' + avgExecutionTime + ' nanoseconds');


function rouletteSelection(pool) {
        // Sum all scores and normalize by shifting range to minimum of 0
        var sumScore = 0, lowestScore = 0;
        pool.forEach((obj) => {
            sumScore += obj.Score;
            if (obj.Score < lowestScore)
                lowestScore = obj.Score;
        })
        sumScore += Math.abs(lowestScore * pool.length);
    
        var rouletteSum = 0;
        var random = Math.random() * sumScore << 0;
        for (var i in pool) {
            rouletteSum += pool[i].Score + lowestScore;
            if (random < rouletteSum)
                return pool[i];
        }
    
        //Failsafe
        console.warn('Could not choose roulette winner, selecting random');
        return pool[Math.random() * pool.length];
};

При запуске производительность неплохая: на моей машине каждый вызов rouleteSelection() занимает около 2500-3200 наносекунд. Однако, прежде чем использовать его в производстве, я хочу оптимизировать этот процесс и сократить как можно больше накладных расходов, так как эта функция может быть вызвана десятки миллионов раз в крайних случаях.

Очевидной оптимизацией было бы как-то объединить все в один цикл, чтобы массив объектов повторялся только один раз. Проблема в том, что для того, чтобы нормализовать оценки (отрицательные оценки смещены до 0), мне нужно знать наименьшую оценку для начала.

У кого-нибудь есть идеи относительно того, как обойти это?

Answer 1

С риском констатировать очевидное: просто не делайте нормализацию при каждом вызове rouletteSelection, Сделайте это один раз, после того как вы построили pool,