[MUZIKO Ludante] DAVID Malan: Jen CS50. Kaj ĉi tiu estas la komenco kaj la end-- kiel literally-- preskaŭ la fino de semajno ses. 

Mi pensis, ke mi volonte dividas iom de amuza fakto. Mi tiris ĉi supre de pasinta semestro la datuma aro. Vi eble memoras, ke ni demandos al vi pri ĉiu p aro formo se vi spektis linio aŭ se vi jam ĉeestis en persono. Kaj jen la datumoj. Do hodiaŭ estis tre antaŭvideblaj. Sed ni volis elspezi iom el tempo kun vi malgraŭ tio. Ĉu iu ŝatus konjekti kial ĉi grafeo estas tiel jaggy, supren malsupren, supren malsupren, tiel konsekvence? Kion do ĉiu el la bekoj kaj trogojn reprezentas? 

Publiko: [inaudible] DAVID Malan: Efektive. Kaj pli amuze, dio malpermesu, ni tenu unu prelego en vendredo komence de la semestro, ke estas kion ni vidas okazi. Do hodiaŭ ni partoprenas en iom pli pri datumstrukturoj. Kaj doni al vi pli solida mensa modelo por problemoj en kvin, kio estas nun ekster. Fuŝo, kiun, ni protektu vin tekstdosiero iuj 100.000 plus anglaj vortoj, kaj vi tuj havos elkompreni kiel lerte ŝarĝi ilin en memoro, en RAM, uzante iuj datumoj strukturo de via elekto. 

Nun unu tia datumstrukturo povis esti, sed probable ne devus esti, la sufiĉe simplista ligillisto, kiun ni enkondukis lastan fojon. Kaj ligillisto havis almenaŭ unu avantaĝon super tabelo. Kio estas unu avantaĝon lerta kunligita defendeble? 

Publiko: Insertion. 

DAVID Malan: Insertion. Kion vi volas diri per tio? 

Publiko: Anywhere kune la listo [inaudible]. 

DAVID Malan: Bone. Do vi povas enigi ero kien vi deziras en la mezo de la listo sen devi barajar ion, kiun ni konkludis, en nia ordigado diskutoj, estas ne nepre estas bona afero, ĉar ĝi prenas tempon por fakte movas ĉiuj tiuj homoj maldekstra aŭ dekstra. Kaj tial kun ligillisto, vi povas simple malŝparas kun malloc, nova nodo, kaj tiam ĝisdatigi kelkaj pointers-- du, tri operacioj max-- kaj ni povis slot iu en ie en listo. 

Kion plu estis avantaĝa pri ligillisto? Yeah? 

Publiko: [inaudible] DAVID Malan: Perfekta. Perfekta. Estas vere dinamika. Kaj ke vi ne faras, anticipe al iu fiksa grandeco eron de memoro, kiel vi devus al kun tabelo, la inversa de kio estas ke vi povas atribui nodoj nur sur peto tiel uzante nur tiom da spaco kiel vi vere bezonas. Kontraste kun tabelo, eble vi hazarde atribui tro malmulte. Kaj tiam ĝi estas ĝuste iri esti doloro en la kolo al reallocate nova pli granda tabelo, kopiu ĉio finiĝis, liberigi la malnovan tabelon, kaj tiam movi pri via negoco. Aŭ pli malbone, vi povus atribui vojo pli memoro ol vi fakte bezonas, kaj tial vi estas iranta havi tre maldense loĝatajn tabelo, por tiel diri. 

Do ligillisto donas tiujn avantagxoj de dinamismo kaj fleksebleco kun inserciones kaj forigoj. Sed certe devas esti prezo pagita. Fakte, unu el la temoj esploris en kvizo nulo Estis paro de la komerco-offs ni vidis ĝis nun. Do kio estas prezo pagita aŭ Downside de ligillisto? Yeah. 

Publiko: Neniu hazarda aliro. 

DAVID Malan: Neniu hazarda aliro. Sed kiu zorgas? Hazarda aliro ne sonas konvinka. 

Publiko: [inaudible] DAVID Malan: Ĝuste. Se vi volas havi iu algorithm-- kaj mi efektive proponas duuma serĉo en aparta, kiu Estas unu ni uzas tute bit-- Se vi ne havas aliro aleatorio, vi ne povas fari tion simpla aritmetiko trovi kiel la meza ero kaj saltante rajton gxin. Vi anstataŭe devas starti je la unua elemento kaj lineare serĉo de maldekstra dekstren, se vi volas trovi meze aŭ ajna alia elemento. 

Publikon: ĝi probable bezonas pli memoro. 

DAVID Malan: Takes pli memoro. Kie estas tiu aldona kostas devenante en memoro? 

Publiko: [inaudible] DAVID Malan: Ĝuste. En tiu kazo tie, ni devis kunligita listo por entjeroj, kaj tamen ni estas duobliganta la kvanto de memoro ni bezonas por la ankaŭ stoki tiuj punteros. Nun malpli granda negoco kiel via structs akiri pli grandaj kaj vi stoki ne nombro sed eble studento aŭ alian objekton. Sed la punkto certe restas. Kaj tiel multaj el la operacioj en ligitaj lertaj vokitaj estis granda a de n-- lineara. Aĵoj kiel inserción aŭ serĉo aŭ viŝita en kazo ero pasis al esti ĉe la fino de la listo ĉu ĝi estas ordo aŭ ne. 

Foje vi povus akiri bonŝanca kaj en tiel malaltaj baroj sur tiuj operacioj povus ankaŭ esti konstanta tempo se vi estas ĉiam rigardante la unua elemento, ekz. Sed fine, ni promesis atingi la Holy Grail de datumstrukturoj, aŭ iuj alproksimiĝo gxiajn pere de konstanta tempo. Povas trovi elementojn aŭ aldoni elementojn aŭ forigi elementojn el listo? Ni vidos tute frue. Kaj ĝi rezultas ke unu de la mekanismojn ni tuj ekuzas hodiaŭ, jara uzo en p starigis kvin, Estas vere bela familiara. Ekzemple, se tiu estas faskon de ekzameno libroj, ĉiu el kiuj havas studentan unua Nomo kaj familinomo en ĝi, kaj mi kaptas ilin el ĉe la fino de iu ekzameno, kaj ili ĉiuj estas belaj multe en hazarda ordo, kaj ni volas iri de ordiga tiujn ekzamenojn por ke fojo gradita estas nur multe pli facila kaj rapida transdoni ilin el por lernantoj alfabete. Kia estus via instinktoj esti por amaso de ekzamenoj tiel? 

