Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Python dicts are now ordered

softwaremaniacs.org

Post reply on HN
Print view View original

191–200 of 457 posts

Re: Python dicts are now ordered

#191

Post by opportune »

alayne wrote: post #157
opportune wrote: post #133

Earlier quoted context omitted.

Imagine a trie implemented as a tree of dictionaries (ignore thinking about whether a tree of arrays may actually be better for now). Let’s say you want to implement an autocomplete algorithm based on a dictionary of words from a corpus. The autocomplete algorithm is naive: if a user types in “abc” you recommend whichever word starting in “abc” has the most occurrences in the corpus. With ordered dicts you can use th…

This isn't a sorted dictionary, it's an insertion order dictionary.

Well, you can convert any sorted dictionary to an insertion order dictionary by copying it over, but that does the make the original example pretty clunky.

I guess a better use case is if you needed some sort of priority/FIFO logic along with indexing. Hard to think of something that doesn’t feel contrived, but I guess imagine having a queue where determining membership or updating fields of an element based on ID can be done in O(1) for any element?

Re: Python dicts are now ordered

#192

Post by Arnavion »

dehrmann wrote: post #85
EGreg wrote: post #45

Earlier quoted context omitted.

PHP has had this undocumented feature since forever and so did all mainstream Javascript engines. Big whoop

> Javascript Javascript doesn't specify performance characteristics of objects and arrays, so even with implementations, one object could be a hashtable, another a balanced tree.

The implementation doesn't matter to EGreg's point, which is that ES standardized that iterating over object keys are generally required to return keys in insertion order.

In the past (from before this standardization) Chrome had in fact changed the object iteration order due to an optimization, and had to revert it after lots of complaining on their bug tracker.

(To be precise, the spec still requires array index properties to be returned ahead of other properties regardless of insertion order. The behavior that Chrome "reverted" to is this new one, so not exactly the same as the original behavior.)

Re: Python dicts are now ordered

#193

Post by maxnoe »

masklinn wrote: post #116
setr wrote: post #64

Earlier quoted context omitted.

Portability isn't affected; if they claim compatibility with python3.7, then they claim their dicts have insertion-ordered keys. If they claim compatibility with only up to python3.6, they can have whatever order they choose. The only issue with portability is that I think the main reason it was made a gaurantee is that cpython found the new, presumably optimized, implementation came with insertion order for free, so…

That also goes both way: Pypy defaulted to ordered dicts a few years before cpython did.

The insertion order dict implementation actually comes from pypy

Re: Python dicts are now ordered

#194

Post by strken »

harikb wrote: post #61
hprotagonist wrote: post #47

Earlier quoted context omitted.

If you know you're supporting old code, use OrderedDict. you arguably ought to anyway, for explicitness.

The trouble is I publish a (new) code that advertises itself as working on 3.x and then it turns out it is being used by a person who only had the version prior to this change. That said, Go made a similar change (from insertion-order to explicitly-randomized) and world didn’t end. So there’s that.

I thought Go made the change from undefined behaviour with an underlying implementation that was insertion order in a map with 8 or fewer entries, to similarly undefined behaviour with an implementation that randomised lookups in those cases. Any code that has ever relied on any kind of ordering in Go maps will almost certainly be wrong, even random ordering, because the distribution of the "random" ordering is biased.

See https://medium.com/i0exception/map-iteration-in-go-275abb76f...

Re: Python dicts are now ordered

#195

Post by yurlungur »

hprotagonist wrote: post #47
biddlesby wrote: post #26

Earlier quoted context omitted.

It doesn’t break existing code. Code written for Python 3.7 might break on older versions of Python

If you know you're supporting old code, use OrderedDict. you arguably ought to anyway, for explicitness.

Yeah I think this is probably my main issue. I don't think it's reasonable to ask users of your code to always use 3.7+ instead of 3.6 if they are usually expected to be compatible. And it's also unnecessary to break such compatibility for something like preferring dict over OrderedDict anyways. At least I would try to avoid any such issues by still using OrderedDict.

That said, I have no idea about the internals of dict. I assume no performance was sacrificed for this change.

Re: Python dicts are now ordered

#196

Post by _whiteCaps_ »

alayne wrote: post #164
_aleph2c_ wrote: post #144

This is an amazing contribution to the language. A mixture of speed and convenience, probably made by volunteers. As for people criticizing a change to what use to be a non-deterministic ordering of a dict iteration; I don't know what to say to them, other than, are you serious? There are people out there who are working for us, they work for free and they did some heavy lifting to give us this. They might read what…

Other languages don't generally have special order guarantees about standard maps. This seems very idiosyncratic.

Golang map iteration is returned in random order specifically to make sure that people don't rely on the order.

I think this feature says a lot about the philosophy of Python vs Go.

Re: Python dicts are now ordered

#198

Post by reubenmorais »

alayne wrote: post #164
_aleph2c_ wrote: post #144

This is an amazing contribution to the language. A mixture of speed and convenience, probably made by volunteers. As for people criticizing a change to what use to be a non-deterministic ordering of a dict iteration; I don't know what to say to them, other than, are you serious? There are people out there who are working for us, they work for free and they did some heavy lifting to give us this. They might read what…

Other languages don't generally have special order guarantees about standard maps. This seems very idiosyncratic.

std::map in C++ stores keys in order. You have to use std::unordered_map to not get that behavior.

Re: Python dicts are now ordered

#199

Post by xapata »

masklinn wrote: post #140
zurtex wrote: post #109

Earlier quoted context omitted.

No, OrderedDict has it's own C implementation which was created just before it was decided that dict would preserve order across iteration. Further there is a big difference, regular dict preserves order across iteration but OrderedDict treats order up to equality. I.e. this returns True: {1: 1, 2: 2} == {2: 2, 1: 1} Where as this returns False: OrderedDict({1: 1, 2: 2}) == OrderedDict({2: 2, 1: 1}) To make that diff…

Also ordereddicts provide methods to move items to the start or end, and remove items specifically at the start or end, not so for regular dicts.

dict has popitem for removing at the end. That used to be arbitrary, but now it (de facto) means last-inserted.

Re: Python dicts are now ordered

#200

Post by jonreem »

_aleph2c_ wrote: post #144

This is an amazing contribution to the language. A mixture of speed and convenience, probably made by volunteers. As for people criticizing a change to what use to be a non-deterministic ordering of a dict iteration; I don't know what to say to them, other than, are you serious? There are people out there who are working for us, they work for free and they did some heavy lifting to give us this. They might read what…

People who bother to complain are those who actually care about your thing. People who do not care simply leave without ever telling you why. Your complainers are often your most dedicated and invested users.
Post reply on HN