note 126659 added to function.array-rand
| From: | Vitaly at main dot php dot net | Date: | Fri, 03 Dec 2021 15:06:19 +0000 |
| Subject: | note 126659 added to function.array-rand | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-217325@lists.php.net to get a copy of this message | ||
Generate random index in weights array.
Implementation of Vose's Alias Method.
<?php
class AliasMethod
{
protected $count;
protected $prob;
protected $alias;
public function __construct($weight)
{
$count = count($weight);
$sum = array_sum($weight);
$d = $count / $sum;
$small = [];
$large = [];
foreach ($weight as $i => & $w) {
if ( ($w *= $d) < 1)
$small[] = $i;
else
$large[] = $i;
}
unset($w);
$prob = [];
$alias = [];
while (!empty($small) AND !empty($large)) {
$l = array_pop($small);
$g = array_pop($large);
$prob[$l] = $weight[$l];
$alias[$l] = $g;
if ( ($weight[$g] += $weight[$l] - 1) < 1)
$small[] = $g;
else
$large[] = $g;
}
foreach ($large as $i)
$prob[$i] = 1;
foreach ($small as $i)
$prob[$i] = 1;
$this->prob = $prob;
$this->alias = $alias;
$this->count = $count;
}
public function next(): int
{
$i = mt_rand(0, $this->count - 1);
if (mt_rand() / mt_getrandmax() <= $this->prob[$i])
return $i;
else
return $this->alias[$i];
}
}
// Usage:
$weight = [1, 2, 1, 1, 100, 1, 1, 5, 1, 1];
$rnd = new AliasMethod($weight);
$results = array_fill(0, count($weight), 0);
for($i = 0; $i < 100000; ++$i) {
$results[$rnd->next()]++;
}
print_r($results);
/*
Array
(
[0] => 901
[1] => 1785
[2] => 899
[3] => 907
[4] => 87655
[5] => 867
[6] => 836
[7] => 4371
[8] => 910
[9] => 869
)
*/
----
Server IP: 45.112.84.4
Probable Submitter: 45.112.85.242 (proxied: 212.119.233.35)
----
Manual Page -- https://php.net/manual/en/function.array-rand.php
Edit -- https://main.php.net/note/edit/126659
Del: integrated -- https://main.php.net/note/delete/126659/integrated
Del: useless -- https://main.php.net/note/delete/126659/useless
Del: bad code -- https://main.php.net/note/delete/126659/bad+code
Del: spam -- https://main.php.net/note/delete/126659/spam
Del: non-english -- https://main.php.net/note/delete/126659/non-english
Del: in docs -- https://main.php.net/note/delete/126659/in+docs
Del: other reasons-- https://main.php.net/note/delete/126659
Reject -- https://main.php.net/note/reject/126659
Search -- https://main.php.net/manage/user-notes.php