[Powered by Google Translate] [Uke 6, Fortsatt]
[David J. Malan] [Harvard University]
[Dette er CS50.] [CS50.TV]
Dette er CS50 og dette er slutten av uke 6.
Så CS50x, en av Harvards første kurs involvert i EDX initiativ
faktisk debuterte denne siste mandag.
Hvis du ønsker å få et glimt av hva andre på Internett
følger nå sammen med, kan du ta turen til x.cs50.net.
Det vil omdirigere deg til riktig sted på edx.org,
som var der denne og andre kurs fra MIT og Berkeley nå bor.
Du må registrere deg for en konto, vil du finne at materialet er stort sett det samme
som du har hatt dette semesteret, riktignok et par uker forsinket, så vi får alt klart.
Men hva elevene i CS50x vil nå se er et grensesnitt helt som denne.
Dette, for eksempel, er Zamyla leder walkthrough for oppgavesettet 0.
Ved å logge deg på edx.org, ser en CS50x student slags ting
du forventer å se i en bane: forelesningen for den Mandag,
foredrag for onsdag, ulike shorts, problemet sett, de walkthroughs, PDF-filer.
I tillegg, som du ser her, maskinoversettelser
av engelske karakterutskrifter til kinesisk, japansk, spansk, italiensk,
og en hel haug med andre språk som vil sikkert være ufullkommen
som vi kastet dem ut programmatisk ved hjelp av noe som kalles en API,
eller programmeringsgrensesnitt fra Google
som tillater oss å konvertere engelsk til disse andre språk.
Men takket være den fantastiske ånden av noen hundre pluss frivillige,
tilfeldige folk på internett som har vennlig tilbudt å bli involvert
i dette prosjektet, vil vi gradvis forbedre kvaliteten på disse oversettelsene
ved å ha mennesker korrigere feilene som våre datamaskiner har gjort.
>> Så det viser seg at vi hadde noen flere elever dukker opp på mandag enn vi opprinnelig forventet.
Faktisk, nå CS50x har 100.000 mennesker følger sammen hjemme.
Så skjønner dere er alle en del av dette første klasse for å gjøre dette kurset i informatikk
utdanning mer generelt, i videre forstand, tilgjengelig.
Og realiteten er nå, med noen av disse massive online kurs,
de alle begynner med disse svært høye tall, som vi synes å ha gjort her.
Men målet, til slutt, for CS50x er virkelig å få så mange mennesker til mållinjen som mulig.
Av design, er CS50x kommer til å bli tilbudt fra dette siste mandag
hele veien gjennom 15 April, 2013, slik at folk som har forpliktelser på skolen andre steder,
arbeid, familie, andre konflikter og lignende, har en litt mer fleksibilitet
som å dykke inn dette kurset, som nok det å si,
er ganske ambisiøst gjort hvis bare i løpet av bare tre måneder i løpet av en vanlig semester.
Men disse studentene vil bli takle det samme problemet sett, ser det samme innholdet,
å ha tilgang til de samme shorts og lignende.
Så innser at vi alle er virkelig i dette sammen.
Og en av slutten mål CS50x er ikke bare å få så mange folk
til mållinjen og gi dem denne nyvunne forståelsen av datateknologi
og programmering, men også å ha dem har denne erfaringen.
En av de definerende karakteristikkene av 50 på campus, håper vi,
har vært denne slags felles opplevelse, for bedre eller verre, noen ganger,
men å ha disse menneskene til å vende seg til til venstre og til høyre,
og kontortid og hackathon og virkelig.
Det er litt vanskeligere å gjøre det i person med folk på nettet,
men CS50x vil konkludere i april med den aller første CS50 Expo,
som vil være en online tilpasning av vår idé av virkelig
hvor disse tusenvis av studenter vil alle bli invitert til å sende inn en 1 - til 2-minutters video,
enten en screencast av deres siste prosjekt eller video av dem vinke hallo
og snakker om sitt prosjekt og demoing det,
mye som dine forgjengere har gjort her på campus i messen,
slik at ved semester slutt, er det håp å ha et globalt utstilling
av CS50x studentenes endelige prosjektene, mye som det som venter deg i desember her på campus.
Så mer om det i månedene som kommer.
>> Med 100.000 studenter, men kommer et behov for noen flere sertifiseringsinstanser.
Gitt at dere er flammende stien her og tar CS50
flere uker i forkant av dette materialet ble utgitt til folk på EDX,
innser vi ville elske å involvere så mange av våre egne studenter som mulig i dette initiativet,
både i løpet av semesteret, samt denne vinteren og våren.
Så hvis du ønsker å bli involvert i CS50x,
spesielt bli med på CS50x Diskuter den EDX versjonen av CS50 Diskuter,
som mange av dere har brukt på campus, den elektroniske oppslagstavle,
vennligst hodet til den URL'en, la oss få vite hvem du er,
fordi vi vil gjerne bygge opp et team av studenter og ansatte, og fakultetet både
på campus som er rett og slett spille sammen og hjelpe ut.
Og når de ser et spørsmål som er kjent for dem,
du hører en student rapporterer noen feil sted der ute i noen land på Internett,
og at ringer en bjelle fordi du også hadde det samme problemet
i d-hallen for en tid siden, forhåpentligvis så kan du kiming i og dele din egen erfaring.
Så vennligst ta del hvis du ønsker.
>> Informatikk kurs ved Harvard har litt av en tradisjon,
CS50 blant dem, for å ha noen klær, noen klær, som du kan bære med stolthet
på semesters slutt, sier ganske stolt at du er ferdig CS50
og tok CS50 og lignende, og vi prøver alltid å involvere elevene
i denne prosessen så mye som mulig, hvorved vi inviterer,
rundt denne tiden av semesteret, til studenter levere design
ved hjelp av Photoshop, eller hva verktøy av valget du ønsker å bruke
hvis du er en designer, til å levere design for T-skjorter og gensere
og paraplyer og små bandanas for hunder vi har nå og lignende.
Og alt er så - vinnerne hvert år blir deretter utstilt
på kurset hjemmeside store.cs50.net.
Alt er solgt til kostpris der, men nettstedet bare styrer seg selv
og tillater folk å velge farger og design som de liker.
Så jeg trodde vi ville bare dele noen av fjorårets design
som var på nettsiden i tillegg til dette en her, som er en årlig tradisjon.
"Hver dag jeg Seg Faultn" var en av de anførsler i fjor,
som fortsatt er tilgjengelig der for alumni.
Vi hadde denne, "CS50, Etablert 1989."
En av våre Bowdens, Rob, var svært populær i fjor.
"Team Bowden" ble født, ble dette designet fremlagt, blant de beste selgerne.
Som var denne her. Mange folk hadde "Bowden Fever" i henhold til salg loggene.
Innse at det kan nå være din design der, opp på internett.
Flere detaljer om dette i neste problemet setter framover.
>> Et ekstra verktøy: du har hatt noen eksponering og forhåpentligvis nå
noen hands-on erfaring med GDB,
som er, selvfølgelig, en debugger, og lar deg manipulere
programmet på et relativt lavt nivå, gjør hva slags ting?
Hva lar GDB du gjøre?
Ja? Gi meg noe. [Student svar, uforståelig]
Bra. Step into funksjon, slik at du ikke bare å skrive kjøre
og har programmet blåse gjennom sin helhet, skrive ut ting til standard ut.
Snarere, kan du gå gjennom den linje for linje, enten skrive neste
å gå linje for linje for linje eller trinn å dykke inn i en funksjon, typisk en som du skrev.
Hva annet lar GDB du gjøre? Ja? [Student svar, uforståelig]
Skriv ut variabler. Så hvis du ønsker å gjøre litt introspeksjon innsiden av programmet
uten å måtte ty til å skrive printf uttalelser over alt,
du kan bare skrive ut en variabel eller vise en variabel.
Hva annet kan du gjøre med en debugger som GDB?
[Student svar, uforståelig]
Akkurat. Du kan angi stoppunkt, du kan si pause kjøring
på de viktigste funksjon eller foo funksjonen.
Du kan si pause kjøring på linje 123.
Og stoppunkter er en virkelig kraftig teknikk
fordi hvis du har en generell følelse av hvor problemet
sannsynligvis er, trenger du ikke å kaste bort tid stepping gjennom programmet sin helhet.
Du kan faktisk hoppe rett der og deretter begynne å skrive -
stepping gjennom den med trinn eller neste eller lignende.
Men fangsten med noe sånt GDB er at det hjelper deg, det menneskelige,
finne dine problemer og finne bugs.
Det betyr ikke nødvendigvis finne dem så mye for deg.
>> Så vi introduserte den andre dagen style50, som er en kort kommandolinjeverktøy
som prøver å stilisere koden litt mer renslig enn deg, menneske, kan ha gjort.
Men det også, er egentlig bare en estetisk ting.
Men det viser seg at det er denne andre verktøy kalt Valgrind som er litt mer uforståelige å bruke.
Produksjonen er atrociously kryptisk ved første øyekast.
Men det er fantastisk nyttig, spesielt nå som vi er på den delen av begrepet
hvor du begynner å bruke malloc og dynamisk minne allokering.
Ting kan gå veldig, veldig galt raskt.
Fordi hvis du glemmer å frigjøre minne, eller dereferanse du noen NULL-peker,
eller du dereferanse noen søppel pekeren, hva er typisk symptom som resulterer?
Seg feil. Og du får denne kildefilen av et antall kilobyte eller megabyte
som representerer staten programmet minne når det krasjet,
men programmet til slutt SEG feil, segmentering feil,
som betyr noe dårlig skjedde nesten alltid relatert
til et minne-relatert feil at du har gjort et eller annet sted.
Så Valgrind hjelper deg å finne ting som dette.
Det er et verktøy som du kjører, som GDB, etter at du har samlet programmet,
men i stedet for å kjøre programmet direkte, kjører du Valgrind
og du passerer til det programmet, akkurat som du gjør med GDB.
Nå bruken, for å få den beste form for produksjon,
er litt lang, så der oppå av skjermen vil du se Valgrind-v.
"-V" nesten universelt betyr verbose når du bruker programmer på en Linux-datamaskin.
Så det betyr spytte ut flere data enn du kanskje som standard.
"- Lekkasje-sjekk = full." Dette er bare å si sjekk for alle mulige minnelekkasjer,
feil som jeg kunne ha gjort. Også dette er en vanlig paradigme med Linux-programmer.
Vanligvis, hvis du har en kommandolinje argument som er en "bryter",
som er ment å endre programmets oppførsel, og det er en enkelt bokstav,
det er-v, men hvis det er slått, bare ved utforming av programmerer,
er et helt ord eller serie av ord, begynner Kommandolinjeargumentet med -.
Dette er bare menneskelige konvensjoner, men du vil se dem stadig.
Og så, til slutt, "a.out" er tilfeldig navn for programmet i dette eksempelet.
Og her er noen representative utgang.
>> Før vi ser på hva det kan bety, la meg gå over til en kodebit over her.
Og la meg flytte dette ut av veien, kommer snart,
og la oss ta en titt på memory.c, som er denne korte eksempel her.
Så i dette programmet, la meg zoome inn på de funksjoner og spørsmål.
Vi har en funksjon hoved som kaller en funksjon, f,
og hva går videre f å gjøre, i litt teknisk engelsk?
Hva fortsette f å gjøre?
Hva om jeg skal begynne med linje 20, og stjernens sted spiller ingen rolle,
men jeg vil bare være konsekvent her med siste forelesning.
Hva er linje 20 gjør for oss? På den venstre side. Vi vil bryte det ned ytterligere.
Int * x: hva gjør det?
Okay. Det erklærer en peker, og la oss nå være enda mer teknisk.
Hva betyr det, veldig konkret, for å erklære en peker? Noen andre?
Ja? [Student svar, uforståelig] For langt.
Så du leser til høyre side av likhetstegnet.
La oss fokusere bare på venstre, bare på int * x.
Dette betyr "erklærer" en peker, men nå la oss dykke dypere til denne definisjonen.
Hva betyr det konkret, teknisk bety? Ja?
[Student svar, uforståelig]
Okay. Det er forbereder å lagre en adresse i minnet.
Bra. Og la oss ta dette et skritt videre, det er å erklære en variabel, x, som er 32 biter.
Og jeg vet det er 32 bits fordi -?
Det er ikke fordi det er en int, fordi det er en peker i dette tilfellet.
Tilfeldighet at det er ett og det samme med en int,
men det faktum at det er stjernen det betyr at dette er en peker
og i apparatet, som med mange datamaskiner, men ikke alle, pekere er 32 biter.
På mer moderne maskinvare som den nyeste Mac, de nyeste PC-er, kan du ha 64-bit pekere,
men i apparatet, disse tingene er 32 bits.
Så vi vil standardisere på det. Mer konkret går historien som følger:
Vi "erklærer" en peker, hva betyr det?
Vi forbereder å lagre et minne adresse.
Hva betyr det?
Vi skaper en variabel kalt x som tar opp 32 biter
som snart lagre adressen for et heltall.
Og det er sannsynligvis omtrent like presis som vi kan få.
Det er greit fremover for å forenkle verden og bare si erklære en peker som heter x.
Erklærer en peker, men skjønner og forstår hva som faktisk skjer
selv i bare disse tegnene.
>> Nå er dette en nesten litt lettere, selv om det er en lengre uttrykk.
Så hva er dette å gjøre, det er markert nå: "malloc (10 * sizeof (int));" Yeah?
[Student svar, uforståelig]
Bra. Og jeg vil ta det der. Det er tildeling av en del av minnet for ti heltall.
Og la oss nå dykke i litt dypere, det er tildeling av en del av minnet for ti heltall.
Hva er malloc deretter retur?
Adressen til del, eller mer konkret, adressen til den første byte som del.
Hvordan blir jeg, programmerer, for å vite hvor det blings av minne ender?
Jeg vet at det er sammenhengende. Malloc, per definisjon, vil gi deg en sammenhengende del av minnet.
Ingen hull i den. Du har tilgang til hver byte i det blings,
rygg mot rygg til rygg, men hvordan vet jeg hvor slutten av denne del av minnet er?
Når du bruker malloc? [Student svar, uforståelig] Bra.
Du gjør ikke det. Du må huske.
Jeg må huske at jeg brukte verdien 10, og jeg vet ikke engang synes å ha gjort det her.
Men onus er helt på meg. Strlen, som vi har blitt litt avhengig av for strykere,
fungerer bare på grunn av denne konvensjonen til å ha \ 0
eller denne spesielle nul karakter, NUL, på slutten av en streng.
Det holder ikke for bare vilkårlige mengder minne.
Det er opp til deg. Så linje 20, så tildeler en del av minnet
som kan lagre ti heltall, og den lagrer adressen til den første byte
av at del av minnet i variabelen x.
Ergo, som er en peker. Så line 21, dessverre var en feil.
Men først, hva er det du gjør? Det sier butikken på 10 plassering, 0 indeksert,
av del av minnet som kalles x verdien 0.
>> Så merke til et par ting skjer.
Selv om x er en peker, husker fra et par uker siden
at du kan fortsatt bruke array-stil hakeparentes notasjon.
Fordi det er faktisk kort hånd notasjon for mer kryptiske utseende pekeren aritmetikk.
der vi ville gjøre noe som dette: Ta adresse x, flytte 10 punkter over,
så går det til hva adressen lagres på denne plasseringen.
Men ærlig, dette er bare fryktelig å lese og bli komfortabel med.
Så verden bruker vanligvis klammeparentesene bare fordi det er så mye mer human-vennlig å lese.
Men det er det som egentlig skjer under panseret;
x er en adresse, ikke en matrise, per se.
Så dette er lagring 0 på stedet 10 i x.
Hvorfor er dette dårlig? Ja?
[Student svar, uforståelig] Nettopp.
Vi bare tildelt ti ints, men vi telle fra 0 når programmering i C,
slik at du har tilgang til 0 1 2 3 4 5 6 7 8 9, men ikke 10.
Så enten programmet skal SEG feil eller er det ikke.
Men vi vet egentlig ikke, dette er liksom en nondeterministic atferd.
Det er egentlig avhengig av om vi får heldig.
Hvis det viser seg at operativsystemet ikke tankene hvis jeg bruker det ekstra byte,
selv om det ikke har gitt det til meg, kanskje mitt program ikke krasje.
Det er rått, det er buggy, men du kan ikke se at symptom,
eller du kan bare se den en gang i blant.
Men realiteten er at feilen er, faktisk, det.
Og det er virkelig problematisk hvis du har skrevet et program som du ønsker å være riktig,
at du har solgt programmet som folk bruker at hver gang en stund krasjer
fordi, selvfølgelig, dette er ikke bra. Faktisk, hvis du har en Android-telefon eller en iPhone
og du laster ned apps i disse dager, hvis du noen gang har hatt en app bare slutte,
plutselig forsvinner, er det nesten alltid et resultat av noen minne-relatert problem,
der programmerer skrudd opp og derefereres en peker
at han eller hun ikke skal ha, og resultatet av iOS eller Android, er å bare drepe programmet helt
heller enn å risikere udefinert atferd eller noen form for sikkerhet kompromiss.
>> Det er en annen bug i dette programmet foruten denne.
Hva annet har jeg skrudd opp i dette programmet?
Jeg har ikke praktisert det jeg har forkynt. Ja?
[Student svar, uforståelig] Bra.
Jeg har ikke frigjort minnet. Så tommelfingerregel nå
må være når du kaller malloc, må du ringe gratis når du er ferdig med å bruke dette minnet.
Nå vil når jeg vil frigjøre dette minnet?
Sannsynligvis, antar dette første linjen var riktig, ville jeg ønsker å gjøre det her.
Fordi jeg ikke kunne, for eksempel, gjør det her nede. Hvorfor?
Bare ut av omfanget. Så selv om vi snakker om pekere,
dette er en uke to eller 3 utgave, der x er kun i omfang innsiden av klammeparentes der det ble erklært.
Så du definitivt ikke kan frigjøre den der. Min eneste sjanse til å frigjøre det er omtrent etter linje 21.
Dette er en ganske enkel program, det var ganske lett når du slags innpakket tankene
rundt hva programmet gjør, hvor feilene var.
Og selv om du ikke ser den først, forhåpentligvis er det litt opplagt nå
at disse feilene er ganske lett løses og enkelt gjort.
Men når et program er mer enn 12 linjer lang, er det 50 linjer lang, 100 linjer lang,
vandre gjennom koden linje for linje, tenke gjennom det logisk,
er mulig, men ikke særlig morsomt å gjøre, stadig på jakt etter feil,
og det er også vanskelig å gjøre, og det er derfor et verktøy som Valgrind eksisterer.
La meg gå videre og gjøre dette: la meg åpne min terminal-vinduet,
og la meg ikke bare kjøre minne, fordi minnet synes å være i orden.
Jeg får heldig. Gå til at ekstra byte ved slutten av tabellen
synes ikke å være for problematisk.
Men la meg likevel, gjør en mental helse sjekk, som bare betyr å sjekke
hvorvidt dette er faktisk riktig.
>> Så la oss gjøre Valgrind-v - lekkasje-sjekk = full,
og deretter navnet på programmet i dette tilfellet er minne, ikke a.out.
Så la meg gå videre og gjøre dette. Trykk Enter.
Kjære Gud. Dette er dens utgang, og dette er hva jeg antydet tidligere.
Men, hvis du lærer å lese gjennom alle de tull her,
meste av dette er bare diagnostisk resultat som ikke er så interessant.
Hva øyet virkelig ønsker å være på jakt etter er noen omtale av feil eller ugyldig.
Ord som tyder problemer.
Og ja, la oss se hva som går galt her nede.
Jeg har en oppsummering av noe slag, "i bruk ved avkjørsel:. 40 bytes i en blokker"
Jeg er ikke helt sikker på hva en blokk er ennå, men 40 bytes
faktisk føles som om jeg kunne finne ut hvor det kommer fra.
40 byte. Hvorfor er 40 byte i bruk ved avkjørsel?
Og mer spesifikt, hvis vi bla nedover her,
hvorfor har jeg definitivt mistet 40 bytes? Ja?
[Student svar, uforståelig] Perfect. Ja, akkurat.
Det var ti heltall, og hver av dem er størrelsen på fire, eller 32 biter,
så jeg har mistet nøyaktig 40 bytes fordi, som du foreslo, jeg har ikke kalles gratis.
Det er en bug, og nå la oss se litt nedover og se ved siden av dette,
"Ugyldig skrive av størrelse 4". Nå hva er dette?
Denne adressen er uttrykt hva basen notasjon, tilsynelatende?
Dette er heksadesimal, og hver gang du ser en som starter med 0x,
det betyr heksadesimal, som vi gjorde helt tilbake i, tror jeg, pset 0-delen av spørsmål,
som var bare for å gjøre en warmup trening, konvertere desimal til hex til binær og så videre.
Heksadesimal, bare av menneskelig konvensjonen, er vanligvis brukes til å representere pekere
eller, mer generelt, adresser. Det er bare en konvensjon,
fordi det er litt lettere å lese, er det litt mer kompakt enn noe sånt som desimal,
og binære er ubrukelig for de fleste mennesker å bruke.
Så nå hva betyr dette? Vel, det ser ut som om det er en ugyldig skrive
av størrelse 4 på linje 21 av memory.c.
Så la oss gå tilbake til linje 21, og ja, her er det ugyldig skrive.
Så Valgrind ikke kommer til å helt holde meg i hånden og fortelle meg hva reparasjonen er,
men det er å oppdage at jeg gjør en ugyldig skrive.
Jeg berøre 4 byte at jeg ikke skulle være, og tilsynelatende det er fordi,
som du påpekte, jeg gjør [10] i stedet for [9] maksimalt
eller [0] eller noe midt i mellom.
Med Valgrind, innser helst du nå skriver et program
som bruker pekere og bruker minne og malloc mer spesifikt,
definitivt komme inn i vanen med å kjøre denne lange
men veldig lett kopieres og limes inn kommandoen over Valgrind
for å se om det er noen feil i det.
Og det vil være overveldende hver gang du ser resultatet,
men bare analysere gjennom visuelt all produksjon og se om du ser nevner av feil
eller advarsler eller ugyldig eller tapt.
Noen ord som høres ut som du skrudd opp et sted.
Så skjønner det er et nytt verktøy i verktøykassen din.
>> Nå på mandag, hadde vi en hel haug med folk kommer opp hit
og representerer oppfatningen av en lenket liste.
Og vi introduserte lenket liste som en løsning på hva problemet?
Ja? [Student svar, uforståelig] Bra.
Arrays kan ikke ha minnet som er lagt til dem.
Hvis du tildeler en rekke størrelse 10, det er alt du får.
Du kan kalle en funksjon som RealLOC hvis du opprinnelig kalt malloc,
og som kan prøve å vokse tabellen hvis det er plass mot slutten av det
at ingen andre bruker, og hvis det ikke er det, vil det bare finne deg en større del et annet sted.
Men så det vil kopiere alle disse byte inn i det nye utvalget.
Dette høres ut som en veldig riktig løsning.
Hvorfor er dette unattractive?
Jeg mener det fungerer, har mennesker løst dette problemet.
Hvorfor gjorde vi trenger å løse det på mandag med koblede lister? Ja?
[Student svar, uforståelig] Det kan ta lang tid.
Faktisk, når som helst du ringer malloc eller RealLOC eller calloc, som er enda en,
hver gang du, programmet, snakker med operativsystemet,
du har en tendens til å bremse programmet ned.
Og hvis du gjør slike ting i looper, er du virkelig bremse ting ned.
Du kommer ikke til å legge merke til dette for den enkleste av "Hello World" type programmer,
men i mye større programmer, spør operativsystemet igjen og igjen for minne
eller gi den tilbake igjen og igjen har en tendens til ikke å være en god ting.
Dessuten er det bare en slags intellektuelt - det er en fullstendig bortkastet tid.
Hvorfor bevilge mer og mer minne, risiko kopiering alt inn i den nye matrisen,
hvis du har et alternativ som lar deg tildele bare så mye minne som du faktisk trenger?
Så det er plusser og minuser i her.
En av de positive nå er at vi har dynamikk.
Spiller ingen rolle hvor biter av minnet er er at gratis,
Jeg kan bare liksom lage disse brødsmuler via pekere
å henge hele mitt lenket liste sammen.
Men jeg betaler minst én pris.
>> Hva må jeg gjøre for å gi opp i å få koblet lister?
Ja? [Student svar, uforståelig] Bra.
Du trenger mer minne. Nå trenger jeg plass til disse pekerne,
og i tilfelle av denne super enkle lenket liste
som bare prøver å lagre heltall, som er 4 byte, holder vi si
vel, er en peker fire bytes, så nå har jeg bokstavelig talt doblet
hvor mye minne trenger jeg bare å lagre denne listen.
Men igjen, dette er en konstant tradeoff i informatikk
mellom tid og rom og utvikling, innsats og andre ressurser.
Hva er en annen ulempe med å bruke en lenket liste? Ja?
[Student svar, uforståelig]
Bra. Ikke så lett å få tilgang. Vi kan ikke lenger utnytte
uke 0 prinsipper som splitt og hersk.
Og mer spesifikt, binær søk. For selv om vi mennesker
kan se omtrent hvor midten av denne listen er,
maskinen vet bare at dette lenket liste starter på adresse som kalles først.
Og det er 0x123 eller noe sånt.
Og den eneste måten programmet kan finne midten element
er å faktisk søke på hele listen.
Og selv da har det bokstavelig talt å søke på hele listen fordi
selv når du har nådd midten element ved å følge pekere,
deg, programmet, har ingen anelse om hvor lenge denne listen er, potensielt,
før du treffer slutten av det, og hvordan vet du programmatisk
at du er på slutten av en lenket liste?
Det er en spesiell NULL-peker, så igjen, en konvensjon.
Snarere enn å bruke denne pekeren, vi definitivt ikke ønsker at det skal være noen søppel verdi
peker av scenen et sted, vi ønsker den skal være hånden ned, NULL,
slik at vi har denne endestasjonen i denne datastruktur slik at vi vet hvor det ender.
>> Hva hvis vi ønsker å manipulere dette?
Vi gjorde det meste av dette visuelt, og med mennesker,
men hva om vi ønsker å gjøre en innsetting?
Så den opprinnelige listen var 9, 17, 20, 22, 29, 34.
Hva hvis vi da ønsket å malloc plass til nummer 55, en node for det,
og vi vil sette 55 inn på listen akkurat som vi gjorde på mandag?
Hvordan gjør vi dette? Vel, kom Anita og hun egentlig gikk listen.
Hun startet på det første elementet, så neste, neste, neste, neste, neste.
Endelig traff venstre hele veien ned
og realisert oh, dette er NULL. Så hva pekeren manipulasjon måtte gjøres?
Personen som var på slutten, nummer 34, trengte hans venstre hånd hevet
å peke på 55, trengte 55 sin venstre arm peker ned for å bli den nye NULL terminator. Ferdig.
Ganske enkelt å sette 55 i en sortert liste.
Og hvordan kan dette se ut?
>> La meg gå videre og åpne opp noen kode eksempel her.
Jeg vil åpne opp gedit, og la meg åpne opp to filer først.
En er list1.h, og la meg bare minne om at dette var del av koden
som vi brukte til å representere en node.
En node har både en int kalt n og en peker som heter neste som bare peker til neste ting på listen.
Det er nå i en. H fil. Hvorfor?
Det er denne konvensjonen, og vi har ikke tatt fordel av dette et stort beløp oss selv,
men personen som skrev printf og andre funksjoner
ga som gave til verden alle disse funksjonene ved å skrive en fil som heter stdio.h.
Og så er det string.h, og så er det map.h, og det er alle disse h-filene
som du kanskje har sett eller brukt under begrepet skrevet av andre mennesker.
Typisk i disse. H-filer er bare ting som typedefs
eller erklæringer av tilpassede typer eller erklæringer av konstanter.
Du trenger ikke sette funksjoner 'implementeringer i header-filer.
Du setter i stedet, bare sine prototyper.
Du setter ting du ønsker å dele med verden hva de trenger
for å kompilere koden sin. Så bare for å komme inn i denne vanen,
vi besluttet å gjøre det samme. Det er ikke mye i list1.h,
men vi har satt noe som kan være av interesse for folk i hele verden
som ønsker å bruke våre lenket liste gjennomføring.
Nå, i list1.c, jeg vil ikke gå gjennom hele denne greia
fordi det er litt lang, dette programmet, men la oss kjøre det virkelige raskt ved ledeteksten.
La meg kompilere liste1, la meg deretter kjøre liste1, og hva du vil se er
vi har simulert en enkel liten programmet her
som kommer til å tillate meg å legge til og fjerne numre i en liste.
Så la meg gå videre og skrive 3 for menyvalget 3.
Jeg ønsker å sette inn nummer - la oss gjøre det første tallet, som var 9,
og nå er jeg fortalt listen er nå 9.
La meg gå videre og gjøre en annen innsetting, så jeg traff menyvalget 3.
Hvilket nummer ønsker jeg å sette? 17.
Enter. Og jeg vil gjøre bare én.
La meg sette nummer 22.
Så vi har begynnelse av lenket liste som vi hadde i lysbilde skjema for et øyeblikk siden.
Hvordan er dette innsetting faktisk skjer?
Faktisk, er 22 nå ved slutten av listen.
Så den historien vi fortalte på scenen på mandag og recapped akkurat nå
må faktisk skje i koden.
La oss ta en titt. La meg bla nedover i denne filen.
Vi vil glatte over noen av funksjonene,
men vi vil gå ned til, si, innsatsen funksjonen.
>> La oss se hvordan vi går om å sette inn en ny node i denne lenket liste.
Hvor er listen erklært? Vel, la oss rulle hele veien opp på toppen,
og legge merke til at min lenket liste er egentlig erklært som en enkelt peker som er utgangspunktet NULL.
Så jeg bruker en global variabel her, som generelt har vi forkynt mot
fordi det gjør koden litt rotete å vedlikeholde,
Det er liksom lat, vanligvis, men det er ikke lat, og det er ikke galt, og det er ikke dårlig
hvis programmet eneste mål i livet er å simulere en lenket liste.
Som er akkurat hva vi gjør.
Så i stedet for å erklære dette i main og deretter måtte gi det til hver funksjon
vi har skrevet i dette programmet, vi i stedet innse oh, la oss bare gjøre det globale
fordi hele hensikten med dette programmet er å demonstrere én og bare én lenket liste.
Så det føles greit. Her er mine prototyper, og vi vil ikke gå gjennom alle disse,
men jeg skrev en slett-funksjon, en finne funksjon, et innstikk funksjon, og en travers funksjon.
Men la oss nå gå tilbake til innsatsen funksjonen
og se hvordan dette fungerer her.
Innsatsen er på linje - here we go.
Sett inn. Slik at den ikke tar noen argumenter, fordi vi kommer til å be
brukeren innsiden av denne funksjonen for antall de ønsker å sette inn.
Men først, forbereder vi å gi dem litt plass.
Dette er liksom kopiere og lime inn fra den andre eksempel.
I så fall var vi fordele en int, denne gangen vi fordele en node.
Jeg vet egentlig ikke huske hvor mange byte en node er, men det er fint.
Sizeof kan finne det ut for meg.
Og hvorfor er jeg sjekker for NULL i linje 120?
Hva kan gå galt i tråd 119? Ja?
[Student svar, uforståelig]
Bra. Bare kunne være tilfelle at jeg har bedt om for mye minne
eller noe er galt og operativsystemet ikke har nok byte til å gi meg,
så det signaliserer så mye ved retur NULL, og hvis jeg ikke se etter at
og jeg bare blindt fortsette å bruke adressen tilbake, kan det være NULL.
Det kan være noen ukjent verdi, ikke en god ting med mindre jeg -
faktisk vil ikke være en ukjent verdi. Det kan være NULL, så jeg ønsker ikke
å misbruke det og risikere dereferencing det.
Hvis det skjer, jeg bare gå tilbake og vi vil late som om jeg ikke får tilbake noe minne i det hele tatt.
>> Ellers har jeg fortelle brukeren gi meg et nummer for å sette inn, kaller jeg vår gamle venn GetInt,
og så dette var den nye syntaksen vi introdusert på mandag.
'Newptr-> n' betyr å ta den adressen du fikk av malloc
som representerer den første byte av en ny node objekt,
og deretter gå til feltet som heter n.
Litt trivia spørsmål: Dette tilsvarer hva mer kryptisk kodelinje?
Hvordan ellers kunne jeg ha skrevet dette? Ønsker du å ta et stikk?
[Student svar, uforståelig]
Bra. Bruke. N, men det er ikke fullt så enkelt som dette.
Hva gjør jeg først må gjøre? [Student svar, uforståelig]
Bra. Jeg trenger å gjøre * newptr.n.
Så dette sier ny pekeren er åpenbart en adresse. Hvorfor?
Fordi det ble returnert av malloc. Den * newptr sier "gå dit"
og deretter en gang du er der, så kan du bruke mer kjent. n,
men dette ser bare litt stygg, spesielt hvis vi mennesker kommer til å
tegne pekere med piler hele tiden, verden har standardisert på denne pilen notasjon,
som gjør akkurat det samme.
Så du bare bruke -> notasjon når ting på venstre er en peker.
Ellers, hvis det er en faktisk struct, bruker. N.
Og så dette: Hvorfor initialisere jeg newptr-> neste til NULL?
Vi ønsker ikke en dinglende venstre hånd ut av slutten av etappen.
Vi ønsker at det peker rett ned, noe som betyr slutten på denne listen
kan potensielt være på denne noden, slik at vi bedre sørge for at det er NULL.
Og generelt, initialiseres variabler eller dine data medlemmer og structs
til noe er bare god praksis.
Bare la søppel eksisterer og fortsetter å eksistere generelt får deg i trøbbel
Hvis du glemmer å gjøre noe senere.
>> Her er noen få tilfeller. Dette, igjen, er innsatsen funksjonen,
og det første jeg se etter er om variabel kalt først,
at global variabel er NULL, betyr at det er ingen lenket liste.
Vi har ikke satt noen tall, så det er trivielt å sette denne aktuelle nummeret
inn på listen, fordi den tilhører bare ved starten av listen.
Så dette var da Anita ble bare stående her oppe alene, late
ingen andre var her oppe på scenen før vi tildelt en node,
så hun kunne løfte hånden for første gang,
hvis alle andre hadde kommet opp på scenen etter henne på mandag.
Nå her, dette er en liten sjekk hvor jeg har å si om den nye nodens verdi av n
er <verdien av n i gjeldende første noden,
det betyr at det er en lenket liste som er begynt.
Det er minst én node i listen, men denne nye fyren
hører før det, så vi trenger å flytte ting rundt.
Med andre ord, hvis listen har startet med bare, la oss si,
bare nummer 17, som er den - faktisk, kan vi gjøre dette mer tydelig.
Hvis vi starter vår historie med en peker her kalt først,
og i utgangspunktet er det NULL, og vi setter inn tallet 9,
tallet 9 tilhører tydelig ved starten av listen.
Så la oss late som vi bare malloced adressen eller tallet 9 og sette den her.
Hvis første er 9 som standard, betyr det første scenariet vi diskuterte bare la oss poeng denne fyren her,
la dette som NULL, nå har vi nummer 9.
Neste nummer vil vi sette inn er 17..
17 tilhører over her, så vi er nødt til å gjøre noen logisk stepping gjennom dette.
Så la oss i stedet, før vi gjør det, la oss late som vi ønsket å sette inn nummer åtte.
>> Så bare for enkelhets skyld, jeg kommer til å trekke her.
Men husk, kan malloc sette den de fleste steder.
Men for tegning skyld, vil jeg si det her.
Så late som jeg har nettopp tildelt en node for nummer 8, og dette er NULL som standard.
Hva må nå skje? Et par ting.
Vi har gjort dette feil på scenen på mandag hvor vi oppdatert en peker som dette,
Deretter gjorde dette, og da vi hevdet - vi foreldreløse alle andre på scenen.
Fordi du L ° vernes - rekkefølgen av operasjoner her er viktig,
fordi nå har vi mistet denne noden 9 som er bare slags flyter i verdensrommet.
Så dette var ikke den rette tilnærmingen på mandag.
Vi først må gjøre noe annet.
Delstaten verden ser slik ut. Utgangspunktet, 8 er blitt tildelt.
Hva ville være en bedre måte å sette 8?
Stedet for å oppdatere denne pekeren første, bare oppdatere denne her i stedet.
Så vi trenger en linje med kode som kommer til å snu denne NULL karakter
til en faktisk peker som er peker på node 9,
og da kan vi trygt endre først å peke på denne fyren her.
Nå har vi en liste, en lenket liste, av to elementer.
Og hva betyr dette egentlig ser ut her?
Hvis vi ser på koden, merker at jeg har gjort akkurat det.
Jeg har sagt newptr, og i denne historien, ble newptr peker på denne fyren.
>> Så la meg trekke en ting, og jeg burde ha igjen litt mer rom for dette.
Så tilgi bitte liten tegning.
Denne fyren heter newptr.
Det er variabelen vi erklært noen linjer tidligere, i tråd - like over 25.
Og den peker til 8. Så når jeg sier newptr-> neste, som betyr å gå til struct
som blir pekt på av newptr, så her er vi, gå dit.
Da pilen sier få det neste feltet, og deretter = sier sette hvilken verdi det?
Verdien som var i første, hva verdien var i først?
Først var peker på denne noden, så det betyr at dette bør nå peke på denne noden.
Med andre ord, ser det riktignok en latterlig rot med håndskrift min,
hva er en enkel idé om bare å flytte disse pilene rundt
oversettes til kode med bare denne ene liner.
Lagre hva som er i først i det neste feltet og deretter oppdatere hva første faktisk er.
La oss gå videre og spole fremover gjennom noe av dette,
og ser bare på dette halen innsetting for nå.
Anta jeg får til det punktet hvor jeg synes at det neste feltet av noen node er NULL.
Og på dette punktet i historien, en detalj som jeg glatter over
er at jeg har introdusert en annen pekeren opp her i 142 linje, forgjenger pekeren.
Hovedsak, på dette punktet i historien, når listen blir lang,
Jeg slags behov for å gå den med to fingre fordi hvis jeg går for langt,
husk i en enkelt lengde, kan du ikke gå bakover.
Så denne ideen predptr er min venstre finger, og newptr - ikke newptr.
En annen peker som er her er min andre finger, og jeg er bare slags vandre listen.
Det er derfor det finnes. Men la oss bare vurdere en av de enklere sakene her.
Hvis det pekerens neste felt er NULL, hva er den logiske implikasjon?
Hvis du er traversing denne listen og du treffer en NULL-peker?
Du er på slutten av listen, og så koden for å deretter legge dette en ekstra element
er liksom den intuitive vil ta den noden som neste pekeren er NULL,
så dette er tiden NULL, og endre den, men å være adressen til den nye noden.
Så vi bare tegne i koden pilen som vi trakk på scenen ved å heve noens venstre hånd.
>> Og saken som jeg vil vinke hendene mine på for nå,
bare fordi jeg tror det er lett å gå seg vill når vi gjør det i denne typen miljø,
sjekker for innsetting på listens midten.
Men bare intuitivt, hva må skje hvis du ønsker å finne ut
hvor noen nummeret tilhører i midten er du nødt til å gå den
med mer enn én finger, mer enn én pekeren,
finne ut hvor den hører hjemme ved kontroll er element <den nåværende,
> Den nåværende, og når du finner dette stedet,
så må du gjøre denne typen skallet spill hvor du beveger pekere rundt svært nøye.
Og det svaret, hvis du ønsker å resonnere gjennom dette hjemme på egen hånd,
koker ned bare til disse to linjene med kode, men rekkefølgen på disse linjene er super viktig.
Fordi hvis du slipper noens hånd og heve en annens i feil rekkefølge,
igjen, kan du ende opp orphaning listen.
Å oppsummere mer konseptuelt, er innsetting på halen relativt enkelt.
Innsetting på hodet er også relativt enkelt,
men du må oppdatere en ekstra peker denne gangen
å presse nummer 5 i listen her,
og deretter innsetting i midten omfatter enda mer innsats,
til veldig forsiktig sette nummer 20 i sin korrekte sted,
som er mellom 17 og 22.
Så du trenger å gjøre noe som har den nye noden 20 poeng til 22,
og deretter må som nodens pekeren for å bli oppdatert sist?
Det er 17, å faktisk sette det inn.
Så igjen, jeg utsette den faktiske koden for den aktuelle gjennomføring.
>> Ved første øyekast, er det litt overveldende, men det er egentlig bare en uendelig løkke
som er looping, looping, looping, looping, og bryte så snart du treffer NULL-peker,
på hvilket tidspunkt du kan gjøre de nødvendige innsetting.
Dette er altså representativt lenket liste koden for innsetting.
Det var snilt av mye, og det føles som vi har løst et problem,
men vi har innført en helt annen en. Oppriktig, vi har brukt all denne tiden
på stor O og Ω og kjører tid, prøver å løse problemer raskere,
og her tar vi et stort skritt bakover, det føles.
Og likevel, hvis målet er å lagre data,
det føles som den hellige gral, som vi sa på mandag, ville virkelig være
å lagre ting umiddelbart.
>> Faktisk anta at vi gjorde satt til side lenket liste for et øyeblikk
og vi i stedet introduserte begrepet i en tabell.
Og la oss bare tenke på en tabell for et øyeblikk som en matrise.
Denne tabellen og denne saken her har ca 26 elementer, 0 til 25,
og anta at du trengte noen del av lagringsplass for navn:
Alice og Bob og Charlie og lignende.
Og du trenger litt datastruktur for å lagre disse navnene.
Vel, du kan bruke noe sånt som en lenket liste
og du kan gå listen sette Alice før Bob og Charlie etter Bob og så videre.
Og, faktisk, hvis du ønsker å se kode sånn som en side,
vet at i list2.h, gjør vi akkurat det.
Vi vil ikke gå gjennom denne koden, men dette er en variant av det første eksempelet
som introduserer en annen struct vi har sett før kalt student,
og hva det faktisk lagrer i lenket liste er en peker til en student struktur
snarere enn en enkel liten heltall.
Så skjønner det er kode det som involverer faktiske strenger,
men hvis målet på hånden virkelig nå er å ta effektiviteten problem,
ville det ikke vært fint hvis vi får et objekt kalt Alice,
Vi ønsker å sette henne inn på riktig sted i en datastruktur,
det føles som om det ville være veldig hyggelig å bare sette Alice,
med navn som starter med A, i den første plasseringen.
Og Bob, med navn som starter med B, i den andre plasseringen.
Med en matrise, eller la oss begynne å kalle det en tabell, en hash tabell på det,
vi kan gjøre akkurat det. Hvis vi får et navn som Alice,
en streng som Alice, hvor du setter A-l-i-c-e?
Vi trenger en hueristic. Vi trenger en funksjon for å ta noen innspill som Alice
og returnere et svar, "Sett Alice på dette stedet."
Og denne funksjonen, denne svarte boksen, kommer til å bli kalt en hash-funksjon.
>> En hash-funksjon er noe som tar en inngang, som "Alice",
og returnerer til deg, vanligvis den numeriske plasseringen i noen datastruktur der Alice tilhører.
I dette tilfellet, bør vår hash-funksjon være relativt enkel.
Vår hash-funksjon skal si, hvis du får "Alice", som tegn skal jeg bry meg om?
Den første. Så jeg ser på [0], og da sier jeg hvis [0] karakter er A, returnere tallet 0.
Hvis det er B, tilbake 1. Hvis det er C, returnere 2, og så videre.
Alle 0-indeksen, og som ville tillate meg å sette Alice og deretter Bob og deretter Charlie og så videre
inn i denne datastruktur. Men det er et problem.
Hva om Anita kommer sammen igjen?
Hvor plasserer vi Anita? Hennes navn også, begynner med bokstaven A,
og det føles som om vi har gjort en enda større rot av dette problemet.
Vi har nå umiddelbar innsetting, konstant tid innsetting, i en datastruktur
heller enn verre-sak lineær,
men hva kan vi gjøre med Anita i dette tilfellet?
Hva er de to alternativene, egentlig? Ja?
[Student svar, uforståelig] Ok, så vi kunne ha en annen dimensjon.
Det er bra. Så vi kan bygge ting ut i 3D som vi snakket om verbalt på mandag.
Vi kunne legge til en annen tilgang her, men antar at nei, jeg prøver å holde dette enkelt.
Hele målet her er å ha umiddelbar konstant tid tilgang,
slik at det er å legge for mye kompleksitet.
Hva er andre alternativer når du prøver å sette inn Anita inn i denne datastrukturen? Ja?
[Student svar, uforståelig] Bra. Så kunne vi gå alle andre ned,
som Charlie nudge ned Bob og Alice, og deretter setter vi Anita hvor hun virkelig ønsker å være.
>> Selvfølgelig, nå er det en bivirkning av dette.
Dette datastruktur er sikkert nyttig, ikke fordi vi ønsker å sette folk en gang
men fordi vi ønsker å undersøke om de er der senere
hvis vi ønsker å skrive ut alle navnene i datastrukturen.
Vi kommer til å gjøre noe med disse dataene til slutt.
Så nå har vi slags skrudd over Alice, som ikke lenger hvor hun er ment å være.
Det er heller ikke Bob, er heller Charlie.
Så kanskje dette er ikke en så god idé.
Men faktisk er dette ett alternativ. Vi kunne skifte alle ned,
eller pokker, Anita kom sent til spillet, hvorfor ikke vi bare sette Anita
ikke her, ikke her, ikke her, la oss bare sette henne litt ned på listen.
Men da dette problemet begynner å devolve igjen.
Du kan være i stand til å finne Alice umiddelbart, basert på hennes fornavn.
Og Bob umiddelbart, og Charlie. Men da du ser etter Anita,
og du ser, hmm, er Alice i veien.
Vel, la meg sjekke under Alice. Bob er ikke Anita.
Charlie er ikke Anita. Åh, det er Anita.
Og hvis du fortsetter som trener for logikk hele veien,
hva er det verst tenkelige kjøretid på å finne eller sette Anita inn i denne nye datastrukturen?
Det er O (n), ikke sant?
Fordi i verste fall, det er Alice, Bob, Charlie. . .
helt ned til noen som heter "Y", så det er bare én plass igjen.
Heldigvis har vi ingen kalt "Z", så vi satt Anita på bunnen.
>> Vi har egentlig ikke løst det problemet.
Så kanskje vi trenger å innføre denne tredje dimensjonen.
Og det viser seg, hvis vi introdusere denne tredje dimensjonen,
vi kan ikke gjøre dette perfekt, men den hellige gral kommer til å være å få
konstant tid innsetting og dynamiske innsettinger slik at
Vi trenger ikke å hard-kode en rekke størrelse 26.
Vi kan sette så mange navn som vi ønsker, men la oss ta vår 5-minutters pause her
og deretter gjøre det ordentlig.
OK. Jeg satt historien opp ganske kunstig der
ved å velge Alice og deretter Bob og deretter Charlie og Anita,
hvis navn ble åpenbart kommer til å kollidere med Alice.
Men spørsmålet vi endte på mandag med er bare hvor sannsynlig er det
at du ville få slike kollisjoner? Med andre ord,
hvis vi begynner å bruke denne tabellform struktur, som er egentlig bare en matrise,
i dette tilfellet av 26 steder,
hva om våre innganger er stedet jevnt fordelt?
Det er ikke kunstig Alice og Bob og Charlie og David og så videre alfabetisk,
det er jevnt fordelt over A til Z.
>> Kanskje vi bare få heldige og vi kommer ikke til å ha to A-eller to B
med meget høy sannsynlighet, men som noen påpekt,
hvis vi generalisert dette problemet, og ikke gjøre 0-25
men, si, 0 gjennom 364 eller 65, ofte antall dager i en typisk år,
og spurte spørsmålet: «Hva er sannsynligheten for at to av oss i dette rommet har samme bursdag?"
Sagt på en annen måte, hva er sannsynligheten for at to av oss har et navn som starter med A?
Slags spørsmålet er den samme, men dette adresserom,
dette søket plass, er større i tilfelle av bursdager,
fordi vi har så mange flere dager i året enn bokstaver i alfabetet.
Hva er sannsynligheten for en kollisjon?
Vel, vi kan tenke på dette ved å finne ut regnestykket motsatt vei.
Hva er sannsynligheten for ingen kollisjoner?
Vel, sier dette uttrykket her at det er sannsynligheten
hvis det er bare en person i dette rommet, at de har en unik bursdag?
Det er 100%. Fordi hvis det er bare én person i rommet,
hans eller hennes bursdag kan være noen av de 365 dagene av året.
Så 365/365 opsjoner gir meg en verdi på 1.
Så sannsynligheten aktuelle i øyeblikket er bare ett.
Men hvis det er en annen person i rommet,
hva er sannsynligheten for at deres fødselsdag er annerledes?
Det er bare 364 mulige dager, ignorerer skuddår,
til bursdagen sin for ikke å kollidere med andre personer.
Så 364/365. Hvis en tredje person kommer inn, er det 363/365, og så videre.
Så vi holder multiplisere sammen disse fraksjonene, som blir mindre og mindre,
å finne ut hva er sannsynligheten for at alle av oss har unike bursdager?
Men da kan vi selvfølgelig bare ta det svaret og snu den rundt
og gjøre en minus alt dette, et uttrykk vi vil til slutt få
hvis du husker på baksiden av matematiske bøker, ser det litt noe sånt som dette,
som er mye lettere tolket grafisk.
Og dette grafisk her har på x-aksen antall bursdager,
eller antall personer med bursdager, og på y-aksen er sannsynligheten for en kamp.
Og hva dette sier er at hvis du har, la oss si, selv,
la oss velge noe som 22, 23.
Hvis det er 22 eller 23 personer i rommet,
sannsynligheten for at to av de svært få mennesker kommer til å ha bursdag på samme dag
er faktisk super høy, combinatorially.
50% sjanser som i en klasse for kun 22 personer, et seminar, praktisk talt,
2 av dem kommer til å ha bursdag på samme dag.
Fordi det er så mange måter du kan ha samme fødselsdag.
Enda verre, hvis du ser på høyre side av diagrammet,
etter den tid har du en klasse med 58 elever i den,
sannsynligheten for 2 personer har en bursdag er super, super høy, nesten 100%.
Nå, det er liksom en morsom fakta om det virkelige liv.
>> Men konsekvensene nå, for datastrukturer og lagring av informasjon
betyr at bare forutsatt at du har en fin, ren, jevn fordeling av data
og du har en stor nok utvalg til å passe en haug av ting
betyr ikke at du kommer til å få folk i unike omgivelser.
Du kommer til å ha kollisjoner. Så denne oppfatningen av hashing, som det kalles,
tar en inngang som "Alice" og masserer den på noen måte
og deretter komme tilbake et svar som 0 eller 1 eller 2.
Komme tilbake noen utgang fra den funksjonen er plaget av dette sannsynligheten for kollisjon.
Så hvordan kan vi håndtere disse kollisjoner?
Vel, på den ene tilfelle, kan vi ta ideen som ble foreslått.
Vi kan bare skifte alle ned, eller kanskje, litt mer enkelt,
stedet for å flytte alle andre, la oss bare flytte Anita til bunnen av den tilgjengelige plass.
Så hvis Alice er i 0, er Bob i 1, er Charlie i 2,
Vi vil bare sette Anita på stedet tre.
Og dette er en teknikk datastrukturer kalt lineær sondering.
Lineær fordi du bare vandre denne linjen, og du er liksom sondering
for ledige plasser i datastrukturen.
Selvsagt, tilfaller dette inn O (n).
Hvis datastrukturen er virkelig full, det er 25 personer i det allerede,
og deretter Anita kommer sammen, ender hun opp på hva som ville være plassering Z, og det er fint.
Hun passer fremdeles, og vi kan finne henne senere.
>> Men dette var i strid med målet om å påskynde ting opp.
Så hva om vi i stedet introduserte denne tredje dimensjonen?
At teknikken er vanligvis kalles separat kjeding, eller å ha kjettinger.
Og hva en hash table er nå, dette tabellform struktur,
tabellen er bare et utvalg av pekere.
Men hva disse pekere peker på er gjette hva?
En lenket liste. Så hva om vi tar det beste fra begge disse verdenene?
Vi bruker arrays for de første indekser
inn i datastrukturen slik at vi umiddelbart kan gå til [0] [1], [30] eller så videre,
men slik at vi har en viss fleksibilitet, og vi kan passe Anita og Alice og Adam
og en annen A navn,
vi i stedet la den andre aksen vokse vilkårlig.
Og vi endelig, som av mandag, har det uttrykksfulle evne med lenket liste.
Vi kan vokse en datastruktur vilkårlig.
Alternativt kan vi bare gjøre en stor 2-dimensjonal array,
men det kommer til å bli en forferdelig situasjon hvis en av radene i en 2-dimensjonal array
er ikke stor nok for ekstra person hvis navn skjer til å begynne med A.
Gud forby vi må omfordele en stor 2-dimensjonal struktur
bare fordi det er så mange som heter A,
spesielt når det er så få som heter Z noe.
Det er bare kommer til å bli en svært sparsommelig datastruktur.
Så det er ikke perfekt på noen måte, men nå har vi i det minste har muligheten
å kjapt finne ut hvor Alice eller Anita tilhører,
minst i form av den vertikale aksen,
og da må vi bare bestemme hvor du skal plassere Anita eller Alice i dette lenket liste.
Hvis vi ikke bryr seg om sortering ting, hvordan kunne fort vi setter Alice inn i en struktur som dette?
Det er konstant tid. Vi indeksen i [0], og hvis ingen er der,
Alice går på starten av det lenket liste.
Men det er ikke en stor avtale. Fordi hvis Anita kommer deretter langs
noen flere trinn senere, ikke hvor Anita hører?
Vel, [0]. OOP. Alice er allerede i det lenket liste.
>> Men hvis vi ikke bryr seg om sortering disse navnene,
Vi kan bare flytte Alice over, insert Anita, men selv det er konstant tid.
Selv om det er Alice og Adam og alle disse andre A navnene,
det er egentlig ikke skiftende dem fysisk. Hvorfor?
Fordi vi bare gjorde her med lenket liste, hvem vet ble disse nodene er likevel?
Alt du trenger å gjøre er å flytte brødsmuler.
Flytt pilene rundt, du trenger ikke å fysisk flytte data rundt.
Så vi kan sette Anita, i så fall, umiddelbart. Konstant tid.
Så vi har konstant tid oppslag, og konstant gangs installasjon av noen som Anita.
Men slags oversimplifying verden.
Hva om vi senere vil finne Alice?
Hvor mange skritt kommer det til å ta?
[Student svar, uforståelig]
Akkurat. Antall personer før Alice i lenket liste.
Så det er ikke helt perfekt, fordi vår datastruktur, igjen, har denne vertikale tilgang
og da må disse koplede listene hengende - faktisk, la oss ikke trekke det en en matrise.
Det har disse koblede lister hengende ut av det som ser litt noe sånt som dette.
Men problemet er hvis Alice og Adam og alle disse andre A navnene
ende opp mer og mer over det,
finne noen kunne ende opp med å ta en haug med trinn,
bcause du må traversere lenket liste,
som er en lineær operasjon.
Så egentlig, da er innsetting tid slutt O (n), der n er antallet av elementer i listen.
Delt på, la oss vilkårlig kalle det m, der m er antall koplede listene
som vi har i denne vertikale aksen.
Med andre ord, hvis vi virkelig anta en jevn fordeling av navn,
helt urealistisk. Det er åpenbart mer av noen bokstaver enn andre.
>> Men hvis vi antar for øyeblikket en jevn fordeling,
og vi har n totalt mennesker, og m. Totalt kjeder
tilgjengelig for oss, deretter lengden av hver av disse kjedene
ganske enkelt skal være den totale, n dividert med antall av kjeder.
Så n / m. Men her er hvor vi kan være alt matematisk smart.
m er en konstant, fordi det er et fast antall av disse.
Du kommer til å erklære din matrise i begynnelsen,
og vi er ikke resizing den vertikale aksen. Per definisjon, forblir det fast.
Det er bare den horisontale aksen, så å si, som er i endring.
Så teknisk sett er dette en konstant. Så nå, innsetting tid
er ganske mye O (n).
Så det ikke føles alt så mye bedre.
Men hva er sannheten her? Vel, hele tiden, i flere uker,
Vi har sagt O (n ²). O (n), 2 x n ², - n, delt på to. . . ech.
Det er bare n ². Men nå, i denne delen av semesteret,
Vi kan begynne å snakke om den virkelige verden igjen.
Og n / m er absolutt raskere enn bare n alene.
Hvis du har tusen navn, og du bryter dem opp i flere bøtter
slik at du har bare ti navn i hver av disse kjedene,
absolutt søke ti ting kommer til å være raskere enn tusen ting.
Og så en av de kommende oppgavesett kommer til å utfordre deg
å tenke på akkurat det, selv om, ja,
asymptotisk og matematisk, er dette fortsatt bare lineær,
som suger generelt når du prøver å finne ting.
I virkeligheten, det kommer til å være raskere enn det
på grunn av dette divisor.
Og så det er igjen kommer til å være denne avveiingen
og denne konflikten mellom teori og virkelighet,
og en av knottene vil begynne å dreie på dette punktet i semesteret
er mer av virkeligheten en som vi liksom forberede semster er slutt,
som vi introdusere en verden av web-programmering,
der virkelig, er ytelsen kommer til å telle fordi brukerne skal
begynner å føle og setter dårlig design beslutninger.
>> Så hvordan går du om å implementere en koblet - en hash tabell med 31 elementer?
Og i forrige eksempel var vilkårlig om fødselsdager.
Hvis noen har bursdag 1. januar eller 1. februar vil vi sette dem i denne bøtta.
Hvis det er 2 januar, 2. februar, 2. mars vil vi sette dem i denne bøtta.
Det er derfor det var 31. Hvordan erklærer du en hash table?
Det kan være ganske enkel, node * mitt bord vilkårlig navn for det, [31].
Dette gir meg 31 pekere til noder,
og som tillater meg å ha 31 pekere til lenkede lister
selv om disse kjedene er i utgangspunktet NULL.
Hva ønsker jeg å sette hvis jeg ønsker å lagre "Alice", "Bob", "Charlie"?
Vel, vi trenger å pakke disse tingene i en struktur
fordi vi trenger Alice til å peke til Bob, å peke på Charlie, og så videre.
Vi kan ikke bare ha navnene alene, så jeg kunne lage en ny struktur kalt node her.
>> Hva er en faktisk node? Hva er en node i denne nye lenket liste?
Det første, kalt ord, er for personens navn.
LENGDE, formodentlig, knyttet til den maksimale lengden av et menneskes navn,
hva som er, 20, 30, 40 tegn i sprø hjørne tilfeller,
og en er for hva? Det er bare den ekstra NULL karakter, \ 0.
Så denne noden skal brytes "noe" inne i seg selv,
men det erklærer også en peker kalt neste
slik at vi kan kjede Alice til Bob til Charlie og så videre.
Kan være NULL men ikke nødvendigvis trenger å være.
Eventuelle spørsmål om disse hash tabeller? Ja?
[Student spør spørsmål, uforståelig] En rekke - godt spørsmål.
Hvorfor er dette røye ord i en matrise i stedet for bare char *?
I dette noe vilkårlig eksempel, ønsker jeg ikke å måtte ty
til malloc for hver av de opprinnelige navnene.
Jeg ønsket å erklære en maksimal mengde minne for strengen
slik at jeg kunne kopiere inn i strukturen Alice \ 0 og ikke trenger å forholde seg til malloc og gratis og lignende.
Men jeg kunne gjøre det hvis jeg ønsket å være mer bevisst på plass bruk. Godt spørsmål.
Så la oss prøve å generalisere bort fra dette
og fokusere resten av dag på datastrukturer mer generelt
og andre problemer som vi kan løse ved hjelp av de samme grunnleggende
selv om datastrukturer selv kan avvike i sine enkeltheter.
>> Så det viser seg i informatikk, trærne er svært vanlig.
Og du kan tenke på et tre liksom som et slektstre,
hvor det er noen røtter, noen matriark eller patriark,
bestemor eller bestefar eller tidligere tilbake,
under som er mamma og pappa eller ulike søsken eller lignende.
Så en trestruktur har noder og den har barn,
vanligvis 0 eller flere barn for hver node.
Og noen av sjargong som du ser i dette bildet her
er noen av de små barna eller barnebarna på kantene
som ikke har noen piler som kommer fra dem,
de er de såkalte blader, og noen på innsiden
er en indre node, du kan kalle det noe langs disse linjene.
Men denne strukturen er ganske vanlig. Dette er litt tilfeldig.
Vi har ett barn på venstre side, har vi tre barn på høyre,
to barn på nederst til venstre.
Så kan vi ha forskjellige størrelser trær, men hvis vi begynner å standardisere ting,
og du husker kanskje dette fra Patricks video på binære søk fra en tidligere kort
nettet, binært søk, har ikke skal gjennomføres med en matrise
eller biter av papir på en tavle.
Anta at du ønsket å lagre numrene i en mer sofistikert datastruktur.
Du kan lage et tre som dette.
Du kan ha en node erklært i C, og at noden kan ha minst to elementer på innsiden av det.
Den ene er nummeret du vil lagre, og den andre er - vel, vi trenger en til.
Den andre er sine barn.
Så her er et annet datastruktur. Denne gangen er en node definert som lagrer et nummer n
og deretter to pekere, venstre barn og høyre barn.
Og de er ikke tilfeldig. Hva er interessant om dette treet?
>> Hva er mønsteret i hvordan vi har lagt dette ut eller hvordan Patrick lagt den ut i videoen hans?
Det er slags åpenbart at det er noen sortering skjer her,
men hva er den enkle regelen? Ja?
[Student svar, uforståelig]
Perfekt. Hvis du blikk på dette, ser du de små tallene på venstre side,
store tall på venstre side, men det er sant for hver node.
For hver node, dens venstre barn mindre enn den, og dens høyre barnet større enn den.
Hva dette betyr nå er om jeg vil søke denne datastruktur for, si, nummer 44,
Jeg må starte på roten, fordi som med alle disse mer komplekse datastrukturer nå,
vi har bare en peker til én ting, begynnelsen.
Og i dette tilfellet, er begynnelsen roten. Det er ikke den venstre siden,
det er roten av denne strukturen. Så jeg ser her er 55, og jeg leter etter 44.
Hvilken retning jeg ønsker å gå?
Vel, jeg ønsker å gå til venstre, fordi åpenbart er til høyre kommer til å være for stor.
Så merker her, du liksom konseptuelt chopping treet i halvparten
fordi du aldri kommer ned til høyre side.
Så nå går jeg fra 55 til 33. Det er for lite av et nummer.
Jeg leter etter 44, men nå vet jeg om 44 er i dette treet, kan jeg gå selvsagt til høyre.
Så igjen, jeg beskjæring av treet i halvparten.
Det er ganske mye identisk konseptuelt til telefonboken.
Det er identisk med hva vi gjorde med papirene på tavla,
men det er en mer sofistikert struktur som tillater oss å faktisk gjøre
dette splitt og hersk ved utformingen av algoritmen,
og faktisk, traversering en struktur som dette - whoops.
Traversing en struktur som dette, hvor det er bare "gå på denne måten, eller gå den veien,"
betyr all denne koden som bøyd hodet først når implementere den i seksjon
eller vandre gjennom det hjemme, for binære søk med rekursjon eller iterasjon,
det er en smerte i nakken. Finn midten element, så gjør din avrunding opp eller ned.
>> Det er en skjønnhet til dette fordi vi nå kan bruke rekursjon igjen,
men mye mer renslig. Faktisk, hvis du er på nummer 55, og du vil finne 44,
du går igjen i dette tilfellet, så hva gjør du? Du kjører nøyaktig samme algoritme.
Du sjekker verdien av node, så du går til venstre eller høyre.
Så du sjekke verdien av noden, gå til venstre eller høyre.
Dette er perfekt egnet til rekursjon.
Så selv om det i det siste har vi gjort noen ganske vilkårlige eksempler som involverer rekursjon
som ikke trenger å være rekursiv, med data stuctures,
spesielt trær, er det et perfekt anvendelse av denne ideen om å ta et problem,
krymper den og deretter å løse det samme type, men mindre, program.
>> Så det er en annen datastruktur som vi kan presentere.
Dette er laget ved første øyekast å se kryptisk, men dette er utrolig.
Så dette er en datastruktur som kalles en trie, trie, som er arvet fra ordet henting,
som ikke uttales re-prøve-val, men det er det verden kaller disse tingene. Prøver. T-r-i-e.
Det er en trestruktur av noe slag, men hver av nodene i en Trie
synes å være hva? Og dette er litt misvisende fordi det er slags forkortet.
Men det ser ut som hver node i denne trie er faktisk en matrise.
Og selv om forfatteren av dette diagrammet ikke har vist det,
i dette tilfellet, er dette trie en datastruktur som har som formål i livet er å lagre ord
som A-l-i-c-e-eller B-o-b.
Og på hvilken måte dette data butikker Alice og Bob og Charlie og Anita og så videre
er det bruker en rekke derved å lagre Alice i en trie,
Vi starter på rotnoden som ser ut som en matrise,
og det er blitt skrevet i stenografi notasjon.
Forfatteren utelatt abcdefg fordi det var ingen navn med det.
De bare viste M og P og T, men i dette tilfellet,
la oss gå bort fra Alice og Bob og Charlie til noen navn som er her.
Maxwell er faktisk i dette diagrammet.
Så hvordan gjorde forfatteren butikken M-a-x-w-e-l-l?
Han eller hun startet på rotnoden, og gikk til [M], så om lag 13, den 13. beliggenhet i matrisen.
Så derfra, det er en peker.
En peker fører til en annen tabell.
Derfra forfatteren indeksert i denne matrisen på stedet A, som avbildet det øverst til venstre,
og da han eller hun fulgte den peker til en annen matrise,
og gikk til pekeren på stedet X.
Deretter i neste matrise plassering W, E, L, L, og så videre,
og til slutt, la oss faktisk prøver å sette et bilde på dette.
Hva gjør en node se ut i koden?
En node i en trie inneholder en rekke pekere til flere noder.
Men det er også nødt til å være en slags boolsk verdi, i hvert fall i denne implementeringen.
Jeg måtte kalle det is_word. Hvorfor?
Fordi når du setter inn Maxwell, du er ikke sette
noe i denne datastruktur.
Du ikke å skrive M. Du skriver ikke X.
Alt du gjør er å følge pekere.
Pekeren som representerer M, deretter pekeren som representerer A,
deretter pekeren som representerer X, og W, E, L, L,
men hva du trenger å gjøre på slutten er liksom går, sjekk, nådde jeg denne plasseringen.
Det var et ord som ender her i datastrukturen.
>> Så hva en trie er virkelig fylt med og forfatteren valgte å representere
disse terminuses med små trekanter.
Dette betyr bare at det faktum denne trekanten er her, denne boolske verdien av ekte
betyr at hvis du går bakover i treet,
det betyr et ord som heter Maxwell er i denne.
Men ordet foo, for eksempel,
er ikke i treet, fordi hvis jeg starter på rotnoden opp her på toppen,
Det er ingen f pekeren, ingen o pekeren, ingen o pekeren. Foo er ikke et navn i denne ordboken.
Men derimot, Turing, t-u-r-i-n-g. Igjen, det gjorde jeg ikke lagre t eller u eller r eller jeg eller n eller g.
Men jeg gjorde butikk i denne datastruktur en verdi av sann vei ned her i denne noden - i treet
ved å sette denne boolean verdi is_word til sann.
Så en trie er snill av denne svært interessant meta struktur,
der du egentlig ikke lagring av ordene seg for denne slags ordbok.
For å være klar, du bare lagrer ja eller nei, det er et ord som slutter her.
>> Nå hva er konsekvensen?
Hvis du har 150 000 ord i en ordbok som du prøver å lagre i minnet
bruke noe sånt som en lenket liste,
du kommer til å ha 150 000 noder i din lenket liste.
Og finne en av disse ordene alfabetisk kunne ta O (n) tid.
Lineær tid. Men i tilfelle her av en trie,
hva er kjøretiden til å finne et ord?
Det viser seg skjønnheten her er at selv om du har 149 999 ord allerede i denne ordboken,
som gjennomføres med dette datastruktur,
hvor mye tid tar det å finne eller sette en person inn på det, som Alice, Alice?
Vel, det er bare 5, kanskje 6 trinnene for etterfølgende tegn.
Fordi tilstedeværelse av andre navn i strukturen
ikke kommer i veien for å sette inn Alice.
Videre finner Alice når det er 150 000 ord i denne ordboken
ikke kommer i veien for å finne Alice i det hele tatt,
fordi Alice er. . . . . her, fordi jeg fant en boolsk verdi.
Og hvis det ikke er boolean sant, så Alice er ikke i denne datastrukturen ord.
Med andre ord, kjøretiden til å finne ting og sette ting inn i denne nye
datastruktur av trie er O av - det er ikke n.
Fordi tilstedeværelse av 150.000 mennesker har ingen effekt på Alice, det virker.
Så la oss kalle det k, hvor k er den maksimale lengden av et ord på engelsk
som er typisk ikke mer enn 20-noe tegn.
Så k er en konstant. Så den hellige gral vi synes å ha funnet nå
er at av en trie, konstant tid for innstikk, for oppslag, for sletting.
Fordi antallet av tingene allerede i strukturen,
som ikke selv fysisk der. Igjen, de bare liksom krysset av, ja eller nei,
har ingen innvirkning på fremtidig driftstid.
>> Men det må jo være en fange, ellers ville vi ikke ha kastet bort så mye tid
på alle disse andre datastrukturer bare for å endelig komme til det hemmelige som er utrolig.
Så hva prisen vi betaler for å oppnå dette storhet her? Plass.
Denne saken er massiv. Og grunnen til at forfatteren
ikke presentere det her, legge merke til at alle disse tingene som ser ut som matriser,
han ikke trekke resten av treet, resten av trie,
fordi de er bare ikke relevant for historien.
Men alle disse nodene er super brede, og hver node i treet opptar
26 eller faktisk, kan være 27 tegn fordi i dette tilfellet ble jeg inkludert plass for apostrof
slik at vi kunne ha apostrophized ord.
I dette tilfellet er disse brede matriser. Så selv om de ikke er picutured,
dette tar opp en enorm mengde RAM.
Som kan være fine, especilly i moderne maskinvare,
men det er tradeoff. Vi får mindre tid ved å bruke mer plass.
Så hvor er dette alt kommer?
Vel, la oss gjøre - la oss se her.
La oss gjøre et hopp til denne fyren her.
>> Tro det eller ei, så mye gøy som C har vært i noen tid nå,
vi nådd det punktet i semesteret der det er på tide å gå over til ting mer moderne.
Ting på et høyere nivå. Og selv om de neste par ukene
vi vil likevel fortsette å fordype oss i en verden av pekere og minnehåndtering
å få den trøst som vi kan deretter bygge på,
slutten spillet er slutt å innføre, ironisk nok, ikke dette språket.
Vi vil bruke, som 10 minutter å snakke om HTML.
All HTML er er et kodespråk, og hva en kodespråk er
er disse seriene av åpne braketter og lukkede braketter som sier "gjøre denne dristige '
Gjør denne kursiv '' gjør dette sentrert.
Det er ikke alle som intellektuelt interessant, men det er super nyttig.
Og det er absolutt allestedsnærværende i disse dager.
Men hva er kraftig om den verden av HTML, og webprogrammering mer generelt,
bygger dynamiske ting, skrive kode i språk som PHP eller Python eller Ruby eller Java eller C #.
Virkelig, uansett språk av valget er, og genererer HTML dynamisk.
Generere noe som kalles CSS dynamisk.
Gjennomgripende stilark, som også er om estetikk.
Og så selv om i dag, hvis jeg går til noen nettside som kjent Google.com,
og jeg går for å vise, utvikler, vis kilde, som kanskje du har gjort før,
men kommer til å vise kilde, ser dette ting sannsynligvis ganske kryptisk.
Men dette er den underliggende koden som implementerer Google.com.
På fronten. Og faktisk alt dette er luftig estetikk ting.
Dette er CSS opp her. Hvis jeg holder rulle ned vi får noen fargekodet ting.
Dette er HTML. Googles kode ser ut som et rot, men hvis jeg faktisk åpne opp et annet vindu,
Vi kan se noen struktur til dette.
Hvis jeg åpner dette opp, legge merke til her, er det litt lettere å lese.
Vi kommer til å se før lenge denne koden, [ord] er en kode,
HTML, hode, kropp, div, script, tekstområdet, span, sentrert, div.
Og dette er liksom også kryptisk utseende ved første øyekast,
men alt dette rotet følger visse mønstre, og repeterbare mønstre,
slik at når vi får det grunnleggende ned, vil du være i stand til å skrive kode som dette
og deretter manipulere kode som dette bruker enda et annet språk, kalt JavaScript.
Og JavaScript er et språk som går inne i en nettleser
i dag at vi bruker på Harvard kurs, for selvfølgelig shopping verktøy som Google maps bruker
å gi deg en hel haug med dynamikk, gir Facebook deg å vise instant statusoppdateringer,
Twitter bruker det til å vise deg tweets umiddelbart.
Alt dette vil vi begynne å fordype oss i.
Men for å komme dit, må vi forstå litt noe om Internett.
Dette klippet her er bare ett minutt lang, og la oss anta for nå er dette faktisk
hvordan Internett fungerer som en teaser for hva som er i ferd med å komme. Jeg gir deg "Warriors of the Net".
>> [♫ Slow chorus musikk ♫]
[Mann fortelleren] Han kom med et budskap.
Med en protokoll all sin egen.
[♫ Raskere elektronisk musikk ♫]
Han kom til en verden av kule brannmurer, uncaring rutere,
og farer langt verre enn døden.
Han er rask. Han er sterk. Han er TCP / IP, og han fikk adressen din.
Warriors of the Net.
[Malan] Neste uke, da. Internett. Webprogrammering. Dette er CS50.
[CS50.TV]