SPEAKER 1: Olgu, nii et see on CS50 See on nädala lõpuks viis. Ja meenutada, et viimane kord Hakkasin uurima Kasvataja andmeid struktuurid, mis algas lahendada probleeme, mis algas tutvustada uusi probleeme, kuid võti selles oli omamoodi väliskeermestamiseks, et me hakkas tegema sõlmest sõlmeni. Nii see muidugi on ühekaupa seotud nimekirja. Ja üksi seotud, Ma mõtlen seal on vaid üks niit omavahel nende sõlmede. Selgub, mida saate teha Kasvataja asjad kahekordselt ahelloendid kusjuures sul on nool läheb mõlemas suunas, mis aitab teatud kasutegurit. Aga see lahendas probleemi? Mis probleem ei seda lahendada? Miks me hoolime esmaspäeval? Miks teoreetiliselt ei me hoolime esmaspäeval? Mida ta teeb? 

Sihtrühm: Me ei dünaamiliselt suurust muuta. 

SPEAKER 1: OK, et saaksime dünaamiliselt suurust muuta. Hästi tehtud teile mõlemale. Nii saab dünaamiliselt suurust selle andmestruktuur, kusjuures massiivi, Meenuta, mida sa pead teada priori, kui palju ruumi soovite ja kui teil on vaja natuke rohkem ruumi, et sa oled selline õnne. Sul on luua täiesti uue massiivi. Sa pead liikuma kogu oma andmeid ühest teise, lõpuks vabastama vana massiivi kui saad, ja siis edasi. Mis lihtsalt tundub väga kulukas ja väga ebaefektiivne ja isegi see võib olla. Aga see pole veel kõik hea. Pöörame hind, mis oli üks ilmsem hindadega me maksma abil ahelloend? 

Sihtrühm: peame kasutama topelt ruumi igaüks. SPEAKER 1: Jah, nii et me peame vähemalt kaks korda sama palju ruumi. Tegelikult ma mõistsin seda pilti oma isegi natuke eksitav, sest kohta CS50 IDE palju kaasaegse arvutid, osuti või aadress ei ole tegelikult neli baiti. See on väga sageli need päeva kaheksa baiti, mis tähendab põhja kõige ristkülikud on tegelikult on mingi kaks korda suur kui see, mida ma olen juhtinud, mis tähendab, te kasutate kolm korda palju ruumi kui meil oleks teisiti. Nüüd samal ajal, et me oleme veel räägi baiti, eks? Me ei pruugi rääkides megabaiti või gigabaiti, kui need andmestruktuurid saada suur. 

Ja nii täna hakkame kaaluma kuidas me võiksime uurida andmeid efektiivsemalt kui ka Tegelikult andmeid muutub suuremaks. Aga proovime õgvenda tegevuse esimene mida saate teha nende liiki andmestruktuuride. Nii midagi seotud nimekirja toetab üldiselt operatsioonide meeldi kustutada, sisestada ning otsida. Ja mida ma mõtlen, et? See tähendab lihtsalt, et tavaliselt, Kui inimesed kasutavad seotud nimekirja, nemad või keegi teine ​​on rakendanud funktsioone nagu delete, lisada, ja otsida, siis võite tegelikult midagi kasulikeks andmestruktuur. Võtame pilgu kuidas me võiksime rakendada Mõnes kood ahelloend järgmiselt. 

Nii et see on vaid mõned C-kood, isegi mitte täielik programm et ma tõesti kiiresti vahustatud. See ei ole internetis levitamise koodi, sest see ei reaalselt sõita. Aga teate ma olen lihtsalt koos Kommentaari ütles, dot dot dot, et siin on midagi seal dot dot dot, midagi seal. Ja olgem lihtsalt vaadata mida mahlane osad. Nii on line kolm, Tuletame meelde, et see on nüüd Me pakkusime kuulutab sõlme viimase aega, üks neist ristkülikukujulise objektid. See on int, et me kutsume N, kuid me võime seda kutsuda midagi, ja siis struct node star nimetas tuleva. Ja just olema selge, et teine line, line kuus, mis see on? Mis on see meie heaks teeb? Sest see kindlasti tundub rohkem segasena kui meie tavaline muutujaid. 

Sihtrühm: See muudab liikuda üle. 

SPEAKER 1: See muudab liikuda üle. Ja täpsemalt, see salvestab aadress sõlme, mis on mõeldud semantiliselt kõrval, eks? Nii see ei lähe pruugi liikuda midagi. See lihtsalt läheb talletada väärtust, mis on saab olema aadress Mõnede muude sõlme, ja sellepärast oleme öelnud struct sõlme täht, mis tähistab osuti või aadress. OK, nii et nüüd, kui sa arvata, et meil on Selles N meile kättesaadav, ja olgem eeldada, et keegi teine ​​on lisada terve hunnik täisarvud arvesse ahelloend. Ja mis on seotud nimekiri on osutas mõnede punkti muutuja nimega loend, mis on möödunud aastal siin parameeter, kuidas ma minna line 14 rakendamisel otsida? Teisisõnu, kui ma rakendamisel funktsiooni, mille eesmärk elus on võtta int ja seejärel algus ahelloend, mis on kursor seotud nimekirja. Nagu esimene, kes ma arvan, et David oli meie vabatahtlike esmaspäeval, ta vastakuti Kogu seotud nimekirja, see on nagu oleks me möödaminnes David on meie argument siin. Kuidas minna liiklevad see nimekiri? Noh, tuleb välja, et kuigi viiteid on suhteliselt uus nüüd meile, Me saame seda teha suhteliselt arusaadav. 

Ma lähen edasi minna ja kuulutada ajutise muutuja Tavapäraselt on lihtsalt läheb mida nimetatakse pointer, ja PTR, aga sa võiksid seda nimetada kõike, mida sa tahad. Ja ma initsialiseerida selle algust nimekirja. Nii saab mingi mõtle sellele kui mul õpetaja teisel päeval, Selline osutades keegi seas meie inimeste vabatahtlikena. Nii et ma olen ajutise muutuja, mis on lihtsalt osutades sama asi et meie juhuslikult nimega Vabatahtliku David oli ka meenutanud. Nüüd, kui kursor on ei ole null, sest meenutavad et null on mingi eriline kontroll väärtus piiritleb nimekirja lõppu, Niisiis, kui ma ei osutades maa nagu meie viimane vabatahtlike oli, lähme edasi ja teha järgmist. Kui pointer-- ja nüüd ma mingi tahan teha seda, mida me tegime koos õpilase structure-- kui osuti dot järgmine equals-- pigem kui osuti dot N võrdub võrdub muutuja N, siis argument, mis on olnud möödunud aastal, siis ma tahan minna ja öelda naasta tõsi. Ma leidsin numbri N sees sõlm minu ahelloendid. Aga dot enam töötab selles kontekstis sest pointer, PTR, on tõepoolest pointer, aadressi, me tegelikult ei imeliselt kasuta lõpuks tükk süntaks et ajab intuitiivset tunnet ja tegelikult kasuta noolt siin, mis tähendab minna et aadressi täisarv seal. Nii et see on väga sarnane vaimu dot operaator, kuid kuna osuti ei viida mitte tegelik struct ise, me lihtsalt kasutada nooleklahve. 

Nii et kui praegune sõlme, et mina, Ajutise muutuja, olen osutades ei ole N, mida ma tahan teha? Noh, minu inimvabatahtlikele et meil oli siin ükspäev, kui mu esimene inimene ei ole see, mida ma tahad, ja võib-olla teisel inimesel ei ole Ühest ma tahan, ja kolmas, ma on vaja hoida füüsiliselt liigub. Nagu kuidas ma sammult läbi nimekirja? Kui meil oli massiivi, siis just tegin nagu ma pluss pluss. Aga sel juhul piisab teha pointer, saab, pointer, kõrval. Teisisõnu järgmisele väljale on nagu kõik kas käsi et meie vabatahtlikel inimestel esmaspäeval kasutasid punkti teisigi sõlme. Need olid nende kõrval naabrid. 

Nii et kui ma tahan astuda läbi selle nimekirja, Ma ei saa lihtsalt ma pluss pluss enam, Ma asemel öelda I, pointer, läheb võrdse iganes järgmise valdkonnas on, Järgmise väli, järgmisel valdkonnas on, järgmiste kõik need jäänud käed et meil oli laval juhtides mõningal järgnevate väärtustega. Ja kui ma saan läbi et kogu korduse ja lõpuks, ma tabanud null, millel ei ole leitud N veel, ma lihtsalt tagasi vale. Nii jälle, kõik, mis me teeme siin, ühe pildi hetk tagasi, hakkab juhtides juures loendi alguses arvatavasti. Ja siis ma kontrollin, on väärtus Otsin võrdne üheksa? Kui jah, siis ma tagasi tõsi ja ma olen teinud. Kui ei, ma uuendada oma käsi, AKA pointer, juhtida järgmisel noole asukoht ja siis järgmisel noole asukoht, ja järgmine. Ma lihtsalt jalgsi läbi selle massiivi. 

