<p dir="ltr">On Jun 13, 2016 6:16 PM, "MRAB" <<a href="mailto:python@mrabarnett.plus.com">python@mrabarnett.plus.com</a>> wrote:<br>
><br>
> On 2016-06-14 01:47, Larry Hastings wrote:<br>
>><br>
>> On 06/13/2016 05:05 PM, MRAB wrote:<br>
>>><br>
>>> This could be avoided by expanding the items to include the index of<br>
>>> the 'previous' and 'next' item, so that they could be handled like a<br>
>>> doubly-linked list.<br>
>>><br>
>>> The disadvantage would be that it would use more memory.<br>
>><br>
>><br>
>> Another, easier technique: don't fill holes.  Same disadvantage<br>
>> (increased memory use), but easier to write and maintain.<br>
>><br>
> 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.</p>
<p dir="ltr">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.</p>
<p dir="ltr">I believe this is what pypy's implementation actually does.</p>
<p dir="ltr">-n</p>