4 ms·
> Because lists are dynamically typed and heterogeneous, does that mean the underlying C is basically a contiguous segment of memory of python object references
by eatitraw 8y ago
> Because lists are dynamically typed and heterogeneous, does that mean the underlying C is basically a contiguous segment of memory of python object references?
Yep, it is an array of pointers: https://github.com/python/cpython/blob/3.7/Include/listobject.h#L23 https://github.com/python/cpython/blob/3.7/Include/listobjec...
> And when the list needs to be resized and doubles itself, it's just doubling the space for object references?
Basically yes. The growth pattern is not as aggressive as doubling though: https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L55 https://github.com/python/cpython/blob/3.7/Objects/listobjec...
- Waterluvian 8y agoI keep forgetting just how readable cpython source is. I'm still mentally stuck in my beginner years, where it was all Greek to me. Thanks for sharing these links.
- mcguire 8y agoInteresting: "The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ..." What is the big-o amortized cost of using this pattern? Doubling has a easy proof that it's O(1) amortized.
- eatitraw 8y agoThe growth pattern is still exponential, instead of going x -> 2 * x, you go x -> 9/8 * x + 6. I think it should still be O(1) amortized, you just need to adjust your proof for doubling a bit.
- rurban 8y agoMathematically the best is not doubling but fibonacci. for the start doubling is used because it's much faster to compute.