[Python-Dev] PEP 487: Simpler customization of class creation

[Raymond Hettinger]

> On Jun 21, 2016, at 10:18 AM, Guido van Rossum <guido at python.org> wrote:
> 
> Judging from Inada's message there seems to be some confusion about how well the compact dict preserves order (personally I think if it doesn't guarantee order after deletions it's pretty useless).

Inada should follow PyPy's implementation of the compact dict which does preserve order after deletions (see below).

My original proof-of-concept code didn't have that feature; instead, it was aimed at saving space and speeding-up iteration.  The key ordering was just a by-product.  Additional logic was needed to preserve order for interleaved insertions and deletions.


Raymond


---(PyPy test of order preservation)-------------------------------------------------------------

'Demonstrate PyPy preserves order across repeated insertions and deletions'

from random import randrange
import string

s = list(string.letters)
d = dict.fromkeys(s)
n = len(s)
for _ in range(10000):
    i = randrange(n)
    c = s.pop(i);    s.append(c)
    d.pop(c);        d[c] = None
    assert d.keys() == s


---(PyPy session showing order preservation)--------------------------------------------------

$ pypy
Python 2.7.10 (c09c19272c990a0611b17569a0085ad1ab00c8ff, Jun 13 2016, 03:59:08)
[PyPy 5.3.0 with GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>>> d = dict(raymond='red', rachel='blue', matthew='yellow')
>>>> del d['rachel']
>>>> d['cindy'] = 'green'
>>>> d['rachel'] = 'azure'
>>>> d
{'raymond': 'red', 'matthew': 'yellow', 'cindy': 'green', 'rachel': 'azure'}