user2726995 user2726995 - 24 days ago 6
Scala Question

Scala combinations function not terminating

I need to generate the combinations for a list of 30,000 items using scalas combinations method on a stream / list

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


This function never completes. When I try the same operation in python

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


The operation completes in 26.2 seconds.

Whats going on here? How can I generate the combinations of a very large list in scala?

Answer

I don't know why the implementation in stdlib takes so long. However, this straightforward implementation (specialized to pairs and Lists), is comparable to the Python one:

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

Then

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)