java - Java排序测试-

Question

在过去的几个月中，我用Java创建了一些实现数据结构的类，更具体地说是列表，二进制搜索树和二进制堆。我决定通过在Integer和n之间创建0值的10*n数组进行压力测试，然后以各种方式进行排序并测量时间。

最初只是出于好奇。显然，我期望我的课程所花费的费用远远超过普通的Arrays.sort()方法。但是，当我进行测试并将课程相互比较时，我发现了一些意外的惊喜。

这是测试的列表，包括详细信息和注释。

1.创建数组的副本，然后使用Java固有的Arrays.sort()方法对副本进行排序。评估的时间是Arrays.sort()方法的时间，即创建数组副本的时间不计算在内。正如预期的那样，这是最快的方法。



2.从数组创建一个列表，然后使用“插入排序”算法对列表进行排序。评估的时间是排序方法的时间，即从数组创建列表的时间不计算在内。由于插入排序的性能不是很好，因此此方法的成本约为数组方法的50倍。
3.通过重复BST方法从数组创建二叉搜索树（从现在开始为add()）。 BST不是像AVL或Red-Black那样的平衡树，而只是在Wikipedia上发现的普通BST：每个节点都链接到其他三个节点（parent，leftChild和rightChild） ，封装value等。此方法的费用约为列表方法的500倍，即数组方法的25,000倍。
4-5。从重复BH_1方法的数组中创建两个Binary Heap（从现在开始为BH_2和add()），然后将它们转换为重复extractMin()方法的两个（排序的）数组。两个BH属于同一类，并将值存储在Vector<Integer>中。两个BH的成本大约是BST的2倍，是数组方法的50000倍。但是有一个转折。
BH_2使用convertHeapToArray()接口的方法Heap<Integer>创建数组。 convertHeapToArray()调用方法extractMin()达n次，而extractMin()依次调用方法heapify()一次。
在使用方法BH_1的convertHeapToArray_1()中不会发生这种情况。我的“ new”方法没有调用extractMin()，而是直接执行extractMin()的代码-当extractMin()调用方法heapify()时，BH_1代替了执行其代码。简而言之，是一种复制粘贴，可以避免打几个电话。
 理论上，BH_1的成本应始终低于BH_2：相同的输入数据，相同的代码，较少的方法调用。但是，只有73％的情况是正确的！

我的问题如下：

1.为什么二叉搜索树排序方法（计算复杂度n log(n)，如果仅由add()创建则期望达到平衡）的成本是插入排序（计算复杂度n 2，如果n较小的话）的500倍比23）
2.为什么Binary Heaps（相同的Binary Search Trees计算复杂度，专门设计用于快速排序）的价格是Binary Search Trees的2倍？
3.而且，比以往任何时候都更加困惑，为什么在4个案例中有4个案例打出更少的电话比打出更多电话更昂贵？



convertHeapToArray()的代码：

    public default T[] convertHeapToArray(){
        T[] output = AArrays.createTarray(length(), min());

        for(int i=0 ; i<length() ; i++)
            output[i] = this.extractMin();
        return output;
    }
public T extractMin() {
    T min = storer.get(indexOfMinimum);
    AVector.swap(storer, indexOfMinimum, length);
    AVector.swap(storer, indexOfMinimum, length);
    length--;
    heapify(indexOfMinimum);
    return min;
}

报告（5000个测试，每个100个随机数组）：

The array use a Comparator<Integer>.
 A Comparator<Integer> executes a confront in 66083 nanoseconds.
The list use a Comparator<NodeList<Integer>>.
 A Comparator<NodeList<Integer>> executes a confront in 85973 nanoseconds.
The BST, BH_1 and BH_2 use a Relationship<Integer>.
 A Relationship<Integer> executes a confront in 107145 nanoseconds.

The total time for the array sorting is 239 717 392 nanoseconds.
The total time for the list sorting is 984 872 184 nanoseconds.
The total time for the BST sorting is 533 338 808 811 nanoseconds.
The total time for the BH_1 sorting is 1 055 836 440 689 nanoseconds.
The total time for the BH_2 sorting is 1 198 365 741 676 nanoseconds.

