Mot-clef « Bench »

Petit bench sur la recherche dans un tableau PHP

Préambule...

Hier, j'avais à parcourir un tableau d'objets (pouvant avoir potentiellement des centaines voire exceptionnellement milliers d'entrée) pour rechercher si l'identifiant de l'un d'eux se trouvait dans un second tableau. J'avais commencé par utiliser pour ça la fonction in_array() à chaque itération pour voir si l'identifiant de l'objet était présent ou non dans le second tableau.

En voyant cela, un collègue m'a fait remarquer que ce serait peut-être plus performant de construire un tableau dont les clés sont les valeurs du second tableau (via array_flip()) pour pouvoir utiliser isset() au lieu de in_array() et voici les résultats obtenus :

Structure du bench

Le bench consiste à rechercher 100 000 fois la même valeur dans le tableau array('11345', '7437', '7329', '45494', '7894311', 'sdfsdg', 'qsqsdcirt', 'd787 sdfs df'), avec trois méthodes différentes :

  • in_array()
  • array_flip() suivi de isset()
  • array_flip() suivi de array_key_exists()

Le test est effectué avec deux valeurs différentes : d'abord avec la première valeur du tableau (cas théoriquement le plus favorable puisqu'on arrête la recherche une fois la valeur trouvée) puis avec une valeur qui n'est pas dans le tableau (cas théoriquement le plus défavorable puisqu'on est obligé de parcourir tout le tableau). Le résultat en conditions réelles sera donc compris dans cette fourchette.

Cas in_array()

Code exécuté :

for ($i = 0; $i < 100000; $i++)
{
	in_array($value, $values);
}

Cas favorable ($value = '11345') : ~0.33 secondes
Cas défavorable ($value = 'uottuyi') : ~0.52 secondes

Cas isset()

Code exécuté :

$keys = array_flip($values);
for ($i = 0; $i < 100000; $i++)
{
	isset($keys[$value]);
}

Cas favorable ($value = '11345') : ~0.12 secondes
Cas défavorable ($value = 'uottuyi') : ~0.09 secondes

Cas array_key_exists()

Code exécuté :

$keys = array_flip($values);
for ($i = 0; $i < 100000; $i++)
{
	array_key_exists($value, $keys);
}

Cas favorable ($value = '11345') : ~0.27secondes
Cas défavorable ($value = 'uottuyi') : ~0.24 secondes

Et pour de plus petites quantités ?

Les grands volumes c'est bien mais qu'est-ce que ça donne quand on a peu d'itérations ?

Un test à 5 itérations au lieu de 100 000 donne environ le même résultat pour les trois méthodes : avec ~6E-05 secondes pour les méthodes 1 et 3 et ~5E-05 pour la méthode 2.

Tandis qu'un test sur une unique itération donne la première méthode gagnante avec ~4E-05 secondes contre ~5E-05 pour les deux autres (à ce niveau c'est le array_flip pour transformer les valeurs en clés qui coute cher).

Conclusion

À moins d'avoir toujours très peu d'itérations (moins de 5), la méthode passant par array_flip() puis isset() est d'assez loin la meilleure (environ quatre fois plus rapide sur des grands nombres et pas plus lente sur des petits).

En passant, on remarque aussi qu'avec cette méthode, rechercher une valeur qui n'existe pas dans le tableau est plus rapide que de rechercher la première valeur du tableau, même si je ne vois pas forcément trop pourquoi :pense: