1. Теоретические положения

1.1. Линейные связные блоковые списки

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

Рис. 1. Узловой связный список

Узлы списков могут быть размещены в памяти любого типа, в том числе в статической и внешней, т.е. не оперативной памяти. Так, типичным односвязным списком является структура данных FAT одноименной файловой системы, размещаемой на внешних носителях.

Вблоковых структурах элементы объединяются в группы - блоки. Явная информация "предыдущий/следующий" определяется для блока, а не для каждого элемента. Элементы внутри блока содержат неявную связь, т.е. образуют массив (см. рис. 2).

Рис. 2. Блоковый связный список

Появление структуры данных, изображенной на рис. 2, обусловлено, в основном, потребностью минимизировать время доступа к данным. Списки применяются в случаях, когда требуются частые и быстрые операции вставки/удаления в произвольную позицию последовательности. Векторы же ориентированы на задачи, в которых требуется эффективный доступ к элементу в произвольной позиции по индексу. Несмотря на то, что для списка можно эмулировать произвольный доступ, любая его реализация будет малоэффективной. В то же время вставка/удаление в вектор тем менее эффективна, чем ближе к началу находится позиция вставки: "хвост" приходится сдвигать на одну позицию. В контейнерах профессионального уровня, например, файловых системах, структурах данных компиляторов и интерпретаторов, часто используются связные блоковые списки. Рассмотрим организацию двусвязного блокового списка с заданным постоянным размером блока М:

const int M = 16;

...

struct Block {

int cnt;

int cells[M];

Block *previous;

Block *next;

};

Здесь приведена структура на языке Си для представления блока размером 16 ячеек (cells), каждая из которых хранит целое число. Интерфейс блокового списка мало чем отличается от интерфейса линейного списка любого другого вида. Таким образом, блочная структура становится скрытой особенностью реализации. С некоторыми упрощениями определим интерфейс так:

1. Вставить элемент в голову списка (InsertToHead).

2. Удалить элемент из головы списка (DeleteFromHead).

3. Вставить элемент в хвост списка (InsertToTail).

4. Удалить элемент из хвоста списка (DeleteFromTail).

5. Вставить элемент в произвольную позицию i (Insert(i)).

6. Удалить элемент из произвольной позиции i (Delete(i)).

7. Получить значение элемента в голове (GetHeadElement).

8. Получить значение элемента в хвосте (GetTailElement).

9. Получить значение элемента в произвольной позиции i (GetElement(i)).

10. Установить значение элемента в голове (SetHeadElement).

11. Установить значение элемента в хвосте (SetTailElement).

12. Установить значение элемента в произвольной позиции (SetElement(i)).

13. Очистить список (Clear).

С узловыми списками применяют итераторы (iterator) – абстракции, сходные с указателями на узлы. В зависимости от степени связности, итератор позволяет переходить к следующему и/или предыдущему узлу, изменяя свое значение на новый адрес. Часто используются термины инкремент/декремент итератора – переход к следующему и предыдущему узлам соответственно. Помимо навигации по списку, итератор используется для чтения/изменения значений данных, хранящихся в узлах. С блоковым списком поэлементный итератор применяться не может, так как для граничных элементов блока семантика итератора отличается от семантики для внутренних элементов. Иными словами, переход к предыдущему/следующему для итераторов первого, некоторого внутреннего и последнего элементов должен осуществляться по разным правилам. Такое разнообразие было бы чрезвычайно неудобным в работе. Поэтому в приведенном выше интерфейсе нет функций вида "получить адрес элемента", в отличие от широко использующегося в узловых списках соответствующего набора операций. Можно было бы отказаться от функций "установить/получить значение", заменив их функциями получения адресов элементов в голове, хвосте и произвольной позиции, а операции чтения/изменения производить через эти указатели, которые не являются итераторами, так как не обеспечивают навигацию. С другой стороны, нежелательно предоставлять доступ к внутренним данным блока из соображений надежности. Помимо надежности, всегда актуальна проблема повышения производительности. Представим ситуацию, что пользователь контейнера реализует просмотр элементов с изменениями, при необходимости, т.е. выполняет нечто подобное:

for (int i = 0; i < n; ++i) {

a = GetElement(i); //прочитать ячейку

...

// использовать а, возможно, изменить значение

if (некоторое условие)

SetElement(i, a);

}

