“比较方法违反其总合同！” - 寻找小样本数据集

可能重复：
“Comparison method violates its general contract!”“比较方法违反其总合同！” - 寻找小样本数据集

我有我要排序的Java 7，并得到部分排序的数据（> 700个项目）的大样本以下例外：

java.lang.IllegalArgumentException: Comparison method violates its general contract! 
    at java.util.TimSort.mergeLo(TimSort.java:747) 
    at java.util.TimSort.mergeAt(TimSort.java:483) 
    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)

现在我试图降低数据集的大小，使查找原因更简单。我写了一个小应用程序，它从大集合中挑选一个随机子集来重现异常。

private static final int SUBSET_SIZE = 32; 

public void testSorting() { 
    ... 
    final Random random = new Random(); 
    for (int i = 10000000; i-- > 0;) { 
     testFew(strings, random); 
    } 
} 

private void testFew(List<String> strings, Random random) { 
    final List<String> list = new ArrayList<String>(); 
    int index = 0; 
    for (int i = 0; i < SUBSET_SIZE; i++) { 
     final int rnd = random.nextInt(strings.size()/100) + 1; 
     index = (index + rnd) % strings.size(); 
     list.add(strings.get(index)); 
    } 

    try { 
     Collections.sort(list, MY_COMPARATOR); 
    } 
    catch (RuntimeException ex) { 
     for (String s : list) { 
      System.err.println(s); 
     } 
     throw ex; 
    } 
}

奇怪的是，找到一个样本复制是很简单的，如果子集包含至少32个项目，但我从来没有成功地找到了一套小。恕我直言，这听起来就像排序算法中的错误比我们的比较器。

来源

2012-11-04 Mot

你可以在这里发布你的比较？ – Baz

我打赌1000美元的错误是在你的代码中，而不是在排序算法中。为什么不把它的代码发布给我们来检查它，以及异常的完整堆栈跟踪？ –

斯蒂芬C处已经猜到了，这是正在使用的两种不同的排序方法的结果的错误。

看的java.util.TimSort代码：

static <T> void sort(T[] a, Comparator<? super T> c) { 
    sort(a, 0, a.length, c); 
} 

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) { 

    // ... 

    // If array is small, do a "mini-TimSort" with no merges 
    if (nRemaining < MIN_MERGE) { 
     int initRunLen = countRunAndMakeAscending(a, lo, hi, c); 
     binarySort(a, lo, hi, lo + initRunLen, c); 
     return; 
    } 

    // ...

MIN_MERGE的价值的确是32，并且把你的异常的方法仅称为另一种情况。

来源

2012-11-04 13:01:22

恕我直言，这味道就像排序算法中的错误比我们的比较。

对我而言，根据输入集合的大小，这个气味就像2种不同的排序算法一样。

虽然在排序实现中存在一个错误并不是不可能的，但是这个问题在您的Comparator中很可能是这样的......就像异常消息所说的那样。建议您将精力集中在代码上，而不是在库代码中寻找（可能不存在的）错误。

来源

2012-11-04 12:49:54

这意味着你的比较有这样compareTo(a, b) != -compareTo(b, a)

来源

2012-11-04 12:51:43

不，我已经检查过了。 – Mot

仍然愿意打赌，这是错误的地方。你似乎不愿意发布代码，所以我们可以检查。 ;） –

错误是我们比较（它违反了一个<乙& &乙<Ç - >一个< C），但我认为，这TimSort将总是导致堆栈跟踪这似乎是错误的。

来源

2012-11-04 13:37:42 Mot

喜你可以请你张贴完整的集合，原始格和固定的一个。实际上，问这个问题的原因是我在我们的prod env中得到了与String相同的错误，我试图找出它的实际破坏情况。所以没有数据 –

我的比较器很简单------新比较器（）{ public int compare（String str1，String str2）{ return str1.substring（3）.compareTo（str2.substring（3 ））; } } ---------可能它与yur原始的一样，仍然无法弄清楚它是如何破坏传递性的，请你帮忙 –

“比较方法违反其总合同！” - 寻找小样本数据集

回答

相关问题