一种权重算法及其实现

撰写于 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;
}
});

就这么简单。

目录

Site by Yifei Zhang using Hexo & Random

Yifei Zhang的博主是一名Node.js程序员,博客的内容会涉及电影 / 生活 / 吐槽 / JavaScript / PHP / Node.js / Express / MongoDB / MySQL / Redis / AngularJS / jQuery / HTML。

Hide