5
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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]]
| improve this answer | |
$\endgroup$
10
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Neat! I thought this was probably something well studied already, but I didn't know what the formula should be. I don't think the n in your definition of b is needed (the n at the end, I mean). $\endgroup$ – MassDefect May 27 at 4:44
  • 1
    $\begingroup$ Uh, that's a typo indeed. Thank you! Anyways, there are many applications of computing some average over all subsets where one cannot come up with such a simple formula. And since we ask here for minimal examples, it is possible that OP meant to give a simple example of a more complicated problem. So there is even more value in learning about the three-argument version of Subsets. $\endgroup$ – Henrik Schumacher May 27 at 4:55
  • $\begingroup$ Thanks, guys (@MassDefect)! Both answers are very nice. Henrik's answer is super elegant but, as he was guessing, the particular case I posted was just a very simple example, and I am not sure that I can find a simple formula in the more complicated cases I have in mind. So learning about the three-argument Subsets has been important! Can I vote both the answers? $\endgroup$ – Dario Rosa May 27 at 5:47
  • 2
    $\begingroup$ +1 for the phrase "Lesson to learn: Brain power can save a lot of runtime and memory." alone :) And of course for a nice answer as always. $\endgroup$ – Marius Ladegård Meyer May 27 at 6:36
  • 1
    $\begingroup$ The hat-tip to Gauß was a nice touch. ;) $\endgroup$ – J. M.'s discontentment May 27 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.