Nii jälle, kes hoolib? Nagu mida see koostisosana? Noh, meelde tuletada, et oleme kasutusele mõiste virna, mis on abstraktne andmetüüp, kuivõrd see on ei ole C asi, see ei ole CS50 asi, see on abstraktne idee, idee virnastamine asju üksteise peale mida saab rakendada kobarad erinevalt. Ja üks viis, kuidas me kavandatud oli massiivi või koos seotud nimekirja. Ja selgub, et kanooniliselt, et stack toetab vähemalt kaks operatsiooni. Ja buzz sõnad on push, kuni lükake midagi peale virna, nagu uus salv söögisaal, või pop, mis tähendab, et eemaldada tähtsaim salve korstna söögituba hall, ja siis võib-olla mõned muud toimingud samuti. Niisiis, kuidas võiks me defineerime struktuur et me nüüd helistades virna? 

Noh, meil on kõik vajalikud süntaks meie käsutuses olevaid C. ütlen, mulle tüübi määratlus struct sees korstna Ma ütlen on massiiv, mille terve hunnik numbreid ja seejärel suurust. Nii teisisõnu, kui ma tahan rakendada seda koodi, lase mul minna ja lihtsalt selline joonistada, mida see ütleb. Nii et see ütleb mulle struktuur, mis sai hulgaliselt, ja ma ei tea, millises ulatuses on see on ilmselt mingi konstant, et ma olen mis on mujal, ja see on hea. Aga arvan, et see on lihtsalt üks, kaks, kolm, neli, viis. Nii võimsus on 5. See element sees minu struktuuri nimetatakse numbrid. Ja siis ma pean ühe muud muutuva ilmselt nimetatakse suurust, mis esialgu ma lähen sätestada käivitub nulli. Kui seal on midagi virna, suurus on null, ja see on prügi väärtused numbrid. Ma ei tea, mis on seal veel. 

Nii et kui ma tahan, et lükata midagi peale virna, arvan, et ma kutsun funktsiooni push, ja Ma ütlen suruda 50, nagu number 50, kus soovitaksite Ma joonistan selle selle massiivi? Seal on viis erinevat vastusevarianti. Kuhu ma suruda number 50? Kui eesmärk siin jälle helistada funktsiooni push, liigu argument 50, kus ma pane see? Viis possible-- 20% võimalus aim õigesti. Jah? 

Sihtrühm: paremas servas. 

SPEAKER 1: paremas servas. Nüüdseks on 25% võimalus aim õigesti. Nii et tegelikult on kõik korras. Kokkuleppeliselt ma ütlen array, me tavaliselt algavad vasakul, aga me võiksime kindlasti alustama õigelt. Nii spoiler oleks siin ma olen ilmselt läheb joonistada vasakul, justnagu tavaline massiiv, kus Ma alguses läheb vasakult paremale. Aga kui sa ei flip aritmeetiline, fine. See lihtsalt ei ole tavalised. OK, mul on vaja teha üks rohkem muutus küll. Nüüd, kui ma olen surunud midagi kuhja, mis järgmiseks? 

Olgu, ma pean juurdekasvu suurust. Nii et lubage mul minna ja lihtsalt uuendada seda, mis oli null. Ja selle asemel, ma lähen panna väärtus on üks. Ja nüüd arvan, et ma suruda teise number peale virna, nagu 51. Noh, ma pean tegema veel ühe muutust, mis on suuruses kuni kaks. Ja siis arvan, et ma push üks number kuhja nagu 61, Nüüd on mul vaja uuendada suurus ühe aega ja saada väärtus 3 nagu suurus. Ja nüüd arvan, et ma kutsun pop. Nüüd pop Tavapäraselt ei võta argument. Mis virna, kogu punkti salve metafoor on see, et sa ei pea äranägemisel minna saan, et salve, mida sa teha oskad on pop tähtsaim üks virna, lihtsalt sellepärast. Just see andmestruktuur teeb. 

Nii selle loogika, kui ma öelda pop, mis tuleb välja? Nii 61. Mis siis tegelikult on arvutiga kavatseb teha mälu? Mida minu kood on teha? Mida soovitaksite meil muuta ekraanil? Mida peaks muutma? Vabandust? Nii me vabaneda 61. Nii võin kindlasti teha. Ja ma ei saa vabaneda 61. Ja mis siis muu muutus peab toimuma? Suurus on ilmselt minna tagasi kaks. Ja nii see on hea. Aga oota natuke, suurus Hetk tagasi oli kolm. Lihtsalt teha kiire meelerahu kontrolli. Kuidas me teame, et me tahtis vabaneda 61? Kuna me popping. Ja nii on mul selle teise vara suurusest. 

Oota, ma olen Mõeldes tagasi nädalal kaks kui me hakkasime rääkima massiivid, kus see oli asukohast null, see oli asukoha ühe, see oli asukoha kaks, see on asukoha kolme, nelja see näeb välja nagu suhet suurus ja element, mida ma tahan, et eemaldada massiivi tundub just see, mida? Suurus miinus üks. Ja nii see on, kuidas nii inimestele me teame 61 jõuab. Kuidas arvuti läheb tea? Kui koodi, kus sa ilmselt tahan teha suurust miinus üks, nii kolme miinus üks on kaks, ja et tähendab, et me tahame vabaneda 61. Ja siis me saame tõepoolest uuendada suurus nii, et suurus praegu läheb kolm kuni vaid kaks. Ja lihtsalt olla pedantne, ma lähen ettepaneku, et ma olen teinud, eks? Sa kavandatud intuitiivselt õigesti ma peaks vabaneda 61. Aga ei ole ma mingi omamoodi saanud lahti 61? Olen tegelikult unustatud et see on tegelikult olemas. Ja arvan, et tagasi PSET4, kui olete lugenud artikkel umbes kriminalistika PDF et meil oli teiega lugeda, või siis loeb sel nädalal PSET4. Tuletame meelde, et see on tegelikult Sobiv Kogu idee arvuti kohtuekspertiisi. Mis arvuti üldiselt teeb, on see lihtsalt unustab, kus midagi on, kuid see ei lähe ja nagu proovige seda kratsida välja või alistada need bitti ühtede ja nullide või mõni muu juhuslikult struktuuris kui sa ise seda tahtlikult. Nii oma intuitsiooni oli õige, olgem vabaneda 61. Aga tegelikult me ​​ei pea vaeva. Me lihtsalt vaja unustada, et see on seal, muutes oma suurust. 

Nüüd on probleem selles virnas. Kui ma hoida surudes asju kuhja, mis on ilmselt juhtub vaid mõni hetk aega? Me läheme ruum otsa. Ja mida me teeme? Me liiki kruvitud. See rakendamist ei lase Meie suurust massiivi, sest kasutades Selle süntaks, kui te arvan, et tagasi nädalal kaks, kui olete deklareerinud suurus massiivi, me ei ole näinud mehhanismi veel, kus saate muuta suurust massiivi. Ja tõepoolest C ei ole selle funktsiooni. Kui te ütlete mulle viis Nths, kutsume neid numbreid, see on kõik sa lähed saada. Nii me nüüd teeme nii esmaspäeval, on suutlikkus väljendada lahendust aga me lihtsalt vaja näpistama määratlus meie stack mitte olema mingi kõva kodeeritud massiiv, aga lihtsalt salvestada aadressi. 

Nüüd, miks see nii on? Nüüd me lihtsalt peame olema rahul asjaolu, et kui mu programm töötab, Ma arvatavasti läheb küsida inimese, kui palju numbreid sa tahad hoida? Nii sisend peab tulema kusagilt. Aga kui ma tean, et number, siis saan lihtsalt kasuta missugust ülesannet anda mul patakas mälu? Oskan kasutada malloc. Ja ma ei saa öelda ühtegi arvu baiti Ma tahan tagasi neid Nths. Ja kõik, mis mul salvestada numbrid muutuva siin sees see struct peaks olema siis? Mis tegelikult läheb numbrid selle stsenaariumi? Jah, viit esimest bait, et patakas mälu või täpsemalt, aadressi esimese neist baiti. Ei ole oluline, kas see on üks baidi või miljard baiti, Ma lihtsalt pean hooli esimene. Sest see, mis malloc garantiide ja minu operatsioonisüsteemi garantiid, on see, et patakas mälu ma saada see saab olema piirnevad. Seal ei kavatse olla puudujääke. Nii et kui ma olen küsinud 50 baiti või 1000 baiti, nad kõik saab olema tagasi seljad. Ja nii kaua, kui ma mäletan, kuidas suur, kuidas palju ma küsisin, kõik mul on vaja teada on esimene selline aadress. 

