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

441–450 of 457 posts

Re: Python dicts are now ordered

#441

Post by kragen »

kragen wrote: post #440
thedirt0115 wrote: post #295

Earlier quoted context omitted.

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.

With Golang 1.11, I get orderings like this. S is spades, H is hearts, D is diamonds, and C is clubs, because HN eats the Unicode characters I was actually using.

     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
On average you would expect about one card in a shuffled deck to be (cyclically) followed in the deck by its succeeding card, and on about one out of 50 shuffles, that card would be followed by its successor. Here we have S4 S5, DA D2, SA S2 S3, and D5 D6 D7.

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.

Re: Python dicts are now ordered

#442

Post by kragen »

jarekkruk wrote: post #289
kragen wrote: post #228

Earlier quoted context omitted.

No, it isn't random enough for that.

IIRC it used to just start iteration at a pseudorandom index and then iterate normally. I looked at it couple years ago, don't know if they changed it.

It seems to do that, but I think it also tweaks the hash function for each newly created map, because in the code linked from https://news.ycombinator.com/item?id=22278753 I'm not getting rotations of the same iteration order when I generate two maps. There doesn't seem to be any randomness in mapiternext() itself.

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.

Re: Python dicts are now ordered

#443

Post by gerikson »

jonreem wrote: post #200
_aleph2c_ wrote: post #144

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

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

Sometimes they're just concern trolls though.

Re: Python dicts are now ordered

#444

Post by mattkrause »

zeroimpl wrote: post #387
mattkrause wrote: post #333

Earlier quoted context omitted.

In that situation, Matlab allocates an array of length 3, fills it with “empty” values (depending on the type), and then sets the third element to the value. That’s what I’d have expected to happen here too...

Would you expect it to do that if somebody wrote the following? $id = 12835151; $arr[$id] = Get_thing_with_id( $id );

If $arr were an array I would, though I'd cringe at the wasted space (unless it were a sparse array).

Obviously, I'd agree that a map/associative array/dict/etc is a better choice here; I'm just annoyed about the name.

Re: Python dicts are now ordered

#445

Post by gerikson »

zwp wrote: post #177
drngdds wrote: post #128

Earlier quoted context omitted.

I haven't done a ton of Python, but I can't really think of a situation where relying on a dict to be ordered is an easy mistake to make. Do you have an example?

I saw this in Perl a long time ago but it could just as easily have happened in Python. The dict (Perl hash) was a set of mappings for template replacement of "from" strings to "to" strings. "FOO" => "bar" # Replace FOO with bar The author had considered the case where one key (FOO) might be a left-substring of another (FOOBAR), and so reversed the output from keys() before iterating over the hash. This ensured that…

The Perl example sounds like someone incorrectly assuming that the output from `keys` be ordered, when it's explicitely not:

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

Re: Python dicts are now ordered

#446

Post by gerikson »

oefrha wrote: post #25

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

Probably because it was posted to lobste.rs and got good traction there:

https://lobste.rs/s/htcz5f

Re: Python dicts are now ordered

#447

Post by strenholme »

wruza wrote: post #401
strenholme wrote: post #361

Earlier quoted context omitted.

What Lua is lacking here (and why the above iterator function needs 17 lines) is the ability to have “for” go through a list ( without converting the list in to values returned by an iterator function), which would let us quickly and easily sort lists that “for” can use. Something like: d = {"foo": 2, "bar": 1, "zoo": 4} for k in sorted(d.keys()): print k (I’m not advocating Python here, since Perl has a similar way…

You can convert a list first and then feed it to a simple iterator. I don’t fully understand what your exact real-code issues can be, but hope this snippet may help: 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) I.e. if “natively” means strictly “for in t” that generates values, then no, Lua can’t do that…

That looks good, and I think putting these in a prominent place of the Lua documentation (along with a notice that the code is public domain) would help us who are used to the AWK/Perl/Python/PHP way of having “for” natively traverse a list without needing a complicated list-to-iterator function that uses function closure (i.e. the iterator function remembers the value “i” -- I’m writing this for the lurkers because code like this can be difficult to follow).

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
I’m curious why we’re returning both the table element for the iterator and the entire table.

Re: Python dicts are now ordered

#448

Post by Aachen »

orf wrote: post #421
Aachen wrote: post #416

Earlier quoted context omitted.

If I rely on a python version and I expect other people to use it, I add a version if statement on top. I hate those packaging tools that insist on installing stuff in your system and create a frankendebian when really all I want to do is run a single py file standalone once. Often have to do chenanigans like "python3 -c 'from sometool import __app__'". If you want to install it, go ahead and copy or symlink it in yo…

Yes, a failure to understand how your tools work or how to use them effectively does indeed make things harder.

Well I know how my tools work, I don't know how this custom file works that is duplicated and delivered with each project.

Re: Python dicts are now ordered

#449

Post by orf »

Aachen wrote: post #448
orf wrote: post #421

Earlier quoted context omitted.

Yes, a failure to understand how your tools work or how to use them effectively does indeed make things harder.

Well I know how my tools work, I don't know how this custom file works that is duplicated and delivered with each project.

> I don't know how this custom file works that is duplicated and delivered with each project.

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.

1. https://github.com/pipxproject/pipx

Re: Python dicts are now ordered

#450

Post by Dylan16807 »

mypalmike wrote: post #321
baddox wrote: post #240

Earlier quoted context omitted.

That's generally what people mean when they say "nondeterministic" in the context of computing. Yeah, in philosophy it generally means something like "the future is not completely determined by the past," but in computing it means something closer to "the programmer cannot reasonably determine the behavior and thus should not depend on specific behavior."

In computing it means a given set of inputs lead to a given set of outputs. It has nothing to do with how difficult it is for a programmer to reason about. Deterministic builds, deterministic tests, etc.

But what counts as "input" will vary based on who you ask and under what context.
Post reply on HN