Issue 12: Memoies

Don't cry because it's over, smile because it happened.
- Dr. Seuss  


After 12 weeks, CSC148H1 for winter 2014 is coming to a conclusion. Ultimately, this means that this will be the last post I make in this SLOG. It is fitting that for this last post I will be talking about Memo(r)ies - Memoization.

Memoization is the process of keeping track of already computed values, if you know that your algorithm will end up using the same value multiple times. A good example of this is the recursive function to find the fibonacci sequence. 

def fib(n):
    """Return the nth fibonacci number"""
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

A function such as the above will call fib multiple times on the same numbers. For example, calling fib(4) will require calling fib(3) and fib(2), which will then call fib(2) again and fib(1). As n increases, fib(n - 1) and fib(n - 2) is called more and more frequently. 

So we use memoization:

def fib(n:int):
    """Return the nth fibonacci number"""
    computed = {} # already-computed values of fib
    def fibmem(k:int):
        if k in computed: # this and next op are O(1)
            return computed[k]
        elif k < 2:
            computed[k] = k
        else:
            computed[k] = fibmem(k - 1) + fibmem(k - 2)

        return computed[k]
    return fibmem(n)

Memoization in python can be achieved via nested functions, by defining a dictionary of computed values, and then loading from the dictionary within the nested function.

I inadvertently discovered this ability when computing M(n) for assignment I, in order to determine the optimal i value for n number of cheese. However, my approach required the use of the keyword "nonlocal". This keyword is used to specify that a variable should be usable outside of the local function I(n), but not necessarily globally. This was weird however, considering that the fib(n) function shown about did not require this keyword. I looked further into it and discovered that it depended entirely on whether there existed an assignment statement such as x = x ... where x was the non local variable. In other words, you require a special declaration to alter the existing variable based on itself.

# This is okay
def f(x):
    y = 1
    def g(x):
        return x - y
    
    return g(x)

# This is not okay
def f(x):
    y = 1
    def g(x):
        y = y * 1
        return x - y
    
    return g(x)

And this is interesting because it is easy to add new memories, but that doesn't mean you have to alter the existing ones. Thank you for the great year!

Issue 11: O(sort(log n))

One finds limits by pushing them.
- Herbert Simon  




The discipline of Computer Science is more than simply programming. We also aim to ensure that our programs are quick and efficient. This is where the theoretical workers of Computer Science came in and determined a simple method to classify the speed of algorithms: Big-O. 

Source: http://bigocheatsheet.com/

Big-O allows us to classify algorithms according to how the algorithm's computation time grow based on the size of the input (n). The fastest possible growth rate of an algorithm is constant, (i.e. it does not grow at all) and is represented by O(1). While somewhat slower algorithms can take n^2 time, growing twice as fast as the input. The slowest algorithms can be O(2^n), O(n!), or O(n^n), taking exponentially longer every time the input size grow.

But what is the big deal about quick and efficient algorithms? "Taking exponentially longer" might not sound too exciting in words, but what if we put it into numbers?

Input(n)	O(1)	O(log(n))	O(n)	O(n^2)	O(2^n)	O(n!)
2	1	1	2	4	4	2
4	1	2	4	16	16	24
8	1	3	8	64	256	40320
16	1	4	16	256	65536	20922789888000
32	1	5	32	1024	4294967296	???
64	1	6	64	4096	18446744073709551616 more than the age of the universe in seconds	???
128	1	7	128	16384	10^38	???
256	1	8	256	65536	10^77	???
512	1	9	512	262144	10^154 There are only 10^80 atoms in the observable universe.	???

As you can see, for a input size as small as 512 item, an algorithm with big-O time complexity of O(2^n) is highly impractical. If you are wondering why I didn't calculate for O(n!), it is because there are 1167 digits in 512 factorial. 

We can easily see that it is important for us to write quick and efficient algorithms if we want to get any work done before the universe ends. But one might ask, why do we use big-O when we can simply time our code? The problem with that is timing our code does not always give us the information we need due to various factors. Big-O is used an upper bound measurement. That means that an algorithm that grows at O(n) grows at most linearly. However, Big-O is not intended to estimate exactly how fast an algorithm is, only how fast it grows. Timing our algorithm on a computer subjects it to factors such as hardware restrictions, background processes, and various other problems, and will not allow us to properly measure an algorithm's growth rate. The best way to ensure that our measurement is correct is by analyzing it line by line.

