DAVID Malan: Allt í lagi. Við erum aftur. Svo í þessum flokki á forritun hvað Ég hélt að við myndum gera er að blanda af hlutum. Einn, gera smá eitthvað snertið ekki-á, að vísu með meira fjörugur forritun environment-- einn sem er sýnileg á nákvæmlega konar hugmyndir við höfum verið að tala um, en lítið meira formlega. Tveir, líta á sumir af meira tæknilega leiðir að forritari myndi reyndar leysa vandamál eins og að leita vandans að við skoðuðum áður og einnig meira grundvallaratriðum áhugavert vandamál að flokka. 

Við ráð bara frá the fá að fara að það símaskrá var raðað, en það eitt er í raun eins konar erfitt vandamál með mörgum mismunandi vegu til að leysa það. Þannig að við munum nota þessar sem flokkur vandamálum fulltrúi hlutum sem gæti verið leyst almennt. Og þá munum við tala um í sumum smáatriðum hvað eru kallaðir gögn structures-- áhugamaður leiðir eins tengd listum og kjötkássa matskeið og tré sem forritari væri í raun notkun og almennt nota á whiteboard að mála mynd af því sem hann eða hún ímynda fyrir framkvæmd sumir stykki af hugbúnaður. 

Svo skulum gera snertið ekki-á hluta fyrst. Svo bara fá þinn snertið ekki óhrein með að umhverfi kallast scratch.mit.edu. Þetta er tæki sem við notum í grunnnámi bekknum okkar. Jafnvel þó að það er hannað fyrir 12 ára og upp, við notum það fyrir þig hluti af þeim töluvert þar sem það er gott, gaman Grafísku leið til að læra lítið eitthvað um forritun. Svo höfuð til þessa vefslóð, þar sem þú ætti að sjá síðu alveg eins og þetta, og fara á undan og smelltu Join Scratch efst til hægri og velja notandanafn og lykilorð og að lokum fá þig An account-- scratch.mit.edu. Ég hélt ég myndi nota þetta sem tækifæri fyrst að sýna þetta. Spurning kom upp á í hálfleik um hvað númer raunverulega lítur út. Og við vorum að tala á í hálfleik um C, í particular-- sérstaklega a lægri í eldri tungumáli. Og ég gerði bara fljótur Google leit til að finna C kóða fyrir tvöfaldur leit, reiknirit sem við notuð til að leita að símaskránni fyrr. Þetta tiltekna dæmi, að sjálfsögðu, ekki leita símaskrá. Það leitar bara a heild búnt af Tölurnar í minni tölvu. En ef þú vilt bara fá sjón tilfinningu fyrir því hvað raunveruleg forritun Tungumál lítur út eins og, það lítur a lítill eitthvað eins og þetta. Svo það er um 20-plús, 30 eða svo línur af kóða, en samtal við voru með yfir hlé var um hvernig þetta í raun og veru fær morphed í núllum og sjálfur og ef þú getur ekki bara snúa að vinna og fara frá núll og sjálfur baka til að kóða. 

Því miður, the aðferð er svo transformative að það er mun auðveldara sagt en gert. Ég fór á undan og í raun snúið það program, Binary Search, í núll og sjálfur með því að forrit sem heitir The þýðanda sem ég átt hér rétt á Mac minn. Og ef þú horfir á skjáinn hér, með áherslu sérstaklega á þessum miðja sex dálka aðeins, þú munt sjá aðeins núll og sjálfur. Og þeir eru núll og sjálfur að semja einmitt að leit program. 

Og svo hver klumpur af fimm bitum, hver bæti núllum og sjálfur hér, tákna sumir kennsla yfirleitt inni í tölvunni. Og í raun, ef þú hefur heyrt markaðssetning slagorð "Intel inni" - sem, auðvitað, þýðir að þú ert með Intel CPU eða heila inni í tölvunni. Og hvað það þýðir að vera CPU er að þú sért með kennsla setja, svo að segja. 

Sérhver CPU í heiminum, margir af þá gerð af Intel þessa dagana, skilur endanlegt Fjöldi leiðbeiningar. Og þessir leiðbeiningar eru svo lágt sem bæta þessa tvo tölur saman, margfalda þessar tvær tölur saman, færa þetta stykki af gögn héðan að hér í minni, spara þetta Upplýsingar frá hér að hér í minni, og svo forth-- svo mjög, mjög lágmark-láréttur flötur, nánast rafræn upplýsingar. En með þeim stærðfræði rekstur par við það sem við ræddum áðan, framsetning gagna eins núllum og sjálfur, getur þú byggja upp allt sem tölvan getur gert í dag, hvort sem það er texta, myndræna, tónlistar, eða á annan hátt. 

Svo er þetta mjög auðvelt að fá glataður í illgresið á fljótt. Og það er mikið af syntactical áskoranir þar ef þú gerir einfaldasta, heimskasta af innsláttarvillur ekkert áætlunarinnar mun vinna af neinu tagi. Og svo í stað þess að nota a Tungumál eins og C í morgun, Ég hélt að það væri meira gaman að raunverulega gera eitthvað meira sjón, sem en hannað fyrir krakka er í raun fullkomið birtingarmynd af raunverulegum forritun Language-- bara gerist nota myndir í stað texta til að tákna þær hugmyndir. 

Svo þegar þú ert örugglega reikningur á scratch.mit.edu, smelltu á Búa til hnapp efst til vinstri af the staður. Og þú ættir að sjá umhverfi eins sá sem ég er að fara að sjá á skjánum mínum hér. Og við munum eyða bara smá smá tíma í að spila hér. Við skulum sjá hvort við getum ekki öll leyst sum vandamál saman á eftirfarandi hátt. 

Svo það sem þú munt sjá í þessari environment-- og í raun bara láta mér hlé. Er einhver ekki hér? Ekki hér? OK. Svo láta mig benda á nokkrar einkenni þessarar umhverfi. 

Svo á efst til vinstri á skjánum, við hafa stigi Scratch er, svo að segja. Scratch er ekki aðeins nafn þessarar forritunarmál; það er einnig nafn á kött sem þú sérð sjálfgefið þar í appelsína. Hann er á sviðinu, svo mikið eins og ég lýsti skjaldbaka fyrr eins og að vera í rétthyrnd hvítt borð umhverfi. Heimurinn Þessi köttur er bundin alveg að því rétthyrningur upp efst þar. 

Á sama tíma, á hægri hönd hlið hér, það er bara forskriftir svæði, autt ef þú vilt. Þetta er þar sem við erum að fara að skrifa áætlanir okkar í bara smá stund. Og byggingareiningar sem við munum nota til að skrifa þetta program-- þraut stykki, ef þú ert will-- þá hérna í miðjunni, og þeir eru flokkaðir með virkni. Svo, til dæmis, ég ætla að fara á undan og sýna fram á að minnsta kosti einn af þessum. Ég ætla að fara á undan og smelltu eftirlitsnefnd flokki upp efst. 

Svo þetta eru flokkar upp efst. Ég ætla að smella Control flokk. Frekar, ég ætla að smella á atburðum flokkur, the mjög fyrstur einn upp topp. Og ef þú vilt að fylgja eftir jafnvel eins og við gerum þetta, þú ert alveg velkomið að. Ég ætla að smella og draga þetta fyrsta, "þegar grænn fáni smellt." Og þá ætla ég að sleppa því bara u.þ.b. efst á auða Spjöld mínum. 

Og hvað er gott um grunni er að þessi þraut stykki, þegar kveikja á öðrum þraut stykki, er að fara að gera bókstaflega hvað þessir púsluspil stykki segja að gera. Svo, til dæmis, Scratch er rétt nú í miðri heiminum. Ég ætla að fara á undan og velja nú, við skulum segja, Motion flokki, ef þú vilt gera same-- Motion flokk. Og nú eftir að ég hafa a heild fullt af stykki púsluspil hér sem, aftur, eins konar að gera það sem þeir segja. Og ég ætla að fara á undan og draga og falla færa blokk hérna. 

Og eftir að um leið og þú færð nálægt the botn af the "græna fána smellti "hnappinn, tilkynning hvernig hvítt lína birtist, eins og það er nánast segulmagnaðir, vill það til að fara þangað. Bara láta fara, og það mun smella saman og form mun passa. Og nú þú getur kannski næstum giska á hvar við erum að fara með þetta. 

Ef þú líta á grunni sviðinu hérna og líta til the toppur af það, þú munt sjá rautt ljós, a stöðva merki og græna fána. Og ég ætla að fara á undan og horfa screen-- mín fyrir réttlátur a augnablik, ef þú gætir. Ég ætla að smella á Grænfánann núna, og hann flutti það virðist vera 10 skref eða 10 punktar, 10 punktar, á skjánum. 

Og svo ekki spennandi, en láta mig leggja án þess þó að kenna þetta, bara nota eigin eigin intuition-- Let mér að leggja til að þú reikna út hvernig á að gera Scratch ganga strax sviðinu. Hafa hann að gera brautina fyrir hægri hlið skjár, alla leið til hægri. Leyfðu mér að gefa þér augnablik eða svo að glíma við það. Þú vilt kannski að kíkja á aðra flokka blokkum. Allt í lagi. Svo bara að ágrip, þegar við höfum grænn fáni smellt hér og færa 10 skref er Aðeins kennsla, í hvert sinn sem ég smelltu á græna fána, hvað er að gerast? Jæja, það er í gangi forritið mitt. Svo ég gæti gert þetta kannski 10 sinnum handvirkt, en þetta líður svolítið bita hackish, svo að segja, þar sem ég er í raun ekki að leysa vandann. Ég er bara að reyna aftur og aftur og aftur og aftur þangað til ég svona óvart ná tilskipunina að ég ákvað að ná fyrr. 

En við vitum af okkar sauðakóðanum fyrr að það er Þessi hugmynd í forritun lykkja, gera eitthvað aftur og aftur. Og svo sá ég að fullt af þér náð fyrir hvað ráðgáta stykki? Endurtakið þar. Þannig að við gætum gert eitthvað eins endurtaka þangað. Og hvað gerðir þú endurtaka þar nákvæmlega? 

OK. Og láta mig fara með einn sem er nokkuð einfaldara fyrir réttlátur a augnablik. Leyfðu mér að fara á undan og gera þetta. Takið eftir því, sem þú kannt að hafa komst undir stjórn, það er þetta endurtaka blokk, sem lítur ekki eins og það sé það stór. Það er ekki mikið pláss í milli þessara tveggja gulum línum. En eins og sumir af þú might hafa tekið, ef þú draga og sleppa, eftir því hvernig það vex að fylla lögun. 

Og þú getur jafnvel troða meira. Það verður bara að halda áfram að stækka ef þú draga og sveima yfir það. Og ég veit ekki hvað er best hér, þannig að við skulum mér að minnsta kosti endurtaka fimm sinnum, fyrir dæmi, og þá fara aftur á svið og smella á græna fána. Og nú eftir að það er ekki alveg það. 

Nú sumir af þú lagt, eins og Victoria bara gerði, endurtaka 10 sinnum. Og það yfirleitt gerir fá hann alla leið, en myndi ekki það að vera öflugri leið en geðþótta vangaveltur út hversu margir færist á að gera? Hvað gæti verið betra blokk en endurtaka 10 sinnum verið? 

Já, svo hvers vegna ekki að gera eitthvað eilífu? Og nú langar mig að færa þessa þraut stykki þarna inni og losna við þessa einn. Nú taka Sama hvar Scratch byrjar, fer hann að brún. Og sem betur fer MIT, sem gerir Scratch, bara gerir viss um að hann hefur aldrei hverfur alveg. Þú getur alltaf grípa skottið. 

Og bara innsæi, hvers vegna er hann að halda að flytja? Hvað er að gerast hér? Hann virðist hafa hætt, en þá ef ég tekið upp og draga Hann heldur langaði til að fara yfir það. Afhverju er það? Sannlega, tölvan er bókstaflega að fara að gera það sem þú segir það að gera. Svo ef þú sagt það áðan að gera það Eftirfarandi hlutur eilífu, færa 10 skref, það er að fara að halda áfram og fara þangað til ég lenti á rauða stöðva merki og stöðva the program öllu leyti. 

Svo jafnvel ef þú did ekki að gera þetta, hvernig gat ég gera Scratch fara hraðar yfir skjáinn? Fleiri skref, ekki satt? Svo í stað þess að gera 10 í einu, hví ekki við fara á undan og breyta því to-- hvað myndir þú propose-- 50? Svo nú er ég að fara að smella á græna merkja, og reyndar fer hann mjög hratt. 

Og þetta, að sjálfsögðu, er bara birtingarmynd fjör. Hvað er fjör? Það er bara að sýna þér manna a heild búnt af kyrrmyndir í raun, virkilega, virkilega hratt. Og svo ef við erum bara að segja honum að fara fleiri skref, við erum bara að hafa áhrif að vera að breyting þar sem hann er á skjánum allt hraðar á tímaeiningu. 

Nú er næsta verkefni sem ég lagði var að hafa hann hopp burt brún. Og án þess að vita hvað ráðgáta stykki exist-- því það er fínt ef þú færð ekki til stigi challenge-- hvað viltu gera innsæi? Hvernig myndum við hafa hann hopp til baka og fram, milli vinstri og hægri? 

Já. Þannig að við þurfum einhvers konar á ástandi og við virðast hafa conditionals, svo að tala, undir stjórn flokki. Hver af þessum blokkum við viljum líklega? Já, kannski "ef, þá." Svo eftir að meðal gulu blokkir við höfum hér, það er þetta "ef" eða þetta "ef annað" blokk sem vilja leyfa okkur að taka ákvörðun um að gera þetta eða til að gera það. Og þú getur jafnvel hreiður þá að gera marga hluti. Eða ef þú hefur ekki farið hér enn, fara á undan til Sensing flokki and-- skulum sjá hvort það er hér. 

Svo það blokk gæti verið gagnlegt hér til greina ef hann er af sviðinu? Já, eftir að sumir af þessum blokkum Hægt er að parametrized, svo að segja. Þeir geta verið eins konar aðlaga, ekki ólíkt HTML gær með eiginleika, ef þessir eiginleikar konar sérsníða hegðun merkinu. Á sama hátt hér, get ég grípa þetta lauslega blokk og breyta og spyrja, ertu að snerta músina bendi eins bendilinn eða ertu að snerta brún? 

Svo láta mig fara á og gera þetta. Ég ætla að þysja út um stund. Leyfðu mér að grípa þessa þraut stykki hér, þetta ráðgáta stykki þetta, og ég ætla að jumble þá upp fyrir réttlátur a augnablik. Ég ætla að færa þetta, að breyta þessu til að snerta brún, og ég ætla að hreyfingu gera þetta. Svo hér eru nokkrar innihaldsefni. Ég held að ég hef fengið allt sem ég vil. 

Myndi einhver vilja leggja því hvernig ég Hægt er að tengja þessar kannski efst til botn í því skyni að leysa vandamál af því að hafa Scratch hreyfa hægri til vinstri til hægri til að vinstri til hægri til vinstri, hvert tími skoppar bara að slökkva á veggnum? Hvað vil ég gera? Hvaða blokk ætti ég að tengja við "Þegar grænn fáni smellt fyrst"? 

OK, þannig að við skulum byrja með "að eilífu." Hvað fer inn næst? Einhver annar. OK, færa skrefum. Allt í lagi. Hvað svo? Svo þá ef. Og eftir, jafnvel þótt það lítur samloka saman þétt, það verður bara að vaxa til að fylla. Það verður bara að hoppa í þar sem ég vil það. 

Og hvað á ég að setja á milli if og þá? Sennilega "ef snerta brún." Og takið eftir, aftur, það er of stór fyrir það, en það mun vaxa að fylla. Og þá snúa 15 gráður? Hversu margar gráður? Já, svo 180 mun snúast mér alla leið kring. Svo skulum sjá hvort ég fékk þetta rétt. Leyfðu mér að súmma út. 

Leyfðu mér að draga Scratch upp. Svo hann er svolítið aum nú, en það er allt í lagi. Hvernig get ég endurstilla hann auðveldlega? Ég ætla að svindla örlítið. Þannig að ég ætla að bæta öðru blokk, bara til að vera skýr. Ég vil að hann benda 90 gráður til hægri sjálfgefið, þannig að ég ætla bara að fara að segja honum að gera það kerfisbundið. Og hér við fara. Við virðumst hafa gert það. Það er svolítið skrítið, því hann er að ganga á hvolfi. Við skulum kalla það galla. Það er rangt. A padda er mistök í a program, a rökrétt villa sem ég, manna, gerði. Hvers vegna er hann að fara á hvolf? Vissir MIT skrúfa upp eða gerði ég? 

Já, ég meina, það er ekki MIT er kenna. Þeir gáfu mér ráðgáta stykki sem segir að snúa einhvern fjölda gráður. Og á tillögu Victoriu, Ég ætla að snúa 180 gráður, sem er rétt innsæi. En beygja 180 gráður bókstaflega þýðir að snúa 180 gráður, og það er í raun ekki það sem ég vil, greinilega. Því að minnsta kosti er hann í þetta tvívíð heimi, svo beygja er virkilega að fara til að fletta honum á hvolfi. 

Ég vil líklega nota hvaða blokk í staðinn, miðað við það sem þú sérð hér? Hvernig getum við lagað þetta? Já, svo við gætum benda í gagnstæða átt. Og reyndar er jafnvel að ekki að fara að vera nóg, vegna þess að við getum aðeins erfitt númer að benda vinstri eða hægri. 

Þú veist hvað við gætum gert? Það lítur út eins og við höfum þægindi blokk hér. Ef ég stækka, sjá eitthvað sem við eins og hér? Svo það lítur út eins og MIT hefur abstrakt byggð hér. Þessi blokk virðist vera jafngildar sem aðrir blokkir, plural? 

Þetta ein húsaröð virðist vera jafngildar að allri þessari þremur blokkum sem við höfum hér. Svo kemur í ljós að ég get einfalda minn Forritið með því að fá losa af öllum sem og bara setja þetta hérna. Og nú er hann enn smá þrjótur, og það er allt í lagi núna. Við munum fara að vera. En forritið mitt er jafnvel einfaldara, og þetta líka, væri fulltrúi um markmið í programming-- er að helst að gera kóðann þinn eins einfalt, eins samningur og mögulegt er, en samt vera eins læsileg og hægt er. Þú vilt ekki að gera það svo gagnorðar að það er erfitt að skilja. 

En eftir að ég hef skipt þrjár blokkir með einn, og það er að öllum líkindum gott. Ég hef horfir burtu hugmynd um að athuga hvort þú ert á brún með réttlátur einn blokk. Nú getum við haft gaman með þetta, í raun. Þetta þýðir ekki að bæta svo mikið vitsmunalegum gildi en fjörugur gildi. Ég ætla að fara á undan og grípa þetta hljóð hér. Svo láta mig fara á undan, og láta mig stöðva forritið um stund. Ég ætla að taka eftirfarandi, leyfa aðgang að hljóðnemanum mínum. 

Hér við fara. Ouch. Við skulum reyna þetta aftur. Hér við fara. OK, ég skráð rangt hlutur. Hér við fara. Ouch. Ouch. Allt í lagi. Nú þarf ég að losna við það. Allt í lagi. 

Svo nú hef ég a Upptakan af réttlátur "Ouch." Svo nú ætla ég að fara á undan og kalla þetta "ouch." Ég ætla að fara aftur til skrifta mínum, og nú tilkynning það er þetta blokk sem heitir spila hljóð "meow" eða spila hljóð "ouch". Ég ætla að draga þetta, og þar sem ætti ég að setja þetta fyrir fyndinn áhrif? Já, svo nú er það eins konar þrjótur, því nú block-- þetta eftir því hvernig þetta "ef á brún, hopp "er eins konar sjálf-gámur. Þannig að ég þarf að laga þetta. Leyfðu mér að fara á undan og gera þetta. Leyfðu mér að losna við þetta og fara aftur að upprunalega okkar, meira vísvitandi virkni. Svo "ef snerta brún, þá" ég vil að snúa, eins og Victoria lagt, 180 gráður. Og ég vil að spila hljóðið "ouch" það? 

Já, eftir það er úti að gult blokk. Svo þetta líka, væri galla, en ég hef tekið eftir því. Þannig að ég ætla að draga það upp hér, og tilkynning nú er það inni í "ef". Svo "ef" er þetta tegund af eins handlegg eins afmá það er bara að fara að hvað er inni í henni. Svo nú ef ég súmma út á hætta á annoying-- 

COMPUTER: Ouch, ouch, ouch. 

DAVID Malan: Og það verður bara að fara að eilífu. Nú bara að flýta hlutina hér, láta mig fara á undan og opna upp, skulum say-- láta mig fara að sumir eigin dótinu mínu frá bekknum. Og láta mig opna, við skulum segja, þetta einn gert með því að einn af félögum kennslu okkar a par af ár síðan. Svo sumir af þú might muna þessi leikur frá fyrra, og það er í raun merkilegt. Jafnvel þó að við höfum gert það Einfaldasta forrit núna, við skulum íhuga hvað þetta reyndar lítur út. Leyfðu mér að ýta leika. 

Svo í þessum leik, höfum við froskur og nota örina keys-- Hann tekur stærri skref en ég remember-- Ég hef stjórn á þessu froskur. Og markmiðið er að komast yfir upptekinn Vegurinn án þess að keyra inn í bíla. Og við skulum see-- ef ég fer upp hér, ég verða að bíða fyrir log til að fletta af. Þetta er eins og galla. Þetta er góður af galla. Allt í lagi. Ég er á þetta hér, þar, og þá halda áfram þangað til þú færð allar froskarnir til Lily pads. Nú gæti þetta litið allt flóknari, en við skulum reyna að brjóta þetta niður andlega og munnlega í upprunalegu blokkir sína. Svo er það líklega ráðgáta Verkið sem við höfum ekki séð ennþá en það er að bregðast við mínútum, að það sem ég lenti á lyklaborðinu. 

Svo er það líklega einhvers konar blokk sem segir, ef lykill jafngildir upp, þá gera eitthvað með Scratch-- kannski færa það 10 skref með þessum hætti. Ef ekki er ýtt niður takkann, fara 10 skref This vegur, eða vinstri takkann, fara 10 skref This vegur, 10 skref sem. Ég hef greinilega sneri köttinn í frosk. Svo er það bara þar sem búningur, eins Scratch símtöl it-- vér bara flutt mynd af froskinn. 

En hvað er að gerast? Hvaða önnur línur af kóða, hvað aðrir stykki púsluspil gerði Blake, kennsla náungi okkar, nota í þessu forriti, virðist? Hvað er að gera allt move-- hvað forritun reisa? 

Hreyfing, sure-- svo færa blokk, fyrir viss. Og hvað er það að færa blokk inni, líklega? Já, einhvers konar lykkju, kannski eilífu loka, kannski endurtaka block-- endurtaka þar til blokk. Og það er það sem er að gera logs og The Lily pads og allt annað færa fram og til baka. Það er bara að gerast endalaust. 

Hvers vegna eru nokkrar af þeim bílum áhrifamikill hraðar en aðrir? Hvað er öðruvísi um þá forrit? Já, sennilega sumir af þeim eru notuð fleiri skref í einu og sumir af þeim færri skref í einu. Og sjónræn áhrif er fljótur móti hægt. 

Hvað finnst þér gerðist? Þegar ég fékk frosk minn alla leið yfir götuna og árinnar inn á Lily púði, eitthvað athyglisvert gerðist. Hvað gerðist um leið og ég gerði það? Það hætt. Það froskur hætt, og Ég fékk annað froskur. Svo það reisa verður nota það, hvað eiginleiki? 

