Perché questo programma utilizza Collections.sort non riesce solo per gli elenchi di dimensioni 32 o superiori?

Question

Il seguente programma genera la seguente eccezione:

java.lang.IllegalArgumentException: Comparison method violates its general contract! 

Capisco il problema con il Comparator. Vedi Unable to replicate : "Comparison method violates its general contract!"

Non capisco perché fallisce solo per List s di dimensione 32 o superiore. Qualcuno può spiegare?

class Experiment { 

    private static final class MyInteger { 
     private final Integer num; 

     MyInteger(Integer num) { 
      this.num = num; 
     } 
    } 

    private static final Comparator<MyInteger> COMPARATOR = (r1, r2) -> { 
     if (r1.num == null || r2.num == null) 
      return 0; 
     return Integer.compare(r1.num, r2.num); 
    }; 

    public static void main(String[] args) { 
     MyInteger[] array = {new MyInteger(0), new MyInteger(1), new MyInteger(null)}; 
     Random random = new Random(); 
     for (int length = 0;; length++) { 
      for (int attempt = 0; attempt < 100000; attempt++) { 
       List<MyInteger> list = new ArrayList<>(); 
       int[] arr = new int[length]; 
       for (int k = 0; k < length; k++) { 
        int rand = random.nextInt(3); 
        arr[k] = rand; 
        list.add(array[rand]); 
       } 
       try { 
        Collections.sort(list, COMPARATOR); 
       } catch (Exception e) { 
        System.out.println(arr.length + " " + Arrays.toString(arr)); 
        return; 
       } 
      } 
     } 
    } 
} 

Answer 1

Dipende l'attuazione, ma in openjdk 8 la dimensione dell'array viene confrontato MIN_MERGE, che è pari a 32. Questo evita la chiamata a mergeLo/mergeHi che generano l'eccezione.

Da JDK/jdk/openjdk/7u40-b43 8-b132 7-b147 - 8-b132 /java.util.TimSort:

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, 
        T[] work, int workBase, int workLen) { 
    assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; 

    int nRemaining = hi - lo; 
    if (nRemaining < 2) 
     return; // Arrays of size 0 and 1 are always sorted 

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

    /** 
    * March over the array once, left to right, finding natural runs, 
    * extending short natural runs to minRun elements, and merging runs 
    * to maintain stack invariant. 
    */ 
    TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen); 
    int minRun = minRunLength(nRemaining); 
    do { 
     // Identify next run 
     int runLen = countRunAndMakeAscending(a, lo, hi, c); 

     // If run is short, extend to min(minRun, nRemaining) 
     if (runLen < minRun) { 
      int force = nRemaining <= minRun ? nRemaining : minRun; 
      binarySort(a, lo, lo + force, lo + runLen, c); 
      runLen = force; 
     } 

     // Push run onto pending-run stack, and maybe merge 
     ts.pushRun(lo, runLen); 
     ts.mergeCollapse(); 

     // Advance to find next run 
     lo += runLen; 
     nRemaining -= runLen; 
    } while (nRemaining != 0); 

    // Merge all remaining runs to complete sort 
    assert lo == hi; 
    ts.mergeForceCollapse(); 
    assert ts.stackSize == 1; 
} 

Answer 2

Java 8 utilizza TimSort algoritmo per ordinare l'ingresso. In TimSort c'è una fase di fusione che si verifica quando la lunghezza è almeno 32. Quando la lunghezza è inferiore a 32, viene utilizzato un semplice algoritmo di ordinamento che probabilmente non rileva la violazione del contratto. Lasciate che i commenti del codice sorgente di TimSort.java parlano da sé:

class TimSort<T> { 
    /** 
    * This is the minimum sized sequence that will be merged. Shorter 
    * sequences will be lengthened by calling binarySort. If the entire 
    * array is less than this length, no merges will be performed. 
    * 
    * This constant should be a power of two. It was 64 in Tim Peter's C 
    * implementation, but 32 was empirically determined to work better in 
    * this implementation. In the unlikely event that you set this constant 
    * to be a number that's not a power of two, you'll need to change the 
    * {@link #minRunLength} computation. 
    * 
    * If you decrease this constant, you must change the stackLen 
    * computation in the TimSort constructor, or you risk an 
    * ArrayOutOfBounds exception. See listsort.txt for a discussion 
    * of the minimum stack length required as a function of the length 
    * of the array being sorted and the minimum merge sequence length. 
    */ 
    private static final int MIN_MERGE = 32;