Scala function combinations does not end

Question

I need to generate combinations for a list of 30,000 elements using the method of skyce combinations in a stream / list

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

This function never ends. When I try to perform the same operation in python

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

The operation ends in 26.2 seconds.

What's going on here? How can I generate combinations of a very large list in scala?

Answer 1

I do not know why the implementation in stdlib takes so much time. However, this simple implementation (specialized for pairs and Lists) is comparable to 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
  })

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)

Answer 2

@TomasMikula , , combinations .

:

CombinationItr IndexedSeqOptimized.slice next(). ArrayBuilder , , , , 30 000 Array[Int], n - 1 , 11,10 1 , GC , , .