Spreker 1: Alle reg, sodat dit is CS50 Dit is die einde van die week vyf. En onthou dat laaste keer dat ons begin kyk na die liefhebber data strukture wat begin het om op te los probleme, wat begin het om in te voer nuwe probleme, maar die sleutel tot hierdie was die soort threading dat ons begin om te doen van knoop tot knoop. So dit is natuurlik 'n enkel geskakelde lys. En een-een gekoppel is, Ek bedoel, daar is net een ryg tussen elk van die nodes. Blyk jy kan doen liefhebber dinge soos dubbel geskakelde lyste waardeur jy 'n pyl gaan in albei rigtings, wat kan help met sekere doeltreffendheid. Maar dit het die probleem opgelos? Watter probleem het dit op te los? Hoekom het ons omgee op Maandag? Hoekom, in teorie, het ons omgee op Maandag? Wat doen dit? 

GEHOOR: Ons kan dinamiese grootte daarvan. 

Spreker 1: OK, so ons kan dinamiese grootte daarvan. Welgedaan beide van julle. Sodat jy kan dinamiese hierdie grootte data struktuur, terwyl 'n skikking, Onthou, jy het 'n ken priori hoeveel ruimte wat jy wil en as jy 'n bietjie meer nodig ruimte, jy is soort van uit van geluk. Jy het 'n hele nuwe reeks te skep. Jy het om al beweeg jou data van die een na die ander, uiteindelik bevry die ou array as jy kan, en dan voort te gaan. Wat voel net baie duur en baie ondoeltreffende, en inderdaad is dit kan wees. Maar dit is nie al die goeie. Ons betaal 'n prys, wat was een van die meer ooglopende pryse wat ons betaal deur die gebruik van 'n geskakelde lys? 

GEHOOR: Ons het om te gebruik dubbel ruimte vir elkeen. Spreker 1: Ja, so ons moet ten minste twee keer soveel ruimte. In werklikheid, het ek besef hierdie prentjie selfs 'n bietjie misleidend, want op CS50 IO in 'n baie moderne rekenaars, 'n wyser of 'n adres is nie in die feit dat vier grepe. Dit is baie dikwels hierdie dae agt grepe, wat beteken die onderkant mees reghoeke daar in werklikheid is soort van twee keer groot soos wat ek getrek, wat beteken jy gebruik drie keer veel ruimte soos ons anders kan hê. Nou op dieselfde tyd, ons is nog praat grepe, reg? Ons is nie noodwendig praat megagrepe of gigagrepe, tensy dit datastrukture kry groot. 

En so vandag het ons begin om te oorweeg hoe ons data kan verken meer doeltreffend as in die feit dat die data kry groter. Maar laat ons probeer om canonicalize die bedrywighede eerste wat jy kan doen op hierdie soorte data strukture. So iets soos 'n gekoppelde lys die algemeen ondersteun bedrywighede wil verwyder, voeg, en soek. En wat doen ek daarmee? Dit beteken net dat gewoonlik, as mense is met behulp van geskakelde lys, hulle of iemand anders geïmplementeer funksies soos verwyder, vul, en soek, sodat jy kan iets werklik doen nuttige met die data-struktuur. So laat ons neem 'n vinnige blik hoe ons kan implementeer sommige kode vir 'n geskakelde lys soos volg. 

So dit is net 'n paar C-kode, nie eens 'n volledige program dat ek regtig vinnig opgesweep. Dit is nie in die verspreiding aanlyn kode, want dit sal nie eintlik loop. Maar let ek het nou net met 'n comment gesê dot dot dot, daar is iets daar dot dot dot, iets daar. En laat ons net kyk na wat die sappige dele is. So op die lyn drie, onthou dat dit is nou Ons het voorgestel waarby 'n node laaste tyd, een van daardie vierkantige voorwerpe. Dit het 'n int dat ons N bel, maar ons kan dit enigiets noem, en dan 'n sogenaamde struct node ster langs. En net om duidelik te wees, dat die tweede lyn, op die lyn ses, wat gaan dit? Wat is dit vir ons doen? Want dit lyk beslis meer kriptiese as ons gewone veranderlikes. 

GEHOOR: Dit maak dit beweeg oor een. 

Spreker 1: Dit maak dit beweeg oor een. En om meer presies te wees, sal dit die adres stoor van die node wat bedoel is om te wees semanties langs dit, reg? So dit is nie van plan om noodwendig beweeg nie. Dit is net gaan om te stoor 'n waarde wat gaan na die adres van 'n paar ander knoop, en dit is hoekom ons het gesê struct node ster, die ster wat aandui 'n wyser of 'n adres. OK, so nou as jy aanvaar dat ons hierdie N tot ons beskikking, en laat aanvaar dat iemand anders ingevoeg n hele klomp van heelgetalle in 'n geskakelde lys. En dat gekoppel lys is wys na 'n sekere punt deur 'n veranderlike genaamd lys wat geslaag hier as 'n parameter, hoe gaan ek te werk lyn 14 search implementering? Met ander woorde, as ek die implementering funksie waarvan die doel in die lewe is om 'n int en dan die neem begin van 'n geskakelde lys, dit is 'n verwysing na die geskakelde lys. Soos die eerste, wat ek dink David was ons vrywilligers op Maandag, hy wys op die hele gekoppel lys dit is asof ons verby David in as ons argument hier. Hoe gaan ons te werk dwars hierdie lys? Wel, dit blyk dat selfs al pointers is nou relatief nuut vir ons, Ons kan dit doen relatief reguit. 

Ek gaan om voort te gaan en verklaar 'n tydelike veranderlike wat deur konvensie is net gaan wyser genoem te word, of PTR, maar jy kan dit iets wat jy wil bel. En ek gaan inisialiseer dit aan die begin van die lys. Sodat jy kan soort van dink van hierdie as my die onderwyser die ander dag, soort wat dui op iemand onder ons mense as vrywilligers. So ek is 'n tydelike veranderlike wat net wys op die dieselfde ding dat ons toevallig vernoem vrywilliger David is ook uit te wys. En terwyl wyser is nie null, want onthou dat null is 'n paar spesiale brandwag waarde die afbaken die einde van die lys, Dus, terwyl ek nie wys op die grond soos ons laaste vrywilliger was, laat ons gaan voort en doen die volgende. As pointer-- en nou kan ek soort van wil om te doen wat ons gedoen het met die student structure-- as wyser dot volgende equals-- eerder as wyser dot N gelyk gelyk aan die veranderlike N, die argument wat alreeds geslaag in, dan wil ek om voort te gaan en sê terugkeer waar. Ek het die aantal N binnekant van gevind een van die nodusse van my geskakelde lys. Maar die dot nie meer werk in hierdie konteks, omdat pointer, PTR, is inderdaad 'n wyser, 'n adres, Ons kan eintlik wonderlik gebruik uiteindelik 'n stukkie van die sintaksis dat soort maak intuïtief sin en eintlik gebruik 'n pyl hier, wat beteken gaan van dat adres aan die heelgetal daar in. So dit is baie soortgelyk in gees om die dot-operateur, maar omdat wyser is nie 'n wyser en nie 'n werklike struct self, ons gebruik net die pyl. 

So as die huidige node dat ek, die tydelike veranderlike, is wys op is nie N, wat wil ek doen? Wel, met my menslike vrywilligers dat ons hier gehad het die ander dag, as my eerste mens is nie die een wat ek wil, en miskien die tweede mens is nie die een wat ek wil hê, en die derde, ek nodig om fisies bly beweeg. Soos hoe ek stap vir stap deur 'n lys? Wanneer ons het 'n verskeidenheid jou, net gedoen soos ek plus plus. Maar in hierdie geval, is dit voldoende om doen pointer, kry, pointer, die volgende. Met ander woorde, die volgende veld is soos al die linkerkant hande dat ons menslike vrywilligers op Maandag was die gebruik om te wys op 'n ander knoop. Dit was hul volgende bure. 

So as ek wil om te stap deur hierdie lys, Ek kan nie net doen ek plus plus meer, Ek het om te sê in plaas Ek, pointer, gaan om gelyk ongeag die volgende veld is, die volgende veld, die volgende veld is, volgende al daardie gelaat hande wat ons gehad het op die verhoog wys sommige daaropvolgende waardes. En as ek kry deur dat die hele iterasie, en uiteindelik, ek getref null nie met gevind N nog, ek het net terug onwaar. So weer, alles wat ons hier doen, soos per die prentjie 'n oomblik gelede begin deur te wys op die begin van die lys vermoedelik. En dan het ek seker te maak, is die waarde Ek soek gelyk aan nege? As dit so is, het ek terug waar en ek is gedaan. Indien nie, ek my hand te werk, AKA pointer, om te wys op die ligging van die volgende pyl se en dan plek die volgende pyl se en die volgende. Ek is net loop deur middel van hierdie skikking. 

