Les clés du dictionnaire Python. "Dans" la complexité
question rapide pour satisfaire principalement ma curiosité sur le sujet.
<!-Je suis en train d'écrire de gros programmes python avec un backend de base de données SQlite et j'aurai affaire à un grand nombre d'enregistrements dans le futur, donc j'ai besoin d'optimiser autant que je peux.pour quelques fonctions, je cherche des clés dans un dictionnaire. J'ai utilisé le mot-clé" in "pour le prototypage et je prévoyais de revenir en arrière et d'optimiser ces recherches plus tard comme je sais que le mot-clé" in " est généralement O (n) (comme cela se traduit par Python itérant sur une liste entière et comparant chaque élément). Mais, comme un python dict est fondamentalement juste une carte de hachage, est l'interpréteur de python assez intelligent pour interpréter:
if(key in dict.keys()):
...code...
à:
if(dict[key] != None):
...code...
il s'agit essentiellement de la même opération mais le haut serait O(n) et le bas serait O(1).
il est facile pour moi d'utiliser la version du bas de mon code, mais alors j'étais juste curieux et j'ai pensé que je demanderais.
4 réponses
tout d'Abord, key in d.keys() est garanti pour vous donner la même valeur que key in d pour toute dict d.
Et in opération sur un dict ou dict_keys objet que vous recevez à partir de l'appelant keys() (dans 3.x), est O(N), O(1).
il n'y a pas de véritable "optimisation" en cours; c'est juste que l'utilisation du hachage est la façon évidente d'implémenter __contains__ sur une table de hachage, tout comme c'est la façon évidente de mettre en œuvre __getitem__.
vous pouvez demander où cela est garanti.
Eh bien, ce n'est pas le cas. Types De Cartographie définit dict comme, fondamentalement, une implémentation de table de hachage de collections.abc.Mapping. Il n'y a rien qui empêche quelqu'un de créer une implémentation de table de hachage D'un Mapping, mais fournissant toujours des recherches O(N). Mais ce serait un travail supplémentaire de faire une mise en œuvre aussi mauvaise, alors pourquoi le feraient-ils?
Si vous avez vraiment besoin de prouver il à vous-même, vous pouvez tester chaque implémentation que vous aimez (avec un profileur, ou en utilisant un type avec un __eq__ que les journaux d'appels, ou...), ou de lire la source.
en 2.x, vous ne voulez pas appeler keys, parce que cela génère un list les touches, au lieu d'un KeysView. Vous pouvez utiliser iterkeys, mais cela peut générer un itérateur ou autre chose qui n'est pas O(1). Donc, utilisez le dict lui-même comme un séquence.
même en 3.x, vous ne voulez pas appeler keys, car il n'y a pas besoin. En évoluant d'un dict, en vérifiant sa __contains__, et, en général, le traitant comme une séquence est toujours équivalent à faire la même chose à ses touches, alors pourquoi s'embêter? (Et bien sûr la construction du trivial KeyView, et l'accès à travers elle, allons ajouter quelques nanosecondes à votre temps de course et quelques touches de votre programme.)
(il n'est pas tout à fait clair que utiliser les opérations séquentielles est équivalent pour d.keys()/d.iterkeys() et d en 2.x. Autres que les problèmes de performance, ils équivalent dans toutes les implémentations de CPython, Jython, IronPython, et PyPy, mais il ne semble pas être indiqué où que ce soit dans la version 3.x. Et il n'a pas d'importance; il suffit d'utiliser key in d.)
Pendant que nous y sommes, notez que ceci:
if(dict[key] != None):
... ça ne va pas marcher. Si le key n'est pas dans le dict, ce va soulever KeyError, pas de retour None.
en outre, vous ne devriez jamais vérifier None== ou !=; toujours utiliser is.
Vous pouvez le faire avec un try-ou, plus simplement, ne if dict.get(key, None) is not None. Mais encore une fois, il n'y a aucune raison de le faire. En outre, cela ne traitera pas les cas où None est un bon point. Si c'est le cas, vous devez faire quelque chose comme sentinel = object(); if dict.get(key, sentinel) is not sentinel:.
Donc, la bonne chose à écrire est:
if key in d:
plus généralement, ce n'est pas vrai:
je sais que le "en" mot-clé est généralement de O(n) (car ce juste se traduit par python itération sur l'ensemble de la liste et de comparer chaque élément
in opérateur, comme la plupart des autres opérateurs, c'est juste un appel à un __contains__ méthode (ou l'équivalent pour un C/Java/.NET/RPython builtin). list l'implémente en itérant la liste et en comparant chaque élément; dict l'implémente en hashant la valeur et en regardant vers le haut; blist.blist le met en œuvre en marchant un arbre B+; etc. Aussi, il pourrait être O(n), O(1), O(log n), ou quelque chose de complètement différent.
En Python 2 dict.keys() crée d'abord la liste complète des touches, c'est pourquoi c'est un O(N) fonctionnement key in dict est un O(1) opération.
if(dict[key] != None) va soulever KeyError si la clé ne se trouve pas dans le dict, elle n'est donc pas équivalente au premier code.
Python 2 résultats:
>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 170 ns per loop
>>> %timeit 10000 in dic.keys()
100 loops, best of 3: 4.98 ms per loop
>>> %timeit 10000 in dic.iterkeys()
1000 loops, best of 3: 402 us per loop
>>> %timeit 10000 in dic.viewkeys()
1000000 loops, best of 3: 457 ns per loop
En Python 3 dict.keys() renvoie un objet view qui est plus rapide que Python 2 keys() mais encore plus lent simple normal key in dict:
Python 3 résultats:
>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 295 ns per loop
>>> %timeit 10000 in dic.keys()
1000000 loops, best of 3: 475 ns per loop
Utilisation:
if key in dict:
#code
La bonne façon de le faire serait
if key in dict:
do stuff
opérateur est O(1) pour les dictionnaires et met en python.