5 ms·
How Python List Works
- TrapLord_Rhodo 5y agoDoes anyone know any good resources for learning more about algorithm times like O(1) and O(n)?
- ganlay 5y agoThe item count is stored separately so that the len() function also performs in O(1) time, and does not have to count the elements each time. Could you kindly explain this part in detail?
- nayuki 5y agoHow a Python list really works? See the underlying C implementation: https://github.com/python/cpython/blob/main/Objects/listobject.c https://github.com/python/cpython/blob/main/Objects/listobje... ; https://github.com/python/cpython/blob/main/Include/listobject.h https://github.com/python/cpython/blob/main/Include/listobje... For comparison, java.util.ArrayList is implemented in Java itself, and is much shorter: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/ArrayList.java http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/...
- azinman2 5y agoYa I was reading this thinking none of this is telling me how CPython implements it. It’s just a poor-man’s version.
- matthias509 5y agoOne point which I think bears mentioning with respect to performance is that even with O(1) access, the performance in the real world of a list implemented by a list of pointers vs a contiguous block of memory will be very different. This is because programs often iterate over lists and a list implemented by a contiguous block of ram will have MUCH better cache locality. AFAIK, this unfortunately wouldn’t be possible to implement in Python though because I don’t think there would be any way to know how much space to allocate for each item in the list.
- Znafon 5y agoIf you have numeric value you can use https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html
- kzrdude 5y agoBut if you're in the real world you use numpy.ndarray instead (this underpins half of the Python ecosystem, more or less).
- seiferteric 5y agoDoes it have to be one or the other? You could allocate blocks of memory for the list then when it will be filled up you allocate more and add a pointer to it.
- dmurray 5y agoThis breaks O(1) access by index, because the objects in the list may have different sizes.
- killingtime74 5y agoFor more efficient "lists" there are Numpy arrays https://numpy.org/doc/stable/reference/generated/numpy.array.html https://numpy.org/doc/stable/reference/generated/numpy.array... which do have cache locality
- wodenokoto 5y agoPython does come with built-in arrays, but I've never seen them used, or heard anyone recommend them for anything. https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html
- uranusjr 5y agoThey are recommended when you want speed, but most people writing Python probably never need that much speed (or would probably want numpy anyway), and the few who do likely have more private sources to recommend it for specific occasions. It should probably be used for more things (instead of reaching for numpy at first chance) but is still a niche tool.
- arthurcolle 5y agoI always wondered why there weren't more 'hyper-collection' abstractions that just implement multiple collection types in one interface, so that you can get the respective speedups of the different collection types while still having the flexibility to use them as you wish
- ketralnis 5y agoC arrays are basically that. Also python dicts (most python types including all user-defined classes are actually dicts underneath), Lua tables, Javascript objects, and more. In most dynamically typed languages, "the" type is actually what you're calling a hyper-collection and not just conceptually, but also in implementation
- karmakaze 5y agoThis is the field of datastructures. There isn't 'just' one be-all to end-all. There are so many kinds of hashing/tables, trees/balancing, hybrid (e.g. skiplists), priority queues, etc. Because there are so many possible combinations, if the choices matter it's useful to use a language that lets you make your own. This is one of the main reasons why generics for Go is a big deal. Go always had generics, but it's only been for the built-ins array/slice, map, and channel. With user-defined generics any datastructures/interfaces can be conveniently made and used without language/library/compiler support. Its curious that for Python this is blog post material, but for Go it's intrinsic to understanding the performance and usage of slices or maps, or in Java (and other langs) would be referenced merely by the class name ArrayList. The fact that so much can be done effectively in Python without always having to think about such details is an achievement of the language and ecosystem of libraries and packages.
- beervirus 5y agoHow would that work? Every time you create an object, internally it creates one of everything?
- kgm 5y agoOne thing to note, in the gritty details of Python's actual implementation of the list type, is that there's a little more to say about how list resizing works than is immediately obvious. The relevant source is here: https://github.com/python/cpython/blob/main/Objects/listobject.c#L57-L77 https://github.com/python/cpython/blob/main/Objects/listobje... As the article points out, the size progression, as detailed in the comment in that source, is relatively modest. Your "classic" dynamic array will simply double the size as needed. This progression does less than that: 16, 24, 32, 40, and so on. But: The underlying implementation is using the standard C library function realloc(). This will perform some amount of in-place resizing on its own, and will lend a lot to the performance of a Python list, albeit in a way that might be difficult to nail down, since it depends on the overall usage of the C library's heap.
- Zababa 5y agoRelated to that, do heterogenous lists make sense as a default? I can see the argument for dictionaries easily, you might want to put a lot of different stuff inside one. However, for lists, I fail to see the advantages of heterogenous lists as a default. Especially since they are going to be way slower, and nobody seem to use arrays in Python.
- pdonis 5y ago> do heterogenous lists make sense as a default? Yes, because then the list object doesn't have to do any extra work to check the types of objects. If your application needs that extra checking, you can add it in your application's code; but there's no reason to burden the basic list object with extra code that not everyone needs. > Especially since they are going to be way slower Way slower than what? They're slower than Python arrays, of course, but Python arrays can only store numeric values (since the amount of space each value takes up is constant and known when the array is created). For a container that needs to be able to store objects of any type (including instances of user-defined classes), a heterogeneous list is faster than a homogeneous one, because, as above, it doesn't have to do extra work to check the types of objects. All the other extra work is there because the size in memory of the objects isn't known in advance; and that will be true even if all of the objects are of the same type, since instances still won't necessarily all have the same in-memory size (for example, consider instances of user-defined classes with different attributes).
- Zababa 5y ago> For a container that needs to be able to store objects of any type (including instances of user-defined classes), a heterogeneous list is faster than a homogeneous one, because, as above, it doesn't have to do extra work to check the types of objects. My question is about that. Is storing objects of any type a common use case, compared to storing objects of one type?
- dragonwriter 5y agoStoring objects of any size is common, because Python objects are rarely fixed size (Python integers aren't fixed size!) At that point, you need pointers anyway, so mixed type doesn't add much overhead. Especially given that you need to handle mixed concrete types even if you have single “typechecking” types because of inheritance (including via declared ABCs and union types.