qu'est-ce qui est le plus rapide: in_array ou isset? [fermé]

96

Cette question est simplement pour moi car j'aime toujours écrire du code optimisé qui peut également fonctionner sur des serveurs lents bon marché (ou des serveurs avec BEAUCOUP de trafic)

J'ai regardé autour de moi et je n'ai pas pu trouver de réponse. Je me demandais ce qui est le plus rapide entre ces deux exemples en gardant à l'esprit que les clés du tableau dans mon cas ne sont pas importantes (pseudo-code naturellement):

<?php
$a = array();
while($new_val = 'get over 100k email addresses already lowercased'){
    if(!in_array($new_val, $a){
        $a[] = $new_val;
        //do other stuff
    }
}
?>

<?php
$a = array();
while($new_val = 'get over 100k email addresses already lowercased'){
    if(!isset($a[$new_val]){
        $a[$new_val] = true;
        //do other stuff
    }
}
?>

Comme le point de la question n'est pas la collision de tableaux, je voudrais ajouter que si vous avez peur de heurter des insertions pour $a[$new_value], vous pouvez utiliser $a[md5($new_value)]. cela peut toujours provoquer des collisions, mais enlèverait une éventuelle attaque DoS lors de la lecture d'un fichier fourni par l'utilisateur ( http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html )

Fabrizio
la source
3
Si vous vous efforcez toujours d'écrire du code optimisé, vous utilisez sûrement un profileur de temps en temps?
mario
59
Je vote pour rouvrir. La question est bien formulée et les réponses sont étayées par des faits et des références. Bien qu'il s'agisse d' une micro- optimisation, ces types de questions sont constructives .
Jason McCreary
5
@JasonMcCreary second; juste un de plus.
Ja͢ck
7
C'est bien des années plus tard, mais je ne considérerais même pas cela comme une micro-optimisation. Pour les grands ensembles de données, cela peut faire une tonne de différence !!
Robert
2
... cette question me paraît "constructive". Je vais commencer une autre campagne de réouverture.
mickmackusa

Réponses:

117

Les réponses à ce jour sont justes. L'utilisation issetdans ce cas est plus rapide car

  • Il utilise une recherche de hachage O (1) sur la clé alors qu'il in_arraydoit vérifier chaque valeur jusqu'à ce qu'il trouve une correspondance.
  • Étant un opcode, il a moins de surcharge que d'appeler la in_arrayfonction intégrée.

Celles-ci peuvent être démontrées en utilisant un tableau avec des valeurs (10 000 dans le test ci-dessous), ce in_arrayqui oblige à faire plus de recherche.

isset:    0.009623
in_array: 1.738441

Cela s'appuie sur le benchmark de Jason en remplissant des valeurs aléatoires et en trouvant occasionnellement une valeur qui existe dans le tableau. Tous aléatoires, alors méfiez-vous que les temps vont fluctuer.

$a = array();
for ($i = 0; $i < 10000; ++$i) {
    $v = rand(1, 1000000);
    $a[$v] = $v;
}
echo "Size: ", count($a), PHP_EOL;

$start = microtime( true );

for ($i = 0; $i < 10000; ++$i) {
    isset($a[rand(1, 1000000)]);
}

$total_time = microtime( true ) - $start;
echo "Total time: ", number_format($total_time, 6), PHP_EOL;

$start = microtime( true );

for ($i = 0; $i < 10000; ++$i) {
    in_array(rand(1, 1000000), $a);
}

$total_time = microtime( true ) - $start;
echo "Total time: ", number_format($total_time, 6), PHP_EOL;
David Harkness
la source
Je connais les hachages, mais je me demande pourquoi quelque chose de similaire n'est pas fait sur les valeurs des tableaux lorsque cela est possible pour accélérer les fonctions, cela réduira également la consommation de mémoire si des valeurs similaires sont utilisées en ajoutant simplement un hachage supplémentaire sur la valeur .. correct?
Fabrizio
3
@Fabrizio - Les valeurs de tableau peuvent être dupliquées et contenir des objets non hachables. Les clés doivent être uniques et ne peuvent être que des chaînes et des entiers, ce qui les rend facilement hachables. Bien que vous puissiez créer une carte un à un qui hache à la fois les clés et les valeurs, ce n'est pas ainsi que le tableau de PHP fonctionne.
David Harkness
3
Si vous êtes sûr que votre tableau contient des valeurs uniques, il existe une autre option - flip + isset .
Arkadij Kuzhel
à noter qu'un isset retourné est toujours plus rapide dans cet exemple que in_array: `` `` $ start = microtime (true); $ toto = tableau_flip ($ a); pour ($ i = 0; $ i <10000; ++ $ i) {isset ($ foo [rand (1, 1000000)]); } $ total_time = microtime (vrai) - $ start; echo "Temps total (jeu d'isset retourné):", number_format ($ total_time, 6), PHP_EOL;
Andre Baumeier
@AndreBaumeier Ce qui est le plus rapide dépendra de la taille du tableau et du nombre de tests que vous ferez. Retourner un tableau de dix mille éléments pour effectuer trois tests n'est probablement pas efficace.
David Harkness
42

Ce qui est plus rapide: isset()vsin_array()

isset() est plus rapide.

Bien que cela devrait être évident, isset()ne teste qu'une seule valeur. Alors que in_array()va itérer sur tout le tableau, en testant la valeur de chaque élément.

Une analyse comparative approximative est assez facile à utiliser microtime().

Résultats:

Total time isset():    0.002857
Total time in_array(): 0.017103

Remarque: les résultats étaient similaires, qu'ils existent ou non.

Code:

<?php
$a = array();
$start = microtime( true );

for ($i = 0; $i < 10000; ++$i) {
    isset($a['key']);
}

$total_time = microtime( true ) - $start;
echo "Total time: ", number_format($total_time, 6), PHP_EOL;

$start = microtime( true );

for ($i = 0; $i < 10000; ++$i) {
    in_array('key', $a);
}

$total_time = microtime( true ) - $start;
echo "Total time: ", number_format($total_time, 6), PHP_EOL;

exit;

Ressources supplémentaires

Je vous encourage à regarder également:

Jason McCreary
la source
Belle solution. Je suis surpris que plus de gens ne divisent pas leurs fonctions / code plus en utilisant microtime()ou d'autres outils. Incroyablement précieux.
nickhar
1
La recherche d'un tableau vide pour la même clé ne met en évidence que la surcharge de l'appel de la in_arrayfonction par rapport à l'utilisation de la fonction issetintégrée. Ce serait mieux avec un tableau contenant un tas de clés aléatoires et recherchant occasionnellement une clé / valeur existante.
David Harkness
J'utilise pas mal de benchmarks et de microtime, mais je me suis aussi rendu compte, pendant que je testais whileet foreachqu'à chaque rafraichissement, j'obtenais différents "gagnants". cela dépend toujours d'un trop grand nombre de variables de serveur, et le mieux est d'itérer un très grand nombre de fois à des moments différents et d'obtenir celui qui gagne le plus souvent, ou simplement de savoir ce qui se passe en arrière-plan et de savoir que ce sera le vainqueur final quoi qu'il
arrive
@David Harkness, vous avez déjà choisi ma réponse. Si vous en voulez plus, mettez-vous sur mes épaules et postez votre propre réponse. :) Néanmoins, si la surcharge de la fonction est déjà beaucoup plus chère par rapport à isset(), qu'est-ce qui vous fait penser que passer un tableau plus grand le rendrait plus rapide ?
Jason McCreary
1
@Fabrizio - Renseignez-vous sur les fonctions de hachage et les tables de hachage .
David Harkness
19

