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

Python dicts are now ordered

softwaremaniacs.org

Post reply on HN
Print view View original

431–440 of 457 posts

Re: Python dicts are now ordered

#431

Post by gsnedders »

inimino wrote: post #395
gsnedders wrote: post #332

Earlier quoted context omitted.

> 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.…

I 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.

SpiderMonkey actually had inline caches before V8 shipped if I'm not mistaken; the motivating factor for the behaviour change in V8 was just to improve the cache-hit ratio.

Re: Python dicts are now ordered

#432

Post by philwelch »

zo1 wrote: post #418
philwelch wrote: post #354

Earlier quoted context omitted.

If a human is inspecting serialized JSON using pen and paper, the human is presumably clever enough to match up key for key regardless of ordering. 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 lexic…

Most diff programs don't have what you describe. And in a lot of cases you don't have the easy ability to "do stuff" before running the input through a diffing algorithm.

> Most diff programs don't have what you describe.

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.

Re: Python dicts are now ordered

#433

Post by d0mine »

user5994461 wrote: post #352
d0mine wrote: post #318

Earlier quoted context omitted.

BDFL declared Python dict to be ordered in 2017 — It can't be more official than that for Python https://mail.python.org/pipermail/python-dev/2017-December/1... i.e., Python 3.7 (whatever implementation must keep the insertion order). CPython keeps the order since Python 3.6. Pypy even before that.

A barely legible email dump with 50 concurrent answers is supposed to be the clear official statement? 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.

The ruling is the very first and only line from the link:

> Make it so. "Dict keeps insertion order" is the ruling. Thanks!

Re: Python dicts are now ordered

#434

Post by jameshart »

skrebbel wrote: post #223

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-acciden…

> 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.

Re: Python dicts are now ordered

#435

Post by tyingq »

zeroimpl wrote: post #389
cliffy wrote: post #306

Earlier quoted context omitted.

The 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.

The PHP documentation refers to them as "associative arrays", which is technically correct, but I agree I'm not sure how they could have conflated these concepts so badly.

I believe the "associative array" terminology came from Perl. Though Perl's associative arrays don't have any guaranteed order. And Perl also has normal arrays.

Re: Python dicts are now ordered

#436

Post by jameshart »

Rapzid wrote: post #384
ummonk wrote: post #380

Wait, if it is held in a separate dense array, is removal of a key from a dictionary O(N)?

You 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.

Great, you recovered the memory. But now you have to update all the pointers to the array in the hashmap....

Re: Python dicts are now ordered

#437

Post by jameshart »

dilap wrote: post #391
ummonk wrote: post #380

Wait, if it is held in a separate dense array, is removal of a key from a dictionary O(N)?

You 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.)

Brilliant: Now your map contains an allocator and a garbage collector.

Re: Python dicts are now ordered

#438

Post by jakear »

fctorial wrote: post #423
gruez wrote: post #400

Earlier quoted context omitted.

so now you have to install a specific python version for your script to work?

Only if you're using version specific features.

What happens when python 3.8 comes out? Everybody needs to go into your script to change the hashbang every time a new release comes?

Re: Python dicts are now ordered

#440

Post by kragen »

thedirt0115 wrote: post #295
MereInterest wrote: post #204

Earlier quoted context omitted.

Sounds like a fast and idiomatic way to shuffle a deck of cards is then to convert to a map and back.

Convert a deck of cards ([]Card?) to a map (map[Card]bool?) and back just to shuffle? That's unlikely to be faster or more idiomatic than a straightforward implementation of the Fisher-Yates shuffle[1]. Try writing the code to do it both ways and compare. [1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

I think "idiomatic" would be using rand.Perm, which implements the Fisher%E2%80%93Yates shuffle. But aside from whether it's idiomatic, converting to a map isn't random enough.
Post reply on HN