>> SPEAKER 1: All right, så vi er tilbake.
Velkommen til CS50.
Dette er slutten av uke syv.
Så husker at sist gang, begynte vi sett på litt mer sofistikert
datastrukturer.
Siden frem til nå, alt vi hadde egentlig til rådighet var dette en matrise.
>> Men før vi forkaste matrisen som ikke alle som interessant, som faktisk er det
faktisk er, hva er noen av de positive til denne enkle data
struktur så langt?
Hva er det gode på?
Så langt som vi har sett?
Hva har du?
Ingenting.
>> STUDENT: [uhørlig].
>> SPEAKER 1: Hva er det?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Fast størrelse.
OK, så hvorfor er fast størrelse bra skjønt?
>> STUDENT: [uhørlig].
>> SPEAKER 1: OK, så det er effektiv i den forstand at du kan tildele en
fast beløp på plass, som forhåpentligvis er nettopp så mye
plass som du vil.
Så det kan være absolutt et pluss.
>> Hva er en annen opp side av en matrise?
Yeah?
>> STUDENT: [uhørlig].
>> SPEAKER 1: All the - beklager?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Alle boksene i minnet eller ved siden av hverandre.
Og det er nyttig - hvorfor?
Det er helt sant.
Men hvordan kan vi utnytte at sannheten?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Akkurat, kan vi holde styr på der alt er bare ved å vite
en adresse, nemlig den adresse i første byte av at mengde minne.
Eller i tilfelle av strengen, adressen til den første
røye i strengen.
Og derfra kan vi finne slutten av strengen.
Vi kan finne det andre elementet, den tredje element, og så videre.
>> Og så fancy måte å beskrive at funksjonen er at arrays gi oss
random access.
Bare ved hjelp av hakeparentes notasjon og et nummer, kan du hoppe til
et spesifikt element i matrisen i konstant tid, big O
av en, så å si.
>> Men det har vært noen ulemper.
Hva en rekke ikke veldig lett?
Hva er det ikke god på?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Hva er det?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Utvidelse i størrelse.
Så ulempene i matrisen er nettopp det motsatte av hva
oppsider er.
Så en av ulempene er at det er en fast størrelse.
Så du kan egentlig ikke vokse det.
Du kan omdisponere en større del av minnet, og deretter flytte de gamle elementene
inn det nye utvalget.
Og så fri den gamle array, for eksempel, ved å bruke malloc eller en lignende
funksjon kalt realloc, som reallocates minne.
>> Realloc, som en side, prøver å gi deg minne som er ved siden av rekken
som du allerede har.
Men det kan flytte ting rundt helt.
Men kort sagt, det er dyrt, ikke sant?
Fordi hvis du har en mengde minne om denne størrelsen, men du virkelig vil ha en
av denne størrelsen, og du ønsker å bevare de opprinnelige elementene, må du
omtrent en lineær tid kopieringen som må skje fra
gamle array til nye.
Og virkeligheten ber operativsystemet systemet igjen og igjen og
igjen for store biter av minne kan starte til å koste deg litt tid også.
Så det er både en velsignelse og en forbannelse i skjule det faktum at disse arrays
er av fast størrelse.
Men hvis vi innfører i stedet noe som dette, som vi kalte en koblet
liste, får vi noen oppsider og noen downsides her også.
>> Så en lenket liste er bare en data Strukturen består av C structs i dette
tilfelle, hvor en struct, husker, er bare en beholder for en eller flere bestemte
typer variabler.
I dette tilfellet, hva gjør de datatyper synes å være inne i struct som
siste gang vi kalte en node?
Hver av disse rektangler er en node.
Og hver av de mindre rektanglene innsiden av det er en datatype.
Hvilke typer vi si de var på mandag?
Yeah?
>> STUDENT: [uhørlig].
>> SPEAKER 1: En variabel og en peker, eller mer spesifikt, en int, for n,
og en peker på bunnen.
Begge disse tilfeldigvis er 32 biter, ved minst på en datamaskin som dette CS50
Apparatet, og slik at de er trukket like i størrelse.
>> Så hva bruker pekeren selv for tilsynelatende?
Hvorfor legge denne pilen nå når arrays var så fint og rent og enkelt?
Hva er pekeren gjør for oss i hver av disse nodene?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Nettopp.
Det forteller deg hvor den neste er.
Så jeg liksom bruke analogien ved hjelp av en tråd å sortere av
træ disse nodene sammen.
Og det er akkurat det vi gjør med pekere fordi hver av disse
biter av hukommelsen kan eller ikke kan være sammenhengende, rygg mot rygg mot rygg
innsiden av RAM, fordi hver gang du kalle malloc sier, gi meg nok
byte for en ny node, kan det være her eller det kan være her.
Det kan være her.
Du vet bare ikke.
>> Men ved hjelp av pekere i adressene til disse nodene, kan du sy dem
sammen på en måte som ser visuelt som en liste, selv om disse tingene er
spredt ut i hele ett eller dine to eller dine fire gigabyte RAM
innsiden av din egen datamaskin.
>> Så nedsiden, da, en lenket liste er hva?
Hva er en pris vi er tilsynelatende å betale?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Mer plass, ikke sant?
Vi har, i dette tilfellet, doblet mengde plass fordi vi har gått
fra 32 bits for hver node, for hver int, så nå 64 bits fordi vi må
holde rundt en peker også.
Du får mer effektivitet hvis struct er større enn dette enkle ting.
Hvis du faktisk har en student inne av disse er et par strenger for
navn og hus, kanskje et ID-nummer, kanskje noen andre felt helt.
>> Så hvis du har en stor nok struct, så kanskje kostnadene for pekeren er
ikke en så big deal.
Dette er en bit av et hjørne i tilfelle at vi lagre en så enkel primitiv
innsiden av lenket liste.
Men her er den samme.
Du definitivt bruke mer minne, men du får
fleksibilitet.
Fordi nå hvis jeg ønsker å legge til et element i begynnelsen av denne listen,
Jeg har til å tildele en ny node.
Og jeg må bare oppdatere dem piler eller annen måte ved å bare flytte
noen tips rundt.
>> Hvis jeg ønsker å sette noe inn i midten av listen, trenger jeg ikke å
presse alle til side som vi gjorde i ukers fortiden med våre frivillige som
representerte en matrise.
Jeg kan bare tildele en ny node og så bare peke pilene i
forskjellige retninger fordi det gjør ikke må forbli i selve
minne en sann linje som jeg har tegnet det her på skjermen.
>> Og så til slutt, hvis du vil sette inn noe ved slutten av listen, er det
enda enklere.
Dette er liksom vilkårlig notasjon, men 34 er pekeren, ta en gjetning.
Hva er verdien av sin pekeren mest sannsynlig trukket liksom som en gammel
skole antenne der?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Det er sannsynligvis null.
Og ja det er en forfatters representasjon av null.
Og det er null fordi du absolutt behov for å vite hvor enden av en koblet
listen er, så du holder følgende og følge og følge disse pilene
til noen søppel verdi.
Så null vil markere at det er ingen flere noder til høyre for tallet 34,
i dette tilfellet.
>> Så vi foreslår at vi kan implementere denne noden i koden.
Og vi har sett denne typen av syntaksen før.
Typedef definerer bare en ny type for oss, gir oss et synonym som
streng var for røye *.
I dette tilfellet, det kommer til å gi oss korte notasjonen slik at struct node
kan i stedet bare skrives som node, som er mye renere.
Det er mye mindre detaljert.
>> Innsiden av en node er tilsynelatende en int kalt n, og deretter en struct node *
som betyr nøyaktig hva vi ønsket pilene til å bety, en peker til en annen
node av nøyaktig samme datatype.
Og jeg foreslår at vi kunne gjennomføre en Søkefunksjonen som dette, som på
første øyekast kan virke litt komplisert.
Men la oss se det i sammenheng.
>> La meg gå over til apparatet her.
La meg åpne opp en fil som heter liste null dot h.
Og som bare inneholder definisjonen vi bare så en stund siden for disse dataene
typen kalles en node.
Så vi har satt det inn i en prikk h-fil.
>> Og som en side, selv om dette program som du er i ferd med å se er
ikke så komplisert, det er faktisk konvensjonen når du skriver et program for å
sette ting som datatyper, for å trekke konstanter noen ganger, inne i ditt
header-fil og ikke nødvendigvis i C-fil, sikkert når
programmer får større og større, slik at du vet hvor du skal lete både for
dokumentasjon i noen tilfeller, eller for grunnleggende som dette, de
definisjon av noen type.
>> Hvis jeg nå åpner opp liste null dot c, merke noen ting.
Den inneholder noen header-filer, de fleste som vi har sett før.
Det inkluderer en egen header-fil.
>> Og som en side, hvorfor det er dobbelt sitater her, i motsetning til vinkelen
brakettene på linjen som Jeg har merket det?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Ja, så det er en lokal fil.
Så hvis det er en lokal fil på din egen her på linje 15, for eksempel, bruker du
de doble anførselstegn i stedet av de vinklede braketter.
>> Nå er dette ganske interessant.
Legg merke til at jeg har erklært en global variabel i dette programmet på linje 18
ringte først, er ideen er dette kommer til å være en peker til den første
node i min lenket liste, og jeg har initialisert det til null, fordi jeg har
ikke tildelt noen faktiske noder ennå.
>> Så dette representerer, billedlig, hva vi så et øyeblikk siden i bildet som
at pekeren på langt venstre side.
Så akkurat nå, som peker ikke har en pil.
Det er i stedet bare null.
Men det viser hva som vil være den adressen til den første faktiske
node i denne listen.
Så jeg har implementert det er en global fordi, som du ser, alt dette
Programmet i livet er å implementere en lenket liste for meg.
>> Nå har jeg fått noen prototyper her.
Jeg bestemte meg for å implementere funksjoner som sletting, innsetting, søking og
traversering -
den siste bare å være spasertur over liste, skrive ut dens elementer.
Og nå her er min viktigste rutine.
Og vi vil ikke bruke for mye tid på disse siden dette er liksom, forhåpentligvis
gammelt hat nå.
>> Jeg kommer til å gjøre følgende, mens brukeren samarbeider.
Så en, kommer jeg til å skrive ut ut denne menyen.
Og jeg har formatert den som en ren, så jeg kunne.
Hvis brukeren skriver i ett, betyr det at de ønsker å slette noe.
Hvis brukeren skriver i to, det betyr de ønsker å sette inn noe.
Og så videre.
Jeg skal da be deretter for en kommando.
Og så jeg kommer til å bruke GetInt.
>> Så dette er en veldig enkel menuing grensesnitt der du bare trenger å skrive
et nummer til en kartlegging av disse kommandoene.
Og nå har jeg en fin clean switch uttalelse som kommer til å slå på
hva brukeren har skrevet i.
Og hvis de skrev en, vil jeg ringe slette og bryte.
Hvis de har skrevet to, vil jeg ringe inn og bryte.
>> Og nå merker jeg har satt hver av disse på samme linje.
Dette er bare en stilistisk avgjørelse.
Vanligvis vi har sett noe som dette.
Men jeg bare bestemte meg, ærlig, mitt program så mer lesbar fordi
det var bare fire saker til bare liste det slik.
Helt legitim bruk av stilen.
Og jeg kommer til å gjøre dette så lenge Brukeren har ikke skrevet null, som jeg
besluttet vil bety at de ønsker å slutte.
>> Så nå merke til hva jeg er kommer til å gjøre her.
Jeg kommer til å frigjøre listen tilsynelatende.
Men mer om det i løpet av et øyeblikk.
La oss først kjøre dette programmet.
Så la meg gjøre en større terminal vindu, dot slash liste 0.
Jeg kommer til å gå videre og sette inn med to typing, et tall som 50, og nå
du vil se listen er nå 50.
Og teksten min bare rullet opp litt.
Så nå merke listen inneholder nummer 50.
>> La oss gjøre en annen innsats ved å ta to.
La oss skrive inn nummeret som en.
Listen er nå en, etterfulgt av 50.
Så dette er bare en tekstlig representasjon av listen.
Og la oss sette inn en flere antall som tallet 42, som er forhåpentligvis
kommer til å ende opp i midten, fordi dette programmet i spesielle former det
elementer som det setter dem.
Så der har vi det.
Super enkelt program som kunne absolutt ha brukt en matrise, men jeg
måtte bruke en lenket liste bare så jeg kan dynamisk
vokse og krympe det.
>> Så la oss ta en titt for søk, hvis jeg kjøre kommandoen tre, jeg ønsker å søke
for, si, nummer 43.
Og ingenting ble tydeligvis funnet, fordi jeg fikk tilbake noe svar.
Så la oss gjøre dette igjen.
Søke.
La oss søke for 50, eller snarere søke henholdsvis 42, som har en fin
lite subtil betydning.
Og jeg fant meningen med livet der.
Number 42, hvis du ikke vet referansen, Google det.
OK.
Så hva har dette programmet gjort for meg?
Det er bare tillatt meg å sette dermed langt og søk etter elementer.
>> La oss spole fremover, da, for å den funksjonen vi kikket på
på mandag som en teaser.
Så denne funksjonen, hevder jeg, søker etter et element i listen ved første
en, spørre brukeren og deretter ringer GetInt å få en faktisk int
du vil søke etter.
>> Deretter merke til dette.
Jeg kommer til å lage en midlertidig variabel på linje 188 som heter spisser -
PTR -
kunne ha kalt det noe.
Og det er en peker til en node fordi jeg sa node * der.
Og jeg klargjør den til å være lik først, slik at jeg effektivt har min
finger, så å si, på den meget første element av listen.
Så hvis min høyre hånd her er PTR jeg er peker på det samme som første
peker på.
>> Så nå tilbake i kode, hva som skjer videre -
dette er en vanlig paradigme ved gjentakelse over en struktur som en
lenket liste.
Jeg kommer til å gjøre følgende mens pekeren er ikke lik null Så mens
min finger peker ikke på noen null verdi, hvis Pekerpilen n er lik n.
Vi vil merke først at n er hva brukeren har skrevet i per GetInts ringe her.
>> Og Pekerpilen n betyr det?
Vel, hvis vi går tilbake til bildet her, hvis jeg har en finger peker på
at første noden som inneholder ni, pil betyr i hovedsak gå til det
node og ta tak i verdien på plasseringen n, I dette tilfellet kalles datafeltet n.
>> Som en side - og vi så denne et par uker siden, da noen spurte -
denne syntaksen er nytt, men det gjør ikke gi oss krefter som vi
ikke allerede har.
Hva var dette uttrykket tilsvarer å bruke dot notasjon og stjerne et par
uker siden da vi skrelles tilbake dette laget litt for tidlig?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Akkurat, var det stjerne, og da var det stjerners dot n, med
parentes her, som ser, ærlig, tror jeg mye
mer kryptisk å lese.
Men stjerners pekeren, som alltid, betyr gå dit.
Og når du er der, hvilke data Feltet vil du få tilgang til?
Vel du bruker dot notasjon for å få tilgang en structs data-feltet, og jeg
ønsker spesielt n.
>> Ærlig, vil jeg hevde dette er bare vanskeligere å lese.
Det er vanskeligere å huske hvor trenger parentesene går, jo
stjerners og alt det.
Så verden vedtatt noen syntaktisk sukker, så å si.
Bare en sexy måte å si: Dette er tilsvarende, og
kanskje mer intuitivt.
Hvis pekeren er faktisk en pekeren, arrow notasjon del gå dit og finne
feltet i dette tilfelle kalles n.
>> Så hvis jeg finner den, legge merke til hva jeg gjør.
Jeg ganske enkelt skrive ut, fant jeg prosent i, plugge i verdien for den int.
Jeg kaller sove i ett sekund bare for å kind av pause ting på skjermen for å
gi brukeren en annen for å absorbere hva skjedde.
Og da jeg bryte.
Ellers hva gjør jeg?
Jeg oppdaterer pekeren til lik Pekerpilen neste.
>> Så bare for å være klar, betyr dette gå der, ved hjelp av min gamle skolen notasjon.
Så dette betyr bare å gå til uansett du peker på, som i svært
første tilfellet er jeg peker på struct med ni i den.
Så jeg har gått der.
Og så dot notasjon betyr, få verdien på neste.
>> Men verdien, selv om den er trukket som en smal, er bare et tall.
Det er en numerisk adresse.
Så man denne linjen med kode, enten skrevet som dette, jo mer kryptisk
måte, eller som dette, de litt mer intuitiv måte, betyr bare flytte hånden min
fra den første noden til den neste, og deretter den neste, og deretter
neste, og så videre.
>> Så vi vil ikke dvele ved den andre implementeringer av sette inn og slette
og traversering, de første to av som er ganske involvert.
Og jeg tror det er ganske lett å få tapt når du gjør det verbalt.
Men hva vi kan gjøre her er prøve for å bestemme hvordan
best å gjøre dette visuelt.
Fordi jeg ville foreslå at hvis vi vil sette inn elementer i dette
eksisterende liste, som har fem elementer -
9, 17, 22, 26, og 33 -
hvis jeg skulle gjennomføre dette i kode, jeg trenger å vurdere hvordan du skal gå
om du gjør dette.
>> Og jeg vil foreslå å ta små steg der, i dette tilfellet jeg mener, hva er
de mulige scenarier som vi kan støte på generelt?
Ved implementering av innsatsen for en koblet listen, så skjer dette bare å være en
spesifikt eksempel på størrelse fem.
Vel, hvis du vil sette inn et tall, liker si nummer én, og
opprettholde sortert rekkefølge, der åpenbart gjør nummer én må
gå i denne konkrete eksempel?
Som i begynnelsen.
>> Men det som er interessant er det at Hvis du ønsker å sette et inn i dette
liste, må det spesielle pekeren å bli oppdatert tilsynelatende?
Først.
Så jeg vil hevde at dette er den første saken at vi kanskje vil vurdere, en
scenario som involverer innsetting på begynnelsen av listen.
>> La oss plukke ut kanskje en så enkel eller lettere fall relativt sett.
Anta ønsker jeg å sette inn nummer 35 i sortert rekkefølge.
Det hører selvsagt der borte.
Så hva pekeren åpenbart kommer til å må oppdateres i det scenarioet?
34 er pekeren blir ikke null men adressen til struct
inneholder nummer 35.
Så det er tilfelle to.
Så allerede, jeg er liksom kvantisering hvor mye arbeid jeg må gjøre her.
>> Og til slutt, er det opplagte midt saken faktisk, i midten, hvis jeg vil
sette inn noe sånt som 23 si, som går mellom 23 til og 26, men
nå ting blir litt mer involvert fordi det
pekere må endres?
Så 22 må åpenbart må endres fordi han ikke kan vise til 26 lenger.
Han trenger å peke på den nye noden som Jeg må fordele ved å ringe
malloc eller noe tilsvarende.
>> Men så må jeg også at ny node, 23 i dette tilfellet, å ha sin pekeren
peker på hvem?
26.
Og det kommer til å bli en rekkefølgen av operasjoner her.
For hvis jeg gjør dette tåpelig, og jeg for eksempel start ved begynnelsen av
listen, og målet mitt er å sette inn 23.
Og jeg sjekke, hører det her, nær ni?
Nei.
Hører det her, ved siden av 17?
Nei.
Betyr det hører hjemme her ved siden av 22?
Ja.
>> Nå hvis jeg er tåpelig her, og ikke tenker dette gjennom, kanskje jeg
tildele min nye node for 23.
Jeg kan oppdatere pekeren fra noden som kalles 22, peker
det ved den nye noden.
Og hva må jeg oppdatere den nye nodens pekeren å være?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Nettopp.
Peker på 26..
Men faen om jeg ikke allerede oppdaterer 22 er pekeren å peke på denne fyren, og
nå har jeg foreldreløse, resten av listen, så å si.
Så rekkefølgen av operasjoner her kommer til å være viktig.
>> For å gjøre dette kan jeg stjele, si, seks frivillige.
Og la oss se om vi ikke kan gjøre dette visuelt i stedet for kode-messig.
Og vi har noen herlige stresset baller for deg i dag.
OK, hva med en, to, i tilbake - på slutten der.
tre, fire, begge to gutta på slutten.
Og fem, seks.
Jada.
Fem og seks.
Greit og vi vil komme til dere neste gang.
Greit, kom igjen opp.
>> Greit, siden du er her oppe først, ønsker du å være en klønete
i Google Glass her?
Ok, så, OK, Glass, spille inn en video.
OK, du er god til å gå.
>> Ok, så hvis dere kan komme over her har jeg forberedt på forhånd
noen tall.
Greit, kom på over her.
Og hvorfor ikke du går litt videre på den måten.
Og la oss se, hva heter du, med Google Glass?
>> STUDENT: Ben.
>> SPEAKER 1: Ben?
OK, Ben, vil du være den første, bokstavelig talt.
Så vi kommer til å sende deg til slutten av den scene.
Greit, og navnet ditt?
>> STUDENT: Jason.
>> SPEAKER 1: Jason, OK du vil bli nummer ni.
Så hvis du ønsker å følge Ben på den måten.
>> STUDENT: Jill.
>> SPEAKER 1: Jill, du kommer til å være 17, som hvis jeg hadde gjort dette mer
intelligent, ville jeg ha startet i den andre enden.
Du går den veien.
22.
Og du er?
>> STUDENT: Mary.
>> SPEAKER 1: Mary, vil du være 22.
Og navnet ditt er?
>> STUDENT: Chris.
>> SPEAKER 1: Chris, vil du være 26.
Og så til slutt.
>> STUDENT: Diana.
>> SPEAKER 1: Diana, vil du være 34.
Så du kommer på over her.
>> All right, så perfekt sortert bestille allerede.
Og la oss gå videre og gjøre dette slik at vi virkelig kan -
Ben du er bare slags jakt ut i intet der.
OK, så la oss gå videre og skildre dette bruker armene, mye som jeg var, akkurat,
hva som skjer.
Så gå videre og gi dere en fot eller to mellom dere.
Og gå videre og peker med den ene hånden til hvem du skal peke på
basert på dette.
Og hvis du er null bare peke rett ned til gulvet.
OK, så bra.
>> Så nå har vi en lenket liste, og la meg foreslår at jeg skal spille rollen som
PTR, så jeg vil ikke bry bærer dette rundt.
Og så - noen dum konvensjonen - du kan kalle dette noe du vil -
forgjenger pekeren, Pred spisser -
det er bare kallenavnet vi ga i vår eksempelkode til min venstre hånd.
Den andre hånden som kommer til å være å holde styr på hvem som er hvem i
følge scenarier.
>> Så vel, først vil jeg rykke ut det første eksempel på å sette inn, sier
20, inn i listen.
Så jeg kommer til å trenge noen til legemliggjøre nummer 20 for oss.
Så jeg trenger å malloc noen fra publikum.
Kom opp.
Hva heter du?
>> STUDENT: Brian.
>> SPEAKER 1: Brian, all right, slik at du skal være den noden som inneholder 20.
Greit, kom på over her.
Og selvsagt, der hører Brian?
Så, i midten av - faktisk vent litt.
Vi gjør dette ut av drift.
Vi gjør dette mye vanskeligere enn den trenger å være først.
OK, vi skal til gratis Brian og realloc Brian som fem.
>> OK, så nå ønsker vi å sette inn Brian som fem.
Så kom igjen over her ved siden av Ben for bare et øyeblikk.
Og du kan antagelig fortelle hvor denne historien går.
Men la oss tenke nøye rekkefølgen av operasjoner.
Og det er nettopp denne visuelle som kommer til å stille opp
med at eksempelkode.
Så her har jeg PTR peker innledningsvis ikke på Ben, per se, men uansett hvilken
setter han inneholder, som i dette tilfellet er - hva heter du igjen?
>> STUDENT: Jason.
>> 1 SPEAKER: Jason, slik at både Ben og jeg er peker på Jason i dette øyeblikk.
Så nå må jeg bestemme, hvor hører Brian?
Så det eneste jeg har tilgang til akkurat nå er hans n data element.
Så jeg kommer til å sjekke, er Brian mindre enn Jason?
Svaret er sant.
>> Så hva må nå skje, i riktig rekkefølge?
Jeg trenger å oppdatere hvor mange pekere totalt i denne historien?
Hvor min hånd er fremdeles peker på Jason, og hånden din - hvis du vil
legg din hånd som, liksom, jeg vet ikke, et spørsmålstegn.
OK, bra.
>> Ok, så du har noen få kandidater.
Enten Ben eller jeg eller Brian eller Jason eller alle andre, som
pekere må endre?
Hvor mange totalt?
>> OK, så to.
Min pekeren spiller egentlig ingen rolle lenger fordi jeg er bare midlertidig.
Så det er disse to gutta, formodentlig, både Ben og Brian.
Så la meg foreslå at vi oppdaterer Ben, siden han er først.
Det første elementet i denne liste nå kommer til å være Brian.
Så Ben punktet Brian.
OK, hva nå?
>> Hvem blir pekt på hvem?
>> STUDENT: [uhørlig].
>> SPEAKER 1: OK så Brian har å peke på Jason.
Men har jeg mistet oversikten over at pekeren?
Vet jeg hvor Jason er?
>> STUDENT: [uhørlig].
>> SPEAKER 1: jeg gjør, siden jeg er den midlertidige pekeren.
Og antagelig har jeg ikke endret å peke på den nye noden.
Så vi kan rett og slett ha Brian point på hvem jeg peker på.
Og vi er ferdige.
Så fall en, innsetting på begynnelsen av listen.
Det var to viktige skritt.
One, må vi oppdatere Ben, og deretter vi må også oppdatere Brian.
Og så jeg ikke trenger å bry seg traipsing gjennom resten av
liste, fordi vi allerede funnet sin plassering, fordi han tilhørte den
venstre for det første element.
>> Greit, så ganske grei.
Faktisk føles som vi er nesten gjør dette for komplisert.
Så la oss nå nappe av enden av listen, og se hvor
kompleksiteten starter.
Så hvis nå, Alloc jeg fra publikum.
Alle som ønsker å spille 55?
Greit, jeg så hånden først.
Kom opp.
Yeah.
Hva heter du?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Habata.
OK, kom igjen opp.
Du vil være nummer 55 år.
Så du, selvfølgelig, tilhører ved enden av listen.
Så la oss spille av simulering med meg være PTR for bare et øyeblikk.
Så jeg først kommer til å peke på hva Ben peker på.
Vi er begge peker nå på Brian.
Så 55 er ikke mindre enn fem.
Så jeg kommer til å oppdatere meg selv ved peker til Brians neste pekeren, som
nå er selvfølgelig Jason.
55 er ikke mindre enn ni, så Jeg kommer til å oppdatere PTR.
Jeg kommer til å oppdatere PTR Jeg kommer til å oppdatere PTR.
Og jeg kommer til å - hmm, hva er navnet ditt igjen?
>> STUDENT: Diana.
>> SPEAKER 1: Diana peker, selvfølgelig, på null med sin venstre hånd.
Så hvor kommer Habata faktisk hører klart?
Til venstre her.
Så hvordan vet jeg å sette henne her Jeg tror jeg har skrudd opp.
Fordi det er PTR kunst dette øyeblikket i tid?
Null.
Så selv om, visuelt, kan vi selvsagt se alle disse
Gutta her på scenen.
Jeg har ikke holdt orden på den forrige person i listen.
Jeg har ikke en finger peker ut, I dette tilfellet noden nummer 34.
>> Så la oss faktisk starte dette over.
Så nå er jeg faktisk trenger en annen lokal variabel.
Og dette er hva du vil se i Selve prøven C-kode, der som jeg går,
når jeg oppdaterer min høyre hånd til å peke Jason, og dermed forlate Brian bak, jeg
bedre begynne å bruke min venstre hånd til oppdatere hvor jeg var, slik at når jeg går
gjennom denne listen -
mer klønete enn jeg ment nå her visuelt -
Jeg kommer til å komme til slutten av listen.
>> Denne hånden er fortsatt null, noe som er ganske ubrukelig, annet enn for å indikere
Jeg er tydelig på slutten av listen, men nå i hvert fall jeg ha denne
forgjenger pekeren peker her, så nå hva hender og hva pekere trenger
å bli oppdatert?
Hvis hånd vil du å konfigurere først?
>> STUDENT: [uhørlig].
>> 1 SPEAKER: OK, så Dianas.
Hvor vil du peke Dianas venstre peker på?
55 at, formodentlig slik at vi har satt inn der.
Og hvor skal 55 pekeren gå?
Down, som representerer null.
Og hendene mine, på dette punktet, ikke saken fordi de var bare
midlertidige variabler.
Så nå er vi ferdige.
>> Så den ekstra kompleksitet der - og det er ikke så vanskelig å implementere,
men vi trenger en sekundær variabel å gjøre sikker på at før jeg flytter min høyre
hånd, oppdaterer jeg verdien av min venstre hånd, pred pekeren i dette tilfellet, så
at jeg har en etterfølgende pekeren å holde styr på hvor jeg var.
Nå som en side, hvis du tenker på dette gjennom, føles dette som om det er en
Litt irriterende å måtte holde spore av denne venstre hånd.
>> Hva ville en annen løsning på dette problemet har vært?
Hvis du fikk til å omstrukturere dataene strukturen vi snakker
gjennom akkurat nå?
Hvis dette bare slags føles litt irriterende å ha, som, to pekere
gå gjennom listen, kan hvem andre har, i en ideell verden, opprettholdes
informasjon som vi trenger?
Yeah?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Nettopp.
Høyre, så det er faktisk en interessant spiren til en idé.
Og denne ideen om en tidligere peker, peker på den forrige element.
Hva om jeg bare nedfelt at innsiden av selve listen?
Og det kommer til å være vanskelig å visualisere dette uten alt papiret
falle ned på gulvet.
Men anta at disse gutta brukte både av sine hender til å ha en tidligere
pekeren, og en neste peker, og dermed gjennomføre det vi kaller en dobbelt
lenket liste.
Som ville tillate meg å sortere av spole tilbake, mye lettere uten meg,
programmerer, måtte holde spore manuelt -
virkelig manuelt -
på hvor jeg hadde vært tidligere i listen.
Så vi vil ikke gjøre det.
Vi vil holde det enkelt fordi det er kommer til å komme til en pris, dobbelt så
mye plass for pekere, Hvis du vil ha en ny en.
Men det er faktisk en felles datastruktur kjent som en
dobbelt lenket liste.
>> La oss gjøre det siste eksempel her og sette disse gutta ut av sin elendighet.
Så 20 malloc.
Kom opp fra midtgangen der.
Ok, hva heter du?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Sorry?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Demeron?
OK tennes opp.
Du skal være 20.
Du åpenbart kommer til å tilhøre mellom 17 og 22.
Så la meg lære min lekse.
Jeg kommer til å starte pekeren peker på Brian.
Og jeg kommer til å ha min venstre hånd bare oppdatere til Brian som jeg flytter til
Jason, kontroll gjør 20 mindre enn ni?
Nei.
Er 20 mindre enn 17?
Nei.
Er 20 mindre enn 22?
Ja.
Så hva pekere eller hender må endre hvor de peker nå?
>> Så vi kan gjøre 17 peker på 20..
Så det er fint.
Hvor ønsker vi å peke pekeren nå?
På 22.
Og vi vet hvor 22 er, igjen takk til min midlertidige pekeren.
Så vi er OK der.
Det på grunn av denne mellomlagring Jeg har holdt styr på hvor alle er.
Og nå kan du visuelt gå inn der du tilhører, og nå trenger vi en, to, tre,
4, 5, 6, 7, 8, 9 stress baller, og en runde med applaus for
disse gutta, hvis vi kunne.
Pent gjort.
>> [APPLAUSE]
>> SPEAKER 1: All right.
Og du kan holde bitene av papir som minner.
>> All right, så stol på meg det er mye lettere å gå gjennom det med
mennesker enn det er med selve koden.
Men hva du finner på bare et øyeblikk nå, er det samme - jo takk.
Takk -
er at du vil finne at de samme dataene struktur, en lenket liste, kan faktisk
anvendes som en byggesten for enda mer sofistikerte datastrukturer.
>> Og innse for temaet her er at vi har absolutt innført mer
kompleksiteten i gjennomføringen av denne algoritmen.
Innsetting, og hvis vi gikk gjennom det, sletting og søking, er litt
mer komplisert enn det ble med en matrise.
Men vi få litt dynamikk.
Vi får en adaptiv datastruktur.
>> Men igjen, vi betaler en pris for å ha noen ytterligere kompleksitet, både
implementere det.
Og vi gitt opp random access.
Og for å være ærlig, det er ikke noe hyggelig rengjøre lysbilde jeg kan gi deg at
sier her er hvorfor en lenket liste er bedre enn en matrise.
Og la det bli med det.
Fordi temaet repeterte nå, selv mer i de kommende ukene, er
at det ikke nødvendigvis et korrekt svar.
>> Dette er grunnen til at vi har egen akse av design for oppgavesett.
Det vil være svært kontekstavhengig om du vil bruke disse dataene
struktur, eller at man, og det vil avhenge av hva som er viktig for deg i form
av ressurser og kompleksitet.
>> Men la meg foreslå at de ideelle data struktur, den hellige gral, ville være
noe som er konstant tid, uavhengig av hvor mye ting er
inni den, ville ikke det være fantastisk hvis en datastruktur returnert svarene i
konstant tid.
Ja.
Dette ordet er i stor ordbok.
Eller nei, dette er ikke ordet.
Eller noe slikt problem der.
Vel la oss se om vi kan ikke minst ta et skritt mot dette.
>> La meg foreslå en ny datastruktur som kan brukes til forskjellige ting,
i dette tilfelle kalles en hash tabell.
Og så er vi faktisk tilbake til skotter ved en matrise, i dette tilfellet, og
noe tilfeldig, jeg har tatt dette hash table som en matrise med en slags
todimensjonal matrise -
eller rettere sagt den er avbildet her som en to dimensjonal array - men dette er bare
en matrise av størrelse 26, slik at hvis vi kaller matrisen, bord brakett
null er rektangelet på toppen.
Bordbrakett 25 er rektangelet nederst.
Og dette er hvordan jeg kunne trekke en data struktur der jeg ønsker å lagre
folks navn.
>> Så for eksempel, og jeg vil ikke trekke hele greia her på overhead, hvis jeg
hadde denne tabellen, som jeg nå kommer til å kalle en hash bord, og dette er igjen
plassering null.
Dette her er beliggenheten en, og så videre.
Jeg påstår at jeg ønsker å bruke disse dataene struktur, av hensyn til diskusjonen,
for å lagre folks navn, Alice og Bob og Charlie og andre slike navn.
Så tenk på dette nå som begynnelsen av, sier en ordbok
med mange ord.
De måtte være navn i vårt eksempel her.
Og dette er alt for germane, kanskje, å gjennomføre en stavekontroll, som vi
kanskje for problem satt seks.
>> Så hvis vi har en rekke total størrelse 26 slik at dette er den 25. plassering
på bunnen, og jeg hevder at Alice er det første ordet i ordlisten av
navnene som jeg ønsker å sette inn i RAM, inn i denne datastruktur, hvor er
instinkter som forteller deg at Alices Navnet bør gå i denne tabellen?
>> Vi har 26 alternativer.
Hvor vi ønsker å sette henne?
Vi ønsker henne i braketten null, ikke sant?
En for Alice, la oss kalle det null.
Og B vil være en, og C vil være to.
Så vi kommer til å skrive Alice navn her oppe.
Hvis vi deretter sette Bob, hans Navnet vil gå her.
Charlie vil gå her.
Og så videre ned igjennom dette datastruktur.
>> Dette er en fantastisk datastruktur.
Hvorfor?
Vel hva er kjøretiden til sette inn et menneskes navn inn i denne
datastruktur akkurat nå?
Gitt at denne tabellen er implementert, virkelig, som en matrise.
Vel det er konstant tid.
Det er rekkefølgen på en.
Hvorfor?
>> Vel hvordan kan du bestemme hvor Alice tilhører?
Du ser på hvilken bokstav i navnet hennes?
Den første.
Og du kan få det, hvis det er en streng, bare ved å se på streng
brakett null.
Så zeroth tegnet i strengen.
Det er lett.
Vi gjorde det i krypto oppdrag uker siden.
Og så når du vet at Alice Brevet er hovedstaden A, kan vi trekke
off 65 eller formue A selv, som gir oss null.
Så nå vet vi at Alice tilhører ved plassering null.
>> Og gitt en peker til disse dataene struktur, av noe slag, hvor lenge varer
det tar meg å finne sted null i en matrise?
Bare ett skritt, akkurat det er konstant tid på grunn av tilfeldig tilgang vi
foreslått var en funksjon av en matrise.
Så kort sagt, å finne ut hva indeksen av Alice navn er, som er i
dette tilfellet er A, eller la oss bare løse at til null, hvor B er en-og C er
to, finne det ut er konstant tid.
Jeg må bare se på sitt første brev, finne ut hvor null er en
matrise er også konstant tid.
Så teknisk sett det er som to skritt nå.
Men det er fortsatt konstant.
Så vi kaller den store O av en, så har vi satt Alice inn i denne tabellen i
konstant tid.
>> Men selvfølgelig, jeg blir naiv her, ikke sant?
Hva hvis det er en Aron i klassen?
Eller Alicia?
Eller noen andre navn som starter med A. Hvor skal vi sette
som person, ikke sant?
Jeg mener, akkurat nå er det bare tre folk på bordet, så kanskje vi
bør sette Aaron på stedet null en to tre.
>> Høyre, kunne jeg sette A her.
Men så, hvis vi prøver å sette inn David inn denne listen, betyr hvor David reise?
Nå systemet vårt begynner å bryte ned, ikke sant?
Fordi nå David havner her hvis Aaron er faktisk her.
Og så nå dette hele ideen om å ha en ren datastruktur som gir oss
konstant tid innsettinger er ikke lenger konstant tid, fordi jeg må
sjekk, oh, damnit, er noen allerede på Alice beliggenhet.
>> La meg undersøke resten av disse dataene struktur, på jakt etter et sted å sette
noen som Aaron navn.
Og så vil også den starter å ta lineær tid.
Dessuten, hvis du nå ønsker å finne den Aaron i dette datastruktur, og du
sjekk, og Aaron navn er ikke her.
Ideelt sett ville du bare si Arons ikke i datastrukturen.
Men hvis du begynner å lage rom for Aaron der det skulle ha vært en D
eller en E, du, verste fall må sjekke hele datastruktur, i
og da er det tilfaller til noe lineær i størrelsen av bordet.
>> Så all right, jeg skal fikse dette.
Problemet her er at jeg hadde 26 elementer i denne tabellen.
La meg endre det.
Uff da.
La meg endre det slik at heller være av størrelse 26 totalt, merker bunnen
indeks kommer til å endre til n minus en.
Hvis 26 er helt klart for lite for mennesker ' navn, fordi det er tusenvis av
navnene i verden, la oss bare gjøre i 100 eller 1000 eller 10000.
La oss bare bevilge mye mer plass.
>> Vel som ikke nødvendigvis redusere sannsynligheten for at vi ikke vil ha to
folk med navn som starter med A, og så, skulle du prøve å sette en
navn på stedet null fortsatt.
De er fortsatt kommer til å kollidere, noe som betyr at vi fortsatt trenger en løsning å sette
Alice og Aron og Alicia og andre navn som starter med A andre steder.
Men hvor mye av et problem er dette?
Hva er sannsynligheten for at du har kollisjoner i en data
struktur som dette?
>> Vel, la meg - vi vil komme tilbake på det spørsmålet her.
Og se på hvordan vi kan løse det først.
La meg trekke opp dette forslaget her.
Hva vi nettopp beskrev er en algoritme, en heuristisk kalt lineær
sondering der, hvis du prøvde å sette inn noe her i disse dataene
struktur, som kalles en hash tabell, og det er ikke plass der, du
virkelig sondere datastruktur kontroll, er dette tilgjengelig?
Dette Tilgjengelig er dette tilgjengelig?
Er dette tilgjengelig?
Og når det endelig er, setter du den nevne at du opprinnelig ment
andre steder på den plasseringen.
Men i verste fall, den eneste flekk kan være den aller bunnen av data
struktur, helt på slutten av tabellen.
>> Så lineær sondering, i verste fall, tilfaller i en lineær algoritme hvor
Aaron, hvis han tilfeldigvis settes inn sist i denne datastruktur, kanskje han
kolliderer med denne første plasseringen, men deretter avslutte med uflaks helt på slutten.
Så dette er ikke en konstant tid hellige gral for oss.
Denne tilnærmingen av å sette inn elementer inn en datastruktur kalt en hash
tabell ser ikke ut til å være konstant tid i det minste ikke i det generelle tilfellet.
Det kan tilfalle til noe lineær.
>> Så hva om vi løse kollisjoner noe annerledes?
Så her er en mer sofistikert tilnærming til hva som fortsatt er
kalles en hash table.
Og etter hasj, som en side, hva Jeg mener er den indeksen som
Jeg refererte til tidligere.
Til hasj noe kan være tenkt som et verb.
>> Så hvis du hash Alice er et navn, en hash-funksjon, så å si,
skal returnere et tall.
I dette tilfelle er null hvis hun hører til null beliggenhet, en hvis hun hører på
sted en, og så videre.
Så min hash-funksjon så langt har vært super enkelt, bare å se på
første bokstaven i noens navn.
Men en hash-funksjon tar som innspill noen stykke data, en
string, en int, uansett.
Og den spytter ut vanligvis et tall.
Og at antallet er der at data element hører hjemme i en datastruktur
kjent her som en hash table.
>> Så bare intuitivt, er dette en litt annen sammenheng.
Dette faktisk henviser til et eksempel involverer bursdager, der
det kan være så mange som 31 dager i måneden.
Men hva gjorde denne personen bestemmer seg for å gjøre i tilfelle av en kollisjon?
Kontekst nå være, ikke en kollisjon mellom navn, men en kollisjon på fødselsdager,
hvis to mennesker har samme bursdag på den 2. oktober for eksempel.
>> STUDENT: [uhørlig].
>> SPEAKER 1: Ja, så her har vi den utnytte av lenkede lister.
Så det ser litt annerledes enn vi trakk det tidligere.
Men vi ser ut til å ha til en matrise på den venstre side.
Det er en indeks, for ingen spesiell grunn.
Men det er fortsatt en matrise.
Det er en rekke pekere.
Og hver av disse elementer, og hver av disse sirklene eller skråstreker - skråstreken
representerer null - hver av disse pekere er tilsynelatende peker til
hva datastruktur?
En lenket liste.
>> Så nå har vi muligheten til å hardt kode i vårt program
størrelsen av bordet.
I dette tilfellet vet vi at det er aldri mer enn 31 dager i en måned.
Så vanskelig koding en verdi som 31 er rimelig i denne sammenheng.
I sammenheng med navn, hard koding 26 er ikke urimelig det folks
bare navn begynner med, for eksempel, alfabetet involverer A til Z.
>> Vi kan stappe dem alle i at data struktur så lenge, når vi får en
kollisjon, kan vi ikke sette navnene her, vi i stedet tenker på disse cellene
ikke som strengene selv, men som pekere til, for eksempel, Alice.
Og så Alice kan ha en annen pekeren til et annet navn som starter med
A. Og Bob faktisk går over her.
>> Og hvis det er et annet navn som starter med B, ender han opp over her.
Og slik at hver av delene av denne tabell to, hvis vi utviklet dette til en
litt mer smart -
come on -
hvis vi laget denne litt mer smart, blir nå en adaptiv data
struktur, hvor det er ingen hard grense av hvor mange elementer du kan sette inn
inn i det fordi hvis du har en kollisjon, er det fint.
Bare gå videre og legge den til hva vi så litt siden var
kjent som en lenket liste.
>> Vel la oss stoppe opp et lite øyeblikk.
Hva er sannsynligheten for en kollisjon i første omgang?
Høyre, kanskje jeg å tenke over, kanskje Jeg er over Engineering Dette problemet,
fordi du vet hva?
Ja, jeg kan komme opp med vilkårlig eksempler av toppen av hodet mitt som
Allison og Aron, men i virkeligheten, gitt en jevn fordeling av
innganger, som er noen tilfeldige innsettinger inn i en datastruktur, hva er egentlig
sannsynligheten for en kollisjon?
Vel viser seg, er det faktisk super høy.
La meg generalisere dette Problemet er som dette.
>> Så på et rom av n CS50 studenter, hva er sannsynligheten for at minst
to studenter i rommet har samme bursdag?
Så det er hva. noen hund -
200, 300 mennesker her og flere hundre folk hjemme i dag.
Så hvis du ønsker å spørre oss selv hva som er sannsynligheten for to personer
i dette rommet som har samme bursdag, vi kan finne ut av dette.
Og jeg hevder faktisk det er to personer med samme fødselsdag.
>> For eksempel er det noen som har bursdag i dag?
I går?
I morgen?
All right, så det føles som jeg kommer til å gjøre dette 363 eller så mer
ganger for å faktisk finne ut hvis vi har en kollisjon.
Eller vi kan bare gjøre dette matematisk snarere enn ordinært
gjør dette.
Og foreslår følgende.
>> Så jeg foreslår at vi kunne modellere Sannsynligheten for to mennesker som har det
samme fødselsdag som sannsynligheten for en minus sannsynligheten for at ingen har
samme fødselsdag.
Så for å få dette, og dette er bare fancy måte å skrive dette, for
første personen i rommet, han eller hun kan ha en hvilken som helst en av de mulige
bursdager forutsatt 365 dager i året, med unnskyldninger til personer med
februar 29 bursdag.
>> Så den første personen i dette rommet er gratis å ha en rekke bursdager
ut av den 365, slik at mulighetene vi vil gjøre at 365 delt på 365,
som er en.
Den neste personen i rommet, hvis målet er å unngå en kollisjon, kan bare
har hans eller hennes bursdag på hvordan mange forskjellige mulige dager?
364.
Så det andre leddet i dette uttrykket er hovedsak gjør at regnestykket for oss
ved å trekke ut en mulig dag.
Og så den neste dag, neste dag, Neste dag ned til det totale antallet
av mennesker i rommet.
>> Og hvis vi da vurdere, hva er da sannsynligheten ikke fra alle har
unike bursdager, men igjen en minus det, hva vi får er et uttrykk
som kan veldig fancifully se slik ut.
Men det er mer interessant å se på visuelt.
Dette er et diagram der på x-aksen er antall personer i rommet,
antall fødselsdager.
På y-aksen er sannsynligheten av en kollisjon, to personer
har samme fødselsdag.
>> Og takeaway fra denne kurven er at så snart du kommer til å like 40
studenter, er du opp i en 90% sannsynlighet combinatorically av to
personer eller mer har samme fødselsdag.
Og når du kommer til å like 58 mennesker er det nesten 100% av en sjanse de to
personer i rommet skal ha samme fødselsdag, selv om det er
365 eller 366 mulige bøtter, og bare 58 personer i rommet.
Bare statistisk du sannsynligvis til å få kollisjoner, som kort fortalt
motiverer denne diskusjonen.
At selv om vi får fancy her, og begynner å ha disse kjedene, er vi fremdeles
nødt til kollisjoner.
>> Så det ber spørsmålet, hva er kostnadene ved å gjøre innsettinger og slettinger
inn i en datastruktur som dette?
Vel la meg foreslå -
og la meg gå tilbake til skjermen over her - hvis vi har n elementer i
liste, så hvis vi prøver å sette inn n elementer, og vi har
hvor mange totalt bøtter?
La oss si 31 totalt bøtter i tilfelle av fødselsdager.
Hva er den maksimale lengden på en av disse kjedene potensielt?
>> Hvis det er det altså 31 mulige bursdager i en gitt måned.
Og vi er bare klumper alle -
faktisk det er en dum eksempel.
La oss gjøre 26 i stedet.
Så hvis faktisk har folk som har navn starter med A til Z, og dermed gi
oss 26 muligheter.
Og vi bruker en datastruktur som den vi nettopp så, hvor vi har
en rekke pekere, hvorav hver enkelt peker på en lenket liste der
første listen er alle med navnet Alice.
Den andre listen er alle med navn som starter med A, fra
med B, og så videre.
>> Hva den sannsynlige lengden av hvert disse listene hvis vi antar en fin ren
fordeling av navnene A til Z på tvers av hele datastrukturen?
Det er n mennesker i datastruktur delt på 26, hvis de er pent
spredt ut langs hele datastruktur.
Slik at lengden av hver av disse kjedene er n delt på 26.
Men i store O notasjon, hva er det?
Hva er det egentlig?
Så det er egentlig bare n, ikke sant?
Fordi vi har sagt i det siste, at ugh du deler med 26.
Ja, i virkeligheten er det raskere.
Men i teorien, det er ikke fundamentalt alt raskere.
>> Slik at vi ikke ser ut til å være så mye nærmere dette hellige gral.
Faktisk er dette bare lineær tid.
Heck, på dette punktet, hvorfor gjør ikke vi bare bruke en stor lenket liste?
Hvorfor kan ikke vi bare bruke en stor array til å lagre navnene
alle i rommet?
Vel, er det fortsatt noe overbevisende om en hash table?
Er det fortsatt noe overbevisende om en datastruktur
som ser ut som dette?
Dette.
>> STUDENT: [uhørlig].
>> SPEAKER 1: Høyre, og igjen hvis det er bare en lineær tid algoritme, og en
lineær tid datastruktur, hvorfor gjør ikke jeg bare lagre alles navn i en stor
matrise, eller i en stor lenket liste?
Og slutte å lage CS så mye vanskeligere enn den trenger å være?
Hva er overbevisende om dette, selv selv om jeg klødde det ut?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Innsettinger ikke?
Dyrt lenger.
Så innsettinger potensielt kunne fortsatt være konstant tid, selv om dataene
Strukturen ser ut som dette, en rekke pekere er hver av hvilke peker mot
potensielt en lenket liste.
Hvordan kan du oppnå konstant tid innsetting av navn?
Stikke den i fronten, ikke sant?
>> Hvis vi ofrer et design mål fra tidligere, hvor vi ønsket å holde
alles navn, for eksempel, sorteres eller alle av tallene på scenen sortert,
anta at vi har en usortert lenket liste.
Det koster bare oss ett eller to trinn, som i tilfellet med Ben og Brian
tidligere, for å sette inn et element på begynnelsen av listen.
Så hvis vi ikke bryr seg om sortering alle av de navn som starter med A eller alle
navnene som begynner på B, kan vi likevel oppnå konstant tid innsetting.
Nå ser opp Alice eller Bob eller navn mer generelt er fortsatt hva?
Det er stor O n delt på 26, i ideell sak der alle er jevnt
distribuert, hvor det er så mange As som det er Z, som sannsynligvis
urealistisk.
Men det er fortsatt lineær.
>> Men her kommer vi tilbake til det punktet av asymptotisk notasjon være
teoretisk sant.
Men i den virkelige verden, hvis hevder jeg at mitt program kan gjøre noe 26 ganger
raskere enn din, hvis program skal du foretrekker å bruke?
Yours eller mine, som er 26 ganger raskere?
Realistisk, er den personen som 26 ganger raskere, selv om det teoretisk
at algoritmene løpe i samme asymptotisk kjøretid.
>> La meg foreslå en annen løsning helt.
Og hvis dette ikke blåse ditt sinn, vi er ute av datastrukturer.
Så dette er det en trie -
slags dumt navn.
Det kommer fra uttak, og ordet er stavet trie, t-r-i-e, på grunn av
Kurset henting høres ut som trie.
Men det er historie av ordet trie.
>> Så en trie er faktisk noen slags tre, og det er også en spiller på det ordet.
Og selv om du ikke helt kan se det med denne visualiseringen, er et en trie
tre strukturert, som en familie tre med en stamfar på toppen og masse
av barnebarn og oldebarn som blader på bunnen.
Men hver node i et trie er en matrise.
Og det er i en matrise - og la oss oversimplify for et øyeblikk - det er en
matrise, i dette tilfellet, av størrelse 26, hvor hver node er igjen en matrise av størrelse
26, hvor zeroth element i det matrise Å representerer, og den siste
element i hvert slikt matrise representerer Z.
>> Så jeg foreslår da at disse dataene struktur, kjent som en trie, kan bli
brukes også til å lagre ord.
Vi så et øyeblikk siden hvor vi kunne lagre ord, eller i dette tilfellet navnene, og vi
så tidligere hvordan vi kan lagre numre, men hvis vi fokuserer på navn eller strenger
her, legge merke til hva som er interessant.
Jeg hevder at navnet Maxwell er innsiden av denne datastruktur.
Hvor ser du Maxwell?
>> STUDENT: [uhørlig].
>> SPEAKER 1: På venstre.
Så hva er interessant med disse dataene Strukturen er stedet lagre det
streng M-A-X-W-E-L-L skråstrek null, alt contiguously, hva du i stedet gjøre
følger.
Hvis dette er en trie som datastruktur hver av nodene som er igjen en matrise,
og du vil lagre Maxwell, må du først indeks og så root sin node, så
å snakke, den øverste node, ved plassering M, til høyre, så
omtrent i midten.
Og derfra, følger du en pekeren til et barn noder, så å si.
Så i ditt tre forstand, du følger den nedover.
Og som fører deg til en annen node til venstre der, som er
bare en annen array.
>> Og så hvis du ønsker å lagre Maxwell, du finner pekeren som representerer
A, er hvor denne her.
Så går du til neste node.
Og legg merke til - dette er grunnen til at bildets litt villedende -
denne noden ser super bittesmå.
Men til høyre for denne er Y og Z. Det er bare forfatteren har avkortet den
bilde, slik at du faktisk se ting.
Ellers er dette bildet ville være enormt stort.
Så nå indeksen i sted X, deretter W, så E, deretter L, da L. Så hva er
denne nysgjerrigheten?
>> Vel, hvis vi bruker denne typen ny ta om hvordan du lagrer en streng i en
datastruktur, du fortsatt trenger å hovedsak krysse av i data
struktur som et ord slutter her.
Med andre ord, hver av disse nodene en eller annen måte må huske på at vi
faktisk fulgt alle disse pekerne og drar litt
brød smule på bunnen av dette her for å indikere hvilken M-A-X-W-E-L-L er
faktisk i dette datastruktur.
>> Så vi kan gjøre dette på følgende måte.
Hver av nodene i bildet vi bare Sagen har en, en rekke størrelse 27.
Og det er nå 27, fordi i p satt seks, vi vil faktisk gi deg en apostrof,
slik at vi kan ha navn som O'Reilly og andre med apostrofer.
Men samme idé.
Hvert av disse elementer i array-peker til en struct
node, så bare en node.
Så dette er veldig minner av vår lenket liste.
>> Og så har jeg en boolsk, som jeg vil ringe ordet, som bare kommer til å være
sant hvis et ord slutter på dette node i treet.
Det representerer effektivt den lille trekant vi så for et øyeblikk siden.
Så hvis et ord slutter på at node i treet, vil det ordet feltet være sant,
som er konseptuelt krysse av, eller vi trekker denne trekanten, ja det
er et ord her.
>> Så dette er en trie.
Og nå er spørsmålet, hva er kjøretiden?
Er det stort O av n?
Er det noe annet?
Vel, hvis du har n navnene på disse dataene struktur, Maxwell blir bare én av
dem, hva er kjøretiden til innsetting eller finne Maxwell?
Hva er kjøretiden med å sette Maxwell?
Hvis det er n andre navn allerede i tabellen?
Yeah?
>> STUDENT: [uhørlig].
>> SPEAKER 1: Ja, det er lengden av navnet, ikke sant?
Så M-en-x-w-e-l-l så det føles som dette algoritmen er big O på syv.
Nå, selvfølgelig, navnet vil variere i lengde.
Kanskje det er et kort navn.
Kanskje det er en lengre navn.
Men det som er viktig her er at det er et konstant tall.
Og kanskje det er egentlig ikke konstant, men gud, hvis realistisk, i en
ordbok, er det sannsynligvis noen grense på antallet bokstaver i en
personens navn i et bestemt land.
>> Og så kan vi anta at Verdien er en konstant.
Jeg vet ikke hva det er.
Det er trolig større enn vi tror det er.
Fordi det er alltid noen hjørne tilfelle med en gal langt navn.
Så la oss kalle det k, men det er fortsatt et konstant formodentlig, fordi hver
navn i verden, i hvert fall i en bestemt land, er at lengden eller
kortere, slik at den er konstant.
Men når vi har sagt noe er stort O av en konstant verdi, hva er det
egentlig tilsvarer?
Det er egentlig det samme som å si konstant tid.
>> Nå er vi litt juks, ikke sant?
Vi er på en måte å utnytte noen teori her å si at vel, er rekkefølgen på k
egentlig bare bestille ett, og det er konstant tid.
Men det er virkelig.
Fordi det her er viktig innsikt at Hvis vi har observert N navnene allerede i denne
datastruktur, og vi insert Maxwell, er hvor lang tid det tar oss til
Sett Maxwell i det hele tatt berørte av hvor mange andre mennesker
er i datastruktur?
Synes ikke å være.
Hvis jeg hadde en milliard flere elementer i denne trie, og deretter sette Maxwell, er
han i det hele tatt berørt?
Nei.
Og det er i motsetning til noen av dagen data strukturer vi har sett så langt, hvor
kjøretiden til algoritmen din er helt uavhengig av hvor mye
ting er eller ikke allerede ved at datastrukturen.
>> Og så med dette gir deg er nå en mulighet for p seks sett, som vil
igjen innebære å implementere din egen stavekontroll, lesing i 150.000
ord, hvordan best å lagre det er ikke nødvendigvis åpenbar.
Og selv om jeg har håpet på å finne den hellige gral, vet jeg ikke
hevder at en trie er.
Faktisk en hash tabell kan godt vise seg å være mye mer effektiv.
Men de er bare -
det er bare én av design beslutninger du må gjøre.
>> Men i avsluttende la oss ta 50 eller så sekunder for å ta en titt på hva som ligger
videre neste uke og utover vi overgang fra denne kommandolinjen
verden hvis C programmer til ting web basert og språk som PHP og
JavaScript og selve Internett, protokoller som HTTP, som du har satt
tatt for gitt i årevis nå, og skrevet de fleste hver
dag, kanskje, eller sett.
Og vi begynner å skrelle tilbake lag av hva er internett.
Og hva er koden som ligger til grunn for dagens verktøy.
Så 50 sekunder av denne teaseren her.
Jeg gir deg Warriors of the Net.
>> [VIDEOAVSPILLING]
>> -Han kom med et budskap.
Med en protokoll all sin egen.
Han kom til en verden av grusom brannmurer, uncaring rutere, og farer langt
verre enn døden.
Han er rask.
Han er sterk.
Han er TCPIP.
Og han har adressen din.
Warriors of Net.
>> [END VIDEOAVSPILLING]
>> SPEAKER 1: Det er hvordan internett skal arbeide med neste uke.