为什么超出内存限制？ C＃

Question

任务是：

Tribonacci 序列是一个序列，其中每个下一个元素都由序列中前三个元素的总和组成。
如果给定序列的前三个元素和数字 N，请编写一个计算机程序来查找 Tribonacci 序列的第 N 个元素。
我已将约束包含在程序中。本题为系统提交，有时间限制。我在最后 2 个案例中遇到了超出内存限制的情况。

请帮忙。

        BigInteger a = BigInteger.Parse(Console.ReadLine());
        BigInteger b = BigInteger.Parse(Console.ReadLine());
        BigInteger c = BigInteger.Parse(Console.ReadLine());

        var fibonacciNumbers = new List<BigInteger> { a, b, c };
        BigInteger N = BigInteger.Parse(Console.ReadLine());    
        if ((a < -2000000000) || (b < -2000000000) || (c < -2000000000) || (a > 2000000000) || (b > 2000000000) || (c > 2000000000) || (N > 15000) || (N < 1))
        {
            throw new Exception("Argument out of range");
        }

        while (fibonacciNumbers.Count <= N)
        {
            var previous = fibonacciNumbers[fibonacciNumbers.Count - 1];
            var previous2 = fibonacciNumbers[fibonacciNumbers.Count - 2];
            var previous3 = fibonacciNumbers[fibonacciNumbers.Count - 3];
            fibonacciNumbers.Add(previous + previous2 + previous3);
        }

        Console.WriteLine((fibonacciNumbers[(int)N - 1]));

Answer 1

如果我们假设您需要在列表中存储以前的斐波那契结果（如果有任何目的）？

使用默认配置，即使在 64 位上，CLR 对象的最大大小也是 2GB。

您正在将斐波那契结果存储在 List 中，这会占用内存。你得到 OutOfMemoryException 当你达到 2GB

您需要超过 2GB 的限制。为此，您需要将 gcAllowVeryLargeObjects 添加到 app.config

<runtime>
  <gcAllowVeryLargeObjects enabled="true" />
</runtime>

另一方面，如果您不需要斐波那契数列的所有先前值，那么

    BigInteger f2 = BigInteger.Parse(Console.ReadLine());
    BigInteger f1 = BigInteger.Parse(Console.ReadLine());
    BigInteger f = BigInteger.Parse(Console.ReadLine());

    BigInteger N = BigInteger.Parse(Console.ReadLine());    
    if ((a < -2000000000) || (b < -2000000000) || (c < -2000000000) || (a > 2000000000) || (b > 2000000000) || (c > 2000000000) || (N > 15000) || (N < 1))
    {
        throw new Exception("Argument out of range");
    }

    while (fibonacciNumbers.Count <= N)
    {
        var fn = f2 + f1 + f;

        f2 = f1;
        f1 = f;
        f = fn;
    }

    Console.WriteLine(fn);

Answer 2

您不能存储所有先前的序列值，因为您只需要存储最后 3 个数字即可计算下一个。

BigInteger prevPrev = BigInteger.Parse(Console.ReadLine());
BigInteger prev = BigInteger.Parse(Console.ReadLine());
BigInteger current = BigInteger.Parse(Console.ReadLine());

BigInteger N = BigInteger.Parse(Console.ReadLine());

for(int i = 3; i < N; i++)
{
    // calculate next number
    var next = prevPrev + prev + current;

    // shift all numbers
    prevPrev = prev;
    prev = current;
    current = next;
}

return current;

Answer 3

您的代码中有些地方需要注意：

为什么要将所有前面的数字存储到一个数组中。正如@Vadim Martynov 已经提到的，您只需要前三个数字（不是斐波那契）。
您使用 BigInteger 来存储计数。它可能应该适合一个 32 位有符号整数，因为它已经超过 20 亿次迭代。对于 BigInteger 结构，这将占用太多内存。在你当前的程序结束时，你已经转换回 int，所以这里没有使用 BigInteger。

如果你确实想将所有项目存储在一个列表中（不要问我为什么），那么请将列表预先分配到正确的数字（你事先知道）并使用数组，所以您将获得更高效的存储，无需重新分配和复制。

    var a = BigInteger.Parse(Console.ReadLine());
    var b = BigInteger.Parse(Console.ReadLine());
    var c = BigInteger.Parse(Console.ReadLine());

    var N = int.Parse(Console.ReadLine());
    if ((a < -2000000000) || (b < -2000000000) || (c < -2000000000) || (a > 2000000000) || (b > 2000000000) || (c > 2000000000) || (N > 15000) || (N < 1))
        throw new Exception("Argument out of range");

    var fibonacciNumbers = new BigInteger[N];
    fibonacciNumbers[0] = a;
    fibonacciNumbers[1] = b;
    fibonacciNumbers[2] = c;

    for (var i=3; i < N; ++i)
    {
        var previous = fibonacciNumbers[i - 1];
        var previous2 = fibonacciNumbers[i - 2];
        var previous3 = fibonacciNumbers[i - 3];
        fibonacciNumbers[i] = previous + previous2 + previous3;
    }

    Console.WriteLine(fibonacciNumbers[N - 1]);

但最好不要将这些项目存储在 array/list 中。我只是想评论其他问题，但请使用@Vadim Martynov 的回答。

为什么超出内存限制？ C＃

Why do I have memory limit exceeded ? C#

c#

memory

limit

fibonacci