I've been unable to find a source for this information, short of looking through the Python source code myself to determine how the objects work. Does anyone know where I could find this online?
Checkout the TimeComplexity page on the py dot org wiki. It covers set/dicts/lists/etc at least as far as time complexity goes.
Raymond D. Hettinger does an excellent talk (slides) 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.
Here is a summary of my notes on list
:
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.range(n)
, map()
, list()
, [None] * n
, and slicing.realloc
ed only when it is wasting 50% of space. pop
is cheap.If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With