[Zope3-checkins] Re: SVN: Zope3/trunk/src/zope/tal/ The lists has been changed to dicts for faster membership testing

[Philipp von Weitershausen]

Stephan Richter wrote:
> On Thursday 21 April 2005 12:10, Dmitry Vasiliev wrote:
> 
>>Log message for revision 30078:
>>  The lists has been changed to dicts for faster membership testing
> 
> Did you do some profiling to see how much faster it is?

Dict lookup *is* faster than checking for list membership. However, this 
is only true on a large scale when you're dealing with >> 1000 members. 
This is what I did quickly on the interpreter shell:

   >>> import profile
   >>> x = map(str, range(1024*1024))  # 1 MiB list

Now test for list membership with an object that is definitely not in there:

   >>> profile.run("str(1024*1024) in x")
            3 function calls in 0.380 CPU seconds
       ...

I ran this three times and it always showed a number in the same range 
(about one third of a second).

Now let's make a dict out of ``x``:

   >>> d = dict.fromkeys(x)
   >>> profile.run("str(1024*1024) in d")
            3 function calls in 0.000 CPU seconds
       ...

I ran this three times as well and it always showed 0.000 seconds.

But again, this is with a huge list... I don't think the minimum of 
speed we gain with small lists (if any) justifies code indirection.

Philipp