CODEWITHSUNDEEP
rubyperformancebig-o
Juliette Siny
Juliette Siny

Reputation: 1

Why is using inject/reduce more efficient than using map.with_index when working with large collections (in Ruby)?

I was working on a Codewar problem and the method I came up with worked with small arrays, but didn't work for very large arrays.

The solution provided used the inject method, which I assume is more efficient than the combination of map and with_index I had.

However, I'm not sure I understand why the inject method is more efficient than looping. Could someone please shine some light on this?

The problem was the following: Given an array, return an array where each element is the sum of the array's subparts.

Example: array = [0, 1, 3, 6, 10]

I'm summing every array element while iterating on the array (so the array gets smaller and smaller): 

[0, 1, 3, 6, 10] => 20
[1, 3, 6, 10] => 20
[3, 6, 10] => 19
[6, 10] => 16
[10] => 10
[] => 0

Hence the method would return here: [20, 20, 19, 16, 10, 0]

My solution (which works for small arrays but is too inefficient for large arrays):

def parts_sums(ls)
  (ls + [0]).map.with_index { |_, i| ls[i..-1].sum }
end

The provided solution:

def parts_sums(ls)
  ls.reduce([ls.sum]) { |sums, x| sums << sums.last - x }
end

By browsing the Codewars comment section, I've understood that this performance difference is linked to the Big O notation. However, every resource I found on this topic is way beyond my mathematical and algorithm understanding.

I've also looked at the Ruby doc but I don't understand C enough to be able to read the implementation of those methods.

Could someone please explain in quite simple terms why inject/reduce is more efficient than map.with_index in this situation?

Upvotes: 0

Views: 544

Answers (1)

Aleksei Matiushkin
Aleksei Matiushkin

Reputation: 121000

Let’s start with reduce version.

ls.reduce([ls.sum]) { |sums, x| sums << sums.last - x }

It sums an array once (on step zero,) and then it subtracts two integers on each subsequent iteration.

Your solution sums the tail of the array on each step. Summing requires the whole array traversal, that’s why it is quite inefficient on large arrays.

Upvotes: 3

Related Questions