随机百分比分支的编码模式?

53

假设我们有一个代码块,我们希望执行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%,然后进行分割。

我想制作一个处理程序来使用自定义哈希映射或其他方式来完成这个任务,但在我开始时,我想知道是否有一些已经确定的方法/模式或lambda可以用来解决这个问题。


3
注意,rand(0,10) 会产生11个可能的值,而你的“60%”实际上是70%,总和为110%。 - CJ Dennis
这个问题是许多其他问题的重复......人们在发布之前确实应该搜索! - Olivier Grégoire
@OlivierGregoire 只链接了一个... - Mischa
@MischaBehrend 1, 2, 3, 4。哦,抱歉...你只想要“一个”。 - Olivier Grégoire
可能是Java中的随机加权选择的重复问题。 - izstas
显示剩余4条评论
7个回答

28

编辑: 请查看结尾处的编辑获取更优雅的解决方案。我将保留这部分内容。

你可以使用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.3r2 = 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();
    }
}

7
30PercentMethod和70PercentMethod不是有效的Java方法名称。 - Michael
7
@Michael,你说得对。我只是在重复OP在问题中提供的名称。 - daniu
4
我很惊讶这个答案得到了如此好的反响(无意冒犯)。如果你有更多方法要添加到地图上,每种方法发生的可能性将不会显而易见——你需要从相邻值中减去每个值。它也不允许你赋予两种方法同等的权重。 - Michael
2
它允许多个等权结果,因为键是累积概率。因此,如果您想要具有概率0.25、0.25、0.5的结果A、B、C,则应该有(0.25,A)、(0.5,B)和(1.0,C)。 - Gareth McCaughan
2
@Michael 我自己也有些惊讶。我现在已经添加了一个更简单的解决方案到答案中,应该可以解决你的问题。 - daniu
显示剩余9条评论

27

所有这些答案看起来都很复杂,所以我将发布一个简单的替代方案:

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

不需要更改其他行,人们可以很容易地看到发生了什么,而无需深入研究辅助类。小缺点是它不强制百分比总和为100%。


1
为什么不使用 if(rnd < 0.6) 呢? - user121330
2
如果有 if(rnd < 0.6),那么下一个 if 就会是 if(rnd < 0.9),也就是要跟踪之前 ifs 的百分比总和。如果只有3或4个选项,这不是问题,但是想象一下如果你有30个选项,然后改变了第一个选项的权重,你就必须更改每个随后的 if 语句的权重。这样每个权重只与它自己的 if 语句相关联,当然除了最后的 else。 - JChristen
检查这段代码:https://ideone.com/Lsjo8e:如果使用else,您可以获得10-12%的操作符,使用else if可以获得25-32%的操作符,如果rnd-=0.30,则其余部分为if rnd -= 0.6。 - Dhaval dave
@Dhavaldave 这对于随机值来说是正常的 - 如果你将循环次数增加到例如10000,方差将会减少。 - jpa
@jpa:我已经运行了这个和其他算法,例如:https://ideone.com/AoBH84 对于10、100、1000、10000等不同的数据量,它们始终存在10%的偏差。我同意对于随机值可能会出现这种情况,但是否有更准确的算法或代码呢? - Dhaval dave
1
@Dhavaldave 您可能希望了解一下泊松分布。但就我而言,例如10000产生的结果为10 -> 1021 30 -> 3022 60 -> 5957左右有2%的差异。如果您想要精确的比例,请用要素数量填充数组并对其进行洗牌。 - jpa

16

我不确定这个算法是否有一个通用的名称,但我在大学学习时学到了它被称为“命运之轮”。

它的工作原理就像你描述的那样:它接收一个值列表和“频率数字”,然后根据加权概率选择一个值。

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()部分。

编辑:

由于需求,这里是实际编译的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());
  }
}

15
可以的,但这更多是一个普遍性问题。我相信您知道如何在Java中实现它... - SteakOverflow
1
很棒,浮点数的观点非常好。如果有一个选项可以将某些值设置为小于1的超低概率分支,那就太好了。不过,这并不完全是我要找的,后端足够简单。我更感兴趣的是如何以高效的方式将其链接到实际制作列表的部分。 - Moff Kalast
2
我确信Java程序员能够阅读伪代码并将其转化为所需的SingletonRunnerFactory调用。 - ndim
1
@Michael:那我告诉你一个:回答问题的人可能并不完全确定习语,但是他们有一个好的解决方案,供OP(或任何其他人)使用。当然:一个程序员如果不能理解伪代码或与他们当前使用的语言非常相似的不同语言中的代码片段,那么他就不是一个程序员。真的。 - Gábor
@HongOoi 你能详细说明一下你认为缺少什么吗? - SteakOverflow
显示剩余4条评论

8
虽然所选答案可行,但对于您的用例来说,它不幸地渐近缓慢。相反,您可以使用称为别名抽样的东西。别名抽样(或别名方法)是一种用于选择具有加权分布的元素的技术。如果选择这些元素的权重不变,则可以在O(1)时间内进行选择!如果不是这种情况,则如果您进行选择的次数与更改别名表(更改权重)的次数之比高,则仍然可以获得摊销O(1)时间。当前所选的答案建议使用O(N)算法,下一个最好的算法是给定排序的概率和二进制搜索的O(log(N)),但没有什么能击败我提出的O(1)时间。

