python - 为什么 `myfloat in myset` 变得 super 慢？

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

代码(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)

Answer 1

因为您使用的是 nan，它因违反关于 __hash__/__eq__ 契约(Contract)的天真期望而臭名昭著...即:

>>> 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__ 操作。由于我重复使用了同一个对象，现在它被认为是“相同的值”。