Логин: Пароль:    Регистрация Всеми возможностями сайта можно пользоваться
только после авторизации.
   Забыли пароль?

Поиск
L



Статистика
u
Пользователи онлайн: нет
Гостей онлайн: 2
Всего онлайн: 2
Зарегистрировано юзеров: 6362
Комментариев на сайте: 645
Новый юзер: Pseulairrerve



Последние комментарии
c
Aqel прокомментировал "Урок 71 - Работа с сжатыми файлами":
GZip псевдоархив, на мой вопрос тоже не отвечают, как распаковать отдельные файлы/папки...
Pingitrus прокомментировал "Урок 71 - Работа с сжатыми файлами":
Есть еще кто нибудь живой на этом сайте, кто сможет помочь? Так то все работает, zip и rar распаковывает, но у меня есть файл dat который сжат GZip, почему то его не удается распаковать или так не получится так как этот файл не является архивом или является?)) пишет ошибку что неверная функция



Мы в соцсетях
c
Delphi
Динамические структуры данных

Что такое динамические структуры? Да просто данные, размер которых может меняться во время работы программы. В 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
	S:= ''; 
	for i := 1 to N do
	s := s + ch;
	...
	
Первая строка - на самом деле S := nil, довольно просто. А вот третья раскладывается на выделение памяти для новой строки длины (Length(S) + 1) и копирование прежней строки в новую область памяти, после этого S указывает на эту область. И так N раз! На самом деле, в цикле еще идет вызов UniqueString, что тоже не добавляет скорости. И если выделение области памяти сравнительно быстрая операция, то время копирования прежней строки на новое место напрямую зависит от ее длины. Можно показать, что время выполнения строк 2 и 3 пропорционально N^2.

Можно ли уменьшить это время? Конечно. В этом примере достаточно заменить три строки на эти:
	SetLength(S, N); 
	for i := 1 to N do
	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.

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

Вот и всё, Удачи!

Источник: www.thedelphi.ru
Автор: Савельев Александр
Опубликовано: 1 Марта 2015
Просмотров:


Зарегистрируйтесь или авторизуйтесь, чтобы добавлять комментарии.