Как не надо писать факториал в Java

Перевод этой статьи уже был однажды опубликован на хабре, но там почему-то осталась за кадром самая важная часть. Ниже — полный перевод.

На написание этой статьи меня вдохновила заметка "Как бы вы написали факториал на Java?". Так что извините, я немного поразглагольствую в коде: у меня есть главная мысль, которую я выскажу в конце.

Если вам надо написать факториал на Java, то большинство из ваc, вероятно, начнёт с чего-нибудь такого:

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

Завернём это в класс (мы всё-таки говорим о Java), вероятно, это будет какой-нибудь вспомогательный (*Util) класс, например:

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

Просто, разве нет?

Существует и нерекурсивное решение:

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

Внимательный читатель заметит, что результат может быть больше, чем максимально допустимое целое число (тип integer), и наверняка захочет переписать функцию так, чтобы она использовала 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. Если бы я кэшировал эти значения, конечно, вычисления могли бы быть гораздо быстрее. Если мы уже однажды рассчитали какое-то значение, то сохраним его для дальнейшего использования, например, в HashMap:

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

Достаточно просто, правда?
Каждый из этих методов имеет свои достоинства и недостатки, поэтому, учитывая, что эта библиотека, вероятно, ещё не раз пригодится нам в будущем, стоит использовать стандартный механизм, популярный в Java-библиотеках. Я говорю о системе подключаемых (pluggable) модулей, которая позволяет во время выполнения (at runtime) решать, какой именно алгоритм использовать: медленный, но потребляющий меньше памяти, либо быстрый, но потребляющий больше памяти. Для начала нам надо переделать наш класс в Singleton, потому что любые подключаемые штуковины требуют инициализированных классов и сиглтон, возвращающий реализацию по умолчанию.

Итак, мы создаём класс, работа которого заключается в поддержке синглтона для нашей фабрики (Factory class), и ссылки на алгоритм, реализующий метод. Этот класс предоставляет старый интерфейс, который был показан выше, а также позволяет использовать новый, улучшенный алгоритм:

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

Недостаток этого дизайна, с точки зрения Java, должен быть очевиден: он не позволяет нам выбрать алгоритм во время выполнения (at runtime) — а ведь это и была изначально наша главная задумка. То есть очевидно, нам надо загрузить конфигурацию и выбрать алгоритм согласно ей. Например, мы можем прочитать некоторое системное свойство (System property), которое содержит имя класса, реализующего алгоритм. В идеале наш главный метод должен выглядеть примерно так:

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

Что означает, что нам нужно иметь ассоциативный массив, содержащий все существующие реализации. Из него мы смогли бы взять нужный алгоритм перед тем, как создать наш синглтон внутри метода-фабрики.

Итак, нам нужна фабрика, которая могла бы генерировать алгоритмы. Мы храним как массив созданных фабрик-синглтонов, так и массив соответствий имён классов и реализаций в classMapping. Таким образом, мы не создаём объект класса-алгоритма, пока он нам реально не понадобится (нечего вызывать лишние конструкторы и тратить ресурсы без пользы).

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

Перепишем класс FactorialUtil, так чтобы он использовал наши именованные алгоритмы:

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

А также нам понадобится добавить в классы CachedFactorialImplementation и LoopedFactorialImplementation блоки статической инициализации (static class initializers), которые зарегистрируют их в фабрике:

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, и зарегистрировать его через FactorialAlgorithmFactory в блоке статической инициализации:

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

И наконец, в главном методе мы убеждаемся, что наш класс загружен, и устанавливаем системное свойство.

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

Нет проблем! Более того, эта архитектура позволяет подключать и более изощрённые решения, такие как эти.

Я уверен, что многие Java-программисты, дойдя до этого места, кивают головами и восхищаются изящностью этой архитектуры. Найдутся и такие, кто уже жмёт кнопку «Оставить комментарий» и пишет: «Чёрт возьми, тебе лучше было бы установить системные свойства так-то и так-то». Например, я мог бы поместить инициализатор для разных классов в файл с свойствами (*.properties) или в XML-файл. Или может, лучше было бы, чтобы значением системного свойства было полное имя класса.

