Casualità ponderata in Java

In Java, dati n elementi, ciascuno con peso w , come si sceglie un object casuale dalla collezione con una probabilità uguale a w ?

Assumi che ogni peso sia un doppio da 0,0 a 1,0 e che i pesi nella sum della raccolta a 1. Item.getWeight () restituisca il peso dell’articolo.

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

Un modo elegante sarebbe quello di campionare una distribuzione esponenziale http://en.wikipedia.org/wiki/Exponential_distribution dove i pesi saranno il tasso della distribuzione (lambda). Infine, è sufficiente selezionare il più piccolo valore campionato.

In Java questo assomiglia a questo:

 public static  E getWeightedRandom(Map 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; } 

Non sono sicuro che sia più efficiente degli altri approcci, ma se il tempo di esecuzione non è il problema, si tratta di una soluzione dall'aspetto gradevole.

E questa è la stessa idea usando Java 8 e Streams:

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

È ansible ottenere il stream di pesi di input ad esempio da una mappa convertendolo con .entrySet().stream() .

TreeMap fa già tutto il lavoro per te.

Crea una TreeMap. Crea pesi in base al tuo metodo di scelta. Aggiungi i pesi a partire da 0.0 mentre aggiungi il peso dell’ultimo elemento al tuo contrappeso.

cioè (Scala):

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

Quindi devi solo generare rand = new Random(); num = rand.nextDouble() * count rand = new Random(); num = rand.nextDouble() * count per ottenere un numero valido.

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

ti darà l'object pesato a caso.

È anche ansible avere una quantità minore di benne: creare un array di 100.000 Int e distribuire il numero del bucket in base al peso tra i campi. Quindi crei un intero casuale compreso tra 0 e 100.000-1 e ottieni immediatamente il numero del bucket.

Se si desidera l’efficienza di selezione del runtime, richiedere un po ‘più di tempo per l’installazione sarebbe probabilmente la scelta migliore. Ecco una ansible soluzione. Ha più codice ma garantisce la selezione di log (n).

WeightedItemSelector Implementa la selezione di un object casuale da una raccolta di oggetti ponderati. La selezione è garantita per essere eseguita nel log (n).

 public class WeightedItemSelector { private final Random rnd = new Random(); private final TreeMap> ranges = new TreeMap>(); private int rangeSize; // Lowest integer higher than the top of the highest range. public WeightedItemSelector(List> weightedItems) { int bottom = 0; // Increments by size of non zero range added as ranges grows. for(WeightedItem wi : weightedItems) { int weight = wi.getWeight(); if(weight > 0) { int top = bottom + weight - 1; Range r = new Range(bottom, top, wi); if(ranges.containsKey(r)) { Range 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 select() { Integer key = rnd.nextInt(rangeSize); Range r = ranges.get(key); if(r == null) return null; return r.weightedItem; } } 

Intervallo Mostra la selezione dell’intervallo per sfruttare la selezione TreeMap.

 class Range implements Comparable{ final int bottom; final int top; final WeightedItem weightedItem; public Range(int bottom, int top, WeightedItem wi) { this.bottom = bottom; this.top = top; this.weightedItem = wi; } public WeightedItem 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 semplicemente incapsula un object da selezionare.

 public class WeightedItem{ 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(); } } 
  1. Dare un ordinamento arbitrario agli elementi … (i1, i2, …, in) … con i pesi w1, w2, …, wn.
  2. Scegliere un numero casuale compreso tra 0 e 1 (con granularità sufficiente, utilizzando qualsiasi funzione di randomizzazione e ridimensionamento appropriato). Chiama questo r0.
  3. Sia j = 1
  4. Sottrai wj dalla tua r (j-1) per ottenere rj. Se rj <= 0, allora si seleziona l'elemento ij. Altrimenti, incrementa j e ripeti.

Penso di averlo fatto prima … ma probabilmente ci sono modi più efficienti per farlo.

Di seguito è riportato un randomizzatore che mantiene la precisione anche nelle proporzioni:

 public class WeightedRandomizer { private final Random randomizer; public WeightedRandomizer(Random randomizer) { this.randomizer = randomizer; } public IWeighable getRandomWeighable(List weighables) { double totalWeight = 0.0; long totalSelections = 1; List 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; } } 

Con una class Item che contiene un metodo getWeight() (come nella tua domanda):

 /** * 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 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 una Map e un metodo più generico:

 /** * 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 getRandomWeighted(Map 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 : balancedObjects.entrySet()) { weight += e.getValue().doubleValue(); if (value < weight) return e.getKey(); } return null; // Never will reach this point }