Как известно, в Visual Basic 6 для хранения наборов данных применяются массивы и объекты Collection. И при работе с наборами данных программисты довольно часто сталкиваются с некоторыми проблемами. Например, приходится создавать свои алгоритмы поиска и сортировки элементов, хотя программисты Microsoft могли создать встроенные механизмы. Да и удобством использования массивы и коллекции VB 6 едва ли могут похвастаться.

Но с выходом на сцену новой платформы Microsoft .NET все меняется к лучшему. Я был приятно впечатлен, когда ознакомился с огромными возможностями .NET Framework в области работы с наборами данных.

Существенно увеличилась функциональность массивов. О них будет подробнее рассказано ниже. А вместо единственного класса Collection, доступного в VB 6, в .NET вы можете использовать 6 различных видов коллекций, каждая из которых «заточена» под свои цели. Эти 6 классов выделены в отдельное пространство имен System.Collections.

Массивы

Должно быть, вы знаете, что все типы данных в .NET являются объектами. Например, когда вы создаете переменную типа Integer, на самом деле создается экземпляр класса System.Integer. Это касается и массивов -  любой массив являются экземпляром класса System.Array.

Правила объявления массивов не изменились со времен VB 6. Единственное существенное изменение – теперь нумерация элементов массива по умолчанию начинается с нуля. Впрочем, задать нижнюю границу всё-таки можно. Это можно сделать с помощью метода CreateInstance класса Array. Ниже приведены несколько примеров объявлений массивов.

Dim a (11) As Date ' Одномерный массив, содержащий 12 элементов

Dim b (9, 11) As Object ' Двухмерный массив размером 10*12 элементов

Dim c () As Integer ' Динамический массив

Другим очень, на мой взгляд, удобным нововведением является возможность инициализации массива при объявлении. После строки объявления нужно поставить оператор присваивания ‘=’, а после него в фигурных скобках через запятую перечислить значения элементов массива.

Dim a () As Integer = {1, 2, 3, 4, 5}

Таким же образом можно инициализировать и многомерные массивы. Только тогда нужно в объявлении сразу указать количество измерений массива.

Dim b(,) As String = {{"аа", "аб"}, {"ба", "бб"}}

Каждый класс может иметь свойства и методы. Если массив – это класс, то логично предположить, что у него есть свойства или методы, или и то и другое. Начнем с методов. Подробно со структурой объектов .NET Framework можно ознакомиться в MSDN, поэтому я не буду подробно рассказывать о каждом методе, а остановлюсь лишь на основных методах, предназначенных для сортировки и поиска.

Класс Array предлагает два метода поиска элементов: простой и двоичный. Для простого поиска используются методы IndexOf и LastIndexOf. IndexOf ищет первое вхождение указанного объекта, а LastIndexOf – последнее. Синтаксис у этих двух методов одинаков. Они перегружены. Это значит, что функция может принимать разные комбинации параметров. В Object Browser (открывается по нажатию F2) вы обнаружите 3 варианта метода IndexOf:

Public Shared Function IndexOf(ByVal array As System.Array, ByVal value As Object) As Integer

Public Shared Function IndexOf(ByVal array As System.Array, ByVal value As Object, ByVal startIndex As Integer) As Integer

Public Shared Function IndexOf(ByVal array As System.Array, ByVal value As Object, ByVal startIndex As Integer, ByVal count As Integer) As Integer

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

При использовании IndexOf и LastIndexOf программа в цикле проверяет все элементы массива и сравнивает их с искомым объектом. Сравнение выполняется с помощью метода Equals искомого объекта. Он сравнивает 2 объекта и если они равны, то возвращает True, а в противном случае - False. Почти все объекты в .NET Framework имеют этот метод.

Метод возвращает индекс найденного элемента, если поиск увенчался успехом или -1, если ничего не найдено. Все сказанное относится и к методу LastIndexOf. Для наглядности приведу примеры использования функций поиска:

Dim a() As String = {"a", "b", "c", "a", "b", "c"}

Console.WriteLine(System.Array.IndexOf(a, "b"))

Console.WriteLine(System.Array.IndexOf(a, "b", 2))

