Простой порядок для связанного списка

Question

Я хочу создать двусвязный список с порядковой последовательностью (целочисленным атрибутом), так что сортировка по последовательности заказов может создать массив, который будет эффективно эквивалентен связанному списку.

given: a <-> b <-> c 

a.index > b.index 
b.index > c.index 

Этот индекс должен обрабатывать эффективно произвольное количество вставок.

Есть ли известный алгоритм для этого? Проблема заключается в том, что список становится большим и индексная последовательность упакована. В этой ситуации список нужно отсканировать, чтобы вернуть обратно. Я просто не знаю, как это должно быть выполнено. В идеальном случае будет какая-то автоматическая балансировка, чтобы это заимствование было быстрым и редким.

Наивное решение изменения всех левых или правых индексов на 1, чтобы освободить место для вставки, - O (n).

Я бы предпочел использовать целые числа, так как я знаю, что числа имеют тенденцию быть менее надежными в плавающей точке, поскольку они приближаются к нулю в большинстве реализаций.

Answer 1

Это одна из моих любимых проблем. В литературе это называется «онлайн-маркировка списка» или просто «маркировка списка». Здесь немного в Википедии: https://en.wikipedia.org/wiki/Order-maintenance_problem#List-labeling

Возможно, самый простой алгоритм, который будет практичным для ваших целей, - это первый здесь: https://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf.

Он обрабатывает вставки в амортизированном O (log N) времени, и для управления N элементами вам нужно использовать целые числа, которые достаточно велики, чтобы удерживать N^2. Для почти всех практических случаев достаточно 64-битных целых чисел.

Answer 2

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

Моя идея - заимствовать некоторые идеи для алгоритма. То, что я сделал, это сделать Ids ints и отсортировать заказы. Тогда алгоритм ленив, набирая записи везде, где они подойдут. Как только он заканчивается в каком-то маленьком скоплении, он начинает сканирование вверх и вниз от клама и пытается установить равномерный интервал, так что если есть n отсканированных предметов, им нужно разделить между ними n^2.

В теории это будет означать, что со временем список будет отлично дополнен, и учитывая, что мои идентификаторы являются int и мои порядки сортировки длинны, никогда не будет сценария, в котором вы не сможете достичь n^2 дополнения , Я не могу говорить о верхних границах числа операций, но мои мужества говорят мне, что, выполняя многочленную работу с частотой 1/полином, я буду делать все отлично.