DOUG LLOYD: Do en CS50, ni kovris multaj diversaj datumstrukturoj, dekstra? Ni vidis arrays, kaj ligitaj listoj, kaj hash tabloj, kaj klopodoj, stakoj kaj atendovicoj. Ni ankaŭ lerni iom pri arboj kaj amasoj, sed vere ili ĉiuj ĵus fini estante variadoj sur temo. Tie vere estas jenaj speco de kvar bazaj ideoj ke io alia povas bolas malsupren al. Arrays, ligitaj listoj, hash tabloj, kaj provoj. Kaj kiel mi diris, estas varioj sur ili, sed tio estas bela multe tuj resumos ĉio ni tuj paroli proksimume en ĉi tiu klaso en terminoj de C. Sed kiel faras cxi cxiuj mezuron supren, dekstra? Ni jam parolis pri la avantaĝoj kaj contras de ĉiu en apartajn videojn sur ili, sed ekzistas multe de nombroj Akiranta ĵetita ĉirkaŭ. Ekzistas multe de ĝenerala pensoj akiranta ĵetita ĉirkaŭ. Ni provu kaj solidigi ĝin nur unu loko. Ni pezi la pros kontraŭ la contras, kaj konsideri kiu datumstrukturo eble estos la dekstra datumoj strukturo por via aparta situacio, ajn speco de datumo vi stokante. Vi ne nepre ĉiam bezonas uzi la super rapida inserción, forigoj, kaj lookup de trie se vi vere ne zorgas pri enmeto kaj viŝante tro. Se vi bezonas nur rapide hazarda aliro, eble tabelo estas pli bone. Do ni distili tio. Ni parolu pri ĉiu el la kvar gravaj specoj de datumstrukturoj ke ni parolis pri, kaj nur vidas kiam povus esti bona, kaj kiam ili ne povus esti tiel bona. Do ni komencu per tabeloj. Do inserción, jen speco de malbona. 

Inserción fine de tabelo estas OK, se ni konstruas tabelo kiel ni iru. Sed se ni bezonas enmeti elementoj en la mezo, pensas reen al inserción speco, ekzistas multe el sxangxigxantaj konveni ero en tie. Kaj do se ni iras por enmeti ie sed la fino de tabelo, ke estas probable ne tiom granda. 

Simile, forigoj, krom se ni estas forviŝo de la fino de tabelo, Estas probable ankaŭ ne tiom granda se ni ne volas lasi malplenaj interspacoj, Kiu kutime ni ne faras. Ni volas forigi elementon, kaj tiam ia fari ĝin komforta denove. Kaj tiel viŝante elementojn de tabelo, ankaŭ ne tiom granda. 

Lookup, tamen, estas granda. Ni havas aliro aleatorio, konstanta tempo lookup. Ni simple diru sep, kaj ni iru al tabelo delokadoj sep. Ni diru 20, kun go al tabelo delokadoj 20. Ni ne devas persisti trans. Tio estas sufiĉe bona. 

Arrays ankaŭ relative facile ordigi. Ĉiufoje ni parolis pri ordigado algoritmo, kiel selektado speco, inserción varo, bobelo varo, kunfandi varon, ni ĉiam uzis arrays fari ĝin, ĉar tabeloj estas sufiĉe facila por varon, relativa al la datumstrukturoj ni vidis ĝis nun. 

Ili estas ankaŭ relative malgranda. Ekzistas ne multe da ekstra spaco. Vi nur flankenmetis ĝuste tiel kiel vi devas teni vian datumon, kaj tio estas sufiĉe multe ĝin. Do ili estas belaj malgrandaj kaj efikaj en tiu vojo. Sed alia malavantaĝo, kvankam, estas ke ili estas fiksitaj en grandeco. Ni devas deklari precize kiel big ni volas nian tabelo por esti, kaj ni nur akiras unu ŝancon al ĝi. Ni ne povas kreski kaj ŝrumpi ĝin. 

Se ni bezonas kreski aŭ ŝrumpi ĝin, ni bezonas deklari tute nova tabelo, kopii ĉiujn la elementoj de la unua tabelo en la dua tabelo. Kaj se ni miskalkulis ke tempo, ni devas fari ĝin denove. Ne tiel granda. Do arrays ne donas al ni la fleksebleco havi variablo nombroj de elementoj. 

