DouKaku? 1671 shiro: メモ化をちょっと試してみた。単純にn...(「組合せ型の最小完全ハッシュ関数」の逆関数)

Comment detail

This comment is reply for 1670 shiro: 2分探索みたいな感じかな。境界値がnCr...(「組合せ型の最小完全ハッシュ関数」の逆関数). Go to thread root.

メモ化をちょっと試してみた。
単純にnCrの引数だけでメモ化するのはあまり効果が無い。
同じ(n,r)の組み合わせは1回しか使わないから (上のrev-hashの
コードでは手抜きで2回使われる箇所もあるけど)。
nCr = n-1Cr + n-1Cr-1 を使えば、最初のnCrの計算で
その後に使う組み合わせは全て計算してしまうのでメモ化の
効果は出る。ただ、これは要するにpascalのテーブルを最初に
(ほぼ)全部計算するってことだから、まだ無駄なことをしている
感じはある。

gosh> (time (begin ((rev-hash-test nCr-memo) (expt 10 599) 2000 1000) (values)))
;(time (begin ((rev-hash-test nCr-memo) (expt 10 599) 2000 1000) (values)))
; real   7.703
; user   7.470
; sys    0.210
gosh> (time (begin ((rev-hash-test nCr) (expt 10 599) 2000 1000) (values)))
;(time (begin ((rev-hash-test nCr) (expt 10 599) 2000 1000) (values)))
; real  35.341
; user  34.710
; sys    0.500

もちろん2度目からはメモ化版は激速だけど。

gosh> (time (begin ((rev-hash-test nCr-memo) (expt 10 599) 2000 1000) (values)))
;(time (begin ((rev-hash-test nCr-memo) (expt 10 599) 2000 1000) (values)))
; real   0.014
; user   0.010
; sys    0.000

テストコードを貼り付けておく。

(define (nCr n r)
  (define (! n k) (if (<= n k) 1 (* n (! (- n 1) k))))
  (/ (! n (- n r)) (! r 0)))

(define nCr-memo
  (let1 tab (make-hash-table 'equal?)
    (define (memo n r v) (hash-table-put! tab (cons n r) v) v)
    (lambda (n r)
      (cond [(or (= n r) (= r 0)) 1]
            [(hash-table-get tab (cons n r) #f)]
            [(> r (quotient n 2)) (nCr-memo n (- n r))]
            [else (memo n r (+ (nCr-memo (- n 1) (- r 1))
                               (nCr-memo (- n 1) r)))]))))

(define (rev-hash-test nCr)
  (define (rev-hash k n m)
    (cond [(= m 0) (make-list n 0)]
          [(= n m) (make-list n 1)]
          [(<= (nCr (- n 1) m) k)
           (cons 1 (rev-hash (- k (nCr (- n 1) m)) (- n 1) (- m 1)))]
          [else
           (cons 0 (rev-hash k (- n 1) m))]))
  rev-hash)

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq