End;
Prime:= True;
End;
Begin
N:= 1000;
For I:= 2 to N do
If Prime(I) then
Writeln(I);
End.
В этих строках содержится ряд улучшений.
* Три оператора if в подпрограмме prime удаляют из рассмотрения числа, кратные 2, 3, и 5 соответственно. Если на основании этих проверок Вам не удается отсеять рассматриваемое число n, то приходится проверять его делимость на оставшиеся целые числа вплоть до корня квадратного из n. Начать эти проверки можно с числа 7, так как наличие операторов if исключает из рассмотрения все меньшие числа.
* Цикл for теперь работает с шагом 2, так как нет смысла рассматривать четные числа.
* Проверка i*i<=n заменила более дорогой, с точки зрения временных затрат, тест, основывающийся на вычислении квадратного корня.
Результатом всех этих изменений явилось то, что общее время выполнения уменьшилось более чем на одну секунду. Данные, приведенные на рисунке 1.7 показывают, что функция printf отнимает теперь 96 % всего времени выполнения.
Рис. 1.7 Временная и количественная статистика, PRIME4.
Сокращение времени ввода/вывода.
Изменение в доле времени, потребляемой оператором printf, говорит о том, что теперь быстродействие программы в большей степени ограничивается операторами ввода/вывода, чем ее вычислительной частью. Возможно, такое положение является вполне приемлемым. Но, хотя бы просто ради интереса, давайте попробуем выжать еще что-нибудь из этих операторов.
Загрузите PRIME5 в окно Module (Модуль) и посмотрите на 28 строку (строку 3 в Паскалевском варианте).
В Turbo C имеется более быстрый вариант функции printf, называемый cprintf, использование которого является единственным отличием программы PRIME5 от PRIME4. Функция cprintf обрабатывает ситуацию перехода на новую строку иначе, чем printf: в cprintf вместо единственного символа «новая строка» используется пара символов «возврат каретки»/«перевод строки» (\r \n).
Информация для пользователей Паскаля: система Turbo Paskal также содержит быстрый вариант Writeln (содержащийся в модуле Crt). Мы даем указание об использовании этой быстрой версии посредством включения оператора uses Crt в начало нашей программы. В этом заключено единственное отличие PRIME5PA от предыдущего варианта.
Вызовите локальное меню окна Module (Модуль) и установите «области» для каждой строки исходного текста PRIME5. Запустите PRIME5, после чего изучите количественные данные профилирования для строки 28 в PRIME5 (или строки 3 в PRIME5PA).
Более быстрый вариант функции вывода на каждых 168 вызовах экономит почти одну секунду.
Удаление пар символов cr/lf («возврат каретки»/«перевод строки») (PRIME6).
И, наконец, одно последнее изменение. Вместо того, чтобы выводить пару символов «возврат каретки»/«перевод строки» после каждого обнаруженного простого числа, попробуйте выводить просто символ «пробел». В этом и заключается единственное изменение, сделанное в программе PRIME6.
Загрузите PRIME6 (пользователям Паскаля необходимо загрузить PRIME6PA) и установите маркеры «области» на каждой строке, затем выполните эту программу.
О чудо! Удаление пар символов «возврат каретки»/«перевод строки» сократило время выполнения почти в 7 раз. Теперь стал очевиден тот факт, что переход на новую строку это дорогостоящая операция. В результате всех внесенных изменений времена выполнения и количества вызовов распределились довольно-таки равномерно.
(Рис. 1.8). Вряд ли нам удастся выжать еще что-нибудь из этой программы без основательной переработки алгоритма.
Рис. 1.8 Временная и количественная статистика программы PRIME6.
А что же дальше?
В этой главе мы научили Вас основам профилирования. К настоящему моменту Вы уже должны научиться обращаться с системой Turbo Profiler до такой степени, чтобы уметь загружать и профилировать программы, печатать содержимое различных окон, сохранять и восстанавливать статистику профилирования и менять расположение и размеры окон для облегчения анализа статистики.
На этом закончим наше обучение и покинем среду системы Turbo Profiler (выберите File| Quit (Файлы| Выход) или просто нажмите Alt-X).
Для того, чтобы получить более обширную информацию о среде системы Turbo Profiler, в том числе и о тех частях профилировщика, которые не были рассмотрены в данной главе, Вам необходимо обратиться к главе 4, являющейся полным справочным руководством по среде системы Turbo Profiler.
Если у Вас возникло желание дополнительно рассмотреть еще какие-то задачи, то мы бы порекомендовали Вам сделать следующее:
* Получите профили для программ, ищущих простые числа меньшие чем:
* 2 500,
* 5 000,
* 7 500,
* 10 000.
* Установите режим профилирования в состояние пассивного анализа (выбрав для этого команду Statistics| Profiling Options (Статистика| Параметры профилирования), что повлечет за собой появление блока диалога Profiling Options (Параметры профилирования)). Какие изменения на экране профилировщика последовали за этим? Какую информацию мы теряем при пассивном анализе? (Информацию о пассивном профилировании можно почерпнуть в главе 3.)
* Посмотрите как улучшатся характеристики программы при применении решета Эратосфена для нахождения простых чисел, не превышающих 10 000.
* Сравните случай применения функции позиционирования курсора с обычным переходом на новую строку.
Существует некоторое количество статей и книг, в которых рассматривается вопрос о получении профиля программы. Книга Джона Бентли «Создание эффективных программ» (Jon Bentley, Writing Efficient Programs), содержащая сводку правил создания эффективно работающего программного кода, предлагает всестороннюю обстоятельную методологию профилирования и включает в себя обширную библиографию.
Для того, чтобы извлечь из системы Turbo Profiler наибольшую пользу, необходимо понимать внутренние механизмы ее работы. Знание того, каким образом действует профилировщик, встретив маркер «области», или того, что происходит каждый раз, когда профилировщик прерывает выполнение программы позволит Вам отточить вашу технику профилирования, а также более адекватно задавать тип статистической информации, которую необходимо собрать для той или иной «области», и интерпретировать полученные данные.
Рассмотрим исходный текст PTOLL и PTOLLPAS: