[Python-Dev] Retrieve an arbitrary element from asetwithoutremoving it

"Martin v. Löwis" martin at v.loewis.de
Mon Nov 9 23:39:04 CET 2009


> We repeatedly search through the slots sequentially and remove the first
> element we find.  The first removal requires checking 1 slot, the second
> removal requires checking 2 slots, the third removal requires checking 3
> slots, and so forth.  The hash table will shrink after the n/2-th
> removal, when we have checked 1 + 2 + 3 + ... + n/2 = O(n**2) slots for
> n/2 removals (or amortized O(n) per removal).  It's too late for
> shrinking to save us; we've already performed too much work.

Ah, right.

Perhaps people writing the loop the way you proposed deserve to get bad
performance, as they should use .pop in the first place.

Regards,
Martin


More information about the Python-Dev mailing list