Optimizing Multiplication Table

Question

I have a class that takes an array of integers and produces a multiplication table.

class MultiplicationTable
  def initialize(num_ary)
    @num_ary = num_ary.to_a
  end         

  def generate             
    a1 = @num_ary.clone    
    a2 = @num_ary.clone    

    rows = []              
    rows << a1             

    a2.shift               

    a2.each do |x|         
      cols = [x]           
      a1[1..-1].each do |y|
        cols << (x * y)    
      end                  
      rows << cols         
    end                    

    rows                   
  end                      
end

So this:

MultiplicationTable.new(1.upto(5)).generate

produces this output:

[
  [1, 2, 3, 4, 5],
  [2, 4, 6, 8, 10],
  [3, 6, 9, 12, 15],
  [4, 8, 12, 16, 20],
  [5, 10, 15, 20, 25] 
]

Here are my results from benchmarking:

                         user     system      total        real
100 entry table      0.000000   0.000000   0.000000 (  0.001295)
1,000 entry table    0.120000   0.010000   0.130000 (  0.132325)
10,000 entry table  15.290000   0.380000  15.670000 ( 15.747799)

Is there anything I can do to speedup/improve up this code?

Answer 1

You only need to compute half the table because it is symmetrical; for your line

a1[1..-1].each do |y|

instead do

a1[x..-1].each do |y|

and if you ever need to look up a * b where b > a, instead look up b * a

This will create a multiplication table that looks like this:

# old table
  1  2  3  4  5
1 1  2  3  4  5
2 2  4  6  8 10
3 3  6  9 12 15
4 4  8 12 16 20
5 5 10 15 20 25

# new table
  1 2 3  4  5
1 1 2 3  4  5
2   4 6  8 10
3     9 12 15
4       16 20
5          25

# final multiplication table
arr = [
  [1,2,3,4,5],
  [4,6,8,10],
  [9,12,15],
  [16,20],
  [25]
]

To access a*b where a >= b, the answer is in arr[a-1][b-a]
To access 3*4, the answer is in row 3-1, element 4-3 = arr[3-1][4-3] = arr[2][1] = 12
To access 5*2 (= 2*5), the answer is in row 2-1, element 5-2 = arr[2-1][5-2] = arr[1][3] = 10
To access 100x100 (assuming the range goes high enough), arr[99][0]

You'll need to do something slightly different if you are passing an array that isn't 1..x - in that case, first look up the index of each of the two numbers in the original array and use THEM in the arr[a-1][b-a] lookup. I suspect you'll need to subtract 1 from the indices but I haven't worked it out in my head.

Answer 2

The code is a lot more complicated than it needs to be. This produces the same result with approximately the same performance:

def multiplication_table(size)
  (1..size).collect { |x| (1..size).collect { |y| x * y } }
end

multiplication_table(10000)

As a general rule, most code that appends elements to an empty array in a loop can be simplified using Enumerable#collect.