Массивы PHP – удаление дубликатов (временная сложность)

Хотя я не могу говорить о собственной функции array_unique, могу сказать, что алгоритм ваших друзей быстрее, потому что:

1. Он использует одиночный цикл foreach, а не ваш двойной цикл for ().
2. Циклы Foreach имеют тенденцию работать быстрее, чем для циклов в PHP.
3. Он использовал одно, если (!) Сравнение, когда вы использовали две структуры if ()
4. Единственная дополнительная функция, которую вызвал ваш друг, была in_array, тогда как вы дважды вызывали count ().
5. Вы сделали три объявления переменных, которые ваш друг не имел ($ a, $ current_is_unique, $ current_index)

Хотя ни один из этих факторов не является огромным, я могу видеть, где кумулятивный эффект заставит ваш алгоритм занять больше времени, чем ваши друзья.

Сложность времени in_array() равна O (n) . Чтобы увидеть это, мы рассмотрим исходный код PHP .

Функция in_array() реализована в ext/standard/array.c . Все, что он делает, это вызов php_search_array() , который содержит следующий цикл:

 while (zend_hash_get_current_data_ex(target_hash, (void **)&entry, &pos) == SUCCESS) { // checking the value... zend_hash_move_forward_ex(target_hash, &pos); } 

Отсюда и возникает линейная характеристика.

Это общая характеристика алгоритма, потому что zend_hash_move_forward_ex() имеет постоянное поведение: глядя на Zend/zend_hash.c , мы видим, что это в основном просто

 *current = (*current)->pListNext; 

Что касается временной сложности array_unique() :

• во-первых, будет создана копия массива, которая представляет собой операцию с линейной характеристикой
• то будет создан массив C struct bucketindex , и указатели в копию нашего массива будут помещены в эти ведра – снова линейная характеристика
• тогда, bucketindex -array будет отсортирован по сортировке по умолчанию – n log n в среднем
• и, наконец, отсортированный массив будет пройден, и дубликаты записей будут удалены из копии нашего массива – это должно быть линейным снова, предполагая, что удаление из нашего массива является постоянной операцией времени

Надеюсь это поможет 😉

Попробуйте этот алгоритм. Он использует тот факт, что поиск ключей быстрее, чем in_array ():

 function array_unique_mine($A) { $keys = Array(); $values = Array(); foreach ($A as $k => $v) { if (!array_key_exists($v, $values)) { $keys[] = $k; $values[$v] = $v; } } return array_combine($keys, $values); } 

В ответе Габриэля есть несколько замечаний о том, почему метод вашего друга побеждает. Заинтригованный разговором после ответа Кристофа , я решил провести собственные тесты.

Кроме того, я пробовал это с различной длиной случайных строк, и хотя результаты были разными, порядок был таким же. Для краткости я использовал 6 символов в этом примере.

Обратите внимание, что array_unique5 фактически имеет те же ключи, что и native, 2 и 3, но просто выводит в другом порядке.

Результаты…

 Testing 10000 array items of data over 1000 iterations: array_unique6: 1.7561039924622 array ( 9998 => 'b', 9992 => 'a', 9994 => 'f', 9997 => 'e', 9993 => 'c', 9999 => 'd', ) array_unique4: 1.8798060417175 array ( 0 => 'b', 1 => 'a', 2 => 'f', 3 => 'e', 4 => 'c', 5 => 'd', ) array_unique5: 7.5023629665375 array ( 10 => 'd', 0 => 'b', 3 => 'e', 2 => 'f', 9 => 'c', 1 => 'a', ) array_unique3: 11.356487989426 array ( 0 => 'b', 1 => 'a', 2 => 'f', 3 => 'e', 9 => 'c', 10 => 'd', ) array_unique: 22.535032987595 array ( 0 => 'b', 1 => 'a', 2 => 'f', 3 => 'e', 9 => 'c', 10 => 'd', ) array_unique2: 62.107122898102 array ( 0 => 'b', 1 => 'a', 2 => 'f', 3 => 'e', 9 => 'c', 10 => 'd', ) array_unique7: 71.557286024094 array ( 0 => 'b', 1 => 'a', 2 => 'f', 3 => 'e', 9 => 'c', 10 => 'd', ) 

И Код …

 set_time_limit(0); define('HASH_TIMES', 1000); header('Content-Type: text/plain'); $aInput = array(); for ($i = 0; $i < 10000; $i++) { array_push($aInput, chr(rand(97, 102))); } function array_unique2($a) { $n = array(); foreach ($a as $k=>$v) if (!in_array($v,$n)) $n[$k]=$v; return $n; } function array_unique3($aOriginal) { $aUnique = array(); foreach ($aOriginal as $sKey => $sValue) { if (!isset($aUnique[$sValue])) { $aUnique[$sValue] = $sKey; } } return array_flip($aUnique); } function array_unique4($aOriginal) { return array_keys(array_flip($aOriginal)); } function array_unique5($aOriginal) { return array_flip(array_flip(array_reverse($aOriginal, true))); } function array_unique6($aOriginal) { return array_flip(array_flip($aOriginal)); } function array_unique7($A) { $keys = Array(); $values = Array(); foreach ($A as $k => $v) { if (!array_key_exists($v, $values)) { $keys[] = $k; $values[$v] = $v; } } return array_combine($keys, $values); } function showResults($sMethod, $fTime, $aInput) { echo $sMethod . ":\t" . $fTime . "\t" . implode("\t", array_map('trim', explode("\n", var_export(call_user_func($sMethod, $aInput), 1)))) . "\n"; } echo 'Testing ' . (count($aInput)) . ' array items of data over ' . HASH_TIMES . " iterations:\n"; $fTime = microtime(1); for ($i = 0; $i < HASH_TIMES; $i++) array_unique($aInput); $aResults['array_unique'] = microtime(1) - $fTime; $fTime = microtime(1); for ($i = 0; $i < HASH_TIMES; $i++) array_unique2($aInput); $aResults['array_unique2'] = microtime(1) - $fTime; $fTime = microtime(1); for ($i = 0; $i < HASH_TIMES; $i++) array_unique3($aInput); $aResults['array_unique3'] = microtime(1) - $fTime; $fTime = microtime(1); for ($i = 0; $i < HASH_TIMES; $i++) array_unique4($aInput); $aResults['array_unique4'] = microtime(1) - $fTime; $fTime = microtime(1); for ($i = 0; $i < HASH_TIMES; $i++) array_unique5($aInput); $aResults['array_unique5'] = microtime(1) - $fTime; $fTime = microtime(1); for ($i = 0; $i < HASH_TIMES; $i++) array_unique6($aInput); $aResults['array_unique6'] = microtime(1) - $fTime; $fTime = microtime(1); for ($i = 0; $i < HASH_TIMES; $i++) array_unique7($aInput); $aResults['array_unique7'] = microtime(1) - $fTime; asort($aResults, SORT_NUMERIC); foreach ($aResults as $sMethod => $fTime) { showResults($sMethod, $fTime, $aInput); } 

Результаты с использованием данных Кристофа из комментариев:

 $aInput = array(); for($i = 0; $i < 1000; ++$i) $aInput[$i] = $i; for($i = 500; $i < 700; ++$i) $aInput[10000 + $i] = $i; Testing 1200 array items of data over 1000 iterations: array_unique6: 0.83235597610474 array_unique4: 0.84050011634827 array_unique5: 1.1954448223114 array_unique3: 2.2937450408936 array_unique7: 8.4412341117859 array_unique: 15.225166797638 array_unique2: 48.685120105743 

Массивы PHP реализованы как хеш-таблицы, т. Е. Их характеристики производительности отличаются от того, что вы ожидаете от «реальных» массивов. Пара ключей-значений массива дополнительно сохраняется в связанном списке, чтобы обеспечить быструю итерацию.

Это объясняет, почему ваша реализация настолько медленна по сравнению с вашим другом: для каждого числового индекса ваш алгоритм должен выполнять поиск хеш-таблицы, тогда как foreach() -loop будет просто перебирать связанный список.

В следующей реализации используется обратная хеш-таблица и, возможно, самая быстрая из них ( двунаправленная любезность joe_mucchiello ):

 function array_unique2($array) { return array_flip(array_flip($array)); } 

Это будет работать, только если значения $array являются действительными ключами, то есть целыми числами или строками.

Я также повторил ваш алгоритм с помощью foreach() -loops. Теперь это будет быстрее, чем ваш друг для небольших наборов данных, но все же медленнее, чем решение через array_flip() :

 function array_unique3($array) { $unique_array = array(); foreach($array as $current_key => $current_value) { foreach($unique_array as $old_value) { if($current_value === $old_value) continue 2; } $unique_array[$current_key] = $current_value; } return $unique_array; } 

Для больших наборов данных встроенная версия array_unique() будет превосходить все остальные, кроме двунаправленной. Кроме того, версия, использующая in_array() вашим другом, будет быстрее, чем array_unique3() .

Подводя итог: Родительский код для победы!

Еще одна версия, которая должна сохранять ключи и их порядок:

 function array_flop($array) { $flopped_array = array(); foreach($array as $key => $value) { if(!isset($flopped_array[$value])) $flopped_array[$value] = $key; } return $flopped_array; } function array_unique4($array) { return array_flip(array_flop($array)); } 

Это на самом деле enobrev 's array_unique3() – я не проверял его реализации так тщательно, как должен …

PHP работает медленнее, чем исходный машинный код (который, скорее всего, выполняется array_unique ).

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

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

Имейте в виду, что у разработчиков PHP, вероятно, была хорошая причина для этого, как они это делают. Кто-нибудь хочет спросить их?

array_unique функция PHP array_unique реализована на языке C. Таким образом, он быстрее PHP, который должен быть переведен первым. Более того, PHP использует другой алгоритм, чем вы. Как я вижу, PHP сначала использует Quick sort для сортировки элементов, а затем удаляет дубликаты за один проход.

Почему реализация его друга быстрее его? Потому что он использует больше встроенных функций, которые пытаются воссоздать их.