- •Глава 1. Основные понятия 14
- •Глава 2. Списки 30
- •Глава 3. Стеки и очереди 59
- •Глава 4. Массивы 74
- •Глава 5. Рекурсия 86
- •Глава 6. Деревья 121
- •Глава 7. Сбалансированные деревья 153
- •Глава 8. Деревья решений 180
- •Глава 9. Сортировка 213
- •Введение
- •Целевая аудитория
- •Глава 1. Основные понятия
- •Что такое алгоритмы?
- •Анализ скорости выполнения алгоритмов
- •Пространство — время
- •Оценка с точностью до порядка
- •Поиск сложных частей алгоритма
- •Сложность рекурсивных алгоритмов
- •Многократная рекурсия
- •Косвенная рекурсия
- •Требования рекурсивных алгоритмов к объему памяти
- •Наихудший и усредненный случай
- •Часто встречающиеся функции оценки порядка сложности
- •Логарифмы
- •Реальные условия — насколько быстро?
- •Обращение к файлу подкачки
- •Псевдоуказатели, ссылки на объекты и коллекции
- •Коллекции
- •Вопросы производительности
- •Глава 2. Списки
- •Знакомство со списками
- •Простые списки
- •Коллекции
- •Список переменного размера
- •Класс SimpleList
- •Неупорядоченные списки
- •Связные списки
- •Добавление элементов к связному списку
- •Удаление элементов из связного списка
- •Уничтожение связного списка
- •Сигнальные метки
- •Инкапсуляция связных списков
- •Доступ к ячейкам
- •Разновидности связных списков
- •Циклические связные списки
- •Проблема циклических ссылок
- •Двусвязные списки
- •Другие связные структуры
- •Псевдоуказатели
- •Глава 3. Стеки и очереди
- •Множественные стеки
- •Очереди
- •Циклические очереди
- •Очереди на основе связных списков
- •Применение коллекций в качестве очередей
- •Приоритетные очереди
- •Многопоточные очереди
- •Модель очереди
- •Глава 4. Массивы
- •Треугольные массивы
- •Диагональные элементы
- •Нерегулярные массивы
- •Прямая звезда
- •Нерегулярные связные списки
- •Разреженные массивы
- •Индексирование массива
- •Очень разреженные массивы
- •Глава 5. Рекурсия
- •Что такое рекурсия?
- •Рекурсивное вычисление факториалов
- •Анализ времени выполнения программы
- •Рекурсивное вычисление наибольшего общего делителя
- •Анализ времени выполнения программы
- •Рекурсивное вычисление чисел Фибоначчи
- •Анализ времени выполнения программы
- •Рекурсивное построение кривых Гильберта
- •Анализ времени выполнения программы
- •Рекурсивное построение кривых Серпинского
- •Анализ времени выполнения программы
- •Опасности рекурсии
- •Бесконечная рекурсия
- •Потери памяти
- •Необоснованное применение рекурсии
- •Когда нужно использовать рекурсию
- •Хвостовая рекурсия
- •Нерекурсивное вычисление чисел Фибоначчи
- •Устранение рекурсии в общем случае
- •Нерекурсивное построение кривых Гильберта
- •Нерекурсивное построение кривых Серпинского
- •Глава 6. Деревья
- •Определения
- •Представления деревьев
- •Полные узлы
- •Списки потомков
- •Представление нумерацией связей
- •Полные деревья
- •Обход дерева
- •Упорядоченные деревья
- •Добавление элементов
- •Удаление элементов
- •Обход упорядоченных деревьев
- •Деревья со ссылками
- •Работа с деревьями со ссылками
- •Квадродеревья
- •Изменение max_per_node
- •Использование псевдоуказателей в квадродеревьях
- •Восьмеричные деревья
- •Глава 7. Сбалансированные деревья
- •Сбалансированность дерева
- •Авл‑деревья
- •Вращения авл‑деревьев
- •Правое вращение
- •Левое вращение
- •Вращение влево‑вправо
- •Вращение вправо‑влево
- •Вставка узлов на языке Visual Basic
- •Удаление узла из авл‑дерева
- •Левое вращение
- •Вращение вправо‑влево
- •Другие вращения
- •Реализация удаления узлов на языке Visual Basic
- •Б‑деревья
- •Производительность б‑деревьев
- •Вставка элементов в б‑дерево
- •Удаление элементов из б‑дерева
- •Разновидности б‑деревьев
- •Нисходящие б‑деревья
- •Улучшение производительности б‑деревьев
- •Балансировка для устранения разбиения блоков
- •Добавление свободного пространства
- •Вопросы, связанные с обращением к диску
- •Псевдоуказатели
- •Выбор размера блока
- •Кэширование узлов
- •Глава 8. Деревья решений
- •Поиск в деревьях игры
- •Минимаксный поиск
- •Улучшение поиска в дереве игры
- •Предварительное вычисление начальных ходов
- •Определение важных позиций
- •Эвристики
- •Поиск в других деревьях решений
- •Метод ветвей и границ
- •Эвристики
- •Восхождение на холм
- •Метод наименьшей стоимости
- •Сбалансированная прибыль
- •Случайный поиск
- •Последовательное приближение
- •Момент остановки
- •Локальные оптимумы
- •Алгоритм «отжига»
- •Сравнение эвристик
- •Другие сложные задачи
- •Задача о выполнимости
- •Задача о разбиении
- •Задача поиска Гамильтонова пути
- •Задача коммивояжера
- •Задача о пожарных депо
- •Краткая характеристика сложных задач
- •Глава 9. Сортировка
- •Общие соображения
- •Объединение и сжатие ключей
- •Примеры программ
- •Сортировка выбором
- •Рандомизация
- •Сортировка вставкой
- •Вставка в связных списках
- •Пузырьковая сортировка
- •Быстрая сортировка
- •Сортировка слиянием
- •Пирамидальная сортировка
- •Пирамиды
- •Приоритетные очереди
- •Анализ пирамид
- •Алгоритм пирамидальной сортировки
- •Сортировка подсчетом
- •Блочная сортировка
- •Блочная сортировка с применением связного списка
- •Блочная сортировка на основе массива
- •Глава 10. Поиск
- •Примеры программ
- •Поиск методом полного перебора
- •Поиск в упорядоченных списках
- •Поиск в связных списках
- •Двоичный поиск
- •Интерполяционный поиск
- •Строковые данные
- •Следящий поиск
- •Интерполяционный следящий поиск
- •Глава 11. Хеширование
- •Связывание
- •Преимущества и недостатки связывания
- •Хранение хеш‑таблиц на диске
- •Связывание блоков
- •Удаление элементов
- •Преимущества и недостатки применения блоков
- •Открытая адресация
- •Линейная проверка
- •Первичная кластеризация
- •Упорядоченная линейная проверка
- •Квадратичная проверка
- •Псевдослучайная проверка
- •Удаление элементов
- •Рехеширование
- •Изменение размера хеш‑таблиц
- •Глава 12. Сетевые алгоритмы
- •Определения
- •Представления сети
- •Оперирование узлами и связями
- •Обходы сети
- •Наименьшие остовные деревья
- •Кратчайший маршрут
- •Установка меток
- •Варианты метода установки меток
- •Коррекция меток
- •Варианты метода коррекции меток
- •Другие задачи поиска кратчайшего маршрута
- •Двухточечный кратчайший маршрут
- •Вычисление кратчайшего маршрута для всех пар
- •Штрафы за повороты
- •Небольшое число штрафов за повороты
- •Большое число штрафов за повороты
- •Применения метода поиска кратчайшего маршрута
- •Разбиение на районы
- •Составление плана работ с использованием метода критического пути
- •Планирование коллективной работы
- •Максимальный поток
- •Приложения максимального потока
- •Непересекающиеся пути
- •Распределение работы
- •Глава 13. Объектно‑ориентированные методы
- •Преимущества ооп
- •Инкапсуляция
- •Обеспечение инкапсуляции
- •Полиморфизм
- •Зарезервированное слово Implements
- •Наследование и повторное использование
- •Парадигмы ооп
- •Управляющие объекты
- •Контролирующий объект
- •Итератор
- •Дружественный класс
- •Интерфейс
- •Порождающий объект
- •Единственный объект
- •Преобразование в последовательную форму
- •Парадигма Модель/Вид/Контроллер.
- •Контроллеры
- •Виды/Контроллеры
- •Требования к аппаратному обеспечению
- •Выполнение программ примеров
Удаление элементов
Удаление элементов из хеш‑таблицы, в которой используется открытая адресация, выполняется не так просто, как удаление их из таблицы, использующей связные списки или блоки. Просто удалить элемент из таблицы нельзя, так как он может находиться в тестовой последовательности другого элемента.
Предположим, что элемент A находится в тестовой последовательности элемента B. Если удалить из таблицы элемент A, найти элемент B будет невозможно. Во время поиска элемента B встретится пустая ячейка, которая осталась после удаления элемента A, поэтому будет сделан неправильный вывод о том, что элемент B отсутствует в таблице.
Вместо удаления элемента из хеш‑таблицы можно просто пометить его как удаленный. Можно использовать эту ячейку позднее, если она встретится во время выполнения вставки нового элемента в таблицу. Если помеченный элемент встречается во время поиска другого элемента, он просто игнорируется и тестовая последовательность продолжится.
После того, как большое число элементов будет помечено как удаленные, в хеш‑таблице может оказаться множество неиспользуемых ячеек, и при поиске элементов достаточно много времени будет уходить на пропуск удаленных элементов. В конце концов, может потребоваться рехеширование таблицы для освобождения неиспользуемой памяти.
Рехеширование
Чтобы освободить удаленные элементы из хеш‑таблицы, можно выполнить ее рехеширование (rehashing) на месте. Чтобы этот алгоритм мог работать, нужно иметь какой‑то способ для определения, было ли выполнено рехеширование элемента. Простейший способ сделать это — определить элементы в виде структур данных, содержащих поле Rehashed.
Type ItemType
Value As Long
Rehashed As Boolean
End Type
Вначале присвоим полю Rehashed значение false. Затем выполним проход по таблице в поиске ячеек, которые не помечены как удаленные, и для которых еще не было выполнено рехеширование.
Если такой элемент встретится, то выполняется его удаление из таблицы и повторное хеширование, при этом выполняется обычная тестовая последовательность для элемента. Если встречается свободная или помеченная как удаленная ячейка, элемент размещается в ней, помечается как рехешированный, и продолжается проверка остальных элементов, для которых еще не было выполнено рехеширование.
Если при выполнении рехеширования найдется элемент, который уже был помечен как рехешированный, то тестовая последовательность продолжается. Если затем встретится элемент, для которого еще не было выполнено рехеширование, то элементы меняются местами, текущая ячейка помечается как рехешированная и процесс начинается снова.
======308
Изменение размера хеш‑таблиц
Если хеш‑таблица становится почти заполненной, производительность значительно падает. В этом случае может понадобиться увеличение размера таблицы, чтобы в ней было больше места для элементов. И наоборот, если в таблице слишком мало ячеек, может потребоваться уменьшить ее, чтобы освободить занимаемую память. Используя методы, похожие на те, которые использовались при рехешировании таблицы на месте, можно увеличивать и уменьшать размер хеш‑таблицы.
Чтобы увеличить хеш‑таблицу, вначале размер массива, в котором она находится, увеличивается при помощи оператора Dim Preserve. Затем выполняется рехеширование таблицы, при этом элементы могут занимать ячейки в созданной свободной области в конце таблицы. После завершения рехеширования таблица будет готова к использованию.
Чтобы уменьшить размер таблицы, вначале определим, сколько элементов должно содержаться в массиве таблицы после уменьшения. Затем выполняем рехеширование таблицы, причем элементы помещаются только в уменьшенную часть таблицы. После завершения рехеширования всех элементов, размер массива уменьшается при помощи оператора ReDim Preserve.
Следующий код демонстрирует рехеширование таблицы с использованием линейной проверки. Код для рехеширования таблицы с использованием квадратичной или псевдослучайной проверки выглядит почти так же:
Public Sub Rehash()
Dim i As Integer
Dim pos As Integer
Dim probes As Integer
Dim Value As Long
Dim new_value As Long
' Пометить все элементы как нерехешированные.
For i = 0 To NumEntries - 1
m_HashTable(i).Rehashed = False
Next i
' Поиск нерехешированных элементов.
For i = 0 To NumEntries - 1
If Not m_HashTable(i).Rehashed Then
Value = m_HashTable(i).Value
m_HashTable(i).Value = UNUSED
If Value <> DELETED And Value <> UNUSED Then
' Выполнить тестовую последовательность
' для этого элемента, пока не найдется свободная,
' удаленная или нерехешированная ячейка.
probes = 0
Do
pos = (Value + probes) Mod NumEntries
new_value = m_HashTable(pos).Value
' Если ячейка свободна или помечена как
' удаленная, поместить элемент в нее.
If new_value = UNUSED Or _
new_value = DELETED _
Then
m_HashTable(pos).Value = Value
m_HashTable(pos).Rehashed = True
Exit Do
End If
' Если ячейка не помечена как рехешированная,
' поменять их местами и продолжить.
If Not m_HashTable(pos).Rehashed Then
m_HashTable(pos).Value = Value
m_HashTable(pos).Rehashed = True
Value = new_value
probes = 0
Else
probes = probes + 1
End If
Loop
End If
End If
Next i
End Sub
Программа Rehash использует открытую адресацию с линейной проверкой. Она аналогична программе Linear, но позволяет также помечать объекты как удаленные и выполнять рехеширование таблицы.
Резюме
Различные типы хеш‑таблиц, описанные в этой главе, имеют свои преимущества и недостатки.
Для хеш‑таблиц, которые используют связные списки или блоки можно легко изменять размер таблицы и удалять из нее элементы. Использование блоков также позволяет легко работать с таблицами на диске, позволяя считать за одно обращение к диску сразу множество элементов данных. Тем не менее, оба эти метода являются более медленными, чем открытая адресация.
Линейная проверка проста и позволяет достаточно быстро вставлять и удалять элементы из таблицы. Применение упорядоченной линейной проверки позволяет быстрее, чем в случае неупорядоченной линейной проверки, установить, что элемент отсутствует в таблице. С другой стороны, вставку элементов в таблицу при этом выполнить сложнее.
Квадратичная проверка позволяет избежать кластеризации, которая характерна для линейной проверки, и поэтому обеспечивает более высокую производительность. Псевдослучайная проверка обеспечивает еще более высокую производительность, так как при этом удается избавиться как от первичной, так и от вторичной кластеризации.
В табл. 11.5 приведены преимущества и недостатки различных методов хеширования.
======310
@Таблица 11.5. Преимущества и недостатки различных методов хеширования
Выбор наилучшего метода хеширования для данного приложения зависит от данных задачи и способов их использования. При применении разных схем достигаются различные компромиссы между занимаемой памятью, скоростью и простотой изменений. Табл. 11.5 может помочь вам выбрать наилучший алгоритм для вашего приложения.
=======311