So we put a factory into your algorithm or how not to consider factorials

From the translator: In this post, the tendency of some developers to use significantly more complex solutions than the situation requires is ridiculed. A simple factorial calculation algorithm is taken as an example.

Many would not be philosophizing slyly and wrote like:

public class FactorialUtil { public static int factorial(int n) { int ret = 1; for (int i = 1; i <= n; ++i) ret *= i; return ret; } } 

The thoughtful reader probably exclaimed now: “Oh, horror, what if the factorial value will be more than fit into an int ?!”, and is ready to rewrite the code using BigInteger, or at least long:

 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 we still have not done anything so that each time we recalculate intermediate values ​​from 1 to n. If you cache these values, you can save a lot of operations! You can, for example, using a recursive algorithm, save already calculated values:

 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; } } 

Pretty simple, huh?

Obviously, all these methods have their advantages and disadvantages, so since we can then want to use this library, we should use the technique that many other libraries use: a tricky mechanism that allows you to choose a calculation algorithm (slow but economical) memory, or fast, but requiring a lot of space). So we need to make a singleton class that has a link to the selected algorithm. This class has the same interface ( for backward compatibility - approx. Transl.), But uses a separate (new and improved!) Engine for algorithms:
')

 public class FactorialUtil { private static FactorialUtil singleton; private FactorialAlgorithm algorithm; /** *    ,     */ private FactorialUtil() { algorithm = new CachedFactorialImplementation(); } /** *  ,     * @param algorithm */ public FactorialUtil(FactorialAlgorithm a) { algorithm = a; } /** *    ,   , *        * @param n * @return */ public static BigInteger factorial(int n) { if (singleton == null) { //       singleton = new FactorialUtil(); } return singleton.doFactorial(n); } /** *  ,      *     * @param n * @return */ private BigInteger doFactorial(int n) { //    return algorithm.factorial(n); } } 

Please note that this class is responsible for creating the singleton and for choosing the algorithm. We have the opportunity to use the class in the old way and in a new way. The algorithm interface we have is:

 public interface FactorialAlgorithm { BigInteger factorial(int n); } 

This is how the implementation of factorial counting with caching will look like:

 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; } } 

Just look how simple and beautiful! You can easily add a non-recursive algorithm without a cache:

 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; } } 

Obviously, the weak point of this design: we will not be able to select the algorithm on the fly, and this was an important feature that we planned. So we, of course, must keep the algorithm in the config. You can put its name in the properties of the system, because it is quite convenient, and then you can easily connect to external storage ( for example, XML - note. Trans.). Ideally, our main method would be:

 public static void main(String[] args) { System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm"); System.out.println("5! = " + FactorialUtil.factorial(5)); } 

So we need a factory of algorithms. We will store both the instances of singletons and classes so as not to create algorithms before we use them (in fact: why call so many designers and allocate a lot of resources while you do not need to do this?)

 /** * ,        * @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 { try { Class.forName("com.chaosinmotion.factorial.LoopedFactorialImplementation"); Class.forName("com.chaosinmotion.factorial.CachedFactorialImplementation"); } catch (ClassNotFoundException e) { //    } } /**        */ public static FactorialAlgorithm getDefaultAlgorithm() { if (defaultAlgorithm == null) { // :   ,  CachedFactorialImplementation // -   classpath defaultAlgorithm = getAlgorithm("cachedAlgorithm"); } return defaultAlgorithm; } /**     */ public static FactorialAlgorithm getAlgorithm(String name) { FactorialAlgorithm f = mapping.get(name); if (f == null) { //      Class<? extends FactorialAlgorithm> c = classMapping.get(name); if (c != null) { //    try { f = c.newInstance(); mapping.put(name, f); return f; } catch (Exception e) { //   Logger.getLogger("com.chaosinmotion.factorial"). warning("Unable to instantiate algorithm " + c.getCanonicalName() + ", named " + name); } } return getDefaultAlgorithm(); //  - } else return f; } /**  ,       */ public static void registerAlgorithm(String name, Class<? extends FactorialAlgorithm> f) { classMapping.put(name, f); } } 

Now we rewrite our class FactorialUtil to use the named algorithms:

 public class FactorialUtil { private static FactorialUtil singleton; private FactorialAlgorithm algorithm; /** *    ,     */ private FactorialUtil() { String name = System.getProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm"); if (name == null) { algorithm = FactorialAlgorithmFactory.getDefaultAlgorithm(); } else { algorithm = FactorialAlgorithmFactory.getAlgorithm(name); } } /** *  ,     * @param algorithm */ public FactorialUtil(FactorialAlgorithm a) { algorithm = a; } /** *    .   FactorialAlgorithmFactory,     * @param name */ public FactorialUtil(String name) { algorithm = FactorialAlgorithmFactory.getAlgorithm(name); } /** *    ,   , *        * @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); } /** *  ,      *     * @param n * @return */ private BigInteger doFactorial(int n) { //    return algorithm.factorial(n); } } 

Now we need to update our implementations of the algorithm so that they are registered in the 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; } } 

This architecture is beautiful in that we can add new algorithms and connect them to the singleton in FactorialUtil. You just need to create a new implementation of the FactorialAlgorithm, which will register itself in the factory:

 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 the main method, make sure that our class is loaded and set the system property:

 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)); } 

And no problems! This architecture allows you to connect and much more cunning algorithms, such as these .