Производительность пользовательского алгоритма сортировки (vs 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 раз медленнее.

Тем не менее, это не лучший способ сравнить методы в первую очередь. Как минимум, вы должны сортировать один и тот же исходный массив для каждого другого алгоритма. Вы также должны выполнить несколько итераций для каждого алгоритма и усреднить ответ. Результат одного испытания будет ложным и ненадежным в качестве хорошего сравнения.