Project 9 Starter Bits

complexity_lab.py

import timeit

# Complexity experiment time.
# Both sum_1x and sum_2x are O(n) functions.
# Let's investigate which is faster AND see if it's linear.


def sum_2x(target: list) -> int:
    total = 0
    for x in target:
        total += x
    for x in target:
        total += x
    return total


assert sum_2x([1, 2, 3]) == 2 + 4 + 6


def sum_1x(target: list) -> int:
    total = 0
    for x in target:
        total += 2 * x
    return total


assert sum_1x([1, 2, 3]) == 2 + 4 + 6


def run_experiment(function, input, repeat=100):
    # write down the current time
    start_time = timeit.default_timer()
    # run the function 100x or so
    for repeat_num in range(repeat):
        function(input)
    # write down our finish time
    end_time = timeit.default_timer()

    # return average time:
    return (end_time - start_time) / repeat


with open("timing.csv", "w") as spreadsheet:
    # a spreadsheet header
    print("n,sum2x_millis,sum1x_millis", file=spreadsheet)

    # TODO: figure out a bit of how 'run_experiment' works.
    # TODO: write a loop around some of this code to try a whole bunch of lengths/ns
    # HINT: consider multiplying the array to make it longer, or something like list(range(n))

    example = [1, 2, 3, 4]
    sum2x_time = run_experiment(sum_2x, example)
    sum1x_time = run_experiment(sum_1x, example)
    # for immediate printing:
    print("sum2x-time", sum2x_time)
    print("sum1x-time", sum1x_time)

    # for the spreadsheet (don't mess with this print-statement too much)
    # string.format is a neat function that replaces {} patterns with variables.
    #  it also supports asking for a set number of decimal points {:.7f} from floats
    print(
        "{},{:.7f},{:.7f}".format(len(example), sum2x_time * 1000, sum1x_time * 1000),
        file=spreadsheet,
    )

# TODO: import the timing.csv to Excel (once you have a handful of rows)