Iterate over a loop to calculate a sum, or update a sum variable as items are added and deleted from a list? [closed]

Question

I thought I ran into this concept at one point but can't figure out how to find an answer for it.

Is it better to iterate over a list of ints to calculate a running sum each frame, or is it better to create a variable to hold the sum and to increase or decrease it as numbers are added to the list?

The only downside I see for keeping a sum variable around is that you have to make sure you really update it correctly in all niche cases that might appear. Or ensure that items are removed from the list correctly, say, on death.

Answer 1

First rule of optimization: profile first!

Computing a sum each frame instead of updating it could be seen as a waste of CPU time, but it might be negligeable compared to all computation done each frame, so optimizing it would result in no visible result. Plus, determining if it is to be updated can require the same amount of CPU time.

If that's the case, adopt the method that you're more comfortable with, is easier to write (without bugs, of course), to read (readability is very important, I'd take readability over premature optimization every day) and to maintain.
If your case, you're mentionning niche cases. That alone is a big threat for write code without bugs and for maintainability.

In conclusion, I would iterate and compute the sum from zero in each frame. Only if I found that it is a potential performance bottleneck, I'd try to find a less CPU-consuming method. Once again: profile first!. This reasoning must be performed again in each case, and not applied everytime without thinking about it.

Answer 2

Regardless of the approach, you will need code with the responsibility to do it correctly. And you want that code to be in a single place.

Why a single place? On one hand, if it has any bug, you only have to fix it there. On the other, if you want to optimize your code, you only have to do it there. Having the code responsible of this in a single place is what enables you to start with a subpart implementation and optimize it later.

Thus, make a class. The only way to access and modify the list should be through the class, making it imposible to do it wrong or forget doing it somewhere. How you compute the sum, is an implementation detail.

Oh, by the way, if you find yourself needing this code somewhere else, a class is easy to reuse. By properly encapsulating you will need to solve this problem less often. In fact, for problems that come very often, it is faster to find a third party library.

---

I like the idea of making more performant software by default (with the fall of Moore's law and all)… YAGNI. Probably. Implement the one you find simpler and easier to read. If your performance is poor (profile), then optimize it.

---

With that said, let us pretend you have decided that this part of the code has bad performance, what can we do?

I give you these guidelines:

• Not doing something is faster than doing it.
• If you need it done, do it later.
• If you need it done right away, do it less often. Can you reuse results?
• If you need it done often, have a third party solution deal with it.
• If you have to do it, then do it faster.

So, what happens less often? Adding and removing elements or querying the sum?

If you query the sum more often than you add or remove items, you don't want to compute the sum each time. The guideline suggest to update the sum when items are added or removed. That way you can have the value already computed and return it.

On the other hand, when you add and remove items more often than you query the sum, the guideline suggests to compute the sum when you query it.

---

There is a third way: you can do it lazily (doing it later). Have cached sum value. Store a bool that tells you if that cached sum is valid or not. If it is, then just return it. If it isn't, then compute it again, mark it valid, and return it. When you add or remove an item, you mark it invalid.

We can actually make it more complicated: keep track of what items has been added or removed since the last computation. There is a word for that: overengineering.

By the way, you could have a not thread-safe solution. Let me rephrase that: you almost certainly have a not thread-safe solution unless you intentionally made it so and know what you are doing.

There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors.

-- Leon Bambrick

---

Or, you know, you could not do it. Chances are that whatever solution you come up with is fine, and never shows up as a problem in profiling. We don't only want to optimize the code, but also the development process. Remember the guidelines.

Also remember that premature optimization something something.

Answer 3

As with most things, and similar to the other answers: it depends.

The important thing here (appart from the well put points about not premeturely optimizing) is to consider how often this calculation needs to be performed - and how many times, and in how many places the total is needed:

As a baseline, to calcualte the total, at a minimum we will need:

• An accumulator variable
• To add each element to this once.

So the total number of operations to calculate the total once is independant of the implementation (more or less).

Whether we do soemting like this psuedocode:

// On our collection
public void AddItem(int item){ this.Items.Add(item);}

// Calculate total later
var total = 0;
foreach(var item in collection){ total += item; }
Console.WriteLine(total);

or something like this:

// On our collection - pre-calculate tpta;
public void AddItem(int item){ this.Total += item; this.Items.Add(item);}

//Use total later
Console.WriteLine(collection.Total);

We still have to perform the same number of steps regardless:

1. Declare a total variable
2. Add to the total N times - once for each item in the list
3. Use the total.

Therefore, the implementations are more or less equivalent, and the important thing to think about is the use case that this will serve.

All other considerations being equal:

• How often / in how many places is the total used?
• If it's used in multiple places, the important thing is not to re-calcualte the total multiple times.
• Can we calcualte the total once (in any way you like) but then share that total with whatever code needs it.
• How often is the list changed or ammended? Does the list change every frame?
  • If infrequently changed, then re-calculating the total when it changes may help.
  • If frequently changed, then re-calculating each time it changes might add extra overhead!