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

Question

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

Например, у меня уже есть hashmap<string, int> hmp; предполагая, что у меня "apple" в моем hashmap, я хочу знать, сколько времени занимает выполнение следующего оператора: hmp["apple"].

Как мне рассчитать время?

Спасибо!

Answer 1

Прежде всего, посмотрите на мой ответ на этот вопрос ; он содержит переносимую (windows / linux) функцию для получения времени в миллисекундах.

Далее сделайте что-то вроде этого:

int64 start_time = GetTimeMs64();
const int NUM_TIMES = 100000; /* Choose this so it takes at the very least half a minute to run */

for (int i = 0; i < NUM_TIMES; ++i) {
   /* Code you want to time.. */
}

double milliseconds = (GetTimeMs64() - start_time) / (double)NUM_TIMES;

Все готово! (Обратите внимание, что я не пытался его скомпилировать)

Answer 2

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

Answer 3

Вы можете рассмотреть график данных и получить его (математическую) функцию. Запустите несколько испытаний, скажем, с 10, 100, 1000, 10000 и 100000 итераций. Используя число итераций в качестве переменной x и полученное время в качестве переменной y, построите график. Из этого вы можете определить функцию, которая описывает производительность кода, используя линейную регрессию (также известную как подгонка кривой в программном обеспечении) - я использую Графический анализ для этого.

Повторите испытания с другими структурами данных / кодом и выполните ту же графическую процедуру, затем сравните свои графики и функции.

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

Answer 4

Если вы действительно хотите выбирать между структурами данных, вам нужно разработать тест, который, по крайней мере, приблизительно соответствует тому, как вы будете использовать эту структуру. Некоторые структуры работают лучше для небольших объемов данных, другие работают лучше для больших объемов данных. Некоторые работают лучше, когда вы выполняете много операций чтения, другие работают лучше, когда вы выполняете много операций вставки / записи. Некоторые работают лучше с данными, которые почти все одинаковы, а некоторые работают лучше с данными, которые очень различны. Некоторые алгоритмы работают лучше, если вы делаете их только один раз, другие работают лучше, если вы делаете их миллион раз, потому что они имеют лучшую локализацию кода, что повышает вероятность попадания в кэш. Что я хочу сказать, так это удачи:)