Wählen Sie k zufällige Elemente aus einer Liste, deren Elemente Gewichte haben

Die Auswahl ohne Gewichte (gleiche Wahrscheinlichkeiten) ist hier schön beschrieben.

Ich habe mich gefragt, ob es einen Weg gibt, diesen Ansatz in einen gewichteten zu verwandeln.

Ich bin auch an anderen Ansätzen interessiert.

Update: Sampling ohne Ersatz

Ich weiß, das ist eine sehr alte Frage, aber ich denke, es gibt einen ordentlichen Trick, dies in O (n) Zeit zu tun, wenn Sie etwas Mathe anwenden!

Die Exponentialverteilung hat zwei sehr nützliche Eigenschaften.

  1. Wenn n Stichproben aus verschiedenen Exponentialverteilungen mit verschiedenen Ratenparametern vorliegen, ist die Wahrscheinlichkeit, dass eine gegebene Stichprobe das Minimum ist, gleich ihrem Ratenparameter dividiert durch die Summe aller Ratenparameter.

  2. Es ist “gedächtnislos”. Wenn Sie also das Minimum bereits kennen, dann ist die Wahrscheinlichkeit, dass eines der verbleibenden Elemente das 2te-zu-Minimum ist, dasselbe wie die Wahrscheinlichkeit, dass das Element das neue wäre, wenn das wahre Minimum entfernt (und niemals erzeugt) würde Mindest. Dies scheint offensichtlich, aber ich denke, aufgrund einiger bedingter Wahrscheinlichkeitsprobleme ist es möglicherweise nicht wahr für andere Distributionen.

Unter Verwendung von Fakt 1 wissen wir, dass die Auswahl eines einzelnen Elements durch Erzeugen dieser exponentiellen Verteilungsstichproben mit dem Ratenparameter gleich der Gewichtung erfolgen kann und dann diejenige mit dem kleinsten Wert gewählt werden kann.

Mit Fakt 2 wissen wir, dass wir die exponentiellen Abtastwerte nicht neu generieren müssen. Erzeuge stattdessen nur eines für jedes Element und nimm die k Elemente mit den niedrigsten Werten.

Das Finden der niedrigsten k kann in O (n) erfolgen. Verwenden Sie den Quickselect- Algorithmus, um das k-te Element zu finden, und führen Sie dann einen weiteren Durchlauf durch alle Elemente durch und geben Sie alle Werte unterhalb des k-ten Werts aus.

Ein nützlicher Hinweis: Wenn Sie keinen unmittelbaren Zugriff auf eine Bibliothek haben, um exponentielle Verteilungsmuster zu erzeugen, können Sie dies einfach tun mit: -ln(rand())/weight

Wenn das Sampling mit Ersetzung durchgeführt wird, können Sie diesen Algorithmus verwenden (hier in Python implementiert):

 import random items = [(10, "low"), (100, "mid"), (890, "large")] def weighted_sample(items, n): total = float(sum(w for w, v in items)) i = 0 w, v = items[0] while n: x = total * (1 - random.random() ** (1.0 / n)) total -= x while x > w: x -= w i += 1 w, v = items[i] w -= x yield v n -= 1 

Dies ist O ( n + m ), wobei m die Anzahl der Elemente ist.

Warum funktioniert das? Es basiert auf dem folgenden Algorithmus:

 def n_random_numbers_decreasing(v, n): """Like reversed(sorted(v * random() for i in range(n))), but faster because we avoid sorting.""" while n: v *= random.random() ** (1.0 / n) yield v n -= 1 

Die function weighted_sample ist nur dieser Algorithmus, der mit einem Spaziergang der items fusioniert wird, um die durch diese Zufallszahlen ausgewählten items auszuwählen.

Dies wiederum funktioniert, weil die Wahrscheinlichkeit, dass n Zufallszahlen 0 … v alle kleiner als z sind, P = ( z / v ) n ist . Löse für z und du bekommst z = vP 1 / n . Das Ersetzen einer Zufallszahl für P wählt die größte Zahl mit der richtigen Verteilung aus; und wir können den Vorgang einfach wiederholen, um alle anderen Zahlen auszuwählen.

Wenn das Sampling ersatzlos ist, können Sie alle Elemente in einen binären Heap versetzen, wobei jeder Knoten die Summe der Gewichte aller Elemente in dieser Subheap speichert. Das Erstellen des Heaps ist O ( m ). Die Auswahl eines zufälligen Elements aus dem Heap unter Berücksichtigung der Gewichte ist O (log m ). Das Entfernen dieses Elements und das Aktualisieren der zwischengespeicherten Summen ist ebenfalls O (log m ). So können Sie n Elemente in O ( m + n log m ) Zeit auswählen.

(Anmerkung: “Gewichtung” bedeutet hier, dass jedes Mal, wenn ein Element ausgewählt wird, die verbleibenden Möglichkeiten mit einer Wahrscheinlichkeit ausgewählt werden, die proportional zu ihren Gewichten ist. Es bedeutet nicht, dass Elemente in der Ausgabe mit einer Wahrscheinlichkeit proportional zu ihren Gewichten erscheinen.)

