Іноді, в процесі написання коду, ви можете зіткнутися з ситуаціями, коли не будете певні, яка з двох функцій виявиться ефективнішою (припускається, що кінцевий результат у обох функцій однаковий). Як це визначити?
Один з найпростіших способів — засікти час виконання кожного з фрагментів коду. У C++11 це робиться через бібліотеку chrono. Ми можемо легко інкапсулювати весь необхідний нам функціонал в клас, який потім будемо використовувати в наших власних програмах.
Ось клас:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <chrono> // для функцій з std::chrono class Timer { private: // Псевдоніми типів використовуються для зручного доступу до вкладених типів using clock_t = std::chrono::high_resolution_clock; using second_t = std::chrono::duration<double, std::ratio<1> >; std::chrono::time_point<clock_t> m_beg; public: Timer() : m_beg(clock_t::now()) { } void reset() { m_beg = clock_t::now(); } double elapsed() const { return std::chrono::duration_cast<second_t>(clock_t::now() - m_beg).count(); } }; |
Для його використання потрібно визначити об’єкт класу Timer у верхній частині функції main() (або звідки ви хочете починати відлік), а потім просто викликати метод elapsed() після частини коду, яку ви перевіряєте:
1 2 3 4 5 6 7 8 9 10 |
int main() { Timer t; // Тут знаходиться код, до якого застосовується таймінг std::cout << "Time elapsed: " << t.elapsed() << '\n'; return 0; } |
Розглянемо реальний приклад, де потрібно впорядкувати масив з 10 000 елементів. Скористаємося алгоритмом сортування методом вибору:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <iostream> #include <array> #include <chrono> // для функцій з std::chrono const int g_arrayElements = 10000; // загальна кількість всіх елементів масиву class Timer { private: // Псевдоніми типів використовуються для зручного доступу до вкладених типів using clock_t = std::chrono::high_resolution_clock; using second_t = std::chrono::duration<double, std::ratio<1> >; std::chrono::time_point<clock_t> m_beg; public: Timer() : m_beg(clock_t::now()) { } void reset() { m_beg = clock_t::now(); } double elapsed() const { return std::chrono::duration_cast<second_t>(clock_t::now() - m_beg).count(); } }; void sortArray(std::array<int, g_arrayElements> &array) { // Перебираємо кожний елемент масиву (крім останнього, він вже буде впорядкований, коли ми до нього дійдемо) for (int startIndex = 0; startIndex < g_arrayElements - 1; ++startIndex) { // У змінній smallestIndex зберігається індекс найменшого значення, яке ми знайшли в цій ітерації. // Почнемо з того, що найменший елемент в цій ітерації - це перший елемент (індекс 0) int smallestIndex = startIndex; // Потім шукаємо елемент менше нашого smallestIndex в решті масиву for (int currentIndex = startIndex + 1; currentIndex < g_arrayElements; ++currentIndex) { // Якщо знайшли елемент менше нашого найменшого елементу, if (array[currentIndex] < array[smallestIndex]) // то записуємо/запам'ятовуємо його smallestIndex = currentIndex; } // smallestIndex тепер найменший елемент в решті масиву. // Міняємо місцями наше стартове найменше значення з тим, яке ми виявили std::swap(array[startIndex], array[smallestIndex]); } } int main() { std::array<int, g_arrayElements> array; for (int i = 0; i < g_arrayElements; ++i) array[i] = g_arrayElements - i; Timer t; sortArray(array); std::cout << "Time taken: " << t.elapsed() << '\n'; return 0; } |
На комп’ютері автора результат 3-х прогонів коду становить 0.0508
, 0.0507
і 0.0499
секунди, тобто близько 0.05
секунди.
Тепер виконаємо те ж саме, але вже з std::sort зі Стандартної бібліотеки C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <iostream> #include <array> #include <chrono> // для функцій з std::chrono #include <algorithm> // для std::sort() const int g_arrayElements = 10000; // загальна кількість всіх елементів масиву class Timer { private: // Псевдоніми типів використовуються для зручного доступу до вкладених типів using clock_t = std::chrono::high_resolution_clock; using second_t = std::chrono::duration<double, std::ratio<1> >; std::chrono::time_point<clock_t> m_beg; public: Timer() : m_beg(clock_t::now()) { } void reset() { m_beg = clock_t::now(); } double elapsed() const { return std::chrono::duration_cast<second_t>(clock_t::now() - m_beg).count(); } }; void sortArray(std::array<int, g_arrayElements> &array) { // Перебираємо кожний елемент масиву (крім останнього, він вже буде впорядкований, коли ми до нього дійдемо) for (int startIndex = 0; startIndex < g_arrayElements - 1; ++startIndex) { // У змінній smallestIndex зберігається індекс найменшого значення, яке ми знайшли в цій ітерації. // Почнемо з того, що найменший елемент в цій ітерації - це перший елемент (індекс 0) int smallestIndex = startIndex; // Потім шукаємо елемент менше нашого smallestIndex в решті масиву for (int currentIndex = startIndex + 1; currentIndex < g_arrayElements; ++currentIndex) { // Якщо знайшли елемент менше нашого найменшого елементу if (array[currentIndex] < array[smallestIndex]) // то записуємо/запам'ятовуємо його smallestIndex = currentIndex; } // smallestIndex тепер найменший елемент в решті масиву. // Міняємо місцями наше стартове значення з тим, яке ми виявили std::swap(array[startIndex], array[smallestIndex]); } } int main() { std::array<int, g_arrayElements> array; for (int i = 0; i < g_arrayElements; ++i) array[i] = g_arrayElements - i; Timer t; std::sort(array.begin(), array.end()); std::cout << "Time taken: " << t.elapsed() << '\n'; return 0; } |
Результати 3-х прогонів на комп’ютері автора складають 0.000694
, 0.000693
і 0.000697
секунди, тобто близько 0.0007
секунди.
Таким чином, алгоритм std::sort() в 75 разів швидший за сортування, яке ми написали самі!
Що впливає на таймінг коду?
Таймінг коду є досить простим і прозорим, але ваші результати можуть істотно відрізнятися.
По-перше, переконайтеся, що ви використовуєте режим конфігурації “Release”, а не “Debug”. Під час режиму “Debug” оптимізація зазвичай відключена, а вона може мати значний вплив на результати. Наприклад, в конфігурації “Debug” виконання сортування елементів масиву через std::sort() на комп’ютері автора зайняло 0.0237
секунди, що в 34 рази більше, ніж в конфігурації “Release”!
По-друге, на результати таймінгу впливають процеси, які ваша система може виконувати у фоновому режимі. Для досягнення найкращих результатів переконайтеся, що ваша ОС не робить нічого, що інтенсивно навантажує процесор, жорсткий диск (наприклад, запущений пошук файлу або сканування антивірусом) або витрачає багато пам’яті (наприклад, ви граєте в ігри або працюєте в фото- або відеоредакторі).
Виконуйте таймінг як мінімум 3 рази. Якщо результати однакові — вибираємо середнє. Якщо один або два результати значно відрізняються один від одного, то запустіть таймінг ще кілька разів, поки не отримаєте краще уявлення про те, які з результатів виявилися «лівими». Зверніть увагу, деякі, здавалося б, невинні речі, такі як веб-браузери, можуть тимчасово збільшити навантаження на ваш процесор до 100%, коли сайт, на якому ви перебуваєте в фоновому режимі, виконує цілу купу JavaScript-скриптів (рекламні банери, запуск відео, складна анімація і т.д.). Запуск таймінгу кілька разів дозволить визначити, чи вплинула подібна подія на ваші результати.
По-третє, при порівнянні двох фрагментів коду намагайтеся не запускати нічого зайвого в фоновому режимі при прогонах коду, так як це також може вплинути на результати таймінгу. Можливо, ваш антивірус почав сканування у фоновому режимі, або ви вирішили послухати музику на стрімінговому сервісі (і це все в перервах між прогонами).
Рандомізація також може вплинути на таймінг. Якби ми відсортували масив, заповнений випадковими числами, то це вплинуло б на результати таймінгу (той факт, що числа є рандомними). Рандомізацію використовувати можна, але переконайтеся, що ваше стартове значення є фіксованим (тобто не використовуйте системний годинник в якості стартового значення) і результати рандомізації ідентичні при кожному запуску. Крім того, переконайтеся, що в фрагментах коду не використовується користувацький ввід, так як час очікування вводу від користувача не повинен враховуватися при визначенні ефективності коду.
Нарешті, ваші результати дійсні тільки для архітектури вашого комп’ютера, ОС, компілятора і системних/технічних характеристик. Ви можете отримати зовсім інші результати на інших системах, які мають інші сильні і слабкі сторони.