4 ms·

Show HN: Inside Python Dict – an explorable explanation

111 points by eatitraw 8y ago

deepakg 8y ago
Related: https://pyvideo.org/pycon-us-2017/modern-python-dictionaries-a-confluence-of-a-dozen-great-ideas.html https://pyvideo.org/pycon-us-2017/modern-python-dictionaries...
stinos 8y ago
Python lists are actually arrays — contiguous chunks of memory. Just wondering here, is this guaranteed to always be the case? Practically it probably is, but does the Python spec (as in: the laguage, not one of it's implementations) say a list must be implemented using contiguous memory of slots with Python objects? That seems so low-level and C-ish. Or does the OP actually mean CPython here for instance?
- lozenge 8y ago
  Python doesn't really have a spec in the way that, say, C# does. The docs are missing things like whether the argument is positional-only, exact exceptions raised in all cases, and time complexity of common operations. That said, I think every implementation uses contiguous memory. PyPy has list "strategies" int[], double[] and PyObject[] and probably more, switching transparently between them.
  - mlthoughts2018 8y ago
    With numba or other jit tools in CPython, you have things equivalent to pypy list strategies as well. If you add jitted helper functions or Cython, you have even more control.
- chrisseaton 8y ago
  It seems like a reasonable shorthand to say that Python does something, but to really mean that CPython happens to be implemented to do it that way.
- eatitraw 8y ago
  It is indexable, and it is used as an array, so I guess it is an array in all implementations. But good point, I should check this. Dicts are definktely implemented differently in different implementations, and I mention this.
- johnisgood 8y ago
  According to this post: https://news.ycombinator.com/item?id=18707403 https://news.ycombinator.com/item?id=18707403, "Lists aren't called arrays in Python because they're not arrays. Next!". I really am confused now. Is it an array, or is it not?
  - joatmon-snoo 8y ago
    Strictly speaking, lists are not arrays. I'm not aware of what the specification for a list would be, this is the closest I'm aware of: https://docs.python.org/3/reference/datamodel.html#objects-values-and-types https://docs.python.org/3/reference/datamodel.html#objects-v..., 3.2 > Sequences > Mutable Sequences > Lists, "The items of a list are arbitrary Python objects. Lists are formed by placing a comma-separated list of expressions in square brackets" CPython implementation is here: https://github.com/python/cpython/blob/e42b705188271da108de42b55d9344642170aa2b/Include/listobject.h#L23-L40 https://github.com/python/cpython/blob/e42b705188271da108de4... If I'm talking about arrays with someone else, I would expect us to be thinking of arrays in the sense of C. Both C++ and Java use the same definition. Other languages that I'm aware of (e.g. Javascript, Go) have their own notions of arrays that you can't conflate with the C notion of an array. From the C11 spec, §6.2.5.20: "An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type."
    - webmaven 8y ago
      Lists are very often used in the way arrays are, though. The heterogeneous use-case (that in C, etc. is usually a struct) is often filled by either tuples or (ordered) dictionaries in Python. If you really want something a bit closer to a C array, you can fairly easily create a UserList that enforces the non-empty requirement and only allows items of a particular type.
      - dorfsmay 8y ago
        If you want some closer to C arrays, you can use Python array.array, which is part of the standard library. https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html https://stackoverflow.com/questions/176011/python-list-vs-array-when-to-use https://stackoverflow.com/questions/176011/python-list-vs-ar...
- black-tea 8y ago
  It's not implemented like that and couldn't be. They aren't arrays unless you consider them arrays of pointers but this isn't a useful definition in Python. An array contains a number of elements of the same size. That means you can find the memory address of any element by simple arithmetic: array_loc + index * element_size. Python lists can contain objects of any type and the objects can't be found using arithmetic like that.
- mcguire 8y ago
  Does Python actually have a spec? AFAIK, it's always been "what CPython does." IIRC, an old joke was that Python lists are arrays and Perl arrays are lists.
whoisnnamdi 8y ago
Thanks. Slowing realizing some of the benefits of dicts and trying to use them more in my code where I would have otherwise defaulted to another data structure. They really are quite useful and intuitive to work with once you understand basic structure I do sometimes worry about speed relative to other options though, especially in large chunks of data

111 points by eatitraw 8y ago

Related: https://pyvideo.org/pycon-us-2017/modern-python-dictionaries-a-confluence-of-a-dozen-great-ideas.html https://pyvideo.org/pycon-us-2017/modern-python-dictionaries...

stinos 8y ago

Python lists are actually arrays — contiguous chunks of memory. Just wondering here, is this guaranteed to always be the case? Practically it probably is, but does the Python spec (as in: the laguage, not one of it's implementations) say a list must be implemented using contiguous memory of slots with Python objects? That seems so low-level and C-ish. Or does the OP actually mean CPython here for instance?

lozenge 8y ago
Python doesn't really have a spec in the way that, say, C# does. The docs are missing things like whether the argument is positional-only, exact exceptions raised in all cases, and time complexity of common operations. That said, I think every implementation uses contiguous memory. PyPy has list "strategies" int[], double[] and PyObject[] and probably more, switching transparently between them.
- mlthoughts2018 8y ago
  With numba or other jit tools in CPython, you have things equivalent to pypy list strategies as well. If you add jitted helper functions or Cython, you have even more control.
chrisseaton 8y ago
It seems like a reasonable shorthand to say that Python does something, but to really mean that CPython happens to be implemented to do it that way.
eatitraw 8y ago
It is indexable, and it is used as an array, so I guess it is an array in all implementations. But good point, I should check this. Dicts are definktely implemented differently in different implementations, and I mention this.
johnisgood 8y ago
According to this post: https://news.ycombinator.com/item?id=18707403 https://news.ycombinator.com/item?id=18707403, "Lists aren't called arrays in Python because they're not arrays. Next!". I really am confused now. Is it an array, or is it not?
- joatmon-snoo 8y ago
  Strictly speaking, lists are not arrays. I'm not aware of what the specification for a list would be, this is the closest I'm aware of: https://docs.python.org/3/reference/datamodel.html#objects-values-and-types https://docs.python.org/3/reference/datamodel.html#objects-v..., 3.2 > Sequences > Mutable Sequences > Lists, "The items of a list are arbitrary Python objects. Lists are formed by placing a comma-separated list of expressions in square brackets" CPython implementation is here: https://github.com/python/cpython/blob/e42b705188271da108de42b55d9344642170aa2b/Include/listobject.h#L23-L40 https://github.com/python/cpython/blob/e42b705188271da108de4... If I'm talking about arrays with someone else, I would expect us to be thinking of arrays in the sense of C. Both C++ and Java use the same definition. Other languages that I'm aware of (e.g. Javascript, Go) have their own notions of arrays that you can't conflate with the C notion of an array. From the C11 spec, §6.2.5.20: "An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type."
  - webmaven 8y ago
    Lists are very often used in the way arrays are, though. The heterogeneous use-case (that in C, etc. is usually a struct) is often filled by either tuples or (ordered) dictionaries in Python. If you really want something a bit closer to a C array, you can fairly easily create a UserList that enforces the non-empty requirement and only allows items of a particular type.
    - dorfsmay 8y ago
      If you want some closer to C arrays, you can use Python array.array, which is part of the standard library. https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html https://stackoverflow.com/questions/176011/python-list-vs-array-when-to-use https://stackoverflow.com/questions/176011/python-list-vs-ar...
black-tea 8y ago
It's not implemented like that and couldn't be. They aren't arrays unless you consider them arrays of pointers but this isn't a useful definition in Python. An array contains a number of elements of the same size. That means you can find the memory address of any element by simple arithmetic: array_loc + index * element_size. Python lists can contain objects of any type and the objects can't be found using arithmetic like that.
mcguire 8y ago
Does Python actually have a spec? AFAIK, it's always been "what CPython does." IIRC, an old joke was that Python lists are arrays and Perl arrays are lists.

whoisnnamdi 8y ago

Thanks. Slowing realizing some of the benefits of dicts and trying to use them more in my code where I would have otherwise defaulted to another data structure. They really are quite useful and intuitive to work with once you understand basic structure I do sometimes worry about speed relative to other options though, especially in large chunks of data