[Prehrávanie hudby] DAVID Malan: To je CS50. A to je ako začiatok a end-- ako literally-- takmer do konca týždňa šesť. 

Myslel som, že by som zdieľať trochu zábavné skutočnosti. Som vytiahol to až z nastaviť údaje minulého semestra. Možno si spomeniete, že sme sa vás opýtať na každom p set formulár, ak ste sledovali on-line alebo ak ste sa zúčastnili osobne. A tu je v dátach. Takže dnes bol veľmi predvídateľný. Ale my sme chceli stráviť trochu času s vami však. Chcel by niekto dohadu, prečo sa to graf je tak Jaggy, hore dole, hore dole, tak dôsledne? Čo každý z vrcholov a žľaby predstavujú? 

Divákov: [nepočuteľné] DAVID Malan: Naozaj. A viac zábavne, nedaj bože, máme jednu prednášku v piatok na začiatku semestra, že to, čo vidíme, sa stalo. Takže dnes sme sa zapojiť do trochu Ďalšie informácie o dátových štruktúrach. A dať vám viac pevnej látky mentálny model pre problémy v päť, ktorý je teraz von. Pravopisné chyby, kde budeme odovzdať vám textový súbor niektorí 100.000 a anglické slová, a budete mať prísť na to, ako šikovne ich načítať do pamäte, do pamäte RAM, pomocou niektoré údaje Štruktúra vášho výberu. 

Práve jedna taká dátová štruktúra by mohla byť, ale pravdepodobne by nemala byť, pomerne zjednodušujúce spájať zoznam, ktoré sme uviedli minule. A spájať zoznam mal aspoň jedna výhoda oproti maticu. Čo je jedna z výhod spájať zoznam pravdepodobne? 

Divákov: Vloženie. 

DAVID Malan: Vloženie. Čo tým myslíš? 

Divákov: Anywhere spolu zoznam [nepočuteľné]. 

DAVID Malan: Dobrý. Takže môžete vložiť prvok, kdekoľvek Chcete uprostred zoznamu bez toho aby museli zamiešať čokoľvek, ktoré sme uzavreli v našom triedenie diskusie, nie je nutne dobrá vec, pretože to si vyžaduje určitý čas, aby skutočne pohybovať všetkých tých ľudí vľavo alebo vpravo. A tak sa spájať zoznam, môžete len prideliť s malloc, nový uzol, a potom aktualizovať pár pointers-- dva, tri operácie max-- a sme schopní slot niekoho kdekoľvek do zoznamu. 

Čo iného bolo výhodné o prepojenom zoznamu? Jo? 

Divákov: [nepočuteľné] DAVID Malan: Perfect. Perfect. Je to naozaj dynamický. A že nie ste spáchanie, dopredu, do určitej pevnej veľkosti kus pamäti, ako by ste mať sa s poľa, inflačné ktoré je, že môžete prideľovať uzly iba na dopyt a tým používať len toľko miesta ako skutočne potrebujete. Na rozdiel od poľa, môžete náhodne rozdeliť príliš málo. A potom je to len bude byť bolesť v krku prerozdeliť nové väčšie pole, skopírujte všetko skončí, uvoľniť staré polia, a potom sa presunúť o vašej firme. Alebo ešte horšie, môžete prideliť cestu viac pamäte, než skutočne potrebujete, a tak budete mať veľmi riedko osídlené poľa, aby som tak povedal. 

Takže spájať zoznam vám tieto Výhody dynamiky a flexibility s inzerciou a deléciou. Ale určite tam musí byť zaplatená cena. V skutočnosti, jednou z tém preskúmať testu nulovej bol pár z kompromisov sme videli doteraz. Takže to, čo je cena, ktorú zaplatil alebo Nevýhodou prepojeného zoznamu? Jo. 

Divákov: Nie náhodný prístup. 

DAVID Malan: No náhodný prístup. Ale koho to zaujíma? Náhodný prístup neznie presvedčivé. 

Divákov: [nepočuteľné] DAVID Malan: Presne tak. Ak chcete mať určitej algorithm-- a dovoľte mi, aby som v skutočnosti navrhnúť binárne vyhľadávanie, najmä, čo je tá, ktorú sme použili celkom bit-- ak nemáte náhodný prístup, môžete to urobiť jednoduchú aritmetiku nájdenie ako prostredný prvok a skákanie na neho právo. Namiesto toho budete musieť začať v prvej element a lineárne vyhľadávania zľava doprava, ak chcete nájsť stredná alebo akýkoľvek iný prvok. 

Divákov: Asi potrebuje viac pamäte. 

DAVID Malan: berie viac pamäte. Kde je ten ďalší náklady prichádzajúce z pamäti? 

Divákov: [nepočuteľné] DAVID Malan: Presne tak. V tomto prípade je tu, mali sme spájať zoznam pre celé čísla, a napriek tomu sme zdvojnásobenie množstvo pamäte musíme tým, že tiež uloženie týchto ukazovateľov. Teraz menej veľký problém, ako Vaša structs sa zväčší a vy ste ukladanie nie je číslo, ale Možno študent alebo nejaký iný predmet. Ale ide samozrejme zostáva. A tak počet operácií na spojových zoznamov boli povolaní Boli veľké-O n- lineárne. Veci ako vloženie alebo hľadanie alebo delécie v prípade, že prvok sa stalo, že na samom konci Zoznam či už je to triedeného alebo nie. 

Niekedy môžete mať šťastie a takže spodnej medze týchto operácií môže byť tiež konštantný čas, ak ste vždy pri pohľade na prvý prvok, napríklad. Ale nakoniec sme sľúbili k dosiahnutiu svätý grál dátových štruktúr, alebo niektoré aproximácie tejto zmluvy, prostredníctvom konštantnom čase. Môžeme nájsť prvky, alebo pridať prvky alebo odstránenie prvkov zo zoznamu? Uvidíme už čoskoro. A ukázalo sa, že jeden mechanizmov sme začnú používať dnes, ročná spotreba v p nastaviť päť, je vlastne celkom známe. Napríklad, ak je to banda skúšky kníh, z ktorých každý má študent je prvá Meno a priezvisko na tom, a ja som vyzdvihnúť z ich na konci testu, a všetci sú dosť veľa v náhodnom poradí, a chceme ísť o triedení Tieto skúšky tak, že akonáhle sa stupňom je to proste oveľa jednoduchšie a rýchlejšie odovzdať je späť študentom abecedy. Čo by vaše inštinkty sa na hromadu skúšok, ako je tento? 

