Reproduktor 1: Dobre, takže to je CS50 To je koniec týždňa päť. A pripomenúť, že minule sme začal hľadať na chovateľa dát štruktúry, ktoré začali riešiť problémy, ktoré začali zavádzať nové problémy, ale, ktorého by malo bol druh závitom, ktoré sme začal robiť z uzla do uzla. Takže to je samozrejme single previazaný zoznam. A jednotlivo prepojené, Myslím, že je len jeden závit medzi každý z týchto uzlov. Ukázalo sa, že môžete robiť milovník veci, ako je dvojnásobne spojových zoznamov kedy máte šípku sa v oboch smeroch, čo môže pomôcť s niektorými účinnosťou. Ale tento problém vyriešil? Aký problém sa to vyriešiť? Prečo sa staráme v pondelok? Prečo, teoreticky, sa staráme v pondelok? Čo to robí? 

Divákov: Môžeme dynamicky zmeniť jeho veľkosť. 

Reproduktor 1: OK, tak môžeme dynamicky zmeniť jeho veľkosť. Výborne vás oboch. Takže môžete dynamicky meniť veľkosť tejto štruktúra dát, zatiaľ čo pole, Pripomeňme, musíte vedieť priori, koľko miesta chcete a ak budete potrebovať trochu viac priestor, ste trochu smolu. Musíte vytvoriť úplne nové pole. Musíte presunúť všetky vaše dáta z jedného na druhého, nakoniec oslobodil starý poľa ak je to možné, a potom pokračujte. Ktorá sa práve cíti veľmi nákladné a veľmi neefektívne, a v skutočnosti, že môže byť. Ale to nie je všetko dobré. Platíme cenu, čo bol jeden z viac zjavné ceny my zaplatiť pomocou prepojeného zoznamu? 

Divákov: Musíme použiť dvojitý priestor pre každú z nich. Reproduktor 1: Jo, takže potrebujeme najmenej dvakrát toľko priestoru. V skutočnosti, som si uvedomil, tento obrázok je dokonca aj trochu zavádzajúce, pretože na CS50 IDE v mnohých moderných počítače, ukazovateľ alebo adresa nie je v skutočnosti štyri bajty. Je to veľmi často títo dni osem bajtov, ktoré znamená, že spodná časť najviac obdĺžniky tam v skutočnosti sú trochu dvakrát veľký ako to, čo som sa vyvodiť, čo znamená, že používate trikrát ako veľký priestor, ako by sme mať inak. Teraz v rovnakej dobe, my sme stále hovoril bytov, nie? My nie nutne hovoriť megabajty alebo gigabajty, ak niet týchto údajov štruktúry dostať veľký. 

A tak dnes začneme uvažovať ako by sme mohli preskúmať údaje efektívnejšie, ak v Skutočnosť, dáta dostane väčší. Ale poďme sa pokúsiť sa získať kanonické operácia prvý že si môžete robiť na tieto druhy dátových štruktúr. Takže niečo ako pripojený Zoznam všeobecne podporuje operácie, ako zmazať, vložiť a vyhľadávanie. A čo mám na mysli, že? To jednoducho znamená, že obvykle, ak ľudia používate spájať zoznam, oni alebo niekto iný zaviedla funkcie ako mazať, vkladať, a vyhľadávania, takže môžete skutočne niečo robiť užitočné so štruktúrou dát. Takže poďme sa rýchlo pozrieť na to, ako by sme mohli realizovať nejaký kód pre prepojenom zoznamu takto. 

Tak to je len niektoré C kód, Ani kompletný program že som naozaj rýchlo rozdúchala. Nie je to on-line v distribúcii kód, pretože to nebude v skutočnosti spustiť. Nevšimnúť som len s komentár povedal, dot dot bodka, je tu niečo, tam, dot dot dot, niečo, čo tam. A nech to len pozrieť na aké sú šťavnaté diely. Takže na linke tri, Pripomíname, že toto je teraz sme navrhli deklarovať uzol posledný čas, jeden z týchto obdĺžnikových objektov. Má int, že budeme volať N, ale my sme to mohli nazvať čokoľvek, a potom struct uzol hviezdu zvanú ďalšie. A len aby bolo jasno, že druhým linka, na linke šesť, čo to je? Čo to robí pre nás? Vzhľadom k tomu, to určite vyzerá viac mystický než naše obvyklé premenné. 

Divákov: To robí to pohybovať po jednom. 

Reproduktor 1: Tak to je pohybovať po jednom. A aby som bol presnejší, to bude ukladať adresu uzla, ktorý je určený na sémanticky vedľa nej, že jo? Takže to nebude nutne presunúť nič. Je to len bude uloženie hodnoty, čo je bude adresa nejakého iného uzla, a to je dôvod, prečo sme povedali struct uzol hviezda, hviezda označujúca ukazovateľ alebo adresa. OK, tak teraz, ak predpokladáme, že máme tento N ktoré máme k dispozícii, a poďme Predpokladajme, že niekto iný má vložené veľa celých čísel do prepojeného zoznamu. A to spájať zoznam je ukázal na nejakým bodom premenná s názvom zoznam, ktorý je prešiel v tu ako parameter, ako mám ísť o linky 14, ktorým sa vykonáva vyhľadávanie? Inými slovami, keď som sa vykonáva funkcie, ktorej účel života je vziať int a potom sa začiatok prepojeného zoznamu, že je ukazovateľ na spájať zoznam. Ako prvý, kto sa myslím, že David Bol to náš dobrovoľník v pondelok, ukazoval na celý spájať zoznam, je to, ako by sme odovzdávate David sa ako naši argumentáciu tu. Ako môžeme ísť o rolovaním tento zoznam? No, to ukáže, že aj napriek tomu, ukazovatele sú relatívne nové teraz na nás, to, čo môžeme urobiť relatívne priamočiaro. 

Chystám sa ísť dopredu a deklarovať dočasnú premennú, ktorá konvencií sa len tak byť nazývaný ukazovateľ, alebo PTR, ale ste to mohli nazvať, čo chcete. A ja idem na inicializovať že na začiatok zoznamu. Takže sa môžete trochu myslieť na to ako sa ma učiteľ na druhý deň, druh ukázal na niekoho medzi našimi ľuďmi ako dobrovoľníci. Takže som dočasné premenné, ktoré je len ukazuje na rovnakú vec že naše zhodou okolností s názvom dobrovoľník David bol tiež poukázať. Teraz, keď je ukazovateľ Nie je null, pretože odvolanie že null je nejaký špeciálny hliadka hodnota vymedzuje koniec zoznamu, takže zatiaľ čo ja nie som ukazuje na zem ako náš posledný dobrovoľníka bol, poďme do toho a vykonajte nasledujúce. Ak pointer-- a teraz som trochu chcem robiť to, čo sme robili so študentom structure-- ak ukazovateľ bodka ďalšie equals-- skôr, ak je ukazovateľ dot N sa rovná sa rovná premenná N sa Argument, že to už prešiel v, potom chcem ísť dopredu a hovoria, vráti hodnotu true. Zistil som, že číslo N vnútro jeden z uzlov môjho spojovaceho zoznamu. Ale bodka už pracuje v tejto súvislosti, pretože ukazovateľ, PTR, je skutočne ukazovateľ, adresu, sme vlastne možné nádherne použite konečne kus syntaxe že druh značiek intuitívne zmysel a vlastne použiť šípky tu, čo znamená, že ísť od že adresa na celé číslo tam v. Takže je to veľmi podobné duch operátorom bodky, ale preto, že ukazovateľ nie je ukazovateľ a nie skutočný struct sám o sebe, sme práve pomocou šípky. 

Takže v prípade, že aktuálne uzol, že I je dočasná premenná, som ukázal na nie je N, čo chcem robiť? No, s mojimi ľudských dobrovoľníkoch že sme tu mali na druhý deň, keď je moja prvá človek nie je ten, ktorý som chcú, a možno druhý človek nie je jediná, ktorú chcem, a tretí, som je potrebné, aby fyzicky v pohybe. Ako ako môžem prechádzať zoznamom? Keď sme mali celý rad tí, práve urobil ako ja a navyše plus. Ale v tomto prípade, stačí robiť ukazovátko, dostane, ukazovateľ, ďalšie. Inými slovami, ďalšie pole je rovnako ako všetky ľavých rúk že naša ľudská dobrovoľníci v pondelok boli pomocou poukázať na nejakom inom uzla. Tí, ktorí boli ich ďalší susedia. 

Takže ak chcem krokovať tohto zoznamu, Nemôžem jednoducho ja a navyše už, Namiesto toho musím povedať, Ja, ukazovateľ, sa deje rovnať bez ohľadu na ďalšie pole, Ďalšie pole je, ďalšie pole, po všetkých tých ľavej ruke že sme mali na javisku polohovacie niektorých ďalších hodnôt. A keď som si cez že celá iterácie, a napokon, som narazila null nemať nájdených N napriek tomu, len som return false. Takže znova, všetko, čo tu robíme, podľa obrázku pred chvíľou, začína poukazom na rokovaní začiatok zoznamu pravdepodobne. A potom som skontrolovať, je hodnota Hľadám rovná deväť? Ak áno, vráťte som pravda a ja som urobil. Ak nie, môžem aktualizovať svoju ruku, AKA ukazovateľ na bod v mieste budúcej Arrow, a potom umiestnenie pri budúcom Arrow, a ďalšie. Ja som jednoducho prechádza tomto poli. 

Takže znova, koho to zaujíma? Rovnako ako to, čo je to zložka pre? No, pripomenúť, že sme zaviedli pojem stohu, ktorý je abstraktné dátový typ, ak je to nie je vec C, to nie je CS50 vec, je to abstraktné nápad, táto myšlienka stohovanie veci na vrchole jedného iný , Ktoré môžu byť vykonávané v zväzky rôznych spôsobov. A jeden spôsob, ako sme navrhovali bol s poľa, alebo s prepojeného zoznamu. A ukázalo sa, že kánonicky, je stack podporuje najmenej dve operácie. A buzz slová sú tlačiť, aby tlačiť niečo do zásobníka, ako nový zásobník v jedáleň, alebo pop, čo znamená, že za účelom odstránenia vrchnej zásobník zo zásobníka v jedálni hala, a potom možno niektorí ďalšie operácie rovnako. Tak ako môžeme definovať štruktúru že sme teraz volá hromadu? 

No, máme všetci sú k dispozícii požadované syntax máme k dispozícii v C. hovorím, Dajte mi definíciu typu pre struct vnútri zásobníka, Ja som chcel povedať, je pole, na celá rada čísel a potom veľkosť. Takže inými slovami, keď budem chcieť na vykonanie tohto v kóde, nechaj ma ísť, a tak nejako kresliť, čo to hovorí. Tak to hovorí, daj mi štruktúra, ktorá má polia, a ja neviem, čo je kapacita, Je to vraj nejaká konštanta, že som definovaná na inom mieste, a to je v poriadku. Predpokladajme však, že je to len jeden, dva, tri, štyri, päť. Takže kapacita je 5. Tento prvok vnútri mojej štruktúra bude volané čísla. A potom som potrebovať iné premenné zrejme volal formát, ktorý pôvodne idem stanoviť je inicializovaný na nulu. Pokiaľ nie je nič v zásobník, veľkosť je nula, a to je hodnoty odpadkové v číslach. Nemám potuchy, čo je tam ešte nie. 

Takže ak chcem, aby sa zasadila niečo do zásobníka, Predpokladám, že volanie funkcie Push, a Hovorím tlačiť 50, ako číslo 50, kde by ste navrhli Kreslím to v tomto poli? K dispozícii je päť rôznych možných odpovedí. Kam chcete tlačiť číslo 50? V prípade, že cieľom tu, opäť, zavolajte funkcie Push, odovzdať argument 50, kde mám dať? Päť possible-- 20% šanca hádať správne. Ano? 

Divákov: Ďaleko vpravo. 

Reproduktor 1: Úplne vpravo. Tam je teraz 25% šanca hádať správne. Tak, že by vlastne v poriadku. Podľa konvencie, poviem s radom, by sme všeobecne začať na ľavej strane, ale mohli by sme určite začať na pravej strane. Takže spojler by tu bolo, že som pravdepodobne bude čerpať ju na ľavej strane, rovnako ako v normálnom poli kde Aj začať chodiť zľava doprava. Ale ak môžete prevrátiť aritmetický, v poriadku. Je to jednoducho nie je konvenčné. OK, musím urobiť jednu ďalšia zmena hoci. Teraz, keď som tlačil niečo do zásobníka, čo bude ďalej? 

Dobre, musím zvýšiť veľkosť. Tak nechaj ma ísť dopredu a len je aktualizuje, ktorý bol nulový. A namiesto toho teraz, idem aby v hodnote jedna. A teraz, že som tlačiť ďalšie Číslo do zásobníka, rovnako ako 51. No, musím urobiť ešte jeden zmena, ktorá je až do veľkosti dve. A potom, že som tlačiť ešte jeden Číslo do zásobníka, ako je 61, teraz musím aktualizovať veľkosti jeden čas, a získať hodnotu 3 ako veľkosť. A teraz, že som zavolať pop. Teraz pop, podľa konvencie, neberie argument. So zásobníkom, celý bod metafory zásobníka je to, že nemáte priestor na voľnú úvahu ísť dostať, že zásobník, môžete všetko, čo urobiť je pop jeden z najvrchnejšiu zásobníka, len preto, že. To je to, čo táto dátová štruktúra robí. 

Takže touto logikou, keby som hovoriť pop, čo príde? Tak 61. Takže to, čo naozaj je počítač, robiť v pamäti? Čo môj kód musíte urobiť? Čo by ste navrhli meníme na obrazovke? Čo by sa malo zmeniť? Prosím? Tak sme sa zbaviť 61. Tak som si rozhodne urobiť. A môžem zbaviť 61. A potom to, čo ostatní Zmena sa má stať? Veľkosť má pravdepodobne vrátiť sa do dvoch. A tak to je v poriadku. Ale počkajte chvíľu, veľkosť pred chvíľou bol tri. Poďme sa len urobiť rýchlu kontrolu zdravý rozum. Ako to vieme, že sme chcel sa zbaviť 61? Vzhľadom k tomu, že sme praskanie. A tak som túto druhú veľkosť majetku. 

Počkaj, ja som spomínal na dve týždeň keď sme začali hovoriť o pole, kam toto miesto nula, toto bolo umiestnenie jedného, ​​toto bolo umiestnenie dve, to je umiestnenie troch, štyroch, to vyzerá ako vzťah medzi veľkosťou a prvok, že chcem odstrániť z poľa sa zdá byť len to, čo? Veľkosť mínus jedna. A tak to je, ako ako ľudia vieme, že šesťdesiat jedna je na prvom mieste. Ako to, že počítač bude vedieť? Keď váš kód, kde na vás pravdepodobne chcete urobiť veľkosť mínus jedna, takže tromi mínus jedna sú dve, a to znamená, že chceme zbaviť 61. A potom môžeme skutočne aktualizovať tak, aby veľkosť veľkosť teraz ide z troch na púhe dva. A len preto, aby pedantská, idem navrhnúť, že som urobil, že jo? Tie navrhovanej intuitívne správne by som mal zbaviť 61. Ale nemám ja druh nejako zbavili 61? Ja som skutočne zabudol že je to vlastne tam. A myslíte, že späť do PSET4, ak ste dočítali Článok o forenznej, PDF že sme mali chlapci čítať, alebo si bude čítať tento týždeň PSET4. Pripomeňme, že je to vlastne relevantné k celá myšlienka počítačovej forenznú. Čo je počítač zvyčajne robí, je to jednoducho zabudne, kde je niečo, ale to nie je ísť a podobne pokúsiť sa poškriabať, alebo ovládanie tie kúsky s núl a jednotiek alebo nejaký iný náhodný vzor ak vy sám to zámerne. Takže vaše intuícia bola Dobre, poďme sa zbaviť 61. Ale v skutočnosti, my nemusíme obťažovať. Potrebujeme len zabudnúť, že je to tam zmenou nášho veľkosť. 

Teraz je tu problém s zásobníka. Keby som neustále tlačí veci do zásobníka, čo je zrejme bude diať len v niekoľko okamihov čase? Budeme chýbať priestor. A čo budeme robiť? Sme trochu v háji. Táto implementácia neumožňuje us zmeniť veľkosť poľa, pretože použitie Táto syntax, ak ste Spomeňte si na dvoch týždňov, potom, čo ste vyhlásili, veľkosť poľa, sme nevideli mechanizmus napriek tomu, kde môžete zmeniť veľkosť poľa. A skutočne C nemá túto funkciu. Keď poviete, daj mi päť NTHS, im hovoria čísla, to je všetko, budete si to. Takže teraz budeme robiť od pondelka, má schopnosť vyjadrovať riešenie aj keď, len je potrebné štípnout definícia nášho stohu nebyť nejaký pevne poľa, ale len preto, aby uložiť adresy. 

Teraz, prečo je to? Teraz len musíme byť pohodlné s skutočnosť, že keď môj program beží, Ja pravdepodobne bude sa opýtať človeka, koľko čísel uložiť? Takže vstup má prísť odniekiaľ. Ale akonáhle ja viem, že číslo, potom môžem len použiť to, čo funkciu, čím sa získa mi kus pamäte? Môžem použiť malloc. A môžem povedať, ľubovoľný počet bajtov Chcem späť na tieto NTHS. A všetko, čo mám skladovať v číslach variabilný tu vnútri tohto struct by malo byť to, čo? Čo je to vlastne ide do Čísla v tomto prípade? Jo, ukazovateľ na prvý bajt tohto kusu pamäti, alebo viac špecificky, adresa z prvej z týchto bajtov. Nezáleží na tom, či je to jedno byte alebo miliarda bajtov, Len musím starať o prvý. Vzhľadom k tomu, čo malloc záruky a môj operačný systém zaručuje, je to, že kus pamäte I si, že to bude byť súvislé. Je tu nebude medzery. Takže ak som požiadal o 50 bajtov alebo 1000 bajtov, oni sú všetci bude chrbtom k sebe k sebe. A tak dlho, ako si spomínam, ako veľký, ako moc som požiadal o, všetko, čo potrebujem vedieť Je to prvá takáto adresa. 

Takže teraz máme možnosť v kóde. Hoci, že to bude trvať nás viac času písať toto hore, sme teraz mohli prerozdeliť, že pamäť Len uloženie inú adresu tu Ak chceme väčší, alebo dokonca menšie kus pamäte. Takže tu na kompromis. Teraz sme si dynamiku. Stále máme contiguousness som tvrdil. Vzhľadom k tomu, malloc bude nám susediace kus pamäte. Ale toto je bude bolesť v krk pre nás, programátor, skutočne kód hore. Je to jednoducho viac práce. Potrebujeme kód podobný tomu, čo som bol búchanie sa pred chvíľou. Veľmi realizovateľné, ale pridáva zložitosť. A tak developer čas, programátor Doba je ďalším zdrojom že by sme mohli musieť stráviť nejaký čas, aby sa nové funkcie. A potom samozrejme je tu front. Nebudeme ísť do toho človek v veľa detaile. Ale je to veľmi podobné duchu. Mohol by som implementovať frontu, a jej zodpovedajúce operácie, Pridať do zoznamu alebo dequeue, ako je pridať alebo odstrániť, je to len milovník spôsob, ako povedať to, Pridať do zoznamu alebo dequeue takto. Môžem len dať sám struct má celý rad celú radu, že opäť, má to znova veľkosť, ale prečo teraz potrebujem sledovať predné fronty? Nepotreboval som vedieť predné môjho stacku. No, keď som znovu pre queue-- Poďme sa len ťažko kódovať to ako mať ako päť celé čísla v potenciálne tu. Takže to je nula, jedna, dva, tri, štyri. To bude znovu zavolal čísla. A to sa bude nazývať veľkosť. 

Prečo nie je dostačujúce mať len veľkosť? Dobre, poďme stlačte tie isté čísla na. Tak som pushed-- I enqueued, alebo tlačil. Teraz budem Zaradí 50, a potom 51, a potom 61, a dot dot dot. Tak to je Enqueue. Aj enqueued 50, potom 51, potom 61. A to vyzerá totožne do komína tak ďaleko, okrem Ja potrebné, aby sa jednu zmenu. Musím aktualizovať tejto veľkosti, takže idem od nuly do jedného na dva až tri teraz. Ako môžem dequeue? Čo sa stane s dequeue? Kto by mal prísť z tohto zoznamu ako prvý ak je to linka na Apple Store? Tak 50. Takže je to trochu zložitejšie tentoraz. Vzhľadom k tomu, naposledy to bol výborný ľahké proste veľkosť mínus jedna, Aj dostať na konci svojho poľa účinne kde čísla sú, odoberie 61. Ale ja nechcem, aby odstrániť 61. Chcem sa 50, ktorý Bol tam v 5:00 hodín na line up pre Nový iPhone alebo ktovie čo ešte. A tak, ako sa zbaviť 50, I Nemôžete jednoducho to urobiť, nie? Môžem vyškrtnúť 50. Ale my sme povedali len nemusí byť tak análny ako na zelenej lúke, alebo skryť dáta. Môžeme len zabudol, kde to je. 

Ale keď zmením veľkosť teraz dva, je to dostatočné informácie vedieť, čo sa deje v mojom fronte? Ani nie. Rovnako ako moja veľkosť je dva, ale kde sa front začína, najmä pokiaľ Stále mám tá rovnaké čísla v pamäti. 50, 51, 61 |. Tak som treba mať na pamäti, Teraz, keď je predné. A tak, ako som navrhla hore tam budeme práve volal Nth predné, ktorých pôvodná hodnota by mala byť čo? Zero, len začiatok zoznamu. Ale teraz okrem dekrementování veľkosť, práve sme zvýšiť predné. A teraz je tu ďalší problém. Takže akonáhle som sa ísť ďalej. Predpokladajme, že sa jedná o počet ako je 121, 124, a potom sa, sakra, Som z vesmíru. Ale počkajte, ja nie som. Takže v tomto bode príbehu, Predpokladajme, že veľkosť je jeden, dva, tri, štyri, tak predpokladať, že veľkosť je štyri, predné je jedna, takže 51 je na prednej strane. Chcem dať iné číslo tu, ale, sakra, ja som z vesmíru. Ale ja nie som, že jo? Tam, kde som mohol dať nejaké ďalšie hodnoty, ako je 171? Jo, mohol by som len tak vrátiť sa tam, že jo? A potom vyškrtnúť na 50, alebo jednoducho ho prepísať s 171. A ak ste premýšľal, prečo náš počet sa dostal tak náhodný, Títo sú obyčajne prijatá počítač prírodovedné predmety na Harvarde po CS50. Ale to bol dobrý optimalizácie, pretože teraz som to plytvanie miestom. Stále mám na pamäti, ako veľká tá vec je totálna. Je to celkom piatich. Pretože nechcem, aby začať prepisovanie 51. Takže teraz som ešte z vesmíru, takže rovnaký problém ako predtým. Ale môžete vidieť, ako teraz v kóde, budete pravdepodobne musieť trochu písať viac zložitosť, aby sa to stalo. A v skutočnosti to, čo operátor v C pravdepodobne umožňuje budete magicky urobiť kruhovitosť? Jo, operátor modulo, znak percenta. Takže to, čo je paráda asi frontu, aj keď sme udržať kreslenie poľa ako tieto, ako rovných čiar, ak ste trochu premýšľať o tom, ako zakrivenie okolo ako kruh, potom stačí intuitívne to trochu funguje mentálne Myslím si, že trochu viac čisto. Tie by sa ešte musí zaviesť že mentálne model v kóde. Takže nie je tak ťažké, nakoniec, implementovať, ale stále stratiť size-- trochu, schopnosť zmeniť veľkosť, ak to urobíme. 

Musíme sa zbaviť poľa, my ho nahradiť jediným ukazovateľom, a potom sa niekde v mojom kóde mám Príjem volania, akú funkciu skutočne vytvoriť pole volaných čísel? Malloc, alebo nejaký podobný funkcie, presne tak. Akékoľvek otázky týkajúce komínov alebo frontoch. Jo? Dobrá otázka. Čo modulo by ste použili tu. Takže všeobecne, pri použití mod, mali by ste to urobiť s veľkosťou Celá štruktúra dát. Takže niečo ako päť alebo kapacity, ak je to je konštantná, je pravdepodobne zapojený. Ale len to, modulo päť asi nie je dostačujúce, pretože musíme vedieť my zábal okolo tu alebo tu alebo tu. Takže vy ste pravdepodobne tiež bude chcieť zapojiť veľkosť veci, alebo predné premenné rovnako. Takže je to práve tento pomerne prostý aritmetický výraz, ale modulo bude kľúčovou zložkou. 

Tak krátky film ak chcete. Animácie, že niektoré ľudia na inej vysokej škole dal dohromady, že máme prispôsobené pre túto diskusiu. To zahŕňa Jack Učenie fakty o frontoch a štatistiky. 

FILM: Kedysi dávno, tam bol chlapík menom Jack. Keď došlo k tomu, že priatelia, Jack nemal talent. Takže Jack šiel hovoriť s najpopulárnejšie chlapec vedel. On išiel do Lou a spýtal sa, čo mám robiť? Lou videl, že jeho priateľ bol naozaj zúfalý. No, on začal, len pozrite sa, ako ste oblečený. Nemáte žiadne šaty s iným pohľadom? Áno, povedal Jack. Som si istý, áno. Poď do môjho domu a Ukážem vám ich. A tak išli preč, aby Jack. A Jack ukázal na políčko lou kde on držal všetky svoje košele, a jeho nohavice, a jeho ponožky. Povedal Lou, vidím, že máte Všetky vaše oblečenie v hromadu. Prečo ste nosiť nejaké iní raz za čas? 

Povedal Jack, dobre, keď som odstrániť oblečenie a ponožky, Aj umyť je a dal je preč v krabici. Potom príde budúci ráno, a ja si hop. Chodím do boxu a získať moje oblečenie z vrcholu. Lou rýchlo si uvedomil, problém s Jackom. Stále oblečenie, CD, a knihy v zásobníku. Keď sa dostal na niečo na čítanie alebo opotrebenia, že by si vybrať horný knihu alebo spodná bielizeň. Potom, keď bol hotový, by dal to späť. Back to pôjde, na vrchole zásobníka. Viem, že riešenie, povedal víťazný Loud. Musíte sa naučiť začať používať front. Lou vzal Jackovej šaty a zavesil ich do skrine. A keď vyprázdnil krabice, proste hodil. 