Console.WriteLine(System.Array.LastIndexOf(a, "b", 3, 3))

Двоичный поиск работает несколько иначе. Он значительно быстрее простого поиска, но может работать только с отсортированными массивами (о сортировке массивов речь пойдет позже). Чтобы найти объект в массиве, BinarySearch сравнивает его с элементом, расположенным в середине массива. Если искомый объект оказывается меньше, значит он находится в первой половине массива, и во второй половине можно его не искать. А если искомый объект больше, то он располагается во второй половине массива. Далее процесс повторяется для той половины массива, в которой находится объект.

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

Как же сравниваются элементы при двоичном поиске? Если в массиве хранятся объекты базовых типов, то все понятно – строки сортируются в алфавитном порядке, сравнение чисел тоже вопросов не вызывает. А как быть, если в массиве хранятся другие объекты? Для того чтобы сортировка массивов, содержащих пользовательские объекты, была возможна, они должны реализовывать интерфейс IComparer. Нужно создать класс, наследующий интерфейс IComparer и реализовать в нём код сравнения двух объектов. Затем  экземпляр этого класса передаётся методу BinarySearch массива. Впрочем, это – отдельная тема, которую мы не будем рассматривать в данной статье подробно.

Двоичный поиск осуществляется с помощью метода BinarySearch класса System.Array. Он перегружен и имеет 4 комбинации параметров. Минимальный набор параметров – массив и искомый объект. Также к этим параметрам вы можете добавить первый элемент и количество элементов области:

Public Shared Function BinarySearch(ByVal array As System.Array, ByVal index As Integer, ByVal length As Integer, ByVal value As Object) As Integer

Вы можете также передать методу BinarySearch объект, наследующий интерфейс IComparer, чтобы задать собственные параметры сравнения объектов при поиске.

Public Shared Function BinarySearch(ByVal array As System.Array, ByVal index As Integer, ByVal length As Integer, ByVal value As Object, ByVal comparer As System.Collections.IComparer) As Integer

Public Shared Function BinarySearch(ByVal array As System.Array, ByVal value As Object, ByVal comparer As System.Collections.IComparer) As Integer

Если объект найден, то метод BinarySearch вернет индекс элемента массива. А если искомый объект не найден, то метод вернёт отрицательное число. Если дополнить его до -1 (изменить знак и вычесть 1), то получится индекс первого из тех элементов массива, которые больше искомого объекта. Если все элементы массива меньше искомого, то получится индекс большего из них. Ниже приведен пример использования метода BinarySearch:

Dim a() As String = {"a", "b", "c", "e", "f"}

Dim ind As Integer

ind = System.Array.BinarySearch(a, "d")

If ind >= 0 Then

  Console.WriteLine("Элемент найден: " & ind.ToString)

Else

  Console.WriteLine("Найдено ближайшее соответствие: " & (-ind - 1).ToString)

End If

Другая полезная возможность, которую предоставляет класс System.Array – сортировка массива. Она производится с помощью метода Sort. Он также перегружен. Самый простой вариант его применения выглядит так:

Public Shared Sub Sort(ByVal array As System.Array)

Он сортирует весь массив. Если вы хотите отсортировать только часть массива, то к параметру array следует добавить индекс начального элемента и длину области, которую вы хотите отсортировать. Sort, в отличие от методов рассмотренных ранее, ничего не возвращает. Ниже приведен пример сортировки части массива.

Dim a() As String = {"c", "r", "z", "b", "d", "a"}

System.Array.Sort(a, 2, 4)

У метода Sort есть ещё одна интересная разновидность, позволяющая сортировать элементы одного массива в соответствии со значениями элементов другого массива.

Public Shared Sub Sort(ByVal keys As System.Array, ByVal items As System.Array)

В первом параметре задаётся массив ключей. На основе элементов этого массива будет отсортирован массив, передаваемый во втором параметре. Допустим, у нас имеется массив со словами (words) и массив, в котором для каждого слова указана частота его употребления в тексте (freq). Используя первую форму метода Sort можно отсортировать слова по алфавиту. А с помощью последней рассмотренной формы метода мы можем отсортировать слова по частоте их использования. Для этого нужно первым параметром указать массив freq, а вторым – words.