Já, svo er það einhvers konar "Ef" ástand þarna líka. Og það kemur out-- við ekki sjá this-- en það er önnur blokkir þarna sem má segja, ef þú ert að snerta annar hlutur á skjánum, ef þú ert að snerta Lily púði, "þá." Og þá er það þegar við gera annað froskur birtast. Svo jafnvel þótt þessi leikur er vissulega mjög dagsett, jafnvel þótt við fyrstu sýn það er svo mikið að fara skráin og Blake ekki svipa þetta upp í tvær mínútur, það tók sennilega honum nokkrir klukkustundir að búa til þennan leik byggt á minni hans eða myndskeið af útgáfu fyrra er af henni. En allar þessar litlu hluti fara á skjánum í einangrun sjóða niður í þessar mjög einfalt constructs-- hreyfingar eða yfirlýsingar eins og við höfum rætt, lykkjur og skilyrði, og það er um það. Það er nokkrar aðrar áhugamaður lögun. Sumir þeirra eru eingöngu fagurfræði eða hljóðeinangrun, eins hljóðum sem ég spilaði bara með. En að mestu leyti, að hafa í þessu tungumáli, klóra, allt grundvallaratriði kubbar sem þú hafa í C, Java, JavaScript, PHP, Ruby, Python, og fjölda annarra tungumála. Einhverjar spurningar um grunni? Allt í lagi. Þannig að við munum ekki kafa dýpra til grunni, þó þú ert velkominn um helgina, sérstaklega ef þú ert með krakka eða dætur og nephews og svo, að kynna þeim grunni. Það er í raun frábærlega fjörugur umhverfi með, eins og höfundar hennar segja, mjög há loft. Jafnvel þó að við byrjuðum með mjög lágmark-láréttur flötur upplýsingar, þú getur raunverulega gert töluvert með það, og þetta er kannski sýning á einmitt það. 

En við skulum nú yfir í meira háþróuð vandamál, ef þú vilt, þekktur sem "leita" og "Flokkun" almennt. Við höfðum þetta símaskrá earlier-- hér er annað bara fyrir discussion-- sem við gátum til að leita á skilvirkari hátt vegna þess að verulegs forsendu. Og bara til að vera skýr, hvað forsenda var ég að gera þegar að leita í gegnum þetta símaskránni? Það Mike Smith var árið símaskrá, þótt ég vildi vera fær um að takast atburðarás án hans það ef ég hætti bara snemma. Bókin er stafrófsröð. Og það er mjög örlátur forsenda, því að þýðir someone-- ég er svona klippa horn, eins og ég er hraðari vegna einhvers annars gerði mikið af vinnu fyrir mig. 

En hvað ef síminn Bókin var óflokkuðu? Kannski Regin fékk latur, bara kastaði nöfn allra og tölur þar kannski í þeirri röð sem þau skráði sig fyrir símaþjónustu. Og hversu miklum tíma tekur það mig að finna einhvern eins og Mike Smith? 1.000 síðu sími book-- hversu margir síður þarf ég að horfa í gegnum? 

Öllum þeim. Þú ert svona út af heppni. Þú þarft bókstaflega að líta á hvert síðu ef síminn bókin er bara handahófi flokkað. Þú might fá heppinn og finna Mike á fyrstu síðu, vegna þess að hann var fyrsti viðskiptavinurinn að panta símaþjónustu. En hann gæti hafa verið síðasta líka. 

Svo er af handahófi röð ekki gott. Svo býst við að raða í símaskrá eða á almennum raða gögnum sem við höfum verið gefið. Hvernig getum við gert það? 

Jæja, láttu mig reyna bara einfalt dæmi hér. Leyfðu mér að fara á undan og henda a Nokkrar tölur um borð. Segjum tölur sem við höfum eru, við skulum segja, fjórir, tveir, einn, og þrjú. Og Ben, raða þessar tölur fyrir okkur. 

Allt í lagi gott. Hvernig gerðir þú þetta? Allt í lagi. Svo byrja með minnstu gildi og hæsta, og það er mjög gott innsæi. Og ljóst að við menn eru í raun frekar gott að leysa vandamál eins og þetta, að minnsta kosti þegar gögnum er tiltölulega lítill. Um leið og þú byrjar að hafa hundruð af tölum, þúsundir tölum, milljónir tölur, Ben sennilega gat ekki gert það alveg að hratt, að því gefnu að það væri eyður í tölurnar. Nokkuð auðvelt að telja upp að milljón annars, bara tímafrekt. 

Svo reiknirit það hljómar eins Ben notað bara núna var að leita fyrir minnstu númer. Svo jafnvel þó að við mennirnir getum tekið í fullt af upplýsingum sjónrænt, tölvan er í raun svolítið meira takmarkaður. Tölvan getur aðeins líta á eitt bæti í einu eða kannski fjögur bæti á a time-- þessa dagana kannski 8 bytes á a time-- en mjög lítill fjöldi bytes á hverjum tíma. 

Svo í ljósi þess að við höfum í raun fjögur aðskilin gildi here-- og hægt er að hugsa um Ben sem hafa augnskjól ef hann væri tölvan slík að hann getur ekki séð neitt annað en eitt númer í time-- svo við almennt mun gera ráð fyrir, eins og í English, munum við lesa frá hægri til vinstri. Svo fyrsta númerið Ben sennilega litið á var fjögurra og þá mjög fljótt komust að því er ansi stór number-- láta mig halda að leita. 

Það er tveggja. Bíddu aðeins. Tveggja er minni en fjórir. Ég ætla að muna. Tvö er nú minnsti. Nú er one-- jafnvel betra. Það er jafnvel minni. Ég ætla að gleyma um tvo og bara muna eitt núna. 

Og gæti hann hætt að leita? Jæja, gat hann byggt á þessum upplýsingum, en hann myndi betri leit restin af listanum. Vegna þess hvað ef núll voru á listanum? Hvað ef neikvætt einn voru á listanum? Hann veit bara að svar hans er rétt ef hann er tæmandi skoðaði alla lista. Þannig að við líta á the hvíla af þessu. Three-- sem var tímasóun. Fékk óheppinn, en ég var enn rétt til að gera það. Og svo nú er hann væntanlega valinn minnsti fjöldi og bara setja það í upphafi á listanum, eins og ég geri hér. Nú hvað gerðirðu næst, jafnvel þótt þú ekki að hugsa um það næstum að þessu leyti? Endurtaka ferlið, svo einhvers konar lykkju. Það er kunnuglegt hugmynd. Svo hér er fjórir. Það er nú minnsti. Það er frambjóðandi. Ekki lengur. Nú hef ég séð tvö. Það er næsta minnsti þátturinn. Three-- það er ekki minni, svo Nú Ben getur slíta út tvö. 

Og nú erum við að endurtaka ferlið og auðvitað þremur fær dreginn út næst. Endurtaka ferlið. Four fær dreginn út. Og nú erum við út af tölum, svo listinn verður flokkaður. 

Og reyndar, þetta er formleg reiknirit. A tölva vísindamaður myndi kalla þetta "val tagi," hugmyndin er að raða a lista iteratively-- aftur og aftur og aftur velja minnsti fjöldi. Og hvað er gott um það er það er bara svo fjári innsæi. Það er svo einfalt. Og er hægt að endurtaka sama rekstur aftur og aftur. Það er einfalt. 

Í þessu tilviki var það hratt, en hversu langan tíma tekur það í raun og veru? Við skulum gera það virðast og feel a lítill fleiri leiðinlegur. Svo einn, tveir, þrír, fjórir, fimm sex, sjö, átta, níu, 10, 11, 12, 13, 14, 15, 16-- handahófskennt númer. Ég vildi bara meira á þessu tími en bara fjórum. Svo ef ég hef fengið heild fullt af tölum now-- það skiptir ekki einu sinni máli hvað þeir are-- skulum hugsa um hvað þetta reiknirit er í raun eins. 

Segjum að það eru tölur þar. Aftur, skiptir ekki máli hvað þeir eru, en þeir eru af handahófi. Ég sæki reiknirit Ben er. Ég þarf að velja minnstu númer. Hvað geri ég? Og ég ætla að líkamlega gera það í þetta sinn til að bregðast hana út. Horft, útlit, leita, leita, leita. Aðeins með þeim tíma sem ég fá að í lok listanum getur Ég geri mér grein minnsti Fjöldi var tveggja þetta sinn. Einn er ekki á listanum. Svo ég setti niður tvö. 

Hvað á ég að gera næst? Horft, útlit, útlit, útlit. Nú er ég fann númerið sjö, því það er eyður í þessum Numbers en bara handahófskennt. Allt í lagi. Svo nú get ég sett niður sjö. Leita að, leita. 

Nú er ég hrokafullur, af Auðvitað, að Ben ekki hafa auka RAM, auka minni, vegna þess, að sjálfsögðu, Ég er að horfa á sama númer. Víst hefði ég mundi allar þær tölur, og það er alveg satt. En ef Ben man alla númera hann séð, Hann hefur í raun ekki gert grundvallaratriði framfarir vegna þess að hann hefur nú þegar getu til að leita í gegnum tölurnar á borðinu. Muna allt í Tölurnar hjálpar ekki, vegna þess að hann getur enn sem tölvu aðeins að líta á, að við höfum sagt, eitt númer í einu. Þannig að það er engin svoleiðis svindl þar sem hægt er að nýta. 

Svo í raun, eins og ég halda áfram að leita á listanum, Ég hef bókstaflega bara að halda áfram fram og til baka í gegnum það, plokkun út næsta minnsti fjöldi. Og eins og þú getur konar álykta frá kjánalegt hreyfingum mínum, þetta verður bara mjög leiðinlegur mjög fljótt, og ég virðist vera að fara til baka og fram, fram og til baka töluvert. Nú til að vera sanngjarn, ég er ekki að fara alveg eins vel, við skulum see-- að vera sanngjarn, Ég þarf ekki að ganga alveg sem margir stíga hvert skipti. Vegna þess, að sjálfsögðu, eins og ég velja númer af listanum, sem eftir listi er að fá styttri. 

Og svo skulum hugsa um hversu mörg skref ég er reyndar traipsing gegnum hvert skipti. Í fyrstu stöðu við höfðum 16 tölur, og svo maximally-- skulum bara gera þetta fyrir discussion-- Ég þurfti að horfa í gegnum 16 tölur til að finna minnstu. En þegar ég kippti út minnsti fjöldi, hvernig lengi var eftirstandandi lista, auðvitað? Bara 15. Svo hversu margar tölur gerðu Ben eða ég hef að líta í gegnum annað sinn í kring? 15, bara að fara og finna minnstu. En nú, auðvitað, listinn er, of, minni en hún var áður. Svo hversu mörg skref gerði ég þarft að taka næst? 14 og síðan 13 og svo 12, plús punktur, punktur, punktur, þar til ég er vinstri með bara einn. Svo nú tölvunarfræðingur myndi spyrja, vel, hvað þýðir að allir jafnir? Það jafngildir í raun smá steypu tala sem við gátum vissulega gera arithmetically, en við viljum að tala um skilvirkni reiknirit smá meira formulaically, óháð hversu lengi listinn er. 

Og svo þú veist hvað? Þetta er 16, en eins og ég sagði áður, við skulum bara kalla stærð vandans n, þar sem n er einhver númer. Kannski er það 16, kannski er það þrír, kannski er það milljón. Ég veit ekki. Mér er alveg sama. Það sem ég vil virkilega er uppskrift sem ég get nota til að bera saman þessa reiknirit gegn öðrum reiknirit að einhver gæti krafa eru betri eða verri. 

Svo kemur í ljós, og ég bara veit þetta af grunnskóla, að þetta virkar í raun út á það sama hlutur sem n yfir n plús einn yfir tvö. Og þetta gerist til að jafna, af Auðvitað n veldi plús n yfir tvö. Þannig að ef ég vildi formúlu fyrir hversu mörg skref tóku þátt í að horfa á alla þær tölur aftur og aftur og aftur og aftur, myndi ég segja það er n veldi plús n yfir tvö. En þú veist hvað? Þetta lítur bara sóðalegur. Ég bara virkilega a almennum skilningi hlutanna. Og þú gætir muna frá menntaskóla að það er hugmyndin um hæsta röð tíma. Hver af þessum skilmálum, n í öðru veldi, N, eða helmingur, hefur mest áhrif með tímanum? The allstór n fær, sem af þessum málum sem mest? 

Með öðrum orðum, ef ég stinga í milljón, n veldi er að fara að vera líklegur ríkjandi þáttur, því milljón sinnum sjálft er mikið stærri en auk einn til viðbótar milljón. Svo þú veist hvað? Þetta er svo fjári stór númer ef þú ferningur númer. Þetta skiptir ekki máli. Við erum bara að fara kross sem út og gleyma óður í það. Og svo tölvunarfræðingur myndi segja að skilvirkni þessarar reiknirit er á röð n squared-- Ég meina sannarlega nálgun. Það er tegund af gróflega n veldi. Með tímanum, stærri og stærri n fær þetta er gott mat á hvað skilvirkni eða skortur á skilvirkni þessarar reiknirit í raun er. Og ég reikna að sjálfsögðu, frá raun að gera stærðfræði. En núna er ég bara að veifa hendur mínar, því ég bara langar almenna tilfinningu þessarar reiknirit. 

