Решают ли редукторы (в Clojure) проблему накопления папок с масштабированием, описанную Гаем Стилом?

В своем выступлении Будущее Clojure Бодил делает следующее заявление:

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

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

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

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

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

Мой вопрос в том, был ли Бодил прав? Рич решил проблему, поставленную Гаем Стилом? Решают ли редукторы (в Clojure) проблему накопления папок с масштабированием, описанную Гаем Стилом?


reducers parallel-processing clojure fold
person hawkeye    schedule 08.12.2014    source источник
comment
Вы можете удалить тег clojure, если считаете, что у вопроса более широкая аудитория.   -  person leppie    schedule 08.12.2014
comment
Имейте в виду, что в настоящее время (clojure 1.7.0-alpha4) преобразователи не имеют параллельной реализации, вызывающей fork-join, как это делают редукторы. Тем не менее, параллельные преобразователи все еще находятся в разработке для будущих версий.   -  person NielsK    schedule 08.12.2014

Ответы (2)


arrow_upward
10
arrow_downward

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

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

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

Складное дерево

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

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

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

person Paul Butcher    schedule 08.12.2014

arrow_upward
2
arrow_downward

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

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

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

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

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

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

person juan.facorro    schedule 08.12.2014