Matrix chain multiplication: Difference between revisions
Added 11l
m (→{{header|J}}: spacing) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 27:
__TOC__
=={{header|11l}}==
{{trans|Nim}}
<lang 11l>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(‘’)</lang>
{{out}}
<pre>
Dims: [5, 6, 3, 1]
Order: (A(BC))
Cost: 48
Dims: [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
Order: ((((((((AB)C)D)E)F)G)(H(IJ)))(KL))
Cost: 38120
Dims: [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
Order: (A((((((BC)D)(((EF)G)H))I)J)K))
Cost: 1773740
</pre>
=={{header|Ada}}==
| |||