System.Array.Sort (freq, words)

Такая сортировка имеет смысл, если длины массивов равны. Если длиннее будет массив items, то последние элементы, для которых нет соответствий в массиве keys, не будут учитываться при сортировке и останутся после вызова метода Sort на своих местах. Например, если в массиве keys 3 элемента, а в items – 5, то будут отсортированы только первые 3 элемента массива items, а четвёртый и пятый элементы не будут участвовать в сортировке и останутся на своих местах. Ну а если длиннее будет массив keys, то будет сгенерировано исключение System.ArgumentException.

ArrayList

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

Но не все так плохо. В пространстве имен System.Collections существует класс ArrayList, который позволяет решить эти проблемы. ArrayList – это список, в которой вы можете хранить нетипизированные данные (то есть, в одном объекте ArrayList могут храниться и строки, и числа, и даты, и прочие объекты). При объявлении списка вам не нужно задавать его размер. Кроме того, вы можете добавлять и удалять элементы из любого места списка, будь то начало, середина или конец.

Для создания нового объекта ArrayList используется следующий код:

Dim collname As New ArrayList()

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

Console.WriteLine (collname.Add (“test”))

Для добавления объекта в середину коллекции служит метод Insert. Ему передается индекс, который будет иметь добавляемый элемент и, собственно, сам объект.

collname.Insert (1, “abc”)

Индекс, передаваемый методу Insert должен быть неотрицателен (index>=0) и меньше или равен размеру коллекции (index<=collname.Count). Все элементы, расположенные после добавляемого элемента будут сдвинуты вправо.

Чтобы удалить элемент коллекции, можно использовать метод RemoveAt. Ему передается индекс удаляемого элемента.

collname.RemoveAt (0)

Для получения элемента по его индексу используется индексированное свойство Item объекта ArrayList. С его помощью можно также устанавливать значения уже существующих элементов. Синтаксис свойства прост:

data = collname.Item (index) ' чтение элемента в переменную data

collname.Item (index) = data ' установка значения элемента

Получить количество элементов коллекции можно с помощью свойства Count.

Console.WriteLine (collname.Count)

Механизмы поиска и сортировки элементов ArrayList и массивов практически одинаковы. Стоит отметить только одну деталь: объект ArrayList не может быть отсортирован по значениям другого ArrayList.

Итак, с точки зрения удобства вставки/удаления элементов ArrayList удобнее и гибче массивов. Также не нужно заботиться о размерах коллекции - она словно резиновая! Впрочем, размеры коллекции все же можно контролировать. Объем памяти, отведенной для коллекции, задается свойством Capacity. Оно имеет тип Integer и устанавливает максимальное количество элементов, которое можно уместить в коллекцию. По умолчанию Capacity равно 16. Если количество элементов превышает значение, установленное в Capacity, то оно автоматически удваивается.

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

collname.Capacity = collname.Count

А можно воспользоваться специально для этого предназначенным методом TrimToSize. Он не имеет параметров. Действие метода TrimToSize аналогично вышеуказанной строке кода. По идее, метод TrimToSize должен освободить некоторое количество оперативной памяти. Однако этого не происходит! А всё потому что приложения .NET по-особому используют оперативную память. В начале работы приложения .NET создаётся куча, состоящая из одного большого блока памяти. Когда сборка запрашивает у CLR объект, память выделяется из свободного блока в верхней части кучи, при этом среда даже не пытается заполнять пустые места, появившиеся на месте ранее освобождённых объектов. Когда весь свободный блок исчерпан, CLR приступает к сборке мусора (garbage collection). При сборке мусора все объекты, на которые нет ссылок, удаляются из памяти. Именно поэтому после вызова метода TrimToSize память не освобождается сразу – неиспользуемые объекты будет удалены из памяти после первой сборки мусора.

Хотя массивы и коллекции ArrayList отличаются по возможностям, обе структуры предназначены для хранения данных. Поэтому неудивительно, что в классе ArrayList предусмотрены механизмы для конвертирования коллекции в массив. Это делается с помощью метода ToArray. Он перегружен. Если объект ArrayList содержит данные одного типа, то вы можете указать в методе ToArray используемый тип данных – параметр типа System.Type. Тогда метод вернет массив указанного типа. Если же вы не укажете тип данных, то будет возвращен массив типа Object.

