Блог

У меня есть следующий простой код для проверки на коллизию с первичным ключом, который я создаю:

 $machine_ids = array();

for($i = 0; $i < 100000; $i  ) {
    //Generate machine id returns a 15 character alphanumeric string
    $mid = Functions::generate_machine_id();

    if(in_array($mid, $machine_ids)) {
        die("Collision!");
    } else {
        $machine_ids[] = $mid;  
    }
}

die("Success!");
  

Есть идеи, почему на выполнение этого уходит много минут? В любом случае, чтобы ускорить это?

 for($i = 0; $i < 100000; $i  ) 
{
  //Generate machine id returns a 15 character alphanumeric string
  $mid = Functions::generate_machine_id();
  if (isset($machine_ids[$mid]))
  {
    die("Collision!");
  }
  $machine_ids[$mid] = true;
}
  

Для этого используйте $mid в качестве ключей и фиктивное значение в качестве значения. В частности, вместо

 if(in_array($mid, $machine_ids)) {
    die("Collision!");
} else {
    $machine_ids[] = $mid;  
}
  

используйте

 if(isset($machine_ids[$mid])) {
    die("Collision!");
} else {
    $machine_ids[$mid] = 1;  
}
  

В конце вы можете извлечь массив, который вы изначально хотели использовать array_keys($machine_ids) .

Это должно быть намного быстрее. Если он все еще медленный, значит, ваш Functions::generate_machine_id() медленный.

ОТРЕДАКТИРОВАНО, чтобы добавить isset согласно комментариям.

Проверка принадлежности к массиву — это операция O (n), поскольку вам приходится сравнивать значение с каждым элементом в массиве. После того, как вы добавляете целую кучу материала в массив, естественно, он становится медленнее.

Если вам нужно выполнить целую кучу тестов на членство, как в данном случае, вам следует использовать другую структуру данных, которая поддерживает O (1) тестов на членство, таких как хэш.

Реорганизуйте свой код так, чтобы он использовал связанный массив для хранения идентификаторов компьютеров и использования isset для проверки

 if( isset($machine_id[$mid]) ) die("Collision");

$machine_ids[$mid] = $mid;
  

Использование isset должно быть быстрее

Если вам нужна максимальная производительность в вашем случае, вам нужно сохранить ваши данные в виде ключа массива и использовать вместо этого isset or array_key_exists (поскольку php > = 7.4 array_key_exists теперь так же быстр, как isset ) in_array .

Внимание. Верно, что isset в хэш-карте выполняется быстрее, чем поиск значения в массиве (in_array), но имейте в виду, что преобразование массива значений [«foo», «bar», «baz»] в хэш-карту [«foo» => true, «bar» => true, «baz» => true] требует затрат памяти (а также потенциального построения хэш-карты, в зависимости от того, как и когда ты делаешь это). Как и во всем остальном, вам придется взвесить все «за» и «против» в каждом конкретном случае, чтобы определить, подходит ли хэш-карта или массив (список) значений лучше всего для ваших нужд. Это не специфично для PHP, а скорее относится к общему проблемному пространству информатики.

И некоторые тесты производительности от https://gist.github.com/alcaeus/536156663fac96744eba77b3e133e50a

 <?php declare(strict_types = 1);

function testPerformance($name, Closure $closure, $runs = 1000000)
{
    $start = microtime(true);
    for (; $runs > 0; $runs--)
    {
        $closure();
    }
    $end = microtime(true);

    printf("Function call %s took %.5f secondsn", $name, $end - $start);
}

$items = [1111111];
for ($i = 0; $i < 100000; $i  ) {
    $items[] = rand(0, 1000000);
}
$items = array_unique($items);
shuffle($items);

$assocItems = array_combine($items, array_fill(0, count($items), true));

$in_array = function () use ($items) {
    in_array(1111111, $items);
};

$isset = function () use ($assocItems) {
    isset($items[1111111]);
};

$array_key_exists = function () use ($assocItems) {
    array_key_exists(1111111, $assocItems);
};

testPerformance('in_array', $in_array, 100000);
testPerformance('isset', $isset, 100000);
testPerformance('array_key_exists', $array_key_exists, 100000);
  

Вывод:

 Function call in_array took 5.01030 seconds
Function call isset took 0.00627 seconds
Function call array_key_exists took 0.00620 seconds