Статьи

Запоминание Groovy функций с помощью GPars

Январь 29, 2019

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

Чтобы увидеть конкретный вариант использования, ознакомьтесь с этим кратким примером в Groovy, используя экспериментальную реализацию GPars memoize : 

GParsPool.withPool {
    def urls = ['http://www.dzone.com', 'http://www.theserverside.com', 'http://www.infoq.com']
    Closure download = {url ->
        println "Downloading $url"
        url.toURL().text.toUpperCase()
    }
    Closure cachingDownload = download.memoize()

    println 'Groovy sites today: ' + urls.findAllParallel {url -> cachingDownload(url).contains('GROOVY')}
    println 'Grails sites today: ' + urls.findAllParallel {url -> cachingDownload(url).contains('GRAILS')}
    println 'Griffon sites today: ' + urls.findAllParallel {url -> cachingDownload(url).contains('GRIFFON')}
    println 'Gradle sites today: ' + urls.findAllParallel {url -> cachingDownload(url).contains('GRADLE')}
    println 'Concurrency sites today: ' + urls.findAllParallel {url -> cachingDownload(url).contains('CONCURRENCY')}
    println 'GPars sites today: ' + urls.findAllParallel {url -> cachingDownload(url).contains('GPARS')}
}

Замыкания на уведомления улучшаются внутри блоков GParsPool.withPool () с помощью функции memoize () , которая возвращает новое закрытие, оборачивающее исходное закрытие кешем.
В этом примере мы вызываем функцию cachingDownload в нескольких местах кода, однако каждый уникальный URL-адрес загружается только один раз — в первый раз, когда это необходимо. Значения затем кэшируются и доступны для последующих вызовов. А также для всех потоков , независимо от того, какой поток изначально был первым с запросом на загрузку для определенного URL и должен был обрабатывать фактические вычисления / загрузки.
Итак, чтобы завершить, запомните функцию защиты экрана кешем прошлых возвращаемых значений.

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

Снимая

Скорее всего, вы, будучи разработчиками, уже видели любой из множества вариантов генераторов чисел Фибоначчи. Здесь я показываю наименее многословную и наименее производительную, чисто рекурсивную реализацию:

Closure fib = {n -> n > 1 ? call(n - 1) + call(n - 2) : n}

Это не только неэффективно, это невероятно неэффективно , я бы сказал, экспоненциально. Попробуйте запустить функцию, чтобы получить приблизительно 40-е число Фибоначчи, и все готово для дня.

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

Посмотрите модифицированную версию моего генератора Фибоначчи, на этот раз с линейной сложностью:

Closure fib
fib = {n -> n > 1 ? fib(n - 1) + fib(n - 2) : n}.memoize()

Выберите любое число, и вы получите результат практически мгновенно . И последующие вызовы функции fib будут использовать значения, рассчитанные по более ранним вызовам . Единственное изменение? Функция fib теперь запоминается , это означает, что она хранит прозрачный кэш вычисленных значений. Концепция memoize позволила мне оптимизировать мой код, не отказываясь от красоты оригинальной рекурсивной функции.
Теперь, я уверен, что функциональные парни могут громко смеяться надо мной, так как это то, что они делали целую вечность, но мой функционально-императивный ум был взволнован, увидев элегантность концепции.

Сократить жир

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

Closure fib
fib = {n -> n > 1 ? fib(n - 1) + fib(n - 2) : n}.memoizeAtMost(2)

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

Вывод

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

Хорошие практические новости — если вы хотите поэкспериментировать с
памяткой в Groovy, посмотрите
образцы памятки GPars , возьмите недавний
снимок GPars 0.11 и не забудьте
отправить нам свой отзыв . Мне особенно любопытно услышать идеи о доменах или алгоритмах, в которых памятка может быть полезной.

 

С http://www.jroller.com/vaclav/entry/memoize_groovy_functions_with_gpars

36
Share: