Computer Algorithms II Lecture Notes

4 October 2007 • Performance Estimation in Practice

Outline

• String processing.

• Vector storage management.

Remember This?

string read

while getline(cin, str)
  read += str

for i = 0 to read.size()
  if read[i] == '<'
    // process tag

• Read in a string, then process all tags.

And This?

string read

while getline(cin, str)
  read += str
  for i = 0 to read.size()
    if read[i] == '<'
      // process tag
      read[i] = ' '

• Likewise: read in a string, then process all tags.

• Which program is better?

Let's Estimate!

while getline(cin, str)
  read += str

for i = 0 to read.size()
  if read[i] == '<'
    // process tag

• What's the input?

  • It could be lines or characters processed.

• What's the output?

  • How about statements executed.

Basic Statements

• Take input to be lines processed.

  • Assume n lines were read.

while getline(cin, str) : O(1)
  read += str : O(1)

for i = 0 to read.size() : O(1)
  if read[i] == '<' : O(1)
    // process tag : O(1)

Compound Statements

while O(1) : O(n)
  O(1)

for O(1)
  if O(1) : O(1)
    O(1)

• The while loop iterates O(n) times, executing O(1) + O(1) = O(1) statements on each iteration.

• The if statement executes O(1) + O(1) = O(1) statements.

Iteration Statements

O(n)

for O(1) : O(1)
  O(1)

• The for loop iterates O(n) times.

  • O(1) characters per line * O(n) lines.

Statement Sequences

O(n)

O(n)

• O(n) + O(n) = max(O(n), O(n)) = O(n).

• The number of statements executed is proportional to the number of lines read.

Second Program

• Reduce the basic statements.

while getline(cin, str) : O(1)
  read += str : O(1)
  for i = 0 to read.size() : O(1)
    if read[i] == '<' : O(1)
      // process tag : O(1)
      read[i] = ' ' : O(1)

Compound Statements

• The for loop iterates in proportion to the number of lines read.

Finishing Up

• O(n)*O(n) = O(n*n) = O(n²).

• O(n) vs. O(n²): the first program wins!

Does It?

• Apparently

• See the code; see the data.

Static Arrays vs. Dynamic Data

• C-C++ arrays are static.

  • Once allocated at compile time, array size can't be changed.

• Static arrays don't work well with dynamic amounts of data.

  • Run-time size information usually isn't available at compile time.

• The result is usually too much wasted space or too little storage space.

Dynamic Arrays

• Run-time storage management resolves static storage vs. dynamic data.

  • Allocate arrays at run-time.

    • Size arrays exactly with run-time information.

    • Replace a too-small array with a larger one.

Implementation

class sequence
  T * data;
  unsigned next-data, max-data

  append(T e)

    if next-data >= max-data
      new-data = new [++max-data] T
      for i = 0 to next-data - 1
        new-data[i] = data[i]
      delete [] data
      data = new-data

    data[next-data++] = e    

Appending Costs

• How much does an append cost?

  • It depends. Does the sequence have extra space or not?

• What's the worst-case cost for append?

  • Worst case, every append resizes storage.

    sequence<int> is
    for i = 0 to 100
      is.append(i)
    

Worst-Case Analysis

if next-data >= max-data : O(1)
  new-data = new [++max-data] T : O(1)?/O(n)
  for i = 0 to next-data - 1 : O(1)
    new-data[i] = data[i] : O(1)
  delete [] data : O(1)?/O(n)
  data = new-data : O(1)
data[next-data++] = e : O(1)

if O(1)
  O(1) or O(n)
  for O(1) : O(n)
    O(1)
  O(1) or O(n)
O(1)

Worst-Case Appending

• In the worst case, appending does work proportional to the size of the sequence.

So?

• Is doing work proportional to n so bad?

• Consider

  sequence<int> is
  for i = 0 to 100
    is.append(i)
  

  How much work is going on here, worst case?

Sloppy Analysis

for i = 0 to n : O(1)
  is.append(i) : O(n)

• In each iteration append() does O(n) work in the worst case.

  for O(1) : O(n)
    O(n)
  

• Loading the sequence takes O(n²) work.

Less Sloppy Analysis

for i = 0 to n
  is.append(i)

• In each iteration append() does work proportional to i.

• The total amount of work performed by append() is proportional to

  1 + 2 + ... + n = n(n + 1)/2 = O(n²)

• Loading a sequence can take O(n²) work.

Better Behavior

• Can append() have better behavior? How?

  • “Better” means “asymptotically less.”

• How about amortizing the amount of work done on each append?

  • Reallocate and copy every t appends, rather than on every append.

Amortized Sequences

class sequence

  T * data
  unsigned next-data, max-data
  unsigned a = 50

  append(T e)

    if next-data >= max-data
      new-data = new [max-data += a] T
      for i = 0 to next-data - 1
        new-data[i] = data[i]
      delete [] data
      data = new-data

    data[next-data++] = e 

Worst-Case Analysis

• The code changes in only one place.

if next-data >= max-data : O(1)
  new-data = new [max-data += a] T : O(n)
  for i = 0 to next-data - 1 : O(1)
    new-data[i] = data[i] : O(1)
  delete [] data : O(n)
  data = new-data : O(1)
data[next-data++] = e : O(1)

• And the change isn't enough to effect the code's asymptotic behavior.

Amortization Effects

• In this case, amortization isn't powerful enough to reduce asymptotic complexity.

• Does amortization have any effect at all?

• Consider

  for i = 0 to n
    is.append(i)
  

  with amortizing sequences.

• With sloppy analysis, append() still does O(n) work on each iteration, worst case.

Less Sloppy Analysis.

• Define “work” to mean “copy elements from old to new.”

  for i = 0 to n
    is.append(i)
  

• In each iteration append() does no work, or work proportional to i.

  • When i = ja, append() does work proportional to ja.

    • a the amortization amount; j a positive integer.

Less Sloppy Analysis..

• In total, append() does work proportional to

  0 + ... + a + ... + 2a + ... + ja = n

  a(1 + 2 + ... + j) = aO(j) = O(j) = O(n)

• Loading a sequence still take O(n²) work.

  • But amortization has reduced the constant.

Does It?

• See the code; see the data.

Asymptotically Better Behavior

• Can append() have asymptotically better behavior? How?

• Adding a constant factor isn't powerful enough, in some sense.

• Multiplication is a more powerful form of addition.

• Will multiplying by a constant factor have enough oomph to change the asymptotic behavior?

Multiplicative Sequences

class sequence

  T * data
  unsigned next-data, max-data

  append(T e)

    if next-data >= max-data
      new-data = new [max-data *= 2] T
      for i = 0 to next-data - 1
        new-data[i] = data[i]
      delete [] data
      data = new-data

    data[next-data++] = e 

Analysis.

• What happens to

  for i = 0 to 100
    is.append(i)
  

• The sloppy analysis remains unchanged.

  • Worst case, append() does O(n) work in each iteration.

• The less-sloppy analysis is almost unchanged.

  • When i = 2^j, append() does work proportional to 2^j, j a positive integer.

Analysis..

• In total, append() does work proportional to

  0 + 2⁰ + 2¹ + 0 + 2² + ... + 2^j, 2^j = n

  20 + 21 + ... + 2j	= 2j + 1 - 1
  	= 2*2j - 1
  	= 2n - 1
  	= O(n).

• Doubling the storage size asymptotically reduces the amount of work.

Does It?