So weer, wat omgee? Soos wat hierdie is 'n bestanddeel vir? Wel, onthou dat ons ' die idee van 'n stapel, wat is 'n abstrakte data tik sover dit nie 'n C ding, dit is nie 'n ding CS50, dit is 'n abstrakte idee, hierdie idee van stapel dinge op die top van mekaar dat geïmplementeer kan word trosse van verskillende maniere. En een manier waarop ons voorgestelde was met 'n skikking, of met 'n geskakelde lys. En dit blyk dat kerkwetlik, 'n stapel ondersteun ten minste twee operasies. En die buzz woorde is druk om stoot iets op die stapel, soos 'n nuwe skinkbord in die eetsaal, of pop, wat beteken dat die boonste verwyder skinkbord uit die stapel in die eetkamer saal, en dan miskien 'n paar ander bedrywighede asook. So hoe kan ons die struktuur definieer dat ons nou 'n beroep 'n stapel? 

Wel, ons het al die nodige sintaksis tot ons beskikking in C. Ek sê, gee my 'n tipe definisie van 'n struct binnekant van 'n stapel, Ek gaan om te sê, is 'n skikking, van 'n hele klomp van die nommers en dan grootte. So met ander woorde, as ek wil om dit te implementeer in die kode, laat my gaan en net soort van teken wat dit sê. So dit sê, gee my 'n struktuur wat is het 'n skikking, en ek weet nie wat kapasiteit is, dit is blykbaar 'n paar konstante wat ek elders gedefinieer, en dit is goed. Maar dink dit is net een, twee, drie, vier, vyf. So kapasiteit is 5. Hierdie element binnekant van my struktuur sal genoem getalle. En dan moet ek een ander veranderlike blykbaar genoem grootte wat aanvanklik ek gaan om te stipuleer geïnisialiseer aan nul. As daar is niks in die stapel, grootte nul is, en dit is vullis waardes in getalle. Ek het geen idee wat is daar net nog nie. 

So as ek wil om te stoot iets op die stapel, dink ek noem die funksie stoot, en Ek sê stoot 50, soos die nommer 50, waar sou jy voorstel Ek teken dit in hierdie reeks? Daar is vyf verskillende moontlike antwoorde. Waar wil jy die nommer 50 stoot? As die doel hier, weer, roep die funksie stoot, slaag in 'n argument 50, waar kan ek dit? Vyf possible-- 20% kans om reg te raai. Ja? 

GEHOOR: heel regs. 

Spreker 1: heel regs. Daar is nou 'n 25% kans om reg te raai. So wat eintlik sou goed wees. Deur konvensie, sal ek sê met 'n skikking, sou ons oor die algemeen begin aan die linkerkant, maar ons kon beslis begin op die regte. So die verwoester hier sou wees ek is waarskynlik gaan om dit te trek aan die linkerkant, net soos in 'n normale verskeidenheid waar Ek begin gaan links na regs. Maar as jy kan flip die rekenkundige, fyn. Dit is net nie konvensionele. OK, ek moet een te maak meer verandering though. Nou dat ek iets het gestoot op die stapel, wat is volgende? 

Alle reg, ek het die grootte inkrementeer. So laat my gaan voort en net werk hierdie, wat nul was. En in plaas daarvan nou, ek gaan in die waarde een te sit. En nou dink ek 'n ander stoot nommer op die stapel, soos 51. Wel, ek het nog een te maak verandering, wat tot die grootte twee. En dan dink ek stoot een nommer op die stapel soos 61, ek moet nou aan die grootte werk een tyd, en kry die waarde 3 as die grootte. En nou dink ek noem pop. Nou pop, deur konvensie, nie 'n argument te neem. Met 'n stapel, die hele punt van die metafoor skinkbord is dat jy nie het diskresie om te gaan kry wat skinkbord, kan alles wat jy doen is pop die boonste een van die stapel, net omdat. Dit is wat hierdie data struktuur nie. 

So deur daardie logika as ek sê pop, wat kom nie? So 61. So, wat is regtig die rekenaar gaan doen in die geheue? Wat beteken my kode hoef te doen? Wat sou jy voorstel ons verander op die skerm? Wat moet verander? Jammer? So kry ons ontslae te raak van 61. So kan ek beslis dit doen. En ek kan ontslae te raak van 61. En dan wat ander verandering moet gebeur? Grootte waarskynlik om terug te gaan na twee. En so is dit goed. Maar wag 'n minuut, grootte 'n oomblik gelede was drie. Laat ons net 'n vinnige gesonde verstand tjek. Hoe het ons weet dat ons wou ontslae raak van 61? Omdat ons knal. En so ek het hierdie tweede eiendom grootte. 

Wag 'n minuut, ek is dink terug na week twee wanneer ons begin praat oor skikkings, waar dit was ligging nul, dit was een plek, dit was ligging twee, dit is plek drie, vier, dit lyk soos die verhouding tussen die grootte en die element wat ek wil om te verwyder van die skikking verskyn net wat? Grootte minus een. En so dit is hoe die mens as ons weet 61 kom eerste. Hoe gaan die rekenaar gaan om te weet? Wanneer jou kode, waar jy waarskynlik wil grootte minus een te doen, so drie minus een is twee, en dat beteken dat ons wil ontslae te raak van 61. En dan kan ons inderdaad werk die grootte, sodat die grootte nou gaan van drie tot net twee. En net om pedanties wees, ek gaan voor te stel dat ek gedoen het, reg? Jy voorgestelde intuïtief korrek moet ek ontslae raak van 61. Maar hy het nie ek soort van soort van ontslae geraak 61? Ek het effektief vergeet dat dit eintlik daar is. En dink terug aan PSET4, as jy gelees het die artikel oor forensiese, die PDF wat ons gehad het julle ouens te lees, of jy sal hierdie week lees PSET4. Onthou dat dit is eintlik related aan Die hele idee van die rekenaar forensiese. Wat 'n rekenaar doen, is oor die algemeen is dit net vergeet waar iets is, maar dit gaan nie in en soos probeer om dit uit of ignoreer krap daardie stukkies met nulle en ene of 'n ander ewekansige patroon tensy jy jouself doen doelbewus. So jou intuïsie was reg, laat ons ontslae te raak van 61. Maar in werklikheid is, het ons nie te pla. Ons moet net om te vergeet dat dit is daar deur die verandering van ons grootte. 

Nou is daar 'n probleem met hierdie stapel. As ek hou dinge stoot op die stapel, wat is natuurlik gaan gebeur in net 'n paar oomblikke tyd? Ons gaan uit die ruimte te loop. En wat doen ons? Ons soort geskroef. Hierdie implementering nie laat ons die grootte van die skikking, want die gebruik van hierdie sintaksis, as jy dink terug aan week twee, sodra jy verklaar die grootte van 'n skikking, ons het 'n meganisme nog nie gesien het nie, waar kan jy die grootte van die skikking te verander. En inderdaad C nie dat die funksie. As jy sê gee my vyf Nths, bel hulle getalle, dit is al wat jy gaan om dit te kry. So ons nou doen as Maandag, het die vermoë om 'n oplossing te druk al is, ons moet net aanpas die definisie van ons stapel om 'n paar harde-gekodeerde verskeidenheid nie, maar net om 'n adres te stoor. 

Nou hoekom is dit? Nou moet ons net gemaklik met die feit dat wanneer my program loop, Ek is vermoedelik gaan moet die menslike vra Hoeveel getalle wil jy om te stoor? So die insette het om te kom van iewers. Maar sodra ek weet dat nommer, dan kan ek net gebruik wat funksioneer om te gee vir my 'n stuk van die geheue? Ek kan gebruik malloc. En ek kan enige aantal sê grepe Ek wil terugkom vir hierdie Nths. En alles wat ek het om op te slaan in die getalle veranderlike hier binnekant van hierdie struct wat behoort te wees? Wat eintlik gaan in die getalle in hierdie scenario? Ja, 'n verwysing na die eerste byte van daardie deel van die geheue, of meer spesifiek, die adres van die eerste van die grepe. Maak nie saak of dit 'n byte of 'n miljard grepe, Ek het net nodig om te sorg oor die eerste. Want wat malloc waarborge en my bedryfstelsel waarborge, is dat die stuk van die geheue Ek te kry, gaan dit aangrensende wees. Daar gaan nie gapings wees. So as ek vir 50 gevra het grepe of 1000 grepe, hulle is almal gaan wees rug aan rug aan rug. En so lank as wat ek onthou hoe groot, hoe veel gevra ek, al wat ek nodig het om te weet is die eerste sodanige adres. 

