1
00:00:01,069 --> 00:00:03,189

the following content is provided under  a Creative Commons license your support  will help MIT OpenCourseWare continue to  offer high quality educational resources  for free  to make a donation or to view additional  materials from hundreds of MIT courses  visit MIT opencourseware at ocw.mit.edu  it is my great pleasure to welcome John  Bentley now retired from Bell Labs John  was my PhD thesis supervisor at Carnegie  Mellon I actually had to supervisor the  other one was HT Kong who is now at  Harvard I guess people flee Carnegie  Mellon like the plague or something so  so John is as you know because you've  studied some of his work is a pioneer in  software performance engineering and  he's going to talk today about a  particularly neat piece of algorithmic  engineering sets that centers around the  so called traveling salesperson problem  which is an NP hard problem and P  complete problem in fact and so without  further ado John why don't you tell us  what you got to say as Charles mentioned  I want to talk with you I want to tell  you a story about a cool problem this is  a problem that I first heard when I was  a young nerd not much older than you  little this little pile of nerds in  front of me in high school that the  traveling salesperson problem who here  has heard of the TSP at some point I  heard about this in high school one of  the things you read about in the math  books and a few years later I had a  chance to work on it in 1980 I was doing  some consulting and I said well what you  need to do is solve a TSP then I went  home and realized that all this stuff  that I had learned about it was sort of  relevant but it didn't solve the problem  so I started working on it then Michael  or our colleague christos papadimitriou  who's been at Berkeley for a long time  after being in a lot of other places  once told me the TSP is not a problem it  is an addiction so I've been hooked for  coming up on 40 years now and I want to  tell you one story about a really cool  program I wrote  I've been paid to be a computer  programmer for coming up on 50 years  I've been doing it for 48 years now this  is probably the most fun the the coolest  program I've written over a couple day  period I wanted hi yes story start off  with what recursive generation is then  the TSP what it is then I'll start with  one program and we'll make it faster and  faster and faster  again I spent my whole life squeezing  performance this is the biggest squeeze  ever and in some principles behind that  we'll start though with how do you  enumerate all the elements in a set if I  want to count numerate the guys between  one and a hundred I just count that's  the big deal but how can I  for instance enumerate all subsets of  the set from the integers from 1 to 5  how many subsets are there I've  introduced from 1 to 5 part of me 2 to  the 5 32 but how do you say which ones  they are how do you go through and count  them well you have to decide how you  represented you you guys know all about  set representations we'll stick with  vectors to the time being an iterative  solution is you just count 0 1 2 3 4 5  up to 31 that's pretty easy but what  does it mean to count what does it mean  to go from one integer to the next how  do you go from a given integer to the  next one what what's the rule for that  it's pretty easy actually you just scan  over all the zeros turning that you  start at the right-hand side least  significant digit scan over all the  zeros turn to 100 I lied to you I scan  over all the ones turning them to zero  until you get to the first zero and then  you turn that to a one so this one goes  to one zero this one goes to one one  this one goes that one becomes zero that  one becomes zero then it becomes zero  zero one zero zero so a pretty easy  with them you could do it that way I  just scan over all the ones turn them to  zeros take that person we flip it around  but that doesn't generalize nicely well  we're gonna see a method generalizes  very nicely this is a recursive solution  to enumerate all to the N subsets of a  set asides in and the answer is this all  sets of size M is just put a zero at  this end enumerate all sets a size n  minus one how many of these will there  be two to the M minus one how many of  those 2 to the M minus one or do they  add up to 2 to the M but all of these  have a zero at that end and one at that  end everyone see that recursive sketch  of how that works here's the example up  here you have the zeros at this end and  you pull it out you have the one at that  and you fill that out if you do that you  notice that in fact we're just counting  backwards 0 0 0 0 0 1 0 1 0 3 4 5 6 7  that's the algorithm and the cool thing  is the code is really simple I could  probably write a program like that in  most languages and get it correct so if  N equals 0 generate all subsets of size  M just visit the current one you have a  pointer going down the array otherwise  set the rightmost bit to 0 generate all  substances recursively it set it to 1 do  it again recursively that's a starting  program if you understand this  everything else is going to be pretty  straightforward if you don't please  speak up one thing that you people have  suffered the tragedy of 14 or 15 or 16  years of educational system that have  sort of beaten the creativity out of you  and and you're afraid to speak up so  even if something even if I'm up here  spouting total [ __ ] you'll ignore  that fact and just sort of politely  stare at me an odd but this is important  I want  understand this ignored him to stay on  this speak now or forever hold it anyone  have any questions please please  [Music]  I'm sorry why do we set P to the so here  first I could go out to the extreme  right most and I set it to zero then I  recursively fill those in then I change  it from a zero to a one there and I fill  all those in so this is a program that  we'll go through and as it enumerates a  subset it will call the visit procedure  a total of two to the M times and it  comes down to the bottom of the  recursion thank you great question any  other questions about how this works  okay welcome back to this the traveling  salesperson problem I apologize I will  really try to say the traveling  salesperson problem but I will slip  because I was raised with us being the  Traveling Salesman problem no  connotations no intentionality they are  just senility galloping along it's a  cool problem Abraham Lincoln faced this  very problem in the years 1847 1853 when  he everyone here has heard of circuit  courts why do they call them circuit  courts because the court used to go out  and ride a circuit to go to a whole  bunch of cities now people in the cities  come to the court but back in the day  and 1847 1853 Lincoln and all of his  homies would hop on their horses judge  defense lawyers prosecutors and go  around and ride the circuit here and so  this is the actual route that they rode  where they wanted to do this effectively  it would be really stupid to start here  in Springfield and go over there then to  come back here then to go over there  back and forth what they did was try to  find a circuit that minimized the total  amount of distance traveled that is the  traveling salesperson problem were given  a set of n cities it might be a general  graph these happen to be in the plane  but you really helicopter service was  really bad in those days so they didn't  fly directly point-to-point whether they  stayed on roads what really matters here  is a graph and better than here I'm  going to speak at this everything I say  will be true for a graph it'll  true for her geometry I'll be sloppy  about that  we'll see interfaces how how you handle  both but just cut me some slack for that  I have actually phases myself when I  worked on a system where we had a big  mechanical plotter and we'd wanted to  draw these beautiful maps where the naps  could fill in dots they happen to be  precincts some of them were red some of  them were blue and you wanted to draw  all the red dots first and go around  here and impact the plotter would draw  this red dot then that red dot then this  one then that one the plotter took an  hour to draw the map  I was consulted on this aha you have a  traveling salesperson problem I went  down i reduced the length to about one  tenth of the original length if it were  took an hour before how long would it  take now well it took about half an hour  and the reason is that the plotter took  about half of its time moving around  about 30 minutes moving around and about  30 minutes just drawing the symbols I  didn't reduce the time drawing the  symbols at all but I reduce the time  moving things around from about 30  minutes to about 3 minutes  that was still a big difference so I  faced there when I worked at Bell Labs  we had drills that would go around laser  drills were on printed circuit boards to  drill holes they wanted to move it that  way I talked to people at General Motors  at one point on any day they might have  a thousand cars go through an assembly  line some of the cars are red some are  white some are Green's more yellow you  have to change the paint some of them  have v6 some of them have v8 some of  them are two-door some of them are four  doors in what order you want to build  those cars well every time you change  one part of the car you have to change  the line and what you want to do is  examine as it were all in factorial  permutations put in the cars through and  choose the one that involves the minimum  amount of change and that's the change  from one car to another is a  well-defined function everyone see how  that weird TSP isn't active TSP so all  these are cool problems further  or as a computer scientist it's the  prototypical problem it's the the e.coli  of algorithmic problems it's it was  literally one of the first problems to  be proven to be np-hard  I held Karp gave a polynomial time  algorithm for it  there are approximation algorithms of  this kernel and given heuristics it's a  really famous problem it's worth  studying but here is what really  happened to me here's why I'm standing  in front of you today talking about this  my friend Mike Sheamus in his 1978 PhD  thesis on computational geometry talked  about a number of problems one of them  was the TSP and he shows us and he gives  an example of this tour he says here's a  set of sixteen points here's a tour  through of them as here's the traveling  salesperson to her through them and then  he says in a footnote in fact I'm not  sure if it's a really optimal tour I  applied a heuristic several times I'm  not positive it's the shortest tour if  you wrote a thesis it would be sort of  nice to to know what's going on there  can you solve a problem that was this  tiny little 16 element problem 16 points  in the plane can you really figure out  what the TSP is to that at the time my  colleague or our colleague a really  smart guy couldn't do it it was  computationally beyond the bounds for  him well in 1997 I came back to this and  I really wondered is it possible now  computers are a whole lot faster in the  20 years we were talking about that  earlier today 20 years computers got  faster a lot of things got better have  things change enough so I can write a  quick little program to solve this I  don't know we'll see I did that I talked  about it I gave a talk at Lehigh  University 20 years ago they liked that  they incorporated it into an algorithms  class the same professor gave it time  and time and time  in eventually he retired they asked me  to come over and give this talk to them  I can't give a talk about 20 year old  material that's the computer science  doesn't work that way  so I coded things and I wanted to see  how things changed in two years so this  talk is about a lot of things but  especially it's about how has  performance changed in 40 years so  that's one of the reasons we were one of  the things we were talking about earlier  today I could give a bunch of titles  this talk for you the title I give is a  sampler performance engineering it could  be next week I'll give it at Lehigh this  is their final class in one of their  final classes and algorithms and data  structures I'm gonna try to tie  everything they learned together  it could be into all this other things  implementing algorithms a lot on  recursive generation applying algorithms  really Charles is a fancy dancy academic  he's a professor at the Massachusetts  Institute of Technology I'm just a poor  dumb computer programmer but boy this is  a fun program what it is not is it's not  state-of-the-art ESP algorithms people  study the problem for well over a  century they have beautiful algorithms I  am NOT going to tell you about any of  those algorithms for the simple reason  that I don't know them I could look him  up in books but I've never read them the  fancy state-of-the-art algorithms and  I'm also going to show you again in  cancer I could analyze it I've analyzed  much of these if I had another hour or  three I could do the analysis but I  can't so I'm just going to do the show  you some anecdotal speeds without  reading the analysis let's talk about  some programs a simple C program max in  it's a maximum number that N and it's  going to be in the number of cities I'm  going to have a permutation vector where  if I have the tour going from city one  to seven to three to four it says 1 7 3  4 the distance between cities is going  to be given by a distance function  there's this distance D of IJ the  distance from city to city J here's the  first algorithm what I'm going to do is  generate all in  toriel permutations look at them and  find the best one it's not rocket  science the way I'm gonna do this is a  recursive function where I happen I  could have done it from left to right I  am a C programmer I always count down  towards zero so I'm gonna count down  that way where all these cities are  already fixed I'm going to print these  here's the program to search for em all  these have already been fixed what I'm  going to do is if M equals one then I  check it otherwise for I equals zero up  to M for each value from zero to minus 1  I take the I element I swap it swap  three seven takes the third and seven  positions and swaps them I swapped that  to the final thing I call it recursively  I didn't swap it back to leave it in  exactly the same state I found it and I  continue so Jordans going to generate  first all nine permutate put all my  digits in the last position then for  each one of those I'll put all eight  digits in the last position and going  down this is really interesting  important and subtle if you don't follow  this part it's going to be difficult  are there any questions at all about  this have I lied to you yet about this  you're honest enough to tell me if I  have thank you anyone else  I'm sorry please so so far as I recur  down with SM moves down all these are  fixed so I'm going to fix these things  and then I'm gonna take care of all  these later so originally I'm going to  have this array v-0 if I have a nine  3tsp it'll be 0 into 2 4 6 7 8 9 and  first I put 0 in the end and do the rest  and I put 1 in the end to up 9 in the  end and do the and recur down but as the  program is progressing if you stop the  program at any time and look at a glance  of the program you can see that given  the value of M this parameter the  recursive function so this is a way that  I'm essentially building this tree we're  at the top of the tree the branching  factor is 9 at each of those 9 knows  French doctors 8 then 7 and 6 it's gonna  be a big tree if n is 10 how big is that  tree gonna be what's 10 factorial part  of me when I was a nerd we used to try  to impress people of appropriate genders  by going off saying things like 3 6 2 8  8 0 0 you can probably guess how  effective that was so 3.6 million it's  gonna be a big tree any questions about  that let's go when I check things I just  compute the sum there I start off with  the sum being the distance from 0 to the  N minus first then I go through and add  up all the pairwise things and save it  what does it mean to say that if the sum  is less than the minimum sum so far I  just copy those over change them then  sum and to solve the whole thing I do a  search of size n this is a simple but  powerful recursive program you should  all feel very comfortable at this  is it correct does it work have you is  it possible to write a program about two  dozen lines of code that works not the  first time but after you get rid of a  few syntax errors you check it how do  you make sure it works I start with n  equals three and I put three and doesn't  give me a tour well work think about it  for three three factorial  they're all the same tour that part  wasn't hard for now that's interesting  that one works too this program in fact  can work is it going to be a fast  program how long we'll take it in equals  ten how many seconds I'm sorry what fast  if I stumbled into is this intact Greek  art 303 how long will this take for an  equals ten part of me about a second  pretty cool for an equal twenty how long  will it take  a lot longer technically speaking it's  gonna take a boatload longer so what I'm  gonna do here is notice that there are  in fact four permutations you do end of  those that each totals that on this  fairly fast laptop from a few years ago  but now they're all about the same at 8  seconds it took that at nine seconds  what should be the ratio what would you  expect would be the ratio between its  time at eight and time at nine now about  a factor of nine you'd hope is 0.5 times  nine about three point point three four  yeah close enough here going down from  tenth it's four seconds 46 seconds yeah  it's going up by a factor  so here I've run all my examples I run  out to one minute of CPU time after that  I estimate if this one takes three  quarters of a minute 12 times that is  twelve minutes three quarters of that is  nine minutes for 13 as two hours how  long should 14 take ballpark yeah add a  ballpark  how long will 15 take if 14 takes today  two weeks  how long will 16 take 8 months you get  the idea are you gonna go out to 20 for  this one no are you gonna go out to 16  with this one can he just put this into  a thesis right now now the problem is  fast for really small values of n as it  becomes bigger how can you make the  program faster if you wanted to make  this program faster what would you do  what are some ideas give me some ideas  please this is performance engineering  you should know this ideas for making it  faster please  okay so you're saying just choose one  start and ignore that ignore all the  others you don't need to take each  random started fantastic a factor of n  like my friend and the grade teacher  just got a factor of n how else can you  make it faster what ideas do you have  please  by  and reject things  be greedy  follow the pig principle if it feels  good do it just local optimization we'll  get to that in a long time the boy would  that be a powerful technique other ideas  please ah parallel lies I would write  that out but the first thing I would  have to do is remember how many R's in  hell's there are in various places so  I'll write that much but we'll have a  comment on that at the end people tried  that sir unlike you Charles and I at one  point attended a real engineering school  the carnegie mellon formerly known as  CIT Cardian technology charleston  remember the tear the tear 3.14159  tangent secant cosine sine square root  cube root log of e water cooled slip  stick CIT what's a water-cooled slip  stick part of me it's a slide rule that  you run so fast it has to be  water-cooled so if you can just  overclock the machine does just spray it  with a garden hose and mcc's over the  finish line you don't care if it dies  but when it collapses so sure you can  you could faster machines and we'll talk  about that how else can you make this  faster other ideas these are all great  ideas we'll try it  let's see some ideas compiler  optimizations I just said GCC and I ran  it what should I have said instead  instead of just GCC  oh three how much difference will that  make  I used to know the answers to all these  as I was gonna turn autom ization 10%  sometimes look the fricken do fifteen  percent does turning on no three still  make it a fifteen percent difference  we'll see you could do that a faster  hardware I I did this twenty years ago I  had all that number there I'll show you  some of those numbers modify the C code  we'll talk about all those options but  let's start with compiler optimizations  with no office there  how much faster will be if I turn  optimization this is a performance  engineering class you should know that  thing doesn't matter at all it's going  to be 15% how is it going to not matter  at all how much will it matter to turn  optimization how much is a lot I know  this isn't the real engineering school  of CIT  but pretend like this is kind of a semi  one of the engineering school give me a  number for this more than fifteen  percent  do I hear more than sixteen percent I  was surprised if I enable 203 it went  from four seconds to twelve I couldn't  even time it here there wasn't enough  time here 45 seconds to 1.6 seconds I  could get real times down there  I observed ballpark here about a factor  of 25  holy tamale on a Raspberry Pi it was  only a factor of six and on other  machines it was somewhere between the  two the turn on optimization really  matters enabling that really matters  from now on I'm only going to show you  full authorization is cheating not to  but just think about that a factor of 25  how else can I make it faster  two machines back in the day I happen to  have some data laying around of running  it on a Pentium Pro - when your  megahertz nowadays I had this how much  faster will this machine be 20 years  later again pretend like you read a real  engineering school hoping to be pleased  20 times faster how do you get 20 times  faster  the clocks eat about 10 here's what I  found on this machine it went from a  factor there is about a hundred these  factors I found consistently were about  over the 20 years about his factor of  154 Moore's law what would it be if you  if you had 20 years if you doubled every  two and then that's ten doublings what  is two to the tenth a thousand so  Moore's law predicts a thousand it's  more than a factor of 20  I got a factor of a hundred and fifty  here which is close to what Moore's law  might predict but there was some slowing  down at the end I'm not a little  traumatized by this a speed-up of about  a factor of hundred and fifty where does  that come from my guess is you get about  a factor of 12 due to a faster clock  speed and another factor of 12 due to  things like wider data paths you'd have  to try to cram everything to a 16-bit  bundle you have 64 bit data paths  they're deeper pipelines more  appropriate instruction sets and  compilers to exploit those instruction  sets if oh three has enabled if both  three has not enabled sucks to be you  questions about that let's go so we have  constant factor improvements external  modern machines kernel optimization may  a factor of a hundred and fifty and a  factor of 25 there's a lot we were  starting off with that that is a good  start back in the day if you change  things from doubles to floats it got way  faster from close to N so it was faster  yet does that change make much  difference nowadays not exactly the same  run  I'm one thing that does make a  difference is this is the difference  definition of the geometric distance  since my J is the square root of the sum  of the squares of the differences that's  doing an array access a subtraction and  multiplication multiplication to Ray  accessing subtraction as a  multiplication in addition and a square  root that used to take a long time if I  replace that with table lookup it's by  it's totally now this free a sort of  table the the distance four algorithm to  is just a distance erase of ice of j  that gave me a speed-up factor of two  and a half or three back in the day that  was the speed-up factor of 25 for you as  performance engineers you have all this  intuition every piece of intuition you  have that I had that was really  appropriate ten years ago is irrelevant  now you have to go back and get models  to figure out how much each thing costs  but still it's another speed a factor of  three just by replacing this arithmetic  with the table lookup algorithm three  what we're going to do is choose the one  city to start with so we'll start at  City one will leave nine if we have a  nine element problem in that position  and just search of n minus one it  doesn't matter where you start you're  gonna go back to it so you can just  choose one to start with not a lot of  code permutations are now that distance  at each so now you've reduced n times n  factorial to induct oriole algorithm for  is I'm computing the same sum each time  is there a way to avoid computing the  same darn sum each time will carry the  sum along with you instead of  recomputing the same thing over and over  and over  start off with the sum mean 0 the  parameters now M and the distance so far  then you just add in these remaining  pieces at each point  and you solve it that way and there it's  sort of a nice piece of mathematics I  wish I had the time to analyze it I did  a spreadsheet where I said how what's  the ratio of this and it started off as  three three and a half three point six  three point six five three point seven  one three point seven one eight two  eight one eight two eight what does that  mean if something if you see a constant  three point seven one eight two eight  one eight two eight it's one plus E and  once I knew what the answer was even I  in my mathematical frailty was able to  prove that it's one plus e times n  factorial I'm not giving you the proof  but it's very cool that you run across  these things so here are the four  algorithms so far on an entirely  different semi-fast machine the run time  here are the real clock times on this  machine for 10 11 12 13 real times and  bold are major times these other times  are approximate estimates and you can  see now that for size 13 you go from  taking a fraction of an hour to taking a  third of a minute with nate's and  programs faster that's pretty cool we  feel good about this this is what we do  any questions at all we got to go faster  how do we go fast just to say precisely  for all these experiments I took one  data set and if I say that to run time  for size 15 I take the first 15 elements  of that data set for 16 I take the first  16 elements 17 so on and so forth it's  not great science I've done the  experiments where I did it on lots of  random data the trends are the same it  smooths out some of the curves but we'll  see this the times are for initial  sequence of one random set it's pretty  robust  but the problem has factorial growth the  starter factorial its dual factorial  what does that mean each factor of en  allows us to creat the problem size by  one in about the same time faster  machine and all that we can now push  into the teams  what does that mean you can take abraham  lincoln's problem and they got a tour  with this length the optimal tour looks  sort of the same on this side but it's  really different over here charles what  figure is that i've mentioned yesterday  that if you work in the traveling  salesman every instance you see turns  into a Rorschach test the bunny had  everyone see that those who are in fact  the correct answers he has a  psychologically sound human being does  anyone else want to give their Rorschach  answers a free diagnosis III absolutely  no charge I'll completely diagnose you  but the bunny the bunny hopping and the  bunny head-on are impacted two correct  answers for here but we'll see more  later so Abraham Lincoln you solve his  problem now my friend Mike Sheamus could  solve his problem did he get the optimal  tour while overhearing on a big part of  it but over here it's really sort of a  different character it's a finally  different character is it far off yeah  about a third of a percent off so his  approach was within a third of a percent  I've always worked I spent much of my  career working on approximate solutions  to DSPs those are often good enough this  algorithm you can prove that he applied  is within fifty percent in the real  world it got within a third of a percent  Wow but now we can go out and we can  solve the whole problem in sixteen hours  if you were writing the thesis and you  happen to do this would it be worthwhile  now right this distinct 16 hours of CPU  time into this you're gonna go away for  a weekend to sure leave your machine  running at the time Charles when we had  one big computer for 60 or 70 people in  the department could we  dreamt about using 16 hours for that on  the very border if you made it a really  mellow background process it might  finish in a week or three all of these  things change this the computers get  faster they get more available you can  devote a machine to is it to dump 16  hours down this but can we make it  faster yet can we ever analyze say all  permutations of a deck of cards how many  permutations are there of a deck of  cards if you take out those Joker's  what's that number  yeah what will one with 15 zeros after  it it's a big number 2 to the 50 52  factorial I want to teach you how big 52  factorial is people say that problems  growing exponentially what does that  mean it's quick it's what the people  usually mean by it in mathematics it's  some constant to the N for some defined  time period n factorial growth is  factorial growth exponential growth why  not why isn't it back to exponential  it's more than exponential it's super  exponential we'll talk about the details  here by Sterling's approximation you  have seen in other classes that log that  it log of n factorial is n log n minus n  plus log n for the natural log the log  base 2 of n factorial is about n log n  minus one point three eight six seven  where have you seen this number before  one point in log n minus 1 and then  algorithms class if you did a lower  bound on a decision tree model of  sorting there were intact Oriole leaves  to Swartz a sort algorithm must take at  least as much time so that gives you  that bound and he merge sort is n log n  minus n so you're really narrow where  else have you seen one point three eight  six n that's the runtime of quicksort  all these things are coming back  together here because it's the natural  log of e I'm sorry the log base two of e  so in factorial is not 2 to the N is 2  to the n log n it's about in to the end  it's faster than any exponential  function  how big is 52 factorial  you guessed 10 to the 15th was that okay  if we see here it's going to be  something like 2 to the n log n in is 52  log of 52 is about 6 that's 2 to the the  300 but it was there's a minus in term  maybe 2 to the 250 it's about 2 to the  225 which is 10 to the 67th  that's a big number how big is it let me  put it in everyday terms try this after  class a set a timer to count down 52  factorial nanoseconds 10 to the 67th  stand on the equator watch out for where  you are and take one step forward every  million years don't rush into this I  don't want you to get a hyper about this  eventually when you circle the Earth's  one--the  take a drop of water from the Pacific  Ocean and keep on going okay be careful  about this but this is an experiment  you're you're nerds it's okay  when the Pacific Ocean is empty at that  point lay a sheet of paper down refill  the ocean and carry on now keep on doing  that when you're stacking paper reaches  to the moon  check the timer you're almost done this  is how a big ten to the fifty second is  the age of the universe so far is about  10 to the 26 nanoseconds it's ten to the  fifty second is a long time can we ever  solve a problem if we look at all ten to  the fifty second options what do we have  to do instead part of me a lot in  computing okay that's great and I have a  really cool bridge across this river out  here that I'll sell you after class  let's talk about that okay is there a  nice quantum approach to this problem  maybe I mean you could actually phrase  this as an optimization problem where  you can maybe get some mileage out of  that but we'll see so wonder purchase  quantum computing what's another  approach what are we going to have to do  to make our program is for mount this  obstacle please  part of me we're gonna have to limit our  search space we're gonna have to prune  the search space that's the idea let's  try it  here's a cool problem I was at a  ceremony a few weeks ago a friend of  mine said here's this cool problem that  his daughter to spot home from high  school how do you solve it  find all permutations of the 10 integer  or the 9 integers 1 through n such that  each initial substring of length m is  divisible by M so the whole darn thing  is divisible by 9 is any permutation of  the integers 1 2 9 to symbol by 9 well  they all sum up to number 12 old 9 he  worked that as it divisible are the  first eight characters divisible by 8  now let's start with an easy one if you  were doing it for size 3 3 2 1 works is  3 2 1 divisible by 3 it's 32 2 visible  by 2 it's 3 differ by one thinking it  works is 1 3 2 divisible by 3  yeah it's 13 days of y2 yeah that  doesn't work so we're gonna try to solve  this problem my friend Greg Conti a  really great computer security guy gave  me this problem how do you solve it how  would you solve this problem if this  high school kid says here's a problem I  brought home from school how do I solve  it what would you do  ideas I'm sorry please  or actually just  use  great so their their two main approaches  one is write a program so you can either  think or you could compute who here who  in this room enjoys writing programs who  enjoys thinking well that's an easy call  what's the right approach here well yes  the right answer is you think for a  while if you solve it in the first three  minutes  don't write a program they spend much  more than five minutes on it let's write  a program see we'll learn from the  program we'll go back and forth they  never think when you should compute  never compute what you should think how  do you know which one to do try each see  which one gets to further faster if you  write a program for this what are the  basic structures you have to deal with  you have to deal with nine digit strings  that are also nine digit numbers what's  a good language for dealing with that  what would you if you had to write a  program to do this what language would  you choose we'll say how do you generate  all intact oriole permutations of the  string well I hope you can see this  here's the way that I chose to do it I  chose to have a recursive procedure  search and I'm gonna have right be the  part that's already fixed left be the  part that you're gonna vary I couldn't  have done it the other way but I'll  choose to do it this way I start with  left equals that right equals that I end  when the left is empty besides weaker  down just like we've been doing so far  but I'm going to do that with with  strings instead and the if I get to the  call search of five six of three five  six with 41:9 seven eight these are all  fixed I'll take each one of these in  turn three five and six put it into here  so I'll call search of 56 without search  of 36 without search of 35 but that  everyone see how that works how long  will the code be and in your favorite  language here's the code in my favorite  language that's it has anyone here ever  used the awk programming language  written by a whole Weinberger and Qurna  hand they observe  naming a language after the initials of  the authors shows a certain paucity of  imagination but it works so a function  search of left right that if left equals  zero is no I'll check it otherwise what  will I do here the details don't matter  for I equals 1 up to the length of the  left hand side of the string search the  substring at the left starting at 1  going for I minus 1 with concatenated  with the substring of the left starting  at I plus 1 and then take the substring  in the middle put it out in front of the  right do that for all I values any  questions about that the details don't  matter it's not a big program if I do  this and at the end probably will 1/2  length if the substring of the right mod  I is nonzero then return if it's not  that you've printed out if I run this  program how long ballpark with this  program take 4 9 factorial ballpark what  was your answer before a second great  well will recycle that reduce reuse  recycle well recycle the answers this  tip I called originally with that string  it takes about three seconds and it  found that there was searched all nine  factorial three six two eight eight zero  362,000 strings and found only one  string there that matches that oops  are these divisible by 9 well they sum  to multiple of nine sure is this thing  that ends in 72 divisible by 8 yeah that  works seven and I'm not going to bother  with all the way down is 38 divisible by  2 its 381 divisible by three this one  works that's a pretty cool problem for a  high school afternoon  if three seconds fast enough yeah  in the trade-off of thinking and  programming right the darn program  you're done is it's cool  if you wanted to make it faster how  could you make it faster I've that's  what this course is all about always  think about how you can make things  faster please you just stop searching  [Music]  how early can you stop searching that's  great  so you could get consequent actor speed  ups like don't check for divisibility by  one at the end you can change language  all that but those are never going to  matter the big win is gonna come from  pruning the search how can you put the  search what any winning string must have  some properties of this string what are  some properties that string has it you  can check for early please the eighth  position has to be a multiple of two  furthermore if you really think about it  you could get more than that has to be a  blues visible by four and it's also an  even number has to be in the eighth  position anywhere else gonna need an  even number this position has to be even  that has to be even that has to be even  that has to be even in general what's  the general rule  every even position has to contain an  even number there are four even numbers  there are five odd numbers  what other rule might you come up with  okay every odd position has to be an odd  number and in particular the fifth  position has to be a five so those are a  few rules even digits and even positions  all digits and opposition's digit five  in position five three simple rules you  can test those easily the code is pretty  straightforward will that shrink the  size to the search space must at all  really how big was the search space  before nine for the first one now how  big is a search space for the first if  you just had the five rule the three  rules evens going evens odds and odds  and five in the middle how many choices  do you have for the first one four  choices for the second one you have it  can't be a five it has to be an odd  number not a five you have a four so  it's four by four times three times  three times one times two times two  times one times everyone see that we've  researched reduce the size in the search  space from a third of a million to half  a thousand isn't there gonna be a lot of  hassle of code that I'm gonna take like  a major software development effort to  code that well yeah if you define that  as a major software development effort  if the parity of the string length is  equal to the parity of the digit and its  then you can continue if you don't have  these things you can't continue three  lines of code allow you to do this  that's the story factorial grows quickly  you can never visit the entire search  space the key to speed is pruning the  search we're doing just a baby  branch-and-bound it's called some fancy  algorithms can begin  a little code that's our break we've  learned a couple things we ready to go  back to the to the fray any questions  about this diversion before we go back  to the TSP these are important lessons  we'll try to apply them now I got great  advice yesterday from people about how  to do this and I seem to have skipped  okay here it is I've got it how do we  prune our search there we had these  conditions how can we prune this search  how can I make the program faster what's  the way I can stop doing the search  simplest way don't keep doing what  doesn't work if the some that you have  so far is greater than the minimum some  by adding more to it are you ever going  to make it less what can you do  you can stop the search right there is  the reason looking algorithm going to be  faster maybe it's a trade-off I'm doing  more work which takes some time but I  might be able to prune the search space  the question is is this benefit worth  this cost what do you think well on the  the same machine algorithm for size 12  took point 6 seconds now it's a factor  of 60 faster factor of 40 faster a  factor of a hundred faster just by if it  doesn't work if you've already screwed  up this don't you - who doesn't work  that makes the thing a whole lot faster  everyone see that that that's the first  big win can we do even better than that  is there any way of stopping a search  with more information other than oops  I've already gone too far please  wait command boys who speak you speak  loudly  that's a really powerful idea that  helden carp use to reduce it from n  factorial times N squared - to the end  time we'll get to that that that's  really powerful but now we're looking  for something not quite that  sophisticated but that's a great idea  can I somehow prune the search if a sum  plus a lower bound on the remaining  cities is greater than the minimum  something because I what kind of lower  bound could I get well I could compute a  TSP path to them that's really powerful  that'll give me a really good bound but  it's really expensive to compute so I  could if this is the city I've done so  far I could compute a TSP path to the  rest which might in this case looks like  this and hook it up that's are going to  be a really powerful heuristic but it's  going to be really expensive to compute  on the other hand I could take just the  distance between two random points I'm  gonna choose this point and this point I  happened to get the diameter of the set  and that's the lower bound it's gonna be  at least that long which and it's really  cheap to compute but is it very  effective yeah so the first choice is  affected but too expensive the second  point is really inexpensive but not very  effective  I could also compute the nearest  neighbor of each city from this city if  I just compute its nearest neighbor  among here see it's that this one is  that that one has its own nearest  neighbor I could compute these distances  and that's pretty inexpensive to compute  and it's a pretty good lower bound that  would work who here knows what a minimum  spanning tree is good what I'll do here  is I'll take here a minimum spanning  tree in cities a tree is n minus 1 edges  this tree is in minus one edges this is  a spanning tree because it touches it  connects all cities and furthermore does  a minimum spanning tree because of all  spanning trees this one has the minimum  total distance now the tour is going to  be less or greater in distance than the  minimum spanning tree why is that if I  get a tour of this I can just knock out  the longest edge and that now becomes a  minimum spanning tree so the minimum  spanning tree is a pretty good bound a  lower bound it's cheap to compute who  here has ever seen an algorithm for  computing minimum spanning trees good  good some of you are awaking some other  classes what are the odds of that what  are the amazing confidence so what we'll  do is say now that a better lower bound  is T add V and the minimum spanning tree  the remaining points so I change this  program to if some plus the MST distance  and now I'm going to do a trick I'm  going to use word parallelism I'm going  to have the representation of the subset  of the cities as a mask bit mask in  which if the appropriate city is all on  the bid is turned on if otherwise it's  turned off and I just or bits into it  and say if I compute the minimum  spanning tree of this set I can cut the  search and return and then I just  compute the MST and bring this along  with me of turning things off and on in  the bitmask  as I go down pretty straightforward how  much code will it cost it to compute a  minimum spanning tree ballpark  yeah about that many lines of code this  is the prim Dijkstra method it takes  quadratic time for computing an MST of  endpoints it takes n squared time it's  quite simple you can do it in evoke log  be edge of time but this is a simple  code it's pretty straightforward  will this make the program run slower or  faster  what would the argument to be that it  might run slower  holy-moly at every node I'm computing an  MST that takes a long time to Marwin  slower  what's the argument to be that it might  run faster yeah but I'm getting a much  more powerful pruning is it worth it I  should play out that I'm only showing  the winds here to you when I redid this  myself I went down a few wrong paths I  wish I would have documented them better  now but I might go back and see if I can  find them that would be a good thing but  here it is it used to take 17 seconds  now it takes or 4 seconds now it takes 0  you move like algorithms to take a 0  seconds that's you you like to live in  the rounding error for point forty two  point two down here this program is not  only faster it's a boatload faster and  so now we can go out and it's and notice  here that you as you go out the times  usually get bigger but they're a bumpy  from 2.4 seconds 2.7 seconds to 1.8  seconds it's because you're doing that  one thing it's just the matter of the  geometry the times that were originally  really smooth now turned bumpy I've done  experiments where I do ten different  data sets randomly drawn at each one and  it's a nice smooth line but I miss doing  it here to be easy before you go out to  size 17 now we can go out to size 30 Wow  how cool is that that's pretty powerful  can I make this please that's absolutely  true and I've tried this both on random  point sets I've parted on distance  matrices I've tried it on points where  they're randomly distributed around the  perimeter of a circle and so this could  be a lot of time almost always it's  pretty effective again if I had more  time I talked about it but in fact we're  going to go until 3:45 Charles's will  355 when the big hand is on the 11 Oh  sucks to be you  i profile this bad boy and it shows that  most of the time is in building minimum  spanning trees your fear that it might  take a long time there might in the  goats low it has a basis that's where  all the time is going how can I reduce  the time spent in building minimum  spanning trees as I search this place I  could do some incremental in standing  trees because they change a lot and so  there are several responses one is  whenever you have you're building  something over again rather than  building it from scratch see if you can  do an incremental algorithm where you  just change one bit of the minimum  spanning tree if I just add one edge  into the graph always try an incremental  algorithm that's cool  that's one sophisticated approach what  is one what was another pretty idiot  simple approach whenever you compute  something over and over again what can  you do to reduce the time spent  computing it store it do I ever compute  the same MST over and over again I don't  know I think maybe it's worth a try  so what I'll do is return if cashing a  store rather than recompute cash and  musty distances rather than recomputing  them the code looks like this the new  mask is that if the MST distance array  is less than zero it you neutralized  everything to zero here I'm just gonna  store them all in a state table of size  two to the end I can just do direct  indexing if it's less than zero computer  telling the value if some plus that  return not much code but do you really  want to store to blast it out and to use  this lazy I'm using lazy evaluation at  this table here only when I need it do I  tell on a value that's not critically  effective rather than storing all two to  the end tables what can I do instead  what's our favorite data structure for  storing stuff hash table a cash via hash  so the key to happiness you can write  that down to store them in a hash table  if some policy MST distance lookup  oh and I have to implement a hash table  now how much code is acting to be  ballpark what does it cost to build a  hash table roughly come on yeah about  that many lines so just go down the hash  table if you find it return its  otherwise make a new node compute the  distance for then there are settle the  values and you're done is it going to be  faster oh we'll see who reads xkcd on a  regular basis the rest of you are bad  bad bad people and you should feel very  guilty until you go to xkcd comm and  start reading it on a regular basis can  i I mean like wow this is too deep  psychological insight so in one lecture  for no additional fee sir by chaining  yes  that makes sure that it's the value  associated with that is a great question  and the answer is left as an exercise  for the listener so you got about 20  minutes Charles it would be yeah and  it's well worth the try all of these  things are empirical questions one thing  that's really important to learn as a  performance engineer is that your  intuition is almost always wrong I'll  always try the experiment to see it's a  great question  well I get home I'll actually oh when I  leave here I'm going to go up to try to  climb Mount Monadnock who here's ever  climbed Mount Monadnock yeah I finished  climbing all 115 4000 foot peaks in the  northeastern US last year I've never  climbed a dad knock I'm really here to  give it a try tomorrow xkcd brute force  in factorial 2 held carton any  programming algorithm uses the grown-up  version of dynamic programming for N  squared 2 to the N but even better  algorithm six looks like that if I cache  the tsps does it have to be faster no is  it faster by about a factor of 15 there  by about a factor of 25 there 26 there  you can go out now much further 6 & 8 so  we've done that we've is there any other  way to make this program faster  we've pruned the search like crazy any  other way to make it faster please  I forget what happens to 39 let's see at  39 it went over a minute like I said  this thing goes up and down guess it  just had some weird bumps in the search  space that's something else the first  algorithm is completely predictable the  other albums you have to get more and  more into analysis and now the tines go  up and down there's a trend and  basically I'm taking an exponent and I'm  lowering I turned it from super  exponential to exponential and that I'm  beating down on the exponent right now  can you make this run faster what we're  gonna do is take this idea of a greedy  search I've been a smarter searching  better than a random order I'm gonna do  a better starting tour and what I'm  going to do is always at each point sort  the points to look at the nearest one to  the current one first start with a  random one then for the next one always  look at the nearest point first in the  second nearest the 3rd nearest etc so  I'll go in that order  - should make the search smarter and  that shouldn't guide me rather quickly  to the initial starting - rather than  just a random tour I'll have a good one  that will give me a better pruning of  the search space Labatt me make a  difference while I have to include a  sort I'll get two birds with one  modification by a really dumb insertion  sort which takes about in the lines of  code I'll visit the nearest 30 city  first and others in order if I do that  here it's a factor of two there it's a  factor of eight a factor of four but it  seems to work it gives you some so you  go out especially I can now go out  further  oops I lied I didn't stop my search it  does 60 seconds there but I can now go  up further and it seems to be a lot  faster so in 1997 twenty years ago I was  really happy to get out 230 the question  now is in twenty more years how much  bigger can I go if I just depend on  Moore's law alone in twenty years a  factor of a thousand  at 30 30 times 31 times 32 that's the  factor I can go up by Moore's law with a  dumb inductor algorithm would give me  two more cities at this size in 20 years  can I get from 30 on to anything  interesting by combining Moore's law and  compiler technology and all the  algorithms how far can I go well I was  going to give a talk at lehigh and so I  could go out in under a minute I could  go to the 45 city tour  Charles answered this yesterday so so he  is completely clear Rorschach test who's  willing to go out what do you see there  dancing doggy that that was - dancing  dog yeah I like that a lot that's  obvious answer but Charles and this  shows that profound the profound mind  professor license and what is this okay  so I any Freudians  you feel free to go to town on that one  45:22 is pretty cool dancing doggy  how far can it go I got up to 45 in  under a minute 46 I broke my rule of  this I I went over the minute boundary  this was my Thanksgiving 2016 cycle test  I was just going hog-wild I was willing  to spend the whole I had to give a I was  doing this Wednesday night I had to give  a lecture on Monday a hundred hours of  CPU time how far can I go  47 yeah yikes factor 5 when do I think  when do I run for should I go back and  work it's Jeff teach it wouldn't it be  sweet to be able to go out to 52  factorial wouldn't that be cool 48  that's not that that's looking pretty  good there actually for all ouch-ouch  that's gonna take so that that's about  two hours right there but 50 oh I my  seat you know that the the turkey was  smellin good but  fifty-one and can I get that 52 will it  make it well I have to go back to my  three hours and seven minutes by  combining all these things we're able to  go out to something that is just obscene  52 is obscenely huge we're able to get  out there by a combination of all of  these things of some really simple  performance engineering techniques if  you're going to work on a real TSP read  the literature study that I hope you  even come across some things that I've  written about approximation algorithms  but if you really need to forget the  approximation algorithms kind of true -  or there's a huge literature I haven't  told you any of that everything that  I've done here are things that you as a  person who has completed this class  should be able to do all these things  are well within your scope of practice  as we say you will not be sued for  malpractice how much code is the final  thing about that much you build an MST I  had a hash table  Charles points out you could get the you  could nuke three or four of those lines  you have to sort here altogether about  160 lines where have we been  we started we can get out to 11 store  the distances after 12 fix the starting  city that was the big one  accumulate doesn't along the way these  were all good but then by pruning the  search we started making the big things  add the MST store that isn't some hash  table this is the cities in a greedy  algorithm each one of these gave us more  and more and more power as we went out  there - were finally able to go out  pretty far there are a lot of things you  can do of parallelism faster machines  more code tuning better hashing that  that malloc is just begging to be  removed better proving it better  starting tore better bounds I can take  the MST length plus the nearest that's  why I do this MST plus the nearest  neighbor to each of the ends I can get  that would that make a big difference  empirical questions easy to find out I  can I'd move by pruning tests earlier  better sorting the  is really cool can i maybe just swart  once for each sitting to get that sort  of this then go through that precomputed  sort and select the things in order is  that going to be a win in this context  the main ideas here are caching  precomputing storing this avoiding the  work can I change that N squared  algorithm to just a linear time  selection all of these things are really  fun to look at I've tried to tell you  about incremental software development I  started off with around 3040 lines of  code it grew to 160 but all together all  the versions versions come to about two  six new lines of code you've now seen  more than you need for one life about  recursive generation it's a surprisingly  powerful technique if you ever need to  use it no excuses now you're obligated  to build immediately the storm pre  computed results partial sums early  cut-offs algorithms and data structures  these are things that sound fancy in  your algorithms class but you just pull  not when you need them vector strings  arrays and bit vectors minimum spanning  trees hash tables insertion sort it's  easy it's a dozen lines of code here two  dozen lines of code there  I believe that Charles may have  mentioned earlier that I wrote a book  and 1982 about code tuning at the time  you did these and in the smaller  programs now compilers do all that for  you but these ideas some of these ideas  still apply store free computed results  rather than common sub-expression  elimination and expression you now put  inner point distances in a matrix or a  table of MST lengths a lazy evaluation  you compute the N squared distances  eagerly but only the MST is that you  need don't bother computing them all  that's essentially what held Karp does  schwarzer greedy monotone functions  reordering tests word parallelism these  are the things that you as performance  engineers can do quite readily  I have a lot of tools behind the scenes  I wish I could come back and give you  another hour about how I really did this  with me and now  and the tools that I use I had a driver  to make experiments easy a whole bunch  of profilers where is the time we'd be  going here what should I focus on cost  models that allowed me to estimate those  how much does an MST cost a spreadsheet  was my lab notebook for graphs to  performance all sorts of curve fitting  but these are the main things I wanted  to talk about the big hand is getting  about nine minutes away from the eleven  professor leiserson is there anything  else that these fine young semi  humanoids need to know about this  material I don't know what point one of  my first exposures to MIT was when I had  Donovan as a software systems book and  it was dedicated to six point five one  graduate students I saw that and I  thought that bastard I'm sure that the  six students really worked hard on it  but to say that the the seventh student  worked only a little much more over  halfway and then to be so precise that's  just cruel well what would have a  son-of-a-bitch that guy might be so I  don't know what project four is but is  it wiser chest spiny oh great I know  what that is so what things have you  used any of these techniques to do ever  prune searches to do Everest war results  what did you do in project four  you're delegating this that's a natural  leader right there okay but speak up so  all of them can hear a place is there  anyone here from the state of California  I was born in California when you hear  alpha-beta  apart from the search what do you think  of there's a grocery store they were  called alpha beta and when Knuth wrote a  paper in that topic he went out and  bought a box of alpha beta prunes that  he had in his desk so he was an expert  in two senses on alpha beta pruning so  good other techniques please  [Music]  great did you resolve collisions at all  or did you just have one element there  with a key how did you address the  problem that the Charles mentioned of  what kind of hashing to use other  techniques yeah that's a classic example  of the fastest way to compute is not to  compute at all in general in life no  problem is so big that it can't be run  away from the these things about a  boarding work and being lazy are  certainly models for organizing your own  life so that lazy evaluation really  works in the real world other questions  without a question or a random have seen  your hand gesture  please oh that's a great question I  worked in this problem a lot in the  early 1990s with my colleague David  Johnson who literally wrote the book on  NP completeness an MIT PhD guy we were  really happy we're in at the time in a  couple of hours of CPU time we could  solve a hundred thousand city problems  to within a few percent we were able to  solve million city problems in a day of  CPU time to within a few percent and we  were ecstatic that that was really big  so we could go out that big to within a  few percent if we worked really really  hard we can get ten thousand problems  counted within 1/2 percent but if you  want to go all the way to have not only  the optimal solution but it proof that  it's optimal for a while people bragged  about we finally solved a problem this  will let you see about what it was done  we solved the problem of all 48 state  capitals so for a while that was the  state of the art and then that number  has crept over time and now you can get  exact solutions to some famous problems  into the tens of thousands by using lots  and lots of really clever searching that  branching down with really clever lower  bounds to guide it up and you at one  point get a tour and you can make like  that tour but then you get a proof of a  lower bound along with it to do that hey  oh man I want to let you know that  they're actually now 50 states in the  Union No  what time did this happen you can tell  that I am much much much older than  Charles and he never lets me hear the  end of it I trusted the rest of you this  is like the third free deep psychology  insight is be kind to old people ignore  the example that the kid over there sets  and show some class the respective might  to me and my fellow geezers yeah we were  both born in 1953 but I was born in the  good part of 1952 in particular I was  born before Her Majesty the Queen of  England assumed the throne okay can you  make the same claim I cannot make the  same thing I'm sorry he can but only cuz  he's a sneaky bastard can you make it to  fillet it's the question I should have  asked other questions this class can be  very important like I said I spent the  past almost half century as a working  computer programmer the majority about  the thing I've done most is performance  engineering it's really to do a number  of really interesting things I've been  able to dabble in all sorts of  computational systems ranging from  automated gerrymandering every time you  make a telephone call in this country if  it's say a call from inside an  institution like a hospital or a  university it uses some code that I  wrote some performance things if you  make a long-distance call it uses code  that I wrote if you've ever used  something called Google internet search  or match or maps or stocks or anything  else that uses and algorithms I've done  it's incredibly satisfying it's been a  very very fulfilling way for me to spend  a big chunk of my life  I am grateful it's allowed me to make  friends whom I've known for almost half  a century and who are wonderful dear  people and it's been a great way for my  life I hope the performance engineering  is as good to you as it has been to me  anything else professor  thank you very much John thank you  [Applause]