No, ak ste ako ja, môže vidieť, že sa jedná m, tak budem nejako dať to do, ak je to môj stôl alebo môj poschodia, kde Som šíri veci out-- alebo moje pole really-- Mohol by som dať všetky Ms tam. Oh. Tu je A. Takže by som mohol dať ako tu. Oh. Tu je ďalší A. idem dať to sem. Tu je Z. Tu je ďalší M. A tak Mohol by som začať robiť pilotov, ako je tento. A potom možno by som ísť neskôr a druh veľmi nitpicky-ly sort jednotlivé pilóty. Ale ide o to by som sa na vstupe, že som rukou a ja by som sa niektoré vypočíta rozhodnutia založené na tomto vstupe. Ak sa začína, dať to tam. Ak sa začne s Z, dal ju tam, a všetko medzi tým. 

Takže to je technika, ktorá je všeobecne známe ako hashing-- H-A-S-H- čo všeobecne znamená, že ako vstup a pomocou tohto vstupu pre výpočet hodnotu, zvyčajne číslo, a že číslo je index do skladu Nádoba, ako pole. Takže inými slovami, mohol by som mať hash funkcie, ako ja v mojej hlave, že keď vidím niekoho to Názov, ktorý sa začína, Chystám sa mapa, ktorá na nulu v mojej hlave. A keď vidím niekoho s Z, som bude mapovať, že až 25 v mojej hlave a potom to dať do posledná najviac hromada. 

Teraz, keď sa nad tým zamyslíte nie je môj mozog ale program v jazyku C, ktoré čísla by mohla sa spoľahnúť na dosiahnutie tohto rovnakého výsledku? Inými slovami, ak máte mal ASCII znak A, Ako zistíte, čo vedro, aby to v? Pravdepodobne nebudete chcieť dať do vedra 65, ktorý by bolo ako tam bez dobrého dôvodu. Kde chcete dať pokiaľ ide o jeho ASCII hodnota? Kam chceš urobiť, aby jeho ASCII hodnota prísť s múdrejší vedra aby ju v? 

Divákov: Mínus A. 

DAVID Malan: Jo. Takže mínus alebo mínus konkrétne 65, ak je to kapitál A. Alebo 98, ak je to malé. A tak, že by nám umožňujú veľmi jednoducho a veľmi aritmeticky, dať niečo do vedra takhle. Tak to dopadá, že sme vlastne robiť to rovnako aj s kvízy. 

Takže si možno pamätáte si krúžil vaše Názov Výučba Kolegovia sa na obálke. A boli organizované mená TF sa do týchto stĺpcov podľa abecedy, No, verte tomu alebo nie, keď všetci 80 a nás sa dali dohromady v noci do platovej triedy, posledný krok v našom procese triedenia, je hash kvízy do veľkej priestor podlahy na [nepočuteľné] a položiť kvízy Každý by presne poradí ich TF rokov mená na obálke, pretože potom je to oveľa jednoduchšie pre nás prehľadávať že pomocou lineárnej vyhľadávanie alebo nejaký chytrosti pre TF nájsť jeho alebo kvízy svojich študentov. 

Takže táto myšlienka z hash ktoré uvidíte, je celkom silný je vlastne celkom samozrejmosťou a veľmi intuitívne, podobne ako napríklad rozdeliť a dobytie bolo v týždni nula. Aj rýchlo vpred na hackathon pred pár rokmi. To bol Zamyla a pár Ostatní zamestnanci pozdrav študenti ako prišli. A mali sme veľa skladanie Stoly s menovkami. A my sme mali menovky organizovanej sa ako ako cez tú a Zs tam. A tak jedným z TFS veľmi šikovne písal to ako návod na deň. A v 12. týždni semestra tohto všetko dávalo zmysel a všetky vedel, čo má robiť. Ale kedykoľvek som fronte rovnakým spôsobom, budete sa vykonáva Rovnaký pojem hash. Takže poďme formalizovať to trochu. Tu je pole. Je vypracovaný, aby sa trochu široký len líčiť, vizuálne, že by sme mohli dať reťazca v niečom, ako je toto. A toto pole je zjavne veľkosť 26 celkom. A vec sa nazýva Tabuľka ľubovoľne. Ale to je len umelca stvárnenie o tom, čo by mohlo byť hash tabuľky. 

Takže hash tabuľka teraz sa chystá byť vyššia štruktúru dát na úrovni. Koniec koncov chystáme vidieť, že vás môžu implementovať hash tabuľku, ktorá je podobne ako check-v súlade na hackathon podobne ako tento Tabuľka slúži k triedenie skúšku kníh. Ale hash tabuľka druh tejto vysokej úrovni koncept, ktorý by mohol použiť pole pod kryt na jeho vykonanie, alebo použiť zoznam dĺžky, alebo dokonca možno niektoré ďalšie dátové štruktúry. A teraz to theme-- prevzatia niektoré z týchto základných zložiek ako pole a budovy Blokovať teraz zo zoznamu dĺžky a vidieť, čo ešte môžeme stavať nad tie, ako prísady na recept, takže stále viac a viac zaujímavé a užitočné konečné výsledky. 

Tak s hash tabuľky môžeme ho zaviesť v pamäti obrazovo takto, ale ako by to vlastne byť kódované up? No, možno, pretože jednoducho je to. Ak KAPACITA vo všetkých veľkých písmenách, je len niektorí constant-- napríklad 26, 26 písmen alphabet-- Mohol by som zavolať svojej variabilný stôl, a mohol by som tvrdiť, že budem dať char hviezdy tam, alebo reťazec. Takže je to tak jednoduché, ako to, ak chcú zaviesť hash tabuľky. A napriek tomu, je to naozaj len pole. Ale opäť, hash Tabuľka je teraz, čo budeme zavolajte abstraktné dátový typ, ktorý je rovnako druh koncepčného vrstvenie na vrchole niečo viac svetského Teraz mi poľa. 

