1章真珠貝を開いて - 珠玉のプログラミング（Programming Pearls）

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

1.6.1

全てを配列（Scheme の場合はリスト）に読み込み list-sort する。

1.6.2

コード bits の実装参照。

1.6.3

メモリ上に全て読み込んでからソートしたほうが圧倒的に速かった。
これは Mosh 特有の false pointer 問題で bits が遅いことに起因すると思う。

1.6.4

乱数を使う。1-gen-data.scm 参照。

1.6.5

ディスク上でマージソートする。ディスクに2回書く分と遅くなる。

1.6.6

bits を使うならば 1 つの数が現れるかどうかの保持に 4bit 余計に情報が必要になる。つまり5倍のメモリで実装できる。
もしメモリが十分あるならば全てメモリに読み込むのもあり。

1.6.7

データ入力時に数値かどうか、範囲内かどうかをチェックすればよい。コード参照。

1.6.8

2bit 余計に使いマージソートする。
上記 2bit だけ登録しておけば簡単に判断できる。

1.6.9

配列の index で bitmap を保持すればよい。初期化されているな 1 が立っている。

1.6.10

電話番号の一部をハッシュのように使う。

1.6.11

郵便で送る。

1.6.12

これは知ってた。鉛筆を使う。

1.scm

;; Programming Pearls Chapter 1
(import (rnrs)
        (mosh)
        (mosh test))

(define-record-type bits
  (fields
   (immutable length)
   (immutable bv))
  (protocol
   (lambda (c)
     (lambda (length)
       (c length (make-bytevector (+ 1 (truncate (/ length 8))) 0))))))


(define (bits-marked? bits index)
  (when (>= index (bits-length bits))
    (error 'bits-marked? "index out of range" index))
  (bitwise-bit-set? (bytevector-u8-ref (bits-bv bits) (truncate (/ index 8))) (mod index 8)))

(define (bits-set! bits index)
  (let* ([bv-index (truncate (/ index 8))]
         [bits-index (mod index 8)]
         [val (bytevector-u8-ref (bits-bv bits) bv-index)])
    (bytevector-u8-set! (bits-bv bits) bv-index (bitwise-ior val (bitwise-arithmetic-shift-left 1 bits-index)))))

(define (bits-test)
  (let ([bits (make-bits 10)])
    (test-true bits)
    (test-eq 10 (bits-length bits))
    (test-false (bits-marked? bits 0))
    (test-false (bits-marked? bits 1))
    (bits-set! bits 1)
    (test-false (bits-marked? bits 0))
    (test-true (bits-marked? bits 1))
    (bits-set! bits 0)
    (test-true (bits-marked? bits 0))
    (test-true (bits-marked? bits 1))
    (bits-set! bits 10)
    (test-error error? (bits-marked? bits 11))))

;(bits-test)

;;; Answer
(define (sort bits)
  (let ([len (bits-length bits)])
    (let loop ([i 0]
               [ret '()])
      (cond
       [(= i len) ret]
       [else
        (if (bits-marked? bits i)
            (loop (+ i 1) ret)
            (loop (+ i 1) (cons i ret)))]))))

;; Bits sort
(time
 (call-with-input-file "./1-data.txt"
   (lambda (p)
     (let ([bits (make-bits (expt 10 7))])
       (let loop ([num (read p)])
         (cond
          [(eof-object? num)
           (display "start sort\n")
           (sort bits)
           (display "end sort\n")]
          [else
           (cond
            [(and (number? num) (< expt 10 7))
             (bits-set! bits num)
             (loop (read p))]
            [else
             (error 'bits "invalid data" num)])]))))))

;; Enough memory, read all into memory and sort.
(time
 (call-with-input-file "./1-data.txt"
   (lambda (p)
       (let loop ([num (read p)]
                  [lst '()])
         (cond
          [(eof-object? num)
           (list-sort > lst)]
          [else
           (loop (read p) (cons num lst))])))))

(test-results)

1-gen-data.scm

(import (rnrs)
        (srfi :27))

;; Generate 1-data.txt
;; mosh 1-gen-data.scm 1-data.txt

(define (main args)
  (let* ([file (cadr args)]
         [max (expt 10 7)]
         [num-of-nums 1000000]
         [ht (make-eqv-hashtable)])
    (call-with-output-file file
      (lambda (port)
        (let loop ([i 0]
                   [num (random-integer max)])
          (cond
           [(= i num-of-nums) '()]
           [else
            (cond
             [(hashtable-ref ht num #f)
              (loop i (random-integer max))]
             [else
              (display num port)
              (newline port)
              (hashtable-set! ht num #t)
              (loop (+ i 1) (random-integer max))])]))))))

(main (command-line))

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

posted with amazlet at 09.07.11

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

Amazon.co.jp で詳細を見る