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

Оператор 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

 

Класс SimpleList

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

Классы Visual Basic могут сильно облегчить выполнение этой задачи. Класс SimpleList инкапсулирует эту структуру списка, упрощая управление списками. В этом классе присутствуют методы Add и Remove для использования в основной программе. В нем также есть процедуры извлечения свойств NumItems и ArraySize, с помощью которых программа может определить число элементов в списке и объем занимаемой им памяти.

Процедура ResizeList объявлена как частная внутри класса SimpleList. Это скрывает изменение размера списка от основной программы, поскольку этот код должен использоваться только внутри класса.

Используя класс SimpleList, легко создать в приложении несколько списков. Для того чтобы создать новый объект для каждого списка, просто используется оператор New. Каждый из объектов имеет свои переменные, поэтому каждый из них может управлять отдельным списком:

 

Dim List1 As New SimpleList

Dim List2 As New SimpleList

 

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

 

=============22

 

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