[Muziek] DAVID MALAN: Dit is CS50. Dit is zowel het begin en het end-- zoals literally-- bijna het einde van week zes. 

Ik dacht dat ik zou delen een beetje een leuk feitje. Ik trok dit uit een data afgelopen semester in te stellen. U herinnert zich misschien dat we u vragen op elke p set formulier als je hebt online bekeken of als je hebt bijgewoond in persoon. En hier is de data. Dus vandaag was heel erg voorspelbaar. Maar we wilden een beetje door te brengen van tijd met jou toch. Zou iemand graag waarom dit vermoeden grafiek is zo jaggy, up down, up down, zo consequent? Wat doen elk van de pieken en dalen vertegenwoordigen? 

Publiek: [onverstaanbaar] DAVID MALAN: Inderdaad. En meer vermakelijk, god verhoede, we houden een lezing op een vrijdag aan het begin van het semester, dat is wat we zien gebeuren. Dus vandaag, we deelnemen aan een beetje meer over datastructuren. En meer van een vaste stof mentaal model voor problemen op vijf, die is nu uit. Spelfouten, waarin, zullen we overhandigen u een tekstbestand zo'n 100.000 plus woorden Engels, en je gaat te hebben om erachter te komen hoe ze slim te laden in het geheugen, in het RAM, met behulp van een aantal gegevens structuur van uw keuze. 

Nu is een dergelijke datastructuur kan , maar waarschijnlijk niet zijn, de vrij simplistische gelinkte lijst, die we vorige keer geïntroduceerd. En een gelinkte lijst had tenminste een voordeel over een array. Wat is een voordeel van een gekoppelde lijst misschien wel? 

Publiek: Insertion. 

DAVID MALAN: Insertion. Wat bedoel je daarmee? 

Publiek: Overal langs de lijst [onverstaanbaar]. 

DAVID MALAN: Goed. Dus je kunt een element waar te voegen je wilt in het midden van de lijst zonder iets te schuifelen, die we tot de conclusie, in onze sorteercentra discussies, is niet noodzakelijk een goede zaak, omdat het tijd kost om daadwerkelijk verplaatsen al deze mensen links of rechts. En dus met een gelinkte lijst, kunt u alleen toe te wijzen met malloc, een nieuw knooppunt, en dan update een paar pointers-- twee, drie operaties max-- en we zijn in staat om iemand sleuf in ergens in een lijst. 

Wat anders was voordelig over een gekoppelde lijst? Yeah? 

Publiek: [onverstaanbaar] DAVID MALAN: Perfect. Perfect. Het is echt dynamisch. En dat je niet plegen, vooraf enkele vaste grootte stuk van het geheugen, zoals je zou hebben om met een array, de kop van die is dat je alleen op knooppunten kan toewijzen vraag daarbij met alleen zoveel ruimte als je eigenlijk nodig hebt. In tegenstelling tot een array, zou je per ongeluk te weinig toe te wijzen. En dan is het gewoon om een ​​pijn in de nek naar een nieuw groter scala herverdelen, kopiëren alles over, gratis de oude array, en ga dan verder over uw bedrijf. Of erger nog, zou je weg te wijzen meer geheugen dan je eigenlijk nodig hebt, en dus je gaat om een ​​zeer hebben dunbevolkte array, om zo te zeggen. 

Dus een gelinkte lijst geeft u deze voordelen van dynamiek en flexibiliteit met inserties en deleties. Maar zeker moet er een prijs betaald worden. In feite is één van de thema verkend quiz nul was een paar van de trade-offs we hebben tot nu toe gezien. Dus wat is een prijs die betaald of een nadeel van een gelinkte lijst? Yeah. 

Publiek: Geen random access. 

DAVID MALAN: Geen random access. Maar who cares? Random access klinkt niet overtuigend. 

Publiek: [onverstaanbaar] DAVID MALAN: Precies. Als je wilt hebben een zekere algorithm-- en laat me eigenlijk voorstellen binary search name die is degene die we hebben nogal een bit-- gebruikt als je geen random access hebben, kun je dat eenvoudige rekenkundige niet doen vinden als het middelste element en springen recht op. U moet in plaats daarvan om te beginnen bij het eerste element en lineair zoeken van links naar rechts als u wilt weten het midden of een ander element. 

Publiek: Het duurt waarschijnlijk meer geheugen. 

DAVID MALAN: neemt meer geheugen. Waar is dat extra kosten komen van de in het geheugen? 

Publiek: [onverstaanbaar] DAVID MALAN: Precies. In dit geval hier, hadden we een gelinkte lijst van gehele getallen, en toch zijn we het verdubbelen de hoeveelheid geheugen we nodig hebben door ook opslaan van deze pointers. Nu minder van een big deal als uw structs groter worden en je bent het opslaan geen nummer maar misschien een student of een ander object. Maar het punt blijft zeker. Dus een aantal bewerkingen geweest op de lijsten werden genoemd waren grote O van N-- lineair. Dingen zoals het inbrengen of zoekopdracht of deletie bij een element toevallig op het einde van de lijst of het nu al dan niet gesorteerd. 

Soms heb je zou je geluk en in dus ondergrenzen op deze operaties Ook constante tijd zijn als je altijd naar het eerste element, bijvoorbeeld. Maar uiteindelijk hebben we beloofd naar de heilige graal te bereiken gegevensstructuren, of sommige benadering daarvan, door middel van een constante tijd. Kunnen we elementen vinden of elementen toe te voegen of elementen uit een lijst verwijderen? We zullen heel snel zien. En het blijkt dat één van de mechanismen die we zal gaan gebruiken vandaag, jaarlijkse gebruik in p vijf, is eigenlijk redelijk bekend. Bijvoorbeeld, als het een groep examen boeken, die elk heeft een student de eerste voornaam en achternaam op, en ik pak ze op uit aan het einde van een examen, en ze zijn allemaal vrij veel in een willekeurige volgorde, en we willen gaan over het sorteren deze examens zodat zodra graded het is gewoon een stuk makkelijker en sneller om ze uit te delen terug aan studenten alfabetisch. Wat zou je instincten zijn voor een stapel van examens als deze? 

