Datenstruktur für die geladenen Würfel?

Nehme an, dass ich eine n-seitige geladen sterben, wo jede Seite k hat einige Wahrscheinlichkeit p_k zu kommen, wenn ich es Rollen. Ich bin gespannt, ob es gut ist-Algorithmus für die Speicherung dieser Informationen statisch (d.h. für einen festen Satz von Wahrscheinlichkeiten), so dass ich effizient simulieren Sie eine zufällige Augenzahl.

Derzeit habe ich eine O(lg n) Lösung für dieses problem. Die Idee ist zum speichern einer Tabelle der kumulierten Wahrscheinlichkeit, dass die ersten k Seiten für alle k, Sie generiert eine zufällige reelle Zahl im Bereich [0, 1), und ausführen einer binären Suche über die Tabelle, um den größten index, deren kumulative Wert ist nicht größer als der gewählte Wert. Ich mag diese Lösung, aber es scheint seltsam, dass die Laufzeit nicht nehmen, die Wahrscheinlichkeiten berücksichtigt. Insbesondere in der extremale Fälle von einer Seite immer kommen oder die Werte gleichmäßig verteilt, ist es möglich, um das Ergebnis der roll-O(1) mit einem naiven Ansatz, obwohl meine Lösung dauert noch logarithmicallh viele Schritte.

Hat jemand irgendwelche Vorschläge, wie dieses problem zu lösen, in einer Weise, die irgendwie "adaptive" in der runtime?

BEARBEITEN: auf der Grundlage der Antworten auf diese Frage habe ich oben geschrieben ein Artikel, der viele Ansätze für dieses problem, zusammen mit Ihren Analysen. Es sieht aus wie Vose Umsetzung der alias Methode gibt Θ(n) preprocessing Zeit O(1) Zeit pro Wurf, das ist wirklich beeindruckend. Hoffentlich ist das eine sinnvolle Ergänzung zu den Informationen in den Antworten!

Es ist vernünftig, dass es einen O(1) - Lösung für jeden spezifischen Fall.

InformationsquelleAutor templatetypedef | 2011-02-17

111

Du suchst die alias-Methode die eine O(1) Methode zur Erzeugung einer festen diskreten Wahrscheinlichkeitsverteilung (vorausgesetzt, Sie können auf Einträge in einem array der Länge n in konstanter Zeit) mit einer Zeit von O(n) set-up. Sie finden es dokumentiert in Kapitel 3 (PDF) von "Non-Uniform Random Variate Generation" von Luc Devroye.

Die Idee ist, nehmen Sie Ihre array von Wahrscheinlichkeiten p_k und produzieren drei neue n-element-arrays, q_k, a_k - und b_k. Jedes q_k ist eine Wahrscheinlichkeit zwischen 0 und 1, und jedes a_k - und b_k ist eine Ganzzahl zwischen 1 und n ein.

Erzeugen wir Zufallszahlen zwischen 1 und n durch die Erzeugung von zwei Zufallszahlen r und s, zwischen 0 und 1. Seien i = floor(r*N)+1. Wenn q_i < s dann wieder ein_i else return b_i. Die Arbeit in der alias-Methode ist, herauszufinden, wie zu produzieren q_k, a_k - und b_k.
- Für solch einen nützlichen Algorithmus, der die Alias-Methode ist überraschenderweise nicht sehr bekannt.
- Für das Protokoll: ich veröffentlichte eine kleine C-Bibliothek für die Stichproben mittels des alias-Methode apps.jcns.fz-juelich.de/ransampl.
- eine spezifische Implementierung der alias Methode ist möglicherweise langsamer, dann eine Methode, mit der schlechteren Zeit-Komplexität wie Roulette Wheel für eine bestimmte n und für eine bestimmte Anzahl von Zufallszahlen zu generieren, die durch Konstante Faktoren, die bei der Implementierung von algorithmen.
InformationsquelleAutor mhum
4

Verwenden Sie eine ausgewogene binären Suchbaum (oder binäre Suche in einem array) und erhalten O(log n) Komplexität. Haben Sie einen Knoten für jede sterben, Ergebnis und habe die Schlüssel der Intervall getriggert wird Ergebnis.
```
function get_result(node, seed):
    if seed < node.interval.start:
        return get_result(node.left_child, seed)
    else if seed < node.interval.end:
        //start <= seed < end
        return node.result
    else:
        return get_result(node.right_child, seed)
```
Das gute an dieser Lösung ist, dass Sie sehr einfach zu implementieren, aber hat immer noch gute Komplexität.
- Hand-made binären Baum wie oben ist einfach zu implementieren, aber es ist nicht garantiert, ausgewogen
- Können Sie garantieren, dass es ausgewogen ist, wenn Sie bauen es in der richtigen Reihenfolge.
InformationsquelleAutor hugomg
3

Ich überlege, Granulieren Ihren Tisch.

Statt mit einer Tabelle mit den kumulativ für jedes sterben Wert, Sie konnte erstellen Sie ein integer-array der Länge xN, wo x ist im Idealfall eine hohe Zahl, zur Erhöhung der Genauigkeit der Wahrscheinlichkeit.

Füllen Sie das array mit dem index (normiert durch xN) als den kumulativen Wert und in jedem 'slot' im array speichern-wäre-würfeln, wenn dieser index kommt.

Vielleicht könnte ich erklären einfacher mit einem Beispiel:

Mit drei würfeln: P(1) = 0.2, P(2) = 0.5, P(3) = 0.3

Erstellen Sie ein array, in diesem Fall werde ich wählen, eine einfache Länge von, sagen wir 10. (das heißt, x = 3.33333)
```
arr[0] = 1,
arr[1] = 1,
arr[2] = 2,
arr[3] = 2,
arr[4] = 2,
arr[5] = 2,
arr[6] = 2,
arr[7] = 3,
arr[8] = 3,
arr[9] = 3
```
Dann um die Wahrscheinlichkeit, nur zufällig eine Zahl zwischen 0 und 10 und einfach Zugriff, index.

Dieser Methode könnte Locker Genauigkeit, sondern erhöhen die x-und die Genauigkeit ausreichend sein.
- Für die volle Genauigkeit, die Sie tun können, die array-lookup als einen ersten Schritt, und der array-Intervallen entsprechen, die für mehrere Seiten, eine Suche dort.
InformationsquelleAutor andrewjs

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.