Alexander Belopolsky wrote:
On Mon, Nov 9, 2009 at 10:09 AM, Daniel Stutzbach daniel@stutzbachenterprises.com wrote:
On Mon, Nov 9, 2009 at 2:42 AM, "Martin v. Löwis" martin@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,
It does not:
s = set(range(100000)) from sys import getsizeof getsizeof(s)
4194536
while s: x = s.pop()
...
getsizeof(s)
4194536
s.clear() getsizeof(s)
232
Interestingly, it looks like there the sparseness check isn't triggering on addition of items either (when dictnotes.txt says it should):
from sys import getsizeof s = set(range(100000)) getsizeof(s)
2097264
while s: x = s.pop()
...
getsizeof(s)
2097264
s.add(1) getsizeof(s)
2097264
I did a similar test with dict.fromkeys and that also didn't resize until .clear() was invoked. I don't know the current criteria settings for the sparseness check, but it seems odd that going from 100k active keys to none wouldn't cause a resize...
Cheers, Nick.