Scala函数式求解Project Euler第25题内存溢出问题排查

问题描述 #

在Project Euler平台练习Scala编程时，求解第25题（求斐波那契数列中第一个包含1000位数字的项对应的索引）过程中程序触发java.lang.OutOfMemoryError异常卡住，要求在保持纯函数式实现风格的前提下，给出可行的内存优化方案。

初始问题代码 #

最初的纯函数式实现如下，运行时直接抛出内存溢出错误：

def fibonacciIndex(numOfDigits: Int): Option[Int] = {
  lazy val fibs: LazyList[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
  fibs.find(_.toString.length == numOfDigits)
}

问题根因 #

排查确认内存溢出的核心诱因不是LazyList本身的内存机制问题，而是**Int类型数值溢出**：

• Int类型的最大表示范围为2^31-1（仅10位十进制数），远小于题目要求的1000位数字量级
• 斐波那契数增长到超出Int范围后会触发数值溢出，变为不符合预期的负数，永远无法匹配到长度为1000位的目标值
• 匹配逻辑永远不命中导致LazyList无限生成元素，最终耗尽堆内存抛出OOM异常

修复后正确实现 #

将数值类型替换为支持任意精度的BigInt即可解决问题，全程保留纯函数式的惰性实现风格，内存占用稳定：

def fibonacciIndex(numOfDigits: Int): Int = {
    lazy val bigFibs: LazyList[BigInt] = BigInt(0) #:: bigFibs.scanLeft(BigInt(1))(_ + _)
    bigFibs.indexWhere(_.toString.length == numOfDigits)
}

修复点说明：

• 用BigInt替换Int存储斐波那契数，从根源避免大整数运算的溢出问题
• 用indexWhere直接返回匹配项的索引，更贴合题目求索引值的需求
• 保留LazyList惰性求值特性，仅生成遍历到目标项之前的数列元素，无额外内存浪费

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