0:15

In this video I want to talk a little bit about how you write functions, and

Â sort of how you think about structuring your

Â code, and you know, what the alternatives are.

Â And as a running example, I'm going to use a

Â function that finds the maximum value in some data structure.

Â All right, this is a common operation that we're going to need

Â to do, so it's as good as any to demonstrate some of the

Â principles, and it should give you some insights into how you should be

Â thinking about doing this, as you have to do it throughout the course.

Â Let's get started.

Â 0:42

Okay, let's say I want to write a simple

Â function to compute the maximum value in a list.

Â So I write here max 1.

Â Which takes data as an argument, which I expect to be a list of numbers.

Â Alright, and I'm going to return the maximum value.

Â So let's think about how we could do this, all right?

Â Well, I'm thinking okay, I'll start with a maximum value, all right?

Â And I'll run through the list and I'll update

Â that maximum value each time I see something bigger.

Â So what should I initialize it to?

Â Well, let's initialize it to the smallest number that

Â I could ever possibly have, okay, that's negative infinity.

Â So you can see, in Python, I can

Â type, float negative inf and I get negative infinity.

Â All right, now, I'm going to iterator over the

Â data, for item in data, and every time I see

Â in item that is greater than the current maxval, I'll

Â set maxval to that item, and I will return it.

Â So save this works.

Â Well, yes it does.

Â I get 123.

Â So, I'm sure you can look at that data list,

Â and you can say hey, yes, 123 is the maximum value.

Â 1:36

Now, this function, you know, it makes sense.

Â It's sort of intuitive to understand.

Â I think that if I hadn't described it to you.

Â You look at it for a little bit.

Â And you'd say yep, that's finding the maximum value.

Â But, there's a better way.

Â Let's look at max 2 here.

Â Okay.

Â So I if I think about this a

Â little bit further and I look at Python's documentation.

Â And say, [UNKNOWN] wait.

Â Python has a built-in function called max that takes

Â a list and returns the maximum value in that list.

Â And so, if I print max 2 update a list, wow!

Â I get 123 back.

Â In fact, I shouldn't even have written this function.

Â Right?

Â Anywhere that I need to use it, I would just call the built-in max function

Â instead of, you know, writing this max to the, that does it for me, okay?

Â So, already we can see that, you know, why should I have written

Â five lines of code when there's already a function that does it for me?

Â Well, it's not always quite that simple.

Â Okay, maybe the function that we have the

Â Max's function doesn't do exactly what I want, right?

Â So, let's think about, you know, maybe I want to know not

Â only the maximum value, but what the index is for that maximum value.

Â Well, okay, so now maybe that first way doesn't look as dumb.

Â Okay, so let's look at max 3 here, what am I doing?

Â 2:54

And again, I'm going to reiterate over the list, I do it

Â slightly differently, so that'll have the index value available to me.

Â And whenever I find an item that's greater than the current maximum value, I set

Â max value to that item and max index to the index in which I found it.

Â 3:14

Okay, I got four in 123.

Â Let's go back up and look at the list.

Â Right, at index four there is the number: 123.

Â One twenty-three is the maximum.

Â Okay, so now, writing that longer function in max three, that

Â kind of looks like max one, starts to make some sense.

Â Okay, but I could this easier again if I

Â understood you know, a little bit more python perhaps, right?

Â And I can write max four here.

Â Lets just run it first.

Â It gives me exactly the same answer.

Â All right, well okay what's happening here?

Â Okay max L, I use my built in max function to find it.

Â Now that I have the max value, I don't know where it

Â was, so I can use the index method of list to find it.

Â So I call data.index of maxval and that

Â gives me back the index, where it was found.

Â All right, so now I've returned the index and the value and again, I don't

Â have that for loop there that you know, maybe seems like a lot of extra work.

Â 4:15

Well when I call max, there's no magic.

Â Okay what's actually happening there.

Â Max is going to have to run through the list and find the maximum value.

Â Okay, there's nothing that's going to be

Â necessarily faster than the for loop version.

Â It's just cleaner to write it this way.

Â Okay.

Â So, it's not necessarily better than the for loop, but you know

Â it looks easier or it looks nicer when, when I read it.

Â Okay.

Â What does data.index do?

Â 4:39

Well it's going to have to run through the

Â list again right, there's no magic here either, 'kay?

Â So I'm looking for the number 123, how do I find out?

Â Well I check the first element, then the second, then the third,

Â at least once I find it I can bail out and stop.

Â I don't have to go through the whole list like I would in max.

Â But effectively, I'm running through the same list twice.

Â Here, okay, to find, that, that, the item, okay?

Â Now, arguably I'm running through the same list twice.

Â Internally in a built-in function that could be heavily optimized instead of

Â the for loop, but I am still running through that list twice, okay?

Â So you want to think long and hard.

