5
\$\begingroup\$

I need help in optimizing my code for this challenge. I think my algorithm is fine and I pass all sample tests but get took longer than 12000ms to complete error for final one.

I guess there are a lot of unnecessary variables but this is all my beginners Ruby brain could think of. :)

I have started learning coding 2 weeks ago so style-wise this is most certainly horrible.

Kata link

Instructions :

Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum. Negative numbers and duplicate numbers can and will appear.

NOTE: There will also be lists tested of lengths upwards of 10,000,000 elements. Be sure your code doesn't time out.

def sum_pairs(numbers, sum) 
  # Idea was :
  #  1. To iterate over array elements take their sum and add
  #     it to hash if it is equal to "sum". 
  #  2. Sort hash by value to find lowest second parameter since
  #     we need entire pair to be first not just first element.
  #  3. Convert that hash to array so that I could take value 
  #      of those elements and return actual numbers. 
  #     (Didn't know to do it from hash directly :))
  x = 0
  h = {}
  while x < numbers.length
    y = 0
    while y < numbers.length
      sum_test = numbers[x] + numbers[y]
      if sum_test == sum && x != y && x < y
        h[x] = y
      end
      y += 1
    end
    x += 1
  end
  if h.empty?
    return nil
  else
    final_positions = h.sort_by {|key, value| value}.first.to_a
    return numbers[final_positions[0]], numbers[final_positions[1]]
  end
end
\$\endgroup\$
8
\$\begingroup\$

You have two nested while loops, so your solution is O(n2). A good solution should be possible in O(n) — that is, one pass through numbers.

Also, the while loops are rather clumsy. Idiomatic Ruby would usually use #each to iterate, or #each_with_index if you need the indexes as well. Here, you don't care about the indexes. If you return as soon as you have encountered a solution, it will necessarily be the leftmost solution.

require 'set'

def sum_pairs(numbers, sum)
  seen = Set.new
  numbers.each do |n|
    return [sum - n, n] if seen.include?(sum - n)
    seen.add(n)
  end
  nil
end
\$\endgroup\$
  • 1
    \$\begingroup\$ It would be nice to point out that checking whether a set includes something uses hashes and runs in constant time, unlike some alternatives. \$\endgroup\$ – JollyJoker Jun 16 '17 at 9:13
  • \$\begingroup\$ It's very simple solution yet effective one. I just need to figure out why it works :) \$\endgroup\$ – SrdjaNo1 Jun 16 '17 at 10:10
  • \$\begingroup\$ @SrdjaNo1 'seen' includes all the previous numbers. If the sum minus the current number equals any previous number you have a match. \$\endgroup\$ – JollyJoker Jun 16 '17 at 12:23
  • \$\begingroup\$ I retract my earlier statement. This is actually a very elegant solution. It is essentially checking for the second number in the pair by looking at the numbers already passed by to see if they add to the sum. And to manage the size of the numbers seen, it is taking advantage of the automatic deduplication feature of Set. \$\endgroup\$ – Mark Thomas Jun 16 '17 at 12:56
5
\$\begingroup\$

Style Comments:

Whenever you find yourself wanting to do a loop by initializing a variable with a while:

y=0
while y < foo.length
  ...
  y=y+1
end

for more idiomatic Ruby, you generally replace it with the following:

foo.each do |y|
  ...
end

If you need the index, add .with_index:

foo.each.with_index do |y,i|
  ...
end

One thing I recommend for new Rubyists is to try to memorize the methods on Array and Enumerable. That's one of the biggest bangs for the buck if you want to exploit Ruby power.

Performance Comments

As @200_success pointed out, you have two nested loops. Each of which is scanning the entire array, which is essentially a brute force method because you're going to check every combination. In fact, because you didn't start the inner loop at the outer loop's index, you're checking each pair twice (the second time in reverse).

There are several techniques you can employ to speed things up:

  • Keep track of the index of the second item in the pair. You can stop iterating when you get there because there will be no smaller indexes, and the smallest index of the pair "wins."
  • When looking for the second item in the pair, you can whittle down the number of elements you need to check. Start right after the first item, and there's no need to look further than the last index of the pair.
  • Utilize methods such as Array#index to find the index of a particular value. Ruby built-ins are generally your fastest option.

Refactoring

