Фундаментальные основы VB. Списки: сортировка, поиск, удаление

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

В чем разница между списками? Она заключается в способах выделения памяти и способами их программирования. Например, коллекции создаются при помощи конструкций вида: Dim MyColl as New Collection, массивы при помощи Dim MyArray (10) as Long, списки можно организовывать при помощи оператора New создавая копии существующих объектов. Несмотря на различные способы формирования списков, все они, конечно, в чем-то схожи друг с другом. В практическом программирования все так же часто встречаются задачи работы с массивами и коллекциями. И коллекция, и массив в Visual Basic позволяют создавать динамические структуры данных, что делает применение этих средств весьма удобным на практике.

Что ж, приступим к более подробному рассмотрению массивов и коллекций.

Создание массива

Массив - это самый распространенный тип списков. Порядок элементов в массиве задается индексами его элементов. В VB (VBA) массивы могут быть одномерными и многомерными (в принципе, одномерный массив - это частный случай многомерного). Размерность массива может достигать 60. Это очень много. Не следует путать многомерность массива с количеством столбцов в нем.

Пример одномерного массива:

Пример двумерного (!) массива:

Пример трехмерного массива привести трудно, но его всегда можно представить в виде куба, например, Таким образом, данные с которыми чаще всего имеем дело - это одномерные и двумерные массивы. В Excel вы чаще всего видите двумерный массив. Известно, что данные на листе Exсel могут иметь связи с другими листами или даже книгами, здесь уже можно говорить и от трехмерном массиве (хотя это и не всегда так).

В общем случае синтаксис объявления массива такой:

{Dim Private | Public | Static} имя_переменной (список_размерностей) _
[As имя_типа]

Например,

Dim Spisok (10) As Long

Dim Spisok (10, 25) As Long

Dim Spisok (1 To 10, 5 to 50) As String

Вы можете не указывать начальную границу массива и тогда VB будет руководствоваться директивой Option Base. Ее не рекомендуется использовать и всегда следует указывать нижнюю границу, как это сделано в последнем примере. Если вам не нравиться указывать нижнюю границу, то определитесь раз и навсегда - с нуля или единицы будет считаться индекс массива.

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

Динамическим массивом является тот массив, при объявлении которого размерность не указывается, но она определяется (или переопределяется) в дальнейшем (в процессе работы программы). Для определения (переопределения) размерности массива используется оператор ReDim.

Пример.

Определяем динамический массив:

Public Sendor() As Integer
В данном случае, размер массива Sendor не определен, и это всегда можно сделать в процессе работы программы.

Dim Listing() As String ' Список элементов.
Dim NumInList As Integer ' Число элементов в списке.

Sub AddToList(value As String)
' Увеличить размер массива.
NumCountArray = NumCountArray + 1
ReDim Preserve Listing (1 To NumCountArray)

' Добавить новый элемент к концу списка.
Listing (NumCountArray) = value
End Sub

Sub RemoveFromList()
' Уменьшить размер массива, освобождая память.
NumCountArray = NumCountArray - 1
ReDim Preserve Listing (1 To NumCountArray)
End Sub

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

ReDim Listing (0)

Будьте внимательны и не используйте оператор ReDim внутри цикла. Это приведет к резкому снижению производительности.

For I =1 To 255
ReDim Listing (I)
Next I

Создание коллекции

Коллекция - это упорядоченная совокупность элементов разного типа. Именно этот факт, коллекция не накладывает ограничение на содержимое и является главным ее преимуществом перед массивами. Однако этим дело не заканчивается.

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

Так объявляется новая коллекция:

Dim RabCollect As New Collection
Работаем с элементами коллекции:

With RabCollect

MsgBox .Count 'показать на экране количество элементов

.Add "Петров" 'добавить запись - в такой виде добавляется всегда конец списка
.Add "Иванов", "рабочий" 'добавить запись, с ключом "рабочий"
.Add "Cидоров", "служ", 2 'добавить запись, с ключом "служ", перед второй записью

.Remove 1 'удаление первого элемента
.Remove "служ" 'удаление элемента по ключу

MsgBox .Item(1) 'печать первого элемента
'как вы догадались это будет Иванов.

End With

Реальная скорость выполнения алгоритмов

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

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

Другой критерий производительности заключается в использовании оперативной памяти компьютера. До тех пор, пока Windows легко помещает все данные списка в ОЗУ производительность алгоритма будет наибольшей. Но ситуация такова, что если весь список не уменьшается в памяти компьютера, то Windows начнет активно использовать файл подкачки. В таком случае, каким бы быстрым не был ваш жесткий диск, производительность упадет очень резко. Решение проблемы заключается в том, чтобы писать эффективные алгоритмы и вовремя очищать память, данные которой уже не требуются. Это легче сказать, чем сделать. О оптимизации программ можно написать много книг.

Сортировка выбором

Сортировка выбором (selectionsort) - простой алгоритм. Идея состоит в поиске наименьшего элемента в списке, который затем меняется местами с элементом на вершине списка. Затем находится наименьший элемент из оставшихся, и меняется местами со вторым элементом. Процесс продолжается до тех пор, пока все элементы не займут свое конечное положение.

Public Sub Selectionsort(List() As Long, min As Long, max As Long)
'здесь List() - массив, который передается в процедуру обработки
'min - минимальное значение индекса
'max - максимальное значение индекса

Dim i As Long
Dim j As Long
Dim b_val As Long
Dim b_j As Long

For i = min To max - 1
' Найти наименьший элемент из оставшихся.
b_val = List(i)
b_j = i
For j = i + 1 To max
If List(j) < b_val Then
b_val = List(j)
b_j = j
End If
Next j

' Поместить элемент на место.
List(b_j) = List(i)
List(i) = b_val
Next i
End Sub

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

Если первоначально список отсортирован в обратном порядке, условие list(j) < b_val выполняется большую часть времени. Например, при первом проходе оно будет истинно для всех элементов, поскольку каждый элемент меньше предыдущего. Алгоритм будет многократно выполнять строки с оператором If, что приведет к некоторому замедлению работы алгоритма.

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

Чтобы отсортировать список в другом порядке замените строку:

If List(j) < b_val Then
на строку: 

If List(j) > b_val Then
Быстрая сортировка

Быстрая сортировка (quicksort) - рекурсивный алгоритм, который использует подход "разделяй и властвуй". Если сортируемый список больше, чем минимальный заданный размер, процедура быстрой сортировки разбивает его на два подсписка, а затем рекурсивно вызывает себя для сортировки двух подсписков. Можно улучшить производительность быстрой сортировки, если прекратить рекурсию до того, как подсписки уменьшатся до нуля, и использовать для завершения работы сортировку выбором.

Public Sub QuickSort (List() As Long, ByVal min As Long, ByVal max As Long)
Dim m_v As Long
Dim hi As Long
Dim lo As Long
Dim i As Long

' Если в списке менее 500 элементов,
' завершить его сортировку процедурой SelectionSort.
If max - min < 500 Then
SelectionSort List(), min, max
Exit Sub
End If

'Собственно, сортировка
' Выбрать разделяющее значение.
i = Int((max - min + 1) * Rnd + min)
m_v = List(i)

' Переместить его вперед.
List(i) = List(min)

lo = min
hi = max
Do
' Просмотр сверху вниз от hi до значения < m_v.
Do While List(hi) >= m_v
hi = hi - 1
If hi <= lo Then Exit Do
Loop
If hi <= lo Then
List(lo) = m_v
Exit Do
End If

' Поменять местами значения lo и hi.
List(lo) = List(hi)

' Просмотр снизу вверх от lo до значения >= m_v.
lo = lo + 1
Do While List(lo) < m_v
lo = lo + 1
If lo >= hi Then Exit Do
Loop
If lo >= hi Then
lo = hi
List(hi) = m_v
Exit Do
End If

' Поменять местами значения lo и hi.
List(hi) = List(lo)
Loop

' Сортировать два подсписка.
QuickSort List(), min, lo - 1
QuickSort List(), lo + 1, max
End Sub

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

Для обратной сортировки используйте следующий код. Вместо строки

Do While List(hi) >= m_v
вставьте

Do While List(hi) < m_v
Вместо строки

Do While List(lo) < m_v
вставьте

Do While List(lo) >= m_v
В подавляющем большинстве задач вы можете смело выбрать быструю сортировку. Это обеспечит достойную производительность.

Сортировка подсчетом

Сортировка подсчетом (countingsort) - специализированный алгоритм, который очень хорошо работает, если элементы данных - целые числа, значения которых находятся в относительно узком диапазоне. Этот алгоритм работает достаточно быстро, например, если значения находятся между 1 и 1000.

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

Public Sub Countingsort(List() As Long, sorted_list() As Long, Counts() As Long, _
ByVal min As Long, ByVal max As Long, _
ByVal min_value As Long, ByVal max_value As Long)

Dim i As Long
Dim j As Long
Dim k As Long
Dim new_index As Long

For i = min_value To max_value
Counts(i) = 0
Next i

For i = min To max
Counts(List(i)) = Counts(List(i)) + 1
Next i

new_index = min
For i = min_value To max_value
For j = 1 To Counts(i)
sorted_list(new_index) = i
new_index = new_index + 1
Next j
Next i
End Sub

Сортировка подсчетом опирается на тот факт, что значения данных - целые числа, поэтому этот алгоритм не может просто сортировать данные других типов. В Visual Basic нельзя создать массив с границами от A до Z. Проще всего для сортировки строковых значений использовать другие виду сортировки (быстрая, выбором).

Резюме

