Clojure: reduzir vs. aplicar

126

Entendo a diferença conceitual entre reducee 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)

No entanto, qual é o clojure mais idiomático? Faz muita diferença de uma maneira ou de outra? Do meu (limitado) teste de desempenho, parece que reduceé um pouco mais rápido.

dbyrne
fonte

Respostas:

125

reducee, applyé claro, são apenas equivalentes (em termos do resultado final retornado) às funções associativas que precisam ver todos os seus argumentos no caso de variável-aridade. Quando eles são equivalentes em termos de resultados, eu diria que applyé sempre perfeitamente idiomático, enquanto reduceé equivalente - e pode raspar uma fração de um piscar de olhos - em muitos casos comuns. O que se segue é minha justificativa para acreditar nisso.

+é implementado em termos de reducepara o caso de variável-arity (mais de 2 argumentos). De fato, esse parece ser um caminho "padrão" imensamente sensato para qualquer função associativa de aridade variável: reducetem o potencial de realizar algumas otimizações para acelerar as coisas - talvez através de algo como internal-reduceuma novidade 1.2 recentemente desativada no master, mas espera-se que seja reintroduzido no futuro - o que seria bobagem replicar em todas as funções que possam se beneficiar delas no caso vararg. Nesses casos comuns, applybasta adicionar um pouco de sobrecarga. (Observe que não é nada para se preocupar.)

Por outro lado, uma função complexa pode tirar proveito de algumas oportunidades de otimização que não são gerais o suficiente para serem incorporadas reduce; então applyvocê pode tirar vantagem disso enquanto reducepode realmente atrasá-lo. Um bom exemplo do último cenário que ocorre na prática é fornecido por str: ele usa um StringBuilderinternamente e se beneficiará significativamente do uso de applye não reduce.

Então, eu diria que use applyquando estiver em dúvida; e se você souber que isso não está comprando nada para você reduce(e que é improvável que isso mude muito em breve), fique à vontade reducepara cortar essa sobrecarga desnecessária e diminuta, se você quiser.

Michał Marczyk
fonte
Ótima resposta. Em uma nota lateral, por que não incluir uma sumfunção interna como no haskell? Parece uma operação bastante comum.
Dbyrne
17
Obrigado, prazer em ouvir isso! Re:, sumeu diria que Clojure tem essa função, é chamado +e você pode usá-lo com apply. :-) Falando sério, acho que no Lisp, em geral, se uma função variável é fornecida, geralmente não é acompanhada por um wrapper operando em coleções - é para isso que você usa apply(ou reduce, se você sabe que faz mais sentido).
Michał Marczyk
6
Engraçado, meu conselho é o contrário: reduceem caso de dúvida, applyquando você tem certeza de que há uma otimização. reduceO contrato é mais preciso e, portanto, mais propenso à otimização geral. applyé mais vago e, portanto, só pode ser otimizado caso a caso. stre concatsão as duas exceções predominantes.
cgrand
1
@cgrand Uma reformulação da minha lógica pode ser mais ou menos a de que, para funções onde reducee applysão equivalentes em termos de resultados, eu esperaria que o autor da função em questão soubesse a melhor forma de otimizar sua sobrecarga variável e implementá-la apenas em termos de reducese é de fato o que faz mais sentido (a opção para fazê-lo certamente está sempre disponível e cria um padrão eminentemente sensível). Eu vejo de onde você é, no entanto, reduceé definitivamente central para a história de desempenho de Clojure (e cada vez mais), muito altamente otimizada e muito claramente especificada.
Michał Marczyk
51

Para iniciantes que olham para esta resposta,
tenha cuidado, eles não são os mesmos:

(apply hash-map [:a 5 :b 6])
;= {:a 5, :b 6}
(reduce hash-map [:a 5 :b 6])
;= {{{:a 5} :b} 6}
David Rz Ayala
fonte
21

As opiniões variam - no mundo maior da Lisp, reduceé definitivamente considerado mais idiomático. Primeiro, há as questões variadas já discutidas. Além disso, alguns compiladores Common Lisp realmente falham quando applyaplicados a listas muito longas, devido à maneira como lidam com listas de argumentos.

Entre os clojuristas do meu círculo, porém, o uso applyneste caso parece mais comum. Acho mais fácil grudar e prefiro também.

drcode
fonte
19

Não faz diferença nesse caso, porque + é um caso especial que pode ser aplicado a qualquer número de argumentos. Reduzir é uma maneira de aplicar uma função que espera um número fixo de argumentos (2) a uma lista arbitrariamente longa de argumentos.

G__
fonte
9

Normalmente, prefiro reduzir ao atuar em qualquer tipo de coleção - ela funciona bem e é uma função bastante útil em geral.

A principal razão pela qual eu aplicaria o apply é se os parâmetros significam coisas diferentes em posições diferentes, ou se você possui alguns parâmetros iniciais, mas deseja obter o restante de uma coleção, por exemplo

(apply + 1 2 other-number-list)
Mikera
fonte
9

Nesse caso específico, prefiro reduceporque é mais legível : quando leio

(reduce + some-numbers)

Sei imediatamente que você está transformando uma sequência em um valor.

Com applyeu tenho que considerar qual função está sendo aplicada: "ah, é a +função, então estou recebendo ... um único número". Um pouco menos direto.

mascip
fonte
7

Ao usar uma função simples como +, realmente não importa qual você usa.

Em geral, a ideia é que reduceé uma operação acumulativa. Você apresenta o valor de acumulação atual e um novo valor para sua função de acumulação. O resultado da função é o valor acumulado para a próxima iteração. Portanto, suas iterações se parecem com:

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

Para aplicar, a idéia é que você esteja tentando chamar uma função esperando vários argumentos escalares, mas eles estão atualmente em uma coleção e precisam ser retirados. Então, ao invés de dizer:

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

nós podemos dizer:

(apply some-fn vals)

e é convertido para ser equivalente a:

(some-fn val1 val2 val3)

Portanto, usar "aplicar" é como "remover os parênteses" ao redor da sequência.

Alan Thompson
fonte
4

Um pouco tarde, mas fiz um experimento simples depois de ler este exemplo. Aqui está o resultado da minha substituição, simplesmente não consigo deduzir nada da resposta, mas parece que há algum tipo de chute de cache entre reduzir e aplicar.

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

Analisar o código-fonte do clojure reduz sua recursão bastante limpa com o interno-reduzir, mas não encontrou nada na implementação do apply. A implementação de Clojure do + for apply invoca internamente a redução, que é armazenada em cache pelo repl, que parece explicar a quarta chamada. Alguém pode esclarecer o que realmente está acontecendo aqui?

rohit
fonte
Eu sei que vou preferir reduzir sempre que pode :)
Rohit
2
Você não deve colocar a rangechamada dentro do timeformulário. Coloque-o do lado de fora para remover a interferência da construção da sequência. No meu caso, reducesempre supera apply.
Davyzhu
3

A beleza de aplicar é dada função (+ neste caso) pode ser aplicada à lista de argumentos formada por argumentos intervenientes pendentes com uma coleção final. Reduzir é uma abstração para processar itens de coleção que aplicam a função para cada um e não funciona com o caso args variável.

(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)
Ira
fonte