So nou het ons die vermoë om in die kode. Hoewel, dit gaan om ons te neem meer tyd om hierdie te skryf, nou kan ons herschikken dat geheue deur net 'n ander adres stoor daar as ons wil 'n groter of selfs 'n kleiner deel van die geheue. So hier om 'n kompromis. Nou kry ons dinamika. Ons het nog contiguousness ek beweer. Omdat malloc ons sal gee 'n aangrensende stuk van die geheue. Maar dit gaan 'n pyn in wees die nek vir ons, die programmeerder, om werklik die kode up. Dis net meer werk. Ons moet code soortgelyk aan wat ek was gebons net 'n oomblik gelede. Baie uitvoerbaar nie, maar dit voeg kompleksiteit. En so ontwikkelaar tyd programmeerder tyd is nog 'n hulpbron dat ons dalk nodig om te spandeer 'n tyd om nuwe funksies te kry. En dan natuurlik is daar 'n tou. Ons sal nie in hierdie gaan een in veel detail. Maar dit is baie soortgelyk in die gees. Ek kon 'n tou te implementeer, en sy ooreenstemmende bedrywighede, enqueue of dequeue soos by te voeg of te verwyder, dit is net 'n liefhebber manier om te sê nie, enqueue of dequeue, soos volg. Ek kan net gee my 'n struct het weer so array 'n aantal se het weer so 'n grote, maar hoekom moet ek nou nodig om tred te hou van die voorkant van 'n tou te hou? Ek het nie nodig om te weet die voorkant van my stapel. Wel, as ek weer vir 'n queue-- laat ons net hard kodeer dit as 'soos vyf heelgetalle hier potensieel. So, dit is nul, een, twee, drie, vier. Dit gaan wees weer geroep getalle. En dit sal genoem grootte. 

Hoekom is dit nie genoeg nie net grootte het? Wel, laat ons stoot daardie nommers op. So ek pushed-- ek waglys, of gestoot. Nou sal ek enqueue 50, en dan 51, en dan 61, en dot dot dot. So dit is enqueue. Ek waglys 50, dan 51, dan 61. En wat identies lyk om 'n stapel tot dusver, behalwe as ek nodig het om een ​​verandering te maak. Ek het nodig om hierdie grootte te werk, so ek gaan van nul tot een om 02:58 nou. Hoe kan ek dequeue? Wat gebeur met dequeue? Wie moet hierdie lys kom eerste af As dit is die lyn by die Apple Store? So 50. So dit is soort van moeiliker hierdie tyd. AANGESIEN laaste keer was dit super maklik om net te doen grootte minus een, Ek kry aan die einde van my array effektief waar die getalle is, is dit verwyder 61. Maar ek wil nie verwyder 61. Ek wil om te neem 50, wat was daar by 05:00 in lyn vir die nuwe iPhone of iets anders. En so om ontslae te raak van 50, ek kan dit nie net doen nie, reg? Ek kan kruis uit 50. Maar ons het net gesê ons nie so anale te wees as uitkrap of die data te verberg. Ons kan net vergeet waar dit is. 

Maar as ek my grootte te verander nou twee, is dit voldoende inligting om te weet wat aangaan in my tou? Nie regtig nie. Soos my grootte is twee nie, maar waar kom die tou te begin, veral as ek het nog daardie getalle in die geheue. 50, 51, 61. So ek moet onthou nou waar die front is. En so het ek voorgestel up daar is, sal ons net genoem Nde voor, wie se aanvanklike waarde moet wat gewees het nie? Nul, net die begin van die lys. Maar nou in bykomend tot decrementing die grootte, het ons net inkrementeer die voorkant. Nou hier is nog 'n probleem. So wanneer ek hou. Veronderstel dit is die getal van soos 121, 124, en dan, dammit, Ek is uit die ruimte. Maar wag 'n minuut, ek is nie. So op hierdie punt in die verhaal, veronderstel dat die grootte is een, twee, drie, vier, so seker dat die grootte is vier die voorkant is een, so 51 is aan die voorkant. Ek wil nog 'n nommer hier sit, maar dammit, ek is uit die ruimte. Maar ek is nie regtig nie, reg? Waar kan ek 'n paar addisionele waarde soos 171? Ja, ek kon net soort van gaan terug daar, reg? En dan oor die 50, of net oorskryf met 171. En as jy wonder hoekom ons getalle het so random, hierdie is algemeen rekenaar geneem wetenskap kursusse by Harvard na CS50. Maar dit was 'n goeie optimalisering, want nou is ek nie mors ruimte. Ek het nog steeds om te onthou hoe groot hierdie ding is totaal. Dit is vyf totaal. Want ek wil nie begin oorskryf 51. So nou is ek nog steeds uit die ruimte, so dieselfde probleem as voorheen. Maar jy kan sien hoe nou in jou kode, het jy waarskynlik 'n bietjie meer skryf kompleksiteit te maak dat gebeur. En in die feit, wat operateur in C waarskynlik kan jy dit die sirkulariteit mettertyd doen? Ja die modulo operateur, die persentasie teken. So, wat is gaaf oor 'n tou, selfs al hou ons teken skikkings aangesien hierdie soos reguit lyne, as jy soort dink oor dit as kromming rond soos 'n sirkel, dan net intuïtief dit soort van werk verstandelik Ek dink 'n bietjie meer skoon. Jy sal nog moet implementeer dat die geestelike model in die kode. So nie so moeilik, uiteindelik te implementeer, maar ons nog steeds verloor die size-- eerder die vermoë om te verander nie, tensy ons dit doen. 

Ons het om ontslae te raak van die skikking, ons vervang dit met 'n enkele muis, en dan iewers in my kode het ek 'n beroep wat funksioneer om werklik te skep die skikking met die naam getalle? Malloc, of 'n soortgelyke funksie, presies. Enige vrae oor stapels of toue. Ja? Goeie vraag. Wat sou jy modulo hier te gebruik. So algemeen, by die gebruik mod, sou jy dit doen met die grootte van die hele data-struktuur. So iets soos vyf of kapasiteit, as dit is konstant, is waarskynlik betrokke is. Maar net modulo vyf doen waarskynlik nie voldoende is nie, want ons moet weet wat ons doen draai om hier of hier of hier. So is jy waarskynlik ook gaan wil betrek die grootte van die ding, of die voorkant veranderlike as well. So dit is net hierdie relatief eenvoudige rekenkundige uitdrukking, maar modulo sou die sleutel bestanddeel wees. 

So kort film as jy wil. 'N animasie dat sommige mense by 'n ander universiteit saam te stel wat ons het aangepas is vir hierdie bespreking. Dit behels die leer van die Jack feite oor toue en statistieke. 

Film: Eens op 'n tyd, daar was 'n man met die naam Jack. Wanneer dit kom by die maak van vriende, Jack het nie 'n gawe. So Jack het na die praat gewildste man het geweet hy. Hy het na Lou en gevra: Wat moet ek doen? Lou sien dat sy vriend was regtig ontsteld. Wel, het hy begin, net kyk hoe jy geklee is. Het jy nie 'n klere met 'n ander kyk? Ja, sê Jack. Ek seker te doen. Kom na my huis en Ek sal hulle jou wys. So het hulle af te Jack se. En Jack het Lou die boks waar hy het al sy hemde, en sy broek en sy sokkies. Lou het gesê: Ek sien jy het al jou klere in 'n hopie. Hoekom het jy nie dra n paar ander keer in 'n rukkie? 

Jack het gesê, wel, wanneer ek verwyder klere en sokkies, Ek was hulle en sit hulle weg in die boks. Dan kom die volgende oggend, en tot ek hop. Ek gaan na die boks en kry my klere af die top. Lou het gou besef die probleem met Jack. Hy het klere, CD's, en boeke in die stapel. Toe hy bereik vir iets om te lees of om te dra, Hy wil kies om die top boek of onderklere. Toe Hy dan gedoen is, het hy sou sit dit terug. Terug dit sou gaan, op die top van die stapel. Ek weet die oplossing, sê 'n triomfantelike Loud. Jy moet leer om begin met 'n tou. Lou het Jack se klere en hang hulle in die kas. En toe hy leeggemaak die boks, het hy net gooi dit. 

