So implementieren Sie ein Weighted Shuffle

Ich habe kürzlich einen Code geschrieben, den ich für sehr ineffizient hielt, aber da er nur wenige Werte enthielt, habe ich ihn akzeptiert. Ich bin jedoch immer noch an einem besseren Algorithmus für Folgendes interessiert:

1. Eine Liste von X Objekten, denen jeweils ein "Gewicht" zugewiesen wurde
2. Fasse die Gewichte zusammen
3. Generiere eine Zufallszahl von 0 bis zur Summe
4. Durchlaufen Sie die Objekte und subtrahieren Sie deren Gewicht von der Summe, bis die Summe nicht mehr positiv ist
5. Entfernen Sie das Objekt aus der Liste und fügen Sie es am Ende der neuen Liste hinzu

Die Punkte 2, 4 und 5 brauchen alle nZeit, und so handelt es sich um einen O(n^2)Algorithmus.

Kann das verbessert werden?

Als Beispiel für ein gewichtetes Shuffle hat ein Element eine größere Chance, mit einem höheren Gewicht vorne zu stehen.

Beispiel (Ich werde Zufallszahlen generieren, um es real zu machen):

6 Objekte mit Gewichten 6,5,4,3,2,1; Die Summe ist 21

Ich wählte 19 19-6-5-4-3-2 = -1:, also 2 geht in die erste Position, Gewichte sind jetzt 6,5,4,3,1; Die Summe ist 19

Ich wählte 16 16-6-5-4-3 = -2:, also 3 geht in die zweite Position, Gewichte sind jetzt 6,5,4,1; Die Summe ist 16

Ich wählte 3 3-6 = -3:, also 6 geht in die dritte Position, Gewichte sind jetzt 5,4,1; Die Summe ist 10

Ich wählte 8:, 8-5-4 = -1also 4 geht in die vierte Position, Gewichte sind jetzt 5,1; Die Summe ist 6

Ich wählte 5:, 5-5=0also 5 geht in die fünfte Position, Gewichte sind jetzt 1; Die Summe ist 1

Ich habe 1: gewählt 1-1=0, also 1 geht in die letzte Position, ich habe keine Gewichte mehr, ich beende

Dies kann O(n log(n))mithilfe eines Baums implementiert werden.

Erstellen Sie zunächst den Baum, und behalten Sie in jedem Knoten die kumulative Summe aller untergeordneten Knoten rechts und links von jedem Knoten bei.

Um ein Element abzutasten, tasten Sie rekursiv vom Stammknoten ab. Verwenden Sie dabei die kumulativen Summen, um zu entscheiden, ob Sie den aktuellen Knoten, einen Knoten von links oder einen Knoten von rechts zurückgeben. Setzen Sie die Gewichtung jedes Mal, wenn Sie einen Knoten abtasten, auf Null und aktualisieren Sie auch die übergeordneten Knoten.

Dies ist meine Implementierung in Python:

import random

def weigthed_shuffle(items, weights):
    if len(items) != len(weights):
        raise ValueError("Unequal lengths")

    n = len(items)
    nodes = [None for _ in range(n)]

    def left_index(i):
        return 2 * i + 1

    def right_index(i):
        return 2 * i + 2

    def total_weight(i=0):
        if i >= n:
            return 0
        this_weigth = weights[i]
        if this_weigth <= 0:
            raise ValueError("Weigth can't be zero or negative")
        left_weigth = total_weight(left_index(i))
        right_weigth = total_weight(right_index(i))
        nodes[i] = [this_weigth, left_weigth, right_weigth]
        return this_weigth + left_weigth + right_weigth

    def sample(i=0):
        this_w, left_w, right_w = nodes[i]
        total = this_w + left_w + right_w
        r = total * random.random()
        if r < this_w:
            nodes[i][0] = 0
            return i
        elif r < this_w + left_w:
            chosen = sample(left_index(i))
            nodes[i][1] -= weights[chosen]
            return chosen
        else:
            chosen = sample(right_index(i))
            nodes[i][2] -= weights[chosen]
            return chosen

    total_weight() # build nodes tree

    return (items[sample()] for _ in range(n - 1))

