3 ms·
Sets are basically hash tables that store only keys and not values. You can easily write your own Set implementation by subclassing `dict` and stripping out ref
by kstrauser 12y ago
Sets are basically hash tables that store only keys and not values. You can easily write your own Set implementation by subclassing `dict` and stripping out references to `.values()`, etc.
As such, testing for membership is an O(1) hash table lookup. If you're skeptical:
$ python -m timeit -s 'nums=range(1000000)' '100000 in nums'
1000 loops, best of 3: 1.4 msec per loop
$ python -m timeit -s 'nums=range(1000000)' '500000 in nums'
100 loops, best of 3: 7.15 msec per loop
$ python -m timeit -s 'nums=range(1000000)' '900000 in nums'
100 loops, best of 3: 13 msec per loop
$ python -m timeit -s 'nums=set(range(1000000))' '100000 in nums'
10000000 loops, best of 3: 0.0572 usec per loop
$ python -m timeit -s 'nums=set(range(1000000))' '500000 in nums'
10000000 loops, best of 3: 0.057 usec per loop
$ python -m timeit -s 'nums=set(range(1000000))' '900000 in nums'
10000000 loops, best of 3: 0.0584 usec per loop