Java中灵活实现加权随机选择的策略与实践

Random random = new Random();
int randomInt = random.nextInt(10)+1; // 生成1到10的随机数

if(randomInt <= 3){
    System.out.println("Magnificent!"); // 30%概率
} else if (randomInt >= 7){
    System.out.println("Marvelous!"); // 40%概率 (7, 8, 9, 10)
} else {
    System.out.println("Delectable!"); // 30%概率 (4, 5, 6)
}

private static class WeightedValue<T> {
    final double weight;
    final T value;

    public WeightedValue(double weight, T value) {
        this.weight = weight;
        this.value = value;
    }
}

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.ThreadLocalRandom; // 推荐用于多线程环境的随机数生成

public class WeightedRandom<T> {    
    // 比较器：按权重降序排列
    private final Comparator<WeightedValue<T>> byWeight = 
        Comparator.comparing((WeightedValue<T> wv) -> wv.weight).reversed(); // 使用reversed()实现降序

    // 存储加权值的TreeSet，自动按权重降序排序
    private final Set<WeightedValue<T>> weightedValues = 
        new TreeSet<>(byWeight);

    private double totalWeight; // 所有权重的总和

    // ... (put和next方法)
}

    /**
     * 添加一个加权值。
     * @param weight 权重，必须大于0。
     * @param value 关联的值。
     */
    public void put(double weight, T value) {
        if (weight <= 0) {
            // 负数或零权重通常没有意义，可以选择抛出异常或忽略
            System.err.println("Warning: Weight must be positive. Ignoring value: " + value + " with weight: " + weight);
            return;
        }
        totalWeight += weight;
        weightedValues.add(new WeightedValue<>(weight, value));
    }

    /**
     * 从加权值集合中随机选择一个值。
     * @return 随机选择的值。
     * @throws NoSuchElementException 如果加权值集合为空。
     */
    public T next() {
        if (weightedValues.isEmpty()) {
            throw new NoSuchElementException("WeightedRandom set is empty.");
        }

        // 生成一个介于0（包含）和totalWeight（不包含）之间的随机数
        double rnd = ThreadLocalRandom.current().nextDouble(totalWeight);

        double sum = 0; // 累积权重
        Iterator<WeightedValue<T>> iterator = weightedValues.iterator();
        WeightedValue<T> result = null;

        // 遍历加权值，直到随机数落在某个值的累积权重区间内
        while (iterator.hasNext()) {
            result = iterator.next();
            sum += result.weight;
            if (rnd < sum) { // 注意：这里是小于，因为nextDouble(totalWeight)不包含totalWeight
                return result.value;
            }
        }
        // 理论上，如果totalWeight计算正确且rnd在[0, totalWeight)范围内，
        // 循环总会找到一个结果。为防止浮点数精度问题，可以添加一个回退机制，
        // 例如返回最后一个元素，但这通常不是必需的。
        // 对于本实现，最后一个元素必然会满足rnd < sum的条件（因为sum最终会等于totalWeight）。
        return result.value; // 如果循环结束，返回最后一个元素（确保覆盖所有情况）
    }

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.ThreadLocalRandom;

public class WeightedRandom<T> {    
    private final Comparator<WeightedValue<T>> byWeight = 
        Comparator.comparing((WeightedValue<T> wv) -> wv.weight).reversed();
    private final Set<WeightedValue<T>> weightedValues = 
        new TreeSet<>(byWeight);

    private double totalWeight;

    /**
     * 添加一个加权值。
     * @param weight 权重，必须大于0。
     * @param value 关联的值。
     */
    public void put(double weight, T value) {
        if (weight <= 0) {
            System.err.println("Warning: Weight must be positive. Ignoring value: " + value + " with weight: " + weight);
            return;
        }
        totalWeight += weight;
        weightedValues.add(new WeightedValue<>(weight, value));
    }

    /**
     * 从加权值集合中随机选择一个值。
     * @return 随机选择的值。
     * @throws NoSuchElementException 如果加权值集合为空。
     */
    public T next() {
        if (weightedValues.isEmpty()) {
            throw new NoSuchElementException("WeightedRandom set is empty.");
        }

        double rnd = ThreadLocalRandom.current().nextDouble(totalWeight);

        double sum = 0;
        Iterator<WeightedValue<T>> iterator = weightedValues.iterator();
        WeightedValue<T> result = null; // 确保result在循环外有定义，以防万一

        while (iterator.hasNext()) {
            result = iterator.next();
            sum += result.weight;
            if (rnd < sum) {
                return result.value;
            }
        }
        // 理论上，如果totalWeight计算正确且rnd在[0, totalWeight)范围内，
        // 循环总会找到一个结果。为防止浮点数精度问题，返回最后一个元素作为安全网。
        return result.value; 
    }

    private static class WeightedValue<T> {
        final double weight;
        final T value;

        public WeightedValue(double weight, T value) {
            this.weight = weight;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        WeightedRandom<String> randomSelector = new WeightedRandom<>();
        randomSelector.put(3, "AAA"); // 权重3
        randomSelector.put(2, "BBB"); // 权重2
        randomSelector.put(5, "CCC"); // 权重5
        // 总权重 = 3 + 2 + 5 = 10
        // 预期概率：AAA (3/10=0.3), BBB (2/10=0.2), CCC (5/10=0.5)

        System.out.println("进行1000次加权随机选择：");
        int countA = 0, countB = 0, countC = 0;
        for (int i = 0; i < 1000; i++) {
            String value = randomSelector.next();
            // System.out.println(value); // 可以打印每次结果
            switch (value) {
                case "AAA": countA++; break;
                case "BBB": countB++; break;
                case "CCC": countC++; break;
            }
        }
        System.out.println("AAA 出现次数: " + countA + " (预期: 300)");
        System.out.println("BBB 出现次数: " + countB + " (预期: 200)");
        System.out.println("CCC 出现次数: " + countC + " (预期: 500)");
    }
}