huge difference in memory usage

Question

I have two pieces of code that do exactly the same thing. However, the memory consumption is very different in the two approaches, and I cannot figure out the reason.

Here is the code:

nMax = 10
attemptOne = Sum[ Total @ i  , {i , Subsets[Range @ nMax, {4}]}];
attemptTwo = Sum[Total[{i , j , k , l}], {l, 4, nMax}, {k, 3, l - 1}, {j, 2, k - 1}, {i, 1, j - 1}]

When I check the memory consumption the difference is huge:

In[11]:= MaxMemoryUsed[
 Sum[ Total @ i  , {i , Subsets[Range @ nMax, {4}]}]]

Out[11]= 17864

In[12]:= MaxMemoryUsed[
 Sum[Total[{i , j , k , l}], {l, 4, nMax}, {k, 3, l - 1}, {j, 2, 
   k - 1}, {i, 1, j - 1}]]

Out[12]= 1192

Can anybody explain this behavior? I would like to write my code using an approach like attemptOne, since this is easy to generalize to sublists of length different from 4.

UPDATE: probably the reason is simply that in attemptOne the code first generates all the subsets and then does the evaluation. So it stores all the tuples in memory, while in the second approach it creates one tuple at a time and saves memory.

Can somebody confirm that my intuition is correct?

Answer 1

Yes, the reason for the greater memory use is that your attemptOne generates the entire set of subsets before performing the summation. Keep in mind that those are bytes used, so the entire list only took up 18 kB so it's not very big. But depending on how large you want nMax and how long the subsets should be, it's possible that the memory use could end up quite large.

If your sets are small enough, I would recommend using the second argument of Total for attemptOne:

nMax = 10;
Total[Subsets[Range@nMax, {4}], 2]

If your sets might be huge, you can generate them one at a time:

nMax = 10;
size = 4;
total = 0;
Do[
  total += Total[Subsets[Range@nMax, {size}, {i}], 2],
  {i, Binomial[nMax, size]}
]

This isn't the cleanest looking way to do it, but since the subset is generated just in time, I think the memory requirement should never go beyond a few kB.

EDIT:

It looks like Henrik's solution is much more elegant, but I was also thinking there should be some way of calculating the total without ever generating any of the sets.

nMax = 10;
size = 4;
Binomial[Range[nMax - 1, size - 1, -1], size - 1].Range[nMax - size + 1]*Total[Range[size]]

Answer 2

Yes, the list of subsets has to generated first and stored somewhere. This is why attemptOne uses more time and memory, namely $k\, O({n \choose k})$ of both.

I had the same idea as MassDefect, but I was a couple of seconds too slow. So I had to come up with another solution:

Let $M$ be a set of size $n$. Then there are $n \choose k$ subsets of size $k$. And for symmetry reasons, each element of $M$ appears the same number of times among all these subsets in total, namely $\frac{k}{n} {n \choose k} = {n -1 \choose k-1}$ times. So if $M$ is a set of numbers, the sum over all elements in all subsets must be ${n -1 \choose k-1} \sum_{m \in M} m$. So it is easy to compute the sum without any looping construct in $O(n)$ time and $O(1)$ memory (assuming that computing ${n -1 \choose k-1}$ requires $O(1)$ time and memory):

n = 20;
k = 10;
set = RandomSample[1 ;; 100, n];

a = Total[Subsets[set, {k}], 2]; // MaxMemoryUsed // AbsoluteTiming
b = Total[set] Binomial[n - 1, k - 1]; // MaxMemoryUsed // AbsoluteTiming
a == b

{0.338788, 31040024}

{0.000018, 392}

True

For a list $M$ of $n$ consecutive numbers, this can be done in $O(1)$ time by virtue of Gauß' formula.

Lesson to learn: Brain power can save a lot of runtime and memory.