如何計算比較器/可比較器中的比較次數？

Question

假設我有以下的compareTo：

public int compareTo(RandomClass o) { 
    if (this.value() < o.value()) { 
     return -1; 
    } else if (this.value() > o.value()) { 
     return 1; 
    } else { 
     return 0; 
    } 
} 

我想知道的比較確切的數字時，我打電話Arrays.sort(randomClassArray)，其中randomClassArray有100個對象？

Answer 1

考慮綁定一個原子整型字段稱爲counter，說你的收藏。在排序算法之前將其設置爲零，然後在compareTo內將其增加1（原子級）。

它需要是原子萬一您的排序算法是並行的。我會避開製作compareTo​​，因爲這可能會破壞任何並行化的好處。

也許它需要遞增兩次返回值爲1,0？

Answer 2

聲明public static int變量並在compareTo()方法中增加它。 Arrays.sort(randomClassArray)之後打印變量並重置它。

Answer 3

設置一個全局計數器。 下面是我的代碼：

公共類ComparatorCount {

static int counter = 0; 

public static void main(String[] args) { 
    Random random = new Random(); 
    List<RandomClass> randomClassList = new ArrayList<>(); 
    for(int i = 0 ; i < 100 ; i++) { 
     RandomClass rc = new RandomClass(); 
     rc.setValue(i + random.nextInt(100)); 
     randomClassList.add(rc); 
    } 

    Collections.sort(randomClassList); 

    randomClassList.forEach(x -> System.out.println(x)); 

    System.out.println("compare " + counter + " times in total."); 
} 

static class RandomClass implements Comparable<RandomClass> { 

    private int value; 

    public int value() { 
     return value; 
    } 

    public void setValue(int value) { 
     this.value = value; 
    } 

    public String toString() { 
     return "randomClass : " + value; 
    } 

    @Override 
    public int compareTo(RandomClass o) { 
     counter++; 
     if (this.value() < o.value()) { 
      return -1; 
     } else if (this.value() > o.value()) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

}

Answer 4

對我來說，最好的方法是使用Comparator類型的裝飾將總計數它被稱爲類似的東西：

public class Counter<T> implements Comparator<T> { 

    private final AtomicInteger counter; 
    private final Comparator<T> comparator; 

    public Counter(Comparator<T> comparator) { 
     this.counter = new AtomicInteger(); 
     this.comparator = comparator; 
    } 

    @Override 
    public int compare(final T o1, final T o2) { 
     counter.incrementAndGet(); 
     return comparator.compare(o1, o2); 
    } 

    public int getTotalCalled() { 
     return this.counter.get(); 
    } 
} 

然後你會提供自己的comparator到它，並使用Arrays.sort(T[], Comparartor)排序您的數組，如下：

Counter<SomeClass> counter = new Counter<>(myComparator); 
Arrays.sort(randomClassArray, counter); 
int totalCalled = counter.getTotalCalled(); 

Answer 5

你可以寫自己的類實現Comparator<RandomClass>接口：

public class CustomComparator implements Comparator<RandomClass> { 

    private final AtomicInteger counter; 

    public CustomComparator() { 
     this.counter = new AtomicInteger(0); 
    } 

    @Override 
    public int compare(RandomClass val1, RandomClass val2) { 
     this.counter.incrementAndGet(); 
     if (val1.value() < val2.value()) { 
      return -1; 
     } else if (val1.value() > val2.value()) { 
      return 1; 
     } 
     return 0; 
    } 

    public int getNumberOfOperations() { 
     return this.counter.intValue(); 
    } 
} 

然後調用static <T> void sort(T[] a, Comparator<? super T> c)功能與以下參數：

CustomComparator comparator = new CustomComparator(); 
Arrays.sort(randomClassAray, comparator); 
System.out.println("Number of operations = " + String.valueOf(comparator.getNumberOfOperations())); 

Answer 6

試試這個。

public class ComparatorCounter<T extends Comparable<T>> implements Comparator<T> { 

    public int counter = 0; 

    @Override 
    public int compare(T o1, T o2) { 
     ++counter; 
     return o1.compareTo(o2); 
    } 
} 

和

RandomClass[] array = new RandomClass[9]; 
// fill array 
ComparatorCounter<RandomClass> comp = new ComparatorCounter<>(); 
Arrays.sort(array, comp); 
System.out.println("compare count=" + comp.counter);