Newsgroup: it.comp.www.php
Titolo: Estrarre numeri casuali

Ho la necessitï¿œ, data una lista di record, di estrarre un certo numero di 
numeri casuali e senza ripetizioni.
Esempio: tra i 100 record di una tabella devo estrarne 20.
 
Qualcuno ha giï¿œ affrontato questo problema?
 
Grazie per l'attenzione
 

 Grazie per l'attenzione
 


In SQL
 
SELECT * FROM tuaTabella ORDER BY rand() LIMIT 20
-- questo dovrebbe [untested] funzionare con MySQL
 
SELECT * FROM (
	SELECT *, dbms_random.random n FROM tuaTabella ORDER BY n
) WHERE ROWNUM <= 20
-- questo dovrebbe [untested] funzionare con Oracle
 
 
N.B.: Lasciare gli "*" fa schifo, ma per brevitï¿œ ho scritto cosï¿œ.
 
 
In PHP
 
shuffle($tuoarray)
e poi ne estrai i primi 20 record
 
 
M.

Qualcuno ha già affrontato questo problema?
 
Si', e non e' cosi' semplice.
 
Se hai pochi record nella tabella, SELECT * FROM table ORDER BY rand() LIMIT
20 funziona benone e puoi smettere di leggere :-D
 
Quando la cardinalita' della tabella sale sopra i 500-1000, ti conviene fare
in un altro modo (se vuoi le prestazioni sopra ogni cosa, ti conviene gia' a
partire da 50-100 elementi; ma implementare quanto segue scassa le balle, ed
anche quelle sono un costo).
 
Quale sara' questo modo, dipende com'e' fatta la tabella.
 
Per es., se hai degli ID numerici senza "buchi", puoi generare 20 ID fra 1 e
MAX(ID):
 
	while(count($ids) < 20) {
		$ids = array_unique($ids, array( getRandomId() ));
        }
 
 
Se hai dei buchi con distribuzione casuale, puoi fare una cosa un po' sporca
e generare 20*1.37*MAX(ID)/COUNT(table) ID fra 1 e MAX(ID), e poi fare
 
	SELECT * FROM table WHERE ID IN (...) LIMIT 20
 
che con fortissima probabilita' ti ritorna 20 numeri non ripetuti.
 
Ci sono vari altri sistemi. Se usi un iteratore, ed estrai un numero piccolo
di record rispetto alle dimensioni della tabella, potrebbe convenirti
 
	$id = mt_rand(1, $TableSize);
 
	SELECT * FROM table LIMIT $id, 1
 
e poi immagazzinare l'$id in sessione. Se generi un $id gia' estratto, basta
ripetere mt_rand. So a mente che se estrai 25 record da 365, la probabilita'
che tu debba rifarci almeno una volta e' circa il 50%.
 
Poi dipende anche da "quanto random" deve essere l'estrazione. Per vari usi,
una congruenza lineare rapida e schifida basta ed avanza. Non e' casuale, ma
non se ne accorge nessuno :-)
 
Leonardo
 
-- 
Were I Glenallan's Earl this tide, and were you Roland Cheyne,
My spur would be in my horse's side, the bridle upon his mane.
If they hae twenty thousand blades and we twice ten times ten,
Yet they hae but their tartan plaids, and we're mail-clad men.


 
ciao
 
volendo generare una sequenza casuale "robusta", ad esempio per sistemi di 
gioco, hai qualche consiglio da darmi, sempre rimanendo nell'ambito php?
 
 
 

gioco, hai qualche consiglio da darmi, sempre rimanendo nell'ambito php?
 
Bisogna che tu sia piu' preciso. Sequenza casuale di che cosa, e ottenuta
come?
 
Per sistemi di gioco, ti serve un sistema impredicibile: quindi eviterei,
ad esempio, l'uso di generatori come mt_rand(). E' costosissimo, pero' se
uno ha a disposizione poco piu' di 600 estrazioni consecutive e una bomba
di potenza di calcolo (o una scheda nVIDIA di buon livello :-) ), ti puo'
predire tutte le future estrazioni. mt_rand() va bene ma va "rinfrescato"
di tanto in tanto. In alternativa puoi usare mcrypt in modalita' CTR, con
l'accortezza di preparare i contatori in ingresso con pack() a blocchi, e
poi estrarli nello stesso modo (ci sono due scuole di pensiero. Questa e'
una. L'altra prevede di clonare il contatore fino a riempire il buffer di
AES, cioe' cifrare N volte lo stesso contatore anziche' N diversi).
 
