Оптимизация (вычислительная техника)

Это статья об оптимизации программ и данных на всех этапах программирования.

Об оптимизациях, применяемых компиляторами, см.: Оптимизация компилятора.

В информатике оптимизацией называется процесс модификации системы для улучшения её эффективности. Система может быть одиночной компьютерной программой, набором компьютеров или даже целой сетью, такой как Internet.

Несмотря на то, что слово «оптимизация» использует тот же самый корень, что и слово «оптимальный», процесс оптимизации весьма редко порождает оптимальную систему, поэтому всегда имеются уступки (tradeoffs).

Оптимизация должна проводиться с осторожностью. Тони Хоар впервые произнёс, а Дональд Кнут впоследствии часто повторял известное высказывание: «Преждевременная оптимизация — это корень всех бед». Очень важно иметь для начала озвученный алгоритм и работающий прототип.

Основы

Некоторые задачи часто могут быть выполнены более эффективно. Например, рассмотрим следующую программу на языке Си, которая суммирует все целые числа от 1 до N:

int i, sum = 0;
for (i = 1; i <= N; i++)
  sum += i;
printf ("sum: %d\n", sum);

Этот код может быть (подразумевая, что нет переполнения) переписан, используя математическую формулу, в следующем виде:

int sum = (N * (N+1)) / 2;
printf ("sum: %d\n", sum);

Термин «оптимизация» обычно подразумевает, что система сохраняет ту же самую функциональность. Однако, значительное улучшение производительности часто может быть достигнуто с помощью решения насущной проблемы и удаления избыточной функциональности. Например, если обоснованно допустить, что программе не требуется поддерживать более, чем (скажем) 100 элементов при вводе, то возможно использовать статическое выделение памяти вместо медленного динамического.

Уступки (tradeoffs)

Оптимизация в основном фокусируется на одиночном или повторном времени выполнения, использовании памяти, дискового пространства, пропускной способности или некотором другом ресурсе. Это обычно требует уступок — один параметр оптимизируется за счёт других. Например, увеличение размера кэша улучшает производительность времени выполнения, но также увеличивает потребление памяти. Другие распространённые уступки включают прозрачность кода и его выразительность. Сложные специализированные алгоритмы требуют больше усилий по отладке и увеличивают вероятность ошибок.

Различные области

В исследовании операций, оптимизация — это проблема определения входных значений функции, при которых она имеет максимальное или минимальное значение. Иногда на эти значения накладываются ограничения, такая задача известна как ограниченная оптимизация.

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

Типичные проблемы имеют настолько большое количество возможностей, что программисты обычно могут позволить использовать только «достаточно хорошее» решение.

Узкие места

Для оптимизации требуется найти узкое место: критическую часть кода, которая является основным потребителем необходимого ресурса. Улучшение примерно 20 % кода влечёт за собой изменение 80 % результатов (см. также принцип Парето).

Архитектурный дизайн системы особенно сильно влияет на её производительность. Выбор алгоритма влияет на эффективность больше, чем любой другой элемент дизайна. Более сложные алгоритмы и структуры данные могут хорошо оперировать с большим количеством элементов, в то время как простые алгоритмы подходят для небольших объёмов данных — накладные расходы на инициализацию более сложного алгоритма могут перевесить выгоду от его использования.

Чем больше памяти использует программа, тем быстрее она обычно выполняется. Например, программа-фильтр обычно читает каждую строку, фильтрует и выводит эту строку непосредственно. Поэтому она использует память только для хранения одной строки, но её производительность обычно очень плохая. Производительность может быть значительно улучшена чтением целого файла и записью потом отфильтрованного результата, однако этот метод использует больше памяти. Кэширование результата также эффективно, однако требует большего количества памяти для использования.

См. также

• Оптимизация в Java
• Оптимизация в C++
• Абстрактная интерпретация
• Метрика хорошести
• Кэширование
• Принцип KISS
• Граф передачи управления
• Ленивые вычисления
• Низкоуровневая виртуальная машина
• Мемоизация
• Окрестность памяти
• Профилирование (анализ производительности)
• Теория очередей
• Симулятор
• Гипотетическое исполнение
• Время выполнения наихудшего случая

Ссылки

• Programming Optimization
• C,C++ optimization
• C optimization tutorial
• Software Optimization at Link-time And Run-time
• Profiling and optimizing Ruby code
• Article «A Plea for Lean Software» by Niklaus Wirth
• Description from the Portland Pattern Repository
• Улучшаем производительность приложения путем перераспределения кода (рус.)
• ПОИСК ГЛОБАЛЬНОГО ОПТИМУМА
• Оптимизация 64-битных программ (рус.)

Литература

• Jon Bentley. Writing Efficient Programs. ISBN 0-13-970251-2
• Дональд Кнут. Основные алгоритмы // Искусство программирования = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: Вильямс, 2006. — Т. 1. — 720 с. — ISBN 0-201-89683-4
• Дональд Кнут. Получисленные методы // Искусство программирования = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. — 832 с. — ISBN 0-201-89684-2
• Дональд Кнут. Сортировка и поиск // Искусство программирования = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: Вильямс, 2007. — Т. 3. — 824 с. — ISBN 0-201-89685-0