DAVID Malan: Dobře. Jsme zpět. Takže v tomto segmentu o programování, co Myslel jsem, že bychom udělat, je mix věcí. Za prvé, udělat trochu něčeho hands-on, byť s použitím hravější programování environment-- ten, který je demonstrativní přesně ty druhy nápadů jsme mluvili o, ale trochu více formálně. Za druhé, podívejte se na některé z čím více technických způsobů že programátor by skutečně řešit Problémy, jako je vyhledávání problému že jsme se zabývali dříve a také více zásadně zajímavý problém třídění. 

Jen jsme předpokládali, od dostat jít že telefonní seznam byl tříděn, ale to samo o sobě je vlastně něco jako obtížný problém s mnoha různými způsoby to vyřešit. Takže budeme používat tyto jako třída problémů Zástupce věcí, které by mohl být vyřešen obecně. A pak si promluvíme asi v nějakém detailu, co se nazývají dat structures-- milovník způsoby, jako spojových seznamů a hashovací tabulky a stromy, které programátor by vlastně použití a obecně používají Na tabuli malovat obrázek o tom, co on nebo ona předpokládá pro provádění některé kus softwaru. 

Takže pojďme dělat hands-na části první. Takže jen dostat své špinavé ruce s Prostředí tzv scratch.mit.edu. Jedná se o nástroj, který používáme v naší třídě vysokoškoláka. I přesto, že je navržen pro děti od 12 a nahoru, budeme používat jej pro nahoru Součástí tohoto docela dost protože je to pěkné, zábavné grafický způsob učení něco málo o programování. Takže zamířit do této adresy URL, kde vás Měli byste vidět stránku přesně takhle, a pokračujte a klikněte Přidejte se k poškrábání v pravém horním rohu a vybrat si uživatelské jméno a heslem a nakonec si sami account-- scratch.mit.edu. Myslel jsem, že použít jako Příležitost první to ukázat. Otázka přišel během přestávky o tom, co vlastně kód vypadá. A my jsme si povídali během přestávky o C, v particular-- zvláště Nižší úroveň ve starším jazykem. A já jsem právě udělal rychlý Google hledání najít C kód pro binární vyhledávání, algoritmus, který jsme použity k hledání tohoto telefonního seznamu dříve. Tento konkrétní příklad, samozřejmě, nevyhledává telefonní seznam. Je to jen hledá spoustu Čísla v paměti počítače. Ale pokud byste chtěli jen dostat vizuální o tom, co skutečné programování jazyk vypadá, že vypadá trochu něco takového. Takže je to asi 20-plus, Přibližně 30 řádků kódu, ale rozhovor jsme vedli přes přestávku Byl o tom, jak to vlastně dostane proměnil nul a jedniček a můžete nejen vrátit v případě, že zpracovávat a jít z nul a jedniček zpět ke kódu. 

Bohužel, tento proces Je tak transformační že je to mnohem snadněji řekne, než udělá. Šel jsem dopředu a ve skutečnosti se obrátil tento program, binární vyhledávání, do nul a jedniček formou program s názvem kompilátoru, že jsem stalo se, že tady právě na mém počítači Mac. A když se podíváte na obrazovce Zde, zejména s důrazem Na těchto středních šest sloupců pouze uvidíte pouze nul a jedniček. A to jsou ty nuly a ty, které skládat přesně ten vyhledávací program. 

A tak každý kus z pěti bitů, každý bajt nul a jedniček tady, reprezentují nějakou instrukci typicky uvnitř počítače. A ve skutečnosti, pokud jste slyšeli marketing slogan "Intel inside" - to, Samozřejmě, prostě znamená, že máte Intel CPU nebo mozku uvnitř počítače. A co to znamená být CPU že máte instrukční sadu, abych tak řekl. 

Každý procesor na světě, mnozí je vyrobený firmou Intel v těchto dnech, chápe konečný počet instrukcí. A tyto pokyny jsou tak nízké úrovni jako doplněk těchto dvou čísel dohromady, násobit těchto dvou čísel dohromady, přesunout tento kousek dat odtud tady v paměti uložit toto Informace odtud do zde v paměti, a tak forth-- tak velmi, velmi low-level, téměř elektronické detaily. Ale s těmi, matematický operace spojené s tím, co jsme diskutovali dříve, reprezentace dat jako nul a jedniček, může si vybudovat vše že počítač může udělat dnes, ať už je to textové, grafické, hudební, nebo jinak. 

Takže je to velmi snadné se dostat ztratil v plevele rychle. A je tu spousta syntaktické výzvy přičemž když uděláte nejjednodušší, nejhloupější překlepů nikdo z programu bude fungovat vůbec. A tak namísto použití jazyk C dnes ráno, Myslel jsem si, že by bylo zábavnější vlastně dělat něco víc vizuální, což zatímco určen pro děti je vlastně ideální projev o skutečném programování language-- jen se stane použít obrázky namísto textu reprezentovat těchto myšlenek. 

Takže až budete opravdu mít Účet na scratch.mit.edu, klepněte na tlačítko Vytvořit V levém horním rohu stránky. A měli byste vidět prostředí, jako je ten, že jsem asi vidět na mé obrazovce zde. A budeme trávit jen trochu Trochu času hraním zde. Uvidíme, jestli se nám podaří ne všichni řešit některé Problémy spolu v následujícím způsobem. 

Takže to, co uvidíte v této environment-- a vlastně jen nechat me pauzy. Je někdo ne tady? Tady ne? OK. Takže mi dovolte zdůraznit několik Charakteristiky tohoto prostředí. 

Takže v levém horním rohu obrazovky, my mají stádium Scratch je, abych tak řekl. Scratch není pouze název tohoto programovacího jazyka; je to také jméno kočky, která vidíte ve výchozím nastavení tam v oranžové barvě. Že je na jevišti, tak stejně jako jsem popsal želva dříve jako v obdélníková bílá tabule prostředí. Tato kočka svět je omezena výhradně v tomto obdélníku do vrcholu. 

Mezitím se na pravé straně straně tady, je to jen skripty prostor, nepopsaný list chcete-li. To je místo, kde budeme psát naše programy za chvíli. A stavební kameny, které budeme použít k napsání této program-- puzzle kusy, pokud jste will-- jsou ty tady ve středu, a oni jsou rozděleny do kategorií funkčností. Tak například, budu pokračovat a ukazují, alespoň jeden z nich. Chystám se jít dopředu a klikněte kategorie Control nahoru vrcholu. 

Tak to jsou kategorie nahoru vrcholu. Jdu kliknout na kategorii řízení. Spíše jdu kliknout na události kategorie, první jedno až nahoru. A pokud byste chtěli sledovat spolu dokonce jak to uděláme, jste docela vítáni. Jdu kliknout a přetáhnout První z nich, "když zelená vlajka klepnutí." A pak budu ji neupustili jen zhruba v horní části svých prázdných břidlic. 

A co je hezké o Scratch je, že tento skládačky, když spojen s jiným puzzle kusů, se chystá udělat doslova co tyto kousky skládačky říci dělat. Tak například, Scratch je správné se v polovině jeho světa. Chystám se jít dopředu a vybrat Nyní, řekněme, kategorie Motion, pokud byste chtěli, aby učinily same-- kategorii Motion. A teď si všimnout mám celek banda skládačky zde že opět trochu dělat to, co říkají. A já jdu dál a přetáhnout drop Přesun bloku támhle. 

A všimněte si, že jakmile se dostanete v blízkosti spodní části "zelenou vlajkou klepnutí "tlačítko, vývěsní jak se objeví bílá čára, jako kdyby to je téměř magnetické, že tam chce jet. Jen ať jdou, a to bude snap dohromady a tvary budou odpovídat. A teď můžete snad téměř hádejte, kde jdeme s tím. 

Podíváte-li se ve fázi Scratch sem a dívat se na vrcholu toho, uvidíte červené světlo, je stopka a zelenou vlajku. A já jdu napřed a sledovat mé screen-- na chvíli, pokud byste mohli. Jdu kliknout na Zelená vlajka právě teď, a přešel co se zdá být 10 kroků nebo 10 obrazových bodů, 10 bodů na obrazovce. 

A tak není tak vzrušující, ale dovolte mi navrhnout aniž by se učí to, jen s použitím vlastní svůj vlastní intuition-- let já navrhuji, aby vám zjistit, jak se aby Scratch procházku hned jeviště. Už ho dělat cestu pro pravou stranu obrazovky, úplně napravo. Dám vám chvilku nebo tak zápasit s tím. Možná budete chtít, aby se podívali u ostatních kategorií bloků. Dobře. Takže jen shrnout, když máme zelená vlajka sem klikl a přesunout 10 kroků je pouze pokyn, pokaždé, když jsem klikněte na zelenou vlajku, co se děje? No, to běží můj program. Takže jsem mohl udělat Možná 10krát ručně, ale to cítí trochu bit hackish, tak říkajíc, přičemž Nejsem vyřešení problému. Já jsem jen dalším pokusem a Znovu a znovu a znovu dokud jsem tak nějak náhodou dosáhnout směrnici že jsem vytyčených cílů dříve. 

Ale víme z našich pseudocode dříve, že je tu Tento pojem v programování zacyklení, dělat něco znovu a znovu. A tak jsem viděl, že banda vás sáhl po tom, co skládačky? Opakujte, dokud. Takže bychom mohli něco udělat jako opakujte, dokud. A co jste opakujte, dokud přesně? 

OK. A nech mě jít s jedním, který je poněkud jednodušší jen na okamžik. Nech mě jít dopředu a to udělat. Všimněte si, že, jak můžete mít objevil pod kontrolou, je toto opakování blok, který nevypadá, že je to tak velký. Není toho moc pokoje v hotelu mezi těmito dvěma žlutou čárou. Ale jak někteří z vás mohou mít si všiml, pokud jste drag and drop, Všimněte si, jak roste k vyplnění tvaru. 

A dokonce můžete nacpat víc. Bude to jen neustále rostou, pokud přetahování a vznášet se nad ním. A já nevím, co je Zde nejlepší, tak ať me alespoň opakuje pětkrát, pro instance, a pak se vrátit na jeviště a klikněte na zelenou vlajku. A teď si všimnout, že to není úplně tam. 

Nyní někteří z vás navrhl, as Victoria jen to, opakujte 10 krát. A to obvykle dělá dostat ho celou cestu, Ale nebylo tam být odolnější způsob, než svévolně přijít na to, kolik tahů udělat? Co by mohlo být lepší blok než opakovat 10krát být? 

Jo, tak proč ne něco navždy? A teď mi dovolte přesunout tento kousek skládačky tam uvnitř a zbavit se této jedné. Nyní všimnout, bez ohledu na místo Scratch Spustí se, chodí k okraji. A naštěstí MIT, kdo dělá nuly, jen zajišťuje, že nikdy zmizí úplně. Vždy se můžete chytit svůj ocas. 

A právě intuitivně, proč se neustále v pohybu? Co se to tu děje? Zdá se, že se zastavil, ale Pak když jsem vyzvednout a táhněte Pořád chce jít tam. Proč tomu tak je? Opravdu, je počítač doslova dělat to, co jste to říct dělat. Takže pokud jste to řekl dříve dělat Následující věc navždy, přesunout 10 kroků, že to bude pokračovat a bude až jsem narazila na červenou stopku a zastavení programu úplně. 

Takže i když ne to, jak bych mohl aby Scratch pohybovat rychleji přes obrazovku? Další kroky, ne? Takže místo toho dělal 10 v době, proč ne my jděte do toho a změnit jej to-- Co byste propose-- 50? Takže teď jdu kliknout na zelenou vlajka, a opravdu, jede opravdu rychle. 

A to, samozřejmě, je jen projevem animace. Co je animace? Je to jen vy zobrazující lidskému celá řada statických snímků ve skutečnosti, opravdu, ale opravdu rychle. A tak jestli jsme jen říkat ho přesunout více kroků, my jsme jen mít vliv mělo být Změna kde je na obrazovce o to rychleji za jednotku času. 

Nyní další úkol, který jsem navrhl měl mít ho odrazit přes okraj. A aniž by věděl, co puzzle kusy exist--, protože to je v pořádku pokud nechcete dostat do etapa challenge-- co chceš dělat intuitivně? Jak bychom museli ho odrazí zpět a dále, mezi levou a pravou? 

To jo. Takže potřebujeme nějaký druh o stavu, a my Zdá se, že podmiňovací, tak říkajíc, v kategorii Control. Který z těchto bloků budeme chtít? Jo, možná "if, then." Takže si všimnout, že mezi žlutými bloky tu máme, je to "kdyby" nebo to "if, else" blok, který bude nám umožňují učinit rozhodnutí, jak toho dosáhnout nebo to udělat. A dokonce můžete vnořit jim dělat více věcí. Nebo pokud jste dosud pryč tady, pokračovat do kategorie snímání a-- uvidíme, jestli je to tady. 

Takže to, co blok by mohlo být užitečné zde zjistit, zda je to z jeviště? Jo, všimněte si, že některé z těchto bloků lze parametrizovat, abych tak řekl. Mohou být nějak přizpůsobit, nikoli Na rozdíl od HTML včera s atributy, pokud tyto atributy druh přizpůsobit chování tagu. Stejně tak zde, mohu uchopit toto dojemné blok a změny a položit otázku, jste dotýká myš Ukazatel jako kurzor nebo jste dotýkat okraje? 

Tak nech mě jít dovnitř a udělat. Jdu pro oddálení na chvíli. Nech mě uchopit tento kousek skládačky Zde tento skládačky to, a budu míchanice je až na chvíli. Chystám se pohybovat to, změnit na dotyku hrany, a já jdu do pohybu to udělat. Takže tady jsou některé ingredience. Myslím, že mám všechno, co chci. 

By někdo chtěl navrhnout, jak jsem lze připojit tyto možná shora dolů za účelem vyřešení problému s Scratch pohyb zprava doleva doprava na zleva zprava doleva, přičemž každý pokus o najetí odráží od zdi? Co chci dělat? Které blokují bych měl připojit k internetu "Při zelenou vlajkou klepnutí na prvním místě"? 

OK, takže začněme s "navždy". Co se děje uvnitř dál? Někdo jiný. OK, pohybovat kroky. Dobře. A co pak? Takže potom, jestliže. A všimněte si, i když to vypadá obložené spolu pevně, to bude jen růst zaplnit. To bude jen skočit, kde to chci. 

A co mám dát mezi if a poté? Pravděpodobně ", pokud se dotknete hrany." A oznámení, opět, je to příliš velká pro něj, ale poroste zaplnit. A pak zase 15 stupňů? Kolik stupňů? Jo, takže 180 bude točit mě celou cestu kolem. Tak uvidíme, jestli mám toto právo. Nech mě oddálit. 

Nech mě táhnout Scratch nahoru. Takže on je trochu zkreslený teď, ale to je v pořádku. Jak mohu resetovat ho snadno? Jdu trochu podvádět. Tak jsem přidat další blok, jen aby bylo jasno. Chci, aby bod o 90 stupňů doprava ve výchozím nastavení, tak jsem prostě jít mu to říct k tomu, že programově. A tady jdeme. Zdá se, že to udělal. Je to trochu divné, protože on šel vzhůru nohama. Říkejme, že chyby. To je chyba. Chyba je chyba v programu, A logická chyba, že jsem člověk, udělal. Proč se děje vzhůru nohama? Věděli MIT mhouřit nebo jsem? 

Jo, myslím, že to není MIT chyba. Dali mi kousek skládačky který říká, že otočit určitý počet stupňů. A na Victoria je návrh, Jsem otočil o 180 stupňů, což je ta správná intuice. Ale otočení o 180 stupňů doslovně znamená otočení o 180 stupňů, a to není opravdu co chci, zřejmě. Vzhledem k tomu, aspoň že je v Tento dvourozměrný svět, takže soustružení se opravdu děje aby ho otočit vzhůru nohama. 

Asi chci použít to, co blok Místo toho, podle toho, co vidíte tady? Jak můžeme tento problém vyřešit? Jo, takže jsme mohli poukázat v opačném směru. A vlastně i to je nebude stačit, protože můžeme jen těžko kód aby ukázal vlevo nebo vpravo. 

Víš, co bychom mohli dělat? Vypadá to, že máme pohodlí blok zde. Kdybych přiblížit, viz něco, co se nám líbí tady? Takže to vypadá, že MIT má abstrakce postavena v roce tady. Tento blok se zdá být ekvivalentní na které ostatní bloky, množné číslo? 

Tento jeden blok se zdá být ekvivalentní k celé této trojice bloků že tu máme. Tak to dopadá mohu zjednodušit můj Program zbavíme to všechno a jen dát to tady. A teď je ještě trochu buggy, a to je v pořádku pro tuto chvíli. Necháme to být. Ale můj program je dokonce jednodušší, a to taky, by být reprezentativní si za cíl v programming-- je v ideálním případě vytvořit svůj kód jako jednoduché, kompaktní, jak je to možné, a přitom stále as čitelné jak je to možné. Nechcete, aby to tak pregnantní že je těžké pochopit. 

Nevšimnout jsem nahradil tři bloky s jedním, a to je pravděpodobně dobrá věc. Já jsem abstrahovat pryč pojmu kontroly, zda jste na hraně jen jeden blok. Nyní můžeme bavit s tím, ve skutečnosti. To nepřidá tolik intelektuální hodnotu, ale hravý hodnotu. Chystám se pokračovat a chytit tento zvuk zde. Tak nech mě jít dopředu, a dovolte mi, abych program zastavit na chvíli. Chystám se zaznamenat následující, umožňující přístup k mému mikrofonu. 

Jdeme na to. Ouch. Zkusme to znovu. Jdeme na to. OK, zaznamenal jsem špatnou věc. Jdeme na to. Ouch. Ouch. Dobře. Teď potřebuji se zbavit toho. Dobře. 

Takže teď mám nahrávka jen "Au." Takže teď jdu vpřed a nazývat "Au." Chystám se vrátit mých skriptů, a teď Oznámení, že je to blok, který se nazývá přehrát zvuk "mňau" nebo přehrát zvuk "Au." Chystám se přetáhnout, a kde Měl bych dát to na komický efekt? Jo, takže teď je to trochu buggy, protože teď to block-- Všimněte si, jak toto "-li na hraně, odraz "je tak trochu soběstačný. Tak jsem třeba to napravit. Nech mě jít dopředu a to udělat. Dovolte mi, abych se zbavit tohoto a vrátit k naší původní, více úmyslné funkčnost. Takže ", pokud se dotknete hrany, pak" Chci otočit, jak Victoria navrženo, 180 stupňů. A nechci hrát zvuk "Au" tam? 

Jo, všimněte si, že je to venku že žlutý blok. Takže i to, by bylo bug, ale všiml jsem si to. Takže budu přetáhněte ji tady, a upozornění teď je to uvnitř "pokud". Takže "pokud" je tento druh podobnou ramenem jako skvrna že to bude jen to, co je uvnitř ní. Takže teď, když jsem oddálit na riziko annoying-- 

COMPUTER: Au, Au, Au. 

DAVID Malan: A bude jen pokračovat donekonečna. Teď už jen stačí k urychlení věci tady, nech mě jít dopředu a otevřít, pojďme say-- nech mě jít k některým ze své vlastní věci z třídy. A dovolte mi otevřít, řekněme, toto jedna ze strany jednoho z našich výukových kolegy před pár lety. Takže někteří z vás možná pamatujete Tato hra z dávných dob, a je to skutečně pozoruhodné. I přesto, že jsme hotová Nejjednodušší programů právě teď, uvažujme, co to ve skutečnosti vypadá. Nech mě zasáhla hru. 

Takže v této hře, máme žába, a pomocí šipky keys-- bere větší kroky, než jsem remember-- Mám kontrolu nad touto žábou. A cílem je dostat se přes rušný Cesta bez spuštění do auta. A pojďme see-- když půjdu sem, já muset počkat na protokol k posouvat. To se cítí jako brouk. To je druh chyby. Dobře. Jsem na to tady, tam, a pak budete mít jít, až se dostanete vše žáby na lilie podložky. Teď to může vypadat o to složitější, ale pojďme zkusit zlomit toto dole psychicky a slovně na jednotlivé bloky. Takže je to asi logická kus, který jsme ještě neviděli ale to reaguje na úhozů, k věcem jsem narazila na klávesnici. 

Takže je to asi nějaká blok, který říká, je-li klíč rovná up, pak udělat něco s Scratch-- Možná ji přesunout 10 kroků tímto způsobem. Je-li stisknuté klávesy pohybovat 10 kroků Tímto způsobem, nebo vlevo klíč, přesunout 10 kroků Tímto způsobem deset kroků, které. Já jsem jasně ukázalo kočku v žábu. Tak to je jen, kdy kostým, jak Scratch hovory to-- my právě importovali obraz žáby. 

Ale co jiného se děje? Jaké další řádky kódu, co skládačky udělal Blake, náš kolega učení, použít v tomto programu, podle všeho? Co se dělat všechno move-- co programovací postavit? 

Motion, takže sure-- přesunout blok, pro jistotu. A co je to pohyb blok uvnitř, s největší pravděpodobností? Jo, nějaký druh smyčky, možná navždy zablokovat, možná opakování block-- opakujte, dokud bloku. A to je to, co dělat protokoly a Lily podložky a všechno ostatní tah sem a tam. Je to prostě děje donekonečna. 

Proč jsou některé vozy pohybující se rychleji než ostatní? Jaký je rozdíl o těchto programech? Jo, pravděpodobně některé z nich užíváte více kroků najednou a některé z nich méně kroků najednou. A vizuální efekt je velmi pomalý proti. 

Co myslíš, že se stalo? Když jsem dostal žábu celou cestu přes ulici a řeku na lilie pad, něco pozoruhodný stalo. Co se stalo, hned jak jsem to udělal? To se zastavil. Že žába se zastavil, a Dostal jsem druhou žába. Takže to, co musí být konstrukt používán tam, jaké funkce? 

Jo, takže tam je nějaký druh "Kdyby" podmiňují tam nahoře, taky. A ukázalo se out-- jsme neviděli tohle-- ale je tu další bloky v tam, že Dá se říci, pokud jste dojemné Další věc, na obrazovce, pokud jste se dotýká lilie pad "a poté". A pak je to, když jsme aby se druhá žába objeví. Takže i když tato hra je určitě velmi starý, i když na první pohled tam je tolik děje on-- a Blake ani bič to ve dvou minut, to asi trvalo mu několik hodiny vytvořit tuto hru založený na jeho paměti nebo videa verze dávných dob je to. Ale všechny tyto maličkostí děje na obrazovce v izolaci redukuje na tyto velmi jednoduché constructs-- pohyby nebo prohlášení jako jsme diskutovali, smyček a podmínky, a to je o tom. Je tu několik dalších milovník rysy. Některé z nich jsou čistě estetické nebo akustické, jako zvuky Jen jsem hrál. Ale z větší části, budete mají v tomto jazyce, škrábání, všechny základní stavební kameny, které vás mají v C, Java, JavaScript, PHP, Ruby, Python, a jakýkoliv počet dalších jazyků. Jakékoliv otázky ohledně začátku? Dobře. Takže nebudeme ponořit hlouběji do nuly, když jste zač tento víkend, zvláště pokud máte děti nebo neteře a synovci a takové, uvést je do nuly. Je to vlastně úžasně hravé Prostředí se, jak jeho autoři říkají, velmi vysoké stropy. I když jsme začali s právě detaily low-level, můžete opravdu dost s ním, a to je možná ukázka přesně to. 

Ale pojďme teď přejít na něco víc sofistikované problémy, chcete-li, známý jako "vyhledávání" a "Třídění," obecněji. Měli jsme tento telefonní seznam zde earlier-- je ještě jeden jen pro discussion-- že jsme byli schopni vyhledávat efektivněji, protože významného předpokladu. A jen proto, aby bylo jasno, jaké předpoklad byl jsem dělat Při vyhledávání prostřednictvím tohoto telefonního seznamu? Že Mike Smith byl v telefonního seznamu, i když jsem by měl být schopen zvládnout Scénář bez něj tam, pokud jsem se předčasně ukončena. Kniha je abecední. A to je velmi velkorysý předpoklad, protože znamená someone-- Jsem typ řezání za roh, jako já rychleji, protože někým jiný udělal hodně tvrdé práce pro mě. 

Ale co když je telefon Kniha byla nevytříděné? Možná, že Verizon dostal líný, právě hodil Jména všech a čísla tam Možná v pořadí, v jakém přihlásili k telefonní služby. A kolik času zabere mi najít někoho, jako je Mike Smith? 1000 strana telefonu book-- kolik Stránky musím prohlédnout? 

Všichni. Vy jste nějak smůlu. Doslova se podívat na každý strana v případě, že telefonní seznam je jen náhodně třídit. Možná budete mít štěstí a najít Mika na první stránce, protože on byl první zákazník objednat telefonní služby. Ale on by mohl být poslední, taky. 

Takže náhodném pořadí není dobré. Takže předpokládám, že musíme seřadíte telefonním seznamu nebo v souhrnném třídění dat že nám byla dána. Jak můžeme udělat? 

No, dovolte mi pokusit jednoduchý příklad zde. Nech mě jít dopředu a hodit Několik čísel na palubě. Předpokládejme, že čísla, která máme, jsou řekněme, čtyři, dva, jedna a tři. A Ben, třídění těchto čísel pro nás. 

OK dobře. Jak jsi to udělal? Dobře. Takže začít s nejmenší hodnotou a nejvyšší, a to je opravdu dobrá intuice. A uvědomit si, že jsme lidé jsou vlastně docela dobrý v řešení problémů jako je tento, minimálně při data je relativně malý. Jakmile se začnete mít stovky čísel, tisíce čísel, milióny čísel, Ben pravděpodobně Nemohl to docela tak rychle, za předpokladu, že existují mezery v číslech. Docela snadno spočítat na milion V opačném případě pouze časově náročné. 

Takže to vypadá algoritmus jako Ben používá právě teď Byl hledat pro nejmenší číslo. Takže i když my lidé mohou mít v mnoha informací vizuálně, počítač je ve skutečnosti trochu omezenější. Počítač může jen podíváme na jeden byte v době nebo možná čtyři byty na první time-- v těchto dnech možná 8 bytů na jeden time-- ale velmi malý počet bytů v daném čase. 

Takže vzhledem k tomu, že skutečně máme čtyři oddělené hodnoty here-- a můžete si myslet, že mají Ben klapky na kdyby byl počítač jako že nevidí nic jiného, než jedno číslo při time-- takže jsme se obecně bude předpokládat, stejně jako v Angličtina, budeme číst zprava doleva. Takže první číslo Ben asi vypadal v Byly čtyři a pak se velmi rychle si uvědomil, že je to dost velký number-- nech mě hledat dál. 

Je tu dva. Počkej chvíli. Dva je menší než čtyři. Jdu si vzpomenout. Dva je nyní nejmenší. Nyní one-- je to ještě lepší. To je ještě menší. Jdu na to zapomenout dva a stačí vzpomenout si jej. 

A mohl přestat hledat? No, mohl založený Na základě těchto informací, ale už tak vyhledávání zbytek seznamu. Vzhledem k tomu, co když nulu byly v seznamu? Co když negativní některý z nich v seznamu? On jen ví, že jeho odpověď je správná, pokud je to vyčerpávajícím způsobem kontroluje celý seznam. Takže se podíváme na zbytek tohoto. Three-- to bylo plýtvání časem. Mám smůlu, ale byl jsem Stále správné, aby tak učinily. A tak teď podle všeho zvolili nejmenší počet a jen dát to na začátku seznamu, jak budu dělat. A teď, co jsi dělal dál, přestože jste si nemyslel, že o něm téměř v tomto rozsahu? Opakujte proces, takže nějaký druh smyčky. K dispozici je známý nápad. Tak tady jsou čtyři. To je v současné době nejmenší. To je kandidátem. Už ne. Teď jsem viděl dva. To je další nejmenší prvek. Three-- to není menší, takže Nyní Ben může vyklovnout dva. 

A teď jsme proces opakovat, a Samozřejmě tři dostane vytáhl další. Tento postup opakujte. Čtyři dostane vytáhl. A teď jsme z čísel, proto musí být seznam tříděn. 

A skutečně se jedná o formální algoritmus. Počítačový vědec by nazývají "Volba druhu" bytí nápadu třídění A znovu vypsat iteratively-- a znovu a znovu zvolením nejmenší číslo. A co je příjemné na tom je, je to prostě tak zatraceně intuitivní. Je to tak jednoduché. A můžete opakovat stejný znovu a znovu provoz. Je to jednoduché. 

V tomto případě se jednalo rychle, ale jak dlouho to vlastně trvá? Řekněme, aby se mohlo zdát, a cítit trochu únavné. Tak jeden, dva, tři, čtyři, pět šest, sedm, osm, devět, 10, 11, 12, 13, 14, 15, 16-- libovolný počet. Jen jsem chtěl víc to Doba než jen čtyři. Takže pokud mám jeden celek banda čísel to now-- ani jedno co are-- Řekněme přemýšlet o tom, co to Algoritmus je doopravdy. 

Předpokládejme, že existují čísla tam. Opět platí, že nezáleží na tom, jaké jsou, ale jsou náhodné. Žádám Benův algoritmus. Musím vyberte nejmenší číslo. Co mám dělat? A budu fyzicky dělat to tentokrát jednat to. Při pohledu, hledáte, hledáte looking. Teprve v době, kdy jsem se dostat do konec seznamu může Uvědomuji si nejmenší číslo bylo dvě tentokrát. Jednou to není v seznamu. Tak jsem si položil dva. 

Co mám dělat dál? Looking looking. Teď jsem našel číslo sedm, protože je tu mezery v těchto numbers-- ale jen subjektivní. Dobře. Takže teď můžu dát dolů sedm. Při pohledu hledá, hledá. 

Teď jsem za předpokladu, ze Samozřejmě, že Ben nemá extra RAM, extra paměť, protože, samozřejmě, Dívám se stejným číslem. Určitě jsem mohl pamatoval Ze všech těchto čísel, a to je naprostá pravda. Ale pokud Ben pamatuje všechny z čísel, že viděl, on není opravdu udělal zásadní pokrok protože už má schopnost vyhledávat přes čísla na palubě. Vzpomínka na všechny Čísla nepomůže, protože se může ještě jako počítač jen se podívat na, jsme řekli, jedním číslem včas. Takže není žádný druh podvodu tam, které můžete využít. 

Takže ve skutečnosti, jak jsem pokračovat v hledání v seznamu, Doslova jsem si to jen dál tam a zpět přes to, vyloupnutí druhý nejmenší počet. A jak si můžete odvodit druh z mých hloupých pohybů, to prostě dostane velmi únavné velmi rychle, a já se zdají být vracet a tam, tam a zpět docela dost. Teď abychom byli spravedliví, nemám jít zas až tak dobře, pojďme see-- být spravedlivý, Nemám chodit docela jako řada kroků, každý čas. Vzhledem k tomu, samozřejmě, jak jsem výběr čísel ze seznamu, zbývající seznam je čím dál kratší. 

A tak se pojďme přemýšlet o tom, kolik kroků jsem vlastně traipsing přes každý čas. V úplně první situaci jsme měli 16 čísel, a tak maximally-- Nechal jen to pro discussion-- Musel jsem se dívat až 16 Čísla najít nejmenší. Ale jakmile jsem vyloupíce nejmenší číslo, jak dlouho byl zbývající seznam, samozřejmě? Jen 15. Takže kolik čísel dělal Ben nebo mám prohlédnout podruhé kolem? 15, prostě jít a najít nejmenší. Ale teď, samozřejmě, jejichž seznam je, Také menší, než tomu bylo dříve. Tak kolik kroků udělal já muset vzít příště? 14 a pak 13 a poté 12 plus dot, tečka, tečka, dokud jsem odešel jen s jedním. Takže teď počítačový vědec by zeptat se, dobře, co dělá, že si všichni rovni? Je to vlastně rovná některými konkrétními Číslo, které bychom mohli jistě dělat aritmeticky, ale chceme mluvit o účinnosti algoritmů trochu víc formulaically, nezávisle na tom, jak dlouho je seznam. 

A tak víte co? To je 16, ale jak jsem řekl dříve, pojďme stačí zavolat na rozsah problému n, kde n je nějaké číslo. Možná je to 16, možná je to tři, možná je to milion. Nevím. Nezajímá mě. Co opravdu chci, je vzorec, který mohu použít k porovnání tohoto algoritmu s jinými algoritmy že někdo může tvrdit, jsou lepší nebo horší. 

Tak to dopadá, a to pouze já vím, že to od základní školy, že to vlastně vyjde na stejné věc jako n přes n plus jedna přes dva. A to se děje na rovné, z Samozřejmě, že n a n na druhou přes dva. Takže když jsem chtěl vzorec za kolik kroků byli zapojeni do pohledu na všechny of znovu a znovu těmito čísly a znovu a znovu, řekl bych, to n druhou a n přes dva. Ale víte co? To jen vypadá chaotický. Já jen opravdu chtít obecný smysl věcí. A ty by mohly vyvolat z vysoká škola, která tam je představa nejvyššího řádu termínu. Který z těchto podmínek, n čtvercový, N, nebo polovinu, má největší dopad v průběhu času? Čím větší n dostane, což z těchto záležitostí nejvíce? 

Jinými slovy, pokud se připojíte z milionu, n čtvercový bude s největší pravděpodobností dominantním faktorem, Vzhledem k tomu, miliónkrát sama o sobě je mnohem větší než plus jeden další milion. Tak víte co? Je to tak velký zašít číslo, pokud náměstí číslo. To opravdu nezáleží. Budeme jen kříž, který out a zapomenout na to. A tak počítačový vědec by se říci, že účinnost tohoto algoritmu je v řádu n squared-- Mám na mysli skutečně přiblížení. Je to jakýsi zhruba n druhou. V průběhu doby, tím větší a větší n dostane toto Je to dobrý odhad pro to, co efektivita nebo nedostatek účinnosti tohoto algoritmu ve skutečnosti je. A já odvodit, že, samozřejmě, od skutečně dělá matematiku. Ale teď jsem jen mávání mé ruce, protože jsem zrovna Chcete obecný smysl tohoto algoritmu. 

Takže za použití stejné logiky, zatím, uvažujme jiný algoritmus už vypadal at-- lineární hledání. Když jsem hledal pro telefonní book-- Není jejich třídění, vyhledávání přes telefonní book-- jsme pořád říkala, že to bylo 1000 kroky, nebo 500 kroků. Ale pojďme generalizovat to. Pokud existuje n stránek v telefonní seznam, co je doba chodu nebo Účinnost lineární hledání? Je to v řádu kolik kroků k nalezení Mike Smith pomocí lineární vyhledávání, První algoritmus, nebo i druhý? 

V nejhorším případě, Mike je na konci knihy. Takže v případě, že telefonní seznam má 1000 stránek, jsme si řekli minule, v nejhorším případě, to může trvat zhruba jak mnoho stránek najít Miku? Stejně jako 1,000. Je to horní mez. Je to nejhorší možné situaci. Ale opět, jdeme pryč z čísel, jako je nyní 1000. Je to jen n. 

Tak jaký je logický závěr? Nalezení Mika v telefonu Kniha, která má n stran může trvat, v nejhorším případě, kolik kroků v řádu n? A opravdu počítačový vědec by se říci, že běží čas nebo se výkonnost nebo účinnost nebo neúčinnost, algoritmu, jako je lineární vyhledávání v řádu n. A můžeme aplikovat stejný Logika křížení něco jak jsem právě udělal do druhého Algoritmus jsme měli s telefonním seznamu, kde jsme udělali dvě stránky najednou. 

Takže 1000 strana telefonní seznam by mohl nás zavede 500 otočených stran, plus jedna pokud bychom zdvojnásobit zpět trochu. Takže pokud telefonní seznam má n stran, ale děláme dvě stránky najednou, To je zhruba to, co? N přes dva, takže to jako n přes dva. Ale já jsem udělal nárokovat Před okamžikem, že n přes two-- to je druh stejné jako právě n. Je to jen konstantní faktor, počítačoví odborníci by se říci. Pojďme se zaměřit pouze na proměnné, really-- největší proměnné v rovnici. 

Takže lineární vyhledávání, zda udělal jednu Strana najednou nebo dvě stránky najednou, je něco v podstatě stejné. Je to stále v řádu n. Ale já tvrdil s mým obrázku dříve že třetí algoritmus nebyl lineární. Bylo to není přímka. Bylo to, že křivka, a algebraické rovnice nebylo co? Log n- takže log základnu dva n. A nemusíme jít do příliš mnoho detailů na logaritmy dnes, ale většina počítačoví odborníci nechtěli i ti, co je základna. Vzhledem k tomu, že je to všechno jen konstantní faktory, tak říkajíc, Jen drobné číselné rozdíly. A tak by to bylo velmi časté způsob, zejména formální počítače Vědci na palubě nebo programátoři na bílou tabuli ve skutečnosti tvrdí, které Algoritmus by se používat nebo to, co je účinnost z jejich algoritmus. 

A to není nutně něco diskutujete v každém detailu, ale dobrý programátor je ten, který má pevnou, formální pozadí. On je schopen mluvit vám v tomto druhu cesty a vlastně dělat kvalitativní argumenty jako proč jeden algoritmus nebo jeden kus softwaru je lepší než nějakým způsobem do druhého. Protože ty by jistě stačí spustit program, jednoho člověka a spočítat počet sekund trvá třídit nějaká čísla, a můžete spustit některé Program jiné osoby a počítání sekund trvá. Ale to je obecnější způsob, můžete použít k analýze algoritmů, chcete-li, jen na papíru nebo jen slovně. Aniž by si běží to, aniž dokonce se snaží vzorové vstupy, můžete jen rozum přes něj. A tak s pronájmem vývojáře, nebo pokud mít ho nebo ji nějak argumentovat pro vás proč jejich algoritmus, jejich tajemství omáčka pro vyhledávání miliardy webových stránek pro vaše Firma je lepší, tito jsou druhy argumentů, že by v ideálním případě být schopen provést. Nebo alespoň to jsou druhy věcí které by přijít v diskuzi, při alespoň ve velmi formální diskuse. Dobře. Takže Ben navrhované něco volal výběr třídit. Ale budu navrhovat, že je tu jiné způsoby, jak to udělat taky. To, co jsem neměl opravdu rád o Benově algoritmu je to, že šel dál, nebo co mě chodit sem a tam a sem a tam a sem a tam. Co když místo toho jsem měl dělat něco podobného těchto čísel zde a já jsme byli jen jednat s každým číslo v pořadí, jak jsem vzhledem k tomu, že? 

Jinými slovy, je zde můj seznam čísel. Čtyři, jedna, tři, dva. A já budu dělat následující. Jdu vložit čísla kam patří spíše Kromě výběru jim jeden po druhém. Jinými slovy, tady je číslo čtyři. 

Tady je můj původní seznam. A budu zachovávat v podstatě nový seznam zde. Tak tohle je starý seznam. Jedná se o nový seznam. Vidím, že číslo čtyři první. Můj nový seznam je zpočátku prázdný, tak je tomu v případě triviálně že čtyři je nyní roztříděný seznam. Já beru jen to číslo jsem dal, a já ho uvedení ve svém novém seznamu. 

Je seřazen tento nový seznam? To jo. Je to hloupé, protože tam je jen jeden prvek, ale je to naprosto třídit. Není nic na svém místě. Je to mnohem zajímavější, tento algoritmus, když jsem se přesunout k dalšímu kroku. 

Teď mám jeden. Tak jeden, samozřejmě, patří u začátek nebo konec tohoto nového seznamu? Začátek. Takže musím udělat nějakou práci hned. Bral jsem některé svobody s mou značku pouhým kreslení věci kde chci jim, ale ve skutečnosti to není přesný v počítači. Počítač, jak víme, má RAM, nebo Random Access Memory, a to je jeden bajt a další byte a další byte. A pokud máte gigabajt RAM, máte miliardě bajtů ale jsou fyzicky na jednom místě. Nemůžete jen přesunout věci kolem tím, že ho na tabuli kamkoliv chceš. Takže pokud můj nový seznam musí Čtyři místa v paměti, Bohužel čtyři je Již na špatném místě. 

Takže vložit číslo jedna Nemůžu jen tak kreslit jej sem. Toto místo v paměti neexistuje. To by bylo podvádění, a byl jsem podvádění obrazově po dobu několika minut zde. Takže opravdu, když chci dát jeden tady, Musím se dočasně zkopírovat čtyři a pak dal ten tam. 

To je v pořádku, to je v pořádku, je to technicky možné, ale uvědomit, že je to práce navíc. Nechtěl jsem jen dát číslo na svém místě. Nejdřív jsem musel přesunout číslo, pak ji na místě, tak nějak jsem zdvojnásobil svůj objem práce. Takže mějte na paměti, že. 

Ale já jsem teď udělal s tímto prvkem. Teď chci chytit číslo tři. V případě, samozřejmě, to patří? Mezi. Nemůžu podvádět už a prostě to tam dal, protože, znovu, této paměti je ve fyzických místech. Takže mám zkopírovat čtyři a dal tři sem. Není velký problém. Je to jen jeden krok navíc again-- cítí velmi levná. 

Ale teď jsem se přesunout na dva. Dva, samozřejmě, patří sem. Nyní můžete začít sledovat, jak Práce může nahromadit. A teď, co mám dělat? Jo, mám přesunout čtyři, pak musím zkopírovat tři, a teď můžu vložit dva. A úlovek s tímto algoritmus, je dost zajímavé, je, že předpokládám, že máme více extrémní případ, kdy je to řekněme, osm, sedm, šest, pět, čtyři, tři, dva, jedna. To je, v mnoha kontextech, nejhorší možný scénář, protože zatracenou věc je doslova pozpátku. 

To není opravdu ovlivní Benův algoritmus, protože v Benově výběru sort že to bude držet tam a zpět přes seznam. A protože byl stále hledá po celou zbývající seznamu to nevadí kde jsou prvky. Ale v tomto případě se svým vkládání approach-- zkusme to. 

Tak jeden, dva, tři, čtyři, pět, šest, sedm, osm. Jedna dva tři čtyři, pět, šest, sedm, osm. Chystám se vzít osm, a kde mám dát? No, na začátku mého seznamu protože tento nový seznam je seřazen. A já ji přejíždějí ven. 

Kam mám dát sedm? Sakra. Je třeba jít tam, tak Musím udělat nějaké kopírování. A teď sedm chodí sem. Teď jsem se přesunout na šest. Teď je to ještě víc práce. 

Osm musí jít sem. Sedm musí jít sem. Nyní je šest může jít sem. Teď jsem chytit pět. Nyní osm musí jít tady, sedm musí jít sem, šest musí jít sem, a nyní pět a opakovat. A jsem docela hodně pohybující se to neustále. 

Takže na konci, to algorithm-- zmíníme říkat vložení sort-- vlastně Má hodně práce, taky. Je to prostě jiný druh práce, než Bena. Benův práce měla mě děje sem a tam po celou dobu, zvolení příští nejmenší znovu a znovu element. Tak to bylo to velmi vizuální druh práce. 

Tento jiný algoritmus, který je ještě correct-- to dostane práci done-- Jen změní množství práce. Vypadá to, že zpočátku budete úsporu, protože jsi zrovna jednání s každým prvkem vepředu, aniž by šel all cesta přes seznamu jako Ben byl. Ale problém je, a to zejména v těch bláznivé případy, kdy je to všechno obráceně, jsi jen trochu odkládá těžkou práci dokud nebudete mít na opravu chyby. 

A tak pokud můžete si to představit osm a sedm a šest a pět a později čtyři a tři a dva pohybující se jejich cestu přes seznamu jsme právě změněn druh práce děláme. Namísto toho, jak to dělá u počátek mé iteraci Dělám jen to u Konec každé iteraci. Tak to dopadá, že tento algoritmus, Také obecně nazývané insertion sort, je také na objednávku n čtvercový. Je to vlastně o nic lepší, o nic lepší vůbec. 

Nicméně, tam je třetina přístup Byl bych nás povzbudit, aby zvážila, který je to. Takže předpokládám, že můj seznam, pro jednoduchost znovu, je čtyři, jedna, tři, two-- jen čtyři čísla. Ben měl dobrou intuici, dobrý člověk intuice Před tím, kterou pevné celý Seznam eventually-- insertion sort. nám vyprosil jsem dál. Ale pojďme zvážit Nejjednodušší způsob, jak opravit tento seznam. 

Tento seznam není seřazena. Proč? V angličtině, vysvětlit, proč to není ve skutečnosti třídit. Co to znamená nebýt řazeny? 

STUDENT: To není sekvenční. 

DAVID Malan: Není sekvenční. Dejte mi příklad. 

STUDENT: Dejte je v pořádku. 

DAVID Malan: OK. Dej mi víc konkrétní příklad. 

STUDENT: vzestupném pořadí. DAVID Malan: Není vzestupně. Být přesnější. Nevím, co myslíš tím vzestupně. Co je špatně? 

STUDENT: Nejmenší z Čísla není v prvním prostoru. 

DAVID Malan: Nejmenší číslo je není v prvním prostoru. Být konkrétnější. Začínám pochopit. Počítáme, ale co je mimo provoz tady? 

STUDENT: číselné posloupnosti. DAVID Malan: číselné posloupnosti. druh věcí každého z chovu to here-- velmi vysokou úroveň. Jen mi doslova říct, co je špatně jako pět let staré síle. 

STUDENT: Plus jeden. 

DAVID Malan: Co je to? 

STUDENT: Plus jeden. 

DAVID Malan: Co tím myslíš plus jedna? Dej mi jiný pět-letý. Co se děje, mami? Co se děje, tati? Co tím myslíš, to není řazeny? 

STUDENT: To není to správné místo. 

DAVID Malan: Co je není na správném místě? 

STUDENT: Čtyři. DAVID Malan: OK, dobře. Takže čtyři není tam, kde by měla být. Zejména, je to pravda? Čtyři a jeden, první dvě čísla Aha. Je to správně? Ne, oni jsou mimo provoz, ne? Ve skutečnosti, že teď o počítači, taky. Může se pouze na možná jeden, možná dvě věci once-- a vlastně jen jedna věc v době, ale může alespoň podívat se na jednu věc, pak Další věc, kterou hned vedle něj. 

Takže jsou tyto v pořádku? Samozřejmě, že ne. Tak víte co? Proč ne vezmeme dítě Kroky upevňovací tento problém namísto toho, aby tyto fantazie algoritmy jako Ben, kde Je to vlastně trochu upevnění ji smyčky v seznamu místo toho dělat to, co jsem udělal, kde I tak nějak připevnil ji, jak jsme jít? Řekněme doslova rozebrat Pojem order-- číselném pořadí, říkat cokoliv want-- Do těchto párová srovnání. 

Čtyři a. Je to správné pořadí? Takže pojďme napravit. Jeden a čtyři, a poté budeme jen zkopírovat to. Dobře, dobře. Opravil jsem jeden a čtyři. Tři a dvě? Ne. Nechť moje slova odpovídala prsty. Čtyři a tři? 

Není to v pořádku, takže jdu dělat jeden, tři, čtyři, dva. OK dobře. Nyní čtyři a dvě? Musíme to opravit taky. Tak jeden, tři, dva, čtyři. Takže je to řazeny? Ne, ale je to blíž do tříděného? 

Je to proto, že jsme opravil toto chyba, jsme opravili tuto chybu, a my pevně tuto chybu. Takže jsme opravili tři chyby pravděpodobně. Stále není opravdu vypadají tříděny, ale je objektivně blíže do tříděného protože jsme pevně některé z těchto chyb. 

A teď, co mám dělat dál? Tak nějak jsem došel na konec seznamu. Zdálo se, že jsem fixní všechny chyby, ale ne. Vzhledem k tomu v tomto případě, některé čísla mohl bublal blíž do jiných čísel, která jsou stále mimo provoz. Takže pojďme udělat to znovu, a budu Jen to v místě tentokrát. Jeden a tři? To je v pořádku. Tři a dvě? Samozřejmě že ne, tak se pojďme změnit. Tak dva, tři. Tři a čtyři? A teď pojďme být jen Zvláště tady pedantský. Je to řazeny? Vy lidé vím, že to třídit. 

Měl bych zkusit znovu. Takže Olivia navrhuje I zkuste to znovu. Proč? Protože počítač nemá luxus našich lidských očí pouhého podíval back-- OK, jsem udělal. Jak se počítač určí že seznam je nyní řazeny? Mechanicky. 

Měl bych projít ještě jednou, a to pouze v případě, I nedělají / najít žádnou chybu mohu pak uzavře jako počítač, jo, jsme dobří jít. Aby jedna a dvě, dvě a tři, tři a čtyři. Teď můžu konečně říct, že je tříděny, protože jsem nedělal žádné změny. Teď to bude chyba a jen Pokud bych hloupý, počítač, zeptal se ty stejné otázky znovu očekával různé odpovědi. By se nemělo stát. 

A tak teď je seřazen seznam. Bohužel, doba běhu Tento algoritmus je také N druhou. Proč? Protože máte n čísel, a ve nejhorším případě budete muset přesunout n čísel n časy, protože musíte jít dál zpět zkontrolovat a případně opravit tato čísla. A můžeme udělat víc formální analýza, taky. 

Tak to je vše, říci, že jsme si vzít tři různé přístupy, jeden z nich okamžitě intuitivní off netopýra z Ben mé navrhované vložení řadit k tomuhle kde jste druh ztrácet ze zřetele les pro stromy zpočátku. Ale pak, když jdete o krok zpět, voila, máme fixní třídění představu. Takže tohle je, troufám tvrdit, nižší úroveň snad než někteří z těch, ostatní algoritmy, ale pojďme uvidíme, jestli nemůžeme představit Tyto prostřednictvím tohoto. 

Takže to je nějaký pěkný software, který někdo napsal pomocí barevné pruhy, aby to dělat následující pro nás. Každý z těchto tyčí představuje číslo. Vyšší je sloupec, tím větší číslo, menší bar, čím menší je počet. Takže v ideálním případě chceme krásný pyramidu kde začíná malý a dostane velký, a to by znamenalo, že Tyto tyče jsou řazeny. Takže já jdu dopředu a zvolit, Například, Benův algoritmus first-- výběr třídit. 

A všimněte si, co dělá. Způsob, jakým jste se rozhodli vizualizovat tento algoritmus je, že stejně jako já procházel mém seznamu, Tento program je chůze prostřednictvím svého seznamu čísel, zvýraznění v růžové každého Číslo že to dívá. A co se stane teď? 

Nejmenší číslo, které I nebo Ben našel náhle se přesune na začátek seznamu. A všimněte si udělali vypudit číslo, které tam byl, a to je naprosto v pořádku. Nedostal jsem se do této úrovni detailu. Ale musíme dát toto číslo někde, tak jsme ho přestěhovali do otevřené místo, které bylo vytvořeno. Tak jdu k urychlení tohoto up, protože jinak se stává velmi únavné rychle. Animace speed-- tam jdeme. Takže teď Stejný princip Byl jsem uplatňují, ale vy může začít cítit algoritmus, pokud se vůle, nebo to vidět trochu jasněji. A tento algoritmus má za následek výběru dalšího nejmenší prvek, takže budete začít vidět to rozjet na levé straně. A na každé iteraci, jak jsem navrhováno, to dělá trochu méně práce. Nemusí jít celou cestu zpět na levý konec seznamu, protože již zná ty jsou řazeny. Takže to trochu pocit, jako by to zrychluje, i když každý krok je přičemž stejné množství času. Je tu jen méně kroků zbývající. A teď se můžete trochu cítit Algoritmus vyčištění její konec, a opravdu teď je to třídit. 

Takže insertion sort je vše hotovo. Musím znovu náhodně pole. A všimněte si mohu jen udržovat randomizing to, a dostaneme aproximaci stejný přístup, vložení sort. Nech mě to zpomalit až sem. Začněme že v průběhu. Stop. 

Pojďme přeskočit čtyři. Tam jedeme. Náhodně oni pole. A tady jsme go-- insertion sort. Hrát. Všimněte si, že to zacházení s jednotlivým prvek narazí hned, ale v případě, že patří do špatné oznámení místa všechny práce, která má dít. Musíme se držet přesouvá více a další prvky, aby se vytvořil prostor Pro jednoho chceme zavést. 

Takže jsme se zaměřením na levý konec jediného seznamu. Všimněte si, jsme ani my vypadal at-- ještě zvýrazněny v růžové cokoliv doprava. Právě jsme se zabývají problémy, jak jsme jít, ale my jsme vytvořit hodně pracovat pro sebe pořád. A tak pokud bychom toto urychlit Nyní jít do dokončení, má jiný pocit na to opravdu. Je to jen se zaměřením na levém konci, ale dělá trochu více práce jako needed-- druh vyhlazování věcí přes, napravuješ, ale nakonec zabývající se každý prvek jeden po druhém až se dostaneme do dobře the--, my Všichni víme, jak to skončí, takže je to trochu nezaujatý možná. 

Ale Seznam v end-- spoiler-- se bude třídit. Takže pojďme se podívat na jeden poslední. Nemůžeme jen tak přeskočit teď. Už tam skoro jsme. Dva jít, kdo jít. A voila. Vynikající. 

Takže teď pojďme udělat jednu poslední, re-randomizing s bublinou druhu. A všimněte si tady, zvlášť když jsem ho zpomalit dolů, to se udržet snášet projít. Nevšimnout to prostě dělá po dvojicích comparisons-- druh místních řešení. Ale jakmile se dostaneme do konec seznamu v růžové, co se muselo stát znovu? Jo, to bude muset začít znovu, protože to jen Pevné párové chyby. A to by mohl odhalit ještě další. A tak když se toto urychlit, budete vidět, že, stejně jako název napovídá, menší elements-- nebo spíše, větší elements-- začínají bublat až na vrchol, chcete-li. A menší prvky jsou začíná bublat dolů doleva. A vskutku, to je druh Vizuální efekt stejně. A tak to bude skončit dokončovací práce ve velmi podobným způsobem, taky. 

Nemáme k bydlení na tento konkrétní jeden. Dovol mi otevřít to teď taky. Je tu několik dalších třídící algoritmy ve světě, málo z nich Zde jsou zachyceny. A to zejména pro studenty, kteří nejsou nutně vizuální nebo matematické, jak tomu bylo dříve, můžeme Také to audially pokud budeme spojovat zvuk s tím. A jen tak pro zábavu, tady je Několik různých algoritmů, a jeden z nich, zejména jste bude všimnout, se nazývá "merge sort." 

Je to vlastně zásadně lepší algoritmus, tak, aby sloučit druh, jedním z ty se chystáte vidět, Není řád n druhou. Je to v řádu n-krát logaritmu n, což je ve skutečnosti menší, a tudíž rychleji než ostatní tři. A je tu další pár ty hloupé, že uvidíme. 

Tak jdeme na to s nějakým zvukem. To je insertion sort, takže opět je to jen do činění s prvky jak přijdou. To je bublina třídit, takže je to s ohledem jim párů najednou. A opět největšími elementy vyvěrá až na vrchol. 

Další na řadě výběr třídit. To je Benův algoritmus, kde Znovu on výběrem iterativně druhý nejmenší prvek. A opět, nyní si můžete skutečně slyšet, že to urychlit, ale jen do té míry, jak to dělá méně a méně práce na každém opakování. To je rychlejší jedno, merge sort, který je třídění shluky čísel dohromady a pak je kombinovat. Takže look-- levý polovina je již řazeno. 

Teď je to třídění pravou polovinu, a Nyní to bude zkombinovat do jednoho. To je něco, co nazývá "Gnome sort." A můžete trochu vidět, že to tam a zpět, kterým se práce trochu tady a že před tím, než pokračuje do nové práce. A to je vše. Je tu jiný druh, který je opravdu jen pro akademické účely, volal "hloupý druh", který bere vaše data, třídí to náhodně, a zkontroluje, je-li seřazeny. A pokud tomu tak není, to re-třídí jej náhodně, zkontroluje, zda je to tříděny, a pokud ne, opakuje. A teoreticky, pravděpodobnostně Tím se dokončí, ale po docela dost času. Není to nejvíce účinné algoritmů. Takže jakékoliv otázky týkající se těch, Konkrétní algoritmy nebo cokoliv vztahující se tam taky? 

Dobře, pojďme teď šprýmaři odděleně co všechno Tyto linky jsou, že jsem byl kreslení a to, co jsem za předpokladu, že počítač může dělat pod kapotou. Řekl bych, že všechny z těchto čísel Pořád drawing-- oni potřebují dostat uložené někde v paměti. Budeme se zbavit toho chlapa teď taky. 

Takže kus v paměti computer-- takže RAM DIMM je to, co jsme hledali včera, dual inline memory module-- vypadá takto. A každý z těchto malých černých čipů je nějaký počet bajtů, typicky. A pak zlaté kolíky jsou stejně jako dráty, které ji připojit k počítači, a zelený křemík deska je prostě co drží všechno pohromadě. Takže co to vlastně znamená? Kdybych druh nakreslit stejný obrázek, Předpokládejme pro jednoduchost že tento DIMM, dual inline paměťový modul, Je jedno GB paměti RAM, jeden gigabajt paměť, která je, kolik bytů celkem? Jeden gigabajt je to, kolik bytů? Víc než to. 1124 je kilo, 1000. Mega je milion. Giga je miliarda. 

Lžu? Můžeme dokonce číst etiketu? To je vlastně 128 GB, takže je to víc. Ale budeme předstírat, že toto Je jen jeden gigabajt. Takže to znamená, že je o miliardu bajtů paměti k dispozici pro mě nebo 8 miliard bitů, ale jdeme mluvit, pokud jde o bytech nyní, kupředu. 

Takže to, co to znamená, že je to jeden byte, je to další bajt, Jedná se o další bajt, a kdybychom opravdu chtěli být konkrétní budeme muset čerpat miliardu malé čtverce. Ale co to znamená? No, dovolte mi zoom na tomto obrázku. Pokud mám něco, co vypadá jako je to teď, to je čtyři bajty. 

A tak jsem mohl dát čtyři čísla zde. Jedna dva tři čtyři. Nebo bych mohl dát čtyři písmena nebo symboly. "Ahoj!" může jít přímo tam, protože každý z dopisů, jsme diskutovali dříve, by mohl být zastoupen s osmi bitů nebo ASCII nebo byte. Takže jinými slovy, můžete dát 8 miliard věci uvnitř tato jedna hůl paměti. A teď co to znamená dát věci zpět se zády v paměti takhle? To je to, co programátor by se nazvat "pole." V počítačovém programu, si nemyslím, že o hardwarem, samy o sobě. Ty prostě myslet na sebe jako vlastnění Přístup k celkově o miliardě bajtů a můžete co chcete s ním. Ale pro pohodlí je obecně užitečné aby se vaše paměť právo vedle sebe, jako to. Takže když jsem se přiblížit na tohle-- protože my rozhodně nebudeme čerpat miliardy trochu squares-- Dejme tomu, že tato deska představuje že hůl paměti hned. A já budu jen čerpat tolik jako my Značka skončí mi dává sem. Takže teď máme hůl paměti na desce který má jeden, dva, tři, čtyři, pět, šest, jeden, dva, tři, čtyři, pět, šest, sedmé takže 42 bajtů paměť na celkovou obrazovky. Děkuji. Ano, udělal můj aritmetický pravdu. tady tak 42 bajtů paměti. Takže co to vlastně znamená? No, počítačový programátor by ve skutečnosti obecně myslíte o této paměti jako adresovat. Jinými slovy, každý z nich místa v paměti, v hardwaru, má jedinečnou adresu. 

Není to tak složité, jako jeden Brattle Square, Cambridge, Mass., 02138. Místo toho, je to jen číslo. To je byte číslo nula, to je jeden, to je dvě, to je tři, a to je 41. Počkej chvíli. Myslel jsem, že jsem řekl 42 před chvílí. Začal jsem počítat od nuly, takže je vlastně správné. Teď nemáme na to skutečně čerpat jako mřížka, a pokud ji nakreslit jako mřížka Myslím, že se věci ve skutečnosti dostat trochu zavádějící. Co programátor by, v jeho vlastní mysli, obecně myslet na to Paměť jako je stejně jako páska, jako kus krycí páskou že prostě pokračuje dál a dál navždy nebo dokud vám dojdou paměti. Takže častější způsob, jak čerpat a jen přemýšlet o paměti by se, že je to byte nula, jedna, dva, tři, a pak tečka, tečka, tečka. A máš celkem 42 takových bytů, a to i i když fyzicky mohlo by to ve skutečnosti být něco víc takhle. 

Takže pokud si nyní myslí vašich paměť, protože to, stejně jako páska, to je to, co programátor znovu by vyžadovalo řadu paměti. A když chcete skutečně uložit něco v paměti počítače, budete obecně dělat uložení věcí back-to-back back-to-back. Takže jsme mluvili o číslech. A když jsem chtěl řešit problémy stejně jako čtyři, jedna, tři, dva, i když jen jsem byl kreslení pouze čísla čtyři, jedna, tři, dva na palubě, by počítač Opravdu mají toto nastavení do paměti. 

A co by bylo vedle dva v paměti počítače? No, není odpověď na tuto otázku. My opravdu nevím. A tak dlouho, dokud Počítač nepotřebuje, to nemusí starat, co je další s čísly, že se zajímá o. A když jsem dříve řekl, že v počítači může se pouze na jedné adrese v době, To je druh proč. 

Ne na rozdíl od záznamu přehrávačem a čtecí hlava budou moci prohlédnout určitá jen Drážka ve fyzickém záznamu old-school v době, obdobně může počítač díky k jeho CPU a jeho Intel instrukční sada, mezi jehož pokyn se čte z paměti nebo uložit do memory-- Počítač může jen dívat na jednom místě při time-- někdy i jejich kombinace, ale opravdu jen jedno místo najednou. Takže když jsme dělali tyto různé algoritmy, Nejsem jen psaní v vacuum-- čtyři, jedna, tři, dva. Tato čísla skutečně patřit někde fyzické paměti. Takže tam jsou malinké tranzistory nebo nějaký druh elektroniky pod kapuce ukládání těchto hodnot. 

A celkem, kolik bitů podílejí právě teď, jen aby bylo jasno? Tak tohle je čtyři byty, nebo Nyní je to 32 bitů celkem. Takže tam jsou vlastně 32 nuly a Ti tvořící tyto čtyři věci. Tam je ještě tady, ale Znovu jsme se nestarají o to. 

Takže teď pojďme položit další Otázkou pomocí paměti, proto, že na konci dne je v rozporu. Bez ohledu na to, co bychom mohli dělat s počítač, na konci dne hardware je stále Stejný pod kapotou. Jak bych ukládat slovo tady? No, slovo v počítači, jako "Ahoj!" by byly uloženy, stejně jako to. A pokud byste chtěli delší Slovo, můžete jednoduše přepsat, že i něco říct jako "ahoj" a obchod, který zde. 

A tak i zde to contiguousness je ve skutečnosti výhodou, protože počítač může jen číst zprava doleva. Ale tady je otázka. V souvislosti s tímto slovem, h-e-l-l-o, vykřičník, jak by počítač vědět, kde je Slovo začíná a kde slovo končí? V souvislosti s čísly, jak dělá počítač vědět, jak dlouho sled Čísla je nebo tam, kde to začíná? No, to ukáže out-- a nepůjdeme příliš mnoho do této úrovně detail-- Počítače pohybovat věci kolem v paměti doslova prostřednictvím těchto adres. Takže v počítači, pokud jste psaní kódu k uložení věcí jako slova, co jste opravdu dělají, je psaní výrazy, které si vzpomenout, kde v Paměť počítače jsou tato slova. Tak mě nech dělat velmi, velmi jednoduchý příklad. 

Chystám se jít dopředu a otevírají jednoduchého textového programu, a jdu k vytvoření soubor s názvem hello.c. Většina těchto informací jsme nepůjde do velmi podrobně, ale budu psát Program v tomto jazyce, C. To je mnohem víc zastrašující, Tvrdím, než Scratch, ale je to velmi podobné v duchu. Ve skutečnosti tyto vlnité braces-- můžete druh myslet na to, co jsem právě udělal, protože to. 

Jdeme na to, ve skutečnosti. Když zelená vlajka kliknutí proveďte následující. Chci vytisknout "Dobrý den." Takže toto je nyní pseudocode. Jsem typ rozmazání linky. V jazyce C, tento jazyk mluvím o tento řádek print ahoj ve skutečnosti se stává "printf" s Některé závorky a středník. 

Ale je to přesně stejný nápad. A to velmi uživatelsky příjemný "Při zelenou vlajkou klepnutí" se stává mnohem více tajemný "int main neplatné." A to opravdu nemá mapování, tak jsem jen tak ignorovat. Ale složené závorky jsou stejně jako zakřivené dílky takhle. 

Takže si můžete trochu hádat. Dokonce i když jste nikdy předtím naprogramován, Co tento program pravděpodobně dělat? Pravděpodobně vytiskne ahoj s vykřičníkem. 

Takže pojďme to zkusit. Chystám se ho zachránit. A to je opět velmi old school prostředí. Nemohu na tlačítko, nemohu přetáhnout. Musím psát příkazy. Takže chci spustit svůj program, takže Mohl jsem to udělat, stejně jako hello.c. To je ten soubor jsem běžel. Ale počkejte, já jsem chybí krok. Co udělal říkáme, je nezbytným krokem pro jazyk C? Právě jsem napsal zdroj kód, ale co k tomu potřebuji? Jo, musím kompilátoru. Takže na mém počítači Mac tady, mám program s názvem GCC, GNU C kompilátor, který mi umožňuje dělat tohle-- zatáčku můj zdrojový kód do, budeme říkat, strojový kód. 

A vidím, že opět následujícím způsobem, tyto jsou nuly a ty, které jsem právě vytvořený ze svého zdrojového kódu, všechny nul a jedniček. A když chci spustit my program-- se to stane být nazýván a.out pro historická reasons-- "Dobrý den." I to může běžet znovu. Ahoj ahoj ahoj. A zdá se, že pracuje. 

Ale to znamená, že někde v mém Paměť počítače jsou slova h-e-l-l-o, vykřičník. A ukázalo se, stejně jako stranou, co je to počítač by typicky tomu, že ví, kde věci začnou a end-- je to bude klást zvláštní symbol tady. A konvence je umístit číslo nula na konci slova takže víte, kde to skutečně končí, takže nevedou vytisknout víc a víc znaky, než si ve skutečnosti v úmyslu. 

Ale stánek s jídlem tady, a to i ačkoli to je docela tajemný, je, že to nakonec relativně jednoduché. Jste dostali jakousi pásku, prázdné Prostor na které můžete psát dopisy. Vy prostě musíte mít Speciální symbol, jako je libovolně číslo nula, aby na konci vaše slova tak, aby počítač ví, oh, měl bych přestat tisku po Vidím vykřičník. Vzhledem k tomu, další věc, kterou zde je ASCII hodnota nula, nebo null charakter as někdo by se to nazvat. Ale je tu trochu problém tady a pojďme vrátit čísel na chvíli. Předpokládejme, že mám ve skutečnosti, mají celou řadu čísel, a předpokládejme, že Program píšu je jako stupeň knihy pro učitele a učitelů ve třídě. A tento program mu umožňuje zadat skóre svých žáků Na vyslýchá. A předpokládám, že student dostane 100 na svém prvním testu, možná jako 80 na ten příští, pak 75, pak 90 na čtvrtém testu. 

Takže v tomto bodě příběhu, pole je velikosti čtyři. Tam je absolutně větší množství paměti v počítač, ale pole, abych tak řekl, je o velikosti čtyři. Předpokládejme nyní, že učitel chce přiřadit pátý kvíz na třídu. No, jedna z věcí, nebo ona bude muset dělat Nyní je uložit dodatečnou hodnotu zde. Ale pokud pole má učitel vytvořené v tomto programu je velikosti pro, jeden z problému s polem je, že můžete nejen držet přidání do paměti. Vzhledem k tomu, co když jiné části Program má slovo "hej" právě tam? 

Jinými slovy, má paměť může být použít na cokoliv v programu. A pokud se předem jsem zadal, hej, Chci vstup čtyř kvíz skóre, Mohou jít zde a zde. A pokud se náhle změní svůj názor později a že chci pátý kvíz skóre, můžete nejen dát kamkoli budete chtít, protože co kdyby to Paměť je používán o něco else-- nějaký jiný program nebo jiné funkce programu že vedete? Takže musíte myslet dopředu Jak chcete uložit svá data, protože teď jsi namaloval yourself do digitálního rohu. 

Takže učitel by mohl místo říci, kdy psaní programu pro uložení jeho nebo její stupně, víte co? Budu požadovat, Při psaní můj program, že chci nula, jedna, dva, tři, čtyři, pět, šest, osm stupňů celkem. Tak jeden, dva, tři, čtyři, pět, šest, sedm, osm. Učitel může jen něco málo přes přidělit paměti při psaní jeho nebo její program, a říkat, víte co? Nikdy nebudu přiřadit více než osm vyslýchá v semestru. To je prostě šílené. Už nikdy přidělit to. Tak, že tento způsob on nebo ona má Flexibilita pro ukládání studentské skóre, stejně jako 75, 90, a možná jeden navíc, pokud student dostal kreditu navíc, 105. 

Ale v případě, že učitel nikdy používá tyto tři mezery, je tu intuitivní stánek s jídlem zde. On nebo ona je jen plýtvání místem. Takže jinými slovy, tam je to Společný kompromis při programování kde si můžete buď přidělit přesně tolik, kolik paměti, jak chcete, Vzhůru z nich je, že jsi výborný efficient-- nejste být nehospodárné na all-- ale nevýhoda, z nichž Je co když si to rozmyslíte, kdy pomocí programu, který chcete uložit více dat, než jste původně zamýšleli. 

Možná řešení je, tedy, napsat své programy tak, že používají více paměti než ve skutečnosti potřebují. Tímto způsobem si nejdeš narazit na tento problém, ale ty jsou nehospodárné. A čím více paměti váš program používá, jak jsme diskutovali včera, tím méně paměť, která je k dispozici pro jiné programy, tím dříve může být váš počítač zpomalit dolů, protože virtuální paměti. A tak ideálním řešením by mohlo být to, co? 

Under-přidělování zdá špatné. Over-Přidělení zdá špatné. Takže to, co by mohlo být lepším řešením? Přerozdělení. Být dynamičtější. Nenuťte si vybrat priori, na začátku, co chcete. A už vůbec ne více než přidělit, abyste nebyli nehospodárné. 

A tak k dosažení tohoto cíle jsme muset hodit tuto datovou strukturu, tak říkajíc, pryč. A tak to, co programátor se obvykle používají Je něco, co nazývá není array ale provázaný seznam. Jinými slovy, on nebo ona bude začít přemýšlet o jejich paměť jako bytí druh tvaru, který jim lze čerpat v následujícím způsobem. Pokud chci uložit jedno číslo program-- takže je to září, Dal jsem moji studenti kvíz; Chci ukládat první kvíz studentů, a dostali 100 na to-- I Chystám se zeptat můj počítač, prostřednictvím tohoto programu jsem napsáno, pro jeden kus paměti. A budu ukládat Číslo 100 v něm, a to je vše. 

Pak několik týdnů později když jsem si svůj druhý kvíz, a je čas psát V tomto 90%, jdu požádat počítač, hej, počítač, mohu mít jiný kus paměti? Bude to, aby mi to prázdný kus paměti. Chystám se dát do čísla 90, ale v mém programu nějakým způsobem other-- a nebudeme bát syntaxe pro tohle-- potřebuji nějak řetěz tyto věci dohromady. A já jim to řetěz spolu s co vypadá jako šíp zde. 

Třetí kvíz, který přijde, Chystám se říct, hej, počítač, dej mi ještě kus paměti. A já jdu dát dolů co to bylo, jako 75, a musím řetězci této teď spolu nějak. Čtvrtý kvíz přijde, a možná to je ke konci semestru. A tím bodem mého programu může být použití paměti všude, po celém fyzicky. A tak jen pro zábavu, jsem bude kreslit to tam quiz-- jsem zapomněl, jaké to bylo; já že možná 80 nebo something-- cesta sem. 

Ale to je v pořádku, protože obrazově Budu čerpat tento řádek. Jinými slovy, ve skutečnosti, v hardwaru počítače, První skóre mohlo skončit tady, protože je to hned na začátku semestru. Příští jeden by mohl skončit tady protože trochu času uplynulo a program stále běží. Dalším skóre, která byla 75, by mohl být tady. A poslední skóre mohlo být 80, což je tady. 

Takže ve skutečnosti fyzicky, by to mohlo být co paměti počítače vypadá. Ale to není užitečný mentální paradigma pro počítačový programátor. Proč by vám záleží, kde je Heck vaše data skončí? Chcete jen pro ukládání dat. 

To je něco jako naši diskusi dřívější čerpání krychle. Proč se staráš, co úhel je krychle a jak budete muset obrátit ji nakreslit? Chcete jen krychle. Stejně tak zde vás prostě chtějí stupně knize. Jen chcete myslet toto jako seznam čísel. Koho zajímá, jak je to realizovány v hardwaru? 

Takže teď abstrakce Je to obrázek zde. Jedná se o seznam spojena, as programátor by to nazval, pokud máte Seznam samozřejmě čísel. Ale je to spojeno obrazově pomocí těchto šipek, a všechny tyto šípy are-- vespod digestoř, pokud jste zvědaví, Připomínáme, že náš fyzický hardware má adresy nula, jedna, dva, tři, čtyři. Všechny tyto šípy jsou jako mapu nebo nasměrování, kde v případě 90 je-- nyní Musím počítat. 

Nula, jedna, dva, tři, čtyři, pět, šest, sedm. Vypadá to, že 90 je adresa paměti číslo sedm. Všechny tyto střely se jako malý kousek papíru že to dává pokyny k Program, který říká, že řídit tuto mapu se dostat na místo sedmé. A tam najdou Druhý kvíz skóre studenta. Mezitím, 75-- když jsem v tom pokračovat, To je sedm, osm, devět, 10, 11, 12, 13, 14, 15. 

Tento druhý šíp právě představuje mapy na paměťové místo 15. Ale opět, programátor obvykle dělá nestará o této úrovni detailu. A ve většině každém programování jazyka dnes, programátor ani nebude vědět, kde v paměti tato čísla ve skutečnosti jsou. Jediné, co nebo ona má se starat o je které jsou nějakým způsobem spojeny dohromady V datové struktury, jako je tato. 

Ale ukazuje se, není se dostat příliš technické. Ale jen proto, že můžeme snad dovolit mít tuto diskusi, Domníváme se, že jsme znovu Tento problém tady z pole. Uvidíme, jestli budeme litovat jít sem. To je 100, 90, 75, a 80. 

Dovolte mi, abych stručně, aby toto tvrzení. Toto je pole, a znovu, charakteristickým rysem matici je to, že všechna vaše data je zpět, aby zády k sobě v memory-- doslovně jeden byte nebo možná čtyři bajty, některé fixní počet bajtů pryč. V propojeném seznamu, který bychom mohli čerpat takhle, pod kapotou, který ví, kde ta věc je? To ani nemusí proudit takhle. Některé z těchto údajů může být zpět vlevo nahoře. Nemusíte ani vědět. 

A tak s řadou, máte Funkce známý jako náhodný přístup. A co s libovolným přístupem znamená, že počítač může skočit okamžitě na libovolné místo v poli. Proč? Vzhledem k tomu, že počítač ví že první poloha je nula, jedna, dvě, tři. 

A tak pokud chcete přejít z tento prvek k dalšímu prvku, doslova, v počítače mysl, stačí přidat jeden. Chcete-li jít do třetího prvku, stačí přidat one-- další prvek, jen přidat jeden. Nicméně, v této verzi příběhu, předpokládám počítač je v současné době hledá na nebo do činění s číslem 100. Jak se dostanete k dalšímu stupně v platové třídě knize? 

Musíte vzít sedm Kroky, které je libovolná. Chcete-li získat na ten příští, budete muset trvat dalších osm kroků se dostat do 15 let. Jinými slovy, to není konstantní mezeru mezi čísly, a tak to prostě bere Počítač více času je bod. Počítač má k hledání prostřednictvím paměti v pořadí najít to, co hledáte. 

Tak vzhledem k tomu, pole má tendenci být rychlá údaje structure-- kvůli tobě může doslova dělat jednoduchou aritmetiku a dostat tam, kam chcete, přidáním jednoho, Pro instance-- spojový seznam, obětujete tuto funkci. Nemůžete prostě jít od první na druhé až třetího na čtvrté místo. Budete muset následovat mapy. Budete muset vzít další kroky se dostat k těm hodnotám, které Zdá se, že přidání náklady. Takže budeme platit cenu, ale to, co bylo funkce, která Dan hledal tady? Co spojový seznam zřejmě nám umožňují dělat, který byl původ tento konkrétní příběh? 

Přesně. Dynamická velikost na to. Můžeme přidat do tohoto seznamu. Můžeme dokonce zmenšit seznamu, takže že jsme pouze pomocí tolik paměti jak vlastně chceme a tak nikdy nejsme over-přidělování. 

Teď už jen stačí být opravdu nit-vybíravý, tam je skrytá náklady. Takže byste neměli nechat mě přesvědčit jste, že je to přesvědčivý kompromis. Je tu další skryté náklady zde. Výhoda, aby bylo jasné, je to, že dostaneme dynamiku. Pokud chci další prvek, mohu jen nakreslit a vložit číslo tam. A pak jsem jej propojit s obrázkem tady, zatímco tady opět, jestli jsem maloval sám sebe do kouta, -li něco jiného již používá paměť tady, jsem smůlu. Já jsem namaloval sám sebe do kouta. 

