ncoghlan at gmail
Nov 9, 2009, 1:44 PM
Post #1 of 1
(254 views)
Permalink
|
|
Re: Retrieve an arbitrary element from asetwithoutremoving it
|
|
Alexander Belopolsky wrote:
> On Mon, Nov 9, 2009 at 10:09 AM, Daniel Stutzbach
> <daniel [at] stutzbachenterprises> wrote:
>> On Mon, Nov 9, 2009 at 2:42 AM, "Martin v. Löwis" <martin [at] v>
>> 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 | Brisbane, Australia
---------------------------------------------------------------
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com
|
