部分有序比较器到全序比较器

Question

首先：这不是问题 Partial Ordered Comparator 的重复，而是建立在它的基础上。

我的目标是就地对对象列表（例如 [2, "a", 1]）进行排序，以便在排序后没有两个整数出现顺序错误。

为此，我使用 this answer 中的实现和以下部分排序并得到 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)

这是因为提议的比较器存在缺陷。示范：

对所有 Object 个实例使用部分排序 R a.before(b) 当且仅当 a 和 b 都是整数并且 a < 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
  // 
  @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，这显然不是有效的总排序。

最后一个问题是：我该如何修复这个错误？

Answer 1

您可以将元素分组到可以相互比较的元素中。你有 canCompare(a, b) 和 canCompare(b, c) 但 !canCompare(a, c) 的问题。但是我们假设情况并非如此，您可以

从一个元素开始，然后将其与所有其他元素进行比较。如果它与任何其他元素无法比较，则添加到目前的结果
如果您发现它与一个或多个元素相当，请对这些元素进行排序并将它们添加到结果中。
继续这样做，直到没有更多元素为止。

这不适合比较，因为您没有使用传统的排序算法。但是，如果您必须这样做，您可以先确定所需的顺序并比较所需顺序的索引。

一个简单的解决方法是提供一个任意的排序策略，这样您就可以完全排序。您遇到的问题是，如果您对 1, "a", 2 进行排序，您希望发生什么？无论您得到 1, 2, "a" 或 "a", 1, 2 还是您说所有可比较的东西都已经准备就绪，您都可以将其保留为未定义。如果后者没问题，冒泡排序就可以了。

您不能使用 TimSort 进行部分排序。它假定如果您比较 a 和 b，您可以说它是大于、等于还是小于。没有其他选择。

但是，其他排序算法没有这个要求。插入排序就是其中之一。唯一的要求是 a < b 和 b < c 然后 a < 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;

Answer 2

我无法为任何部分排序建议完整的解决方案。但是，对于您的特定任务（比较整数而忽略其他任何内容），您只需要决定整数是在其他任何内容之前还是之后。这个假设整数首先出现的比较器应该可以完美地工作（使用 Java-8 语法）：

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

示例：

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]

Answer 3

如果您想要的只是根据它们自己的自然顺序对整数（而不是其他一些完全有序的类型）进行排序，并且如果您不关心其他元素相对于整数的排序方式，但您确实想要结果是正确的总排序（即传递和反对称），然后对您开始时拒绝的答案进行微小的改动就可以解决问题：

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

class IntegerPartialOrderComperator implements Comparator<Object> {
    @Override
    public int compare(Object o1, Object o2) {
        return getIndex(o1) - getIndex(o2);
    }

    private int getIndex(Object i) {
        Integer result = indexMap.get(i);
        if (result == null) {
            if (i instanceof Integer) {
                result = (Integer) i*2;
            } else {
                result = indexMap.size()*2+1;
            }
            indexMap.put(i, result);
        }
        return result;
    }

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

    public static void main(String[] args) {
        Comparator<Object> cmp = new IntegerPartialOrderComperator();
        // since 2 and "a" are incomparable,
        // 2 gets stored with index 4 and "a" with index 3
        assert cmp.compare(2, "a") > 0;

        // since "a" and 1 are incomparable,
        // "a" keeps its index 3 while 1 gets index 2
        assert cmp.compare("a", 1) > 0;

        // since 1 and 2 are comparable:
        assert cmp.compare(1, 2) < 0;
    }
}

这使用运行时间为所有值生成的索引作为比较的基础，其中偶数用作 Integer 的索引，奇数用作任何值的索引其他可能会出现。

如果您的数字可以变大 (> 2^30-1) 或变小 (< -2^30)，那么加倍将溢出，因此您必须求助于 BigInteger 作为值类型索引图。

请注意，同样的技巧不适用于 Integer 之外的许多类型，因为您需要通过索引号在第一名。我认为如果不可能的话，解决方案会变得更加棘手：计算新元素的索引可能会花费与先前比较的元素数量成线性关系的最坏时间，这只会破坏 Comparator 进行排序（高效）。

Answer 4

您正在比较器内部使用 getIndex()。这通常没问题，但在排序算法内部交换值时就不行了。
因此，选择一个仅依赖于值而不是它们在数组中的位置的比较器函数。
您可以使非整数在所有整数之前或之后排序。要么让它们都相等（比较器中的return 0），要么使用一些额外的标准来区分它们。

部分有序比较器到全序比较器

Partial Ordered Comparator to Total Ordered Comparator

java

algorithm

sorting

partial-ordering