The medium time for the array sorting is 47 943 nanoseconds.
The medium time for the list sorting is 196 974 nanoseconds.
The medium time for the BST  sorting is 106 667 761 nanoseconds.
The medium time for the BH_1 sorting is 211 167 288 nanoseconds.
The medium time for the BH_2 sorting is 239 673 148 nanoseconds.
The first method for the Binary Heap has been faster than the second for 3 634 times out of 5 000.

编辑：

重新阅读我写的内容后，我意识到最初的问题并不十分清楚。请允许我纠正我的错误。

我知道该程序执行的实际时间与计算复杂度之间存在差异。我对所使用方法的计算复杂性毫不怀疑：数据结构简单，其代码通常取自Wikipedia。我确定编写的代码表现不佳。开始时并没有表现出来。

我的测试是在实际执行时间上。 Arrays.sort()方法作为参考参数包括在内。由于我在编写代码时并没有考虑性能，因此我在测试之前怀疑结果的成本会比预期的高。但是，我对实际成本超出其实际成本的预测被结果扔到了垃圾箱中。

例如，我相信更少的方法调用将导致更少的成本，但是我错了。这两个Binary Heaps的全部区别在于，第一个Binary Heap执行的代码与第二个Binary Heap的执行方法相同，只是方法调用更少（下面包含BinaryHeap的最小代码）。我希望第一个Binary Heap总是会花更少的钱：这被证明是错误的，我也不知道为什么。

使我感到困惑的另一件事是，二进制堆的成本高于 Binary Search Tree。使用的数组是随机创建的。在这种起始条件下，二进制搜索树的高度预计在 log(n)左右（Cormen，Leiserson，Rivest，Stein撰写的“算法简介”第12章第4章），但我从未听说过使用Binary Search的算法对数组进行排序的树：出于好奇，我将其包括在测试中。但是，对于少量元素（最初为100），二叉搜索树的发现始终比二叉堆快。

为什么会这样？什么时候二进制堆开始更方便了？包括转换Heap»Array的错误吗？

第三个意外结果是双链接 List的性能。与二叉搜索树一样，出于好奇，我将其包含在测试中。排序算法是一个非常基本的插入排序，它仅在一些元素上比我所使用的要少得多，因此速度更快，并且绝对不会为快速而创建整个类的代码。我以为这是我课程中速度最快的课程，却是最快的课程！而且我仍然不知道为什么。

这就是为什么我请教。我没有包含代码，因为在所有类之间，它都是大约3000行代码，其中大多数代码在测试中未使用。我不会读3k行代码，也不会期望随机的stackoverflow-er会这样做！但是，我包含了 BinaryHeap<T>的代码，大约300行。


BinaryHeap<T>的代码：

public class BinaryHeap<T> implements Heap<T> {
    private static final int indexOfMinimum = 1;
    private Vector<T> storer = new Vector<T>(indexOfMinimum + 10);
    private Relationship<T> relationship = null;
    // The class Relationship<T> has a single method whose signature is 
    // public boolean confront(T a, T b);
    // The reason I included it instead of a Comparator is that, in my code, the value null represents -∞
    // 
    // The following code works.
    // 
    // public class Relationship<T>{
    //  Comparator<T> c;
    //  public Relationship<T>(Comparator<T> c){    this.c = c; }
    //  public boolean confront(T a, T b){  return a==null ? true : c.compare(a,b); }
    // }

    // TODO | Constructors

    public BinaryHeap(Relationship<T> relationship){
        storer.add(null);
        this.relationship = relationship;
    }

    // TODO | Methods of the interface Heap