Естественно, здесь рассмотрены далеко не все способы сортировки. Их гораздо больше, но я лишь привел три варианта. Почему? Потому что сортировка выбором используется тогда, когда следует отсортировать короткие списки, независимо от того, строки или числа содержатся в массиве. Результат будет одинаково хорош. Часто этот способ можно использовать при сортировки содержимого ListBox. И даже если учесть, что повторная сортировка в обратом порядке будет крайне неэффективна, все же такой подход вполне оправдан.

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

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

Поиск

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

Поиск методом перебора

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

Public Function LinearSearch(target As Long) As Long
Dim i As Long

For i = 1 To NumItems
If List(i) >= target Then Exit For
Next i

If i > NumItems Then
Search = 0 ' Элемент не найден.
Else
Search = i ' Элемент найден.
End If
End Function

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

Поиск в упорядоченных списках

И все же всегда есть смысл присмотреться к более эффективному алгоритму.

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

Следующий код демонстрирует новую версию алгоритма поиска полным перебором:

Public Function LinearSearch(target As Long) As Long
Dim i As Long

NumSearches = 0

For i = 1 To NumItems
NumSearches = NumSearches + 1
If List(i) >= target Then Exit For
Next i

If i > NumItems Then
LinearSearch = 0 ' Элемент не найден.
ElseIf List(i) target Then
LinearSearch = 0 ' Элемент не найден.
Else
LinearSearch = i ' Элемент найден.
End If
End Function

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

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

Двоичный поиск

Как уже упоминалось в предыдущих разделах, поиск полным перебором выполняется очень быстро для небольших списков, но для больших списков намного быстрее выполняется двоичный поиск. Алгоритм двоичного поиска (binary search) сравнивает элемент в середине списка с искомым. Если искомый элемент меньше, чем найденный, то алгоритм продолжает поиск в первой половине списка, если больше - в правой половине.

Хотя по своей природе этот алгоритм является рекурсивным, его достаточно просто записать и без применения рекурсии.

Следующий код демонстрирует выполнение двоичного поиска:

Public Function BinarySearch(target As Long) As Long
Dim min As Long
Dim max As Long
Dim middle As Long

NumSearches = 0

' Во время поиска индекс искомого элемента будет находиться
' между Min и Max: Min <= target index <= Max
min = 1
max = NumItems
Do While min <= max
NumSearches = NumSearches + 1

middle = (max + min) / 2
If target = List(middle) Then ' Мы нашли искомый элемент!
BinarySearch = middle
Exit Function
ElseIf target < List(middle) Then ' Поиск в левой половине.
max = middle - 1
Else ' Поиск в правой половине.
min = middle + 1
End If
Loop

' Если мы оказались здесь, то искомого элемента нет в списке.
BinarySearch = 0
End Function

Возвращаясь к коллекциям, приведу ниже код, где поиск происходит по коллекции, и найденный элемент удаляется из списка (коллекции).

Public Function BinarySearch(ByVal Target As Long, ByVal numitems As Long) As Long
Dim min As Long
Dim max As Long
Dim middle As Long
Dim NumSearches As Long

NumSearches = 0
min = 1
max = numitems
Do While min <= max
DoEvents
NumSearches = NumSearches + 1
middle = (max + min) / 2
If Str(Target) = SpisokCollection(middle) Then 
BinarySearch = middle
SpisokCollection.Remove (middle) 'удаление элемента, если он найден
Exit Function
ElseIf Str(Target) > SpisokCollection(middle) Then 
max = middle - 1
Else 
min = middle + 1
End If
Loop

BinarySearch = 0
End Function

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

Удаление элементов из списка

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

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

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

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

Const GARBAGE_VALUE = -32767

' Пометить элемент как неиспользуемый.
Sub RemoveFromList(position As Long)
List(position) = GARBAGE_VALUE
End Sub

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

' Печать элементов списка.
Sub PrintItems()
Dim I As Long

For I = 1 To ArraySize
If List(I)-32767 then ' Если элемент не помечен
Print Str$(List(I)) ' напечатать его.
End If
Next I
End Sub

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

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

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

Private Sub CollectGarbage()
Dim i As Long
Dim good As Long

good = 1 ' Первый используемый элемент.
For i = 1 To m_NumItems
' Если он не помечен, переместить его на новое место.
If List(I)-32767 then 
List(good) = list(i)
good = good + 1
End If
Next i

' Последний используемый элемент.
NumItems(good) = good - 1

' Необходимо ли уменьшать размер списка?
If m_NumItems < m_ShrinkWhen Then ResizeList
End Sub

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

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

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

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

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

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

Dim GarbageCount As Long ' Число ненужных элементов.
Dim MaxGarbage As Long ' Это значение определяется в ResizeList.

' Пометить элемент как ненужный.
' Если "мусора" слишком много, начать чистку памяти.
Public Sub Remove(position As Long)
m_List(position) = -32767
m_GarbageCount = m_GarbageCount + 1

' Если "мусора" слишком много, начать чистку памяти.
If m_GarbageCount > m_MaxGarbage Then CollectGarbage
End Sub

Резюме

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

Источник: http://relib.com/

16.02.2006