javascript - Javascript中的加权随机数生成

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

[
    {
        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
    }
]

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

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;
}

这个解决方案有很多我不满意的地方。首先，它的权重没有那么大，因为它实际上只是选择一首未播放的歌曲，或者任何旧的随机歌曲，如果数组中的所有内容都至少播放过一次。其次，它会创建一个新数组，而且由于播放列表有时会包含数百首歌曲，因此如果可能的话，我希望避免这种情况。

我能想出的最接近的解决方案是根据每个元素的 plays 值将每个元素多次复制到一个新数组中，然后从中挑选一个元素，但这会使创建新数组的问题变得更糟，因为那一秒数组可以轻松达到数千个元素。我将非常感谢任何帮助或建议；即使是伪代码也可以。

最佳答案

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

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 Here

编辑 :如果您不希望播放列表中播放次数最多的歌曲的概率为零，请在第一次循环后将 +1 添加到 maxPlays。

关于javascript - Javascript中的加权随机数生成，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12515994/