Dim a () As String

collname.ToArray (System.Type.GetType("System.String"))

Быстродействие

Как известно, за все нужно платить. За удобство и функциональность коллекций ArrayList также приходится платить. По сравнению с массивами коллекции ArrayList работают гораздо медленнее и занимают больше оперативной памяти. Происходит это из-за особенностей коллекций, которые, собственно, и создают удобство их использование (возможность добавлять и удалять элементы из середины коллекции). Если вы создаёте массив, то его размер будет равен количеству элементов массива помноженному на размер каждого элемента. Например, для массива с 10 элементами типа Integer выделяется 10*4=40 байт. Затем для считывания элемента массива вычисляется его положение в памяти на основании номера элемента и размера элементов и затем считывается нужный участок памяти. С коллекциями всё иначе. Каждый элемент коллекции представлен не одной переменной, содержащей его значение, а структурой данных. Она содержит указатель на данные элемента, ссылки на предыдущий и следующий элемент коллекции. Естественно, такая структура будет занимать больше пространства в оперативной памяти, чем одна единственная переменная. Доступ к данным в коллекции также организуется по-особому. Для получения, например, пятого элемента, коллекция перебирает все элементы, начиная с первого, пока не дойдёт до нужного индекса.

Я провел небольшие испытания между массивами и ArrayList[1]. Ниже представлены исходные коды тестов:

Private Sub ArrayAdd()

  Dim d1 As Date

  Dim d2 As Date

  Dim a(10000000) As Integer

  Dim i As Integer

  Dim d As New TimeSpan()

  d1 = DateTime.Now

  For i = 1 To 10000000

    a(i) = i

  Next

  d2 = DateTime.Now

  d = d2.Subtract(d1)

  Console.WriteLine(d.TotalMilliseconds)

End Sub

Private Sub ArrayListAdd()

  Dim d1 As Date

  Dim d2 As Date

  Dim a As New ArrayList(10000000)

  Dim i As Integer

  Dim d As New TimeSpan()

  d1 = DateTime.Now

  For i = 1 To 10000000

    a.Add(i)

  Next

  d2 = DateTime.Now

  d = d2.Subtract(d1)

  Console.WriteLine(d.TotalMilliseconds)

End Sub

Private Sub ArraySort()

  Dim d1 As Date

  Dim d2 As Date

  Dim s As System.Text.StringBuilder

  Dim a(10000) As String

  Dim i As Integer

  Dim j As Integer

  Dim d As New TimeSpan()

  For i = 1 To 10000

    s = New System.Text.StringBuilder(5)

    For j = 1 To 5

      Randomize()

      s = s.Append(Chr(CInt((Rnd() * 25) + 65)))

      a(i) = s.ToString

    Next

  Next

  d1 = DateTime.Now

  Array.Sort(a)

  d2 = DateTime.Now

  d = d2.Subtract(d1)

  Console.WriteLine(d.TotalMilliseconds)

End Sub

Private Sub ArrayListSort()

  Dim d1 As Date

  Dim d2 As Date

  Dim s As System.Text.StringBuilder

  Dim a As New ArrayList(10000)

  Dim i As Integer

  Dim j As Integer

  Dim d As New TimeSpan()

  For i = 1 To 10000

    s = New System.Text.StringBuilder(5)

    For j = 1 To 5

      Randomize()

      s = s.Append(Chr(CInt((Rnd() * 25) + 65)))

      a.Add(s.ToString)

    Next

  Next

  d1 = DateTime.Now

  a.Sort()

  d2 = DateTime.Now

  d = d2.Subtract(d1)

  Console.WriteLine(d.TotalMilliseconds)

End Sub

Private Sub ArrayGet()

  Dim d1 As Date

  Dim d2 As Date

  Dim a(10000000) As Integer

  Dim i As Integer

  Dim b As Integer

  Dim d As New TimeSpan()

  For i = 1 To 10000000

    a(i) = i

  Next

  d1 = DateTime.Now

  For i = 1 To 10000000

    b = a(i)

  Next

  d2 = DateTime.Now

  d = d2.Subtract(d1)

  Console.WriteLine(d.TotalMilliseconds)