Svo nota sömu rökfræði, á meðan, skulum íhuga annað reiknirit við skoðuðum þegar at-- línulega leit. Þegar ég var að leita fyrir síma book-- Ekki flokkun og leita gegnum síma book-- við haldið segja að það væri 1.000 skrefum, eða 500 skref. En við skulum alhæfa það. Ef það er n síður í símaskrá, hvað er gangi sinn eða skilvirkni línuleg leit? Það er á röð hversu mörg skref til að finna Mike Smith nota línulega leit er Fyrsta reiknirit, eða jafnvel annað? 

Í versta tilfelli, Mike er í lok bókarinnar. Svo ef síminn bókin hefur 1.000 síður, sagði að við síðasta skipti, í versta tilfelli, það gæti tekið u.þ.b. hversu margar síður til að finna Mike? Eins 1.000. Það er efri. Það er versta mögulega ástand. En aftur, við erum að flytja í burtu frá tölum eins 1.000 núna. Það er bara n. 

Svo er það rökrétt niðurstaða? Finndu Mike í símann bók sem hefur n síður gæti tekið, í mjög versta tilfelli, hversu mörg skref á röð n? Og raunar tölvu vísindamaður myndi segja sem gangi tíma, eða á árangur eða skilvirkni eða óhagkvæmni, af reiknirit eins línulegt leit er á röð á n. Og við getum beita sömu Röksemdafærsla yfir eitthvað út eins og ég gerði bara til seinni reiknirit sem við höfðum með símaskrá, þar sem við fórum tvær síður í einu. 

Svo 1.000 síðu símaskrá gætu taka okkur 500 page beygjur, plús einn ef við tvöfalda baka svolítið. Svo ef símaskrá hefur n síður, en við erum að gera tvær síður í einu, það er u.þ.b. hvað? N á tveimur, þannig að það er eins og n yfir tveimur. En ég gerði kröfu stund síðan að n yfir two-- það er góður af the sami eins og bara n. Það er bara stöðug þáttur, tölva vísindamenn myndi segja. Við skulum bara einblína á breytur, really-- stærsta breytur í jöfnunni. 

Svo línuleg leit, hvort sem gert einn síðu í einu eða tvær síður í einu, er tegund af grundvallaratriðum sú sama. Það er samt á röð n. En ég hélt með myndina mína áðan að þriðja algrím var ekki línuleg. Það var ekki beina línu. Það var það sveigð lína, og algebrulegt uppskrift var það? Log um n- svo log stöð tvö af n. Og við þurfum ekki að fara út í of mikið smáatriði á logra dag, en flestir tölva vísindamenn myndu ekki jafnvel segja þér hvað stöð er. Vegna þess að það er allt bara stöðug þættir, svo að segja, bara hirða tölugildi munur. Og svo þetta væri mjög algeng leið fyrir sérstaklega formlegrar tölvuna Vísindamenn á borð eða forritari á hvítt borð reyndar með þeim rökum sem algrím þeir myndu nota eða hvað skilvirkni af reiknirit þeirra er. 

Og þetta er ekki endilega eitthvað þú ræða í hvaða smáatriðum, en góður forritari er einhver sem hefur traustan, formlega bakgrunni. Hann er fær um að tala við þú í svona hátt og í raun gera eigindlegar rök sem að hvers vegna einn reiknirit eða eitt stykki af hugbúnaður er betri á einhvern hátt til annars. Þar sem þú gætir örugglega bara keyra forritið ein manneskja er og telja fjölda sekúndur það tekur að raða nokkrar tölur, og þú getur keyrt sum Forritið hins aðilans og telja fjölda um sekúndur sem það tekur. En þetta er meira almenn leið að þú getur notað til að greina reiknirit, ef þú vilt, bara á pappír eða bara munnlega. Án þess þó að keyra það, án þess að jafnvel að reyna sýni inntak, þú getur bara rökrætt gegnum það. Og svo með að ráða verktaki eða ef að hafa hann eða hana svoleiðis að halda því fram við þig hvers vegna reiknirit þeirra, leyndarmál þeirra sósa til að leita milljörðum vefsíðum fyrir þinn Félagið er betra, þessir eru konar rök sem þeir ætti helst að vera fær um að gera. Eða að minnsta kosti að þetta eru hvers konar hluti sem myndi koma upp í umræðu á amk í mjög formlegum umræðum. Allt í lagi. Svo Ben lagt eitthvað kallaði val tegund. En ég ætla að leggja til að það er aðrar leiðir til að gera þetta líka. Það sem ég gerði í raun ekki eins um reiknirit Ben er er að hann hélt gangandi eða hafa mig ganga, fram og til baka og fram og til baka og fram og til baka. Hvað ef í stað ég væri að gera eitthvað eins og þessar tölur hér og ég var bara að takast á við hvert Fjöldi á móti eins og ég gefið henni? 

Með öðrum orðum, hér er minn listi af tölum. Four, einn, þrír, tveir. Og ég ætla að gera eftirfarandi. Ég ætla að setja inn tölurnar þar sem þeir tilheyra frekar en að velja þá einn í einu. Með öðrum orðum, hér er númer fjögur. 

Hér er upprunalega lista minn. Og ég ætla að halda í raun nýjan lista hér. Svo er þetta gamla lista. Þetta er nýja lista. Ég sé númer fjögur fyrst. Ný minn listi er upphaflega tóm, svo það er trivially raunin sem fjögur er nú blandað lista. Ég ætla bara að taka fjölda ég gefið, og ég ætla að setja það í nýjan listanum mínum. 

Er þetta nýr listi flokkuð? Já. Það er heimskulegt vegna þess að það er bara ein þáttur, en það er algerlega flokkað. Það er ekkert af stað. Það er meira áhugavert, þetta reiknirit, þegar ég flyt í næsta skref. 

Nú hef ég einn. Svo einn, auðvitað, tilheyrir í síðasta upphafi eða við lok þessarar nýju listanum? Byrjunin. Svo ég verð að gera sumir vinna núna. Ég hef verið að taka nokkrar frelsi með prjónamerki mitt bara með því að teikna hluti þar sem ég vil þá, en það er í raun ekki nákvæmur í tölvu. A tölva, eins og við vitum, hefur RAM, eða Random Access Memory, og það er eitt bæti og annar bæti og annar bæti. Og ef þú ert með gígabæti af RAM, hefur þú milljarð bytes, en þeir eru líkamlega á einum stað. Þú getur ekki bara að færa efni kring með því að teikna hana á borð hvar sem þú vilt. Svo ef nýr listi mitt hefur fjórum stöðum í minni, Því miður er fjögur er þegar á röngum stað. 

Svo að setja númer eitt Ég get ekki bara draga það hér. Þetta minni staðsetningu er ekki til. Það væri að svindla, og ég hef verið svindla á myndrænan í nokkrar mínútur hér. Svo í raun, ef ég vil setja einn hér, Ég verð að tímabundið afrita fjórum og þá setja einn þar. 

Það er allt í lagi, það er rétt, það er tæknilega mögulegt, en ljóst að er auka vinna. Ég vissi ekki bara að setja númerið í stað. Ég þurfti fyrst að fara á tala, þá setja það í stað, svo ég tvöfaldast konar magn mínu starfi. Svo halda að í huga. 

En ég er nú búin með þennan þátt. Nú vil ég að grípa númer þrjú. Þar sem, að sjálfsögðu, er það tilheyra? Þar á milli. Ég get ekki svindla lengur og bara setja það þar, vegna þess, aftur, þetta minni er í líkamlegum stöðum. Svo ég verð að afrita fjórum og setja þrjá hérna. Ekki mikið mál. Það er bara eitt auka skref again-- finnst mjög ódýrt. 

En núna er ég að fara á tveimur. Tveir, að sjálfsögðu, tilheyrir hér. Nú getur þú byrjað að sjá hvernig vinna getur hrannast upp. Nú hvað þarf ég að gera? Já, ég verð að færa fjórir, Ég hef þá að afrita þrjú, og nú get ég sett tvö. Og aflinn við þetta reiknirit, Athyglisvert nóg, er að gera ráð fyrir að við höfum fleiri Extreme Málið þar sem það er skulum segja átta, sjö, sex, fimm, fjórir, þrír, tveir, einn. Þetta er, í mörgum samhengi, versta falli, vegna þess að fjári hlutur er bókstaflega aftur á bak. 

Það skiptir í raun ekki áhrif reiknirit Ben er, vegna þess að í Ben er val tegund hann er að fara að halda fara fram og til baka í gegnum listann. Og vegna þess að hann var alltaf að leita í gegnum allt eftir listanum, það skiptir ekki máli þar sem þættir eru. En í þessu tilfelli með því að setja mína approach-- skulum reyna þetta. 

Svo einn, tveir, þrír, fjórir, fimm, sex, sjö, átta. Einn tveir þrír fjórir, fimm, sex, sjö, átta. Ég ætla að taka átta, og hvar á ég að setja það? Jæja, í upphafi listanum mínum, vegna þess að þetta nýja lista er raðað. Og ég yfir það út. 

Hvar set ég sjö? Fjári það. Það þarf að fara þangað, svo Ég verð að gera sumir afritun. Og nú sjö fer hér. Nú er ég að fara á sex. Nú er það jafnvel meiri vinna. 

Átta þarf að fara hér. Seven þarf að fara hér. Nú sex hægt að fara hér. Nú er ég grípa fimm. Nú hefur átta til að fara hér sjö þarf að fara hér, sex þarf að fara hér, og nú fimm og endurtaka. Og ég er ansi mikið færa það stöðugt. 

Svo í lok, þetta algorithm-- við munum kalla það innsetning sort-- raun hefur mikið af vinnu líka. Það er bara öðruvísi konar vinnu en Ben er. verk Bens lét mig fara fram og til baka allan tímann, að velja næsta minnstu frumefni aftur og aftur. Svo það var þetta mjög sjónræn tagi vinna. 

Þessi annar reiknirit, sem er enn correct-- það vilja fá the starf done-- bara breytir magn af vinna. Það lítur út eins fyrst þú ert sparnaður, vegna þess að þú ert bara takast á við hvert frumefni upp að framan án þess að ganga alla leið í gegnum listann eins Ben var. En vandamálið er, sérstaklega í þessum brjálaður tilfelli þar sem það er allt aftur á bak, þú ert bara svona fresta vinnusemi þangað til þú þarft að festa mistök. 

Og svo ef þú getur ímyndað þetta átta og sjö og sex og fimm og síðar fjórir og þrír og tveir flytja leið sína í gegnum listann, við höfum bara breytt tegund vinnu sem við erum að gera. Í stað þess að gera það á upphaf endurtekning minn, Ég ætla bara að gera það á sem enda hverjum endurtekning. Svo kemur í ljós að þetta reiknirit, of, yfirleitt kölluð innsetning flokka, er einnig á röð af n veldi. Það er í raun engin betri, ekkert betra á öllum. 

Hins vegar er þriðja nálgun Ég myndi hvetja okkur til að íhuga, sem er þetta. Svo býst listanum mínum, fyrir einfaldleika aftur, er fjórir, einn, þrír, two-- bara fjórar tölur. Ben hafði gott innsæi, gott mannlegt innsæi áður, sem við fast allt listi eventually-- innsetningu konar. Ég coaxed okkur eftir. En við skulum íhuga Einfaldasta leiðin til að laga þennan lista. 

Þessi listi er ekki raðað. Hvers vegna? Á ensku, útskýra hvers vegna það er í raun ekki raðað. Hvað þýðir það ekki að vera flokkaður? 

STUDENT: Það er ekki kaflaskipt. 

DAVID Malan: Ekki myndaröð. Gefðu mér dæmi. 

STUDENT: Setjið þá í röð. 

DAVID Malan: Allt í lagi. Gefðu mér meira ákveðna dæmi. 

STUDENT: Hækkandi röð. DAVID Malan: Ekki hækkandi röð. Vera nákvæmari. Ég veit ekki hvað þú átt við með hækkandi. Hvað er að? 

