Неупорядоченные списки

В некоторых приложениях может понадобиться удалять элементы из середины списка, добавляя при этом элементы в конец списка. В этом случае порядок расположения элементов может быть не важен, но при этом может быть необходимо удалять определенные элементы из списка. Списки такого типа называются неупорядоченными списками (unordered lists). Они также иногда называются «множеством элементов».[RP3]

Неупорядоченный список должен поддерживать следующие операции:

* добавление элемента к списку;

* удаление элемента из списка;

* определение наличия элемента в списке;

* выполнение каких‑либо операций (например, вывода на дисплей или принтер) для всех элементов списка.

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

Удаление из массива элемента при таком подходе может занять достаточно много времени, особенно если удаляется элемент в начале списка. Чтобы удалить первый элемент из массива с 1000 элементов, потребуется сдвинуть влево на одну позицию 999 элементов. Гораздо быстрее удалять элементы можно при помощи простой схемы чистки памяти (garbage collection)[RP4] .

Вместо удаления элементов из списка, пометьте их как неиспользуемые. Если элементы списка — данные простых типов, например целые, можно помечать элементы, используя определенное, так называемое «мусорное» значение (garbage value).

 

@Рисунок 2.1 Удаление элемента из середины массива

 

===========23

 

Для целых чисел можно использовать для этого значение ‑32.767. Для переменной типа Variant можно использовать значение NULL. Это значение присваивается каждому неиспользуемому элементу. Следующий фрагмент кода демонстрирует удаление элемента из подобного целочисленного списка:

 

Const GARBAGE_VALUE = -32767

 

‘ Пометить элемент как неиспользуемый.

Sub RemoveFromList(position As Long)

List(position) = GARBAGE_VALUE

End Sub

 

Если элементы списка — это структуры, определенные оператором Type, вы можете добавить к такой структуре новое поле IsGarbage. Когда элемент удаляется из списка, значение поля IsGarbage устанавливается в True.

 

Type MyData

Name As Sring            ‘ Данные.

IsGarbage As Integer     ‘ Этот элемент не используется?

End Type

 

‘ Пометить элемент, как не использующийся.

Sub RemoveFromList (position As Long)

List(position).IsGarbage = True

End Sub

 

Для простоты далее в этом разделе предполагается, что элементы данных являются данными универсального типа и их можно помечать значением NULL.

Теперь можно изменить другие процедуры, которые используют список, чтобы они пропускали помеченные элементы. Например, так можно модифицировать процедуру, которая печатает список:

 

‘ Печать элементов списка.

Sub PrintItems()

Dim I As Long

 

For I = 1 To ArraySize

   If Not IsNull(List(I)) [RP5] Then ‘ Если элемент не помечен

      Print Str$(List(I))     ‘ напечатать его.

   End If

Next I

End Sub

 

После использования в течение некоторого времени схемы пометки «мусора», список может оказаться полностью им заполнен. В конце концов, подпрограммы вроде этой процедуры больше времени будут тратить на пропуск ненужных элементов, чем на обработку настоящих данных.

 

=============24

 

Для того, чтобы избежать этого, можно периодически запускать процедуру очистки памяти (garbage collection routine). Эта процедура перемещает все непомеченные записи в начало массива. После этого можно добавить их к свободным элементам в конце массива. Когда потребуется добавить к массиву дополнительные элементы, их также можно будет использовать без изменения размера массива.

После добавления помеченных элементов к другим свободным ячейкам массива, полный объем свободного пространства может стать достаточно большим, и в этом случае можно уменьшить размер массива, освобождая память:

 

Private Sub CollectGarbage()

Dim i As Long

Dim good As Long

 

good = 1  ‘ Первый используемый элемент.

For i = 1 To m_NumItems

   ‘ Если он не помечен, переместить его на новое место.

   If Not IsNull(m_List(i)) Then

      m_List(good) = m_list(i)

      good = good + 1

   End If

Next i

 

‘ Последний используемый элемент.

m_NumItems(good) = good - 1

   

‘ Необходимо ли уменьшать размер списка?

If m_NumItems < m_ShrinkWhen Then ResizeList

End Sub

 

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

Можно выбирать разные моменты для запуска процедуры чистки памяти. Один из них — когда массив достигает определенного размера, например, когда список содержит 30000 элементов.

Этому методу присущи определенные недостатки. Во‑первых, он использует большой объем памяти. Если вы часто добавляете или удаляете элементы, «мусор» будет занимать довольно большую часть массива. При таком неэкономном расходовании памяти, программа может тратить время на свопинг, хотя список мог бы целиком помещаться в памяти при более частом переупорядочивании.

 

===========25

 

Во-вторых, если список начинает заполняться ненужными данными, процедуры, которые его используют, могут стать чрезвычайно неэффективными. Если в массиве из 30.000 элементов 25.000 не используются, подпрограмма типа описанной выше PrintItems, может выполняться ужасно медленно.

И, наконец, чистка памяти для очень большого массива может потребовать значительного времени, в особенности, если при обходе элементов массива программе приходится обращаться к страницам, выгруженным на диск. Это может приводить к «подвисанию» вашей программы на несколько секунд во время чистки памяти.

Чтобы решить эту проблему, можно создать новую переменную GarbageCount, в которой будет находиться число ненужных элементов в списке. Когда значительная часть памяти, занимаемой списком, содержит ненужные элементы, вы может начать процедуру «сборки мусора».

 

Dim GarbageCount As Long ‘ Число ненужных элементов.

Dim MaxGarbage As Long ‘ Это значение определяется в ResizeList.

 

‘ Пометить элемент как ненужный.

‘ Если «мусора» слишком много, начать чистку памяти.

Public Sub Remove(position As Long)

m_List(position) = Null

m_GarbageCount = m_GarbageCount + 1

 

‘ Если «мусора» слишком много, начать чистку памяти.

If m_GarbageCount > m_MaxGarbage Then CollectGarbage

End Sub

 

Программа Garbage демонстрирует этот метод чистки памяти. Она пишет рядом с неиспользуемыми элементами списка слово «unused», а рядом с помеченными как ненужные — слово «garbage». Программа использует класс GarbageList примерно так же, как программа SimList использовала класс SimpleList, но при этом она еще осуществляет «сборку мусора».

Чтобы добавить элемент к списку, введите его значение и нажмите на кнопку Add (Добавить). Для удаления элемента выделите его, а затем нажмите на кнопку Remove (Удалить). Если список содержит слишком много «мусора», программа начнет выполнять чистку памяти.

При каждом изменении размера списка объекта GarbageList, программа выводит окно сообщения, в котором приводится число используемых и свободных элементов в списке, а также значения переменных MaxGarbage и ShrinkWhen. Если удалить достаточное количество элементов, так что больше, чем MaxGarbage элементов будут помечены как ненужные, программа начнет выполнять чистку памяти. После ее окончания, программа уменьшает размер массива, если он содержит меньше, чем ShrinkWhen занятых элементов.

Если размер массива должен быть увеличен, программа Garbage добавляет к массиву еще 50 процентов пустых ячеек, и всегда оставляет хотя бы одну пустую ячейку при любом изменении размера массива. Эти значения были выбраны для упрощения работы пользователя со списком. В реальной программе процент свободной памяти должен быть меньше, а число свободных ячеек — больше. Оптимальными выглядят значения порядка 10 процентов и 10 свободных ячеек.

 

==========26

 

Связные списки

Другая стратегия используется при управлении связанными списками. Связанный список хранит элементы в структурах данных или объектах, которые называются ячейками (cells). Каждая ячейка содержит указатель на следующую ячейку в списке. Так как единственный тип указателей, которые поддерживает Visual Basic — это ссылки на объекты, то ячейки в связном списке должны быть объектами.

