Файл к
статье
Что такое динамические структуры? Да просто данные,
размер которых может меняться во время работы программы. В 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
от полной вместимости:
