Измерение времени работы программы с часами

Question

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

Например, приведенный ниже вывод функции clock () может показывать 30 секунд с большим входом, но когда мы используем реальный таймер, используя наши телефоны, основная программа занимает около 2 минут.

Чего нам здесь не хватает? Не правильно ли мы используем функцию clock ()? Почему такая большая разница (1,5 минуты)?

Спасибо

int n;
cout << "Enter n - lenght of array" << endl;
cin >> n;

vector<int> v(n);

for(int i = 0; i < n; ++i)
{
    v[i] = i;
}

auto rng = default_random_engine {};
std::shuffle(std::begin(v), std::end(v), rng);

clock_t begin = clock();

sort(v);

cout << "done";

clock_t end = clock();

cout <<"total time : " << (double)(end-begin) / CLOCKS_PER_SEC<<endl;

return 0;

Answer 1

Я запустил ваш код, заменив функцию sort на std::sort, для n=5000000 она показала 11.744s, затем я переместил строку clock_t begin = clock(); до объявления vector v, а время было 13.818s

Похоже, что выделение памяти, O (N) инициализация и перестановка могут занять много времени, и если вы выберете гораздо большее число для n, в зависимости от эффективности вашей функции sort для случайного набора ввода, инициализация может занять больше времени, чем сортировка.