Lecture Notes for Computer Algorithms I

4 December 2003 - Assignment 4 Code Review

Outline

• Design

  • The printing-changing trade-off.

• Tests

  • Don't forget old friends.

• Implementation

The Problem

• Keep cumulative word counts for all Web pages received.

  • Print the cumulative word counts after every page.

• We need a data structure that supports two operations:

  1. Add new word counts for a page.

  2. Print all word counts gathered so far.

• The problem is adding and printing are in conflict.

  • Adding is a page-specific operation.

    • Adding also means replacing pages already added.

  • Printing is a word-specific operation.

  • A data structure good for one is not good for the other.

Wishin' for Addition

• Let's stay with what we have and consider adding pages.

  • We already have lists of words on a page.

• What we want is a list of page-word lists.

• Adding new page-word lists is easy.

• Replacing an existing page-word list is almost as easy.
• But printing cumulative word counts seems hard.

  • The counts are spread all over the list of lists.

Let's Try Printing Instead

• Keep a list of words, each word pointing to a list of pages.

• Each page contains the associated word.

• This is a common design trick known as inverting the data structure.

  • Well, that's what I call it.
• Printing is now a snap.

• Adding a new page not too difficult or costly.

  • Replacing an existing page, however, is expensive.

  • Adding links to makes it cheaper but increases complexity.

Making The Decision

• This is a non-trivial decision; the trade-offs are real.

  • Easy printing vs. easy replacing.

• Good designers, when faced with tough decisions, punt.

• Wish for a data structure that supports both adding pages and printing words.

  • O.k. *poof* you got it. Now what?

  void
  mitm(string uri, resource document)
  
    word_info * words = get_words(document)
  
    if (words)
      concordance::add_page(uri, words)
      concordance::print_words(std::cout)
  

• We can hide our decision behind the data structure.

Really Making the Decision

• We can decide in the isolation and protection of our concordance ADT.

  • Because we've already got them, let's go with a list of page-word lists.

• Adding new and replacing old page-word lists is easy.

• Printing will require some thought.
  

Sorting

• An auxiliary array points to the set of words available for printing.

  • Sorting the array tells us the next word to print.

• Copies of the same word get sorted again on count.

• After printing a word, the associated array pointer advances to the next word.

  • Null pointers get dropped off the array.

• Stop when all pointers drop off the array.

Word Sorting

static sort_node * sort_by_words(
  sort_node * words_s, sort_node *& words_e)

  // Compress nulls.
  for snp = words_e - 1; words_s <= snp; --snp
    if (not snp->word)
      *snp = *--words_e;

  // Sort by word.
  for snp = words_s; snp < words_e; snp++
    min = snp
    for j = snp + 1; j < words_e; j++
      if min->word->word > j->word->word
	min = j
    swap(snp, min)

  // Find leftmost run.
  for snp = words_s; snp < words_e; snp++
    if snp->word->word != words_s->word->word
      break
  sort_by_count(words_s, snp)

  return snp

Printing

void
print_pages(std::ostream & os)

  sort_node * const words_s, * words_e = 
    top_words(pages_visited)

  while true
    sort_node * const words_m 
      = sort_by_words(words_s, words_e)
    if (words_s >= words_e) break

    for snp = words_s; snp < words_m; snp++
      assert(snp->word and snp->page)
      os << snp->word->word << " "
         << snp->page->page_name << " "
         << snp->word->cnt << " "
         << snp->page->word_count << "\n"
      snp->word = snp->word->next

  delete [] words_s

Consider the Alternative

• How would a list of word-pages work?

• The problem is replacing an old page with a newer one.

  • The old page entries have to be found and removed.

• This isn't too hard to do if there's cross-links between the word-page lists.

  • The cross-links keep track of pages from list to list.

• Fast printing isn't that crucial.

• Fear pointer errors.
• Maybe next time.

Test Cases

• The test cases were

  • Old friends.

    • Empty pages and bodies.

    • Bodies broken, spaced and tabbed.

    • Pages of 50 and 1000 words.

  • New faces.

    • Simple words in pages.

    • Repeated words in pages.

    • Repeated words across pages.

    • Same pages with different words (the CNN test).

The Results

	c	n	-	+	y
empty page	0	0	0	0	12
empty body	0	1	0	1	10
broken body	0	1	0	0	11
spaced body	0	7	0	2	3
tabbed body	0	8	0	1	3
1000 words	0	5	1	1	5
50 words	0	8	1	1	2
two words	0	7	0	2	3
redundant words	0	8	0	2	2
repeated words	0	10	0	1	1
changing words	0	10	0	0	2

• Three people submitted code that didn't compile.

• Four people submitted nothing.

Count the Errors

long findBodyStart(
long start, long end, string totalString)

  for (long pos = start; pos < end; pos++)
   if totalString[pos] == '<'
    if toupper(totalString[pos+1]) == 'B'
     if toupper(totalString[pos+2]) == 'O' 
      if toupper(totalString[pos+3]) == 'D' 
       if toupper(totalString[pos+4]) == 'Y' 
        pos +=5
        while (totalString[pos] != '>') pos++
        if totalString[pos] == '>' && pos < end
         return(pos+1)

long findBodyEnd(
  long start, long end, string totalString)

  for long pos = start; pos + 6 < end; pos++
   if totalString[pos] == '<'
    if totalString[pos+1] == '/'
     if toupper(totalString[pos+2]) == 'B' 
      if toupper(totalString[pos+3]) == 'O' 
       if toupper(totalString[pos+4]) == 'D' 
        if toupper(totalString[pos+5]) == 'Y'
         if totalString[pos+6] == '>'
          return pos

A Tale of Two Sorts, I

void StrLinkedList::Sort()

  LinkedNode 
    * Current = Head_Node,
    * SmallestNode,
    * Next
  int intsmallestcount
  std::string strsmallestsword

  while Current != NULL
    SmallestNode = Current
    intsmallestcount = Current->count
    strsmallestsword = Current->word
    Next = Current->Next_Node

    while Next != NULL
      if Next->count < intsmallestcount
        SmallestNode = Next
	intsmallestcount = Next->count
	strsmallestsword = Next->word
      Next = Next->Next_Node

    SmallestNode->count = Current->count
    SmallestNode->word = Current->word
    Current->count = intsmallestcount
    Current->word = strsmallestsword
    Current = Current->Next_Node

A Tale of Two Sorts, II

void AddressLinkedList::Sort()

  Node * Current = Head,
       * GreatestNode,
       * Next;

  int intGreatestcount

  while Current != NULL

    GreatestNode = Current
    intGreatestcount = Current->Count
    Next = Current->Next

    while Next != NULL
      if Next->Count > intGreatestcount
        GreatestNode = Next
	intGreatestcount = Next->Count
    Next = Next->Next

    GreatestNode = Current
    Current->Count = intGreatestcount
    Current = Current->Next

Two Sorts Compared

• Sort I is

  • Potentially more expensive.

  • Breakable (also known as fragile or brittle).

  • Better written as (if you need to write it this way at all)

    while Current != NULL
      *smallest = *Current
      Next = Current->Next_Node
    
      while Next != NULL
        if Next->count < smallest->count
          smallest = *Next
        Next = Next->Next_Node
    
      swap(*smallest, *current)
      swap(smallest->next current->next)
    

    • Although it should not be written this way at all.

• Programmers using pointers are on a short leash.

  • Make sure you show you're well behaved.

Know Your Tools

• You may have seen this message:

  I've writting the following code
  
    ostringstream message
    message << *this
    document.size = message.str().size()
    document.data = new char [document.size]
    document.data = message.str().c_str()
  
  and gcc is complaining about
  
    LList.cc:55: warning: invalid conversion 
    from const char* to char*
  
  While this is just a warning and the code 
  seems to work, is there a better way to 
  do this?
  

• This programmer's leash has run out.

Hello Garbage

• The code

  document.data = new char [document.size]
  document.data = message.str().c_str()
  

  has two problems, here's the first.

  

Hello Hyperspace

• The code

  document.data = new char [document.size]
  document.data = message.str().c_str()
  

  has two problems, here's the second.

  

• The programmer has been leashed, hog-tied, and left at curbside.

Points to Remember

• Understand the trade-offs.

  • Know the value of something, and the frequency.

• Hide your decisions behind ADTs.

  • You can be dumb, and wrong, and change it easily.

• Your code is talking about you, make sure it's saying nice things.

• Know your tools, and use them.

  • There's no excuse not to.

This page last modified on 5 December 2003.