Distanza casuale tra due elementi

[superfox1]

Ciao,
sto cercando di risolvere il seguente problema: immaginate che abbia N elementi in ordine e che ne voglia selezionare (in media) solamente M (con M << N). Allora un modo classico è quello di scandire ciascun elemento ad uno ad uno e lanciare una moneta con p = M/N per vedere se selezionarlo o meno, però è inefficiente (lineare su N). Invece qual è il modo per ottenere una distanza casuale tra due elementi con la proprietà, in modo che alla fine ne prenda (all'incirca) M ? così da diventare lineare su M...

Ciao
- Dean

[superfox1]

cioè non so se sono stato spiegato )
proviamo così:
sia X vettore, una volta che seleziono X, c'è modo di avere un numero casuale j con cui selezionare X[j], senza dover scorrer gli elementi in mezzo tra i e j per verificare se selezionare anche loro?

Ciao
- Dean

[superfox1]

ragazzi ho risolto, anzi Vitter l'ha risolto... per chi ha lo stesso problema vedi articolo http://www.ittc.ku.edu/~jsv/Papers/Vit84.sampling.pdf

Ciao
- Dean