Динамические структуры данных

Что такое динамические структуры? Да просто данные, размер которых может меняться во время работы программы. В Delphi есть массивы, которые так и называются динамическими, есть строки. TStream тоже можно так назвать, его размер легко изменить в любой момент. Все замечательно, и очень удобно для программиста. Вот только в современных компьютерах работа с памятью - одна из самых медленных операций, да еще и скорость работы память практически не зависит от частоты процессора. А изменение размера структуры, как правило, приводит к перераспределению памяти. Вот и получается, что изменение размера массива, например, весьма долгая операция.
В этой статье мне хочется рассказать о структуре, которая позволяет значительно ускорить операции со структурами изменяемых размеров.

Программисту очень часто приходится работать со строками, и иногда - с длинными строками. И часто мне приходится видеть примерно следующий код:

var
 s: string;
 ch: char;
 i, N: integer;
begin
 S:= '';
 for i := 1 to N do
 s := s + ch;
...

Вроде бы все хорошо. Но string в Delphi подразумевает использование динамической строки (ansistring, можно, правда, объявить переменную как ShortString или выключить опцию компилятора, но тогда длина строки ограничена 255 символами). Чтобы понять, что именно происходит в цикле, посмотрим, как устроена динамическая строка. Почти все сказанное ниже относится и к динамическому массиву, исключением является только отсутствие аналога UniqueString для массива.

Итак, про включенной опции компилятора $H (или $LONGSTRINGS ON), которая включена по-умолчанию, тип string - это на самом деле ansistring. А переменная, имеющая тип ansistring, является указателем. Delphi автоматически разыменовывает (операция-шапочка ^) этот указатель, и делает некоторые другие преобразования. Если в этой переменной содержится nil - это и есть пустая строка, таково соглашение. Но когда переменной присваивают другую строку или устанавливают длину строки через SetLength, этот указатель уже ссылается на следующую область памяти:

Здесь S - переменная типа ansistring

Как видно, не все так просто: сам указатель ссылается на первый символ строки, но за 4 байта до него идет поле длины строки, а перед ним - еще и поле подсчета ссылок. Вправо от указателя идут как раз Length символов, собственно строка, плюс еще один символ, #0. Для чего это сделано? Все очень просто, легким нажатием на клавиатуру строка может превратиться в PChar: PChar(S), и это часто применяется при работе с API. Именно для этого переменная ссылается на первый символ и в конце стоит #0. Но при этом надо учитывать, что функция, получающая PChar, ничего не знает о Length и RefCount, поэтому изменение длины строки в ней недопустимо.
Поле Length, думаю, понятно, хранит длину строки, функция Length просто возвращает это значение. RefCount - гораздо более интересное поле, это счетчи использований строки. Дело в том, что при присвоении одной переменной другой копирования строки не происходит, просто увеличивается счетчик ссылок, а обе переменные указывают в одно и то же место. Но при изменении одной из переменных вызывается встроенная функция UniqueString, которая "раздваивает" переменные при необходимости. Счетчик ссылок очень выгоден при обмене строк, что происходит, например, при сортировке: T := S1; S1 := S2; S2 := T, здесь просто присваиваются указатели, и модифицируется поле ссылок. Кстати, это также означает, что использовать указатели на строки абсолютно бессмысленно: все уже сделано.

Вернемся к примеру и посмотрим, что же происходит на самом деле:

var
 s: string; //ansistring
 ch: char;
 i, N: integer;
begin
1. S:= ''; 
2. for i := 1 to N do
3. s := s + ch;
...

Первая строка - на самом деле S := nil, довольно просто. А вот третья раскладывается на выделение памяти для новой строки длины (Length(S) + 1) и копирование прежней строки в новую область памяти, после этого S указывает на эту область. И так N раз! На самом деле, в цикле еще идет вызов UniqueString, что тоже не добавляет скорости. И если выделение области памяти сравнительно быстрая операция, то время копирования прежней строки на новое место напрямую зависит от ее длины. Можно показать, что время выполнения строк 2 и 3 пропорционально N^2.

Можно ли уменьшить это время? Конечно. В этом примере достаточно заменить три строки на эти:

1. SetLength(S, N); 
2. for i := 1 to N do
3. s[i] := ch;

Здесь память для всей строки выделяется сразу и время выполнения цикла пропорционально N. Но что делать, когда окончательная длина строки заранее не известна? Можно выделить память с запасом, а потом, когда она станет известной, вызовом SetLength установить нужную. Но часто это слишком накладно. Второй выход - использовать связанный список, каждый элемент которого - символ или строка, и потом собирать строку, проходя по этому списку. Что-то подобное сделано в TStringList и TList.

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

