Eine gewichtete Version von random.choice

Question

Ich musste eine gewichtete Version von random.choice schreiben (jedes Element in der Liste hat eine unterschiedliche Wahrscheinlichkeit ausgewählt zu werden). Das ist, was ich erstellt habe:

def weightedChoice(choices):
    """Wie random.choice, aber jedes Element kann eine andere Chance haben, ausgewählt zu werden.

    choices kann eine beliebige Iterable sein, die Iterable mit zwei Elementen enthält.
    Technisch gesehen können sie mehr als zwei Elemente haben, der Rest wird einfach ignoriert. Das erste Element ist das ausgewählte Element, das zweite Element ist
    sein Gewicht. Die Gewichte können beliebige numerische Werte sein, was zählt sind die
    relativen Unterschiede zwischen ihnen.
    """
    space = {}
    current = 0
    for choice, weight in choices:
        if weight > 0:
            space[current] = choice
            current += weight
    rand = random.uniform(0, current)
    for key in sorted(space.keys() + [current]):
        if rand < key:
            return choice
        choice = space[key]
    return None

Diese Funktion scheint mir übermäßig komplex und hässlich zu sein. Ich hoffe, dass alle hier einige Vorschläge zur Verbesserung oder alternative Möglichkeiten bieten können. Effizienz ist für mich nicht so wichtig wie die Leserlichkeit und die Sauberkeit des Codes.

Answer 1

import numpy as np
w=np.array([ 0.4,  0.8,  1.6,  0.8,  0.4])
np.random.choice(w, p=w/sum(w))

Answer 2

Ich bin wahrscheinlich zu spät dran, um etwas Nützliches beizutragen, aber hier ist ein einfaches, kurzes und sehr effizientes Snippet:

def choose_index(probabilies):
    cmf = probabilies[0]
    choice = random.random()
    for k in xrange(len(probabilies)):
        if choice <= cmf:
            return k
        else:
            cmf += probabilies[k+1]

Es ist nicht notwendig, Ihre Wahrscheinlichkeiten zu sortieren oder einen Vektor mit Ihrem cmf zu erstellen, und es endet, sobald es seine Wahl getroffen hat. Speicher: O(1), Zeit: O(N), mit durchschnittlicher Laufzeit ~ N/2.

Wenn Sie Gewichte haben, fügen Sie einfach eine Zeile hinzu:

def choose_index(weights):
    probabilities = weights / sum(weights)
    cmf = probabilies[0]
    choice = random.random()
    for k in xrange(len(probabilies)):
        if choice <= cmf:
            return k
        else:
            cmf += probabilies[k+1]

Answer 3

Wenn Ihre Liste gewichteter Auswahlmöglichkeiten relativ statisch ist und Sie häufige Stichproben wünschen, können Sie einen O(N)-Vorverarbeitungsschritt durchführen und die Auswahl dann in O(1) durchführen, indem Sie die Funktionen in dieser verwandten Antwort verwenden.

# ausführen, nur wenn sich `choices` ändert.
preprocessed_data = prep(Gewicht für _, Gewicht in choices)

# O(1) Auswahl
value = choices[sample(preprocessed_data)][0]

Answer 4

Wenn Sie zufällig Python 3 haben und Angst haben, numpy zu installieren oder eigene Schleifen zu schreiben, könnten Sie Folgendes tun:

import itertools, bisect, random

def weighted_choice(choices):
   weights = list(zip(*choices))[1]
   return choices[bisect.bisect(list(itertools.accumulate(weights)),
                                random.uniform(0, sum(weights)))][0]

Weil man alles aus einer Tasche mit Rohradaptern bauen kann! Obwohl... muss ich zugeben, dass Neds Antwort, obwohl etwas länger, leichter zu verstehen ist.

Answer 5

Eine allgemeine Lösung:

import random
def weighted_choice(choices, weights):
    total = sum(weights)
    treshold = random.uniform(0, total)
    for k, weight in enumerate(weights):
        total -= weight
        if total < treshold:
            return choices[k]