Изучение функции складывания

СТАТЬЯ

Изучение функции складывания

Из Стандартной библиотеки Clojure Ренцо Боргатти
___________________________________________________________________

Скидка 37% на Стандартная библиотека Clojure. Просто введите код fccborgatti в поле кода скидки при оформлении заказа на manning.com.
___________________________________________________________________

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

Функция складывания

function since 1.5

Листинг 1. Параллельная обработка, сокращение-комбинирование, вилка-соединение

(fold
   ([reducef coll])
   ([combinef reducef coll] )
   ([n combinef reducef coll]))

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

(require '[clojure.core.reducers :as r])  ❶
 (r/fold + (into [] (range 1000000)))      ❷
 ;; 499999500000

❶ Редукторы входят в комплект Clojure, но они должны быть необходимы перед использованием.

❷ fold разбивает вектор из миллиона элементов на фрагменты примерно по 512 в каждом (по умолчанию). Затем фрагменты отправляются в пул потоков fork-join для параллельного выполнения, где они сокращаются на + и снова объединяются на +

fold предлагает параллелизм, основанный на принципе «разделяй и властвуй»: создаются блоки работы, и вычисления выполняются параллельно, в то же время завершенные задачи объединяются в окончательный результат. Следующая диаграмма иллюстрирует путь коллекции через операцию сворачивания:

Важный механизм, который реализует fold (диаграмма не может ясно показать это, не сбивая с толку), - это кража работы. После того, как fold отправит фрагмент в платформу fork-join Java, каждый рабочий может разделить работу на более мелкие части, создавая смесь меньших и больших частей. Находясь бесплатно, рабочий может украсть работу у другого - модель Fork-Join для параллельных вычислений - сложная тема, которую нельзя проиллюстрировать в этой статье. Если вы хотите узнать больше, прочтите следующий документ Дуга Ли, автора Fork-join на Java: http://gee.cs.oswego.edu/dl/papers/fj.pdf. Кража работы улучшается по сравнению с базовым объединением потоков, например, для менее предсказуемых заданий, когда один поток неожиданно загружен.

Контракт

ВХОД

Контракт отличается в зависимости от наличия необязательного «combf» и того, является ли входная коллекция картой.

«Reducef» - обязательный аргумент. Это должна быть функция, поддерживающая как минимум два аргумента (и вызов нулевого аргумента, если не указано «combf»). Вызов двух аргументов реализует канонический контракт сокращения, получающий аккумулятор и текущий элемент. Вызов нулевых аргументов используется для установки начального числа для результата аналогично аргументу «init» в reduce. Когда не указан «combf», 0-арность вызывается один раз для каждого фрагмента, чтобы установить начальное значение для сокращения. «Reducef» также используется вместо «combf», когда функция комбинирования не предусмотрена. В этом случае «reducef» должно быть ассоциативным, так как фрагменты могут быть повторно объединены в любом порядке.
«Combinef» является необязательным, и когда он присутствует, он должен разрешать вызов с нулевым и двумя аргументами. «Combinef» должен быть ассоциативным, чтобы можно было комбинировать фрагменты в любом порядке. Вызов с двумя аргументами используется для объединения фрагментов обратно в окончательный результат. Когда присутствует «combf», ноль арности «reducef» никогда не вызывается, а вместо этого вызывается «combf».
«N» - это приблизительный размер фрагмента, на который разбивается входная коллекция «coll». По умолчанию 512.
«Coll» может иметь любой последовательный тип, пустой или nil. Если coll не является объектом vector, hash-map или clojure.core.reducers.Cat (подробнее см. r/foldcat), fold возвращается к последовательному reduce вместо параллельного. Когда «coll» hash-map, оба «reducef» и «combf» вызываются с тремя аргументами вместо двух, согласно контракту «reduce-kv».

ЗАМЕТНЫЕ ИСКЛЮЧЕНИЯ

IllegalArgumentException поднимается для нескольких неподдерживаемых типов коллекций. Это могло произойти, например, когда «coll» - временная или популярная коллекция Java, такая как java.util.HashMap. Существуют веские причины для исключения небезопасных для потоков изменяемых коллекций, которые в противном случае подлежат параллелизму. Другие потокобезопасные коллекции Java (например, java.util.concurrent.ConcurrentHashMap) можно сделать «складываемыми», как мы собираемся изучить в расширенном примере).