2
00:00:03,189 --> 00:00:05,769
the following content is provided under  a Creative Commons license your support  will help MIT OpenCourseWare continue to  offer high quality educational resources  for free  to make a donation or to view additional  materials from hundreds of MIT courses  visit MIT opencourseware at ocw.mit.edu  it is my great pleasure to welcome John  Bentley now retired from Bell Labs John  was my PhD thesis supervisor at Carnegie  Mellon I actually had to supervisor the  other one was HT Kong who is now at  Harvard I guess people flee Carnegie  Mellon like the plague or something so  so John is as you know because you've  studied some of his work is a pioneer in  software performance engineering and  he's going to talk today about a  particularly neat piece of algorithmic  engineering sets that centers around the  so called traveling salesperson problem  which is an NP hard problem and P  complete problem in fact and so without  further ado John why don't you tell us  what you got to say as Charles mentioned  I want to talk with you I want to tell  you a story about a cool problem this is  a problem that I first heard when I was  a young nerd not much older than you  little this little pile of nerds in  front of me in high school that the  traveling salesperson problem who here  has heard of the TSP at some point I  heard about this in high school one of  the things you read about in the math  books and a few years later I had a  chance to work on it in 1980 I was doing  some consulting and I said well what you  need to do is solve a TSP then I went  home and realized that all this stuff  that I had learned about it was sort of  relevant but it didn't solve the problem  so I started working on it then Michael  or our colleague christos papadimitriou  who's been at Berkeley for a long time  after being in a lot of other places  once told me the TSP is not a problem it  is an addiction so I've been hooked for  coming up on 40 years now and I want to  tell you one story about a really cool  program I wrote  I've been paid to be a computer  programmer for coming up on 50 years  I've been doing it for 48 years now this  is probably the most fun the the coolest  program I've written over a couple day  period I wanted hi yes story start off  with what recursive generation is then  the TSP what it is then I'll start with  one program and we'll make it faster and  faster and faster  again I spent my whole life squeezing  performance this is the biggest squeeze  ever and in some principles behind that  we'll start though with how do you  enumerate all the elements in a set if I  want to count numerate the guys between  one and a hundred I just count that's  the big deal but how can I  for instance enumerate all subsets of  the set from the integers from 1 to 5  how many subsets are there I've  introduced from 1 to 5 part of me 2 to  the 5 32 but how do you say which ones  they are how do you go through and count  them well you have to decide how you  represented you you guys know all about  set representations we'll stick with  vectors to the time being an iterative  solution is you just count 0 1 2 3 4 5  up to 31 that's pretty easy but what  does it mean to count what does it mean  to go from one integer to the next how  do you go from a given integer to the  next one what what's the rule for that  it's pretty easy actually you just scan  over all the zeros turning that you  start at the right-hand side least  significant digit scan over all the  zeros turn to 100 I lied to you I scan  over all the ones turning them to zero  until you get to the first zero and then  you turn that to a one so this one goes  to one zero this one goes to one one  this one goes that one becomes zero that  one becomes zero then it becomes zero  zero one zero zero so a pretty easy  with them you could do it that way I  just scan over all the ones turn them to  zeros take that person we flip it around  but that doesn't generalize nicely well  we're gonna see a method generalizes  very nicely this is a recursive solution  to enumerate all to the N subsets of a  set asides in and the answer is this all  sets of size M is just put a zero at  this end enumerate all sets a size n  minus one how many of these will there  be two to the M minus one how many of  those 2 to the M minus one or do they  add up to 2 to the M but all of these  have a zero at that end and one at that  end everyone see that recursive sketch  of how that works here's the example up  here you have the zeros at this end and  you pull it out you have the one at that  and you fill that out if you do that you  notice that in fact we're just counting  backwards 0 0 0 0 0 1 0 1 0 3 4 5 6 7  that's the algorithm and the cool thing  is the code is really simple I could  probably write a program like that in  most languages and get it correct so if  N equals 0 generate all subsets of size  M just visit the current one you have a  pointer going down the array otherwise  set the rightmost bit to 0 generate all  substances recursively it set it to 1 do  it again recursively that's a starting  program if you understand this  everything else is going to be pretty  straightforward if you don't please  speak up one thing that you people have  suffered the tragedy of 14 or 15 or 16  years of educational system that have  sort of beaten the creativity out of you  and and you're afraid to speak up so  even if something even if I'm up here  spouting total [ __ ] you'll ignore  that fact and just sort of politely  stare at me an odd but this is important  I want  understand this ignored him to stay on  this speak now or forever hold it anyone  have any questions please please  [Music]  I'm sorry why do we set P to the so here  first I could go out to the extreme  right most and I set it to zero then I  recursively fill those in then I change  it from a zero to a one there and I fill  all those in so this is a program that  we'll go through and as it enumerates a  subset it will call the visit procedure  a total of two to the M times and it  comes down to the bottom of the  recursion thank you great question any  other questions about how this works  okay welcome back to this the traveling  salesperson problem I apologize I will  really try to say the traveling  salesperson problem but I will slip  because I was raised with us being the  Traveling Salesman problem no  connotations no intentionality they are  just senility galloping along it's a  cool problem Abraham Lincoln faced this  very problem in the years 1847 1853 when  he everyone here has heard of circuit  courts why do they call them circuit  courts because the court used to go out  and ride a circuit to go to a whole  bunch of cities now people in the cities  come to the court but back in the day  and 1847 1853 Lincoln and all of his  homies would hop on their horses judge  defense lawyers prosecutors and go  around and ride the circuit here and so  this is the actual route that they rode  where they wanted to do this effectively  it would be really stupid to start here  in Springfield and go over there then to  come back here then to go over there  back and forth what they did was try to  find a circuit that minimized the total  amount of distance traveled that is the  traveling salesperson problem were given  a set of n cities it might be a general  graph these happen to be in the plane  but you really helicopter service was  really bad in those days so they didn't  fly directly point-to-point whether they  stayed on roads what really matters here  is a graph and better than here I'm  going to speak at this everything I say  will be true for a graph it'll  true for her geometry I'll be sloppy  about that  we'll see interfaces how how you handle  both but just cut me some slack for that  I have actually phases myself when I  worked on a system where we had a big  mechanical plotter and we'd wanted to  draw these beautiful maps where the naps  could fill in dots they happen to be  precincts some of them were red some of  them were blue and you wanted to draw  all the red dots first and go around  here and impact the plotter would draw  this red dot then that red dot then this  one then that one the plotter took an  hour to draw the map  I was consulted on this aha you have a  traveling salesperson problem I went  down i reduced the length to about one  tenth of the original length if it were  took an hour before how long would it  take now well it took about half an hour  and the reason is that the plotter took  about half of its time moving around  about 30 minutes moving around and about  30 minutes just drawing the symbols I  didn't reduce the time drawing the  symbols at all but I reduce the time  moving things around from about 30  minutes to about 3 minutes  that was still a big difference so I  faced there when I worked at Bell Labs  we had drills that would go around laser  drills were on printed circuit boards to  drill holes they wanted to move it that  way I talked to people at General Motors  at one point on any day they might have  a thousand cars go through an assembly  line some of the cars are red some are  white some are Green's more yellow you  have to change the paint some of them  have v6 some of them have v8 some of  them are two-door some of them are four  doors in what order you want to build  those cars well every time you change  one part of the car you have to change  the line and what you want to do is  examine as it were all in factorial  permutations put in the cars through and  choose the one that involves the minimum  amount of change and that's the change  from one car to another is a  well-defined function everyone see how  that weird TSP isn't active TSP so all  these are cool problems further  or as a computer scientist it's the  prototypical problem it's the the e.coli  of algorithmic problems it's it was  literally one of the first problems to  be proven to be np-hard  I held Karp gave a polynomial time  algorithm for it  there are approximation algorithms of  this kernel and given heuristics it's a  really famous problem it's worth  studying but here is what really  happened to me here's why I'm standing  in front of you today talking about this  my friend Mike Sheamus in his 1978 PhD  thesis on computational geometry talked  about a number of problems one of them  was the TSP and he shows us and he gives  an example of this tour he says here's a  set of sixteen points here's a tour  through of them as here's the traveling  salesperson to her through them and then  he says in a footnote in fact I'm not  sure if it's a really optimal tour I  applied a heuristic several times I'm  not positive it's the shortest tour if  you wrote a thesis it would be sort of  nice to to know what's going on there  can you solve a problem that was this  tiny little 16 element problem 16 points  in the plane can you really figure out  what the TSP is to that at the time my  colleague or our colleague a really  smart guy couldn't do it it was  computationally beyond the bounds for  him well in 1997 I came back to this and  I really wondered is it possible now  computers are a whole lot faster in the  20 years we were talking about that  earlier today 20 years computers got  faster a lot of things got better have  things change enough so I can write a  quick little program to solve this I  don't know we'll see I did that I talked  about it I gave a talk at Lehigh  University 20 years ago they liked that  they incorporated it into an algorithms  class the same professor gave it time  and time and time  in eventually he retired they asked me  to come over and give this talk to them  I can't give a talk about 20 year old  material that's the computer science  doesn't work that way  so I coded things and I wanted to see  how things changed in two years so this  talk is about a lot of things but  especially it's about how has  performance changed in 40 years so  that's one of the reasons we were one of  the things we were talking about earlier  today I could give a bunch of titles  this talk for you the title I give is a  sampler performance engineering it could  be next week I'll give it at Lehigh this  is their final class in one of their  final classes and algorithms and data  structures I'm gonna try to tie  everything they learned together  it could be into all this other things  implementing algorithms a lot on  recursive generation applying algorithms  really Charles is a fancy dancy academic  he's a professor at the Massachusetts  Institute of Technology I'm just a poor  dumb computer programmer but boy this is  a fun program what it is not is it's not  state-of-the-art ESP algorithms people  study the problem for well over a  century they have beautiful algorithms I  am NOT going to tell you about any of  those algorithms for the simple reason  that I don't know them I could look him  up in books but I've never read them the  fancy state-of-the-art algorithms and  I'm also going to show you again in  cancer I could analyze it I've analyzed  much of these if I had another hour or  three I could do the analysis but I  can't so I'm just going to do the show  you some anecdotal speeds without  reading the analysis let's talk about  some programs a simple C program max in  it's a maximum number that N and it's  going to be in the number of cities I'm  going to have a permutation vector where  if I have the tour going from city one  to seven to three to four it says 1 7 3  4 the distance between cities is going  to be given by a distance function  there's this distance D of IJ the  distance from city to city J here's the  first algorithm what I'm going to do is  generate all in  toriel permutations look at them and  find the best one it's not rocket  science the way I'm gonna do this is a  recursive function where I happen I  could have done it from left to right I  am a C programmer I always count down  towards zero so I'm gonna count down  that way where all these cities are  already fixed I'm going to print these  here's the program to search for em all  these have already been fixed what I'm  going to do is if M equals one then I  check it otherwise for I equals zero up  to M for each value from zero to minus 1  I take the I element I swap it swap  three seven takes the third and seven  positions and swaps them I swapped that  to the final thing I call it recursively  I didn't swap it back to leave it in  exactly the same state I found it and I  continue so Jordans going to generate  first all nine permutate put all my  digits in the last position then for  each one of those I'll put all eight  digits in the last position and going  down this is really interesting  important and subtle if you don't follow  this part it's going to be difficult  are there any questions at all about  this have I lied to you yet about this  you're honest enough to tell me if I  have thank you anyone else  I'm sorry please so so far as I recur  down with SM moves down all these are  fixed so I'm going to fix these things  and then I'm gonna take care of all  these later so originally I'm going to  have this array v-0 if I have a nine  3tsp it'll be 0 into 2 4 6 7 8 9 and  first I put 0 in the end and do the rest  and I put 1 in the end to up 9 in the  end and do the and recur down but as the  program is progressing if you stop the  program at any time and look at a glance  of the program you can see that given  the value of M this parameter the  recursive function so this is a way that  I'm essentially building this tree we're  at the top of the tree the branching  factor is 9 at each of those 9 knows  French doctors 8 then 7 and 6 it's gonna  be a big tree if n is 10 how big is that  tree gonna be what's 10 factorial part  of me when I was a nerd we used to try  to impress people of appropriate genders  by going off saying things like 3 6 2 8  8 0 0 you can probably guess how  effective that was so 3.6 million it's  gonna be a big tree any questions about  that let's go when I check things I just  compute the sum there I start off with  the sum being the distance from 0 to the  N minus first then I go through and add  up all the pairwise things and save it  what does it mean to say that if the sum  is less than the minimum sum so far I  just copy those over change them then  sum and to solve the whole thing I do a  search of size n this is a simple but  powerful recursive program you should  all feel very comfortable at this  is it correct does it work have you is  it possible to write a program about two  dozen lines of code that works not the  first time but after you get rid of a  few syntax errors you check it how do  you make sure it works I start with n  equals three and I put three and doesn't  give me a tour well work think about it  for three three factorial  they're all the same tour that part  wasn't hard for now that's interesting  that one works too this program in fact  can work is it going to be a fast  program how long we'll take it in equals  ten how many seconds I'm sorry what fast  if I stumbled into is this intact Greek  art 303 how long will this take for an  equals ten part of me about a second  pretty cool for an equal twenty how long  will it take  a lot longer technically speaking it's  gonna take a boatload longer so what I'm  gonna do here is notice that there are  in fact four permutations you do end of  those that each totals that on this  fairly fast laptop from a few years ago  but now they're all about the same at 8  seconds it took that at nine seconds  what should be the ratio what would you  expect would be the ratio between its  time at eight and time at nine now about  a factor of nine you'd hope is 0.5 times  nine about three point point three four  yeah close enough here going down from  tenth it's four seconds 46 seconds yeah  it's going up by a factor  so here I've run all my examples I run  out to one minute of CPU time after that  I estimate if this one takes three  quarters of a minute 12 times that is  twelve minutes three quarters of that is  nine minutes for 13 as two hours how  long should 14 take ballpark yeah add a  ballpark  how long will 15 take if 14 takes today  two weeks  how long will 16 take 8 months you get  the idea are you gonna go out to 20 for  this one no are you gonna go out to 16  with this one can he just put this into  a thesis right now now the problem is  fast for really small values of n as it  becomes bigger how can you make the  program faster if you wanted to make  this program faster what would you do  what are some ideas give me some ideas  please this is performance engineering  you should know this ideas for making it  faster please  okay so you're saying just choose one  start and ignore that ignore all the  others you don't need to take each  random started fantastic a factor of n  like my friend and the grade teacher  just got a factor of n how else can you  make it faster what ideas do you have  please  by  and reject things  be greedy  follow the pig principle if it feels  good do it just local optimization we'll  get to that in a long time the boy would  that be a powerful technique other ideas  please ah parallel lies I would write  that out but the first thing I would  have to do is remember how many R's in  hell's there are in various places so  I'll write that much but we'll have a  comment on that at the end people tried  that sir unlike you Charles and I at one  point attended a real engineering school  the carnegie mellon formerly known as  CIT Cardian technology charleston  remember the tear the tear 3.14159  tangent secant cosine sine square root  cube root log of e water cooled slip  stick CIT what's a water-cooled slip  stick part of me it's a slide rule that  you run so fast it has to be  water-cooled so if you can just  overclock the machine does just spray it  with a garden hose and mcc's over the  finish line you don't care if it dies  but when it collapses so sure you can  you could faster machines and we'll talk  about that how else can you make this  faster other ideas these are all great  ideas we'll try it  let's see some ideas compiler  optimizations I just said GCC and I ran  it what should I have said instead  instead of just GCC  oh three how much difference will that  make  I used to know the answers to all these  as I was gonna turn autom ization 10%  sometimes look the fricken do fifteen  percent does turning on no three still  make it a fifteen percent difference  we'll see you could do that a faster  hardware I I did this twenty years ago I  had all that number there I'll show you  some of those numbers modify the C code  we'll talk about all those options but  let's start with compiler optimizations  with no office there  how much faster will be if I turn  optimization this is a performance  engineering class you should know that  thing doesn't matter at all it's going  to be 15% how is it going to not matter  at all how much will it matter to turn  optimization how much is a lot I know  this isn't the real engineering school  of CIT  but pretend like this is kind of a semi  one of the engineering school give me a  number for this more than fifteen  percent  do I hear more than sixteen percent I  was surprised if I enable 203 it went  from four seconds to twelve I couldn't  even time it here there wasn't enough  time here 45 seconds to 1.6 seconds I  could get real times down there  I observed ballpark here about a factor  of 25  holy tamale on a Raspberry Pi it was  only a factor of six and on other  machines it was somewhere between the  two the turn on optimization really  matters enabling that really matters  from now on I'm only going to show you  full authorization is cheating not to  but just think about that a factor of 25  how else can I make it faster  two machines back in the day I happen to  have some data laying around of running  it on a Pentium Pro - when your  megahertz nowadays I had this how much  faster will this machine be 20 years  later again pretend like you read a real  engineering school hoping to be pleased  20 times faster how do you get 20 times  faster  the clocks eat about 10 here's what I  found on this machine it went from a  factor there is about a hundred these  factors I found consistently were about  over the 20 years about his factor of  154 Moore's law what would it be if you  if you had 20 years if you doubled every  two and then that's ten doublings what  is two to the tenth a thousand so  Moore's law predicts a thousand it's  more than a factor of 20  I got a factor of a hundred and fifty  here which is close to what Moore's law  might predict but there was some slowing  down at the end I'm not a little  traumatized by this a speed-up of about  a factor of hundred and fifty where does  that come from my guess is you get about  a factor of 12 due to a faster clock  speed and another factor of 12 due to  things like wider data paths you'd have  to try to cram everything to a 16-bit  bundle you have 64 bit data paths  they're deeper pipelines more  appropriate instruction sets and  compilers to exploit those instruction  sets if oh three has enabled if both  three has not enabled sucks to be you  questions about that let's go so we have  constant factor improvements external  modern machines kernel optimization may  a factor of a hundred and fifty and a  factor of 25 there's a lot we were  starting off with that that is a good  start back in the day if you change  things from doubles to floats it got way  faster from close to N so it was faster  yet does that change make much  difference nowadays not exactly the same  run  I'm one thing that does make a  difference is this is the difference  definition of the geometric distance  since my J is the square root of the sum  of the squares of the differences that's  doing an array access a subtraction and  multiplication multiplication to Ray  accessing subtraction as a  multiplication in addition and a square  root that used to take a long time if I  replace that with table lookup it's by  it's totally now this free a sort of  table the the distance four algorithm to  is just a distance erase of ice of j  that gave me a speed-up factor of two  and a half or three back in the day that  was the speed-up factor of 25 for you as  performance engineers you have all this  intuition every piece of intuition you  have that I had that was really  appropriate ten years ago is irrelevant  now you have to go back and get models  to figure out how much each thing costs  but still it's another speed a factor of  three just by replacing this arithmetic  with the table lookup algorithm three  what we're going to do is choose the one  city to start with so we'll start at  City one will leave nine if we have a  nine element problem in that position  and just search of n minus one it  doesn't matter where you start you're  gonna go back to it so you can just  choose one to start with not a lot of  code permutations are now that distance  at each so now you've reduced n times n  factorial to induct oriole algorithm for  is I'm computing the same sum each time  is there a way to avoid computing the  same darn sum each time will carry the  sum along with you instead of  recomputing the same thing over and over  and over  start off with the sum mean 0 the  parameters now M and the distance so far  then you just add in these remaining  pieces at each point  and you solve it that way and there it's  sort of a nice piece of mathematics I  wish I had the time to analyze it I did  a spreadsheet where I said how what's  the ratio of this and it started off as  three three and a half three point six  three point six five three point seven  one three point seven one eight two  eight one eight two eight what does that  mean if something if you see a constant  three point seven one eight two eight  one eight two eight it's one plus E and  once I knew what the answer was even I  in my mathematical frailty was able to  prove that it's one plus e times n  factorial I'm not giving you the proof  but it's very cool that you run across  these things so here are the four  algorithms so far on an entirely  different semi-fast machine the run time  here are the real clock times on this  machine for 10 11 12 13 real times and  bold are major times these other times  are approximate estimates and you can  see now that for size 13 you go from  taking a fraction of an hour to taking a  third of a minute with nate's and  programs faster that's pretty cool we  feel good about this this is what we do  any questions at all we got to go faster  how do we go fast just to say precisely  for all these experiments I took one  data set and if I say that to run time  for size 15 I take the first 15 elements  of that data set for 16 I take the first  16 elements 17 so on and so forth it's  not great science I've done the  experiments where I did it on lots of  random data the trends are the same it  smooths out some of the curves but we'll  see this the times are for initial  sequence of one random set it's pretty  robust  but the problem has factorial growth the  starter factorial its dual factorial  what does that mean each factor of en  allows us to creat the problem size by  one in about the same time faster  machine and all that we can now push  into the teams  what does that mean you can take abraham  lincoln's problem and they got a tour  with this length the optimal tour looks  sort of the same on this side but it's  really different over here charles what  figure is that i've mentioned yesterday  that if you work in the traveling  salesman every instance you see turns  into a Rorschach test the bunny had  everyone see that those who are in fact  the correct answers he has a  psychologically sound human being does  anyone else want to give their Rorschach  answers a free diagnosis III absolutely  no charge I'll completely diagnose you  but the bunny the bunny hopping and the  bunny head-on are impacted two correct  answers for here but we'll see more  later so Abraham Lincoln you solve his  problem now my friend Mike Sheamus could  solve his problem did he get the optimal  tour while overhearing on a big part of  it but over here it's really sort of a  different character it's a finally  different character is it far off yeah  about a third of a percent off so his  approach was within a third of a percent  I've always worked I spent much of my  career working on approximate solutions  to DSPs those are often good enough this  algorithm you can prove that he applied  is within fifty percent in the real  world it got within a third of a percent  Wow but now we can go out and we can  solve the whole problem in sixteen hours  if you were writing the thesis and you  happen to do this would it be worthwhile  now right this distinct 16 hours of CPU  time into this you're gonna go away for  a weekend to sure leave your machine  running at the time Charles when we had  one big computer for 60 or 70 people in  the department could we  dreamt about using 16 hours for that on  the very border if you made it a really  mellow background process it might  finish in a week or three all of these  things change this the computers get  faster they get more available you can  devote a machine to is it to dump 16  hours down this but can we make it  faster yet can we ever analyze say all  permutations of a deck of cards how many  permutations are there of a deck of  cards if you take out those Joker's  what's that number  yeah what will one with 15 zeros after  it it's a big number 2 to the 50 52  factorial I want to teach you how big 52  factorial is people say that problems  growing exponentially what does that  mean it's quick it's what the people  usually mean by it in mathematics it's  some constant to the N for some defined  time period n factorial growth is  factorial growth exponential growth why  not why isn't it back to exponential  it's more than exponential it's super  exponential we'll talk about the details  here by Sterling's approximation you  have seen in other classes that log that  it log of n factorial is n log n minus n  plus log n for the natural log the log  base 2 of n factorial is about n log n  minus one point three eight six seven  where have you seen this number before  one point in log n minus 1 and then  algorithms class if you did a lower  bound on a decision tree model of  sorting there were intact Oriole leaves  to Swartz a sort algorithm must take at  least as much time so that gives you  that bound and he merge sort is n log n  minus n so you're really narrow where  else have you seen one point three eight  six n that's the runtime of quicksort  all these things are coming back  together here because it's the natural  log of e I'm sorry the log base two of e  so in factorial is not 2 to the N is 2  to the n log n it's about in to the end  it's faster than any exponential  function  how big is 52 factorial  you guessed 10 to the 15th was that okay  if we see here it's going to be  something like 2 to the n log n in is 52  log of 52 is about 6 that's 2 to the the  300 but it was there's a minus in term  maybe 2 to the 250 it's about 2 to the  225 which is 10 to the 67th  that's a big number how big is it let me  put it in everyday terms try this after  class a set a timer to count down 52  factorial nanoseconds 10 to the 67th  stand on the equator watch out for where  you are and take one step forward every  million years don't rush into this I  don't want you to get a hyper about this  eventually when you circle the Earth's  one--the  take a drop of water from the Pacific  Ocean and keep on going okay be careful  about this but this is an experiment  you're you're nerds it's okay  when the Pacific Ocean is empty at that  point lay a sheet of paper down refill  the ocean and carry on now keep on doing  that when you're stacking paper reaches  to the moon  check the timer you're almost done this  is how a big ten to the fifty second is  the age of the universe so far is about  10 to the 26 nanoseconds it's ten to the  fifty second is a long time can we ever  solve a problem if we look at all ten to  the fifty second options what do we have  to do instead part of me a lot in  computing okay that's great and I have a  really cool bridge across this river out  here that I'll sell you after class  let's talk about that okay is there a  nice quantum approach to this problem  maybe I mean you could actually phrase  this as an optimization problem where  you can maybe get some mileage out of  that but we'll see so wonder purchase  quantum computing what's another  approach what are we going to have to do  to make our program is for mount this  obstacle please  part of me we're gonna have to limit our  search space we're gonna have to prune  the search space that's the idea let's  try it  here's a cool problem I was at a  ceremony a few weeks ago a friend of  mine said here's this cool problem that  his daughter to spot home from high  school how do you solve it  find all permutations of the 10 integer  or the 9 integers 1 through n such that  each initial substring of length m is  divisible by M so the whole darn thing  is divisible by 9 is any permutation of  the integers 1 2 9 to symbol by 9 well  they all sum up to number 12 old 9 he  worked that as it divisible are the  first eight characters divisible by 8  now let's start with an easy one if you  were doing it for size 3 3 2 1 works is  3 2 1 divisible by 3 it's 32 2 visible  by 2 it's 3 differ by one thinking it  works is 1 3 2 divisible by 3  yeah it's 13 days of y2 yeah that  doesn't work so we're gonna try to solve  this problem my friend Greg Conti a  really great computer security guy gave  me this problem how do you solve it how  would you solve this problem if this  high school kid says here's a problem I  brought home from school how do I solve  it what would you do  ideas I'm sorry please  or actually just  use  great so their their two main approaches  one is write a program so you can either  think or you could compute who here who  in this room enjoys writing programs who  enjoys thinking well that's an easy call  what's the right approach here well yes  the right answer is you think for a  while if you solve it in the first three  minutes  don't write a program they spend much  more than five minutes on it let's write  a program see we'll learn from the  program we'll go back and forth they  never think when you should compute  never compute what you should think how  do you know which one to do try each see  which one gets to further faster if you  write a program for this what are the  basic structures you have to deal with  you have to deal with nine digit strings  that are also nine digit numbers what's  a good language for dealing with that  what would you if you had to write a  program to do this what language would  you choose we'll say how do you generate  all intact oriole permutations of the  string well I hope you can see this  here's the way that I chose to do it I  chose to have a recursive procedure  search and I'm gonna have right be the  part that's already fixed left be the  part that you're gonna vary I couldn't  have done it the other way but I'll  choose to do it this way I start with  left equals that right equals that I end  when the left is empty besides weaker  down just like we've been doing so far  but I'm going to do that with with  strings instead and the if I get to the  call search of five six of three five  six with 41:9 seven eight these are all  fixed I'll take each one of these in  turn three five and six put it into here  so I'll call search of 56 without search  of 36 without search of 35 but that  everyone see how that works how long  will the code be and in your favorite  language here's the code in my favorite  language that's it has anyone here ever  used the awk programming language  written by a whole Weinberger and Qurna  hand they observe  naming a language after the initials of  the authors shows a certain paucity of  imagination but it works so a function  search of left right that if left equals  zero is no I'll check it otherwise what  will I do here the details don't matter  for I equals 1 up to the length of the  left hand side of the string search the  substring at the left starting at 1  going for I minus 1 with concatenated  with the substring of the left starting  at I plus 1 and then take the substring  in the middle put it out in front of the  right do that for all I values any  questions about that the details don't  matter it's not a big program if I do  this and at the end probably will 1/2  length if the substring of the right mod  I is nonzero then return if it's not  that you've printed out if I run this  program how long ballpark with this  program take 4 9 factorial ballpark what  was your answer before a second great  well will recycle that reduce reuse  recycle well recycle the answers this  tip I called originally with that string  it takes about three seconds and it  found that there was searched all nine  factorial three six two eight eight zero  362,000 strings and found only one  string there that matches that oops  are these divisible by 9 well they sum  to multiple of nine sure is this thing  that ends in 72 divisible by 8 yeah that  works seven and I'm not going to bother  with all the way down is 38 divisible by  2 its 381 divisible by three this one  works that's a pretty cool problem for a  high school afternoon  if three seconds fast enough yeah  in the trade-off of thinking and  programming right the darn program  you're done is it's cool  if you wanted to make it faster how  could you make it faster I've that's  what this course is all about always  think about how you can make things  faster please you just stop searching  [Music]  how early can you stop searching that's  great  so you could get consequent actor speed  ups like don't check for divisibility by  one at the end you can change language  all that but those are never going to  matter the big win is gonna come from  pruning the search how can you put the  search what any winning string must have  some properties of this string what are  some properties that string has it you  can check for early please the eighth  position has to be a multiple of two  furthermore if you really think about it  you could get more than that has to be a  blues visible by four and it's also an  even number has to be in the eighth  position anywhere else gonna need an  even number this position has to be even  that has to be even that has to be even  that has to be even in general what's  the general rule  every even position has to contain an  even number there are four even numbers  there are five odd numbers  what other rule might you come up with  okay every odd position has to be an odd  number and in particular the fifth  position has to be a five so those are a  few rules even digits and even positions  all digits and opposition's digit five  in position five three simple rules you  can test those easily the code is pretty  straightforward will that shrink the  size to the search space must at all  really how big was the search space  before nine for the first one now how  big is a search space for the first if  you just had the five rule the three  rules evens going evens odds and odds  and five in the middle how many choices  do you have for the first one four  choices for the second one you have it  can't be a five it has to be an odd  number not a five you have a four so  it's four by four times three times  three times one times two times two  times one times everyone see that we've  researched reduce the size in the search  space from a third of a million to half  a thousand isn't there gonna be a lot of  hassle of code that I'm gonna take like  a major software development effort to  code that well yeah if you define that  as a major software development effort  if the parity of the string length is  equal to the parity of the digit and its  then you can continue if you don't have  these things you can't continue three  lines of code allow you to do this  that's the story factorial grows quickly  you can never visit the entire search  space the key to speed is pruning the  search we're doing just a baby  branch-and-bound it's called some fancy  algorithms can begin  a little code that's our break we've  learned a couple things we ready to go  back to the to the fray any questions  about this diversion before we go back  to the TSP these are important lessons  we'll try to apply them now I got great  advice yesterday from people about how  to do this and I seem to have skipped  okay here it is I've got it how do we  prune our search there we had these  conditions how can we prune this search  how can I make the program faster what's  the way I can stop doing the search  simplest way don't keep doing what  doesn't work if the some that you have  so far is greater than the minimum some  by adding more to it are you ever going  to make it less what can you do  you can stop the search right there is  the reason looking algorithm going to be  faster maybe it's a trade-off I'm doing  more work which takes some time but I  might be able to prune the search space  the question is is this benefit worth  this cost what do you think well on the  the same machine algorithm for size 12  took point 6 seconds now it's a factor  of 60 faster factor of 40 faster a  factor of a hundred faster just by if it  doesn't work if you've already screwed  up this don't you - who doesn't work  that makes the thing a whole lot faster  everyone see that that that's the first  big win can we do even better than that  is there any way of stopping a search  with more information other than oops  I've already gone too far please  wait command boys who speak you speak  loudly  that's a really powerful idea that  helden carp use to reduce it from n  factorial times N squared - to the end  time we'll get to that that that's  really powerful but now we're looking  for something not quite that  sophisticated but that's a great idea  can I somehow prune the search if a sum  plus a lower bound on the remaining  cities is greater than the minimum  something because I what kind of lower  bound could I get well I could compute a  TSP path to them that's really powerful  that'll give me a really good bound but  it's really expensive to compute so I  could if this is the city I've done so  far I could compute a TSP path to the  rest which might in this case looks like  this and hook it up that's are going to  be a really powerful heuristic but it's  going to be really expensive to compute  on the other hand I could take just the  distance between two random points I'm  gonna choose this point and this point I  happened to get the diameter of the set  and that's the lower bound it's gonna be  at least that long which and it's really  cheap to compute but is it very  effective yeah so the first choice is  affected but too expensive the second  point is really inexpensive but not very  effective  I could also compute the nearest  neighbor of each city from this city if  I just compute its nearest neighbor  among here see it's that this one is  that that one has its own nearest  neighbor I could compute these distances  and that's pretty inexpensive to compute  and it's a pretty good lower bound that  would work who here knows what a minimum  spanning tree is good what I'll do here  is I'll take here a minimum spanning  tree in cities a tree is n minus 1 edges  this tree is in minus one edges this is  a spanning tree because it touches it  connects all cities and furthermore does  a minimum spanning tree because of all  spanning trees this one has the minimum  total distance now the tour is going to  be less or greater in distance than the  minimum spanning tree why is that if I  get a tour of this I can just knock out  the longest edge and that now becomes a  minimum spanning tree so the minimum  spanning tree is a pretty good bound a  lower bound it's cheap to compute who  here has ever seen an algorithm for  computing minimum spanning trees good  good some of you are awaking some other  classes what are the odds of that what  are the amazing confidence so what we'll  do is say now that a better lower bound  is T add V and the minimum spanning tree  the remaining points so I change this  program to if some plus the MST distance  and now I'm going to do a trick I'm  going to use word parallelism I'm going  to have the representation of the subset  of the cities as a mask bit mask in  which if the appropriate city is all on  the bid is turned on if otherwise it's  turned off and I just or bits into it  and say if I compute the minimum  spanning tree of this set I can cut the  search and return and then I just  compute the MST and bring this along  with me of turning things off and on in  the bitmask  as I go down pretty straightforward how  much code will it cost it to compute a  minimum spanning tree ballpark  yeah about that many lines of code this  is the prim Dijkstra method it takes  quadratic time for computing an MST of  endpoints it takes n squared time it's  quite simple you can do it in evoke log  be edge of time but this is a simple  code it's pretty straightforward  will this make the program run slower or  faster  what would the argument to be that it  might run slower  holy-moly at every node I'm computing an  MST that takes a long time to Marwin  slower  what's the argument to be that it might  run faster yeah but I'm getting a much  more powerful pruning is it worth it I  should play out that I'm only showing  the winds here to you when I redid this  myself I went down a few wrong paths I  wish I would have documented them better  now but I might go back and see if I can  find them that would be a good thing but  here it is it used to take 17 seconds  now it takes or 4 seconds now it takes 0  you move like algorithms to take a 0  seconds that's you you like to live in  the rounding error for point forty two  point two down here this program is not  only faster it's a boatload faster and  so now we can go out and it's and notice  here that you as you go out the times  usually get bigger but they're a bumpy  from 2.4 seconds 2.7 seconds to 1.8  seconds it's because you're doing that  one thing it's just the matter of the  geometry the times that were originally  really smooth now turned bumpy I've done  experiments where I do ten different  data sets randomly drawn at each one and  it's a nice smooth line but I miss doing  it here to be easy before you go out to  size 17 now we can go out to size 30 Wow  how cool is that that's pretty powerful  can I make this please that's absolutely  true and I've tried this both on random  point sets I've parted on distance  matrices I've tried it on points where  they're randomly distributed around the  perimeter of a circle and so this could  be a lot of time almost always it's  pretty effective again if I had more  time I talked about it but in fact we're  going to go until 3:45 Charles's will  355 when the big hand is on the 11 Oh  sucks to be you  i profile this bad boy and it shows that  most of the time is in building minimum  spanning trees your fear that it might  take a long time there might in the  goats low it has a basis that's where  all the time is going how can I reduce  the time spent in building minimum  spanning trees as I search this place I  could do some incremental in standing  trees because they change a lot and so  there are several responses one is  whenever you have you're building  something over again rather than  building it from scratch see if you can  do an incremental algorithm where you  just change one bit of the minimum  spanning tree if I just add one edge  into the graph always try an incremental  algorithm that's cool  that's one sophisticated approach what  is one what was another pretty idiot  simple approach whenever you compute  something over and over again what can  you do to reduce the time spent  computing it store it do I ever compute  the same MST over and over again I don't  know I think maybe it's worth a try  so what I'll do is return if cashing a  store rather than recompute cash and  musty distances rather than recomputing  them the code looks like this the new  mask is that if the MST distance array  is less than zero it you neutralized  everything to zero here I'm just gonna  store them all in a state table of size  two to the end I can just do direct  indexing if it's less than zero computer  telling the value if some plus that  return not much code but do you really  want to store to blast it out and to use  this lazy I'm using lazy evaluation at  this table here only when I need it do I  tell on a value that's not critically  effective rather than storing all two to  the end tables what can I do instead  what's our favorite data structure for  storing stuff hash table a cash via hash  so the key to happiness you can write  that down to store them in a hash table  if some policy MST distance lookup  oh and I have to implement a hash table  now how much code is acting to be  ballpark what does it cost to build a  hash table roughly come on yeah about  that many lines so just go down the hash  table if you find it return its  otherwise make a new node compute the  distance for then there are settle the  values and you're done is it going to be  faster oh we'll see who reads xkcd on a  regular basis the rest of you are bad  bad bad people and you should feel very  guilty until you go to xkcd comm and  start reading it on a regular basis can  i I mean like wow this is too deep  psychological insight so in one lecture  for no additional fee sir by chaining  yes  that makes sure that it's the value  associated with that is a great question  and the answer is left as an exercise  for the listener so you got about 20  minutes Charles it would be yeah and  it's well worth the try all of these  things are empirical questions one thing  that's really important to learn as a  performance engineer is that your  intuition is almost always wrong I'll  always try the experiment to see it's a  great question  well I get home I'll actually oh when I  leave here I'm going to go up to try to  climb Mount Monadnock who here's ever  climbed Mount Monadnock yeah I finished  climbing all 115 4000 foot peaks in the  northeastern US last year I've never  climbed a dad knock I'm really here to  give it a try tomorrow xkcd brute force  in factorial 2 held carton any  programming algorithm uses the grown-up  version of dynamic programming for N  squared 2 to the N but even better  algorithm six looks like that if I cache  the tsps does it have to be faster no is  it faster by about a factor of 15 there  by about a factor of 25 there 26 there  you can go out now much further 6 & 8 so  we've done that we've is there any other  way to make this program faster  we've pruned the search like crazy any  other way to make it faster please  I forget what happens to 39 let's see at  39 it went over a minute like I said  this thing goes up and down guess it  just had some weird bumps in the search  space that's something else the first  algorithm is completely predictable the  other albums you have to get more and  more into analysis and now the tines go  up and down there's a trend and  basically I'm taking an exponent and I'm  lowering I turned it from super  exponential to exponential and that I'm  beating down on the exponent right now  can you make this run faster what we're  gonna do is take this idea of a greedy  search I've been a smarter searching  better than a random order I'm gonna do  a better starting tour and what I'm  going to do is always at each point sort  the points to look at the nearest one to  the current one first start with a  random one then for the next one always  look at the nearest point first in the  second nearest the 3rd nearest etc so  I'll go in that order  - should make the search smarter and  that shouldn't guide me rather quickly  to the initial starting - rather than  just a random tour I'll have a good one  that will give me a better pruning of  the search space Labatt me make a  difference while I have to include a  sort I'll get two birds with one  modification by a really dumb insertion  sort which takes about in the lines of  code I'll visit the nearest 30 city  first and others in order if I do that  here it's a factor of two there it's a  factor of eight a factor of four but it  seems to work it gives you some so you  go out especially I can now go out  further  oops I lied I didn't stop my search it  does 60 seconds there but I can now go  up further and it seems to be a lot  faster so in 1997 twenty years ago I was  really happy to get out 230 the question  now is in twenty more years how much  bigger can I go if I just depend on  Moore's law alone in twenty years a  factor of a thousand  at 30 30 times 31 times 32 that's the  factor I can go up by Moore's law with a  dumb inductor algorithm would give me  two more cities at this size in 20 years  can I get from 30 on to anything  interesting by combining Moore's law and  compiler technology and all the  algorithms how far can I go well I was  going to give a talk at lehigh and so I  could go out in under a minute I could  go to the 45 city tour  Charles answered this yesterday so so he  is completely clear Rorschach test who's  willing to go out what do you see there  dancing doggy that that was - dancing  dog yeah I like that a lot that's  obvious answer but Charles and this  shows that profound the profound mind  professor license and what is this okay  so I any Freudians  you feel free to go to town on that one  45:22 is pretty cool dancing doggy  how far can it go I got up to 45 in  under a minute 46 I broke my rule of  this I I went over the minute boundary  this was my Thanksgiving 2016 cycle test  I was just going hog-wild I was willing  to spend the whole I had to give a I was  doing this Wednesday night I had to give  a lecture on Monday a hundred hours of  CPU time how far can I go  47 yeah yikes factor 5 when do I think  when do I run for should I go back and  work it's Jeff teach it wouldn't it be  sweet to be able to go out to 52  factorial wouldn't that be cool 48  that's not that that's looking pretty  good there actually for all ouch-ouch  that's gonna take so that that's about  two hours right there but 50 oh I my  seat you know that the the turkey was  smellin good but  fifty-one and can I get that 52 will it  make it well I have to go back to my  three hours and seven minutes by  combining all these things we're able to  go out to something that is just obscene  52 is obscenely huge we're able to get  out there by a combination of all of  these things of some really simple  performance engineering techniques if  you're going to work on a real TSP read  the literature study that I hope you  even come across some things that I've  written about approximation algorithms  but if you really need to forget the  approximation algorithms kind of true -  or there's a huge literature I haven't  told you any of that everything that  I've done here are things that you as a  person who has completed this class  should be able to do all these things  are well within your scope of practice  as we say you will not be sued for  malpractice how much code is the final  thing about that much you build an MST I  had a hash table  Charles points out you could get the you  could nuke three or four of those lines  you have to sort here altogether about  160 lines where have we been  we started we can get out to 11 store  the distances after 12 fix the starting  city that was the big one  accumulate doesn't along the way these  were all good but then by pruning the  search we started making the big things  add the MST store that isn't some hash  table this is the cities in a greedy  algorithm each one of these gave us more  and more and more power as we went out  there - were finally able to go out  pretty far there are a lot of things you  can do of parallelism faster machines  more code tuning better hashing that  that malloc is just begging to be  removed better proving it better  starting tore better bounds I can take  the MST length plus the nearest that's  why I do this MST plus the nearest  neighbor to each of the ends I can get  that would that make a big difference  empirical questions easy to find out I  can I'd move by pruning tests earlier  better sorting the  is really cool can i maybe just swart  once for each sitting to get that sort  of this then go through that precomputed  sort and select the things in order is  that going to be a win in this context  the main ideas here are caching  precomputing storing this avoiding the  work can I change that N squared  algorithm to just a linear time  selection all of these things are really  fun to look at I've tried to tell you  about incremental software development I  started off with around 3040 lines of  code it grew to 160 but all together all  the versions versions come to about two  six new lines of code you've now seen  more than you need for one life about  recursive generation it's a surprisingly  powerful technique if you ever need to  use it no excuses now you're obligated  to build immediately the storm pre  computed results partial sums early  cut-offs algorithms and data structures  these are things that sound fancy in  your algorithms class but you just pull  not when you need them vector strings  arrays and bit vectors minimum spanning  trees hash tables insertion sort it's  easy it's a dozen lines of code here two  dozen lines of code there  I believe that Charles may have  mentioned earlier that I wrote a book  and 1982 about code tuning at the time  you did these and in the smaller  programs now compilers do all that for  you but these ideas some of these ideas  still apply store free computed results  rather than common sub-expression  elimination and expression you now put  inner point distances in a matrix or a  table of MST lengths a lazy evaluation  you compute the N squared distances  eagerly but only the MST is that you  need don't bother computing them all  that's essentially what held Karp does  schwarzer greedy monotone functions  reordering tests word parallelism these  are the things that you as performance  engineers can do quite readily  I have a lot of tools behind the scenes  I wish I could come back and give you  another hour about how I really did this  with me and now  and the tools that I use I had a driver  to make experiments easy a whole bunch  of profilers where is the time we'd be  going here what should I focus on cost  models that allowed me to estimate those  how much does an MST cost a spreadsheet  was my lab notebook for graphs to  performance all sorts of curve fitting  but these are the main things I wanted  to talk about the big hand is getting  about nine minutes away from the eleven  professor leiserson is there anything  else that these fine young semi  humanoids need to know about this  material I don't know what point one of  my first exposures to MIT was when I had  Donovan as a software systems book and  it was dedicated to six point five one  graduate students I saw that and I  thought that bastard I'm sure that the  six students really worked hard on it  but to say that the the seventh student  worked only a little much more over  halfway and then to be so precise that's  just cruel well what would have a  son-of-a-bitch that guy might be so I  don't know what project four is but is  it wiser chest spiny oh great I know  what that is so what things have you  used any of these techniques to do ever  prune searches to do Everest war results  what did you do in project four  you're delegating this that's a natural  leader right there okay but speak up so  all of them can hear a place is there  anyone here from the state of California  I was born in California when you hear  alpha-beta  apart from the search what do you think  of there's a grocery store they were  called alpha beta and when Knuth wrote a  paper in that topic he went out and  bought a box of alpha beta prunes that  he had in his desk so he was an expert  in two senses on alpha beta pruning so  good other techniques please  [Music]  great did you resolve collisions at all  or did you just have one element there  with a key how did you address the  problem that the Charles mentioned of  what kind of hashing to use other  techniques yeah that's a classic example  of the fastest way to compute is not to  compute at all in general in life no  problem is so big that it can't be run  away from the these things about a  boarding work and being lazy are  certainly models for organizing your own  life so that lazy evaluation really  works in the real world other questions  without a question or a random have seen  your hand gesture  please oh that's a great question I  worked in this problem a lot in the  early 1990s with my colleague David  Johnson who literally wrote the book on  NP completeness an MIT PhD guy we were  really happy we're in at the time in a  couple of hours of CPU time we could  solve a hundred thousand city problems  to within a few percent we were able to  solve million city problems in a day of  CPU time to within a few percent and we  were ecstatic that that was really big  so we could go out that big to within a  few percent if we worked really really  hard we can get ten thousand problems  counted within 1/2 percent but if you  want to go all the way to have not only  the optimal solution but it proof that  it's optimal for a while people bragged  about we finally solved a problem this  will let you see about what it was done  we solved the problem of all 48 state  capitals so for a while that was the  state of the art and then that number  has crept over time and now you can get  exact solutions to some famous problems  into the tens of thousands by using lots  and lots of really clever searching that  branching down with really clever lower  bounds to guide it up and you at one  point get a tour and you can make like  that tour but then you get a proof of a  lower bound along with it to do that hey  oh man I want to let you know that  they're actually now 50 states in the  Union No  what time did this happen you can tell  that I am much much much older than  Charles and he never lets me hear the  end of it I trusted the rest of you this  is like the third free deep psychology  insight is be kind to old people ignore  the example that the kid over there sets  and show some class the respective might  to me and my fellow geezers yeah we were  both born in 1953 but I was born in the  good part of 1952 in particular I was  born before Her Majesty the Queen of  England assumed the throne okay can you  make the same claim I cannot make the  same thing I'm sorry he can but only cuz  he's a sneaky bastard can you make it to  fillet it's the question I should have  asked other questions this class can be  very important like I said I spent the  past almost half century as a working  computer programmer the majority about  the thing I've done most is performance  engineering it's really to do a number  of really interesting things I've been  able to dabble in all sorts of  computational systems ranging from  automated gerrymandering every time you  make a telephone call in this country if  it's say a call from inside an  institution like a hospital or a  university it uses some code that I  wrote some performance things if you  make a long-distance call it uses code  that I wrote if you've ever used  something called Google internet search  or match or maps or stocks or anything  else that uses and algorithms I've done  it's incredibly satisfying it's been a  very very fulfilling way for me to spend  a big chunk of my life  I am grateful it's allowed me to make  friends whom I've known for almost half  a century and who are wonderful dear  people and it's been a great way for my  life I hope the performance engineering  is as good to you as it has been to me  anything else professor  thank you very much John thank you  [Applause]
 