И уж конечно, найдутся и такие, которые всю дорогу делали записи в своём блокноте и уже копируют куски кода из этого блога (да, весь этот код рабочий, я его протестировал на своей машине).

Но погодите, вот наконец моя главная мысль.

Всё это хрень.

Каждая-прекаждая строчка.

Несомненно, в некоторых обстоятельствах подключаемая архитектура полезна и даже необходима. Но это бывает достаточно редко — настолько редко, что это даже несмешно. В 99% случаев, когда я видел подобный код, он был целиком и полностью бесполезным. Он скрывает истинное назначение кода, заменяя двух-трёхстрочный вспомогательный метод десятками и даже сотнями строчек самодовольного напыщенного буллшита на Java. Возможно, он помогает вам чувствовать себя хорошо, но он создаёт уродливый беспорядок, который будущим разработчикам придётся подчистить, или скорее всего избегать как чумы.

А самое интересное, вы заметили кое-что? В течение всей этой дискусии, вы ничего не заметили?

Мы ни разу не позаботились об отрицательных числах.

Умный Java-разработчик знает, когда остановиться. Жизнь слишком коротка, чтобы строить замки в облаках. Он знает, что простого решения с циклом более чем достаточно, и конечно, он позаботится об отрицательных числах. (Ну вы в курсе, да? Наше рекурсивное решение впадёт в бесконечный цикл, если дать на входе отрицательное число.)

По-настоящему умный Java-разработчик может погрузиться в проблему чуть глубже и узнать, что факториал — это частный случай Гамма-функции. Возможно, правильное решение — это вовсе и никакой из приведённый выше кусков кода, а вообще аппроксимация Стирлинга для гамма-функции:

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

Но это уже зависит от проблемной области — о которой мы вообще-то даже и не думали, создавая все эти наши фабрики.

Моя самая большая жалоба на Java-разработчиков состоит в том, что они развивают целую кучу действительно плохих привычек. Спецификации неясные. Они думают, что когда-нибудь код, возможно, должен будет быть расширен в другом направлении. Поэтому они пишут целую кучу раздутой архитектурной бессмыслицы, полагая, что однажды вся эта дополнительная фигня внезапно им поможет и сделает их жизнь проще. А Java как язык позволяет это делать быстро и удобно, так что нам легко строить архитектуру, которая когда-нибудь в будущем упростит нам жизнь.

Но будущее никогда не становится проще, верно?

Потому что через год они, продираясь через весь этот лишний багаж, написанный в то время, когда они думали, что понимают проблемную область (хотя теперь ясно, что не понимали), вместо того, чтобы иметь несколько строчек простого кода (как наш самый первый пример факториала), который они могли бы пересмотреть при необходимости, вынуждены иметь дело с навороченной кучей бессмыслицы, которую уже никто не может понять.

И вместо того, чтобы пробраться через эту кучу, чтобы развязать узел или хотя бы понять, как этот механизм работает, они просто шлёпают заплатку поверх архитектуры, как в классическом примере потока лавы. Например, они не понимают, как создать подключаемый алгоритм, и поэтому они переопределяют класс FactoryUtil или просто пишут класс FactoryUtil заново и добавляют туда ещё сотню-другую (непродуманного) кода, просто для того, чтобы по-быстрому залатать непонимание предыдущих ста строк (непродуманного) кода.

Поэтому пожалуйста, сделайте всем нам одолжение: если вы испытываете желание добавить сложности просто потому, что «когда-нибудь нам это пригодится» или «система пока недостаточно гибкая» или «в нашем коде должно быть повторное использование (reusability)» или (не дай бог!) потому что «это круто» — просто уйдите домой пораньше. Посмотрите мультики. Или возьмите в прокате "Начало".

Перестаньте создавать нам дополнительную работу без хорошей на то причины.