Need some help with Python Problem(Convert/rewrite a function to a faster implementation)

Starting Codes:

def do_insertions_fast(l, insertions):

"""Implement here a faster version of do_insertions_simple """

# YOUR CODE HERE

raise NotImplementedError()

Checking Coes: (in addition, the codes need to have faster implementation)

l, insertions = generate_testing_case()

simple_time = timeit(do_insertions_simple, l, insertions)

fast_time = timeit(do_insertions_fast, l, insertions)

speedup = simple_time / fast_time

print("Speedup:", speedup)

points = int(np.log2(speedup))

print("You got", points, "points")

- Inserting elements into a list, slowly The following function do_insertions_simple takes as input a list 1, and a list of insertions insertions. The latter is a list of elements of the form (i, x) specifying that x should be inserted at position i in the list. The list insertions is sorted according to i (the problem would be markedly more difficult if this were not true, but you can consider on your own how to solve it in that case). The function do_insertions_simple performs all insertions, and returns the result, without modifying the original list 1. [] def do_insertions_simple(1, insertions): ""Performs the insertions specified into 1. @param 1: list in which to do the insertions. Is is not modified. @param insertions: list of pairs (i, x), indicating that x should be inserted at position i. r = list(1) for i, x in insertions: r.insert(i, x) return r How long does do_insertions_simple take to execute? We can time it using the Python time module, and using Numpy to generate a large test case: import time def timeit(f, 1, insertions): te = time.time () f(1, insertions) return time.time() - te [] import numpy as np import random def generate_testing_case(list_len=1000000, num_insertions=10000): 1 = list(np.random.random(list_len)) insertions = [] for j in range (num_insertions): i = random.randint (0, list_len + j) x = random.random() insertions.append ( (i, x)) insertions.sort() return 1, insertions Your task: writing a faster implementation For this homework assignment, you will write a faster implementation of do_insertions_simple (which we will call do_insertions_fast). We won't need anything extra (no special modules, no advanced algorithms, no Numpy) in order to obtain a considerable speedup. Let's think about what makes do_insertions_simple slow, and about how we can rewrite the whole thing in a faster way. The biggest problem with do_insertions_simple is that it calls insert once for every element of the insertions list -- or 10,000 times, in our test case above. Insertion into a list is expensive, because it requires all the elements after the insertion point to be rearranged. So, insertions early in the list are especially expensive. Appending to the end of a list, on the other hand, is very cheap, because nothing has to be rearranged. So, how can we make it that we use insert as little as possible, and instead use append whenever possible? Here's one strategy for implementing do_insertions_fast: 1. Create a new, empty list. We will use this list to build up the output. 2. For each pair (i, x) in insertions, do the following: o If i is greater than the current length of the output list, insert x into the output list at the appropriate position. o Otherwise, do as follows: Find out how many list elements should fall between the current end of the output list and the place should go. Take only those elements from the original list 1, and concatenate them to the output list. Then append x to the end of the output list. 3. Finally, after all insertions are done, concatenate any remaining elements of 1 onto the output list. 4. Return the output list. In the below cell, write your implementation of do_insertions_fast. You are not required to use the strategy outlined above, but it's a pretty good one, and I recommend it: using it, you should end up with something at least 100 times faster than do_insertions_simple! Finally, here's one more hint if you decide to use the above strategy: keep track of the number of elements in 1 that have gone into the output list as you go along. This number will be useful in implementing the above strategy. [ ] def do_insertions_fast(1, insertions): """Implement here a faster version of do_insertions_simple """ # YOUR CODE HERE raise NotImplementedError ()