好的,这不是"如何获得所有唯一身份"或"如何从我的数组中删除重复项"的问题.这是一个关于时间复杂性的问题.
我认为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 s.
测试(array_unique)...操作耗时0.28323101997375 s.
这使得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),只使用了函数顶部的变量,在100 000个元素上获得了2秒!
虽然我不能说原生array_unique函数,但我可以告诉你,你的朋友算法更快,因为:
他使用单个foreach循环而不是双重for()循环.
Foreach循环往往比PHP中的循环执行得更快.
当你使用两个if()结构时,他使用了单个if(!)比较
你的朋友调用的唯一附加函数是in_array,而你调用了count()两次.
你做了三个你的朋友不需要的变量声明($ 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()
:
首先,将创建一个数组的副本,这是一个具有线性特征的操作
然后,struct bucketindex
将创建一个C数组,并将指向我们数组副本的指针放入这些存储桶 - 线性特性
届时,bucketindex
-array将被分拣usign快速排序- ñ log
ñ平均
最后,排序的数组将被遍历并且重复的条目将从我们的数组副本中删除 - 这应该是线性的,假设我们的数组中的删除是一个恒定的时间操作
希望这可以帮助 ;)