Friday, December 31, 2010

Lazy-loading fibonacci

Let's start the next year by becoming a lazy person, in a Dilbert-kind-of-way. Less lines of code, lean code, less to debug.



For a start, here's your friendly neighborhood yield return in action (Fibonacci using IEnumerable):

using System;
using System.Collections.Generic;

using System.Linq;

namespace Fibonacci
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Console.WriteLine("Sans list. Lazy load stuff:");
            int i = 0;
            
            
            foreach(int n in Fibonacci().Take(10))
            {
                ++i;
                Console.WriteLine("Loading {0} {1}", i, n);             
            }
            
            
            Console.WriteLine("\nPick the 20th fibonacci:");
            Console.WriteLine("\n20th fibonacci: {0}", Fibonacci().Skip(20 - 1).Take(1).Single());
            
            
            Console.WriteLine("\nEagerly load everything in list:");
            i = 0;      
            foreach(int n in Fibonacci().Take(10).ToList())
            {
                ++i;
                Console.Write("\nEager loading {0} {1}", i, n);
            }
                    
        }
        

                        
        static IEnumerable<int> Fibonacci()
        {
            int a = 0,  b = 1;
                        
            for(;;)
            {
                Console.Write("Lazy");         
                yield return a;
             
                int n = a;
                a += b;
                b = n;          
            }                           
        }
    }//class
        
}


Contrast that to an old way, a lot of boilerplate code is needed (which maybe favorable to a PHB) :

using System;

namespace Fib2
{
    using System.Linq;
    using FibLib;

    class MainClass
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Sans list. Lazy load stuff:");
            int i = 0;

            var f = new Fibonacci();

            foreach (int n in f.Take(10))
            {
                ++i;
                Console.WriteLine("Loading {0} {1}", i, n);
            }


            Console.WriteLine("\nPick the 20th fibonacci:");
            Console.WriteLine("\n20th fibonacci: {0}", f.Skip(20 - 1).Take(1).Single());


            Console.WriteLine("\nEagerly load everything in list:");
            i = 0;
            foreach (int n in f.Take(10).ToList())
            {
                ++i;
                Console.Write("\nEager loading {0} {1}", i, n);
            }

        }
    }


}

namespace FibLib
{    
    class Fibonacci : System.Collections.Generic.IEnumerable<int>
    {
        System.Collections.Generic.IEnumerator<int> _f = new FibonacciIterator();
        // implement IEnumerable<int>...
        System.Collections.Generic.IEnumerator<int> System.Collections.Generic.IEnumerable<int>.GetEnumerator()
        {
            _f.Reset();
            return _f;
        }


        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new Exception("This doesn't get executed. What's the use?");
            return _f;
        }


        // ...implement IEnumerable



        class FibonacciIterator : System.Collections.Generic.IEnumerator<int>
        {
            int a = 0, b = 1;

            int System.Collections.Generic.IEnumerator<int>.Current
            {
                get
                {
                    return b;
                }
            }

            object System.Collections.IEnumerator.Current
            {
                get
                {
                    throw new Exception("This doesn't get executed. What's the use?");
                    return b;
                }
            }

            void System.IDisposable.Dispose() { }


            bool System.Collections.IEnumerator.MoveNext()
            {
                Console.Write("Lazy");
                int n = a;
                a += b;
                b = n;
                return true;
            }

            void System.Collections.IEnumerator.Reset()
            {
                a = 0;
                b = 1;
            }

        }

    }//class Fibonacci
}


Code A has 55 lines of code, while code B has 108 lines

yield return saves the day! :-)

Output of both approach:

Sans list. Lazy load stuff:
LazyLoading 1 0
LazyLoading 2 1
LazyLoading 3 1
LazyLoading 4 2
LazyLoading 5 3
LazyLoading 6 5
LazyLoading 7 8
LazyLoading 8 13
LazyLoading 9 21
LazyLoading 10 34

Pick the 20th fibonacci:
LazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazyLazy
20th fibonacci: 4181

Eagerly load everything in list:
LazyLazyLazyLazyLazyLazyLazyLazyLazyLazy
Eager loading 1 0
Eager loading 2 1
Eager loading 3 1
Eager loading 4 2
Eager loading 5 3
Eager loading 6 5
Eager loading 7 8
Eager loading 8 13
Eager loading 9 21
Eager loading 10 34

This is the SQL and eager-loading approach: http://www.ienablemuch.com/2010/09/fibonacci-using-sql.html

No comments:

Post a Comment