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

[Dmitry Vasiliev]

Philipp von Weitershausen wrote:
> 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.

...or if you repeat the operation for many times.

> This is what I did quickly on the interpreter shell:
[SKIP]

It's better to test small snippets of code with the timeit module instead of 
the profile module. For example with the code:

from timeit import Timer

keys = [str(i) for i in range(11)]

code = """
for s in keys:
     s in c
"""

lst = [str(i) for i in range(10)]
map = dict.fromkeys(lst)

t1 = Timer(code, "from __main__ import keys, lst as c")
t2 = Timer(code, "from __main__ import keys, map as c")

print "List:", t1.repeat()
print "Dict:", t2.repeat()

I've got the following results:

List: [3.8474152441162213, 3.8472666218751264, 3.8494990285078119]
Dict: [1.783690664595639, 1.7893994907173969, 1.8036929274530724]

> 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.

I think it's always better use a mapping if you need membership testing 
operation if possible, since you will have practically constant lookup time.

-- 
Dmitry Vasiliev (dima at hlabs.spb.ru)
     http://hlabs.spb.ru