Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位
證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

Functions: Finding the Max

Loading...

计算原理（第 1 部分）

4.8（446 個評分） | 21K 名學生已註冊

課程 3（共 7 門，计算机基础專項課程）

This two-part course builds upon the programming skills that you learned in our Introduction to Interactive Programming in Python course. We will augment those skills with both important programming practices and critical mathematical problem solving skills. These skills underlie larger scale computational problem solving and programming. The main focus of the class will be programming weekly mini-projects in Python that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 1 of this course, the programming aspect of the class will focus on coding standards and testing. The mathematical portion of the class will focus on probability, combinatorics, and counting with an eye towards practical applications of these concepts in Computer Science. Recommended Background - Students should be comfortable writing small (100+ line) programs in Python using constructs such as lists, dictionaries and classes and also have a high-school math background that includes algebra and pre-calculus.

查看授課大綱

您將學習的技能

Computer Programming, Algorithms, Python Programming, Combinatorics

審閱

4.8（446 個評分）

5 stars
374 ratings
4 stars
57 ratings
3 stars
12 ratings
1 star
3 ratings

IB

Jun 12, 2017

Yay, no more peer grading! This course felt easier than intro2. Less fiddling with your programs and more about concepts.

JG

May 29, 2016

Awesome course! Recommend to newcomers and intermediate alike. The instructors are great and the content is challenging.

從本節課中

Counting, growth of functions, higher-order functions

This week, we will explain the importance of counting in solving complex problems.

The Importance of Counting 4:29

Counting and Sums14:15

Functions: Finding the Max 9:50

Higher-order Functions 11:06

Plotting Statement Counts13:57

教學方

Scott Rixner
Professor
Joe Warren
Professor
Luay Nakhleh
Associate Professor

腳本

[MUSIC]

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.

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.

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?

There are pretty much the same thing, I

have maxval that I initialized to negative infinity, but

I also have the maxindex, this is going to

be the index where I found that maximum valued.

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.

Now when I'm done, I can return the tuple

of max index and max val, so let's try this.

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.

Now, lets think about this for a second.

I would argue that this might actually be worse than max three, why?

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?

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.

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.

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.

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.

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.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司