應(yīng)用場景：最近做一個推廣活動的小程序悄谐，用戶通過鏈接分享點(diǎn)擊數(shù)可以抽取獎勵介评，點(diǎn)擊數(shù)越高，抽取到大獎的概率越高爬舰，所以這里獎品的隨機(jī)概率是確定并且動態(tài)變化的们陆。
參考了HashMap的些許設(shè)計(jì)思路，代碼如下：
package com.rc.components.common.utils;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Set;
import lombok.Data;
/**
* 概率隨機(jī)工具
* @author: rc
* @date: 2018年2月5日 下午4:55:48
* @version: V1.0
* @review: rc/2018年2月5日 下午4:55:48
*/
public class ProbRandom {
private final Integer randomBound; //隨機(jī)邊界范圍
private final Random random; //隨機(jī)生成器
private final HashMap<Object, Integer> originalMap; //隨機(jī)元素的原始數(shù)據(jù)容器
private ArrayList<ProbDistribution> probDistributions; //元素分布概率的數(shù)組
private boolean updateFlag; //原始數(shù)據(jù)容器是否有更新
private Integer originalSum; //原始數(shù)據(jù)隨機(jī)值求和
private Integer zeroOriginalCount; //原始數(shù)據(jù)隨機(jī)值為0(未設(shè)置隨機(jī)值)的元素個數(shù)
public ProbRandom(Integer randomBound) {
this.originalMap = new HashMap<>();
this.updateFlag = true;
this.randomBound = randomBound;
this.originalSum = 0;
this.zeroOriginalCount = 0;
this.random = new Random();
}
/**
* 生成隨機(jī)數(shù)
* @return
*/
public Object next(){
distribute(); //計(jì)算元素分布的概率值
if (null == probDistributions) {
return null;
}
int nextInt = random.nextInt(randomBound);
ProbDistribution prob = probDistributions.stream().filter(c->(c.floor<=nextInt&&c.ceil>nextInt)).findFirst().get();
return prob.getKey();
}
/**
* 添加隨機(jī)元素和概率值情屹，返回添加后的概率值
* 如果prob=0 坪仇，概率值計(jì)算為總體概率值確定的默認(rèn)值
* @param key
* @param prob
* @return
*/
public void put(Object key, Integer prob){
//校驗(yàn)
if (null == key || prob == null ) {
throw new NullPointerException("key或者prob不能為空");
}
if (prob < 0) {
throw new RuntimeException("prob不能小于0");
}
//添加
Integer previousProb = originalMap.put(key, prob);
//更新
if (prob == 0) {
zeroOriginalCount ++ ;
} else {
originalSum += prob;
}
if (previousProb == null) {
updateFlag = true;
} else {
if (previousProb == 0) {
zeroOriginalCount -- ;
} else {
originalSum -= previousProb;
}
if (prob != previousProb) {
updateFlag = true;
}
}
}
/**
* 刪除已經(jīng)添加的元素，返回元素設(shè)置的隨機(jī)值
* 如果元素不存在屁商，返回null
* @param key
* @return
*/
public Integer remove(Object key){
//校驗(yàn)
if (null == key) {
throw new NullPointerException("key或者prob不能為空");
}
//刪除
Integer remove = originalMap.remove(key);
if (null != remove) {
updateFlag = true;
}
return remove;
}
/**
* 等同于put(key,0)
* @param key
*/
public void put(Object key){
put(key,0);
}
/**
* 返回隨機(jī)值邊界randomBound
* @return
*/
public Integer getRandomBound(){
return randomBound;
}
/**
* 返回元素的隨機(jī)值prob
* @param key
* @return
*/
public Integer getProb(Object key){
return originalMap.get(key);
}
/**
* 返回元素的集合
* @return
*/
public Set<Object> getKeySet(){
return originalMap.keySet();
}
//計(jì)算概率元素的概率分布
private void distribute() {
if (randomBound < originalSum) {
throw new RuntimeException("總隨機(jī)值不能大于隨機(jī)值邊界");
}
//如果原始數(shù)據(jù)容器有更新烟很，就從新計(jì)算分布概率數(shù)組
if (updateFlag) {
//創(chuàng)建分布概率數(shù)組
probDistributions = new ArrayList<ProbRandom.ProbDistribution>();
//重組分布概率數(shù)組
Integer tempFloor = 0;
if (zeroOriginalCount == 0) {
for (Entry<Object, Integer> e : originalMap.entrySet()) {
Integer ceil = (int) (tempFloor + e.getValue()*1.00*randomBound/originalSum);
probDistributions.add(new ProbDistribution(e.getKey(), tempFloor, ceil)) ;
tempFloor = ceil;
}
} else {
Integer defProbSize = (int) ((randomBound - originalSum)*1.00/zeroOriginalCount);
for (Entry<Object, Integer> e : originalMap.entrySet()) {
Integer ceil;
if (e.getValue() == 0) {
ceil = tempFloor + defProbSize;
} else {
ceil = (int) (tempFloor + e.getValue());
}
probDistributions.add(new ProbDistribution(e.getKey(), tempFloor, ceil)) ;
tempFloor = ceil;
}
}
updateFlag = false;
}
}
//描述單個元素分布概率情況
@Data
private class ProbDistribution{
private Object key;
private Integer floor;
private Integer ceil;
ProbDistribution(Object key, Integer floor, Integer ceil){
this.key = key;
this.floor = floor;
this.ceil = ceil;
}
}
}
以上代碼大致思路：
1.使用一個集合originalMap作為隨機(jī)元素的容器，key是對應(yīng)隨機(jī)對象蜡镶，value是設(shè)定的隨機(jī)概率雾袱，這里的概率并不是百分?jǐn)?shù)，而是以一個概率基數(shù)randomBound作為比較的官还。
2.在進(jìn)行隨機(jī)取樣時芹橡，是將originalMap中的所有概率值轉(zhuǎn)換計(jì)算distribute()成randomBound內(nèi)的數(shù)值范圍分布probDistributions，通過random生成的隨機(jī)數(shù)對應(yīng)的數(shù)值范圍分布next()來產(chǎn)生一定概率的隨機(jī)對象望伦。
3.其中distribute()是一個比較關(guān)鍵并且損耗性能的方法林说，所以在這里使用一個標(biāo)記updateFlag來標(biāo)識originalMap中概率值是否發(fā)生過變化，只有發(fā)生過變化的時候才需要重新distribute()進(jìn)行probDistributions的計(jì)算，否則使用原有的probDistributions來產(chǎn)生隨機(jī)對象即可菠红。
4.另外對外暴露了put,remove,get的方法來操作originalMap莽鸭，但是沒有直接獲取originalMap的方法，因?yàn)槿绻梢灾苯荧@取originalMap珠移，updateFlag就無法準(zhǔn)確的描述概率值是否發(fā)生了變化。
簡單的測試：
package com.rc.components.common.utils;
public class ProbRandoTest {
public static void main(String[] args) {
ProbRandom pr = new ProbRandom(1000);
pr.put("A", 300);
pr.put("B", 200);
pr.put("C", 300);
int countA = 0;
int countB = 0;
int countC = 0;
long start = System.currentTimeMillis();
System.out.println(start);
for (int i = 0; i < 10000; i++) {
Object next = pr.next();
if ("A".equals(next)) {
countA++;
}else if ("B".equals(next)) {
countB++;
}else if ("C".equals(next)) {
countC++;
}
}
long end = System.currentTimeMillis();
System.out.println(end-start);
System.out.println("countA" + countA);
System.out.println("countB" + countB);
System.out.println("countC" + countC);
}
}
測試結(jié)果
循環(huán)隨機(jī)1000000次耗時223毫秒
countA末融。钧惧。。375239
countB勾习。浓瞪。。250509
countC巧婶。乾颁。涂乌。374252
結(jié)果顯示概率準(zhǔn)確性和運(yùn)行速度都沒有太大問題。
當(dāng)然這只是一個初級的版本钮孵，沒有考慮多線程情況下的數(shù)據(jù)可靠性問題骂倘，如果需要考慮到線程安全，可以模擬ConcurrentHashMap的分段鎖機(jī)制巴席，實(shí)現(xiàn)性能和安全性調(diào)和历涝。
