SPEAKER 1: Oke, dus dit is CS50 Dit is het einde van de week vijf. En herinneren dat laatste keer dat we begon te kijken naar de liefhebber gegevens structuren die begon op te lossen problemen, die begon te voeren nieuwe problemen, maar de sleutel tot deze was het soort threading dat we begonnen zijn van knooppunt naar knooppunt. Dus dit is natuurlijk een enkelvoudig gelinkte lijst. En afzonderlijk verbonden, Ik bedoel, er is slechts één draad tussen elk van deze knooppunten. Blijkt dat u kunt liefhebber doen dingen zoals dubbel gelinkte lijsten waarbij je een pijl gaan in beide richtingen, waarbij kunnen helpen met bepaalde efficiëntie. Maar dit het probleem opgelost? Welk probleem deed dit op te lossen? Waarom hebben we de zorg op maandag? Waarom, in theorie, hebben we de zorg op maandag? Wat doet het? 

PUBLIEK: We kunnen dynamisch resize. 

SPEAKER 1: OK, dus we kunnen dynamisch resize. Goed gedaan jullie beiden. Dus je kunt dynamisch dit formaat datastructuur, terwijl een array, recall, moet u een weten priori hoeveel ruimte je wilt en als je een beetje meer nodig ruimte, je bent soort van geluk. Je moet een hele nieuwe serie te maken. Je moet al beweeg je gegevens van de ene naar de andere, uiteindelijk bevrijden van de oude serie als je kunt, en ga dan verder. Die voelt gewoon erg duur en zeer inefficiënt, en inderdaad kan worden. Maar dit is niet alles goed. We betalen een prijs, wat was één van de meer voor de hand liggende prijzen wij betalen met behulp van een gekoppelde lijst? 

PUBLIEK: We moeten gebruiken dubbele ruimte voor een ieder. SPEAKER 1: Ja, dus we moeten ten minste tweemaal zoveel ruimte. In feite, realiseerde ik me van deze foto zelfs een beetje misleidend, want op CS50 IDE in een veel moderne computers, een pointer of een adres is in feite vier bytes. Het is heel vaak zijn deze dagen acht bytes die : het onderste meest rechthoeken er in werkelijkheid zijn een soort van twee keer zo groot als wat ik heb getekend, wat betekent dat je gebruikt drie keer zo zoveel ruimte als we anders zouden kunnen hebben. Nu op hetzelfde moment, we zijn nog steeds in gesprek bytes, toch? We zijn niet per se praten megabytes of gigabytes, tenzij deze gegevens structuren te groot. 

En dus vandaag beginnen we te overwegen hoe wij gegevens kunnen verkennen efficiënter als in feite de gegevens wordt groter. Maar laten we proberen om canonicalize de activiteiten eerste dat je kunt doen op deze soorten gegevens structuren. Dus iets als een gekoppelde lijst algemeen ondersteunt operaties willen verwijderen, invoegen en zoeken. En wat moet ik daarmee? Dat betekent gewoon dat meestal, als mensen met behulp van gelinkte lijst, zij of iemand anders heeft geïmplementeerd functies zoals verwijderen, invoegen, en zoeken, zodat u kunt iets wat eigenlijk doen nuttig bij de gegevensstructuur. Dus laten we eens een snelle blik hoe we kunnen implementeren een code voor een gekoppelde lijst als volgt. 

Dus dit is slechts enkele C-code, zelfs niet een compleet programma dat ik echt snel opgezweept. Het is niet online in de distributie code, omdat het niet kan draaien. Maar let ik heb net met een reactie zei, dot dot dot, er is iets daar, dot dot dot, daar iets. En laten we gewoon kijken naar wat de sappige delen zijn. Dus op lijn drie, herinneren dat dit is nu we voorgesteld waarbij een knooppunt laatste tijd zo'n rechthoekige objecten. Het heeft een int dat wij N zullen noemen, maar we konden het iets noemen, en riep toen een struct knooppunt ster naast. En alleen maar om duidelijk te zijn, dat de tweede regel op regel zes, wat is dat? Wat doet het voor ons? Want het ziet er zeker meer cryptisch dan onze gebruikelijke variabelen. 

Publiek: Het maakt het bewegen over één. 

SPEAKER 1: Het maakt het bewegen over één. En om precies te zijn, zal het adres op te slaan van het knooppunt dat bedoeld is semantisch ernaast, toch? Dus het is niet van plan om noodzakelijkerwijs bewegen iets. Het gaat gewoon om opslaan van een waarde, die naar het adres van een andere node en dat is waarom we hebben gezegd struct knooppunt ster, de ster duidt een pointer of een adres. OK, dus nu als je ervan uitgaat dat we Deze N beschikbaar voor ons, en laten veronderstellen dat iemand anders ingevoegd een heleboel getallen in een gekoppelde lijst. En dat gekoppelde lijst is gewezen op een bepaald punt een variabele genaamd lijst die is doorgegeven hier als een parameter, Hoe ga ik over lijn 14 zoekresultaten implementeren? Met andere woorden, als ik ben de uitvoering functie waarvan het doel in het leven is naar een int en vervolgens het nemen begin van een gekoppelde lijst, dat is een wijzer naar de gekoppelde lijst. Net als de eerste, die ik denk dat David was onze vrijwilligers op maandag, hij wees naar de hele gelinkte lijst, het is alsof we passeren David in onze argumentatie hier. Hoe kunnen we gaan over het doorkruisen van dit overzicht? Nou, het blijkt dat, hoewel pointers zijn nu relatief nieuw voor ons, we kunnen deze relatief doen onomwonden. 

Ik ga om te gaan en verklaren een tijdelijke variabele die volgens afspraak wordt gewoon wijzer te worden genoemd, of PTR, maar je kon alles wat je wilt bellen. En ik ga initialiseren aan het begin van de lijst. Dus je kunt soort denken van deze als ik de leraar de andere dag, soort wijzend op iemand onder onze mensen als vrijwilliger. Dus ik ben een tijdelijke variabele die is gewoon te wijzen op hetzelfde dat onze toevallig genoemd vrijwilliger David werd ook gewezen. Nu, terwijl aanwijzer niet ongeldig, omdat recall dat null is een aantal speciale sentinel waarde het markeert het einde van de lijst, dus terwijl ik niet te wijzen op de grond als onze laatste vrijwilliger was, laten we gaan vooruit en doe het volgende. Als pointer-- en nu ik soort van wil om te doen wat we deden met de student structure-- als wijzer stip equals-- eerder, als wijzer dot N gelijk gelijk is aan de variabele N, de argument dat is doorgegeven in, dan wil ik gaan en zeggen return true. Ik heb het nummer N binnenkant van gevonden één van de knooppunten van mijn gekoppelde lijst. Maar de dot niet meer werkt in deze context omdat wijzer, PTR, is inderdaad een pointer, een adres, we eigenlijk kunnen heerlijk Gebruik tot slot een stuk van de syntaxis dat soort merken intuïtief gevoel en eigenlijk Gebruik een pijl here, waardoor gaan van dat adres aan de integer daar in. Dus het is zeer vergelijkbaar in geest van de puntoperator, maar omdat pointer geen pointer en niet een echte structuur zelf, we gebruiken alleen de pijl. 

Als het huidige knooppunt I, de tijdelijke variabele, ben wijzend op is niet N, wat wil ik doen? Nou, met mijn menselijke vrijwilligers dat we hier de andere dag, als mijn eerste mens is niet degene die ik willen, en misschien de tweede mens is niet degene die ik wil, en de derde, ik moeten fysiek in beweging te houden. Net als hoe ik stap door een lijst? Toen hadden we een array u, net deed alsof ik plus plus. Maar in dit geval volstaat doen wijzer, krijgt, wijzer, naast. Met andere woorden, het volgende veld is net als alle linker handen dat onze menselijke vrijwilligers op maandag werden gebruikt om te wijzen op een ander knooppunt. Dat waren hun volgende buren. 

Dus als ik wil om door deze lijst, Ik kan niet zomaar doen ik plus plus meer, Ik heb in plaats daarvan te zeggen Ik, wijzer, gaat evenaren ongeacht het volgende veld, het volgende veld is het volgende veld, na al die linker handen dat we op het podium pointing enkele opeenvolgende waarden. En als ik via dat hele iteratie, en tot slot, ik raakte null niet hebben gevonden N nog, ik heb net return false. Dus nogmaals, alles wat we hier doen, zoals in de foto een moment geleden, begint door te wijzen op de begin van de lijst vermoedelijk. En dan heb ik te controleren, is de waarde Ik ben op zoek naar die gelijk is aan negen? Als dat zo is, ik terug waar en ik ben klaar. Zo niet, ik mijn hand te werken, AKA pointer te wijzen op de locatie van de volgende pijl's en dan is de locatie van het volgende pijl's, en de volgende. Ik ben gewoon wandelen door deze array. 

