java - 自定义排序算法性能(与 Arrays.sort() 和 parallelSort() 相比)

Question

我用 Java 实现了一个基本的排序算法，并将其性能与本地方法(Arrays.sort() 和 Arrays.parallelSort())的性能进行了比较。程序如下。

 public static void main(String[] args) {
    // Randomly populate array
    int[] array = new int[999999];
    for (int i = 0; i < 999999; i++)
        array[i] = (int)Math.ceil(Math.random() * 100);

    long start, end;

    start = System.currentTimeMillis();
    Arrays.sort(array);
    end = System.currentTimeMillis();
    System.out.println("======= Arrays.sort: done in " + (end - start) + " ms ========");

    start = System.currentTimeMillis();
    Arrays.parallelSort(array);
    end = System.currentTimeMillis();
    System.out.println("======= Arrays.parallelSort: done in " + (end - start) + " ms ========");

    start = System.currentTimeMillis();
    orderArray(array);
    end = System.currentTimeMillis();
    System.out.println("======= My way: done in " + (end - start) + " ms ========");
}


private static int[] orderArray(int[] arrayToOrder) {
    for (int i = 1; i < arrayToOrder.length; i++) {
        int currentElementIndex = i;
        while (currentElementIndex > 0 && arrayToOrder[currentElementIndex] < arrayToOrder[currentElementIndex-1]) {
            int temp = arrayToOrder[currentElementIndex];
            arrayToOrder[currentElementIndex] = arrayToOrder[currentElementIndex-1];
            arrayToOrder[currentElementIndex-1] = temp;
            currentElementIndex--;
        }
    }
    return arrayToOrder;
}

当我运行这个程序时，我的自定义算法在我的机器上始终比本地查询好几个数量级。这是我得到的代表性输出:

======= Arrays.sort: done in 67 ms ========
======= Arrays.parallelSort: done in 26 ms ========
======= My way: done in 4 ms ========

这独立于:

• 数组中元素的数量(在我的示例中为 999999)
• 执行排序的次数(我在for循环中尝试并迭代了很多次)
• 数据类型(我尝试使用 double 数组而不是 int 并没有发现任何区别)
• 我调用每个排序算法的顺序(不影响性能的整体差异)

显然，我的算法实际上不可能比 Java 提供的算法更好。我只能想到两种可能的解释:

• 我衡量绩效的方式存在缺陷
• 我的算法太简单了，遗漏了一些极端情况

我希望后者是正确的，因为我使用了一种相当标准的方法来衡量 Java 的性能(使用 System.currentTimeMillis())。但是，我已经广泛地测试了我的算法并且到目前为止还没有发现任何谬误 - 一个 int 有预定义的边界(Integer.MIN_VALUE 和 MAX_VALUE)并且不能为空，我想不出任何我没有涵盖的可能的极端情况。

我的算法的时间复杂度 (O(n^2)) 和本地方法的时间复杂度 (O(n log(n))))，这显然会造成影响。然而，我再次相信我的复杂性已经足够了......

我能否得到一个局外人的看法，以便我知道如何改进我的算法？

非常感谢，

克里斯。

Answer 1

您正在就地对数组进行排序，但您没有在每条路径之间重新打乱数组。这意味着您正在对最佳情况进行排序。在每次调用数组排序方法之间，您可以重新创建数组。

for (int i = 0; i < TEST_SIZE; i++)
    array[i] = (int)Math.ceil(Math.random() * 100);

执行此操作后，您会发现您的算法大约慢了 100 倍。

也就是说，这并不是首先比较这些方法的最佳方式。至少您应该为每种不同的算法对相同的原始数组进行排序。您还应该对每个算法执行多次迭代并对响应进行平均。单次试验的结果将是虚假的，作为一个好的比较是不可靠的。