3

私のアプリケーションの 1 つで、Comparison メソッドがその一般的な契約に違反していることを示す IllegalArgumentException がスローされました。http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124やhttp://www.oracle.com/technetwork/java/javase/compatibility-417013など、問題の詳細を示すソースをいくつか見つけました。 html#sourceで、アプリケーションでこれを修正したいと考えていました。

しかし、問題を再現できないため、修正が正しいかどうかわかりません。

再現するために、問題をできるだけ単純化しようと試み、次のような小さなクラスを作成しました。

public class Sortee implements Comparable<Sortee>
{
  /** a value to sort by */
  public final int _x;

  public Sortee(int x)
  {
    _x = x;
  }

  public int compareTo(Sortee o)
  {
    return 1;
  }
}

Comparator と同等のものも作成しました。

public class SorteeIncorrectComparator implements Comparator<Sortee>
{
  public int compare(Sortee a, Sortee b)
  {
    return 1;
  }
}

別のクラスでは、Sortee オブジェクトの List を作成し、Collections.sort() バリアントを呼び出して IllegalStateException を引き起こしました。

private static void sort()
{
   List<Sortee> sortees = createSortees();

   Collections.shuffle( sortees );
   Collections.sort( sortees, new SorteeIncorrectComparator() );

   Collections.shuffle( sortees );
   Collections.sort( sortees );
}

しかし、IllegalStateException が発生することはありません。

Linux と Windows で試し、Java 1.7.0_21、23.21-b01 を使用して Windows の eclipse で試し、プロパティ java.util.Arrays.useLegacyMergeSort が設定されていないことを確認しました。

比較メソッドで常に 1 を返すことは、可換でも推移的でもないため、コントラクトを破る必要があると考えました。

IllegalStateException が発生しないのはなぜですか?

4

3 に答える 3

2 
public static void main(String[] args) {
    Object[] array = new Object[37];
    for (int i = 0; i < array.length; i++) {
        array[i] = new Object();
    }
    Arrays.sort(array, new Comparator<Object>() {
        private int result[] = {1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, 0, -1, -1, 0, -1, 0, 0, -1, 0, 0, -1, 0, 0, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        private int index;
        @Override
        public int compare(Object o1, Object o2) {
            return result[index++];
        }
    });
}
于 2013-09-27T19:37:42.080 に答える
1

コンパレータが a=b および b=c -> a=c に違反すると、これを再現できました。その後、timsort が文句を言うようです。私のテストは：

List<Integer> timSortTestList = new ArrayList<Integer>();
{
    for(int i=0; i<100; ++i) {
        timSortTestList.add(i);
        timSortTestList.add(i);
        timSortTestList.add(i);
    }
    Collections.shuffle(timSortTestList, new Random(42));
}
Comparator<Integer> broken = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        if (Math.abs(o1-o2) < 10) {
            return Compare.EQUAL; // WRONG
        }
        return Ordering.natural().compare(o1, o2);
    }
};
Collections.sort(timSortTestList, broken); // throws up

この質問を比較してください- おそらくこれが起こるときの一般的な規則があります.

于 2014-07-25T08:28:13.660 に答える