Здесь содержится 2000 операций увеличения счетчика и проверки. Требующееся для их выполнения время можно сэкономить, если инициализировать начальные значения оператором DATA во время компиляции. Если это сделать невозможно, тогда следует объединить эти два цикла.

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

СО 10 [=1,1000.2 А(1)=0.0 В(0=О.О А(Г+1)=0.0 В(Г+1) = 0.0 10 CONTINUE

Чрезмерное развертывание угрожает ясности и делает программу излишне ДЛИНРЮЙ.

Упрощение внутренних циклов. Несомненно, наиболее ценный ОДИНОЧНЫЙ прием ускорения заключается в упрощении внутренних циклов. Если ничего больше не делается для проверки эффективности, нужно хотя бы проверить, нельзя ли уменьшить количество вычислений во внутренних циклах.

Например, рассмотрим следующую структуру со вложенными циклами:

00 30 1 = 1,50

DO 20 J = 1,100 DO 10 К = 1,200

ОПЕРАТОР X

«

10 CONTINUE

20 CONHNUE

30 CONTINUE

A что, если действие оператора X никак не зависит от I, J или К? Там, где он находится, он будет выполнен миллион раз. Если его убрать из всей структуры циклов и разместить перед оператором DO 30, он будет выполняться только один раз.

Профили исполнения. Здесь следовало бы заметить, что многие компиляторы обладают встроенными программами оптимизации, которые могут автоматически повышать эффективность программы. Однако мы не хотели бы представить эти компиляторы в качестве единст-

венного средства повышения эффективности программы, особенно если можно повысить эффективность изменением логики алгоритма.

Время ценно, и мы не хотели бы его терять, проходя по всем строчкам программы ради экономии нескольких микросекунд времени центрального процессора. Существует ли эксперимент, который помог бы нам найти, какие именно части программы съедают большую часть времени выполнения? Если удастся выделить эти сегменты, то мы сможем сосредоточить на них наши усилия по проверке эффективности.

Один из хороших способов выполнения этого заключается в построении профиля исполнения программы. Работа программы контролируется набором таймеров и счетчиков, и выдается листинг, показывающий, сколько раз выполнялся каждый оператор и сколько единиц времени затрачено на выполнение каждого оператора. Библиотечные программы, вырабатывающие такие профили, становятся обычным средством на вычислительных установках.

Если нет готового пакета программ для построения профиля, не так уж трудно собрать грубые профили. Можно разместить счетчики в программе так, чтобы следить за количеством выполнений операторов или групп операторов. Получить точные оценки времени оказывается гораздо труднее. Многие внутренние часы не удобны для определения времени выполнения отдельных операций. Один из способов получения грубой оценки времени состоит в следующем. Найдите, сколько времени занимает выполнение простейшего возможного оператора присваивания, например А=2.0. Определите это как единицу времени. Затем найдите относительные продолжительности выполнения более сложных операторов; например, выполнение простого оператора присваивания с использованием индексированной переменной (такого, как А(1)=2.0) может занять две единицы времени. При небольшой тренировке и некотором вычислительном опыте можно построить довольно полную таблицу.

Статистические исследования с использованием профилей исполнения обнаружили замечательный факт, что менее чем 5% объема большинства программ поглощают приблизительно 50% времени выполнения. Как и следовало ожидать, внутренние циклы ответственны за большую часть этой концентрации.

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

проверка вычислительной сложности

Для большинства алгоритмов трудно проверить вычислительную сложность серьезно и убедительно. Возникают две главные проблемы: (1) выбор входных данных и (2) перевод результатов эксперимента в эмпирические кривые сложности.

Как мы выбираем данные для проверки сложности алгоритма? Стандартный метод состоит в прогоне алгоритма на некоторых случайных данных и в построении графиков зависимости продолжительности прогона от одного или более параметров, характеризующих размеры задачи. Какое количество случайных данных мы должны создать и насколько случайны случайные данные? Количество создаваемых данных обычно определяется терпением программиста и бюджетом машинного времени. Случайрюсть чаще всего определяется посредством равномерного или нормального распределения, так как эти распределения наиболее удобны.

Как быть с переводом выходных данных в эмпирические кривые сложности? Эта проблема, по существу, безнадежна, если входные данные зависят от трех или более параметров. Вычисления становятся очень трудными, и часто для достижения самого грубого заключения нужен невероятно большой объем выходных данных. К счастью, для многих программ размер задачи с достаточной точностью измеряется единственным параметром N, например для некоторых задач о сетях и для сортировки.

Как производится анализ для этих программ? Случайные данные прогоняют для некоторого диапазона N и для каждого значения N вычисляют средние длительности прогона. Последние изображают на графике как функции N и используют какой-нибудь метод для аппроксимации данных кривой заданного вида. Этот подход может оказаться информативным, особенно если он применяется для подтверждения теоретического анализа сложности.

Насколько серьезно следует относиться к выбору аппроксимирующей кривой? Мы не ыол<ем дать определенного ответа на этот вопрос, но имеется несколько полезных указаний. (Предупреждение: нетрудно найти контрпример для каждого из следующих правил.)

1. Согласие с аппроксимирующей кривой должно увеличиваться с увеличением размера выборки. Скорость роста должна быть меньше для более сложных алгоритмов. Так, грубо говоря, согласие должно быть лучше для хорошей линейной аппроксимации, чем для хорошей экспоненциальной аппроксимации.

2. Согласие с аппроксимирующей кривой должно убывать с ростом N. Скорость убывания должна быть больше для более сложных алгоритмов.

3. Никогда не доверяйте полиномиальной аппроксимации для алгоритма, который, как вы подозреваете, должен давать экспоненциальную зависимость. Можно получить разумную интерполяцион-