Python Speed: ‘x in list’ vs ‘x in set’
Well, this is my second post about speed in Python. Today, I noticed that debimg’s dependency resolver was much much slower than before. I thought what the problem could be and finally realized that the problem was that I switched from sets to list. This is fixed now in commit d0fd700080de5c19cb5fd66918d14c5ffa26e805
Now, some benchmarks (using IPython):
In : a = range(10**6)
In : b = set(a)
In : %timeit 10**6 in a
10 loops, best of 3: 31.8 ms per loop
In : %timeit 10**6 in b
10000000 loops, best of 3: 98.6 ns per loop
1ms are 1 million ns. Therefore, using sets is about 322515 times faster than using lists (or tuples).
debimg can now calculate dependencies in 0.5 seconds again, instead of 1 minute with lists.