Проблема с обслуживанием заказов

В информатике предполагает проблема поддержания порядка поддержание полностью упорядоченного набора, поддерживающего следующие операции:

insert(X, Y), который вставляет X сразу после Y в общем порядке;
order(X, Y), который определяет, предшествует ли X Y в общем порядке; и
delete(X), который удаляет X из набора.

Пол Дитц впервые представил структуру данных для решения этой проблемы в 1982. ^[1] Эти данные опоры конструкции insert(X, Y) в $O(\log n)$ (в обозначении Big O ) амортизированное время и order(X, Y) в постоянное время, но делает не поддерживает удаление. Афанасиос Цакалидис использовал деревья BB[α] с теми же границами производительности, которые поддерживают удаление в $O(\log n)$ и улучшена производительность вставки и удаления для $O(1)$ амортизированное время с косвенностью. ^[2] Дитц и Дэниел Слитор опубликовали улучшение постоянного времени для наихудшего случая в 1987 году. ^[3] Майкл Бендер, Ричард Коул и Джек Зито опубликовали значительно упрощенные альтернативы в 2002 году. ^[4] Бендер, Файнман, Гилберт, Копеловиц и Монтес также опубликовали деамортизированное решение в 2017 году. ^[5]

Эффективные структуры данных для поддержания заказов находят применение в во многих областях, включая сохранение структуры данных , ^[6] графовые алгоритмы ^[7]^[8] и отказоустойчивые структуры данных. ^[9]

Маркировка списка

Проблема, связанная с проблемой поддержания порядка, заключается в проблема с разметкой списков, в которой вместо order(X, Y) операция решение должно поддерживать присвоение меток из вселенной целых чисел $\{1,2,\ldots ,m\}$ к элементы набора такие, что X предшествует Y в общем порядке, если и только если X присвоена меньшая метка, чем Y. Он также должен поддерживать операция label(X) возвращая метку любого узла X. Обратите внимание, что order(X, Y) может быть реализовано просто путем сравнение label(X) и label(Y) так что любой решение проблемы разметки списков немедленно приводит к проблема с поддержанием заказов. Фактически, большинство решений проблема поддержания порядка - это решение проблемы маркировки списков дополнен уровнем косвенности структуры данных для улучшения производительность. Пример этого мы увидим ниже.

Для задачи разметки списков на множествах размером до $n$ , стоимость маркировки списка зависит от того, насколько велик $m$ является функцией $n$ . Соответствующий диапазон параметров для ведения заказа: $m=n^{1+\Theta (1)}$ , для чего $O(\log n)$ Решение по амортизированной стоимости известно, ^[10] и $2^{\Omega (n)}$ для которого известно амортизированное решение с постоянным временем ^[11]

O(1) амортизированная вставка через косвенность

Косвенность — это метод, используемый в структурах данных, в которых проблема разделен на несколько уровней структуры данных для улучшения эффективность. Обычно проблема размера $n$ разделен на $n/\log n$ проблемы с размером $\log n$ . Для Например, этот метод используется в y-fast Trys . Этот стратегия также работает над улучшением производительности вставки и удаления. структуры данных, описанной выше, к постоянному амортизированному времени. В Фактически, эта стратегия работает для любого решения разметки списка проблема с $O(\log n)$ амортизированная вставка и удаление время.

Новая структура данных полностью перестраивается всякий раз, когда она увеличивается. большой или слишком маленький. Позволять $N$ быть числом элементов общий порядок на момент последнего восстановления. Структура данных перестраивается всякий раз, когда инвариант ${\tfrac {N}{3}}\leq n\leq 2N$ является нарушены вставкой или удалением. Поскольку восстановление может быть выполнено в линейное время, это не влияет на амортизированную производительность вставки и удаления.

В ходе восстановительных работ было $N$ элементы общий заказ делится на $O(N/\log N)$ смежный подсписки, каждый размером $\Omega (\log N)$ . Проблема разметки списков решается на множестве набор узлов, представляющих каждый из подсписки в исходном порядке. Метки для этой подзадачи считаются полиномиальными --- скажем $m=N^{2}$ , чтобы их можно было сравнивать за постоянное время и обновлять в амортизированных $O(\log N)$ время.

Для каждого подсписка строится двусвязный список его элементов, сохраняющий для каждого элемента указатель на своего представителя в дереве, а также локальное целое число этикетка. Локальные целочисленные метки также берутся из диапазона $m=N^{2}$ , так что их можно сравнивать за постоянное время, но поскольку каждая локальная задача включает в себя только $\Theta (\log N)$ предметы, диапазон этикеток $m$ экспоненциально зависит от количества помеченных элементов. Таким образом, они могут быть обновлены в $O(1)$ амортизированное время.

см. в разделе «Проблема с маркировкой списков» Подробности обоих решений .

Заказ

Учитывая узлы подсписка X и Y, order(X, Y) может быть ответил, сначала проверив, находятся ли два узла в одном и том же подсписок. Если да, то их порядок можно определить путем сравнения их локальных этикетки. В противном случае сравниваются метки их представителей в первой задаче разметки списка. Эти сравнения занимают постоянное время.

Вставлять

Учитывая новый узел подсписка для X и указатель на узел подсписка Y, insert(X, Y) вставляет X сразу после Y в подсписок Y, если в списке есть место для X, то есть если длина списка не превышает $2\log N$ после вставки. Его локальная метка задается алгоритмом маркировки локального списка для экспоненциальных меток. Этот случай занимает $O(1)$ амортизированное время.

Если локальный список переполняется, он равномерно разбивается на два списка размером $\log N$ , а элементам в каждом списке присваиваются новые метки из их (независимых) диапазонов. При этом создается новый подсписок, который вставляется в список подсписков, а новому узлу подсписка присваивается метка в списке подсписков с помощью алгоритма маркировки списка. Наконец, X вставляется в соответствующий список.

Эта последовательность операций занимает $O(\log N)$ время, но были $\Omega (\log N)$ вставки с момента создания списка или его последнего разделения. Таким образом, амортизированное время на вставку равно $O(1)$ .

Удалить

Учитывая узел подсписка X, который нужно удалить, delete(X) просто удаляет X из своего подсписка за постоянное время. Если это оставляет подсписок пуст, то нам нужно удалить представителя список подсписков. Поскольку по крайней мере $\Omega (\log N)$ элементы были удалены из подсписка, так как он был впервые создан, мы можем позволить себе потратить $O(\log N)$ времени амортизированная стоимость удаления равна $O(1)$ .

Ссылки

