views:

272

answers:

3

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?

+2  A: 

If your asking what I think your asking, you can find them Here. Page 476 and on.

It's written around optimization techniques for python, It's mostly Big-O notation of time efficiencies not much memory.

Hope it still helps.

Brian Gianforcaro

Brian Gianforcaro
+3  A: 

Raymond D. Hettinger does an excellent talk 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.

I haven't found a video of the talk online yet, but there are some photos of the pertinent slides from EuroPython in a blog.

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 range(n), map(), list(), [None] * n, and slicing.
  • When shrinking, the array is realloced only when it is wasting 50% of space. pop is cheap.
Will Harris
Thanks, I just tried to find it and, for reference, the talk is now available on YouTube – http://youtube.com/watch?v=hYUsssClE94
Jeremy Banks
+7  A: 

Checkout the TimeComplexity page on the py dot org wiki. It covers set/dicts/lists/etc at least as far as time complexity goes.

Aaron Maenpaa