[Python-Dev] Retrieve an arbitrary element from asetwithoutremoving it
daniel at stutzbachenterprises.com
Mon Nov 9 23:44:53 CET 2009
On Mon, Nov 9, 2009 at 3:50 PM, "Martin v. Löwis" <martin at 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
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>
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-Dev