0

Clearly, if you need to count up, count up. If you need to count down, count down. However, other things being equal, is one faster than the other? Here is my Scala code for a well-known puzzle - checking if a number is divisible by 13. In the first example, I reverse my array and count upwards in the subsequent for-loop. In the second example I leave the array alone and do a decrementing for-loop. On the surface, the second example looks faster. Unfortunately, on the site where I run the code, it always times out.

 // works every time
object Thirteen {
import scala.annotation.tailrec

  @tailrec
  def thirt(n: Long): Long = {
    val getNum = (n: Int) => Array(1, 10, 9, 12, 3, 4)(n % 6)
    val ni  = n.toString.split("").reverse.map(_.toInt)
    var s: Long = 0
    for (i <- 0 to ni.length-1) {
        s += ni(i) * getNum(i)
    }
    if (s == n) s else thirt(s)
  }
}

// times out every time 
object Thirteen {
import scala.annotation.tailrec

  @tailrec
  def thirt(n: Long): Long = {
    val getNum = (n: Int) => Array(1, 10, 9, 12, 3, 4)(n % 6)
    val ni  = n.toString.split("").map(_.toInt)
    var s: Long = 0
    for (i <- ni.length-1 to 0 by -1) {
        s = s + ni(i) * getNum(i)
    }
    if (s == n) s else thirt(s)
  }
}

I ask the following questions:

  1. Is there an obvious rule I am unaware of?
  2. What is an easy way to test two code versions for performance – reliably measuring performance in the JVM appears difficult.
  3. Does it help to look at the underlying byte code?
  4. Is there a better piece of code solving the same problem, If so, I'd be very grateful to see it.

Whilst I've seen similar questions, I can't find a definitive answer.

5
  • I don't know if this would be any faster, but the code would be cleaner: val s :Long = ni.indices.foldLeft(0L){case (acc,x) => acc + ni(x)*getNum(x)}
    – jwvh
    Commented Oct 20, 2018 at 10:05
  • I agree, much cleaner and runs successfully. Thank you.
    – Fred
    Commented Oct 20, 2018 at 10:34
  • The best tool that I'm aware of for benchmarking Scala code performance (in terms of CPU and memory overhead) is ScalaMeter. It allows warm-up periods before collecting data (to account for JIT performance improvements) and discarding of results due to GC cycles, etc.
    – Mike Allen
    Commented Oct 20, 2018 at 16:18
  • When I run your code on 130, I see i bouncing forever at 0 and 1. With another println, it is recursing on 13 and 31. So it's the algorithm, not the control structure or the Range.
    – som-snytt
    Commented Oct 20, 2018 at 18:02
  • I see the problem - a descending index is not enough. Many thanks for pointing that out, som-snytt.
    – Fred
    Commented Oct 20, 2018 at 19:14

1 Answer 1

1

Here's how I'd be tempted to tackle it.

val nums :Stream[Int] = 1 #:: 10 #:: 9 #:: 12 #:: 3 #:: 4 #:: nums

def thirt(n :Long) :Long = {
  val s :Long = Stream.iterate(n)(_ / 10)
                      .takeWhile(_ > 0)
                      .zip(nums)
                      .foldLeft(0L){case (sum, (i, num)) => sum + i%10 * num}
  if (s == n) s else thirt(s)
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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