Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Так что же такого замечательного в использовании массивов в качестве структуры данных? Во-первых, вычисление адресов элементов выполняется очень быстро. Как уже говорилось, для этого нужно всего лишь умножение и сложение. При получении доступа к элементу N (MyArray [N]) компилятор для вычисления адреса добавляет простой машинный код. Независимо от значения числа N, формула для вычисления адреса будет одной и той же. Другими словами, получение доступа к элементу с индексом N принадлежит к классу операций O(1) и не зависит от величины N.

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

До сих пор мы рассматривали только преимущества массивов, но хотелось бы знать и об их недостатках. Первый недостаток связан с операциями вставки и удаления элементов. Что происходит, если, например, в массив необходимо вставить новый элемент с индексом n? В общем случае, все элементы с индексами, начиная с n и до конца массива, потребуется переместить на одну позицию, чтобы освободить место под новый элемент. А фактически выполняется следующий блок кода:

{сначала освободить место под новый элемент}

for i := LastElement downto N do

MyArray[i+1] := MyArray[i];

{вставить новый элемент в позицию с индексом N}

MyArray[N] := NewElement;

{увеличить значение длины массива на единицу}

inc(LastElementIndex);

(Конечно, на практике цикл заменяется вызовом процедуры Move.)

Рисунок 2.1. Вставка в массив нового элемента

Рисунок 2.2. Удаление элемента из массива

Объем памяти, который будет затронут при вставке нового элемента, зависит от значения n и количества элементов в самом массиве. Чем больше количество элементов, которые необходимо переместить, тем больше времени потребуется на выполнение операции. То есть, время, требуемое на выполнение цикла For, будет пропорционально количеству элементов в массиве. Другими словами, вставка нового элемента в массив принадлежит к классу операций O(n).

Тот же ход рассуждений справедлив и для операции удаления элемента из массива. Но в этом случае удаление элемента с индексом n означает, что элементы, начиная с индекса n + 1 и до конца массива, будут перенесены на одну позицию к началу массива, чтобы "закрыть" образовавшуюся от удаления элемента "дыру". Как и в случае со вставкой, удаление принадлежит к классу операций O(n).

{удалить элемент, переместив следующие за ним элементы на одну позицию вперед}

for i := N+ 1 to LastElementIndex do

MyArray[i-1] := MyArray[i];

{уменьшить значение длины массива на единицу}

dec(LastElementIndex);

(Конечно, на практике цикл заменяется вызовом процедуры Move.)

Таким образом, важно понимать, что операции вставки и удаления элемента при увеличении количества элементов в массиве будут выполняться медленнее, поскольку они принадлежат к классу операций O(n).

Кроме того, есть еще один вопрос, связанный со вставкой и удалением элементов, - необходимо контролировать количество активных элементов, т.е. в качестве последнего элемента массива нужно ввести сигнальный (sentinel) элемент, который будет использоваться в качестве метки конца массива. (В строках с завершающим нулем таким сигнальным элементом является символ #0.) Как правило, во время компиляции объявляются массивы фиксированного размера (сейчас мы говорим о методах увеличения размеров массивов), а, следовательно, для этого нам необходимо знать количество активных элементов. В двух приведенных выше примерах для хранения количества активных элементов использовалась переменная LastElementIndex. В строках и длинных строках, например, в самой строке, содержится счетчик количества символов. Но если мы не планируем использовать вставку или удаление элементов, никаких дополнительных элементов не требуется.

Стоит упомянуть и об еще одной проблеме, которая касается только программирования в Delphi1. В Delphi1 максимальный объем непрерывного выделяемого блока памяти (по крайней мере, без написания дополнительного кода на ассемблере) равен 64 Кб. Если объем одного элемента массива составляет 100 байт, то это означает, что в массиве не может быть больше 655 таких элементов. Не так уж и много. Это 64-Кбное ограничение может вызвать определенные проблемы и привести к тому, что придется использовать указатели на элементы (как, например, в знаменитом классе TList), а не сами элементы (в массиве TList в Delphi1 количество элементов ограничено числом 16 383).

Часто приходится сталкиваться с программированием процедур, которые требуют использования массива, причем количество элементов в таком массиве заранее не известно - их может быть десять, сто или тысяча, но окончательно количество элементов будет известно только во время выполнения процедур. Более того, из-за незнания количества элементов, его трудно объявить как локальную переменную (объявление массива с максимально возможным количеством элементов может привести к перегрузке стека, особенно это касается Delphi1). Таким образом, память под элементы массива лучше выделять из кучи.

Но даже в этом случае не все недостатки устраняются. Предположим, что вы решили, что количество элементов в массиве не может превысить 100. Но никогда не говорите "никогда", поскольку в один прекрасный день количество элементов может оказаться 101. Это приведет к перезаписи памяти или возникновению ошибок нарушения доступа (если, конечно, в коде не использовались утверждения, которые проверяли возможность превышения количества элементов над ожидаемым значением).

Одним из методов, которые уходят корнями еще к временам языка Pascal, является создание типа массива со всего одним элементом и указателя на этот массив:

type

PMyArray : ^TMyArray;

TMyArray : array[0..0] of TMyType;

Теперь, если нам необходим массив типа TMyType, можно легко указать требуемое количество элементов:

var

MyArray : PMyArray;

begin

GetMem(MyArray, 42 * sizeof(TMyType));

... использование массива MyArray...

FreeMem(MyArray, 42*sizeof(TMyType));

Обратите внимание, что процедура FreeMem при освобождении выделенного блока памяти только в Delphi1 требует указания размера блока. Все 32-разрядные версии Delphi и Kylix хранят размер выделенного блока в самом блоке. Размер блока находится непосредственно перед блоком, который код получает с помощью процедуры GetMem. В последних версиях Delphi передаваемый в качестве входного параметра размер блока игнорируется, а вместо него используется скрытое значение.