Nou, als je net als ik, je zou kunnen zien dat dit m, dus ik ga dit soort zetten in, als dit is mijn tafel of mijn verdieping waar Ik ben het verspreiden van dingen out-- of mijn reeks really-- Ik zou al de mevrouw in daar te zetten. Oh. Hier is een A. Dus ik zou zet de Zoals hier. Oh. Hier is nog een A. Ik ga te zetten dat meer dan hier. Hier is een Z. Hier is een andere M. En zo Ik zou kunnen beginnen met het maken van palen als deze. En dan misschien zou ik in later gaan en een soort van zeer nitpicky-ly sorteren de individuele palen. Maar het punt is dat ik zou kijken aan de ingang dat ik handed en ik zou een aantal berekende maken besluit op basis van die input. Als het begint met A, zet het daar. Als het begint met Z, zet het dan daar, en alles daar tussenin. 

Dus dit is een techniek die algemeen bekend als hashing-- H-A-S-H-- Dit betekent gewoonlijk met als invoeren en gebruiken die ingang te berekenen een waarde, meestal een aantal, en dat nummer is de index in een opslagbuffer container, zoals een array. Dus met andere woorden, zou ik een heb hash-functie, als ik in mijn hoofd, dat als ik iemand zie is naam die begint met A, Ik ga naar de kaart die tot nul in mijn hoofd. En als ik iemand zie met Z, ik ben ga naar de kaart die op 25 in mijn hoofd en zet dan die in de laatste meest stapel. 

Nu, als je denkt over het niet mijn hersenen maar een C-programma, welke nummers kan u vertrouwen op om dat hetzelfde resultaat te bereiken? Met andere woorden, als je had het ASCII-teken A, hoe bepaal wat emmer om het aan te brengen? U heeft waarschijnlijk niet wilt zet het in emmer 65, dat zou zijn als daar zonder goede reden. Waar wil je A zetten in termen van de ASCII-waarde? Waar wilt u doen om zijn ASCII waarde om te komen met een slimmere emmer om het aan te brengen? 

Publiek: Minus A. 

DAVID MALAN: Yeah. Zo min A of min bijzonder 65 als het een hoofdletter A. Of 98 als het is een kleine letter a. En dus dat zou ons in staat stellen, zeer eenvoudig en zeer rekenkundig, zet iets in een emmer als dat. Dus het blijkt dat we eigenlijk doen dit zo goed zelfs met de quizzen. 

Dus je zou herinneren u omcirkeld uw naam lesgeven collega's op de cover. En de namen van de TF's werden georganiseerd in deze kolommen alfabetisch, Nou, geloof het of niet, wanneer alle 80 plus van ons kwamen bij elkaar de andere nacht naar rang, de laatste stap in onze sorteerproces is om de quizzen hash in een grote ruimte van grond aan de [onverstaanbaar] en tot ieders quizzen lay out precies de volgorde van TF namen op de omslag, omdat dan is het een stuk makkelijker voor ons om door middel van dat met lineaire zoeken of een soort van slimheid een TF te vinden zijn quizzen van haar leerlingen. 

Dus dit idee van hashing dat je zult zien is vrij krachtig is eigenlijk best alledaags en zeer intuïtief, net als misschien verdelen en heers was in week nul. Ik snel vooruit naar de hackathon een paar jaar geleden. Dit was Zamyla en een paar ander personeel groet studenten als ze kwam. En we hadden een hele hoop van het vouwen tafels daar met naamplaatjes. En we hadden de naamplaatjes georganiseerd met als de As daar en de Zs daar. En dus een van de TF's heel slim schreef dit als de instructies voor de dag. En in week 12 van het semester deze alles was volkomen logisch en iedereen wist wat te doen. Maar wanneer je hebt wachtrij op dezelfde wijze je bent de uitvoering van de Hetzelfde idee van een hash. Dus laten we formaliseren het een beetje. Hier is een array. Het is getrokken om een ​​beetje breed net uit te beelden, visueel, dat we strings zou kunnen brengen in iets als dit. En dit array duidelijk van de grootte 26 in totaal. En het ding heet tafel willekeurig. Maar dit is slechts vertolking van een kunstenaar van wat een hash table zou kunnen zijn. 

Dus een hash table nu gaat zijn een hoger niveau datastructuur. Aan het eind van de dag we staan ​​op het punt om te zien dat u kan een hash table, implementeren die is net als de check-in lijn bij een hackathon dit veel op tabel gebruikt voor het sorteren examen boeken. Maar een hash table is soort van dit hoge niveau concept dat een array kunnen gebruiken onder de motorkap om het te implementeren, of het kan een lengte lijst gebruiken of zelfs misschien enkele andere datastructuren. En nu is dat de theme-- nemen sommige van deze fundamentele ingrediënten zoals een array en dit gebouw blokkeren nu met een lengte lijst en het zien van wat we kunnen bouwen naast die welke, zoals ingrediënten in een recept, waardoor meer en meer interessant en nuttig eindresultaten. 

Dus met de hash table we zouden het uit te voeren in het geheugen van dit picturaal als, maar hoe zou het eigenlijk zijn gecodeerd up? Nou, misschien zo eenvoudig is dit. Als de capaciteit in alle caps, is gewoon sommige constant-- bijvoorbeeld 26, voor de 26 letters van het alphabet-- Ik zou mijn variabele tafel roepen, en ik zou beweren dat ik ga zet char sterren daar, of string. Dus het is zo simpel als dit als je willen een hash table implementeren. En toch, dit is echt gewoon een array. Maar nogmaals, een hash tafel is nu wat we zullen noem een ​​abstract datatype dat is gewoon soort van een conceptuele gelaagdheid op de top van iets meer alledaagse nu graag een array. 