Nu, se vi estas kiel mi, vi povus vidi ke tiu estas m, tial Mi iras al ia meti tiu enen, Se ĉi tiu estas mia tablo aŭ mia garbejo kie Mi etendis tion out-- aŭ mia tabelo really-- Mi povus meti ĉiuj m tien. Oh. Jen A. Do mi povus metis la mezuro super tie. Oh. Jen alia A. Mi iras meti tiun ĉi tien. Jen Z. Jen alia M. Kaj tiel Mi povus komenci farante aretojn kiel ĉi. Kaj tiam eble mi irus en postaj kaj ia tre nitpicky-tas speco la individuo aretoj. Sed la punkto estas mi aspektus ĉe la eniro ke mi manoj kaj mi farus kelkajn kalkulinta decido bazita sur tiu eniro. Se ĝi komenciĝas per A, metis ĝin tien. Se ĝi komencas kun Z, metu ĝin sur tie kaj ĉio en inter. 

Do tiu estas teknika kiu estas ĝenerale konata kiel hashing-- H-A-S-H-- kiu ĝenerale signifas prenanta enigo kaj uzas input komputi valoro, ĝenerale numero, kaj ke nombro estas la indico en stokado ujo, kiel tabelo. Do alivorte, mi povus havi hash funkcio, kiel mi faras en mia kapo, ke se mi vidas ke iu estas nomo kiu komenciĝas per A, Mi tuj mapaj ke al nulo en mia kapo. Kaj se mi vidas iun kun Z, mi estas tuj mapaj ke al 25 en mia kapo kaj tiam enkalkulu en la lasta plej amaso. 

Nun, se vi pensas pri ne mia cerbo sed C programo, kio nombroj povis fidi atingi tiun saman rezulton? En aliaj vortoj, se vi havis la ASCII A kiel vi determini kio sitelo meti ĝin? Vi probable ne volas jxetos en rubujon 65, kiu estus kiel tie sen bona kialo. Kie vi deziras meti en terminoj de lia ASCII valoro? Kie vi deziras fari al liaj ASCII valoro veni supren kun inteligenta sitelo meti ĝin? 

Publiko: Minus A. 

DAVID Malan: Jes. Do minus A aŭ minus specife 65 se ĝi estas majuskla A. Aŭ 98 se ĝi estas minuskla a. Kaj por ke ili permesus al ni, tre simple kaj tre aritmetike, meti ion en sitelo tiel. Do rezultas ni efektive fari ĉi tiel eĉ kun la kvizojn. 

Do vi eble memoras vin kaj cxirkaux via instruado ulo nomo sur la ferdekon. Kaj la TF nomoj estis organizitaj en tiuj kolumnoj alfabete, nu, kredu ĝin aŭ ne, Kiam ĉiuj 80 plus nin kunvenigis la alian nokton al grado, la lasta paŝo en nia grading procezo estas hash la kvizojn en grandan spaco de etaĝo ĉe la [inaudible] kaj meti ĉies kvizojn el en ĝuste la ordo de ilia TF La nomoj sur la kovrilo, ĉar tiam ĝi estas multe pli facile por ni serĉi tra tiu uzanta linearaj serĉu aŭ ian lertecon por TF trovi sian aŭ ŝi studentoj kvizojn. 

Do tiu ideo de hashing ke vi vidos estas sufiĉe potenca estas vere bela banala kaj tre intuicia, multe kiel eble dividu kaj konkero estis en semajno nulo. Mi firme antaŭen al la hackathon paro de jaroj. Tio estis Zamyla kaj paro da alia personaro saluton studentoj kiam ili eniris. Kaj ni havis tutan faskon da kunmeto tabloj tie kun nomo etikedoj. Kaj ni estis la nomo tags organizita kun kiel la mezuro tien kaj Zs tie. Kaj venis unu el la TFS tre lerte verkis tion kiel la instrukcioj cxar la tago. Kaj en la semajno 12 de la semestro ĉi ĉiuj perfektiĝas senco kaj ĉiuj sciis, kion fari. Sed anytime vi havas vosto en la sama maniero, vi realiganta la sama nocio de hash. Do ni formaligi gxin iomete. Jen tabelo. Ĝi estas desegnita por esti iom larĝa ĝuste priskribi, vide, ke ni povu kordoj en iu kiel ĉi tio. Kaj ĉi tabelo estas klare de grandeco 26 entute. Kaj la afero estas nomita tablo arbitre. Sed tio estas nur artisto lego de kia hash tablo povus esti. 

Do hash tablo nun tuj esti supera nivelo datumstrukturo. Je la fino de la tago ni estas proksimume vidi ke vi povas implementar hash tablo, kiu estas tre simila al la check-in linio ĉe hackathon multe ŝatas ĉi tablo uzita por ordiga ekzameno libroj. Sed hash tablo ia tiu alta nivelo koncepto kiu povus uzi tabelo sub la kapuĉo funkciigi ĝin, aŭ ĝi povus uzi longitudon listo, aŭ eĉ eble iuj aliaj datumstrukturoj. Kaj nun jen la theme-- preno kelkaj el tiuj fundamentaj ingrediencoj kiel tabelo kaj tiu konstruaĵo bloki nun de longa lerta kaj vidante kion alian ni povas konstrui sur supro de tiuj, kiel ingrediencoj en recepto, farante pli kaj pli interesa kaj utila finaj rezultoj. 

Do kun la hash tablo ni povus apliki ŝin memore pictóricamente ŝatas tion, sed kiom eble ĝi reale esti koditaj supren? Nu, eble simple estas tiu. Se kapablo en ĉiuj kaskedoj, estas nur iuj constant-- ekzemple 26 por 26 literoj de la alphabet-- Mi povus nomi mian variablo tablo kaj mi povus aserti, ke mi tuj metis char steloj en tie, aŭ ŝnuro. Do ĝi estas tiel simpla kiel ĉi se vi volas implementar hash tablo. Kaj tamen, tio estas vere nur tabelo. Sed denove, hash tablo estas nun kion ni alvoki abstrakta datumtipo estas nur ia conceptual layering supre de iu pli sekulara nun kiel tabelo. 

