Функциональное мышление: Различные подходы к трансформации и оптимизации

Продолжаем сравнение возможностей функциональных языков и инфраструктур

Различные функциональные языки и инфраструктуры часто предлагают одни и те же абстракции и функции, но под разными названиями. В статье из цикла "Функциональное мышление" Нил Форд выполнит оптимизацию решения из предыдущей статьи, улучшив алгоритм и добавив кэширование, чтобы показать, как каждый язык или инфраструктура обеспечивают необходимые изменения.

Нил Форд, Архитектор приложений, ThoughtWorks

Нил Форд (Neal Ford) работает архитектором приложений в ThoughtWorks, революционной компании, предоставляющей профессиональные IT-услуги и помогающей талантливым людям по всему миру эффективнее использовать программное обеспечение. Он также является проектировщиком и разработчиком приложений, учебных материалов, журнальных статей, учебных курсов, видео/DVD-презентаций и автором книг "Разработка с Delphi: Объектно-ориентированный подход", "JBuilder 3 Unleashed" и "Искусство разработки Web-приложений на Java". Он специализируется на консультациях по построению широкомасштабных корпоративных приложений. Он также является общепризнанным докладчиком и выступал на многочисленных конференциях разработчиков по всему миру. С ним можно связаться по адресу: nford@thoughtworks.com.



13.05.2013

Об этой серии статей

Эта серия статей призвана переориентировать читателя в "функциональном" направлении и помочь ему взглянуть на проблемы под новым углом, чтобы улучшить повседневное написание кода. В ней изучаются принципы функционального программирования и инфраструктуры, позволяющие использовать функциональное программирование в языке Java™. Так, в статьях рассматриваются функциональные языки программирования, работающие на виртуальной Java-машине, и некоторые направления будущего развития языков программирования. Эта серия статей предназначена для программистов, знающих язык Java и работу его абстракций, но не имеющих опыта в использовании функциональных языков.

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

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

Оптимизация версии, написанной на Java

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

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

В листинге 1 приведена исходная версия Java-программы для определения простоты числа.

Листинг 1. Исходная версия Java-программы для определения простоты числа
public class PrimeNumberClassifier {
    private Integer number;

    public PrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public Set<Integer> getFactors() {
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (Integer i = 2; i < number; i++)
            if (isFactor(i))
                factors.add(i);
        return factors;
    }

    public int sumFactors() {
        int sum = 0;
        for (int i : getFactors())
            sum += i;
        return sum;
    }

    public boolean isPrime() {
        return sumFactors() == number + 1;
    }
}

В листинге 1 метод getFactors() выполняет итерирование по списку потенциальных делителей от 2 до самого исследуемого числа, что довольно неэффективно. Необходимо учесть тот факт, что делители всегда встречаются парами, поэтому, найдя один делитель, я могу легко найти парный ему делитель с помощью простого деления. Таким образом, нет необходимости выполнять итерирование до самого числа; достаточно выполнить итерирование до квадратного корня из целевого числа, а затем собрать все делители попарно. В листинге 2 представлена улучшенная версия программы с оптимизированным методом getFactors().

Листинг 2. Оптимизация Java версии
public class PrimeNumber {
    private Integer number;
    private Map<Integer, Integer> cache;

    public PrimeNumber() {
        cache = new HashMap<Integer, Integer>();
    }

    public PrimeNumber setCandidate(Integer number) {
        this.number = number;
        return this;
    }

    public static PrimeNumber getPrime(int number) {
        return new PrimeNumber().setCandidate(number);
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public Set<Integer> getFactors() {
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (int i = 2; i < sqrt(number) + 1; i++)
            if (isFactor(i)) {
                factors.add(i);
                factors.add(number / i);
            }
        return factors;
    }

    public int sumFactors() {
        int sum = 0;
        if (cache.containsValue(number))
            sum = cache.get(number);
        else
            for (int i : getFactors())
                sum += i;
        return sum;
    }

    public boolean isPrime() {
        return number == 2 || sumFactors() == number + 1;
    }

}

В методе getFactors() в листинге 2 я выполняю итерирование от 2 до квадратного корня из целевого числа (увеличенного на 1, чтобы учесть возможные ошибки при округлении) и собираю делители по парам. Важно отметить, что этот метод возвращает коллекцию типа Set, что позволяет учесть особую ситуацию, когда исходное число является точным квадратом. Например, квадратный корень из числа 16 равен 4, и если бы в методе getFactors() использовалась коллекция типа List, то в получившемся списке делитель 4 присутствовал бы два раза. Unit-тесты как раз и предназначаются для поиска таких особых ситуаций.

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

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


Оптимизация Functional Java версии

Functional Java – это инфраструктура, добавляющая функциональные возможности в язык Java (см. раздел "Ресурсы"). В листинге 3 показаны первоначальные версии методов getFactors() и sumFactors(), которые нам предстоит оптимизировать.

Листинг 3. Первоначальные версии методов getFactors() и sumFactors() для Functional Java
public List<Integer> getFactors() {
    return range(1, number + 1)
            .filter(new F<Integer, Boolean>() {
                public Boolean f(final Integer i) {
                    return isFactor(i);
                }
            });
}

public int sumFactors() {
    return getFactors().foldLeft(fj.function.Integers.add, 0);
}

Метод getFactors() в листинге 3 выполняет фильтрацию диапазона чисел от 1 до целевого числа плюс 1 (так как в Functional Java граничные значения не входят в сам диапазон), используя метод isFilter(), чтобы определить, входит число в список делителей или нет. В листинге 4 показана оптимизированная версия программы на Functional Java для определения простоты числа.

Листинг 4. Оптимизированная версия программы на Functional Java
import fj.F;
import fj.data.List;
import java.util.HashMap;
import java.util.Map;
import static fj.data.List.range;
import static fj.function.Integers.add;
import static java.lang.Math.round;

import static java.lang.Math.sqrt;

public class FjPrimeNumber {
    private int candidate;
    private Map<Integer, Integer> cache;

    public FjPrimeNumber setCandidate(int value) {
        this.candidate = value;
        return this;
    }

    public FjPrimeNumber(int candidate) {
        this.candidate = candidate;
        cache = new HashMap<Integer, Integer>();
    }

    public boolean isFactor(int potential) {
        return candidate % potential == 0;
    }

    public List<Integer> getFactors() {
        final List<Integer> lowerFactors = range(1, (int) round(sqrt(candidate) + 1))
                .filter(new F<Integer, Boolean>() {
                    public Boolean f(final Integer i) {
                        return isFactor(i);
                    }
                });
        return lowerFactors.append(lowerFactors.map(new F<Integer, Integer>() {
            public Integer f(final Integer i) {
                return candidate / i;
            }
        }))
        .nub();
    }

    public int sumFactors() {

        if (cache.containsKey(candidate))
            return cache.get(candidate);
        else {
            int sum = getFactors().foldLeft(add, 0);
            cache.put(candidate, sum);
            return sum;
        }
    }

    public boolean isPrime() {
        return candidate == 2 || sumFactors() == candidate + 1;
    }
}

В методе getFactors() в листинге 4 я также использую методы range() и filter(), но уже избирательно. Сначала с помощью метода filter(), как и в листинге 3, я отбираю делители от 1 до квадратного корня из целевого числа. На второй строке метода getFactors() я использую метод map() из арсенала Functional Java, чтобы получить список делителей, превышающих квадратный корень из числа. Метод map() применяет указанную функцию к каждому элементу коллекции, возвращая измененную коллекцию. Список делителей, превышающих квадратный корень, применяется к списку делителей меньше квадратного корня (переменная lowerFactors). На последней строке вызывает метод nub() из Functional Java, преобразующий коллекцию типа List (список) в коллекцию типа Set (набор), тем самым решая проблему с дублированием делителей для точных квадратов.

Оптимизированная версия метода sumFactors() в листинге 4 использует кэш аналогично версии на обычном Java в листинге 2, что накладывает на класс аналогичное требование по хранению внутреннего состояния.


Оптимизация Groovy-версии

В листинге 5 показаны методы getFactors() и sumFactors() из первоначальной версии Groovy-программы.

Листинг 5. Первоначальные методы getFactors() и sumFactors() из Groovy-программы
public def getFactors() {
  (1..number).findAll { isFactor(it) }.toSet()
}

public def sumFactors() {
  getFactors().inject(0, {i, j -> i + j})
}

Groovy-метод findAll() выполняет фильтрацию диапазона чисел, а метод sumFactors() использует Groovy-метод inject(), применяя указанный блок кода к каждому элементу в коллекции, чтобы сократить список до одного элемента (который будет представлять собой сумму всех элементов коллекции, так как в качестве "свертывающей" операции использовалось сложение). В листинге 6 показана оптимизированная Groovy-программа для определения простоты числа.

Листинг 6. Оптимизированная версия Groovy-программы
import static java.lang.Math.sqrt

class PrimeNumber {
  static def isFactor(potential, number) {
    number % potential == 0;
  }

  static def factors = { number ->
    def factors = (1..sqrt(number)).findAll { isFactor(it, number) }
    factors.addAll factors.collect { (int) number / it}
    factors.toSet()
  }

  static def getFactors = factors.memoize();

  static def sumFactors(number) {
    getFactors(number).inject(0, {i, j -> i + j})
  }

  static def isPrime(number) {
    number == 2 || sumFactors(number) == number + 1
  }
}

Как и в версии для Functional Java, в методе factors() из листинга 6 делители делятся на две группы квадратным корнем из целевого числа, а получившийся список преобразуется в набор с помощью метода toSet(). Основное различие между Functional Java и Groovy заключается в используемой терминологии; так, методы filter() и foldLeft() в Functional Java соответствуют методам findAll() и inject() в Groovy.

Оптимизация, показанная в листинге 6, радикально отличается от предыдущих Java-версий. Вместо превращения класса в stateful-компонент я воспользовался Groovy-методом memoize(). Метод factors() в листинге 6 – это "идеальная" функция, что означает, что она зависит только от своих входных параметров и не использует никакого другого внутреннего состояния. При выполнении этого требования среда исполнения Groovy может автоматически кэшировать значения с помощью метода memoize(), который возвращает метод getFactors() – кэшированную версию метода factors(). Это отличный пример того, как возможности функциональных языков помогают уменьшить количество механизмов, которые должны поддерживаться разработчиком приложения - таких как кэширование. Более подробно я рассматривал мемоизацию в статье "Функциональные шаблоны проектирования. Часть 1" из этой же серии.


Оптимизация Scala-версии

В листинге 7 показаны первоначальные версии Scala-методов factors() и sum.

Листинг 7. Первоначальные версии Scala-методов factors() и sum()
def factors(number: Int) =
  (1 to number) filter (isFactor(number, _))

def sum(factors: Seq[Int]) =
 factors.foldLeft(0)(_ + _)

В листинге 7 используется удобный подстановочный символ "_", заменяющий параметры, имена которых не имеют значения. В листинге 8 представлена оптимизированная версия Scala-программы для определения простоты числа.

Листинг 8. Оптимизированная Scala-версия
import scala.math.sqrt;

object PrimeNumber {
  def isFactor(number: Int, potentialFactor: Int) =
    number % potentialFactor == 0

  def factors(number: Int) = {
    val lowerFactors = (1 to sqrt(number).toInt) filter (isFactor(number, _))
    val upperFactors = lowerFactors.map(number / _)
    lowerFactors.union(upperFactors)
  }

