セガドに分割できません。上記の例では、5 つのスレッドが設定されている場合、最初のセグメントは 2 つの最初のオブジェクト、2 番目の 3 番目と 4 番目のオブジェクトを取るため、重複は見つかりませんが、2 番目と 3 番目のそれらをマージすると重複があります。
最初のスレッドからより複雑な戦略が取られる可能性があります..ああ、気にしないでください。説明するのは難しいです。
そしてもちろん、私の計画における問題自体。
編集 ：
InChunk に移動し、そのチャンクを最後まで分析し続けます。;/
重複排除されるアイテムを分割するプロセスは、セクションの最後を見て、それを過ぎた重複を含むように前進する必要があると思います。たとえば、次の場合:
1 1 2 . 2 4 4 . 5 5 6
そして、3つのブロックに分割すると、分割プロセスに時間がかかります1 1 2が、別のブロックがあることがわかり、最初のブロックとして2生成されます. 1 1 2 2再び forward 3 して generate4 4 5しますが、 dups forward と generate があったことがわかります4 4 5 5。3 番目のスレッドには6. それは次のようになります。
1 1 2 2 . 4 4 5 5 . 6
ブロックのサイズは一定ではありませんが、リスト全体のアイテム数が大きくなると、これらの小さな変更は重要ではなくなります。最後のスレッドは、実行することがほとんどないか、完全に短く変更されている可能性がありますが、要素の数が大きくなっても、これはアルゴリズムのパフォーマンスに影響を与えるべきではありません。
この方法は、オーバーラップするブロックを 1 つのスレッドで処理するよりも優れていると思います。その方法では、dup がたくさんある場合、dup の位置付けが不運だった場合、2 つ以上の連続したブロックを処理する必要があることがわかります。例えば：
1 1 2 . 2 4 5 . 5 5 6
2 と 5 があるため、1 つのスレッドがそのリスト全体を処理する必要があります。
チャンクベースの分割、タスク キュー (例: ExecutorService)、およびプライベート ハッシュ テーブルを使用して重複を収集します。
プール内の各スレッドは、オンデマンドでキューからチャンクを取得し、プライベート ハッシュ テーブル内の項目のキーに対応する値に 1 を追加します。最後に、それらはグローバル ハッシュ テーブルとマージされます。
最後に、ハッシュ テーブルを解析して、どのキーの値が 1 より大きいかを確認します。
たとえば、チャンク サイズが 3 でアイテムが次の場合:
1 2 2 2 3 4 5 5 6 6
プールに 2 つのスレッドがあるとします。スレッド 1 は 1 2 2 を受け取り、スレッド 2 は 2 3 4 を受け取ります。プライベート ハッシュ テーブルは次のようになります。
1 1
2 2
3 0
4 0
5 0
6 0
と
1 0
2 1
3 1
4 1
5 0
6 0
次に、スレッド 1 は 5 5 6 を処理し、スレッド 2 は 6 を処理します。
1 1
2 2
3 0
4 0
5 2
6 1
と
1 0
2 1
3 1
4 1
5 0
6 1
最後に、重複は 2、5、および 6 です。
1 1
2 3
3 1
4 1
5 2
6 2
これは、各スレッドのプライベート テーブルのためにある程度のスペースを占有する可能性がありますが、最後のマージ フェーズまでスレッドが並行して動作できるようにします。