Why does `myfloat in myset` become super slow?

user_16759116 0
Viewed 76

When I re-insert the same float value into my set a few times, the x in s check that should take constant time becomes very slow. Why?

Output of timing x in s:

   0.06 microseconds
   0.09 microseconds
   0.16 microseconds
   0.56 microseconds
   1.00 microseconds
   1.58 microseconds
   2.55 microseconds
   5.98 microseconds
  10.50 microseconds
  24.54 microseconds
  40.39 microseconds
  96.60 microseconds
 160.24 microseconds
 419.08 microseconds
 732.27 microseconds

Code (Try it online!):

from timeit import timeit

s = {float('nan')}
for _ in range(15):
    for _ in [*s]:
        x = float('nan')
        s.add(x)
    time = timeit('x in s', number=1000, globals=globals()) * 1e3
    print('%7.2f microseconds' % time)
set python performance
1 Answers

Because you are using nan, which is notorious for breaking naive expectations regarding __hash__/__eq__ contract... i.e.:

>>> myset = set()
>>> myset.add(float('nan'))
>>> myset
{nan}
>>> myset.add(float('nan'))
>>> myset
{nan, nan}

This happens because:

>>> float('nan') == float('nan')
False

But:

>>> hash(float('nan')) == hash(float('nan'))
True

So you are guaranteed to collide every time, and you are seeing hash set behavior degrade to O(N), which is the worst-case behavior, not O(1). Fundamentally, you are not re-inserting the same float value.

Moreover, watch out for this behavior:

>>> nan = float('nan')
>>> myset = set()
>>> myset.add(nan)
>>> myset.add(nan)
>>> myset
{nan}

Despite:

>>> nan == nan
False

The above is due to an optimization, that for containers, Python actually checks identity first to avoid potentially costly __eq__ operations. Since I re-used the same object, now it is being considered "the same value".

user_50144550
Related