estrazione pesata
ViandanteOscuro
Ho un array dal quale devo estrarre n elementi a caso, e fin qui
niente di complicato.
Il problema e' che io vorrei che gli elementi dell'array con un valore
piu' alto abbiano piu' possibilità di essere estratti, mettere una
sorta di peso all'estrazione...
E' possibile? come posso fare?
Grazie mille!!
V
Leonardo Serni
wrote:
E' possibile, un sistema relativamente semplice e' quello di usare un
vettore "pesato"... pero' funziona *solo* se il numero degli elementi
dell'array e' molto superiore a quello degli elementi estratti.
Mi spiego: se hai un array (Alfa, Beta, Gamma) e chiedi di estrarre i
primi tre elementi, te li ritorna sempre tutti e tre.
Quindi la loro frequenza e' di 33%, 33%, 33% - *anche* se hai chiesto
una frequenza differente.
Idem se ne chiedi due (vederlo e' un po' meno intuitivo :-)).
Se ti pòle anda' bene...
Leonardo
--
What do you make, so fair and bright;
What do you build with sails for flight;
What do you weave with wool so white?
Umberto Salsi
Caro ViandanteOscuro,
potresti fare cosi'. Crei una funzione di distribuzione f(x) sull'intervallo
[0,1] normalizzata a 1 (cioe' l'integrale f(x)dx su [0,1] da' 1). Poi generi
dei punti casuali nel piano [0,1]x[0,max(f(x)] e prendi solo i punti (x,y)
tali che f(x)<=y. Poi dall'array selezioni l'elemento di posizione x*count(a).
Esempi di funzioni normalizzate:
f(x)=2.0*x
f(x)=0.333*x*x
...
Implementazione con quest'ultima funzione:
define("RND_K", 1.0 / (1.0 + getrandmax()));
/**
* Return random number in [0.0,1.0[
* @return float
*/
function rnd()
{
return RND_K * rand();
}
$a = array("a", "b", "c");
do {
$x = rnd();
$y = 0.333 * rnd();
} while( $y > 0.333 * $x * $x );
print $a[ (int)($x * count($a)) ];
Ciao,
___
/_|_\ Umberto Salsi
\/_\/ www.icosaedro.it
ViandanteOscuro
>
> define("RND_K", 1.0 / (1.0 + getrandmax()));
>
> /**
> * Return random number in [0.0,1.0[
> * @return float
> */
> function rnd()
> {
> return RND_K * rand();
>
> }
>
> $a = array("a", "b", "c");
>
> do {
> $x = rnd();
> $y = 0.333 * rnd();
>
> } while( $y > 0.333 * $x * $x );
>
> print $a[ (int)($x * count($a)) ];
>
ehm... non proprio, a me non serve pesare tutta l'estrazione, a me
serve che alcuni elementi dell'array abbiano probabilità maggiore di
essere estratti, in base a criteri scelti da me.
Ad esempio se ho un array cosi' composto:
ar1 (4, 6, 10, 8, 9) voglio che invece di avere probabilità 0.2 ogni
elemento, quelli sopra l'8 abbiano probabilità chesso'... .3 e il
resto diviso equamente tra gli altri elementi.
Umberto Salsi
> Esempi di funzioni normalizzate:
>
> f(x)=0.333*x*x
Errore di stampa: "0.333" leggasi invece "3" altrimenti non e' normalizzata.
Adesso che mi viene in mente, se non c'e' necessita' di seguire una
distribuzione specifica basta fare semplicemente il quadrato o il cubo di un
numero casuale tra 0 e 1, cosi' distribuisci i valori ottenuti di piu' verso
1 e meno verso 0. Piu' alta la potenza, piu' squilibrata e' la distribuzione:
$x = rnd();
print $a[ (int)($x*$x*$x * count($a)) ]
Umberto Salsi
> ehm... non proprio, a me non serve pesare tutta l'estrazione, a me
> serve che alcuni elementi dell'array abbiano probabilità maggiore di
> essere estratti, in base a criteri scelti da me.
>
> Ad esempio se ho un array cosi' composto:
>
> ar1 (4, 6, 10, 8, 9) voglio che invece di avere probabilit=E0 0.2 ogni
> elemento, quelli sopra l'8 abbiano probabilità chesso'... .3 e il
> resto diviso equamente tra gli altri elementi.
Il principio non cambia, solo che la distribuzione continua f() diventa
discreta $f[]:
$a = array("a", "b", "c");
$f = array(0.2, 0.3, 0.5); // ovviamente somma $f[] = 1.0
$n = count($a);
do {
$x = (int) ($n * rnd());
$y = rnd();
} while( $y > $f[$x] );
echo $a[$x];
Leonardo Serni
wrote:
>ehm... non proprio, a me non serve pesare tutta l'estrazione, a me
>serve che alcuni elementi dell'array abbiano probabilità maggiore di
>essere estratti, in base a criteri scelti da me.
>Ad esempio se ho un array cosi' composto:
>ar1 (4, 6, 10, 8, 9) voglio che invece di avere probabilità 0.2 ogni
>elemento, quelli sopra l'8 abbiano probabilità chesso'... .3 e il
>resto diviso equamente tra gli altri elementi.
Con i caveat del post precedente:
/*
In ingresso: un array con pesi relativi e il numero di
elementi desiderati.
In uscita: un array con, se possibile, le chiavi dell'
array $scelte.
Es: array('a' => 4, 'b' => 1), 1
dovrebbe ritornare o a o b, e a 4 volte piu' spesso di
b.
*/
function estrai_con_frequenza($scelte, $desiderati)
{
$estratti = array();
// Per ogni estrazione
while(!empty($scelte) && ((count($estratti)<$desiderati)))
{
// Un punto a caso equiprobabile su un'area
// variabile
$punto = rand(0, array_sum($scelte)-1);
// Determino a chi appartiene questo punto
$index = 0;
$values = array_values($scelte);
while($punto >= $values[$index])
$punto -= $values[$index++];
unset($values);
$keys = array_keys($scelte);
$key = $keys[$index];
// Aggiungo all'estrazione
$estratti[] = $key;
// Elimino dalle scelte
unset($scelte[$key]);
}
return $estratti;
}
Il risultato lo vedi da te:
<?php
$scelte = array(
'mela' => 15,
'pera' => 33,
'gatti' => 5,
'cani' => 11,
'cippa' => 7,
'lippa' => 40,
'dingo' => 2,
);
$volte = 10000;
$previste = array();
$base = 0;
$totali = count($scelte);
foreach($scelte as $cosa => $quanto)
$base += $quanto;
foreach($scelte as $cosa => $quanto)
$previste[$cosa] = number_format($quanto*100/$base, 2);
print '<table border="1" cellspacing="0" style="font-family:
Courier">';
for ($prove = 1; $prove <= count($scelte); $prove++)
{
$elementi = 0;
$ottenute = array_combine(array_keys($scelte),
array_fill(0, count($scelte), 0));
for ($i = 0; $i < $volte; $i++)
{
$got = estrai_con_frequenza($scelte, $prove);
foreach($got as $it)
$ottenute[$it]++;
$elementi += count($got);
}
$previsti = $prove * $volte;
print '<tr bgcolor="blue"><td colspan=5 style="color:
white">';
print "$volte estrazioni di $prove/$totali elementi
($elementi/$previsti valori)";
print "</td></tr>";
print "<tr><th>Cosa</th><th>Frequenza</th><th>Attese
%</th><th>Attesi</th><th>Ottenuti</th></tr>";
$norma = 0;
$errore = 0;
foreach($scelte as $cosa => $quanto)
{
$attass = (int)($previste[$cosa] * $elementi /
100 + 0.5);
print "<tr style=\"text-align: right\"><td
bgcolor=\"lightgray\" style=\"text-align:
left\">$cosa</td><td>$quanto</td>";
print
"<td>$previste[$cosa]</td><td>$attass</td><td>$ottenute[$cosa]</td></tr>";
$errore += ($attass - $ottenute[$cosa]) * ($attass
- $ottenute[$cosa]);
$norma += $attass*$attass;
}
$errore = number_format((100*$errore)/$norma, 2);
print "</tr>";
print "<tr><td> </td><td colspan=3>Scarto rispetto al
comportamento desiderato</td>";
print "<td style=\"text-align:
right\">$errore%</td></tr>";
}
print "</table>";
?>
~
~
iuz
> ViandanteOscuro <mas...@mponline.org> wrote:
>
>> ehm... non proprio, a me non serve pesare tutta l'estrazione, a me
>> serve che alcuni elementi dell'array abbiano probabilità maggiore di
>> essere estratti, in base a criteri scelti da me.
[..]
cerchiamo di non esagerare con troppa teoria ed implementazioni troppo
complesse..
non testato.. (il funzionamento si puo' intuire)
function lottery ($values, $frequencies)
{
$maxFrequency = array_sum($frequencies);
$randValue = rand(1, $maxFrequency);
for ($i = $limit = 0; $i < count($frequencies); $i++) {
$limit += $frequencies[$i];
if ($randValue <= $limit) {
return $values[$i];
}
}
}
probabilita' eque per tutti gli elementi..
$v = array(1, 2, 3);
$f = array(1, 1, 1);
echo lottery($v, $f)
probabilita' 25% 25% 50%..
$v = array(1, 2, 3);
$f = array(1, 1, 2);
echo lottery($v, $f)
che per convenienza puo' anche essere scritto..
$v = array(1, 2, 3);
$f = array(25, 25, 50);
echo lottery($v, $f)
mi sembra pratico veloce e semplice..
Ugo
e anche funzionale:
$i = 5000;
$val = array();
while ( $i-- )
{
$val[lottery($v, $f)]++;
}
print_r( $val );
direi che funziona bene (il piccolo margine d'errore è dato dalla funzione
rand che non è perfettamente equidistribuita - mt_rand non mi sembra che
migliori molto questo aspetto...)
Leonardo Serni
>non testato.. (il funzionamento si puo' intuire)
>function lottery ($values, $frequencies)
>{
> $maxFrequency = array_sum($frequencies);
> $randValue = rand(1, $maxFrequency);
> for ($i = $limit = 0; $i < count($frequencies); $i++) {
> $limit += $frequencies[$i];
> if ($randValue <= $limit) {
> return $values[$i];
> }
> }
>}
Pero' cosi' estrai un solo elemento; il problema era "estrarne n".
Per estrarne due, devi chiamare due volte la funzione... che potrebbe
anche ritornarti l'elemento gia' estratto. Sicche', a quel punto devi
eliminare gli elementi estratti dal pool dell'estrazione successiva e
vedi spuntare fuori i noti problemi di distribuzione...
Leonardo "Prima legge di Ginsberg: Non puoi vincere"
iuz
> On Sat, 08 Sep 2007 12:08:46 +0200, iuz <us...@host.network> wrote:
[..]
>
> Pero' cosi' estrai un solo elemento; il problema era "estrarne n".
questo non l'avevo capito..
> Per estrarne due, devi chiamare due volte la funzione... che potrebbe
> anche ritornarti l'elemento gia' estratto. Sicche', a quel punto devi
> eliminare gli elementi estratti dal pool dell'estrazione successiva e
> vedi spuntare fuori i noti problemi di distribuzione...
beh il codice comunque cambia "poco"..
non testato..
function lottery ($values, $freqs, $n)
{
// Calculate the max range passed to rand()
$maxFreq = array_sum($freqs);
// Extract $n n from $values without
// repeated elemets in the result
for ($extracted = array(); $n > 0; $n--) {
// Extract one element from the $values
// array according to the freqs given
$randValue = rand(1, $maxFreq);
for ($i = $limit = 0; $i < count($freqs); $i++) {
$limit += $freqs[$i];
if ($randValue <= $limit) {
$extracted[] = $values[$i];
}
}
// Calculate the max range for the next extraction and
// remove extracted element from input arrays
$maxFreq -= $freqs[$i];
array_splice(&$values, $i, 1);
array_splice(&$freqs, $i, 1);
}
return $extracted;
}
ma ti confesso che a questo punto preferirei di gran lunga spezzare il tutto
in 2 funzioni una che estrae e ritorna l'indice al valore estratto ed una
che elimina dagli array delgli elementi e delle frequenze il valore
estratto..
non testato..
function lottery ($values, $freqs)
{
$maxFreq = array_sum($freqs);
$randValue = rand(1, $maxFreq);
for ($i = $limit = 0; $i < count($freqs); $i++) {
$limit += $freqs[$i];
if ($randValue <= $limit) {
return $i;
}
}
}
function lotteryRemove (&$values, &$freqs, $i)
{
array_splice(&$values, $i, 1);
array_splice(&$freqs, $i, 1);
}
>
> Leonardo "Prima legge di Ginsberg: Non puoi vincere"
>
non posso vincere, non posso pareggiare e non posso neppure abbandonare.. ma
posso sempre scommettere sull'avversario :-)