PHP数组 - 删除重复项(时间复杂度)

Question

好的,这不是"如何获得所有唯一身份"或"如何从我的数组中删除重复项"的问题.这是一个关于时间复杂性的问题.

我认为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秒!

Answer 1

虽然我不能说原生array_unique函数,但我可以告诉你,你的朋友算法更快,因为:

1. 他使用单个foreach循环而不是双重for()循环.
2. Foreach循环往往比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():

• 首先,将创建一个数组的副本,这是一个具有线性特征的操作
• 然后,struct bucketindex将创建一个C数组,并将指向我们数组副本的指针放入这些存储桶 - 线性特性
• 届时,bucketindex-array将被分拣usign快速排序- ñ logñ平均
• 最后,排序的数组将被遍历并且重复的条目将从我们的数组副本中删除 - 这应该是线性的,假设我们的数组中的删除是一个恒定的时间操作

希望这可以帮助 ;)