STUDENT: minnsti númer er ekki í fyrsta pláss. 

DAVID Malan: Minnsta númer er ekki í fyrsta pláss. Vera nákvæmari. Ég er farin að veiða á. Við erum að telja, en hvað er út af röð hér? 

STUDENT: Tölulegar röð. DAVID Malan: Töluleg röð. Allra konar gæsla það here-- mjög háu stigi. Bara bókstaflega segja mér hvað er rangt eins og fimm ára gamall mætti. 

STUDENT: Plús einn. 

DAVID Malan: Hvað er það? 

STUDENT: Plús einn. 

DAVID Malan: Hvað meinarðu plús einn? Gefðu mér annan fimm ára. Hvað er rangt, mamma? Hvað er rangt, pabbi? Hvað meinarðu þetta er ekki raðað? 

STUDENT: Það er ekki rétti staðurinn. 

DAVID Malan: Hvað er ekki á réttum stað? 

STUDENT: Four. DAVID Malan: Allt í lagi, gott. Svo fjögur er ekki þar sem það ætti að vera. Einkum er þetta rétt? Four og einn, fyrstu tvær tölur sem ég sé. Er þetta rétt? Nei, þeir eru út af röð, ekki satt? Í raun held nú um tölvu líka. Það getur aðeins að líta á kannski einn, kannski tvennt á once-- og í raun aðeins eitt í einu, en það getur að minnsta kosti líta á eitt þá Næsta hlutur við hliðina á henni. 

Svo eru þessir í röð? Auðvitað ekki. Svo þú veist hvað? Hvers vegna eigum við ekki að taka barnið skref ákveða þetta vandamál í stað þess að gera þessar ímynda reiknirit eins Ben, þar hann er svona að ákveða það með lykkja í gegnum listann í stað þess að gera það sem ég gerði, þar sem Ég fastur bara svona það sem við förum? Við skulum bara bókstaflega brjóta niður Hugtakið order-- töluröð, kalla það hvað sem þú want-- í þessum parasamanburður. 

Four og einn. Er þetta rétt röð? Svo skulum laga það. Einn og fjórir, og þá við verðum bara að afrita það. Allt í lagi, gott. Ég fastur einn og fjórir. Þrír og tveir? Nei Látum orð mín passa fingur mína. Four og þremur? 

Það er ekki í röð, þannig að ég ætla að gera eitt, þrír, fjórir, tveir. Allt í lagi gott. Nú fjórum og tveimur? Við þurfum að laga þetta líka. Svo einn, þrír, tveir, fjórir. Svo er það flokkað? Nei, en það er nær flokkað? 

Það er, vegna þess að við fastur þetta mistök, fast við þetta mistök, og við fast þetta mistök. Þannig að við fast þrjár mistök að öllum líkindum. Enn er í raun ekki líta raðað, en það er hlutlægt nær að raðað vegna þess að við fast sum þessara mistökum. 

Nú hvað á ég að gera næst? Ég náði konar enda á listanum. Ég virtist hafa fasta allir mistök, en nei. Vegna þess að í þessu tilfelli, nokkrar tölur gæti hafa loftbólum í upp nær að aðrar tölur sem eru enn út af röð. Svo skulum gera það aftur, og ég ætla bara gera það í stað að þessu sinni. Einn og þremur? Það er fínt. Þrír og tveir? Auðvitað ekki, þannig að við skulum breyta því. Svo tveir, þrír. Þrír og fjórir? Og nú skulum bara vera sérstaklega smámunasamur hér. Er það flokkað? Þú menn vita að það er flokkað. 

Ég ætti að reyna aftur. Svo Olivia er að leggja ég að reyna aftur. Hvers vegna? Vegna þess að tölvan er ekki með lúxus manna augum okkar á bara glancing back-- lagi, ég er búin. Hvernig virkar tölvan ákveða að listinn er nú flokkaður? Vélrænt. 

Ég ætti að fara í gegnum einu sinni enn, og aðeins ef ég ekki gera / finna einhver mistök get ég þá gera eins og the tölva, jebb, við erum gott að fara. Svo einn og tveir, tveir og þrír, þrír og fjórir. Nú get ég endanlega segja að þetta er flokkað, því ég gerði engar breytingar. Nú það væri padda og bara heimska ef ég, tölvan, spurði sömu spurninga aftur búast við mismunandi svör. Ætti ekki að gerast. 

Og svo nú listinn er raðað. Því miður, hlaupandi tími þetta reiknirit er einnig n veldi. Hvers vegna? Þar sem þú hefur n tölur, og í versta tilfelli þú þarft að færa n tölur n sinnum vegna þess að þú þarft að halda áfram baka til að athuga og hugsanlega festa þessar tölur. Og við getum gert meira formleg greining líka. 

Svo er þetta allt að segja að við höfum tekið þrjár mismunandi aðferðir, einn þeirra strax innsæi the kylfa frá Ben að leiðbeinandi innsetningu minn tegund í þessu einn þar sem þú missir konar sjónar á skógurinn fyrir trjánum í upphafi. En svo ef þú tekur skref til baka, Voila, höfum við fast í flokkun hugmynd. Þannig að þetta er, þora að segja, lægra verði kannski en sumir af þeim annað reiknirit, en við skulum sjá hvort við getum ekki sjón þetta með því að þetta. 

Svo er þetta sumir ágætur Hugbúnaðurinn sem einhver skrifaði nota litrík bars sem er fara að gera eftirfarandi fyrir okkur. Hver af þessum börum táknar fjölda. Hærri bar, stærri fjöldi, minni bar, minni númer. Svo fullkomlega við viljum gott pýramída þar sem það byrjar lítill og fær stór, og sem myndi þýða að þessi barir eru flokkuð. Þannig að ég ætla að fara á undan og velja, til dæmis, reiknirit Bens first-- val tegund. 

Og taka eftir hvað það er að gera. Leiðin sem þeir hafa kosið að sjón þessa reiknirit er það bara eins og ég var að ganga í gegnum listann minn, þetta forrit er að ganga gegnum lista með tölum, undirstrika í bleiku hverju tala sem það er að horfa á. Og hvað er að gerast núna? 

Minnsti fjöldi sem Ég eða Ben fann skyndilega fær flutt til the byrjun af listanum. Og eftir að þeir gerðu evict fjöldi sem var þarna, og það er fullkomlega í lagi. Ég vissi ekki að fá inn í þessi stigi smáatriðum. En við þurfum að setja að tala einhvers staðar, þannig að við fluttum bara það til opinn blettur sem var búin til. Þannig að ég ætla að flýta þessu upp, því annars verður mjög leiðinlegur fljótt. Fjör speed-- þar sem við förum. Svo nú sama lögmál Ég var að sækja um, en þú getur byrjað að líða reiknirit, ef þú mun, eða sjá það svolítið betur. Og þetta reiknirit hefur þau áhrif að velja næsta minnstu frumefni, svo þú ert að fara að byrja að sjá það pallinum upp á vinstri. Og á hverjum endurtekning, eins og ég lagt, er það smá minni vinna. Það þarf ekki að fara alla leið aftur til vinstri lok lista, vegna þess að það sem þegar þekkir þá eru flokkuð. Svo mér finnst svona eins og það er hraða, jafnvel þótt hvert skref er taka sama magn af tíma. Það er bara færri skrefum eftir. Og nú þú getur konar finnst reiknirit þrífa upp endann á henni, og reyndar nú er flokkað. 

Svo er allt gert innsetning tegund. Ég þarf að koma aftur randomize fylkisins. Og eftir ég get bara halda Randomizing henni, og við munum fá nálgun á sama aðferð, innsetning flokka. Leyfðu mér að hægja hann niður til hér. Við skulum byrja að yfir. Hætta. 

Við skulum sleppa fjórir. Þar sem við förum. Randomize array þeir. Og hér erum við go-- innsetningu konar. Spila. Takið eftir að það er að fást við hverju þáttur það kynni strax, en ef það tilheyrir rangur staður tilkynningu alla vinnu sem þarf að gerast. Við verðum að halda breytast meira og fleiri þætti til að búa til pláss fyrir einn við viljum setja í stað. 

Þannig að við erum með áherslu á vinstri enda aðeins listanum. Taka við höfum ekki einu sinni litið at-- vér hafa ekki lögð áhersla á bleiku neinu til hægri. Við erum bara að fást við vandamálin sem við förum, en við erum að búa til mikið af vinna fyrir okkur enn. Og svo ef við flýta þessu upp nú að fara að ljúka, það hefur mismunandi feel til það örugglega. Það er bara að einblína á vinstri enda en gera smá meiri vinnu sem needed-- konar refur hlutum yfir, ákveða hlutina, en fást að lokum með hver þáttur einn í einu þar til við fáum að the-- vel, við Allir vita hvernig þetta er að fara að enda, svo það er lítið underwhelming kannski. 

En listinn í end-- spoiler-- er að fara að vera flokkaður. Svo skulum líta á eitt síðasta. Við getum ekki bara sleppa því núna. Við erum næstum þarna. Tveir til að fara, einn að fara. Og voila. Excellent. 

Svo nú skulum gera eitt síðasta einn, aftur Randomizing með kúla tagi. Og eftir hér, sérstaklega ef ég hægja hana niður, þetta er að halda swooping gegnum. En eftir það gerir bara pöruðum comparisons-- konar staðbundnar lausnir. En um leið og við komum til í lok listanum í bleikur, hvað er að fara að þurfa að gerast aftur? Já, það er að fara að þurfa að start over, vegna þess að það bara fastur parasamanburður mistök. Og það gæti hafa leitt í ljós enn aðra. Og svo ef þú flýta þessu upp, þú munt sjá að mikið eins og nafnið gefur til kynna, minni elements-- eða öllu heldur, stærri elements-- eru farin að kúla upp til the toppur, ef þú vilt. Og smærri þættir eru byrja að kúla niður til vinstri. Og reyndar, það er góður af sjónræn áhrif eins og heilbrigður. Og svo þetta mun enda upp klára á mjög svipaðan hátt líka. 

Við þurfum ekki að búa á þessu tiltekna einn. Leyfðu mér að opna þetta núna líka. Það er nokkrar aðrar flokkun reiknirit í heiminum, nokkrar sem eru teknar hér. Og sérstaklega fyrir nemendur sem eru ekki endilega sjón eða stærðfræði, eins og við gerðum áður, við getum einnig að gera þetta audially Ef við tengjum hljóð með þetta. Og bara til gamans, hér er nokkrar mismunandi reiknirit, og einn af þeim í lagi að þú ert fara til tilkynningar er kallað "Mergesort." 

Það er í raun í grundvallaratriðum betri reiknirit, þannig að Mergesort, einn af þær sem þú ert að fara að sjá, er ekki röð n veldi. Það er á röð af n sinnum lóg af n, sem er í raun minni og svona hraðar en þeim hinum þremur. Og það er a par annar kjánalegt þau sem við munum sjá. 

Svo hér við fara með einhverjum hljóð. Þetta er innsetning tegund, svo aftur það er bara að takast á við þá þætti eins og þeir koma. Þetta er kúla tegund, þannig að það er miðað við þá pör í einu. Og aftur, stærsta þættir eru freyðandi upp á toppinn. 

Næst val tagi. Þetta er reiknirit Bens, þar aftur hann er að velja iteratively næsta minnstu þáttur. Og aftur, nú þú geta raunverulega heyra að það er hraðakstur upp en aðeins að því marki eins og það er að gera minna og minna vinna á hverri ítrun. Þetta er hraðari einn, Mergesort, sem er flokkun klasa af tölum saman og þá sameina þá. Svo look-- vinstri helmingur er þegar raðað. 

Nú það er að flokka rétt helminginn, og nú það er að fara að sameina þær í eina. Þetta er eitthvað sem kallast "Gnome tegund." Og þú getur konar séð það það er að fara fram og til baka, ákveða að vinna svolítið hér og það áður en það gengur til nýja vinnu. Og það er það. Það er annar tegund, sem er í raun bara fyrir fræðilegum tilgangi, kallað "heimskur tegund", sem tekur gögn, raðar því af handahófi, og þá athugar hvort það er flokkað. Og ef það er ekki, aftur skiptir það það handahófi, tékka ef það er raðað, og ef ekki endurtekur. Og í orði, probabilistically þetta mun ljúka, en eftir töluvert af tíma. Það er ekki mest duglegur reiknirit. Svo einhverjar spurningar um þá sérstaklega reiknirit eða eitthvað tengist það líka? 

