Вам почти никогда не придется реализовать хеш-таблицу самостоятельно. Язык программирования, который вы используете, должен предоставить необходимую реализацию. Вы можете пользоваться хеш-таблицами Python, и при этом вам будет обеспечена производительность среднего случая: постоянное время.
Хеш-таблицы чрезвычайно полезны, потому что они обеспечивают высокую скорость операций и позволяют по-разному моделировать данные. Возможно, вскоре выяснится, что вы постоянно используете их в своей работе.
• Хеш-таблица создается объединением хеш-функции с массивом.
• Коллизии нежелательны. Хеш-функция должна свести количество коллизий к минимуму.
• Хеш-таблицы обеспечивают очень быстрое выполнение поиска, вставки и удаления.
• Хеш-таблицы хорошо подходят для моделирования отношений между объектами.
• Как только коэффициент заполнения превышает 0,7, пора изменять размер хеш-таблицы.
• Хеш-таблицы используются для кэширования данных (например, на веб-серверах).
• Хеш-таблицы хорошо подходят для обнаружения дубликатов.
В этой главе
• Вы научитесь моделировать сети при помощи новой абстрактной структуры данных — графов.
• Вы освоите поиск в ширину — алгоритм, который применяется к графам для получения ответов на вопросы вида «Какой кратчайший путь ведет к X?»
• Вы узнаете, чем направленные графы отличаются от ненаправленных.
• Вы освоите топологическую сортировку — другой алгоритм сортировки, раскрывающий связи между узлами.
Эта глава посвящена графам. Сначала вы узнаете, что такое граф. Затем я покажу первый алгоритм, работающий с графами. Он называется
Поиск в ширину позволяет найти кратчайшее расстояние между двумя объектами. Однако сам термин «кратчайшее расстояние» может иметь много разных значений! Например, с помощью поиска в ширину можно:
• написать программу для игры в шашки, которая вычисляет кратчайший путь к победе;
• реализовать проверку правописания (минимальное количество изменений, преобразующих ошибочно написанное слово в правильное, например АЛГОРИФМ -> АЛГОРИТМ — одно изменение);
• найти ближайшего к вам врача.
Одни из самых полезных алгоритмов, известных мне, работают с графами. Внимательно прочитайте несколько следующих глав — этот материал неоднократно пригодится вам в работе.
Предположим, вы находитесь в Сан-Франциско и хотите добраться из Твин-Пикс к мосту Золотые Ворота. Вы намереваетесь доехать на автобусе с минимальным количеством пересадок. Возможные варианты:
Какой алгоритм вы бы использовали для поиска пути с наименьшим количеством шагов?
Можно ли сделать это за один шаг? На следующем рисунке выделены все места, в которые можно добраться за один шаг.
Мост на этой схеме не выделен; до него невозможно добраться за один шаг. А можно ли добраться до него за два шага?
И снова мост не выделен, а значит, до него невозможно добраться за два шага. Как насчет трех шагов?
Ага! На этот раз мост Золотые Ворота выделен. Следовательно, чтобы добраться из Твин-Пикс к мосту по этому маршруту, необходимо сделать три шага.
Есть и другие маршруты, которые приведут вас к мосту, но они длиннее (четыре шага). Алгоритм обнаружил, что кратчайший путь к мосту состоит из трех шагов. Задача такого типа называется
Чтобы найти кратчайший путь из Твин-Пикс к мосту Золотые Ворота, нам пришлось выполнить два шага:
1. Смоделировать задачу в виде графа.
2. Решить задачу методом поиска в ширину.
В следующем разделе я расскажу, что такое графы. Затем будет рассмотрен более подробно поиск в ширину.
Граф моделирует набор связей. Представьте, что вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, условие «Алекс должен Раме» можно смоделировать так:
А полный граф может выглядеть так:
Граф задолженностей при игре в покер
Алекс должен Раме, Том должен Адиту и т.д. Каждый граф состоит из
Вот и все! Графы состоят из узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются
