Взвешенная случайность в Java

Ответ 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];

Ответ 2

Один из элегантных способов - образец экспоненциального распределения http://en.wikipedia.org/wiki/Exponential_distribution, где весовые коэффициенты будут скоростью распространения (лямбда). Наконец, вы просто выбираете наименьшее выбранное значение.

В 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().

Ответ 3

TreeMap уже выполняет всю работу за вас.

Создайте TreeMap. Создайте весы на основе выбранного вами метода. Добавьте весовые коэффициенты, начиная с 0,0, добавляя вес последнего элемента к счетчику рабочего веса.

то есть. (Scala):

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 Int и распределите количество ковша на основе веса по всем полям. Затем вы создадите случайное целое число от 0 до 100 000-1, и вы сразу получите номер ведра.

Ответ 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();
    }
}

Ответ 5

• Дайте произвольный порядок элементам... (i1, i2,..., in)... с весами w1, w2,..., wn.
• Выберите случайное число от 0 до 1 (с достаточной детализацией, используя любую функцию рандомизации и соответствующее масштабирование). Назовите это r0.
• Пусть j = 1
• Вычитаем wj из вашего r (j-1), чтобы получить rj. Если rj <= 0, вы выбираете элемент ij. В противном случае добавьте j и повторите.

Я думаю, что я сделал это так раньше... но, вероятно, есть более эффективные способы сделать это.

Ответ 6

Ниже приведена рандомизатор, который также сохраняет точность в пропорциях:

public class WeightedRandomizer
{
    private final Random randomizer;

    public WeightedRandomizer(Random randomizer)
    {
        this.randomizer = randomizer;
    }

    public IWeighable getRandomWeighable(List<IWeighable> weighables)
    {
        double totalWeight = 0.0;
        long totalSelections = 1;
        List<IWeighable> openWeighables = new ArrayList<>();

        for (IWeighable weighable : weighables)
        {
            totalWeight += weighable.getAllocation();
            totalSelections += weighable.getNumSelections();
        }

        for(IWeighable weighable : weighables)
        {
            double allocation = weighable.getAllocation() / totalWeight;
            long numSelections = weighable.getNumSelections();
            double proportion = (double) numSelections / (double) totalSelections;

            if(proportion < allocation)
            {
                openWeighables.add(weighable);
            }
        }

        IWeighable selection = openWeighables.get(this.randomizer.nextInt(openWeighables.size()));
        selection.setNumSelections(selection.getNumSelections() + 1);
        return selection;
    }
}

Ответ 7

С классом Item, который содержит метод getWeight() (как в вашем вопросе):

/**
 * Gets a random-weighted object.
 * @param items list with weighted items
 * @return a random item from items with a chance equal to its weight.
 * @assume total weight == 1
 */
public static Item getRandomWeighted(List<Item> items) {
    double value = Math.random(), weight = 0;

    for (Item item : items) {
        weight += item.getWeight();
        if (value < weight)
            return item;
    }

    return null; // Never will reach this point if assumption is true
}

С помощью Map и более общего метода:

/**
 * Gets a random-weighted object.
 * @param balancedObjects the map with objects and their weights.
 * @return a random key-object from the map with a chance equal to its weight/totalWeight.
 * @throws IllegalArgumentException if total weight is not positive.
 */
public static <E> E getRandomWeighted(Map<E, ? extends Number> balancedObjects) throws IllegalArgumentException {
    double totalWeight = balancedObjects.values().stream().mapToInt(Number::intValue).sum(); // Java 8

    if (totalWeight <= 0)
        throw new IllegalArgumentException("Total weight must be positive.");

    double value = Math.random()*totalWeight, weight = 0;

    for (Entry<E, ? extends Number> e : balancedObjects.entrySet()) {
        weight += e.getValue().doubleValue();
        if (value < weight)
            return e.getKey();
    }

    return null; // Never will reach this point
}