Proper deletion of selected items during map iteration in for loop: Thanks to all

[Roy Smith]

In article <535c67e9$0$29965$c3e8da3$5496439d at news.astraweb.com>,
 Steven D'Aprano <steve+comp.lang.python at pearwood.info> wrote:

> I think the two obviously good enough approaches are:
> 
> - save a "to be deleted" list, then delete those keys;
> 
> - copy the "not to be deleted" items into a new dict

There is a third possibility:

Iterate over the dict, storing keys to be deleted in a list, but break 
out after the list reaches N items.  Delete those keys from the dict.  
Repeat the whole process until you reach the end of the dictionary 
before you reach N saved keys.

It's going to take multiple (perhaps many) passes over the dict, but it 
will limit the amount of extra memory used.  In the extreme case, if 
N=1, with k keys in the dict, it will turn a process which is O(k) in 
time and O(k) in extra memory into one which is O(k^2) in time and O(1) 
in extra memory.  Is that a good tradeoff?  Only your hairdresser knows 
for sure.