0

I implememted two versions of the collatz problem and felt an icy terror in the pit of my stomach as an optimized solution was slower than tail. The tail recursion is simple:

// calculate the next term in a Collatz sequence
def nextTerm(term: Long): Long = 
  if (term % 2 == 0) term / 2 else (3 * term) + 1

def byTailRecursion(upperbound: Long) = {
  range(upperbound)
    .map(x => (x, tailRec(x)))
    .maxBy(_._2)
}

@tailrec
def tailRec(term: Long, length: Int = 0): Int =
  term match {
    case x if x == 1l => length + 1
    case x => tailRec( nextTerm(x), length+1)
}

I believed that the nextTerm function would be the most computationally expensive because of the modulo and division involved. The attempt to optimize it was to save sequence lengths in a map identified by the current number. If during a computation a collatz sequence already was computed we would get the length of it and avoid unnecessary calculations:

def savePaths(upperbound: Long) = {
  var cLengths = scala.collection.mutable.Map(1l -> 1)
  for(i <- 2l to upperbound) {
    var queue = new mutable.Queue[Long]
    queue.enqueue(i)
    var j = nextTerm(i)
    while(!cLengths.contains(j)) {
      queue.enqueue(j)  
      j = nextTerm(j)
    }
    queue.dequeueWhile((term) => {
    cLengths(term) = queue.size + cLengths(j)
    queue.size > 0
    })
  }
  cLengths.maxBy(_._2)
}

However, in practice as numbers got large the "optimized" savePaths solution became significantly slower. When the upperbound was 1,000,000 tailrecursion ran in one-fourth of the time on average from the savePaths version. the nextTerm function, however, was called approximately 1 million times less than with tail recursion.

I suppose the major offender is lookups in the cLengths map? The other possibility is that Scala is parallelizing the tail recursion call but I'm not sure.

3
  • as the numbers got larger, the map too should get larger and hence (1) more allocations, (2)the map index too might get inefficient or require rebuild unless you have an index method already defined based on the data domain. – Surya Pratap Nov 24 '19 at 5:37
  • That's a good point. I'll look into configuring this he map differently – IcedDante Nov 24 '19 at 12:39
  • Also memosiation may be causing paging to occur to the disk, which is probably an ssd, but still slower than main memory < cache < registers. If you are going to take this approach you may want to consider wiring memory, and perhaps have a retention policy to selectively maintain resume points. – Kain0_0 May 25 '20 at 5:04
1

Answer: You are comparing two entirely different algorithms, and in one of them you use tail recursion instead of a loop. I suggest you write a third version which just does a loop without storing anything, so you can measure the effect of tail recursion and the effect of storing values separately. You can't change two variables and assume that a difference in results is due to changing the first variable.

PS What does your language do in case of overflow? Silently give the wrong results?

2
  • 1
    Sorry- is this an answer? It seems like a comment/question. – IcedDante Nov 27 '19 at 2:45
  • Obviously an answer. – gnasher729 May 24 '20 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.