Toe sê hy nou Jack, aan die einde van die dag, sit jou klere aan die linkerkant wanneer jy sit hulle weg. Dan môre oggend wanneer jy sien die sonskyn, kry jou klere op die regte, van die einde van die lyn. Het jy nie sien nie? gesê Lou. Dit sal so lekker wees. Jy sal alles een keer dra voordat jy iets twee keer te dra. En met alles in toue in sy kas en rak, Jack begin om te voel heeltemal seker van homself. Alles te danke aan Lou en sy wonderlike tou. Spreker 1: Alle reg, dit is adorable. So, wat is regtig gaan op onder die kap nou? Dat ons wysers, dat ons malloc, dat ons die vermoë om te skep stukke van die geheue vir onsself dinamiese. So dit is 'n prentjie wat ons bijhorend net die ander dag. Ons het nie regtig woon op dit, maar hierdie foto is aan die gang onder die kap vir weke nou. En sodat hierdie verteenwoordig, net 'n reghoek wat ons het getrek, jou rekenaar se geheue. En miskien jou rekenaar, of CS50 ID, het 'n GB geheue of RAM of twee gigagrepe of vier. Dit maak nie regtig saak nie. Jou bedryfstelsel Windows of Mac OS of Linux, kan in wese jou program om te dink dat dit toegang om die geheel van jou rekenaar se geheue, selfs al is jy kan loop verskeie programme gelyktydig. So in werklikheid, beteken dit nie regtig werk. Maar dit is soort van 'n illusie gegee om al jou programme. So as jy het twee gigs RAM, hierdie is hoe die rekenaar kan dink. 

Nou toevallig een van hierdie dinge, een van hierdie segmente van die geheue, word 'n stapel. En inderdaad enige tyd dusver skriftelik kode dat jy geroep het funksie, byvoorbeeld belangrikste. Onthou dat enige tyd wat ek het se geheue geteken rekenaar, Ek trek altyd soort van helfte van 'n reghoek hier en nie die moeite praat oor wat hierbo. Want as hoof genoem word, ek eis dat u hierdie stukkie van die geheue te kry wat gaan hier neer. En as 'n funksie genoem belangrikste soos swap, goed swap gaan hier. En dit blyk, dit is waar dit eindig. Op iets genoem 'n stapel binnekant van jou rekenaar se geheue. En aan die einde van die dag, dit is net aanspreek. Dit is soos byte nul, byte een byte 2000000000. Maar as jy dink oor dit as hierdie reghoekige voorwerp, al is ons elke doen tyd noem ons 'n funksie is gelaagdheid 'n nuwe deel van die geheue. Ons gee daardie funksie 'n sny van sy eie geheue om mee te werk. 

En onthou nou dat dit is belangrik. Want as ons het nie iets soos swap en twee plaaslike veranderlikes soos A en B en ons daardie waardes van een en twee twee en een, onthou dat wanneer swap terugkom, dit is asof hierdie stukkie geheue is net weg. In werklikheid, dit is nog steeds daar forensies. En iets is eintlik nog steeds daar. Maar konseptueel, dit is so al is dit heeltemal weg. En so hoof nie weet enige van die werk wat gedoen is in daardie swap funksie, tensy dit eintlik in daardie is verby argumente deur wyser of deur verwysing. Nou, die fundamentele oplossing dat die probleem met swap verby dinge in deur adres. Maar dit blyk ook wat is is aan die gang bo wat deel van die reghoek al hierdie tyd is tog is daar daar meer geheue up. En wanneer jy dinamies toeken geheue, of dit nou binne GetString, wat ons het al te doen vir jou in die CS50 biblioteek, of as jy ouens noem malloc en vra die bedryfstelsel vir 'n stuk van geheue, beteken dit nie kom uit die stapel. Dit kom van 'n ander plek in jou rekenaar se geheue Dit is genoem die hoop. En dit is nie 'n verskil. Dit is dieselfde RAM. Dit is dieselfde geheue. Dis net die geheue wat tot daar in plaas van af hier. 

En so wat beteken dit? Wel, as jou rekenaar het 'n eindige hoeveelheid geheue en die stapel grootword, so om te praat, en die hoop, volgens hierdie pyl, groei af. Met ander woorde, elke tyd wat jy malloc noem, jy word gegee 'n sny geheue van bo, dan miskien 'n bietjie laer, dan 'n bietjie laer, elke keer as jy malloc noem, die hoop, dit is gebruik, is 'n soort van groei, groeiende nader en nader aan wat? Die stapel. So het dit lyk soos 'n goeie idee? Ek bedoel, waar dit is nie regtig duidelik Wat anders wat jy kan doen as jy net het 'n beperkte bedrag van die geheue. Maar dit is sekerlik sleg. Dié twee pyle op 'n crash kursus vir mekaar. 

En dit blyk dat slegte ou, mense wat is besonder goed met die ontwikkeling, en probeer om te hack in rekenaars, kan hierdie realiteit te ontgin. In werklikheid, laat ons kyk 'n bietjie brokkie. So, dit is 'n voorbeeld wat jy kan lees oor in meer besonderhede oor Wikipedia. Ons sal jou wys by die artikel as nuuskierig. Maar daar is 'n aanval in die algemeen bekend as buffer oorloop dat bestaan ​​vir so lank as die mens die vermoë om te manipuleer het se rekenaar geheue, veral in C. So, dit is 'n baie arbitrêre program, maar laat ons lees dit van onder af. Main in argC char star argV. So dit is 'n program wat neem command line argumente. En al die vernaamste blykbaar is call 'n funksie, noem dit F vir eenvoud. En dit verby in wat? ArgV een. Dit gaan so in F ookal die woord is dat die gebruiker getik op die instruksielyn na die naam program by. Soveel soos Caesar of Vigenere, wat u sal onthou te doen met argV. 

So, wat is F? F neem in 'n string as sy enigste argument, AKA n kar ster dieselfde ding, as 'n string. En dit is arbitrêr genoem bar in hierdie voorbeeld. En dan char c 12, net in leketaal, wat char c bracket 12 vir ons doen? Wat doen dit? Toekenning geheue, spesifiek 12 grepe vir 12 karakters. Presies. En dan is die laaste linie, roer en kopie, jy het waarskynlik nie gesien nie. Dit is 'n string kopie funksie waarvan die doel in die lewe is om sy tweede argument kopieer in sy eerste argument, maar slegs tot op 'n sekere aantal grepe. So die derde argument sê, hoeveel bytes moet jy kopieer? Die lengte van bar, Wat ook al die gebruiker getik. En die inhoud van Bar, wat string, is in die geheue gekopieer wys na by C. 

So dit lyk soort van dom, en dit is nie. Dit is 'n geforseerde byvoorbeeld maar dit is verteenwoordigend van 'n klas van die aanval vektore, 'n manier van die aanval van 'n program. Alles is goed en goed as die gebruiker tipes in 'n woord wat 11 karakters of minder, plus agteroorskuisstreep nul. Wat as die gebruiker in meer as 11 of 12 of 20 of 50 karakters? Wat is dié program gaan doen? Potensieel seg skuld. Dit gaan blindelings alles bar up kopieer om sy lengte, wat letterlik alles in bar, in die adres daarop by C. Maar C slegs preemptively gegee as 12 grepe. Maar daar is geen bykomende tjek. Daar is geen indien toestande. Daar is geen fout hier te keur. 

En ja, wat die program is gaan doen, is net blindelings kopieer een ding na die ander. En so as ons dit trek as 'n foto, hier is net 'n stukkie van die geheue spasie. So sien aan die onderkant, ons het die plaaslike veranderlike bar. Sodat wyser wat gaan store-- eerder dat plaaslike argument wat gaan na die string bar te stoor. En dan sien net bo dit in 'n stapel, want elke keer as jy vra vir die geheue op die stapel, dit gaan 'n bietjie bo dit picturaal, kennis dat ons daar het 12 grepe. Links bo een is C bracket nul en die onderste regterkantste een is C bracket 11. Dit is net hoe die rekenaars gaan om dit uit te lê. Dus net intuïtief, as bar het meer as 12 karakters in totaal, insluitend agteroorskuisstreep nul, waar is die 12 of die C bracket 12 gaan om te gaan? Of eerder waar is die 12de karakter of die 13de karakter, die honderdste karakter gaan aan die einde in die prentjie? Bo of onder? 

