用于大型数组的php in_array的替代品,用于避免重复条目

Question

我需要从600k到2000k生成一个大的随机数列表,但列表不能有重复.

我目前的'实施'看起来像这样:

<?php
    header('Content-type: text/plain');
    $startTime = microtime(true);
    $used = array();
    for ($i=0; $i < 600000; ) { 
        $random = mt_rand();
        //if (!in_array($random, $used)) {
        $used[] = $random;
        $i++;
        //}
    }
    $endTime = microtime(true);
    $runningTime = $endTime - $startTime;
    echo 'Running Time: ' . $runningTime;
    //print_r($used);
?>

如果我保持in_array测试评论处理时间大约是1秒,那么mt_rand调用和used数组填充相对"便宜"但是当我取消注释in_array测试时,会发生坏事!(我只是等待 - 已经超过10分钟 - 脚本终止......)

所以我在重复检测方面或生成部分寻找替代方案(如何生成随机数而不存在重复的风险)

我对任何建议持开放态度.

Answer 1

对于快速/脏的解决方案,使用/检查数组键是否可以提高速度？

$used = array();
for ($i = 0; $i < 600000; ) { 
    $random = mt_rand();
    if (!isset($used[$random])) {
        $used[$random] = $random;
        $i++;
    }
}
$used = array_values($used);

Answer 2

in_array在最坏的情况下需要搜索整个数组,这意味着线性成本(O(n)).但是使用数组密钥作为密钥,成本是恒定的(O(1)),因为数组访问的成本总是不变的.