如何计算比较器/可比较器中的比较次数？

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