Ответ 1
Я не совсем уверен, что это правильно, но я думал, что выброшу его для комментариев. Во-первых, позвольте мне представить алгоритм блокировки непересекающихся множеств, который станет важной частью моего предложенного алгоритма.
Запрещенный алгоритм непересекающихся множеств
Я предполагаю наличие операции сравнения и замены с двумя указателями по вашему выбору архитектуры процессора. Это доступно для архитектуры x86 и x64 как минимум.
Алгоритм во многом аналогичен алгоритму странице Википедии для однопоточного случая с некоторыми изменениями для безопасной блокировки. Во-первых, мы требуем, чтобы ранговые и родительские элементы были как размер указателя, так и согласованы с 2 * sizeof (указателем) в памяти, для атомного CAS позже.
Найти() не нужно изменять; худший случай заключается в том, что оптимизация сжатия пути не будет иметь полного эффекта при наличии одновременных авторов.
Союз(), однако, должен измениться:
function Union(x, y)
redo:
x = Find(x)
y = Find(y)
if x == y
return
xSnap = AtomicRead(x) -- read both rank and pointer atomically
ySnap = AtomicRead(y) -- this operation may be done using a CAS
if (xSnap.parent != x || ySnap.parent != y)
goto redo
-- Ensure x has lower rank (meaning y will be the new root)
if (xSnap.rank > ySnap.rank)
swap(xSnap, ySnap)
swap(x, y)
-- if same rank, use pointer value as a fallback sort
else if (xSnap.rank == ySnap.rank && x > y)
swap(xSnap, ySnap)
swap(x, y)
yNew = ySnap
yNew.rank = max(yNew.rank, xSnap.rank + 1)
xNew = xSnap
xNew.parent = y
if (!CAS(y, ySnap, yNew))
goto redo
if (!CAS(x, xSnap, xNew))
goto redo
return
Это должно быть безопасным, поскольку он никогда не будет создавать циклы и всегда будет иметь правильный союз. Мы можем подтвердить это, заметив, что:
- Во-первых, до завершения один из двух корней всегда будет иметь родителя, указывающего на другой. Поэтому, если цикл отсутствует, слияние будет успешным.
- Во-вторых, ранг всегда увеличивается. После сравнения порядка x и y мы знаем, что x имеет меньший ранг, чем y во время моментального снимка. Для того, чтобы петля сформировалась, другой поток должен был сначала увеличить ранг x, а затем объединить x и y. Однако в CAS, который пишет x родительский указатель, мы проверяем, что ранг не изменился; поэтому y-ранг должен оставаться больше x.
В случае одновременной мутации возможно, что у-ранг может быть увеличен, а затем вернуться к повторному использованию из-за конфликта. Однако это означает, что либо y больше не является корнем (в этом случае ранг не имеет значения), либо у-ранг был увеличен другим процессом (в этом случае второй ход не будет иметь эффекта, а y будет иметь правильный ранг).
Следовательно, не должно быть никаких шансов на формирование петель, и этот незанятый алгоритм несвязанного набора должен быть безопасным.
И теперь к приложению к вашей проблеме...
Предположения
Я делаю предположение, что сегменты хребта могут пересекаться только на своих конечных точках. Если это не так, вам нужно каким-то образом изменить фазу 1.
Я также делаю предположение, что совместное проживание одного целочисленного пиксельного местоположения является достаточным для сегментов хребта. Если нет, вам нужно будет изменить массив в фазе 1, чтобы удержать несколько сегментов хребта кандидатов + пары с непересекающимися наборами и пропустить фильтр, чтобы найти те, которые действительно связаны.
Структуры непересекающихся множеств, используемые в этом алгоритме, должны содержать ссылку на сегмент линии в их структурах. В случае слияния мы выбираем один из двух записанных сегментов произвольно для представления множества.
Этап 1: идентификация локальной сети
Начнем с деления отображения на сектора, каждый из которых будет обрабатываться как отдельное задание. Несколько заданий могут обрабатываться в разных потоках, но каждое задание будет обрабатываться только одним потоком. Если сегмент хребта пересекает сектор, он делится на два сегмента, по одному для каждого сектора.
Для каждого сектора устанавливается положение пикселя отображения массива в структуру с несвязанной сеткой. Большая часть этого массива будет отброшена позже, поэтому его требования к памяти не должны быть слишком тяжелыми.
Затем мы переходим к каждому сегменту линии в секторе. Сначала выберем непересекающееся множество, представляющее всю линию, часть которой образует часть. Сначала мы просматриваем каждую конечную точку в массиве пикселей, чтобы увидеть, была ли уже назначена структура несвязанных множеств. Если одна из конечных точек уже находится в этом массиве, мы используем назначенный непересекающийся набор. Если оба находятся в массиве, мы выполняем слияние на непересекающихся множествах и используем новый корень как наш набор. В противном случае мы создадим новый непересекающийся набор и сопоставим с непересекающейся структурой ссылку на текущий сегмент линии. Затем мы записываем обратно в массив пиксельных позиций наш новый корневой корень для каждой из наших конечных точек.
Этот процесс повторяется для каждого сегмента линии в секторе; к концу мы будем идентифицировать все линии полностью внутри сектора непересекающимся множеством.
Обратите внимание, что поскольку непересекающиеся наборы еще не разделены между потоками, нет необходимости использовать операции сравнения и замены; просто используйте обычный однопоточный алгоритм объединения-слияния. Поскольку мы не освобождаем какую-либо из непересекающихся структур множества до тех пор, пока алгоритм не завершится, распределение также может быть выполнено из распределяющего блока распределения потоков, что делает невозможным блокирование памяти (фактически) и O (1).
Как только сектор полностью обработан, все данные в массиве пиксельных позиций отбрасываются; однако данные, соответствующие пикселям на краю сектора, копируются в новый массив и сохраняются для следующей фазы.
Так как итерация по всему изображению O (x * y), а дизъюнктное слияние эффективно O (1), эта операция O (x * y) и требует рабочей памяти O (m + 2 * x * y/k + k ^ 2) = O (x * y/k + k ^ 2), где t - число секторов, k - ширина сектора, а m - число сегментов частичной части сектора ( в зависимости от того, как часто линии пересекают границы, m может значительно различаться, но никогда не будет превышать количество сегментов линии). Память, перенесенная на следующую операцию, равна O (m + 2 * x * y/k) = O (x * y/k)
Этап 2: кросс-секторные слияния
После обработки всех секторов мы переходим к объединению строк, которые пересекают сектора. Для каждой границы между секторами мы выполняем операции блокировки слияния на линиях, которые пересекают границу (т.е. Где соседние пиксели на каждой стороне границы назначены наборам строк).
Эта операция имеет время работы O (x + y) и потребляет память O (1) (мы должны сохранить память из фазы 1, однако). По завершении реберные массивы могут быть отброшены.
Фаза 3: Сбор строк
Теперь мы выполняем операцию многопоточной карты над всеми выделенными объектами структуры с разбивкой. Сначала пропустите любой объект, который не является корнем (т.е. Где obj.parent!= Obj). Затем, начиная с репрезентативного сегмента линии, мы выходим оттуда и собираем и записываем любую информацию, необходимую о соответствующей строке. Мы уверены, что только один поток смотрит на любую заданную строку за раз, так как пересекающиеся линии оказались бы в одной и той же структуре с непересекающимися сетями.
Это время работы O (m) и использование памяти зависят от того, какую информацию вам нужно собирать по этим сегментам линии.
Резюме
В целом, этот алгоритм должен иметь время работы O (x * y) и использование памяти O (x * y/k + k ^ 2). Корректировка k дает компромисс между использованием переходной памяти в процессах фазы 1 и более длительным использованием памяти для массивов смежности и структур с несвязанной сетью, перенесенных в фазу 2.
Обратите внимание, что я действительно не тестировал производительность этого алгоритма в реальном мире; также возможно, что я упустил проблемы concurrency в алгоритме объединения-слияния без блокировки, описанном выше. Комментарии приветствуются:)
