Doug LLOYD: Tātad CS50, mēs esam uz daudz dažādu datu struktūras, labi? Mēs esam redzējuši bloki, un saistīta saraksti, un hash tabulas, un cenšas, skursteņi un rindas. Mēs arī uzzināt nedaudz par kokiem un kaudzes, bet tiešām tie visi tikai beigās galā ir variācijas par tēmu. Tur tiešām ir šie veida četrām pamatidejām ka viss pārējais var vārīties uz leju, lai. Bloki, kas saistīti saraksti, hash tabulas, un mēģina. Un kā jau teicu, tur ir variācijas par tiem, bet tas ir diezgan daudz kas notiek apkopot viss, ko mēs ejam, lai runātu par šajā klasē ziņā C. Bet kā tie visi pasākums up, labi? Mēs esam runājuši par plusi un mīnusi Katras atsevišķās video par to, bet tur ir daudz skaitļu kļūst izmet apkārt. Tur ir daudz vispārējs domas kļūst izmet apkārt. Pamēģināsim un konsolidēt to tikai vienā vietā. Pieņemsim nosver plusi pret mīnusi, un apsvērt kas datu struktūra varētu būt pareizā dati struktūra jūsu konkrēto situāciju, jebkāda veida datu jūs glabāšanai. Jums nav obligāti vienmēr vajag izmantot super ātru ievietošanas, dzēšanu, un lookup par TRIE ja jums tiešām nerūp ievietošanas un dzēšana pārāk daudz. Ja jums ir nepieciešams tikai ātri izlases Pieeja, varbūt masīvs ir labāka. Tātad, pieņemsim, ka dedzināt. Parunāsim par katru no četriem galvenie veidi datu struktūras ka mēs esam runājuši par, un tikai redzēt, kad tie varētu būt labs, un kad tie varētu nebūt tik labi. Tāpēc sāksim ar masīviem. Tātad ievietošanas, tas ir sava veida slikti. 

Ievietošana beigās masīva ir OK, ja mēs ēkā masīvs, kā mums iet. Bet, ja mums ir nepieciešams, lai ievietotu elementi uz centru, domāju, ka atpakaļ uz ievietošanas kārtot, tur ir daudz no novirzot lai ietilptu elements tur. Un tāpēc, ja mēs ejam, lai ievietotu jebkur bet gala no masīva, tas ir iespējams, nav tik liels. 

Tāpat, dzēšanu, ja vien mēs esam svītrot no beigām masīva, Ir iespējams arī nav tik liels, ja mēs negribam atstāt tukšus nepilnības, kas parasti mums nav. Mēs vēlamies, lai noņemtu elementu, un tad veida padara akurāti vēlreiz. Un tā dzēšot elementus no masīvs, arī ne tik liels. 

Lookup, tomēr ir liels. Mums ir izlases piekļūt, konstante laiks lookup. Mēs vienkārši sakām septiņiem, un mēs ejam ar masīvu pārvietošanu septiņiem. Mēs sakām 20, ar iet uz masīvs pārvietošana 20. Mums nav atkārtot pāri. Tas ir diezgan labs. 

Masīvi ir arī salīdzinoši viegli sakārtot. Katru reizi, kad mēs runājām par šķirošanu algoritmu, piemēram, atlases veida, ievietošanas kārtot, burbulis kārtot, apvienot kārtot, mēs vienmēr izmanto blokus, lai to izdarītu, jo masīvi ir diezgan viegli kārtot, salīdzinot ar datu struktūru mēs esam redzējuši līdz šim. 

Viņi arī salīdzinoši neliels. Tur nav daudz papildu telpas. Jūs vienkārši atcelt tieši tik daudz, kā jums ir nepieciešams, lai noturētu savus datus, un tas ir diezgan daudz to. Tātad viņi diezgan mazs un efektīvu šādā veidā. Bet vēl viens negatīvie, lai gan, ir tā, ka tie ir noteikti lieluma. Mums ir jādeklarē, kā tieši big mēs vēlamies, lai mūsu masīvs būt, un mēs tikai iegūt vienu shot pie tā. Mēs nevaram augt un sarauties to. 

Ja mums ir nepieciešams, lai augt vai sarukt, mēs nepieciešams deklarēt pilnīgi jaunu masīvu, kopēt visu elementu pirmais masīvs uz otro masīvs. Un, ja mēs nepareizi, ka laiks, mums ir nepieciešams to darīt atkal. Ne tik liels. Tātad bloki nedod mums elastību ir mainīgas skaitu elementu. 

