DAVID Malan: V redu. Mi smo nazaj. Torej, v tem segmentu o programiranju, kaj Mislil sem, da bi naredil je mešanica stvari. Ena, narediti malo nečesa hands-on, čeprav z uporabo bolj igriv programiranje environment-- tisti, ki je demonstrativen od natanko vrste idej smo se pogovarjali o tem, ampak malo bolj formalno. Dva, pogled na nekatere bolj tehnične načine da bi programer dejansko rešiti težave, kot so, ki išče težave da smo pogledal, preden tudi bolj temeljito zanimiv problem razvrščanja. 

Pravkar smo prevzela od zaslužiti iti da je bila ta imenik razporejene, ampak da sam je pravzaprav nekakšen Težko problem z veliko različnih načinov za njegovo rešitev. Tako bomo uporabili kot ti razred težav Predstavnik stvari, lahko rešili na splošno. In potem bomo govorili pa v nekaterih podrobnostih, kaj so ti podatki structures-- luksuznih načinov kot povezanih seznamov in hash tabele in drevesa, ki programer bi dejansko uporabo in splošno uporabo na tabli slikati sliko o tem, kaj on ali ona predvideva za izvajanje nekatere kos programske opreme. 

Torej, kaj je naredil roke-na delu prvi. Torej le dobili svoje roke umazane s okolju imenovane scratch.mit.edu. To je orodje, ki ga uporabljamo V naši dodiplomski razredu. Čeprav je bilo načrtovano za otroke, stare 12 let in več, smo ga uporabili za up del tega zelo malo saj je lepo, zabavno grafični način učenja nekaj malega o programiranju. Torej glavo na tem URL-ju, kjer vas bi morali videti stran, prav takšen, in gredo naprej in kliknite Pridružite praske na zgornjem desnem kotu in izberite uporabniško ime in geslo in na koncu dobili sami account-- scratch.mit.edu. Mislil sem, da bi to uporabili kot priložnost najprej pokazati to. Vprašanje je prišel med odmorom o tem, kaj koda dejansko izgleda. In sva se pogovarjala med odmorom o C, v particular-- še zlasti nižja stopnja v starejšem jeziku. In sem naredil na hitro Google iskanje, da bi našli številko C za binarno iskanje, algoritem, ki smo uporablja za iskanje, da je telefonski imenik prej. To še posebej primer, seveda, ne išče telefonski imenik. Samo išče cel kup Številke v spominu računalnika. Ampak, če bi rad samo dobil vizualno občutek za kaj dejansko programiranje jezik Izgleda, da izgleda malo kaj takega. Torej, to je približno 20-plus, 30 ali tako vrstic kode, ampak pogovor smo so ob več kot premoru je o tem, kako to dejansko dobi morphed v ničel in enic in če ne moreš vrniti, da obdelavo in gredo iz ničel in enic nazaj na kodo. 

Žal, proces je tako transformativno da je veliko lažje reči kot narediti. Šel sem naprej in dejansko obrnil ta program, Binary Search, v ničel in enic s sprejetjem program, imenovan prevajalnik, da sem zgodi, da so tukaj prav na mojem Mac. In če pogledaš na zaslon tukaj, se posebej osredotoča na teh srednjih šest stolpcev le, boste videli samo ničle in narave. In to so ničle in tiste, ki sestaviti točno to iščejo program. 

In tako je vsak kos pet bitov, vsak bajt ničel in enic tukaj, predstavljajo nekaj navodil tipično znotraj računalnika. In v resnici, če ste slišali marketing slogan "Intel znotraj" - da, seveda, samo pomeni, da imate Intel CPU ali možganov notranjosti računalnika. In kaj to pomeni, da je CPU je da imate nabor ukazov, tako rekoč. 

Vsak CPU na svetu, veliko jih je Intel v teh dneh, razume končna Število navodil. In ta navodila so tako nizki ravni kot dodatek teh dveh številk skupaj, množijo teh dveh številk skupaj, premakniti ta podatek od tukaj tukaj v spomin, razen tega informacije tukaj, da tukaj v spomin, in tako forth-- tako zelo, zelo nizko raven, skoraj elektronske podrobnosti. Ampak s tistimi, matematična operacije skupaj s tem, kar smo razpravljali prej, upodobitev podatkov kot ničel in enic, lahko ste zgraditi vse da lahko računalnik storiti danes, ali je tekstovni, grafični, glasbene, ali kako drugače. 

Torej, to je zelo enostavno priti izgubil v plevela hitro. In tam je veliko sintaktične izzivi pri čemer, če bi najenostavnejši, neumna tipkarskih napak nič programa bo delo sploh. In tako namesto z uporabo jezik kot C zjutraj, Mislil sem, da bi bilo bolj zabavno dejansko ne nekaj bolj vizualna, ki medtem ko je namenjen za otroke je pravzaprav popolna manifestacija z dejansko programiranja language-- slučajno uporaba slik namesto besedila da predstavljajo te ideje. 

Torej, ko si res imeti račun na scratch.mit.edu, kliknite gumb Ustvari na vrhu levi strani. In bi morali videti okolje, kot tisti sem, da vidijo na mojem zaslonu tukaj. In bomo porabili le malo malo časa igrajo tukaj. Poglejmo, če ne moremo vsi rešiti nekatere Težave skupaj na naslednji način. 

Torej, kaj boste videli v tem environment-- in dejansko pusti me premor. Ali kdo ni tukaj? Ne tukaj? V REDU. Torej, naj omenim nekaj Značilnosti tega okolja. 

Torej v zgornjem levem kotu zaslona, ​​smo imajo stopnjo na praske, tako rekoč. Scratch ni le ime tega programskega jezika; to je tudi ime mačke, ki vidite privzeto tam v oranžni barvi. Je na odru, zato podobno kot sem opisal želva prej kot je z pravokotne bele okolje krovu. Ta mačke svet je omejena v celoti v ta pravokotnik do vrha tam. 

Medtem, na desni hand side tukaj, to je samo skripte prostora, nepopisan list, če bo. To je, če bomo napisali naši programi v samo trenutek. In gradnikov, ki jih mora uporabite za pisanje tega program-- sestavljanko kosov, če will-- so tistih, ki tukaj v sredini, in oni so razvrščeni s funkcionalnostjo. Tako, na primer, bom šel naprej in pokazati vsaj enega od njih. Bom, da gredo naprej in kliknite Nadzor kategorija do vrha. 

Torej, to so kategorije do vrha. Bom kliknite kategorijo upravljanje. Namesto tega bom kliknite Dogodki kategorija, zelo prvi up top. In, če bi želeli slediti skupaj tudi kot smo to naredili, ste zelo dobrodošli. Bom kliknite in povlecite to Prvi je, "ko je zelena zastava kliknili." In potem bom spusti samo približno na vrhu mojih praznih tablice. 

In kaj je lepo o Scratch je, da je to puzzle kos, ko prepletena z drugimi sestavljanke kosov, bo naredil dobesedno kaj ti kosov sestavljanke pravijo storiti. Tako, na primer, Scratch je prav Sedaj sredi njegovega sveta. Bom, da gredo naprej in izberite Zdaj, recimo, kategorija Predlog, Če želite, da storijo nam je isti Motion kategorijo. In zdaj opazili imam celoto kup koščke tukaj da, še enkrat, nekako to, kar pravijo. In bom, da gredo naprej in povlecite in spusti premikanje blok prav tukaj. 

In opazili, da se takoj, ko dobiš blizu dna "zeleno zastavo kliknili "gumb, obvestilo kako se pojavi bela črta, kot da je skoraj magnetna, želi iti tja. Samo izpustil in bo snap skupaj in bodo oblike ujemajo. In zdaj si lahko morda kmalu Verjetno kam gremo s tem. 

Če pogledaš v fazi Scratch sem in poglej na vrhu je, boste videli rdečo luč, stop znak in zeleno zastavo. In bom, da gredo naprej in gledal moje screen-- za trenutek, če bi lahko. Bom kliknite zeleno zastavo zdaj, in se je preselil, kar se zdi, da je 10 korakov ali 10 točk, 10 pik, na zaslonu. 

In zato ni to zanimivo, vendar naj predlaga ne da bi to poučevanje, samo uporabo lastnih svoje intuition-- Let jaz predlagam, da ugotovimo, kako da blok za sprehod pravico off fazi. So mu naredili prostor za desno stran zaslon, vse tja v desno. Naj vam trenutek ali tako boriti s tem. Morda boste želeli, da pogled na druge kategorije blokov. V redu. Torej, samo da povzamem, ko imamo zelena zastava kliknete tukaj in premikanje 10 korakov je samo navodila, vsakič, ko sem kliknite zeleno zastavo, kaj se dogaja? No, to je tekmovanje v teku svoj program. Tako sem lahko to naredil morda 10-krat ročno, vendar to meni malo bit hekerske, tako rekoč, pri čemer Nisem reševanju problema. Jaz sem samo enkrat poskušam in znova in znova in znova dokler sem nekako po naključju dosegli direktive da sem določeno, da se doseže prej. 

Vendar vemo iz naše psevdokoda prej, da obstaja ta pojem v programiranju petlji, tem znova in znova nekaj. In tako sem videl, da je kup vas dosegla za kaj puzzle kos? Ponavljajte, dokler. Tako smo lahko nekaj storiti kot ponavljati, dokler. In kaj si ponoviti, dokler točno? 

V REDU. In mi gredo z eno, ki je nekoliko enostavnejši za trenutek. Naj gredo naprej in to. Upoštevajte, da se boste morda morali odkrili pod nadzor, je to ponavljanje blok, ki ni videti, kot da je to velik. Tam ni veliko prostora v med tema dvema rumenimi črtami. Toda, kot nekateri od vas morda opazili, če ste povleci in spusti, opazili, kako raste zapolniti obliko. 

In lahko celo strpati več. To bo samo še naraščal, če povlečete in lebdijo nad njim. In ne vem, kaj je Najboljši tukaj, zato naj me vsaj ponovi petkrat, za primer, nato pa pojdite nazaj na oder in kliknite na zeleno zastavo. In sedaj opazili, da to ni čisto tam. 

Zdaj ste nekateri predlagani, Victoria ravno ni, ponovite 10-krat. In ki na splošno ne spraviti vso pot, vendar ne bi bilo treba bolj robusten Tako kot samovoljno ugotoviti koliko se premika narediti? Kaj bi lahko bil boljši blok kot ponovitev 10-krat? 

Ja, zakaj ne stori vedno kaj? In zdaj naj mi premakniti ta kos sestavljanke notri in se znebite tega. Zdaj opazili, ne glede na to kje Scratch začne, gre do roba. In na srečo MIT, ki naredi nič, samo poskrbi, da on nikoli popolnoma izgine. Vedno lahko zgrabi svoj rep. 

In samo intuitivno, zakaj je premikati? Kaj se dogaja tukaj? Zdi se, da so se ustavili, vendar potem, če sem se poberem in povlecite ga še naprej želijo, da gredo tja. Zakaj je tako? Resnično, računalnik je dobesedno bo to, kar je povedal, da storiti. Torej, če ste to povedali prej storijo naslednja stvar za vedno, gremo 10 korakov, to se dogaja, da se dogaja in bo dokler ne zadeti rdečo stop znak in zaustavitev programa v celoti. 

