Comet has search functions scattered across three practice files. "Let's copy the one we need into each program," she says.
Wren shakes his head and taps last week's fleet.py. "What does the evidence say? One trusted file worked well for the fleet. One trusted file can work for searching too."
Comet laughs. "Fine. And I want one more search in it, a fast one. Nova keeps hinting about halves."
Nova projects the sorted catalog grams with a bright line down the middle. "How can I help?" she asks. "Type it today. Tomorrow we trace why it is fast."
Wren clips a fresh sheet to his board. "Lead programmer, type. I will count checks."
Stage 1. Every run of search.py today shows nothing at all, because the file only defines functions. No output and no traceback means the file has no syntax errors.
# search.py
# Searching the catalog and the field (week 8).
def linear_search(items, target):
"""Index of the first item equal to target, or -1."""
for i in range(len(items)):
if items[i] == target:
return i
return -1
def find_label(samples, label):
"""The Sample with this label, or None."""
for s in samples:
if s.label == label:
return s
return None Stage 2: find_in_grid().
def find_in_grid(rows, mark):
"""(row, col) of the first cell holding mark, row by row, or None."""
for r in range(len(rows)):
for c in range(len(rows[r])):
if rows[r][c] == mark:
return (r, c)
return None Stage 3: binary_search(). You will trace it tomorrow. For now, type it carefully and read the docstring.
def binary_search(items, target):
"""Index of target in a sorted list, or -1."""
low = 0
high = len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid
elif items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 Now search_demo.py imports all four functions. Made-up data from the FieldSim story.
# search_demo.py
from field_data import CATALOG, FIELD
from sample import Sample
from search import binary_search, find_in_grid, find_label, linear_search
samples = []
labels = []
for label, kind, grams in CATALOG:
samples.append(Sample(label, kind, grams))
labels.append(label)
print(linear_search(labels, "S04"))
print(find_label(samples, "S06").kind)
print(find_in_grid(FIELD, "*"))
sorted_grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
print(binary_search(sorted_grams, 51)) 3 shale (0, 2) 7
A statement execution count is how many times a line runs. Wren's counting copy counts the checks inside linear search, on the sorted grams.
# count_linear.py
# A copy of linear_search that also counts its checks.
def linear_count(items, target):
"""Gives back (index or -1, number of checks)."""
checks = 0
for i in range(len(items)):
checks += 1
if items[i] == target:
return i, checks
return -1, checks
# Made-up data from the FieldSim story: the catalog grams, sorted.
sorted_grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
print(linear_count(sorted_grams, 39))
print(linear_count(sorted_grams, 40)) (5, 6) (-1, 10)
Change one thing: add print(linear_count(sorted_grams, 7)) and print(linear_count(sorted_grams, 88)) at the end. Predict, then run.
(5, 6) (-1, 10) (0, 1) (9, 10)
Break one thing on purpose: in search_demo.py, change samples to CATALOG in the find_label line. Run it and read the traceback calmly. Then change it back.
3
Traceback (most recent call last):
File "search_demo.py", line 13, in <module>
print(find_label(CATALOG, "S06").kind)
~~~~~~~~~~^^^^^^^^^^^^^^^^
File "search.py", line 16, in find_label
if s.label == label:
^^^^^^^
AttributeError: 'tuple' object has no attribute 'label' search.py is done: four searches in one trusted module. Tomorrow you trace binary search and see why it needs so few checks.