Kun ligillisto, inserción estas sufiĉe facila. Ni nur najlu sur la fronto. Forigo estas ankaŭ sufiĉe facila. Ni devas trovi la elementojn. Kiuj implikas iun serĉadon. 

Sed unufoje vi jam trovis la elementon vi estas serĉanta, ĉiuj vi bezonas fari estas ŝanĝi puntero, eble du se vi havas kunligita list-- duoble ligillisto, rather-- kaj tiam vi povas simple liberigi la nodo. Vi ne devas ŝanĝi ĉio ĉirkaŭe. Vi nur ŝanĝi du punteros, tiel ke estas sufiĉe rapida. 

Lookup estas malbona kvankam, dekstra? En ordo por ni trovi elemento en ligillisto, ĉu unuope aŭ duoble ligitaj, ni havos linear serĉu ĝin. Ni devas komenci je la komenco kaj movi la fino, aŭ komenci fine movo al la komenco. Ni ne havas hazarda aliro anymore. Do se ni faras Multa traserĉado, eble ligillisto ne tre tiel bona por ni. 

Ili estas ankaŭ vere malfacile ordigi, ĉu ne? La sola maniero vi povas vere ordigi ligillisto estas ordigi ĝin kiel vi konstrui ĝin. Sed se vi ordigi ĝin kiel vi konstrui ĝin, vi ne plu farante rapidajn inserciones anymore. Vi ne nur tacking aferojn sur la fronto. Vi devas trovi la dekstra loko por meti ĝin, kaj tiam via inserción iĝas proksimume tiel malbona kiel enmeto en tabelo. Do ligitaj listoj ne estas tiel granda por ordigado de datumoj. 

Ili estas ankaŭ belaj malgrandaj, grandeco-saĝa. Duoble ligita listo iomete granda ol unuope ligitaj listoj, kiuj estas iomete pli granda ol arrays, sed ĝi ne estas grandega kvanto de malŝparis spaco. Do se spaco estas ĉe premium, sed Ne vere intensa premio, ĉi povus esti la ĝusta vojo por iri. 

Hash tabloj. Inserción en hash tablo estas sufiĉe simpla. Ĝi estas du-paŝa procezo. Unue ni devas kuri nia datumoj tra hash funkcio akiri hash kodo, kaj tiam ni enŝovu la elemento en la hash tablo en tiu hash kodo situon. 

Forigo, simila al ligillisto, Facilas iam vi trovos la elemento. Vi devas trovi ĝin unue, sed tiam, kiam vi forigas ĝin, vi nur bezonos interŝanĝi kelkaj punteros, se vi uzas apartan sinsekvon. Se vi uzas sondado, aŭ se vi ne estas uzante ĉenante tute en via hash tablo, forigo estas efektive vere facila. Ĉiuj vi devas fari estas hash la datumoj, kaj tiam iru al tiu loko. Kaj supozante vi faras ne havas koliziojn, vi povos forviŝi tre rapide. 

Nun, lookup estas kie aferoj ricevas iom pli komplika. Ĝi estas averaĝe pli bona ol ligitaj listoj. Se vi uzas sinsekvon, vi ankoraŭ havas ligillisto, kio signifas ke vi ankoraŭ havas la serĉo malutilo ligillisto. Sed ĉar vi prenas vian ligitaj lerta kaj disfendante ĝin super 100 aŭ 1,000 aŭ n elementoj en via hash tablo, vi estas ligitaj listoj cxiuj estas unu na la grandeco. Ili ĉiuj estas substance pli malgranda. Vi n ligitaj listoj anstataŭe de unu ligillisto de amplekso n. 

Kaj tiel ĉi reala mondo konstanta faktoro, kiun ni ĝenerale Ne parolu pri ĝustatempe komplekseco, ĝi faras efektive fari diferencon cxi tie. Do lookup estas ankoraŭ lineara serĉu, se vi uzas sinsekvon, sed la longo de la listo vi trasercxante estas tre, tre mallonga por komparo. Denove, se ordigado estas via celo tie, hash tablo la probable ne la ĝusta vojo por iri. Simple uzu tabelo se ordiga estas vere grava por vi. 