We have seen an example already where we can measure the Big-O Time complexity - sorting algorithms. Sorting is a process that you may say "is easier said than done". Coming up with an efficient sorting algorithm is not trivial, and there are countless algorithms out there with Big-O Time complexity ranging from O(n^2) to O(n log (n)). Some may even argue that there are algorithms that can sort in O(n). However, this year we are only looking at some of the more commonly known algorithms: Merge Sort, Quicksort, Selection Sort, Insertion Sort, and Bubble Sort.

Here are the algorithms:

############ Selection sort ############

def find_min(L, i):
    """Return the index of the smallest item in L[i:]."""

    smallest = i
    for j in range(i + 1, len(L)):
        if L[j] < L[smallest]:
            smallest = j
    return smallest


def selection_sort(L):
    """Sort the items in L in non-decreasing order."""

    i = 0
    while i != len(L) - 1:

        # Find the smallest remaining item and move it to index i.
        smallest = find_min(L, i)
        L[smallest], L[i] = L[i], L[smallest]
        i += 1


############ Insertion sort 1 ############

def insert(L, i):
    """Move L[i] to where it belongs in L[:i]"""

    v = L[i]
    while i > 0 and L[i - 1] > v:
        L[i] = L[i - 1]
        i -= 1
    L[i] = v

def insertion_sort_1(L):
    """Sort the items in L in non-decreasing order."""

    i = 1

    # Insert each item i where it belongs in L[0:i + 1]
    while i != len(L):
        insert(L, i)
        i += 1


############ Bubblesort 1 ############

def bubblesort_1(L):
    """Sort the items in L in non-decreasing order."""

    j = len(L) - 1
    while j != 0:

        # Swap every item that is out of order.
        for i in range(j):
            if L[i] > L[i + 1]:
                L[i], L[i + 1] = L[i + 1], L[i]
        j -= 1


############ Mergesort 1 ############

def _merge_1(left, right):
    """Merge sorted lists left and right into a new list and return that new
    list."""

    result = []

    i ,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result += left[i:]
    result += right[j:]
    return result

def _mergesort_1(L):
    """Return a new list that is a sorted version of list L."""

    if len(L) < 2:
        return L[:]
    else:
        middle = len(L) // 2
        left = _mergesort_1(L[:middle])
        right = _mergesort_1(L[middle:])
    return _merge_1(left, right)

def mergesort_1(L):
    """Sort list L in non-decreasing order."""

    L[:] = _mergesort_1(L)


############ Quicksort 1 ############

def _partition_1(L):
    """Rearrange L so that items < L[0] are at the beginning and items >= L[0]
    are at the end, and return the new index for L[0]."""

    v = L[0]
    i = 1
    j = len(L) - 1
    while i <= j:
        if L[i] < v:
            i += 1
        else:
            L[i], L[j] = L[j], L[i]
            j -= 1

    L[0], L[j] = L[j], L[0]
    return j

def _quicksort_1(L):
    """Sort L by partitioning it around the first item, then recursing."""

    if len(L) <= 1:
        return L
    else:
        pivot = _partition_1(L)
        left = L[:pivot]
        right = L[pivot + 1:]
        return _quicksort_1(left) + [L[pivot]] + _quicksort_1(right)

def quicksort_1(L):
    """Sort list L in non-decreasing order."""

    L[:] = _quicksort_1(L)

As we can, Selection Sort, Insertion Sort, and Bubble Sort all require at least 2 nested loops. Since both loops involve n as a condition, this makes the Big-O time complexity of all these algorithms O(n^2).  On the other hand, Merge Sort and Quick Sort uses a "divide and conqueror" strategy by splitting up the list into multiple sublists, and sorting the sublist. This means that instead of requiring O(n^2), it has O(n log (n)). This makes Merge Sort and Quick Sort much superior algorithms, and a quick test by timing our algorithm can confirm that.

bubblesort_1 1000 items in 0.748769
selection_sort 1000 items in 0.475687
insertion_sort_1 1000 items in 0.429609
mergesort_1 1000 items in 0.030901
quicksort_1 1000 items in 0.029133

However, we can observe that even though Selection Sort, Bubble Sort, and Insertion Sort are in O(n^2), they do not take the same amount of time to compute. The same goes for Merge Sort and Quicksort. Once again, this is because Big-O does not measure exactly how fast the algorithm performs. It simply gives an upper bound representing how the algorithm will grow. 

