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

@TomasMikula提供了另一种选择,我有兴趣了解为什么combinations在生成结果时效率低下.

使用Mission Control和Flight Recorder快速查看问题:

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

Answer 2

我不知道为什么stdlib中的实现需要这么长时间.但是,这个简单的实现(专门用于pair和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)