2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Время работы алгоритма
Сообщение16.05.2007, 22:09 
Аватара пользователя
Приветы!
Написал несколько алгоритмов, хочу проверить время их работы.
В коде делаю такую штуку:
Код:
struct timeb startTime;
struct timeb stopTime;
ftime(&startTime);
//алгоритм
ftime(&stopTime);
double tspent=tend.time+((double)tend.millitm)/1000.0-(double)tstart.time-((double)tstart.millitm)/1000.0;
cout<<"Timespent = "<<tspent*1000.0<<endl;

Существуют ли другие (может быть более эффективные) способы померить время работы алгоритма?

 
 
 
 
Сообщение17.05.2007, 07:46 
Аватара пользователя
:evil:
В виндузе есть функции GetSystemTimeAsFileTime() и пара QueryPerformanceCounter() /
QueryPerformanceFrequency().

GetSystemTimeAsFileTime() имеет очень маленькие накладные расходы, но точность невелика: 10 или 15.625 в зависимости от конфигурации системы.

Query[…]Counter() имеет очень высокую точность, но требует переключения контекста в ядро, что заметно повышает время работы функции.

Всё вышесказанное относится к XP(-). Мне говорили, что служба времени в Висте переписана, и многое изменилось…

 
 
 
 
Сообщение17.05.2007, 14:33 
Здесь были два класса таймеров.
Первый - как раз на QueryPerformanceCounter() / QueryPerformanceFrequency().

 
 
 
 Re: Время работы алгоритма
Сообщение17.05.2007, 19:09 
botanik писал(а):
Написал несколько алгоритмов, хочу проверить время их работы.
Код с QueryPerformance..., который привел VLarin, дает более высокую точность, но я обычно стараюсь обходиться стандартными средствами и использую такой код:
Код:
double d;
int iLoop;
int numberOfLoops = 1000;
clock_t   StartTime, StopTime;
StartTime = clock();
for (iLoop=0; iLoop<numberOfLoops; iLoop++)
{
    // implementation of the algorithm
}
StopTime = clock();
d = (double)(StopTime - StartTime) / CLOCKS_PER_SEC;
cout << d / numberOfLoops << " sec" << endl;
Чтобы повысить точность измерения достаточно увеличить число циклов.
Если проверяемый код очень короткий, для получения приемлемой оценки нужно использовать много циклов, например 10000000. В таком случае можно отдельно замерить время выполнения пустого цикла и вычесть накладные расходы на for (){}.

 
 
 
 
Сообщение19.05.2007, 07:27 
Аватара пользователя
:evil:
Иногда компилятор ловчит, и оптимизирует пустой цикл иначе, чем цикл с содержимым. Поэтому я обычно сравниваю что нибудь типа:
Код:
for (iLoop=0; iLoop<numberOfLoops; ++iLoop) {
    f();
}
и
Код:
for (iLoop=0; iLoop<numberOfLoops; ++iLoop) {
    f();
    f();
}


Часто результат достовернее…

И еще (забыл уточнить): при измерении относительно больших интервалов времени в виндузе колебания результата в пределах 0.1 сек. и больше. Поэтому всерьез стабильны времена в секундах.

Кроме того, если задача счетная, то лучше не гонять на лаптопе: у них начинает нагреваться процессор, и система начинает пинать тактовую частоту.

 
 
 
 
Сообщение19.05.2007, 08:28 
Аватара пользователя
А еще можно загнать все алгоритмы в один модуль (разными функциями) и провести профилирование. Абсолютные времена работы здесь, конечно, ничего не покажут, но относительно друг друга сравнить очень даже можно. Заодно можно будет понять узкие места каждого из алгоритмов.

 
 
 
 
Сообщение19.05.2007, 09:28 
Аватара пользователя
Шарите :)

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

TO PAV:
Идея понравилась, но у меня уже оформлено несколько иначе ((

 
 
 
 
Сообщение20.05.2007, 09:21 
Использование таймеров имеет тот недостаток, что в общее время выполнения алгоритма складывается еще и временем выполнения служебных функций самой ОС. В некоторых случаях это время может внести значительную ошибку, например – даже относительно редкий вывод промежуточных результатов в окно консольного приложения может исказить результат.

PAV писал(а):
Абсолютные времена работы здесь, конечно, ничего не покажут, но относительно друг друга сравнить очень даже можно.


В принципе можно произвести подсчет количества тиков выполнения участка программного кода с учетом переключения ОС на выполнение других задач – нечто похожее есть в Диспетчере Задач (Windows).

Интересно, имеется такой подобный профайлер?

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group