Приступим. Задача состоит в том, что нам нужен массив, который может расти и уменьшаться в размере, но при этом делать это как можно быстрее. Основная идея: если мы знает, что массив будет расти, то можно выделить память не просто под новый размер, а с запасом. Подобное, как раз, делается в TStringList и в TList, в этих классах есть совершенно одинаковый метод Grow, который вызывается, когда места во внутреннем массиве недостаточно:

procedure TList.Grow;
var
 Delta: Integer;
begin
 if FCapacity > 64 then
 Delta := FCapacity div  4
 else
 if FCapacity > 8 then
 Delta := 16
 else
 Delta := 4 ;
 SetCapacity(FCapacity + Delta);
end;

Capacity - это максимальное количество элементов списка. SetCapacity как раз и выделяет дополнительную память для (FCapacity + Delta) элементов. При количестве элементов больше 64, как только все место использовано, к нему прибавляется еще четверть. Понятно, что это гораздо быстрее, чем выделять место каждый раз при добавлении нового элемента.

Но, к сожалению, обратной процедуры (я бы назвал ее Shrink) нет, оба списка, захапав себе память, держат ее до самого Free.

Давайте сделаем класс, который будет как забирать память, так и отдавать ее. Иногда ;). Меня больше всего привлекает символьный стек, что-то вроде TStack, но для символов.

В качестве операций предусмотрим Pop, Push, asString (получить все содержимое в виде строки) и Clear (полная очистка). Разумеется, ничто не мешает сделать аналог того же TList или TMemoryStream, но ограничимся этим.

Сначала рассмотрим и проанализируем простое добавление символов в стек. Хранить мы их будем внутри объекта в строке, что вполне естественно. Если в строке не хватает места для очередного символа, надо увеличить ее длину. Поскольку предполагается, что символы будут и удаляться, будем щедрыми, будем увеличивать длину сразу в два раза. На самом деле, как будет видно ниже, вопрос не совсем в щедрости, так лучше всего.

Вот объявление класса:

 type
 TCharStack = class
 private
 FList: string;
 FSize: integer;
 function GetCapacity: integer;
 function GetSize: integer;
 procedure Grow;
 procedure Shrink;
 public
 procedure Push(Ch: char);
 function Pop: char;
 procedure Clear;
 function AsString: string;
 property Size: integer read GetSize;
 property Capacity: integer read GetCapacity;
 end;
 
 

А это - реализация:

 function TCharStack.AsString: string;
begin
 Result := FList;
 SetLength(Result, FSize);
end;
procedure TCharStack.Clear;
begin
 FSize := 0 ;
 FList := '' ;
end;
function TCharStack.GetCapacity: integer;
begin
 Result := Length(FList);
end;
function TCharStack.GetSize: integer;
begin
 Result := FSize;
end;
procedure TCharStack.Grow;
var
 Delta, Len: integer;
begin
 Len := Length(FList);
 Delta := Len;
 if Delta = 0 then
 Delta := 64 ;
 SetLength(FList, Len + Delta);
end;
procedure TCharStack.Push(Ch: char);
begin
 if (FSize + 1 ) > Length(FList) then
 Grow;
 inc(FSize);
 FList[FSize] := ch;
end;
 

Как видно, пока нет реализации Pop и нет метода Shrink, уменьшения размера. Чуть позднее, сначала посмотрим, что получилось. FList - собственно строка, содержащая символы, FSize хранит реальный размер стека. Я добавил пару свойств, Size и Capacity, думаю, понятно, что они возвращают. AsString просто берет всю строку, и устанавливает реальный размер. Push - "заталкивает" символ в стек, при этом, если места в FList нет, предварительно вызывается процедура Grow, которая выделяет его. При этом, хотя мы договорились удваивать его, но в ней, если символов еще не было, выделяется место сразу для 64 символов, на мой взгляд, так более целесообразно, иначе при пустом FList и условии if Delta = 0 then Delta := 1; он становится длиной сначала 1 символ, потом 2, 4, 8 - это довольно частое перераспределение памяти.

Теперь оценим, во что нам обходится вставка символов в стек. Все происходит очень быстро, пока не возникает необходимость в увеличении размера FList. Действительно, вызов Push, при котором не выполнилось условие для наращивания памяти, можно принять за единицу, ведь время выполнения не зависит в этом случае от размера стека. Теперь посмотрим, за какое время выполняется Grow: получение длины строки - тоже единица, функция возвращает переменную, не проходя всю строку. Остается SetLength, и ее время выполнения напрямую зависит от длины строки, здесь неявно, как я уже говорил, происходит выделение памяти для новой строки длиной Len + Delta, копирование Len символов на новое место (исключая первый вызов, естественно) и уничтожение прежней строки. Теперь два важных замечания:

