[Python-Dev] Review request: issue 27350, compact ordered dict (original) (raw)

Armin Rigo arigo at tunes.org
Thu Aug 18 03:53:11 EDT 2016

Hi Inada,

On 10 August 2016 at 18:52, INADA Naoki <songofacandy at gmail.com> wrote:

a. dict has one additional word and support ring internally. b. OrderedDict reimplements many APIs (iterating, resizing, etc...) to support ring.

There is a solution "c." which might be simpler. Let's think first about what occurs with a normal dict (with your patch, or in PyPy) if the user repeatedly pops the oldest item and adds a new item. In this case, the dict will accumulate dead entries at the start of the list, and when it gets too many of them, it needs to make a complete copy of the list to get rid of them. (This is not a problem as it is amortized over many pop-and-add operations.)

So now, when the user calls move_to_end(last=False), we can do the opposite. We look if there are already some deleted entries at the start, and if so, we add the item at the place of the last deleted entry. If there aren't any, then we make a copy of the list that adds some number of entries at the start, which are initially marked as deleted...

A bientôt,

Armin.

More information about the Python-Dev mailing list