[Python-Dev] PEP 468

[Nathaniel Smith]

On Jun 13, 2016 6:16 PM, "MRAB" <python at mrabarnett.plus.com> wrote:
>
> On 2016-06-14 01:47, Larry Hastings wrote:
>>
>> On 06/13/2016 05:05 PM, MRAB wrote:
>>>
>>> This could be avoided by expanding the items to include the index of
>>> the 'previous' and 'next' item, so that they could be handled like a
>>> doubly-linked list.
>>>
>>> The disadvantage would be that it would use more memory.
>>
>>
>> Another, easier technique: don't fill holes.  Same disadvantage
>> (increased memory use), but easier to write and maintain.
>>
> When iterating over the dict, you'd need to skip over the holes, so it
would be a good idea to compact it a some point, when there are too many
holes.

Right -- but if you wait for some ratio of holes to filled space before
compacting, you can amortize the cost down, and have a good big-O
complexity for both del and iteration simultaneously. Same basic principle
as using proportional overallocation when appending to a list, just in
reverse.

I believe this is what pypy's implementation actually does.

-n
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20160613/76158ad7/attachment.html>