java - setborder - ¿Patrón de codificación para ramificación porcentual aleatoria?
setborder java (7)
Digamos que tenemos un bloque de código que queremos ejecutar el 70% de las veces y otro el 30% de las veces.
if(Math.random() < 0.7)
70percentmethod();
else
30percentmethod();
Suficientemente simple. Pero, ¿qué sucede si queremos que sea fácilmente expandible para decir, 30% / 60% / 10%, etc.? Aquí requeriría agregar y cambiar todas las declaraciones if sobre el cambio que no es exactamente genial para usar, lento e inductor de errores.
Hasta ahora he encontrado que los interruptores grandes son decentemente útiles para este caso de uso, por ejemplo:
switch(rand(0, 10)){
case 0:
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:70percentmethod();break;
case 8:
case 9:
case 10:30percentmethod();break;
}
Que se puede cambiar muy fácilmente a:
switch(rand(0, 10)){
case 0:10percentmethod();break;
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:60percentmethod();break;
case 8:
case 9:
case 10:30percentmethod();break;
}
Pero también tienen sus inconvenientes, ya que son engorrosos y se dividen en una cantidad predeterminada de divisiones.
Supongo que algo ideal se basaría en un sistema de "número de frecuencia", así:
(1,a),(1,b),(2,c) -> 25% a, 25% b, 50% c
entonces si agregaste otro:
(1,a),(1,b),(2,c),(6,d) -> 10% a, 10% b, 20% c, 60% d
Entonces, simplemente sumando los números, haciendo que la suma sea igual al 100% y luego divídala.
Supongo que no sería un problema crear un controlador con un hashmap personalizado o algo así, pero me pregunto si hay alguna forma / patrón establecido o lambda para ello antes de ponerme todos los espaguetis en esto.
Haría algo como esto:
class RandomMethod {
private final Runnable method;
private final int probability;
RandomMethod(Runnable method, int probability){
this.method = method;
this.probability = probability;
}
public int getProbability() { return probability; }
public void run() { method.run(); }
}
class MethodChooser {
private final List<RandomMethod> methods;
private final int total;
MethodChooser(final List<RandomMethod> methods) {
this.methods = methods;
this.total = methods.stream().collect(
Collectors.summingInt(RandomMethod::getProbability)
);
}
public void chooseMethod() {
final Random random = new Random();
final int choice = random.nextInt(total);
int count = 0;
for (final RandomMethod method : methods)
{
count += method.getProbability();
if (choice < count) {
method.run();
return;
}
}
}
}
Uso de la muestra:
MethodChooser chooser = new MethodChooser(Arrays.asList(
new RandomMethod(Blah::aaa, 1),
new RandomMethod(Blah::bbb, 3),
new RandomMethod(Blah::ccc, 1)
));
IntStream.range(0, 100).forEach(
i -> chooser.chooseMethod()
);
Lo siguiente es un poco como la respuesta @daniu pero hace uso de los métodos proporcionados por
TreeMap
:
private final NavigableMap<Double, Runnable> map = new TreeMap<>();
{
map.put(0.3d, this::branch30Percent);
map.put(1.0d, this::branch70Percent);
}
private final SecureRandom random = new SecureRandom();
private void branch30Percent() {}
private void branch70Percent() {}
public void runRandomly() {
final Runnable value = map.tailMap(random.nextDouble(), true).firstEntry().getValue();
value.run();
}
De esta manera, no es necesario iterar todo el mapa hasta que se encuentre la entrada coincidente, pero se
TreeSet
las capacidades de
TreeSet
para encontrar una entrada con una clave que se compare específicamente con otra clave.
Sin embargo, esto solo hará una diferencia si el número de entradas en el mapa es grande.
Sin embargo, guarda algunas líneas de código.
No estoy seguro de si hay un nombre común para esto, pero creo que aprendí esto como la rueda de la fortuna en la universidad.
Básicamente funciona tal como lo describió: recibe una lista de valores y "números de frecuencia" y se elige uno de acuerdo con las probabilidades ponderadas.
list = (1,a),(1,b),(2,c),(6,d)
total = list.sum()
rnd = random(0, total)
sum = 0
for i from 0 to list.size():
sum += list[i]
if sum >= rnd:
return list[i]
return list.last()
La lista puede ser un parámetro de función si desea generalizar esto.
Esto también funciona con números de coma flotante y los números no tienen que normalizarse.
Si normaliza (para resumir hasta 1 por ejemplo), puede omitir la parte
list.sum()
.
EDITAR:
Debido a la demanda aquí hay un ejemplo real de implementación y uso de compilación de Java:
import java.util.ArrayList;
import java.util.Random;
public class RandomWheel<T>
{
private static final class RandomWheelSection<T>
{
public double weight;
public T value;
public RandomWheelSection(double weight, T value)
{
this.weight = weight;
this.value = value;
}
}
private ArrayList<RandomWheelSection<T>> sections = new ArrayList<>();
private double totalWeight = 0;
private Random random = new Random();
public void addWheelSection(double weight, T value)
{
sections.add(new RandomWheelSection<T>(weight, value));
totalWeight += weight;
}
public T draw()
{
double rnd = totalWeight * random.nextDouble();
double sum = 0;
for (int i = 0; i < sections.size(); i++)
{
sum += sections.get(i).weight;
if (sum >= rnd)
return sections.get(i).value;
}
return sections.get(sections.size() - 1).value;
}
public static void main(String[] args)
{
RandomWheel<String> wheel = new RandomWheel<String>();
wheel.addWheelSection(1, "a");
wheel.addWheelSection(1, "b");
wheel.addWheelSection(2, "c");
wheel.addWheelSection(6, "d");
for (int i = 0; i < 100; i++)
System.out.print(wheel.draw());
}
}
Podrías calcular la probabilidad acumulada para cada clase, elegir un número aleatorio de [0; 1) y ver dónde cae ese número.
class WeightedRandomPicker {
private static Random random = new Random();
public static int choose(double[] probabilties) {
double randomVal = random.nextDouble();
double cumulativeProbability = 0;
for (int i = 0; i < probabilties.length; ++i) {
cumulativeProbability += probabilties[i];
if (randomVal < cumulativeProbability) {
return i;
}
}
return probabilties.length - 1; // to account for numerical errors
}
public static void main (String[] args) {
double[] probabilties = new double[]{0.1, 0.1, 0.2, 0.6}; // the final value is optional
for (int i = 0; i < 20; ++i) {
System.out.printf("%d/n", choose(probabilties));
}
}
}
Si bien la respuesta seleccionada funciona, desafortunadamente es asintóticamente lenta para su caso de uso. En lugar de hacer esto, podría usar algo llamado Alias Sampling . El muestreo de alias (o método de alias) es una técnica utilizada para la selección de elementos con una distribución ponderada. Si el peso de elegir esos elementos no cambia, ¡puede hacer la selección en O (1) tiempo! . Si este no es el caso, aún puede obtener el tiempo O (1) amortizado si la relación entre el número de selecciones que realiza y los cambios que realiza en la tabla de alias (cambio de pesos) es alta. La respuesta actual seleccionada sugiere un algoritmo O (N), la siguiente mejor opción es O (log (N)) dadas las probabilidades ordenadas y la búsqueda binaria , pero nada va a superar el tiempo O (1) que sugerí.
Este sitio proporciona una buena visión general del método Alias que es principalmente independiente del lenguaje. Esencialmente, crea una tabla donde cada entrada representa el resultado de dos probabilidades. Hay un umbral único para cada entrada en la tabla, debajo del umbral se obtiene un valor, por encima se obtiene otro valor. Distribuye las probabilidades más grandes a través de múltiples valores de la tabla para crear un gráfico de probabilidad con un área de uno para todas las probabilidades combinadas.
Digamos que tiene las probabilidades A, B, C y D, que tienen los valores 0.1, 0.1, 0.1 y 0.7 respectivamente. El método de alias distribuiría la probabilidad de 0.7 a todos los demás. Un índice correspondería a cada probabilidad, donde tendría 0.1 y 0.15 para ABC, y 0.25 para el índice de D. Con esto, normaliza cada probabilidad para que termine con 0.4 posibilidades de obtener A y 0.6 posibilidades de obtener D en el índice de A (0.1 / (0.1 + 0.15) y 0.15 / (0.1 + 0.15) respectivamente) así como B y C índice, y 100% de probabilidad de obtener D en el índice de D (0.25 / 0.25 es 1).
Dado un PRNG uniforme imparcial (Math.Random ()) para la indexación, obtienes la misma probabilidad de elegir cada índice, pero también haces un lanzamiento de moneda por índice que proporciona la probabilidad ponderada. Tienes un 25% de posibilidades de aterrizar en la ranura A o D, pero dentro de eso solo tienes un 40% de posibilidades de elegir A y un 60% de D.40 * .25 = 0.1, nuestra probabilidad original, y si Si sumas todas las probabilidades de D esparcidas por los otros índices, obtendrás .70 nuevamente.
Entonces, para hacer una selección aleatoria, solo necesita generar un índice aleatorio de 0 a N, luego hacer un lanzamiento de moneda, sin importar cuántos elementos agregue, este es un costo muy rápido y constante. Hacer una tabla de alias tampoco toma tantas líneas de código, mi versión de Python toma 80 líneas incluyendo declaraciones de importación y saltos de línea, y la versión presentada en el artículo de Pandas tiene un tamaño similar (y es C ++)
Para su implementación de Java, uno podría asignar entre las probabilidades y los índices de la lista de matrices a sus funciones que debe ejecutar, creando una matriz de funciones que se ejecutan a medida que indexa cada una, alternativamente, puede usar objetos de función ( functors ) que tienen un método que utiliza para pasar parámetros a ejecutar.
ArrayList<(YourFunctionObject)> function_list;
// add functions
AliasSampler aliassampler = new AliasSampler(listOfProbabilities);
// somewhere later with some type T and some parameter values.
int index = aliassampler.sampleIndex();
T result = function_list[index].apply(parameters);
EDITAR:
He creado una versión en java del método AliasSampler, usando clases, esto usa el método de índice de muestra y debería poder usarse como se indicó anteriormente.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class AliasSampler {
private ArrayList<Double> binaryProbabilityArray;
private ArrayList<Integer> aliasIndexList;
AliasSampler(ArrayList<Double> probabilities){
// java 8 needed here
assert(DoubleStream.of(probabilities).sum() == 1.0);
int n = probabilities.size();
// probabilityArray is the list of probabilities, this is the incoming probabilities scaled
// by the number of probabilities. This allows us to figure out which probabilities need to be spread
// to others since they are too large, ie [0.1 0.1 0.1 0.7] = [0.4 0.4 0.4 2.80]
ArrayList<Double> probabilityArray;
for(Double probability : probabilities){
probabilityArray.add(probability);
}
binaryProbabilityArray = new ArrayList<Double>(Collections.nCopies(n, 0.0));
aliasIndexList = new ArrayList<Integer>(Collections.nCopies(n, 0));
ArrayList<Integer> lessThanOneIndexList = new ArrayList<Integer>();
ArrayList<Integer> greaterThanOneIndexList = new ArrayList<Integer>();
for(int index = 0; index < probabilityArray.size(); index++){
double probability = probabilityArray.get(index);
if(probability < 1.0){
lessThanOneIndexList.add(index);
}
else{
greaterThanOneIndexList.add(index);
}
}
// while we still have indices to check for in each list, we attempt to spread the probability of those larger
// what this ends up doing in our first example is taking greater than one elements (2.80) and removing 0.6,
// and spreading it to different indices, so (((2.80 - 0.6) - 0.6) - 0.6) will equal 1.0, and the rest will
// be 0.4 + 0.6 = 1.0 as well.
while(lessThanOneIndexList.size() != 0 && greaterThanOneIndexList.size() != 0){
//https://.com/questions/16987727/removing-last-object-of-arraylist-in-java
// last element removal is equivalent to pop, java does this in constant time
int lessThanOneIndex = lessThanOneIndexList.remove(lessThanOneIndexList.size() - 1);
int greaterThanOneIndex = greaterThanOneIndexList.remove(greaterThanOneIndexList.size() - 1);
double probabilityLessThanOne = probabilityArray.get(lessThanOneIndex);
binaryProbabilityArray.set(lessThanOneIndex, probabilityLessThanOne);
aliasIndexList.set(lessThanOneIndex, greaterThanOneIndex);
probabilityArray.set(greaterThanOneIndex, probabilityArray.get(greaterThanOneIndex) + probabilityLessThanOne - 1);
if(probabilityArray.get(greaterThanOneIndex) < 1){
lessThanOneIndexList.add(greaterThanOneIndex);
}
else{
greaterThanOneIndexList.add(greaterThanOneIndex);
}
}
//if there are any probabilities left in either index list, they can''t be spread across the other
//indicies, so they are set with probability 1.0. They still have the probabilities they should at this step, it works out mathematically.
while(greaterThanOneIndexList.size() != 0){
int greaterThanOneIndex = greaterThanOneIndexList.remove(greaterThanOneIndexList.size() - 1);
binaryProbabilityArray.set(greaterThanOneIndex, 1.0);
}
while(lessThanOneIndexList.size() != 0){
int lessThanOneIndex = lessThanOneIndexList.remove(lessThanOneIndexList.size() - 1);
binaryProbabilityArray.set(lessThanOneIndex, 1.0);
}
}
public int sampleIndex(){
int index = new Random().nextInt(binaryProbabilityArray.size());
double r = Math.random();
if( r < binaryProbabilityArray.get(index)){
return index;
}
else{
return aliasIndexList.get(index);
}
}
}
Todas estas respuestas parecen bastante complicadas, así que solo publicaré la alternativa de mantenerlo simple:
double rnd = Math.random()
if((rnd -= 0.6) < 0)
60percentmethod();
else if ((rnd -= 0.3) < 0)
30percentmethod();
else
10percentmethod();
No necesita cambiar otras líneas y uno puede ver fácilmente lo que sucede, sin profundizar en las clases auxiliares. Una pequeña desventaja es que no impone que los porcentajes sumen 100%.
EDITAR: vea la edición al final para obtener una solución más elegante. Aunque dejaré esto adentro.
Puede usar un
NavigableMap
para almacenar estos métodos asignados a sus porcentajes.
NavigableMap<Double, Runnable> runnables = new TreeMap<>();
runnables.put(0.3, this::30PercentMethod);
runnables.put(1.0, this::70PercentMethod);
public static void runRandomly(Map<Double, Runnable> runnables) {
double percentage = Math.random();
for (Map.Entry<Double, Runnable> entry : runnables){
if (entry.getKey() < percentage) {
entry.getValue().run();
return; // make sure you only call one method
}
}
throw new RuntimeException("map not filled properly for " + percentage);
}
// or, because I''m still practicing streams by using them for everything
public static void runRandomly(Map<Double, Runnable> runnables) {
double percentage = Math.random();
runnables.entrySet().stream()
.filter(e -> e.getKey() < percentage)
.findFirst().orElseThrow(() ->
new RuntimeException("map not filled properly for " + percentage))
.run();
}
NavigableMap
está
ordenado
(por ejemplo,
HashMap
no garantiza las entradas) por teclas, por lo que obtiene las entradas ordenadas por sus porcentajes.
Esto es relevante porque si tiene dos elementos
(3, r1)
,
(7, r2)
, dan como resultado las siguientes entradas:
r1 = 0.3
y
r2 = 1.0
y deben evaluarse en este orden (por ejemplo, si se evalúan en el orden inverso, el resultado
siempre
sería
r2
).
En cuanto a la división, debería ser algo como esto: con una clase Tuple como esta
static class Pair<X, Y>
{
public Pair(X f, Y s)
{
first = f;
second = s;
}
public final X first;
public final Y second;
}
Puedes crear un mapa como este
// the parameter contains the (1,m1), (1,m2), (3,m3) pairs
private static Map<Double,Runnable> splitToPercentageMap(Collection<Pair<Integer,Runnable>> runnables)
{
// this adds all Runnables to lists of same int value,
// overall those lists are sorted by that int (so least probable first)
double total = 0;
Map<Integer,List<Runnable>> byNumber = new TreeMap<>();
for (Pair<Integer,Runnable> e : runnables)
{
total += e.first;
List<Runnable> list = byNumber.getOrDefault(e.first, new ArrayList<>());
list.add(e.second);
byNumber.put(e.first, list);
}
Map<Double,Runnable> targetList = new TreeMap<>();
double current = 0;
for (Map.Entry<Integer,List<Runnable>> e : byNumber.entrySet())
{
for (Runnable r : e.getValue())
{
double percentage = (double) e.getKey() / total;
current += percentage;
targetList.put(current, r);
}
}
return targetList;
}
Y todo esto agregado a una clase
class RandomRunner {
private List<Integer, Runnable> runnables = new ArrayList<>();
public void add(int value, Runnable toRun) {
runnables.add(new Pair<>(value, toRun));
}
public void remove(Runnable toRemove) {
for (Iterator<Pair<Integer, Runnable>> r = runnables.iterator();
r.hasNext(); ) {
if (toRemove == r.next().second) {
r.remove();
break;
}
}
}
public void runRandomly() {
// split list, use code from above
}
}
EDITAR:
En realidad, lo anterior es lo que obtienes si tienes una idea atrapada en tu cabeza y no la cuestionas adecuadamente.
Mantener la interfaz de clase
RandomRunner
, esto es mucho más fácil:
class RandomRunner {
List<Runnable> runnables = new ArrayList<>();
public void add(int value, Runnable toRun) {
// add the methods as often as their weight indicates.
// this should be fine for smaller numbers;
// if you get lists with millions of entries, optimize
for (int i = 0; i < value; i++) {
runnables.add(toRun);
}
}
public void remove(Runnable r) {
Iterator<Runnable> myRunnables = runnables.iterator();
while (myRunnables.hasNext()) {
if (myRunnables.next() == r) {
myRunnables.remove();
}
}
public void runRandomly() {
if (runnables.isEmpty()) return;
// roll n-sided die
int runIndex = ThreadLocalRandom.current().nextInt(0, runnables.size());
runnables.get(runIndex).run();
}
}