在Scala中如何在一个for循环中高效地迭代两个Set？

Question

我想要遍历一个Set的所有元素，然后再遍历另一个Set的所有元素，使用同一个循环。（我不关心重复元素，因为我知道这两个Set是不相交的。）

我想要在一个循环中进行迭代是因为我有一些额外的代码需要测量进度，这需要在一个循环中完成。

这种方法通常不起作用，因为它可能随意混合两个 Set ：

for(x <- firstSet ++ secondSet) {
   ...
}

这个方法能够运行，但是它会在内存中构建3个中间Seq，因此在时间和空间的使用上非常低效：

for(x <- firstSet.toSeq ++ secondSet.toSeq) {
   ...
}

- Robin Green

Answer 1

for(x <- firstSet.toIterator ++ secondSet.toIterator) {
   ...
}

这种方法不会构建任何中间数据结构，所以我认为它是最有效率的方式。

- Robin Green

---

我相当确定当调用++时，这将把两个集合都转换为长的List，因此它并不是真正高效的。不确定为什么@huynhjl删除了他的答案，但是作为参考，他建议使用额外的生成器，形式为for (set <- List(firstSet, secondSet); x <- set) { ... }，这似乎是更有效的方法。 - Luigi Plinge

@LuigiPlinge，我删除了我的回答，因为我认为我误解了问题，因为我的解决方案有一个嵌套循环。我不知道那是否仍然允许“测量进度”。由于问题缺乏关于“测量进度”的细节，所以我决定将其删除。 - huynhjl

@LuigiPlinge 看一下 scala.collection.Iterator 中 ++ 的实现。 - Robin Green

该死，他们想到了一切！但我仍然想不出为什么你不会只是使用一个额外的生成器。 - Luigi Plinge

Answer 2

如果您只需要遍历，并且希望达到最大的性能，即使它很难看，这仍然是最佳选择：

val s1 = Set(1,2,3)
val s2 = Set(4,5,6)
val block : Int => Unit = x => { println(x) }
s1.foreach(block)
s2.foreach(block)

鉴于这个看起来相当丑陋，您可以为其定义一个类：

def traverse[T](a:Traversable[T], b:Traversable[T]) : Traversable[T] = 
  new Traversable[T] { 
    def foreach[U](f:T=>U) { a.foreach(f); b.foreach(f) } 
  }

然后像这样使用它：

for(x<-traverse(s1, s2)) println(x)

然而，除非这是极其性能关键的，否则Robin Green发布的解决方案更好。它的开销是创建两个迭代器并将它们串联起来。如果您有更深层嵌套的数据结构，则串联迭代器可能会非常昂贵。例如，通过串联子树迭代器定义的树迭代器将非常缓慢，而在每个子树上调用foreach的树遍历将接近最优。

- Rüdiger Klaehn