- Forward


Loop Replacement
A Programming Pattern


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • A Common Feature of Programs:
    • Nested Loops
  • A Common Shortcoming:
    • The code can be very difficult to read and understand when the bodies of the loops are complicated
A Solution
Back SMYC Forward
  • Loop Replacement:
    • Replace (one or more of) the inner loop(s) with a method call (often a private method)
  • An Observation:
    • This is really just a particular kind of functional decomposition
An Example - A Moving Average
Back SMYC Forward
  • The Description:
    • Each element in a moving average of a data array is the mean of the corresponding element in the data array and a fixed number of previous elements
  • The Math (0-Based Indexing):
    • \(m_i = \left( \sum_{i-n+1}^{i} d_i \right) / n, \text{ for } i = n-1, N-1\)
  • A Visualization:
Moving Average (cont.)
Back SMYC Forward

A "Naive" Implementation

javaexamples/programmingpatterns/LoopReplacement.java (Fragment: 0)
 
Moving Average (cont.)
Back SMYC Forward
  • A Shortcoming of the "Naive" Implementation:
    • The purpose of the inner loop isn't obvious
  • A Better Approach:
    • Use the subarray pattern to create a method that can replace the inner loop
Moving Average (cont.)
Back SMYC Forward

The average() Method

javaexamples/programmingpatterns/LoopReplacement.java (Fragment: 1)
 
Moving Average (cont.)
Back SMYC Forward

The Improved Implementation of the movingAverage() Method

javaexamples/programmingpatterns/LoopReplacement.java (Fragment: 2)
 
Even More Motivation
Back SMYC Forward
  • An Observation:
    • When working with arrays of arrays nested loops are used just to iterate over the elements
  • An Implication:
    • When each element needs to be processed in a loop (or multiple loops) the nesting can get very deep
An Example - Blurring an Image
Back SMYC Forward
  • Representing an Image:
    • Images are commonly represented as a rectangular array of pixels which are Color objects
  • Blurring an Image:
    • Is commonly accomplished by finding a weighted average of a particular element's neighbors
Blurring an Image (cont.)
Back SMYC Forward
  • The Math (for a 3x3 Neighborhood):
    • \(d_{i,j} = \left( \sum_{\Delta_i=-1}^{1} \sum_{\Delta_j=-1}^{1} s_{i+\Delta_i, j+\Delta_j} \right) / 9 \)
  • A Visualization:
    • convolution
Blurring an Image (cont.)
Back SMYC Forward

A "Naive" Implementation (Assuming Pixels are double Values)

javaexamples/programmingpatterns/LoopReplacement.java (Fragment: 3)
 
Blurring an Image (cont.)
Back SMYC Forward
  • A Shortcoming of the "Naive" Implementation:
    • There are now four nested loops and they are difficult to understand
  • A Better Approach:
    • Use the neighborhoods pattern to create a method that can replace the inner loop
Blurring an Image (cont.)
Back SMYC Forward

A Method for Calculating a Neighborhood Average

javaexamples/programmingpatterns/Neighborhoods.java (Fragment: 1)
 
Blurring an Image (cont.)
Back SMYC Forward

An Improved Implementation

javaexamples/programmingpatterns/LoopReplacement.java (Fragment: 4)
 
There's Always More to Learn
Back -