Ereignisse mit unterschiedlichen Eintrittswahrscheinlichkeiten

[Daniel Thoma]

Hallo Julian,

ich wäre an einer Beispielimplementation sehr interessiert. Hast du da was für mich?

Ich hab' jetzt mal eine in Java gebastelt. Ich hoffe, es ist kein Fehler drin, bei binärer Suche haut man da gerne mal irgendwo ne 1 zu viel oder zu wenig rein.

Erstmal die Klasse RandomChooser, die die Ereignisse verwaltet und die Auswahl durchführt:

  
import java.util.Collections;  
import java.util.Map;  
  
public class RandomChooser<T> {  
  
    private Map<? extends T, Double> event2propability;  
    private T[] events;  
    private double[] probabilities;  
  
    /**  
     * Creates a new instance of RandomChooser  
     */  
    @SuppressWarnings("unchecked")  
    public RandomChooser(Map<? extends T, Double> event2propability) {  
        this.event2propability = Collections.unmodifiableMap(event2propability);  
        int pos = 0;  
        events = (T[]) new Object[event2propability.size()];  
        // Enthält die beiden "überflüssigen" Elemente. Macht die binäre Suche einfacher.  
        probabilities = new double[event2propability.size() + 1];  
        probabilities[0] = 0;  
        for (Map.Entry<? extends T, Double> entry: event2propability.entrySet()) {  
            probabilities[pos + 1] = probabilities[pos] + entry.getValue();  
            ++pos;  
        }  
        // Explizites setzen auf 1, da sich die Wahrscheinlichkeiten bei Rundungsfehleren evtl. nicht exakt aufsumiereren.  
        probabilities[probabilities.length - 1] = 1;  
    }  
  
    public Map<? extends T, Double> getEvent2propability() {  
        return event2propability;  
    }  
  
    public T choose(double d) {  
        if (d < 0 || d >= 1) {  
            throw new IllegalArgumentException();  
        }  
        int a = 0;  
        int b = probabilities.length - 1;  
        int pos = 0;  
        while (true) {  
            pos = (a + b) / 2;  
            if (probabilities[pos] > d) {  
                b = pos - 1;  
            } else if (probabilities[pos + 1] <= d) {  
                a = pos + 1;  
            } else {  
                break;  
            }  
        }  
        return events[pos];  
    }  
  
}  

Verwenden kann man das dann folgendermaßen:

  
Random rand = new Random(seed);  
Map<String, Double> events = new HashMap<String, Double>();  
events.put("A", 0.3);  
events.put("B", 0.2);  
events.put("C", 0.5);  
RandomChooser<String> chooser = new RandomChooser<String>(events);  
  
String event = chooser.choose(random.nextDouble());  

Grüße

Daniel