До третьей версии Visual Basic не содержал средств для прямого создания ссылок. Тем не менее, поскольку указатель всего лишь ссылается на какой‑либо участок данных, то можно, создав массив, использовать целочисленный индекс массива в качестве указателя на его элементы. Это называется псевдоуказателем (fake pointer).
В 4-й версии Visual Basic были впервые введены классы. Переменная, указывающая на экземпляр класса, является ссылкой на объект. Например, в следующем фрагменте кода переменная obj — это ссылка на объект класса MyClass. Эта переменная не указывает ни на какой объект, пока она не определяется при помощи зарезервированного слова New. Во второй строке оператор New создает новый объект и записывает ссылку на него в переменную obj.
Dim obj As MyClass
Set obj = New MyClass
Ссылки в Visual Basic — это разновидность указателей.
Объекты в Visual Basic используют счетчик ссылок (reference counter) для упрощения работы с объектами. Когда создается новая ссылка на объект, счетчик ссылок увеличивается на единицу. После того, как ссылка перестает указывать на объект, счетчик ссылок соответственно уменьшается. Когда счетчик ссылок становится равным нулю, объект становится недоступным программе. В этот момент Visual Basic уничтожает объект и возвращает занятую им память.
В следующих главах более подробно обсуждаются ссылки и счетчики ссылок.
Кроме объектов и ссылок, в 4-й версии Visual Basic также появились коллекции. Коллекцию можно представить как разновидность массива. Они
================14
предоставляют в распоряжение программиста удобные возможности, например можно менять размер коллекции, а также осуществлять поиск объекта по ключу.
Псевдоуказатели, ссылки и коллекции упоминаются в этой главе потому, что они могут сильно влиять на производительность программы. Ссылки и коллекции могут упрощать программирование определенных операций, но они могут потребовать дополнительных расходов памяти.
Программа Faker на диске с примерами демонстрирует взаимосвязь между псевдоуказателями, ссылками и коллекциями. Когда вы вводите число и нажимаете кнопку Create List (Создать список), программа создает список элементов одним из трех способов. Вначале она создает объекты, соответствующие отдельным элементам, и добавляет ссылки на объекты к коллекции. Затем она использует ссылки внутри самих объектов для создания связанного списка объектов. И, наконец, она создает связный список при помощи псевдоуказателей. Пока не будем останавливаться на том, как работают связные списки. Они будут подробно разбираться во 2 главе.
После нажатия на кнопку Search List (Поиск в списке), программа Faker выполняет поиск по всем элементам списка, а после нажатия на кнопку Destroy List (Уничтожить список) уничтожает все списки и освобождает память.
В табл. 1.5 приведены значения времени, которое требуется программе для выполнения этих задач на компьютере с процессором Pentium с тактовой частотой 90 МГц. Из таблицы видно, что за удобство работы с коллекциями приходится платить ценой большего времени, затрачиваемого на создание и уничтожение коллекций.
Коллекции также содержат индекс списка. Часть времени, затрачиваемого при создании коллекции, и уходит на создание индекса. При уничтожении коллекции сохраняемые в ней ссылки освобождаются. При этом система проверяет и обновляет счетчики ссылок для всех объектов. Если они равны нулю, то сам объект также уничтожается. Все это занимает дополнительное время.
При использовании псевдоуказателей создание и уничтожение списка происходит так быстро, что этим временем можно практически пренебречь. Системе при этом не надо заботиться о ссылках, счетчиках ссылок и об освобождении объектов.
С другой стороны, поиск в коллекции осуществляется гораздо быстрее, чем в двух остальных случаях, поскольку коллекция использует быстрое хеширование (hashing) построенного индекса, в то время как список ссылок и список псевдоуказателей используют медленный последовательный поиск. В 11 главе объясняется, как можно добавить хеширование к своей программе без использования коллекций.
@Таблица 1.5. Время Создания/Поиска/Уничтожения списков в секундах
==============15
Хотя применение псевдоуказателей обычно обеспечивает лучшую производительность, оно менее удобно, чем использование ссылок. Если в программе нужен лишь небольшой список, ссылки и коллекции могут работать достаточно быстро. При работе с большими списками можно получить более высокую производительность, используя псевдоуказатели.
Анализ производительности алгоритмов позволяет сравнить разные алгоритмы. Он также помогает оценить поведение алгоритмов при различных условиях. Выделяя только части алгоритма, которые вносят наибольший вклад во время исполнения программы, анализ помогает определить, доработка каких участков кода позволяет внести максимальный вклад в улучшение производительности.
В программировании часто приходится идти на различные компромиссы, которые могут сказываться на производительности. Один алгоритм может быть быстрее, но за счет использования большого объема памяти. Другой алгоритм, использующий коллекции, может быть более медленным, но зато его проще разрабатывать и поддерживать.
После анализа доступных алгоритмов, понимания того, как они ведут себя в различных условиях и их требований к ресурсам, вы можете выбрать оптимальный алгоритм для вашей задачи.
==============16
Существует четыре основных способа распределения памяти в Visual Basic: объявление переменных стандартных типов (целые, с плавающей точкой и т.д.); объявление переменных типов, определенных пользователем; создание экземпляров классов при помощи оператора New и изменение размера массивов. Существует еще несколько способов, например, создание нового экземпляра формы или элемента управления, но эти способы не дают больших возможностей при создании сложных структур данных.
Используя эти методы, можно легко строить статические структуры данных, такие как большие массивы определенных пользователем типов. Вы также можете изменять размер массива при помощи оператора ReDim. Тем не менее, перераспределение данных может быть достаточно сложным. Например, для того, чтобы переместить элемент с одного конца массива на другой, потребуется переупорядочить весь массив, сдвинув все элементы на одну позицию, чтобы заполнить освободившееся пространство. Затем можно поместить элемент на его новое место.
Динамические структуры данных позволяют быстро и легко выполнять такого рода изменения. Всего за несколько шагов можно переместить любой элемент в структуре данных в любое другое положение.
В этой главе описаны методы создания динамических списков в Visual Basic. Различные типы списков обладают разными свойствами. Некоторые из них просты и обладают ограниченной функциональностью, другие же, такие как циклические списки, одно‑ или двусвязные списки, являются более сложными и поддерживают более развитые средства управления данными.
В последующих главах описанные методы используются для построения стеков, очередей, массивов, деревьев, хэш‑таблиц и сетей. Вам необходимо усвоить материал этой главы перед тем, как продолжить чтение.
Простейшая форма списка — это группа объектов. Она включает в себя объекты и позволяет программе обращаться к ним. Если это все, что вам нужно от списка, вы можете использовать массив в качестве списка, отслеживая при помощи переменной NumInList число элементов в списке. Определив при помощи этой переменной число имеющихся элементов, программа затем может по очереди обратиться к ним в цикле For и выполнить необходимые действия.
=============17
Если вы в своей программе можете обойтись этим подходом, используйте его. Этот метод эффективен, и его легко отлаживать и поддерживать благодаря его простоте. Тем не менее, большинство программ не столь просты, и в них требуются более сложные конструкции даже для таких простых объектов, как списки. Поэтому в последующих разделах этой главы обсуждаются некоторые пути создания списков с большей функциональностью.
В первом параграфе описываются пути создания списков, которые могут расти и уменьшаться со временем. В некоторых программах нельзя заранее определить, насколько большой список понадобится. Вы можете справиться с такой ситуацией при помощи списка, который может при необходимости изменять свой размер.
В следующем параграфе обсуждаются неупорядоченные списки (unordered list), которые позволяют удалять элементы из любой части списка. Неупорядоченные списки дают больший контроль над содержимым списка, чем простые списки. Они также являются более динамичными, так как позволяют изменять содержимое в произвольный момент времени.
В последующих разделах обсуждаются связные списки (linked list), которые используют указатели для создания чрезвычайно гибких структур данных. Вы можете добавлять или удалять элементы из любой части связного списка с минимальными усилиями. В этих параграфах также описаны некоторые разновидности связных списков, такие как циклические, двухсвязные списки или списки со ссылками.
Если в вашей программе необходим список постоянного размера, вы можете создать его, просто используя массив. В этом случае можно при необходимости опрашивать его элементы в цикле For.
Многие программы используют списки, которые растут или уменьшаются со временем. Можно создать массив, соответствующий максимально возможному размеру списка, но такое решение не всегда будет оптимальным. Не всегда можно заранее знать, насколько большим может стать список, кроме того, вероятность, что список станет очень большим, может быть невелика, и созданный массив гигантских размеров может большую часть времени лишь понапрасну занимать память.