在Scala中合并巨集（HashSet）

我有两个巨大的（如百万条目）集（HashSet），它们之间有一些（< 10％）重叠。我需要将它们合并成一个集合（我不关心维护原始集合）。在Scala中合并巨集（HashSet）

目前，我加入了一组所有的项目都与其他：

setOne ++= setTwo

这需要几分钟才能完成（后在成员调整的hashCode（）多次尝试）。

任何想法如何加快速度？

2011-08-03 Alexandros

这些是可变集合，对不对？ –

之后你对合并后的设置做什么？什么操作和多少？（我认为你可以采取一种懒惰的方式，而且如果有少量的事情你可以用它来完成，就不用费力去合并 - 只需在适当的一组或两组上做操作） –

你知道吗？性能受内存堆大小的影响？有时，当JVM耗尽堆时，由于垃圾收集器花费所有时间来回收内存，因此性能会下降。 – huynhjl

你可以用Scala的并行集合API 2.9.0+表现稍好：

setOne.par ++ setTwo

或

2011-08-03 13:13:24

这对我的四核很好用！ – Alexandros

有你可能想几件事情尝试：

在我看来，后面的选项给出了更好的结果，虽然两者都显示了测试的改进。

2011-08-03 13:58:10

这通常很有用。不幸的是，我正在进行强力搜索，并不知道各个组的大小是多少;至少直到我计算出它们为止...... – Alexandros

@Alexandros您可以在每个集合上始终调用'size'并估计合并的大小。或者使用'useSizeMap'，它不需要你告诉任何东西。 –

你能告诉我更多关于集合内的数据吗？我问的原因是，对于这种事情，你通常想要一些专业化的东西。这里有几件事情可以做：

如果数据是（或可以）排序，你可以走指针做一个合并，类似于使用合并排序完成的。此操作非常平凡，因为您可以对一个数据集进行分区，然后使用二分搜索对第二个数据集进行分区以找到正确的边界。
如果数据在特定的数字范围内，您可以使用bitset，只要您遇到该数字就设置位。
如果其中一个数据集小于另一个，则可以将其放入散列集并快速循环其他数据集，以检查是否存在遏制。

我已经使用了第一个策略在一秒钟创造一个巨大的一套约40K的小套约800万整数（上结实的硬件，Scala中）。

2011-08-03 16:09:49

回答