Potom povedal, teraz Jack, na konci roka deň, dať svoje oblečenie na ľavej strane keď dal je preč. Potom sa zajtra ráno, keď vás vidieť slnko, dostať svoje šaty Na pravej strane, od konca riadku. Copak nevidíš? povedal Lou. Bude to tak pekné. Budete nosiť všetko raz Než budete nosiť niečo dvakrát. A so všetkým v frontoch v jeho skrini a policou, Jack začal cítiť celkom istý sám sebou. Všetky vďaka Lou a Jeho úžasné front. Reproduktor 1: Dobre, to je rozkošný. Takže to, čo sa v skutočnosti deje Na pod pokrievku teraz? Že máme ukazovatele, že máme malloc, že máme schopnosť vytvárať kusy pamäte pre seba dynamicky. Takže toto je obrázok sme zazrel len druhý deň. My sme naozaj prebývať na to, ale tento obrázok má sa deje pod odsávač niekoľko týždňov. A tak to znamená, len obdĺžnik, ktorý sme vyvodiť, pamäte počítača. A možno váš počítač, alebo CS50 ID, má gigabajt pamäte alebo RAM alebo dva gigabajty alebo štyri. Je to naozaj nezáleží. Váš operačný systém Windows alebo Mac OS či Linux, v podstate umožňuje program myslieť si, že má prístup na celý rozsah pamäť počítača, aj keď by ste mohli byť spustený viac programov naraz. Takže v skutočnosti, že v skutočnosti nefunguje. Ale je to trochu ilúzia venovať všetky svoje programy. Takže ak ste mali dva koncerty RAM, toto je, ako sa počítač môže myslieť na to. 

Teraz náhodne, jeden z nich veci, jeden z týchto segmentov pamäti, sa nazýva zásobník. A skutočne kedykoľvek tak ďaleko v písaní kódu že ste volal funkcie, napríklad main. Pripomeňme si, že kedykoľvek som Pamäť Drawn počítače, Vždy som tomu nejako polovica z obdĺžnika tu a neobťažujú hovoriť o tom, čo je vyššie. Pretože keď je hlavná volal, tvrdím, že ste si to plátok pamäti že ide sem dole. A ak hlavná volal funkcie ako odkladací priestor, dobre odkladacie ide tu. A ukázalo sa, že je to kde je to končí. Na takzvaný stoh vnútornej pamäte vášho počítača. Teraz sa na konci dňa, to je len adresy. Je to ako bajt nula, Byte jedného, ​​byte 2000000000. Ale či si myslíte, že o tom ako je obdĺžnikový objekt, všetko robíme každý Doba hovoríme funkcie vrstvenie nový rez pamäte. Dávame túto funkciu plátok zo svojej vlastnej pamäte pre prácu s. 

A teraz pripomínajú, že je to dôležité. Vzhľadom k tomu, keby sme sa niečo ako odkladací priestor a dve lokálne premenné, ako je A a B a zmeníme tieto hodnoty z jednej a dvoch na dva a jeden, odvolanie že keď sa vráti swapu, je to, ako by tento plátok pamäte je jednoducho preč. V skutočnosti, je to stále tam forenzných. A niečo je ešte v skutočnosti tam. Ale koncepčne, je to, ako aj keď je to úplne preč. A tak hlavné nepozná žiadnu z prác ktorá bola vykonaná v tejto funkcii odkladacieho ak je to vlastne prešiel v tých Argumenty ukazovateľom alebo odkazom. Teraz, základné riešenie k tomuto problému s swapu je okolo veci podľa adresy. Ale ukazuje sa, taky, čo je sa deje nad túto časť obdĺžnika celú dobu je Ešte je tu viac pamäte tam hore. A keď dynamicky alokovať pamäť, či už je to vo vnútri getString, ktorý sme robili pre vás v CS50 knižnica, alebo či vy zavolať a opýtať sa malloc operačný systém pre kus pamäť, nepochádza zo zásobníka. To pochádza z iného miesta v pamäti počítača Tomu sa hovorí haldy. A to nie je nič iné. Je to rovnaké RAM. Je to rovnaká pamäť. Je to len RAM, ktorý sa deje tam miesto tu dole. 

A tak čo to znamená? No, ak má počítač konečné množstvo pamäte a zásobník sa vyrastal, takže hovoriť, a haldy, podľa k tejto šípky, rastie nadol. Inými slovami, každý Čas hovoru malloc, ste daná plátok pamäte zhora, potom možno o niečo nižšia, a potom trochu nižšia, zakaždým, keď budete volať malloc, haldy, je to použitie, je druh rastie, rastie bližšie a bližšie k čomu? Stoh. Takže to zdá ako dobrý nápad? Mám na mysli, ak to nie je naozaj jasné, čo iného môžete robiť, keď len majú obmedzené množstvo pamäte. Ale to je určite zlé. Tieto dva šípy sú na Rýchlokurz jeden o druhého. 

A ukázalo sa, že zlý človek, ľudí, ktorí sú veľmi dobré s programovaním, a snaží sa preniknúť do počítačov, môžete využiť túto skutočnosť. V skutočnosti, uvažujme trochu úryvok. Takže toto je príklad si môžete prečítať o podrobnejšie na Wikipédii. Budeme bod, ktorý u článku, ak zvedavý. Ale je tu útok všeobecne známy ako pretečeniu vyrovnávacej pamäti, že existuje tak dlho, ako u ľudí mali schopnosť manipulovať pamäť počítača, a to najmä v C. Tak to je veľmi ľubovoľný program ale poďme ju prečítať zdola nahor. Hlavná do argc char hviezdy argv. Takže je to program, ktorý berie argumenty príkazového riadku. A všetky hlavné robí zrejme je výzva funkcie, hovoria F pre jednoduchosť. A to prejde v čom? Argv jedného. Tak to prechádza do F čokoľvek slovo je, že používateľ zadaný do príkazového riadku po vyrobení Názov programu vôbec. Takže rovnako ako Caesar alebo Vigener, ktorý môžete pripomenúť robíte s argv. 

Takže to, čo je F? F sa v reťazci ako jeho jediný argument AKA char hviezda, rovnaká vec, ako reťazec. A je to len svojvoľne bar v tomto príklade. A potom char c 12, len v Laicky povedané, čo je char c držiak 12 robí pre nás? Čo to robí? Prideľovanie pamäte, konkrétne 12 bytov pre 12 znakov. Presne tak. A potom posledný riadok, zamiešať a kopírovanie, pravdepodobne ste ešte nevideli. To je reťazec kópia funkcie, ktorej účel života je skopírovať svoj druhý argument do prvý argument, ale iba do určitý počet bajtov. Takže tretí argument hovorí, koľko bajtov by ste mali kopírovať? Dĺžka tyče, bez ohľadu na užívateľ zadal. A obsahu bar, tento reťazec, sú skopírované do pamäte ukázal na pri ° C 

Takže to vyzerá trochu hlúpe, a to je. Je to neprirodzený príklad, ale je to zástupca triedy vektorov útoku, spôsob, ako útočiť program. Všetko je v poriadku a dobré, ak užívateľ Typy v slovách, ktorá je 11 znakov alebo menej, plus spätné lomítko nula. Čo keď používateľ zadá vo viac ako 11 alebo 12 alebo 20 alebo 50 znakov? Čo je tento program bude robiť? Potenciálne seg chyba. Ide to slepo kopírovať všetko, čo v bare hore k jeho dĺžke, čo je doslova všetko, čo v bare, do adresného ukázal na C. Ale ° C má len preventívne uvedený ako 12 bajtov. Ale nie je ďalšiu kontrolu. Ak nie je podmienkach. Neexistuje kontrola tu žiadna chyba. 

A tak to, čo je tento program chystá urobiť, je len slepo kopírovať jednu vec na druhú. A tak, keď čerpáme to ako obrázok, tu je len trieska pamäťového priestoru. Tak si všimnúť na dne, sme majú lokálne premenné bar. Tak, aby ukazovateľ, ktorý to bude store-- skôr to, že miestne argumentu, ktorý je bude ukladať reťazec bar. A potom si všimnúť len nad ňou v stohu, pretože zakaždým, keď sa pýtate pre pamäť na zásobníku, to ide trochu nad ňou obrazovo, Všimnite si, že máme 12 bajtov tam. V ľavom hornom z nich je C držiak nula a vpravo dole nich je C držiak 11. To je len, ako sa počítače chystá položiť ju von. Takže len intuitívne, pokiaľ bar má viac ako 12 znakov celkom, vrátane spätné lomítko nula, kde je 12 alebo C držiak 12 ísť? Alebo skôr, kde je 12. znak alebo 13. znak, sté postava ísť skončiť na obrázku? Nad alebo pod? 