Ar saistītajā sarakstā, ievietošana ir diezgan viegli. Mēs tikko sadiegšana uz priekšu. Dzēšana ir arī diezgan viegli. Mums ir jāatrod elementus. Tas ietver daži meklē. 

Bet tad, kad jūs esat atradis elements jūs meklējat, viss, kas jums jādara, ir mainīt rādītāju, iespējami divi, ja Jums ir saistītais list-- divkārt saistīts saraksts, rather-- un tad jūs varat vienkārši atbrīvot mezglā. Jums nav novirzīt viss apkārt. Jūs vienkārši mainīt divas norādes, tā ka ir diezgan ātri. 

Lookup ir slikti, lai gan, vai ne? Lai mēs varētu atrast elements saistītajā sarakstā, vai atsevišķi vai divkārt saistīti, mums ir lineāra meklēt to. Mums ir jāsāk sākumā un pārvietot beigas, vai sākt gada beigās kustībā uz sākumu. Mums nav brīvpieejas vairs. Tātad, ja mēs darām no meklēšanu daudz, varbūt saistītais saraksts nav gluži tik labu mums. 

Viņi arī patiešām grūti atrisināt, vai ne? Vienīgais veids, kā jūs varat tiešām kārtot saistīts sarakstu ir, lai sakārtotu to, kā jūs būvēt to. Bet, ja jūs sakārtotu to, kā jūs būvēt to, jūs vairs padarot ātri ievietošanas vairs. Jūs esat ne tikai lokalizācijas lietas uz priekšu. Jums ir atrast tiesības uz vietas, lai to, un tad jūsu ievietošanas kļūst tikai par tik slikti kā ievietojot masīva. Tātad saistīti saraksti nav tik liels, lai šķirošanas datus. 

Viņi arī ir diezgan maza, izmēra ziņā. Divkārt saistīts sarakstu nedaudz lielāks nekā atsevišķi saistītas sarakstus, kas ir nedaudz lielāks nekā blokiem, bet tas nav milzīgs daudzums izšķērdēta kosmosa. Tātad, ja telpa ir piemaksa, bet nav īsti intensīva piemaksa, tas varētu būt pareizais ceļš. 

Hash tabulas. Ievietošanai hash tabulu ir diezgan vienkārši. Tas ir divpakāpju process. Vispirms mums ir nepieciešams, lai palaistu mūsu datus, izmantojot hash funkciju, lai iegūtu hash kodu, un tad mēs ievietojiet elementu Into hash tabulu šajā hash kodu vietas. 

Dzēšana, līdzīgi saistīta sarakstā, ir viegli, kad jūs atrast elementu. Jums ir jāatrod tā pirmo reizi, bet tad, kad jūs to izdzēst, Jums vienkārši nepieciešams, lai apmainītos pāris norādes, ja jūs izmantojat atsevišķu ķēžu rādītāju. Ja jūs izmantojat zondēšana, vai, ja jūs neesat izmantojot Ķēžu vispār Jūsu hash tabulu, dzēšana ir tiešām ļoti viegli. Viss, kas jums jādara, ir hash dati, un tad doties uz šo vietu. Un pieņemot, ka jums nav ir kādas sadursmes, jūs varēsiet dzēst ļoti ātri. 

Tagad, lookup ir, ja lietas saņemt nedaudz sarežģītāka. Tas ir vidēji labāk nekā saistītas sarakstus. Ja jūs izmantojat Ķēžu, jums vēl joprojām ir saistīts sarakstu, kas nozīmē, ka jūs vēl joprojām ir meklēšana kaitējot ir saistīts sarakstu. Bet tāpēc, ka jūs lietojat savu saistīta saraksts un sadalot to pa 100 vai 1000 vai n elementi jūsu hash tabulu, jūs esat saistītie saraksti ir viss viens n lielumu. Viņi visi ir ievērojami mazāka. Jūs esat n saistīts sarakstus vietā Vienas saistīta saraksta lieluma n. 

Un tā tas reālās pasaules konstante faktors, kas Parasti mēs nerunā par savlaicīgas sarežģītību, to tas tiešām kaut ko mainīt šeit. Tātad lookup joprojām ir lineārs meklēt, ja jūs izmantojat Ķēžu, bet garums saraksta jūs meklējat, izmantojot ir ļoti, ļoti īss, salīdzinot. Atkal, ja šķirošana ir jūsu mērķis šeit, hash tabulas iespējams, nav pareizais veids, kā iet. Just izmantot masīvu ja šķirošanas ir ļoti svarīgi, lai jums. 