L'utilisation isset()tire parti d'une recherche plus rapide car elle utilise une table de hachage , évitant ainsi le besoin de O(n)recherches.

La clé est d'abord hachée à l'aide de la fonction de hachage djb pour déterminer le compartiment de clés hachées de manière similaire dans O(1). Le compartiment est ensuite recherché de manière itérative jusqu'à ce que la clé exacte soit trouvée dans O(n).

À moins de collisions de hachage intentionnelles , cette approche donne de bien meilleures performances que in_array().

Notez que lors de l'utilisation isset()de la manière que vous avez montrée, passer les valeurs finales à une autre fonction nécessite d'utiliser array_keys()pour créer un nouveau tableau. Un compromis de mémoire peut être fait en stockant les données à la fois dans les clés et les valeurs.

Mettre à jour

Un bon moyen de voir comment vos décisions de conception de code affectent les performances d'exécution, vous pouvez consulter la version compilée de votre script:

echo isset($arr[123])

compiled vars:  !0 = $arr
line     # *  op                           fetch      ext  return  operands
-----------------------------------------------------------------------------
   1     0  >   ZEND_ISSET_ISEMPTY_DIM_OBJ              2000000  ~0      !0, 123
         1      ECHO                                                 ~0
         2    > RETURN                                               null

echo in_array(123, $arr)

compiled vars:  !0 = $arr
line     # *  op                           fetch      ext  return  operands
-----------------------------------------------------------------------------
   1     0  >   SEND_VAL                                             123
         1      SEND_VAR                                             !0
         2      DO_FCALL                                 2  $0      'in_array'
         3      ECHO                                                 $0
         4    > RETURN                                               null

Non seulement in_array()utilise une O(n)recherche relativement inefficace , mais elle doit également être appelée en tant que fonction ( DO_FCALL) alors qu'elle isset()utilise un seul opcode ( ZEND_ISSET_ISEMPTY_DIM_OBJ) pour cela.

Jack
la source
7

Le second serait plus rapide, car il ne recherche que cette clé de tableau spécifique et n'a pas besoin d'itérer sur tout le tableau jusqu'à ce qu'il soit trouvé (examinera chaque élément du tableau s'il n'est pas trouvé)

Mike Brant
la source
mais dépend également de la localisation d'une var recherchée dans le monde entier
el Dude
@ EL2002, pouvez-vous expliquer cette déclaration?
Fabrizio
1
Mike, ne regarderait-il pas l'ensemble du tableau même avec le isset()s'il n'est pas trouvé?
Fabrizio
1
@Fabrizio Non, il n'a pas besoin d'itérer. En interne (en C), le tableau PHP n'est qu'une table de hachage. Afin de rechercher une seule valeur d'index, C effectue simplement un hachage de cette valeur et recherche son emplacement attribué en mémoire. Il y a une valeur là ou il n'y en a pas.
Mike Brant
1
@Fabrizio Cet article fournit un bon aperçu de la façon dont les tableaux sont représentés en interne en C par PHP. nikic.github.com/2012/03/28/…
Mike Brant