Montag, Mai 25, 2020

Datenstruktur für die geladenen Würfel?

Nehme an, dass ich eine n-seitige geladen sterben, wo jede Seite k hat einige Wahrscheinlichkeit pk 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.

3 Kommentare

  1. 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 pk und produzieren drei neue n-element-arrays, qk, ak – und bk. Jedes qk ist eine Wahrscheinlichkeit zwischen 0 und 1, und jedes ak – und bk 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 qi < s dann wieder eini else return bi. Die Arbeit in der alias-Methode ist, herauszufinden, wie zu produzieren qk, ak – und bk.

  2. 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.
  3. 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.

Kostenlose Online-Tests