Reg, want selfs al die stapel self groei daarbo, sodra jy dinge gesit het in , is dit vir die ontwerp redes, plaas die geheue van bo tot onder. So as jy het meer as 12 grepe, jy gaan om te begin om bar te vervang. Nou is dit 'n fout nie, maar dit is nie regtig 'n groot deal. Maar dit is 'n groot deal, want daar is meer dinge aan die gang in die geheue. So hier is hoe ons sit hello, duidelik te wees. As ek getik in hallo op die instruksielyn. H-E-L-L-O backslash nul eindig binne diegene 12 grepe, en ons is super veilig. Alles is goed. Maar as ek iets tik langer, dit is potensieel gaan kruip in bar ruimte. Maar erger nog, dit blyk al hierdie tyd, selfs al het ons nog nooit gepraat oor dit is die stapel gebruik word vir ander dinge. Dit is nie net die plaaslike veranderlikes. 

C is 'n baie lae vlak taal. En dit soort van die geheim gebruik die stapel ook om te onthou wanneer 'n funksie genoem word, wat die adres van die vorige funksie, sodat dit kan terug na daardie funksie te spring. So wanneer hoof oproepe te ruil, onder die dinge op die stapel geplaas is nie net swaps plaaslike veranderlikes, of ook die geheim gestoot sy argumente, op die stapel soos verteenwoordig deur hier die rooi sny, is die adres van hoof fisies in jou rekenaar se geheue, sodat wanneer ruil is gedoen, die rekenaar weet wat ek nodig het om terug te gaan na die hoof en eindig uitvoering van die belangrikste funksie. So dit is nou gevaarlik, want as die gebruiker in goed meer as hello, sodanig dat die invoer van die gebruiker se clobbers of oor skryf dat die rooi gedeelte, logies as die rekenaar se net gaan om blindelings aanvaar dat die grepe in daardie rooi skyfie is die adres waarheen dit moet terugkeer, Wat as die teenstander is slim genoeg of gelukkig genoeg om 'n reeks van grepe sit daar wat lyk soos 'n adres, maar dit is die adres van die kode dat hy of sy wil die rekenaar om uit te voer in plaas van die belangrikste? 

Met ander woorde, as wat die gebruiker tik op die instruksielyn, is nie net iets onskadelike soos hello, maar dit is eintlik kode wat is ekwivalent om al die lêers se gebruiker verwyder? Of e-pos hul wagwoord na my toe? Of begin meld hul toetsaanslagen, reg? Daar is 'n manier, laat ons vandag stipuleer, dat hulle kan tik in nie net hallo wêreld of hul naam, hulle kon in wese slaag in die kode, nulle en kinders, wat die rekenaar foute vir beide kode en 'n adres. So hoewel ietwat abstrakte, indien die tipes gebruiker genoeg opponerende kode dat ons hier as jy veralgemeen A. A is aanval of teëstanders. Dus net slegte dinge. Ons gee nie om oor die getalle of die nulle of kinders vandag, soos wat jy beland oorskryf dat die rooi gedeelte, sien dat die volgorde van grepe. O 835 C nul agt nul. En nou as Wikipedia se artikel hier het voorgestel, as jy nou eintlik begin etikettering van die grepe in jou rekenaar se geheue, wat die Wikipedia artikel is stel is dat, wat as die adres van daardie boonste linkerkantste byte is 80 C 0 3508. 

Met ander woorde, as die slegte ou is slim genoeg met sy of haar code om werklik te sit hier 'n getal wat ooreenstem met die adres van die kode hy of sy ingespuit in die rekenaar, het jy kan die rekenaar te mislei in enigiets doen. Die verwydering van lêers, e-pos dinge, snuif jou verkeer, letterlik enigiets kan wees ingespuit word in die rekenaar. En so 'n buffer oorloop aanval op sy kern is net 'n dom, dom oorheersende van 'n skikking wat het nie sy grense nagegaan. En dit is wat is super gevaarlike en terselfdertyd super kragtige in C is dat ons inderdaad toegang tot enige plek in die geheue. Dit is aan ons, die programmeerders, wat die oorspronklike kode te skryf die darn lengte van enige tjek skikkings wat ons manipuleer. So duidelik wees, wat is die oplossing? As ons terug gaan na hierdie kode, sou ek nie net verander die lengte van bar, wat anders moet ek nagaan? Wat anders moet ek doen om heeltemal te verhoed dat hierdie aanval? Ek wil nie net blindelings sê dat jy soveel grepe moet kopieer soos die lengte van bar. Ek wil om te sê, as kopieer baie grepe as in bar tot die toegekende geheue, of 12 maksimaal. So ek moet 'n soort van as voorwaarde wat nie gaan die lengte van bar, maar as dit 12, het ons net hard-kode oorskry 12 as die maksimum moontlike afstand. Anders sal die sogenaamde buffer oorloop aanval kan gebeur. Aan die onderkant van die skyfies, As jy nuuskierig om meer te lees is is die werklike oorspronklike artikel As jy wil om 'n blik te neem. 

Maar nou, onder die pryse hier betaal is, was ondoeltreffendheid. So dit was 'n vinnige lae vlak kyk na wat probleme kan nou ontstaan ​​dat ons toegang tot die geheue se rekenaar. Maar 'n ander probleem wat ons wat reeds op Maandag gestruikel was net die ondoeltreffendheid van 'n geskakelde lys. Ons is terug na lineêre tyd. Ons het 'n aangrensende verskeidenheid nie meer nie. Ons het nie 'n ewekansige toegang. Ons kan nie gebruik vierkante hakienotasie. Ons het letterlik 'n while lus gebruik soos die een wat ek geskryf het 'n oomblik gelede. Maar op Maandag, ons beweer dat ons kan kruip terug in die ryk van die doeltreffendheid bereiking iets wat logaritmiese miskien, of die beste nog, miskien selfs iets wat sogenaamde konstante tyd. So, hoe kan ons dit doen deur die gebruik van hierdie nuwe gereedskap, hierdie adresse hierdie wysers, en threading dinge van ons eie? Wel, gestel dat hier, dit is 'n klomp getalle wat ons wil om te slaan in 'n data struktuur en soek doeltreffend. Ons kan absoluut rewind tot week twee, gooi dit in 'n skikking, en soek hulle met behulp van binêre soek. Verdeel en oorwin. En in die feit dat jy geskryf het binêre soek in PSET3, waar jy die vonds program geïmplementeer word. Maar jy weet wat. Daar is soort van 'n meer slim manier om dit te doen. Dit is 'n bietjie meer gesofistikeerd en dit miskien kan ons sien waarom binêre soek is soveel vinniger. Eerstens, laat ons stel die idee van 'n boom. Wat al in werklikheid bome soort groei soos hierdie, in die wêreld van die rekenaar wetenskap hulle soort afwaartse groei soos 'n stamboom waar jy jou grootouers of grootouers of iets anders aan die bokant, die aartsvader en die matriarg van die familie, net een sogenaamde wortel, knoop, onder wat sy kinders is, hieronder wat is sy kinders, of sy nageslag meer algemeen. En enigiemand hang af die onderkant van die familie boom, naas die jongste in die gesin, kan ook net generies wees genoem die blare van die boom. 

So dit is net 'n klomp van woorde en definisies vir iets genoem 'n boom in die rekenaar wetenskap, baie soos 'n stamboom. Maar daar is liefhebber inkarnasies van die bome, waarvan een word 'n binêre soek boom. En jy kan soort van terg afgesien wat hierdie ding doen. Wel, dit is binêre in watter sin? Waar kom die binêre kom van hier af? Jammer? Dit is nie soseer 'n een of. Dit is meer dat elkeen van die nodes het geen meer as twee kinders, as ons hier sien. In die algemeen, 'n tree-- en jou ouers en grootouers kan soveel kinders het of kleinkinders as hulle eintlik wil hê, en so byvoorbeeld is daar drie het ons kinders af dat regterhand knoop, maar in 'n binêre boom, 'n node het nul, een, of twee kinders maksimaal. En dit is 'n mooi eiendom, want as dit beperk deur twee ons gaan in staat wees om kry 'n bietjie log basis twee aksie gaan hier uiteindelik. So het ons iets logaritmiese. Maar meer oor dit in 'n oomblik. Soek boom beteken dat die getalle is gereël sodat die linker kind se waarde is groter as die wortel. En sy reg kind groter as die wortel. Met ander woorde, as jy enige van die neem nodes, die sirkels in hierdie foto, en kyk na die links kind en sy regte kind, die eerste minder as moet wees, die tweede moet groter wees as. So gesonde verstand gaan 55. Dit is links kind 33. Dit is minder as. 55, sy reg kind 77. Dit is groter as. En dit is 'n rekursiewe definisie. Ons kon elke een van daardie kyk nodes en dieselfde patroon sou hou. 

