CS 345 Homework 9

Due Monday Apr 10 at 9pm. Upload to Desire 2 Learn dropbox for homework 9.

Benchmarking Iteration Solution

Description

This homework exercise should allow you to observe the performance benefits of various approaches to processing data structures. You are going to write a number of functions that process lists as arrays and linked lists. You are then going to use the timeit library to observe performance differences between each of pair of functions. Functions are described below.

Functions:

1a. sum the values in a large list (n > 100000) using a for loop

1b. sum the values in a large list (n > 100000) using python’s sum() method

2a. push (), pop() operations on a Queue implemented using a python list.

push to end of list. pop from front e.g., pop(0)

2b. enqueue(), dequeue() operations on a Queue implemented using a LinkedList.

use linked_queue.py

Write each of the functions above in one source code file. You will need additional files in the directory to reference external classes. Compare each pair of functions using timeit. For each comparison, print out the results of each benchmard (three pairs total)

Turn In:

Your source code file containing your functions and timeit tests.

Resources

DSAP Source Code files

What to Turn In?

Your submission will include one source code file named according to syllabus.

Solution

# solution hw9 cs345 sp 2017
from collections import deque
import timeit
from timeit import Timer

from linked_queue import LinkedQueue

#  Build test data structures:
nums = range(100000)
qlist_a = nums
qlist_b = LinkedQueue()
for i in nums: qlist_b.enqueue(i)
qlist_c = deque(nums)


def sum_a():
    """Summation over list using simple summation algorithm"""
    summed = 0
    for i in nums:
        summed += i
    return summed

def sum_b():
    """Summation over list using python's builtin sum function"""
    summed = sum(nums)
    return summed

def queue_a():
    """A dequeue and enqueue operations using simple python list"""
    a = qlist_a.pop(0)
    b = qlist_a.append(99)

def queue_b():
    """A dequeue and enqueue operations using simple linked list"""
    a = qlist_b.dequeue()
    b = qlist_b.enqueue(99)

def queue_c():
    """A dequeue and enqueue operations using deque module"""
    a = qlist_c.popleft()
    b = qlist_c.append(99)

t1 = Timer("sum_a()", "from __main__ import sum_a")
print("simple summation ", t1.timeit(number=1000), "milliseconds")

t2 = Timer("sum_b()", "from __main__ import sum_b")
print("python summation ", t2.timeit(number=1000), "milliseconds")

t3 = Timer("queue_a()", "from __main__ import queue_a")
print("simple list as queue ", t3.timeit(number=1000), "milliseconds")

t4 = Timer("queue_b()", "from __main__ import queue_b")
print("linked list as queue ", t4.timeit(number=1000), "milliseconds")

# Compare the deque dequeue and enqueue (popleft and append)
t5 = Timer("queue_c()", "from __main__ import queue_c")
print("deque as queue ", t5.timeit(number=1000), "milliseconds")