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 1 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.^[1]

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.^[2]

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.