Чисто функциональный параллельный список пропуска
Пропустите списки (Pugh, 1990) предоставляют отсортированным словарям логарифмически-разовые операции как деревья поиска, но пропускают списки, намного более поддаются параллельным обновлениям.
Действительно ли возможно создать эффективный чисто функциональный параллельный список пропуска? В противном случае действительно ли возможно создать какой-либо вид эффективного чисто функционального параллельного отсортированного словаря?
2 ответа
Свойство списков пропуска, которое делает их пригодными для одновременных обновлений (а именно, что большинство сложений и вычитаний являются локальными), также ухудшает их неизменяемость (а именно то, что многие более ранние элементы в списке указывают в конечном итоге на более поздние элементы, и пришлось бы поменять).
В частности, списки пропуска состоят из структур, которые выглядят следующим образом:
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 , которую вы можете применить все за один раз (или вам придется выполнять различные другие очень умные штуки).
Однако одновременное чтение фантастически хорошо работает с неизменяемыми структурами данных, поскольку вы гарантированно не измените состояние. Если вы не предполагаете, что у вас может быть цикл чтения / записи, который разрешается до того, как любая другая запись может прерваться, тогда вам никогда не придется блокировать чтение.
Таким образом, структуры данных с большим объемом записи, вероятно, лучше реализовывать изменчиво (и с чем-то вроде списка пропуска, где требуется только локальная блокировка), в то время как структуры данных с интенсивным чтением, вероятно, лучше реализовать неизменяемо (где дерево является более сложным). естественная структура данных).
Не список пропуска, но, похоже, соответствует описанию проблемы: постоянные красно-черные деревья 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
*/
Эти деревья поддерживают порядок элементов и являются «постоянными» в том смысле, в котором Рич Хикки использует это слово (неизменяемые и способные поддерживать свои гарантии производительности по мере создания обновленных версий).
Если вы хотите поиграть с ними, вы можете создавать экземпляры в коде Clojure с помощью функции sorted-map .