Хорошо, это не вопрос "как получить все уникальные" или "Как удалить дубликаты из моего массива в 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
i, получилось следующее:
Тестирование (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?
Edit Я удалил счетчик ($ array) из обоих циклов и просто использовал переменную в верхней части функции, которая набрала 2 секунды на 100 000 элементов!