Clojure: zmniejsz a zastosuj


126

Rozumiem koncepcyjną różnicę między reducei 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)

Jednak który z nich jest bardziej idiomatyczny? Czy ma to duże znaczenie w taki czy inny sposób? Z moich (ograniczonych) testów wydajności wynika, że reducejest nieco szybszy.

Odpowiedzi:


125

reducei applysą oczywiście równoważne tylko (pod względem zwróconego ostatecznego wyniku) dla funkcji asocjacyjnych, które muszą widzieć wszystkie swoje argumenty w przypadku zmiennej-arity. Kiedy są równoważne wynikom, powiedziałbym, że applyzawsze jest to idealnie idiomatyczne, podczas gdyreduce jest równoważne - i może skrócić o ułamek mrugnięcia oka - w wielu typowych przypadkach. Oto moje uzasadnienie, aby w to wierzyć.

+jest zaimplementowany w kategoriach reducedla przypadku zmiennej-arity (więcej niż 2 argumenty). Rzeczywiście, wydaje się to niezmiernie rozsądnym "domyślnym" sposobem na zastosowanie dowolnej funkcji asocjacyjnej o zmiennej arsenale: reducema potencjał do wykonania pewnych optymalizacji, aby przyspieszyć działanie - być może poprzez coś w rodzaju internal-reducenowości 1.2 ostatnio wyłączonej w trybie głównym, ale miejmy nadzieję, że zostaną ponownie wprowadzone w przyszłości - co byłoby głupio powielać w każdej funkcji, która mogłaby z nich skorzystać w przypadku vararg. W takich typowych przypadkach applypo prostu doda trochę narzutów. (Zauważ, że nie ma się czym martwić.)

Z drugiej strony, funkcja złożona może wykorzystywać pewne możliwości optymalizacji, które nie są na tyle ogólne, aby można je było wbudować reduce; następnie applypozwolili skorzystać z tych chwili reducerzeczywiście może spowolnić. Dobrym przykładem tego drugiego scenariusza występującego w praktyce jest str: wykorzystuje StringBuilderwewnętrznie i odniesie znaczne korzyści z użycia applyzamiast reduce.

Więc powiedziałbym, że używaj applyw razie wątpliwości; a jeśli zdarzy ci się wiedzieć, że nie kupuje ci to niczego ponad reduce(i że jest mało prawdopodobne, aby to się wkrótce zmieniło), możesz swobodnie reduceogolić to drobne niepotrzebne obciążenie, jeśli masz na to ochotę.


Świetna odpowiedź. Na marginesie, dlaczego nie uwzględnić wbudowanej sumfunkcji, takiej jak w haskell? Wydaje się, że to dość powszechna operacja.
dbyrne

17
Dzięki, miło mi to słyszeć! Re sum:, powiedziałbym, że Clojure ma tę funkcję, nazywa się +i możesz jej używać apply. :-) Poważnie mówiąc, myślę, że generalnie w Lispie, jeśli zapewnia się funkcję wariadyczną, zwykle nie towarzyszy jej opakowanie działające na kolekcjach - do tego używasz apply(lub reduce, jeśli wiesz, ma to większy sens).
Michał Marczyk

6
Zabawne, moja rada jest odwrotna: kiedy masz reducewątpliwości, applykiedy wiesz na pewno, istnieje optymalizacja. reduceumowa jest bardziej precyzyjna, a przez to bardziej podatna na ogólną optymalizację. applyjest bardziej niejasny i dlatego może być optymalizowany tylko dla poszczególnych przypadków. stri concatsą dwoma powszechnymi wyjątkami.
cgrand

1
@cgrand Przeformułowanie mojego uzasadnienia może z grubsza polegać na tym, że w przypadku funkcji, które są równoważne pod względem wyników reducei applysą równoważne pod względem wyników, spodziewałbym się, że autor danej funkcji będzie wiedział, jak najlepiej zoptymalizować ich wariadyczne przeciążenie i po prostu zaimplementować je w kategoriach, reducejeśli to jest rzeczywiście najbardziej sensowne (taka opcja jest z pewnością zawsze dostępna i stanowi wyjątkowo rozsądną wartość domyślną). Widzę jednak, skąd pochodzisz, reducejest zdecydowanie kluczem do historii wydajności Clojure (i coraz bardziej), bardzo dobrze zoptymalizowanej i bardzo jasno określonej.
Michał Marczyk 22.08.13

