Распределение памяти

Генерация кода.

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

Оптимизация программы — это исключение лишних операций.

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

В качестве составляющей критерия эффективности обычно берутся два показателя: объем памяти для задачи и скорость выполнения программы (быстродействие).

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

Оптимизация может выполняться для следующих типовых синтаксических конструкций:

1. Последовательность операций с одним входом и одним выходом.

Исключение лишних операций и перестановка операций.

2. Логические выражения. Отсутствие избыточных маршрутов.

3. Циклы.

4. Вызовы процедур — функций. Оптимизация передачи параметров.

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

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

Чтобы оценить сложность алгоритма, нужно:

1. Выделить циклы.

Если их нет, то, как правило, число элементарных операций не зависит от размерности задачи. Сложность постоянна: T(1).

Циклическая структура алгоритма приводит к повторению выполнения его частей, что влияет на общее число шагов (т. е. на сложность).

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

2. Оценить сложности.

Если цикл Б с числом повторений n(Б) вложен в цикл А с числом повторений n(А) и циклы независимы, т. е. число повторений цикла Б не зависит от цикла А, то общее число повторений цикла Б с учетом повторений цикла А составляет n(А)*n(Б). Для независимых циклов сложности перемножаются.

Если циклы не являются вложенными, то сложность определяется максимумом из сложностей цикла: T(n) = max(n(А), n(Б)).

§3. Рекурсия

Рекурсия — процедура, которая прямо или косвенно обращается к самой себе.

Рекурсивное программирование базируется на разбиении задач на подзадачи меньшей размерности.

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

1. Рекурсивное (обычное) разделение.

Предполагается разделение на задачи различной природы.

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

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

Независимость полученных подзадач подразумевает соответствующее разделение исходных данных задачи на непересекающиеся подмножества. Эффективность и сложность таких алгоритмов зависит от затрат на само разделение, а также от пропорций разделяемых частей: лучшему случаю соответствует деление на равные части (логарифмическая зависимость), а худшему — выделение единственного элемента (линейная зависимость).