Java中的加权随机性

Question

在Java中,给定n个项目,每个项目都有权重w,如何从集合中选择一个等于w的随机项目？

假设每个权重是从0.0到1.0的双精度,并且集合中的权重总和为1. Item.getWeight()返回Item的权重.

Answer 1

Item[] items = ...;

// Compute the total weight of all items together
double totalWeight = 0.0d;
for (Item i : items)
{
    totalWeight += i.getWeight();
}
// Now choose a random item
int randomIndex = -1;
double random = Math.random() * totalWeight;
for (int i = 0; i < items.length; ++i)
{
    random -= items[i].getWeight();
    if (random <= 0.0d)
    {
        randomIndex = i;
        break;
    }
}
Item myRandomItem = items[randomIndex];

Answer 2

一种优雅的方法是对指数分布进行抽样http://en.wikipedia.org/wiki/Exponential_distribution,其中权重将是分布的比率(lambda).最后,您只需选择最小的采样值.

在Java中,这看起来像这样:

public static <E> E getWeightedRandom(Map<E, Double> weights, Random random) {
    E result = null;
    double bestValue = Double.MAX_VALUE;

    for (E element : weights.keySet()) {
        double value = -Math.log(random.nextDouble()) / weights.get(element);

        if (value < bestValue) {
            bestValue = value;
            result = element;
        }
    }

    return result;
}

我不确定这是否比其他方法更有效,但如果执行时间不是问题,那么它是一个很好看的解决方案.

这与使用Java 8和Streams的想法相同:

public static <E> E getWeightedRandomJava8(Stream<Entry<E, Double>> weights, Random random) {
    return weights
        .map(e -> new SimpleEntry<E,Double>(e.getKey(),-Math.log(random.nextDouble()) / e.getValue()))
        .min((e0,e1)-> e0.getValue().compareTo(e1.getValue()))
        .orElseThrow(IllegalArgumentException::new).getKey();
}

您可以通过转换来获取输入权重流,例如从地图中获取.entrySet().stream().

Answer 3

TreeMap已经为您完成了所有工作.

创建一个TreeMap.根据您选择的方法创建权重.添加以0.0开头的权重,同时将最后一个元素的权重添加到正在运行的权重计数器中.

即(斯卡拉):

var count = 0.0  
for { object <- MyObjectList } { //Just any iterator over all objects 
  map.insert(count, object) 
  count += object.weight
}

然后你只需生成rand = new Random(); num = rand.nextDouble() * count一个有效的数字.

map.to(num).last  // Scala
map.floorKey(num) // Java

会给你随机加权项目.

对于少量的桶也是可能的:创建一个100,000 100,000的数组,并根据字段的权重分配桶的数量.然后创建一个0到100,000-1之间的随机整数,然后立即返回桶号.

Answer 4

如果您想要运行时选择效率,那么在设置上花费更多时间可能是最好的.这是一种可能的解决方案.它有更多的代码,但保证log(n)选择.

WeightedItemSelector实现从加权对象集合中选择随机对象.选择保证在log(n)时间内运行.

public class WeightedItemSelector<T> {
    private final Random rnd = new Random();
    private final TreeMap<Object, Range<T>> ranges = new TreeMap<Object, Range<T>>();
    private int rangeSize; // Lowest integer higher than the top of the highest range.

    public WeightedItemSelector(List<WeightedItem<T>> weightedItems) {
        int bottom = 0; // Increments by size of non zero range added as ranges grows.

        for(WeightedItem<T> wi : weightedItems) {
            int weight = wi.getWeight();
            if(weight > 0) {
                int top = bottom + weight - 1;
                Range<T> r = new Range<T>(bottom, top, wi);
                if(ranges.containsKey(r)) {
                    Range<T> other = ranges.get(r);
                    throw new IllegalArgumentException(String.format("Range %s conflicts with range %s", r, other));
                }
                ranges.put(r, r);
                bottom = top + 1;
            }
        }
        rangeSize = bottom; 
    }

    public WeightedItem<T> select() {
        Integer key = rnd.nextInt(rangeSize);
        Range<T> r = ranges.get(key);
        if(r == null)
            return null;
        return r.weightedItem;
    }
}

范围实现范围选择以利用TreeMap选择.

class  Range<T> implements Comparable<Object>{
    final int bottom;
    final int top;
    final WeightedItem<T> weightedItem;
    public Range(int bottom, int top, WeightedItem<T> wi) {
        this.bottom = bottom;
        this.top = top;
        this.weightedItem = wi;
    }

    public WeightedItem<T> getWeightedItem() {
        return weightedItem;
    }

    @Override
    public int compareTo(Object arg0) {
        if(arg0 instanceof Range<?>) {
            Range<?> other = (Range<?>) arg0;
            if(this.bottom > other.top)
                return 1;
            if(this.top < other.bottom)
                return -1;
            return 0; // overlapping ranges are considered equal.
        } else if (arg0 instanceof Integer) {
            Integer other = (Integer) arg0;
            if(this.bottom > other.intValue())
                return 1;
            if(this.top < other.intValue())
                return -1;
            return 0;
        }
        throw new IllegalArgumentException(String.format("Cannot compare Range objects to %s objects.", arg0.getClass().getName()));
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("{\"_class\": Range {\"bottom\":\"").append(bottom).append("\", \"top\":\"").append(top)
                .append("\", \"weightedItem\":\"").append(weightedItem).append("}");
        return builder.toString();
    }
}

WeightedItem简单地封装了要选择的项目.

public class WeightedItem<T>{
    private final int weight;
    private final T item;
    public WeightedItem(int weight, T item) {
        this.item = item;
        this.weight = weight;
    }

    public T getItem() {
        return item;
    }

    public int getWeight() {
        return weight;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("{\"_class\": WeightedItem {\"weight\":\"").append(weight).append("\", \"item\":\"")
                .append(item).append("}");
        return builder.toString();
    }
}

Answer 5

1. 给项目赋予一些任意的排序......(i1,i2,...,in)......权重为w1,w2,...,wn.
2. 选择0到1之间的随机数(具有足够的粒度,使用任何随机化函数和适当的缩放).叫这个r0.
3. 设j = 1
4. 从你的r(j-1)中减去wj得到rj.如果rj <= 0,则选择项目ij.否则,增加j并重复.

我想我之前已经这样做了......但是可能有更有效的方法来做到这一点.