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

[ast]

"ast" <nomail at com.invalid> a écrit dans le message de news:57eb5a4a$0$3305$426a74cc at news.free.fr...
> Hello
>
> I noticed that searching in a set is faster than searching in a list.
>
> from timeit import Timer
> from random import randint
>
> l = [i for i in range(100)]
> s = set(l)
>
> 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 ?

I tried in an array which is supposed to be an optimised list, but it is slightly
slower

from array import array

a = array('H', [i for i in range(100)])
t3 = Timer("randint(0, 200) in a", "from __main__ import a, randint")

t3.repeat(3, 100000)
[1.6311116356968114, 1.638082912772461, 1.6018925589704622]