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

mt_rand

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

• PHP Manual - rand
• PHP Manual - mt_rand

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

mt_array_rand, mt_shuffle

array_rand や shuffle は内部で 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;
    }
}

ベンチマーク

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