Pull to refresh

So we put a factory into your algorithm или как не надо считать факториалы

Java *
Translation
Original author: William Woody
От переводчика: В этом посте высмеивается тенденция некоторых разработчиков применять существенно более сложные решения, чем требует ситуация. В качестве примера взят простой алгоритм подсчёта факториала.

Многие бы не стали мудрствовать лукаво и написали подобное:
public class FactorialUtil {
    public static int factorial(int n) {
        int ret = 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}
Вдумчивый читатель наверняка сейчас воскликнул: «О, ужас, а вдруг значение факториала будет больше, чем помещается в int?!», и уже готов переписать код с использованием BigInteger, или хотя бы 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;
    }
}
Заметьте, что мы до сих пор ничего не сделали с тем, что каждый раз пересчитываем промежуточные значения от 1 до n. Если эти значения закешировать, то можно сэкономить кучу операций! Можно, например, используя рекурсивный алгоритм, сохранять уже подсчитанные значения:
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;
     }
}

Довольно просто, да?

Очевидно, у всех этих методов есть свои достоинства и недостатки, так что поскольку эту библиотеку мы потом можем захотеть использовать, нам стоит использовать технику, которую используют многие другие библиотеки: хитрый механизм, который позволяет в рантайме выбрать алгоритм подсчёта(медленный, но экономный по памяти, или быстрый, но требующий много места). Так что нам нужно сделать класс-синглетон, который имеет ссылку на выбранный алгоритм. У этого класса остаётся тот же интерфейс (для обратной совместимости — прим. перев.), но использует отдельный (новый и улучшенный!) движок для алгоритмов:

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

Обратите внимание, что этот класс отвечает за создание синглетона и за выбор алгоритма. У нас есть возможность использовать класс и по-старому, и по-новому. Интерфейс алгоритма у нас такой:

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

Очевидно и слабое место этого дизайна: мы не сможем выбрать алгоритм «на лету», а это была важная фича, которую мы планировали. Так что мы, конечно же, должны хранить алгоритм в конфиге. Можно положить его имя в свойства системы, потому что это довольно удобно, и потом можно легко подключить к внешнему хранилищу (например, XML — прим.перев.). В идеале наш метод main будет таким:

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

Значит, нам нужна фабрика алгоритмов. Будем хранить и сами экземпляры синглетонов, и классы, чтобы не создавать алгоритмы до того, как ими будем пользоваться (в самом деле: зачем вызывать столько конструкторов и выделять кучу ресурсов пока этого не нужно делать?)

/**
 * Фабрика, которая управляет алгоритмами подсчёта факториала в системе
 * @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);
    }
}

Теперь перепишем наш класс FactorialUtil, чтобы он исользовал именованные алгоритмы:
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);
    }
}


Теперь нужно обновить наши реализации алгоритма, чтобы они регистрировались в фабрике:

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

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


Эта архитектура прекрасна тем, что мы можем добавлять новые алгоритмы и подключать их к синглетону в FactorialUtil. Нужно просто создать новую реализацию FactorialAlgorithm, которая себя зарегистрирует в фабрике:
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));
    }
}

А в методе main убедимся, что наш класс загружен и установим системное свойство:
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));
    }


И никаких проблем! Эта архитектура позволяет подключить и куда более хитрые алгоритмы, например, эти.
Tags: javafactoryantipatternlulzпереинженерин
Hubs: Java
Total votes 130: ↑114 and ↓16 +98
Comments 121
Comments Comments 121

Popular right now

Top of the last 24 hours