Неупорядоченный список должен поддерживать следующие операции:
а добавление элемента к списку;
о удаление элемента из списка;
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 свободных ячеек. |
Главная
Каталог файлов