这个网站提供了一个很好的关于Alias方法的概述,它主要是与语言无关的。基本上,你需要创建一张表格,其中每个条目代表两个概率的结果。每个条目都有一个单独的阈值,在阈值下,你会得到一个值,而在阈值以上,则会得到另一个值。你需要将更大的概率分散到多个表格值中,以创建一个概率图,所有概率的总面积为一。

假设您有概率A、B、C和D,它们的值分别为0.1、0.1、0.1和0.7。别名方法将会把0.7的概率分布到其他所有概率上。每个概率对应一个索引,其中ABC的概率为0.1和0.15,D的索引为0.25。通过这种方式,您可以对每个概率进行归一化处理,以便在A的索引中获得0.4的A机会和0.6的D机会(分别为0.1 /(0.1 + 0.15)和0.15 /(0.1 + 0.15)),以及B和C的索引,并在D的索引中获得100%的D机会(0.25 / 0.25等于1)。
给定一个无偏的均匀伪随机数生成器(Math.Random())进行索引,您可以选择每个索引的概率相等,但是您还需要对每个索引进行一次硬币翻转以提供加权概率。您有25%的机会落在A或D插槽上,但在这之内,您只有40%的机会选择A和60%的机会选择D。0.40 * 0.25 = 0.1,这是我们最初的概率,如果将D的所有概率加起来散布在其他索引中,您会再次得到0.70。

因此,要进行随机选择,您只需要从0到N生成一个随机索引,然后进行硬币翻转,无论添加多少项,这都是非常快速和恒定成本。制作别名表也不需要太多代码行,我的Python版本包括导入语句和换行符共计80行,Pandas文章中介绍的版本大小类似(它是C ++)

对于你的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);

编辑:

我已经用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://dev59.com/22Qn5IYBdhLWcg3wPlGj
            // 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);
        }
    }

}

3
我通常同意这个原则,但在这种情况下,我会认为实际实现别名表是相当简单的,所以它并不是一个大问题,并且使用起来比标记答案要简单得多。此外,问题询问了他所谈论的“事实上编码模式”的内容,我认为别名方法就是这种编码模式。因此,虽然顶部回答提供了一个简单的解决方案,但它也不是这种问题的标准解决方案。我认为这就像在应该使用链表或哈希表时使用数组一样。 - Krupip
2
@Michael 为了避免听起来很防御,我应该重申我原则上同意,并总结一下,我认为这不属于过早优化的最大原因是,在我看来,别名方法是OP似乎要求的标准编码模式。 - Krupip
2
@Michael,我的方法保证至少和你提供的例子一样快,即使在非常罕见的最佳情况下:使用Math.random()生成索引,比较值,返回索引,根据索引执行。就是这样。在任何需要执行多次迭代搜索的情况下,它总是更快的。这不是某种理论上的斐波那契堆,因为高固定成本而可能在给定足够大的N时变得更好,你可以通过理解它的工作原理来证明它。 - Krupip
2
@Micheal,需要解释某些事情并不会使其失效,哈希表很难解释,但我怀疑你不会对它们的使用做出同样的判断。此外,我已经在这里解释了算法,所以您甚至不需要查看文章,我列出的Python代码也不难理解,我只是无法理解您在那部分的困惑。而且像我说的,23与35?差别不大。再次强调,性能提升并不微不足道,它是几个数量级的提升,显然因为它是O(1)具有~= const成本,OP毫无疑问也在进行循环采样。 - Krupip
2
@Michael,我不同意你认为解释某些东西会让它变得复杂的观点,我也不同意我们不知道这是一个性能问题。而且在我回复你之前,你已经决定“完成”了。 - Krupip
显示剩余9条评论

6
您可以计算每个类别的累积概率,从 [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));
        }
    }
}

2
以下类似于 @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 在查找与另一个键具体比较的条目时的能力。但是,只有在映射表中的条目数量很大时,才会产生影响。然而,它确实可以节省几行代码。


0

我会这样做:

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

在此运行


1
看到你在其他答案中抱怨“不是Java”之类的话语,还有那种充满攻击性的被动语气,真的有点有趣。而你自己的回答却连人类语言都没有,我至少看不到任何解释你的代码、你所使用的算法、优缺点等等的内容。与其浪费时间批评其他答案(实际上它们非常好),为什么不先改进自己的回答呢?(P.S.:http://www.differencebetween.com/difference-between-probability-and-vs-chance/) - Sebastian Mach
@SebastianMach,我没有用被动攻击的语气说话,但如果你这样理解了,我也无能为力。我倾向于让我的评论尽可能简洁。我发表的所有内容都是建设性的批评,说明我认为他们的回答可以改进的地方。没有人能免受批评 - 没有必要生气并将其个人化。 - Michael
@SebastianMach 现在,我认为你在最后一个链接中有点自谦了,但是没错,我已经修复了它。 - Michael
2
就个人而言,我一直很感激像那样削弱自己的链接。由于英语不是我的母语,有可能“chance”本来会是我的第一选择。 - Sebastian Mach

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接