CODEWITHSUNDEEP
ruby
Dan Rubio
Dan Rubio

Reputation: 4907

Execution Timed Out (12000 ms): How can I optimize this simple kata to run faster?

I'm practicing my coding chops after a long break and ran into this kata on CodeWars

With an input of numbers in an array, return the sums of its parts. So for example:

def parts_sums(ls)
 sums = []
  until ls.size == 0
    sums << ls.inject(:+)
    ls.shift
  end
  sums << 0
end

######### INPUT #######
parts_sums([0, 1, 3, 6, 10])

######### EXPECTED OUTPUT ######
[20, 20, 19, 16, 10, 0]

0 + 1 + 3 + 6 + 10 = 20
1 + 6 + 3 + 10 = 20
3 + 6 + 10 = 19
6 + 10 = 16
10 = 10 
0 = 0

My solution solves the kata, however once I reach arrays of around 30,000+ my solution takes too long to solve.

So my question is to the community, how would I even attempt to make this go faster. I know that recursion is usually slow, and that for loops and its variants are usually sufficient to get the job done. What happens when that fails? What are some things to try to make my code above faster?

I'm looking for some advice and some examples if anyone has any. Appreciate the input. Thanks.

Upvotes: 0

Views: 4140

Answers (3)

Cary Swoveland
Cary Swoveland

Reputation: 110695

def parts_sums(ls)
  ls.each_with_object([ls.sum]) { |n,arr| arr << arr.last - n }
end

parts_sums([0, 1, 3, 6, 10])
  #=> [20, 20, 19, 16, 10, 0]

Upvotes: 3

max pleaner
max pleaner

Reputation: 26778

This version of the function runs much faster:

def parts_sums_2(ls)
 sums = []
 last_sum = 0
 (ls.length - 1).downto(0).each do |i|
   last_sum += ls[i]
   sums.prepend last_sum
 end
 sums + [0]
end

The key here is going backwards through the array - starting with the smallest sum (only the last element). Each subsequent step moves one index towards the beginning, and adds that value to the previous sum.

Since the problem statement requires you to shift each step, your result must have the largest sums at the beginning, even though these are the last ones to be computed. This is why my code uses prepend rather than push.

This is O(N) time complexity instead of O(N^2), which is an order of magnitude difference.

With 100_000 inputs, your original function took 7.040443 seconds, while mine here took 0.000008 seconds

Also in general you should try to avoid mutating the input to your methods (as you were doing with shift).

Upvotes: 0

Valery Zajkov
Valery Zajkov

Reputation: 51

The issue with the code is that you are performing an inject on every iteration of your loop, which is unnecessarily slow.

You only need to sum the elements of the array once, outside of any loop. Once you have that sum, you can iterate through the elements of the array and perform a constant time subtraction from the current sum and push it into the sums array. 

def part_sums(ls)
  sum = ls.inject(:+)
  sums = [sum]
  ls.each do |val|
    sum -= val
    sums << sum
  end
  sums
end

There is also no need to shift, if you iterate through the array with the each iterator or keep a counter and use a while loop.

Upvotes: 2

Related Questions