Простые списки

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

Многие программы используют списки, которые растут или уменьшаются со временем. Можно создать массив, соответствующий максимально возможному размеру списка, но такое решение не всегда будет оптимальным. Не всегда можно заранее знать, насколько большим может стать список, кроме того, вероятность, что список станет очень большим, может быть невелика, и созданный массив гигантских размеров может большую часть времени лишь понапрасну занимать память.

Коллекции

Программа может использовать коллекции Visual Basic для хранения списка переменного размера. Метод Add Item добавляет элемент в коллекцию. Метод Remove удаляет элемент. Следующий фрагмент кода демонстрирует программу, которая добавляет три элемента к коллекции и затем удаляет второй элемент.

Dim list As New Collection

Dim obj As MyClass

Dim I As Integer

‘ Создать и добавить 1 элемент.

Set obj = New MyClass

list.Add obj

‘ Добавить целое число.

i = 13

list.Add I

‘ Добавить строку.

list.Add "Работа с коллекциями"

‘ Удалить 2 элемент (целое число).

list.Remove 2

===============18

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

Тем не менее, коллекциям свойственны и определенные недостатки. Для больших списков, коллекции могут работать медленнее, чем массивы. Если в вашей программе не нужны все свойства, предоставляемые коллекцией, более быстрым может быть использование простого массива.

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

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

Список переменного размера

Оператор Visual Basic ReDim позволяет изменять размер массива. Вы можете использовать это свойство для построения простого списка переменного размера. Начните с объявления безразмерного массива для хранения элементов списка. Также определите переменную NumInList для отслеживания числа элементов в списке. При добавлении элементов к списку используйте оператор ReDim для увеличения размера массива, чтобы новый элемент мог поместиться в нем. При удалении элемента также используйте оператор ReDim для уменьшения массива и освобождения ненужной больше памяти.

Dim List() As String ‘ Список элементов.

Dim NumInList As Integer ‘ Число элементов в списке.

Sub AddToList(value As String)

‘ Увеличить размер массива.

NumInList = NumInList + 1

ReDim Preserve List (1 To NumInList)

‘ Добавить новый элемент к концу списка.

List(NumInList) = value

End Sub

Sub RemoveFromList()

‘ Уменьшить размер массива, освобождая память.

NumInList = NumInList – 1

ReDim Preserve List (1 To NumInList)

End Sub

==================19

Эта простая схема неплохо работает для небольших списков, но у нее есть пара недостатков. Во-первых, приходится часто менять размер массива. Для создания списка из 1000 элементов, придется 1000 раз изменять размер массива. Хуже того, при увеличении размера списка, на изменение его размера потребуется больше времени, поскольку придется каждый раз копировать растущий список в памяти.

Для уменьшения частоты изменений размера массива, можно добавлять дополнительные элементы к массиву при увеличении его размера, например, по 10 элементов вместо одного. При этом, когда вы будете добавлять новые элементы к списку в будущем, массив уже будет содержать неиспользуемые ячейки, в которые вы сможете поместить новые элементы без увеличения размера массива. Новое увеличение размера массива потребуется, только когда пустые ячейки закончатся.

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

Заметим, что максимальное число неиспользуемых ячеек (20) должно быть больше, чем минимальное число (10). Это уменьшает число изменений размера массива при удалении или добавлении его элементов.

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

Dim List() As String ‘ Список элементов.

Dim ArraySize As Integer ‘ Размер массива.

Dim NumInList As Integer ‘ Число используемых элементов.

‘ Если массив заполнен, увеличить его размер, добавив 10 ячеек.

‘ Затем добавить новый элемент в конец списка.

Sub AddToList(value As String)

NumInList = NumInList + 1

If NumInList > ArraySize Then

ArraySize = ArraySize + 10

ReDim Preserve List(1 To ArraySize)

End If

List(NumInList) = value

End Sub

‘ Удалить последний элемент из списка. Если осталось больше

‘ 20 пустых ячеек, уменьшить список, освобождая память.

Sub RemoveFromList()

NumInList = NumInList – 1

If ArraySize – NumInList > 20 Then

ArraySize = ArraySize –10

ReDim Preserve List(1 To ArraySize)

End If

End Sub

=============20

Для очень больших массивов это решение может также оказаться не самым лучшим. Если вам нужен список, содержащий 1000 элементов, к которому обычно добавляется по 100 элементов, то все еще слишком много времени будет тратиться на изменение размера массива. Очевидной стратегией в этом случае было бы увеличение приращения размера массива с 10 до 100 или более ячеек. Тогда можно было бы добавлять по 100 элементов одновременно без частого изменения размера списка.

Более гибким решением будет изменение приращения в зависимости от размера массива. Для небольших списков это приращение было бы также небольшим. Хотя изменения размера массива происходили бы чаще, они потребовали бы относительно немного времени для небольших массивов. Для больших списков, приращение размера будет больше, поэтому их размер будет изменяться реже.

Следующая программа пытается поддерживать примерно 10 процентов списка свободным. Когда массив заполняется, его размер увеличивается на 10 процентов. Если свободное пространство составляет более 20 процентов от размера массива, программа уменьшает его.

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

Const WANT_FREE_PERCENT = .1 ‘ 10% свободного места.

Const MIN_FREE = 10 ‘ Минимальное число пустых ячеек.

Global List() As String ‘ Массив элементов списка.

Global ArraySize As Integer ‘ Размер массива.

Global NumItems As Integer ‘ Число элементов в списке.

Global ShrinkWhen As Integer ‘ Уменьшить размер, если NumItems < ShrinkWhen.

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

‘ Затем добавить новый элемент в конец списка.

Sub Add(value As String)

NumItems = NumItems + 1

If NumItems > ArraySize Then ResizeList

List(NumItems) = value

End Sub

‘ Удалить последний элемент из списка.

‘ Если в массиве много пустых ячеек, уменьшить его размер.

Sub RemoveLast()

NumItems = NumItems – 1

If NumItems < ShrinkWhen Then ResizeList

End Sub

‘ Увеличить размер массива, чтобы 10% ячеек были свободны.

Sub ResizeList()

Dim want_free As Integer

want_free = WANT_FREE_PERCENT * NumItems

If want_free < MIN_FREE Then want_free = MIN_FREE

ArraySize = NumItems + want_free

ReDim Preserve List(1 To ArraySize)

‘ Уменьшить размер массива, если NumItems < ShrinkWhen.

ShrinkWhen = NumItems – want_free

End Sub

===============21