Nu, hoe gaan we heen over het oplossen van problemen? Nou, vroeger had ik de luxe van het hebben hier genoeg ruimte in zodat ik kon het zetten quizzen ergens wilde ik. Dus als zou hier gaan. Zs zou hier gaan. Ms zou gaan hier. En toen had ik wat extra ruimte. Maar dit is een beetje een cheat recht nu, omdat deze tabel, als ik echt dacht aan het als een array, is gewoon gaan van bepaalde vaste omvang hebben. 

Dus technisch gezien, als ik trek up van een andere student quiz en zie, oh, deze persoon naam met een A begint ook, Ik wil dat soort om het daar te zetten. Maar zodra ik het daar, als Deze tabel vormt inderdaad een matrix, Ik ga worden dwingende of beuken wie deze student quiz is. Right? Als dit een array slechts één ding kan gaan in elk van deze cellen of elementen. En dus heb ik soort om te kiezen. 

Nu eerder het soort van I bedrogen en deed dit of ik gewoon een soort van gestapelde ze boven elkaar. Maar dat gaat niet in code om te vliegen. Dus waar kan ik de tweede student wiens naam is A als alles wat ik had is dit beschikbare ruimte in? En ik heb drie slots en het gebruikt ziet eruit alsof er net een paar anderen. Wat zou u doen? Publiek: [onverstaanbaar] DAVID MALAN: Yeah. Misschien laten we het gewoon simpel houden. Right? Het past niet waar ik wil om het te zetten. Dus ik ga om het te zetten technisch gezien waar een B zou gaan. Nu, natuurlijk, ik begin om mezelf te schilderen in een hoek. Als ik aan een student wiens naam is eigenlijk B, B zal nu een beetje te verplaatsen naar voren, zoals zou kunnen gebeuren, yep, indien een B is nu het moet hier gaan. 

En dus is deze zeer snel kan problematisch worden, maar het is een techniek die eigenlijk wordt aangeduid als lineaire sonderen, waarbij je gewoon rekening houden met uw array worden langs de lijn. En je gewoon een soort sonde of inspecteren elke beschikbare element op zoek naar een beschikbare plek. En zodra je merkt één, je het laat vallen daar. 

Nu, wordt de prijs die nu betaald deze oplossing is wat? We hebben een vaste grootte array, en toen ik de namen in te voegen in het, althans in het begin, wat is de looptijd van het inbrengen voor het aanbrengen van de studenten ' quizzen in de juiste bakken? Big O van wat? 

Publiek: n. DAVID MALAN: Ik hoorde big O van n. Niet waar. Maar we zullen elkaar plagen waarom in slechts een moment. Wat zou het zijn? 

Publiek: [onverstaanbaar] DAVID MALAN: En laat me visueel doen. Dus stel dat dit de letter S. 

Publiek: Het is één. DAVID MALAN: Het is één. Right? Dit is een array, die betekent dat we random access. En als we denken van deze als nul en dit als 25, en we beseffen dat, oh, hier is mijn ingang S, Ik kan zeker omzetten S, een ASCII-karakter, een overeenkomstig aantal tussen nul en 25 en dan meteen het zetten waar het behoort. 

Maar natuurlijk, zodra ik bij de tweede persoon wiens naam is A of B of C uiteindelijk, als ik heb gebruikt de lineaire indringende als mijn oplossing, de looptijd van insertie in het ergste geval er werkelijk gaande is om te delegeren naar wat? En ik heb hier horen kunnen vroeg. Publiek: [onverstaanbaar] DAVID MALAN: Dus het is n inderdaad een keer heb je een voldoende grote dataset. Dus, enerzijds, indien array is groot genoeg en uw gegevens is schaars genoeg, je krijg deze mooie constante tijd. Maar zodra je begint steeds meer en meer elementen, en gewoon statistisch je krijgt meer mensen met de letter Een als hun naam of de letter B, het kon in potentie overgaan in iets meer lineair. Dus niet helemaal perfect. Dus konden we beter doen? 

Nou, wat was onze oplossing voor wanneer we willen meer dynamiek dan hebben iets als een array toegestaan? Publiek: [onverstaanbaar] DAVID MALAN: Wat hebben we introduceren? Yeah. Dus een gelinkte lijst. Nou, laten we eens kijken wat een gekoppelde lijst zou in plaats daarvan voor ons doen. Nou, laat ik stel voor dat we de foto te trekken als volgt. Nu is dit een ander afbeelding van een voorbeeld een andere tekst, eigenlijk, dat eigenlijk met een array van grootte 31. En deze auteur gewoon besloten om strings hash niet op naam van de persoon, maar op basis van hun geboortedata. Onafhankelijk van de maand, ze dacht als je geboren bent op de eerste van de maand of de 31e van een maand, de auteur zal hash op basis van die waarde, zodat de namen een beetje spreiden meer dan alleen maar 26 plekken zou kunnen stellen. En misschien is het een beetje meer uniforme dan ga met alfabetische letters, want natuurlijk is er waarschijnlijk meer mensen in de wereld met namen die beginnen met A dan zeker andere letters van het alfabet. Dus misschien is dit een beetje uniformer, uitgaande een uniforme verdeling van baby's over een maand. 

Maar natuurlijk is dit nog steeds niet perfect. Right? We hebben van botsingen. Meerdere mensen in dit datastructuur nog met dezelfde geboortedatum minstens je bent ongeacht maand. Maar wat heeft de auteur gedaan? Nou, het lijkt erop dat we hebben een scala aan de linkerkant verticaal getrokken, maar dat is slechts vertolking van een kunstenaar. Het maakt niet uit welke richting je trekken een array, het is nog steeds een array. Wat is dit voor een reeks van schijnbaar? 

Publiek: Linked lijst. 

