DAVID Malan: U redu. Vratili smo se. Tako je u ovom segmentu o programiranju ono Mislio sam da ćemo učiniti je mješavina stvari. Jedan od njih, napraviti malo nešto hands-on, iako korištenjem više razigran programiranje environment-- onaj koji je demonstrativno od upravo one vrste ideja smo se govori o, ali malo više formalno. Dva, pogled na neke od više tehničkih načina da programer će zapravo riješiti problemi kao što je traženje problema da smo pogledali prije i i važnije Zanimljivo problem sortiranja. 

Mi smo samo pretpostaviti iz dobiti ići da je taj telefonski imenik je riješeno, ali to samo po sebi zapravo neka vrsta Teško je problem s mnogo različitih načina to riješiti. Dakle, mi ćemo koristiti ih kao klasa problema Predstavnik stvari koje mogla biti riješena u cjelini. A onda ćemo razgovarati o u nekim detaljima što nazivaju podatke structures-- ljubitelj načine kao povezane liste i hash tablica i drveća koje programer bi zapravo upotrebu i uglavnom koriste na ploči slikati slika ono što on ili ona predviđena za provedbu neki komad softvera. 

Tako ćemo učiniti ruke na dio prvi. Dakle, samo dobiti vaše ruke prljave s okoliš nazivaju scratch.mit.edu. To je alat koji koristimo u našem preddiplomskog klasi. Iako je dizajniran za mlađe od 12 i više godina, ćemo ga koristiti za gore dio tog vrlo malo budući da je lijepa, zabavna grafički način učenja Malo nešto o programiranju. Pa glavu na tom URL-u, gdje vas treba vidjeti stranicu baš tako, i ići naprijed i kliknite Pridružite Scratch u gornjem desnom kutu i odabrati korisničko ime i lozinka i na kraju sami doći account-- scratch.mit.edu. Mislio sam da ću koristiti kao prilika prvi pokazati ovo. Pitanje je došao za vrijeme pauze o tome što je broj zapravo izgleda. I razgovarali smo tijekom pauze o C, u particular-- osobito Niža razina u starijoj jeziku. A ja samo na brzinu Google pretraživanje kako bi pronašli C koda za binarno pretraživanje, algoritam koji smo koristiti za pretraživanje taj telefonski imenik ranije. Ovaj primjer, naravno, ne traži telefonskog imenika. To samo traži hrpu Brojevi u memoriju racunala. Ali, ako želite samo dobiti vizualni osjećaj što stvarni programiranje jezik izgleda, to izgleda malo nešto ovako. Dakle, riječ je o 20-plus, 30-ak linija koda, ali razgovor smo imali više od odmora je o tome kako je to zapravo dobiva prerasla u nula i jedinica a ako ne može samo vratiti da proces i idu od nula i jedinica natrag na kodu. 

Nažalost, proces tako je transformativni da je puno lakše reći nego učiniti. JA je otišao naprijed i zapravo okrenuo taj program, binarna pretrage, u nula i jedinica na način da se Program pod nazivom prevodilac da sam dogoditi da su ovdje upravo na moj Mac. A ako pogledate na zaslonu ovdje, posebno usredotočuje na ovim srednjim šest stupaca samo vidjet ćete samo nula i jedinica. I oni su nula i jedinica koje sastaviti točno da je u potrazi program. 

I tako svaki komad pet bitova, svaki bajt nula i jedinica ovdje, predstavljaju neke upute obično unutar jednog računala. A u stvari, ako ste čuli Marketing slogan "Intel Inside" - da je, Naravno, samo znači da imate Intel CPU ili mozga u unutrašnjosti računala. A što to znači biti CPU da imate skup instrukcija, da se tako izrazim. 

Svaki procesor na svijetu, mnogi od ih je napravio Intel ovih dana, razumije konačan Broj uputa. A oni su upute tako niska razina kao dodaj ta dva broja zajedno, pomnožiti ova dva broja zajedno, premjestiti ovaj dio podataka odavde ovdje u memoriji, osim toga Informacije odavde do ovdje u memoriji, i tako forth-- tako jako, jako niske razine, gotovo elektronički detalje. Ali, s onima koji su matematički operacije zajedno s onim što smo ranije, predstavljanje podataka kao nula i jedinica, mogu ste izgraditi sve koje računalo može učiniti danas, da li to je tekstualni, grafički, glazbene, ili drugačije. 

Dakle, to je vrlo lako doći izgubljen u korova brzo. I tu je puno sintaktičke izazovi pri čemu ako bi najjednostavnije, najgluplji pri upisu nitko od programa će raditi što god. I tako, umjesto pomoću jezik kao što je C jutros, Mislio sam da će to biti zabavnije stvari za napraviti nešto više vizualni, što dok je dizajniran za djecu je zapravo savršena manifestacija stvarnog programiranja language-- je slučajno korištenje slika umjesto teksta da predstavlja one ideje. 

Dakle, nakon što doista imaju računa o scratch.mit.edu, kliknite gumb Stvori u gornjem lijevom kutu stranice. A ti bi trebao vidjeti okruženje kao što je onaj sam vidjet na mom ekranu ovdje. A mi ćemo samo malo troše malo vremena igrajući ovdje. Da vidimo, ako ne možemo sve riješiti neke Problemi zajedno na sljedeći način. 

Dakle, ono što ćete vidjeti u ovo environment-- i zapravo samo neka mi pauza. Je li netko nije ovdje? Ne ovdje? U REDU. Dakle, dopustite mi naglasiti neke Karakteristike ovom okruženju. 

Dakle, u gornjem lijevom kutu zaslona, ​​mi imaju nule pozornici, da tako kažemo. Scratch je ne samo naziv ovog programskog jezika; to je ujedno i naziv mačka koja vidiš po defaultu tamo u narančasto. On je na pozornici, tako baš kao što sam opisao kornjača ranije kao u pravokutna bijela okolina ploča. Ova mačka je svijet ograničen u cijelosti na taj pravokutnik do vrha tamo. 

U međuvremenu, na desnoj ruka strana ovdje, to je samo skripte područje, prazna ploča, ako će. Ovo je mjesto gdje ćemo pisati naši programi u samo jednom trenutku. I izgrađeni da ćemo koristiti za pisanje ovog program-- zagonetku komada, ako will-- su oni ovdje u sredini, i oni su kategorizirane po funkcionalnosti. Tako, na primjer, ja ću ići naprijed i pokazuju barem jednu od ovih. Ja ću ići naprijed i kliknite kategorija Kontrola do vrha. 

Dakle, to su kategorije do vrha. Idem kliknite kategoriju upravljanje. Umjesto toga, ja ću kliknuti na događaje kategorija, prvi jednog do vrha. A ako želite slijediti čak kao što smo to učinili, vi ste sasvim dobrodošli. Idem kliknite i povucite ovo Prvi, "kad zelena zastava kliknuli". A onda ću ga odvesti samo otprilike na vrhu mojih praznih lista. 

A što je lijepo o ispočetka je da je ova zagonetka komad, kad isprepleteni s drugim slagalice komada, će učiniti doslovno što one slagalice kažu učiniti. Tako, na primjer, ispočetka je u pravu sada usred njegovog svijeta. Ja ću ići naprijed i birati Sada, recimo, u kategoriji Motion, ako želite da učine same-- kategoriju Motion. A sada primijetiti imam jednu cjelinu hrpa slagalice ovdje da, opet, vrsta učiniti ono što oni kažu. I ja ću ići naprijed i povući i ispustiti potez blok u pravu ovdje. 

I primjetite da čim ste dobili blizu dna "zelene zastave kliknuo "gumb, obavijest kako izgleda bijela linija, kao da je to gotovo magnetska, on želi ići tamo. Samo neka idu, i to će puknuti zajedno i oblici će odgovarati. A sada možete možda gotovo pogodite gdje ćemo s ovim. 

Ako pogledate nule fazi ovdje i gledati na vrhu, vidjet ćete crvenu svjetlost, znak stop, i zelenu zastavu. I ja ću ići naprijed i gledati screen-- samo na trenutak, ako može. Idem kliknite Zelena zastava upravo sada, i on se ono što se čini 10 koraka ili 10 piksela, 10 točkice na zaslonu. 

I tako ne da je uzbudljivo, ali neka mi predloži čak i bez poučavanja to, samo koristeći svoj vlastiti intuition-- neka ja predlažem da si shvatiti kako čine Blok Hodajte s pozornice. Jeste ga se napravilo mjesta za desnu stranu ekran, sve do desne strane. Dopustite mi da vam dati trenutak ili tako boriti s tim. Možda želite pogledati na druge kategorije blokova. U redu. Samo da ponovimo, kada smo zelena zastava klik ovdje i premjestiti 10 koraka je samo pouku, svaki put kad kliknite zelenu zastavu, što se događa? Pa, to je trčanje moj program. Tako sam mogao učiniti možda 10 puta ručno, ali to se osjeća malo malo hackish, da tako kažemo, pri čemu nisam stvarno rješavanju problema. Ja sam samo jednom pokušava i opet i opet i opet dok sam nekako slučajno postigla direktive da sam krenuo u postizanju ranije. 

Ali mi znamo iz naših pseudokod ranije da postoji Taj pojam je u programiranju petlje, radi nešto opet i opet. I tako sam vidio da je hrpa vas posegnuo je za ono puzzle komada? Ponavljaj do. Tako smo mogli učiniti nešto kao i ponovite sve dok. I što si ponavljati sve dok se točno? 

U REDU. I pusti me jednima nešto jednostavnije samo na trenutak. Dopustite mi ići naprijed i učiniti. Uočite da, kao što svibanj imati Otkrio pod kontrolom, nalazi se ova ponavljanja bloka, koji ne izgleda kao da je to velika. Nema puno mjesta u između ta dva žuta linija. Ali, kao što neki od vas možda ima primijetio, ako povučete i ispustite, primijetiti kako ona raste popuniti oblik. 

A čak možete strpati više. To će zadržati samo raste ako povucite i lebdjeti nad njom. A ja ne znam što je najbolje ovdje, pa neka mi barem ponavljati pet puta, na instanca, a zatim se vratiti na pozornicu i kliknite na zelenu zastavu. I sad primijetiti da nije dosta tamo. 

Sada neki od vas predložio, kao Victoria jednostavno nije, ponovite 10 puta. I to uglavnom ne dobiti ga skroz, ali ne bi li biti robusniji način nego samovoljno figuring out koliko poteza napraviti? Što bi moglo biti bolje blok nego ponoviti 10 puta biti? 

Da, pa zašto ne učiniti nešto zauvijek? I sad neka mi premjestiti ovaj dio slagalice unutra i riješi se ove. Sada primjetiti Bez obzira gdje ispočetka počne, on ide do ruba. I srećom MIT, koji čini nule, samo osigurava da on nikada potpuno nestaje. Uvijek možete uhvatiti svoj rep. 

I samo intuitivno, zašto je držati se kreće? Što se ovdje događa? On kao da je stalo, ali onda ako sam pokupiti i povucite on drži žele ići tamo. Zašto je to? Zaista, računalo je doslovno učiniti ono što vi to kažem. Dakle, ako ste ga rekli ranije učiniti Sljedeća stvar zauvijek, pomaknuti 10 koraka, to će zadržati ide i ide dok sam pogodio crveni znak stop i uopce zaustaviti program. 

Dakle, čak i ako nije to, kako sam mogao napraviti Scratch brže preko ekrana? Više koraka, zar ne? Dakle, umjesto da radiš 10 u isto vrijeme, zašto ne ići naprijed i promijeniti ga to-- što bi propose-- 50? Dakle, sada ću kliknuti zelena zastava, i doista, on ide jako brzo. 

A to je, naravno, samo je manifestacija animacije. Što je animacija? To je samo ti pokazuje čovjeku cijela hrpa fotografija zaista, jako, jako brzo. I tako, ako mi samo reći ga premjestiti više koraka, mi smo samo imaju efekt biti Promjena gdje je na ekranu sve brže po jedinici vremena. 

Sada sljedeći izazov koji sam predložio bilo da ga odbijaju ruba. I ne znajući što zagonetka komada exist-- jer to je u redu ako ne dobiti na faza challenge-- ono želiš raditi intuitivno? Kako bi smo ga odskočiti natrag i dalje, između lijevo i desno? 

Da. Dakle, treba nam nekakav stanja, a mi čini se da su uvjetne, tako da se govoriti u kategoriji kontrole. Koji od ovih blokova mi vjerojatno želite? Da, možda ", ako, onda." Dakle, primijetiti da je među žutim blokovima ovdje imamo, nalazi se ova "ako" ili ovo "ako drugi" blok koji će nam omogućiti da donese odluku da to učini ili to učiniti. A možete ih i gnijezdo raditi više stvari. Ili ako ne ste otišli još ovdje, ići naprijed u kategoriju Sensing and-- da vidimo je li to ovdje. 

Dakle, ono blok bi moglo biti korisno ovdje otkriti je li on s pozornice? Da, primijetiti da su neki od tih blokova može biti parametrizirana, da tako kažemo. Oni mogu biti na neki način prilagoditi, a ne za razliku od HTML-a jučer s atributima, gdje su ti atributi vrsta prilagoditi ponašanje oznake. Isto tako ovdje mogu zgrabiti ovu dira blok i promjene i postaviti pitanje, ti dira miš pokazivač poput pokazivača ili si dira rub? 

Zato me pusti i to učiniti. Idem smanjivanje na trenutak. Dopustite mi da iskoristite ovu slagalice ovdje, ova zagonetka komad toga, a ja ću promućkati im se samo na trenutak. Idem da se presele toga, promijeniti u dirljivim ruba, a ja ću pokretu to učiniti. Dakle, ovdje su neki sastojci. Mislim da imam sve što želim. 

Bi li netko želio predložiti kako sam mogu povezati to možda vrha do dna kako bi se riješio problem koji ima Blok potez ka lijeva na desno kako bi lijeva na desna na lijevo, svaki Vrijeme samo odskakanje zidu? Što želim raditi? Koji blok bih trebao spojiti na "Kad zelena zastava kliknuli na prvom mjestu"? 

OK, počnimo s "zauvijek". Ono što ide u sljedeći? Netko drugi. OK, premjestiti korake. U redu. Što onda? Pa onda, ako. I primijetiti, iako to izgleda sendviču zajedno čvrsto, to će samo rasti ispuniti. To će samo skok u kojoj ja to želim. 

A što da stavim između if i onda? Vjerojatno "ako dira rub." I napomena, opet, to je prevelika za to, ali to će rasti ispuniti. A onda okrenuti za 15 stupnjeva? Koliko stupnjeva? Da, pa 180 će se vrtjeti meni sve na putu oko. Dakle, neka je vidjeti ako sam dobio to pravo. Pusti me smanjivanje. 

Pusti me vući Scratch gore. Dakle, on je malo iskrivljena sada, ali to je u redu. Kako ga mogu resetirati lako? Idem malo prevariti. Pa ja sam dodao još jedan blok, samo da bude jasno. Želim da ukazuju 90 stupnjeva desno po defaultu, tako Samo ću mu reći to učiniti programski. I ovdje mi ići. Čini se da su to učinili. To je malo čudno, jer Hoda naopako. Nazovimo to kukca. To je pogreška. Bug je greška u programu, a logička pogreška koju sam, ljudski, napravljen. Zašto ide naopako? Jeste MIT zeznuo ili sam? 

Da, mislim, nije MIT-a kvara. Dali su mi slagalice koja kaže okrenuti neki broj stupnjeva. I na Victoria prijedlog, Ja sam okreće za 180 stupnjeva, koji je pravi intuicija. Ali okreće za 180 stupnjeva doslovno znači okretanje za 180 stupnjeva, a to nije stvarno ono što želim, očito. Jer barem je on u ovo dvodimenzionalni svijet, tako okreće se zapravo događa da ga okrenuti naopako. 

Vjerojatno želite koristiti ono što blok umjesto toga, na temelju onoga što vidite ovdje? Kako bismo mogli popraviti? Da, kako bismo mogli ukazati u suprotnom smjeru. A zapravo čak i da je to neće biti dovoljno, jer možemo samo teško kod na ulijevo ili udesno. 

Znaš što možemo učiniti? Čini se da imamo praktičnost blok ovdje. Ako sam zumirati, vidi nešto što nam se sviđa ovdje? Tako to izgleda kao MIT ima apstrakcija sagrađena ovdje. Ovaj blok čini se da je jednaka na koji drugi blokovi, množina? 

Ovaj blok čini se da je jednaka cijeloj ovoj trio blokova da imamo ovdje. Tako ispada da se pojednostavi moj Program uzimajući osloboditi od svega toga i samo staviti ovo ovdje. A sad je još malo lud, i to je u redu za sada. Ostavit ćemo to biti. No, moj program je još jednostavnije, a to je, također, će biti predstavnik od cilja u programming-- je idealno bi svoj kod kako jednostavan, kompaktan je to moguće, dok je još uvijek kao Ëitkijim. Vi ne želite da bude tako kratak da je teško razumjeti. 

Ali primijetit sam zamijenio tri bloka s jedne, i to je vjerojatno dobra stvar. Ja sam izdvojiti daleko pojam provjere da li ste na rubu sa samo jednim blokom. Sada možemo zabaviti uz to, u stvari. To ne dodavati toliko intelektualna vrijednost, ali razigrana vrijednost. Idem samo naprijed i iskoristite ovaj zvuk ovdje. Pa neka mi ići naprijed, i neka me zaustaviti program za trenutak. Idem snimati sljedeće, omogućava pristup do mog mikrofona. 

Idemo. Ouch. Pokušajmo ponovno. Idemo. OK, zabilježio sam krivu stvar. Idemo. Ouch. Ouch. U redu. Sada moram riješiti to. U redu. 

Tako sada imam Snimanje samo "jao". Dakle, sada ću ići naprijed i to nazivamo "jao". Idem se vratiti moje skripte, a sada Obavijest postoji taj blok koji se zove igrati zvuk "Mijau" ili reproducirati zvuk "jao". Idem povući ovo, i gdje trebao sam staviti ovo komično snagu? Da, pa sad je to vrsta lud, jer sada to block-- primijetiti kako je to "ako je na rubu, bounce "je vrsta self-sadržane. Dakle, moram popraviti. Dopustite mi ići naprijed i učiniti. Pusti me da biste dobili osloboditi od toga i vratiti našem original, promišljeniji funkcionalnost. Dakle, "ako se dodiruje rub, a zatim" Želim da se, kao što je Victoria predložio, 180 stupnjeva. I želim igrati zvuk "jao" ne postoji? 

Da, primijetiti da je vani da je žuta blok. Dakle, to je, također, bio bi bug, ali sam ga primijetio. Tako ću ga povući ovdje, i obavijest sada je unutar "ako". Dakle, "ako" je ovo vrsta baš kao ruka nalik na mrlje da će samo učiniti ono što je u njoj. Pa sad, ako sam smanjivanje na rizik od annoying-- 

Računalo: Joj, joj, joj. 

DAVID Malan: I samo će ići na zauvijek. Sada samo ubrzati stvari Ovdje, dopusti mi ići naprijed i otvoriti, neka je say-- me pusti da se neki moje vlastite stvari iz razreda. I neka mi se otvaraju, recimo, ovaj jednom napravio jedan od naših nastavnih bližnjima prije par godina. Dakle, neki od vas možda podsjetiti ova igra od prošle, i to je zapravo nevjerojatno. Iako smo učinili Najjednostavniji programa upravo sada, neka je razmotriti što je to zapravo izgleda. Pusti me pogodak igrati. 

Dakle, u ovoj igri, imamo žaba i korištenja strelicu keys-- on uzima veće korake nego što sam remember-- Imam kontrolu nad tom žaba. A cilj je da se preko zauzet Cesta bez trčanje u automobilima. I neka je see-- ako idem ovdje, ja morati čekati zapisnik se pomicati. To se osjeća kao kukca. To je vrsta kukca. U redu. Ja sam na ovo ovdje, tamo, a onda držati ide dok ne dobijete sve žabe na ljiljan jastučići. Sada bi to moglo izgledati sve složeniji, ali neka je pokušati razbiti ovo dolje psihički i verbalno u sastavne blokove. Dakle, tu je vjerojatno puzzle komad koji još nismo vidjeli ali to je reagirati na tipke, stvari sam pogodio na tipkovnici. 

Tako da je vjerojatno neka vrsta blok koji kaže da, ako je ključ jednak gore, zatim učinite nešto s Scratch-- možda premjestiti ga 10 koraka na ovaj način. Ako je pritisnut tipku, pomaknite 10 koraka na ovaj način, ili lijevu tipku, pomaknite 10 koraka Na taj način, 10 koraka to. Ja sam jasno pretvorio mačka u žabu. Dakle, to je samo gdje je kostim, kao i Blok pozivi it-- mi Samo uvezena sliku žabe. 

Ali što drugo se događa? Ono što drugi linija koda, što drugi slagalice učinio Blake, naš demonstrator, koriste u ovom programu, očito? Što čineći sve move-- ono programiranje graditi? 

Motion, sure-- tako premjestiti blok, to je sigurno. A što je to potez blok unutar, najvjerojatnije? Da, neka vrsta petlje, možda zauvijek blokirati, možda ponoviti block-- ponovite sve dok blok. I to je ono što je stvaranje dnevnika i ljiljan jastučići i sve ostalo potez naprijed-nazad. To je samo što se događa u nedogled. 

Zašto su neki od automobila kreće brže od ostalih? Što je drugačije o tim programima? Da, vjerojatno neki od njih su uzimanje više koraka odjednom, a neke od njih manje koraka odjednom. A vizualni efekt je brz u odnosu na spor. 

Što misliš da se dogodilo? Kad sam je dobio moj žaba skroz preko ulice i rijeke na ljiljan jastučić, nešto pažnje dogodilo. Ono što se dogodilo čim sam to učinio? Zaustavio. To žaba zaustavljen, a Dobio sam drugu žabu. Pa što konstrukt mora biti koristi tamo, što je značajka? 

