PHP Arrays - удаление дубликатов (сложность по времени)

Question

Хорошо, это не вопрос "как получить все уникальные файлы" или "как удалить дубликаты из моего массива в php". Это вопрос о сложности времени.

Я понял, что array_unique в некоторой степени O (n ^ 2 - n), и вот моя реализация:

function array_unique2($array) 
{ 
    $to_return = array(); 
    $current_index = 0;

    for ( $i = 0 ; $i < count($array); $i++ ) 
    { 
        $current_is_unique = true; 

        for ( $a = $i+1; $a < count($array); $a++ ) 
        { 
            if ( $array[$i] == $array[$a] ) 
            { 
                $current_is_unique = false; 
                break; 
            } 
        } 
        if ( $current_is_unique ) 
        { 
            $to_return[$current_index] = $array[$i];
        } 

    } 

    return $to_return; 
}

Однако, сравнив это с array_unique, я получил следующий результат:

Тестирование (array_unique2) ... Операция заняла 0,52146291732788 с.

Тестирование (array_unique) ... Операция заняла 0,28323101997375 с.

Что делает array_unique в два раза быстрее, мой вопрос: почему (у обоих были одинаковые случайные данные)?

И мой друг написал следующее:

function array_unique2($a)
{
    $n = array();
    foreach ($a as $k=>$v)
        if (!in_array($v,$n))
            $n[$k]=$v;
    return $n;
}

, что в два раза быстрее встроенного в php.

Я хотел бы знать, почему?

Какова временная сложность array_unique и in_array?

Редактировать Я удалил счетчик ($ array) из обоих циклов и просто использовал переменную в верхней части функции, которая получила 2 секунды на 100 000 элементов!

Answer 1

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

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

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

Answer 2

Сложность времени 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():

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

Надеюсь, это поможет;)

Answer 3

Попробуйте этот алгоритм. Он использует тот факт, что поиск ключа быстрее, чем 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);
}

Answer 4

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

Кроме того, я пробовал это с разными длинами случайных строк и, хотя результаты были разными, порядок был тот же. Я использовал 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

Answer 5

Массивы 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 array_unique3() - я не проверял его реализации так тщательно, как следовало бы ...

Answer 6

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

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

Answer 7

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

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

Answer 8

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

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