问题 包含NaN的集合的最小值/最大值（处理订单中的不可比性）


由于以下行为，我刚遇到一个令人讨厌的错误：

scala> List(1.0, 2.0, 3.0, Double.NaN).min
res1: Double = NaN

scala> List(1.0, 2.0, 3.0, Double.NaN).max
res2: Double = NaN

我理解，对于成对比较，有时可能更好 max(NaN, 0) = NaN 这可能是原因所在 java.lang.Double.compare 遵循这个惯例（似乎有一个 IEEE标准 为了那个原因）。然而，对于一个集合，我真的认为这是一个奇怪的约定。以上所有上述集合确实包含有效数字;这些数字有明确的最大值和最小值。在我看来，这个概念就是 最大数量 该系列是 不是数字 是一个矛盾，因为，NaN不是一个数字，所以它不能是一个集合的最大或最小“数字” - 除非根本没有有效数字;在这种情况下，最大的“不是数字”是完全合理的。语义上的 min 和 max 函数退化以检查集合是否包含NaN。由于有更合适的方法来检查NaN的存在（例如 collection.find(_.isNaN)）在集合上保持语义上有意义的最小/最大值会很棒。

所以我的问题是：获得忽略NaN存在的行为的最佳方法是什么？我看到两种可能性：

  1. 在调用min / max之前过滤NaN。由于这需要在所有地方明确处理问题，并可能导致性能损失，我宁愿更容易。

  2. 有一种NaN忽略排序会很好，可以在必要时用作隐式排序。我尝试了以下方法： 

      object NanAwareOrdering extends Ordering[Double] {
    def compare(x: Double, y: Double) = {
      if (x.isNaN()) {
        +1 // without checking x, return y < x
      } else if (y.isNaN()) {
        -1 // without checking y, return x < y
      } else {
        java.lang.Double.compare(x, y)
      }
    }
  }

    然而，这种方法似乎取决于我是否有兴趣找到最小值或最大值，即：

     scala> List(1.0, 2.0, 3.0, Double.NaN).min(NanAwareOrdering)
 res7: Double = 1.0

 scala> List(1.0, 2.0, 3.0, Double.NaN).max(NanAwareOrdering)
 res8: Double = NaN

    这意味着我必须有两个NanAwareOrdering，具体取决于我是否需要最小值或最大值，这将禁止具有 implicit val。因此，我的问题是：如何定义一个排序，以便同时处理两个案例？

更新：

为了完整起见：在分析问题的过程中，我意识到前提“退化为检查NaN”实际上是错误的。事实上，我认为它更难看：

scala> List(1.0, Double.NaN).min
res1: Double = NaN

scala> List(Double.NaN, 1.0).min
res2: Double = 1.0

6688
2018-05-09 12:00


起源
“收集的最大数量不是一个数字是一个矛盾，因为，好吧，NaN不是一个数字，所以它不能是一个集合的最大或最小”数“”该方法被称为 max不是 maxNumber，并且在其他情况下也不返回数字：例如当集合不是数字而是某些其他有序类型时，或者当它包含无穷大时，或者它是空的时。如果只是，这将是奇怪的 NaN 在标准库中是特殊的。 - Alexey Romanov
我真的没有看到你的观点。的名字 max 函数显然不应该依赖于底层类型。如果您的收藏包含 Customer比 max 让你成为“最大客户”。当集合包含“数字”时，你应该得到“最大数量”，对吗？在这个类比中，也存在一个不可比元素的概念：你也不想获得一个 UncomparableCustomer 最大或最小。 - bluenote10
你是否同意你的论证的这个变体：如果集合包含数字，那么 collection.head 必须是一个数字，等等 List(Double.NaN, 1).head 应该 1？如果没有，那么它们之间的相关区别是什么 head 和 max？ - Alexey Romanov
正如你所见，你不能有一个对待的订单 NaN你想要的方式。同样，你不能写一个泛型 max[T] 不包括在内 NaN秒。 - Alexey Romanov
两者之间存在巨大的语义差异 head 和 max：第一个是纯粹的位置，后者本质上取决于一个排序（这也反映在这个事实上 head 不需要任何隐含参数）。既然Scala提供了隐含地传递这种顺序的可能性，那么通过排序是不是一种自然的愿望，它可以根据我们的要求处理“无法比较”？ - bluenote10

