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

# 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:

- Declare and initialize an array to hold the number of accumulators needed.
- Create an algorithm for identifying the index of the particular accumulator that needs to be updated during a particular iteration.
- 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.