Большинство многопоточных структур данных не гарантирует неизменности порядка элементов в случае, если эта структура изменяется во время прохождения. То же верно, кстати, и в случае большинства изменяемых коллекций. Особенность многопоточных префиксных деревьев– tries– заключается в том, что они позволяют модифицировать само дерево, которое в данный момент просматривается. Сделанные изменения становятся видимыми только при следующем прохождении. Так ведут себя и последовательные префиксные деревья, и их параллельные аналоги; единственное отличие– в том, что первые перебирают элементы последовательно, а вторые– параллельно.
Это замечательное свойство позволяет упростить ряд алгоритмов. Обычно это такие алгоритмы, в которых некоторый набор данных обрабатывается итеративно, причем для обработки различных элементов требуется различное количество итераций.
В следующем примере вычисляются квадратные корни некоторого набор чисел. Каждая итерация обновляет значение квадратного корня. Числа, квадратные корни которых достигли необходимой точности, исключаются из перебираемого набора.
case class Entry(num: Double) {
var sqrt = num
}
val length = 50000
// готовим исходные данные
val entries = (1 until length) map { num => Entry(num.toDouble) }
val results = ParTrieMap()
for (e <- entries) results += ((e.num, e))
// вычисляем квадратные корни
while (results.nonEmpty) {
for ((num, e) <- results) {
val nsqrt = 0.5 * (e.sqrt + e.num / e.sqrt)
if (math.abs(nsqrt - e.sqrt) < 0.01) {
results.remove(num)
} else e.sqrt = nsqrt
}
}
Отметим, что в приведенном выше вычислении квадратных корней вавилонским методом ([3]) некоторые значения могут сойтись гораздо быстрее, чем остальные. По этой причине мы исключаем их из results, чтобы перебирались только те элементы, которые нуждаются в дальнейшей обработке.
Другим примером является алгоритм поиска в ширину, который итеративно расширяет очередь перебираемых узлов до тех пор, пока или не будет найден целевой узел, или не закончатся узлы, за счет которых можно расширить поиск. Определим точку на двухмерной карте как кортеж значений Int. Обозначим как map двухмерный массив булевых значений, которые обозначают, занята соответствующая ячейка или нет. Затем объявим два многопоточных дерева– open, которое содержит все точки, которые требуется раскрыть, и closed, в котором хранятся уже обработанные точки. Мы намерены начать поиск с углов карты и найти путь к центру– инициализируем ассоциативный массив open подходящими точками. Затем будем раскрывать параллельно все точки, содержащиеся в ассоциативном массиве open до тех пор, пока больше не останется точек. Каждый раз, когда точка раскрывается, она удаляется из массива open и помещается в массив closed.
Выполнив все это, выведем путь от целевого до стартового узла.
val length = 1000
// объявляем тип Node
type Node = (Int, Int);
type Parent = (Int, Int);
// операции над типом Node
def up(n: Node) = (n._1, n._2 - 1);
def down(n: Node) = (n._1, n._2 + 1);
def left(n: Node) = (n._1 - 1, n._2);
def right(n: Node) = (n._1 + 1, n._2);
// создаем карту и целевую точку
val target = (length / 2, length / 2);
val map = Array.tabulate(length, length)((x, y) => (x % 3) != 0 || (y % 3) != 0 || (x, y) == target)
def onMap(n: Node) = n._1 >= 0 && n._1 < length && n._2 >= 0 && n._2 < length
// список open - фронт обработки
// список closed - уже обработанные точки
val open = ParTrieMap[Node, Parent]()
val closed = ParTrieMap[Node, Parent]()
// добавляем несколько стартовых позиций
open((0, 0)) = null
open((length - 1, length - 1)) = null
open((0, length - 1)) = null
open((length - 1, 0)) = null
// "жадный" поиск в ширину
while (open.nonEmpty && !open.contains(target)) {
for ((node, parent) <- open) {
def expand(next: Node) {
if (onMap(next) && map(next._1)(next._2) && !closed.contains(next) && !open.contains(next)) {
open(next) = node
}
}
expand(up(node))
expand(down(node))
expand(left(node))
expand(right(node))
closed(node) = parent
open.remove(node)
}
}
// выводим путь
var pathnode = open(target)
while (closed.contains(pathnode)) {
print(pathnode + "->")
pathnode = closed(pathnode)
}
println()
На GitHub есть пример реализации игры “Жизнь”, который использует многопоточные хэш-деревья– Ctries, чтобы выборочно симулировать только те части механизма игры, которые в настоящий момент активны [4].
Он также включает в себя основанную на Swing визуализацию, которая позволяет посмотреть, как подстройка параметров влияет на производительность.
Многопоточные префиксные деревья также поддерживают атомарную, неблокирующую(lock-free) операцию snapshot, выполнение которой осуществляется за постоянное время. Эта операция создает новое многопоточное дерево со всеми элементами на некоторый выбранный момент времени, создавая таким образом снимок состояния дерева в этот момент.
На самом деле, операция snapshot просто создает новый корень дерева. Последующие изменения отложенно перестраивают ту часть многопоточного дерева, которая соответствует изменению, и оставляет нетронутой ту часть, которая не изменилась. Прежде всего это означает, что операция ‘snapshot’ сама по себе не затратна, так как не происходит копирования элементов. Кроме того, так как оптимизация “копирования при записи” создает копии только измененных частей дерева, последующие модификации горизонтально масштабируемы.
Метод readOnlySnapshot чуть более эффективен, чем метод snapshot, но он возвращает неизменяемый ассоциативный массив, который доступен только для чтения. Многопоточные деревья также поддерживают атомарную операцию постоянного времени clear, основанную на рассмотренном механизме снимков.
Чтобы подробнее узнать о том, как работают многопоточные деревья и их снимки, смотрите [1] и [2].
На рассмотренном механизме снимков основана работа итераторов многопоточных деревьев. Прежде чем будет создан объект-итератор, берется снимок многопоточного дерева. Таким образом, итератор перебирает только те элементы дерева, которые присутствовали на момент создания снимка. Фактически, итераторы используют те снимки, которые дают доступ только на чтение.
На том же механизме снимков основана операция size. В качестве примитивной реализации этой операции можно просто создать итератор (то есть, снимок) и перебрать все элементы, подсчитывая их. Таким образом, каждый вызов операции size будет требовать времени, прямо пропорционального числу элементов. Однако, многопоточные деревья в целях оптимизации кэшируют размеры своих отдельных частей, тем самым уменьшая временную сложность метода size до амортизированно-логарифмической. В результате получается, что если вызвать метод size один раз, можно осуществлять последующие вызовы size затрачивая минимум ресурсов, вычисляя, как правило, размеры только тех частей, которые изменились после последнего вызова size. Кроме того, вычисление размера параллельных многопоточных деревьев выполняется параллельно.