Dictionary order?
Dan Stromberg
drsalists at gmail.com
Mon Aug 1 16:41:11 EDT 2022
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!
More information about the Python-list
mailing list