Torej, tudi če ni To naredite tako, da bi lahko, kako sem da Scratch potezo hitreje po zaslonu? Več korakov, kajne? Torej, namesto da delaš 10 v času, zakaj ne bi iti naprej in ga spremeniti to-- kaj bi propose-- 50? Torej, zdaj bom kliknite zeleno zastavo, in res, gre zelo hitro. 

In to je seveda samo manifestacija animacije. Kaj je animacija? To je samo prikazuje človeško a cel kup fotografij, res, zelo, zelo hitro. In zato, če smo pravkar povedali ga premakniti več korakov, smo le imajo učinek je, da Sprememba kje je na zaslonu vse hitreje na enota časa. 

Zdaj naslednji izziv, ki sem ga predlagal je, da so mu premetavati čez rob. In ne da bi vedel, kaj puzzle kosov exist-- ker je v redu Če ne boste dobili na faza challenge-- kaj hočeš narediti intuitivno? Kako bi morali ga Odklonijo nazaj in tja med levo in desno? 

Ja. Torej potrebujemo nekakšen stanja, in Zdi se, da imajo Pogojniki, tako rekoč, pod kategorijo nadzor. Kateri od teh blokov bomo verjetno želeli? Ja, mogoče ", če je, potem." Tako opazili, da med rumenih blokov imamo tukaj, je ta "če" ali to ", če še" blok, ki bo nam omogočajo, da bi odločitev, da to storijo ali za to. celo in lahko gnezdo narediti več stvari. Ali pa, če še niste šli tukaj, pojdi na kategorijo Sensing in-- da vidimo, če je tukaj. 

Torej, kaj blok bi bil lahko koristen tukaj odkriti, če je to z odra? Ja, opazili, da nekatere od teh blokov lahko parametriziramo, tako rekoč. Jih lahko nekako meri ne za razliko od HTML včeraj z atributi, kadar ti atributi vrste prilagodite obnašanje oznako. Prav tukaj, lahko zgrabi to dotikanje blok in spremembe in vprašati, ste dotika z miško Kazalec kot kazalca ali ste dotika rob? 

Torej me noter in to. Bom pomanjšati za trenutek. Naj zgrabi ta kos sestavljanke tukaj je to puzzle kos tem, in bom packarije jih za nekaj trenutkov. Bom premakniti to, spremeni to dotika roba, in bom gibanja to. Torej, tukaj je nekaj sestavin. Mislim, da imam vse, kar hočem. 

Bi kdo rad predlagal, kako mogoče povezati ti morda vrha do dna da bi rešili problem z Scratch premik od desne proti levi, da pravica do leve proti desne na levo, vsak Čas samo odbijajo steno? Kaj želite narediti? Kateri blok naj priključite na "Ko je zelena zastava kliknil prvi"? 

OK, začnimo z "večno". Kaj se dogaja v notranjosti sledi? Nekdo drug. OK, gremo korake. V redu. In kaj potem? Torej if. In opazil, čeprav je videti stisnjena skupaj tesno, to bo samo rasla izpolniti. To bo samo skoči, kje sem ga želim. 

In kaj sem dal med if in potem? Verjetno ", če se dotika roba." In obvestilo, še enkrat, to je prevelika za njo, vendar se bo hkrati izpolniti. Nato pa 15 stopinj? Koliko stopinj? Ja, 180 se vrti me vse ravno obratno. Torej, da vidimo, če imam to pravico. Naj pomanjšavo. 

Naj povlecite blok za ukrepanje. Tako je malo popačena zdaj, ampak to je v redu. Kako naj ga ponastaviti enostavno? Bom malo goljufati. Tako da sem dodal še eno blok, samo da bo jasno. Hočem, da točka 90 stopinj na desni privzeto, tako da sem le, da bo mu povedati za to programsko. In gremo. Zdi se, da smo to naredili. To je malo čudno, ker on hodi z glavo navzdol. Recimo, da je hrošč. To je napaka. Bug je napaka v programu, a logične napake, da sem človek, ki. Zakaj se dogaja narobe? Ali MIT zajebal, ali sem? 

Ja, mislim, da ni MIT je napake. Dali so mi kos sestavljanke ki pravi, da zavrtite nekaj stopinj. In na predlog Victoria, Jaz obrača za 180 stopinj, ki je prav intuicija. Toda obrača za 180 stopinj dobesedno pomeni obrača za 180 stopinj, in to ni res kaj hočem, očitno. Ker vsaj, da je v Ta dvodimenzionalni svet, tako struženje se v resnici dogaja da ga flip na glavo. 

Verjetno želite uporabiti kakšen blok namesto tega, glede na to, kar vidite tu? Kako bi lahko to popravimo? Ja, tako da bi lahko kazal v obratni smeri. In pravzaprav tudi, da je ne bo dovolj, saj lahko le težko koda da kaže levo ali desno. 

Veš, kaj lahko naredimo? Izgleda, da imamo udobje blok tukaj. Če bi povečavo, glej nekaj, kar je všeč tukaj? Torej izgleda, da ima MIT abstrakcija zgradili tukaj. Zdi se, da je enakovredna Ta blok na kateri drugi bloki, množina? 

Zdi se, da je enakovredna tale blok s tem celotno trio blokov da imamo tukaj. Tako se izkaže, da sem lahko poenostavi moje Program, ki ga znebi vseh, ki in samo da to tukaj. In zdaj je še vedno malo Otroški voziček, in to je v redu za zdaj. Bomo pustimo, da se. Ampak moj program je celo enostavnejši in tudi to, bi bil predstavnik za zadetek v programming-- je idealno, da kodo kot preprost, kot kompaktna kot je mogoče, pri čemer pa so, kot je berljivi kot je mogoče. Vi ne želite, da bi bilo tako jedrnat da je težko razumeti. 

Ampak opazil sem zamenjati tri bloke z enim, in to je verjetno dobra stvar. Sem odvzete stran pojem preverjanja, ali ste na robu z enim blokom. Zdaj pa se lahko zabavajo s tem, v resnici. To ne doda toliko intelektualno vrednost, vendar igriv vrednost. Bom, da gredo naprej in zgrabi ta zvok tukaj. Torej naj grem naprej, in naj me zaustavitev programa za trenutek. Bom za snemanje naslednje, omogoča dostop do mojega mikrofona. 

Gremo. Auč. Pa poskusimo znova. Gremo. OK, sem posnel napačno stvar. Gremo. Auč. Auč. V redu. Zdaj se moram znebiti tega. V redu. 

Zdaj imam Snemanje samo "Ouch." Torej, zdaj bom šel naprej in pravijo temu "av". Bom šel nazaj za moje skripte, in zdaj Obvestilo pa je to blok, ki se imenuje predvajanje zvoka "mijav" ali predvajanje zvoka "av". Bom vleči to, in kje naj dajo to za komični učinek? Ja, zdaj je vrsta Otroški voziček, ker zdaj to block-- opaziti, kako to ", če na robu, bounce "je nekako samostojen. Torej moram popraviti to. Naj gredo naprej in to. Naj se znebite tega in nazaj za naše izvirniku, bolj premišljeno funkcionalnost. Torej, "če se dotika roba, nato pa" hočem vrteti, kot je predlagano Victoria, 180 stopinj. In ne želim igrati zvok "au" tam? 

Ja, opazili, da je zunaj da rumena blok. Torej tudi to bi bilo napako, vendar sem jo opazil. Tako bom, da ga povlečete tukaj, in obvestilo zdaj je znotraj "če". Torej "če" je to neke iz podobnega roke podobnih blot da bo le to, kar je znotraj njega. Torej, zdaj, če sem pomanjšati na tveganje annoying-- 

COMPUTER: Au, au, au. 

DAVID Malan: In bo le večno. Zdaj pa samo, da pospeši stvari sem, naj gredo naprej in odprli, kaj je say-- Naj gre za nekaj moje stvari iz razreda. In mi odprla, recimo, to ena je eden od naših učnih štipendistov nekaj let nazaj. Torej, nekateri od vas morda odpoklic ta igra iz minulih dni, in to je dejansko izjemen. Čeprav smo storili Najenostavnejši programov sedaj, kaj je razmisliti, kaj je to dejansko izgleda. Naj hit igro. 

Torej, v tej igri, imamo žaba, in z uporabo puščico keys-- je potrebno večje korake, kot sem remember-- Imam nadzor nad tem žaba. In cilj je priti čez zaseden cesta ne teče v avtomobile. In kaj je see-- če grem tukaj sem morali počakati log, da se premaknete s. To počuti kot hrošč. To je neke vrste hrošča. V redu. Jaz sem na to tukaj, tam, potem pa naprej bo, dokler ne dobiš vse žabe na lilije blazinice. Zdaj to lahko videti vse bolj zapletena, ampak poskusimo prodreti to dol duševno in ustno v svojih blokih. Torej je verjetno puzzle kos, ki ga še nismo videli ampak to je odziv na pritiske tipk, za stvari, ki sem udaril po tipkovnici. 

Torej je verjetno nekakšna blok, ki pravi, če ključ enaka navzgor, naredite nekaj z Scratch-- Mogoče je premakniti 10 korakov na ta način. Če je pritisnjena tipka, premaknite 10 korakov na ta način, ali levo tipko, premakne 10 korakov na ta način, 10 korakov, ki. Sem jasno obrnil mačka v žabo. Torej, to je samo, če kostum, kot Scratch klici it-- smo samo uvozili sliko žabe. 

Toda, kaj se dogaja? Katera druga vrstic kode, kaj drugi kosov sestavljanke storil Blake, naše poučevanje kolegi, uporabo v tem programu, očitno? Kaj je tako vse move-- kaj programiranje konstrukt? 

Predlog, sure-- tako premakniti blok, zagotovo. In kaj je to poteza blok notranjosti, najverjetneje? Ja, neke vrste zanke, morda vedno blokira, morda ponovitev block-- ponovite do bloka. In to je tisto, kar bi dnevnike in lilija blazinice in vse ostalo poteza naprej in nazaj. To je samo dogaja v nedogled. 

Zakaj so nekateri avtomobili gibljejo hitreje od drugih? Kaj je drugačnega teh programov? Ja, verjetno nekateri od njih so ob več korakov naenkrat in nekateri od njih manj korakov naenkrat. In vizualni učinek hitro v primerjavi s počasno. 

Kaj misliš, da se je zgodilo? Ko sem dobil žabo vso pot čez cesto in reko na lilija pad, nekaj Omembe vredno je zgodilo. Kaj se je zgodilo takoj, ko sem to naredil? Ustavil se je. Da žaba prekiniti in Imam drugo žabo. Kaj konstrukt mora biti tam uporabljajo, kaj funkcija? 

Ja, tako da je nekakšna "Če" pogojujejo tam, preveč. In se izkaže out-- nismo videli this-- vendar pa druge bloke v tam, da Lahko rečem, če ste dotika še ena stvar, na zaslonu, če ste se dotikajo lilija pad, "potem". In potem, da je, ko smo da se bodo drugi žaba. Torej, čeprav je ta igra zagotovo zelo dne, čeprav je na prvi pogled tam je tudi veliko dogaja on-- in Blake ni bič to v dveh minutah verjetno je on več ur ustvariti to igro temelji na njegovem spominu ali video posnetkov različice minulih dni je od tega. Toda vse te malenkosti bo na zaslonu v izolaciji omejijo na te zelo preprosta constructs-- gibi ali izjave kot smo razpravljali, zank in pogoji, in to je približno to. Obstaja še nekaj drugih luksuznih funkcij. Nekateri od njih so povsem estetsko ali akustično, kot zvokov sem igral z. Toda za večino del, ki jih imajo v tem jeziku, Scratch, vsi temeljni gradnikov, ki vas imajo v C, Java, JavaScript, PHP, Ruby, Python, in poljubno število drugih jezikov. Vsa vprašanja o nič? V redu. Torej ne bomo potopite globlje praske, čeprav ste dobrodošli, ta vikend, še posebej, če imate otroke ali nečakinje in nečaki in podobno, jih seznaniti z Scratch. To je pravzaprav čudovito igriv okolje z, kot pravijo njegovi avtorji, zelo visokim stropom. Čeprav smo začeli z zelo podrobnosti nizko stopnjo, lahko res zelo malo z njo, in to je morda dokaz točno to. 

Ampak kaj je zdaj prehod v nekaj več sofisticirane težave, če hočete, poznan kot "iskanje" in "Razvrščanje", bolj na splošno. Imeli smo ta imenik earlier-- tukaj še ena samo za discussion-- da smo lahko iskanje učinkoviteje ker znatnega predpostavke. In samo zato, da bo jasno, kaj predpostavka, sem bil kar Pri iskanju po tem imeniku? To je bil Mike Smith v telefonski imenik, čeprav I bi bila sposobna izpeljati scenarij brez njega tam, če sem ustavil predčasno. Knjiga je po abecedi. In to je zelo radodaren predpostavka, ker je pomeni someone-- sem nekako rezanja kotiček, kot da sem hitrejši, ker nekdo drug naredil veliko trdega dela za mene. 

Kaj pa, če je telefon knjige so bile Nerazvrščene? Mogoče Verizon dobil leni, samo vrgel imen in številk vsakogar tam morda v vrstnem redu, v katerem so prijavili za telefonske storitve. In koliko časa traja, me da bi našli nekoga, kot je Mike Smith? 1.000 strani telefona book-- koliko Strani moram gledati skozi? 

Vse. Ti si nekako od sreče. Vi dobesedno gledati vsak Stran če imenik je samo naključno razporejene. Morda boste imeli srečo in našli Mike na zelo prvi strani, ker on je bil prvi naročnik naročiti telefonsko storitev. Vendar bi lahko bil zadnji, preveč. 

Torej naključno da ni dobro. Torej, da imamo za razvrstite imenik ali v splošnih podatkov sort ki ste nam bili dana. Kako lahko to storimo? 

No, naj le poskusite enostaven primer tukaj. Naj gredo naprej in kretnjo Nekaj ​​številke na krovu. Recimo, da številke, ki jih imamo, so recimo, štiri, dva, ena in tri. In, Ben, rešiti te številke za nas. 

OK, dobro. Kako si to naredil? V redu. Torej začnite z najmanjšim vrednost in najvišjo, in to je res dobro intuicijo. In zavedati, da smo ljudje so dejansko precej dobri v reševanju problemov kot je ta, vsaj ko je podatkovna relativno majhna. Takoj, ko začnete na stotine številk, na tisoče številk, milijone številk, Ben verjetno to ne bi mogel storiti prav tako hitro, ob predpostavki, da je bilo razlike v številu. Zelo enostavno, da računajo na milijon sicer pa porabijo le čas. 

Torej algoritem se sliši kot Ben uporablja šele zdaj je iskanje najmanjšim številom. Torej, čeprav mi lahko ljudje sprejmejo V veliko informacij vizualno, računalnik dejansko malo bolj omejen. Računalnik lahko samo poglej enega bita naenkrat ali morda štiri bajte na time-- v teh dneh morda 8 bajtov na time-- vendar zelo majhno število bajtov v določenem času. 

Torej, glede na to, moramo res štirje ločeni vrednosti here-- in lahko si misliš, Ben, da ima senčila za, če bi bil računalnik kot da ne vidim ničesar drugega kot eno številko pri time-- zato smo na splošno bo prevzel, kot v Angleščina, bomo prebrali od desne proti levi. Torej prva številka Ben verjetno pogledal je bil štiri in nato zelo hitro spoznal, da je precej velik number-- mi iščite naprej. 

Tam je dva. Počakaj minuto. Dva manjša od štiri. Grem, da se spomnimo. Dva je sedaj najmanjši. Zdaj one--, da je še boljši. To je še manjši. Bom pozabil približno dva in zapomni si zdaj. 

In bi lahko nehali iskati? No, vendar je bil na podlagi na te informacije, vendar je bolje, iskanje preostanek seznama. Ker kaj če nič je bilo na seznamu? Kaj pa, če so bili negativni ena na seznamu? On ve, da je njegov odgovor je pravilna, če je to izčrpno preverili celoten seznam. Tako gledamo na preostanek tega. Three--, da je izguba časa. Dobil sreče, vendar sem bil Še vedno pravi, da to storijo. In zdaj je verjetno izbrali najmanjše število in samo da na začetku seznama, ker bom naredil tukaj. Zdaj, kaj si naredil zraven, čeprav si ne mislim o tem skoraj do te mere? Ponovite postopek, tako neke vrste zanke. Tam je znana ideja. Torej, tukaj je štiri. To je trenutno najmanjša. To je kandidat. Ne več. Zdaj sem videl dva. To je naslednji najmanjši element. Three-- ki ni manjši, tako Zdaj Ben lahko izderi dva. 

In zdaj smo ponovite postopek, in Seveda treh gets potegnil naprej. Ponovite postopek. Štiri gets potegnil ven. In zdaj smo iz številk, tako da je seznam mora biti urejeno. 

In res, to je formalno algoritem. Računalniški znanstvenik bi Takšno "izbiro vrste," ideja pa neke Seznam iteratively-- znova in spet izbiro najmanjše število. In kaj je lepo, pa je to je samo tako darn intuitivno. To je tako enostavno. In lahko ponovite isti spet in spet operacija. To je enostavno. 

V tem primeru je bilo hitro, vendar kako dolgo je pravzaprav trajalo? Recimo, da se zdi, in počutim malo bolj dolgočasno. Torej ena, dva, tri, štiri, pet šest, sedem, osem, devet, 10, 11, 12, 13, 14, 15, 16-- poljubna številka. Hotela sem več to Čas kot le štiri. Torej, če imam celoto kup številk je now-- sploh ni pomembno kaj are-- Oglejmo razmišljati o tem, kaj je to Algoritem je res všeč. 

Recimo, da so številke tam. Še enkrat, ni pomembno, kaj so, ampak oni so naključno. Prijavljam Ben je algoritem. Moram izbrati najmanjše število. Kaj naj naredim? In bom fizično storiti je to čas, da to deluje ven. Če pogledamo, je videti, išče, išče, išče. Šele ko sem dobil, da Konec seznama lahko Zavedam se, najmanjši Številka je dva tokrat. One ni na seznamu. Zato sem odložil dva. 

Kaj naj storim zdaj? Če pogledamo, je videti, videti, videti. Sedaj sem našel številko sedem, saj tam je razlike v teh numbers-- ampak samo arbitrarno. V redu. Sedaj sem lahko odložil sedem. Če pogledamo v prihodnost, je videti. 

Zdaj sem ob predpostavki, od Seveda, da Ben ne imajo dodaten RAM, extra pomnilnika, saj seveda Gledam isto številko. Gotovo bi lahko sem se spomnil vse te številke, in to je popolnoma res. Ampak, če Ben spomni vse številk je videl, on je res ni postavil temeljni napredek ker je že sposobnost za iskanje s številkami na krovu. Spomin na vse Številke ne pomaga, ker je lahko še vedno kot računalnik samo poglej, da smo omenjeno, eno številko ob času. Tako da ni neke vrste goljufija tam, da lahko izkoristite. 

Torej v resnici, kot sem naprej iskati seznam, Sem dobesedno samo nadaljuj naprej in nazaj skozi njo, skubljenje ven naslednjo manjšo številko. In kot lahko nekako sklepati iz mojih neumnih gibanja, to samo postane zelo zamudno zelo hitro, in mi zdi, da se vrača in naprej, naprej in nazaj zelo malo. Zdaj bi bilo pošteno, da ne bi bilo treba iti čisto tako, no, see-- biti pošten, Nimam dokaj hoditi toliko korakov vsak čas. Ker je seveda, ko sem izberite številke iz seznama, preostali seznam je vedno krajši. 

In tako da je razmišljati o koliko korakov sem dejansko traipsing skozi vsak čas. V prvem položaju smo imeli 16 številk, in tako maximally-- jev naj samo To storite za discussion-- Sem moral pogledati skozi 16 številke, da bi našli najmanjši. Ampak, ko sem potegnil najmanjše število, kako dolgo je preostalo seznam, seveda? Samo 15. Torej, koliko številke storil Ben, ali imam odmisliti drugič naokoli? 15, samo, da gredo in najti najmanjši. Toda zdaj, seveda, seznam, Tudi manjše, kot je bilo prej. Torej, koliko korakov sem morali naslednjič? 14 in 13, nato pa 12 plus pika, dot, dot, dokler ne bom ostal samo eden. Zdaj bi računalniški znanstvenik vprašati, dobro, kaj počne, da so vsi enaki? To dejansko enaka nekaj konkretnega število, ki smo lahko zagotovo narediti računsko, vendar želimo govoriti o učinkovitosti algoritmov malo bolj formulaically, neodvisna, kako dolgo je seznam. 

In tako da boste vedeli, kaj? To je 16, ampak kot sem rekel prej, kaj je samo pokličite na velikost problema n, kjer je n nekaj številka. Mogoče je 16, morda je tri, morda je milijon. Nevem. Me ne zanima. Kaj si res želim, je formula, da sem lahko uporabljajo za primerjavo ta algoritem v primerjavi z drugimi algoritmi da bi nekdo trdijo bolje ali slabše. 

Tako se je izkazalo, in sem samo vem, to je osnovni šoli, da to dejansko deluje ven enaka stvar kot n nad n plus ena več kot dve. In to se zgodi, da bo enak, od Seveda, n kvadrat plus n več kot dva. Torej, če sem hotel formulo za koliko korakov so sodelovali pri iskanju sploh od znova in znova te številke in znova in znova, bi rekel to je n na kvadrat plus n več kot dva. Ampak veš kaj? To samo izgleda grdo. Pravkar sem res želijo splošni občutek stvari. In morda spomnite iz visoka šola, ki je je pojem najvišjega izraza naročila. Kateri od teh pogojev, n kvadrat, N, ali polovico, ima največji vpliv skozi čas? Večji n bolnikih, ki teh zadev je najbolj? 

Z drugimi besedami, če priključim na milijon, n kvadrat se bo najverjetneje prevladujoči faktor, ker je milijon krat Sama je veliko večja kot plus eno dodatno milijonov. Torej, veste kaj? To je tako darn velik številko, če kvadratni številko. To sploh ni pomembno. Mi smo le, da bo predložek, ki ven in pozabi. In tako bi bil računalniški znanstvenik reči da je za učinkovitost tega algoritma je reda n squared-- Mislim resnično približevanje. To je neke vrste grobo n kvadrat. Sčasoma, večji in večji n postane ta je dobra ocena za kaj učinkovitost ali pomanjkanje učinkovitosti tega algoritma v resnici. In sem izhaja, da seveda od dejansko delaš math. Ampak zdaj sem samo mahal moje roke, ker sem pravkar želijo splošni smisel tega algoritma. 

