2. По умолчанию активируется блок ввода File Name (Имя файла), содержащий шаблон имени файла вида *.EXE. Нажмите ENTER.
3. В блоке списка Files (Файлы) переместите световой маркер на PRIME1.EXE (или PRIME1PA.EXE), используя для этого клавиши «стрелка вверх» и «стрелка вниз».
4. Нажмите ENTER. Система Turbo Profiler загрузит программу PRIME1 (PRIME1PA) в окно Module (Модуль).
5. Распахните окно Module (Модуль) (нажав для этого F5). Обратите внимание на то, что в строке 4 появилась подпрограмма prime (Prime).
Сразу бросаются в глаза два отличия от предыдущего примера:
* Во-первых, исчез массив primes. Данная программа не использует способ деления на меньшие простые числа, она просто содержит в себе цикл, в котором делается попытка разделить рассматриваемое число на все нечетные числа, строго меньшие данного. Вначале результатом этого будет увеличение числа итераций по сравнению с предыдущим примером, но мы увидим, что в конечном итоге, после переработки данного примера, можно получить более рациональную и качественную программу.
* Во-вторых проверка на то, является ли данное число простым, выделена в самостоятельную подпрограмму, которая вызывается из основной программы.
Пометьте «области» в загруженной программе (выбрав для этого команду Add Areas|Every Line (Добавить «области»|Каждая строка) в локальном меню окна Module (Модуль)), нажмите ENTER, затем запустите PRIME1 (нажав F9) под управлением системы Turbo Profiler и ознакомьтесь с полученной статистикой. Затем выберите Display из локального меню окна Execution Profile (Профиль выполнения) для того, чтобы открыть блок диалога Display Options (Параметры изображения) и привести кнопку Both в состояние On (Используется).
Нажмите ENTER, затем распахните окно профиля (клавиша F5).
Рис. 1.6 Временная и количественная статистика. PRIME1.
Вы можете заметить, что время выполнения немного уменьшилось (отчасти это произошло за счет того, что PRIME1 выдает на экран меньше информации чем PRIME0). Самым узким местом программы попрежнему остается оператор printf (теперь находящийся в строке 21) (в PRIME1PA ему соответствует оператор Writeln в строке 24.)
Отметим, что строка, в которой непосредственно проверяется является ли очередное число простым (строка 9 в PRIME0, строка 12 в PRIME0PA), теперь выполняется 78 022 раза вместо 15 122. На первый взгляд, этот факт выглядит впечатляюще, но нужно учесть, что в результате, общее время, затрачиваемое на выполнение данной строки, увеличится всего лишь примерно на 1 секунду, так как, в соответствии с ранее полученными данными, эта строка работает очень эффективно с точки зрения использования времени.
Если принять во внимание, что цикл проверки числа выделен теперь в отдельную подпрограмму, то одним из очевидных путей повышения эффективности ее работы является сокращение вызовов данной подпрограммы. Существует несколько путей сокращения количества целых чисел, передаваемых данной подпрограмме для проверки.
Чем больше чисел будет отсеяно на уровне основной программы, тем меньшее количество раз будет вызываться данная подпрограмма и тем быстрее будет выполняться вся программа в целом. В следующих нескольких примерах мы продемонстрируем как на практике применяется вышеизложенная стратегия.
Модификация программы и повторное профилирование.
Бентли отмечает, что вместо проверки всех множителей из интервала от 1 до n в операторе деления по модулю, достаточно ограничиться лишь числами, не превосходящими корня квадратного из рассматриваемого числа. Это и реализовано нами в программе PRIME2 (PRIME2PA).
Загрузка программы PRIME2.
Итак, продолжим наши упражнения. Для начала загрузим в окно Module (Модуль) программу PRIME2, следующую версию нашей программы. В программе PRIME2 мы добавили использование подпрограммы root (Root), библиотечной подпрограммы вычисления квадратного корня, возвращающей в качестве результата целое число.
Информация для пользователей Паскаля: Загрузите в окно программы PRIME1PA.
Вам необходимо пометить каждую строку программы как «область». Вызовите локальное меню и выберите в нем команду Add Areas| Every Line in Module (Добавить «области»| Каждая строка в модуле), затем нажмите ENTER.
Нажмите F9 для начала профилирования. На экране пользователя опять появятся все простые числа, находящиеся в диапазоне от 1 до 1000.
Когда программа закончит свою работу, откройте блок диалога Display Options (Параметры изображения) (для этого выберите команду Display (Изображение) из локального меню окна Execution Profile (Профиль выполнения)) и установите параметр Display в состояние Both («И то, и другое»). Нажмите ОК. Несмотря на уменьшение количества обращений к строке 15 (c 78022 до 5288) и соответственно сокращения общего времени, затрачиваемого на выполнение данной строки, полное время выполнения данной программы значительно возросло.
Объяснение данной особенности программы PRIME2 кроется в использовании новой подпрограммы root. Строка 7 нашей программы выполняется 5465 раз, и это занимает почти 5 секунд. На один вызов подпрограммы затрачивается приблизительно 1 милисекунда, следовательно частое обращение к этой подпрограмме является расточительным (в PRIME2PA соответствующая строка имеет номер 9.)
Если в окне Execution Profile (Профиль выполнения) временная и количественная статистика показываются одновременно, то некоторые сочетания этих данных заслуживают внимания. Для неэффективных подпрограмм вторая строка гистограммы (временные данные) гораздо длиннее, чем первая (количественные данные), это означает, что отношение времени выполнения к количеству вызовов велико. Именно такая ситуация наблюдается в строке 27, оператор printf (в Паскалевской программе это строка 28).
В том случае, если для какой-то подпрограммы отношение общего времени ее выполнения к количеству ее вызовов велико, то самое лучшее из того, что можно предпринять — это попытаться заменить ее на другую подпрограмму.
Рассматривая оператор return в подпрограмме root (строка 7), мы попадаем в другую ситуацию. Этот оператор характеризуется самым большим числом обращений и самым большим общим временем выполнения. К двум другим строкам (строке 5 и строке 8) обращение происходит 5456 раз, но гистограммы для каждой из этих строк показывают маленькие затраты времени на их выполнение. Такое сочетание нас вполне устраивает, оно означает, что данные операторы работают быстро. Итак, самой большой проблемой на настоящий момент является количество вызовов подпрограммы root.
Сокращение количества вызовов подпрограммы (PRIME3).
Теперь наша основная задача — это сокращение количества вызовов подпрограммы root. Загрузите PRIME3 в окно Module (Модуль), затем распахните это окно и посмотрите на исходный текст нашего примера.
Информация для пользователей Паскаля: Вам следует загрузить в окно Module (Модуль) пример PRIME3PA.
Единственная модификация, имеющаяся в PRIME3, содержится в подпрограмме prime. Мы добавили новую целочисленную переменную limit и, перед началом работы цикла for, присвоили ей значение, равное root(n). Переменная limit — это верхняя граница для параметра цикла for.
Информация для пользователей Паскаля: В PRIME3PA мы добавили целочисленную переменную Limit и положили ее равной корню квадратному из n перед началом выполнения цикла for. Переменная Limit — это верхняя граница для параметра цикла for.
При помощи локального меню окна Module (Модуль), пометьте «области» на каждой строке программы. Во время данного сеанса профилирования (для того, чтобы запустить программу выберите Run| Run (Выполнение| Выполнение) или нажмите клавишу F9), программа работает немного быстрее. Общее время выполнения программы PRIME3 сократилось почти на 50 %.
Теперь в качестве основного потребителя времени выполнения выступает функция printf. За счет сокращения числа обращений к подпрограмме вычисления квадратного корня (с 5456 до 999) мы значительно уменьшили общее время выполнения программы.
Добавим еще немного эффективности.
У нас осталось еще несколько возможностей для увеличения эффективности подпрограммы prime. Загрузите PRIME4 в окно Module (Модуль), затем просмотрите строки исходного текста с 8 по 17.
Информация для пользователей Паскаля: загрузите PRIME4PA и изучите строки с 11 по 32.
/* Copyright (c) 1990, Borland International */
#include <stdio.h>
prime(int n)
{
int i;
if (n % 2 == 0)
return (n==2);
if (n % 3 == 0)