3
00:00:05,769 --> 00:00:08,019

 

4
00:00:08,019 --> 00:00:09,850

 

5
00:00:09,850 --> 00:00:10,930

 

6
00:00:10,930 --> 00:00:13,120

 

7
00:00:13,120 --> 00:00:15,160

 

8
00:00:15,160 --> 00:00:21,880

 

9
00:00:21,880 --> 00:00:25,040

 

10
00:00:25,040 --> 00:00:31,609

 

11
00:00:31,609 --> 00:00:35,150

 

12
00:00:35,150 --> 00:00:37,040

 

13
00:00:37,040 --> 00:00:39,620

 

14
00:00:39,620 --> 00:00:42,530

 

15
00:00:42,530 --> 00:00:47,080

 

16
00:00:47,080 --> 00:00:51,290

 

17
00:00:51,290 --> 00:00:56,410

 

18
00:00:56,410 --> 00:01:00,020

 

19
00:01:00,020 --> 00:01:02,450

 

20
00:01:02,450 --> 00:01:06,380

 

21
00:01:06,380 --> 00:01:10,399

 

22
00:01:10,399 --> 00:01:12,530

 

23
00:01:12,530 --> 00:01:15,680

 

24
00:01:15,680 --> 00:01:19,010

 

25
00:01:19,010 --> 00:01:21,950

 

