timequeue.py

"""CSC148 Lab 4: Abstract Data Types

=== CSC148 Winter 2025 ===
Department of Computer Science,
University of Toronto

=== Module Description ===
This module runs timing experiments to determine how the time taken
to enqueue or dequeue grows for different Queue implementations.
"""
from timeit import timeit
from copy import deepcopy
from python_ta import contracts

# Turn off contract checking to minimize its effect on timing experiments
contracts.ENABLE_CONTRACT_CHECKING = False

from myqueue import Queue, QueueOpposite, QueueDeque

###############################################################################
# Task 4: Running timing experiments
#
# In this part of the lab, you will be conducting timing experiments on Queue
# operations.
#
# Make sure you complete the 3 Queue implementations in myqueue.py
###############################################################################
# Experiment Parameters
# Below are our experiment settings: you may want to change these values.
#
# QUEUE_SIZES: This represents the queue sizes we'll be experimenting with.
#              i.e. enqueueing and dequeueing from Queues with size 10000,
#              20000, etc.
# NUM_TRIALS:  This represents the number of times we will repeat an
#              experiment: when we run our timing experiments, we want to get
#              use the average time over a number of trials in order to
#              minimize the effect of any outliers.
###############################################################################
QUEUE_SIZES = [1000, 2000, 4000, 8000, 100000]
QUEUE_TYPES = [Queue, QueueOpposite, QueueDeque]
NUM_TRIALS = 20


def _set_up_queues(qsize: int, n: int, qtype: object) -> list:
    """Return a list of <n> queues, each with <qsize> elements.
    The returned queues should all be of type qtype.

    qtype is either Queue, QueueOpposite, or QueueDeque.

    >>> my_queues = _set_up_queues(1, 2, Queue)
    >>> len(my_queues)
    2
    >>> type(my_queues[0]) == Queue
    True
    >>> my_queues[0].is_empty()
    False
    >>> _ = my_queues[0].dequeue()
    >>> my_queues[0].is_empty()
    True
    """
    # We create a single Queue with the number of elements we want
    q = qtype()
    for _ in range(qsize):
        q.enqueue(1)

    # And make a copy of this Queue (using deepcopy, to save time.)
    queue_list = []
    for _ in range(n):
        queue_list.append(deepcopy(q))

    return queue_list


def time_enqueue(qtype: object) -> list[float]:
    """Run timing experiments for the Queue with type qtype
    """
    # These two lists will hold our timing results.
    queue_times = []

    # This loop runs the timing experiment for enqueueing one item to
    print(f"Running {qtype.__name__}.enqueue experiments...")
    for queue_size in QUEUE_SIZES:
        # 1. Initialize the sample queues
        queues = _set_up_queues(queue_size, NUM_TRIALS, qtype)

        # 2. For each queue created, call the function timeit.
        #    timeit takes three arguments:
        #        - a *string* representation of a piece of code to run
        #        - the number of times to run it (just 1 for us)
        #        - globals is a technical argument that you DON'T need to
        #          care about
        time = 0
        for queue in queues:
            time += timeit('queue.enqueue(1)', number=1, globals=locals())

        # 3. Get the average time in microseconds (μs)
        average_time = (time / NUM_TRIALS) * 1e6

        # 4. Report the average time taken and add that to our list of
        #    results.
        queue_times.append(average_time)
        print(f'Enqueue: Queue size {queue_size:>7}, time (μs): {average_time}')

    return queue_times


def plot_experiment() -> None:
    """Run the timing experiment on AddToStartQueue and AddToEndQueue
     and plot a graph."""
    import matplotlib.pyplot as plt

    # Plot the results of our experiments and assign labels to each plot.
    # Our call to plt.plot takes 3 arguments:
    #     - The x-coordinates of the values to plot
    #     - The y-coordinates of the values to plot
    #     - The format we want to plot with.
    #       'ro' is 'red circle'
    #       'bo' is 'blue circle'
    #       Other formats include 'rx' (red X), 'bx' (blue X) and many more!
    # TODO: If you add more types of Queues, add more markers to this list!
    enqueue_markers = ['ro', 'bo', 'go']

    for i in range(len(QUEUE_TYPES)):
        qt = QUEUE_TYPES[i]
        times = time_enqueue(qt)
        q_plt, = plt.plot(QUEUE_SIZES, times, enqueue_markers[i])
        q_plt.set_label(f"{qt.__name__}.enqueue")

    # TODO: Using the provided code as a template, you may want to
    #       run timing experiments for dequeue as well!
    # Hint: You'll need to make a function like time_enqueue but for dequeue
    #       and then plot the returned time similarly to the above code.

    # After we finish plotting everything, we can create the legend of
    # our graph and label the axes
    plt.legend()
    plt.xlabel("Queue Size")
    plt.ylabel("Average Time (μs)")

    # Show our plotted results. This line must be called after
    # all of the other setup.
    plt.show()


if __name__ == '__main__':
    # Uncomment the plot_experiment() line below to see the plotted graph once
    # you have time_enqueue() working.
    plot_experiment()