Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Иногда можно написать код так, что программа будет обращаться к блокам памяти последовательно. Алгоритм сортировки слиянием, описанный в 9 главе, манипулирует большими блоками данных. Эти блоки сортируются, а затем сливаются вместе. Упорядоченная работа с памятью уменьшает число обращений к диску.
@Таблица 1.4. Время выполнения программы Pager в секундах
===============13
Алгоритм пирамидальной сортировки, также описанный в 9 главе, произвольно переходит от одной части списка к другой. Для очень больших списков это может приводить к перегрузке памяти. С другой стороны, сортировка слиянием требует большего объема памяти, чем пирамидальная сортировка. Если список достаточно большой, это также может приводить к обращению к файлу подкачки.
Псевдоуказатели, ссылки на объекты и коллекции
В некоторых языках, например в C, C++ или Delphi, можно определять переменные, которые являются указателями (pointers) на участки памяти. В этих участках могут содержаться массивы, строки, или другие структуры данных. Часто указатель ссылается на структуру, которая содержит другой указатель и так далее. Используя структуры, содержащие указатели, можно организовывать всевозможные списки, графы, сети и деревья. В последующих главах рассматриваются некоторые из этих сложных структур.
До третьей версии 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
Глава 2. СпискиСуществует четыре основных способа распределения памяти в Visual Basic: объявление переменных стандартных типов (целые, с плавающей точкой и т.д.); объявление переменных типов, определенных пользователем; создание экземпляров классов при помощи оператора New и изменение размера массивов. Существует еще несколько способов, например, создание нового экземпляра формы или элемента управления, но эти способы не дают больших возможностей при создании сложных структур данных.
Используя эти методы, можно легко строить статические структуры данных, такие как большие массивы определенных пользователем типов. Вы также можете изменять размер массива при помощи оператора ReDim. Тем не менее, перераспределение данных может быть достаточно сложным. Например, для того, чтобы переместить элемент с одного конца массива на другой, потребуется переупорядочить весь массив, сдвинув все элементы на одну позицию, чтобы заполнить освободившееся пространство. Затем можно поместить элемент на его новое место.
Динамические структуры данных позволяют быстро и легко выполнять такого рода изменения. Всего за несколько шагов можно переместить любой элемент в структуре данных в любое другое положение.
В этой главе описаны методы создания динамических списков в Visual Basic. Различные типы списков обладают разными свойствами. Некоторые из них просты и обладают ограниченной функциональностью, другие же, такие как циклические списки, одно‑ или двусвязные списки, являются более сложными и поддерживают более развитые средства управления данными.
В последующих главах описанные методы используются для построения стеков, очередей, массивов, деревьев, хэш‑таблиц и сетей. Вам необходимо усвоить материал этой главы перед тем, как продолжить чтение.
Знакомство со списками
Простейшая форма списка — это группа объектов. Она включает в себя объекты и позволяет программе обращаться к ним. Если это все, что вам нужно от списка, вы можете использовать массив в качестве списка, отслеживая при помощи переменной NumInList число элементов в списке. Определив при помощи этой переменной число имеющихся элементов, программа затем может по очереди обратиться к ним в цикле For и выполнить необходимые действия.
=============17
Если вы в своей программе можете обойтись этим подходом, используйте его. Этот метод эффективен, и его легко отлаживать и поддерживать благодаря его простоте. Тем не менее, большинство программ не столь просты, и в них требуются более сложные конструкции даже для таких простых объектов, как списки. Поэтому в последующих разделах этой главы обсуждаются некоторые пути создания списков с большей функциональностью.
В первом параграфе описываются пути создания списков, которые могут расти и уменьшаться со временем. В некоторых программах нельзя заранее определить, насколько большой список понадобится. Вы можете справиться с такой ситуацией при помощи списка, который может при необходимости изменять свой размер.
В следующем параграфе обсуждаются неупорядоченные списки (unordered list), которые позволяют удалять элементы из любой части списка. Неупорядоченные списки дают больший контроль над содержимым списка, чем простые списки. Они также являются более динамичными, так как позволяют изменять содержимое в произвольный момент времени.
В последующих разделах обсуждаются связные списки (linked list), которые используют указатели для создания чрезвычайно гибких структур данных. Вы можете добавлять или удалять элементы из любой части связного списка с минимальными усилиями. В этих параграфах также описаны некоторые разновидности связных списков, такие как циклические, двухсвязные списки или списки со ссылками.
Простые списки
Если в вашей программе необходим список постоянного размера, вы можете создать его, просто используя массив. В этом случае можно при необходимости опрашивать его элементы в цикле 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 ‘ Число используемых элементов.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48
