Data Structures & Algorithms Lecture Notes

15 October 2009 • Performance Estimation in Practice

Outline

String processing.
Vector storage management.

Remember This?

StringBuilder read

while str = input.readline()
  read.append(str)

for i = 0 to read.length()
  if read.charAt(i) == '<'
    // process tag

Read in a string, then process all tags.

And This?

StringBuilder read

while str = input.readline()
  read.append(str)
  for i = 0 to read.length()
    if read.charAt(i) == '<'
      // process tag
      read.setCharAt(i, ' ')

Likewise: read in a string, then process all tags.
Which program is better?

Let's Estimate!

while str = input.readline()
  read.append(str)

for i = 0 to read.length()
  if read.charAt(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 str = input.readline() : O(1)
  read.append(str) : O(1)

for i = 0 to read.length() : O(1)
  if read.charAt(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 str = input.readline() : O(1)
  read.append(str) : O(1)
  for i = 0 to read.length() : O(1)
    if read.charAt(i) == '<' : O(1)
      // process tag : O(1)
      read.setCharAt(i, ' ') : O(1)

Compound Statements

while O(1)
  O(1)
  for O(1)
    if O(1)
      O(1)
      O(1)

while O(1)
  O(1)
  for O(1)
    O(1)

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

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

Finishing Up

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

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

Does It?

string processing performance

Apparently
See the code; see the data.

Static Arrays vs. Dynamic Data

Once allocated at compile time, static-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
  Object data []
  int next-data

  append(T e)

    if next-data ≥ data.length()
      Object new-data [] = 
        new Object [data.length() + 1]
      for i = 0 to data.length() - 1
        new-data[i] = data[i]
      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<Integer> is
for i = 0 to 100
  is.append(i)
```

Worst-Case Analysis

if next-data ≥ data.length() : O(1)
  Object new-data [] = new 
    Object [data.length() + 1] : O(1)?/O(n)
  for i = 0 to data.length() - 1 : O(1)
    new-data[i] = data[i] : O(1)
  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

if O(1)
  O(1) or O(n)
  O(n)
  O(1) or O(n)
O(1)

if O(1)
  O(n)
O(1)

O(n)
O(1)

O(n)

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<Integer> 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
  Object data []
  int next-data
  unsigned a = 50

  append(T e)

    if next-data ≥ data.length()
      Object new-data [] = 
        new Object [data.length() + a]
      for i = 0 to data.length() - 1
        new-data[i] = data[i]
      data = new-data

    data[next-data++] = e

Worst-Case Analysis

The code changes in only one place.

 if next-data ≥ data.length() : O(1)
  Object new-data [] = new 
    Object [data.length() + a] : O(n)
  for i = 0 to data.length() - 1 : O(1)
    new-data[i] = data[i] : O(1)
  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?

amortization in effect

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

  Object data []
  int next-data

  append(T e)

    if next-data ≥ data.length()
      Object new-data [] = 
        new Object [data.length()*2]
      for i = 0 to data.length() - 1
        new-data[i] = data[i]
      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

2⁰ + 2¹ + ... + 2^j = 2^{j + 1} - 1

= 2*2^j - 1

= 2n - 1

= O(n).
Doubling the storage size asymptotically reduces the amount of work.

Does It?

amortization vs doubling

Summary

For better performance, find an asymptotically better algorithm.

2⁰ + 2¹ + ... + 2^j	= 2^{j + 1} - 1
	= 2*2^j - 1
	= 2n - 1
	= O(n).