#gauche.sequence#fold-right が再帰で実装されているので、後ろからの列挙が高速にできるデータ型に対して遅い(し空間O(n)な)実装になっていて、<string> や <vector> 等に特殊化したい…と思っていろいろ考えてみました。srfi.152#string-fold-right (string一つしか取らない)や scheme.vector#vector-fold-right (コールバックの引数順が違いますがとりあえずvector一つに対してはflip噛ませて尚速そうでした)はより高速な実装になっていますが、gauche.sequence がこれらのモジュールに依存していいものでしょうか。或いは、直接 fold-right を特殊化するより call-with-reverse-iterator みたいなものを導入して解決することを考えた方がいいでしょうか。後者の場合、新たにクラスを用意することも考えられます。前者だけだと (fold-right <top> <top> <string> <vector>) みたいなのが急に遅くてメモリを食ってそれがまた落とし穴になりそうなので、やっぱり call-with-reverse-iterator みたいなものがほしくなりそうです。
#雑な計測ですが
gosh> (define (f n) (let1 s (make-string n) (time (fold-right (^ (c r) (+ r (char->ucs c))) 0 s))))
f
gosh> (define (g n) (let1 s (make-string n) (time (string-fold-right (^ (c r) (+ r (char->ucs c))) 0 s))))
g
gosh> (f 3000000)
;(time (fold-right (^ (c r) (+ r (char->ucs c))) 0 s))
; real 1.456
; user 1.340
; sys 0.130
96000000
gosh> (g 3000000)
;(time (string-fold-right (^ (c r) (+ r (char->ucs c))) 0 s))
; real 0.783
; user 0.760
; sys 0.010
96000000
gosh> (define (fv f n) (let1 s (make-vector n #\!) (time (fold-right f 0 s))))
fv
gosh> (define (gv f n) (let1 s (make-vector n #\!) (time (vector-fold-right (^ (r c) (f c r)) 0 s))))
gv
gosh> (fv (^ (c r) (+ r (char->ucs c))) 3000000)
;(time (fold-right f 0 s))
; real 1.450
; user 1.310
; sys 0.120
99000000
gosh> (gv (^ (c r) (+ r (char->ucs c))) 3000000)
;(time (vector-fold-right (^ (r c) (f c r)) 0 s))
; real 0.417
; user 0.410
; sys 0.000
#ジェネリックに逆順列挙しようとすると fold-right になるんですよね。
#（関連する話題として、ランダムアクセスが高速にできるかどうかでディスパッチしたいみたいなのもありそうです。クラスに対して問い合わせできるといいんでしょうか）
#（リストに対する lazy-size-of がプロミスを返さなくて驚いた思い出）
#fold-rightは自分であんまり使わないのでおざなりです。直すならreverse-iteratorと*-fold-rightがあれば呼び出し、の両方ありだと思います。依存関係についてはautoloadかな。
#そういや (lazy-size-of ((coll <list>)) は単に見落としだと思う
#なるほど。とりあえずは新クラス(<reversible-sequence> みたいな？)は導入せず (applicable? call-with-reverse-iterator ...) でやる感じですかね。やってみます。クラス分けた方が見通しがいい気がするのと reverse-for-each みたいなメソッドも生やしやすいと思う一方、継承関係がどんどん深くなるのは嫌な感じもあるんですよね。call-with-builder なんかもクラスは分かれていないですね。
#そういう性質の場合は直径継承より <reversable-sequence-mixin> などmixinクラスを使うのがCLOS流かも。ただ、mixinが入ってて嬉しいのはそれにまつわるメソッドがいくつもある場合に一括判定ができるからで、単一メソッドの有無なra
#nara
#ならapplicable?が使えるのであまりこだわる必要はないとも思います。
Gauche > Archives > 2021/01/12