6 ms·

Dicts are UNORDERED associative containers. If youre depending your app on implementation defined behavior, that's on your developpers shoulders. Stuff like tha

Dicts are UNORDERED associative containers. If youre depending your app on implementation defined behavior, that's on your developpers shoulders. Stuff like that shouldn't pass code review

jstimpfle 9y ago
It is surprising though that the order was non-deterministic, not only undefined. Determinism is something I intuitively expect from read-only operations like iteration.
- fyi1183 9y ago
  Non-determinism comes from randomness in the hash function. I don't know the details of the Python implementation, but generally you want randomness at the very least when processing potentially hostile user input. Otherwise your code is susceptible to a denial of service attack where the attacker sends data that was crafted to maximize hash collisions, to break the expected performance of hash tables. From a theoretical angle, the only way to build hash tables with some kind of provable runtime guarantees is to include randomness.
- brett40324 9y ago
  It is simply that a python dict is not a list (read array).
- StavrosK 9y ago
  I think that's a habit you need to shake. If something is undefined, you should intuitively shy away from expecting things from it. If I found myself wondering why some undefined behavior was not consistent, I'd question why I even believed it should be consistent in the first place.
  - ridiculous_fish 9y ago
    Would you expect that `str(some_dict) == str(some_dict)`?
    - StavrosK 9y ago
      No, of course not. Some order has to be applied to serialize it to a string, but that order is not defined between calls.
      - eesmith 9y ago
        Python long ago made the guarantee that: > Keys and values are iterated over in an arbitrary order which is non-random, varies across Python implementations, and depends on the dictionary’s history of insertions and deletions. If keys, values and items views are iterated over with no intervening modifications to the dictionary, the order of items will directly correspond. That is, the order will be maintained between calls, so long as the dictionary had not been modified. Going back to "str(some_dict) == str(some_dict)". I would not expect to always be the same, but for entirely different reasons. Consider: class Strange(): def __repr__(self): import random return str(random.random()) some_dict = {1: Strange()} >>> str(some_dict) == str(some_dict) False
        StavrosK 9y ago
        A section called "CPython implementation detail" looks like the very antithesis of a guarantee, to me.
        eesmith 9y ago
        My apologies. I looked for the answer I knew was there, and quoted the wrong section because it matched what I was looking for. I should have quoted the next section: > If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are called with no intervening modifications to the dictionary, the lists will directly correspond. Curiously, the "Dictionary view objects" section at https://docs.python.org/2.7/library/stdtypes.html#dictionary-view-objects https://docs.python.org/2.7/library/stdtypes.html#dictionary... has the same "Keys and values are iterated over in an arbitrary order which is non-random ..." text, but without being inside of a "CPython implementation detail" box.
- ubernostrum 9y ago
  See this comment for the details: https://news.ycombinator.com/item?id=16307007 https://news.ycombinator.com/item?id=16307007
djrobstep 9y ago
Not for much longer, as of 3.7 the ordering is a language feature: https://mail.python.org/pipermail/python-dev/2017-December/151283.html https://mail.python.org/pipermail/python-dev/2017-December/1... It's mad that it ever wasn't this way. Mapping-with-ordered-keys is such a useful and pervasive data structure (all database query result rows, for one) that an ordered dictionary should be a fundamental part of a language. It has been so much more pleasant to write python since ordering was maintained by default.
- Avshalom 9y ago
  >>(all database query result rows, for one) What? No. SQL does not return results in any consistent ordering unless specifically instructed to.
  - djrobstep 9y ago
    Not the result set, the rows of the result set.
    - icedchai 9y ago
      Unless there is an "order by" clause, the order of rows in the result set is undefined and non-deterministic from query to query.
      - djrobstep 9y ago
        As I said: > Not the result set, the rows of the result set. Each row is a mapping with ordered keys.
        icedchai 9y ago
        Perhaps you are confused and mean "columns"? ("Rows of the result set" is what I was referring to.) A result set has rows, which are not in a deterministic order unless an "order by" is provided. Each row has columns. The columns are in order, obviously.
otempomores 9y ago
Shoulda woulda coulda.. then the mob carried him away. Srsly look at js.. How many bugs and fast first solutions are syntactic sugar by now.. Its just temp O' Rary until sth better comes along always becomes the default behavior.
doug1001 9y ago
agree completely aside from that, python has a separate ordered dict class