26
00:01:21,950 --> 00:01:24,649

 

27
00:01:24,649 --> 00:01:28,340

 

28
00:01:28,340 --> 00:01:31,760

 

29
00:01:31,760 --> 00:01:33,680

 

30
00:01:33,680 --> 00:01:35,630

 

31
00:01:35,630 --> 00:01:37,490

 

32
00:01:37,490 --> 00:01:40,130

 

33
00:01:40,130 --> 00:01:42,500

 

34
00:01:42,500 --> 00:01:44,770

 

35
00:01:44,770 --> 00:01:47,270

 

36
00:01:47,270 --> 00:01:48,350

 

37
00:01:48,350 --> 00:01:51,140

 

38
00:01:51,140 --> 00:01:53,930

 

39
00:01:53,930 --> 00:01:57,110

 

40
00:01:57,110 --> 00:01:59,510

 

41
00:01:59,510 --> 00:02:01,730

 

42
00:02:01,730 --> 00:02:03,800

 

43
00:02:03,800 --> 00:02:05,150

 

44
00:02:05,150 --> 00:02:07,940

 

45
00:02:07,940 --> 00:02:10,479

 

46
00:02:10,479 --> 00:02:12,770

 

47
00:02:12,770 --> 00:02:13,940

 

48
00:02:13,940 --> 00:02:18,410

 

