Навигация
Главная »  Java 

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


Источник: habrahabr
Sigrlami
Нил Форд, Архитектор ПО, 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 getFactors() { Set factors = new HashSet(); 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 cache;  public PrimeNumber() { cache = new HashMap(); }  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 getFactors() { Set factors = new HashSet(); 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 getFactors() { return range(1, number + 1) .filter(new F() { 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 cache;  public FjPrimeNumber setCandidate(int value) { this.candidate = value; return this; }  public FjPrimeNumber(int candidate) { this.candidate = candidate; cache = new HashMap(); }  public boolean isFactor(int potential) { return candidate % potential == 0; }  public List getFactors() { final List lowerFactors = range(1, (int) round(sqrt(candidate) + 1)) .filter(new F() { public Boolean f(final Integer i) { return isFactor(i); } }); return lowerFactors.append(lowerFactors.map(new F() { 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() , например). Наличие мемоизации формирует существенные различия в легкости ипользования и реализации кеширования. В следующей части, я буду исследовать ленивость более подробно в различных языках и фреймворках.



 

 [Перевод] Как я читаю книги по программированию.
 IBM Rational Test Workbench.
 Oracle представляет серверы SPARC на базе самого быстрого микропроцессора в мире.
 jRIApp - новый HTML5 фреймворк для создания интернет бизнес приложений.
 Crystal Enterprise. Введение в Smart Reporting Technology.


Главная »  Java 

© 2018 Team.Furia.Ru.
Частичное копирование материалов разрешено.