6 ms·
This 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 m
by skrebbel 7y ago
This 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!!)
- styfle 7y agoAlso don’t forget about JS Map which is ordered https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- svnpenn 7y ago> PHP really got this one right (and immediately messed it up by mixing it with arrays, but hey, PHP). No, it didnt. What PHP calls "array" is actually an Ordered Map, as you alluded to: https://yaml.org/type/omap https://yaml.org/type/omap it literally says that in the documentation, paragraph one, sentence one: > An array in PHP is actually an ordered map. https://php.net/types.array https://php.net/types.array The issue, if one exists, is that PHP doesnt have a sequence type: https://yaml.org/type/seq https://yaml.org/type/seq but one is provided as a package: https://php.net/class.ds-sequence https://php.net/class.ds-sequence https://github.com/php-ds/extension https://github.com/php-ds/extension
- skrebbel 7y agoSure, PHP arrays are actually ordered maps, but it's super confusing when used as arrays. I mean, look at code like this: $arr = []; $arr[2] = "two"; $arr[0] = "zero"; $arr[1] = "one"; echo join($arr, ", "); // two, zero, one In any other language, the result of similar code would be "zero, one, two". You'd need to `ksort` this thing to get it to behave like a normal bog-standard boring array. 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.
- kingdomcome50 7y agoI disagree. The behavior you exhibit makes more sense than the behavior you imagine. 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.
- cliffy 7y agoThe problem is PHP calling an ordered map an array. Array in pretty much every other language means a sequence indexed by integers. Ideally the maintainers of PHP would rename it and deprecate the use of `array()` over a long period of time.
- wruza 7y ago>1) https://stackoverflow.com/questions/30076219/does-es6-introduce-a-well-defined-order-of-enumeration-for-object-properties https://stackoverflow.com/questions/30076219/does-es6-introd...
- lostcolony 7y ago>There's so many cases where it's a benefit for map entries to retain order (and none where it's a problem)' 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.
- coldtea 7y ago>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). 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.
- wrsh07 7y agoI think it's also worth noting that requiring an ordering is preventing a performance optimization 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)
- rossmohax 7y agoPython dicts are not ordered maps, they are dicts preserving insertion order.
- svnpenn 7y ago...thats the same thing. Maybe youre thinking about "sorted maps"?
- ebg13 7y agoIt's not the same thing. Compare two OrderedDicts that weren't constructed in the same order and the comparison will fail. Compare two dicts that weren't constructed in the same order and the comparison will pass. 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.
- skrebbel 7y agoGood point, but close enough! My points about how it makes the data structure more awesome stands. 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.
- reidrac 7y agoThe title of the post is misleading: it means "ordered by insertion order" (not sorted). 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-types-dict 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=ordereddict#ordereddict-objects https://docs.python.org/3/library/collections.html?highlight... Interesting!
- pavanky 7y ago> and immediately messed it up by mixing ordered maps with arrays into a big soup, but hey, PHP 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.
- skrebbel 7y agoIn JS's defense, it really tried as well. Fortunately though they failed harder at it, which is why arrays and objects are probably more different from one another than Eich had intended there in that mad 2 week language design frenzy. Good for us! 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"; After all, well, it works! Like in PHP! So what's the problem? :-) Most people felt the same way about these tutorials as people feel about monad tutorials nowadays. Good times!
- inopinatus 7y agoPoint of order: Ruby’s hashes do preserve insertion order. Python dicts are now the same.
- skrebbel 7y agoGood for Ruby! Nice to hear. 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 :)
- tene 7y agoCould you explain some examples of what this is useful for? What sort of algorithms or operations do you have in mind where you both want insertion order, and also key-based lookup in the same data structure? 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!
- ivalm 7y agoI think there is a lot of counters you might want both. 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])
- behindsight 7y agoI use ordered maps to keep track of state snapshots/patches of redux/mobx-state-tree stores. It allows me to both apply them sequentially as generated, or to "jump to" a particular point in time.
- mehrdadn 7y agoFor "algorithms", I mean, some really do care about insertion order. Like idk, if you have a priority queue, then you generally want FIFO ordering when the priority is the same? It like a pretty obvious desire in most cases... imagine a thread scheduler or a packet scheduler or what have you. 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.
- inimino 7y ago> JS objects are ordered maps 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.
- gsnedders 7y ago> 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... 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.
- inimino 7y agoI forgot about that when writing my comment but yes, V8 made that change along with "shadow classes" or whatever the object specialization stuff was called. Heady days for JS performance. 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.
- jrochkind1 7y agoRuby hashes are currently ordered and have been for quite a while now. Ruby 1.9 maybe? 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.
- jameshart 7y ago> There's so many cases where it's a benefit for map entries to retain order (and none where it's a problem) 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.