Depending on the implementation of the algorithm, even the same algorithm can have different run time. We can push the limit of an algorithm by reducing the number of calls it needs to do, and using optimized versions of various functions (e.g. min(), max()) whenever possible. However, this will never be able to change it's time complexity. Think of it as changing the starting position, but not the slope. Even a very well implemented Bubble sort will eventually lose to a poorly implemented merge sort!

Issue 10: The Case of the Quadratic Merge Sort

Anyone who has never made a mistake has never tried anything new.
- Albert Einstein  

This week, we were introduced to two efficient sorting algorithm: Quick sort and Merge sort. Both algorithm applies the idea of "divide and conqueror" by splitting a list in half and sorting them recursively. This means that we should expect both algorithm to have an average run time of O(n log n).

However, an interesting issue came up when this code from the 9 AM lecture was ran:

from random import shuffle, randint


def quick(L: list) -> list:
    """Produce a sorted version of L

    >>> quick([2, 1, 3])
    [1, 2, 3]
    """
    if len(L) < 2:
        return L[:]
    else:
        i = randint(0, len(L) - 1)
        return (quick([x for x in L if x < L[i]]) +
                [L[i]] +
                quick([x for x in (L[0:i] + L[i+1:]) if x >= L[i]]))


def merge(L1, L2):
    """return merge of L1 and L2

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([1, 2, 3], [0, 4, 5])
    [0, 1, 2, 3, 4, 5]
    >>> merge([0], [1, 2, 3, 4])
    [0, 1, 2, 3, 4]
    """
    L = []
    i1, i2 = 0, 0
    while L1[i1:] and L2[i2:]:
        if L1[i1] < L2[i2]:
            L.append(L1[i1])
            i1 += 1
        else:
            L.append(L2[i2])
            i2 += 1
    return L + L1[i1:] + L2[i2:]

def merge_sort(L):
    """Produce copy of L in non-decreasing order

    >>> merge_sort([1, 5, 3, 4, 2])
    [1, 2, 3, 4, 5]
    >>> L = list(range(20))
    >>> shuffle(L)
    >>> merge_sort(L) == list(range(20))
    True
    """
    if len(L) < 2 :
        return L[:]
    else :
        return merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))


if __name__== '__main__':
    import doctest
    doctest.testmod()
    from time import time, clock
    L = list(range(1000))
    shuffle(L)
    start = time()
    quick(L)
    print("quick sort: {} for {} items".format(time() - start, len(L)))
    start = time()
    merge_sort(L)
    print("merge sort: {} for {} items".format(time() - start, len(L)))

Logically, both algorithm should take roughly the same time. Yet, as we increased the size of the list, this happened:

quick sort: 0.0055048465728759766 for 1000 items
merge sort: 0.013010978698730469 for 1000 items
quick sort: 0.06204104423522949 for 10000 items
merge sort: 0.44429707527160645 for 10000 items
quick sort: 0.7655110359191895 for 100000 items
merge sort: 47.87060809135437 for 100000 items

This goes against what we expect entirely. Why did this happen? As it turns out, the problem exists on the line while L1[i1:] and L2[i2:]: within the function merge(L1, L2). 

Splicing a list in python does not have complexity O(1) as we'd expect (i.e. constant time). Some research reveals that splicing actually have complexity O(k). The k in this case is not a constant - it is some variable unrelated to n. This means that splicing grows linearly, but does not necessarily grow according to the size of the list.

We can verify this with a quick function:

from random import shuffle, randint
from time import time, clock

def splice(L: list) -> []:    
    return L[:]

if __name__== '__main__':
    import doctest
    doctest.testmod()
    L = list(range(100000))
    start = time()
    splice(L)
    print("splicing takes {} for {} items".format(time() - start, len(L)))    

Notice has as the size of a list increase, the time it takes to splice a list also increase:

splicing takes 0.0010027885437011719 for 100000 items
splicing takes 0.010010957717895508 for 1000000 items
splicing takes 0.08705687522888184 for 10000000 items

Since comparisons do indeed take linear time, changing the while condition to a comparison managed to resolve this issue.

def merge(L1, L2):
    """return merge of L1 and L2

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([1, 2, 3], [0, 4, 5])
    [0, 1, 2, 3, 4, 5]
    >>> merge([0], [1, 2, 3, 4])
    [0, 1, 2, 3, 4]
    """
    L = []
    i1, i2 = 0, 0
    while i1 < len(L1) and i2 < len(L2):
        if L1[i1] < L2[i2]:
            L.append(L1[i1])
            i1 += 1
        else:
            L.append(L2[i2])
            i2 += 1
    return L + L1[i1:] + L2[i2:]