• Если строка достаточно длинная, то временем выделения и освобождения памяти можно пренебречь, основное и гораздо большее время расходуется на копирование Len символов на новое место. Вопрос состоит в том, какую строку можно назвать достаточно длинной? Это зависит от многих факторов, и можно указать, что при длине строки больше размера свободной памяти это утверждение явно не выполнится. Но давайте примем это замечание, как близкое к истине. Тогда время выполнения Grow будет пропорционально Len, длине уже имеющихся символов (копируем-то только половину новой строки!).
• Второе: Хотя время выполнения Grow зависит от длины строки, вызовы его идут все реже с ростом ее размера, первый вызов - через 64 вызова Push, следующий - через 128 и так далее, время между вызовами возрастает по экспоненте.

Понятно, что можно указать точное время выполнения Push для ланного количества уже имеющихся символов в стеке, но интереснее и практичнее ответить на вопрос: сколько времени в среднем выполняется Push?

Ответ на этот вопрос легче всего получить с помощью амортизационного анализа. Что это такое? Найдите главного бухгалтера и спросите у него. Ответ, скорее всего, будет таким: "Есть, например компьютер. На нем работают. Но через пять лет он устареет, и придется покупать новый, и скорее всего стоить он будет столько же, сколько в свое время старый. Вот и делают каждый месяц амортизационные отчисления, равные 1/(5*12), то есть 1/64 его стоимости. И через 5 лет накапливается как раз стоимость нового компьютера." На самом деле, немного сложнее, но суть та же.

Здесь тот же принцип, распределим время выполнения Grow равномерно на каждый вызов Push. Начнем с момента, когда первые 64 символа заполнены, и длина строки увеличена до 128. Как написано выше, выполнение Push без вызова Grow принято за 1. Допустим, стоимость этой операции 1 рубль (или 1 ms, или 100 тиков...). Но платить мы будет не 1, а 3 рубля при каждой вставке. 1 рубль - за вставку, а следующие два распределим так: рубль оставим для переноса только что вставленного символа на новое место, и еще один - для переноса символа из первой половины таблицы. Тогда в тот момент, когда будут вставлены оставшиеся 64 символа и наступит момент нового увеличения таблицы, перенос всех 128 символов на новое место жительства будет оплачен. Далее история повторится: размер увеличен до 256, можно вставить еще 128 символов, платим за каждый по трешке, рубль на вставку, рубль на будущий перенос этого символа и символа из первой половины...

Что же получается? В среднем время на вставку символа в стек примерно в три раза дороже, чем в лучшем случае. Конечно, нельзя сказать, что это время равно (время на присвоение значения символу в строке)*3, оно гораздо больше, но тем не менее, в среднем вставка символа не зависит от длины строки! То есть, вставка N символов займет время, пропорциональное N. Хотя, конечно, это время будет больше, чем в приведенном выше примере наращивания строки символами, но при этом нет нужды знать окончательную длину строки.

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

Но вернемся к стеку. Нам осталось реализовать удаление символа из стека. Сначала процедура уменьшения длины FList в два раза:

 procedure TCharStack.Shrink;
var
 NewSize, Len: integer;
begin
 Len := Length(FList);
 NewSize := Len div  2 ;
 if NewSize < 64 then
 exit;
 SetLength(FList, NewSize);
end;
 
 

Она, по сути, аналогична Grow, и сохраняет минимальный размер в 64 символа. Понятно, что минимальный размер принят просто для удобства, он не оказывает влияния на оценки, сделанные выше. Но тут возникает следующая проблема: допустим, в строке у нас 128 символов и мы добавили 129 (Push), при этом размер строки увеличился до 256. Уберем символ (Pop). Логично было бы вернуть размер строки обратно к 128 символам, не так ли? Но это вызовет копирование всех 128 символов на новое место, а мы только что израсходовали всю амортизацию на увеличение... Что делать? Учитывать в амортизации еще и уменьшение? Не получится, модет получиться так, что в программе этот 129 символ будет добавляться и удаляться много раз, этого не учтешь. Но выход есть, будем уменьшать размер строки, когда количество символов в ней станет не больше 1/4 от полной вместимости:

 function TCharStack.Pop: char;
begin
 if FSize = 0 then
 raise ERangeError.Create( 'Стек пуст!' );
 Result := FList[FSize];
 dec(FSize);
 if FSize <= (length(FList) div  4 ) then
 Shrink;
end;
 
 

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

Назовем отношение Size/Capacity (количество символов к размеру стека) коэффициентом заполнения µ. Тогда для данной структуры оптимальным считается µ=1/2, и при отклонении в два раза в обе стороны (до 1/4 и до 1) память перераспределяется. В этом случае среднее время на операции добавления N символов в стек, равно как и удаления N символов пропорционально N.

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