sort(); java , 100 элементов сортирует быстрее чем 10

138
11 сентября 2019, 11:40

sort(); java , 100 элементов сортирует быстрее чем 10 почему так ?

 Random random = new Random();
    int[] array10 = new int[10];
    int[] array100 = new int[100];
    int[] array1000 = new int[1000];
    for (int i = 0; i < array10.length; i++) {
        array10[i]=random.nextInt(10000);
    }
    for (int i = 0; i < array100.length; i++) {
        array100[i]=random.nextInt(10000);
    }
    for (int i = 0; i < array1000.length; i++) {
        array1000[i]=random.nextInt(10000);
    }
// быстрая сортировка
        long start0 = System.nanoTime();
        Arrays.sort(array10);
        long end0 = System.nanoTime();
        long traceTime0 = end0-start0;
    long start1 = System.nanoTime();
    Arrays.sort(array100);
    long end1 = System.nanoTime();
    long traceTime1 = end1-start1;
    long start2 = System.nanoTime();
    Arrays.sort(array1000);
    long end2 = System.nanoTime();
    long traceTime2 = end2-start2;
    // в наносекундах
    System.out.println("Qsort");
    System.out.println("10 elements: " + traceTime0+"ns");
    System.out.println("100 elements: " +traceTime1+"ns");
    System.out.println("1000 elements: " +traceTime2+"ns");

Консоль: 

Qsort
10 elements: 974322ns
100 elements: 80737ns
1000 elements: 1101587ns
Answer 1

У вас неверная методика замера времени работы алгоритма. Попробуйте запустить сортировку меньшего массива последней, она станет заметно быстрее остальных: https://repl.it/repls/WordyLightgrayIntegers.

Вы замеряете всего один прогон алгоритма. В такой ситуации на результат замеров тут может влиять множество факторов - от "прогрева" JIT-компилятора и накладных расходов на загрузку класса Arrays до случайных всплесков использования CPU другими программами. Сделайте хотя бы 10000 прогонов для каждого массива и возьмите среднее время - результат будет более точным. Также можете сделать ручной "прогрев" – несколько раз отсортировать массивы вхолостую, и только после этого приступать к замерам.

Ну и на десерт – если посмотреть на реализацию сортировки в методе Arrays.sort(), то можно увидеть, что для небольших массивов (до 286 элементов) используется алгоритм QuickSort, а для совсем маленьких (до 47 элементов) - сортировка вставками. У последней сложность варьируется от линейной до квадратичной, в зависимости от того, насколько отсортированы данные в исходном массиве. Это ещё один аргумент в пользу неточности единичного замера.

Answer 2

Обернул код в while(true) получаю такие результаты. Полагаю дело может быть связано в отсутсвием прогрева при замерах.

Qsort
10 elements: 367ns
100 elements: 2932ns
1000 elements: 39953ns

Вот ссылка на вопрос про прогрев JIT

READ ALSO
Необычный цикл foreach
Java

Необычный цикл foreach

Увидел в проекте(Spring) вот такой код:

 130
Быстрый рендер видео в игре
Java

Быстрый рендер видео в игре

Есть играПри каждой отрисовке кадра вызывается функция render() Мне надо добавить видео в рендеринг имея только функцию renderImage(int startx, int starty,...

 122
Spring boot и моя ошибка
Java

Spring boot и моя ошибка

Не очень понимаю в чем ошибка Controller

 119
Разная высота выделения шрифта, в разных ос
CSS

Разная высота выделения шрифта, в разных ос

в Ubuntu 1604 в браузерах Chrome, Firefox а также на андроиде в Samsung Internet и Chrome; Шрифт подключаеться с помощью @font-face; Шрифт имеет следующую область выделения:

 121