Hier ist eine Implementierung davon, reichlich kommentiert:

 import random class Node: # Each node in the heap has a weight, value, and total weight. # The total weight, self.tw, is self.w plus the weight of any children. __slots__ = ['w', 'v', 'tw'] def __init__(self, w, v, tw): self.w, self.v, self.tw = w, v, tw def rws_heap(items): # h is the heap. It's like a binary tree that lives in an array. # It has a Node for each pair in `items`. h[1] is the root. Each # other Node h[i] has a parent at h[i>>1]. Each node has up to 2 # children, h[i< <1] and h[(i<<1)+1]. To get this nice simple # arithmetic, we have to leave h[0] vacant. h = [None] # leave h[0] vacant for w, v in items: h.append(Node(w, v, w)) for i in range(len(h) - 1, 1, -1): # total up the tws h[i>>1].tw += h[i].tw # add h[i]'s total to its parent return h def rws_heap_pop(h): gas = h[1].tw * random.random() # start with a random amount of gas i = 1 # start driving at the root while gas >= h[i].w: # while we have enough gas to get past node i: gas -= h[i].w # drive past node i i < <= 1 # move to first child if gas >= h[i].tw: # if we have enough gas: gas -= h[i].tw # drive past first child and descendants i += 1 # move to second child w = h[i].w # out of gas! h[i] is the selected node. v = h[i].v h[i].w = 0 # make sure this node isn't chosen again while i: # fix up total weights h[i].tw -= w i >>= 1 return v def random_weighted_sample_no_replacement(items, n): heap = rws_heap(items) # just make a heap... for i in range(n): yield rws_heap_pop(heap) # and pop n items off it. 

Wenn das Sampling mit einem Ersatz durchgeführt wird, verwenden Sie die Rouletterad-Auswahlmethode (oft in genetischen Algorithmen verwendet):

  1. sortiere die Gewichte
  2. Berechnen Sie die kumulativen Gewichte
  3. [0,1]*totalWeight eine Zufallszahl in [0,1]*totalWeight
  4. finde das Intervall, in das diese Zahl fällt
  5. Wählen Sie die Elemente mit dem entsprechenden Intervall aus
  6. wiederhole k mal

Alt-Text

Wenn das Sampling ersatzlos ist, können Sie die obige Technik anpassen, indem Sie das ausgewählte Element nach jeder Iteration aus der Liste entfernen und dann die Gewichte neu normieren, so dass ihre Summe 1 ist (gültige Wahrscheinlichkeitsverteilungsfunktion).

Ich habe das in Ruby gemacht

https://github.com/fl00r/pickup

 require 'pickup' pond = { "selmon" => 1, "carp" => 4, "crucian" => 3, "herring" => 6, "sturgeon" => 8, "gudgeon" => 10, "minnow" => 20 } pickup = Pickup.new(pond, uniq: true) pickup.pick(3) #=> [ "gudgeon", "herring", "minnow" ] pickup.pick #=> "herring" pickup.pick #=> "gudgeon" pickup.pick #=> "sturgeon" 

Wenn Sie große Arrays von zufälligen Ganzzahlen mit Ersetzung generieren möchten, können Sie stückweise lineare Interpolation verwenden. Zum Beispiel mit NumPy / SciPy:

 import numpy import scipy.interpolate def weighted_randint(weights, size=None): """Given an n-element vector of weights, randomly sample integers up to n with probabilities proportional to weights""" n = weights.size # normalize so that the weights sum to unity weights = weights / numpy.linalg.norm(weights, 1) # cumulative sum of weights cumulative_weights = weights.cumsum() # piecewise-linear interpolating function whose domain is # the unit interval and whose range is the integers up to n f = scipy.interpolate.interp1d( numpy.hstack((0.0, weights)), numpy.arange(n + 1), kind='linear') return f(numpy.random.random(size=size)).astype(int) 

Dies ist nicht effektiv, wenn Sie ohne Ersatz probieren möchten.

