GC is very expensive: am I doing something wrong?

Paul Rubin no.email at nospam.invalid
Tue Mar 23 09:17:32 CET 2010


Steven D'Aprano <steven at REMOVE.THIS.cybersource.com.au> writes:
> Well, perhaps one order of magnitude.
>>>> for i in xrange(100):
> ...     n = 32*i+1
> ...     assert hash(2**n) == hash(2)

Try with much more than 100 items (you might want to construct the
entries a little more intricately to avoid such big numbers).  The point
is that access becomes O(N) instead of O(1).  See:

   http://www.cs.rice.edu/~scrosby/hash/

for the consequences.  http://cr.yp.to/critbit.html  discusses the
issue a little more.



More information about the Python-list mailing list