Я выполняю некоторые тесты времени выполнения для моей реализации быстрой сортировки. Кажется, что из 100 последовательных измерений на одних и тех же входных данных первый вызов быстрой сортировки занимает примерно в 10 раз больше времени, чем все последующие вызовы. Является ли это следствием того, что операционная система готовится выполнить программу, или есть какое-то другое объяснение? Кроме того, разумно ли отбрасывать первое измерение при вычислении среднего времени выполнения?
На приведенной ниже гистограмме показано время выполнения (в миллисекундах) в зависимости от номера вызова метода. Каждый раз, когда метод вызывается, он обрабатывает одни и те же данные.
![execution time vs. method call number](https://i.stack.imgur.com/tRAfl.png)
Чтобы получить этот конкретный граф, основной метод вызывает quicksort_timer::time_fpi_quicksort(5, 100)
, реализацию которого можно увидеть ниже.
static void time_fpi_quicksort(int size, int runs)
{
std::vector<int> vector(size);
for (int i = 0; i < runs; i++)
{
vector = utilities::getRandomIntVectorWithConstantSeed(size);
Timer timer;
quicksort(vector, ver::FixedPivotInsertion);
}
}
getRandomIntVectorWithConstantSeed
реализован следующим образом
std::vector<int> getRandomIntVectorWithConstantSeed(int size)
{
std::vector<int> vector(size);
srand(6475307);
for (int i = 0; i < size; i++)
vector[i] = rand();
return vector;
}
Процессор и компиляция
ЦП: Broadwell 2,7 ГГц Intel Core i5 (5257U)
Версия компилятора: Apple LLVM версия 10.0.0 (clang-1000.11.45.5)
Опции компилятора: -std=c++17 -O2 -march=native