quick sort: 10.197987079620361 for 1000000 items
merge sort: 16.52327299118042 for 1000000 items

Now Merge sort and Quick sort grows according to the complexity O(n log n) as expected. However, this leaves one more question unanswered. If both Quick sort and Merge sort has time complexity O(n log n), why is Quick sort performing better for a randomized list? Unfortunately, I don't have the answer this week. Maybe more research will yield the answer next week!

Issue 9: Using Iteration on a Recursive Problem

I didn't fail the test, I just found 100 ways to do it wrong.
- Benjamin Franklin  

During our Lab #8, we had a rather unique challenge: create the recursive count_less(item) method without using recursion. This came as a surprise, as just a week earlier, I was working on an iterative version of the function nested_depth(L). I will present it here:

def nested_depth(L: list) -> int:
    '''Return the maximum depth of nested lists L. Does not work on infinitely
    nested list.
    
    >>> nested_depth(1)
    0
    >>> nested_depth([1])
    1
    >>> nested_depth([1, 2])
    1
    >>> nested_depth([[1, 2], 3])
    2
    >>> nested_depth([[1, 2], [[3]]])
    3
    >>> nested_depth([[[[1]], [2]], [2]])
    4
    >>> nested_depth([[1], 2, [3, 4, [5, 6, [7, 8, [9, 10]]]]])
    5
    >>> nested_depth([0, [1, [2, [0]], [3, [4, [[5]]]], 5], 6, 7])
    6
    >>> nested_depth([[3, 6, [2, [3, [[9, [1, 0, 7], 6], 8, 1], 9], 7]], 9, 4])
    7
    >>> nested_depth([0, [[1], [2, [0]], [3, [4, [[[[5]]]]]], 6], [7], [[8]]])
    8
    >>> nested_depth([1, 1, 1, 1, 1, [1], [1], [1], [1], [[1]]])
    3
    >>> nested_depth([1, 1, 1, 1, 1, [[1]], [[1]], [[1]], [[1]], 1])
    3
    '''
    # All non-lists have depth of 0
    if isinstance(L, list):
        # We keep track of two things: A dictionary to record the maximum
        # depth we reached; and a copy of the current list where we iteratively
        # append inner nested lists (as opposed to recursively.)
        max_depths = {}
        todo = L[:]
        
        for item in todo:
            if isinstance(item, list):
                # All the inner lists are appended to the end of todo
                for inner in item:
                    todo.append(inner)
                    
                    # The depth that we have currently reached is equivalent
                    # to the depth of the last item + 1
                    try:
                        max_depths[id(inner)] = max_depths[id(item)] + 1
                    except KeyError:
                        # If there was no last item, then we have just started
                        # at depth 2
                        max_depths[id(inner)] = 2

        # Since we record max_depths starting at depth 2 (a loop inside a list)
        # if the dictionary is empty then the depth is only 1
        return max(max_depths.values()) if len(max_depths) > 0 else 1
    else:
        return 0

As a reminder, the original nested_depth(L) function given in class was a 1 line function that returned the maximum depth of nested lists L. It is as follow:

def nested_depth (L):
 return (1 + max ([nested_depth (x) for x in L] + [0]) 
   if isinstance (L, list) else 0)

The idea behind my algorithm is to iterate through a list "todo" which begins as a copy of "L". However, every time a list nested inside "L" is reached, its content is appended to "todo" so that it will be analyzed later on in the iteration.

In the meantime, a dictionary "max_depths​" is used to keep track of the deepest list that we have discovered through the above process. In this dictionary, the key is the id of an object, and the value is the depth of that object. Every time a list's content is appended via the above process, each item is put into the max_depths​ dictionary with their id as the key. The value of of each item is determined by taking the value of the shallower list stored in the dictionary (i. e. the value in the dictionary of the list this item belongs to), and adding 1 to it. If a KeyError is returned, then it means there are no other lists that this item belongs to, meaning this is the first nested list with a depth of 2. The maximum nested depth can be determined simply by finding the maximum value in the dictionary "max_depths". If "max_depths" is empty, then there are no nested lists, so the nested depth is 1.

This algorithm works because it takes the idea of recursion, and convert it to iteration. Appending nested list to the end of "todo" while iterating through it is similar to recursion. The returned value of each would-be recursive call is stored in the format of a dictionary, as opposed to being returned.

