user2726995 - 1 year ago 63

Scala Question

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 Source

I don't know why the implementation in stdlib takes so long. However, this straightforward implementation (specialized to pairs and `List`

s), 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)
```