Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Содержание сайт... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Invision Power ... 65285
Организация зап... 63935
Модуль Forms 60855
Создание отчето... 60713
ТЕХНОЛОГИИ ДОСТ... 57039
Создание потоко... 56372
Пример работы с... 54270
Имитационное мо... 52480
Реклама
Сейчас на сайте
Гостей: 15
На сайте нет зарегистрированных пользователей

Пользователей: 13,065
новичок: railval
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование работы узла коммутации сообщений на GPSS + Пояснительная з...
Моделирование интернет кафе на GPSS + Отчет
Моделирование ЭВМ на GPSS (три класса заданий) + Пояснительная записка

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Неупорядоченные списки
Неупорядоченный список должен поддерживать следующие операции:
а добавление элемента к списку;
о удаление элемента из списка;
Q определение наличия элемента в списке;
а выполнение каких-либо операций (например, печати или вывода не дис-
плей) для всех элементов списка.
Для управления подобным списком вы можете изменить простую схему, пред-
ставленную в предыдущем разделе. Когда удаляется элемент из середины списка,
оставшиеся элементы сдвигаются на одну позицию, запол-
няя образовавшийся промежуток. Это показано на рис. 2.1,
где из списка удаляется второй элемент, а третий, четвер-
тый и пятый элементы сдвигаются влево, занимая свобод-
ный участок.
Удаление элемента массива подобным способом может за-
нимать много времени, особенно если этот элемент находит-
ся в начале списка. Чтобы удалить первый элемент массива,
содержащего 1000 записей, необходимо сдвинуть 999 элементов на одну позицию
влево. Гораздо быстрее удалять элементы при помощи простой схемы сборки мусора.
Вместо удаления элементов из списка отметьте их как неиспользуемые. Если
элементы списка - данные простых типов, например целочисленные, то можно
маркировать их с помощью так называемого «мусорное» значения. Для целых чи-
сел можно использовать значение -32767. Вы присваиваете это значение любому
неиспользуемому элементу. Следующий фрагмент кода показывает, как можно
•удалить элемент из подобного целочисленного списка.

const
GARBAGE_VALUE=-32767;
// Пометка элемента как ненужного.
procedure RemoveFromList(position : Integer);
begin
List^[position] := GARBAGE_VALUE ;
end;



И соответственно для динамических массивов:
const
GARBAGE_VALUE=-32767;
// Пометка элемента как ненужного.
procedure RemoveFromList(position : Integer);
begin
List[position] := GARBAGE_VALUE ;
end;




Если элементы списка - это структуры, определенные оператором Туре, то
можно добавить к ним новое поле IsGarbage. При удалении элемента из списка
значение поля IsGarbage устанавливается в True.

type
MyRecord = record
Name : String[20]; // Данные.
IsGarbage : Boolean; // Является ли элемент ненужным?
end;
// Пометка элемента как 'ненужного.
procedure RemoveFromList(position : Integers);
begin
List^[position].IsGarbage := true;
end;

И соответственно для динамических массивов:

type
MyRecord = record
Name : String[20]; // Данные.
IsGarbage : Boolean; // Является ли элемент ненужным?
end;
var
List : Array Of MyRecord;
// Пометка элемента как ненужного.
procedure RemoveFromList(position : Integers);
begin
List[position].IsGarbage := true;
end;




Для упрощения примера далее в этом разделе предполагается, что все эле-
менты имеют целочисленный тип данных и их можно помечать «мусорным» зна-
чением.
Теперь необходимо изменить другие процедуры, использующие список, чтобы
они пропускали маркированные элементы. Например, так можно модифицировать
процедуру, отображающую элементы списка:
// Отображение элементов списка.
procedure Showlt ems;
var
i : Integer;
begin
For i := 1 to Numltems do
if (Lisf4 [i]<>GARBAGE_VALUE) then // Если элемент значащий.
ShowMessagedntToStr (List" [i]) ) ; // Печать этого элемента.
end;



И соответственно для динамических массивов:
// Отображение элементов списка.
procedure Showltems;
var
i : Integer;
begin
For i := Low(List) to High(List) do
if (List [i] <>GARBAGE_VALUE) then // Если элемент значащий.
ShowMessagedntToStr (List [ i ] ) ) ; // Печать этого Элемента.
end;



Через некоторое время список может переполниться «мусором». В результате
процедуры, подобные приведенной выше, больше времени будут тратить на про-
пуск ненужных элементов, чем на обработку реальных данных.
Во избежание такой ситуации надо периодически выполнять процедуру сбор-
ки мусора (garbage collection routine). Эта процедура перемещает все непомечен-
ные элементы в начало массива. После этого они добавляются к неиспользуемым
элементам в конце массива. Когда вам потребуется включить в список дополни-
тельные элементы, можно повторно использовать помеченные ячейки без измене-
ния размера массива.
После добавления дополнительных неиспользуемых записей к другим свобод-
ным ячейкам полный объем свободного пространства может стать слишком боль-
шим. В этом случае следует уменьшить размер массива, чтобы освободив память
(для динамических массивов Delphi 4 код будет практически идентичным):
procedure CollectGarbage;
var
i, good : Longint;
begin
good := 1; //На это место ставится первый значащий элемент.
for i := 1 to NumIterns do
begin
// Если элемент значащий, то он перемещается на новую позицию.
if (not (ListA[i]=GARBAGE_VALUE)) then
begin
if (goodoi) then
ListA[good] := ListA[i];
Good := good+1;
end;
end;
// Позиция, где находится последний значащий элемент.
Numltems := good-1;
end;




Когда выполняется процедура сборки мусора, используемые элементы пере-
мещаются из конца списка в начало, заполняя пространство, которое занимали
помеченные элементы. Это означает, что позиции элементов в списке могут изме-
ниться во время этой операции. Если другие части программы обращаются к эле-
ментам списка по их исходным позициям, то необходимо модифицировать про-
цедуру сборки мусора так, чтобы она обновляла ссылки на положение элементов
в списке. Подобные преобразования достаточно сложны и затрудняют сопровож-
дение программ.

Существует несколько этапов в работе приложения, когда стоит выполнить
подобную чистку памяти. Один из них - когда массив достигнет определенного
размера, например, когда список содержит 30 000 записей.
Этому методу присущи некоторые недостатки. Во-первых, он требует большо-
го объема памяти. Если вы часто добавляете или удаляете элементы, то «мусор»
заполнит большую часть массива. Такое неэкономное расходование памяти может
привести к процессу подкачки, особенно если список не помещается полностью
в оперативной памяти. Это будет занимать, в свою очередь, больше времени при
перестройке массива.
Во-вторых, если список начинает заполняться ненужными данными, процеду-
ры, использующие его, станут очень неэффективными. Если в массиве из 30 000
элементов 25 000 не используются, то процедуры, подобные описанной ранее про-
цедуре Showltems, будут выполняться слишком медленно.
И наконец, сборка мусора в очень большом массиве может занимать значитель-
ное время, особенно если сканирование массива заставляет программу обращать-
ся к файлам подкачки. Это может вызвать остановку программы на несколько се-
кунд, пока не очистится память.
Чтобы решить подобную проблему, достаточно создать новую переменную
GarbageCount для отслеживания числа неиспользуемых элементов в списке. Ког-
да не используется существенная доля памяти списка, можно начать «сборку му-
сора». В следующем фрагменте кода переменная MaxGarbage сохраняет макси-
мальное число неиспользуемых записей, которые может содержать список:

// Удаление элемента из списка.
procedure Remove(index:Longint);
begin
ListA[index] := GARBAGE_VALUE ;
NumGarbage := NumGarbage+1;
if (NumGarbage>MaxGarbage) then CollectGarbage;
end;




Программа Garbage демонстрирует метод сборки мусора. Она отображает не-
используемые элементы списка как , а записи, помеченные как му-
сор - . Используемый программой класс TGarbageList аналоги-
чен классу TSimpleLi st, используемому программой SimList, но дополнительно
выполняет «сборку мусора».
Чтобы добавить элемент к списку, введите значение и нажмите кнопку Add. Для
удаления элемента выделите его, а затем нажмите кнопку Remove. Если список со-
держит слишком много «мусора», программа начнет выполнять чистку памяти.
Когда объект TGarbageList изменяет размер списка, программа выводит
окно сообщений, в котором приводится количество используемых и неиспользуе-
мых элементов списка и значения переменных MaxGarbage и ShrinkWhen. Если
удалить довольно много элементов и их количество превысит значение перемен-
ной MaxGarbage, то программа начинает «сборку мусора». Как только этот про-
цесс заканчивается, программа уменьшает размер массива, чтобы он содержал
меньшее, чем значение ShrinkWhen, число элементов.

Программа Garbage при изменении размера массива добавляет еще 50% пус-
тых ячеек и всегда оставляет как минимум одну свободную ячейку при любом из-
менении размера. Эти значения были выбраны для упрощения работы пользова-
теля со списком. В реальной программе процент свободной памяти должен быть
меньше, и минимальное число свободных элементов - больше. Оптимальными
являются значения порядка 10% текущего размера списка и 10 свободных ячеек.
Опубликовал Kest September 13 2009 22:10:39 · 0 Комментариев · 5674 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
База англоязычных...
Tag Игра "Пятнашк...
Java в примерах -...
Delphi 2005. Разр...
Bitmap [для кнопок]
Шаблон для новост...
Игра Car [Исходни...
Программа рисует ...
Пользовательская...
Еext Editor
XPATComponents
ShadelLabel
Delphi. Учимся на...
SMExport
45 уроков по дельфи
Пишем программы и...
TelBook
Работа с матрицами
Добавление басса ...
PDJPack

Топ загрузок
Приложение Клие... 100376
Delphi 7 Enterp... 83084
Converter AMR<-... 20046
Borland C++Buil... 11177
GPSS World Stud... 10901
Borland Delphi ... 8124
Turbo Pascal fo... 6973
Visual Studio 2... 4963
Калькулятор [Ис... 4358
FreeSMS v1.3.1 3510
Случайные статьи
Определение абстра...
Игры. Безопасность...
Практическая реали...
Массивы
Построение активно...
Межкомнатные двери...
No inherited metho...
Экскурсии из Праги...
Ламбда-подъем при ...
Инструменты для по...
Рехеширование – сл...
Web Proxy
Реализация модели ...
Охранная сигнализа...
Регистрация нового...
13.5. Принципы
Взаимодействия кла...
Интерфейс модели в...
Какие из следующих...
Операторы прерыван...
Подбор плитки в кухню
Метод обратного ра...
Раскрутка блога в ...
Несколько мелких х...
Unit version mismatch
Статистика



Друзья сайта
Программы, игры


  • Подбор кредита калькулятор кредита credit-online.ws
  • credit-online.ws
Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?