Математика структур данных помогает нам понять, как различные системы хранения данных предполагают разные компромиссы между временем, памятью и другими ресурсами. Комментарий Сохранить статью Прочитать позже
В сфере хранения данных иногда лучше смириться с некоторым беспорядком.
Введение
Так же, как не существует единственного наилучшего способа организовать книжную полку, не существует и универсального решения для хранения информации.
Рассмотрим простую ситуацию, когда вы создаете новый цифровой файл. Вашему компьютеру необходимо быстро найти место для его сохранения. Если позже вы захотите его удалить, машина должна быстро найти нужные биты для стирания. Исследователи стремятся разработать системы хранения данных, называемые структурами данных, которые обеспечивают баланс между временем, необходимым для добавления данных, временем, необходимым для их последующего удаления, и общим объемом памяти, необходимым для системы.
Чтобы понять эти сложности, представьте, что все ваши книги лежат в ряд на одной длинной полке. Если они рассортированы по алфавиту, вы можете быстро найти любую книгу. Но каждый раз, когда вы приобретаете новую книгу, вам потребуется время, чтобы найти её на нужном месте. И наоборот, если вы размещаете книги там, где есть место, вы экономите время сейчас, но потом их будет трудно найти. Этот компромисс между временем на размещение и временем на поиск может не быть проблемой для библиотеки с одной полкой, но вы можете представить, насколько это может стать обременительным при наличии тысяч книг.
Вместо полки можно расставить 26 ящиков с алфавитными надписями и распределить книги по ящикам в зависимости от первой буквы фамилии автора. Когда вы покупаете новую книгу, вы сразу понимаете, в какой ящик её нужно положить, и когда вам нужно достать книгу, вы сразу же знаете, где её искать. В некоторых ситуациях и вставка, и извлечение книг могут быть намного быстрее, чем если бы вы хранили их на одной длинной полке.
Конечно, у этой системы ящиков есть свои проблемы. Найти нужные книги можно мгновенно только если в каждом ящике по одной книге; в противном случае придётся долго искать. В крайнем случае, если все ваши книги — это произведения Азимова, Этвуд и Остин, вы снова столкнётесь с проблемой одной длинной полки, плюс к этому у вас будет куча пустых ящиков, загромождающих гостиную.
Специалисты по информатике часто изучают структуры данных, называемые хеш-таблицами, которые напоминают более сложные версии этой простой системы ячеек. Хеш-таблицы вычисляют адрес хранения для каждого элемента на основе известного свойства этого элемента, называемого ключом. В нашем примере ключом для каждой книги является первая буква фамилии автора. Но этот простой ключ делает вероятным, что некоторые ячейки будут гораздо полнее других. (Например, у немногих авторов, пишущих на английском языке, фамилия начинается с буквы X.) Лучший подход — начать с полного имени автора, заменить каждую букву в имени числом, соответствующим ее положению в алфавите, сложить все эти числа и разделить сумму на 26. Остаток — это некоторое число от нуля до 25. Используйте это число, чтобы присвоить книге ячейку.
Такое математическое правило преобразования ключа в адрес хранилища называется хеш-функцией. Грамотно разработанная хеш-функция гарантирует, что элементы, как правило, будут распределены относительно равномерно по контейнерам, поэтому вам не придется тратить много времени на поиск в каждом контейнере.
Если вы хотите еще больше сократить время извлечения, вы можете использовать больше контейнеров. Но это приводит к другому компромиссу: эти контейнеры будут занимать место, даже если в итоге окажутся пустыми.
Этот компромисс между пространством и временем является неотъемлемой особенностью хеш-таблиц — это цена, которую приходится платить за избежание противоречия между временем вставки и временем извлечения, которое характерно для более простых структур данных. Спустя более 70 лет после изобретения хеш-таблиц, специалисты по информатике продолжают открывать новые грани их фундаментальных свойств. Недавно они наконец разработали версию, которая обеспечивает идеальный баланс между пространством и временем. А в прошлом году студент опроверг давнее предположение о минимальном времени, необходимом для поиска конкретного элемента в почти заполненной хеш-таблице.
Куча приоритетов
Хеш-таблицы хорошо работают, когда невозможно предсказать, какой фрагмент данных потребуется получить следующим. Но это не всегда так. Представьте, что вы пытаетесь выполнить задачи из списка дел, но вам постоянно назначают новые задачи с разными сроками выполнения. Вы хотите быстро добавлять новые элементы в список дел, но вас не интересует получение этих элементов, пока они не станут для вас первоочередной задачей.
В этом случае лучшим вариантом будет структура данных, называемая кучей. Как следует из названия, куча — это несколько хаотичный подход к хранению данных. По сути, это математическая версия кучи вещей: одни элементы хранятся над другими, и к этим элементам, расположенным выше, легче получить доступ. Элемент с наивысшим приоритетом всегда находится на вершине кучи, откуда его можно мгновенно извлечь. Нижние слои будут более неорганизованными, но вам не нужно беспокоиться об относительном положении этих элементов с низким приоритетом.
Простейшая реализация этой базовой идеи использует математический объект, называемый бинарным деревом, которое представляет собой сеть узлов особой формы: наверху находится единственный узел, и каждый узел соединен с двумя узлами, расположенными непосредственно под ним.
Представим себе бинарное дерево, содержащее элементы списка дел. Каждый узел может хранить один элемент, и каждый элемент помечен числом, обозначающим срок его выполнения. Элементы с высоким приоритетом получают меньшие номера.
Каждый новый предмет помещается в пустое место на текущем самом нижнем слое.
После добавления нового элемента сравните его срок выполнения со сроком выполнения элемента в узле, расположенном непосредственно над ним. Если срок выполнения новой задачи наступает раньше, поменяйте элементы местами. Продолжайте менять местами элементы, пока новый элемент не окажется непосредственно под более срочным элементом.
Эта процедура гарантирует, что задача с наивысшим приоритетом всегда будет подниматься наверх. Более того, процедура чрезвычайно быстрая. Даже в кошмарном сценарии, когда у вас в списке дел 1000 задач и постоянно появляются новые, хранение их в куче гарантирует, что для перемещения каждой новой задачи на соответствующую позицию потребуется не более девяти обменов. Как только вы завершите самую срочную задачу и удалите её из кучи, вы сможете быстро поднять новую задачу с наивысшим приоритетом из нижележащего слоя.
В информатике кучи широко используются в алгоритмах для поиска кратчайшего пути от заданной начальной точки в сети до любой другой точки. В 2024 году группа исследователей использовала оригинальную новую конструкцию кучи, чтобы преобразовать классический алгоритм поиска кратчайших путей в алгоритм, теоретически оптимальный для любой конфигурации сети.
В интернете полно книг по самосовершенствованию, полных противоречивых советов о том, как лучше организовать свои вещи. Если компьютерная наука чему-то и учит, так это тому, что идеального решения не существует — у каждого подхода есть свои компромиссы. Но если для вас одни вещи важнее других, не бойтесь оставить после себя немного беспорядка.
Источник: www.quantamagazine.org