While this shows that a recursive function can indeed be done with iteration, it is nonetheless very long and cumbersome. Similarly, a few years ago I ended up developing an iterative (although not in-place) version of Merge Sort as I did not have the knowledge of recursion back then. It took me several days of drafting, but our professor was able to complete it with 1 line and 1 helper function. In the end, the moral of recursion isn't that we must use it. Rather, it is simply much easier to use in many cases.

Issue 8: More Complicated Recursion

Failure is the key to success; each mistake teaches us something.
- Morihei Ueshiba  


Last week, I discusssed a simple recursive function that returns a boolean value. However, in many cases that is insufficient. Luckily, it is just as easy to return non-boolean values in recursion.

Let us consider a standard Tree ADT.  

class Tree:
    
    def __init__(self: "Tree", value: str=None, children: list=None):
        self.value = value
        if not children:
            self.children = []
        else:
            self.children = children[:]

We are given a few Trees and we need to find whether a letter exists in value of the Tree and its children, and if so, how many. We'll try to find how many times the letter a exists in the following tree as our example:

    tn2 = Tree("one", [Tree("two"), Tree("three"), Tree("apple"), Tree("five")])

    tn3 = Tree("answer", [Tree("six"), Tree("seven")])

    tn1 = Tree("eight", [tn2, tn3])

Similar to last time, we first consider the simplest case. A single Tree with no children.

def count(t: "Tree", x: str) -> int:
    """Return number of values in t and its children that contains x.
    
     >>> tn2 = Tree("one", [Tree("two"), Tree("three"),\
    Tree("apple"), Tree("five")])
    >>> tn3 = Tree("answer", [Tree("six"), Tree("seven")])
    >>> tn1 = Tree("eight", [tn2, tn3])
    >>> count_tree(tn1, "a")
    2
    >>> count_tree(tn2, "a")
    1
    """
    return t.value.count(x)

We simply count the number of letters, easy enough. Now, what if the Tree have children? Then we can call this recursively, as we've already defined the simplest case. 

def count(t: "Tree", x: str) -> int:
    """Return number of values in t and its children that contains x.
    
    >>> tn2 = Tree("one", [Tree("two"), Tree("three"),\
    Tree("apple"), Tree("five")])
    >>> tn3 = Tree("answer", [Tree("six"), Tree("seven")])
    >>> tn1 = Tree("eight", [tn2, tn3])
    >>> count_tree(tn1, "a")
    2
    >>> count_tree(tn2, "a")
    1
    """
    if not t.children is None:
        for child in t.children:
            return count_tree(child, x)
        
    return t.value.count(x)

However, running it like this won't do us any good. We don't want to simply return how many items exist in a particular Tree, we want to return how many items exists in all the trees in total. This should be a good hint as to what we need to do! (hint: add)

def count_tree(t: "Tree", x: str) -> int:
    """Return number of values in t and its children that contains x.
    
    >>> tn2 = Tree("one", [Tree("two"), Tree("three"),\
    Tree("apple"), Tree("five")])
    >>> tn3 = Tree("answer", [Tree("six"), Tree("seven")])
    >>> tn1 = Tree("eight", [tn2, tn3])
    >>> count_tree(tn1, "a")
    2
    >>> count_tree(tn2, "a")
    1
    """
    total = 0
    
    if not t.children is None:
        for child in t.children:
            total = total + count_tree(child, x)
        
    return total + t.value.count(x)

What makes this algorithm works is that if a Tree has no children, then total is 0, and the for loop is not run; so it is equivalent to the very simple case. However, if a Tree has children, then it will run equivalent to the very simple case for every single child, and sum it up in our accumulator variable called total. As a result, even though every "branch" of the Tree returns a different value, we are still able to return the final sum when we call the function.

As a bonus, here is my alternative algorithm that works. 

def count_tree(t: "Tree", x: str):
    """Return number of values in t that begin with 'a'.
    
    >>> tn2 = Tree("one", [Tree("two"), Tree("three"),\
    Tree("apple"), Tree("five")])
    >>> tn3 = Tree("answer", [Tree("six"), Tree("seven")])
    >>> tn1 = Tree("eight", [tn2, tn3])
    >>> count_tree(tn1, "a")
    2
    >>> count_tree(tn2, "a")
    1
    """
    initial_list = [t.value] + t.children 
    
    total_list = [count_tree(t, x) if isinstance(t, Tree) 
              else t.count(x) for t in initial_list]
    
    return sum(total_list)

