<div class="gmail_quote">On Mon, Nov 9, 2009 at 3:50 PM, "Martin v. Löwis" <span dir="ltr"><<a href="mailto:martin@v.loewis.de">martin@v.loewis.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I think for regular removal, the same logic should not apply: if a<br>
series of removals is performed, then further (non-pop) removals<br>
see increasing costs, as do regular lookups. So I think that a removal<br>
should trigger shrinking (with appropriate thresholds) unless it's a<br>
.pop.<br></blockquote></div><br>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.<br>
<br>(the above assumes a good hash function with few collisions, of course)<br><blockquote style="margin: 1.5em 0pt;">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</blockquote>