Как узнать время выполнения сортировки в C++?

Question

[IvankoPo]

В программировании новичок, недавно начал изучать сортировки, возник вопрос как можно вывести в консоль время выполнения моей сортировки.
Какие методы есть?

Comments

[Толстый Лорри]

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

Answer 1

[Mercury13]

Используйте либо time.h из Си, либо std::chrono из Си++11. Вот пример по второму.

#include <iostream>
#include <chrono>

int main()
{
    using Time = std::chrono::time_point<std::chrono::high_resolution_clock>;
    using Diff = std::chrono::milliseconds;

    Time t1 = std::chrono::high_resolution_clock::now();
    int i;
    std::cin >> i;
    Time t2 = std::chrono::high_resolution_clock::now();
    Diff diff = std::chrono::duration_cast<Diff>(t2 - t1);
    std::cout << diff.count() << " ms" << std::endl;
    return 0;
}

Answer 2

[Максим Мосейчук]

const std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
my_sort();
const std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();

Answer 3

[Дмитрий]

Mercury13 и fshp ответили верно.
С одним лишь исключением: std::chrono::high_resolution_clock — не монотонные часы. Т. е. они могут дрифтить даже относительно RTC, а этот дрифт будет корректироваться и влиять на результаты измерений. Например, когда вы будете делать измерения, и между стартом и стопом к вам прилетит синхронизация NTP.

Использовать нужно монотонные часы, для этого предназначены std::chrono::steady_clock. Они независимы от изменений и специально предназначены для измерений интервалов.

Comments

[Максим Мосейчук]

Хорошее замечание, спасибо.
А разрешение у этих часов такое же?

[Дмитрий]

fshp: зависит от реализации. Часто это даже алиас на high_resolution_clock. Но не всегда, поэтому лучше их различать. Можно просто вызвать статический метод is_steady у high_resolution_clock. Он часто возвращает true. Но чтоб не париться, лучше сразу для измерений юзать steady_clock.

[Максим Мосейчук]

Дмитрий: если верить документации, то это high_resolution_clock может являться алиасом. Т.е steady_clock всегда монотонные, а high_resolution_clock по ситуации.

[Дмитрий]

fshp: ну да, я это имел в виду.

[Mercury13]

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

[Дмитрий]

На самом деле, там такой зоопарк... пару лет назад тестил, юзать в продакшене или не юзать. Так вот, вижуал студия вообще не следует ничему, они как хотят реализуют эти часы. У них high_resolution_clock были с разрешением 15мс на то время... очень высокое разрешение, однако! При том, что через их же winmm можно было выжать разрешение около 1мс.
Сейчас ситуацию не знаю, правда. Может, что-то лучше стало. У юниксов, вроде, всё нормально с этим, хотя, зависит от настроек ядра.