答案:

免责声明：我会在问题中添加我自己的答案，以防万一其他人仍然对此事的更多细节感兴趣。

一些理论......

我觉得这个问题比我想象的要复杂得多。正如阿列克谢·罗曼诺夫已经指出的那样，无法比较的概念要求最大/最小功能采取部分顺序。不幸的是，Alexey也是正确的，基于部分顺序的一般最大/最小函数没有意义：想想部分排序仅定义某些组内的关系的情况，但这些组本身完全独立于彼此（例如，元素{a，b，c，d}只有两个关系a <b和c <d;我们将有两个max / min）。在这方面，人们甚至可能认为正式的最大/最小应该 总是 返回两个值，NaN 和 相应的有效最小值/最大值，因为NaN本身也是其自身关系组中的极值。

因此，由于部分订单过于笼统/复杂，最小/最大功能需要一个 Ordering。不幸的是，总订单不允许无法比较的概念。回顾总订单的三个定义属性，很明显“忽略NaN”在形式上是不可能的：

  1. 如果a≤b且b≤a则a = b（反对称）
  2. 如果a≤b且b≤c则a≤c（传递性）
  3. a≤b或b≤a（总数）

......并且练习......

所以当试图想出一个实现 Ordering 为了实现我们理想的最小/最大行为，很明显我们必须违反某些事情（并承担后果）。实施 min/max/minBy/maxBy 在 TraversableOnce 遵循模式（for min）：

reduceLeft((x, y) => if (cmp.lteq(x, y)) x else y)

和 gteq 为了 max 变种。这给了我“左偏”这个比较的想法，即：

x   <comparison_operator> NaN    is always true to keep x in the reduction
NaN <comparison_operator> x      is always false to inject x into the reduction

由此产生的“左偏”排序实现如下：

object BiasedOrdering extends Ordering[Double] {
  def compare(x: Double, y: Double) = java.lang.Double.compare(x, y) // this is inconsistent, but the same goes for Double.Ordering

  override def lteq(x: Double, y: Double): Boolean  = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) true  else compare(x, y) <= 0
  override def gteq(x: Double, y: Double): Boolean  = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) true  else compare(x, y) >= 0
  override def lt(x: Double, y: Double): Boolean    = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) false else compare(x, y) < 0
  override def gt(x: Double, y: Double): Boolean    = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) false else compare(x, y) > 0
  override def equiv(x: Double, y: Double): Boolean = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) true  else compare(x, y) == 0

}

......分析：

目前我正试图找出：

  • 此订单与默认订单的比较方式，
  • 我们在哪里违反总订单属性，
  • 什么是潜在的问题。

我将此与Scala的默认顺序进行比较 Ordering.Double 和以下直接派生的排序 java.lang.Double.compare：

object OrderingDerivedFromCompare extends Ordering[Double] {
  def compare(x: Double, y: Double) = {
    java.lang.Double.compare(x, y)
  }
}

Scala默认订单的一个有趣属性 Ordering.Double 是它通过语言的本机数值比较运算符覆盖所有比较成员函数（<， <=， ==， >=， >所以比较结果是相同的，就像我们将直接与这些运算符进行比较一样。以下显示了NaN与三个排序的有效数字之间的所有可能关系：

