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

Ответ 1

РЕДАКТИРОВАТЬ: Подробнее см. в конце для более элегантного решения. Я оставлю это, хотя.

Вы можете использовать NavigableMap для хранения этих методов, сопоставленных с их процентами.

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 сортируется (например, HashMap не дает никаких гарантий для записей) ключами, так что вы получаете записи, упорядоченные по их процентам. Это важно, потому что, если у вас есть два элемента (3, r1), (7, r2), они приводят к следующим записям: r1 = 0.3 и r2 = 1.0, и их нужно оценивать в этом порядке (например, если они оцениваются в обратном порядке результат всегда будет r2).

Что касается расщепления, он должен выглядеть примерно так: С классом Tuple, подобным этому

static class Pair<X, Y>
{
    public Pair(X f, Y s)
    {
        first = f;
        second = s;
    }

    public final X first;
    public final Y second;
}

Вы можете создать такую ​​карту

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

И все это добавлено в класс

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

РЕДАКТИРОВАТЬ:
Собственно, вышесказанное - это то, что вы получаете, если у вас идея застряла у вас в голове и не ставьте под сомнение ее правильность. Сохраняя интерфейс класса RandomRunner, это намного проще:

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

Ответ 2

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

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

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

Ответ 3

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

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

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

Ответ 4

Пока выбранный ответ работает, он, к сожалению, асимптотически медленный для вашего варианта использования. Вместо этого вы можете использовать нечто, называемое Alias ​​Sampling. Алгоритм выборки (или псевдоним) - это метод, используемый для выбора элементов с взвешенным распределением. Если веса выбора этих элементов не изменяются, вы можете сделать выбор в течение 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 in D (0,25/0,25 равен 1).

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

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

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

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

}

Ответ 5

Вы можете вычислить кумулятивную вероятность для каждого класса, выбрать случайное число из [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));
        }
    }
}

Ответ 6

Следующее немного напоминает ответ @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 при поиске записи с ключом, специально сравниваемым с другим ключом. Это, однако, будет иметь значение только в том случае, если количество записей на карте велико. Однако он сохраняет несколько строк кода.

Ответ 7

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

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

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