Week 7

Linked lists. Fun! I’d say the hardest thing about understanding them is the lack of a real index, a consequence of the lack of a real container. It just feels so odd, you know? Having all the elements floating around out there, as far as Python is concerned. Each element only aware of the next one’s location via that rest attribute. The next element not even aware of the element that is aware of it. So tenuous. In fact, it’s that unidirectional awareness that screwed us in labs. That damn prepend method and that damn remove_first method. I mean, queues are first in, first out. That means you’re using one side to put things on and the other to take things off. But both “pre” and “first” deal with just the one side. That was misleading. In order to deal with one side of a conveyor belt—putting things on sometimes and taking them off sometimes from the same side—you would either need a container or you would need the elements to be aware of themselves in both directions (i.e., each element would have an attribute “next” and another attribute “previous”, such that two adjacent elements would be pointing to each other, using up even more memory). Anyway, once we realized that the methods were misleading and decided that we had to ignore at least one of them, the problem became easier to solve, and the benefit of a linked list implementation for a queue ADT became clearer. After all, if you have no index… you have no index to update for each of the potentially millions of elements left in the queue whenever you dequeue.

What else? The midterm. Considering the fact that we only have two lectures this week and one of them hasn’t happened yet, I consider this a chance to unwind rather than to reflect on, well, things we’re about to learn. Therefore, enjoy this hilarious review of a terrible old game.

Week 6

The handout for the lab this week mentioned that we use idioms in a specific language because they’re more elegantly written and their implementation can save time. Intrigued by the idea, I decided to compare the running times of the functions we wrote in the lab vs. the ones we were provided.

First, the functions. You can get the originals on the labs page of the course site. Here are my non-idiomatic implementations:

def ascending_pythagorean(t: (int, int, int)) -> bool:
    return (t[0] <= t[1] <= t[2]) and (t[0]**2 + t[1]**2) == t[2]**2

def dot_prod_2(u: [float, ...], v: [float, ...]) -> float:
    total = 0
    for i in range(len(u)-1):
        total += u[i] + v[i]
    return total

def matrix_vector_prod_2(m: [[float, ...], ...], v: [float, ...]) -> [float, ...]:
    final = []
    for u in m:
        final.append(dot_prod_2(u, v))
    return final

def pythagorean_triples_2(n: int) -> [(int, int, int), ...]:
    final = []
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                if ascending_pythagorean((i, j, k)):
                    final.append((i, j, k))
    return final

def any_pythagorean_triples_2(start: int, finish: int) -> bool:
    for i in range(start, finish+1):
        for j in range(start, finish+1):
            for k in range(start, finish+1):
    if ascending_pythagorean((i, j, k)):
        return True
    return False

So then I wrote a little script called timeloops.py. It imports all the functions — original and my own — and then runs them a lot of times. It does two tests on each. In the first, we run the function tens or hundreds of thousands of times, giving it easy parameters. In the second, we run the function a few times, giving it difficult parameters. (For example, we could make dot_prod’s two list parameters have thousands of elements each.) This allows us both to test both how fast it normally runs and how it responds to more complex cases.

Here’s what it spits out with a few test values:

<dot_prod_1...> ran 2000000 times on basic difficulty in 3.46 seconds.
<dot_prod_2...> ran 2000000 times on basic difficulty in 2.60 seconds.

<matrix_vector_prod_1...> ran 1000000 times on basic difficulty in 4.43 seconds.
<matrix_vector_prod_2...> ran 1000000 times on basic difficulty in 3.42 seconds.

<pythagorean_triples_1...> ran 80000 times on basic difficulty in 9.47 seconds.
<pythagorean_triples_2...> ran 80000 times on basic difficulty in 9.30 seconds.

<any_pythagorean_triples_1...> ran 50000 times on basic difficulty in 12.65 seconds.
<any_pythagorean_triples_2...> ran 50000 times on basic difficulty in 12.58 seconds.

<dot_prod_1...> ran 10000 times on difficulty 2500 in 6.80 seconds.
<dot_prod_2...> ran 10000 times on difficulty 2500 in 11.36 seconds.

<matrix_vector_prod_1...> ran 10000 times on difficulty 800 in 11.79 seconds.
<matrix_vector_prod_2...> ran 10000 times on difficulty 800 in 9.18 seconds.

<pythagorean_triples_1...> ran 2500 times on difficulty 22 in 20.56 seconds.
<pythagorean_triples_2...> ran 2500 times on difficulty 22 in 18.25 seconds.

<any_pythagorean_triples_1...> ran 500 times on difficulty 120 in 15.31 seconds.
<any_pythagorean_triples_2...> ran 500 times on difficulty 120 in 15.26 seconds.

As you can see, all the non-idiomatic implementations are a little faster, except that (1) the difference between the two versions of any_pythagorean_triples is non-significant, and (2) dot_prod_2 runs basic difficulty faster than dot_prod but is far worse at handling complex parameters.

Curious…

Makes me wish I knew how to investigate and compare the underlying implementations!

Week 5

What would recursion look like the wrong way round?

A few nights ago I had a dream. I was on an airplane. I don’t remember the details all that well, but I do have a few visual images of it. Then, at one point, I realized it was a dream, and I woke up. I went about my life for a while, lived various episodes. I was slightly puzzled about having realized that my dream was a dream—I’m not the kind of person who becomes aware of that fact while still dreaming. Then… I woke up again. I realized that I had actually still been having a dream that first time that I woke up and realized I had been dreaming. It was so Inceptiony. It was practically Inception 2.

Anyway, so this obviously has a parallel with recursion in that you go deeper and deeper into the same function. The problem is that the base case here feels like it should be waking life, not any of the dreams. That is to say, unlike in proper recursion, where you go deeper and deeper until you hit a solvable case, in the case of my dreams, the deeper you go into instances of the same function, you further you get from resolving it… so you will go infinitely deep.

I don’t know, I guess we could represent it in Python like this:

def recursive_dream(x):
    if x == 0:
        return x
    larger = recursive_dream(x + 1)
    smaller = larger - 1
    return smaller

Here we’re trying desperately to exit the dream by backing out to our base case of 0, but unfortunately our one operation on x is to make it larger. (The analogy might not be perfect.) You might feel like this will run the function x times. In fact it will go infinitely. Actually, you can’t really enter an infinite loop with recursion in Python, because it has a maximum recursion depth of 987, so you’ll get a RuntimeError.

How do we prove that this is infinite? Well, let’s trace it. What happens if we plug in 1 for x? Well, it’s not our base case of 0, so it calls the function with x + 1, i.e. 2. That calls it with 3… which calls it with 4… etc. So the function never gets to set the value of larger at any depth, nor subtract 1 from it to get smaller, nor return smaller.

So now let’s modify our code a little bit and add an upper limit, our own “maximum dream depth”. Think about it: what will the following code do?

def recursive_dream(x):
    if x == 0:
        return x
    if x == 50:
        return x
    larger = recursive_dream(x + 1)
    smaller = larger - 1
    return smaller

Okay, so now x will presumably == 50 at some point and we’ll hit our upper limit. So try to reason this out: what will recursive_dream(20) return? Trace it if you have to.

If you guessed an infinite loop, good thought but wrong. If you guessed 50, good thought but also wrong. It’ll return 20.

Tracing it again (by the “computer method”), if we pass 20 to our function, it’ll call itself with x + 1, i.e. 21. It’ll keep doing that until it calls itself with x = 50, which will trigger our upper limit case. That case returns x itself. Which means we now have a value for larger, i.e. 50. Next we subtract 1 from that to get smaller, i.e. 49, and we return that. Now, remember that this call is itself what’s setting larger for the next call in the stack, i.e. the next less deep call. Said less deep call will then subtract 1 from that to get its value for smaller, and return that… etc. Until the original call we made, with 20, receives the value 21 for larger, subtracts 1 to get its smaller value, and returns 20.

If it helps, remember that we can also trace this by the method zingarod calls the “human method” (in my opinion not necessarily more human, just the opposite direction). Don’t forget that we’re still working with a perversely inversed recursive function here, so our simpler case is nearer to the upper limit, not to the base case. So we should first ask ourselves, what does recursive_dream(50) return? Clearly 50 itself. So what does recursive_dream(49) return? Well, it calls recursive_dream(50). We know that that returns 50. Which our original call stores as larger, then subtracts 1 from to get 49, which it returns. Then you work out recursive_dream(48), plugging in recursive_dream(49) when it’s time to make that call, and pretty soon you realize that your tracing job is done.

Okay, we get that. Before we finish, let’s do one more odd thing for the sake of fun with our awful recursion. So, making our thoughts more convoluted, what will happen if we do… this?

def recursive_dream(x):
    if x == 0:
        return x
    if x == 50:
        return x + 1
    larger = recursive_dream(x + 1)
    smaller = larger - 1
    return smaller

What will recursive_dream(20) return? Again, try to trace it before you read the next sentence.

The answer, you’ll think, is that surely here it’ll be infinite. Surely! After all, we’ll never get a value for larger that allows us to exit the depth at the upper limit call and start working our way down the stack. That’s totes my own conclusion. Right?

Wrong. It returns 21.

If you’re frustrated, trace it again using the “human method”. So we try recursive_dream (50). Clearly this returns 51. Next, we work out recursive_dream(49). That will bypass our base and upper limit conditions and call itself with x + 1, i.e. recursive_dream(50). We know it returns 51, so 51 is the value for larger back at the recursive_dream(49) call. So the value for smaller is 50, and is returned. Now, again with recursive_dream(48). This calls recursive_dream(49), which we know returns 50. So 50 is the value for larger at the level of recursive_dream(48), and thus smaller is 49, which is what’s returned. It’ easy to extrapolate why recursive_dream(20) returns 21.

Okay, one last one. But I’ll leave you with this one, because it should be cake by now. So far we’ve had the +1 and -1 operations be exactly even. What happens if we unbalance them? That is to say, what does recursive_dream(20) do if we use the following version?

def recursive_dream(x):
    if x == 0:
        return x
    if x == 50:
        return x + 10
    larger = recursive_dream(x + 1)
    smaller = larger - 1
    return smaller

Enjoy! Don’t forget to trace! 🙂