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.

之后执行一次

JavaScript：更快的轮盘选择

JavaScript: Faster roulette selection

javascript

optimization

v8

micro-optimization