Torej, z uporabo iste logike, medtem, kaj menijo drugi algoritem smo že pogledal at-- linearno iskanje. Ko sem iskal za telefonsko book-- ne razvrščanje, iskanje prek telefonske book-- smo ohranili pravi, da je bilo 1.000 korakov ali 500 korakov. Ampak kaj je posploševati, da je. Če je n strani v telefonski imenik, kar je čas teče ali Učinkovitost linearne iskanju? Je o vrstnem redu koliko korakov, da bi našli Mike Smith z linearno iskanja, Prvi algoritem, niti drugega? 

V najslabšem primeru, Mike na koncu knjige. Torej, če je imenik 1.000 strani, smo rekli zadnjič, v najslabšem primeru, to lahko traja približno kako veliko strani, da bi našli Mike? Like 1.000. To je zgornja meja. To je najslabši možni položaj. Ampak še enkrat, smo se oddaljuje od številk kot 1.000 zdaj. To je samo n. 

Torej, kaj je logičen zaključek? Iskanje Mike v telefonu knjiga, ki ima n strani lahko traja, v zelo najslabšem primeru, koliko korakov na reda n? In seveda računalnik znanstvenik bi rekel da je čas, ki teče, ali uspešnosti ali učinkovitosti ali neučinkovitost, z algoritmom, kot je linearna iskanje je reda n. In lahko uporablja isti Logika prehodu nekaj iz kot sem naredil drugo Algoritem smo imeli z imenika, kjer smo šli dve strani naenkrat. 

Torej 1000 stran imenika morda da nas 500 stran obrne, plus ena če bomo podvojili malo nazaj. Torej, če ima telefonski imenik n strani, vendar delamo dve strani naenkrat, to je približno kaj? N čez dva, tako da je kot n več kot dva. Ampak sem zahtevka a Trenutek nazaj, da n nad dvo To je nekako isto kot le n. To je samo konstanten faktor, računalniški znanstveniki, bi rekli. Osredotočimo se le na spremenljivke, really-- največji spremenljivke v enačbi. 

Torej linearno iskanje, ali narediti eno Stran naenkrat ali dve strani naenkrat, je nekako v osnovi enaka. To je še vedno v redu n. Ampak sem trdil, z mojo sliko prej da tretja algoritem ni bilo linearna. To ni bil ravno črto. To je bil, da je ukrivljena linija, in algebraična enačba je bilo kaj? Dnevnik N- tako logaritem dva n. In mi ne bi bilo treba iti v preveč veliko podrobnosti o logaritmov danes vendar je večina računalniški znanstveniki ne bi tudi povedal, kaj je baza. Ker je vse samo stalnih dejavnikov, tako rekoč, le manjše numerične razlike. In tako bi bilo to zelo pogost način, zlasti formalno računalnik znanstveniki na desko ali programerji na belo ploščo dejansko trdi, ki algoritem, ki bi jih uporabili ali kaj učinkovitost za njihov algoritem. 

In to ni nujno nekaj ste razpravljali v vsakem zelo podrobno, ampak dober programer je nekdo ki ima trdno, formalno ozadje. On je sposoben govoriti z vi v tovrstni način in dejansko narediti kvalitativne argumente zakaj en algoritem ali en kos programske opreme je boljše, na nek način v drugo. Ker si lahko zagotovo samo izvajanje programa za ene osebe in štetje števila sekund je potrebno rešiti nekaj številk, in lahko teče nekaj Program druge osebe in štetje števila sekund je potrebno. Ampak to je bolj splošen način, da lahko uporabite za analizo algoritmov, če hočete, samo na papir ali samo verbalno. Brez celo vožnjo, ne da bi celo poskuša vzorčne vložkov, lahko samo razum skozi to. In tako z najemom razvijalec ali če ob mu ali ji nekako trdijo, da vas zakaj njihova algoritem, njihova skrivnost omaka za iskanje milijarde spletnih strani za vaše Družba je bolje, ti so vrste argumente, ki jih naj bodo sposobni narediti. Ali vsaj gre vrste stvari, da bi prišel v razpravo, na vsaj v zelo formalno razpravo. V redu. Torej Ben predlagala nekaj imenuje izbor vrste. Ampak bom predlagala, da obstaja drugih načinov za to, preveč. Kaj mi ni res všeč o Benova algoritem je, da je ohranil hojo, ali ko sem hodil, sem in tja ter naprej in nazaj in naprej in nazaj. Kaj če bi namesto da bi naredil nekaj podobnega te številke tukaj in jaz bi samo ukvarjati z vsako številka pa, kot sem jo dal? 

Z drugimi besedami, tukaj je moj seznam številk. Štiri ena, tri, dva. In bom naredil naslednje. Bom vstaviti številke kamor sodijo precej kot jih izbiro enega naenkrat. Z drugimi besedami, tu je številka štiri. 

Tukaj je moj prvotni seznam. In bom, da se ohrani v bistvu nov seznam tukaj. To je torej stara seznam. To je novi seznam. Vidim, da se je število štiri prva. Moja Nov seznam je na začetku prazna, zato je trivially drži da se štirje zdaj urejene seznam. Jaz sem samo pokazal številko sem dano, in sem ga je dala v mojem novem seznamu. 

Je to nov seznam razporejene? Ja. To je neumno, ker tam je samo ena element, vendar je popolnoma urejeno. Nič ni na pravem mestu. To je bolj zanimivo, ta algoritem, ko sem se premaknete na naslednji korak. 

Zdaj imam enega. Torej on, seveda, spada v začetek ali konec tega novega seznama? Začetek. Tako da sem moral narediti nekaj dela zdaj. Sem bil ob nekaj svoboščine z mojim označevalec s samo pripravo stvari kjer jih hočem, vendar to ni res točna v računalniku. Računalnik, kot vemo, je RAM ali Random Access Memory, in to je en bajt in en bajt in en bajt. In če imate GB RAM, imate milijardo bajtov, ampak oni so fizično na enem mestu. Ne moreš premikati stvari okoli tako, da ga pripravi na krovu kjerkoli hočeš. Torej, če ima moj nov seznam štiri lokacije v pomnilniku, žal štirih je že na napačnem mestu. 

Torej, da vstavite številko ena Ne morem ga pripraviti tukaj. Ta pomnilnik ne obstaja. To bi bilo goljufanje, in sem bil varanje slikovno nekaj minut tukaj. Torej res, če želim postaviti enega tukaj, Moram začasno kopirati štiri in potem dal eno tam. 

To je v redu, da je pravilna, da je to tehnično izvedljivo, vendar spoznali, da je dodatno delo. Nisem samo to število v mestu. Sem moral najprej premaknete številko, nato pa ga na mestu, zato sem nekako podvojila svoj obseg dela. Tako da se vodijo v mislih. 

Ampak jaz sem zdaj naredil s tem elementom. Zdaj hočem, da zgrabite številko tri. Kjer seveda ne pripada? Vmes. Ne morem goljufija več in to samo da tam, ker, spet, ta spomin je v fizičnih lokacijah. Tako da sem moral kopirati štiri in dal tri tukaj. Ni nič takega. To je samo en dodaten korak again-- se počuti zelo poceni. 

Sedaj pa pojdite na obeh. Sta seveda pripada tukaj. Zdaj boste videli, kako Delo lahko kopičijo. Zdaj, kaj moram storiti? Ja, moram premakniti štiri, potem moram kopirati tri, in zdaj sem lahko vstavite dva. In ulov s tem algoritem, dovolj zanimivo, je to da imamo bolj ekstremni primer, kjer je recimo osem, sedem, šest, pet, štiri, tri, dve, ena. To je v številnih kontekstih, najslabšem primeru, ker je darn stvar je dobesedno nazaj. 

To pa ni res vplivajo Ben je algoritem, ker pri izbiri Benova vrsta se dogaja, da gre naprej in nazaj po seznamu. In ker je bil vedno iščejo preko celotnega preostalega seznama ni pomembno kjer so elementi. Toda v tem primeru z mojim vstavljanje approach-- poskusimo to. 

Torej ena, dva, tri, štiri, pet, šest, sedem, osem. Ena dve tri Štiri, pet, šest, sedem, osem. Bom vzeti osem, in kje sem ga dal? No, na začetku mojega seznama, ker ta novi Seznam je razvrščen. In sem prečkati to. 

Kam je sedem? Presneto. To mora iti tja, tako Moram narediti nekaj kopiranje. In sedaj sedem gre tukaj. Zdaj pa pojdite na šest. Zdaj je še več dela. 

Osem mora iti tukaj. Sedem mora iti tukaj. Zdaj šest more iti tukaj. Zdaj pa zgrabi pet. Zdaj osem mora iti tukaj, sedem mora iti tu, šest mora iti tu in zdaj pet in ponovite. In sem precej premikanjem ves čas. 

Torej, na koncu pa je to algorithm-- bomo pravijo vstavljanje sort-- dejansko Ima veliko dela, preveč. To je samo drugačen način dela kot Ben-jev. Delo Benova imel me bo in nazaj ves čas, izberete naslednjo manjšo znova in znova element. Tako da je bilo to zelo vizualni način dela. 

Ta drugi algoritem, ki je še vedno correct-- bo dobil delo done-- Samo spremeni količino dela. Videti je, da na začetku, da si prihranek, saj si samo ki se ukvarjajo z vsakim elementom spredaj brez hojo vse pot po seznamu, kot so Ben je bil. Ampak problem je, še posebej v teh nori primeri, v katerih je vse nazaj, ste le nekako preložitev trdo delo dokler ne boste morali popraviti svoje napake. 

In tako, če si lahko to predstavljate osem in sedem in šest in pet kasneje pa štiri in tri in dva premika svojo pot po seznamu, smo pravkar spremenila vrsta dela delamo. Namesto, da delaš na začetek mojega ponovitev, Jaz samo delam Na konec vsake iteracije. Tako se izkaže, da ta algoritem, Tudi na splošno se imenuje vstavljanje razvrščanje, je tudi na vrstni red n razčetverjen. To je pravzaprav nič boljši, Ni boljšega sploh. 

Vendar pa je tretji pristop Rad bi nas spodbujajo, da razmisli, ki je to. Torej predvidevam svoj seznam, zaradi enostavnosti Ponovno je štiri, ena, tri, dvo le štiri številke. Ben je imel dobro intuicijo, dobra človeška intuicija Prej, s katerim smo določena celotna Seznam eventually-- vstavljanje vrste. coaxed sem naju skupaj. Ampak kaj je menijo, da je Najenostavnejši način, da se določi ta seznam. 

Ta seznam ni razvrščen. Zakaj? V angleščini, razložiti, zakaj to ni dejansko razporejene. Kaj to pomeni, ni treba sortirati? 

ŠTUDENT: To ni sekvenčno. 

DAVID Malan: Ni sekvenčno. Daj mi primer. 

ŠTUDENT: Daj jih v zaporedju. 

DAVID Malan: OK. Daj mi bolj poseben primer. 

ŠTUDENT: naraščajočem vrstnem redu. DAVID Malan: Ni naraščajoče vrstnem redu. Bodite bolj natančni. Ne vem, kaj misliš s naraščajoče. Kaj je narobe? 

