Newsgroup: it.comp.lang.c++
Titolo: [Forse-OT] Generatore numero casuali con distribuzione empirica

Salve a tutti,
forse sono un po' OT in quanto il problema che ho non e' tanto relativo 
al linguaggio C++ ma piu' che altro e' di natura algoritmica; dato pero' 
che sto sviluppando in C++ spero vogliate/possiate/sappiate aiutarmi.
Dunque, ho un array di float a[] i cui elementi rappresentano ognuno una 
probabilità di estrazione (no, non e' un programma per il gioco del 
lotto :-) ), quindi:
a[0] = prob. di uscita elemento 0
.
.
.
a[n] = prob. di uscita elemento n
Alcuni valori di a[] potrebbero anche essere nulli.
Quello che mi servirebbe e' una funzione che, preso in pasto l'array a[] 
mi estragga i numeri da 1 a n secondo le probabilita' definite da a[].
Diciamo che qualche idea mi e' venuta (tipo ordino l'array dal valore 
più piccolo al piu' grande, estraggo un numero con prob. uniforme con 
radn(), poi sommo le i valori di a[] finche' non supero il valore 
estratto ecc....) ma a parte che non l'ho provata, il altro problema 
consiste nel fatto che tale funzione verrebbe richiamata un numero molto 
elevato di volte, in un programma che deve prestare moltissima 
attenzione al tempo di esecuzione (quindi vorrei evitare algoritmi di 
ordinamento).
Per rendere l'idea, n può variare da 50 a 70, ogni ciclo di estrazioni 
deve estrarre da 10 a 20 numeri e sono previsti da 5 a 10 cicli.
In giro ho trovato questa libreria: 
http://statistik.wu-wien.ac.at/unuran/index.html
 ma mi pare di capire 
che non è possibile dare come dato di ingresso un array di probabilita' 
come il mio a[].
Qualcuno ha qualche idea di come approcciare il problema?
Ringrazio per ogni aiuto.
Saluti
Libra

Libra wrote:
interessante .... Provo a escogitare un'idea. Perdonami se sparo 
uan cavolata, ma data l'ora non avrò molto tempo di ripensarci.
Dovresti mappare tutte le probabilità in una sorta di array 
"integrale" cumulativo, magari moltiplicando anche i dati in 
modo che siano tutti interi,
Es.
nota, suppongo gli eventi siano mutualmente incompatibili e che 
la somma degli eventi sia la certezza (array normalizzato). Se 
non si applica al tuo caso, che non hai spiegato in dettaglio, 
la soluzione è da cestinare. Al limite potresti aggiungere un 
ulteriore evento la cui probabilità è 1,0 - somma di tutte le 
altre. Se invece gli eventi non sono incompatibili crolla tutto 
e si richiedono analisi più attente
array probabilità "disgiunte" singole
[0] = 0,2
[1] = 0,3
[2] = 0,1
[3] = 0,4
creiamo l'array integrale, moltiplicato per 10 (questo step è 
facoltativo se rand, che non ricordo, estrae già numeri compresi 
tra zero e uno e occorre solo se estrae interi in un range)
[0] = 0,2
[1] = 0,5
[2] = 0,6
[3] = 1,0
[0] = 2
[1] = 5
[2] = 6
[3] = 10
ora tu fai in modo con rand che estragga interi tra uno e dieci 
(zero non ammesso in questa mappatura).
Ebbene, si tratta solo di trovare con una ricerca lineare qual'è 
il più piccolo indice dell'array il cui valore è maggiore o 
uguale al numero estratto.
Ad es. se estraggo 7, l'indice è 3 perché la cella [3] contiene 
il primo valore più grande di 7.
ciao
Soviet_Mario


 [3] = 0,4
[cut]
La soluzione che proponi e' simile a quella che avevo pensato io e che
ho provato a spiegare ma non ad implementare, solo che io mi ero 
convinto che fosse necessario ordinare i valori dell'array prima di 
sommarli nell'array "integrale".
Ho provato e sembra funzionare.
Saluti e grazie
Libra


ordinare in che senso ? Devi sommarli in ordine di indice 
crescente (o decrescente) senza saltare indici, quindi più che 
ordinarli in ordine di probabilità è sufficiente che sia 
rispettata la sequenza degli indici (e che gli indici dell'array 
integrale corrano parallelamente ai valori di integrazione, ma è 
ovvio e anche questo si codifica naturalmente con uan scansione 
iterativa, e per fare diversamente bisognerebbe complicare il 
codice artatamente).
L'array integrale è naturalmente già ordinato anche per valori 
comunque lo si implementi, in quanto l'integrale di una funzione 
non negativa è monotono (crescente e/o costante) per definizione 
(questo lo dico in generale per cautela, non conoscendoti, poi 
magari tu sei un matematico e ti fai due risate :-))
ciao
Soviet_Mario


 probabilità è sufficiente che sia rispettata la sequenza degli indici
Infatti, non so perche' ma mi ero convinto che dovessi ordinare l'array 
a[] per probabilita' crescenti, altrimenti il metodo non funzionava.
Invece ho fatto qualche prova e funziona come mi hai suggerito tu.
Grazie per l'aiuto.
Saluti
Libra