Hier ist eine Go-Implementierung von Geodns :

 package foo import ( "log" "math/rand" ) type server struct { Weight int data interface{} } func foo(servers []server) { // servers list is already sorted by the Weight attribute // number of items to pick max := 4 result := make([]server, max) sum := 0 for _, r := range servers { sum += r.Weight } for si := 0; si < max; si++ { n := rand.Intn(sum + 1) s := 0 for i := range servers { s += int(servers[i].Weight) if s >= n { log.Println("Picked record", i, servers[i]) sum -= servers[i].Weight result[si] = servers[i] // remove the server from the list servers = append(servers[:i], servers[i+1:]...) break } } } return result } 

Wenn Sie x Elemente aus einem gewichteten Satz ohne Ersatz auswählen möchten, so dass die Elemente mit einer Wahrscheinlichkeit ausgewählt werden, die proportional zu ihren Gewichten ist:

 import random def weighted_choose_subset(weighted_set, count): """Return a random sample of count elements from a weighted set. weighted_set should be a sequence of tuples of the form (item, weight), for example: [('a', 1), ('b', 2), ('c', 3)] Each element from weighted_set shows up at most once in the result, and the relative likelihood of two particular elements showing up is equal to the ratio of their weights. This works as follows: 1.) Line up the items along the number line from [0, the sum of all weights) such that each item occupies a segment of length equal to its weight. 2.) Randomly pick a number "start" in the range [0, total weight / count). 3.) Find all the points "start + n/count" (for all integers n such that the point is within our segments) and yield the set containing the items marked by those points. Note that this implementation may not return each possible subset. For example, with the input ([('a': 1), ('b': 1), ('c': 1), ('d': 1)], 2), it may only produce the sets ['a', 'c'] and ['b', 'd'], but it will do so such that the weights are respected. This implementation only works for nonnegative integral weights. The highest weight in the input set must be less than the total weight divided by the count; otherwise it would be impossible to respect the weights while never returning that element more than once per invocation. """ if count == 0: return [] total_weight = 0 max_weight = 0 borders = [] for item, weight in weighted_set: if weight < 0: raise RuntimeError("All weights must be positive integers") # Scale up weights so dividing total_weight / count doesn't truncate: weight *= count total_weight += weight borders.append(total_weight) max_weight = max(max_weight, weight) step = int(total_weight / count) if max_weight > step: raise RuntimeError( "Each weight must be less than total weight / count") next_stop = random.randint(0, step - 1) results = [] current = 0 for i in range(count): while borders[current] < = next_stop: current += 1 results.append(weighted_set[current][0]) next_stop += step return results 

In der Frage, auf die Sie sich beziehen, würde Kyles Lösung mit einer trivialen Verallgemeinerung funktionieren. Scannen Sie die Liste und summieren Sie die Gesamtgewichte. Dann sollte die Wahrscheinlichkeit, ein Element zu wählen, sein:

1 – (1 – (# benötigt / (Gewicht übrig))) / (Gewicht bei n). Nach dem Besuch eines Knotens subtrahieren Sie das Gewicht von der Summe. Wenn du n brauchst und n übrig hast, musst du explizit aufhören.

Sie können überprüfen, dass mit allem, was Gewicht 1 hat, dies zu Kyles Lösung vereinfacht.

Bearbeitet: (musste neu überdenken was doppelt so wahrscheinlich gemeint war)

Dieser tut genau das mit O (n) und keinen übermäßigen Speicherverbrauch. Ich glaube, dass dies eine clevere und effiziente Lösung ist, die problemlos in jede Sprache portiert werden kann. Die ersten beiden Zeilen dienen lediglich dazu, Beispieldaten in Drupal zu füllen.

 function getNrandomGuysWithWeight($numitems){ $q = db_query('SELECT id, weight FROM theTableWithTheData'); $q = $q->fetchAll(); $accum = 0; foreach($q as $r){ $accum += $r->weight; $r->weight = $accum; } $out = array(); while(count($out) < $numitems && count($q)){ $n = rand(0,$accum); $lessaccum = NULL; $prevaccum = 0; $idxrm = 0; foreach($q as $i=>$r){ if(($lessaccum == NULL) && ($n < = $r->weight)){ $out[] = $r->id; $lessaccum = $r->weight- $prevaccum; $accum -= $lessaccum; $idxrm = $i; }else if($lessaccum){ $r->weight -= $lessaccum; } $prevaccum = $r->weight; } unset($q[$idxrm]); } return $out; } 

Ich stelle hier eine einfache Lösung für die Auswahl von 1 Element, Sie können es leicht für k Elemente (Java-Stil) erweitern:

 double random = Math.random(); double sum = 0; for (int i = 0; i < items.length; i++) { val = items[i]; sum += val.getValue(); if (sum > random) { selected = val; break; } } 

Ich habe hier einen ähnlichen Algorithmus wie Jason Orendorff in Rust implementiert. Meine Version unterstützt zusätzlich Massenoperationen: Einfügen und Entfernen (wenn Sie eine Menge von Elementen, die durch ihre IDs und nicht durch den gewichteten Auswahlpfad gegeben wurden, entfernen) aus der Datenstruktur in O(m + log n) -Zeit, wobei m die Zahl ist der zu entfernenden Elemente und n der Anzahl der gespeicherten Elemente.

Sampling ohne Austausch mit Rekursion – elegante und sehr kurze Lösung in c #

// wie viele Wege wir wählen 4 von 60 Studenten, so dass jedes Mal, wenn wir andere wählen 4

 class Program { static void Main(string[] args) { int group = 60; int studentsToChoose = 4; Console.WriteLine(FindNumberOfStudents(studentsToChoose, group)); } private static int FindNumberOfStudents(int studentsToChoose, int group) { if (studentsToChoose == group || studentsToChoose == 0) return 1; return FindNumberOfStudents(studentsToChoose, group - 1) + FindNumberOfStudents(studentsToChoose - 1, group - 1); } } 

Ich benutzte eine assoziative Karte (Gewicht, Objekt). beispielsweise:

 { (10,"low"), (100,"mid"), (10000,"large") } total=10110 

Suchen Sie eine Zufallszahl zwischen 0 und ‘Gesamt’ und durchlaufen Sie die Schlüssel, bis diese Zahl in einen bestimmten Bereich passt.