Система Turbo Profiler фирмы Borland

2. Изменение структуры операторов цикла на более эффективную и рациональную.

Проблема ввода/вывода может быть частично решена за счет сокращения оператора printf с его настоящего вида

printf(«prime #%d=%d\n», lastprime, curprime)

до вида

printf(«%d\n», curprime).

Информация для пользователей Паскаля: Вы можете привести оператор Writeln к виду Writeln(CurPrime);.

Только одно это простое изменение дает значительное уменьшение времени выполнения программы. Однако заметим, что Вы не можете уменьшить количество обращений к оператору вывода (в данном примере на экран каждый раз будет выводиться 168 простых чисел).

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

(Заметим, что данный алгоритм не очень эффективен с точки зрения использования памяти, так как наличие массива требует резервирования памяти, размеры которой должны позволить разместить все найденные простые числа. Из вышеизложенного следует ограничение на количество простых чисел, которые могут быть найдены данной программой, поскольку при некотором их количестве неизбежно произойдет переполнение оперативной памяти.)

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

Модульная программа поиска простых чисел (PRIME1).

Завершим рассмотрение PRIME0 и загрузим в окно Module (Модуль) программу PRIME1, следующий вариант программы поиска простых чисел. Начнем изучение этой программы с простого просмотра ее текста.

1. Выберите команду File|Open (Файл|Открыть).

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.)