Core Python Containers -- Under the Hood
Why Stack Overflow recommends it
Stack Overflow users link it when answering questions about the time and space complexity or internal storage of Python lists, dicts and sets.
Recommended by 4 people across 4 different months, 2008 to 2017.
What it is
A 2008 conference talk by Python core developer Raymond Hettinger that looks at how CPython implements its built-in containers, mainly list, dict and set. It covers memory layout, growth strategies and performance implications, and when to use each type.
What people said
Strong rec Will Harris · 2008-09 · Stack Overflow · on “Where can I find the time and space complexity of the built-in sequence types in Python”
Raymond D. Hettinger does an excellent talk [this video] ( slides [LINK] ) about Python's built-in collections called 'Core Python Containers - Under the Hood'. The version I saw focussed mainly on set and dict , but list was covered too. There are also some photos of the pertinent slides from EuroPython in a blog [LINK] . Here is a summary of my notes on list : Stores items as an array of pointers. Subscript costs O(1) time. Append costs amortized O(1) time. Insert costs O(n) time. Tries to avoid memcpy when growing by over-allocating. Many small lists will waste a lot of space, but large lists never waste more than about 12.5% to overallocation. Some operations pre-size. Examples given were ran
Recommends sunqiang · 2009-07 · Stack Overflow · on “How does Python store lists internally?”
from Core Python Containers: Under the Hood [LINK] List Implementation: Fixed-length array of pointers * When the array grows or shrinks, calls realloc() and, if necessary, copies all of the items to the new space source code: Include/listobject.h [LINK] and Objects/listobject.c [LINK] btw: here is the video [this video]
Recommends Alex Martelli · 2010-01 · Stack Overflow · on “Python lists with STL like interface”
Python's "lists" are not linked lists -- they're like Java ArrayList [LINK] s or C++'s std::vector s, i.e., in lower-level terms, a resizable compact array of pointers. A good "advanced tutorial" on such subjects is Hettinger's Core Python containers: under the hood [LINK] presentation (the video at the URL is of the presentation at an Italian conference, but it's in English; another, shorter presentation of essentially the same talk is here [this video] ). So the performance characteristics of Python lists are essentially those of C++'s std::vector : Python's .append , like C++'s push_back , is O(1), but insertion or removal "in the middle" is O(N). Consequently, keeping a list sorted (as can be
Recommends Raymond Hettinger · 2017-04 · Stack Overflow · on “Why are dict lookups always better than list lookups?”
The short answer is that lists use linear search and dicts use amortized O(1) search. In addition, dict searches can skip an equality test either when 1) hash values don't match or 2) when there is an identity match. Lists only benefit from the identity-implies equality optimization. Back in 2008, I gave a talk on this subject where you'll find all the details: [this video] Roughly the logic for searching lists is: for element in s: if element is target: # fast check for identity implies equality return True if element == target: # slower check for actual equality return True return False For dicts the logic is roughly: h = hash(target) for i in probe_sequence(h, len(table)): element = key_table[
Cites Pejvan · 2012-05 · Stack Overflow · on “Initialise a list to a specific length in Python”
In a talk about core containers internals in Python at PyCon 2012, Raymond Hettinger is suggesting to use [None] * n to pre-allocate the length you want. Slides available as PPT [LINK] or via Google [LINK] The whole slide deck is quite interesting. The presentation is available on YouTube [this video] , but it doesn't add much to the slides.
Cites vartec · 2013-09 · Stack Overflow · on “Memory, CPU, complexity tradeoffs for Python dict v. list with large 2D arrays”
Lists won't be particularly efficient for storing this data, because you take no advantage in the fact that it's sparse. Basically you'd have to create a list of 1024000 elements, initially set to None . Internally it'd be a vector or 1024000 pointers, 8-bytes each on 64-bit system. Once this list is created, accessing and setting particular cell will be O (1) operation. OTOH, dictionary is implemented as hash table. So you'll only need space for elements you've inserted. If you're dealing with sparse data it's better option. Inserts have amortized cost of O (1), access is obviously O (1) also. You can read more about these datastructures in PyCon presentation "Core Python Containers: under-