По законам пространственной и временной локальности, эмпирически выведенным для типичных случаев доступа к данным, вероятность того, что обращения, разделенные небольшим промежутком времени, будут осуществляться к близким в адресном пространстве ячейкам, выше вероятности обращения к разнесенным данным. Иными словами, если в указанном цикле мы обращаемся к одному и тому же элементу на чтение/запись (логическое расстояние 0), то могли бы с высокой вероятностью использовать предыдущий/следующий элементы (логическое расстояние 1). И наоборот, значительно реже может понадобиться доступ "через один" (логическое расстояние 2) и т.д. элементы. Реализация функций GetElement/SetElement будет, в общем случае, просматривать в блоковом списке блок за блоком, начиная, например, от головы и наращивая счетчик пройденных элементов каждый раз на значение счетчика занятых элементов в текущем блоке, пока не остановится на том блоке, в котором находится запрашиваемая позиция. Это весьма длительный итеративный процесс, несмотря на то, что по сравнению с узловыми списками здесь происходит ускорение за счет "скачков" через блоки. Эффективная реализация функций доступа к произвольному элементу должна вести нечто вроде кэш-таблицы, содержащей два поля – номер позиции, адрес блока, в котором находится элемент, индекс элемента в массиве. При каждом обращении к некоторому элементу i сначала просматривается кэш-таблица. Если в поле "номер позиции" найдено значение i, то сопутствующая информация на этой строке используется для быстрого доступа; если же кэш не содержит позицию i, происходит общая процедура скачкообразной итерации по блокам. Когда элемент будет найден, индекс элемента в массиве и адрес блока, в котором остановился поиск, следует занести в кэш.

Размер кэш-таблицы должен выбираться относительно небольшим. Следует постоянно держать в кэше записи для головы и хвоста. Так как поиск в такой таблице будет, скорее всего, линейным, ее размер ограничен единицами строк (3-5). Она может включать, например, записи о голове, хвосте, последнем из запрашивавшихся элементов, предыдущем и последующем – для последнего из запрашивающихся. Как будет показано ниже, подобный кэш может эволюционировать в индексную таблицу, ускоряющую доступ. Следует также иметь в виду, что кэш перестраивается при каждой операции вставки/удаления и при каждом новом обращении, что является еще одним аргументом в пользу его ограниченного размера.

Вставка элемента в блок реализуется по следующему правилу:

если блок содержит свободные ячейки (т.е. cnt < M), то вставить элемент (возможно, со сдвигом содержимого блока на одну позицию); увеличить счетчик;

иначе // т.е. блок заполнен до конца

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

конец_если

Если реализован кэш, следует обновить соответствующие позиции и адреса. Графический пример вставки элемента в блоковый список приведен на рис. 3. Несмотря на то, что в блоке D (рис. 3) оставалось свободное место и можно было не создавать новый блок C', а сдвинуть блок D на одну позицию вправо и разместить там "вытесняемую" из блока С букву m, был добавлен новый блок. Очевидно, что допустимы обе стратегии (рис. 4). Назовем первый вариант вставки (рис. 3) стратегией 1, а второй (рис. 4) – стратегией 2.

Рис. 3. Пример вставки элемента: а – исходный блоковый список; б – блоковый список после вставки в позицию 8 буквы "i"

Рис. 4. Вставка элемента без создания нового блока

В случае использования стратегии 2 правило вставки таково:

если блок содержит свободные ячейки (т.е. cnt < M), то вставить элемент (возможно, со сдвигом содержимого блока на одну позицию); увеличить счетчик;

иначе // т.е. блок заполнен до конца

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

иначе // следующий блок тоже заполнен до конца

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

конец_если

конец_если

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

При удалении существует только одна стратегия. Общий принцип реализации удаления из блока таков:

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

иначе // удаляется последний элемент

исключить опустевший блок полностью, удалив узел в двусвязном списке, настроив указатели previous и next, где необходимо

конец_если

Графический пример удаления элементов приведен на рис. 5.

Преимущества блоковых списков перед узловыми:

1. Ускорение доступа к произвольной позиции в списке.

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

2. Снижение накладных расходов на служебные описатели динамической памяти.

Рис. 5. Удаление элементов: а – исходный блоковый список; б – блоковый список после удаления элементов из позиций 4 и 7

Каждый участок динамической памяти, занятый или свободный, содержит примерно следующие дополнительные атрибуты: признак занятости, размер, указатель на следующий участок в цепочке. Известно, что описатель участка динамической памяти занимает от восьми до шестнадцати и более байт. Объявление типичного узла занимает 12 байт:

struct Node {

Node *previous; //как правило, указатель занимает 4 байта

Node *next;

int data; // размер данных целого типа, как правило, 4 байта

};

Возможно, что структура будет выровнена на параграф, т.е. границу 16 байт. Когда такой элементарный узел нужно будет разместить в куче, описатели фрагмента потребуют еще от восьми до шестнадцати байт. Видно, что полезная информация узла (поле int data) "тонет" среди обилия сопутствующих служебных полей.

Для блоковых списков ситуация с накладными расходами значительно улучшается. Для блока, являющегося узлом двусвязного списка, потребуются два указателя (8 байт), дополнительно – счетчик целого типа (4 байта) и уже не одна, а M ячеек полезных данных. При типичном значении M = 16 и хранении в ячейках целых чисел, получаем 64 "полезных" байта и 12 + (8..16) байт на указатели, счетчик и описатели в куче, т.е. в 2-3 раза меньше служебной информации, чем полезной.

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