Assignment 4 Code Review

12 November 2002 - CS 509

The Problem

• A variant of the Dutch National Flag Problem.

  • Sort an array of three values in linear time.

• A sort that isn't.

  • Learn to recognize special cases and exploit them.

  • The special case here: no sorted arrays.

The Solution

• The big idea was not to sort.

  • Count the moves required if the vectors were sorted.

  • The count requires O(n) time.

• The next problems:

  1. How to count the residues.

  2. How to find the minimum.

Design

• Finding the minimum moves.

• It has something to do with the maximum residue count in each vector.

  • But what?

  • What happens for identical counts, both within and between the same vectors?

  • This is getting complicated.

• On the other hand, there are only six possible outcomes.

  • Determining the moves for each is fast and simple.

  • Brute force can be your friend.

Test Cases

• Exhaustively generate all possible combinations of moduli.
  

  • Combinations of min, mid, and max (6)

  • Combinations of min and max (6)

  • All the same (1).

• There are (6 + 6 + 1)³ = 13³ = 2,197 possible test cases.

What Happened?

• Everybody lost points by having duplicated code not having documentation.

• 11 of 22 made at least one mistake.

  !!! modulus repeated in computed answer.
  !!! calculated answer v1: 0, v2: 2, v3: 2, moves: 2
  !!! check answer      v1: 0, v2: 1, v3: 2, moves: 2
  Input vectors were
  v1:  2 
  v2:  2 
  v3:  2 
  
  !!! calculated move count larger than the check move count.
  !!! calculated answer v1: 0, v2: 1, v3: 2, moves: 3
  !!! check answer      v1: 0, v2: 1, v3: 2, moves: 2
  Input vectors were
  v1:  2 
  v2:  2 
  v3:  2 2 2 
  

• Of the 11, five failed to handle the empty vectors.

  !!! calculated move count larger than the check move count.
  !!! calculated answer v1: 0, v2: 0, v3: 4290699319, moves: 4290699688
  !!! check answer      v1: 0, v2: 1, v3: 2, moves: 0
  Input vectors were
  v1:  
  v2:  
  v3:  
  

• One of the 11 had an infinite loop.

Line Statistics - Newlines

Line Statistics - Semicolons

Procedure Statistics

Control Complexity

while r.v1 == max or r.v2 == max or r.v3 == max

  if     (*it).at_vector == 0)
     and r.v1 == max
     and mode_assigned[(*it).of_mod] == -1
     
     mode_assigned[(*it).of_mod]=1
     r.v1 = (*it).of_mod
     it = v.erase(it)

  else if     (*it).at_vector == 1
	  and r.v2 == max
	  and mode_assigned[(*it).of_mod] == - 1

     mode_assigned[(*it).of_mod]=1
     r.v2 = (*it).of_mod
     it = v.erase(it)

  else if     (*it).at_vector == 2 
	  and r.v3 == max 
	  and mode_assigned[(*it).of_mod] == -1

      mode_assigned[(*it).of_mod]=1
      r.v3=(*it).of_mod
      it = v.erase(it)

   else ++it

Complexity

• What is complexity?

  • Anything that's too much.

    • Too many arguments.

    • Too many statements.

    • Too much indentation.

    • Too much nesting.

    • Too big.

• In general, more than two or three things in one place is complex.

Informative Documentation

• Documentation should tell the reader something new.

  // Initialize mod_arr to zero.
  
  for (i = 0; i < THREE; i++)
    for (j = 0; j < THREE; j++)
     mod_arr[i][j] = ZERO;
  
  unsigned mod_arr[3][3] = {
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 }
    };
  
  answer min_3sort(ivec iv1, ivec iv2, ivec iv3)
  
    // Implement the min_3sort function.
  
  answer min_3sort(ivec iv1, ivec iv2, ivec iv3)
  
    // Find the minimum 3-sort for the given vectors,
    // returning the minimum sort information.
  

Behavioral Documentation

• Documentation should describe behavior, not actions.

  static void 
  assign(answer & local, ivec local_vec, unsigned & min)
  
    // Assigns values to local of type answer.
  
  static answer
  timed_run(min3sort_fun m3s, input_vectors vecs, time_t & et)
  
    // Run the 3-sorting procedure m3s against the given input
    // vectors, returning the result returned by the sort.
    // Also return in et the sorting time in usecs.
  
  

  • The code is good at describing activities.

Function Documentation

• Function documentation should describe input and output parameters and the relation between them.

  
  VT find_min_moves(VT * v_ary, int sz, int & mvs) {
  
    // Calculates the minimum move of the given 3 x 3 matrix.
  
  
  static void
  check_sort(answer & a, unsigned mods[], unsigned m_cnts[][3])
  
    // Determine the number of moves in a sort in which all
    // residue mods[0] elements are moved to vector 1, all
    // residue mods[1] elements are moved to vector 2, and all
    // residue mods[2] elements are moved to vector 3.  If the
    // sort is better than the results given in a, update a
    // with the new, better results.  m_cnts[v][m] is the
    // number of elements with residue m in vector v.
  
  

  • Don't forget the return value and any globals modified.

Other Documentation Recommendations

• Don't document variables.

  • Use meaningful names instead.

  • Document unobvious variable characteristics.

  unsigned mod_arr[3][3] = {
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 }
    };
  
  // mod_cnts[v][m] = the number of elements
  // with residue m in vector v.
  
  unsigned mod_cnts[3][3] = {
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 }
    };
  

• Mixing documentation and code suggests poor documentation, poor code, or both.

• Syntax documentation is not documentation.

      } // end of if
    }  // end of for
  } // end of while
  

Use Generic Algorithms

• Counting residues.

  for (i = 0; i < v.size(); i++)
    if (v[i] % 3 == 0)
      cnts[0]++
    else if (v[i] % 3 == 1)
      cnts[1]++
    else
      cnts[2]++
  

• Control complexity.

  for (i = 0; i < v.size(); i++)
    cnts[v[i] % 3]++
  

• Use generic algorithms.

  void f(int i, int c[])
    c[i % 3]++
  
  void cnt_residues(ivec v, int cnts[3])
    for_each(v.begin(), v.end(), 
             bind2nd(ptr_fun(f), cnts))
  

Points to Remember

• Recognize and exploit special cases.

  • They can save you time and effort.

• Control complexity.

  • Avoid it, reconginze it, and control it.

• Document your code.

  • You're writing for other programmers, not a machine.

• Use generic algorithms.

This page last modified on 13 November 2002.