Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

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

Что более важно, если не нужно будет разбиение блоков, то не понадобится и перемещение элемента в родительский узел. Это предотвращает возникновение длительной последовательности разбиений блоков.

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

Добавление свободного пространства

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

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

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

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

@Рис. 7.20. Балансировка для устранения разбиения блоков

=======178

@Рис. 7.21. Плотное заполнение Б‑дерева

Вопросы, связанные с обращением к диску

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

Псевдоуказатели

Коллекции и ссылки на объекты удобны для построения деревьев в памяти, но они могут быть бесполезны при хранении дерева на диске. Нельзя создать ссылку на запись в файле.

Вместо этого можно использовать методы работы с псевдоуказателями, похожие на те, которые были описаны во 2 главе. Вместо использования в качестве указателей на узлы дерева ссылок на объекты при этом используется номер записи узла в файле. Предположим, что Б+дерево 12 порядка использует 80‑байтные ключи. Структуру данных узла можно определить в следующем коде:

Global Const ORDER = 12

Global Const KEYS_PER_NODE = 2 * ORDER

Type BtreeNode

    Key (1 To KEYS_PER_NODE) As String * 80     ' Ключи.

    Child (0 To KEYS_PER_NODE) As Integer ' Указатели потомков.

End Type

Значения элементов массива Child представляют собой номера записей из дочерних узлов в файле. Произвольный доступ к данным Б+дерева из файла осуществляется при помощи записей, которые соответствуют структуре BtreeNode.

@Рис. 7.22. Свободное заполнение Б‑дерева

======179

Dim node As BtreeNode

    Open Filename For Random As #filenum Len = Len(node)

После открытия файла, при помощи оператора Get можно выбрать любую запись:

Dim node As BtreeNode

    ' Выбрать запись с номером recnum.

    Get #filenum, recnum, node

Чтобы упростить работу с Б+деревьями, можно хранить узлы Б+дерева и записи данных в разных файлах и использовать для управления каждым из них псевдоуказатели.

Когда счетчик ссылок на объект становится равным нулю, то Visual Basic автоматически уничтожает его. Это облегчает работу со структурами данных в памяти. С другой стороны, если программе больше не нужна какая‑либо запись в файле, то она не может просто очистить все ссылки на нее. Если сделать так, то программа больше не сможет использовать эту запись, но запись по‑прежнему будет занимать место в файле.

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

Выбор размера блока

Чтение данных с диска происходит блоками, которые называются кластерами. Размер кластера обычно составляет 512 или 1024 байта, или еще какое‑либо число байтов, равное степени двойки. Чтение всего кластера занимает столько же времени, сколько и чтение одного байта.

Можно воспользоваться этим фактом и создавать блоки, размер которых составляет целое число кластеров, а затем уместить в этот размер максимальное число ключей или записей. Например, предположим, что мы решили создавать блоки размером 2048 байт. При создании Б+дерева с 80‑байтными ключами в каждый блок можно поместить 24 ключа и 25 указателей (если указатель представляет собой 4‑байтное число типа long). Затем можно создать Б+дерево 12 порядка с блоками, которые определяются в следующем коде:

Global Const ORDER = 12

Global Const KEYS_PER_NODE = 2 * ORDER

Type BtreeNode

    Key(1 To KEYS_PER_NODE) As String * 80      ' Ключ данных.

    Child(0 To KEYS_PER_NODE) As Integer ' Указатели потомков.

End Type

=======180

Для того, чтобы считывать данные максимально быстро, программа должна использовать оператор Visual Basic Get для чтения узла целиком. Если использовать цикл For для чтения ключей и данных для каждого элемента по очереди, то программе придется обращаться к диску при чтении каждого элемента. Это намного медленнее, чем считывание всего узла сразу. В одном из тестов, для массива из 1000 элементов определенного пользователем типа чтение элементов по одиночке заняло в 27 раз больше времени, чем чтение их всех сразу. Следующий код демонстрирует оба способа чтения данных из узла:

Dim i As Integer

Dim node As BtreeNode

    ' Медленный способ доступа к данным.

    For i = 1 To KEYS_PER_NODE

        Get #filenum, , node.Key(i)

    Next i

    ' Быстрый способ доступа к данным.

    Get #filenum, , node

Кэширование узлов

Каждый поиск в Б‑дереве начинается с корневого узла. Можно ускорить поиск, если корневой узел будет все время находиться в памяти. Тогда во время поиска придется на один раз меньше обращаться к диску. При этом все равно необходимо записывать корневой узел на диск при каждом его изменении, иначе при повторной загрузке после отказа программы изменения в Б‑дереве будут потеряны.