Verwendung:

In [2]: items = list(range(10))
   ...: weights = list(range(10, 0, -1))
   ...:

In [3]: for _ in range(10):
   ...:     print(list(weigthed_shuffle(items, weights)))
   ...:
[5, 0, 8, 6, 7, 2, 3, 1, 4]
[1, 2, 5, 7, 3, 6, 9, 0, 4]
[1, 0, 2, 6, 8, 3, 7, 5, 4]
[4, 6, 8, 1, 2, 0, 3, 9, 7]
[3, 5, 1, 0, 4, 7, 2, 6, 8]
[3, 7, 1, 2, 0, 5, 6, 4, 8]
[1, 4, 8, 2, 6, 3, 0, 9, 5]
[3, 5, 0, 4, 2, 6, 1, 8, 9]
[6, 3, 5, 0, 1, 2, 4, 8, 7]
[4, 1, 2, 0, 3, 8, 6, 5, 7]

weigthed_shuffleist ein Generator, so dass Sie die Top- kArtikel effizient abtasten können. Wenn Sie das gesamte Array mischen möchten, iterieren Sie einfach bis zur Erschöpfung über den Generator (mithilfe der listFunktion).

AKTUALISIEREN:

Weighted Random Sampling (2005; Efraimidis, Spirakis) bietet hierfür einen sehr eleganten Algorithmus. Die Implementierung ist super einfach und läuft auch in O(n log(n)):

def weigthed_shuffle(items, weights):
    order = sorted(range(len(items)), key=lambda i: -random.random() ** (1.0 / weights[i]))
    return [items[i] for i in order]

EDIT: Diese Antwort interpretiert die Gewichte nicht so, wie es zu erwarten wäre. Dh ein Gegenstand mit Gewicht 2 ist nicht doppelt so wahrscheinlich wie einer mit Gewicht 1.

Eine Möglichkeit, eine Liste zu mischen, besteht darin, jedem Element in der Liste Zufallszahlen zuzuweisen und nach diesen Zahlen zu sortieren. Wir können diese Idee erweitern, wir müssen nur gewichtete Zufallszahlen auswählen. Zum Beispiel könnten Sie verwenden random() * weight. Unterschiedliche Auswahlmöglichkeiten führen zu unterschiedlichen Verteilungen.

In etwas wie Python sollte dies so einfach sein wie:

items.sort(key = lambda item: random.random() * item.weight)

Achten Sie darauf, dass Sie die Schlüssel nicht mehrmals auswerten, da sie unterschiedliche Werte haben.

Lassen Sie uns zunächst davon ausgehen, dass die Gewichtung eines bestimmten Elements in der zu sortierenden Liste konstant ist. Es wird sich nicht zwischen den Iterationen ändern. Wenn ja, dann ... nun, das ist ein größeres Problem.

Zur Veranschaulichung verwenden wir ein Kartenspiel, bei dem die Bildkarten nach vorne gewichtet werden sollen. weight(card) = card.rank. Diese zu summieren, wenn wir die Verteilung der Gewichte nicht kennen, ist in der Tat O (n) einmal.

Diese Elemente werden in einer sortierten Struktur gespeichert, z. B. als Änderung an einer indexierbaren Überspringliste , sodass von einem bestimmten Knoten aus auf alle Indizes der Ebenen zugegriffen werden kann:

   1 10
 o ---> o -------------------------------------------- -------------> o Oberste Ebene
   1 3 2 5
 o ---> o ---------------> o ---------> o ---------------- -----------> o Stufe 3
   1 2 1 2 5
 o ---> o ---------> o ---> o ---------> o ----------------- ----------> o Stufe 2
   1 1 1 1 1 1 1 1 1 1 1 
 o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o Untere Ebene

Kopf 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. NIL
      Knoten Knoten Knoten Knoten Knoten Knoten Knoten Knoten Knoten Knoten Knoten Knoten

In diesem Fall "beansprucht" jeder Knoten jedoch auch so viel Platz wie sein Gewicht.

