如何在 scala 中为 collat​​z 链改进我的 tailrec 函数的执行时间

Question

 def collatzChainLength(n:Int):Int={
      @tailrec
      def collatz(n:Int,acc:Int):Int=
         if(n==1) acc+1
         else if (n%2==0) collatz(n/2,acc+1)
         else collatz(3*n+1,acc+1)
      collatz(n,0)
   }

我得到了 100000 次迭代的几乎即时结果，但之后它会取无穷大

 println( (1 to 100000).map(x=> 
(x,collatzChainLength(x))).foldLeft((0,0))((m,y)=>{ 
if(y._2>m._2) y else m}))
 println( (100001 to 200000).map(x=> 
(x,collatzChainLength(x))).foldLeft((0,0))((m,y)=>{ 
if(y._2>m._2) y else m}))

Answer 1

你最好对偶数进行尾递归缩减，因为奇数情况给出偶数。 （否定 if）

或者：

  else collatz((3*n + 1)/2, acc +2)

但实际的解决方案是在最后进行一次调用。

  if (n == 1) acc + 1
  else collatz(n & 1 == 0? n/2 : 3*n + 1, acc + 1)

达到 2³¹.

的三分之一时也使用 Long

Answer 2

虽然您可以进行一些小的改进，但真正的问题是您的 Int 值溢出了。尽管 200000 是一个舒适的 Int 值，但请记住 n 在多次迭代过程中可以增长也可以收缩。

进行此更改...

def collatzChainLength(n: Long): Int = { 

...以及所有用于协调编译器的小模块，您可以开始了。