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.