DAVID Malan: Dobre. Sme späť. Takže v tomto segmente o programovaní, čo Myslel som, že by sme urobiť, je mix vecí. Po prvé, urobiť trochu niečoho hands-on, hoci s použitím hravejší programovanie environment-- ten, ktorý je demonštratívny presne tie druhy nápadov sme hovorili o, ale trochu viac formálne. Po druhé, pozrite sa na niektoré z čím viac technických spôsobov že programátor by skutočne riešiť Problémy, ako je vyhľadávanie problému že sme sa zaoberali skôr a tiež viac zásadne zaujímavý problém triedenia. 

Len sme predpokladali, od dostať ísť že telefónny zoznam bol triedený, ale to samo o sebe je vlastne niečo ako ťažký problém s mnohými rôznymi spôsobmi to vyriešiť. Takže budeme používať tieto ako trieda problémov Zástupca vecí, ktoré by mohol byť vyriešený všeobecne. A potom si pohovoríme asi v nejakom detaile, čo sa nazývajú dát structures-- milovník spôsoby, ako spojových zoznamov a hashovacie tabuľky a stromy, ktoré programátor by vlastne použitie a všeobecne používajú Na tabuli maľovať obrázok o tom, čo on alebo ona predpokladá pre vykonávanie niektoré kus softvéru. 

Takže poďme robiť hands-na prvej časti. Takže len dostať svoje špinavé ruky s Prostredie tzv scratch.mit.edu. Ide o nástroj, ktorý používame v našej triede vysokoškoláka. Aj napriek tomu, že je navrhnutý pre deti od 12 a hore, budeme používať ho pre hore Súčasťou tohto docela dost pretože je to pekné, zábavné grafický spôsob učenia niečo málo o programovaní. Takže zamieriť do tejto adresy URL, kde vás Mali by ste vidieť stránku presne takto, a pokračujte a kliknite Pridajte sa k poškriabaniu v pravom hornom rohu a vybrať si užívateľské meno a heslom a nakoniec si sami account-- scratch.mit.edu. Myslel som, že použiť ako Príležitosť prvý to ukázať. Otázka prišiel počas prestávky o tom, čo vlastne kód vyzerá. A my sme sa rozprávali počas prestávky o C, v particular-- obzvlášť Nižšia úroveň v staršom jazykom. A ja som práve urobil rýchly Google hľadanie nájsť C kód pre binárne vyhľadávanie, algoritmus, ktorý sme použité k hľadanie tohto telefónneho zoznamu skôr. Tento konkrétny príklad, samozrejme, nevyhľadáva telefónny zoznam. Je to len hľadá veľa Čísla v pamäti počítača. Ale ak by ste chceli len dostať vizuálne o tom, čo skutočné programovanie jazyk vyzerá, že vyzerá trochu niečo také. Takže je to asi 20-plus, Približne 30 riadkov kódu, ale rozhovor sme viedli cez prestávku Bol o tom, ako to vlastne dostane premenil núl a jednotiek a môžete nielen vrátiť v prípade, že spracovávať a ísť z núl a jednotiek späť ku kódu. 

Bohužiaľ, tento proces Je tak transformačné že je to oveľa ľahšie povie, ako urobí. Išiel som dopredu a v skutočnosti sa obrátil tento program, binárne vyhľadávanie, do núl a jednotiek formou program s názvom kompilátora, že som stalo sa, že tu práve na mojom počítači Mac. A keď sa pozriete na obrazovke Tu, najmä s dôrazom Na týchto stredných šesť stĺpcov iba uvidíte iba núl a jednotiek. A to sú tie nuly a tie, ktoré skladať presne ten vyhľadávací program. 

A tak každý kus z piatich bitov, každý bajt núl a jednotiek tu, reprezentujú nejakú inštrukciu typicky vnútri počítača. A v skutočnosti, ak ste počuli marketing slogan "Intel inside" - to, Samozrejme, jednoducho znamená, že máte Intel CPU alebo mozgu vnútri počítača. A čo to znamená byť CPU že máte inštrukčnú sadu, tak povediac. 

Každý procesor na svete, mnohí je vyrobený firmou Intel v týchto dňoch, chápe konečný počet inštrukcií. A tieto pokyny sú tak nízkej úrovni ako doplnok týchto dvoch čísel dohromady, násobiť týchto dvoch čísel dohromady, presunúť tento kúsok dát odtiaľ tu v pamäti uložiť toto Informácie odtiaľ do tu v pamäti, a tak forth-- tak veľmi, veľmi low-level, takmer elektronické detaily. But s tými, matematický operácie spojené s tým, čo sme diskutovali skôr, reprezentácie dát ako núl a jednotiek, môže si vybudovať všetko že počítač môže urobiť dnes, či už je to textové, grafické, hudobné, alebo inak. 

Takže je to veľmi ľahké sa dostať stratil v buriny rýchlo. A je tu veľa syntaktické výzvy pričom keď urobíte najjednoduchšie, najhlúpejší preklepov nikto z programu bude fungovať vôbec. A tak namiesto použitia jazyk C dnes ráno, Myslel som si, že by bolo zábavnejšie vlastne robiť niečo viac vizuálne, čo zatiaľ čo určený pre deti je vlastne ideálna prejav o skutočnom programovaní language-- len sa stane použiť obrázky namiesto textu reprezentovať týchto myšlienok. 

Takže až budete naozaj mať Účet na scratch.mit.edu, kliknite na tlačidlo Vytvoriť V ľavom hornom rohu stránky. A mali by ste vidieť prostredie, ako je ten, že som asi vidieť na mojej obrazovke tu. A budeme tráviť len trochu Trochu času hraním tu. Uvidíme, či sa nám podarí nie všetci riešiť niektoré Problémy spolu v nasledujúcom spôsobom. 

Takže to, čo uvidíte v tejto environment-- a vlastne len nechať me pauzy. Je niekto nie tu? Nie tu? OK. Takže mi dovoľte zdôrazniť niekoľko Charakteristiky tohto prostredia. 

Takže v ľavom hornom rohu obrazovky, my majú štádium Scratch je, aby som tak povedal. Scratch nie je len názov tohto programovacieho jazyka; je to tiež meno mačky, ktorá vidíte v predvolenom nastavení tam v oranžovej farbe. Že je na javisku, tak rovnako ako som popísal korytnačka skôr ako v obdĺžniková biela tabuľa prostredia. Táto mačka svet je obmedzená výhradne v tomto obdĺžniku do vrcholu. 

Medzitým sa na pravej strane strane tu, je to len skripty priestor, nepopísaný list ak chcete. To je miesto, kde budeme písať naše programy za chvíľu. A stavebné kamene, ktoré budeme použiť na napísanie tejto program-- puzzle kusy, ak ste will-- sú ty tu v stredu, a oni sú rozdelené do kategórií funkčnosťou. Tak napríklad, budem pokračovať a ukazujú, aspoň jeden z nich. Chystám sa ísť dopredu a kliknite kategórie Control hore vrchole. 

Tak to sú kategórie hore vrchole. Idem kliknúť na kategóriu konania. Skôr idem kliknúť na udalosti kategórie, prvý jedno až hore. A ak by ste chceli sledovať spolu dokonca ako to urobíme, ste celkom vítaní. Idem kliknúť a pretiahnuť Prvý z nich, "keď zelená vlajka kliknutí." A potom budem ju neupustili len zhruba v hornej časti svojich prázdnych bridlíc. 

A čo je pekné o Scratch je, že tento skladačky, keď spojený s iným puzzle kusov, sa chystá urobiť doslova čo tieto kúsky skladačky povedať robiť. Tak napríklad, Scratch je správne sa v polovici jeho sveta. Chystám sa ísť dopredu a vybrať Teraz, povedzme, kategórie Motion, ak by ste chceli, aby urobili same-- kategórii Motion. A teraz si všimnúť mám celok banda skladačky tu že opäť trochu robiť to, čo hovoria. A ja idem ďalej a pretiahnuť drop Presun bloku tamto. 

A všimnite si, že akonáhle sa dostanete v blízkosti spodnej časti "zelenou vlajkou kliknutí "tlačidlo, vývesné ako sa objaví biela čiara, ako keby to je takmer magnetické, že tam chce ísť. Len nech idú, a to bude snap dohromady a tvary budú odpovedať. A teraz môžete snáď takmer hádajte, kde ideme s tým. 

Ak sa pozriete vo fáze Scratch sem a pozerať sa na vrchole toho, uvidíte červené svetlo, je stopka a zelenú vlajku. A ja idem napred a sledovať moje screen-- na chvíľu, ak by ste mohli. Idem kliknúť na Zelená vlajka práve teraz, a prešiel čo sa zdá byť 10 krokov alebo 10 obrazových bodov, 10 bodov na obrazovke. 

A tak nie je tak vzrušujúce, ale dovoľte mi navrhnúť bez toho aby sa učia to, len s použitím vlastnej svoj vlastný intuition-- rokov ja navrhujem, aby vám zistiť, ako sa aby Scratch prechádzku hneď javiska. Už ho robiť cestu pre pravú stranu obrazovky, úplne napravo. Dám vám chvíľku alebo tak zápasiť s tým. Možno budete chcieť, aby sa pozreli u ostatných kategórií blokov. Dobre. Takže len zhrnúť, keď máme zelená vlajka sem klikol a presunúť 10 krokov je iba pokyn, zakaždým, keď som kliknite na zelenú vlajku, čo sa deje? No, to beží môj program. Takže som mohol urobiť Možno 10-krát ručne, ale to cíti trochu bit hackish, tak povediac, pričom Nie som vyriešenie problému. Ja som len ďalším pokusom a Znovu a znovu a znovu kým som tak nejako náhodou dosiahnuť smernicu že som vytýčených cieľov skôr. 

Ale vieme z našich pseudocode skôr, že je tu Tento pojem v programovaní zacykleniu, robiť niečo znovu a znovu. A tak som videl, že banda vás siahol po tom, čo skladačky? Opakujte, pokiaľ. Takže by sme mohli niečo urobiť ako opakujte, kým. A čo ste opakujte, kým presne? 

OK. A nechaj ma ísť s jedným, ktorý je trochu jednoduchšie len na okamih. Nechaj ma ísť dopredu a to urobiť. Všimnite si, že, ako môžete mať objavil pod kontrolou, je toto opakovanie blok, ktorý nevyzerá, že je to tak veľký. Nie je toho moc izby v hoteli medzi týmito dvoma žltou čiarou. Ale ako niektorí z vás môžu mať si všimol, ak ste drag and drop, Všimnite si, ako rastie na vyplnenie tvaru. 

A dokonca môžete napchať viac. Bude to len neustále rastú, ak preťahovanie a vznášať sa nad ním. A ja neviem, čo je Tu najlepšie, tak nech me aspoň opakuje päťkrát, pre inštancie, a potom sa vrátiť na javisko a kliknite na zelenú vlajku. A teraz si všimnúť, že to nie je úplne tam. 

Teraz niektorí z vás navrhol, as Victoria len to, opakujte 10 krát. A to zvyčajne robí dostať ho celú cestu, Ale nebolo tam byť odolnejšie spôsob, ako svojvoľne prísť na to, koľko ťahov urobiť? Čo by mohlo byť lepšie blok než opakovať 10-krát byť? 

Jo, tak prečo nie niečo navždy? A teraz mi dovoľte presunúť tento kúsok skladačky tam vnútri a zbaviť sa tejto jednej. Teraz všimnúť, bez ohľadu na miesto Scratch Spustí sa, chodí k okraju. A našťastie MIT, kto robí nuly, len zabezpečuje, že nikdy zmizne úplne. Vždy sa môžete chytiť svoj chvost. 

A práve intuitívne, prečo sa neustále v pohybe? Čo sa tu deje? Zdá sa, že sa zastavil, ale Potom keď som vyzdvihnúť a ťahajte Stále chce ísť tam. Prečo to tak je? Naozaj, je počítač doslova robiť to, čo ste to povedať robiť. Takže ak ste to povedal skôr robiť Nasledujúce vec navždy, presunúť 10 krokov, že to bude pokračovať a bude až som narazila na červenú stopku a zastavenie programu úplne. 

