好吧,这不是“如何获取所有唯一值”或“如何从我的 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 快了一倍,我的问题是,为什么(两者都有相同的随机数据)?
我的一个 friend 写道:
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 的时间复杂度是多少?
编辑 我从两个循环中删除了 count($array) 并且只在函数顶部使用了一个变量,它在 100 000 个元素上获得了 2 秒!
最佳答案
虽然我不能代表原生的 array_unique 函数,但我可以告诉你你 friend 的算法更快,因为:
- 他使用单个 foreach 循环而不是您的双 for() 循环。
- Foreach 循环往往比 PHP 中的 for 循环执行得更快。
- 他使用了一个 if(!) 比较,而你使用了两个 if() 结构
- 您 friend 调用的唯一附加函数是 in_array,而您调用了 count() 两次。
- 你做了三个你 friend 不需要的变量声明($a, $current_is_unique, $current_index)
虽然单独这些因素都不是很大,但我可以看到累积效应会使您的算法比您的 friend 花费更长的时间。
关于PHP 数组 - 删除重复项(时间复杂度),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/478002/