Правильный метод определения времени, сколько занимает алгоритм сортировки

Question

(с использованием Java)

Я тестирую сортирующие массивы, чтобы увидеть буквально, насколько быстро работают разные сортировочные массивы. Я хочу отсеять ошибочные времена, поэтому в идеале я хотел бы запустить таймер, запустить сортировку в цикле, скажем, 100 раз, остановить таймер, а затем разделить на 100, чтобы получить довольно точный показатель.

Проблема в том, что если бы я зацикливал один и тот же массив, он будет правильно сортироваться в первый раз, а затем после каждой сортировки будет продолжать сортировать уже отсортированный массив, а это не то, что мне нужно.

Может быть, я упускаю очевидное решение, но есть ли способ заставить его продолжать сортировать один и тот же исходный рандомизированный массив?

Я думал о переназначении вновь отсортированного массива обратно в исходный случайный массив каждый раз, но это испортило бы мой таймер.

спасибо за любые предложения

что я хотел бы сделать:

        startTime = System.nanoTime();
        for(int i=0; i<cntr; i++) {
            sort array
        }
        endTime = System.nanoTime();
        time = (endTime - startTime)/cntr;

Answer 1

Вы можете использовать метод System.currentTimeMillis(), чтобы получить текущее время, а затем вычесть, когда метод завершит выполнение.

long totalRuntime = 0;

for(int i = 0; i < 100; i++)
{
   long startTime = System.currentTimeMillis();
   sortArrays()
   long endTime = System.currentTimeMillis();

   totalRuntime += (endTime - startTime);
}

System.out.println("Algorithm X on average took " 
                    + totalRuntime/100 + " milliseconds);

Если вы хотите сделать это X раз, просто сохраняйте счетчик для каждого алгоритма и приращения,Затем вы можете разделить на общее количество прогонов в конце и сравнить.

Answer 2

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

int[] toBeSorted = new int[10000];
// fill the array with data
int[] copied = new int[10000];
System.arrayCopy(toBeSorted, 0, copied, 0, copied.length);
// prepare the timer, but do not start it
for (int = 0 ; i != 100 ; i++) {
    System.arrayCopy(copied, 0, toBeSorted, 0, copied.length);
    // Now the toBeSorted is in its initial state
    // Start the timer
    Arrays.sort(toBeSorted);
    // Stop the timer before the next iteration
}

Answer 3

поместите алгоритм сортировки в функцию и продолжайте вызывать функцию с тем же самым снова и снова и передавая массив функции после клонирования, используя метод clone. Вы можете вызывать функцию текущего времени и распечатывать ее каждый раз, когда запускаете цикл.

Answer 4

Идите с чем-то вроде этого

new array equals random array,
start timer
sort new array
stop timer
add time to your list of times
repeat until necessary

Пока вы копируете исходный массив каждый раз, вы никогда не будете сортировать исходный массив

Answer 5

Как правило, вы должны останавливать и запускать таймер между каждым запуском алгоритма, который вы тестируете, суммируя индивидуальное время, а затем деля его на количество запусков.Таким образом, любое «время установки» не включено, потому что таймер не работает во время установки.

Answer 6

Если вы хотите уничтожить память, просто сделайте 100 (или сколько угодно) копий одного и того же массива, прежде чем начинать синхронизацию.Если это не так, то время на сортировку и копирование вместе, а затем время просто на копирование, чтобы увидеть приблизительно, сколько времени было потрачено на копирование + сортировка + копирование.

Кроме того, sidenote: посмотрите на использование инфраструктуры сравнения, например Штангенциркуль вместо того, чтобы делать свой собственный "ручной" бенчмаркинг.Это проще, и они решили множество проблем, о которых вы, возможно, даже не подозреваете, которые могут испортить вам время.