Jæja, við skulum nú stríða sundur hvað allt þessar línur eru sem ég hef verið að teikna og það sem ég er hrokafullur tölvuna getur gert undir hetta. Ég myndi halda því fram að allar þessar tölur Ég að halda samningu þeir þurfa að fá geymdar einhvers staðar í minni. Við munum losna við þennan gaur núna, líka. 

Svo a stykki af minni í computer-- svo RAM DIMM er hvað við leitað gær, tvískiptur inline minni module-- lítur svona út. Og hver af þessum litlu svörtu flögum er einhver fjöldi bytes, yfirleitt. Og þá gull prjónar eru eins og vír sem tengja það við tölvuna, og græna sílikon borð er bara hvað heldur allt allt saman. Svo hvað þýðir þetta í raun? Ef ég teikna svona þetta sama mynd, við skulum gera ráð fyrir einfaldleika að þetta DIMM, tvískiptur inline minni mát, er einn gígabæti af RAM, einn gígabæti af minni, sem er hversu margir bæti alls? Einn gígabæti er hversu margir bæti? Meira en það. 1124 er kíló, 1.000. Mega er ein milljón. Giga er milljarð. 

Er ég að ljúga? Getum við lesið jafnvel merkið? Þetta er í raun 128 gígabæta, svo það er meira. En við munum láta þetta er bara einn gígabæti. Svo það þýðir að það er milljarður bæti af minni í boði fyrir mig eða 8 milljarðar bitar, en við erum að fara að tala í skilmálar af bæti nú, halda áfram. 

Svo hvað það þýðir er að þetta er eitt bæti, þetta er annar bæti, þetta er annar bæti, og ef við vildum virkilega til að vera nákvæm við yrðum að draga milljarð litla ferninga. En hvað þýðir það? Jæja, láttu mig súmma bara í á þessari mynd. Ef ég hef eitthvað sem lítur svona nú, það er fjögur bæti. 

Og svo ég gæti sett fjórar tölur hér. Einn tveir þrír fjórir. Eða ég gæti sett fjögur bréf eða tákn. "Hey!" gæti farið þarna, því að hver af bréfum, við ræddum áðan, mætti ​​fulltrúa með átta bitum eða ASCII eða bæti. Svo í öðrum orðum, getur þú setja 8 milljarða hlutina inni af þessum eina staf minni. Nú hvað þýðir það að setja hlutina aftur til baka til baka í minni svona? Þetta er það sem forritari myndi kalla "fylki". Í tölvuforriti, finnst þér ekki um undirliggjandi vélbúnaður, í sjálfu sér. Þú heldur bara um sjálfan þig og að hafa aðgangur að milljarð bytes samtals, og þú getur allt sem þú vilt með það. En fyrir þægindi það er yfirleitt gagnlegt að halda minni þitt rétt við hliðina á hvort öðru eins og þetta. Þannig að ef ég súmma inn á this-- vegna þess að við erum vissulega ekki að fara að draga milljarð smá squares-- skulum gera ráð fyrir að þetta borð táknar að standa af minni núna. Og ég ætla bara að teikna eins og margir eins minn merki endar gefa mig hér. Svo nú höfum spýtu minni á borð sem fékk einn, tveir, þrír, fjórir, fimm, sex, einn, tveir, þrír, fjórir, fimm, sex, seven-- svo 42 bæti af minni á samtals skjánum. Þakka þér. Já, gerði tölur minn rétt. Svo 42 bæti af minni hér. Svo hvað þýðir þetta í raun þýtt? Jæja, tölva forritari myndi reyndar almennt hugsa um þetta minni sem addressable. Með öðrum orðum, hver og einn af þessum stöðum í minni, í vélbúnaði, hefur einstakt tölu. 

Það er ekki eins flókið eins og eitt BRATTLE Square, Cambridge, Mass., 02138. Þess í stað, það er bara tala. Þetta er bæti númer núll, þetta er einn, þetta er tveir, þetta er þrír, og þetta er 41. Bíddu aðeins. Ég hélt að ég sagði 42 í smá stund síðan. Ég byrjaði að telja á núlli, svo það er í raun rétt. Nú erum við ekki að í raun draga það sem rist, og ef þú draga það sem rist Ég held að það í raun og veru fá dálítið villandi. Hvað forritari myndi, í hans eða hennar eigin huga, almennt hugsa um þetta minni sem er bara eins og borði, eins og a stykki af gríma borði sem bara fer á og á eilífu eða þar til þú keyrir út af minni. Svo algengari leið til að vekja og hugsa bara um minni væri verið að þetta sé bæti núll, einn, tveir, þrír, og þá punktur, punktur, punktur. Og þú ert 42 slíkar bytes alls, jafnvel þó líkamlega það gæti í raun og veru vera eitthvað meira svona. 

Svo ef þú heldur nú af þinn minni eins og þetta, rétt eins og borði, þetta er það sem forritari aftur myndi kalla á fjölbreytta minni. Og þegar þú vilt í raun og veru að geyma eitthvað í minni tölvu, þú gerir venjulega geyma hluti bak-til-bak við bak-til-bak. Þannig að við höfum verið að tala um tölur. Og þegar ég vildi til að leysa vandamál eins og fjögurra, einn, þrír, tveir, jafnvel þótt ég var bara að teikna aðeins tölurnar fjögur, einn, þrír, tveir á borð, tölvan myndi í raun hafa þetta skipulag í minni. 

Og hvað væri við hliðina á tvær í minni tölvunnar? Jæja, það er ekkert svar við því. Við í raun ekki vita. Og svo lengi sem tölva hjartarskinn ekki þurfa það, það þarf ekki að hugsa hvað er næst að tölurnar það gerir sama um. Og þegar ég sagði áðan að tölvu getur aðeins líta á eitt netfang í einu, þetta er góður af hverju. 

Ekki ólíkt met leikmaður og lestur höfuð aðeins að vera fær um að líta á ákveðin gróp í líkamlegu gamla skólann met í einu, álíka getur tölvan takk CPU hennar og þess Intel kennsla setja, meðal hverra kennsla er að lesa úr minni eða spara til memory-- a tölva getur aðeins líta á einum stað í time-- stundum a samsetning af þeim, en í raun bara einn stað í einu. Svo þegar við vorum að gera þessi mismunandi reiknirit, Ég er ekki bara að skrifa í vacuum-- fjórir, einn, þrír, tveir. Þær tölur tilheyra í raun einhvers staðar líkamlega í minni. Þannig að það eru pínulítill lítill smári eða einhvers konar rafeindatækni undir hetta geyma þessi gildi. 

Og í heild, eru hvernig margir bitar þátt núna, bara að vera skýr? Svo er þetta fjögur bæti, eða nú er það 32 bita alls. Þannig að það eru í raun 32 núll og Þeir semja þessum fjórum hlutum. Það er jafnvel meira hérna, en aftur við ekki sama um það. 

Svo nú skulum spyrja annan spurning með minni, vegna þess að að í lok dagsins er í dreifni. Sama hvað við gætum gert með tölva, í lok dags vélbúnaður er enn Sama undir hetta. Hvernig myndi ég geyma orð hér? Jæja, orð í tölvu eins og "Hey!" væri hægt að geyma bara svona. Og ef þú vildir vera lengur orð, þú getur einfaldlega skrifa það og segja eitthvað eins og "halló" og geyma það hér. 

Og svo hér líka, þetta contiguousness er í raun kostur, vegna þess að tölva getur bara lesa frá hægri til vinstri. En hér er spurning. Í tengslum við þetta orð, H-e-L-L-o, upphrópunarmerki, hvernig gæti tölvan vita hvar Bæta hefst og þar sem orðið endar? Í tengslum við tölum, hvernig virkar tölvan vita hversu lengi runa númer er eða hvar það byrjar? Jæja, það kemur out-- og við munum ekki fara of mikið í þessu stigi detail-- tölvur færa efni í kring í minni bókstaflega með því að þessi vefföng. Svo í tölvu, ef þú ert skrifa kóða til að geyma hluti eins orðum, hvað þú ert í raun að gera er að skrifa orðasambönd sem muna hvar í minni í tölvunni þessi orð eru. Svo láta mig gera mjög, mjög einfalt dæmi. 

Ég ætla að fara á undan og opna einfaldan texta program, og ég ætla að búa til skrá sem heitir hello.c. Flest af þessum upplýsingum við mun ekki fara í í smáatriðum, en ég ætla að skrifa Dagskráin í sama tungumáli, C. Þetta er miklu meira ógnandi, Ég myndi halda því fram, en grunni, en það er mjög svipað í anda. Í staðreynd, þessir hrokkið braces-- þú getur konar hugsa um hvað ég gerði bara eins og þetta. 

Við skulum gera þetta, í raun og veru. Þegar grænn fáni smellt gera eftirfarandi. Ég vil að prenta út "halló." Svo er þetta nú sauðakóðanum. Ég er svona blurring línurnar. Í C, þetta tungumál ég er að tala um þetta lína prenta halló reyndar verður "printf" með sumir svigum og hálf-hreinsun. 

En það er nákvæmlega sama hugmynd. Og þetta mjög notandi-vingjarnlegur "Þegar grænn fáni smellt" verður miklu meira Bogagöng "int helstu ógilt." Og þetta hefur í raun enga kortlagning, þannig að ég ætla bara að fara að hunsa það. En hrokkið axlabönd eru eins og boginn stykki púsluspil eins og þetta. 

Svo þú getur konar giska á. Jafnvel ef þú hefur aldrei forritað áður, hvað þýðir þetta forrit sennilega gera? Sennilega prentar halló með upphrópunarmerki. 

Svo skulum reyna það. Ég ætla að spara hana. Og þetta er, aftur, mjög gamla skólanum umhverfi. Ég get ekki smellt, ég get ekki dregið. Ég verð að slá skipanir. Svo ég vil að hlaupa program minn, svo Ég gæti gert þetta, eins hello.c. Það er skrá sem ég hljóp. En bíddu, ég er vantar skref. Hvað gerði við segjum er nauðsynlegt skref fyrir tungumál eins og C? Ég hef bara skrifað uppspretta númer, en hvað þarf ég? Já, ég þarf þýðanda. Svo á Mac minn hér, ég er með forrit sem heitir GCC, GNU C þýðanda, sem leyfir mér að gera this-- beygju Kóðinn minn í, munum við kalla það, vél númer. 

Og ég get séð það, aftur, eins og hér segir, þessir eru núll og sjálfur ég bara búin til úr uppspretta minn kóða, allar núllum og sjálfur. Og ef ég vil keyra minn program-- það gerist að vera kölluð a.out fyrir sögulegu reasons-- "halló." Ég get keyrt það aftur. Halló, halló, halló. Og það virðist vera að virka. 

En það þýðir einhvers staðar í minn minni tölvunnar eru orðin H-e-L-L-o, upphrópunarmerki. Og það kemur í ljós, eins og innskot, hvað tölva myndi venjulega gera þannig að það veit hvar hlutir byrja og end-- það er fara að setja sérstaka tákn hér. Og venju er að setja númer núll í lok orði þannig að þú veist hvar það reyndar endar, þannig að þú halda ekki að prenta út fleiri og fleiri stafir en þú í raun og veru ætla. 

En takeaway hér, jafnvel þó að þetta er nokkuð yfirnáttúrulegt, er að það er á endanum tiltölulega einfalt. Þú varst að gefa einhverskonar borði, autt pláss sem þú getur skrifað bréf. Þú þarft einfaldlega að hafa sérstakt tákn, eins og geðþótta fjöldi núll, að setja í lok orð þín svo að tölvan veit, ó, ætti ég að hætta prentun á eftir Ég sé upphrópunarmerki. Vegna þess að næsta sem þar er ASCII gildi núll, eða null karakter sem einhver myndi kalla það. En það er góður af vandamál hér, og við skulum snúa aftur til tölur um stund. Segjum sem svo að ég geri, í raun, hafa fjölbreytta tölum, og ætla að Forritið sem ég er að skrifa er eins og bekk bók fyrir kennara og kennara í kennslustofunni. Og þetta forrit gerir hann eða hana að slá í stig nemenda sinna á Skyndipróf. Og ætla að fær nemandinn 100 á fyrsta prófið sitt, kannski eins og 80 á næsta einn, þá er 75, þá 90 á fjórða spurningakeppni. 