DAVID MALAN: Yeah. Het lijkt erop dat het een reeks van gekoppelde lijst. Dus nogmaals, op dit punt van de soort het gebruik van deze gegevensstructuren nu als ingrediënten meer interessante oplossingen, je absoluut eens fundamenteel, als een array, en neem dan iets meer interessant als een gelinkte lijst en zelfs te combineren tot een nog interessanter gegevensstructuur. En inderdaad, ook dit zou een hash tabel worden genoemd, waarbij de array echt de hash table, maar dat hash table heeft kettingen zogezegd, die kan groeien of krimpen basis van de aantal elementen die u wilt invoegen. 

Nu, dus, wat is er de lopende tijd nu? Als ik iemand wil invoegen wiens verjaardag is 31 oktober, waar komt hij of zij heen? Prima. Helemaal onderaan waar het zegt 31. En dat is perfect. Dat was constante tijd. Maar wat als we iemand anders vinden wiens verjaardag is, laten we eens kijken, Oktober, november, 31 december? Waar is hij of zij gaan om te gaan? Hetzelfde. Twee stap wel. Dat is constant al is het niet? Prima. Op dit moment is het. Maar in het algemene geval, hoe meer mensen we voegen, probabilistisch, we gaan om meer en meer botsingen te krijgen. 

Nu is dit een beetje beter omdat technisch nu mijn ketenen zou kunnen worden in het ergste geval hoe lang? Als ik n mensen in te voegen in dit meer geavanceerde datastructuur, n mensen, in het ergste geval het gaat om n zijn. Waarom? 

Publiek: Want als iedereen heeft dezelfde verjaardag, ze gaan om één lijn te zijn. DAVID MALAN: Perfect. Het is misschien een beetje gekunsteld, maar echt in het ergste geval, als iedereen heeft dezelfde verjaardag, gezien de ingangen u hebt, je gaat naar een hebben massaal lange keten. En dus, zou je het kunnen noemen een hash table, maar eigenlijk is het gewoon een enorme gelinkte lijst met een hele hoop verspilde ruimte. Maar in het algemeen, als we aannemen dat tenminste verjaardagen zijn uniform-- en is het waarschijnlijk niet. Ik ben het maken van die up. Als we aannemen voor Omwille van de bespreking dat zij dan in theorie, indien Dit is de verticale voorstelling van de array, en dan hopelijk ben je ga ketens die zijn, weet je, ongeveer dezelfde lengte waarbij elk van deze staat voor een dag van de maand. 

Nu, als er 31 dagen in de maand, dat betekent dat mijn lopende tijd echt is big O van n meer dan 31, die voelt beter dan lineair. Maar wat was een van onze toezeggingen een paar weken geleden wanneer het ging om het uiten van de looptijd van een algoritme? Gewoon alleen kijken naar de hoge orde term. Right? 31 is zeker nuttig. Maar dit is nog steeds big O van n. Maar een van de thema's van het probleem te stellen vijf zal worden erkennen dat absoluut, asymptotisch theorie Deze gegevensstructuur is niet beter dan één massieve gelinkte lijst. Inderdaad, in het ergste geval, dit hash table zou kunnen delegeren naar die. 

Maar in de echte wereld, met ons mensen dat de eigen Mac's of pc's of wat dan ook en lopen echte wereld software op reële datasets, welk algoritme ga je het liefst? De ene daartoe stappen of het neemt die n neemt gedeeld door 31 stappen om een ​​stukje data te vinden of opzoeken wat informatie? Ik bedoel, absoluut de 31 merken een verschil in de echte wereld. Het is 31 keer sneller. En wij mensen zijn zeker gaan waarderen dat. 

Zo realiseren de dichotomie er tussen eigenlijk praten over dingen theoretisch en asymptotisch die zeker heeft waarde zoals we hebben gezien, maar in de echte wereld, als je de zorg over alleen het maken van de mens blij voor algemene ingangen, je zou heel goed willen accepteren dat, ja, is lineair, maar het is 31 keer sneller dan lineair kan zijn. En beter nog, we hebben niet alleen te iets willekeurig doen, zoals een geboortedatum, konden we een beetje door te brengen meer tijd en slimheid en na te denken over wat we zouden kunnen doen, gegeven naam van een persoon en misschien hun geboortedatum die combineren ingrediënten om erachter te komen wat dat is echt meer uniforme en minder jaggy, bij wijze van spreken dan deze foto momenteel suggereert dat het zou kunnen zijn. Hoe kunnen we dit implementeren in de code? Nou, laat ik stel voor dat we gewoon lenen sommige syntax we hebben gebruikt een paar keer tot nu toe. En ik ga om te definiëren een knooppunt opnieuw dat is een generieke term voor slechts enkele container enige datastructuur. Ik ga om te stellen dat een string gaat daar. Maar we gaan beginnen met het nemen opleiders van wielen van nu. 

Niet meer CS50 bibliotheek echt, tenzij je wilt om het te gebruiken voor uw uiteindelijke project, dat is prima, maar nu gaan we terug te trekken het gordijn en zeggen: het is gewoon een char ster. Dus het woord er gaat worden naam van de persoon in kwestie. En nu heb ik een link hier de volgende knoop zodat deze vertegenwoordigen elk van de knooppunten in de keten, eventueel, van een gelinkte lijst. 

En nu hoe doe ik verklaar de hash tabel zelf? Hoe kan ik verklaar deze hele structuur? Nou ja, echt, net als ik vroeger een pointer om alleen het eerste element van een lijst vóór, evenzo kan ik alleen maar zeggen Ik gewoon een stelletje pointers nodig ter uitvoering van deze hele hash table. Ik ga naar een array riep tafel voor hash table. Het zal van de omvang van de capaciteit te zijn. Dat is hoe veel elementen kunnen passen in het. En elk van deze elementen in deze serie gaat een knooppunt ster te zijn. Waarom? Nou, per deze foto, wat ik ben de uitvoering van de hash table als effectief in het begin is gewoon deze array dat we verticaal hebt getekend, elk van wie de pleinen is een pointer. Dat degenen die slashes hebben door hen zijn gewoon null. En degenen die moeten pijlen naar rechts daadwerkelijke verwijzingen naar daadwerkelijke knooppunten ergo het begin van een gelinkte lijst. 

