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

[Daniel Stutzbach]

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
> .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>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20091109/3736443f/attachment-0001.htm>