49
00:02:18,410 --> 00:02:21,520

 

50
00:02:21,520 --> 00:02:24,559

 

51
00:02:24,559 --> 00:02:27,290

 

52
00:02:27,290 --> 00:02:29,590

 

53
00:02:29,590 --> 00:02:31,630

 

54
00:02:31,630 --> 00:02:34,420

 

55
00:02:34,420 --> 00:02:36,760

 

56
00:02:36,760 --> 00:02:39,250

 

57
00:02:39,250 --> 00:02:41,650

 

58
00:02:41,650 --> 00:02:44,020

 

59
00:02:44,020 --> 00:02:46,570

 

60
00:02:46,570 --> 00:02:50,200

 

61
00:02:50,200 --> 00:02:52,810

 

62
00:02:52,810 --> 00:02:53,890

 

63
00:02:53,890 --> 00:02:56,110

 

64
00:02:56,110 --> 00:02:58,090

 

65
00:02:58,090 --> 00:03:01,300

 

66
00:03:01,300 --> 00:03:04,990

 

67
00:03:04,990 --> 00:03:09,610

 

68
00:03:09,610 --> 00:03:11,770

 

69
00:03:11,770 --> 00:03:14,080

 

70
00:03:14,080 --> 00:03:15,940

 

71
00:03:15,940 --> 00:03:18,820

 

72
00:03:18,820 --> 00:03:22,230

 

73
00:03:22,230 --> 00:03:24,580

 

74
00:03:24,580 --> 00:03:29,770

 

75
00:03:29,770 --> 00:03:33,190

 

76
00:03:33,190 --> 00:03:34,630

 

77
00:03:34,630 --> 00:03:39,340

 

78
00:03:39,340 --> 00:03:41,170

 

79
00:03:41,170 --> 00:03:43,900

 

80
00:03:43,900 --> 00:03:47,320

 

81
00:03:47,320 --> 00:03:53,380

 

82
00:03:53,380 --> 00:03:57,190

 

83
00:03:57,190 --> 00:03:58,540

 

84
00:03:58,540 --> 00:04:02,470

 

85
00:04:02,470 --> 00:04:04,660

 

86
00:04:04,660 --> 00:04:07,740

 

87
00:04:07,740 --> 00:04:11,949

 

88
00:04:11,949 --> 00:04:13,900

 

89
00:04:13,900 --> 00:04:16,210

 

90
00:04:16,210 --> 00:04:18,280

 

91
00:04:18,280 --> 00:04:23,710

 

92
00:04:23,710 --> 00:04:26,320

 

93
00:04:26,320 --> 00:04:28,930

 

94
00:04:28,930 --> 00:04:31,450

 

95
00:04:31,450 --> 00:04:33,520

 

96
00:04:33,520 --> 00:04:35,920

 

97
00:04:35,920 --> 00:04:37,750

 

98
00:04:37,750 --> 00:04:41,210

 

99
00:04:41,210 --> 00:04:43,130

 

100
00:04:43,130 --> 00:04:46,520

 

101
00:04:46,520 --> 00:04:48,800

 

102
00:04:48,800 --> 00:04:51,710

 

103
00:04:51,710 --> 00:04:53,240

 

104
00:04:53,240 --> 00:04:56,380

 

105
00:04:56,380 --> 00:05:02,000

 

106
00:05:02,000 --> 00:05:07,640

 

107
00:05:07,640 --> 00:05:11,210

 

108
00:05:11,210 --> 00:05:13,340

 

109
00:05:13,340 --> 00:05:15,170

 

110
00:05:15,170 --> 00:05:18,080

 

111
00:05:18,080 --> 00:05:19,910

 

112
00:05:19,910 --> 00:05:22,040

 

113
00:05:22,040 --> 00:05:23,630

 

114
00:05:23,630 --> 00:05:26,000

 

115
00:05:26,000 --> 00:05:32,180

 

116
00:05:32,180 --> 00:05:34,159

 

117
00:05:34,159 --> 00:05:35,930

 

118
00:05:35,930 --> 00:05:37,850

 

119
00:05:37,850 --> 00:05:39,620

 

120
00:05:39,620 --> 00:05:46,720

 

121
00:05:46,720 --> 00:05:49,610

 

122
00:05:49,610 --> 00:05:53,720

 

123
00:05:53,720 --> 00:05:55,190

 

124
00:05:55,190 --> 00:05:59,120

 

125
00:05:59,120 --> 00:06:01,460

 

126
00:06:01,460 --> 00:06:03,920

 

127
00:06:03,920 --> 00:06:06,130

 

128
00:06:06,130 --> 00:06:11,510

 

129
00:06:11,510 --> 00:06:14,719

 

130
00:06:14,719 --> 00:06:17,510

 

131
00:06:17,510 --> 00:06:19,790

 

132
00:06:19,790 --> 00:06:21,290

 

133
00:06:21,290 --> 00:06:23,360

 

134
00:06:23,360 --> 00:06:30,170

 

135
00:06:30,170 --> 00:06:34,310

 

136
00:06:34,310 --> 00:06:37,159

 

137
00:06:37,159 --> 00:06:39,320

 

138
00:06:39,320 --> 00:06:41,420

 

139
00:06:41,420 --> 00:06:43,070

 

140
00:06:43,070 --> 00:06:45,650

 

141
00:06:45,650 --> 00:06:47,330

 

142
00:06:47,330 --> 00:06:49,909

 

143
00:06:49,909 --> 00:06:50,629

 

144
00:06:50,629 --> 00:06:52,279

 

145
00:06:52,279 --> 00:06:57,230

 

146
00:06:57,230 --> 00:07:00,660

 

147
00:07:00,660 --> 00:07:00,670

 

148
00:07:00,670 --> 00:07:06,909


149
00:07:06,909 --> 00:07:14,779

 

150
00:07:14,779 --> 00:07:16,879

 

151
00:07:16,879 --> 00:07:19,010

 

152
00:07:19,010 --> 00:07:21,170

 

153
00:07:21,170 --> 00:07:23,809

 

154
00:07:23,809 --> 00:07:26,570

 

155
00:07:26,570 --> 00:07:29,540

 

156
00:07:29,540 --> 00:07:32,089

 

157
00:07:32,089 --> 00:07:34,520

 

158
00:07:34,520 --> 00:07:35,450

 

159
00:07:35,450 --> 00:07:38,240

 

160
00:07:38,240 --> 00:07:39,409

 

161
00:07:39,409 --> 00:07:44,810

 

162
00:07:44,810 --> 00:07:50,330

 

163
00:07:50,330 --> 00:07:52,100

 

164
00:07:52,100 --> 00:07:54,680

 

165
00:07:54,680 --> 00:07:56,150

 

166
00:07:56,150 --> 00:07:58,430

 

167
00:07:58,430 --> 00:08:01,310

 

168
00:08:01,310 --> 00:08:04,879

 

169
00:08:04,879 --> 00:08:07,760

 

170
00:08:07,760 --> 00:08:11,689

 

171
00:08:11,689 --> 00:08:14,930

 

172
00:08:14,930 --> 00:08:17,450

 

173
00:08:17,450 --> 00:08:20,570

 

174
00:08:20,570 --> 00:08:22,520

 

175
00:08:22,520 --> 00:08:24,439

 

176
00:08:24,439 --> 00:08:26,420

 

177
00:08:26,420 --> 00:08:29,719

 

178
00:08:29,719 --> 00:08:32,269

 

179
00:08:32,269 --> 00:08:34,490

 

180
00:08:34,490 --> 00:08:36,920

 

181
00:08:36,920 --> 00:08:38,480

 

182
00:08:38,480 --> 00:08:41,029

 

183
00:08:41,029 --> 00:08:43,699

 

184
00:08:43,699 --> 00:08:46,160

 

185
00:08:46,160 --> 00:08:47,540

 

186
00:08:47,540 --> 00:08:50,449

 

187
00:08:50,449 --> 00:08:53,300

 

188
00:08:53,300 --> 00:08:55,430

 

189
00:08:55,430 --> 00:08:57,260

 

190
00:08:57,260 --> 00:09:00,079

 

191
00:09:00,079 --> 00:09:01,880

 

192
00:09:01,880 --> 00:09:05,600

 

193
00:09:05,600 --> 00:09:07,910

 

194
00:09:07,910 --> 00:09:09,500

 

195
00:09:09,500 --> 00:09:11,150

 

196
00:09:11,150 --> 00:09:13,040

 

197
00:09:13,040 --> 00:09:15,260

 

198
00:09:15,260 --> 00:09:17,400

 

199
00:09:17,400 --> 00:09:19,769

 

200
00:09:19,769 --> 00:09:20,819

 

201
00:09:20,819 --> 00:09:22,860

 

202
00:09:22,860 --> 00:09:24,509

 

203
00:09:24,509 --> 00:09:29,670

 

204
00:09:29,670 --> 00:09:31,740

 

205
00:09:31,740 --> 00:09:33,600

 

206
00:09:33,600 --> 00:09:35,490

 

207
00:09:35,490 --> 00:09:37,050

 

208
00:09:37,050 --> 00:09:39,749

 

209
00:09:39,749 --> 00:09:41,550

 

210
00:09:41,550 --> 00:09:43,259

 

211
00:09:43,259 --> 00:09:45,809

 

212
00:09:45,809 --> 00:09:47,579

 

213
00:09:47,579 --> 00:09:49,590

 

214
00:09:49,590 --> 00:09:51,210

 

215
00:09:51,210 --> 00:09:55,769

 

216
00:09:55,769 --> 00:09:57,840

 

217
00:09:57,840 --> 00:10:00,150

 

218
00:10:00,150 --> 00:10:02,429

 

219
00:10:02,429 --> 00:10:03,869

 

220
00:10:03,869 --> 00:10:09,210

 

221
00:10:09,210 --> 00:10:11,429

 

222
00:10:11,429 --> 00:10:13,559

 

223
00:10:13,559 --> 00:10:15,569

 

224
00:10:15,569 --> 00:10:17,639

 

225
00:10:17,639 --> 00:10:19,350

 

226
00:10:19,350 --> 00:10:20,999

 

227
00:10:20,999 --> 00:10:23,040

 

228
00:10:23,040 --> 00:10:24,300

 

229
00:10:24,300 --> 00:10:26,550

 

230
00:10:26,550 --> 00:10:29,009

 

231
00:10:29,009 --> 00:10:31,139

 

232
00:10:31,139 --> 00:10:33,480

 

233
00:10:33,480 --> 00:10:35,069

 

234
00:10:35,069 --> 00:10:38,670

 

235
00:10:38,670 --> 00:10:41,999

 

236
00:10:41,999 --> 00:10:43,800

 

237
00:10:43,800 --> 00:10:47,610

 

238
00:10:47,610 --> 00:10:50,160

 

239
00:10:50,160 --> 00:10:51,900

 

240
00:10:51,900 --> 00:10:54,269

 

241
00:10:54,269 --> 00:10:55,650

 

242
00:10:55,650 --> 00:10:58,079

 

243
00:10:58,079 --> 00:10:59,939

 

244
00:10:59,939 --> 00:11:01,889

 

245
00:11:01,889 --> 00:11:04,549

 

246
00:11:04,549 --> 00:11:07,980

 

247
00:11:07,980 --> 00:11:09,960

 

248
00:11:09,960 --> 00:11:12,749

 

249
00:11:12,749 --> 00:11:16,439

 

250
00:11:16,439 --> 00:11:17,519

 

251
00:11:17,519 --> 00:11:19,439

 

252
00:11:19,439 --> 00:11:24,030

 

253
00:11:24,030 --> 00:11:28,470

 

254
00:11:28,470 --> 00:11:33,180

 

255
00:11:33,180 --> 00:11:37,620

 

256
00:11:37,620 --> 00:11:41,639

 

257
00:11:41,639 --> 00:11:43,139

 

258
00:11:43,139 --> 00:11:44,579

 

259
00:11:44,579 --> 00:11:48,420

 

260
00:11:48,420 --> 00:11:49,879

 

261
00:11:49,879 --> 00:11:52,019

 

262
00:11:52,019 --> 00:11:55,110

 

263
00:11:55,110 --> 00:11:57,180

 

264
00:11:57,180 --> 00:12:02,189

 

265
00:12:02,189 --> 00:12:04,379

 

266
00:12:04,379 --> 00:12:05,939

 

267
00:12:05,939 --> 00:12:09,720

 

268
00:12:09,720 --> 00:12:13,470

 

269
00:12:13,470 --> 00:12:15,000

 

270
00:12:15,000 --> 00:12:18,060

 

271
00:12:18,060 --> 00:12:21,000

 

272
00:12:21,000 --> 00:12:23,009

 

273
00:12:23,009 --> 00:12:24,840

 

274
00:12:24,840 --> 00:12:26,550

 

275
00:12:26,550 --> 00:12:30,000

 

276
00:12:30,000 --> 00:12:31,860

 

277
00:12:31,860 --> 00:12:34,139

 

278
00:12:34,139 --> 00:12:36,809

 

279
00:12:36,809 --> 00:12:40,199

 

280
00:12:40,199 --> 00:12:42,050

 

281
00:12:42,050 --> 00:12:45,569

 

282
00:12:45,569 --> 00:12:48,870

 

283
00:12:48,870 --> 00:12:51,000

 

284
00:12:51,000 --> 00:12:54,240

 

285
00:12:54,240 --> 00:12:56,069

 

286
00:12:56,069 --> 00:12:58,379

 

287
00:12:58,379 --> 00:13:00,210

 

288
00:13:00,210 --> 00:13:05,069

 

289
00:13:05,069 --> 00:13:07,910

 

290
00:13:07,910 --> 00:13:10,199

 

291
00:13:10,199 --> 00:13:11,879

 

292
00:13:11,879 --> 00:13:13,829

 

293
00:13:13,829 --> 00:13:16,170

 

294
00:13:16,170 --> 00:13:17,910

 

295
00:13:17,910 --> 00:13:20,030

 

296
00:13:20,030 --> 00:13:24,030

 

297
00:13:24,030 --> 00:13:26,639

 

298
00:13:26,639 --> 00:13:29,220

 

299
00:13:29,220 --> 00:13:30,720

 

300
00:13:30,720 --> 00:13:33,300

 

301
00:13:33,300 --> 00:13:34,130

 

302
00:13:34,130 --> 00:13:36,590

 

303
00:13:36,590 --> 00:13:37,940

 

304
00:13:37,940 --> 00:13:41,090

 

305
00:13:41,090 --> 00:13:42,410

 

306
00:13:42,410 --> 00:13:43,310

 

307
00:13:43,310 --> 00:13:46,550

 

308
00:13:46,550 --> 00:13:48,920

 

309
00:13:48,920 --> 00:13:50,750

 

310
00:13:50,750 --> 00:13:52,550

 

311
00:13:52,550 --> 00:13:55,490

 

312
00:13:55,490 --> 00:13:56,870

 

313
00:13:56,870 --> 00:13:57,650

 

314
00:13:57,650 --> 00:14:01,760

 

315
00:14:01,760 --> 00:14:04,430

 

316
00:14:04,430 --> 00:14:07,130

 

317
00:14:07,130 --> 00:14:10,610

 

318
00:14:10,610 --> 00:14:13,310

 

319
00:14:13,310 --> 00:14:14,660

 

320
00:14:14,660 --> 00:14:16,190

 

321
00:14:16,190 --> 00:14:17,300

 

322
00:14:17,300 --> 00:14:18,920

 

323
00:14:18,920 --> 00:14:21,350

 

324
00:14:21,350 --> 00:14:23,540

 

325
00:14:23,540 --> 00:14:29,480

 

326
00:14:29,480 --> 00:14:31,370

 

327
00:14:31,370 --> 00:14:33,710

 

328
00:14:33,710 --> 00:14:35,900

 

329
00:14:35,900 --> 00:14:39,710

 

330
00:14:39,710 --> 00:14:41,600

 

331
00:14:41,600 --> 00:14:43,490

 

332
00:14:43,490 --> 00:14:45,170

 

333
00:14:45,170 --> 00:14:47,000

 

334
00:14:47,000 --> 00:14:48,560

 

335
00:14:48,560 --> 00:14:52,100

 

336
00:14:52,100 --> 00:14:54,080

 

337
00:14:54,080 --> 00:14:55,730

 

338
00:14:55,730 --> 00:14:57,920

 

339
00:14:57,920 --> 00:15:00,230

 

340
00:15:00,230 --> 00:15:02,450

 

341
00:15:02,450 --> 00:15:04,100

 

342
00:15:04,100 --> 00:15:07,460

 

343
00:15:07,460 --> 00:15:08,930

 

344
00:15:08,930 --> 00:15:12,650

 

345
00:15:12,650 --> 00:15:17,030

 

346
00:15:17,030 --> 00:15:19,460

 

347
00:15:19,460 --> 00:15:21,350

 

348
00:15:21,350 --> 00:15:23,570

 

349
00:15:23,570 --> 00:15:25,550

 

350
00:15:25,550 --> 00:15:28,940

 

351
00:15:28,940 --> 00:15:33,530

 

352
00:15:33,530 --> 00:15:34,790

 

353
00:15:34,790 --> 00:15:38,420

 

354
00:15:38,420 --> 00:15:42,140

 

355
00:15:42,140 --> 00:15:44,330

 

356
00:15:44,330 --> 00:15:46,220

 

357
00:15:46,220 --> 00:15:48,470

 

358
00:15:48,470 --> 00:15:51,170

 

359
00:15:51,170 --> 00:15:54,620

 

360
00:15:54,620 --> 00:15:57,320

 

361
00:15:57,320 --> 00:16:00,770

 

362
00:16:00,770 --> 00:16:03,580

 

363
00:16:03,580 --> 00:16:05,690

 

364
00:16:05,690 --> 00:16:08,240

 

365
00:16:08,240 --> 00:16:09,790

 

366
00:16:09,790 --> 00:16:15,740

 

367
00:16:15,740 --> 00:16:17,780

 

368
00:16:17,780 --> 00:16:19,880

 

369
00:16:19,880 --> 00:16:22,640

 

370
00:16:22,640 --> 00:16:25,100

 

371
00:16:25,100 --> 00:16:28,910

 

372
00:16:28,910 --> 00:16:31,040

 

373
00:16:31,040 --> 00:16:33,380

 

374
00:16:33,380 --> 00:16:35,690

 

375
00:16:35,690 --> 00:16:39,260

 

376
00:16:39,260 --> 00:16:41,180

 

377
00:16:41,180 --> 00:16:44,140

 

378
00:16:44,140 --> 00:16:48,380

 

379
00:16:48,380 --> 00:16:50,750

 

380
00:16:50,750 --> 00:16:52,400

 

381
00:16:52,400 --> 00:16:53,930

 

382
00:16:53,930 --> 00:16:56,960

 

383
00:16:56,960 --> 00:16:59,990

 

384
00:16:59,990 --> 00:17:01,400

 

385
00:17:01,400 --> 00:17:02,930

 

386
00:17:02,930 --> 00:17:06,130

 

387
00:17:06,130 --> 00:17:08,210

 

388
00:17:08,210 --> 00:17:14,960

 

389
00:17:14,960 --> 00:17:25,700

 

390
00:17:25,700 --> 00:17:29,240

 

391
00:17:29,240 --> 00:17:30,950

 

392
00:17:30,950 --> 00:17:33,320

 

393
00:17:33,320 --> 00:17:35,780

 

394
00:17:35,780 --> 00:17:38,750

 

395
00:17:38,750 --> 00:17:41,950

 

396
00:17:41,950 --> 00:17:45,800

 

397
00:17:45,800 --> 00:17:47,630

 

398
00:17:47,630 --> 00:17:51,560

 

399
00:17:51,560 --> 00:17:53,360

 

400
00:17:53,360 --> 00:17:55,340

 

401
00:17:55,340 --> 00:17:58,190

 

402
00:17:58,190 --> 00:18:00,230

 

403
00:18:00,230 --> 00:18:03,740

 

404
00:18:03,740 --> 00:18:06,200

 

405
00:18:06,200 --> 00:18:07,970

 

406
00:18:07,970 --> 00:18:09,950

 

407
00:18:09,950 --> 00:18:13,640

 

408
00:18:13,640 --> 00:18:16,940

 

409
00:18:16,940 --> 00:18:23,540

 

410
00:18:23,540 --> 00:18:28,280

 

411
00:18:28,280 --> 00:18:30,890

 

412
00:18:30,890 --> 00:18:33,170

 

413
00:18:33,170 --> 00:18:38,300

 

414
00:18:38,300 --> 00:18:43,760

 

415
00:18:43,760 --> 00:18:45,500

 

416
00:18:45,500 --> 00:18:50,960

 

417
00:18:50,960 --> 00:18:52,880

 

418
00:18:52,880 --> 00:18:54,890

 

419
00:18:54,890 --> 00:18:56,690

 

420
00:18:56,690 --> 00:18:58,280

 

421
00:18:58,280 --> 00:19:00,410

 

422
00:19:00,410 --> 00:19:02,270

 

423
00:19:02,270 --> 00:19:04,220

 

424
00:19:04,220 --> 00:19:06,320

 

425
00:19:06,320 --> 00:19:09,590

 

426
00:19:09,590 --> 00:19:11,630

 

427
00:19:11,630 --> 00:19:15,960

 

428
00:19:15,960 --> 00:19:20,879

 

429
00:19:20,879 --> 00:19:22,529

 

430
00:19:22,529 --> 00:19:25,560

 

431
00:19:25,560 --> 00:19:26,789

 

432
00:19:26,789 --> 00:19:29,279

 

433
00:19:29,279 --> 00:19:32,340

 

434
00:19:32,340 --> 00:19:34,710

 

435
00:19:34,710 --> 00:19:37,049

 

436
00:19:37,049 --> 00:19:38,279

 

437
00:19:38,279 --> 00:19:40,740

 

438
00:19:40,740 --> 00:19:43,249

 

439
00:19:43,249 --> 00:19:46,740

 

440
00:19:46,740 --> 00:19:52,470

 

