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

[Nick Coghlan]

Alexander Belopolsky wrote:
> On Mon, Nov 9, 2009 at 10:09 AM, Daniel Stutzbach
> <daniel at stutzbachenterprises.com> wrote:
>> On Mon, Nov 9, 2009 at 2:42 AM, "Martin v. Löwis" <martin at 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   |   ncoghlan at gmail.com   |   Brisbane, Australia
---------------------------------------------------------------