リストの要素を検査して述語が#tを返す要素を数える関数――以下count関数と称する――がscheme/srfi/gaucheにはなさそうだったので、しこしこ実装することになったのですが――その際いくつも方法を思いついたため、どの方法が効率的なのか、おおざっぱに計測してみました。
2015/11/10 19:20 追記:
コメント欄で教えてもらった通り、count関数はsrfi-1に存在するそうです――というか存在していました……。ここ半年近くcount関数はないとばかり勘違いしていて、しかもこの記事を書くにあたって30分近くは調査したのですが、それでも見つからなかったので、てっきりないものと決め込んでいました。調査不足というよりわたしの調査力不足がたたったということになります。反省します(´・ω・`)
というわけで以降はまったくの与太記事世迷言となります。削除することも考えたのですが、個人的にはとても勉強になったし、何より計測中は楽しかったので、一応ここに残しておきます。
さてエントリーは以下の5選手です。オーソドックスなものはほぼほぼカバーできたはず。
; ふつうの再帰 (define (count1 proc ls) (if (null? ls) 0 (if (proc (car ls)) (+ 1 (count proc (cdr ls))) (count proc (cdr ls))))) ; named let (define (count2 proc ls) (let loop ((l ls) (c 0)) (if (null? l) c (if (proc (car l)) (loop (cdr l) (+ c 1)) (loop (cdr l) c))))) ; 畳み込み演算 (define (count3 proc ls) (fold (lambda (val sum) (if (proc val) (+ sum 1) (+ sum 0))) 0 ls)) ; procがtrueを返す要素のみからなるリストを作り、その大きさを返す (define (count4 proc ls) (length (filter proc ls))) ; 手続き的：要素がtrueを返せばカウンタを1進める。 (define (count5 proc ls) (let ((c 1)) (for-each (lambda (val) (when (proc val) (set! c (+ c 1)))) ls) c))
そしておのおのの関数についてgauche.timeモジュールで計測を行います。その結果が以下。
(time (count1 odd? (iota 10000000))) (time (count2 odd? (iota 10000000))) (time (count3 odd? (iota 10000000))) (time (count4 odd? (iota 10000000))) (time (count5 odd? (iota 10000000))) ;(time (count1 odd? (iota 10000000))) ; real 1.422 ; user 1.391 ; sys 0.031 ;(time (count2 odd? (iota 10000000))) ; real 0.984 ; user 1.016 ; sys 0.047 ;(time (count3 odd? (iota 10000000))) ; real 1.594 ; user 1.578 ; sys 0.000 ;(time (count4 odd? (iota 10000000))) ; real 1.501 ; user 1.719 ; sys 0.016 ;(time (count5 odd? (iota 10000000))) ; real 1.109 ; user 1.110 ; sys 0.000
というわけでreal time最速はcount2、つまりループをnamed letでまわしたcount関数になりました。ぱちぱちぱち。count1とは違って再帰的呼び出しのたびに述語のコピーが発生するようなことはなく、かつ末尾再帰の最適化が行われた結果、最速になったのではないかと予想します。なお詳細は記しませんが、同じような複数回行った感想としてはcount2がずばぬけて速く、次に手続き的なcount5。残りのcount1(再帰)/count3(fold)/count4(filter)に関してはcount1がやや速い印象はあるものの、はっきりいうとどんぐりの背比べでした。
今回やってみて感じたのはgauche.timeが超便利だということ、そしてベンチマークの難しさでした。たとえばとある関数の性能を見たいとしましょう。その場合、性能とはどのようなものか、性能が具体化されたとしてそれを可視化するにはどのようなテストケースが最適か、あるいは結果をどのように比較すべきか、などなど考えるべきことが多く、頭が破裂しそうになります。この手の知識や方法論は体系化されていない、というかやや場当たり的にやっていくほかないことなので、今回わたしが行ったベンチマークも正しいかどうか判断がつきかねるというのが本音です。
とりあえず参考程度に、あまり信用しないでいただけると幸いです。
読み返してみると、すべての関数において述語をしめす変数をprocにしていますね……。predにすべきでした(´・ω・｀)
