2
votes

Pourquoi la limite de mémoire est-elle dépassée? C #

La tâche est:

La séquence Tribonacci est une séquence dans laquelle chaque élément suivant est constitué par la somme des trois éléments précédents de la séquence.
Écris un programme informatique qui trouve le Nième élément de la séquence Tribonacci, si on vous donne les trois premiers éléments de la séquence et le nombre N.
J'ai inclus les contraintes dans le programme. Ce problème est soumis dans un système et il y a une limite de temps. J'ai atteint la limite de mémoire dépassée sur les 2 derniers cas.

Veuillez aider.

        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]));

c# memory fibonacci limit

2 commentaires

Ouais, bien sûr, vous atteignez une limite de mémoire si vous avez une liste avec autant d'éléments. Ces éléments doivent occuper un peu de RAM, n'est-ce pas? Cela m'amène à la question: pour quelle raison avez-vous cette liste? Quel est son objectif? Vous pouvez réaliser votre algorithme sans cette liste (ou avec une liste assez petite). Pensez-y un peu ...

Je voulais pratiquer les listes, c'est pourquoi je l'ai trop compliqué. J'ai réalisé que si j'utilise simplement les 3 variables dont j'ai besoin au lieu de les remplir quelque part, je vais économiser beaucoup de mémoire lorsque je travaille avec beaucoup de nombres. Merci!

3 Réponses :

2
votes

SI nous supposons que vous devez stocker les résultats de Fibonacci précédents dans la liste (s'il y a un but)?

Avec la configuration par défaut, la taille maximale d'un objet CLR est de 2 Go même sur 64 bits.

vous stockez les résultats de fibonacci dans List qui occupe la mémoire. vous obtenez OutOfMemoryException lorsque vous atteignez 2 Go

Vous devez dépasser la limite de 2 Go. Pour cela, vous devez ajouter gcAllowVeryLargeObjects dans app.config

    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);

D'autre part si vous ne pas besoin de toutes les valeurs précédentes de la séquence fibonacci, alors

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

0 commentaires

1
votes

Vous ne devez pas stocker toutes les valeurs de séquence précédentes car il vous suffit de stocker les 3 derniers nombres pour calculer le suivant.

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;

0 commentaires

1
votes

Il y a certaines choses dans votre code qui nécessitent une attention:

Pourquoi stockeriez-vous tous les nombres précédents dans un tableau. Comme @Vadim Martynov l'a déjà mentionné, vous n'aurez besoin que des trois numéros précédents (ce qui n'est pas Fibonacci).
Vous utilisez un BigInteger pour stocker le décompte. Il devrait probablement correspondre à un entier signé de 32 bits, car ce serait déjà plus de 2 milliards d'itérations. Avec les structures BigInteger , cela prendra déjà trop de mémoire. À la fin de votre programme actuel, vous avez déjà casté vers int , il n'y a donc pas d'utilisation de BigInteger ici.

Si vous souhaitez stocker tous les éléments dans une liste (ne me demandez pas pourquoi), veuillez pré-allouer la liste au bon numéro (vous le savez à l'avance) et utiliser un tableau , vous obtenez ainsi un stockage beaucoup plus efficace qui n'a pas besoin de réallouer et de copier.

    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]);

Mais il est préférable de ne pas stocker ces éléments dans un tableau / une liste de toute façon . Je voulais juste commenter les autres problèmes, mais veuillez utiliser la réponse de @Vadim Martynov.

0 commentaires