Is there a better way to generate a list of pairs (x,y) from a given list which preserve the order of x and y. For example computePairs(List(1,2,3)) returns a list containing (1,2), (1,3), and (2,3) but not (2,1), (3,1), or (3,2). It seems my solution is more complicated than necessary.
It seems fairly common that I encounter functions which I only know how to write using tail recursion.
That implementation is REALLY SLOW. on a 7311 length test case, my implementation finishes in about a second (wall clock timing) I let Jasper-M’s implementation run for 5 minutes and it never finished.
Without really measuring yours and my tails solution seem to be similar in memory and time usage. Though they take considerably longer than a second for me. I wonder what kind of machine you’re using.
That the combinations one is so slow might be related to the duplicate checking.
val list = List(1, 2, 3, 4)
val result = list.tails.foldLeft[List[(Int, Int)]](Nil)((acc, subList) => {
subList match {
case head :: tail => tail.map((head, _)).reverse ::: acc
case _ => acc
}
}).reverse
println(result) // prints: List((1,2), (1,3), (1,4), (2,3), (2,4), (3,4))
???
Or that:
val list = List(1, 2, 3, 4)
val result = List.unfold(list) {
case head :: tail => Some(tail.map((head, _)) -> tail)
case Nil => None
}.flatten
println(result) // prints: List((1,2), (1,3), (1,4), (2,3), (2,4), (3,4))
So now computePairs3 is faster than computePairs? Looks like your benchmarks results are rather unstable. I would consider using sbt-jmh if performance numbers are really important.
I have a suspicion that your recursive version is the fastest because it generates the least number of non-optimizable garbage. Even here: tail.map((head, _)) ::: acc - first the prefix is generated (tail.map((head, _))) and then preprending it to acc required rebuilding the prefix to point to new tail.
For reducing garbage probably something like that would be good:
It seems to me that building a list just in order to flatten it is inherently wasteful. If one can use flatMap that avoids the needs to create an intermediate object just to flatten it later.
The test case is done simply with lists of integers. But in my actual program the objects are heftier. I suppose this is why I was getting an out-of-memory error.
In some examples I’ve build lists of lists, but in other I’ve built iterators of iterators. Creating or flattening iterators in Scala 2.13 should be constant time operation as there are many iterator implementations and specialized methods on iterators.
list.tails returns Iterator. list.iterator and Iterator.unfold too (obviously).
Another scheme-like approach is to write a function to map over the cons cells, and a function to do collection using a poor man’s continuation passing style. Here is an example implementation:
// call the given client function on each cons cell in the given list,
// discarding the return values
def mapConsCells[T](data:List[T])(client:List[T]=>Unit):Unit = {
@tailrec
def recur(data: List[T]):Unit = {
if (data.nonEmpty) {
client(data)
recur(data.tail)
}
}
recur(data)
}
def withCollector[T](continuation: (T => Unit) => Unit): List[T] = {
var objects: List[T] = Nil
def collect(obj: T): Unit = {
objects = obj :: objects
}
continuation(collect)
objects
}
def computePairs5[T](data:List[T]):List[(T,T)] = {
withCollector(collect => {
mapConsCells(data) { c: List[T] =>
val a = c.head
c.tail.foreach { b: T => collect((a, b)) } }
})
}
