[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.
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]