java - 比较方法在排序时违反了其一般契约

Question

是的，我知道有很多人有同样的问题，但我真的找不到我的比较器出了什么问题。

所以，这里是:

evaluateComparator = (m1, m2) -> {
    Color color = m1.getColor(); // m1 and m2 will have the same one
    double m1Value, m2Value;
    if (sortingCache.containsKey(m1)) {
        m1Value = sortingCache.get(m1);
    } else {
        // The value has not been computed before so it's not in the cache and I need to compute it now     
        someClass.doSomething(m1);
        m1Value = someClass.getValue();
        someClass.undoSomething(m1);
        sortingCache.put(m1, m1Value);
    }
    if (sortingCache.containsKey(m2)) {
        m2Value = sortingCache.get(m2);
    } else {
        // The value has not been computed before so it's not in the cache and I need to compute it now     
        someClass.doSomething(m2);
        m2Value = someClass.getValue();
        someClass.undoSomething(m2);
        sortingCache.put(m2, m2Value);
    }
    // Since I'm comparing two doubles I can use the Double's comparator
    return Double.compare(m1Value, m2Value);
};

代码非常简单:我需要根据一些对象如何改变我的主要结构对它们进行排序，并且我希望首先获得最高的值。

由于计算 m1 或 m2 对象的影响可能需要一些时间，我只是缓存值以便重用它们，因此在排序之前，我检查是否我有缓存值或者我是否需要计算它。

一旦计算出将 m1 或 m2 应用到我的结构的结果，我就会恢复更改。

您可以将其视为来自人工智能世界的某种评估排序: 我想根据我要应用的棋盘分数对棋步进行排序。

你对此有什么想法吗？

编辑: 由于可能涉及到涉及哈希和缓存的奇怪内容，因此我删除了对缓存的所有引用，但问题仍然存在。

evaluateComparator = (m1, m2) -> {
    double m1Value, m2Value;

    someClass.doSomething(m1);
    m1Value = someClass.getValue();
    someClass.undoSomething(m1);

    someClass.doSomething(m2);
    m2Value = someClass.getValue();
    someClass.undoSomething(m2);

    return Double.compare(m1Value, m2Value);
};

Answer 1

这并不完全算作比较器实现的简单代码。很多事情可能会出错，并且关键代码(doSomething 和 undoSomething)不会显示。从表面上看，m1 和 m2 是可变对象，如果它们发生变化而与之前的自身不相等，则排序算法就会中断。我认为这是对您的错误最有可能的解释。

解决问题的另一种方法(无论如何我都会推荐)是重新考虑您的方法。由于任何排序算法都必须至少接触每个值一次，因此惰性初始化方案只会增加复杂性的开销。相反，准备一个简单的移动列表，其中包含其值(您需要一个代表移动及其评估的对象)，然后仅使用以下命令对这个不可变对象(immutable对象)列表进行排序它们的自然顺序(一个简单的compareTo实现就可以做到)。到那时，您的错误将几乎没有隐藏的地方，并且可能在您完成之前就消失了。