On Mon, Nov 9, 2009 at 2:42 AM, "Martin v. Löwis" <mar...@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>
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
