Estrarre numeri casuali

[pisoloso]

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

[PAOLO FRANCESCO Bertolotti]

Crei un secondo array vuoto e lo riempi con le righe che vengono prese a random per poi ciclare su questo ad ogni estrazione per verificare che non sia stato già usato.

Il giorno venerdì 23 agosto 2013 07:50:47 UTC+2, pisoloso ha scritto:
> 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

[Mau C]

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.

[Leonardo Serni]

On Fri, 23 Aug 2013 05:50:47 GMT, "pisoloso" <info.e...@email.it> wrote:

>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?

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.

[Mister]

"Leonardo Serni" <ser...@tin.it> ha scritto nel messaggio
news:6h0f19pdej2ep7q51...@L.Serni...

> On Fri, 23 Aug 2013 05:50:47 GMT, "pisoloso" <info.e...@email.it>
> wrote:
>
>
> 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 :-)
>

ciao

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

[Leonardo Serni]

On Fri, 23 Aug 2013 23:18:22 +0200, "Mister" <pippo@pippo-com> wrote:

>volendo generare una sequenza casuale "robusta", ad esempio per sistemi di
>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>.

[Marco Albarelli (fu Motosauro) @fisso]

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

[Leonardo Serni]

On Sat, 24 Aug 2013 00:24:23 +0200, Leonardo Serni <lse...@gmail.com> wrote:

>Una fonte di 'randomness' abbastanza cattiva, ma non performantissima, e'
>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.

[Mister]

"Leonardo Serni" <lse...@gmail.com> ha scritto nel messaggio
news:0ojh19ls944rmpots...@L.Serni...

> On Sat, 24 Aug 2013 00:24:23 +0200, Leonardo Serni <lse...@gmail.com>
> wrote:
>
>>Una fonte di 'randomness' abbastanza cattiva, ma non performantissima, e'
>>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?).

anche dalle mie parti :)

Comunque grazie degli interventi, mi hai dato un p� si spunti per
approfondire.