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

Поиск
L



Статистика
u
Пользователи онлайн: нет
Гостей онлайн: 4
Всего онлайн: 4
Зарегистрировано юзеров: 5970
Комментариев на сайте: 630
Новый юзер: GeorgeKax



Последние комментарии
c
Theihpled прокомментировал "Урок 62 - Методы, наследование классов, операции с классами Delphi, (часть 4/6)":
Здравствуйте, Савельев Александр. У меня к вм небольшой вопрос по языку https://cloud.mail.ru/public/KFS1/dYUrFbaTU . Cпасибо за уроки.
Theihpled прокомментировал "Урок 54 - Потоки в Delphi, (часть 2/3)":
Кстати да. С потоками тоже ничего не вышло.



Мы в соцсетях
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
Просмотров: 127754


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