Advanced Programming I Lecture Notes

28 February 2006 • Assignment 2 Code Review

Outline

• The problem.

• Some solutions.

• Testing

• Results

• Coding observations.

The Problem

• Given the hash function

  f(str)
    return v[s.first-char] + 
           v[s.last-char] + 
           s.length
  

  and a set of words, assign values to v to avoid collisions, subject to

  0 ≤ v[i] ≤ 15
  

The Big Idea

• Treat v as a 26-digit hexadecimal number.

• This leads directly to the solution

  v = 0
  while v < 0xfffffffffffffffffffffffffff 
    if no-colisions(v, words)
      break
    v++ 
  

• Trying every possibility is known as brute-force search.

Are We Done?

• There are roughly 16²⁶ - 1 possible values for v.

  • That's about 2×10³¹ values.

• Although correct and simple, brute-force search is too inefficient.

  • We need a way to cut down on the number of values to search.

A Refinement

• It isn't necessary to assign values to all 26 letters.

  • Just to the letters appearing at the start or end of a string.

• This reduces v to a n-digit number, where n distinct letters start or end the words.

  • That's better, but not by much if n > 8.

  • And n could be 26.

Another Refinement

• If a particular assignment to v fails, where's the problem?

  • It's not clear.

• The code assigns values to letters, but it's the words that collide.

• Assign values to letters as directed by the words.

Another Solution

solve(words, encoding)
  if words is empty
    // success
  else
    pick a word in words
    while encode word
      compare for collisions        
      if not found
        solve(words - word, encoding)
    // failure

• This is equivalent to assigning values to an n-digit hexadecimal number.

Choosing Words

• How should the solution choose a word from words?

• Two general principles provide useful guidelines:

  1. Make important decisions first.

  2. Find mistakes as early as possible.

• How can word choice follow these guidelines?

Important Decisions

• Frequently occuring letters are more important than infrequently occurring letters.
  elk, egg, the, elf, end, pie

  • Frequently occurring letters effect more words.

• Order words by decreasing letter frequency.

  f[word.first] + f[word.last]
  

Early Mistakes

• Find collisions as soon as possible.
  egg, elf, ..., fog

• A word should be tested for collisions as soon as its first and last letters have values.
  egg, elf, fog, ...

• Reorder the list to test for collisions as soon as possible.

Does It Help?

• Sometimes.

  	set 1	set 2	set 3
  Unsorted	13.2	3.6	30.3
  Sorted	0.2	0.0	0.0

• Sometimes not.

  	set 1	set 2
  Unsorted	0.6	2.1	9.7
  Sorted	0.7	3.9	9.7

• These are guidelines, not rules.

Sorting

• The two guidlines could be implemented as sorts on the word list.

  • One sort by decreasing letter frequencey.

  • The other by earliest definition.

• An example of sorting for something other than information retrevial.

  • Find and exploit data properties.

Test Cases

• The usual empty and garbage test cases.

• The abc test, a collision test, and the five word sets.

Test Results

	1	2	3	4	5	6	7	8	9	10
1
2
3
4
5
6

Coding Observations

• Follow directions.

• Don't repeat yourself.

• Test your code.

• Know your tools.

• Avoid globals.

Follow Directions

• This

  a 0
  b 0
  c 0
  d 0
  e 0
  f 0
  g 0
  h 0
  

  is not the required output format.

Don't Repeat Yourself

• If you find yourself writing code like this

  
  int StrLenMatrix::getIndex(char start, char end) {
    // get index for start/end char location
    if ( (start == 'a' && end == 'a') || ( end == 'a' && start == 'a')) return 0;
    if ( (start == 'a' && end == 'b') || ( end == 'a' && start == 'b')) return 1;
    if ( (start == 'a' && end == 'c') || ( end == 'a' && start == 'c')) return 2;
    if ( (start == 'a' && end == 'd') || ( end == 'a' && start == 'd')) return 3;
    if ( (start == 'a' && end == 'e') || ( end == 'a' && start == 'e')) return 4;
    if ( (start == 'a' && end == 'f') || ( end == 'a' && start == 'f')) return 5;
    if ( (start == 'a' && end == 'g') || ( end == 'a' && start == 'g')) return 6;
    if ( (start == 'a' && end == 'h') || ( end == 'a' && start == 'h')) return 7;
    if ( (start == 'a' && end == 'i') || ( end == 'a' && start == 'i')) return 8;
  
    // And so on.
  
  

  stop and think.

• Duplicate code is bad code.

Test Your Code

class Hash {

  string word;

  Hash() {}
  Hash(const string& s, int hv) {}

  int last_value()
    char last_char = 
      word.at(word.size() - 1)

• This code can't possibly work

Know Your Tools

if cap = 0
  strArray = new string[1]
  cap++
else if cap == size
  string * newArray = new string[2*cap]
  if 0 = newArray
    cerr << "! Not sufficient capacity"
    exit(1)

• new throws bad_alloc.
  new(nothrow) returns 0.

  • Also, be consistent; check once, check everywhere.

Avoid Globals

void find_characters()
  for (i = 0; i < largest; i++)
    if (i==0)
      for (j = 0; j < countarray[i]; j++)
        string str = lengtharray[i][j]
        carray[indx1][indx2[indx1]++] = str[0]
      indx1++
    else
      for (j = 0; j < countarray[i]; j++)
        string str1 = lengtharray[i][j]
        carray[indx1][indx2[indx1]++] = 
	  str1[str1.size()-1]
      indx1++

References

Minimal Perfect Hash Functions Made Simple by Richard Cichelli, Communications of the ACM, January 1980, pages 17-19.