This is more of a from scratch implementation. Let's start by initializing our tracking variables for the last index of the pair's value and the overall "winning" pair (because you can't necessarily stop looking the first time you find a pair).

def sum_pairs(numbers, sum) 
  last_index = numbers.length - 1 
  winning_pair = nil

Now we iterate over all the numbers array, with the index. Also, let's include the optimization where we immediately stop when we get to the last index.

  numbers.each.with_index do |n,i|
    break if i >= last_index

Now let's find the matching pairs. Rather than iterate again, we'll use the Ruby builtin index which will either return an index if there is a match, or nil. Another optimization is to minimize the size of the array we need to find the pair in, by starting after the index of the first pair, and not going any further than the last pair's index (this provides a small improvement, according to the benchmarks below).

    offset = i + 1
    pair = numbers[offset..last_index].index(sum-n)
    next if pair.nil? #no match, move on
    pair += offset #index is relative to the offset, so add it back in

So at this point we've found a match. Check to see if it is a new "winner" by comparing the last pair's index:

    if pair <= last_index
      winning_pair = [n,numbers[pair]]
      last_index = pair
    end

And finally return the winning pair's value. The lack of an explicit return may look weird to you, but it is a common Ruby convention. Ruby returns the value of the last executed statement.

  end

  winning_pair
end

Let's add in the given tests:

#tests
puts [3,7] == sum_pairs([11, 3, 7, 5],       10)
puts [4,2] == sum_pairs([4, 3, 2, 3, 4],      6)
puts nil   == sum_pairs([0, 0, -2, 3],        2)
puts [3,7] == sum_pairs([10, 5, 2, 3, 7, 5], 10)

And when we run it:

true
true
true
true

it works!

Benchmarks

I've benchmarked the original with my two variations and also the answer from @200_success:

pairs = [10, 5, 2, 3, 7, 5, 10, 5, 2, 3, 7, 5, 10, 5, 2, 3, 7, 5, 10, 5, 2, 3, 7, 5, 
         11, 7, 4, 1000, 4, 99, 55, 46, 23, 76, 75, 49, 60, 41, 92, 16, 20, 21, 0, -1]
sum = 21

require 'benchmark'
n = 500000
Benchmark.bm(11) do |x|
  x.report("SrdjaNo1:") {n.times do; sum_pairs(pairs, sum); end}
  x.report("Mark-1:") {n.times do; sum_pairs_mark1(pairs, sum); end}
  x.report("Mark-2:") {n.times do; sum_pairs_mark2(pairs, sum); end}
  x.report("200_success:") {require 'set';n.times do; sum_pairs_200_success(pairs, sum); end}
end

The results:

$ sum_pairs.rb
                  user     system      total        real
SrdjaNo1:   110.953000   0.016000 110.969000 (110.966885)
Mark-1:       7.281000   0.000000   7.281000 (  7.280735)
Mark-2:       7.766000   0.000000   7.766000 (  7.764450)
200_success:  4.156000   0.000000   4.156000 (  4.151558)
\$\endgroup\$
  • \$\begingroup\$ numbers[offset..last_index] and .index(sum-n) both take linear time. Thus, your solution has quadratic performance, just like the original. \$\endgroup\$ – 200_success Jun 16 '17 at 3:48
  • \$\begingroup\$ Your solution doesn't seem to work for some reason for some examples: [4,-2,3,3,4] sum 8, or [0,2,0] sum 0 and [5, 9, 13, -3] sum 10 \$\endgroup\$ – SrdjaNo1 Jun 16 '17 at 10:06
  • \$\begingroup\$ Aha, when the pair was the last item I missed it. Change if pair < last_index to if pair <= last_index \$\endgroup\$ – Mark Thomas Jun 16 '17 at 12:35
  • \$\begingroup\$ @200_success I'm calling index on a subset of the list, just as you are calling include on a subset of the list. Granted, your implementation means that your subset is usually smaller than mine, but if the pair is toward the end of the list, our implementations are a lot closer in speed. \$\endgroup\$ – Mark Thomas Jun 16 '17 at 17:18
3
\$\begingroup\$

I'm not a ruby person, so my answer will be more general. 200_success's answer is way more idiomatic and should perform significantly better due to Set.include' prbably optimized implementation.

I'll also try to make my answer very followable by a beginner

square vs. triangle

First of all let's acknowledge that you don't need to iterate over ALL xand ALL y. because then you'll test x+y and y+x. plus, you have to make a special case for not testing x+x or y+y. think of it this way, suppose we have only 4 numbers. The search space is 4² : 16 potential pairs, but most of them are redundant or even erroneous. Your algorithm performs 16 tests, when 6 are necessary at most. Imagine the search space as a square grid :

000u # 0 :a needed test
00u. # . :a test that's already been made in the other half of the square
0u.. # u : a useless test that may give false positives
u...

we're going to do almost that, but revert the triangle because we need to search the beginning of the table, like this:

0
00
000

all of the hashing you do is useless (and maybe expensive)

when trying to optimize for speed, you need to tune your algorithm so that the first match is the one, instead of finding all matches and trying to recoup after the fact. We'll see how

ruby (with my limited knowledge, may be buggy)

this is very much like success_200's version, but I removed the Set (it is certainly faster but may be confusing to beginners)

def sum_pairs(numbers, sum)
  numbers[1..numbers.length-1].each.with_index do |x,i|
    # notice we iterate from the second item
    # (the first would be compared zero times)
    # beware of a possible confusion : here i is not x's
    # index in numbers, but in numbers[1...],
    # so for the second number, i is 0
    num = sum - x # let's only compute this once :)
    numbers[0..i].each |y| #we look _back_ to be sure to find the first pair
      return [y, x] if y == num #instead of x + y == sum
    end
  end
  return nil #nothing to find
end
\$\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.