Эта статья завершает цикл материалов, начатый в № 7/01 и адресованный студентам и школьникам, интересующимся программированием. Были рассмотрены практически все аспекты интерфейса пользователя для спрайтовой игры (за исключением звука): перемещение по экрану одного или нескольких спрайтов, работа с мышью и клавиатурой, вывод текста и чтение файла формата BMP, отсчет времени и некоторые вопросы оптимизации.
Редакции хотелось бы знать мнение читателей, стоит ли в дальнейшем продолжать циклы статей, адресованные начинающему программисту: использование OpenGL для отображения динамичных 3D-сцен; внутренняя логика игр; элементы искусственного интеллекта, применяемые в компьютерных играх, и т. п.
Название статьи не следует понимать как «определение истинного времени», поскольку речь здесь пойдет о таком измерении малых интервалов времени, которое невозможно выполнить стандартными средствами ОС.
Программисту приходится довольно часто отслеживать время, например в игровых и мультимедийных приложениях, при разработке программ, работающих с аппаратной частью ПК, а также при проведении всевозможных тестов. Кроме того, нередко требуется отладить критичные ко времени исполнения фрагменты кода, для чего нужны «часы» с высокой разрешающей способностью.
КАК ИЗМЕРИТЬ ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММЫ, КОДА, МЕТОДА, ФУНКЦИИ, ЗАПРОСА | C# STOPWATCH | C# ПЛЮШКИ
Один из методов измерения времени уже был описан в журнале 1 , но он возможен только в одной ОС (DOS и совместимые с ней). Другие операционные системы обладают собственными инструментами измерения времени, например Windows включает сообщение таймера или функцию GetTickCount.
К сожалению, хотя такие средства и предоставляются разными ОС, они имеют общие недостатки, в первую очередь низкую точность и большую погрешность измерения. Так, в DOS время отсчитывается квантами по 55 мс, в Windows 95 — по 13,7 мс (видимо, эта величина зависит от конфигурации ПК), а в Windows 98/NT — по 5 мс.
Таким образом, получается интервал, который существенно больше принятого для отсчета измеряемой величины: для DOS — 0,01 с, для Windows — 1 мс. С периодичностью вызова сообщения таймера дело обстоит еще хуже. Их частота не превышает 18,2 в секунду, а минимальный интервал составляет все те же 55 мс. Кроме того, опыты показывают, что приращение времени — величина непостоянная. Попробуйте запустить следующий фрагмент программы:
t0 := GetTickCount;
for i := 0 to 10 do begin
t1 := t0;
repeat
t0 := GetTickCount;
until t0 <> t1;
c[i] := t0-t1;
end;
for i := 1 to 10 do
writeln(i:3,c[i]:3);
Если это приложение не будет единственным запущенным, то вы легко убедитесь в неритмичности системных часов.
Наряду с использованием GetTime и GetTickCount можно применить и более радикальные меры: в DOS — переопределение прерывания таймера, в Windows — употребление QueryPerformanceCounter. Однако и здесь есть свои недостатки.
Тем не менее уже начиная с Pentium средства, пригодные для измерения времени, находятся в центральном процессоре. К ним можно отнести 64-разрядный счетчик циклов тактовой частоты, показания которого считываются программно. Очевидно, значение тактовой частоты достаточно велико, чтобы обеспечить любую разумную точность.
Ты неправильно замеряешь время в Python! Или нет?
Беда только в том, что частота работы у всех процессоров разная и колеблется от 60 МГц до 3 ГГц. Поэтому счетчик следует отградуировать с помощью стандартных функций измерения времени ОС. Конечно, по абсолютной точности он будет уступать стандартным средствам для измерения больших интервалов времени (например, погрешность может составить несколько секунд за час — из-за неточности градуировки), но при определении малых интервалов, а также при вычислении отношения длительности двух измерений его точности вполне достаточно.
Измерение времени на основе внутреннего счетчика процессора реализовано в модуле, приведенном в листинге 1. Он содержит три функции для получения отсчетов времени, функцию для получения полного 64-разрядного значения счетчика (вдруг она кому-нибудь понадобится), а также (в качестве побочного продукта) функции, возвращающие измеренную частоту процессора и предполагаемую погрешность ее измерения.
Наличие трех функций измерения объясняется тем, что использовать 64-разрядные числа в большинстве случаев неудобно (пока еще не нашли широкого применения 64-разрядные процессоры), а 32-разрядный счетчик, работающий на высокой частоте, довольно часто обнуляется. Поэтому для измерения коротких интервалов времени следует предпочесть счетчик с максимальным разрешением, равным 1 мкс, а в остальных случаях — с более грубым.
Градуировка модуля измерения времени выполняется в блоке инициализации, но эта процедура доступна и извне. Она бывает нужна тогда, когда точность определения тактовой частоты процессора при загрузке может показаться недостаточной. Пример использования некоторых функций модуля приведен в листинге 2.
В блоке инициализации модуля происходят подсчет частоты процессора, оценка погрешности вычисления, а также определение коэффициентов деления для всех точек входа и масок для них. Последние необходимы для того, чтобы предотвратить переполнение при целочисленном делении 64-разрядного числа на 32-разрядное. Маска представляет собой максимальное число, не превосходящее делитель, все биты которого установлены в «1». Если маски не вычислять, а задавать константами, то на медленных процессорах будет слишком маленький период обнуления, а на тех, что ожидаются в будущем, вероятно, произойдет аварийное завершение программы из-за ошибки деления.
Чтобы поточнее определить частоту ЦП, измерения нужно проводить несколько раз, далее их массив сортируется и при вычислении берется только его центральная часть (наибольшие и наименьшие результаты отбрасываются). Таким способом удается отсечь отдельные измерения с большой погрешностью, характерные для многозадачных ОС и вызванные разделением времени.
Модуль написан для TMT Pascal 4.0 и совместим с любой из целевых платформ: DOS, Windows или OS/2, причем в двух последних, как консольное приложение 2 . Правда, при работе в стандартной оконной среде Windows в приложениях, использующих кодовую страницу 866, возникают проблемы с кириллицей. Поэтому здесь я изменил своему правилу применять в программах сообщения на русском языке. Другой способ решения проблемы описан во врезке.
Если необходимо переделать модуль для одноплатформного компилятора, не поддерживающего совместимую с DOS процедуру GetTime, то последнюю следует заменить стандартной операцией для выбранной ОС. Например, для Windows целесообразно выбрать GetTickCount, и тогда из цикла измерения можно будет убрать дополнительную проверку на обнуление сотых долей секунды.
Константы модуля подобраны для оптимальной работы при интервале приращения показаний системных часов, равном 55 мс, но модуль сохраняет работоспособность и при любых других, что, правда, порой сказывается на точности вычисления тактовой частоты процессора и, следовательно, на точности коэффициентов деления. Здесь необходимо пойти на определенный компромисс: при росте числа измерений (константа n) повышается точность последних, но в этом случае увеличивается время, приходящееся на них и, естественно, тот период, в течение которого пользователю придется простаивать в ожидании загрузки программы. При уменьшении числа измерений наблюдается обратная зависимость. Думаю, что время измерения не более 0,5 с можно считать вполне приемлемым. А если опираться на приращение времени, равное 5 мс, то лучше задать следующие значения констант:
const
n = 100;
Const1 : extended = 0.2;
Можно изменять n таким образом, чтобы время измерения не превышало фиксированной величины, например 500 мс. Однако для этого следует описать размеры массивов не менее чем 501 — на случай, если вдруг приращение времени составит 1 мс.
В таблице приведены процедуры измерения времени. Вот несколько рекомендаций по их применению.
GetTime — предназначена для получения показаний астрономического времени в часах, минутах и секундах. С некоторой натяжкой может быть использована для измерения временн?ых интервалов от нескольких секунд (при условии, что требуется точность не ниже 1%). Данная процедура неудобна из-за того, что нужно отслеживать переходы на следующие секунду, минуту, час, а также сутки. Она работает медленно из-за многочисленных промежуточных вызовов и преобразований. В 24 ч 00 мин 00 с показания сбрасываются.
GetTickCount — подходит для измерения интервалов времени от 0,5 с в случае, если допустима погрешность в пределах 1%. При этом она предпочтительнее всех остальных для измерения больших интервалов времени (в пределах нескольких суток), так как в отличие от GetTime не требует преобразований. Эта процедура позволяет определить время в удобных единицах и не несет в себе погрешности измерения частоты процессора. Данная процедура — самая быстрая, она выполняет наиболее простую работу, а именно читает значения переменной из оперативной памяти или даже из кэш-памяти процессора.
QueryPerformanceCounter — опрашивает при работе порты таймера, подключенного по шине ISA, или ее аналога в современных наборах микросхем. Работает очень долго — несколько миллисекунд, что существенно искажает результаты измерения. Поэтому диапазон ее применения начинается с интервалов в сотни микросекунд. Кроме того, сама единица измерения довольно неудобна. Тем не менее процедура не требует градуировки, возвращаемое ею значение никогда не переполняется и имеет достаточно высокое разрешение, так что она может быть полезна тогда, когда нужно использовать лишь одну операцию в очень широком диапазоне: от долей миллисекунд до нескольких месяцев и даже лет.
GetTimer_1 — применяется от десятков микросекунд до десятков секунд, если, конечно, не хочется «натыкаться» на переход через 0 чаще одного раза на 100 измерений. Впрочем, хороший стиль программирования требует, чтобы подобные ситуации специально отслеживались. И тогда процедуру можно будет безболезненно использовать для измерения времени в интервале до получаса.
GetTimer_50 — наверное, наилучший выбор для программ, написанных для использования на компьютере дома или в офисе. Счетчик переполнится лишь спустя сутки с небольшим после последней перезагрузки ПК, поэтому если компьютер ежедневно выключается или хотя бы перезапускается, то переполнение счетчика не грозит. В то же время процедура обеспечивает достаточную точность, например, при определении того, как распределяется вычислительная нагрузка между разными блоками при формировании одного кадра для игр в режиме реального времени.
GetTimer_1000 — несколько точнее, чем GetTickCount на небольших интервалах (до нескольких секунд), и менее точна на больших вследствие погрешности определения частоты. А если требуется знать не действительное значение времени, а отношение длительности двух измеренных интервалов, то всегда обеспечивает более высокую точность, чем GetTickCount. Кроме того, может использоваться в среде любой ОС.
GetCPUtick — для измерения длительности выполнения коротких фрагментов кода в тактах процессора, а также в качестве основы для разработки других систем измерения времени.
InitTimer — применяется для реинициализации таймера, т. е. для вычисления частоты процессора и всех необходимых констант заново. Пример использования дается в листинге 2.
В заключение следует еще раз обратить внимание на то, что функции GetTimer_XX нежелательно применять для определения времени суток, так как из-за погрешности измерения оно не будет совпадать с тем, которое показывают системные часы.
1 См. «Мир ПК», № 1/02, с.117.
2 Точнее, сам модуль сохраняет работоспособность и в GUI, но пример программы осуществляет вывод в консольное окно или файл.
Как работать с текстом в кодировке 866 из оконной среды Windows
При разработке консольных приложений и DOS-программ с помощью оконной среды (IDE) Windows возникает одна проблема, характерная только для нашей страны, а именно, несоответствие кодировок кириллицы: в DOS и консольном режиме используется кодовая страница 866, а в оконной среде — 1251. Проблема не является типично паскалевской, с ней сталкиваются все программисты, которые, используя оконную среду, пишут русскоязычные программы для DOS или консоли. Фактически задача разделяется на две части: достигнуть правильного отображения на экране текста в кодировке 866 и добиться соответствия странице 866 кодов, выдаваемых клавиатурой.
Первая часть решается просто: в качестве шрифта для отображения текста программы следует указать Terminal. Именно его используют консольные приложения, и после его применения текст программы будет отображаться на экране в соответствии с кодовой страницей 866. В среде ТМТ Паскаль для этого нужно внести изменения, выбрав Options•Environment•Display•Font name.
Источник: www.osp.ru
Как объяснить результаты измерения времени выполнения программы ?
Программа на C. Не могу понять, как интерпретировать результаты измерения работы локальной и внешней функции, т.е. когда ее код написан в том же файле, откуда она вызывается и в отдельном файле. Компьютер CPU i5-2500 3.30 GHz Windows 7. На ней стоит VirtualBox 4.1.6 c Ubuntu 10.04. Измеряется время вызова функции, которая много раз в цикле реверсирует переданный ей массив, размещаемый в куче вызывающей программой. Один раз меряем локальный вызов, а во втором случае вызов той же функции (с другим именем), определенной в своем файле. Windows
c:/Users/avp/src/sort $ gcc —version gcc.exe (GCC) 3.4.5 (mingw-vista special r3) c:/Users/avp/src/sort $ gcc -O3 t.c e.c c:/Users/avp/src/sort $ ./a 1000000 test 1000000 elements 1000 loops internal 8057 msec external 8456 msec c:/Users/avp/src/sort $ gcc t.c e.c c:/Users/avp/src/sort $ ./a 1000000 test 1000000 elements 1000 loops internal 10832 msec external 10518 msec c:/Users/avp/src/sort $
Заранее извиняюсь за объем, но привожу код. t.c
#include #include #include #include static long long mtime() < struct timeval t; gettimeofday( long long mt = (long long)t.tv_sec * 1000 + t.tv_usec / 1000; return mt; >static void swap (void *t, void *a, void *b, int size) < memcpy(t,a,size); memcpy(a,b,size); memcpy(b,t,size); >void rev (void *a, void *t, int n, int l, int size) < while (l—) < int i, j; for (i = 0, j = n-1; i < j; i++,j—) swap(t, a+i*size,a+j*size,size); >> main (int ac, char *av[]) < int n = 100000, l = 1000; if (ac >1) if ((n = atoi(av[1])) < 3) n = 100000; if (ac >2) if ((l = atoi(av[2]))
#include #include #include static void swap (void *t, void *a, void *b, int size) < memcpy(t,a,size); memcpy(a,b,size); memcpy(b,t,size); >void erev (void *a, void *t, int n, int l, int size) < while (l—) < int i, j; for (i = 0, j = n-1; i < j; i++,j—) swap(t, a+i*size,a+j*size,size); >>
Собственно смущает разница во времени выполнения на виртуальной машине. Какие объяснения этому факту можно привести ? Обратите внимание, это проявляется при -O3 и версия компилятора в винде другая. Но в чем именно может заключаться такая фантастическая оптимизация или почему виртуальная машина так влияет ? Может быть где-то в программе ошибка, а я ее не вижу ? Но, я обратил внимание на такое поведение системы при разработке других программ, а здесь привел ярко иллюстрирующий эту аномалию (?) пример.
Источник: ru.stackoverflow.com
Единицы измерения времени выполнения алгоритма
Для этой цели можно просто воспользоваться общепринятыми единицами измерения времени — секундой, миллисекундой и т.д. и с их помощью оценить время выполнения программы, реализующей рассматриваемый алгоритм. Однако у такого подхода существуют явные недостатки, поскольку результаты измерений будут зависеть от:
¦ быстродействия конкретного компьютера;
¦ тщательности реализации алгоритма в виде программы;
¦ типа компилятора, использованного для генерации машинного кода;
¦ точности хронометрирования реального времени выполнения программы.
Поскольку перед нами стоит задача измерения эффективности алгоритма, а не реализующей его программы, мы должны воспользоваться такой системой измерений, которая бы не зависела от приведенных выше посторонних факторов.
Таким образом, для анализа временной эффективности алгоритмов этот показатель будет оцениваться по количеству основных операций, которые должен выполнить алгоритм при обработке входных данных размера n.
Рассмотрим один важный пример. Предположим, что сор — время выполнения основной операции алгоритма на конкретном компьютере, а С (n) — количество раз, которые эта операция должна быть выполнена при работе алгоритма.
Тогда время выполнения программной реализации этого алгоритма на данном компьютере T(n) можно приблизительно определить по следующей формуле: Разумеется, эту формулу нужно использовать очень аккуратно. В значении счетчика С(n) не учитывается количество выполняемых алгоритмом операций, не относящихся к основным. Кроме того, обычно значение этого счетчика можно определить только приблизительно. Более того, значение константы Сор также можно определить лишь приблизительно и оценить ее точность весьма непросто. Тем не менее, эта формула дает приемлемую оценку времени выполнения алгоритма для небесконечно больших и небесконечно малых значений n. Она также позволяет ответить на вопросы: во сколько раз быстрее будет работать реализация данного алгоритма на компьютере, быстродействие которого больше нашего в 10 раз?
В самом деле, для достаточно больших n справедлива следующая формула:
Этому в процессе анализа эффективности при достаточно больших размерах входных данных не учитывают постоянные множители, а сосредотачиваются на оценке порядка роста (order of growth) количества основных операций с точностью до постоянного множителя.
Источник: studopedia.su