186 #4829(2007/12/15 09:22 GMT) [ Scheme ] Rating3/3=1.00
see: どう書く?org #1671 shiro: メモ化をちょっと試してみた。 単純にn...(「組合せ型の最小完全ハッシュ関数」の逆関数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
(define (maho-memo n) (define cn (/ (* n (+ (* n n) 1)) 2)) (define maho-in-memo (let1 tab (make-hash-table 'equal?) (define (memo m l v) (hash-table-put! tab (cons m l) v) v) (lambda (m l) (cond ((= m 0) 1) ((hash-table-get tab (cons m l) #f)) (else (memo m l (apply + (map (lambda (a) (maho-in-memo (- m n) (lset-difference equal? l a))) (map (lambda (li) (cons (car l) li)) (filter (lambda (li) (= (apply + li) (- cn (car l)))) (combinations (cdr l) (- n 1)))))))))))) (maho-in-memo (* n n) (iota (* n n) 1)))
Rating3/3=1.00-0+
2 replies [ reply ]
186 #4829() [ Scheme ] Rating3/3=1.00
n=5で2分と少々です. メモリ使用量は11MB (多分).
Pen4 3GHzです.
gosh> ;(time (maho-memo 4))
; real 0.078
; user 0.078
; sys 0.000
392
gosh> ;(time (maho-memo 5))
; real 130.656
; user 124.562
; sys 4.828
3245664
see: どう書く?org #1671 shiro: メモ化をちょっと試してみた。 単純にn...(「組合せ型の最小完全ハッシュ関数」の逆関数)
Rating3/3=1.00-0+