Struttura dei dati per i dadi caricati?

Supponiamo che io abbia un dado caricato su n lati in cui ogni lato k ha qualche probabilità di salire quando lo lancio. Sono curioso di sapere se esiste un buon algoritmo per archiviare queste informazioni staticamente (cioè per un insieme fisso di probabilità) in modo da poter simulare in modo efficiente un lancio casuale del dado.

Attualmente, ho una soluzione O (lg n) per questo problema. L’idea è di memorizzare una tabella della probabilità cumulativa dei primi k lati per tutti i k, di generare un numero reale casuale nell’intervallo [0, 1) ed eseguire una ricerca binaria sulla tabella per ottenere l’indice più grande il cui totale il valore non è maggiore del valore scelto. Mi piace questa soluzione, ma mi sembra strano che il runtime non tenga conto delle probabilità. In particolare, nei casi estremi di un lato sempre in aumento o dei valori distribuiti uniformsmente, è ansible generare il risultato del roll in O (1) usando un approccio ingenuo, sebbene la mia soluzione effettui ancora molti passaggi logaritmici.

Qualcuno ha qualche suggerimento su come risolvere questo problema in un modo che è in qualche modo “adattativo” nel suo runtime?

EDIT : Sulla base delle risposte a questa domanda, ho scritto un articolo che descrive molti approcci a questo problema , insieme alle loro analisi. Sembra che l’implementazione di Vose del metodo alias dia il tempo di pre-elaborazione Θ (n) e il tempo O (1) per tiro di dado, che è davvero impressionante. Si spera che questa sia un’utile aggiunta alle informazioni contenute nelle risposte!

Stai cercando il metodo alias che fornisce un metodo O (1) per generare una distribuzione di probabilità discreta fissa (supponendo che tu possa accedere a voci in un array di lunghezza n in tempo costante) con un setup O (n) una tantum . Potete trovarlo documentato nel capitolo 3 (PDF) di “Non-Uniform Random Variate Generation” di Luc Devroye.

L’idea è di prendere la tua serie di probabilità p e produrre tre nuovi array di n elementi, qk, ak e bk . Ogni q k è una probabilità compresa tra 0 e 1, e ognuno a k e b k è un numero intero compreso tra 1 e n.

Generiamo numeri casuali tra 1 e n generando due numeri casuali, r e s, tra 0 e 1. Lascia che i = floor (r * N) +1. Se qi i . Il lavoro nel metodo di alias sta nel capire come produrre q k , ak eb.

Utilizzare un albero di ricerca binario bilanciato (o ricerca binaria in un array) e ottenere la complessità di O (log n). Avere un nodo per ogni risultato del dado e avere le chiavi come l’intervallo che attiverà quel risultato.

 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) 

La cosa buona di questa soluzione è che è molto semplice da implementare ma ha ancora una buona complessità.

Sto pensando di granulare il tuo tavolo.

Invece di avere una tabella con il cumulativo per ogni valore del dado, è ansible creare un array intero di lunghezza xN, dove x è idealmente un numero elevato per aumentare l’accuratezza della probabilità.

Popolare questo array usando l’indice (normalizzato da xN) come valore cumulativo e, in ogni ‘slot’ nell’array, memorizza il risultato del lancio dei dadi se questo indice viene visualizzato.

Forse potrei spiegare più facilmente con un esempio:

Usando tre dadi: P (1) = 0,2, P (2) = 0,5, P (3) = 0,3

Crea un array, in questo caso sceglierò una lunghezza semplice, ad esempio 10. (ovvero, 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 

Quindi, per ottenere la probabilità, basta randomizzare un numero compreso tra 0 e 10 e accedere semplicemente all’indice.

Questo metodo potrebbe perdere precisione, ma aumentare x e accuratezza saranno sufficienti.