scala - 覆盖 `Comparison method violates its general contract` 异常

Question

我有一个像这样的比较器:

lazy val seq = mapping.toSeq.sortWith { case ((_, set1), (_, set2)) =>
  // Just propose all the most connected nodes first to the users
  // But also allow less connected nodes to pop out sometimes
  val popOutChance = random.nextDouble <= 0.1D && set2.size > 5
  if (popOutChance) set1.size < set2.size else set1.size > set2.size
}

我的目的是比较集合的大小，以便较小的集合在排序列表中可能以 10% 的机会出现在较高的位置。

但是编译器不允许我这样做，并抛出异常:java.lang.IllegalArgumentException:比较方法违反了其一般契约!一旦我尝试在运行时使用它。我怎样才能覆盖它？

Answer 1

我认为这里的问题是，每次比较两个元素时，结果都是随机的，从而违反了任何排序算法中比较器函数所需的传递属性。

例如，假设某个实例 a比较小于 b ，然后 b比较小于c 。这些结果应该意味着a比较小于c 。但是，由于您的比较是随机，因此您无法保证结果。事实上，你甚至不能保证 a将小于b下次比较它们时。

所以不要这样做。没有排序算法可以处理它。 (这种方法也违反了函数式编程的引用透明度原则，并且会让你的程序更难推理。)

相反，您需要做的是用随机分配的权重来装饰 map 的成员 - 在尝试对它们进行排序之前 - 以便它们可以一致地排序。但是，由于这种情况发生在排序操作开始时，因此每次排序的结果都会不同，我认为这就是您正在寻找的。

不清楚什么类型mapping在你的例子中有，但它看起来像: Map[Any, Set[_]] 。 (您可以根据需要替换类型 - 这对于这种方法来说并不重要。例如，假设 mapping 实际上具有类型 Map[String, Set[SomeClass]] ，那么您可以将下面对 Any 的引用替换为 String 和 Set[_]至Set[SomeClass]。)

首先，我们将创建一个 case class我们将用它来对 map 元素进行评分和比较。然后我们将映射 mapping 的内容到该案例类的元素序列。接下来，我们对这些元素进行排序。最后，我们从装饰类中提取元组。结果应该是这样的:

final case class Decorated(x: (Any, Set[_]), rand: Double = random.nextDouble)
extends Ordered[Decorated] {

  // Calculate a rank for this element. You'll need to change this to suit your precise
  // requirements. Here, if rand is less than 0.1 (a 10% chance), I'm adding 5 to the size;
  // otherwise, I'll report the actual size. This allows transitive comparisons, since
  // rand doesn't change once defined. Values are negated so bigger sets come to the fore
  // when sorted.
  private def rank: Int = {
    if(rand < 0.1) -(x._2.size + 5)
    else -x._2.size
  }

  // Compare this element with another, by their ranks.
  override def compare(that: Decorated): Int = rank.compare(that.rank)
}

// Now sort your mapping elements as follows and convert back to tuples.
lazy val seq = mapping.map(x => Decorated(x)).toSeq.sorted.map(_.x)

这应该将具有较大集合的元素放在前面，但集合有 10% 的机会显得大 5，因此会在列表中向上移动。每次重新执行最后一行时，结果都会不同，因为 map将为每个元素创建新的随机值。但排序时，排名是固定的，不会改变。

(请注意，我将排名设置为负值。 Ordered[T] 特征按升序对元素进行排序，因此 - 如果我们纯粹按集合大小排序 - 较小的集合将出现在较大的集合之前。排名值，排序会将较大的集合放在较小的集合之前。如果您不希望出现此行为，请删除否定。)