It ended up confusing several people during their first glance. However, if we break it down, we can see that the value and children are added together into a single list. Using the list comprehension syntax, we ask Python to treat every item in the list differently, depending on whether it is a Tree or a value. If it was a value, then we simply returned the number of time x exists value using t.count(x). This is our simplest case. If it was a Tree, then we recursively called count_tree(t, x) on that Tree. Our recursive function will then find the number of times x exists in that Tree, and return it as an integer. Eventually, total_list will be populated by integers, each representing the number of time x exists in value for a particular Tree or value, which we sum up to find to total number of time.

So in conclusion, even complicated Recursive functions can be made based on the rule of starting with the simplest case, and then adding up from there.

Issue 7: Recursion

In order to understand recursion, one must first understand recursion.
- Anonymous  


Recursion is a notorious source of confusion for many people going into Computer Science. The problem with recursion is that recursion is not intuitive. In recursion a function calls itself to get a value, while in the middle of writing the function. This presents the question of: "How can we write our function in a way to use a value, before we even know what the value is going to be?"

Recursion is used to solve a big problem by solving a series of smaller problems. Divide and conquer if you will. Thus, I found that the best way to approach a recursive problem is to first analyze the simplest scenario, and then work my way up.

Let's take the ADT "SearchList" as an example. A SearchList is a python list with 3 elements.
element 0 is an integer.
element 1 is either None or a SearchList that contains integers smaller than element 0
element 2 is either None or a SearchList that contains integers larger than element 0
We want to create a function that returns whether or not an integer n exist somewhere in the SearchList.

We want to begin by writing out some examples, starting from the simplest case, and going into more complicated cases

def find_num(SL: 'SearchList', n: int) -> bool:
    """
    Return True if n is in SL, False otherwise.
    
    >>> find_num([0, None, None], 0)
    True
    >>> find_num([1, [0, None, None], None], 0)
    True
    >>> find_num([0, None, [3, None, None]], 3)
    True
    >>> find_num([5, [2, [1, None, None], [3, None, None]], [6, None, None]], 6)
    True
    >>> find_num([5, [2, [1, None, None], [3, None, None]], [6, None, None]], 3)
    True
    """

The simplest scenario is finding n whether n is equal to element 0, so we start by writing that.

def find_num(SL: 'SearchList', n: int) -> bool:
    """Omitted for brevity.
    >>> find_num([0, None, None], 0)
    True
    """
    if SL[0] == n:
        return True

Next, we know that if n is not element 0, then it must be smaller or greater than element 0. We know that if n is smaller than the integer 0, then n is somewhere in element 1. 

However, since we are writing this function recursively, we already know that this very function is capable of finding out whether element 0 is equal to n. So instead of writing more code, we can simply call this function to search element 0.

def find_num(SL: 'SearchList', n: int) -> bool:
    """Omitted for brevity.
    >>> find_num([1, [0, None, None], None], 0)
    True
    """
    if SL[0] == n:
        return True
    elif SL[0] > n and isinstance (SL[1], list):
        return find_num(SL[1], n)

We check to see whether element 1 is a list because element 1 could be None. Similarly, if n is greater than element 0, we check element 2 in the same way.

def find_num(SL: 'SearchList', n: int) -> bool:
    """Omitted for brevity.
    >>> find_num([0, None, [3, None, None]], 3)
    True
    """
    if SL[0] == n:
        return True
    elif SL[0] > n and isinstance (SL[1], list):
        return find_num(SL[1], n)
    elif SL[0] < n and isinstance (SL[2], list):
        return find_num(SL[2], n)

Finally, if n is no where to be found, we can simply return False.

def find_num(SL: 'SearchList', n: int) -> bool:
    """
    Return True if n is in SL, False otherwise.
    
    >>> find_num([0, None, None], 0)
    True
    >>> find_num([1, [0, None, None], None], 0)
    True
    >>> find_num([0, None, [3, None, None]], 3)
    True
    >>> find_num([5, [2, [1, None, None], [3, None, None]], [6, None, None]], 6)
    True
    >>> find_num([5, [2, [1, None, None], [3, None, None]], [6, None, None]], 3)
    True
    """
    # [0, None, None]
    if SL[0] == n:
        return True
    elif SL[0] > n and isinstance (SL[1], list):
        return find_num(SL[1], n)
    elif SL[0] < n and isinstance (SL[2], list):
        return find_num(SL[2], n)
    else:
        return False

In this example, there is only a single "branch" or "path" that the code can take, and the final result will only be either True or False. This makes it fairly simple to trace the code, as the function will keep searching until either element 0 is n, and every depth of the recursion will return a True; or the function will reach a None, and then every branch of the recursion will return a False. However, there are also recursive function where each branch returns varying values. We will discuss more on those next time!