В классе, задающем ячейку, должна быть определена переменная NextCell, которая указывает на следующую ячейку в списке. В нем также должны быть определены переменные, содержащие данные, с которыми будет работать программа. Эти переменные могут быть объявлены как открытые (public) внутри класса, или класс может содержать процедуры для чтения и записи значений этих переменных. Например, в связном списке с записями о сотрудниках, в этих полях могут находиться имя сотрудника, номер социального страхования, название должности, и т.д. Определения для класса EmpCell могут выглядеть примерно так:

 

Public EmpName As String

Public SSN As String

Public JobTitle As String

Public NextCell As EmpCell

 

Программа создает новые ячейки при помощи оператора New, задает их значения и соединяет их, используя переменную NextCell.

Программа всегда должна сохранять ссылку на вершину списка. Для того, чтобы определить, где заканчивается список, программа должна установить значение NextCell для последнего элемента списка равным Nothing (ничего). Например, следующий фрагмент кода создает список, представляющий трех сотрудников:

 

Dim top_cell As EmpCell

Dim cell1 As EmpCell

Dim cell2 As EmpCell

Dim cell3 As EmpCell

 

‘ Создание ячеек.

Set cell1 = New EmpCell

cell1.EmpName = "Стивенс”

cell1.SSN = "123-45-6789"

cell1.JobTitle = "Автор"

 

Set cell2 = New EmpCell

cell2.EmpName = "Кэтс”

cell2.SSN = "123-45-6789"

cell2.JobTitle = "Юрист"

 

Set cell3 = New EmpCell

cell3.EmpName = "Туле”

cell3.SSN = "123-45-6789"

cell3.JobTitle = "Менеджер"

 

‘ Соединить ячейки, образуя связный список.

Set cell1.NextCell = cell2

Set cell2.NextCell = cell3

Set cell3.NextCell = Nothing

 

‘ Сохранить ссылку на вершину списка.

Set top_cell = cell1

 

 

===============27

 

На рис. 2.2 показано схематическое представление этого связного списка. Прямоугольники представляют ячейки, а стрелки — ссылки на объекты. Маленький перечеркнутый прямоугольник представляет значение Nothing, которое обозначает конец списка. Имейте в виду, что top_cell, cell1 и cell2 – это не настоящие объекты, а только ссылки, которые указывают на них.

Следующий код использует связный список, построенный при помощи предыдущего примера для печати имен сотрудников из списка. Переменная ptr используется в качестве указателя на элементы списка. Она первоначально указывает на вершину списка. В коде используется цикл Do для перемещения ptr по списку до тех пор, пока указатель не дойдет до конца списка. Во время каждого цикла, процедура печатает поле EmpName ячейки, на которую указывает ptr. Затем она увеличивает ptr, указывая на следующую ячейку в списке. В конце концов, ptr достигает конца списка и получает значение Nothing, и цикл Do останавливается.

 

Dim ptr As EmpCell

 

Set ptr = top_cell ‘ Начать с вершины списка.

Do While Not (ptr Is Nothing)

   ‘ Вывести поле EmpName этой ячейки.

   Debug.Print ptr.Empname

   ‘ Перейти к следующей ячейке в списке.

   Set ptr = ptr.NextCell

Loop

 

После выполнения кода вы получите следующий результат:

 

Стивенс

Кэтс

Туле

 

 

@Рис. 2.2. Связный список

 

=======28

 

Использование указателя на другой объект называется косвенной адресацией (indirection), поскольку вы используете указатель для косвенного манипулирования данными. Косвенная адресация может быть очень запутанной. Даже для простого расположения элементов, такого, как связный список, иногда трудно запомнить, на какой объект указывает каждая ссылка. В более сложных структурах данных, указатель может ссылаться на объект, содержащий другой указатель. Если есть несколько указателей и несколько уровней косвенной адресации, вы легко можете запутаться в них

Для того, чтобы облегчить понимание, в изложении используются иллюстрации, такие как рис. 2.2,(для сетевой версии исключены, т.к. они многократно увеличивают размер загружаемого файла) чтобы помочь вам наглядно представить ситуацию там, где это возможно. Многие из алгоритмов, которые используют указатели, можно легко проиллюстрировать подобными рисунками.