21. Оптимизация: цель, критерии, требования, методика, средства.

Оптимизация программ не стремится к поиску оптимального варианта, т.е. варианта, который нельзя улучшить. Оптимизация программ – процесс улучшения программы в смысле некоторых критериев.

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

Основными критериями при оптимизации программ являются:

• Скорость работы

• Объем используемой памяти

• Объем места, занимаемого на диске

Если программа работает медленно:

• ее не удастся применить на практике (пример: Прогноз погоды на завтра нужен сегодня, а не через неделю)

• с ней откажутся работать потенциальные пользователи (пример: Обработка фотографий – слишком большое время ожидания, и у нас не купят наш графический редактор)

Если программа требует много памяти (ОЗУ):

• с ней откажутся работать потенциальные пользователи (пример: Задача о поиске оптимального маршрута между городами – при хранении разреженной матрицы в полном варианте огромный объем требуемой памяти приведет к активному использованию файла подкачки Windows – крайне медленная работа)

Если программа требует много места на жестком диске:

• ее могут отказаться приобретать потенциальные пользователи

(пример: вспомним наше недовольство при установке программ с 5 компакт-дисков, а также разговоры о том, что каждый новый Windows занимает в 3 раза больше места, чем старый).

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

Требования:

• Переносимость

• Небольшая трудоемкость

• Значимый выигрыш

• Понятность программы

• Возможность развития

Прежде чем оптимизировать программу, убеждаемся в ее работоспособности. Основной прирост производительности приходит от алгоритмической оптимизации, а не от «трюков» (ищем эффективные алгоритмы). Оптимизация кода ≠ Ассемблерная реализация (улучшаем код для увеличения быстродействия в рамках ЯПВУ). Перед переписыванием на Ассемблер изучаем ассемблерный листинг после работы компилятора (знаем ли мы, как сделать лучше?). Если все вышеперечисленное не помогло и мы знаем как улучшить ассемблерный код, только тогда переходим на Ассемблер.

Средства оптимизации:

• Оптимизирующий компилятор.

• Средства профилировки.

• Оптимизирующие библиотеки.

Главное средство: голова программиста, снабженная знаниями основ программирования, теории алгоритмов, архитектуры ЭВМ.

22. Алгоритмическая оптимизация: временная сложность, сравнение алгоритмов, примеры.

Алгоритмическая оптимизация – выбор хорошего в некотором смысле алгоритма для конкретной задачи. Принципиальный момент: алгоритмическая оптимизация дает наибольший прирост производительности по сравнению с другими вариантами (к примеру, программной). Никакая оптимизация под современные архитектуры не позволит исправить ошибок, допущенных при выборе подходящего алгоритма.

Как это делать?

• Анализируем задачу.

• Ищем (литература, Интернет, изобретаем сами) алгоритмы ее решения.

• Сравниваем эти алгоритмы по тем критериями, которые для нас имеют смысл.

• Выбираем лучший алгоритм.

• Думаем, нельзя ли улучшить и его.

Сравнение алгоритмов – теория сложности. Теория сложности игнорирует константы. Для получения реальной картины и выбора путей дальнейшей (не алгоритмической) оптимизации необходимо оценить полученную реализацию.

Задача: Дано прямоугольное поле размера m x n. В каждой ячейке лежит определенное кол-во денег. Буратино начинает свой путь в ячейке (1, 1) и за 1 шаг способен двигаться на 1 клетку вправо, либо на 1 клетку вниз. Требуется найти наибольшее кол-во денег, которое может собрать Буратино на пути из (1, 1) в (m, n) и соответствующий путь.

Алгоритм 1. Полный перебор всех путей.

Перебор:

• сгенерировать все пути;

• для каждого найти сумму денег;

• из сумм найти максимум.

1-я разумная модификация: сгенерировав путь, сразу считать сумму и сравнивать с максимумом.