Dus nogmaals, who cares? Zoals wat is dit ingrediënt voor? Nou, herinneren dat we geïntroduceerd het begrip van een stapel, die is een abstracte data typen, voor zover het geen C ding, het is niet een CS50 ding, het is een abstract idee, dit idee van stapelen dingen bovenop elkaar dat kan worden geïmplementeerd trossen verschillende manieren. En een manier waarop we voorgesteld was met een array of een gekoppelde lijst. En het blijkt dat canoniek, een stack ondersteunt ten minste twee operaties. En de buzz woorden zijn duwen, om duwen iets op de stack, zoals een nieuwe verpakking in het eetzaal, of pop, wat betekent dat de bovenste verwijderen lade van de stapel in de eetzaal hal, en dan misschien wat andere operaties ook. Dus hoe kunnen we de structuur definiëren dat we nu belt een stapel? 

Nou, we hebben allemaal de vereiste syntax tot onze beschikking in C. zeg ik, geef me een soort definitie van een structuur binnenkant van een stapel, Ik ga zeggen is een array, van een heleboel nummers en grootte. Dus met andere woorden, als ik wil om dit te implementeren in code, laat me gaan en gewoon een soort van tekenen wat dit zegt. Dus dit zegt, geef me een structuur die heeft een array, en ik weet niet wat de capaciteit is, het is blijkbaar een aantal constante die ik heb elders gedefinieerd, en dat is prima. Maar veronderstel dat het is slechts een, twee, drie, vier, vijf. Dus de capaciteit is 5. Dit element binnenkant van mijn structuur wordt opgeroepen nummers. En dan moet ik een andere variabele blijkbaar riep grootte die in eerste instantie ga ik te bepalen wordt geïnitialiseerd op nul. Als er niets in de stack, grootte nul, en het vuilnis waarden in getallen. Ik heb geen idee wat er in zit gewoon nog niet. 

Dus als ik wil duwen iets wat op de stapel, veronderstel ik noem de functie push, en Ik zeg duw 50, net als de nummer 50, waar zou u voorstellen Ik trek hem in deze serie? Er zijn vijf verschillende mogelijke antwoorden. Waar wil je het nummer 50 te duwen? Als het doel hier, opnieuw, bel dan de push-functie, passeren in een argument 50, waar moet ik het zeggen? Vijf possible-- 20% kans van correct gissen. Ja? 

Publiek: Helemaal rechts. 

SPEAKER 1: Helemaal rechts. Er is nu een 25% kans van correct gissen. Dus dat zou eigenlijk wel goed. Volgens afspraak, zeg ik met een array, We zouden beginnen meestal links, maar we konden zeker vanaf rechts. Zodat de spoiler hier zou ik ben waarschijnlijk gaan om het trekken aan de linkerkant, net als in een normale reeks, waar Ik begin naar links naar rechts. Maar als je kunt spiegelen het rekenkundig, prima. Het is gewoon niet conventioneel. Oké, ik moet te maken meer veranderen wel. Nu dat ik iets heb geduwd op de stapel, wat is het volgende? 

Oké, ik heb om de grootte te verhogen. Dus laat me gaan en gewoon actualiseren dit, dat nul was. En in plaats daarvan nu, ga ik de waarde één zetten. En nu denk ik nog een duw nummer op de stapel, zoals 51. Nou, ik moet nog een maken verandering, die is aan de grootte van twee. En dan denk ik duw één nummer op de stapel, zoals 61, nu moet ik het formaat werken een meer tijd, en krijgt de waarde 3 als de grootte. En nu denk ik bel pop. Nu pop, volgens afspraak, geen argument te nemen. Met een stack, heel punt van de metafoor tray is dat je geen inzicht hebt gaan halen die lade, kan alles wat je doet is pop de bovenste één van de stack, gewoon omdat. Dat is wat deze datastructuur doet. 

Dus door die logica als ik zeggen pop, wat komt er uit? Zo 61. Dus wat er werkelijk is de computer gaan doen in het geheugen? Wat doet mijn code hoeft te doen? Wat zou u voorstellen we veranderen op het scherm? Wat moet veranderen? Sorry? Dus krijgen we ontdoen van 61. Dus kan ik zeker doen. En ik kan ontdoen van 61. En dan wat andere verandering moet gebeuren? Maat heeft waarschijnlijk terug naar twee. En dus dat is prima. Maar wacht eens even, maat een moment geleden was drie. Laten we gewoon een snelle sanity check. Hoe hebben we weten dat we wilde om zich te ontdoen van 61? Omdat we knallen. En dus heb ik deze tweede eigenschap grootte. 

Wacht even, ik ben Terugdenkend aan week twee toen we begonnen te praten over arrays, waar was locatie nul, dit was één locatie, dit was de locatie twee, dit plaats drie, vier, het lijkt alsof de relatie tussen de grootte en het element dat ik wil verwijderen uit de array lijkt net wat? Minus één. En dus dat is hoe als mensen we weten dat 61 de eerste plaats komt. Hoe gaat het met de computer te gaan om te weten? Wanneer uw code, waar u waarschijnlijk wilt grootte min één te doen, dus drie min één twee, en dat betekent dat we willen om zich te ontdoen van 61. En dan kunnen we inderdaad te werken de grootte, zodat de grootte nu gaat van drie naar twee. En alleen maar om belerend te zijn, ga ik voor te stellen dat ik klaar ben, toch? U voorgesteld intuïtief correct moet ik ontdoen van 61. Maar heb ik niet soort soort gekregen ontdoen van 61? Ik heb effectief vergeten dat het eigenlijk daar. En denk terug aan PSET4, als je hebt gelezen het artikel over forensisch onderzoek, de PDF- dat we jullie lezen, of u zal deze week lezen PSET4. Bedenk dat dit is eigenlijk relevant voor het hele idee van computer forensics. Wat een computer algemeen doet is het gewoon vergeet waar iets is, maar het gaat niet verder in en net probeer het uit of override krassen die bits met nullen en enen of een ander willekeurig patroon tenzij u zelf doen met opzet. Dus je intuïtie was Goed, laten zich te ontdoen van 61. Maar in werkelijkheid, hoeven we niet te storen. We hoeven alleen maar te vergeten dat het is er door het veranderen van onze omvang. 

Nu is er een probleem met deze stapel. Als ik blijf dingen duwen op de stapel, wat is uiteraard gaat gebeuren in slechts een paar momenten de tijd? We gaan uit van de ruimte om te rennen. En wat doen we? We soort geschroefd. Deze implementatie niet laat ons het formaat van de matrix, omdat het gebruik van deze syntax, als u denk terug aan week twee, als je eenmaal hebt verklaard de grootte van een array, hebben we een mechanisme, waar nog niet gezien kunt u de grootte van de array te wijzigen. En inderdaad C heeft niet die functie. Als je zegt geef me vijf Nths, noemen ze nummers, dat is alles wat je gaat om het te krijgen. Dus we nu doen vanaf maandag, hebben het vermogen om een ​​oplossing te drukken hoewel, we hoeven alleen maar te tweaken de definitie van onze stack enkele hardcoded matrix niet, maar gewoon om een ​​adres op te slaan. 

Waarom is dit? Nu moeten we gewoon comfortabel met zijn dat als mijn programma draait, Ik ben vermoedelijk gaan moet de menselijke vragen hoeveel nummers wilt u opslaan? Dus de ingang moet ergens vandaan komen. Maar zodra ik weet dat nummer, dan kan ik alleen maar Gebruik welke functie te geven me een brok van geheugen? Ik kan gebruiken malloc. En ik kan een aantal zeggen bytes Ik wil terug voor deze nths. En alles wat ik heb om op te slaan in de nummers variabele hier binnenkant van deze structuur wat zou moeten zijn? Wat er werkelijk gaat in de getallen in dit scenario? Ja, een verwijzing naar het eerste byte van dat stuk van het geheugen, of meer specifiek, het adres de eerste van deze bytes. Maakt niet uit of het een byte of een miljard bytes, Ik moet alleen de zorg over de eerste. Want wat malloc garanties en mijn besturingssysteem garanties, is dat de brok van geheugen I krijgen, gaat het aaneengesloten te zijn. Er is niet van plan om hiaten zijn. Dus als ik 50 ben gevraagd bytes of 1000 bytes, ze allemaal gaan worden rug aan rug aan rug. En zolang ik me herinner hoe groot, hoe veel vroeg ik voor, alles wat ik moet weten is het eerste adres. 

Dus nu hebben we de mogelijkheid om in de code. Zij, het gaat om ons meer tijd om dit te schrijven op, we kunnen nu herverdelen dat het geheugen door gewoon een ander adres op te slaan er als we willen een groter of zelfs een kleiner deel van het geheugen. Dus hier om een ​​afweging. Nu krijgen we dynamiek. We hebben nog steeds contiguousness ik te beweren. Omdat malloc ons zal geven een aaneengesloten stuk van het geheugen. Maar dit gaat om een ​​pijn in zijn de nek voor ons, de programmeur, daadwerkelijk coderen up. Het is gewoon meer werk. We moeten code verwant aan wat ik was bonzen uit slechts een moment geleden. Zeer goed te doen, maar het voegt complexiteit. En dus ontwikkelaar tijd, programmeur de tijd is nog een andere bron dat we nodig zou kunnen hebben om te besteden wat tijd om nieuwe functies te krijgen. En dan is er natuurlijk een wachtrij. We zullen niet in deze te gaan een in veel detail. Maar het is zeer vergelijkbaar in de geest. Ik kon een wachtrij uit te voeren, en zijn overeenkomstige operaties, enqueue of dequeue, zoals toevoegen of verwijderen, het is gewoon een liefhebber manier om te zeggen dat, enqueue of dequeue, als volgt. Ik geef mezelf een structuur heeft dat nog eens serie een aantal's, heeft dat nog eens een afmeting, maar waarom moet ik nu nodig te houden van de voorzijde van een wachtrij bewaren? Ik hoefde niet te weten de voorkant van mijn stack. Nou, als ik opnieuw voor een queue-- laten we gewoon moeilijk code het als het hebben als vijf integers hier mogelijk. Dus dit nul, één, twee, drie, vier. Dit gaat worden riep opnieuw nummers. En deze zal worden genoemd size. 

Waarom is het niet voldoende gewoon formaat hebben? Nou, laten we duw die dezelfde nummers op. Dus ik pushed-- ik enqueued, of geduwd. Nu zal ik enqueue 50, en vervolgens 51 en vervolgens 61, en dot dot dot. Dus dat is enqueue. Ik enqueued 50, dan 51, dan 61. En die identiek uitziet Stapels nu toe, behalve dat ik geen behoefte aan een verandering te maken. Ik moet dit formaat te werken, dus ik ga van nul tot 1 tot 2 tot 3 kaarten. Hoe kan ik dequeue? Wat gebeurt er met dequeue? Wie moet deze lijst eerst komt uit als het de rij bij de Apple Store? Zo 50. Dus het is een beetje lastiger deze keer. Overwegende dat de laatste keer dat het was super gemakkelijk om gewoon te doen grootte minus één, Ik aan het einde van mijn reeks effectief waar de nummers zijn, het verwijdert 61. Maar ik wil niet te verwijderen 61. Ik wil nemen 50, die was er op 05:00 in de rij voor de nieuwe iPhone of zo. En dus te ontdoen van 50, I kan dit niet alleen doen, toch? Ik kan doorstrepen 50. Maar we zeiden dat we moeten niet zo anal worden als uitkrabben of de gegevens te verbergen. We kunnen gewoon vergeten waar het is. 

Maar als ik mijn maat veranderen nu twee, is dit voldoende informatie om te weten wat er gaande is in mijn wachtrij? Niet echt. Net als mijn maat is twee, maar waar komt de wachtrij begint, vooral als ik heb nog steeds die dezelfde nummers in het geheugen. 50, 51, 61. Dus ik moet onthouden nu waar de voorkant is. En zo heb ik voorgesteld up daar zullen we net hebben genoemd N front, waarvan de eerste waarde moet wat geweest? Nul, maar het begin van de lijst. Maar nu naast decrementeren de grootte, we verhogen de voorkant. Nu hier is een ander probleem. Dus zodra ik blijven gaan. Veronderstel dat dit is het aantal zoals 121, 124, en dan, dammit, Ik ben uit de ruimte. Maar wacht eens even, ik ben niet. Dus op dit punt in het verhaal, veronderstellen dat de grootte één, twee, drie, vier, zodat veronderstellen dat de size vier de voorste één, dus 51 is aan de voorzijde. Ik wil een ander nummer hier te zetten, maar, verdomme, ik ben uit de ruimte. Maar ik ben niet echt, toch? Waar kan ik een aantal toegevoegde waarde, zoals 171? Ja, ik kon gewoon een soort van ga terug daar, toch? En dan steken de 50, of gewoon overschrijven met 171. En als je je afvraagt ​​waarom onze nummers werd zo willekeurig, Deze worden vaak computer taken wetenschap cursussen op Harvard na CS50. Maar dat was een goede optimalisatie, want nu ben ik niet verspillen ruimte. Ik heb nog steeds te onthouden hoe groot dit ding is totaal. Het is vijf in totaal. Omdat ik het niet wil start overschrijven 51. Dus nu ben ik nog steeds uit de ruimte, dus hetzelfde probleem als voorheen. Maar je kunt zien hoe nu in de code, heb je waarschijnlijk moet je een beetje meer te schrijven complexiteit om dat te realiseren. En inderdaad, welke operator in C waarschijnlijk laat u dit de circulariteit magisch doen? Ja, de modulo operator, het percentage teken. Dus wat is een soort van cool over een wachtrij, ook al houden wij tekenen arrays omdat deze als rechte lijnen, als je soort van denken over dit als gebogen rond als een cirkel, dan gewoon intuïtief dat soort werkt mentaal Ik denk dat een beetje schoner. Je zou nog steeds moeten uitvoeren dat mentale model in de code. Dus niet zo moeilijk, uiteindelijk, te implementeren, maar we nog steeds verliest de omvang-- eerder, de mogelijkheid om het formaat, tenzij we dit doen. 

Wij hebben om zich te ontdoen van de array, we te vervangen door een enkele wijzer, en dan ergens in mijn code ik heb een roep welke functie om daadwerkelijk te creëren de array gebelde nummers? Malloc, of iets dergelijks functie, precies. Vragen over stapels of wachtrijen. Ja? Goede vraag. Wat modulo zou u hier te gebruiken. Dus in het algemeen bij gebruik mod, zou je het doen de omvang van de geheel gegevensstructuur. Zo iets als vijf of capaciteit, indien het is constant, is waarschijnlijk betrokken. Maar gewoon modulo vijf doen waarschijnlijk onvoldoende, want we moeten weten doen we wrap around hier of hier of hier. Dus je bent waarschijnlijk ook gaat te willen betrekken de grootte van het ding of de voorste variabele ook. Dus het is gewoon deze relatief eenvoudige rekenkundige uitdrukking, maar modulo zou het belangrijkste ingrediënt zijn. 

Dus korte film als je wil. Een animatie die sommige mensen aan een andere universiteit samen te stellen dat we hebben aangepast voor deze discussie. Het gaat om het leren van de Jack feiten over wachtrijen en statistieken. 

FILM: Once upon a time, Er was een jongen genaamd Jack. Als het ging om het maken van vrienden, Jack had geen talent. Dus Jack ging naar de te praten populairste jongen wist hij. Hij ging naar Lou en vroeg: Wat moet ik doen? Lou zag dat zijn vriend was echt bedroefd. Nou, begon hij, net kijk eens hoe je gekleed bent. Heb je geen kleren met een andere look? Ja, zei Jack. Dat doe ik zeker. Kom naar mijn huis en Ik zal ze laten zien. Dus gingen ze af naar Jack's. En Jack liet Lou de doos waar hij hield al zijn overhemden, en zijn broek en zijn sokken. Lou zei, ik zie je hebt al je kleren in een stapel. Waarom ga je niet dragen wat anderen af ​​en toe? 

Jack zei, nou ja, toen ik verwijder kleding en sokken, Ik was ze en zet ze weg in de doos. Dan komt de volgende 's morgens, en tot ik hop. Ik ga naar de doos en krijg mijn kleren uit de top. Lou snel gerealiseerd het probleem met Jack. Hij hield kleding, cd's, en boeken in de stapel. Toen hij bereikte voor iets te lezen of om te dragen, hij zou kiezen voor de top boek of ondergoed. Toen hij klaar was, hij zou het te zetten terug. Terug zou gaan, boven op de stapel. Ik weet de oplossing, zei een triomfantelijke Loud. Je nodig hebt om te leren beginnen met een wachtrij. Lou nam Jack's kleding en hing ze in de kast. En toen hij had geleegd de doos, hij gooide het. 

Toen zei hij, nu Jack, aan het einde van de dag, zet je kleren aan de linkerkant wanneer je ze weg. Dan morgen ochtend als je zie de zon, krijg je kleren aan de rechterkant, vanaf het einde van de lijn. Zie je niet? zei Lou. Het zal zo leuk zijn. U vindt alles een keer te dragen voordat je iets twee keer te dragen. En met alles in de rij in zijn kast en plank, Jack begon te voelen helemaal zeker van zichzelf. Alle dank aan Lou en zijn prachtige wachtrij. SPEAKER 1: Oké, het is schattig. Dus wat er werkelijk aan de hand op onder de motorkap nu? Dat we pointers, dat wij malloc, dat we de mogelijkheid om te creëren brokken van het geheugen voor onszelf dynamisch. Dus dit is een beeld dat wij glimp net de andere dag. We hebben niet echt wonen op, maar deze foto is er aan de hand eronder de kap voor weken nu. En dus dit betekent, net een rechthoek die we hebben getrokken, geheugen van uw computer. En misschien uw computer, of CS50 ID, heeft een gigabyte aan geheugen of RAM of twee gigabyte of vier. Het maakt eigenlijk niet uit. Uw besturingssysteem Windows of Mac OS of Linux, maakt in wezen het programma om te denken dat het heeft toegang het geheel van geheugen van uw computer, hoewel je zou worden uitgevoerd meerdere programma's tegelijk. Dus in werkelijkheid, dat werkt niet echt. Maar het is een soort van een illusie gegeven om al uw programma's. Dus als je had twee optredens van RAM-geheugen, deze is hoe de computer zou kunnen denken. 

Nu toevallig een van deze dingen, een van deze segmenten van het geheugen, wordt een stapel. En inderdaad elk moment tot nu toe in het schrijven van code dat u wel een functie, bijvoorbeeld de belangrijkste. Herinneren dat elke keer dat ik heb het geheugen van de computer getrokken, Ik trek altijd een soort van de helft van een rechthoek hier en niet de moeite praten over wat er boven. Want als belangrijkste wordt genoemd, ik beweer dat u deze strook van het geheugen krijgen dat gaat hier beneden. Als belangrijkste noemde functie als ruilmiddel, goed swap gaat hier. En het blijkt, dat is waar het belanden. Op iets genaamd een stapel binnenkant van het geheugen van uw computer. Nu aan het eind van de dag, dit is gewoon adressen. Het is net als byte nul, één byte, byte 2 miljard. Maar als je erover nadenkt aangezien dit rechthoekig voorwerp, alle we elke doen tijd noemen we een functie gelaagdheid een nieuw stukje van het geheugen. We geven die functie een plak eigen geheugen werken. 

En herinner me nu dat dit belangrijk is. Want als we hebben iets als swap en twee lokale variabelen zoals A en B we de waarden van de ene en twee twee en één, recall dat wanneer swap terugkeert, het is alsof dit stukje van het geheugen is gewoon weg. In werkelijkheid, het is nog steeds er forensisch. En wat is er eigenlijk nog steeds. Maar conceptueel, het is zo al is het helemaal weg. En zo de belangrijkste kent geen van de werkzaamheden die werd gedaan doordat swap functie, tenzij daadwerkelijk die wordt doorgegeven argumenten wijzer of door verwijzing. Nu, de fundamentele oplossing om dat probleem met de swap passeert dingen op adres. Maar het blijkt ook, wat is er aan de hand boven dat deel van de rechthoek al die tijd is maar er is er meer geheugen. En als je dynamisch geheugen toewijzen, of het nu de binnenkant van GetString, waarvan we hebben gedaan voor u in de CS50 bibliotheek, of als jullie bellen malloc en vragen het besturingssysteem voor een brok van geheugen, komt niet uit de stapel. Het komt uit een andere plaats in het geheugen van de computer dat heet de heap. En dat is niet anders. Het is hetzelfde RAM. Het is hetzelfde geheugen. Het is gewoon het RAM-geheugen dat is up er in plaats van hier beneden. 

En wat betekent dat? Nou, als uw computer een beperkte hoeveelheid geheugen en de stapel groeit, dus te spreken, en de hoop, volgens deze pijl, groeit naar beneden. Met andere woorden, elke keer dat je malloc noemen, je wordt gegeven een plak geheugen van boven, dan misschien een beetje lager, dan een beetje lager, elke keer als je belt malloc, de hoop, het gebruik, is soort groeit, groeien dichter en dichter bij wat? De stapel. Betekent dit lijkt een goed idee? Ik bedoel, waar het niet echt duidelijk wat je kunt doen als je maar een beperkte hoeveelheid geheugen. Maar dit is zeker slecht. Die twee pijlen zijn op een Stoomcursus voor elkaar. 

En het blijkt dat de bad guy, mensen die zijn bijzonder goed met de programmering, en proberen om inbreken in computers, kan deze realiteit te exploiteren. In feite, laten we eens kijken een klein fragment. Dus dit is een voorbeeld kunt u lezen over meer in detail op Wikipedia. Wij zullen u wijzen op de artikel als nieuwsgierig. Maar er is een aanval over het algemeen bekend als buffer overflow dat bestaat zolang mensen het vermogen om te manipuleren hebben gehad De computergeheugen, vooral in C. Dit is dus een willekeurig programma, maar laten we het lezen van onder naar boven. Hoofd in argc char ster argv. Dus het is een programma dat duurt command line argumenten. En alle belangrijke blijkbaar is bellen een functie, noem het F voor eenvoud. En het gaat in wat? Argv van één. Het gaat dus in F, ongeacht het woord is dat de gebruiker getypte bij de prompt na de naam van het programma's op alle. Zoveel als Caesar of Vigenere, die je zou herinneren doen met argv. 

Dus wat is F? F neemt in een string als enige argument, AKA een char ster, dezelfde ding, als een string. En het is willekeurig heet bar in dit voorbeeld. En dan char c 12, alleen in termen van de leek, Wat is char c beugel 12 voor ons doet? Wat is er te doen? Toewijzen van geheugen, in het bijzonder 12 bytes 12 tekens. Precies. En dan de laatste regel, roer en kopiëren, hebt u waarschijnlijk niet gezien. Dit is een string kopie functie waarvan het doel in het leven is haar tweede argument kopiëren in zijn eerste argument, maar slechts tot een aantal bytes. Dus de derde argument zegt: hoeveel bytes moet je mij? De lengte van de bar, ongeacht de gebruiker getypt. En de inhoud van bar, die string, zijn in het geheugen gekopieerde wees op bij C. 

Dus dit lijkt soort dom, en het is. Het is een gekunsteld voorbeeld maar het is representatief van een klasse van aanvalsvectoren, een manier van het aanvallen van een programma. Alles is prima en goed als de gebruiker types in een woord, dat is 11 tekens of minder, plus de backslash nul. Wat als de gebruiker soorten in meer dan 11 of 12 of 20 of 50 tekens? Wat is dit programma gaan doen? Potentieel seg fout. Het gaat blindelings alles in de bar up kopiëren zijn lengte, wat letterlijk alles in de bar, in de adresbalk wees bij C. Maar C slechts preventief gegeven als 12 bytes. Maar er is geen extra controle. Er is geen als de omstandigheden. Er is geen fout hier controleren. 

En dus wat dit programma is gaan doen is gewoon blindelings kopiëren een ding naar de andere. En dus als we deze trekken als beeld, hier is slechts een splinter van de geheugenruimte. Zo merkt aan de onderkant, we hebben de lokale variabele bar. Zodat pointer dat gaat store-- eerder dat lokale argument dat is naar de string bar slaan. En dan merk gewoon daarboven in een stack, want elke keer als je vragen voor geheugen op de stack, het gaat een beetje erboven pictorially, bericht dat we daar hebben 12 bytes. Linksboven is men C beugel nul en rechtsonder men C beugel 11. Dat is gewoon hoe de computers gaat om het uit te leggen. Dus gewoon intuïtief, als bar heeft meer dan 12 tekens in totaal, inclusief de backslash nul, waar is de 12 of de C beugel 12 gaan om te gaan? Of liever gezegd waar is de 12e vermogen of de 13de karakter, de honderdste karakter gaan om te eindigen op de foto? Boven of onder? 

Juist, want hoewel de stapel zelf groeit omhoog, zodra je spullen hebt gezet in het, het voor het ontwerp redenen, zet het geheugen van boven naar beneden. Dus als je hebt meer dan 12 bytes, je gaat om te beginnen met bar overschrijven. Nu is dat een bug, maar het is niet echt een groot probleem. Maar het is een groot probleem, want er is meer dingen gaande in het geheugen. Dus hier is hoe we misschien zet hello, om duidelijk te zijn. Als ik getypt in hallo de prompt. H-E-L-L-O backslash nul eindigt binnen die 12 bytes, en we zijn super veilig. Alles is goed. Maar als ik iets typt langer mogelijk is het gaat kruipen in bar ruimte. Maar erger nog, het blijkt al die tijd, ook al hebben we nog nooit gesproken over het, wordt de stapel gebruikt voor andere dingen. Het is niet alleen lokale variabelen. 

C is een zeer laag niveau taal. En het soort van geheim gebruikt de stapel ook om te onthouden wanneer een functie wordt aangeroepen, welke het adres van de vorige functie, dus het kan terug naar die functie springen. Dus als belangrijkste gesprekken te wisselen, onder de dingen die duwde op de stapel zijn niet alleen swaps lokale variabelen, of ook in het geheim duwde zijn argumenten, op de stapel zoals weergegeven door hier de plak rood, is het adres van de belangrijkste fysisch in het geheugen van uw computer, zodat wanneer swap wordt uitgevoerd, de computer weet dat ik nodig om terug te gaan naar de belangrijkste en eindig het uitvoeren van de belangrijkste functie. Dus dit is nu gevaarlijk, omdat als de gebruiker types in goed meer dan hallo, zodanig dat invoer van de gebruiker clobbers of overschrijft dat rode gedeelte, logisch als de computer gewoon blindelings veronderstellen dat de bytes die rode slice zijn het adres waar het zou moeten terugkeren, wat als de tegenstander is slim genoeg of gelukkig genoeg om een ​​opeenvolging van bytes gezet daar dat eruit ziet als een adres, maar het is het adres van de code dat hij wil dat de computer uit te voeren in plaats van de belangrijkste? 

Met andere woorden, als wat gebruiker te typen op de prompt, is niet alleen iets onschuldig als hello, maar het is eigenlijk de code dat is gelijk om alle bestanden van deze gebruiker wilt verwijderen? Of e-mail hun wachtwoord voor mij? Of beginnen te loggen hun toetsaanslagen, toch? Er is een manier, laten we vandaag bepalen, dat ze kon typen in niet alleen gedag wereld of hun naam, ze konden wezen passeren in de code, nullen en degenen, die de computer fouten voor zowel code en een adres. Dus hoewel enigszins abstracte wijze als de types gebruiker genoeg hoor en wederhoor code dat we hier zullen generaliseren A. A is aanval of tegenstanders. Dus gewoon slechte dingen. We niet de zorg over de nummers of de nullen of degenen vandaag de dag, zodat je uiteindelijk overschrijven dat rode gedeelte, merken dat reeks bytes. O 835 C nul acht nul. En nu als Wikipedia's artikel hier heeft voorgesteld, als je nu echt beginnen labelen van de bytes in uw computer geheugen, wat het artikel Wikipedia is voorstelt, is dat wat als het adres van die linksboven byte is 80 C 0 3508. 

Met andere woorden, indien het bad guy is slim genoeg om met zijn of haar code om daadwerkelijk zet hier een nummer dat overeen met het adres van de code hij geïnjecteerd in de computer, je kan de computer truc in iets te doen. Het verwijderen van bestanden, e-mailen dingen, snuiven uw verkeer, letterlijk alles zou kunnen zijn geïnjecteerd in de computer. En zo een buffer overflow aanval in de kern is gewoon een stom, stom dwingende van een array die had niet de grenzen gecontroleerd. En dit is wat is super gevaarlijk en tegelijkertijd super krachtig in C is dat we hebben inderdaad toegang tot overal in het geheugen. Het is aan ons, de programmeurs, die de oorspronkelijke code te schrijven aan de darn lengte van een eventuele controle arrays die wij manipuleren. Dus om duidelijk te zijn, wat is de oplossing? Als we teruggaan naar deze code, zou ik niet alleen verandert de lengte van de bar, wat anders moet ik controleren? Wat moet ik doen om volledig te voorkomen deze aanval? Ik wil niet alleen maar blindelings zeggen dat je zoveel bytes moeten kopiëren zoals de lengte van de balk. Ik wil zeggen, kopiëren als veel bytes net als in de bar tot aan de toegewezen geheugen, of 12 maximaal. Dus ik moet een soort van als voorwaarde dat doet controleert de lengte van de bar, maar als het 12, we gewoon moeilijk code overschrijdt 12 als de maximaal mogelijke afstand. Anders wordt de zogenaamde buffer overflow aanval kan gebeuren. Onderaan deze slides, als je nieuwsgierig bent om meer te lezen is de eigenlijke oorspronkelijke artikel als je wilt om een ​​kijkje te nemen. 

Maar nu, onder de prijzen hier betaald was inefficiënties. Dus dat was een snelle lage niveau kijken naar wat problemen kunnen ontstaan ​​nu dat we hebben toegang tot het geheugen van de computer. Maar een ander probleem dat we al op maandag struikelde was gewoon de inefficiëntie van een gekoppelde lijst. We zijn terug naar de lineaire tijd. We hebben een aaneengesloten reeks niet meer. We hebben geen random access. We kunnen geen gebruik maken van vierkante haakjesnotering. We hebben letterlijk een tijdje lus zoals degene die ik schreef een moment geleden. Maar op maandag, we beweerden dat we kunnen kruipen terug in het rijk van de efficiëntie het bereiken van iets dat logaritmische misschien, of best nog, misschien zelfs iets dat zogenaamde constante tijd. Dus hoe kunnen we dat doen met behulp van deze nieuwe gereedschap, deze adressen, die pointers, en threading dingen van onze eigen? Nou, stel dat Hier, dit zijn een stelletje van de nummers die we willen opslaan in een datastructuur en zoeken efficiënt. We kunnen absoluut terugspoelen tot week twee, gooi deze in een array, en zoeken ze met behulp van binaire zoeken. Verdeel en heers. En in feite schreef binary search in PSET3, waar u de vondst programma uitgevoerd. Maar weet je wat. Er is een soort van een meer slimme manier om dit te doen. Het is een beetje meer geavanceerd en wellicht laat ons toe om te zien waarom binaire zoeken is zo veel sneller. Laten we eerst eens introduceren het begrip boom. Die ook al in werkelijkheid bomen soort groeien als deze, in de wereld van de computer wetenschap zij soort neerwaartse groeien als een stamboom, waar je uw grootouders of overgrootouders of wat aan de top, de patriarch en de matriarch van de familie, maar een zogenaamde root node hieronder die zijn kinderen, waaronder zijn de kinderen, of haar nakomelingen in het algemeen. En iedereen opknoping uit de onderkant van de familie tree, naast de jongste in het gezin, kan ook gewoon generiek zijn genaamd de bladeren van de boom. 

Dus dit is gewoon een stelletje woorden en definities voor iets genaamd een boom in de computer wetenschap, net als een stamboom. Maar er is liefhebber incarnaties bomen, waarvan wordt een binaire zoekboom. En u kunt soort tease behalve wat dit ding doet. Nou, het is binaire in welke zin? Waar komt de binaire vandaan hier? Sorry? Het is niet zozeer een van beide of. Het is meer dat elk van de knooppunten geen meer dan twee kinderen, zoals we hier zien. In het algemeen, een tree-- en je ouders en grootouders kan zo veel kinderen hebben of kleinkinderen als ze eigenlijk willen, en zo bijvoorbeeld er drie hebben we kinderen uit dat rechterhand knooppunt maar in een binaire boom, een knooppunt nul, één of twee kinderen maximaal. En dat is een mooie eigenschap, want als het wordt afgedekt door twee, we gaan om te kunnen een beetje log base twee actie gebeurt hier uiteindelijk. Dus we hebben iets logaritmische. Maar meer op dat in een moment. Zoekboom betekent dat de nummers zijn zodanig ingericht dat de linker kind waarde groter is dan de wortel. En zijn recht kind groter dan de wortel. Met andere woorden, als u een van de te nemen knooppunten, de cirkels in deze foto, en kijkt naar zijn linker kind en zijn recht kind, het eerste lager dient te zijn dan, de tweede moet groter zijn dan. Dus sanity check 55. Het linker kind is 33. Het is minder dan. 55, haar recht kind is 77. Het is groter dan. En dat is een recursieve definitie. Konden we elk een van die controleren knooppunten en hetzelfde patroon zou houden. 

Dus wat is leuk in een binaire zoekboom, is dat men, kunnen we het uit te voeren met een structuur, net als dit. En hoewel we gooien veel van de structuren op uw, ze zijn enigszins intuïtieve nu hopelijk. De syntax is nog steeds geheimzinnig zeker, maar de inhoud van een knooppunt in dit context-- en we houden gebruik van het woord knooppunt of het een rechthoek op het scherm of een cirkel, het is gewoon een aantal generieke container, in dit geval van een boom, zoals die we zagen we een integer nodig in elk van de knooppunten en dan moet ik twee pointers wijzen naar links kind en het juiste kind, respectievelijk. Dus dat is hoe we misschien implementeren die in een structuur. En hoe zou ik kunnen implementeren in de code? Nou, laten we eens een snelle kijk naar dit kleine voorbeeld. Het is niet functioneel, maar ik heb gekopieerd en geplakt die structuur. En als mijn functie een binaire zoeken boom zoeken genoemd, en dit duurt twee argumenten, N een integer en een pointer een knooppunt, zodat een pointer naar de boom of een verwijzing naar de wortel van een boom, Hoe ga ik over op zoek naar N? Nou, ten eerste, want ik ben omgaan met pointers, Ik ga een sanity check doen. Als boom gelijken gelijk aan nul, is N in deze boom dan niet in deze boom? Het kan niet, toch? Als ik voorbij null, er is niets daar. Ik kan net zo goed blindelings zeggen return false. Als je me niets, ik kan toch niet vindt een aantal N. Dus wat zou ik Check nu? Ik ga ook anders als N zeggen minder dan wat er bij de boom knooppunt dat ik heb ingeleverd N waarde. Met andere woorden, wanneer het aantal ik zoekt, N lager is dan de knoop dat ik ben op zoek naar. En het knooppunt ik zoek op boom wordt genoemd, en op te roepen uit het vorige voorbeeld de waarde om in een pointer, Ik gebruik de pijl notatie. Als n kleiner is dan tree arrow N, ik wil conceptueel gaan links. Hoe kan ik de uitdrukkelijke searching over? Om duidelijk te zijn, als dit de foto in kwestie, en ik heb doorgegeven dat bovenste arrow dat is naar beneden gericht. Dat is mijn boom pointer. Ik wees naar de wortel van de boom. En ik ben op zoek zeggen, voor het nummer 44, willekeurig. 44 is kleiner dan of groter dan 55 natuurlijk? Dus het is minder dan. En dus dit als voorwaarde geldt. Dus conceptueel, wat wil ik aan zoek volgende als ik ben op zoek naar 44? Ja? 

Precies, ik wil zoeken in de linker kind, of de linker sub-boom van deze foto. En in feite, laat me door de foto hier beneden voor slechts een moment, omdat Ik kan dit niet uitkrabben. Als ik begin hier op 55 en Ik weet dat de waarde 44 Ik ben op zoek naar is om links, het is een soort van zoals scheuren het telefoonboek in de helft of scheuren van de boom in de helft. Ik heb niet langer zorgen te maken over deze hele helft van de boom. En toch, vreemd genoeg in termen van de structuur, dit ding hier dat begint met 33, die zich is een binaire zoekboom. Ik zei het woord recursieve voordat omdat inderdaad dit is een gegevensstructuur die per definitie recursieve. Je zou een boom die dit hebben groot, maar ieder van haar kinderen vertegenwoordigt een boom net iets kleiner. In plaats van dat het opa of oma, nu is het gewoon moeder of-- Ik kan niet say-- niet mom of vader, dat zou raar zijn. In plaats van de twee kinderen is er zou zijn als broer en zus. Een nieuwe generatie van de stamboom. Maar structureel, het is hetzelfde idee. En het blijkt dat ik een functie hebben waarmee ik een binaire zoekopdracht kan zoeken boom. Het is zoeken genoemd. Ik zoek naar N in boom pijl links anders als N groter is dan de waarde dat ik momenteel op. 55 in het verhaal een ogenblik geleden. Ik heb een functie genaamd zoeken die ik kan gewoon passeren N deze en recursief zoeken de sub-boom en net terug wat dat antwoord. Else Ik heb wat laatste base case kreeg hier. 

Wat is het laatste geval is? Boom is ofwel null. De waarde die ik ofwel zoek is minder dan of groter dan die of gelijk aan. En ik kon gelijk zeggen gelijk, maar het is logisch gelijk aan gewoon hier zeggen anders. Zo waar is hoe ik iets vind. Dus hopelijk is dit een nog meer overtuigend voorbeeld dan de domme sigma-functie we hebben een paar lezingen terug, waar het was net zo gemakkelijk om een ​​lus te gebruiken optellen alle nummers een N. hier met een gegevensstructuur dat zelf is recursief gedefinieerd en recursief getrokken, nu zijn we hebben de mogelijkheid om onszelf te uiten in de code dat zichzelf is recursieve. Dus dit is exact dezelfde code hier. 

Dus wat andere problemen kunnen we oplossen? Dus snel een stap verwijderd van bomen voor een ogenblik. Hier is, zeggen de Duitse vlag. En er is duidelijk een patroon om deze vlag. En er is veel vlaggen in de wereld die zijn zo simpel als dit in termen hun kleuren en patronen. Maar stel dat wordt opgeslagen als een GIF, of JPEG, of bitmap of een ping, een grafisch bestandsformaat waarmee je bekend bent, waarvan sommige we spelen met in PSET4. Dit lijkt niet zinvol te slaan zwarte pixel, zwarte pixel, zwarte pixel, dot, dot, dot, een hele hoop zwarte pixels voor de eerste scanline, of rij, dan een hele hoop hetzelfde, dan een hele hoop dezelfde, en vervolgens een heleboel rode pixels, rode pixels, rode pixels, vervolgens geheel stelletje gele pixels, geel, toch? 

Er is hier een dergelijke inefficiëntie. Hoe zou je intuïtief comprimeren de Duitse vlag als de uitvoering ervan als een bestand? Net als wat informatie kunnen we niet moeite het opslaan op de harde schijf in orde om ons bestand te verkleinen, zoals uit een megabyte naar een kilobyte, iets kleiner? Waarin ligt de redundantie hier om duidelijk te zijn? Wat zou je doen? Ja? Precies. Waarom niet eerder dan herinneren de kleur van elke pixel darn net zoals je doet in PSET4 met de bitmap-bestandsformaat, waarom ga je niet gewoon vertegenwoordigen de meest linkse kolom van pixels, bijvoorbeeld een bos van zwarte pixels, een bos rood, en een bos van geel, en dan gewoon een of andere manier coderen idee van herhaal dit 100 keer of herhaal dit 1000 keer? Waarbij 100 of 1000 is gewoon een integer, zodat u kan wegkomen met slechts een enkel nummer in plaats van honderden of duizenden extra pixels. En inderdaad, dat is hoe we kon de Duitse vlag te comprimeren. En Nu wat over de Franse vlag? En een beetje een soort van mentale oefening, die de vlag Meer op de schijf worden gecomprimeerd? De Duitse vlag of de Franse vlag, als we die aanpak? De Duitse vlag, omdat er meer horizontale redundantie. En door het ontwerp, veel grafische bestanden formaten inderdaad werken zoals scan-lijnen horizontaal. Ze kunnen werken verticaal, maar de mensheid besloot jaren geleden dat we over het algemeen denken aan dingen rij per rij in plaats van kolom voor kolom. Dus inderdaad als je om te kijken naar het bestand grootte van een Duitse vlag en een Franse vlag, mits de resolutie hetzelfde, dezelfde breedte en hoogte, deze hier zal groter zijn, omdat je moet je drie keer te herhalen. Je moet blauw, herhaal opgeven uzelf, wit, herhaal je voor, rood, herhaal jezelf. Je kunt niet zomaar gaan allemaal helemaal naar rechts. En als een terzijde, te maken duidelijk de compressie overal, als deze vier frames van een video-- u misschien herinneren dat een film of video in het algemeen zoals 29 of 30 frames per seconde. Het is net een klein flip boek waar u afbeelding, beeld, beeld, zien, het super snel, dus het ziet er net als de acteurs op het scherm te bewegen. Hier is een hommel op top van een bos bloemen. En al is het misschien soort zijn moeilijk te zien op het eerste gezicht, de enige bewegen deze film is de bijen. 

Wat is stom over het opslaan video ongecomprimeerd? Het is een soort van een verspilling om video op te slaan vier bijna identieke beelden die verschillen alleen in zoverre waar de bijen is. U kunt weggooien meest van die informatie en herinner me alleen, bijvoorbeeld, het eerste frame en het laatste frame, keyframes Als je hebt ooit gehoord van het woord, en gewoon opslaan in de midden waar het bij is. En je hoeft niet te opslaan van alle van de roze, en de blauwe en de groene waarden ook. Dus dit is alleen dat compressie is overal. Het is een techniek die we vaak gebruiken of voor lief nemen deze dagen. 

Maar hoe doe je tekst te comprimeren? Hoe ga je over de tekst te comprimeren? Nou ja, elk van de personages in ASCII is een byte, of acht bits. En dat is een beetje dom, toch? Omdat je waarschijnlijk type A en E en I en O en U veel vaker dan als W of Q of Z, afhankelijk van de taal waarin je bent zeker het schrijven. En dus waarom maken we gebruik acht bits voor elke letter, waaronder de minst populaire brieven, toch? Waarom niet minder bits voor gebruik de super populaire brieven, zoals E, de dingen die je denk eerst in Rad van Fortuin, en gebruiken meer bits voor de minder populaire letters? Waarom? Omdat we gewoon gaan gebruiken ze minder vaak. 

Nou, het blijkt dat daar zijn pogingen gedaan om dit te doen. En als u zich herinneren van de rang school of middelbare school, morse code. Morsecode heeft puntjes en streepjes die kunnen worden overgebracht langs een draad als geluiden of signalen van een soort. Maar Morse code is een super schoon. Het is een soort van een binair systeem dat u stippen of streepjes. Maar als je, bijvoorbeeld, twee punten. Of als u denkt terug aan de exploitant die gaat als piep, piep, piep, piep, het raken van een kleine trekker dat een signaal, Als u de ontvanger, krijgt twee stippen, welke boodschap heb je gekregen? Volkomen willekeurig. 

Ik? Ik? Of wat about-- of ik? Misschien was het gewoon twee rechte E's? Dus er is dit probleem van decodeerbaarheid met Morse code, waarbij tenzij persoon kan u het bericht eigenlijk pauzeert zodat u kunt sorteren van zien of horen de kloof tussen letters, het is niet voldoende om alleen stuur dan een stroom van nullen en enen, of puntjes en streepjes, omdat er onduidelijkheid. E is een enkele punt, dus als je zie twee punten of hoort twee punten, misschien is het twee E's of misschien is het een I. Dus hebben we een systeem dat is een behoefte iets slimmer dan dat. Dus een man genaamd Huffman jaar geleden kwam met precies dit. Dus we gaan gewoon om een ​​snelle blik te nemen hoe bomen zijn relevant voor deze. Veronderstel dat dit sommige dom bericht dat u wilt verzenden, samengesteld alleen A, B, C's D's en E's, maar er is veel redundantie hier. Het is niet de bedoeling in het Engels zijn. Het is niet versleuteld. Het is gewoon een dom bericht met veel herhaling. Dus als je eigenlijk tellen alle A, B, C's, D's en E's, hier de frequentie. 20% van de letters A, 45% van de letters zijn E's, en drie andere frequenties. We telden daar handmatig en net deed de wiskunde. 

Dus het blijkt dat Huffman, enige tijd geleden, besefte dat, je weet wat, als ik begin gebouw een boom, of een bos van bomen, als je wil, als volgt, kan ik het volgende doen. Ik ga een knooppunt aan elk geven van de brieven die ik de zorg over en ik ga om te slaan binnenin dat knooppunt de frequenties als floating point waarde, of je kan het gebruiken van een N, ook, maar we zullen gewoon gebruik maken hier een vlotter. En het algoritme dat stelde hij, is dat je neem dit woud van enkele knoop bomen, dus super korte bomen, en je begint ze te verbinden met nieuwe groepen, nieuwe ouders, als je wil. En u dit doen door te kiezen voor de twee kleinste frequenties tegelijk. Dus nam ik de 10% en 10%. Ik maak een nieuw knooppunt. En ik roep de nieuwe knooppunt 20%. 

Die twee knooppunten combineer ik de volgende stap? Het is een beetje dubbelzinnig. Dus er is een hoekje gevallen beschouwen, maar om dingen vrij te houden, Ik ga om uit te kiezen 20% - Ik negeer nu de kinderen. Ik ga om uit te kiezen 20% en 15% en trekken twee nieuwe randen. En nu die twee knooppunten ik logisch combineren? Negeer alle kinderen, alle kleinkinderen, kijk maar naar de wortels nu. Welke twee knopen heb ik samen te binden? Punt twee en 0,35. Dus laat me trekken twee nieuwe randen. En dan heb ik maar één links. Dus hier is een boom. En het is met opzet opgesteld te kijken soort van mooie, maar merken dat de randen Ook bestempeld nul en één. Dus alle linkerranden nul willekeurig, maar consequent. Alle rechterrand zijn degenen. 

En dus wat Hoffman voorgesteld is, als je wilt een B vertegenwoordigen, plaats geven het aantal 66 als Een ASCII die hele acht bits, weet je wat, gewoon winkel het patroon nul, nul, nul, nul, want dat is de weg uit mijn boom, Mr. Huffman de boom, aan het blad van de wortel. Als je wilt naar een winkel E daarentegen niet stuur acht bits die een E. vertegenwoordigen In plaats daarvan stuurt welk patroon bits? Een. En wat is er leuk is aan dit dat E is de meest populaire letter, en je bent met behulp van de kortste code voor het. De volgende meest populaire brief lijkt alsof het was A. En hoeveel bits heeft hij voorgesteld met behulp van voor dat? Nul, één. 

En omdat het uitgevoerd als deze boom, voor nu laat me bepalen is er geen dubbelzinnigheid zoals in Morse code, omdat alle brieven u de zorg over aan het einde van deze randen. Dus dat is slechts een toepassing van een boom. Dit is-- en ik zal zwaaien mijn hand op deze manier waarop u kan dit implementeren als C constructie. We hoeven alleen maar te combineren een symbool, zoals een char, en de frequentie links en rechts. Maar laten we eens kijken naar twee laatste voorbeelden die je zult behoorlijk vertrouwd met na quiz nul probleem van de vijf. 

Dus er is de datastructuur bekend als een hashtabel. En een hash-tabel is een soort van afkoelen doordat het bakken. En stel dat er vier emmers hier, slechts vier spaties. Hier is een spel kaarten, en hier is club, spade, club, diamanten, club, diamanten, club, diamanten, clubs-- dus dit is het willekeurig. Harten, Hearts-- dus ik ben bucketizing alle ingangen in. En een hash table behoeften te kijken naar uw input, en dan zet het in een bepaalde plaats op basis van wat je ziet. Het is een algoritme. En ik was met behulp van een super eenvoudige visuele algoritme. Het moeilijkste deel van die herinneren wat de foto's waren. En dan is er nog vier in totaal dingen. 

Nu werden de stapels groeien, waarbij is een bewuste ontwerp ding hier. Maar wat zou ik doen? Dus eigenlijk hier hebben we een stelletje oude school examen boeken. Stel dat een stelletje studenten namen zijn hier. Hier is een groter hash tafel. In plaats van vier emmers, Ik heb, laten we zeggen 26. En we niet willen gaan lenen 26 dingen van buiten [? Annenberg?], Dus hier is vijf die vertegenwoordigen A tot Z. En als ik zie een leerling wiens achternaam begint met A, Ik ga naar zijn of haar quiz daar te zetten. Als iemand begint met C, daar, A-- eigenlijk niet willen doen. B gaat over hier. Dus ik heb A en B en C. En nu hier is nog een student. Maar als dit hash tafel uitgevoerd met een matrix, Ik ben soort geschroefd op dit punt, toch? Ik heb soort om dit ergens te zetten. 

Dus een manier waarop ik kan dit op te lossen is, alle rechts, A is druk, B bezet is, C is bezet. Ik ga hem in D. zetten Dus op eerste, heb ik willekeurig direct toegang elk van de bakken voor de leerlingen. Maar nu is het soort decentrale iets lineaire, want als ik wil om te zoeken naar iemand waarvan de naam begint met A, controleer ik hier. Maar indien dit niet het A student Ik ben op zoek naar, Ik heb soort te beginnen met het controleren de emmers, want wat ik deed was een soort van lineair sonde de gegevensstructuur. Een domme manier om te zeggen kijk maar voor de eerste beschikbare opening, en bevestigd op een plan B, zogezegd, of plan D in dit geval de waarde op die locatie plaats. Dit is gewoon zo dat als je hebt kreeg 26 locaties en geen studenten met de naam Q of Z, of iets dergelijks dat, in ieder geval dat je het gebruik van de ruimte. 

Maar we hebben al meer gezien slimme oplossingen hier, toch? Wat zou je doen in plaats als je een aanrijding? Als twee mensen hebben de naam A, wat zou hebben een slimmere of meer geweest intuïtieve oplossing dan alleen putting Een waarbij D hoort te zijn? Waarom heb ik niet zomaar gaan buiten [? Annenberg?], zoals malloc, een ander knooppunt, zet het hier, en vervolgens dat een student hier. Zodat ik in wezen een soort van een array, of misschien meer elegant als we begint een gekoppelde lijst te zien. 

En zo een hash-tabel is een structuur dat kan er net als dit, maar slim, je iets te noemen aparte chaining, waarbij een hash table eenvoudigweg een array, elke waarvan de elementen geen getal, is zelf een gelinkte lijst. Zodat je super snelle toegang beslissen waar je waarde hash aan. Net als met de kaarten bijvoorbeeld, Ik heb super snelle beslissingen. Harten gaat hier, diamanten gaat hier. Same here, A gaat hier, D gaat hier, B komt hier. Zo super snel look-ups, en als je toevallig te lopen in een zaak waar je hebt botsingen, twee mensen met dezelfde naam, nou dan je gewoon beginnen met elkaar te koppelen. En misschien heb je houd ze naargelang alfabetisch, misschien heb je niet. Maar in ieder geval nu hebben we de dynamiek. Dus aan de ene kant hebben we super snel constante tijd, en soort van lineaire tijd die betrokken zijn als deze gekoppeld lijsten begin een beetje lang te komen. 

Dus dit soort een dwaas, geeky grap jaar geleden. Op de CS50 hack-a-thon, wanneer de studenten in te checken, sommige TF of CA jaarlijks denkt dat het is grappig om te zetten een teken als dit, waar het net betekent dat als je naam begint met een A, gaan op deze manier. Als uw naam begint met een B, ga dit-- OK, het is grappig misschien later in het semester. Maar er is een andere manier om dit te doen, ook. Kom terug naar dat. 

Dus er is deze structuur. En dit is onze laatste structuur voor vandaag, dat is zoiets als een trie. T-R-I-E, die om wat voor reden kort voor het ophalen, maar het heet trie. Dus een trie is een ander interessant amalgaam van veel van deze ideeën. Het is een boom, die we eerder hebben gezien. Het is niet een binaire zoekboom. Het is een boom met een aantal kinderen, maar elk van de kinderen in een trie een matrix. Een array van grootte, zeg, 26 of misschien 27 als je wilt koppelteken namen ondersteunen of apostrof in de namen van mensen. 

En dus dit is een datastructuur. En als je kijkt van boven naar beneden, alsof je kijk naar de bovenste knooppunt daar, M, is wijzend naar de meest linkse ding daar, dat dan A, X, W, E, L, L. Zo slechts een gegevensstructuur die willekeurig is het opslaan van namen van mensen. En Maxwell wordt opgeslagen door net na een pad van array array array. Maar wat is verbazingwekkend om een ​​trie is dat, terwijl een gelinkte lijst en zelfs een array, de beste die we ooit hebben gekregen is lineaire tijd of logaritmische tijd op zoek iemand. In deze gegevensstructuur van een trie, indien mijn datastructuur heeft één naam erin en ik ben op zoek naar Maxwell, ik ben ga hem vrij snel te vinden. Ik kijk voor M-A-X-W-E-L-L. Als Deze gegevensstructuur, daarentegen, indien N een miljoen, als er een miljoen namen in deze datastructuur, Maxwell is nog steeds gaat worden detecteerbaar na slechts M-A-X-W-E-L-L stappen. En David-- D-A-V-I-D stappen. Met andere woorden, door het bouwen een gegevensstructuur die kreeg al deze arrays, die zichzelf te onderhouden random access, Ik kan beginnen te kijken van mensen noem het gebruik van een hoeveelheid tijd die evenredig aan het aantal niet dingen in de gegevensstructuur, als een miljoen bestaande namen. De hoeveelheid tijd die het kost me te vinden M-A-X-W-E-L-L in deze gegevensstructuur niet evenredig met de omvang van de datastructuur, maar de lengte van de naam. En realistisch de namen we opzoeken zijn nooit te lang gek zijn. Misschien heeft iemand een 10 karakter te noemen, 20 karakter naam. Het is zeker eindig, toch? Er is een mens op aarde die de langste mogelijke naam, maar die naam is een constante waarde lengte, toch? Het varieert niet in enige zin. Dus op deze manier, we hebben bereikte een datastructuur die constante tijd look-up. Het vergt wel een aantal stappen afhankelijk van de lengte van de input, maar niet het aantal naam in de gegevensstructuur. Dus als we het dubbele van het aantal namen volgend jaar een miljard tot twee miljard, bevinding Maxwell gaat nemen precies hetzelfde aantal zeven stappen om hem te vinden. En dus we lijken te hebben bereikt onze heilige graal van de looptijd. 

Dus een paar aankondigingen. Quiz nul is coming up. Meer daarover op de website van de cursus in de komende paar dagen. Maandag lecture-- het is een vakantie hier bij Harvard op maandag. Het is niet in New Haven, dus we nemen de klasse naar New Haven voor de lezing op maandag. Alles wordt gefilmd en live gestreamd zoals gebruikelijk, maar laten we eindigen vandaag met een 30 seconden clip genaamd "Diepe Gedachten" door Daven Farnham, die werd geïnspireerd vorig jaar op zaterdag Night Live "Diepe Gedachten" door Jack Handy, die moet nu zinvol. 

FILM: En nu, "Deep Gedachten "door Daven Farnham. Hash tabel. 

SPEAKER 1: Oké, dat is het voor nu. We zien je volgende week. 

DOUG: Om het in actie te zien. Dus laten we een kijkje nemen op dat moment. Dus hier hebben we een ongesorteerde array. 

IAN: Doug, kun je gaan en herstarten dit voor slechts een seconde, alsjeblieft. Oké, zijn camera's rollen, dus actie wanneer je klaar, Doug bent, OK? DOUG: Oké, dus wat we hier hebben is een ongesorteerde array. En ik heb alle elementen gekleurde om aan te geven dat het in feite ongesorteerd. Zo herinneren dat het eerste wat we doen is sorteren we de linkerhelft van de array. Vervolgens sorteren we de juiste de helft van de array. En ya-da, da-ya, ya-da, we ze samen te voegen. En we hebben een volledig gesorteerde array. Dus dat is hoe fuseren soort werkt. 

IAN: Whoa, whoa, whoa, knippen, snijden, knippen, snijden. Doug, kun je niet zomaar ya-da, ya-da, ya-da, je een weg door merge soort. 

DOUG: Ik heb net gedaan. Het is goed. We zijn goed om te gaan. Laten we gewoon blijven rollen. Dus hoe dan ook, 

IAN: Je moet uitleggen deze breder dan dat. Dat is gewoon niet genoeg. Doug: Ian, we doen niet nodig hebben om terug te gaan naar één. Het is goed. Maar goed, als we doorgaan met merge-- Ian, we zijn in het midden van filmen. 

IAN: Ik weet het. En we kunnen niet zomaar ya-da, ya-da, ya-da, door het hele proces. Je moet uitleggen hoe de twee kanten krijgen samengevoegd. 

DOUG: Maar we hebben al legde uit hoe de twee sides-- 

IAN: Je hebt net getoond hen samenvoegen array. DOUG: Ze weten het proces. Ze zijn prima. We hebben meer dan het tien keer gegaan. 

IAN: Je overgeslagen precies goed overheen. We gaan terug naar een, je kan je niet ya-da, ya-DA over. Oké, terug naar één. 

DOUG: Ik heb om terug te gaan door alle van de dia's? Mijn God. Het is net als de zesde keer, Ian. Het is goed. 

IAN: Oké. Ben je klaar? Grote. Actie.