Алгоритмы и структуры данных. Извлечение информации на языке Java
Изучите, как следует реализовывать эффективные алгоритмы на основе важнейших структур данных на языке Java, а также как измерять производительность этих алгоритмов. Каждая глава сопровождается упражнениями, помогающими закрепить материал.
- Научитесь работать со структурами данных, например, со списками и словарями, разберитесь, как они работают.
- Напишите приложение, которое читает страницы Википедии, выполняет синтаксический разбор и обеспечивает навигацию по полученному дереву данных.
- Анализируйте код и учитесь прогнозировать, как быстро он будет работать и сколько памяти при этом потреблять.
- Пишите классы, реализующие интерфейс Map, пользуйтесь при этом хеш-таблицей и двоичным деревом поиска.
- Создайте простой веб-поисковик с собственным поисковым роботом: он будет индексировать веб-страницы, сохранять их содержимое и возвращать нужные результаты.
Предисловие................................................................................12
Философия книги....................................................................12
Обязательные условия............................................................14
Работа с кодом.......................................................................15
Условные обозначения...........................................................16
Соавторы................................................................................17
Глава 1. Интерфейсы ............................................................... 19
Почему существует два типа List.............................................20
Интерфейсы в Java.................................................................21
Интерфейс List........................................................................22
Упражнение 1.........................................................................25
Глава 2. Анализ алгоритмов ..................................................... 28
Сортировка выбором..............................................................30
Нотация «О» большого...........................................................33
Упражнение 2.........................................................................35
Глава 3. Класс ArrayList ............................................................ 40
Классификация методов MyArrayList.......................................40
Классификация версий метода add.........................................43
Размер задачи........................................................................46
Связные структуры данных.....................................................47
Упражнение 3.........................................................................51
Примечание о сборке мусора..................................................54
Глава 4. Класс LinkedList .......................................................... 56
Классификация методов MyLinkedList......................................56
Сравнение MyArrayList и MyLinkedList......................................60
Профилирование....................................................................61
Интерпретация результатов....................................................65
Упражнение 4.........................................................................67
Глава 5. Двусвязный список ..................................................... 69
Результаты профилирования производительности..................69
Профилирование производительности
методов LinkedList...................................................................73
Добавление в конец LinkedList................................................74
Двусвязный список.................................................................78
Выбор структуры....................................................................79
Глава 6. Обход дерева ............................................................. 82
Поисковые системы................................................................82
Парсинг HTML.........................................................................84
Применение jsoup...................................................................86
Итерация по дереву DOM........................................................90
Поиск в глубину......................................................................91
Стеки в Java............................................................................92
Итеративный поиск в глубину.................................................94
Глава 7. Путь к философии ...................................................... 97
Начало разработки.................................................................97
Интерфейсы Iterable и Iterator................................................98
WikiFetcher.............................................................................101
Упражнение 5........................................................................103
Глава 8. Индексатор ................................................................ 106
Выбор структуры данных.......................................................107
TermCounter...........................................................................109
Упражнение 6........................................................................112
Глава 9. Интерфейс Map ......................................................... 118
Реализация MyLinearMap........................................................118
Упражнение 7........................................................................120
Анализ MyLinearMap...............................................................121
Глава 10. Хеширование ........................................................... 125
Хеширование.........................................................................125
Как работает хеширование....................................................128
Хеширование и изменяемость................................................131
Упражнение 8........................................................................133
Глава 11. HashMap .................................................................. 135
Упражнение 9........................................................................136
Анализ MyHashMap................................................................137
Компромиссные решения.......................................................140
Профилирование MyHashMap.................................................141
Исправление MyHashMap.......................................................142
Диаграммы классов UML........................................................145
Глава 12. TreeMap ................................................................... 149
Что не так с хешированием....................................................149
Бинарное дерево поиска........................................................151
Упражнение 10......................................................................154
Реализация TreeMap..............................................................155
Глава 13. Бинарное дерево поиска ......................................... 160
Простая реализация MyTreeMap.............................................160
Поиск по значению................................................................162
Реализация put......................................................................164
Симметричный обход.............................................................166
Методы, выполняющиеся за логарифмическое время............168
Самобалансирующиеся деревья.............................................172
Дополнительное упражнение.................................................173
Глава 14. Сохраняемость ........................................................ 174
Redis......................................................................................175
Клиенты и серверы Redis.......................................................177
Создание индекса на основе Redis.........................................178
Типы данных Redis.................................................................181
Упражнение 11......................................................................184
Дополнительные рекомендации.............................................186
Несколько советов по проектированию..................................188
Глава 15. Сбор данных в «Википедии» .................................... 190
Индексатор на основе Redis...................................................190
Анализ поиска.......................................................................194
Анализ индексирования.........................................................195
Обход графа..........................................................................196
Упражнение 12......................................................................198
Глава 16. Логический поиск .................................................... 202
Решение для поискового робота............................................202
Поиск информации................................................................206
Логический поиск..................................................................207
Упражнение 13......................................................................208
Интерфейсы Comparable и Comparator...................................211
Дополнения...........................................................................214
Глава 17. Сортировка .............................................................. 216
Сортировка вставкой.............................................................217
Упражнение 14......................................................................220
Анализ сортировки слиянием.................................................222
Поразрядная сортировка.......................................................226
Пирамидальная сортировка...................................................229
Ограниченная куча................................................................232
Пространственная сложность.................................................233
Об авторе...................................................................................235
Об обложке................................................................................236
Изучаем Python, том 1, 5-е издание3 280 ₽
Java. Полное руководство, 10-е издание4 430 ₽
Анализ ценных бумаг. 3-е издание5 690 ₽