C# Language Exemple d'évaluation paresseuse: numéros de Fibonacci


Exemple

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics; // also add reference to System.Numberics

namespace ConsoleApplication33
{
    class Program
    {
        private static IEnumerable<BigInteger> Fibonacci()
        {
            BigInteger prev = 0;
            BigInteger current = 1;
            while (true)
            {
                yield return current;
                var next = prev + current;
                prev = current;
                current = next;
            }
        }

        static void Main()
        {
            // print Fibonacci numbers from 10001 to 10010
            var numbers = Fibonacci().Skip(10000).Take(10).ToArray();
            Console.WriteLine(string.Join(Environment.NewLine, numbers));
        }
    }
}

Comment ça marche sous le capot (je recommande de décompiler le fichier .exe résultant dans l'outil IL Disaambler):

  1. Le compilateur C # génère une classe implémentant IEnumerable<BigInteger> et IEnumerator<BigInteger> ( <Fibonacci>d__0 dans ildasm).
  2. Cette classe implémente une machine à états. L'état se compose de la position actuelle dans la méthode et des valeurs des variables locales.
  3. Le code le plus intéressant se trouve dans la méthode bool IEnumerator.MoveNext() . Fondamentalement, ce que MoveNext() fait:
    • Restaure l'état actuel. Les variables comme prev et current deviennent des champs dans notre classe ( <current>5__2 et <prev>5__1 in ildasm). Dans notre méthode, nous avons deux positions ( <>1__state ): la première à l'accolade ouvrante, la deuxième à la yield return .
    • Exécute le code jusqu'au prochain yield return yield break ou yield break / } .
    • Pour les yield return valeur résultante est enregistrée, ainsi la propriété Current peut la renvoyer. true est retourné. À ce stade, l'état actuel est à nouveau enregistré pour la prochaine invocation MoveNext .
    • Pour la méthode yield break / } méthode renvoie simplement false ce qui signifie que l'itération est effectuée.

Notez également que ce nombre 10001 est long de 468 octets. La machine d'état enregistre uniquement current variables current et prev tant que champs. Alors que si vous souhaitez enregistrer tous les nombres dans la séquence du premier au dixième, la taille de la mémoire consommée sera supérieure à 4 mégaoctets. L'évaluation paresseuse, si elle est utilisée correctement, peut réduire l'encombrement de la mémoire dans certains cas.