Array Processing Patterns: Sum, Average, Min, and Max

References:

• Pre-requisite: it is assumed that you have read through the prior tutorials, and are familiar with the concepts covered in those tutorials.

Goals:

• In this tutorial, we will:
  • Examine how to make use of an 'array processing' pattern, including a 'Three Phase" approach to thinking about the pattern, which further includes a very visual representation for thinking about how the main loop operates on the array(s).

1. Obtain the example code

• Here is the zip file to the source files and compiled executable of this example.
• Here is the keyboard mapping for the XBOX 360 controller.  
• Here is the main tutorial page for working with XNACS1Lib, and here is the complete documentation of the library: html-page or compiled html help file.

When the game starts, you'll see a screen that looks similar to this:

In this tutorial, the program that you can run closely resembles the program that you ran in the previous tutorial.  What's different is the message at the top of the screen.  The program displays the sum of all the hit counts as "total", the average (which is the total, divided by the number of rectangles), the smallest hit count as "min", and the largest as "max"

2. Background

The major topic for this tutorial is the pattern for processing arrays.  Since we can only interact with arrays one element at a time, we will need a strategy that will allow us to accomplish tasks by only examining 1 element at a time.  The tasks that we'll examine in this tutorial include summing up all the numbers in the array, or averaging the numbers, or finding the min/max number.  Let's examine the overall pattern using the task of averaging the numbers in the array.

In order to calculate the average of the numbers in the array, we first need to first sum up all the elements in the array, and then divide that total by the number of elements in the array.  The we will break up the basic pattern into three phases:

1. Pre-Loop Initialization
   When we start our algorithm, we haven't summed up any elements yet, so the running total should be initialized to zero (let's call this variable total).  Generally, just about anything we do to 'process' an array will require that we (at least) initialize some variables.

2. The Loop
   In this stage, we'll process the array, step by step.  For our problem, this is where we'll sum up all the numbers in the array.  More detail on this, below.

3. Post-Loop Processing
   Once we've got the sum of the elements, the only thing left to do is to divide that total by the number of elements, and then store the resulting average into a variable.

The second phase ("The Loop") is involved enough that we will examine it separately, here.  The key thing to understand is that since we can't deal with the entire array in a single statement, we'll have to approach the problem element-by-element.  It may help to mentally break the array down into a couple of regions: the region of the array wherein we've already done the work, the current array element that we're looking at, and the remaining elements in the array, where we'll need to do work in the future.  Here's a picture to help visualize that (using the first six elements of the array that keeps track of hits, in the above screenshot):

The green 'Already Done' region starts out being empty, since at the start of the loop, we haven't done any work.  The blue 'Current Element' region is just element #0 - in most (but not all) cases, it's easiest to count up from zero.  The tan 'Future Work' region consists of all of the elements we haven't looked at yet, which are elements 1 through 5.

How will we sum up all the elements in the array?  Simply put, we need to add the element we're currently looking at (number 11, stored in element #0), to the sum of all the elements that we've already looked at.  In other words, we need to add 11 to the total of the elements in the green region.  Since the variable total stores the sum of the elements in the green region, we just need to add 11 to that total (which starts out at zero).  Once we've done that, then we've processed element #0, and it becomes part of the green, 'Already Done' region of the array.  In the next iteration through the loop, the blue, 'Current Element' region moves up by one, like so:

In this iteration through the loop, we add the number in the current element (zero) to the total (11), and get 11, which extends the green region to now include the current element.

 At the start of the next iteration through the loop, we have:

In this iteration through the loop, we add the number in the current element (11) to the total (11), and get 22, which extends the green region to now include the current element. 

 At the start of the next iteration through the loop, we have:

As you can see, this process will repeat, until the 'Future Work' region is empty, and the entire array is covered by the green 'Already Done' region.  Once that's done, phase 2 ("The Loop") is done, and our program will have the sum of all the elements in the array, stored into the variable total.  After that, it will go on to phase 3, in which it will divide the sum by the number of elements, in order to get the average.

Please also keep in mind that the 'Three Phase' division, and the green/blue/tan way of thinking about this array processing pattern is something that's specific to this tutorial, and not something that will be commonly recognized anywhere in the computer industry.

3. Examining The Program:

Let's examine the C# source code that produces the behavior we see on-screen

• Declaring the instance variables and named constants, and initialize them
  • For this tutorial, we don't need to declare any new instance variables, nor any new named constants.
  • Instead, we will create several functions that compute things like the the sum, the average, and the min and max of the elements in the array.  These functions will return their results to UpdateWorld, which will (temporarily) capture those values into local variables.  Because of this, instance variables are not required.
