Математический анализ структур данных помогает понять, как в разных системах хранения данных сочетаются компромиссы между временем, памятью и другими ресурсами.
Кристина Армитаж/Quanta Magazine
автор: Бен Брубейкер
Введение
Как не существует единственно верного способа организовать книжную полку, так и универсального решения для хранения информации не существует. Рассмотрим простую ситуацию: вы создаете новый цифровой файл. Вашему компьютеру нужно быстро найти место для его хранения. Если позже вы захотите его удалить, машина должна быстро найти нужные биты для удаления. Исследователи стремятся разработать системы хранения данных, так называемые структуры данных, которые бы обеспечивали баланс между временем, необходимым для добавления данных, временем, необходимым для их последующего удаления, и общим объемом памяти, который требуется системе. Чтобы понять, с какими трудностями вы можете столкнуться, представьте, что все ваши книги стоят в ряд на одной длинной полке. Если они расположены в алфавитном порядке, вы сможете быстро найти любую из них. Но когда вы приобретаете новую книгу, вам потребуется время, чтобы найти для нее подходящее место. И наоборот, если вы будете расставлять книги там, где есть свободное место, вы сэкономите время сейчас, но потом вам будет сложно их найти. Такой компромисс между временем на размещение и временем на поиск может не стать проблемой для библиотеки с одной полкой, но представьте, насколько это может усложнить работу с тысячами книг. Вместо одной полки можно поставить 26 контейнеров с алфавитными обозначениями и распределять книги по контейнерам в соответствии с первой буквой фамилии автора. Когда вы получаете новую книгу, вы сразу понимаете, в какой контейнер ее положить, а когда вам нужно достать книгу, вы сразу знаете, где ее искать. В некоторых случаях и добавление, и изъятие книг происходит намного быстрее, чем если бы они хранились на одной длинной полке. Конечно, у этой системы хранения есть свои недостатки. Найти нужную книгу можно мгновенно, только если в каждом контейнере лежит по одной книге; в противном случае придется долго искать нужную. В крайнем случае, если у вас есть книги Азимова, Этвуд и Остин, вы снова столкнетесь с проблемой одной длинной полки, а еще у вас будет куча пустых контейнеров, загромождающих гостиную.
Студент опроверг гипотезу в области науки о данных, выдвинутую 40 лет назад алгоритмы
Студент опроверг гипотезу в области науки о данных, выдвинутую 40 лет назад 10 февраля 2025 года
Программисты часто изучают структуры данных, называемые хэш-таблицами, которые представляют собой более сложные версии этой простой системы хранения. Хэш-таблицы вычисляют адрес хранения для каждого элемента на основе известного свойства этого элемента, называемого ключом. В нашем примере ключом для каждой книги является первая буква фамилии автора. Но из-за такого простого ключа некоторые ячейки могут оказаться заполнены гораздо сильнее, чем другие. (Например, у немногих авторов, пишущих на английском языке, фамилия начинается с буквы X.) Более эффективный подход заключается в том, чтобы взять полное имя автора, заменить каждую букву в имени на число, соответствующее ее позиции в алфавите, сложить все эти числа и разделить сумму на 26. Остаток будет представлять собой число от нуля до 25. Используйте это число, чтобы отнести книгу к той или иной категории. Такое математическое правило преобразования ключа в адрес хранилища называется хеш-функцией. Грамотно составленная хеш-функция гарантирует, что элементы будут относительно равномерно распределены по корзинам, поэтому вам не придется тратить много времени на поиск в каждой из них.
Если вы хотите еще больше сократить время извлечения данных, можно использовать больше корзин. Но это приведет к другому компромиссу: корзины будут занимать место, даже если в них ничего не окажется. Этот компромисс между пространством и временем — неотъемлемая черта хеш-таблиц. Это цена, которую приходится платить за то, чтобы избежать противоречий между временем вставки и извлечения данных, характерных для более простых структур данных. Спустя более 70 лет после изобретения хеш-таблиц ученые-компьютерщики продолжают открывать новые факты об их фундаментальных свойствах. Недавно они наконец разработали версию, которая обеспечивает идеальный баланс между пространством и временем. А в прошлом году студент опроверг давнюю гипотезу о минимальном количестве времени, необходимом для поиска конкретного элемента в почти заполненной хэш-таблице.
Куча приоритетов
Хеш-таблицы хорошо подходят для случаев, когда вы не можете предугадать, какие данные вам понадобятся в следующий момент. Но так бывает не всегда. Представьте, что вы пытаетесь выполнить задачи из списка дел, но вам постоянно поручают новые задачи с разными сроками выполнения. Вам нужно иметь возможность быстро добавлять новые задачи в список дел, но вы не хотите извлекать их из списка, пока они не станут для вас приоритетными. В этом случае лучше всего использовать структуру данных под названием «куча». Как следует из названия, «куча» — это довольно хаотичный подход к хранению данных. По сути, это математическая версия кучи: одни элементы хранятся над другими, и к верхним элементам легче получить доступ. Элемент с наивысшим приоритетом всегда находится в верхней части кучи, и его можно мгновенно извлечь. Нижние слои будут менее упорядоченными, но вам не нужно беспокоиться об относительном расположении этих низкоприоритетных элементов.
В простейшей реализации этой базовой идеи используется математический объект под названием «двоичное дерево» — сеть узлов особой формы: в верхней части находится один узел, а каждый узел ниже соединен с двумя узлами, расположенными непосредственно под ним.
Давайте представим бинарное дерево, в котором хранятся элементы списка дел. В каждом узле может находиться один элемент, и каждый элемент помечен числом, обозначающим срок выполнения. Элементы с высоким приоритетом имеют меньшие номера.
Каждый новый элемент помещается в пустой слот на самом нижнем уровне текущего слоя.
После добавления нового элемента сравните дату его выполнения с датой выполнения элемента в узле, расположенном непосредственно над ним. Если новая задача должна быть выполнена раньше, поменяйте их местами. Продолжайте менять местами, пока новый элемент не окажется непосредственно под более срочным.
Эта процедура гарантирует, что задача с наивысшим приоритетом всегда будет находиться в верхней части списка. Более того, эта процедура выполняется очень быстро. Даже в самом неблагоприятном сценарии, когда в вашем списке дел 1000 задач и вы постоянно получаете новые, хранение задач в куче гарантирует, что для перемещения каждой новой задачи на соответствующее место потребуется не более девяти перестановок. Как только вы завершите самую срочную задачу и удалите ее из кучи, вы сможете быстро выбрать новую задачу с наивысшим приоритетом из нижнего слоя.
В информатике кучи широко используются в алгоритмах поиска кратчайшего пути от заданной начальной точки в сети до любой другой точки. В 2024 году группа исследователей применила новую оригинальную конструкцию кучи, чтобы преобразовать классический алгоритм поиска кратчайших путей в алгоритм, который теоретически оптимален для любой топологии сети.
Существует множество книг по саморазвитию, в которых даются противоречивые советы о том, как лучше организовать свои вещи. Если информатика и учит нас чему-то, так это тому, что идеального решения не существует — у каждого подхода есть свои недостатки. Но если какие-то вещи для вас важнее других, не бойтесь немного наводить порядок.
источник: https://www.quantamagazine.org/why-theres-no-single-best-way-to-store-information-20260116/