ŠTUDENT: Najmanjši izmed Številke ni v prvem prostoru. 

DAVID Malan: Najmanjše število je Ne v prvem prostoru. Bodite bolj natančni. Začenjam ujeti naprej. Računamo, vendar kaj je v okvari tu? 

ŠTUDENT: Numerična zaporedje. DAVID Malan: Numerična zaporedje. Vsakdo je vrsta vodenja je here-- zelo visoko raven. Samo mi dobesedno pove, kaj je narobe kot pet let stari moči. 

ŠTUDENT: plus ena. 

DAVID Malan: Kaj je to? 

ŠTUDENT: plus ena. 

DAVID Malan: Kaj misliš s plus ena? Daj mi drugo pet-year-old. Kaj je narobe, mama? Kaj je narobe, oče? Kaj misliš da to ni urejeno? 

ŠTUDENT: To ni pravi kraj. 

DAVID Malan: Kaj je ni na pravem mestu? 

ŠTUDENT: Štiri. DAVID Malan: OK, dobro. Torej, štiri je ni tam, kjer bi morala biti. Še zlasti je to prav? Štiri in ena prva dve številki vidim. Ali je to v redu? Ne, oni so v okvari, kajne? V bistvu, mislim zdaj o računalniku, preveč. To lahko ogledate le na morda eno, morda dve stvari na once-- in dejansko samo ena stvar hkrati pa je lahko vsaj poglej eno stvar potem Naslednja stvar, tik ob njem. 

Torej so to, da bi? Seveda ne. Torej, veste kaj? Zakaj ne vzamemo otroka ukrepe, ki določajo te težave namesto da bi te fancy algoritmi, kot so Ben, kjer on je nekako pritrjevanje, ki ga zanka po seznamu namesto da bi to, kar sem storil, kjer Sem ga le nekako določen, ko gremo? Naj samo dobesedno zlomil navzdol Pojem order-- številčnem vrstnem redu rečejo karkoli want-- v teh parne primerjave. 

Štiri in eden. Je to pravi red? Torej, kaj je popraviti. Ena in štiri, nato pa bomo samo kopirajte to. Dobro, dobro. Popravil sem eno in štiri. Tri, dva? No. Naj moje besede ujemajo prste. Štiri in tri? 

To ni v redu, tako da bom narediti eno, tri, štiri, dva. OK, dobro. Sedaj štiri in dve? Moramo popraviti tudi to. Torej ena, tri, dva, štiri. Tako je urejeno? Ne, ampak je bližje razporejene? 

To je, ker smo to določen napaka, smo fiksni to napako, in mi določena to napako. Tako smo v osnovna tri napake verjetno. Še vedno pa ni res videti sortirani, toda je objektivno bližje sortiranega ker smo določen nekatere od teh napak. 

Zdaj, kaj naj storim zdaj? Nekako dosegel konec seznama. Zdelo sem, da so določene vse napake, toda ne. Ker v tem primeru, nekatere številke morda vrela bližje na druge številke, ki so še vedno v okvari. Torej, dajmo še enkrat, in bom samo to na mestu tokrat. Ena in tri? V redu je. Tri, dva? Seveda ne, tako da je spremeniti. Torej dva, tri. Tri in štiri? In zdaj kaj je samo biti še posebej občutljiv tukaj. Je urejeno? Vi ljudje vedo, da je urejeno. 

Moral bi poskusiti znova. Torej Olivia predlaga, da poskusite znova. Zakaj? Ker računalnik nima razkošje naše človeške oči bi samo pogledal back-- OK, bom končal. Kako računalnik določi da je ta seznam zdaj urejeno? Mehansko. 

Moral bi iti skozi še enkrat, in le če ne delajo / najti nobene napake lahko nato pa ugotoviti, računalnika, ja, smo na dobri poti. Tako ena in dve, dve in tri, tri in štiri. Zdaj lahko dokončno reči, da je to razporejene, ker sem naredil nobenih sprememb. Zdaj bi bilo napako in samo neumno, če I, računalnik, vprašal še enkrat te iste vprašanja pričakujejo različne odgovore. Ne bi smelo zgoditi. 

In zdaj je seznam razvrščeni. Na žalost, teče čas Ta algoritem je tudi N na kvadrat. Zakaj? Ker imate n številke, in v najslabšem primeru boste morali premakniti n številk n-krat, ker imate nadaljuj nazaj, da preveri in morda popraviti te številke. In lahko naredimo bolj formalna analiza, preveč. 

Torej, to je vse, da bi rekli, da smo sprejeti trije različni pristopi, ena od njih takoj intuitivno off kij iz Ben na mojo predlagano vključitev vrste, da je ta kjer si nekako pozabimo gozd za drevesa sprva. Ampak potem, če naredimo korak nazaj, voila, smo določen vrstni pojem. Torej, to je, upal reči, nižja raven morda kot nekateri od tistih drugih algoritmi, ampak dajmo vidim, če ne moremo vizualizirati te s pomočjo tega. 

Torej, to je nekaj lepih programsko opremo, da je nekdo napisala s pomočjo pisane palice, ki je naredili naslednje za nas. Vsaka od teh palic predstavlja številko. Višji bar, večji število, manjši bar, manjše število. Torej v najboljšem primeru želimo lepo piramido kjer se začne mala in postane velika, in da bi pomenilo, da Te palice so razporejene. Tako da sem šel naprej in izbrati, na primer, Benova algoritem first-- izbor vrste. 

In opazili, kaj počne. Način, ki so jih izbrali na vizualizirati ta algoritem je, da sem tako kot je bilo hoja skozi moj seznam, ta program je hoja s svojega seznama številk, poudarjanje v roza vsakem Številka, ki jo gleda. In kaj se bo zgodilo zdaj? 

Najmanjše število, ki I ali ben dalo nenadoma dobi premakne na začetku seznama. In zaznali so naredili izselijo številka, ki je bil tam, in to je popolnoma v redu. Nisem dobil v tej ravni podrobnosti. Vendar moramo dati ta številka nekje, zato smo samo preselili na odprto mesto, ki je bilo ustvarjeno. Tako da bom za pospešitev tega gor, ker v nasprotnem primeru pa postane zelo dolgočasno hitro. Animacija speed-- tam gremo. Torej, zdaj enako načelo Sem se uporabljajo, vendar si Lahko začnete počutiti algoritem, če bo, ali pa malo bolj jasno. In to algoritem ima za posledico izberete naslednji najmanjši element, tako da boste začeli videli, da ploščadi na levi strani. In na vsaki ponovitvi, kot sem predlagal, je pa malo manj dela. To ni nujno, da gredo do konca nazaj na levem koncu seznama zato, ker je že ve tisti, so razporejene. Torej je nekako zdi, kot da je pospeševanje, čeprav je vsak korak je pri čemer enako količino časa. Tam je samo manj korakov preostale. In sedaj lahko nekako čutijo Algoritem čiščenje konec njega, in tudi zdaj je to urejeno. 

Torej vstavljanje vrsta je vse narejeno. Moram ponovno naključen array. In opazil sem lahko samo da ga randomizing, in bomo dobili približevanje enak pristop, urejanje z navadnim vstavljanjem. Naj upočasni tukaj. Začnimo da več. Stop. 

Poglejmo preskočiti štiri. No pa gremo. Naključni so niz. In tukaj smo go-- vstavljanje vrste. Igrajo. Opazili, da se ukvarjajo z vsako element naleti takoj, če pa sodi v obvestilo o napačnem mestu vse delo, ki ga je zgodilo. Moramo ohraniti premika več več elementov, da bi naredili prostor za tistega, želimo vzpostaviti. 

Torej smo s poudarkom na levo konec le seznama. Obvestilo nismo niti pogledal at-- mi niso poudarjeno v roza nič na desno. Mi samo ukvarjajo z težave, ko gremo, vendar smo ustvariti veliko delajo za nas še vedno. In zato, če bi pospešili to gor zdaj, da gredo do konca, ima drugačen občutek, da je res. To je samo usmerimo levo na koncu, ampak tem malo več dela kot needed-- vrsta glajenja stvari več, pritrjevanje stvari, vendar se ukvarjajo na koncu z vsak element eden naenkrat dokler ne bomo dobili dobro the-- smo vsi vemo, kako se bo to končalo, tako da je malo underwhelming morda. 

Toda seznam v end-- spoiler-- se bo urejeno. Tako da je pogled na eni zadnji. Ne moremo preskočiti zdaj. Skoraj smo že tam. Še dva, eden iti. In voila. Odlično. 

Zdaj naredimo eno zadnjo, ponovno randomizing z mehurček vrste. In opazil sem, še posebej, če ga počasi navzdol, se ta vodi swooping skozi. Toda opazili samo naredi parno comparisons-- vrste lokalnih rešitev. Toda takoj, ko smo prišli do konec seznama v roza, kaj se dogaja, da imajo spet zgodilo? Ja, to se dogaja, da imajo za začeti znova, ker je to le fiksne Parne napake. In da bi lahko še pokazala druge. In tako, če pospeši to gor, boste glej, da toliko, kot pove že samo ime, manjša elements-- ali ne, večji elements-- začenjajo mehurček do vrha, če hočete. In manjši elementi začenja mehurček navzdol proti levi. In res, da je vrsta vizualni učinek kot dobro. In tako da bo to na koncu zaključna na zelo podoben način, preveč. 

Nimamo spuščala o tem eno. Naj odpre to zdaj, preveč. Obstaja še nekaj drugih sortiranje algoritmi V svetu, nekateri od katerih Tu so zajeti. In še posebej za učence, ki niso nujno vizualni ali matematične, kot smo prej, smo lahko tudi to narediti slušnega če bomo povezali zvok s tem. In samo za zabavo, tukaj je nekaj različnih algoritmov, in eden od njih še posebej si bomo opazili, se imenuje "zlivanjem." 

Je dejansko bistveno boljši algoritem, tako da zlivanjem, eden izmed tisti, s katerimi boste videli, ni red n kvadrat. To je o vrstnem redu za n-krat dnevnik N, ki je pravzaprav manjše in zato hitrejši od tistih ostalih treh. In tam je drugi par neumno tisti, ki bomo videli. 

Torej gremo z nekaj zvokom. To je vstavljanje razvrščanje, tako da še enkrat to je samo ukvarjajo z elementi ko pridejo. To je mehurček vrste, tako da je upoštevamo jim parov naenkrat. In spet, največji elementi so prepihavanje do vrha. 

Naslednji izbor vrste. To je Benova algoritem, kjer spet on izbiro iterativno naslednji najmanjši element. In še enkrat, zdaj lahko zares slišati, da to je pospešilo, vendar le toliko, kolikor saj počne vse manj delo na vsaki ponovitvi. To je hitrejši eno, urejanje z zlivanjem, ki je razvrščanje skupin številk jih skupaj in nato združevanje. Torej look-- levo pol je že urejeno. 

Zdaj je razvrščanje v desno polovico, in Zdaj pa se dogaja, da jih združiti v eno. To je nekaj, kar se imenuje "Gnome vrste." In lahko nekako videli, da to se dogaja, naprej in nazaj, določitvi dela malo tukaj in tam, preden se nadaljuje z novo delo. In to je to. Obstaja še ena vrsta, ki je res samo za akademske namene imenovano "neumen vrste", ki traja vaše podatke, da razvrsti naključno, in nato preveri če je razvrščen. In če je ni, se ponovno razvrsti ga naključno, preveri, če je to urejeno, in če ne ponavlja. In v teoriji, probabilistically To bo popolna, vendar po zelo malo časa. To ni najbolj učinkovitih algoritmov. Tako da kakršna koli vprašanja o tistih posebni algoritmi ali karkoli je povezana tudi? 

