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] | | # 
Clean Code by Uncle Bob
( Clean Code by Uncle Bob )

image

http://www.amazon.com/Clean-Code-Handbook-Software-Craftsmanship/dp/0132350882

My notes below on Bobs book.. also need next article on refactoring PrimeNumber code.

We need 'Clean Code' because otherwise it can bring a company to its knees
As messy code builds up, productivity decreases

What is clean code?
Elegant, Efficient, Does one thing well, Simple, crisp abstractions, Has Unit Tests, Meaningful Names, minimal dependencies, Clear, no duplication, minimal number of entities, What you expect, beautiful

Make code easy to read

Boy Scout Rule:  Leave the campground cleaner than you found it... same for code.. leave it cleaner than you found it

Dave's Simplest Refactoring List
** change one variable name for the better
** break up a function thats a bit too large
** eliminate one small bit of duplication
** clean up a composite if statement

SRP - Single Responsibility Principle
OCP - Open Closed Principle
L
I
DIP - Dependency Inversion Principle

DRY - Don't repeat yourself

2. Meaningful Names

intention revealing names
// this is bad!
int d; // elapsed time in days

**// better....What is being measured, and the units
int elapsedTimeInDays;

see c:\development\ch2 Intentional Names.
and ch2 Statistics Message


**Class names - nouns (things), or noun phrases eg PrimeGenerator, WikiPage, Customer, Account, AddressParser.... not a verb (doing) eg manager, data, info

**Method names - verb or very phrases eg GeneratePrimes, postPayment, deletePage

3. Functions

**First rule:  they should be small
Second rule: they should be smaller than that!

Do one thing!

** shrink function down.. so one level of abstration per function

TO test..
TO RenderPageWithSetupsAndTeardown, we check to see whether the page is a test page and if so, we include the setups and teardown.  In either case we render the page in HTML.

One level of abstraction per function.

4. Comments

Comments are to compensate for our failure to express ourselves in code

eg
// Check to see if the employee is eligible for full benefits
if ((employee.flag && HOURLY_FLAG) && (employee.age > 65))

or
if (employee.isEligibleForFullBenefits())

Dont comment out code :-)

ch4Primes - great to understand at a higher level of abstraction

5. Formatting
important

6. Objects and Data Abstraction

A class does not push its variables out through getters and setters
Rather it exposes abstract interfaces that allow its users to manipulate the essence of the data,
without having to know its implementation.

** am here.. would be good to type in the code again looking at procedural stuff from page 96.
Objects expose behaviour and hide data.
Data Structures expose data and have no significant behaviour.

DTO's - public variables and no functions
Active Records are special forms of DTO's...with public variables... and naviagtaional methods like save and find.

7. Error Handling

8. Boundaries

9. Unit Tests
Very important to keep clean

10. Classes
SRP
Good prime generator example
Open Closed principle

11. Systems
Seperation of main
Factories
Dependency Injection

12. Emergent Design

13. Concurrency

14. Successive Refinement - Case Study - command line parser

15. JUnit internals - Case study (smaller)

16. Refactoring SerialDate

17. Smells and Heuristics
Comments
Environment
Functions
General
Java
Names

Comments [0] | | #