Однако с хеш-таблицами возникают проблемы: иногда хеш-функция возвращает одинаковую позицию для разных входных данных. Такая ситуация называется хеш-коллизией. Когда она происходит, все такие элементы должны быть сохранены в одной позиции в памяти (эта проблема решается, например, посредством связного списка, который начинается с заданного адреса). Хеш-коллизии влекут за собой издержки процессорного времени и памяти, поэтому их желательно избегать.
Хорошая хеш-функция должна возвращать разные значения для разных входных данных. Следовательно, чем шире диапазон значений, которые может вернуть хеш-функция, тем больше будет доступно позиций для данных и меньше вероятность возникновения хеш-коллизии. Поэтому нужно гарантировать, чтобы в хеш-таблице оставалось незанятым по крайней мере 50 % пространства. В противном случае коллизии начнут происходить слишком часто и производительность хеш-таблицы значительно упадет.
Хеш-таблицы часто используются для реализации словарей и множеств. Они позволяют выполнять операции вставки и удаления быстрее, чем структуры данных, основанные на деревьях.
С другой стороны, для корректной работы хеш-таблицы требуют выделения очень большого блока непрерывной памяти.
Подведем итоги
Мы узнали, что структуры данных определяют конкретные способы организации элементов в памяти компьютера. Разные структуры данных требуют разных операций для хранения, удаления, поиска и обхода хранящихся данных. Чудодейственного средства не существует: всякий раз нужно выбирать, какую структуру данных использовать в соответствии с текущей ситуацией.
Еще мы узнали, что вместо структур данных лучше иметь дело с АТД. Они освобождают код от деталей, связанных с обработкой данных, и позволяют легко переключаться с одной структуры на другую без каких-либо изменений в коде.
Не изобретайте колесо заново, пытаясь с нуля создавать базовые структуры данных и абстрактные типы данных (если только вы не делаете это ради забавы, обучения или исследования). Пользуйтесь проверенными временем сторонними библиотеками обработки данных. Большинство языков имеет встроенную поддержку этих структур.
Полезные материалы
• Балансировка двоичного дерева поиска (Balancing a Binary Search Tree, Stoimen, см. https://code.energy/stoimen).
• Лекция Корнелльского университета по абстрактным типам данных и структурам данных (Cornell Lecture on Abstract Data Types and Data Structures, см. https://code.energy/cornell-adt).
• Конспекты IITKGP по абстрактным типам данных (IITKGP notes on Abstract Data Types, см. https://code.energy/iitkgp).
• Реализация дерева поиска на «интерактивном Python» (Search Tree Implementation by “Interactive Python”, см. https://code.energy/python-tree).
Глава 5. Алгоритмы
[Программирование является] привлекательным занятием не только потому, что оно перспективно с экономической и научной точек зрения, но и потому, что оно во многом может стать эстетическим опытом, как сочинение стихов или музыки.
Дональд Кнут
Человечество изыскивает решения все более и более трудных задач. В большинстве случаев вам приходится иметь дело с задачами, над примерными аналогами которых уже потрудились многие разработчики. Вполне вероятно, что они придумали эффективные алгоритмы, которые можно брать и использовать. Когда вы решаете задачи, вашим первым шагом всегда должен быть поиск существующих алгоритмов
[51]. В этой главе мы займемся исследованием хорошо известных алгоритмов, которые:
эффективно сортируют очень длинные списки;
быстро отыскивают нужный элемент;
оперируют и управляют графами;
используют исследование операций для оптимизации процессов.
Вы научитесь распознавать проблемы, к которым можно применить известные решения. Существует много различных типов задач: сортировка данных, поиск закономерностей (образов, шаблонов), прокладывание маршрута и др. И многие типы алгоритмов имеют непосредственное отношение к областям научно-практических исследований: обработке изображений, криптографии, искусственному интеллекту… В этой книге мы не сможем охватить их все
[52]. Однако мы изучим самые важные алгоритмы, с которыми должен быть знаком любой хороший программист.
5.1. Сортировка
До появления компьютеров сортировка данных была известной проблемой, ее ручное выполнение занимало колоссальное количество времени. Когда в 1890-х годах компания Tabulating Machine Company (которая позже стала называться IBM) автоматизировала операции сортировки, это позволило на несколько лет быстрее обработать данные переписи населения США.
Существует много алгоритмов сортировки. Более простые имеют временную сложность O(n2). Сортировка выбором (см. раздел «Оценка затрат времени» главы 2) — один из таких алгоритмов. Именно его люди предпочитают использовать для сортировки физической колоды карт. Сортировка выбором принадлежит многочисленной группе алгоритмов с квадратичной стоимостью. Мы, как правило, используем их для упорядочивания наборов данных, состоящих меньше чем из 1000 элементов. Одним из известных алгоритмов является сортировка вставками. Он показывает очень хорошую эффективность в сортировке уже почти упорядоченных наборов данных даже очень большого объема:
function insertion_sort(list)
