Навигация
Главная
Поиск
Форум
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
Бип из системно... 63923
Организация зап... 60421
Invision Power ... 59999
Приложение «Про... 59873
Оператор выбора... 58814
Модуль Forms 58157
Подключение Mic... 57839
Создание отчето... 57589
ТЕХНОЛОГИИ ДОСТ... 53884
Программируемая... 52021
Пример работы с... 50048
Имитационное мо... 49320
21 ошибка прогр... 44211
Реклама
Сейчас на сайте
Гостей: 12
На сайте нет зарегистрированных пользователей

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

База данных студентов на Delphi (файл записей) + Блок схемы
Моделирование автомойки на GPSS + Отчет + Блок схемы
Моделирование процесса обработки заданий на вычислительном центре на GP...

Реклама



Подписывайся на 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 23:10:39 · 0 Комментариев · 5336 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Базы данных в Инт...
Delphi Быстрый Ст...
BIOS
Панель Наша Кнопка
AVIwriter
Java в примерах -...
DemoEdit [Исходни...
Шифрование по алг...
Советы от Даниилы...
Пример OpenGL гра...
SearchAndReplace
Tenis [Исходник н...
Calendar
GamesBase 3.0
Клавиатурный трен...
Электронный магаз...
Info
Domen Name IP
Редактор анимаций
Мод "register.php...

Топ загрузок
Приложение Клие... 100338
Delphi 7 Enterp... 80522
Converter AMR<-... 20029
Borland C++Buil... 10870
GPSS World Stud... 9955
Borland Delphi ... 7898
Turbo Pascal fo... 6925
Visual Studio 2... 4931
Калькулятор [Ис... 4177
FreeSMS v1.3.1 3492
Случайные статьи
Имейте достаточно ...
Квартир оценка
INCREMENT (УВЕЛИЧИТЬ)
Unit version mismatch
Ограничение распро...
Решения, по органи...
29юс20з Почтовый с...
Инсталляция библио...
Работа с избранным...
Matrix: операторы ...
2.2. АНТИПАТТЕРН: ...
СВОЙСТВА
на попытки сканиро...
Использование функ...
Процедура GETMEM. ...
Подпрограмма Input...
Выработка решенияП...
4.1. Порождение ...
Левое вращение при...
Создание в среде D...
Вложенные множества
Вывод элементарных...
Серверы, обеспечив...
Бюджетные цветные ...
Вопросы гидродина...
Статистика



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


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