Správne, pretože aj keď stoh sám rastie nahor, akonáhle ste dal veci do to, že z konštrukčných dôvodov, kladie pamäť od zhora nadol. Takže ak máte viac ako 12 bajtov, budete začať prepísať bar. Tak to je chyba, ale je to nie je naozaj veľký problém. Ale je to veľký problém, pretože tam je viac vecí sa deje v pamäti. Takže tu je návod, ako by sme mohli dal ahoj, aby bolo jasné. Ak som napísal v ahoj na príkazovom riadku. H-E-L-L-O backslash nula, končí v rámci tieto 12 bajtov, a my sme výborný bezpečia. Všetko je v poriadku. Ale ak píšem niečo dlhšie, prípadne je to chystá vplížit do baru priestoru. Ale ešte horšie, to dopadá out celú tú dobu, aj keď sme sa nikdy nehovoril o to, zásobník sa používa pre iné veci. Nie je to len lokálne premenné. 

C je veľmi nízka úroveň jazyka. A to tak nejako tajne používa zásobník tiež mať na pamäti, keď sa Funkcia je volaná, čo je adresa z predchádzajúcej funkcie, tak to môže skočiť späť na túto funkciu. Takže keď hlavné výzvy výmene, medzi veci tlačil do fronty nie sú len swapy lokálne premenné, alebo jej argumenty, tiež tajne tlačil do zásobníka, ako je znázornené červeným rezu tu, je adresa hlavného fyzicky v pamäti počítača, tak, že keď je odkladacia vykonáva, počítač vie, že je potrebné sa vrátiť k hlavnému a dokončiť prevedenia hlavnú funkciu. Takže toto je teraz nebezpečné, pretože ak užívateľ zadá v dobre viac ako ahoj, taká, že vstup užívateľa clobbers alebo prepíše že červené úsek, logicky v prípade, že počítač je jednoducho ísť slepo predpokladať, že byty v tomto červenom plátok sú adresa, na ktorú by mal vrátiť, čo v prípade, že protivník je dosť šikovný, alebo šťastie dať postupnosť bytov tam, že vyzerá ako adresa, ale je to adresa kódu že on alebo ona chce počítač vykonávať miesto main? 

Inými slovami, či to, čo sa Užívateľ je písanie na výzvy, Nie je to len niečo, neškodný ako Dobrý deň, ale je to vlastne kód, ktorý je rovnocenný vymazať všetky súbory tohto užívateľa? Alebo e-mailom svoje heslo ku mne? Alebo začať protokolovanie ich kláves, že jo? Existuje spôsob, poďme stanoviť dnes, že by mohli zadajte nie je len ahoj world alebo ich meno, mohli v podstate odovzdať kódov, nuly a ty, že je počítač chyby ako pre kód a adresu. Takže aj keď trochu abstraktne, v prípade, že užívateľ zadá v dostatočnom sporného kóde že budeme zovšeobecniť tu A. A je útok alebo protivníci. Takže len zlé veci. My sa nestarajú o čísla alebo nuly, alebo tie, dnes, takže môžete skončiť prepisovanie, že červená časť, Všimnite si, že poradie bajtov. O 835 C nula ôsmich nula. A teraz, keď na Wikipédii článok tu navrhla, ak si teraz skutočne začať označovanie bajtov v počítača pamäť, čo článok Wikipédie navrhujúci je, že to, čo v prípade, že adresa tohto ľavom hornom bytu je 80 C 0 3508. 

Inými slovami, ak je zlý chlap je dosť chytrý s jeho alebo jej kód skutočne vložiť číslo, ktoré tu odpovedá na adresu kódu on alebo ona injekčne do počítača, ktorá dokáže oklamať počítač do niečo robiť. Odstránenie súborov, posielanie e-mailov veci, ňuchania svoju prevádzku, doslova niečo mohlo byť vstrekuje do počítača. A tak pretečeniu vyrovnávacej pamäte útok vo svojom jadre je len hlúpa, hlúpa Prvoradým z poľa, ktorý nemal kontrolovať jeho hranice. A to je to, čo je super nebezpečný a zároveň veľmi výkonný v C je, že sme skutočne majú prístup k kdekoľvek v pamäti. Je to na nás, programátori, ktorí píšu pôvodný kód skontrolovať dĺžku zašiť niektorého polí, že sme manipulovali. Tak, aby bolo jasné, čo je to oprava? Ak by sme sa vrátiť k tomu kód, mal by som to nielen zmeniť dĺžku tyče, čo inak by som mal skontrolovať? Čo iné by som mal robiť, aby zabrániť úplne tento útok? Nechcem, aby len slepo povedať že by ste mali skopírovať toľko bajtov ako je dĺžka tyče. Chcem povedať, kopírovanie as veľa bajtov ako sú v baroch až do pridelenej pamäť, alebo 12 maximálne. Tak som potrebovať nejaký, ak stav ktorá robí skontrolujte dĺžku tyče, ale ak prekročí 12, len sme pevný kód 12 ako maximálnej možnej vzdialenosti. V opačnom prípade takzvaný vyrovnávacej pamäte overflow útoku sa môže stať. V dolnej časti týchto snímok, ak ste zvedaví čítať viac je skutočný pôvodný článok ak by ste chceli, aby sa pozrieť. 

Ale teraz, medzi cenami Tu zaplatil bol neefektívny. Takže to bola rýchla nízka úroveň pohľad na to, čo Problémy môžu vznikať teraz, že sme majú prístup do pamäte počítača. Ale ďalší problém, ktorý sme Už narazil v pondelok bol len neefektívnosť prepojeného zoznamu. Sme späť do lineárneho času. Máme už nemajú súvislý rad. Nemáme náhodný prístup. Nemôžeme použiť hranatú zátvorku notácie. Máme doslova musieť použiť while ako ten, ktorý som napísal pred chvíľou. Ale v pondelok, sme tvrdili, že môžeme vplížit späť do ríše účinnosti dosiahnutie niečo, čo je logaritmický možná, alebo najlepšie napriek tomu, možno aj niečo, čo je tzv časová konštanta. Tak ako môžeme urobiť, že pri použití tieto nové nástroje, tieto adresy, týchto ukazovateľov, a rezanie závitov veci vlastné? No, predpokladám, že tu, to sú banda čísel, ktoré chceme uložiť v štruktúra a vyhľadávanie dát efektívne. Môžeme úplne pretočiť do týždňa dva, hodiť ich do poľa, a vyhľadávanie je pomocou binárneho vyhľadávania. Rozdeľ a panuj. A v skutočnosti ste napísal binárne vyhľadávanie v PSET3, kde ste zaviedli program find. Ale viete čo. Tam je trochu viac šikovný spôsob, ako to dosiahnuť. Je to trochu viac sofistikované a to možno nám umožňuje vidieť, prečo binárne Vyhľadávanie je tak oveľa rýchlejšie. Po prvé, poďme predstaviť pojem stromu. Ktoré, aj keď v reality stromy druh rastú ako to, vo svete počítačov veda, že druh rastú smerom nadol ako rodinný strom, kde máte vašu prarodičia alebo prarodičia alebo ktovie čo ešte na vrchole, patriarcha a matriarchát rodiny, len jeden tzv koreň, uzol, nižšie ktoré sú jeho deti, pod ktorou sú jeho deti, alebo jeho potomkovia všeobecnejšie. A niekto visí spodný rodiny tree, vedľa byť najmladší v rodine, môže byť tiež všeobecne volal listy stromu. 

Tak to je len banda slov a definícií pre niečo, čo sa nazýva strom v počítači veda, podobne ako rodokmeni. Ale je tu milovník inkarnácií stromov, z ktorých jedna sa nazýva binárny vyhľadávací strom. A môžete druh vtipálek okrem toho, čo táto vec robí. No, je to binárny v akom zmysle? Odkiaľ binárne pochádza tu? Prosím? To nie je ani tak alebo. Je to skôr, že každý z uzlov nemá viac ako dve deti, pretože tu vidíme. Všeobecne platí, že tree-- a vaši rodičia a prarodičia môže mať toľko detí, alebo vnúčatá, ako sa v skutočnosti chcú, a tak napríklad tam máme tri deti z toho pravého uzla, ale v binárnom stromu, uzol má nula, jedna alebo dve deti maximálne. A to je pekná vlastnosť, pretože ak je limitovaný dvoma, budeme môcť si trochu log základňu dvoch akcie deje nakoniec. Takže máme niečo logaritmickej. Ale o tom viac za chvíľu. Vyhľadávací strom znamená, že čísla sú usporiadané tak, že ľavá dieťaťa hodnota je väčšia než koreňa. A jeho právo dieťa väčší než koreňa. Inými slovami, ak budete mať niektorý z uzly, kruhy v tomto obrázku, a pozerá sa na jej ľavej strane Dieťa a jeho právo dieťaťa, Prvá by mala byť nižšia ako, druhá by mala byť väčšia ako. Takže zdravý rozum skontrolovať 55. Je to nechal dieťa je 33. To je menej ako. 55, jeho právo dieťa je 77. To je väčší ako. A to je rekurzívne definície. Mohli by sme skontrolovať každý jeden z tých, uzly a rovnaký vzor by sa držať. 

