Навигация
Главная
Поиск
Форум
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
Invision Power ... 65535
Содержание сайт... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Организация зап... 65282
Создание отчето... 61741
Модуль Forms 61629
ТЕХНОЛОГИИ ДОСТ... 58193
Пример работы с... 55819
Имитационное мо... 53550
Реклама
Сейчас на сайте
Гостей: 7
На сайте нет зарегистрированных пользователей

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

Моделирование процесса передачи данных по магистрали с основным и резерв...
Файл записей с выводом обратного заголовка на Turbo Pascal
Обучающая и тестирующая программа по здаче экзамена ПДД на Turbo Pascal ...

Реклама



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

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
StartMark
FormShape [Исходн...
Книга по Delphi (...
PHP 5 в подлинник...
PHP 5
Adapter (пример D...
Delphi на примерах
PolyFlow
Delphi 2005. Разр...
IpEditAdress
Эффект лампы на р...
CoolHints2k v1.03
Java в примерах -...
Rotolabel
Самоучитель PHP 5...
Файловый менеджер
Редактор анимаций
Tenis [Исходник н...
Swing. Эффектные...
Ehlib

Топ загрузок
Приложение Клие... 100399
Delphi 7 Enterp... 84036
Converter AMR<-... 20052
GPSS World Stud... 11499
Borland C++Buil... 11298
Borland Delphi ... 8251
Turbo Pascal fo... 6994
Visual Studio 2... 4975
Калькулятор [Ис... 4499
FreeSMS v1.3.1 3517
Случайные статьи
Сегменты, использу...
IPSecПри работе пр...
Коммутаторы локаль...
Тестирование: конс...
Варианты ошибок с ...
Модификация программы
Датчики давления
Сообщения имеют сл...
может быть установ...
Выбор разрешения э...
Использование карк...
3.1. Обработка шаб...
Тематические интер...
Режим Ночной портр...
Вычислительные модели
Асбестоцементные т...
Разработка сайта п...
Строки в стиле язы...
Очереди
Звуковая карта
Что означает равен...
Графические редакт...
Теперь давайте пос...
Листинг 2.18
Географические диа...
Статистика



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


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