java - यादृच्छिक प्रतिशत शाखाकरण के लिए कोडिंग पैटर्न?




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

तो मान लें कि हमारे पास एक कोड ब्लॉक है जिसे हम 70% बार और एक 30% बार निष्पादित करना चाहते हैं।

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

काफी सरल। लेकिन क्या होगा अगर हम यह कहना चाहते हैं कि यह आसानी से विस्तार योग्य हो सकता है, 30% / 60% / 10% आदि? यहां इसे जोड़ने और बदलने पर सभी बयानों को बदलने की आवश्यकता होगी जो उपयोग करने के लिए बिल्कुल सही नहीं है, धीमी और गलती उत्प्रेरण।

अब तक मैंने इस उपयोग के मामले के लिए बड़े स्विच को शालीनता से उपयोगी पाया है:

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% के बराबर करना और फिर विभाजित करना।

मुझे लगता है कि इसके लिए एक अनुकूलित हैशमैप या कुछ और के साथ एक हैंडलर बनाने के लिए इतनी परेशानी नहीं होगी, लेकिन मैं सोच रहा हूं कि क्या इस पर सभी स्पेगेटी जाने से पहले इसके लिए कुछ स्थापित तरीका / पैटर्न या लैम्ब्डा है।


जबकि चयनित उत्तर काम करता है, यह दुर्भाग्य से आपके उपयोग के मामले के लिए समान रूप से धीमा है। ऐसा करने के बजाय, आप कुछ अन्य उपनाम नमूने का उपयोग कर सकते हैं। एलियास नमूनाकरण (या उर्फ ​​विधि) एक तकनीक है जिसका उपयोग भारित वितरण के साथ तत्वों के चयन के लिए किया जाता है। यदि उन तत्वों को चुनने का वजन नहीं बदलता है तो आप O (1) समय में चयन कर सकते हैं ! । यदि यह मामला नहीं है, तो आप अभी भी O (1) समय प्राप्त कर सकते हैं यदि आपके द्वारा किए गए चयनों की संख्या और उपनाम तालिका में परिवर्तन (भार बदलकर) के बीच का अनुपात अधिक है। वर्तमान चयनित उत्तर एक O (N) एल्गोरिथ्म का सुझाव देता है, अगली सबसे अच्छी चीज O (लॉग (N)) है जिसे सॉर्ट की गई संभावनाएं और द्विआधारी खोज दी गई है, लेकिन मैंने जो O (1) समय सुझाया है उसे हरा नहीं पा रहा है।

यह साइट अलियास विधि का एक अच्छा अवलोकन प्रदान करती है जो ज्यादातर भाषा अज्ञेयवादी है। अनिवार्य रूप से आप एक तालिका बनाते हैं जहां प्रत्येक प्रविष्टि दो संभावनाओं के परिणाम का प्रतिनिधित्व करती है। तालिका में प्रत्येक प्रविष्टि के लिए एक एकल सीमा है, जिस सीमा के नीचे आपको एक मान मिलता है, ऊपर आपको एक और मूल्य मिलता है। आप संयुक्त संभावनाओं के लिए एक के एक क्षेत्र के साथ एक संभावना ग्राफ बनाने के लिए कई तालिका मूल्यों में बड़ी संभावनाएं फैलाते हैं।

मान लें कि आपके पास प्रायिकता A, B, C, और D हैं, जिनके मूल्य क्रमशः 0.1, 0.1, 0.1 और 0.7 हैं। उपनाम की विधि 0.7 की संभावना को अन्य सभी को फैलाएगी। एक सूचकांक प्रत्येक संभावना के अनुरूप होगा, जहां आपके पास एबीसी के लिए 0.1 और 0.15 और डी के सूचकांक के लिए 0.25 होगा। इसके साथ आप प्रत्येक संभावना को सामान्य करते हैं ताकि आप A प्राप्त करने के 0.4 अवसर और A के सूचकांक में D प्राप्त करने का 0.6 मौका (0.1 / (0.1 + 0.15) और 0.15 / (0.1 + 0.15) के साथ-साथ B और C के C के साथ समाप्त करें। सूचकांक, और डी के सूचकांक में डी होने का 100% मौका (0.25 / 0.25 1 है)।

अनुक्रमण के लिए एक समान वर्दी PRNG (Math.Random ()) को देखते हुए, आपको प्रत्येक अनुक्रमणिका को चुनने की समान संभावना मिलती है, लेकिन आप प्रति इंडेक्स एक सिक्का फ्लिप भी करते हैं जो भारित संभावना प्रदान करता है। आपके पास ए या डी स्लॉट पर उतरने का 25% मौका है, लेकिन इसके भीतर आपके पास केवल A चुनने का 40% मौका है, और 60% D. .40 * .25 = 0.1, हमारी मूल संभावना है, और यदि आप। अन्य सूचकांकों के माध्यम से बिखरे हुए डी की संभावनाओं को जोड़ें, आपको फिर से .70 मिलेगा।

इसलिए यादृच्छिक चयन करने के लिए, आपको केवल 0 से एन तक एक यादृच्छिक सूचकांक उत्पन्न करने की आवश्यकता है, फिर एक सिक्का फ्लिप करें, चाहे आप कितनी भी आइटम जोड़ लें, यह बहुत तेज़ और निरंतर लागत है। एक उपनाम तालिका बनाने से कोड की कई पंक्तियाँ नहीं होती हैं, मेरे अजगर संस्करण में आयात विवरण और लाइन ब्रेक सहित 80 लाइनें हैं, और पंडस लेख में प्रस्तुत संस्करण समान आकार (और यह C ++ है)

आपके जावा कार्यान्वयन के लिए, आप अपने कार्यों को निष्पादित करने वाले संभावित कार्यों और सरणी सूची सूचकांकों के बीच मैप कर सकते हैं, उन कार्यों की एक सरणी बना सकते हैं जिन्हें आप प्रत्येक के सूचकांक के रूप में निष्पादित किया जाता है, वैकल्पिक रूप से आप फ़ंक्शन ऑब्जेक्ट्स ( 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);

संपादित करें:

मैंने अलियासैंपलर विधि के जावा में एक संस्करण बनाया है, कक्षाओं का उपयोग करके, यह नमूना सूचकांक विधि का उपयोग करता है और ऊपर की तरह उपयोग करने में सक्षम होना चाहिए।

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

}

मुझे यकीन नहीं है कि यह एक सामान्य नाम है, लेकिन मुझे लगता है कि मैंने इसे विश्वविद्यालय में भाग्य का पहिया के रूप में सीखा है।

यह मूल रूप से आपके बताए अनुसार काम करता है: यह मूल्यों की एक सूची प्राप्त करता है और "आवृत्ति संख्या" और एक को भारित संभावनाओं के अनुसार चुना जाता है।

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() भाग को छोड़ सकते हैं।

संपादित करें:

यहां मांग के कारण एक वास्तविक संकलन जावा कार्यान्वयन और उपयोग उदाहरण है:

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

मैं ऐसा कुछ करूँगा:

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

इसे यहां चलाएं


संपादित करें: अधिक सुरुचिपूर्ण समाधान के लिए अंत में संपादित देखें। मैं हालांकि इसमें छोड़ दूंगा।

आप अपने प्रतिशत में मैप की गई इन विधियों को संग्रहीत करने के लिए एक 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, आर 1) , (7, r1 = 0.3 ) हैं , तो वे निम्नलिखित प्रविष्टियों में परिणाम करते हैं: r1 = 0.3 और 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();
    }
}







random