The motivation for this entry is based on chapter 5 of the book Agile Software Development Principles, Patterns and Practices by **Robert Martin**. In that chapter the author writes an initial program with correct output. The issue is that it is not as simple to follow (and possibly maintain) as the final one. The final one is longer but much easier to follow.

I was not able to find the source code in the URL specified by the book: **www.objectmentor.com/PPP** (the domain is up for grabs). I wanted to determine if the performance would be different (better) for the short program when compared against the longer one, which also outputs the same results.

Following is the **initial** **slightly** modified program that generates prime numbers:

package com.john.canessa.primes; import java.util.Scanner; public class Solution { /* * test class */ public static void main(String[] args) { int[] primes = null; long begin = 0; long end = 0; long average = 0; long duration = 0; int loops = 10; // **** **** Scanner sc = new Scanner(System.in); System.out.print("main >>> maxValue: "); int maxValue = sc.nextInt(); sc.close(); // **** **** for (int i = 0; i < loops; i++) { // **** **** begin = System.currentTimeMillis(); primes = GeneratePrimes.generatePrimes(maxValue); end = System.currentTimeMillis(); duration = end - begin; System.out.println("main <<< short duration: " + duration + " ms"); average += duration; // GeneratePrimes.show(primes); // **** **** begin = System.currentTimeMillis(); primes = PrimeGenerator.generatePrimes(maxValue); end = System.currentTimeMillis(); duration = end - begin; System.out.println("main <<< long duration: " + (end - begin) + " ms"); average += duration; // PrimeGenerator.show(primes); } // **** compute average time **** System.out.println("main <<< average: " + average / (loops * 2) + " ms"); } }

Following is the **final** **slightly** modified program that generates prime numbers:

package com.john.canessa.primes; public class PrimeGenerator { private static boolean[] crossedOut = null; private static int[] result = null; /* * generate primes */ public static int[] generatePrimes(int maxValue) { // **** **** if (maxValue < 2) { return new int[0]; } // **** **** uncrossIntegersUpTo(maxValue); crossOutMultiples(); putUncrossedIntegersIntoResult(); // **** **** return result; } /* * allocate and uncross integers up to the specified value */ private static void uncrossIntegersUpTo(int maxValue) { crossedOut = new boolean[maxValue + 1]; } /* * */ private static void crossOutMultiples() { int limit = determineIterationLimit(); for (int i = 2; i <= limit; i++) { if (notCrossed(i)) { crossOutMultiplesOf(i); } } } /* * */ private static int determineIterationLimit() { double iterationLimit = Math.sqrt(crossedOut.length); return (int)iterationLimit; } /* * */ private static void crossOutMultiplesOf(int i) { for (int multiple = 2 * i; multiple < crossedOut.length; multiple += i) { crossedOut[multiple] = true; } } /* * */ private static boolean notCrossed(int i) { return crossedOut[i] == false; } /* * */ private static void putUncrossedIntegersIntoResult() { result = new int[numberOfUncrossedIntegers()]; for (int j = 0, i = 2; i < crossedOut.length; i++) { if (notCrossed(i)) { result[j++] = i; } } } /* * count the number of uncrossed values */ private static int numberOfUncrossedIntegers() { int count = 0; for (int i = 2; i < crossedOut.length; i++) { if (notCrossed(i)) { count++; } } return count; } /* * show primes in array */ public static void show(int[] primes) { for (int i = 0; i < primes.length; i++) { System.out.printf("%6d ", primes[i]); if ((i != 0) && (((i + 1)% 10) == 0)) { System.out.println(); } } System.out.println(); } }

Following is the test program comparing the initial and final (and more complex) programs to generate the same set of primes (in our case the primes from 2 to 9,999,999):

package com.john.canessa.primes; public class GeneratePrimes { /* * generate prime numbers using a sieve. * * Sieve: an instrument with a meshed or perforated bottom, * used for separating coarse from fine parts of loose matter, * for straining liquids, etc., especially one with a circular * frame and fine meshes or perforations. */ public static int[] generatePrimes(int maxValue) { // **** not a prime **** if (maxValue < 2) { return new int[0]; } // **** declarations **** int s = maxValue + 1; // size of array boolean[] f = new boolean[s]; int i = 0; int[] primes = null; // **** initialize array to true **** for (i = 2; i < s; i++) { f[i] = true; } // **** sieve **** int j; for (i = 2; i < (Math.sqrt(s) + 1); i++) { // **** cross off its multiples (as needed) **** if (f[i]) { for (j = 2 * i; j < s; j += i) { // **** multiple is not a prime **** f[j] = false; } } } // **** count the number of primes **** int count = 0; for (i = 0; i < s; i++) { if (f[i]) { count++; } } // **** allocate an array for the prime numbers **** primes = new int[count]; // **** set the primes in the array **** for (i = 0, j = 0; i < s; i++) { if (f[i]) { primes[j++] = i; } } // **** return list of prime numbers **** return primes; } /* * show primes in array */ public static void show(int[] primes) { for (int i = 0; i < primes.length; i++) { System.out.printf("%6d ", primes[i]); if ((i != 0) && (((i + 1)% 10) == 0)) { System.out.println(); } } System.out.println(); } }

Following is the output from the test program as captured from the console of the Eclipse IDE:

main >>> maxValue: 9999999 main <<< short duration: 234 ms main <<< long duration: 246 ms main <<< short duration: 227 ms main <<< long duration: 209 ms main <<< short duration: 196 ms main <<< long duration: 238 ms main <<< short duration: 214 ms main <<< long duration: 195 ms main <<< short duration: 188 ms main <<< long duration: 190 ms main <<< short duration: 195 ms main <<< long duration: 190 ms main <<< short duration: 195 ms main <<< long duration: 201 ms main <<< short duration: 208 ms main <<< long duration: 171 ms main <<< short duration: 179 ms main <<< long duration: 190 ms main <<< short duration: 186 ms main <<< long duration: 195 ms main <<< average: 202 ms

As we can see, sometimes the shorter program takes longer than the longer but easier to follow and maintain program. On other occasions the longer program takes more time. In this case it seems that there is no overhead penalty writing easier to maintain programs. Please keep in mind that on some occasions the shorter program may in most cases run faster than the longer one. Always test with real data in order to make performance decisions.

If you have comments or questions regarding this or any other entry in this blog, please send me a message via email. I will not disclose your name unless you explicitly specify so.

John

**john.canessa@gmail.com**

**@john_canessa**