Takže to, čo je milé v binárny vyhľadávací strom, je že jeden, môžeme ho realizovať s struct, rovnako ako táto. A aj keď sme hádzanie veľa stavieb na dosah, oni sú trochu intuitívne teraz nádejne. Syntax je stále tajomný pre istotu, ale obsah uzla v tejto context-- a držíme pomocou uzla slovo, či už je to obdĺžnik na obrazovku alebo do kruhu, je to len nejaký všeobecný kontajner, V tomto prípade stromu, ako je tá sme videli, potrebujeme číslo v každom z uzlov a potom som potrebné dva ukazovateľov ukazujúcich do ľavého dieťa a pravé dieťa, v tomto poradí. Tak to je to, ako by sme mohli náradie, ktoré v Struct. A ako by som mohol realizovať ju v kóde? Dobre, poďme sa rýchlo pozrite sa na tento malý príklad. Nie je to funkčné, ale ja som skopírovať a vložiť túto štruktúru. A keď je moja funkcia pre binárne vyhľadávací strom sa nazýva hľadanie, a to trvá dva argumenty, celé číslo N a ukazovateľ do uzla, takže ukazovateľ na stromu alebo ukazovateľ ku koreňu stromu, Ako mám ísť o hľadanie N? No, v prvom, pretože som rokovania s ukazovateľmi, Budem robiť kontrolu zdravý rozum. Ak strom rovná rovná null, je N v tejto vetve alebo nie je v tejto vetve? To nemôže byť, že jo? Ak som v minulosti null, tam nič nie je. Ja by som mohol tiež práve slepo hovoria return false. Ak mi nič, rozhodne nemôžem nájsť ľubovoľný počet N. Takže čo iného by som mohol skontroluj teraz? Chystám sa povedať aj inak, ak N je menšie ako to, čo je v uzla stromu že som bola odovzdaná hodnota n. Inými slovami, ak je číslo nie som hľadá, N, je menšie, než uzol že som pri pohľade na. A uzol sa pozerám u sa nazýva strom, a vyvolať z predchádzajúceho príkladu sa dostať na hodnotu v ukazovateli, Používam notáciu so šípkou. Takže ak N je menší ako stromu šípky N, chcem koncepčne ísť doľava. Ako môžem express vyhľadávania odišiel? Aby bolo jasno, či sa jedná obraz v otázke, a bol som prešiel, že najvyššie šípka, ktorá je smerom nadol. To je môj strom ukazovateľ. Ja som ukázal na koreň stromu. A ja hľadám povedzme, pre číslo 44, ľubovoľne. Je menšia ako 44, alebo väčší ako 55 zrejme? Takže je to menej ako. A tak, ak podmienka platí. Tak koncepčne, čo chcem hľadať ďalšie, keď som hľadal 44? Jo? 

Presne tak, chcem vyhľadávať ľavej dieťa, alebo doľava sub-strom obrázku. A v skutočnosti, dovoľte mi, aby som prostredníctvom obrázok tu dole len na chvíľu, pretože Nemôžem poškriabaniu to. Ak začnem tu na 55, a Viem, že hodnota 44 Ja som hľadal je ľavá, je to druh ako sa trhá telefónny zoznam v polpenzia alebo trhanie strom na polovicu. Ja už musieť starať o Celá táto polovica stromu. A napriek tomu, zvedavo v termínoch štruktúra, toto tu, že začína 33, ktoré samo o sebe je binárny vyhľadávací strom. Povedal som to slovo rekurzívne skôr, pretože v skutočnosti to je dátová štruktúra, ktorá podľa definície je rekurzívne. Možno budete mať strom, ktorý je tento veľký, ale každý z jej detí predstavuje strom len trochu menší. Namiesto toho, že dedo alebo babička, teraz je to len mama nebo-- Nemôžem say-- nie je mama alebo otec, to by bolo divné. Namiesto toho tam dve deti by bol ako brat a súrodenci. Nová generácia rodinného stromu. Ale štrukturálne, je to rovnaký nápad. A ukázalo sa, že mám funkciu s ktorými môžem vyhľadávať binárne vyhľadávanie strom. Nazýva sa vyhľadávanie. Aj hľadať N vo stromu Šípka doľava else if N je väčší ako hodnota že som v súčasnej dobe. 55 v príbehu pred chvíľou. Mám funkciu nazvanú Hľadania, ktorý môžem len prejsť N a to rekurzívne vyhľadávanie sub-strom a práve návrat čo to odpoveď. Inak mám nejaké finálnej základné prípad tu. 

Aká je konečná prípad? Strom je buď nulový. Hodnota som buď hľadal je menšie ako, alebo väčšia ako alebo rovná to. A mohol by som povedať, rovná rovní, ale logicky je to čo zodpovedá len hovorím, že tu inde. Takže pravda je, ako som sa niečo nájsť. Tak dúfajme, že to je ešte presvedčivejší príklad ako stupídny funkcie sigma sme urobili niekoľko prednášok späť, kde to bolo rovnako jednoduché používanie slučku spočítať všetky čísla od jednotky N. Tu s dátovú štruktúru ktorý sám o sebe je rekurzívne definované a rekurzívne vyvodiť, teraz sme majú schopnosť vyjadriť seba V kódu, ktorý sám o sebe je rekurzívne. Tak to je presne rovnaký kód tu. 

Takže to, čo ďalšie problémy môžeme vyriešiť? Tak rýchly krôčik od stromy na chvíľku. Tu je, povedzme, pod nemeckou vlajkou. A je tu jednoznačne vzor tohto parametra. A je tu veľa Vlajky na svete, ktorý sú tak jednoduché, ako je to z hľadiska ich farieb a vzorov. Ale predpokladajme, že tento je uložený ako GIF, alebo JPEG, alebo bitmapové, alebo ping, akýkoľvek grafický formát súboru , S ktorým ste sa zoznámili, z ktorých niektoré sme hrať s v PSET4. To sa zdá ako veľmi užitočné pre ukladanie Čierny pixel, čierny pixel, čierny pixel, bodka, bodka, bodka, celá partia čierne pixely pre prvú scanline, alebo riadku, potom celá partia rovnaké, potom sa celý zväzok of rovnaké, a potom Celá banda červených pixelov, červené pixely, červené pixely, potom celý banda žltých pixelov, žltá, že jo? 

Je tu taký neefektívnosť sem. Ako by ste intuitívne stlačiť pod nemeckou vlajkou ak sa vykonáva ako súbor? Ako aké informácie nemôžeme obťažovať ukladanie na disk v poradí znížiť našu veľkosť súboru z podobne megabajt na kilobyte, niečo menšie? V čom spočíva redundancie tu musí byť jasné? Čo si to mohol urobiť? Jo? Presne tak. Prečo radšej než spomenúť farba každého pixelu zašiť rovnako ako to robíte v PSET4 s formátom bitmapový obrázok, prečo si jednoducho predstavujú vľavo stĺpec obrazových bodov, napríklad banda čiernych pixelov, partia červenej a banda žlté, a potom už len nejako zakódovať idea Opakujte tento 100 krát alebo zopakovať tento 1,000 časov? V prípade, 100 alebo 1000, je len číslo, takže si môže dostať preč len s jedným číslom namiesto stoviek alebo tisícok dodatočných pixelov. A naozaj, to je, ako sme by mohlo stlačiť pod nemeckou vlajkou. A A teraz, čo o francúzskou vlajkou? A trochu akýsi mentálne cvičenie, ktoré vlajka môžu byť komprimované viac na disku? Nemeckej vlajky alebo francúzska vlajky, ak vezmeme tento prístup? Nemecká vlajka, pretože tam je viac horizontálne redundancie. A podľa návrhu, mnohí grafický súbor formáty skutočne pracovať ako rozkladovej riadky horizontálne. Mohli by fungovať vertikálne, len ľudstvo Pred rokmi sa rozhodli, že budeme všeobecne myslieť na veci, radu riadkom namiesto riadok po riadku. Takže naozaj, ak ste boli sa pozrieť na súbor veľkosť nemeckou vlajkou a francúzštine flag, tak dlho, kým je rozlíšenie rovnaké, rovnakú šírku a výška, tahle Tu bude väčší, pretože musieť opakovať sami trikrát. Musíte zadať modrá, opakovanie sami, biela, opakovať sami, červená, opakovať sa. Nemôžete jednoducho ísť all cesta doprava. A ako stranou, aby sa zrušte kompresie je všade, ak sa jedná o Štyri rámy z video-- vás by mohol pripomenúť, že filmu alebo video je všeobecne ako je 29 alebo 30 snímok za sekundu. Je to ako malé flip knihy, kde vás Len pozri obrázok, obrázok, image, image, image proste super rýchly, takže to vyzerá, herci na obrazovke sa pohybujú. Tu je bumble včela na Vrchol kytice. A aj keď to by mohlo byť trochu ťažké vidieť na prvý pohľad, Jediná vec, pohybujúce sa v tento film je včela. 

