###### Books / Patterns for Beginning Programmers / Chapter 16

# Accumulators

In some situations, the iterations of a loop are independent of each other. However, in many situations a program needs to “keep track of” something over the course of multiple iterations. In situations like these, accumulators often come into play.

## Motivation

If you ask someone “on the street” how to add a column of numbers by
hand, they will probably say something like “just add them up”. If you
then ask them to demonstrate with a column of fifty **single-digit**
numbers, they probably won’t have any trouble. However, if you talk to
them while they’re doing it (especially if you drop some numbers into
the conversation), they’ll have much more difficulty, and may not be
able to do it at all.

If you then suggest that they “write things down” as they go, there’s a good chance that they won’t know what you mean and/or how that would help. The reason is that, when adding single-digit numbers, people use their brain both to add pairs of numbers and to store the result, and they can’t imagine how to use paper for storage. However, as you know, when writing a program you must carefully differentiate between the two.

## Review

Suppose you need to write a program that operates on all of the elements
of an array of numbers (e.g., `double`

values). You will immediately
recognize that you need to use a loop. Hopefully, because it’s a
*determinate* (or *definite*) loop (i.e., the number of iterations is
known), you will also recognize that you should use a `for`

loop.

For example, given an array named `data`

that contains `n`

elements, you
might start with code like the following:

```
for (int i = 0; i < n; i++) {
// Do something with data[i]
}
```

To go from here to a program that calculates the sum, you need to think
about what needs to be done with each element of the array (i.e., each
`data[i]`

in the example) in order to calculate the sum.

## Thinking About The Problem

Returning to the person on the street, suppose you again ask them to
find the sum of fifty single-digit numbers and describe what they are
doing while they are doing it. Suppose further that the numbers start
with 7, 3, and 2. Most likely, they will say something like “7 plus 3 is
10, plus 2 is 12, …”. Which is to say, they will use what is commonly
called a *running total*.

If you now point this out to them, they will probably be able to use a
piece of paper to store the running total, rather than their brain. This
is exactly the same technique that you need to use when writing a
program for this purpose. That is, you need a variable, called an
*accumulator*, to store the running total.

## The Pattern

The accumulator pattern involves declaring a variable of appropriate type in which the running value can be stored, initializing this variable to an appropriate value, and then using the updating pattern from Chapter 2 to (potentially) change the value each iteration.

In the context of finding the sum of an array of `double`

values, this
pattern is realized as follows:

```
double total;
int n;
n = data.length;
total = 0.0;
for (int i = 0; i < n; i++) {
total += data[i];
}
```

In this realization, `total`

is declared to be a `double`

because the
sum of an array of `double`

values is a `double`

, it is initialized to
`0`

because the sum of an array containing no elements is zero, and at
each iteration `total`

is increased by the value of `data[i]`

.

## Examples

An accumulator can be of almost any type and can be used for a variety of different purposes. Several examples should make the flexibility of this pattern apparent.

### Numeric Examples

In addition to finding the sum, numeric accumulators can be used for many other purposes. For example, you can use a numeric accumulator to find either the minimum or the maximum of an array of double values. This is illustrated for the maximum below:

```
double maximum;
int n;
n = data.length;
maximum = Double.NEGATIVE_INFINITY;
for (int i = 0; i < n; i++)
if (data[i] > maximum) maximum = data[i];
}
```

The accumulator (now named `maximum`

) is initialized to the lower bound
on `double`

values (which is defined in a static attribute of the
`Double`

class named `Double.NEGATIVE_INFINITY`

), and it is only updated
at iteration `i`

if `data[i]`

is greater than the running maximum that
has been found so far.

### Boolean Examples

Boolean accumulators are commonly used for containment checks (i.e., to
determine if an array contains a particular target value). The following
example determines if the `double`

value named `target`

equals any
element of the `double`

array named `data`

:

```
boolean found;
int n;
n = data.length;
found = false;
for (int i = 0; ((i < n) && !found); i++) {
if (target == data[i]) found = true;
}
```

The accumulator in this case is the `boolean`

variable named `found`

. It
is important to note that this method does not assign `false`

to `found`

when `target`

does not equal `data[i]`

, as this is the default value of
`found`

. Note also that, though it isn’t necessary to do so, this method
breaks out of the loop as soon as `found`

is `true`

. It other words, it
only iterates as long as both `i < n`

evaluates to `true`

and `!found`

evaluates to `true`

.

### Examples with Multiple Accumulators

Sometimes it is convenient or even necessary to use two accumulators in
the same loop. In the following example, one accumulator named `total`

contains the running total, and another accumulator named `lowest`

contains the running minimum:

```
double lowest, result, total;
int n;
n = data.length;
total = 0.0;
lowest = Double.POSITIVE_INFINITY;
for (int i = 0; i < n; i++) {
total += data[i];
if (data[i] < lowest) lowest = data[i];
}
result = (total - lowest) / (n - 1);
```

It then returns the mean of the elements of the array after having dropped the minimum. While one could accomplish the same thing using two loops (one to calculate the running total and one to calculate the minimum), it is much more elegant to use one loop and two accumulators.

As another example, suppose you want to find **not** the maximum of an
array, but, instead, the index of the largest element (often called the
*argmax*, the argument that maximizes the “function”, as opposed to the
*max*). One way to do this is to use one accumulator to keep track of
the maximum and another to keep track of its index as follows:

```
double maximum;
int index, n;
n = data.length;
maximum = Double.NEGATIVE_INFINITY;
index = -1;
for (int i = 0; i < n; i++) {
if (data[i] > maximum) {
index = i;
maximum = data[i];
}
}
```

## A Warning

Some people like to initialize the accumulator to a “smarter” value. For example, when calculating the running total, some people like to initialize the accumulator to the 0th element of the array rather than 0 as follows:

```
double total;
int n;
n = data.length;
// Initialize to element 0
total = data[0];
// Start with element 1
for (int i = 1; i < n; i++) {
total += data[i];
}
```

The purported advantage of this approach is that there is one less iteration of the loop.

As another example, when calculating the maximum, some people like to
initialize the accumulator to the 0th element of the array rather than
`Double.NEGATIVE_INFINITY`

as follows:

```
double maximum;
int n;
n = data.length;
// Initialize to element 0
maximum = data[0];
// Start with element 1
for (int i = 1; i < n; i++) {
if (data[i] > maximum) maximum = data[i];
}
```

Again, this has the advantage of one fewer iterations. It also has the
advantage of not having to treat `Double.NEGATIVE_INFINITY`

as a special
case.

The shortcoming of this approach is that arrays of length `0`

must be
treated as a special case. That is, if the array contains no elements,
then initializing the accumulator to element `0`

of the array will throw
an exception (at run-time) when the array has no elements. Hence, one
must **first** check to ensure that the array has a length of at least
`1`

.

In some circumstances, this may be worthwhile. For example, the argmax
code can be written using just the accumulator named `index`

by changing
the initialization and the expression in the `if`

statement as follows:

```
double maximum;
int index, n;
n = data.length;
// Initialize to element 0
index = 0;
// Start with element 1
for (int i = 1; i < n; i++) {
if (data[i] > data[index]) index = i;
}
```

Whether this trade-off is worthwhile is a matter of personal preference.

## Looking Ahead

Though you may not have used `String`

objects other than for output yet,
you will soon, and they can and are used as accumulators in a variety of
different ways. They are commonly used with the concatenation operator,
to combine `String`

objects into a longer `String`

.

For example, the following code uses an array of `String`

objects
containing the parts of a person’s name (e.g., personal name, “middle”
name, and family name) and constructs a Gmail address from them:

```
int n;
String address;
n = name.length;
if (n == 0) {
address = "no-reply";
} else {
address = name[0];
for (int i = 1; i < n; i++) {
address += "." + name[i];
}
}
address += "@gmail.com";
```

The accumulator in this case (named `address`

) creates a long `String`

that contains all the parts of the person’s name, with periods between
them.