Search

Categories

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Send mail to the author(s) E-mail

# Monday, February 08, 2010
Prime Number Refactoring
( Clean Code by Uncle Bob )

From Uncle Bobs book clean code example on refactoring:

    {
        static void Main()
        {
            int[] result = GeneratePrimes.generatePrimes(30);
            foreach (var i in result)
                Console.Write(i.ToString() + ", ");
        }
    }
 
    /// <summary>
    /// Given an array of integers starting at 2, cross out the multiples of 2.  Fine the next
    /// uncrossed integer, and cross out all of its multiples.
    /// Repeat until you have passed the square root of the maximum value
    /// </summary>
    public class GeneratePrimes
    {
class Program
        public static int[] generatePrimes(int maxValue)
        {
            if (maxValue >= 2) // the only valid case
            {
                // declarations
                int s = maxValue + 1; // size of the array
                bool[] f = new bool[s];
                int i;
 
                // initialize array to be true
                for (i = 0; i < s; i++)
                {
                    f[i] = true;
                }
 
                // get rid of non-primes
                f[0] = f[1] = false;
 
                //sieve
                int j;
                for (i = 2; i < Math.Sqrt(s) + 1; i++)
                {
                    if (f[i]) // if i is uncrossed, cross its multiples
                    {
                        for (j = 2 * i; j < s; j += i)
                            f[j] = false; // multiple is not a prime
                    }
                }
 
                // how many primes are there?
                int count = 0;
                for (i = 0; i < s; i++)
                {
                    if (f[i])
                        count++; // bump count
                }
 
                int[] primes = new int[count];
 
                //move the primes into the result
                for (i = 0, j=0;i<s ; i++)
                {
                    if (f[i])
                        primes[j++] = i;
                }
 
                return primes; // return the primes
            } else // maxvalue < 2
                return new int[0]; // return null array if bad input
        }
    }

This is messy code because:

  • Variable names are cryptic
  • Some comments are unnecessary

Here is Bob’s refactored version:

/// <summary>
    /// Generates prime number up to a user specified maximum
    /// The algorithm used is the Sieve of Eratosthenes.
    /// Given an array of integers starting at 2:
    /// Find the first uncrossed (eg 3 ) integer, and cross out all its multiples (eg 6,9,12,14)
    /// Repeat until there are no more multipes in the array
    /// </summary>
    class PrimeGenerator
    {
        static bool[] crossedOut;
        static int[] result;
 
        public static int[] generatePrimes(int maxValue)
        {
            if (maxValue < 2)
                return new int[0];
            else
            {
                uncrossIntegersUpTo(maxValue);
                crossOutMultiples();
                putUncrossedIntegersIntoResult();
                return result;
            }
        }
 
        static void uncrossIntegersUpTo(int maxValue)
        {
            crossedOut = new bool[maxValue + 1]; // as bool array starts at 0, and if maxvalue = 10, we need an array of length 11
            for (int i = 2; i < crossedOut.Length; i++) // less than as we don't want to reference crossedOut[4] which doesn't exist
                crossedOut[i] = false;
        }
 
        static void crossOutMultiples()
        {
            int limit = determineIterationLimit();
            for (int i = 2; i <= limit; i++)
                if (notCrossed(i))
                    crossOutMultiplesOf(i);
        }
 
        static int determineIterationLimit()
        {
            // Every multiple in the array has a prime factor that
            // is less than or equal to the square root of the array size, 
            // which is the largest number we are trying to find primes in.
            // So we don't have to cross out numbers
            // larger than that square root of the maxnumber, as they will have been crossed out already
            double iterationLimit = Math.Sqrt(crossedOut.Length);
            return (int) iterationLimit;
        }
 
        static void crossOutMultiplesOf(int i)
        {
            for (int multiple = 2 * i; multiple < crossedOut.Length; multiple += i)
                crossedOut[multiple] = true;
        }
 
        static bool notCrossed(int i)
        {
            return crossedOut[i] == false;
        }
 
        static void putUncrossedIntegersIntoResult()
        {
            result = new int[numberOfUncrossedIntegers()];
            for (int j = 0, i = 2; i < crossedOut.Length; i++)
                if (notCrossed(i))
                    result[j++] = i;
        }
 
        static int numberOfUncrossedIntegers()
        {
            int count = 0;
            for (int i = 2; i < crossedOut.Length; i++)
                if (notCrossed(i))
                    count++;
            return count;
        }
    }