441
00:19:52,470 --> 00:19:55,889

 

442
00:19:55,889 --> 00:20:02,549

 

443
00:20:02,549 --> 00:20:05,639

 

444
00:20:05,639 --> 00:20:09,389

 

445
00:20:09,389 --> 00:20:15,289

 

446
00:20:15,289 --> 00:20:18,509

 

447
00:20:18,509 --> 00:20:23,240

 

448
00:20:23,240 --> 00:20:26,480

 

449
00:20:26,480 --> 00:20:29,450

 

450
00:20:29,450 --> 00:20:31,669

 

451
00:20:31,669 --> 00:20:33,649

 

452
00:20:33,649 --> 00:20:37,570

 

453
00:20:37,570 --> 00:20:40,100

 

454
00:20:40,100 --> 00:20:44,299

 

455
00:20:44,299 --> 00:20:47,480

 

456
00:20:47,480 --> 00:20:49,460

 

457
00:20:49,460 --> 00:20:50,870

 

458
00:20:50,870 --> 00:20:54,919

 

459
00:20:54,919 --> 00:20:57,260

 

460
00:20:57,260 --> 00:20:59,180

 

461
00:20:59,180 --> 00:21:05,360

 

462
00:21:05,360 --> 00:21:08,630

 

463
00:21:08,630 --> 00:21:10,100

 

464
00:21:10,100 --> 00:21:12,710

 

465
00:21:12,710 --> 00:21:14,990

 

466
00:21:14,990 --> 00:21:17,120

 

467
00:21:17,120 --> 00:21:19,399

 

468
00:21:19,399 --> 00:21:20,960

 

469
00:21:20,960 --> 00:21:24,950

 

470
00:21:24,950 --> 00:21:32,020

 

471
00:21:32,020 --> 00:21:32,030

 

472
00:21:32,030 --> 00:21:33,200


473
00:21:33,200 --> 00:21:36,190

 

474
00:21:36,190 --> 00:21:37,580

 

475
00:21:37,580 --> 00:21:43,130

 

476
00:21:43,130 --> 00:21:44,570

 

477
00:21:44,570 --> 00:21:46,610

 

478
00:21:46,610 --> 00:21:48,590

 

479
00:21:48,590 --> 00:21:51,770

 

480
00:21:51,770 --> 00:21:54,830

 

481
00:21:54,830 --> 00:21:58,010

 

482
00:21:58,010 --> 00:22:01,250

 

483
00:22:01,250 --> 00:22:02,570

 

484
00:22:02,570 --> 00:22:04,220

 

485
00:22:04,220 --> 00:22:05,779

 

486
00:22:05,779 --> 00:22:08,149

 

487
00:22:08,149 --> 00:22:17,379

 

488
00:22:17,379 --> 00:22:25,480

 

489
00:22:25,480 --> 00:22:29,180

 

490
00:22:29,180 --> 00:22:30,379

 

491
00:22:30,379 --> 00:22:33,200

 

492
00:22:33,200 --> 00:22:34,759

 

493
00:22:34,759 --> 00:22:36,740

 

494
00:22:36,740 --> 00:22:39,879

 

495
00:22:39,879 --> 00:22:39,889

 

496
00:22:39,889 --> 00:22:43,899


497
00:22:43,899 --> 00:22:43,909

 

498
00:22:43,909 --> 00:22:46,080


499
00:22:46,080 --> 00:22:51,200

 

500
00:22:51,200 --> 00:22:53,330

 

501
00:22:53,330 --> 00:22:56,100

 

502
00:22:56,100 --> 00:23:00,300

 

503
00:23:00,300 --> 00:23:01,830

 

504
00:23:01,830 --> 00:23:03,810

 

505
00:23:03,810 --> 00:23:09,300

 

506
00:23:09,300 --> 00:23:10,650

 

507
00:23:10,650 --> 00:23:12,210

 

508
00:23:12,210 --> 00:23:14,190

 

509
00:23:14,190 --> 00:23:16,650

 

510
00:23:16,650 --> 00:23:18,510

 

511
00:23:18,510 --> 00:23:25,920

 

512
00:23:25,920 --> 00:23:29,240

 

513
00:23:29,240 --> 00:23:31,950

 

514
00:23:31,950 --> 00:23:34,620

 

515
00:23:34,620 --> 00:23:41,160

 

516
00:23:41,160 --> 00:23:43,950

 

517
00:23:43,950 --> 00:23:46,290

 

518
00:23:46,290 --> 00:23:50,010

 

519
00:23:50,010 --> 00:23:55,440

 

520
00:23:55,440 --> 00:23:57,000

 

521
00:23:57,000 --> 00:23:58,800

 

522
00:23:58,800 --> 00:24:01,020

 

523
00:24:01,020 --> 00:24:05,490

 

524
00:24:05,490 --> 00:24:06,690

 

525
00:24:06,690 --> 00:24:09,150

 

526
00:24:09,150 --> 00:24:11,280

 

527
00:24:11,280 --> 00:24:16,440

 

528
00:24:16,440 --> 00:24:24,510

 

529
00:24:24,510 --> 00:24:26,360

 

530
00:24:26,360 --> 00:24:30,930

 

531
00:24:30,930 --> 00:24:34,710

 

532
00:24:34,710 --> 00:24:37,850

 

533
00:24:37,850 --> 00:24:41,750

 

534
00:24:41,750 --> 00:24:44,720

 

535
00:24:44,720 --> 00:24:44,730

 

536
00:24:44,730 --> 00:24:45,200


537
00:24:45,200 --> 00:24:49,730

 

538
00:24:49,730 --> 00:24:52,610

 

539
00:24:52,610 --> 00:24:55,010

 

540
00:24:55,010 --> 00:24:57,200

 

541
00:24:57,200 --> 00:24:59,720

 

542
00:24:59,720 --> 00:25:03,110

 

543
00:25:03,110 --> 00:25:05,120

 

544
00:25:05,120 --> 00:25:07,310

 

545
00:25:07,310 --> 00:25:09,650

 

546
00:25:09,650 --> 00:25:11,690

 

547
00:25:11,690 --> 00:25:13,250

 

548
00:25:13,250 --> 00:25:14,210

 

549
00:25:14,210 --> 00:25:15,920

 

550
00:25:15,920 --> 00:25:17,990

 

551
00:25:17,990 --> 00:25:19,310

 

552
00:25:19,310 --> 00:25:20,780

 

553
00:25:20,780 --> 00:25:22,910

 

554
00:25:22,910 --> 00:25:24,650

 

555
00:25:24,650 --> 00:25:30,680

 

556
00:25:30,680 --> 00:25:32,450

 

557
00:25:32,450 --> 00:25:33,050

 

558
00:25:33,050 --> 00:25:35,450

 

559
00:25:35,450 --> 00:25:37,100

 

560
00:25:37,100 --> 00:25:39,800

 

561
00:25:39,800 --> 00:25:39,810

 

562
00:25:39,810 --> 00:25:40,280


563
00:25:40,280 --> 00:25:42,440

 

564
00:25:42,440 --> 00:25:46,820

 

565
00:25:46,820 --> 00:25:49,880

 

566
00:25:49,880 --> 00:25:51,170

 

567
00:25:51,170 --> 00:25:53,990

 

568
00:25:53,990 --> 00:25:55,790

 

569
00:25:55,790 --> 00:25:59,030

 

570
00:25:59,030 --> 00:26:01,330

 

571
00:26:01,330 --> 00:26:06,260

 

572
00:26:06,260 --> 00:26:07,970

 

573
00:26:07,970 --> 00:26:09,440

 

574
00:26:09,440 --> 00:26:11,720

 

575
00:26:11,720 --> 00:26:13,150

 

576
00:26:13,150 --> 00:26:16,040

 

577
00:26:16,040 --> 00:26:17,660

 

578
00:26:17,660 --> 00:26:21,670

 

579
00:26:21,670 --> 00:26:26,970

 

580
00:26:26,970 --> 00:26:29,609

 

581
00:26:29,609 --> 00:26:31,649

 

582
00:26:31,649 --> 00:26:33,090

 

583
00:26:33,090 --> 00:26:35,879

 

584
00:26:35,879 --> 00:26:37,769

 

585
00:26:37,769 --> 00:26:43,979

 

586
00:26:43,979 --> 00:26:47,810

 

587
00:26:47,810 --> 00:26:50,789

 

588
00:26:50,789 --> 00:26:50,799

 

589
00:26:50,799 --> 00:26:53,180


590
00:26:53,180 --> 00:26:59,669

 

591
00:26:59,669 --> 00:27:02,970

 

592
00:27:02,970 --> 00:27:08,820

 

593
00:27:08,820 --> 00:27:11,340

 

594
00:27:11,340 --> 00:27:14,599

 

595
00:27:14,599 --> 00:27:17,849

 

596
00:27:17,849 --> 00:27:20,190

 

597
00:27:20,190 --> 00:27:22,859

 

598
00:27:22,859 --> 00:27:27,060

 

599
00:27:27,060 --> 00:27:28,769

 

600
00:27:28,769 --> 00:27:30,119

 

601
00:27:30,119 --> 00:27:33,149

 

602
00:27:33,149 --> 00:27:35,430

 

603
00:27:35,430 --> 00:27:36,869

 

604
00:27:36,869 --> 00:27:38,659

 

605
00:27:38,659 --> 00:27:41,700

 

606
00:27:41,700 --> 00:27:43,409

 

607
00:27:43,409 --> 00:27:45,779

 

608
00:27:45,779 --> 00:27:47,580

 

609
00:27:47,580 --> 00:27:50,249

 

610
00:27:50,249 --> 00:27:53,279

 

611
00:27:53,279 --> 00:27:55,019

 

612
00:27:55,019 --> 00:27:56,999

 

613
00:27:56,999 --> 00:27:59,609

 

614
00:27:59,609 --> 00:28:00,930

 

615
00:28:00,930 --> 00:28:02,729

 

616
00:28:02,729 --> 00:28:04,979

 

617
00:28:04,979 --> 00:28:07,859

 

618
00:28:07,859 --> 00:28:12,810

 

619
00:28:12,810 --> 00:28:14,669

 

620
00:28:14,669 --> 00:28:17,849

 

621
00:28:17,849 --> 00:28:20,669

 

622
00:28:20,669 --> 00:28:24,119

 

623
00:28:24,119 --> 00:28:26,190

 

624
00:28:26,190 --> 00:28:31,259

 

625
00:28:31,259 --> 00:28:33,269

 

626
00:28:33,269 --> 00:28:35,099

 

627
00:28:35,099 --> 00:28:36,720

 

628
00:28:36,720 --> 00:28:40,320

 

629
00:28:40,320 --> 00:28:40,330

 

630
00:28:40,330 --> 00:28:40,620


631
00:28:40,620 --> 00:28:44,850

 

632
00:28:44,850 --> 00:28:46,860

 

633
00:28:46,860 --> 00:28:50,240

 

634
00:28:50,240 --> 00:28:55,320

 

635
00:28:55,320 --> 00:28:57,330

 

636
00:28:57,330 --> 00:28:59,970

 

637
00:28:59,970 --> 00:29:03,390

 

638
00:29:03,390 --> 00:29:04,680

 

639
00:29:04,680 --> 00:29:06,450

 

640
00:29:06,450 --> 00:29:09,180

 

641
00:29:09,180 --> 00:29:11,640

 

642
00:29:11,640 --> 00:29:14,640

 

643
00:29:14,640 --> 00:29:17,070

 

644
00:29:17,070 --> 00:29:19,430

 

645
00:29:19,430 --> 00:29:21,840

 

646
00:29:21,840 --> 00:29:23,940

 

647
00:29:23,940 --> 00:29:26,460

 

648
00:29:26,460 --> 00:29:28,230

 

649
00:29:28,230 --> 00:29:31,470

 

650
00:29:31,470 --> 00:29:33,180

 

651
00:29:33,180 --> 00:29:37,890

 

652
00:29:37,890 --> 00:29:40,260

 

653
00:29:40,260 --> 00:29:43,760

 

654
00:29:43,760 --> 00:29:47,130

 

655
00:29:47,130 --> 00:29:51,090

 

656
00:29:51,090 --> 00:29:56,060

 

657
00:29:56,060 --> 00:29:59,820

 

658
00:29:59,820 --> 00:30:05,790

 

659
00:30:05,790 --> 00:30:09,270

 

660
00:30:09,270 --> 00:30:10,980

 

661
00:30:10,980 --> 00:30:15,120

 

662
00:30:15,120 --> 00:30:16,320

 

663
00:30:16,320 --> 00:30:17,640

 

664
00:30:17,640 --> 00:30:20,940

 

665
00:30:20,940 --> 00:30:23,520

 

666
00:30:23,520 --> 00:30:25,560

 

667
00:30:25,560 --> 00:30:28,980

 

668
00:30:28,980 --> 00:30:32,970

 

669
00:30:32,970 --> 00:30:35,670

 

670
00:30:35,670 --> 00:30:39,360

 

671
00:30:39,360 --> 00:30:40,980

 

672
00:30:40,980 --> 00:30:42,510

 

673
00:30:42,510 --> 00:30:43,190

 

674
00:30:43,190 --> 00:30:47,910

 

675
00:30:47,910 --> 00:30:49,940

 

676
00:30:49,940 --> 00:30:52,320

 

677
00:30:52,320 --> 00:30:54,330

 

678
00:30:54,330 --> 00:30:59,680

 

679
00:30:59,680 --> 00:31:01,149

 

680
00:31:01,149 --> 00:31:03,669

 

681
00:31:03,669 --> 00:31:05,649

 

682
00:31:05,649 --> 00:31:07,710

 

683
00:31:07,710 --> 00:31:11,799

 

684
00:31:11,799 --> 00:31:14,860

 

685
00:31:14,860 --> 00:31:17,049

 

686
00:31:17,049 --> 00:31:18,759

 

687
00:31:18,759 --> 00:31:20,830

 

688
00:31:20,830 --> 00:31:21,880

 

689
00:31:21,880 --> 00:31:25,029

 

690
00:31:25,029 --> 00:31:27,460

 

691
00:31:27,460 --> 00:31:30,820

 

692
00:31:30,820 --> 00:31:33,490

 

693
00:31:33,490 --> 00:31:35,080

 

694
00:31:35,080 --> 00:31:36,820

 

695
00:31:36,820 --> 00:31:38,320

 

696
00:31:38,320 --> 00:31:42,009

 

697
00:31:42,009 --> 00:31:45,720

 

698
00:31:45,720 --> 00:31:48,700

 

699
00:31:48,700 --> 00:31:52,930

 

700
00:31:52,930 --> 00:31:56,049

 

701
00:31:56,049 --> 00:31:58,389

 

702
00:31:58,389 --> 00:32:01,750

 

703
00:32:01,750 --> 00:32:05,139

 

704
00:32:05,139 --> 00:32:07,539

 

705
00:32:07,539 --> 00:32:10,990

 

706
00:32:10,990 --> 00:32:15,539

 

707
00:32:15,539 --> 00:32:20,080

 

708
00:32:20,080 --> 00:32:24,909

 

709
00:32:24,909 --> 00:32:27,580

 

710
00:32:27,580 --> 00:32:31,269

 

711
00:32:31,269 --> 00:32:33,879

 

712
00:32:33,879 --> 00:32:35,409

 

713
00:32:35,409 --> 00:32:38,200

 

714
00:32:38,200 --> 00:32:39,879

 

715
00:32:39,879 --> 00:32:41,470

 

716
00:32:41,470 --> 00:32:45,129

 

717
00:32:45,129 --> 00:32:46,570

 

718
00:32:46,570 --> 00:32:48,460

 

719
00:32:48,460 --> 00:32:51,490

 

720
00:32:51,490 --> 00:32:51,500

 

721
00:32:51,500 --> 00:32:53,850


722
00:32:53,850 --> 00:32:57,009

 

723
00:32:57,009 --> 00:33:00,090

 

724
00:33:00,090 --> 00:33:04,570

 

725
00:33:04,570 --> 00:33:06,610

 

726
00:33:06,610 --> 00:33:09,070

 

727
00:33:09,070 --> 00:33:10,869

 

728
00:33:10,869 --> 00:33:11,710

 

729
00:33:11,710 --> 00:33:14,980

 

730
00:33:14,980 --> 00:33:17,680

 

731
00:33:17,680 --> 00:33:20,680

 

732
00:33:20,680 --> 00:33:22,779

 

733
00:33:22,779 --> 00:33:27,759

 

734
00:33:27,759 --> 00:33:30,159

 

735
00:33:30,159 --> 00:33:31,539

 

736
00:33:31,539 --> 00:33:33,430

 

737
00:33:33,430 --> 00:33:42,100

 

738
00:33:42,100 --> 00:33:43,869

 

739
00:33:43,869 --> 00:33:45,519

 

740
00:33:45,519 --> 00:33:47,499

 

741
00:33:47,499 --> 00:33:48,970

 

742
00:33:48,970 --> 00:33:53,980

 

743
00:33:53,980 --> 00:33:55,749

 

744
00:33:55,749 --> 00:34:00,100

 

745
00:34:00,100 --> 00:34:01,659

 

746
00:34:01,659 --> 00:34:03,399

 

747
00:34:03,399 --> 00:34:07,330

 

748
00:34:07,330 --> 00:34:10,480

 

749
00:34:10,480 --> 00:34:14,319

 

750
00:34:14,319 --> 00:34:16,329

 

751
00:34:16,329 --> 00:34:22,480

 

752
00:34:22,480 --> 00:34:24,040

 

753
00:34:24,040 --> 00:34:26,379

 

754
00:34:26,379 --> 00:34:29,050

 

755
00:34:29,050 --> 00:34:31,059

 

756
00:34:31,059 --> 00:34:33,430

 

757
00:34:33,430 --> 00:34:35,290

 

758
00:34:35,290 --> 00:34:38,800

 

759
00:34:38,800 --> 00:34:40,270

 

760
00:34:40,270 --> 00:34:42,550

 

761
00:34:42,550 --> 00:34:44,349

 

762
00:34:44,349 --> 00:34:46,780

 

763
00:34:46,780 --> 00:34:49,030

 

764
00:34:49,030 --> 00:34:50,919

 

765
00:34:50,919 --> 00:34:52,180

 

766
00:34:52,180 --> 00:34:55,930

 

767
00:34:55,930 --> 00:34:58,089

 

768
00:34:58,089 --> 00:34:59,620

 

769
00:34:59,620 --> 00:35:01,870

 

770
00:35:01,870 --> 00:35:04,750

 

771
00:35:04,750 --> 00:35:05,940

 

772
00:35:05,940 --> 00:35:09,240

 

773
00:35:09,240 --> 00:35:11,130

 

774
00:35:11,130 --> 00:35:12,750

 

775
00:35:12,750 --> 00:35:16,380

 

776
00:35:16,380 --> 00:35:18,359

 

777
00:35:18,359 --> 00:35:19,980

 

778
00:35:19,980 --> 00:35:22,140

 

779
00:35:22,140 --> 00:35:24,300

 

780
00:35:24,300 --> 00:35:27,060

 

781
00:35:27,060 --> 00:35:29,760

 

782
00:35:29,760 --> 00:35:31,290

 

783
00:35:31,290 --> 00:35:35,480

 

784
00:35:35,480 --> 00:35:42,690

 

785
00:35:42,690 --> 00:35:45,540

 

786
00:35:45,540 --> 00:35:49,050

 

787
00:35:49,050 --> 00:35:52,140

 

788
00:35:52,140 --> 00:35:56,640

 

789
00:35:56,640 --> 00:35:57,690

 

790
00:35:57,690 --> 00:35:59,849

 

791
00:35:59,849 --> 00:36:01,980

 

792
00:36:01,980 --> 00:36:05,130

 

793
00:36:05,130 --> 00:36:07,560

 

794
00:36:07,560 --> 00:36:11,400

 

795
00:36:11,400 --> 00:36:14,510

 

796
00:36:14,510 --> 00:36:16,950

 

797
00:36:16,950 --> 00:36:19,349

 

798
00:36:19,349 --> 00:36:23,250

 

799
00:36:23,250 --> 00:36:25,920

 

800
00:36:25,920 --> 00:36:29,099

 

801
00:36:29,099 --> 00:36:32,730

 

802
00:36:32,730 --> 00:36:35,579

 

803
00:36:35,579 --> 00:36:37,370

 

804
00:36:37,370 --> 00:36:42,349

 

805
00:36:42,349 --> 00:36:46,740

 

806
00:36:46,740 --> 00:36:48,210

 

807
00:36:48,210 --> 00:36:50,609

 

808
00:36:50,609 --> 00:36:52,530

 

809
00:36:52,530 --> 00:36:54,510

 

810
00:36:54,510 --> 00:36:56,640

 

811
00:36:56,640 --> 00:36:59,400

 

812
00:36:59,400 --> 00:37:01,440

 

813
00:37:01,440 --> 00:37:02,640

 

814
00:37:02,640 --> 00:37:06,450

 

815
00:37:06,450 --> 00:37:07,680

 

816
00:37:07,680 --> 00:37:09,420

 

817
00:37:09,420 --> 00:37:14,960

 

818
00:37:14,960 --> 00:37:19,170

 

819
00:37:19,170 --> 00:37:21,540

 

820
00:37:21,540 --> 00:37:25,920

 

821
00:37:25,920 --> 00:37:25,930

 

822
00:37:25,930 --> 00:37:27,200


823
00:37:27,200 --> 00:37:29,790

 

824
00:37:29,790 --> 00:37:34,920

 

825
00:37:34,920 --> 00:37:36,960

 

826
00:37:36,960 --> 00:37:41,099

 

827
00:37:41,099 --> 00:37:44,970

 

828
00:37:44,970 --> 00:37:46,800

 

829
00:37:46,800 --> 00:37:51,720

 

830
00:37:51,720 --> 00:37:55,190

 

831
00:37:55,190 --> 00:37:57,920

 

832
00:37:57,920 --> 00:38:01,849

 

833
00:38:01,849 --> 00:38:06,890

 

834
00:38:06,890 --> 00:38:10,760

 

835
00:38:10,760 --> 00:38:13,730

 

836
00:38:13,730 --> 00:38:15,980

 

837
00:38:15,980 --> 00:38:17,990

 

838
00:38:17,990 --> 00:38:21,010

 

839
00:38:21,010 --> 00:38:23,300

 

840
00:38:23,300 --> 00:38:23,310

 

841
00:38:23,310 --> 00:38:23,630


842
00:38:23,630 --> 00:38:25,310

 

843
00:38:25,310 --> 00:38:28,190

 

844
00:38:28,190 --> 00:38:30,349

 

845
00:38:30,349 --> 00:38:31,880

 

846
00:38:31,880 --> 00:38:34,190

 

847
00:38:34,190 --> 00:38:36,500

 

848
00:38:36,500 --> 00:38:39,829

 

849
00:38:39,829 --> 00:38:41,540

 

850
00:38:41,540 --> 00:38:42,200

 

851
00:38:42,200 --> 00:38:46,220

 

852
00:38:46,220 --> 00:38:47,900

 

853
00:38:47,900 --> 00:38:50,930

 

854
00:38:50,930 --> 00:38:54,650

 

855
00:38:54,650 --> 00:38:57,770

 

856
00:38:57,770 --> 00:38:59,660

 

857
00:38:59,660 --> 00:39:02,059

 

858
00:39:02,059 --> 00:39:07,790

 

859
00:39:07,790 --> 00:39:11,359

 

860
00:39:11,359 --> 00:39:13,099

 

861
00:39:13,099 --> 00:39:14,690

 

862
00:39:14,690 --> 00:39:18,410

 

863
00:39:18,410 --> 00:39:21,010

 

864
00:39:21,010 --> 00:39:23,480

 

865
00:39:23,480 --> 00:39:25,370

 

866
00:39:25,370 --> 00:39:26,630

 

867
00:39:26,630 --> 00:39:28,550

 

868
00:39:28,550 --> 00:39:30,020

 

869
00:39:30,020 --> 00:39:32,089

 

870
00:39:32,089 --> 00:39:35,390

 

871
00:39:35,390 --> 00:39:39,450

 

872
00:39:39,450 --> 00:39:42,990

 

873
00:39:42,990 --> 00:39:47,809

 

874
00:39:47,809 --> 00:39:54,690

 