No, kaj je zdaj draži narazen, kaj vse te vrstice so, da sem bila risba in kaj sem ob predpostavki, da računalnik lahko storite pod pokrovom. Jaz bi trditi, da so vse te številke Držim drawing-- ki jih potrebujejo, da bi dobili shranjena nekje v spominu. Bomo znebili tega fanta sedaj, preveč. 

Tako kos pomnilnika je z computer-- tako RAM DIMM tisto, kar smo iskali včeraj, dual inline spomin module-- izgleda takole. In vsaka od teh malih črnih žetonov je nekaj število bajtov, običajno. In potem zlato nožice so všeč žice, ki jo povezujejo z računalnikom, in zelena silicijevega plošča je le tisto, kar ohranja vse skupaj. Torej, kaj to v resnici pomeni? Če bi nekako sestaviti to isto sliko, recimo, zaradi enostavnosti da ta DIMM, dvojni inline pomnilniški modul, je eden GB RAM-a, en gigabajt spomin, ki je, koliko bajtov skupaj? Eden od gigabyte je, koliko bajtov? Več kot to. 1124 je kilo, 1000. Mega je milijon. Giga je milijard. 

Sem laže? lahko celo beremo etiketo? To je dejansko 128 GB, tako da je več. Vendar bomo to pretvarjamo je samo en gigabajt. Torej to pomeni, da je milijardo bajtov pomnilnika, ki so na voljo, da me ali 8 milijard bitov, vendar bomo govoriti v smislu bajtov zdaj, premikanje naprej. 

Torej, kaj to pomeni, je to Enobajtni, to je druga bajt, To je še en bajt, in če bomo res hoteli da je specifična bi se morali pripravi milijardo malo kvadratov. Toda kaj to pomeni? No, naj le povečavo v to sliko. Če imam nekaj, kar izgleda kot je to sedaj, to je štiri bajte. 

In tako sem lahko dal štiri številke tukaj. Ena dve tri Štiri. Ali pa bi dal štiri črke ali simbole. "Zdravo!" bi šel tam, ker je vsak od črk, smo razpravljali prej, mogoče predstaviti osem bitov ali ASCII ali bajt. Torej, z drugimi besedami, lahko dal 8 milijard stvari v notranjosti to eno palico spomina. Zdaj kaj to pomeni, da se dajo stvari nazaj nazaj nazaj v spomin, kot je ta? To je tisto, kar je programer bi klic "nizom." V računalniškem programu, ne mislite okoli osnovnega strojne opreme, samo po sebi. Pravkar si mislijo o sebi, kot da imajo dostop do milijardo bajtov vsoto, in lahko karkoli želite z njim. Ampak za udobje je na splošno koristno da pomnilniško pravico drug poleg drugega takole. Torej, če sem povečate this-- ker smo gotovo ne bo pripraviti milijarde malo squares-- recimo, da je ta svet zastopa da palico spomina zdaj. In bom sestaviti toliko kot moja dvojno podajo konča mi daje tukaj. Torej, zdaj imamo palico spomina na krovu da je dobil en, dva, tri, štiri, pet, šest, ena, dva, tri, štiri, pet, šest, seven-- tako 42 bajtov spomin na skupno zaslona. Hvala. Da, naredil moj aritmetično desno. Torej 42 bajtov pomnilnika tukaj. Torej, kaj to dejansko pomeni? No, računalniški programer bi dejansko splošno razmišljati o tem spominu kot Adresabilni. Z drugimi besedami, vsak izmed njih lokacije v pomnilniku, v strojni opremi, ima edinstven naslov. 

To ni tako zapleten, kot One Brattle Square, Cambridge, Mass., 02.138. Namesto tega je samo številka. To je bajt število nič, to je ena, to je dve, to je tri, in to je 41. Počakaj minuto. Mislil sem, da sem rekel 42 pred nekaj trenutki. Začel sem štetja na nič, tako da je dejansko pravilna. Zdaj nimamo, da ga dejansko pripravi kot omrežje, in če jo pripravijo kot mreža Mislim, da stvari dejansko dobili nekoliko zavajajoča. Kaj programer bi, v svojem lastnem umu, na splošno misli o tem pomnilnik, ki je tako kot trak, kot kos samolepilnim trakom da samo nadaljuje in v nedogled ali dokler ne zmanjka pomnilnika. Torej bolj običajen način pripraviti in samo pomislite spomin bi bilo, da je to bajt nič, ena, dva, tri, nato pa pika, pika, pika. In imaš 42 takih bajte skupaj, čeprav čeprav fizično da bi lahko dejansko je nekaj več, kot je ta. 

Torej, če zdaj pomislim na vaš spomin kot je ta, tako kot trak, To je tisto, kar programer znova bi zahtevala vrsto pomnilnika. In če želite, da dejansko shranjevanje nekaj v spominu računalnika, vam na splošno storiti shranjevanje stvari back-to-back to back-to-back. Tako smo že govorili o številkah. In ko sem hotel rešiti probleme kot štiri, ena, tri, dva, čeprav sem bil samo risanje samo številke štiri, ena, tri, dve na krovu, bi računalnik Res so to nastavitev v spomin. 

In kaj bi bilo zraven dva v spominu računalnika? No, ni odgovor na to. Mi res ne vem. In tako dolgo, dokler računalnik ne potrebuje, da ni nujno, da je vseeno, kaj je naslednji s številkami to ne briga. In ko sem že povedal, da je v računalniku lahko ogledate le na en naslov v času, To je nekako, zakaj. 

Ni v nasprotju z zapisom predvajalnik in glavo branje samo, da lahko pogled na določeno groove v fizičnem stare šole zapisu naenkrat, podobno lahko računalnik hvala njegove CPU in njenih Intel nabor ukazov, med katere navodili bere iz pomnilnika ali shranite v memory-- Računalnik lahko ogledate le na enem mestu pri time-- včasih njihove kombinacije, ampak res samo eno lokacijo naenkrat. Torej, ko smo počeli ti različni algoritmi, Ne bom samo pisni obliki v vacuum-- štiri, ena, tri, dva. Te številke dejansko pripadajo nekje fizično v spomin. Tako da so mali tranzistorji ali nekakšen elektronike pod hood shranjevanje teh vrednot. 

In skupaj, koliko bitov vpleten zdaj, samo da bo jasno? Torej, to je štiri bajte, ali zdaj je 32 bitov skupaj. Tako da so dejansko 32 ničel in tisti, ki sestavljajo te štiri stvari. Še več tukaj, ampak spet nam ni mar za to. 

Sedaj pa vprašam drugo Vprašanje uporablja pomnilnik, ker to na koncu dneva v variance. Ne glede na to, kaj lahko naredimo z računalnik, na koncu dneva strojna oprema je še vedno Enako pod pokrovom. Kako bi shraniti besedo tukaj? No, beseda v računalniku kot "zdravo!" bodo shranjeni, tako kot je ta. In če si hotel daljše beseda, lahko preprosto prepišejo da in nekaj reči kot "zdravo" in trgovina, ki tu. 

In tako tudi tu, to contiguousness je pravzaprav prednost, ker računalnik lahko samo bere od desne proti levi. Ampak tukaj je vprašanje. V okviru te besede, h-e-l-l-ol, klicaj, kako bi računalnik ve, kje Beseda se začne in kje se beseda konča? V okviru številk kako deluje računalnik vem, kako dolgo zaporedje številke je, ali če se začne? No, se izkaže out-- in ne bo šel preveč na tej ravni detail-- računalniki premakniti stvari okrog v spomin dobesedno s pomočjo teh naslovov. Torej, v računalniku, če ste pisanje kode za shranjevanje stvari kot povedano, kaj ste res počne je tipkanje izrazi, ki se spomnite, kje v pomnilnik računalnika te besede. Torej mi naredil zelo, zelo preprost primer. 

Bom, da gredo naprej in odpirajo preprost program besedila, in bom za ustvarjanje datoteka z imenom hello.c. Večina teh informacij smo ne bo šel v zelo podrobno, ampak bom napisati Program v istem jeziku, C. To je veliko bolj zastrašujoče, Jaz bi trditi, kot Scratch, ampak to je v duhu zelo podobna. V bistvu, ti Skodrana braces-- lahko nekako mislim, kaj sem storil, kot je ta. 

Naredimo to, pravzaprav. Ko je zelena zastava kliknili, naredite naslednje. Želim natisniti "zdravo." Torej, to je zdaj psevdokoda. Jaz sem nekako zabrisane linije. V C, ta jezik govorim o, ta linija print zdravo dejansko postane "printf" s nekateri oklepaje ter podpičjem. 

Ampak to je točno isto idejo. In to zelo uporabniku prijazen "Ko je zelena zastava kliknili" postane veliko bolj starinski "int main nična." In to je res ni kartiranje, tako da sem le, da bo prezreti, da je. Toda zaviti oklepaji so všeč ukrivljenih kosov sestavljanke je to všeč. 

Tako da lahko nekako uganiti. Tudi če ste nikoli programirano pred, kaj ta program verjetno ne? Verjetno natisne zdravo s klicajem. 

Torej, poskusimo to. Bom, da ga shranite. To pa je spet zelo staro šolsko okolje. Ne morem klikniti, ne morem vleči. Moram vpisovati ukaze. Torej, želim teči svoj program, tako Jaz bi to naredil, kot hello.c. To je datoteka sem tekel. Toda počakaj, sem manjka korak. Kaj smo rekli, je potrebno korak za jezik kot C? Pravkar sem napisal vir kodo, ampak kaj potrebujem? Ja, rabim prevajalnik. Torej, na mojem Mac tukaj, imam program, imenovan GCC, GNU C prevajalnik, ki mi omogoča, da naredite this-- vrsti moje izvorno kodo v, ga bomo klic, strojni kodi. 

In vidim, da je Ponovno, kot sledi, to so ničle in tisti I samo ustvarjena iz moje izvorne kode, vse ničel in enic. In če želim teči moj program-- se zgodi da se imenuje a.out za zgodovinski reasons-- "zdravo." Sem ga lahko ponovno zagnati. Živijo živijo živijo. In zdi se, da se dela. 

Toda to pomeni, da nekje v moji pomnilnik računalnika so besede h-e-l-l-ol, klicaj. In se je izkazalo, tako kot prahi, kakšen računalnik bi običajno tako da se ne ve, kje stvari začnejo in end-- je bo dal poseben simbol tukaj. In konvencija je dal Številka ničelne konec besede tako da boste vedeli, kje je dejansko konča, tako da si ne vodijo bolj tiskanje znakov, kot bi dejansko nameravajo. 