Da, tako je neka vrsta "Ako" stanje tamo, previše. I ispada out-- nismo vidjeli učinimo ali ima drugih blokova u bilo koje mogu reći, ako ste dira još jedna stvar na ekranu, ako ste dodirivanje Lily Pad ", zatim". I onda je to kad smo bi se pojaviti druga žaba. Dakle, iako je ova igra je svakako vrlo datiran, iako na prvi pogled postoji toliko ide on-- i Blakea nije bič to u dvije minute, to je vjerojatno uzeo ga je nekoliko sati za izradu ove igre temelji se na njegovoj memoriji ili videa prošla verzija njega. No, sve ove sitnice ide na zaslonu u izolaciji svode se na to vrlo jednostavan constructs-- pokreti ili izjave kao što smo rekli, petlje i uvjeti, te da je o tome. Postoji nekoliko drugih ljubitelj značajke. Neki od njih su čisto estetskog ili akustični, poput zvukova samo sam igrao s. No, za najveći dio, ima na tom jeziku, ispočetka, svi temeljni građevni blokovi koji vas ima u C, Java, JavaScript, PHP, Ruby, Python, i bilo koji broj drugih jezika. Bilo kakva pitanja o nule? U redu. Pa nećemo roniti dublje ispočetka, iako ste dobrodošli ovaj vikend, pogotovo ako imate djecu ili nećakinje i nećaka i slično, uvesti ih ispočetka. To je zapravo predivno razigrano okruženje s, kako njegovi autori kažu, vrlo visokim stropovima. Iako smo započeli s vrlo detalji niske razine, zaista možete učiniti vrlo malo s njim, a to je vjerojatno demonstracija upravo to. 

Ali neka se sada prijeći na nešto više sofisticirane problemi, ako će, poznat kao "traži" i "Sortiranje" općenito. Imali smo taj telefonski imenik earlier-- evo još jedna samo za discussion-- da smo bili u mogućnosti pretraživanja učinkovitije jer značajnog pretpostavke. I samo da bude jasno, što pretpostavka bila sam izradi kada se pretražuje putem ovog telefonskog imenika? Mike Smith je bio u telefonski imenik, iako sam će biti u mogućnosti da obrađuju scenarij bez njega tamo ako sam prerano prestao. Knjiga je abecedni. I to je vrlo velikodušan pretpostavka, jer to znači someone-- Ja sam vrsta rezanje kutak, kao što sam brže jer netko još je puno teškog rada za mene. 

No, što ako je telefon Knjiga se nerazvrstani? Možda Verizon dobio lijen, samo bacila svakog čovjeka imena i brojeva tamo možda u redoslijedu u kojem su prijavili za telefonske usluge. I koliko vremena to me odvesti naći nekoga kao što je Mike Smith? 1000 stranica telefon book-- koliko Stranice moram gledati kroz? 

Svi oni. Ti si neka vrsta sreće. Vi doslovno morati pogledati svaki stranica ako je telefonski imenik je samo nasumce razvrstani. Možda ćete dobiti sretan i naći Mike na prvoj stranici, jer je on Bio je to prvi kupac naručiti telefonske usluge. No, on je možda bio posljednji, previše. 

Dakle, slučajnim redoslijedom nije dobro. Dakle, pretpostavimo da imamo za sortiranje telefonski imenik ili općenito podatke sortiranja koje smo dobili. Kako ćemo to učiniti? 

Pa, neka mi samo probati jednostavan primjer. Pusti me naprijed i bacanje nekoliko brojeva na brodu. Pretpostavimo brojeve koje imamo su, recimo, četiri, dva, jedan i tri. I Ben, sortiranje ove brojeve za nas. 

OK Dobro. Kako ti je to uspjelo? U redu. Dakle, početi s najmanji vrijednost i najviša, i to je stvarno dobar intuicija. I shvatili da smo ljudi su zapravo prilično dobar u rješavanju problema ovako, barem kada su podaci relativno mali. Čim počnete da imaju stotine brojeva, tisuće brojeva, milijuni brojeva, Ben vjerojatno to ne mogu baš tako brzo, uz pretpostavku da su praznine u tim brojevima. Prilično lako brojati do milijun inače, baš vremena. 

Dakle, algoritam zvuči kao što je Ben sada koristi samo je potraga za najmanji broj. Dakle, iako mi ljudi mogu uzeti u puno informacija vizualno, računalo je zapravo malo više ograničen. CAN računalo samo pogledajte jedan bajt u isto vrijeme ili možda četiri bajta na prvi time-- ovih dana možda 8 bajta na prvi time-- ali vrlo mali broj bajtova u određenom trenutku. 

Dakle, s obzirom da smo stvarno imati Četiri odvojene vrijednosti here-- i možete misliti Ben kao vlasništvo povez preko očiju da se radi o računalu, kao što da on ne može vidjeti ništa drugo od jednog broja pri time-- tako da će općenito pretpostaviti, kao u Engleski, mi ćemo čitati s desna na lijevo. Tako je prvi broj Ben vjerojatno izgledala na bilo četiri, a zatim vrlo brzo shvatio da je prilično velika number-- neka mi držati obličje. 

Ima dva. Pričekaj minutu. Dva je manji od četiri. Idem za pamćenje. Dva je sada najmanji. Sada one-- to je čak i bolje. To je još manji. Idem zaboraviti dvije i samo sjetiti sada. 

A mogao prestati gledati? Pa, mogao je na bazi na ovoj informaciji, ali on je bolje pretragu ostatak popisa. Jer, što ako nule su na popisu? Što ako je negativna su na popisu? On samo zna da je njegov odgovor je ispravan ako je iscrpno provjeriti cijeli popis. Tako smo, pogledajte ostatak ove. Three-- to je gubljenje vremena. Imaš sreće, ali sam bio još uvijek točna to učiniti. I tako je sada vjerojatno odabrana najmanji broj i samo ga stavi na početku popisa, kao što ću učiniti ovdje. Sad što si dalje, iako ne mislite o tome gotovo do te mjere? Ponovite postupak, pa neka vrsta petlje. Postoji poznata ideja. Dakle, ovdje je četiri. To je trenutno najmanji. To je kandidat. Ne više. Sad sam vidio dva. To je sljedeći najmanji element. Three-- to nije manja, tako da Sada je Ben može oteti iz dva. 

I sada smo ponoviti postupak, a naravno tri dobiva izvukao sljedeći. Ponovite postupak. Četiri dobiva izvukao. A sada smo bez brojeva, tako da popis mora biti riješeno. 

I doista, ovo je formalna algoritam. Računalni znanstvenik to nazivamo "Odabir vrste" Ideja se Poredaj A opet navesti iteratively-- i opet i opet odabira najmanji broj. A što je lijepo o tome je to je jednostavno tako prokleto intuitivno. To je tako jednostavno. A možete ponoviti isti Operacija opet i opet. Jednostavno je. 

U ovom slučaju to je brzo, ali Koliko je zapravo potrebno? Učinimo to činiti i Osjećam se malo više zamoran. Dakle, jedan, dva, tri, četiri, pet i šest, sedam, osam, devet, 10, 11, 12, 13, 14, 15, 16-- proizvoljan broj. Samo sam htjela još ovo Vrijeme od samo četiri. Dakle, ako sam dobio jednu cjelinu hrpa brojeva to now-- ni ne smeta što are-- Idemo razmišljati o tome što je to Algoritam je stvarno slično. 

Pretpostavimo da postoje brojevi tamo. Opet, ne smeta što je oni su, ali oni su slučajni. Javljam Benov algoritam. Moram odabrati najmanji broj. Što da radim? I ja idem na fizički to učiniti ovaj put da ga glume. U potrazi, u potrazi, gleda, gleda, gleda. Tek kad sam doći do kraj popisa mogu Jasno mi je najmanji broj je bio dva i ovaj put. Jedan nije na popisu. Zato sam spustio dva. 

Što da učinim? U potrazi, u potrazi, u potrazi, u potrazi. Sad sam našla broj sedam, jer postoji praznina u tim numbers-- ali samo proizvoljna. U redu. Pa sad ja mogu spustiti sedam. Gledajući gleda, gleda. 

Sada sam uz pretpostavku, od Naravno, da Ben ne imati dodatni RAM, pomoćni memorije, jer, naravno, Gledam u istom broju. Sigurno sam mogao sjetio sve te brojeve, i to je apsolutno istinito. Ali ako Ben pamti sve od brojeva što je vidio, on zapravo nije napravio temeljni napredak jer on već ima sposobnost za pretraživanje kroz brojeve na brodu. Sjećanje na sve od Brojevi ne pomogne, jer on može i dalje kao računalo samo pogledajte, mi smo navedeni, jedan broj u isto vrijeme. Dakle, nema vrsta varanja ima koji možete iskoristiti. 

Dakle, u stvarnosti, kao što sam držati koji traži popis, Doslovno sam se samo zadržati ide naprijed i nazad kroz njega, čupanje sljedeći najmanji broj. I kao što možete vrsta zaključiti iz mojih glupih pokreta, Ovo postaje vrlo dosadan vrlo brzo, i čini mi se da ide natrag i naprijed, natrag i naprijed vrlo malo. Sad da bude fer, ja ne moram ići sasvim kao, dobro, neka je see-- da bude fer, Ne moram hodati sasvim onoliko koraka svaki put. Jer, naravno, kao što sam odabir brojeva s popisa, preostali popis je sve kraći. 

I tako ćemo razmišljati o koliko koraka sam zapravo traipsing kroz svaki put. U prvom situaciji imali smo 16 brojeva, pa maximally---a neka samo to učiniti za discussion-- Morao sam gledati kroz 16 Brojevi pronaći najmanji. Ali jednom sam iskopali najmanji broj, kako dugo je preostalo popis, naravno? Samo 15. Dakle, koliko brojeva učinio Ben ili moram gledati kroz drugi put oko? 15, samo otići i pronaći najmanji. Ali sada, naravno, popis je, također, manji nego što je bio prije. Pa koliko koraka zar ne uzeti sljedeći put? 14, a zatim 13, a zatim 12, plus dot, točka, točka, dok sam napustio sa samo jednom. Tako sada računalni znanstvenik pitam, dobro, što to svi jednaki? To je zapravo jednak neki beton broj koji smo mogli sigurno učiniti aritmetički, ali želimo razgovarati o učinkovitosti algoritama malo više formulaically, neovisna o tome koliko dugo je popis. 

I tako, znate što? To je 16 godina, ali kao što sam rekao prije, neka je samo poziv na veličinu problema n, gdje je n neki broj. Možda je 16, možda je tri, možda je milijun. Ne znam. Ne zanima me. Ono što stvarno želim je formula koja mogu koristiti za usporedbu ovog algoritma protiv drugih algoritama da bi netko mogao tvrditi su bolje ili lošije. 

Tako ispada, a samo ja znam iz osnovne škole, da je to zapravo radi se na isto stvar kao N iznad n plus jedan više od dva. I to se događa jednaka, od Naravno, n na kvadrat plus n više od dva. Dakle, ako sam htjela formulu za koliko koraka su bili uključeni u gleda na sve svaki put iznova tim brojevima i opet i opet, rekao bih to n je kvadrat plus n više od dva. Ali znate što? To samo izgleda neuredno. Samo sam stvarno želite opći osjećaj stvari. A možda sjetiti iz visoka škola koja postoji je pojam najvišeg reda pojam. Koji od ovih uvjeta, n kvadrat, N, ili pola, ima najveći utjecaj tijekom vremena? Veći n dobiva, koji o ovim pitanjima najviše? 