So, wat is lekker in 'n binêre soek boom is dat 'n mens, kan ons dit implementeer met 'n struct, net soos hierdie. En selfs al is ons gooi baie van die strukture op jou, hulle is ietwat intuïtief nou hopelik. Die sintaksis nog arcane vir seker, maar die inhoud van 'n node in hierdie context-- en hou ons gebruik van die woord node, of dit 'n reghoek op die skerm of 'n sirkel, dit is net 'n paar generiese houer, in hierdie geval van 'n boom, soos die een ons gesien het, het ons 'n heelgetal nodig in elk van die nodes en dan moet ek twee wysers wys aan die linkerkant kind en die regte kind, onderskeidelik. So dit is hoe ons dalk implementeer wat in 'n struct. En hoe kan ek dit implementeer in die kode? Wel, laat ons neem 'n vinnige kyk na hierdie klein voorbeeld. Dit is nie funksioneel nie, maar ek het gekopieer en geplak daardie struktuur. En as my funksie vir 'n binêre soek boom search genoem, en dit neem twee argumente, 'n heelgetal N en 'n wyser om 'n knoop, so 'n verwysing na die boom of 'n verwysing na die wortel van 'n boom, hoe gaan ek oor die soek na N? Wel, die eerste, want ek is hantering van wysers, Ek gaan 'n gesonde verstand tjek te doen. As boom gelykes gelyk null, is N in hierdie boom of nie in hierdie boom? Dit kan nie wees nie, reg? As ek verlede nul, daar is niks. Ek kan net sowel blindelings sê terugkeer onwaar. As jy gee my niks, ek kan sekerlik nie vind 'n aantal N. So wat anders kan ek kyk nou? Ek gaan ook anders as N is sê minder as wat ookal op die boom node wat ek ingehandig N waarde. Met ander woorde, indien die aantal Ek is soek, N, is minder as die node dat ek is op soek na. En die knoop ek soek At is boom genoem, en onthou uit die vorige voorbeeld op die waarde te kry in 'n wyser, Ek gebruik die pyl notasie. So as N minder as boom pyl N, ek wil konseptueel gaan links. Hoe kan ek uitdruklike soek gelaat? Om duidelik te wees, indien dit die prentjie in die vraag, en ek het geslaag dat boonste arrow dit is wys af. Dit is my boom wyser. Ek wys aan die wortel van die boom. En ek is op soek sê vir die aantal 44, arbitrêr. Is 44 minder as of groter as 55 natuurlik? So dit is minder as. En so gaan dit as voorwaarde geld. So konseptueel, wat wil ek soek volgende as ek is op soek na 44? Ja? 

Presies, ek wil soek die linker kind of links sub-boom van hierdie foto. En in die feit, laat my deur die prentjie hier af vir 'n oomblik, aangesien Ek kan dit nie krap nie. As ek hier begin op 55, en Ek weet dat die waarde 44 Ek soek is na links, dit is soort van soos skeur die telefoon boek in half of skeur die boom in die helfte. Ek het nie meer te bekommer oor hierdie hele helfte van die boom. En tog, vreemd in terme van die struktuur, hierdie ding hier dat begin met 33, wat homself is 'n binêre soek boom. Ek het gesê die woord rekursiewe voor omdat inderdaad dit is 'n struktuur wat data per definisie is rekursiewe. Jy kan 'n boom wat is dié het groot nie, maar elkeen van sy kinders verteenwoordig 'n boom net 'n bietjie kleiner. In plaas daarvan dat oupa of ouma, nou is dit net ma or-- Ek kan nie say-- nie ma of pa, sou vreemd wees. Plaas die twee kinders is daar sou wees soos broer en suster. 'N nuwe generasie van die familie boom. Maar struktureel, dit is dieselfde idee. En dit blyk ek het 'n funksie waarmee ek 'n binêre soek kan soek boom. Dit is search genoem. Ek soek in die boom N pyl links anders as N is groter as die waarde dat ek tans op. 55 in die storie 'n oomblik gelede. Ek het 'n funksie genoem soek wat ek kan net slaag N hierdie en rekursief soek die sub-boom en net terugkeer wat dit ook al antwoord. Anders wat ek het 'n paar finale basis geval het hier. 

Wat is die finale geval? Boom is óf null. Die waarde wat ek soek, is óf minder as wat dit of groter is as wat of gelyk aan dit. En ek kon gelyk sê gelyk, maar dit is logies gelykstaande aan net hier sê anders. So waar is hoe ek iets vind. So hopelik is dit 'n selfs meer dwingende byvoorbeeld as die dom sigma funksie ons het 'n paar lesings terug, waar dit was net so maklik om 'n lus gebruik tel tot al die getalle van een om N. Hier met 'n datastruktuur wat homself is rekursief gedefinieer en rekursief getrek, nou is ons het die vermoë om onsself uit te druk in kode wat self rekursiewe. So, dit is die presiese dieselfde kode hier. 

So, wat ander probleme kan ons op te los? So 'n vinnige stap weg van bome vir net 'n oomblik. Hier is, sê die Duitse vlag. En daar is duidelik 'n patroon om hierdie vlag. En daar is baie van die vlae in die wêreld wat is so eenvoudig soos dit in terme van hul kleure en patrone. Maar veronderstel dat dit gestoor as 'n GIF of 'n JPEG, of bitmap, of 'n ping, enige grafiese lêer formaat waarmee jy vertroud is, waarvan sommige ons speel met in PSET4. Dit lyk nie die moeite werd om te stoor swart pixel, swart pixel, swart pixel, dot, dot, dot, 'n hele klomp van die swart pixels vir die eerste scanline, of ry, dan 'n hele klomp van die dieselfde, dan 'n hele klomp van dieselfde, en dan 'n hele klomp van rooi pixels, rooi pixels, rooi pixels, dan 'n hele n klomp van die geel pixels, geel, reg? 

Daar is hier so ondoeltreffendheid. Hoe sal jy intuïtief compress die Duitse vlag As die uitvoering daarvan as 'n lêer? Soos wat inligting kan ons nie pla stoor op skyf in orde ons lêergrootte afneem van soos 'n megabyte om 'n kilogreep, iets kleiner? Daarin lê die ontslag hier om duidelik te wees? Wat kan jy doen? Ja? Presies. Hoekom nie eerder as onthou die kleur van elke pixel darn net soos jy doen in PSET4 met die bitmap lêer formaat, hoekom doen jy nie net verteenwoordig die linker kolom van pixels, byvoorbeeld 'n klomp van die swart pixels, 'n klomp rooi, en 'n klomp van die geel, en dan net een of ander manier te enkodeer die idee van herhaling hierdie 100 keer of herhaal hierdie 1000 keer? Waar 100 of 1000 is net 'n heelgetal is, sodat jy kan wegkom met net 'n enkele nommer in plaas van honderde of duisende van bykomende pixels. En inderdaad, dit is hoe ons kon die Duitse vlag compress. En Nou wat van die Franse vlag? En 'n bietjie 'n soort van geestelike oefening, wat flag kan meer op die skyf saamgepers? Die Duitse vlag of die Franse vlag, as ons daardie benadering? Die Duitse vlag, want daar is meer horisontale ontslag. En deur die ontwerp, baie grafiese lêer formate wel werk as scan lyne horisontaal. Hulle kan werk vertikaal, net die mensdom besluit jaar gelede dat ons sal algemeen dink dinge ry deur ry in plaas van kolom deur kolom. So inderdaad as jy om te kyk na die lêer grootte van 'n Duitse vlag en 'n Franse vlag, so lank as wat die resolusie is dieselfde, dieselfde wydte en hoogte, hierdie een hier gaan groter, omdat jy moet jouself drie keer herhaal. Jy het na blou, herhaal spesifiseer jouself, wit, herhaal jouself, rooi, herhaal jouself. Jy kan nie net almal gaan die pad na regs. En as 'n eenkant, maak duidelik die kompressie is oral, indien dit vier rame van 'n video-- jy sal onthou dat 'n fliek of video is oor die algemeen soos 29 of 30 rame per sekonde. Dit is soos 'n klein flip boek waar jy beeld, beeld, beeld, beeld te sien net, beeld super vinnig, sodat dit lyk net soos die akteurs op die skerm beweeg. Hier is 'n hommel op top van 'n klomp van die blomme. En al is dit dalk soort wees moeilik om te sien met die eerste oogopslag, die enigste ding wat beweeg in hierdie film is die bye. 

