Функциональное мышление: Часть 3. Функциональные возможности Groovy

Мемоизация и кэширование

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

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

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



01.08.2012

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

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

Чем больше низкоуровневых аспектов реализации берет на себя язык программирования, тем меньше у вас остается возможностей для внесения ошибок и чрезмерного усложнения программы. (Классическим примером данного подхода является "сборка мусора" и управление памятью в виртуальной Java-машине. Как я подчеркивал в предыдущих статьях, одна из характеристик функциональных языков и динамических языков с функциональными возможностями — это то, что они позволяют выборочно передавать языку или среде исполнения управление низкоуровневыми аспектами реализации. В статье "Функциональные возможности Groovy. Часть 1" я показывал, как рекурсия избавляет разработчика от необходимости поддержки состояния. В этой статье я применю подобный подход для кэширования в Groovy.

Кэширование является широко распространенным требованием к приложениям, но зачастую представляет собой источник трудноуловимых ошибок. В объектно-ориентированных языках кэширование обычно происходит на уровне объектов с данными, и разработчики вынуждены управлять им самостоятельно. Во многих функциональных языках кэширование уже встроено на уровне функций с помощью механизма мемоизации (memoization). Мемоизация — это специальная оптимизационная методика, которая позволяет увеличить скорость выполнения компьютерных программ. Данная методика заключается в том, чтобы исключить повторное вычисление результатов, полученных при предыдущих вызовах. В этой статье я исследую два сценария кэширования, подходящих для функций: внутри класса и с помощью внешних методов. Я также представлю две реализации кэширования: с "ручным" управлением состоянием и с помощью мемоизации.

Кэширование на уровне метода

Если вы уже читали статьи из этой серии, то знакомы с проблемой классификации чисел, рассматривавшейся в первой статье. Отправной точкой для этой статьи послужит Groovy-версия программы из предыдущей статьи, приведенная в листинге 1.

Листинг 1. Классификатор чисел на языке Groovy
class Classifier {
  def static isFactor(number, potential) {
    number % potential == 0;
  }

  def static factorsOf(number) {
    (1..number).findAll { i -> isFactor(number, i) }
  }

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

  def static isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def static isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def static isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }
}

Внутреннюю реализацию метода factorsOf() в листинге 1 можно оптимизировать, если воспользоваться приёмами, описанными в статье "Функциональное мышление. Часть 2", но в данный момент я более заинтересован в кэшировании на уровне функции.

Так как класс Сlassifier определяет тип числа, стандартным сценарием его использования будет последовательность вызовов из различных методов с целью классификации одного и того же числа, как показано в листинге 2.

Листинг 2. Стандартный сценария использования программы-классификатора
//...
if (Classifier.isPerfect(n)) print '!'
else if (Classifier.isAbundant(n)) print '+'
else if (Classifier.isDeficient(n)) print '-'
//...

В текущей реализации при каждом вызове метода для классификации числа я должен заново вычислить сумму всех делителей. Это пример кэширования внутри класса: при обычном использовании метод sumOfFactors() вызывается несколько раз для одного и того же числа. Но в данном стандартном сценарии подобный подход оказывается неэффективным.

Кэширование суммы

Один из способов повысить эффективность кода — это воспользоваться результатами уже выполненной трудоемкой задачи. Так как вычисление суммы делителей — это сложная задача, то я хотел бы выполнять её только один раз для каждого числа. Для этого мне потребуется создать кэш для хранения вычислений, как показано в листинге 3.

Листинг 3. Кэширование суммы
class ClassifierCachedSum {
  private sumCache

  ClassifierCachedSum() {
    sumCache = [:]
  }

  def sumOfFactors(number) {
    if (sumCache.containsKey(number))
      return sumCache[number]
    else {
      def sum = factorsOf(number).inject(0, {i, j -> i + j})
      sumCache.putAt(number, sum)
      return sum
    }
  }
  //... остальной код остается без изменений
}

В листинге 3 в конструкторе создается хеш-таблица sumCache. В методе sumOfFactors() я проверяю, есть ли уже в кэше сумма для переданного параметра, и если есть, возвращаю её. В противном случае я выполняю сложную операцию по вычислению суммы и перед возвращением сохраняю её в кэше.

