これが正しいかどうかは完全にはわかりませんが、コメントのために捨てると思いました。まず、提案するアルゴリズムの重要な部分を形成する、ロックレスの素集合アルゴリズムを紹介します。
ロックレス素集合アルゴリズム
選択したCPUアーキテクチャで、2ポインタサイズのコンペアアンドスワップ操作が存在すると想定しています。これは、少なくともx86およびx64アーキテクチャで使用できます。
アルゴリズムは、ウィキペディアのシングルスレッドの場合のページで説明されているものとほぼ同じですが、安全なロックレス操作のためにいくつかの変更が加えられています。まず、後でアトミックCASを実行するために、ランク要素と親要素の両方をポインターサイズにし、メモリ内で2 * sizeof（pointer）に揃える必要があります。
Find（）を変更する必要はありません。最悪のケースは、パス圧縮の最適化が、同時ライターが存在する場合に完全に効果を発揮できないことです。
ただし、Union（）は変更する必要があります。
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
これは、ループを形成せず、常に適切な結合をもたらすという点で安全である必要があります。これは、次のことを観察することで確認できます。
- まず、終了する前に、2つのルートの一方は常にもう一方を指す親になります。したがって、ループがない限り、マージは成功します。
- 第二に、ランクは常に増加します。xとyの順序を比較すると、スナップショットの時点でxのランクがyよりも低いことがわかります。ループを形成するには、別のスレッドが最初にxのランクを上げてから、xとyをマージする必要があります。ただし、xの親ポインタを書き込むCASでは、ランクが変更されていないことを確認します。したがって、yのランクはxより大きくなければなりません。
同時ミューテーションの場合、yのランクが上がり、競合のためにやり直しに戻る可能性があります。ただし、これは、yがルートではなくなったか（この場合、ランクは関係ありません）、またはyのランクが別のプロセスによって増加したことを意味します（この場合、2回目の実行は効果がなく、yは正しいランクになります）。
したがって、ループが形成される可能性はなく、このロックレスの素集合アルゴリズムは安全である必要があります。
そして今、あなたの問題への応用に移ります...
仮定
尾根セグメントはそれらの端点でのみ交差できると仮定します。そうでない場合は、何らかの方法でフェーズ1を変更する必要があります。
また、リッジセグメントを接続するには、単一の整数ピクセル位置の共存で十分であると仮定します。そうでない場合は、フェーズ1で配列を変更して、複数の候補リッジセグメントと互いに素なセットのペアを保持し、フィルター処理して実際に接続されているものを見つける必要があります。
このアルゴリズムで使用される互いに素な集合構造は、それらの構造内の線分への参照を運ぶものとします。マージの場合、セットを表すために2つの記録されたセグメントの1つを任意に選択します。
フェーズ1：ローカル回線の識別
まず、マップをセクターに分割します。各セクターは個別のジョブとして処理されます。複数のジョブが異なるスレッドで処理される場合がありますが、各ジョブは1つのスレッドでのみ処理されます。尾根セグメントがセクターと交差する場合、セクターごとに1つずつ、2つのセグメントに分割されます。
セクターごとに、ピクセル位置を素集合構造にマッピングする配列が確立されます。この配列のほとんどは後で破棄されるため、そのメモリ要件はそれほど大きな負担にはなりません。
次に、セクター内の各線分に進みます。まず、セグメントが一部を形成する線全体を表す互いに素なセットを選択します。まず、ピクセル位置配列の各エンドポイントを調べて、互いに素なセット構造がすでに割り当てられているかどうかを確認します。エンドポイントの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）をスキップします。次に、代表的な線分から始めて、そこから移動し、問題の線について必要な情報を収集して記録します。交差する線は同じ互いに素なセット構造になってしまうため、一度に1つのスレッドだけが任意の線を見ていることが保証されます。
これには、O（m）の実行時間と、これらの線分について収集する必要のある情報に応じたメモリ使用量があります。
概要
全体として、このアルゴリズムにはO（x * y）の実行時間と、O（x * y / k + k ^ 2）のメモリ使用量が必要です。kを調整すると、フェーズ1プロセスでの一時的なメモリ使用量と、フェーズ2に持ち越された隣接配列および互いに素な構造の長期的なメモリ使用量との間のトレードオフが得られます。
私は実際にこのアルゴリズムのパフォーマンスを実際にテストしていないことに注意してください。上記のロックレス素集合データ結合マージアルゴリズムの同時実行性の問題を見落としている可能性もあります。コメント歓迎:)
