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

[Daniel Stutzbach]

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>