RetroSearch Browse

Mon Nov 9 09:42:15 CET 2009 · https://mail.python.org/pipermail/python-dev/2009-November/093942.html

> The problem arises because we're systematically unbalancing the hash
> table.  The iterator returns the first valid entry in the hash table,
> which we remove.  Repeat several times and pretty soon the iterator has
> to spend O(n) time scanning through empty entries to find the first
> remaining valid entry.

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).

Regards,
Martin

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://mail.python.org/pipermail/python-dev/2009-November/093942.html below:

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