Программирование алгоритмов, требующих больших объемов оперативной памяти

Юрий Зачесов

Что мы можем описать?
Увы! Это всегда лишь то, что начинает увядать и портиться.
Ницше. По ту сторону добра и зла

Идея написания предлагаемой вашему вниманию статьи навеяна многократным штудированием книги Д.Кнута «Искусство программирования для ЭВМ» [1] и личным опытом автора, приобретенным при разработке и программировании алгоритмов, требующих большого объема оперативной памяти. Описанные в указанной книге методы выделения «наиболее подходящего», «первого подходящего» и «системы близнецов», а также методы освобождения памяти в настоящее время относятся к задачам, возлагаемым скорее на операционные системы, чем на средства разработки приложений, что отмечено Д. Кнутом в конце главы 2.5. Причина этого заключается в том, что сейчас большинство операционных систем снабжены подсистемой управления памятью, которая эффективно предоставляет оперативную память как один из ресурсов. В то же время у автора были проблемы с использованием 256 Мбайт оперативной памяти до появления операционной системы Windows 95 (в эпоху DOS и Windows 3.11), а также при организации эффективного использования в одной из задач 1 Гбайт памяти уже во времена Windows 95/98/NT/2000. Это и послужило причиной написания данной статьи, посвященной программированию работы с оперативной памятью.

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

Если x₀, x₁,…x_n-1, x_n (где x_iО{0,1}) — адрес идентификатора в приложении, то максимально возможный адрес, доступный данному приложению, — 2ⁿ⁺¹. Для 16-разрядных приложений (n = 15) это число составляет 65 536, для 32-разрядных — 4 294 967 296 (»  4 Гбайт), для 64-разрядных — 1,844674407371*10⁺¹⁹. Обычно на эти ограничения в адресации накладываются дополнительные ограничения, присущие операционой системе и средству разработки. Например, в Windows 95/98/NT/2000 реальный размер максимальной адресации меньше теоретически возможного, так как часть доступной памяти забирает для своих нужд сама операционная система. К тому же средства разработки позволяют создавать приложения, как правило, с фиксированной разрядностью в смысле адресации.

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

Таблица 1

Ясно, что закономерность здесь более или менее очевидна.

Во времена, когда 640 Кбайт conventional memory (обычная память, которую нередко также называют основной памятью — ввиду двоякой возможности перевода слова conventional) были пределом доступной для программистов ОП, приходилось бороться за десятки «лишних» килобайт, придумывая драйверы, позволяющие выйти за пределы возможностей 16-разрядных приложений и ограничений операционной системы. Например, были популярны стандарты EMS (expanded memory), которая продавалась на отдельной плате со своим процессором, и XMS (extended memory), которая была организована так же, как и основная память. В настоящий момент интерес к таким драйверам снизился вследствие появления процессоров, операционных систем и средств разработки с большей разрядностью, но для иллюстрации идей и методов представляется интересным рассмотреть и этот случай управления памятью. В операционной системе MS-DOS оперативная память распределялась следующим образом:

• 0-640 Kбайт — обычная (conventional) память;
• 640-1024 Kбайт — так называемая старшая (upper) память (UMB);
• 1024-1088 Kбайт — так называемая верхняя (high) память (HMS);
• 1088 Кбайт и выше — дополнительная (extended) память (XMS);
• на отдельной плате — расширенная (expanded) память (EMS).