Wat is stom oor die stoor video ongecomprimeerd? Dit is soort van 'n vermorsing om video te stoor as vier byna identies beelde wat verskil net sover waar die bye is. Jy kan weggooi mees van daardie inligting en onthou net, byvoorbeeld, die eerste raam en die laaste raam, sleutel rame as jy het ooit gehoor die woord, en net in die stoor middel waar die bye is. En jy hoef nie te stoor al die pienk, en die blou, en die groen waardes as well. So dit is net sê dat kompressie is oral. Dit is 'n tegniek wat ons gebruik dikwels of as vanselfsprekend aanvaar hierdie dae. 

Maar hoe weet jy teks compress? Hoe gaan jy oor die teks comprimeren? Wel, elkeen van die karakters in Ascii is een byte, of agt stukkies. En dit is soort van dom, reg? Omdat jy waarskynlik tik A en E en ek en O en U 'n baie meer dikwels as soos W of V of Z, afhangende van die taal waarin jy beslis skryf. En so hoekom gebruik ons agt bisse vir elke brief insluitend die minste gewilde letters, reg? Hoekom nie minder stukkies vir gebruik die super gewilde briewe, soos E, die dinge wat jy dink eerste in Wheel of Fortune, en gebruik meer stukkies vir die minder gewilde letters? Hoekom? Omdat ons net gaan om gebruik dit minder gereeld. 

Wel, dit blyk dat daar nie was pogings aangewend om dit te doen. En as jy onthou van graad skool of die hoërskool, Morsekode. Morsekode het kolle en strepies wat kan wees oorgedra langs 'n draad soos klink of seine van 'n soort. Maar Morsekode is 'n super skoon te maak. Dit is soort van 'n binêre stelsel in dat jy kolle of koppeltekens. Maar as jy sien, byvoorbeeld, twee kolle. Of as jy dink terug aan die operateur wat gaan soos beep, beep, beep, beep, slaan 'n bietjie sneller wat stuur 'n sein, as jy die ontvanger, ontvang twee kolletjies, watter boodskap het jy gekry? Heeltemal arbitrêre. 

Ek? Ek? Of wat about-- of ek? Miskien was dit net twee regte E se? So daar is hierdie probleem van decodability met Morse kode, waardeur tensy die persoon stuur jou boodskap eintlik pouses sodat jy kan soort van sien of hoor die gapings tussen letters, dit is nie voldoende om net stuur 'n stroom van nulle en ene, of kolletjies en strepies, want daar is onduidelikheid. E is 'n enkele dot, so as jy sien twee kolle of hoor twee punte, miskien is dit twee E's of miskien is dit een I. Sodat ons 'n stelsel wat is 'n moet bietjie meer slim as dit. So 'n man met die naam Huffman jaar gelede het met presies hierdie. So ons is maar net gaan om 'n vinnige blik te neem hoe bome is related hierdie. Veronderstel dat dit 'n paar stupid boodskap wat jy wil stuur, saamgestel uit net A, B, C se D's en E se maar daar is 'n baie ontslag hier. Dit is nie bedoel om Engels. Dit is nie geïnkripteer. Dis net 'n dom boodskap met baie van die herhaling. So as jy eintlik tel al die A se B se C se D's, en E se, hier is die frekwensie. 20% van die briewe is A se 45% van die letters is E se en drie ander frekwensies. Ons getel daar met die hand en net het die wiskunde. 

So dit blyk dat Huffman, 'n geruime tyd gelede, besef dat, jy weet wat, as ek begin bou 'n boom, of bos bome, as jy wil, soos volg, kan ek die volgende doen. Ek gaan 'n knoop aan elke gee van die briewe wat ek omgee en ek gaan om te slaan binnekant van die node die frekwensies as 'n drywende punt waarde, of jy kan dit gebruik om 'n N ook maar ons sal net gebruik hier 'n float. En die algoritme wat hy voorgestel is dat jy neem hierdie bos enkele node bome, so super kort bome, en jy begin hulle verbind met nuwe groepe, nuwe ouers, as jy wil. En jy dit doen deur die keuse van die twee kleinste frekwensies op 'n tyd. So ek het 10% en 10%. Ek skep 'n nuwe knoop. En ek noem die nuwe node 20%. 

Watter twee nodes Ek kombineer volgende? Dit is 'n bietjie dubbelsinnig. So is daar 'n paar hoek gevalle oorweeg nie, maar om dinge mooi te hou, Ek gaan om te kies 20% - Ek ignoreer nou die kinders. Ek gaan om te kies 20% en 15% en trek twee nuwe kante. En nou, wat twee nodes ek logies te kombineer? Ignoreer al die kinders, al die kleinkinders, kyk net na die wortels nou. Watter twee nodes ek saam te bind? Punt twee en 0,35. So laat my trek twee nuwe kante. En dan het ek nog net een gekry linkerkant. So hier is 'n boom. En dit is doelbewus getrek om te kyk soort mooi, maar sien dat die rande het ook gemerk nul en een. So al die linkerkant kante is nul arbitrêr nie, maar konsekwent. Al die regte kante is kinders. 

En so wat Hoffman voorgestelde is, As jy wil 'n B verteenwoordig, eerder as verteenwoordig die aantal 66 as 'n ASCII wat agt hele stukkies, jy weet wat, net store die patroon nul, zero, zero, nul, want dit is die pad uit my boom, mnr Huffman se boom, die blaar van die wortel. As jy wil 'n stoor E, daarenteen, het nie stuur agt stukkies wat 'n E. verteenwoordig In plaas daarvan, stuur Watter patroon van stukkies? Een. En wat is lekker oor hierdie is wat E is die gewildste brief en gebruik jy is die kortste kode vir dit. Die volgende mees gewilde brief lyk soos dit was A. En so hoeveel stukkies het hy voor die gebruik vir wat? Nul, een. 

En omdat dit geïmplementeer as hierdie boom, vir nou laat my stipuleer daar geen dubbelsinnigheid as in Morse kode, want al die letters wat jy omgee is aan die einde van hierdie kante. Sodat is net een toepassing van 'n boom. Dit is-- en ek sal waai my hand op hierdie hoe jy kan implementeer as 'n C-struktuur. Ons moet net kombineer 'n simbool, soos 'n kar, en die frekwensie in links en regs. Maar laat ons kyk na twee finale voorbeelde dat jy kry baie vertroud is met na quiz nul in die probleem stel vyf. 

So is daar die data struktuur bekend as 'n hash tafel. En 'n hash tafel is soort van koel in dat dit emmers. En veronderstel daar is vier emmers hier, net vier leë spasies. Hier is 'n pak kaarte, en hier is klub, graaf, klub, diamante, klub, diamante, klub, diamante, clubs-- so dit is die ewekansige. Harte, hearts-- so ek is bucketizing al die insette hier. En 'n hash tafel behoeftes om te kyk na jou insette, en sit dit dan in 'n sekere plaas op grond van wat jy sien. Dit is 'n algoritme. En Ek gebruik 'n super eenvoudige visuele algoritme. Die moeilikste deel van wat was onthou wat die foto's is. En dan is daar vier totale dinge. 

Nou is die stapels groei, wat is 'n doelbewuste ontwerp ding hier. Maar wat anders kan ek doen? So eintlik hier het ons 'n n klomp van die ou skool eksamen boeke. Veronderstel dat 'n klomp van die studente se name op hier. Hier is 'n groter hash tafel. In plaas van vier emmers, Ek het, kom ons sê 26. En ons het nie wil gaan leen 26 dinge van buite [? Annenberg?], So hier is vyf wat verteenwoordig A deur Z. En as ek sien 'n student wie se naam begin met A, Ek gaan om sy of haar quiz daar te vestig. As iemand begin met C, daar, A-- eintlik nie wil om dit te doen. B gaan oor hier. So ek het 'n en B en C. En nou hier is nog 'n student. Maar as dit hash tafel geïmplementeer met 'n skikking, Ek is soort van geskroef op hierdie punt, reg? Ek moet soort van om dit iewers sit. 

So een manier wat ek kan hierdie los is, al reg, A besig is, is besig om B, C is besig. Ek gaan hom in D. sit So by eerste, ek het ewekansige direkte toegang aan elk van die emmers vir die studente. Maar nou is dit soort van afgewentel in iets lineêre, want as ek wil om te soek vir iemand wie se naam begin met A, Ek is so hier. Maar as dit nie die A student Ek is op soek na, Ek het soort van begin nagaan die emmers, want wat ek gedoen het was soort van lineêr ondersoek die data struktuur. A stupid manier om te sê net kyk vir die eerste beskikbare opening, en sit 'n plan B, om so te praat, of plan D in hierdie geval, die waarde in daardie plek plaas. Dit is net so dat as jy het het 26 plekke en geen studente met die naam Q of Z, of iets soos dat ten minste jy die ruimte. 

