java - 单个集合的多线程搜索重复项

Question

使用我不能分成segads。至于我上面的例子，如果设置了 5 个线程，那么第一个段将采用 2 个第一个对象，第二个第 3 个和第 4 个，所以他们找不到 dups，但是如果我们合并它们，它的第 2 个和第 3 个有 dups。

从第一个线程可能会有更复杂的策略.. 啊没关系，很难解释。

当然，问题本身也在我的计划中。

编辑 ：

InChunk，然后继续分析该块直到结束。;/

Answer 1

我认为划分要重复数据删除的项目的过程将不得不查看该部分的末尾并继续前进以涵盖过去的重复数据。例如，如果您有：

1  1  2 . 2  4  4 . 5  5  6

然后你分成 3 个块，然后分割过程需要1 1 2，但看到有另一个块2，所以它会1 1 2 2作为第一个块生成。它会再次向前移动 3 并生成4 4 5，但看到有 dups forward 和 generate 4 4 5 5。第三个线程将只有6. 它会变成：

1  1  2  2 . 4  4  5  5 . 6

块的大小将不一致，但随着整个列表中的项目数量变大，这些小的变化将是微不足道的。最后一个线程可能几乎没有什么可做的，或者完全改变了，但同样，随着元素的数量变大，这不应该影响算法的性能。

我认为这种方法比让一个线程处理重叠块更好。使用这种方法，如果您有很多 dup，如果您在放置 dup 时不走运，您可能会看到它必须处理超过 2 个连续的块。例如：

1  1  2 . 2  4  5 . 5  5  6

由于 2s 和 5s，一个线程必须处理整个列表。

Answer 2

我会使用基于块的划分、任务队列（例如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

由于每个线程的私有表，这可能会占用一些空间，但会允许线程并行操作，直到最后的合并阶段。