• UpdateWorld():

  int total = TotalHits();     float avg = AverageHits();     int min = MinHits();     int max = MaxHits();     EchoToTopStatus("Block Hit Status[total=" + total +                         " avg=" + avg +                         " min=" + min +                         " max=" + max + "] " +                         "Soccer located at: " + m_SoccerBall.Center);

  • UpdateWorld for this tutorial is almost identical to the UpdateWorld for the one for the previous tutorial.
  • The only code that's new is listed above, and (essentially) it just calls various utility functions to do the actual work of processing the array.  Once UpdateWorld has all the data it needs, it then updates the message at the top of the screen.
• TotalHits():

  /// <summary> /// Compute total number of hits (collisions) by adding up the contents /// of all m_BlockHits. /// </summary> /// <returns>Sum of all elements in m_BlockHits</returns> private int TotalHits() {     int total = 0;     for (int i = 0; i < m_BlockHits.Length; i++)         total = total + m_BlockHits[i];     return total; }

  • Above is the code for the TotalHits method, which sums up all the total numbers in the m_BlockHits array.  Since this array stores the hit count for each of the rectangles, TotalHits therefore accomplishes the task of summing up the total number of hits.
  • For 'Phase 1', we declare a temporary, local, integer variable named total, and initialize it to start with the value zero.  The way to think about this is that when the function starts, the function hasn't done any work yet, so the sum total of the (zero) elements that the function has examined is zero. 

     This is represented pictorially in the first picture, above.

  • For 'Phase 2', we use a loop to iterate over every element in the array:
        for (int i = 0; i < m_BlockHits.Length; i++)

            total = total + m_BlockHits[i];

    • As was explained in the Background section, above, this is the part of the array processing pattern that steps through the array, element by element.  The running total of the green, 'Already Done' region is stored in total, and m_BlockHits[i] is the blue, 'Current Element' that keeps getting added to total (in order to expand the 'Already Done' region).
    • Technically, the part of the loop that creates and initializes the loop's counter (int i = 0) should probably be thought of as being part of Phase 1, rather than the loop itself.
  • Once the sum total of the elements in the array has been been computed, the algorithm is pretty much done.  One can argue that returning the total (return total;) is all of 'Phase 3' for this function, but one could also argue that returning the value is something that the function is doing (as opposed to the 'summing all the elements in the array' pattern), and that maybe there is no phase 3 for this particular array processing algorithm.
• AverageHits():

  /// <summary> /// returns the average number of hits (collisions) from the m_BlockHits array /// </summary> /// <returns>average of all numbers in m_BlockHits</returns> private float AverageHits() {     float total = TotalHits();     return total / m_BlockHits.Length; }

  • The average (the arithmetic mean) of a collection of numbers is just the sum of those numbers, divided by how many numbers there are. 
  • Since we already have a function that will sum up the elements of the array, we simply call that (which, in turn, makes use of the array processing pattern):
    float total = TotalHits();
  • Once we've got the sum total, all that's left is to divide that number by the number of elements in the array.  Note that we can think of this as being 'Phase 3' of the algorithm for finding an average: you can't get the average without doing this, so the algorithm isn't complete until this work is done.
• MinHits():

  /// <summary> /// Min hits (collisions) in the m_BlockHits array /// </summary> /// <returns>the smallest value in the m_BlockHits array</returns> private int MinHits() {     int min = m_BlockHits[0];     for (int i = 1; i < m_BlockHits.Length; i++)         if (m_BlockHits[i] < min)             min = m_BlockHits[i];     return min; }

  • The purpose of this function is to find the minimal (smallest) element in the array.  The basic strategy will be to store the smallest value that we've seen so far in the variable min, (i.e., the smallest value from the green, 'Already Done' region is stored in min).  As we examine the blue, Current Element, we will ask "Is this smaller than the value of min?"  (i.e., "Is the value of the current element smaller than the smallest element from the green region?")  If is, then we assign the value of that element to min.  Whether the current element is the new minimum or not, the green, 'Already Done' region is then expanded to include the blue, 'Current Element', until all elements get processed.
  • 'Phase 1' consists of declaring the min variable, and initializing it with the value of the first element of the array:
        int min = m_BlockHits[0];
  • 'Phase 2' consists of a loop that will allow us to traverse the entire array:
        for (int i = 1; i < m_BlockHits.Length; i++)
    • The body of the loop consists of an if statement, which asks if the current element is less than the minimum value from the green, 'Already Done' region.  If the current element is less, then it's assigned to the min variable.  If the current element is greater than (or equal to) the current minimum, then nothing is done:
              if (m_BlockHits[i] < min)

                  min = m_BlockHits[i];

  • The loop exits once it has iterated through all elements of the array.  Again, a strong argument can be made that there is no 'Phase 3' for this particular algorithm since once the loop is done, we have the minimum element.  One might also argue that 'Phase 3' is to return the minimum value to the calling method.  Given that we devised the 'Three Phase' explanation only for this tutorial, it's more important to be able to look at the situation, and understand the arguments for (or against) there being a 'Phase 3', rather than worrying about what the "Right Answer" is.
