重複のための単一のコレクションのマルチスレッド検索

Question

使用私はsegadsに分割することはできません。私の上記の例では、5つのスレッドが設定されている場合、最初のセグメントは2つの最初のオブジェクトを取り、2番目の3番目と4番目のセグメントはdupを見つけられませんが、2番目と3番目をマージするとdupsがあります。

最初のスレッドからもっと複雑な構造を取ることができます。ああ、心配しないで説明するのは難しいです。

もちろん、私の計画では予報そのもの。その後、

InChunk、そして最後までそのチャンクを分析し続ける：

ター EDIT。 ;/

Answer 1

私はチャンクベースの分割、タスクキュー（例：ExecutorService）とプライベートハッシュテーブルを使用して重複を収集します。

プール内の各スレッドは、要求に応じてキューからチャンクを取り出し、プライベートハッシュテーブル内のアイテムのキーに対応する値に1を加算します。最後に、グローバルハッシュテーブルとマージします。終わり

だけハッシュテーブルを解析し、キーが3のチャンクサイズとアイテムと例えば1

より大きい値を有する参照：

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 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 

これは、各スレッドのプライベートテーブルにスペースある程度の量を取るかもしれませんが、スレッドが最後にマージ・フェーズまで、並列に動作することができます。

Answer 2

デデュープされるアイテムを分割するプロセスは、セクションの終わりを見て、それを超えてダブを含むように進むべきだと思います。あなたが持っていた場合、例えば：

1 1 2 . 2 4 4 . 5 5 6 

そして、あなたは3のブロックに分割する場合、分割処理は1 1 2を取るが、別の2はそれが最初のブロックとして1 1 2 2を生成していたことがわかります。それは再び3に進み、4 4 5を生成しますが、dupsが前方にあり、4 4 5 5を生成することがわかります。 3番目のスレッドは6となります。ブロックのサイズは矛盾であることを行っている

1 1 2 2 . 4 4 5 5 . 6 

が、全体のリスト内の項目数が多くなるにつれて、これらの小さな変化は軽微であることを行っている：それはなるだろう。最後のスレッドは、行うことがほとんどないか、または短く変更されているかもしれませんが、要素の数が多くなるにつれて、アルゴリズムのパフォーマンスに影響を与えるべきではありません。

私は、この方法は、何らかの形で1つのスレッドが重複するブロックを処理するよりも優れていると思います。その方法では、dupsがたくさんある場合、dupsのポジションに不運な場合は、2つ以上の連続ブロックを処理する必要があることがわかります。例：

1 1 2 . 2 4 5 . 5 5 6 

2つのスレッドと5つのスレッドのために、1つのスレッドでリスト全体を処理する必要があります。