Ordering.Double             0.0 >  NaN = false
Ordering.Double             0.0 >= NaN = false
Ordering.Double             0.0 == NaN = false
Ordering.Double             0.0 <= NaN = false
Ordering.Double             0.0 <  NaN = false
OrderingDerivedFromCompare  0.0 >  NaN = false
OrderingDerivedFromCompare  0.0 >= NaN = false
OrderingDerivedFromCompare  0.0 == NaN = false
OrderingDerivedFromCompare  0.0 <= NaN = true
OrderingDerivedFromCompare  0.0 <  NaN = true
BiasedOrdering              0.0 >  NaN = true
BiasedOrdering              0.0 >= NaN = true
BiasedOrdering              0.0 == NaN = true
BiasedOrdering              0.0 <= NaN = true
BiasedOrdering              0.0 <  NaN = true

Ordering.Double             NaN >  0.0 = false
Ordering.Double             NaN >= 0.0 = false
Ordering.Double             NaN == 0.0 = false
Ordering.Double             NaN <= 0.0 = false
Ordering.Double             NaN <  0.0 = false
OrderingDerivedFromCompare  NaN >  0.0 = true
OrderingDerivedFromCompare  NaN >= 0.0 = true
OrderingDerivedFromCompare  NaN == 0.0 = false
OrderingDerivedFromCompare  NaN <= 0.0 = false
OrderingDerivedFromCompare  NaN <  0.0 = false
BiasedOrdering              NaN >  0.0 = false
BiasedOrdering              NaN >= 0.0 = false
BiasedOrdering              NaN == 0.0 = false
BiasedOrdering              NaN <= 0.0 = false
BiasedOrdering              NaN <  0.0 = false

Ordering.Double             NaN >  NaN = false
Ordering.Double             NaN >= NaN = false
Ordering.Double             NaN == NaN = false
Ordering.Double             NaN <= NaN = false
Ordering.Double             NaN <  NaN = false
OrderingDerivedFromCompare  NaN >  NaN = false
OrderingDerivedFromCompare  NaN >= NaN = true
OrderingDerivedFromCompare  NaN == NaN = true
OrderingDerivedFromCompare  NaN <= NaN = true
OrderingDerivedFromCompare  NaN <  NaN = false
BiasedOrdering              NaN >  NaN = false
BiasedOrdering              NaN >= NaN = true
BiasedOrdering              NaN == NaN = true
BiasedOrdering              NaN <= NaN = true
BiasedOrdering              NaN <  NaN = false

我们可以看到：

  • 只要 OrderingDerivedFromCompare 履行总订单属性。基于这个结果 背后的推理 java.lang.Double.compare 变得更加清晰：将NaN置于总顺序的上端简单地避免了任何矛盾！
  • Scala的默认顺序和偏差顺序违反了许多总体条件。 Scala的默认订单始终返回 false，而对于有偏见的顺序，它取决于位置。由于两者都导致矛盾，因此很难看出哪些可能导致更严重的问题。

现在我们手头的实际问题，最小/最大功能。对于 OrderingDerivedFromCompare 现在很清楚我们必须得到什么 - NaN只是最大的值，因此无论列表中的元素是如何排列的，都可以将其作为最大值获得：

OrderingDerivedFromCompare  List(1.0, 2.0, 3.0, Double.NaN).min = 1.0
OrderingDerivedFromCompare  List(Double.NaN, 1.0, 2.0, 3.0).min = 1.0
OrderingDerivedFromCompare  List(1.0, 2.0, 3.0, Double.NaN).max = NaN
OrderingDerivedFromCompare  List(Double.NaN, 1.0, 2.0, 3.0).max = NaN

现在来看Scala的默认排序。看到这种情况实际上比我的问题中提到的更复杂，我深感震惊：

Ordering.Double             List(1.0, 2.0, 3.0, Double.NaN).min = NaN
Ordering.Double             List(Double.NaN, 1.0, 2.0, 3.0).min = 1.0
Ordering.Double             List(1.0, 2.0, 3.0, Double.NaN).max = NaN
Ordering.Double             List(Double.NaN, 1.0, 2.0, 3.0).max = 3.0

事实上，元素的顺序变得相关（作为返回的结果 false 对于每一次比较 reduceLeft）。 “左偏”显然解决了这个问题，导致了一致的结果：