Dus hier is dan ook hoe we zouden kunnen implementeren van een hash table die implementeert aparte chaining. Nu kunnen we beter doen? Oké Ik beloofde vorige keer dat we konden constante tijd te bereiken. En ik soort gaf je constante tijd hier, maar zei toen niet echt constante tijd, want het is nog steeds afhankelijk van de totale aantal elementen je invoeren in de gegevensstructuur. Maar stel dat we dit deden. Laat me teruggaan naar het scherm over hier. Laat me dit ook projecteren hier, duidelijk het scherm, en stel dat ik dit deed. Neem nu dat je de naam in te voegen Daven in in mijn datastructuur. 

Dus ik wil een string te voegen Daven in de datastructuur. Wat als ik geen gebruik maken van een hash table, maar ik gebruik iets dat meer boomachtige als een stamboom, waar heb je een aantal wortels in de top en dan knopen en bladeren dat gaat naar beneden en naar buiten. Veronderstel dan, dat ik wilt Daven's invoegen in wat er is momenteel een lege lijst. Ik ga het volgende doen: ik ben naar een knooppunt maken in dit gezin boomachtige datastructuur die eruit ziet wat dit houdt, die elk rechthoeken is, laten we zeggen, nu 26 elementen daarin. En elk van de cellen in deze array gaat naar de letter van een alfabet vertegenwoordigen. 

Concreet, ik ga behandelen dit is A, dan B, dan C, dan D, deze hier. Dus dit gaat om effectief vertegenwoordigen de letter D. Maar om alle Daven's invoegen noem ik nodig om een ​​beetje meer te doen. Dus ik ga eerst naar hash, zo te zeggen. Ik ga kijken naar de eerste letter in Daven's die uiteraard een D, en ik ga om te wijzen een knooppunt dat eruit ziet als dit-- een grote rechthoek groot voldoende om het gehele alfabet passen. 

Nu D gebeurt. Nu A. D-A-V-E-N is het doel. Dus nu wat ik ga doen is het volgende. Zodra ik begon D kennisgeving er is geen wijzer daar. Het is vuilnis waarden op het moment, of ik kan het initialiseren op null. Maar laat me blijven gaan met Dit idee van het bouwen van een boom. Laat me nog een van deze toe te wijzen knooppunten die 26 elementen in zich heeft. 

En weet je wat? Als dit is gewoon een knoop in het geheugen dat Ik heb met malloc, met behulp van een structuur als we straks zullen zien, Ik ga dit-- doen Ik ga om een ​​pijl te trekken uit het ding dat D beneden vertegenwoordigd deze nieuwe knooppunt. En nu, voor het eerst de volgende brief in naam Daven's, V-- D-A-V-- ik ga om verder te gaan en teken een ander knooppunt als dit, waarbij de V elementen hier, dat we trekken voor instance-- whoops. We zullen niet tekenen daar. Het zal hier gaan. 

Dan gaan we naar beschouw dit als V. zijn En dan naar beneden hier gaan we naar index neer van V in wat we zullen overwegen E. En dan van hier gaan we ga een van deze knooppunten hier. En nu hebben we een vraag om te beantwoorden. Ik moet een of andere manier aan te geven dat we zijn aan het einde van de string Daven. Dus kon ik gewoon laten null. 

Maar wat als we hebben Daven's volledige naam ook, die is, zoals we hebben gezegd, Davenport? Dus wat als Daven is eigenlijk een substring, een prefix van een veel langere reeks? We kunnen niet zomaar permanent zeggen dat er niets gebeurt om daar heen te gaan, want we konden steek nooit een woord als Davenport in deze data Structuur 

Dus wat we konden doen in plaats daarvan is behandelen elk van deze elementen zoals je misschien met twee elementen binnen hen. Eén is een pointer inderdaad zoals ik heb gedaan. Zodat elk van deze dozen niet één cel. Maar wat als de top een-- de onderste's gaan null zijn, omdat er is geen Davenport gewoon nog niet. Wat als de bovenste is een aantal speciale waarde? En het gaat een beetje te zijn moeilijk om het deze grootte te tekenen. Maar stel dat het is gewoon een vinkje. Controleren. D-A-V-E-N is een string in deze datastructuur. 

Ondertussen, als ik meer ruimte hier, kon ik doen P-O-R-T, en ik kon check in de knoop leggen dat heeft de letter T op het einde. Dus dit is een massively complex kijkt datastructuur. En mijn handschrift zeker niet helpen. Maar als ik iets wilde voegen anders, nadenken over wat we zouden doen. Als we wilden David in te zetten, we dezelfde logica, D-A-V zou volgen, maar nu ik zou wijzen in de komende element niet uit E, maar van I tot D. Dus er gaat worden meer knooppunten in deze boom. We gaan bellen malloc meer hebben. Maar ik wil niet een te maken grote puinhoop van deze foto. Dus laten we in plaats daarvan kijken naar een dat is al-pre geformuleerd als dit met niet dot, dot, stippen, maar gewoon afgekort arrays. Maar elk van de knooppunten in deze boom hier vertegenwoordigt dezelfde thing-- een array Ray van grootte 26. 

Of als we willen zijn nu echt een goede, wat Als iemands naam als een apostrof, laten we aannemen dat ieder knooppunt eigenlijk zoals 27 indexen in het, niet alleen 26. Dus dit nu gaat om een ​​data zijn genaamd een trie-- T-R-I-E. Een trie, die zogenaamd historisch gezien een slimme naam voor een boom die is geoptimaliseerd voor ophalen, die natuurlijk wordt gespeld met een I-E dus het is trie. Maar dat is de geschiedenis van de trie. 

