A Lazy Algorithm

• Estimating algorithm performance with big-oh.
• Extending a class hierarchy to accommodate new features.
• Adapting tools written earlier to make all of this simpler to run, test, and document.

• Start with the punchline and work backward
• The bottom lines in this graph show the performance we can get by changing our implementation of invasion percolation

Lazy Evaluation

• We have been searching the entire grid to find the next cell to fill
  • But we only need to look on the border
  • And we can keep track of where the border is
• Keep a dictionary called candidates
  • Key: a value in the grid
  • Values: coordinates of cells on the border that have that value
• On each step:
  • Find the lowest key
  • Choose one of its cells at random (to solve the bias problem discovered earlier)
  • Fill it in
  • Add its unfilled neighbors to candidates
• Trading space for time
  • Storing cell values and coordinates is redundant
  • But filling the next cell now takes constant time regardless of grid size
• GridLazy constructor

def __init__(self, width, height, depth):
    """Construct and fill."""
    super().__init__(width, height, depth)
    self._candidates = {}

• Filling algorithm overrides inherited method
  • Fill the center cell
  • Add its neighbors as candidates
  • Repeatedly choose a cell to fill (stopping if we’ve reached the boundary)

def fill(self):
    """Fill grid one cell at a time."""
    x, y = (self.width() // 2, self.height() // 2)
    self[x, y] = 0
    num_filled = 1
    self.add_candidates(x, y)
    while True:
        x, y = self.choose_cell()
        self[x, y] = 0
        num_filled += 1
        if self.on_border(x, y):
            break
    return num_filled

• Adding candidates

def add_candidates(self, x, y):
    """Add candidates around (x, y)."""
    for ix in (x - 1, x + 1):
        self.add_one_candidate(ix, y)
    for iy in (y - 1, y + 1):
        self.add_one_candidate(x, iy)

def add_one_candidate(self, x, y):
    """Add (x, y) if suitable."""
    if x < 0 or x >= self.width() or y < 0 or (y >= self.height()):
        return
    if self[x, y] == 0:
        return
    value = self[x, y]
    if value not in self._candidates:
        self._candidates[value] = set()
    self._candidates[value].add((x, y))

• Choosing a cell

def choose_cell(self):
    """Choose the next cell to fill."""
    min_key = min(self._candidates.keys())
    available = list(sorted(self._candidates[min_key]))
    i = random.randrange(len(available))
    choice = available[i]
    del available[i]
    if not available:
        del self._candidates[min_key]
    else:
        self._candidates[min_key] = set(available)
    self.add_candidates(*choice)
    return choice

• Sweep the same parameter ranges as before
• Performance is much better
  • Searching an \( N{\times}N \) grid is \( N^2 \) operations
  • Fill about \( N^{1.5} \) cells (it’s a fractal)
  • So running time of the naïve approach is proportional to \( N^{3.5} \)
  • Which a computer scientist would write \( \mathcal{O}(N^{3.5}) \)
  • Running time of lazy approach is just \( \mathcal{O}(N^{1.5}) \)

Testing

FIXME: show how to test lazy approach with randomnmess

Exercises

1. Modify the list and array implementation to collect candidate cells of equal lowest value and select one of those.

2. Does it make sense to pre-populate candidates by adding all cells in the grid at the start of the program? Why or why not?