Preface
Now apps are just springing up after a rain, and are soaring out. Experienced, inexperienced, qualified, and unqualified all want to start a business. More than 90% of entrepreneurs need to make an app, which seems to have become the standard configuration for entrepreneurship.
Once you make an app, you have to promote it. How to promote it? Sending coupons is the most indispensable thing. Now many products or operations require the amount of coupons to be randomly issued, but it cannot be too random. Are all coupons sent out? The money of investors, right?
Therefore, in the randomly generated amount, it is required that the probability of small amounts should be greater, and the probability of large amounts should be smaller. For example, 70% of 3 yuan, 25% of 5 yuan, and 5% of 10 yuan. What should I do if I generate coupons with this kind of probability?
For the above questions, it is not enough to use our Random.next(Integer range); directly. Because this pseudo-random is not weighted, the probability of 3, 5, and 10 appearing is the same.
Implementation ideas
Let’s take the example above. The probability of 3 appearing is 70%. We assign it a weight of 70. The probability of 5 appearing is 25. We assign it a weight of 25. The probability of 10 appears is 5%. We assign it a weight of 5.
We calculate the sum of weights in order, use the value before the sum of the weights that appear in the current number as the starting point value of its weight range, and use the value after the sum as the end point value of its weight range.
In this way, we can use Random.next(100) to make random numbers, then judge the range in which the random numbers fall, and then map to the corresponding coupon value.
Java implementation
package com.nggirl.test.weight.random;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Random;public class WeightRandom {public static void main(String[] args){WeightRandom wr = new WeightRandom();wr.initWeight(new String[]{"1","2","3","4"}, new Integer[]{100,100,200,600});Random r = new Random();for (int i = 0; i < 10; i++){Integer rv = r.nextint(wr.getMaxRandomValue());System.out.println(rv);System.out.println(wr.getElementByRandomValue(rv).getKey() + " " + rv);}HashMap<String, Integer> keyCount = new HashMap<String, Integer>();keyCount.put("1", 0);keyCount.put("2", 0);keyCount.put("3", 0);keyCount.put("4", 0);for (int i = 0; i < 10000; i++){Integer rv = r.nextint(wr.getMaxRandomValue());String key = wr.getElementByRandomValue(rv).getKey();keyCount.put(key, keyCount.get(key).intValue()+1);}System.out.println("");}private List<WeightElement> weightElements;public void initWeight(String[] keys, Integer[] weights){if(keys == null || weights == null || keys.length != weights.length){return;}weightElements = new ArrayList<WeightElement>();for (int i=0; i< keys.length; i++){weightElements.add(new WeightElement(keys[i], weights[i]));}rangeWeightElemnts();printRvs();}private void rangeWeightElemnts(){if(weightElements.size() == 0){return;}WeightElement ele0 = weightElements.get(0);ele0.setThresholdLow(0);ele0.setThresholdHigh(ele0.getWeight());for (int i = 1; i < weightElements.size(); i++){WeightElement curElement = weightElements.get(i);WeightElement preElement = weightElements.get(i - 1);curElement.setThresholdLow(preElement.getThresholdHigh());curElement.setThresholdHigh(curElement.getThresholdLow() + curElement.getWeight());}}public WeightElement getElementByRandomValue(Integer rv){//Because the element weight range is incremented in an orderly manner, it can be changed to a binary search for (WeightElement e:weightElements){if(rv >= e.getThresholdLow() && rv < e.getThresholdHigh()){return e;}}return null;}public Integer getMaxRandomValue(){if(weightElements == null || weightElements.size() == 0){return null;}return weightElements.get(weightElements.size() - 1).getThresholdHigh();}public void printRvs(){for (WeightElement e:weightElements){System.out.println(e.toString());}}static class WeightElement{/** * Element tag */private String key;/** * Element weight*/private Integer weight;/** * Weight corresponds to the range of random numbers low lines*/private Integer thresholdLow;/** * Weight corresponds to the range of random numbers high lines*/private Integer thresholdHigh;public WeightElement(){}public WeightElement(Integer weight){this.key = weight.toString();this.weight = weight;}public WeightElement(String key, Integer weight){this.key = key;this.weight = weight;}public String getKey() {return key;}public void setKey(String key) {this.key = key;}public Integer getWeight() {return weight;}public void setWeight(Integer weight) {this.weight = weight;}public Integer getThresholdLow() {return thresholdLow;}public void setThresholdLow(Integer thresholdLow) {this.thresholdLow = thresholdLow;}public Integer getThresholdHigh() {return thresholdHigh;}public void setThresholdHigh(Integer thresholdHigh) {this.thresholdHigh = thresholdHigh;}public String toString(){return "key:"+this.key + " weight:" + this.weight + " low:"+this.thresholdLow+" height:"+this.thresholdHigh;}}}result:
2 1028764 876
Implementation of dichotomy
public WeightElement getElementByRandomValue(Integer rv){if(rv < 0 || rv > getMaxRandomValue()-1){return null;}//At this time, rv must be in the range of 0 - getMaxRandomValue()-1, // That is, it must be able to hit a certain value int start = 0, end = weightElements.size() - 1;int index = weightElements.size()/2;while(true){if(rv < weightElements.get(index).getThresholdLow()){end = index - 1;} else if(rv >= weightElements.get(index).getThresholdHigh()){start = index + 1;} else{return weightElements.get(index);}index = (start + end)/2;}}Let’s share another example below to strengthen the understanding of weight random algorithms, and be in place at once!
The weight random algorithm is widely used in systems such as lottery, resource scheduling, etc. It is a simple random implementation according to the weight. The weight is the ratio of hits of several random objects (categorized). The higher the weight setting, the easier the hits, and the sum of the hits can not be equal to 100;
The simple implementation code is as follows:
import java.util.ArrayList;import java.util.List;import java.util.Random;public class WeightRandom {static List<WeightCategory> categories = new ArrayList<WeightCategory>();private static Random random = new Random();public static void initData() {WeightCategory wc1 = new WeightCategory("A",60);WeightCategory wc2 = new WeightCategory("B",20);WeightCategory wc3 = new WeightCategory("C",20);categorys.add(wc1);categorys.add(wc2);categorys.add(wc3);}public static void main(String[] args) {initData();Integer weightSum = 0;for (WeightCategory wc : categories) {weightSum += wc.getWeight();}if (weightSum <= 0) {System.err.println("Error: weightSum=" + weightSum.toString());return;}Integer n = random.nextint(weightSum);// n in [0, weightSum) Integer m = 0;for (WeightCategory wc : categories) {if (m <= n && n < m + wc.getWeight()) {System.out.println("This Random Category is "+wc.getCategory());break;}m += wc.getWeight();}}}class WeightCategory {private String category;private Integer weight;public WeightCategory() {super();}public WeightCategory(String category, Integer weight) {super();this.setCategory(category);this.setWeight(weight);}public Integer getWeight() {return weight;}public void setWeight(Integer weight) {this.weight = weight;}public String getCategory() {return category;}public void setCategory(String category) {this.category = category;}}result:
Summarize
The above is the complete content of this article on the implementation of the Java language weight random algorithm. I hope it will be helpful to everyone. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!