Zufallsvariable mit Verteilung in Tabelle

[Goswin]

Für ein vorgegebenes Dictionary prob_var,

Code: Alles auswählen

prob_var = {v53:123, v07:34, v19:8976, v66:670, ...}  #prob = prob_var[var]

welcher jedem Schlüssel var eine nichtnegative Zahl prob_var[var] zuordnet, soll zufallsverteilt ein var ausgewählt werden, so dass die Auswahlwahrscheinlichkeit von var proportional zu prob_var[var] ist.

Falls ich mir so eine Funktion selber zusammenbastele, dürfte das bei großem prob_var ziemlich ineffizient werden. Gibt es da vielleicht schon etwas Vorprogrammiertes?

[jerch]

@Goswin: KA, ob es da was fertiges gibt, nach KISS ginge es wie folgt (ungetestet):

Code: Alles auswählen

prob_var = {v53:123, v07:34, v19:8976, v66:670}
distribution = sorted([(v,k) for k,v in prob_var.iteritems()], reverse=True) # reverse since more probable is more probable ;)
num = random.randint(1, sum(prob_var.values()))
for value, var in distribution:
    if value < num:
        break
# var ist deine Zielvariable

Die Suche in ``distribution`` ist hier der laufzeitkritische Teil, was aber durch die absteigende Sortierung nach Häufigkeit allerdings unter O(n) gedrückt wird im Mittel.

[BlackJack]

Ungetestet:

Code: Alles auswählen

#!/usr/bin/env python
from bisect import bisect
from random import random


def weighted_choice(items2weights):
    cumulated_weights = list()
    running_total = 0
    for weight in items2weights.viewvalues():
        running_total += weight
        cumulated_weights.append(running_total)
    return items2weights.keys()[
        bisect(cumulated_weights, random() * cumulated_weights[-1])
    ]

[Goswin]

Es funktioniert, vielen Dank!

(Laufzeiten der beiden Vorschläge habe ich noch nicht getestet; es sieht aber gut aus)

[jerch]

@Goswin:
Ich überlass Dir die Fingerübung, die Summen zu bilden, die hab ich nämlich vergessen

Und wenn sich Dein `prob_var` relativ konstant zur zur random-Abfrage bleibt, spart Du mit der Vorberechnung der Verteilung bei den nachgeschalteten random-Aufrufen (falls Laufzeit wirklich zum Problem wird).

[EyDu]

"numpy.random.choice" kann das ebenfalls.

[/me]

Ich überlass Dir die Fingerübung, die Summen zu bilden, die hab ich nämlich vergessen

Ab Python 3.2 kann man da mit itertools.accumulate arbeiten.

[Goswin]

Zwei Kleinigkeiten:

(1)
BlackJack verwendet in seinem Vorschlag eine Methode "items2weights.viewvalues()" wo "items2weights" ein Dictionary ist. Diese Methode existiert bei mir nicht (Python_3.2.3), weshalb ich sie durch "items2weights.values()" ersetzt habe. Alles scheint nun zu funktionieren, aber ich bin mir nicht sicher, ob ich damit Änderungen von unterschelliger Art verursache. Ist die Methode ".viewvalues()" vielleicht veraltet? (kann ich mir bei BlackJack kaum vorstellen)

(2)
Wenn ich den Iterator prob_var.values() verwende, und etwas später (ohne prob_var verändert zu haben) den Iterator prob_var.keys() verwende, kann ich dann absolut sicher sein, dass die Keys und Values der verschiedenen Elemente immer in derselben Reihenfolge ausgegeben werden, obwohl prob_var kein OrderedDict ist?

[DaftWullie]

@Goswin:
BlackJack hat die Methode unter dem Namen verwendet, mit dem sie in Python 2.7 eingeführt wurde. In Python 3 liefern keys() und values() von vornherein "Dictionary view objects", was halt in Python 2.7 nachgerüstet wurde.

Dict Objekte liefern beim iterieren unter den genannten Randbedingungen konstante und "passende" Reihenfolgen.

Beides steht hier.

[Goswin]

Wenn sich Dein `prob_var` relativ konstant zur zur random-Abfrage bleibt, spart Du mit der Vorberechnung der Verteilung bei den nachgeschalteten random-Aufrufen (falls Laufzeit wirklich zum Problem wird).

Aber gerade in so einem Fall wäre deine "KISS"-Suche (mit Laufzeit O(n)) der bisect-Methode (mit Laufzeit O(log(n)) doch hoffnungslos unterlegen!

[jerch]

Aber gerade in so einem Fall wäre deine "KISS"-Suche (mit Laufzeit O(n)) der bisect-Methode (mit Laufzeit O(log(n)) doch hoffnungslos unterlegen!

Das gilt für beide Fälle, Du kannst in beiden Fälle die kumulierten Summen vorberechnen. Falls die Änderung der Einträge << random-Zugriffe ist, lohnt evtl. sogar die Erstellung einer "Urnen"-Liste. Damit reduziert sich der Aufwand auf einen Indexzugriff, also O(1):

Code: Alles auswählen

d = {1: 5, 2: 3, 3: 7, 4: 20, 5: 2}
urn = []
for k, v in d.iteritems():
    urn.extend([k] * v)
...
def pick(urn):
    return urn[int(random.random() * len(urn))]

[EyDu]

Wenn du dir Sorgen um die Laufzeit machst: Wie viele Anfragen musst du denn an das selbe Dictionary stellen? Bei einer Dictionary-Größe von 1000 Elementen ist die reine Python-Lösung von BlackJack bereits bei 25 Werten langsamer als der numpy-Ansatz. Ab 1000 Anfragen geht es schon um den Faktor 10.

[Goswin]

Wie viele Anfragen musst du denn an das selbe Dictionary stellen?

Die Anzahl der Anfragen ist gering, aber das Dictionary ist riesengroß.
Nach (relativ) wenigen Anfragen wird das Dictionary in (relativ) wenigen Einträgen verändert.

Bei einer Dictionary-Größe von 1000 Elementen ist die reine Python-Lösung von BlackJack bereits bei 25 Werten langsamer als der numpy-Ansatz. Ab 1000 Anfragen geht es schon um den Faktor 10.

Du meinst wahrscheinlich: "ab 1000 Werten (Dictionary-Größe) geht es schon um den Faktor 10".

Das ist mir klar, weil numpy_1.7 nämlich mit ziemlicher Sicherheit ebenfalls ein O(log(n))-Verfahren verwendet. Dummerweise hat mein Linux-Mint-Repository nur numpy_1.6, und ich habe keinerlei Erfahrung, wie man ein Linux-Paket installiert, das nicht im Repository vorhanden ist (habe diese Frage bereits im Installations-Forum gestellt).