Tail recursion with List + .toVector or Vector?

Question

  val dimensionality = 10
  val zeros = DenseVector.zeros[Double](dimensionality)

  @tailrec private def specials(list: List[DenseVector[Int]], i: Int): List[DenseVector[Int]] = {
    if(i >= dimensionality) list
    else {
      val vec = zeros.copy
      vec(i to i) := 1
      specials(vec :: list, i + 1)
    }
  }

  val specialList = specials(Nil, 0).toVector
  specialList.map(...doing my thing...)

Should I write my tail recursive function using a List as accumulator above and then write

specials(Nil, 0).toVector

or should I write my trail recursion with a Vector in the first place? What is computationally more efficient?

By the way: specialList is a list that contains DenseVectors where every entry is 0 with the exception of one entry, which is 1. There are as many DenseVectors as they are long.

score 1 · Accepted Answer · answered Nov 04 '16 at 09:40

1

I'm not sur what you're trying to do here but you could rewrite your code like so:

type Mat = List[Vector[Int]]

@tailrec
private def specials(mat: Mat, i: Int): Mat = i match {
  case `dimensionality` => mat
  case _ => 
    val v = zeros.copy.updated(i,1)
    specials(v :: mat, i + 1)
}

As you are dealing with a matrix, Vector is probably a better choice.

answered Nov 04 '16 at 09:40

jlncrnt

46
5

I updated the question, now it should be clear what is happening. – Make42 Nov 04 '16 at 10:22

fxlae · Answer 2 · 2016-11-04T14:10:25.753

Let's compare the performance characteristics of both variants:

List: prepending takes constant time, conversion to Vector takes linear time.
Vector: prepending takes "effectively" constant time (eC), no subsequent conversion needed.

If you compare the implementations of List and Vector, then you'll find out that prepending to a List is a simpler and cheaper operation than prepending to a Vector. Instead of just adding another element at the front as it is done by List, Vector potentially has to replace a whole branch/subtree internally. On average, this still happens in constant time ("effectively" constant, because the subtrees can differ in their size), but is more expensive than prepending to List. On the plus side, you can avoid the call to toVector.

Eventually, the crucial point of interest is the size of the collection you want to create (or in other words, the amount of recursive prepend-steps you are doing). It's totally possible that there is no clear winner and one of the two variants is faster for <= n steps, whereas the other variant is faster for > n steps. In my naive toy benchmark, List/toVecor seemed to be faster for less than 8k elements, but you should perform a set of well-chosen benchmarks that represent your scenario adequately.

Tail recursion with List + .toVector or Vector?

2 Answers2