note 119942 added to function.mt-rand
| From: | Vitaly | Date: | Sat, 24 Sep 2016 13:46:42 +0000 |
| Subject: | note 119942 added to function.mt-rand | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-206662@lists.php.net to get a copy of this message | ||
Generate random number by Array weights.
Implementation of Vose's Alias Method (http://www.keithschwarz.com/darts-dice-coins/)
<?php
function random_aliasMethod($weight, &$prob = array(), &$alias = array())
{
$count = count($weight);
if (empty($prob)) {
$small = array(); $large = array();
$sum = array_sum($weight);
foreach ($weight as $i => &$w)
($w *= $count / $sum) < 1 ? $small[] = $i : $large[] = $i;
unset($w);
while (!empty($small) AND !empty($large)) {
$l = array_pop($small);
$g = array_pop($large);
$prob[$l] = $weight[$l];
$alias[$l] = $g;
($weight[$g] += $weight[$l] - 1) < 1 ? $small[] = $g : $large[] = $g;
}
foreach ($large as $i)
$prob[$i] = 1;
foreach ($small as $i)
$prob[$i] = 1;
}
return mt_rand() / mt_getrandmax() <= $prob[$i = mt_rand(0, $count - 1)] ? $i : $alias[$i];
}
// Example:
$weight = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100);
$result = random_aliasMethod($weight);
// Distribution test:
$prob = array(); $alias = array(); // for cache
$results = array_fill(0, count($weight), 0);
for($i = 0; $i < 10000; ++$i) {
$results[random_aliasMethod($weight, $prob, $alias)]++;
}
print_r($results);
/*
[0] => 0
[1] => 70
[2] => 136
[3] => 190
[4] => 250
[5] => 322
[6] => 401
[7] => 444
[8] => 492
[9] => 596
[10] => 627
[11] => 6472
*/
----
Server IP: 72.52.91.14
Probable Submitter: 79.104.200.134
----
Manual Page -- http://php.net/manual/en/function.mt-rand.php
Edit -- https://master.php.net/note/edit/119942
Del: integrated -- https://master.php.net/note/delete/119942/integrated
Del: useless -- https://master.php.net/note/delete/119942/useless
Del: bad code -- https://master.php.net/note/delete/119942/bad+code
Del: spam -- https://master.php.net/note/delete/119942/spam
Del: non-english -- https://master.php.net/note/delete/119942/non-english
Del: in docs -- https://master.php.net/note/delete/119942/in+docs
Del: other reasons-- https://master.php.net/note/delete/119942
Reject -- https://master.php.net/note/reject/119942
Search -- https://master.php.net/manage/user-notes.php