9章「コードチューニング」 - 珠玉のプログラミング（Programming Pearls）

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

9.5.1

Mosh でやったことがあるので略。

9.5.2

配布プログラムがうまく動かないので略。

9.5.3

do while なら良さそう。という話だろうか。

9.5.4

配列が小さい順にソートされていると、arrmax が 2倍呼ばれてしまう。

9.5.5

本当は見つかるはずの物を見逃す。

9.5.6

例えば isupper なら
int isupper(char ch) { return ch >= 'A' && ch <= 'Z'; }
と書いて答えを見たら、負けた。

9.5.7

word サイズの配列を作るかな。

9.5.8

コード参照。

9.5.9

コード参照。

9.5.10

略。

9.5.11

360 / 5 = 72 個しかないので表引き。

9.5.12

Horner の多項式というのがあるらしい。

9.scm

;; Programming Pearls Chapter 9
(import (rnrs)
        (mosh)
        (mosh control)
        (srfi :27)
        (only (srfi :1) list-tabulate)
        (mosh test))

(define v `#(1 2 3 4 8 9 5 -1 ,(least-fixnum)))

(define (find-max v)
  (let loop ([i 0]
             [m (least-fixnum)])
    (cond
     [(= (least-fixnum) (vector-ref v i))
      m]
     [else
      (loop (+ i 1) (max m (vector-ref v i)))])))

(define (linear-search vec t)
  (let1 len (vector-length vec)
    (let loop ([i 0])
      (cond
       [(= i len) -1]
       [else
        (if (= (vector-ref vec i) t)
            i
            (loop (+ i 1)))]))))


(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 (random-vector n)
  (random-source-randomize! default-random-source)
  (list->vector (list-tabulate n (lambda x
                                   ((if (= (random-integer 2) 0) + -) (random-integer n))))))

(display (find-max v))

(for-each
 (lambda (i)
   (define v (vector-sort > (random-vector i)))
   (format #t "i = ~d\n" i)
   (time (linear-search v 5))
   (time (binary-search v 5)))
 '(10 100 1000 10000 100000))

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

posted with amazlet at 09.07.11

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

Amazon.co.jp で詳細を見る