Set is much faster than list while lookup for membership

Question

How set is much much faster in lookup for an element than list, is that something to do with the ordered maintain in list ? or is the lookup algorithm is different in set than list ?

>>> from timeit import Timer    
>>> Timer("100042 in L", "L=range(100000)").timeit(number=10000)
21.69940710067749
>>>
>>> Timer("100042 in S", "S=set(range(100000))").timeit(number=10000)
0.0006740093231201172
>>>

Some one pleae point me out any link or algorithm used between the two ?

thefourtheye · Accepted Answer · 2013-12-12T08:16:17.253

7

set uses hashing (it allows only items which are hashable), which will be much faster than list's sequential access, for random lookup.

But, list might beat set, if the item being searched is at the beginning.

from timeit import Timer
print Timer("0 in L", "L=range(100000)").timeit(number=10000)
print Timer("0 in S", "S=set(range(100000))").timeit(number=10000)

Output on my machine

0.00127078635541
0.00143169642464

Edit: Time complexity of different operations on various objects are documented here. Thanks @mgilson :)

edited Dec 12 '13 at 08:16

answered Dec 12 '13 at 07:56

thefourtheye

233,700
52
457
497

1

@KDawG, hi, there is a similar question [How is CPython's set() implemented?](http://stackoverflow.com/questions/3949310/how-is-cpythons-set-implemented) – flyer Dec 12 '13 at 08:00
@KDawG Included reference in the solution. Please check now. – thefourtheye Dec 12 '13 at 08:01
Ah, set doesn't allow non-hashable member >>> s = set([1,[1,2,3]]) Traceback (most recent call last): File "", line 1, in TypeError: unhashable type: 'list' >>> – James Sapam Dec 12 '13 at 08:03
@thefourtheye now looks complete :) – K DawG Dec 12 '13 at 08:11
@mgilson Thanks :) Added that also in the answer :) – thefourtheye Dec 12 '13 at 08:16

Set is much faster than list while lookup for membership

1 Answers1