> 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 _______________________________________________ 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