A teraz, ako máme ísť o riešenie problémov? No, skôr som mal luxus mať dostatok tabuľkový priestor tu tak, že by som mohol dať kvízy nikde som chcel. Tak, aby mohla ísť sem. Zs môže ísť sem. Pani môže ísť sem. A potom som mal nejaké extra priestor. Ale to je trochu cheat práva teraz, pretože tejto tabuľke, či som naozaj myslel na to ako pole, je len bude nejaké pevné veľkosti. 

Takže technicky, keď som vytiahnuť do iného študenta kvíz a vidieť, oh, táto osoba je Názov začína príliš, Tak nejako som chcel dať to tam. Ale akonáhle som to tam dal, ak je táto tabuľka skutočne predstavuje pole, Chystám sa byť prevažujúci alebo prepisovanie kto tento študent kvíz je. Je to tak? Pokiaľ sa jedná o pole, len jedna vec môže ísť v každej z týchto buniek alebo prvkov. A tak nejako som sa vybrať a zvoliť. 

Teraz skôr som tak trochu podvádzal a robil to alebo I len tak na seba je nad sebou. Ale to nebude lietať v kóde. Tak, kde som mohol dať Druhý študent, ktorého meno Ak je všetko, čo som mal, je to k dispozícii tabuľkový priestor? A ja som použil tri sloty a to vyzerá to, že je to len niekoľko ďalších. Čo si to mohol urobiť? Divákov: [nepočuteľné] DAVID Malan: Jo. Možno, povedzme, aby to jednoduché. Je to tak? To sa nehodí tam, kde chcem, aby to. Takže idem dať technicky kde by B ísť. Teraz, samozrejme, ja začínam maľovať sám seba do kúta. Ak sa dostanem na študenta ktorého meno je vlastne B, Teraz B bude pohybovať trochu dopredu, ako by sa mohlo stať, jo, ak je to B, teraz to musí ísť sem. 

A tak sa veľmi rýchlo by sa mohlo stať problematickým, ale je to technika, ktorá v skutočnosti je označovaný ako lineárne snímanie, kedy stačí zvážiť svoje polia, že pozdĺž čiary. A práve typ snímača, alebo skontrolujte každú dostupné prvok hľadá k dispozícii na mieste. A akonáhle zistíte, jedno, čo si len kvapka tam. 

Teraz je cena v dnešnej dobe venované pre toto riešenie je to, čo? Máme pevnú veľkosť poľa, a pri vložení mena do neho, aspoň spočiatku, čo je doba chodu vloženie pre uvedenie študentov " kvízy na správnych vedierka? Big O čo? 

Divákov: n. DAVID Malan: Počul som, že veľký O n. To nie je pravda. Ale budeme dráždiť seba prečo za chvíľu. Čo iné by to mohlo byť? 

Divákov: [nepočuteľné] DAVID Malan: A dovoľte mi, aby som to vizuálne. Takže predpokladám, že je to písmeno S. 

Divákov: Je to jedna. DAVID Malan: Je to jedno. Je to tak? To je pole, ktoré znamená, že máme náhodný prístup. A ak si myslíme, že to na nulu a to až 25, a my sme si uvedomili, že, oh, tu je môj vstup S, Ja určite previesť S, znak ASCII, do zodpovedajúceho počtu medzi nulou a 25 a potom sa okamžite dať tam, kam patrí. 

Ale samozrejme, akonáhle sa dostanem do Druhá osoba, ktorá sa volá A alebo B alebo C nakoniec, ak som použil lineárne snímanie ako moje riešenie, Doba chodu vloženie v najhoršom prípade bude skutočne preniesť do čoho? A ja som počul tu správne čoskoro. Divákov: [nepočuteľné] DAVID Malan: Tak to je naozaj n raz máte dostatočne veľký súbor dát. Tak, na jednej strane, ak vaše pole je dostatočne veľký a vaše dáta je riedke dosť, vy si tento krásny konštantný čas. Ale akonáhle začnete stále viac a viac prvkov, a len štatisticky dostanete viac ľudí s písmenom Ako ich meno alebo písmeno B, mohlo by to potenciálne prejsť na niečo viac lineárny. Takže nie je úplne dokonalá. Tak by sme mohli robiť lepšie? 

No, čo bolo naše riešenie, ako keď sme sa Chcete mať väčšiu dynamiku ako niečo ako pole dovolené? Divákov: [nepočuteľné] DAVID Malan: Čo sme predstaviť? Jo. Takže spájať zoznam. No, uvidíme, čo súvisí Zoznam môže urobiť pre nás miesto. No, dovoľte mi, aby som navrhujem, aby sme nakresliť obrázok takto. Teraz je to iná obrázok z príkladu z iného textu, v skutočnosti, že je v skutočnosti pomocou poľa veľkosti 31. A to autor jednoducho rozhodol hash reťazca nie sú založené na mená tejto osoby, ale na základe ich narodeniny. Bez ohľadu na mesiace, ale prišiel ak ste sa narodil na prvý mesiac alebo 31. v mesiaci, autor hash bude na základe tejto hodnoty, tak, aby sa rozšírila mená sa trochu viac než len 26 miest, by mohli umožniť. A možno je to trochu jednotnejší ako ísť s písmenami abecedy, pretože samozrejme je to asi viac ľudí na celom svete sa menami ktoré začínajú ako iste niektoré ďalšie písmená abecedy. Takže možno je to trochu jednotnejší, za predpokladu, že rovnomerné rozloženie dojčiat po celé mesiace. 

Ale, samozrejme, je to stále nedokonalé. Je to tak? Budeme mať kolízie. Viac ľudí v tejto dátové štruktúry sú stále majú rovnaký dátum narodenia najmenej ste bez ohľadu na mesiac. Ale čo sa autor urobil? No, vyzerá to, že máme celý rad na ľavej strane ťahané vertikálne, ale to je len umelca stvárnenie. Nezáleží na tom, akým smerom sa vás čerpať rad, je to ešte pole. Čo je to pole zdanlivo? 

Divákov: spájať zoznam. 

DAVID Malan: Jo. Vyzerá to, ako by to polia prepojeného zoznamu. Takže znova, do tohto bodu druhu použitie týchto dátových štruktúr teraz ako prísady do viacerých zaujímavé riešenie, môžete mať úplne Základné, rovnako ako pole, a potom niečo viac zaujímavé ako spájať zoznam a dokonca spojiť ich do ešte zaujímavejšie dátové štruktúry. A skutočne, taky by to sa nazýva hash tabuľky, pričom pole je naozaj hash tabuľka, ale to hash tabuľka reťaze, aby som tak povedal, že môže rásť alebo zmenšiť na základe počet prvkov, ktorý chcete vložiť. 

Teraz teda, čo je doba chodu teraz? Ak chcem vložiť niekoho ktorého narodeniny 31. októbra, kde sa on alebo ona ísť? Dobrá. Na samom dne, kde sa hovorí, že 31. A to je perfektné. To bolo konštantný čas. Ale čo keď nájdeme niekoho iného ktorého narodeniny, poďme sa pozrieť, Október, november k 31? Ak sa on alebo ona ísť? To isté. Dvojstupňová hoci. To je konštantná aj keď je to tak? Dobrá. V súčasnej dobe to je. Ale vo všeobecnom prípade, čím viac ľudí pridáme, pravdepodobnostne, ideme aby sa viac a viac ku kolíziám. 

Teraz je to trochu lepšie, pretože technicky teraz moje reťaze môžu byť v v najhoršom prípade, ako dlho? Ak mám vložiť n ľudí do toho viac sofistikované dátové štruktúry, n ľudí, V najhoršom prípade to bude n. Prečo? 

Divákov: Pretože keby každý má narodeniny v rovnaký deň, že budeš jeden riadok. DAVID Malan: Perfect. To by mohlo byť trochu neprirodzený, ale skutočne v najhoršom prípade, ak každý má narodeniny v rovnaký deň, s ohľadom na vstupy máte, budete mať masívne dlhým reťazcom. A áno, môžete ho hovoru hash tabuľky, ale v skutočnosti je to len masívne spájať zoznam s veľa nevyužitého miesta. Ale všeobecne, ak budeme predpokladať, že aspoň narodeniny sú uniform-- a to asi nie je. Robím, že až. Ale ak budeme predpokladať, pre Z dôvodu diskusia že sú, potom teoreticky, ak To je vertikálny reprezentácia matice, no a potom dúfajme, že ste dostane reťazcov, ktoré sú, ako viete, zhruba rovnakú dĺžku, kde každý z to predstavuje deň v mesiaci. 

Teraz, keď je tam 31 dní v mesiaci, to znamená, že moja doba chodu naozaj je veľký O n viac ako 31, čo cíti lepšie ako lineárny. Ale to, čo bol jeden z našich Záväzky pár týždňov Pred keď to prišlo k vyjadrovaniu doba chodu algoritmu? Stačí len pozrieť na vysokú objednávky termíne. Je to tak? 31 je určite užitočné. Ale je to stále veľký O n. Ale jedným z tém o problém nastaviť päť bude na na vedomie, že absolútne, asymptoticky, teoreticky Táto dátová štruktúra nie je o nič lepší, než len jeden masívny spájať zoznam. A skutočne, v najhoršom prípade to hash tabuľka môže prejsť do toho. 

Ale v reálnom svete, s nami ľudia že vlastné Macintosha alebo PC, alebo čokoľvek a beží v reálnom svete softvér z reálnych dát, ktoré algoritmus budete preferovať? Ten, ktorý má koncové kroky alebo ten, ktorý trvá n deleno 31 stupňov nájsť nejakú časť dát alebo vyhľadať nejaké informácie? Myslím, že absolútne 31 značiek rozdiel v reálnom svete. To je 31 krát rýchlejšie. A my ľudia sú určite ísť si uvedomiť, že. 

Takže si uvedomiť rozpor tam medzi skutočne hovorí o tom, čo teoreticky a asymptoticky, ktoré rozhodne má hodnotu, ako sme videli, ale v reálnom svete, ak vám záleží len robiť človek šťastný pre všeobecné vstupy, môžete veľmi dobre chcete prijať skutočnosť, že áno, je to lineárny, ale to je 31 krát rýchlejší ako môže byť lineárny. A ešte lepšie, nebudeme musieť niečo ľubovoľného ako dátum narodenia, by sme mohli stráviť trochu viac času a chytrosť a premýšľať o tom, čo by sme mohli urobiť, krstné meno človeka, a možno Ich dátum narodenia kombinovať tie, zložky na niečo vymyslíme je to naozaj viac jednotná a menej Jaggy, aby som tak povedal, než tento obrázok V súčasnej dobe naznačuje, že by mohlo byť. Ako by sme mohli realizovať to v kóde? No, dovoľte mi, aby som navrhujem, aby sme len požičať nejaké syntax sme použitý párkrát tak ďaleko. A ja budem definovať uzol, ktorý opäť je všeobecný termín pre len niektoré Kontajner pre niektoré dátové štruktúry. Chystám sa navrhnúť, aby reťazec sa deje tam. Ale budeme začnete tých koliesok off teraz. 

Žiadne ďalšie CS50 knižnica Naozaj, ak budete chcieť ho použiť pre finále Projekt, ktorý je v poriadku, ale teraz budeme ťahať späť záclony a hovoria, že je to len znak hviezda. Takže slovo sa bude meno osoby v otázke. A teraz mám odkaz tu k ďalšiemu uzlu tak, že tieto predstavujú Každý z uzlov v reťazci, prípadne, prepojeného zoznamu. 

A teraz ako sa Vyhlasujem hash tabuľka sám? Ako môžem vyhlásiť celú túto štruktúru? No, naozaj, rovnako ako som použila ukazovateľ sa iba prvý prvok zoznamu predtým, podobne môžem len povedať, Proste potrebujem veľa ukazovateľov realizovať celý tento hash tabuľky. Budem mať celý rad volal tabuľka hash tabuľky. Bude to mať veľkosť kapacity. To je to, koľko prvkov sa vojde do neho. A každý z týchto prvkov v tomto pole bude uzol hviezda. Prečo? No, na obrázku je to, čo som vykonávanie hash tabuľku ako účinne na začiatku je len Toto pole, ktoré sme vypracovaný vo zvislom smere, každý z ktorého námestí predstavuje ukazovateľ. Že tie, ktoré majú lomítka medzi nimi sú len null. A tie, ktoré majú šípky idú doprava sú skutočné ukazovatele na skutočných uzlov, ergo začiatok spojovaceho zoznamu. 

Tak tu teda je, ako by sme mohli realizovať hash tabuľku, ktorá implementuje samostatný reťazenie. Teraz môžeme robiť lepšie? V poriadku som sľúbil minule, že by sme mohli dosiahnuť konštantný čas. A nejako som ti dal konštantný čas tu, ale potom povedal, že naozaj konštantný čas, pretože je to stále v závislosti na celkovej počet prvkov ste vklad do dátová štruktúra. Ale predpokladajme, že sme to urobili. Dovoľte mi, aby som sa vrátiť na obrazovku sem. Dovoľte mi, aby som tiež premietať to tu, jasné, obrazovky, a predpokladám, že som to urobil. Dajme tomu, že som chcel vložiť meno Daven v do mojej dátovej štruktúry. 

Tak som chcel vložiť reťazec Daven do dátovej štruktúry. Čo keď nemám používať hash tabuľky, ale ja používam niečo, čo je viac stromová ako rodokmeň, kde máte nejaké korene na Horné a potom uzly a listy ktoré idú dole a von. Predpokladajme teda, že ja chcete vložiť Daven je na to, čo je v súčasnej dobe prázdny zoznam. Chystám sa vykonať nasledujúce kroky: Ja som bude vytvárať uzol v tejto rodine stromová dátová štruktúra, ktorá vyzerá trochu ako je tento, z ktorých každý obdĺžniky sa, povedzme, Pre túto chvíľu 26 prvkov v ňom. A každý z buniek V tomto poli sa deje reprezentovať písmeno abecedy. 

Konkrétne sa budem liečiť to je, potom B, potom C, potom D, toto tu. Takže to bude účinne predstavujú písmeno D. Ale vložiť všetky Daven je meno musím urobiť trochu viac. Takže som prvýkrát bude hash, aby som tak povedal. Idem sa pozrieť na prvé písmeno v Daven je, čo je zrejme D, a budem prideliť uzol, ktorý vyzerá ako tohle-- veľký obdĺžnik veľký tak, aby sa zmestili na celú abecedu. 

Teraz D je hotovo. Teraz A. D-A-E-V-N je cieľ. Takže čo teraz budem robiť, je to. Akonáhle som začal D oznámenia Je tam žiadny ukazovateľ. Je to nezmyselné hodnoty v okamihu, alebo by som mohol inicializovať na hodnotu null. Ale dovoľte mi, aby som ďalej s Táto myšlienka vybudovania stromu. Dovoľte mi, aby som prideliť ďalšie z nich uzly, ktoré má 26 prvkov v nej. 

A viete čo? Ak je to len uzol v pamäti, že Vytvoril som s malloc pomocou struct ako čoskoro uvidíte, Chystám sa robiť tohle-- Budem čerpať šípku z to, čo reprezentoval D dole do tohto nového uzla. A teraz, najprv ďalšie písmeno Daven menom, V- D-A-V- Chystám sa ísť dopredu a čerpať ďalšie uzol takto, pričom sú tu prvky V, ktoré budeme čerpať pre instance-- Ups. Nebudeme tam kresliť. Bude to nájdete tu. 

Potom ideme do Považujeme to za V. A potom tu budeme indexu dole z V na to, čo budeme považovať E. A potom tu budeme ísť jeden z týchto uzlov tu. A teraz tu máme otázku odpovedať. Musím nejako vyplýva, že sme na konci reťazca Daven. Takže som mohol len nechať null. 

Ale čo keď máme Daven je celé meno tiež, čo je, ako sme povedali, Davenport? Takže čo keď je Daven vlastne podreťazec, prefix oveľa dlhší reťazec? Nemôžeme len trvalo hovoria, nič sa deje tam ísť, pretože sme mohli Nikdy nevkladajte slovo ako Davenport do tejto dátovej štruktúry 

Takže to, čo by sme mohli urobiť, namiesto toho je zaobchádzať s každým z týchto prvkov ako možno mať dva prvky vo vnútri nich. Jedným z nich je ukazovateľ, naozaj, ako som robil. Takže každá z týchto krabíc nie je len jedna bunka. Ale čo v prípade, že horná one-- spodnej niečí bude nulový, pretože nie Davenport ešte nie. Čo v prípade, že jeden vrchol je nejaký zvláštny hodnota? A to bude trochu ťažké stanoviť, že táto veľkosť. Ale predpokladám, že je to len značka začiarknutia. Pozrite sa. D-E-V-N-je reťazec V tejto dátovej štruktúry. 

Medzitým, keby som mal viac priestoru tu som mohol robiť P-O-R-T, a ja som mohol dať šek v uzle ktorý má na písmeno T na samom konci. Tak toto je masívne komplexné vyzerajúce štruktúru dát. A môj rukopis rozhodne nepomôže. Ale keď som chcel vložiť niečo iný, zvážte, čo budeme robiť. Ak by sme chceli, aby Dávida, by sme nasledovať rovnakú logiku, D-A-V, ale teraz by som upozorniť na ďalšie prvok, ktorý z E, ale od I do D. Takže tam to bude viac uzly tohto stromu. Budeme mať volania malloc viac. Ale ja nechcem, aby sa úplný zmätok obrázku. Takže poďme sa pozrieť na miesto jedného ktorá bola vopred formulovaná takto sa nie je bodka, bodka, bodky, ale len skrátene pole. Avšak každý z uzlov v tomto tu stromu hore predstavuje rovnaký thing-- pole Ray veľkosti 26. 

Alebo ak chceme byť naozaj správne teraz, čo ak niekto názov, apostrof, poďme Predpokladajme, že každý uzol má v skutočnosti ako 27 indexy v ňom, nie len 26 rokov. Tak to teraz bude dát Štruktúra nazýva trie-- T-R-I-E. Trie, ktorá je údajne historicky šikovný názov pre drevo , Ktorý je optimalizovaný pre vyhľadávanie, čo samozrejme, sa píše s I-E, takže je to trie. Ale to je história trie. 

Takže trie je to stromová údaje štruktúra ako rodinný strom že nakoniec sa chová takto. A tu je len ďalším príkladom toho, celá partia mien iných ľudí. Ale otázka teraz na dosah ruky je to, čo majú sme získali zavedením pravdepodobne viac zložitá štruktúra dát, a jeden, úprimne, že používa veľa pamäte. 

Vzhľadom k tomu, aj keď, v túto chvíľu, ja som len pomocou D je ukazovateľ a A V a Es a Ns, Som plytvanie sakra veľa pamäte. Ale tam, kde som strávil jeden zdroj, Mám vo zvyku sa získať späť ďalšie. Takže keď som tráviť viac priestoru, čo je asi nádeje? Že som strávil menej čo? Divákov: Menej času. DAVID Malan: Čas. A prečo by to mohlo byť? No, a čo je vloženie čas, ak ide o veľký O teraz, mená, ako je Daven alebo Davenport alebo David? No, Daven bol päť krokov. Davenport by deväť krokov, tak to by bolo ešte niekoľko krokov. David by bol päť krokov rovnako. To sú konkrétne čísla, ale určite je tu horná medza Dĺžka niečí meno. A skutočne, v probléme sady piatich špecifikácia, budeme navrhovať že je to niečo, to je 40-niektoré-nepárne znaky. 

Realisticky, nikto nemá nekonečne dlhý názov, čo znamená, že dĺžka meno alebo dĺžka reťazca by sme mohli majú určitý stav Štruktúra je pravdepodobne to, čo? Je to konštantná. Je to tak? Mohlo by to byť veľký ako konštantný 40-niečo, ale to je konštantná. A to nemá závislosti na tom, koľko Ostatné názvy v tejto dátovej štruktúre. Inými slovami, keď som chcel teraz vložiť Colton alebo Gabriel alebo Rob alebo Zamyla alebo Alison alebo Belinda alebo iné názvy z radov zamestnancov do týchto údajov štruktúra, je doba chodu vloženie ďalšie mená bude vôbec ovplyvnené podľa toho, ako mnoho ďalších prvkov, sú v dátovej štruktúre už? To nie. Je to tak? Vzhľadom k tomu, že sme efektívne používať Tento multi-layer hash tabuľky. A beží čas Niektoré z týchto operácií nezávisí od počtu prvky, ktoré sú v dátovej štruktúre alebo že sa nakoniec bude byť v dátovej štruktúre, ale na dĺžke čo konkrétne? 

Reťazec je vložená, ktorý predsa robí tento asymptoticky konštantný time-- veľký O jednej. A úprimne povedané, práve v reálnom svete, to znamená vloženie Daven meno sa ako piatich krokoch, alebo Davenport deväť kroky, alebo David päť krokov. To je sakramentsky malá prevádzkovej doby. A naozaj, je to veľmi dobrá vec, najmä keď to nie je závislé na celkovej počet prvkov v tam. Tak ako môžeme realizovať tento druh štruktúry v kóde? Je to trochu viac zložité, ale napriek tomu je to len aplikácie základné stavebné kamene. Chystám sa znovu definovať nás uzol takto: bool volal word--, a to by sa dalo nazvať čokoľvek. Ale bool predstavuje to, čo som nakreslil ako začiarknutie. Áno. To je koniec reťazca V tejto dátovej štruktúry. 

A samozrejme, uzol hviezda sa odkazuje na deti. A naozaj, rovnako ako rodokmeň, budete by zvážiť uzly ktoré visí dna niektorých rodičia element byť deti. A tak sa deti sa chystá byť pole 27, 27. jedna byť len pre apostrof. Budeme triediť o osobitný prípad, že. Takže môžete mať isté mená s apostrofmi. Možno aj pomlčkou musia tam ísť, ale budete viď str sade 5 my len starostlivosť o listov a apostrofy. 

A potom ako si predstavujú dátová štruktúra sama o sebe? Ako si predstavujú koreň tohto trie, aby som tak povedal? No, rovnako ako s prepojeného zoznamu, vždy ho potrebujú ukazovateľ na prvý prvok. S trie stačí jeden ukazovateľ na koreň tohto trie. A odtiaľ môžete hash vaša cesta dole hlbšie a hlbšie pre každý uzol v štruktúre. Tak jednoducho sa to môže predstavujeme, že struct. 

Teraz Meanwhile-- Oh, otázku. 

Divákov: Čo je bool slovo? 

DAVID Malan: BOOL slovo práve táto inkarnácia C z toho, čo som popísal V tomto boxe tu, keď Začal som rozdelenie každého z prvky poľa do dvoch častí. Jedným z nich je ukazovateľ na ďalší uzol. Iný musí byť niečo ako zaškrtávacie políčko povedať, že áno, je tu Slovo Daven, že tu končí, pretože nechceme, v okamihu, Dave. 

Aj keď Dave bude legitímne slovo, že to nie je v trie ešte. A D nie je ani slovo. A D-nie je slovo alebo meno. Takže začiarknutie označuje iba raz vás hit tento uzol predchádzajúca cesta znakov vlastne reťazec, ktorý ste vložili. Tak to je všetko bool tam robí pre nás. 

Akékoľvek ďalšie otázky týkajúce sa pokusov? Jo. 

Divákov: Čo je presah? Čo keď máte Dave a Daven? DAVID Malan: Perfect. Čo keď máte Dave a Daven? Pokiaľ teda vložíte, povedzme prezývku, pre David-- Dave-- D-A-V-E? To je vlastne super jednoduché. Takže sme len bude trvať štyri kroky. D-A-V-E. A čo mám robiť, až som narazila, že štvrtý uzol? Len tak pre kontrolu. Už sme dobré ísť. Hotovo. Štyri kroky. Konštantný čas asymptoticky. A teraz sme ukázali, že obaja Dave a Daven sú reťazce v štruktúre. Takže nie je problém. A všimnite si, ako prítomnosť z Daven to nezvládli mať viac času, alebo menej čas pre Dave a naopak. 

Takže čo iného môžeme teraz robiť? Použili sme túto metaforu pred zásobníkov predstavuje niečo. Ale ukazuje sa, že stĺpec podložiek je vlastne demonštratívny iného abstraktné údajov type-- vyššiu dátovú štruktúru úrovne že na konci dňa je len ako pole alebo spojovaceho zoznamu alebo niečo prozaickejšia. Ale je to oveľa zaujímavejšie koncepčné poňatie. Stack, ako sú tieto žľaby tu v Mather, sa všeobecne nazývajú len that-- stoh. 

A v tomto type dátovej štruktúry Máte dve operations-- máte jednu s názvom Push pre pridať niečo do zásobníka, ako dávať iný zásobník Späť na vrchol zásobníka. A potom pop, ktorý vás znamená vziať najvrchnejšiu zásobníka off. Ale to, čo je kľúčom k stack je, že to dostal túto kuriózne vlastnosť. Ako zamestnanci jedálne sú preskupiť zásobníky na ďalšie jedlo, čo sa bude pravda o tom, ako študenti interagujú s touto dátovou štruktúrou? Divákov: Chystajú sa pop jednorazové. DAVID Malan: Chystajú sa pop jednorazové, dúfajme, že na vrchol. V opačnom prípade je to len trochu hlúpy ísť celú cestu až na dno. Je to tak? Dátová štruktúra nie je v skutočnosti umožňuje uchopiť spodný zásobník aspoň ľahko. Takže tam je to zvedavý vlastnosť stohu že posledná položka je bude prvý von. A počítačoví odborníci hovoria tento LIFO-- posledný dnu, prvý von. A to v skutočnosti nemá mať zaujímavé aplikácie. To nie je nevyhnutne tak zrejmé, ako niektorí iní, ale môže skutočne byť užitočné, a môže skutočne byť vykonaná v niekoľkými rôznymi spôsobmi. 

Takže človek, a v skutočnosti, nech ma nie sa ponoriť do toho. Ideme na to miesto. Poďme sa pozrieť na ten, ktorý je takmer Rovnaký nápad, ale je to trochu spravodlivejší. Je to tak? Ak ste niektorý z týchto ventilátorov chlapčenské alebo dievčatá, ktoré naozaj rád Apple produkty a prebudil vo 3:00 sa zoradia v nejakom obchode získať najnovšie iPhone, budete mohol fronte takhle. 

Teraz fronta je veľmi zámerne menovaný. Je to čiara, pretože tam je niektoré spravodlivosť k nemu. Je to tak? Bolo by trochu nasáva, ak ste tam dostal najprv na Apple Store ale vy ste skutočne najspodnejšej zásobník, pretože zamestnanci Apple potom pop posledná osoba, ktorá vlastne dostal do vedenia. Tak komíny a frontu, aj keď funkčne sú druh na same-- je to práve táto kolekcia zdrojov, ktoré je tam bude rásť a shrink-- sa Táto spravodlivosť aspekt k tomu, aspoň v reálnom svete, kde tieto operácie cvičíte sú zásadne odlišné. Stack-- front rather-- je povedal, aby mal dve operácie: n frontu a d frontu. Alebo ich môžete volať ľubovoľný počet vecí. Ale len chcete zachytiť Predstava, že človek je pridanie a jeden je nakoniec odpočítaním. 

Teraz pod pokrievku, ako stack a front by mohla byť vykonávaná ako na to? Nebudeme zachádzať do kódu to preto, že vyššia úroveň nápad je trochu viac zrejmé. Chcem povedať, čo ľudia robia? Ak som prvý človek na Apple Uložte a to je predné dvere, vieš, ja budem stáť tu. A ďalšie osoby bude tu stáť. A ďalšie osoby bude tu stáť. Takže to, čo dátová štruktúra je možné uplatniť na fronte? 

Divákov: front. DAVID Malan: No, front. Iste. Čo ešte? 

Divákov: spájať zoznam. 

DAVID Malan: súvisí zoznam, ktorý by mohol realizovať. A spájať zoznam je pekné, pretože potom môže rásť ľubovoľne dlho, na rozdiel sa mať nejaký pevný počet ľudí v obchode. Ale možno, že pevne stanovený počet miest je legitímne. Vzhľadom k tomu, ak majú len ako 20 iPhone prvý deň, možno oni len potrebujú rad veľkostí 20 predstavujú, že front, ktorá je len povedať teraz, akonáhle začneme hovoriť o týchto problémoch vyššej úrovni, môžete ju implementovať v mnohých rôznymi spôsobmi. A je to asi len tak byť kompromis v priestore a čase alebo len vo svojom vlastnom kóde zložitosti. 

Čo stohu? No, zásobník, sme videli príliš môže byť len tieto zásobníky. A tie by mohli realizovať toto pole. Ale v určitom okamihu, ak používate polia, čo sa bude diať na zásobníky sa snažíte dať dole? Dobrá. Budeš len môcť ísť tak vysoko. A myslím, že v Mather, že sú skutočne zapustené v tomto otvore. Takže v skutočnosti, to je takmer ako Mather používa pole pevnej veľkosti, pretože môžete len zmestí toľko zásobníky v tomto otvore v steny dole pod kolená ľudí. A tak, aby mohla byť hovorí, že je pole, ale mohli by sme iste realizovať, že všeobecnejšie s prepojeného zoznamu. 

No, čo iné dátové štruktúry? Dovoľte mi, aby som vytiahnuť jeden iný vizuálny tu. Niečo ako, ako o tomto tu? Prečo by mohlo byť užitočné mať nie niečo tak nóbl ako trie, ktorá videli sme mali tieto veľmi široké uzly, z ktorých každý je v poli? Ale čo keď urobíme niečo viac jednoducho, ako starej školy rodokmeni, ktorých jednotlivé uzly tu práve ukladanie čísiel. Namiesto názvu alebo potomka práve ukladanie čísel, ako je tento. 

No, žargón používame v dátové štruktúry je obaja snažia a stromy, kde Trie, opäť, je len ten, ktorého uzly sú polia, je stále to, čo by mohlo používať od základnej škole keď ste sa rodina tree-- listy a koreň stromu a deti materská a ich súrodenci. A my by sme mohli realizovať strom, napríklad, ako jednoducho ako to. Strom, ak to ako uzol, jeden z Tieto kruhy, ktoré má číslo, že to nebude mať jeden ukazovateľ, ale dva. A akonáhle pridáte Druhý ukazovateľ, môžete teraz môžu skutočne urobiť trochu dvojrozmerného údajov štruktúry v pamäti. Rovnako ako dvojrozmerný poľa, môžete mať takú dvoch-dimenzionální spojové zoznamy, ale tie že nasledovať vzor tam, kde je žiadne cykly. Je to naozaj strom s jedným prarodič až sem a potom niektorí rodičia a deti a vnúčatá a pravnúčatá. a tak ďalej. 

Ale čo je naozaj pekné o tom taky, len preto, aby ťa podpichovať s trochou kódu, odvolanie rekurzia od chvíľu späť, pričom môžete napísať funkciu, ktorá volá sama seba. To je krásna príležitosť vykonávať niečo ako rekurzie, pretože to považujú. 

Jedná sa o strom. A bol som trochu análny s tým, ako Dal som celé čísla na ulici. Natoľko, že to má zvláštne name-- binárny vyhľadávací strom. Teraz sme počuli o binárny hľadať, ale môžete pospiatky z mena tá vec je? Čo je vzor, ​​ako som vložená celé čísla do tohto stromu? To nie je ľubovoľná. Tam je nejaký vzor. Jo. 

Divákov: menšie na ľavej strane. 

DAVID Malan: Jo. Menšie sú na ľavej strane. Tie väčšie sú na pravej strane. Tak, že pravdivé tvrdenie je rodič je väčší než jeho ľavej dieťa, ale menej než pravom dieťa. A to samo o sebe je ešte rekurzívne slovné definície pretože môžete použiť, že Rovnaká logika sa ku každému uzlu a to len dna out, referenčný prípad, ak vás bude, keď narazí jeden z listy, aby som tak povedal, kde má dovolenka žiadne deti ďalej. 

Teraz, ako môžete nájsť číslo 44? Tie by začať pri koreni a povedať, hm. 55 nie je 44 Tak to ja chcem ísť právo alebo nechcem ísť doľava? No, samozrejme budete chcieť ísť doľava. A tak je to rovnako ako telefón Kniha príklad v binárnej vyhľadávania všeobecnejšie. Ale my sme jeho vykonávanie Teraz trochu viac dynamicky ako pole môže dovoliť. A v skutočnosti, ak sa chcete pozrieť na kód, na prvý pohľad iste. Vyzerá to, že veľa liniek. Ale je to krásne jednoduché. Ak chcete implementovať funkciu volal hľadanie, ktorého zmysel života je hľadať hodnotu ako je N, celé číslo, a ty si prešiel v jednom pointer-- ukazovateľ na uzol koreňov, skôr z toho stromu, z ktorého môžete pristupovať všetko ostatné, Všimnite si, ako priamočiaro môžete implementovať logiku. Ak je strom je null, samozrejme, že to tam nie je. Povedzme, vráti false. Je to tak? Ak to ruky nič, tam nič nie je. 

Inak, ak n je menšia než strom šípka n- teraz šípka n, spomínam sme zaviedli Super Krátko na druhý deň, a to len znamená, že de-referencie ukazovateľ a pozrite sa na polia s názvom n. Takže to znamená, tam a pozrite sa na polia s názvom n. Takže ak n, hodnota, ktorú ste daný, je menej ako hodnota v korunách stromov číslo, kam chcete ísť? Doľava. 

Takže si všimnúť rekurziu. Ja returning-- nie je pravda. Nie false. Vraciam sa bez ohľadu na odpoveď je z volanie seba, okolo opäť n, ktorá je nadbytočná, ale to, čo je teraz trochu inak? Ako mám robiť problém menšie? Som odovzdaním ako druhý Tvrdenie nie je koreň stromu, ale ľavá dieťa v tomto prípade. Takže som okolo v ľavom dieťaťa. 

Medzitým, ak n je väčšie ako uzol Som v súčasnosti pri pohľade na, Som hľadať na pravej strane. Inak, v prípade, že strom nie je null, a V prípade, že prvok nie je doľava a nie je to na pravej strane, čo je nádherne prípad? Sme skutočne našli uzol v otázka, a tak sme sa vrátiť true. 

Tak sme práve poškriabaný povrch teraz niektoré z týchto dátových štruktúr. V problém nastaviť päť budete preskúmať tieto ešte ďalej, a budete mať váš návrh Voľba, ako ísť o to. Čo by som chcel na záver o je len 30 sekúnd teaser o tom, čo čaká budúci týždeň a mimo nej. 

Ako sme begin-- našťastie by ste mohli think-- náš prechod pomaly zo sveta C a nižšej detaily implementácie na úrovni, do sveta, v ktorom si môžeme pre samozrejmé, že niekto iný má konečne realizované tieto údaje štruktúry pre nás, a začneme chápať reálny svet prostredníctvom vykonávacích web-based programy a Webové stránky všeobecne a tiež veľmi bezpečnostné dôsledky, ktoré sme len začal poškriabať povrch. Tu je to, čo nás čaká v najbližších dňoch. 

[VIDEO PREHRÁVANIE] 

-Je Prišiel so správou, s protokolom všetci jeho vlastné. Prišiel na svet krutý firewally, routery, bezcitný a nebezpečenstvo ďaleko horšie ako smrť. Je rýchly. On je silný. Je to TCP / IP, a on má svoju adresu. "Bojovníci siete." [END Videoprehrávanie] DAVID Malan: Už budúci týždeň. Uvidíme sa potom. [VIDEO PREHRÁVANIE] -A Teraz, "hlboké myšlienky" od Daven Farnham. -David Vždy začína prednášky sa, "v poriadku." Prečo nie, "Tu je riešenie na tento týždeň problém set " alebo "Dávame všetky z vás?" [Smiech] [END Videoprehrávanie]