875
00:39:54,690 --> 00:39:56,599

 

876
00:39:56,599 --> 00:39:58,680

 

877
00:39:58,680 --> 00:40:01,440

 

878
00:40:01,440 --> 00:40:03,000

 

879
00:40:03,000 --> 00:40:04,170

 

880
00:40:04,170 --> 00:40:06,260

 

881
00:40:06,260 --> 00:40:09,480

 

882
00:40:09,480 --> 00:40:11,549

 

883
00:40:11,549 --> 00:40:14,370

 

884
00:40:14,370 --> 00:40:16,829

 

885
00:40:16,829 --> 00:40:20,250

 

886
00:40:20,250 --> 00:40:24,720

 

887
00:40:24,720 --> 00:40:28,049

 

888
00:40:28,049 --> 00:40:30,210

 

889
00:40:30,210 --> 00:40:32,450

 

890
00:40:32,450 --> 00:40:35,400

 

891
00:40:35,400 --> 00:40:39,540

 

892
00:40:39,540 --> 00:40:43,380

 

893
00:40:43,380 --> 00:40:46,440

 

894
00:40:46,440 --> 00:40:49,349

 

895
00:40:49,349 --> 00:40:54,569

 

896
00:40:54,569 --> 00:40:57,839

 

897
00:40:57,839 --> 00:41:01,069

 

898
00:41:01,069 --> 00:41:05,339

 

899
00:41:05,339 --> 00:41:08,730

 

900
00:41:08,730 --> 00:41:11,160

 

901
00:41:11,160 --> 00:41:13,049

 

902
00:41:13,049 --> 00:41:14,789

 

903
00:41:14,789 --> 00:41:19,370

 

904
00:41:19,370 --> 00:41:31,370

 

905
00:41:31,370 --> 00:41:36,700

 

906
00:41:36,700 --> 00:41:36,710

 

907
00:41:36,710 --> 00:41:39,450


908
00:41:39,450 --> 00:41:41,680

 

909
00:41:41,680 --> 00:41:44,109

 

910
00:41:44,109 --> 00:41:47,890

 

911
00:41:47,890 --> 00:41:50,859

 

912
00:41:50,859 --> 00:41:55,260

 

913
00:41:55,260 --> 00:41:58,690

 

914
00:41:58,690 --> 00:42:00,460

 

915
00:42:00,460 --> 00:42:02,049

 

916
00:42:02,049 --> 00:42:02,059

 

917
00:42:02,059 --> 00:42:02,559


918
00:42:02,559 --> 00:42:04,539

 

919
00:42:04,539 --> 00:42:06,339

 

920
00:42:06,339 --> 00:42:07,690

 

921
00:42:07,690 --> 00:42:09,190

 

922
00:42:09,190 --> 00:42:10,809

 

923
00:42:10,809 --> 00:42:12,460

 

924
00:42:12,460 --> 00:42:14,170

 

925
00:42:14,170 --> 00:42:18,339

 

926
00:42:18,339 --> 00:42:19,990

 

927
00:42:19,990 --> 00:42:23,940

 

928
00:42:23,940 --> 00:42:27,609

 

929
00:42:27,609 --> 00:42:31,029

 

930
00:42:31,029 --> 00:42:32,339

 

931
00:42:32,339 --> 00:42:34,779

 

932
00:42:34,779 --> 00:42:36,279

 

933
00:42:36,279 --> 00:42:43,180

 

934
00:42:43,180 --> 00:42:44,799

 

935
00:42:44,799 --> 00:42:47,410

 

936
00:42:47,410 --> 00:42:49,329

 

937
00:42:49,329 --> 00:42:51,549

 

938
00:42:51,549 --> 00:42:56,769

 

939
00:42:56,769 --> 00:42:58,420

 

940
00:42:58,420 --> 00:43:00,400

 

941
00:43:00,400 --> 00:43:01,510

 

942
00:43:01,510 --> 00:43:03,549

 

943
00:43:03,549 --> 00:43:07,120

 

944
00:43:07,120 --> 00:43:09,849

 

945
00:43:09,849 --> 00:43:11,140

 

946
00:43:11,140 --> 00:43:12,910

 

947
00:43:12,910 --> 00:43:16,750

 

948
00:43:16,750 --> 00:43:20,019

 

949
00:43:20,019 --> 00:43:22,269

 

950
00:43:22,269 --> 00:43:24,339

 

951
00:43:24,339 --> 00:43:27,269

 

952
00:43:27,269 --> 00:43:31,059

 

953
00:43:31,059 --> 00:43:33,930

 

954
00:43:33,930 --> 00:43:36,849

 

955
00:43:36,849 --> 00:43:39,579

 

956
00:43:39,579 --> 00:43:44,230

 

957
00:43:44,230 --> 00:43:46,150

 

958
00:43:46,150 --> 00:43:47,859

 

959
00:43:47,859 --> 00:43:50,079

 

960
00:43:50,079 --> 00:43:51,520

 

961
00:43:51,520 --> 00:43:54,460

 

962
00:43:54,460 --> 00:43:56,800

 

963
00:43:56,800 --> 00:44:00,850

 

964
00:44:00,850 --> 00:44:03,430

 

965
00:44:03,430 --> 00:44:06,520

 

966
00:44:06,520 --> 00:44:12,730

 

967
00:44:12,730 --> 00:44:15,100

 

968
00:44:15,100 --> 00:44:17,470

 

969
00:44:17,470 --> 00:44:19,600

 

970
00:44:19,600 --> 00:44:22,390

 

971
00:44:22,390 --> 00:44:24,460

 

972
00:44:24,460 --> 00:44:26,950

 

973
00:44:26,950 --> 00:44:28,180

 

974
00:44:28,180 --> 00:44:30,850

 

975
00:44:30,850 --> 00:44:32,830

 

976
00:44:32,830 --> 00:44:38,110

 

977
00:44:38,110 --> 00:44:40,090

 

978
00:44:40,090 --> 00:44:42,790

 

979
00:44:42,790 --> 00:44:46,990

 

980
00:44:46,990 --> 00:44:48,790

 

981
00:44:48,790 --> 00:44:50,650

 

982
00:44:50,650 --> 00:44:57,700

 

983
00:44:57,700 --> 00:45:00,670

 

984
00:45:00,670 --> 00:45:02,590

 

985
00:45:02,590 --> 00:45:04,720

 

986
00:45:04,720 --> 00:45:07,630

 

987
00:45:07,630 --> 00:45:12,370

 

988
00:45:12,370 --> 00:45:14,980

 

989
00:45:14,980 --> 00:45:17,640

 

990
00:45:17,640 --> 00:45:20,260

 

991
00:45:20,260 --> 00:45:24,810

 

992
00:45:24,810 --> 00:45:28,300

 

993
00:45:28,300 --> 00:45:30,580

 

994
00:45:30,580 --> 00:45:33,850

 

995
00:45:33,850 --> 00:45:35,740

 

996
00:45:35,740 --> 00:45:38,950

 

997
00:45:38,950 --> 00:45:42,610

 

998
00:45:42,610 --> 00:45:45,340

 

999
00:45:45,340 --> 00:45:50,329

 

1000
00:45:50,329 --> 00:45:54,469

 

1001
00:45:54,469 --> 00:45:56,150

 

1002
00:45:56,150 --> 00:45:58,370

 

1003
00:45:58,370 --> 00:45:59,989

 

1004
00:45:59,989 --> 00:46:02,779

 

1005
00:46:02,779 --> 00:46:05,630

 

1006
00:46:05,630 --> 00:46:07,759

 

1007
00:46:07,759 --> 00:46:08,689

 

1008
00:46:08,689 --> 00:46:11,850

 

1009
00:46:11,850 --> 00:46:11,860

 

1010
00:46:11,860 --> 00:46:14,730


1011
00:46:14,730 --> 00:46:18,120

 

1012
00:46:18,120 --> 00:46:18,130

 

1013
00:46:18,130 --> 00:46:18,420


1014
00:46:18,420 --> 00:46:20,370

 

1015
00:46:20,370 --> 00:46:24,359

 

1016
00:46:24,359 --> 00:46:26,130

 

1017
00:46:26,130 --> 00:46:28,079

 

1018
00:46:28,079 --> 00:46:29,970

 

1019
00:46:29,970 --> 00:46:31,950

 

1020
00:46:31,950 --> 00:46:35,220

 

1021
00:46:35,220 --> 00:46:38,220

 

1022
00:46:38,220 --> 00:46:39,780

 

1023
00:46:39,780 --> 00:46:52,140

 

1024
00:46:52,140 --> 00:46:55,700

 

1025
00:46:55,700 --> 00:46:57,870

 

1026
00:46:57,870 --> 00:46:59,160

 

1027
00:46:59,160 --> 00:47:02,720

 

1028
00:47:02,720 --> 00:47:04,589

 

1029
00:47:04,589 --> 00:47:06,240

 

1030
00:47:06,240 --> 00:47:10,859

 

1031
00:47:10,859 --> 00:47:12,870

 

1032
00:47:12,870 --> 00:47:15,390

 

1033
00:47:15,390 --> 00:47:20,110

 

1034
00:47:20,110 --> 00:47:22,660

 

1035
00:47:22,660 --> 00:47:25,300

 

1036
00:47:25,300 --> 00:47:26,650

 

1037
00:47:26,650 --> 00:47:32,340

 

1038
00:47:32,340 --> 00:47:37,720

 

1039
00:47:37,720 --> 00:47:40,720

 

1040
00:47:40,720 --> 00:47:45,250

 

1041
00:47:45,250 --> 00:47:48,340

 

1042
00:47:48,340 --> 00:47:50,950

 

1043
00:47:50,950 --> 00:47:54,250

 

1044
00:47:54,250 --> 00:47:56,110

 

1045
00:47:56,110 --> 00:47:58,060

 

1046
00:47:58,060 --> 00:47:59,650

 

1047
00:47:59,650 --> 00:48:03,640

 

1048
00:48:03,640 --> 00:48:09,760

 

1049
00:48:09,760 --> 00:48:11,320

 

1050
00:48:11,320 --> 00:48:12,970

 

1051
00:48:12,970 --> 00:48:15,070

 

1052
00:48:15,070 --> 00:48:18,310

 

1053
00:48:18,310 --> 00:48:22,690

 

1054
00:48:22,690 --> 00:48:28,600

 

1055
00:48:28,600 --> 00:48:29,950

 

1056
00:48:29,950 --> 00:48:33,130

 

1057
00:48:33,130 --> 00:48:34,600

 

1058
00:48:34,600 --> 00:48:36,550

 

1059
00:48:36,550 --> 00:48:38,830

 

1060
00:48:38,830 --> 00:48:40,540

 

1061
00:48:40,540 --> 00:48:43,030

 

1062
00:48:43,030 --> 00:48:46,480

 

1063
00:48:46,480 --> 00:48:48,790

 

1064
00:48:48,790 --> 00:48:50,860

 

1065
00:48:50,860 --> 00:48:53,980

 

1066
00:48:53,980 --> 00:48:56,010

 

1067
00:48:56,010 --> 00:49:01,660

 

1068
00:49:01,660 --> 00:49:05,070

 

1069
00:49:05,070 --> 00:49:07,390

 

1070
00:49:07,390 --> 00:49:09,820

 

1071
00:49:09,820 --> 00:49:12,870

 

1072
00:49:12,870 --> 00:49:17,320

 

1073
00:49:17,320 --> 00:49:19,600

 

1074
00:49:19,600 --> 00:49:22,030

 

1075
00:49:22,030 --> 00:49:23,590

 

1076
00:49:23,590 --> 00:49:28,390

 

1077
00:49:28,390 --> 00:49:29,830

 

1078
00:49:29,830 --> 00:49:32,710

 

1079
00:49:32,710 --> 00:49:35,020

 

1080
00:49:35,020 --> 00:49:38,260

 

1081
00:49:38,260 --> 00:49:39,610

 

1082
00:49:39,610 --> 00:49:42,880

 

1083
00:49:42,880 --> 00:49:52,000

 

1084
00:49:52,000 --> 00:49:59,980

 

1085
00:49:59,980 --> 00:50:03,420

 

1086
00:50:03,420 --> 00:50:07,780

 

1087
00:50:07,780 --> 00:50:09,400

 

1088
00:50:09,400 --> 00:50:13,020

 

1089
00:50:13,020 --> 00:50:16,870

 

1090
00:50:16,870 --> 00:50:20,400

 

1091
00:50:20,400 --> 00:50:23,110

 

1092
00:50:23,110 --> 00:50:26,740

 

1093
00:50:26,740 --> 00:50:28,870

 

1094
00:50:28,870 --> 00:50:30,700

 

1095
00:50:30,700 --> 00:50:33,270

 

1096
00:50:33,270 --> 00:50:35,980

 

1097
00:50:35,980 --> 00:50:37,960

 

1098
00:50:37,960 --> 00:50:43,390

 

1099
00:50:43,390 --> 00:50:45,520

 

1100
00:50:45,520 --> 00:50:46,780

 

1101
00:50:46,780 --> 00:50:49,720

 

1102
00:50:49,720 --> 00:50:56,110

 

1103
00:50:56,110 --> 00:51:02,020

 

1104
00:51:02,020 --> 00:51:04,570

 

1105
00:51:04,570 --> 00:51:09,040

 

1106
00:51:09,040 --> 00:51:13,600

 

1107
00:51:13,600 --> 00:51:14,740

 

1108
00:51:14,740 --> 00:51:16,780

 

1109
00:51:16,780 --> 00:51:19,120

 

1110
00:51:19,120 --> 00:51:22,240

 

1111
00:51:22,240 --> 00:51:25,900

 

1112
00:51:25,900 --> 00:51:28,270

 

1113
00:51:28,270 --> 00:51:29,890

 

1114
00:51:29,890 --> 00:51:37,590

 

1115
00:51:37,590 --> 00:51:39,850

 

1116
00:51:39,850 --> 00:51:39,860

 

1117
00:51:39,860 --> 00:51:50,960


1118
00:51:50,960 --> 00:51:53,120

 

1119
00:51:53,120 --> 00:51:55,490

 

1120
00:51:55,490 --> 00:51:58,520

 

1121
00:51:58,520 --> 00:52:00,140

 

1122
00:52:00,140 --> 00:52:01,490

 

1123
00:52:01,490 --> 00:52:02,930

 

1124
00:52:02,930 --> 00:52:05,690

 

1125
00:52:05,690 --> 00:52:08,690

 

1126
00:52:08,690 --> 00:52:11,120

 

1127
00:52:11,120 --> 00:52:12,950

 

1128
00:52:12,950 --> 00:52:17,059

 

1129
00:52:17,059 --> 00:52:20,000

 

1130
00:52:20,000 --> 00:52:22,099

 

1131
00:52:22,099 --> 00:52:23,930

 

1132
00:52:23,930 --> 00:52:26,990

 

1133
00:52:26,990 --> 00:52:29,329

 

1134
00:52:29,329 --> 00:52:33,470

 

1135
00:52:33,470 --> 00:52:38,349

 

1136
00:52:38,349 --> 00:52:41,660

 

1137
00:52:41,660 --> 00:52:43,609

 

1138
00:52:43,609 --> 00:52:44,990

 

1139
00:52:44,990 --> 00:52:49,760

 

1140
00:52:49,760 --> 00:52:52,460

 

1141
00:52:52,460 --> 00:53:00,260

 

1142
00:53:00,260 --> 00:53:04,480

 

1143
00:53:04,480 --> 00:53:07,849

 

1144
00:53:07,849 --> 00:53:10,519

 

1145
00:53:10,519 --> 00:53:12,049

 

1146
00:53:12,049 --> 00:53:19,910

 

1147
00:53:19,910 --> 00:53:21,470

 

1148
00:53:21,470 --> 00:53:23,809

 

1149
00:53:23,809 --> 00:53:23,819

 

1150
00:53:23,819 --> 00:53:24,440


1151
00:53:24,440 --> 00:53:26,809

 

1152
00:53:26,809 --> 00:53:28,609

 

1153
00:53:28,609 --> 00:53:29,750

 

1154
00:53:29,750 --> 00:53:31,880

 

1155
00:53:31,880 --> 00:53:33,589

 

1156
00:53:33,589 --> 00:53:37,299

 

1157
00:53:37,299 --> 00:53:41,630

 

1158
00:53:41,630 --> 00:53:43,519

 

1159
00:53:43,519 --> 00:53:49,250

 

1160
00:53:49,250 --> 00:53:53,930

 

1161
00:53:53,930 --> 00:53:55,940

 

1162
00:53:55,940 --> 00:54:01,630

 

1163
00:54:01,630 --> 00:54:04,359

 

1164
00:54:04,359 --> 00:54:06,819

 

1165
00:54:06,819 --> 00:54:08,799

 

1166
00:54:08,799 --> 00:54:10,989

 

1167
00:54:10,989 --> 00:54:13,150

 

1168
00:54:13,150 --> 00:54:17,620

 

1169
00:54:17,620 --> 00:54:20,890

 

1170
00:54:20,890 --> 00:54:23,620

 

1171
00:54:23,620 --> 00:54:32,200

 

1172
00:54:32,200 --> 00:54:44,319

 

1173
00:54:44,319 --> 00:54:46,390

 

1174
00:54:46,390 --> 00:54:48,249

 

1175
00:54:48,249 --> 00:54:51,489

 

1176
00:54:51,489 --> 00:54:52,930

 

1177
00:54:52,930 --> 00:54:55,870

 

1178
00:54:55,870 --> 00:54:57,910

 

1179
00:54:57,910 --> 00:55:02,259

 

1180
00:55:02,259 --> 00:55:05,529

 

1181
00:55:05,529 --> 00:55:09,190

 

1182
00:55:09,190 --> 00:55:11,019

 

1183
00:55:11,019 --> 00:55:13,630

 

1184
00:55:13,630 --> 00:55:17,549

 

1185
00:55:17,549 --> 00:55:20,410

 

1186
00:55:20,410 --> 00:55:23,019

 

1187
00:55:23,019 --> 00:55:25,509

 

1188
00:55:25,509 --> 00:55:28,089

 

1189
00:55:28,089 --> 00:55:30,400

 

1190
00:55:30,400 --> 00:55:31,870

 

1191
00:55:31,870 --> 00:55:35,589

 

1192
00:55:35,589 --> 00:55:39,039

 

1193
00:55:39,039 --> 00:55:43,329

 

1194
00:55:43,329 --> 00:55:45,309

 

1195
00:55:45,309 --> 00:55:46,930

 

1196
00:55:46,930 --> 00:55:50,739

 

1197
00:55:50,739 --> 00:55:51,370

 

1198
00:55:51,370 --> 00:55:55,779

 

1199
00:55:55,779 --> 00:55:57,759

 

1200
00:55:57,759 --> 00:56:04,490

 

1201
00:56:04,490 --> 00:56:11,750

 

1202
00:56:11,750 --> 00:56:13,280

 

1203
00:56:13,280 --> 00:56:16,430

 

1204
00:56:16,430 --> 00:56:21,320

 

1205
00:56:21,320 --> 00:56:24,650

 

1206
00:56:24,650 --> 00:56:28,580

 

1207
00:56:28,580 --> 00:56:31,960

 

1208
00:56:31,960 --> 00:56:35,089

 

1209
00:56:35,089 --> 00:56:35,099

 

1210
00:56:35,099 --> 00:56:37,420


1211
00:56:37,420 --> 00:56:39,589

 

1212
00:56:39,589 --> 00:56:41,800

 

1213
00:56:41,800 --> 00:56:44,120

 

1214
00:56:44,120 --> 00:56:45,890

 

1215
00:56:45,890 --> 00:56:45,900

 

1216
00:56:45,900 --> 00:56:46,250


1217
00:56:46,250 --> 00:56:47,690

 

1218
00:56:47,690 --> 00:56:51,290

 

1219
00:56:51,290 --> 00:56:54,050

 

1220
00:56:54,050 --> 00:56:55,970

 

1221
00:56:55,970 --> 00:56:57,950

 

1222
00:56:57,950 --> 00:56:59,990

 

1223
00:56:59,990 --> 00:57:01,609

 

1224
00:57:01,609 --> 00:57:03,859

 

1225
00:57:03,859 --> 00:57:07,220

 

1226
00:57:07,220 --> 00:57:11,329

 

1227
00:57:11,329 --> 00:57:13,900

 

1228
00:57:13,900 --> 00:57:16,460

 

1229
00:57:16,460 --> 00:57:19,520

 

1230
00:57:19,520 --> 00:57:23,089

 

1231
00:57:23,089 --> 00:57:26,480

 

1232
00:57:26,480 --> 00:57:29,720

 

1233
00:57:29,720 --> 00:57:33,260

 

1234
00:57:33,260 --> 00:57:36,290

 

1235
00:57:36,290 --> 00:57:38,359

 

1236
00:57:38,359 --> 00:57:41,180

 

1237
00:57:41,180 --> 00:57:42,530

 

1238
00:57:42,530 --> 00:57:44,089

 

1239
00:57:44,089 --> 00:57:46,190

 

1240
00:57:46,190 --> 00:57:48,560

 

1241
00:57:48,560 --> 00:57:50,900

 

1242
00:57:50,900 --> 00:57:52,670

 

1243
00:57:52,670 --> 00:57:56,030

 

1244
00:57:56,030 --> 00:58:00,320

 

1245
00:58:00,320 --> 00:58:05,990

 

1246
00:58:05,990 --> 00:58:13,609

 

1247
00:58:13,609 --> 00:58:26,339

 

1248
00:58:26,339 --> 00:58:28,650

 

1249
00:58:28,650 --> 00:58:30,480

 

1250
00:58:30,480 --> 00:58:32,910

 

1251
00:58:32,910 --> 00:58:34,770

 

1252
00:58:34,770 --> 00:58:38,160

 

1253
00:58:38,160 --> 00:58:41,339

 

1254
00:58:41,339 --> 00:58:43,859

 

1255
00:58:43,859 --> 00:58:45,720

 

1256
00:58:45,720 --> 00:58:51,230

 

1257
00:58:51,230 --> 00:58:55,880

 

1258
00:58:55,880 --> 00:59:00,770

 

1259
00:59:00,770 --> 00:59:04,310

 

1260
00:59:04,310 --> 00:59:06,950

 

1261
00:59:06,950 --> 00:59:09,200

 

1262
00:59:09,200 --> 00:59:10,640

 

1263
00:59:10,640 --> 00:59:12,920

 

1264
00:59:12,920 --> 00:59:14,720

 

1265
00:59:14,720 --> 00:59:16,400

 

1266
00:59:16,400 --> 00:59:26,020

 

1267
00:59:26,020 --> 00:59:28,280

 

1268
00:59:28,280 --> 00:59:29,930

 

1269
00:59:29,930 --> 00:59:31,850

 

1270
00:59:31,850 --> 00:59:33,230

 

1271
00:59:33,230 --> 00:59:34,730

 

1272
00:59:34,730 --> 00:59:36,890

 

1273
00:59:36,890 --> 00:59:38,210

 

1274
00:59:38,210 --> 00:59:39,560

 

1275
00:59:39,560 --> 00:59:41,210

 

1276
00:59:41,210 --> 00:59:43,250

 

1277
00:59:43,250 --> 00:59:44,720

 

1278
00:59:44,720 --> 00:59:47,300

 

1279
00:59:47,300 --> 00:59:49,610

 

1280
00:59:49,610 --> 00:59:51,710

 

1281
00:59:51,710 --> 00:59:53,390

 

1282
00:59:53,390 --> 00:59:55,190

 

1283
00:59:55,190 --> 00:59:59,420

 

1284
00:59:59,420 --> 01:00:01,760

 

1285
01:00:01,760 --> 01:00:06,230

 

1286
01:00:06,230 --> 01:00:09,580

 

1287
01:00:09,580 --> 01:00:12,710

 

1288
01:00:12,710 --> 01:00:14,330

 

1289
01:00:14,330 --> 01:00:17,060

 

1290
01:00:17,060 --> 01:00:20,450

 

1291
01:00:20,450 --> 01:00:22,580

 

1292
01:00:22,580 --> 01:00:24,980

 

1293
01:00:24,980 --> 01:00:26,720

 

1294
01:00:26,720 --> 01:00:28,460

 

1295
01:00:28,460 --> 01:00:31,880

 

