MY-APPEND or why reduce is not suitable for append.
MY-APPEND or why reduce is not suitable for append.
Introduction
このようなツイートがありまして、このようにリツイートしたところまさかの返信がありまして。
話すと長くなるのでここにまとめます。
なお、僕はCommon Lispには明るいもののこちらのPureLISP_shについては暗いので以降の例は全てCommon Lispで書かれたものとなります。
REDUCE.
REDUCE
という関数は二引数関数とリストをとり、畳み込み(reduce)を行う高階関数です。
以下のような振る舞いになります。
* (reduce #'+ '(1 2 3 4 5))
15
* (reduce #'max '(1 2 3 4 5))
5
* (reduce #'min '(1 2 3 4 5))
1
REDUCE*
元記事のREDUCE
をCommon Lispで再実装すると以下になります。
CL:REDUCE
と名前がぶつかるのでここでは末尾に*
をつけて回避します。
(defun reduce* (function list initial-value)
(cond
((eql list nil) initial-value)
(t (funcall function
(car list)
(reduce* function (cdr list) initial-value)))))
Actualy it is foldr.
REDUCE*
の一番の問題点は末尾再起になっておらず、いわゆるREDUCE
と振る舞いが異なる点でしょうか。
* (trace reduce*)
(REDUCE*)
* (reduce* #'+ '(1 2 3 4 5) 0)
0: (REDUCE* #<FUNCTION +> (1 2 3 4 5) 0)
1: (REDUCE* #<FUNCTION +> (2 3 4 5) 0)
2: (REDUCE* #<FUNCTION +> (3 4 5) 0)
3: (REDUCE* #<FUNCTION +> (4 5) 0)
4: (REDUCE* #<FUNCTION +> (5) 0)
5: (REDUCE* #<FUNCTION +> NIL 0)
5: REDUCE* returned 0
4: REDUCE* returned 5
3: REDUCE* returned 9
2: REDUCE* returned 12
1: REDUCE* returned 14
0: REDUCE* returned 15
15
これはHaskellでいうfoldr
の振る舞いです。
Haskellはfold
とfoldr
という二種類の関数を用意する道を選びました。
Common Lispは引数で制御する道を選びました。
Common LispのREDUCE
はキーワード引数:FROM-END
を受け付けます。
指定された場合Haskellでいうfoldr
の振る舞いとなります。
;; いわゆるREDUCE。
* (reduce #'cons '(1 2 3) :initial-value nil)
(((nil . 1) . 2) . 3)
;; Haskellでいうfoldr。
* (reduce #'cons '(1 2 3) :initial-value nil :from-end t)
(1 2 3)
;; REDUCE*はfoldrの振る舞いをする。
* (reduce* #'cons '(1 2 3) nil)
(1 2 3)
APPEND by REDUCE.
Common LispでAPPEND
をREDUCE
を使って実装するなら、以下のようになるでしょう。
(defun my-append (&rest lists)
(reduce (lambda (list acc)
(reduce (lambda (x y)
(cons x y))
list :initial-value acc :from-end t))
lists
:initial-value nil
:from-end t))
APPEND without REDUCE.
Common Lispの界隈には、いにしえよりTCONC
という技法が伝わっております。
効率の良いAPPEND
の実装を考えるならTCONC
を使ったものとなるでしょう。
これは要するに即席のqueueです。
(defun my-append2 (&rest lists)
(do* ((acc (cons :dummy nil))
(tail acc)
(lists lists (cdr lists)))
((null lists) (cdr acc))
(do ((list (car lists) (cdr list)))
((null list))
(setf (cdr tail)
(setf tail (list (car list)))))))
Bench.
まずは元ツイの全関数を実装。
(defun append2 (a b) (reduce* #'cons a b))
(defun append* (&rest lists)
(reduce* #'append2 lists nil))
ベンチ。
* (time (append* '(1 2) '(3 4) '(5 6)))
Evaluation took:
0.000 seconds of real time
0.000003 seconds of total run time (0.000003 user, 0.000000 system)
100.00% CPU
5,356 processor cycles
0 bytes consed
* (time (my-append '(1 2) '(3 4) '(5 6)))
Evaluation took:
0.000 seconds of real time
0.000003 seconds of total run time (0.000003 user, 0.000000 system)
100.00% CPU
7,048 processor cycles
0 bytes consed
* (time (my-append2 '(1 2) '(3 4) '(5 6)))
Evaluation took:
0.000 seconds of real time
0.000002 seconds of total run time (0.000002 user, 0.000000 system)
100.00% CPU
2,368 processor cycles
0 bytes consed
* (time (append '(1 2) '(3 4) '(5 6)))
Evaluation took:
0.000 seconds of real time
0.000004 seconds of total run time (0.000003 user, 0.000001 system)
100.00% CPU
2,636 processor cycles
0 bytes consed
元ツイのAPPEND*
はCL:REDUCE
で実装したものより早いですね。
これはCL:REDUCE
が一つのインターフェイスに:FROM-END
やら何やらあれこれつぎ込んだのがオーバーヘッドになっているからかと思われます。
とはいえTCONC
のテイクは倍の速さとなります。
CL:APPEND
の効率がTCONC
のものと大差ないので、SBCLのAPPEND
はおよそTCONC
での実装とみて良いのかもしれません。
Conclusion.
これ以上のベンチは取りようがないのでこれは憶測になってしまうのですが、REDUCE
のテイクが遅いのは末尾再帰にならずスタック負荷が高いのと高階関数の宿命たる関数の動的呼び出しコストによるものではないかと思われます。
実装コストと実行コストはある程度あちらを立てればこちらが立たずという関係にあるかと思われます。
TCONC
のテイクはお世辞にも読みやすいものではありません。
そのバランスを取るのは実装者の責任です。
REDUCE*
のテイクは充分に短く把握が容易です。
本記事が参考になったなら幸い!