Assignment 4 Code Review

17 April 2003 - CS 509

Assignment 4 Code Review

• Design

• Analysis

• Test Cases

• Statistics

• Coding problems

The Problem

• When placing witness-criminals in towns,

  1. Each town should have at most one witness-criminal.

  2. Each pair of towns with a road between them should have a total of at most one witness-criminal.

• Given a map of towns and the roads between them, place the largest number of witness-criminals possible subject to the two constraints above.

• Find the largest possible valid subset of towns that can host witness-criminals.

  • A valid subset is one in which all towns in the subset obey the two constraints above.

  • A one-element set is always valid.

Design

• What to wish for.

  • A way to generate all possible subsets of a given set.

• Ok, so *poof*

  std::vector<sets> all_subsets(int n);
  

• The solution

  subsets = all_subsets(map.size())
  best = subsets[0]
  
  for (i = 1; i < subsets.size(); i++)
    if ok(map, subsets[i]) and
       subsets[i].size() > best.size()
      best = subsets[i]
  

Generating All Subsets

• For any element e in a set, either e is in a subset or it's not.

• Algorithm for finding all subsets of a set S:

  1. Remove an arbitrary element e from set S to form set S'.

  2. Find all subsets of S'.

  3. Copy the subsets of S' and add e to each copy.

Subset Generating Example

• Example: Find all subsets of {1 2 3}.

  AllSS { 1 2 3 }	=	AllSS { 1 2 } union (AllSS { 1 2 } + 3)
  AllSS { 1 2 }	=	AllSS { 1 } union (AllSS { 1 } + 2)
  AllSS { 1 }	=	AllSS { } union (AllSS { } + 1)
  AllSS { }	=	{ { } }
  AllSS { 1 }	=	{ { } } union ({ { } } + 1)
  	=	{ { } } union { { 1 } }
  	=	{ { } { 1 } }
  AllSS { 1 2 }	=	AllSS { 1 } union (AllSS { 1 } + 2)
  AllSS { 1 2 }	=	{ { } { 1 } } union ({ { } { 1 } } + 2)
  AllSS { 1 2 }	=	{ { } { 1 } } union { { 2 } { 1 2 } }
  AllSS { 1 2 }	=	{ { } { 1 } { 2 } { 1 2 } }
  AllSS { 1 2 3 }	=	AllSS { 1 2 }
  		union (AllSS { 1 2 } + 3)
  AllSS { 1 2 3 }	=	{ { } { 1 } { 2 } { 1 2 } }
  		union ({ { } { 1 } { 2 } { 1 2 } } + 3)
  AllSS { 1 2 3 }	=	{ { } { 1 } { 2 } { 1 2 } }
  		union { { 3 } { 1 3 } { 2 3 } { 1 2 3 } }
  AllSS { 1 2 3 }	=	{ { } { 1 } { 2 } { 1 2 } { 3 } { 1 3 } { 2 3 } { 1 2 3 } }

• How many subsets are there?

We've Been Here Before

• Each element of a set S is either in or not in a subset of S.

  • { y-n y-n y-n y-n . . . }

• For each element you have one of two possible decisions.

  • And you have 2 * 2 * 2 * 2 . . . total decisions, each one representing a subset.

• For an n element set, you have 2ⁿ possible subsets.

  • For n = 30, there are 2³⁰ = 1,073,741,824 possible subsets.

• Our ol' pal, exponential behavior.

  • And remember, your arms are too short to box with exponential behavior.

Exhaustive Search

void place(
  uvec current, uvec & best, unsigned ctown)

  if ctown < map.size()
    place(current, best, ctown + 1)
    current.push_back(ctown)
    place(current, best, ctown + 1)

  else if best.size() < current.size()
          and ok(current)
    best = current


uvec maximal_placement()

  uvec towns
  place(uvec(), towns, 0)
  return towns

• This code combines searching and generation.

Battling Exponential Growth

• We can prune candidates, and order the rest for searching.

• Ordering the candidates is a good idea, but hard to do.

  • The largest successful candidate ends the search.

  • Generating the candidates in decreasing order requires lots of space.

• You could also order the towns.

  • A greedy solution.

  • Add towns with few connecting roads first.

  • This is still exhaustive search.

• Pruning by success or counts.

  • If the current candidate is invalid, don't continue the search.

  • If the current candidate plus the remaining towns is less than the best candidate, don't continue the search.

Searching by Road Order

• Re-ordering the map is a pain because everything's an index.

  • The neighbor lists have to be changed to match the new order.

    0: 1 2 1: 0 2: 0

    ->

    0: 2 1: 2 2: 0 1

• Create an index vector instead.

  • map[index.front()] has the fewest neighbors.

  • map[index.back()] has the most neighbors.

• The ordering criterion is

  If i < j, then
  map[index[i]].size() < map[index[j]].size().

• Notice road ordering requires three parameters: i, j, and the map.

A Road Ordering

• We have to make our own ordering.

• Because road ordering requires three parameters, function adaptors won't help.

  • They only deal with unary and binary functions.

• We need to use a functor.

  struct map_less {
  
    const umat & map;
  
    map_less(const umat & map) : map(map) { }
  
    bool 
    operator () (unsigned i, unsigned j) {
      return map[i].size() < map[j].size();
      }
    };
  

A Road-Ordering Search

place(uvec index, 
      uvec current, uvec & best, 
      unsigned ctown)

  if ctown < map.size()
    place(index, current, best, ctown + 1)
    current.push_back(index[ctown])
    if ok(current)
      if best.size() < current.size()
        best = current
      place(index, current, best, ctown + 1)


