Меню
Что нового?

Скорость сравнения массивов

Vivaldy

Новичок
Задача сравнить между собой два массива. В каждом массиве 50-100 тыс элементов.
Массивы такого плана:
$array1 = array(13, 21, 45, 984, 1289, 2390, 45689, 123983, 765432)
$array2 = array(13, 21, 984, 1289, 2390, 45689, 123983, 534234, 645342, 765432)

На выходе необходимы два массива:
- массив удаленных значений: $new_records = array(45)
- массив добавленных значений: $del_records = array(534234, 645342)

Значения в массивах упорядочены по возрастанию.

Изначально получился такой код:
Код: 
if (is_array($array2))
    foreach ($array2 as $elem)
        if (!is_array($array1) || !in_array($elem, $array1))
            $new_records[] = $elem;
   
if (is_array($array1))
    foreach ($array1 as $elem)
        if (!is_array($array2) || !in_array($elem, $array2))
            $del_records[] = $elem;
Однако время исполнения такого кода оказалось просто невероятно огромно!

Стал думать над оптимизацией, предположил что поиск вхождения элемента в массив будет работать дольше чем поиск подстроки в строке. Как результат - пришел к следующему решению:
Код: 
$str1 = '*'.implode('*', $array1).'*';
if (is_array($array2))
    foreach ($array2 as $elem)
        if (strpos($str1, '*'.$elem.'*') === false)
            $new_records[] = $elem;
   
$str2 = '*'.implode('*', $array2).'*';
if (is_array($array1))
    foreach ($array1 as $elem)
        if (strpos($str2, '*'.$elem.'*') === false)
            $del_records[] = $elem;
Выигрыш в скорости обработки получился, в среднем, в 8-9 раз. Однако это все равно слишком медленно.

Сейчас сижу думаю над идеей как то последовательно двигаться по обоим массивам разыскивая и накапливая отличия, но пока не смог придумать реализацию.

Может кто-то может подсказать как ускорить это решение.
 

MiksIr

miksir@home:~$
Раз сортировано, то просто. Берем по элементу из массивов, сравниваем. Если равны - берем следующие. Если не равны - берем элемент с меньшим значением, заносим его в ваш new_records/del_records в зависимости от того - из какого массива меньший, берем следующий элемент из этого же массива (у другого оставляем тот же элемент).
Как-то так...
 

AnrDaemon

Продвинутый новичок
Vivaldy, твоя проблема в том, что ты (в пределе) на каждый элемент одного массива просматриваешь все элементы второго массива. И так два раза.
Конечно, скорость будет невысокой.
 
WMix

WMix

герр M:)ller
Партнер клуба
мне почемуто кажется, что массивы были взяты из базы данных, если так, то алгоритм в корне не верный
 
hell0w0rd

hell0w0rd

Продвинутый новичок
Эм
PHP: 
❯ php -a
Interactive shell

php > $a = [1,2,3];
php > $b = [3,2,1];
php > $c = [1,2,3];
php > var_dump($a === $b);
bool(false)
php > var_dump($a === $c);
bool(true)
 
fixxxer

fixxxer

К.О.
Партнер клуба
MiksIr правильно сказал про сортированные. Но если нет - даже в тупо в лоб будет, наверное, достаточно эффективно, если представить как array(13 => true, 21 => true ... ) и проверять isset, это если не вспоминать про всякие специальные array_функции.

Впрочем, постановка задачи действительно намекает на то, что если там где-то рядом база данных то ты делаешь вообще все не там.
 
Фанат

Фанат

oncle terrible
Команда форума
ты просто длжен понимать, что за красивым фантиком in_array() скрывается полновесный цикл.
А теперь посчитай, сколько у тебя получается циклов.
 
флоппик

флоппик

promotor fidei
Команда форума
Партнер клуба
Старомодные жопы зарезали красивый оператор in в php7 :(
 

Vivaldy

Новичок
WMix написал(а):
мне почемуто кажется, что массивы были взяты из базы данных, если так, то алгоритм в корне не верный
Нажмите для раскрытия...
Не совсем - первый массив взят из базы данных, второй - я получаю запросом с другого сервера в виде JSON.
Пока данные приходили упорядоченные, но мне кажется что такое может быть не всегда, потому за сортировку второго массива я и переживаю. Miksir - предложил тот вариант который пытаюсь реализовать. Думаю что даже с сортировкой одного массива может быть еще быстрее. По результатам отпишусь.

Насчет базы данных - у меня один массив не в ней и добавлять сотню тысяч элементов - мне кажется будет долго.
 
hell0w0rd

hell0w0rd

Продвинутый новичок
Vivaldy, да какой ты нафиг вариант пытаешься реализовать? У тебя два отсортированных массива, все уже сделали за тебя и на сях.
PHP: 
<?php

$array1 = array(13, 21, 45, 984, 1289, 2390, 45689, 123983, 765432);
$array2 = array(13, 21, 984, 1289, 2390, 45689, 123983, 534234, 645342, 765432);

var_dump($array1 === $array2);
var_dump(array_diff($array1, $array2));
var_dump(array_diff($array2, $array1));
 
Redjik

Redjik

Джедай-мастер
hell0w0rd написал(а):
Vivaldy, да какой ты нафиг вариант пытаешься реализовать? У тебя два отсортированных массива, все уже сделали за тебя и на сях.
PHP: 
<?php

$array1 = array(13, 21, 45, 984, 1289, 2390, 45689, 123983, 765432);
$array2 = array(13, 21, 984, 1289, 2390, 45689, 123983, 534234, 645342, 765432);

var_dump($array1 === $array2);
var_dump(array_diff($array1, $array2));
var_dump(array_diff($array2, $array1));
Нажмите для раскрытия...
там в общем случае линейное время исполнения? лень исходники ради этого ковырять =)
 