  def memoize[A, B](f: A => B) = new (A => B) {
    val cache = scala.collection.mutable.Map[A, B]()
    def apply(x: A): B = cache.getOrElseUpdate(x, f(x))
  }

  def getFactors = memoize(factors)

  def sum(factors: Seq[Int]) =
    factors.foldLeft(0)(_ + _)

  def isPrime(number: Int) =
    number == 2 || sum(getFactors(number)) == number + 1
}

В оптимизированном варианте метода factors() используется тот же приём, что и в предыдущих примерах (например, в листинге 3), но адаптированный к синтаксису Scala, что приводит к довольно прямолинейной реализации.

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


Оптимизация Clojure-версии

В листинге 9 показаны исходные версии Clojure-методов factors и sum-factors.

Листинг 9. Первоначальные версии методов factors и sum-factors
(defn factors [n]
  (filter #(factor? n %) (range 1 (+ n 1))))

(defn sum-factors [n]
  (reduce + (factors n)))

Как и в других неоптимизированных версиях, первоначальная Clojure-программа фильтрует диапазон чисел от 1 до целевого числа плюс 1 и с помощью Clojure-метода reduce применяет операцию + к каждому элементу списка, получая в итоге их сумму. В листинге 10 показана оптимизированная версия Clojure-программы для определения простоты числа.

Листинг 10. Оптимизированная Clojure-версия
(ns primes)

(defn factor? [n, potential]
  (zero? (rem n potential)))

(defn factors [n]
  (let [factors-below-sqrt (filter #(factor? n %) (range 1 (inc (Math/sqrt n))))
        factors-above-sqrt (map #(/ n %) factors-below-sqrt)]
    (concat factors-below-sqrt factors-above-sqrt)))

(def get-factors (memoize factors))

(defn sum-factors [n]
  (reduce + (get-factors n)))

(defn prime? [n]
  (or (= n 2) (= (inc n) (sum-factors n))))

В методе factors для оптимизации используется тот же алгоритм, что и в предыдущих примерах (например, как в листинге 3), собирающий делители меньше квадратного корня путём фильтрации диапазона чисел от 1 до квадратного корня из целевого числа плюс 1: (filter #(factor? n %) (range 1 (inc (Math/sqrt n)))). Для безымянных параметров Clojure-версия использует собственный подстановочный символ "%", как и Scala-версия в листинге 8. Выражение #(/ n %) создаёт анонимную функцию и является сокращённой записью от (fn [x] (/ n x)).

В Clojure присутствует возможность для мемоизации "идеальных" функций с помощью метода memoize, как и в Groovy-версии, что упрощает вторую оптимизацию.


Заключение

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

В следующей статье я детально исследую, как реализуется отложенное выполнение в различных языках и инфраструктурах.

Ресурсы

  • Functional thinking: Transformations and optimizations: оригинал статьи (EN).
  • The Productive Programmer (Neal Ford, O'Reilly Media, 2008): новая книга Нила Форда, в которой более подробно рассматриваются некоторые вопросы из данной серии статей.
  • Scala: современный функциональный язык на основе JVM.
  • Clojure: современная, функциональная реализация Lisp, работающая поверх JVM.
  • Инфраструктура Functional Java добавляет в язык Java множество возможностей из арсенала функциональных языков программирования.
  • Groovy: Java-подобный динамический язык программирования, добавляющий различные функциональные расширения к синтаксису Java.
  • Practically Groovy: познакомьтесь с функциональными (и не только) возможностями Groovy в этой серии статей, опубликованной на портале developerWorks.
  • Execution in the Kingdom of Nouns (Steve Yegge, март 2006 г.) (EN): статья о различных аспектах дизайна языка Java.
  • Посетите магазин книг, посвященных ИТ-технологиям и различным аспектам программирования.

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


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

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=929509
ArticleTitle=Функциональное мышление: Различные подходы к трансформации и оптимизации
publish-date=05132013