Hi Inada, On 10 August 2016 at 18:52, INADA Naoki <songofaca...@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. _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
