26 ms·
Python dicts are now ordered
- geophile 7y ago"Ordered dict" is ambiguous, and from the title I thought that key order was meant. Reading the article, I see that it's actually insertion order. Which makes much more sense. Key order would have been a much more significant change.
- _verandaguy 7y agoNot to mention there's often no meaningful way to order by key value since keys can be any hashable values -- so things like this break this idea: _dict = {} _dict.update({MyObject: 3}) _dict.update({'MyObject': 3}) There's no ordering over _most_ hashable values since they span multiple types, so insertion ordering is the only sane way to do it.
- Sharlin 7y agoWell, keys of sorted dictionaries don’t need to be hashable but do need an ordering, whether intrinsic or user-provided. A sorted map (usually implemented in terms of a binary search tree) is simply a separate data type with different requirements than a hash table based one.
- masklinn 7y agoA sorted map would be tree-based and require its keys to be orderable but not hashable. For instance Rust's HashMap has its key bound on Hash + Eq, while BTreeMap's is bound on Ord. They're different data structures, with different use cases and different requirements. > There's no ordering over _most_ hashable values since they span multiple types, so insertion ordering is the only sane way to do it. Python 2 actually had total ordering of all values. The result was usually stupid but it was there.
- _verandaguy 7y ago>The result was usually stupid but it was there This is what I meant by "sane" in my comment. It's _way_ more meaningful to the user if data's insertion-ordered.
- jiveturkey 7y agoIt's not ambiguous, because it refers to the long pre-existing OrderedDict class.
- geophile 7y agoYes, I see that, but the title is unclear.
- masklinn 7y ago> I thought that key order was meant. Surely that would be a sorted dict not an ordered dict.
- dmitriid 7y agoJavascript taught me to never assume any ordering in a dict/map/hashmap (whatever the term)
- pfdietz 7y agoIs the ordering there at least fixed, or can it vary from run to run even on the same data, or between implementations or versions of the same implementation? EDIT: to clarify, I was asking about JavaScript there.
- deleted 7y ago[deleted]
- nobleach 7y agoIt is deterministic, but it's an odd rule-set. For example: `var o = { 3: 'foo', 1: 'bar', b: 'baz', a: 'quux' }` Will yield: `{1: "bar", 3: "foo", b: "baz", a: "quux"}`. Numeric keys get sorted. String keys are insertion-order. If key order is a priority, a Map should be used instead. Often when JavaScript's objects are used and a particular sort order is required, an accompanying (sorted) array is used.
- japhyr 7y agoBrandon Rhodes gave a great talk at PyCon 2017 about the evolution of dictionaries in Python. I really appreciate the people who dive deep into these implementation details, and continue to optimize the languages we all use. https://www.youtube.com/watch?v=66P5FMkWoVU https://www.youtube.com/watch?v=66P5FMkWoVU
- kstrauser 7y agoI usually feel like a reasonably bright person, and then I go to a talk like this and suddenly remember how terribly much I don't (and will never) know. There are some very sharp people at play here.
- taeric 7y agoThis is a solid argument for why you should have more datatypes available to you. If your program relies on an insertion order, say so. If anyone ever moves to another implementation, they will thank you for it.
- Sean1708 7y agoIt's extra annoying because collections.OrderedDict has been in the standard library for ages.
- masklinn 7y agoI fail to see what's annoying how. OrderedDict provide features for manipulating ordering, but they are expensive and slower. dict initially became ordered as a consequence of implementation details changes, and that was considered useful enough (or likely enough to trigger compatibility issues with third party implementation) that the core team decided to standardise it rather than break it (one of the advantages of the new implementation is iteration performances, shuffling iteration would probably have slowed it back down more than the old implementation)
- taeric 7y agoAnnoying is that it is not obvious why the two exist, by their name. They are both ordered. One is orderable in that you can change is order. I would not guess that looking at this. For a language that prides itself on being readable, that is an amusing quirk.
- duckerude 7y agoOrdered dictionaries already existed as a separate type. Much of the gain was in the use of dicts for core language features. In particular, Python 3.6 guarantees that the order in which class attributes are defined is preserved, and that functions which take variadic keyword arguments receive them in the order in which they were passed. It permits other implementations to use types other than dict to accomplish that. Dataclasses make use of ordering of dictionaries in a subtle way. If you write: class Foo: bar: int baz: str Then Foo.__annotations__ is a dictionary {'bar': int, 'baz': str}. The @dataclass decorator transforms that into standard boilerplate, and it needs to know the order to do that.
- jkbbwr 7y agoAm I the only one that thinks this is a stupid decision? This will silently break code that starts to rely on this behaviour that gets executed on Python3.5 and lower. I would consider changing how a builtin works to be a major breaking change. It would have been fine if this was a change between 2 and 3 but on a minor version? Thats insane.
- kyrra 7y agoGo purposely "randomizes" order of a map when it's iterated over, which you can see running this demo: https://play.golang.org/p/DISpyv0Zuq_j https://play.golang.org/p/DISpyv0Zuq_j HN discussed this a little 6 years ago: https://news.ycombinator.com/item?id=7655948 https://news.ycombinator.com/item?id=7655948 As crawshaw pointed in that discussion, it helps catch people inadvertently relying on map order in tests or other places in their code.
- throwaway8291 7y agoThat surprised me, when I first saw it. If someone takes a minute to read the docs (e.g. Python), one would never build something knowing that order is not guaranteed (e.g. order in dictionaries). But seemingly people do.
- UncleEntity 7y agoHad some code break while porting from 2 to 3 because it assumed dict order and it was part of the official Python build system, the old spark parser for the AST module.
- ipsin 7y agoMore important (in my opinion), adding a random seed to your hash prevents collision attacks, where an attacker tries to ruin your performance by sending many values (e.g. HTTP params) that would hash to the same bucket.
- tomp 7y ago
- raymondh 7y agoThis 37 minute Pycon video covers the essential details of how Python dictionaries are implemented: https://www.youtube.com/watch?v=npw4s1QTmPg&t=3s https://www.youtube.com/watch?v=npw4s1QTmPg&t=3s
- dfox 7y agoI had firsthand experience with this otherwise useful feature masking an obvious bug. In one codebase there was function along the lines of (for calling into MSSQL with it's "peculiar" stored procedures): def call_stored_procedure(name, **args): cursor.call_proc(name, *args.values()) Of course this is obviously wrong and on Python 3.6 this will break horribly on first use, while in Python 3.7 this worked as long as the keyword arguments were in the correct order.
- doubleunplussed 7y agoOn 3.6 it will work, it's just relying on an implementation detail (dicts are ordered in 3.6, it's just that it is considered an implementation detail, not a guarantee)
- oefrha 7y agoNot sure why this is posted and upvoted to front page now. After all this is a major bullet point in py37 What’s New, and even py38 has been out for a while. Anyway, I’ll keep using collections.OrderedDict (except for personal scripts) until py35 EOL.
- gerikson 7y agoProbably because it was posted to lobste.rs and got good traction there: https://lobste.rs/s/htcz5f https://lobste.rs/s/htcz5f
- rcfox 7y agoI still see dict ordering as an implementation detail; not a technical one but a descriptive one. If you want to rely on insertion order, use collections.OrderedDict. It communicates your intention far better, and there should be no overhead.
- xapata 7y agoOrderedDict is less efficient. It's best to replace usage with basic dict where possible to improve efficiency. There is one obscure feature of OrderedDict that isn't in the basic, so it can't always be swapped.
- rcfox 7y agoReally? I would have figured they'd just do something like: class OrderedDict(dict): pass (Plus a little bit of API shimming.)
- zurtex 7y agoNo, 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 difference speedy it needs to be done on the C level.
- throwawaylolx 7y agoWhere "now" dates back to 2018? https://docs.python.org/3/whatsnew/3.7.html https://docs.python.org/3/whatsnew/3.7.html
- sfoley 7y agoEven further (2016) if you count the fact they were ordered as an implementation detail in CPython 3.6.
- throw18374 7y agoCame to say the same.. insertion order of dict has been here for years for 90+% of Python users (CPython implementation) and a part of the language spec also for almost as many years. I guess it’s good to spread awareness to HN readers who apparently were unaware, but the headline is very misleading.
- raziel2p 7y ago90% seems optimistic. I don't think that many Python projects are running the most recent version in production. From personal experience, upgrading to 3.7 was especially a pain because of packages that used "async" for variable/kwarg names.
- throw18374 7y agoThat’s a very good point, in that case even 50% would probably be optimistic. We can probably attribute this article’s novelty to the slow adoption of Python 3. In that way it’s probably a good thing that it’s such a popular topic, even if it is old news.
- faraggi 7y agoI've always thought this was a bit annoying in Python, good to know a (very) small itch is now scratched.
- Recursing 7y agoIt's been this way since python3.6 in 2016, so you really only have to worry about very old versions
- cal97g 7y agoThis is not new.. it's an implementation side affect as mentioned. Previous to this though the order was random according to a random string generated each time a python process launched; so you would get the same order in one process, and a different order when you restarted it.
- paulhodge 7y agoGreat decision IMO. I remember maintaining a bunch of Python code that we supported on both OSX and Windows. Out of all the platform-specific bugs we had (where it worked on one OS and not the other), one of the most common causes was code that relied on a certain key order. And we knew that relying on key order was bad, we're supposed to use things like OrderedDict, blah blah blah. It was still a really easy mistake to make, just like it's really easy to have memory safety bugs in C. At some point, if a human error is common enough, it makes pragmatic sense to change the design so the error is impossible.
- rob74 7y agoThe Go designers went the other way (as they often do): > When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next. Actually it is not only "not guaranteed to be the same", the runtime actively makes sure that the iteration order is actually different so you don't even start to rely on it...
- tele_ski 7y agoThat seems like it would be a performance hit to actively make it different? That seems like a very weird and strange design decision if true
- TheNorthman 7y agoIt actually doesn't make that much of a difference. See this commit for actual benchmarks about the impact: https://github.com/golang/go/commit/3be4d95731a17073afb1f69bde264eecbdfa32bb https://github.com/golang/go/commit/3be4d95731a17073afb1f69b...
- dallbee 7y agoIt is a performance hit and I initially had the same reservations. Importantly, the implementation imposes a small overhead on the access time of iteration over a map, but not in a way which changes the scaling behavior. Other map operations are not implicated. I think the decision was wise - it prevents user code from relying on ordered iteration behavior, which allows the go team to switch to different map implementations without fear of breaking user code. If the order had been unspecified, but iteration was still ordered in practice, there'd undoubtedly be (incorrect) user code that relied on that behavior. Amusingly, I now run into engineers who are under the misconception that map iteration is random, and proceed to use maps as an RNG. That's an unfortunate mistake because Go's map iteration is quite non-uniform - it's shuffled just enough to appear random to the untrained eye, while be performant.
- dehrmann 7y agoI've written a lot of Python, but more Java. This is where I have a gripe with "batteries included." In Java, I'd have to think slightly about this, then use a LinkedHashMap. It's been in Java since *2002. It also has a Set flavor. Python just doesn't have as rich of a collection of included data structures, and the APIs are more limited.
- masklinn 7y agoWhat java calls linkedhashmap, Python calls ordereddict. It's not quite as old as java's linkedhashmap but is no spring chicken either (it's a bit above 10 years old).
- dehrmann 7y agoWhere's orderedset, though?
- masklinn 7y agoNowhere because so far the core team has remained unconvinced. People have brought up replacing standard set implementation by a variant of dict's (even expressing surprise that that wasn't already the case) but no dice yet. There are discussions on the subject on python-dev once in a while e.g. https://mail.python.org/pipermail/python-dev/2019-February/156466.html https://mail.python.org/pipermail/python-dev/2019-February/1...
- TylerE 7y agoOrderedDict has existed in python since 2.7, released in 2009.
- Igelau 7y agoI agree, and I think it's troublesome that dict now means something more specialized than it did before and the language doesn't communicate this. The dict is dead, long live the dict. I suspect it's the result of my Java goggles, because the distaste comes from a sense that this is analagous to if the Map interface suddenly always meant LinkedHashMap.
- zackmorris 7y agoI'm glad to see other languages finally catching up to PHP. I'm joking (kind of) but after a lot of years of doing this, I've begun de-prioritizing pure abstractions and favoring the way that humans tend to do things on their own. Technically this is along the lines of the worse-is-better philosophy. The single biggest cost in software development is friction. Performance, size, etc are all less important, because they become less important with each passing year as computers grow more powerful. And along those lines, I think that silly concepts like assigning letter names to drives in Windows, or having a paltry few registers in x86, made those architectures more accessible to the masses than the more generalized Unix and Mac platforms. Not that I completely agree with that, just, it's all I can come up with (other than cost and familiarity) for why people are so attached to worse-is-better paradigms. Preserving insertion order has some small cost associated with it, but that's going to be dwarfed by the cost of bugs introduced when junior devs are surprised by unordered dictionaries. And the pedantic people can just use an unordered dictionary manually since they are already converting pure abstractions to whatever imperfect implementations are provided by languages anyway.
- harryf 7y ago> I'm glad to see other languages finally catching up to PHP Now if python could just implement PHP's date function the world would be a simpler place... ( https://simonwillison.net/2003/Oct/7/dateInPython/ https://simonwillison.net/2003/Oct/7/dateInPython/ )
- upofadown 7y ago>Performance, size, etc are all less important, because they become less important with each passing year as computers grow more powerful. That isn't as true as it once was. We are running up against fundamental limits and people are even starting to talk about the environmental impact of computing.
- masklinn 7y agoIt should be noted that the ordering of python dict occurred as a side-effect of a new implementation with better memory profile (and as good or better performances).
- 6gvONxR4sf7o 7y agoI'd love to know more about where an ordered dict comes in handy. Anyone have use cases? Otherwise, guaranteeing this behavior just seems ‾\_(ツ)_/‾ If this is useful, I wonder if an ordered set is useful.
- bootlooped 7y agoI've used TreeMap in Java many times. I don't recall exactly why I used it, I think at least some of the cases were simply that it was convenient to be able to store an ordered list of two different types without having to go through the trouble of making a full blown class that holds those types.
- masklinn 7y ago> If this is useful, I wonder if an ordered set is useful. An ordered set is a unique list. It's useful. However it's not present in Python, dicts and sets have separate implementations and sets were not moved over to the ordered implementation (because the ordering was initially a side-effect of a change in implementation which was not considered useful or advantageous for sets).
- 6gvONxR4sf7o 7y agoAn ordered multiset is a list, not an ordered set.
- opportune 7y agoImagine 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 the trie to compute your autocomplete very quickly with no additional data structures. There are lots of other trie operations which are more efficient with ordered dicts too. I’m sure someone can come up with less complicated examples but this was the first one I thought of
- daenz 7y agoCool, but, this just encourages people to rely on hashmaps being ordered by insertion. The nature of a hashmap is not one where you rely on the ordering. This is going to trip up newbies who then move to other languages. Some comments on the post don't seem to understand the changes, for example, the C++ comment saying that std::map is ordered, so this isn't a strange change. The difference is that std::map is a red-black tree implementation, which has a traversal order, not a hashmap with insertion order. So there is already confusion.
- diN0bot 7y agoquestion: does the following expression still evaluate to True with ordered dicts? {'a':1, 'b':2} == {'b':2, 'a':1}
- ebg13 7y agoYes. Dict comparison doesn't rely on iteration order.
- diN0bot 7y agothanks :-) i mean, i would hope not if it's an implementation detail and not a change in the abstraction itself... feels a bit like it is breaking the abstraction, though.
- ebg13 7y agoThe definition of a dict hasn't changed. It's still defined as a set of key:value pairs. It just happens to also have a particular guarantee now that iterating over the keys will return them in insertion order.
- diN0bot 7y agonevermind, i thought this was a future change, but it's already live. i've been using 3.7.4, and can confirm that two dictionaries with equivalent key,value pairs, even if inserted in a different order, are considered abstractly equal. this coincidentally came up for me this morning on a small interview challenge: https://dev.to/candidateplanet/comment/l8o2 https://dev.to/candidateplanet/comment/l8o2
- sproketboy 7y agoBreak Everything. YAY
- _aleph2c_ 7y agoThis 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 you wrote and think, "Why bother? Maybe I should spend my weekends playing with my kids instead."
- bbrik 7y agoAs far as I know, it was implemented by Raymond Hettinger. This is a very interesting talk about the new tech: https://www.youtube.com/watch?v=p33CVV29OG8&t=1202s https://www.youtube.com/watch?v=p33CVV29OG8&t=1202s
- brettcannon 7y agoRaymond came up with the idea, PyPy implemented it, and then INADA Naoki implemented it for CPython.
- takeda 7y agoIf I remember correctly his talk. He went to CPython first and it was rejected, but PyPy welcomed it.
- lapink 7y agoIndeed, here is the mail from Raymond Hettinger explaining the new design on the python-dev list: https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... Quite amazing that it is faster, more memory efficient and convenient for the end user.
- masklinn 7y agoIt was proposed by Raymond Hettinger, but was actually first implemented by PHP and Pypy.
- 7y ago
- ebg13 7y agoFor some definition of "now". Python 3.7 was released in June 27, 2018. So "now" is "for the past year and a half". Python 3.6, which implemented the change originally, was released in December 23, 2016. By that measure "now" actually means "for the past 3 years".
- toyg 7y agoThe whole Python 3 affair made me realise that a lot of people upgrade their tools like once every 5-10 years. Which is shocking, in an industry as fast as this. I’m not saying you should churn your whole build setup every 6 months (I think release speed for Python is a bit excessive at the moment, for example), but complaining in 2020 for a feature that was released almost two years ago, was in development for a year or so before that, and was widely publicised... I mean, c’mon.
- c-smile 7y agoSame thing as in JavaScript : https://www.stefanjudis.com/today-i-learned/property-order-is-predictable-in-javascript-objects-since-es2015/ https://www.stefanjudis.com/today-i-learned/property-order-i...
- codesnik 7y agoRuby introduced similar change in 1.9 back in 2007, and we're fine.
- dekhn 7y agoA bit of a side topic, but when Judge Alsup (himself a descendent of Boole and with a middle name of Haskell, and a programmer to boot) said "It is so ordered" (https://casetext.com/case/oracle-america-inc-v-google-8 https://casetext.com/case/oracle-america-inc-v-google-8) in the Oracle Google case, I could only think that's what a computer scientist would say when quicksort was done.
- TimMurnaghan 7y agoFrom TFA "... it brings Python on par with PHP" Faint praise indeed
- jmilloy 7y agoI think this change is great, but this really only becomes news again once all major LTS are shipping with at least Python 3.7, right? No one can really use it in code they plan to distribute at the moment. Maybe I am underestimating the amount of Python code that is meant for internal or personal use only.
- sandgiant 7y agoWe've been running FROM python:3.7 in production for months. Works just fine. ;)
- dharmab 7y agoMany apps bundle Python along with their app, either within a container image or as a complete portable copy distributed with the binary. We've been building FROM python:3.8 for a few months.
- mixmastamyk 7y ago3.6 is ordered as well. All other versions are about to be EOL soon.
- svnpenn 7y agoIt seems people dont realize that you can have your cake and eat it too. You can have both orderered and unordered maps in the same language: https://yaml.org/type/map https://yaml.org/type/map https://yaml.org/type/omap https://yaml.org/type/omap No reason to argue about which one to make "dict". In fact it would be better to have both because youre taking a performance hit (a significant one) by ordering the entries.
- lvh 7y agoThe new dict does not come with a performance hit, let alone a significant one. It’s much more memory efficient and generally slightly faster.
- svnpenn 7y agopretty strong evidence to the contrary https://apps.dtic.mil/dtic/tr/fulltext/u2/a627127.pdf https://apps.dtic.mil/dtic/tr/fulltext/u2/a627127.pdf do you have any references to back your claim that its actually faster?
- joshuamorton 7y agohttps://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff... The new python dict implementation is benchmarked as faster in both microbenchmarks and in practice for almost all real-world workloads. Note that this isn't a sorted map, like C++'s "Ordered Map", but an Ordered map. C++ get's the name wrong. Items aren't ordered by key comparison, but ordered by insertion time.
- svnpenn 7y agoGood link, thanks
- masklinn 7y agoPython has had both ordered and unordered maps in the same languages for 10 years or so (OrderedDict was added to the stdlib in 2009). In 2016, the standard dict was moved to a new and more efficient implementation (more compact & faster to iterate). It was naturally ordered, and so as a side-effect of this change and since the CPython devs did not explicitly scramble it, iteration on dicts became both deterministic and specific (it would always follow insertion order). This was considered both a boon because conserving iteration order is strictly more useful than not doing it and a woe because it would cause compatibility issues with third-party implementations or further changes down the line as users would absolutely start relying on the iteration order even if it was still considered unspecified. So in the next major release they decided to resolve the issue by making this behaviour part of the language. It restricts future design space, but they can always add an unordered dict as part of the stdlib if that ever truly becomes useful so meh.
- awkward 7y ago1) I am personally annoyed as someone who has had to unwind knotty dict soup python codebases. 2) This will make life easier for thousands of programmers and prevent a massive number of extremely difficult bugs from hurting users.
- deleted 7y ago[deleted]
- skrebbel 7y agoThis is awesome, because the ordered map is the best data structure out there for easy & predictable programming, possibly only barring the array. There's so many cases where it's a benefit for map entries to retain order (and none where it's a problem). PHP really got this one right (and immediately messed it up by mixing ordered maps with arrays into a big soup, but hey, PHP). And so did, JS, sorta-kinda-by-accident.¹ When I went from PHP to Ruby back in the day, Hashes not being ordered definitely was my biggest gotcha. Everything about Ruby (except the deployment) was nicer, but the hashes... I've spent serious amounts of extra thinking just to make code work that would've worked out of the box in PHP. Yay for ordered maps! Every language should have them, they're the best! There's just so much ergonomics packed in such a simple API. 1) JS objects are ordered maps, iff the keys are strings that cannot be parsed as an integer (really) (yeah it's nuts) (but still better than unordered maps!!)
- BiteCode_dev 7y agoI live in the Python bubble, so I haven't realized until this post that so few people knew about that. This post is massively popular despite talking about a feature we had since Python 3.6, in 2016, that was posted on HN at the time and that is featured in most popular tutorials. A good reminder that most of the world doesn't revolve about my favorite language. And that information is not that fast to spread.
- rplnt 7y ago> about a feature we had since Python 3.6, in 2016 No, you had that feature in one implementation. Now it's in the language specification. That's vastly different because only now you can rely on it without fearing it can go away with the next release.
- BiteCode_dev 7y agoFirst, cPython is 99% of Python deployments. So much that if a script works on it but not on another implementation, people often consider the later broken. As this post proves that most people don't even know about this feature, you can be pretty sure the vast majority of people don't know about pypy, micropython, etc. Secondly, even if you want to nit pick, Python 3.7 made it official more than one year ago. We are currently in the 3.9 alpha. In fact, 3.7 didn't touch the implementation, just merely declared "yep, good idea, let's keep it that way".
- deleted 7y ago[deleted]
- squeaky-clean 7y agoThere's also the indication that this is official, and not just an implementation quirk. I still used OrderedDict in 3.6 because there was no guarantee 3.7 (or later) wouldn't silently break ordering on the standard dict. At least now it's unlikely to change because it will be considered a breaking change.
- 7y ago
- jnwatson 7y agoIt sure is annoying seeing people complain about a well-received feature implemented 3 years ago that has already transitioned smoothly.
- strenholme 7y agoThis is a refreshing update for those of us that like having code which will always act in the same way across multiple invocations. Now, if only Lua could follow the same path with their “tables” (“tables” is what Lua programmers call their form of Python’s “dictionaries” and Perl’s “hashes”). I just spent eight hours earlier this week debugging Lua code which would run differently on different invocations of the same code. The standard way to iterate in a table with Lua is like this: for key, value in pairs(foo) do One problem: The order we get elements from the table “foo” is undefined, and it can change between different invocations of the same Lua code, even if the elements were put in the table in the same order. In order to fix things so that we can iterate a table in a consistent manner, this is my fix (public domain [1], if those who want to copy and paste it): function sorted_table_keys(t) local a = {} local b = 1 for k,_ in pairs(t) do -- pairs() use OK; will sort a[b] = k b = b + 1 end table.sort(a, function(y,z) return tostring(y) < tostring(z) end) return a end Then we iterate the table like this: for _, key in ipairs(sorted_table_keys(foo)) do local value = foo[key] (In Lua, two dashes indicates a comment.) Note that this code will not always sort in the same order all tables. If we have a table with the keys 1 (as a number) and "1" (as a string), iteration order is still undefined. The code is open source, and is a procedural (“random”) map generator for Doom written mainly by Andrew Apted which I have added some features and fixed some bugs with. It’s here: https://github.com/samboy/ObHack https://github.com/samboy/ObHack and the issue is here: https://github.com/samboy/ObHack/issues/4 https://github.com/samboy/ObHack/issues/4 [1] The project I added this code to is GPL, but this function, which I wrote entirely by myself, is one I am donating to the public domain.
- wruza 7y agoYou can write an iterator yourself, no need to leave ?pairs idiom: function sortpairs(t) local keys = { } for key in pairs(t) do table.insert(keys, key) end table.sort(keys, function (a, b) return tostring(a) < tostring(b) end) local i = 1 return function (t) local key = keys[i] i = i + 1 if key ~= nil then return key, t[key], i-1 end end, t end t = {a=10, c=20, d=30, b=40, 50} for k,v,i in sortpairs(t) do print(k, v, i) end
- Grimm1 7y agoThis has been true since 3.7 why is this such a seemingly major revelation on HN?
- deleted 7y ago[deleted]
- divbzero 7y agoThe historical background for those interested… The ordered dict for Python was originally an implementation detail, part of a more compact dict representation that was first proposed for Python in 2012 [1], implemented for PyPy in 2015 [2], and merged into CPython 3.6 in 2016 [3] [4]. [1]: https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... [2]: https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff... [3]: https://mail.python.org/pipermail/python-dev/2016-September/146327.html https://mail.python.org/pipermail/python-dev/2016-September/... [4]: https://news.ycombinator.com/item?id=12460936 https://news.ycombinator.com/item?id=12460936 The decision to add it officially to the language spec wasn’t made until Python 3.7 in 2017. [5] [5]: https://mail.python.org/pipermail/python-dev/2017-December/151283.html https://mail.python.org/pipermail/python-dev/2017-December/1... "Guido says ‘Make it so.’"
- amelius 7y agoTitle should say what "ordered" means. Is it by key, or by insertion-order?
- deleted 7y ago[deleted]
- neycoda 7y agoYou ordered snake dicks?!
- ummonk 7y agoWait, if it is held in a separate dense array, is removal of a key from a dictionary O(N)?
- Rapzid 7y agoYou can use memcpy to remove items from the middle of a memory segment. It's probably not a single memory segment either; I imagine it works more like a Golang slice.
- ummonk 7y agoMemcpy is certainly O(N). But yeah, if they implement it with multiple slices (e.g. a B tree) it could be fast.
- Rapzid 7y agoHrm, I'm pretty sure I meant memmove: https://golang.org/src/runtime/slice.go https://golang.org/src/runtime/slice.go EDIT: I could have sworn they were shifting entire pages around without using a cycle per byte but I can't find any reference to that now haha.
- jameshart 7y agoGreat, you recovered the memory. But now you have to update all the pointers to the array in the hashmap....
- dilap 7y agoYou don't actually remove the entry, you just mark it as deleted. Eventually if too many things are deleted you repack the array. Still amortized O(1). (No different than a hash table in general, which will need to recopy the underlying array when it grows.)
- jameshart 7y agoBrilliant: Now your map contains an allocator and a garbage collector.
- deathanatos 7y agoHow does one have insertion order and maintain O(1) deletions?
- Sami_Lehtinen 7y agoUnfortunately ordered dict doesn't provide index access. In many cases, it's still required to maintain parallel list + dict approach, even if dictionary is ordered. List for index access and dict for fast look ups and containing the data.
- lunias 7y agoPretty important to note that it's "insertion order". I immediately thought, ordered by what comparator function?
- ibic 7y agoSo isn't that a backward-incompatible change for versions prior to 3.7?
- jxramos 7y agoA great talk behind the redesign which achieved this can be found here: BayPIGgies at LinkedIn June 2017: "Techniques for Design Reviews" by Raymond Hettinger https://www.youtube.com/watch?v=cNqJDRsefg8 https://www.youtube.com/watch?v=cNqJDRsefg8 There's a lengthy lead in, but its worth listening to.
- peter_retief 7y agoMust say I am glad about that. It confused me when I first discovered this and was told it was not a bug
- jillesvangurp 7y agoJava has many types of Map, Set, and List implementations. And that's just in the core library. Here are some Map implementations that come with Java: TreeMap, a HashMap, A LinkedHashMap, ConcurrentHashMap, EnumMap. There are many more and they each have their own uses, features, and performance/memory characteristics. I always wondered why languages like ruby, javascript, and python don't include a bit more choice on this front. It seems like sets are still somewhat of a novelty for javascript developers and people just wing it with half-assed solutions involving stupid O(N) contains operations.
- cocoa19 7y agoUnpopular opinion: I'd rather have classes that have precise meanings such as in Java. ArrayList, HashMap, TreeMap. Having classes with ambiguous names makes it seem like a toy language.
- deleted 7y ago[deleted]
- yason 7y agoFunny, I've never expected or needed dict to be ordered. I've known about collections.OrderedDict but never really found much use for it. A dictionary is a hashtable and the order generally isn't important for typical uses of a hashtable. So, what is it that people are putting in dicts where the order of insertion actually matters?
- deleted 7y ago[deleted]
- leksak 7y agoIt'd be nice if using collections.OrderedDict could elicit a warning. Is there a tool like flake8/autoflake for flagging things that used to be Pythonic but no longer are?
- stevefan1999 7y agoBut how does ordered map(self-binary search trees) handle hash-only key? I mean you can compare lexicographical order with character strings or numbers, but not a class instance right?