Maar ons het reeds meer gesien slim oplossings hier, reg? Wat sou jy doen in plaas as jy 'n botsing? As twee mense het die naam A, wat sou het 'n slimmer of meer is intuïtief oplossing as net Om 'n waar D is veronderstel om te wees? Hoekom het ek nie net gaan buite [? Annenberg?], soos malloc, 'n ander node, sit dit hier, en dan sit dat 'n student hier. Sodat ek in wese 'n soort van 'n skikking, of miskien meer elegant as ons begin om 'n geskakelde lys te sien. 

En so 'n gemors tafel is 'n struktuur wat kan kyk net soos hierdie, maar meer slim, jy iets genoem aparte aaneenskakeling, waardeur 'n hash tafel eenvoudig is 'n skikking, elk van waarvan die elemente is nie 'n nommer, is self 'n geskakelde lys. Sodat jy super vinnige toegang besluit waar om jou waarde te hash. Baie soos met die kaarte byvoorbeeld Ek het super vinnige besluite. Harte gaan hier, diamante gaan hier. Dieselfde hier, A gaan hier, D gaan hier, B gaan hier. So super vinnige blik-ups, en as jy gebeur om te loop in 'n geval waar jy het botsings, twee mense met dieselfde naam, goed dan jy net begin om saam te koppel. En miskien hou hulle gesorteer alfabeties, miskien het jy nie. Maar ten minste nou het ons die dinamika. So aan die een kant het ons super vinnig konstante tyd, en soort van lineêre tyd betrokke as hierdie geskakelde lyste begin 'n bietjie lank om te kry. 

So hierdie soort van 'n dom, geeky grap jaar gelede. Aan die CS50 hack-a-thon, Wanneer studente so, sommige TF of CA elke jaar dink dit is snaaks om te sit 'n teken soos hierdie, waar dit net beteken dat as jou naam begin met 'n A, gaan op hierdie manier. As jou naam begin met 'n B, gaan this-- OK, dit is snaaks dalk later in die semester. Maar daar is 'n ander manier om dit te doen, ook. Kom terug na daardie. 

So daar is hierdie struktuur. En dit is ons laaste struktuur vir vandag, dit is iets wat 'n sogenaamde Trie. T-R-I-E, wat vir een of ander rede is kort vir herwinning, maar dit is bekend Trie. So 'n Trie is nog 'n interessante mengsel van 'n baie van hierdie idees. Dit is 'n boom, wat ons voorheen gesien het. Dit is nie 'n binêre soek boom. Dit is 'n boom met 'n aantal van kinders, maar elkeen van die kinders in 'n Trie is 'n skikking. 'N verskeidenheid van grootte, sê 26 of dalk 27 as jy wil koppelteken name ondersteun of apostrofs in mense se name. 

En so dit is 'n data-struktuur. En as jy kyk van bo na onder, soos as jy kyk na die top node daar M, is verwys na die linker ding daar wat dan 'n, X, W, E, L, L. Dit is net 'n data struktuur wat arbitrêr is die stoor mense se name. En Maxwell gestoor deur net volgende 'n pad van skikking om verskeidenheid te skikking. Maar wat is ongelooflik om 'n Trie is dat, terwyl 'n geskakelde lys en selfs 'n skikking, die beste wat ons nog ooit gekry het is lineêre tyd of logaritmiese tyd op soek iemand op. In hierdie data struktuur van 'n Trie, as my data struktuur het 'n naam in dit en ek is op soek na Maxwell, ek is gaan hom redelik vinnig te vind. Ek kyk net vir M-A-X-W-E-L-L. As hierdie data struktuur, daarenteen, As N is 'n miljoen, as daar 'n miljoen name in hierdie data struktuur, Maxwell is nog steeds gaan wees opspoorbar ná net M-A-X-W-E-L-L stappe. En David-- D-A-V-I-D stappe. Met ander woorde, deur die bou 'n datastruktuur wat het al hierdie skikkings, wat almal hulself te ondersteun ewetoeganklike, Ek kan begin soek op mense se noem die gebruik van 'n bedrag van die tyd wat eweredig aan die aantal nie van die dinge in die data struktuur, soos 'n miljoen bestaande name. Die bedrag van die tyd wat dit neem om my te vind M-A-X-W-E-L-L in hierdie data struktuur is proporsionele nie die grootte van die data struktuur, maar om die lengte van die naam. En realisties die name wat ons soek up gaan nooit lank mal wees. Miskien is iemand het 'n 10 karakter noem, 20 naam karakter. Dit is beslis eindige, reg? Daar is 'n mens op aarde wat het die langste moontlike naam maar dat die naam is 'n konstante waarde lengte, reg? Dit maak nie verskil in enige sin nie. So op hierdie manier, ons het bereik 'n datastruktuur wat konstant tyd look-up. Dit neem 'n aantal stappe afhangende van die lengte van die insette, maar nie die aantal naam in die data struktuur. So as ons dubbel die getal name volgende jaar van 'n miljard tot twee miljard, bevinding Maxwell gaan neem presies dieselfde aantal sewe stappe om hom te vind. En so het ons lyk bereik ons heilige graal van die bestuur van die tyd. 

So 'n paar vinnige aankondigings. Quiz nul kom. Meer oor wat op die webwerf die kursus se oor die volgende paar dae. Maandag se lecture-- dit is 'n vakansie hier by Harvard op Maandag. Dit is nie in New Haven, so ons is die neem van die klas New Haven vir lesing op Maandag. Alles sal verfilm en gestroom live soos gewoonlik, maar laat eindig vandag met 'n 30 sekonde clip genaamd "Diep gedagtes" deur Daven Farnham, wat is geïnspireer verlede jaar deur die Saterdag Night Live se "Diep gedagtes" deur Jack Handy, wat moet nou sin maak. 

Film: En nou, "Diep Gedagtes "deur Daven Farnham. Hash tafel. 

Spreker 1: Alle reg, dit is dit vir nou. Ons sal sien dat jy volgende week. 

DOUG: Om dit te sien in aksie. So laat ons neem 'n blik op wat nou. So hier het ons 'n ongesorteerde skikking. 

IAN: Doug, kan jy gaan voort en herlaai hierdie vir net een sekonde, asseblief. Alle reg, is kameras rol, so aksie wanneer jy gereed is, Doug is, OK? DOUG: Alle reg, sodat dit wat ons hier is 'n ongesorteerde skikking. En ek het al die elemente gekleurde rooi om aan te dui dat dit, in werklikheid, ongesorteerde. So onthou dat die eerste ding wat ons doen is ons sorteer die linker helfte van die skikking. Dan sorteer ons die reg helfte van die skikking. En ya-da, ya-da, ya-da, ons hulle saam te smelt. En ons het 'n heeltemal gesorteerde skikking. So dit is hoe saamsmelt soort werk. 

IAN: Whoa, whoa, whoa, sny, sny, sny, sny. Doug, kan jy nie net ya-da, ya-da, ya-da, jou pad deur merge soort. 

DOUG: Ek net gedoen het. Dis reg. Ons is goed om te gaan. Kom ons hou rollende. So in elk geval, 

IAN: Jy het om te verduidelik dit meer volledig as dit. Dit is net nie genoeg nie. DOUG: Ian, ons doen nie nodig het om terug te gaan na een. Dis reg. So in elk geval, as ons voortgaan met merge-- Ian, ons is in die middel van die verfilming. 

IAN: Ek weet. En ons kan nie net ya-da, ya-da, ya-da, deur die hele proses. Jy het om te verduidelik hoe die twee kante bymekaar te kry saamgesmelt. 

DOUG: Maar ons het reeds verduidelik hoe die twee sides-- 

IAN: Jy het net gewys hulle 'n merge skikking. DOUG: Hulle weet die proses. Hulle is fine. Ons het meer as dit tien keer weg. 

IAN: Jy oorgeslaan net reg oor. Ons gaan terug na een, het jy Kan jy nie ya-da, ya-da oor. Alle reg, terug na die een. 

DOUG: Ek het om terug te gaan deur al die skyfies? My God. Dit is soos die sesde keer, Ian. Dis reg. 

IAN: Alle reg. Jy gereed? Groot. Aksie.