Accumulator Arrays

Programs often need to keep track of (in one way or another) multiple things over multiple iterations. In some cases, this can be accomplished with multiple accumulators of the kind discussed in Chapter 16. However, in other cases, it is better to use an array of accumulators.

Motivation

Many K-12 schools assign numeric grades (on a scale of 0 to 100) to individual students during the year and then, at the end of the year, create a summary report that shows the number of students that were in each centile (i.e., the 90s, the 80s, etc.). If you were asked to write a program for this purpose, you’d know (from Chapter 16) that you should use an accumulator to keep a running count of the number of students in each centile. Since there are eleven different centiles (treating 100 as an entire centile), this means that you need eleven different accumulators.

Review

If you approached the problem in this way, you might proceed by declaring and initializing eleven different accumulators as follows:

        int ones, tens, twentys, thirtys, fortys, fiftys, sixtys,
            seventys, eightys, ninetys, hundreds;

        ones = tens = twentys = thirtys = fortys = fiftys
            = sixtys = seventys = eightys = ninetys = hundreds = 0;

You then might write the following loop to update these accumulators:

        int n = data.length;        

        for (int i = 0; i < n; i++) {
            if      (data[i] <  10) ones++;
            else if (data[i] <  20) tens++;
            else if (data[i] <  30) twentys++;
            else if (data[i] <  40) thirtys++;
            else if (data[i] <  50) fortys++;
            else if (data[i] <  60) fiftys++;
            else if (data[i] <  70) sixtys++;
            else if (data[i] <  80) seventys++;
            else if (data[i] <  90) eightys++;
            else if (data[i] < 100) ninetys++;
            else                    hundreds++;
        }

Unfortunately, there are three big shortcomings of this approach. First, all of the variables must be declared and initialized individually, and, while its only mildly awkward in this case, if you needed more accumulators it would become very awkward. Second, the nested if statement that is used to update the appropriate accumulator is both awkward, tedious, and error-prone. Finally, since methods in Java can only return a single entity, you could not write a re-usable method to return all of the calculated values, you would have to copy it to wherever it was needed.

As you should know, in situations like this (i.e., when you have multiple “related” values) it is better to use an array than to use individual variables. What you may not yet know is how to use an array to solve the centile histogram problem.

Thinking About The Problem

The first thing to realize is that the variables ones, tens, etc. can be replaced with an array named count. Specifically, count[0] will replace ones, count[1] will replace tens, etc. This facilitates both the declaration and the initialization.

The second thing to realize is that the truncation pattern from Chapter 6 can be used to calculate the index associated with a particular centile. Specifically, one can truncate to the 10s place to get the centile. For example, a value of 63 is in centile 63/10 (i.e., centile 6; the 60s), a value of 8 is in centile 8/10 (i.e., centile 0; the 1s), and a value of 100 is in centile 100/10 (i.e., centile 10; the 100s). This eliminates the need for a complicated if statement.

The Pattern

The pattern, then, can be stated as follows:

1. Declare and initialize an array to hold the number of accumulators needed.
2. Create an algorithm for identifying the index of the particular accumulator that needs to be updated during a particular iteration.
3. Write a loop that calculates the index and updates the appropriate accumulator.

In most situations, this logic should be encapsulated in a method.

Examples

A few examples should help you see how you can use this pattern in a wide variety of situations.

The Motivating Example

Continuing with the grading example, this pattern can be implemented as follows:

    public static int[] gradeHistogram(int[] data) {
        int   centile, n;        
        int[] count = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        
        n = data.length;        

        for (int i = 0; i < n; i++) {
            centile = data[i] / 10;
            count[centile] += 1;
        }

        return count;
    }

The expression data[i] / 10 is used to calculate the index (i.e., the centile) of data[i] in the accumulator array, and the statement count[centile] += 1; increases the value of the \(\texttt{centile}^{th}\) accumulator by 1.

Some Other Examples

This pattern works best when the algorithm for calculating the index of the accumulator is straightforward. For example, suppose you need to count the number of odd and even values in an array. If the number of even values is stored in element 0 and the number of odd elements is stored in element 1, then you can implement this pattern as follows:

    public static int[] oddsAndEvens(int[] data) {
        int[] count = {0, 0};
        int n = data.length;
        
        for (int i = 0; i < n; i++) {
            count[data[i] % 2] += 1;
        }

        return count;
    }

This works because, as you know from Chapter 5, data[i] is even when (data[i] % 2) is 0 and is odd when (data[i] % 2) is 1.

However, in some cases you can’t (or it is awkward to) avoid the use of a complicated if statement. For example, suppose you need to count the number of negative, zero, and positive elements in an array. You can implements this as follows:

    public static int[] signs(int[] data) {
        int[] count = {0, 0, 0};
        int n = Array.getLength(data);
        
        for (int i = 0; i < n; i++) {
            if      (data[i] <  0) count[0]++;
            else if (data[i] == 0) count[1]++;
            else                   count[2]++;
        }
        return count;
    }

Notice that, even though this implementation uses a nested if statement, there are benefits to using an accumulator array. First, it facilitates the declaration and initialization of the accumulators. Second, all of the accumulators can be returned by returning the array.