Хотя код получился более сложным, результат говорит сам за себя. Я пропустил все примеры через набор unit-тестов, основанных на шаблоне, приведенном в листинге 4.

Листинг 4. Тесты
class ClassifierTest {
  def final TEST_NUMBER_MAX = 1000
  def classifier = new ClassifierCachedSum()

  @Test
  void classifier_many_checks_without_caching() {
    print "Без оптимизации:              "
    def start = System.currentTimeMillis()
    (1..TEST_NUMBER_MAX).each {n ->
      if (Classifier.isPerfect(n)) print '!'
      else if (Classifier.isAbundant(n)) print '+'
      else if (Classifier.isDeficient(n)) print '-'
    }
    println "\n\t ${System.currentTimeMillis() - start} ms"
    print "Без оптимизации (второй запуск):        "
    start = System.currentTimeMillis()
    (1..TEST_NUMBER_MAX).each {n ->
      if (Classifier.isPerfect(n)) print '!'
      else if (Classifier.isAbundant(n)) print '+'
      else if (Classifier.isDeficient(n)) print '-'
    }
    println "\n\t ${System.currentTimeMillis() - start} ms"
  }

Результат запуска тестов из листинга 4 свидетельствует о том, что кэширование действительно помогает, как показано в листинге 5:

Листинг 5. Результат тестирования на производительность примера с кэшированием суммы
Тестирование диапазона чисел от 1 до 1000
Без оптимизации:             
	 577 ms
Без оптимизации (второй запуск):       
	 280 ms
С кэшированием суммы:                
	 600 ms
С кэшированием суммы (второй запуск):      
	 50 ms

Из листинга 5 видно, что неоптимизированная версия из листинга 1 в первый раз выполняется за 577 мс, в то время как версия с кэшированием в первый раз выполняется за 600 мс. В этих двух случаях разница получается незначительной. Однако второй запуск неоптимизированной версии проходит за 280 мс. Разницу между первой и второй попыткой можно объяснить факторами среды, например, «сборкой мусора». Повторный запуск версии с кэшированием выполняется значительно быстрее, занимая всего 50 мс. При повторном запуске все значения уже будут помещены в кэш, и на самом деле я уже измеряю скорость чтения из кэша. При первом запуске разница между неоптимизированной и кэшированной версией незначительна, но она становится заметной при втором запуске. Это пример внешнего кэширования: готовые результаты доступны всем, кто вызывает код, поэтому повторный запуск проходит очень быстро.

Кэширование суммы обеспечивает прирост производительности, но требует определенных компромиссов. Класс ClassifierCachedSum не может больше содержать полностью статических методов. Внутренний кэш представляет собой состояние, так что все методы, которые работают с ним, должны быть не статическими, что ведет к дальнейшим последствиям. Я могу попытаться реализовать синглтон-подобное решение (см. раздел "Ресурсы"), но это тоже увеличит сложность. Поскольку я сам управляю кэш-переменной, я должен обеспечить правильность работы (например, с помощью тестов). Хотя кэширование и улучшает производительность, оно имеет побочные эффекты: усложняет структуру кода и его последующее сопровождение (см. раздел "Ресурсы").

Тотальное кэширование

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

Листинг 6. Тотальное кэширование
class ClassifierCached {
  private sumCache, factorCache

  ClassifierCached() {
    sumCache = [:]
    factorCache = [:]
  }

  def sumOfFactors(number) {
    sumCache.containsKey(number) ?
      sumCache[number] :
      sumCache.putAt(number, factorsOf(number).inject(0, {i, j -> i + j}))
  }

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

  def factorsOf(number) {
    factorCache.containsKey(number) ?
      factorCache[number] :
      factorCache.putAt(number, (1..number).findAll { i -> isFactor(number, i) })
  }

  def isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }

}

В классе ClassifierCached в листинге 6 я создаю два кэша: для суммы делителей и самих делителей числа. Вместо сложного синтаксиса из листинга 3 я воспользовался тернарным оператором, принимающим на вход три аргумента, который отлично подошел к данному сценарию. В методе sumOfFactors() я использую условную часть тернарного оператора для проверки наличия числа в кэше. В Groovy последняя строка метода используется в качестве возвращаемого значения, поэтому если значение обнаруживается в кэше, оно возвращается; в противном случае я вычисляю число, сохраняю его в кэш и возвращаю значение. (Метод putAt() в Groovy возвращает значение, добавленное в хеш-таблицу). В листинге 7 представлены результаты запуска обновленной программы.

