I’m curious about the difference in space complexity between map and map! in ruby.
If I have the methods:
def mult_by_two(arr)
arr.map {|i| i * 2 }
end
def mult_by_two!(arr)
arr.map! {|i| i * 2 }
end
While there’s no explicit assignment in the first method, it’s implicitly collecting the result of the map somewhere and is not operating in-place like the second method.
Would it be correct to say that the first has O(n) auxiliary space complexity while the second is O(1)? How should I represent them when looking at the auxiliary space complexity of a method?
The answer is hidden in the source of the page Ruby-doc: Core Array
If one goes to Ruby-doc: Core Array#map or Ruby-doc: Core Array#map! and mouses over the block, they will see
Clicking the ‘click to toggle source’ then gives us the C source code that implements the method in the interpreter.
For map the code is:
collect = rb_ary_new2(RARRAY_LEN(ary));
for (i = 0; i < RARRAY_LEN(ary); i++) {
rb_ary_push(collect, rb_yield(RARRAY_AREF(ary, i)));
}
For map! the code is:
rb_ary_modify(ary);
for (i = 0; i < RARRAY_LEN(ary); i++) {
rb_ary_store(ary, i, rb_yield(RARRAY_AREF(ary, i)));
}
One can clearly then see that map allocates a new array of the length of the original array and pushes the values that are used into this array while map! stores the value in the initial array.
Thus, you are correct – map uses O(n) auxiliary space while map! uses O(1) (none at all).
array.map: “Invokes the given block once for each element of self. Creates a new array containing the values returned by the block.”.
array.map!: “Invokes the given block once for each element of self, replacing the element with the value returned by the block.”.
The first allocates a new array of the same size, the second does not. The “space complexity” of both are exactly the same: O(1). The “auxiliary space usage” of map is O(N), for map! is O(1).
The main reason to use map! is to avoid the extra allocation which eventually has to be garbage collected.