info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Dictionary order?
14 views
Skip to first unread message
Dan Stromberg
Aug 1, 2022, 4:41:47 PM8/1/22
to
Hi folks.
I'm still porting some code from Python 2.7 to 3.10.
As part of that, I saw a list being extended with a dict.values(), and
thought perhaps it wasn't ordered as intended on Python 2.7, even though
the problem would conceivably just disappear on 3.10.
So I decided to write a little test program to run on a variety of
CPythons, to confirm what I was thinking.
And instead I got a surprise.
On 1.4 through 2.1 I got descending key order. I expected the keys to be
scattered, but they weren't.
On 2.2 through 3.5 I got ascending key order. I expected the keys to be
scattered, but they weren't.
On 3.6 through 3.10 I got insertion order, as expected.
But why are 1.4 through 3.5 ordering so much? It's like they're a treap or
red-black tree or something. I'm pretty sure dict's used to be ordered in
a mostly-arbitrary way.
What am I missing?
Here's the little test program:
#!/usr/local/cpython-2.7/bin/python2
import sys
keys = [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7, 12, 11]
dict_ = {}
for key in keys:
dict_[key] = 1
if list(dict_.keys()) == keys:
# The order matches
print('compact')
sys.exit(0)
else:
# The order does not match
print('list(dict_): %s, keys: %s' % (list(dict_.keys()), keys))
sys.exit(1)
Here's some output (irrelevant python's deleted) when run under
https://stromberg.dnsalias.org/~strombrg/pythons/
/usr/local/cpython-1.4/bin/python (1.4) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-1.5/bin/python (1.5.2) bad list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-1.6/bin/python (1.6.1) bad list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.0/bin/python (2.0.1) bad list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.1/bin/python (2.1.0) bad list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.2/bin/python (2.2.0) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.3/bin/python (2.3.0) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.4/bin/python (2.4.0) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.5/bin/python (2.5.6) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.6/bin/python (2.6.9) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.7/bin/python (2.7.16) bad list(dict_): [1, 2, 4, 5,
6, 7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.0/bin/python (3.0.1) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.1/bin/python (3.1.5) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.2/bin/python (3.2.5) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.3/bin/python (3.3.7) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.4/bin/python (3.4.8) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.5/bin/python (3.5.5) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.6/bin/python (3.6.13) good compact
/usr/local/cpython-3.7/bin/python (3.7.0) good compact
/usr/local/cpython-3.8/bin/python (3.8.0) good compact
/usr/local/cpython-3.9/bin/python (3.9.0) good compact
/usr/local/cpython-3.10/bin/python (3.10.0) good compact
BTW, usually with pythons (the script which can be found at the URL above),
a little test program will be written to exit shell-true for success or
shell-false for failure. But in this case I'm using the exit code not as
success+failure but as compact+notcompact.
Why are those keys so ordered?
Also, I realize that the keys could come up ordered somehow by accident,
but I tried with 30 values (not just 12), and still got the same
weirdness. Naturally, as the number of key-value pairs goes up, the chance
of accidental ordering goes way down.
Thanks for reading!
I'm still porting some code from Python 2.7 to 3.10.
As part of that, I saw a list being extended with a dict.values(), and
thought perhaps it wasn't ordered as intended on Python 2.7, even though
the problem would conceivably just disappear on 3.10.
So I decided to write a little test program to run on a variety of
CPythons, to confirm what I was thinking.
And instead I got a surprise.
On 1.4 through 2.1 I got descending key order. I expected the keys to be
scattered, but they weren't.
On 2.2 through 3.5 I got ascending key order. I expected the keys to be
scattered, but they weren't.
On 3.6 through 3.10 I got insertion order, as expected.
But why are 1.4 through 3.5 ordering so much? It's like they're a treap or
red-black tree or something. I'm pretty sure dict's used to be ordered in
a mostly-arbitrary way.
What am I missing?
Here's the little test program:
#!/usr/local/cpython-2.7/bin/python2
import sys
keys = [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7, 12, 11]
dict_ = {}
for key in keys:
dict_[key] = 1
if list(dict_.keys()) == keys:
# The order matches
print('compact')
sys.exit(0)
else:
# The order does not match
print('list(dict_): %s, keys: %s' % (list(dict_.keys()), keys))
sys.exit(1)
Here's some output (irrelevant python's deleted) when run under
https://stromberg.dnsalias.org/~strombrg/pythons/
/usr/local/cpython-1.4/bin/python (1.4) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-1.5/bin/python (1.5.2) bad list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-1.6/bin/python (1.6.1) bad list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.0/bin/python (2.0.1) bad list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.1/bin/python (2.1.0) bad list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.2/bin/python (2.2.0) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.3/bin/python (2.3.0) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.4/bin/python (2.4.0) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.5/bin/python (2.5.6) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.6/bin/python (2.6.9) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.7/bin/python (2.7.16) bad list(dict_): [1, 2, 4, 5,
6, 7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.0/bin/python (3.0.1) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.1/bin/python (3.1.5) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.2/bin/python (3.2.5) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.3/bin/python (3.3.7) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.4/bin/python (3.4.8) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.5/bin/python (3.5.5) bad list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.6/bin/python (3.6.13) good compact
/usr/local/cpython-3.7/bin/python (3.7.0) good compact
/usr/local/cpython-3.8/bin/python (3.8.0) good compact
/usr/local/cpython-3.9/bin/python (3.9.0) good compact
/usr/local/cpython-3.10/bin/python (3.10.0) good compact
BTW, usually with pythons (the script which can be found at the URL above),
a little test program will be written to exit shell-true for success or
shell-false for failure. But in this case I'm using the exit code not as
success+failure but as compact+notcompact.
Why are those keys so ordered?
Also, I realize that the keys could come up ordered somehow by accident,
but I tried with 30 values (not just 12), and still got the same
weirdness. Naturally, as the number of key-value pairs goes up, the chance
of accidental ordering goes way down.
Thanks for reading!
Skip Montanaro
Aug 1, 2022, 4:49:18 PM8/1/22
to
>
> So I decided to write a little test program to run on a variety of
> CPythons, to confirm what I was thinking.
>
> And instead I got a surprise.
>
> On 1.4 through 2.1 I got descending key order. I expected the keys to be
> scattered, but they weren't.
>
> On 2.2 through 3.5 I got ascending key order. I expected the keys to be
> scattered, but they weren't.
>
> On 3.6 through 3.10 I got insertion order, as expected.
>
> But why are 1.4 through 3.5 ordering so much?
>
That's long in the past, but I seem to recall that key order was
> So I decided to write a little test program to run on a variety of
> CPythons, to confirm what I was thinking.
>
> And instead I got a surprise.
>
> On 1.4 through 2.1 I got descending key order. I expected the keys to be
> scattered, but they weren't.
>
> On 2.2 through 3.5 I got ascending key order. I expected the keys to be
> scattered, but they weren't.
>
> On 3.6 through 3.10 I got insertion order, as expected.
>
> But why are 1.4 through 3.5 ordering so much?
>
unspecified. That would give the implementer (likely Tim Peters much of the
time) the freedom to do whatever worked best for performance or simplicity
of implementation.
Skip
>
Chris Angelico
Aug 1, 2022, 5:09:35 PM8/1/22
to
will begin randomizing them with Python 3.3. But other than strings,
it's always been "arbitrary" rather than "random".
ChrisA
Dan Stromberg
Aug 1, 2022, 5:24:43 PM8/1/22
to
On Mon, Aug 1, 2022 at 1:41 PM Dan Stromberg <drsa...@gmail.com> wrote:
> On 1.4 through 2.1 I got descending key order. I expected the keys to be
> scattered, but they weren't.
>
I just noticed that 1.4 was ascending order too - so it was closer to 2.2
> On 1.4 through 2.1 I got descending key order. I expected the keys to be
> scattered, but they weren't.
>
than 1.5.
I guess that's kind of beside the point though - it's still more ordered
than I'd've expected.
2QdxY4Rz...@potatochowder.com
Aug 1, 2022, 5:47:30 PM8/1/22
to
On 2022-08-01 at 13:41:11 -0700,
Python 3.10.5 (main, Jun 6 2022, 18:49:26) [GCC 12.1.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> [hash(x) for x in range(20)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Just sayin'. :-)
Dan Stromberg <drsa...@gmail.com> wrote:
> keys = [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7, 12, 11]
>
> dict_ = {}
> for key in keys:
> dict_[key] = 1
$ python
> keys = [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7, 12, 11]
>
> dict_ = {}
> for key in keys:
> dict_[key] = 1
Python 3.10.5 (main, Jun 6 2022, 18:49:26) [GCC 12.1.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> [hash(x) for x in range(20)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Just sayin'. :-)
Chris Angelico
Aug 1, 2022, 5:51:24 PM8/1/22
to
for small integers have been themselves for as long as I can remember.
But the behaviour of the dictionary, when fed such keys, is what's
changed.
ChrisA
2QdxY4Rz...@potatochowder.com
Aug 1, 2022, 6:24:49 PM8/1/22
to
On 2022-08-02 at 07:50:52 +1000,
I'm not disputing either of those facts. I'm pointing out that the
apparently arbitrary order of a mapping's keys becomes obvious when you
look at the hashes of those keys.
apparently arbitrary order of a mapping's keys becomes obvious when you
look at the hashes of those keys.
Dan Stromberg
Aug 1, 2022, 7:43:31 PM8/1/22
to
list(range(250, 260))
But i == hash(i) holds for the first million values at least.
Dan Stromberg
Aug 1, 2022, 7:47:23 PM8/1/22
to
On Mon, Aug 1, 2022 at 4:42 PM Dan Stromberg <drsa...@gmail.com> wrote:
>
> > Yes, but I'm pretty sure that's been true for a LONG time. The hashes
>> > for small integers have been themselves for as long as I can remember.
>> > But the behaviour of the dictionary, when fed such keys, is what's
>> > changed.
>>
>> I'm not disputing either of those facts. I'm pointing out that the
>> apparently arbitrary order of a mapping's keys becomes obvious when you
>> look at the hashes of those keys.
>>
>
> It looks like the relationship no longer holds at around keys =
> list(range(250, 260))
>
> But i == hash(i) holds for the first million values at least.
>
I could've been more clear. int dict keys stop being stored-in-order at
>
> > Yes, but I'm pretty sure that's been true for a LONG time. The hashes
>> > for small integers have been themselves for as long as I can remember.
>> > But the behaviour of the dictionary, when fed such keys, is what's
>> > changed.
>>
>> I'm not disputing either of those facts. I'm pointing out that the
>> apparently arbitrary order of a mapping's keys becomes obvious when you
>> look at the hashes of those keys.
>>
>
> It looks like the relationship no longer holds at around keys =
> list(range(250, 260))
>
> But i == hash(i) holds for the first million values at least.
>
near 256.
But i == hash(i) holds for the first million values, and probably more.
This suggests to me that there's something more than i == hash(i) going on
inside dict's - but it doesn't much matter what it is for my purposes.
Weatherby,Gerard
Aug 1, 2022, 9:15:12 PM8/1/22
to
I don’t see what is surprising. The interface for a dictionary never specified the ordering of the keys, so I would not be surprised to see it vary based on release, platform, values of keys inserted, number of items in the dictionary, etc.
—
Gerard Weatherby | Application Architect NMRbox | NAN | Department of Molecular Biology and Biophysics
UConn Health 263 Farmington Avenue, Farmington, CT 06030-6406 uchc.edu
On Aug 1, 2022, 7:48 PM -0400, Dan Stromberg <drsa...@gmail.com>, wrote:
*** Attention: This is an external email. Use caution responding, opening attachments or clicking on links. ***
--
https://urldefense.com/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!j3p_Aq5MoGqDk5XMsKb4SKs3U1nfuMOx0wVkSa_hbURJ22w6lP8NrCOc_PYAfELYOdVlC9x6JzLfIMIw5sLe$
—
Gerard Weatherby | Application Architect NMRbox | NAN | Department of Molecular Biology and Biophysics
UConn Health 263 Farmington Avenue, Farmington, CT 06030-6406 uchc.edu
On Aug 1, 2022, 7:48 PM -0400, Dan Stromberg <drsa...@gmail.com>, wrote:
*** Attention: This is an external email. Use caution responding, opening attachments or clicking on links. ***
https://urldefense.com/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!j3p_Aq5MoGqDk5XMsKb4SKs3U1nfuMOx0wVkSa_hbURJ22w6lP8NrCOc_PYAfELYOdVlC9x6JzLfIMIw5sLe$
0 new messages