PHP
乱択アルゴリズム

array_randやshuffleの乱択精度を改善しよう

More than 3 years have passed since last update.


mt_rand

PHPに精通している方はほぼ全員ご存じだと思いますが、PHPには乱数生成関数として rand の他に mt_rand というものもあります。

マニュアルを見る限り、後者の方が精度が良いようです。


mt_array_rand, mt_shuffle

array_randshuffle は内部で rand を使用しています。もし mt_rand を使用したい場合は、自分で関数を定義する必要があります。


実装例


mt_array_rand

function mt_array_rand(array $array, $num = 1) {

static $max;
if (!$max) {
$max = mt_getrandmax() + 1;
}
$num = (int)$num;
$count = count($array);
if ($num <= 0 || $count < $num) {
return null;
}
foreach ($array as $key => $_) {
if (!$num) {
break;
}
if (mt_rand() / $max < $num / $count) {
$retval[] = $key;
--$num;
}
--$count;
}
return !isset($retval[1]) ? $retval[0] : $retval;
}


mt_shuffle

function mt_shuffle(array &$array) {

$array = array_values($array);
for ($i = count($array) - 1; $i > 0; --$i) {
$j = mt_rand(0, $i);
$tmp = $array[$i];
$array[$i] = $array[$j];
$array[$j] = $tmp;
}
}


openssl_rand, openssl_array_rand, openssl_shuffle

暗号学的な安全性まで求めたい場合はこちらで。

追記: PHP7以降ではrandom_intが使用出来ます。自分で怪しい関数を実装する必要は無くなりました。


実装例


openssl_rand

function openssl_rand($min = 0, $max = PHP_INT_MAX) {

$min = (int)$min;
$max = (int)$max;
$range = $max - $min;
if ($range <= 0) {
return $min;
}
$log = log($range, 2);
$bytes = (int)($log / 8) + 1;
$bits = (int)$log + 1;
$filter = (int)(1 << $bits) - 1;
do {
$rand = hexdec(bin2hex(openssl_random_pseudo_bytes($bytes))) & $filter;
} while ($rand > $range);
return $min + $rand;
}


openssl_array_rand (openssl_randに依存)

function openssl_array_rand(array $array, $num = 1) {

$num = (int)$num;
$count = count($array);
if ($num <= 0 || $count < $num) {
return null;
}
foreach ($array as $key => $_) {
if (!$num) {
break;
}
if (openssl_rand() / (PHP_INT_MAX + 1) < $num / $count) {
$retval[] = $key;
--$num;
}
--$count;
}
return !isset($retval[1]) ? $retval[0] : $retval;
}


openssl_shuffle (openssl_randに依存)

function openssl_shuffle(array &$array) {

$array = array_values($array);
for ($i = count($array) - 1; $i > 0; --$i) {
$j = openssl_rand(0, $i);
$tmp = $array[$i];
$array[$i] = $array[$j];
$array[$j] = $tmp;
}
}


ベンチマーク

誰か性能いいマシン持ってる人試してください(丸投げ)