BiasedOrdering              List(1.0, 2.0, 3.0, Double.NaN).min = 1.0
BiasedOrdering              List(Double.NaN, 1.0, 2.0, 3.0).min = 1.0
BiasedOrdering              List(1.0, 2.0, 3.0, Double.NaN).max = 3.0
BiasedOrdering              List(Double.NaN, 1.0, 2.0, 3.0).max = 3.0

不幸的是，我仍然无法完全回答所有问题。剩下的一些要点是：

  • 为什么Scala的默认排序按照它的方式定义？目前处理NaNs似乎存在很大缺陷。一个非常危险的细节 Ordering.Double 是那个 compare 函数实际上委托给 java.lang.Double.compare，而比较成员是基于语言的本机比较实现的。这显然会导致不一致的结果，例如：

    Ordering.Double.compare(0.0, Double.NaN) == -1     // indicating 0.0 < NaN
Ordering.Double.lt     (0.0, Double.NaN) == false  // contradiction

  • 有什么潜在的缺点 BiasedOrdering，除了直接评估任何矛盾的比较？快速检查 sorted 给出了以下结果，但没有发现任何问题：

    Ordering.Double             List(1.0, 2.0, 3.0, Double.NaN).sorted = List(1.0, 2.0, 3.0, NaN)
OrderingDerivedFromCompare  List(1.0, 2.0, 3.0, Double.NaN).sorted = List(1.0, 2.0, 3.0, NaN)
BiasedOrdering              List(1.0, 2.0, 3.0, Double.NaN).sorted = List(1.0, 2.0, 3.0, NaN)

Ordering.Double             List(Double.NaN, 1.0, 2.0, 3.0).sorted = List(1.0, 2.0, 3.0, NaN)
OrderingDerivedFromCompare  List(Double.NaN, 1.0, 2.0, 3.0).sorted = List(1.0, 2.0, 3.0, NaN)
BiasedOrdering              List(Double.NaN, 1.0, 2.0, 3.0).sorted = List(1.0, 2.0, 3.0, NaN)

暂时我会选择这种左偏序。但由于问题的性质不允许完美的通用解决方案：小心使用！

更新

在基于monkjack建议的隐式类的解决方案方面，我非常喜欢以下内容（因为它根本没有混淆（有缺陷的？）总订单，但内部转换为一个干净的完全有序的域）：

implicit class MinMaxNanAware(t: TraversableOnce[Double]) {
  def nanAwareMin = t.minBy(x => if (x.isNaN) Double.PositiveInfinity else x)
  def nanAwareMax = t.maxBy(x => if (x.isNaN) Double.NegativeInfinity else x)
}

// and now we can simply use
val goodMin = list.nanAwareMin

5
2018-05-10 21:01



如何将隐式带入允许您在列表中使用新的最小/最大方法的范围。

就像是：

object NanAwareMinOrdering extends Ordering[Double] {
    def compare(x: Double, y: Double) = {
      if (x.isNaN()) {
        +1 // without checking x, return y < x
      } else if (y.isNaN()) {
        -1 // without checking y, return x < y
      } else {
        java.lang.Double.compare(x, y)
      }
    }
  }

object NanAwareMaxOrdering extends Ordering[Double] {
  ....
}

implicit class MinMaxList(list:List[Double]) {
  def min2 = list.min(NanAwareMinOrdering)
  def max2 = list.max(NanAwareMaxOrdering)
}

List(1.0, 2.0, 3.0, Double.NaN).min2


2
2018-05-09 12:10


您可以定义隐式接受Seq或其他常见的超类型的集合类。并且min2 / max2方法不一定必须使用过滤器（这只是为了回答速度），您可以使用您建议的自定义顺序调用原始文件的最小/最大值，或者确实做其他事情。 - monkjack
是的，为它定义它可能是有意义的 TraversableOnce，它还提供最小/最大。我们还需要 maxBy/minBy 实现。 - bluenote10
是的，所以只需使min2 / max2使用排序而不是过滤和最小/最大。 - monkjack
更新的答案显示我的意思。 - monkjack
您可以添加一个隐式排序，在调用时抛出异常。因此list.max / list.min将使用隐式，而min2 / max2将使用其他排序并工作。有点hacky也许会工作。 - monkjack

