Code Optimisation via Memoization - Computerphile

Key Takeaways

I thought we'd um go back to a bit of basics and talk about memorization or as I like to call it caching things. Um it's it's an interesting and useful technique in programming and one that perhaps people sometimes kind of don't really understand what it is. It's actually quite simple. Um and so I I thought the way to do this would be to pick a problem that can be helped with memorization depending on how you implement it and and then we'll see what it does. So, there was a lovely number file video on frog hopping. >> Now, if we have two lily pads, we could go one and then one, or we could go two, >> which is a problem I've come across before, but it's always nice to see the mathematical derivation of this. Note that there won't be any such things in this video. I'm going to program it. >> Will those frogs be on stilts? >> Frogs on stilts? >> No. No regular frogs. Actually, I was very impressed with Brady's animations. The idea is you've got some number of lily pads or stones or something that frogs are hopping on and they can hop one at a time or two at a time and you've got, you know, let's say 10 stones. How many different combinations of types of hops would would it require to get to the end? So let's say one one one two or two hops and then one one, right? It turns out that it's related to Fibonacci sequence. Fibonacci is a very common example of something you can use recursion to solve not unwisely sometimes. Right? So I thought we'd perhaps make the problem a little bit more complicated just to make it a bit more interesting, right? And also there is already a great number file video on this. So we're going to do stair climbing. You know those things in your house that are tiring to go up. Let's imagine you have some number of stairs, right? So let's say 1 2 3 4 5 6 8 9 10. I think that's 10 stairs. Why is the last one round? >> It's carpet. >> Yeah, round a carpet. Now you can climb up. Sometimes you could skip a stair or you could skip up three stairs. If you really got good legs, you could jump four or five stairs, right? I can't. Um, or you can just be regular and climb one stair at a time. So, we've got n stairs. Let's say n stairs. And we can go in some number. It's, you know, let's say a set of 1, three, or five stairs at a time. Right? So, we can go from here up one stair or we can go up one, two, three stairs or we can jump 1 2 3 4 5 which looking at it is quite a long way. um you can just just jump half the half the staircase. How many different ways could you climb these stairs? It's a very similar problem to the frog hopping problem. Um it's just a slightly more interesting implementation when we code it up, right? And so I won't be driving the maths. I'm going to brute force it using my laptop. Let's think about breaking the problem down in this kind of recursive way. So let's say we're at the top, right? How did we get there? What was the last step we could have done? Right? It's one or three or five, right? So, we either came from here or we came from one, two, three here or we did this ridiculous jump 1 2 3 4 5 and we came from here. If we say, well, okay, f, which is our function we're trying to solve of n steps, right? with one, three, and five possible steps is going to be equal to however many combinations of stairs we could go here plus however many stairs combinations we could get to here plus however many combinations we could get to here. Right? It's a very similar problem. So it would be f of nus1 plus f of n -3 plus f of n -5. you've drawn starting at the top and will you always have to work backwards to work this out? >> Um, it's easier in this case. Um, it's it's better to think of it if someone's climbing the stairs, but we're kind of in hindsight reflecting on how it went, right? >> How could you have got there? >> Yeah. How could you have got there? And so, actually, if if you were doing this for frogs where you jump one or two steps, it's easier just to write a for loop that calculates a Fibonacci number, right? And and you wouldn't necessarily even need to use recursion to solve Fibonacci even though it's a nice example of it. I suppose it's a bit like when you're planning a route in in a map, you know, you need to know where you're going before you set off, don't you? >> If you consider that you might have very many possible step jumps, right? So, let's say you're trying to climb a 100 steps, but you're some kind of athlete and you can jump eight, seven, six, five, four time at the same time. It becomes very unwieldy to try and encounter all those or try and try and consider all those possibilities from the start going upwards, right? That is going to expand. So, in a way, breaking it down into just copies of the same problem in a slightly easier way is a very natural way to do this, right? And it and it lends itself well to recursion. When you see a function like that, if you're writing in using recursion, at least naively, looks pretty easy to do. So, let's code that up and then we'll explain why that's a very bad idea. All right, so I've got a almost blank Python file here. We've got this small function that I've written where we can time how long another function takes to run. So this will allow us later to test. We're not going to that's not interesting. We're going to skip over that. What we're going to do to begin with is not worry too much about like possible combinations of steps. So 1 2 3 4 five different different steps. Let's just say we're fixing it at 1, three, and five for now, right? To make it a bit easier. So we're going to define some function define step count which is going to be for n where n is the number of steps. It's going to return a value of how many different combinations are of steps you can take given the options are one, three, or five. Right? So, we already know broadly speaking what we're going to have to do is return step count of n uh minus one plus step count of n minus 3 plus step count of n minus 5. Right? And that will workish. Right? If we run this, we will quickly find it doesn't work. Right? So uh if we say step count of 10. >> So step count is how many steps in total? >> Yeah, give me the steps in total. It's going to say ah maximum recursion depth reached because the previous line repeated 990 times. Right. The reason is because I haven't got an end condition. I haven't said what happens when we get to the bottom of the staircase. >> Oh, so it could go into minus numbers and just >> Yeah, it's just going on on some infinite staircase and it turns out my laptop isn't powerful enough. What are the end conditions? Well, if we arrive at zero, there are no more steps, then this was a successful path. We don't know what the function calls were. So, we don't know what the order of the paths were, but we know that's successful. So, if there's no brackets, I've been doing too much Java. If n equals 0, return one. Right? This is a successful path. And we add one to our total. >> So, to trap it in case it goes below zero. >> Ah, yes. So, let's imagine you're one step from the bottom. your n minus one will return zero but n minus 3 or n minus 5 are going to overshoot and those are not valid combinations of steps right so we can say if n is less than zero return n and those are our uh end conditions let's save that and let's run this and see if this runs any better than it did before so step count 10 47 possible combinations right I couldn't actually off the top of my head tell you whether that's correct but let's pretend that it is now this is actually not a good implementation this is exponential growth. What essentially intuitively what's happening here is n minus one, n minus 3 and n minus 5 are computing a load of repeating versions of the same problem and it's hugely memory inefficient to do this. Right? So you'll see that if I if I call step count of 25, it's pretty fast. If it's 30, it's getting a little bit slower. If it's 35, now we're actually having to wait for a little bit for it to finish. Once it gets to 40 or 50, this laptop probably won't do it. Right. So, it's growing very, very fast because it's an explosion of different combinations of steps. >> So, it's just literally having to do too many, if you pardon the pun, steps. >> Yes, it's Yes, that's exactly right. Let's have a look at why. We're back on our paper and we're just going to look at the sort of function calls we would be doing if we were writing it this way and why that is a big big problem, right? In terms of the speed, it doesn't matter for for n equals 10, right? And so sometimes you needn't do anything extra because yes it's slow but you never have a big problem and so it's not a problem but often that is not the case. So let's just go with um f of six for now. I'm going to call it f only because if I write step count I'm going to very much run out of page very very quickly. So this is f of six. >> So this is a sixst step stair count. >> Yes. And remember for now all we can do is go in one three and five jumps. So this is going to call three functions. It's going to call n -1, n -3, n - 5. So that's going to go to f of 5, which is n minus one, f of 3. It makes me feel better when you nod, you know, my my simple arithmetic. I'm not messing up in front of everyone. Uh, and f of one, right? Because, you know, which is nearly finished. Now, let's expand this one. So f of five could be f of four, f of two and f of n which is actually our win condition but you know we we won't dwell on it. I mean I'm already running out of page this is a problem. So let's go f of three would be f of two f of n f of minus2 right which is going to be a fail condition but f of one is going to be f of n f of -2 and f of -4 these will end f of four will be f of three f of 1 f of - uh one something like that you can see we're very quickly expanding and this is only f of six I already did f of 10 on here. So, you know, this is this is a big problem. I mean, let's keep going. F of of one and so on and so on, right? So, and you can imagine this is expanded very very quickly. You know, N6 if it goes bigger than this, it's going to be huge. And the other problem is we've just done all this work multiple times for absolutely no benefit at all. So, if you look at all the occurrences of let's say f of three, right? N equals 3. Here, here there's another one over here. um two is here here zero is everywhere right and this will happen more and more the bigger the tree is and the more combinations of sets you can do memorization is the idea that if we're using let's say a recursive function or a function that we're calling multiple times if for a given input the output doesn't change we can just cache that result store it and then do a very quick look up and go ah we already calculated that as five we don't need to we don't need to do it again and we can massive massively reduce the time it would take. So let's imagine that we'd already calculated this. When we get down to here, we don't need to expand it because we already have the result. That's what memorization is. Before we think about memorization and caching our intermediate results, let's just improve our step count algorithm to handle the general case of it's not always 1, three, and five steps that you're doing. Right? What we're basically doing is n minus whatever that step combination is for all the possible step combinations. So we can add a parameter. Let's call it steps and that is the different let's say 1 three and five and then we can have something like so in Python for those of you that don't use Python you can do something called list comprehension where you can say a particular step for for all of the steps in that list. So we can say s for s in steps, right? And then we're going to put this into a function. For each s, we're going to say we're going to call step count n minus s for s in steps. And then we're going to sum that, right? And Python has a lovely sum function that I don't have to bother writing. And then we're going to return that instead. So let's just test that works before we get too carried away. So I'm going to save that step count of let's say 10 steps. And we already know it's one, three, and five possible combinations missing one argument. Oh, I've forgotten to pass the steps to the to the function, right? So, let's go from there. So, let's see if this works. So, step count for let's say 10 steps and 1 3 and five possible step combinations. 47. I'm kind of pleased the answer is the same. Actually, I'll be honest with you. We can actually change it. So, we could say, okay, you can now only go one and five steps. You can't go three steps at a time. And that was actually only eight combinations, right? And you could probably work them out by hand. So it it does theoretically work. It's just going to be very very slow and very very inefficient. So let's go back to our code and think about how we could fix this. All we need to do is store a dictionary, right, which is Python's name for a kind of an array of key and values for each potential n. And when we encounter it, we just store that value and we can reference it later. I'm just going to tidy this up a bit. So, we're not going to uh override or change our step count cuz we want to be able to compare the speed of these things. So, I'm just going to copy this down here and we're going to call it memsteps. And mem is going to be some kind of memorized version, some caching version of the same thing, right? So, how would we do that? Well, we need an implementation that has a cache. So, we're going to need to create that cache. There are lots of different ways in Python you could choose to do this. I'm going to do it by having another function that has a cache as a parameter. Right? You could put it inside. You could do all kinds of clever things. For the sake of clarity, I won't do that. So, mem cache with n steps and a cache, right? And now, mem is just going to call meeps cache with n steps and an empty dictionary, which is going to be the empty cache that we're going to use. So, we don't actually call memsteps cache directly. We could, we're going to use memsteps, and then we're going to have this cached version, right? Hopefully that's nice and clear. The rest of the code is pretty similar. So how do we add our temporary cache into this function? Well, first of all, if n is zero, we're still going to return one, right? If n is less than zero, we're still going to return zero, right? That's nice and easy. There's no lookups. That's very quick. If n is in the cache, right? That's a nice uh Python way of saying, does the dictionary contain that key? Right? then we're just going to return the cache value at position n. If it's not, we actually have to do the slightly more troubling expansion. All we're going to do, so instead of just returning the sum, we're going to say total equals sum and then we're going to say cache of n is equal to total, right? And we also need to return the total. Now the only other thing is I need to update this function call because this function call is looking in the wrong place. I'm currently calling step count. I need to return I need to call memstep's cache like this right and I need to pass the cash through. All we're doing is exactly the same algorithm but this time we have access to this dictionary that is holding previous ends that we've seen before. If we come up with one we've seen before we just return that value straight away rather than actually doing all these function calls and expanding this. This is what memorization is. It's just adding this ability to recall previous versions of this function and returning those results really, really quickly rather than computing them all again from scratch. Now, it's just occurred to me that we don't actually return this value here. So, I'm just going to put a return in. I'm sure those of you were very annoyed and had spotted that already. Um, let's do some timing tests. So, I've got this time it function. So, time it and you pass the function you're trying to time. So let's say step count the number of steps 10 and the number of possible step combinations 135 and the time elapse was 0 0 083 seconds not very long. Let's watch what happens as we start to increase that number. So now we're going to do 30 steps. Half a second, right? 35 steps. Well, now we're just sitting watching nothing, right? It's about Oh, hang on. Uh it will do it. Yeah. So, it's 3.7 million possible combinations and it took seven and a half seconds to run. >> Okay. >> Not great. Now, let's replace the step count with our mem, right? And just remind myself what I called it. Memsteps. Yeah. Okay. Good. Me steps. 0.051 seconds >> for that same >> for the same function. I can't really increase the step count test any further because my laptop won't do it. I can produce much bigger values for with memsteps because I'm caching so much of this tree. So let's say what are the possible combinations of a 100 steps in one three and five step increments and the answer is a very very big number in fractions of a second right the number is is into the quadrillions or trillions or something. It's very very large. I suggest you don't try and do it by hand on the stairs basically um or by feet in languages like this. Often libraries exist to help you with this kind of stuff. So memorization is the idea of you've got a repetitive function you're calling over and over again. You're going to see f of two another time, maybe lots of times. Let's store that result and just return it rather than expanding that function tree any further and just recursing over and over again cuz that would be really really slow. >> Today's episode sponsor is Brilliant. And for the longest time, I thought of them as a place to learn about math and general science. But lately, I've been delving into their huge number of courses and lessons about coding, computers, and AI. This is great stuff, and I think the sort of people who watch Computer File might like it. You might also like it as a gift for other people in your life. You can do that, too. You know, this stuff is the future for many of us. Our careers, our day-to-day lives, and Brilliant, with its great design and interactive content, they're going to put you well on top of it. This might be the first step on a new career path. To learn for free on Brilliant, go to brilliant.org/computile. You can also scan the QR code on the screen or click on the links below. Brilliant's also giving our viewers 20% off an annual premium subscription which gives you unlimited daily access to everything. Our thanks to them for supporting computer file.