Попытка понять оптимизацию array_diff_uassoc

Question

Попытка понять оптимизацию array_diff_uassoc

Кажется, что массивы отсортированы перед сравнением друг с другом внутри array_diff_uassoc.

В чем выгода этого подхода?

Тестовый скрипт

function compare($a, $b)
{
echo("$a : $b\n");
return strcmp($a, $b);
}

$a = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
$b = array('v' => 1, 'w' => 2, 'x' => 3, 'y' => 4, 'z' => 5);
var_dump(array_diff_uassoc($a, $b, 'compare'));$a = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
$b = array('d' => 1, 'e' => 2, 'f' => 3, 'g' => 4, 'h' => 5);
var_dump(array_diff_uassoc($a, $b, 'compare'));$a = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
$b = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
var_dump(array_diff_uassoc($a, $b, 'compare'));

$a = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
$b = array('e' => 5, 'd' => 4, 'c' => 3, 'b' => 2, 'a' => 1);
var_dump(array_diff_uassoc($a, $b, 'compare'));

http://3v4l.org/DKgms#v526

Постскриптум похоже, что алгоритм сортировки изменился в php7.

5

arrays php php-7 sorting

Решение

Другие решения

теория

Сортировка позволяет сделать несколько ярлыков; например:

A      | B
-------+------
1,2,3  | 4,5,6

Каждый элемент A будет сравниваться только с B [0], потому что другие элементы, как известно, по крайней мере такие же большие.

Другой пример:

A      | B
-------+-------
4,5,6  | 1,2,6

В этом случае A [0] сравнивается со всеми элементами из B, но A [1] и A [2] сравниваются только с B [2].

Если какой-либо элемент A больше, чем все элементы в B, вы получите худшую производительность.

практика

Хотя вышесказанное хорошо работает для стандарта array_diff() или же array_udiff()после использования функции сравнения ключей она прибегнет к производительности O (n * m) из-за это изменение пытаясь исправить эта ошибка.

Вышеупомянутая ошибка описывает, как пользовательские функции сравнения ключей могут вызывать неожиданные результаты при использовании с массивами, которые имеют смешанные ключи (то есть числовые и строковые значения ключей). Я лично чувствую, что это должно быть решено с помощью документации, потому что вы получите такие же странные результаты с ksort(),

3

Источник

Accepted Answer

Алгоритм сортировки не изменился в PHP 7. Элементы просто передаются в другом порядке алгоритму сортировки для улучшения производительности.

Ну, выгода может быть в конечном итоге более быстрым исполнением. Вы действительно столкнулись с наихудшим случаем, когда оба массива имеют совершенно другие ключи.

В худшем случае сложность заключается в двойной сортировке массивов и последующем сравнении каждого ключа двух массивов. O(n*m + n * log(n) + m * log(m))

Наилучший случай — это двойная сортировка, а затем столько же сравнений, сколько есть элементов в меньшем массиве. O(min(m, n) + n * log(n) + m * log(m))

В случае совпадения вам не придется снова сравнивать весь массив, а только по ключу после сопоставления.

Но в текущей реализации сортировка просто избыточна. Я думаю, что реализация в php-src нуждается в некотором улучшении. Там нет прямой ошибки, но реализация просто плохо. Если вы понимаете некоторые C: http://lxr.php.net/xref/PHP_TRUNK/ext/standard/array.c#php_array_diff
(Обратите внимание, что эта функция вызывается через php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_ASSOC, DIFF_COMP_DATA_INTERNAL, DIFF_COMP_KEY_USER); от array_diff_uassoc)

4