Add tags

Add tags to the following comment
同じ計算を何回もしているので#1671を参考にメモ化しました.
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
 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)))

Add tags

The input will be splited to tags with space.

Index

Feed

Other

Link

Pathtraq

loading...