Alexander Belopolsky wrote: > On Mon, Nov 9, 2009 at 10:09 AM, Daniel Stutzbach > <dan...@stutzbachenterprises.com> wrote: >> 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, > > 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. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --------------------------------------------------------------- _______________________________________________ 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
