多線程搜索單個集合的副本

Question

使用我無法分割成多個分區。至於我上面的例子，如果設置了5個線程，那麼第一個分段會佔用2個第一個對象，第二個第三個和第四個分組，所以他們不會找到dups，但是如果我們合併它們，第二個和第三個會有dups。

從第一個線程可能會有更復雜的戰略..啊，沒關係，難以解釋。

而當然，在我的計劃中，問題本身。

臨屋 編輯：

InChunk，然後繼續分析該塊，直到結束。 ;/

Answer 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 

這可能的空間一定量佔用由於每個線程的私有表，但將允許線程並行地操作，直到在最後的合併階段。

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。第三個線程將只有6。這將成爲：

1 1 2 2 . 4 4 5 5 . 6 

塊的大小將是不一致的，但作爲項目的整個列表中的號碼變大，這些小的變化都將是微不足道的。最後一個線程可能做的很少，或者完全沒有改變，但是隨着元素數量變大，這不應該影響算法的性能。

我認爲這種方法會比以某種方式處理重疊塊更好。用這種方法，如果你有很多的孿生兄弟，你可能會發現它不得不處理兩個以上的連續塊，如果你在運氣不好的時候不走運的話。例如：

1 1 2 . 2 4 5 . 5 5 6 

一個線程將不得不處理整個列表，因爲2s和5s。