Статьи Королевства Дельфи

         

Продолжение


Раздел Поземелье Магов
Оглавление.
  1. Динамические массивы.
  2. Заключение.

§4 Динамические массивы.

ДМ удобнее в использовании и во многом заменяют списки. Однако, ситуация, когда заранее не известно, сколько оперативной памяти надо выделять под объект, которым является ДМ, не обрабатывается. В этом случае, как и раньше, требуется дополнительное программирование. Одна из возможных стратегий - периодическая проверка не выхода индекса массива за границу установленного диапазона и перераспределение памяти в случае выхода. Причём, существует несколько способов перераспределения: увеличивать ДМ поэлементно; на фиксированное количество элементов; на переменное, в зависимости от ситуации, количество элементов. Недостатком данного подхода являются дополнительные операции проверки выхода индекса за границу диапазона и перераспределение (выделение и освобождение памяти). Особенно это будет ощущаться в случае, когда трудно сделать априорные предположения о возможных границах массивов. Тактика программирования для реализации идей может быть аналогична тактике построения динамических списков, рассмотренных выше. В этом месте необходимо отметить, что ДМ не является классом в традиционном смысле. И другие типы данных, например integer, не являются классами в Pascal-я подобных языках. Как представляется, это существенно облегчило бы программирование, к которому мы сейчас переходим. Представим вариант класса расширяющего возможности ДМ.

TS = array of TObject; // Массив объектов TGigaArray = class // (5*) protected FGArray: TS; FSizeBlockTS:TCount; FMaxArray: TCount; procedure SetElGigaArray(Index: integer; A: TObject); function GetElGigaArray(Index: integer): TObject; function ReplaceArray(var C1: TCount): boolean; virtual; destructor Destroy; virtual; public constructor Create(ExtentSizeArray: integer); property Element[Index: integer]:Tobject read GetElGigaArray write SetElGigaArray;default; end; Методы класса реализуют возможность увеличения количества элементов массива произвольных объектов (классов) на фиксированную величину, задающуюся в конструкторе.

constructor TGigaArray.Create(ExtentSizeArray: integer); begin FSizeBlockTS:= ExtentSizeArray; FMaxArray := ExtentSizeArray; SetLength(FGArray, FMaxArray); end; destructor TGigaArray.Destroy; begin FGArray := NIL; inherited Destroy; end; procedure TGigaArray.SetElGigaArray(Index: integer; A: TObject); var C: TCount; begin C := Index; ReplaceArray(C); FGArray[Index] := A; end; function TGigaArray.GetElGigaArray(Index: integer): TObject; var i: integer; C1: TCount; begin if Index <= FMaxArray then Result := FGArray[Index] else begin C1 := Index; ReplaceArray(C1); for i:=FmaxArray-FSizeBlockTS to FMaxArray do FGArray[i] := nil; Result := FGArray[Index]; end; end; function TGigaArray.ReplaceArray(var C1: TCount): boolean; var WGArray: TS; i: integer; begin Result := True; if C1 > FMaxArray then begin FMaxArray := 0; Dec(C1); SetLength(WGArray, C1); for i:=0 to C1-1 do begin WGArray[i] := FGArray[i]; Inc(FMaxArray); end; FGArray := NIL; C1:= 0; Inc(FMaxArray, FSizeBlockTS); SetLength(FGArray, FMaxArray); Dec(FMaxArray, FSizeBlockTS); for i:=0 to FMaxArray-1 do begin FGArray[i] := WGArray[i]; Inc(C1); end; Inc(FMaxArray, FSizeBlockTS); Inc(C1); WGArray := nil; Result := False; end; end; В данном классе не производится проверки типов, как в классе TDataListС. Метод ReplaceArray, реализующий расширение массива, вызывается как при чтении (GetElGigaArray), так и при записи (SetElGigaArray) в массив. Возможно, это не всегда нужно, тогда эти методы надо сделать виртуальными. Применение класса TGigaArray требует некоторых накладных расходов по сравнению с чистым ДМ. Для создания объекта класса надо применять метод Сreate, а не функцию SetLength. Для освобождения ресурсов необходимо применять метод Free, а не присваивать nil. Самое не приятное - элемент массива только объект (класс), что требует определенную технику программирования. Например, такую:

... TS = class // описание типа элемента динамического массива I: integer; end; ... M: TGigaArray; // описание экземпляра класса ДМ (объекта) S: TS; // описание экземпляра элемента ДМ ... M:=TGigaArray.Create("первичное число элементов"); // создание ДМ ... S:=TS.Create; // создание текущего элемента ДМ S.I:="какое-то значение"; // присвоение ему значения M[i]:=S; // запись объекта в ДМ ... write(TS(M[i]).I); // обращение к массиву с приведением типов ... M.Free; // освобождение ОП, занятой ДМ Можно избавиться от приведения типов и создания экземпляров элементов ДМ, отказавшись от типа TObject в качестве типа элемента. Создавать классы по аналогии с TGigaArray, подставляя нужные типы элементов в описание класса, например TGigaArrayInteger, TGigaArrayWord или TGigaArrayReal. В [2] для динамических таблиц, которыми могут быть стек, куча, хеш-таблица или просто массив, рекомендуется увеличивать таблицу в момент переполнения вдвое (ссылаются на опыт). Такой способ управления оперативной памятью предполагает наличие процедуры для вставки нового элемента в ДМ. Сложнее производить перераспределение памяти при удалении ненужных элементов. В том же источнике [2] предлагается, как только число элементов падает ниже некоторого предела, выделять память под новый ДМ меньшего размера, копировать в меньший ДМ все элементы из большего ДМ, после чего возвращаем ОС ресурсы, старого ДМ. Только сокращение памяти рекомендуется предпринимать тогда, когда коэффициент заполнения ДМ (отношение числа заполненных элементов к размеру массива) падает ниже . Стратегия удаления также нуждается в дополнительной процедуре, которая (в случае с ДМ) не только проверяет коэффициент заполнения, но и переписывает "хвосты" в случае удаления элемента из середины массива. Всё вышесказанное можно проиллюстрировать следующим кодом.

TS = array of integer; // Массив целых чисел TGiga2Array = class // (6*) protected FGArray: TS; FCount: integer; // количество элементов FSize: integer; // размер массива procedure Put(Index: integer; A: integer); function Get(Index: integer): integer; function GetCount: integer; destructor Destroy; virtual; public constructor Create; procedure Add(X: integer); procedure Delete(I: integer); property Element[Index: integer]: integer read Get write Put; default; property Count: integer read GetCount; end; constructor TGiga2Array.Create; begin FSize := 1; FCount := 0; SetLength(FGArray, FSize); end; destructor TGiga2Array.Destroy; begin FGArray := NIL; inherited Destroy; end; procedure TGiga2Array.Put(Index: integer; A: integer); begin FGArray[Index] := A; end; function TGiga2Array.Get(Index: integer): integer; begin if Index <= FSize then Result := FGArray[Index] else Result := -1; // ошибочная ситуация end; function TGiga2Array.GetCount: integer; begin Result:= Length(FGArray); end; procedure TGiga2Array.Add(X: integer); var NFGArray: TS; i: integer; begin if FCount = FSize then begin SetLength(NFGArray, 2*FSize); // ОП вдвое больше для времянки for i:=Low(FGArray) to High(FGArray) do NFGArray[i]:=FGArray[i]; // копируем старые значения FGArray := nil; // освободить старую ОП SetLength(FGArray, 2*FSize); // ОП вдвое больше for i:=Low(NFGArray) to High(NFGArray) do FGArray[i]:=NFGArray[i]; //копируем в новый массив NFGArray := nil; // освободить времянку FSize := 2*FSize; end; FGArray[FCount]:= X; // добавить в конец массива FCount := FCount + 1; end; procedure TGiga2Array.Delete(I: integer); var NFGArray: TS; j: integer; begin if FSize < (4*FCount) then begin SetLength(NFGArray, FSize div 2); // ОП вдвое меньше для времянки for i:=Low(FGArray) to I-1 do // копируем старые значения NFGArray[i]:=FGArray[i]; for j:=I+1 to High(FGArray) do // пропуская удалённый NFGArray[j]:=FGArray[j]; FGArray := nil; // освободить старую ОП SetLength(FGArray, FSize div 2); // ОП вдвое меньше for j:=Low(NFGArray) to High(NFGArray) do FGArray[j]:=NFGArray[j]; // копируем в новый массив NFGArray := nil; // освободить времянку FSize := FSize div 2; end; FCount := FCount - 1; end; Наверняка, предлагаемый код не является самым оптимальным с точки зрения поставленной задачи. Можно определить в классе два поля типа FGArray и писать-читать данные попеременно то в одно то в другое поля, что даст возможность в методах Add и Delete избавиться от двойного копирования данных. М.б. метод Delete для классов такого типа вообще не имеет смысла. Не проводилось никаких исследований по подбору пороговых коэффициентов и т. п. Однако, сама идея управления оперативной памятью применима. В поддиректории "Массивы" можно найти разложенные по поддиректориям исходные тексты с проектами, иллюстрирующими вышеописанный механизм хранения данных.

§5 Заключение.

Руководствуясь опытом, приобретенным от рассмотренных программ, попытаемся сформулировать требования к представлению и способу хранения данных:



    Содержание  Назад  Вперед