Placeholder Image

字幕列表 影片播放

  • Yeah, we're looking at trees like those, actually, trees and computer science a little bit different.

  • You know, the wood is on top and the leaves on bottom.

  • That's a rotten thing to remember about three.

  • So many people don't know.

  • I want to talk about trees.

  • Andi, I want to show how Tow whatever, Chris trees in using python and using objects.

  • No, Uh, please are very, very versatile data structure, and I think they're often but under use.

  • Some people always want to your strings for everything.

  • And I think a good program a really needs their trees, you know?

  • So the example we're going to look a TTE a syntax trees, And, uh so let me just start us An example S So we're looking at a mathematical expression, something like we times by plus X.

  • That's a mathematical expression.

  • And there's another 13 times.

  • Why plus X.

  • Now people may think it's it's It's like a sequence like a string on dhe.

  • Actually, I think this goes some more, general.

  • I mean, and you and you learn mathematics.

  • My impression is that lots of people get confused by thinking off arithmetic expression itself like a one dimensional structure from left to right.

  • And then there's his operations in this strange things, like brackets on the new you learn some marriageable on and some rules so times good before plus.

  • But really, these expressions is one dimensional.

  • Structures really represent the two dimensions faction in the A tree.

  • So if you look at expression exists is the one question is, what is the top level operation, right?

  • It's a star.

  • Plus it's yeah, because they look at the expression on the top.

  • We should start the star, and then we have to sup expression and left and from the right from the left.

  • But the three and none survived.

  • You get this one here, the plus, and then we can go further doll like this and you can play the same game here.

  • So what was the top level expression here?

  • It's the same.

  • Yeah, could thinks about the baby because we don't have the brackets.

  • The first thing we look at it it's a plus here, right?

  • And then if you go to the left, we have the star and you're good to the violet.

  • We have sex, and here, if you go to the left, we have the three.

  • If you go to divide, we have a vie.

  • And really, the brackets are used to make clear what, what three We mean the blanket that that's a little bit off trick to represent ity every really when we thought, Think about expressions.

  • We should really think about the please and not about the one dimensional structure.

  • And yes, we have this convention like Here's At Star by its more than class.

  • But what is this?

  • Just the convention?

  • And then there's all that.

  • You can avoid having to put brackets here because, as you know, there is only a a limited number of black it in the world and to be tried to safe breakers.

  • There's really a black it saving device.

  • But really, if you look at the trees, the brackets completely disappear and we really see is a structure that you mean if he evaluates them, if he assigned values to vie and two X and then we very it's something we get different answers for these two expressions for those two trees.

  • What we're going to do is now is to represent these trees as objects in Python.

  • Okay, so I'm going to use my Jupiter system, and I'm going to define a class of expressions.

  • So in that class expressions and I'm not going to put anything into hears I was past.

  • That's actually mainly for documentation on, well, nobody finding sap classes off expressions.

  • So what of the sub classes?

  • Off expressions.

  • What can expression be?

  • What's an example, for example, operators.

  • Right.

  • So we have, uh, times.

  • So that's a class times subclass off expression.

  • Okay.

  • And I'm going to fill it in later.

  • Just different in the moment with another one is plus front.

  • Plus, it's a sum plus off expressions.

  • Bitch starters.

  • Plus, there was a party.

  • What is it with the numbers, right, The numbers.

  • Because I'm constant.

  • Okay, close, const.

  • It's pushing empty in the moment.

  • Oh, that's I'm gonna hate myself for saying this.

  • The brackets?

  • Yeah, the blankets we don't need because here's a simple in the trees.

  • Yeah, other.

  • These things, they're not really I mean, but one thing is missing.

  • No, but what does this thing is here.

  • Oh, of course.

  • Right.

  • Yes.

  • So it's okay, class.

  • This is why I'm behind the camera.

  • No, it's good.

  • Okay, So now we have defined structure, class structure.

  • But now let's put something in the first thing we put in his message to create these trees in python.

  • It's an innit method.

  • Every method in person always gets referenced to the object which cuts left and a slippers may not with self.

  • Okay, two SS not very well today.

  • Okay, If you produce a product, a times, we need two expressions.

  • Overly.

  • I mean, one to the left and one to the right.

  • So it's called them left for l and R Shorter.

  • Okay.

  • And all I'm doing in my inner method ISS I'm initializing some instance variables which has the same name.

  • So l becomes l and r becomes up.

  • That looks very tautological, but really, what's happening here is you create an object.

  • Uh, just books Lexus time spokes.

  • He has little times.

  • And now, inside the spokes, there is very about instance very well.

  • One is called el, and one was called our and they're going to be filled in with some other rifle and sisters of mother objects will be created.

  • This is a common scheme I'm using.

  • I'm using the same name for the perimeter and for instance, variables.

  • But really there is something different.

  • So the same game I'm going to play for plus, so I'm not going to do something naughty.

  • I'm going to copy some court.

  • So that's really evil, all right, because one of the holy rule off programming has never copy court.

  • But they're exceptions.

  • The professors can copy court in general.

  • But to be honest, when you start writing a program and you write a prototype, often you end up copying some coat and then later you have another look at your at your court in new start to defector toe effect out thes copies.

  • So So it's okay for quick and dirty, which we do today.

  • It's okay to copy some court, but if you really want to, lucrative than you should factor down.

  • So how would we do this?

  • We will create a new sub class in between behind every operation, and then he would factor out with common for binary operations.

  • But it's a quick and dirty just cookie.

  • Okay, so what do we do for Constance?

  • Defined, entered method and all we need for constant.

  • It's the value, which is surely a number.

  • So it was the same thing.

  • Initialize instance.

  • Variable value off this parents and they use the same name.

  • Finally, we define the labels again.

  • Find a new method.

  • And what's a perimeter here?

  • Would we need to know about a variable is the name which is this thing safe dot Okay, so now we have first version or the O.

  • R of our structure We can create these two trees The 1st 1 even the top level constructor here, if you look at the tree, is times so now as specified in the inn admitted I've got to sup expressions one to the left and went to the right so the front was left.

  • Assist Const.

  • Three.

  • And the one on the right is this expression.

  • And plus plus again has to some expressions bonus available so far.

  • And he is.

  • Argument is the name Why and there's another right self expression.

  • X So far X can hope that's see what happens.

  • Uh, because they would constitute a little sea.

  • And that's not good plastics.

  • No arguments.

  • Did you press enter on that bed of code?

  • Maybe not, uh, but observed You must press.

  • Yeah, otherwise it doesn't because I copied it right But then I didn't.

  • This one poem is called Affairs.

  • Okay, let's do the other one.

  • E two equals.

  • So we start with Plus So they left.

  • Sub three is the times on the set left up to four times as a cost of capital C three So right, Savoir Why?

  • Okay, Nobody If you look here, you see the black it's matching.

  • We finished times Now here we have of our gets a string X and through doesn't go because I mistyped.

  • Plus this is this is the joy of life cooling Know So we have this expression.

  • What can we do with them?

  • You could fix something.

  • Look at them.

  • So what type in Yvonne?

  • Even so, I get the times object and it tells me that it lives at this address which is very exciting and always wanted to know where my time's object lives in case I want to visit it like but that's not enough.

  • We wanted to see what we have is under these trees and okay, maybe we wouldn't go a CE farce expecting it to draw a tree.

  • But at least print something which looks like think expression on it.

  • So you and Piper.

  • So if I want to print an object, I have to say, however, want to print it.

  • So that's another method, are by the vases, double underline.

  • So I mean, it's off like an internal method for Piper and we went to define another message is double underlines in this method is the str method and let me know Start with the with the operators that the 1st 2 how to put a valuable so that's particularly easy.

  • So deaf so on str miss it.

  • It's supposed to return presentation off the object as the string and this is particularly easy in the case of a variable because of every represented this thing.

  • So we just return the name.

  • Okay, so now we can print valueless.

  • But what about Constance?

  • Can reprint Constance.

  • Okay, So constant escapism.

  • There's a number and private already knows how to turn numbers into string by just using str so interesting Turn, Stu huh?

  • Off self dot What?

  • But now let's go to the more interesting cases.

  • How do we plant a times three now what we want to print We want to put the left, expression the times and then divide expression and let's ignore the bracket thing in the moment when we get back to this and it's just oozes So death.

  • Str self and I want to return something.

  • Namely I turn my left explosion.

  • This is Sefton L into a string and here using str But this high, it's that what's really going on?

  • It's a record in because str tries to plant this expression so it's going to call the underline underline str method for this object, whichever just defining here.

  • It's really another application application off the Magic, Rikers and Twig.

  • But in this case is likely but hidden.

  • Okay, and then I would know provider in between Starr, I don't know, it was the same for safety are okay.

  • And because we're in the quick and dirty in support of typing mood, I'm lazy.

  • And there's this copy.

  • Okay.

  • And now the only change, it's Plus, there's this really a case here for refectory.

  • But this time I tried to remember pressing return and I don't see what this point even, um, not exactly what we want.

  • But this is the first step point.

  • He too looks very similar.

  • Okay, partial result we can see or expressions, but the black it's Arnold said Okay, because you've run out.

  • Yeah, maybe if you was too much in the previous lecture is really annoying.

  • So but no, let's be.

  • You could be clever and tied to Clint as little brackets as possible, but leaves This is an exercise.

  • Actually, it's explained in the book.

  • But today we're just play it easy, and we print lots of brackets.

  • So each time and we have a binary operation, you put some packets.

  • I don't like this.

  • Okay?

  • And here's the same.

  • No can copy.

  • And he was a problem.

  • If you copy and then you change something, you have to change it to places.

  • And often we forget to change it at the second place.

  • It's a very nice source off hours.

  • Okay, Actually done this.

  • Okay, well, let's see.

  • And I couldn't even lots of pockets.

  • 22 now.

  • Not pretty, but at least it's collect.

  • There are some some base, too, to, uh, minimize the number off packets and used the convention that time spine more than plus or any such conventional.

  • Okay.

  • But instead I'm going to write another operation, namely, we want to evaluate or expressions on the movements, expressions of those trees.

  • And we We can't We don't We don't know what what are their values are.

  • And for doing this, I'm going to use a dictionary because I need to bury it in expression with variables.

  • I needed assignment off variables to numbers, but things to numbers I could environment.

  • Okay, which is a dictionary?

  • Dictionaries are written was set for tickets.

  • And I say, Okay, Bxb too.

  • And why be four?

  • So ends is no dictionary, and I can look up.

  • For example, if I want to know what is the value of X?

  • I used the syntax too.

  • And what is the value?

  • Oh, boy, that's full.

  • Okay.

  • We want to evaluate our expression using such a environment assignment available to the numbers.

  • Okay, let's do this.

  • Let's tow again.

  • The the easy cases, the easiest case for the evaluator is actually the constant.

  • So you're very later frontal.

  • This time we don't use underlines because of just the method invented myself safe.

  • So has got the object that safe and this dictionary logical end environment.

  • And in the case of the constant, actually the environment is completely ignored because all you have to do is to return the very you because the very off a constant doesn't actually depend on the assignment.

  • Two very.

  • It's no next.

  • That's the very image which is a bit more interesting because there we do get the dependency.

  • So we have Yvonne.

  • So if end and what do we do if you just look up?

  • Is the very off this variable So return health and now safe dot name.

  • So you took up slaves this name and return it.

  • Okay, now the case for the, uh, operators.

  • So how do we very eight times so so And to get a dictionary.

  • But death was maybe because miss ability.

  • And here we really see the records in because to evaluate times vary it The left expression I am very It's a light expression and then multiply results.

  • Okay, so I see said if I got her that Eva that used the same environment times safe dot ah dot Evolved the same environment sneaky Rikers in was the one for str because he couldn't see it towards.

  • So because here, so under str calls str but actually str called underline str So there was a sneaky because this one is actually not sneaky because we define evil, and then we call evil.

  • So it's really incursion with, because it's a common situation.

  • If you have a distraction like a tree and you want to process it you Because if I recall, you're safe on the substructure.

  • Important pitter No, I'm doing more or less the same for Plus Okay, how tall was my in the nation?

  • But this time I use plus half.

  • Actually, you find everything.

  • Okay?

  • We have this environment already, so let's see.

  • Even even you want to evaluate it?

  • This ends.

  • So I don't really know what the ancestors have to calculate it.

  • What's the answer?

  • Okay, three times two plus four is 18.

  • Let's see, right?

  • Yep.

  • By then and now, the second expression Corvis was called to you R f three times for 12 plus 2 14 three times forest, Plus to his 14 year angry yet and personally know at this point, you could say Okay, fine.

  • You have no represented expressions and you can prince him and you can evaluate them.

  • What's the big deal now you can do operations on expressions.

  • The one operation on expressions like this and this is quite important for the latest fashion for formation learning.

  • So the mission.

  • Learning the use derivatives.

  • So the idea is that soft so that every measure learning poor problem correspond to some landscape, and we want to find the minimum.

  • And this landscape is smooth.

  • So hold your finds a minimum in the landscape.

  • How do you find the valley?

  • You go down, right?

  • And to go down to determine what is down, you have to calculate the partial derivatives in each direction.

  • The box.

  • Over here we have two variables.

  • So I mean, this is a very simple case.

  • Will not be interesting, but for every very off x vay, we get a height and Loki, I fused Just interject here.

  • But if you think about floating for normal, your numbers uh, we want to find us.

  • The bottom is a little point and we don't know where this we looked.

  • We start someone's on be walked on because of dissent.

  • 555 is an order.

  • Actually, five would be possible.

  • There's a six year a seven here in eight year and nine here.

  • Hence, what do we do?

  • 55?

  • What a way to the end.

Yeah, we're looking at trees like those, actually, trees and computer science a little bit different.

字幕與單字

單字即點即查 點擊單字可以查詢單字解釋

A2 初級

在Python中對樹進行編碼 - Computerphile (Coding Trees in Python - Computerphile)

  • 8 0
    林宜悉 發佈於 2021 年 01 月 14 日
影片單字