Proper deletion of selected items during map iteration in for loop: Thanks to all
Roy Smith
roy at panix.com
Sat Apr 26 22:57:14 EDT 2014
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.
More information about the Python-list
mailing list