首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >权重随机算法的java实现

权重随机算法的java实现

作者头像
张哥编程
发布于 2024-12-17 10:52:30
发布于 2024-12-17 10:52:30
6130
举报
文章被收录于专栏:云计算linux云计算linux

一、概述

  平时,经常会遇到权重随机算法,从不同权重的N个元素中随机选择一个,并使得总体选择结果是按照权重分布的。如广告投放、负载均衡等。

  如有4个元素A、B、C、D,权重分别为1、2、3、4,随机结果中A:B:C:D的比例要为1:2:3:4。

  ​总体思路​:累加每个元素的权重A(1)-B(3)-C(6)-D(10),则4个元素的的权重管辖区间分别为[0,1)、[1,3)、[3,6)、[6,10)。然后随机出一个[0,10)之间的随机数。落在哪个区间,则该区间之后的元素即为按权重命中的元素。

  ​实现方法​:

利用TreeMap,则构造出的一个树为:

    B(3)

    / \

/ \

A(1) D(10)

/

/

C(6)

然后,利用treemap.tailMap().firstKey()即可找到目标元素。

当然,也可以利用​数组+二分查找​来实现。

二、源码

代码语言:javascript
复制
packagecom.xxx.utils;
                                                   importcom.google.common.base.Preconditions;
importorg.apache.commons.math3.util.Pair;
importorg.slf4j.Logger;
importorg.slf4j.LoggerFactory;
                                                   importjava.util.List;
importjava.util.SortedMap;
importjava.util.TreeMap;
                                                                             publicclassWeightRandom<K,V extendsNumber> {
    privateTreeMap<Double, K> weightMap = newTreeMap<Double, K>();
    privatestaticfinalLogger logger = LoggerFactory.getLogger(WeightRandom.class);
                                                       publicWeightRandom(List<Pair<K, V>> list) {
        Preconditions.checkNotNull(list, "list can NOT be null!");
        for(Pair<K, V> pair : list) {
            doublelastWeight = this.weightMap.size() == 0? 0: this.weightMap.lastKey().doubleValue();//统一转为double
            this.weightMap.put(pair.getValue().doubleValue() + lastWeight, pair.getKey());//权重累加
        }
    }
                                                       publicK random() {
        doublerandomWeight = this.weightMap.lastKey() * Math.random();
        SortedMap<Double, K> tailMap = this.weightMap.tailMap(randomWeight, false);
        returnthis.weightMap.get(tailMap.firstKey());
    }
                                                   }

三、性能

4个元素A、B、C、D,其权重分别为1、2、3、4,运行1亿次,结果如下:

元素

命中次数

误差率

A

10004296

0.0430%

B

19991132

0.0443%

C

30000882

0.0029%

D

40003690

0.0092%

从结果,可以看出,准确率在​99.95%​以上。

四、另一种实现

利用B+树的原理。叶子结点存放元素,非叶子结点用于索引。非叶子结点有两个属性,分别保存左右子树的累加权重。如下图:

权重随机算法的java实现_广告
权重随机算法的java实现_广告

看到这个图,聪明的你应该知道怎么随机了吧。

此方法的优点是:更改一个元素,只须修改该元素到根结点那半部分的权值即可。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-03-09,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 一、概述
  • 二、源码
  • 三、性能
  • 四、另一种实现
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档