^ Дитц, Пол Ф. (1982), «Поддержание порядка в связанном списке», Труды 14-го ежегодного симпозиума ACM по теории вычислений (STOC '82) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 122–127, дои : 10.1145/800070.802184 , ISBN 978-0897910705 .
^ Цакалидис, Афанасиос К. (1984), «Поддержание порядка в обобщенном связанном списке», Acta Informatica , 21 (1): 101–112, doi : 10.1007/BF00289142 , MR 0747173 .
^ Дитц, П.; Слитор, Д. (1987), «Два алгоритма поддержания порядка в списке», Труды 19-го ежегодного симпозиума ACM по теории вычислений (STOC '87) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 365–372. , doi : 10.1145/28395.28434 , hdl : 1802/5693 , ISBN 978-0897912211 . Полная версия, Тех. Представитель CMU-CS-88-113 , Карнеги-Меллон Университет, 1988.
^ Бендер, Майкл А .; Коул, Ричард ; Демейн, Эрик Д .; Фарах-Колтон, Мартин ; Зито, Джек (2002), «Два упрощенных алгоритма поддержания порядка в списке», Мёринг, Рольф Х.; Раман, Раджив (ред.), Алгоритмы - ESA 2002, 10-й ежегодный европейский симпозиум, Рим, Италия, 17–21 сентября 2002 г., Труды , конспекты лекций по информатике, том. 2461, Springer, стр. 152–164, номер документа : 10.1007/3-540-45749-6_17.
^ Бендер, Майкл А .; Файнман, Джереми Т.; Гилберт, Сет; Копеловиц, Цви; Монтес, Пабло (2017), «Обслуживание файлов: если есть сомнения, измените макет!», Кляйн, Филип Н. (ред.), Труды двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16–19 января , Общество промышленной и прикладной математики, стр. 1503–1522, doi : 10.1137/1.9781611974782.98
^ Дрисколл, Джеймс Р.; Сарнак, Нил; Слитор, Дэниел Д .; Тарьян, Роберт Э. (1989), «Как сделать структуры данных постоянными», Journal of Computer and System Sciences , 38 (1): 86–124, doi : 10.1016/0022-0000(89)90034-2 , MR 0990051 .
^ Эппштейн, Дэвид ; Галил, Цви ; Итальяно, Джузеппе Ф .; Ниссенцвейг, Амнон (1997), «Разреженность — метод ускорения алгоритмов динамических графов», Journal of the ACM , 44 (5): 669–696, doi : 10.1145/265910.265914 , MR 1492341 .
^ Катриэль, Ирит; Бодлендер, Ханс Л. (2006), «Топологическое упорядочение в Интернете», Транзакции ACM по алгоритмам , 2 (3): 364–379, CiteSeerX 10.1.1.78.7933 , doi : 10.1145/1159892.1159896 , MR 2253786 .
^ Ауманн, Йонатан; Бендер, Майкл А. (1996), «Отказоустойчивые структуры данных», Труды 37-го ежегодного симпозиума по основам информатики (FOCS 1996) , стр. 580–589, doi : 10.1109/SFCS.1996.548517 , ISBN 978-0-8186-7594-2 .
^ Итай, Алон; Конхейм, Алан Г.; Роде, Майкл (1981), «Реализация очередей с приоритетами в разреженной таблице», ICALP , стр. 417–431.
^ Буланек, Ян; Куцкий, Михал; Сакс, Майкл Э. (2015), «Жесткие нижние границы проблемы онлайн-маркировки», SIAM Journal on Computing , vol. 44, стр. 1765—1797 .

Внешние ссылки

Два упрощенных алгоритма поддержания порядка в списке. - В этой статье ( Майкл А. Бендер , Ричард Коул, Эрик Д. Демейн , Мартин Фарах-Колтон и Джек Зито, 2002) представлена структура данных с разметкой списка с амортизированной производительностью, которая не сохраняет дерево явно. Приведенный анализ проще, чем анализ, проведенный (Dietz and Sleator, 1987) для аналогичной структуры данных.

[Dietz-1] Дитц, Пол Ф. (1982), «Поддержание порядка в связанном списке», Труды 14-го ежегодного симпозиума ACM по теории вычислений (STOC '82) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 122–127, дои : 10.1145/800070.802184 , ISBN 978-0897910705 .

[Tsakalidis-2] Цакалидис, Афанасиос К. (1984), «Поддержание порядка в обобщенном связанном списке», Acta Informatica , 21 (1): 101–112, doi : 10.1007/BF00289142 , MR 0747173 .

[DietzSleator-3] Дитц, П.; Слитор, Д. (1987), «Два алгоритма поддержания порядка в списке», Труды 19-го ежегодного симпозиума ACM по теории вычислений (STOC '87) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 365–372. , doi : 10.1145/28395.28434 , hdl : 1802/5693 , ISBN 978-0897912211 . Полная версия, Тех. Представитель CMU-CS-88-113 , Карнеги-Меллон Университет, 1988.

[4] Бендер, Майкл А .; Коул, Ричард ; Демейн, Эрик Д .; Фарах-Колтон, Мартин ; Зито, Джек (2002), «Два упрощенных алгоритма поддержания порядка в списке», Мёринг, Рольф Х.; Раман, Раджив (ред.), Алгоритмы - ESA 2002, 10-й ежегодный европейский симпозиум, Рим, Италия, 17–21 сентября 2002 г., Труды , конспекты лекций по информатике, том. 2461, Springer, стр. 152–164, номер документа : 10.1007/3-540-45749-6_17.

[5] Бендер, Майкл А .; Файнман, Джереми Т.; Гилберт, Сет; Копеловиц, Цви; Монтес, Пабло (2017), «Обслуживание файлов: если есть сомнения, измените макет!», Кляйн, Филип Н. (ред.), Труды двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16–19 января , Общество промышленной и прикладной математики, стр. 1503–1522, doi : 10.1137/1.9781611974782.98

[Driscoll-6] Дрисколл, Джеймс Р.; Сарнак, Нил; Слитор, Дэниел Д .; Тарьян, Роберт Э. (1989), «Как сделать структуры данных постоянными», Journal of Computer and System Sciences , 38 (1): 86–124, doi : 10.1016/0022-0000(89)90034-2 , MR 0990051 .

[Eppstein-7] Эппштейн, Дэвид ; Галил, Цви ; Итальяно, Джузеппе Ф .; Ниссенцвейг, Амнон (1997), «Разреженность — метод ускорения алгоритмов динамических графов», Journal of the ACM , 44 (5): 669–696, doi : 10.1145/265910.265914 , MR 1492341 .

[Katriel-8] Катриэль, Ирит; Бодлендер, Ханс Л. (2006), «Топологическое упорядочение в Интернете», Транзакции ACM по алгоритмам , 2 (3): 364–379, CiteSeerX 10.1.1.78.7933 , doi : 10.1145/1159892.1159896 , MR 2253786 .

[Aumann-9] Ауманн, Йонатан; Бендер, Майкл А. (1996), «Отказоустойчивые структуры данных», Труды 37-го ежегодного симпозиума по основам информатики (FOCS 1996) , стр. 580–589, doi : 10.1109/SFCS.1996.548517 , ISBN 978-0-8186-7594-2 .

[ItaiKoRo-10] Итай, Алон; Конхейм, Алан Г.; Роде, Майкл (1981), «Реализация очередей с приоритетами в разреженной таблице», ICALP , стр. 417–431.

[BulanekKoSa15-11] Буланек, Ян; Куцкий, Михал; Сакс, Майкл Э. (2015), «Жесткие нижние границы проблемы онлайн-маркировки», SIAM Journal on Computing , vol. 44, стр. 1765—1797 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]