プログラミングGauche p.112 delete-1についての練習問題

未だnonLisp脳なせいか、ヒント読んでも分からない。
ごり押しで下のコードができた。一応テストは通るし、末尾再帰なので速い。

(define (my-delete-1 elt lis . options)
  (define orig-lis lis)
  (let-optionals* options ((cmp-fn equal?))
    (define (loop lis result)
      (cond [(null? lis) (reverse result)]
            [(cmp-fn elt (car lis)) (reverse (append (reverse (cdr lis)) result))]
            [(null? (cdr lis)) orig-lis]
            [else (loop (cdr lis) (cons (car lis) result))]))
    (loop lis '())))

これではあんまりだ。でも思いつかないから他の方、emaさんのコードを見る。

(define (delete-1 elt lis . options)
  (let-optionals* options ((cmp-fn equal?))
    (define (loop lis)
      (cond [(null? lis) lis]
            [(cmp-fn elt (car lis)) (cdr lis)]
            [else (let ((memo (loop (cdr lis))))
              (if (eq? (cdr lis) memo) lis (cons (car lis) memo)))]))
  (loop lis)))

http://emaame.com/20081025.html

おお、ヒントそのままだｗ
結果のみを組み込むイメージが掴めた。気がする。emaさん、ありがとうございます。

実行速度

timeマクロで実行速度を測ってみる。
CPUはCore2Duo E7200。
面倒なので計測回数は1回だけ。

計測対象の手続きは、p.111に載ってるdelete-1(コードは最後に載せる)、自分で作った最初のもの、emaさんのの3つ。それぞれwasteful、my、emaと呼ぶ。計測には以下のコードを使った。

(time (delete-1 #t (make-list 1000000 #f)))

評価時間にはtimeマクロが表示するrealの値を使う。結果を以下の表に示す。

手続き	評価時間(秒)
wasteful	1.131
my	0.142
ema	0.519

意外と差が出るのね。

所でtimeマクロは最後の式の結果を返すので、この場合、巨大なリストが帰ってきてしまう。巨大リストがインタプリタによって表示されてうっとうしいからnull?で捨てるようにしてみた。*1

(null? (time (delete-1 #t (make-list 1000000 #f))))

すると結果は

手続き	評価時間(秒)
wasteful	0.466
my	0.147
ema	0.468

wasteful変わりすぎ。なんでかしら。

p.111に載ってるdelete-1

(define (wasteful-delete-1 elt lis . options)
  (let-optionals* options ((cmp-fn equal?))
    (define (loop lis)
      (cond [(null? lis) '()]
            [(cmp-fn elt (car lis)) (cdr lis)] 
            [else (cons (car lis) (loop (cdr lis)))]))
    (loop lis)))

*1:もっと手軽な捨て方あるかな？