[Speel van musiek] David Malan: Dit is CS50. En dit is beide die begin en die end-- soos literally-- byna die einde van week ses. 

Ek het gedink ek wil deel 'n bietjie van 'n pret feit. Ek het hierdie getrek uit 'n afgelope semester se data stel. Jy kan onthou dat ons vra om op elke p stel vorm as jy online gekyk of as jy in die persoon bygewoon het. En hier is die data. So vandag was baie voorspelbaar. Maar ons wou 'n bietjie te spandeer tyd saam met jou nietemin. Sou iemand graag waarom dit veronderstelling grafiek is so dronk, op en af, op en af, so konsekwent? Wat doen elkeen van die hoogtepunte en krippe verteenwoordig? 

Publiek: [onhoorbaar] David Malan: Inderdaad. En meer aantrekkelijke God verbied, ons hou een lesing op 'n Vrydag aan die begin van die semester dit is wat ons sien gebeur nie. So vandag, ons deel in 'n bietjie meer oor data strukture. En om te gee jy meer van 'n vaste geestelike model vir probleme op vyf, wat is nou uit. Spelfoute, waarin ons sal julle 'n teks lêer sommige 100,000 plus Engelse woorde, en jy gaan te hê om uit te vind hoe om te slim laai hulle in die geheue, in die geheue, met behulp van 'n paar data struktuur van jou keuse. 

Nou een so 'n data struktuur kon wees, maar waarskynlik moet nie wees nie, die redelik eenvoudige gekoppel lys wat ons 'n laaste keer. En 'n geskakelde lys het ten minste een voordeel oor 'n skikking. Wat is een voordeel van 'n geskakelde lys waarskynlik? 

Publiek: inplanting. 

David Malan: inplanting. Wat bedoel jy daarmee? 

Publiek: Enigeplek saam die lys [onhoorbaar]. 

David Malan: Goed. So kan jy 'n element waar voeg wat jy wil in die middel van die lys sonder om iets te skuif, wat ons tot die gevolgtrekking gekom, in ons sortering besprekings, is nie noodwendig 'n goeie ding, want dit neem tyd om werklik te beweeg al daardie mense links en regs. En so met 'n geskakelde lys, kan jy net wys met malloc, 'n nuwe knoop, en dan werk 'n paar pointers-- twee, drie operasies max-- en ons in staat is om iemand te skakel in enige plek in 'n lys. 

Wat anders was voordelig oor 'n geskakelde lys? Ja? 

Publiek: [onhoorbaar] David Malan: Perfect. Volmaak. Dit is regtig dinamiese. En dat jy nie te doen nie, vooraf, na 'n paar vaste grootte stuk van die geheue, soos wat jy wil hê om met 'n verskeidenheid, die onderstebo waarvan is dat jy knope net op kan toeken vraag sodoende met net soveel ruimte as jy eintlik nodig het. In teenstelling met 'n verskeidenheid, kan jy ongeluk ken te min. En dan is dit net gaan 'n pyn in die nek te wees 'n nuwe groter verskeidenheid te wysig, kopieer alles oor, vry om die ou skikking, en beweeg dan oor jou besigheid. Of nog erger, kan jy weg ken meer geheue as wat jy werklik nodig het, en so gaan jy 'n baie het dunbevolkte skikking, om so te praat. 

So 'n geskakelde lys gee jou hierdie voordele van dinamika en buigsaamheid met invoegings en weglatings. Maar seker moet daar 'n prys betaal word. Trouens, een van die temas verken op quiz nul was 'n paar van die trade-offs ons het tot dusver gesien het. So, wat is 'n prys wat betaal is of 'n nadeel van 'n geskakelde lys? Ja. 

Publiek: Geen ewekansige toegang. 

David Malan: Geen ewekansige toegang. Maar wie gee om? Ewetoeganklike klink nie oortuigend. 

Publiek: [onhoorbaar] David Malan: Presies. As jy wil hê 'n sekere algorithm-- en laat my eintlik stel binêre soek in die besonder, wat is een wat ons het nogal 'n bit-- gebruik as jy nie ewekansige toegang het nie, jy kan dit nie doen nie eenvoudige rekenkundige vind soos die Midde-element en spring reg om dit te. Jy plaas moet begin by die eerste element en lineêr soek van links na regs as jy wil om te vind die middel of enige ander element. 

Publiek: Dit neem waarskynlik meer geheue. 

David Malan: meer geheue. Waar is dat bykomende kos kom uit in die geheue? 

Publiek: [onhoorbaar] David Malan: Presies. In hierdie geval hier, ons het 'n geskakelde lys vir heelgetalle, en tog is ons verdubbel die bedrag van die geheue Ons moet deur ook berging van hierdie wenke. Nou minder van 'n groot deal as jou structs kry groter en jy nie 'n aantal stoor, maar miskien 'n student of 'n ander voorwerp. Maar die punt beslis bly. En so 'n aantal van die bedrywighede op geskakelde lyste geroep was groot O van n-- lineêre. Dinge soos voeg of soek of skrap in die geval 'n element gebeur te wees aan die einde van die lys of dit gesorteer is of nie. 

Soms moet jy kan kry gelukkig en in so laer perke op hierdie bedrywighede dalk ook konstant tyd as jy altyd op soek na die eerste element, byvoorbeeld. Maar uiteindelik het ons belowe die heilige graal te bereik data strukture, of sommige aanpassing daarvan, deur middel van 'n konstante tyd. Kan ons elemente of voeg elemente of verwyder elemente van 'n lys? Ons sal baie gou sien. En dit blyk dat 'n mens van die meganismes ons gaan om te begin vandag om te gebruik, jaarlikse gebruik in p stel vyf, is eintlik redelik bekend is. Byvoorbeeld, as dit is 'n klomp van eksamen boeke, wat elk 'n student se eerste naam en die laaste naam op dit, en ek haal hulle uit aan die einde van 'n eksamen, en hulle is almal mooi veel in 'n ewekansige volgorde, en ons wil om te gaan oor die sortering hierdie eksamens so dat sodra gegradeer dit is net 'n baie makliker en vinniger om hulle uit te lewer terug aan studente alfabeties. Wat sou jou instink wees vir 'n stapel van eksamens soos hierdie? 

Wel, as jy soos ek, jy kan sien dat dit 'm, so ek gaan soort van sit dit in, As dit is my tafel of my vloer waar Ek is die verspreiding van dinge out-- of my skikking really-- Ek kan al die me sit daar. O. Hier is 'n A. So mag ek sit die As hier. O. Hier is 'n ander A. Ek gaan wat om te sit oor hier. Hier is 'n Z. Hier is 'n ander M. En so Ek kan begin om hope soos hierdie. En dan miskien ek later gaan en die soort van baie nitpicky-ly soort die individuele planke. Maar die punt is ek wil kyk by die insette wat ek handed en Ek sal maak 'n paar bereken besluit op grond van wat insette. As dit begin met 'n, plaas dit daar. As dit begin met Z, sit dit oor daar, en alles tussenin. 

So, dit is 'n tegniek wat algemeen bekend as hashing-- H-A-S-H-- wat beteken die algemeen neem as insette en die gebruik van daardie insette te bereken 'n waarde, in die algemeen 'n aantal, en dat getal is die indeks in 'n stoor houer, soos 'n skikking. So met ander woorde, kan ek 'n hash funksie, soos ek in my kop, dat as ek sien iemand is naam wat begin met A, Ek is van plan om dit te karteer na nul in my kop. En as ek sien iemand met Z, ek is gaan dit karteer tot 25 in my kop en dan sit dit in die laaste mees paal. 

Nou, as jy dink oor my brein maar 'n C program, wat getalle kan jy staatmaak op dieselfde resultaat te bereik? Met ander woorde, as jy het die ASCII karakter A, Hoe bepaal jy wat die emmer om dit te sit in? Jy het waarskynlik nie wil sit dit in die emmer 65, wat sou wees soos daar vir geen goeie rede. Waar wil jy 'n plaas in terme van sy ASCII waarde? Waar wil jy na die ASCII te doen waarde met 'n slimmer emmer te kom om dit te sit in? 

Publiek: Min A. 

David Malan: Ja. So minus A of minus spesifiek 65 as dit 'n kapitale A. Of 98 indien dit is 'n klein a. En sodat ons in staat sou stel om baie eenvoudig en baie aritmetisch, sit iets in 'n emmer soos dit. So dit blyk ons ​​eintlik doen hierdie sowel selfs met die vasvrae. 

Sodat jy kan onthou wat jy omkring jou onderrig man se naam op die voorblad. En die TF se name is georganiseer in hierdie kolomme alfabeties, Wel, glo dit of nie, wanneer al 80 plus ons het ook die ander aand tot graad, Die laaste stap in ons gradering is die vasvrae om hash in 'n groot ruimte van die vloer by die [onhoorbaar] en almal se vasvrae om uit te lê presies die einde van hul TF se name op die voorblad, want dan is dit 'n baie vir ons makliker om te soek deur die gebruik van lineêre soek of 'n soort van slim vir 'n TF te vind om sy of haar studente se vasvrae. 

So hierdie idee van hashing dat jy sal sien is nogal sterk is eintlik redelik alledaags en baie intuïtief, baie soos miskien verdeel en oorwin was in week nul. Ek vas uit na die hackathon 'n paar jaar gelede. Dit was Zamyla en 'n paar ander personeel groet studente toe hulle in. En ons het 'n hele klomp van die vou tafels met naambordjies. En ons het die naam tags georganiseer met soos die As daar en die Zs daar. En so een van die TFS baie slim geskryf het as die instruksies vir die dag. En in week 12 van die semester hierdie al perfekte sin en almal het geweet wat om te doen. Maar elke keer as jy het tougestaan ​​in die dieselfde manier, jy die implementering van die Dieselfde idee van 'n gemors. So laat formaliseer dit 'n bietjie. Hier is 'n skikking. Dit is gevestig op 'n klein om te wees wye net te beeld, visueel, dat ons snare kan sit in iets soos hierdie. En hierdie skikking is duidelik van die totale grootte 26. En die ding genoem tafel arbitrêr. Maar dit is net 'n kunstenaar se vertoning van wat 'n gemors tafel kan wees. 

So 'n gemors tafel nou gaan 'n hoër vlak data struktuur. Aan die einde van die dag ons is oor om te sien dat jy kan 'n gemors tafel, implementeer wat is baie soos die check-in lyn 'n hackathon baie soos hierdie tabel gebruik vir sortering eksamen boeke. Maar 'n hash tafel soort van hierdie hoë vlak konsep wat 'n skikking te gebruik onder die kap om dit te implementeer, of dit kan 'n lengte lys te gebruik, of selfs miskien 'n paar ander data strukture. En nou is dit die theme-- neem sommige van hierdie fundamentele bestanddele soos 'n skikking en die gebou blok nou van 'n lengte lys en sien wat anders kan ons bou op die top van die, soos bestanddele in 'n resep, wat meer en meer interessante en nuttige finale uitslae. 

So met die hash tafel ons kan dit implementeer in die geheue picturaal soos hierdie, maar hoe kan dit eintlik gekodeer word? Wel, miskien so eenvoudig is dit. As kapasiteit in hoofletters, is net sommige constant-- byvoorbeeld 26, 26 letters van die alphabet-- Ek kan my veranderlike tafel noem, en ek kan sê dat ek gaan sit kar sterre daar, of string. So dit is so eenvoudig soos dit as jy wil 'n hash tafel te implementeer. En tog, dit is regtig net 'n skikking. Maar weereens, 'n gemors tafel is nou wat ons sal roep 'n abstrakte data tipe wat net soort van 'n konseptuele lae bo-op van iets meer aards nou graag 'n skikking. 

Nou, hoe gaan ons oor die oplossing van probleme? Wel, vroeër het ek die luukse om genoeg tafel ruimte hier sodat ek kan sit die vasvrae waar ek wou. So kan hier gaan. ZS kan hier gaan. Me kan hier gaan. En dan het ek het 'n paar ekstra ruimte. Maar dit is 'n bietjie van 'n bedrieër reg nou, want hierdie tabel, as ek regtig gedink dat dit as 'n skikking, is net gaan wees van 'n paar vaste grootte. 

So tegnies, as ek trek 'n ander student se quiz en sien, o, die persoon se naam begin met 'n A te, Ek het soort van wil dit daar te vestig. Maar so gou as ek dit daar, as hierdie tabel inderdaad verteenwoordig 'n skikking, Ek gaan word oorheersende of beuken Wie ook al hierdie student se toets is. Reg? As dit is 'n skikking, net een ding kan gaan in elk van hierdie selle of elemente. En so het ek soort van 'n te kies en te keur. 

Nou vroeër ek soort verneuk en het dit of ek net soort van gestapel hulle bo mekaar. Maar dit is nie gaan om te vlieg in die kode. So waar kan ek die tweede student wie se naam is 'n as al wat ek gehad het, is hierdie beskikbaar tafel ruimte? En ek het drie posisies en dit gebruik lyk asof daar is net 'n paar ander. Wat kan jy doen? Publiek: [onhoorbaar] David Malan: Ja. Miskien laat ons net hou dit eenvoudig. Reg? Dit pas nie waar ek wil om dit te sit. So ek gaan om dit te sit tegnies waar 'n B gaan. Nou, natuurlik, ek begin myself te verf in 'n hoek. As ek aan 'n student wie se naam is eintlik B, nou B gaan 'n bietjie te verskuif vorentoe, soos kan gebeur, yep, As dit is 'n B, nou is dit hier gaan. 

En so gaan dit baie vinnig kan 'n probleem raak, maar dit is 'n tegniek wat eintlik verwys word as lineêre indringende, waardeur jy net oorweeg om jou skikking te wees langs die lyn. En jy moet net soort van ondersoek of inspekteer elke beskikbare element soek vir 'n beskikbare plek. En so gou as wat jy kry een, het jy dit laat val in daar. 

Nou, die prys wat nou betaal vir hierdie oplossing is wat? Ons het 'n vaste grootte skikking, en toe ek voeg name in dit, ten minste aanvanklik, wat is die loop van die tyd van die inplanting vir die plaas van die studente se vasvrae in die regte emmers? Big O van wat? 

Publiek: n. David Malan: Ek het gehoor die groot O van n. Nie waar nie. Maar ons sal mekaar terg Hoekom in net 'n oomblik. Wat anders kan dit wees? 

Publiek: [onhoorbaar] David Malan: En laat my dit doen visueel. So veronderstel dit is die letter S. 

Publiek: Dit is een. David Malan: Dit is een. Reg? Dit is 'n skikking, wat beteken dat ons ewekansige toegang. En as ons dink van hierdie as nul en dit as 25, en ons besef dat, O ja, hier is my insette S, Ek kan beslis omskep S, 'n ASCII karakter, 'n ooreenstemmende nommer tussen nul en 25 en dan onmiddellik sit dit waar dit hoort. 

Maar natuurlik, so gou as ek by die tweede persoon wie se naam is A of B of C uiteindelik, as ek gebruik die lineêre indringende as my oplossing, die loop van die tyd van inplanting in die ergste geval eintlik gaan oorgaan in wat? En ek het dit hoor hier korrek vroeg op. Publiek: [onhoorbaar] David Malan: So dit is inderdaad n keer jy het 'n groot genoeg data stel. So, aan die een kant, as jou skikking is groot genoeg en jou data is yl genoeg nie, jy kry hierdie pragtige konstante tyd. Maar so gou as jy begin meer en meer elemente, en net statisties jy meer mense met die letter A as hul naam of die letter B, kan dit moontlik oorgaan in iets meer lineêre. So nie heeltemal perfek nie. So kan ons beter doen? 

Wel, wat was ons oplossing voor wanneer ons wil meer dinamika as om iets soos 'n skikking toegelaat? Publiek: [onhoorbaar] David Malan: Wat het ons begin? Ja. So 'n geskakelde lys. Wel, laat ons sien wat 'n gekoppelde lys kan doen vir ons plaas. Wel, laat ek stel voor dat ons teken die prentjie as volg. Nou is dit 'n ander foto van 'n voorbeeld uit 'n ander teks, eintlik, wat is eintlik die gebruik van 'n verskeidenheid van grootte 31. En hierdie skrywer eenvoudig besluit snare te hash nie gebaseer op die persoon se name, maar op grond van hul birthdates. Ongeag van die maand, het hulle gedink As jy gebore op die eerste van 'n maand of die 31ste van 'n maand, die skrywer sal hash gebaseer op die waarde, sodat die name uit 'n bietjie te versprei meer as net 26 plekke kan toelaat. En miskien is dit 'n bietjie meer uniform as om met alfabetiese letters, want natuurlik daar is waarskynlik meer mense in die wêreld met name wat begin met 'n as beslis 'n ander letters van die alfabet. So miskien is dit 'n bietjie meer uniform, in die veronderstelling 'n eenvormige verspreiding van babas oor 'n maand. 

Maar, natuurlik, dit is nog steeds onvolmaak. Reg? Ons is met botsings. Verskeie mense in hierdie data struktuur is nog steeds met dieselfde geboortedatum ten minste jy ongeag maand. Maar wat het die skrywer gedoen het? Wel, dit lyk soos ons het 'n skikking op die linkerkant vertikaal geteken, maar dit is net 'n kunstenaar se vertoning. Dit maak nie saak watter rigting jy trek 'n skikking, dit is nog steeds 'n skikking. Wat is hierdie 'n verskeidenheid van glo? 

Publiek: Gekoppel lys. 

David Malan: Ja. Dit lyk soos dit is 'n verskeidenheid van geskakelde lys. So weer, op hierdie punt van die soort van die gebruik van hierdie data strukture nou as bestanddele meer interessante oplossings, jy kan absoluut 'n fundamentele, soos 'n skikking, en dan is daar iets meer neem interessante soos 'n geskakelde lys en selfs kombineer hulle in 'n selfs meer interessant data struktuur. En inderdaad, dit ook sou word genoem 'n hash tafel, waardeur die skikking is regtig die hash tafel, maar dat die hash tafel het kettings, om so te praat, wat kan groei of krimp gebaseer op die aantal elemente wat jy wil in te voeg. 

Nou, dienooreenkomstig, wat is die loop van die tyd nou? As ek wil iemand te voeg wie se verjaarsdag is 31 Oktober, waar hy of sy gaan? Alle regte. Op die heel onderste waar dit sê 31. En dit is volmaak. Dit was konstant tyd. Maar wat as ons iemand anders kry wie se verjaarsdag is, laat ons sien, Oktober, November, Desember 31? Waar is hy of sy gaan om te gaan? Dieselfde ding. Twee stap al is. Dit is konstante al is dit nie? Alle regte. Op die oomblik is dit. Maar in die algemene geval, hoe meer mense ons by te voeg, probabilistically, ons gaan meer en meer botsings te kry. 

Nou is dit 'n bietjie beter, want tegnies nou my kettings kan wees in die ergste geval hoe lank? As ek voeg n volk in hierdie meer gesofistikeerde data struktuur, N mense, In die ergste geval dit gaan n wees. Hoekom? 

Publiek: Want as almal het dieselfde verjaarsdag hulle gaan 'n reël te wees. David Malan: Perfect. Dit mag dalk 'n bietjie slinks, maar werklik in die ergste geval, As almal het dieselfde verjaarsdag gegewe die insette wat jy het, jy gaan 'n te hê groot skaal lang ketting. En so is, kan jy dit 'n oproep hash tafel, maar eintlik is dit net 'n massiewe gekoppel lys met 'n hele klomp van die gemors ruimte. Maar in die algemeen, as ons aanvaar dat ten minste verjaarsdae is uniform-- en dit is waarskynlik nie. Ek maak dat tot. Maar as ons aanvaar, vir ter wille van die bespreking dat hulle, dan in teorie, indien dit is die vertikale voorstelling van die skikking, goed dan hopelik jy gaan kettings wat, jy weet te kry, min of meer dieselfde lengte waar elkeen van hierdie verteenwoordig 'n dag van die maand. 

Nou as daar 31 dae in die maand, dit beteken dat my loop tyd regtig is 'n groot O van n meer as 31, wat voel beter as lineêre. Maar wat was een van ons verpligtinge 'n paar weke gelede wanneer dit kom by die uitdrukking die loop van die tyd van 'n algoritme? Maar net kyk na die hoë orde termyn. Reg? 31 is beslis nuttig. Maar dit is nog steeds 'n groot O van n. Maar een van die temas van die probleem stel vyf gaan wees om erken dat absoluut, asymptotically, teoreties hierdie data struktuur is nie beter as net een massiewe gekoppel lys. En inderdaad, in die ergste geval, dit hash tafel kan oorgaan in daardie. 

Maar in die werklike wêreld, met ons mense wat eie Mac of PC of wat ook al en loop werklike wêreld sagteware op werklike wêreld data, watter algoritme gaan jy verkies? Die een wat einde stappe of die neem een wat hom N gedeel deur 31 stappe 'n stuk van data te vind of om te kyk 'n paar inligting? Ek bedoel, absoluut die 31 fabrikate 'n verskil in die werklike wêreld. Dit is 31 keer vinniger. En ons mense is beslis gaan dit waardeer. 

So besef die tweespalt daar tussen eintlik praat oor dinge teoreties en asymptotically wat beslis waarde het soos ons gesien het, maar in die werklike wêreld, as jy omgee vir net om die menslike gelukkig vir algemene insette, jy kan baie goed wil aanvaar die feit dat, ja, dit is lineêre, maar dit is 31 keer vinniger as lineêre kan wees. En nog beter, ons het net nie iets arbitrêre doen soos 'n geboortedatum, ons 'n bietjie kan spandeer meer tyd en slim en dink oor wat ons kan doen, gegee 'n persoon se naam en miskien hul geboortedatum diegene te kombineer bestanddele om uit te vind iets dit is werklik meer uniform en minder dronk, om so te praat as hierdie foto tans dui dit mag wees. Hoe kan ons die uitvoering van hierdie in die kode? Wel, laat ek stel voor dat ons net leen sintaksis ons het gebruik om 'n paar keer tot dusver. En ek gaan om te definieer 'n knoop, wat weer is 'n generiese term vir net 'n paar houer vir 'n paar data struktuur. Ek is van plan om dit voor te stel 'n string gaan daar in. Maar ons gaan om te begin neem diegene opleiding wiele af nou. 

Geen meer CS50 biblioteek regtig nie, tensy jy wil hê om dit te gebruik vir die finale projek, wat is goed, maar nou gaan ons terug te trek die gordyn en sê dit is net 'n kar ster. So het die woord daar gaan wees die persoon se naam in die vraag. En nou het ek 'n skakel hier na die volgende knoop sodat hierdie verteenwoordig elk van die knope in die ketting, potensieel, van 'n geskakelde lys. 

En nou hoe kan ek verklaar die hash tafel self? Hoe kan ek hierdie hele struktuur verklaar nie? Wel, regtig, baie soos ek gebruik om 'n wyser om net die eerste element van 'n lys voor, insgelyks kan ek net sê Ek het net 'n klomp van die wysers hierdie hele gemors tafel te implementeer. Ek gaan 'n skikking te hê genoem tafel hash tafel. Dit gaan wees van die grootte kapasiteit. Dit is hoe baie elemente kan inpas in dit. En elkeen van die elemente in hierdie skikking gaan 'n knoop ster. Hoekom? Wel, per hierdie foto, wat ek die implementering van die hash tafel effektief in die begin is net hierdie skikking wat ons vertikaal geteken, elk van wie blokkies verteenwoordig 'n wyser. Dat diegene wat houe deur hulle is net null. En die mense wat pyle gaan aan die regterkant werklike verwysings na werklike knope, ergolitiese die begin van 'n geskakelde lys. 

So hier is, dan, is hoe ons kan implementering van 'n hash tafel wat implemente aparte aaneenskakeling. Nou kan ons beter doen? Alle regte ek die laaste keer belowe dat ons kon konstante tyd bereik. En ek soort het jy konstante tyd hier, maar dan het nie regtig konstante tyd, want dit is nog steeds afhanklik van die totale aantal elemente jy skryf in die data struktuur. Maar veronderstel dat ons dit gedoen het. Laat my terug te gaan na die skerm hier. Laat my ook by hierdie projek hier, duidelik die skerm, en dink ek het dit gedoen. Dink ek wou die naam te voeg Daven in in my data struktuur. 

So ek wil 'n string te voeg Daven in die data struktuur. Wat gebeur as ek nie van 'n hash tafel, maar ek gebruik iets wat nog 'n boom-agtige soos 'n stamboom, waar jy het 'n paar wortel by die bo-op en dan knope en blare wat gaan afwaarts en na buite. Veronderstel dan, dat ek wil Daven se te voeg in wat tans 'n leë lys. Ek gaan die volgende te doen: Ek is gaan 'n knoop in die gesin te skep boom-agtige struktuur data wat lyk 'n bietjie soos hierdie, wat elk reghoeke het, kom ons sê, vir nou 26 elemente in dit. En elkeen van die selle in hierdie reeks gaan die letter van 'n alfabet te verteenwoordig. 

Spesifiek, ek gaan om te behandel Dit is 'n, dan B, dan C, dan D, hierdie een hier. So dit gaan om effektief verteenwoordig die letter D. Maar al Daven se te voeg noem ek 'n bietjie meer te doen. So ek eerste gaan hash, om so te praat. Ek gaan om te kyk na die eerste brief in Daven se wat natuurlik 'n D, en ek gaan toe te ken 'n knoop wat lyk soos this-- 'n groot reghoek groot genoeg om die hele alfabet aan te pas. 

Nou D gedoen word. Nou A. D-A-V-E-N is die doel te bereik. So nou wat ek gaan doen, is om hierdie. Sodra ek begin D kennisgewing daar is geen wyser daar. Dit is vullis waardes op die oomblik, of ek dit kan inisialiseer te null. Maar laat my gaan hou met hierdie idee van die bou van 'n boom. Laat my ken 'n ander een van hierdie nodes wat 26 elemente in dit. 

En weet jy wat? As dit is net 'n knoop in die geheue wat Ek geskep met malloc, met behulp van 'n struct soos ons sal gou sien, Ek gaan this-- te doen Ek gaan 'n pyl te trek uit die ding wat verteenwoordig D af hierdie nuwe knoop. En nou, eers die volgende brief in Daven se naam, V-- D-A-V-- ek gaan om voort te gaan en trek 'n ander knoop soos hierdie, waardeur die V elemente hier, wat ons sal teken vir instance-- Oeps. Ons sal nie daar vestig. Dit gaan hier gaan. 

Toe ons gaan oorweeg om dit te wees V. En dan hier gaan ons na die indeks af van V in wat ons sal oorweeg E. En dan van hier af gaan ons gaan een van hierdie knope hier. En nou het ons 'n vraag te beantwoord. Ek nodig het om een ​​of ander manier aan te dui dat Ons is aan die einde van die string Daven. So ek kon net laat dit nul. 

Maar wat as ons het Daven se volle naam ook, wat is, soos ons gesê het, Dave? So, wat as Daven is eintlik 'n substring, 'n voorvoegsel van 'n veel langer string? Ons kan nie net permanent sê niks gaan om daar te gaan, want ons kon nooit 'n woord soos Davenport voeg in hierdie data struktuur 

So wat ons kan doen is eerder ' hanteer elkeen van hierdie elemente as miskien om twee elemente binne hulle. Een is 'n wyser, inderdaad, as ek doen. So elkeen van hierdie bokse is nie net een sel. Maar wat as die top one-- die onderste een se gaan nul wees nie, want daar is geen Davenport net nog nie. Wat as die boonste een is 'n spesiale waarde? En dit gaan 'n bietjie wees moeilik dit hierdie grootte te trek. Maar dit is seker net 'n tjek merk. Keur. D-A-V-E-N is 'n string in hierdie data struktuur. 

Intussen, as ek meer ruimte hier kan ek doen P-O-R-T, en ek kon tjek in die knoop wat die letter T aan die einde. So dit is 'n groot skaal komplekse-soek data struktuur. En my handskrif beslis nie help nie. Maar as ek wou iets te voeg anders, oorweeg wat ons sou doen. As ons wou Dawid in te stel, ons wil dieselfde logika, D-A-V volg Maar nou sou ek wys in die volgende element nie van E, maar van wat ek tot D. So daar gaan wees meer nodes in hierdie boom. Ons gaan oproep malloc meer hê. Maar ek wil nie 'n te maak volledige gemors van hierdie foto. So laat ons maar kyk na een dit is vooraf geformuleer soos hierdie met nie dot, dot, punte, maar net verkorte skikkings. Maar elkeen van die knope in hierdie boom hier verteenwoordig dieselfde thing-- 'n verskeidenheid Ray grootte 26. 

Of as ons wil wees regtig behoorlike nou, wat as iemand se naam as 'n toespraak, laat aanvaar dat elke knoop het eintlik ' soos 27 indekse in dit, nie net 26. So dit nou gaan 'n data wees struktuur bekend as 'n trie-- T-R-I-E. 'N tydstip waarop, wat vermoedelik histories 'n slim naam vir 'n boom dit is geskik vir herwinning, wat van die kursus, gespel met 'n I-E en dit is dus die tydstip waarop. Maar dit is die geskiedenis van die tydstip waarop. 

So 'n tydstip waarop is hierdie boom-agtige data struktuur soos 'n stamboom wat uiteindelik optree soos dit. En hier is net nog 'n voorbeeld van 'n hele klomp van die ander mense se name. Maar die vraag is nou aan die hand is wat het ons het deur die bekendstelling van waarskynlik 'n meer ingewikkelde data strukture, en een, eerlik, wat gebruik maak van 'n baie van die geheue. 

Want selfs al is, op die oomblik, ek is maar net gebruik van D's wyser en A en V en Es en Ns, Ek mors 'n heck van baie van die geheue. Maar waar ek spandeer 'n hulpbron, Ek is geneig om te doen kry terug die ander. So as ek spandeer meer ruimte, wat is waarskynlik die hoop? Dat ek minder uitgawes wat? Publiek: Minder tyd. David Malan: Time. Nou hoekom sou dit wees? Wel, wat is die inplanting tyd, in terme van die groot O nou, van 'n naam soos Daven of Davenport of Dawid? Wel, Daven was vyf stappe. Davenport sou wees nege stappe, sodat dit sou wees om 'n paar stappe. David sou wees vyf stappe as well. So dit is beton getalle nie, maar sekerlik is daar 'n bogrens op die lengte van iemand se naam. En inderdaad, in die probleem stelle van vyf spesifikasie, ons gaan voor te stel dat dit is iets dit is die 40-paar-vreemd karakters. 

Realisties, niemand het 'n oneindig lang naam, wat is om te sê dat die lengte van 'n Noem of die lengte van 'n string ons kan sekere van die toestand van struktuur is waarskynlik wat? Dit is konstant. Reg? Dit mag dalk 'n groot konstante wees soos 40-iets, maar dit is konstant. En dit het geen afhanklikheid van hoeveel ander name is in hierdie data struktuur. Met ander woorde, as ek wou nou voeg Colton of Gabriel of Rob of Zamyla of Alison of Belinda of enige ander name uit die personeel in die data struktuur, is die loop van die tyd van die plaas van ander name gaan wees op alle beïnvloed deur hoeveel ander elemente is in die data struktuur al? Dit is nie. Reg? Omdat ons effektief met behulp van hierdie multi-laag hash tafel. En die loop van die tyd van enige van hierdie bedrywighede afhanklik is nie op die aantal elemente wat in die data struktuur of wat uiteindelik gaan te wees in die data struktuur, maar op die lengte van wat spesifiek? 

Die string om plaas, wat nie maak hierdie asymptotically konstante time-- groot O van een. En eerlik, net in die werklike wêreld, dit beteken die inbring Daven se naam is soos vyf stappe, of Davenport nege stappe, of David vyf stappe. Dit is pretty darn klein hardloop tye. En, inderdaad, dit is 'n baie goeie ding, veral wanneer dit is nie afhanklik van die totale aantal elemente in daar. So, hoe kan ons die uitvoering van hierdie soort struktuur in die kode? Dit is 'n bietjie meer kompleks, maar nog steeds dit is net 'n toepassing van basiese boustene. Ek gaan herdefinieer ons node soos volg: Bool genoem word-- en dit kon niks genoem word. Maar die Bool verteenwoordig wat ek het as 'n tjek merk. Ja. Dit is die einde van 'n string in hierdie data struktuur. 

En, natuurlik, die knoop ster Daar is verwys na kinders. En, inderdaad, net soos 'n stamboom, jy die knope sal oorweeg wat hang af van die onderkant van 'n ouer element kinders te wees. En so het die kinders gaan wees om 'n verskeidenheid van 27, 27 een net om vir afkappingsteken. Ons gaan om te sorteer spesiale geval dat. So kan jy seker het name met apostrofes. Miskien moet selfs koppelteken gaan daar, maar jy sal sien bl stel 5 ons net sorg oor briewe en apostrofes. 

En dan hoe kan jy verteenwoordig die data struktuur self? Hoe die wortel verteenwoordig jy nie hierdie tydstip waarop, om so te praat? Wel, net soos met 'n geskakelde lys, jy 'n verwysing na die eerste element. Met 'n tydstip waarop jy net een nodig het wyser na die wortel van hierdie tydstip waarop. En van daar kan jy hash jou pad af dieper en dieper elke ander nodus in die struktuur. So eenvoudig Met hierdie kan ons verklaar dat struct. 

Meanwhile-- nou O, vraag. 

Publiek: Wat is Bool woord? 

David Malan: Bool woord net hierdie C inkarnasie van wat ek beskryf in hierdie boks hier, wanneer Ek het begin verdeel elk van die skikking se elemente in twee stukke. Een is 'n verwysing na die volgende knoop. Die ander moet wees iets soos 'n boks om te sê ja, daar is 'n woord Daven wat hier eindig, omdat ons wil nie, op die oomblik, Dave. 

Selfs al is Dave gaan 'te wees wettige woord, hy is nie in die tydstip waarop nog. En D is nie 'n woord nie. En D-A is nie 'n woord of 'n naam. So het die tjek merk dui slegs wanneer jy getref die knoop is die vorige pad van karakters eintlik 'n string wat jy plaas. So dit is al wat die Bool daar is vir ons doen. 

Enige ander vrae oor drieë? Ja. 

Publiek: Wat is die oorvleuel? Wat gebeur as jy 'n Dave en 'n Daven? David Malan: Perfect. Wat gebeur as jy 'n Dave en 'n Daven? So as ons voeg, sê 'n bynaam, vir David-- Dave-- D-A-V-E? Dit is eintlik 'n super eenvoudige. So ons gaan net vier stappe te neem. D-A-V-E. En wat moet ek doen wanneer ek getref dat die vierde knoop? Net gaan om seker te maak. Ons is reeds goed om te gaan. Gedoen. Vier stappe. Konstante asymptotically. En nou het ons aangedui het dat beide Dave en Daven is snare in die struktuur. So nie 'n probleem nie. En sien hoe die teenwoordigheid van Daven dit nie maak nie enige meer tyd of minder neem tyd vir Dave en omgekeerd. 

So wat anders kan ons nou doen? Ons het hierdie metafoor gebruik voor van bak wat iets. Maar dit blyk dat 'n stapel bak is eintlik demonstratiewe van 'n ander abstrakte data type-- 'n hoër vlak data struktuur wat aan die einde van die dag is net soos 'n skikking of 'n geskakelde lys of iets meer aards. Maar dit is 'n meer interessant konseptuele begrip. 'N stapel, soos hierdie bak hier in Mather, is oor die algemeen genoem net that-- 'n stapel. 

En in hierdie tipe van data struktuur jy het twee operations-- jy het 'n beroep druk vir voeg iets aan die stapel, soos om 'n ander skinkbord Terug op die top van die stapel. En dan pop, wat beteken dat jy neem die boonste skinkbord af. Maar wat is die sleutel van 'n stapel is dat dit het hierdie eienaardige kenmerk. As die eetsaal personeel herrangskik die bak vir die volgende maaltyd, wat gaan wees ware oor hoe studente interaksie met die data struktuur? Publiek: Hulle gaan een af ​​te pop. David Malan: Hulle gaan pop een af, hopelik die top. Anders is dit net 'n soort van dom al die pad om te gaan na die bodem. Reg? Die data struktuur nie regtig nie toelaat jy die onderkant skinkbord minstens gryp maklik. So is daar hierdie merkwaardige eiendom aan 'n stapel dat die laaste item in is gaan die eerste een te wees. En rekenaar wetenskaplikes noem hierdie LIFO-- in die laaste, eerste uit. En dit het eintlik interessante programme. Dit is nie noodwendig so duidelik soos 'n paar ander, maar dit kan inderdaad nuttig wees, en dit kan inderdaad geïmplementeer word in 'n paar van die verskillende maniere. 

So een, en eintlik, laat my nie te duik in dit. Kom ons doen dit eerder. Kom ons kyk na een wat amper dieselfde idee, maar dit is 'n bietjie skoner. Reg? As jy een van hierdie fan seuns of meisies wat regtig hou Apple produkte en jy wakker geword 03:00 te reël om op 'n sekere winkel die heel nuutste iPhone te kry, moet jy kan tougestaan ​​het om soos hierdie. 

Nou 'n tou is baie doelbewus naam. Dit is 'n lyn, want daar is sommige regverdigheid om dit te. Reg? Dit sou soort van suig as jy het het daar eers by die Apple Store maar jy is effektief die onderste skinkbord omdat die Apple werknemers dan pop die laaste persoon wat eintlik het in die lyn. So stapels en toue, al funksioneel hulle is soort van die same-- dit is net hierdie versameling van hulpbronne wat gaan om te groei en shrink-- daar hierdie regverdigheid aspek aan dit, ten minste in die werklike wêreld, waar die bedrywighede jy oefen is fundamenteel anders. A stack-- 'n tou rather-- gesê het twee operasies: N tou en d tou. Of jy kan hulle noem enige aantal van die dinge. Maar jy wil net te vang die idee dat 'n mens voeg en een uiteindelik af te trek. 

Nou onder die enjinkap, beide die stapel en 'n tou geïmplementeer kan word hoe? Ons gaan nie in die kode van omdat die hoër vlak idee is soort van meer voor die hand liggend. Ek bedoel, wat doen mens dit? As ek die eerste persoon by die Apple Slaan en dit is die voordeur, jy weet, ek gaan om hier te staan. En die volgende persoon se gaan om hier te staan. En die volgende persoon se gaan om hier te staan. So, wat data struktuur leen hom tot 'n tou? 

Publiek: 'n tou. David Malan: Wel, 'n tou. Seker. Wat anders? 

Publiek: 'n geskakelde lys. 

David Malan: 'n gekoppelde lys wat jy kan implementeer. En 'n geskakelde lys is lekker want dan dit kan arbitrêr groei solank as wat gekant om met 'n paar vaste aantal van die mense in die winkel. Maar miskien 'n vaste aantal plekke wettig is. Want as hulle net soos 20 iPhones op die eerste dag, miskien hulle moet net 'n verskeidenheid van grootte 20 wat ry, te verteenwoordig wat is net nou sê sodra ons begin praat oor hierdie 'n hoër vlak probleme, jy kan dit te implementeer in 'n aantal maniere. En daar is waarskynlik net gaan 'n kompromis in ruimte en tyd of net in jou eie kode kompleksiteit. 

Wat van 'n stapel? Wel, 'n stapel, ons het ook gesien kon net die bak. En jy kan implementeer 'n skikking. Maar op 'n punt as jy 'n skikking, wat gaan gebeur met die bak jy probeer om neer te sit? Alle regte. Jy net gaan in staat wees om so 'n hoë om te gaan. En ek dink in Mather hulle eintlik ingeboude in die opening. So ja, dit is byna soos Mather gebruik 'n verskeidenheid van vaste grootte, want jy kan slegs pas so baie bak in die opening in die muur af onder mense se knieë. En so wat kan wees gesê 'n skikking te wees, maar ons kan beslis implementeer wat meer in die algemeen met 'n geskakelde lys. 

Wel, wat oor 'n ander datastruktuur? Laat my toe om 'n ander visuele hier. Iets soos hoe oor hierdie een hier? Hoekom is dit dalk nuttig wees om nie ' iets so fancy soos 'n tydstip waarop, wat Ons het gesien het hierdie baie wye knope, elk van wat is in 'n skikking? Maar wat as ons iets meer eenvoudig, soos 'n ou skool stamboom elk van wie knope hier is net die stoor van 'n aantal. In plaas van 'n naam of 'n afstammeling is net die stoor van 'n aantal soos hierdie. 

Wel, die jargon wat ons gebruik in data strukture is beide drieë en bome, waar 'n tydstip waarop weer, is net een wie se knope is skikkings, is nog steeds wat jy kan gebruik van graad skool wanneer jy 'n gesin tree-- blare en die wortel van die boom en kinders van die ouer, broers en susters daarvan. En ons kan 'n boom te implementeer, byvoorbeeld, so eenvoudig as dit. 'N boom, indien dit as 'n knoop, een van hierdie kringe dat 'n aantal, dit is nie van plan om een wyser nie, maar twee. En so gou as wat jy voeg 'n tweede wyser, jy kan eintlik nou 'n soort twee-dimensionele data strukture in die geheue. Baie soos 'n twee-dimensionele skikking, kan jy het soort van twee-dimensionele gekoppel lyste maar dié wat volg 'n patroon waar daar is geen siklusse. Dit is werklik 'n boom met 'n grootouer pad tot hier en dan sommige ouers en kinders en kleinkinders en agterkleinkinders. en so meer. 

Maar wat is regtig netjies oor hierdie ook, net om jou te terg met 'n bietjie van die kode, Onthou rekursie uit 'n rukkie terug, waardeur jy skryf 'n funksie wat homself. Dit is 'n wonderlike geleentheid iets om te implementeer soos rekursie, want oorweeg nie. 

Dit is 'n boom. En ek het al 'n bietjie anale met hoe Ek het die heelgetalle in die straat. Soveel so dat dit 'n spesiale name-- n binêre soek boom. Nou is ons van binêre gehoor het soek, maar jy kan werk terug van hierdie ding se naam? Wat is die patroon van hoe ek plaas die heelgetalle in hierdie boom? Dit is nie arbitrêr. Daar is 'n patroon. Ja. 

Publiek: kleiner aan die linkerkant. 

David Malan: Ja. Kleiner is aan die linkerkant. Grotes is op die regte. Sodanig dat 'n ware stelling is 'n ouer is groter as sy linker kind, maar minder as sy reg kind. En dit alleen is selfs 'n rekursiewe verbale definisie want jy kan aansoek doen dat Dieselfde logika vir elke node en dit net bottoms uit 'n basis geval as jy wil, wanneer jy getref een van die blare, so te sê, waar 'n verlof het geen kinders verder. 

Nou hoe kan jy die nommer 44? Jy sal begin by die wortel en sê, hm. 55 is nie 44 So wil ek gaan reg of ek wil gaan oorbly? Wel, natuurlik wat jy wil laat gaan. En so het dit is net soos die telefoon boek byvoorbeeld in binêre soek meer in die algemeen. Maar ons is die uitvoering daarvan nou 'n bietjie meer dinamies as 'n skikking kan toelaat. En in die feit, as jy wil om te kyk by die kode, met die eerste oogopslag seker. Dit lyk soos 'n hele klomp van die lyne. Maar dit is pragtig eenvoudig. As jy wil 'n funksie te implementeer genoem soek wie se doel in die lewe is om te soek na 'n waarde soos n, 'n heelgetal, en jy geslaag het in 'n een pointer-- 'n verwysing na die knoop van die wortels, eerder van die boom waaruit jy alles kan toegang anders, sien hoe reguit jy kan die logika implementeer. As boom is nul, Natuurlik is dit nie daar nie. Laat ons net terug vals. Reg? As jy handig dit niks nie, daar is niks. 

Anders, as n minder as boom pyl n-- nou pyl n, onthou ons 'super kortliks die ander dag, en dit beteken dat net die verwysing die wyser en kyk na die veld genaamd n. So dit beteken daar gaan en kyk na die veld genaamd n. So as n, die waarde wat jy gegee het, is minder as die waarde in die bome heelgetal, waar wil jy gaan? Aan die linkerkant. 

So neem kennis van die rekursie. Ek returning-- nie waar nie. Nie vals. Ek is terug, ongeag die antwoord is van 'n oproep vir myself, verby 'n n weer, wat is oorbodig, maar wat is effens anders nou? Hoe moet ek maak om die probleem kleiner? Ek is verby in die tweede argument, nie die wortel van die boom, maar die linker kind in hierdie geval. So ek verby in die linker kind. 

Intussen, as n groter is as die knoop ek is tans op soek na, Ek soek die regterkant. Want as die boom is nie nul is, en indien die element is nie aan die linkerkant en dit is nie aan die regterkant, wat is wonderlik om die saak? Ons het eintlik het die knoop in vraag, en so het ons terug waar. 

Dus het ons net die oppervlak krap nou 'n paar van hierdie data strukture. In probleem wat vyf jy sal verken hierdie nog verder en jy sal gegee word om jou ontwerp keuse van hoe om te gaan daaroor. Wat ek wil eindig op is net 'n 30 sekonde teaser van wat volgende week en buite wag. 

Soos ons begin-- gelukkig jy dalk think-- ons oorgang stadig uit die wêreld van C en laer vlak implementering besonderhede, 'n wêreld waarin ons kan neem verleen dat iemand anders het uiteindelik geïmplementeer hierdie data strukture vir ons, en ons sal begin om die verstaan werklike wêreld beteken van die implementering web-gebaseerde programme en webtuistes meer algemeen en ook die heel sekuriteit implikasies dat ons net begin om die oppervlak van te krap. Hier is wat op ons wag in die dae wat kom. 

[Video speel] 

-He Gekom met 'n boodskap, met 'n protokol al sy eie. Hy het gekom om 'n wêreld van wrede firewalls, routers omgee, en gevare veel erger as die dood. Hy is vinnig. Hy is sterk. Hy is TCP / IP, en hy het jou adres. "Warriors van die Net." [Einde video speel] David Malan: kom volgende week. Ons sal sien jy dan. [Video speel] -en Nou, "Diep gedagtes" deur Daven Farnham. -David Begin altyd lesings met, "Goed." Waarom nie, "Hier is die oplossing hierdie week se probleem stel " of "Ons gee almal van julle 'n A?" [ROOIBORSDUIFIE] [Einde video speel]