PHP Arrays - Supprimer les doublons (complexité temporelle)

https://stackoverflow.com/questions/478002

20-08-2019
|

Question

D'accord, ce n'est pas une question de & "comment obtenir tous les uniques &"; ou & "Comment supprimer les doublons de mon tableau en php &"; C’est une question de complexité temporelle.

J'ai pensé que le array_unique est un peu O (n ^ 2 - n) et voici ma mise en oeuvre:

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; 
}

Cependant, lorsque nous comparons cela avec le <=> j’obtiens le résultat suivant:

Test (array_unique2) ... L'opération a pris 0,52146291732788 s.

Test (array_unique) ... L'opération a pris 0,28323101997375 s.

Ce qui rend le array_unique deux fois plus rapide, ma question est: pourquoi (les deux avaient les mêmes données aléatoires)?

Et un de mes amis a écrit ce qui suit:

function array_unique2($a)
{
    $n = array();
    foreach ($a as $k=>$v)
        if (!in_array($v,$n))
            $n[$k]=$v;
    return $n;
}

qui est deux fois plus rapide que celui intégré en php.

Je voudrais savoir pourquoi?

Quelle est la complexité temporelle de array_unique et in_array?

Modifier J'ai enlevé le nombre ($ array) des deux boucles et juste utilisé une variable dans le haut de la fonction, qui a gagné 2 secondes sur 100 000 éléments!

La solution

Bien que je ne puisse pas parler de la fonction native array_unique, je peux vous dire que l'algorithme de vos amis est plus rapide car:

Il utilise une seule boucle foreach par opposition à votre double boucle for ().
Les boucles Foreach ont tendance à fonctionner plus rapidement que les boucles for PHP.
Il a utilisé une seule comparaison if (!) alors que vous utilisiez deux structures if ()
Le seul appel de fonction supplémentaire que votre ami a appelé est in_array alors que vous avez appelé count () deux fois.
Vous avez fait trois déclarations de variable que votre ami n'avait pas à ($ a, $ current_is_unique, $ current_index)

Bien qu'aucun de ces facteurs ne soit à lui seul énorme, je peux voir en quoi l'effet cumulatif ferait prendre votre algorithme plus longtemps que vos amis.

Autres conseils

La complexité temporelle de in_array() est O (n) . Pour voir cela, nous allons jeter un oeil à la page Code source PHP .

La fonction ext/standard/array.c est implémentée dans php_search_array(). Il ne fait qu’appeler zend_hash_move_forward_ex(), qui contient la boucle suivante:

while (zend_hash_get_current_data_ex(target_hash, (void **)&entry, &pos) == SUCCESS) {

    // checking the value...

    zend_hash_move_forward_ex(target_hash, &pos);
}

C'est de là que vient la caractéristique linéaire.

C’est la caractéristique générale de l’algorithme, car Zend/zend_hash.c a un comportement constant: en regardant array_unique(), nous voyons qu’il s’agit essentiellement de

*current = (*current)->pListNext;

En ce qui concerne la complexité temporelle de struct bucketindex:

Tout d'abord, une copie du tableau sera créée, ce qui correspond à une opération avec la caractéristique linéaire
puis, un tableau C de bucketindex sera créé et des pointeurs dans la copie de notre tableau sera mis en ces seaux - linear caractéristique à nouveau
alors, le log - tableau sera trié selon la méthode de tri rapide - n <=> n en moyenne
et enfin, le tableau trié sera piétiné et et entrées en double seront supprimées de la copie de notre gamme - ce qui devrait être linear à nouveau, en supposant que la suppression de notre tableau est une opération de constante de temps

J'espère que cela aide;)

Essayez cet algorithme. Il tire parti du fait que la recherche de clé est plus rapide que 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);
}

Gabriel's answer contient quelques points intéressants sur la raison pour laquelle la méthode de votre ami est supérieure à la vôtre. Intriguée par la conversation qui a suivi celle de Christoph réponse , j’ai décidé de faire mes propres tests.

De plus, j’ai essayé cela avec différentes longueurs de chaînes aléatoires et bien que les résultats aient été différents, l’ordre était le même. J'ai utilisé 6 caractères dans cet exemple pour des raisons de brièveté.

Notez que array_unique5 a en fait les mêmes clés que les clés natives 2 et 3, mais les affiche dans un ordre différent.

Résultats ...

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',  )

Et le code ...

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);
}

Résultats obtenus à l'aide de ensemble de données de Christoph à partir des commentaires:

$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

Les tableaux de PHP sont implémentés sous forme de tables de hachage, c’est-à-dire que leurs performances sont différentes de celles que vous attendez des tableaux "réels". Les paires clé-valeur d'un tableau sont en outre stockées dans une liste chaînée pour permettre une itération rapide.

Ceci explique la lenteur de votre implémentation par rapport à celle de vos amis: pour chaque index numérique, votre algorithme doit effectuer une recherche dans une table de hachage, alors qu'une boucle foreach() - va simplement parcourir la liste chaînée.

L'implémentation suivante utilise une table de hachage inversée et pourrait être la plus rapide de la foule (double retournement avec la permission de joe_mucchiello ):

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

Ceci ne fonctionnera que si les valeurs de $array sont des clés valides, à savoir des entiers ou des chaînes.

J'ai également réimplémenté votre algorithme en utilisant des boucles array_flip(). Désormais, il sera en réalité plus rapide que vos amis pour les petits ensembles de données, mais toujours plus lent que la solution via array_unique():

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;
}

Pour les grands ensembles de données, la version intégrée in_array() surperformera toutes les autres, à l’exception de la version à double retournement. De plus, la version utilisant array_unique3() de votre ami sera plus rapide que <=>.

Pour résumer: le code natif de la victoire!

Encore une autre version, qui devrait conserver les clés et leur classement:

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));
}

Il s’agit en fait de enobrev <=> - je n'ai pas vérifié ses implémentations aussi minutieusement que je l'aurais dû ...

PHP est plus lent à exécuter que le code machine brut (qui est probablement exécuté par array_unique).

Votre deuxième exemple de fonction (celui que votre ami a écrit) est intéressant. Je ne vois pas en quoi cela serait plus rapide que l’implémentation native, à moins que celle-ci ne supprime des éléments au lieu de créer un nouveau tableau.

J'admets que je ne comprends pas très bien le code natif, mais il semble copier tout le tableau, le trier, puis le parcourir en boucle pour supprimer les doublons. Dans ce cas, votre deuxième morceau de code est en réalité un algorithme plus efficace, car ajouter à la fin d'un tableau est moins coûteux que de le supprimer au milieu.

N'oubliez pas que les développeurs PHP avaient probablement une bonne raison de le faire comme ils le font. Quelqu'un veut-il leur demander?

La fonction PHP native array_unique est implémenté en C . Ainsi, il est plus rapide que PHP, il faut d’abord le traduire. De plus, & # 8217; PHP utilise un algorithme différent de celui que vous utilisez. D'après ce que je vois, PHP utilise d'abord Tri rapide pour trier les éléments, puis supprime les doublons. une course.

Pourquoi la mise en œuvre de son ami & # 8217; est-elle plus rapide que la sienne? Parce qu'il utilise davantage de fonctionnalités intégrées qui tentent de les recréer.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow