Проверка эффективности выбора времени сортировки медленно в начале - PullRequest
Новая
       25

Проверка эффективности выбора времени сортировки медленно в начале

1 голос
/ 03 ноября 2019

Я проверяю эффективность выбора. Но сроки в начале очень длинные. Вот результаты временной эффективности для сортировки выбора. 

Run: | 100 : 560128 nanoseconds |
Run: | 200 : 3072 nanoseconds |
Run: | 400 : 1707 nanoseconds |
Run: | 800 : 1707 nanoseconds |
Run: | 1600 : 1365 nanoseconds |
Run: | 3200 : 1365 nanoseconds |
Run: | 6400 : 1707 nanoseconds |
Run: | 12800 : 1365 nanoseconds |
Run: | 25600 : 1365 nanoseconds |
Run: | 51200 : 1365 nanoseconds |
Run: | 102400 : 1707 nanoseconds |
Run: | 204800 : 1707 nanoseconds |
Run: | 409600 : 1366 nanoseconds |
Run: | 819200 : 1707 nanoseconds |
Run: | 1638400 : 4437 nanoseconds |
Run: | 3276800 : 5120 nanoseconds |

При размере массива 100 отчетливо видно, что время составляет 560128 наносекунд. Затем при размере массива 200 он падает до 3072 наносекунд. Почему время занимает так много времени в начале и падает после того, как размер списка равен 200? Потому что это не должно быть правильное время для сортировки выбора.

Это метод, который я написал для теста эффективности на сортировке выбора: 

    public void testQuicksort() {
        for (int archerAmount = 100; archerAmount < 5000000; archerAmount *= 2) {
            List<Archer> unsortedArchersForSelInSort = new ArrayList<>(archerAmount);
            StopWatch timer = new StopWatch();
            timer.reset();
            timer.start();
            List<Archer> sortedArchersSelInSort = ChampionSelector.selInsSort(unsortedArchersForSelInSort, comparator);
            timer.stop();
            System.out.printf("Run: | %d : %d nanoseconds |\n", archerAmount, timer.getNanoTime());
        }
    }

Это сортировка выбора:

public static List<Archer> selInsSort(List<Archer> archers, Comparator<Archer> scoringScheme) {

        for (int i = 0; i < archers.size(); i++)
        {
            int minArcherIndex = i;

            for (int a = i; a < archers.size(); a++)
            {
                if (scoringScheme.compare(archers.get(minArcherIndex), archers.get(a)) > 0)
                {
                    minArcherIndex = a;
                }
            }

            Archer swapArcher = archers.get(i);

            archers.set(i, archers.get(minArcherIndex));
            archers.set(minArcherIndex, swapArcher);

        }

        return archers;
    }

Секундомер, который я использовал: https://commons.apache.org/proper/commons-lang/javadocs/api-3.9/org/apache/commons/lang3/time/StopWatch.html

...