对于

val a = List(1.0, 2.0, 3.0, Double.NaN)

把它分类，

a.sortWith {_ >_ }
res: List[Double] = List(3.0, 2.0, 1.0, NaN)

所以 NaN 价值降级，因此最大，

a.sortWith {_ >_ }.head
res: Double = 3.0

同样

a.sortWith {_ < _ }
res: List[Double] = List(1.0, 2.0, 3.0, NaN)

所以对于min，

a.sortWith {_ < _ }.head
res: Double = 1.0

1
2018-05-09 12:28


鉴于我庞大的收藏规模，从O（N）变为O（N log N）可能会造成一些麻烦...... - bluenote10
@ bluenote10也许是对可变变量中max或min值的收集和更新进行非惯用迭代。初始化第一个最小值或最大值时，从集合中首次出现非NaN。 - elm
其实我喜欢方便 min/max/minBy/maxBy 很多。在完全忽略这些功能之前，我仍然希望明确地传递一个 NanIgnoringMaxOrdering 和 NanIgnoringMinOrdering 取决于我是采取最小还是最大。 - bluenote10

这个答案仅仅是为了解释这个问题，@ monkjack的答案可能提供了最好的实用解决方案。

既然Scala提供了隐含地传递这种顺序的可能性，那么通过排序是不是一种自然的愿望，它可以根据我们的要求处理“无法比较”

Ordering 在Scala中仅代表 总 排序，即所有元素都具有可比性的排序。有一个 PartialOrdering[T]： http://www.scala-lang.org/api/2.10.3/index.html#scala.math.PartialOrdering，但有几个问题：

  1. 它实际上并未在标准库中的任何位置使用。

  2. 如果你试图实施 max/maxBy/等等。哪个 PartialOrdering，你很快就会发现它通常不可能 除 在像这样的情况下 Float/Double 你有一些与任何东西都不具有可比性的元素 是 相互比较（你可以决定忽略无比的元素）。


1
2018-05-10 11:11


非常好的结论 - 我只是发表了一些研究的结果。 - bluenote10

热门问题

不使用eval / new函数的JavaScript模板库 当涉及内部类时，Java继承如何工作 .NET Windows服务的奇怪问题 在.ipa或.app下查找App ID 快速入门XSLT参考[关闭] 如何找出Android应用程序中未使用的资源 Ruby中并发的同步方法[重复] 将std :: chrono :: system_clock :: time_point转换为struct timeval并返回 Google Drive API V3（javascript）更新文件内容 Bootstrap 3.0 - 将元素推到底部 受密码保护的.NET ClickOnce部署？ 如何用postgresql安装wordpress coq Set或Type如何成为命题 硒滚动元素进入（中心）视图 在Spring Transaction JUnit测试中自动装配Hibernate会话的正确方法 Git的Dockerfile策略 如何在FOS_PICKFOLDER中使用IFileDialog，同时仍在对话框中显示文件名 在Firefox扩展中复制Google Chrome浏览器操作弹出效果 CakePHP找到MAX 芹菜 - 完成任务的召唤功能 从使用fmemopen创建的流中读取宽字符 .NET是否为每个程序集创建一个字符串实习池？ DefaultModelBinder不绑定嵌套模型 Navigator.MediaDevices.getUserMedia（）使用了哪些相机通信标准？ 选择命名空间名称时应该知道什么？ cout Swagger Codegen CLI Java客户端 - 如何正确使用它 一个很好的哈希函数用于采访整数，字符串？ Maven 3 ciManagement配置的目的是什么？ 如何通过语言文化获取代码页？
licensed under cc by-sa 3.0 with attribution.
隐私政策 往来