Drugim riječima, ako se spoji u milijun, n na kvadrat koja će se najvjerojatnije faktor u momčadi, jer milijun puta Sama je puno veći od plus jedan dodatni milijun. Dakle, znate što? Ovo je tako prokleto velika broj ako trg broj. To nije važno. Samo ćemo križ koji van i zaboraviti o tome. I tako računalni znanstvenik će reći da učinkovitost tog algoritma je reda n squared-- Mislim zaista aproksimacija. To je na neki način grubo n na kvadrat. Tijekom vremena, što je veći i veći n dobiva, to je dobra procjena za ono što je Učinkovitost ili nedostatak učinkovitosti ovog algoritma zapravo jest. I ja izvući, naravno, od zapravo radi math. Ali sada sam samo maše moje ruke, jer sam upravo Želite opći osjećaj tog algoritma. 

Dakle, koristeći istu logiku, u međuvremenu, Razmotrimo još jedan algoritam mi već gledao at-- linearno pretraživanje. Kad sam bio u potrazi za telefon book-- Nije ga sortiranje, pretraživanje putem telefona book-- mi je stalno govorio da je to 1.000 koraka, ili 500 koraka. Ali neka se generalizirati to. Ako postoji n stranice u telefonski imenik, što je Računanje vremena ili Učinkovitost linearno pretraživanje? To je na red koliko koraka kako bi pronašli Mike Smith linearnom pretraživanje, Prvi algoritam, ili čak i drugi? 

U najgorem slučaju, Mike se nalazi na kraju knjige. Dakle, ako je telefon knjiga ima 1.000 stranica, mi je rekao prošli put, u najgorem slučaju, to bi moglo potrajati otprilike koliko mnoge stranice kako bi pronašli Mike? Kao i 1000. To je gornja granica. To je najgora moguća situacija. Ali opet, idemo dalje od brojeva kao što su 1000 sada. To je samo n. 

Dakle, što je logičan zaključak? Pronalaženje Mike u telefonu Knjiga koja ima n stranice bi moglo potrajati, u najgorem slučaju, koliko koraka reda veličine n? I doista računalo znanstvenik će reći da je vrijeme rada, odnosno performansi ili učinkovitosti ili neučinkovitost, algoritma kao linearna pretraživanje na red n. I možemo primijeniti isti Logika prelaska nešto kao što sam upravo učinio u sekundu Algoritam smo imali s telefonskog imenika, gdje smo išli dvije stranice odjednom. 

Dakle 1000 stranica telefonski imenik možda će nas 500 stranica okreta, plus jedan ako smo dvostruko natrag malo. Dakle, ako telefon knjiga ima n stranica, ali radimo dvije stranice u isto vrijeme, to je otprilike što? N iznad dvije, tako da je kao N iznad dva. Ali ja napravio tvrditi Trenutak prije da n nad two-- to je vrsta isto kao i samo n. To je samo konstantan faktor, računalni znanstvenici će reći. Recimo samo da se usredotočite na varijable, really-- najveće varijable u jednadžbi. 

Dakle linearno pretraživanje, je li učinjeno jedno stranica odjednom ili dvije stranice odjednom, je vrsta u osnovi isti. To je još uvijek na red n. Ali ja tvrdio sa svojom slikom ranije da je treći algoritam nije bilo linearna. To nije bio ravna crta. Bilo je to zakrivljena linija, a algebarska formula je bilo što? Prijavite od n- tako log baze dvije n. I ne moramo ići u previše mnogo detalja o logaritmi danas, ali većina računalni znanstvenici ne bi čak vam reći što je baza. Jer to je sve samo stalne čimbenici, da tako kažemo, samo male brojčani razlike. I tako će to biti vrlo čest način posebno formalno računala znanstvenici na brodu ili programera na bijeloj ploči zapravo tvrdeći koji Algoritam će koristiti ili što je učinkovitost od njihova algoritam je. 

I to ne mora nužno biti nešto raspravljate na bilo vrlo detaljno, ali dobar programer je onaj koji ima solidnu, formalnu pozadinu. On je u stanju razgovarati s što u ovoj vrsti način i zapravo napraviti kvalitativne argumente zašto jedan algoritam ili jedan komad softvera je superioran na neki način u drugi. Zato što bi svakako samo pokrenuti program za jedne osobe i brojati broj sekundi što je potrebno za sortiranje neke brojeve, i možete pokrenuti neke Program druge osobe i brojati broj sekundi je potrebno. No, to je nešto širi način na koji možete koristiti za analizu algoritama, ako hoćete, samo na papir ili samo verbalno. Čak i bez da radi bez čak i težak uzorak ulaza, možete samo razmišljati kroz nju. I tako s bicikla programer ili ako ima mu ili joj na neki način raspravljati s tobom zašto je njihov algoritam, njihova tajna Umak za pretraživanje milijarde web stranica za vaš Tvrtka je bolje, to su vrste argumenata se idealno bi trebao biti u mogućnosti napraviti. Ili barem to su vrste stvari da bi se u raspravi, na barem u vrlo formalne rasprave. U redu. Dakle, Ben predložio nešto zove odabir vrsta. Ali ja ću predložiti da postoji drugi načini za to, previše. Ono što nisam stvarno volio oko Benova algoritam je da je hodao, ili što mi je hodati, naprijed i natrag i natrag i naprijed i natrag i naprijed. Što ako umjesto toga sam bila napraviti nešto poput ovih brojeva ovdje i ja se samo nositi sa svakim Broj opet kao što sam ga dao? 

Drugim riječima, ovdje je moj popis brojeva. Četiri, jedan, tri, dva. I ja ću učiniti sljedeće. Idem ubaciti brojeve gdje pripadaju a od odabira ih jednu po jednu. Drugim riječima, ovdje je broj četiri. 

Evo moj izvorni popis. A ja ću za održavanje u suštini novi popis ovdje. Dakle, ovo je stari popis. Ovo je nova lista. Vidim broj četiri na prvom mjestu. Moj novi popis početku je prazan tako da je trivijalno slučaj da su četiri sada ponekog popis. Ja samo da broj sam dao, a ja sam ga stavljajući u mom novom popisu. 

Je li to novi popis razvrstani? Da. To je glupo, jer postoji samo jedan Element, ali to apsolutno je riješeno. Nema ništa izvan mjesta. To je još zanimljivije, ovaj algoritam, kad sam premjestiti na sljedeći korak. 

Sada imam jedan. Dakle, jedan, naravno, pripada Na početku ili na kraju ovog novog popisa? Početak. Dakle, moram napraviti neki posao sada. Ive 'bio uzimajući neke slobode s markerom mom za samo crtanje stvari gdje želim ih, ali to nije stvarno točan u računalu. Računalo, kao što znamo, ima RAM ili Random Access Memory, i to je jedan bajt i još jedan bajt a drugi bajt. A ako imate gigabajt RAM-a, imate milijardu bajtova, ali oni su fizički na jednom mjestu. Ne možete samo premjestiti stvari oko tako da je crtež na brodu gdje god želiš. Dakle, ako je moj novi popis ima četiri lokacije u memoriji, nažalost četiri je Već na krivom mjestu. 

Dakle umetnuti broj jedan Ne mogu ga izvući ovdje. Ova memorija lokacija ne postoji. To bi bilo varanje, i ja sam bio varanje slikovno za nekoliko minuta ovdje. Pa stvarno, ako želim staviti ga ovdje, Moram privremeno kopirati četiri a zatim staviti onu tamo. 

To je u redu, to je točno, to je tehnički moguće, ali shvatite da je dodatni rad. Nisam samo staviti broj na mjestu. Prvi put sam morao pomaknuti broj, a zatim ga staviti na mjesto, pa sam nekako udvostručio svoju količinu rada. Dakle, imajte to na umu. 

Ali ja sam sada učinjeno s ovim elementom. Sada želim da zgrabite broj tri. Gdje je, naravno, to pripada? Između. Ne mogu varati više i samo ga tamo stavio, jer, opet, ove memorije u fizičkim lokacijama. Pa moram kopirati četiri i stavi tri ovamo. Nije velika stvar. To je samo jedan dodatni korak again-- osjeća vrlo jeftin. 

Ali sada sam prijeći na dva. Njih dvoje, naravno, pripada ovdje. Sada počinjete vidjeti kako rad može nagomilati. Sada ono što moram napraviti? Da, moram premjestiti četiri, I onda moram kopirati tri, i sada mogu umetnuti dvije. A kvaka s tim Algoritam Zanimljivo je da pretpostavimo imamo više ekstremnih slučaj u kojemu je recimo osam, sedam, šest, pet, četiri, tri, dva, jedan. To je, u mnogim kontekstima, najgori mogući scenarij, jer je prokleto stvar je doslovno unatrag. 

To ne stvarno utjecati na Benovu algoritam, jer u Benove odabir sortirati on će zadržati ide natrag i naprijed kroz popis. A budući da je uvijek u potrazi kroz cijeli preostali popisu nije važno gdje su elementi. No, u ovom slučaju s mojim umetanje approach-- pokušajmo. 

Dakle, jedan, dva, tri, četiri, pet, šest, sedam, osam. Jedan dva tri četiri, pet, šest, sedam, osam. Idem uzeti osam, i gdje sam ga stavio? Pa, na početku moje liste, jer je ova nova Popis je sortiran. I ja sam ga prekrižiti. 

Gdje da stavim sedam? Prokleti. To treba da ide tamo, pa Moram obaviti neke kopiranja. A sada sedam ide ovdje. Sada sam prijeći na šest. Sada je još više posla. 

Osam mora ići ovdje. Sedam mora ići ovdje. Sada je šest može ići ovdje. Sad sam uzeo pet. Sada je osam mora otići ovdje, sedam mora ići ovdje, šest mora ići ovdje, a sada pet i ponoviti. I ja sam prilično mnogo pomičući ga stalno. 

Tako je na kraju, ovaj algorithm-- mi ćemo zovu ga umetanje sort-- zapravo ima puno posla, previše. To je samo drugačiji vrsta posla nego Benov. Benov rad imao me ide natrag i naprijed cijelo vrijeme, Odabirom sljedeći najmanji Element opet i opet. Tako da je to vrlo vizualna vrsta posla. 

Taj drugi algoritam, koji je još correct-- da će dobiti posao done-- samo mijenja količinu rada. Čini se da u početku si štedi, jer ti si samo bave svaki element up front ne hodaju sve put kroz popis kao Ben bio. No, problem je, osobito u ovim ludi slučajevi u kojima je sve unatrag, ti si samo vrsta odgađanje teško raditi dok imate popraviti svoje pogreške. 

I tako, ako možete zamisliti osam i sedam i šest i pet a kasnije četiri, a tri i dva kreće put kroz popis, smo upravo promijenio vrsta posla radimo. Umjesto da radi u počevši od mog iteracije, Ja sam samo to radio u kraj svake iteracije. Tako ispada da je ovaj algoritam, također, općenito nazivaju umetanje sortiranje, Također je na red od n na kvadrat. To je zapravo ništa bolja, Nema boljeg na sve. 

Međutim, postoji i treći pristup Ja bi nas potaknuti da razmislite, što je ovo. Dakle, pretpostavimo da moj popis, zbog jednostavnosti Ponovno je četiri, jedan, tri, two-- samo četiri broja. Ben je imao dobru intuiciju, dobar čovjek intuicija prije, kojima smo fiksne cijeli popis eventually-- umetanja vrsta. natjerane da nas zajedno. Ali neka se uzeti u obzir Najjednostavniji način da se riješi ovaj popis. 

Ovaj popis nije riješeno. Zašto? U engleskom jeziku, objasniti zašto to nije zapravo riješeno. Što to znači da ne mogu izdvojiti? 

STUDENT: To nije linearan. 