Dus een trie is deze boom-achtige data structuur als een stamboom die uiteindelijk gedraagt ​​als dat. En hier is weer een voorbeeld van een hele hoop namen van andere mensen. Maar de vraag is nu bij de hand is wat hebben we hebben opgedaan door de invoering van misschien wel een meer complexe datastructuur, en één, eerlijk gezegd, dat gebruikt veel geheugen. 

Want ook al, op het moment, ik ben alleen met behulp van D's pointer en A en V en Es en Ns, Ik verspil een deurklink van veel geheugen. Maar waar ik doorbrengen één bron, Ik heb de neiging om te doen terug te krijgen een ander. Dus als ik de uitgaven meer ruimte, wat is waarschijnlijk de hoop? Dat ik minder uitgeven wat? Publiek: Minder tijd. DAVID MALAN: Tijd. Waarom zou dat zijn? Nou, wat is het inbrengen tijd qua grote O nu, van een naam als Daven of Davenport of David? Nou, Daven was vijf stappen. Davenport zou zijn negen stappen, dus het zou een paar stappen. David zou vijf stappen ook. Dus dat zijn betonnen aantallen, maar zeker is er een bovengrens voor de lengte van iemands naam. En inderdaad, in het probleem sets van vijf specificatie we gaan voorstellen dat het iets dat is 40-sommige-oneven tekens. 

Realistisch, niemand heeft een oneindig lange naam, dat wil zeggen dat de lengte van een de naam of de lengte van een string kunnen we bepaalde de stand van structuur is misschien wel wat? Het is constant. Right? Het is misschien een grote constante zoals zijn 40 iets, maar is constant. En het heeft geen afhankelijkheid hoeveel andere namen zijn in deze datastructuur. Met andere woorden, als I wilde nu voegen Colton of Gabriel of Rob of Zamyla of Alison of Belinda of enige andere namen van het personeel op deze data structuur, is de looptijd van het invoegen van andere namen zal zijn op alle beïnvloed door hoeveel andere elementen in de datastructuur al? Het is niet. Right? Omdat we effectief gebruik Deze meerlagige hash tabel. En de looptijd van een van deze bewerkingen is niet afhankelijk van het aantal elementen die in de datastructuur of die uiteindelijk gaan om in de gegevensstructuur, maar de lengte van wat specifiek? 

De snaar ingevoegd, die maakt deze asymptotisch constante tijd-- big O van één. En eerlijk gezegd, gewoon in de echte wereld, dit betekent het invoegen naam Daven's neemt als vijf stappen, of Davenport negen stappen, of David vijf stappen. Dat is pretty darn kleine looptijden. En, inderdaad, dat is een zeer goede zaak, vooral wanneer Het is niet afhankelijk van de totale aantal elementen in daar. Dus hoe kunnen we dit implementeren soort structuur in de code? Het is een beetje meer complex, maar toch is het gewoon een toepassing van elementaire bouwstenen. Ik ga om te herdefiniëren Knoop van de VS als volgt: bool genaamd word-- en dit alles onder de noemer. Maar de bool vertegenwoordigt wat ik tekende als een vinkje. Ja. Dit is het einde van een string in deze datastructuur. 

En, natuurlijk, het knooppunt ster Er wordt verwezen naar kinderen. En, inderdaad, net als een stamboom, je zou overwegen de knooppunten die zijn opknoping uit van onder sommige ouder element zijn kinderen. En zodat de kinderen gaat zijn een reeks van 27, 27 één gewoon voor de apostrof. We gaan om te sorteren Een bijzonder geval van dat. Dus u kunt er zeker van zijn namen met apostrof. Misschien zelfs koppelteken moet naar binnen gaan, maar je zult zien in p set 5 we alleen zorg over brieven en apostrof. 

En hoe doe je vertegenwoordigen de datastructuur zelf? Hoe maak je de wortel vertegenwoordigen van deze trie, om zo te zeggen? Nou, net als met een gelinkte lijst, u moet een pointer naar het eerste element. Met een trie je hoeft alleen maar een Pointer naar de wortel van deze trie. En vanaf daar kun je hash je weg naar beneden dieper en dieper met elk ander knooppunt in de structuur. Dus gewoon met dit blikje wij vertegenwoordigen dat struct. 

Meanwhile-- nu Oh, vraag. 

Publiek: Wat is bool woord? 

DAVID MALAN: Bool woord is alleen deze C incarnatie van wat ik beschreef in deze doos hier, wanneer Ik begon het splitsen van elk van de elementen array in twee stukken. Eén is een pointer naar de volgende knoop. De andere moet worden iets als een selectievakje om ja te zeggen, er is een woord Daven dat hier eindigt, omdat we niet willen, op het moment, Dave. 

Hoewel Dave gaat om een ​​te zijn legitiem woord, hij is niet in de trie Nog. En D is niet een woord. En D-A is niet een woord of een naam. Dus het vinkje geeft alleen aan als je eenmaal raakte dit knooppunt is het vorige pad karakters eigenlijk een string die je hebt ingevoegd. Dus dat is al de bool er voor ons doet. 

Alle andere vragen over pogingen? Yeah. 

Publiek: Wat is de overlap? Wat als je een Dave en een Daven? DAVID MALAN: Perfect. Wat als je een Dave en een Daven? Dus als we in te voegen, bijvoorbeeld een bijnaam, voor David-- Dave-- D-A-V-E? Dit is eigenlijk super simpel. Dus we alleen gaan om vier stappen te ondernemen. D-A-V-E. En wat moet ik doen zodra ik raakte dat vierde knooppunt? Gewoon gaan controleren. We zijn al goed om te gaan. Gedaan. Vier stappen. Constante tijd asymptotisch. En nu hebben we aangegeven dat zowel Dave en Daven zijn strings in de structuur. Dus geen probleem. En merk op hoe de aanwezigheid van Daven heeft het niet gehaald neem geen tijd meer of minder tijd voor Dave en vice versa. 

