8章「アルゴリズムのデザインテクニック」 - 珠玉のプログラミング（Programming Pearls）
珠玉のプログラミングの8章。
8.7.1
maxendinghere の不変表明は「任意の 0 .. i-1 に関して maxendinghere がx[i - 1] を含む部分配列の総和の max 」であること。
- 0 のときは 0 なので成り立つ。
- k - 1 まで成り立っているのであれば、maxendinghere は x[k] を足したものか、もしくは 0 であるから成り立つ。
maxsofar の不変表明は「任意の 0 .. i-1 に関して maxsofar 0 ... i-1 に存在する部分配列の総和の max 」であること。
- 0 のときは 0なので成り立つ
- k - 1 まで成り立っているのであれば、k での最大値は k - 1 までの最大値か、maxendinghere のどちらか大きい方であるから成り立つ。
8.7.2
コード参照。
8.7.3
R6RS の rename を使ってカウンターを差し込んで max の回数を調べた。
100 要素のベクタに関して、それぞれ 5050, 5050, 871, 200 回呼ばれている。
n の要素に足して定数項を省くと、n^3, n^2, logn, n 回呼ばれる。
メモリの使用量は n に関係なく一定。
8.7.4
直感的には 0 だけど違う？
8.7.5
- 1 の場合は特別に扱う。
8.7.6
分からない。答えどこかにないかな。
8.7.7
浮動小数とか。
8.7.8
分からない。答えどこかにないかな。
8.7.9
max-so-far を INT_MIN にする
8.7.10
0 との差分を保持し min で比べるように変更する。
答えはもっとスマートだった。
8.7.11
8.7.10 と似た問題だ。具体的になると簡単に分かる。
料金所の料金を足し合わせた配列を持てば O(1) で行ける。
8.7.12
難しい。思いつかなかった。
8.7.13
方向が増えるから難しい。
8.7.14
分からない。
8.7.15
n=2^k とすると
T(n) = 2^(k - 1) * c2 + 2^(k -2) * c4 + ....
8.scm
;; Programming Pearls Chapter 8 (import (rename (rnrs) (max rnrs:max)) (mosh) (mosh control) (srfi :27) (only (srfi :1) list-tabulate) (mosh test)) (define counter 0) (define (reset-counter!) (set! counter 0)) (define (counter++!) (set! counter (+ counter 1))) (define (max . arg*) (counter++!) (apply rnrs:max arg*)) ;; 8.7.2 (define (max-part1 v) (define (sum x y) (let loop ([i x] [total 0]) (cond [(= i y) (+ total (vector-ref v y))] [else (loop (+ i 1) (+ total (vector-ref v i)))]))) (let1 len (vector-length v) (let loop-i ([max-so-far 0] [i 0]) (cond [(= i len) max-so-far] [else (let loop-j ([max-so-far-j max-so-far] [j i]) (cond [(= j len) (loop-i max-so-far-j (+ i 1))] [else (loop-j (max (sum i j) max-so-far-j) (+ j 1))]))])))) (define (max-part2 v) (let1 len (vector-length v) (let loop-i ([max-so-far 0] [i 0]) (cond [(= i len) max-so-far] [else (let loop-j ([j i] [sum 0] [max-so-far-j max-so-far]) (cond [(= j len) (loop-i max-so-far-j (+ i 1))] [else (let1 s (+ sum (vector-ref v j)) (loop-j (+ j 1) s (max s max-so-far-j)))]))])))) (define (max-part3 v) (define (calc-lmax l m) (let loop ([i m] [sum 0] [lmax 0]) (cond [(= i (- l 1)) lmax] [else (let1 s (+ sum (vector-ref v i)) (loop (- i 1) s (max lmax s)))]))) (define (calc-rmax u m) (let loop ([i (+ m 1)] [sum 0] [rmax 0]) (cond [(= i (+ u 1)) rmax] [else (let1 s (+ sum (vector-ref v i)) (loop (+ i 1) s (max rmax s)))]))) (define (rec l u) (cond [(> l u) 0] [(= l u) (max 0 (vector-ref v l))] [else (let1 m (div (+ l u) 2) (max (+ (calc-lmax l m) (calc-rmax u m)) (rec l m) (rec (+ m 1) u)))])) (rec 0 (- (vector-length v) 1))) (define (max-part4 v) (let1 n (vector-length v) (let loop ([i 0] [max-so-far 0] [max-ending-here 0]) (cond [(= i n) max-so-far] [else (let1 mhere (max 0 (+ max-ending-here (vector-ref v i))) (loop (+ i 1) (max max-so-far mhere) mhere)]))))) (define (random-vector n) (random-source-randomize! default-random-source) (list->vector (list-tabulate n (lambda x ((if (= (random-integer 2) 0) + -) (random-integer n)))))) (test-eq 187 (time (max-part1 '#(31 -41 59 26 -53 58 97 -93 -23 84)))) (test-eq 187 (time (max-part2 '#(31 -41 59 26 -53 58 97 -93 -23 84)))) (test-eq 187 (time (max-part3 '#(31 -41 59 26 -53 58 97 -93 -23 84)))) (test-eq 187 (time (max-part4 '#(31 -41 59 26 -53 58 97 -93 -23 84)))) (let1 v (random-vector 200) (test-true (apply = (map (lambda (proc) (reset-counter!) (let1 val (time (proc v)) (format #t "counter=~d\n" counter) val)) (list max-part1 max-part2 max-part3 max-part4))))) (test-results)
珠玉のプログラミング—本質を見抜いたアルゴリズムとデータ構造
posted with amazlet at 09.07.11
ジョン ベントリー
ピアソンエデュケーション
売り上げランキング: 5607
ピアソンエデュケーション
売り上げランキング: 5607
