Liste des Grands-O pour les fonctions PHP

Après l'utilisation de PHP pour un certain temps maintenant, j'ai remarqué que pas intégré toutes les fonctions PHP sont aussi rapide que prévue. Tenir compte de ces deux implémentations possibles d'une fonction qui détecte si un nombre est premier à l'aide d'un cache de tableau de nombres premiers.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $prime_array => $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( $prime_array => $number ) {
    $result_array[$number] = array_key_exists( $number, $large_prime_array );
}

C'est parce que in_array est mis en œuvre avec une recherche linéaire O(n) qui de façon linéaire ralentir $prime_array grandit. Où la array_key_exists fonction est implémentée avec une valeur de hachage de recherche O(1), qui ne sera pas ralentir à moins que la table de hachage devient extrêmement peuplée (dans ce cas, c'est seulement O(n)).

Jusqu'à présent, j'ai eu à découvrir le big-O par essai et erreur, et parfois en regardant le code source. Maintenant, pour la question...

S'il existe une liste de la partie théorique (et pratique) big O fois pour toutes* intégré dans les fonctions de PHP?

*ou au moins l'intéressantes

Par exemple, je trouve qu'il est très difficile de prédire le grand O de fonctions énumérées à cause de la possible mise en œuvre dépend de l'inconnu structures de données de base de PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace (avec un tableau en entrée), etc.

Totalement hors sujet, mais, 1 n'est pas premier.
Bon appel de Jason Punyon
Les tableaux en PHP sont les tables de hashage. Cela devrait vous dire tout ce que vous devez savoir. La recherche d'une clé dans une table de hachage est O(1). Recherche d'une valeur est O(n) -- ce que vous ne pouvez pas les battre sur un des ménagères de jeu. La plupart des fonctions que vous êtes curieux de savoir sont probablement O(n). Bien sûr, si vous voulez vraiment savoir, vous pouvez lire la source: cvs.php.net/viewvc.cgi/php-src/ext/standard/...
Pour l'enregistrement, la manière la plus rapide de mise en œuvre de ce que vous essayez de le faire serait de (au lieu d'utiliser la valeur NULL pour vos valeurs) utilisation true puis test de présence à l'aide d' isset($large_prime_array[$number]). Si je me souviens bien, c'est dans l'ordre de l'être des centaines de fois plus rapide que la in_array fonction.
mattbasta; si ce que vous dites est vrai, alors j'ai juste appris la chose la plus cool que j'ai appris toute la semaine.
ne serait-il pas toujours a la même big-O, mais simplement un plus petit coefficient?
Pas vraiment sûr, mais je l'ai utilisé et c'est FOU rapide.
Selon mes tests, la seule raison que isset est plus rapide, parce que c'est une structure du langage, et il y a un peu plus de la tête pour array_key_exists. Cette surcharge de travail, selon mon test pastebin.com/E9WtuzPb est que d'environ 50% (différence entre 0.0000006 et 0.0000004). Je crois que la raison isset peuvent être des ordres de grandeur plus rapide est parce qu'il cache recherches lorsque la clé est codée en dur, parce que c'est une construction du langage. Je pense que je vais encore le bâton avec array_key_exists car il n'a pas la valeur NULL gotcha.
Le Big O la notation n'est pas une question de vitesse. C'est à propos de la limitation de comportement.
Je ne suis pas le comparer à array_key_exists, je suis en comparant à in_array. in_array itération de chaque élément d'un tableau et compare la valeur de l'aiguille qui vous transmettez. Si vous retournez les valeurs de la clé (et il suffit de remplacer chacune des valeurs avec une valeur factice comme true, à l'aide de isset est beaucoup de beaucoup de fois plus rapide. C'est parce que les clés d'un tableau sont indexés par PHP (comme une table de hachage). Par conséquent, la recherche d'un tableau de cette manière peut avoir une amélioration significative de la vitesse.
Intéressant! Ainsi, une conversion rapide à utiliser la 2ème, plus rapide, est d'utiliser $prime_array = array_fill_keys( $prime_array, null ) . Ceci permet de clés dans les valeurs et maintenant, nous pouvons utiliser la fonction isset() à la place de in_array(). À partir de stackoverflow.com/questions/10641865/...
$array_of_number n'est pas défini ??

InformationsquelleAutor Kendall Hopkins | 2010-03-18

607

Car il ne semble pas comme quelqu'un l'a fait avant je pensais que ça serait une bonne idée de l'avoir pour référence quelque part. J'ai traversé et soit par référence ou code-écrémage pour caractériser la array_* fonctions. J'ai essayé de mettre le plus intéressant Big-O près du sommet. Cette liste n'est pas complète.

Note: Tous les Big-O lorsqu'il est calculé en supposant une valeur de hachage de recherche est O(1) même si c'est vraiment O(n). Le coefficient de la n est si bas, la mémoire vive de surcharge de stockage d'un assez grand tableau serait vous faire du mal avant les caractéristiques de recherche de Big-O serait de commencer à prendre effet. Par exemple la différence entre un appel à array_key_exists à N=1 et N=1 000 000 de est de ~50% augmentation de temps.

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 ressemble plus belle). Mais il fonctionne différemment donc, gardez cela à l'esprit.
3. shuffle est sur le même Big-O tier comme array_rand
4. array_pop/array_push est plus rapide que array_shift/array_unshift en raison de ré-indexer la peine de
Recherches:

