Question

Problem 5: 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:
   • If i is greater than the current length of the output list, insert x into the output list at the appropriate position.
   • Otherwise, do as follows:
     • Find out how many list elements should fall between the current end of the output list and the place x should go. Take only those elements from the original list l, 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 l 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 l 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(l, insertions):

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

    # YOUR CODE HERE

Correctness

First, let's check that you compute the right thing.

import string

l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

insertions = [(0, 'a'), (2, 'b'), (2, 'b'), (7, 'c')]

r1 = do_insertions_simple(l, insertions)

r2 = do_insertions_fast(l, insertions)

print("r1:", r1)

print("r2:", r2)

assert_equal(r1, r2)

is_correct = False

for _ in range(20):

    l, insertions = generate_testing_case(list_len=100, num_insertions=20)

    r1 = do_insertions_simple(l, insertions)

    r2 = do_insertions_fast(l, insertions)

    assert_equal(r1, r2)

    is_correct = True

Answer 1

Program

def do_insertions_fast(l, insertions):
"""Implement here a faster version of do_insertions_simple """
new = []
count = 0

for i, x in insertions:
space = i - len(new)
if i <= len(new):
new.insert(i, x)
else:
new += l[count:count+space]
count += space
new.append(x)
  
new += l[count:]

return new

import string
l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
insertions = [(0, 'a'), (2, 'b'), (2, 'b'),(7, 'c')]
r1 = do_insertions_simple(l, insertions)
r2 = do_insertions_fast(l, insertions)
print("r1:", r1)
print("r2:", r2)
assert_equal(r1, r2)

is_correct = False
for _ in range(20):
l, insertions = generate_testing_case(list_len=100, num_insertions=20)
r1 = do_insertions_simple(l, insertions)
r2 = do_insertions_fast(l, insertions)
assert_equal(r1, r2)
is_correct = True

output

r1: ['a', 0, 'b', 'b', 1, 2, 3, 'c', 4, 5, 6, 7, 8, 9] r2: ['a', 0, 'b', 'b', 1, 2, 3, 'c', 4, 5, 6, 7, 8, 9]

Hope this helps!

Please let me know if any changes needed.

Thank you!

I hope you're safe during the pandemic