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

Поиск
L



Статистика
u
Пользователи онлайн: нет
Гостей онлайн: 9
Всего онлайн: 9
Зарегистрировано юзеров: 7432
Комментариев на сайте: 665
Новый юзер: puskkk



Последние комментарии
c
Ginaneula прокомментировал "Урок 3 - Конструкция IF...THEN...ELSE":
[img]https://kapsuly-lipocarnit.ru/files/lipocarnit_1/img/product-head1.png[/img] [url=https://kapsuly-lipocarnit.ru/][img]https://karga.info/wp-content/uploads/2019/02/orig.jpg[/img][/url] Купить Липокарнит в Могилёве (Беларусь) через интернет-аптеку Функции Производитель: ООО "КоролевФарм" Форма выпуска: капсул Упаковка: полимер Объем: 72 г Срок действия: 2 года Доставка: почтой, курьером Оплата : наличными, карта Фотографии продукции Чтобы заказать Липокарнит, оставьте свои контактные данные в форме ниже, и мы свяжемся с вами как можно скорее. [url=https://kapsuly-lipocarnit.ru/]lipocarnit отзывы реальные[/url] - Мы обещаем полную анонимность. Ваши данные не будут переданы 3 людям. Внимание: внимательно проверьте введенный номер и не забудьте включить телефон, чтобы наш оператор мог с вами связаться. Левокарнитин для похудения Городская суета стимулирует постоянный стресс. Большинство людей не справляются с ними, они начинают компенсировать отвратительное настроение избытком соленой и высококалорийной пищи, что приводит к увеличению веса. Ожирение является предпосылкой других приобретенных заболеваний, таких как диабет, гипертония, склероз сосудистого русла, болезни сердца. Чтобы сохранить здоровье на долгие годы, вы должны иметь нормальный вес. Для этого есть комплекс Липокарнит. Что это за продукт Липокарнит - фармацевтический продукт, созданный российскими и швейцарскими учеными специально для лечения ожирения у пациентов с избыточным весом. Преимуществом продукта является стопроцентная натуральная композиция растительного происхождения, которая не подвергает организм чрезмерным нагрузкам при метаболизме его компонентов. Биологически активная добавка к пище доступна в форме капсул от производителя. Обмана нет Перед выпуском лечебного средства для продажи производитель выполнил медицинские тесты. Была взята контрольная группа клиентов, которые худели с помощью ежедневных физических нагрузок, правильного питания, различных органических добавок. Исследуемая группа не изменила привычного распорядка дня и образа жизни. Он просто воспринимал продукт Липокарнит. Динамика снижения веса один раз в день регистрировалась в дневнике. Данные контрольной группы были значительно ниже, чем в исследовании. Испытания и противопоказания для введения фармацевтического продукта По крайней мере, некоторые продукты имеют свои собственные ограничения на потребление. Пищевая добавка Липокарнит характеризуется небольшим перечнем противопоказаний. Отзывы Противопоказания Любая степень ожирения беременность; лактация; отвратительная переносимость фармацевтического продукта; аллергическая реакция на активные или вспомогательные компоненты препарата; Дефицит лактазы. Медицинские исследования не выявили побочных эффектов при введении биодобавки. Влияние [url=https://kapsuly-lipocarnit.ru/]липокарнит купить в могилеве[/url]а на организм Продукт положительно влияет на работу всех органов и систем пациента. Нормализует работу печени, восстанавливает ее клетки. Помогает очистить кишечный тракт, средство удаления накопившихся токсических веществ. Оказывает разрушительное действие на атеросклеротические бляшки артерий, что увеличивает их внутренний просвет. Благодаря этому эффекту улучшается питание органов и тканей, снижается риск инфаркта миокарда и инфаркта миокарда. Липокарнит снижает уровень холестерина и уровень сахара в крови. Биокомплекс повышает активность клеток мозговой ткани, ускоряет проведение нервных импульсов, улучшает память и общее самочувствие. Биоактивная добавка ускоряет клеточный метаболизм за счет истончения подкожного жира. В дополнение к этим эффектам липокарнит способен нормализовать гормональный фон организма человека. Препарат устраняет нарушение функции щитовидной железы. Многие женщины с историей гипотиреоза заметили улучшение своего общего состояния, укрепление ногтей, волос, нормализацию менструального цикла и отсутствие ночного пота при приеме Липокарнита. Состав и характеристика фармацевтического препарата Биокомплекс содержит три активных элемента. К ним относятся: липоевая кислота; L-корнитин; пиколинат хрома Основные эффекты биологических компонентов активной добавки компоненты Воздействие на организм ускоряет обмен веществ в клетках; подавляет всасывание обычных углеводов; разрушает жировые клетки, направляет энергию, выделяемую для восстановления силы тела; оказывает омолаживающее действие на кожу. облагораживает познавательные способности человека; стимулирует физическую активность пациента; снимает синдром приобретенной усталости; Способ введения энергии от расщепления жиров в конструкцию молекул белкового соединения ускоряет рост мышц. удаляет токсичные соединения, свободные радикалы, способ их абсорбции в кишечнике; снижает уровень сахара в крови; восстанавливает клетки мышечной и костной ткани. В совокупности эти три вещества выполняют регенеративную функцию для всех тканей организма. Примечание о введении биоактивных добавок Фармацевтический препарат следует употреблять потребителям с ожирением и избыточным весом по 1-2 капсулы 2 раза в день во время еды утром и вечером, запивая большим количеством воды. Вступительный курс составляет 1 месяц. Если результат не был достигнут, потребление Lipocarnitum может быть продолжено после 2-месячного перерыва. Перед введением препарата проконсультируйтесь с врачом. Не принимайте биологический комплекс самостоятельно. Где я могу найти Липокарнит Товар эксклюзивный, аналогов не имеет. В аптеке пт нет. Липокарнит можно приобрести только на нашем официальном сайте. Сейчас идет акция: фармацевтический продукт можно получить со скидкой 50% для всех посетителей. Рекламная продукция ограничена (осталось 60 упаковок). Поставщик имеет все необходимые лицензии и сертификаты для внедрения продукта. Посетите сайт производителя, закажите отличный продукт для похудения. Чтобы не покупать поддельный фармацевтический продукт, не покупайте биокомплекс в магазинах и других местах. Каждый пакет имеет свой уникальный код безопасности. Он может быть размещен на сайте производителя для проверки подлинности лечебного средства. Сколько стоит диетический продукт Общая стоимость липокарнита - 1980 руб. Цена лечебного средства со скидкой 50% составляет 990 рублей. Количество товара ограничено. Возьми комплекс по хорошей цене, сожги лишние килограммы, наслаждайся своей безупречной фигурой. Мы стараемся сделать все, чтобы вы не спали и были красивыми.
AshleyDuh прокомментировал "Урок 3 - Конструкция IF...THEN...ELSE":
[img]https://kapsuly-lipocarnit.ru/files/lipocarnit_1/img/product-head1.png[/img] [url=https://kapsuly-lipocarnit.ru/][img]https://karga.info/wp-content/uploads/2019/02/orig.jpg[/img][/url] Липокарнит в Казани Аптека 24 г. [url=https://kapsuly-lipocarnit.ru/]липокарнит для похудения[/url] - Казань, ул. Энергетиков, 3, 7 (843) 205–57–99 Таттехмедфарм г. Казань, ул. Охранники, 31/42, 7 (843) 222–00–03 Сакура, аптека № 1 г. Казань, ул. Адоратского, 1а, 7 (843) 527–61–72 Приусадебный участок г. Казань, ул. Ричард Зорге, 57, 7 (843) 204–05–60 Вита Казань, ул. Декабристы, 131, 7 (843) 239–15–20 Аккуратная аптека Казань, Сибирский тракт, 22, 7 (843) 279–50–35 Последняя покупка: просто Сейчас 99 человек смотрят этот продукт Последняя покупка: просто Сейчас 99 человек смотрят этот продукт Приготовление натуральных ингредиентов Это не лекарство и пищевая добавка Доставка : от 99 руб. укажите оператор Платеж : наличные / карта при получении Липокарнит - правильный курс для естественной потери веса до 10 кг на курс Для 90% людей с великолепными формами похудение сравнимо с изощренными пытками инквизиции. Отказ от любимых блюд, строгий контроль аппетита, ежедневные изнурительные нагрузки и постоянное нервное напряжение до следующего взвешивания. До недавнего времени через него проходили все, кто осмелился избавиться от лишнего веса в виде жира на боку, животе, бедрах и других частях тела. Но такие методы помогают только 40% людей с избыточным весом, потому что очень часто причиной его набора является не недостаточная активность или переедание, а замедление метаболических процессов. Чтобы стать победителем в борьбе за гармонию, диетологи рекомендуют покупать Липокарнит - в Казани нет других средств для похудения, которые могут деликатно и безопасно разгонять обменные процессы и сжигать жировые отложения без потери здоровья. Что такое Липокарнит, состав продукта Препарат Липокарнит - это 100% органический продукт, состоящий из активных аминокислот, способствующих расщеплению жировых клеток. Выпускается в виде желатиновых капсул, внутри которых находится белый порошок. Их удобно принимать, а активные вещества всасываются в кишечнике, отвечают за всасывание органических аминокислот. Благодаря этому активные ингредиенты полностью усваиваются. В состав препарата входит: Липоевая кислота - это органическое вещество, участвующее в переработке глюкозы и других сахаров. При ее участии утилизируются метаболиты, потенциально опасные для клеток печени, а жировые ткани превращаются в энергию и воду.Липоевая кислота показана для использования профессиональными спортсменами для улучшения метаболических процессов и поддержания физической формы. Пиколинат хрома - органическое производное триптофана, способствует образованию мышечной массы и расщеплению жира. Полезным свойством соединения при похудении является ослабление аппетита. [img]https://kapsuly-lipocarnit.ru/files/lipocarnit_1/img/review-3.jpg[/img] L-карнитин - это органическая аминокислота, которая превращает жировую ткань в энергию и воду. Дополнительным полезным свойством этого вещества является снижение уровня холестерина в крови. Аминокислота подавляет всасывание жиров в кишечнике. Средство оказывает комплексное воздействие на организм: помогает уменьшить количество жира в организме и предотвращает его повторное накопление. Как работает [url=https://kapsuly-lipocarnit.ru/]липокарнит в аптеках казани[/url] Действие препарата сильно отличается от других препаратов для похудения. Препарат не создает чувства сытости, не изменяет процесс пищеварения, но в то же время помогает избавиться от жировых отложений. Это стало возможным благодаря уникальной способности Lipocarnitum перепрограммировать обмен энергии и обмен веществ в организме. Активные вещества сами по себе не влияют на жировые клетки. Они заставляют организм активизировать свои собственные ресурсы. Результат: разрушение мембран жировых клеток; Расщепление жира - энергия и вода высвобождаются; Энергия, получаемая от сжигания жира, направляется в жизненно важные органы. Эта короткая схема содержит естественный процесс, представленный природой, но по какой-то причине нарушенный. Возвращение в состояние, естественное для здорового организма, не проходит бесследно. На фоне снижения веса нормализуются артериальное давление, уровень глюкозы в крови и холестерина. Общее состояние организма улучшается, энергия увеличивается. При использовании Липокарнита нет необходимости менять привычки питания. Тренировки в тренажерном зале также необязательны. После недели приема препарата прилив энергии будет таким, что сам организм потребует повышенной активности. С курсом приема препарат не вызывает привыкания. Тело, настроившись на режим, необходимый для похудения, продолжает бороться с лишним весом самостоятельно. Эффект длится 60 дней. Как взять Несмотря на то, что Липокарнит не продается в аптеке в Казани, применение препарата следует проводить строго по инструкции. Нарушение описанных в нем правил потенциально опасно для здоровья. Липокарнит на завтрак и ужин принимайте по 1 или 2 капсуле в зависимости от исходного веса. Курс похудения длится 30 дней. За это время наблюдается потеря веса не менее 2 кг (при небольшом лишнем весе). У тучных людей с высокой степенью ожирения потеря веса достигает до 20 кг в месяц. При необходимости дальнейшего похудения курс повторяют через 60 дней, когда предыдущий теряет силу. Побочные эффекты и противопоказания При использовании в соответствии с инструкцией побочные эффекты после приема Липокарнита не возникают. Ему также не хватает серьезных противопоказаний. Препарат подходит для похудения у диабетиков и тех, кто испытал гормональные изменения. Единственная категория людей, которым противопоказано применение препарата - это беременные и кормящие женщины. В редких случаях после применения капсул индивидуальные реакции непереносимости возникают в виде: дискомфорт в кишечнике; сыпь на коже; n; [img]https://kapsuly-lipocarnit.ru/files/lipocarnit_1/img/review-2.jpg[/img] заложенность носа. При появлении симптоматических препаратов, назначенных лечащим врачом, это поможет. Купить Липокарнит Не рекомендуется приобретать капсулы для похудения данной марки в магазинах товаров для здоровья. Производитель не поставляет препарат в розничные сети. Вы можете заказать его только у официальных представителей в интернете.Это позволило гарантировать, что цена на Липокарнит в Казани соответствует заявленной производителем, поскольку нет торговых наценок. Кроме того, при покупке у дистрибьюторов, к которым относится Аптека-5, предоставляется 100% гарантия качества и подлинности товара. В Аптеке-5 вы можете заказать Липокарнит со скидкой, пока действует акция. Постоянным клиентам предоставляются дополнительные бонусы. Вы можете совершить покупку через корзину без регистрации или заказав обратный звонок менеджера. Инструкция по применению Прием препарата Липокарнит рекомендуется в течение 30 дней. Пить по 1 или 2 капсулы в день на завтрак и ужин. При необходимости курс повторяют через 2 месяца после окончания предыдущего.

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

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


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