альтернативы 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)), поскольку затраты на доступ к массиву всегда постоянны.

Answer 3

Например, вместо этого вы можете сделать что-то подобное

$random = mt_rand();

$array = range($random, $random + 600000);

$array = shuffle($array);

Это создало бы массив, который сначала упорядочен, но затем он перетасовывает массив, поэтому значения будут случайными. Никаких столкновений! : D

Answer 4

Если вы все равно делаете циклы и если вам не нужно больше 600000, зачем вообще их проверять, почему бы просто не добавить $ i к $ random сделанный. не достаточно случайно?

for ($i = 0; $i < 600000; $i++)
{
    $yourArray[] = mt_rand() . $i; 
}

Кроме того, есть функция массива array_unique, которая удаляет повторяющиеся значения из массива.