|
Речь шла вроде о том, что мы оцениваем время работы программы, замеряя момент ее старта и завершения. Проблема заключается в том, что накладные расходы могут результат этого измерения исказить.
Допустим, что программа заключается в многократном выполнении тела некоторого цикла, причем одна итерация цикла занимает очень малое время. Какой-нибудь метод последовательных приближений. Количество итераций достаточно велико, так что общее время выполнения программы, скажем, измеряется в десятках секунд. Для контроля того, как работает программа, можно, например, на каждой итерации выводить на экран номер этой итерации или же какую-нибудь дополнительную информацию. Последние несколько цифр номера итерации мелькают на экране очень быстро, но первые вполне видны. Мой опыт показывает, что на этом шаге если выводить данные не на каждой итерации, а, скажем, на каждой сотой или тысячной, то ускорение времени будет вполне заметным даже "на глаз". При том, что содержательная часть ровно такая же. Это пример накладных расходов от частого вывода на экран.
Аналогично могут быть накладные расходы от операций работы с диском. Могу привести пример из собственной практики. Необходимо было провести работу с некоторыми данными, которые были записаны в файлы. Файлы были небольшого размера и их было много. Программа работала реально медленно. Потом я склеил все данные в один огромный файл (размером в несколько гигабайт). Разумеется, для работы с ним пришлось применять специальные функции ОС. Ускорение от этой процедуры было на один-два порядка. Причина - в накладных расходах, связанных с процедурами открытия-закрытия файла.
Еще один пример, который я также реально наблюдал, связан с кешем жесткого диска. Прочитанные данные хранятся в этом кеше и при повторном чтении грузятся гораздо быстрее. При этом программа, подобная предыдущей, при двух последовательных запусках работала существенно разное время.
С многократными вызовами простых и сравнительно бессодержательных процедур и необходимостью их оптимизации я также сталкивался.
Что же касается проблем измерения времени, связанных с паралеллизмом, то это, конечно, проблема, в том смысле, что это нельзя учесть средствами самой программы. Но операционная система при распределении процессорного времени между потоками аккуратно подсчитывает, кто сколько получал, и имеются специальные функции, которыми можно у ОС спросить, сколько реально процессорного времени было выделено заданному потоку. Так что это решено.
Все это я к тому лишь, что существует ряд технических деталей, которые могут повлиять на время выполнения программы и исказить картину, если задача стоит о практической оценке трудоемкости чистого алгоритма.
|
, где 
число элементов массива.