uvec maximal_placement()

  uvec towns

  uvec index(map.size())
  for (unsigned i = 0; i < map.size(); i++)
    index[i] = i
  std::sort(index.begin(), index.end(), 
            map_less(map))

  place(index, uvec(), towns, map.size())

  return towns

Road-Ordering Results

• Not helpful.

  • Can't cover the cost of ordering.

A Size-Pruning Search

• If the number of current towns plus the number of towns left isn't greater than the number of towns in the best solution, punt.

  • 3 towns current + 3 towns left vs. 6 towns best.

void place(
  uvec current, uvec & best, unsigned ctown)

  const unsigned max = 
    current.size() + (map.size() - ctown)

  if max > best.size()
    place(current, best, ctown + 1)
    current.push_back(ctown)
    if ok(current)
      if best.size() < current.size()
        best = current
      place(current, best, ctown + 1)

uvec maximal_placement()

  uvec towns
  place(uvec(), towns, 0)
  return towns

Does Size-Pruning Help?

• Not much help, but it's not as expensive as sorting was.

How about Pruning and Sorting?

• How about if the algorithm both prunes and sorts?
  

• Not even close.

Use All The Data

• More knowledge = better code.

• What knowledge are we wasting here?

• When you place a witness-criminal in a town, all neighbors of that town are out of the search.

  • Knock them out of the search.

A Knockout Search

void place(
  flag_set valid, uvec current, uvec & best)

  const flags_iter
    b = valid.begin(),
    e = valid.end(),
    v = std::find(b, e, true)

  if (v == e) return

  *v = false
  place(valid, current, best)

  const unsigned i = v - b
  std::for_each(
    map.at(i).begin(), map.at(i).end(), 
    set_false(valid))

  current.push_back(i)
  place(valid, current, best)

  if best.size() < current.size()
    best = current

Knockout Search Details

typedef std::vector<bool>        flag_set
typedef flag_set::iterator       flags_iter
typedef flag_set::const_iterator flags_citer

struct set_false {

  flag_set & flags;

  set_false(flag_set & flags) 
    : flags(flags) { }

  void operator () (unsigned i) {
    flags.at(i) = false;
    }
  };


uvec maximal_placement(const umat & map)

  uvec towns
  flag_set valid(map.size(), true)

  place(valid, uvec(), towns)

  return towns

Does Knockout Help?

• Not bad, but a little costly.

Knockout With Pruning

• Stop when no better solutions are possible.

  const flags_iter
    b = valid.begin()
    e = valid.end()
    v = std::find(b, e, true)
  
  if (v != e) and 
     (current.size() + (e - v) > best.size())
  
    // as before
  

  

• A little better.

Knockout With Counting

• Stop when no better solutions are possible.

  const unsigned max = 
    current.size() + std::count(v, e, true)
  
  if (v != e) and (max > best.size())
  
    // as before
  

  

• Much better.

  • More knowledge = better code.

Line Statistics - Newlines

Line Statistics - Semicolons

Procedure Statistics

Watch Initialization

• Should you do

  std::vector<int> temp_vec
  for i = 0; i < no_of_towns; i++
    temp_vec.push_back(-100)
  

  or

  std::vector<int> temp_vec(no_of_towns, -100)
  

• Should you do

  ulist townsLeft;
  for uint i = 0; i < map.size(); ++i
    townsLeft.push_back(i)
  

  or

  ulist townsLeft(map.size())
  for uint i = 0; i < map.size(); ++i
    townsLeft[i] = i
  

Use Generic Algorithms

• Should you use

  void init(int *actarrp, int sz)
    for (int i = 0; i < sz; i++)
      actarrp[i] = ACTIVE
  

  or

  std::fill(actarrp, actarrp + sz, ACTIVE)
  

Use Dynamic Memory Correctly

int findnext(umat map, int * actarrp, int sz)

 int *taarrp = new int [sz]

 townaffected(map, actarrp, sz, taarrp)

 for (i = 0; i < sz; i++)
   if actarrp[i] != ACTIVE
     continue
   if (taarrp[i] < mincnt) or (mincnt == 0)
     mincnt = taarrp[i]
     minidx = i

 return minidx;


uvec maximum_placement(umat map)

  int * actarrp = new int[mapsize]

  check_map(map)
  init(actarrp, mapsize)

  while findactivecnt(actarrp, mapsize) > 0
    idx = findnext(map, actarrp, mapsize)
    addtolist(map, actarrp, idx, townlist)

  return townlist

Duplicate Code is Bad Code

• You can do this.

  bool in_match(pvec sort,unsigned temp)
    unsigned is_size = sort.size()
    for unsigned i = 0; i < is_size; i++
      if sort[i].second == temp
        return true
    return false
  
  void match_find(pvec & sort, unsigned n)
    unsigned is_size = sort.size()
    for unsigned i = 0; i < is_size; i++
      if sort[i].second == n
        sort.erase(sort.begin() + i)
        return
  

• Or factor duplicate code.

  pvec::iterator
  find(pvec pv, unsigned n) 
    return std::find(pv.begin(), pv.end(), n)
  
  bool found(pvec sort, unsigned n)
    return find(sort, n) != sort.end()
  
  void remove(pvec & sort, unsigned n)
    pvec::iterator i = find(sort, n)
    if i != sort.end()
      sort.erase(i)
  

Points To Remember

• You always lose against exponential growth.

  • Know when you're up against it.

  • Don't out run it, out think it.

• If you make an assumption, test it.

  • You'll probably be surprised.

• Performance often comes at the cost of clarity.

  • Make sure you can pay for it; make sure you need it.

• More knowledge = better code.

This page last modified on 18 April 2003.