array_key_exists O(n) mais vraiment proche de O(1) - c'est à cause de linéaire de vote dans les collisions, mais parce que les chances de collision est très faible, le coefficient est également très faible. Je trouve que vous traiter de hachage recherches que O(1) pour donner une idée plus réaliste de la grande-O. Par exemple la différence entre N=1000 et N=100000 n'est que d'environ 50% de ralentir.

isset( $array[$index] ) O(n) mais vraiment proche de O(1) - il utilise la même recherche que array_key_exists. Puisque c'est la langue de construire, la mise en cache sera la recherche de si la clé est codée en dur, résultant de la vitesse dans le cas où la même clé est utilisée à plusieurs reprises.

in_array O(n) - c'est parce qu'il fait une recherche linéaire même si la batterie jusqu'à ce qu'il trouve la valeur.

array_search O(n) - il utilise la même fonction de base comme in_array mais retourne la valeur.

File d'attente fonctions:

array_push O(∑ var_i, pour tout i)

array_pop O(1)

array_shift O(n) - c'est à réindexer toutes les clés

array_unshift O(n + ∑ var_i, pour tout i), il a pour réindexer toutes les clés

Tableau Intersection, Union, Soustraction:

array_intersect_key si l'intersection de 100% ne O(Max(param_i_size)*∑param_i_count, pour tout i), si l'intersection de 0% se coupent en O(∑param_i_size, pour tout i)

array_intersect si l'intersection de 100% ne O(n^2*∑param_i_count, pour tout i), si l'intersection de 0% se coupent en O(n^2)

array_intersect_assoc si l'intersection de 100% ne O(Max(param_i_size)*∑param_i_count, pour tout i), si l'intersection de 0% se coupent en O(∑param_i_size, pour tout i)

array_diff O(π param_i_size, pour tous les i)) Que du produit de tous les param_sizes

