Get best of the week

PHP: array_key_exists recherche 500 fois plus vite que in_array

En 2014, ils avaient déjà écrit sur la recherche du réseau , mais presque personne ne comprenait.

Depuis lors, de nombreuses versions de PHP ont été publiées et n'ont pas été corrigées, ce qui signifie que les commentaires sont mauvais et que peu de gens le savent. Sur python c'est pareil, et en 3 * pire qu'en 2.7.

Parfois, vous devez trouver une chaîne dans un tableau de chaînes - une opération très fréquente dans différents algorithmes et si le tableau est petit et semble un peu et pas en boucle, alors in_array est normal, cela n'affecte pas la vitesse globale, mais si vous avez besoin de données volumineuses et recherchez un tableau d'un milliard de lignes et d'un milliard de fois , alors c'est critique: une meilleure heure au lieu de la semaine.

Un test simple montre:

in_array recherche ideone.com/Yb1mDa 6600msen 6-9 secondes
et array_key_exists cherche la même chose, mais plus vite que 250 (php5.6 / py3. *) 400+ fois (php7.3 / py2.7) ideone .com / gwSmFc(cycle augmenté 100 fois) 12 ms (6600/12 = 550 fois + -10% de propagation en raison de la charge et du cache)

Pourquoi cela se produit-il? Considérez en détail:

1) La recherche de chaînes dans un assembleur / s pur consiste à trier un tableau de chaînes (rapide ou à bulles), puis à effectuer une recherche binaire.

Le nombre d'étapes dans un journal de recherche binaire (n) fois dépend de la taille du tableau et est beaucoup plus petit qu'une recherche simple.

Vous pouvez trier un tableau de chaînes à l'avance, une fois, et mettre en cache, puis effectuer un milliard de recherches. Mais cela n'aide pas.

Par défaut, le tri se produit à chaque fois, bien qu'ils aient écrit qu'ils s'étaient améliorés dans 7.2 in_array grâce à un hachage, mais pas beaucoup.

2) Rechercher l'index / la clé (sous forme de chaîne) dans l'association. tableau / dictionnaire se produit par le hachage des chaînes et le traitement des collisions (erreurs de recherche de hachage). Un hachage est l'index numérique du tableau et le récupère en tant que (adresse de l'élément zéro) + offset * la taille du pointeur vers le tableau de chaînes avec ce hachage) en 2 étapes. + collisions par force brute, pas en moyenne inférieur à la recherche binaire.
Le hachage d'index est effectué automatiquement une fois à l'avance lors de la création de l'élément de dictionnaire $ m [key] = val et est mis en cache.

La taille du hachage, l'algorithme de hachage est cousu dans le moteur php et il ne peut pas être changé, bien que le code source soit ouvert, vous pouvez télécharger pour changer et compiler si votre serveur.

Vous ne pouvez pas lire plus loin, changez in_array en array_combine + array_key_exists et c'est tout.

Le nombre d'étapes lors de la recherche par hachage dépend du nombre de collisions et du nombre de lignes avec le même hachage. Ils doivent être triés ou également triés et recherche binaire.

Pour réduire les collisions, vous pouvez allouer plus de mémoire, s'il est possible que ce ne soit plus le cas il y a 50 ans quand 1 ko de mémoire sur des bobines magnétiques coûtait comme un avion. Et c'est alors que tous les algorithmes de base ont été inventés: tri / zip / gif / jpg / etc. - ils n'ont pas besoin de beaucoup de mémoire, mais ils sont mauvais, maintenant ils sont bien meilleurs, mais ils ont besoin de beaucoup de mémoire 1-16 Mo. Oui, il y a des serveurs avec 256 Mo et chacun a un flux séparé et 16 Mo c'est déjà beaucoup, mais sur l'appareil de l'utilisateur moyen 1 Go au moins et 16 Mo est une goutte dans le seau.

Vous pouvez obtenir encore plus d'effet si vous remplacez l'appel à array_key_exists par la construction isset ($ m [key]), il n'efface pas la file d'attente de commandes et le cache, il n'utilise pas la pile et est plus rapide d'environ 20%.

Vous pouvez également l'accélérer si vous créez un tableau des 2 premières lettres - 4 * 16 Ko et regardez d'abord l'offset (index = code du 1er caractère + 2e * 256) un pointeur vers le tableau de hachage pour le reste de la ligne, puis recherchez un petit tableau de «queues» de chaînes et les collisions sont beaucoup plus petites.

Il nécessite encore plus de mémoire et l'algorithme est plus compliqué, mais la recherche est 30 fois plus rapide. Mais ceci n'est pas implémenté en php, vous pouvez écrire votre bibliothèque so / dll et l'appeler, ou demander aux développeurs de l'ajouter en 7.5.

Vous pouvez rechercher dans mySQL, mais vous devez regrouper les requêtes et ce sera toujours plus lent.

PS: Cette méthode a été accidentellement trouvée en tapant, en intuition et en expérience lorsque j'ai accéléré un grand site lent, il y a beaucoup de telles subtilités et astuces, j'ai réussi à télécharger des données vers Excel de 40 secondes à 0,8 secondes, afficher des listes avec tri et filtres, et bien d'autres des choses où les techniques standard, les frameworks et les frameworks le font trop lentement, bien qu'ils soient bien sûr pratiques et accélèrent le développement.

More articles:


All Articles