Un viņi var palaist toņkārta no izmēra. Ir grūti pateikt, vai hash tabulā ir mazs vai liels, jo tas tiešām ir atkarīgs cik liels jūsu hash tabula ir. Ja jūs tikai būs uzglabāšanai pieci elementi jūsu hash tabulu, un jums ir hash tabulu ar 10000 elementiem tajā, jūs, iespējams, izšķērdēt daudz vietas. Kontrasts ir Varat arī ir ļoti kompaktas hash tabulas, bet mazākais jūsu hash tabulu izpaužas, jo ilgāk katru no šiem sarakstiem, kas saistītas izpaužas. Un tā tur tiešām nav veids, kā definēt tieši lielums hash tabulu, bet tas ir iespējams, droši teikt, tas ir vispār būs lielāks nekā saistīta saraksts uzglabājot to pašu datu, bet mazāka nekā TRIE. 

Un cenšas ir ceturtais Šo struktūru ka mēs esam runājuši par. Ievietojot uz TRIE ir sarežģīta. Tur ir daudz dinamisku atmiņas sadalījumu, īpaši sākumā, kā jūs sāk būvēt. Bet tas ir nemainīgs laiks. Tas ir tikai cilvēka faktors šeit, kas padara to grūts. Ņemot sastapties null rādītāju, malloc telpa, iet tur, iespējams, malloc telpa no turienes atkal. Par iebiedēšana faktora veida Norādes dinamisku atmiņas sadalījumu ir šķērslis, lai notīrītu. Bet tad, kad jūs esat noskaidroti to, ievietošanas faktiski ir diezgan vienkārši, un tas, protams, ir nemainīgs laika. 

Dzēšana ir viegli. Viss, kas jums jādara, ir orientēties uz leju Pāris norādes un bezmaksas mezglā, tā ka ir diezgan laba. Lookup ir arī diezgan ātri. Tas ir balstīts tikai uz garums jūsu datiem. Tātad, ja visi jūsu dati ir pieci rakstzīmju virknes, Piemēram, jūs uzglabātu pieci rakstzīmju virknes jūsu TRIE, tas aizņem tikai pieci soļi, lai atrast to, ko jūs meklējat. Pieci ir tikai nemainīgs faktors, tāpēc atkal, ievietošana, dzēšana, un lookup Šeit ir visi nemainīgs laiku, efektīvi. 

Vēl viena lieta ir, ka jūsu trie ir faktiski veida jau sakārtots, labi? Pamatojoties uz to, kā mēs esam ievietojot elementi, dodoties burtu pēc burta atslēgu, vai cipars ar ciparu taustiņu, parasti, jūsu trie beidzas ar to, veida sakārtoti kā jūs veidot to. Tas nav īsti padara jēga domāt par šķirošanas tādā pašā veidā, kā mēs domājam par tas ar masīviem, vai saistīti sarakstiem, vai hash tabulas. Bet savā ziņā, jūsu trie ir sakārtots, kā jums iet. 

Negatīvie, protams, ir tas, ka trie strauji kļūst milzīgs. No katra krustojuma vietā, jūs varētu have-- ja jūsu galvenais sastāv no cipariem, Jums ir 10 citas vietas, jūs varat iet, kas nozīmē, ka katrā mezglā satur informāciju par datiem, jūs vēlaties, lai saglabātu šajā mezglā, plus 10 norādes. Kas, CS50 IDE, ir 80 baiti. Tātad, tas ir vismaz 80 baiti uz katrs mezgls, ka jūs izveidojat, un tas nav pat skaitīšanas datus. Un, ja jūsu mezgli ir burti nevis cipari, Tagad jums ir 26 norādes No katras vietas. Un 26 reizes 8, iespējams, ir 200 baiti, vai kaut kas tamlīdzīgs. Un jums ir kapitāls un lowercase-- jūs varat redzēt, kur es esmu, kas ar šo, labi? Jūsu mezgli var iegūt patiešām liels, un tā trie pati, kopumā var riktīgi liels, too. Tātad, ja telpa ir liela premium jūsu sistēmā, trie varētu nebūt pareizais veids, kā iet, pat ja citi tās priekšrocības stāties spēlēt. Es esmu Doug Lloyd. Tas ir CS50.