Измерение времени решения задачи с помощью ЭВМ

Измерение времени решения задачи для разных объёмов исходных данных — важная составляющая процедуры тестирования любой программы. Для измерения времени можно применять специальные приборы (секундомер) или средства, предоставляемые системой программирования (профайлер). Но для исследования алгоритма удобнее всего организовать измерение времени в самой программе тестирования, используя для этого средства, предоставляемые системой программирования.

1.4.1. Использование функции clock ()

Функция clock() возвращает значение счётчика тиков внутренних часов ПЭВМ как 32-битное целое типа clock_t, что соответствует unsignedlong. Для измерения времени обработки множеств нужно вызвать функцию clock () в момент, когда в памяти готовы исходные данные, и в момент, когда получен результат, а затем найти разность двух отсчётов.

Каждый тик соответствует 1/50 с, т. е. 0,017 с, следовательно, о какой-либо точности измерения времени функцией clock() можно говорить, если измеряемый интервал времени — порядка нескольких секунд. Чтобы добиться этого, измеряемый процесс приходится многократно повторять (до 1 000 000 раз и даже более). Полученную разность отсчётов времени можно затем разделить на количество повторений.

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

1) исходные множества не должны искажаться, их память нельзя использовать для получения результата вычислений;

2) не должно быть «утечки памяти» — выделения в динамической памяти большего объёма, чем освобождается после вычислений. Так, в варианте со списками до начала вычислений следует освобождать память из-под всех результатов, полученных предыдущим проходом.

Другие функции стандартной библиотеки time.h (например, функцию time() и т. п.) использовать нет смысла, поскольку источник информации о времени у них всех один, и точность измерения у них не больше, чем у clock().

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

1.4.2. Практикум по теме