Nüüd on meil võimalus koodi. Kuigi, see läheb meid rohkem aega kirjutada seda üles, me võiks nüüd ümber, et mälu lihtsalt ladustamiseks erinev aadress olemas kui me tahame suurem või isegi väiksem patakas mälu. Nii et siin on kompromiss. Nüüd saame dünaamikat. Meil on veel contiguousness ma väidan. Kuna malloc annab meile külgnevas patakas mälu. Aga see saab olema valu kaela juures, programmeerija, tegelikult koodi üles. See on lihtsalt rohkem tööd. Me peame kood sarnane sellele, mida olin peksma välja hetk tagasi. Väga sooritatav, kuid see lisab keerukust. Ja nii arendaja aega, programmeerija aega on veel üks ressurss mis võiks olla vaja kulutada aega, et saada uusi funktsioone. Ja siis muidugi on järjekord. Me ei hakka seda üks palju detaile. Aga see on väga sarnase sisuga. Ma võiks rakendada järjekorda, ja sellele vastava tegevuse, Lisa järjekorda või dequeue, nagu lisada või eemaldada, see on lihtsalt Kasvataja viis öelda seda, Lisa järjekorda või dequeue järgmiselt. Ma ei anna endale struct et jälle on mitmeid tema massiiv, seda uuesti tema suurus, aga miks ma nüüd vaja jälgida ees järjekorras? Ma ei pea teadma ees minu pakk. Noh, kui ma veel kord queue-- olgem lihtsalt raske koodeksi, millel, nagu viis täisarvud siin potentsiaalselt. Nii et see on null, üks, kaks, kolm, neli. See saab olema numbrite uuesti. Ja see saab nimeks suurusest. 

Miks ei ole piisav on lihtsalt suurus? Noh, olgem suruda samu numbreid. Nii et ma pushed-- ma enqueued või lükatakse. Nüüd ma Lisa järjekorda 50 ja seejärel 51 ja siis 61 ja dot dot dot. Nii et Lisa järjekorda. Ma enqueued 50, siis 51, siis 61. Ja mis näeb välja identne korstnat seni, va ma vaja teha üks muutus. Mul on vaja uuendada selle suurus, nii et ma lähen nullist üheni to 02:58 nüüd. Kuidas dequeue? Mis juhtub dequeue? Kes peaks tulema välja selle nimekirja esimene kui see rida on Apple Store? Nii 50. Nii et see on selline keerukam seekord. Kui eelmisel korral oli super lihtne lihtsalt teha suurust miinus üks, Ma saan lõpuks minu rida tõhusalt kus numbrid on, see eemaldab 61. Aga ma ei taha kaotada 61. Ma tahan olla 50, kes oli seal 5:00 rivistama jaoks uus iPhone või tühi-tähi. Ja nii vabaneda 50, ma ei saa lihtsalt teha seda, eks? Ma ei kriipsutama 50. Aga me lihtsalt ütles, et me ei pea olema nii anal kui tühjalt läbi või peita andmed. Me lihtsalt unustada, kus ta on. 

Aga kui ma muudan suurust nüüd kaks, on see piisav teave teada, mis toimub minu järjekord? Mitte päris. Nagu mu suurus on kaks, kuid kus ei järjekorda hakkavad, eriti kui ma veel samad numbrid mällu. 50, 51, 61. Nii et ma pean meeles Nüüd, kus ees on. Ja nii nagu ma pakutud üles seal, me oleme just helistas Nth ees, kelle algne väärtus oleks pidanud olema, mida? Zero, alles algus nimekirja. Aga nüüd lisaks decrementing suurus, me lihtsalt juurdekasvu ees. Nüüd siin on veel üks probleem. Nii et kui ma edasi. Oletame, et see on number nagu 121, 124, ja siis, kurat võtaks, Ma olen enam ruumi. Aga oota üks hetk, ma ei ole. Nii siinkohal lugu, oletame, et suurus on üks, kaks, kolm, neli, nii oletame, et suurus on neli, ees on üks, nii 51 eesmises. Ma tahan panna teisele numbrile siin kuid, kurat võtaks, ma olen enam ruumi. Aga ma ei ole tõesti, eks? Kust ma panen lisaväärtust, nagu 171? Jah, ma võiks lihtsalt selline minna tagasi sinna, eks? Ja siis välja järgmised 50 või lihtsalt kirjutada seda 171. Ja kui sa ei tea, miks Meie numbrid sain nii juhuslik, need on tavaliselt tehtud arvuti reaalerialadel Harvardi pärast CS50. Aga see oli hea optimeerimine, sest nüüd ma ei raiska ruumi. Mul on veel meeles kui suur see asi on kokku. See viis kokku. Sest ma ei taha alustada kirjutaks 51. Nüüd ma olen ikka ruumi, nii sama probleem nagu enne. Aga näed, kuidas nüüd oma koodi, siis ilmselt pean kirjutama natuke rohkem keerukuse teha, mis juhtub. Ja tegelikult, mida operaator C ilmselt laseb sa võluväel teha ringlev? Jah mooduli järgi operaator, protsenti märk. Mis siis selline lahe umbes järjekorda, kuigi me hoida joonistus massiivid kui need nagu sirged jooned, kui te Selline mõtle seda koole umbes nagu ring, siis lihtsalt intuitiivselt seda liiki töötab vaimselt Ma arvan, et veidi rohkem vigadeta. Sa ikkagi ellu et vaimse mudeli koodi. Nii ei ole nii raske, lõpuks rakendada, aga me ikka kaotada size-- pigem võime suurust, kui me seda teeme. 

Meil on vabaneda massiivi me asendada see ühe pointer, ja siis kuskil minu kood on mul helista mida toimida tegelikult luua massiivi nimetatakse numbrid? Malloc või samalaadse funktsiooni, täpselt. Iga küsimustele korstnad või järjekorrad. Jah? Hea küsimus. Mis moodul oleks te kasutate siin. Nii üldisemalt kasutamisel mod, siis teeksin seda koos suurust Kogu andmestruktuur. Nii midagi viiest või võimsust, kui see on pidev, on ilmselt seotud. Aga teeme moodul viis ilmselt ei ole piisav, sest me peame teadma, kas me ümbritsev siit või siit või siit. Nii et sa oled ilmselt ka kavatse soovite kaasata suurusest asi või ees muutuja samuti. Nii et see on lihtsalt see suhteliselt Lihtne aritmeetika väljendus, aga mooduli oleks võtmetähtsusega. 

Nii lühifilm kui soovite. Animatsioon, et mõned inimesed teises ülikoolis kokku panna, et me oleme kohandatud arutelu. See hõlmab Jack õppimise fakte järjekorrad ja statistika. 

FILM: Kunagi ammu, seal oli mees nimega Jack. Kui ta tuli sõpru, Jack ei olnud harjumus. Nii Jack läks rääkima Populaarseim poiss teadis ta. Ta läks Lou ja küsis, mida ma pean tegema? Lou nägi, et tema sõber oli tõesti õnnetud. Noh, ta hakkas lihtsalt vaata kui sa riides. Kas sul pole riideid erineva ilme? Jah, ütles Jack. Ma kindlasti teha. Tule minu maja ja Ma näitan neid teile. Nii nad läksid välja Jacki. Ja Jack näitas Lou kasti kus ta jättis kõik oma särgid, ja tema püksid, ja tema sokid. Lou ütles, ma näen sa pead kõik oma riided kuhja. Miks sa ei kulumine mõned teised kord aega? 

Jack ütles, noh, kui ma eemaldada riideid ja sokke, Ma pesta neid ja panna neid ära kasti. Siis tuleb järgmine hommikul, ja kuni ma hop. Ma lähen kasti ja saada minu riided kaovad. Lou kiiresti aru probleem Jack. Ta hoidis riideid, CD, ja raamatud virnas. Kui ta jõudis jaoks midagi lugeda või kandma, ta tahaks valida top raamatu või aluspesu. Siis, kui ta oli teinud, ta paneks ta kohe tagasi. Tagasi ta ei tahaks minna, peal virnas. Ma tean, et lahendus, ütles võidukas Loud. Sa pead õppima hakake järjekorda. Lou võttis Jacki riideid ja riputasid need kapis. Ja kui ta oli tühjendada kasti, siis ta lihtsalt viskad ta. 