Toda takeaway tukaj, čeprav čeprav je to dokaj Skrivnosten, je, da je na koncu relativno enostavna. Dobil si neke vrste traku, prazno Prostor, na katerem lahko pišete pisma. Vi preprosto morali imeti posebno oznako, kot samovoljno število nič, da dajo na koncu tvoje besede, tako da računalnik ve, oh, naj neha tiskati po Vidim klicaj. Ker je naslednja stvar, ki obstaja je ASCII vrednost nič, ali null značaj kot kdo bi ga poklical. Ampak tam je nekako problem tu, in kaj je vrniti nazaj številkam za trenutek. Recimo, da sem naredil, v resnici, imajo vrsto številk, in domnevam, da je Program pišem je kot redovalnice za učitelja in učiteljev v razredu. In ta program mu omogoča vnesti rezultate svojih učencev na kvizov. In domnevam, da študent dobi 100 na prvi kviz, morda kot 80 na naslednjega, nato pa 75, nato pa 90 na četrtem kviz. 

Tako da na tej točki v zgodbo, matrika z velikostjo štiri. Tam je absolutno več pomnilnika v računalnik, vendar matrika, tako rekoč z velikostjo štiri. Recimo zdaj, da učitelj želi dodeliti peti kviz v razredu. No, ena od stvari, ki jih ali ona se dogaja, da imajo opraviti je zdaj trgovina dodatno vrednost tukaj. Ampak, če array ima učitelj ustvarjena v tem programu je velikosti za, eden od problema z matrike je to ne moreš kar naprej tako, da spomin. Ker kaj če drugi del od Program ima besedo "hej" tam? 

Z drugimi besedami, moj spomin je uporabljen za nič v programu. In če vnaprej sem tipkal v, hej, Želim vhod štirih rezultatov kviza, morda gre tukaj in tukaj. In če ste nenadoma premislite kasneje in da hočem peti kviz ocena, ne moreš samo ga kjerkoli želite, ker kaj pa če je to pomnilnik se uporablja nekaj else-- kakšen drug program, ali kakšno drugo značilnost programa da delate? Tako da boste morali razmišljati vnaprej kako želite shraniti podatke, ker zdaj ste naslikal sami v digitalno kotu. 

Tako učitelj bi lahko namesto pravijo pri pisanju programa za shranjevanje njegovo ali njeno stopnje, veš kaj? Bom, da zahteva, pri pisanju svoj program, da Rad nič, ena, dva, tri, štiri, pet, šest, osem stopenj skupaj. Torej ena, dva, tri, štiri, pet, šest, sedem, osem. Učitelj lahko samo over-dodeliti spomin pri pisanju svoj program, in rekel, veste kaj? Nikoli ne bom dodeliti več kot osem kvizov v semestru. To je samo nor. Nikoli ne bom dodeli da. Tako, da je on ali ona ima na ta način prožnost za shranjevanje študentskih rezultate, kot 75, 90, in morda eno dodatno, kadar študent dobil dodaten kredit, 105. 

Ampak, če učitelj ne uporablja te tri prostore, tam je intuitiven takeaway tukaj. On ali ona je samo zapravljaš prostor. Torej, z drugimi besedami, da je to Skupno kompromis v programiranju kjer lahko dodeli natanko toliko pomnilnika, kot želite, Glavo, ki je, da ste super efficient-- si niso potratne na all-- vendar je slaba stran, ki je kaj, če si premisliš, kadar s pomočjo programa, ki ga želite shraniti več podatkov, kot bi bilo prvotno predvideno. 

Mogoče je rešitev, potem pisati programe na tak način da se porabi več pomnilnika kot jih dejansko potrebujejo. Na ta način ne boš teči v ta problem, ampak si pa potratna. In več pomnilnika vaš program uporablja, kot smo razpravljali včeraj, manj pomnilnika, ki je na voljo za druge programe, prej računalnik lahko počasen navzdol zaradi navideznega pomnilnika. In zato je idealna rešitev bi lahko bila, kaj? 

Pod-razdeljevanje zdi slabo. Over-prirejanje zdi slabo. Torej, kaj bi lahko bila boljša rešitev? Prerazporeditev. Bolj dinamično. Ne se prisiliti, da izberejo priori, na začetku, kaj hočeš. In gotovo ne preveč dodeliti, da ne bi ti bilo potratno. 

In tako bi dosegli ta cilj, smo treba metati to strukturo podatkov, tako rekoč proč. In kaj programer se običajno uporabljajo je nekaj, kar ti ni matrika ampak povezani seznam. Z drugimi besedami, on ali ona bo začeli razmišljati o svojem spominu kot čemer koli obliki, ki jih lahko pripravi na naslednji način. Če hočem shraniti eno številko v program-- tako da je september, Dal sem moji učenci kviz; hočem za shranjevanje prve kviz učencev, in so dobili 100 na it-- I bom vprašal svoj računalnik, s pomočjo programa, ki sem jih napisan za en kos pomnilnika. In bom shranili Številka 100 v njem, in to je to. 

Potem pa nekaj tednov kasneje ko sem dobil svoj drugi kviz, in je čas, da tip V tem 90%, bom vprašati računalnik, hej, računalnik, Lahko sem še en kos pomnilnika? To se dogaja, da mi to prazen kos pomnilnika. Bom dal v številko 90, ampak v mojem programu tako ali other-- in ne bomo skrbeti sintaksa za this-- rabim nekako veriga te stvari skupaj. In jih bom verigo skupaj z Izgleda puščico tukaj. 

Tretji kviz, ki pride gor, Sem hotel reči, hej, računalnik, daj mi še en kos pomnilnika. In bom dal dol kar je bilo, kot 75, in moram verigo tem skupaj zdaj nekako. Četrta kviz pride mimo, in morda da je proti koncu semestra. In v tej točki moje programa lahko uporablja pomnilnik po vsem mestu, po vsej fizično. In tako samo za brcne, da sem dogaja, da pripravi to naprej quiz-- sem pozabil, kaj je bilo; jaz mislim, morda 80 ali something-- Tako tukaj. 

Ampak to je v redu, ker je slikovno Bom, da pripravi te vrstice. Z drugimi besedami, v resnici, strojne opreme računalnika, Prvi rezultat morda na koncu sem, ker je to takoj na začetku semestra. Naslednjič morda na koncu tukaj ker je malo časa minilo in program ohranja teče. Naslednji rezultat, ki je bil 75, lahko tukaj. In zadnji rezultat morda 80, ki je tukaj. 

Torej, v resnici, fizično, bi to lahko bilo kaj spomin računalnika izgleda. Vendar to ni uporaben mentalna paradigma za računalniški programer. Zakaj bi morali skrbeti, če heck vaši podatki se konča? samo želite shraniti podatke. 

To je nekako tako kot naši razpravi prej črpanja kocke. Zakaj ti je mar, kaj kota je kocke in kako moraš obrniti, da ga pripravi? Pravkar si želijo kocko. Prav tu, vas hočejo redovalnice. Pravkar si želeli, da razmišljajo o to kot seznam številk. Koga briga, kako je izvaja v strojno opremo? 

Torej abstrakcija zdaj je ta slika tukaj. To je povezano seznama, kot je programer bi ga poklical, če imate seznam, seveda številk. Vendar je to povezano slikovno s pomočjo teh puščic, in vse te puščice are-- pod pokrov, če ste radovedni, opozarjajo, da je naša fizične strojne opreme naslovi nič, ena, dva, tri, štiri. Vse te puščice so se kot zemljevid ali smeri, kjer je po 90 is-- zdaj Moram štetje. 

Nič, ena, dva, tri, štiri, pet, šest, sedem. Izgleda, da 90 je na Naslov številka spominskega sedem. Vse te puščice so se kot majhen kos papirja da se daje navodila na program, ki pravi, da sledijo temu zemljevid priti do lokacije sedem. In tam boste našli študent drugega kviz ocena. Medtem, 75--, če sem še to, To je sedem, osem, devet, 10, 11, 12, 13, 14, 15. 

Ta druga puščica pravkar predstavlja zemljevid na pomnilniško lokacijo 15. Ampak še enkrat, programer na splošno ne Ne skrbi za to raven podrobnosti. In v večini vsakem programiranju jezik danes, programer sploh ne bo vedel, kje v pomnilniku te številke dejansko so. Vse, on ali ona mora skrbeti, je da so nekako povezane skupaj v podatkovno strukturo, kot je ta. 

Vendar se izkaže, da niso da bi dobili preveč strokovno. Ampak samo zato, ker smo lahko morda privoščiti, da bi to razpravo tukaj, Predpostavimo, da smo ponovno to vprašanje tukaj za matrike. Poglejmo, če smo žal dogaja tukaj. To je 100, 90, 75 in 80. 

Naj na kratko, da to trditev. To je matrika in enkrat, pereče značilnost array je, da je vse vaše podatke nazaj na hrbtni strani v memory-- dobesedno en bajt ali morda štiri bajte, nekateri določeno število bajtov stran. V povezanem seznamu, ki lahko črpamo kot je ta, pod pokrovom, ki ve, kje je ta stvar? Da sploh ne potrebujejo, da teče, kot je ta. Nekateri podatki so lahko nazaj na levo, tam. Sploh ne vem. 

In tako z vrsto, imate Funkcija znan kot bralno. In kaj bralno sredstvo je da lahko računalnik skoči takoj na katero koli mesto v matriki. Zakaj? Ker računalnik ve da je prva lokacija nič, ena, dva, tri. 

In tako, če želite, da gredo iz ta element na naslednji element, dobesedno, v um računalnika, dodajte eno. Če želite iti na tretji element, dodajte one-- naslednji element, samo dodali. Vendar pa v tej različici zgodbe, domnevam računalnik je trenutno iščejo na ali se ukvarjajo s številko 100. Kako priti do naslednjega razred v redovalnice? 

Moraš vzeti sedem koraki, ki je poljubna. Da bi prišli do naslednjega, morate sprejeti še osem korakov, da bi dobili do 15. Z drugimi besedami, to ni stalna razlika med številkami, in zato je prav da prevzame Računalnik več časa, je točka. Računalnik ima za iskanje v pomnilniku, da da bi našli tisto, kar iščete. 

Torej, ker je matrika kaže, da je hitro podatki structure-- ker vas Lahko dobesedno pač enostavno aritmetično in dobili, če želite, z dodajanjem enega, za instance-- povezan seznam, ste žrtvovati to funkcijo. Ne moreš kar iti iz prve na drugi do tretji do četrti. Moraš slediti zemljevid. Moraš sprejeti več ukrepov priti do tistih vrednot, ki so Zdi se, da dodajanje stroškov. Torej smo plačuje ceno, ampak kaj je bilo funkcija, ki je bil Dan išče tukaj? Kaj povezan seznam očitno nam omogočajo, da ne, ki je bila izvor to predvsem zgodba? 

Točno tako. Dinamični velikost nanjo. Mi lahko dodamo na ta seznam. Mi lahko tudi skrči seznam, tako da smo le z uporabo toliko pomnilnika kot dejansko želimo in tako smo nikoli preveč razdeljevanje. 

Zdaj pa samo, da je res nit-izbirčen, tam je skrito stroškov. Zato se nikoli ne pusti me prepričal si, da je to prepričljiv kompromis. Še en skriti strošek tukaj. Korist, mora biti jasno, je, da smo dobili dinamiko. Če želim še en element, da lahko samo ga pripravi in ​​dal več tam. In potem sem ga lahko poveže s sliko tod ker je tukaj, še enkrat, če sem sam naslikal v kotu, če kaj drugega se že uporablja spomin tu, sem od sreče. Sem sam naslikal v kotu. 

