时间戳

首页 > 解决方案 > 自定义排序算法性能（对比 Arrays.sort() 和 parallelSort()）

java - 自定义排序算法性能（对比 Arrays.sort() 和 parallelSort()）

问题描述

我在 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 ========

这独立于：

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

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

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

我可以从局外人的角度来看待这个问题，这样我就知道如何改进我的算法了？

非常感谢，

克里斯。

标签： javaarrayssorting

解决方案

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

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

完成此操作后，您会注意到您的算法慢了大约 100 倍。

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

推荐阅读