More Python Exercises - Sample solutions _ Supplemental Notebooks_

Fast searching in ordered collections. This problem consists of just a single exercise, worth ten (10) points. It is about an elementary principle of computer science algorithm design, which is that one can often do things faster if one exploits structure in the input data. Suppose you are given a list of already sorted numbers. In [ ]: Suppose you now want to know whether a certain value exists in this list. A simple way to do that in Python is as follows. In [ ]: This method works fine and is reasonably fast on small lists. However, if the list is very large, this method can be wasteful, computationally speaking. That's because it does not take advantage of the fact that A is already ordered. In such a case, it should be easier to determine whether the element exists. (How?) Exercise 0 (3 + 7 == 10 points). Write a function, ordered_contains(S, x), that takes an already sorted list, S, as input, and determines whether it contains x. But there is one more condition: your method must be at least ten times faster than contains() for "large" lists! In particular, there are two test codes for this exercise. The first one checks that your procedure does, indeed, return the correct result by comparing its output to contains(), which we will assume is correct. Correctness is worth three (3) points of partial credit out of ten (10). The second test cell checks whether your implementation is faster than contains() for a relatively large, but ordered, list. If your implementation is slower for smaller lists, that is okay! Hint. If you can find a standard Python library routine to help you, by all means, use it! In [ ]: def ordered_contains(S, x): # You may assume that `S` is sorted ### BEGIN SOLUTION return ordered_contains 2(S, x) # Version 0: Use Python's built-in `bisect()` routine def ordered_contains 0(S, x): from bisect import bisect i = bisect(S, x) return i 0 and S[i-1] == x def contains(A, x): """Returns True only if the value `x` exists in `A`.""" return x in A print("A contains 32: {}".format(contains(A, 32))) print("A contains 7: {}".format(contains(A, 7))) print("A contains -10: {}".format(contains(A, -10))) A = [2, 16, 26, 32, 52, 71, 80, 88] # These are already sorted: assert A == sorted(A) 8/19/2020 More Python Exercises - Sample solutions | Supplemental Notebooks: More Python Exercises | CSE6040x Courseware | edX # Version 1: A manual implementation of binary search. ## This is the algorithm that this exercise is intended to # "introduce." # ## However, for a variety of implementation reasons, this # implementation is unlikely to beat Version 0, above. # Any ideas why not? # THRESHOLD 1 = 128 # An "engineering" constant - use to tune speed def ordered_contains 1(S, x): if len(S) = THRESHOLD 1: return contains(S, x) midpoint = int(len(S) / 2) if x S[midpoint]: return ordered_contains 1(S[:midpoint], x) if x S[midpoint]: return ordered_contains 1(S[midpoint+1:], x) return True # Found it! # The following method improves on the above. Why is it faster? THRESHOLD 2 = 8 # An "engineering" constant - use to tune speed def ordered_contains 2(S, x, l=0, r=None): if r is None: r = len(S) if (r-l) = THRESHOLD 2: return contains(S[l:r], x) midpoint = int((l+r) / 2) if x S[midpoint]: return ordered_contains 2(S, x, l, midpoint) if x S[midpoint]: return ordered_contains 2(S, x, midpoint+1, r) return True # Found it! ### END SOLUTION print("A contains 32: {}".format(ordered_contains(A, 32))) print("A contains 7: {}".format(ordered_contains(A, 7))) print("A contains -10: {}".format(ordered_contains(A, -10))) print("n(Did those results match the earlier example?)") In [ ]: In [ ]: # Test cell: `test_is_faster` (7 points) # Test cell: `test_is_correct` (1 point) from random import randint, sample def gen_list(n, v_max, v_min=0): return sample(range(v_min, v_max), n) def gen_sorted_list(n, v_max, v_min=0): return sorted(gen_list(n, v_max, v_min)) def check_case(S, x): msg = "`contains(S, {}) == {}` while `ordered_contains(S, {}) == {}`!" true_solution = contains(S, x) your_solution = ordered_contains(S, x) assert your_solution == true_solution, t(true_solution, your_solution) S = gen_sorted_list(13, 100) print("Checking your code on this input: S = {}".format(S)) check_case(S, S[0]) check_case(S, S[0]-1) check_case(S, S[-1]) check_case(S, S[-1]+1) for x in gen_list(50, 100, -100): check_case(S, x) print("n(Passed basic correctness checks.)") print("nTiming `contains()`...") x = randint(-100, 100) %timeit contains(S, x) print("nTiming `ordered_contains()`...") %timeit ordered_contains(S, x) print("n(This problem is small, so it's okay if your method is slower.)") print("n(Passed!)")