1

まず第一に、これは質問Partial Ordered Comparatorの複製ではなく、それに基づいています。

私の目標は、オブジェクトのリスト ([2, "a", 1] など) をその場で並べ替えて、並べ替え後に 2 つの整数の順序が乱れないようにすることです。

このために、この回答の実装を次の半順序で使用し、次の結果を得ましたIllegalArgumentException。

java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeHi(TimSort.java:868)
        at java.util.TimSort.mergeAt(TimSort.java:485)
        at java.util.TimSort.mergeCollapse(TimSort.java:410)
        at java.util.TimSort.sort(TimSort.java:214)
        at java.util.TimSort.sort(TimSort.java:173)
        at java.util.Arrays.sort(Arrays.java:659)
        at java.util.Collections.sort(Collections.java:217)
        at MySortUtils.sortPartially(ArimsCollectionUtils.java:150)

これは、提案されたコンパレータに欠陥があるためです。デモンストレーション：

iffとが両方とも整数であり、整数の自然な順序付けに従っているRすべてのObjectインスタンスに対して半順序付けを使用します。a.before(b)aba < b

public boolean before(Object a, Object b) {
    // only integers are ordered
    if (a instanceof Integer && b instanceof Integer) {
        int intA = ((Integer) a).intValue();
        int intB = ((Integer) b).intValue();
        return intA < intB;
    } else {
        return false;
    }
}

この理由は、次の実装では

Comparator<Object> fullCmp = new Comparator<Object>() {

  // Implementation shamelessly plucked from
  // https://stackoverflow.com/a/16702332/484293
  @Override
  public int compare(Object o1, Object o2) {
    if(o1.equals(o2)) {
      return 0;
    }
    if(partialComparator.before(o1, o2)) {
        return -1;
    }
    if(partialComparator.before(o2, o1)) {
        return +1;
    }
    return getIndex(o1) - getIndex(o2);
  }

  private Map<Object ,Integer> indexMap = new HashMap<>();

  private int getIndex(Object i) {
    Integer result = indexMap.get(i);
    if (result == null) {
        indexMap.put(i, result = indexMap.size());
    }
    return result;
  }
};

これにより、生成された順序でサイクルが発生する可能性があります。

// since 2 and "a" are incomparable, 
// 2 gets stored with index 0 
// "a" with index 1
assert fullCmp.compare(2, "a") == -1   

// since "a" and 1 are incomparable,
// "a" keeps its index 1
// 2 gets index 2
assert fullCmp.compare("a", 1) == -1

// since 1 and 2 are comparable:
assert fullCmp.compare(1,   2) == -1

つまり、2 < "a"、"a" < 1、"1 < 2 です。これは明らかに有効な全順序付けではありません。

最後の質問は次のとおりです。このバグを修正するにはどうすればよいですか?

4

4 に答える 4

-1

要素を相互に比較できる要素にグループ化できます。canCompare(a, b) と canCompare(b, c) が !canCompare(a, c) という問題があります。ただし、これは当てはまらないと想定しています。

  • 1 つの要素から始めて、それを他のすべての要素と比較します。他の要素と比較にならない場合は、これまでの結果に追加します
  • 1 つ以上の要素に匹敵することがわかった場合は、それらを並べ替えて結果に追加します。
  • 要素がなくなるまでこれを続けます。

従来のソートアルゴリズムを使用していないため、これは Comparable には向いていません。ただし、これを行う必要がある場合は、必要な順序を決定し、必要な順序のインデックスを比較することから始めることができます。

簡単な回避策は、任意の並べ替え戦略を提供して、完全な順序付けを行うことです。あなたが抱えている問題は、並べ替える1, "a", 2とどうなるかということです。比較可能なすべてがすでに整っていると言うか、または言う1, 2, "a"かどうかにかかわらず、未定義のままにしておくことができます。"a", 1, 2後者で問題がなければ、バブル ソートが機能します。

半順序付けに TimSort を使用することはできません。a比較するとb、より大きいか、等しいか、より小さいかがわかると仮定します。他に選択肢はありません。

ただし、他の並べ替えアルゴリズムにはこの要件がありません。挿入ソートもその一つです。従わなければならない唯一の要件は、これらのエントリを注文することはできませんa < b.b < ca < c

ところで、一般的に平均はより大きいため、-1比較できない平均を持つことはできません。-1

あなたができることは

static final int INCOMPARABLE = Integer.MIN_VALUE;

// since 2 and "a" are incomparable, 
// 2 gets stored with index 0 
// "a" with index 1
assert fullCmp.compare(2, "a") == INCOMPARABLE;  

// since "a" and 1 are incomparable,
// "a" keeps its index 1
// 2 gets index 2
assert fullCmp.compare("a", 1) == INCOMPARABLE;  

// since 1 and 2 are comparable:
assert fullCmp.compare(1,   2) == -1;

assert fullCmp.compare(2,   1) == 1;
于 2015-08-12T16:24:47.317 に答える