Шаблон кодирования для случайного процентного ветвления?

все эти ответы кажутся довольно сложными, поэтому я просто опубликую простую альтернативу:

double rnd = Math.random()
if((rnd -= 0.6) < 0)
    60percentmethod();
else if ((rnd -= 0.3) < 0)
    30percentmethod();
else
    10percentmethod();

Не нужно менять другие строки, и можно довольно легко увидеть, что происходит, не копаясь во вспомогательных классах. Небольшой недостаток заключается в том, что он не обеспечивает, чтобы проценты суммировались до 100%.

Я не уверен, что есть общее название для этого, но я думаю, что я узнал это как Колесо Фортуны еще в университете.

он в основном работает так, как вы описали: он получает список значений и "номера частот", и один выбирается в соответствии с взвешенными вероятностями.

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

список может быть параметром функции, если вы хотите обобщить.

Это также работает с числами с плавающей запятой и цифры не должны быть нормированный. Если вы нормализуете (например, чтобы суммировать до 1), Вы можете пропустить list.sum() часть.

EDIT:

из-за спроса вот фактический пример реализации и использования компиляции 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());
  }
}

хотя выбранный ответ работает, он, к сожалению, асимптотически медленный для вашего случая использования. Вместо этого вы можете использовать что-то под названием Отбора Проб Псевдоним. Выборка псевдонимов (или метод псевдонимов) - это метод, используемый для выбора элементов с взвешенным распределением. Если вес выбора этих элементов не изменяется, вы можете сделать выбор в O (1) Время!. Если это не так, вы все равно можете получить амортизированный O(1) время если соотношение между количеством выбранных элементов и изменениями в таблице псевдонимов (изменение Весов) велико. Текущий выбранный ответ предлагает алгоритм O(N), следующая лучшая вещь-O(log(N)) с учетом отсортированных вероятностей и бинарный поиск, но ничто не собирается бить O(1) раз я предложил.

этот сайт предоставляет хороший обзор метода псевдонима, который в основном является агностиком языка. По существу вы создаете таблицу, в которой каждая запись представляет результат двух вероятностей. Существует один порог для каждой записи в таблице, ниже порога вы получаете одно значение, выше вы получаете другое значение. Вы распределяете большие вероятности по нескольким табличным значениям, чтобы создать вероятностный график с областью одного для всех вероятностей вместе взятых.

скажем, у вас есть вероятности A, B, C и D, которые имеют значения 0.1, 0.1, 0.1 и 0.7 соответственно. Метод псевдонима распространил бы вероятность 0,7 на все остальные. Один индекс будет соответствовать каждой вероятности, где у вас будет 0.1 и 0.15 для ABC и 0.25 для индекса D. При этом вы нормализуете каждую вероятность так, что вы в конечном итоге получаете 0.4 шанс получить A и 0.6 шанс получить D в индексе A (0.1/(0.1 + 0.15) и 0.15/(0.1 + 0.15) соответственно), а также индекс B и C и 100% шанс получить D в индексе D (0.25/0.25 равен 1).

объективно единый ГПСЧ (Математика.Random ()) для индексации вы получаете равную вероятность выбора каждого индекса, но вы также делаете бросок монеты на индекс, который обеспечивает взвешенную вероятность. У вас есть 25% шанс посадки на слот A или D, но в пределах этого у вас есть только 40% шанс выбора A и 60% D.40 * .25 = 0.1, наша исходная вероятность, и если вы сложите все вероятности D, разбросанные по другим индексам, вы получите .70 опять.

Итак, чтобы сделать случайный выбор, вам нужно только сгенерируйте случайный индекс от 0 до N, затем сделайте бросок монеты, независимо от того, сколько элементов вы добавляете, это очень быстро и постоянных затрат. Создание таблицы псевдонимов также не занимает много строк кода, моя версия python занимает 80 строк, включая операторы импорта и разрывы строк, а версия, представленная в статье Pandas, имеет аналогичный размер (и это C++)

для вашей реализации java можно сопоставить между вероятностями и индексами списка массивов для ваших функций вы должны выполнить, создав количество функций которые выполняются по мере индексирования для каждого, в качестве альтернативы вы можете использовать объекты функций (функторы) которые имеют метод, который вы используете для передачи параметров для выполнения.

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

EDIT:

Я создал версию в java метода AliasSampler, используя классы, это использует метод индекса образца и должно быть в состоянии использоваться как выше.

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://stackoverflow.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);
        }
    }

}

вы можете вычислить кумулятивную вероятность для каждого класса, выбрать случайное число из [0; 1) и посмотреть, где это число падает.

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

следующее немного похоже на ответ @daniu, но использует методы, предоставляемые 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();
}

таким образом, нет необходимости повторять всю карту, пока не будет найдена соответствующая запись, но возможности TreeSet в поиске используется запись с ключом, специально сравнивая с другим ключом. Однако это будет иметь значение только в том случае, если количество записей на карте велико. Однако он сохраняет несколько строк кода.

Я бы сделал что-то вроде этого:

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

пример использования:

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()
);

запустить его здесь.