Kaj ili povas kuri la gamut de grandeco. Estas malfacile diri, ĉu hash tablo estas malgranda aŭ granda, ĉar vere dependas kiom granda viajn hash tablo estas. Se vi nur tuj estos stokante kvin elementoj en via hash tablo, kaj vi havas hash tablo kun 10.000 elementoj en ĝi, vi probable malŝparas multe da spaco. Kontrasto esti vi povas ankaŭ havas tre kompakta hash tabloj, sed la malgrandaj viajn hash tablo ricevas, la longaj ĉiu de tiuj ligitaj lertaj ricevas. Kaj tiel ekzistas vere neniu maniero por difini ĝuste la grandeco de hash tablo, sed ĝi estas probable sekura diri ke estas ĝenerale tuj estos granda ol kunligita listo stokante la samaj datumoj, sed pli malgranda ol trie. 

Kaj klopodoj estas la kvara de tiuj strukturoj ke ni parolis pri. Enmeto en trie estas kompleksa. Ekzistas multe de dinamika memoro atribuo, speciale komence, kiel vi komencas konstrui. Sed estas konstanta tempo. Ĝi estas nur la homa elemento tie kiu faras ĝin malfacila. Devante renkontas nula puntero, malloc spaco, iri tien, eble malloc spaco de tie denove. La varo de timigado faktoro de punteros en dinamika memoro atribuo estas la hurdo malbari. Sed iam vi malbaris ĝin, inserción fakte venas tute simpla, kaj gxi certe estas konstanta tempo. 

Forigo estas facila. Ĉiuj vi devas fari estas navigi malsupren kelkaj montriloj kaj libera la nodo, tiel ke estas sufiĉe bonaj. Lookup estas ankaŭ sufiĉe rapida. Ĝi estas nur bazita sur la longo de viaj datumoj. Do se ĉiuj viaj datumoj estas kvin karaktero ŝnuroj, ekzemple, vi stokante kvin karaktero ŝnuroj en via trie, ĝi nur prenas kvin paŝoj al trovi kion vi serĉas. Kvin estas nur konstanta faktoro, tiel denove, inserción, forigo, kaj lookup tie ĉiuj estas konstanta tempo, efike. 

Alia afero estas ke via trie estas fakte speco de jam ordo, ĉu ne? En virto de kiel ni estas enmeto elementoj, irante letero de letero de la klavo, aŭ cifero de cifero de la ŝlosilo, tipe, via trie finas esti ia ordo kiel vi konstruos ĝin. Fakte ne faras sentita pensi pri ordigado en la sama maniero kiel ni pensas pri ĝi kun sensilo, aŭ ligitaj listoj, aŭ hash tabloj. Sed iusence, via trie estas ordo kiel vi iros. 

La malavantaĝo, kompreneble, estas ke trie rapide iĝas grandega. El ĉiu junton punkto, vi eble have-- se via ŝlosilo konsistas de ciferoj, vi havos 10 aliaj lokoj vi povas iri, kiu signifas ke ĉiu nodo enhavas informon pri la datumojn vi volas konservi en tiu nodo, plus 10 punteros. Kiu, sur CS50 IDE, estas 80 bajtoj. Do estas almenaŭ 80 bajtoj por ĉiu nodo kiun vi kreas, kaj tio eĉ ne kalkulante datumoj. Kaj se via nodoj estas literojn anstataŭ ciferoj, nun vi havas 26 punteros de ĉiu loko. Kaj 26 fojojn 8 estas probable 200 bajtoj, aŭ io simila. Kaj vi havas ĉefurbo kaj lowercase-- vi povas vidi kie mi iros kun tiu, ĉu ne? Via nodoj povas akiri vere granda, kaj tiel la trie mem, entute, povas akiri vere granda, tro. Do se spaco estas ĉe alta premio en via sistemo, trie eble ne estas la dekstra maniero iri, eĉ se liaj aliaj profitoj veni en ludon. Mi Doug Lloyd. Jen CS50.