[Musikken afspilles]
>> DAVID MALAN: Dette er CS50.
Og det er både begyndelsen og end-- ligesom literally-- næsten enden
af uge seks.
>> Jeg troede, jeg ville dele en lidt af en sjov kendsgerning.
Jeg har trukket det op fra en data forløbne semesters indstillet.
Du husker måske, at vi beder dig om hver p sæt formular, hvis du har set online
eller hvis du har deltaget i person.
Og her er dataene.
Så i dag var meget forudsigelig.
Men vi ønskede at tilbringe en smule af tid sammen med dig alligevel.
Ville nogen gerne formodninger hvorfor dette graf er så jaggy, op ned, op ned,
så konsekvent?
Hvad gør hver af toppene og trug repræsentere?
>> PUBLIKUM: [uhørligt]
DAVID MALAN: Ja.
Og mere underholdende, gud forbyde det, vi holder et foredrag på en fredag
i begyndelsen af ​​semestret, det er, hvad vi ser ske.
Så i dag, vi deltager i en lidt mere om datastrukturer.
Og for at give dig mere af en solid mental model for problemer på fem,
der er nu ude.
Stavefejl, hvor, vil vi hånd du en tekstfil omkring 100.000
plus engelske ord, og du er nødt til
at finde ud af, hvordan man behændigt indlæse dem ind i hukommelsen, i RAM, ved hjælp af nogle data
opbygning af dit valg.
>> Nu en sådan datastruktur kunne være, men burde nok ikke være,
den ret forsimplede linkede liste, som vi introducerede sidste gang.
Og en sammenkædet liste havde mindst en fordel i forhold til et array.
Hvad der er en fordel ved en sammenkædet liste velsagtens?
>> PUBLIKUM: Indsættelse.
>> DAVID MALAN: Indsættelse.
Hvad mener du med det?
>> PUBLIKUM: Anywhere sammen listen [uhørligt].
>> DAVID MALAN: God.
Så du kan indsætte et element, hvor du ønsker i midten af ​​listen
uden at blande noget, som vi konkluderede i vores sortering
diskussioner, er ikke nødvendigvis en god ting,
fordi det tager tid at faktisk bevæge alle disse mennesker til venstre eller højre.
Og så med en linket liste, kan du bare tildele med malloc en ny node,
og derefter opdatere et par pointers-- to, tre operationer max--
og vi er i stand til slot nogen i overalt i en liste.
>> Hvad der ellers var fordelagtig om en sammenkædet liste?
Ja?
>> PUBLIKUM: [uhørligt]
DAVID MALAN: Perfect.
Perfect.
Det er virkelig dynamisk.
Og at du ikke begå, i forvejen, til nogle faste størrelse
luns af hukommelse, ligesom du ville have til med et array, opadrettede som
er, at du kan tildele knuder kun på efterspørgsel og dermed kun bruger så meget plads
som du rent faktisk har brug for.
I modsætning til et array, kan du uheld tildele for lidt.
Og så er det bare at gå at være en smerte i nakken
at omfordele en ny større array, kopiere alt i, befri den gamle array,
og derefter flytte om din virksomhed.
Eller endnu værre, kan du tildele måde mere hukommelse end du rent faktisk har brug for,
og så du kommer til at have en meget tyndt befolkede array, så at sige.
>> Så en sammenkædet liste giver dig disse fordele ved dynamik og fleksibilitet
med indsætninger og sletninger.
Men sikkert skal der være en pris betalt.
Faktisk er en af ​​de temaer udforskes på quiz nul
var et par af de afvejninger vi har set hidtil.
Så hvad er en pris, der betales eller en Ulempen ved en linket liste?
Ja.
>> PUBLIKUM: Ingen random access.
>> DAVID MALAN: Ingen random access.
Men hvem bekymrer sig?
Random access lyder ikke overbevisende.
>> PUBLIKUM: [uhørligt]
DAVID MALAN: Præcis.
Hvis du vil have en vis algorithm--
og lad mig faktisk foreslå søgning binær især som
er en vi har brugt en hel bit-- hvis du ikke har random access,
du kan ikke gøre det simple aritmetiske finde ligesom den midterste element
og hoppe ret til det.
Du i stedet nødt til at starte på det første element og lineært søge fra venstre
til højre, hvis du ønsker at finde midten eller noget andet grundstof.
>> PUBLIKUM: Det tager nok mere hukommelse.
>> DAVID MALAN: Tager mere hukommelse.
Hvor er det ekstra koste kommer fra i hukommelsen?
>> PUBLIKUM: [uhørligt]
DAVID MALAN: Præcis.
I dette tilfælde her, havde vi en sammenkædet liste for heltal,
og alligevel er vi fordobling mængden af ​​hukommelse
vi har brug for ved også at opbevare disse pejlemærker.
Nu mindre af en big deal som dine structs får større
og du lagre ikke et nummer, men måske en studerende eller en anden genstand.
Men punktet bestemt tilbage.
Og så en række af de aktioner, om hægtede lister blev kaldt
var store O n- lineær.
Ting som indsættelse eller søg eller sletning i tilfælde et element
tilfældigvis i slutningen af listen uanset om det er sorteret eller ej.
>> Nogle gange kan du få heldig og i så nedre grænser på disse operationer
kunne også være konstant tid, hvis du er altid kigger på det første element,
f.eks.
Men i sidste ende, vi lovede at opnå den hellige gral
datastrukturer, eller vis tilnærmelse deraf
ved konstant tid.
Kan vi finde elementer eller tilføje elementer eller fjerne elementer fra en liste?
Vi skal se meget snart.
Og det viser sig, at en af de mekanismer, vi er
vil begynde at bruge i dag, årlige forbrug i p sæt fem,
er faktisk temmelig bekendt.
For eksempel, hvis dette er en flok eksamensspørgsmål bøger, som hver
har en elevs første navn og efternavn på den,
og jeg hente dem fra ved slutningen af ​​en eksamen,
og de er alle temmelig meget i en tilfældig rækkefølge,
og vi ønsker at gå om sortering disse eksamener, så engang sorteres
det er bare meget nemmere og hurtigere at udlevere dem ud igen
til studerende alfabetisk.
Hvad ville dine instinkter være for en bunke af eksamener som denne?
>> Tja, hvis du er ligesom mig, du kunne se, at dette er m,
så jeg har tænkt mig at slags sætte det i, hvis dette er mit bord eller min etage, hvor
Jeg sprede tingene out-- eller min opstilling really--
Jeg kunne sætte alle MS i der.
Oh.
Her er en A. Så jeg måske sætte Som herovre.
Oh.
Her er en anden A. Jeg har tænkt mig at sætte det herovre.
Her er en Z. Her er en anden M. Og så Jeg kunne begynde at gøre bunker som denne.
Og så måske jeg vil gå i senere og sortering af meget nitpicky-ly slags
de enkelte pæle.
Men pointen er, at jeg ville se ved indgangen, at jeg er handed
og jeg ville gøre nogle beregnede beslutning baseret på denne indgang.
Hvis den begynder med A, sætte det derovre.
Hvis den begynder med Z, sætte det over der, og alt derimellem.
>> Så dette er en teknik, der er almindeligt kendt som hashing-- H-A-S-H--
hvilket generelt betyder at tage som input og bruge dette input til at beregne
en værdi, der generelt er et tal, og at nummer er indekset i et lager
beholder, som et array.
Så med andre ord, kunne jeg have en hash-funktionen, som jeg gør i mit hoved,
at hvis jeg ser nogen er navn, der starter med A,
Jeg har tænkt mig at kortlægge det til nul i mit hoved.
Og hvis jeg ser en person med Z, jeg er kommer til kort, der til 25 i mit hoved
og derefter sætte det ind sidste mest bunken.
>> Nu, hvis du tænker over ikke min hjerne men et C-program, hvilke numre kunne
du stole på at opnå det samme resultat?
Med andre ord, hvis du havde ASCII A,
hvordan kan du bestemme hvad spand at sætte det i?
Du har sandsynligvis ikke ønsker at sætte det ind i spand 65, som
ville være ligesom derovre uden god grund.
Hvor vil du sætte A i form af dens ASCII værdi?
Hvor vil du gøre for at dens ASCII værdi at komme op med en smartere spand
at sætte det i?
>> PUBLIKUM: Minus A.
>> DAVID MALAN: Ja.
Så minus A eller minus specifikt 65, hvis det er
en kapital A. Eller 98, hvis det er et lille et.
Og så ville tillade os at, meget enkelt og meget aritmetisk
sætte noget i en spand som.
Så det viser sig, vi rent faktisk gør det så godt selv med quizzer.
>> Så du kan huske du kredsede din undervisning fyrs navn på omslaget.
Og TF navne var organiseret i disse kolonner alfabetisk,
godt, tro det eller ej, når alle 80 plus os
fik sammen den anden aften til lønklasse, det sidste trin i vores grading proces
er at hash quizzer ind i en stor rum etage på [uhørligt]
og lægge alles quizzer ud i nøjagtig den rækkefølge, deres TF s
navne på dækslet, da så er det meget lettere for os
at søge gennem at anvendelse af lineær søge eller anden form for klogskab
til TF at finde hans eller hendes studerendes quizzer.
>> Så denne idé om hashing at du vil se, er
ganske stærke er faktisk temmelig banal og meget intuitiv,
ligesom måske opdele og erobring var i uge nul.
Jeg hurtigt frem til hackathon et par år siden.
Dette var Zamyla og et par andre ansatte hilsen studerende
som de kom ind.
Og vi havde en hel bunke af foldning tabeller der med navneskilte.
Og vi havde navneskilte organiseret med ligesom Som derovre
og Zs derovre.
Og så en af ​​TFS meget behændigt skrev dette som instruktioner
for dagen.
Og i uge 12 af semestret dette alle gav god mening, og alle
vidste, hvad de skal gøre.
Men når du har kø på samme måde,
du gennemføre samme forestilling om en hash.
Så lad os formalisere det en lille smule.
Her er et array.
Det er udarbejdet til at være lidt bred bare at skildre, visuelt,
at vi kan sætte strenge i noget som dette.
Og dette array er tydeligt af størrelse 26 total.
Og de ting kaldes tabel vilkårligt.
Men dette er blot en kunstners gengivelse af, hvad en hash tabel kan være.
>> Så en hashtabel nu kommer til at være et højere niveau datastruktur.
Ved slutningen af ​​dagen vi er ved at se, at du
kan gennemføre en hash tabel, som er meget ligesom check-in-line
ved en hackathon meget som denne Tabellen, der anvendes til sortering eksamen bøger.
Men en hash tabel er art af det høje
koncept, der kunne bruge et array under hætten til at gennemføre den,
eller det kunne bruge en liste længde, eller endog måske nogle andre datastrukturer.
Og nu det er den theme-- udtagning nogle af disse grundlæggende ingredienser
som en matrix, og denne bygning blokere nu en liste længde
og se, hvad vi ellers kan bygge på toppen af ​​dem, ligesom ingredienser
i en opskrift, så mere og mere interessante og nyttige endelige resultater.
>> Så med hash tabellen vi måske gennemføre den
i hukommelsen billedligt som denne, men hvordan kan det faktisk være kodet op?
Nå, måske så enkelt er det.
Hvis kapacitet i alle kasketter, er bare nogle constant-- for eksempel 26,
for 26 bogstaver i det alphabet-- Jeg kunne kalde min variabel bord,
og jeg kunne påstå, at jeg har tænkt mig at sætte char stjerner derinde, eller snor.
Så det er så simpelt som dette, hvis du ønsker at gennemføre en hash tabel.
Og dog, det er virkelig bare et array.
Men igen, en hash Tabellen er nu, hvad vi får
kalder en abstrakt datatype, der er bare sortering af en begrebsmæssig lagdeling på toppen
af noget mere prosaisk Nu vil et array.
>> Nu, hvordan gør vi gå om at løse problemer?
Tja, tidligere havde jeg den luksus for at have nok bordplads her
så jeg kunne sætte quizzer overalt jeg ønskede.
Så kan gå her.
Zs kan gå her.
Ms kan gå her.
Og så havde jeg nogle ekstra plads.
Men det er lidt af en snyde ret nu, fordi denne tabel, hvis jeg virkelig
tænkte på det som et array, er bare kommer til at være af en vis fast størrelse.
>> Så teknisk set, hvis jeg trækker op en anden elevs quiz
og se, åh, denne persons navn starter med et A også,
Jeg slags ønsker at sætte det der.
Men så snart jeg sætte det der, hvis denne tabel faktisk udgør et array,
Jeg har tænkt mig at være tvingende eller clobbering hvem denne studerendes quiz er.
Right?
Hvis dette er et array, kun én ting kan gå i hver af disse celler eller elementer.
Og så jeg har slags at vælge og vrage.
>> Nu jeg tidligere slags snydt og gjorde dette eller jeg
lige slags stablet dem over hinanden.
Men det kommer ikke til at flyve i koden.
Så hvor kan jeg sætte anden elev, hvis navn
er A, hvis alt havde jeg er dette tilgængelig tabel plads?
Og jeg har brugt tre slots og det ser ud der er bare et par andre.
Hvad kunne du gøre?
PUBLIKUM: [uhørligt]
DAVID MALAN: Ja.
Måske lad os bare holde det simpelt.
Right?
Det passer ikke, hvor jeg ønsker at sætte det.
Så jeg har tænkt mig at sætte det teknisk hvor B ville gå.
Nu, selvfølgelig, er jeg begyndt at male mig op i et hjørne.
Hvis jeg kommer til en elev hvis navn er faktisk B,
nu B vil blive flyttet lidt fremad, som kunne ske, jep,
hvis dette er et B, nu er det at gå her.
>> Og så dette meget hurtigt kan blive problematisk,
men det er en teknik, der faktisk betegnes som lineær probing,
hvorved du lige overveje din array til at være langs linien.
Og du bare slags sonde eller inspicere hver tilgængelig element
på udkig efter en ledig plet.
Og så snart du finder en, du skulle tabe det derinde.
>> Nu, idet den betalte pris nu denne løsning er hvad?
Vi har en fast størrelse array, og når jeg sætter navne
i det mindste i begyndelsen, hvad er køretiden for indsættelse
for at sætte de studerende quizzer i de rigtige spande?
Big O i hvad?
>> PUBLIKUM: n.
DAVID MALAN: Jeg hørte store O n.
Ikke sandt.
Men vi vil drille hinanden hvorfor i bare et øjeblik.
Hvad ellers kunne det være?
>> PUBLIKUM: [uhørligt]
DAVID MALAN: Og lad mig gøre det visuelt.
Så formoder, det er bogstavet S.
>> PUBLIKUM: Det er én.
DAVID MALAN: Det er én.
Right?
Dette er et array, som betyder, at vi har random access.
Og hvis vi tænker på dette som nul og dette som 25,
og vi indser, at, åh, her er mit input S,
Jeg kan helt sikkert konvertere S, en ASCII-tegn,
til et tilsvarende antal mellem nul og 25
og derefter straks sætte det, hvor det hører hjemme.
>> Men selvfølgelig, så snart jeg kommer til anden person, der er navn er A, B eller C
til sidst, hvis jeg har brugt den lineær sondering som min løsning,
køretiden for indsættelse i værste fald
rent faktisk vil udvikle sig til hvad?
Og jeg hørte det her korrekt tidligt.
PUBLIKUM: [uhørligt]
DAVID MALAN: Så det er n faktisk en gang du har et tilstrækkeligt stort datasæt.
Så på den ene side, hvis dit array er stor nok
og dine data er sparsomme nok, du få denne smukke konstant tid.
Men så snart du begynder at få flere og flere elementer,
og bare statistisk får du flere mennesker med bogstavet
A som deres navn eller bogstavet B, det kunne potentielt
udvikle sig til noget mere lineær.
Så ikke helt perfekt.
Så kunne vi gøre bedre?
>> Nå, hvad var vores løsning før, når vi
ønsker at have mere dynamik end noget som et array tilladt?
PUBLIKUM: [uhørligt]
DAVID MALAN: Hvad gjorde vi præsentere?
Ja.
Så en sammenkædet liste.
Nå, lad os se, hvad en sammenkædet Listen kan gøre for os i stedet.
Nå, lad mig foreslå, at vi tegne billedet som følger.
Nu er det en anden billede fra et eksempel
fra en anden tekst, faktisk, at er faktisk ved hjælp af en vifte af størrelse 31.
Og denne forfatter simpelthen besluttede at hash strings
ikke er baseret på personens navn, men baseret på deres fødselsdage.
Uafhængigt af den måned, de regnede hvis du er født den første i en måned
eller den 31. i en måned, forfatteren vil hash baseret på denne værdi,
således at sprede navne en smule mere end blot 26 spots kunne give.
Og måske er det en smule mere ensartet end at gå med alfabetiske bogstaver,
fordi selvfølgelig er der sandsynligvis flere mennesker i verden med navne
at starte med A end sikkert nogle andre bogstaver i alfabetet.
Så måske det er lidt mere ensartet, antager
en ensartet fordeling babyer over en måned.
>> Men, selvfølgelig, det er stadig ufuldkommen.
Right?
Vi skal have kollisioner.
Flere mennesker i denne datastruktur er stadig
har den samme fødselsdato mindst du er uanset måned.
Men hvad har forfatteren gjort?
Tja, det ser ud til vi har en array på den venstre side trukket vertikalt,
men det er bare en kunstners gengivelse.
Det er ligegyldigt, hvilken retning du tegne et array, er det stadig et array.
Hvad er dette en række tilsyneladende?
>> PUBLIKUM: Linked listen.
>> DAVID MALAN: Ja.
Det ligner det er en vifte af linkede liste.
Så igen, at dette punkt i form anvende disse datastrukturer nu
som ingredienser til mere interessante løsninger,
du kan absolut tage en grundlæggende som et array,
og derefter tage noget mere interessant som en sammenkædet liste
og endda kombinere dem til et endnu mere interessant datastruktur.
Og ja, dette også ville kaldes en hash tabel,
hvorved array er virkelig hash tabellen,
men at hash bordet har kæder, så at sige,
der kan vokse eller skrumpe baseret på Antallet af elementer, du vil indsætte.
>> Nu derfor, hvad er køretiden nu?
Hvis jeg ønsker at indsætte nogen hvis fødselsdag er den 31. oktober
hvor er han eller hun gå?
Ok.
Nederst, hvor der står 31.
Og det er perfekt.
Det var konstant tid.
Men hvad nu, hvis vi finder en anden hvis fødselsdag er, lad os se,
Oktober, november, 31. December?
Hvor er han eller hun kommer til at gå?
Samme ting.
To skridt selv.
Det er konstant dog er det ikke?
Ok.
I øjeblikket er det.
Men i det generelle tilfælde, jo flere mennesker, vi tilføjer,
probalistisk, vil vi for at få flere og flere kollisioner.
>> Nu er det en lille bedre, fordi teknisk
nu er mine kæder kunne være i værste fald hvor længe?
Hvis jeg indsætter n folk ind i denne mere sofistikeret datastruktur, n mennesker,
i værste fald kommer til at være n.
Hvorfor?
>> PUBLIKUM: Fordi hvis alle har samme fødselsdag,
de kommer til at være en linje.
DAVID MALAN: Perfect.
Det kan være en smule konstruerede, men virkelig i værste fald
hvis alle har samme fødselsdag, givet de indgange, du har,
du kommer til at have en massivt lang kæde.
Og så kan du kalde det en hash tabellen, men det er virkelig
blot en massiv forbundet liste med en hel masse spildplads.
Men generelt, hvis vi antager, at mindst fødselsdage er uniform--
og er det sandsynligvis ikke.
Jeg gør det op.
Men hvis vi antager, for af hensyn til diskussion
at de er, så i teorien, hvis dette er den lodrette repræsentation
af array, ja så forhåbentlig er du vil få kæder, der er, du kender,
omtrent den samme længde, hvor hver af disse repræsenterer en dag i måneden.
>> Nu, hvis der er 31 dage i måneden, det betyder min køretid virkelig
er stor O n over 31, som føles bedre end lineær.
Men hvad var en af ​​vores forpligtelser et par uger
siden, når det kom til at udtrykke køretiden for en algoritme?
Bare kun se på den høje orden sigt.
Right?
31 er absolut nyttige.
Men det er stadig big O n.
Men en af ​​de temaer, af problem sæt fem
vil være til anerkender, at absolut,
asymptotisk, teoretisk denne datastruktur
er ikke bedre end bare en massiv linkede liste.
Og ja, i værste fald, dette hash tabel kan udvikle sig til det.
>> Men i den virkelige verden, med os mennesker at egne Mac eller pc eller hvad
og kører virkelige verden software på virkelige verden data
hvilken algoritme vil du foretrække?
Den ene, der tager de endelige skridt eller den en, der tager n divideret med 31 trin
at finde nogle stykke af data, eller at slå op nogle oplysninger?
Jeg mener, absolut de 31 mærker en forskel i den virkelige verden.
Det er 31 gange hurtigere.
Og vi mennesker er helt sikkert vil forstå, at.
>> Så indser dikotomien der mellem faktisk
taler om ting, teoretisk og asymptotisk som definitivt
har værdi som vi har set, men i den virkelige verden,
hvis du interesserer bare gøre human glad for generelle input,
du kan meget vel ønsker at acceptere den kendsgerning, at ja, det er lineær,
men det er 31 gange hurtigere end lineær kunne være.
Og bedre endnu, vi ikke bare nødt til at gøre noget vilkårlig som en fødselsdato,
vi kunne bruge lidt mere tid og dygtighed
og tænke over, hvad vi kan gøre, givet en persons navn og måske
deres fødselsdato at kombinere de ingredienser til at finde ud af noget
der er virkelig mere ensartet og mindre jaggy,
så at sige end dette billede i øjeblikket tyder det kunne være.
Hvordan kunne vi gennemføre dette i koden?
Nå, lad mig foreslå, at vi bare låne nogle syntaks vi har
brugt et par gange hidtil.
Og jeg har tænkt mig at definere en knude, som igen
er en generisk betegnelse for blot nogle container for nogle datastruktur.
Jeg har tænkt mig at foreslå, at en streng går derind.
Men vi kommer til at begynde at tage dem uddannelse hjul off nu.
>> Ikke mere CS50 bibliotek virkelig, medmindre du ønsker
at bruge det til din endelige projekt, hvilket er fint,
men nu vil vi trække sig tilbage gardin og siger, det er bare en char stjerne.
Så ordet der vil være personens navn pågældende.
Og nu har jeg et link her til den næste node
således at disse repræsenterer hvert af knudepunkterne
i kæden potentielt af en sammenkædet liste.
>> Og nu, hvordan gør jeg erklærer hash tabellen selv?
Hvordan kan jeg erklære hele denne struktur?
Nå, virkelig, ligesom jeg brugte en pointer til blot det første element i en liste
før, ligeledes kan jeg bare sige Jeg skal bare have en masse pointers
at gennemføre hele denne hash tabel.
Jeg har tænkt mig at have et array kaldet bord til hash tabellen.
Det kommer til at være på størrelse kapacitet.
Det er, hvor mange elementer kan passe ind i det.
Og hver af disse elementer i dette array vil være en node stjerne.
Hvorfor?
Nå, per dette billede, hvad jeg gennemførelse af hash tabellen som
effektivt i starten er bare dette array, som vi har trukket vertikalt,
hver af hvis firkanter betegner en pointer.
At dem, der har skråstreger gennem dem er lige nul.
Og dem, der har pile der går til højre
er faktiske henvisninger til faktiske noder, ergo starten på en sammenkædet liste.
>> Så her er så, hvordan vi kan gennemføre en hash tabel,
implementerer særskilt chaining.
Nu kan vi gøre bedre?
Okay jeg lovede sidste gang, vi kunne opnå konstant tid.
Og jeg slags gav dig konstant tid her,
men så sagde ikke rigtig konstant tid, fordi det er stadig
afhængig af den totale antallet af elementer
du indtaster ind datastrukturen.
Men formoder, at vi gjorde dette.
Lad mig gå tilbage til skærmen herovre.
Lad mig også projicere det op her, klar skærmen, og formoder jeg gjorde dette.
Antag jeg ønskede at indsætte navnet Daven i ind i min datastruktur.
>> Så jeg ønsker at indsætte en streng Daven i datastrukturen.
Hvad hvis jeg ikke bruger en hash tabellen, men jeg bruger
noget, der er mere trælignende ligesom et stamtræ, hvor
du har nogle rod på toppen og derefter knudepunkter og blade
at gå nedad og udad.
Antag derefter, at jeg vil indsætte Daven s
i, hvad der er i øjeblikket en tom liste.
Jeg har tænkt mig at gøre følgende: Jeg er vil skabe et knudepunkt i denne familie
trælignende datastruktur, der ser lidt ligesom dette, som hver
rektangler har, lad os sige, for nu 26 elementer i det.
Og hver af cellerne i dette array går
at repræsentere bogstav i et alfabet.
>> Konkret vil jeg behandle dette er A, så B, og C, og D,
denne ene her.
Så det kommer til at effektivt repræsenterer bogstavet D.
Men at indsætte alle Daven s navn, jeg er nødt til at gøre lidt mere.
Så jeg først kommer til hash, så at sige.
Jeg har tænkt mig at kigge på det første bogstav i Daven s hvilket naturligvis er en D,
og jeg har tænkt mig at tildele en knude, der ser
ligesom denne-- en stor rektangel big nok til at passe til hele alfabetet.
>> Nu D er færdig.
Nu A. D-A-V-E-N er målet.
Så nu, hvad jeg har tænkt mig at gøre, er dette.
Så snart jeg begyndte D varsel der er ingen pointer der.
Det er skrald værdier i øjeblikket, eller jeg kunne initialisere den til null.
Men lad mig holde i gang med denne idé om at bygge et træ.
Lad mig tildele endnu en af ​​disse noder, der har 26 elementer i det.
>> Og ved du hvad?
Hvis dette er bare en knude i hukommelsen som Jeg oprettede med malloc, ved hjælp af en struct
som vi snart vil se, Jeg har tænkt mig at gøre denne--
Jeg har tænkt mig at tegne en pil fra de ting, der repræsenterede D ned
til denne nye knudepunkt.
Og nu, først den næste brev i Daven navn,
V-- D-A-V-- Jeg har tænkt mig at gå videre og tegne en anden node som dette,
hvorved V elementer her, som vi vil trække for instance-- hovsa.
Vi vil ikke trække der.
Det kommer til at gå her.
>> Så vi kommer til at anser dette for at være V.
Og derefter ned her vi kommer til indeks ned fra V ind i, hvad vi vil overveje E.
Og så herfra vil vi gå have en af ​​disse knudepunkter her.
Og nu har vi et spørgsmål at besvare.
Jeg har brug for en eller anden måde viser, at vi er ved enden af ​​strengen Daven.
Så jeg kunne bare lade det null.
>> Men hvad hvis vi har Daven s fulde navn også, som
er, som vi har sagt, Davenport?
Så hvad nu hvis Daven er faktisk en understreng,
et præfiks af en meget længere snor?
Vi kan ikke bare permanent siger ingenting kommer
at gå der, fordi vi kunne aldrig indsætte et ord ligesom Davenport
i denne datastruktur
>> Så hvad vi kunne gøre i stedet er behandle hvert af disse elementer
som måske har to elementer inde i dem.
Den ene er en pointer, ja, som jeg har gjort.
Så hver af disse kasser er ikke blot en celle.
Men hvad nu, hvis top en-- bunden ens
kommer til at være nul, fordi der er ingen Davenport endnu.
Hvad hvis den øverste er nogle særlige værdi?
Og det kommer til at være lidt svært at tegne det denne størrelse.
Men formoder, det er bare et flueben.
Tjek.
D-A-V-E-N er en streng i denne datastruktur.
>> I mellemtiden, hvis jeg havde mere plads her, jeg kunne gøre P-O-R-T,
og jeg kunne sætte check i knudepunktet der har bogstavet T til allersidst.
Så dette er et massivt kompleks udseende datastruktur.
Og min håndskrift bestemt ikke hjælpe.
Men hvis jeg ønskede at indsætte noget andet, overveje, hvad vi ville gøre.
Hvis vi ønskede at sætte David i, vi ville følge den samme logik, D-A-V,
men nu vil jeg gerne i den næste element ikke fra E, men fra I til D.
Så der vil være flere knuder i træet.
Vi kommer til at have opkald malloc mere.
Men jeg ønsker ikke at lave en komplet rod af dette billede.
Så lad os i stedet se på en der er blevet præ-formuleret
som dette med ikke dot, dot, prikker, men blot forkortede arrays.
Men hver af knudepunkterne i dette træ op her
repræsenterer den samme thing-- et array Ray størrelse 26.
>> Eller hvis vi ønsker at være virkelig ordentlig nu, hvad
hvis en persons navn som en apostrof, lad os
antager, at hvert knudepunkt har faktisk ligesom 27 indekser i den, ikke bare 26.
Så det nu kommer til at være en data struktur, der kaldes en trie-- T-R-I-E.
En trie, som er angiveligt historisk set et smart navn til et træ
der er optimeret til hentning, hvilket naturligvis,
staves med et I-E, så det er trie.
Men det er historien om trie.
>> Så en trie er dette træ-lignende data struktur som et stamtræ
der i sidste ende opfører sig sådan.
Og her er bare endnu et eksempel på en hel masse andre folks navne.
Men spørgsmålet er nu ved hånden er det har
vi opnået ved at indføre velsagtens en mere kompliceret datastruktur, og en,
helt ærligt, der bruger en masse hukommelse.
>> Fordi selvom, i det øjeblik, jeg er kun
ved hjælp af D's pointer og A og V og Es og Ns,
Jeg spilder en dælen af ​​meget hukommelse.
Men hvor jeg tilbringer en ressource, Jeg har tendens til at gøre vinde tilbage en anden.
Så hvis jeg bruger mere plads, hvad er sandsynligvis det håb?
At jeg bruger mindre hvad?
PUBLIKUM: Mindre tid.
DAVID MALAN: Time.
Nu hvorfor kan det være?
Nå, hvad er indsættelsen tid, i form af store O nu
af et navn som Daven eller Davenport eller David?
Nå, Daven var fem trin.
Davenport ville være ni trin, så det ville være et par flere trin.
David ville være fem skridt så godt.
Så dem er konkrete tal, men mon der er
en øvre grænse for længden af ​​en persons navn.
Og ja, i det problem sæt af fem specifikation
vi kommer til at foreslå at det er noget
der er 40-nogle-ulige tegn.
>> Realistisk set ingen har en uendelig lang navn,
hvilket vil sige, at længden af ​​en navn eller længden af ​​en streng vi måske
har visse tilstand struktur er det nok?
Det er konstant.
Right?
Det kan være en stor konstant ligesom 40 noget, men det er konstant.
Og det har ingen afhængighed af hvor mange andre navne er i denne datastruktur.
Med andre ord, hvis I ville nu indsætte
Colton eller Gabriel eller Rob eller Zamyla eller Alison eller Belinda eller andre navne
fra personalet i disse data struktur, er køretiden
indsætte andre navne vil være på alle påvirket
ved hvor mange andre elementer er i data, der allerede struktur?
Det er det ikke.
Right?
Fordi vi er effektivt ved hjælp af denne multi-lag hashtabel.
Og køretiden for nogen af ​​disse operationer
afhænger ikke af antallet af elementer, der er i datastrukturen
eller som i sidste ende går at være i datastrukturen,
men af ​​længden af ​​hvad der specifikt?
>> Strengen er indsat, hvilket gør
dette asymptotisk konstant time-- store O i én.
Og helt ærligt, bare i den virkelige verden, det
betyder indsættelse Daven navn tager ligesom fem trin, eller Davenport ni
trin eller David fem trin.
Det er temmelig darn små køretider.
Og, ja, det er en meget god ting, især når
det er ikke afhængig af den totale antallet af elementer i der.
Så hvordan kan vi gennemfører dette form for struktur i koden?
Det er lidt mere kompleks, men det er stadig
blot en anvendelse af grundlæggende byggesten.
Jeg har tænkt mig at omdefinere os node på følgende måde:
bool kaldet word-- og dette kunne kaldes noget.
Men bool repræsenterer hvad jeg tegnede som en markering.
Ja.
Dette er afslutningen af ​​en streng i denne datastruktur.
>> Og naturligvis knudepunktet stjerne der henviser til børn.
Og, ja, ligesom et stamtræ, du
ville overveje knudepunkterne der hænger ud
af bunden af ​​nogle forælder element til at være børn.
Og så børnene kommer til at være en vifte af 27 den 27. ene
bare at være for apostrof.
Vi kommer til at sortere af særtilfælde det.
Så du kan have en vis navne med apostrof.
Måske endda bindestreg bør gå derind, men du vil
se i p sæt 5 vi kun pleje om bogstaver og apostroffer.
>> Og så hvordan gør du repræsenterer datastrukturen selv?
Hvordan du repræsenterer roden af denne trie, så at sige?
Nå, bare gerne med en linket liste, du brug for en pointer til det første element.
Med en trie du bare har brug for en pointer til roden af ​​denne trie.
Og derfra kan du hash din vej ned dybere og dybere
til hver andet knudepunkt i strukturen.
Så blot med denne dåse vi repræsenterer, at struct.
>> Nu Meanwhile-- Åh, spørgsmål.
>> PUBLIKUM: Hvad er bool ord?
>> DAVID MALAN: Bool ord er netop dette C inkarnation
af hvad jeg beskrev i denne ramme, når
Jeg begyndte at opdele hver af de array-elementer i to stykker.
Den ene er en pointer til den næste node.
Den anden skal være noget som et afkrydsningsfelt
til at sige ja, der er en Ordet Daven der ender her,
fordi vi ikke ønsker, i øjeblikket, Dave.
>> Selvom Dave vil være en legitime ord, han er ikke i trie
endnu.
Og D er ikke et ord.
Og D-A er ikke et ord eller et navn.
Så markeringen angiver kun, når du
ramt dette knudepunkt er tidligere sti tegn
faktisk en streng, som du har indsat.
Så det er alle de bool der gør for os.
>> Alle andre spørgsmål om forsøg?
Ja.
>> PUBLIKUM: Hvad er overlap?
Hvad hvis du har en Dave og en Daven?
DAVID MALAN: Perfect.
Hvad hvis du har en Dave og en Daven?
Så hvis vi indsætter, siger et kaldenavn, for David-- Dave-- D-A-V-E?
Dette er faktisk super enkel.
Så vi kun kommer til at tage fire trin.
D-A-V-E. Og hvad skal jeg gøre, når jeg ramte det fjerde node?
Bare for at kontrollere.
Vi er allerede gode til at gå.
Udført.
Fire trin.
Konstant tid asymptotisk.
Og nu har vi angivet, at både Dave og Daven er strenge i strukturen.
Så ikke et problem.
Og bemærk, hvordan tilstedeværelsen af Daven ikke gøre det
tage noget mere tid eller mindre tid for Dave og vice versa.
>> Så hvad andet kan vi nu gøre?
Vi har brugt denne metafor før bakker repræsenterer noget.
Men det viser sig, at en stablen af ​​bakker er faktisk
demonstrative af en anden abstrakt data Motortype- et højere niveau datastruktur
at der ved udgangen af ​​dagen er bare som en matrix eller en sammenkædet liste
eller noget mere prosaisk.
Men det er en mere interessant konceptuelle koncept.
En stak, som disse bakker her i Mather,
kaldes generelt bare at-- en stak.
>> Og i denne type datastruktur du har to operations--
du har en kaldet fremstød for tilføje noget til stakken,
som at sætte en anden bakke tilbage på toppen af ​​stakken.
Og derefter pop, hvilket betyder, at du tage den øverste bakke off.
Men hvad er nøglen omkring en stak, er, at det har fået denne besynderlige egenskab.
Som den spisesal personale er omarrangere bakker til det næste måltid,
hvad der kommer til at være sandt om, hvordan de studerende
interagere med denne datastruktur?
PUBLIKUM: De kommer til at poppe en off.
DAVID MALAN: De kommer til at poppe en off, forhåbentlig toppen.
Ellers er det bare lidt dum at gå hele vejen til bunden.
Right?
Datastrukturen ikke rigtig tillade dig at få fat den nederste bakke i det mindste
let.
Så der er denne besynderlige ejendom til en stak
at det sidste element i er vil være den første ud.
Og dataloger kalder dette LIFO-- vare ind, først ud.
Og det faktisk har interessante anvendelser.
Det er ikke nødvendigvis så indlysende, som nogle andre, men det kan faktisk være nyttigt,
og det kan faktisk implementeres i et par forskellige måder.
>> Så en, og faktisk, lad mig ikke at dykke ned i det.
Lad os gøre det i stedet.
Lad os se på en, der er næsten samme idé, men det er lidt mere retfærdig.
Right?
Hvis du er en af ​​disse fan drenge eller piger, der virkelig kan lide Apples produkter
og du vågnede op på 3:00 at line op på nogle butik
at få det nyeste iPhone, du kunne have kø som denne.
>> Nu er en kø er meget bevidst navngivet.
Det er en linje, fordi der er nogle retfærdighed til det.
Right?
Det ville suges slags, hvis du har fik der først på Apple Store
men du er faktisk det nederste bakke, fordi Apple ansatte derefter
pop den sidste person, der faktisk fik i linje.
Så stakke og køer, selv om der funktionelt de er slags af same--
det er bare denne samling af ressourcer, som er
kommer til at vokse og shrink-- der er denne fairness aspekt til det,
i det mindste i den virkelige verden, hvor operationerne du motionerer
er fundamentalt forskellige.
En stack-- en kø rather-- siges at have
to operationer: n kø og d kø.
Eller du kan ringe til dem en række ting.
Men du blot ønsker at fange det begreb, at man tilføjer
og man er i sidste ende at subtrahere.
>> Nu under hætten, både stakken og en kø kan gennemføres hvordan?
Vi vil ikke gå ind i koden for det, fordi det højere niveau
Ideen er slags mere indlysende.
Jeg mener, hvad gør mennesker gør?
Hvis jeg er den første person på Apple Opbevar og det er hoveddøren,
du ved, jeg har tænkt mig at stå her.
Og den næste person kommer til at stå her.
Så hvad datastruktur egner sig til en kø?
>> PUBLIKUM: En kø.
DAVID MALAN: Tja, en kø.
Sure.
Hvad ellers?
>> PUBLIKUM: En linkede liste.
>> DAVID MALAN: Et sammenkædet liste, du kunne gennemføre.
Og en linket liste er rart, fordi så det kan vokse vilkårligt længe i modsætning
at have nogle fast antal af mennesker i butikken.
Men måske et fast antal steder er legitim.
Fordi hvis de kun har ligesom 20 Iphones på den første dag, måske
de kun behøver en vifte af størrelse 20 til at repræsentere den kø, som
er kun at sige nu, når vi begynder at tale om disse problemer højere niveau,
du kan gennemføre det i en række forskellige måder.
Og der er nok bare at gå til være en afvejning i tid og rum
eller bare i din egen kode kompleksitet.
>> Hvad med en stak?
Tja, en stak, har vi set alt for kunne bare være disse bakker.
Og man kunne gennemføre denne et array.
Men på et tidspunkt, hvis du bruger et array, hvad der vil ske med bakkerne
du forsøger at lægge ned?
Ok.
Du vil kun være i stand til at gå så højt.
Og jeg tror i Mather, de er faktisk forsænket i denne åbning.
Så ja, det er næsten ligesom Mather bruger
en matrix af fast størrelse, fordi du kun kan
passer så mange bakker i, at åbningen i muren ned under folks knæ.
Og så der kan være siges at være et array,
men vi kunne sikkert gennemføre denne mere generelt med en linket liste.
>> Nå, hvad en anden datastruktur?
Lad mig trække op en anden visuel her.
Noget som hvordan omkring denne ene her?
Hvorfor kan det være nyttigt at have ikke noget så fancy som en trie, som
vi så haft disse meget brede knudepunkter, som hver er i en array?
Men hvad nu, hvis vi gør noget mere simpelthen, som en gammel skole stamtræ,
hver af hvis knudepunkter her blot lagre et nummer.
I stedet for et navn eller en efterkommer er bare at lagre et nummer som dette.
>> Nå, den jargon, vi bruger i datastrukturer er begge forsøg
og træer, hvor en trie igen, er blot én, hvis knudepunkter er arrays,
er stadig, hvad man kunne bruge fra folkeskolen
når du har lavet en familie tree-- blade og roden
af træet og børn af forælder og søskende deraf.
Og vi kan gennemføre et træ, for eksempel så enkelt som dette.
Et træ, hvis det som et knudepunkt, en af disse kredse, der har et nummer
det kommer ikke til at have en pointer, men to.
Og så snart du tilføjer en anden pointer, du
kan faktisk nu gøre slags af to-dimensionelle data
strukturer i hukommelsen.
Ligesom en todimensional array, kan du
har form af to-dimensionelle hægtede lister, men dem
at følge et mønster hvor der er ingen cykler.
Det er virkelig et træ med en bedsteforælder vej op her og derefter
nogle forældre og børn, og børnebørn og oldebørn.
og så videre.
>> Men hvad er virkelig sirlige om dette også, bare for at drille dig en smule kode med,
tilbagekaldelse rekursion fra et stykke tid tilbage, hvorved
du skriver en funktion, der kalder sig selv.
Dette er en smuk lejlighed at implementere noget
ligesom rekursion, fordi overveje dette.
>> Dette er et træ.
Og jeg har været lidt anal med hvordan Jeg sætter heltal på gaden.
Så meget, at det har en særlig name-- en binær søgning træ.
Nu har vi hørt om binær at søge, men kan du
arbejde baglæns fra denne ting navn?
Hvad er det mønster af, hvordan jeg indsættes heltal i dette træ?
Det er ikke vilkårlig.
Der er nogle mønster.
Ja.
>> PUBLIKUM: Mindre dem til venstre.
>> DAVID MALAN: Ja.
Mindre er på venstre.
Større virksomheder er på rette.
Sådan at en sand erklæring er en forælder er større end dens venstre barn,
men mindre end dens højre barn.
Og det alene er endda en rekursive verbal definition
fordi du kan anvende denne samme logik til hver node
og det kun bunde ud, en base tilfældet, hvis du
vil, når du rammer en af bladene, så at sige,
hvor en orlov har ingen børn yderligere.
>> Nu, hvordan kan du finde nummeret 44?
Du ville starte ved roden og sige, hm.
55 er ikke 44 Så gør jeg ønsker at gå ret eller skal jeg ønsker at gå tilbage?
Nå, selvfølgelig, du ønsker at gå til venstre.
Og så er det bare ligesom telefonen Bogen eksempel i binær søgning
mere generelt.
Men vi gennemføre den nu lidt mere dynamisk
end et array kunne give.
Og i virkeligheden, hvis du ønsker at se på den kode, ved første øjekast sikker.
Det ligner en hel masse linjer.
Men det er smukt enkle.
Hvis du ønsker at gennemføre en funktion kaldet søgning hvis formål i livet
er at søge efter en værdi ligesom n, et helt tal,
og du er gået i en en pointer-- en pointer til knudepunktet af rødder,
snarere af det træ, hvorfra du kan få adgang til alt det andet,
mærke til, hvor ligefremt du kan gennemføre logikken.
Hvis træet er null, selvfølgelig er det ikke der.
Lad os bare return false.
Right?
Hvis du aflevere det ingenting, der er ikke noget der.
>> Else, hvis n er mindre end træ pil n- nu arrow n,
husker vi indførte super kort den anden dag,
og det betyder bare de-reference pointer og se på det område, der kaldes n.
Så betyder det, gå der og se felt, der kaldes n.
Så hvis n, den værdi, du er givet, er mindre end værdien i træerne heltal,
Hvor vil du hen?
Til venstre.
>> Så mærke rekursionen.
Jeg returning-- ikke sandt.
Ikke falsk.
Jeg tilbage uanset svaret er fra et kald til mig selv, der passerer
en n igen, hvilket er overflødig men hvad er lidt anderledes nu?
Hvordan skal jeg gøre problemet mindre?
Jeg passerer ind som den anden argument, ikke roden af ​​træet,
men den venstre barn i dette tilfælde.
Så jeg passerer i venstre barn.
>> I mellemtiden, hvis n er større end node Jeg er i øjeblikket kigger på,
Jeg søger den højre side.
Else, hvis træet ikke er nul, og Hvis elementet ikke er til venstre
og det er ikke til højre, hvad er vidunderligt tilfældet?
Vi har faktisk fundet node i spørgsmål, og så vender vi tilbage sandt.
>> Så vi har lige kradset i overfladen nu nogle af disse datastrukturer.
I problem sæt fem du vil udforske disse endnu videre,
og du vil blive givet dit design valg af, hvordan man kan gå om dette.
Hvad jeg gerne vil slutte på er bare en 30 sekunders teaser
af, hvad der venter i næste uge og videre.
>> Som vi begin-- heldigvis du måske tror-- langsomt vores overgang
fra en verden af ​​C og lavere implementering niveau detaljer,
til en verden, hvor vi kan tage for givet, at en anden har endelig
gennemført disse data strukturer for os,
og vi vil begynde at forstå virkelige verden betyder, at gennemføre
web-baserede programmer, og websites mere generelt
og også meget sikkerhed konsekvenser, vi har kun
begyndt at ridse overfladen på.
Her er hvad der venter os i de kommende dage.
>> [VIDEO PLAYBACK]
>> -Han Kom med et budskab, med en protokol alle hans egen.
Han kom til en verden af ​​grusom firewalls, ufølsom routere,
og farer langt værre end døden.
Han er hurtig.
Han er stærk.
Han er TCP / IP, og han har fået din adresse.
"Warriors den i nettet."
[END VIDEO PLAYBACK]
DAVID MALAN: Kommer i næste uge.
Vi vil se dig derefter.
[VIDEO PLAYBACK]
-Og Nu, "dybe tanker" af Daven Farnham.
-David Starter altid forelæsninger med "All right."
Hvorfor ikke: "Her er løsningen til denne uges problem sæt "
eller "Vi giver jer alle et A?"
[LAUGHING]
[END VIDEO PLAYBACK]