1296
01:00:31,880 --> 01:00:33,950

 

1297
01:00:33,950 --> 01:00:37,790

 

1298
01:00:37,790 --> 01:00:40,820

 

1299
01:00:40,820 --> 01:00:43,100

 

1300
01:00:43,100 --> 01:00:44,900

 

1301
01:00:44,900 --> 01:00:48,710

 

1302
01:00:48,710 --> 01:00:51,440

 

1303
01:00:51,440 --> 01:00:53,440

 

1304
01:00:53,440 --> 01:00:55,640

 

1305
01:00:55,640 --> 01:01:00,980

 

1306
01:01:00,980 --> 01:01:04,400

 

1307
01:01:04,400 --> 01:01:07,100

 

1308
01:01:07,100 --> 01:01:10,070

 

1309
01:01:10,070 --> 01:01:12,140

 

1310
01:01:12,140 --> 01:01:16,330

 

1311
01:01:16,330 --> 01:01:20,690

 

1312
01:01:20,690 --> 01:01:26,420

 

1313
01:01:26,420 --> 01:01:34,220

 

1314
01:01:34,220 --> 01:01:36,230

 

1315
01:01:36,230 --> 01:01:38,780

 

1316
01:01:38,780 --> 01:01:39,830

 

1317
01:01:39,830 --> 01:01:42,410

 

1318
01:01:42,410 --> 01:01:45,920

 

1319
01:01:45,920 --> 01:01:48,560

 

1320
01:01:48,560 --> 01:01:50,900

 

1321
01:01:50,900 --> 01:01:54,200

 

1322
01:01:54,200 --> 01:01:56,840

 

1323
01:01:56,840 --> 01:02:00,860

 

1324
01:02:00,860 --> 01:02:02,210

 

1325
01:02:02,210 --> 01:02:08,660

 

1326
01:02:08,660 --> 01:02:08,670

 

1327
01:02:08,670 --> 01:02:13,840


1328
01:02:13,840 --> 01:02:16,610

 

1329
01:02:16,610 --> 01:02:19,790

 

1330
01:02:19,790 --> 01:02:21,800

 

1331
01:02:21,800 --> 01:02:26,390

 

1332
01:02:26,390 --> 01:02:32,870

 

1333
01:02:32,870 --> 01:02:35,480

 

1334
01:02:35,480 --> 01:02:38,750

 

1335
01:02:38,750 --> 01:02:41,180

 

1336
01:02:41,180 --> 01:02:43,460

 

1337
01:02:43,460 --> 01:02:45,800

 

1338
01:02:45,800 --> 01:02:50,090

 

1339
01:02:50,090 --> 01:02:50,930

 

1340
01:02:50,930 --> 01:02:53,570

 

1341
01:02:53,570 --> 01:02:54,860

 

1342
01:02:54,860 --> 01:02:56,870

 

1343
01:02:56,870 --> 01:02:59,810

 

1344
01:02:59,810 --> 01:03:04,400

 

1345
01:03:04,400 --> 01:03:05,690

 

1346
01:03:05,690 --> 01:03:07,730

 

1347
01:03:07,730 --> 01:03:11,510

 

1348
01:03:11,510 --> 01:03:14,720

 

1349
01:03:14,720 --> 01:03:16,910

 

1350
01:03:16,910 --> 01:03:19,310

 

1351
01:03:19,310 --> 01:03:26,380

 

1352
01:03:26,380 --> 01:03:29,000

 

1353
01:03:29,000 --> 01:03:31,790

 

1354
01:03:31,790 --> 01:03:35,870

 

1355
01:03:35,870 --> 01:03:41,270

 

1356
01:03:41,270 --> 01:03:46,670

 

1357
01:03:46,670 --> 01:03:50,450

 

1358
01:03:50,450 --> 01:03:52,040

 

1359
01:03:52,040 --> 01:03:55,550

 

1360
01:03:55,550 --> 01:04:01,150

 

1361
01:04:01,150 --> 01:04:07,120

 

1362
01:04:07,120 --> 01:04:11,020

 

1363
01:04:11,020 --> 01:04:13,750

 

1364
01:04:13,750 --> 01:04:15,310

 

1365
01:04:15,310 --> 01:04:17,800

 

1366
01:04:17,800 --> 01:04:20,170

 

1367
01:04:20,170 --> 01:04:21,250

 

1368
01:04:21,250 --> 01:04:23,140

 

1369
01:04:23,140 --> 01:04:25,120

 

1370
01:04:25,120 --> 01:04:27,310

 

1371
01:04:27,310 --> 01:04:29,260

 

1372
01:04:29,260 --> 01:04:31,180

 

1373
01:04:31,180 --> 01:04:34,170

 

1374
01:04:34,170 --> 01:04:36,940

 

1375
01:04:36,940 --> 01:04:39,610

 

1376
01:04:39,610 --> 01:04:44,730

 

1377
01:04:44,730 --> 01:04:47,080

 

1378
01:04:47,080 --> 01:04:48,940

 

1379
01:04:48,940 --> 01:04:51,730

 

1380
01:04:51,730 --> 01:04:54,580

 

1381
01:04:54,580 --> 01:04:55,870

 

1382
01:04:55,870 --> 01:04:57,880

 

1383
01:04:57,880 --> 01:04:59,560

 

1384
01:04:59,560 --> 01:05:01,570

 

1385
01:05:01,570 --> 01:05:02,350

 

1386
01:05:02,350 --> 01:05:04,240

 

1387
01:05:04,240 --> 01:05:05,710

 

1388
01:05:05,710 --> 01:05:07,930

 

1389
01:05:07,930 --> 01:05:10,300

 

1390
01:05:10,300 --> 01:05:11,740

 

1391
01:05:11,740 --> 01:05:14,230

 

1392
01:05:14,230 --> 01:05:15,340

 

1393
01:05:15,340 --> 01:05:17,440

 

1394
01:05:17,440 --> 01:05:20,800

 

1395
01:05:20,800 --> 01:05:22,900

 

1396
01:05:22,900 --> 01:05:25,660

 

1397
01:05:25,660 --> 01:05:28,530

 

1398
01:05:28,530 --> 01:05:31,720

 

1399
01:05:31,720 --> 01:05:35,080

 

1400
01:05:35,080 --> 01:05:37,960

 

1401
01:05:37,960 --> 01:05:42,910

 

1402
01:05:42,910 --> 01:05:42,920

 

1403
01:05:42,920 --> 01:05:44,190


1404
01:05:44,190 --> 01:05:47,470

 

1405
01:05:47,470 --> 01:05:50,410

 

1406
01:05:50,410 --> 01:05:52,060

 

1407
01:05:52,060 --> 01:05:55,660

 

1408
01:05:55,660 --> 01:05:58,900

 

1409
01:05:58,900 --> 01:06:01,240

 

1410
01:06:01,240 --> 01:06:03,070

 

1411
01:06:03,070 --> 01:06:05,290

 

1412
01:06:05,290 --> 01:06:08,249

 

1413
01:06:08,249 --> 01:06:13,120

 

1414
01:06:13,120 --> 01:06:15,249

 

1415
01:06:15,249 --> 01:06:16,989

 

1416
01:06:16,989 --> 01:06:20,709

 

1417
01:06:20,709 --> 01:06:23,979

 

1418
01:06:23,979 --> 01:06:26,589

 

1419
01:06:26,589 --> 01:06:28,660

 

1420
01:06:28,660 --> 01:06:31,420

 

1421
01:06:31,420 --> 01:06:35,499

 

1422
01:06:35,499 --> 01:06:37,209

 

1423
01:06:37,209 --> 01:06:38,949

 

1424
01:06:38,949 --> 01:06:40,930

 

1425
01:06:40,930 --> 01:06:45,099

 

1426
01:06:45,099 --> 01:06:48,630

 

1427
01:06:48,630 --> 01:06:51,430

 

1428
01:06:51,430 --> 01:06:52,839

 

1429
01:06:52,839 --> 01:06:54,640

 

1430
01:06:54,640 --> 01:06:58,589

 

1431
01:06:58,589 --> 01:07:09,939

 

1432
01:07:09,939 --> 01:07:12,939

 

1433
01:07:12,939 --> 01:07:17,039

 

1434
01:07:17,039 --> 01:07:20,289

 

1435
01:07:20,289 --> 01:07:24,160

 

1436
01:07:24,160 --> 01:07:28,420

 

1437
01:07:28,420 --> 01:07:31,209

 

1438
01:07:31,209 --> 01:07:34,059

 

1439
01:07:34,059 --> 01:07:36,999

 

1440
01:07:36,999 --> 01:07:39,459

 

1441
01:07:39,459 --> 01:07:41,019

 

1442
01:07:41,019 --> 01:07:44,170

 

1443
01:07:44,170 --> 01:07:46,439

 

1444
01:07:46,439 --> 01:07:51,489

 

1445
01:07:51,489 --> 01:07:53,109

 

1446
01:07:53,109 --> 01:07:54,849

 

1447
01:07:54,849 --> 01:07:56,380

 

1448
01:07:56,380 --> 01:07:59,969

 

1449
01:07:59,969 --> 01:08:02,650

 

1450
01:08:02,650 --> 01:08:05,640

 

1451
01:08:05,640 --> 01:08:08,949

 

1452
01:08:08,949 --> 01:08:13,900

 

1453
01:08:13,900 --> 01:08:15,969

 

1454
01:08:15,969 --> 01:08:17,249

 

1455
01:08:17,249 --> 01:08:20,709

 

1456
01:08:20,709 --> 01:08:22,979

 

1457
01:08:22,979 --> 01:08:25,660

 

1458
01:08:25,660 --> 01:08:27,999

 

1459
01:08:27,999 --> 01:08:30,099

 

1460
01:08:30,099 --> 01:08:32,979

 

1461
01:08:32,979 --> 01:08:34,959

 

1462
01:08:34,959 --> 01:08:38,609

 

1463
01:08:38,609 --> 01:08:40,990

 

1464
01:08:40,990 --> 01:08:43,479

 

1465
01:08:43,479 --> 01:08:45,760

 

1466
01:08:45,760 --> 01:08:46,899

 

1467
01:08:46,899 --> 01:08:48,490

 

1468
01:08:48,490 --> 01:08:51,339

 

1469
01:08:51,339 --> 01:08:52,839

 

1470
01:08:52,839 --> 01:08:54,999

 

1471
01:08:54,999 --> 01:08:56,769

 

1472
01:08:56,769 --> 01:08:59,039

 

1473
01:08:59,039 --> 01:09:01,030

 

1474
01:09:01,030 --> 01:09:03,669

 

1475
01:09:03,669 --> 01:09:05,829

 

1476
01:09:05,829 --> 01:09:08,470

 

1477
01:09:08,470 --> 01:09:10,629

 

1478
01:09:10,629 --> 01:09:14,919

 

1479
01:09:14,919 --> 01:09:16,269

 

1480
01:09:16,269 --> 01:09:17,979

 

1481
01:09:17,979 --> 01:09:19,689

 

1482
01:09:19,689 --> 01:09:23,050

 

1483
01:09:23,050 --> 01:09:25,629

 

1484
01:09:25,629 --> 01:09:30,309

 

1485
01:09:30,309 --> 01:09:33,579

 

1486
01:09:33,579 --> 01:09:34,930

 

1487
01:09:34,930 --> 01:09:36,970

 

1488
01:09:36,970 --> 01:09:38,439

 

1489
01:09:38,439 --> 01:09:39,820

 

1490
01:09:39,820 --> 01:09:43,599

 

1491
01:09:43,599 --> 01:09:45,579

 

1492
01:09:45,579 --> 01:09:48,550

 

1493
01:09:48,550 --> 01:09:50,470

 

1494
01:09:50,470 --> 01:09:51,939

 

1495
01:09:51,939 --> 01:09:55,930

 

1496
01:09:55,930 --> 01:09:59,290

 

1497
01:09:59,290 --> 01:10:02,500

 

1498
01:10:02,500 --> 01:10:04,089

 

1499
01:10:04,089 --> 01:10:07,240

 

1500
01:10:07,240 --> 01:10:10,270

 

1501
01:10:10,270 --> 01:10:13,060

 

1502
01:10:13,060 --> 01:10:15,189

 

1503
01:10:15,189 --> 01:10:17,649

 

1504
01:10:17,649 --> 01:10:19,169

 

1505
01:10:19,169 --> 01:10:22,089

 

1506
01:10:22,089 --> 01:10:24,629

 

1507
01:10:24,629 --> 01:10:26,830

 

1508
01:10:26,830 --> 01:10:29,470

 

1509
01:10:29,470 --> 01:10:31,689

 

1510
01:10:31,689 --> 01:10:33,790

 

1511
01:10:33,790 --> 01:10:37,300

 

1512
01:10:37,300 --> 01:10:39,129

 

1513
01:10:39,129 --> 01:10:42,089

 

1514
01:10:42,089 --> 01:10:44,649

 

1515
01:10:44,649 --> 01:10:46,390

 

1516
01:10:46,390 --> 01:10:48,609

 

1517
01:10:48,609 --> 01:10:52,120

 

1518
01:10:52,120 --> 01:10:56,709

 

1519
01:10:56,709 --> 01:10:58,540

 

1520
01:10:58,540 --> 01:11:01,959

 

1521
01:11:01,959 --> 01:11:04,419

 

1522
01:11:04,419 --> 01:11:06,760

 

1523
01:11:06,760 --> 01:11:11,379

 

1524
01:11:11,379 --> 01:11:14,200

 

1525
01:11:14,200 --> 01:11:18,129

 

1526
01:11:18,129 --> 01:11:20,050

 

1527
01:11:20,050 --> 01:11:22,959

 

1528
01:11:22,959 --> 01:11:26,169

 

1529
01:11:26,169 --> 01:11:28,209

 

1530
01:11:28,209 --> 01:11:31,600

 

1531
01:11:31,600 --> 01:11:33,879

 

1532
01:11:33,879 --> 01:11:35,589

 

1533
01:11:35,589 --> 01:11:38,310

 

1534
01:11:38,310 --> 01:11:40,570

 

1535
01:11:40,570 --> 01:11:44,200

 

1536
01:11:44,200 --> 01:11:46,270

 

1537
01:11:46,270 --> 01:11:48,160

 

1538
01:11:48,160 --> 01:11:50,800

 

1539
01:11:50,800 --> 01:11:51,970

 

1540
01:11:51,970 --> 01:11:54,910

 

1541
01:11:54,910 --> 01:11:56,919

 

1542
01:11:56,919 --> 01:11:59,290

 

1543
01:11:59,290 --> 01:12:01,209

 

1544
01:12:01,209 --> 01:12:03,760

 

1545
01:12:03,760 --> 01:12:06,550

 

1546
01:12:06,550 --> 01:12:08,950

 

1547
01:12:08,950 --> 01:12:10,870

 

1548
01:12:10,870 --> 01:12:13,680

 

1549
01:12:13,680 --> 01:12:16,450

 

1550
01:12:16,450 --> 01:12:18,550

 

1551
01:12:18,550 --> 01:12:20,500

 

1552
01:12:20,500 --> 01:12:22,830

 

1553
01:12:22,830 --> 01:12:24,970

 

1554
01:12:24,970 --> 01:12:27,790

 

1555
01:12:27,790 --> 01:12:29,410

 

1556
01:12:29,410 --> 01:12:32,410

 

1557
01:12:32,410 --> 01:12:36,189

 

1558
01:12:36,189 --> 01:12:37,629

 

1559
01:12:37,629 --> 01:12:39,430

 

1560
01:12:39,430 --> 01:12:40,129

 

1561
01:12:40,129 --> 01:12:42,890

 

1562
01:12:42,890 --> 01:12:45,109

 

1563
01:12:45,109 --> 01:12:47,419

 

1564
01:12:47,419 --> 01:12:49,910

 

1565
01:12:49,910 --> 01:12:52,010

 

1566
01:12:52,010 --> 01:12:55,790

 

1567
01:12:55,790 --> 01:12:57,770

 

1568
01:12:57,770 --> 01:13:00,520

 

1569
01:13:00,520 --> 01:13:03,770

 

1570
01:13:03,770 --> 01:13:07,060

 

1571
01:13:07,060 --> 01:13:10,100

 

1572
01:13:10,100 --> 01:13:12,080

 

1573
01:13:12,080 --> 01:13:14,899

 

1574
01:13:14,899 --> 01:13:16,790

 

1575
01:13:16,790 --> 01:13:36,919

 

1576
01:13:36,919 --> 01:13:39,709

 

1577
01:13:39,709 --> 01:13:43,100

 

1578
01:13:43,100 --> 01:13:45,770

 

1579
01:13:45,770 --> 01:13:48,260

 

1580
01:13:48,260 --> 01:13:50,990

 

1581
01:13:50,990 --> 01:13:52,669

 

1582
01:13:52,669 --> 01:13:55,520

 

1583
01:13:55,520 --> 01:13:57,530

 

1584
01:13:57,530 --> 01:14:00,530

 

1585
01:14:00,530 --> 01:14:02,720

 

1586
01:14:02,720 --> 01:14:03,890

 

1587
01:14:03,890 --> 01:14:06,709

 

1588
01:14:06,709 --> 01:14:10,760

 

1589
01:14:10,760 --> 01:14:14,750

 

1590
01:14:14,750 --> 01:14:16,459

 

1591
01:14:16,459 --> 01:14:18,890

 

1592
01:14:18,890 --> 01:14:28,890

 

1593
01:14:28,890 --> 01:14:31,840

 

1594
01:14:31,840 --> 01:14:39,070

 

1595
01:14:39,070 --> 01:15:00,670

 

1596
01:15:00,670 --> 01:15:02,470

 

1597
01:15:02,470 --> 01:15:05,710

 

1598
01:15:05,710 --> 01:15:05,720

 

1599
01:15:05,720 --> 01:15:06,610


1600
01:15:06,610 --> 01:15:08,680

 

1601
01:15:08,680 --> 01:15:12,100

 

1602
01:15:12,100 --> 01:15:14,380

 

1603
01:15:14,380 --> 01:15:16,150

 

1604
01:15:16,150 --> 01:15:19,150

 

1605
01:15:19,150 --> 01:15:22,060

 

1606
01:15:22,060 --> 01:15:25,360

 

1607
01:15:25,360 --> 01:15:39,430

 

1608
01:15:39,430 --> 01:15:39,440

 

1609
01:15:39,440 --> 01:15:52,570


1610
01:15:52,570 --> 01:15:57,800

 

1611
01:15:57,800 --> 01:15:59,030

 

1612
01:15:59,030 --> 01:16:01,190

 

1613
01:16:01,190 --> 01:16:03,280

 

1614
01:16:03,280 --> 01:16:10,010

 

1615
01:16:10,010 --> 01:16:12,920

 

1616
01:16:12,920 --> 01:16:15,290

 

1617
01:16:15,290 --> 01:16:21,980

 

1618
01:16:21,980 --> 01:16:23,750

 

1619
01:16:23,750 --> 01:16:26,060

 

1620
01:16:26,060 --> 01:16:28,190

 

1621
01:16:28,190 --> 01:16:30,620

 

1622
01:16:30,620 --> 01:16:34,370

 

1623
01:16:34,370 --> 01:16:39,700

 

1624
01:16:39,700 --> 01:16:42,140

 

1625
01:16:42,140 --> 01:16:45,120

 

1626
01:16:45,120 --> 01:16:52,620

 

1627
01:16:52,620 --> 01:16:55,950

 

1628
01:16:55,950 --> 01:16:58,350

 

1629
01:16:58,350 --> 01:17:00,180

 

1630
01:17:00,180 --> 01:17:05,790

 

1631
01:17:05,790 --> 01:17:08,490

 

1632
01:17:08,490 --> 01:17:10,770

 

1633
01:17:10,770 --> 01:17:13,649

 

1634
01:17:13,649 --> 01:17:16,020

 

1635
01:17:16,020 --> 01:17:18,450

 

1636
01:17:18,450 --> 01:17:21,359

 

1637
01:17:21,359 --> 01:17:23,399

 

1638
01:17:23,399 --> 01:17:25,649

 

1639
01:17:25,649 --> 01:17:28,050

 

1640
01:17:28,050 --> 01:17:31,109

 

1641
01:17:31,109 --> 01:17:33,209

 

1642
01:17:33,209 --> 01:17:35,580

 

1643
01:17:35,580 --> 01:17:37,740

 

1644
01:17:37,740 --> 01:17:40,140

 

1645
01:17:40,140 --> 01:17:42,569

 

1646
01:17:42,569 --> 01:17:44,399

 

1647
01:17:44,399 --> 01:17:46,919

 

1648
01:17:46,919 --> 01:17:50,669

 

1649
01:17:50,669 --> 01:17:52,950

 

1650
01:17:52,950 --> 01:17:54,990

 

1651
01:17:54,990 --> 01:17:56,879

 

1652
01:17:56,879 --> 01:17:59,729

 

1653
01:17:59,729 --> 01:18:04,770

 

1654
01:18:04,770 --> 01:18:06,569

 

1655
01:18:06,569 --> 01:18:10,140

 

1656
01:18:10,140 --> 01:18:11,640

 

1657
01:18:11,640 --> 01:18:13,950

 

1658
01:18:13,950 --> 01:18:16,830

 

1659
01:18:16,830 --> 01:18:19,830

 

1660
01:18:19,830 --> 01:18:21,810

 

1661
01:18:21,810 --> 01:18:27,429

 

1662
01:18:27,429 --> 01:18:33,049

 

1663
01:18:33,049 --> 01:18:35,719

 

1664
01:18:35,719 --> 01:18:38,239

 

1665
01:18:38,239 --> 01:18:41,719

 

1666
01:18:41,719 --> 01:18:43,939

 

1667
01:18:43,939 --> 01:18:47,209

 

1668
01:18:47,209 --> 01:18:49,040

 

1669
01:18:49,040 --> 01:18:53,179

 

1670
01:18:53,179 --> 01:18:56,359

 

1671
01:18:56,359 --> 01:18:59,779

 

1672
01:18:59,779 --> 01:19:06,919

 

1673
01:19:06,919 --> 01:19:09,679

 

1674
01:19:09,679 --> 01:19:12,589

 

1675
01:19:12,589 --> 01:19:14,330

 

1676
01:19:14,330 --> 01:19:16,850

 

1677
01:19:16,850 --> 01:19:18,319

 

1678
01:19:18,319 --> 01:19:19,819

 

1679
01:19:19,819 --> 01:19:23,959

 

1680
01:19:23,959 --> 01:19:26,270

 

1681
01:19:26,270 --> 01:19:28,699

 

1682
01:19:28,699 --> 01:19:30,589

 

1683
01:19:30,589 --> 01:19:32,569

 

1684
01:19:32,569 --> 01:19:35,089

 

1685
01:19:35,089 --> 01:19:37,250

 

1686
01:19:37,250 --> 01:19:39,859

 

1687
01:19:39,859 --> 01:19:41,419

 

1688
01:19:41,419 --> 01:19:44,569

 

1689
01:19:44,569 --> 01:19:46,339

 

1690
01:19:46,339 --> 01:19:50,449

 

1691
01:19:50,449 --> 01:19:52,129

 

1692
01:19:52,129 --> 01:19:54,109

 

1693
01:19:54,109 --> 01:19:57,379

 

1694
01:19:57,379 --> 01:19:58,850

 

1695
01:19:58,850 --> 01:20:00,229

 

1696
01:20:00,229 --> 01:20:02,899

 

1697
01:20:02,899 --> 01:20:06,679

 

1698
01:20:06,679 --> 01:20:08,870

 

1699
01:20:08,870 --> 01:20:11,449

 

1700
01:20:11,449 --> 01:20:14,270

 

1701
01:20:14,270 --> 01:20:16,969

 

1702
01:20:16,969 --> 01:20:21,020

 

1703
01:20:21,020 --> 01:20:23,509

 

1704
01:20:23,509 --> 01:20:26,719

 

1705
01:20:26,719 --> 01:20:29,839

 

1706
01:20:29,839 --> 01:20:31,759

 

1707
01:20:31,759 --> 01:20:33,529

 

1708
01:20:33,529 --> 01:20:38,140

 

1709
01:20:38,140 --> 01:20:40,720

 

1710
01:20:40,720 --> 01:20:40,730

 

1711
01:20:40,730 --> 01:20:46,510