Можно также кэшировать в памяти и другие узлы Б‑дерева. Если хранить в памяти все дочерние узлы корня, то их также не потребуется считывать с диска. Для Б‑дерева порядка K, корневой узел будет иметь от 1 до 2 * K ключей и поэтому у него будет от 2 до 2 * K + 1 дочерних узлов. Это значит, что в этом случае придется кэшировать до 2 * K + 1 узлов.

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

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

=======181

Private Sub PreorderPrint(node_index As Integer)

Dim i As Integer

Dim node As BtreeNode

    Get #filenum, node_index, node       ' Кэшировать узел.

    Print node_index                            ' Обращение к узлу.

    For i = 0 To KEYS_PER_NODE

        If node.Child(i) < 0 Then Exit For      ' Вызов потомков.

        PreorderPrint node.Child(i)             ' Вызов потомка.

    Next i

End Sub

База данных на основе Б+дерева

Программа Bplus работает с базой данных на основе Б+дерева, используя два файла данных. Файл Custs.DAT содержит записи с данными о клиентах, а файл Custs.IDX — узлы Б+дерева.

Чтобы добавить новую запись в базу данных, введите данные в поле Customer Record (Запись о клиенте), и затем нажмите на кнопку Add. Для поиска записи заполните поля Last Name (Фамилия) и First Name (Имя) в верхней части формы и нажмите на кнопку Find (Найти).

На рис. 7.23 показано окно программы после выполнения поиска записи для Рода Стивенса. Статистика внизу показывает, что данные были найдены в записи номер 302 после всего лишь трех обращений к диску. Высота Б+дерева в программе равна 3, и оно содержит 1303 записей данных и 118 блоков.

Когда вы вводите запись или проводите поиск, программа Bplus выбирает эту запись из файла. После нажатия на кнопку Remove программа удаляет запись из базы данных.

@Рис. 7.23. Программа Bplus

========182

Если выбрать в меню Display (Показать) команду Internal Nodes (Внутренние узлы), то программа выведет список внутренних узлов дерева. Она также выводит рядом с каждым узлом ключи, чтобы показать внутреннюю структуру дерева.

При помощи команды Complete Tree (Все дерево) из меню Display можно вывести структуру дерева целиком. Данные о клиентах выводятся внутри пунктирных скобок.

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

Type CustRecord

    LastName As String * 20

    FirstName As String * 20

    Address As String * 40

    City As String * 20

    State As String * 2

    Zip As String * 10

    Phone As String * 12

    NextGarbage As Long

End Type

' Размер записи данных о клиенте.

Global Const CUST_SIZE = 20 + 20 + 40 + 20 + 2 + 10 + 12 + 4

Внутренние узлы Б+дерева содержат ключи, которые используются для поиска данных о клиенте. Ключом для записи является фамилия клиента, дополненная в конце пробелами до 20 символов и заканчивающаяся запятой, за которой следует имя клиента, дополненное пробелами до 20 символов. Например, "Washington..........,George..............". При этом полная длина ключа составляет 41 символ.

Каждый внутренний узел также содержит указатели на дочерние узлы. Эти указатели определяют положение записей с данными о клиенте в файле Custs.DAT. Узлы также включают переменную NumKeys, которая содержит число используемых ключей.

Программа читает и пишет данные блоками примерно по 1024 байта. Если предположить, что блок содержит K ключей, то в каждом блоке будет K ключей длиной 41 байт, K + 1 указателей на дочерние узлы длиной по 4 байта, и двухбайтное целое число NumKeys. При этом блоки должны иметь максимально возможный размер и быть не больше 1024 байт.

Решив уравнение 41 * K + 4 * (K + 1) + 2 <= 1.024, получим K <= 22,62, поэтому K должно быть равно 22. В этом случае Б+дерево должно иметь 11 порядок, поэтому оно содержит по 22 ключа в каждом блоке. Каждый блок занимает 41 * 22 + 4 * (22 + 1) + 2 = 996 байт. Следующий код демонстрирует определение блоков в программе Bplus.

=======183

Const KEY_SIZE = 41

Const ORDER = 11

Global Const KEYS_PER_NODE = 2 * ORDER

Type Bucket

    NumKeys As Integer

    Key(1 To KEYS_PER_NODE) As String * KEY_SIZE

    Child(0 To KEYS_PER_NODE) As Long

End Type

Global Const BUCKET_SIZE = 2 + _

    KEYS_PER_NODE * KEY_SIZE + _

    (KEYS_PER_NODE + 1) * 4

