[Python-Dev] Retrieve an arbitrary element from asetwithoutremoving it
Nick Coghlan
ncoghlan at gmail.com
Mon Nov 9 22:44:10 CET 2009
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
---------------------------------------------------------------
More information about the Python-Dev
mailing list