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 | ||
---|---|---|
Code | Expected | Actual |
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][1] 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)[0] rhs_cost = best_split(cache, split_after+1, chunk_end, *matrices)[0] 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[0] * chain[1] * chain[2]) |
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[0] 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 |