40 lines
1.1 KiB
Text
40 lines
1.1 KiB
Text
T Optimizer
|
||
[Int] dims
|
||
[[Int]] m, s
|
||
|
||
F (dims)
|
||
.dims = dims
|
||
|
||
F findMatrixChainOrder()
|
||
V n = .dims.len - 1
|
||
.m = [[0] * n] * n
|
||
.s = [[0] * n] * n
|
||
|
||
L(lg) 1 .< n
|
||
L(i) 0 .< n - lg
|
||
V j = i + lg
|
||
.m[i][j] = 7FFF'FFFF
|
||
L(k) i .< j
|
||
V cost = .m[i][k] + .m[k + 1][j] + .dims[i] * .dims[k + 1] * .dims[j + 1]
|
||
I cost < .m[i][j]
|
||
.m[i][j] = cost
|
||
.s[i][j] = k
|
||
|
||
F optimalChainOrder(i, j)
|
||
I i == j
|
||
R String(Char(code' i + ‘A’.code))
|
||
E
|
||
R ‘(’(.optimalChainOrder(i, .s[i][j]))‘’
|
||
‘’(.optimalChainOrder(.s[i][j] + 1, j))‘)’
|
||
|
||
V Dims1 = [5, 6, 3, 1]
|
||
V Dims2 = [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
|
||
V Dims3 = [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
|
||
|
||
L(dims) [Dims1, Dims2, Dims3]
|
||
V opt = Optimizer(dims)
|
||
opt.findMatrixChainOrder()
|
||
print(‘Dims: ’dims)
|
||
print(‘Order: ’opt.optimalChainOrder(0, dims.len - 2))
|
||
print(‘Cost: ’opt.m[0][dims.len - 2])
|
||
print(‘’)
|