Takže aj keď nie to, ako by som mohol aby Scratch pohybovať rýchlejšie cez obrazovku? Ďalšie kroky, nie? Takže namiesto toho robil 10 v čase, prečo nie my choďte do toho a zmeniť ho to-- Čo by ste propose-- 50? Takže teraz idem kliknúť na zelenú vlajka, a naozaj, jede naozaj rýchlo. 

A to, samozrejme, je len prejavom animácie. Čo je animácia? Je to len vy zobrazujúci ľudskému celá rada statických snímok v skutočnosti, naozaj, ale naozaj rýchlo. A tak či sme len hovoriť ho presunúť viac krokov, my sme len mať vplyv malo byť Zmena kde je na obrazovke o to rýchlejšie za jednotku času. 

Teraz ďalšiu úlohu, ktorý som navrhol mal mať ho odraziť cez okraj. A bez toho aby vedel, čo puzzle kusy exist--, pretože to je v poriadku ak nechcete dostať do etapa challenge-- čo chceš robiť intuitívne? Ako by sme museli ho odrazí späť a ďalej, medzi ľavou a pravou? 

Jo. Takže potrebujeme nejaký druh o stave, a my Zdá sa, že podmieňovací, tak povediac, v kategórii Control. Ktorý z týchto blokov budeme chcieť? Jo, možno "if, then." Takže si všimnúť, že medzi žltými blokmi tu máme, je to "keby" alebo to "if, else" blok, ktorý bude nám umožňujú urobiť rozhodnutie, ako to dosiahnuť alebo to urobiť. A dokonca môžete vnoriť im robiť viac vecí. Alebo ak ste doteraz preč tu, pokračovať do kategórie snímania a-- uvidíme, či je to tu. 

Takže to, čo blok by mohlo byť užitočné tu zistiť, či je to z javiska? Jo, všimnite si, že niektoré z týchto blokov možno parametrizovať, aby som tak povedal. Môžu byť nejako prispôsobiť, nie Na rozdiel od HTML včera s atribútmi, ak tieto atribúty druh nastaviť správanie tagu. Rovnako tak tu, môžem uchopiť toto dojemné blok a zmeny a položiť otázku, ste dotýka myš Ukazovateľ ako kurzor alebo ste dotýkať okraja? 

Tak nechaj ma ísť dovnútra a urobiť. Idem pre oddialenie na chvíľu. Nechaj ma uchopiť tento kúsok skladačky Tu tento skladačky to, a budem míchanice je až na chvíľu. Chystám sa pohybovať to, zmeniť na dotyku hrany, a ja idem do pohybu to urobiť. Takže tu sú niektoré ingrediencie. Myslím, že mám všetko, čo chcem. 

By niekto chcel navrhnúť, ako som možno pripojiť tieto možná zhora nadol na vyriešenie problému s Scratch pohyb sprava doľava doprava na zľava sprava doľava, pričom každý Doba len odrazil od steny? Čo chcem robiť? Ktoré blokujú by som mal pripojiť k internetu "Pri zelenou vlajkou kliknutí na prvom mieste"? 

OK, takže začnime s "navždy". Čo sa deje vo vnútri ďalej? Niekto iný. OK, pohybovať kroky. Dobre. Čo potom? Takže potom, ak. A všimnite si, aj keď to vyzerá obložené spolu pevne, to bude len rásť zaplniť. To bude len skočiť, kde to chcem. 

A čo mám dať medzi if a potom? Pravdepodobne ", ak sa dotknete hrany." A oznámenia, opäť, je to príliš veľká pre neho, ale porastie zaplniť. A potom zase 15 stupňov? Koľko stupňov? Jo, takže 180 bude točiť ma celú cestu okolo. Tak uvidíme, či mám toto právo. Nechaj ma oddialiť. 

Nechaj ma ťahať Scratch nahor. Takže on je trochu skreslený teraz, ale to je v poriadku. Ako môžem resetovať ho ľahko? Idem trochu podvádzať. Tak som pridať ďalšie blok, len aby bolo jasno. Chcem, aby bod o 90 stupňov doprava v predvolenom nastavení, tak som jednoducho ísť mu to povedať k tomu, že programovo. A tu to máme. Zdá sa, že to urobil. Je to trochu divné, pretože on išiel hore nohami. Hovorme, že chyby. To je chyba. Chyba je chyba v programe, A logická chyba, že som človek, urobil. Prečo sa deje hore nohami? Vedeli MIT mhouřit alebo som? 

Jo, myslím, že to nie je MIT chyba. Dali mi kúsok skladačky ktorý hovorí, že otočiť určitý počet stupňov. A na Victoria je návrh, Som otočil o 180 stupňov, čo je tá správna intuícia. Ale otočenie o 180 stupňov doslovne znamená otočenie o 180 stupňov, a to nie je naozaj čo chcem, zrejme. Vzhľadom k tomu, aspoň že je v Tento dvojrozmerný svet, takže sústruženie sa naozaj deje aby ho otočiť hore nohami. 

Asi chcem použiť to, čo blok Namiesto toho, podľa toho, čo vidíte tu? Ako môžeme tento problém vyriešiť? Jo, takže sme mohli poukázať v opačnom smere. A vlastne aj to je nebude stačiť, pretože môžeme len ťažko kód aby ukázal vľavo alebo vpravo. 

Vieš, čo by sme mohli robiť? Vyzerá to, že máme pohodlie blok tu. Keby som priblížiť, pozri niečo, čo sa nám páči tu? Takže to vyzerá, že MIT má abstrakcie postavená v roku tady. Tento blok sa zdá byť ekvivalentná na ktoré ostatní bloky, množné číslo? 

Tento jeden blok sa zdá byť ekvivalentná k celej tejto trojice blokov že tu máme. Tak to dopadá môžem zjednodušiť môj Program zbavíme to všetko a len dať to tu. A teraz je ešte trochu buggy, a to je v poriadku pre túto chvíľu. Necháme to byť. Ale môj program je dokonca jednoduchšie, a to taky, by byť reprezentatívne si za cieľ v programming-- je v ideálnom prípade vytvoriť svoj kód ako jednoduché, kompaktné, ako je to možné, a pritom stále as čitateľné ako je to možné. Nechcete, aby to tak pregnantne že je ťažké pochopiť. 

Nevšimnúť som nahradil tri bloky s jedným, a to je pravdepodobne dobrá vec. Ja som abstrahovať preč pojmu kontroly, či ste na hrane len jeden blok. Teraz môžeme baviť s tým, v skutočnosti. To nepridá toľko intelektuálne hodnotu, ale hravý hodnotu. Chystám sa pokračovať a chytiť tento zvuk tu. Tak nechaj ma ísť dopredu, a dovoľte mi, aby som program zastaviť na chvíľu. Chystám sa zaznamenať nasledujúce, umožňujúci prístup k môjmu mikrofónu. 

Ideme na to. Ouch. Skúsme to znovu. Ideme na to. OK, zaznamenal som zlú vec. Ideme na to. Ouch. Ouch. Dobre. Teraz potrebujem sa zbaviť toho. Dobre. 

Takže teraz mám nahrávka len "Au." Takže teraz idem vpred a nazývať "Au." Chystám sa vrátiť mojich skriptov, a teraz Oznámenie, že je to blok, ktorý sa nazýva prehrať zvuk "mňau" alebo prehrať zvuk "Au." Chystám sa pretiahnuť, a kde Mal by som dať to na komický efekt? Jo, takže teraz je to trochu buggy, pretože teraz to block-- Všimnite si, ako toto "-Li na hrane, odraz "je tak trochu sebestačný. Tak som potrebné to napraviť. Nechaj ma ísť dopredu a to urobiť. Dovoľte mi, aby som sa zbaviť tohto a vrátiť k našej pôvodnej, viac úmyselné funkčnosť. Takže ", ak sa dotknete hrany, potom" Chcem otočiť, ako Victoria navrhnuté, 180 stupňov. A nechcem hrať zvuk "Au" tam? 

Jo, všimnite si, že je to vonku že žltý blok. Takže aj to, by bolo bug, ale všimol som si to. Takže budem pretiahnite ju tu, a upozornenie teraz je to vo vnútri "ak". Takže "ak" je tento druh podobnú ramenom ako škvrna že to bude len to, čo je vnútri nej. Takže teraz, keď som oddialiť na riziko annoying-- 

COMPUTER: Au, Au, Au. 

DAVID Malan: A bude len pokračovať donekonečna. Teraz už len stačí na urýchlenie veci tu, nechaj ma ísť dopredu a otvoriť, poďme say-- nechaj ma ísť k niektorým zo svojej vlastnej veci z triedy. A dovoľte mi otvoriť, povedzme, toto jedna zo strany jedného z našich výukových kolegami pred pár rokmi. Takže niektorí z vás možno pamätáte Táto hra z dávnych čias, a je to skutočne pozoruhodné. Aj napriek tomu, že sme hotová Najjednoduchšie programov práve teraz, uvažujme, čo to v skutočnosti vyzerá. Nechaj ma zasiahla hru. 

Takže v tejto hre, máme žaba, a pomocou šípky keys-- berie väčšie kroky, ako som remember-- Mám kontrolu nad touto žabou. A cieľom je dostať sa cez rušný Cesta bez spustenia do auta. A poďme see-- keď pôjdem sem, ja musieť počkať na protokol k posúvať. To sa cíti ako chrobák. To je druh chyby. Dobre. Som na to tu, tam, a potom budete mať ísť, až sa dostanete všetko žaby na ľalie podložky. Teraz to môže vyzerať o to zložitejšie, ale poďme skúsiť zlomiť toto dole psychicky a slovne na jednotlivé bloky. Takže je to asi logická kus, ktorý sme ešte nevideli ale to reaguje na úderov, k veciam som narazila na klávesnici. 

Takže je to asi nejaká blok, ktorý hovorí, ak je kľúč rovná up, potom urobiť niečo s Scratch-- Možno ju presunúť 10 krokov týmto spôsobom. Ak je stlačené klávesy pohybovať 10 krokov Týmto spôsobom, alebo vľavo kľúč, presunúť 10 krokov Týmto spôsobom desať krokov, ktoré. Ja som jasne ukázalo mačku v žabu. Tak to je len, kedy kostým, ako Scratch hovory to-- we práve importovali obraz žaby. 

Ale čo iného sa deje? Aké ďalšie riadky kódu, čo skladačky urobil Blake, náš kolega učenia, použiť v tomto programe, podľa všetkého? Čo sa robiť všetko move-- čo programovací postaviť? 

Motion, takže sure-- presunúť blok, pre istotu. A čo je to pohyb blok vnútri, s najväčšou pravdepodobnosťou? Jo, nejaký druh slučky, možno navždy zablokovať, možno opakovanie block-- opakujte, kým bloku. A to je to, čo robiť protokoly a Lily podložky a všetko ostatné ťah sem a tam. Je to proste deje donekonečna. 

Prečo sú niektoré vozidlá pohybujúce sa rýchlejšie ako ostatné? Aký je rozdiel o týchto programoch? Jo, pravdepodobne niektoré z nich užívate viac krokov naraz a niektoré z nich menej krokov naraz. A vizuálny efekt je veľmi pomalý proti. 

Čo myslíš, že sa stalo? Keď som dostal žabu celú cestu cez ulicu a rieku na ľalie pad, niečo pozoruhodný stalo. Čo sa stalo, hneď ako som to urobil? To sa zastavil. Že žaba sa zastavil, a Dostal som druhú žaba. Takže to, čo musí byť konštrukt používaný tam, aké funkcie? 

Jo, takže tam je nejaký druh "Keby" podmieňujú tam hore, taky. A ukázalo sa out-- sme nevideli tohle-- ale je tu ďalšie bloky v tam, že Dá sa povedať, ak ste dojemné Ďalšia vec, na obrazovke, ak ste sa dotýka ľalie pad "a potom". A potom je to, keď sme aby sa druhá žaba objaví. Takže aj keď táto hra je určite veľmi starý, aj keď na prvý pohľad tam je toľko deje on-- a Blake ani bič to v dvoch minút, to asi trvalo mu niekoľko hodiny vytvoriť túto hru založený na jeho pamäti alebo videa verzia dávnych čias je to. Ale všetky tieto maličkostí deje na obrazovke v izolácii redukuje na tieto veľmi jednoduché constructs-- pohyby alebo vyhlásenia ako sme diskutovali, slučiek a podmienky, a to je o tom. Je tu niekoľko ďalších milovník rysy. Niektoré z nich sú čisto estetické alebo akustické, ako zvuky Len som hral. Ale z väčšej časti, budete majú v tomto jazyku, škrabanie, všetky základné stavebné kamene, ktoré vás majú v C, Java, JavaScript, PHP, Ruby, Python, a akýkoľvek počet ďalších jazykov. Akékoľvek otázky ohľadom začiatku? Dobre. Takže nebudeme ponoriť hlbšie do nuly, keď ste zač tento víkend, najmä ak máte deti alebo netere a synovci a také, uviesť ich do nuly. Je to vlastne úžasne hravé Prostredie sa, ako jeho autori hovoria, veľmi vysoké stropy. Aj keď sme začali s práve detaily low-level, môžete naozaj dosť s ním, a to je možno ukážka presne to. 

Ale poďme teraz prejsť na niečo viac sofistikované problémy, ak chcete, známy ako "vyhľadávanie" a "Triedenie," všeobecnejšie. Mali sme tento telefónny zoznam tu earlier-- je ešte jeden len pre discussion-- že sme boli schopní vyhľadávať efektívnejšie, pretože významného predpokladu. A len preto, aby bolo jasno, aké predpoklad bol som robiť Pri vyhľadávaní prostredníctvom tohto telefónneho zoznamu? Že Mike Smith bol v telefónneho zoznamu, aj keď som by mal byť schopný zvládnuť Scenár bez neho tam, ak som sa predčasne ukončená. Kniha je abecedný. A to je veľmi veľkorysý predpoklad, pretože znamená someone-- Som typ rezanie za roh, ako ja rýchlejšie, pretože niekým iný urobil veľa tvrdej práce pre mňa. 

Ale čo keď je telefón Kniha bola nevytriedené? Možno, že Verizon dostal lenivý, práve hodil Mená všetkých a čísla tam Možno v poradí, v akom prihlásili k telefónnej služby. A koľko času zaberie mi nájsť niekoho, ako je Mike Smith? 1000 strana telefónu book-- koľko Stránky musím pozrieť? 

Všetky. Vy ste nejako smolu. Doslova sa pozrieť na každý strana v prípade, že telefónny zoznam je len náhodne triediť. Možno budete mať šťastie a nájsť Mika na prvej stránke, pretože on bol prvý zákazník objednať telefónne služby. Ale on by mohol byť posledný, taky. 

Takže náhodnom poradí nie je dobré. Takže predpokladám, že musíme zoradíte telefónnom zozname alebo v súhrnnom triedenie dát že nám bola daná. Ako môžeme urobiť? 

No, dovoľte mi pokúsiť jednoduchý príklad tu. Nechaj ma ísť dopredu a hodiť Niekoľko čísel na palube. Predpokladajme, že čísla, ktoré máme, sú povedzme, štyri, dva, jedna a tri. A Ben, triedenie týchto čísel pre nás. 

OK, dobre. Ako si to spravil? Dobre. Takže začať s najmenšou a najvyššou, a to je naozaj dobrá intuícia. A uvedomiť si, že sme ľudia sú vlastne celkom dobrý v riešení problémov ako je tento, minimálne pri dáta je relatívne malý. Akonáhle sa začnete mať stovky čísel, tisíce čísel, milióny čísel, Ben pravdepodobne Nemohol to celkom tak rýchlo, za predpokladu, že existujú medzery v číslach. Celkom ľahko spočítať na milión V opačnom prípade iba časovo náročné. 

Takže to vyzerá algoritmus ako Ben používa práve teraz Bol hľadať pre najmenšie číslo. Takže aj keď my ľudia môžu mať v mnohých informácií vizuálne, počítač je v skutočnosti trochu obmedzenejšie. Počítač môže len pozrieme na jeden bajt naraz alebo možno štyri byty na prvý time-- v týchto dňoch možno 8 bytov na jeden time-- ale veľmi malý počet bytov v danom čase. 

Takže vzhľadom na to, že skutočne máme štyri oddelené hodnoty here-- a môžete si myslieť, že majú Ben klapky na keby bol počítač ako že nevidí nič iné, ako jedno číslo pri time-- takže sme sa všeobecne bude predpokladať, rovnako ako v Angličtina, budeme čítať sprava doľava. Takže prvé číslo Ben asi vyzeral v Boli štyri a potom sa veľmi rýchlo si uvedomil, že je to dosť veľký number-- nechaj ma hľadať ďalej. 

Je tu dva. Počkaj minútu. Dva je menšia ako štyri. Idem si spomenúť. Dva je teraz najmenší. Teraz one-- je to ešte lepšie. To je ešte menšia. Idem na to zabudnúť dva a stačí spomenúť si ho. 

A mohol prestať hľadať? No, mohol based Na základe týchto informácií, ale už tak vyhľadávanie zvyšok zoznamu. Vzhľadom k tomu, čo keď nulu boli v zozname? Čo keď negatívne niektorý z nich v zozname? On len vie, že jeho odpoveď je správna, ak je to vyčerpávajúcim spôsobom kontroluje celý zoznam. Takže sa pozrieme na zvyšok tohto. Three-- to bolo plytvanie časom. Mám smolu, ale bol som Stále správne, aby tak urobili. A tak teraz podľa všetkého zvolili najmenší počet a len dať to na začiatku zoznamu, ako budem robiť. A teraz, čo si robil ďalej, hoci ste si nemyslel, že o ňom takmer v tomto rozsahu? Opakujte proces, takže nejaký druh slučky. K dispozícii je známy nápad. Tak tu sú štyri. To je v súčasnej dobe najmenší. To je kandidátom. Už nie. Teraz som videl dva. To je ďalší najmenší prvok. Three-- to nie je menšie, takže Teraz Ben môže vyklovnout dva. 

A teraz sme proces opakovať, a Samozrejme tri dostane vytiahol ďalšie. Tento postup opakujte. Štyri dostane vytiahol. A teraz sme z čísel, Preto musí byť zoznam triedi. 

A skutočne sa jedná o formálne algoritmus. Počítačový vedec by nazývajú "Voľba druhu" bytia nápadu triedenie A znova vypísať iteratively-- a znova a znova zvolením najmenšie číslo. A čo je príjemné na tom je, je to proste tak sakramentsky intuitívne. Je to tak jednoduché. A môžete opakovať rovnaký znovu a znovu prevádzku. Je to jednoduché. 

V tomto prípade išlo rýchlo, ale ako dlho to vlastne trvá? Povedzme, aby sa mohlo zdať, a cítiť trochu únavné. Tak jeden, dva, tri, štyri, päť šesť, sedem, osem, deväť, 10, 11, 12, 13, 14, 15, 16-- ľubovoľný počet. Len som chcel viac to Doba než len štyri. Takže ak mám jeden celok banda čísel to now-- ani jedno čo are-- Povedzme premýšľať o tom, čo to Algoritmus je naozaj. 

Predpokladajme, že existujú čísla tam. Opäť platí, že nezáleží na tom, aké sú, ale sú náhodné. Žiadam Benov algoritmus. Musím vyberte najmenšie číslo. Čo robím? A budem fyzicky robiť to tentoraz konať to. Pri pohľade, hľadáte, hľadáte looking. Až v čase, keď som sa dostať do koniec zoznamu môže Uvedomujem si najmenší číslo bolo dve tentoraz. Raz to nie je v zozname. Tak som si položil dva. 

Čo mám robiť ďalej? Looking looking. Teraz som našiel číslo sedem, pretože je tu medzery v týchto numbers-- ale len subjektívne. Dobre. Takže teraz môžem dať dole sedem. Pri pohľade hľadá, hľadá. 

Teraz som za predpokladu, ze Samozrejme, že Ben nemá extra RAM, extra pamäť, pretože, samozrejme, Pozerám sa rovnakým číslom. Určite som mohol pamätal Zo všetkých týchto čísel, a to je úplná pravda. Ale ak Ben pamätá všetky z čísel, že videl, on nie je naozaj urobil zásadný pokrok pretože už má schopnosť vyhľadávať cez čísla na palube. Spomienka na všetky Čísla nepomôže, pretože sa môže ešte ako počítač len sa pozrieť na, sme povedali, jedným číslom v tom čase. Takže nie je žiadny druh podvodu tam, ktoré môžete využiť. 

Takže v skutočnosti, ako som pokračovať v hľadaní v zozname, Doslova som si to len ďalej tam a späť cez to, olúpanie druhý najmenší počet. A ako si môžete odvodiť druh z mojich hlúpych pohybov, to jednoducho dostane veľmi únavné veľmi rýchlo, a ja sa zdajú byť vracať tam, tam a späť celkom dosť. Teraz aby sme boli spravodliví, nemám ísť zas až tak dobre, poďme see-- byť spravodlivý, Nemám chodiť docela ako rad krokov, každý čas. Vzhľadom k tomu, samozrejme, ako som výber čísel zo zoznamu, zostávajúce zoznam je čím ďalej kratšie. 

A tak sa poďme premýšľať o tom, koľko krokov som vlastne traipsing cez každý čas. V úplne prvej situácii sme mali 16 čísel, a tak maximally-- Nechal len to pre discussion-- Musel som sa pozerať až 16 Čísla nájsť najmenší. Ale akonáhle som vyloupíce najmenšie číslo, ako dlho bol zostávajúce zoznam, samozrejme? Len 15. Takže koľko čísel robil Ben alebo mám prehliadnuť druhýkrát okolo? 15, jednoducho ísť a nájsť najmenšie. Ale teraz, samozrejme, ktorých zoznam je, Tiež menšie, než tomu bolo predtým. Tak koľko krokov urobil ja musieť vziať nabudúce? 14 a potom 13 a potom 12 plus dot, bodka, bodka, kým som odišiel len s jedným. Takže teraz počítačový vedec by opýtať sa, dobre, čo robí, že si všetci rovní? Je to vlastne rovná niektorými konkrétnymi Číslo, ktoré by sme mohli iste robiť aritmeticky, ale chceme hovoriť o účinnosti algoritmov trochu viac formulaically, nezávisle na tom, ako dlho je zoznam. 

A tak viete čo? To je 16, ale ako som povedal predtým, poďme stačí zavolať na rozsah problému n, pričom n je nejaké číslo. Možno je to 16, možno je to tri, možno je to milión. Neviem. Nezaujíma ma. Čo naozaj chcem, je vzorec, ktorý môžem použiť na porovnanie tohto algoritmu s inými algoritmy že niekto môže tvrdiť, sú lepšie alebo horšie. 

Tak to dopadá, a to iba ja viem, že to od základnej školy, že to vlastne vyjde na rovnakej vec ako n cez n plus jedna cez dva. A to sa deje na rovné, z Samozrejme, že n a n na druhú cez dva. Takže keď som chcel vzorec za koľko krokov boli zapojení do pohľade na všetky of znovu a znovu týmito číslami a znova a znova, povedal by som, to n druhú a n cez dva. Ale viete čo? To len vyzerá chaotický. Ja len naozaj chcieť všeobecný zmysel vecí. A tie by mohli vyvolať z vysoká škola, ktorá tam je predstava najvyššieho rádu termíne. Ktorý z týchto podmienok, n štvorcový, N, alebo polovicu, má najväčší vplyv v priebehu času? Čím väčšia n dostane, čo z týchto záležitostí najviac? 

Inými slovami, ak sa pripojíte z milióna, n štvorcový bude s najväčšou pravdepodobnosťou dominantným faktorom, Vzhľadom k tomu, miliónkrát sama o sebe je oveľa väčšia ako plus jeden ďalší milión. Tak viete čo? Je to tak veľký zašiť číslo, ak námestí číslo. To naozaj nezáleží. Budeme len kríž, ktorý out a zabudnúť na to. A tak počítačový vedec by sa povedať, že účinnosť tohto algoritmu je v poriadku n squared-- Mám na mysli skutočne priblíženie. Je to akýsi zhruba n druhú. V priebehu doby, tým väčšia a väčšie n dostane toto Je to dobrý odhad pre to, čo efektivita alebo nedostatok účinnosti tohto algoritmu v skutočnosti je. A ja odvodiť, že, samozrejme, od skutočne robí matematiku. Ale teraz som len mávanie moje ruky, pretože som zrovna Chcete všeobecný zmysel tohto algoritmu. 

Takže pomocou rovnakého logiku, zatiaľ, uvažujme iný algoritmus už vyzeral at-- lineárne hľadanie. Keď som hľadal pre telefónne book-- Nie je ich triedenie, vyhľadávanie cez telefónne book-- sme stále hovorila, že to bolo 1000 kroky, alebo 500 krokov. Ale poďme generalizovať to. Ak existuje n stránok v telefónny zoznam, čo je doba chodu alebo Účinnosť lineárny hľadanie? Je to v poriadku koľko krokov k nájdeniu Mike Smith pomocou lineárne vyhľadávanie, Prvý algoritmus, alebo aj druhý? 

V najhoršom prípade, Mike je na konci knihy. Takže v prípade, že telefónny zoznam má 1000 stránok, sme si povedali minule, v najhoršom prípade, to môže trvať zhruba ako veľa stránok nájsť Miku? Rovnako ako 1,000. Je to horná hranica. Je to najhoršie možné situáciu. Ale opäť, ideme preč z čísel, ako je teraz 1000. Je to len n. 

Tak aký je logický záver? Nájdenie Mika v telefóne Kniha, ktorá má n strán môže trvať, v najhoršom prípade, koľko krokov v poriadku n? A naozaj počítačový vedec by sa povedať, že beží čas alebo sa výkonnosť alebo účinnosť alebo neúčinnosť, algoritmu, ako je lineárne vyhľadávanie v poriadku n. A môžeme aplikovať rovnaký Logika kríženie niečo ako som práve urobil do druhého Algoritmus sme mali s telefónnom zozname, kde sme urobili dve stránky naraz. 

Takže 1000 strana telefónny zoznam by mohol nás zavedie 500 otočených strán, plus jedna ak by sme zdvojnásobiť späť trochu. Takže ak telefónny zoznam má n strán, ale robíme dve stránky naraz, To je zhruba to, čo? N cez dva, takže to ako n cez dva. Ale ja som urobil nárokovať Pred okamihom, že n cez two-- to je druh rovnaké ako práve n. Je to len konštantný faktor, počítačoví odborníci by sa povedať. Poďme sa zamerať iba na premenné, really-- najväčšie premenné v rovnici. 

Takže lineárne vyhľadávanie, či urobil jednu Strana naraz alebo dve stránky naraz, je niečo v podstate rovnaké. Je to stále v poriadku n. Ale ja tvrdil s mojím obrázku skôr že tretí algoritmus nebol lineárne. Bolo to nie je priamka. Bolo to, že krivka, a algebraické rovnice nebolo čo? Log n- takže log základňu dva n. A nemusíme ísť do príliš veľa detailov na logaritmy dnes, ale väčšina počítačoví experti nechceli aj tí, čo je základňa. Vzhľadom k tomu, že je to všetko len konštantný faktory, tak povediac, Len drobné číselné rozdiely. A tak by to bolo veľmi časté spôsob, najmä formálnu počítače Vedci na palube alebo programátori na bielu tabuľu v skutočnosti tvrdí, ktoré Algoritmus by sa používať alebo to, čo je účinnosť z ich algoritmus. 

A to nie je nevyhnutne niečo diskutujete v každom detaile, ale dobrý programátor je ten, ktorý má pevnú, formálne pozadia. On je schopný hovoriť vám v tomto druhu cesty a vlastne robiť kvalitatívne argumenty ako prečo jeden algoritmus alebo jeden kus softvéru je lepšia ako nejakým spôsobom do druhého. Pretože tie by určite stačí spustiť program, jedného človeka a spočítať počet sekúnd trvá triediť nejaké čísla, a môžete spustiť niektoré Program iné osoby a počítanie sekúnd trvá. Ale to je všeobecnejší spôsob, môžete použiť na analýzu algoritmov, ak chcete, len na papiera alebo len slovne. Bez toho aby si beží to bez toho, dokonca sa snaží vzorové vstupmi, môžete len rozum cez neho. A tak s prenájmom vývojárov, alebo ak mať ho alebo ju nejako argumentovať pre vás prečo ich algoritmus, ich tajomstvo omáčka pre vyhľadávanie miliardy webových stránok pre vaše Firma je lepšie, títo sú druhy argumentov, že by v ideálnom prípade byť schopný vykonať. Alebo aspoň to sú druhy vecí ktoré by prísť v diskusii, pri aspoň vo veľmi formálne diskusie. Dobre. Takže Ben navrhovanej niečo volal výber triediť. Ale budem navrhovať, že je tu iné spôsoby, ako to urobiť taky. To, čo som nemal naozaj rád o Benovom algoritmu je to, že išiel ďalej, alebo čo ma chodiť sem a tam a sem a tam a sem a tam. Čo keď namiesto toho som mal robiť niečo podobné týchto čísel tu a ja sme boli len rokovať s každým číslo v poradí, ako som vzhľadom k tomu, že? 

Inými slovami, je tu môj zoznam čísel. Štyri, jedna, tri, dva. A ja budem robiť nasledujúce. Idem vložiť čísla kam patrí skôr Okrem výberu im jeden po druhom. Inými slovami, tu je číslo štyri. 

Tu je môj pôvodný zoznam. A budem zachovávať v podstate nový zoznam tu. Tak toto je starý zoznam. Jedná sa o nový zoznam. Vidím, že číslo štyri prvé. Môj nový zoznam je spočiatku prázdny, tak je to v prípade triviálne že štyri je teraz roztriedený zoznam. Ja beriem len to číslo som dal, a ja ho uvedenie vo svojom novom zozname. 

Je zoradený tento nový zoznam? Jo. Je to hlúpe, pretože tam je len jeden prvok, ale je to úplne triediť. Nie je nič na svojom mieste. Je to oveľa zaujímavejšie, tento algoritmus, keď som sa presunúť k ďalšiemu kroku. 

Teraz mám jeden. Tak jeden, samozrejme, patrí u začiatok alebo koniec tohto nového zoznamu? Začiatok. Takže musím urobiť nejakú prácu hneď. Bral som niektoré slobody s mojou značku jednoduchým kreslenie veci kde chcem im, ale v skutočnosti to nie je presný v počítači. Počítač, ako vieme, má RAM, alebo Random Access Memory, a to je jeden bajt a ďalšie byte a ďalšie byte. A ak máte gigabajt RAM, máte miliarde bajtov ale sú fyzicky na jednom mieste. Nemôžete len presunúť veci okolo tým, že ho na tabuľu kdekoľvek chceš. Takže ak môj nový zoznam musí Štyri miesta v pamäti, Bohužiaľ štyri je Už na zlom mieste. 

Takže vložiť číslo jedna Nemôžem len tak kresliť ho sem. Toto miesto v pamäti neexistuje. To by bolo podvádzanie, a bol som podvádzanie obrazovo po dobu niekoľkých minút tu. Takže naozaj, keď chcem dať jeden tu, Musím sa dočasne skopírovať štyri a potom dal ten tam. 

To je v poriadku, to je v poriadku, je to technicky možné, ale uvedomiť, že je to práca navyše. Nechcel som len dať číslo na svojom mieste. Najskôr som musel presunúť číslo, potom ju na mieste, tak nejako som zdvojnásobil svoj objem práce. Takže majte na pamäti, že. 

Ale ja som teraz urobil s týmto prvkom. Teraz chcem chytiť číslo tri. V prípade, samozrejme, to patrí? Medzi. Nemôžem podvádzať už a proste to tam dal, pretože, znovu, tejto pamäti je vo fyzických miestach. Takže mám skopírovať štyri a dal tri sem. Nie je to veľký problém. Je to len jeden krok navyše again-- cíti veľmi lacná. 

Ale teraz som sa presunúť na dva. Dva, samozrejme, patrí sem. Teraz môžete začať sledovať, ako Práca môže nahromadiť. A teraz, čo mám robiť? Jo, mám presunúť štyri, potom musím skopírovať tri, a teraz môžem vložiť dva. A úlovok s týmto algoritmus, je dosť zaujímavé, je, že predpokladám, že máme viac extrémne prípad, kedy je to povedzme, osem, sedem, šesť, päť, štyri, tri, dva, jedna. To je, v mnohých kontextoch, najhorší možný scenár, pretože zatratenou vec je doslova pospiatky. 

To nie je naozaj ovplyvní Benov algoritmus, pretože v Benovom výberu sort že to bude držať tam a späť cez zoznam. A pretože bol stále hľadá po celú zostávajúcu zoznamu to nevadí kde sú prvky. Ale v tomto prípade sa svojím vkladanie approach-- skúsme to. 

Tak jeden, dva, tri, štyri, päť, šesť, sedem, osem. Raz dva tri štyri, päť, šesť, sedem, osem. Chystám sa vziať osem, a kde mám dať? No, na začiatku môjho zoznamu pretože tento nový zoznam je zoradený. A ja ju prechádzajú von. 

Kam mám dať sedem? Látat to. Je potrebné ísť tam, tak Musím urobiť nejaké kopírovanie. A teraz sedem chodia sem. Teraz som sa presunúť na šesť. Teraz je to ešte viac práce. 

Osem musí ísť sem. Sedem musí ísť sem. Teraz je šesť môže ísť sem. Teraz som chytiť päť. Teraz osem musí ísť tu, sedem musí ísť sem, šesť musí ísť sem, a teraz päť a opakovať. A som celkom veľa pohybujúce sa to neustále. 

Takže na konci, to algorithm-- zmienime hovoriť vloženie sort-- vlastne Má veľa práce, taky. Je to proste iný druh práce, než Bena. Benov práca mala ma deje sem a tam po celú dobu, zvolenie budúci najmenší znovu a znovu element. Tak to bolo to veľmi vizuálne druh práce. 

Tento iný algoritmus, ktorý je ešte correct-- to dostane prácu done-- Len zmení množstvo práce. Vyzerá to, že spočiatku budete úsporu, pretože si zrovna rokovania s každým prvkom vpredu, bez šiel all cesta cez zozname ako Ben bol. Ale problém je, a to najmä v tých bláznivé prípady, keď je to všetko obrátene, si len trochu odkladá ťažkú ​​prácu kým nebudete mať na opravu chyby. 

A tak ak môžete si to predstaviť osem a sedem a šesť a päť a neskôr štyri a tri a dva pohybujúce sa ich cestu cez zoznamu sme práve zmenený druh práce robíme. Namiesto toho, ako to robí u počiatok mojej iteráciu Robím len to u Koniec každej iterácii. Tak to dopadá, že tento algoritmus, Tiež všeobecne nazývané triedenie priamym vkladaním, je tiež na objednávku n štvorcový. Je to vlastne o nič lepší, o nič lepšie vôbec. 

Avšak, tam je tretina prístup Bol by som nás povzbudiť, aby zvážila, ktorý je to. Takže predpokladám, že môj zoznam, pre jednoduchosť znovu, je štyri, jeden, tri, two-- len štyri čísla. Ben mal dobrú intuíciu, dobrý človek intuícia Pred tým, ktorú pevné celý Zoznam eventually-- triedenie priamym vkladaním. nám vyprosil som ďalej. Ale poďme zvážiť Najjednoduchší spôsob, ako opraviť tento zoznam. 

Tento zoznam nie je zoradená. Prečo? V angličtine, vysvetliť, prečo to nie je v skutočnosti triediť. Čo to znamená nebyť radené? 

STUDENT: To nie je sekvenčná. 

DAVID Malan: Nie je sekvenčná. Dajte mi príklad. 

STUDENT: Dajte je v poriadku. 

DAVID Malan: OK. Daj mi viac konkrétny príklad. 

STUDENT: vzostupnom poradí. DAVID Malan: Nie je vzostupne. Byť presnejší. Neviem, čo myslíš tým vzostupne. Čo je zle? 

STUDENT: Najmenší z Čísla nie je v prvom priestore. 

DAVID Malan: Najmenšie číslo je nie je v prvom priestore. Byť konkrétnejší. Začínam pochopiť. Počítame, ale čo je mimo prevádzky tu? 

STUDENT: číselné postupnosti. DAVID Malan: číselné postupnosti. druh vecí každého z chovu to here-- veľmi vysokú úroveň. Len mi doslova povedať, čo je zle ako päť rokov staré sile. 

STUDENT: Plus jeden. 

DAVID Malan: Čo je to? 

STUDENT: Plus jeden. 

DAVID Malan: Čo tým myslíš plus jedna? Daj mi iný päť-ročný. Čo sa deje, mami? Čo sa deje, ocko? Čo tým myslíš, to nie je radené? 

STUDENT: To nie je to správne miesto. 

DAVID Malan: Čo je nie je na správnom mieste? 

STUDENT: Štyri. DAVID Malan: OK, dobre. Takže štyri nie je tam, kde by mala byť. Najmä, je to pravda? Štyri a jeden, prvý dve čísla Aha. Je to správne? Nie, oni sú mimo prevádzky, nie? V skutočnosti, že teraz o počítači, taky. Môže sa iba na možno jeden, možno dve veci once-- a vlastne len jedna vec v čase, ale môže aspoň pozrieť sa na jednu vec, potom Ďalšia vec, ktorú hneď vedľa neho. 

Takže sú tieto v poriadku? Samozrejme, že nie. Tak viete čo? Prečo nie vezmeme dieťa Kroky upevňovacie tento problém namiesto toho, aby tieto fantázie algoritmy ako Ben, kde Je to vlastne trochu upevnenie ju slučky v zozname namiesto toho robiť to, čo som urobil, kde Aj tak nejako pripevnil ju, ako sme ísť? Povedzme doslova rozobrať Pojem order-- číselnom poradí, hovoriť čokoľvek want-- Do týchto párová porovnanie. 

Štyri a. Je to správne poradie? Takže poďme napraviť. Jeden a štyri, a potom budeme len skopírovať to. Dobre, dobre. Opravil som jeden a štyri. Tri a dve? Nie. Nech moje slová zodpovedala prsty. Štyri a tri? 

Nie je to v poriadku, takže idem robiť jeden, tri, štyri, dva. OK, dobre. Teraz štyri a dve? Musíme to opraviť taky. Tak jeden, tri, dva, štyri. Takže je to radené? Nie, ale je to bližšie do triedeného? 

Je to preto, že sme opravil toto chyba, sme opravili túto chybu, a my pevne túto chybu. Takže sme opravili tri chyby pravdepodobne. Stále nie je naozaj vyzerajú triedené, ale je objektívne bližšie do triedeného pretože sme pevne niektoré z týchto chýb. 

A teraz, čo mám robiť ďalej? Tak nejako som došiel na koniec zoznamu. Zdalo sa, že som fixné všetky chyby, ale nie. Vzhľadom k tomu v tomto prípade, niektoré čísla mohol bublala bližšie do iných čísel, ktoré sú stále mimo prevádzky. Takže poďme urobiť to znova, a budem Len to v mieste tentoraz. Jeden a tri? Je to fajn. Tri a dve? Samozrejme že nie, tak sa poďme zmeniť. Tak dva, tri. Tri a štyri? A teraz poďme byť len Zvlášť tu pedantská. Je to radené? Vy ľudia viem, že to triediť. 

Mal by som skúsiť znova. Takže Olivia navrhuje Aj skúste to znova. Prečo? Pretože počítač nemá luxus našich ľudských očí púheho pozrel back-- OK, som urobil. Ako sa počítač určí že zoznam je teraz radené? Mechanicky. 

Mal by som prejsť ešte raz, a to iba v prípade, I nerobia / nájsť žiadnu chybu môžem potom uzavrie ako počítač, jo, sme dobrí ísť. Aby jedna a dve, dve a tri, tri a štyri. Teraz môžem konečne povedať, že je triedené, pretože som nerobil žiadne zmeny. Teraz to bude chyba a len Ak by som hlúpy, počítač, spýtal sa tie isté otázky znovu očakával rôzne odpovede. By sa nemalo stať. 

A tak teraz je zoradený zoznam. Bohužiaľ, doba behu Tento algoritmus je tiež N druhú. Prečo? Pretože máte n čísel, a vo najhoršom prípade budete musieť presunúť n čísel n časy, pretože musíte ísť ďalej späť skontrolovať a prípadne opraviť tieto čísla. A môžeme urobiť viac formálna analýza, taky. 

Tak to je všetko, povedať, že sme si vziať tri rôzne prístupy, jeden z nich okamžite intuitívne off netopiera z Ben mojej navrhované vloženie radiť k tomuto kde ste druh strácať zo zreteľa les pre stromy spočiatku. Ale potom, keď idete o krok späť, voila, máme fixné triedenie predstavu. Takže toto je, trúfam tvrdiť, nižšiu úroveň snáď ako niektorí z tých, ostatné algoritmy, ale poďme uvidíme, či nemôžeme predstaviť Tieto prostredníctvom tohto. 

Takže to je nejaký pekný softvér, ktorý niekto napísal pomocou farebné pruhy, aby to robiť nasledujúce pre nás. Každý z týchto tyčí predstavuje číslo. Vyššia je stĺpec, tým väčšia číslo, menšie bar, čím menší je počet. Takže v ideálnom prípade chceme krásny pyramídu kde začína malý a dostane veľký, a to by znamenalo, že Tieto tyče sú radené. Takže ja idem dopredu a zvoliť, Napríklad, Benov algoritmus first-- výber triediť. 

A všimnite si, čo robí. Spôsob, akým ste sa rozhodli vizualizovať tento algoritmus je, že rovnako ako ja prechádzal mojom zozname, Tento program je chôdza prostredníctvom svojho zoznamu čísiel, zvýraznenie v ružovej každého Číslo že to pozerá. A čo sa stane teraz? 

Najmenšie číslo, ktoré I alebo Ben našiel náhle sa presunie na začiatok zoznamu. A všimnite si urobili vypudiť číslo, ktoré tam bol, a to je úplne v poriadku. Nedostal som sa do tejto úrovni detailu. Ale musíme dať toto číslo niekde, tak sme ho presťahovali do otvorené miesto, ktoré bolo vytvorené. Tak idem na urýchlenie tohto up, pretože inak sa stáva veľmi únavné rýchlo. Animácia speed-- tam ideme. Takže teraz Rovnaký princíp Bol som uplatňujú, ale vy môže začať cítiť algoritmus, ak sa vôle, alebo to vidieť trochu jasnejšie. A tento algoritmus má za následok výbere ďalšieho najmenší prvok, takže budete začať vidieť to rozbehnúť na ľavej strane. A na každej iterácii, ako som navrhuje, to robí trochu menej práce. Nemusí ísť celú cestu späť na ľavý koniec zoznamu, pretože už pozná tie sú radené. Takže to trochu pocit, ako by to zrýchľuje, aj keď každý krok je pričom rovnaké množstvo času. Je tu len menej krokov zostávajúce. A teraz sa môžete trochu cítiť Algoritmus vyčistenie jej koniec, a naozaj teraz je to triediť. 

Takže triedenie priamym vkladaním je všetko hotové. Musím znovu náhodne poľa. A všimnite si môžem len udržiavať randomizing to, a dostaneme aproximáciu rovnaký prístup, vloženie sort. Nechaj ma to spomaliť až sem. Začnime že v priebehu. Prestať. 

Poďme preskočiť štyri. Tam sme ísť. Náhodne oni poľa. A tu sme go-- triedenie priamym vkladaním. Hrať. Všimnite si, že to zaobchádzanie s jednotlivým prvok narazí hneď, ale v prípade, že patrí do zlé oznámenia miesta všetky práce, ktorá má diať. Musíme sa držať presúva viac a ďalšie prvky, aby sa vytvoril priestor Pre jedného chceme zaviesť. 

Takže sme sa zameraním na ľavý koniec jediného zoznamu. Všimnite si, sme ani my vyzeral at-- ešte zvýraznené v ružovej čokoľvek doprava. Práve sme sa zaoberajú problémy, ako sme ísť, ale my sme vytvoriť veľa pracovať pre seba stále. A tak ak by sme toto urýchliť Teraz ísť do dokončenia, má iný pocit na to naozaj. Je to len so zameraním na ľavom konci, ale robí trochu viac práce ako needed-- druh vyhladzovanie vecí cez, napravuješ, ale nakoniec zaoberajúce sa každý prvok jeden po druhom až sa dostaneme do dobre the--, my Všetci vieme, ako to skončí, takže je to trochu nezaujatý možná. 

Ale Zoznam v end-- spoiler-- sa bude triediť. Takže poďme sa pozrieť na jeden posledný. Nemôžeme len tak preskočiť teraz. Už tam skoro sme. Dva ísť, kto ísť. A voila. Výborne. 

Takže teraz poďme urobiť jednu posledný, re-randomizing s bublinou druhu. A všimnite si tu, zvlášť keď som ho spomaliť dole, to sa udržať znášať prejsť. Nevšimnúť to jednoducho robí po dvojiciach comparisons-- druh miestnych riešení. Ale akonáhle sa dostaneme do koniec zoznamu v ružovej, čo sa muselo stať znova? Jo, to bude musieť začať znovu, pretože to len Pevné párové chyby. A to by mohol odhaliť ešte ďalšie. A tak keď sa toto urýchliť, budete vidieť, že, rovnako ako názov napovedá, menšie elements-- alebo skôr, väčšie elements-- začínajú bublať až na vrchol, ak chcete. A menšie prvky sú začína bublať dole doľava. A vskutku, to je druh Vizuálny efekt rovnako. A tak to bude skončiť dokončovacie práce vo veľmi podobným spôsobom, taky. 

Nemáme na bývanie na tento konkrétny jeden. Dovoľ mi otvoriť to teraz taky. Je tu niekoľko ďalších triediace algoritmy vo svete, málo z nich Tu sú zachytené. A to najmä pre študentov, ktorí nie sú nutne vizuálny alebo matematické, ako tomu bolo predtým, môžeme Tiež to audially ak budeme spájať zvuk s tým. A len tak pre zábavu, tu je Niekoľko rôznych algoritmov, a jeden z nich, najmä ste bude všimnúť, sa nazýva "triedenie zlučovaním." 

Je to vlastne zásadne lepší algoritmus, tak, aby zlúčiť druh, jedným z tie sa chystáte vidieť, Nie je poriadok n druhú. Je to v poriadku n-krát logaritmu n, čo je v skutočnosti menší, a teda rýchlejšie ako ostatné tri. A je tu ďalší pár tie hlúpe, že uvidíme. 

Tak ideme na to s nejakým zvukom. To je triedenie priamym vkladaním, takže opäť je to len do činenia s prvkami ako prídu. To je bublina triediť, takže je to vzhľadom im párov naraz. A opäť najväčšími elementy vyviera až na vrchol. 

Ďalší na rade výber triediť. To je Benov algoritmus, kde Znovu on výberom iteratívne druhý najmenší prvok. A opäť, teraz si môžete skutočne počuť, že to urýchliť, ale len do tej miery, ako to robí menej a menej práca na každom opakovaní. To je rýchlejšie jedno, triedenie zlučovaním, ktorý je triedenie zhluky čísel dohromady a potom ich kombinovať. Takže look-- ľavý polovica už je zoradený. 

Teraz je to triedenie pravú polovicu, a Teraz to bude skombinovať do jedného. To je niečo, čo nazýva "Gnome sort." A môžete trochu vidieť, že to tam a späť, ktorým sa práca trochu tu a že pred tým, než pokračuje do novej práce. A to je všetko. Je tu iný druh, ktorý je naozaj len pre akademické účely, volal "hlúpy druh", ktorý berie vaše dáta, triedi to náhodne, a skontroluje, ak je zoradené. A ak to tak nie je, to re-triedi ho náhodne, skontroluje, či je to triedené, a ak nie, opakuje. A teoreticky, pravdepodobnostne Tým sa dokončí, ale po celkom dosť času. Nie je to najviac účinné algoritmov. Takže akékoľvek otázky týkajúce sa tých, Konkrétne algoritmy alebo čokoľvek vzťahujúce sa tam taky? 

Dobre, poďme teraz šprýmař oddelene čo všetko Tieto linky sú, že som bol kreslenie a to, čo som za predpokladu, že počítač môže robiť pod kapotou. Povedal by som, že všetky z týchto čísel Stále drawing-- oni potrebujú dostať uložené niekde v pamäti. Budeme sa zbaviť toho chlapa teraz taky. 

Takže kus v pamäti computer-- takže RAM DIMM je to, čo sme hľadali včera, dual inline memory module-- vyzerá takto. A každý z týchto malých čiernych čipov je nejaký počet bajtov, typicky. A potom zlaté kolíky sú rovnako ako drôty, ktoré ju pripojiť k počítaču, a zelený kremík doska je jednoducho čo drží všetko pohromade. Takže čo to vlastne znamená? Keby som druh nakresliť rovnaký obrázok, Predpokladajme pre jednoduchosť že tento DIMM, dual inline pamäťový modul, Je jedno GB pamäte RAM, jeden gigabajt pamäť, ktorá je, koľko bytov celkom? Jeden gigabajt je to, koľko bytov? Viac ako. 1124 je kíl, 1000. Mega je milión. Giga je miliarda. 

Klamem? Môžeme dokonca čítať etiketu? To je vlastne 128 GB, takže je to viac. Ale budeme predstierať, že toto Je len jeden gigabajt. Takže to znamená, že je o miliardu bajtov pamäte k dispozícii pre mňa alebo 8 miliárd bitov, ale ideme hovoriť, pokiaľ ide o bytoch teraz, hýbať sa vpred. 

Takže to, čo to znamená, že je to jeden bajt, je to ďalší bajt, Ide o ďalší bajt, a keby sme naozaj chceli byť konkrétny budeme musieť čerpať miliardu malé štvorce. Ale čo to znamená? No, dovoľte mi zoom na tomto obrázku. Ak mám niečo, čo vyzerá ako je to teraz, to je štyri bajty. 

A tak som mohol dať štyri čísla tu. Raz dva tri štyri. Alebo by som mohol dať štyri písmená alebo symboly. "Hej!" môže ísť priamo tam, pretože každý z listov, sme diskutovali skôr, by mohol byť zastúpený s ôsmimi bitov alebo ASCII alebo byte. Takže inými slovami, môžete dať 8 miliárd veci vo vnútri táto jedna palica pamäte. A teraz čo to znamená dať veci späť sa chrbtom v pamäti takto? To je to, čo programátor by sa nazvať "pole." V počítačovom programe, si nemyslím, že o hardvérom, samy o sebe. Ty jednoducho myslieť na seba ako vlastnenie Prístup k celkovo o miliarde bajtov a môžete čo chcete s ním. Ale pre pohodlie je všeobecne užitočné aby sa vaša pamäť právo vedľa seba, ako to. Takže keď som sa priblížiť na tohle-- pretože my rozhodne nebudeme čerpať miliardy trochu squares-- Dajme tomu, že táto doska predstavuje že palicu pamäti hneď. A ja budem len čerpať toľko ako my Značka skončí mi dáva sem. Takže teraz máme palicu pamäte na doske ktorý má jeden, dva, tri, štyri, päť, šesť, jeden, dva, tri, štyri, päť, šesť, siedmej takže 42 bajtov pamäť na celkovú obrazovky. Ďakujem. Áno, urobil môj aritmetický pravdu. tu tak 42 bajtov pamäte. Takže čo to vlastne znamená? No, počítačový programátor by v skutočnosti všeobecne myslíte o tejto pamäti ako adresovať. Inými slovami, každý z nich umiestnenia v pamäti, v hardvéru, má jedinečnú adresu. 

Nie je to tak zložité, ako jeden Brattle Square, Cambridge, Mass., 02138. Namiesto toho, je to len číslo. To je byte číslo nula, to je jeden, to je dve, to je tri, a to je 41. Počkaj minútu. Myslel som, že som povedal 42 pred chvíľou. Začal som počítať od nuly, takže je vlastne správne. Teraz nemáme na to skutočne čerpať ako mriežka, a pokiaľ ju nakresliť ako mriežka Myslím, že sa veci v skutočnosti dostať trochu zavádzajúce. Čo programátor by, v jeho vlastnej mysli, všeobecne myslieť na to Pamäť ako je rovnako ako páska, ako kus krycou páskou že jednoducho pokračuje ďalej a ďalej navždy alebo kým vám dôjdu pamäte. Takže častejšie spôsob, ako čerpať a len premýšľať o pamäti by sa, že je to bajt nula, jedna, dva, tri, a potom bodka, bodka, bodka. A máš celkom 42 takých bytov, a to aj aj keď fyzicky mohlo by to v skutočnosti byť niečo viac takhle. 

Takže ak si teraz myslí vašich pamäť, pretože to, rovnako ako páska, to je to, čo programátor znovu by vyžadovalo rad pamäte. A keď chcete skutočne uložiť niečo v pamäti počítača, budete všeobecne robiť uloženie vecí back-to-back back-to-back. Takže sme hovorili o číslach. A keď som chcel riešiť problémy rovnako ako štyri, jeden, tri, dva, aj keď len som bol kreslenie len čísla štyri, jeden, tri, dva na palube, by počítač Naozaj majú toto nastavenie do pamäte. 

A čo by bolo vedľa dva v pamäti počítača? No, nie je odpoveď na túto otázku. My naozaj neviem. A tak dlho, kým Počítač nepotrebuje, to nemusí starať, čo je ďalší s číslami, že sa zaujíma o. A keď som skôr povedal, že v počítači môže sa iba na jednej adrese v čase, To je druh prečo. 

Nie na rozdiel od záznamu prehrávačom a čítacia hlava budú môcť prezrieť určitá len Drážka vo fyzickom zázname old-school v čase, obdobne môže počítač vďaka k jeho CPU a jeho Intel inštrukčná sada, medzi ktorého pokyn sa číta z pamäte alebo uložiť do memory-- Počítač môže len pozerať na jednom mieste pri time-- niekedy aj ich kombinácie, ale naozaj len jedno miesto naraz. Takže keď sme robili tieto rôzne algoritmy, Nie som len písanie v vacuum-- štyri, jeden, tri, dva. Tieto čísla skutočne patriť niekde fyzickej pamäte. Takže tam sú malinké tranzistory alebo nejaký druh elektroniky pod kapucňa ukladanie týchto hodnôt. 

A celkom, koľko bitov podieľajú práve teraz, len aby bolo jasno? Tak toto je štyri byty, alebo Teraz je to 32 bitov celkom. Takže tam sú vlastne 32 nuly a Tí tvoriaci tieto štyri veci. Tam je ešte tu, ale Znovu sme sa nestarajú o to. 

Takže teraz poďme položiť ďalšie Otázkou pomocou pamäte, preto, že na konci dňa je v rozpore. Bez ohľadu na to, čo by sme mohli robiť s počítač, na konci dňa hardvér je stále Rovnaký pod kapotou. Ako by som ukladať slovo tu? No, slovo v počítači, ako "Hej!" by boli uložené, rovnako ako to. A ak by ste chceli dlhšiu Slovo, môžete jednoducho prepísať, že aj niečo povedať ako "ahoj" a obchod, ktorý tu. 

A tak aj tu to contiguousness je v skutočnosti výhodou, pretože počítač môže len čítať sprava doľava. Ale tu je otázka. V súvislosti s týmto slovom, h-e-l-l-o, výkričník, ako by počítač vedieť, kde je Slovo začína a kde slovo končí? V súvislosti s číslami, Ako sa počítače vedieť, ako dlho sled Čísla je alebo tam, kde to začína? No, to ukáže out-- a nepôjdeme príliš veľa do tejto úrovne detail-- Počítače pohybovať veci okolo v pamäti doslova prostredníctvom týchto adries. Takže v počítači, ak ste písania kódu na uloženie vecí ako slová, čo ste naozaj robia, je písanie výrazy, ktoré si spomenúť, kde v Pamäť počítača sú tieto slová. Tak ma nechaj robiť veľmi, veľmi jednoduchý príklad. 

Chystám sa ísť dopredu a otvárajú jednoduchého textového programu, a idem k vytvoreniu súbor s názvom hello.c. Väčšina týchto informácií sme nepôjde do veľmi podrobne, ale budem písať Program v tomto jazyku, C. To je oveľa viac zastrašujúce, Tvrdím, než Scratch, ale je to veľmi podobné v duchu. V skutočnosti tieto vlnité braces-- môžete druh myslieť na to, čo som práve urobil, pretože to. 

Ideme na to, v skutočnosti. Keď zelená vlajka kliknutie vykonajte nasledujúce. Chcem vytlačiť "Dobrý deň." Takže toto je teraz pseudocode. Som typ rozmazanie linky. V jazyku C, tento jazyk hovorím o tento riadok print ahoj v skutočnosti sa stáva "printf" s Niektoré zátvorky a bodkočiarku. 

Ale je to presne rovnaký nápad. A to veľmi užívateľsky príjemný "Pri zelenou vlajkou kliknutí" sa stáva oveľa viac tajomný "int main neplatné." A to naozaj nemá mapovanie, tak som len tak ignorovať. Ale zložené zátvorky sú rovnako ako zakrivené dieliky takto. 

Takže si môžete trochu hádať. Dokonca aj keď ste nikdy predtým naprogramovaný, Čo tento program pravdepodobne robiť? Pravdepodobne vytlačí ahoj s výkričníkom. 

Takže poďme to skúsiť. Chystám sa ho zachrániť. A to je opäť veľmi old school prostredie. Nemôžem na tlačidlo, nemôžem pretiahnuť. Musím písať príkazy. Takže chcem spustiť svoj program, takže Mohol som to urobiť, rovnako ako hello.c. To je súbor som bežal. Ale počkajte, ja som chýba krok. Čo urobil hovoríme, je nevyhnutným krokom pre jazyk C? Práve som napísal zdroj kód, ale čo k tomu potrebujem? Jo, musím kompilátora. Takže na mojom počítači Mac tu, mám program s názvom GCC, GNU C kompilátor, ktorý mi umožňuje robiť tohle-- zákrutu môj zdrojový kód do, budeme hovoriť, strojový kód. 

A vidím, že opäť nasledujúcim spôsobom, tieto sú nuly a tie, ktoré som práve vytvorené z môjho zdrojového kódu, všetky núl a jednotiek. A keď chcem spustiť my program-- sa to stane byť nazývaný a.out pre historická reasons-- "Dobrý deň." Aj to môže bežať znovu. Ahoj ahoj ahoj. A zdá sa, že pracuje. 

Ale to znamená, že niekde v mojom Pamäť počítača sú slová h-e-l-l-o, výkričník. A ukázalo sa, rovnako ako stranou, čo je to počítač by typicky tomu, že vie, kde veci začnú a end-- je to bude klásť zvláštny symbol tady. A konvencie je umiestniť číslo nula na konci slova takže viete, kde to skutočne končí, takže nevedú vytlačiť viac a viac znaky, ako si v skutočnosti v úmysle. 

Ale stánok s jedlom tu, a to aj hoci to je docela tajomný, je, že to nakoniec relatívne jednoduché. Ste dostali akúsi pásku, prázdne Priestor na ktoré môžete písať listy. Vy proste musíte mať Špeciálny symbol, ako je ľubovoľne číslo nula, aby na konci vaše slová tak, aby počítač vie, oh, mal by som prestať tlače po Vidím výkričník. Vzhľadom k tomu, ďalšia vec, ktorú tu je ASCII hodnota nula, alebo null charakter as niekto by sa to nazvať. Ale je tu trochu problém tu a poďme vrátiť čísel na chvíľu. Predpokladajme, že mám v skutočnosti, majú celý rad čísel, a predpokladajme, že Program píšem je ako stupeň knihy pre učiteľov a učiteľov v triede. A tento program mu umožňuje zadať skóre svojich žiakov Na vypočúva. A predpokladám, že študent dostane 100 na svojom prvom teste, možno ako 80 na ten budúci, potom 75, potom 90 na štvrtom teste. 

Takže v tomto bode príbehu, poľa je veľkosti štyri. Tam je absolútne väčšie množstvo pamäte v počítač, ale pole, aby som tak povedal, je o veľkosti štyri. Predpokladajme teraz, že učiteľ chce priradiť piaty kvíz na triedu. No, jedna z vecí, alebo ona bude musieť robiť Teraz je uložiť dodatočnú hodnotu tu. Ale ak pole má učiteľ vytvorené v tomto programe je veľkosti pre, jeden z problému s poľom je, že môžete nielen držať pridanie do pamäte. Vzhľadom k tomu, čo keď iné časti Program má slovo "hej" práve tam? 

Inými slovami, má pamäť môže byť použiť na čokoľvek v programe. A ak sa vopred som zadal, hej, Chcem vstup štyroch kvíz skóre, Môžu ísť tu a tu. A ak sa náhle zmení svoj názor neskôr a že chcem piaty kvíz skóre, môžete nielen dať kamkoľvek budete chcieť, pretože čo keby to Pamäť je používaný o niečo else-- nejaký iný program alebo iné funkcie programu že vediete? Takže musíte myslieť dopredu Ako chcete uložiť svoje dáta, pretože teraz si namaľoval yourself do digitálneho rohu. 

Takže učiteľ by mohol miesto povedať, kedy písanie programu pre uloženie jeho alebo jej stupňa, viete čo? Budem požadovať, Pri písaní môj program, že chcem nula, jedna, dva, tri, štyri, päť, šesť, osem stupňov celkom. Tak jeden, dva, tri, štyri, päť, šesť, sedem, osem. Učiteľ môže len niečo málo cez prideliť pamäti pri písaní jeho alebo jej program, a hovoriť, viete čo? Nikdy nebudem priradiť viac ako osem vypočúva v semestri. To je jednoducho šialené. Už nikdy prideliť to. Tak, že tento spôsob on alebo ona má Flexibilita pre ukladanie študentské skóre, rovnako ako 75, 90, a možno jeden navyše, ak študent dostal kreditu navyše, 105. 

Ale v prípade, že učiteľ nikdy používa tieto tri medzery, je tu intuitívne stánok s jedlom tu. On alebo ona je len plytvanie miestom. Takže inými slovami, tam je to Spoločný kompromis pri programovaní kde si môžete buď prideliť presne toľko, koľko pamäte, ako chcete, Nahor z nich je, že si výborný efficient-- nie ste byť nehospodárne na all-- ale nevýhoda, z ktorých Je čo keď si to rozmyslíte, kedy pomocou programu, ktorý chcete uložiť viac dát, než ste pôvodne zamýšľali. 

Možné riešenia je, teda, napísať svoje programy tak, že používajú viac pamäte než v skutočnosti potrebujú. Týmto spôsobom si nejdeš naraziť na tento problém, ale tie sú nehospodárne. A čím viac pamäte váš program používa, ako sme diskutovali včera, tým menej pamäť, ktorá je k dispozícii pre iné programy, tým skôr môže byť váš počítač spomaliť dole, pretože virtuálnej pamäte. A tak ideálnym riešením by mohlo byť to, čo? 

Under-prideľovanie zdá zlé. Over-Pridelenie zdá zlé. Takže to, čo by mohlo byť lepším riešením? Prerozdelenie. Byť dynamickejšie. Nenúťte si vybrať priori, na začiatku, čo chcete. A už vôbec nie viac ako prideliť, aby ste neboli nehospodárne. 

A tak na dosiahnutie tohto cieľa sme musieť hodiť túto dátovú štruktúru, tak povediac, preč. A tak to, čo programátor sa zvyčajne používajú Je niečo, čo nazýva nie je array ale previazaný zoznam. Inými slovami, on alebo ona bude začať premýšľať o ich pamäť ako bytia druh tvaru, ktorý im možno čerpať v nasledujúcom spôsobom. Ak chcem uložiť jedno číslo program-- takže je to september, Dal som moji študenti kvíz; Chcem ukladať prvý kvíz študentov, a dostali 100 na to-- I Chystám sa opýtať môj počítač, prostredníctvom tohto programu som napísané, pre jeden kus pamäte. A budem ukladať Číslo 100 v ňom, a to je všetko. 

Potom niekoľko týždňov neskôr keď som si svoj druhý kvíz, a je čas písať V tomto 90%, idem požiadať počítač, hej, počítač, môžem mať iný kus pamäti? Bude to, aby mi to prázdny kus pamäte. Chystám sa dať do položky 90, ale v mojom programe nejakým spôsobom other-- a nebudeme báť syntax pre tohle-- potrebujem nejako reťaz tieto veci dohromady. A ja im to reťaz spolu s čo vyzerá ako šíp tu. 

Tretí kvíz, ktorý príde, Chystám sa povedať, hej, počítač, daj mi ešte kus pamäte. A ja idem dať dole čo to bolo, ako 75, a musím reťazci tejto teraz spolu nejako. Štvrtý kvíz príde, a možno to je ku koncu semestra. A tým bodom môjho programu môže byť použitie pamäte všade, po celom fyzicky. A tak len pre zábavu, som bude kresliť to tam quiz-- som zabudol, aké to bolo; ja že možno 80 alebo something-- cesta sem. 

Ale to je v poriadku, pretože obrazovo Budem čerpať tento riadok. Inými slovami, v skutočnosti, v hardvéru počítača, Prvý skóre mohlo skončiť tu, pretože je to hneď na začiatku semestra. Budúci jeden by mohol skončiť tady pretože trochu času uplynulo a program stále beží. Ďalším skóre, ktorá bola 75, by mohol byť tu. A posledná skóre mohlo byť 80, čo je tu. 

Takže v skutočnosti fyzicky, by to mohlo byť čo pamäte počítača vyzerá. Ale to nie je užitočný mentálny paradigma pre počítačový programátor. Prečo by vám záleží, kde je Heck vaše dáta skončí? Chcete len pre ukladanie dát. 

To je niečo ako našu diskusiu skoršie čerpanie kocky. Prečo sa staráš, čo uhol je kocka a ako budete musieť obrátiť ju nakresliť? Chcete len kocky. Rovnako tak tu vás jednoducho chcú stupňa knihe. Len chcete myslieť toto ako zoznam čísel. Koho zaujíma, ako je to realizované v hardvéri? 

Takže teraz abstrakcie Je to obrázok tu. Ide o zoznam spojená, as programátor by to nazval, ak máte Zoznam samozrejme čísel. Ale je to spojené obrazovo pomocou týchto šípok, a všetky tieto šípy are-- naspodku digestor, ak ste zvedaví, Pripomíname, že náš fyzický hardvér má adresy nula, jedna, dva, tri, štyri. Všetky tieto šípy sú ako mapu alebo nasmerovanie, kde v prípade 90 je-- teraz Musím počítať. 

Nula, jedna, dva, tri, štyri, päť, šesť, sedem. Vyzerá to, že 90 je adresa pamäti číslo sedem. Všetky tieto strely sa ako malý kúsok papiera že to dáva pokyny k Program, ktorý hovorí, že riadiť túto mapu sa dostať na miesto siedmej. A tam nájdu Druhý kvíz skóre študenta. Medzitým, 75--, či budem pokračovať to, To je sedem, osem, deväť, 10, 11, 12, 13, 14, 15. 

Tento druhý šíp práve predstavuje mapy na pamäťové miesto 15. Ale opäť, programátor zvyčajne robí nestará o tejto úrovni detailu. A vo väčšine každom programovania jazyka dnes, programátor ani nebude vedieť, kde v pamäti tieto čísla v skutočnosti sú. Všetky on alebo ona má sa starať o ich ktoré sú nejakým spôsobom spojené dohromady V dátové štruktúry, ako je táto. 

Ale ukazuje sa, nie je sa dostať príliš technické. Ale len preto, že môžeme snáď dovoliť mať túto diskusiu, Domnievame sa, že sme znova Tento problém tu z poľa. Uvidíme, či budeme ľutovať ísť sem. To je 100, 90, 75, a 80. 

Dovoľte mi, aby som stručne, aby toto tvrdenie. Toto je pole, a znovu, charakteristickým rysom maticu je to, že všetky vaše dáta je späť, aby chrbtom k sebe v memory-- doslovne jeden byte alebo možno štyri bajty, niektoré fixný počet bajtov preč. V prepojenom zozname, ktorý by sme mohli čerpať takto, pod kapotou, ktorý vie, kde tá vec je? To ani nemusí prúdiť takhle. Niektoré z týchto údajov môže byť späť vľavo hore. Nemusíte ani vedieť. 

A tak s radom, máte Funkcia známy ako náhodný prístup. A čo s priamym prístupom znamená, že počítač môže skočiť okamžite na ľubovoľné miesto v poli. Prečo? Vzhľadom k tomu, že počítač vie že prvá poloha je nula, jedna, dve, tri. 

A tak ak chcete prejsť z tento prvok k ďalšiemu prvku, doslova, v počítače myseľ, stačí pridať jeden. Ak chcete ísť do tretieho prvku, stačí pridať one-- ďalší prvok, len pridať jeden. Avšak, v tejto verzii príbehu, predpokladám počítač je v súčasnej dobe hľadá na alebo do činenia s číslom 100. Ako sa dostanete k ďalšiemu stupňa v platovej triede knihe? 

Musíte vziať sedem Kroky, ktoré je ľubovoľná. Ak chcete získať na ten budúci, budete musieť trvať ďalších osem krokov sa dostať do 15 rokov. Inými slovami, to nie je konštantný medzeru medzi číslami, a tak to jednoducho berie Počítač viac času je bod. Počítač má k hľadanie prostredníctvom pamäte v poradí nájsť to, čo hľadáte. 

Tak vzhľadom k tomu, pole má tendenciu byť rýchla údaje structure-- kvôli tebe môže doslova robiť jednoduchú aritmetiku a dostať tam, kam chcete, pridaním jedného, Pre instance-- spájať zoznam, obetujete túto funkciu. Nemôžete jednoducho ísť od prvej na druhej až tretieho na štvrté miesto. Budete musieť nasledovať mapy. Budete musieť vziať ďalšie kroky sa dostať k tým hodnotám, ktoré Zdá sa, že pridanie náklady. Takže budeme platiť cenu, ale to, čo bolo funkcia, ktorá Dan hľadal tu? Čo spájať zoznam zrejme nám umožňujú robiť, ktorý bol pôvod tento konkrétny príbeh? 

Presne tak. Dynamická veľkosť na to. Môžeme pridať do tohto zoznamu. Môžeme dokonca zmenšiť zoznamu, takže že sme iba pomocou toľko pamäti ako vlastne chceme a tak nikdy nie sme over-prideľovanie. 

Teraz už len stačí byť naozaj niť-vyberavý, tam je skrytá náklady. Takže by ste nemali nechať ma presvedčiť ste, že je to presvedčivý kompromis. Je tu ďalšie skryté náklady tu. Výhoda, aby bolo jasné, je to, že dostaneme dynamiku. Ak chcem ďalší prvok, môžem len nakresliť a vložiť číslo tam. A potom som ho prepojiť s obrázkom tu, zatiaľ čo tu opäť, či som maľoval sám seba do kúta, -Li niečo iné už používa pamäť tu, som smolu. Ja som namaľoval sám seba do kúta. 

Ale to, čo je skryté stálo na tomto obrázku? Nejde len o sumu o čas potrebný ísť odtiaľ až sem, čo je sedem krokov, potom osem stupňov, čo je viac ako jedna. Aký je ďalšie skryté náklady? Nie je to len čas. Doplňujúce informácie potrebné na dosiahnutie tento obrázok. 

Jasne, že mapa, tie malé kúsky papiera, ako som držať popisovať je ako. Jedná arrows-- tie nie sú zadarmo. Computer-- viete čo je v počítači. To má núl a jednotiek. Ak chcete reprezentovať šípky alebo A máp alebo číslo, budete potrebovať nejakú pamäť. Takže druhú cenu, ktorú platiť za prepojeného zoznamu obyčajná počítačová veda zdroj, je tiež priestor. 

A skutočne tak, tak často, medzi kompromisov pri navrhovaní softvérové ​​inžinierstvo Systémy je čas a space-- sú dve z vašich zložiek, dvaja z vašich najnákladnejších zložiek. To ma stojí viac času pretože musím sledovať túto mapu, ale je to tiež mi stojí viac priestoru pretože musím držať túto mapu okolia. Takže nádej, ako sme druh diskutovali viac ako včera a dnes je, že výhody preváži náklady. 

Ale nie je jasné riešenie tu. Možno je to better-- a la rýchle a špinavé, ako Kareem navrhnuté earlier-- hodiť pamäte na problém. Stačí kúpiť viac pamäte, myslím, že menej hard o vyriešenie problému, a riešiť ju v jednoduchším spôsobom. A skutočne skôr, keď sme sa rozprávali o kompromisy, to nebolo priestor v počítač a čas. Bolo na čase developer, ktorý je ďalším zdrojom. 

Takže znova, je to balansovanie sa snaží rozhodnúť, ktorá z týchto vecí ste ochotní minúť? Čo je najlacnejšie? Čo vedie k lepším výsledkom? Jo? 

Naozaj. V takom prípade, ak ste reprezentujúci čísla v maps-- títo sú povolaní v mnohých jazykoch "Ukazovátka" alebo "adresa" - je to dvojnásobok priestor. Že nemusí byť tak zlé, ako double ak Teraz sme len ukladanie čísel. Predpokladajme, že sme boli ukladanie záznamy o pacientoch v hospital-- takže mená Pierson to, telefónne čísla, čísla sociálneho poistenia, lekár históriou. Tento box môže byť veľa, oveľa väčšie, v takom prípade malinké ukazovateľ, adresa ďalšie element--, že to nie je veľký problém. Je to taký strapce stálo na tom nezáleží. Ale v tomto prípade, jo, je to dvojnásobok. Dobrá otázka. 

Poďme sa baviť o dobe, kedy trochu konkrétnejšie. Aká je doba chodu vyhľadávania tento zoznam? Dajme tomu, že som chcel hľadať cez všetky stupne študentov, a je tu n tried v tejto dátovej štruktúry. Tiež tu môžeme požičať Slovník skôr. Jedná sa o lineárny štruktúra dát. 

Veľký O n je to, čo je potrebné, aby si na konci tejto dátové štruktúry, whereas-- a my sme nevideli Tento before-- pole vám dáva čomu sa hovorí časová konštanta, čo znamená, jeden krok alebo dva kroky alebo 10 steps-- nezáleží. Je to pevne stanovený počet. To nemá nič spoločné s veľkosť poľa. A dôvod pre to, Znovu je náhodný prístup. Počítač môže len bezprostredne skočiť na inom mieste, pretože sú všetky rovnaké vzdialenosť od všetkého ostatného. Neexistuje žiadna myslenie zapojiť. Dobre. Takže ak môžem, dovoľte mi, aby som sa snaží maľovať dve posledné fotky. Veľmi častým jeden známy ako hash tabuľky. Takže motivovať túto diskusiu, nechaj ma premýšľať o tom, ako to urobiť. 

Tak ako o tom? Predpokladajme, že problém Ak chceme riešiť teraz realizuje v dictionary-- takže celá partia anglických slov alebo čokoľvek iného. A cieľom je, aby bolo možné zodpovedať otázky forme je to slovo? Takže chcete implementovať kontrolu pravopisu, len ako fyzická slovníka že sa môžete pozrieť, čo sa v. Predpokladajme, že keby som to s poľom. Nemohol som to urobiť. 

A predpokladám, že slová sú jablká a banán a melón. A ja si nemyslím, že ovocie že začať s d, takže sme len bude mať tri plody. Takže to je pole, a my sme skladovanie všetky tieto slová v tomto slovníku ako pole. Otázkou teda je, ako inak mohol by ste uložiť tieto informácie? 

No, ja som trochu podvádzanie tu, pretože každý z týchto písmen v slove je naozaj individuálne byte. Takže keď som naozaj chcel byť niť-vyberavý, mal som naozaj Tento rozdelit do oveľa Menšie kúsky pamäte, a my sme mohli robiť presne to. Ale budeme narážať na rovnaký problém ako predtým. Čo keď, ako Merriam Webster alebo Oxford robí každý rok-- dodávajú slová na dictionary-- my nie nutne chcú maľovať sami do rohu s poľom? 

Takže namiesto toho, možno múdrejší prístup je dať jablko vo vlastnom uzla alebo box ako by sme povedať, banán, a Potom tu máme ananásový melón. A my string tieto veci dohromady. Tak toto je pole, a To je previazaný zoznam. Ak sa vám nie je úplne vidieť, to jednoducho hovorí: "pole", a to hovorí, že "zoznam." 

Takže máme rovnaký Presné problémy ako predtým, kedy máme teraz dynamika nášho prepojeného zoznamu. Ale my máme pomerne pomalý slovník. Dajme tomu, že chcem vyhľadať slovo. To mi môže trvať veľký O n kroky, pretože slovo by mohla sa celú cestu na konci zoznam, rovnako ako melónu. A ukázalo sa, že programovanie, triedenie Svätého grálu údajov štruktúry, je niečo, že vám dáva konštantný Čas ako maticu ale napriek tomu vám dáva dynamiku. 

Takže môžeme mať to najlepšie z oboch svetov? A skutočne, je tu niečo volal hash tabuľky ktorý vám umožní robiť presne že, hoci len približne. Hash tabuľka je milovník Dátová štruktúra, ktorá nám napadne ako kombinácia array-- a budem ju čerpať ako tohle-- a spojových zoznamov že budem čerpať takhle tady. 

A to, ako tá vec Práca je nasledujúci. Pokiaľ toto now-- hash table-- je môj tretí dátová štruktúra, A chcem uložiť slov to, nemám chcete len ukladať všetky Slová chrbtom k sebe, aby chrbtom k sebe. Chcem využiť niektoré kus informácií o slovách, ktorá vám umožní me dostať tam, kde je to rýchlejšie. 

Tak daný slová jablko a banán a melón, Zámerne som zvolil tie slová. Prečo? Čo je to druh zásadne odlišný o tri? Čo je jasné? Začínajú s rôznymi písmenami. 

Tak viete čo? Skôr než dať všetky moje slová rovnaký vedro, tak povediac, rovnako ako v jednej veľkej zozname, prečo nie Aj aspoň pokúsiť optimalizácia a aby sa moje zoznamy 1/26 tak dlho. presvedčivá optimalizácia by mohol byť dôvod, prečo nie Já-- pri vkladaní slovo do tejto dátovej štruktúry, do pamäte počítača, prečo Čo keby som sem dať všetky "A" slovo, všetky "b" slová tu, a všetky "C" slova tu? Takže toto skončí uvedenie jablko tu, banán tu, ananásový melón tu, a tak ďalej. 

A ak mám ďalšie Slovo jako--, čo je ďalší? Jablko, banán, hruška. Každý, kto myslieť na ovocie ktorý začína, B alebo C? Blueberry-- perfektné. Že sa chystá skončiť tu. A tak sa zdá, že majú okrajovo lepšie riešenie, pretože teraz, keď chcem hľadať jablko, ja first-- ja nie len ponoriť do mojej dátové štruktúry. Nemyslím ponoriť do pamäte svojho počítača. Prvýkrát som sa pozrieť na prvé písmeno. 

A to je to, čo počítačový vedec povie. Vy hash do svojej dátovej štruktúry. Budete mať svoj vstup, ktorý v Tento prípad je slovo, ako jablko. Môžete analyzovať, pri pohľade na Prvé písmeno v tomto prípade, tým ju hash. Hešovanie je všeobecný termín, kedy budete mať niečo ako vstup a produkovať nejaký výstup. A výstup v tom, že Prípad je umiestnenie Ak chcete vyhľadávať, prvý lokalita, druhé miesto, tretí. Takže vstup je jablko, je výstup prvej. Vstup je banán sa Výstup by mal byť druhý. Vstup je ananásový melón, výstup by mal byť tretí. Vstup je čučoriedka sa Výstup by mal byť opäť druhý. A to je to, čo vám pomôže vziať skratky cez svoju pamäť za účelom získania slovám alebo dáta efektívnejšie. 

Teraz to znižuje svoj čas potenciálne ako veľa ako jedna z 26, pretože ak predpokladáme, že vás mať toľko "A" slová ako "z" Slová ako "q" slov, ktorá v skutočnosti nie je realistic-- budete mať prekrútiť naprieč niektoré písmená alphabet-- ale to by prírastkové Prístup, ktorý má umožniť môžete sa dostať do slov oveľa rýchlejšie. A v skutočnosti, sofistikovaná programu, Okuliare na svete, Facebooks z world-- by použiť hash tabuľky pre mnoho rôznych účelov. Ale oni by nemala byť tak naivný, len pozrieť na prvé písmeno V jablko alebo banán alebo hruškovica alebo melónu, pretože ako môžete vidieť tieto zoznamy by mohli ešte dostať dlho. 

A tak by to mohlo byť ešte sort z linear-- tak nejako pomaly, rovnako ako s veľkým O n ktoré sme diskutovali skôr. Takže, čo je to naozaj dobrý hash tabuľka do-- to bude mať oveľa väčší poľa. A bude používať oveľa sofistikované funkcie zatrieďovanie takže to nie je len pozrieť na "A". Možno to vyzerá na "A-p-p-l-e" a nejako prevádza tých päť písmen do miesta, kde Apple by mal byť uložený. My len naivne pomocou písmeno "A" sám, pretože je to pekný a jednoduchý. 

Ale hash tabuľka, v koniec, môžete myslieť ako kombinácia poľa, pričom každý z nich Má prepojený zoznam, ktorý v ideálnom prípade by mala byť čo najkratšia. A to nie je samozrejmé riešenie. V skutočnosti, veľa z jemného doladenia , Čo sa deje pod kapotou, keď vykonávaní týchto druhov sofistikované dátové štruktúry je to, čo je správne Dĺžka poľa? Aká je správna hash funkcie? Ako sa vám uloženie vecí do pamäte? 

Ale uvedomujem, ako rýchlo tento druh diskusie stupňoval, a to buď tak ďaleko, že je to trochu of nad hlavou v tomto bode, ktorý je v poriadku. Ale my sme začali, odvolanie, sa skutočne niečo, čo low-level a elektronické. A tak to zase je to Téma abstrakcie, kde akonáhle začnete brať za samozrejmosť, OK, mám tú to-- fyzickej pamäte, OK, to mám každý fyzické umiestnenie má adresu, OK, ja to mám, môžem reprezentovať tieto adresy sú arrows-- môžete veľmi rýchlo začať mať sofistikovanejšie konverzácie, ktoré nakoniec sa zdá, že nám umožňuje riešiť problémy, ako je vyhľadávanie a triedenie efektívnejšie. A buďte si istý, too-- pretože myslím, že to je najhlbšia sme išli do niektorej z týchto tém SK proper-- my sme vykonaná v deň a pol na to bod, čo by ste mohli robiť viac ako obvykle Priebeh osem týždňov v semestri. 

Akékoľvek otázky týkajúce sa títo? Nie? Dobre. No, prečo nie my pozastaviť tam, spustiť obed niekoľko minút skôr, pokračovať v len asi hodinu? A budem prodleva pre trochu otázkami. Potom budem musieť ísť trvať niekoľko hovory iba v prípade, že je v poriadku. Budem zapnúť nejakú hudbu do tej doby, ale obed by mal byť za rohom.