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

в 15:44, , рубрики: clojure, functional programming, groovy, java, scala, функциональное программирование

Нил Форд, Архитектор ПО, ThoughWorks Inc.
16 октября 2012
перевод статьи Functional thinking: Transformations and optimizations

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

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

Оптимизированная классификация простых чисел, в чистой Java

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

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

Мой оригинальный Java код для определения простых чисел, представлен в Листинге 1:

Листинг 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 до целевого числа, что довольно неэффективно. Рассмотрим тот факт, что делители всегда встречаются парами; из этого следует, что если я нашел один делитель, я могу установить его пару с помощью простого деления. Таким образом, я не должен выполнять итерацию вплоть до целевого числа; Взамен, я могу выполнить итерацию лишь до квадратного корня из целевого числа, собирая делители в пары. Улучшенная версия метода getFactors() представлена в Листинге 2:

Листинг 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 вместо Set будет создавать дубликат 4ки в списке. Юнит тесты существуют именно для того, чтоб находить такие пограничные случаи!

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

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


Оптимизированная Functional Java

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

Листинг 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);
}

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

Листинг 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. Вторая строка использует метод map() из Functional Java для генерации делителей больше, чем квадратный корень. Метод map() применяет функцию к каждому элементу в коллекции и возвращает преобразованную коллекцию. Список делителей больше квадратного корня добавляется к списку делителей меньше(lowerFactors). В последнем методе происходит вызов метода nub() из Functional Java, который конвертирует список в набор, избегая проблему полного квадрата.

Оптимизация sumFactors() в Листинге 4 использует кеш идентично реализации в чистой Java в Листинге 2, предполагая то же условие, что класс имеет состояние.


Оптимизированный Groovy

Оригинальная версия Groovy методов getFactors() и sumFactors() представлена в Листинге 5:

Листинг 5. Оригинальные Groovy методы getFactors() и sumFactors()

public def getFactors() {
  (1..number).findAll { isFactor(it) }.toSet()
}

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

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

Листинг 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 это терминология. В Functional Java методы filter() и foldLeft() синонимы методам findAll() и inject() в Groovy, соответственно.

Оптимизированное решение в Листинге 6 радикально отличается от предшествующих Java версий. Вместо того, чтоб добавлять состояние в класс, я использую метод memoize() из Groovy. Метод factors в Листинге 6 это чистая функция (pure function), это значит, что она опирается только на передаваемые параметры, а не состояния. Как только это условие соблюдено, среда исполнения Groovy может кэшировать значения автоматически с помощь метод memoize(), который возвращает кэшированную версию метода factors(). Этот отличный пример показывает возможность функционального программирования уменьшить число механизмов, которые должен поддерживать разработчик, например кэширование. Мемоизация полностью раскрывается в одной из моих прошлых частей серии — Функциональное мышление: Функциональные шаблоны проектирования, часть 1.


Оптимизированная Scala

Оригинальная Scala версия методов getFactors() и sumFactors() представлена в Листинге 7:

Листинг 7. Оригинальная версия методов factors() и sum()

def factors(number: Int) =
  (1 to number) filter (isFactor(number, _))

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

Код в Листинге 7 использует удобный заполнитель _, для параметров, чьи имена не важны. Оптимизированная Scala версия классификатора простых чисел представлена в Листинге 8:

Листинг 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 не имеет встроенной возможности мемоизации, однако это есть в планах по развитию. Она может быть реализована многими способами, самая простая реализация базируется на встроенной изменяемой(mutable, мутабельной) версии map и удобном методе getOrElseUpdate().


Оптимизированный Clojure

Оригинальные методы factors и sum-factors представлены в Листинге 9:

Листинг 9. Оригинальные методы factors и sum-factors

(defn factors [n]
  (filter #(factor? n %) (range 1 (+ n 1))))

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

Как и в других неоптимизированных версиях, оригинальный код в Clojure фильтрует диапазон чисел от 1 до целевого плюс 1 и использует функцию reduce из Clojure для того, чтобы наложить функцию "+" на каждый элемент, получив в результате сумму. Оптимизированная Clojure версия представлена в Листинг 10:

Листинг 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(), например). Наличие мемоизации формирует существенные различия в легкости ипользования и реализации кеширования.

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

Автор: Sigrlami

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js