3
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.