Issue 6: Comprehensions and Efficiency

Real knowledge is to know the extent of one's ignorance.
- Confucius  


We were informally introduced to the concept of generator comprehension as a part of our lab exercise. However, the format of our introduction led us to believe that generator comprehension is in some ways faster than list comprehension. How true is this exactly? I did a brief investigation.

import time

def list_via_comprehension(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n using list comprehension."""
    start = time.time()
    l = [i for i in range(n)]
    end = time.time()
    
    return end - start

    
def list_via_loop(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n using a loop."""
    start = time.time()
    l = []
    for i in range(n):
        l.append(i)
    end = time.time()
    
    return end - start


def generator_to_list(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n by converting a generator into a list."""
    start = time.time()
    l = (i for i in range(n))
    list(l)
    end = time.time()
    return end - start


def list_via_generator(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n by extracting each item from a generator using the 
    next() method."""
    start = time.time()
    l = (i for i in range(n))
    
    try: 
        while True:
            next(l)
    except Exception:
        end = time.time()
        return end - start        
        

if __name__ == "__main__":
    n = 10000000
    print("It takes {} seconds to create a list of {}".format(
        list_via_comprehension(n), n), "consecutive integers via comprehension.")
    print("It takes {} seconds to create a list of {}".format(
        list_via_loop(n), n), "consecutive integers via for loop.")    
    print("It takes {} seconds to create a list of {}".format(
          generator_to_list(n), n), "consecutive integers by converting",
          "a generator into a list.")    
    print("It takes {} seconds to create a list of {}".format(
          list_via_generator(n), n), "consecutive integers by using the next",
          "method.")

Here were the results:

It takes 0.9541211128234863 seconds to create a list of 10000000 consecutive integers via comprehension.

It takes 1.6146352291107178 seconds to create a list of 10000000 consecutive integers via for loop.

It takes 1.520693063735962 seconds to create a list of 10000000 consecutive integers by converting a generator into a list.

It takes 1.9292449951171875 seconds to create a list of 10000000 consecutive integers by using the next method.

According to this, it seems that using a generator is less efficient. What if we gave every item a more demanding calculation to perform, such as i ** 2?

import time

def list_via_comprehension(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n using list comprehension."""
    start = time.time()
    l = [i ** 2 for i in range(n)]
    end = time.time()
    
    return end - start

    
def list_via_loop(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n using a loop."""
    start = time.time()
    l = []
    for i in range(n):
        l.append(i ** 2)
    end = time.time()
    
    return end - start


def generator_to_list(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n by converting a generator into a list."""
    start = time.time()
    l = (i ** 2 for i in range(n))
    list(l)
    end = time.time()
    return end - start


def list_via_generator(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n by extracting each item from a generator using the 
    next() method."""
    start = time.time()
    l = (i ** 2 for i in range(n))
    
    try: 
        while True:
            next(l)
    except Exception:
        end = time.time()
        return end - start        
        

if __name__ == "__main__":
    n = 10000000
    print("It takes {} seconds to create a list of {}".format(
        list_via_comprehension(n), n), "consecutive integers via comprehension.")
    print("It takes {} seconds to create a list of {}".format(
        list_via_loop(n), n), "consecutive integers via for loop.")    
    print("It takes {} seconds to create a list of {}".format(
          generator_to_list(n), n), "consecutive integers by converting",
          "a generator into a list.")    
    print("It takes {} seconds to create a list of {}".format(
          list_via_generator(n), n), "consecutive integers by using the next",
          "method.")

It takes 6.058269023895264 seconds to create a list of 10000000 consecutive integers via comprehension.

It takes 6.724354028701782 seconds to create a list of 10000000 consecutive integers via for loop.

It takes 6.631842136383057 seconds to create a list of 10000000 consecutive integers by converting a generator into a list.

It takes 7.01439094543457 seconds to create a list of 10000000 consecutive integers by using the next method.

At this point, it becomes clear that generators are less efficient when it comes to creating a list of items. However, what if we want to know whether a particular item in a list exists.

import time


def list_via_comprehension(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n using list comprehension."""
    start = time.time()
    if any([i for i in range(n)]):
        end = time.time() 
        return end - start
    else:
            return False    

    
def list_via_loop(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n using a loop."""
    start = time.time()
    l = []
    for i in range(n):
        if i:
            end = time.time()
            return end - start
    return False


def generator_to_list(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n by converting a generator into a list."""
    start = time.time()
    l = (i for i in range(n))
    if any (list(l)):
        end = time.time()
        return end - start
    else:
            return False    


def list_via_generator(n: int) -> float:
    """Return the time it took to create a list of consecutive integers 
    from 0 to n by extracting each item from a generator using the 
    next() method."""
    start = time.time()
    l = (i for i in range(n))
    if any(l):
        end = time.time()
        return end - start 
    else:
        return False
        

if __name__ == "__main__":
    n = 10000000
    print("It takes {} seconds to find whether a list of {}".format(
        list_via_comprehension(n), n), "integers had a True value using",
          "list comprehension.")
    print("It takes {} seconds to find whether a list of {}".format(
        list_via_loop(n), n), "integers had a True value using for loop.")    
    print("It takes {} seconds to find whether a list of {}".format(
          generator_to_list(n), n), "integers had a True value by converting",
          "a generator into a list.")    
    print("It takes {} seconds to find whether a list of {}".format(
          list_via_generator(n), n), "integers had a True value by using the",
          "next method.")

It takes 1.2131540775299072 seconds to find whether a list of 10000000 integers had a True value using list comprehension.

It takes 0.0 seconds to find whether a list of 10000000 integers had a True value using for loop.

It takes 1.554197072982788 seconds to find whether a list of 10000000 integers had a True value by converting a generator into a list.

It takes 0.0 seconds to find whether a list of 10000000 integers had a True value by using the next method.

Since the second value in the list is a True value, both loops and generator seems to be equally fast. For our final investigation, we shall refer back to the any_pythagorean_triples(start, finish) example in our lab. 

import time

    
def any_pythagorean_triples_generator(start: int, finish: int) -> bool:
    """Return whether there is at least one pythagorean triple formed
    of integers from start to finish

    start, finish --- positive integers

    >>> any_pythagorean_triples(1, 4)
    False
    >>> any_pythagorean_triples(1, 5)
    True
    """
    start_time = time.time()
    # are there any...
    if any(
        # pythagorean triples in the *generator* --- notice the (...) not [...]
        # look up generator comprehensions, and experiment with changing
        # it back to [...] and calling any_pythagorean_triples(500, 1000)
        ((i**2 + j**2) == k**2 
                for i in range(start, finish + 1)
                for j in range(start, finish + 1)
                for k in range(start, finish + 1))):
        end_time = time.time()
        return end_time - start_time
    else:
        return False

def any_pythagorean_triples_loop(start: int, finish: int) -> bool:
    """Return whether there is at least one pythagorean triple formed
    of integers from start to finish

    start, finish --- positive integers

    >>> any_pythagorean_triples(1, 4)
    False
    >>> any_pythagorean_triples(1, 5)
    True
    """
    start_time = time.time()
    for i in range(start, finish + 1):
        for j in range(start, finish + 1):
            for k in range(start, finish + 1):
                if (i**2 + j**2) == k**2:
                    end_time = time.time()
                    return end_time - start_time
                
    return False


if __name__ == "__main__":
    start = 500
    finish = 1000
    print("It takes {} seconds to find whether there is at least one".format(
          any_pythagorean_triples_generator(start, finish)),
          "pythagorean triple formed from integers {} to {}".format(
           start, finish), "using a generator.")    

    print("It takes {} seconds to find whether there is at least one".format(
          any_pythagorean_triples_loop(start, finish)),
          "pythagorean triple formed from integers {} to {}".format(
           start, finish), "using a loop.")   
    

Our final results were as follow:

It takes 0.021003007888793945 seconds to find whether there is at least one pythagorean triple formed from integers 500 to 1000 using a generator.  

It takes 0.02050304412841797 seconds to find whether there is at least one pythagorean triple formed from integers 500 to 1000 using a loop.

Conclusion

• List Comprehensions are always the fastest at creating a complete list of items, and performing any amount of calculations on all the items. This is because python has optimized this procedure.
• Converting a Generator Comprehension into a list is only slightly faster than creating a list using a for loop.
• Generator Comprehensions should not be used to create lists via iteration using next().
• Generator Comprehensions are significantly faster than List Comprehension at finding whether a particular value exists in the list (i.e. True).
• However, a loop is slightly faster than a Generator Comprehension at finding whether a particular value exists.
• Generator Comprehension's main purpose is for saving memory. (i.e. Generators are for Performance, not Efficiency.)