Dus wat kunnen we nu doen? We hebben deze metafoor gebruikt voor trays vertegenwoordigen iets. Maar het blijkt dat een stapel trays eigenlijk demonstratieve van een andere abstracte gegevens type-- een hoger niveau datastructuur dat aan het eind van de dag is gewoon als een array of een gelinkte lijst of iets meer alledaagse. Maar het is een interessantere conceptuele concept. Een stapel, zoals deze trays hier in Mather, algemeen genoemd gewoon dat-- een stapel. 

En dergelijke datastructuur je hebt twee operations-- heb je een zogenaamde push voor iets toe te voegen aan de stapel, als het zetten van een andere lade rug op de top van de stack. En dan pop, wat betekent dat u neem de bovenste lade uit. Maar wat is belangrijk over een stack is dat het heeft deze merkwaardige eigenschap. Zoals de eetzaal personeel zijn herschikken van de laden voor de volgende maaltijd, wat gaat worden waar over hoe studenten interageren met deze datastructuur? Publiek: Ze gaan eenmalige pop. DAVID MALAN: Ze gaan pop one off, hopelijk de top. Anders is het gewoon een soort van domme om helemaal naar de bodem. Right? De datastructuur niet echt toe u naar de onderste lade tenminste grijpen gemakkelijk. Dus er is deze merkwaardige woning naar een stack dat het laatste item in is naar de eerste uit zijn. En computer wetenschappers noemen Dit LIFO-- last in, first out. En het eigenlijk heeft interessante toepassingen. Het is niet per se zo vanzelfsprekend als een aantal anderen, maar het kan inderdaad nuttig, en kan inderdaad worden toegepast in een paar verschillende manieren. 

Zo één, en eigenlijk, laat me niet om te duiken in die. Laten we dit doen in plaats daarvan. Laten we eens kijken naar een die is bijna de Hetzelfde idee, maar het is een beetje eerlijker. Right? Als je een van deze fan jongens of meisjes die echt leuk vindt Apple producten en je werd wakker om 3:00 aan line-up op een bepaald winkel aan de allernieuwste iPhone te krijgen, je zou kunnen hebben in de wachtrij als deze. 

Nu een wachtrij is heel bewust vernoemd. Het is een lijn, want er is sommige eerlijkheid aan. Right? Het zou soort gezogen als je hebt eerst daar aankwam bij de Apple Store maar je bent in feite de onderste lade omdat de Apple-medewerkers dan pop de laatste persoon die eigenlijk kreeg in de rij. Dus stapels en rijen, hoewel functioneel ze zijn soort van de same-- het is gewoon deze collectie van de middelen die gaan groeien en shrink-- er is Deze eerlijkheid aspect aan, althans in de echte wereld, waar de handelingen die u uit te oefenen zijn fundamenteel verschillend. Een stack-- een wachtrij rather-- wordt gezegd dat twee operaties: n rij en d wachtrij. Of je kunt ze bellen een aantal dingen. Maar je wilt vastleggen het idee dat men toevoegt en een uiteindelijk trekken. 

Nu onder de kap zowel de stack en een wachtrij kunnen worden uitgevoerd hoe? We zullen niet in de code van gaan omdat de hogere idee is een soort van meer voor de hand. Ik bedoel, wat doen mensen dat doen? Als ik de eerste persoon op de Apple Slaan en dit is de voordeur, weet je, ik ga hier staan. En de volgende persoon gaan om hier te staan. En de volgende persoon gaan om hier te staan. Wat datastructuur leent zich voor een wachtrij? 

Publiek: Een wachtrij. DAVID MALAN: Nou, een wachtrij. Tuurlijk. Wat anders? 

Publiek: Een gelinkte lijst. 

DAVID MALAN: Een gekoppeld lijst kon implementeren. En een gelinkte lijst is leuk want dan kan willekeurig lang worden tegenstelling om met een aantal vast aantal van de mensen in de winkel. Maar misschien een vast aantal plaatsen is legitiem. Want als ze alleen als 20 iPhones op de eerste dag, misschien ze alleen een array van grootte nodig hebt 20 die wachtrij vertegenwoordigen die is alleen nu te zeggen als we eenmaal beginnen te praten over deze hogere problemen niveau, je kunt het implementeren in een aantal manieren. En er is waarschijnlijk gewoon gaan zijn een afweging in ruimte en tijd of gewoon in uw eigen code complexiteit. 

Hoe zit het met een stapel? Nou, een stapel, we hebben ook gezien kon gewoon zijn deze trays. En je kon dit een array uit te voeren. Maar op een gegeven moment als je een array, wat er gaat gebeuren met de trays je probeert neer te zetten? Prima. Je bent alleen gaat zijn om zo hoog te gaan. En ik denk dat in Mather ze eigenlijk verzonken in die opening. Dus inderdaad, het is bijna zoals Mather wordt met behulp van een array van vaste grootte, want je kunt alleen past zo veel laden in die opening in de muur beneden de knieën van de mensen. En dus dat zou kunnen zijn gezegd dat een array, maar we konden zeker implementeren dat meer in het algemeen met een gekoppelde lijst. 

Nou, wat te denken van een andere datastructuur? Laat me omhoog te trekken een andere visuele hier. Zoiets als hoe dacht je van deze hier? Waarom zou het nuttig zijn om niet over iets zo luxe als een trie, die we zagen hadden deze zeer breed knooppunten, die elk in een array? Maar wat als we iets meer te doen gewoon, net als een oude school stamboom, elk van wie de knooppunten hier wordt gewoon het opslaan van een nummer. In plaats van een naam of een afstammeling wordt gewoon het opslaan van een nummer als dit. 