Siis ta ütles, nüüd Jack, lõpus Päeva panna oma riideid vasakul kui paned neid ära. Siis homme hommikul, kui sa vaata päikest, su riided Paremal alates rea lõppu. Kas sa ei näe? ütles Lou. See on nii kena. Sa kannan kõike korraga Enne kanda midagi korda. Ja kõike järjekorrad tema kapis ja riiul, Jack hakkas tunda üsna enesekindel. Kõik tänu Lou ja Tema imeline järjekorda. SPEAKER 1: Olgu, see on jumalik. Mis on tõesti kohta all kapuuts nüüd? Et meil on viiteid, et meil on malloc, et meil on võime luua tükkideks mälu ise dünaamiliselt. Nii et see on pilt me ühtesid just mõni päev. Me tegelikult ei ela seda, kuid see pilt on kestnud alla kapuuts nädalat nüüd. Ja nii see on, lihtsalt ristkülik, et oleme tõmmatud, arvuti mällu. Ja võib-olla arvuti või CS50 ID, on GB mälu või RAM või kaks gigabaiti või neli. See ei ole tegelikult küsimus. Teie operatsioonisüsteem Windows või Mac OS või Linux, sisuliselt võimaldab oma programmi arvan, et tal on juurdepääs ta kõigile arvuti mälus, kuigi võite olla töötab mitut programmi korraga. Nii et tegelikult see ei toimi. Aga see on selline illusioon anda kõik oma programmid. Nii et kui sul oli kaks kontserti RAM, seda kuidas arvuti võiks mõelda. 

Nüüd juhuslikult, üks neist asju, üks neist segmentides mälu, nimetatakse virna. Ja tõepoolest igal ajal Seni kirjalikult koodi et olete kutsutud funktsiooni, näiteks peamine. Tuletame meelde, et igal ajal ma olen joonistatud arvuti mälus, Olen alati teha omamoodi pool ristküliku siin ja ei viitsinud räägi mida on eespool. Sest kui peamine nimetatakse, Väidan mis sa selle Kiip mälu et loojub siin. Ja kui peamine nimetatakse funktsiooni nagu swap, ka swap läheb siia. Ja selgub, et on kus see jõuavad. On midagi, mida nimetatakse virna sees arvuti mällu. Nüüd lõpus päeval, see on lihtsalt aadressid. See on nagu bait null, bait ühe baidi 2 miljardit. Aga kui sa arvad kui see nelinurkne objekt, kõik me teeme iga kord, kui me nimetame funktsiooni kihilisus uus tükk mälu. Anname selle funktsiooni viilu omal mälu töötada. 

Ja meenutada nüüd, et see on oluline. Sest kui me ei ole midagi swap ja kaks kohalikud muutujad nagu A ja B ning muudame need väärtused ühest ja kaks kaks ja üks, tagasikutsumine et kui swap naaseb, see on nagu oleks see tükk mälu on lihtsalt läinud. Tegelikult, see on ikka seal forensically. Ja midagi on ikka tegelikult olemas. Aga põhimõtteliselt, see on nii Kuigi see on täiesti kadunud. Ja nii peamine ei tea ühtegi tööd mis tehti, et swap funktsiooni, kui see on tegelikult läbinud nendes argumendid, pointer, viitena. Nüüd põhiline lahendus Selle probleemi swap möödub asju aadressi. Aga selgub ka, mis on kestnud üle, et osa ristküliku kõik see aeg on veel seal on rohkem mälu seal. Ja kui sa dünaamiliselt mälu eraldada, kas see on sees getString, mis oleme teinud teie jaoks on CS50 raamatukogu, või kui te poisid helistada malloc ja küsi operatsioonisüsteemi patakas mälu, ta ei ole pärit virna. Ta on pärit teise koha arvuti mällu seda nimetatakse hunnik. Ja see pole veel kõik erinevad. See on sama RAM. See on sama mälu. See on lihtsalt RAM, mis on üles seal asemel siin. 

Ja mis see tähendab? Noh, kui arvuti on piiratud kogus mälu ja stack kasvab üles, nii et rääkida, ja hunnik järgi Selle nool, kasvab alla. Teisisõnu, iga kord, kui helistada malloc, sa pööratakse viilu mälu ülevalt, siis võibolla natuke väiksem, siis natuke madalam, iga kord, kui helistada malloc, hunnik, see kasutust, on selline kasvab, kasvav lähemale ja lähemale, mis? Virna. Nii see tunduda hea mõte? Ma mõtlen, kus see ei ole päris selge, mida veel saab teha, kui sa ainult on piiratud mälu. Aga see on kindlasti halb. Need kaks noolt olete kiirkursuse üksteise. 

Ja selgub, et paha poiss, inimesed, kes Eriti hea programmeerimise, ja üritab häkkida arvuteid, võib kasutada seda reaalsust. Tegelikult Vaatleme väike väljavõte. Nii et see on näide saate lugeda umbes põhjalikumalt Wikipedia. Me juhtida sind article kui uudishimulik. Aga seal on rünnak üldiselt tuntud buffer overflow, et on eksisteerinud niikaua inimestel pidanud manipuleerimise võimet arvuti mällu, eriti C. Nii et see on väga meelevaldne programmi kuid olgem lugeda alt üles. Main arvesse Argc char star argv. Nii et see on programm, mis võtab käsurea argumente. Ja kõik peamised see ilmselt on kõne funktsioon, nimetame seda F lihtsuse. Ja see möödub mida? Argv ühe. Nii satub F iganes sõna on see, et kasutaja sisestatud käsureale pärast Programmi nimi üldse. Nii palju nagu Caesar või Vigenere, mis sa võiks meenutada, teed argv. 

Mis on F? F võtab string kui selle ainus argument, AKA char star, samal asi, kui string. Ja seda nimetatakse suvaliselt baar see näide. Ja siis char c 12 lihtsalt üldarusaadavat mõttes, Mis on char c sulg 12 teeme meie jaoks? Mida see teeb? Eraldamine mälu, eriti 12 baiti 12 tähemärki. Täpselt. Ja siis viimane rida, segatakse ja koopia, olete ilmselt ei näinud. See on string koopia funktsiooni, mille eesmärk elus on kopeerida oma teise argumendi arvesse oma esimese väitega, kuid ainult kuni Teatud baitide arvu. Nii kolmas argument ütleb, kui palju baite peaksid sa kuuled? Pikkus baar, olenemata kasutaja sisestatud. Ja sisu Baar, et string on kopeeritakse mällu osutas juures C. 

Nii et see tundub tobe, ja see on. See on kunstlik näiteks aga see on esindaja klassi rünnaku vektorid, viis rünnata programmi. Kõik on korras ja hea, kui kasutaja liigid sõna, mis on 11 tähemärki või vähem, pluss kurakriips null. Mis siis, kui kasutaja tipib üle 11 või 12 või 20 või 50 tähemärki? Mis see programm tegema hakkad? Potentsiaalselt seg süü. See läheb pimesi kopeerida kõike bar kuni selle pikkuse, mis on sõna otseses mõttes kõike baar, aadressiribale osutas C. Aga C on ainult ennetavalt manustada 12 baiti. Aga seal on mingit täiendavat kontrolli. Ei ole, kui tingimused. Pole veakontrollialgoritmide siin. 

Ja mis siis see programm on lähen tegema, on lihtsalt pimesi kopeerida üks asi teise. Ja kui me tõmbame selle kui pilt, siin lihtsalt Kiip mälu. Nii märkate allosas, me on kohaliku muutuja baar. Nii et osuti, mis läheb store-- pigem, et kohalikud argument, mis on läheb salvestada string baar. Ja siis märkate lihtsalt Ülaltoodud seda virna, sest iga kord, kui küsida mälu virna, see läheb natuke Ülaltoodud see piltlikult, teate, et meil 12 baiti seal. Ülemine vasakpoolne on C sulg null ja alumine parempoolne on C sulg 11. See on lihtsalt, kuidas arvutid läheb panna see välja. Nii lihtsalt intuitiivselt, kui baaris on rohkem kui 12 tähemärki kokku, sh längkriipsu null, kus on 12 või C sulg 12 kavatse minna? Või õigemini, kus on 12 iseloomu või 13. iseloomu, sajandat iseloomu, mis lõpuks pildil? Kõrgem või madalam? 