Ale to, co je skryto stálo na tomto obrázku? Nejde jen o částku o čas potřebný jít odtud až sem, což je sedm kroků, pak osm stupňů, což je více než jedna. Jaký je další skryté náklady? Není to jen čas. Doplňující informace nezbytné pro dosažení tento obrázek. 

Jasně, že mapa, ty malé kousky papíru, jak jsem držet popisovat je jako. Jedná arrows-- ty nejsou zadarmo. Computer-- víte co je v počítači. To má nul a jedniček. Chcete-li reprezentovat šipky nebo A map nebo číslo, budete potřebovat nějakou paměť. Takže druhou cenu, kterou platit za propojeného seznamu obyčejná počítačová věda zdroj, je také prostor. 

A skutečně tak, tak často, Mezi kompromisů při navrhování softwarové inženýrství Systémy je čas a space-- jsou dvě z vašich složek, dva z vašich nejnákladnějších složek. To mě stojí víc času protože musím sledovat tuto mapu, ale je to také mi stojí více prostoru protože musím držet tuto mapu okolí. Takže naděje, jak jsme druh diskutovali více než včera a dnes je, že výhody převáží nad náklady. 

Ale není jasné řešení zde. Možná je to better-- a la rychlé a špinavé, jako Kareem navrženo earlier-- hodit paměti na problém. Stačí koupit více paměti, myslím, že méně hard o vyřešení problému, a řešit ji v jednodušším způsobem. A skutečně dříve, když jsme si povídali o kompromisy, to nebylo prostor v počítač a čas. Bylo na čase developer, který je dalším zdrojem. 

Takže znovu, je to balancování se snaží rozhodnout, která z těchto věcí jste ochotni utratit? Což je nejlevnější? Což vede k lepším výsledkům? To jo? 

Vskutku. V takovém případě, pokud jste reprezentující čísla v maps-- tito jsou voláni v mnoha jazycích "ukazovátka" nebo "adresa" - je to dvojnásobek prostor. Že nemusí být tak špatné, jak double-li Teď jsme jen ukládání čísel. Předpokládejme, že jsme byli ukládání záznamy o pacientech v hospital-- takže jména Pierson to, telefonní čísla, čísla sociálního pojištění, lékař dějiny. Tento box může být mnoho, mnohem větší, v kterémžto případě malinké ukazatel, adresa další element--, že to není velký problém. Je to takový třásně stálo na tom nezáleží. Ale v tomto případě, jo, je to dvojnásobek. Dobrá otázka. 

Pojďme se bavit o době, kdy trochu konkrétněji. Jaká je doba chodu vyhledávání tento seznam? Dejme tomu, že jsem chtěl hledat přes všechny stupně studentů, a je tu n tříd v této datové struktury. Také zde můžeme půjčit Slovník dříve. Jedná se o lineární struktura dat. 

Velký O n je to, co je zapotřebí, aby si na konci této datové struktury, whereas-- a my jsme neviděli Tento before-- pole vám dává čemu se říká časová konstanta, což znamená, jeden krok nebo dva kroky nebo 10 steps-- nezáleží. Je to pevně stanovený počet. To nemá nic společného s velikost pole. A důvod pro to, Znovu je náhodný přístup. Počítač může jen bezprostředně skočit na jiném místě, protože jsou všechny stejné vzdálenost od všeho ostatního. Neexistuje žádná myšlení zapojit. Dobře. Takže pokud mohu, dovolte mi, abych se snaží malovat dvě poslední fotky. Velmi častým jeden známý jako hash tabulky. Takže motivovat tuto diskusi, nech mě přemýšlet o tom, jak to udělat. 

Tak jak o tom? Předpokládejme, že problém Chceme-li řešit nyní realizuje v dictionary-- takže celá parta anglických slov nebo cokoliv jiného. A cílem je, aby bylo možné zodpovědět otázky formě je to slovo? Takže chcete implementovat kontrolu pravopisu, jen jako fyzická slovníku že se můžete podívat, co se v. Předpokládejme, že kdybych to s polem. Nemohl jsem to udělat. 

A předpokládám, že slova jsou jablka a banán a meloun. A já si nemyslím, že ovoce že začít s d, takže jsme jen bude mít tři plody. Takže to je pole, a my jsme skladování všechna tato slova v tomto slovníku jako pole. Otázkou tedy je, jak jinak mohl byste uložit tyto informace? 

No, já jsem trochu podvádění tady, protože každý z těchto písmen ve slově je opravdu individuální byte. Takže když jsem opravdu chtěl být nit-vybíravý, měl jsem opravdu Tento rozdelit do mnohem Menší kousky paměti, a my jsme mohli dělat přesně to. Ale budeme narážet na stejný problém jako předtím. Co když, jak Merriam Webster nebo Oxford dělá každý rok-- dodávají slova na dictionary-- my ne nutně chtějí malovat sami do rohu s polem? 

Takže místo toho, možná chytřejší přístup je dát jablko ve vlastním uzlu nebo box jak bychom říci, banán, a Pak zde máme ananasový meloun. A my string tyto věci dohromady. Tak tohle je pole, a To je provázaný seznam. Pokud se vám není úplně vidět, to prostě říká: "pole", a to říká, že "seznam." 

Takže máme stejný Přesné problémy jako dříve, kdy máme nyní dynamika našeho propojeného seznamu. Ale my máme poměrně pomalý slovník. Dejme tomu, že chci vyhledat slovo. To mi může trvat velký O n kroky, protože slovo by mohla se celou cestu na konci seznam, stejně jako melounu. A ukázalo se, že programování, třídění svatého grálu údajů struktury, je něco, že vám dává konstantní Čas jako matici ale přesto vám dává dynamiku. 

Takže můžeme mít to nejlepší z obou světů? A skutečně, je tu něco volal hash tabulky který vám umožní dělat přesně že, byť jen přibližně. Hash tabulka je milovník Datová struktura, která nám napadne jako Kombinace array-- a budu ji čerpat jako tohle-- a spojových seznamů že budu čerpat takhle tady. 

A to, jak ta věc Práce je následující. Pokud toto now-- hash table-- je můj třetí datová struktura, A chci uložit slov to, nemám chcete jen ukládat všechny Slova zády k sobě, aby zády k sobě. Chci využít některé kus informací o slovech, která vám umožní me dostat tam, kde je to rychlejší. 

Tak daný slova jablko a banán a meloun, Záměrně jsem zvolil ta slova. Proč? Co je to druh zásadně odlišný o tři? Co je jasné? Začínají s různými písmeny. 

Tak víte co? Spíše než dát všechny moje slova stejný vědro, tak říkajíc, stejně jako v jedné velké seznamu, proč ne I alespoň pokusit optimalizace a aby se mé seznamy 1/26 tak dlouho. Přesvědčivá optimalizace by mohl být důvod, proč ne Já-- při vkládání slovo do této datové struktury, do paměti počítače, proč Co kdybych sem dát všechny "A" slovo, všechna "b" slova zde, a všechny "C" slova tady? Takže tohle skončí uvedení jablko tady, banán tady, ananasový meloun tady, a tak dále. 

A pokud mám další Slovo jako--, co je další? Jablko, banán, hruška. Každý, kdo myslet na ovoce který začíná, B nebo C? Blueberry-- perfektní. Že se chystá skončit tady. A tak se zdá, že mají okrajově lepší řešení, protože teď, když chci hledat jablko, já first-- já ne jen ponořit do mé datové struktury. Nemyslím ponořit do paměti svého počítače. Poprvé jsem se podívat na první písmeno. 

A to je to, co počítačový vědec řekne. Vy hash do své datové struktury. Budete mít svůj vstup, který v Tento případ je slovo, jako jablko. Můžete analyzovat, při pohledu na První písmeno v tomto případě, tím ji hash. Hešování je obecný termín, kdy budete mít něco jako vstup a produkovat nějaký výstup. A výstup v tom, že Případ je umístění Chcete-li vyhledávat, první lokalita, druhé místo, třetí. Takže vstup je jablko, je výstup první. Vstup je banán se Výstup by měl být druhý. Vstup je ananasový meloun, výstup by měl být třetí. Vstup je borůvka se Výstup by měl být opět druhý. A to je to, co vám pomůže vzít zkratky přes svou paměť za účelem získání slovům nebo data efektivněji. 

Teď to snižuje svůj čas potenciálně jak hodně jako jedna z 26, protože pokud předpokládáme, že vás mít tolik "A" slova jako "z" Slova jako "q" slov, která ve skutečnosti není realistic-- budete mít překroutit napříč některá písmena alphabet-- ale to by přírůstkové Přístup, který má umožnit můžete se dostat do slov mnohem rychleji. A ve skutečnosti, sofistikovaná programu, Brýle na světě, Facebooks z world-- by použít hash tabulky pro mnoho různých účelů. Ale oni by neměla být tak naivní, jen podívat na první písmeno V jablko nebo banán nebo hruškovice nebo melounu, protože jak můžete vidět tyto seznamy by mohly ještě dostat dlouho. 

A tak by to mohlo být ještě sort z linear-- tak nějak pomalu, stejně jako s velkým O n které jsme diskutovali dříve. Takže, co je to opravdu dobrý hash tabulka do-- to bude mít mnohem větší pole. A bude používat mnohem sofistikované funkce zatřiďování takže to není jen podívat na "A". Možná to vypadá na "A-p-p-l-e" a nějak převádí těch pět písmen do místa, kde Apple by měl být uložen. My jen naivně pomocí písmeno "A" sám, protože je to pěkný a jednoduchý. 

Ale hash tabulka, ve konec, můžete myslet jako kombinace pole, přičemž každý z nich Má propojený seznam, který v ideálním případě by měla být co nejkratší. A to není samozřejmé řešení. Ve skutečnosti, hodně z jemného doladění , co se děje pod kapotou, když provádění těchto druhů sofistikované datové struktury je to, co je správné Délka pole? Jaká je správná hash funkce? Jak se vám uložení věcí do paměti? 

Ale uvědomuji, jak rychle tento druh diskuse stupňoval, a to buď tak daleko, že je to trochu of nad hlavou v tomto bodě, který je v pořádku. Ale my jsme začali, odvolání, se skutečně něco, co low-level a elektronické. A tak to zase je to Téma abstrakce, kde jakmile začnete brát za samozřejmost, OK, mám tu to-- fyzické paměti, OK, to mám každý fyzické umístění má adresu, OK, já to mám, můžu reprezentovat tyto adresy jsou arrows-- můžete velmi rychle začít mít sofistikovanější konverzace, které nakonec se zdá, že nám umožňuje řešit problémy, jako je vyhledávání a třídění efektivněji. A buďte ujištěni, too-- protože myslím, že to je nejhlubší jsme šli do některé z těchto témat CS proper-- my jsme provedeno v den a půl na to bod, co byste mohli dělat více než obvykle Průběh osm týdnů v semestru. 

Jakékoli otázky týkající se tito? Ne? Dobře. No, proč ne my pozastavit tam, spustit oběd několik minut dříve, pokračovat v jen asi hodinu? A budu prodlévat pro trochu otázkami. Pak budu muset jít trvat několik hovory pouze v případě, že je v pořádku. Budu zapnout nějakou hudbu do té doby, ale oběd by měl být za rohem.