Čo je nemý o skladovaní Video nekomprimované? Je to druh odpadu pre ukladanie videa ako štyri takmer identické obrazy, ktoré sa líšia iba v prípade, keď je včela. Môžete zahodiť väčšinu týchto informácií a pamätať si len, napríklad, prvý záber a posledná snímka, kľúčové snímky, ak ste niekedy počul slovo, a len uložiť do prostredný kde včela je. A nemusíte sa ukladať všetky ružové, a modrej, a zelené hodnoty rovnako. Tak toto je len povedať, že kompresie je všade. Jedná sa o techniku ​​často používame alebo považuje za samozrejmosť v týchto dňoch. 

Ale ako si komprimovať text? Ako sa vám ísť o kompresiu textu? No, každý zo znakov v ASCII je jeden bajt, alebo osem bitov. A to je trochu hlúpa, že jo? Vzhľadom k tomu, budete pravdepodobne typu A a E a I a O a U veľa častejšie než ako W alebo Q alebo Z, v závislosti na jazyk, v ktorom píšete určite. A prečo sme s použitím osem bitov pre každé písmeno, vrátane najmenej populárne listy, že jo? Prečo nie použiť menej bitov pre Super populárne listy, ako E, veci, ktoré hádať najprv v Wheel of Fortune, a používať viac bitov pre menej populárne listy? Prečo? Pretože sme len tak používať menej často. 

No, to ukáže, že tam majú Bol pokusy, ako to dosiahnuť. A ak si spomínate zo stupňa škola alebo vysoká škola, Morseova abeceda. Morseova abeceda má bodky a pomlčky, ktoré môžu byť prenášané po drôte as zvuky alebo signály nejakého druhu. Ale Morseova abeceda je super čistý. Je to trochu binárneho systému že máte bodky alebo čiarky. Ale keď vidíte, napríklad, dve bodky. Alebo ak si myslíte, späť na prevádzkovateľa ktorí chodia ako píp, píp, pípnutie, pípnutie, biť trochu spúšť ktorý vysiela signál, ak vás, príjemcu, dostane dve bodky, akú správu ste dostali? Úplne ľubovoľné. 

Aj? Aj? Alebo čo about-- alebo ja? Možno to bolo len dva E má pravdu? Takže tam je to problém z decodability s Morse kód, pričom ak sa osoba zasielanie správy v skutočnosti sa zastaví, takže si môžete triediť podľa vidieť alebo počuť medzery medzi písmenami, že to nie je dostačujúce len Poslať prúdu núl a jednotiek, alebo bodky a čiarky, pretože tam je dvojznačnosť. E je jediná bodka, takže ak vás pozri dve bodky alebo počuť dve bodky, Možno je to dva E je alebo možno je to jedna I. Takže potrebujeme systém, ktorý je málo múdrejší než to. Takže muž menom Huffman rokov Pred prišli s presne toto. Takže sme len tak vziať rýchly pohľad na to, ako stromy sú pre predmetnú. Predpokladajme, že je to nejaký hlúpy správa, ktorú chcete odoslať, zložený z iba A, B, C je D'S a E je, ale je tu veľa redundancie sem. Nie je to znamená byť angličtina. To nie je šifrovaná. Je to len hlúpa správa s množstvom opakovaní. Takže ak ste naozaj počítať sa všetky A to, B je, je C, D's, a E je, tu je frekvencie. 20% z listov sú A je 45% z listov sú E je, a ďalšie tri frekvencie. Počítali sme tam ručne a práve urobil matematický. 

Tak to dopadá, že Huffman, pred nejakým časom, si uvedomil, že, viete, čo, keď som začať stavať strom alebo les stromov, ak chcete, takto, môžem urobiť nasledovné. Chystám sa dať uzla ku každému z listov, ktoré som záleží a budem ukladať vnútri tohto uzla frekvencie ako pohyblivou rádovou čiarkou hodnota, alebo môžete použiť N, taky, ale my budeme stačí použiť float tu. A algoritmus, ktorý navrhol je, že ste tento les jedného uzla stromy, takže extra krátke stromy, a začnete ich spájajú s nové skupiny, nové rodičia, ak chcete. A to tým, že voľbe dve najmenšie frekvenciou naraz. Tak som vzal 10% a 10%. Aj vytvoriť nový uzol. A ja hovorím nového uzla 20%. 

Ktorí dva uzly Aj kombinovať ďalej? Je to trochu nejasné. Takže tam je niekoľko prípadov roh zvážiť, ale udržať veci dosť, Budem voliť 20% - Aj teraz ignorovať deti. Budem voliť 20% a 15% a kresliť dva nové hrany. A teraz, keď sú dve uzly mám logicky kombinovať? Ignorovať všetky deti, sú všetky vnúčatá, stačí sa pozrieť na korene teraz. Ktorí dva uzly mám zviazať dohromady? Bod dva a 0.35. Dovoľte mi teda kresliť dva nové hrany. A potom som sa dostal len jeden vľavo. Tak tu je to strom. A to bol vypracovaný zámerne vyzerať trochu pekná, ale všimnite si, že hrany majú Tiež bol označený nulou a jednotkou. Takže všetky ľavého okraja sú nulové ľubovoľne, ale dôsledne. Všetky hrany sú tie správne. 

A tak to, čo Hoffman Navrhuje sa, Ak chcete reprezentovať B, skôr než predstavujú počet 66 as ASCII, ktorý je osem celé bitov, Vieš čo, len obchod vzor nula, nula, nula, nula, pretože to je cesta z môjho stromu, pána Huffmanův strom, na liste z koreňa. Ak chcete uložiť E, naproti tomu nemajú poslať osem bitov, ktoré predstavujú E. Namiesto toho, čo poslať vzor bitov? One. A čo je príjemné na tom je, že E je najpopulárnejší list, a používate Najkratšie kód pre ňu. Budúci Najobľúbenejšie list vyzerá, že bol A. A tak, koľko bitov urobil navrhujú použitie za to? Nula, jedna. 

A pretože je implementované ako tohto stromu, zatiaľ dovoľte mi, aby som sa stanovuje, že je žiadna nejasnosť ako v Morse kód, pretože všetky listy vám záleží sú na konci týchto hrán. Tak to je len jeden Aplikácia stromu. To je-- a budem mávať moja ruka sa na to, ako na Vás môže vykonávať toto ako štruktúra C. Potrebujeme len kombinovať symbol, ako char, a frekvencia doľava a doprava. Ale poďme sa pozrieť na dva Konečné príklady, ktoré budete dostať docela oboznámení s po kvíz nula problém nastaviť päť. 

Takže tam je dátová štruktúra známy ako stola mriežky. A hash tabuľka je druh ochladí sa tým, že korčeky. A predpokladám, že tam je štyri vedierka tu, iba štyri medzery. Tu je balíček kariet, a je tu klubu, rýľ, klub, diamanty, klub, diamanty, klub, diamanty, clubs-- takže to je náhodné. Hearts, hearts-- takže som bucketizing všetky vstupy sem. A A potrebuje hash table pozrieť sa na váš vstup, a potom ju do určitej položte na základe toho, čo vidíte. Je to algoritmus. A ja som bol s použitím super jednoduché vizuálne algoritmus. Najťažšia časť, ktorá bola si spomenul, aké obrázky boli. A potom je tu celkom štyri veci. 

Teraz komíny rástli, čo je zámerná návrh vec tu. Ale čo iného by som mohol urobiť? Takže vlastne tu máme banda starej školy skúšky kníh. Predpokladajme, že banda Mená študenti sú tu. Tu to väčšie hash tabuľky. Namiesto štyroch vedier, Som, povedzme 26. A my sme nechceli ísť požičať 26 z krajín mimo [? Annenberg?], Tak tu je piatich ktoré reprezentujú A až Z. A ak ja pozri študentom, ktorého meno začína na A, Chystám sa dať jeho alebo jej kvíz tam. Ak niekto začne s C, tam, Je-- skutočnosti, nechcel urobiť. B jede sem. Tak som dostal A a B a C a teraz tu je ďalší študent. Ale ak to hash tabuľka implementovaný s maticu Som typ skrutkované v tomto bode, že jo? Tak nejako som potrebujete, aby to niekde. 

