6.1.6 – Compare program efficiency

6.1.6 – Compare program efficiency

Compare correct programs using named comparisons, loop passes and additional data stored. Explain when early stopping or retaining data helps the stated purpose, and when it does not.

Count comparisons and loop passes

Two programs can be fit for the same purpose but do different amounts of work. The comparison must use the same requirement and test data, and it must state what is being counted.

Comparison and loop pass

In the examples below, one comparison means one evaluation of code == target. One loop pass means one execution of the loop body. Loop-control checks and hidden interpreter work are not included in this stated counting convention.

Requirement: print whether target occurs anywhere in codes. For this efficiency investigation, also print the number of target comparisons.

Program A: scan every item

Python
codes = ["C04", "C11", "C18", "C25", "C32", "C40"]
target = "C18"
found = False
comparisons = 0

for code in codes:
    comparisons = comparisons + 1
    if (code == target):
        found = True

print(found)
print(comparisons)

Program B: stop scanning once the target is found

Python
codes = ["C04", "C11", "C18", "C25", "C32", "C40"]
target = "C18"
found = False
comparisons = 0
index = 0

while (index < len(codes)) and (not found):
    comparisons = comparisons + 1
    if (codes[index] == target):
        found = True
    index = index + 1

print(found)
print(comparisons)

Both programs are PLS-safe and predict True, so both meet the requirement for this input. The trace exposes their different work:

ProgramPassItem compared with C18Comparison resultfound after pass
A1C04FalseFalse
A2C11FalseFalse
A3C18TrueTrue
A4C25FalseTrue
A5C32FalseTrue
A6C40FalseTrue
B1C04FalseFalse
B2C11FalseFalse
B3C18TrueTrue, so the loop ends

Program A makes 6 target comparisons and 6 loop passes. Program B makes 3 target comparisons and 3 loop passes. Its predicted output is:

Output
True
3

The improvement depends on the data. If target is absent, both programs make 6 target comparisons and 6 passes; if it is the final item, both again make 6. Early stopping reduces work only when the target is found before the final item. "Stops early" does not mean "always does less work".

Judge memory use

Efficiency also includes memory use. At this level, compare the additional data stored by each program and how that storage can grow; do not invent exact byte totals, because Python object sizes can depend on the implementation.

Requirement: print the number of readings that are at least 15.

Program A: store every matching value

Python
readings = [12, 18, 9, 16, 20, 15]
high_readings = []

for reading in readings:
    if (reading >= 15):
        high_readings.append(reading)

print(len(high_readings))

Program B: store only a running count

Python
readings = [12, 18, 9, 16, 20, 15]
high_count = 0

for reading in readings:
    if (reading >= 15):
        high_count = high_count + 1

print(high_count)

The state after each loop pass is:

PassReadingProgram A: high_readingsProgram B: high_count
Initial-[]0
112[]0
218[18]1
39[18]1
416[18, 16]2
520[18, 16, 20]3
615[18, 16, 20, 15]4

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account