3
\$\begingroup\$

I'm trying to find all possible product of two 3-digit numbers. When I work with small ranges, I'm able to get an output almost instantly but when the ranges are big, it seems to take really long time. I ran the code below and still didn't get an output past 15 minutes. Is there any way to to shorten the time to get the result?

a = []
for x in 100..999
    for y in 100..999
        num = (x * y)
        unless a.include? num
            a.push num
        end
    end
end

p a
\$\endgroup\$
1
  • \$\begingroup\$ It could also be useful to know the next step. If there's something specific that you are planning to do with these products, you may not need to build an array at all. \$\endgroup\$
    – icy
    Sep 15, 2014 at 22:10

5 Answers 5

6
\$\begingroup\$

Performance

Your code is slow because your algorithm is \$O(n^4)\$, where \$n = 900\$:

  • The outer x loop runs for 900 iterations (\$O(n)\$).
  • For every x, the y loop runs for 900 iterations (\$O(n)\$).
  • For every product, you search the array to see if the entry already exists. Since the length of the array will grow up to \$O(n^2)\$, and .include? does a linear search, the deduplication takes \$O(n^2)\$ time.

You can cut the time in half by taking advantage of the fact that \$x \cdot y = y \cdot x\$. The big win, though, would be to store the results in a Set, which performs deduplication for "free". That would bring your runtime down to \$O(n^2)\$.

Style

The standard indentation width for Ruby is two spaces.

The parentheses around (x * y) are superfluous. However, parentheses for the parameter to .include? would be considered good practice.

\$\endgroup\$
1
\$\begingroup\$

You are doing redundant extra work, this way you don't have to check if the item is already there :

a = []
for x in 100..999
  for y in x..999
    num = (x * y)
      a.push num
  end
end

a.uniq!

p a
\$\endgroup\$
1
\$\begingroup\$

A functional, concise, space-efficient implementation of the points made in @user50399's answer could be (Ruby >= 2.0):

require 'set'
products = (100..999).lazy.flat_map { |x| (x..999).map { |y| x*y } }.to_set
\$\endgroup\$
0
1
\$\begingroup\$

Here's how the answers posted to date compare in execution speed. [Edit: I updated the results to include another method.

The methods

require 'matrix'
require 'set'

elios264

def elios264(r)
  a = []
  for x in r
    for y in (x..r.last)
      num = (x * y)
        a.push num
    end
  end
  a.uniq!
end

tokland

def tokland(r)
  r.lazy.flat_map { |x| (x..r.last).map { |y| x*y } }.to_set
end

cary1

def cary1(r)
  a = [*r]
  (Matrix::column_vector(a) * Matrix::row_vector(a)).to_a.flatten.uniq
end

cary2

def cary2(r)
  f, l = r.first, r.last 
  fpl = f+l
  m = fpl/2
  ml = m+1
  mf = fpl.odd? ? m : m-1 
  arr = (f..mf).each_with_object([]) { |i,a| p = i*fpl;
    (i..mf).each { |j| n = i*j; a << n << p-n } }
  (ml..l).each { |i| p = i*fpl;
    (ml..i).each  { |j| n = i*j; arr << n << p-n } }  
  if (fpl).even?
    p = m*fpl
    (f..mf).each { |i| n = i*m; arr << n << p-n }
    arr << m*m
  end
  arr.uniq
end

The benchmark

Benchmark.bm('elios264'.size) do |bm|
  r = (100..999)
  bm.report 'elios264' do
    elios264(r)
  end
  bm.report 'tokland' do
    tokland(r)
  end
  bm.report 'cary1' do
    cary1(r)
  end
  bm.report 'cary2' do
    cary2(r)
  end
end

The results

               user     system      total        real
elios264   0.280000   0.010000   0.290000 (  0.298585)
tokland    0.320000   0.010000   0.330000 (  0.322057)
cary1      1.160000   0.010000   1.170000 (  1.174107)
cary2      0.210000   0.010000   0.220000 (  0.221317)

The results for elios264 were only slightly different when uniq! is changed to uniq.

\$\endgroup\$
1
\$\begingroup\$

Here are two other approaches.

#1

You could use methods from the Matrix class:

require 'matrix'

def unique_products(r)
  a = [*r]
  (Matrix::column_vector(a) * Matrix::row_vector(a)).to_a.flatten.uniq
end

unique_products((1..4))
  #=> [1, 2, 3, 4, 6, 8, 9, 12, 16]

The class methods Matrix::column_vector and Matrix::row_vector are used to convert r1 to a column vector and r2 to a row vector. Matrix#* is then used to compute the outer product, a matrix that contains the products of all pairs of elements from the two ranges. That matrix is then converted to an array, flattened and uniq'ed, to eliminate duplicates.

Compared to approaches that do not use matrix methods, this one has some extra steps and greater memory requirements. However, the computation of the outer product, being implemented in C, should be relatively fast. Whether this method is faster than other methods is an empirical question. (Edit: the benchmark showed this method to be relatively slow.)

#2

The second approach employs a bit of fine tuning to boost performance:

def cary2(r)
  f, l = r.first, r.last 
  fpl = f+l
  m = fpl/2
  ml = m+1
  mf = fpl.odd? ? m : m-1 
  arr = (f..mf).each_with_object([]) { |i,a| p = i*fpl;
    (i..mf).each { |j| n = i*j; a << n << p-n } }
  (ml..l).each { |i| p = i*fpl;
    (ml..i).each  { |j| n = i*j; arr << n << p-n } }  
  if (fpl).even?
    p = m*fpl
    (f..mf).each { |i| n = i*m; arr << n << p-n }
    arr << m*m
  end
  arr.uniq
end

Let f and l be the range endpoints, and let m be the average:

m = (f+l)/2

There are two cases to consider, depending on whether f+l is even or odd. The easier of the two is when it is odd. Suppose, for example, f=1 and l=6, so m=3 and f+l is odd. In this case the range can be divided into (1..3) and (4..6). Let a be the array that will hold the products. When calculating:

(1..3).each { |i| (i..3).each { |j| a << i*j }

we can also calculate:

(1..3).each { |i| (i..3).each { |j| a << i*(l-(j-f)) }

which is:

(1..3).each { |i| (i..3).each { |j| a << i*(f+l) - i*j }

We can combine these as follows:

fpl = f+l
(1..3).each { |i| p = i*fpl; (i..3).each { |j| n = i*j; a << n << p-n }

Similarly, for

(4..6).each { |i| (4..i).each { |j| a << i*j }

we can also calculate:

(4..6).each { |i| (4..i).each { |j| a << i*(f+(l-j) }

which is:

(4..6).each { |i| (4..i).each { |j| a << i*(f+l) - i*j }

so we can write:

(4..6).each { |i| p = i*fpl; (4..i).each { |j| n = i*j; a << n << p-n }

These two expressions cover all the products.

If f+l is even, the situation is slightly more complex. Suppose f=1 and l=5, so f+l = 6 and m = 3. In this case we will perform the same calculations as above, but for (1..2) and (4..5). We must then add the combinations involving the midpoint, 3. An efficient way to do this is as follows:

p = 3*(1+5)
(1..2).each { |i| n = i*3; arr << n << p-n }
arr << 3*3
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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