为什么`myfloat in myset` 变得超级慢？

Question

当我将相同的float值重新插入我的集合几次时，x in s应该花费恒定时间的检查变得非常缓慢。为什么？

计时输出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

代码（在线试用！）：

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)

Answer 1

因为您正在使用nan，这因打破对__hash__/__eq__合同的幼稚期望而臭名昭著......即：

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

发生这种情况是因为：

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

但：

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

所以你每次都会发生碰撞，你会看到散列集的行为降级为 O(N)，这是最坏的情况，而不是 O(1)。从根本上说，您不会重新插入相同的浮点值。

此外，请注意以下行为：

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

尽管：

>>> nan == nan
False

以上是由于优化，对于容器，Python 实际上首先检查身份以避免潜在的昂贵__eq__操作。由于我重新使用了相同的对象，现在它被认为是“相同的值”。