Scala懒加载动态规划斐波那契实现的技术问询

1. 自定义Lazy类的核心作用 #

你写的Lazy类其实是对Scala原生lazy val的轻量封装：

• 构造时接收的expr: => T是传名参数，意味着这段逻辑不会立即执行，只有首次访问value时才会触发计算。
• apply()方法是个语法糖，让你可以用lazyInstance()代替lazyInstance.value，调用更简洁。
• 它的核心价值是把「延迟计算逻辑」包装成一个可存储的实例，这样就能把这些实例放进数组里，实现动态规划所需的懒加载缓存。

2. fib(5)的完整运行逻辑 #

当你调用fib(5)时，执行流程是这样的：

1. 进入fib函数，先定义内部函数doFib：它返回一个Lazy[Int]，逻辑是如果i <= 2直接返回1（对应斐波那契前两项），否则依赖fibs(i-1)和fibs(i-2)的计算结果。
2. 定义lazy val fibs：这是一个长度为5的数组，元素是doFib(0)到doFib(4)的Lazy[Int]实例。注意fibs是懒加载的，只有首次被访问时才会初始化数组。
3. 触发计算：调用doFib(5).value
   • 因为5 > 2，需要计算fibs(4)() + fibs(3)()，这时候首次访问fibs，数组开始初始化。
   • 计算fibs(4)()：触发doFib(4)的value计算，需要fibs(3)() + fibs(2)()。
   • 计算fibs(3)()：触发doFib(3)的value计算，需要fibs(2)() + fibs(1)()。
   • 计算fibs(2)()：i=2 <=2，直接返回1，结果被缓存。
   • 计算fibs(1)()：i=1 <=2，直接返回1，结果被缓存。
   • 此时fibs(3).value = 1 + 1 = 2，缓存起来。
   • 计算fibs(2)()：直接取缓存的1。
   • 此时fibs(4).value = 2 + 1 = 3，缓存起来。
   • 计算fibs(3)()：直接取缓存的2。
   • 最终doFib(5).value = 3 + 2 = 5，这就是fib(5)的返回结果。

3. 常见技术问题解答 #

• 为什么不用Scala原生lazy val直接存数组？
  Scala的数组元素不能直接是lazy val——lazy val是变量修饰符，不是可实例化的类型。你需要一个封装类（也就是你写的Lazy）把延迟计算逻辑包装成对象，才能放进数组统一管理。
• 这个实现的优势是什么？
  它是典型的懒加载动态规划：每个斐波那契数只会被计算一次，结果被Lazy类的lazy val value缓存，彻底避免了普通递归中重复计算的问题（比如普通递归fib(5)会重复计算fib(3)两次）。
• 索引对应关系正确吗？
  完全正确：你的fib(n)返回的就是斐波那契数列的第n项（前两项为1,1），比如fib(3)=2、fib(4)=3、fib(5)=5，符合预期。

最终运行结果 #

调用fib(5)的输出结果为 5。

内容的提问来源于stack exchange，提问作者kkspeed