Subscribed unsubscribe Subscribe Subscribe

末尾再帰のクイックソートつづき

プログラミング

先日のエントリに対してid:nozomさんからトラックバックをいただいた.どうやら先に挙げたページにあるquicksort/cpsのcpsは継続渡しスタイル(CPS)のことだったようだ.調べてみると確かにこのCPSは末尾再帰に変換するときによく使われるらしく,Wikipediaにも

Besides space and execution efficiency, the tail recursion is important to allowing a common idiom in functional programming, continuation passing style (CPS), without quickly running out of stack space.

とあり,リンク先には用例も載っている.

ということで,昨日のqsortをCPSに変換する.

その前にfilterをpartitionへ

その前に,ちょっと気になる部分を修正する.
関数filterはltとgeを生成するのに同じリストを2回走査するので,無駄が多い.そこで,リスト走査1回で計算できるpartitionを作る*1

(define (partition pred? lst)
  (define (iter lst true false)
    (if (null? lst)
        (values (reverse true) (reverse false))
        (let ((x (car lst)) (xs (cdr lst)))
          (if (pred? x)
              (iter xs (cons x true) false)
              (iter xs true (cons x false))))))
  (iter lst '() '()))

これを使うとqsort-recは

(define (qsort lst)
  (if (null? lst)
      lst
      (let ((x (car lst)) (xs (cdr lst)))
        (receive (le gt) (partition (lambda (y) (< y x)) xs)
          (append (qsort le) (list x) (qsort gt))))))

となり,実行時間も短くなる.

CPS

d:id:nozom:20060131と同じ.

(append (qsort le) (list x) (qsort gt))

(let ((v1 (qsort le)))
  (append v1 (list x) (qsort gt)))

と等価で,さらに

((lambda (v1)
   (append v1 (list x) (qsort gt)))
 (qsort le))

と等価となる.ここから末尾再帰にするために

(qsort le
       (lambda (v1)
         (qsort gt
                (lambda (v2)
                  (k (append v1 (list x) v2))))))

と変換する.
最終的にqsortは次のようになる.

(define (qsort lst k)
  (if (null? lst)
      (k lst)
      (let ((x (car lst)) (xs (cdr lst)))
        (receive (lt ge) (partition (lambda (y) (< y x)) xs)
          (qsort lt
                 (lambda (v1)
                   (qsort ge
                          (lambda (v2)
                            (k (append v1 (cons x v2)))))))))))

呼び出す際にはkにvaluesを使うのが一般的だとか.

プロファイル

プロファイルを取ったところ元のqsortより少し遅くなったことがわかった.ここを見ると同じように遅くなっている.クロージャ作成のときのヒープ確保が遅いのではないかという考察.なるほど.

*1:ちなみにfilterもpartitionもgauche.collectionにあるので,Gaucheでは(use gauche.collection)すれば使える.