ВЫВОД

возвращает результат вызова (reducef) или (combinef) без аргументов, когда «coll» равно nil или содержит один элемент.
возвращает результат применения «reducef» к следующему элементу в коллекции. Затем снова «reducef» применяется к предыдущему результату и следующему элементу, вплоть до последнего элемента в коллекции. Если присутствует «combf», то частичные накопления объединяются обратно с помощью «combf». Возвращается последний результат применения «reducef» (или «combf»).

Примеры

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

(require '[clojure.core.reducers :as r])
  
 (defn count-occurrences [coll]
   (r/fold
     (r/monoid #(merge-with + %1 %2) (constantly {}))  ❶
     (fn [m [k cnt]] (assoc m k (+ cnt (get m k 0))))  ❷
     (r/map #(vector % 1) (into [] coll))))            ❸
  
 (defn word-count [s]
   (count-occurrences (.split #"\s+" s)))
  
 (def war-and-peace "http://www.gutenberg.org/files/2600/2600-0.txt")
 (def book (slurp war-and-peace))
  
 (def freqs (word-count book))
 (freqs "Andrew")
 ;; 700

❶ <r/monoid - вспомогательная функция для создания функции, подходящей для "combf". Первый аргумент для r/monoid - это функция слияния, которая используется при объединении частей. Мы хотим просуммировать количество одного и того же слова, что мы можем сделать с помощью «слияния с».

❷ «reducef» необходимо assoc каждое слово в карте результатов «m». Возможны два случая: слово уже существует и счетчик увеличивается, или слово не существует, и в качестве начального счетчика используется ноль.

❸ «coll» должен быть vector, чтобы входные данные преобразовывались с помощью в. Преобразование каждой строки включает создание кортежа (вектора из двух элементов) со словом и номером один. Для этого мы используем r / map из библиотеки reducer, и преобразование отложено до параллельного выполнения.

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

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

(defn group-by-initial [freqs]                           ❶
   (r/fold
     (r/monoid #(merge-with into %1 %2) (constantly {}))  ❷
     (fn [m k v]                                          ❸
       (let [c (Character/toLowerCase (first k))]
         (assoc m c (conj (get m c []) v))))
     freqs))
  
 (defn update-vals [m f]                                  ❹
   (reduce-kv (fn [m k v] (assoc m k (f v))) {} m))
  
 (defn avg-by-initial [by-initial]                        ❺
   (update-vals by-initial #(/ (reduce + 0. %) (count %))))
  
 (defn most-frequent-by-initial [freqs]                   ❻
   (->> freqs
     group-by-initial
     avg-by-initial
     (sort-by second >)
     (take 5)))
  
 (most-frequent-by-initial freqs)                         ❼
  
 ;; ([\t 41.06891634980989]
 ;;  [\o 33.68537074148296]
 ;;  [\h 28.92705882352941]
 ;;  [\w 26.61111111111111]
 ;;  [\a 26.54355400696864])

❶ group-by-initial использует fold ожидание хеш-карты от строк к числам. На выходе получается гораздо меньшая карта букв в векторы. Количество клавиш на этой карте равно количеству букв в алфавите (при условии, что текст достаточно большой и мы отфильтровали числа и символы). Буква «а» на этой карте содержит что-то вроде [700, 389, 23, 33, 44], которые являются повторениями каждого слова в книге, начинающегося с буквы «а».

❷ Функция комбинирования собрана с использованием r/monoid. Начальным значением для каждой операции сокращения является пустая карта {}. Частичные результаты объединяются путем слияния их векторных значений в один вектор.

❸ Функция сокращения принимает три параметра: карту частичных результатов «m», текущий ключ «k» и текущее значение «v». Точно так же, чтобы подсчитать частоту слов, мы извлекаем потенциально существующий ключ (используя пустой вектор в качестве значения по умолчанию) и объединяем его в вектор значений «v». Ключ - это начальная буква каждого слова, найденного во входной карте.

❹ update-vals принимает карту и функцию «f» одного параметра. Затем он применяет «f» к каждому значению на карте, используя «reduce-kv».

❺ avg-by-initial замените каждое значение вектора на карте средним значением найденных в нем чисел.

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

❼ freqs - результат подсчета слов из предыдущего примера.

После выполнения most-frequent-by-initial мы видим, что буква «t» в среднем чаще всего используется в начале слова, за ней следуют «o», «h», «w» и «a». Это указывает на то, что слова, начинающиеся с буквы «т», в среднем чаще всего повторяются в моей книге (хотя некоторые другие слова, не начинающиеся с «т», могут быть в абсолютном смысле наиболее частыми).

(import 'java.util.concurrent.ConcurrentHashMap)
 (require '[clojure.core.reducers :as r])
  
 (defn pi [n]                         ❶
   "Pi Leibniz formula approx."
   (->> (range)
        (filter odd?)
        (take n)
        (map / (cycle [1 -1]))
        (reduce +)
        (* 4.0)))
  
 (defn large-map [i j]                ❷
   (into {}
     (map vector (range i) (repeat j))))
  
 (defn combinef [init]                ❸
   (fn
     ([] init)
     ([m _] m)))
  
 (defn reducef [^java.util.Map m k]   ❹
   (doto m
     (.put k (pi (.get m k)))))
  
 (def a-large-map (ConcurrentHashMap. (large-map 100000 100)))
  
 (dorun                               ❺
   (r/fold
     (combinef a-large-map)
     reducef
     a-large-map))
 ;; IllegalArgumentException No implementation of method: :kv-reduce

❶ pi вычисляет приближенное значение π. Чем больше число «n», тем лучше приближение. Относительно небольшие числа порядка сотен требуют дорогостоящих вычислений.

❷ large-map служит цели создания большого ConcurrentHashMap, который будет использоваться в нашем примере. Ключи карты являются увеличивающимися целыми числами, хотя значения всегда одинаковы.

❸ combinef без аргументов возвращает базовую карту, которую все потоки должны обновлять одновременно. Конкатенация не требуется, поскольку обновления происходят в одном изменяемом экземпляре ConcurrentHashMap. 'Combinef' с двумя аргументами возвращает один из двух (это один и тот же объект). combinef можно эффективно заменить на (постоянно м).

❹ reducef заменяет существующий ключ вычисленным «пи». Обратите внимание на использование «doto», которое разрешает операции Java, такие как .put, который в противном случае возвращает карте nil.

❺ fold неудачно, так как он ищет подходящую реализацию reduce-kv, но не найден.

Мы столкнулись с первой проблемой: fold не удается из-за отсутствия двух полиморфных отправок: fold не имеет конкретной параллельной версии для java.util.concurrent.ConcurrentHashMap, и он направляет вызов на reduce-kv. reduce-kv также не работает, потому что есть реализация для Clojure hash-map, но не для Java ConcurrentHashMap. В качестве первого шага мы могли бы предоставить reduce-kv версию, которая устраняет ошибку, но этого решения недостаточно для параллельного выполнения преобразований:

(extend-protocol                   ❶
   clojure.core.protocols/IKVReduce
   java.util.concurrent.ConcurrentHashMap
   (kv-reduce [m f _]
     (reduce (fn [amap [k v]] (f amap k)) m m)))
  
 (time                              ❷
   (dorun
     (r/fold
       (combinef a-large-map)
       reducef
       a-large-map)))
 ;; "Elapsed time: 41113.49182 msecs"
  
 (.get a-large-map 8190)            ❸
 ;; 3.131592903558553

❶ Мы можем добавить тип к протоколу, используя протокол расширения. Нашему reduce-kv это значение не требуется, потому что мы изменяем Java ConcurrentHashMap на месте.

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

❸ Чтобы быть уверенным, что большая карта действительно обновлена, мы проверяем случайный ключ «8190». Как и ожидалось, он содержит приблизительное значение «пи».

Хотя мы предоставили подходящую reduce-kv реализацию, java.util.concurrent.ConcurrentHashMap еще не имеет подходящей параллели fold. Как и в случае с reduce-kv, нам нужно обеспечить реализацию fold, расширив правильный протокол. Идея состоит в том, чтобы разделить набор ключей вместо карты, и каждый поток работает параллельно для обработки данного подмножества:

(defn foldmap [m n combinef reducef]       ❶
   (#'r/foldvec
     (into [] (keys m))
     n
     combinef
     reducef))
  
 (extend-protocol r/CollFold                ❷
   java.util.concurrent.ConcurrentHashMap
   (coll-fold
     [m n combinef reducef]
     (foldmap m n combinef reducef)))
  
 (def a-large-map (ConcurrentHashMap. (large-map 100000 100)))
  
 (time                                      ❸
   (dorun
     (into {}
       (r/fold
         (combinef a-large-map)
         reducef
         a-large-map))))
 "Elapsed time: 430.96208 msecs"

❶ foldmap реализует параллельную стратегию для java.util.concurrent.ConcurrentHashMap. Он делегирует foldvec в пространство имен редюсеров с ключами, поступающими из карты, эффективно повторно используя параллелизм векторов.

❷ Мы инструктируем протокол CollFold использовать карту свертки, когда свертка представлена экземпляром java.util.concurrent.HashMap.

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

После расширения протокола CollFold из пространства имен clojure.core.reducers мы видим, что fold эффективно выполняет обновление карты параллельно, последовательно сокращая время выполнения. Для сравнения, это та же операция, выполняемая на постоянном hash-map, который по умолчанию включен параллельно:

(def a-large-map (large-map 100000 100))
  
 (time
   (dorun
     (r/fold
       (r/monoid merge (constantly {}))
       (fn [m k v] (assoc m k (pi v)))
       a-large-map)))
 ;; "Elapsed time: 17977.183154 msecs"  ❶

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

См. также

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

Соображения производительности и детали реализации

= ›O(n) линейный

fold реализован для рекурсивного разделения коллекции на фрагменты и отправки их в структуру fork-join, эффективно строя дерево в O(log n) passes. Однако каждый фрагмент подвергается линейному сокращению, которое доминирует при логарифмическом обходе: чем больше исходная коллекция, тем больше вызовов функции сокращения, что в целом делает ее линейным поведением. Линейность fold вряд ли будет иметь значение при анализе производительности, поскольку имеют место другие факторы, такие как параллельное выполнение ресурсоемких вычислительных задач.

Оркестровка параллельных потоков требует затрат, которые следует учитывать при параллельном выполнении операций: как и pmap, fold оптимально работает для нетривиальных преобразований потенциально большого набора данных. Например, следующая простая операция приводит к снижению производительности при параллельном выполнении:

(require '[criterium.core :refer [quick-bench]])
 (require '[clojure.core.reducers :as r])
  
 (let [not-so-big-data (into [] (range 1000))]
   (quick-bench (reduce + not-so-big-data)))
 ;; Execution time mean : 11.481952 µs
  
 (let [not-so-big-data (into [] (range 1000))]
   (quick-bench (r/fold + not-so-big-data)))
 ;; Execution time mean : 32.683242 µs

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

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

Теперь вы хорошо понимаете, как работает функция складывания!
___________________________________________________________________

Если вы хотите узнать больше о книге, посмотрите ее в liveBook здесь и посмотрите эту колоду слайдов.
___________________________________________________________________

Об авторе:
Ренцо Боргатти - инженер-программист с более чем 15-летним опытом работы в этой области. Ренцо работал с Java, Ruby и Objective-C, прежде чем несколько лет назад открыл для себя Clojure и функциональное программирование, увлечение, которое быстро превратилось в профессиональную работу. Он часто выступает на группах пользователей и на конференциях.

Первоначально опубликовано на freecontent.manning.com.

Изучение функции складывания

СТАТЬЯ