I like Bobs version because it splits the code into simple manageable chunks eg:

    uncrossIntegersUpTo(maxValue);
    crossOutMultiples();
    putUncrossedIntegersIntoResult();

I paired with a friend over the weekend, and we thought this was better:

  • Initialised crossedOut in generatePrimes method instead of ‘child’ method
  • Pass in crossedOut as a parameter instead of a class scope variable
  • Took out (defactored), the notCrossed(i) method as !crossedOut[i] is very readable inline.
  • Make everything non static
  • Keep in /// summary method so intellisense works in the IDE – am trialling Ghostdoc.
/// <summary>
    /// Generates prime number up to a user specified maximum
    /// The algorithm used is the Sieve of Eratosthenes.
    /// Given an array of integers starting at 2:
    /// Find the first uncrossed (eg 3 ) integer, and cross out all its multiples (eg 6,9,12,14)
    /// Repeat until there are no more multipes in the array
    /// </summary>
    class PrimeGenerator
    {
        public int[] generatePrimes(int maxValue)
        {
            bool[] crossedOut;
 
            if (maxValue < 2)
                return new int[0];
            else
            {
                crossedOut = new bool[maxValue + 1];
                uncrossIntegersUpTo(crossedOut);
                crossOutMultiples(crossedOut);
                return putUncrossedIntegersIntoResult(crossedOut);
            }
        }
 
        void uncrossIntegersUpTo(bool[] crossedOut)
        {
            // as bool array starts at 0, and if maxvalue = 10, we need an array of length 11
            for (int i = 2; i < crossedOut.Length; i++) // less than as we don't want to reference crossedOut[4] which doesn't exist
                crossedOut[i] = false;
        }
 
        void crossOutMultiples(bool[] crossedOut)
        {
            int limit = determineIterationLimit(crossedOut);
            for (int i = 2; i <= limit; i++)
                if (!crossedOut[i])
                    crossOutMultiplesOf(crossedOut, i);
        }
 
        int determineIterationLimit(bool[] crossedOut)
        {
            // Every multiple in the array has a prime factor that
            // is less than or equal to the square root of the array size, 
            // which is the largest number we are trying to find primes in.
            // So we don't have to cross out numbers
            // larger than that square root of the maxnumber, as they will have been crossed out already
            double iterationLimit = Math.Sqrt(crossedOut.Length);
            return (int) iterationLimit;
        }
 
        void crossOutMultiplesOf(bool[] crossedOut, int i)
        {
            for (int multiple = 2*i; multiple < crossedOut.Length; multiple += i)
                crossedOut[multiple] = true;
        }
 
        int[] putUncrossedIntegersIntoResult(bool[] crossedOut)
        {
            int[] result = new int[numberOfUncrossedIntegers(crossedOut)];
            for (int j = 0, i = 2; i < crossedOut.Length; i++)
                if (!crossedOut[i])
                    result[j++] = i;
            return result;
        }
 
        int numberOfUncrossedIntegers(bool[] crossedOut)
        {
            int count = 0;
            for (int i = 2; i < crossedOut.Length; i++)
                if (!crossedOut[i])
                    count++;
            return count;
        }
    }
Comments [0] | | # 
Related posts:
Clean Code by Uncle Bob
All comments require the approval of the site owner before being displayed.
Name
E-mail
Home page

Comment (Some html is allowed: a@href@title, strike) where the @ means "attribute." For example, you can use <a href="" title=""> or <blockquote cite="Scott">.  

Enter the code shown (prevents robots):
Live Comment Preview