Schnelles Sampling und Update von gewichteten Elementen (Datenstruktur wie Rot-Schwarz-Bäume?)

Question

Was ist die geeignete Datenstruktur für diese Aufgabe?

Ich habe eine Reihe von N-Elemente. N ist groß. Jeder Gegenstand hat einen positiven Gewichtswert.

würde Ich mag folgende tun, schnell:

innere Schleife:

Probe, das ein Element, das sein Gewicht nach.

[Ein ...]

Aktualisieren Sie das Gewicht von K Elementen, wobei K < < N.

Wenn ich Probst Gewicht sagen, dies ist anders als einheitliche Probenahme. Die Wahrscheinlichkeit eines Gegenstands ist proportional zu seinem Gewicht. Wenn also zwei Elemente vorhanden sind, und eines ein Gewicht von .8 hat und eines ein Gewicht von .2, dann haben sie eine Wahrscheinlichkeit von 80% bzw. 20%.

Die Anzahl der Elemente N bleibt fest. Gewichte liegen in einem begrenzten Bereich, sagen wir [0, 1]. Gewichte addieren sich nicht immer zu eins.

Eine naive Methode benötigt O (n) Zeitschritte zum Abtasten. Gibt es einen O (log (n)) Algorithmus?

Was ist die geeignete Datenstruktur für diese Aufgabe? Ich glaube, dass rot-schwarze Bäume ungeeignet sind, da sie jeden Gegenstand als gleichwertig behandeln.

Answer 1

Eigentlich können Sie dafür (modifizierte) RB-Bäume verwenden. Darüber hinaus ist eine Modifikation jedes ausgeglichenen Baumes (nicht notwendigerweise binär) möglich.

Der Trick besteht darin, zusätzliche Informationen in jedem Knoten zu speichern - in Ihrem Fall könnte es das Gesamtgewicht des Teilbaums sein, der am Knoten verwurzelt ist, oder so ähnlich.

Wenn Sie den Baum aktualisieren (dh einfügen/löschen), folgen Sie dem Algorithmus für Ihren Lieblingsbaum. Wenn Sie die Struktur ändern, berechnen Sie nur die Summe der Knoten neu (dies ist eine O (1) -Operation für zB Rotationen und B-Baum-Splits und Joins). Wenn Sie das Gewicht eines Elements ändern, aktualisieren Sie die Summen der Vorfahren des Knotens.

Wenn Sie eine Stichprobe erstellen, führen Sie eine modifizierte Version der Suche aus. Sie erhalten die Summe aller Gewichte in den Bäumen (dh Summe der Wurzel) und erzeugen eine positive Zufallszahl niedriger als diese. Dann führen Sie den Suchalgorithmus aus, bei dem Sie zum linken Knoten gehen, wenn die Nummer (die ein Quantil ist, nach dem Sie suchen) kleiner ist als die Summe des linken Knotens. Wenn Sie zum rechten Knoten gehen, subtrahieren Sie die linke Summe vom Quantil.

Diese Beschreibung ist ein wenig chaotisch, aber ich hoffe, es hilft.

Answer 2

Ich mag jpaleceks Antwort. Ich würde hinzufügen, dass der einfachste Weg, um Ihre Zufallszahl zu erhalten wäre (1) Generieren Sie sich von einer einheitlichen (0,1) Verteilung. (2) Multiplizieren Sie u mit der Summe aller Gewichte im Baum.

Answer 3

Da N fest ist, können Sie dies lösen, indem Sie ein Array verwenden, z. B. v, wobei v [i + 1] = v [i] + Gewicht [i], v [1] = Gewicht [0], v [0] = 0 und teste es durch binäre Suche, die log (N) ist, für eine untere Grenze einer Zufallszahl, die gleichmäßig zwischen 0 und der Summe der Gewichte verteilt ist.

Naive Aktualisierung der K-Elemente ist O (KN), eine nachdenkliche ist O (N).

Spoiling noch ein weiteres Interview Frage durch den Kreis von süffisanten :)

Answer 4

Dies ist ein Problem, das ich für einige Monte-Carlo-Simulationen zu lösen hatte. Sie können meinen aktuellen Binärbaum unter dem folgenden Link sehen. Ich habe versucht, es ziemlich STL-ähnlich zu machen. Mein Baum hat eine feste Kapazität, die man mit einem rot-schwarzen Baumansatz, über den ich geredet habe, umgehen konnte. Es ist im Wesentlichen eine Umsetzung der von jpacelek beschriebenen Ideen.

Die Methode ist sehr robust im Umgang mit ungenauen Gleitkommazahlen, weil sie fast immer Größen gleicher Größe summiert und vergleicht, weil sie sich im Baum auf gleicher Höhe befinden.

http://mopssuite.svn.sourceforge.net/viewvc/mopssuite/utils/trunk/include/binary_tree.hpp?view=markup