Программа Bplus записывает блоки Б+дерева в файле Custs.IDX. Первая запись в этом файле содержит заголовок, который описывает текущее состояние Б+дерева. В заголовок входит указатель на корневой узел, текущая высота дерева, указатель на первый пустой блок в файле Custs.IDX, и указатель на первый пустой блок в файле Custs.DAT.

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

Global Const HEADER_PADDING = _

    BUCKET_SIZE - (7 * 4 + 2)

Type HeaderRecord

    NumBuckets As Long

    NumRecords As Long

    Root As Long

    NextTreeRecord As Long

    NextCustRecord As Long

    FirstTreeGarbage As Long

    FirstCustGarbage As Long

    Height As Integer

    Padding As String * HEADER_PADDING

End Type

При запуске программы она запрашивает директорию, в которой находятся данные, и затем открывает файлы Custs.DAT файлы Custs.IDX в этой директории. Если эти файлы не существуют, то программа их создает. В противном случае, она считывает заголовок с информацией о дереве из файла Custs.IDX. Затем она считывает корневой узел Б+дерева и кэширует его в памяти.

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

Увеличение размера блоков позволяет сделать Б+деревья более эффективными, но при этом тестировать их вручную будет сложнее. Чтобы высота Б+дерева 11 порядка стала равна 2, необходимо добавить к базе данных 23 элемента. Чтобы увеличить высоту дерева до 3 уровня, необходимо добавить более 250 дополнительных элементов.

=======184

Чтобы было проще тестировать программу Bplus, вы можете захотеть уменьшить порядок Б+дерева до 2. Для этого закомментируйте в файле Bplus.BAS строку, которая определяет 11 порядок, и уберите комментарий из строки, которая задает 2 порядок:

'Const ORDER = 11

Const ORDER = 2

Команда Create Data (Создать данные) в меню Data (Данные) позволяет быстро создать множество записей данных. Введите число записей, которые вы хотите создать, и число, которое программа должна использовать для создания первого элемента. Затем программа создаст записи и вставит их в Б+дерево. Например, если задать в программе создание 100 записей, начиная со значения 200, то программа создаст записи 200, 201, … 299, которые будут выглядеть так:

FirstName: First 0000200

LastName:  Last 0000200

Address:   Addr 0000200

Cuty:      City 0000200

Резюме

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

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

========185

Многие сложные реальные задачи можно смоделировать при помощи деревьев решений (decision trees). Каждый узел дерева представляет один шаг решения задачи. Каждая ветвь в дереве представляет решение, которое ведет к более полному решению. Листья представляют собой окончательное решение. Цель заключается в том, чтобы найти «наилучший» путь от корня к листу при выполнении определенных условий. Эти условия и значение понятия «наилучший» для пути зависит от задачи.

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

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

В следующих разделах описываются способы поиска в более общих деревьях решений. Для самых маленьких деревьев, можно использовать метод полного перебора (exhaustive searching) всех возможных решений. Для деревьев большего размера, можно использовать метод ветвей и границ (branch‑and‑bound technique) позволяет найти наилучшее решение без необходимости выполнять поиск по всему дереву.

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

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

Поиск в деревьях игры

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

========187

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

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

Как можно увидеть на рис. 8.1, дерево игры в крестики‑нолики растет очень быстро. Если оно продолжит расти таким образом, так что каждый следующий узел в дереве будет иметь на одну ветвь меньше, чем его родитель, то дерево целиком будет иметь 9 * 8 * 7 … * 1 = 362.880 листьев. В дереве будет 362.880 возможных путей, соответствующих 362.800 возможным играм.

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

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

@Рис. 8.1. Фрагмент дерева игры в крестики‑нолики

========188

@Рис. 8.2. Быстрое окончание игры

Минимаксный поиск

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

Для каждого игрока, можно присвоить позиции один из четырех весов. Если вес равен 4, то это значит, что игрок в этой позиции выигрывает. Если вес равен 3, то из текущего положения на доске неясно, кто из игроков выиграет в конце концов. Вес, равный 2, означает, что позиция приводит к ничьей. И, наконец, вес, равный 1, означает, что выигрывает противник.

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

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

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

======189

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

И наконец, процедура может достигнуть заданной максимальной глубины рекурсии. В этом случае, процедура BoardValue присваивает позиции вес 3, что указывает, что она не может определить победителя. Задание максимальной глубины рекурсии ограничивает время поиска в дереве игры. Это особенно важно для более сложных игр, таких как шахматы, в которых поиск в дереве игры может продолжаться практически вечно. Максимальная глубина поиска также может задавать уровень мастерства программы. Чем дальше вперед программа сможет анализировать ходы, тем лучше она будет играть.

Страницы: 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