На этом шаге мы рассмотрим оптимизацию алгоритмов.

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

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

    Во-первых, сложно сформулировать критерий оптимизации, имеющий одновременно и бесспорное практическое значение и однозначно определенный в математическом плане. Например, можно поставить задачу минимизации числа команд машины Тьюринга - критерий, хорошо определенный математически; но совсем неясно его практическое значение, поскольку вряд ли реальная программа на реальном компьютере будет моделировать машину Тьюринга. Можно поставить задачу минимизации времени выполнения программы на реальной машине - ясный с практической точки зрения критерий. Однако невозможно будет решить задачу оптимизации математическими методами, так как время выполнения зависит (иногда значительно) от архитектуры ЭВМ, а архитектуру современных компьютеров не опишешь небольшим числом параметров. Важно также, что программа, работающая быстрее других на одном компьютере, может оказаться не самой быстрой на другом. Существуют даже специальные программы с общим названием benchmark, предназначенные для оценки архитектур.

    Во-вторых, не совсем ясно, что такое сложность задачи. Ее можно было бы определить как минимальную из сложностей алгоритмов, решающих эту задачу. Но существует ли алгоритм минимальной сложности (как убедиться, что найденный алгоритм действительно минимальный или, напротив, не минимальный)? Есть ли к чему стремиться? И насколько труден поиск этого минимума? Эти вопросы связаны с нижней оценкой сложности алгоритмов (а не верхней, как в предыдущих шагах).

    Можно ли для рассматриваемой задачи доказать, что никакой решающий ее алгоритм не может быть проще этой нижней оценки? Возьмем уже решавшуюся задачу перемножения квадратных матриц. Приведен алгоритм сложности Тα(n) = 3n³ + n². Вероятно это не лучший алгоритм, но какова оценка снизу? Результирующая матрица имеет n² элементов. Для вычисления любого элемента нужна хотя бы одна операция однопроцессорной машины - два элемента за одну операцию найти нельзя. Таким образом, для минимального алгоритма мы получаем неравенства

n² <= Tα, min(n) <= 3n³+n²

    Вряд ли n² - хорошая нижняя оценка, но уже известно, что n³ нижней оценкой не является, так как найдены более быстрые алгоритмы (в частности, алгоритм Штрассена).

    Имея в виду сказанное, можно отступить от математической традиции и под оптимизацией алгоритмов понимать просто изменение алгоритма или поиск нового с меньшей сложностью.

    Существует несколько самостоятельных аспектов оптимизации программ, из которых выделим два:

• оптимизация, связанная с выбором метода построения алгоритма;
• оптимизация, связанная с выбором методов представления данных в программе.

    Первый вид оптимизации имеет глобальный характер и (при удачной оптимизации) ведет к уменьшению порядка функции сложности - например, замена алгоритма с Тα(V) = O(F^S) на алгоритм с Tα(V) = O(V⁴). Он зависит от того, как задача разбивается на подзадачи, насколько это разбиение свойственно самой задаче или является только искусственным приемом.

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

  Формула, задающая желаемую сложность -> 
  Соответствующее уравнение (одно из возможных) -> 
  Метод разбиения задачи на подзадачи.

    Второй вид оптимизации, не меняя структуры программы в целом, ведет к экономии памяти и/или упрощению работы со структурами данных, повышению эффективности вспомогательных процедур, обеспечивающих "интерфейс" между прикладным уровнем (на котором мыслим в терминах высокоуровневых объектов - графов, матриц, текстов и т. д.) и машинным уровнем, поддерживающим простейшие типы данных (числа, символы, указатели). Результатом этого обычно является уменьшение коэффициентов при некоторых слагаемых в функции сложности (при удачной оптимизации - при наиболее значимом слагаемом), но порядок функции сложности остается тем же.

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

    На следующем шаге мы рассмотрим рекурсивный алгоритм умножения матриц.

Предыдущий шаг Содержание Следующий шаг