Why searching in a set is much faster than in a list ?

[Christian Gollwitzer]

Am 28.09.16 um 07:51 schrieb ast:
> Hello
>
> I noticed that searching in a set is faster than searching in a list.

Because a set is a hashtable, which has constant-time lookup, whereas in 
a list it needs to compare with every element.

> from timeit import Timer
> from random import randint
>
> l = [i for i in range(100)]
> s = set(l)

Try longer lists/sets and the difference should increase.

	Christian

> t1 = Timer("randint(0, 200) in l", "from __main__ import l, randint")
> t2 = Timer("randint(0, 200) in s", "from __main__ import s, randint")
>
> t1.repeat(3, 100000)
> [1.459111982109448, 1.4568229341997494, 1.4329947660946232]
>
> t2.repeat(3, 100000)
> [0.8499233841172327, 0.854728743457656, 0.8618653348400471]
>
> I tried a search in a tuple, it's not different that in a list.
> Any comments ?