Листинг 7. Результаты запуска программы с полным кэшированием
Тестирование диапазона чисел от 1 до 1000
Без оптимизации:             
	 577 ms
Без оптимизации (повторный запуск):       
	 280 ms
С кэшированием суммы:                
	 600 ms
С кэшированием суммы (повторный запуск):      
	 50 ms
С полным кэшированием:                    
	 411 ms
С полным кэшированием (повторный запуск):          
	 38 ms

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

Листинг 8. Результаты тестов с классификацией 5000 чисел
Тестирование диапазона чисел от 1 до 5000
Без оптимизации:         
	 6199 ms
Без оптимизации (повторный запуск):   
	 5064 ms
С кэшированием суммы:            
	 5962 ms
С кэшированием суммы (повторный запуск):  
	 93 ms
С полным кэшированием:                
	 6494 ms
С полным кэшированием (повторный запуск):      
	 41 ms

При классификации 10000 чисел картина становится ещё более печальной, как показано в листинге 9.

Листинг 9. Результат попытки классифицировать 10000 чисел
Результаты тестировании диапазона чисел от 1 до 10000
Без оптимизации:
	 43937 ms
Без оптимизации (повторный запуск):
	 39479 ms
С кэшированием суммы:         
	 44109 ms
С кэшированием суммы (повторный запуск):
	 289 ms
С полным кэшированием:              
java.lang.OutOfMemoryError: Java heap space

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


Мемоизация

Функциональное программирование старается ограничить количество "движущихся частей" путем встраивания алгоритмов, пригодных для многократного использования, непосредственно в среду исполнения. Мемоизация – это встроенная функциональность языков программирования, позволяющая автоматически кэшировать повторяющиеся значения, возвращаемые функциями. Иначе говоря, мемоизация автоматически поддерживает код, который я написал в листингах 3 и 6. Многие функциональные языки поддерживают мемоизацию, и Groovy недавно вошел в их число (см. раздел "Ресурсы").

Для мемоизации функции в Groovy её необходимо определить в блоке кода, а затем вызвать метод memoize(), чтобы вернуть функцию, результаты выполнения которой были ранее кэшированы.

Мемоизация суммы

Чтобы реализовать кэширование в методе sumOfFactors(), как это уже было сделано в листинге 3, я применю к этому методу мемоизацию, как показано в листинге 10.

Листинг 10. Мемоизация суммы
class ClassifierMemoizedSum {
  def static isFactor(number, potential) {
    number % potential == 0;
  }

  def static factorsOf(number) {
    (1..number).findAll { i -> isFactor(number, i) }
  }

  def static sumFactors = { number ->
    factorsOf(number).inject(0, {i, j -> i + j})
  }
  def static sumOfFactors = sumFactors.memoize()
 
 // последующий код остается без изменений
}

В листинге 10 я создаю метод sumFactors() в виде блока кода (обратите внимание на оператор = и расположение параметров). Это довольно стандартный метод, и он в принципе мог бы быть извлечен из какой-либо библиотеки. Для мемоизации я присваиваю переменной sumOfFactors значение, полученное при вызове функции memoize() для функции sumFactors().

Результаты запуска версии приложения, использующей мемоизацию, показаны в листинге 11.

Листинг 11. Результаты запуска приложения, в котором используется мемоизация суммы
Тестирование для диапазона чисел от 1 до 1000
Без оптимизации:             
	 577 ms
Без оптимизации (повторный запуск):       
	 280 ms
С кэшированием суммы:                
	 600 ms
С кэшированием суммы (повторный запуск):      
	 50 ms
С полным кэшированием:                    
	 411 ms
С полным кэшированием (повторный запуск):          
	 38 ms
С частичной мемоизацией:        
	 228 ms
С частичной мемоизацией (повторный запуск):  
	 60 ms

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

Тотальная мемоизация

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

Листинг 12. Тотальная мемоизация
class ClassifierMemoized {
  def static dividesBy = { number, potential ->
    number % potential == 0
  }
  def static isFactor = dividesBy.memoize()
//  def static isFactor = dividesBy.memoizeAtMost(100)

