LAB6_EFFICENCY.PY
TERMINALPLOT.PY
Exercise 2: Compare the Time Efficiency of Bounded and Circular Queues In this task, you will compare the runtimes of the dequeue() methods in the Bounded Queue and the Circular Queue. In the Bounded Queue, the dequeue method removes the item at the front of the queue, and then shifts the remaining items in the list to the left (i.e. to fill in the hole created by removing that first item). For a Bounded Queue containing n items, what is the big-O time efficiency of the dequeue? In the Circular Queue, you just shift the head index when you dequeue an item - no shifting of the actual data elements is required. For a Circular Queue containing n items, what is the big-O time efficiency of the dequeue? Considering your answers to the above two questions, which queue's dequeue do you predict will run faster? 1. Download and save labb_efficiency.py and terminalplot.py. (Save in the same folder as your queue.py from Exercise 1.) In this file, both your Bounded and Circular Queues have been imported from queues.py. This file also contains 4 function definitions: 3 have already been completed for you (enqueue_experiment, average_de queue_experiment, and main). Read through the comments of those 3 functions to understand what they are doing. 2. Complete the function de queue_experiment (queue) so that it removes the first item in the queue, and continues to do so until that queue is empty. Note that the queue is passed in as an input to the function - so you do NOT have to create it or fill it with data in this function. Use a function from either the time or timeit modules to measure how long it takes to dequeue all of the items in the queue, and return that time measurement. Hint: there is an example of how to use time.time () at the bottom of labb_efficiency.py. The time module returns times in seconds. import time start = time. time() # The statement(s) that you want to test end = time.time() time_interval = end - start 3. Run labb_efficiency. (This may take some time to run.) This will run a number of experiments, measuring the time it takes to dequeue all items from Bounded and Circular Queues of increasing capacities. These times will be printed in a table for you to view. The data should also be plotted for you, with time on the y-axis, and n on the x-axis (where n is the number of dequeues made). If a plot is not displayed (i.e. if you see a message that says "Not able to print graph. Continuing..."), plot the data from the table using a spreadsheet program. You can run more experiments with larger queue capacities to get more values for your graph, but keep in mind that doing so will increase the runtime of the overall program. Which has a more efficient dequeue method: the Bounded Queue, or the Circular Queue? import random import time from queues import BoundedQueue from queues import CircularQueue from decimal import Decimal from terminalplot import plot2 def enqueue_experiment (queue_class, queue_size): This function will enqueue elements into Bounded and Circular queues and return them :param queue_class: The queue_class description that we want to declare the object for like BoundedQueue, CircularQueue :param queue_size: The size of the queue and the number of elements that we want to enter in queue :return: Bounded Queue Object, Circular Queue Object # init the relevant objects queue = queue_class (queue_size) # enqueue elements to max capacity of queue while not queue.is_full(): value = random.random() queue.enqueue (value) return queue def dequeue_experiment (queue): This function will be responsible for dequeues the elements in the queue :param queue: (queue object) The queue object that we want to test on :return: (float) Returns the time of execution of the dequeue operation time = 0.0 # the time to dequeue all the elements ##### START CODE HERE ##### ## ### END CODE HERE ### ### return time def avg_dequeue_experiment (queue_class, size, sample_size = 5): This function is used to average over many runs for the de queue experiment :param queue_class: (function-type) The typeof queue that we are using :param size: (int) Size of the queue to do experiment :param sample_size : (int) The number of samples to be used for averaging :return: (float) return the average time q_run_avg = 0 for i in range (sample_size): queue = enqueue_experiment (queue_class, size) q_run_avg += dequeue_experiment (queue) return float (q_run_avg)/sample_size def main(): # queue sizes that we will use for different experiments # queues_sizes = [10000, 20000 30000, 40000, 50000, 60000, 70000, 80000, queues_sizes = [10000, 30000, 50000, 70000, 90000, 100000] 90000, 100000] # the setup of the experiment bqueues = [] cqueues = [] for q in queues_sizes: # print ("Done for Queue Size : ()". format (.)) b = enqueue_experiment (BoundedQueue, q) cq = enqueue_experiment (Circular Queue, q) bqueues.append (ba) cqueues.append (ca) # perform the dequeue experiment bounded_queue_times = [dequeue_experiment (g) for q in bqueues) circular_queue_times = [de queue_experiment (9) for qin cqueues ] # print table of results for one run each (not averaged) print ("Times for Bounded and Circular Queue without using Average") line = '-'*(13 + 14*len (queues_sizes)) line2 = str('-'*13 + '+')*(1 + len (queues_sizes)) print (line) print (str(" Queue Size "+' '.join(" {:
