Python中的sort函数在存在nan时会出现问题

52

sorted([2, float('nan'), 1]) 返回 [2, nan, 1]

(至少在Activestate Python 3.1实现中是这样。)

我知道nan是一个奇怪的对象,所以如果它出现在排序结果中的随机位置,我不会感到惊讶。但它也会破坏容器中非nan数字的排序,这真的是意料之外的。

我曾经提过一个相关问题关于max,基于那个问题,我理解为什么sort会这样处理。但这应该被视为一个错误吗?

文档只是说“返回一个新的排序列表[...]”,而没有指定任何详细信息。

编辑: 我现在同意这不违反IEEE标准。然而,从任何常识的角度来看,它都是一个错误,我认为。即使是微软,他们并不经常承认自己的错误,也已经把这个问题识别为一个错误,并在最新版本中修复了它:http://connect.microsoft.com/VisualStudio/feedback/details/363379/bug-in-list-double-sort-in-list-which-contains-double-nan

不管怎样,最终我采用了@khachik的答案:

sorted(list_, key = lambda x : float('-inf') if math.isnan(x) else x)

我怀疑与语言默认方式相比这会导致性能下降,但至少它可以工作(除非我引入了任何错误)。


不是数字(NAN)是数值排序或任何期望数字的输入无效;因此,我不认为这是一个错误。 - frayser
1
@Frayser:那不完全正确。在Python中无效吗?不是因为Python不会引发异常。在IEEE754中无效吗?不是因为它提供了非常特定的行为(至少对于安静的nan)。在其他标准中无效吗? - max
3
“nan”在结果列表中随机出现是可以理解的,但更难理解的是,在最后一个数字值中似乎有意将其错误排序,这被认为是正确的行为:sorted([1.0, 2.0, 3.0, float('nan'), 4.0, 3.0, 2.0, 1.0]) => [1.0, 2.0, 3.0, nan, 1.0, 2.0, 3.0, 4.0]。参见http://bugs.python.org/issue12286。 - Noah
但是它也会破坏容器中非NaN数字的排序,这真的很出乎意料。确切地说,我认为问题出在.sort()上,直到我已经解决了问题才来到这个问答页面:\感谢您记录下来! - jtlz2
1
@Noah,截至2019年,该问题线程已关闭 :( - jtlz2
8个回答

18
之前的答案很有用,但可能不清楚问题的根源。
在任何语言中,排序都会应用给定的顺序,由比较函数或其他方式定义输入值域。例如,小于,也就是operator <,只有当小于定义了适合输入值的排序时才能被使用。
但这对于浮点数和小于运算符特别不适用: “NaN是无序的:它不等于、大于或小于任何东西,包括它本身。”(来自GNU C手册的明确描述,但适用于所有现代基于IEEE754浮点数
因此,可能的解决方案为:
  1. 首先移除NaN,通过<(或其他排序函数)使输入域定义良好
  2. 定义一个自定义的比较函数(又称谓词),该函数定义NaN的排序方式,如小于任何数字或大于任何数字。
以上两种方法可以在任何语言中使用。
实际上,在考虑Python时,如果要么不太关心最快速度,要么在上下文中希望去除NaN,我更倾向于先移除NaN。
否则,您可以通过“cmp”在旧版本的Python或通过这个和functools.cmp_to_key()使用适当的谓词函数。后者比先移除NaN会更加笨拙,而在定义这个谓词函数时需要小心避免性能变差。

2
IEEE 754 要求 max(NaN, 1) 返回 1。如果 Python 遵循这个标准就好了,但它没有。如果它遵循自己的规则,至少应该有一些合理的规则,而不是随机不稳定的行为。 - max
澄清一下,我同意您的观点,即float('nan')<1或float('nan')> = 1应该返回False。最新的IEEE标准(IEEE 754 = IEEE 754-2008)似乎为函数“最小值”和“最大值”(必须返回数字)做了一个例外,但对于“排序”或常规比较则没有。 - max
cmp_to_key是一个相当迂回的解决方案。你真正需要的只是一个键函数,它将NaN替换为其他东西(例如无穷大或自定义对象,比任何东西都小)。 - plugwash
“定义一个自定义比较函数(也称为谓词),该函数确实为NaN定义了一种排序方式,例如小于任何数字或大于任何数字。"是不够的,因为它没有定义比较两个NaN的情况。由于NaN有多个编码,因此需要对两个NaN进行一致的<、==、>比较。也许在这种子情况下需要进行内存位比较。” - chux - Reinstate Monica
据我所知,这个回答没有解释为什么非 NaN 数字会随机放置在应该排序的列表中。我理解 NaN 的问题,并且我不介意它们落在哪里。然而,我确实关心“已排序”列表中数字 1 和 2 的相对位置。 - Eric Duminil

10

我不确定这个bug,但解决方法可能如下:

sorted(
    (2, 1, float('nan')),
    lambda x,y: x is float('nan') and -1 
                or (y is float('nan') and 1
                or cmp(x,y)))

结果为:

('nan', 1, 2)

在排序或其他操作之前,可以先移除 nan 值。


1
我将为Python 3重写此代码,并处理nannumpy.nan的情况。 - max
1
我怀疑当列表中有两个NAN时会失败。许多排序例程在cmp(n1,n2)为-1且cmp(n2,n1)也为-1时会失败。 - chux - Reinstate Monica

8
问题在于,如果list中包含一个NAN,则不存在正确的排序顺序,因为序列a1,a2,a3,...,an的排序方式是a1 <= a2 <= a3 <= ... <= an。 如果其中任何一个a值是NAN,则排序属性将被破坏,因为对于所有的a,a <= NAN和NAN <= a都是false

IEEE定义了两种不同的排序方式:部分排序,其中NaN是不可比较的,正零和负零相等;以及允许比较任何两个浮点数值的总线性顺序,包括具有不同有效载荷的NaN。如果Python使用后者的顺序对浮点数值进行排序,那将更为实用。 - Yakov Galka

8

假设您想保留NaN并将其排序为最低的“值”,这里有一个解决方法,适用于非唯一NaN、唯一的numpy NaN、数值和非数值对象:

def is_nan(x):
    return (x is np.nan or x != x)

list_ = [2, float('nan'), 'z', 1, 'a', np.nan, 4, float('nan')]
sorted(list_, key = lambda x : float('-inf') if is_nan(x) else x)
# [nan, nan, nan, 1, 2, 4, 'a', 'z']

2
我喜欢这个答案。我不明白为什么nan不能被定义为-inf或inf。我理解在数学上如何无法比较0和1/0,但这不应该妨碍一个合理的语言结构来处理这个问题。 - demongolem
1
如果nan就像-inf一样,那么一个列表[nan,-inf,nan,-inf]将被认为是已排序的。 - chux - Reinstate Monica

4

IEEE754是定义浮点运算的标准。该标准规定,当至少有一个操作数为NaN时,比较操作将被视为错误。因此,这不是一个错误。在对数组进行操作之前,您需要处理NaN。


6
Python不遵循IEEE754标准,该标准要求存在两个NaN:信号和非信号,以及两个比较运算符:信号和非信号。此外,IEEE754-2008明确要求在与nan进行比较时,max函数应返回该数字本身。 - max
如果您在基于IEEE754的FP硬件上运行CPython,则会得到这个结果。此外,IEEE754如何定义最大值? - David Heffernan
1
Python文档对IEEE754有如下描述:“几乎所有的机器(截至2010年7月)都使用IEEE-754浮点运算,几乎所有平台都将Python浮点数映射到IEEE-754“双精度”。” 此外,非常感谢您的投票。仅仅因为您不喜欢答案并不意味着您应该攻击传递信息的人!!;-) - David Heffernan
@David Heffernan:我找不到参考资料,但在阅读相关内容时,似乎它只是说明了max应该如何处理quiet NaNs。 - max
4
@max,我们可以争论不休,但事实就是事实,你只能预处理数组并检查NaN-如果你不喜欢这种方法,那么你必须向Guido提出异议! - David Heffernan
显示剩余8条评论

2

回顾以下问题:

NaN

在任何比较中,NaN 总是返回 False,因此它将保留在列表中的原位置。

>>> sorted([float('nan'), 0])
[nan, 0]
>>> sorted([0, float('nan')])
[0, nan]

-0.0

这与0.0相等,但具有不同的表示形式、不同的json表示和略微不同的数值属性。它与正零和负零一样存在问题,即正零和负零将保持在原始列表中的相对顺序不变:

>>> sorted([0.0, -0.0])
[0.0, -0.0]
>>> sorted([-0.0, 0.0])
[-0.0, 0.0]

其他解决方案?

@khachik的解决方案在NaN-inf的排序行为上不一致。

>>> key=lambda x: float('-inf') if math.isnan(x) else x
>>> sorted([float('nan'), float('-inf')], key=key)
[nan, -inf]
>>> sorted([float('-inf'), float('nan')], key=key)
[-inf, nan]

解决方案:更复杂的键函数。

因此,存在符号和NaN的问题。我们可以将它们包含在键函数中:

def stable_float_sort_key(x: float):
    return math.copysign(1, x), math.isnan(x), x

这适用于上述所有示例:

>>> sorted([float('nan'), 0.0], key=stable_float_sort_key)
[0.0, nan]
>>> sorted([0.0, float('nan')], key=stable_float_sort_key)
[0.0, nan]
>>> sorted([float('nan'), float('-inf')], key=stable_float_sort_key)
[-inf, nan]
>>> sorted([float('-inf'), float('nan')], key=stable_float_sort_key)
[-inf, nan]
>>> sorted([0.0, -0.0], key=stable_float_sort_key)
[-0.0, 0.0]
>>> sorted([-0.0, 0.0], key=stable_float_sort_key)
[-0.0, 0.0]

实际上,您可以编写一个假设检验,以显示它在所有浮点数上都是一致的:

import json
from hypothesis import given, settings
from hypothesis import strategies as st

@given(nums=st.lists(st.floats()), random=st.randoms())
@settings(max_examples=10000)
def test_stable_json_sorting(nums, random):
    shuffled = list(nums)
    random.shuffle(shuffled)
    l1 = sorted(nums, key=stable_float_sort_key)
    l2 = sorted(shuffled, key=stable_float_sort_key)
    assert json.dumps(l1) == json.dumps(l2)

然而,它确实有一些奇怪之处,因为一些NaN是负数!例如:

>>> sorted([float('nan'), -0.0, 0.0, float('-nan')], key=stable_float_sort_key)
[-0.0, nan, 0.0, nan]

如果这让你感到困扰,你可以通过更改顺序来解决问题:
def stable_float_sort_key(x: float):
    return math.isnan(x), math.copysign(1, x), x

这将首先对负数进行排序,然后是正数,最后是NaN。

这些内容有意义吗?

当然,其他回答者正确地指出,在某种意义上,这些都没有意义。比较NaN是某种概念错误。但是,即使在问题“没有意义”的情况下,您可能希望具有不变量,例如将由相同代码生成的浮点数集合序列化为完全相同的JSON表示形式,尽管哈希随机化(我的用例)。那更多是Python代码的形式属性,而不是IEEE标准的“正确答案”。


0

一个弹性排序涉及到比较两个项目并返回:小于、等于、大于。

如果 cmp(a,b) 是 "大于",那么 cmp(b,a) 必须是 "小于"。

如果 cmp(a,b) 是 "零",那么 cmp(b,a) 必须是 "零"。

迄今为止答案中缺少的是比较两个都是 NANfloat 的情况,并保留上述属性。2个 NAN 应该被视为相等或者基于它们有效负载的一些一致解释。

备用比较 算法 将所有 NAN > +inf

if isnan(a)
  if isnan(b)
    return 0 (or maybe compare payloads/bit patterns)
  return 1
if isnan(b) return 1
if a > b return 1
if a < b return -1
return 0

0

无论标准如何,有许多情况下用户定义的浮点数和NA值的排序是有用的。例如,我正在对股票回报进行排序,并希望最高到最低,NA值排在最后(因为它们是不相关的)。有4种可能的组合:

  1. 升序浮点数,NA值最后
  2. 升序浮点数,NA值最先
  3. 降序浮点数,NA值最后
  4. 降序浮点数,NA值最先

这里有一个函数,通过有条件地将NA值替换为+/- inf来覆盖所有情况。

import math 

def sort_with_na(x, reverse=False, na_last=True):
    """Intelligently sort iterable with NA values

    For reliable behavior with NA values, we should change the NAs to +/- inf
    to guarantee their order rather than relying on the built-in
    ``sorted(reverse=True)`` which will have no effect. To use the ``reverse``
    parameter or other kwargs, use functools.partial in your lambda i.e.

        sorted(iterable, key=partial(sort_with_na, reverse=True, na_last=False))

    :param x: Element to be sorted
    :param bool na_last: Whether NA values should come last or first
    :param bool reverse: Return ascending if ``False`` else descending
    :return bool:
    """
    if not math.isnan(x):
        return -x if reverse else x
    else:
        return float('inf') if na_last else float('-inf')

测试每个4种组合

from functools import partial

a = [2, float('nan'), 1]
sorted(a, key=sort_with_na)                                         # Default
sorted(a, key=partial(sort_with_na, reverse=False, na_last=True))   # Ascend, NA last
sorted(a, key=partial(sort_with_na, reverse=False, na_last=False))  # Ascend, NA first
sorted(a, key=partial(sort_with_na, reverse=True, na_last=True))    # Descend, NA last
sorted(a, key=partial(sort_with_na, reverse=True, na_last=False))   # Descend, NA first

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接