51

Dla początkujących, którzy patrzą na tę odpowiedź,
bądź ostrożny, to nie to samo:

(apply hash-map [:a 5 :b 6])
;= {:a 5, :b 6}
(reduce hash-map [:a 5 :b 6])
;= {{{:a 5} :b} 6}

21

Opinie są różne - w większym świecie Lispów reducejest zdecydowanie bardziej idiomatyczny. Po pierwsze, omówiono już różne kwestie. Ponadto niektóre kompilatory Common Lisp będą faktycznie zawieść, gdyapply zostaną zastosowane do bardzo długich list z powodu sposobu, w jaki obsługują listy argumentów.

Jednak wśród Clojurists w moim kręgu używanie applyw tym przypadku wydaje się bardziej powszechne. Łatwiej mi się bawić i wolę to też.


19

W tym przypadku nie ma to znaczenia, ponieważ + to specjalny przypadek, który można zastosować do dowolnej liczby argumentów. Reduce to sposób na zastosowanie funkcji, która oczekuje stałej liczby argumentów (2) na dowolnie długiej liście argumentów.


9

Zwykle wolę redukować, gdy działam na jakimkolwiek rodzaju kolekcji - działa to dobrze i ogólnie jest całkiem użyteczną funkcją.

Głównym powodem, dla którego użyłbym Apply, jest to, że parametry oznaczają różne rzeczy w różnych pozycjach lub jeśli masz kilka parametrów początkowych, ale chcesz pobrać resztę z kolekcji, np.

(apply + 1 2 other-number-list)

9

W tym konkretnym przypadku wolę, reduceponieważ jest bardziej czytelny : kiedy czytam

(reduce + some-numbers)

Wiem od razu, że zmieniasz sekwencję w wartość.

Z applymuszę rozważyć, która funkcja jest stosowana: „Ach, to jest to +funkcja, więc jestem coraz ... jeden numer”. Nieco mniej proste.


7

Kiedy używasz prostej funkcji, takiej jak +, naprawdę nie ma znaczenia, której używasz.

Generalnie chodzi o to, że reducejest to operacja akumulacyjna. Przedstawiasz bieżącą wartość akumulacji i jedną nową wartość swojej funkcji sumującej. Wynikiem funkcji jest skumulowana wartość dla następnej iteracji. Twoje iteracje wyglądają więc następująco:

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

W przypadku zastosowania chodzi o to, że próbujesz wywołać funkcję oczekującą wielu argumentów skalarnych, ale obecnie znajdują się one w kolekcji i muszą zostać wyciągnięte. Więc zamiast mówić:

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

możemy powiedzieć:

(apply some-fn vals)

i jest konwertowany na odpowiednik:

(some-fn val1 val2 val3)

Zatem użycie „zastosuj” jest jak „usunięcie nawiasów” wokół sekwencji.


4

Trochę za późno na ten temat, ale po przeczytaniu tego przykładu przeprowadziłem prosty eksperyment. Oto wynik z mojej odpowiedzi, po prostu nie mogę nic wywnioskować z odpowiedzi, ale wydaje się, że między redukcją a zastosowaniem jest jakiś rodzaj buforowania.

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

Patrząc na kod źródłowy clojure, zmniejszając jego całkiem czystą rekursję za pomocą funkcji Internal-Red, nie znalazłem nic na temat implementacji Apply. Implementacja Clojure + dla zastosuj wewnętrznie wywołaj redukuj, która jest buforowana przez repl, co wydaje się wyjaśniać czwarte wywołanie. Czy ktoś może wyjaśnić, co się tu naprawdę dzieje?


Wiem, że wolę redukować, kiedy tylko będę mógł :)
rohit

2
Nie należy umieszczać rangepołączenia wewnątrz timeformularza. Umieść go na zewnątrz, aby usunąć zakłócenia konstrukcji sekwencji. W moim przypadku reducekonsekwentnie przewyższa apply.
Davyzhu,

3

Piękno zastosowania polega na tym, że funkcja (w tym przypadku +) może być zastosowana do listy argumentów utworzonej przez poprzedzające argumenty interweniujące z końcową kolekcją. Reduce jest abstrakcją służącą do przetwarzania elementów kolekcji, stosując funkcję dla każdego z nich i nie działa ze zmiennymi przypadkami args.

(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)
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.