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

当我重新插入相同的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

Code (在线尝试一下！ https://tio.run/##TY3bCsIwEETf8xX7UpJIKa1FFKFfIiJpm9RAcyGJUBG/PaYXivOy7MzuGfsOT6Pri3UxCmcUBKm4DCCVNS5sG0IeGviI0bBAsGYa0y8SxsEDpAbH9MBJdaJXBEm7fzv4@2rNmhLhH7AHvmB9T6bVmPvS4VpL8DRzPM5Bv1TLXVOVZZnDMJqWjb7ZJqEUDlDxeiFYJ3X6zM7FUYCSnTOed0b3HkO2cGmMPw):

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)

因为你正在使用nan，这因打破天真的期望而臭名昭著__hash__/__eq__合同...即：

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

发生这种情况是因为：

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

But:

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

因此，每次都会发生冲突，并且您会看到哈希集行为退化为 O(N)，这是最坏情况的行为，而不是 O(1)。从根本上来说，你不重新插入相同的浮点值.

此外，请注意以下行为：

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

Despite:

>>> nan == nan
False

以上是由于一项优化，对于容器来说，Python 实际上首先检查身份以避免潜在的代价__eq__运营。由于我重复使用了同一个对象，现在它被认为是“相同的值”。