5章「あと少しの事」- 珠玉のプログラミング（Programming Pearls）

珠玉のプログラミングの5章。

5.8.1

コードは古いが擬似コードは勉強になる。

5.8.2

コード参照

5.8.3

(< l u) の不等号を逆にする。テストで発覚。

5.8.4

コード参照。
sorted? を定義し assert を入れた。

5.8.5

ソートし忘れているのだから、部分的にソートされている可能性は少ないことを利用して。
いくつかピックアップして比較すれば O(1) で済む。

5.8.6

大変なのはわかりきっているので略。

5.8.7

1000万要素の vector だと初回は 5倍くらい遅かった。

5.8.8

xUnit

5.8.9

略。

5.scm

;; Programming Pearls Chapter 5
(import (rnrs)
        (mosh)
        (srfi :42)
        (mosh test))

(define (binary-search vec t)
  (let loop ([l 0]
             [u (- (vector-length vec) 1)])
    (if (> l u)
       -1
       (let* ([m (div (+ l u) 2)]
              [vm (vector-ref vec m)])
         (cond
          [(< vm t)
           (loop (+ m 1) u)]
          [(= vm t)
           m]
          [else
           (loop l (- u 1))])))))

(define (sorted? vec)
  (let ([len (vector-length vec)])
    (let loop ([i 0])
      (cond
       [(>= i (- len 1))
        #t]
       [else
        (and (< (vector-ref vec i) (vector-ref vec (+ i 1))) (loop (+ i 1)))]))))

(test-eq -1 (binary-search '#(2 4 6 8 10 12 14 16) 5))
(let ([v '#(2 4 6 8 10 12 14 16)])
  (assert (sorted? v))
  (test-eq 2 (binary-search v ' 6)))

(let ([v (vector-ec (: i 10000000) i)])
  (do ([i 0 (+ i 1)])
      ((= i 10))
    (time (binary-search v 954))))

(test-results)

珠玉のプログラミング—本質を見抜いたアルゴリズムとデータ構造

posted with amazlet at 09.07.11

ジョン ベントリー
ピアソンエデュケーション
売り上げランキング: 5607

Amazon.co.jp で詳細を見る