Two Pass Algorithms
Contents
Two Pass Algorithms#
Sometimes as you are working through one step in a loop, you find that you need information that will be available only on a subsequent step. Often the solution is to split your algorithm into two passes through the data. Loop through once to gather the information you need, then loop through again to use that information.
A Simple Example#
Suppose we had a set of scores for a project:
Name |
Score |
|---|---|
Albert |
30 |
Bertal |
24 |
Cheri |
32 |
Dolores |
22 |
Ethan |
20 |
———- |
——- |
The scores might be represented as a list of tuples:
scores = [
("Albert", 30),
("Bertal", 24),
("Cheri", 32),
("Dolores", 22),
("Ethan", 20)
]
Suppose we wished to normalize these scores, replacing the raw score by a a ratio to the average (arithmetic mean) score. (This is a very bad idea, but we will suppose it for the sake of the example.) Since Cheri’s score is 125% of the average score, her score should be represented as 1.25. Since Ethan’s score is 78% of the average score, his score should be represented as 0.75.
Name |
Score |
|---|---|
Albert |
1.17 |
Bertal |
0.94 |
Cheri |
1.25 |
Dolores |
0.86 |
Ethan |
0.78 |
We might begin to write a simple function to build the list of tuples with normalized scores:
def normalize_scores(scores: List[Tuple[str, Number]]) -> List[Tuple[str, float]]:
"""Normalized scores are fraction of average"""
result = [ ]
for student, score in scores:
normalized = score / mean ## I need the mean here!
result.append((student, normalized))
return result
To make this work, we need the mean value. We could try calculating it as we loop through the entries:
def normalize_scores(scores: List[Tuple[str, Number]]) -> List[Tuple[str, float]]:
"""Normalized scores are fraction of average"""
result = [ ]
total = 0
count = 0
for student, score in scores:
count += 1
total += score
mean = total / count # This is not correct!
normalized = score / mean
result.append((student, normalized))
return result
This doesn’t work … it divides the score by the sum so far rather than the sum of all entries.
We could get very fancy with a list comprehension to calculate the sum and count each time we need them:
def bad_normalize(scores: List[Tuple[str, Number]]) -> List[Tuple[str, float]]:
"""Looks cute, but this algorithm is quadratic in length of list!"""
result = [ ]
count = len(scores)
for student, score in scores:
total = sum([score for name, score in scores])
mean = total / count
normalized = score / mean
result.append((student, normalized))
return result
This looks clever, but it is actually very bad. While the code looks like
it only has one loop, it is actually nested loops, because the
sum and the list comprehension are actually loops through the
list of scores. We won’t notice the inefficiency for a list of
five scores. We would surely notice for
a list of 1000 scores.
The fix is very simple: We need to calculate the total just once. We loop through the list of scores once to get the total (and perhaps also the count), and then loop through again to produce the normalized list:
def normalize_scores(scores: List[Tuple[str, Number]]) -> List[Tuple[str, float]]:
"""Normalized scores are fraction of average"""
# Pass 1: Gather the summary information
total = 0
count = 0
for student, score in scores:
count += 1
total += score
mean = total / count
# Pass 2: Use the summary information
result = [ ]
for student, score in scores:
normalized = score / mean
result.append((student, normalized))
return result
There are still two loops in this solution, but now they are not nested loops. Suppose there are n entries in the list; nested loops will touch each entry n2 times, but one loop followed by another loop through the same items will touch each entry only 2n times. For a list of 1000 items, the difference is 1,000,000 vs 2000 operations.
Summarizing in a Table#
In the example above, we just needed a couple of variables
(total and count) to hold the summary information. Often
we will need more. In that case, instead of a few summary
variables, we may need a table of summary information.
A typical real-life example requiring a table of summary information is producing cross references in text formatting. For example, the source code for a book to be formatted by the LaTeX document processing system might include a cross-reference entry like this:
As we will explain in more detail later (page \ref{sec:binary}),
executable code in computer memory is indistinguishable
from data.
Another part of the document source code might indicate the intended page number:
\Section{Binary Encoding Of Everything You can Imagine}
\label{sec:binary}
Everything is binary. Everything. That too.
And it's all a big undifferentiated soup of numbers
until we decide how to interpret it.
The text formatting system has to essentially format the whole text twice.
On the first pass it may discover that the label sec:binary appears on
page 42. This might be before or after the cross reference; either way
it saves the pair ("sec:binary", 42) in a table, and uses that table
on the second pass when it can substitute the page number for the
reference.
As a less realistic but simpler example, suppose we have a list of fruits like this:
fruit_bowl = ["banana", "orange", "banana", "kiwi", "banana", "orange"]
We want “m of n” style formatting for each item in the bowl:
banana 1 of 3
orange 1 of 2
banana 2 of 3
kiwi 1 of 1
banana 3 of 3
orange 2 of 2
We will write a function itemize_fruits to produce the
printed list of fruits in a bowl.
def itemize_fruits(bowl: List[str]):
"""Print the fruits as
banana 1 of 3
orange 1 of 2
etc
"""
Keeping a count is not difficult, but we need two counts for each fruit:
the total count, and the count of items encountered so far.
In the first pass through the list of fruits, we will produce the
table of total counts:
# Pass 1
full_counts = { } # We'll keep summary information here
for fruit in bowl:
# Ensure there is an entry for the fruit
if fruit not in full_counts:
full_counts[fruit] = 0
full_counts[fruit] += 1
In the second pass, we will recompute counts and store them in a separate table.
# Pass 2
cur_counts = { }
for fruit in bowl:
# Ensure this is an entry for the fruit
if fruit not in cur_counts:
cur_counts[fruit] = 0
cur_counts[fruit] += 1
We could make a third pass through the list to do the actual printing, but it is not necessary. We can print as soon as we have computed the the second count, in the same loop:
def itemize_fruits(bowl: List[str]):
"""Print the fruits as
banana 1 of 3
orange 1 of 2
etc
"""
# Pass 1
full_counts = { } # We'll keep summary information here
for fruit in bowl:
# Ensure there is an entry for the fruit
if fruit not in full_counts:
full_counts[fruit] = 0
full_counts[fruit] += 1
# Pass 2
cur_counts = { }
for fruit in bowl:
# Ensure this is an entry for the fruit
if fruit not in cur_counts:
cur_counts[fruit] = 0
cur_counts[fruit] += 1
# Now we have both pieces of information
print(f"{fruit} {cur_counts[fruit]} of {full_counts[fruit]}")
Application to the Assembler Project#
In week 8 of CIS 211, you will build the address resolution logic of an assembler, a program that translates Duck Machine assembly code to machine code. What you will create actually is the first phase of the assembler, which resolves labels to pc-relative addresses. Given an input program like this:
# Determine the maximum of two integers.
# This program triggers memory-mapped IO to
# read integers from the keyboard and to
# write integers to the display.
LOAD r1,r0,r0[510] # Trigger read from console
LOAD r2,r0,r0[510] # Trigger read from console
SUB r0,r1,r2[0]
JUMP/P r1bigger
STORE r2,r0,r0[511] # Trigger write to console
HALT r0,r0,r0
r1bigger:
STORE r1,r0,r0[511] # Trigger write to console
HALT r0,r0,r0
Your program will translate the label r1bigger into a
PC-relative address, resulting in a modified (“resolved”)
version of the program, like this:
# Determine the maximum of two integers.
# This program triggers memory-mapped IO to
# read integers from the keyboard and to
# write integers to the display.
LOAD r1,r0,r0[510] # Trigger read from console
LOAD r2,r0,r0[510] # Trigger read from console
SUB r0,r1,r2[0]
ADD/P r15,r0,r15[3] #Jump to r1bigger
STORE r2,r0,r0[511] # Trigger write to console
HALT r0,r0,r0
r1bigger:
STORE r1,r0,r0[511] # Trigger write to console
HALT r0,r0,r0
Note that the JUMP/P pseudo-instruction has been translated
to the real Duck Machine instruction ADD/P (add if positive),
and that the instruction adds 3 to the program counter
in register 15. The relative address 3 is the difference
between address 6 at which the label r1bigger appears
address 3 at which the jump appears.
Just as we counted fruits twice above to itemize them,
your address resolver will need to count instructions
twice to determine the addresses. In the first pass,
you will create a table associating labels like r1bigger
with addresses by counting the number of machine instructions
to be produced. In the second pass, you will count
machine instructions again, and also produce the
modified program code.
Summary#
We often use multi-pass (two-pass or more) algorithms when a step in a loop requires information that will not be available until a future step. We make (at least) one “pass” (loop) through the whole data to gather the needed information, and then a second “pass” to use it. Sometimes we only need a summary variable or two, but often we need a table to hold whatever information we need to summarize.
Example Code#
Sample source code is available for this chapter.