Où puis-je trouver le temps et l'espace de la complexité des types de séquence dans Python
-
09-06-2019 - |
Question
J'ai été incapable de trouver une source pour cette information, court de regarder à travers le code source Python moi-même afin de déterminer la façon dont les objets de travail.Quelqu'un sait-il où je pourrais trouver cette ligne?
La solution
La caisse de la TimeComplexity page sur le py dot org wiki.Il couvre l'ensemble/dicts/lists/etc au moins autant que le temps de la complexité va.
Autres conseils
Raymond D.Hettinger n' un excellent parler (les diapositives) à propos de Python intégré dans les collections appelé "Core Python des Conteneurs Sous le Capot".La version que j'ai vu porté principalement sur l' set
et dict
, mais list
était trop couverts.
Il y a aussi quelques photos de la pertinence des diapositives à partir de EuroPython dans un blog.
Voici un résumé de mes notes sur list
:
- Stocke les éléments dans un tableau de pointeurs.Indice des coûts de O(1) fois.Ajouter les coûts d'amorti O(1) fois.Insérez les coûts de O(n) fois.
- Essaie d'éviter
memcpy
lors de la croissance par la sur-allocation.Beaucoup de petites listes de déchets de beaucoup d'espace, mais les grandes listes ne perdez pas plus d'environ 12,5% de la surutilisation. - Certaines opérations de pré-taille.Les exemples donnés ont été
range(n)
,map()
,list()
,[None] * n
, et de le trancher. - Lors de la réduction, le tableau est
realloc
ed seulement quand il perd 50% de l'espace.pop
est bon marché.
Si vous demandiez à ce que j'en pense votre demande, vous pouvez trouver Ici...page 476 et sur.
Il est écrit autour de techniques d'optimisation pour Python;C'est surtout le Big-O notation des échéanciers pas beaucoup de mémoire.