[SOLVED] Cse2050 homework 03: lists and timing

You will be developing multiple algorithms for one problem:  Given a list of unique integers and a target integer, find all pairs in the list that add up to the target.  For example, given a list of integers [1, 2, 3, 4, 5] and a target integer 5, the function should return
{(1, 4), (2, 3)} (a set of tuples).  NOTE: It does not, and it should not, return the reverse pairs.  It should not return {(1, 4), (2, 3) , (3, 2) , (4, 1)}.

import unittest
from hw3 import find_pairs_naive, find_pairs_optimized

class TestPairFindingAlgorithms(unittest.TestCase):

def test_basic_functionality(self):
“””Using a basic list, test hw3″””
self.assertEqual(find_pairs_naive([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})
self.assertEqual(find_pairs_optimized([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})

def test_with_negative_numbers(self):
“””Using a list with negative numbers”””
self.assertEqual(find_pairs_naive([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})
self.assertEqual(find_pairs_optimized([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})

def test_no_pairs(self):
“””Using a list and target where no two numbers can sum up to the target”””
self.assertEqual(find_pairs_naive([1, 2, 3, 4], 10), set())
self.assertEqual(find_pairs_optimized([1, 2, 3, 4], 10), set())

def test_large_list(self):
“””Using a somewhat large list”””
large_list = list(range(100))
target = 50
expected_pairs = {(10, 40), (11, 39), (1, 49), (2, 48), (18, 32), (17, 33), (8, 42), (24, 26), (9, 41), (15, 35), (0, 50), (16, 34), (19, 31), (6, 44), (22, 28), (7, 43), (23, 27), (14, 36), (5, 45), (13, 37), (20, 30), (21, 29), (12, 38), (3, 47), (4, 46)}
self.assertEqual(find_pairs_naive(large_list, target), expected_pairs)
self.assertEqual(find_pairs_optimized(large_list, target), expected_pairs)

if __name__ == ‘__main__’:
unittest.main()

 

def find_pairs_naive(L, n):
“””Utilizes O(n^2) to find a par of numbers”””
pairs = set()
for i in range(len(L)):
for j in range(i + 1, len(L)):
if L[i] + L[j] == n:
pairs.add((L[i], L[j]))
return pairs

def find_pairs_optimized(L, n):
“””Utilizes Dictionary to find a pair of numbers”””
pairs = set()
seen = {}
for number in L:
complement = n – number
if complement in seen:
pairs.add((min(number, complement), max(number, complement)))
seen[number] = True
return pairs

 

def measure_min_time(func, args, n_trials=10):
“””Takes a function and argument input and
will keep track of the results of all n_trials and
return the minimum amount of execution time as float”””
min_time = float(‘inf’)
for _ in range(n_trials):
start = time.perf_counter()
func(*args)
end = time.perf_counter()
min_time = min(min_time, end – start)
return min_time

 

n           naive       optimized

10             –             –

50             –             –

100            –             –

150            –             –

200            –             –

300            –             –

500            –             –

def compare_algorithms():
“””Compares the naive time and optimized pair finding codes and generates a table which describes the processing
time of each function”””
trials = [1800, 1850, 1950, 2150, 2500]    print(f”ntnaivetoptimized”)
for n in trials:
list_to_test = generate_list(n)
naive_time = measure_min_time(find_pairs_naive, [list_to_test, n], 100)
optimized_time = measure_min_time(find_pairs_optimized, [list_to_test, n], 100)
print(f”{n}t{naive_time:.4f}t{optimized_time:.4f}”)

n naive         optimized

1800 0.0676       0.0001

1850 0.0714       0.0001

1950 0.0793       0.0001

2150 0.0970       0.0001

2500 0.1310       0.0002

 

 

 

def find_pairs_naive(L, n):
“””Utilizes O(n^2) operations to take an input of a list and a number which will determine the pairs in the list
that add up to the number”””
pairs = set() # 1 (Assigns a variable)
for i in range(len(L)): # n (Outer loop runs n times)
for j in range(i + 1, len(L)):  # n (Inner loop runs n times)
if L[i] + L[j] == n:    # 1 (Assigns a variable if true)
pairs.add((L[i], L[j])) # 1 (Performs addition)
return pairs    #1 (Returns a value)
# ————————
# 1 + 2n + 3 = O(n^2)

def find_pairs_optimized(L, n):
“””Utilizes O(n) operations to take an input of a list and a number which will determine the pairs in the list
that add up to the number”””
pairs = set()   # 1 (Assigns a variable)
seen = {}   # 1 (Builds blank dictionary)
for number in L:    # n (Loop iterates n times)
complement = n – number # 1 (Subtraction)
if complement in seen:  # 1 (Dictionary lookup)
pairs.add((min(number, complement), max(number, complement)))   # 1 (Adds pairs)
seen[number] = True # 1 (Dictionary set operation)
return pairs    # 1 (Returns a value)
# ______________________________
# 2 + n + 5 = O(n)

 

n  naive optimized

1800     0.0692      0.0001

1850     0.0724      0.0001

1950     0.0793      0.0001

2150     0.1035      0.0002

2500     0.1327      0.0002

import time
import random
def find_pairs_naive(L, n):
“””Utilizes O(n^2) operations to take an input of a list and a number which will determine the pairs in the list
that add up to the number”””
pairs = set() # 1 (Assigns a variable)
for i in range(len(L)): # n (Outer loop runs n times)
for j in range(i + 1, len(L)):  # n (Inner loop runs n times)
if L[i] + L[j] == n:    # 1 (Assigns a variable if true)
pairs.add((L[i], L[j])) # 1 (Performs addition)
return pairs    #1 (Returns a value)
# ————————
# 1 + 2n + 3 = O(n^2)

def find_pairs_optimized(L, n):
“””Utilizes O(n) operations to take an input of a list and a number which will determine the pairs in the list
that add up to the number”””
pairs = set()   # 1 (Assigns a variable)
seen = {}   # 1 (Builds blank dictionary)
for number in L:    # n (Loop iterates n times)
complement = n – number # 1 (Subtraction)
if complement in seen:  # 1 (Dictionary lookup)
pairs.add((min(number, complement), max(number, complement)))   # 1 (Adds pairs)
seen[number] = True # 1 (Dictionary set operation)
return pairs    # 1 (Returns a value)
# ______________________________
# 2 + n + 5 = O(n)

def measure_min_time(func, args, n_trials=10):
“””Takes a function and argument input and
will keep track of the results of all n_trials and
return the minimum amount of execution time as float”””
min_time = float(‘inf’)
for _ in range(n_trials):
start = time.perf_counter()
func(*args)
end = time.perf_counter()
min_time = min(min_time, end – start)
return min_time

def compare_algorithms():
“””Compares the naive time and optimized pair finding codes and generates a table which describes the processing
time of each function”””
trials = [1800, 1850, 1950, 2150, 2500]
print(f”ntnaivetoptimized”)
for n in trials:
list_to_test = generate_list(n)
target = random.randint(1, n*10)
naive_time = measure_min_time(find_pairs_naive, [list_to_test, target], 100)
optimized_time = measure_min_time(find_pairs_optimized, [list_to_test, target], 100)
print(f”{n}t{naive_time:.4f}t{optimized_time:.4f}”)

def generate_list(n):
“””Generates a list of random, non-repeated numbers”””
return random.sample(range(1, n*10), n)

if __name__ == “__main__”:
compare_algorithms()

 

 

 

import unittest
from hw3 import find_pairs_naive, find_pairs_optimized

class TestPairFindingAlgorithms(unittest.TestCase):

def test_basic_functionality(self):
“””Using a basic list, test hw3″””
self.assertEqual(find_pairs_naive([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})
self.assertEqual(find_pairs_optimized([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})

def test_with_negative_numbers(self):
“””Using a list with negative numbers”””
self.assertEqual(find_pairs_naive([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})
self.assertEqual(find_pairs_optimized([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})

def test_no_pairs(self):
“””Using a list and target where no two numbers can sum up to the target”””
self.assertEqual(find_pairs_naive([1, 2, 3, 4], 10), set())
self.assertEqual(find_pairs_optimized([1, 2, 3, 4], 10), set())

def test_large_list(self):
“””Using a somewhat large list”””
large_list = list(range(100))
target = 50
expected_pairs = {(10, 40), (11, 39), (1, 49), (2, 48), (18, 32), (17, 33), (8, 42), (24, 26), (9, 41), (15, 35), (0, 50), (16, 34), (19, 31), (6, 44), (22, 28), (7, 43), (23, 27), (14, 36), (5, 45), (13, 37), (20, 30), (21, 29), (12, 38), (3, 47), (4, 46)}
self.assertEqual(find_pairs_naive(large_list, target), expected_pairs)
self.assertEqual(find_pairs_optimized(large_list, target), expected_pairs)

if __name__ == ‘__main__’:
unittest.main()