一种权重算法及其实现

撰写于 2015年5月15日 修改于 2016年7月23日 分类 算法 标签 JavaScript

一大早在V2EX上看到有人讨论一个关于权重的算法，源于题主的面试，他还发了博文，果然，面试他的人夸奖了他的态度。这的确是难得的。

面试官给出的题目如下：

每首歌曲都是一个评分，现在有2000首歌曲，要求实现一个随机播放器，每首歌曲播放的概率应该正比于它的评分，例如评分9.1的歌曲，和评分7.9的歌曲，播放的次数应该是91:79

面试官给出了如下的解决方案：

把评分从小到大排序，之后把根据每首歌的评分，生成一个半闭开区间，然后生成一个随机数，看随机数落在哪个区间，就是选择的那首歌。例如，有三首歌，评分是[1,2,3] 那么应该是生成三个区间 [0-1,1-3,3-6]，之后生成一个0-6之间的随机数，随机数落在哪个区间，就选择对应的歌曲。

被面试的人后来给出的解决方案是：

假定每个评分只到小数点后一位，那么其实，利用空间换取时间的思路，只需要把每首歌按照他的评分多少相应的复制多少重复的歌曲，并且把所有的歌曲都扔到一个池子里面，之后从池子里面等概率的选取一首歌就行了。在最坏的情况下，2000首歌曲的评分都是9.9，那么每首歌需要复制99首。

不过其实细想来，这无非就是一个简单的权重问题。权重算法有大量的解决思路，前不久在实现一个小的广告系统时，正好也有权重设置。在这里分享了下我的解决方案吧。

分为三步：

• 遍历所有项，得到所有项的总权重
• 再次遍历所有项，给每一项，加一个0到总权重之间的随机值，得到新权重。注意，每项加的都是即时生成的随机数
• 在第二步遍历的同时，取出新权重最大那一项

这一算法的思路是，各项的权重，在增加一个随机数后，被选中的概率是不变的，而增加的随机数的范围则很有讲究，如果比最小的权重值还小，那权重值大的被选中的可能性就要大大增加，而如果比最总权重之和还高，则就起不到区分作用了——所有被选中的概率就变得一样了。

这个方法不增加额外的空间，时间上只需要两次遍历，而且算法逻辑简单，权重值不管是整数还是小数，甚至负数，两项的权重值一样，都没有问题，实现也非常容易。

下面来是实现的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//待选项列表
var gnaTempAdv = [...];
//选取的结果
var gnaTarget = null;
//总权重
var totalWeight = 0;
//计算总权重
gnaTempAdv.forEach(function(gnata){
  if(gnata.weight)
    totalWeight += Number(gnata.weight);
});
gnaTempAdv.forEach(function(gnata2){
  //加随机数
  gnata2.newWeight = 0;
  gnata2.newWeight = gnata2.weight + Math.random()*totalWeight;
  
  //取新的weight最大的值
  if(!gnaTarget) {
    gnaTarget = gnata2;
  } else if(gnata2.newWeight > gnaTargetAdv.newWeight) {
    gnaTargetAdv = gnata2;
  }
});

就这么简单。