On Mon, Nov 9, 2009 at 3:50 PM, "Martin v. Löwis" <martin@v.loewis.de>wrote:
I think for regular removal, the same logic should not apply: if a series of removals is performed, then further (non-pop) removals see increasing costs, as do regular lookups. So I think that a removal should trigger shrinking (with appropriate thresholds) unless it's a .pop.
Minor technicality, but it's the next() operation of the iterator that has increasing cost as the set/dict becomes sparse. Removals are always O(1). The removal uses the hash to find the item quickly. The iterator has to scan through the table for non-empty entries. (the above assumes a good hash function with few collisions, of course) -- Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>