 This page contains automated test results for code from O'Reilly's Ruby Cookbook. If this code looks interesting or useful, you might want to buy the whole book.

Multiplying Matrices
CodeExpectedActual
```require 'matrix'
require 'mathn'
a1 = [[1, 1, 0, 1],
[2, 0, 1, 2],
[3, 1, 1, 2]]
m1 = Matrix[*a1]```
Matrix[[1, 1, 0, 1], [2, 0, 1, 2], [3, 1, 1, 2]] Matrix[[1, 1, 0, 1], [2, 0, 1, 2], [3, 1, 1, 2]]
```a2 = [[1, 0],
[3, 1],
[1, 0],
[2, 2.5]]
m2 = Matrix[*a2]```
Matrix[[1, 0], [3, 1], [1, 0], [2, 2.5]] Matrix[[1, 0], [3, 1], [1, 0], [2, 2.5]]
`m1 * m2`
Matrix[[6, 3.5], [7, 5.0], [11, 6.0]] Matrix[[6, 3.5], [7, 5.0], [11, 6.0]]
```class Matrix
def Matrix.multiply(*matrices)
cache = []
matrices.size.times { cache << [nil] * matrices.size }
best_split(cache, 0, matrices.size-1, *matrices)
multiply_following_cache(cache, 0, matrices.size-1, *matrices)
end
:private
def Matrix.multiply_following_cache(cache, chunk_start, chunk_end, *matrices)
if chunk_end == chunk_start
# There's only one matrix in the list; no need to multiply.
return matrices[chunk_start]
elsif chunk_end-chunk_start == 1
# There are only two matrices in the list; just multiply them together.
lhs, rhs = matrices[chunk_start..chunk_end]
else
# There are more than two matrices in the list. Look in the
# cache to see where the optimal split is located. Multiply
# together all matrices to the left of the split (recursively,
# in the optimal order) to get our equation's left-hand
# side. Similarly for all matrices to the right of the split, to
# get our right-hand side.
split_after = cache[chunk_start][chunk_end]
lhs = multiply_following_cache(cache, chunk_start, split_after, *matrices)
rhs = multiply_following_cache(cache, split_after+1, chunk_end, *matrices)
end
# Begin debug code: this illustrates the order of multiplication,
# showing the matrices in terms of their dimensions rather than their
# (possibly enormous) contents.
if \$DEBUG
lhs_dim = "#{lhs.row_size}x#{lhs.column_size}"
rhs_dim = "#{rhs.row_size}x#{rhs.column_size}"
cost = lhs.row_size * lhs.column_size * rhs.column_size
puts "Multiplying #{lhs_dim} by #{rhs_dim}: cost #{cost}"
end
# Do a matrix multiplication of the two matrices, whether they are
# the only two matrices in the list or whether they were obtained
# through two recursive calls.
return lhs * rhs
end
def Matrix.best_split(cache, chunk_start, chunk_end, *matrices)
if chunk_end == chunk_start
cache[chunk_start][chunk_end] = [0, nil]
end
return cache[chunk_start][chunk_end] if cache[chunk_start][chunk_end]
#Try splitting the chunk at each possible location and find the
#minimum cost of doing the split there. Then pick the smallest of
#the minimum costs: that's where the split should actually happen.
minimum_costs = []
chunk_start.upto(chunk_end-1) do |split_after|
lhs_cost = best_split(cache, chunk_start, split_after, *matrices)
rhs_cost = best_split(cache, split_after+1, chunk_end, *matrices)
lhs_rows = matrices[chunk_start].row_size
rhs_rows = matrices[split_after+1].row_size
rhs_cols = matrices[chunk_end].column_size
merge_cost = lhs_rows * rhs_rows * rhs_cols
cost = lhs_cost + rhs_cost + merge_cost
minimum_costs << cost
end
minimum = minimum_costs.min
minimum_index = chunk_start + minimum_costs.index(minimum)
return cache[chunk_start][chunk_end] = [minimum, minimum_index]
end
end
class Matrix
# Creates a randomly populated matrix with the given dimensions.
def Matrix.with_dimensions(rows, cols)
a = []
rows.times { a << []; cols.times { a[-1] << rand(10) } }
return Matrix[*a]
end
# Creates an array of matrices that can be multiplied together
def Matrix.multipliable_chain(*rows)
matrices = []
0.upto(rows.size-2) do |i|
matrices << Matrix.with_dimensions(rows[i], rows[i+1])
end
return matrices
end
end```
`Create an array of matrices 100x20, 20x10, 10x1.`
`chain = Matrix.multipliable_chain(100, 20, 10, 1)`
`Multiply those matrices two different ways, giving the same result.`
`Matrix.multiply(*chain) == (chain * chain * chain)`
```Multiplying 20x10 by 10x1: cost 200
Multiplying 100x20 by 20x1: cost 2000
We'll generate the dimensions and contents of the matrices randomly,
so no one can accuse us of cheating.```
```dimensions = []
10.times { dimensions << rand(90)+10 }
chain = Matrix.multipliable_chain(*dimensions)
require 'benchmark'
result_1 = nil
result_2 = nil
Benchmark.bm(11) do |b|
b.report("Unoptimized") do
result_1 = chain
chain[1..chain.size].each { |c| result_1 *= c }
end
b.report("Optimized") { result_2 = Matrix.multiply(*chain) }
end```
```user     system      total        real
Unoptimized  4.350000   0.400000   4.750000 ( 11.104857)
Optimized    1.410000   0.110000   1.520000 (  3.559470)
Both multiplications give the same result.```
```user     system      total        real
Unoptimized  2.970000   0.290000   3.260000 (  4.266516)
Optimized    2.540000   0.220000   2.760000 (  4.013971)```
`result_1 == result_2`
true true