比较java.util.Date时,比较方法违反了它的一般契约

Question

我收到以下错误:

Caused by: javax.faces.el.EvaluationException: java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at javax.faces.component.MethodBindingMethodExpressionAdapter.invoke(MethodBindingMethodExpressionAdapter.java:101) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at com.sun.faces.application.ActionListenerImpl.processAction(ActionListenerImpl.java:101) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at javax.faces.component.UICommand.broadcast(UICommand.java:315) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at javax.faces.component.UIViewRoot.broadcastEvents(UIViewRoot.java:786) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at javax.faces.component.UIViewRoot.processApplication(UIViewRoot.java:1251) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at com.sun.faces.lifecycle.InvokeApplicationPhase.execute(InvokeApplicationPhase.java:81) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at com.sun.faces.lifecycle.Phase.doPhase(Phase.java:101) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at com.sun.faces.lifecycle.LifecycleImpl.execute(LifecycleImpl.java:118) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at javax.faces.webapp.FacesServlet.service(FacesServlet.java:593) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    ... 29 more
Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:899) [rt.jar:1.8.0_65]
    at java.util.TimSort.mergeAt(TimSort.java:516) [rt.jar:1.8.0_65]
    at java.util.TimSort.mergeForceCollapse(TimSort.java:457) [rt.jar:1.8.0_65]
    at java.util.TimSort.sort(TimSort.java:254) [rt.jar:1.8.0_65]
    at java.util.Arrays.sort(Arrays.java:1512) [rt.jar:1.8.0_65]
    at java.util.ArrayList.sort(ArrayList.java:1454) [rt.jar:1.8.0_65]
    at java.util.Collections.sort(Collections.java:175) [rt.jar:1.8.0_65]

下面是我的比较方法代码.vo1.getAttribute()返回java.util.DateObject.

    @Override
    public int compare(DateComparableVO vo1, DateComparableVO vo2) {
        if (vo1 != null && vo1.getAttribute() != null && vo2 != null && vo2.getAttribute() != null) {
            return vo1.getAttribute().compareTo(vo2.getAttribute());
        }
        return -1;
    }

我的比较方法的实现有什么问题吗？

如果是空方案.

为什么下面的代码没有任何问题.

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.List;

public class TestMain {

    public static void main(String[] args) {
        List<Employee> employees = new ArrayList<Employee>();
        employees.add(new Employee(new Date()));
        employees.add(null);
        employees.add(new Employee(new Date()));
        employees.add(new Employee(new Date()));
        employees.add(null);
        employees.add(new Employee(new Date()));
        employees.add(null);
        System.out.println(employees.size());
        Collections.sort(employees, new EmployeeComparator());

    }

}

class Employee {


    private Date attribute;

    public Employee() {
        // TODO Auto-generated constructor stub
    }

    public Employee(Date attribute) {
        this.attribute = attribute;
    }


    public Date getAttribute() {
        return attribute;
    }

    public void setAttribute(Date attribute) {
        this.attribute = attribute;
    }

    @Override
    public String toString() {
        return "Employee [attribute=" + attribute + "]";
    }
}

class EmployeeComparator implements Comparator<Employee>{

    @Override
    public int compare(Employee vo1, Employee vo2) {
        System.out.println("VO1 : " + vo1 + " VO2 : " + vo2);

        if (vo1 != null && vo1.getAttribute() != null && vo2 != null && vo2.getAttribute() != null) {
            return vo1.getAttribute().compareTo(vo2.getAttribute());
        }
        return -1;
    }

}

产量

7
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : null
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : null
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null

我在理解比较中错过了一些重要的部分

Answer 1

用于比较的"合同"是比较函数必须定义总订单.总订单的要求之一是"不对称",这基本上意味着如果a <b,则b> a.在Java术语中,这意味着如果compare(a,b)(或a.compareTo(b))返回结果<0,则compare(b,a)(或b.compareTo(a))必须返回结果> 0.您的比较函数不遵守此规则; 如果x.getAttribute()为非null且y.getAttribute()为null,则compare(x,y)返回-1并compare(y,x)返回-1.TimSort有时会注意到这一点并在发现一个不会返回预期的比较时引发异常.

另一种看待它的方法:如果输入中有"特殊"值,你必须事先决定你想要的东西是什么顺序(除非你想让对象比较为"相等",顺序不是物).假设您的输入包含getAttribute()null为null的对象和getAttribute()非null的对象.您希望具有null属性的那些出现在输出中？你想如何订购它们？ "我不在乎"不是一种选择. 假设您希望所有null属性都是最后一个,但您不关心null属性对象的排序方式.然后你需要编写你的比较函数

• 具有非null属性的对象<具有null属性的对象;
• 具有null属性的对象>具有非null属性的对象;
• 具有null属性的两个对象被视为相等(比较函数返回0).

如果您希望null数据首先出现在数组中,那么前两个点中的<和>将被反转.如果你想要根据一些其他属性对两个具有null属性的对象进行排序,那么编写你的比较函数以便它可以做到这一点,但是你仍然需要确定具有null属性的对象在哪里出现相对于具有该属性的那些对象.非null属性.也许你选择哪一个并不重要.但是你必须选择一些东西,你必须编写比较函数以根据你选择的内容返回结果.

PS: 没有特别的理由为什么你的第二个代码片段有Employee作品而第一个没有.第二种情况下的比较器和第一种情况一样错误.但是,TimSort不会查看每对元素以确保比较符合合同(这将使其成为O(n ²)算法).我不熟悉TimSort的细节,但我怀疑只有当它有理由比较两个元素才能看到比较是(或许)<0或= 0,并且它"知道"如果比较函数符合合同,则不应该> 0.如果已经必须进行比较,那么检查结果为> 0是相当便宜的,但我怀疑TimSort在没有必要时调用比较器,因为比较器的执行时间超出了它的控制范围.所以你的第二个例子的基本原因是"你很幸运".

Answer 2

最后的盲目-1意味着null值不能稳定处理(并且会破坏合并排序算法).你可以做点什么

@Override
public int compare(DateComparableVO vo1, DateComparableVO vo2) {
    Date l = null, r = null;
    if (vo1 != null) {
        l = vo1.getAttribute();
    }
    if (vo2 != null) {
        r = vo2.getAttribute();
    }
    if (l == null && r == null) {
        return 0;
    } else if (l == null) {
        return -1;
    } else if (r == null) {
        return 1;
    }
    return l.compareTo(r);
}