Space complexity of a function that builds an n-size array after calling it
I am trying to find out how to estimate the memory complexity of certain functions. And now I have a problem with one weird case.
So, let's say we're building a function like this:
let f x = (fun x -> x :: [1;2;3]);;
And we never call that function, we just compose it with another function at some point using this:
let compose f g x = f (g x);;
So the question is, how much space is required before and after the call? To make this question more general, when f builds an n-dimensional array but is not called, does it still take up O (n) space, or perhaps starts taking that space after being called?
source to share
First of all, notice that it [1;2;3]
is an immutable list, not an array. This affects your space calculations, as lists can share a structure. Second, for the sake of simplicity, I'll talk about things in terms of "conses", two-argument constructors that take three words of memory — in fact, OCaml programs are written in terms of the constructors of many arities.
Looking at f
, it generates one fresh minus per call and links to a list containing three persistent requirements. Assuming constant conses are statically distributed (since ocamlopt
they are), we can use these observations to write a rough equation for the use of space.
conses_used = 3 + 1 * reachable-results-of f
"Achievable result" means a value created f
and still visible in the program. The unreachable parts are ignored as the GC will fix them.
When doing this kind of assessment, make sure you understand that the cons are constant when all parts of it are constant (and no part is changed). If the tail minus is a list with some non-constant part, then the minuses are non-constant.
That is, in the following
let f x = [1;2;3;x]
no permanent considerations - all four will stand out every time through f
.
source to share