Когда компьютерные учёные говорят о «сортировке книг», это может показаться чем-то несерьёзным. Но за этим термином стоит фундаментальная задача, определяющая скорость и эффективность множества реальных систем — от баз данных до управления файлами на жёстких дисках. Недавнее исследование, описанное в статье «New Book-Sorting Algorithm Almost Reaches Perfection», показало, что группа специалистов приблизилась к теоретическому пределу в этой задаче, сократив время вставки нового элемента (книги) почти до log n. А ведь десятилетиями никто не мог улучшить алгоритмы, предлагавшие вставку за (log n)².
Историческая справка и суть проблемы
Речь идёт о задаче «библиотечной сортировки» (library sorting или list labeling). Если совсем упрощённо:
🔎 Неэффективный пример — Представьте, что у вас все книги сдвинуты к левому краю полки, а свободное место — справа. Когда вы решите вставить новую «книгу» по алфавиту (или по любому другому ключу), придётся «протолкнуть» многие тома, чтобы освободить место. При большом количестве книг n такое «сдвигание» может занимать пропорционально n времени, что весьма накладно.
🤏 Оставлять зазоры — В 1981 году предложили распределять свободное пространство по полке так, чтобы каждый вставленный элемент двигал только небольшую часть соседних книг. Это позволило достичь асимптотики (log n)² — что долгое время считалось большим прорывом.
✨ Свежий подход — отойти от жёсткого принципа «гладкости» и ввести случайность в принятие решений
Математики и компьютерщики всегда стремятся улучшить верхнюю границу (upper bound) алгоритма и догнать нижнюю (lower bound), которая для этой задачи равна log n. До последнего момента, все «детерминированные» (без случайностей) и «сглаженные» (smooth) алгоритмы упирались в ту же (log n)².
Но команда исследователей (во главе с Майклом Бендером и Уильямом Кушмаулом) пошла на нестандартный шаг:
🎲 Случайность — алгоритм использует рандомизированные решения, т. е. при распределении зазоров может подбрасывать «мысленно монету».
🌀 Несглаженность — нарушается жёсткое правило равномерного распределения книг. Вместо этого система может оставлять пространство то в одном месте, то в другом, опираясь на вероятностные оценки и неполную «историю» полки.
И, как оказалось, такая «неинтуитивная» стратегия даёт резкое улучшение. Сначала (в 2022 году) время вставки снизилось до ( log n )¹·⁵. А в недавней работе авторам удалось достичь почти log n ⋅ ( log ( log n ) )³. По меркам асимптотики это уже практически «около log n» — оставшийся зазор крайне мал.
🚀 Главные технические детали
🎉 Немного истории — Для «сглаженных» и детерминированных алгоритмов нижняя граница доказана как (log n)², поэтому лучше нельзя. Значит, нужна рандомизация и отсутствие «сглаженности»!
📚 Ограниченная история — В одной из статей авторы вводят историческую независимость «history independence», когда алгоритм не знает всей предыстории расстановки книг, но при этом (в последующей работе) разрешают ему чуть-чуть опираться на прошлые тенденции (например, вдруг многие авторы были на букву N). При этом не дают ему «захлебнуться» деталями.
🔐 Приватность как ускоритель — Парадокс в том, что механизм, используемый для сокрытия «секретов» (чтобы никто не узнал, какие книги снимали с полки), внезапно помог увеличить эффективность. Идеи криптографии и рандомизированных структур слились, дав почти логарифмическую вставку.
🔧 Где это применить?
🤖 Базы данных — Любая динамическая структура, где нужно вставлять миллионы и миллиарды записей в отсортированном виде.
💾 Файловые системы — При размещении файлов на диске важно минимизировать лишние перемещения массивов при добавлении новых файлов.
🖥️ Динамические графы — Некоторые эксперименты показывают, что библиотечную сортировку «list labeling» можно адаптировать для хранения вершин и рёбер меняющихся графов, и новые алгоритмы обещают существенный прирост в скорости.
🤔 Личное мнение
Меня особенно впечатляет, как комбинирование случайности и «минимального пользования историей» способно уничтожить стереотип о том, что «сглаживание = всегда лучше». Более того, это напоминает кейсы, когда кажется, что более «хаотичная» стратегия (без строгой равномерности) вдруг оказывается эффективнее. Скорее всего, в будущем мы увидим, как этот подход будет доработан до log n, ведь остался символический зазор с log log n. Но учёные предупреждают: «Мир полон сюрпризов», и не исключено, что кто-то найдёт более жёсткое доказательство, поднимающее нижнюю границу.
Так или иначе, результат впечатляет: впервые за 40+ лет мы видим радикальный шаг вперёд в «библиотечной сортировке». Теоретики радуются, а практики уже предвкушают ускорение своих систем.