scala - Scala 中不可变集合实现的性能

Question

我最近一直在深入研究 Scala，并且(也许可以预见)花了很多时间研究 Scala 标准库中的不可变集合 API。

我正在编写一个应用程序，它必须在大型集合上执行许多 +/- 操作。出于这个原因，我想确保我选择的实现是所谓的“持久”数据结构，这样我就避免了写时复制。我看到了 this answer由 Martin Odersky 撰写，但它并没有真正解决我的问题。

我编写了以下测试代码来比较 ListSet 和 HashSet 对添加操作的性能:

import scala.collection.immutable._

object TestListSet extends App {
  var set = new ListSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

object TestHashSet extends App {
  var set = new HashSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

这是 HashSet 的粗略运行时测量:

$ time scala TestHashSet

real    0m0.955s
user    0m1.192s
sys     0m0.147s

和列表集:

$ time scala TestListSet

real    0m30.516s
user    0m30.612s
sys     0m0.168s

单向链表的缺点是时间恒定的操作，但这种性能看起来是线性的或更糟。这种性能下降是否与需要检查集合的每个元素的对象相等性以符合 Set 的无重复不变量有关？如果是这种情况，我意识到这与“持久性”无关。

至于官方文档，我只能找到以下页面，但似乎不完整: Scala 2.8 Collections API -- Performance Characteristics .由于 ListSet 最初似乎是其内存占用的不错选择，因此 API 文档中可能应该有一些有关其性能的信息。

Answer 1

关键线来自ListSet来源是(在子类 Node 内):

override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e)

您可以在其中看到仅当尚未包含某个项目时才添加该项目。所以添加到集合是 O(n) .您通常可以假设 XMap 具有与 XSet 相似的性能特征，并且 ListMap一直被列为线性时间。这就是为什么，这也是集合应该表现的方式。

附言在 TestHashSet 情况下，您正在测量启动时间。它的速度快了 30 倍以上。