I will admit this post was inspired by How would you write factorial(n) in java? So excuse me while I rant in code: I have a point to make at the bottom of this article.
Now most people who write factorial in Java may start with something simple, like:
public static int factorial(int n)
{
if (n == 0) return 1;
return n * factorial(n-1);
}
Wrapping this in a class (since we’re talking about Java, of course), they may write it inside a utility class. For example:
public class FactorialUtil
{
public static int factorial(int n)
{
if (n == 0) return 1;
return n * factorial(n-1);
}
}
Simple, no?
There is a non-recursive solution as well:
public class FactorialUtil
{
public static int factorial(int n)
{
int ret = 1;
for (int i = 1; i <= n; ++i) ret *= i;
return ret;
}
}
Now the observent reader may note “gosh, it’s entirely possible the value will be longer than an integer”, so they’ll perhaps rewrite in terms of BigInteger or at least in terms of long, depending on the requirements of the program. Thus:
public class FactorialUtil
{
public static BigInteger factorial(int n)
{
BigInteger ret = BigInteger.ONE;
for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
return ret;
}
}
Notice that thus far, of course, I’ve made no use the fact that I’m constantly recalculating the intemediate values from 1 to n. If those values were cached, of course, I could save myself a lot of computations. One way to do this is to use recursion, but if we’ve already calculated the value, store it away for future use. Thus (using HashMap, because it’s there), we get:
public class FactorialUtil
{
static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
public static BigInteger factorial(int n)
{
BigInteger ret;
if (n == 0) return BigInteger.ONE;
if (null != (ret = cache.get(n))) return ret;
ret = BigInteger.valueOf(n).multiply(factorial(n-1));
cache.put(n, ret);
return ret;
}
}
Easy enough, right?
Now each of these different methods entail different tradeoffs, and given that we may wish to reuse this library in the future, perhaps what we want to use is a technique routinely used in other Java libraries: a pluggable mechanism that allows us at runtime to decide which technique (the slower but small memory footprint technique, or the more memory intensive, but faster technique). So first, we need to refactor our class as a singleton, because pluggable things require instantiated classes and a default singleton class to implement the default mechanism.
So we create a class whose job it is to maintain a singleton for our factory class, and a reference to the algorithm that actually implements our method. This class provides the old interface we have from above, but defers to a separate (and new and improved!) algorithm engine:
public class FactorialUtil
{
private static FactorialUtil singleton;
private FactorialAlgorithm algorithm;
/**
* Default (internal) constructor constructs our default algorithm.
*/
private FactorialUtil()
{
algorithm = new CachedFactorialImplementation();
}
/**
* New initializer which allows selection of the algorithm mechanism
* @param algorithm
*/
public FactorialUtil(FactorialAlgorithm a)
{
algorithm = a;
}
/**
* Default public interface for handling our factorial algorithm. Uses
* the old standard established earlier for calling into our utility class.
* @param n
* @return
*/
public static BigInteger factorial(int n)
{
if (singleton == null) {
// Use default constructor which uses default algorithm
singleton = new FactorialUtil();
}
return singleton.doFactorial(n);
}
/**
* New mechanism which allows us to instantiate individual factorial
* utilitiy classes and invoke customized factorial algorithms directory.
* @param n
* @return
*/
private BigInteger doFactorial(int n)
{
// Defer to our algorithm
return algorithm.factorial(n);
}
}
Notice the above class is now responsible for creating the singleton and deferring to the algorithm class. We even have a private initializer which initializes to any algorithm, and a way to create an instance which uses the algorithm we select.
This all depends on an algorithm interface:
public interface FactorialAlgorithm
{
BigInteger factorial(int n);
}
And here is our cached factorial implementation referred to from above:
public class CachedFactorialImplementation implements FactorialAlgorithm
{
static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
@Override
public BigInteger factorial(int n)
{
BigInteger ret;
if (n == 0) return BigInteger.ONE;
if (null != (ret = cache.get(n))) return ret;
ret = BigInteger.valueOf(n).multiply(factorial(n-1));
cache.put(n, ret);
return ret;
}
}
Look how beautiful this structure is! I mean, we can also add a non-caching non-recursive algorithm easily:
public class LoopedFactorialImplementation implements FactorialAlgorithm
{
@Override
public BigInteger factorial(int n)
{
BigInteger ret = BigInteger.ONE;
for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
return ret;
}
}
The weakness of this design from a Java perspective should be obvious: it does not allow us to select the algorithm we wish to use at runtime, which was a major design feature we were striving for. (I mean, after all, if our new program has different constraints, we should be able to select the specific algorithm used, right?) So clearly we need to load a configuration property and select the algorithm we want. We can do this by having our utility class look in the System properties, for example, which has the nice property that we can then, higher up, wire up to an external interface as needed. Ideally our main method would look like:
public static void main(String[] args)
{
System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm");
System.out.println("5! = " + FactorialUtil.factorial(5));
}
This implies that we need a hash map of algorithms that we pick from prior to creating our singleton inside the factorial method.
So we need a factory that can generate the algorithms. We store both a map of instantiated factory singletons by name in mapping, and we store the class references in classMapping, so we don’t create the algorithm class until we actually need it. (No point in running a bunch of constructors and allocating resources we don’t use.)
/**
* Factory class manages the factorial algorithms in our system.
* @author wwoody
*
*/
public class FactorialAlgorithmFactory
{
private static HashMap<String,FactorialAlgorithm> mapping = new HashMap<String,FactorialAlgorithm>();
private static HashMap<String,Class<? extends FactorialAlgorithm>> classMapping = new HashMap<String,Class<? extends FactorialAlgorithm>>();
private static FactorialAlgorithm defaultAlgorithm = new CachedFactorialImplementation();
/** Static initializer registers some of my known classes */
static {
try {
Class.forName("com.chaosinmotion.factorial.LoopedFactorialImplementation");
Class.forName("com.chaosinmotion.factorial.CachedFactorialImplementation");
}
catch (ClassNotFoundException e) {
// Should never happen.
}
}
/** Get the default algorithm for computing factorials */
public static FactorialAlgorithm getDefaultAlgorithm()
{
if (defaultAlgorithm == null) {
// Warning: this will fail if for whatever reason CachedFactorialImplementation
// is not in the class path.
defaultAlgorithm = getAlgorithm("cachedAlgorithm");
}
return defaultAlgorithm;
}
/** Get the factorial algorithm specified by name */
public static FactorialAlgorithm getAlgorithm(String name)
{
FactorialAlgorithm f = mapping.get(name);
if (f == null) {
// We haven't created an instance yet. Get it from the class mapping.
Class<? extends FactorialAlgorithm> c = classMapping.get(name);
if (c != null) {
// Create a new instance of the factorial algorithm specified
try {
f = c.newInstance();
mapping.put(name, f);
return f;
}
catch (Exception e) {
// Log the error
Logger.getLogger("com.chaosinmotion.factorial").
warning("Unable to instantiate algorithm " +
c.getCanonicalName() + ", named " + name);
}
}
return getDefaultAlgorithm(); // return something.
}
else return f;
}
/** Register the class so we can construct a new instance if not already initialized */
public static void registerAlgorithm(String name, Class<? extends FactorialAlgorithm> f)
{
classMapping.put(name, f);
}
}
Rewriting our FactorialUtil class to use our named algorithms instead, we get:
public class FactorialUtil
{
private static FactorialUtil singleton;
private FactorialAlgorithm algorithm;
/**
* Default (internal) constructor constructs our default algorithm.
*/
private FactorialUtil()
{
String name = System.getProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm");
if (name == null) {
algorithm = FactorialAlgorithmFactory.getDefaultAlgorithm();
} else {
algorithm = FactorialAlgorithmFactory.getAlgorithm(name);
}
}
/**
* New initializer which allows selection of the algorithm mechanism
* @param algorithm
*/
public FactorialUtil(FactorialAlgorithm a)
{
algorithm = a;
}
/**
* Utility to create by name. Calls into FactorialAlgorithmFactory to
* actually get the algorithm.
* @param name
*/
public FactorialUtil(String name)
{
algorithm = FactorialAlgorithmFactory.getAlgorithm(name);
}
/**
* Default public interface for handling our factorial algorithm. Uses
* the old standard established earlier for calling into our utility class.
* @param n
* @return
*/
public static BigInteger factorial(int n)
{
if (singleton == null) {
// Use default constructor which uses default algorithm
singleton = new FactorialUtil();
}
return singleton.doFactorial(n);
}
/**
* New mechanism which allows us to instantiate individual factorial
* utilitiy classes and invoke customized factorial algorithms directory.
* @param n
* @return
*/
private BigInteger doFactorial(int n)
{
// Defer to our algorithm
return algorithm.factorial(n);
}
}
And we have to modify our CachedFactorialImplementation and LoopedFactorialImplementation to include static class initializers which register those classes with my factory:
public class CachedFactorialImplementation implements FactorialAlgorithm
{
static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
static {
FactorialAlgorithmFactory.registerAlgorithm("cachedAlgorithm", CachedFactorialImplementation.class);
}
@Override
public BigInteger factorial(int n)
{
BigInteger ret;
if (null != (ret = cache.get(n))) return ret;
ret = BigInteger.valueOf(n).multiply(factorial(n-1));
cache.put(n, ret);
return ret;
}
}
and
public class LoopedFactorialImplementation implements FactorialAlgorithm
{
static {
FactorialAlgorithmFactory.registerAlgorithm("loopedAlgorithm", LoopedFactorialImplementation.class);
}
@Override
public BigInteger factorial(int n)
{
BigInteger ret = BigInteger.ONE;
for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
return ret;
}
}
The beauty of this architecture, of course, is that we can even add in our own custom algorithm and plug it into the singleton underlying FactorialUtil. We simply create our new FactorialAlgorithm implementation, registering our class with the FactorialAlgorithmFactory class during static class initialization:
public class RecursiveFactorialImplementation implements FactorialAlgorithm
{
static {
FactorialAlgorithmFactory.registerAlgorithm("recursiveAlgorithm", RecursiveFactorialImplementation.class);
}
@Override
public BigInteger factorial(int n)
{
if (n == 0) return BigInteger.ONE;
return BigInteger.valueOf(n).multiply(factorial(n-1));
}
}
and in our main routine, we make sure our class is loaded, then we set the property to specify we use our new algorithm.
public static void main(String[] args)
{
try {
Class.forName("com.chaosinmotion.factorial.RecursiveFactorialImplementation");
}
catch (ClassNotFoundException e) {
// if this fails, no matter; we'll still use the default implementation.
}
System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "recursiveAlgorithm");
System.out.println("5! = " + FactorialUtil.factorial(5));
}
No problems! And the architecture even lends itself to our plugging in more ingenious solutions, such as the algorithms documented here.
Now I’m sure at this point there are a number of Java programmers reading this who are nodding their heads at how cool all of this mechanism is. There are a few, of course, who are about to hit the comment button and say “gosh, instead you should wire up the properties this way, or that way…” For example, I could have put the initializer for the different class mappings into a properties file that is part of the package, or as an XML file. Or perhaps I could have set the property to accept the class name explicitly; that way I could have the FactorialAlgorithmFactory do the ‘forName’ call and instantiate the class directly without having to look it up in two hash maps.
And I’m sure there are a few programmers out there taking notes or even cutting and pasting the above blocks of code. (Yes, I tested it all; it works on my system, though I don’t claim to have done the cut and paste properly in all cases.)
But here’s my point.
It’s all crap.
Every last line of it.
Sure, there are circumstances where a pluggable architecture would be desirable or even necessary–but that comes up so rarely it’s not even funny. About 99% of the time I see code like this, it’s completely and utterly useless. It’s obscuring the purpose of the code–replacing a two or three line utility (max!) with dozens or even hundreds of lines of self-important masturbatory Java bullshit. Sure, it may make you feel good–but it makes an ugly mess of it that future developers will have to clean up, or more likely just avoid like the plague.
And, worse, in the entire discussion, did you notice something?
We never handled negative numbers.
The smart Java developer would know when to stop. Life is too short to build castles in the clouds. He’d know that a simple looped solution is more than sufficient, and of course he handles negative numbers. (Note that in our recursive solutions, a negative number results in an endless loop.)
The really smart Java developer figures out the domain of the problem set, knowing (for example) that factorial is actually a special subset of the Gamma function. Perhaps the right answer isn’t any of the code above; perhaps the right answer is using Gergo Nemes’s approximation to Stirling’s approximation to the Gamma Function:
static double Gamma(double z)
{
double tmp1 = Math.sqrt(2*Math.PI/z);
double tmp2 = z + 1.0/(12 * z - 1.0/(10*z));
tmp2 = Math.pow(z/Math.E, z); // ooops; thanks hj
tmp2 = Math.pow(tmp2/Math.E, z);
return tmp1 * tmp2;
}
But it depends on the domain: a domain we only second-guessed in all of our factory creation/algorithm interface bullshit above.
The biggest complaint I have with many Java developers is that they develop a whole bunch of really bad habits. Specifications are unclear, or they think someday the code may need to be extended into a different direction. So they write a whole bunch of overblown architectural nonsense, sight unseen, thinking that the additional crap someday will help out and make things easier. And Java as a language lends itself to doing this very quickly and easily, so that (as the theory goes) it’s easy for us to build architectures that will someday make it easier on us in the future.
But the future never gets easier, does it?
Because a year from now they wade through all this excess baggage written at a time when they thought they understood the domain of the problem (but clearly didn’t), instead of having simple code (like the very first example of factorial above) that they can revise as needed, they wind up with the most over-engineered pile of nonsense that no-one can possibly understand.
And rather than wade into the mess to untangle the knot, or at least understand the mechanism that was put into place, they just plaster over the problem in a classical example of the lava flow anti-pattern. Perhaps they don’t understand how to create a pluggable algorithm, so instead they override the FactoryUtil class, or they simply create a new FactoryUtil class instead–and add hundreds more lines of (ill-conceived) code to plaster over the lack of understanding of the hundreds of existing lines of (ill-conceived) code.
So please, do us all a favor: if you have the urge to add complexity because “someday we’ll need it, I just know it!”, or because “it’s not sufficiently flexible enough” or “we need reusability in our code” or (God help us!) because it’s “cool”–just go home early. Watch some cartoons. Rent Inception on DVD.
And stop creating extra work for us in the future for no good reason.
Development Chaos Theory 