Où puis-je trouver le temps et l'espace de la complexité des types de séquence dans Python

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?

Answer 1

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.

Answer 2

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 realloced seulement quand il perd 50% de l'espace. pop est bon marché.

Answer 3

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.