Nou, het jargon gebruiken we in datastructuren is zowel pogingen en bomen, waarbij een trie, opnieuw, is slechts één waarvan de knopen zijn arrays, is nog steeds wat je misschien Gebruik van de lagere school wanneer je een gezin gemaakt tree-- bladeren en de wortel van de boom en de kinderen van de ouders en broers en zussen daarvan. En we zouden een boom te implementeren, bijvoorbeeld Zo eenvoudig. Een boom, als het als een knoop, een van deze cirkels een getal, het gaat niet om te hebben één wijzer, maar twee. En zodra je toevoegen een tweede wijzer, u kan eigenlijk nu maken soort tweedimensionale data structuren in het geheugen. Net als een tweedimensionale array, kunt u hebben dergelijke tweedimensionale gelinkte lijsten, maar degenen die volgen een patroon waar er geen cycli. Het is echt een boom met een grootouder weg hier en dan omhoog sommige ouders en kinderen en kleinkinderen en achterkleinkinderen. enzovoort. 

Maar wat echt netjes over dit ook, alleen maar om je te plagen met een stukje code, recall recursie uit een tijdje terug, waarbij u een functie die zichzelf aanroept schrijven. Dit is een mooie kans iets implementeren zoals recursie, omdat dit te overwegen. 

Dit is een boom. En ik heb een beetje anale met hoe geweest Ik zette de gehele getallen in de straat. Zozeer zelfs dat het een speciale name-- een binaire zoekboom. Nu hebben we gehoord van binaire zoeken, maar kan je terug te werken uit naam van dit ding? Wat is het patroon van hoe ik ingestoken de gehele getallen in deze boom? Het is niet willekeurig. Er is een bepaald patroon. Yeah. 

Publiek: kleinere aan de linkerkant. 

DAVID MALAN: Yeah. Kleinere zijn aan de linkerkant. Grotere zijn aan de rechterkant. Zodanig dat een ware uitspraak is een ouder groter is dan zijn linkerkind, maar minder dan haar recht kind. En dat alleen is zelfs een recursieve verbale definitie want je kunt toepassen dat Dezelfde logica elk knooppunt en alleen bodems out, een base case als je zal, wanneer u een van hit de bladeren, zogezegd, waar een verlof heeft geen kinderen meer. 

Nu hoe zou u het nummer 44 vinden? Je zou beginnen bij de wortel en zeggen, hm. 55 is geen 44 Dus wil ik gaan rechts of wil ik om links te gaan? Nou, natuurlijk wilt u links gaan. En dus is het net als de telefoon boek bijvoorbeeld in binaire zoekopdracht meer algemeen. Maar we zijn de uitvoering ervan nu een beetje meer dynamisch dan een serie zou kunnen stellen. En in feite, als je wilt kijken bij de code, op het eerste gezicht zeker. Het ziet eruit als een hele hoop van lijnen. Maar het is heel eenvoudig. Als u een functie wilt implementeren riep zoeken waarvan het doel in het leven is het zoeken naar een waarde als n een geheel getal, en je bent geslaagd in een één pointer-- een pointer naar het knooppunt van de wortels, veeleer van die boom waarvan kun je al het andere toegang, merken hoe onomwonden kunt u de logica te implementeren. Als boom is null, uiteraard is het er niet. Laten we gewoon return false. Right? Als je hand het niets, er is niets daar. 

Anders, indien n kleiner dan boom pijl N-- nu arrow n, herinneren we super geïntroduceerd kort op de andere dag, en dat betekent gewoon de-verwijzing de pointer en kijk naar het veld met de naam n. Het betekent dus ga daar en kijk naar het veld met de naam n. Dus als n, de waarde die u hebt opgegeven, is minder dan de waarde in de bomen integer, waar wil je heen? Naar links. 

Dus let op de recursie. Ik ben returning-- niet waar. Niet vals. Ik ben terug, ongeacht het antwoord is van een oproep bij mezelf, het passeren weer een n, die overbodig maar wat is er nu iets anders? Hoe maak ik het probleem kleiner? Ik ben het passeren in de tweede argument, niet de wortel van de boom, maar de linkerkind in dit geval. Dus ik ben het passeren in de linker kind. 

Ondertussen, als n groter is dan de knoop Ik ben momenteel op zoek naar, Ik zoek de rechterkant. Anders, als de structuur niet nul, en Als het element niet naar links en het is niet aan de rechter, wat is er heerlijk het geval? We hebben eigenlijk vond het knooppunt in vraag, en dus hebben we return true. 

Dus we hebben net gekrast de oppervlakte nu een aantal van deze datastructuren. In set probleem vijf u zult staand deze nog verder, en u zult gegeven worden uw ontwerp keuze van hoe om te gaan over dit. Wat ik zou willen besluiten op is slechts een 30 seconden teaser van wat wacht volgende week en verder. 

Zoals we begin-- gelukkig je misschien langzaam think-- onze overgang uit de wereld van C en lager level implementatie details, aan een wereld waarin we kunnen nemen voor vanzelfsprekend dat iemand anders heeft eindelijk geïmplementeerd deze data structuren voor ons, en we beginnen om het te begrijpen echte wereld betekent de uitvoering web-based programma's en websites algemeen en ook het security implicaties die we hebben alleen begonnen om krassen op het oppervlak van. Hier is wat ons te wachten staat in de dagen die komen. 

[VIDEO AFSPELEN] 

-Hij Kwam met een boodschap, met een protocol al zijn eigen. Hij kwam tot een wereld van wrede firewalls, onverschillig routers, en gevaren veel erger dan de dood. Hij is snel. Hij is sterk. Hij is TCP / IP, en hij heeft je adres. "Warriors of the Net." [END VIDEO AFSPELEN] DAVID MALAN: Coming volgende week. Wij zullen u dan zien. [VIDEO AFSPELEN] -En Nu, "Deep Thoughts" door Daven Farnham. -David Begint altijd lezingen met: "Goed." Waarom niet, "Hier is de oplossing om deze week probleem set " of "We geven jullie allemaal een A?" [Lacht] [END VIDEO AFSPELEN]