In [ ]:
import random
import numpy as np
from matplotlib import pyplot as plt
It can be hard to guess which code is going to operate faster just by looking at it because the interactions between software and computers can be extremely complex. The best way to optimize code is through using profilers to identify bottlenecks in your code and then attempt to address these problems through optimization. Let's give it a whirl.
Problem 1a
Let's say you have a sorted list of random elements, and you want to see where a new number fits into them to remain ordered. The simplest way to search through an ordered list to find the location for your desired element is to just step through it one-by-one, but this is not algorithmically ideal. Please write out such a function, and comment on the complexity of this algorithm (seen below) in big O notation. Then use timeit to test how fast it is.
In [ ]:
# Create sorted random array and random element of that array; this just sets up the problem.
def rand_arr(n_elements=100000):
random_list = [random.random() for i in np.arange(n_elements)]
random_list.sort()
return random_list
random_list = rand_arr()
new_number = random.random()
In [ ]:
%%timeit
# complete
Problem 1b
We can cut corners all we want to optimize that code, but at the end of the day, it's still going to not be very good. So let's try to make a better algorithm for searching the ordered array to find where to put our new number. One such way is by continually bisecting the array in what is called a binary search, and checking if the special_number is greater than, or less than the value at the bisection, then shifting to the remaining values to continue the search. Please code this up, and comment on its complexity in big O notation, and use timeit to get its speed. Did you get the result you expected to get? If not, why do you think that happened? You may get different results if you change the input parameters. Think about it.
In [ ]:
%%timeit
# complete
Problem 1c
OK, now let's say we have to do a lot of these operations. Like do this binary search on a thousand different random lists. This is what is known as an embarassingly parallel operation, because you're repeating a single function/algorithm on a bunch of independent objects. We can use our good friend, the map function to map a function to a list of objects! Do this with your binary_search function on 100 random lists and time it.
In [ ]:
%%timeit
list_of_list_of_ran = [rand_arr() for i in range(100)]
# complete
Problem 1d
But it gets better! We can actually use multiprocessing.Pool.map() to do the same thing, but this way it uses every processor available to it! Load this up and see what you get, or if you run into any problems.
In [ ]:
%%timeit
# complete
Problem 1e
Did it succeed? What sort of speed bonus did you see? Or if it failed, what do you think you could do in order to make it not fail?
In [ ]: