生成斐波那契数列时遭遇Java堆内存溢出问题的解决方案咨询

运行代码时出现以下错误：

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

尝试将斐波那契数存入List用于后续处理，初始代码如下：

int a;
int b = 0;
int c = 1;

int prod = 2932589879121
    

List<Integer> list = new ArrayList<>();
for (int i = 0; i < prod; i++) {
    a = b;
    b = c;
    c = a + b;
    list.add(c);
}

完整实现代码如下，需求是判断连续两个斐波那契数的乘积是否等于指定值prod，小数值时逻辑正常，但大数值下触发内存溢出：

public static long[] productFib(long prod) {
    long[] result = new long[3];

    int a;
    int b = 0;
    int c = 1;

    int first = 0;
    int second = 0;

    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < prod; i++) {
        a = b;
        b = c;
        c = a + b;
        list.add(c);
    }

    int index = 0;
    while (true) {
        first = list.get(index);
        second = list.get(index + 1);
        if (first * second == prod) {
            result[0] = list.get(index);
            result[1] = list.get(index + 1);
            result[2] = 1;
            break;
        } else if (first * second > prod) {
            result[0] = list.get(index);
            result[1] = list.get(index + 1);
            result[2] = 0;
            break;
        }
        index++;
    }

    return result;
}

修改后的可正常运行代码：

public static long[] productFib(long prod) {
    long[] result = new long[3];

    long a;
    long b = 0;
    long c = 1;

    for (int i = 0; i < prod; i++) {
        a = b;
        b = c;
        c = a + b;
        if (a * b == prod) {
            result[0] = a;
            result[1] = b;
            result[2] = 1;
            break;
        } else if (a * b > prod) {
            result[0] = a;
            result[1] = b;
            result[2] = 0;
            break;
        }
    }

    return result;
}

修复关键点 #

• 移除冗余的List存储：原代码将所有生成的斐波那契数存入List，当prod极大时，List会存储天文数字级的元素，直接耗尽堆内存。实际上只需在生成过程中判断连续两个数的乘积，不需要保存所有历史值。
• 升级数据类型为long：原代码用int存储斐波那契数，数值增长后会快速触发整数溢出，导致计算错误。long的取值范围更大，能适配更大的斐波那契数。
• 提前终止循环：原循环需执行接近prod次，而斐波那契数呈指数增长，乘积会迅速超过prod。修改后每次生成数值就判断，符合条件立即终止循环，大幅减少执行次数。

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