[Python-Dev] Add __reversed__ methods for dict

[INADA Naoki]

On Sun, May 27, 2018 at 12:43 PM Raymond Hettinger <
raymond.hettinger at gmail.com> wrote:


> > On May 26, 2018, at 7:20 AM, INADA Naoki <songofacandy at gmail.com> wrote:
> >
> > Because doubly linked list is very memory inefficient, every
implementation
> > would be forced to implement dict like PyPy (and CPython) for
efficiency.
> > But I don't know much about current MicroPython and other Python
> > implementation's
> > plan to catch Python 3.6 up.

> FWIW, Python 3.7 is the first Python that where the language guarantees
that regular dicts are order preserving.  And the feature being discussed
in this thread is for Python 3.8.


Oh, my mistake.

> What potential implementation obstacles do you foresee?  Can you imagine
any possible way that an implementation would have an order preserving dict
but would be unable to trivially implement __reversed__?  How could an
implementation have a __setitem__ that appends at the end, and a popitem()
that pops from that same end, but still not be able to easily iterate in
reverse?  It really doesn't matter whether an implementer uses a dense
array of keys or a doubly-linked-list; either way, looping backward is as
easy as going forward.


I thought `popitem()` removes the last item is still implementation detail.
So I thought about hashmap + single linked list.  When removing item, dummy
entry will be kept in the list.
The dummy entry in the list will be removed when iterating over the list,
or rebuilding hashmap.

FWIW, quick survey of other languages hashmap implementations and APIs are:

# PHP

PHP 5 used hashmap + doubly linked list.  PHP 7 uses Python-like
implementation.

While PHP doesn't have reverse iterator, there are `end()` and `prev()`
which can be used
to iterate backwards.

# Ruby

 From Ruby 1.9, Hash is ordered.  At the time, implementation is hashmap +
doubly linked list.
 From Ruby 2.4, Python-like implementation.

There are `Enumereble.reverse_each` API.  But the API is documented as
"Builds a temporary array and traverses that array in reverse order."
So Ruby seems allow other implementation which doesn't have zerocopy
reverse iterator.
(I don't know CRuby provides it or not.)

http://ruby-doc.org/core-2.2.2/Enumerable.html#method-i-reverse_each

# Java

The LinkedHashMap document says " it maintains a doubly-linked list ".
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

On the other hand, there are no reverse iterator API.
So if we require `__reverse__` for dict, Jython can't use LinkedHashMap as
backend of dict.

# C# (.Net)

There are legacy (non generic) OrderedDict.  It's `remove()` seems O(n)
implementation.
https://referencesource.microsoft.com/#System/compmod/system/collections/specialized/ordereddictionary.cs,bc8d8035ee2d2927

# Rust, Swift, and Go

Builtin mapping is arbitrary ordered, and there is no ordered mapping in
the standard library.

---

It seems:

* There are no single linked list based OrderedDict implementation, but
* Only PHP exposes "zerocopy reverse iterate" API.

I may be wrong because I'm not expert of these languages.  Please point out
if I am wrong.


> Raymond


> P.S. It isn't going to be hard to update MicroPython to have a compact
and ordered dict (based on my review of their existing dict
implementation).  This is something they are really going to want because
of the improved memory efficiency.  Also, they're also already going to
need it just to comply with guaranteed keyword argument ordering and
guaranteed ordering of class dictionaries.

Thanks.

Sadly speaking, Jython and IronPython development seems very slow and "wait
until 3.9" may be
not long enough for they catch Python 3.7 up.

When focusing to CPython, PyPy and MicroPython, no problem for adding
__reverse__ in 3.8 seems OK.

Regards,

-- 
INADA Naoki  <songofacandy at gmail.com>