2.10. Объект tList (универсальный список)

Итак, первый объект, ведущий свое происхождение от TObj (и уже используемый в самом объекте TObj, чтобы хранить список объектов и методов для автоматического разрушения) - это TList. В нем можно хранить произвольные указатели или 32-разрядные числа (поэтому и называется он "универсальным" списком).

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

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

Для этого существует свойство Capacity, которое определяет, для какого количества элементов в списке будет резервироваться память. При превышении размером списка (свойство Count - текущий размер списка) величины Capacity, она пересчитывается по некоторому несложному алгоритму, который выбран как разумный компромисс между экономией резервируемой памяти и оптимизацией скорости программы за счет уменьшения количества перераспределений памяти для массива указателей. По умолчанию, пересчет заключается в увеличении резервируемого размера на AddBy, изначально равное 4, но если свойству AddBy присвоить 0, то увеличение происходит сразу на 25%, но не более чем на 1000. Разумеется, этот алгоритм не может быть хорош для всех случаев жизни, поэтому при необходимости оптимизации автор программы имеет возможность своим кодом определить минимальный размер резервируемой памяти, присваивая желаемое значение свойству Capacity.

Основное свойство объекта TList - это Items[ i ], которое обеспечивает доступ к элементам списка по индексу. Например, типичный цикл перечисления всех элементов списка от первого до последнего мало чем отличается от того, что делается в VCL:

var L: PList; i: Integer; P: Pointer;

...

for i := 0 to L.Count-1 do

begin

P := L.Items[ i ];

... // работаем с P

end;

Отмечу (еще раз, это уже упоминалось выше), что краткая запись P := L[ i ] недоступна, т.к. объекты object, в отличие от классов, не могут иметь свойств по умолчанию (а жаль, я, например, не вижу в таком ограничении никакого смысла, кроме отсутствия желания у разработчиков Dephi обеспечить этот удобный сервис).

Еще одно существенное отличие от VCL состоит в том, как создается экземпляр объектного типа TList. Если в VCL мы писали:

var L: TList;

...

L := TList.Create;

то в KOL следует писать иначе:

var L: PList;

...

L := NewList;

Теперь приведу основной набор методов и свойств TList, в дополнение к уже упомянутым:

Add( P ) - добавляет указатель в конец списка;

Insert( i, P ) - вставляет указатель в позицию i (все прежние элементы начиная с i, если такие были, сдвигаются на одну позицию вверх);

Delete( i ) - удаляет один элемент с индексом i (все элементы с индекса i+1, если такие есть, сдвигаются на одну позицию вниз);

DeleteRange( i, n ) - быстрое удаление n элементов с позиции i (допускается указывать в качестве n большее значение, чем имеется элементов начиная с позиции i, т.е. DeleteRange( i, MaxInt ) - удалит все элементы начиная с индекса i);

Remove( P ) - находит и удаляет первое вхождение указателя P;

Clear - очищает список, удаляя из него все указатели;

IndexOf( P ) - находит первое вхождение указателя P и возвращает его индекс (или -1, если такого указателя в списке нет);

Last - возвращает последний указатель в списке, эквивалентен Items[ Count-1 ];

Swap( i1, i2 ) - обменивает местами указатели с индексами i1 и i2;

MoveItem( i1, i2 ) - удаляет элемент из позиции с индексом i1 и вставляет его в позицию с индексом i2;

Release - может использоваться для разрушения списка указателей на области памяти, выделенные в куче (функциями GetMem или AllocMem, ReallocMem), предварительно для всех ненулевых указателей выполняется вызов FreeMem;

ReleaseObjects - аналогично предыдущей процедуре, но используется для списка указателей на объекты: все объекты в списке разрушаются вызовом метода Free;

AddItems( a ) - позволяет добавить сразу массив указателей;

Assign( L ) - присваивает списку элементы другого списка, т.е. попросту копирует массив указателей;

DataMemory - возвращает текущий указатель на внутренний массив указателей, из которых и состоит список (следует применять с осторожностью, и только при необходимости существенно оптимизировать скорость доступа к элементам списка).

Замечание. В KOL имеется так же объектный тип TListEx (но он вынесен в дополнительный модуль KOLadd.pas, из соображений экономии числа строк в основном модуле KOL.pas, и по причине отсутствия жесткой необходимости в его использовании). В дополнение к свойствам и методам TList, в нем имеется свойство Objects[ i ], методы AddObject( P, o ), InsertObject( i, P, o ) и прочие - позволяющие связать с каждым элементом списка еще один "объект"-число или указатель. В действительности, особой необходимости в таком объекте нет, и часто достаточно использовать тот же TList, храня в нем пары значений и полагая, что каждый четный элемент вместе с последующим нечетным образуют неразрывную связку.

2.10.А. Ускорение работы с большими списками и списками строк. Символ условной компиляции TLIST_FAST.

Кроме того, с символом условной компиляции TLIST_FAST изменяется структура списка и алгоритмы работы с элементами таким образом, чтобы обеспечить большую скорость операций добавления новых элементов. При этом становится доступным дополнительное свойство UseBlocks, позволяющее контролировать использование новых методов списка. Повышение скорости происходит, прежде всего, за счет того, что уменьшается количество операций перераспределения памяти (с копированием накопленных указателей в новое место в памяти). Точнее, перераспределение памяти вообще более не требуется, лишь по мере надобности выделяются новые блоки по 256 элементов на блок.

К сожалению, увеличение быстродействия на этапе добавления элементов оборачивается уменьшением скорости обращения к элементам списка. В случае, когда в блоках, кроме последнего, используются все элементы, сокращение скорости доступа незначительно: по индексу вычисляется индекс блока (простым делением на 256), и после получения указателя на блок из сплошного списка блоков, требуемый элемент может быть извлечен. Худший результат получается, если в результате удаления или вставки элементов где-нибудь в середине или в начале списка образовались не полностью занятые блоки. В этом случае для поиска нужного блока и индекса искомого элемента в нем используется более долгий алгоритм, требующий перечисления всех блоков от начального до требуемого блока. Он несколько оптимизирован для случая последовательного доступа к элементам, но часто списки используются как массивы указателей с произвольным порядком доступа, и в этом случае замедление может быть существенным.

Чтобы ускорить работу с «быстрым» списком на этапе, когда его первоначальное наполнение выполнено, и далее он используется только для доступа к элементам, требуется обеспечить его «плотное» заполнение, при котором в нем полностью заполнены все блоки (кроме, может быть, последнего). Для этого достаточно вызвать метод OptimizeForRead, выполняющий уплотнение блоков.

Заметим, что в случае, когда в опциях проекта определен символ TLIST_FAST, он оказывает влияние так же на списки строк TStrList, TStrListEx, TWStrList, TWStrListEx. Для того, чтобы ускорить их работу после первоначального заполнения, следует вызывать их метод OptimizeForRead, который обращается к соответствующему методу внутреннего списка.