Lab 2: Runtime Review

What is Runtime?

Runtime (or Execution Time) is the time it takes a computer to execute a program. Runtime is an important metric that is often used to determine the efficiency of a function. Each program has a best-case runtime and a worst-case runtime. The reason for this is because the runtime of a program is not static. For example, the size of a datafile may affect the iterations a program must perform, which makes the runtime depend on the size of the file. Worst-case runtime is the most common used because we must always account for the worst-case scenarios (i.e. a data file with hundreds of inputs).

Set-Up

The goal of this assignment is to be able to see the differences in runtimes of efficient vs. inefficient functions, through plotted graphs. Most of the program is already written and your task will be to fill in two of the methods.

First, you’ll need to open up a new Project in PyCharm. You can name it runtimeLab and then create a new Python File in the directory named runtime_lab.py. We have provided the stencil code below, which you can copy into the runtime_lab.py file.

import timeit
import gc

''' 
    The best case input is one that would allow an operation to run in
    constant/linear time. This function is returning a list in which all the
    indices are the same. If n = 3, the list would looks as follows:
                            list = [1, 1, 1]
    This is the best case input because, since all the elements are the
    same, something like-- x not in list -- never takes more than a 
    constant number of operations.
'''
def best_case_input(n: int) -> list:
    return [1 for i in range(n)]

''' 
    The worst case input is one that would NOT lead a function to run in
    constant/linear time (i.e. quadratic time). For this function, return
    a list that represents the worst_case_input. This should model a return
    statement really similar to that of best_case_input(). 
'''
def worst_case_input(n: int) -> list:
    # TODO: Return a list representing a worst_case_input
    pass

'''
    This function appends elements from a list to the list d if d does not yet
    have the element. The worst-case runtime for this function is quadratic.
'''
def distinct1(l: list) -> list:
    d = []
    for x in l:
        if x not in d:
            d.append(x)
    return d

'''
    This function adds elements from a list to the set d if d does not yet
    have the element. The worst-case runtime for this function is linear.
'''
def distinct2(l: list) -> list:
    d = set()
    for x in l:
        if x not in d:
            d.add(x)
    return d

''' 
    This method calculates the time it takes a function to run by 
    getting the difference between the end/start times.
'''
def time(fn, arg):
    gc.disable()
    start = timeit.default_timer()
    fn(arg)
    end = timeit.default_timer()
    gc.enable()
    return end - start

'''
    This method graphs/plots the run times of a function given
    across different inputs. The graphs will save as images in
    your current directory.
'''
def graph(name: str, sizes: list, times: list):
    import matplotlib.pyplot as plt

    plt.figure()
    plt.scatter(sizes, times)
    plt.savefig(name + ".png")
    plt.show()
    plt.close()

def generate_graphs():
    '''
        Create a list with 10 different sizes that increment. i.e. 100, 300, 500, etc.
        Your highest size should not exceed 50000.
    '''
    sizes = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

    ''' 
        Create 2 Graphs that represent the Best Case Graphs (efficient run 
        times). 
        1. inputs should be a list of lists: call best_case_input() for every
            size in the sizes list (HINT: use a comprehension)
        2. results1 should be a list with the times it takes to run inputs on
            the distinct1 function: call the time() function by passing in
            distinct1 as the function and arg for every arg in inputs 
            (HINT: use a comprehension)
        3. results2 should be a list with the times it takes to run inputs on
            the distinct2 function: call the time() function by passing in
            distinct2 as the function and arg for every arg in inputs
            (HINT: use a comprehension) 
    '''
    inputs = []
    results1 = []
    results2 = []

    # Calling the graph() to save images of the 2 Best Case Graphs
    graph("best1", sizes, results1)
    graph("best2", sizes, results2)

    ''' 
        Create 2 Graphs that represent the Worst Case Graphs (inefficient run 
        times). 
        1. inputs should be a list of lists: call worst_case_input() for every
            size in the sizes list (HINT: use a comprehension)
        2. results1 should be a list with the times it takes to run inputs on
            the distinct1 function: call the time() function by passing in
            distinct1 as the function and arg for every arg in inputs 
            (HINT: use a comprehension)
        3. results2 should be a list with the times it takes to run inputs on
            the distinct2 function: call the time() function by passing in
            distinct2 as the function and arg for every arg in inputs
            (HINT: use a comprehension) 
    '''
    inputs = [worst_case_input(size) for size in sizes]
    results1 = [time(distinct1, arg) for arg in inputs]
    results2 = [time(distinct2, arg) for arg in inputs]

    # Calling the graph() to save images of the 2 Worst Case Graphs
    graph("worst1", sizes, results1)
    graph("worst2", sizes, results2)
    

if __name__ == '__main__':
    generate_graphs()

IMPORTANT: Since this program uses matplotlib in order to be able to create the graphs and save them to your directory, you will need to head over to the Terminal in PyCharm and run pip install matplotlib.

Task

  • Complete the worst_case_input() method by looking at the hints outlined in the method’s header comment.
  • Complete the generate_graphs() method, which is also outlined in the stencil code. This method is in charge of calling the helper methods, respectively, in order to generate the graphs.

Running File

In order to run the program, you can do either of the following:

  • Use the PyCharm Terminal and call python3 runtime_lab.py
  • Highlight all of the methods and then right-click to select Execute Selection in Python Console. Make sure you call generate_graphs() in the Python Console to then run the program.

After running the program, you should see four images in your directory (best1.png, best2.png, worst1.png, worst2.png). Sometimes you must go to your folder/directory in Finder in order to see the images. These images will show how the runtime increases as the size of the input also increases.


CHECKPOINT:

Once you have completed both methods and the graph images are saved in your directory, notify your TA.