Clojure: уменьшить или применить

126

Я понимаю концептуальную разницу между reduceи apply:

(reduce + (list 1 2 3 4 5))
; translates to: (+ (+ (+ (+ 1 2) 3) 4) 5)

(apply + (list 1 2 3 4 5))
; translates to: (+ 1 2 3 4 5)

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

dbyrne
источник

Ответы:

125

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

+сам реализован в терминах reduceдля случая переменной арности (более 2 аргументов). В самом деле, это кажется чрезвычайно разумным способом "по умолчанию" для любой ассоциативной функции переменной арности: reduceимеет потенциал для выполнения некоторых оптимизаций для ускорения работы - возможно, с помощью чего-то вроде internal-reduceновинки 1.2, недавно отключенной в master, но надеюсь, что в будущем они будут повторно введены - что было бы глупо повторять в каждой функции, которая могла бы получить от них пользу в случае vararg. В таких распространенных случаях applyэто просто добавит немного накладных расходов. (Обратите внимание, что это не повод для беспокойства.)

С другой стороны, сложная функция может использовать преимущества некоторых возможностей оптимизации, которые недостаточно общие, чтобы быть встроенными reduce; тогда applyвы сможете воспользоваться ими, а на reduceсамом деле замедлить работу. Хороший пример реализации последнего сценария на практике str: он использует для StringBuilderвнутренних целей и значительно выиграет от использования applyвместо reduce.

Итак, я бы сказал, используйте, applyесли сомневаетесь; и если вы знаете, что это не дает вам ничего лишнего reduce(и что это вряд ли изменится в ближайшее время), не стесняйтесь использовать, reduceчтобы сбрить эти крошечные ненужные накладные расходы, если вам это нравится.

Михал Марчик
источник
Отличный ответ. Кстати, почему бы не включить встроенную sumфункцию, как в haskell? Похоже на довольно распространенную операцию.
dbyrne 01
17
Спасибо, рад это слышать! Re: sumЯ бы сказал, что в Clojure есть эта функция, она вызывается +и с ней можно использовать apply. :-) Если серьезно, то я думаю, что в Лиспе в целом, если предусмотрена функция с переменным числом аргументов, она обычно не сопровождается оболочкой, работающей с коллекциями - это то, что вы используете applyдля этого (или reduce, если вы знаете, что это имеет больше смысла).
Michał Marczyk
6
Забавно, мой совет прямо противоположный: reduceкогда сомневаешься, applyкогда точно знаешь, что есть оптимизация. reduceКонтракт является более точным и, следовательно, более подвержен общей оптимизации. applyявляется более расплывчатым и поэтому может быть оптимизирован только в индивидуальном порядке. strи concatявляются двумя распространенными исключениями.
cgrand
1
@cgrand Перефразируя мое логическое обоснование , я мог бы предположить, что для функций, которые эквивалентны по результатам reduceи applyэквивалентны, я бы ожидал, что автор рассматриваемой функции знает, как лучше всего оптимизировать свою вариативную перегрузку, и просто реализовать ее с точки зрения reduceif это действительно то, что имеет наибольший смысл (такая возможность, безусловно, всегда доступна и является в высшей степени разумным вариантом по умолчанию). Я действительно понимаю, откуда вы пришли, reduceэто определенно центральное место в истории производительности Clojure (и все чаще), очень оптимизировано и очень четко определено.
Michał Marczyk
51

Для новичков, смотрящих на этот ответ,
будьте осторожны, они не совпадают:

(apply hash-map [:a 5 :b 6])
;= {:a 5, :b 6}
(reduce hash-map [:a 5 :b 6])
;= {{{:a 5} :b} 6}
Давид Рз Айяла
источник
21

Мнения разнятся - в большом мире Lisp reduceон определенно считается более идиоматичным. Во-первых, уже обсуждались различные вопросы. Кроме того, некоторые компиляторы Common Lisp фактически не работают при applyприменении к очень длинным спискам из-за того, как они обрабатывают списки аргументов.

Однако среди клоюристов моего круга использование applyв этом случае кажется более распространенным. Мне легче грокнуть, и я тоже предпочитаю это.

drcode
источник
19

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

ГРАММ__
источник
9

Обычно я предпочитаю reduce при работе с любым типом коллекции - он работает хорошо и в целом является довольно полезной функцией.

Основная причина, по которой я бы использовал apply, заключается в том, что параметры означают разные вещи в разных положениях или если у вас есть пара начальных параметров, но вы хотите получить остальное из коллекции, например

(apply + 1 2 other-number-list)
mikera
источник
9

В этом конкретном случае я предпочитаю, reduceпотому что он более читабелен : когда я читаю

(reduce + some-numbers)

Я сразу понимаю, что вы превращаете последовательность в значение.

При этом applyя должен подумать, какая функция применяется: «а, это +функция, поэтому я получаю ... одно число». Чуть менее простой.

mascip
источник
7

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

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

cum-val[i+1] = F( cum-val[i], input-val[i] )    ; please forgive the java-like syntax!

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

vals = [ val1 val2 val3 ]
(some-fn (vals 0) (vals 1) (vals 2))

мы можем сказать:

(apply some-fn vals)

и он преобразуется в эквивалент:

(some-fn val1 val2 val3)

Таким образом, использование «применить» похоже на «удаление скобок» вокруг последовательности.

Алан Томпсон
источник
4

Немного поздно в теме, но после прочтения этого примера я провел простой эксперимент. Вот результат моего ответа, я просто не могу ничего вывести из ответа, но, похоже, между сокращением и применением есть своего рода кеширование.

user=> (time (reduce + (range 1e3)))
"Elapsed time: 5.543 msecs"
499500
user=> (time (apply + (range 1e3))) 
"Elapsed time: 5.263 msecs"
499500
user=> (time (apply + (range 1e4)))
"Elapsed time: 19.721 msecs"
49995000
user=> (time (reduce + (range 1e4)))
"Elapsed time: 1.409 msecs"
49995000
user=> (time (reduce + (range 1e5)))
"Elapsed time: 17.524 msecs"
4999950000
user=> (time (apply + (range 1e5)))
"Elapsed time: 11.548 msecs"
4999950000

Глядя на исходный код clojure, уменьшите его довольно чистую рекурсию с помощью internal-reduce, но ничего не нашел по реализации apply. Реализация + в Clojure для внутреннего вызова reduce, которая кешируется с помощью repl, что, кажется, объясняет 4-й вызов. Может кто-нибудь прояснить, что здесь происходит на самом деле?

Рохит
источник
Я знаю, что предпочитаю сокращать, когда смогу :)
rohit
2
Вы не должны помещать rangeзвонок внутрь timeформы. Поместите его снаружи, чтобы устранить помехи при построении последовательности. В моем случае reduceстабильно превосходит apply.
Давыжу 05
3

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

(apply + 1 2 3 [3 4])
=> 13
(reduce + 1 2 3 [3 4])
ArityException Wrong number of args (5) passed to: core/reduce  clojure.lang.AFn.throwArity (AFn.java:429)
Айра
источник