DAVID Malan: Nije sekvencijalno. Daj mi jedan primjer. 

STUDENT: Stavi ih u red. 

DAVID Malan: U redu. Daj mi više specifičan primjer. 

STUDENT: uzlaznim redoslijedom. DAVID Malan: Nije uzlaznim redoslijedom. Budi precizniji. Ne znam što misliš pod uzlazno. Što nije u redu? 

STUDENT: Najmanji od Brojevi nije u prvom prostoru. 

DAVID Malan: Najmanji broj je ne u prvom prostoru. Budi određeniji. Počinjem shvaćati. Brojimo, ali ono što je izvan reda ovdje? 

STUDENT: Numerički slijed. DAVID Malan: Numerički slijed. Svatko je vrsta čuvanja to here-- vrlo visoku razinu. Samo doslovno mi reći što je krivo kao pet-godišnje moći. 

STUDENT: plus jedan. 

DAVID Malan: Å to je to? 

STUDENT: plus jedan. 

DAVID Malan: Što misliš plus jedan? Daj mi drugačiji od pet godina. Što nije u redu, mama? Što nije u redu, tata? Što misliš to nije razvrstani? 

STUDENT: To nije pravo mjesto. 

DAVID Malan: Å to je nije na pravom mjestu? 

STUDENT: Četiri. DAVID Malan: OK, dobro. Dakle, četiri nije tamo gdje bi trebao biti. Konkretno, je li to u redu? Četiri i jedan prvi dva broja ja vidim. Je li to u redu? Ne, oni su iz reda, zar ne? U stvari, mislim da je sada o računalu, previše. To može samo gledati na možda jedan, možda dvije stvari na once-- i zapravo samo jedna stvar u isto vrijeme, ali može barem pogledajte jednu stvar onda Sljedeća stvar tik do nje. 

Tako su to u redu? Naravno da ne. Dakle, znate što? Zašto ne uzeti dijete korake kako riješiti ovaj problem umjesto da radi ove maštu algoritmi poput Bena, gdje je on je na neki način popravljanja strane petlje kroz popis umjesto da radiš ono što sam učinio, gdje Ja samo vrsta je fiksiran kao idemo? Recimo samo doslovno razbiti Pojam order-- brojčanom redoslijedu, nazovite ga što god want-- u tim parovima usporedbe. 

Četiri i jedan. Je li to ispravan nalog? Tako ćemo popraviti. Jedan i četiri, a onda mi ćemo samo kopirati to. U redu, dobro. fiksna sam jedan i četiri. Tri i dva? Ne. Neka moje riječi odgovara prste. Četiri i tri? 

To nije u redu, pa ću napraviti jedan, tri, četiri, dva. OK Dobro. Sada četiri i dva? Moramo popraviti ovo. Dakle, jedan, tri, dva, četiri. Tako je to razvrstani? Ne, ali je to bliže razvrstani? 

To je zato što fiksne ovo pogreška, fiksne mi ovu grešku, a mi fiksne ovu pogrešku. Tako smo fiksne tri greške nedvojbeno. Još se zapravo ne izgleda riješeno, ali to je objektivno bliža sortirati jer smo fiksne neke od tih pogrešaka. 

Sada što da učinim? Ja vrsta došla do kraja popisa. Činilo se da sam fiksni sve pogreške, ali ne. Budući da u ovom slučaju, neki brojevi možda u obliku mjehurića se bliži na druge brojeve koji su još uvijek izvan reda. Tako ćemo to učiniti opet, i ja ću upravo to učiniti na mjestu ovaj put. Jedan i tri? U redu je. Tri i dva? Naravno ne, pa neka je to promijeniti. Dakle, dva, tri. Tri i četiri? A sada neka je samo biti osobito pedantan ovdje. Je li izdvojiti? Ti ljudi znaju da je riješeno. 

Trebao bih probati ponovno. Dakle, Olivia predlaže pokušam ponovno. Zašto? Budući da računalo nema raskoš naše ljudske oči samo gledajući back-- OK, ja sam učinio. Kako se računalo odrediti da je popis sada je sortiran? Mehanički. 

Ja bi trebao ići kroz još jednom, i to samo ako sam ne čine / pronaći bilo kakve pogreške mogu onda zaključiti kako je računalo, yep, mi smo dobro ide. Dakle, jedan i dva, dva i tri, tri i četiri. Sada sam se definitivno može reći da je ovo riješeno, jer sam napravio nikakve promjene. Sada će biti bug i samo glupo ako sam, računalo, upita ona ista pitanja opet očekujući različite odgovore. ne bi trebalo dogoditi. 

I tako sada Popis je sortiran. Nažalost, vrijeme rada Ovaj algoritam je također n na kvadrat. Zašto? Budući da imate n broj, te u najgorem slučaju morate premjestiti n brojeva n puta jer morate nastaviti nazad na provjeru i potencijalno popraviti ti brojevi. I mi možemo učiniti više formalna analiza, previše. 

Dakle, to je sve što za reći da smo uzeti tri različita pristupa, jedan od njih odmah intuitivno isključiti šišmiš iz Benu mom predložene umetanja sortirati na ovaj gdje se vrsta izgubiti iz vida šuma za drveće početku. Ali onda, ako se uzme jedan korak nazad, voila smo popravili sortiranje pojam. Dakle, ovo je, usudio bih se reći, niža razina možda nego neki od onih drugih algoritmi, ali neka je vidi ako ne možemo vizualizirati to putem ovoga. 

Dakle, ovo je nešto lijepo softver koji je netko napisao je korištenjem šarene trake koja se učiniti sljedeće za nas. Svaka od tih šipki predstavlja broj. Viši bar, veći broj, manji bar, manji broj. Dakle, idealno želimo lijep piramida gdje počinje mala i dobiva veliki, a to bi značilo da ti barovi su razvrstani. Tako ću ići naprijed i birati, Na primjer, Benova algoritam first-- odabir vrsta. 

A primijetiti ono što radi. Način na koji su si izabrali vizualizirati ovaj algoritam je da, baš kao što sam bio hodanje kroz moje liste, ovaj program je hodanje preko svog popisa brojeva, isticanje u roza svakom broj koji se gleda. A što će se dogoditi upravo sada? 

Najmanji broj koji I ili Ben pronašao odjednom dobiva se preselili na početak popisa. I primijetiti jesu neprihvaćanju broj koji je bio tamo, i to je savršeno u redu. Nisam se u tom razinom detalja. Ali trebamo staviti taj broj negdje, pa smo ga samo preselili na otvorena spot koji je izrađen. Tako ću ubrzati ova gore, jer inače postaje vrlo zamoran brzo. Animacija speed-- tamo idemo. Tako sada isti princip Bio sam nanošenja, ali ti možete početi osjećati algoritam, ako hoću, ili ga malo jasnije. I to algoritam ima učinak Odabirom sljedeći najmanji element, tako da ćeš početi vidi se rampa na lijevoj strani. I na svakoj iteraciji, kao što sam predložio, to ne malo manje posla. To ne mora da ide sve na putu natrag na lijevom kraju popisa, jer je već zna one su razvrstani. Tako je vrsta osjeća kao da je ubrzava, iako je svaki korak uzimajući istu količinu vremena. Postoji samo manje korake. A sada možete vrsta osjetiti Algoritam čišćenje kraj nje, i doista sada je riješeno. 

Dakle, umetanje sorta je sve učinio. Moram ponovno slučajnom polje. I primijetit ja mogu samo držati ga randomizirano, a mi ćemo dobiti približan Isti pristup, umetanje vrsta. Dopustite mi da to uspori do ovdje. Počnimo da više. Stop. 

Idemo preskočiti četiri. Idemo tamo. Nasumce su niz. I ovdje smo go-- umetanja vrsta. Igrati. Obavijest da je to bave svaki Element naiđe odmah, ali ako to spada u Obavijest krivo mjesto sve o radu koji mora dogoditi. Moramo držati se kreće više i više elemenata kako bi napravili mjesta za onoga želimo staviti na mjesto. 

Tako ćemo se usredotočiti na Lijevi kraj samo popis. Obavijest nismo ni pogledao at-- mi nisu označene u ružičastom ništa nadesno. Mi samo bave problemi kako idemo, ali mi stvara puno raditi za sebe i dalje. I tako, ako smo brzinu ovo gore sada da ide do kraja, ona ima drugačiji osjećaj za njega, istina. To je samo s naglaskom na lijevom kraju, ali radi malo više posla kao needed-- vrsta izglađivanje stvari više, popravljajući stvari, ali se bave konačnici s svaki element jedan po jedan dok ne dođemo do the-- dobro, mi svi znamo kako će se to završiti, tako da je malo underwhelming možda. 

No, popis u end-- spoiler-- će biti riješeno. Pa pogledajmo jedan posljednji. Ne možemo preskočiti. Mi smo skoro tamo. Dva ići, jedan. I voila. Izvrsno. 

Dakle, sada ćemo napraviti jedan posljednji, ponovno randomizirano s bubble sort. I obavijest ovdje, pogotovo ako sam ga usporiti dolje, to ne vodi swooping preko. Ali primijetit to samo čini par po par, comparisons-- vrsta lokalnih rješenja. No, čim smo dobili kraj popisa na roza, što će se morati ponoviti? Da, to će morati početi ispočetka, jer je to jedini fiksni parovima greške. I to je možda otkrila još druge. I tako, ako ubrzati ovaj gore, vi ćete vidjeti da, mnogo kao i ime implicira, manji elements-- ili bolje rečeno, veće elements-- počinju mjehurić do vrha, ako hoćete. I manji elementi s početkom u mjehuru dolje lijevo. I doista, to je vrsta vizualni efekt, kao dobro. I tako će to završiti završnu obradu na vrlo sličan način, previše. 

Mi ne moramo živjeti na ovaj jedan. Pusti me da otvori ovo sada, previše. Postoji nekoliko drugih algoritam za sortiranje u svijetu, od kojih su neke zarobljeni ovdje. A pogotovo za učenike koji nisu nužno vizualna ili matematički, kao što smo učinili prije, možemo Također to audially ako se povezati zvuk s ovim. I samo za zabavu, ovdje je nekoliko različitih algoritama, a jedan od njih posebno si će primijetiti zove se "stapaju vrsta." 

To je zapravo bitno bolji algoritam, tako da spajanje vrsta, jedan od one kojima namjeravate vidjeti, Nije red n na kvadrat. To je na red za n puta log n, koji je zapravo manji i time brže od one druge tri. I tu je drugi par glup one koje ćemo vidjeti. 

Dakle, ovdje mi ići s nekim zvukom. To je umetanje vrsta, pa opet to je samo bavi elementima kao i oni dolaze. To je balon vrsta, tako da je smatrajući ih parova u isto vrijeme. I opet, najveći elementi su mjehurića do vrha. 

Dalje se izbor vrsta. To je Benova algoritam, gdje opet on odabirom iterativno sljedeći najmanji element. I opet, sada možete zaista čuti da to je ubrzanje ali samo u mjeri u kojoj kao što se to radi sve manje i manje rad na svakoj iteraciji. To je brži jednom, spajanje vrsta, koji je sortiranje nakupine brojeva zajedno i onda ih se kombinira. Dakle look-- lijevu polovica je već riješeno. 

Sada je sortiranje desnu polovicu, a sada će ih kombinirati u jedan. To je nešto što se zove "Gnome vrsta." A možete vrsta vidi da je to ide natrag i naprijed, popravljajući rad malo i ovdje tamo prije nego što prijeđe u novi posao. I to je to. Postoji još jedna vrsta, što je stvarno samo za akademske svrhe, pod nazivom "glupo vrsta", koji se podatke, sortira ga slučajno, a zatim provjerava da li je to riješeno. A ako to nije, on ponovno sortira ga slučajno, provjerava da li je to riješeno, a ako ne ponavlja. I u teoriji, probabilistically to će se završiti, ali nakon vrlo malo vremena. Nije to najviše učinkovit algoritama. Dakle, bilo kakva pitanja o onima Posebni algoritmi ili ništa vezane tamo? 

Pa, sada zafrkavati, osim što je sve ove linije su da sam bio crtež i što sam uz pretpostavku računalo može učiniti ispod haube. Ja smatram da su svi od tih brojeva Držim drawing-- što im je potrebno da se pohranjene negdje u memoriji. Mi ćemo se riješiti tog tipa sad, previše. 

Dakle, komad memorije u computer-- tako RAM DIMM ono što smo tražili jučer, dual inline memory module-- izgleda ovako. A svaki od tih malih crnih žetona neki broj bajtova, tipično. A onda su zlatne igle su poput žice koje se spajaju na računalo, a zeleni silicij odbor je upravo ono što drži sve zajedno. Dakle, što to zapravo znači? Ako sam nekako izvući ovu istu sliku, pretpostavimo zbog jednostavnosti da je ovaj DIMM, dual inline memorijski modul, jedan gigabajt RAM-a, jedan gigabajt memorije, što je koliko bajtova ukupno? Jedan gigabajt je koliko je bajtova? Više od toga. 1124 je kilogram, 1000. Mega je milijun. Giga je milijardu. 

Jesam li lagao? Možemo čak i pročitati etiketu? To je zapravo 128 gigabajta, tako da je više. No, mi ćemo se pretvarati ovo je samo jedan gigabajt. Dakle, to znači da postoji milijarde bajtova memorije dostupne za mene ili 8 milijardi bita, ali idemo razgovarati u smislu bajtova sada, ići naprijed. 

Dakle, što znači da je to jedan bajt, ovo je još jedan bajt, ovo je još jedan bajt, a ako smo htjeli biti specifičan da bi morao izvući milijardu malo kvadrata. No, što to znači? Pa, neka mi samo uvećanje u na ovoj slici. Ako imam nešto što izgleda ovako sada, to je četiri bajta. 

I tako sam mogao staviti četiri brojeve ovdje. Jedan dva tri četiri. Ili sam mogao staviti četiri slova ili simbole. "Hej!" mogao ići upravo tamo, jer svaki od slova, smo raspravljali ranije, mogu se prikazati s osam bita ili ASCII ili bajt. Dakle, drugim riječima, možete stavi 8 milijardi stvari u ovog jednog stick memorije. Sad što to znači staviti stvari natrag natrag na leđa u spomen na ovako? To je ono što programer će nazvati "niz". U računalnom programu, ne mislim o podlozi hardvera, sam po sebi. Vi samo misliti o sebi kao vlasništvo Pristup ukupno milijardu bajtova, i možete sve što želite s njim. No, za praktičnost to je općenito korisno zadržati svoju memorijsku pravo jedni pored drugih se ovo sviđa. Dakle, ako sam zumirati učinimo jer mi sigurno ne ide privući milijarde malo squares-- pretpostavimo da je ova ploča predstavlja da štap memorije sada. A ja ću samo izvući što više moj marker završi davanje me ovdje. Tako sada imamo štap memorije na ploči koji je dobio jedan, dva, tri, četiri, pet, šest, jedan, dva, tri, četiri, pet, šest, seven-- tako 42 bajtova memorije na ukupno na ekranu. Hvala ti. Da, nije mi aritmetika pravu. Tako 42 bajta memorije ovdje. Dakle, što to zapravo znači? Pa, računalni programer zapravo bi se općenito mislite o ovom sjećanju kao upućujc. Drugim riječima, svaki od njih lokacija u memoriji, u hardver, ima jedinstvenu adresu. 

To nije tako kompliciran kao jedan Brattle Trg, Cambridge, Mass., 02.138. Umjesto toga, to je samo broj. To je bajt broj nula, to je on, ova dva, to je tri, a to je 41. Pričekaj minutu. Mislio sam da sam rekao 42 maloprije. počela sam brojati od nule, tako da je zapravo točno. Sada nemamo zapravo ga izvući kao mreža, a ako ga izvući kao mreža Mislim da stvari zapravo dobiti malo zabludu. Što programer bi, u svom vlastitom umu, općenito misli o ovome memorije kao što je to baš kao i kasetu, kao komad samoljepljiva traka koji samo ide na i na zauvijek ili dok ne ponestane memorije. Dakle češći način za crtanje i samo razmišljam o memoriji bi se da je to bajt nula, dva, tri, a onda točka, točka, točkica. A imate ukupno 42 takvih bajtova, čak iako je fizički to bi zapravo biti nešto više ovako. 

Dakle, ako se sada sjetiti svoje memorije što je to, baš kao i kasetu, to je ono što programer opet bih nazvao niz memorije. A kad želite da se zapravo pohranu nešto u memoriju računala, općenito Čuvati stvari back-to-back u back-to-back. Tako smo se govori o brojevima. A kad sam htio riješiti probleme kao i četiri, jedan, tri, dva, iako sam samo bio crtanje samo brojevi četiri, jedan, tri, dva na brodu, računalo će Stvarno su ove postava u memoriju. 

A što će biti sljedeći na dva u memoriju racunala? Pa, nema odgovor na to. Mi zapravo ne znamo. I tako dugo dok Računalo ne treba, to ne mora brinuti što je sljedeće brojevima on ne brine o tome. A kad sam rekao ranije da je na računalu mogu samo gledati na jednu adresu u isto vrijeme, to je vrsta zašto. 

Nije za razliku od rekordnih player i glava za čitanje samo biti u mogućnosti pogledati neki utor u fizičkom old-school rekord u isto vrijeme, na sličan način mogu se računalo hvala svog procesora i njegovog Intel skup instrukcija, među čijim uputama čita iz memorije ili spremiti u memory-- računalo može samo gledati na jednom mjestu u isto time-- ponekad kombinacija od njih, ali zapravo samo na jednom mjestu u isto vrijeme. Dakle, kada smo radili ovi razni algoritmi, Nisam samo pisanje u vacuum-- četiri, jedan, tri, dva. Ti brojevi zapravo pripadaju negdje fizički u memoriji. Dakle, postoje maleni malo tranzistori ili neki elektronike ispod napa spremanje te vrijednosti. 

A ukupno, koliko bita su uključeni sada, samo da bude jasno? Dakle, ovo je četiri bajta ili sada je ukupno 32 bita. Dakle, postoje zapravo 32 nula i Oni koji čine ove četiri stvari. Tu je još ovdje, ali opet mi nije stalo do toga. 

Dakle, sada ćemo postaviti još Pitanje pomoću memorije, jer je na kraju dana je u suprotnosti. Bez obzira što smo mogli učiniti s računalo, na kraju dan hardver je još uvijek Isto ispod haube. Kako bih pohraniti riječ ovdje? Pa, riječ je u računalu kao što su "Hej!" će biti pohranjen samo ovako. A ako si htio duže riječ, možete jednostavno prebrisati to i reći nešto kao što je "zdravo" i pohraniti ovdje. 

I tako i ovdje, također, ovaj contiguousness je zapravo prednost, jer računalo može jednostavno čitati s desna na lijevo. No, ovdje je pitanje. U kontekstu ove riječi, h-e-l-l-o, uskličnik, Kako bi se računalo zna gdje je Riječ počinje i gdje završava riječ? U kontekstu brojeva kako se računalo znam koliko je slijed Brojevi ni gdje to počinje? Pa, ispada out-- i nećemo ići previše u ovu razinu detail-- računala premjestiti stvari okolo u memoriji doslovno putem te adrese. Tako je u računalu, ako ste pisanja koda za pohranu stvari kao i riječi, što si stvarno radi piše Izrazi koji se sjećaju gdje su u memoriji računala te riječi. Pa neka mi to jako, vrlo jednostavan primjer. 

Ja ću ići naprijed i otvoriti jednostavan tekst programa, a ja ću stvoriti datoteka zove hello.c. Većina ovih informacija mi neće ići u vrlo detaljno, ali ja ću napisati Program u tom istom jeziku, C. To je daleko više zastrašujuće, Ja smatram, nego ispočetka, ali to je vrlo slično u duhu. U stvari, to kovrčava braces-- možete vrsta razmišljati o tome što sam upravo učinio što je ovaj. 

Učinimo to, zapravo. Kada zelena zastava pritisne, učinite sljedeće. Želim ispisati "pozdrav". Dakle, ovo je sada pseudokod. Ja sam vrsta zamućivanje linije. U C, taj jezik sam govori o, ova linija ispisa Pozdrav zapravo postaje "printf" s neke zagrade i zarez. 

No, to je točno ista ideja. I to vrlo razumljiv "Kad zelena zastava kliknuo" postaje mnogo više kompliciranih "int glavni nevažeće." A to stvarno nema mapiranje, tako Samo ću ignorirati to. No, vitičastim zagradama su poput zakrivljena slagalice kao što je ovaj. 

Dakle, možete vrsta pogoditi. Čak i ako ste nikada nije programiran prije, Što je ovaj program vjerojatno učiniti? Vjerojatno ispisuje pozdrav s uskličnikom. 

Tako ćemo pokušati. Idem da ga spasi. A to je, opet, vrlo stara škola okoliša. Ne mogu kliknuti, ne mogu povući. Moram upisati naredbe. Dakle, želim pokrenuti svoj program, tako da Možda ću to učiniti, kao što hello.c. To je datoteka trčao sam. Ali čekajte, Nedostaje mi korak. Što smo rekli je potrebno korak za jezik poput C? Ja sam upravo napisao izvora broj, ali što mi je potrebno? Da, treba mi prevodilac. Dakle, na moj Mac ovdje, imam Program pod nazivom GCC, GNU C prevodilac, koja mi omogućuje da to učinimo zaokret moj izvorni kod u, mi ćemo ga nazvati, Stroj kod. 

I vidim da, Ponovno, kao što slijedi, ovi su nula i one koje sam upravo izrađen od mog izvornog koda, sve nula i jedinica. A ako želim pokrenuti moj program-- se to dogodi da se zove a.out za Povijesna reasons-- "zdravo". Mogu ga pokrenuti ponovno. Bok bok bok. A čini se da se radi. 

No, to znači da je negdje u mom memorije računala su riječi h-e-l-l-o, uskličnik. I ispostavilo se, baš kao i na stranu, što računalo će obično učiniti tako da se zna gdje je stvari se počinju i end-- je će staviti poseban simbol ovdje. I Konvencija je staviti broj nula na kraju riječi tako da znate gdje se zapravo završava, tako da ne držati ispis više znakova nego što zapravo namjeravaju. 