Svo á þessum tímapunkti í sögunni, fylki er stærð fjórum. Það er algerlega meira minni í tölva, en array, svo að segja, af stærð fjórum. Segjum nú að kennarinn vill að úthluta fimmta quiz á bekknum. Jæja, einn af þeim hlutum sem hann eða hún er að fara að þurfa að gera er nú geymt fleiri gildi hér. En ef array kennarinn hefur búin í þessari áætlun er stærð fyrir, einn af vandamálinu með array er að þú getur ekki bara að halda að bæta við minni. Vegna þess hvað ef annar hluti af Forritið hefur orðið "hey" þarna? 

Með öðrum orðum, minni mitt er hægt að notaður fyrir neitt í áætluninni. Og ef fyrirfram ég slóst í, hey, Ég vil inntak fjórum quiz skora, þeir gætu farið hér og hér. Og ef þú breytir skyndilega um skoðun seinna og segja ég vil fimmta quiz skora, þú getur ekki bara setja það hvar sem þú vilt, því hvað ef þetta minni er verið að nota fyrir eitthvað else-- annað forrit eða einhver annar lögun af the program að þú ert að keyra? Svo þú verður að hugsa fyrirfram hvernig þú vilt geyma gögn, því nú þú hefur málað sjálfur í stafrænu horn. 

Svo kennari gæti í staðinn segja þegar þú skrifar forrit að geyma hans eða hennar bekk, þú veist hvað? Ég er að fara að biðja, þegar þú skrifar forritið mitt, að ég vil núll, einn, tveir, þrír, fjögur, fimm, sex, átta einkunna samtals. Svo einn, tveir, þrír, fjórir, fimm, sex, sjö, átta. Kennarinn getur bara yfir-úthluta minni þegar þú skrifar áætlun hans eða hennar og segja, þú veist hvað? Ég ætla aldrei að fara að úthluta fleiri en átta Skyndipróf í önn. Það er bara brjálaður. Ég mun aldrei úthluta því. Þannig að þetta leiðin sem hann eða hún hefur sveigjanleika til að skora geyma nemenda, eins 75, 90, og kannski einn auka þar nemandi fékk auka lánsfé, 105. 

En ef kennarinn aldrei notar þessi þrjú rými, það er innsæi takeaway hér. Hann eða hún er bara að sóa pláss. Svo í öðrum orðum, það er þetta algengt tradeoff í forritun þar sem þú getur annað hvort úthluta nákvæmlega eins mikið minni og þú vilt, The kosti sem er að þú ert frábær efficient-- þú ert ekki að vera eyðslusamur á all-- en hæðir sem er það ef þú skiptir um skoðun þegar nota forritið sem þú vilt geyma fleiri gögn en þú upphaflega ætlað. 

Svo kannski er lausnin, þá, skrifa forrit þannig sem þeir nota meira minni en þeir þurfa í raun og veru. This vegur þú ert ekki að fara að hlaupa inn í þessi vandamál, en þú ert að eyðslusamur. Og því meira minni program notar, eins og við ræddum í gær, því minni minni sem er í boði fyrir önnur forrit, fyrr tölvan þín gæti hægja niður vegna raunverulegur minni. Og svo tilvalin lausn gæti verið það? 

Undir-úthlutun virðist slæmt. Yfir-úthlutun virðist slæmt. Svo það gæti verið betri lausn? Endurúthluta. Vera meira dynamic. Ekki þvinga þig til að velja fyrirfram, í upphafi, það sem þú vilt. Og vissulega ekki yfir-úthluta, svo að þú eyðslusamur. 

Og svo til að ná því markmiði, að við þarf að henda þessu gögn uppbygging, svo að segja, í burtu. Og svo hvað forritari mun nota venjulega er eitthvað sem kallast ekki array en tengda listanum. Með öðrum orðum, hann eða hún mun byrja að hugsa um minni þeirra Eins og að vera einskonar form sem þeir getur teiknað á eftirfarandi hátt. Ef ég vil að geyma eitt númer í a program-- svo það er September, Ég hef gefið nemendum mínum quiz; ég vil að geyma nemandans fyrsta prófið, og þeir fengu 100 á ég it-- er að fara að spyrja tölvuna mína, með því að áætluninni sem ég hef skrifað, fyrir einn klumpur af minni. Og ég ætla að geyma það Fjölda 100 í það, og það er það. 

Þá nokkrum vikum seinna þegar ég fæ annað quiz minn, og það er kominn tími til að slá af því að 90%, ég er að fara að spyrja tölvuna, hey, tölva, má ég hafa aðra klumpur af minni? Það er að fara að gefa mér þetta tóm klumpur af minni. Ég ætla að setja á fjölda 90, en í áætlun mína einhvern veginn eða other-- og við munum ekki hafa áhyggjur setningafræði fyrir this-- ég þarf að einhvern veginn keðjureykir þetta saman. Og ég keðjureykir þær saman við það lítur út eins og ör hér. 

Þriðja quiz sem kemur upp, Ég ætla að segja, hey, tölva, gefa mér annað klumpur af minni. Og ég ætla að setja niður hvað sem það var, eins og 75, og ég verð að keðja þetta saman nú einhvern veginn. Fjórða quiz kemur með, og kannski það er undir lok misseris. Og eftir þeim tímapunkti program minn gæti verið að nota minni um allt, allan líkamlega. Og svo bara fyrir spörk, ég er að fara að draga þetta fram quiz-- ég gleymi hvað það var; ég held kannski 80 eða something-- leið hérna. 

En það er allt í lagi, vegna þess að á myndrænan Ég ætla að draga þessa línu. Með öðrum orðum, í raun, í vélbúnaði tölvunnar, fyrsta skora gæti enda hér vegna þess að það er strax í upphafi misseris. Næsta einn gæti endað hér vegna smá tíma hefur liðið og forritið heldur gangi. Næsta stig, sem var 75, gæti verið hérna. Og síðasta skora gæti verið 80, sem er hérna. 

Svo í raun, líkamlega, þetta gæti verið hvað minni tölvunnar lítur út. En þetta er ekki gagnlegt andlega fyrirmynd fyrir a tölva forritari. Hvers vegna ættir þú að hugsa þar sem Heck gögn er lendi? Þú vilt bara til að geyma gögn. 

Þetta er góður af eins og umræðu okkar fyrr teikna teningur. Hvers vegna gera þú aðgát hvað hornið er á teningnum og hvernig þú þarft að snúa að draga það? Þú vilt bara teningur. Á sama hátt hér, þér bara að bekk bók. Þú vilt bara að hugsa um þetta sem lista af tölum. Hverjum er ekki sama hvernig það er framkvæmda í vélbúnaði? 

Svo abstrakt nú er þessi mynd hér. Þetta er tengdur lista, eins og forritari myndi kalla það, að því marki sem þú hefur lista, augljóslega af tölum. En það er tengt á myndrænan með því að þessum örvum, og allar þessar örvar are-- undir hetta, ef þú ert forvitinn, muna að líkamlega vélbúnaður okkar hefur heimilisföng núll, einn, tveir, þrír, fjórir. Allar þessar örvar eru er eins og kort eða áttir, þar sem ef 90 is-- nú Ég fékk að telja. 

Núll, einn, tveir, þrír, fjórir, fimm, sex, sjö. Það lítur út eins og 90 er minni heimilisfang númer sjö. Allar þessar örvar eru er eins og lítið rusl úr pappír það er að gefa leiðbeiningar til að forrit sem segir fylgja þessu korti að fá að staðsetningu sjö. Og þar sem þú munt finna Annað quiz nemanda skora. Á sama tíma, 75-- ef ég halda áfram á þessu, þetta er sjö, átta, níu, 10, 11, 12, 13, 14, 15. 

Þessi annar arrow táknar bara kort í minni stað 15. En aftur, forritari almennt gerir ekki sama um þennan stigi smáatriðum. Og í flestum hverjum forritun Tungumál dag, forritari mun ekki einu sinni vita hvar á minni þessar tölur í raun eru. Allt sem hann eða hún hefur til að hugsa um er að þeir séu á einhvern hátt tengd saman í gagnagrind eins og þetta. 

En það reynist ekki að fá of tæknilegur. En bara vegna þess að við getum kannski efni á að hafa þessa umræðu hér, ráð fyrir að við endurskoðun þetta mál hér á fylki. Við skulum sjá hvort við eftirsjá fara hér. Þetta er 100, 90, 75, og 80. 

Leyfðu mér að gera stuttlega þessa fullyrðingu. Þetta er fylki, og aftur, mikilvæg einkenni fylki er að öll gögn er aftur til aftur til baka í memory-- bókstaflega eitt bæti eða kannski fjögur bæti, sumir fastur fjöldi bæti burtu. Í tengda listanum, sem við gætum dregið eins og þetta, undir hetta sem veit hvar það efni sem er? Það þarf ekki einu sinni að renna svona. Sumar af eftirfarandi upplýsingum gæti verið aftur til vinstri þar upp. Þú þarft ekki einu sinni vita. 

Og svo með fjölbreytta, hefur þú a lögun þekktur sem handahófi aðgang. Og hvað handahófi aðgang leið er sem tölvan getur hoppað stað á hvaða stað í fylki. Hvers vegna? Vegna þess að tölvan veit að fyrsta staðsetning er núll, einn, tveir, og þrír. 

Og svo ef þú vilt fara úr þessi þáttur í næsta frumefni, þú bókstaflega, í Hugur tölvunni, réttlátur bæta við einum. Ef þú vilt fara í þriðja frumefni, bara bæta one-- næsta frumefni, bara bæta við einum. Hins vegar, í þessari útgáfu af sögunni, býst tölvan er nú að leita á eða takast á við fjölda 100. Hvernig gera þú fá til the næstur bekk í bekk bókinni? 

Þú þarft að taka sjö skref, sem er handahófskennt. Til að fá til the næstur einn, þú þarft að taka aðra átta þrep til að komast til 15. Með öðrum orðum, það er ekki stöðug bilið milli talnanna, og svo það tekur bara tölva meiri tími er málið. Tölvan þarf að leita með minni í röð til að finna það sem þú ert að leita að. 

Svo á meðan fylki tilhneigingu til að vera fljótur gögn structure-- vegna þess að þú getur bókstaflega bara gera einfalda stærðfræði og fá þar sem þú vilt með því að bæta við einum, fyrir instance-- tengdan lista, þú fórna að lögun. Þú getur ekki bara farið úr fyrsta að öðrum til þriðja til fjórða. Þú þarft að fylgja kortinu. Þú þarft að taka fleiri skref til að fá að þeim gildum sem virðist vera að bæta kostnað. Þannig að við erum að borga verð, en það var eiginleiki sem Dan var að leita hér? Hvað gerir tengdan lista virðist leyfa okkur að gera, sem var uppruni þetta tiltekna saga? 

Nákvæmlega. A dynamic stærð við það. Við getum bætt við þennan lista. Við getum jafnvel skreppa lista, svo að við erum bara að nota eins mikið minni eins og við viljum í raun og veru og svo við erum aldrei yfir-úthlutun. 

Nú bara að vera mjög nit-vandlátur, það er falinn kostnaður. Svo þú ættir ekki bara að láta mig sannfæra þú að þetta er sannfærandi tradeoff. Það er annar falinn kostnaður hér. Ávinningur, að vera ljóst, er að við fáum kraft. Ef ég vil annað þáttur, ég get bara teikna það og setja númer í það. Og þá get ég tengt það með mynd hér, en hérna, aftur, ef ég hef málað mig út í horn, ef eitthvað annað er nú þegar að nota minni hér, ég er út af heppni. Ég hef málað mig í horn. 

En hvað er falinn kosta á þessari mynd? Það er ekki bara magn Tíminn sem það tekur að fara héðan til hér, sem er sjö skref, þá átta skrefum, sem er meira en ein. Hvað er annað falinn kostnaður? Ekki bara tími. Frekari upplýsingar eru nauðsynleg til að ná þessari mynd. 