array_diff_key O(∑ param_i_size, pour moi != 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'effectuer une itération sur le premier tableau

+ (union) O(n), où n est la taille de la 2e tableau (c'est à dire array_first + array_second) - moins de frais généraux que array_merge car elle n'a pas de renuméroter

array_replace O( ∑ array_i, pour tout i )

Aléatoire:

shuffle O(n)

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

Évident Big-O:

array_fill O(n)

array_fill_keys O(n)

range O(n)

array_splice O(offset + 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(pad_size)

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 le rendre facile de trouver le Big-O des fonctions. C'est une incroyable gratuit programme qui peut trouver le mieux adapté à une fonction arbitraire de données.

EDIT:

Pour ceux qui doutent que le tableau PHP des recherches sont O(N), j'ai écrit une référence de test (ils sont effectivement encore O(1) pour la plupart des valeurs 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 );
}
```
- C'est une bonne chose qu'il s'exécute dans le vin, puis 🙂
- C'est peut-être bon pour la rétro-ingénierie des pilotes de périphériques. Je vais m'en tenir à une virtualbox 😉 Avoir du plaisir avec elle maintenant. Merci!
- Êtes-vous sûr de hachage des recherches sont en O(n)? Ce que je comprends, PHP utilise des chaînes et des nombres entiers pour les clés de hachage, de la sorte, peut collisions ne pas être traités à l'aide de certains logn discbased (par exemple un arbre de recherche binaire)?
- Avant que je m'adresse à votre première question, je vais parler de la façon dont les index sont stockés. Tout d'abord, les index sont stockés en tant que cordes et comme par magie transtypage vers entiers si elles correspondent forme entière. Par exemple, tous les de le suivre clés dans le tableau ressemble à ints si vous vérifiez leur type: array( 1 => NULL, "1" => NULL, "1000" => NULL, "-100" => NULL ), mais ces sont des chaînes de caractères: array( "01" => NULL, "--1" => NULL, "1 " => NULL, " 1" => NULL ).
- De ce fait, il est à seulement 1 type de hachage, de sorte que votre droit qu'il pourrait avoir un O(Log(n)). Dans les pratiques, le hachage peut être plus rapide pour les petits (ou même d'assez grande taille) les valeurs de N, même si elle se fait au prix de linéaire de vote en cas de collisions. Comme je l'ai dit dans le post la différence entre un tableau de N=1 et N=1 000 000 de n'est 2x plus lent, de sorte que la fonction de hachage est évidemment assez grand pour manger la plupart du temps dans la plupart des cas. Mais pour répondre à votre première question, PHP hachage recherches sont techniquement O(n), vous pourrez même le voir, parce que vous serez à court de mémoire ram d'abord.
- J'ai mis à jour le post w/ une recherche de référence graphique qui montre qu'il est O(N).
- Merci! J'ai fait un peu de lecture et il s'avère que PHP utilise "imbriquées" tables de hachage pour les collisions. C'est, au lieu d'un logn structure pour les collisions, il utilise simplement une autre table de hachage. Et je comprends que, pratiquement parlant, PHP tables de hachage donner O(1) de la performance, ou au moins O(1) en moyenne - c'est ce que les tables de hashage sont pour. J'étais juste curieux de savoir pourquoi vous avez dit qu'ils sont "vraiment O(n)" et "pas vraiment O(logn)". Après la grande en passant!
- Big-O est la limite supérieure de la fonction lorsque N->infitity. Tandis que la fonction a O(1) et O(log(N)) au cours de la "fillup étapes" il finit par se stabilise à O(N).
- Dans le pire des cas, c'est vrai qu'il aura O(n) de la performance. Mais je pense que la moyenne des cas, la performance est toujours en O(1). Pour voir ceci: Lorsqu'une collision se produit, une nouvelle table de hachage est créé pour toutes les valeurs de cette clé, et les touches sont rabâchage là. Il est très peu probable que les collisions auront lieu de nouveau. Comme nous l'avons ajouter des tables de hachage à de plus en plus profonde des profondeurs de gérer les collisions, nous parlons en fait d'un plus petit et plus petit sous-ensemble de l'entrée, depuis ce nid de collisions qui va arriver très rarement. Si la moyenne des cas d'exécution est O(1), et pas de O(n) avec une petite constante.
- C'est la façon dont je le comprends au moins - si je suis incorrect j'aimerais vraiment comprendre pourquoi il est O(n), même dans le cas moyen.
- Je pense que votre incorrection sur la façon de PHP array est mis en œuvre. PHP array (ou hash) est mis en œuvre à l'aide de le chaînage. Ce qui signifie bien que votre remplissage de la première couche, il est fondamentalement O(1) en raison de la cher de hachage dessus, mais une fois la première couche est rempli, vous devez utiliser linéaire d'interrogation (à pied une liste) pour atteindre la collision. Cela aussi est aussi insignifiant par rapport aux hachage de surcharge pour toute valeur réaliste N<10000000 (pourquoi il est O(1) dans la pratique). Si votre encore difficile de lire la suite de la page wiki.
- Temps complexités devrait être inclus dans la documentation! Choisir la bonne fonction peut vous sauver beaucoup de temps, ou de vous dire d'éviter de faire ce que vous avez prévu :p Merci pour cette liste déjà!
- Note rapide: isset est un opérateur, de sorte qu'il est prévu (plusieurs posts et documenté trop afair). key_exists seulement un hachage de recherche, ce qui est beaucoup plus rapide que la recherche de tous les tableau elems.
- Je sais que c'est vieux ... mais quoi? Cette courbe ne montre pas de O(n), il montre O(log n), en.wikipedia.org/wiki/Logarithm. Ce qui est aussi précise de ce que vous attendez pour imbriquée de hachage-cartes.
- Qu'est-ce que le Big-O de unset sur un élément d'un tableau?
- Alors que les tables de hachage ont, en effet, pour le pire des cas O(n) de recherche de la complexité, la moyenne des cas est O(1) et le cas particulier de votre cas-test est le test est même garantie O(1), c'est un zéro continu, numériquement-tableau indexé, qui n'aura jamais les collisions de hachage. La raison pour laquelle vous voyez toujours une dépendance à la taille de la matrice n'a rien à voir avec la complexité algorithmique, elle est causée par le cache du PROCESSEUR d'effets. Plus le tableau est grand, plus il est probable que l'accès aléatoire recherches entraînera dans le cache (et le cache supérieur de la hiérarchie).
- Pour info, PHP 7 utilise un grandement amélioré la table de hachage de la mise en œuvre pour les tableaux.
InformationsquelleAutor Kendall Hopkins
4

L'explication pour le cas où vous décrire précisément, c'est que les tableaux associatifs sont mis en œuvre comme les tables de hachage - de sorte que la recherche par clé (et, en conséquence, array_key_exists) est O(1). Toutefois, les tableaux ne sont pas indexés par valeur, donc la seule façon que dans le cas général, pour découvrir si une valeur existe dans le tableau est une recherche linéaire. Il n'y a pas de surprise là.

Je ne pense pas qu'il existe une certaine documentation complète de la complexité algorithmique des méthodes de PHP. Cependant, si c'est une assez grande préoccupation pour justifier l'effort, vous pouvez toujours regarder à travers le code source.
- Ce n'est pas vraiment une réponse. Comme je l'ai dit dans la question, j'ai déjà essayé de regarder dans le code source PHP. Depuis PHP est mis en œuvre est écrite en C, rendant l'utilisation de macros complexes, ce qui peut rendre difficile à la fois pour "voir" le sous-jacent big O pour les fonctions.
- J'ai oublié votre référence pour plonger dans le code source. Cependant, il y a une réponse à ma réponse: "je ne pense pas qu'il existe une certaine documentation complète de la complexité algorithmique des méthodes de PHP." "Non" est une parfaite réponse valable. (c:
InformationsquelleAutor Dathan
3

Vous presque toujours utiliser isset au lieu de array_key_exists. Je ne suis pas à la recherche à l'interne, mais je suis assez sûr que array_key_exists est O(N) car il itère sur chaque clé du tableau, alors que isset tente d'accéder à un élément en utilisant le même algorithme de hachage est utilisée lorsque vous accédez à un tableau d'index. Qui devrait être O(1).

Un "piège" à regarder dehors pour est ceci:
```
$search_array = array('first' => null, 'second' => 4);

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

//returns true
array_key_exists('first', $search_array);
```
J'étais curieux, j'ai donc comparé 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 secondes

array_key_exists: 2.33202195168 secondes

Bien sûr, ce n'est pas le spectacle de la complexité, mais il montre comment les 2 fonctions de comparer les uns aux autres.

Pour tester le temps de la complexité, de comparer la quantité de temps nécessaire pour exécuter l'une de ces fonctions sur la première et la dernière touche.
- Ce qui est faux. Je suis sûr à 100% array_key_exists ne pas avoir à répéter sur chaque touche. Si vous ne croyez pas à être jeter un oeil au lien ci-dessous. La raison isset est donc beaucoup plus rapide, c'est que c'est une construction du langage. Ce qui signifie qu'il n'a pas la surcharge de faire un appel de fonction. Aussi, je pense qu'il pourrait être mise en cache de la recherche, à cause de cela. Aussi, ce n'est pas une réponse à LA QUESTION! Je voudrais une liste de Gros(O) pour les fonctions de PHP (comme la question des états). Pas une seule référence de mes exemples. svn.php.net/repository/php/php-src/branches/PHP_5_3/ext/...
- Si vous ne me croyez toujours pas, j'ai créer un petit benchmark de le démontrer. pastebin.com/BdKpNvkE
- Quel est le problème avec votre référence, vous devez désactiver l'extension xdebug. =)
- Il existe deux raisons pour lesquelles vous souhaitez utiliser la fonction isset plus array_key_exists. Tout d'abord, la fonction isset est une structure du langage limiter le coût d'un appel de fonction. Ceci est similaire à la $arrray[] = $append vs array_push($array, $append) argument. Deuxièmement, array_key_exists également la distinction entre les non-set et les valeurs null. Pour $a = array('fred' => null); array_key_exists('fred', $a) retourne true, alors que isset($['fred']) retournera false. Cette étape supplémentaire est non-trivial et permettra d'accroître considérablement le temps d'exécution.
InformationsquelleAutor ryeguy
0

Si les gens étaient en cours d'exécution dans le trouble, dans la pratique, avec la clé de collisions, de mettre en œuvre des contenants avec un secondaire hachage de la recherche et l'équilibre de l'arbre. L'équilibre de l'arbre donnerait O(log n) le pire des cas, le comportement et O(1) avg. cas (le hash lui-même). La surcharge n'est pas la peine, dans la plupart des pratiques dans les applications de mémoire, mais peut-être qu'il existe des bases de données de mise en œuvre de cette forme mixte de stratégie par défaut dans les cas.

InformationsquelleAutor Josh Stern

Vous devez vous connecter pour publier un commentaire.