Python dicts are now ordered
softwaremaniacs.org
softwaremaniacs.org
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.
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.
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".
Not to mention that developers just begin migrating to python 3 in 2017 and code still had to work on 2.7 that doesn't order.
https://www.python.org/downloads/release/python-370/
“The insertion-order preservation nature of dict objects is now an official part of the Python language spec.” (June 27, 2018)
> Make it so. "Dict keeps insertion order" is the ruling. Thanks!
[0] Well, he usually gives great talks anyway
[1] Alright, he literally started many talks doing that
This is Python we're talking about.
I don't use dicts if I require ordering, but if I did I would probably still reach for collections.OrderedDict...
I wonder what the implications are of dict ordering with the "new" (new for me...) function args and *kwargs...from the hip it sounds pretty handy.
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!!)
No, it didnt. What PHP calls "array" is actually an Ordered Map, as you alluded to:
it literally says that in the documentation, paragraph one, sentence one:
> An array in PHP is actually an ordered map.
The issue, if one exists, is that PHP doesnt have a sequence type:
but one is provided as a package:
$arr = [];
$arr[2] = "two";
$arr[0] = "zero";
$arr[1] = "one";
echo join($arr, ", ");
// two, zero, one
Everybody's writing PHP code pretending that it has arrays when really, it does not. The gotchas are way bigger than the gotchas in Python <3.7's unordered maps. It's a mess.
You start with an _empty_ array, then (somehow) set the third element of that array? That makes very little sense.
Had you _initialized_ your example as an array with a length of 3, your desired behavior would, indeed, manifest.
Ideally the maintainers of PHP would rename it and deprecate the use of `array()` over a long period of time.
$id = 12835151;
$arr[$id] = Get_thing_with_id( $id );Obviously, I'd agree that a map/associative array/dict/etc is a better choice here; I'm just annoyed about the name.
Well, there's no reason a language could not initialize an empty array to some initial capacity, either on declaration or when you add an indexed element.
The order inserted makes most sense in most cases. Hand crafting integer based array indexes out of order is rare. And as you say a simple ksort call guarantees sort order.
ksort($arr);
echo join($arr, ", ");
// one, two, threeWell, no so weird, I'm not a native english speaker, and I've seen the term hundreds of times over the years...
It's also quite common on HN:
https://www.google.com/search?q=site%3Anews.ycombinator.com+...
array_values($arr)[2];So example, if you had numeric indices that you wanted to guarantee that index order is equal to insertion order, you'd create an array using $my_array = array_pad([], 20, null); If it's an array that you didn't create, the ksort(...) method will order the array for you as expected.
Edit: after reading through the documentation on array_pad, it looks like it will even correct key order in existing arrays. https://www.php.net/manual/en/function.array-pad.php#87735
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
Don't know if this could actually be the case in practice, but theoretically the ordering could allow for a timing attack to glean some bit of information when performing a linear scan of the map (size of the map, relative location of the data, etc).
Just a contrarian thought given the definitive statement of "none where it's a problem". I'm generally of the same opinion as you though; mostly if not entirely harmless, potentially helpful in certain applications.
An attack where the attacker has access to your ...program code and can run instructions there? In that case, leaks from a "timing attack" would be the least of your worries...
If they just provide an input to your program somehow externally, then whether you put that input into a map or an ordered map or not is an implementation detail. You could make your program rid of the "timing attack" in 100s of ways... (or have one, in 100s of ways). That doesn't make an ordered map more unsafe than any of the 1000s of ways to have a timing attack.
This doesn't impact most high level python code, and an OrderedDict is a very reasonable default. But there's a reason why Google's c++ map intentionally randomizes iteration order
(Hint: it allows the hash map and hash function to be extremely high performance while allowing themselves the flexibility to change the hash function)
The difference is whether order is part of its identity. A dict is still just a set of pairs, not a list of them. It just happens that it also guarantees now that if you _iterate_ over the set you'll walk the keys in insertion order.
FWIW I don't think people agree on whether "element order is part of the value's identity" is part of the definition of "ordered map". There's plenty other languages & libs with ordered maps where the order isn't part of its identity but they still use the term "ordered map" in the name or the docs. Eg PHP's arrays or ImmutableJS's OrderedMap.
Previously it was unpredictable, and that's why collections have OrderedDict; which makes sense instead of trusting an implementation detail of CPython from 3.6.
Is not mentioned in the docs: https://docs.python.org/3/library/stdtypes.html#mapping-type...
EDIT: but the behaviour is documented in OrderedDict itself! https://docs.python.org/3/library/collections.html?highlight...
Interesting!
You can get the first/last key of a 3.8 dict with dict.keys() and reversed(dict.keys()) which you can then delete to reimplement OrderedDict.popitem.
Deleting a key and reinserting it will let you reimplement move_to_end.
The only cool thing that OrderedDict's implementation might be useful for is to move to front (or anywhere else not the back) but it doesn't expose that api.
And here I thought Lua was the only language insane enough to do something like that.
Just realized Lua tables aren't ordered, but it still mixes arrays and maps / tables into a single data structure.
Back when JS got popular and the majority of web programmers knew PHP, there were dozens of tutorials out there trying to convince you not to do stuff like this:
var a = new Array();
a["moo"] = "five";
a["foo"] = "six";
Good times!
I'm pretty sure they didn't in Ruby ~1.8 though. It's been awhile :-) Can't remember exactly which version, but it bit me more than once so I'm pretty sure :)
I've made heavy use of all kinds of maps, and of queues and channels and arrays, but I don't recall ever noticing a situation where I wanted the properties of both mixed into the same data structure.
I'd love to learn more about useful tools to add to my toolbox!
For example, supposed you have a list of ids accessing some system, you may want to count the raw number, but then also have some transformations thereof that are still ordered by count.
Example
l = getListOfAccessIds()
counts = Counter(l)
total = np.sum(counts.values())
fractions = {k:v/total for k,v in counts.most_common()}
#use the fact new dictionary is still ordered by most common
plt.semilogy(fractions.values())
plt.plot(np.cumsum(fractions.values()))
#still works like dict
print(fractions[id_of_interest])It allows me to both apply them sequentially as generated, or to "jump to" a particular point in time.
But generally it's about determinism and avoiding loss of information, not just whether a particular algorithm needs it. For example, you'd want serialize(obj) and serialize(deserialize(serialize(obj))) to produce the same output, otherwise you e.g. might not be able to cache stuf. But for a data structure like a hashtable, it's pretty tough (not logically impossible, but rather pointlessly difficult) to make that happen without preserving insertion order.
As another example, it's incredibly handy for a user to see items in the order in which they were inserted. Like say you're parsing command-line arguments, and the command is ./foo --x=y --w. If the user sees {x: y, w: None} then that tells them w was passed after x. That can be extremely useful for debugging; e.g. maybe you expected the caller to specify w earlier, in a different context and for an entirely different reason. Seeing that it came afterward immediately tells you something is wrong. But when such information is lost it's harder to debug code.
console.log(object)
{
keys
in
headache
less
order
}
* Inserting into the cache is just normal insertion.
* To delete excessive items, simply iterate to get the first few items' keys, then delete.
* To lookup, simply do a key-based lookup, then delete and re-insert.
For the same reason, though, it's potentially a bad idea. All these algorithms that generate dicts generally won't promise to maintain insertion order, they just happen to by chance. Then consumers come to depend on it and be surprised when it inevitably changes.
So currently (now that there are Symbols in JS), the order is: array-indexed properties first (integers), then string-key properties, in insertion order, then Symbol-keyed properties in insertion order.
The reason for the funny behavior in treating integer keys differently is that property keys are always treated as strings, so obj["3"] and obj[3] can't be distinguished, and arrays are also ordinary objects, so setting obj[3] was made to do the same thing on any object rather than special-casing arrays and non-array plain objects...
Today, JavaScript is a small, reasonably elegant scripting language with reasonable semantics, buried in a medium-sized, reasonably expressive scripting language with reasonable but different semantics, added 20 years later. The kitchen-sink disease is far enough along that it'll probably never recover the appeal it once had as a beginners' language. It still has the advantage of backwards compatibility, and it's become more practical as a compilation target.
Note that special-casing arrays is precisely what implementations used to do (i.e., for non-Array objects, the order in most VMs was simply "properties in insertion order").
V8 was the first JS VM to stop special-casing Array (and this was done before Chrome went public, and was the behaviour in the first Chrome beta). It turned out that virtually no websites relied on "array index" properties appearing in enumeration order (there was some breakage, but it was relatively few and far between, and believed to be worthwhile for the gains in cache-hits when accessing properties), and this also allowed the more compact array representations to be used for them.
In retrospect if something was going to be standardized I'd have preferred it to be the older behavior which was simpler to explain, but so it goes.
/s
But back in the day they indeed were not, for appropriate values of back in the day. :)
it did make a LOT of things more convenient and less buggy when they made ruby hashes ordered, I recall. I didn't expect it would matter much, by found myself loving it. I believe the ruby maintainers investigated and determined they could do it with very little performance hit. It turns out that having a repeatable and predictable order, that also matches insertion order, is what a lot of people end up assuming whether they realize it or not, just makes everything smoother when it is.
Of course there’s a trade off. There has to be.
In this case it prioritizes usage patterns oriented around insertion and enumeration over usage patterns involving repeated removal Or modification of items.
as items are removed, the insertion-ordered index will either fragment, require removal operations to not be constant time, or be implemented using a data structure that has per-item storage overhead (such as a linked list).
also there are two possible, reasonable things for an ordered list to do when you write a new value to an existing key - leave the key in original insertion position, or move it to the end. Whichever one the implementation chooses, people who want the other will need to implement their own key ordering state alongside that which the collection is doing for them.
https://play.golang.org/p/DISpyv0Zuq_j
HN discussed this a little 6 years ago: 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.
Code that assumed it was arbitrary, would expect to handle any arbitrary order, including a happens-to-be sorted order.
Code that assumed it was random, like actually inserted by random(), was already broken, because that simply isn't the case.
Code that assumed the order would stay constant was relying on implementation-specific behavior, and could potentially break on any version update; as with any reliance on implementation-specific behavior, you'd break if the dictionary code ever got touched -- even if it were for a bugfix.
Code that ordered the dictionary keys before iterating are now slightly innefficient due to extra work of sorting a sorted list.
But in the case of downgrading, I'm fairly sure there's a number of other breaking changes that can't trivially downgrade minor versions. Like f-strings were only introduced in python3.6 as I recall. Async keyword only exists as of 3.4 as well I think?
The only way to consistently code cross-version is to start with the lowest you plan to support (assuming the higher versions are actually backwards-compatible).
Does any language gaurantee that code is both backwards and forwards compatible?
The other why around is also true, code that relies on it must specify that it requires python >= 3.7
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 they went ahead and gauranteed it. But that might not be an optimal strategy in other areas, but they're forced to follow along anyways.
But actually moving cpython code to say ironpython should not be impacted, unless ironpython lies about it's compatibility
you arguably ought to anyway, for explicitness.
That said, Go made a similar change (from insertion-order to explicitly-randomized) and world didn’t end. So there’s that.
That field itself is kinda new; but if needing to block users with older versions, that shouldn't be an issue.
See https://medium.com/i0exception/map-iteration-in-go-275abb76f...
It has useful features for manipulating ordering but while I've regularly needed had use for maintaining insertion ordering I can't remember ever needing to move items around within a map.
>>> isinstance(OrderedDict(), dict)
TrueIt remains so today, ordereddict is not an alias or trivial facade to the normal dict because it has to maintain its doubly linked list and implement a bunch of additional operations based on that e.g. pop first or move to end.
That said, I have no idea about the internals of dict. I assume no performance was sacrificed for this change.
I could potentially assert a version, but do I really want to do that each time I wrote something that might be used somewhere else?
And yes of course I could add a line of documentation, but there is a 100% chance I’d still get bug reports from people on 3.5.
If you are just distributing raw python files then congratulations you’ve just realised why packaging is valuable.
If you want to install it, go ahead and copy or symlink it in your ~/bin or whatever you fancy (that's your personal preference anyway unless I'd specifically package it for some OS like Debian). I don't want to have to use some setup.py that I have no clue where in my OS it installs things.
It's not duplicated and in most cases it's not even delivered as part of the installation.
> If you want to install it, go ahead and copy or symlink it in your ~/bin or whatever you fancy
That's exactly what pip will do if invoked with `--user`.
> I don't want to have to use some setup.py that I have no clue where in my OS it installs things.
It installs it to a single place. Run `python3 -m site` and look at `USER_BASE`.
To avoid a lot of this, use pipx[1] to keep things even more isolated.
> Often have to do chenanigans like "python3 -c 'from sometool import __app__'".
You're doing things wrong because you don't know the tooling. You'd also typically just do `python3 -m sometool`.
Things that are distributed as a single file are either so simplistic and have no other dependencies that you can just make do, or written by someone who doesn't know what they are doing and so you're going to have a bad time.
If your code won’t work for older versions you can make an explicit check that the version of python is greater than whatever you need.
I suppose Python doesn't even have backwards compatibility within the same major release as we saw with the addition of the async keyword in Python3.5. Many older Python 3 packages broke because they expected that to be a legal identifier for a variable name.
facebook is just as capable of writing hot garbage, sadly.
I don't see how anything could break (unless there are alternative implementations with different behaviour I'm not aware of?)
Dicts have been effectively ordered since 3.6. Iteration order was literally randomised (at process start) before 3.6. I'm also not sure whether the behaviour under deletion was changed between 3.6 and 3.7 so it's possible that there are subtle differences there.
Also, this change was implemented 3.6, but in 3.7 they officially documented it as a language feature (i.e. that all other Python implementations also need to preserve the order).
That's a truism. For all versions of Python. If you use feature of python ver X, you should not be surprised that it doesn't run on versions less than X that lack that feature!!!
If you write a Python library and use feature of Python ver X and don't mark library as only >= Python ver X, you are doing it wrong and a horrible person.
I get the whole principal of least surprise, but not at the expense of progress.
Dicts are ordered, specifically insertion-ordered, not sorted.
Sometimes they'll be sorted:
D = {i:i for i in range(10)}
D[-1] = -1
zip(D.keys(), D.values())
D.items()
> If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are called with no intervening modifications to the dictionary, the lists will directly correspond. This allows the creation of (value, key) pairs using zip(): pairs = zip(d.values(), d.keys()).
oldkeys = list(D.keys())
D[z] = foo(z)
zip(oldkeys, D.values())
The subtlety of this is what I, and perhaps others, find the most jarring.
> Changed in version 3.7: LIFO order is now guaranteed. In prior versions, `popitem()` would return an arbitrary key/value pair. [1]
If they added a new `popordereditem()` method, good 3.7 code would use that, and an attempt to run that code on 3.5 would throw a reasonable, useful error message. If they wanted to play it safe like Rust or Go, they'd add the ordered method and make popitem() deprecated or make it artificially use random/arbitrary order so you can't accidentally depend on a new implementation detail and have a test case work.
Also, your case 4 does deserve some protection because while bad code it's hard to test for bad but working code. Implementation-specific or undefined behavior that works is the worst kind of problem, because it's hardest to test against. Compile-time syntax errors are the easiest, runtime errors are testable with a solid test harness, some possible can be identified as warnings with linters, but sloppy code requires manual inspection to detect.
Actually, no, I take that back: Implementation-specific or undefined behavior that works sometimes! is the worst kind of problem. That's what this code enables; if your test case is `dict({'one': True, 'two': True})` and you have a unit test where you popitem() to assert that you get 'two' and then 'one' it will pass the test harness on 3.7, it will pass on 3.6 because of implementation-specific behavior, and it will pass on 3.5 because the hash map arbitrarily puts those particular items in order. But it will silently get it wrong when you pass in user-supplied data. Shudder.
[1]: https://docs.python.org/3/library/stdtypes.html#dict.popitem
I think TimSort is extremely efficient for presorted lists, so even that isn't a major impediment.
Baking this as a language guarantee is the only protection against Hyrum's Law.
People will just do what they've always done - they'll be aware of the differences, or they'll test.
There's nowhere I have seen that mentions dicts are ordered without mentioning in the same paragraph the version since which this has been the case, so anyone who knows they're ordered will be aware.
Tldr its fine
This one is unusual because it won't break old code being brought forward, only the other way around, and theoretically there are lots of things going the other direction that would break (though most of them are explicit, not silent).
Backward compatibility is the ability to run old code with new interpreters. This is not broken here.
What's broken is the ability to run new code on old interpreters. But this is already broken at every python update (new operators, methods, syntactic sugar..). We could call it reverse backward compatibility.
- backwards compatible code: new code can run on an old interpreter
- backwards compatible interpreter: old code can run on a new interpreter
EDIT: After some thought, you're right. The second description is the reasonable interpretation.
"python 3.7 is backwards compatible with python 3.6"
(Driving to an airport) "Okay, we gotta pick a road. Arrivals or departures? We're arriving, but then we're departing."
But, from a pragmatic angle, it strikes me as a genius move. As the article said, this was a natural by-product of a performance enhancement that was made in 3.6. In principle, that was fine, because there was officially no predictable ordering, so a change to how it was being ordered in practice shouldn't materially affect anyone. And nobody really paid much notice to it then.
And that's where the danger lies - there's risk there, because, as you said, someone who's used to Python 3.6 might have problems switching to 3.5. And that's probably a greater risk if they left it out of the spec, because people would have continued to not pay it much notice. By making it official in 3.7, though, they've sent out a message that the Internet hate machine has ensured that everyone will hear. That probably, in practice, actually reduces the risk.
And, while many understandably see this as violating the spirit of semver, it unambiguously does not break the letter: Minor changes are only supposed to avoid breaking the software's compatibility with code written against an old version. There was never any rule saying that old versions have to be compatible with code written against the new version.
That is actually why the Python maintainers decided to make this behaviour official: the ordering was the consequence of changes in implementation details, but over 3.6's lifecycle they feared it would cause compatibility issues as users would start relying on the ordering properties of CPython and that would be an issue for alternate implementations (though pypy had switched to the same implementation even earlier so was also insertion-ordered even when running in Python 2.7 mode).
Providing stronger guarantees was considered useful and unlikely to be severely detrimental in the long run, so the project decided to make it part of the language spec.
It does come at a cost, but I think Python aims for ease of use over runtime speed and memory efficiency, so it seems perfect for them.
Big whoop
Javascript doesn't specify performance characteristics of objects and arrays, so even with implementations, one object could be a hashtable, another a balanced tree.
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.)
I can't imagine how it can break something. In which case can you have an advantage to have an unordered list? Biggest downside can be about perf, but I don't think it's the case here.
And beyond this, even if maintaining backward compatibility is important, I don't think it should prevent software from being improved, and dicts being ordered is pretty awesome. I'm pretty sure relying on unsorted dicts might involve pretty hacky code.
I recently stopped writing a z-order test application because I remembered that dicts are not sorted, so it made my goal a little pointless. Meanwhile C++'s std::map is sorted. I think there was already sorted dict in python, but I don't remember.
EDIT: I'm wrong, I'm mixing "ordered" and "sorted"
If a new guarantee or behaviour were a breaking change, every non-patch release of a semversioned tool (which python isn't) would be major.
And that's sort of the problem. If it was broken, you'd know it and you'd fix/rearchitect it. Instead, it will appear to work.
For example, if you wrote something in pypy it would be ordered versus cpython.
And randomised at interpreter start, since Python 3.3.
This is like many evaluation guarantees in latest C++-NN standards. Good to know, might be useful for performance tuning of automatic code generators, etc. , but irrelevant most of the time. My 2c.
It's like, you have a great marriage with everything working out and some fine children who are doing great too, but you get a divorce anyway to pursue your dreams of being a conceptual artist.
(BTW, in case anyone is keeping track, I was going to maintain P2 but got caught up in Prolog, of all things, and now Python looks just as crude as everything else and I don't have the requisite love anymore to shoulder the work. I might make a Python 2 interpreter in Prolog though! That would be fun.)
It's important to discover coupling between your tests, this just isn't the way most people want to do it.
Dot-upgrades do allow for breaking changes, but this one can break silently and I’m not sure where such breakages neither belongs in python nor where they should belong.
Personally I’m happy to get ordered ducts sooner rather than later.
I don't agree with the complaints about ordering ducts, but this is a ludicrous response. Appreciation of volunteers' work on Python isn't diminished by criticism of language features or changes. In fact, it enhances it: if people have opinions about the project you work on, it's a good sign that it's important, significant work. I've contributed to OSS projects before, and the ones in use by more than just my friends and I were naturally the ones that felt the most meaningful.
Python has had one such in the standard library for a decade or so.
While we're here, another tidbit that's often overlooked in the Java collections: If you reallly care about iteration performance, your data is without nulls, your data is already ordered how you like it or you don't care about ordering, your qty items >= 10, and you don't need random access, then ArrayDeque is gonna be your horse because of how much better it co-locates its contents in memory and how much less overhead is required to maintain it during each operation compared to all the other List implementations, including ArrayList and LinkedList.
LHM indeed pays 2 references per node but they are well worth as it has deterministic ordering/iteration and I have witnessed numerous cases with HashMap that show up in production only due to iteration order (esp after rehashing). The code is broken but the cases did not reproduce during testing...
Now if the two extra references are an issue, consider that HashMap is quite space inefficient with having a dedicated node per each entry - that's the main price. The (simple) node memory footprint is 36bytes on heaps less than 32GB, i.e. compact pointers. The extra references add another 8 bytes for having an insert or access order.
If the goal is getting a compact low memory footprint, HashMap is not fit for purpose. Overall it's the jack of all trades and even got reworked (java8) to support tri-based collision resolution for keys that implement Comparable.
Couple years back I wrote CompactHashMap (under CC0) that has an average cost of 10bytes per entry and it's extremely compact for small sizes with having only 2 fields on its right own, so even small/empty maps are tiny. In microbenchmarks (same used in openjdk) it handily (2x) beats java.util.HashMap on "Traverse key or value", get/put have similar performance, and "Search Absent" is worse.
The point is: LHM should be the go-to hashmap for java as being node based hashmap is justified (unlike java.util.HashMap)
https://www.stefanjudis.com/today-i-learned/property-order-i...
I think this feature says a lot about the philosophy of Python vs Go.
You could imagine that the hash function itself might do an adequate job of randomizing the order of the cards, though, especially if salted with a per-map salt. SipHash, for example, would probably not have any detectable biases in the distribution of the permutations thus produced. But whatever hash function Golang is using for my structs has an easily visible bias, as described in that comment.
[1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
S9 SJ SK HQ D9 S4 S5 S10 HJ S8 H6 DA D2
D4 DQ C6 C8 CJ H3 H9 DK C3 CQ SA S2 S3
S6 SQ H4 H10 D8 D10 C4 CK S7 H7 D5 D6 D7
C7 H2 HK D3 DJ C2 C5 C9 HA H5 H8 CA C10
This is very strong evidence of bias.
I'm interested to hear if my Golang can be made more idiomatic, or if there are bugs in it: http://canonical.org/~kragen/sw/dev3/mapshuffle.go
In particular it seems like there ought to be a less verbose way to express the equivalent of the Python list({card: True for card in deck}) in Golang.
Now wasting computation on randomizing... that is a problem.
If the human is using a computer to compare two JSON payloads (as the use of a diffing algorithm suggests), the human and computer should be clever enough as a team to realize that they could just deserialize and reserialize each JSON payload such that the keys were lexicographically sorted and the data was pretty-printed in the exact same way before running it through the diffing algorithm. `jq -Sc` would do the trick.
That’s why pipes were invented.
> And in a lot of cases you don't have the easy ability to "do stuff" before running the input through a diffing algorithm.
Well, in that case you’re not going to be able to meaningfully compare two JSON payloads because neither order nor white space have any semantic meaning in JSON. I’m really curious what you’re talking about though, since if you’re working on the shell you can easily use jq to do as I describe.
[1] Well you _can_ choose to do so, and I recently have, but it's not without its costs.
But the dict TFA talks about doesn't use a doubly linked list, or closed addressing, its ordering is a side-effect of its implementation but not originally a core goal (memory saving and iteration speed were). It'd probably been proposed by others before but it came to wider attention after Raymond Hettinger (a core dev) proposed it a few years back[0]. PHP actually released it first[1], closely followed by pypy[2]. CPython only got around to it some time later[3]
[0] https://mail.python.org/pipermail/python-dev/2012-December/1...
[1] https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implem...
[2] https://morepypy.blogspot.com/2015/01/faster-more-memory-eff...
[3] https://docs.python.org/3/whatsnew/3.6.html?highlight=3.6#wh...
set(dict.keys())
set(dict.values())
thing1 = dict(...)
thing2 = copy.deepcopy(thing1)
2. IIRC the new dicts are no(t significantly) slower than the old dicts, however they use less memory, and iterate faster
The iteration order is actually a side-effect of implementation details, the original goals were a more compact representation and a faster iteration: https://mail.python.org/pipermail/python-dev/2012-December/1...
Yes, of course. That's why I'm wondering if turning dict keys into a set is slower now.
1. it's been there since 2016, the new dict was released as part of Python 3.6 (though the ordering was only an implementation detail until 3.7)
2. the new dict is much more compact (20~25%) and should have much faster iteration speed, those were actually the original goals, ordered iteration was a side-effect
3. the new dict should not benchmark significantly slower across the board, it wouldn't have been merged if it were a regression
Python is just bizarrely political. I suspect that it's now cursed for all time to have every future PEP become a battle in a proxy war over PEP 3000.
So I would claim that equates to non-deterministic
To me, nondeterministic is when the input does not change but the output does. The docs essentially say to not rely on the order, not that the result is not reproducible.
From the origin to Python 3.2, iteration order was arbitrary but deterministic (in CPython, it was not guaranteed to be determinstic in other implementations)
From Python 3.3 to Python 3.5, iteration order was non-determinstic (across runs, it was deterministic per-process instance)
In Python 3.6 it's unspecified but deterministic and follows insertion order (in CPython)
In Python 3.7, Python 3.6's behaviour was specified and documented
At some point, if a human error is common enough, it makes pragmatic sense to change the design so the error is impossible.
> 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...
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.
Not really. I don't know the go implementation but you can get this behaviour by adding an arbitrary "startup defined" seed to your hash function and that does the trick.
It also gives the benefit of making hash table attacks harder.
Go's philosophy is also definitely willing to pay that price to avoid a large class of known bugs that has hit all kinds of code bases. It is not about being the fastest language. As compiled languages go, it's solidly middle-tier, and not likely to go up much from there. (Among the C-style compiled languages, it's low-tier on performance, at around half the speed of C in general. However there's enough compiled languages like Haskell that are still generally relatively slow so that Go is mid-tier for compiled languages over all.)
If I read https://lwn.net/Articles/474912/ correctly, Perl fixed that in 2003. C#, Java and Swift do it, too. As does (or, reading this, did?) Python (https://bugs.python.org/issue13703)
Welllllllll
In the case of C# it is/was more a matter of picking the -correct- Dictionary.
'OrderedDictionary' has been around since Net 2.0 (2005 or so,) as has 'SortedDictionary<TKey, TValue>'
But for some ungodly reason, there is no 'OrderedDictionary<TKey,TValue>' included in the framework that you can use. All you get normally is the non-generic one (where you have to type-check everything...) There are internal implementations used by the framework, but you'd have to do some hacky things to even get it to work.
However, in my 12 years of C# programming, I've only run into the need for this _once_, and it was to assist interfacing with a VB6 monstrosity.
Python 3.6 changed the underlying implementation to one which incidentally made iteration order not rely on the hash function, and as that seemed like a useful property and one which risked causing compatibility issues with alternate implementation (developers would come to rely on cpython's iteration order and code would break on jython or whatever) they decided to make it part of the spec for 3.7.
od = OrderedDict({
"y": "first",
"x": "second",
})
od = OrderedDict([
("y", "first"),
("x", "second"),
])
collections.OrderedDict(y = "first", x = "second")Same with class attribute ordering, PEP 520 still talks about using OrderedDict, however it was only merged after the new dicts, and even if ordering was not defined at the time (as part of Python-the-language) PEP 520 could use this internal property just fine and the ordereddict-based version was stripped out, the PEP was essentially accepted as a no-op (the ordering properties would just be officially documented).
"FOO" => "bar" # Replace FOO with bar
Unfortunately, despite empirical evidence to the contrary at the time, keys() does not guarantee sort-order results https://perldoc.perl.org/functions/keys.html
This worked for a while (appeared to work?) and but was subsequently caught by another developer, who added a sort().
(Get a templating library alreay yeesh).
Incidentally Ruby made the transition to sorted Hash some years ago (1.9 maybe?) and I don't remember any great fall-out.
Only possible downside might be performance (or memory). I recall the ruby maintainers ensuring they had an implementation with very little if any performance/memory implication.
> Hash entries are returned in an apparently random order. The actual random order is specific to a given hash; the exact same series of operations on two hashes may result in a different order for each hash.
Applying a `sort` to the output of `keys` is second nature to me - I'm always aware that hash entries are unordered in Perl.
For example, suppose you have a dictionary containing PriorityItem values. PriorityItems are sorted by priority, while the value only matters for equality (affects __eq__ but not __lt__). If you have a dictionary whose values are PriorityItems and you say `sorted(dictionary.values())` the order of the output could vary w.r.t. equal priority items. So if you wrote a test asserting a process hiding a dictionary had a stable ordering of the items, it might consistently pass by accident on your machine and then fail elsewhere.
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.
Now if python could just implement PHP's date function the world would be a simpler place... ( https://simonwillison.net/2003/Oct/7/dateInPython/ )
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.
https://www.php.net/manual/en/language.types.array.php
Its pretty much the main data type used in php. Once you get used to it is pretty powerful for dynamic languages. They even have built in sorts:
https://www.php.net/manual/en/array.sorting.php
They are "simple arrays" that have numeric indexes, but I find those used less frequently. (They can morph into the key->value pair).
PHP arrays may have been one of the "killer features" that lead to it taking hold of the web. It's so frictionless, powerful, and you can bend them to your will with ease.
_dict = {}
_dict.update({MyObject: 3})
_dict.update({'MyObject': 3})
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.
This is what I meant by "sane" in my comment. It's _way_ more meaningful to the user if data's insertion-ordered.
Surely that would be a sorted dict not an ordered dict.
I guess it’s good to spread awareness to HN readers who apparently were unaware, but the headline is very misleading.
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.
class OrderedDict(dict):
pass
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}
OrderedDict({1: 1, 2: 2}) == OrderedDict({2: 2, 1: 1})
For the latter issue, as explained above, can't they just implement a replacement __eq__ only for OrderedDict, and still re-use the new dict implementation?
Similarly, any subtle difference can be shimmed on top of the new implementation inside Python, no?
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.
I really appreciate the people who dive deep into these implementation details, and continue to optimize the languages we all use.
For a language that prides itself on being readable, that is an amusing quirk.
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
Class __annotations__ was new in 3.6. For its original use there's no need for ordering. They were ordered, because dicts were ordered, but only as an implementation detail.
Dataclasses were added to 3.7, after 3.6's features made a nice syntax possible. If __annotations__ hadn't happened to be ordered already then I would guess it wouldn't have been made ordered just for dataclasses - dataclasses just wouldn't have existed.
Making everything ordered in one go opens up possibilities you haven't even thought of yet.
As soon as you do something that cares about order, state how it is derived. Sometimes, insertion order is right. Sometimes, not.
Don't get me wrong alists are nice. And order def matters to those. But it is part of their definition. And reinsertion changes the order in obvious ways. Not even clear what it does to just "dict".
Now, I will concede this is overblown. Life will easily go on.
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
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
for _, key in ipairs(sorted_table_keys(foo)) do
local value = foo[key]
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 and the issue is here: 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.
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 d = {"foo": 2, "bar": 1, "zoo": 4}
for k in sorted(d.keys()):
print k
However, with Lua, “for” only accepts a numeric range, or an iterator function, so customizing “for” requires understanding function closures: Understanding how a function, when called multiple times, stores variables altered in previous invocations of the function, and understanding how to give those variables initial values (usually in the “function factory” function which creates the function we use).
In other words, “for”, in most modern high-level languages, can be one of:
1. for variable in [something that specifies a numeric range]
2. for variable in [iterator function]
3. for variable in [list]
But Lua only has “something that specifies a numeric range” and “iterator function”; it can not natively go through a list.
function vs(t)
local i = 0
return function (t)
i = i + 1
return t[i]
end, t
end
function sorted(t, cmp)
table.sort(t, cmp or function (a, b)
return tostring(a) < tostring(b)
end)
return t
end
function keys(t)
local keys = { }
for key in pairs(t) do
table.insert(keys, key)
end
return keys
end
t = {a=10, c=20, d=30, b=40, 50}
for k in vs(sorted(keys(t))) do
print(k, t[k])
end
One honest question: Is there any reason why the function factory (i.e. a function which returns a function) which converts a list (Actually, table with ascending integer indexes) in to an iterator Lua can use with “for” returns both the element and the entire table here? Here is the code I am asking about:
return function (t)
i = i + 1
return t[i]
end, t
2) This will make life easier for thousands of programmers and prevent a massive number of extremely difficult bugs from hurting users.
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.
https://apps.dtic.mil/dtic/tr/fulltext/u2/a627127.pdf
do you have any references to back your claim that its actually faster?
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.
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.
Anyway, I’ll keep using collections.OrderedDict (except for personal scripts) until py35 EOL.
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.
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.)
There are copious notes in there about the implementation and it indicates linked lists are used.
EDIT: Blargh, it's here: https://github.com/python/cpython/blob/60ac6ed5579f6666130fc... . That file references this blog post which indicates they may be flagging and repacking as dilap commented: https://morepypy.blogspot.com/2015/01/faster-more-memory-eff...
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.
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/1...
[2]: https://morepypy.blogspot.com/2015/01/faster-more-memory-eff...
[3]: https://mail.python.org/pipermail/python-dev/2016-September/...
[4]: 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/1... "Guido says ‘Make it so.’"
{'a':1, 'b':2} == {'b':2, 'a':1}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.
this coincidentally came up for me this morning on a small interview challenge: https://dev.to/candidateplanet/comment/l8o2
BayPIGgies at LinkedIn June 2017: "Techniques for Design Reviews" by Raymond Hettinger https://www.youtube.com/watch?v=cNqJDRsefg8
There's a lengthy lead in, but its worth listening to.
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).
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
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?
Faint praise indeed
def call_stored_procedure(name, **args):
cursor.call_proc(name, *args.values())
It's not quite as old as java's linkedhashmap but is no spring chicken either (it's a bit above 10 years old).
There are discussions on the subject on python-dev once in a while e.g. https://mail.python.org/pipermail/python-dev/2019-February/1...
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.
That’s like saying binary search tree is dead because the implementation uses a red-black tree.
Having classes with ambiguous names makes it seem like a toy language.
EDIT: to clarify, I was asking about JavaScript there.
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.