Já, það kort, þessir litlu bjórar pappír, eins og ég að halda lýsa þeim sem. Þetta arrows-- þeir eru ekki ókeypis. A computer-- þú veist hvað tölva hefur. Það hefur núll og sjálfur. Ef þú vilt að tákna ör eða a kortleggja eða tala, þú þarft sumir minni. Svo hinn verð sem þú greiða fyrir tengda listanum, sameiginlegt tölvunarfræði úrræði, er líka pláss. 

Og reyndar svo, svo almennt, meðal tradeoffs í að hanna hugbúnaðarverkfræði kerfi er tími og space-- eru tveir af hráefni þínum, tveir af the dýr hráefni þínum. Þetta er kosta mig meiri tíma því ég þarf að fylgja þessu korti, en það er líka kosta mig meira pláss vegna þess að ég þarf að halda þessu korti í kring. Svo vonin, sem við höfum eins konar rætt um í gær og dag, er að ávinningur mun meiri en kostnaðurinn. 

En það er engin augljós lausn hér. Kannski er það better-- a la fljótur og óhreinn, sem Kareem lagt earlier-- að kasta minni á vandamálinu. Bara kaupa meira minni, hugsa minna erfitt um að leysa vandann, og leysa það á auðveldari hátt. Og reyndar fyrr, þegar við ræddum um tradeoffs, það var ekki pláss í tölva og tíma. Það var verktaki tími, sem er enn annar auðlind. 

Svo aftur, það er þetta jafnvægislist að reyna að ákveða hvaða af þessum hlutum ertu tilbúinn að eyða? Sem er amk dýr? Sem gefur betri árangri? Já? 

Einmitt. Í þessu tilfelli, ef þú ert fulltrúi tölur í maps-- þessir eru kallaðir á mörgum tungumálum "ábendingum" eða "heimilisföng" - það er tvöfalt rúm. Það þarf ekki að vera eins slæmt eins og tvöfaldur ef núna erum við bara að geyma tölur. Segjum sem svo að við vorum að geyma sjúkraskrám í hospital-- svo nöfnum Pierson er, símanúmerum, almannatryggingar reikningur, læknir sögu. Þessi kassi gæti verið mikið, miklu stærri, en í því tilviki a pínulítill lítill músina, heimilisfang næsta element-- það er ekki stór samningur. Það er svo kögur kosta það skiptir ekki máli. En í þessu tilfelli, já, það er tvöföldun. Góð spurning. 

Við skulum tala um tíma lítið meira concretely. Hvað er í gangi tími á að leita þennan lista? Segjum að ég vildi leita í gegnum alla nemenda bekk, og það er n einkunnir í þessum gögnum uppbyggingu. Hér líka, getum við fengið lánað orðaforða fyrr. Þetta er línulegt gögn uppbygging. 

Big O n er það sem er nauðsynlegt til að fá til loka þessum gögnum uppbyggingu, whereas-- og við höfum ekki séð þetta before-- fylki gefur þér hvað heitir fasti tími, sem þýðir eitt skref eða tvö skref eða 10 steps-- skiptir ekki máli. Það er föst tala. Það hefur ekkert að gera með stærð fylkisins. Og ástæðan fyrir því, aftur, er handahófi aðgang. Tölvan getur bara strax hoppa á annan stað, vegna þess að þeir eru allir á sama fjarlægð frá öllu öðru. Það er engin hugsun að ræða. Allt í lagi. Svo ef ég get, láta mig reyna að mála tvær endanlega myndir. A mjög sameiginlegur einn þekktur sem kjötkássa töflunni. Svo til að hvetja þessa umræðu, láta mig hugsa um hvernig á að gera þetta. 

Svo hvernig um þetta? Gerum ráð fyrir að vandamálið Við viljum leysa nú er að innleiða í dictionary-- svo er allt fullt af enskum orðum eða hvað sem er. Og markmiðið er að vera fær um að svara spurningar um form er þetta orð? Svo þú vilt að framkvæma a stafa afgreiðslumaður, bara eins og líkamlega orðabókina að þú getur litið það upp í. Segjum að ég væri að gera þetta með fjölda. Ég gæti gert þetta. 

Og ætla orðin eru epli og banani og cantaloupe. Og ég get ekki hugsað um ávöxtum að byrja með d, þannig að við erum bara fara að hafa þrjú ávexti. Svo er þetta fylki, og við erum að geyma öll þessara orða í þessari orðabók sem fylki. Spurningin er þá hvernig annars gætir þú geymt þessar upplýsingar? 

Jæja, ég er góður af svindla hér, vegna þess að hver af þessum bréfum í orði er í raun einstaklingur bæti. Þannig að ef ég vildi virkilega að vera nit-vandlátur, ég ætti virkilega að skipta þessu upp í mikið smærri klumpur af minni, og við gætum gert einmitt það. En við erum að fara að keyra inn sama vandamál og áður. Hvað ef, eins og Merriam Webster eða Oxford er sérhver year-- þeir bæta orðum til dictionary-- við gerum ekki endilega að mála okkur í horn með fjölda? 

Þannig að í stað, kannski betri nálgun er að setja epli í eigin hnút þess eða kassa, eins og við myndi segja, banani, og þá hér höfum cantaloupe. Og við string þetta saman. Svo er þetta array, og þetta er tengt með lista. Ef þú getur ekki alveg séð það bara segir "array", og þetta segir "lista." 

Þannig að við höfum sama Nákvæmlega málefni eins og áður, þar sem við höfum nú kraftur í tengda listanum okkar. En við höfum nokkuð hægur orðabók. Segjum að ég vil að líta upp orði. Það gæti tekið mig stór O n skref, vegna þess að orðið gæti að vera alla leið í lok listi, eins cantaloupe. Og það kemur í ljós að í forritun, flokka af Gral af gögnum mannvirki, er eitthvað sem gefur þér stöðug tími eins og fylki en það samt gefur þér kraft. 

Svo getum við hafa það besta af báðum heimum? Og reyndar, það er eitthvað kallað kjötkássa borð sem leyfir þér að gera einmitt að vísu um það bil. A kjötkássa borð er áhugamaður gögn uppbygging sem við er að hugsa um eins og Sambland af array-- og ég ætla að draga það eins this-- og tengd listum að ég teikna svona hérna. 

Og hvernig þessi hlutur verk er eins og hér segir. Ef þetta now-- kjötkássa table-- er þriðji gögn uppbygging minn, og ég vil að geyma orð í þetta, ég er ekki vil bara geyma allt í orð aftur til baka til baka til baka. Ég vil nýta sumir stykki af upplýsingar um orðum sem munu láta mér að fá það þar sem það er hraðar. 

Svo gefið orðin epli og banani og cantaloupe, Ég valdi vísvitandi þessi orð. Hvers vegna? Hvað er tegund af grundvallaratriðum öðruvísi um þremur? Hvað er augljóst? Þeir byrja með mismunandi stöfum. 

Svo þú veist hvað? Frekar en að setja öll mín orð í sama fötu, svo að segja, eins og í eina stóra skrá, hvers vegna ekki Ég að minnsta kosti reyna hagræðingu og gera listum mínum 1/26 eins lengi. A sannfærandi hagræðingu gæti verið ástæðan ekki I-- að setja í orð í þessum gögnum uppbyggingu, í minni tölvunnar, hvers vegna ég er ekki að setja allar "A" orð hér, allir 'B' orð hér, og allir 'c' orð hér? Svo endar þetta allt að koma epli hér, banani hér, cantaloupe hér, og svo framvegis. 

Og ef ég hef til viðbótar Bæta like-- hvað er annað? Epli, banani, pera. Einhver hugsa um ávöxtum sem byrjar með a, b, eða c? Blueberry-- fullkominn. Það er að fara að enda hér. Og svo við virðast hafa ívið betri lausn, því nú ef ég vil til að leita að epli, ég first-- ég ekki bara kafa í uppbyggingu gagna mína. Ég kafa ekki í minni tölvunnar minnar. Ég lít fyrst á fyrsta stafnum. 

Og þetta er hvað tölva vísindamaður myndi segja. Þú kjötkássa í uppbyggingu gögn þína. Þú tekur inntak þitt, sem í þetta mál er orðið eins og epli. Þú greina það, að horfa á fyrsti stafurinn í þessu tilfelli, þannig hass það. Hökkun er almennt hugtak þar þú tekur eitthvað sem inntak og þú framleiða nokkur framleiðsla. Og framleiðsla í það Málið er staðsetningin þú vilt leita, fyrsta staðsetningu, annar staðsetning, þriðja. Svo inntak er epli, framleiðsla er fyrst. The inntak er banani, sem framleiðsla ætti að vera annað. The inntak er cantaloupe, framleiðsla ætti að vera þriðji. The inntak er bláberja, sem framleiðsla ætti aftur að vera annað. Og það er það sem hjálpar þér að taka flýtileiðir í gegnum minni þitt í því skyni að fá að orðum eða gögn á skilvirkari hátt. 

Nú sker þetta niður okkar tíma hugsanlega með eins mikið eins og einn af 26, því ef þú ráð fyrir að þú hafa eins mörg "a" orð eins og "z" orð eins og "Q" orð, sem er í raun ekki realistic-- þú ert að fara að hafa Skekkja yfir ákveðin bréf í alphabet-- en þetta væri stigvaxandi nálgun sem ekki leyfa þú þarft að fá að orðum miklu hraðar. Og í raun, háþróuð program, Googles í heiminum, sem Facebooks af world-- þeir myndu nota kjötkássa töflu fyrir a einhver fjöldi af mismunandi tilgangi. En þeir myndu ekki vera svo barnaleg og bara líta á fyrsta staf í epli eða banana eða pera eða cantaloupe, því eins og þú getur séð þetta listar gæti samt fengið lengi. 

Og svo þetta gæti samt verið eins konar af linear-- svo konar hægur, eins og með stór O n sem við ræddum áðan. Svo það alvöru gott kjötkássa borð vilja do-- það mun hafa miklu stærri array. Og það mun nota miklu meira háþróuð Hökkun virka, þannig að það er ekki bara að líta á "a". Kannski lítur á "a-p-P-L-e" og einhvern veginn breytir þeim fimm stafi í stað þar epli skal geyma. Við erum bara naively nota stafinn 'a' einn, því að það er gott og einfalt. 

En kjötkássa borð, í enda, getur þú hugsa af eins og a blöndu af fylki, sem hver um sig hefur tengdan lista sem helst skal vera eins stutt og mögulegt er. Og þetta er ekki augljós lausn. Í raun, mikið af fínstilla sem fer á undir hetta hvenær framkvæmd þessar tegundir af háþróuð gögn uppbygging er það sem er rétt lengd fylkisins? Hvað er rétt kjötkássa virka? Hvernig finnst þér að geyma hluti í minni? 

En átta sig hversu fljótt Þessi tegund af umræðu stigmagna, annaðhvort svo langt að það er góður af yfir höfuð manns á þessum tímapunkti, sem er fínt. En við byrjuðum, muna, með sannarlega eitthvað lágmark-láréttur flötur og rafræn. Og svo þetta aftur er þetta þema abstrakt, þar þegar þú byrjar að taka til veitt, OK, ég hef fengið it-- það er líkamlegur minni, OK, fékk það, hver líkamlegur staðsetning hefur heimilisfang, OK, ég fékk það, get ég tákna þessir heimilisföng sem arrows-- þú getur mjög fljótt að byrja að hafa flóknari samtöl sem á endanum virðast vera að leyfa okkur til að leysa vandamál eins og að leita og flokkun á skilvirkari hátt. Og treyst, too-- vegna þess að ég held að þetta er dýpsta sem við höfum farið í nokkrar þessara CS viðfangsefnum proper-- við höfum gera í dag og hálfan á þetta benda hvað þú gætir venjulega gera yfir auðvitað af átta vikur í önn. 

Einhverjar spurningar um þetta? Nei? Allt í lagi. Ja, hvers vegna eigum við ekki að staldra þar, byrja hádegismat nokkrar mínútur snemma, halda áfram í bara um klukkutíma? Og ég sitja fyrir svolítið með spurningum. Þá er ég að fara að fara taka nokkrar símtöl ef það er í lagi. Ég kveiki á smá tónlist í millitíðinni, en hádegisverður ætti að vera handan við hornið.