Wenn Sie nun eine Karte in dieser Liste nachschlagen, können Sie in O (log n) Zeit auf ihre Position in der Liste zugreifen und sie in O (1) Zeit aus den zugehörigen Listen entfernen. Ok, es könnte nicht O (1) sein, es könnte O (log log n) sein (ich müsste viel mehr darüber nachdenken). Das Entfernen des sechsten Knotens im obigen Beispiel würde das Aktualisieren aller vier Ebenen umfassen - und diese vier Ebenen sind unabhängig von der Anzahl der Elemente in der Liste (abhängig davon, wie Sie die Ebenen implementieren).

Da das Gewicht eines Elements konstant ist, kann einfach darauf sum -= weight(removed)verzichtet werden, die Struktur erneut zu durchlaufen.

Sie haben also einmalige Kosten für O (n) und einen Nachschlagewert für O (log n) sowie Kosten für das Entfernen von O (1) von der Liste. Dies wird zu O (n) + n * O (log n) + n * O (1), was eine Gesamtleistung von O (n log n) ergibt.

Schauen wir uns das mit Karten an, denn das habe ich oben verwendet.

      10
top 3 -----------------------> 4d
                                .
       3 7.
    2 ---------> 2d ---------> 4d
                  . .
       1 2. 3 4.
bot 1 -> Ad -> 2d -> 3d -> 4d

Dies ist ein wirklich kleines Deck mit nur 4 Karten. Es sollte leicht zu erkennen sein, wie dies erweitert werden kann. Mit 52 Karten hätte eine ideale Struktur 6 Ebenen (log ₂ (52) ~ = 6), aber wenn Sie in die Überspringlisten graben, könnte dies sogar auf eine kleinere Zahl reduziert werden.

Die Summe aller Gewichte ist 10. Sie erhalten also eine Zufallszahl aus [1 .. 10) und seiner 4. Sie durchsuchen die Überspringliste, um das Element zu finden, das sich an der Decke befindet (4). Da 4 kleiner als 10 ist, wechseln Sie von der obersten zur zweiten Ebene. Four ist größer als 3, also sind wir jetzt bei der 2 der Diamanten. 4 ist weniger als 3 + 7, also bewegen wir uns nach unten und 4 ist weniger als 3 + 3, also haben wir 3 Diamanten.

Nachdem Sie die 3 Diamanten aus der Struktur entfernt haben, sieht die Struktur nun wie folgt aus:

       7
top 3 ----------------> 4d
                         .
       3 4.
    2 ---------> 2d -> 4d
                  . .
       1 2. 4.
bot 1 -> Ad -> 2d -> 4d

Sie werden feststellen, dass die Knoten eine Menge 'Platz' einnehmen, die proportional zu ihrem Gewicht in der Struktur ist. Dies ermöglicht die gewichtete Auswahl.

Da dies in etwa einem ausgeglichenen Binärbaum entspricht, muss die Suche in diesem nicht über die unterste Ebene erfolgen (dies wäre O (n)). Stattdessen können Sie von oben nach unten in der Struktur springen, um herauszufinden, wonach Sie suchen zum.

Vieles davon könnte stattdessen mit einer Art ausgeglichenem Baum geschehen. Das Problem dabei ist, dass das Neuausbalancieren der Struktur beim Entfernen eines Knotens verwirrend wird, da dies keine klassische Baumstruktur ist und die Verwaltung sich daran erinnert, dass die 4 von Diamanten jetzt von den Positionen [6 7 8 9] auf [3 4 verschoben wird 5 6] kann mehr kosten als die Vorteile der Baumstruktur.

Während die Überspringliste in ihrer Fähigkeit, die Liste in O (log n) -Zeit zu überspringen, einem Binärbaum nahekommt, hat sie die Einfachheit, stattdessen mit einer verknüpften Liste zu arbeiten.

Das soll nicht heißen, dass es einfach ist , all dies zu tun (Sie müssen immer noch alle Links im Auge behalten, die Sie ändern müssen, wenn Sie ein Element entfernen), aber es bedeutet, dass Sie nur so viele Ebenen und deren Links aktualisieren, wie Sie haben als alles rechts auf der richtigen Baumstruktur.