偏序比较，以总计有序比较 [英] Partial Ordered Comparator to Total Ordered Comparator

问题描述

首先：这不是问题偏序比较的重复，而是建立在它

我的目标是要排序的对象的列表（例如，[2，一个，1]）就地使得排序后没有两个整数乱序

对于这一点，我用这个答案用下面的偏序的实施，并得到了抛出：IllegalArgumentException ：

  java.lang.IllegalArgumentException：如果比较的方法违反了一般的合同！
        在java.util.TimSort.mergeHi（TimSort.java:868）
        在java.util.TimSort.mergeAt（TimSort.java:485）
        在java.util.TimSort.mergeCollapse（TimSort.java:410）
        在java.util.TimSort.sort（TimSort.java:214）
        在java.util.TimSort.sort（TimSort.java:173）
        在java.util.Arrays.sort（Arrays.java:659）
        在java.util.Collections.sort（Collections.java:217）
        在MySortUtils.sortPartially（ArimsCollectionUtils.java:150）
 

这是因为所提出的比较有一个缺陷。示范：

使用一个偏序研究在所有对象实例，以供其 a.before（ B）当且仅当 A 和 B 都是整数和 A ＆LT; b 根据整数的自然顺序：

 前公共布尔（对象A，对象B）{
    //只有整数排序
    如果（一个的instanceof整数放大器;和b的instanceof整数）{
        诠释INTA =（（整数）一）.intValue（）;
        INT INTB =（（整数）B）.intValue（）;
        返回INTA＆LT; INTB;
    } 其他 {
        返回false;
    }
}
 

这样做的原因是，与下面的实施

 比较＆LT;对象＆gt; fullCmp =新的比较＆LT;对象＆gt;（）{

  //执行无耻地从采
  // http://stackoverflow.com/a/16702332/484293
  @覆盖
  公众诠释比较（对象01，对象02）{
    如果（o1.equals（02））{
      返回0;
    }
    如果（partialComparator.before（O1，O2））{
        返回-1;
    }
    如果（partialComparator.before（02，01））{
        返回+1;
    }
    返回getIndex（01） -  getIndex（02）;
  }

  私人地图＆LT;对象，整数GT; indexMap =新的HashMap＆LT;＆GT;（）;

  私人诠释getIndex（目标I）{
    整数结果= indexMap.get（我）;
    如果（结果== NULL）{
        indexMap.put（ⅰ，结果= indexMap.size（））;
    }
    返回结果;
  }
};
 

这可以产生一个周期中产生的顺序，因为

  //自2和A所无法比拟的，
// 2获取存储索引为0
//一个索引1
断言fullCmp.compare（2，一个）== -1

//因为A和1所无法比拟的，
//A保持它的索引1
// 2得到指数2
断言fullCmp.compare（一，1）== -1

//自1和2是比较的：
断言fullCmp.compare（1，2）== -1
 

都是真实的，即2版; 一，一个＆所述; 1和1所述; 2，这显然不是有效的全排序

这给我留下了最后一个问题：如何解决这个错误

解决方案

我不建议任何部分排序一个完整的解决方案。然而，对于特定的任务（比较整数忽略其他东西），你只需要决定之前，或其他任何东西之后是否整数去。该比较器，它假定整数先走应该很好地工作（使用Java-8语法）：

 比较＆LT;对象＆gt;比较=（A，B） - ＆GT; {
    如果（一个的instanceof整数）{
        如果（B的instanceof整数）{
            返程（（整数）一）.compareTo（（整数）B）;
        }
        返回-1;
    }
    如果（B的instanceof整数）
        返回1;
    返回0;
};
 

例如：

 名单，其中，对象＆gt;表= Arrays.asList（A，BB，1，3，C，0，广告，-5，E，2）;
list.sort（比较）;
的System.out.println（名单）; // [-5，0,1，2，3，一，BB，C，广告，电子]
 

First of all: this is not a duplicate of the question Partial Ordered Comparator but rather builds on it.

My goal is to sort a list of objects (e.g. [2, "a", 1]) in-place such that after sorting no two integers are out of order.

For this, I used the implementation in this answer with the following partial ordering and got a 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)

This is because the proposed comparator has a flaw. Demonstration:

use a partial ordering R over all Object instances for which a.before(b) iff a and b are both integers and a < b according to the integer's natural ordering:

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;
    }
}

The reason for this is that with the following implementation

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

  // Implementation shamelessly plucked from
  // http://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;
  }
};

this can yield a cycle in the produced ordering, since

// 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

are all true, i.e. 2 < "a", "a" < 1 and "1 < 2, which obviously is not a valid total ordering.

Which leaves me with the final question: How do I fix this bug?

解决方案

I cannot suggest a full solution for any partial ordering. However for your particular task (comparing integers ignoring anything else) you just have to decide whether integers go before or after anything else. This comparator which assumes that integers go first should work perfectly (using Java-8 syntax):

Comparator<Object> comparator = (a, b) -> {
    if(a instanceof Integer) {
        if(b instanceof Integer) {
            return ((Integer) a).compareTo((Integer) b);
        }
        return -1;
    }
    if(b instanceof Integer)
        return 1;
    return 0;
};

Example:

List<Object> list = Arrays.asList("a", "bb", 1, 3, "c", 0, "ad", -5, "e", 2);
list.sort(comparator);
System.out.println(list); // [-5, 0, 1, 2, 3, a, bb, c, ad, e]

这篇关于偏序比较，以总计有序比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！