hell0w0rd

hell0w0rd

Продвинутый новичок
Redjik написал(а):
там в общем случае линейное время исполнения? лень исходники ради этого ковырять =)
Нажмите для раскрытия...
мне тоже лень:)
PHP: 
$array1 = [];
$array2 = [];

for ($i = 0; $i < 100000; $i++) {
    $array1[] = $i;
    $array2[] = $i;
}

for ($i = 0; $i < 100000; $i++) {
    $array2[] = rand();
}

sort($array2);

$start = microtime(true);

array_diff($array1, $array2);
array_diff($array2, $array1);

var_dump(microtime(true) - $start);
100000 - double(3.7954561710358)
50000 - double(1.5283269882202)
 

Vivaldy

Новичок
hell0w0rd написал(а):
Vivaldy, да какой ты нафиг вариант пытаешься реализовать? У тебя два отсортированных массива, все уже сделали за тебя и на сях.
PHP: 
<?php

$array1 = array(13, 21, 45, 984, 1289, 2390, 45689, 123983, 765432);
$array2 = array(13, 21, 984, 1289, 2390, 45689, 123983, 534234, 645342, 765432);

var_dump($array1 === $array2);
var_dump(array_diff($array1, $array2));
var_dump(array_diff($array2, $array1));
Нажмите для раскрытия...
Спасибо - вот что значит ночь и усталость (((((( убрел в дебри ((((((
 

MiksIr

miksir@home:~$
hell0w0rd написал(а):
Vivaldy, да какой ты нафиг вариант пытаешься реализовать? У тебя два отсортированных массива, все уже сделали за тебя и на сях.
Нажмите для раскрытия...
Если бы на "сях", а то "ся" там формально. Обращение к элементам массива все-равно через абстракции идет ;) так что...
PHP: 
<?php
$array1 = [];
$array2 = [];

for ($i = 0; $i < 100000; $i++) {
    $array2[] = rand(1,10000000);
    $array1[] = rand(1,10000000);
}

$array1 = array_unique($array1, SORT_NUMERIC);
$array2 = array_unique($array2, SORT_NUMERIC);

$start = microtime(true);

$t1 = array_diff($array1, $array2);
$t2 = array_diff($array2, $array1);

var_dump(microtime(true) - $start);
var_dump(count($t1));
var_dump(count($t2));

$t1 = [];
$t2 = [];

$start = microtime(true);

sort($array2, SORT_NUMERIC);
sort($array1, SORT_NUMERIC);
$max1 = max($array1);
$max2 = max($array2);
$max = max($max1, $max2)+1;
$c1 = count($array1);
$c2 = count($array2);

for($a = 0, $b = 0; $a < $c1 || $b < $c2;) {
  $x = isset($array1[$a]) ? $array1[$a] : $max;
  $y = isset($array2[$b]) ? $array2[$b] : $max;
  if ($x === $y) {
      $a ++; $b ++;
  } elseif ($x < $y) {
      $t1[] = $x;
      $a ++;
  } else {
      $t2[] = $y;
      $b ++;
  }
}
Нажмите для раскрытия...
Дает
float(2.5227448940277)
int(98464)
int(98460)
float(0.511234998703)
int(98463)
int(98460)

Это даже не в два раза из-за двух проходов. И это как бы не самый оптимальный код еще ;)

Кстати, почему-то array_diff на сортированных массивах работает медленнее, чем на не сортированных.
 
Последнее редактирование:
antson

antson

Новичок
Партнер клуба
https://php.net/manual/en/function.next.php может в этом направлении посмотреть.
массивы должны быть оба отсортированными
а и б текущие элементы массивов
в цикле пока а и б не примут логическое значение ложь
если равны, то сдвинуть оба
если а меньше б , то а удаленный элемент , взять следующее а
иначе б новый , б = следущий
конец цикла
 
Войдите или зарегистрируйтесь для ответа.
Сверху