On Mon, Nov 9, 2009 at 3:50 PM, "Martin v. Löwis" <mar...@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>
_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com