• MaxHits():

  /// <summary> /// Max hits (collision) in the m_BlockHits array /// </summary> /// <returns>the largest value in the m_BlockHits array</returns> private int MaxHits() {     int max = m_BlockHits[0];     for (int i = 1; i < m_BlockHits.Length; i++)         if (m_BlockHits[i] > max)             max = m_BlockHits[i];     return max; }

  • The MaxHits function will find the largest element in the array, using an approach that's very similar to the MinHits function.
  • You should be able to go through this function, and understand it fully, on your own.

FURTHER EXERCISES:

1. Start from a blank starter project (1000.201, if you need it), and re-do the code from memory as much as possible.  On your first try, do what you can, and keep the above code open so that when you get stuck, you can quickly look up what you forgot (and that after you finish a line, so that you can compare your line to the 'correct' line).  On the next try, do the same thing, but try to use the finished code less.  Repeat this until you can type everything, without referring to the tutorial's code.
   • Repeat this exercise daily for several days, so that you really get the hang of this.  As you go on, periodically review this by re-doing this exercise.
2. Examining The AverageHits() Function
   For this exercise, you should use the same project that was explained in the above tutorial.
   Notice that the numbers stored in the m_BlockHits array are integers, and that TotalHits returns an integer.  Notice also that we are specifically declaring total to be a float, not an int.  Why was this done?  What would happen if you declare total to be an int, instead?
3. Problem with MinHits if we assign min to be zero?
   For this exercise, you should use the same project that was explained in the above tutorial.
   Notice that in the function MinHits, we initialize the variable min to have the value of the first element of the array. 
   1. What problem(s) would arise if the variable min was assigned the value zero, instead?  It may help to list the values stored in an example array when explaining the danger of doing this.
   2. In your own words, in English, concisely explain why min is initialized with the value of the first element of the array, and not some other number, like zero.
4. ComputeAllStats Function
   For this exercise, you should use the same project that was explained in the above tutorial.
   Instead of using each of the four, separate functions that each compute one thing, you will instead create a single function that does all four tasks using a single loop.  As you're doing this exercise, think about the advantages and disadvantages of writing the code this way.  Given a choice of a single ComputeAllStuats function, versus four separate functions, how do the two solutions compare in regards to how easy the code is to test, to debug, to maintain, and to use (as a programmer), as well as how efficient the algorithms are from the computer's point of view - is there work that's being duplicated in the ComputeAllStats solution?  In the solution with four separate functions?
   
   Your function should look like this, but filled in with working code:
   

   public void ComputeAllStats(ref float sum, ref float avg, ref float min, ref float max)

   {

   }

5. Creating a SecondToMinHits function
   For this exercise, you should use the same project that was explained in the above tutorial.
   For this exercise, you should create a function named SecondToMinHits, which will find the second to smallest number in the array. 
   Here are some examples, to clarify
   1. If the array contains:
      

      Index	0	1	2	3	4
      Value	0	10	20	30	40

      
      Then the minimum element is: 0
      And the second to smallest number is: 10

   2. If the array contains:
      

      Index	0	1	2	3	4
      Value	90	12	20	30	9

      
      Then the minimum element is: 9
      And the second to smallest number is: 12

   3. If the array contains:
      

      Index	0	1	2	3	4
      Value	90	12	9	30	9

      
      Then the minimum element is: 9
      And the second to smallest number is: 9

6. Extra Challenging: Reversing The Array
   For this exercise, you should use the same project that was explained in the above tutorial.
   Can you write a function that will take the m_BlockHits array, and reverse the order of the elements in the array? 
   For example, if the array starts out with the values
   

   Index	0	1	2	3	4
   Value	0	10	20	30	40

   
   then after calling the array-reversing function, the array should have the values:
   

   Index	0	1	2	3	4
   Value	40	30	20	10	0

   
   

   Keep in mind that this exercise is extra challenging, and may not be a good exercise to start with if you're looking at this topic for the first time.

	This work is supported in part by a grant from Microsoft Research under the Computer Gaming Curriculum in Computer Science RFP, Award Number 15871 and 16531.
2/8/2010