Продвинутые алгоритмы и структуры данных

Предисловие
Вступление
Благодарности
О книге
Кому адресована эта книга
Структура книги
О примерах программного кода
От издательства
Об авторе
Иллюстрация на обложке
Глава 1. Введение в структуры данных
1.1. Структуры данных
1.1.1. Определение структуры данных
1.1.2. Описание структуры данных
1.1.3. Алгоритмы и структуры данных: так есть ли разница?
1.2. Целеполагание: ваши ожидания от прочтения этой книги
1.3. Собираем рюкзак: структуры данных в реальном мире
1.3.1. Абстрагирование задачи
1.3.2. Поиск решений
1.3.3. Спасительные алгоритмы
1.3.4. Выходим за рамки (в буквальном смысле)
1.3.5. Счастливый конец
Резюме
Часть I. Улучшаем базовые структуры данных
Глава 2. Улучшаем очереди с приоритетом: d-кучи
2.1. Структура этой главы
2.2. Задача: как работать с приоритетами?
2.2.1. Приоритеты на практике: отслеживание ошибок
2.3. Простое решение: храним отсортированный список
2.3.1. От отсортированных списков к очередям с приоритетом
2.4. Описание API структуры данных: очереди с приоритетом
2.4.1. Примеры работы очереди с приоритетом
2.4.2. Приоритет имеет значение: обобщаем FIFO
2.5. Конкретные структуры данных
2.5.1. Сравнение производительности
2.5.2. Какая конкретная структура данных наиболее верна?
2.5.3. Куча
2.5.4. Приоритет, неубывающая и невозрастающая куча
2.5.5. Продвинутый вариант: d-куча
2.6. Как реализовать кучу
2.6.1. BubbleUp
2.6.2. PushDown
2.6.3. Вставка
2.6.4. Метод top
2.6.5. Метод update
2.6.6. Обработка дубликатов
2.6.7. Преобразование в кучу
2.6.8. Методы вне API: contains
2.6.9. Еще раз о производительности
2.6.10. От псевдокода к реализации
2.7. Пример: поиск k наибольших элементов
2.7.1. Правильная структура данных...
2.7.2. ...И правильное ее использование
2.7.3. Реализация
2.8. Другие случаи использования
2.8.1. Поиск кратчайшего пути в графе: алгоритм Дейкстры
2.8.2. Еще о графах: алгоритм Прима
2.8.3. Сжатие данных: коды Хаффмана
2.9. Анализ коэффициента ветвления
2.9.1. Нужны ли d-ичные кучи?
2.9.2. Время выполнения
2.9.3. Поиск оптимального коэффициента ветвления
2.9.4. Коэффициент ветвления и память
2.10. Анализ производительности: поиск наилучшего коэффициента ветвления
2.10.1. Добро пожаловать в профилирование
2.10.2. Интерпретация результатов
2.10.3. Загадка _heapify
2.10.4. Выбор лучшего коэффициента ветвления
Резюме
Глава 3. Декартовы деревья: применение рандомизации для получения сбалансированных двоичных деревьев поиска
3.1. Задача: множественная индексация
3.1.1. Суть решения
3.2. Решение: описание и API
3.3. Декартово дерево
3.3.1. Поворот
3.3.2. Несколько вопросов по организации
3.3.3. Реализация поиска
3.3.4. Вставка
3.3.5. Удаление
3.3.6. Методы top, peek и update
3.3.7. Методы min и max
3.3.8. Еще раз о производительности
3.4. Применение: рандомизированные декартовы деревья
3.4.1. Сбалансированные деревья
3.4.2. Введение в рандомизацию
3.4.3. Применение рандомизированных декартовых деревьев
3.5. Анализ производительности и профилирование
3.5.1. Теория: ожидаемая высота
3.5.2. Экспериментальное определение высоты
3.5.3. Профилирование времени выполнения
3.5.4. Профилирование потребления памяти
3.5.5. Выводы
Резюме
Глава 4. Фильтры Блума: отслеживание содержимого с меньшими затратами памяти
4.1. Словари: отслеживание содержимого
4.2. Альтернативы реализации словаря
4.3. Описание API структуры данных: ассоциативный массив
4.4. Конкретные структуры данных
4.4.1. Несортированный массив: быстрая вставка, медленный поиск
4.4.2. Отсортированные массивы и поиск методом дихотомии: медленная вставка, быстрый поиск
4.4.3. Хеш-таблица: в среднем время постоянно, если порядок неважен
4.4.4. Двоичное дерево поиска: логарифмическое время выполнения всех операций
4.4.5. Фильтр Блума: так же быстр, как хеш-таблицы, при этом экономит память (но есть подвох)
4.5. За кулисами: как работают фильтры Блума
4.6. Реализация
4.6.1. Использование фильтра Блума
4.6.2. Чтение и запись битов
4.6.3. Поиск места, где хранится ключ
4.6.4. Генерирование хеш-функций
4.6.5. Конструктор
4.6.6. Проверка ключа
4.6.7. Сохранение ключа
4.6.8. Оценка точности
4.7. Применение
4.7.1. Кэш
4.7.2. Маршрутизаторы
4.7.3. Интернет-роботы
4.7.4. Сборщик операций ввода/вывода
4.7.5. Проверка орфографии
4.7.6. Распределенные базы данных и файловые системы
4.8. Как работают фильтры Блума
4.8.1. Почему невозможны ложноотрицательные результаты проверок...
4.8.2. ...Но ложноположительные возможны
4.8.3. Фильтры Блума как рандомизированные алгоритмы
4.9. Анализ производительности
4.9.1. Время выполнения
4.9.2. Конструктор
4.9.3. Сохранение элемента
4.9.4. Поиск элемента
4.10. Оценка точности фильтра Блума
4.10.1. Объяснение формулы отношения ложноположительных результатов
4.11. Улучшенные варианты
4.11.1. Фильтр Блумьера
4.11.2. Комбинирование фильтров Блума
4.11.3. Многослойный фильтр Блума
4.11.4. Сжатый фильтр Блума
4.11.5. Масштабируемый фильтр Блума
Резюме
Глава 5. Непересекающиеся множества: обработка за сублинейное время
5.1. Задача разделения на подмножества
5.2. Размышления о возможных решениях
5.3. Описание API структуры данных: непересекающееся множество
5.4. Простейшее решение
5.4.1. Реализация простейшего решения
5.5. Использование древовидной структуры
5.5.1. От списка к деревьям
5.5.2. Реализация версии с деревьями
5.6. Эвристика для улучшения времени выполнения
5.6.1. Сжатие пути
5.6.2. Реализация балансировки и сжатия пути
5.7. Применение
5.7.1. Графы: связанные компоненты
5.7.2. Графы: алгоритм Краскала для минимального остовного дерева
5.7.3. Кластеризация
5.7.4. Унификация
Резюме
Глава 6. Префиксные деревья, компактные префиксные деревья: эффективный поиск строк
6.1. Проверка орфографии
6.1.1. Прнцесса, Деймон и эльф звходят в бар
6.1.2. Сжатие — ключ к успеху
6.1.3. Описание и API
6.2. Префиксное дерево
6.2.1. Почему снова лучше?
6.2.2. Поиск
6.2.3. Вставка
6.2.4. Удаление
6.2.5. Самый длинный префикс
6.2.6. Ключи, соответствующие префиксу
6.2.7. Когда следует использовать префиксные деревья
6.3. Компактные префиксные деревья
6.3.1. Узлы и ребра
6.3.2. Поиск
6.3.3. Вставка
6.3.4. Удаление
6.3.5. Самый длинный общий префикс
6.3.6. Поиск ключей, начинающихся с префикса
6.4. Варианты применения
6.4.1. Проверка орфографии
6.4.2. Сходство строк
6.4.3. Сортировка строк
6.4.4. T9
6.4.5. Автодополнение
Резюме
Глава 7. Примеры использования: кэш LRU
7.1. Не вычисляйте одно и то же дважды
7.2. Первая попытка: запоминание значений
7.2.1. Описание и API
7.2.2. Освежите данные, пожалуйста
7.2.3. Обработка асинхронных вызовов
7.2.4. Маркировка значений в кэше признаком «загружается»
7.3. Нехватка памяти (буквально)
7.4. Удаление устаревших данных: кэш LRU
7.4.1. Иногда важно удвоить усилия для решения проблем
7.4.2 Упорядочение по времени
7.4.3. Производительность
7.5. Когда более свежие данные ценнее: LFU
7.5.1. Как сделать правильный выбор?
7.5.2. Отличительные особенности LFU
7.5.3. Производительность
7.5.4. Недостатки политики LFU
7.6. Порядок использования кэша не менее важен
7.7. Введение в синхронизацию
7.7.1. Решение проблемы параллельного выполнения (на Java)
7.7.2. Блокировки
7.7.3. Получение блокировки
7.7.4. Реентерабельные блокировки
7.7.5. Блокировки для чтения
7.7.6. Другие подходы к решению проблемы параллелизма
7.8. Примеры применения кэша
Резюме
Часть II. Многомерные запросы
Глава 8. Поиск ближайших соседей
8.1. Задача поиска ближайшего соседа
8.2. Решения
8.2.1. Первые попытки
8.2.2. Иногда кэширование не является решением
8.2.3. Упрощение, дающее подсказку
8.2.4. Тщательно выбирайте структуру данных
8.3. Описание и API
8.4. Переход к k-мерным пространствам
8.4.1. Одномерный двоичный поиск
8.4.2. Переход к более высоким измерениям
8.4.3. Моделирование двумерных разделов с помощью структуры данных
Резюме
Глава 9. K-мерные деревья: индексирование многомерных данных
9.1. Продолжаем с того места, на котором остановились
9.2. Переход к k-мерным пространствам: циклический перебор измерений
9.2.1. Конструирование двоичного дерева поиска
9.2.2. Инварианты
9.2.3. Важность сбалансированности
9.3. Методы
9.3.1. Метод search
9.3.2. Метод insert
9.3.3. Сбалансированное дерево
9.3.4. Метод remove
9.3.5. Ближайший сосед
9.3.6. Поиск области
9.3.7. Обзор всех методов
9.4. Ограничения и возможные улучшения
Резюме
Глава 10. Деревья поиска по сходству: приближенный поиск ближайших соседей для выбора похожих изображений
10.1. Продолжаем с того места, на котором остановились
10.1.1. Новый более сложный пример
10.1.2. Преодоление недостатков k-мерных деревьев
10.2. R-дерево
10.2.1. Шаг назад: знакомство с B-деревьями
10.2.2. От B-дерева к R-дереву
10.2.3. Вставка точек в R-дерево
10.2.4. Поиск
10.3. Деревья поиска по сходству
10.3.1. Поиск в SS-дереве
10.3.2. Вставка
10.3.3. Вставка: дисперсия, средние значения и проекции
10.3.4. Вставка: разделение узлов
10.3.5. Удаление
10.4. Поиск по сходству
10.4.1. Поиск ближайшего соседа
10.4.2. Поиск области
10.4.3. Приближенный поиск по сходству
10.5. Деревья SS+
10.5.1. SS-деревья лучше?
10.5.2. Смягчение недостатков гиперсфер
10.5.3. Улучшение эвристики разделения
10.5.4. Уменьшение площади перекрытия
Резюме
Глава 11. Применение поиска ближайшего соседа на практике
11.1. Приложение: поиск ближайшего склада
11.1.1. Набросок решения
11.1.2. Неожиданные проблемы
11.2. Централизованное приложение
11.2.1. Фильтрация точек
11.2.2. Сложные решения
11.3. Переход к распределенному приложению
11.3.1. Проблемы, связанные со взаимодействиями через HTTP
11.3.2. Синхронизация информации о товарах на складах
11.3.3. Извлеченные уроки
11.4. Другие приложения
11.4.1. Уменьшение количества цветов
11.4.2. Взаимодействие частиц
11.4.3. Оптимизация многомерных запросов к БД
11.4.4. Кластеризация
Резюме
Глава 12. Кластеризация
12.1. Введение в кластеризацию
12.1.1. Типы обучения
12.1.2. Типы кластеризации
12.2. K-средних
12.2.1. Недостатки алгоритма k-средних
12.2.2. Проклятие размерности снова в действии
12.2.3. Анализ производительности метода k-средних
12.2.4. Ускорение метода k-средних с помощью k-мерных деревьев
12.2.5. Заключительные замечания об алгоритме кластеризации методом k-средних
12.3. DBSCAN
12.3.1. Прямая достижимость и достижимость по плотности
12.3.2. От определений к алгоритму
12.3.3. И наконец, реализация
12.3.4. Достоинства и недостатки DBSCAN
12.4. OPTICS
12.4.1. Определения
12.4.2. Алгоритм OPTICS
12.4.3. От расстояния достижимости к кластеризации
12.4.4. Иерархическая кластеризация
12.4.5. Анализ производительности и заключительные замечания
12.5. Оценка результатов кластеризации: метрики оценки
12.5.1. Интерпретация результатов
Резюме
Глава 13. Параллельная кластеризация: MapReduce и кластеризация методом купола
13.1. Параллельные вычисления
13.1.1. Параллельные и распределенные вычисления
13.1.2. Распараллеливание метода k-средних
13.1.3. Кластеризация методом купола
13.1.4. Применение кластеризации методом купола
13.2. MapReduce
13.2.1. Представьте, что вы Дональд Дак...
13.2.2. Сначала отображение, потом свертка
13.2.3. Еще кое-что
13.3. Реализация метода k-средних с помощью модели MapReduce
13.3.1. Распараллеливание кластеризации методом купола
13.3.2. Инициализация центроидов с помощью кластеризации методом купола
13.3.3. Кластеризация методом купола с использованием модели MapReduce
13.4. Реализация DBSCAN с использованием MapReduce
Резюме
Часть III. Планарные графы и минимальное число пересечений
Глава 14. Введение в графы: поиск кратчайшего пути
14.1. Определения
14.1.1. Реализация графов
14.1.2. Графы как алгебраические типы
14.1.3. Псевдокод
14.2. Свойства графа
14.2.1. Неориентированный
14.2.2. Связный
14.2.3. Ациклический
14.3. Обход графа: алгоритмы BFS и DFS
14.3.1. Оптимизация маршрутов доставки
14.3.2. Поиск в ширину
14.3.3. Реконструкция пути к цели
14.3.4. Поиск в глубину
14.3.5. И снова о выборе между очередью и стеком
14.3.6. Лучший маршрут доставки посылки
14.4. Кратчайший путь во взвешенных графах: алгоритм Дейкстры
14.4.1. Отличия от BFS
14.4.2. Реализация
14.4.3. Анализ
14.4.4. Кратчайший путь доставки
14.5. За пределами алгоритма Дейкстры: A×
14.5.1. Насколько хорош алгоритм A×?
14.5.2. Эвристика как способ балансировки в реальном времени
Резюме
Глава 15. Представление графов и планарность: рисование графа с минимальным числом пересечений ребер
15.1. Представление графов
15.1.1. Некоторые основные определения
15.1.2. Полные и двудольные графы
15.2. Планарные графы
15.2.1. Практическое применение теоремы Куратовского
15.2.2. Проверка планарности
15.2.3. Наивный алгоритм проверки планарности
15.2.4. Увеличение производительности
15.2.5. Эффективные алгоритмы
15.3. Непланарные графы
15.3.1. Поиск числа пересечений
15.3.2. Количество прямолинейных пересечений
15.4. Пересечения ребер
15.4.1. Прямолинейные отрезки
15.4.2. Ломаные линии
15.4.3. Кривые Безье
15.4.4. Пересечение квадратичных кривых Безье
15.4.5. Пересечения вершина-вершина и ребро-вершина
Резюме
Глава 16. Градиентный спуск: оптимизация задач (не только) на графах
16.1. Эвристика для определения числа пересечений
16.1.1. Мне послышалось, вы только что сказали «эвристики»?
16.1.2. Расширение до поддержки криволинейных ребер
16.2. Как работает оптимизация
16.2.1. Функции стоимости
16.2.2. Ступенчатые функции и локальные минимумы
16.2.3. Оптимизация случайной выборки
16.3. Градиентный спуск
16.3.1. Математика градиентного спуска
16.3.2. Геометрическая интерпретация
16.3.3. Когда применяется градиентный спуск?
16.3.4. Задачи с градиентным спуском
16.4. Применение градиентного спуска
16.4.1. Пример: линейная регрессия
16.5. Градиентный спуск для поиска представления графа
16.5.1. Другие критерии
16.5.2. Реализация
Резюме
Глава 17. Имитация отжига: оптимизация за пределами локальных минимумов
17.1. Имитация отжига
17.1.1. Иногда нужно подняться, чтобы спуститься
17.1.2. Реализация
17.1.3. Почему имитация отжига работает
17.1.4. Переходы на короткие и большие расстояния
17.1.5. Варианты
17.1.6. Имитация отжига или градиентный спуск: что использовать?
17.2. Имитация отжига + коммивояжер
17.2.1. Точное и приближенное решения
17.2.2. Визуализация стоимости
17.2.3. Сужение пространства задачи
17.2.4. Переходы между состояниями
17.2.5. Перестановка смежных и случайно выбранных вершин
17.2.6. Применение решения задачи о коммивояжере
17.3. Имитация отжига и представление графа
17.3.1. Минимальное число пересечений ребер
17.3.2. Силовые алгоритмы визуализации
Резюме
Глава 18. Генетические алгоритмы: заимствованная из биологии быстросходящаяся оптимизация
18.1. Генетические алгоритмы
18.1.1. Заимствование у природы
18.1.2. Хромосомы
18.1.3. Популяция
18.1.4. Приспособленность
18.1.5. Естественный отбор
18.1.6. Отбор индивидуумов для спаривания
18.1.7. Скрещивание
18.1.8. Мутации
18.1.9. Шаблон генетического алгоритма
18.1.10. Когда генетический алгоритм работает лучше всего?
18.2. Задача о коммивояжере
18.2.1. Приспособленность, хромосомы и инициализация
18.2.2. Мутации
18.2.3. Скрещивание
18.2.4. Настройка результатов и параметров
18.2.5. За пределами задачи о коммивояжере: оптимизация маршрутов для всего парка грузовиков
18.3. Минимальное вершинное покрытие
18.3.1. Практическое применение вершинного покрытия
18.3.2. Реализация генетического алгоритма
18.4. Другие применения генетического алгоритма
18.4.1. Максимальный поток
18.4.2. Свертывание белков
18.4.3. За пределами генетических алгоритмов
18.4.4. За пределами круга алгоритмов, рассмотренных в этой книге
Резюме
Приложения
Приложение А. Краткое руководство по псевдокоду
A.1. Переменные и основы синтаксиса
A.2. Массивы
A.3. Условные инструкции
A.3.1. else-if
А.3.2. switch
A.4. Циклы
A.4.1. Цикл for
A.4.2. Цикл while
A.4.3. break и continue
A.5. Блоки и отступы
А.6. Функции
A.6.1. Перегрузка и аргументы по умолчанию
A.6.2. Кортежи
A.6.3. Кортежи и деструктурирование объектов
Приложение Б. Нотация «О большое»
Б.1. Алгоритмы и производительность
Б.2. Модель памяти
Б.3. Порядок величины
Б.4. Нотация
Б.5. Примеры
Приложение В. Основные структуры данных
В.1. Основные структуры данных
В.2. Массив
В.3. Связанный список
В.4. Дерево
В.4.1. Двоичные деревья поиска
В.5. Хеш-таблица
В.5.1. Хранение пар «ключ — значение»
В.5.2. Хеширование
В.5.3. Разрешение коллизий в хешировании
В.5.4. Производительность
В.6. Сравнительный анализ основных структур данных
Приложение Г. Контейнеры в роли очередей с приоритетами
Г.1. Мультимножество
Г.2. Стек
Г.3. Очередь
Г.4. Сравнительный анализ контейнеров
Приложение Д. Рекурсия
Д.1. Простая рекурсия
Д.1.1. Ловушки
Д.1.2. Оправданная рекурсия
Д.2. Хвостовая рекурсия
Д.3. Взаимная рекурсия
Приложение Е. Задачи классификации и рандомизированные алгоритмы
Е.1. Задачи принятия решений
Е.2. Алгоритмы Лас-Вегаса
Е.3. Алгоритмы Монте-Карло
Е.4. Метрики классификации
Е.4.1. Достоверность
Е.4.2. Точность и полнота
Е.4.3. Другие метрики и подведение итогов