Showing content from http://mail.python.org/pipermail/python-dev/attachments/20091109/e9b61dac/attachment.htm below:
<div class="gmail_quote">On Mon, Nov 9, 2009 at 2:42 AM, "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;">
Interesting. Something goes wrong, it seems: if items get removed over<br>
and over again, I think the set should shrink (not sure whether it<br>
actually does). Then, I think you should end up with an amortized O(1)<br>
for selecting an element (assuming that the underlying hashes don't<br>
collide).<br></blockquote></div><br>I'm not sure if Python's implementation shrinks or not, but even if it did shrink, it would still be amortized O(n).<br><br>Imagine a completely full hash table that currently contains n elements in n slots (I know this cannot happen in Python's implementation but it's useful for illustrative purposes). Assume it will shrink when it gets down to n/2 elements.<br>
<br>Here is my pathological algorithm again, for reference purposes:<br><br>while s:<br>Â Â Â for i in s:<br>
       break<br>   # Imagine a complex algorithm here that depends on i still being in s<br>   s.remove(i)<br><br>We repeatedly search through the slots sequentially and remove the first element we find. The first removal requires checking 1 slot, the second removal requires checking 2 slots, the third removal requires checking 3 slots, and so forth. The hash table will shrink after the n/2-th removal, when we have checked 1 + 2 + 3 + ... + n/2 = O(n**2) slots for n/2 removals (or amortized O(n) per removal). It's too late for shrinking to save us; we've already performed too much work.<br>
<blockquote style="margin: 1.5em 0pt;">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</blockquote>
RetroSearch is an open source project built by @garambo
| Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4