Ali takeaway ovdje, čak iako je to prilično kompliciranih, je da je to u konačnici relativno jednostavan. Ti su dobili neku vrstu kasete, prazan Prostor na kojem možete pisati pisma. Vi jednostavno morate imati poseban simbol, kao što je samovoljno broj nula, staviti na kraju tvoje riječi tako da se računalo zna, oh, ja bi trebao prestati s ispisivanjem kad Vidim uskličnik. Budući da je sljedeća stvar tamo je ASCII vrijednost nula, ili nul znak kao netko bi to nazvao. No, tu je vrsta problema ovdje, i neka je vratiti brojeva za trenutak. Pretpostavimo da ja, u stvari, imaju niz brojeva, i pretpostavimo da je Program Pišem je kao razred knjiga za nastavnika i učitelja. I ovaj program mu ili joj omogućuje upisati rezultate svojih učenika na kvizovima. I pretpostavimo da je učenik dobiva 100 na njihov prvi kviz, možda kao 80 na sljedeći jedan, a zatim i 75, zatim 90 na četvrtom kvizu. 

Dakle, u ovom trenutku u priči, polje je veličine četiri. Ne postoji apsolutno više memorije u računalo, ali je polje, da tako kažemo, je veličine četiri. Pretpostavimo sada da učitelj želi dodijeliti peti kviz na klase. Pa, jedna od stvari koje je ili ona će morati učiniti Sada je pohraniti dodatnu vrijednost ovdje. No, ako je niz nastavnik ima stvorena u ovom programu je veličine za, jedan od problema s nizom je da ne možete samo držati dodajući da memorije. Jer, što ako drugi dio Program ima riječ "hej" upravo tamo? 

Drugim riječima, moja memorija može biti koristi se za ništa u programu. A ako unaprijed sam utipkao, hej, Želim ulaz četiri kviz rezultate, oni mogu ići ovdje i ovdje. A ako odjednom se predomislite kasnije i reći želim peti kviz rezultat, ne možeš samo stavi ga gdje god želite, jer što ako se to memorija se koristi nešto else-- neki drugi program ili neki drugi karakteristika programa da radite? Dakle, morate razmišljati unaprijed kako želite za pohranu podataka, jer sada ste slikano sebe u digitalni kutu. 

Dakle, učitelj možda umjesto kažu prilikom pisanja programa pohraniti njegov ili njezin razreda, znaš što? Ja ću tražiti, prilikom pisanja moj program, da želim nula, jedan, dva, tri, četiri, pet, šest, osam razreda ukupno. Dakle, jedan, dva, tri, četiri, pet, šest, sedam, osam. Nastavnik može samo preko dodijeliti memorije prilikom pisanja svoju programa i reći, znate što? Nikada neću dodijeliti više od osam kvizova u semestru. To je samo lud. Nikad neću izdvojiti to. Tako da je to način na koji on ili ona ima fleksibilnost za pohranu rezultatima učenika, kao što su 75, 90, a možda i jednim pomoćnim, gdje student dobio dodatni kredit, 105. 

Ali ako se nikad učitelj koristi ova tri mjesta, postoji intuitivno takeaway ovdje. On ili ona samo troši prostor. Dakle, drugim riječima, ima ova zajednički kompromis u programiranju gdje možete ili dodijeliti točno onoliko koliko memorije kao što želite, Naopako a to je da ste super efficient-- niste bude razoran na all-- ali je downside od kojih je što ako se predomislite kada pomoću programa koji želite pohraniti više podataka nego što ste namjeravali. 

Dakle, možda je rješenje, a onda, pisati svoje programe na takav način da oni koriste više memorije nego što je zapravo potrebno. Na taj način nećeš upasti u taj problem, ali ste se razoran. I više memorije vaš program koristi, kao što je objašnjeno jučer, manje memorije koja je dostupna za ostale programe, prije računalo može usporiti dolje zbog virtualne memorije. I tako idealno rješenje bi moglo biti što? 

Pod-dodjele izgleda loše. Over-alociranje izgleda loše. Dakle, ono što bi moglo biti bolje rješenje? Preraspodjelom. Budite dinamičniji. Ne silite sebe da odaberete priori, na početku, ono što želite. A sigurno ne pretjerano izdvojiti, da ne bude razoran. 

I tako bi se postigao taj cilj, morati baciti ove strukture podataka, da tako kažemo, daleko. I što programer obično će koristiti je nešto što ne zove Niz ali vezana lista. Drugim riječima, on ili ona će početi razmišljati o svojoj memoriji kao vrsta oblik koji im može privući na sljedeći način. Ako želim pohraniti jedan broj u program-- tako da je rujan, Ja sam dao moje studente kviz; Želim pohraniti studenata prvi kviz, a dobio 100 na it-- I. idem pitati moje računalo, putem programa sam pisano za jedan komad memorije. I ja ću pohraniti Broj 100 u njemu, i to je to. 

Tada je nekoliko tjedana kasnije a ja dobijem drugi kviz, i da je vrijeme da se upišete u tom 90%, ja odlazim pitati računalo, hej, računalo, mogu li dobiti još jedan komad memorije? To će mi dati taj prazan komad memorije. Idem staviti u broj 90, ali u svom programu nekako other-- i nećemo brinuti o sintaksa za učinimo, mi treba nekako lanac ove stvari zajedno. A ja ću ih lanac skupa s ono što izgleda kao strijela ovdje. 

Treći kviz koji dolazi, Ja ću reći, hej, računalo, daj mi još jedan komad memorije. I ja ću staviti dolje što god to bilo, kao što su 75, i moram lanac ovom zajedno sada nekako. Četvrto kviz dolazi zajedno, a možda to je prema kraju semestra. I tog trenutka moj program Možda korištenjem memorije posvuda, posvuda fizički. I tako samo za slatkiš, ja sam će privući ova naprijed quiz-- zaboravim što je bilo; ja da je možda 80 ili something-- način ovdje. 

No, to je u redu, jer je slikovito Idem izvući ovu liniju. Drugim riječima, u stvarnosti, u hardveru računala, Prvi rezultat možda završiti ovdje, jer to je odmah na početku semestra. Sljedeći moglo bi se završiti ovdje jer malo vremena je prošlo a program nastavlja raditi. Sljedeći rezultat, koji je bio 75, može biti ovdje. I posljednji rezultat bi mogao biti 80, što je ovdje. 

Dakle, u stvarnosti, fizički, to bi moglo biti što memorije računala izgleda. Ali ovo nije korisna mentalna paradigma za računalni programer. Zašto bi se brinete gdje je kritički vaši podaci će završiti? Vi samo želite spremiti podatke. 

To je vrsta kao što su naše rasprave prije crtanja kocku. Zašto te briga što je kut kocke i kako se okrenuti ga izvući? Vi samo želite kocku. Isto tako ovdje, Samo želim razred knjige. Vi samo želite razmišljati o ovo kao popis brojeva. Koga briga kako je to ugraditi u hardver? 

Tako je apstrakcija sada je ova slika ovdje. To je povezano popis, kao i programer bi to nazvao, ukoliko imate popis, očito brojeva. No, to je povezano u slikama putem ove strelice, i sve te strelice are-- ispod sjenilo, ako ste znatiželjni, Podsjetimo da je naš fizički hardverski ima adrese nula, jedan, dva, tri, četiri. Sve ove strijele su se kao karta ili upute, u kojem, ako 90 is-- sada Dobio sam brojati. 

Nula, jedan, dva, tri, četiri, pet, šest, sedam. To izgleda kao 90 na memorijska adresa broj sedam. Sve ove strijele su se kao mali komadić papira da je davanje smjera za program koji kaže da slijedite ove karte doći do položaja sedam. I tu ćete naći studenta drugi rezultat kviz. U međuvremenu, 75-- ako sam i dalje ovo, To je sedam, osam, devet, 10, 11, 12, 13, 14, 15. 

Ova druga strelica predstavlja samo mapa na memorijsku lokaciju 15. Ali opet, programer općenito ne ne brine o ovoj razini detalja. I u većini svakom programiranju Jezik danas, programer neće ni znati gdje je u memoriji ti brojevi su zapravo. Sve što on ili ona mora brinuti o je koji su na neki način povezani u strukture podataka kao što je ovaj. 

No, ispostavilo se ne da se previše tehnički. Ali samo zato što možda može priuštiti da imaju ovu raspravu ovdje, Pretpostavljam da smo ponovno ovo pitanje ovdje u polje. Da vidimo žalimo se ovdje događa. To je 100, 90, 75 i 80. 

Dopustite mi da ukratko bi ovu tvrdnju. To je niz, a opet, Istaknuta karakteristika niza je da sve svoje podatke je natrag natrag na leđa u memory-- doslovno jedan bajt ili možda četiri bajta, neki fiksni broj bajtova daleko. U povezanom popisu, koje smo mogli izvući ovako, ispod poklopca motora koji zna gdje je to stvar je? To ni ne treba da teče ovako. Neki podaci mogu biti natrag na lijevo gore. Vi ni ne znaju. 

I tako s nizom, imate značajka poznat kao slučajni pristup. A što Random Access sredstvo koje računalo može skočiti odmah na bilo koje mjesto u nizu. Zašto? Budući da računalo zna da je prva lokacija nula, jedan, dva, tri, 

I tako, ako želite ići od ovaj element na sljedeći element, doslovno, u računala um, samo dodati. Ako želite ići na treći element samo dodajte one-- sljedeći element, samo dodati. Međutim, u ovoj verziji priče, recimo računalo trenutno gleda na ili se bave s brojem 100. Kako ste dobili na sljedeću grade u knjizi razred? 

Morate uzeti sedam koraka, koji je proizvoljna. Da biste dobili na sljedeću, morate uzeti još osam koraka doći do 15 godina. Drugim riječima, to nije konstantan razmak između brojeva, pa to samo uzima Računalo više vremena je točka. Računalo mora tražiti kroz memoriju kako kako bi pronašli ono što tražite. 

Dakle, dok je niz teži da bude brzo podaci structure-- zbog vas doslovno može samo učiniti jednostavna aritmetička i dobili gdje želite dodavanjem jednog, za instance-- povezanog popisa, li žrtvovati tu značajku. Ne možeš samo otići iz prvog do drugog na treće mjesto na četvrtom mjestu. Morate slijediti kartu. Morate uzeti više koraka doći do tih vrijednosti, koje Čini se da se dodavanjem troškova. Tako smo plaćati cijenu, ali ono što je značajka koja je Dan traži ovdje? Što povezani popis očito nam omogućiti da učinite, koji je podrijetlo ova priča? 

Točno. Dinamična veličina na njega. Možemo dodati na ovaj popis. Možemo čak i smanjiti popis, tako da da smo samo pomoću što više memorije što mi zapravo želimo i tako mi smo nikad pretjerano dodjele. 

Sada samo da se stvarno NIT-izbirljiva, postoji skrivenih troškova. Tako da ne treba samo neka mi uvjeriti li da je to uvjerljiv kompromis. Postoji još jedan skriveni troškovi ovdje. Korist, da bude jasno, je da smo dobili dinamiku. Ako želim još jedan element, samo da mogu izvući ga i staviti broj u tamo. I onda ja to mogu povezati sa slikom ovdje dok je ovdje, opet, ako sam naslikao sebe u kut, ako je nešto drugo već koristi sjećanje ovdje, ja sam od sreće. Ja sam sebe naslikao u kutu. 

No, ono što je skriveno cijene na ovoj slici? To je ne samo iznos vremena koje je potrebno ići odavde do ovdje, što je sedam koraka, a zatim Osam koraka, što je više nego jednom. Što je još jedan skriveni troškovi? Ne samo vremena. Dodatne informacije potrebne za postizanje ovu sliku. 

