nextint - Aleatoriedad ponderada en Java

random java 8

Question

Esta pregunta ya tiene una respuesta aquí:

• Selección ponderada aleatoria en Java 7 respuestas

En Java, dados n Items, cada uno con un peso w , ¿cómo se elige un Item aleatorio de la colección con una probabilidad igual a w ?

Suponga que cada peso es un doble de 0.0 a 1.0 y que los pesos en la colección suman 1. Item.getWeight () devuelve el peso del artículo.

Answer 1

1. Dar un orden arbitrario a los artículos ... (i1, i2, ..., in) ... con los pesos w1, w2, ..., wn.
2. Elija un número aleatorio entre 0 y 1 (con granularidad suficiente, utilizando cualquier función de aleatorización y escalado apropiado). Llamar a esto r0.
3. Deje que j = 1
4. Reste wj de su r (j-1) para obtener rj. Si rj <= 0, entonces selecciona el ítem ij. De lo contrario, incremente jy repita.

Creo que lo he hecho así antes ... pero probablemente haya formas más eficientes de hacerlo.

Answer 2

A continuación se muestra un aleatorizador que también mantiene la precisión en las proporciones:

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;
    }
}

Answer 3

Con una clase de Item que contiene un método getWeight() (como en su pregunta):

/**
 * 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
}

Con un Map y método más genérico:

/**
 * 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
}

Answer 4

Si desea eficiencia en la selección del tiempo de ejecución, tomarse un poco más de tiempo en la instalación probablemente sea lo mejor. Aquí hay una posible solución. Tiene más código pero garantiza la selección de log (n).

WeightedItemSelector Implementa la selección de un objeto aleatorio de una colección de objetos ponderados. La selección está garantizada para ejecutarse en tiempo de registro (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;
    }
}

Rango Implementa la selección de rango para aprovechar la selección 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 simplemente encapsula un elemento para ser seleccionado.

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

TreeMap ya hace todo el trabajo por ti.

Crea un TreeMap. Cree pesas según su método de elección. Agregue los pesos comenzando con 0.0 mientras agrega el peso del último elemento a su contador de peso en ejecución.

es decir, (Scala):

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

Entonces solo tienes que generar rand = new Random(); num = rand.nextDouble() * count rand = new Random(); num = rand.nextDouble() * count para obtener un número válido.

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

le dará el artículo ponderado al azar.

Para cantidades más pequeñas de cubetas también es posible: cree una matriz de, por ejemplo, 100.000 Int. Y distribuya el número del cucharón según el peso en los campos. Luego, crea un Entero aleatorio entre 0 y 100,000-1 e inmediatamente recupera el número de cangilón.

Answer 6

Una manera elegante sería muestrear una distribución exponencial http://en.wikipedia.org/wiki/Exponential_distribution donde los pesos serán la tasa de la distribución (lambda). Finalmente, simplemente selecciona el valor más pequeño de la muestra.

En Java esto se ve así:

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;
}

No estoy seguro de si esto es más eficiente que los otros enfoques, pero si el tiempo de ejecución no es el problema, es una solución muy bien vista.

Y esta es la misma idea usando Java 8 y 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();
}

Puede obtener la secuencia de ponderaciones de entrada, por ejemplo, desde un mapa convirtiéndola con .entrySet().stream() .

Answer 7

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];