PHP 数组 - 删除重复项（时间复杂度）

StackOverflow https://stackoverflow.com/questions/478002

  •  20-08-2019
  •  | 
  •  

题

好吧，这不是“如何获取所有唯一值”或“如何从 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 秒。

测试（数组唯一）...操作耗时 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 的时间复杂度是多少？

编辑我从两个循环中删除了 count($array)，只在函数顶部使用了一个变量，这在 100 000 个元素上节省了 2 秒！

有帮助吗？

解决方案

虽然我不能代表本机array_unique功能，我可以告诉你，你的朋友，算法是更快，因为：

  1. 他用一个单一的foreach循环而不是你的双为()循环。
  2. Foreach循环往往执行的速度比用于环PHP.
  3. 他用一个单一的if(!)比较的话，你用两个如果()结构
  4. 唯一的附加功能打电话给你的朋友是in_array而你叫count()两次。
  5. 你犯了三个可变的声明，你的朋友没有($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():

  • 第一，一份列将创建，这是一个操作 线性 特征
  • 然后，C系列 struct bucketindex 将建立和指针入我们的阵列是复制将投入这些水桶- 线性 特再次
  • 然后， bucketindex-列将按usign快速排序- n log n 平均
  • 最后，在排列将走，并重复的项目将被删除从我们的阵列是复制的，这应该是 线性 再次，假定，删除从我们的阵列是一个固定的时间操作

希望这可以帮助；)

尝试此算法。它利用这样的事实，关键查找比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);
}

加布里埃尔的 回答 关于为什么你朋友的方法胜过你的方法，有一些很好的观点。对下面的对话很感兴趣 克里斯托夫的 回答, ，我决定自己进行一些测试。

另外，我尝试使用不同长度的随机字符串，虽然结果不同，但顺序是相同的。为简洁起见，我在本示例中使用了 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

PHP中的数组实现为哈希表，即其性能特点是从你的“真实”的阵列预期的不同。阵列的键 - 值对被附加存储在一个链表，以允许快速迭代。

这解释了为什么比你的朋友你的实现是如此之慢：对于每一个数字指标，你的算法必须做一个哈希表查找，而foreach()循环只会遍历链表

。

下面的实现使用反向哈希表，并且可能是最快的人群（双翻转礼貌 joe_mucchiello ）：

function array_unique2($array) {
    return array_flip(array_flip($array));
}

此，如果$array的值是有效的键，即，整数或字符串才有效。

我也使用foreach()，循环重新实现你的算法。现在，它实际上是比你的朋友对小数据集不是通过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() - 我没有那样彻底，我应该检查他的实现...

PHP是慢于原始机器码（这是最有可能通过执行array_unique）来执行。

你的第二个例子功能（一个朋友写的）很有趣。我不明白怎么会比本机实现更快，除非本地一个是移除元素，而不是建立一个新的数组。

我承认我不明白的本地代码非常好，但似乎通过它删除重复整个数组，排序，然后循环复制。在这种情况下，你的代码第二片实际上是一种更有效的算法中，由于添加到阵列的端部是比从它的中间删除便宜。

请记住PHP开发人员可能有一个很好的理由这样做，他们做的方式。有谁要问他们？

原生 PHP 函数 array_unique 是 用C实现. 。因此它比必须先翻译的 PHP 更快。此外，PHP 使用的算法与您不同。据我所知，PHP 首先使用 快速排序 对元素进行排序，然后在一次运行中删除重复项。

为什么他朋友的实现速度比他自己的快？因为它使用了更多的内置功能来尝试重新创建它们。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top