今天看到一段Javascirpt 代码,其功能是按数据权重(weight)来显示广告.
基本算法描述如下:
给每个数据(节点)指定一个权重.
1.将各节点的权重求和得到总数sum.
2.采用随机函数(js中为 Math.round(Math.random() *sum) )生成一个取值范围在[1~sum]之间的值ranSum.
3.接着遍历所有数据(节点),访问顺序可以随意.将当前节点的权重值加上前面访问的各节点权重值得curSum,判断curSum >= ranSum,如果条件成立则返回当前节点,如果不是则继续累加下一节点. 直到符合上面的条件,由于ranSum<=sum 因此一定存在curSum >=ranSum.
说明:
假设有这么一组数据: A4,A5,A3,A1,A2 其对应的权重为 10,20,40,20,10 现在我们要从这5个值中按他们的权重取数据,
那么每100次取值应该有10次能取到A4,40次能取到A3等等,现在根据下面的表示,并考虑上面的算法
0--A4---A5------------A3-------A1--A2>100
每次取值时的遍历操作按A4,A5,A3,A1,A2的顺序访问,按上面的条件,ranSum的范围应该在1-100,对于A4按上面的算法在ranSum取1-10时都符合条件,因此每100次取值应该有10次被取到的机会,对于A3它的范围应该是31-70(a4+a5,a4+a5+a3),那么ranSum为31到70之间数值的可能性为每100次里有40次.由上面过程我们可以看到数据被获取的概率只跟其权重有关,跟算法中数据访问顺序无关.
代码(C#伪代码)
class Node
{
public int Weight=0;
public string Data;
}
public Node GetNode(IList<Node> nodes){
int sum=GetSum(nodes);
int ranSum=GetRandom(sum); //获取1到sum之间的随机数
int curSum=0;
foreach(Node node in Nodes){
curSum +=node.Weight;
if(curSum >= ranSum) return node;
}
return null;
}