为什么 myset 中的 myfloat 变得超级慢？

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__ 合同的幼稚期望而臭名昭著...即：

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

为什么 myset 中的 myfloat 变得超级慢？

Why does `myfloat in myset` become super slow?

python

performance

set