Чисто функциональный список одновременных пропусков

Question

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

Можно ли создать эффективный чисто функциональный список одновременных пропусков?Если нет, то возможно ли создать какой-либо эффективный чисто функциональный параллельный отсортированный словарь?

Answer 1

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

В частности, списки пропусков состоят из структур, которые выглядят так:

NODE1 ---------------------> NODE2 ---------...
  |                           |
  V                           V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...

Теперь, если у вас есть обновление, которое, скажем, удаляет NODE2b илиNODE1b, вы можете позаботиться об этом очень локально: вы просто указываете 2a на 2c или 1a на 2a соответственно, и все готово.К сожалению, поскольку все конечные узлы указывают друг на друга, это не очень хорошая структура для функционального (неизменяемого) обновления.

Таким образом, древовидные структуры лучше для неизменности (так как повреждение всегда локально ограничено - простоузел, о котором вы заботитесь, и его прямые родительские элементы через корень дерева).

Параллельные обновления плохо работают с неизменяемыми структурами данных.Если подумать, любое функциональное решение имеет обновление A как f(A).Если вам нужны два обновления, одно из которых f, а другое g, вам, скорее всего, нужно сделать f(g(A)) или g(f(A)), или вам нужно перехватить запросы и создать новую операцию h = f,g, котораявы можете применять все сразу (или делать другие очень умные вещи).

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

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

Answer 2

Решение Эндрю МакКинлея - это настоящее «истинное» функциональное решение для реального списка пропусков, но оно имеет недостаток.Вы платите логарифмическое время, чтобы получить доступ к элементу, но теперь мутация за пределами головного элемента становится безнадежной.Ответ, который вы хотите, закопан в бесчисленных копиях путей!

Можем ли мы добиться большего успеха?

Отчасти проблема в том, что существует множество путей от -infinity к вашему элементу.

Но если вы продумываете алгоритмы поиска в ски-листе, вы никогда не будете использовать этот факт.

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

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

Теперь мы можем начать с простого пропускающего списка

-inf-------------------> 16
-inf ------> 8 --------> 16
-inf -> 4 -> 8 -> 12 --> 16

Расширение его по уровню:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8 --------> 16
  |          |            |
  v          v            v
-inf -> 4 -> 8 -> 12 --> 16

Уберите все указатели, кроме предпочитаемых:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8           16
  |          |            |
  v          v            v
-inf -> 4    8 -> 12     16

Затем вы можете переместить «палец» в положение 8, отслеживая все указатели, которые вам нужно будет щелкнуть, чтобы попасть туда.

-inf ------------------> 16
   ^                      |
   |                      v
-inf <------ 8           16
   |         |            |
   v         v            v
-inf -> 4    8 -> 12     16

Оттуда можночтобы удалить 8, нажмите пальцем куда-нибудь еще, и вы можете продолжать перемещаться по структуре пальцем.

При таком взгляде мы видим, что привилегированные пути в списке пропусков образуют связующее дерево!

Перемещение пальца на 1 шаг является операцией O (1), если у вас есть только привилегированные указатели в дереве и вы используете такие узкие узлы, как этот.Если бы вы использовали толстые узлы, то движение пальца влево / вправо было бы потенциально более дорогим.

Все операции остаются O (log n), и вы можете использовать рандомизированную структуру пропускающего списка или детерминированную структуру как обычно.

Тем не менее, когда мы разбиваем пропускающий список на понятие предпочтительного пути, мы получаем, что пропускающий список - это просто дерево с некоторыми избыточными неприоритетными ссылками, которые нам не нужны для вставки / поиска /удалить, чтобы длина каждого из этих путей в верхнем правом углу была O (log n) либо с высокой вероятностью, либо с гарантией, в зависимости от стратегии обновления.

Даже без пальца вы можете поддерживать O (log n)) ожидаемое время для вставки / удаления / обновления в дереве с помощью этой формы.

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

Answer 3

Не пропустить список, но, похоже, соответствует описанию проблемы: постоянные красно-черные деревья Clojure (см. PersistentTreeMap.java ).Источник содержит это уведомление:

/**
 * Persistent Red Black Tree
 * Note that instances of this class are constant values
 * i.e. add/remove etc return new values
 * <p/>
 * See Okasaki, Kahrs, Larsen et al
 */

Эти деревья поддерживают порядок элементов и являются "постоянными" в том смысле, в котором Rich Hickey использует слово (неизменяемое и способное поддерживать свои гарантии производительности, поскольку обновленные версии являютсяпостроено).

Если вы хотите поэкспериментировать с ними, вы можете создавать экземпляры в коде Clojure с помощью функции sorted-map.

Answer 4

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

Преимуществом этого вида списка пропусков будет «произвольный» доступ.Например, вы можете получить доступ к n-му элементу быстрее, чем в обычном едином связанном списке.