Liste des fonctions Big-O for PHP

Question

Après avoir utilisé PHP pendant un certain temps maintenant, j'ai remarqué que toutes les fonctions intégrées à PHP ne sont pas aussi rapides que prévu. Considérez les deux implémentations possibles ci-dessous d'une fonction qui détermine si un nombre est premier en utilisant un tableau de nombres premiers mis en cache.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $array_of_number => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $array_of_number => $number ) {
    $result_array[$number] = array_key_exists( $number, $large_prime_array );
}

Ceci est dû au fait que in_array est implémenté avec une recherche linéaire O(n) qui ralentira linéairement lorsque $prime_array se développe. Là où le array_key_exists est implémentée avec une recherche de hachage O(1) qui ne ralentira pas, sauf si la table de hachage est extrêmement remplie (dans ce cas, c'est seulement O(n)).

Jusqu'à présent, j'ai dû découvrir les grands principes par essai et erreur, et occasionnellement en regardant le code source . Maintenant pour la question...

Existe-t-il une liste des temps théoriques (ou pratiques) de grand O pour toutes* les fonctions intégrées de PHP ?

*ou du moins ceux qui sont intéressants

Par exemple, il est très difficile de prédire ce que sera le grand O des fonctions listées car leur implémentation possible dépend de structures de données inconnues du noyau de PHP : array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace (avec des tableaux en entrée), etc.

Answer 1

Comme personne ne semble l'avoir fait auparavant, j'ai pensé que ce serait une bonne idée de l'avoir comme référence quelque part. J'ai cherché à caractériser l'architecture de l'ordinateur par le biais d'un benchmark ou d'un code-skimming. array_* fonctions. J'ai essayé de placer les Big-O les plus intéressants en tête de liste. Cette liste n'est pas complète.

Note : Tous les Big-O ont été calculés en supposant qu'une consultation de hachage est O(1) même si c'est en réalité O(n). Le coefficient de n est si faible que la surcharge en mémoire vive liée au stockage d'un tableau suffisamment grand vous ferait souffrir avant que les caractéristiques du Big-O de la recherche ne commencent à prendre effet. Par exemple, la différence entre un appel à array_key_exists à N=1 et N=1.000.000 est une augmentation de temps de ~50%.

Points intéressants :

1. isset / array_key_exists est beaucoup plus rapide que in_array et array_search
2. + (union) est un peu plus rapide que array_merge (et il est plus beau). Mais le fonctionnement est différent, alors gardez cela à l'esprit.
3. shuffle est sur le même palier Big-O que array_rand
4. array_pop / array_push est plus rapide que array_shift / array_unshift en raison de la pénalité de réindexation

Recherches :

array_key_exists O(n) mais vraiment proche de O(1) - c'est à cause de la scrutation linéaire dans les collisions, mais comme la chance de collisions est très petite, le coefficient est aussi très petit. Je trouve que vous traitez les recherches de hachage comme O(1) pour donner un big-O plus réaliste. Par exemple, la différence entre N=1000 et N=100000 n'est qu'un ralentissement d'environ 50%.

isset( $array[$index] ) O(n) mais très proche de O(1) - il utilise la même recherche que array_key_exists. Puisqu'il s'agit d'une construction du langage, la recherche sera mise en cache si la clé est codée en dur, ce qui permet d'accélérer les cas où la même clé est utilisée de manière répétée.

in_array O(n) - c'est parce qu'il effectue une recherche linéaire dans le tableau jusqu'à ce qu'il trouve la valeur.

array_search O(n) - il utilise la même fonction centrale que in_array mais renvoie une valeur.

Fonctions de file d'attente :

array_push O(∑ var_i, pour tout i)

array_pop O(1)

array_shift O(n) - il doit réindexer toutes les clés

array_unshift O(n + ∑ var_i, pour tous les i) - il faut réindexer toutes les clés.

Intersection, union, soustraction de tableaux :

array_intersect_key si intersection 100% faire O(Max(param_i_size)*∑param_i_count, pour tous les i), si intersection 0% faire O(∑param_i_size, pour tous les i)

array_intersect si intersection 100% faire O(n^2*∑param_i_count, pour tout i), si intersection 0% faire O(n^2)

array_intersect_assoc si intersection 100% faire O(Max(param_i_size)*∑param_i_count, pour tous les i), si intersection 0% faire O(∑param_i_size, pour tous les i)

array_diff O(π param_i_size, pour tout i) - C'est le produit de tous les param_size

array_diff_key O(∑ param_i_size, pour i != 1) - c'est parce que nous n'avons pas besoin d'itérer sur le premier tableau.

array_merge O( ∑ array_i, i != 1 ) - n'a pas besoin d'itérer sur le premier tableau.

+ (union) O(n), où n est la taille du second tableau (c'est-à-dire tableau_premier + tableau_second) - moins de surcharge que array_merge puisqu'il n'a pas à renuméroter.

array_replace O( ∑ array_i, pour tous les i )

Random :

shuffle O(n)

array_rand O(n) - Nécessite un sondage linéaire.

Big-O évident :

array_fill O(n)

array_fill_keys O(n)

range O(n)

array_splice O(décalage + longueur)

array_slice O(offset + longueur) ou O(n) si longueur = NULL

array_keys O(n)

array_values O(n)

array_reverse O(n)

array_pad O(taille_du_papier)

array_flip O(n)

array_sum O(n)

array_product O(n)

array_reduce O(n)

array_filter O(n)

array_map O(n)

array_chunk O(n)

array_combine O(n)

Je tiens à remercier Eureqa pour avoir facilité la recherche du Big-O des fonctions. C'est un incroyable gratuit qui peut trouver la meilleure fonction d'ajustement pour des données arbitraires.

EDIT :

Pour ceux qui doutent que les recherches dans les tableaux PHP sont O(N) J'ai écrit un benchmark pour tester cela (ils sont toujours efficaces). O(1) pour les valeurs les plus réalistes).

$tests = 1000000;
$max = 5000001;

for( $i = 1; $i <= $max; $i += 10000 ) {
    //create lookup array
    $array = array_fill( 0, $i, NULL );

    //build test indexes
    $test_indexes = array();
    for( $j = 0; $j < $tests; $j++ ) {
        $test_indexes[] = rand( 0, $i-1 );
    }

    //benchmark array lookups
    $start = microtime( TRUE );
    foreach( $test_indexes as $test_index ) {
        $value = $array[ $test_index ];
        unset( $value );
    }
    $stop = microtime( TRUE );
    unset( $array, $test_indexes, $test_index );

    printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
    unset( $stop, $start );
}

Answer 2

L'explication pour le cas que vous décrivez spécifiquement est que les tableaux associatifs sont implémentés comme des tables de hachage - donc la recherche par clé (et par conséquent, la recherche par clé), array_key_exists ) est O(1). Cependant, les tableaux ne sont pas indexés par valeur, donc la seule façon dans le cas général de découvrir si une valeur existe dans le tableau est une recherche linéaire. Il n'y a pas de surprise.

Je ne pense pas qu'il existe une documentation spécifique et complète sur la complexité algorithmique des méthodes PHP. Cependant, si c'est un problème suffisamment important pour justifier cet effort, vous pouvez toujours regarder dans le code source .

Answer 3

Vous voulez presque toujours utiliser isset au lieu de array_key_exists . Je n'ai pas regardé les internes, mais je suis presque sûr que array_key_exists est O(N) car il itère sur chaque clé du tableau, alors que isset essaie d'accéder à l'élément en utilisant le même algorithme de hachage que celui utilisé lorsque vous accédez à un index de tableau. Cela devrait être O(1).

Voici un "piège" auquel il faut faire attention :

$search_array = array('first' => null, 'second' => 4);

// returns false
isset($search_array['first']);

// returns true
array_key_exists('first', $search_array);

---

J'étais curieux, alors j'ai analysé la différence :

<?php

$bigArray = range(1,100000);

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    isset($bigArray[50000]);
}

echo 'is_set:', microtime(true) - $start, ' seconds', '<br>';

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    array_key_exists(50000, $bigArray);
}

echo 'array_key_exists:', microtime(true) - $start, ' seconds';
?>

is_set: 0,132308959961 seconde
array_key_exists: 2,33202195168 secondes

Bien sûr, cela ne montre pas la complexité temporelle, mais cela montre comment les deux fonctions se comparent l'une à l'autre.

Pour tester la complexité temporelle, comparez le temps nécessaire à l'exécution d'une de ces fonctions sur la première et la dernière touche.