    public void add(T newData) {
        storer.add(null);
        updateValue(storer.size() - 1, newData);
    }
    public T extractMin() {
        T min = storer.get(indexOfMinimum);
        heapify(indexOfMinimum);
        return min;
    }
    public void updateValue(int indexOfToBeUpgraded, T newValue) {
        int i = indexOfToBeUpgraded;
        T support;
        if( i >= indexOfMinimum )
            {
            storer.set(i, newValue);
            while( i > indexOfMinimum && ! relationship.confront(storer.get(i/2), storer.get(i)) )
                {
                support = storer.get(i);
                storer.set(i, storer.get(i/2));
                storer.set(i, support);
                i = i/2;
                }
            }
    }
    private void heapify(int i){
        int j = i;
        int maximumIndexOfArray = storer.size();
        while( j <= maximumIndexOfArray/2 )         // i.e. if H[j] isn't a leaf of the Tree
            {
            int indexOfLocalMinimum =   relationship.confront(storer.get(j),    storer.get(2*j))                        
                        ?   (   relationship.confront(storer.get(  j), storer.get(2*j+1))   ?     j : 2*j+1 )
                        :   (   relationship.confront(storer.get(2*j), storer.get(2*j+1))   ?   2*j : 2*j+1 )   ;
            if( j != indexOfLocalMinimum )
                {
                AVector.swap(storer, j, indexOfLocalMinimum);
                j = indexOfLocalMinimum;
                }
            else j = maximumIndexOfArray;
            }
    }
    public default T[] convertHeapToArray(){
    T[] output = (T[]) Array.newInstance(min().getClass(), length());
        for(int i=0 ; i<length() ; i++)
            output[i] = this.extractMin();
        return output;
    }

    // TODO | Second version of the method convertHeapToArray, found out not to be improved

    public T[] convertHeapToArray_1(){
        int length = length(), j;
    T[] output = (T[]) Array.newInstance(min().getClass(), length());
        for(int i=0 ; i<length ; i++)
            {
    //      output[i] = this.extractMin();
                output[i] = storer.get(indexOfMinimum);
        //      heapify(indexOfMinimum);
                    j = indexOfMinimum;
                    int maximumIndexOfArray = storer.size();
                    while( j <= maximumIndexOfArray/2 )         // i.e. if H[j] isn't a leaf of the Tree
                        {
                        int indexOfLocalMinimum =   relationship.confront(storer.get(j),    storer.get(2*j))                        
                                    ?   (   relationship.confront(storer.get(  j), storer.get(2*j+1))   ?     j : 2*j+1 )
                                    :   (   relationship.confront(storer.get(2*j), storer.get(2*j+1))   ?   2*j : 2*j+1 )   ;
                        if( j != indexOfLocalMinimum )
                            {
                            AVector.swap(storer, j, indexOfLocalMinimum);
                            j = indexOfLocalMinimum;
                            }
                        else j = maximumIndexOfArray;
                        }
                }
        return output;
    }

Answer 1

计算复杂性不能度量纳秒，毫秒或任何类似的东西。它可以测量算法的运行时间如何随输入大小的变化而变化，而对于我或您为实现该算法可能要编写的代码的效率，它没有说什么。

现在，当您编写算法的实际实现时，您将引入开销，该开销取决于计算复杂性理论根本不关心的许多因素。

代码的性能取决于您选择的语言，您的执行环境，您所做的编程选择，编写执行代码的经验以及避免常见的性能陷阱等。

此外，在测试代码的性能时，很大程度上取决于您是否知道如何在执行环境中执行此操作。在具有数百个同时运行的进程的系统上，使用字节码翻译的，及时编译的，垃圾回收的语言（例如java），这是非常古怪的。

因此，您的问题的答案是您的比较是不平等的，因为a）您编写的代码编写得不好，b）某些东西的花费比您在Java中预期的要高得多，并且c）您尝试进行基准测试的系统是比您想象的更混乱，更少封闭。

为了进行符合计算复杂性理论的测试，您必须从理论上衡量代码的性能。这意味着您将不需要计算纳秒，而是计算理论值。这些将是节点访问次数和节点创建次数（以树为单位）。

但是，计算复杂度理论仍然成立，因此，即使您坚持计时，即使您对算法进行性能测试时，也要对较大的Ns进行几个数量级的测试（这可能意味着它们可以运行数年而不是数百纳秒），最终应该开始看到理论上预测的差异，因为从长远来看，尽管执行不佳的代码带来了不平等，但log N击败了N，N击败了log N，N击败了N2。

当然，由于实施技巧，性能测试中的算法和数据结构总是有可能与我们认为的算法和数据结构具有完全不同的计算复杂度特征。例如，您知道，要进行性能测试的链表可以在内部使用哈希映射来帮助提高其性能。但是我们只能判断您是否发布了代码，以便我们可以准确地了解发生了什么。