Scala 组合函数不终止

Question

我需要在流/列表上使用 Scalas 组合方法为包含 30,000 个项目的列表生成组合

1 to 30000.toStream.combinations(2).size

此函数永远不会完成。当我在 python

中尝试相同的操作时

r = list(range(1,30000))
z = itertools.combinations(r, 2)
%time sum(1 for _ in z)

操作在 26.2 秒内完成。

这是怎么回事？如何在 Scala 中生成一个非常大的列表的组合？

Answer 1

我不知道为什么stdlib 中的实现需要这么长时间。但是，这种直接的实现（专门用于成对和 Lists）与 Python 的实现相当：

def combinations2[A](l: List[A]): Iterator[(A, A)] =
  l.tails.flatMap(_ match {
    case h :: t => t.iterator.map((h, _))
    case Nil => Iterator.empty
  })

然后

scala> {
     |   val t0 = System.nanoTime
     |   val res = combinations2((1 to 30000).toList).size
     |   val secs = (System.nanoTime - t0) / 1000000.0
     |   s"$res (computed in $secs seconds)"
     | }
res11: String = 449985000 (computed in 24992.487638 seconds)

Answer 2

@TomasMikula 提供了一个替代方案，我很想知道为什么 combinations 在生成结果时效率低下。

使用 Mission Control 和 Flight Recorder 快速查看发现问题：

CombinationItr 迭代器在 next() 的每次迭代中调用 IndexedSeqOptimized.slice。 ArrayBuilder 每次运行时都会创建一个新的构建器，其中包含需要迭代的元素数量，这意味着它将分配 30,000 Array[Int]，每个包含 n - 1 个元素，导致总共 11.10GB 1 分钟样本。这会导致大量的 GC 压力并且通常不是很有效。

Scala 组合函数不终止

Scala combinations function not terminating

scala

scalaz