4 ms·

One 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

One 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 ago
If 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 ago
  But if you're in the real world you use numpy.ndarray instead (this underpins half of the Python ecosystem, more or less).
seiferteric 5y ago
Does 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 ago
  This breaks O(1) access by index, because the objects in the list may have different sizes.
killingtime74 5y ago
For 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 ago
  Python 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 ago
    They 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.
    - abecedarius 5y ago
      The times I've used array, it was a common data structure for communicating with a C extension. You could use a Python list, but that's not just slower but more of a pain to deal with on the C side. (This was before numpy was everywhere; I don't know how much fun that might be to work with from C.) If you're going pure Python then space is a better reason than speed. I'm not sure an array is even as fast as a list.
      - uranusjr 5y ago
        I think I use struct much more when interfacing with C, but I can see array being useful for arrays specifically when you expect more than a couple of elements. Both are still quite niche though.
  - kgm 5y ago
    The standard array module was more relevant in the distant past, before version 2.6 added the bytearray type. Otherwise, numpy arrays are considerably more useful in virtually every circumstance.
  - edgyquant 5y ago
    I had never heard of them and when I try to Google Python array v set speed it just returns list v set. I did get the official documentation but it doesn’t go into speed.
mark-r 5y ago
In CPython at least, there's no other way. Everything is an object, even simple types like integers. And references to objects are implemented with pointers. Even a Numpy array which stores a contiguous array of simple values requires conversion to an object when you actually try to use those values.
bjoli 5y ago
On a similar note: Has cpython implemented tagged pointers yet? I remember there being a lot more discussion about boxed types when Java sometimes boxed primitive types (at the expense of performance). Why python gets away with it I don't know. Back when I still did python, integers below 256 and above -3 (?) were "cached" and had no boxing overhead. In 3.6 that was still the case. Either cpython lacks tagged pointers or has the worst tagging scheme in history.

Znafon 5y ago

If 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 ago
But if you're in the real world you use numpy.ndarray instead (this underpins half of the Python ecosystem, more or less).

seiferteric 5y ago

Does 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 ago
This breaks O(1) access by index, because the objects in the list may have different sizes.

killingtime74 5y ago

For 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 ago
Python 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 ago
  They 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.
  - abecedarius 5y ago
    The times I've used array, it was a common data structure for communicating with a C extension. You could use a Python list, but that's not just slower but more of a pain to deal with on the C side. (This was before numpy was everywhere; I don't know how much fun that might be to work with from C.) If you're going pure Python then space is a better reason than speed. I'm not sure an array is even as fast as a list.
    - uranusjr 5y ago
      I think I use struct much more when interfacing with C, but I can see array being useful for arrays specifically when you expect more than a couple of elements. Both are still quite niche though.
- kgm 5y ago
  The standard array module was more relevant in the distant past, before version 2.6 added the bytearray type. Otherwise, numpy arrays are considerably more useful in virtually every circumstance.
- edgyquant 5y ago
  I had never heard of them and when I try to Google Python array v set speed it just returns list v set. I did get the official documentation but it doesn’t go into speed.

mark-r 5y ago

In CPython at least, there's no other way. Everything is an object, even simple types like integers. And references to objects are implemented with pointers. Even a Numpy array which stores a contiguous array of simple values requires conversion to an object when you actually try to use those values.

bjoli 5y ago

On a similar note: Has cpython implemented tagged pointers yet? I remember there being a lot more discussion about boxed types when Java sometimes boxed primitive types (at the expense of performance). Why python gets away with it I don't know. Back when I still did python, integers below 256 and above -3 (?) were "cached" and had no boxing overhead. In 3.6 that was still the case. Either cpython lacks tagged pointers or has the worst tagging scheme in history.