Делать редукторы (в Clojure) решения проблемы масштабирования накопление выражения производится, изложенных Гаем Стилом?

В своем выступлении будущее Клоджюра Бодиль делает следующее заявление:

Гай Стил выступил с докладом в ICFP под названиеморганизация функционального кода для параллельного выполнения (или, foldl и foldr считаются слегка вредными) (такжев ACM ).

В нем Гай Стил утверждает на слайде 70:

Как только вы скажете " во-первых, SUM = 0", вас обольют из шланга. Аккумуляторы вредны для параллелизма. обратите внимание, что foldl и foldr, хотя они и функциональны, в основе своей являются накопительными.

Что довольно интересно. Итак, Бодил говорит, что Гай Стил вызывает проблему. Затем она утверждала, что Рич обратился к ней с помощьюредукторов (ипреобразователей , которые являются продолжением этой линии мышления). В преобразователи говорят в 16:11 мы видим, как Рич называет некоторые конкретные статьи о foldr.

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

Мой вопрос - Была ли Бодиль права? Рич решил проблему, поставленную Гаем Стилом? делать редукторы (в Clojure) решения проблемы масштабирования накопление выражения производится, изложенных Гаем Стилом?
2 9
clojure parallel-processing reducers

2 ответа:

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

foldr и foldl Возьмите один аргумент функции, который применяется к каждому члену коллекции (вместе со значением аккумулятора) по очереди. Как говорит Стил, они внутренне последовательны (именно поэтому имеет смысл иметь "левый" и "правый" варианты). Функция клоджюра clojure.core/reduce работает и так.

clojure.core.reducers/fold, с другой стороны, принимаетдва аргумента функции , функцию сокращения и функцию объединения. Коллекция делится на блоки, каждый из которых сокращается с помощью функции уменьшения, и эти результаты затем объединяются с помощью функции объединения. Графически это выглядит так:

Сложите Дерево

(эта диаграмма взята из моей книги семь моделей параллелизма за семь недель , которая включает раздел о Редукторы).

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

При использовании одной функции как для сокращения, так и для комбинирования, clojure.core.reducers/fold даст те же результаты, что и последовательная складка, если и только если функция сокращения/комбинирования ассоциативна.

10

Оригинальный пост в блоге о редукторах (редукторы - библиотека и модель для обработки коллекции ) вводит функцию fold под разделомПростота-это возможность .

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

Структуры данных Clojure используют преимущества возможный паралеллизм.

Он делает это, когда коллекция поддается параллельному разбиению. Идеальными кандидатами являются структуры данных, построенные из деревьев. Векторы в Clojure а карты-это деревья, и имеют параллельные реализации на основе сгиба на раздвоенной раме.

И если коллекция является последовательностью, то применяется старая добрая функция reduce.

Что делать, если базовая коллекция не поддается обработке (например, является последовательность)? сложите просто переходит в сокращение, производя то же самое семантический, если не физический, результат.

2