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;

using System.Collections.Generic;


using System.Linq;


namespace Fib2
{
    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);
            }

        }
    }
    
    
    class Fibonacci : IEnumerable<int>
    {
        FibonacciIterator _f = new FibonacciIterator();
        // implement IEnumerable...
        public IEnumerator<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 : IEnumerator<int>
        {
            int a = 0, b = 1;
        
            
            public bool MoveNext()
            {
                Console.Write("Lazy");
                int n = a;
                a += b;
                b = n;
                return true;
            }
            
            public void Reset()
            {
                a = 0; 
                b = 1;
            }
            
            public int Current
            {
                get
                {
                    return b;
                }
            }
            
                        
            void IDisposable.Dispose() { }
        
            
            object System.Collections.IEnumerator.Current {
                get 
                {
                    throw new Exception("This doesn't get executed. What's the use?");
                    return b;
                }
            }
             
        }

    }//class Fibonacci
}


Code A has 56 lines of code, while code B has 106 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