Exercises

The following exercises provide you with the opportunity to practice with benchmarking Python code. The solutions to these exercises are found in the section .

Following are two different Python functions that accept an unsorted array of integers and return the smallest number from the array. Here’s the first version:

	def minimum(array):
	smallest_item_so_far = float('inf')

	for item in array:
	if item < smallest_item_so_far:
	smallest_item_so_far = item

	return smallest_item_so_far

This first version performs a linear search on the array while keeping track of the smallest number throughout the search.

Here’s the second version:

	def minimum(array):
	array.sort()
	return array[0]

This second version accomplishes the same task of returning the smallest number using another approach. It first sorts the array by ascending order and then returns whichever item is at the beginning of the array. Naturally, this item will be the smallest value.

Hypothesize which version you think will run faster. Then, write and run benchmarking code to confirm whether your hypothesis is correct.

Following are two functions that both sum up all integers from 1 up until (but not including) 1_000_000.

The first version uses a for..range loop:
def sum_up_to_one_million():
sum = 0

for i in range(1_000_000):
sum += i

return sum

The second version uses a while loop:
def sum_up_to_one_million():
sum = 0
i = 1

while i < 1_000_000:
sum += i
i += 1

return sum

Hypothesize which function you think will run faster. Then, write and run benchmarking code to confirm your hypothesis.

Following is code that benchmarks an awesome new sorting algorithm that I’ve just invented. I call it awesome_sort, and it’s too awesome for me to even show you how it works. However, I will show you my benchmarking code that I’m using to test it.

But there’s a problem, as my benchmarking code is not set up correctly. Can you spot the mistake?

	import timeit
	import awesome_sort

	setup_code = '''
	array = []
	for i in range(100_000):
	array.append(i)
	'''

	test_code = '''
	awesome_sort.sort(array)
	'''

	print(timeit.repeat(stmt=test_code, setup=setup_code, repeat=5, number=1))

I’ve always wanted to use benchmarking to discover the actual-time performance difference between linear search and binary search. However, this time I’ve made two mistakes in my benchmarking code. Can you find them?

Here’s my code for benchmarking linear search:

	import timeit

	setup_code = '''
	def linear_search(array, search_value):
	for index, element in enumerate(array):

	if element == search_value:
	return index
	elif element > search_value:
	break

	return None

	array = []
	for i in range(100_000):
	array.append(i)
	'''

	test_code = '''
	print(linear_search(array, 89124))
	'''

	print(timeit.repeat(stmt=test_code, setup=setup_code, repeat=5, number=1))

And here’s my code for benchmarking binary search:

	import timeit

	setup_code = '''
	def binary_search(array, search_value):
	lower_bound = 0
	upper_bound = len(array) - 1

	while lower_bound <= upper_bound:

	midpoint = (upper_bound + lower_bound) // 2
	value_at_midpoint = array[midpoint]

	if search_value == value_at_midpoint:
	return midpoint
	elif search_value < value_at_midpoint:
	upper_bound = midpoint - 1
	elif search_value > value_at_midpoint:
	lower_bound = midpoint + 1

	return None

	array = []
	for i in range(1_000_000):
	array.append(i)
	'''

	test_code = '''
	binary_search(array, 89124)
	'''

	print(timeit.repeat(stmt=test_code, setup=setup_code, repeat=5, number=1))

	def sum_up_to_one_million():
	sum = 0

	for i in range(1_000_000):
	sum += i

	return sum

	def sum_up_to_one_million():
	sum = 0
	i = 1

	while i < 1_000_000:
	sum += i
	i += 1

	return sum