Aleatoriedade ponderada em Java

Em Java, dado n itens, cada um com peso w , como escolher um item random da coleção com uma chance igual a w ?

Suponha que cada peso seja um dobro de 0,0 a 1,0 e que os pesos na coleção totalizem 1. Item.getWeight () retorna o peso do item.

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

Uma maneira elegante seria provar uma distribuição exponencial http://en.wikipedia.org/wiki/Exponential_distribution, onde os pesos serão a taxa da distribuição (lambda). Finalmente, você simplesmente seleciona o menor valor amostrado.

Em Java isso é assim:

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

Não tenho certeza se isso é mais eficiente do que as outras abordagens, mas se o tempo de execução não é o problema, é uma solução muito atraente.

E esta é a mesma ideia usando o 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(); } 

Você pode obter o stream de pesos de input, por exemplo, a partir de um mapa, convertendo-o com .entrySet().stream() .

O TreeMap já faz todo o trabalho para você.

Crie um TreeMap. Crie pesos com base no seu método de escolha. Adicione os pesos começando com 0.0 e adicione o peso do último elemento ao seu contador de peso em execução.

ie (Scala):

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

Então você apenas tem que gerar rand = new Random(); num = rand.nextDouble() * count rand = new Random(); num = rand.nextDouble() * count para obter um número válido.

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

lhe dará o item ponderado random.

Para quantidades menores de buckets também é possível: Crie uma matriz de 100.000 Int's e distribua o número do bucket com base no peso entre os campos. Em seguida, você cria um número inteiro random entre 0 e 100.000-1 e recupera imediatamente o número do depósito.

Se você quiser eficiência de seleção em tempo de execução, então, tomar um pouco mais de tempo na configuração provavelmente seria melhor. Aqui está uma solução possível. Tem mais código, mas garante a seleção log (n).

WeightedItemSelector Implementa a seleção de um object random de uma coleção de objects ponderados. A seleção é garantida para ser executada no log (n) time.

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

Range Implements range selection para alavancar a seleção 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 simplesmente encapsula um item a ser selecionado.

 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. Dê alguma ordem arbitrária aos itens … (i1, i2, …, in) … com pesos w1, w2, …, wn.
  2. Escolha um número random entre 0 e 1 (com granularidade suficiente, usando qualquer function de aleatorização e escalonamento apropriado). Chame isso de r0.
  3. Deixe j = 1
  4. Subtraia wj do ​​seu r (j-1) para obter rj. Se rj <= 0, você seleciona o item ij. Caso contrário, incremente j e repita.

Acho que já fiz isso antes … mas provavelmente há maneiras mais eficientes de fazer isso.

Abaixo está um randomizador que mantém a precisão em proporções também:

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

Com uma class Item que contém um método getWeight() (como na sua pergunta):

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

Com um Map e um método mais 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 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 }