Répondre à la réponse Cette question j'ai confronté une situation intéressante 2 Code similaire les extraits effectués de manière assez différente. Je demande ici juste de comprendre la raison de cela et d'améliorer mon intuition pour de tels cas.
Je vais adapter les extraits de code pour Python 2.7 (en Python 3, les différences de performance sont les mêmes). P> xxx pré>
sortie: p>
0.603327797248 1.21580172899
4 Réponses :
Comme vous l'avez mentionné vous-même, il y a une différence entre les fonctions.
Lorsque la première fonction iTère sur une liste de chaînes, pour chaque chaîne, il va au dictionnaire et le regarde pour obtenir la valeur, puis il trouve le minimum et le retourne.
La deuxième fonction iTère sur des tuples de cordes / de paires de cordes. Et puis pour chacun d'entre eux, il accède au deuxième élément (l'int / valeur), puis il trouve le minimum (qui est un tuple dans ce cas), puis il renvoie ce premier élément.
La deuxième fonction fait beaucoup plus de travail, sur des objets nécessitant beaucoup plus de traitement, (tuples> chaînes), puis (tuples> INTS), ainsi que la récupération d'élément supplémentaire.
Pourquoi êtes-vous surpris?
Je suis surpris de 2 fois différentes différences. Je pensais que ces extraits devraient avoir une performance similaire. Étant donné que la recherche dans le dictionnaire n'est pas si simple (la corbeille doit être trouvée, que des touches correspondant à cette corbeille, puis valorisez la clé de montage). Lorsque nous iTerons des paires de vales-clés de dictionnaire, il n'y a pas de recherche de bac, puis de la clé, nous allons simplement passer à tous les bacs et toutes les clés. Mais la deuxième solution a une surcharge d'avoir à mettre la valeur de la clé en tuple et à obtenir une deuxième valeur de TUPLE BACK (qui est un accès aléatoire), mais je ne m'attendais pas à ce que cela donne une telle générale.
Quel objet vous voulez dire? Avez-vous regardé la vidéo sur la réutilisation de Tuple? Je viens de poser cette question parce que je ne comprends pas complètement toutes les étapes Python prises dans chaque cas de code, alors je m'attendais à ce que quelqu'un puisse expliquer tout cela en détail. Du premier coup d'œil (sans comparaison comparative), je pensais que la première solution est plus lente car elle doit établir des recherches de dictionnaire et il suffit de stocker des valeurs de clé dans le même tuple.
Zhangyangyu 's Réponse résout vos questions techniques.
@ovgolovin, ce n'est pas seulement 2 fois. Essayez de donner un plus gros dictionnaire et voir la différence. L'utilisation de l'itérateur ajoutera O (n) complexité de temps, de sorte que l'écart entre les timings continuera à augmenter à mesure que le nombre d'éléments de la dict augmente.
Dans Python 3 .items () donnera itérateur comme .iteritems () en 2.7, la performance sera la même.
@ user568109 C'est un bon point sur la taille du dictionnaire. En ce qui concerne l'itérateur addin O (n) la complexité du temps, je ne l'obtiens pas. Min (éléments, touche = items.get) a o (n) complexité, car il passe à travers tous les éléments. min (éléments.iteritems (), clé = itemGetter (1)) [0] a également o (n) complexité car il passe par les mêmes éléments, emballés dans la clé -Value paires par iteritems générateur. La différence concerne les constantes.
@ user568109 Ce que j'attends vraiment de la question est d'obtenir la règle du pouce quelles opérations je préférerais lorsque vous préférez des extraits de code. Les deux solutions de la question sont presque égales en termes de lisibilité (au moins pour moi), donc je souhaite pouvoir comprendre au premier coup d'œil que l'on sera plus rapide et le préférera sur l'autre option.
@OVGOLOVIN Oui Ajout de deux O (n) Le temps signifierait uniquement le changement de coefficient de N dans O (n), car l'heure d'accès par clé de clé est augmentée. La différence de temps entre les deux méthodes augmente avec n.
@ user568109 Deuxième solution ajoute non seulement à ce coefficient, mais économisez de la nécessité d'accéder à la valeur dans le dictionnaire par la touche, car elle itière via des paires de la valeur de clé consécutivement, tandis que le premier iTerate via des touches, mais doit récupérer la valeur via le dictionnaire. Recherche (qui implique de prendre des opérations de hash et d'autres opérations), la deuxième solution n'a à stocker que la valeur dans le tuple. Il n'est donc pas correct de dire que la deuxième solution a augmenté le coefficient: il a un coefficient différent, et il n'est pas évident au premier coup d'œil s'il est plus grand ou plus petit.
@ovgolovin Le dictionnaire existe pour les deux méthodes. Vous bannissez le temps nécessaire à Itérateur pour renvoyer une paire de valeur clé. Il devra également rechercher la valeur pour renvoyer une paire de valeur clé. Après tout ce que vous donnez, l'itérateur est dictionnaire. Ce que Itérateur est différent de celui-ci, est-ce que cela donne à la prochaine valeur de la clé en boucle jusqu'à la demande (évaluation paresseuse), tandis que la première méthode donne toutes les valeurs à la fois. La deuxième méthode ajoute le traitement et la copie à la recherche, il aura donc un coefficient plus élevé.
@ user568109 Si vous savez comment fonctionne de la carte Hash-Carte, vous devez constater qu'il n'est pas nécessaire de rechercher la clé tandis que l'itération via Hash-Carte, car vous venez d'itérer à toutes les touches de bacs et de retournement et de valeurs associées Pour calculer le hasch sur celui-ci pour obtenir un numéro de bin et n'accumule que cette touche dans cette corbeille, et après cela, l'accès à celui-ci). Sûrement, iteritems peut être mis en œuvre pour créer des recherches, mais cela serait insensé de la mettre en œuvre de cette façon de calculer à nouveau la corbeille pendant que vous êtes déjà dans cette corbeille.
@ user568109 La première méthode ne donne pas toutes les valeurs à la fois, comme min l'utilise comme itérateur (il invoque __ iTer __ méthode et passe la valeur informatique par valeur). En ce sens, les solutions se ressemblent comme ils traversent le dictionnaire paresseux.
@ user568109 Deuxième solution forme définitivement un tuple à partir de la paire de forces de clé sur chaque itération. Mais s'il y a une réutilisation de tuple (comme dans CPPHON), le tuple n'est pas attribué, il est extrait de disposer précédemment. Donc, cela revient à ne pas enregistrer la clé et la valeur pour le tuple existant tiré de disposé. Je m'attends à ce que l'économie de deux valeurs soit assez rapide. La première solution doit invoquer hachage pour déterminer la corbeille. Êtes-vous sûr que l'enregistrement de 2 valeurs à tuple est plus lent que le hachage de calcul et accéder à la corbeille?
@ovgolovin, je comparais des articles vs itérateurs.iteritems (). Oui, un itérateur ne donnera pas toutes les valeurs, mais je ne faisais pas référence à min. Je me référais à la différence dans les premiers arguments. Le premier a toutes les valeurs, la seconde nécessite un traitement supplémentaire pour obtenir les valeurs.
Vous devriez vraiment déplacer cette conversation en discussion.
... Si vous le déplacez sur une conversation, vous devez inclure le lien ici pour la postérité.
pour la réutilisation de tuple, je ne le crois pas:
>>> a
OrderedDict([('a', 1), ('c', 3), ('b', 2)])
>>> N = 100000
#Use []
>>> Timer(stmt='for x in a: z = a[x]', setup='from __main__ import a').timeit(number=N)
0.2354598045349121
#Use get
>>> Timer(stmt='for x in a: z = a.get(x)', setup='from __main__ import a').timeit(number=N)
0.21950387954711914
#Use iterator
>>> Timer(stmt='for x in a.iteritems(): z = x[1]', setup='from __main__ import a').timeit(number=N)
0.29949188232421875
#Use iterator and itemgetter
>>> b = itemgetter(1)
>>> Timer(stmt='for x in a.iteritems(): z = b(x)', setup='from __main__ import a, b').timeit(number=N)
0.32039499282836914
Oui, c'est probablement plus facile à voir que d'essayer de l'expliquer avec des mots. +1
Le fait que f2 ne signifie plus que cela doit être exécuté plus longtemps. Parce que beaucoup de ces commandes ne sont invoqués qu'une seule fois. À propos de la réutilisation. Je pense que cela arrive à l'intérieur des fonctions écrites en C (dict, min, etc.), mais cela devine juste, j'aimerais en savoir plus s'il y a quelqu'un pour l'expliquer (Raymond Hettinger est la personne à écrire beaucoup de noyau Les structures de données Python, et si le dit qu'il y a une réutilisation, je pense qu'il y en a, car il connaît très bien des internes).
Je sais que la longueur ne signifie pas le temps d'excustion. Mais de mon point de vue, je peux voir f2 est plus lent. Plus d'appels de fonction, plus d'opérations. Et à propos de la réutilisation, je crois juste que le résultat que je reçois. En CPPHON, ID renvoie l'adresse de l'objet en mémoire. S'ils sont identiques, le résultat devrait être identique. @ Ovgolovin
J'ai mis à jour ma réponse. Peut être d'une certaine aide. J'espère que vous pouvez vérifier. @ovgolovin
Le démontage n'a pas de sens sans signification, car le vrai travail se produira à l'intérieur de l'appel à min , que vous ne pouvez pas voir là-bas. Tous les spectacles de démontage sont des trucs de configuration - il n'a aucune boucle.
Merci! Je pense que votre enquête met en lumière ce qui se passe là-bas.
Si nous utilisons dict au lieu de ordonnancier Différence horaire existe toujours, toujours pas ce dramatique (0.243047929276 et 0.327879101953 sur mon ordinateur). Ma seule hypothèse est que la conservation du tuple prend plus de temps que de récupérer du dictionnaire par clé.
En outre, il y a encore peut-être une allocation tuple sur chaque itération en deuxième solution.
Pour développer mon réponse précédente . Pour obtenir une meilleure vue de ce qui se passe, vous pouvez toujours utiliser DIS module.
>>> import dis
>>> dis.dis(f1)
0 LOAD_GLOBAL 0 (min)
3 LOAD_GLOBAL 1 (items)
6 LOAD_CONST 1 ('key')
9 LOAD_GLOBAL 1 (items)
12 LOAD_ATTR 2 (get)
15 CALL_FUNCTION 257
18 RETURN_VALUE
>>> dis.dis(f2)
0 LOAD_GLOBAL 0 (min)
3 LOAD_GLOBAL 1 (items)
6 LOAD_ATTR 2 (iteritems)
9 CALL_FUNCTION 0
12 LOAD_CONST 1 ('key')
15 LOAD_GLOBAL 3 (itemgetter)
18 LOAD_CONST 2 (1)
21 CALL_FUNCTION 1
24 CALL_FUNCTION 257
27 LOAD_CONST 3 (0)
30 BINARY_SUBSCR
31 RETURN_VALUE
Les différences de performance sont principalement causées par ordonnancierddict code>. de
CommandéDict Code> Utilise dict code> 'S Obtenez code> et __ getItem __ code>, mais redéfini son propre __ iter __ code> et iteritems code> . min
2.44175265292 <-- lookup is slow
2.76424538594 <-- lookup is slow
2.26508627493 <-- lookup is slow
0.199363955475
traverse
0.200654482623
2.59635966303 <-- lookup is slow
0.0454684184722
0.0733798569371
La deuxième solution est-elle plus rapide pour xs = [(aléatoire (), aléatoire (), aléatoire ()) pour x dans la plage (1000000)] car la prise de hachage pour flotteur est plus lente (tandis que pour le hachage d'intenseur est généralement INT)?
@ovgolovin, tu as raison. Il calcule les valeurs de hachage qui ont ralenti la première solution dans ce cas. La collision de hachage rendrait la première solution plus lente aussi plus.
Merci! Je pense que commandeddict peut être implémenté de manière meilleure: pas par sous-classement dict , mais en ayant dict et Liste des sublistes , avec dict mappage clé à subliste dans la liste , chaque subliste contenant Key-Valeur < / code> paires. Ensuite, l'itération peut être effectuée sans recherches dictionnaires simplement en parcourant la liste . Et il préférerait être mis en œuvre dans C, évitant ainsi de garder les clés dans dict et comme les premiers éléments de la liste , car la corbeille peut être dirigée directement sur [Touche, Value] Sublistes Dans la liste au lieu de la touche .