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


Итак, допустим, у нас есть блок кода, который мы хотим выполнить 70% раз и еще один-30% раз.

if(Math.random() < 0.7)
    70percentmethod();
else
    30percentmethod();

достаточно просто. Но что, если мы хотим, чтобы он был легко расширяемым, чтобы сказать, 30%/60%/10% и т. д.? Здесь это потребует добавления и изменения всех операторов if на изменение, которое не совсем здорово использовать, медленное и ошибочное побуждение.

до сих пор я нашел большие переключатели, чтобы быть прилично полезным для этого случая использования, для пример:

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

который можно очень легко изменить на:

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

но они также имеют свои недостатки, будучи громоздкими и разделенными на определенное количество подразделений.

что-то идеальное было бы основано на системе "частотного номера", я думаю, так:

(1,a),(1,b),(2,c) -> 25% a, 25% b, 50% c

тогда, если вы добавили еще один:

(1,a),(1,b),(2,c),(6,d) -> 10% a, 10% b, 20% c, 60% d

поэтому просто сложите числа, сделав сумму равной 100%, а затем разделите ее.

небось было бы не так уж сложно сделать обработчик для него с помощью настроенной хэш-карты или чего-то еще, но мне интересно, есть ли какой-то установленный способ/шаблон или лямбда для него, прежде чем я пойду на все спагетти.

7   51  

7 ответов:

EDIT: см. редактирование в конце для более элегантного решения. Я оставлю это, хотя.

можно использовать 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();
}

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

что касается расщепления, он должен идти что-то вроде этого: С кортежем класса, как это

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

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

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

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