End Sub

Private Sub ArrayListGet()

  Dim d1 As Date

  Dim d2 As Date

  Dim a As New ArrayList(10000000)

  Dim i As Integer

  Dim b As Integer

  Dim d As New TimeSpan()

  For i = 1 To 10000000

    a.Add(i)

  Next

  d1 = DateTime.Now

  For i = 1 To 10000000

    b = a(i - 1)

  Next

  d2 = DateTime.Now

  d = d2.Subtract(d1)

  Console.WriteLine(d.TotalMilliseconds)

End Sub

Их результаты вы можете увидеть в таблице 1.

Таблица 1.

Результаты впечатляют... Массивы работают быстрее коллекций ArrayList в десятки раз! Если ваше приложение постоянно работает с большим объемом данных, стоит отказаться от коллекций ArrayList и использовать массивы.

Коллекция HashTable

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

В .NET Framework имеется коллекция HashTable, реализующая, как нетрудно догадаться, хэш-таблицу. Каждый элемент в этой коллекции имеет значение и ключ. Ключ – это уникальный идентификатор, предназначенный для доступа к элементу. Он может быть любого типа, будь то String, Integer, Object или любой другой объект.

Класс HashTable очень похож на ArrayList, но имеет ряд серьезных отличий. Сразу стоит отметить отсутствие у класса HashTable свойства Capacity. О других новшествах я расскажу ниже.

Работа с коллекцией начинается с создания нового объекта HashTable. Это делается с помощью оператора New.

Dim col As New HashTable ()

Для добавления нового элемента в коллекцию используется метод Add. Ему передаются ключ и собственно добавляемый объект.

Dim orders As New HashTable ()

orders.Add (“Moscow”, 8)

orders.Add (“Tomsk”, 5)

При добавлении элемента вы должны помнить, что ключи должны быть уникальными. Если вы попытаетесь использовать уже имеющийся ключ, то будет сгенерировано исключение. Узнать, имеется ли в коллекции некоторый ключ, можно с помощью метода ContainsKey. Ему передается проверяемый ключ. Метод возвратит True, если ключ существует и False в обратном случае. Также существует метод ContainsValue. Он позволяет узнать, имеется ли в коллекции значение и используется так же, как и ContainsKey.

If col.ContainsKey (“abc”) = True Then

  Console.WriteLine (“Ключ ‘abc’ имеется в коллекции”)

End If

Удаление элементов из коллекции HashTable осуществляет метод Remove. Ему следует передать ключ удаляемого элемента.

Другие коллекции

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

Коллекция SortedList представляет собой нечто вроде гибрида HashTable и ArrayList. К элементам коллекции можно обращаться как по индексам, так и по ключам. Более того, эта коллекция всегда отсортирована по ключам. Метода для сортировки коллекции по значениям не существует.

Еще две интересных коллекции – Queue и Stack. Они отличаются лишь способом добавления и удаления элементов. Класс Stack добавляет элементы в конец коллекции и удаляет всегда последний элемент. Коллекция Stack реализует структуру LIFO (last in first out – последний вошел, первый вышел). А класс Queue добавляет элементы в конец коллекции и удаляет только первый элемент. Это очередь или структура FIFO (first in first out – первый вошел, первый вышел).

И ещё одна коллекция, которая находится в пространстве имён System.Collections – BitArray. Она предназначена для хранения битов (значений типа Boolean). Стоит подчеркнуть один интересный момент: в этом классе содержатся методы, реализующие поэлементные логические операции XOR, OR, AND и NOT.

Заключение

В этой статье мы рассмотрели базовые возможности массивов и коллекций. Microsoft .NET предлагает программистам богатые возможности хранения и обработки наборов данных. Массивы стали намного удобнее и функциональнее. А богатство коллекций .NET ни в какое сравнение не идет с единственным классом Collection в VB6. Практически для любых целей вы можете подобрать подходящую коллекцию или создать собственную на базе имеющихся.

Павел Сурменок

pavel@vbnet.ru

http://vbnet.ru