Da, to karta, one malo komadići papir, kao što sam držati opisujući ih kao. To arrows-- oni nisu slobodni. Computer-- znaš što računalo ima. Ona ima nula i jedinica. Ako želite predstavlja strijelu, ili njegov map ili broj, trebate neke memorije. Dakle, s druge cijenu koju platiti za povezanu listu, zajednička računalna znanost resursa, je i prostor. 

I doista je tako, tako često, među tradeoffs u izradi softverskog inženjerstva sustava je vrijeme i space-- su dvije od svojih sastojaka, dva svojim najčešće skupih sastojaka. To je koštalo mi još vremena jer moram slijediti tu kartu, ali i košta me više prostora jer moram zadržati ovu kartu okolo. Tako je nada, jer mi smo vrsta raspravljalo tijekom jučerašnjeg dana i danas, je da su prednosti će prevagnuti troškove. 

Ali nema Očito rješenje ovdje. Možda je better-- la brz i prljav, kao Kareem predložio earlier-- baciti memorije na problem. Dovoljno je kupiti više memorije, mislim manje teško o rješavanju problema, i riješiti ga na lakši način. I doista ranije, kada razgovarali smo o tradeoffs, to nije bilo prostora u računalo i vrijeme. To je bio razvijen vrijeme, koje još je jedan izvor. 

Pa opet, to je ovaj čin balansiranja pokušavajući odlučiti koji od tih stvari ste spremni potrošiti? Koji je najjeftiniji? Koji daje bolje rezultate? Da? 

Doista. U tom slučaju, ako ste predstavlja brojeve u maps-- nazivaju se u mnogim jezicima "upućuje" ili "adrese" - to je dvostruko više prostora. To ne mora biti tako loše kao dvostruki ako sada mi samo spremanje brojeva. Pretpostavimo da smo spremanje zapisi o bolesnicima u hospital-- pa Piersonovu imena, telefonskih brojeva, brojevi socijalnog osiguranja, liječnik povijest. Ovaj okvir može biti puno, puno veći, u kojem slučaju maleni malo pokazivač, adresu sljedeći element-- to nije velika stvar. To je takva skuta košta to ne smeta. No, u ovom slučaju, da, to je udvostručenje. Dobro pitanje. 

Razgovarajmo o vremenu a malo konkretnije. Što je vrijeme izvršavanja traženja ovaj popis? Recimo ja sam htjela za pretraživanje kroz sve razrede studenata, a tu je n ocjene u ovoj strukturi podataka. Ovdje, također, možemo posuditi Vokabular ranije. To je linearna struktura podataka. 

Big O n je ono što je potrebno da se na kraju ove strukture podataka, whereas-- i nismo vidjeli ovo before-- niz vam daje ono što se naziva konstanta vrijeme, što znači korak ili dva koraka ili 10 steps-- ne smeta. To je fiksni broj. To nema nikakve veze s veličina polja. A razlog za to, opet, s izravnim pristupom. Računalo može samo odmah skok na drugo mjesto, jer oni su svi isti udaljenost od svega ostalog. Nema razmišljanja su uključeni. U redu. Dakle, ako mogu, neka me pokušaju slikati dvije konačne slike. Vrlo čest jedna poznata kao hash tablicu. Tako motivirati ovu raspravu, neka mi misliti o tome kako to učiniti. 

Pa kako o tome? Pretpostavimo da je problem želimo riješiti sada provodi se u dictionary-- pa cijela hrpa engleskih riječi ili bilo što drugo. A cilj je biti u mogućnosti odgovoriti Pitanja obliku je to riječ? Dakle, želite provesti čarolija provjeru, samo kao fizički rječnik da možete gledati stvari u. Recimo da su to učiniti s nizom. Mogao sam to učiniti. 

A valjda su riječi od jabuka a banana i dinja. I ne mogu se sjetiti voća koji počinju s D, tako da smo samo će imati tri plodova. Dakle, ovo je polje, a mi smo čuvanje svih tih riječi u ovom rječniku, kao polje. Pitanje je, dakle, koliko je ostalo možeš li čuvati te podatke? 

Pa, ja sam vrsta varanja ovdje, jer svaki od ovih slova u riječi stvarno pojedinac bajt. Dakle, ako sam stvarno htjela biti nit-izbirljiva, ja stvarno bi trebao se podijeli ovo gore u mnogo manji komadi memorije, i da bismo mogli učiniti upravo to. Ali ćemo naletjeti na isti problem kao i prije. Što ako, kao što je Merriam Webster ili Oxfordu radi svaki year-- dodaju riječi na dictionary-- mi ne nužno želite da se bojite u kut s polja? 

Umjesto toga, možda pametniji pristup je staviti jabuku u svom čvor ili kutiji, rekli bismo, banana, i onda ovdje imamo dinja. A mi niz ove stvari zajedno. Dakle, ovo je polje, a to je popis povezani. Ako ne možete baš vidjeti, to je samo kaže: "polje", a ovaj kaže: "popis". 

Dakle, imamo isti Točni pitanja kao i prije, pri čemu mi sada imamo dinamizam u našem povezanom popisu. No, imamo prilično sporo rječnika. Pretpostavimo da želim gledati ni riječi. To bi moglo potrajati mi veliku O n koraka, jer je riječ možda biti skroz na kraju popis, kao i dinja. I ispada da u programiranju, sortiranje Svetog grala podataka strukture, je nešto koji vam daje konstantan Vrijeme kao niz ali to još uvijek vam daje dinamiku. 

Tako možemo imati najbolje od oba svijeta? I doista, ima nešto naziva hash tablicu koji vam omogućuje da učinite upravo da, iako otprilike. Hash tablica je ljubitelj struktura podataka koje smo mogu misliti kako je Kombinacija array-- i ja ću ga izvući kao što učinimo i povezanim listama da ću nacrtati ovako ovdje. 

A način na koji je ova stvar Radovi se kako slijedi. Ako se to now-- hash table-- je moj treći struktura podataka, i želim se pohraniti riječi na to, ne znam žele samo pohraniti sve od riječi natrag na leđa na leđa na leđa. Želim iskoristiti neke podatak o riječima koje će pustiti ja ga dobiti gdje je brže. 

Dakle, s obzirom na riječi jabuku a banana i dinja, Namjerno sam izabrao te riječi. Zašto? Koja je vrsta temelja različito u tri? Što je očito? Počinju sa različitim slovima. 

Dakle, znate što? Umjesto da stavi sve svoje riječi u ista kanta, da tako kažemo, kao u jednoj velikoj listi, zašto ne Ja barem isprobati optimizaciju i da moji popisi 1/26 dokle. Uvjerljiv optimizacija možda zašto ne I-- prilikom umetanja riječi u ovu strukturu podataka, u memoriju računala, zašto ja ne staviti sve 'A' riječi ovdje, svi oznakom 'b' riječi ovdje, i sve 'c' riječi ovdje? Dakle, ovo završi stavljanjem jabuku Ovdje, banana ovdje, dinja ovdje i tako dalje. 

A ako imam dodatnih Riječ volimo-članovima što je još jedan? Apple, banana, kruška. Svatko misliti na plod koja počinje sa a, b, ili c? Blueberry-- savršen. To će završiti ovdje. I tako mi se čini da imaju marginalno bolje rješenje, jer sada ako želim u potrazi za jabuke, ja first-- ja ne samo roniti u moju strukture podataka. Ja ne zaroniti u memoriji mog računala. Prvi put sam, pogledajte prvo slovo. 

A to je ono što računalo znanstvenik će reći. Vi raspršiti u svoje strukture podataka. Vi uzmite ulaz, koji je u ovaj slučaj je riječ poput jabuke. Možete ga analizirati, gledajući prvo slovo u ovom slučaju, time se raspršivanja. Raspršivanja je opći pojam kojim uzmete nešto kao ulaz i proizvoditi neki izlaz. A izlaz u tome Slučaj je lokacija Želite li pretraživati, prvi mjesto, drugo mjesto, treće mjesto. Dakle, ulaz je jabuka, izlaz je na prvom mjestu. Ulaz je banana je Izlaz bi trebao biti drugi. Ulaz je dinja, izlaz bi trebao biti treći. Ulaz je borovnica je Izlaz bi trebao opet biti drugi. I to je ono što vam pomaže preuzeti prečaci kroz memoriju kako bi se na riječi ili podatke učinkovitije. 

Sada je to smanjuje naše vrijeme potencijalno po koliko je jedan od 26, jer ako pretpostavimo da vas imati što više "A" riječi kao što su "z" riječi kao "Q", odnosno koji zapravo nije realistic-- ti si idući u morati izvrtati preko određene slova alphabet-- ali to će biti inkrementalni pristup koji dopušta li doći do riječi mnogo brže. A u stvarnosti, sofisticirani Program je Googleova svijeta, Facebooks od svijet- oni će koristiti hash tablicu za puno različitih namjena. Ali, oni ne bi bili toliko naivan samo pogledajte prvo slovo u jabuke ili banane ili kruške ili dinja, jer kao što možete vidjeti to popisi još uvijek mogao dugo. 

I tako bi to moglo ipak biti neka vrsta od linear-- tako nekako sporo, kao i sa velikim O n da smo raspravljali ranije. Dakle, što je pravi dobar hash tablicu će do-- to će imati puno veću lepezu. I to će se koristiti mnogo više sofisticirane funkcije raspršivanja, tako da ne samo gledati na "a". Možda to izgleda na "a-p-p-l-e" i nekako pretvara tih pet slova u mjestu gdje Apple bi trebao biti pohranjen. Mi samo naivno koristi slovo "A" sama, jer je lijepo i jednostavno. 

No, hash tablicu u kraj, možete misliti u obliku kombinacije niz, od kojih je svaki ima povezanu listu koja je idealno treba biti što je moguće kraće. I to nije očito rješenje. U stvari, mnogo fino ugađanje da ide na ispod haube kada je provođenje ove vrste sofisticirane strukture podataka je ono što je pravo Duljina niza? Koji je pravi hash funkcija? Kako spremiti stvari u memoriji? 

Ali shvatili koliko brzo ova vrsta rasprave eskalirali, bilo tako daleko da je to vrsta od nad glavom u ovom trenutku, što dobro je. Ali počeli smo, podsjetimo, s uistinu nešto niske razine i elektronski. I tako opet je to Tema apstrakcije, gdje je nakon što počnete da se za gotovo, u redu, imam it-- postoji fizičke memorije, OK, shvaćam, svaki fizička lokacija ima adresu, U redu, ja sam ga dobio, mogu predstavljati te adrese kao arrows-- možete vrlo brzo početi imati više sofisticirane razgovore koje na kraju Čini se da nam omogućava za rješavanje problema kao što su tražili i sortiranje učinkovitije. I budite uvjereni, too-- jer mislim da to je najdublji smo otišli u neki tih CS tema proper-- smo učinjeno u dan i pol na to ukazati ono što bi mogli obično učiniti preko roku od osam tjedana u semestru. 

Bilo kakva pitanja o njima? Ne? U redu. Pa, zašto ne bismo pauzu tamo, započeti ručak nekoliko minuta ranije, nastaviti u samo oko sat vremena? A ja ću se vući malo s pitanjima. Onda ću morati otići potrajati nekoliko poziva ako je to u redu. Ja ću okrenuti na neku glazbu u međuvremenu, ali ručak bi trebao biti oko kutu.