Õigus, sest kuigi korstnat ise kasvab ülespoole, kui olete panna asjad see, et konstruktsiooni tõttu, paneb mälu ülevalt alla. Nii et kui sul on rohkem kui 12 baiti, sa lähed alustada kirjutada baar. Nüüd ongi viga, aga see on tegelikult ei ole suur asi. Aga see on suur asi, sest seal on rohkem asju toimub mälu. Nii et siin on, kuidas me võiksime pane hello, peab olema selge. Kui ma kirjutada hello käsureale. H-E-L-L-O kurakriips null, jõuab jooksul need 12 baiti, ja me oleme super ohutu. Kõik on hästi. Aga kui ma kirjuta midagi enam, potentsiaalselt on läheb libiseda baar ruumi. Aga hullem veel, selgub välja kõik see aeg, kuigi me pole kunagi rääkinud see, korstna kasutatakse muud kraami. See ei ole lihtsalt kohalikud muutujad. 

C on väga madal keeles. Ja see omamoodi salaja kasutab stack ka meeles pidada, kui funktsiooni nimetatakse, mida aadress on eelmise funktsiooni, et ta saaks hüpata tagasi selle funktsiooni. Nii et kui peamine kõnesid vahetada hulgas asjad surutakse korstnat ei ole lihtsalt vahetab kohalikud muutujad, või tema argumente, ka salaja surunud peale virna, mida esindab punane viil siin on aadress peamised füüsiliselt arvuti mälus, nii, et kui swap tehakse, arvuti teab, et ma pean minema tagasi pealehele ja lõpetuseks täidesaatva põhiülesanne. Nii et see on ohtlik nüüd, sest kui kasutaja liigid ka rohkem kui hello, nii, et kasutaja sisend clobbers või kirjutab, et punane osa, loogiliselt, kui arvuti lihtsalt läheb pimesi oletada et baiti, et punane viil on aadress, kuhu ta peaks tagasi, Mis siis, kui vastane on piisavalt targad või õnn panna baitide järjestust seal, et näeb välja nagu aadress, aga see on aadress koodi et ta tahab arvuti täita asemel peamine? 

Teisisõnu, kui see, mida kasutaja kirjutades käsureale, ei ole lihtsalt midagi kahjutu nagu hello, aga see on tegelikult kood, mis on samaväärne kustutada kõik selle kasutaja faile? Või e-posti oma parooli mind? Või alustada logides oma klahvivajutusi, eks? On võimalus, olgem sätestada täna et nad võiksid kirjutada mitte ainult hello maailma või oma nime, nad võiksid sisuliselt pass koodi, nulle ning ones, et arvuti vigu nii koodi ja aadressi. Nii ehkki mõnevõrra abstraktselt, kui kasutaja liigid piisavalt võistleva koodi et me üldistada siin A. A on rünnaku või vaenlased. Nii lihtsalt halvad asjad. Me ei hooli numbrid või nulli või need täna, nii et sa lõpuks kirjutaks, et punane osa, märgata, et baitide järjestust. O 835 C null kaheksa null. Ja nüüd, kui Wikipedia artikkel siin on teinud ettepaneku, kui te nüüd tõesti hakata märgistades baiti arvuti mälu, mida Wikipedia artikkel Ettepaneku, et mis siis, kui aadress Selle ülaosas vasakul bait on 80 C 0 3508. 

Teisisõnu, kui halb on piisavalt targad koos tema kood tegelikult panna number siin, et vastab aadress koodi ta süstida arvuti, siis võib petta arvuti arvesse tee midagi. Failide eemaldamine, postitada asju, nuusutamisel oma liiklust, sõna otseses mõttes midagi võiks olla süstitakse arvutisse. Ja nii buffer overflow rünnaku keskmes on lihtsalt loll, loll ülekaalukate massiivi et ei oma piire kontrollida. Ja see on see, mis on super ohtlik ja samal ajal super võimas C on see, et meil on tõepoolest juurdepääs kõikjal mälu. See on kuni meile programmeerijaid, kes kirjutavad originaal kood kontrollida paganama pikkus tahes massiivid, et me manipuleerides. Nii et oleks selge, milline on fix? Kui me tagasi pöörata sellele kood, ma ei tohiks lihtsalt pikkuse muutmine bar, mida ma veel peaksin kontrollida? Mida ma peaksin tegema, et vältida selle rünnaku täielikult? Ma ei taha lihtsalt pimesi öelda et sa peaksid kopeerida nii palju baite kui on pikkus baar. Ma tahan öelda, kopeerib palju baite kui on baar kuni eraldatud mälu, või 12 maksimaalselt. Nii et ma pean mingi kui seisund et ei vaadata pikkus baar, aga kui see ületab 12, me lihtsalt raske koodi 12 puhul maksimaalne võimalik kaugus. Vastasel niinimetatud puhvris ülevoolu rünnak võib juhtuda. Allosas slaidid, kui sa oled uudishimulik loe edasi on tegelik algartikkel Kui soovite võtta pilk. 

Aga nüüd hulgas hinnad makstakse siin oli ebaefektiivsust. Nii et oli kiire madal pilk probleemid võivad tekkida nüüd, et me on juurdepääs arvuti mällu. Aga teine ​​probleem meil juba komistanud esmaspäeval oli lihtsalt ebaefektiivsuse on seotud nimekirja. Oleme tagasi lineaarne aeg. Me ei pea enam külgnevas massiivi. Meil ei ole muutmälu. Me ei saa kasutada nurksulg märke. Me sõna otseses mõttes pea kasutama samas loop nagu ma kirjutasin hetk tagasi. Aga esmaspäeval, me väita, et suudame libiseda tagasi rüppe efektiivsuse saavutada midagi, mis on logaritmiline äkki, või parimal veel võibolla isegi midagi, mis on nn konstantse ajaga. Niisiis, kuidas me saame teha, et kasutades neid uusi tööriistad, nende aadressid, neid viiteid, ja väliskeermestamiseks asju meie enda? Noh, oletame, et Siin need on kamp Numbrite et me tahame hoida oma andmete struktuuri ja tõhusalt otsida. Saame absoluutselt tagasi kerida nädal kaks, viska need massiivi, ja otsida neid kasutades binaarne otsing. Jaga ja valitse. Ja tegelikult sa kirjutasid Kahendotsimine PSET3, kus sa ellu leid programmi. Aga tead mis. Seal on selline rohkem nutikas viis seda teha. See on veidi rohkem kogenud ja see võib-olla võimaldab meil mõista, miks binaarne otsing on nii palju kiiremini. Esiteks, ärgem tutvustada mõiste puu. Milline kuigi Tegelikkuses puud liiki kasvada niimoodi, maailma arvuti teaduse nad omamoodi kasvada allapoole nagu sugupuu, kus teil on Sinu vanavanemad või vanavanemad või tühi-tähi tipus, patriarh ja matriarh pere, vaid üks nn root, sõlm, alla mis on tema lapsed, allpool, mis on oma laste või tema järeltulijad üldisemalt. Ja keegi rippumas põhja perekonna puu, peale selle Noorim perekonnas, võib ka lihtsalt olla üldiselt nimetatakse puu lehed. 

Nii et see on lihtsalt kamp sõnad ja mõisted midagi nimega puu arvuti teadust, palju nagu sugupuu. Aga seal on Kasvataja kehastused puud, millest üks nimetatakse kahendotsingupuu. Ja saate mingi kraakleja peale mida see asi teeb. Noh, see on binaarne mis mõttes? Kui ei binaarne tulevad siit? Vabandust? See ei ole niivõrd kas või. See on rohkem, et iga sõlm pole rohkem kui kaks last, nagu me näeme siin. Üldiselt tree-- ja Teie vanemad ja vanavanemad võib olla nii palju lapsi või lapselast, kui nad tegelikult tahavad, ja nii näiteks on meil kolm lapsed maha, et parem käsi sõlme, kuid Binääripuu sõlm on null, üks või kaks last maksimaalselt. Ja see on tore omadus, sest kui see ülempiir kahte, me ei kavatse olla võimeline natuke Logi baasi kaks tegevus toimub siin lõpuks. Nii et meil on midagi logaritmiline. Aga rohkem sellest kohe. Otsi puu tähendab, et numbrid paigutatud selliselt, et vasakul lapse väärtus on suurem kui juurestik. Ja selle õige laps suurem kui juurestik. Teisisõnu, kui te võtate mõnda sõlmed, ringid see pilt, ja vaatab vasakule lapse ja tema õigust lapse, esimese peaks olema väiksem kui, teine ​​peab olema suurem. Nii meelerahu vaadata 55. See on jäänud lapse 33. See on vähem kui. 55, oma õigust laps on 77. See on suurem kui. Ja see on rekursiivne definitsioon. Võiksime vaadata iga üks neist sõlmed ja sama mustrit hoiaks. 

Mis on tore on kahendotsingupuu, on et üks, saame seda rakendada koos struct, vaid niimoodi. Ja kuigi me viskamine palju struktuure teie, Nad on pisut intuitiivne nüüd loodetavasti. Süntaks on veel kauge kindel, kuid sisu sõlme selles context-- ja hoiame kasutades sõna sõlme, kas see on ristkülik ekraanil või ring see on lihtsalt mõned üldised konteiner, sel juhul puu, nagu üks nägime, peame täisarv Iga sõlmede ja siis ma pean kaks osuti osutab vasakule laps ja õigus lapsega, võrra. Nii et see, kuidas me võiksime rakendada, et oma struktuure. Ja kuidas võiks ma rakendab seda koodi? Noh, võtame kiire vaadata selle väikese näite. See ei ole funktsionaalne, kuid ma olen kopeerida ja kleepida, et struktuur. Ja kui minu funktsioon binaarne search tree nimetatakse otsingumootori, ja see võtab kaks argumenti, täisarv N ja osuti et sõlm, nii et kursor puu või kursor puu juurt, kuidas ma minna otsima N? Noh, esiteks sellepärast, et ma olen tegelevad suunanäitajaks, Ma lähen tegema meelerahu kontrolli. Kui puu võrdsete võrdne null, on N Selles puu või mitte see puu? See ei saa olla, eks? Kui ma olen varem null, seal on midagi seal. Ma võin ka lihtsalt pimesi öelda tagasi vale. Kui sa annad mulle midagi, ma kindlasti ei saa leia arv N. Mida veel võiks ma vaadake nüüd? Ma ütlen ka mujal kui N on väiksem kui iganes on puu sõlme et olen kätte N väärtust. Teisisõnu, kui number Kõht otsivad, N, on väiksem kui sõlm et ma vaatan. Ja sõlme Otsin kell nimetatakse puu, ja meenutada eelmise näiteks saada on väärtus osuti, Ma kasutan noolt märke. Nii et kui N on väiksem kui puu nool N, ma tahan kontseptuaalselt minna vasakule. Kuidas ma väljendan otsinguks jäänud? Et asi oleks selge, kui see on Pilti küsimus, ja ma olen läbinud selle tipmine nool, mis on suunaga allapoole. See on minu puu pointer. Ma osutades puu juur. Ja ma otsin ütleme, arvu 44, suvaliselt. Kas 44 või väiksem suurem kui 55 ilmselt? Nii et see on väiksem kui. Ja nii see, kui tingimus kehtib. Nii kontseptuaalselt, mida ma tahan otsi kõrval, kui ma otsin 44? Jah? 

Täpselt, ma tahan otsi vasakul laps, või vasakule sub-tree of this picture. Ja tegelikult, las ma läbi pilt siin hetkeks, kuna Ma ei kriimusta seda. Kui ma hakkan siin on 55, ja Ma tean, et väärtus 44 Otsin on vasakul, see on selline ja nagu pisaravool telefoniraamat poole või pisaravool puu pooleks. Ma ei pea enam hooli kogu see pool puud. Ja veel, uudishimulikult poolest struktuuri, et see asi siin, et algab 33, et ise on kahendotsingupuu. Ma ütlesin sõna kirjutan enne, sest tõepoolest see on andmestruktuur, et definitsiooni järgi on rekursiivne. Sul võib olla puu, mis on selle suur, kuid igaüks oma lastele kujutab endast puu vaid veidi väiksem. Selle asemel, et oleks vanaisa või vanaema, nüüd on see lihtsalt ema või-- ma ei saa say-- ole ema või isa, et oleks imelik. Selle asemel kaks last olemas Oleks nagu vend ja õde-vend. Uue põlvkonna sugupuu. Aga struktuurilt, see on sama mõte. Ja selgub, mul on funktsioon mida ma otsida binaarne otsing puu. Seda nimetatakse otsing. Ma otsin N puude nool vasakule else if N on suurem kui väärtus et ma olen praegu. 55 lugu hetk tagasi. Mul on funktsioon nimega otsing, et ma ei saa lihtsalt edasi N sellele ja rekursiivselt otsida sub-tree ja lihtsalt tagasi mida iganes see vastus. Else Mul on mõned lõplik alus asjas. 

Mis on viimane juhtum? Tree on kas null. Väärtus ma kas otsin on vähem kui see suurema või sellega või sellega võrdne. Ja ma võiks öelda, mis võrdub võrdsed, kuid loogiliselt on võrdub lihtsalt öeldes teine ​​siin. Nii tõsi on see, kuidas ma leian midagi. Loodetavasti on see süveneb veelgi, näiteks kui loll sigma funktsiooni tegime mõned loengud tagasi, kus see oli lihtsalt nii lihtne kasutada loop loendada üles kõik numbrid ühest N. Siin koos andmestruktuur mis iseenesest on rekursiivselt määratletud ja rekursiivselt tõmmatud, nüüd on suutlikkus väljendada ennast koodi, mis iseenesest on rekursiivne. Nii et see on täpselt sama koodi siin. 

Mis siis muud probleemid saame lahendada? Nii kiire sammu kaugusel puud hetkeks. Siin on, ütleme, Saksa lipp. Ja seal on selgelt muster see lipp. Ja seal on palju lipud maailmas, mis on nii lihtne kui see nii oma värvid ja mustrid. Aga oletame, et see on salvestatud kui GIF või JPEG või bitmap või ping, graafiline failiformaat millega te olete juba tuttav, millest mõned oleme mängides in PSET4. See ei tundu mõttekas salvestada must piksel, must piksel, must piksel dot, dot, dot, terve hunnik musti piksleid esimest scanline, või rida, siis terve hunnik sama, siis terve hunnik sama, ja seejärel terve hunnik punane pikslit, punane pikslit, punane pikslit, siis kogu kamp kollane pikslit, kollane, eks? 

Seal on selline ebaefektiivsus siin. Kuidas teile intuitiivselt suruma Saksa lipu kui rakendada seda faili? Nagu millist teavet me ei saa viitsinud salvestamine kettale, et vähendada meie faili suurus, nagu megabaidi et kilobait, midagi väiksem? Kus asub koondamise siin on selge? Mis võiks teha? Jah? Täpselt. Miks mitte pigem mäletan värvi iga darn piksli nagu sa teed PSET4 koos bitmap faili formaadis miks sa lihtsalt ei esinda vasakpoolsel veerul pikslit, näiteks hunnik musti piksleid, kamp punane, ja hunnik kollane, ja siis lihtsalt kuidagi kodeerida Idee korrata seda 100 korda või korrake seda 1000 korda? Kus 100 või 1000 on lihtsalt täisarv, siis pääse ainult üks number asemel sadu või tuhandeid Täiendavate pikslit. Ja tõepoolest, see, kuidas me võiks tihendada Saksa lipu. Ja Mida aga Prantsuse lipu? Ja natuke mingisugune vaimne harjutus, mis lipu saab kokkusurutud rohkem kettal? Saksa lipu või Prantsuse lipp, kui me võtame seda lähenemist? Saksa lipu, sest seal on rohkem horisontaalne koondamine. Ja disain, paljud graafilise faili formaate tõepoolest töötavad rastrijoont horisontaalselt. Nad võiksid teha vertikaalselt, vaid inimkonna otsustas aastat tagasi, et me tulen Üldiselt arvan, et asjad reas realt, mitte kolonni kolonni. Nii tõesti kui sa olid et vaadata faili suurus Saksa lipp ja Prantsuse lipp, nii kaua, kui resolutsioon on Samal, sama laiusega ja kõrgus, see üks siin saab olema suurem, sest sa kordama ennast kolm korda. Pead määrama sinine, korrake ise, valge, kordan ennast, punane, kordama ennast. Sa ei saa lihtsalt minna kõik kuidas paremale. Ja kui kõrvale, teha selge compression on kõikjal, isegi kui need on Nelja kaadreid video-- sa võiks meenutada, et filmi või video üldiselt nagu 29 või 30 kaadrit sekundis. See on nagu väike flip raamat, kus te lihtsalt näha, pilt, pilt, pilt, pilt lihtsalt super kiire, et see näeb välja nagu näitlejad ekraanil liiguvad. Siin on kimalaste kohta peal kimp lilli. Ja kuigi see võib olla mingi raske näha esmapilgul Ainuke asi liigub Selles filmis on bee. 

Mis on loll säilitan video pakkida? See on selline raiskamine salvestada video neli peaaegu identsed pildid, erinevad ainult niivõrd, kuivõrd kus bee on. Võite visata kõige Selle info ja mäletan ainult, näiteks, esimese kaadri ja viimane kaader, võti raamid, kui olete kunagi kuulnud sõna, ja lihtsalt salvestada ka keskel, kui mesilane on. Ja sa ei pea salvestada kõik roosa, ja sinine, ja roheline väärtuste samuti. Nii et see on ainult öelda, et compression on kõikjal. See on meetod, mida me sageli kasutada või enesestmõistetavaks nendel päevadel. 

Aga kuidas sa suruma teksti? Kuidas minna umbes kokkusurumise teksti? Noh, iga tähemärki Ascii on üks bait, või kaheksa bitti. Ja see on selline loll, eks? Kuna sa ilmselt tüüpi ja E ja I ja O ja U palju sagedamini kui näiteks W või Q või Z, Sõltuvalt keelest, milles sa oled kirjalikult kindlasti. Ja miks me kasutame kaheksa bitti iga kirja, sealhulgas vähemalt Populaarseim tähed, eks? Miks mitte kasutada vähem bitti jaoks super populaarne tähed, nagu E, mida sa vist esimene Wheel of Fortune, ja kasutada rohkem bitte eest vähem populaarne tähed? Miks? Sest me lihtsalt läheb neid kasutada harvem. 

Noh, tuleb välja, et seal on püütud teha seda teha. Ja kui te mäletate hinne kooli või gümnaasiumi Morse koodi. Morse kood on dots ja kriipsud, mis võib olla edastatakse mööda traadist Kõlab või signaalid mingi. Aga Morse kood on super puhas. See on selline binaarne süsteem et teil on punktid või kriipsud. Aga kui sa näed, näiteks kaks punkti. Või kui te arvate tagasi operaatori kes läheb nagu PIIKSUD, piiks, piiksu, lööb natuke vallandada mis edastab signaali, kui sa, saaja, saab kaks täpid, mis sõnumi olete saanud? Täiesti meelevaldne. 

Ma? Ma? Või mis about-- või olen? Võib-olla oli see lihtsalt kaks E õigust? Nii et see probleem of decodability Morse kood, mille kohaselt juhul, kui isik saadan sulle sõnumi tegelikult peatab nii saate sortida kohta näha ega kuulda lõhed tähed, see ei ole piisav lihtsalt Kirjuta oja ühtede ja nullide, või punktid ja kriipsud, sest seal on ebaselgus. E on ühe dot, nii et kui sa vaata kaks punkti või kuulda kaks punkti, võibolla on kaks E-või äkki see on üks I. Seega on meil vaja süsteemi, mis on natuke targem kui see. Nii mees nimega Huffman aastat tagasi tulid just seda. Nii et me lihtsalt läheb võtta kiire pilgu kuidas puud Sobiv seda. Oletatakse, et see on mingi loll sõnum, mida soovite saata, koosneb ainult A, B, C on D's ja E-ndatel, kuid seal on palju koondamise siin. See ei ole mõeldud olema inglise keeles. See ei ole krüpteeritud. See on lihtsalt loll sõnum palju kordusi. Nii et kui sa tegelikult loota läbi kõik A, B, C-ndatel, D's ja E-ndatel, siin on sagedust. 20% tähed A, 45% tähed on E-ndatel ja kolm muud sagedused. Meil arvestatakse seal käsitsi ja just tegin matemaatikat. 

Nii selgub, et Huffman, mõni aeg tagasi, mõistsin, et sa tead mis, kui ma hakkan hoone puu või metsa puid, kui soovite, järgmine, mida ma teha saan järgmine. Ma annan sõlme igale Tähtede et ma hoolin ja ma lähen hoida sees, et sõlm sagedusi ujukoma väärtus, või sa võiksid kasutada seda N Ka aga me lihtsalt kasutada float siin. Ja algoritmi, mis tegi ta ettepaneku, et teil seda metsa ühe sõlme puud, nii super lühike puud, ja sa alustada ühendavad neid uued rühmad, uued vanemad, kui soovite. Ja sa seda valides kaks väikseimat sagedustel korraga. Nii ma võtsin 10% ja 10%. Teen uue sõlme. Ja ma nimetan uus sõlm 20%. 

Millised kaks sõlmede ma ühendada edasi? See on veidi ebamäärane. Nii et mõnes nurgas juhtudel kaaluda, kuid hoida asjad päris, Ma lähen valima 20% - Ma nüüd ignoreerida lapsi. Ma lähen valima 20% ja 15% ja juhtida kaks uut servi. Ja nüüd, kus kaks sõlmede ma loogiliselt ühendada? Ignoreeri kõiki lapsi, kõiki lapselapsed, lihtsalt pilk juured nüüd. Millised kaks sõlmede ma lips koos? Point kaks ja 0.35. Ma joonistan kaks uut servi. Ja siis ma sain ainult üks vasakule. Nii et siin on puu. Ja see on välja töötatud teadlikult otsida selline ilus, kuid teade, et servad on Samuti on märgistatud null ja üks. Nii on kõik lahkunud servad on null suvaliselt, kuid järjekindlalt. Kõik õige servad on ones. 

Ja mis siis Hoffman kavandatud tähendab, kui sa tahad esindada B, mitte esindama arvu 66 kui ASCII mis on kaheksa kogu bitti, sa tead, mida, vaid poest muster null, null, null, null, sest see on tee minu puu, hr Huffman puu, lehestiku juurest. Kui soovite salvestada E seevastu ei Kirjuta kaheksa bitti, mis kujutavad endast E. Selle asemel, Kirjuta, mida muster bitti? Üks. Ja mis tore on see et E on kõige populaarsem kirja, ja te kasutate lühim koodi. Järgmine populaarsemaid kiri välja näeb ta oli A. Ja nii mitu bitti ta ettepaneku kasutada on? Zero, üks. 

Ja kuna see on rakendatud kui see puu, nüüd andke mulle ette näha pole kahemõttelisust nagu Morse koodi, sest kõik Tähtede sa hoolid lõpus on nende servad. Nii see on lihtsalt üks kohaldamise puu. See on-- ja ma lehvitada minu käsi selles, kuidas võiks rakendada seda kui C struktuur. Meil on vaja ainult ühendada sümbol, nagu paalia, ja sagedus vasakule ja paremale. Aga vaatame kaks lõplik näiteid, et teil saada üsna tuttav pärast viktoriin null probleemi seatud viis. 

Nii on andmestruktuur tuntud kui hash tabelit. Ja hash tabelis on omamoodi jahtuda, et sellel on kopad. Ja oletame seal neli ämbrid siin, vaid nelja tühikuid. Siin on kaardipakk, ja siin on klubi, labidas, klubi, teemandid, klubi, teemandid, klubi, teemandid, clubs-- nii et see on juhuslik. Hearts, hearts--, et ma olen bucketizing kõik sisendid siin. Ja hash tabelis vajadustele vaadata oma panus, ja siis pane see teatud paigutada selle põhjal, mida sa näed. See algoritm. Ja ma olin kasutades super lihtsaid visuaalseid algoritm. Kõige raskem osa, mis oli mäleta, mida pildid olid. Ja siis on neli kokku asju. 

Nüüd korstnad kasvasid, mis Messil disain asi siin. Aga mida veel võiks teha? Nii tegelikult on meil siin hunnik vana kooli eksam raamatuid. Oletame, et kamp õpilaste nimed on siin. Siin on suurem hash tabelit. Selle asemel, et neli ämbrid, Olen oletame 26. Ja me ei taha minna laenata 26 asju väljastpoolt [? Annenberg?], Et Siin on viis, mis esindavad A-Z. Ja kui ma vaata õpilane, kelle nimi algab A, Ma panen tema mängust on. Kui keegi hakkab koos C, seal, A-- tegelikult ei tahtnud seda teha. B läheb siia. Nii et ma sain A ja B ja C ning Nüüd siin on veel üks õpilane. Aga kui see hash tabelis on rakendatakse array, Ma olen selline kruvitud Sel hetkel, eks? Ma nagu vaja panna see kuhugi. 

Nii et üks viis, kuidas ma lahendada see kõik õige, A on hõivatud, B on hõivatud, C on hõivatud. Ma panen ta D. Nii et Esimene, mul juhuslikult vahetu juurdepääs et iga kopad õpilastele. Aga nüüd on selline detsentraliseeritud millekski lineaarne, sest kui ma tahan otsida keegi kelle nimi algab A, ma kontrollin siin. Aga kui see ei ole A õpilase Otsin, Ma nagu on alustada kontrollides ämbrid, sest see, mida ma tegin oli omamoodi lineaarselt sond andmestruktuuri. Rumal viis öelda lihtsalt vaadata Esimest saadaval avamine, ja panna kui plaan B, kui nii võib öelda, või plaani D sel juhul, väärtus selles kohas asemel. See on lihtsalt nii, et kui olete sain 26 kohas ja no õpilased nimega Q või Z, või midagi sellist et vähemalt te kasutate ruumi. 

Aga me oleme juba näinud rohkem targad lahendused siin, eks? Mida sa teeksid, selle asemel Kui teil on kokkupõrge? Kui kaks inimest on nimi A, mida oleks on targemaks või rohkem intuitiivne lahendus kui lihtsalt Haara kus D peaks olema? Miks ma just ei lähe väljaspool [? Annenberg?] nagu malloc, teise sõlme, pane see siin, ja seejärel panna, et õpilane siin. Nii et ma sisuliselt on mingi hulga, või äkki rohkem elegantselt nagu me oleme hakanud näha ahelloend. 

Ja nii räsi tabelis on struktuur et võiks vaadata nagu see, kuid nutikalt, sa midagi, mida nimetatakse Eraldi ühendamine, millega hash tabelis lihtsalt on massiiv, iga mille elemendid ei ole number, ise on seotud nimekirja. Nii et sa saad super kiire juurdepääsu otsustama, kus räsi oma väärtust. Sarnaselt kaarte, näiteks Tegin super kiireid otsuseid. Hearts läheb siia, teemandid läheb siia. Sama siin A läheb siin D läheb siia, B läheb siia. Nii super kiire pilk-ups, ja kui juhtub, et joosta juhul kus sul kokkupõrkeid, kaks inimesed, kellel on sama nimi, samuti siis sa lihtsalt alustada nende ühendamise. Ja äkki sa hoida neid järjestatud tähestiku, võibolla mitte. Aga vähemalt nüüd on dünaamikat. Nii et ühelt poolt on meil super kiire konstantset aega, ja selline lineaarne aeg seotud, kui need on seotud nimekirjad hakkama saada veidi pikk. 

Nii selline rumal, geeky nali aastat tagasi. Kell CS50 hack-a-Thon, kui õpilased kontrollida, mõned TF või CA igal aastal arvab, et see on naljakas, et panna märk, nagu see, kus ta lihtsalt tähendab, et kui su nimi algab A, minna seda teed. Kui teie nimi algab B-, minna see-- OK, see on naljakas võibolla hiljem poolaastal. Aga seal on veel viis seda teha ka. Tule tagasi, et. 

Nii et see struktuur. Ja see on meie viimane struktuuri täna mis on midagi, mida nimetatakse Prefiksipuu. T-R-I-E, mis mingil põhjusel on lühike otsinguks, kuid seda nimetatakse Prefiksipuu. Nii Prefiksipuu on veel üks huvitav sulam palju neid ideid. See on puu, mis me oleme näinud. See ei ole kahendotsingupuu. See on puu tahes laste arvu, kuid iga lastega Prefiksipuu on massiiv. Array suurus, ütleme, 26 või äkki 27 Kui soovite toetada sidekriipsuga nimed või ülakoma inimeste nimed. 

Ja nii see on andmestruktuur. Ja kui te vaatate ülevalt alla, nagu siis, kui sa vaadata top sõlme seal, M, on osutades vasakpoolsem asi seal, mis seejärel A, X, W, E, L, L. See on vaid andmestruktuur, mis meelevaldselt on talletamiseks inimeste nimed. Ja Maxwell on salvestatud ainult järgmisi teele massiivi massiivi massiivi. Aga mis on hämmastav umbes Prefiksipuu on et samas ahelloend ja isegi massiivi, parim oleme kunagi saanud on lineaarne aeg või logaritmiline aega otsin keegi üles. Selles andmestruktuur Prefiksipuu, kui minu andmete struktuur on ühe nime ta ja ma otsin Maxwell, ma olen leiame teda päris kiiresti. Ma lihtsalt otsida M-A-X-W-E-L-L. Kui Selle andmestruktuur seevastu kui N on miljon, kui seal on miljonit nime selles andmestruktuur, Maxwell on ikka veel olla leitavaks pärast vaid M-A-X-W-E-L-L samme. Ja David-- D-A-V-I-D samme. Teisisõnu, ehitades andmebaasi struktuur, mis on sai kõik need massiivid, mis kõik ise toetada muutmälu, Ma ei hakata otsima üles inimesed nimi kasutades aja jooksul, mis on proportsionaalne mitte number asju andmestruktuur, nagu miljon olemasolevate nimesid. Aega kulub mul leida M-A-X-W-E-L-L selles andmestruktuuri on proportsionaalne mitte suurus andmestruktuuri, kuid pikkusele nime. Ja realistlikult nimed otsime üles on kunagi saab olema hull pikk. Äkki keegi on 10 märk Nime, 20 karakteri nimi. See on kindlasti piiratud, eks? Hetkel inimese Maal, kes on pikim võimalik nime, kuid see nimetus on pidev väärtuse pikkus, eks? See ei erine üheski mõttes. Nii et sel viisil oleme saavutatud andmestruktuuri mis on pidevas aega look-up. See ei võta mitmeid samme sõltuvalt sisendandmete pikkus, kuid mitte arv nimi andmestruktuuris. Nii et kui me kaks korda rohkem nimed Järgmisel aastal miljard kuni kaks miljardit leid Maxwell kavatseb võtta täpselt sama arvu seitse sammu teda leida. Ja nii näib, et oleme saavutanud meie Püha Graal sõiduaega. 

Nii Paar kiiret teadaandeid. Quiz null on tulemas. Veel, et muidugi veebilehte üle järgmise paari päeva jooksul. Esmaspäeval lecture-- see on puhkus siin Harvardi esmaspäeval. See ei ole New Haven, nii et me oleme võttes klassi New Haven loeng esmaspäeval. Kõik saab filmida ja striimitakse live nagu tavaliselt, kuid olgem end täna koos 30 teise klipi nn "Deep Mõtted" poolt Daven Farnham, mis eeskujuks oli eelmisel aastal laupäeval Öö Live "Deep Mõtted" Jack Handy, mis Nüüd peaks mõtet. 

FILM: Ja nüüd, "Deep Mõtted "poolt Daven Farnham. Hash tabelis. 

SPEAKER 1: Olgu, see on see nüüd. Näeme järgmisel nädalal. 

DOUG: Et näha, kuidas see toimib. Võtame pilk, et just nüüd. Nii et siin on meil sorteerimata massiivi. 

IAN: Doug, võite minna ja restart see vaid üks teine, palun. Olgu, kaamerad on jooksvalt, nii tegevus, kui sa oled valmis, Doug, OK? DOUG: Okei, nii et see, mida me on siin on sorteerimata massiivi. Ja ma olen värviline kõik elemendid punane, see tähendab, et see on tegelikult sorteerimata. Nii meenutada, et esimene asi, mida me teeme on sortida vasakule poole massiivi. Siis sortida õigus pool massiivi. Ja ya-blaa-blaa-da, me ühinevad nendega koos. Ja meil on täiesti sorteeritud massiivi. Nii see on, kuidas ühendada omamoodi toimib. 

IAN: Oot, oot, oot, lõigatud, lõigatud, lõigatud, lõigatud. Doug, sa ei saa lihtsalt ya-blaa-da, ya-da, teed kaudu ühendada omamoodi. 

DOUG: Ma just tegin. Kõik on korras. Me oled hea minna. Lihtsalt hoida jooksvalt. Igatahes, 

IAN: Sa pead selgitama see paremini, kui on. See on lihtsalt ei piisa. DOUG: Ian, me ei pead minema tagasi ühe. Kõik on korras. Igatahes, kui me jätkame merge-- Ian, me oleme keset filmimist. 

IAN: Ma tean. Ja me ei saa lihtsalt ya-blaa-da, ya-da, läbi kogu protsessi. Sul on selgitada, kuidas Mõlemad pooled saavad kokku liita. 

DOUG: Aga me oleme juba selgitas, kuidas kaks sides-- 

IAN: Sa oled näidanud neid ühendamise massiivi. DOUG: Nad teavad protsessi. Nad on kõik korras. Me oleme läinud üle kümne korra. 

IAN: Sa lihtsalt vahele paremale üle. Me läheme tagasi üks, siis ei saa sa ya-blaa-da üle. Olgu, tagasi ühe. 

DOUG: Ma pean minema tagasi läbi kõik slaidid? Mu Jumal. See on nagu kuuendat korda, Ian. Kõik on korras. 

IAN: Okei. Oled valmis? Hea. Action.