Doug LLOYD: Taigi CS50, mes, kuriems skirtingų duomenų struktūrų daug, tiesa? Mes matėme masyvus ir susiję sąrašus, maišos lentelės, ir nutraukė, vamzdžiai ir eilių. Mes taip pat sužinoti šiek tiek apie medžių ir krūvos, bet tikrai jie visi tiesiog galų gale yra Variacijos tema. Ten tikrai yra šie rūšies keturių pagrindinių idėjų kad viskas dar gali skliautais. Matricos, susijusios sąrašus, maišos lentelės, ir nutraukė. Ir kaip jau sakiau, Yra variantai ant jų, tačiau tai yra gana daug vyksta apibendrinti viskas mes ketiname kalbėti apie šioje klasėje, kalbant apie C Bet kaip tai padaryti visa tai priemonė aukštyn, tiesa? Mes kalbėjome apie privalumus ir trūkumus vienas atskirose video apie juos, bet ten yra numeriais gauti mesti aplink. Yra bendra aikštelė mintys vis mesti aplink. Pabandykime ir įtvirtinti jį į tik vieną vietą. Leiskite pasverti privalumus prieš kad trūkumai, ir apsvarstyti kurios duomenų struktūra gali būti teisingas duomenys struktūra jūsų konkrečioje situacijoje, bet kokios rūšies duomenų esate saugoti. Jūs nebūtinai visada reikia naudoti super greitai įterpimo, ištrynimą, ir peržvalgos iš TRIE jei jūs tikrai nerūpi įterpiant ir trynimas per daug. Jei jums reikia tik greitai atsitiktinis prieiga, gal masyvas yra geriau. Taigi leiskite distiliuoti, kad. Pakalbėkime apie kiekvieną iš keturių Pagrindiniai rūšių duomenų struktūrų kad mes kalbėjome apie, ir tik pamatyti, kai jie gali būti gera, ir kai jie gali būti ne taip gerai. Taigi pradėkime su matricomis. Taigi įkišimo, kad tipo blogai. 

Įterpimas į masyvo pabaigos yra gerai, jei mes pastatų masyvą, kaip mes einame. Bet jei mums reikia įterpti elementai į centrą, prisiminkite įterpimą Rūšiuoti, yra daug perkelia kad tilptų elementas ten. Ir todėl, jei mes ketiname įrašyti kur bet masyvo pabaigos, tai tikriausiai ne toks didelis. 

Be to, išbraukta, jei mes išbraukiant iš masyvo pabaigos, tikriausiai taip pat nėra toks didelis, jei mes nenorime palikti tuščių tarpų, kuris paprastai darome ne. Mes norime, kad pašalinti elementą, tada rūšiuoti, kad jis aptemptas dar kartą. Ir taip išbraukiant elementus iš masyvas, taip pat nėra toks didelis. 

Ieškoti, nors yra didelis. Mes turime laisvą prieigą, pastovus laikas peržvalgos. Mes tiesiog pasakyti septyni, ir mes einame masyvo perkėlimo septyni. Mes sakome, 20, su eikite į masyvo perkėlimas 20. Mes neturime kartoti visoje. Tai gana gerai. 

Masyvai taip pat yra gana lengva rūšiuoti. Kiekvieną kartą, kai mes kalbėjome apie rūšiavimą algoritmas, kaip antai atrankos rūšiuoti, įterpimo rūšiuoti, burbulas rūšiuoti, sujungti Rūšiuoti mes visada naudojamas matricas tai padaryti, nes matricos yra gana lengva rūšiuoti, santykinis į duomenų struktūrų mes matėme iki šiol. 

Jie taip pat yra santykinai mažas. Yra ne daug papildomos vietos daug. Jūs tiesiog atidėta tiksliai taip, kaip daug kaip jums reikia turėti savo duomenis, ir tai gana daug. Taigi jie gana mažas ir efektyvus, kad tokiu būdu. Bet kita vertus, nors, yra tai, kad jie yra fiksuotas dydžio. Turime pripažinti, kaip tiksliai didelis, mes norime, kad mūsų masyvas turi būti, ir mes tik gauti vieną kadrą į jį. Mes negalime augti ir trauktis. 

Jei mes turime augti arba mažėti, mes reikia pripažinti visiškai naują masyvą, nukopijuoti visus iš elementų pirmasis masyvo į antrąjį masyvo. Ir jei mes apsiskaičiavo, kad laikas, mes turime padaryti jį dar kartą. Ne toks didelis. Taigi matricas nesuteikia mums lanksčiai turėti kintamas skaičių elementų. 

Su susietą sąrašą įterpimas yra gana lengva. Mes tiesiog smeigtuko ant priekio. Išbraukus taip pat yra gana lengva. Turime rasti elementus. Tai apima tam tikrą paiešką. 

Bet kai jūs radote elementą jūs ieškote, viskas, ką jums reikia padaryti, yra pakeisti žymiklį, galbūt dvi, jei turite susijusiantrosios list-- dvigubai susiję sąrašas rather-- ir tada galite tiesiog nemokamai mazgas. Jūs neturite pereiti viskas aplink. Jūs tiesiog pakeisti dvi rodykles, taip, kad gana greitai. 

Lookup yra blogai, nors, tiesa? Kad galėtume rasti elementas, susietą sąrašą atskirai arba dvigubai susiję, turime linijinis ieškoti ją. Mes turime pradėti pradžioje ir pereiti prie pabaigos, arba pradėti pabaigoje manevrų į pradžią. Neturime laisvą prieigą nebėra. Taigi, jei mes darome daug ieškojimų, gal susijusiantrosios sąrašas nėra visai taip gerai mums. 

Jie taip pat labai sunku rūšiuoti, tiesa? Vienintelis būdas galite tikrai rūšiuoti susietą sąrašą yra rūšiuoti ją, kaip jūs statyti ją. Bet jei jūs rūšiuoti ją kaip jus statyti ją, jūs nebėra priėmimo greitai intarpais nebėra. Jūs neprisijungęs tik sujungdamas viskas ant priekio. Turite rasti reikiamoje vietoje įdėti ją, ir tada jūsų įterpimo tampa tik apie taip blogai kaip įterpti į masyvą. Taigi, susijusios sąrašai nėra toks didelis, rūšiavimo duomenis. 

Jie taip pat yra gana mažas, dydis-protingas. Dvigubai susiję sąrašą šiek tiek didesnis nei pavieniui, susijusių sąrašus, kuris yra šiek tiek didesnis nei masyvus, tačiau tai nėra didžiulis iššvaistytos erdvėje. Taigi, jei erdvė yra priemoka, bet ne tikrai intensyvus priemokos, tai gali būti tinkamas būdas eiti. 

Hash lentelės. Įterpimas į maišos lentelė yra gana paprasta. Tai dviejų etapų procesas. Pirmiausia, mes turime paleisti mūsų duomenis per maišos funkcija gauti maišos kodą, ir tada mes įdėti elementą į maišos lentelės tuo maišos kodo vietą. 

Ištrynimą, panašus į susijusio sąrašą yra lengva, kai jums rasti elementą. Jūs turite jį rasti, pirma, bet tada, kai jūs jį pašalinti, jums tiesiog reikia keistis iš rodyklės pora, jei jūs naudojate atskirą Grupavimo. Jei naudojate zondavimo, arba, jei nesate naudojant Grupavimo ne visi Jūsų maišos lentelė, išbraukta iš tikrųjų labai paprasta. Viskas, ką jums reikia padaryti, tai maišos duomenų, ir tada pereiti prie tos vietos. Ir jei jūs neturite turite kokių nors susidūrimų, Galėsite labai greitai pašalinti. 

Dabar lookup yra, kur viskas gauti šiek tiek sudėtingesnis. Tai vidutiniškai geriau nei susijusių sąrašus. Jei naudojate Grupavimo, jūs vis dar turite susietą sąrašą o tai reiškia, jūs vis dar turite Paieška nenaudai susietą sąrašą. Bet kadangi jūs vartojate savo susietos sąrašą ir padalijant jį per 100 ar 1000 arba n elementų savo maišos lentelė, jūs susiję sąrašai yra visi vienas n-tasis dydžio. Jie visi žymiai mažesnis. Jūs N susiję sąrašus vietoj vieno susijusio sąrašą dydžio n. 

Ir todėl tai realaus pasaulio pastovus faktorius, kurį mes paprastai nereikia kalbėti apie laiko sudėtingumą, ar iš tikrųjų padaryti skirtumą čia. Taigi lookup yra dar linijinis ieškoti jei jūs naudojate Grupavimo, bet sąrašo ilgis esate ieškant per yra labai, labai trumpas, palyginus. Vėlgi, jei rūšiavimas yra jūsų tikslas čia, maišos lentelės tikriausiai nėra tinkamas būdas eiti. Tiesiog naudoti masyvą, jei rūšiavimo yra tikrai svarbu jums. 