Nun, kiel do ni iru pri solvi problemojn? Nu, antaŭe mi havis la lukson havi sufiĉe tablo spacon tie tiel ke mi povus meti la kvizojn ie mi volis. Do Kiel povas iri tien. Zs venu ĉi tie. M povus iri tien. Kaj tiam mi havis iun ekstran spacon. Sed tio estas iom de Cheat dekstra nun ĉar ĉi tabelo, se mi vere pensis pri ĝi kiel tabelo, estas nur tuj estos de iu fiksa grandeco. 

Do teknike, se mi tiri ĝis alia studenta kvizo kaj vidu, ho, tiu persono nomo komenciĝas per A tro, Mi ia volas meti ĝin tie. Sed tuj kiam mi metis ĝin tie, se tiu tabelo efektive reprezentas tabelo, Mi iras al esti supera aŭ clobbering Kiu ĉi studenta kvizo estas. Rajto? Se ĉi tiu estas tabelo, nur unu afero povas iru en ĉiu el tiuj ĉeloj aŭ elementoj. Kaj tial mi specon de havi elekti kaj elekti. 

Nun antaŭe mi specon de trompis kaj faris tion aŭ mi nur speco de plata ili supre la alia. Sed tio ne tuj flugas en kodo. Do kie mi povus meti la dua studento kies nomo estas A se ĉiuj mi havis estas ĉi disponebla tablo spaco? Kaj mi uzis tri fendojn kaj Ŝajnas ke estas nur kelkaj aliaj. Kion vi povus fari? Publiko: [inaudible] DAVID Malan: Jes. Eble ni simple teni ĝin simpla. Rajto? Ĝi ne taŭgas, kie mi volas meti ĝin. Do mi tuj metis ĝin teknike kie B devus iri. Nun, kompreneble, mi ekde pentri min en angulon. Se mi alvenas al lernanto kies nomo estas fakte B Nun B tuj movi iom antaŭen, kiel povus okazi, Yep, se tio estas B, nun devas iri tien. 

Kaj tiel ĉi tre rapide povus iĝi problema, sed estas teknika kiu reale estas referita al kiel lineara sondado, per vi nur rigardu vian tabelo por esti laŭ la linio. Kaj vi ĝuste speco de sondilo aux inspekti ĉiu disponebla elemento serĉas havebla makulo. Kaj kiam vi trovas unu, vi faligis ĝin tie. 

Nun, la prezo pagita nun por ĉi tiu solvo estas kio? Ni havas fiksan grandecon tabelo, kaj kiam mi enŝovu nomoj en ĝin, almenaŭ komence, kio estas la rula tempo de inserción por meti la studentoj ' kvizojn en la dekstra siteloj? Big O de kio? 

Publiko: n. DAVID Malan: Mi aŭdis granda O de n. Tio ne veras. Sed ni turmentus aparte kial en nur momento. Kion alian povus esti? 

Publiko: [inaudible] DAVID Malan: Kaj lasu min fari ĝin vide. Do hipotezu tiu estas la letero S. 

Publiko: Estas unu. DAVID Malan: Estas unu. Rajto? Tiu estas tabelo, kiu signifas ke ni havos hazarda aliro. Kaj se ni pensas pri tio kiel nulo kaj ĉi tiu 25 kaj ni rimarkas ke, Ho, ĉi tie estas mia enigo S, Mi certe povas konverti S, estas ASCII, al responda nombro inter nulo kaj 25 kaj tiam tuj meti ĝin kie ĝi apartenas. 

Sed kompreneble, kiam mi alvenas al la dua persono kiu estas nomo estas A aŭ B aŭ C eventuale, se mi uzis la lineara sondado kiel mia solvo, la rula tempo de inserción en la plej malbona kazo Efektive tuj devolve en kio? Kaj mi ne aŭdas ĝin tie korekte frue. Publiko: [inaudible] DAVID Malan: Do ĝi estas n ja unufoje vi havas sufiĉe granda datumaro. Do, unuflanke, se via tabelo estas sufiĉe granda kaj viajn datumojn estas maldensa sufiĉas, vi ricevas tiun belegan konstanta tempo. Sed tuj kiam vi komencas atingi pli kaj pli da eroj, kaj ĝuste statistike vi ricevas pli da homoj kun la letero A kiel ilia nomo aŭ la letero B, ĝi povus potenciale devolve en ion pli lineara. Do ne plene perfekta. Do ni povus fari pli bone? 

Nu, kion fari estis nia solvon antaŭ kiam ni volas havi pli dinamismo ol iu kiel tabelo permesita? Publiko: [inaudible] DAVID Malan: Kion ni enkonduki? Yeah. Tiel lerta kunligita. Nu, ni vidu kion kunligita lerta povus fari por ni anstataŭe. Nu, lasu min proponi ke ni desegni la bildon kiel sekvas. Nun ĉi tiu estas malsama bildo de ekzemplo el alia teksto, efektive, ke fakte uzante tabelo de amplekso 31. Kaj tiu aŭtoro simple decidis hash kordoj ne bazita sur la persona nomoj sed bazita sur ilia birthdates. Sendepende de la monato, oni kalkulis se vi naskiĝis en la unua de monato aŭ la 31a de la monato, la aŭtoro Mi hash bazita sur tiu valoro, tiel kiel disvastigi la nomojn el iom pli ol 26 makuloj povus permesi. Kaj eble ĝi estas iom pli unuforma ol iri kun alfabeta leteroj ĉar kompreneble ekzistas probable pli da homoj en la mondo kun nomoj ke komenciĝu per ol certe kelkaj aliaj literoj de la alfabeto. Do eble tio iom pli unuforma, supozante uniforma distribuo de beboj transa monato. 

Sed, kompreneble, tiu estas ankoraŭ neperfekta. Rajto? Ni devi kolizioj. Pluraj personoj en tiu datumstrukturo restas havantaj la saman naskiĝo almenaŭ vi senkonsidere monato. Sed kion la aŭtoro faris? Nu, ĝi aspektas kiel ni havas tabelo sur la maldekstra flanko desegnita vertikale, sed tio estas nura artisto transdonado. Negrave kiudirekte vi cxerpi tabelo, estas ankoraŭ tabelo. Kio estas ĉi tiu tabelo de ŝajne? 

Publiko: Ligita listo. 

DAVID Malan: Jes. Ĝi aspektas kiel ĝi estas tabelo de ligitaj listo. Do denove, por tiu punkto de la varo uzi tiujn datumstrukturoj nun kiel ingrediencojn por pli interesajn solvojn, vi povas absolute preni fundamenta, kiel tabelo, kaj poste prenu ion pli interesa kiel ligillisto kaj eĉ kombini ilin en eĉ pli interesa datumstrukturo. Kaj efektive, tiu tro farus nomiĝi hash tablo per la tabelo estas vere la hash tablo sed tiu hash tablo havas ĉenoj, por tiel diri, kiu povas kreski aŭ ŝrumpi bazita sur la nombro de elementoj vi volas enigi. 

Nun, laŭe, kio estas la rula tempo nun? Se mi volas enigi iu kies naskiĝtago estas oktobro 31 Kie li aŭ ŝi iros? Bone. Ĉe la fundo kie diras 31. Kaj tio estas perfekta. Tio estis konstanta tempo. Sed kio se ni trovos iun alian kies naskiĝtago estas, vidu, Oktobro, Novembro, Decembro 31? Kie estas li aŭ ŝi tuj iros? Samon. Du paŝo tamen. Tio estas konstanto se ĉu ne? Bone. Nuntempe ĝi estas. Sed en la ĝenerala kazo, ju pli da homoj ni aldonu, _probabilistically_, ni iras akiri pli kaj pli kolizioj. 

Nun tiu estas iom bona ĉar teknike nun mia ĉenoj eblus en la plej malbona kazo, kiel longe? Se mi enŝovu n popolon en tiu pli malnaiva datumstrukturo, n popolon en la plej malbona kazo tuj estos n. Kial? 

Publiko: Ĉar se ĉiuj havas la saman naskiĝtagon, ili tuj estos unu linio. DAVID Malan: Perfekta. Ĝi povus esti iom artefaritaj, sed nur en la plej malbona kazo, se ĉiuj havas la saman naskiĝtagon, donita la enigoj vi, vi tuj havos amase longa ĉeno. Kaj tiel, vi povus nomi tion hash tablo, sed vere ĝi estas nur amasan ligillisto kun tutan multan malŝparis spaco. Sed ĝenerale, se ni supozas, ke almenaŭ naskiĝtago estas uniform-- kaj tio probable ne estas. Mi faras ke supren. Sed se ni supozas, por pro diskuto ke ili, tiam teorie se tio estas la vertikala reprezento de la tabelo, bone do espereble vi tuj akiri ĉenoj kiuj estas, vi scias, proksimume la sama longo, kie ĉiu de tiuj reprezentas tago de la monato. 

Nun, se estas 31 tagoj en la monato kiu volas diri mian rultempo vere estas granda O de n super 31, kiu sentas pli bona ol lineara. Sed kio estis unu el niaj devontigoj paron de semajnoj antaŭ kiam ĝi venis al esprimo la rula tempo de algoritmo? Simple nur rigardi la alta ordo terminon. Rajto? 31 estas definitive helpema. Sed tio estas ankoraŭ granda O de n. Sed unu el la temoj de problemo starigis kvin tuj estos al agnoski ke absolute, asimptote, teorie tiu datumstrukturo Estas ne pli bona ol nur unu masiva ligillisto. Kaj efektive, en la plej malbona kazo, ĉi hash tablo povus devolve en tiun. 

Sed en la reala mondo, kun ni homoj ke propraj Macs aŭ PC aŭ kio ajn kaj kuras reala mondo programaro sur reala mondo datumoj kiun algoritmon vi iras preferi? Kiu portas fino paŝoj aŭ Kiu prenas n dividita per 31 paŝoj trovi iun pecon de datumoj aŭ serĉi informojn? Mi volas diri, absolute la 31 fabrikas diferenco en la reala mondo. Ĝi estas 31 fojoj pli rapida. Kaj ni homoj estas sendube tuj estimos tio. 

Do realigi la dicotomía ekzistas inter reale parolante pri aferoj teorie kaj asimptote kiu definitive havas valoron kiel ni vidis, sed en la reala mondo, se vi interesas nur farante la homa feliĉa por ĝenerala enigoj, vi eble tre bone volas akcepti la fakto, ke, jes, tio estas lineara, sed estas 31 fojoj pli rapida ol lineara povus esti. Kaj eĉ pli bone, ni ne nur devas faru ion arbitra kiel naskiĝo, ni povis elspezi iom pli tempo kaj lerteco kaj pensi pri kio ni povus fari, donis la nomon de persono kaj eble ilia naskiĝo kombini tiujn ingrediencoj elkompreni ion kiu estas vere pli unuforma kaj malpli jaggy, tiel diri, ol tiu bildo aktuale sugestas estu. Kiel ni povus apliki tion en la kodo? Nu, lasu min proponi ke ni nur prunteprenis kelkajn sintakso ni uzis paron tempoj tiom. Kaj mi tuj difinos nodon, kiu denove estas ĝenerala termino por nur kelkaj kontenero por iu datumstrukturo. Mi tuj proponas ke ŝnureto tuj tien. Sed ni tuj komencos preni tiuj trejnado radoj for nun. 

Plu CS50 biblioteko vere, krom se vi volas uzi ĝin por via fina projekto, kiu estas pura, sed nun ni iras por tiri reen la kurteno kaj diri estas nur char stelo. Do la vorto tie tuj estos la persono nomo en demando. Kaj nun mi havas ligilon tie al la sekva nodo tiel ke ĉi tiuj reprezentas ĉiu el la nodoj en la ĉeno, potenciale, de ligillisto. 

Kaj nun kio do mi rakontu la hash tablo mem? Kjel mi rakontos cxi tiun tutan strukturon? Nu, vere, multe kiel mi uzis montrilon al nur la unua elemento de listo antaŭe, simile mi povas simple diri Mi nur bezonas faskon de punteros implementar ĉi tiu tuta hash tablo. Mi iras havi tabelo nomata tablo por hash tablo. Ĝi tuj estos de grandeco kapablo. Tiel estas kiel multaj elementoj povas havi en ĝi. Kaj ĉiu el tiuj elementoj en ĉi tabelo tuj estos nodo stelo. Kial? Nu, por ĉi tiu bildo, kio mi estas realiganta la hash tablo efike en la komenco estas nur tiu tabelo ke ni eltiris vertikale, ĉiu el kies kvadratoj reprezentas montrilo. Ke tiuj, kiuj havas slashes tra ili estas simple nula. Kaj tiuj, kiuj havas sagoj tuj dekstre Estas reala punteros al efektiva nodoj, Ergo la komenco de ligillisto. 

Do jen, do, estas kiel ni povus implementar hash tablo ke implementa apartan sinsekvon. Nun ni povas fari pli bone? Bone mi promesis lastan fojon ke ni povis atingi konstantan tempon. Kaj mi ia donis vin konstanta tempo tie, sed tiam ne diris vere konstantan tempo ĉar ĝi estas ankoraŭ dependa de la tuta nombro de elementoj vi inputting en la datumstrukturo. Sed supozu ni faris. Lasu min reiri al la ekrano super tie. Permesu al mi ankaŭ projekti ĉi tien, klaraj la ekrano, kaj supozas ke mi tion faris. Supozi volis enmeti la nomon Daven en en mian datumstrukturo. 

Do mi volas enigi kordo Daven en la datumstrukturo. Kio se mi ne uzas hash tablo, sed mi uzas iu kiu estas pli arbo-simila kiel familio arbo, kie vi havas iun radikon en la supro kaj tiam nodoj kaj folioj kiuj iras malsupren kaj eksteren. Supozu, ke mi volas enigi Daven La en kio estas nuntempe vaka listo. Mi tuj faros la sekvan: Mi tuj kreos nodon en tiu familio arbo-simila datumstrukturo kiuj aspektas iom kiel tio, ĉiu el kiuj ortanguloj estas, ni diru, nun 26 eroj en ĝi. Kaj ĉiu de la ĉeloj en tiu tabelo tuj reprezenti la litero de alfabeto. 

Specife, Mi iras por trakti ĉi estas A, do B, tiam C, tiam D, ĉi tie. Do tiu tuj efike reprezenti la literon D. Sed enigi ĉiuj Daven La nomon mi bezonas fari iom pli. Do mi unue iri al hash, por tiel diri. Mi iras rigardi la unuan literon en Daven la kiu estas evidente D, kaj mi tuj rezervu nodon kiu vidas kiel this-- grandan rektangulon big sufiĉis por persvadi la tuta alfabeto. 

Nun D estas farita. Nun A. D-A-V-E-N estas la celo. Do nun kion mi tuj faros estas tiu. Apenaŭ mi komencis D avizo ne estas puntero tie. Estas rubo valoroj en la momento, aŭ mi pravalorizi ĝin nula. Sed lasu min plu iri kun ĉi tiu ideo de konstruado de arbo. Lasu min atribui alia de tiuj nodoj kiu havas 26 eroj en ĝi. 

Kaj vi scias kion? Se ĉi tio estas nur nodo en memoro ke Mi kreis kun malloc, uzante struct kiel ni baldaŭ vidos, Mi tuj faros this-- Mi iras al desegni sago de la afero, kiun reprezentis D malsupren al tiu nova nodo. Kaj nun, unue la proksima letero en Daven nomo, V-- D-A-V-- Mi tuj iros antaŭen ellogu alia nodo kiel tiu, per la V elementoj tie, kiuj ni devos sortear instance-- Whoops. Ni ne tiros tie. Ĝi tuj iru tien. 

Tiam ni tuj opinias tion V. Kaj poste malsupren tie ni iras al indekso malsupren de V en kion ni konsideras E. Kaj tiam el tie ni tuj iri havi unu el tiuj nodoj tie. Kaj nun ni havas demandon respondi. Mi bezonas iel indiki ke ni estas ĉe la fino de la kordo Daven. Do mi povis nur lasi ĝin nula. 

Sed kio se ni havas Daven La plena nomo ankaŭ, kiu estas, kiel ni jam diris, Davenport? Do kio se Daven estas fakte subĉeno, prefikso de multe pli longa kordo? Ni ne povas simple konstante diru nenion tuj iri tien, ĉar ni povis neniam enmeti vorton kiel Davenport en tiu datumstrukturo 

Do kion ni povus fari anstataŭ trovas trakti ĉiu el tiuj elementoj kiel eble havante du elementoj ene de ili. Unu estas puntero ja kiel Mi estis faranta. Do ĉiu el tiuj skatoloj ne estas nur unu ĉelo. Sed kion se la supro one-- malsupre ies tuj estos nula, ĉar ne ekzistas Davenport nur ankoraŭ. Kio se la supra Estas iu speciala valoro? Kaj tuj estos iom malfacile treni lin tiu grandeco. Sed supozu gxuste ĉekon marko. Kontroli. D-A-V-E-N estas ĉeno en tiu datumstrukturo. 

Dume, se mi havus pli spaco tie mi povis fari P-O-R-T, kaj mi povus meti ĉeko en la nodo kiu havas la literon T en la fino. Do tio estas amase kompleksa aspekto datumstrukturo. Kaj mia manskribo certe ne helpas. Sed se mi volas enigi ion alie, konsideri kion ni faros. Se ni volis meti Davidon, Ni volonte sekvus la saman logikon, D-A-V, sed nun mi notus en la sekvanta elemento ne de E, sed de Mi al D. Do tuj estos pli nodoj en la arbo. Ni tuj havas alvokon malloc pli. Sed mi ne volas fari kompleta salaton de ĉi tiu pentraĵo. Do ni anstataŭ rigardi unu kiuj pasis antaŭ-formulita kiel tiu de ne pentras, punkto, dots, sed simple mallongigita arrays. Sed ĉiu el la nodoj en tiu arbo tien reprezentas la saman thing-- tabelo Radio de grandeco 26. 

Aŭ se ni volas esti vere taŭga nun kion se ies nomon apostrofo, ni supozi ke ĉiu nodo reale havas kiel 27 indeksoj en ĝi, ne nur 26. Do tio nun tuj estos datuma strukturo nomiĝas trie-- T-R-Mi-E. A trie, kiu estas supozeble historie saĝa nomo por arbo ke estas optimumigita por reakiro, kiu kompreneble, literumas kun I-E tiel ĝi estas trie. Sed tio estas la historio de la trie. 

Do trie estas tiu arbo-similaj datumoj strukturo kiel familio arbo kiuj fine kondutas tiel. Kaj tie ĉi estas ĝuste alia ekzemplo de amaso de fremdaj nomoj. Sed la demando nun ĉe mano estas kio havas ni gajnis enkondukante defendeble pli komplika datumstrukturo, kaj unu, sincere, kiu uzas multe da memoro. 

Ĉar kvankam, Nuntempe, mi estas nur uzante D's puntero kaj A kaj V kaj S kaj Ns, Mi malŝparante heck de multe da memoro. Sed kie mi pasigas unu rimedo, Mi emas ne gajni reen alia. Do se mi elspezi pli spaco, kio estas verŝajne la esperon? Ke mi elspezante malpli kio? Publiko: Malpli tempo. DAVID Malan: Epoko. Nun kial povus esti? Nu, kio estas la inserción tempo, en terminoj de granda a nun, de nomo kiel Daven aŭ Davenport aŭ David? Nu, Daven kvin paŝojn. Davenport estus naŭ ŝtupoj, tiel estus kelkaj paŝoj. David estus kvin paŝoj tiel. Do tiuj estas konkretaj nombroj, sed verŝajne ekzistas supera baro sur la longo de ies nomon. Kaj efektive, la problemo aroj de kvin specifo, Ni tuj proponos ke io tio estas 40-iom-neparaj signoj. 

Realisme, neniu havas senfine longa nomo tio estas, ke la longo de nomo aŭ la longeco de kordo ni povus havi iun la stato de strukturo estas defendeble kio? Ĝi estas konstanta. Rajto? Ĝi povus esti granda konstanta ŝatas 40-ion, sed estas konstanta. Kaj ĝi havas nenian dependecon kiom aliaj nomoj estas en tiu datumstrukturo. En aliaj vortoj, se mi volis nun enmeti Colton aŭ Gabriel aŭ Rob aŭ Zamyla aŭ Alison aŭ Belinda aŭ ajna aliaj nomoj de la dungitaro en ĉi datumoj strukturon, estas la rultempo havigo aliaj nomoj tuj estos tute impactado por kiel multaj aliaj elementoj estas en la datumstrukturo jam? Ĝi estas ne. Rajto? Ĉar ni efike uzi tiu multi-tavolaj hash tablo. Kaj la rula tempo de iu el tiuj operacioj dependas ne de la nombro de elementoj, kiuj estas en la datumstrukturo aŭ kiu eventuale iri esti en la datumstrukturo, sed sur la longeco de kion specife? 

La kordoj estas insertan, kio faras ke ĉi asimptote konstanto time-- granda O de unu. Kaj sincere, nur en la reala mondo, tiu signifas enmeto Daven nomo prenas kiel kvin paŝoj, aŭ Davenport naŭ paŝoj, aŭ Davido kvin paŝojn. Tio estas bela Darn malgrandaj kurado fojojn. Kaj ja, tio estas tre bona afero, precipe kiam tio ne dependas de la tuta nombro de elementoj en tie. Do kiel povas ni implementar ĉi speco de strukturo en kodo? Ĝi estas iom pli kompleksa, sed ankoraŭ estas nur apliko de bazaj konstruelementoj. Mi iras redifini ni nodo kiel sekvas: bool nomita word-- kaj ĉi povus nomi ion. Sed la bool reprezentas kion mi desegnis kiel ĉekon marko. Jes. Jen la fino de ĉeno en tiu datumstrukturo. 

Kaj, kompreneble, la nodo stelo tie estas referenco al infanoj. Kaj efektive, nur ŝatas familio arbo, vi konsiderus la nodoj kiuj pendis ekstere de la fundo de iu patro elemento esti infanoj. Kaj tial la infanoj tuj esti tabelo de 27, la 27-unu simple restante por apostrofo. Ni tuj ordigi de speciala kazo tio. Do vi povas havi iun nomoj kun apostrofoj. Eble eĉ streketo devus iri tien, sed vi vidi en p aro 5 ni nur zorgo pri literoj kaj apostrofoj. 

Kaj do kiel vi reprezentas la datumstrukturo mem? Kiel vi reprezentus la radiko de tiu trie, por tiel diri? Nu, simile kun ligillisto, vi bezonas puntero al la unua ero. Kun trie vi nur bezonas unu montrilon al la radiko de tiu trie. Kaj de tie povas hash vian vojon malsupren pli kaj pli profunden al ĉiu alia nodo en la strukturo. Do simple per ĉi tedaĵo Ni reprezentas ke struct. 

Nun Meanwhile-- Ho, demando. 

Publiko: Kio bool vorto? 

DAVID Malan: bool vorto nur tiun C enkarniĝo kion mi priskribis en tiu skatolo tie, kiam Mi komencis dividi ĉiu de la tabelo de elementoj en du pecojn. Unu estas puntero al la venonta vertico. La aliaj devas esti iu kiel ĉeko skatolo diri jes, ekzistas vorto Daven kiu finiĝas ĉi tie, ĉar ni ne volas, Nuntempe, Dave. 

Kvankam Dave tuj estos legitima vorton, li ne estas en la trie ankoraŭ. Kaj D estas ne unu vorton. Kaj D-A ne estas vorto aŭ nomo. Do la ĉekon markon indikas nur unufoje vi batita tiu nodo estas antaŭa vojo de karakteroj fakte ĉeno kiu vi enmetita. Do jen ĉio la bool tie faras por ni. 

Ajna alia demandojn tries? Yeah. 

Publiko: Kio estas la koincido? Kio, se vi havas Dave kaj Daven? DAVID Malan: Perfekta. Kio, se vi havas Dave kaj Daven? Do se ni enŝovu diru alnomo, por David-- Dave-- D-A-V-E? Tiu estas vere súper simpla. Do ni nur tuj prenos kvar paŝoj. D-A-V-E. Kaj kion mi havas por fari unufoje mi trafis ke kvara vertico? Nur tuj kontrolu. Ni estas jam bone iri. Farita. Kvar ŝtupoj. Konstanta tempo asimptote. Kaj nun ni indikis ke ambaŭ Dave kaj Daven estas kordoj en la strukturo. Do ne estas problemo. Kaj rimarki kiom la ĉeesto de Daven ne fari preni plu tempo aŭ malpli tempon por Dave kaj viceversa. 

Do kion ajn ni povas nun fari? Ni uzis tiun metaforon antaŭe de pletoj reprezenti ion. Sed rezultu ke stako de pletoj estas reale demonstrativo de alia abstrakta datumoj type-- altan nivelon datumstrukturo ke fine la tago estas nur kiel tabelo aŭ ligillisto aŭ ion pli sekulara. Sed ĝi estas pli interesa koncepta koncepto. Stako, kiel tiuj pletoj tie en Mather, ĝenerale nomiĝas nur that-- stako. 

Kaj en ĉi tiu tipo de datumstrukturo vi havas du operations-- Vi havas unu nomis puŝo por aldoni ion al la pilo, kiel meti alian pleto denove sur la supro de la stako. Kaj tiam elvenos, kio signifas ke preni la plejsupra pleto ekstere. Sed kio estas klavo sur stako estas ke ĝi estas atingis tiun scivolan karakterizaĵon. Kiel la manĝejo ŝablono estas reordigante la pletoj por la venonta manĝo, kio okazas al esti vera pri kiel studentoj interagi kun tiu datumstrukturo? Publiko: ili tuj pop unu ekstere. DAVID Malan: ili tuj pop unu malproksime, espereble la supro. Alie ĝi estas nur speco de stulta iri la tutan vojon al la fundo. Rajto? La datumstrukturo vere ne permesas vi ekpreni la malsupro pleto almenaŭ facile. Do tie estas tio scivolema posedaĵo al pilo ke la lasta ero en estas tuj estos la unua unu el. Kaj komputilaj sciencistoj nomas ĉi LIFO-- daŭri en, unua el. Kaj fakte ne havas interesajn aplikojn. Tio ne nepre tiel evidenta kiel iuj aliaj, sed ĝi povas ja esti utila, kaj ĝi povas efektive esti implementado en kelkaj malsamaj manieroj. 

Do, kaj fakte, lasu mi ne plonĝi en tiun. Ni faru tion anstataŭe. Ni rigardu, kiu estas preskaŭ la sama ideo, sed ĝi estas iom pli justan. Rajto? Se vi estas unu el tiuj fano boys aŭ knabinoj kiuj vere ŝatas Apple produktoj kaj vi vekiĝis je 3:00 AM vicigi en iu vendejo akiri la tre lasta iPhone, vi eble vosto supren kiel ĉi. 

Nun vosto estas tre intence nomita. Estas linio ĉar estas iuj justeco al ĝi. Rajto? Estus ia sucxis Se vi alvenis tie unue en la Apple Store sed vi estas efektive la ĉefundan pleto ĉar la Apple oficistoj tiam pop la lasta persono, kiu efektive havas en la linio. Do stakoj kaj vostoj, kvankam funkcie ili estas speco de la same-- estas nur tiu kolekto de rimedoj kiuj estas tuj kreski kaj shrink-- ekzistas tiu justeco aspekton al ĝi, almenaŭ en la reala mondo, kie la operacioj vin praktiki estas fundamente malsama. A stack-- vosto rather-- laŭdire havas du operacioj: n vosto kaj d vosto. Aŭ vi povas nomi ilin ajna kvanto de aĵoj. Sed vi simple volas kapti la nocio ke oni aldonas kaj estas finfine restante. 

Nun sub la kapuĉo, ambaŭ la pilo kaj vosto povus implementados kiel? Ni ne eniros en la kodo de ĉar la pli alta nivelo ideo estas ia pli evidenta. Mi volas diri, kion homoj faras? Se mi estas la unua persono en la Apple Stoki kaj tio estas la granda pordo, Vi scias, ke mi tuj staru tie. Kaj en la sekvanta persono tuj staru tie. Kaj en la sekvanta persono tuj staru tie. Do kio datumstrukturo pruntas al vosto? 

Publiko: A vosto. DAVID Malan: Bone, vosto. Certa. Kion alian? 

Publiko: Ligita listo. 

DAVID Malan: Ligita listo vi povus apliki. Kaj ligillisto estas bela ĉar tiam Ĝi povas kreski arbitre longajn kontraste por havi iu fiksita nombro homoj en la vendejo. Sed eble fiksa nombro de lokoj estas leĝa. Ĉar se ili nur havas kiel 20 iPhones en la unua tago, eble Ili nur bezonas tabelo de amplekso 20 reprezenti ke vosto, kiu nur diri nun kiam ni komencos parolante pri tiuj altaj nivelo problemoj, vi povas funkciigi ĝin en ajna nombro de manieroj. Kaj estas verŝajne nur tuj esti komerco off en spaco kaj tempo aŭ nur en via propra kodo komplekseco. 

Kio pri pilo? Nu, stako, ni vidis tro povus esti simple tiuj pletoj. Kaj vi povus implementar ĉi tabelo. Sed en iu momento, se vi uzas tabelo, kio okazos al la pletojn vi provas sufoki? Bone. Vi nur tuj povos iri tiom alte. Kaj mi kredas en Mather ili estas efektive recessed en tiu malfermo. Do ja, estas preskaŭ kiel Mather estas uzanta tabelo de fiksa grandeco, ĉar vi nur povas ĝustigis tiel multaj pletoj en tiu malfermo en la muro malsupre popola genuoj. Kaj tial eble dirita esti tabelo, sed ni certe povus implementar ke pli ĝenerale kun ligitaj listo. 

Nu, kio pri alia datumstrukturo? Lasu min eltiri supren unu alia vida tie. Io kiel kio pri tiu ĉi ankaŭ? Kial povus gxin utile havi ne io kiel fantazio kiel trie, kion ni vidis havis tiujn tre larĝa nodoj, ĉiu de kiuj estas en tabelo? Sed kio se ni faros ion pli simple, kiel malnova lernejo genealogia arbo, ĉiu el kies verticoj tie Estas simple stoki numero. Anstataŭ nomo aŭ posteulo Estas simple stoki nombro kiel ĉi. 

Nu, la ĵargonon ni uzas en datumstrukturoj estas ambaŭ tries kaj arboj, kie trie, denove, estas nur unu kies nodoj estas arrays, Ankoraŭ kion vi eble uzi de grado lernejo kiam vi faris familio tree-- folioj kaj la radiko de la arbo kaj infanoj de la patro kaj gefratoj largxo. Kaj ni povus apliki al arbo, ekzemple, kiel simple kiel tiu. Arbo, se kiel nodo, unu el tiuj rondoj kiuj havas numeron, tio ne tuj havos unu montrilo, sed du. Kaj kiam vi aldonas dua montrilo, vi efektive povas nun fari speco de dudimensiaj datumoj strukturoj en memoro. Multe kiel du-dimensia tabelo, vi povas havi specon de du-dimensia ligitaj lertaj sed aĵoj kiuj sekvas mastron kie ne estas cikloj. Estas vere arbon kun unu avo vojon tien kaj tiam kelkaj gepatroj kaj infanoj kaj nepoj kaj pranepoj. ks. 

Sed kio estas vere neta pri tiu tro, nur turmentus vin per iom da kodo, Memoru rikuro de momenton dorso, per kiu vi skribas funkcio kiu nomas sin. Tiu estas bela ŝanco implementar ion kiel rikuro, ĉar konsideras ĉi. 

Tio estas arbo. Kaj mi estis iom anal kun kiel Mi metis la entjeroj eksteren. Tiel ke ĝi havas specialan name-- duuma serĉarbo. Nun ni aŭdis pri duumaj esplori, sed ĉu eblas labori malantaŭen de tiu afero estas nomata? Kio estas la mastro de kiel mi insertado la entjerojn en ĉi arbo? Ĝi ne estas arbitra. Ekzistas iuj ŝablono. Yeah. 

Publiko: plej malgranda sur la maldekstra. 

DAVID Malan: Jes. Malgrandaj estas maldekstre. Pli grandajn estas dekstre. Tia ke vera aserto estas patro estas pli granda ol lia maldekstra infano, sed malpli ol lia dekstra infano. Kaj tio sola estas eĉ rekursiaj parola difino ĉar vi povas peti ke saman logikon por ĉiu nodo kaj nur fundoj ekster, bazo kazo se vi volas, kiam vi batas unu el la folioj, tiel diri, kie permeso ne havas infanojn for. 

Nun kiel eble vi trovos la numeron 44? Vi komencu je la radiko kaj diru, hm. 55 ne estas 44 tiel Mi volas iri dekstra aŭ mi volas iri forlasis? Nu, evidente vi volas iri maldekstren. Kaj tiel estas ĝuste kiel la telefono libro ekzemple en duuma serĉo pli ĝenerale. Sed ni implementarla nun iom pli dinamike ol tabelo povus permesi. Kaj fakte, se vi volas rigardi en la kodo, unuavide certa. Ĝi aspektas kiel tuta fasko da linioj. Sed estas bele simpla. Se vi volas implementar funkcio nomita serĉo kies celo en la vivo estas serĉi valoro kiel n, entjero, kaj vi pasis en unu pointer-- puntero al la nodo de la radikoj, pli ĝuste, de tiu arbo de kiu Vi povas aliri ĉion alian, rimarki kiom juste Vi povas apliki la logikon. Se arbo estas nula, Evidente ĝi ne estas tie. Ni simple reveni falsaj. Rajto? Se vi transdonos ŝin nenion, nenio estas tie. 

Alie, se n estas malpli ol arbo sagon n-- nun arrow n, memoras ni enkondukis súper brevemente la alia tago, kaj tio nur signifas de-referenco la puntero kaj rigardi la kampo nomata n. Do ĝi signifas iri tie kaj rigardi la kampo nomata n. Do se n, la valoro vi donis, estas malpli ol la valoro en la arboj entjero, Kien vi volas iri? Maldekstren. 

Do rimarki la rikuro. Mi returning-- ne veras. Ne falsaj. Mi revenos ajn respondon Estas de alvoko al mi, pasante n denove, kio estas redunda, sed kio estas iomete malsama nun? Kiel mi fari la problemo malgrandaj? Mi pasis en la dua argumenton, ne la radiko de la arbo, sed la maldekstra infano en tiu kazo. Do mi pasis en la maldekstra infano. 

Dume, se n estas pli granda ol la nodo Mi aktuale rigardis, Mi serĉas la dekstra flanko. Alie, se la arbo ne estas nula, kaj se la elemento ne maldekstren kaj ne estas por la dekstra, kio estas mirinde la kazo? Ni fakte trovis la nodo en demando, do ni revenos vera. 

Do ni nur skrapis la surfacon nun kelkaj el tiuj datumstrukturoj. En problemo starigis kvin Vi esplori tiujn ankoraŭ plu, kaj vi estos donita vian dezajno elekto de kiel iri pri tio. Kion mi volas konkludi pri Estas nur 30 duaj teaser de kio atendas venontan semajnon kaj pretere. 

Kiel ni begin-- dankeme vi eble think-- nian transiron malrapide el la mondo de C kaj malsupra nivelo efektivigo detaloj al mondo en kiu ni povas preni por koncedas ke iu alia havas finfine implementado tiuj datumoj strukturoj por ni, kaj ni komencas kompreni la reala mondo signifas efektivigo TTT-bazita programoj kaj retejojn pli ĝenerale kaj ankaŭ la tre sekureco implicoj kiujn ni nur komencis skrapi la surfaco de. Jen kio atendas nin en la tempo estonta. 

[VIDEO Playback] 

-li Venis kun mesaĝo, per protokolo tutan sian. Li venis al mondo de kruela firewalls, uncaring routers, kaj danĝeroj multe pli malbona ol la morto. Li estas rapida. Li estas forta. Li estas TCP / IP, kaj li havas vian adreson. "Soldatoj de la Reto". [END VIDEO Playback] DAVID Malan: Coming venontan semajnon. Ni vidos vin poste. [VIDEO Playback] -kaj Nun, "Deep Pensoj" per Daven Farnham. -David Ĉiam startas prelegoj kun, "Bone." Kial ne, "Jen la solvo al tiu semajno problemo aro " aŭ "Ni donas al vi ĉiuj A?" [Ridante] [END VIDEO Playback]