Предположим, на вашем компьютере имеется 2 Мбайт оперативной памяти. К 640 Кбайт можно адресоваться непосредственно из программы, причем размер одного блока, то есть максимальная длина части оперативной памяти для переменной (или идентификатора массива) не должна превышать 65 519. Операционная система для своих нужд также использовала память из тех же 640 Кбайт. Первоначально (при создании DOS) предполагалось, что максимальный объем требуемой оперативной памяти для любой задачи не может превысить 1 Мбайт. Память от 640 Кбайт до 1 Мбайт (upper memory) была занята чем попало — видеобуфером экрана, областями специально для компьютера PS/2 и т.д. В дальнейшем функциональное назначение ее расширилось — туда стали записывать резидентные программы в целях экономии основной памяти. Теперь представим, что перед нами стоит задача написать систему управления базой данных, размер записи которой — 1 Кбайт, а количество записей может составить несколько тысяч. При этом для быстроты работы приложения все или большая часть записей должны находиться в памяти. Понятно, что без дополнительных ухищрений в DOS такая задача решена быть не может, поскольку здесь нет необходимого для этого ресурса — памяти размером в несколько мегабайт с прямой адресацией. Однако физически такая память есть — надо только обойти ограничение, заложенное в операционной системе, чтобы заставить приложение работать быстрее при выполнении операций чтения и записи в память. Обычно это делается при помощи организации связи между небольшим «окном» оперативной памяти с прямой адресацией, куда можно обратиться с помощью быстрых команд операционной системы, и большим «окном» «верхней» памяти, куда можно обратиться с помощью медленных команд операционной системы, которые все же более быстрые, чем команды чтения/записи на долговременные носители данных. Можно долго рассказывать, как это сделать на уровне команд DOS, а можно воспользоваться библиотекой, реализующей подобные функции (например, Object Professional компании TurboPower Software, http://www.turbopower.com), и обсудить проблему на более высоком уровне. Именно это мы и сделаем.

Для иллюстрации идей, рассматриваемых в данной статье, будут использоваться Borland Pascal 7.0 или Borland Delphi. Надеюсь, что реализация рассматриваемых алгоритмов на других языках программирования не будет вызывать затруднений.

В библиотеке Object Professional (используемой совместно с Borland Pascal 7.0) имеется класс OpArray, наследуемый от класса AbstractArray и позволяющий управлять памятью при помощи больших двухмерных массивов:

OpArray =    object(AbstractArray)
             constructor Init(Rows,    Cols : Word; ElementSize : Word;
                                             FileName : String; HeapToUse : LongInt;
                             ArrayOptions:    Byte; var Priority : AutoPriority);
   ….
   end;

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

 PAsciizStringArray = ^TAsciizStringArray;
   TAsciizStringArray = object(TObject)
         …
       constructor Init(Rows, Cols, Element : Word;
                   FileName:    String; HeapToUse: LongInt);
       procedure InsertQ(var Item: Asciiz);
   …
   end;
   var
      OA: OpArray;
   …
   constructor TAsciizStringArray.Init(Rows, Cols, Element : Word;
   FileName: String; HeapToUse: LongInt);
   const
   ArrayOptions : Word = LDeleteFile + LRangeCheck;
   MyDefaultPriority:AutoPriority=(LXmsArray,LRamArray,LEMSArray,
   LVirtualArray);   {массив может располагаться в ОП с прямой адресацией    (LRamArray), в “верхней” ОП (LXMSArray и LEMSArray) и во временных наборах    данных (LVirtualArray)}
   …
   var
     E: Word;
   begin
   XmsAvailable := TRUE;
   OA.Init(Rows, Cols, Element, FileName, HeapToUse, ArrayOptions,
   MyDefaultPriority);
   Count := 0;
   E := OA.ErrorA;
     if E <> 0 then ErrorM(E, Count);   {обработка ошибок}
     OA.ClearA(ItemDefault, ExactInit);   {предварительная    очистка массива}
     E := OA.ErrorA;
     if E <> 0 then ErrorM(E, Count);  {обработка ошибок}
     …
   end;
   procedure TAsciizStringArray.InsertQ(var Item: Asciiz);
   var
     E:  Word;
   begin
   OA.SetA(count, 0, Item); {метод вставки, наследуемый от AbstractArray}
       E := OA.ErrorA;
       if E <> 0 then ErrorM(E, count);
       Inc(Count);
   end;
   …

Для использования объекта надо описать его и запросить для него ресурс в памяти:

…
PS: PAsciizStringArray;  AS: Asciiz;
…
PS := New(PAsciizStringArray, Init(MaxSize, 1, SizeOf(S), 'kadr.wrk',
                                     MaxAvail div 2 ));
…
PS^.InsertQ(AS);  {вставка новой строки в динамический массив}
…

Попутно отметим, что, кроме того, с помощью класса TAsciizStringArray могут быть решены вопросы отсева дубликатов, поиска, сортировки, а также другие проблемы, выходящие за рамки тематики статьи. Также обратите внимание на размер запрашиваемой памяти с прямой адресацией — параметр HeapToUse, который равен половине размера доступной памяти и, в свою очередь, может быть получен с помощью функции MaxAvail. Во избежание коллизий необходимо предусмотреть, чтобы вашим приложением запрашивалась не вся доступная память, так как явные или неявные запросы на свободную память возможны из других мест вашего приложения либо из приложений, работающих параллельно с вашим. Приложение, фрагменты исходного текста которого приведены выше, будет работать в MS-DOS или в DOS-окне Windows.

Актуальность задачи распределения и перераспределения памяти сохранилась и после появления 32-разрядных операционных систем и средств разработки, позволяющих адресоваться из одного массива данных к памяти размером до 4 Гбайт. Дело в том, что алгоритмы, обходящиеся одним массивом, встречаются редко — как правило, их бывает несколько. В случае если в алгоритме используется память полиномиального размера [2], перед разработчиком встает вопрос о способах организации данных. Прежде чем подавать исходные данные на вход алгоритма, надо договориться о том, как они представляются в «понятном для компьютера виде». До появления в Delphi 4 (выпущенном в 1998 году) динамических массивов, позволяющих резервировать место в ОП по мере необходимости, при программировании на Object Pascal обходились линейными списками. При программировании на Delphi для организации списков можно воспользоваться классом TList из модуля classes. Здесь возможны два варианта:

1. создавать наследника класса Tlist:

     TDataListI = class (TList)        //  (1*)
        protected
          procedure Put(Index: Integer; Item: TData);
          function Get (Index: Integer): TData;
        public
          procedure Add (Obj: TData);
          property Items[Index: Integer]: TData    read    Get write Put; default;
        end;

2. вставлять класс TList в класс-контейнер:

   TDataListW = class(TObject)      //  (2*)
        private
          FList: TList;
          function Get(Index: Integer): TData;
          procedure Put(Index: Integer; Item: TData);
          function GetCount: Integer;
        public
          constructor Create;
          destructor Destroy; override;
          function Add(Item: TData): Integer;
          function Equals(List: TDataListW): Boolean;
          property Count: Integer read GetCount;
          property Items[Index: Integer]: TData read Get write    Put; default;
        end;

Тип элемента TData, как правило, является классом, но в общем случае может быть и любым другим типом данных. Если тип элемента — не класс, то память освободить сложнее, поскольку операции освобождения памяти ложатся не на функцию Destroy, принадлежащую классу, а на дополнительные модули или операторы внутри ваших модулей. Как видно из описания классов, унификация внутри модуля относительно типа элементов (записи, классы и т.п.), из которых состоят списки, существует только для классов, так как только классы «знают», как освобождать память, занятую объектом данного класса. Для реализации корректного освобождения памяти нужно переписать класс TDataListW, например следующим образом:

TDataListС = class          //  (3*)
     private
       LType: TClass;
       FList: TList;
       function Get (Index: Integer): TObject;
       procedure Put (Index: Integer; Item: TObject);
       function GetCount: Integer;
     public
       constructor Create (CType: TClass);
       destructor Destroy; override;
       function Add (Item: TObject): Integer;
       function Equals(List: TDataListС): Boolean;
       property Count: Integer read GetCount;
       property Items [Index: Integer]: TObject  read    Get write Put; default;
     end;

Тексты самих методов здесь не приводятся из-за их тривиальности. В итоге, применяя методы Create и Add, можно создавать списки и добавлять в них новые элементы. Обращаться к элементам списков можно при помощи идентификатора Items или как к обычному элементу массива, поскольку свойство Items определено как default. Кроме того, в Delphi определены классы TClassList и TObjectList (из модуля contnrs), наследуемые от класса TLlist и похожие на класс TDataListС, а также классы TStack, TObjectStack, TQueue, TObjectQueue, наследуемые от TOrderedList и реализующие различные виды линейных списков; класс TCollection (из модуля classes), наследуемый от TPersistent, в котором реализована возможность синхронизации доступа к элементам благодаря методам BeginUpdate, EndUpdate; класс TStrings (из модуля classes), наследуемый от Tpersistent, — абстрактный базовый класс для манипуляции со строками; TStringList (из модуля classes), наследуемый от TStrings и управляющий списками строк и присоединенных к ним объектов с замещенными абстрактными методами из TStrings. Как видите, классы, реализующие списки, довольно многообразны.

Однако при работе со списками могут быть и проблемы. У автора при использовании класса типа TDataListW не освобождалась оперативная память — немного, всего 16 байт, но при интенсивной работе со списками это приводило к нехватке памяти. Поэтому иногда бывает оправдан подход, когда разработчик не использует чужих классов, а все пишет сам. Это несложно. Сначала создается запись, которая будет являться элементом списка.

  PItem_Tree = ^TItem_Tree;
   TItem_Tree = record
       {Рабочая часть записи}
       …
       {-------------------------------------------------}
       {Часть записи для организации списка}
       Next:          PItem_Tree;
   end; 

TRecList = class          //  (4*)
   private
       Head, Last:   PItem_Tree;
       BeforeSet:              PItem_Tree;
       IndexBeforeSet:     integer;
       BeforeGet:                PItem_Tree;
       IndexBeforeGet:    integer;
       FCount:                    integer;
       RetCode:                byte;
       function    GetItem(Index: integer):    TItem_Tree;
       procedure   SetItem(Index: integer; Rec: TItem_Tree);
       function    Empty: boolean;
       function    GetNodeSet(i:integer):    PItem_Tree;
       function    GetNodeGet(i:integer):    PItem_Tree;
   protected
       function    GetCount:  integer;
   public
       constructor Create;
       destructor  Destroy; override;
       procedure   Clear;
       function    Add(Rec: TItem_Tree):    integer; virtual;
       function    AddBegin(Rec: TItem_Tree):    integer; virtual;
       procedure   Assign(var Output: TRecList);
       procedure   Insert(Index: integer; const Rec:    TItem_Tree); virtual;
       procedure   DeleteFromListCheckedFlagItog;
       procedure   CopyRec(const Input: TItem_Tree;    var Output: TItem_Tree);
       property Items[i: integer]:TItem_Tree read GetItem write    SetItem;default;
       property    Count: integer read    GetCount;
   end;   
   
   function TRecList.Empty:boolean;
   begin
       if Head<>nil then
       begin
         RetCode:=Succes;
         if Head^.Next=nil then
           Empty:=TRUE
         else
           Empty:=FALSE
       end
       else
       begin
         RetCode:=NotFill; Empty:=TRUE;
       end;
   end;
   
   procedureTRecList.CopyRec(const Input:TItem_Tree; var Output:TItem_Tree);
   begin
       with OUTPUT do
       begin
       {Присвоение рабочей части записи}
         …
       {Часть записи для организации списка}
         Next:=nil;
       end;
   end;
   
   constructor TRecList.Create;
   begin
       inherited Create;
       Head:=nil;
       Last:=Head;
       Before:=Head;
       IndexBefore:=0;
       BeforeSet:=Head;
       IndexBeforeSet:=0;
       BeforeGet:=Head;
       IndexBeforeGet:=0;
       FCount:=0;
   end;
   
   destructor TRecList.Destroy;
   begin
       Clear;
       inherited Destroy;
   end;
   
   procedure TRecList.Clear;
     var P,P1:PItem_Tree;
     begin
       if Head<>nil then
       begin
         if Empty and (RetCode=Succes) then
         begin Dispose(Head);Head:=nil; RetCode:=Succes;    Exit; end;
         P:=Head;
         while P<>nil do
         begin
           P1:=P^.Next;
           Dispose(P);
           P:=P1;
         end;
         RetCode:=Succes;
         Head   :=nil;
         Last   :=nil;
         Before :=nil;
         IndexBefore:=0;
         BeforeSet :=nil;
         IndexBeforeSet:=0;
         BeforeGet :=nil;
         IndexBeforeGet:=0;
         FCount:=0;
       end
       else
          RetCode:=NotFill;
   end;
   
   function TRecList.GetNodeSet(i:integer): PItem_Tree;
   var
       j: integer;
      P: PItem_Tree;
   begin
       RetCode:=Succes;
       if (i-1=IndexBeforeSet) and
          (BeforeSet <> nil) then
       begin
         P:=BeforeSet^.Next;
         BeforeSet:=P;
         IndexBeforeSet:=i;
         GetNodeSet:=P;
       end
       else
       begin
         P:=Head;
         j:=0;
         while P<>nil do
         begin
           if i=j then break;
           P:=P^.Next;
           Inc(j);
         end;
         BeforeSet:=P;
         IndexBeforeSet:=i;
         GetNodeSet:=P;
       end;
   end;
   
   function TRecList.GetNodeGet(i: integer): PItem_Tree;
   var
       j: integer;
       P: PItem_Tree;
   begin
       RetCode:=Succes;
       if (i-1=IndexBeforeGet) and
          (BeforeGet <> nil) then
       begin
         P:=BeforeGet^.Next;
         BeforeGet:=P;
         IndexBeforeGet:=i;
         GetNodeGet:=P;
       end
       else
       begin
         P:=Head;
         j:=0;
         while P<>nil do
         begin
           if i=j then break;
           P:=P^.Next;
           Inc(j);
         end;
         BeforeGet:=P;
         IndexBeforeGet:=i;
         GetNodeGet:=P;
       end;
   end;
   
   procedure TRecList.SetItem(Index: integer; Rec: TItem_Tree);
   var
       P, P1: PItem_Tree;
   begin
       if Index>FCount then begin RetCode:=ErrIndex;Exit;end;
       P:=GetNodeSet(Index);
       if RetCode=Succes then
       begin
         P1:=P^.Next;
         CopyRec(Rec,  P^);
         P^.Next:=P1;
        end;
   end;
   
   function TRecList.GetItem(Index: integer): TItem_Tree;
   var
       P:PItem_Tree;
   begin
       if Index>FCount then begin RetCode:=ErrIndex;Exit;end;
       P:=GetNodeGet(Index);
       if RetCode=Succes then
         if P<>nil then CopyRec(P^, Result);
   end;
   
   function TRecList.Add(Rec: TItem_Tree): integer;
   begin
       if Head=nil then
       begin
         New(Head);
         if Head<>nil then
         begin
           CopyRec(Rec, Head^);
           Last:=Head;
           FCount:=1;
           Result:=1;
         end
         else
           Result:=-1;
       end
       else
       begin
         New(Last^.Next);
         Last:=Last^.Next;
         CopyRec(Rec, Last^);
         Inc(FCount);
         Result:=FCount;
       end;
   end;
   
   function TRecList.AddBegin(Rec: TItem_Tree): integer;
   var
       P: PItem_Tree;
   begin
       if Head=nil then
       begin
         New(Head);
         if Head<>nil then
         begin
           CopyRec(Rec, Head^);
           Last:=Head;
           FCount:=1;
           Result:=1;
         end
         else
           Result:=-1;
       end
       else
       begin
         New(P);
         P^.Next:=Head;
         Head:=P;
         P:=P^.Next;
         BeforeSet:=Head;
         IndexBeforeSet:=0;
         BeforeGet:=Head;
         IndexBeforeGet:=0;
         CopyRec(Rec, Head^);
         Head^.Next:=P;
         Inc(FCount);
         Result:=FCount;
       end;
   end;
   
   procedure TRecList.Assign(var Output: TRecList);
   begin
       output.Clear;
       output.Head:=Head;
       output.Last:=Last;
       output.BeforeSet:=BeforeSet;
       output.IndexBeforeSet:=IndexBeforeSet;
       output.BeforeGet:=BeforeGet;
       output.IndexBeforeGet:=IndexBeforeGet;
       output.FCount:=FCount;
       inherited Destroy;
   end;
   
   procedure TRecList.Insert(Index: integer; const Rec: TItem_Tree);
   var
       P,P1,P2:PItem_Tree;
       i: integer;
   begin
       New(P);
       Inc(FCount);
       CopyRec(Rec, P^);
       if Head=nil then
         Head:=P
       else
       {Если список не пуст}
       begin
         P1:=Head; P2:=Head;
         i:=0;
         while (P2<>nil) and (i<Index) do
         begin
           P1:=P2;
           P2:=P2^.Next;
           Inc(i)
         end;
         {Пройден весь список-элемент в конец}
         if P2=nil then
           P1^.Next:=P
         else
         begin
           P^.Next:=P2;
           {В начало списка}
           if P2=Head then
             Head:=P
           else
           {Внутрь списка}
             P1^.Next:=P
         end;
       end;
   end;
   
   function TRecList.GetCount: integer;
   begin
       GetCount:=FCount;
   end;
   
   procedure TRecList.DeleteFromListCheckedFlagItog;
   var
       P, P1: PItem_Tree;
   begin
       P:=Head;
       while P<>nil do
         if not P^.FlagItog then
         begin
           {Удаление из начала списка}
           if P=Head then
           begin
             Head:=Head^.Next;
             Dispose(P);
             Dec(FCount);
             P:=Head;
           end
           else
           begin
           {Удаление из середины списка}
             P1^.Next:=P^.Next;
             Dispose(P);
             Dec(FCount);
             P:=P1^.Next;
           end;
         end
         else
         begin
         {Переход на следующий элемент списка}
           P1:=P;
           P:=P^.Next;
         end;
   end;

Метод Empty предназначен для проверки списка на наличие элементов и используется в других методах класса. CopyRec используется для заполнения элементов списка. Методы Create и Destroy применяются для создания и уничтожения списка соответственно. Метод Clear удаляет все элементы из списка. Методы GetNodeSet и GetNodeGet совместно с полями BeforeSet, IndexBeforeSet, BeforeGet, IndexBeforeGet используются как внутренние и обеспечивают простенькую оптимизацию без дополнительных связей, основанную на том, что при чтении и записи элементов подряд достаточно хранить индекс предыдущего элемента для проверки и ссылку на предыдущий элемент для выполнения действий. Этот способ оптимизации для однонаправленного списка оказывается эффективным, естественно, только для больших списков (сотни тысяч элементов). Методы SetItem и GetItem обслуживают доступ к элементам с помощью свойства Items. Добавление элементов в конец, начало и в указанное место списка обслуживается методами Add, AddBegin и Insert. Метод Assign при помощи полей Head (указатель на первый элемент) и Last (указатель на последний элемент) поддерживает копирование из списка в список. DeleteFromListCheckedFlagItog – тоже хитрый метод. Если вы, работая с большим списком, попытаетесь удалять из него элементы по одному, это займет много времени. Однако можно вместо удаления просто пометить какое-то поле в элементе, а затем, просмотрев список, за один раз удалить все помеченные элементы.

Попутно отметим, что в объектах, аналогичных приведенным выше, возможно выполнять сжатие данных (хранить в элементах списка типы данных меньшего размера, чем данные, с которыми производятся какие-то действия). При программировании на Delphi для сжатия узла списка можно воспользоваться классом (объектом) TBits из модуля classes. В случае если поля узла списка имеют тип массива байт, слов и т.п., можно при сохранении структуры в узле списка производить операции сжатия данных, как, например, в функции, приведенной ниже:

function ByteTo2Bit(B: array of Byte; var Bit: TBits): boolean;
   var i, j: integer;
   begin
   ByteTo2Bit:=True;
   Bit:=TBits.Create;
   Bit.Size:=Length(B)*2;
   for i:=Low(B) to High(B) do begin
     j:=(i-Low(B))*2;
     if B[i]=2 then Bit.Bits[j]:=True
     else if B[i]=1 then Bit.Bits[j+1]:=True;
   end;
   end;

А при извлечении данных из узла списка для работы можно использовать функцию Bit2ToByte:

function Bit2ToByte(Bit: TBits; var B: array of Byte): Boolean;
   var i, j: integer;
   begin
   Bit2ToByte:=True;
   if Length(B)*2<Bit.Size then begin
     Bit2ToByte:=False;
     Exit;
   end;
   i:=0;
   while i<Bit.Size do begin
     j:=(i div 2)+Low(B);
     if Bit.Bits[i] then B[j]:=2
     else if Bit.Bits[i+1] then B[j]:=1
          else B[j]:=0;
     inc(i,2);
   end;
   end;   

В табл. 2 представлено время обработки списков различного размера — без сжатия и со сжатием — для классов типа TDataListW. Размер записи до сжатия составлял 3688 байт, после сжатия — 68 байт.

Таблица 2

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

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

Здесь необходимо отметить, что динамический массив не является классом в традиционном смысле. И другие типы данных, например 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);
        propertyElement[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 требует некоторых «накладных расходов» по сравнению с чистым динамическим массивом. Для создания объекта класса надо применять метод Create, а не функцию 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] предлагается, как только число элементов падает ниже некоторого предела, выделять память под новый динамический массив меньшего размера, копировать в меньший динамический массив все элементы из большего динамического массива, после чего высвободить память, занятую старым динамическим массивом. Высвобождение памяти рекомендуется предпринимать, когда коэффициент заполнения динамического массива (отношение числа заполненных элементов к размеру массива) падает ниже 1/4. Стратегия удаления также нуждается в дополнительной процедуре, которая (в случае с динамическим массивом) не только проверяет коэффициент заполнения, но и сдвигает элементы в случае удаления элемента из середины массива. Все вышесказанное можно проиллюстрировать следующим кодом:

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 для классов такого типа вообще не имеет смысла. Не проводилось также никаких исследований по подбору пороговых коэффициентов и т.п. Однако сама идея управления памятью для таких задач вполне применима.

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

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

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

Литература

1. Кнут Д. Искусство программирования для ЭВМ. Том II — М.: Мир, 1976.
2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

С автором можно связаться по адресу y_zaches@mail.ru или по тел. (095)971-36-23.

КомпьютерПресс 12'2000