3 ms·

Set membership checking is constant-time? Somehow I don't believe that.

• TorKlingberg 12y ago
  It's a hash table, so constant time lookup in the average case. It could be argued that it's actually O(log(n)), but it would not matter for any practical n.
• 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