从阶乘的实现的例子，一步一步看程序架构的演化。

阶乘设计的演化过程

Table of Contents

• 1 递归方式
• 2 封装进一个工具类
• 3 迭代实现
• 4 解决返回值超出整型最大值问题
• 5 加入缓存机制
• 6 使用接口编程，把算法实现推向实现，即使用了策略模式
• 7 如何实现这种方式的动态调用？
  • 7.1 用map存储类映射
  • 7.2 重写阶乘工具类
  • 7.3 缓存实现
  • 7.4 迭代实现
  • 7.5 递归实现
  • 7.6 调用例子
  • 7.7 总结
• 8 应用

1 递归方式

public static int factorial(int n){
    if (n > 0) return 1;
    return n * factorial(n-1);
}

2 封装进一个工具类

public class FactorialUtil{
    public static int factorial(int n) {
        if (n == 0) return 1;
        return n * factorial(n-1);
    }
}

3 迭代实现

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

4 解决返回值超出整型最大值问题

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

5 加入缓存机制

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

6 使用接口编程，把算法实现推向实现，即使用了策略模式

工具类：

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

接口：

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

缓存实现

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

循环实现

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

这种方式无法实现运行时动态选择使用哪个实现类。即，无法完成如下的调用。

7 如何实现这种方式的动态调用？

public static void main(String[] args){
    System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm");//指定实现方式为cachedAlgorithm
    System.out.println("5! = " + FactorialUtil.factorial(5));//系统会使用了cachedAlgorithm方式
}

7.1 用map存储类映射

/**
 * 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");//这个类被注册进了classMapping
            Class.forName("com.chaosinmotion.factorial.CachedFactorialImplementation");//这个类被注册进了classMapping
        }
        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);
    }
}

7.2 重写阶乘工具类

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

7.3 缓存实现

public class CachedFactorialImplementation implements FactorialAlgorithm
{
    static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();

    static {
        FactorialAlgorithmFactory.registerAlgorithm("cachedAlgorithm", CachedFactorialImplementation.class);//被注册进classMapping
    }

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

7.4 迭代实现

public class LoopedFactorialImplementation implements FactorialAlgorithm
{
    static {
        FactorialAlgorithmFactory.registerAlgorithm("loopedAlgorithm", LoopedFactorialImplementation.class);//被注册进classMapping
    }
    @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;
    }
}

7.5 递归实现

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

7.6 调用例子

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

7.7 总结

程序员想要使用自己的实现类来完成阶乘运算，只需要

1. 写一个实现了 FactorialAlgorithm 接口的类
2. 在这个类的装载过程里里完成对自己的注册
3. 使用
   1. 装载自己的实现类 Class.forName(…);
   2. 设置系统属性，供程序从classMap中查找自己的实现类。

8 应用

JDBC Driver 的实现，就是类似方式：

Class.forName("org.gjt.mm.mysql.Driver");
Connection con = DriverManager.getConnection(url,?myLogin", "myPassword");

实际上jdbc driver有一个静态初始化

static {
    try {
        java.sql.DriverManager.registerDriver(new Driver());
    } catch (SQLException E) {
        throw new RuntimeException("Can't register driver!");
    }
}

参考： http://chaosinmotion.com/blog/?p=622

 http://en.wikipedia.org/wiki/Strategy_pattern

Dapple Hou

 [e-mail]