Â Does the improved readability of max 4 really, you

Â know, make sense over the potential efficiencies of max 3?

Â And a lot of that is going to have to do with how big your list is, right?

Â For really, really, really long lists, this might matter a lot.

Â Okay, for short lists, it probably doesn't matter at all.

Â 5:31

All right, well, let's go even further, right, maybe, you know, if I look at this

Â list, 123 appears more than once, okay, so what does it mean to find the maximum?

Â Okay, well if I run max 1 okay, and, or max 2,

Â and I'm just finding the maximum value, returning me 123 makes total sense.

Â Okay?

Â Now once I start returning indices with max 3 and

Â max 4, okay, well, it found me one of the locations.

Â And maybe that's okay for what I'm doing.

Â But maybe it's not.

Â Maybe I want to find all of the locations.

Â So now I should think about this a little bit further.

Â Okay, how do I find all of the locations?

Â Well, let's look at max 5 here.

Â Let's just run it and see what it does.

Â And then we can talk about it for a second, okay?

Â This gives me 123 twice.

Â The list of 123 twice, okay?

Â So now, I'm telling you I am returning to you the number of times that it happened.

Â Okay?

Â Or, rather, I'm returning the maximum value each

Â time that happens or a list of them.

Â Okay.

Â So what I do, I have maxvals now, which is

Â a empty list, and then I run through all the data.

Â Okay.

Â If there's nothing in that list, well then what I'm looking at right now

Â must be the maximum value, so I just append it to the list, okay.

Â Otherwise, if the item is equal to the first element in the

Â list, well, then I've found another maximum value, and so I append it.

Â Then I've got this last [UNKNOWN] here where

Â I check if item is greater than maxval zero.

Â Okay, what this means is the things I have in the

Â list right now are not the maximum, because I found something bigger.

Â Right, so I want to replace the list entirely with a new list, and that's

Â exactly what I do, and then when I'm done here now I have a list.

Â 7:05

Now, arguably this is kind of silly, why would I want two 123's in a list,

Â I guess I might want to know that 123, or the maximum value occurs twice.

Â All right, that's possible.

Â But it's probably more interesting to know where it occurs.

Â So that's where Max 6 comes in.

Â Okay, and the structure here is again almost identical.

Â All right, I just keep track of the index as I go, and now I can put

Â both the index and the item into the list,

Â and I arguably have some more interesting information now.

Â I know that 123 occurs twice and incurs that index 4 and index 7.

Â 7:41

So, what did we just do here?

Â I showed you six different ways of basically doing the same thing.

Â [LAUGH] Okay?

Â And I guarantee there are more than six ways of doing this, okay?

Â And some of those others might even be better than the six that I showed you.

Â All right, but that's not the point.

Â The point is I don't want you to just sit down and say oh, I

Â need to find the maximum and type the first thing that comes to your mind.

Â When you build your functions you need to think what do I actually need

Â here, and what's the best of accomplishing it for what I'm trying to do.

Â In fact, I'd argue that I actually

Â showed you three different types of maximum functions.

Â Right?

Â The first type just returned the maximum value.

Â The second type returned the maximum value in

Â one of the indices at which it occurred,

Â and the third type returned the maximum value

Â in all of the indices at which it occurred.

Â Which is better?

Â Well, that depends on your program and what you're trying to do, okay?

Â So there's no.

Â Obvious best chose about how to do even functions like this.

Â You need to think carefully about what you're trying to accomplish,

Â and what the best way of doing it is for your situation.

Â Okay.

Â Now in practice you're probably going to be having to find

Â the max in more complicated data structures, like say a dictionary.

Â Now you going to think about do I want it in the keys, in the values,

Â do I need to associate the key and value, okay, and that adds some complexity here.

Â 8:48

Perhaps more relevant to this class, maybe you need to find a maximum in a grid.

Â A grid is now a 2d structure, okay?

Â So I have a list of lists.

Â Well, you can imagine using these functions.

Â Exactly the ones that I showed you here.

Â To find the maximum of the row list, and then build a list

Â out of that and find the maximum of, you know, out of the columns.

Â Okay.

Â Well, what if I need to know the indices?

Â I need the, need the row and column index.

Â Perhaps it's better now to use one of the methods with a loop and have

Â a doubly nested loop, where I loop over all the rows, loop over al the columns.

Â I have the row and column index available as I"m trying to find that maximum.

Â Okay.

Â The question is really what do you need

Â and what is most appropriate for your situation.

Â Now you may think that these silly maximum functions are not worth the time,

Â and talking about this, but this is

Â really representative of how you should design functions.

Â You need to think about what am I trying to do, and what is the best way to do it.

Â Okay?

Â This is what yields well, well design functions not sitting down and say, I

Â need something to find the max, I'll just type whatever I need right now.

Â