Takže jeden spôsob, ako môžem riešiť to, všetko vpravo, A je zaneprázdnený, B je zaneprázdnený, C je zaneprázdnený. Chystám sa ho dať do D. Takže na Prvé, mám náhodný okamžitý prístup ku každej z lopatiek pre študentov. Ale teraz je to trochu preniesol do niečoho lineárne, pretože keď chcem hľadať niekoho, Názov ktorého začína, ja pozrite sa sem. Ale ak to nie je A Student Hľadám, Tak nejako som musel spustiť kontrolu vedierka, pretože to, čo som urobil Bolo to trochu lineárne skúmať štruktúru dát. Hlúpa spôsob ako povedať, stačí sa pozrieť za prvé dostupné otvoru, a dal ako plán B, aby som tak povedal, alebo plán D v tomto prípade je hodnota V tomto mieste namiesto. Je to len preto, aby, ak ste dostal 26 miest a žiadni študenti s názvom Q alebo Z, alebo niečo podobné že prinajmenšom používate priestor. 

Ale my sme už videli viac Múdra riešenie tu, že jo? Čo by ste robili, miesto Ak máte ku kolízii? Ak sa dvaja ľudia majú názov A, čo by boli múdrejší a viac intuitívne riešenie než len Uvedenie kde D má byť? Prečo nemôžem jednoducho ísť mimo [? Annenberg?], ako je malloc, iného uzla, dať to tu, a potom dal, že študent tu. Tak, že som v podstate majú nejaký poľa, alebo možno viac elegantne, ako sme Začíname vidieť prepojeného zoznamu. 

A tak hash tabuľky je štruktúra ktoré by mohli vyzerať presne takto, ale chytro, ste niečo ako samostatný reťazenie, pričom hash tabuľky celkom jednoducho je pole, každý z ktorej prvky nie je číslo, je sám o sebe spojený zoznam. Tak, že máte super rýchly prístup rozhodovanie o tom, kde sa vaše hash hodnotu. Podobne ako v príklade karty, Urobil som mimoriadne rýchle rozhodovanie. Hearts ide tu, diamanty ide tu. Ja taky, A tu ide, D ide tu, B ide tu. Takže super rýchle look-ups, a pokiaľ ste náhodou naraziť na prípade kde ste dostal kolízie, dva ľudia s rovnakým názvom, no a potom stačí začať spájať dokopy. A možno si udržať je zoradená abecedne, možno nie. Ale aspoň teraz máme dynamiku. Takže na jednej strane máme veľmi rýchle konštantný čas, a druh lineárneho času zapojiť, ak týchto spojových zoznamov začne byť trochu dlho. 

Takže tento druh hlúpy, geek vtip pred rokmi. Na CS50 hack-a-Thon, Keď študenti check in, niektoré TF alebo CA každý rok si myslí, že je to smiešne, aby sa znamenia ako je tento, kde ide len znamená, že ak vaše meno začína s A, ísť touto cestou. Ak sa spustí Vaše meno s B, choďte tohle-- OK, je to smiešne možno neskôr v semestri. Ale je tu ďalší spôsob, ako to dosiahnuť, taky. Vráť sa k tomu. 

Takže je tu táto štruktúra. A to je náš posledný štruktúra pre dnešok, čo je niečo, čo nazýva trie. T-R-I-E, ktorá z nejakého dôvodu je krátka pre vyhľadávanie, ale je to len trie. Takže Trie je ďalšia zaujímavá amalgám z mnohých týchto nápadov. Je to strom, ktorý sme videli skôr. Nie je to strom binárneho vyhľadávania. Je to strom s ľubovoľným počtom detí, ale každý z detí v trie je pole. Poľa veľkosti, povedzme, 26 alebo možno 27 Ak chcete podporiť pomlčkou mená alebo apostrofy v názvoch ľudí. 

A tak to je dátová štruktúra. A keď sa pozriete z vrcholu dole, ako keď pozrite sa na hornom uzla tam, M, je ukazujúci na najviac vľavo vec tam, ktorý je potom A, X, W, E, L, L. To je len dátová štruktúra, ktorá ľubovoľne je ukladanie mien ľudí. A Maxwell je uložený práve týmto cesta z poľa na pole do poľa. Ale čo je to úžasné asi trie je že, vzhľadom k tomu, Google zoznamu a dokonca pole, to najlepšie, čo som kedy dostal, je lineárny čas alebo logaritmickej čas hľadáte niekto up. V tejto dátovej štruktúre trie, ak je to môj dátová štruktúra má jedno meno v ňom a ja som hľadal Maxwella, ja som že ho celkom rýchlo nájsť. Ja sa len pozrieť na M-A-X-W-E-L-L. Ak Táto dátová štruktúra, naopak ak N je milión, či je milión mená v tejto dátovej štruktúry, Maxwell sa ešte bude zistiteľný po práve M-A-X-W-E-L-L, kroky. A David-- D-A-V-I-D kroky. Inými slovami tým, že stavebné dátová štruktúra, ktorá je dostal pričom všetky z týchto polí, všetko samy podporujú náhodný prístup, Môžem začať vzhliadol ľudí'S názov pomocou množstvo času, ktorý je úmerný nie číslo vecí v dátovej štruktúry, ako milión existujúcu mien. Množstvo času to trvá mi nájsť M-A-X-W-E-L-L v tejto dátovej štruktúry je úmerný nie je na veľkosť dátové štruktúry, ale k dĺžke názvu. A Realisticky Mená pozeráme hore sa nikdy nebude blázon dlho. Možno, že niekto má 10 znak meno, názov 20 znakov. Je to určite konečný, že jo? Tam je človek na Zemi, ktorý má najdlhší názov, ale to meno je konštantná hodnota dĺžky, nie? To sa nemení v žiadnom zmysle. Takže týmto spôsobom, máme dosiahla dátovú štruktúru že je konštantná doba look-up. Je to trvať niekoľko krokov v závislosti na dĺžke vstupe, ale nie množstvo názvu v dátovej štruktúre. Takže ak budeme zdvojnásobiť počet mien v budúcom roku z miliardy do dvoch miliárd, nález Maxwell bude trvať presne rovnaký počet siedmich stupňoch ho nájsť. A tak sa zdá k dosiahli náš svätý grál doby chodu. 

Takže pár rýchlych oznámenia. Kvíz nula sa blíži. Viac o tom na internetových stránkach Course počas najbližších pár dní. Pondelkové lecture-- je to sviatok tu na Harvarde v pondelok. Nie je to v New Haven, takže berieme triedu do New Havene pre prednášku v pondelok. Všetko bude natočený a sledovať naživo ako obvykle, ale poďme skončiť dnes s 30 druhého klipu zvané "hlboké myšlienky" podľa Daven Farnham, ktorý bol inšpirovaný v minulom roku v sobotu Night Live "hlboké myšlienky" Jack Handy, ktorý by teraz mala zmysel. 

FILM: A teraz, "Hlboké Myšlienky "od Daven Farnham. Hash tabuľky. 

Reproduktor 1: Dobre, to je pre teraz. Uvidíme sa budúci týždeň. 

DOUG: Ak chcete ho vidieť v akcii. Takže poďme sa pozrieť na práve teraz. Takže tu máme netriedeného poľa. 

IAN: Doug, môžete ísť dopredu a reštart to len na jednu sekundu, prosím. Dobre, kamery sú rolovacie, tak akcie vždy, keď budete pripravení, Doug, OK? DOUG: Dobre, takže to, čo sme tu je netriedený pole. A ja som farebné všetkých prvkov červeno, čo znamená, že to je, v skutočnosti, netriedený. Takže pripomenúť, že prvá vec, ktorú robíme je triedime na ľavej polovici poľa. Potom sme triediť právo polovica poľa. A ya-da, da-ya, ya-da, sme ich spojiť dohromady. A máme úplne zotriedené poľa. Tak to je, ako zlúčiť nejako funguje. 

IAN: Whoa, hej, hej, strih, strih, strih, rez. Doug, nemôžeš ya-da, ya-da, ya-da, si cestu cez zlúčenie druhu. 

DOUG: Len som urobil. Je to fajn. Sme dobré ísť. Poďme sa len držať valcovania. Tak ako tak, 

IAN: Musíte vysvetliť to vo väčšej miere, než to. To je jednoducho nestačí. DOUG: Ian, my nie je potrebné sa vrátiť do jedného. Je to fajn. Takže tak ako tak, ak budeme pokračovať s merge-- Ian sme v polovici natáčania. 

IAN: Ja viem. A my nemôžeme len ya-da, ya-da, ya-da, celý proces. Musíte vysvetliť, ako Obe strany si spojil. 

DOUG: Ale máme už vysvetlil, ako dva sides-- 

IAN: Práve ste zobrazené im merge poľa. DOUG: Poznajú proces. Sú v poriadku. Šli sme cez to desaťkrát. 

IAN: Práve si preskočil hneď nad ním. Vraciame sa do jedného, ​​vy nemôžeš ya-da, ya-da cez ňu. Dobre, späť do jedného. 

DOUG: Musím sa vrátiť cez všetky snímky? Môj Bože. Je to ako už po šiestykrát, Ian. Je to fajn. 

IAN: Dobre. Ste pripravení? Skvelé. Akcie.