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

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

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

Можем ли мы сделать лучше?

Часть проблемы заключается в том, что существует несколько путей от -infinity к вашему элементу.

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

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

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

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

-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), и вы можете использовать рандомизированную структуру списка пропуска или детерминированную, как обычно.

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

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

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

Ответ 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.

Ответ 4

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

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