Какие классы структур данных можно сделать постоянными?

19

Постоянные структуры данных являются неизменными структурами данных. Операции над ними возвращают новую «копию» структуры данных, но измененную операцией; старая структура данных остается неизменной. Эффективность обычно достигается за счет совместного использования некоторых базовых данных и предотвращения полного копирования структуры данных.

Вопросов:

  • Есть ли результаты о классах структур данных, которые можно сделать постоянными (при сохранении тех же или очень похожих сложностей)?

  • Можно ли сделать все структуры данных постоянными (при сохранении одинаковых или очень похожих сложностей)?

  • Известно ли, что какие-либо структуры данных невозможно сделать постоянными (при сохранении тех же или очень похожих сложностей)?

Реал Слав
источник
1
Вы не можете сделать вектор постоянным с сохраненной сложностью O (1) для доступа к случайному элементу.
смоссен
2
@ Smossen ты можешь доказать это?
Реал Слав
1
Ваш первый вопрос - очень широкий вопрос. Есть много результатов по теме структур данных, которые можно сделать постоянными. Можно написать целую книгу на эту тему, и некоторые люди написали: например, книга Окасаки является классикой по этой теме. Вы сделали некоторые исследования по этой теме? Вы можете сузить вопрос? В настоящее время, я подозреваю, что он может быть слишком широким, чтобы подходить для этого сайта. Может быть, разделить 3-й вопрос на отдельный вопрос?
DW
@Realz Slaw: Я не могу доказать это формально, но я думаю, что это здравый смысл. O (1) доступ к элементам в векторах (включая хеш-таблицы) зависит от фиксированного времени для декодирования адреса на данном оборудовании. Постоянство добавляет одно или два измерения в дополнение к векторному индексу. Но аппаратные адреса все еще одномерные.
смоссен

Ответы:

22

Положительный результат: настойчивость не стоит слишком дорого. Можно показать, что каждая структура данных может быть сделана полностью постоянной с максимальным замедлением .О(Л.Г.N)

Доказательство: вы можете взять массив и сделать его постоянным, используя стандартные структуры данных (например, сбалансированное бинарное дерево; более подробную информацию смотрите в конце этого ответа). Это приводит к замедлению : каждый доступ к массиву занимает время O ( lg n ) с постоянной структурой данных вместо времени O ( 1 ) для непостоянного массива. Теперь возьмем любой императивный алгоритм, время работы которого в модели ОЗУ равно O ( f ( n ) ) , где n обозначает объем используемой памяти. Представлять всю память как один большой массив (сО(Л.Г.N)О(Л.Г.N)О(1)О(е(N))N элементов), и сделайте его постоянным, используя постоянную карту. Каждый шаг императивного алгоритма влечет за собой самое большее O ( lg n ) замедление, поэтому общее время работы составляет O ( f ( n ) lg n ) .NО(Л.Г.N)О(е(N)Л.Г.N)

По-видимому, это можно сделать немного лучше: очевидно, можно уменьшить коэффициент замедления до (ожидаемое, амортизированное время), используя методы, приведенные ниже в статье Demaine, - но я не знаком с деталями этой работы, поэтому я не могу поручиться за это сам. Спасибо jbapple за это наблюдение.О(Л.Г.Л.Г.N)


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

В частности, рассмотрим массив из элементов. Без сохранения каждый доступ к массиву занимает O ( 1 ) времени (в модели RAM). С постоянством, по-видимому, было показано, что нет способа построить постоянный массив с O ( 1 ) наихудшей сложностью для доступа к случайному элементу. В частности, очевидно, что существует нижняя граница, показывающая, что у полностью постоянных массивов должно быть время доступа Ω ( lg lg n ) . Эта нижняя граница утверждается на стр.3 следующей статьи:NО(1)О(1)Ω(Л.Г.Л.Г.N)

Нижняя граница относится к Михаю Патраску, но нет упоминания об источнике, который подробно описывает доказательство этой утвержденной нижней границы.


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

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


О(Л.Г.N)

dd

NО(Л.Г.N)О(Л.Г.N)О(Л.Г.N)

Вы можете найти больше объяснений, с красивыми картинками, на следующих ресурсах:

Это даст вам основную идею. Есть дополнительные детали, о которых нужно позаботиться, но детали этого вопроса не входят в объем. К счастью, это все стандартные вещи, и в литературе доступно много информации о том, как строить такие структуры данных. Не стесняйтесь задавать отдельный вопрос, если вышеперечисленных ресурсов недостаточно, и вам нужна дополнительная информация о деталях построения структуры данных постоянного массива.

DW
источник
Я не очень понимаю первый абзац, как мне сделать массив постоянным, используя красно-черное дерево?
Г. Бах
@ G.Bach, есть довольно хорошее объяснение в разделах, озаглавленных «Двоичные деревья поиска» и «Структуры произвольного доступа» (в частности, метод дерева) на toves.org/books/persist/index.html . Еще одно приятное описание смотрите на netcode.ru/dotnet/?artID=6592#BinaryTrees и некоторых последующих разделах. Это даст вам основную идею. Детали не входят в сферу охвата этого вопроса, но это все стандартные вещи; Я рекомендую вам задать отдельный вопрос, если вы хотите получить больше информации о том, как построить такую ​​структуру данных.
DW
4
О(Л.Г.Л.Г.N)