Учёные в области компьютерных технологий представили новый алгоритм, который касается не только решения абстрактных задач, но и практических проблем, таких как организация книг на полке. Этот алгоритм помогает минимизировать время, необходимое для добавления новой книги в отсортированный список, будь то библиотечная полка или хранилище данных.
Представьте ситуацию: книги на полке сдвинуты к левому краю, а пустое пространство остаётся справа. При добавлении книги, например, Исабель Альенде, вам придётся переместить все книги, чтобы вставить её в нужное место. Если затем поступает книга Дугласа Адамса, процесс повторяется. Оптимальная организация предполагает распределение свободного места по всей полке. Вопрос в том, как лучше это сделать.
Проблема была впервые описана в научной работе 1981 года . Она применима не только к библиотекам, но и к организации данных на жёстких дисках и в базах данных. Поскольку такие системы часто работают с миллиардами элементов, неэффективное решение может вызывать значительные задержки и дополнительные вычислительные расходы.
В прошлом году команда из семи исследователей представила на конференции Foundations of Computer Science в Чикаго новый алгоритм , который приблизился к теоретически возможному идеалу. Этот подход использует немного информации о предыдущем состоянии полки и элементы случайности.
По словам Сета Петти из Мичиганского университета, проблема имеет огромное значение, так как большинство современных структур данных хранит информацию последовательно. Он назвал новую работу одной из самых вдохновляющих в этом году.
Задача состоит в том, чтобы найти способ, который минимизирует время вставки элемента. Исторически доказано, что существующие алгоритмы достигали времени вставки, пропорционального квадрату логарифма количества элементов. Однако для достижения более высокой эффективности потребовалось разработать совершенно новый подход.
В 2022 году команда исследователей создала алгоритм, который был независим от истории, не требовал равномерного распределения и использовал случайность. Это позволило сократить время вставки до логарифма в степени 1,5 от числа элементов. Более того, этот метод оказался полезен не только для оптимизации скорости, но и для обеспечения конфиденциальности данных.
В прошлом году команда снова улучшила алгоритм, сократив время вставки до почти идеального уровня, равного логарифму числа элементов. Новый подход использовал ограниченную степень зависимости от истории, что позволило предугадывать будущие вставки. Это сделало алгоритм более эффективным и практичным для использования в реальных задачах.
Хотя оставшийся разрыв между теоретическим минимумом и текущим достижением ещё существует, учёные уверены, что дальнейшие улучшения будут связаны с оптимизацией верхней границы времени вставки. Однако, как отметил Петти, мир науки полон сюрпризов.