Ir jie gali paleisti dydžio gamą. Sunku pasakyti, ar maišos lentelė mažas ar didelis, nes tai tikrai priklauso nuo kaip didelis jūsų maišos lentelė. Jei tik bus saugoti Penki elementai Jūsų maišos lentelė, ir jūs turite maišos lentelę su 10.000 elementų jį, jūs tikriausiai eikvoti daug vietos. Kontrastas yra taip pat galite labai kompaktiškas maišos lenteles, bet mažesnis jūsų maišos lentelės gauna, ilgiau kiekviena iš šių susijusių sąrašą pasireiškia. Ir taip ten tikrai ne būdas apibrėžti būtent tas maišos lentelės dydis, bet tai tikriausiai saugus pasakyti, kad tai apskritai bus didesnis nei susijusi Sąrašas saugoti tuos pačius duomenis, bet mažesnis nei TRIE. 

Ir nutraukė yra ketvirtas šių struktūrų kad mes jau kalbame apie. Įdėjimas į TRIE yra sudėtinga. Yra daug dinamiškas daug atminties paskirstymas, ypač pradžioje, kaip jūs pradedate statyti. Bet tai pastovus laikas. Tai tik žmogiškasis faktorius čia, kad daro tai sudėtinga. Atsižvelgdama susidurti null žymeklį, malloc Erdvė, ten, galbūt malloc vietos iš ten vėl. Bauginimo veiksnį Rūšiuoti rodykles į dinaminės atminties paskirstymo yra kliūtis išvalyti. Bet kai jūs vartų, įterpimo faktiškai yra gana paprasta, ir tai tikrai yra pastovus laikas. 

Išbraukus yra paprasta. Viskas, ką jums reikia padaryti, tai eikite žemyn pora patarimų ir nemokama mazgas, kad gana gera. Lookup yra taip pat gana greitai. Jis grindžiamas tik ilgis jūsų duomenis. Taigi, jei visi jūsų duomenis penki charakterio įsipareigojimų, Pavyzdžiui, jūs saugoti penkis charakterio įsipareigojimų Jūsų TRIE, tai trunka tik Penki žingsniai rasti tai, ko ieškote. Penkios yra tik pastovus veiksnys, todėl vėl, įterpimo, išbraukta, ir peržvalgos Čia yra visi pastovus laikas, efektyviai. 

Kitas dalykas yra tai, kad jūsų Trie yra realiai natūra jau rūšiuojamos, tiesa? Pagal tai, kaip mes įterpimą elementai, eidami raštą raidė klavišą arba skaitmenį rakto, Paprastai, jūsų Trie baigiasi yra rūšies rūšiuojami kaip jūs statyti. Jis tikrai ne daro prasmės galvoti apie rūšiavimas tokiu pačiu būdu mes galvojame apie Ji su matricos, ar susijusių sąrašus, arba maišos lentelės. Bet tam tikra prasme, jūsų Trie yra rūšiuojami kaip jūs einate. 

Neigiama, žinoma, yra tai, kad Trie greitai tampa didžiulis. Iš kiekvienos jungties taško, jums gali have-- jei jūsų raktas susideda iš skaitmenų, jūs turite 10 kitų vietų, kur galite eiti, kuri reiškia, kad kiekvienas mazgas pateikiama informacija apie duomenų, kuriuos norite saugoti tuo mazgu, plius 10 patarimų. Kuri, CS50 IDE, yra 80 baitų. Taigi, tai ne mažiau kaip 80 baitų kiekvienas mazgas, kad jums sukurti, ir tai net ne skaičiuoti duomenis. Ir jei jūsų mazgai raidės vietoj skaičių, dabar jūs turite 26 patarimų iš kiekvienos vietos. Ir 26 kartų 8 turbūt 200 baitų, ar kažkas panašaus. Ir jūs turite kapitalą ir lowercase-- galite pamatyti, kur aš einu su tuo, ar ne? Jūsų mazgai gali gauti tikrai didelis, ir todėl Trie pati apskritai gali gauti tikrai didelis, taip pat. Taigi, jei erdvė yra ne aukšto įmoka į savo sistemą, Trie gali būti tinkamas būdas eiti, nors kiti jo nauda ateiti į žaidimą. Aš Doug Lloyd. Tai CS50.