1 00:00:00,000 --> 00:00:10,900 2 00:00:10,900 --> 00:00:15,860 >> Spreker 1: Alle reg, sodat dit is CS50 Dit is die einde van die week vyf. 3 00:00:15,860 --> 00:00:19,220 En onthou dat laaste keer dat ons begin kyk na die liefhebber data 4 00:00:19,220 --> 00:00:22,310 strukture wat begin het om op te los probleme, wat begin het om in te voer 5 00:00:22,310 --> 00:00:25,640 nuwe probleme, maar die sleutel tot hierdie was die soort threading dat ons 6 00:00:25,640 --> 00:00:27,940 begin om te doen van knoop tot knoop. 7 00:00:27,940 --> 00:00:30,085 So dit is natuurlik 'n enkel geskakelde lys. 8 00:00:30,085 --> 00:00:31,960 En een-een gekoppel is, Ek bedoel, daar is net een 9 00:00:31,960 --> 00:00:33,380 ryg tussen elk van die nodes. 10 00:00:33,380 --> 00:00:35,890 Blyk jy kan doen liefhebber dinge soos dubbel geskakelde lyste 11 00:00:35,890 --> 00:00:38,470 waardeur jy 'n pyl gaan in albei rigtings, wat 12 00:00:38,470 --> 00:00:40,320 kan help met sekere doeltreffendheid. 13 00:00:40,320 --> 00:00:42,000 Maar dit het die probleem opgelos? 14 00:00:42,000 --> 00:00:43,500 Watter probleem het dit op te los? 15 00:00:43,500 --> 00:00:46,620 Hoekom het ons omgee op Maandag? 16 00:00:46,620 --> 00:00:49,820 Hoekom, in teorie, het ons omgee op Maandag? 17 00:00:49,820 --> 00:00:50,630 Wat doen dit? 18 00:00:50,630 --> 00:00:51,950 >> GEHOOR: Ons kan dinamiese grootte daarvan. 19 00:00:51,950 --> 00:00:53,740 >> Spreker 1: OK, so ons kan dinamiese grootte daarvan. 20 00:00:53,740 --> 00:00:54,710 Welgedaan beide van julle. 21 00:00:54,710 --> 00:00:57,560 Sodat jy kan dinamiese hierdie grootte data struktuur, terwyl 'n skikking, 22 00:00:57,560 --> 00:01:00,760 Onthou, jy het 'n ken priori hoeveel ruimte wat jy wil 23 00:01:00,760 --> 00:01:03,870 en as jy 'n bietjie meer nodig ruimte, jy is soort van uit van geluk. 24 00:01:03,870 --> 00:01:05,560 Jy het 'n hele nuwe reeks te skep. 25 00:01:05,560 --> 00:01:07,893 Jy het om al beweeg jou data van die een na die ander, 26 00:01:07,893 --> 00:01:10,600 uiteindelik bevry die ou array as jy kan, en dan voort te gaan. 27 00:01:10,600 --> 00:01:13,891 Wat voel net baie duur en baie ondoeltreffende, en inderdaad is dit kan wees. 28 00:01:13,891 --> 00:01:14,890 Maar dit is nie al die goeie. 29 00:01:14,890 --> 00:01:18,180 Ons betaal 'n prys, wat was een van die meer ooglopende pryse wat ons 30 00:01:18,180 --> 00:01:20,550 betaal deur die gebruik van 'n geskakelde lys? 31 00:01:20,550 --> 00:01:22,825 >> GEHOOR: Ons het om te gebruik dubbel ruimte vir elkeen. 32 00:01:22,825 --> 00:01:25,200 Spreker 1: Ja, so ons moet ten minste twee keer soveel ruimte. 33 00:01:25,200 --> 00:01:27,700 In werklikheid, het ek besef hierdie prentjie selfs 'n bietjie misleidend, 34 00:01:27,700 --> 00:01:32,200 want op CS50 IO in 'n baie moderne rekenaars, 'n wyser of 'n adres 35 00:01:32,200 --> 00:01:33,700 is nie in die feit dat vier grepe. 36 00:01:33,700 --> 00:01:36,090 Dit is baie dikwels hierdie dae agt grepe, wat 37 00:01:36,090 --> 00:01:38,530 beteken die onderkant mees reghoeke daar in werklikheid 38 00:01:38,530 --> 00:01:40,900 is soort van twee keer groot soos wat ek getrek, 39 00:01:40,900 --> 00:01:44,409 wat beteken jy gebruik drie keer veel ruimte soos ons anders kan hê. 40 00:01:44,409 --> 00:01:46,700 Nou op dieselfde tyd, ons is nog praat grepe, reg? 41 00:01:46,700 --> 00:01:49,140 Ons is nie noodwendig praat megagrepe of gigagrepe, 42 00:01:49,140 --> 00:01:51,000 tensy dit datastrukture kry groot. 43 00:01:51,000 --> 00:01:54,510 >> En so vandag het ons begin om te oorweeg hoe ons data kan verken 44 00:01:54,510 --> 00:01:57,310 meer doeltreffend as in die feit dat die data kry groter. 45 00:01:57,310 --> 00:02:00,360 Maar laat ons probeer om canonicalize die bedrywighede eerste 46 00:02:00,360 --> 00:02:02,460 wat jy kan doen op hierdie soorte data strukture. 47 00:02:02,460 --> 00:02:04,790 So iets soos 'n gekoppelde lys die algemeen ondersteun 48 00:02:04,790 --> 00:02:07,514 bedrywighede wil verwyder, voeg, en soek. 49 00:02:07,514 --> 00:02:08,639 En wat doen ek daarmee? 50 00:02:08,639 --> 00:02:11,222 Dit beteken net dat gewoonlik, as mense is met behulp van geskakelde lys, 51 00:02:11,222 --> 00:02:14,287 hulle of iemand anders geïmplementeer funksies soos verwyder, vul, 52 00:02:14,287 --> 00:02:16,120 en soek, sodat jy kan iets werklik doen 53 00:02:16,120 --> 00:02:18,030 nuttige met die data-struktuur. 54 00:02:18,030 --> 00:02:20,760 So laat ons neem 'n vinnige blik hoe ons kan implementeer 55 00:02:20,760 --> 00:02:24,530 sommige kode vir 'n geskakelde lys soos volg. 56 00:02:24,530 --> 00:02:27,885 >> So dit is net 'n paar C-kode, nie eens 'n volledige program 57 00:02:27,885 --> 00:02:29,260 dat ek regtig vinnig opgesweep. 58 00:02:29,260 --> 00:02:32,300 Dit is nie in die verspreiding aanlyn kode, want dit sal nie eintlik loop. 59 00:02:32,300 --> 00:02:33,790 Maar let ek het nou net met 'n comment gesê 60 00:02:33,790 --> 00:02:36,130 dot dot dot, daar is iets daar dot dot dot, iets daar. 61 00:02:36,130 --> 00:02:38,410 En laat ons net kyk na wat die sappige dele is. 62 00:02:38,410 --> 00:02:40,790 So op die lyn drie, onthou dat dit is nou 63 00:02:40,790 --> 00:02:45,960 Ons het voorgestel waarby 'n node laaste tyd, een van daardie vierkantige voorwerpe. 64 00:02:45,960 --> 00:02:48,790 Dit het 'n int dat ons N bel, maar ons kan dit enigiets noem, 65 00:02:48,790 --> 00:02:51,920 en dan 'n sogenaamde struct node ster langs. 66 00:02:51,920 --> 00:02:55,520 En net om duidelik te wees, dat die tweede lyn, op die lyn ses, wat gaan dit? 67 00:02:55,520 --> 00:02:57,930 Wat is dit vir ons doen? 68 00:02:57,930 --> 00:03:01,044 Want dit lyk beslis meer kriptiese as ons gewone veranderlikes. 69 00:03:01,044 --> 00:03:02,740 >> GEHOOR: Dit maak dit beweeg oor een. 70 00:03:02,740 --> 00:03:04,650 >> Spreker 1: Dit maak dit beweeg oor een. 71 00:03:04,650 --> 00:03:08,580 En om meer presies te wees, sal dit die adres stoor 72 00:03:08,580 --> 00:03:11,582 van die node wat bedoel is om te wees semanties langs dit, reg? 73 00:03:11,582 --> 00:03:13,540 So dit is nie van plan om noodwendig beweeg nie. 74 00:03:13,540 --> 00:03:15,290 Dit is net gaan om te stoor 'n waarde wat 75 00:03:15,290 --> 00:03:17,170 gaan na die adres van 'n paar ander knoop, 76 00:03:17,170 --> 00:03:20,810 en dit is hoekom ons het gesê struct node ster, die ster wat aandui 77 00:03:20,810 --> 00:03:22,370 'n wyser of 'n adres. 78 00:03:22,370 --> 00:03:26,390 OK, so nou as jy aanvaar dat ons hierdie N tot ons beskikking, en laat 79 00:03:26,390 --> 00:03:29,490 aanvaar dat iemand anders ingevoeg n hele klomp van heelgetalle 80 00:03:29,490 --> 00:03:30,400 in 'n geskakelde lys. 81 00:03:30,400 --> 00:03:35,640 En dat gekoppel lys is wys na 'n sekere punt deur 82 00:03:35,640 --> 00:03:39,040 'n veranderlike genaamd lys wat geslaag hier as 'n parameter, 83 00:03:39,040 --> 00:03:43,120 hoe gaan ek te werk lyn 14 search implementering? 84 00:03:43,120 --> 00:03:45,990 Met ander woorde, as ek die implementering funksie waarvan die doel in die lewe 85 00:03:45,990 --> 00:03:48,889 is om 'n int en dan die neem begin van 'n geskakelde lys, 86 00:03:48,889 --> 00:03:50,430 dit is 'n verwysing na die geskakelde lys. 87 00:03:50,430 --> 00:03:52,992 Soos die eerste, wat ek dink David was ons vrywilligers op Maandag, 88 00:03:52,992 --> 00:03:54,700 hy wys op die hele gekoppel lys 89 00:03:54,700 --> 00:03:57,820 dit is asof ons verby David in as ons argument hier. 90 00:03:57,820 --> 00:03:59,990 Hoe gaan ons te werk dwars hierdie lys? 91 00:03:59,990 --> 00:04:04,640 Wel, dit blyk dat selfs al pointers is nou relatief nuut vir ons, 92 00:04:04,640 --> 00:04:07,010 Ons kan dit doen relatief reguit. 93 00:04:07,010 --> 00:04:09,500 >> Ek gaan om voort te gaan en verklaar 'n tydelike veranderlike wat 94 00:04:09,500 --> 00:04:12,364 deur konvensie is net gaan wyser genoem te word, of PTR, 95 00:04:12,364 --> 00:04:14,030 maar jy kan dit iets wat jy wil bel. 96 00:04:14,030 --> 00:04:16,470 En ek gaan inisialiseer dit aan die begin van die lys. 97 00:04:16,470 --> 00:04:20,050 Sodat jy kan soort van dink van hierdie as my die onderwyser die ander dag, 98 00:04:20,050 --> 00:04:23,580 soort wat dui op iemand onder ons mense as vrywilligers. 99 00:04:23,580 --> 00:04:26,470 So ek is 'n tydelike veranderlike wat net wys op die dieselfde ding 100 00:04:26,470 --> 00:04:31,390 dat ons toevallig vernoem vrywilliger David is ook uit te wys. 101 00:04:31,390 --> 00:04:35,440 En terwyl wyser is nie null, want onthou 102 00:04:35,440 --> 00:04:40,350 dat null is 'n paar spesiale brandwag waarde die afbaken die einde van die lys, 103 00:04:40,350 --> 00:04:44,280 Dus, terwyl ek nie wys op die grond soos ons laaste vrywilliger 104 00:04:44,280 --> 00:04:47,190 was, laat ons gaan voort en doen die volgende. 105 00:04:47,190 --> 00:04:51,820 As pointer-- en nou kan ek soort van wil om te doen wat ons gedoen het met die student 106 00:04:51,820 --> 00:04:57,410 structure-- as wyser dot volgende equals-- eerder as wyser dot N gelyk 107 00:04:57,410 --> 00:05:02,290 gelyk aan die veranderlike N, die argument wat alreeds geslaag in, 108 00:05:02,290 --> 00:05:05,370 dan wil ek om voort te gaan en sê terugkeer waar. 109 00:05:05,370 --> 00:05:11,020 Ek het die aantal N binnekant van gevind een van die nodusse van my geskakelde lys. 110 00:05:11,020 --> 00:05:13,500 Maar die dot nie meer werk in hierdie konteks, 111 00:05:13,500 --> 00:05:17,260 omdat pointer, PTR, is inderdaad 'n wyser, 'n adres, 112 00:05:17,260 --> 00:05:20,632 Ons kan eintlik wonderlik gebruik uiteindelik 'n stukkie van die sintaksis 113 00:05:20,632 --> 00:05:22,590 dat soort maak intuïtief sin en eintlik 114 00:05:22,590 --> 00:05:27,870 gebruik 'n pyl hier, wat beteken gaan van dat adres aan die heelgetal daar in. 115 00:05:27,870 --> 00:05:30,160 So dit is baie soortgelyk in gees om die dot-operateur, 116 00:05:30,160 --> 00:05:33,860 maar omdat wyser is nie 'n wyser en nie 'n werklike struct self, 117 00:05:33,860 --> 00:05:35,380 ons gebruik net die pyl. 118 00:05:35,380 --> 00:05:40,620 >> So as die huidige node dat ek, die tydelike veranderlike, is wys op 119 00:05:40,620 --> 00:05:43,060 is nie N, wat wil ek doen? 120 00:05:43,060 --> 00:05:45,910 Wel, met my menslike vrywilligers dat ons hier gehad het die ander dag, 121 00:05:45,910 --> 00:05:49,710 as my eerste mens is nie die een wat ek wil, en miskien die tweede mens is nie 122 00:05:49,710 --> 00:05:52,660 die een wat ek wil hê, en die derde, ek nodig om fisies bly beweeg. 123 00:05:52,660 --> 00:05:54,690 Soos hoe ek stap vir stap deur 'n lys? 124 00:05:54,690 --> 00:05:57,470 Wanneer ons het 'n verskeidenheid jou, net gedoen soos ek plus plus. 125 00:05:57,470 --> 00:06:03,660 Maar in hierdie geval, is dit voldoende om doen pointer, kry, pointer, die volgende. 126 00:06:03,660 --> 00:06:07,580 Met ander woorde, die volgende veld is soos al die linkerkant hande 127 00:06:07,580 --> 00:06:10,880 dat ons menslike vrywilligers op Maandag was die gebruik om te wys op 'n ander knoop. 128 00:06:10,880 --> 00:06:12,890 Dit was hul volgende bure. 129 00:06:12,890 --> 00:06:17,060 >> So as ek wil om te stap deur hierdie lys, Ek kan nie net doen ek plus plus meer, 130 00:06:17,060 --> 00:06:20,120 Ek het om te sê in plaas Ek, pointer, gaan 131 00:06:20,120 --> 00:06:24,650 om gelyk ongeag die volgende veld is, die volgende veld, die volgende veld is, 132 00:06:24,650 --> 00:06:28,350 volgende al daardie gelaat hande wat ons gehad het op die verhoog wys 133 00:06:28,350 --> 00:06:30,000 sommige daaropvolgende waardes. 134 00:06:30,000 --> 00:06:32,590 En as ek kry deur dat die hele iterasie, 135 00:06:32,590 --> 00:06:39,330 en uiteindelik, ek getref null nie met gevind N nog, ek het net terug onwaar. 136 00:06:39,330 --> 00:06:44,100 So weer, alles wat ons hier doen, soos per die prentjie 'n oomblik gelede 137 00:06:44,100 --> 00:06:47,840 begin deur te wys op die begin van die lys vermoedelik. 138 00:06:47,840 --> 00:06:50,970 En dan het ek seker te maak, is die waarde Ek soek gelyk aan nege? 139 00:06:50,970 --> 00:06:52,650 As dit so is, het ek terug waar en ek is gedaan. 140 00:06:52,650 --> 00:06:56,450 Indien nie, ek my hand te werk, AKA pointer, om te wys 141 00:06:56,450 --> 00:06:59,540 op die ligging van die volgende pyl se en dan plek die volgende pyl se 142 00:06:59,540 --> 00:07:00,480 en die volgende. 143 00:07:00,480 --> 00:07:03,770 Ek is net loop deur middel van hierdie skikking. 144 00:07:03,770 --> 00:07:06,010 >> So weer, wat omgee? 145 00:07:06,010 --> 00:07:07,861 Soos wat hierdie is 'n bestanddeel vir? 146 00:07:07,861 --> 00:07:10,360 Wel, onthou dat ons ' die idee van 'n stapel, wat 147 00:07:10,360 --> 00:07:15,400 is 'n abstrakte data tik sover dit nie 'n C ding, dit is nie 'n ding CS50, 148 00:07:15,400 --> 00:07:19,430 dit is 'n abstrakte idee, hierdie idee van stapel dinge op die top van mekaar 149 00:07:19,430 --> 00:07:21,820 dat geïmplementeer kan word trosse van verskillende maniere. 150 00:07:21,820 --> 00:07:25,600 En een manier waarop ons voorgestelde was met 'n skikking, of met 'n geskakelde lys. 151 00:07:25,600 --> 00:07:29,570 En dit blyk dat kerkwetlik, 'n stapel ondersteun ten minste twee operasies. 152 00:07:29,570 --> 00:07:32,320 En die buzz woorde is druk om stoot iets op die stapel, 153 00:07:32,320 --> 00:07:34,770 soos 'n nuwe skinkbord in die eetsaal, of pop, 154 00:07:34,770 --> 00:07:39,000 wat beteken dat die boonste verwyder skinkbord uit die stapel in die eetkamer 155 00:07:39,000 --> 00:07:41,500 saal, en dan miskien 'n paar ander bedrywighede asook. 156 00:07:41,500 --> 00:07:45,770 So hoe kan ons die struktuur definieer dat ons nou 'n beroep 'n stapel? 157 00:07:45,770 --> 00:07:50,020 >> Wel, ons het al die nodige sintaksis tot ons beskikking in C. Ek sê, 158 00:07:50,020 --> 00:07:53,830 gee my 'n tipe definisie van 'n struct binnekant van 'n stapel, 159 00:07:53,830 --> 00:07:58,030 Ek gaan om te sê, is 'n skikking, van 'n hele klomp van die nommers en dan grootte. 160 00:07:58,030 --> 00:08:00,930 So met ander woorde, as ek wil om dit te implementeer in die kode, 161 00:08:00,930 --> 00:08:03,830 laat my gaan en net soort van teken wat dit sê. 162 00:08:03,830 --> 00:08:06,317 So dit sê, gee my 'n struktuur wat is het 'n skikking, 163 00:08:06,317 --> 00:08:09,400 en ek weet nie wat kapasiteit is, dit is blykbaar 'n paar konstante wat ek 164 00:08:09,400 --> 00:08:10,858 elders gedefinieer, en dit is goed. 165 00:08:10,858 --> 00:08:15,260 Maar dink dit is net een, twee, drie, vier, vyf. 166 00:08:15,260 --> 00:08:16,700 So kapasiteit is 5. 167 00:08:16,700 --> 00:08:21,730 Hierdie element binnekant van my struktuur sal genoem getalle. 168 00:08:21,730 --> 00:08:24,020 En dan moet ek een ander veranderlike blykbaar 169 00:08:24,020 --> 00:08:27,814 genoem grootte wat aanvanklik ek gaan om te stipuleer geïnisialiseer aan nul. 170 00:08:27,814 --> 00:08:29,730 As daar is niks in die stapel, grootte nul is, 171 00:08:29,730 --> 00:08:31,420 en dit is vullis waardes in getalle. 172 00:08:31,420 --> 00:08:33,450 Ek het geen idee wat is daar net nog nie. 173 00:08:33,450 --> 00:08:36,059 >> So as ek wil om te stoot iets op die stapel, 174 00:08:36,059 --> 00:08:40,780 dink ek noem die funksie stoot, en Ek sê stoot 50, soos die nommer 50, 175 00:08:40,780 --> 00:08:44,090 waar sou jy voorstel Ek teken dit in hierdie reeks? 176 00:08:44,090 --> 00:08:47,124 Daar is vyf verskillende moontlike antwoorde. 177 00:08:47,124 --> 00:08:48,790 Waar wil jy die nommer 50 stoot? 178 00:08:48,790 --> 00:08:51,899 As die doel hier, weer, roep die funksie stoot, slaag in 'n argument 179 00:08:51,899 --> 00:08:52,940 50, waar kan ek dit? 180 00:08:52,940 --> 00:08:55,680 181 00:08:55,680 --> 00:08:59,052 Vyf possible-- 20% kans om reg te raai. 182 00:08:59,052 --> 00:08:59,896 Ja? 183 00:08:59,896 --> 00:09:00,740 >> GEHOOR: heel regs. 184 00:09:00,740 --> 00:09:01,990 >> Spreker 1: heel regs. 185 00:09:01,990 --> 00:09:08,359 Daar is nou 'n 25% kans om reg te raai. 186 00:09:08,359 --> 00:09:09,650 So wat eintlik sou goed wees. 187 00:09:09,650 --> 00:09:12,770 Deur konvensie, sal ek sê met 'n skikking, sou ons oor die algemeen begin aan die linkerkant, 188 00:09:12,770 --> 00:09:14,519 maar ons kon beslis begin op die regte. 189 00:09:14,519 --> 00:09:17,478 So die verwoester hier sou wees ek is waarskynlik gaan om dit te trek aan die linkerkant, 190 00:09:17,478 --> 00:09:20,060 net soos in 'n normale verskeidenheid waar Ek begin gaan links na regs. 191 00:09:20,060 --> 00:09:21,780 Maar as jy kan flip die rekenkundige, fyn. 192 00:09:21,780 --> 00:09:23,060 Dit is net nie konvensionele. 193 00:09:23,060 --> 00:09:24,880 OK, ek moet een te maak meer verandering though. 194 00:09:24,880 --> 00:09:27,710 Nou dat ek iets het gestoot op die stapel, wat is volgende? 195 00:09:27,710 --> 00:09:29,400 >> Alle reg, ek het die grootte inkrementeer. 196 00:09:29,400 --> 00:09:32,600 So laat my gaan voort en net werk hierdie, wat nul was. 197 00:09:32,600 --> 00:09:35,950 En in plaas daarvan nou, ek gaan in die waarde een te sit. 198 00:09:35,950 --> 00:09:39,460 En nou dink ek 'n ander stoot nommer op die stapel, soos 51. 199 00:09:39,460 --> 00:09:42,680 Wel, ek het nog een te maak verandering, wat tot die grootte twee. 200 00:09:42,680 --> 00:09:46,100 En dan dink ek stoot een nommer op die stapel soos 61, 201 00:09:46,100 --> 00:09:52,530 ek moet nou aan die grootte werk een tyd, en kry die waarde 3 as die grootte. 202 00:09:52,530 --> 00:09:54,690 En nou dink ek noem pop. 203 00:09:54,690 --> 00:09:57,250 Nou pop, deur konvensie, nie 'n argument te neem. 204 00:09:57,250 --> 00:10:00,430 Met 'n stapel, die hele punt van die metafoor skinkbord 205 00:10:00,430 --> 00:10:03,450 is dat jy nie het diskresie om te gaan kry wat skinkbord, kan alles wat jy doen 206 00:10:03,450 --> 00:10:06,330 is pop die boonste een van die stapel, net omdat. 207 00:10:06,330 --> 00:10:08,010 Dit is wat hierdie data struktuur nie. 208 00:10:08,010 --> 00:10:12,250 >> So deur daardie logika as ek sê pop, wat kom nie? 209 00:10:12,250 --> 00:10:13,080 So 61. 210 00:10:13,080 --> 00:10:15,402 So, wat is regtig die rekenaar gaan doen in die geheue? 211 00:10:15,402 --> 00:10:16,610 Wat beteken my kode hoef te doen? 212 00:10:16,610 --> 00:10:20,330 Wat sou jy voorstel ons verander op die skerm? 213 00:10:20,330 --> 00:10:23,410 Wat moet verander? 214 00:10:23,410 --> 00:10:24,960 Jammer? 215 00:10:24,960 --> 00:10:26,334 So kry ons ontslae te raak van 61. 216 00:10:26,334 --> 00:10:27,500 So kan ek beslis dit doen. 217 00:10:27,500 --> 00:10:28,640 En ek kan ontslae te raak van 61. 218 00:10:28,640 --> 00:10:30,980 En dan wat ander verandering moet gebeur? 219 00:10:30,980 --> 00:10:33,160 Grootte waarskynlik om terug te gaan na twee. 220 00:10:33,160 --> 00:10:34,210 En so is dit goed. 221 00:10:34,210 --> 00:10:36,690 Maar wag 'n minuut, grootte 'n oomblik gelede was drie. 222 00:10:36,690 --> 00:10:38,240 Laat ons net 'n vinnige gesonde verstand tjek. 223 00:10:38,240 --> 00:10:41,810 Hoe het ons weet dat ons wou ontslae raak van 61? 224 00:10:41,810 --> 00:10:42,760 Omdat ons knal. 225 00:10:42,760 --> 00:10:46,450 En so ek het hierdie tweede eiendom grootte. 226 00:10:46,450 --> 00:10:48,470 >> Wag 'n minuut, ek is dink terug na week twee 227 00:10:48,470 --> 00:10:51,660 wanneer ons begin praat oor skikkings, waar dit was ligging nul, 228 00:10:51,660 --> 00:10:55,920 dit was een plek, dit was ligging twee, dit is plek drie, vier, 229 00:10:55,920 --> 00:10:58,460 dit lyk soos die verhouding tussen die grootte 230 00:10:58,460 --> 00:11:02,780 en die element wat ek wil om te verwyder van die skikking verskyn net wat? 231 00:11:02,780 --> 00:11:05,120 Grootte minus een. 232 00:11:05,120 --> 00:11:07,786 En so dit is hoe die mens as ons weet 61 kom eerste. 233 00:11:07,786 --> 00:11:09,160 Hoe gaan die rekenaar gaan om te weet? 234 00:11:09,160 --> 00:11:11,701 Wanneer jou kode, waar jy waarskynlik wil grootte minus een te doen, 235 00:11:11,701 --> 00:11:14,950 so drie minus een is twee, en dat beteken dat ons wil ontslae te raak van 61. 236 00:11:14,950 --> 00:11:18,000 En dan kan ons inderdaad werk die grootte, sodat die grootte nou 237 00:11:18,000 --> 00:11:20,300 gaan van drie tot net twee. 238 00:11:20,300 --> 00:11:24,520 En net om pedanties wees, ek gaan voor te stel dat ek gedoen het, reg? 239 00:11:24,520 --> 00:11:27,660 Jy voorgestelde intuïtief korrek moet ek ontslae raak van 61. 240 00:11:27,660 --> 00:11:30,700 Maar hy het nie ek soort van soort van ontslae geraak 61? 241 00:11:30,700 --> 00:11:33,790 Ek het effektief vergeet dat dit eintlik daar is. 242 00:11:33,790 --> 00:11:37,680 En dink terug aan PSET4, as jy gelees het die artikel oor forensiese, die PDF 243 00:11:37,680 --> 00:11:40,780 wat ons gehad het julle ouens te lees, of jy sal hierdie week lees PSET4. 244 00:11:40,780 --> 00:11:44,300 Onthou dat dit is eintlik related aan Die hele idee van die rekenaar forensiese. 245 00:11:44,300 --> 00:11:47,820 Wat 'n rekenaar doen, is oor die algemeen is dit net vergeet waar iets is, 246 00:11:47,820 --> 00:11:51,300 maar dit gaan nie in en soos probeer om dit uit of ignoreer krap 247 00:11:51,300 --> 00:11:54,560 daardie stukkies met nulle en ene of 'n ander ewekansige patroon 248 00:11:54,560 --> 00:11:56,690 tensy jy jouself doen doelbewus. 249 00:11:56,690 --> 00:11:58,930 So jou intuïsie was reg, laat ons ontslae te raak van 61. 250 00:11:58,930 --> 00:12:00,650 Maar in werklikheid is, het ons nie te pla. 251 00:12:00,650 --> 00:12:04,040 Ons moet net om te vergeet dat dit is daar deur die verandering van ons grootte. 252 00:12:04,040 --> 00:12:05,662 >> Nou is daar 'n probleem met hierdie stapel. 253 00:12:05,662 --> 00:12:07,620 As ek hou dinge stoot op die stapel, wat is 254 00:12:07,620 --> 00:12:11,167 natuurlik gaan gebeur in net 'n paar oomblikke tyd? 255 00:12:11,167 --> 00:12:12,500 Ons gaan uit die ruimte te loop. 256 00:12:12,500 --> 00:12:13,580 En wat doen ons? 257 00:12:13,580 --> 00:12:14,680 Ons soort geskroef. 258 00:12:14,680 --> 00:12:19,000 Hierdie implementering nie laat ons die grootte van die skikking, want die gebruik van 259 00:12:19,000 --> 00:12:21,240 hierdie sintaksis, as jy dink terug aan week twee, 260 00:12:21,240 --> 00:12:23,520 sodra jy verklaar die grootte van 'n skikking, 261 00:12:23,520 --> 00:12:26,780 ons het 'n meganisme nog nie gesien het nie, waar kan jy die grootte van die skikking te verander. 262 00:12:26,780 --> 00:12:29,020 En inderdaad C nie dat die funksie. 263 00:12:29,020 --> 00:12:32,524 As jy sê gee my vyf Nths, bel hulle getalle, 264 00:12:32,524 --> 00:12:33,940 dit is al wat jy gaan om dit te kry. 265 00:12:33,940 --> 00:12:38,790 So ons nou doen as Maandag, het die vermoë om 'n oplossing te druk 266 00:12:38,790 --> 00:12:42,480 al is, ons moet net aanpas die definisie van ons stapel 267 00:12:42,480 --> 00:12:46,840 om 'n paar harde-gekodeerde verskeidenheid nie, maar net om 'n adres te stoor. 268 00:12:46,840 --> 00:12:47,890 >> Nou hoekom is dit? 269 00:12:47,890 --> 00:12:51,690 Nou moet ons net gemaklik met die feit dat wanneer my program loop, 270 00:12:51,690 --> 00:12:53,730 Ek is vermoedelik gaan moet die menslike vra 271 00:12:53,730 --> 00:12:55,110 Hoeveel getalle wil jy om te stoor? 272 00:12:55,110 --> 00:12:56,776 So die insette het om te kom van iewers. 273 00:12:56,776 --> 00:12:59,140 Maar sodra ek weet dat nommer, dan kan ek net 274 00:12:59,140 --> 00:13:02,470 gebruik wat funksioneer om te gee vir my 'n stuk van die geheue? 275 00:13:02,470 --> 00:13:03,580 Ek kan gebruik malloc. 276 00:13:03,580 --> 00:13:06,710 En ek kan enige aantal sê grepe Ek wil terugkom vir hierdie Nths. 277 00:13:06,710 --> 00:13:10,910 En alles wat ek het om op te slaan in die getalle veranderlike hier binnekant van hierdie struct 278 00:13:10,910 --> 00:13:13,480 wat behoort te wees? 279 00:13:13,480 --> 00:13:18,440 Wat eintlik gaan in die getalle in hierdie scenario? 280 00:13:18,440 --> 00:13:21,300 Ja, 'n verwysing na die eerste byte van daardie deel van die geheue, 281 00:13:21,300 --> 00:13:24,940 of meer spesifiek, die adres van die eerste van die grepe. 282 00:13:24,940 --> 00:13:27,300 Maak nie saak of dit 'n byte of 'n miljard grepe, 283 00:13:27,300 --> 00:13:28,890 Ek het net nodig om te sorg oor die eerste. 284 00:13:28,890 --> 00:13:31,530 Want wat malloc waarborge en my bedryfstelsel waarborge, 285 00:13:31,530 --> 00:13:34,170 is dat die stuk van die geheue Ek te kry, gaan dit aangrensende wees. 286 00:13:34,170 --> 00:13:35,378 Daar gaan nie gapings wees. 287 00:13:35,378 --> 00:13:38,576 So as ek vir 50 gevra het grepe of 1000 grepe, 288 00:13:38,576 --> 00:13:40,450 hulle is almal gaan wees rug aan rug aan rug. 289 00:13:40,450 --> 00:13:44,500 En so lank as wat ek onthou hoe groot, hoe veel gevra ek, al wat ek nodig het om te weet 290 00:13:44,500 --> 00:13:46,230 is die eerste sodanige adres. 291 00:13:46,230 --> 00:13:48,660 >> So nou het ons die vermoë om in die kode. 292 00:13:48,660 --> 00:13:51,280 Hoewel, dit gaan om ons te neem meer tyd om hierdie te skryf, 293 00:13:51,280 --> 00:13:55,900 nou kan ons herschikken dat geheue deur net 'n ander adres stoor daar 294 00:13:55,900 --> 00:13:59,060 as ons wil 'n groter of selfs 'n kleiner deel van die geheue. 295 00:13:59,060 --> 00:14:00,170 So hier om 'n kompromis. 296 00:14:00,170 --> 00:14:01,360 Nou kry ons dinamika. 297 00:14:01,360 --> 00:14:03,350 Ons het nog contiguousness ek beweer. 298 00:14:03,350 --> 00:14:05,881 Omdat malloc ons sal gee 'n aangrensende stuk van die geheue. 299 00:14:05,881 --> 00:14:08,630 Maar dit gaan 'n pyn in wees die nek vir ons, die programmeerder, 300 00:14:08,630 --> 00:14:09,770 om werklik die kode up. 301 00:14:09,770 --> 00:14:10,730 Dis net meer werk. 302 00:14:10,730 --> 00:14:13,930 Ons moet code soortgelyk aan wat ek was gebons net 'n oomblik gelede. 303 00:14:13,930 --> 00:14:16,120 Baie uitvoerbaar nie, maar dit voeg kompleksiteit. 304 00:14:16,120 --> 00:14:19,520 En so ontwikkelaar tyd programmeerder tyd is nog 'n hulpbron 305 00:14:19,520 --> 00:14:22,520 dat ons dalk nodig om te spandeer 'n tyd om nuwe funksies te kry. 306 00:14:22,520 --> 00:14:24,020 En dan natuurlik is daar 'n tou. 307 00:14:24,020 --> 00:14:26,227 Ons sal nie in hierdie gaan een in veel detail. 308 00:14:26,227 --> 00:14:27,560 Maar dit is baie soortgelyk in die gees. 309 00:14:27,560 --> 00:14:31,220 Ek kon 'n tou te implementeer, en sy ooreenstemmende bedrywighede, 310 00:14:31,220 --> 00:14:35,660 enqueue of dequeue soos by te voeg of te verwyder, dit is net 'n liefhebber manier om te sê nie, 311 00:14:35,660 --> 00:14:38,100 enqueue of dequeue, soos volg. 312 00:14:38,100 --> 00:14:41,170 Ek kan net gee my 'n struct het weer so array 'n aantal se 313 00:14:41,170 --> 00:14:44,000 het weer so 'n grote, maar hoekom moet ek nou nodig 314 00:14:44,000 --> 00:14:46,940 om tred te hou van die voorkant van 'n tou te hou? 315 00:14:46,940 --> 00:14:50,630 Ek het nie nodig om te weet die voorkant van my stapel. 316 00:14:50,630 --> 00:14:53,570 Wel, as ek weer vir 'n queue-- laat ons net hard 317 00:14:53,570 --> 00:14:57,870 kodeer dit as 'soos vyf heelgetalle hier potensieel. 318 00:14:57,870 --> 00:15:00,940 So, dit is nul, een, twee, drie, vier. 319 00:15:00,940 --> 00:15:03,430 Dit gaan wees weer geroep getalle. 320 00:15:03,430 --> 00:15:06,940 En dit sal genoem grootte. 321 00:15:06,940 --> 00:15:10,056 >> Hoekom is dit nie genoeg nie net grootte het? 322 00:15:10,056 --> 00:15:11,680 Wel, laat ons stoot daardie nommers op. 323 00:15:11,680 --> 00:15:14,220 So ek pushed-- ek waglys, of gestoot. 324 00:15:14,220 --> 00:15:20,150 Nou sal ek enqueue 50, en dan 51, en dan 61, en dot dot dot. 325 00:15:20,150 --> 00:15:21,070 So dit is enqueue. 326 00:15:21,070 --> 00:15:23,176 Ek waglys 50, dan 51, dan 61. 327 00:15:23,176 --> 00:15:25,050 En wat identies lyk om 'n stapel tot dusver, 328 00:15:25,050 --> 00:15:27,190 behalwe as ek nodig het om een ​​verandering te maak. 329 00:15:27,190 --> 00:15:33,680 Ek het nodig om hierdie grootte te werk, so ek gaan van nul tot een om 02:58 nou. 330 00:15:33,680 --> 00:15:35,760 Hoe kan ek dequeue? 331 00:15:35,760 --> 00:15:36,890 Wat gebeur met dequeue? 332 00:15:36,890 --> 00:15:41,950 Wie moet hierdie lys kom eerste af As dit is die lyn by die Apple Store? 333 00:15:41,950 --> 00:15:42,780 So 50. 334 00:15:42,780 --> 00:15:44,700 So dit is soort van moeiliker hierdie tyd. 335 00:15:44,700 --> 00:15:47,880 AANGESIEN laaste keer was dit super maklik om net te doen grootte minus een, 336 00:15:47,880 --> 00:15:51,440 Ek kry aan die einde van my array effektief waar die getalle is, is dit verwyder 61. 337 00:15:51,440 --> 00:15:52,920 Maar ek wil nie verwyder 61. 338 00:15:52,920 --> 00:15:55,030 Ek wil om te neem 50, wat was daar by 05:00 339 00:15:55,030 --> 00:15:56,790 in lyn vir die nuwe iPhone of iets anders. 340 00:15:56,790 --> 00:16:01,200 En so om ontslae te raak van 50, ek kan dit nie net doen nie, reg? 341 00:16:01,200 --> 00:16:02,547 Ek kan kruis uit 50. 342 00:16:02,547 --> 00:16:04,380 Maar ons het net gesê ons nie so anale te wees 343 00:16:04,380 --> 00:16:06,330 as uitkrap of die data te verberg. 344 00:16:06,330 --> 00:16:08,090 Ons kan net vergeet waar dit is. 345 00:16:08,090 --> 00:16:12,330 >> Maar as ek my grootte te verander nou twee, is dit voldoende inligting 346 00:16:12,330 --> 00:16:15,711 om te weet wat aangaan in my tou? 347 00:16:15,711 --> 00:16:16,680 Nie regtig nie. 348 00:16:16,680 --> 00:16:19,830 Soos my grootte is twee nie, maar waar kom die tou te begin, 349 00:16:19,830 --> 00:16:22,980 veral as ek het nog daardie getalle in die geheue. 350 00:16:22,980 --> 00:16:24,260 50, 51, 61. 351 00:16:24,260 --> 00:16:27,090 So ek moet onthou nou waar die front is. 352 00:16:27,090 --> 00:16:29,630 En so het ek voorgestel up daar is, sal ons net genoem 353 00:16:29,630 --> 00:16:33,729 Nde voor, wie se aanvanklike waarde moet wat gewees het nie? 354 00:16:33,729 --> 00:16:35,270 Nul, net die begin van die lys. 355 00:16:35,270 --> 00:16:40,876 Maar nou in bykomend tot decrementing die grootte, het ons net inkrementeer die voorkant. 356 00:16:40,876 --> 00:16:42,000 Nou hier is nog 'n probleem. 357 00:16:42,000 --> 00:16:43,030 So wanneer ek hou. 358 00:16:43,030 --> 00:16:47,520 Veronderstel dit is die getal van soos 121, 124, en dan, dammit, 359 00:16:47,520 --> 00:16:48,610 Ek is uit die ruimte. 360 00:16:48,610 --> 00:16:50,390 Maar wag 'n minuut, ek is nie. 361 00:16:50,390 --> 00:16:55,630 So op hierdie punt in die verhaal, veronderstel dat die grootte is een, twee, 362 00:16:55,630 --> 00:17:00,370 drie, vier, so seker dat die grootte is vier die voorkant is een, 363 00:17:00,370 --> 00:17:01,621 so 51 is aan die voorkant. 364 00:17:01,621 --> 00:17:04,329 Ek wil nog 'n nommer hier sit, maar dammit, ek is uit die ruimte. 365 00:17:04,329 --> 00:17:06,710 Maar ek is nie regtig nie, reg? 366 00:17:06,710 --> 00:17:11,192 Waar kan ek 'n paar addisionele waarde soos 171? 367 00:17:11,192 --> 00:17:13,400 Ja, ek kon net soort van gaan terug daar, reg? 368 00:17:13,400 --> 00:17:18,161 En dan oor die 50, of net oorskryf met 171. 369 00:17:18,161 --> 00:17:20,410 En as jy wonder hoekom ons getalle het so random, 370 00:17:20,410 --> 00:17:24,150 hierdie is algemeen rekenaar geneem wetenskap kursusse by Harvard na CS50. 371 00:17:24,150 --> 00:17:27,510 Maar dit was 'n goeie optimalisering, want nou is ek nie mors ruimte. 372 00:17:27,510 --> 00:17:30,750 Ek het nog steeds om te onthou hoe groot hierdie ding is totaal. 373 00:17:30,750 --> 00:17:31,500 Dit is vyf totaal. 374 00:17:31,500 --> 00:17:33,375 Want ek wil nie begin oorskryf 51. 375 00:17:33,375 --> 00:17:36,260 So nou is ek nog steeds uit die ruimte, so dieselfde probleem as voorheen. 376 00:17:36,260 --> 00:17:39,140 Maar jy kan sien hoe nou in jou kode, het jy waarskynlik 377 00:17:39,140 --> 00:17:41,910 'n bietjie meer skryf kompleksiteit te maak dat gebeur. 378 00:17:41,910 --> 00:17:44,510 En in die feit, wat operateur in C waarskynlik kan 379 00:17:44,510 --> 00:17:48,110 jy dit die sirkulariteit mettertyd doen? 380 00:17:48,110 --> 00:17:50,160 Ja die modulo operateur, die persentasie teken. 381 00:17:50,160 --> 00:17:53,160 So, wat is gaaf oor 'n tou, selfs al hou ons teken skikkings 382 00:17:53,160 --> 00:17:56,520 aangesien hierdie soos reguit lyne, as jy soort dink oor dit as kromming 383 00:17:56,520 --> 00:18:00,341 rond soos 'n sirkel, dan net intuïtief dit soort van werk verstandelik 384 00:18:00,341 --> 00:18:01,590 Ek dink 'n bietjie meer skoon. 385 00:18:01,590 --> 00:18:05,190 Jy sal nog moet implementeer dat die geestelike model in die kode. 386 00:18:05,190 --> 00:18:07,550 So nie so moeilik, uiteindelik te implementeer, 387 00:18:07,550 --> 00:18:12,430 maar ons nog steeds verloor die size-- eerder die vermoë om te verander nie, tensy ons dit doen. 388 00:18:12,430 --> 00:18:15,310 >> Ons het om ontslae te raak van die skikking, ons vervang dit met 'n enkele muis, 389 00:18:15,310 --> 00:18:20,010 en dan iewers in my kode het ek 'n beroep wat funksioneer om werklik te skep 390 00:18:20,010 --> 00:18:23,720 die skikking met die naam getalle? 391 00:18:23,720 --> 00:18:26,190 Malloc, of 'n soortgelyke funksie, presies. 392 00:18:26,190 --> 00:18:30,481 Enige vrae oor stapels of toue. 393 00:18:30,481 --> 00:18:30,980 Ja? 394 00:18:30,980 --> 00:18:33,657 395 00:18:33,657 --> 00:18:34,240 Goeie vraag. 396 00:18:34,240 --> 00:18:35,830 Wat sou jy modulo hier te gebruik. 397 00:18:35,830 --> 00:18:38,520 So algemeen, by die gebruik mod, sou jy dit doen 398 00:18:38,520 --> 00:18:40,620 met die grootte van die hele data-struktuur. 399 00:18:40,620 --> 00:18:44,120 So iets soos vyf of kapasiteit, as dit is konstant, is waarskynlik betrokke is. 400 00:18:44,120 --> 00:18:47,100 Maar net modulo vyf doen waarskynlik nie voldoende is nie, 401 00:18:47,100 --> 00:18:51,380 want ons moet weet wat ons doen draai om hier of hier of hier. 402 00:18:51,380 --> 00:18:54,160 So is jy waarskynlik ook gaan wil betrek 403 00:18:54,160 --> 00:18:57,220 die grootte van die ding, of die voorkant veranderlike as well. 404 00:18:57,220 --> 00:19:00,140 So dit is net hierdie relatief eenvoudige rekenkundige uitdrukking, 405 00:19:00,140 --> 00:19:02,000 maar modulo sou die sleutel bestanddeel wees. 406 00:19:02,000 --> 00:19:03,330 >> So kort film as jy wil. 407 00:19:03,330 --> 00:19:05,780 'N animasie dat sommige mense by 'n ander universiteit 408 00:19:05,780 --> 00:19:08,060 saam te stel wat ons het aangepas is vir hierdie bespreking. 409 00:19:08,060 --> 00:19:12,630 Dit behels die leer van die Jack feite oor toue en statistieke. 410 00:19:12,630 --> 00:19:19,010 411 00:19:19,010 --> 00:19:21,890 >> Film: Eens op 'n tyd, daar was 'n man met die naam Jack. 412 00:19:21,890 --> 00:19:25,330 Wanneer dit kom by die maak van vriende, Jack het nie 'n gawe. 413 00:19:25,330 --> 00:19:28,220 So Jack het na die praat gewildste man het geweet hy. 414 00:19:28,220 --> 00:19:30,920 Hy het na Lou en gevra: Wat moet ek doen? 415 00:19:30,920 --> 00:19:33,400 Lou sien dat sy vriend was regtig ontsteld. 416 00:19:33,400 --> 00:19:36,050 Wel, het hy begin, net kyk hoe jy geklee is. 417 00:19:36,050 --> 00:19:38,680 Het jy nie 'n klere met 'n ander kyk? 418 00:19:38,680 --> 00:19:39,660 Ja, sê Jack. 419 00:19:39,660 --> 00:19:40,840 Ek seker te doen. 420 00:19:40,840 --> 00:19:43,320 Kom na my huis en Ek sal hulle jou wys. 421 00:19:43,320 --> 00:19:44,550 So het hulle af te Jack se. 422 00:19:44,550 --> 00:19:47,520 En Jack het Lou die boks waar hy het al sy hemde, 423 00:19:47,520 --> 00:19:49,260 en sy broek en sy sokkies. 424 00:19:49,260 --> 00:19:52,290 Lou het gesê: Ek sien jy het al jou klere in 'n hopie. 425 00:19:52,290 --> 00:19:54,870 Hoekom het jy nie dra n paar ander keer in 'n rukkie? 426 00:19:54,870 --> 00:19:58,020 >> Jack het gesê, wel, wanneer ek verwyder klere en sokkies, 427 00:19:58,020 --> 00:20:00,780 Ek was hulle en sit hulle weg in die boks. 428 00:20:00,780 --> 00:20:03,210 Dan kom die volgende oggend, en tot ek hop. 429 00:20:03,210 --> 00:20:06,380 Ek gaan na die boks en kry my klere af die top. 430 00:20:06,380 --> 00:20:09,070 Lou het gou besef die probleem met Jack. 431 00:20:09,070 --> 00:20:12,080 Hy het klere, CD's, en boeke in die stapel. 432 00:20:12,080 --> 00:20:14,420 Toe hy bereik vir iets om te lees of om te dra, 433 00:20:14,420 --> 00:20:17,100 Hy wil kies om die top boek of onderklere. 434 00:20:17,100 --> 00:20:19,500 Toe Hy dan gedoen is, het hy sou sit dit terug. 435 00:20:19,500 --> 00:20:21,970 Terug dit sou gaan, op die top van die stapel. 436 00:20:21,970 --> 00:20:24,460 Ek weet die oplossing, sê 'n triomfantelike Loud. 437 00:20:24,460 --> 00:20:27,090 Jy moet leer om begin met 'n tou. 438 00:20:27,090 --> 00:20:29,870 Lou het Jack se klere en hang hulle in die kas. 439 00:20:29,870 --> 00:20:32,710 En toe hy leeggemaak die boks, het hy net gooi dit. 440 00:20:32,710 --> 00:20:36,500 >> Toe sê hy nou Jack, aan die einde van die dag, sit jou klere aan die linkerkant 441 00:20:36,500 --> 00:20:37,990 wanneer jy sit hulle weg. 442 00:20:37,990 --> 00:20:41,300 Dan môre oggend wanneer jy sien die sonskyn, kry jou klere 443 00:20:41,300 --> 00:20:43,440 op die regte, van die einde van die lyn. 444 00:20:43,440 --> 00:20:44,880 Het jy nie sien nie? gesê Lou. 445 00:20:44,880 --> 00:20:46,370 Dit sal so lekker wees. 446 00:20:46,370 --> 00:20:49,770 Jy sal alles een keer dra voordat jy iets twee keer te dra. 447 00:20:49,770 --> 00:20:52,670 En met alles in toue in sy kas en rak, 448 00:20:52,670 --> 00:20:55,160 Jack begin om te voel heeltemal seker van homself. 449 00:20:55,160 --> 00:20:59,720 Alles te danke aan Lou en sy wonderlike tou. 450 00:20:59,720 --> 00:21:01,220 Spreker 1: Alle reg, dit is adorable. 451 00:21:01,220 --> 00:21:05,920 452 00:21:05,920 --> 00:21:10,080 So, wat is regtig gaan op onder die kap nou? 453 00:21:10,080 --> 00:21:12,370 Dat ons wysers, dat ons malloc, 454 00:21:12,370 --> 00:21:15,680 dat ons die vermoë om te skep stukke van die geheue vir onsself 455 00:21:15,680 --> 00:21:16,344 dinamiese. 456 00:21:16,344 --> 00:21:18,510 So dit is 'n prentjie wat ons bijhorend net die ander dag. 457 00:21:18,510 --> 00:21:21,180 Ons het nie regtig woon op dit, maar hierdie foto 458 00:21:21,180 --> 00:21:24,180 is aan die gang onder die kap vir weke nou. 459 00:21:24,180 --> 00:21:27,050 En sodat hierdie verteenwoordig, net 'n reghoek wat ons het getrek, 460 00:21:27,050 --> 00:21:28,180 jou rekenaar se geheue. 461 00:21:28,180 --> 00:21:31,850 En miskien jou rekenaar, of CS50 ID, het 'n GB geheue of RAM 462 00:21:31,850 --> 00:21:33,050 of twee gigagrepe of vier. 463 00:21:33,050 --> 00:21:34,450 Dit maak nie regtig saak nie. 464 00:21:34,450 --> 00:21:37,240 Jou bedryfstelsel Windows of Mac OS of Linux, 465 00:21:37,240 --> 00:21:41,120 kan in wese jou program om te dink dat dit toegang 466 00:21:41,120 --> 00:21:42,982 om die geheel van jou rekenaar se geheue, 467 00:21:42,982 --> 00:21:45,440 selfs al is jy kan loop verskeie programme gelyktydig. 468 00:21:45,440 --> 00:21:46,990 So in werklikheid, beteken dit nie regtig werk. 469 00:21:46,990 --> 00:21:49,448 Maar dit is soort van 'n illusie gegee om al jou programme. 470 00:21:49,448 --> 00:21:53,110 So as jy het twee gigs RAM, hierdie is hoe die rekenaar kan dink. 471 00:21:53,110 --> 00:21:57,110 >> Nou toevallig een van hierdie dinge, een van hierdie segmente van die geheue, 472 00:21:57,110 --> 00:21:58,350 word 'n stapel. 473 00:21:58,350 --> 00:22:01,680 En inderdaad enige tyd dusver skriftelik kode 474 00:22:01,680 --> 00:22:05,900 dat jy geroep het funksie, byvoorbeeld belangrikste. 475 00:22:05,900 --> 00:22:08,410 Onthou dat enige tyd wat ek het se geheue geteken rekenaar, 476 00:22:08,410 --> 00:22:10,640 Ek trek altyd soort van helfte van 'n reghoek hier 477 00:22:10,640 --> 00:22:12,520 en nie die moeite praat oor wat hierbo. 478 00:22:12,520 --> 00:22:15,980 Want as hoof genoem word, ek eis dat u hierdie stukkie van die geheue te kry 479 00:22:15,980 --> 00:22:16,970 wat gaan hier neer. 480 00:22:16,970 --> 00:22:20,650 En as 'n funksie genoem belangrikste soos swap, goed swap gaan hier. 481 00:22:20,650 --> 00:22:23,720 En dit blyk, dit is waar dit eindig. 482 00:22:23,720 --> 00:22:26,277 Op iets genoem 'n stapel binnekant van jou rekenaar se geheue. 483 00:22:26,277 --> 00:22:28,360 En aan die einde van die dag, dit is net aanspreek. 484 00:22:28,360 --> 00:22:30,680 Dit is soos byte nul, byte een byte 2000000000. 485 00:22:30,680 --> 00:22:33,130 Maar as jy dink oor dit as hierdie reghoekige voorwerp, 486 00:22:33,130 --> 00:22:35,130 al is ons elke doen tyd noem ons 'n funksie is 487 00:22:35,130 --> 00:22:37,180 gelaagdheid 'n nuwe deel van die geheue. 488 00:22:37,180 --> 00:22:41,700 Ons gee daardie funksie 'n sny van sy eie geheue om mee te werk. 489 00:22:41,700 --> 00:22:44,490 >> En onthou nou dat dit is belangrik. 490 00:22:44,490 --> 00:22:46,400 Want as ons het nie iets soos swap 491 00:22:46,400 --> 00:22:51,610 en twee plaaslike veranderlikes soos A en B en ons daardie waardes van een en twee 492 00:22:51,610 --> 00:22:55,130 twee en een, onthou dat wanneer swap terugkom, 493 00:22:55,130 --> 00:22:58,330 dit is asof hierdie stukkie geheue is net weg. 494 00:22:58,330 --> 00:23:00,080 In werklikheid, dit is nog steeds daar forensies. 495 00:23:00,080 --> 00:23:01,940 En iets is eintlik nog steeds daar. 496 00:23:01,940 --> 00:23:05,410 Maar konseptueel, dit is so al is dit heeltemal weg. 497 00:23:05,410 --> 00:23:10,910 En so hoof nie weet enige van die werk wat gedoen is in daardie swap funksie, 498 00:23:10,910 --> 00:23:14,890 tensy dit eintlik in daardie is verby argumente deur wyser of deur verwysing. 499 00:23:14,890 --> 00:23:17,790 Nou, die fundamentele oplossing dat die probleem met swap 500 00:23:17,790 --> 00:23:19,970 verby dinge in deur adres. 501 00:23:19,970 --> 00:23:23,250 Maar dit blyk ook wat is is aan die gang bo wat deel 502 00:23:23,250 --> 00:23:26,330 van die reghoek al hierdie tyd is tog is daar daar meer geheue up. 503 00:23:26,330 --> 00:23:28,790 En wanneer jy dinamies toeken geheue, 504 00:23:28,790 --> 00:23:32,020 of dit nou binne GetString, wat ons het al te doen vir jou in die CS50 505 00:23:32,020 --> 00:23:34,710 biblioteek, of as jy ouens noem malloc en vra 506 00:23:34,710 --> 00:23:37,950 die bedryfstelsel vir 'n stuk van geheue, beteken dit nie kom uit die stapel. 507 00:23:37,950 --> 00:23:40,960 Dit kom van 'n ander plek in jou rekenaar se geheue 508 00:23:40,960 --> 00:23:42,220 Dit is genoem die hoop. 509 00:23:42,220 --> 00:23:43,430 En dit is nie 'n verskil. 510 00:23:43,430 --> 00:23:44,285 Dit is dieselfde RAM. 511 00:23:44,285 --> 00:23:45,160 Dit is dieselfde geheue. 512 00:23:45,160 --> 00:23:49,080 Dis net die geheue wat tot daar in plaas van af hier. 513 00:23:49,080 --> 00:23:50,750 >> En so wat beteken dit? 514 00:23:50,750 --> 00:23:53,650 Wel, as jou rekenaar het 'n eindige hoeveelheid geheue 515 00:23:53,650 --> 00:23:57,450 en die stapel grootword, so om te praat, en die hoop, volgens 516 00:23:57,450 --> 00:23:59,349 hierdie pyl, groei af. 517 00:23:59,349 --> 00:24:01,140 Met ander woorde, elke tyd wat jy malloc noem, 518 00:24:01,140 --> 00:24:03,430 jy word gegee 'n sny geheue van bo, 519 00:24:03,430 --> 00:24:06,630 dan miskien 'n bietjie laer, dan 'n bietjie laer, elke keer as jy malloc noem, 520 00:24:06,630 --> 00:24:10,100 die hoop, dit is gebruik, is 'n soort van groei, 521 00:24:10,100 --> 00:24:11,950 groeiende nader en nader aan wat? 522 00:24:11,950 --> 00:24:13,382 Die stapel. 523 00:24:13,382 --> 00:24:14,840 So het dit lyk soos 'n goeie idee? 524 00:24:14,840 --> 00:24:18,420 525 00:24:18,420 --> 00:24:22,140 Ek bedoel, waar dit is nie regtig duidelik Wat anders wat jy kan doen as jy net 526 00:24:22,140 --> 00:24:23,910 het 'n beperkte bedrag van die geheue. 527 00:24:23,910 --> 00:24:25,200 Maar dit is sekerlik sleg. 528 00:24:25,200 --> 00:24:27,920 Dié twee pyle op 'n crash kursus vir mekaar. 529 00:24:27,920 --> 00:24:31,930 >> En dit blyk dat slegte ou, mense wat is besonder goed met die ontwikkeling, 530 00:24:31,930 --> 00:24:36,140 en probeer om te hack in rekenaars, kan hierdie realiteit te ontgin. 531 00:24:36,140 --> 00:24:38,290 In werklikheid, laat ons kyk 'n bietjie brokkie. 532 00:24:38,290 --> 00:24:41,350 So, dit is 'n voorbeeld wat jy kan lees oor in meer besonderhede oor Wikipedia. 533 00:24:41,350 --> 00:24:43,100 Ons sal jou wys by die artikel as nuuskierig. 534 00:24:43,100 --> 00:24:45,650 Maar daar is 'n aanval in die algemeen bekend as buffer oorloop dat 535 00:24:45,650 --> 00:24:49,570 bestaan ​​vir so lank as die mens die vermoë om te manipuleer het 536 00:24:49,570 --> 00:24:53,120 se rekenaar geheue, veral in C. So, dit is 'n baie arbitrêre program, 537 00:24:53,120 --> 00:24:55,130 maar laat ons lees dit van onder af. 538 00:24:55,130 --> 00:24:57,650 Main in argC char star argV. 539 00:24:57,650 --> 00:24:59,830 So dit is 'n program wat neem command line argumente. 540 00:24:59,830 --> 00:25:03,620 En al die vernaamste blykbaar is call 'n funksie, noem dit F vir eenvoud. 541 00:25:03,620 --> 00:25:04,610 En dit verby in wat? 542 00:25:04,610 --> 00:25:05,490 ArgV een. 543 00:25:05,490 --> 00:25:09,320 Dit gaan so in F ookal die woord is dat die gebruiker getik 544 00:25:09,320 --> 00:25:11,500 op die instruksielyn na die naam program by. 545 00:25:11,500 --> 00:25:15,730 Soveel soos Caesar of Vigenere, wat u sal onthou te doen met argV. 546 00:25:15,730 --> 00:25:16,680 >> So, wat is F? 547 00:25:16,680 --> 00:25:19,760 F neem in 'n string as sy enigste argument, 548 00:25:19,760 --> 00:25:22,100 AKA n kar ster dieselfde ding, as 'n string. 549 00:25:22,100 --> 00:25:24,920 En dit is arbitrêr genoem bar in hierdie voorbeeld. 550 00:25:24,920 --> 00:25:27,710 En dan char c 12, net in leketaal, 551 00:25:27,710 --> 00:25:31,750 wat char c bracket 12 vir ons doen? 552 00:25:31,750 --> 00:25:33,440 Wat doen dit? 553 00:25:33,440 --> 00:25:36,490 Toekenning geheue, spesifiek 12 grepe vir 12 karakters. 554 00:25:36,490 --> 00:25:36,990 Presies. 555 00:25:36,990 --> 00:25:40,000 En dan is die laaste linie, roer en kopie, jy het waarskynlik nie gesien nie. 556 00:25:40,000 --> 00:25:43,360 Dit is 'n string kopie funksie waarvan die doel in die lewe 557 00:25:43,360 --> 00:25:48,160 is om sy tweede argument kopieer in sy eerste argument, 558 00:25:48,160 --> 00:25:51,190 maar slegs tot op 'n sekere aantal grepe. 559 00:25:51,190 --> 00:25:53,860 So die derde argument sê, hoeveel bytes moet jy kopieer? 560 00:25:53,860 --> 00:25:56,720 Die lengte van bar, Wat ook al die gebruiker getik. 561 00:25:56,720 --> 00:25:59,320 En die inhoud van Bar, wat string, is 562 00:25:59,320 --> 00:26:02,330 in die geheue gekopieer wys na by C. 563 00:26:02,330 --> 00:26:04,060 >> So dit lyk soort van dom, en dit is nie. 564 00:26:04,060 --> 00:26:06,300 Dit is 'n geforseerde byvoorbeeld maar dit is verteenwoordigend 565 00:26:06,300 --> 00:26:10,100 van 'n klas van die aanval vektore, 'n manier van die aanval van 'n program. 566 00:26:10,100 --> 00:26:15,050 Alles is goed en goed as die gebruiker tipes in 'n woord wat 11 karakters 567 00:26:15,050 --> 00:26:18,040 of minder, plus agteroorskuisstreep nul. 568 00:26:18,040 --> 00:26:22,830 Wat as die gebruiker in meer as 11 of 12 of 20 of 50 karakters? 569 00:26:22,830 --> 00:26:25,090 Wat is dié program gaan doen? 570 00:26:25,090 --> 00:26:29,360 Potensieel seg skuld. Dit gaan blindelings alles bar up kopieer 571 00:26:29,360 --> 00:26:31,750 om sy lengte, wat letterlik alles in bar, 572 00:26:31,750 --> 00:26:36,307 in die adres daarop by C. Maar C slegs preemptively gegee as 12 grepe. 573 00:26:36,307 --> 00:26:37,640 Maar daar is geen bykomende tjek. 574 00:26:37,640 --> 00:26:38,700 Daar is geen indien toestande. 575 00:26:38,700 --> 00:26:40,580 Daar is geen fout hier te keur. 576 00:26:40,580 --> 00:26:43,270 >> En ja, wat die program is gaan doen, is net blindelings 577 00:26:43,270 --> 00:26:45,750 kopieer een ding na die ander. 578 00:26:45,750 --> 00:26:47,880 En so as ons dit trek as 'n foto, hier is 579 00:26:47,880 --> 00:26:49,860 net 'n stukkie van die geheue spasie. 580 00:26:49,860 --> 00:26:53,470 So sien aan die onderkant, ons het die plaaslike veranderlike bar. 581 00:26:53,470 --> 00:26:57,330 Sodat wyser wat gaan store-- eerder dat plaaslike argument wat 582 00:26:57,330 --> 00:26:58,672 gaan na die string bar te stoor. 583 00:26:58,672 --> 00:27:00,380 En dan sien net bo dit in 'n stapel, 584 00:27:00,380 --> 00:27:02,505 want elke keer as jy vra vir die geheue op die stapel, 585 00:27:02,505 --> 00:27:04,310 dit gaan 'n bietjie bo dit picturaal, 586 00:27:04,310 --> 00:27:06,270 kennis dat ons daar het 12 grepe. 587 00:27:06,270 --> 00:27:10,690 Links bo een is C bracket nul en die onderste regterkantste een is C bracket 11. 588 00:27:10,690 --> 00:27:12,870 Dit is net hoe die rekenaars gaan om dit uit te lê. 589 00:27:12,870 --> 00:27:18,300 Dus net intuïtief, as bar het meer as 12 karakters in totaal, insluitend 590 00:27:18,300 --> 00:27:25,790 agteroorskuisstreep nul, waar is die 12 of die C bracket 12 gaan om te gaan? 591 00:27:25,790 --> 00:27:28,440 Of eerder waar is die 12de karakter of die 13de karakter, 592 00:27:28,440 --> 00:27:30,900 die honderdste karakter gaan aan die einde in die prentjie? 593 00:27:30,900 --> 00:27:33,400 Bo of onder? 594 00:27:33,400 --> 00:27:36,300 >> Reg, want selfs al die stapel self groei daarbo, 595 00:27:36,300 --> 00:27:39,590 sodra jy dinge gesit het in , is dit vir die ontwerp redes, 596 00:27:39,590 --> 00:27:41,294 plaas die geheue van bo tot onder. 597 00:27:41,294 --> 00:27:44,460 So as jy het meer as 12 grepe, jy gaan om te begin om bar te vervang. 598 00:27:44,460 --> 00:27:47,280 Nou is dit 'n fout nie, maar dit is nie regtig 'n groot deal. 599 00:27:47,280 --> 00:27:51,130 Maar dit is 'n groot deal, want daar is meer dinge aan die gang in die geheue. 600 00:27:51,130 --> 00:27:53,074 So hier is hoe ons sit hello, duidelik te wees. 601 00:27:53,074 --> 00:27:54,490 As ek getik in hallo op die instruksielyn. 602 00:27:54,490 --> 00:27:59,330 H-E-L-L-O backslash nul eindig binne diegene 12 grepe, en ons is super veilig. 603 00:27:59,330 --> 00:28:00,330 Alles is goed. 604 00:28:00,330 --> 00:28:03,020 Maar as ek iets tik langer, dit is potensieel 605 00:28:03,020 --> 00:28:05,860 gaan kruip in bar ruimte. 606 00:28:05,860 --> 00:28:08,405 Maar erger nog, dit blyk al hierdie tyd, 607 00:28:08,405 --> 00:28:11,530 selfs al het ons nog nooit gepraat oor dit is die stapel gebruik word vir ander dinge. 608 00:28:11,530 --> 00:28:13,560 Dit is nie net die plaaslike veranderlikes. 609 00:28:13,560 --> 00:28:15,100 >> C is 'n baie lae vlak taal. 610 00:28:15,100 --> 00:28:17,810 En dit soort van die geheim gebruik die stapel ook 611 00:28:17,810 --> 00:28:21,260 om te onthou wanneer 'n funksie genoem word, wat 612 00:28:21,260 --> 00:28:26,040 die adres van die vorige funksie, sodat dit kan terug na daardie funksie te spring. 613 00:28:26,040 --> 00:28:29,980 So wanneer hoof oproepe te ruil, onder die dinge op die stapel geplaas 614 00:28:29,980 --> 00:28:34,380 is nie net swaps plaaslike veranderlikes, of ook die geheim gestoot sy argumente, 615 00:28:34,380 --> 00:28:37,510 op die stapel soos verteenwoordig deur hier die rooi sny, 616 00:28:37,510 --> 00:28:40,520 is die adres van hoof fisies in jou rekenaar se geheue, 617 00:28:40,520 --> 00:28:44,180 sodat wanneer ruil is gedoen, die rekenaar weet wat ek nodig het om terug te gaan na die hoof 618 00:28:44,180 --> 00:28:46,760 en eindig uitvoering van die belangrikste funksie. 619 00:28:46,760 --> 00:28:51,960 So dit is nou gevaarlik, want as die gebruiker in goed meer as hello, 620 00:28:51,960 --> 00:28:57,030 sodanig dat die invoer van die gebruiker se clobbers of oor skryf dat die rooi gedeelte, 621 00:28:57,030 --> 00:28:59,820 logies as die rekenaar se net gaan om blindelings aanvaar 622 00:28:59,820 --> 00:29:03,830 dat die grepe in daardie rooi skyfie is die adres waarheen dit moet terugkeer, 623 00:29:03,830 --> 00:29:09,020 Wat as die teenstander is slim genoeg of gelukkig genoeg om 'n reeks van grepe sit 624 00:29:09,020 --> 00:29:13,450 daar wat lyk soos 'n adres, maar dit is die adres van die kode 625 00:29:13,450 --> 00:29:18,730 dat hy of sy wil die rekenaar om uit te voer in plaas van die belangrikste? 626 00:29:18,730 --> 00:29:21,670 >> Met ander woorde, as wat die gebruiker tik op die instruksielyn, 627 00:29:21,670 --> 00:29:23,850 is nie net iets onskadelike soos hello, 628 00:29:23,850 --> 00:29:28,210 maar dit is eintlik kode wat is ekwivalent om al die lêers se gebruiker verwyder? 629 00:29:28,210 --> 00:29:30,060 Of e-pos hul wagwoord na my toe? 630 00:29:30,060 --> 00:29:31,940 Of begin meld hul toetsaanslagen, reg? 631 00:29:31,940 --> 00:29:34,920 Daar is 'n manier, laat ons vandag stipuleer, dat hulle kan tik in nie net hallo 632 00:29:34,920 --> 00:29:36,711 wêreld of hul naam, hulle kon in wese 633 00:29:36,711 --> 00:29:39,570 slaag in die kode, nulle en kinders, wat die rekenaar 634 00:29:39,570 --> 00:29:43,450 foute vir beide kode en 'n adres. 635 00:29:43,450 --> 00:29:48,950 So hoewel ietwat abstrakte, indien die tipes gebruiker genoeg opponerende kode 636 00:29:48,950 --> 00:29:52,330 dat ons hier as jy veralgemeen A. A is aanval of teëstanders. 637 00:29:52,330 --> 00:29:53,140 Dus net slegte dinge. 638 00:29:53,140 --> 00:29:55,306 Ons gee nie om oor die getalle of die nulle of kinders 639 00:29:55,306 --> 00:29:59,470 vandag, soos wat jy beland oorskryf dat die rooi gedeelte, 640 00:29:59,470 --> 00:30:01,580 sien dat die volgorde van grepe. 641 00:30:01,580 --> 00:30:05,020 O 835 C nul agt nul. 642 00:30:05,020 --> 00:30:08,960 En nou as Wikipedia se artikel hier het voorgestel, as jy nou eintlik begin 643 00:30:08,960 --> 00:30:12,460 etikettering van die grepe in jou rekenaar se geheue, wat die Wikipedia artikel is 644 00:30:12,460 --> 00:30:19,060 stel is dat, wat as die adres van daardie boonste linkerkantste byte is 80 C 0 3508. 645 00:30:19,060 --> 00:30:22,200 >> Met ander woorde, as die slegte ou is slim genoeg met sy of haar code 646 00:30:22,200 --> 00:30:26,650 om werklik te sit hier 'n getal wat ooreenstem met die adres van die kode 647 00:30:26,650 --> 00:30:29,180 hy of sy ingespuit in die rekenaar, het jy 648 00:30:29,180 --> 00:30:31,050 kan die rekenaar te mislei in enigiets doen. 649 00:30:31,050 --> 00:30:34,140 Die verwydering van lêers, e-pos dinge, snuif jou verkeer, 650 00:30:34,140 --> 00:30:36,710 letterlik enigiets kan wees ingespuit word in die rekenaar. 651 00:30:36,710 --> 00:30:39,220 En so 'n buffer oorloop aanval op sy kern 652 00:30:39,220 --> 00:30:43,530 is net 'n dom, dom oorheersende van 'n skikking wat 653 00:30:43,530 --> 00:30:45,840 het nie sy grense nagegaan. 654 00:30:45,840 --> 00:30:48,850 En dit is wat is super gevaarlike en terselfdertyd super kragtige 655 00:30:48,850 --> 00:30:52,560 in C is dat ons inderdaad toegang tot enige plek in die geheue. 656 00:30:52,560 --> 00:30:55,320 Dit is aan ons, die programmeerders, wat die oorspronklike kode te skryf 657 00:30:55,320 --> 00:30:59,330 die darn lengte van enige tjek skikkings wat ons manipuleer. 658 00:30:59,330 --> 00:31:00,750 So duidelik wees, wat is die oplossing? 659 00:31:00,750 --> 00:31:03,190 As ons terug gaan na hierdie kode, sou ek nie net 660 00:31:03,190 --> 00:31:08,000 verander die lengte van bar, wat anders moet ek nagaan? 661 00:31:08,000 --> 00:31:10,620 Wat anders moet ek doen om heeltemal te verhoed dat hierdie aanval? 662 00:31:10,620 --> 00:31:14,110 Ek wil nie net blindelings sê dat jy soveel grepe moet kopieer 663 00:31:14,110 --> 00:31:16,140 soos die lengte van bar. 664 00:31:16,140 --> 00:31:18,910 Ek wil om te sê, as kopieer baie grepe as in bar 665 00:31:18,910 --> 00:31:24,090 tot die toegekende geheue, of 12 maksimaal. 666 00:31:24,090 --> 00:31:27,450 So ek moet 'n soort van as voorwaarde wat nie gaan die lengte van bar, 667 00:31:27,450 --> 00:31:32,800 maar as dit 12, het ons net hard-kode oorskry 12 as die maksimum moontlike afstand. 668 00:31:32,800 --> 00:31:35,910 Anders sal die sogenaamde buffer oorloop aanval kan gebeur. 669 00:31:35,910 --> 00:31:38,451 Aan die onderkant van die skyfies, As jy nuuskierig om meer te lees is 670 00:31:38,451 --> 00:31:41,200 is die werklike oorspronklike artikel As jy wil om 'n blik te neem. 671 00:31:41,200 --> 00:31:44,550 >> Maar nou, onder die pryse hier betaal is, was ondoeltreffendheid. 672 00:31:44,550 --> 00:31:46,680 So dit was 'n vinnige lae vlak kyk na wat 673 00:31:46,680 --> 00:31:49,709 probleme kan nou ontstaan ​​dat ons toegang tot die geheue se rekenaar. 674 00:31:49,709 --> 00:31:51,750 Maar 'n ander probleem wat ons wat reeds op Maandag gestruikel 675 00:31:51,750 --> 00:31:53,800 was net die ondoeltreffendheid van 'n geskakelde lys. 676 00:31:53,800 --> 00:31:56,019 Ons is terug na lineêre tyd. 677 00:31:56,019 --> 00:31:57,560 Ons het 'n aangrensende verskeidenheid nie meer nie. 678 00:31:57,560 --> 00:31:58,980 Ons het nie 'n ewekansige toegang. 679 00:31:58,980 --> 00:32:00,710 Ons kan nie gebruik vierkante hakienotasie. 680 00:32:00,710 --> 00:32:04,590 Ons het letterlik 'n while lus gebruik soos die een wat ek geskryf het 'n oomblik gelede. 681 00:32:04,590 --> 00:32:09,740 Maar op Maandag, ons beweer dat ons kan kruip terug in die ryk van die doeltreffendheid 682 00:32:09,740 --> 00:32:13,040 bereiking iets wat logaritmiese miskien, of die beste nog, 683 00:32:13,040 --> 00:32:16,120 miskien selfs iets wat sogenaamde konstante tyd. 684 00:32:16,120 --> 00:32:19,840 So, hoe kan ons dit doen deur die gebruik van hierdie nuwe gereedskap, hierdie adresse hierdie wysers, 685 00:32:19,840 --> 00:32:22,210 en threading dinge van ons eie? 686 00:32:22,210 --> 00:32:23,960 Wel, gestel dat hier, dit is 'n klomp 687 00:32:23,960 --> 00:32:27,170 getalle wat ons wil om te slaan in 'n data struktuur en soek doeltreffend. 688 00:32:27,170 --> 00:32:30,960 Ons kan absoluut rewind tot week twee, gooi dit in 'n skikking, 689 00:32:30,960 --> 00:32:33,150 en soek hulle met behulp van binêre soek. 690 00:32:33,150 --> 00:32:34,040 Verdeel en oorwin. 691 00:32:34,040 --> 00:32:37,720 En in die feit dat jy geskryf het binêre soek in PSET3, 692 00:32:37,720 --> 00:32:40,100 waar jy die vonds program geïmplementeer word. 693 00:32:40,100 --> 00:32:40,890 Maar jy weet wat. 694 00:32:40,890 --> 00:32:45,060 Daar is soort van 'n meer slim manier om dit te doen. 695 00:32:45,060 --> 00:32:47,390 Dit is 'n bietjie meer gesofistikeerd en dit miskien 696 00:32:47,390 --> 00:32:50,830 kan ons sien waarom binêre soek is soveel vinniger. 697 00:32:50,830 --> 00:32:52,980 Eerstens, laat ons stel die idee van 'n boom. 698 00:32:52,980 --> 00:32:54,730 Wat al in werklikheid bome soort 699 00:32:54,730 --> 00:32:57,730 groei soos hierdie, in die wêreld van die rekenaar wetenskap hulle soort afwaartse groei 700 00:32:57,730 --> 00:33:00,830 soos 'n stamboom waar jy jou grootouers of grootouers 701 00:33:00,830 --> 00:33:04,580 of iets anders aan die bokant, die aartsvader en die matriarg van die familie, net een 702 00:33:04,580 --> 00:33:07,930 sogenaamde wortel, knoop, onder wat sy kinders is, 703 00:33:07,930 --> 00:33:11,442 hieronder wat is sy kinders, of sy nageslag meer algemeen. 704 00:33:11,442 --> 00:33:13,400 En enigiemand hang af die onderkant van die familie 705 00:33:13,400 --> 00:33:16,070 boom, naas die jongste in die gesin, 706 00:33:16,070 --> 00:33:19,520 kan ook net generies wees genoem die blare van die boom. 707 00:33:19,520 --> 00:33:21,800 >> So dit is net 'n klomp van woorde en definisies 708 00:33:21,800 --> 00:33:25,790 vir iets genoem 'n boom in die rekenaar wetenskap, baie soos 'n stamboom. 709 00:33:25,790 --> 00:33:28,770 Maar daar is liefhebber inkarnasies van die bome, waarvan een 710 00:33:28,770 --> 00:33:30,780 word 'n binêre soek boom. 711 00:33:30,780 --> 00:33:34,380 En jy kan soort van terg afgesien wat hierdie ding doen. 712 00:33:34,380 --> 00:33:37,180 Wel, dit is binêre in watter sin? 713 00:33:37,180 --> 00:33:41,455 Waar kom die binêre kom van hier af? 714 00:33:41,455 --> 00:33:41,955 Jammer? 715 00:33:41,955 --> 00:33:45,961 716 00:33:45,961 --> 00:33:47,210 Dit is nie soseer 'n een of. 717 00:33:47,210 --> 00:33:52,000 Dit is meer dat elkeen van die nodes het geen meer as twee kinders, as ons hier sien. 718 00:33:52,000 --> 00:33:54,990 In die algemeen, 'n tree-- en jou ouers en grootouers 719 00:33:54,990 --> 00:33:57,640 kan soveel kinders het of kleinkinders as hulle eintlik wil hê, 720 00:33:57,640 --> 00:34:00,820 en so byvoorbeeld is daar drie het ons kinders af dat regterhand knoop, 721 00:34:00,820 --> 00:34:05,480 maar in 'n binêre boom, 'n node het nul, een, of twee kinders maksimaal. 722 00:34:05,480 --> 00:34:08,496 En dit is 'n mooi eiendom, want as dit beperk deur twee 723 00:34:08,496 --> 00:34:10,620 ons gaan in staat wees om kry 'n bietjie log basis twee 724 00:34:10,620 --> 00:34:11,975 aksie gaan hier uiteindelik. 725 00:34:11,975 --> 00:34:13,350 So het ons iets logaritmiese. 726 00:34:13,350 --> 00:34:14,558 Maar meer oor dit in 'n oomblik. 727 00:34:14,558 --> 00:34:19,810 Soek boom beteken dat die getalle is gereël sodat die linker kind se 728 00:34:19,810 --> 00:34:22,429 waarde is groter as die wortel. 729 00:34:22,429 --> 00:34:26,010 En sy reg kind groter as die wortel. 730 00:34:26,010 --> 00:34:29,290 Met ander woorde, as jy enige van die neem nodes, die sirkels in hierdie foto, 731 00:34:29,290 --> 00:34:31,840 en kyk na die links kind en sy regte kind, 732 00:34:31,840 --> 00:34:34,739 die eerste minder as moet wees, die tweede moet groter wees as. 733 00:34:34,739 --> 00:34:36,159 So gesonde verstand gaan 55. 734 00:34:36,159 --> 00:34:37,780 Dit is links kind 33. 735 00:34:37,780 --> 00:34:38,620 Dit is minder as. 736 00:34:38,620 --> 00:34:40,929 55, sy reg kind 77. 737 00:34:40,929 --> 00:34:41,783 Dit is groter as. 738 00:34:41,783 --> 00:34:43,199 En dit is 'n rekursiewe definisie. 739 00:34:43,199 --> 00:34:46,480 Ons kon elke een van daardie kyk nodes en dieselfde patroon sou hou. 740 00:34:46,480 --> 00:34:49,389 >> So, wat is lekker in 'n binêre soek boom is 741 00:34:49,389 --> 00:34:52,204 dat 'n mens, kan ons dit implementeer met 'n struct, net soos hierdie. 742 00:34:52,204 --> 00:34:54,620 En selfs al is ons gooi baie van die strukture op jou, 743 00:34:54,620 --> 00:34:56,560 hulle is ietwat intuïtief nou hopelik. 744 00:34:56,560 --> 00:35:00,570 Die sintaksis nog arcane vir seker, maar die inhoud van 'n node in hierdie 745 00:35:00,570 --> 00:35:02,786 context-- en hou ons gebruik van die woord node, 746 00:35:02,786 --> 00:35:04,910 of dit 'n reghoek op die skerm of 'n sirkel, 747 00:35:04,910 --> 00:35:08,970 dit is net 'n paar generiese houer, in hierdie geval van 'n boom, soos die een 748 00:35:08,970 --> 00:35:11,780 ons gesien het, het ons 'n heelgetal nodig in elk van die nodes 749 00:35:11,780 --> 00:35:15,460 en dan moet ek twee wysers wys aan die linkerkant kind en die regte kind, 750 00:35:15,460 --> 00:35:16,590 onderskeidelik. 751 00:35:16,590 --> 00:35:20,730 So dit is hoe ons dalk implementeer wat in 'n struct. 752 00:35:20,730 --> 00:35:22,315 En hoe kan ek dit implementeer in die kode? 753 00:35:22,315 --> 00:35:26,730 Wel, laat ons neem 'n vinnige kyk na hierdie klein voorbeeld. 754 00:35:26,730 --> 00:35:29,820 Dit is nie funksioneel nie, maar ek het gekopieer en geplak daardie struktuur. 755 00:35:29,820 --> 00:35:33,510 En as my funksie vir 'n binêre soek boom search genoem, 756 00:35:33,510 --> 00:35:36,980 en dit neem twee argumente, 'n heelgetal N en 'n wyser 757 00:35:36,980 --> 00:35:41,400 om 'n knoop, so 'n verwysing na die boom of 'n verwysing na die wortel van 'n boom, 758 00:35:41,400 --> 00:35:43,482 hoe gaan ek oor die soek na N? 759 00:35:43,482 --> 00:35:45,440 Wel, die eerste, want ek is hantering van wysers, 760 00:35:45,440 --> 00:35:46,750 Ek gaan 'n gesonde verstand tjek te doen. 761 00:35:46,750 --> 00:35:54,279 As boom gelykes gelyk null, is N in hierdie boom of nie in hierdie boom? 762 00:35:54,279 --> 00:35:55,070 Dit kan nie wees nie, reg? 763 00:35:55,070 --> 00:35:56,870 As ek verlede nul, daar is niks. 764 00:35:56,870 --> 00:35:59,230 Ek kan net sowel blindelings sê terugkeer onwaar. 765 00:35:59,230 --> 00:36:04,050 As jy gee my niks, ek kan sekerlik nie vind 'n aantal N. So wat anders kan ek 766 00:36:04,050 --> 00:36:04,750 kyk nou? 767 00:36:04,750 --> 00:36:12,830 Ek gaan ook anders as N is sê minder as wat ookal op die boom node 768 00:36:12,830 --> 00:36:16,300 wat ek ingehandig N waarde. 769 00:36:16,300 --> 00:36:20,270 Met ander woorde, indien die aantal Ek is soek, N, is minder as die node 770 00:36:20,270 --> 00:36:21,340 dat ek is op soek na. 771 00:36:21,340 --> 00:36:23,190 En die knoop ek soek At is boom genoem, 772 00:36:23,190 --> 00:36:26,370 en onthou uit die vorige voorbeeld op die waarde te kry in 'n wyser, 773 00:36:26,370 --> 00:36:28,310 Ek gebruik die pyl notasie. 774 00:36:28,310 --> 00:36:35,960 So as N minder as boom pyl N, ek wil konseptueel gaan links. 775 00:36:35,960 --> 00:36:38,590 Hoe kan ek uitdruklike soek gelaat? 776 00:36:38,590 --> 00:36:41,560 Om duidelik te wees, indien dit die prentjie in die vraag, 777 00:36:41,560 --> 00:36:44,612 en ek het geslaag dat boonste arrow dit is wys af. 778 00:36:44,612 --> 00:36:45,570 Dit is my boom wyser. 779 00:36:45,570 --> 00:36:48,060 Ek wys aan die wortel van die boom. 780 00:36:48,060 --> 00:36:52,100 En ek is op soek sê vir die aantal 44, arbitrêr. 781 00:36:52,100 --> 00:36:55,300 Is 44 minder as of groter as 55 natuurlik? 782 00:36:55,300 --> 00:36:56,360 So dit is minder as. 783 00:36:56,360 --> 00:36:58,760 En so gaan dit as voorwaarde geld. 784 00:36:58,760 --> 00:37:03,981 So konseptueel, wat wil ek soek volgende as ek is op soek na 44? 785 00:37:03,981 --> 00:37:04,480 Ja? 786 00:37:04,480 --> 00:37:08,310 787 00:37:08,310 --> 00:37:11,100 >> Presies, ek wil soek die linker kind 788 00:37:11,100 --> 00:37:12,789 of links sub-boom van hierdie foto. 789 00:37:12,789 --> 00:37:14,830 En in die feit, laat my deur die prentjie hier af 790 00:37:14,830 --> 00:37:17,770 vir 'n oomblik, aangesien Ek kan dit nie krap nie. 791 00:37:17,770 --> 00:37:21,150 As ek hier begin op 55, en Ek weet dat die waarde 44 792 00:37:21,150 --> 00:37:23,180 Ek soek is na links, dit is soort 793 00:37:23,180 --> 00:37:26,010 van soos skeur die telefoon boek in half of skeur die boom in die helfte. 794 00:37:26,010 --> 00:37:29,660 Ek het nie meer te bekommer oor hierdie hele helfte van die boom. 795 00:37:29,660 --> 00:37:33,270 En tog, vreemd in terme van die struktuur, hierdie ding hier dat 796 00:37:33,270 --> 00:37:36,682 begin met 33, wat homself is 'n binêre soek boom. 797 00:37:36,682 --> 00:37:39,890 Ek het gesê die woord rekursiewe voor omdat inderdaad dit is 'n struktuur wat data 798 00:37:39,890 --> 00:37:41,707 per definisie is rekursiewe. 799 00:37:41,707 --> 00:37:44,540 Jy kan 'n boom wat is dié het groot nie, maar elkeen van sy kinders 800 00:37:44,540 --> 00:37:46,870 verteenwoordig 'n boom net 'n bietjie kleiner. 801 00:37:46,870 --> 00:37:50,910 In plaas daarvan dat oupa of ouma, nou is dit net ma 802 00:37:50,910 --> 00:37:54,300 or-- Ek kan nie say-- nie ma of pa, sou vreemd wees. 803 00:37:54,300 --> 00:37:59,000 Plaas die twee kinders is daar sou wees soos broer en suster. 804 00:37:59,000 --> 00:38:01,120 'N nuwe generasie van die familie boom. 805 00:38:01,120 --> 00:38:02,900 Maar struktureel, dit is dieselfde idee. 806 00:38:02,900 --> 00:38:06,790 En dit blyk ek het 'n funksie waarmee ek 'n binêre soek kan soek 807 00:38:06,790 --> 00:38:07,290 boom. 808 00:38:07,290 --> 00:38:08,680 Dit is search genoem. 809 00:38:08,680 --> 00:38:17,870 Ek soek in die boom N pyl links anders as N is groter as die waarde 810 00:38:17,870 --> 00:38:18,870 dat ek tans op. 811 00:38:18,870 --> 00:38:20,800 55 in die storie 'n oomblik gelede. 812 00:38:20,800 --> 00:38:23,780 Ek het 'n funksie genoem soek wat ek kan net 813 00:38:23,780 --> 00:38:29,660 slaag N hierdie en rekursief soek die sub-boom en net terugkeer 814 00:38:29,660 --> 00:38:30,620 wat dit ook al antwoord. 815 00:38:30,620 --> 00:38:33,530 Anders wat ek het 'n paar finale basis geval het hier. 816 00:38:33,530 --> 00:38:35,310 >> Wat is die finale geval? 817 00:38:35,310 --> 00:38:36,570 Boom is óf null. 818 00:38:36,570 --> 00:38:39,980 Die waarde wat ek soek, is óf minder as wat dit of groter is as wat 819 00:38:39,980 --> 00:38:42,610 of gelyk aan dit. 820 00:38:42,610 --> 00:38:44,750 En ek kon gelyk sê gelyk, maar dit is logies 821 00:38:44,750 --> 00:38:46,500 gelykstaande aan net hier sê anders. 822 00:38:46,500 --> 00:38:49,150 So waar is hoe ek iets vind. 823 00:38:49,150 --> 00:38:51,710 So hopelik is dit 'n selfs meer dwingende byvoorbeeld 824 00:38:51,710 --> 00:38:54,900 as die dom sigma funksie ons het 'n paar lesings terug, 825 00:38:54,900 --> 00:38:58,360 waar dit was net so maklik om 'n lus gebruik tel tot al die getalle van een 826 00:38:58,360 --> 00:39:02,390 om N. Hier met 'n datastruktuur wat homself is rekursief 827 00:39:02,390 --> 00:39:07,050 gedefinieer en rekursief getrek, nou is ons het die vermoë om onsself uit te druk 828 00:39:07,050 --> 00:39:09,780 in kode wat self rekursiewe. 829 00:39:09,780 --> 00:39:12,580 So, dit is die presiese dieselfde kode hier. 830 00:39:12,580 --> 00:39:14,400 >> So, wat ander probleme kan ons op te los? 831 00:39:14,400 --> 00:39:18,160 So 'n vinnige stap weg van bome vir net 'n oomblik. 832 00:39:18,160 --> 00:39:20,130 Hier is, sê die Duitse vlag. 833 00:39:20,130 --> 00:39:22,020 En daar is duidelik 'n patroon om hierdie vlag. 834 00:39:22,020 --> 00:39:23,811 En daar is baie van die vlae in die wêreld wat 835 00:39:23,811 --> 00:39:27,560 is so eenvoudig soos dit in terme van hul kleure en patrone. 836 00:39:27,560 --> 00:39:31,930 Maar veronderstel dat dit gestoor as 'n GIF of 'n JPEG, of bitmap, of 'n ping, 837 00:39:31,930 --> 00:39:34,240 enige grafiese lêer formaat waarmee jy vertroud is, 838 00:39:34,240 --> 00:39:36,460 waarvan sommige ons speel met in PSET4. 839 00:39:36,460 --> 00:39:41,550 Dit lyk nie die moeite werd om te stoor swart pixel, swart pixel, swart pixel, 840 00:39:41,550 --> 00:39:44,790 dot, dot, dot, 'n hele klomp van die swart pixels vir die eerste scanline, 841 00:39:44,790 --> 00:39:47,430 of ry, dan 'n hele klomp van die dieselfde, dan 'n hele klomp 842 00:39:47,430 --> 00:39:49,530 van dieselfde, en dan 'n hele klomp van rooi pixels, 843 00:39:49,530 --> 00:39:53,020 rooi pixels, rooi pixels, dan 'n hele n klomp van die geel pixels, geel, reg? 844 00:39:53,020 --> 00:39:55,050 >> Daar is hier so ondoeltreffendheid. 845 00:39:55,050 --> 00:39:59,040 Hoe sal jy intuïtief compress die Duitse vlag 846 00:39:59,040 --> 00:40:01,320 As die uitvoering daarvan as 'n lêer? 847 00:40:01,320 --> 00:40:04,940 Soos wat inligting kan ons nie pla stoor op skyf in orde 848 00:40:04,940 --> 00:40:08,040 ons lêergrootte afneem van soos 'n megabyte om 'n kilogreep, iets 849 00:40:08,040 --> 00:40:09,430 kleiner? 850 00:40:09,430 --> 00:40:13,130 Daarin lê die ontslag hier om duidelik te wees? 851 00:40:13,130 --> 00:40:13,880 Wat kan jy doen? 852 00:40:13,880 --> 00:40:14,380 Ja? 853 00:40:14,380 --> 00:40:21,380 854 00:40:21,380 --> 00:40:21,970 Presies. 855 00:40:21,970 --> 00:40:24,550 Hoekom nie eerder as onthou die kleur van elke pixel darn 856 00:40:24,550 --> 00:40:28,200 net soos jy doen in PSET4 met die bitmap lêer formaat, 857 00:40:28,200 --> 00:40:32,060 hoekom doen jy nie net verteenwoordig die linker kolom van pixels, byvoorbeeld 858 00:40:32,060 --> 00:40:35,370 'n klomp van die swart pixels, 'n klomp rooi, en 'n klomp van die geel, 859 00:40:35,370 --> 00:40:39,210 en dan net een of ander manier te enkodeer die idee van herhaling hierdie 100 keer 860 00:40:39,210 --> 00:40:41,020 of herhaal hierdie 1000 keer? 861 00:40:41,020 --> 00:40:43,430 Waar 100 of 1000 is net 'n heelgetal is, sodat jy 862 00:40:43,430 --> 00:40:47,290 kan wegkom met net 'n enkele nommer in plaas van honderde of duisende 863 00:40:47,290 --> 00:40:48,270 van bykomende pixels. 864 00:40:48,270 --> 00:40:50,990 En inderdaad, dit is hoe ons kon die Duitse vlag compress. 865 00:40:50,990 --> 00:40:51,490 En 866 00:40:51,490 --> 00:40:53,470 Nou wat van die Franse vlag? 867 00:40:53,470 --> 00:40:58,930 En 'n bietjie 'n soort van geestelike oefening, wat flag 868 00:40:58,930 --> 00:41:01,040 kan meer op die skyf saamgepers? 869 00:41:01,040 --> 00:41:05,720 Die Duitse vlag of die Franse vlag, as ons daardie benadering? 870 00:41:05,720 --> 00:41:08,490 Die Duitse vlag, want daar is meer horisontale ontslag. 871 00:41:08,490 --> 00:41:12,190 En deur die ontwerp, baie grafiese lêer formate wel werk as scan lyne 872 00:41:12,190 --> 00:41:12,830 horisontaal. 873 00:41:12,830 --> 00:41:14,674 Hulle kan werk vertikaal, net die mensdom 874 00:41:14,674 --> 00:41:17,090 besluit jaar gelede dat ons sal algemeen dink dinge ry 875 00:41:17,090 --> 00:41:18,880 deur ry in plaas van kolom deur kolom. 876 00:41:18,880 --> 00:41:20,820 So inderdaad as jy om te kyk na die lêer 877 00:41:20,820 --> 00:41:24,670 grootte van 'n Duitse vlag en 'n Franse vlag, so lank as wat die resolusie is 878 00:41:24,670 --> 00:41:27,530 dieselfde, dieselfde wydte en hoogte, hierdie een 879 00:41:27,530 --> 00:41:31,580 hier gaan groter, omdat jy moet jouself drie keer herhaal. 880 00:41:31,580 --> 00:41:35,570 Jy het na blou, herhaal spesifiseer jouself, wit, herhaal jouself, rooi, 881 00:41:35,570 --> 00:41:36,740 herhaal jouself. 882 00:41:36,740 --> 00:41:39,000 Jy kan nie net almal gaan die pad na regs. 883 00:41:39,000 --> 00:41:41,200 En as 'n eenkant, maak duidelik die kompressie 884 00:41:41,200 --> 00:41:43,910 is oral, indien dit vier rame van 'n video-- jy 885 00:41:43,910 --> 00:41:45,890 sal onthou dat 'n fliek of video is oor die algemeen 886 00:41:45,890 --> 00:41:47,286 soos 29 of 30 rame per sekonde. 887 00:41:47,286 --> 00:41:50,410 Dit is soos 'n klein flip boek waar jy beeld, beeld, beeld, beeld te sien net, 888 00:41:50,410 --> 00:41:54,410 beeld super vinnig, sodat dit lyk net soos die akteurs op die skerm beweeg. 889 00:41:54,410 --> 00:41:57,130 Hier is 'n hommel op top van 'n klomp van die blomme. 890 00:41:57,130 --> 00:41:59,790 En al is dit dalk soort wees moeilik om te sien met die eerste oogopslag, 891 00:41:59,790 --> 00:42:04,020 die enigste ding wat beweeg in hierdie film is die bye. 892 00:42:04,020 --> 00:42:06,880 >> Wat is stom oor die stoor video ongecomprimeerd? 893 00:42:06,880 --> 00:42:11,420 Dit is soort van 'n vermorsing om video te stoor as vier byna identies beelde wat 894 00:42:11,420 --> 00:42:13,670 verskil net sover waar die bye is. 895 00:42:13,670 --> 00:42:16,280 Jy kan weggooi mees van daardie inligting 896 00:42:16,280 --> 00:42:20,190 en onthou net, byvoorbeeld, die eerste raam en die laaste raam, 897 00:42:20,190 --> 00:42:22,180 sleutel rame as jy het ooit gehoor die woord, 898 00:42:22,180 --> 00:42:24,337 en net in die stoor middel waar die bye is. 899 00:42:24,337 --> 00:42:26,170 En jy hoef nie te stoor al die pienk, 900 00:42:26,170 --> 00:42:28,330 en die blou, en die groen waardes as well. 901 00:42:28,330 --> 00:42:31,200 So dit is net sê dat kompressie is oral. 902 00:42:31,200 --> 00:42:34,900 Dit is 'n tegniek wat ons gebruik dikwels of as vanselfsprekend aanvaar hierdie dae. 903 00:42:34,900 --> 00:42:38,750 >> Maar hoe weet jy teks compress? 904 00:42:38,750 --> 00:42:40,450 Hoe gaan jy oor die teks comprimeren? 905 00:42:40,450 --> 00:42:45,410 Wel, elkeen van die karakters in Ascii is een byte, of agt stukkies. 906 00:42:45,410 --> 00:42:47,360 En dit is soort van dom, reg? 907 00:42:47,360 --> 00:42:51,160 Omdat jy waarskynlik tik A en E en ek en O en U 'n baie 908 00:42:51,160 --> 00:42:55,270 meer dikwels as soos W of V of Z, afhangende van die taal waarin 909 00:42:55,270 --> 00:42:56,610 jy beslis skryf. 910 00:42:56,610 --> 00:42:59,600 En so hoekom gebruik ons agt bisse vir elke brief 911 00:42:59,600 --> 00:43:02,040 insluitend die minste gewilde letters, reg? 912 00:43:02,040 --> 00:43:05,300 Hoekom nie minder stukkies vir gebruik die super gewilde briewe, 913 00:43:05,300 --> 00:43:07,760 soos E, die dinge wat jy dink eerste in Wheel of Fortune, 914 00:43:07,760 --> 00:43:10,450 en gebruik meer stukkies vir die minder gewilde letters? 915 00:43:10,450 --> 00:43:10,950 Hoekom? 916 00:43:10,950 --> 00:43:13,130 Omdat ons net gaan om gebruik dit minder gereeld. 917 00:43:13,130 --> 00:43:15,838 >> Wel, dit blyk dat daar nie was pogings aangewend om dit te doen. 918 00:43:15,838 --> 00:43:18,630 En as jy onthou van graad skool of die hoërskool, Morsekode. 919 00:43:18,630 --> 00:43:20,400 Morsekode het kolle en strepies wat kan wees 920 00:43:20,400 --> 00:43:24,270 oorgedra langs 'n draad soos klink of seine van 'n soort. 921 00:43:24,270 --> 00:43:25,930 Maar Morsekode is 'n super skoon te maak. 922 00:43:25,930 --> 00:43:29,010 Dit is soort van 'n binêre stelsel in dat jy kolle of koppeltekens. 923 00:43:29,010 --> 00:43:30,977 Maar as jy sien, byvoorbeeld, twee kolle. 924 00:43:30,977 --> 00:43:33,810 Of as jy dink terug aan die operateur wat gaan soos beep, beep, beep, 925 00:43:33,810 --> 00:43:36,760 beep, slaan 'n bietjie sneller wat stuur 'n sein, 926 00:43:36,760 --> 00:43:40,360 as jy die ontvanger, ontvang twee kolletjies, watter boodskap het jy gekry? 927 00:43:40,360 --> 00:43:43,490 Heeltemal arbitrêre. 928 00:43:43,490 --> 00:43:44,450 >> Ek? 929 00:43:44,450 --> 00:43:45,060 Ek? 930 00:43:45,060 --> 00:43:47,500 Of wat about-- of ek? 931 00:43:47,500 --> 00:43:49,570 Miskien was dit net twee regte E se? 932 00:43:49,570 --> 00:43:52,480 So daar is hierdie probleem van decodability met Morse 933 00:43:52,480 --> 00:43:54,890 kode, waardeur tensy die persoon stuur jou boodskap 934 00:43:54,890 --> 00:43:59,510 eintlik pouses sodat jy kan soort van sien of hoor die gapings tussen letters, 935 00:43:59,510 --> 00:44:02,990 dit is nie voldoende om net stuur 'n stroom van nulle en ene, 936 00:44:02,990 --> 00:44:05,610 of kolletjies en strepies, want daar is onduidelikheid. 937 00:44:05,610 --> 00:44:08,640 E is 'n enkele dot, so as jy sien twee kolle of hoor twee punte, 938 00:44:08,640 --> 00:44:11,254 miskien is dit twee E's of miskien is dit een I. 939 00:44:11,254 --> 00:44:13,670 Sodat ons 'n stelsel wat is 'n moet bietjie meer slim as dit. 940 00:44:13,670 --> 00:44:16,851 So 'n man met die naam Huffman jaar gelede het met presies hierdie. 941 00:44:16,851 --> 00:44:18,600 So ons is maar net gaan om 'n vinnige blik te neem 942 00:44:18,600 --> 00:44:20,114 hoe bome is related hierdie. 943 00:44:20,114 --> 00:44:22,530 Veronderstel dat dit 'n paar stupid boodskap wat jy wil stuur, 944 00:44:22,530 --> 00:44:26,342 saamgestel uit net A, B, C se D's en E se maar daar is 'n baie ontslag hier. 945 00:44:26,342 --> 00:44:27,550 Dit is nie bedoel om Engels. 946 00:44:27,550 --> 00:44:28,341 Dit is nie geïnkripteer. 947 00:44:28,341 --> 00:44:30,540 Dis net 'n dom boodskap met baie van die herhaling. 948 00:44:30,540 --> 00:44:34,010 So as jy eintlik tel al die A se B se C se D's, en E se, hier is 949 00:44:34,010 --> 00:44:34,890 die frekwensie. 950 00:44:34,890 --> 00:44:37,800 20% van die briewe is A se 45% van die letters 951 00:44:37,800 --> 00:44:39,660 is E se en drie ander frekwensies. 952 00:44:39,660 --> 00:44:41,960 Ons getel daar met die hand en net het die wiskunde. 953 00:44:41,960 --> 00:44:44,579 >> So dit blyk dat Huffman, 'n geruime tyd gelede, 954 00:44:44,579 --> 00:44:46,620 besef dat, jy weet wat, as ek begin bou 955 00:44:46,620 --> 00:44:51,172 'n boom, of bos bome, as jy wil, soos volg, kan ek die volgende doen. 956 00:44:51,172 --> 00:44:53,880 Ek gaan 'n knoop aan elke gee van die briewe wat ek omgee 957 00:44:53,880 --> 00:44:55,530 en ek gaan om te slaan binnekant van die node 958 00:44:55,530 --> 00:44:58,610 die frekwensies as 'n drywende punt waarde, of jy kan dit gebruik om 'n N ook 959 00:44:58,610 --> 00:45:00,210 maar ons sal net gebruik hier 'n float. 960 00:45:00,210 --> 00:45:03,100 En die algoritme wat hy voorgestel is dat jy 961 00:45:03,100 --> 00:45:07,210 neem hierdie bos enkele node bome, so super kort bome, 962 00:45:07,210 --> 00:45:11,920 en jy begin hulle verbind met nuwe groepe, nuwe ouers, as jy wil. 963 00:45:11,920 --> 00:45:16,150 En jy dit doen deur die keuse van die twee kleinste frekwensies op 'n tyd. 964 00:45:16,150 --> 00:45:18,110 So ek het 10% en 10%. 965 00:45:18,110 --> 00:45:19,090 Ek skep 'n nuwe knoop. 966 00:45:19,090 --> 00:45:20,910 En ek noem die nuwe node 20%. 967 00:45:20,910 --> 00:45:22,750 >> Watter twee nodes Ek kombineer volgende? 968 00:45:22,750 --> 00:45:23,810 Dit is 'n bietjie dubbelsinnig. 969 00:45:23,810 --> 00:45:26,643 So is daar 'n paar hoek gevalle oorweeg nie, maar om dinge mooi te hou, 970 00:45:26,643 --> 00:45:29,300 Ek gaan om te kies 20% - Ek ignoreer nou die kinders. 971 00:45:29,300 --> 00:45:33,640 Ek gaan om te kies 20% en 15% en trek twee nuwe kante. 972 00:45:33,640 --> 00:45:35,624 En nou, wat twee nodes ek logies te kombineer? 973 00:45:35,624 --> 00:45:38,540 Ignoreer al die kinders, al die kleinkinders, kyk net na die wortels 974 00:45:38,540 --> 00:45:39,070 nou. 975 00:45:39,070 --> 00:45:42,220 Watter twee nodes ek saam te bind? 976 00:45:42,220 --> 00:45:44,530 Punt twee en 0,35. 977 00:45:44,530 --> 00:45:45,890 So laat my trek twee nuwe kante. 978 00:45:45,890 --> 00:45:47,570 En dan het ek nog net een gekry linkerkant. 979 00:45:47,570 --> 00:45:48,650 So hier is 'n boom. 980 00:45:48,650 --> 00:45:51,160 En dit is doelbewus getrek om te kyk soort mooi, 981 00:45:51,160 --> 00:45:55,870 maar sien dat die rande het ook gemerk nul en een. 982 00:45:55,870 --> 00:45:59,510 So al die linkerkant kante is nul arbitrêr nie, maar konsekwent. 983 00:45:59,510 --> 00:46:01,170 Al die regte kante is kinders. 984 00:46:01,170 --> 00:46:05,070 >> En so wat Hoffman voorgestelde is, As jy wil 'n B verteenwoordig, 985 00:46:05,070 --> 00:46:10,080 eerder as verteenwoordig die aantal 66 as 'n ASCII wat agt hele stukkies, 986 00:46:10,080 --> 00:46:13,360 jy weet wat, net store die patroon nul, zero, zero, 987 00:46:13,360 --> 00:46:17,030 nul, want dit is die pad uit my boom, mnr Huffman se boom, 988 00:46:17,030 --> 00:46:18,600 die blaar van die wortel. 989 00:46:18,600 --> 00:46:20,970 As jy wil 'n stoor E, daarenteen, het nie 990 00:46:20,970 --> 00:46:26,290 stuur agt stukkies wat 'n E. verteenwoordig In plaas daarvan, stuur Watter patroon van stukkies? 991 00:46:26,290 --> 00:46:26,890 Een. 992 00:46:26,890 --> 00:46:30,410 En wat is lekker oor hierdie is wat E is die gewildste brief 993 00:46:30,410 --> 00:46:32,340 en gebruik jy is die kortste kode vir dit. 994 00:46:32,340 --> 00:46:34,090 Die volgende mees gewilde brief lyk soos dit 995 00:46:34,090 --> 00:46:37,380 was A. En so hoeveel stukkies het hy voor die gebruik vir wat? 996 00:46:37,380 --> 00:46:38,270 Nul, een. 997 00:46:38,270 --> 00:46:41,060 >> En omdat dit geïmplementeer as hierdie boom, vir nou 998 00:46:41,060 --> 00:46:43,350 laat my stipuleer daar geen dubbelsinnigheid as in Morse 999 00:46:43,350 --> 00:46:46,090 kode, want al die letters wat jy omgee 1000 00:46:46,090 --> 00:46:48,780 is aan die einde van hierdie kante. 1001 00:46:48,780 --> 00:46:50,580 Sodat is net een toepassing van 'n boom. 1002 00:46:50,580 --> 00:46:52,538 Dit is-- en ek sal waai my hand op hierdie hoe jy 1003 00:46:52,538 --> 00:46:55,570 kan implementeer as 'n C-struktuur. 1004 00:46:55,570 --> 00:46:58,260 Ons moet net kombineer 'n simbool, soos 'n kar, 1005 00:46:58,260 --> 00:46:59,910 en die frekwensie in links en regs. 1006 00:46:59,910 --> 00:47:02,510 Maar laat ons kyk na twee finale voorbeelde dat jy 1007 00:47:02,510 --> 00:47:06,070 kry baie vertroud is met na quiz nul in die probleem stel vyf. 1008 00:47:06,070 --> 00:47:09,210 >> So is daar die data struktuur bekend as 'n hash tafel. 1009 00:47:09,210 --> 00:47:12,247 En 'n hash tafel is soort van koel in dat dit emmers. 1010 00:47:12,247 --> 00:47:14,830 En veronderstel daar is vier emmers hier, net vier leë spasies. 1011 00:47:14,830 --> 00:47:20,830 Hier is 'n pak kaarte, en hier is klub, graaf, klub, diamante, klub, 1012 00:47:20,830 --> 00:47:25,960 diamante, klub, diamante, clubs-- so dit is die ewekansige. 1013 00:47:25,960 --> 00:47:30,330 Harte, hearts-- so ek is bucketizing al die insette hier. 1014 00:47:30,330 --> 00:47:32,430 En 'n hash tafel behoeftes om te kyk na jou insette, 1015 00:47:32,430 --> 00:47:34,850 en sit dit dan in 'n sekere plaas op grond van wat jy sien. 1016 00:47:34,850 --> 00:47:35,600 Dit is 'n algoritme. 1017 00:47:35,600 --> 00:47:37,980 En Ek gebruik 'n super eenvoudige visuele algoritme. 1018 00:47:37,980 --> 00:47:40,030 Die moeilikste deel van wat was onthou wat die foto's is. 1019 00:47:40,030 --> 00:47:41,590 En dan is daar vier totale dinge. 1020 00:47:41,590 --> 00:47:45,440 >> Nou is die stapels groei, wat is 'n doelbewuste ontwerp ding hier. 1021 00:47:45,440 --> 00:47:46,540 Maar wat anders kan ek doen? 1022 00:47:46,540 --> 00:47:49,080 So eintlik hier het ons 'n n klomp van die ou skool eksamen boeke. 1023 00:47:49,080 --> 00:47:51,240 Veronderstel dat 'n klomp van die studente se name op hier. 1024 00:47:51,240 --> 00:47:52,570 Hier is 'n groter hash tafel. 1025 00:47:52,570 --> 00:47:54,867 In plaas van vier emmers, Ek het, kom ons sê 26. 1026 00:47:54,867 --> 00:47:57,950 En ons het nie wil gaan leen 26 dinge van buite [? Annenberg?], So 1027 00:47:57,950 --> 00:48:00,289 hier is vyf wat verteenwoordig A deur Z. En as ek 1028 00:48:00,289 --> 00:48:03,580 sien 'n student wie se naam begin met A, Ek gaan om sy of haar quiz daar te vestig. 1029 00:48:03,580 --> 00:48:08,850 As iemand begin met C, daar, A-- eintlik nie wil om dit te doen. 1030 00:48:08,850 --> 00:48:10,060 B gaan oor hier. 1031 00:48:10,060 --> 00:48:13,390 So ek het 'n en B en C. En nou hier is nog 'n student. 1032 00:48:13,390 --> 00:48:16,212 Maar as dit hash tafel geïmplementeer met 'n skikking, 1033 00:48:16,212 --> 00:48:17,920 Ek is soort van geskroef op hierdie punt, reg? 1034 00:48:17,920 --> 00:48:19,510 Ek moet soort van om dit iewers sit. 1035 00:48:19,510 --> 00:48:24,380 >> So een manier wat ek kan hierdie los is, al reg, A besig is, is besig om B, C is besig. 1036 00:48:24,380 --> 00:48:28,880 Ek gaan hom in D. sit So by eerste, ek het ewekansige direkte toegang 1037 00:48:28,880 --> 00:48:31,064 aan elk van die emmers vir die studente. 1038 00:48:31,064 --> 00:48:33,230 Maar nou is dit soort van afgewentel in iets lineêre, 1039 00:48:33,230 --> 00:48:36,750 want as ek wil om te soek vir iemand wie se naam begin met A, Ek is so hier. 1040 00:48:36,750 --> 00:48:38,854 Maar as dit nie die A student Ek is op soek na, 1041 00:48:38,854 --> 00:48:41,520 Ek het soort van begin nagaan die emmers, want wat ek gedoen het 1042 00:48:41,520 --> 00:48:44,530 was soort van lineêr ondersoek die data struktuur. 1043 00:48:44,530 --> 00:48:47,710 A stupid manier om te sê net kyk vir die eerste beskikbare opening, 1044 00:48:47,710 --> 00:48:51,850 en sit 'n plan B, om so te praat, of plan D in hierdie geval, die waarde 1045 00:48:51,850 --> 00:48:53,340 in daardie plek plaas. 1046 00:48:53,340 --> 00:48:56,470 Dit is net so dat as jy het het 26 plekke en geen studente 1047 00:48:56,470 --> 00:49:00,600 met die naam Q of Z, of iets soos dat ten minste jy die ruimte. 1048 00:49:00,600 --> 00:49:03,140 >> Maar ons het reeds meer gesien slim oplossings hier, reg? 1049 00:49:03,140 --> 00:49:04,870 Wat sou jy doen in plaas as jy 'n botsing? 1050 00:49:04,870 --> 00:49:06,670 As twee mense het die naam A, wat sou 1051 00:49:06,670 --> 00:49:09,160 het 'n slimmer of meer is intuïtief oplossing as net 1052 00:49:09,160 --> 00:49:12,840 Om 'n waar D is veronderstel om te wees? 1053 00:49:12,840 --> 00:49:14,810 Hoekom het ek nie net gaan buite [? Annenberg?], 1054 00:49:14,810 --> 00:49:19,960 soos malloc, 'n ander node, sit dit hier, en dan sit dat 'n student hier. 1055 00:49:19,960 --> 00:49:22,120 Sodat ek in wese 'n soort van 'n skikking, 1056 00:49:22,120 --> 00:49:25,590 of miskien meer elegant as ons begin om 'n geskakelde lys te sien. 1057 00:49:25,590 --> 00:49:29,520 >> En so 'n gemors tafel is 'n struktuur wat kan kyk net soos hierdie, 1058 00:49:29,520 --> 00:49:33,900 maar meer slim, jy iets genoem aparte aaneenskakeling, waardeur 'n hash tafel 1059 00:49:33,900 --> 00:49:38,340 eenvoudig is 'n skikking, elk van waarvan die elemente is nie 'n nommer, 1060 00:49:38,340 --> 00:49:40,470 is self 'n geskakelde lys. 1061 00:49:40,470 --> 00:49:45,080 Sodat jy super vinnige toegang besluit waar om jou waarde te hash. 1062 00:49:45,080 --> 00:49:48,059 Baie soos met die kaarte byvoorbeeld Ek het super vinnige besluite. 1063 00:49:48,059 --> 00:49:49,600 Harte gaan hier, diamante gaan hier. 1064 00:49:49,600 --> 00:49:52,180 Dieselfde hier, A gaan hier, D gaan hier, B gaan hier. 1065 00:49:52,180 --> 00:49:55,740 So super vinnige blik-ups, en as jy gebeur om te loop in 'n geval 1066 00:49:55,740 --> 00:49:59,429 waar jy het botsings, twee mense met dieselfde naam, goed dan 1067 00:49:59,429 --> 00:50:00,970 jy net begin om saam te koppel. 1068 00:50:00,970 --> 00:50:03,900 En miskien hou hulle gesorteer alfabeties, miskien het jy nie. 1069 00:50:03,900 --> 00:50:05,900 Maar ten minste nou het ons die dinamika. 1070 00:50:05,900 --> 00:50:10,250 So aan die een kant het ons super vinnig konstante tyd, en soort van lineêre tyd 1071 00:50:10,250 --> 00:50:14,110 betrokke as hierdie geskakelde lyste begin 'n bietjie lank om te kry. 1072 00:50:14,110 --> 00:50:16,880 >> So hierdie soort van 'n dom, geeky grap jaar gelede. 1073 00:50:16,880 --> 00:50:19,590 Aan die CS50 hack-a-thon, Wanneer studente so, 1074 00:50:19,590 --> 00:50:22,040 sommige TF of CA elke jaar dink dit is snaaks om te sit 1075 00:50:22,040 --> 00:50:27,772 'n teken soos hierdie, waar dit net beteken dat as jou naam begin met 'n A, 1076 00:50:27,772 --> 00:50:28,870 gaan op hierdie manier. 1077 00:50:28,870 --> 00:50:31,110 As jou naam begin met 'n B, gaan this-- OK, 1078 00:50:31,110 --> 00:50:33,290 dit is snaaks dalk later in die semester. 1079 00:50:33,290 --> 00:50:36,420 Maar daar is 'n ander manier om dit te doen, ook. 1080 00:50:36,420 --> 00:50:37,410 Kom terug na daardie. 1081 00:50:37,410 --> 00:50:38,600 >> So daar is hierdie struktuur. 1082 00:50:38,600 --> 00:50:40,420 En dit is ons laaste struktuur vir vandag, 1083 00:50:40,420 --> 00:50:42,400 dit is iets wat 'n sogenaamde Trie. 1084 00:50:42,400 --> 00:50:47,140 T-R-I-E, wat vir een of ander rede is kort vir herwinning, maar dit is bekend Trie. 1085 00:50:47,140 --> 00:50:51,389 So 'n Trie is nog 'n interessante mengsel van 'n baie van hierdie idees. 1086 00:50:51,389 --> 00:50:52,930 Dit is 'n boom, wat ons voorheen gesien het. 1087 00:50:52,930 --> 00:50:54,180 Dit is nie 'n binêre soek boom. 1088 00:50:54,180 --> 00:50:58,410 Dit is 'n boom met 'n aantal van kinders, maar elkeen van die kinders in 'n Trie 1089 00:50:58,410 --> 00:51:00,090 is 'n skikking. 1090 00:51:00,090 --> 00:51:04,790 'N verskeidenheid van grootte, sê 26 of dalk 27 as jy wil koppelteken name ondersteun 1091 00:51:04,790 --> 00:51:06,790 of apostrofs in mense se name. 1092 00:51:06,790 --> 00:51:08,280 >> En so dit is 'n data-struktuur. 1093 00:51:08,280 --> 00:51:10,290 En as jy kyk van bo na onder, soos as jy 1094 00:51:10,290 --> 00:51:13,710 kyk na die top node daar M, is verwys na die linker ding daar 1095 00:51:13,710 --> 00:51:17,665 wat dan 'n, X, W, E, L, L. Dit is net 'n data struktuur wat arbitrêr 1096 00:51:17,665 --> 00:51:19,120 is die stoor mense se name. 1097 00:51:19,120 --> 00:51:25,720 En Maxwell gestoor deur net volgende 'n pad van skikking om verskeidenheid te skikking. 1098 00:51:25,720 --> 00:51:30,050 Maar wat is ongelooflik om 'n Trie is dat, terwyl 'n geskakelde lys en selfs 1099 00:51:30,050 --> 00:51:34,520 'n skikking, die beste wat ons nog ooit gekry het is lineêre tyd of logaritmiese tyd op soek 1100 00:51:34,520 --> 00:51:35,600 iemand op. 1101 00:51:35,600 --> 00:51:40,530 In hierdie data struktuur van 'n Trie, as my data struktuur het 'n naam in dit 1102 00:51:40,530 --> 00:51:43,720 en ek is op soek na Maxwell, ek is gaan hom redelik vinnig te vind. 1103 00:51:43,720 --> 00:51:47,910 Ek kyk net vir M-A-X-W-E-L-L. As hierdie data struktuur, daarenteen, 1104 00:51:47,910 --> 00:51:51,830 As N is 'n miljoen, as daar 'n miljoen name in hierdie data struktuur, 1105 00:51:51,830 --> 00:51:57,100 Maxwell is nog steeds gaan wees opspoorbar ná net M-A-X-W-E-L-L 1106 00:51:57,100 --> 00:51:58,090 stappe. 1107 00:51:58,090 --> 00:52:01,276 En David-- D-A-V-I-D stappe. 1108 00:52:01,276 --> 00:52:03,400 Met ander woorde, deur die bou 'n datastruktuur wat 1109 00:52:03,400 --> 00:52:07,240 het al hierdie skikkings, wat almal hulself te ondersteun ewetoeganklike, 1110 00:52:07,240 --> 00:52:11,090 Ek kan begin soek op mense se noem die gebruik van 'n bedrag van die tyd wat 1111 00:52:11,090 --> 00:52:14,340 eweredig aan die aantal nie van die dinge in die data struktuur, 1112 00:52:14,340 --> 00:52:16,330 soos 'n miljoen bestaande name. 1113 00:52:16,330 --> 00:52:20,135 Die bedrag van die tyd wat dit neem om my te vind M-A-X-W-E-L-L in hierdie data struktuur is 1114 00:52:20,135 --> 00:52:22,260 proporsionele nie die grootte van die data struktuur, 1115 00:52:22,260 --> 00:52:25,930 maar om die lengte van die naam. 1116 00:52:25,930 --> 00:52:28,440 En realisties die name wat ons soek up 1117 00:52:28,440 --> 00:52:29,970 gaan nooit lank mal wees. 1118 00:52:29,970 --> 00:52:32,600 Miskien is iemand het 'n 10 karakter noem, 20 naam karakter. 1119 00:52:32,600 --> 00:52:33,900 Dit is beslis eindige, reg? 1120 00:52:33,900 --> 00:52:37,110 Daar is 'n mens op aarde wat het die langste moontlike naam 1121 00:52:37,110 --> 00:52:39,920 maar dat die naam is 'n konstante waarde lengte, reg? 1122 00:52:39,920 --> 00:52:41,980 Dit maak nie verskil in enige sin nie. 1123 00:52:41,980 --> 00:52:45,090 So op hierdie manier, ons het bereik 'n datastruktuur 1124 00:52:45,090 --> 00:52:47,800 wat konstant tyd look-up. 1125 00:52:47,800 --> 00:52:50,670 Dit neem 'n aantal stappe afhangende van die lengte van die insette, 1126 00:52:50,670 --> 00:52:54,250 maar nie die aantal naam in die data struktuur. 1127 00:52:54,250 --> 00:52:58,700 So as ons dubbel die getal name volgende jaar van 'n miljard tot twee miljard, 1128 00:52:58,700 --> 00:53:03,720 bevinding Maxwell gaan neem presies dieselfde aantal sewe stappe 1129 00:53:03,720 --> 00:53:04,650 om hom te vind. 1130 00:53:04,650 --> 00:53:08,810 En so het ons lyk bereik ons heilige graal van die bestuur van die tyd. 1131 00:53:08,810 --> 00:53:10,860 >> So 'n paar vinnige aankondigings. 1132 00:53:10,860 --> 00:53:11,850 Quiz nul kom. 1133 00:53:11,850 --> 00:53:14,600 Meer oor wat op die webwerf die kursus se oor die volgende paar dae. 1134 00:53:14,600 --> 00:53:17,120 Maandag se lecture-- dit is 'n vakansie hier by Harvard op Maandag. 1135 00:53:17,120 --> 00:53:18,850 Dit is nie in New Haven, so ons is die neem van die klas 1136 00:53:18,850 --> 00:53:20,310 New Haven vir lesing op Maandag. 1137 00:53:20,310 --> 00:53:22,550 Alles sal verfilm en gestroom live soos gewoonlik, 1138 00:53:22,550 --> 00:53:24,900 maar laat eindig vandag met 'n 30 sekonde clip 1139 00:53:24,900 --> 00:53:26,910 genaamd "Diep gedagtes" deur Daven Farnham, wat 1140 00:53:26,910 --> 00:53:30,850 is geïnspireer verlede jaar deur die Saterdag Night Live se "Diep gedagtes" 1141 00:53:30,850 --> 00:53:35,700 deur Jack Handy, wat moet nou sin maak. 1142 00:53:35,700 --> 00:53:38,810 >> Film: En nou, "Diep Gedagtes "deur Daven Farnham. 1143 00:53:38,810 --> 00:53:42,100 1144 00:53:42,100 --> 00:53:42,870 Hash tafel. 1145 00:53:42,870 --> 00:53:45,940 1146 00:53:45,940 --> 00:53:47,660 >> Spreker 1: Alle reg, dit is dit vir nou. 1147 00:53:47,660 --> 00:53:48,805 Ons sal sien dat jy volgende week. 1148 00:53:48,805 --> 00:53:55,380 1149 00:53:55,380 --> 00:53:56,680 >> DOUG: Om dit te sien in aksie. 1150 00:53:56,680 --> 00:53:58,304 So laat ons neem 'n blik op wat nou. 1151 00:53:58,304 --> 00:53:59,890 So hier het ons 'n ongesorteerde skikking. 1152 00:53:59,890 --> 00:54:04,860 >> IAN: Doug, kan jy gaan voort en herlaai hierdie vir net een sekonde, asseblief. 1153 00:54:04,860 --> 00:54:08,562 Alle reg, is kameras rol, so aksie wanneer jy gereed is, Doug is, OK? 1154 00:54:08,562 --> 00:54:11,020 DOUG: Alle reg, sodat dit wat ons hier is 'n ongesorteerde skikking. 1155 00:54:11,020 --> 00:54:13,960 En ek het al die elemente gekleurde rooi om aan te dui dat dit, in werklikheid, 1156 00:54:13,960 --> 00:54:14,460 ongesorteerde. 1157 00:54:14,460 --> 00:54:17,960 So onthou dat die eerste ding wat ons doen is ons sorteer die linker helfte van die skikking. 1158 00:54:17,960 --> 00:54:20,630 Dan sorteer ons die reg helfte van die skikking. 1159 00:54:20,630 --> 00:54:22,830 En ya-da, ya-da, ya-da, ons hulle saam te smelt. 1160 00:54:22,830 --> 00:54:24,520 En ons het 'n heeltemal gesorteerde skikking. 1161 00:54:24,520 --> 00:54:25,360 So dit is hoe saamsmelt soort werk. 1162 00:54:25,360 --> 00:54:27,109 >> IAN: Whoa, whoa, whoa, sny, sny, sny, sny. 1163 00:54:27,109 --> 00:54:30,130 Doug, kan jy nie net ya-da, ya-da, ya-da, jou pad deur merge soort. 1164 00:54:30,130 --> 00:54:31,970 >> DOUG: Ek net gedoen het. 1165 00:54:31,970 --> 00:54:32,832 Dis reg. 1166 00:54:32,832 --> 00:54:33,540 Ons is goed om te gaan. 1167 00:54:33,540 --> 00:54:34,760 Kom ons hou rollende. 1168 00:54:34,760 --> 00:54:35,380 So in elk geval, 1169 00:54:35,380 --> 00:54:37,800 >> IAN: Jy het om te verduidelik dit meer volledig as dit. 1170 00:54:37,800 --> 00:54:39,999 Dit is net nie genoeg nie. 1171 00:54:39,999 --> 00:54:41,790 DOUG: Ian, ons doen nie nodig het om terug te gaan na een. 1172 00:54:41,790 --> 00:54:42,350 Dis reg. 1173 00:54:42,350 --> 00:54:45,690 So in elk geval, as ons voortgaan met merge-- Ian, ons is in die middel van die verfilming. 1174 00:54:45,690 --> 00:54:46,612 >> IAN: Ek weet. 1175 00:54:46,612 --> 00:54:49,320 En ons kan nie net ya-da, ya-da, ya-da, deur die hele proses. 1176 00:54:49,320 --> 00:54:52,200 Jy het om te verduidelik hoe die twee kante bymekaar te kry saamgesmelt. 1177 00:54:52,200 --> 00:54:53,570 >> DOUG: Maar ons het reeds verduidelik hoe die twee sides-- 1178 00:54:53,570 --> 00:54:55,321 >> IAN: Jy het net gewys hulle 'n merge skikking. 1179 00:54:55,321 --> 00:54:56,486 DOUG: Hulle weet die proses. 1180 00:54:56,486 --> 00:54:57,172 Hulle is fine. 1181 00:54:57,172 --> 00:54:58,380 Ons het meer as dit tien keer weg. 1182 00:54:58,380 --> 00:55:00,330 >> IAN: Jy oorgeslaan net reg oor. 1183 00:55:00,330 --> 00:55:03,360 Ons gaan terug na een, het jy Kan jy nie ya-da, ya-da oor. 1184 00:55:03,360 --> 00:55:05,480 Alle reg, terug na die een. 1185 00:55:05,480 --> 00:55:07,833 >> DOUG: Ek het om terug te gaan deur al die skyfies? 1186 00:55:07,833 --> 00:55:08,332 My God. 1187 00:55:08,332 --> 00:55:11,008 1188 00:55:11,008 --> 00:55:13,004 Dit is soos die sesde keer, Ian. 1189 00:55:13,004 --> 00:55:13,940 Dis reg. 1190 00:55:13,940 --> 00:55:15,200 >> IAN: Alle reg. 1191 00:55:15,200 --> 00:55:16,590 Jy gereed? 1192 00:55:16,590 --> 00:55:17,400 Groot. 1193 00:55:17,400 --> 00:55:18,950 Aksie.