Портал:ЕГЭ и ОГЭ/Информатика/ЕГЭ/Программирование. Оптимизация по времени и памяти

Материалы

Поможем подготовиться к ЕГЭ/ОГЭ

Проведена экспертиза
Российской Академией Наук

Программирование. Оптимизация по времени и памяти

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

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

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

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

Значимость выбора эффективных алгоритмов

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

Оценка сложности алгоритмов

Оценка сложности алгоритмов — это первый шаг на пути правильному выбору. Необходимо определить их временную сложность, демонстрирующую, как быстро выполняется алгоритм в зависимости от объема входных данных, и пространственную сложность, определяющую объём памяти, необходимый для выполнения алгоритма. Выражая временную сложность как «O(f(n))» и пространственную как «O(g(n))», программисты могут сравнивать различные алгоритмы и выбирать оптимальные решения.

Оптимизатор

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

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

Оптимизация пространства памяти

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

Управление памятью: Эффективное управление памятью, такое как использование умных указателей в языках программирования C++ или автоматическое управление памятью в языках высокого уровня, снижает риск утечек памяти и оптимизирует использование ресурсов.

Простейшие приёмы оптимизации программ по затратам процессорного времени

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

Инициализация объектов данных

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

Оптимизация выполнения арифметических операций

В том случае, когда значительная часть времени работы программы отводится арифметическим вычислениям, немалые резервы повышения скорости работы программы таятся в правильном программировании арифметических (и логических) выражений. Важно, что различные арифметические операции значительно различаются по быстродействию. В большинстве архитектур, самыми быстрыми являются операции сложения и вычитания. Более медленным является умножение, затем идёт деление. Например, вычисление значения выражения ${\frac {x}{a}}$, где $a$ — константа, для аргументов с плавающей точкой производится быстрее в виде $x\cdot b$, где $b={\frac {1}{a}}$ — константа, вычисляемая на этапе компиляции программы (фактически медленная операция деления заменяется быстрой операцией умножения). Для целочисленного аргумента $x$ вычисление выражения $2x$ быстрее произвести в виде $x+x$ (операция умножения заменяется операцией сложения) или с использованием операции сдвига влево (что обеспечивает выигрыш не на всех процессорах). Подобные оптимизации называются понижением силы операций.

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

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

Пример. Пусть необходимо вычислить многочлен 4-й степени:

$ax^{4}+bx^{3}+cx^{2}+dx+e$

При условии, что вычисление степени производится перемножением основания определенное число раз, нетрудно найти, что в этом выражении содержится 10 умножений («медленных» операций) и 4 сложения («быстрых» операций). Это же самое выражение можно записать в виде:

$(((ax+b)x+c)x+d)x+e$

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

Подобные оптимизации являются алгоритмическими и обычно не выполняются компилятором автоматически.

Литература

Крис Касперски. Техника оптимизации программ. Эффективное использование памяти. — СПб.: БХВ-Петербург, 2003. — 464 с. — ISBN 5-94157-232-8.