  def static factorsOf(number) {

    (1..number).findAll { i -> isFactor.call(number, i) }
  }

  def static sumFactors = { number ->
    factorsOf(number).inject(0, {i, j -> i + j})
  }
  def static sumOfFactors = sumFactors.memoize()

  def static isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def static isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def static isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }
}

Как и в случае с полным кэшированием, показанном в листинге 6, полная мемоизация имеет свои преимущества и недостатки. В листинге 13 показаны результаты классификации 1000 чисел различными способами.

Листинг 13. Результаты классификации 1000 чисел с использованием полной мемоизации
Тестирование диапазона чисел от 1 до 1000
Без оптимизации:             
	 577 ms
Без оптимизации (повторный запуск):       
	 280 ms
С кэшированием суммы:                
	 600 ms
С кэшированием суммы (повторный запуск):      
	 50 ms
С полным кэшированием:                    
	 411 ms
С полным кэшированием (повторный запуск):          
	 38 ms
С частичной мемоизацией:        
	 228 ms
С частичной мемоизацией (повторный запуск):  
	 60 ms
С полной мемоизацией:                  
	 956 ms
С полной мемоизацией (повторный запуск):
	 19 ms

При полной мемоизации первый запуск выполняется медленно, но повторный запуск этой же версии проходит быстрее, чем у остальных, правда, только для небольшого количества чисел. Как и в случае с результатом тестирования императивного кэширования, приведенным в листинге 8, большое количество чисел приводит к существенному снижению производительности. На практике в версии с мемоизацией переполнение памяти происходит при попытке обработать 5000 чисел. Но для императивного подхода требуется обеспечить вычислительные ресурсы, защиту от «перегрузки» и учесть особенности среды исполнения; и всё это - еще один пример сложностей, возникающих при использовании императивных "движущихся частей". В случае же с мемоизацией оптимизация происходит на уровне функции. Рассмотрим пример тестирования программ с поддержкой мемоизации и без неё, приведенный в листинге 14.

Листинг 14. Тестирование усовершенствованной программы с поддержкой мемоизации.
Тестирование диапазона чисел от 1 до 10000
Без оптимизации:          
	 41909 ms
Без оптимизации (повторный запуск):    
	 22398 ms
С мемоизацией:               
	 55685 ms
С мемоизацией(повторный запуск)           
	 98 ms

Мне удалось добиться результатов, показанных в листинге 14, за счет вызова метода memoizeAtMost(1000) вместо метода memoize(). Как и другие языки с поддержкой мемоизации, Groovy обладает несколькими возможностями, позволяющими оптимизировать получение результатов, которые перечислены в таблице 1.

Таблица 1. Методы для мемоизации, имеющиеся в Groovy
МетодОписание
memoize()создание кэшированной версии замыкания
memoizeAtMost()создание кэшированной версии замыкания с ограниченным максимальным размером кэша
memoizeAtLeast()создание кэшированной версии замыкания с автоматической регулировкой размера кэша и ограниченным минимальным размером кэша
memoizeBetween()создание кэшированной версии замыкания с автоматической регулировкой размера кэша и ограниченными минимальным и максимальным размерами кэша

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


Заключение

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

Ресурсы

Научиться

  • Functional thinking: Functional features in Groovy, Part 3: оригинал статьи (EN).
  • The Productive Programmer (Neal Ford, O'Reilly Media, 2008): новая книга Нила Форда, в которой более подробно рассматриваются некоторые вопросы из данной серии статей.
  • Closure memoization: документ, в котором описывается реализация мемоизации в Groovy, добавленная в версии 1.8.
  • Синглтон: известный шаблон проектирования из каталога книги "банды четырех" Design Patterns, предназначенный для поддержки глобального состояния в объектно-ориентированных языках.
  • Evolutionary architecture and emergent design: Investigating architecture and design: в этой статье обсуждаются вопросы "естественного" и "намеренного" усложнения ПО.
  • Посетите магазин книг, посвященных ИТ-технологиям и различным аспектам программирования.

Получить продукты и технологии

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

Комментарии

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=828641
ArticleTitle=Функциональное мышление: Часть 3. Функциональные возможности Groovy
publish-date=08012012