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 commonly used metric 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.

This stencil code contains 7 functions. The generate_graphs function will use its helpers graph and time to plot graphs which show the runtimes of distinct1 and distinct2 on different inputs. Those inputs will come from the best_case_input and worst_case_input functions. Although distinct1 and distinct2 have the same functionality, distinct2 should be faster in the worst-case scenario. You will implement worst_case_input and finish the stencil of generate_graphs.

When the input to distinct1 and distinct2 is the output from best_case_input, they should run with their best (fastest) possible runtimes. When the input to distinct1 and distinct2 is the output from worst_case_input, they should run with their worst (slowest) possible runtimes.

When you implement worst_case_input, start by looking at distinct1 and distinct2. In what cases do distinct1 and distinct2 have the best possible runtime? In what cases do distinct1 and distinct2 have the worst possible runtime? Construct an input to distinct1 and distinct2 which would give them the worst case runtime. That value should be returned by worst_case_input.

Open up a new Project in VSCode. You can name it runtime_lab and then create a new Python File in the directory and name it runtime_lab.py. We have provided the stencil code below, which you can copy into the runtime_lab.py file.

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 and run pip3 install matplotlib.

import timeit
import gc

'''
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 function returns a list which is the best case input to distinct1 and distinct2

The best case input allows distinct1 and distinct2 to run in constant time. This function is returning a list in which all the indices are the same. If n = 3, the list would look 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)]

''' 
This function reruns a list which is the worst case input to distinct1 and distinct2

It causes distinct1 to work in quadratic time and distinct2 to work in linear time.

Try to find which step of distinct1 makes it take longer than distinct2, and write a list which would cause that piece to be slower - that is the list which worst_case_input should return
'''
def worst_case_input(n: int) -> list:
    # TODO: FILL ME IN
    pass

''' 
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 runtimes 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] # TODO - CHANGE ME

    '''
    Create 2 Graphs that represent the Best Case Graphs (efficient runtimes).

    1. inputs should be a list of lists: call best_case_input() for every size in the sizes list

    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

    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
    '''
    inputs = [] # TODO - CHANGE ME
    results1 = [] # TODO - CHANGE ME
    results2 = [] # TODO - CHANGE ME

    # 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

    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

    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
    '''
    inputs = [] # TODO - CHANGE ME
    results1 = [] # TODO - CHANGE ME
    results2 = [] # TODO - CHANGE ME

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


if __name__ == '__main__':
    generate_graphs()

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

Use a Terminal to navigate to your runtime_lab directory and call python3 runtime_lab.py to 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. You can also open these images directly in VSCode. These images will show how the runtime increases as the size of the input also increases.

---

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