Spreker 1: Alle reg, so ons is terug. Welkom by CS50. Dit is die einde van die week sewe. So onthou dat dit die laaste tyd, het ons begin kyk na effens meer gesofistikeerd data strukture. Sedert tot nou toe, al het ons regtig tot ons beskikking was dit 'n skikking. Maar voordat ons wegdoen met die skikking as nie alles wat interessant is, wat dit inderdaad eintlik is, wat is 'n paar van die plus punte van hierdie eenvoudige data struktuur tot dusver? Wat is dit goed? So ver as wat ons gesien het? Wat doen jy het? Niks nie. STUDENT: [onhoorbaar]. Spreker 1: Wat is dit? STUDENT: [onhoorbaar]. Spreker 1: vaste grootte. OK, so is die rede waarom vaste grootte goeie alhoewel? STUDENT: [onhoorbaar]. Spreker 1: OK, so dit is effektief in die sin dat jy 'n kan toeken vaste bedrag van die ruimte, wat hopelik is juis soveel ruimte as wat jy wil. So wat kan absoluut 'n plus wees. Wat is 'n ander up kant van 'n skikking? Ja? STUDENT: [onhoorbaar]. Spreker 1: Al die - jammer? STUDENT: [onhoorbaar]. Spreker 1: Al die bokse in die geheue of langs mekaar. En dit is nuttig - hoekom? Dit is heeltemal waar nie. Maar hoe kan ons uitbuit dat die waarheid? STUDENT: [onhoorbaar]. Spreker 1: Presies, kan ons hou van waar alles is net deur te weet een adres, naamlik die adres van die eerste greep van daardie deel van die geheue. Of in die geval van die string, die adres van die eerste kar in die tou. En van daar af, kan ons die einde van die string. Ons kan die tweede element, die derde element, en so meer. En so het die fancy manier om te beskryf wat kenmerk is dat skikkings gee ons ewekansige toegang. Net deur die gebruik van die vierkante hakies notasie en 'n getal is, kan jy spring om te 'n spesifieke element in die skikking in konstante tyd, 'n groot O van een, om so te spreek. Maar daar is 'n paar nadele. Wat 'n skikking nie baie maklik doen? Wat is dit glad nie goed nie? STUDENT: [onhoorbaar]. Spreker 1: Wat is dit? STUDENT: [onhoorbaar]. Spreker 1: uit te brei in grootte. So het die nadele van die skikking is presies die teenoorgestelde van wat die upsides is. So een van die nadele is dat dit 'n vaste grootte. So jy kan nie regtig groei nie. Jy kan weer toe 'n groter deel van geheue, en dan beweeg die ou elemente in die nuwe skikking. En dan is vry om die ou skikking, vir byvoorbeeld deur die gebruik van malloc of 'n soortgelyke funksie genoem realloc, wat reserveert geheue. Realloc, as 'n eenkant, probeer om jou te gee geheue wat langs die skikking wat jy reeds het. Maar dit kan beweeg dinge om geheel en al. Maar in kort, dit is duur, reg? Want as jy 'n stuk van die geheue van hierdie grootte, maar jy regtig wil een van hierdie grootte, en jy wil om te bewaar die oorspronklike elemente, jy het ongeveer 'n lineêre tyd kopiëring proses wat moet gebeur uit ou skikking te nuwe. En die werklikheid vra die bedryfstelsel stelsel weer en weer en weer vir groot dele van die geheue kan begin kos jou 'n paar keer as well. So dit is beide 'n seën en 'n vloek in verbloem die feit dat hierdie skikkings is van vaste grootte. Maar as ons in plaas daarvan voer iets soos hierdie, wat ons noem 'n gekoppelde lys, kry ons 'n paar upsides en 'n paar nadele ook hier. So 'n gekoppelde lys is bloot 'n data struktuur bestaan ​​uit C structs in hierdie geval, waar 'n struct, onthou, is net 'n houer vir een of meer spesifieke tipes veranderlikes. In hierdie geval, wat doen die data tipes lyk binnekant van die struct wees wat laaste keer dat ons 'n sogenaamde knoop? Elkeen van hierdie reghoeke is 'n knoop. En elk van die kleiner reghoeke binnekant van dit is 'n data tipe. Watter tipes het ons sê hulle was op Maandag? Ja? STUDENT: [onhoorbaar]. Spreker 1: 'n veranderlike en 'n wyser, of meer spesifiek, 'n int, vir n, en 'n wyser aan die onderkant. Beide van hulle gebeur om te wees 32 stukkies, by minste op 'n rekenaar soos hierdie CS50 Apparaat, en so is hulle getrek ewe groot is. So, wat is die gebruik van die wyser al vir glo? Hoekom voeg die pyl nou toe skikkings was so mooi en skoon en eenvoudig? Wat is die wyser doen vir ons in elk van hierdie nodes? STUDENT: [onhoorbaar]. Spreker 1: Presies. Dit is wat jy vertel waar die volgende een is. So het ek soort van gebruik van die analogie van die met behulp van 'n draad te sorteer ryg hierdie nodes saam. En dit is presies wat ons doen met wysers omdat elk van hierdie stukke van die geheue mag of nie mag wees aangrensende, om terug te Terug na binnekant van die geheue, want elke keer as jy noem malloc sê, gee my genoeg grepe vir 'n nuwe node, kan dit hier te wees of dit kan hier te wees. Dit mag dalk hier te wees. Dit mag dalk hier te wees. Jy weet net nie. Maar met behulp van verwysings in die adresse van diegene nodes, jy kan steek hulle saam in 'n manier wat lyk visueel soos 'n lys, selfs al hierdie dinge is al versprei vind jou een of u twee of jou vier GB RAM binnekant van jou eie rekenaar. So het die negatiewe kant, dan, 'n gekoppel lys is wat? Wat is 'n prys wat ons blykbaar betaal? STUDENT: [onhoorbaar]. Spreker 1: Meer ruimte, reg? Ons het, in hierdie geval, verdubbel die bedrag van ruimte, want ons het gegaan van 32 stukkies vir elke knoop, vir elke int, so nou 64 stukkies, want ons het om te hou om 'n wyser as well. Kry jy meer doeltreffendheid as jou struct is groter as hierdie eenvoudige ding. As jy werklik 'n student in van wat is 'n paar van die snare vir naam en huis, miskien 'n ID-nommer, miskien 'n paar ander lande geheel en al. So as jy 'n groot genoeg struct, dan miskien die koste van die wyser is nie so 'n groot deal. Dit is 'n bietjie van 'n hoek geval in daardie ons stoor so 'n eenvoudige primitiewe binnekant van die geskakelde lys. Maar die punt is dieselfde. Jy is beslis spandeer meer geheue, maar jy kry buigsaamheid. Want nou as ek wil 'n element by te voeg aan die begin van hierdie lys, Ek het 'n nuwe node te ken. En ek moet net as werk pyle een of ander manier deur net die beweging 'n paar wenke rond. As ek iets wil plaas in die middel van die lys, ek het nie te stoot almal opsy soos ons gedoen het in weke se verlede met ons vrywilligers wat verteenwoordig 'n skikking. Ek kan net ken 'n nuwe knoop en dan net wys die pyle in verskillende rigtings, omdat dit nie het om te bly in die werklike geheue 'n ware lyn soos ek het getrek dit hier op die skerm. En dan laastens, as jy wil te voeg iets wat aan die einde van die lys is, is dit nog makliker. Dit is 'n soort van arbitrêre notasie, maar 34 se wyser, neem 'n raaiskoot. Wat is die waarde van die wyser die meeste waarskynlik getrek soort van soos 'n ou skool antenna daar? STUDENT: [onhoorbaar]. Spreker 1: Dit is waarskynlik nul. En inderdaad, dit is een skrywer se voorstelling van nul. En dit is nietig omdat jy absoluut nodig het om te weet waar die einde van 'n gekoppelde lys is nie, dat jy hou volgende en volg en na aanleiding van hierdie pyle tot 'n gemors waarde. So null sal beteken dat daar geen meer nodes aan die regterkant van nommer 34, in hierdie geval. So stel ons voor dat ons kan implementeer hierdie knoop in die kode. En ons het gesien hierdie soort van sintaksis voor. Typedef definieer net 'n nuwe soort vir ons, gee ons 'n sinoniem soos string was vir char *. In hierdie geval, dit gaan om te gee ons snelskriknotasie sodat struct node kan plaas net geskryf word as knoop, wat is 'n baie skoner. Dit is 'n baie minder verbose. Binnekant van 'n knoop is blykbaar 'n int genoem n, en dan 'n struct node * wat beteken presies wat ons wou die pyle om te beteken, 'n verwysing na 'n ander knoop van die presies dieselfde data tipe. En ek stel voor dat ons 'n kan implementeer soek funksie soos hierdie, wat op die eerste oogopslag mag lyk 'n bietjie kompleks. Maar laat ons sien dit in konteks. Laat my gaan oor na die toestel hier. Laat my oop 'n lêer genaamd lys nul dot h. En dit bevat slegs die definisie ons het net gesien 'n oomblik gelede vir hierdie data tipe genoem 'n knoop. So het ons sit dit in 'n dot h lêer. En as 'n eenkant, selfs al is dit program wat jy oor om te sien, is nie al wat kompleks is, is dit inderdaad konvensie toe te skryf om 'n program te sit dinge soos data tipes, te trek konstantes soms, binnekant van jou kop-lêer en nie noodwendig in jou C lêer, seker wanneer jou programme kry groter en groter, sodat jy weet waar beide om te kyk vir dokumentasie in sommige gevalle, of vir basiese dinge soos hierdie, die definisie van 'n soort. As ek nou oop lys nul dot c, sien 'n paar dinge. Dit sluit 'n paar kop lêers, die meeste waarvan ons nog nooit gesien. Dit sluit in sy eie kop lêer. En as 'n eenkant, hoekom dit is dubbel aanhalings hier, in teenstelling met die hoek tussen hakies op die lyn wat Ek het daar uitgelig? STUDENT: [onhoorbaar]. Spreker 1: Ja so dit is 'n plaaslike lêer. So as dit is 'n plaaslike lêer van jou eie hier on line 15, byvoorbeeld, wat jy gebruik die dubbele aanhalingstekens plaas van die hoek tussen hakies. Nou is dit 'n soort interessant. Let daarop dat ek 'n globale het verklaar veranderlike in hierdie program op die lyn 18 genoem die eerste, die idee dat dit is gaan na 'n verwysing na die eerste wees knoop in my geskakelde lys, en ek het geïnisialiseer dit aan nul, want ek het nie toegeken enige werklike nodes net nog nie. Sodat hierdie verteenwoordig, picturaal, wat ons het 'n oomblik gelede in die prentjie as dat wyser op die ver links hand kant. So nou dat wyser het nie 'n pyl. Dit is in plaas net null. Maar dit verteenwoordig wat sal wees om die adres van die eerste werklike node in hierdie lys. So ek het dit geïmplementeer is 'n globale want, soos jy sal sien, dit alles program nie in die lewe is te implementeer 'n gekoppel lys vir my. Nou het ek 'n paar prototipes hier. Ek het besluit om funksies soos om te implementeer weglating, invoeging, soek, en traversal - die laaste om net loop oor die lys, druk uit sy elemente. En nou is hier om my roetine. En ons sal nie te veel tyd spandeer op hierdie want dit is soort van, hopelik ou hoed nou. Ek gaan die volgende te doen, terwyl die gebruiker werk. So een, ek gaan om te druk uit die menu. En ek het dit as geformateer skoon as ek kon. As die gebruiker in een, wat beteken hulle wil iets om te verwyder. As die gebruiker in twee, wat beteken hulle iets wil voeg. En so meer. Ek gaan dan gevra dan vir 'n bevel. En dan gaan ek getint te gebruik. So, dit is 'n baie eenvoudige menuing koppeling waar jy hoef net te tik 'n aantal kartering aan een van daardie opdragte. En nou, ek het 'n mooi skoon skakelaar verklaring wat gaan aan te skakel wat die gebruiker getik in En as hulle getik een, ek sal noem verwyder en breek. As hulle getik twee, ek sal noem voeg en breek. En nou is ek agterkom het sit elke van hierdie op dieselfde lyn. Dit is net 'n stilistiese besluit. Tipies ons het gesien iets soos hierdie. Maar ek het net besluit, eerlik, my program lyk meer leesbare omdat dit was net vier gevalle te net noem dit so. Heeltemal wettige gebruik van styl. En ek gaan om dit te doen so lank as wat die gebruiker het nie 'getik nul, wat ek besluit sal beteken dat hulle wil hê om op te hou. So nou sien wat ek gaan om hier te doen. Ek gaan die lys te glo bevry. Maar meer op wat in net 'n oomblik. Laat se eerste uitvoering van hierdie program. So laat my toe om 'n groter terminale venster, dot streep lys 0. Ek gaan om voort te gaan en voeg by tik twee, 'n aantal soos 50, en nou sal jy sien die lys is nou 50. En my teks net scrolled 'n bietjie. So nou op die lys bevat die nommer 50. Kom ons doen 'n insetsel deur die neem van twee. Kom ons tik in die aantal soos een. Lys is nou een, gevolg deur 50. So dit is net 'n tekstuele verteenwoordiging van die lys. En laat ons voeg een meer aantal soos die nommer 42, wat hopelik gaan aan die einde in die middel, as gevolg hierdie program in die besonder allerhande dit elemente soos dit plaas hulle. So daar het ons dit. Super eenvoudige program wat kan absoluut gebruik het om 'n skikking, maar ek gebeur word met behulp van 'n gekoppelde lys net sodat ek kan dinamiese groei en krimp dit. So kom ons neem 'n blik vir die soektog, as ek hardloop opdrag drie, ek wil soek vir, sê, die getal 43. En niks is glo gevind is, want ek het weer geen reaksie. So kom ons doen dit weer. Soek. Kom ons soek vir 50, of liewer soek 42, wat 'n mooi bietjie subtiele betekenis. En ek het die betekenis van die lewe daar. Nommer 42, as jy nie weet nie die verwysing, Google dit. Alle regte. So, wat het hierdie program vir my gedoen? Dit is net my toegelaat om so te voeg ver en soek vir elemente. Kom vinnig vorentoe, dan, te wat funksioneer ons kyk na op Maandag as 'n teaser. So hierdie funksie, ek eis, soek 'n element in die lys deur die eerste een, waarna die gebruiker en dan roep Getint 'n werklike int te kry wat jy wil om te soek vir. Toe dit agterkom. Ek gaan 'n tydelike veranderlike te skep in lyn 188 geroep wyser - PTR - kon noem dit niks. En dit is 'n verwysing na 'n knoop want ek sê knoop * daar. En ek initializing dit gelyk te wees aan eerste sodat ek effektief het my vinger, om so te spreek, op die baie eerste element van die lys. So as my regterhand hier is PTR ek wys op dieselfde ding wat die eerste is wat dui op. So nou terug in die kode, wat gebeur volgende - hierdie is 'n algemene paradigma wanneer iterating meer as 'n struktuur soos 'n gekoppel lys. Ek gaan die volgende te doen, terwyl wyser is nie gelyk aan nul So terwyl my vinger is nie wys op 'n nul waarde, indien wyser pyl n gelykes n. Ons sal die eerste keer kennis dat n is wat die gebruiker getik per GetInts noem hier. En wyser pyl n beteken wat? Wel as ons gaan terug na die prentjie hier, as ek 'n vinger te wys op dat die eerste knoop met nege, pyl beteken in wese gaan na daardie knoop en gryp die waarde op plek n, in hierdie geval, die data veld genaamd n. As 'n eenkant - en ons het dit gesien 'n paar weke gelede, toe iemand gevra - hierdie sintaksis is 'n nuwe, maar dit beteken nie gee ons magte wat ons nie reeds het. Wat was hierdie frase gelykstaande aan die gebruik van dot notasie en ster 'n paar weke gelede, toe ons geskil terug hierdie laag 'n bietjie te vroeg? STUDENT: [onhoorbaar]. Spreker 1: Presies, dit was star, en dan was dit ster dot n, met hakies hier, wat lyk, eerlik, ek dink 'n baie meer kripties te lees. Maar ster wyser, soos altyd, beteken daar gaan. En wanneer jy daar is, wat data gebied wil jy maak? Wel, jy gebruik maak van die dot-notasie om toegang te verkry 'n structs data veld, en ek spesifiek wil n. Eerlik, ek sou argumenteer dit is net moeiliker om te lees. Dit is moeiliker om te onthou waar moenie die hakies te gaan, die ster en al van dat. So het die wêreld aangeneem 'n sintaktiese suiker, om so te praat. Net 'n sexy manier om te sê, Dit is ekwivalent, en miskien meer intuïtief. As wyser is inderdaad 'n wyser, die pyl skryfwyse beteken daar gaan en vind die veld in hierdie geval het n. So as ek dit vind, let op wat ek doen. Ek het net uit te druk, het ek gevind persent i, steek in die waarde vir daardie int. Ek noem slaap vir 'n tweede net om te soort van pouse dinge wat op die skerm te gee die gebruiker 'n tweede te absorbeer wat nou net gebeur. En dan het ek breek. Anders, wat doen ek? Ek werk wyser op gelyke wyser pyl volgende. So net om duidelik te wees, beteken dit gaan daar is, met behulp van my ou-skool notasie. So, dit beteken net om te gaan na wat ook al jy wys op wat in die baie eerste geval is ek wys op die struct met nege in dit. So het ek daar weg is. En dan is die dot-notasie beteken, kry die waarde op die volgende. Maar die waarde, selfs al is dit getrek as 'n smal, is net 'n nommer. Dit is 'n numeriese adres. So hierdie een lyn van kode, of geskryf soos hierdie, die meer kriptiese manier, of soos hierdie, die effens meer intuïtiewe manier, beteken net beweeg my hand vanaf die eerste knoop na die volgende een, en dan die volgende een, en dan die volgende een, en so meer. So ons sal nie die bewoners van die ander implementering van voeg en te verwyder en traversal, die eerste twee van wat redelik betrokke is. En ek dink dit is baie maklik om te kry verloor wanneer dit mondelings. Maar wat kan ons hier doen, is om probeer om te bepaal hoe dit die beste om visueel te doen. Want ek wil voorstel dat as ons wil elemente in te voeg in hierdie bestaande lys, wat het vyf elemente - 9, 17, 22, 26, en 33 - As ek gaan om dit te implementeer in kode, ek nodig het om te oorweeg hoe om te gaan oor om dit te doen. En ek stel voor die neem van baba stappe waarvolgens, in hierdie geval ek bedoel, wat die moontlike scenario's wat ons mag teëkom in die algemeen? Wanneer die implementering insetsel vir 'n gekoppelde lys, dit gebeur net te wees om 'n spesifieke voorbeeld van grootte vyf. Wel, as jy 'n telefoonnommer in te voeg, wil sê die nommer een, en die handhawing van orde gesorteer, waar natuurlik het die nommer een nodig het om te gaan in hierdie spesifieke voorbeeld? Soos aan die begin. Maar wat interessant is, is daar daardie As jy wil om een ​​te voeg in hierdie lys, wat spesiale wyser moet word blykbaar opgedateer? Eerste. So ek sou argumenteer, is dit die eerste geval dat ons dalk wil om te oorweeg, 'n scenario wat voeg by die begin van die lys. Kom ons aftrek miskien 'n so maklik of selfs makliker geval, relatief gesproke. Dink ek wil die te voeg nommer 35 in gesorteer orde. Dit behoort duidelik daar. So, wat wyser natuurlik gaan bygewerk moet word in daardie scenario? 34 se wyser raak nie null Maar die adres van die struct met die nommer 35. So dit is die geval twee. So al, ek is soort van quantizing hoeveel werk ek het om hier te doen. En laastens, die voor die hand liggende middel geval is Inderdaad, in die middel, as ek wil voeg iets soos sê 23, wat gaan tussen die 23 en die 26, maar nou dinge 'n bietjie meer betrokke is, omdat wat verwysings moet verander word? So 22 moet natuurlik om te verander want hy kan nie verwys na 26 nie. Hy moet verwys na die nuwe knoop wat Ek sal moet ken deur te bel malloc of 'n ekwivalent. Maar dan moet ek ook dat die nuwe knoop, 23 In hierdie geval, het sy wyser wys na wie? 26. En daar gaan wees om 'n orde van bedrywighede hier. Want as ek dit doen dwaasheid, en ek byvoorbeeld begin by die begin van die die lys, en my doel is om 23 te voeg. En ek gaan nie, beteken dit behoort hier, naby nege? No Maak dit hoort hier, langs 17? No Doen dit hier hoort langs 22? Ja. Nou as ek dwase hier, en nie dink dit deur, kan ek wys my nuwe node vir 23. Ek kan werk om die verwysing van die knoop genoem 22, wys dit by die nuwe knoop. En dan wat moet ek te werk die nuwe node se wyser te wees? STUDENT: [onhoorbaar]. Spreker 1: Presies. Wys op 26. Maar dammit as ek nie reeds werk 22 se muis te wys op hierdie man, en nou het ek weeskinders, die res van die lys, om so te spreek. So orde van bedrywighede hier gaan belangrik wees. Om dit te doen, kan ek nie steel nie, sê, ses vrywilligers. En laat ons kyk of ons kan dit nie doen nie visueel in plaas van die kode-wyse. En ons het 'n paar pragtige stres balle vir jou vandag. OK, hoe oor een, twee, in die terug - op die ou end. drie, vier, albei van julle ouens op die einde. En vyf, ses. Seker nie. Vyf en ses. Alle reg, en ons sal kom om julle volgende keer. Alle reg, kom op. Alle reg, aangesien jy eers hier, wil jy die een wees wat ongemaklik in Google Glass hier? Alle reg, so, OK, Glass, 'n video opneem. OK, jy is goed om te gaan. Alle reg, so as jy ouens kan kom oor Hier het ek berei in advance 'n paar nommers. Alle reg, kom hier. En hoekom gaan jy nie 'n bietjie verder dat die pad. En laat ons sien, wat is jou naam, met die Google Glass? STUDENT: Ben. Spreker 1: Ben? OK, Ben, sal jy eerste wees, letterlik. So ons gaan jou te stuur aan die einde van die verhoog. Alle reg, en jou naam? STUDENT: Jason. Spreker 1: Jason, OK jy sal wees nommer nege. So as jy wil Ben dat die pad om te volg. STUDENT: Jill. Spreker 1: Jill, jy gaan te wees 17, wat as ek dit gedoen het meer intelligent, sou ek begin aan die ander kant. Jy gaan op die manier. 22. En jy is nie? STUDENT: Mary. Spreker 1: Mary, sal jy 22. En jou naam? STUDENT: Chris. Spreker 1: Chris, sal jy 26. En dan laastens. STUDENT: Diana. Spreker 1: Diana, sal jy 34. So jy kom op hier. Alle reg, so perfek gesorteer gelas reeds. En laat ons gaan voort en doen dit sodat ons kan regtig - Ben jy is net soort van kyk uit na nêrens. OK, so laat ons gaan voort en stel dit die gebruik van arms, baie soos ek was, presies, wat gaan aan. So gaan voort en gee julle 'n voet of twee met mekaar het. En voort te gaan en wys met die een hand te wie jy moet wys word by gebaseer op hierdie. En as jy null net wys reguit af na die vloer. OK, so goed. So nou het ons 'n gekoppelde lys, en laat my stel dat ek die rol van speel PTR, so ek sal nie die moeite uitvoering van hierdie rond. En dan - iemand dom konvensie - jy kan noem dit wat jy wil - voorganger wyser, pred wyser - dit is net die bynaam wat ons in ons voorbeeld kode aan my linkerhand. Die ander kant wat gaan word om spoor van wie is wie in die volgende scenario's. So dink, in die eerste, ek wil om uit te ruk af dat die eerste voorbeeld van die inbring, sê 20, in die lys. So ek gaan iemand nodig verpersoonlik die nommer 20 vir ons. So ek moet malloc iemand van die gehoor. Kom up. Wat is jou naam? STUDENT: Brian. Spreker 1: Brian, alles reg, sodat jy sal die knoop met 20 wees. Alle reg, kom hier. En natuurlik, waar beteken Brian behoort? So, in die middel van - eintlik, wag 'n minuut. Ons doen dit buite orde. Ons is die maak van hierdie 'n baie moeiliker as wat dit moet wees by die eerste. OK, gaan ons gratis Brian en realloc Brian as vyf. OK, so nou wil ons in te voeg Brian as vyf. So kom hier langs Ben vir net 'n oomblik. En jy kan vermoedelik vertel waar hierdie storie gaan. Maar laat ons dink mooi oor die einde van bedrywighede. En dit is juis hierdie visuele wat gaan om te reël om met die voorbeeld kode. So hier het ek PTR wys aanvanklik nie by Ben, per se nie, maar op watter waarde wat hy bevat, wat in hierdie geval is - wat is jou naam nou weer? STUDENT: Jason. Spreker 1: Jason, sodat beide Ben en ek is wys op Jason op hierdie oomblik. So nou het ek om te bepaal, waar kom Brian behoort? Dus is die enigste ding wat ek het toegang tot nou is sy n data item. So ek gaan om seker te maak, is Brian minder as Jason? Die antwoord is waar. So, wat moet nou gebeur, in die korrekte volgorde? Ek het hoeveel verwysings na werk in totaal in hierdie storie? Waar my hand is nog steeds wys na Jason, en jou hand - as jy wil sit jou hand soos, soort van, ek weet nie, 'n vraagteken. OK, goed. Alle reg, sodat jy 'n paar kandidate. Óf Ben of ek of Brian of Jason of enigiemand anders, wat wysers te verander? Hoeveel in totaal? OK, so twee. My wyser nie regtig meer saak nie want ek is net tydelik. So dit is hierdie twee ouens, vermoedelik, beide Ben en Brian. So laat ek stel voor dat ons werk Ben, want hy is die eerste. Die eerste element van hierdie lys nou gaan wees Brian. So Ben punt Brian. OK, wat nou? Wie word gewys na wie? STUDENT: [onhoorbaar]. Spreker 1: OK so Brian het te wys op Jason. Maar ek het tred verloor wat wyser? Weet ek waar Jason is? STUDENT: [onhoorbaar]. Spreker 1: Dit doen nie, want ek is die tydelike wyser. En vermoedelik, het ek nie verander nie te wys op die nuwe knoop. Sodat ons kan eenvoudig Brian punt by wie ek wys op. En ons klaar is. So geval een, voeg by die die begin van die lys. Daar was twee belangrike stappe. Een, ons het Ben by te werk, en dan ons het ook Brian te werk. En dan het ek hoef nie te pla traipsing deur die res van die lys, want ons het reeds bevind sy plek, want hy behoort aan die links van die eerste element. Alle reg, so mooi eenvoudig. In werklikheid, voel soos ons is amper die maak van hierdie te ingewikkeld. So laat ons nou aftrek die einde van die lys, en sien die kompleksiteit begin. So as ek nou alloc van die gehoor. Iemand wil hê om 55 te speel? Alle reg, sien ek jou hand eerste. Kom up. Ja. Wat is jou naam? STUDENT: [onhoorbaar]. Spreker 1: Habata. OK, kom op. Jy sal die nommer 55 wees. So jy, natuurlik, behoort aan die einde van die lys. So laat speel die simulasie met my synde die PTR vir net 'n oomblik. So ek gaan eers te wys op wat Ben is wys. Ons is albei wys nou by Brian. So 55 is nie minder nie as vyf. So ek gaan myself te werk deur wys na Brian se volgende wyser, wat nou is natuurlik Jason. 55 is nie minder nie as nege, so Ek gaan PTR te werk. Ek gaan PTR te werk. Ek gaan PTR te werk Ek gaan PTR te werk. En ek gaan - hmm, wat is jou naam nou weer? STUDENT: Diana. Spreker 1: Diana is wys, natuurlik, by null met haar linkerhand. So, waar Habata eintlik behoort duidelik? Aan die linkerkant, hier. So, hoe weet ek haar hier te plaas Ek dink ek het screwed up. Want wat is PTR kuns hierdie oomblik in tyd? Null. Dus, selfs al is, visueel, kan ons duidelik sien al hierdie ouens hier op die verhoog. Ek het nie tred gehou het met die vorige persoon in die lys. Ek het nie 'n vinger te wys, in hierdie geval, die knoop nommer 34. So laat ons begin eintlik dit oor. So nou is ek regtig nodig 'n tweede plaaslike veranderlike. En dit is wat jy sien in die werklike monster C-kode, waar as Ek gaan, toe ek my hand na die punt Jason, en daardeur verlaat Brian agter, ek beter begin met my linkerhand te werk waar ek was, so dat as ek gaan deur middel van hierdie lys - meer ongemaklik as wat ek bedoel nou hier visueel - Ek gaan om te kry om die einde van die lys. Hierdie hand is nog nul, wat is mooi nutteloos, anders as om aan te dui Ek is duidelik aan die einde van die lys, maar nou ten minste ek het dit voorganger wyser wys hier, so nou wat hande en wat wysers bygewerk moet word? Wie se hand wil jy om weer instel eerste? STUDENT: [onhoorbaar]. Spreker 1: OK, so Diana se. Waar wil jy om te wys Diana se linker muis op? Op 55, vermoedelik, sodat Ons het daar plaas. En waar moet 55 wyser gaan? Down, wat null. En my hande, op hierdie punt, doen nie saak nie, want hulle was net tydelike veranderlikes. So nou is ons klaar is. So die bykomende kompleksiteit daar - en dit is nie so moeilik om te implementeer, maar ons moet 'n sekondêre veranderlike te maak seker dat voordat ek skuif my reg hand, ek werk om die waarde van my linkerhand hand, pred wyser in hierdie geval, so dat ek 'n sleep wyser rekord te hou van waar ek was. Nou as 'n eenkant, as jy dink hierdie deur, dit voel soos dit is 'n klein irriterende te hê om te hou spoor van die linkerhand. Wat sou 'n ander oplossing om hierdie probleem gewees het? As jy die data te herontwerp struktuur wat ons praat deur nou? As dit net 'n soort van voel 'n bietjie irriterende te hê, soos, twee wysers gaan deur die lys, kan wie anders het, in 'n ideale wêreld, in stand gehou inligting wat ons nodig het? Ja? STUDENT: [onhoorbaar]. Spreker 1: Presies. Reg so daar is eintlik 'n interessante kiem van 'n idee. En die idee van 'n vorige wyser, wys op die vorige element. Wat as ek net vergestalt wat binnekant van die lys self? En dit gaan moeilik wees om te visualiseer dit sonder om al die papier val op die vloer. Maar veronderstel dat hierdie ouens gebruik om beide van hul hande 'n vorige te hê wyser, en 'n volgende wyser, en daardeur die uitvoering van wat ons noem 'n dubbel gekoppel lys. Dit sou toelaat om my te sorteer van rewind, veel makliker sonder my, die programmeerder, om te hou spoor die hand - waarlik hand - van waar ek voorheen in die lys. So sal ons dit nie doen nie. Ons sal dit eenvoudig te hou, want dit is gaan om te kom teen 'n prys, twee keer so veel ruimte vir die wysers, As jy wil 'n tweede een. Maar dit is inderdaad 'n gemeenskaplike data struktuur bekend as 'n dubbel gekoppel lys. Kom ons doen die laaste voorbeeld hier en hierdie ouens uit hulle ellende. So malloc 20. Kom op uit die paadjie is daar. Alle reg, wat is jou naam? STUDENT: [onhoorbaar]. Spreker 1: Sorry? STUDENT: [onhoorbaar]. Spreker 1: Demeron? OK kom up. Jy sal wees 20. Jy het natuurlik gaan behoort tussen 17 en 22. So laat my leer my les. Ek gaan wyser te begin wys na Brian. En ek gaan my linkerhand te hê net werk na Brian as ek skuif na Jason, kontrolering doen 20 minder as nege? No Is 20 minder as 17? No Is 20 minder as 22? Ja. So, wat verwysings of hande nodig om te verander waar hulle nou wys? So ons kan doen 17 wys op 20. So dit is goed. Waar wil ons te wys jou wyser nou? Op 22. En ons weet waar 22 is, weer dankie tot my tydelike wyser. So ons is OK daar. So as gevolg van hierdie tydelike berging Ek het tred gehou waar almal is. En nou kan jy visueel gaan in waar jy behoort, en nou moet ons 1, 2, 3, 4, 5, 6, 7, 8, 9 stress balle, en 'n rondte van applous vir hierdie ouens, as ons kon. Mooi gedoen. [Applous] Spreker 1: Alle reg. En jy mag die stukke papier as aandenkings. Alle reg, so, glo my dit is 'n baie makliker om te loop deur wat met die mens as wat dit is met die werklike kode. Maar wat jy sal vind in net 'n oomblik nou, is dat dieselfde - O, dankie. Dankie - is dat jy dat dieselfde data sal vind struktuur, 'n gekoppelde lys, kan eintlik gebruik word as 'n boublok om selfs meer gesofistikeerde data strukture. En besef ook die tema hier is dat Ons het absoluut ingestel meer kompleksiteit in die implementering van hierdie algoritme. Inplanting, en as ons deur dit gegaan, skrap en soek, is 'n bietjie meer ingewikkeld as wat dit was met 'n skikking. Maar ons kry 'n bietjie dinamika. Ons kry 'n aangepaste data struktuur. Maar weereens, ons betaal 'n prys van 'n paar bykomende kompleksiteit, beide in die uitvoering daarvan. En ons opgegee ewekansige toegang. En om eerlik te wees, is daar nie 'n paar mooi skoon te skuif ek kan gee wat sê hier is die rede waarom 'n gekoppelde lys is beter as 'n skikking. En laat dit op daardie. Omdat die tema herhaling nou, selfs meer so in die komende weke, is dat daar nie noodwendig 'n korrekte antwoord. Dit is hoekom ons die afsonderlike as van die ontwerp vir die probleem stelle. Dit sal baie konteks sensitiewe of jy wil hierdie inligting te gebruik struktuur of dat 'n mens, en dit sal afhang van wat vir jou saak maak in terme van hulpbronne en kompleksiteit. Maar laat ek stel voor dat die ideale data struktuur, die heilige graal, sou wees iets wat konstant tyd, ongeag van hoeveel dinge is binne-in, dit sal nie verbasend as 'n data struktuur teruggekeer antwoorde in konstante tyd. Ja. Hierdie woord is in jou groot woordeboek. Of nee, hierdie woord is nie. Of enige so 'n probleem daar. Wel, laat ons kyk of ons nie ten minste neem 'n stap in die rigting wat. Laat my stel 'n nuwe data struktuur wat kan gebruik word vir verskillende dinge, In hierdie geval het 'n hash tafel. En so is ons eintlik terug na skrams by 'n skikking, in hierdie geval, en ietwat arbitrêr, het ek opgestel om hierdie hash tafel as 'n skikking met die soort van 'n twee-dimensionele skikking - of eerder dit hier uitgebeeld as 'n twee dimensionele skikking - maar dit is net 'n skikking van grootte 26, soos dat as ons noem die skikking, tafel bracket zero is die reghoek aan die bokant. Table bracket 25 is die reghoek aan die onderkant. En dit is hoe ek 'n data kan trek struktuur in wat ek wil om te stoor mense se name. So byvoorbeeld, en ek sal nie trek die hele ding hier op die oorhoofse, as ek het hierdie skikking, wat ek nou gaan roep 'n hash tafel, en dit is weer plek nul. Dit is hier plek een, en so meer. Ek eis dat ek wil hê om hierdie inligting te gebruik struktuur, ter wille van die bespreking, mense se name op te slaan, Alice en Bob en Charlie en ander sulke name. So dink van hierdie nou as die begin van, sê, 'n woordeboek met baie van die woorde. Dit gebeur om te wees name In ons voorbeeld hier. En dit is al te related, miskien, te implementering van 'n speltoetser, soos ons dalk vir die probleem wat ses. So as ons het 'n verskeidenheid van die totale grootte 26 sodat dit is die 25ste plek aan die onderkant, en ek beweer dat Alice is die eerste woord in die woordeboek van name wat ek wil in te voeg in geheue, in hierdie data struktuur, waar is instink vertel dat Alice se naam moet gaan in hierdie reeks? Ons het 26 opsies. Waar ons wil om haar te sit? Ons wil haar in hakies nul, reg? A vir Alice, kom ons noem dat die nul. En B sal een wees, en C sal twee. So ons gaan om te skryf Alice se naam hier. As ons dan voeg Bob, sy naam kom hier. Charlie sal hier gaan. En so meer af deur hierdie data struktuur. Dit is 'n wonderlike data struktuur. Hoekom? Wel, wat is die loop van die tyd van voeg 'n mens se naam in hierdie data struktuur nou? Gegee dat hierdie tabel geïmplementeer word, waarlik, as 'n skikking. Wel dit is konstante tyd. Dit is om van die een. Hoekom? Wel, hoe bepaal jy waar Alice behoort? Jy kyk na watter letter van haar naam? Die eerste. En jy kan daar kom, al is dit 'n string, deur net te kyk na string bracket nul. So het die nulde karakter van die string. Dit is maklik. Ons het dit in die crypto opdrag weke gelede. En dan wanneer jy weet dat Alice se letter A is kapitaal, kan ons trek af 65 of kapitaal 'n self, wat gee ons 'n nul. So ons weet nou dat Alice behoort by plek nul. En die lig van 'n verwysing na hierdie data struktuur, van 'n soort, hoe lank dit neem my plek te vind nul in 'n skikking? Net 'n stap, reg Dit is konstante as gevolg van die ewekansige toegang ons voorgestelde was 'n kenmerk van 'n skikking. Dus, in kort, uitzoeken wat die indeks van Alice se naam is, wat is, in hierdie geval, is A, of laat ons net los wat aan nul is, waar B is een en C is twee, besyfering dat uit konstant tyd. Ek het net om te kyk na haar eerste brief, uitzoeken waar nul is 'n skikking is ook konstante tyd. So tegnies dit is soos twee stappe nou. Maar dit is nog steeds konstant. So ons noem dat die groot O van een, so ons het ingevoeg Alice in hierdie tabel in konstante tyd. Maar natuurlik, ek word naïef hier, reg? Wat as daar 'n Aaron in die klas? Of Alicia? Of enige ander name wat begin met A. Waar gaan ons te sit daardie persoon, reg? Ek meen, nou is daar net drie mense op die tafel, so miskien kan ons moet sit Aaron op plek nul een twee drie. Reg, kan ek 'n hier. Maar dan, as ons probeer om Dawid te voeg in hierdie lys, nie waar Dawid gaan? Nou ons stelsel begin breek af, reg? Want nou David eindig hier As Aaron is eintlik hier. En so nou hierdie hele idee van 'n skoon data struktuur wat gee ons konstante tyd invoegings is nie meer konstante tyd, want ek het om te kyk, o, o bliksem, iemand is reeds op Alice se plek. Laat my ondersoek die res van hierdie data struktuur, op soek na 'n plek om te sit iemand soos Aaron se naam. En so het dit ook begin lineêre tyd te neem. Verder, as jy wil nou die te vind Aaron in hierdie data struktuur, en jy gaan, en Aaron se naam is nie hier nie. Ideaal, jy wil net sê Aaron se nie in die data struktuur. Maar as jy begin om ruimte vir Aaron waar daar moes gewees het 'n D of 'n E, julle, die ergste geval, het om seker te maak die hele data struktuur, in welke geval dit wentel in iets lineêre in die grootte van die tabel. So alles reg is, sal ek dit regmaak. Die probleem hier is dat ek moes 26 elemente in die skikking. Laat my dit verander. Oeps. Laat my dit verander sodat eerder welsyn van grootte 26 in totaal, kennis van die onderkant indeks gaan verander na n minus 1. As 26 is duidelik te klein is vir die mens se name, want daar is duisende name van die wêreld, laat ons net maak in 100 of 1000 of 10000. Laat ons net ken 'n baie meer ruimte. Wel, dit beteken nie noodwendig afneem die waarskynlikheid dat ons nie sal twee mense met name wat begin met A, en ja, jy gaan probeer om 'n te sit name op plek nul steeds. Hulle is nog steeds gaan om te bots, wat beteken dat ons nog nodig het om 'n oplossing te sit Alice en Aaron en Alicia en ander name wat begin met 'n elders. Maar hoe veel van 'n probleem is dit? Wat is die waarskynlikheid dat jy het botsings in 'n data struktuur soos hierdie? Wel, laat my - ons sal terugkom op die vraag hier. En kyk hoe ons kan los dit die eerste keer. Laat my toe om hierdie voorstel hier. Wat ons nou net beskryf is 'n algoritme, 'n heuristiese genoem lineêre indringende waardeur, as jy probeer om te voeg iets wat hier in hierdie data struktuur, wat genoem word 'n hash tafel, en daar is geen plek oor nie, jy waarlik ondersoek die data struktuur nagaan, is dit beskikbaar? Is dit beskikbaar is, is dit beskikbaar? Is dit beskikbaar? En toe dit uiteindelik, jy plaas die naam wat jy oorspronklik bedoel elders op die plek. Maar in die ergste geval, die enigste plek dalk die heel onderkant van die data wees struktuur, die einde van die skikking. So lineêre indringende, in die ergste geval, wentel in 'n lineêre algoritme waar Aaron, as hy gebeur te word ingevoeg laaste in hierdie data struktuur, kan hy bots met die eerste plek nie, maar dan eindig deur slegte geluk aan die einde. Dit is dus nie 'n konstante tyd heilige graal vir ons. Hierdie benadering van die inbring elemente in 'n data struktuur genaamd 'n gemors tafel lyk nie konstante tyd ten minste nie in die algemene geval. Dit kan oorgaan in iets lineêre. So wat as ons los botsings ietwat anders? So hier is 'n meer gesofistikeerde nader aan wat nog bekend as 'n hash tafel. En deur hash, as 'n eenkant, wat Ek bedoel is die indeks wat Ek verwys na vroeër. Om hash iets kan wees beskou as 'n werkwoord. So as jy hash Alice is 'n naam, 'n hash funksie, om so te praat, moet terugkeer 'n nommer. In hierdie geval is nul as sy behoort aan plek nul, een of sy behoort op plek een, en so meer. So my hash funksie tot dusver super eenvoudige, net na die eerste letter in iemand se naam. Maar 'n hash funksie neem as insette 'n stuk van data, 'n string, 'n int, wat ook al. En dit spoeg tipies 'n aantal. En dat die getal is waar dat die data element behoort in 'n data struktuur bekend hier as 'n hash tafel. Dus net intuïtief, dit is 'n effens ander konteks. Dit is eintlik verwys na 'n voorbeeld waarby verjaarsdae, waar is daar dalk soveel as 31 dae in die maand. Maar wat het hierdie persoon besluit om te doen in die geval van 'n botsing? Konteks nou geplaas word en nie 'n botsing van name nie, maar 'n botsing van verjaarsdae, As twee mense het dieselfde verjaarsdag op 2 Oktober, byvoorbeeld. STUDENT: [onhoorbaar]. Spreker 1: Ja, so hier het ons ' die benutting van geskakelde lyste. So dit lyk 'n bietjie anders as ons het dit vroeër. Maar ons verskyn het om 'n skikking op die linkerkant. Dit is een indeks, vir geen spesifieke rede. Maar dit is nog steeds 'n skikking. Dit is 'n verskeidenheid van wysers. En elkeen van hierdie elemente, elk van hierdie sirkels of houe - die streep verteenwoordig null - elk van hierdie wysers is blykbaar verwys na wat data struktuur? 'N geskakelde lys. So nou het ons die vermoë om te harde kode in ons program die grootte van die tabel. In hierdie geval, ons weet daar is nooit meer as 31 dae in 'n maand. So hard kodering 'n waarde soos 31 is redelike in daardie konteks. In die konteks van die name, hard kodering 26 is nie onredelik nie om mense se name net begin met, byvoorbeeld, die alfabet wat 'n deur Z. Ons kan inprop hulle almal in die data struktuur so lank as wat, toe kry ons 'n botsing, het ons nie die name hier, ons dink in plaas van hierdie selle nie as stringe self nie, maar as verwysings na, byvoorbeeld, Alice. En dan Alice kan nog 'n wyser na 'n ander naam begin met A. En Bob gaan eintlik oor hier. En as daar 'n ander naam begin met B, hy beland hier. En so het elk van die elemente van hierdie tafel twee, as ons ontwerp dat dit ' bietjie meer slim - kom op - As ons ontwerp dat dit 'n bietjie meer slim, word nou 'n aangepaste data struktuur, waar daar is geen harde limiet op hoeveel elemente wat jy kan voeg in dit, want as jy nie ' 'n botsing, dit is goed. Net voort te gaan en voeg dit te wat ons gesien het 'n bietjie gelede was bekend as 'n geskakelde lys. Wel, laat ons breek vir net 'n oomblik. Wat is die waarskynlikheid van 'n botsing in die eerste plek? Reg, miskien is ek oor dink, miskien Ek is meer as Ingenieurswese Die probleem is, want jy weet wat? Ja, ek kan kom met 'n arbitrêre voorbeelde uit die top van my kop soos Allison en Aaron, maar in werklikheid, gegee 'n eenvormige verspreiding van insette, wat is 'n paar random invoegings in 'n data struktuur, wat werklik die waarskynlikheid van 'n botsing? Wel blyk, dit is eintlik super hoog. Laat my veralgemeen hierdie probleem is as dit. So in 'n kamer van n CS50 studente, wat is die waarskynlikheid dat ten minste twee studente in die kamer het dieselfde verjaarsdag? So is daar wat. 'n paar Hund - 200, 300 mense hier en verskeie honderd mense by die huis vandag. So as jy wil om onsself te vra wat is die waarskynlikheid van twee mense in hierdie kamer met dieselfde verjaarsdag, ons kan uitvind dit uit. En ek eis eintlik is daar twee mense met dieselfde verjaardag. Byvoorbeeld, nie almal het verjaar vandag? Gister? Môre? Alle reg, sodat dit voel asof ek gaan om hierdie 363 of so meer te doen keer om werklik uit te vind As ons nie 'n botsing. Of ons kan net doen dit wiskundig eerder as tediously om dit te doen. En stel die volgende. So ek stel voor dat ons die kan modelleer waarskynlikheid van twee mense wat die dieselfde verjaarsdag as die waarskynlikheid van 1 minus die waarskynlikheid van niemand wat dieselfde verjaarsdag. So om dit te kry, en dit is net die fancy manier van die skryf van hierdie, vir die eerste persoon in die kamer, het hy of sy kan enige een van die moontlike verjaarsdae aanvaarding van 365 dae in die jaar, Met apologie aan persone met die Februarie-29ste verjaardag. So het die eerste persoon in die kamer is gratis enige aantal verjaarsdae te hê uit die 365 moontlikhede sodat ons sal doen wat 365 gedeel deur 365, Dit is een. Die volgende persoon in die kamer, indien die doel is 'n botsing te vermy, kan slegs sy of haar verjaardag op hoe baie verskillende moontlike dae? 364. So het die tweede termyn in hierdie uitdrukking is wese doen wat wiskunde vir ons deur af te trek uit 'n moontlike dag. En dan is die volgende dag, die volgende dag, die volgende dag af tot die totale aantal van die mense in die kamer. En as ons dan kyk, wat is dan die waarskynlikheid nie van almal wat unieke verjaarsdae, maar weer 1 minus dat, wat ons kry, is 'n uitdrukking wat kan baie denkbeeldig lyk. Maar dit is meer interessant om te kyk na visueel. Dit is 'n grafiek waar op die x-as die aantal mense wat in die kamer, die aantal verjaarsdae. Op die y-as is die waarskynlikheid van 'n botsing, twee mense wat dieselfde verjaarsdag. En die afhaal van die kurwe is dat sodra jy 40 te hou studente nie, is jy op 'n 90% waarskynlikheid combinatorically van twee mense of meer met dieselfde verjaarsdag. En as jy een van 58 mense is dit te hou byna 100% van 'n kans om die twee mense in die kamer gaan die te hê dieselfde verjaarsdag, selfs al is daar 365 of 366 moontlik emmers, en Slegs 58 mense in die kamer. Net statisties jy geneig om te kry botsings, wat in 'n kort motiveer hierdie bespreking. Dat selfs as ons fancy hier, en begin met die kettings, ons is nog steeds gaan botsings te hê. Sodat lei tot die vraag, wat is die koste om invoegings en delesies in 'n data struktuur soos hierdie? Wel, laat my stel - en laat my terug te gaan na die skerm oor hier - as ons met n elemente in die lys, so as ons probeer om te voeg n elemente, en ons het hoeveel totale emmers? Kom ons sê 31 totale emmers in die geval van verjaarsdae. Wat is die maksimum lengte van een van hierdie kettings potensieel? As weer daar is 31 moontlike verjaarsdae in 'n gegewe maand. En ons is net geplant almal - eintlik is dit 'n stupid voorbeeld. Kom ons doen 26 plaas. So as eintlik mense wie se name begin met 'n deur Z, waardeur ons 26 moontlikhede. En ons is met behulp van 'n data struktuur soos die een wat ons nou net gesien het, waardeur ons 'n 'n verskeidenheid van wysers, wat elk dui op 'n geskakelde lys waar die eerste lys is almal met die naam Alice. Die tweede lys is elke met die noem wat begin met A, begin met B, en so meer. Wat is die waarskynlike lengte van elk van die lyste indien ons aanvaar 'n mooi skoon verspreiding van name 'n deur Z oor die hele data struktuur? Daar is 'n volk in die data struktuur gedeel deur 26, as hulle mooi versprei oor die hele data struktuur. So het die lengte van elk van hierdie kettings is n gedeel deur 26. Maar in 'n groot O-notasie, wat is dit? Wat is dit regtig? So dit is regtig net n, reg? Want ons het gesê in die verlede, dat ugh jy deel deur 26. Ja, in werklikheid is dit is vinniger. Maar in teorie, is dit nie fundamenteel alles wat vinniger. So lyk ons ​​nie te wees nie alles wat veel nader aan die heilige graal. Trouens, dit is net lineêre tyd. Heck, op hierdie punt, hoekom doen ons nie gebruik net een groot gekoppel lys? Hoekom doen ons nie net gebruik om 'n groot verskeidenheid van die name van die stoor almal in die kamer? Wel, is daar nog iets dwingende oor 'n hash tafel? Is daar nog iets dwingende oor 'n data struktuur wat lyk soos hierdie? Dit. STUDENT: [onhoorbaar]. Spreker 1: Right, en weer is dit net 'n lineêre tyd algoritme, en 'n lineêre tyd data struktuur, hoekom het ek nie net slaan almal se naam in 'n groot skikking, of in 'n groot gekoppel lys? En ophou om CS soveel harder as wat dit moet wees? Wat is dwingende oor hierdie, selfs al het ek gekrap dit uit? STUDENT: [onhoorbaar]. Spreker 1: invoegings is nie? Duur nie. So invoegings potensieel kan nog steeds wees konstante tyd, selfs as jou data struktuur lyk soos hierdie, 'n verskeidenheid van wysers, is elk van wat dui op potensieel 'n geskakelde lys. Hoe kan jy bereik konstante tyd inplaas van name? Plak dit in die voorkant, reg? As ons offer 'n ontwerp doel van vroeër, waar ons wou hou elkeen se naam, byvoorbeeld, gesorteer, of al die nommers wat op die verhoog gesorteer, veronderstel dat ons 'n ongesorteerde gekoppel lys. Dit kos ons net een of twee stappe, soos in die geval van Ben en Brian Vroeër, in te voeg 'n element by die begin van die lys. So as ons nie omgee sorteer al van die name wat begin met A of al die name wat begin met B, kan ons nog bereik konstante tyd te voeg. Nou kyk op Alice of Bob of enige naam meer algemeen is nog wat? Dit is 'n groot O van n gedeel deur 26, in die ideale geval waar almal is eenvormig versprei, waar daar soveel A se as daar Z's, wat waarskynlik onrealisties. Maar dit is nog steeds lineêre. Maar hier is ons, ons kom terug na die punt van asimptotiese notasie om teoreties waar. Maar in die werklike wêreld, as ek beweer dat my program kan iets doen 26 keer vinniger as joune, wie se program gaan jy verkies om met behulp van? Joune of myne, wat is 26 keer vinniger? Realisties, die persoon wie is 26 keer vinniger, selfs al is teoreties ons algoritmes in dieselfde asimptotiese loop van die tyd. Laat my stel 'n ander oplossing geheel en al. En as dit nie blaas nie jou gedagtes, Ons is uit die data strukture. So dit is dit 'n Trie - soort van 'n stupid naam. Dit kom van Retrievals, en die woord gespel Trie, t-r-i-e, as gevolg van Natuurlik herwinning klink soos Trie. Maar dit is die geskiedenis van die woord Trie. So 'n Trie is inderdaad 'n soort van die boom, en dit is ook 'n toneelstuk op daardie woord. En selfs al is jy kan baie dit nie sien nie met hierdie visualisering, 'n tydstip waarop 'n boom gestruktureer is, soos 'n familie boom met 'n voorloper op die top en baie van kleinkinders en agterkleinkinders as blare aan die onderkant. Maar elke knoop in 'n tydstip waarop 'n skikking. En dit is in 'n skikking - en laat eenvoudig vir 'n oomblik - dit is 'n skikking, in hierdie geval, die grootte 26, waar elke knoop weer 'n skikking van die grootte 26, waar die nulde element in daardie verskeidenheid verteenwoordig 'n, en die laaste element in elke sodanige verskeidenheid verteenwoordig Z. So ek stel voor, dan, dat hierdie data struktuur, bekend as 'n Trie, kan gebruik ook woorde op te slaan. Ons het 'n oomblik gelede hoe ons kon slaan woorde, of in hierdie geval name, en ons vroeër gesien het hoe ons getalle kan stoor, maar as ons fokus op name of snare hier, sien wat is interessant. Ek beweer dat die naam Maxwell is binnekant van die data struktuur. Waar sien jy Maxwell? STUDENT: [onhoorbaar]. Spreker 1: Op die linkerkant. So, wat is interessant met hierdie data struktuur is eerder as die winkel string M-A-X-W-E-L-L agteroorskuisstreep nul, al contiguously, wat jy plaas nie volg. As dit is 'n Trie soos data struktuur, elk van wie se knope is weer 'n skikking, en jy wil Maxwell te slaan, moet jy eers indeks en so die wortel se knoop, sodat te spreek, het die boonste knoop, by plek M, regs, so rofweg in die middel. En dan van daar af, jy volg 'n wyser na 'n kind nodes, om so te praat. So in die stamboom sin, volg jy dit afwaarts. En dit lei jou na 'n ander node aan die linkerkant is daar, wat net nog 'n skikking. En dan as jy wil Maxwell te slaan, vind jy die wyser wat verteenwoordig A, wat is hierdie een hier. Dan gaan jy na die volgende knoop. En kennis - dit is die rede waarom die foto's 'n bietjie mislei - hierdie knoop lyk super klein. Maar aan die regterkant van hierdie is Y en Z. Dit is net die skrywer het kapt die prentjie sodat jy eintlik sien dinge. Andersins hierdie foto sou wees uiters wyd. So nou kan jy indeks in plek X, dan W, dan E, dan is L, dan L. Dan wat is hierdie nuuskierigheid? Wel, as ons die gebruik van hierdie soort van nuwe neem oor hoe om 'n string op te slaan in 'n data struktuur, het jy nog nodig het om te wese gaan af in die data struktuur wat 'n woord hier eindig. Met ander woorde, elk van hierdie nodes een of ander manier het om te onthou dat ons eintlik gevolg van al hierdie wenke en laat 'n bietjie brood krummel aan die onderkant hier van hierdie struktuur M-A-X-W-E-L-L aan te dui is inderdaad in hierdie data struktuur. So ons kan dit doen as volg. Elkeen van die nodes in die prentjie wat ons net gesien het, het een, 'n skikking van grootte 27. En dit is nou 27, want in p stel ses, ons sal eintlik gee jou 'n toespraak, sodat ons kan name soos O'Reilly en ander met apostrofs. Maar dieselfde idee. Elkeen van hierdie elemente in die verskeidenheid punte na 'n struct knoop, sodat net 'n knoop. So dit is baie herinner van ons gekoppelde lys. En dan het ek 'n Boole, wat ek sal noem woord, wat net gaan om te wees waar as 'n woord eindig op hierdie nodus in die boom. Dit verteenwoordig effektief die klein driehoek het ons 'n oomblik gelede. So as 'n woord eindig op daardie knoop in die boom, sal die woord veld waar te wees, wat konseptueel kontrole af, of ons is die opstel van hierdie driehoek, ja daar is 'n woord hier. So dit is 'n Trie. En nou is die vraag, wat is sy loop van die tyd? Is dit groot O van n? Is dit iets anders? Wel, as jy het n 'name in die data struktuur, Maxwell om net een van hulle, wat is die loop van die tyd van voeg of te vind Maxwell? Wat is die loop van die tyd inbring van Maxwell? As daar 'n ander name reeds in die tabel? Ja? STUDENT: [onhoorbaar]. Spreker 1: Ja, dit is die lengte van die naam, reg? So M-a-x-w-e-l-l so dit voel soos hierdie algoritme is 'n groot O van sewe. Nou, natuurlik, die naam sal wissel in lengte. Miskien is dit 'n kort naam. Miskien is dit 'n langer naam. Maar wat is die sleutel hier is dat dit is 'n konstante getal is. En miskien is dit nie regtig konstant, maar God, as realisties, in 'n woordeboek, daar is waarskynlik 'n beperking op die aantal letters in 'n persoon se naam in 'n spesifieke land. En so kan ons aanvaar dat waarde 'n konstante is. Ek weet nie wat dit is. Dit is waarskynlik groter as ons dink dit is. Want daar is altyd 'n hoek geval met 'n gek lang naam. So kom ons noem dit k, maar dit is nog steeds 'n konstante vermoedelik, want elke naam in die wêreld, ten minste in 'n bepaalde land, is dat lengte of korter, so dit is 'n konstante. Maar toe het ons iets gesê het is 'n groot O van 'n konstante waarde, wat is dit regtig gelykstaande aan? Dit is regtig dieselfde ding gesê konstante tyd. Nou is ons 'n soort van bedrog, reg? Ons is soort van gebruik te maak van 'n teorie hier om te sê dat goed, einde van k is regtig net om van die een, en dit is konstante tyd. Maar dit is regtig nie. Omdat die sleutel insig hier is dat As ons n 'name reeds in hierdie data struktuur, en ons insetsel Maxwell, is die bedrag van die tyd wat dit neem om ons te voeg Maxwell aan alle geaffekteerde deur hoeveel ander mense is in die data struktuur? Lyk nie te wees nie. As ek 'n miljard meer elemente aan hierdie Trie, en voeg dan Maxwell, is Hy ten alle geraak? No En dit is in teenstelling met enige van die dag data strukture wat ons tot dusver gesien het, waar die loop van die tyd van jou algoritme heeltemal onafhanklik van hoeveel dinge is of nie reeds in die data struktuur. En so met hierdie bied jy is nou 'n geleentheid vir p stel ses, wat sal weer betrek die uitvoering van jou eie speltoetser, lees in 150000 woorde, hoe om die beste wat te stoor is nie noodwendig voor die hand liggend. En al het ek daarna gestreef om uit te vind die heilige graal, ek doen nie beweer dat 'n Trie is. In werklikheid, 'n hash tafel kan baie goed blyk te wees baie meer doeltreffend. Maar dit is net - dit is net een van die ontwerp besluite te neem jy sal hê om te maak. Maar in die sluiting van Kom ons neem 50 of so sekondes 'n blik op wat lê te neem voor volgende week en buite ons oorgang van hierdie opdrag lyn wêreld as C programme dinge web gebaseer en tale soos PHP en JavaScript en die internet self, protokolle soos HTTP, wat jy het vanselfsprekend vir die jaar nou, en getikte meeste elke dag, miskien, of gesien het. En ons sal begin om te skil terug die lae van wat is die internet. En wat is die kode wat onderlê vandag se gereedskap. So 50 sekondes van hierdie teaser hier. Ek gee jou Warriors van die Net. [Video speel] -Hy het gekom met 'n boodskap. Met 'n protokol al sy eie. Hy het gekom om 'n wêreld van wrede firewalls, onverskillige routers, en gevare ver erger as die dood. Hy is vinnig. Hy is sterk. Hy is TCPIP. En hy het jou adres. Warriors van die Net. [Einde video-vertoning] Spreker 1: Dit is hoe die internet sal werk as van volgende week.