Предыдущий раздел

Использование динамической памяти

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

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

Но если нам нужен массив вспомогательной информации, то к нему такой подход не годится по двум причинам:
1) массив занял бы неоправданно много места в стеке, объем которого весьма ограничен;
2) когда мы пишем процедуру, мы обычно не знаем, какой длины массив понадобится.

В этом случае вспомогательный массив берется из динамической памяти. Чтобы отличить его от обычного массива, объявленного предложением VAR, его обычно называют динамическим массивом:

GetMem(p, n * 6);

Здесь n – длина массива (размерность вспомогательного вектора), 6 – длина одной переменной типа REAL в байтах (если вспомогательные данные должны иметь другой тип, то это число соответственно заменяется другим). А p – указатель на начало выделенного под вспомогательный массив участка динамической памяти.

Обращение к элементам такого массива, естественно, производится через указатель p. Здесь возможны два подхода, один из которых надо выбрать, приступая к написанию процедуры (функции). Эти подходы были уже рассмотрены в предыдущем разделе, при написании функции norm.

При первом из них выбирается тип указателя p:^REAL (или p:RealPtr), после чего элементом динамического массива является выражение p^. Для того, чтобы это выражение обозначало различные элементы массива, указатель p перемещают по массиву посредством операций инкрементирования Inc и декрементирования Dec. Программисту приходится тщательно следить за тем, чтобы указатель p всегда, когда используется p^, указывал на элемент массива, а не мимо него, причем именно на тот элемент, который нужен.
Повторю еще раз:

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

Этот подход эффективнее и удобнее, если в ходе выполнения процедуры элементы вспомогательного массива (один или несколько раз) просматриваются подряд, один за другим, в порядке возрастания или убывания номера.

При втором подходе вводится тип массива фиктивной длины
TYPE ar=ARRAY[1..1] OF REAL;,
объявляется локальный указатель
VAR p: ^ar;,
после чего p^ – это массив, а p^[i] – его i-тый элемент.

Все предупреждения о соответствии индекса массива его реальному размеру сохраняют силу!

Пример: метод простых итераций

Пусть надо найти n-мерный вектор , удовлетворяющий уравнению

.

(*)

Любую систему из n уравнений с n неизвестными можно переписать в такой форме. В курсе математического анализа доказывается, что при определенных условиях (если F удовлетворяет условию Липшица с константой q < 1) уравнение (*) имеет единственное решение, которое можно получить как предел сходящейся последовательности, определенной рекуррентной зависимостью

– любой начальный вектор,
для .

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

Задача. Написать процедуру, реализующую этот метод.

Решение. Сначала разработаем в общих чертах алгоритм, по которому будет работать процедура. Фактически алгоритм работает с двумя основными объектами: это предыдущий вектор x и следующий вектор y, полученный из предыдущего применением отображения F. Для выполнения следующего шага компоненты вектора x надо заполнить значениями из вектора y.
Кроме них, потребуется использовать еще вектор разности для оценки его нормы. Если норма окажется меньше наперед заданного числа , то вектор y и будет искомым приближенным решением.

Вот набросок алгоритма:

1) Вычисление .

2) Обмен значениями

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

3)

4) Проверка условия . Если оно не выполняется, то продолжить с п. 1), иначе...

5) x – (приближенное) решение задачи. Все.

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

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

Следующий раздел