1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
;;; Dynamic Programming examples
;;; (c)2018 Toshihiro Matsui, IISEC
;;; 2018-06-10
(defun rows (matrices i)
(print "BAKA")
(if (< i 0)
(first (first matrices))
(second (nth i matrices))))
(defun matmul (matrices i j)
(if (= i j)
0
(let (xlist)
(dotimes (k (- j i))
(push (+ (aref *mvec* i (+ i k)) ; (matmul matrices i (+ i k))
(aref *mvec* (+ i k 1) j) ; (matmul matrices (+ i k 1) j)
(* (rows matrices (1- i))
(rows matrices (+ i k))
(rows matrices j)))
xlist) )
(apply #'min xlist)) )
)
;; (fastest-matmul '((10 20) (20 50) (50 1) (1 100)))
(defun recursive-fastest-matmul (matrices)
(let* ((mats (length matrices))
(m (make-array (list mats mats) :initial-element 0))
(l) (i) (j) )
(setq *mvec* m)
(setq *matmulcount* 0)
(labels
((rows (i)
(if (< i 0)
(first (first matrices))
(second (nth i matrices))))
(matmul (i j)
(incf *matmulcount*)
(if (= i j) 0
(let (xlist)
(dotimes (k (- j i))
(push (+ ;;(aref m i (+ i k))
(matmul i (+ i k))
;; (aref m (+ i k 1) j)
(matmul (+ i k 1) j)
(* (rows (1- i))
(rows (+ i k))
(rows j)))
xlist) )
(apply #'min xlist)) )
))
(dotimes (l mats)
(dotimes (i (- mats l))
(setq j (+ i l))
(setf (aref m i j) (matmul i j))
(if *debug* (print (list i j (aref m i j))))
)
)
(aref m 0 (1- mats))
))
)
(defun fastest-matmul (matrices)
(let* ((mats (length matrices))
(m (make-array (list mats mats) :initial-element 0))
(l) (i) (j) )
(setq *mvec* m)
(setq *matmulcount* 0)
(labels
((rows (i)
(if (< i 0)
(first (first matrices))
(second (nth i matrices))))
(matmul (i j)
(incf *matmulcount*)
(if (= i j) 0
(let (xlist)
(dotimes (k (- j i))
(push (+ (aref m i (+ i k)) ; (matmul i (+ i k))
(aref m (+ i k 1) j) ; (matmul (+ i k 1) j)
(* (rows (1- i))
(rows (+ i k))
(rows j)))
xlist) )
(apply #'min xlist)) )
))
(dotimes (l mats)
(dotimes (i (- mats l))
(setq j (+ i l))
(setf (aref m i j) (matmul i j))
(if *debug* (print (list i j (aref m i j))))
)
)
(aref m 0 (1- mats))
))
)
|
