42-годишният проблем с подреждането на книгите вече има елегантно решение

Новото решение се намира на по-малко от една страница ширина от идеалното.

Учени от областта на компютърните технологии представиха нов алгоритъм, който решава не само абстрактни, но и практически проблеми, като например подреждане на книги на рафтовете. Този алгоритъм помага да се сведе до минимум времето, необходимо за добавяне на нова книга към сортиран списък, независимо дали е на библиотечен рафт или е хранилище за данни.

Представете си следната ситуация: книгите на рафта са избутани към левия край, а отдясно е оставено празно място. Когато добавяте книга като Исабел Алиенде например, ще трябва да преместите всички книги, за да я поставите на правилното място. Ако след това пристигне книга на Дъглас Адамс, процесът се повтаря. Оптималната организация включва разпределяне на наличното пространство по рафта. Въпросът е как най-добре да се направи това.

Проблемът е описан за пръв път в научен труд от 1981 г. Той се отнася не само за библиотеките, но и за организирането на данни в харддисковете и в базите данни. Тъй като тези системи често работят с милиарди елементи, едно неефективно решение може да доведе до значителни забавяния и допълнителни изчислителни разходи.

Миналата година екип от седем изследователи представи нов алгоритъм на конференцията Foundations of Computer Science в Чикаго, който се доближава до теоретично възможния идеал. Подходът използва съвсем малко информация за предишното състояние на рафта и елементи на случайност.

Според Сет Пети от Мичиганския университет проблемът е от голямо значение, тъй като повечето съвременни структури от данни съхраняват информацията последователно. Той нарече новата работа една от най-вдъхновяващите през тази година.

Задачата е да се намери метод, който да сведе до минимум времето, необходимо за вмъкване на даден елемент. В миналото беше доказано, че съществуващите алгоритми постигат време за вмъкване, пропорционално на квадрата на логаритъма на броя на елементите. Въпреки това е необходим изцяло нов подход за постигане на по-висока ефективност.

През 2022 г. екип от изследователи създаде алгоритъм, който е независим от хронологията, не изисква равномерно разпределение и използва случайността. Това намали времето за вмъкване до логаритъм на степен 1,5 от броя на елементите. Нещо повече, този метод се оказал полезен не само за оптимизиране на скоростта, но и за осигуряване на поверителността на данните.

Миналата година екипът отново подобри алгоритъма, като намали времето за вмъкване до почти идеалното ниво, равно на логаритъма на броя на елементите. Новият подход използва ограничена степен на зависимост от хронологията, което му позволи да предвиди бъдещите вмъквания. Това е направило алгоритъма по-ефективен и практичен за използване в реални проблеми.