Dicts are UNORDERED associative containers. If youre depending your app on implementation defined behavior, that's on your developpers shoulders. Stuff like that shouldn't pass code review

jstimpfle 9y ago

It is surprising though that the order was non-deterministic, not only undefined. Determinism is something I intuitively expect from read-only operations like iteration.

fyi1183 9y ago
Non-determinism comes from randomness in the hash function. I don't know the details of the Python implementation, but generally you want randomness at the very least when processing potentially hostile user input. Otherwise your code is susceptible to a denial of service attack where the attacker sends data that was crafted to maximize hash collisions, to break the expected performance of hash tables. From a theoretical angle, the only way to build hash tables with some kind of provable runtime guarantees is to include randomness.
brett40324 9y ago
It is simply that a python dict is not a list (read array).
StavrosK 9y ago
I think that's a habit you need to shake. If something is undefined, you should intuitively shy away from expecting things from it. If I found myself wondering why some undefined behavior was not consistent, I'd question why I even believed it should be consistent in the first place.
- ridiculous_fish 9y ago
  Would you expect that `str(some_dict) == str(some_dict)`?
  - StavrosK 9y ago
    No, of course not. Some order has to be applied to serialize it to a string, but that order is not defined between calls.
    - eesmith 9y ago
      Python long ago made the guarantee that: > Keys and values are iterated over in an arbitrary order which is non-random, varies across Python implementations, and depends on the dictionary’s history of insertions and deletions. If keys, values and items views are iterated over with no intervening modifications to the dictionary, the order of items will directly correspond. That is, the order will be maintained between calls, so long as the dictionary had not been modified. Going back to "str(some_dict) == str(some_dict)". I would not expect to always be the same, but for entirely different reasons. Consider: class Strange(): def __repr__(self): import random return str(random.random()) some_dict = {1: Strange()} >>> str(some_dict) == str(some_dict) False
      - StavrosK 9y ago
        A section called "CPython implementation detail" looks like the very antithesis of a guarantee, to me.
        eesmith 9y ago
        My apologies. I looked for the answer I knew was there, and quoted the wrong section because it matched what I was looking for. I should have quoted the next section: > If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are called with no intervening modifications to the dictionary, the lists will directly correspond. Curiously, the "Dictionary view objects" section at https://docs.python.org/2.7/library/stdtypes.html#dictionary-view-objects https://docs.python.org/2.7/library/stdtypes.html#dictionary... has the same "Keys and values are iterated over in an arbitrary order which is non-random ..." text, but without being inside of a "CPython implementation detail" box.
ubernostrum 9y ago
See this comment for the details: https://news.ycombinator.com/item?id=16307007 https://news.ycombinator.com/item?id=16307007

djrobstep 9y ago

Not for much longer, as of 3.7 the ordering is a language feature: https://mail.python.org/pipermail/python-dev/2017-December/151283.html https://mail.python.org/pipermail/python-dev/2017-December/1... It's mad that it ever wasn't this way. Mapping-with-ordered-keys is such a useful and pervasive data structure (all database query result rows, for one) that an ordered dictionary should be a fundamental part of a language. It has been so much more pleasant to write python since ordering was maintained by default.

Avshalom 9y ago
>>(all database query result rows, for one) What? No. SQL does not return results in any consistent ordering unless specifically instructed to.
- djrobstep 9y ago
  Not the result set, the rows of the result set.
  - icedchai 9y ago
    Unless there is an "order by" clause, the order of rows in the result set is undefined and non-deterministic from query to query.
    - djrobstep 9y ago
      As I said: > Not the result set, the rows of the result set. Each row is a mapping with ordered keys.
      - icedchai 9y ago
        Perhaps you are confused and mean "columns"? ("Rows of the result set" is what I was referring to.) A result set has rows, which are not in a deterministic order unless an "order by" is provided. Each row has columns. The columns are in order, obviously.

otempomores 9y ago

Shoulda woulda coulda.. then the mob carried him away. Srsly look at js.. How many bugs and fast first solutions are syntactic sugar by now.. Its just temp O' Rary until sth better comes along always becomes the default behavior.

doug1001 9y ago

agree completely aside from that, python has a separate ordered dict class