[Python-Dev] Retrieve an arbitrary element from asetwithoutremoving it (original) (raw)

Daniel Stutzbach daniel at stutzbachenterprises.com
Mon Nov 9 16:09:54 CET 2009

On Mon, Nov 9, 2009 at 2:42 AM, "Martin v. Löwis" <martin at v.loewis.de>wrote:

Interesting. Something goes wrong, it seems: if items get removed over and over again, I think the set should shrink (not sure whether it actually does). Then, I think you should end up with an amortized O(1) for selecting an element (assuming that the underlying hashes don't collide).

I'm not sure if Python's implementation shrinks or not, but even if it did shrink, it would still be amortized O(n).

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.

Here is my pathological algorithm again, for reference purposes:

while s: for i in s: break # Imagine a complex algorithm here that depends on i still being in s s.remove(i)

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.

-- 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/e9b61dac/attachment.htm>

More information about the Python-Dev mailing list