Converting a set into list

[Roy Smith]

In article 
<34fc571c-f382-405d-94b1-0a673da5f46b at t16g2000vbi.googlegroups.com>,
 SigmundV <sigmundv at gmail.com> wrote:

> I think the OP wants to find the intersection of two lists.
> list(set(list1) & set(list2)) is indeed one way to achieve this. [i
> for i in list1 if i in list2] is another one.

Both ways work, but the first is O(n) and the second is O(n^2).

import time
n = 10000
list1 = range(n)
list2 = range(n)
t0 = time.time()
list(set(list1) & set(list2))
t1 = time.time()
print "list(set) method took %f seconds" % (t1 - t0)
t0 = time.time()
[i for i in list1 if i in list2]
t1 = time.time()
print "loop method took %f seconds" % (t1 - t0)


./intersect.py 100000
list(set) method took 0.004791 seconds
loop method took 1.437322 seconds