Javascript中的加权随机数生成 [英] Weighted random number generation in Javascript

问题描述

我有一个看起来像这样的数组：

I have an array that looks something like this:

[
    {
        plays: 0,
        otherData: someValues
    }, {
        plays: 4,
        otherData: someValues
    }, {
        plays: 1,
        otherData: someValues
    }, {
        plays: 2,
        otherData: someValues
    } {
        plays: 9,
        otherData: someValues
    }, {
        plays: 7,
        otherData: someValues
    }, {
        plays: 5,
        otherData: someValues
    }, {
        plays: 0,
        otherData: someValues
    }, {
        plays: 8,
        otherData: someValues
    }
]

这是关于播放列表中歌曲的一系列信息，其中播放是歌曲播放的次数。我试图想出一个加权随机数生成器，它将选择一个元素的索引，加权使得较少播放的歌曲更有可能被选中。这是我现在的代码：

It's an array of information about songs in a playlist, where plays is the number of times a song has been played. I' trying to come up with a weighted random number generator that will pick an index of an element, weighted such that less-played songs are more likely to be picked. Here's the code I have now:

function pickRandom(){
    var oldIndex = index;
    if(songs.length <= 1)
        return index = 0;
    var unheard = [];
    for(i in songs){
        if(!songs[i].plays)
            unheard.push(i);
    }if(unheard.length > 0)
        return index = unheard[Math.round(Math.random() * (unheard.length - 1))];
    var tries = 0;
    while(index == oldIndex && tries < 100){
        index = Math.round(Math.random() * (songs.length - 1));
        tries++;
    }return index;
}

这个解决方案有很多我不满意的事情。首先，它没有加权，因为它真的只是选择一首未播放的歌曲，或任何旧的随机曲目，如果阵列中的所有内容至少播放过一次。其次，它会创建一个新的数组，因为播放列表有时会有数百首歌曲，如果可能的话，我想远离它。

There are a number of things with this solution that I'm unhappy with. First off, it's not weighted so much as it really just picks an unplayed song, or any old random one if everything in the array has been played at least once. Second, it creates a new array, and since playlists will sometimes have hundreds of songs, that's something I'd like to steer away from if possible.

最接近的解决方案我已经能够想出基于其播放值多次将每个元素复制到一个新数组中，然后从中选择一个元素，但这会使问题恶化创建一个新数组，因为第二个数组可以很容易地达到数千个元素。我非常感谢任何帮助或建议;甚至伪代码都没问题。

The closest solution I've been able to come up with is copying each element into a new array multiple times based on its plays value, then pick an element out of that, but that worsens the issue of creating a new array, since that second array could easily reach thousands of elements. I'd be much appreciative of any help or suggestions; even pseudocode would be fine.

推荐答案

我会做你想做的循环。总计列表中任何歌曲的最大播放次数，然后通过计算反向加权的数字并从反向总计中选择来反转概率。这样的事情：

I would do what you want to do with loops. Total up the max number of plays for any song in the list, then reverse the probability by calculating a number that is reverse weighted and choosing from the reverse total. Something like this:

function pickRandom(myArray) {
    var maxPlays = 0, reverseTotPlays = 0, ipl, picked, revAcc = 0;

    // Empty array or bad input param
    if (!myArray || !myArray.length) {
        return -1;
    }

    // Calculate the max plays for any song in the list
    for (ipl = 0;  ipl < myArray.length;  ++ipl) {
        if (myArray[ipl].plays > maxPlays) {
            maxPlays = myArray[ipl].plays;
        }
    }
    maxPlays += 1;   // Avoid excluding max songs

    // Calculate the reverse weighted total plays
    for (ipl = 0;  ipl < myArray.length;  ++ipl) {
        reverseTotPlays += maxPlays - myArray[ipl].plays;
    }

    // Choose a random number over the reverse weighted spectrum
    picked = ~~(Math.random() * reverseTotPlays);

    // Find which array member the random number belongs to
    for (ipl = 0;  ipl < myArray.length;  ++ipl) {
        revAcc += maxPlays - myArray[ipl].plays;
        if (revAcc > picked) {
            return ipl;
        }
    }
    return myArray.length - 1;
}

var pp = [{ plays: 3 }, { plays: 1 }, { plays: 2 }];
console.log(pickRandom(pp));

工作JSFiddle 这里

Working JSFiddle Here

编辑：如果您不希望播放已播放的歌曲的概率为零在列表中播放了最多次，在第一次循环后为maxPlay添加+1。

Edit: If you don't want a zero probability on playing the songs that have been played the max times in the list, add +1 to maxPlays after the first loop.

这篇关于Javascript中的加权随机数生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！