Toda tisto, kar je skrito stalo na tej sliki? To ni samo količina Čas, ki je potreben iti od tu do tu, kar je sedem korakov, nato Osem korakov, ki jih je več kot ena. Kaj je še skritih stroškov? Ne samo čas. Dodatne informacije potrebno za dosego to sliko. 

Ja, to karto, ti malo zapisov o papir, kot sem vedno znova opisujejo kot. To arrows-- to ni zastonj. Computer-- veš kar ima računalnik. Ima ničle in narave. Če želite predstavlja puščico ali A map ali več, boste potrebovali nekaj pomnilnika. Torej drugi ceno, ki jo plačati za povezani seznam, skupni računalništva virov, je tudi prostor. 

In res je tako, tako pogosto, med kompromisi pri oblikovanju programske opreme inženiring Sistemi za čas in space-- sta dva izmed svojih sestavin, dva vaših najdražjih sestavin. To me stanejo več časa ker moram upoštevati ta zemljevid, vendar pa je že tudi mi stanejo več prostora ker imam, da bo ta zemljevid okoli. Torej upanje, kot smo jih nekako obravnavali kot včeraj in danes, je, da so koristi bodo večje od stroškov. 

Vendar ni očitna rešitev tukaj. Mogoče je better-- a la hitro in umazano, kot Kareem predlagano earlier-- metati spomin na problem. Samo kupiti več pomnilnika, mislim manj težko o reševanju problema, in ga rešiti na lažji način. In celo prej, ko smo se pogovarjali o kompromisi, ni bilo prostor računalnik in čas. To je bil čas za razvijalce, ki še en vir. 

Torej še enkrat, da je to ravnotežja poskuša odločiti, katere od teh stvari ste pripravljeni porabiti? Ki je najcenejši? Ki prinaša boljše rezultate? Ja? 

Prav zares. V tem primeru, če ste predstavljajo številke v maps-- to so ti v številnih jezikih "kazalci" ali "naslovi" - to je dvakrat več prostora. To ne bi smelo biti tako slabo, kot dvojna, če zdaj smo samo shranjevanje številk. Denimo, da smo bili shranjevanje zapisov bolnikov v hospital-- tako imena Pierson je, telefonske številke, številke socialnega zavarovanja, zdravnik Zgodovina. To polje je lahko veliko, veliko večji, pri čemer majhen malo kazalec, naslov Naslednji element-- to ni nič takega. To je tako obroben stalo ni pomembno. Toda v tem primeru, ja, to je podvojitev. Dobro vprašanje. 

Spregovorimo o časovnem a malo bolj konkretno. Kaj je čas teče iskanja ta seznam? Recimo, da sem želel iskanje skozi vse razrede učencev, in tam je n ocene V tej strukturi podatkov. Tudi tu lahko sposodim Besednjak prej. To je linearna struktura podatkov. 

Big O n je tisto, kar je potrebno, da bi dobili na koncu te strukture podatkov, whereas-- in nismo videli To before-- matrika vam daje kar se imenuje konstanta čas, kar pomeni, en korak ali dva koraka ali 10 steps-- ni važno. To je osnovna številka. To nima nič opraviti z velikost polja. In razlog za to, še enkrat, je bralno-pisalnega. Računalnik lahko samo takoj skok na drugo mesto, ker so vsi enaki oddaljenost od vsega drugega. Ni vpleten razmišljanje. V redu. Torej, če sem lahko, naj poskušajo slikati dve končne slike. Zelo pogost en znan kot hash tabelo. Torej motivirati to razpravo, Naj razmišljati o tem, kako to storiti. 

Torej, kaj pa je to? Denimo, da je problem želimo zdaj rešiti izvaja v dictionary-- tako cel kup angleških besed ali karkoli. In cilj je, da bi lahko odgovorili vprašanja obliki je to beseda? Torej hočeš, da izvajanje črkovalnik, le kot fizični slovar da si lahko ogledate stvari v. Recimo, da bi to naredili s paleto. Jaz bi to lahko naredil. 

In domnevam besede so jabolko in banana in melona. In ne morem misliti sadja ki se začnejo z d, tako da smo pravkar dogaja, da imajo tri sadje. Torej, to je množica, in smo shranjevanje vseh teh besed V tem slovarju kot matrike. Vprašanje je torej, kako še lahko shranite te informacije? 

No, jaz sem nekako varanje tukaj, ker vsako od teh črk v besede je res posameznik bajt. Torej, če sem res želela biti nit-izbirčen, da bi moral res je treba tako, da to gor v veliko manjše kose pomnilnika, in lahko storimo ravno to. Ampak bomo zašli v enak problem kot prej. Kaj pa, če, kot Merriam Webster ali Oxford počne vsak year-- dodajo besede na dictionary-- ne bomo nujno želijo slikati sebe v kotu z vrsto? 

Torej, namesto, morda pametnejši pristop je dal jabolko v svojem vozlišču ali polje kot bi rekli, banana, in potem tukaj imamo melona. In smo niz te stvari skupaj. To je torej matrika, in to je povezani seznam. Če ne more povsem videti, je samo pravi: "Niz", in ta pravi, da "seznam". 

Torej imamo enake Natančne vprašanja, kot prej, pri čemer imamo zdaj dinamika v našem povezani seznam. Vendar imamo dokaj počasno slovar. Recimo, da želite poiskati besedo. To mi lahko traja veliko O n koraki, ker beseda morda so vse poti na koncu seznam, kot melone. In se izkaže, da v programiranje, razvrščanje na sveti gral podatkov strukture, je nekaj ki vam omogoča stalen Čas kot niz vendar to še vedno vam daje dinamiko. 

Tako lahko imamo najboljše iz obeh svetov? In res, da je nekaj imenuje hash tabela ki vam omogoča, da natančno da, čeprav približno. Razpršene tabele je Ljubitelj struktura podatkov, ki jih moremo misliti kot Kombinacija array-- in bom, da ga pripravi kot this-- in povezanih seznamov da bom pripravi takole tukaj. 

In kako ta stvar dela je, kot sledi. Če now-- this hash table-- je moj tretji struktura podatkov, in želim, da shranite besede v tem, da ne želi le shraniti vse besede back to back to back to back. Želim vzvoda nekaj podatek o besedah, ki bo pustil mi ga dobili, če je hitrejši. 

Torej, glede na besede jabolko in banane in melone, Namenoma sem izbrala te besede. Zakaj? Kaj je nekako v osnovi razlikuje glede na tri? Kaj je jasno? Začnejo z različnimi črkami. 

Torej, veste kaj? Namesto da bi vse moje besede enako vedro, tako rekoč kot v enem dolgem seznamu, zakaj ne Sem vsaj poskusiti optimizacijo in da moje sezname 26/01 tako dolgo. Prepričljivih optimizacija morda, zakaj pa ne Jaz-- pri vstavljanju besede v to strukturo podatkov v spominu računalnika, zakaj ne bom dal vse "A" besede, tukaj, vsi "b" besede tukaj, in vse "c" besede so tukaj? Torej, to konča dajanje jabolko tukaj, banana tukaj, melone tukaj, in tako naprej. 

In če imam dodaten Beseda like-- kaj drugega? Jabolko, banana, hruška. Kdo misli iz sadja ki se začne z a, b ali c? Blueberry-- popolna. To se bo končalo tukaj. In tako se zdi, da imajo nekoliko boljša rešitev, ker zdaj, če hočem za iskanje jabolko, sem first-- jaz ne le potop v svojo podatkovno strukturo. Ne potopite v spomin mojega računalnika. Sem prvi pogled na prvo črko. 

In to je tisto, kar računalnik znanstvenik bi rekel. Si hash v svojo podatkovno strukturo. Vzamete vhod, ki je v V tem primeru je beseda, kot jabolko. Jo proučiti prva črka v tem primeru s čimer je razpršitev. Razprševanje je splošen izraz, s katerim vzameš nekaj kot vhod in jih proizvajajo nekatere izhod. In izhod s tem Primer je lokacija želite iskati, prvi lokacija, druga lokacija, tretji. Torej, vhod je jabolko, proizvodnja je prva. Vhod je banana je Izhod mora biti drugi. Vhod je melone, proizvodnja mora biti tretji. Vhod je borovnica je Izhod bi moral spet drugi. In to je tisto, kar vam pomaga, da bližnjice skozi spomin da bi prišli do besede ali podatke bolj učinkovito. 

Zdaj to zmanjša našega časa potencialno toliko, kot eden od 26, ker če predpostavimo, da vas imajo toliko "A" besede, kot so "Z" besede, kot so "Q" besed, ki ni res realistic-- boste imeli nagnjenost čez nekatere črke alphabet-- vendar pa bi bilo to primarni pristop, ki ne omogočajo da si veliko hitreje priti do besede. In v resnici, prefinjeno Program je Googlovo sveta, Facebooks od world-- bi jih uporabili razpršene tabele za veliko različnih namenov. Vendar pa ne bi bil tako naiven, kot je samo poglej na prvo črko v jabolko ali banana ali hrušk ali melone, saj, kot lahko vidite, to Seznami lahko še vedno dobite dolgo. 

In zato je to morda še vedno neke od linear-- tako nekako počasi, kot z velikim O n da smo razpravljali prej. Torej, kaj je resnično dober hash tabela bo do-- bo imel veliko večji nabor. In bo uporabila veliko bolj prefinjen razprševanje funkcija, tako, da se ne samo pogled na "a." Morda je videti na "a-p-p-l-e" in nekako pretvori tistih pet črk v kraju, kjer jabolko je treba shraniti. Mi samo naivno z črko "a" sam, saj je lepo in enostavno. 

Toda razpršene tabele, v konec, si lahko zamislite ali kot kombinacija niz, od katerih vsaka je povezan seznam, ki v najboljšem primeru mora biti čim krajše. In to ni očitna rešitev. V resnici, velik del fino nastavitev da gre na pod pokrovom kadar izvajanje tovrstnih izpopolnjene podatkovne strukture je tisto, kar je prav dolžina polja? Kaj je prava funkcija hash? Kako hranite stvari v spomin? 

Toda zavedamo, kako hitro tovrstna razprava stopnjevalo, in sicer tako daleč, da je vrsta za nad glavo na tej točki, ki je v redu. Ampak smo začeli, odpoklic, z resnično nekaj nizko stopnjo in elektronsko. In zato je to spet je to Tema abstrakcije, kjer je nekoč začnete jemati odobrena, OK, imam it-- obstaja fizičnega pomnilnika, OK, razumem, vsak fizično lokacijo, ki ima naslov, OK, razumem, da lahko predstavljajo ti naslovi so arrows-- lahko zelo hitro, da imajo bolj zapletene pogovorov, ki Na koncu se zdi, da se nam omogoči za reševanje problemov, kot so iskanje Sortiranje in bolj učinkovito. In prepričani, too-- ker sem to mislim je najgloblja smo šli v nekatere od teh tem CS proper-- smo jih na opravljeno v enem dnevu in pol na to poudariti tisto, kar bi običajno stori preko potek osem tednov v semestru. 

Vsa vprašanja glede te teme? Ne? V redu. Torej, zakaj ne se ustavimo tam, začetek kosilo nekaj minut prej, nadaljeval v skoraj eno uro? In bom ostajal za malo z vprašanji. Potem bom moral iti traja nekaj klicev, če je to v redu. Bom vklopite glasbo v tem času, ampak mora kosilo je za vogalom.