scala Seq sortWith 或 sortBy 与 NaN

Question

我在 scala(2.11.8 和 2.12.1)中遇到 Seq[(Long, Double)]< 的一些非常奇怪的排序行为。我可能误解了一些基本的东西。

给定一个没有 Double.NaN 值的序列，一切都按预期工作

Seq[(Long, Double)]((1L, 2.5D), (2L, 0D), (11L, 11D), (2L, 10D)).sortWith(_._2 > _._2)
output >>> Seq[(Long, Double)] = List((11,11.0), (2,10.0), (1,2.5), (2,0.0))

如果我在排序列中添加一个带有 NaN 的元组，就会发生奇怪的事情

Seq[(Long, Double)]((1L, 2.5D), (2L, 0D), (3L, Double.NaN), (11L, 11D), (2L, 10D)).sortWith(_._2 > _._2)
output >>> Seq[(Long, Double)] = List((1,2.5), (2,0.0), (5,NaN), (11,11.0), (2,10.0))

所以看起来什么也没做

如果我交换前两个元素

Seq[(Long, Double)]((2L, 0D), (1L, 2.5D), (5L, Double.NaN), (11L, 11D), (2L, 10D)).sortWith(_._2 > _._2)
output >>> Seq[(Long, Double)] = List((11,11.0), (2,10.0), (1,2.5), (2,0.0), (5,NaN))

排序再次有效？

仅使用 Seq[Double] 即可观察到同样的情况

Seq[Double](2.5, 0, Double.NaN, 11, 10).sortWith(_ > _)
output >>> Seq[Double] = List(2.5, 0.0, NaN, 11.0, 10.0)

Seq[Double](0, 2.5, Double.NaN, 11, 10).sortWith(_ > _)
output >>> Seq[Double] = List(11.0, 10.0, 2.5, 0.0, NaN)

.sortBy(_._2) 似乎在所有情况下都有效。这是 scala 中的错误，还是我大脑中的错误？我在 Ubuntu 16.04 和 Java HotSpot(TM) 64 位服务器虚拟机上使用 scala 2.11.8 和 2.12.1 ，Java 1.8.0_91。

更新

事实证明，如果我颠倒排序顺序，那么会发生更可预测的事情

Seq[(Long, Double)]((1L, 2.5D), (2L, 0D), (3L, Double.NaN), (11L, 11D)).sortWith(_._2 < _._2)
output >>> Seq[(Long, Double)] = List((2,0.0), (1,2.5), (3,NaN), (11,11.0))

但再次在两者之间添加 NaN 会破坏排序

Seq[(Long, Double)] = List((2,0.0), (3,NaN), (1,2.5), (11,11.0))
output >>> Seq[(Long, Double)] = List((1,2.5), (3,NaN), (2,0.0), (11,11.0))

那么，Seq.sortWith 或 .sortBy 在看到 NaN 时就决定放弃？

<小时/>

在一个稍微不相关的注释中，当我尝试对上述类型的元组序列进行排序时，我遇到了这个问题，因为 spark 抛出了一个错误(如下)。上面的结果只是来自 scala REPL，其中没有涉及 Spark。

java.lang.IllegalArgumentException: Comparison method violates its general contract!

<小时/>

还有一个关于 .max 和 .min 的相关问题，其中 NaN s min/max of collections containing NaN (handling incomparability in ordering)

Answer 1

Spark 异常实际上很好地提示了这里发生的情况:Spark 假设比较方法定义了 Total Order 在输入集上，这意味着，除其他外，对于集合中的每两个元素:

A > B OR B > A

现在，函数_ > _ 是 double 的全序，但它对于所有 double 和 NaN 的集合不是全序>。使用这些简单的测试可以看出这一点:

scala> Double.NaN > 1.0
res19: Boolean = false

scala> Double.NaN < 1.0
res20: Boolean = false

因此，NaN 既不大于也不小于 1.0。

回到 sortWith 的实现 - 我没有检查，但我假设它做出了相同的假设，但当情况并非如此时，它不会抛出错误，而是简单地得出结果当整体性被打破时，不可预测(依赖于顺序)。

编辑:

So Seq.sortWith or .sortBy just decides to give up when it sees a NaN?

不，它只是返回“错误”的结果，因为它由于不支持假设而做出了错误的决定。没有测试寻找NaN并放弃(正如@TheArchetypalPaul评论的那样:“进行排序处理需要它在比较之前检查每个值不是NaN 。 不值得”)。