java加权随机排序

Question

问题：

我有一些有重量的东西。重量越高，他们拥有该物品的几率就越大。我需要一种基于核心Java（没有第三方库、JAR等）的干净、简单的方法来实现这一点

我对两个项目做了这项工作，将权重相加，然后在该范围内使用Math.random()随机选取一个数字。非常简单。但是对于大于2的项目，我可以在相同的范围内进行更多的样本更改未命中，或者我可以重新计算剩余项目的权重之和，然后再次选择（递归方法）。我认为可能有什么东西可以更快/更干净地做到这一点。这段代码会被反复使用，所以我正在寻找一个有效的解决方案

本质上，它类似于随机权重排列

一些例子：

1. A的重量为1，B的重量为99。如果我用这个运行模拟，我希望得到99%的时间和1%的时间

2. A的重量为10，B的重量为10，C的重量为80。如果我用这个进行模拟，我会期望C在80%的时间里是排序中的第一项，在这种情况下，A和B成为下一个角色的几率相等

额外细节：

对于我的特殊问题，有一小部分物品的重量可能很大。比如说，20到50件物品的重量以长条的形式存储，其中最小重量至少为1000。项目的数量可能也会增加很多，所以如果我们能找到一个不需要项目太小的解决方案，那将是首选

Answer 1

你有重量的物品：

• A项，重量42
• B项，重量5
• C项，重量96
• D项，重量33

首先把所有的重量加起来：42+5+96+33=176

现在选择一个随机数r，从0到权重之和：0<；=r<；我用过整数，但如果需要你可以用实数

将r与权重定义的范围进行比较：

• 0<；=r<；42：选择项目A
• 42<；=r<；47（=42+5）：选择项目B
• 47<；=r<；143（=47+96）：选择项目C
• 143<；=r<；176（=143+33）：选择项目D

当你选择了第一个项目，然后对剩下的三个项目和所有权重的减少总和重复这个过程。不断重复，直到没有更多的物品可供挑选

Answer 2

public class RandomPriorityQueue {

    private TreeMap<Integer, List<WeightedElement>> tree = new TreeMap();
    private Random random = new Random();

    public void add(WeightedElement e) {
        int priority = random.nextInt(e.getWeight());
        if (tree.containsKey(priority)) {
            List<WeightedElement> list = new LinkedList();
            list.add(e);
            tree.put(priority, list);
        } else {
            List<WeightedElement> list = tree.get(priority);
            list.add(random.nextInt(list.size()), e);
        }
    }

    public WeightedElement poll() {
        Map.Entry<Integer, List<WeightedElement>> entry = tree.lastEntry();
        if (entry == null){
            return null;
        }
        List<WeightedElement> list = entry.getValue();
        if (list.size() == 1){
            tree.remove(entry.getKey());
        }
        return list.remove(0);
    }
}

当然，如果我们重写TreeMap，这样就可以添加复制键，我们的性能会更好