编码模式为随机百分比分支？
假设我们有一个代码块，我们要执行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％，然后分开。
我想用自定义的HashMap或其他东西来做一个处理程序并不会有那么多麻烦，但是我想知道是否有一些既定的方式/模式或lambda，因为在我去所有的意大利面条之前。
编辑：请参阅编辑结束更优雅的解决scheme; 我会离开这个。
您可以使用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是通过键sorting的 （例如HashMap不能保证条目），所以你得到按百分比sorting的条目。 这是相关的，因为如果你有两个项目（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; }
你可以像这样创build一个地图：
// 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(); } }
所有这些答案似乎相当复杂，所以我只是发表保持简单的select：
double rnd = Math.random() if((rnd -= 0.6) < 0) 60percentmethod(); else if ((rnd -= 0.3) < 0) 30percentmethod(); else 10percentmethod();
不需要改变其他线路，人们可以很容易地看到发生了什么，而不需要挖掘辅助类。 一个小缺点是，它不强制百分比总和为100％。
我不确定这是否有一个共同的名字，但我认为我把它当成了大学的命运之轮。
它基本上就像你所描述的那样工作：它接收一个数值列表和“频率数字”，根据加权概率select一个数值。
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()); } }
虽然选定的答案有效，但不幸的是，您的用例渐渐变慢。 而不是这样做，你可以使用一个叫做Alias Sampling的东西。 别名抽样（或别名方法）是用于select具有加权分布的元素的技术。 如果select这些元素的权重不变，你可以在O（1）时间做select！ 。 如果不是这种情况，如果您所做select的数量与对别名表所做的更改（更改权重）之间的比率很高，则仍可以分摊O（1）次 。 当前select的答案build议O（N）algorithm，下一个最好的事情是O（log（N））给出sorting的概率和二进制search ，但没有什么是打败我build议的O（1）时间。
这个网站提供了一个很好的Alias方法的概述，主要是语言不可知的。 基本上，你创build一个表，其中每个条目代表两个概率的结果。 对于表中的每个条目都有一个阈值，在阈值以下获得一个值，高于您获得另一个值。 您将较大的概率分布在多个表值中，以便为所有概率组合的概率图创build一个面积为1的概率图。
假设您有概率A，B，C和D，它们的值分别为0.1,0.1,0.1和0.7。 别名方法将0.7的概率传播给所有其他人。 一个指数将对应于每个概率，其中ABC的值为0.1，0.15，D的指数为0.25。 有了这个，你可以规范化每个概率，这样你最终有0.4的几率获得A和0.6的几率得到D的A的指数（0.1 /（0.1 + 0.15）和0.15 /（0.1 + 0.15））以及B和C指数，在D的指数中获得D的几率为100％（0.25 / 0.25为1）。
给定一个无偏差的统一PRNG（Math.Random（））索引，你可以得到相同的select每个索引的概率，但是你也可以为每个索引做一个硬币翻转来提供加权概率。 你有25％的机会着陆在A或D槽，但是在那里你只有40％的机会selectA，而D .40 * .25 = 0.1的60％，我们的原始概率，如果你加上其他指标中所有的D的概率，你会再次得到.70。
所以要进行随机select，只需要生成一个从0到N的随机索引，然后做一次投币，不pipe你添加了多less项，这个速度非常快，而且成本不变。 制作一个别名表并不需要太多的代码行，我的python版本需要80行，包括import语句和换行符，Pandas文章中提供的版本大小相似（而且是C ++）
对于你的java实现，你可以将概率和数组列表索引映射到你必须执行的函数上 ，创build一个函数数组，当你为每个函数索引时执行，或者你可以使用函数对象（ 函子 ）传入参数执行。
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);
编辑：
我已经创build了一个使用类的AliasSampler方法的java版本，这使用示例索引方法，应该能够像上面一样使用。
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(); }
这样就不需要迭代整个地图直到find匹配的条目，但是TreeSet使用专门与另一个关键字进行比较的关键字来查找条目的function。 但是，如果地图中的条目数量很大，这只会有所作为。 但是它保存了几行代码。
我会这样做：
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() );
在这里运行 。