Una fonte di 'randomness' abbastanza cattiva, ma non performantissima, e'
urandom (anche su Windows):
 
	$binary = mcrypt_create_iv(4, MCRYPT_DEV_URANDOM);
        $value  = unpack('Ni', $binary);
        $value  = $value['i'] & 0x7FFFFFFF;
 
...che ti ritorna un intero, fra 0 e 2^31-1. Se ti serve un valore su un
intervallo, NON fare "$min + $value % ( $max - $min )", che SEMBRA anche
funzionare, ma badaben badaben badaben, non funziona (funziona QUASI: e,
in alcuni casi, magari ti va anche bene... con numeri piu' piccoli, vedi
subito il trucco). Converti $value in float, dividi per 2^31-1, e quello
che risulta lo moltiplichi per ($max-$min) prima di sommare $min - c'e',
anche qui, un piccolo errore: ma e' sparpagliato meglio (thanks, IEEE) e
non saprei neanche da che parte cominciare per rilevarlo.
 
(Ah, visto che serve un float, verra' anche a voi la tentazione di usare
"fi" al posto di "Ni". E se avete fortuna, la macchina su cui lo fate e'
di quelle che vi mordono subito sul culo. Se avete sfiga, non lo e' - e,
siccome Murphy e' una sicurezza, lo sara' la macchina di produzione. Per
i sordidi dettagli, vedi sul manuale alla voce pack(), e sotto alla 'f':
"machine dependent size and representation". "Qui, funziona... la' no" -
e, quindi, noi siamo i programmatori che dicono 'Ni').
 
A proposito di casualita' e giochi, beh, anche l'implementazione ti puo'
fregare:
 
 
http://www.cigital.com/papers/download/developer_gambling.php
 
 
...e io conoscevo un sito che invece usava incautamente mt_rand() <g>.



Questa la stampo :D
Thx, a me è servito molte poche volte di implementare cose rand(), ma 
quelle volte mi avrebbe fatto comodo una spiegazione così
M
 
-- 
I fatti mi cosano

urandom (anche su Windows):
 
Scusate per la versione in fiorentinaccio. Dalle mie parti "cattivo" e' un
complimento :-) -- si intende che la fonte di randomness e' "valida" (poi,
voglio dire, se avesse fatto schifo, mica avrei messo il codice per usarla
sul serio, no?).
 
Quindi basta email per difendere urandom, per carita'.
 
Mentre invece il tapinaccio che mi scrive per proporre "MCRYPT_DEV_RANDOM"
(che pure esiste) vive pericolosamente.
 
Su Windows non c'e' problema - ma su Linux, PHP si attacca a /dev/random e
succhia.
 
Se qualche mariuolo se n'accorge e ha il modo di indurre il processo PHP a
usare quella routine suonando a festa... il risultato e' che la riserva di
entropia di /dev/random si svuota. E finche' non si riempie di nuovo tutti
i processi che provano a usarla SI FERMANO.
 
Oh, e fra quei processi, c'e' anche l'handshake di SSH. Per cui nel server
sotto attacco non ci entrate piu' (il timeout di sessione e' *troppo* piu'
corto), fino a 1-2 minuti dopo la fine dell'attacco... se finisce.
 
(Su un server, il pool di entropia si riempie piano... perche' sui desktop
c'e' il mouse e la tastiera che sono collegati a un sistema biologico :-),
pieno zipillo di entropia di qualita'. Sui server no [1]).
 
/dev/urandom prende "un po'" di entropia da /dev/random e la monta a neve,
e da un pugnello di entropia forte crea una montagna di entropia che, si',
e' piu' debole, ma sempre piu' che sufficiente perche' IN ASSENZA DI ALTRA
INFORMAZIONE un attaccante si ciucci le dita. Ed esaurire /dev/urandom non
e' operazione facile.
 
Pero', pero'... a volte quell'altra informazione C'E':
 
 
http://crypto.di.uoa.gr/CRYPTO.SEC/Randomness_Attacks_files/paper.pdf
 
 
...e, quando c'e', un attaccante puo' usarla.
 
Leonardo
 
[1] o quasi mai. Ci sono CPU con generatori di rumore quantistico, come il
    Core i5 e i7 di 3a e 4a gen. e lo Xeon E3. Non ricordo il VIA se tante
    volte ce l'avesse.


 sul serio, no?).
 
 
anche dalle mie parti :)
 
Comunque grazie degli interventi, mi hai dato un p� si spunti per 
approfondire.