DAVID Malan: Gerai. Mes grįžome. Taigi šiame segmente programavimo ką Aš maniau, mes norime padaryti, tai daug dalykų derinys. Vienas iš jų, padaryti šiek tiek kažko hands-on, nors naudojant daugiau žaismingumo programavimo environment-- vienas, kad yra demonstratyvus iš tiksliai idėjų rūšių mes jau kalbame apie, bet šiek tiek daugiau formaliai. Du, pažvelgti į kai labiau techniniai būdai kad programuotojas iš tikrųjų išspręsti problemos, pavyzdžiui, ieško problemos kad mes pažvelgė prieš ir Taip pat labiau iš esmės Įdomu problema rūšiavimas. 

Mes tiesiog prielaida iš gauti eiti kad telefonas knyga buvo rūšiuojamos, bet, kad vien iš tikrųjų rūšies sunku problema su daugeliu skirtingų būdų ją išspręsti. Taigi, mes naudosime juos kaip nemažai problemų klasė atstovas dalykų, kurie gali būti išspręsta iš esmės. Ir tada mes kalbame apie gana išsamiai, ką yra vadinami duomenų structures-- mėgėjas būdų, kaip tiesinis sąrašas ir dėstymo lentelė ir medžiai, kurie programuotojas iš tikrųjų naudoti ir paprastai naudoja Lentoje tapyti iš vaizdo, ką jis ar ji įsivaizduoja įgyvendinimo kai programinė įranga,. 

Taigi darykime rankas ant dalį pirmiausia. Taigi tiesiog gauti savo rankas purvinas su Aplinka vadinami scratch.mit.edu. Tai yra įrankis, kad mes naudojame Mūsų bakalauro klasėje. Nors jis sukurtas 12 metų ir daugiau, mes ją naudoti aukštyn dalis, kad gana didelis nes jis gražus, įdomus grafinė mokymosi būdas šiek tiek kažkas apie programavimą. Taigi galvą į tą URL, kur jums turėtų pamatyti puslapyje labai patiko tai, ir eiti į priekį ir spustelėkite Prisijunkite prie nulio viršuje dešinėje ir pasirinkite vardą ir slaptažodis ir galiausiai gauti sau account-- scratch.mit.edu. Aš maniau, kad aš naudoju tai kaip galimybė pirmą kartą parodyti tai. Klausimas atėjo pertraukos metu apie tai, ką kodas tikrųjų atrodo. Ir mes kalbame Per pertrauką apie C, į particular-- ypač mažesnis lygis vyresnio kalba. Ir aš tiesiog padarė greitai "Google" paieška rasti C kodą naudojant dvejetainį paieškos algoritmas, kad mes naudojama paieškos sistema, telefono knyga anksčiau. Šis konkretus pavyzdys, žinoma, neieško telefono knyga. Jis tiesiog ieško visa krūva numeriai kompiuterio atmintyje. Bet jei norite tik gauti vaizdo jausmas, kas yra faktinis programavimo Kalba išvaizda, atrodo, šiek tiek kažką panašaus į tai. Taigi, tai apie 20-plius, 30 arba tiek eilučių kodo, bet pokalbis mes buvo turintys per pertrauką buvo apie tai, kaip tai iš tikrųjų gauna peraugo į nulių ir ir jei jūs galite ne tik sugrįžti, kad apdoroti ir eik iš nulių ir atgal į kodą. 

Deja, šis procesas taip transformacijos kad tai daug lengviau pasakyti nei padaryti. Nuėjau į priekį ir iš tikrųjų pasirodė Ta programa, Dvejetainiai Paieška, į nulių ir pateikdamas programa, vadinama kompiliatorius, kad aš atsitikti, kad čia tiesiai ant mano Mac. Ir jei peržvelgsite ekrane čia daugiausia dėmesio skiriama būtent šiais vidutinio šešių kolonų tik pamatysite tik nulių ir. Ir tas yra nuliai ir tie, kurie rašyti tiksliai kad asmenys, ieškantys programą. 

Ir taip kiekvieną iš penkių bitų riekė, kiekvienas iš nulių ir baitų čia atstovauti kokį nurodymą paprastai viduje kompiuterio. Ir iš tiesų, jei jūs girdėjote rinkodaros šūkis "Intel Inside", - kad Žinoma, tiesiog reiškia, kad jūs turėti Intel CPU arba smegenų viduje kompiuterio. Ir ką tai reiškia, kad turi būti CPU yra kad jūs turite instrukcijų rinkinys, taip sakant. 

Kiekvienas pasaulyje CPU, daugelis iš juos padarė "Intel" šių dienų, supranta baigtinis skaičius instrukcijas. Ir tie nurodymai yra toks žemas lygis kaip pridėti šie du numerius kartu, daugintis šiuos du numerius kartu, perkelti šį duomenų gabalas iš čia į čia iš atminties, išsaugoti tai informacija iš čia į čia atminties, ir taip forth-- taip labai, labai žemo lygio, beveik elektronikos detales. Bet su tais, matematinis operacijos kartu su tuo, ką aptarėme anksčiau, duomenų atvaizdavimas kaip nulių ir gali jums sukurti viską kad kompiuteris gali padaryti šiandien, ar tai tekstinė, grafinė, muzikinė, arba kitaip. 

Todėl tai yra labai lengva gauti prarasta greitai piktžolių. Ir ten daug sintaksiniai iššūkiai kuriuo, jei jūs padarote paprasčiausias, stupidest iš rašybos nė programos dirbs kokia. Ir todėl vietoj naudojant kalba kaip C šįryt Maniau, kad tai būtų smagiau tikrųjų kažkas daugiau vaizdo, kuris o skirtas vaikams iš tikrųjų yra tobula išraiška kurių faktinė programavimo language-- tik atsitinka naudoti nuotraukas, o ne tekstą atstovauti šias idėjas. 

Taigi, kai jūs iš tikrųjų turėti abonementas scratch.mit.edu, spustelėkite mygtuką "Sukurti" viršuje kairėje svetainėje. Ir jūs turėtumėte pamatyti, kaip aplinkos vienas aš apie matyti mano ekrano čia. Ir mes praleisti tik šiek tiek tiek laiko žaisti čia. Leiskite pamatyti, jei mes galime ne visos išspręsti kai problemos kartu į tokiu būdu. 

Taigi, ką jūs pamatysite viduje tai environment-- ir iš tikrųjų tiesiog leiskite man pristabdyti. Ar kas nors čia nėra? Ne čia? GERAI. Taigi leiskite man pabrėžti keletą charakteristikos šioje aplinkoje. 

Taigi viršuje kairėje ekrano, mes turi įbrėžimams scenoje, taip sakant. Įbrėžimams yra ne tik pavadinimas Šio programavimo kalba; tai taip pat yra katė vardas matote pagal nutylėjimą ten oranžinė. Jis yra etape, todėl panašiai kaip aprašiau vėžlys anksčiau kaip A stačiakampio formos balta lenta aplinka. Ši katė pasaulis apsiriboja tik tai stačiakampis iki viršūnės. 

Tuo tarpu, dešinėje pusėje čia, tai tik scenarijai zona, tuščias šiferis, jei bus. Tai kur mes ketiname rašyti Mūsų programos tik akimirkai. Ir statybiniai blokai, kad mes naudoti parašyti šį program-- galvosūkį vienetų, jei will-- yra tie čia centru, ir jie suskirstyti funkcionalumą. Taigi, pavyzdžiui, aš ruošiuosi eiti į priekį ir įrodyti bent vieną iš jų. Aš ruošiuosi eiti į priekį ir spustelėkite Valdymo kategorijoje iki viršaus. 

Taigi tai yra kategorijos iki viršaus. Aš ruošiuosi spustelėkite Control kategoriją. Atvirkščiai, aš ruošiuosi spustelėkite Renginiai kategorija, labai pirmasis iki viršaus. Ir jei jūs norite sekti kartu net kaip mes tai padaryti, jūs gana Sveiki. Aš ruošiuosi spustelėkite ir vilkite tai Pirmasis "Kai žalia vėliava paspaudėte". Ir tada aš ruošiuosi atsisakyti jo tiesiog maždaug tuo mano tuščių šiferis viršuje. 

Ir kas malonu apie Scratch yra tai, kad įspūdį, kai sujungtas su kitomis dėlionės vienetų, ketina daryti tiesiog ką tie įspūdį pasakyti daryti. Taigi, pavyzdžiui, "Scratch yra teisinga dabar jo pasaulyje viduryje. Aš ruošiuosi eiti į priekį ir pasirinkti dabar tarkim, judesio kategorija, jei norite daryti same-- Motion kategoriją. Ir dabar pastebėsite, turiu vieną visumą krūva įspūdį čia , kad vėl, tipo tai, ką jie sako. Ir aš ruošiuosi eiti į priekį ir vilkite ir lašas Perkelti blokas teisę čia. 

Ir pastebėti, kad kuo greičiau gauti netoli "žaliosios vėliavos apačioje paspaudėte "mygtuką pranešimas kaip atrodo balta linija, kaip nors ji beveik magnetinis, ji nori ten eiti. Tiesiog leiskite eiti, ir jis bus rodomas kartu ir figūros sutaps. Ir dabar jūs galite galbūt beveik atspėti, kur mes ketiname su tai. 

Jei pažvelgti į "Scratch etape čia ir atrodo, kad jo viršuje, pamatysite raudoną šviesą A sustabdyti pasirašyti ir žalia vėliava. Ir aš ruošiuosi eiti į priekį ir žiūrėti savo screen-- tik už akimirką, jei galėtų. Aš ruošiuosi spustelėkite žalia vėliava dabar, ir jis persikėlė kas atrodo, kad 10 žingsnių arba 10 taškų, 10 taškų, ekrane. 

Ir taip nėra, kad įdomus, bet leiskite man pasiūlyti net moko tai, tiesiog naudojant savo savo intuition-- tegul man pasiūlyti, kad jums išsiaiškinti, kaip padaryti Scratch vaikščioti į dešinę nuo scenos. Ar jam padaryti kelią dešinėje pusėje ekranas, visą kelią į dešinę. Leiskite man duoti jums momentą ar taip galynėtis su tuo. Jūs galbūt norėsite pažvelgti ne kitų kategorijų blokus. Gerai. Taigi tik Priminti, kai mes turime žalia vėliava čia paspaudėte ir perkelti 10 žingsnių yra tik instrukcija, kiekvieną kartą spustelėkite žalią vėliavą, kas vyksta? Na, tai veikia mano programą. Kad galėčiau tai padaryti gal 10 kartų rankiniu būdu, bet tai jaučiasi šiek tiek tiek hackish, taip sakant, kuriuo aš tikrai ne sprendžiant šią problemą. Aš tiesiog bando vėl ir vėl ir vėl ir vėl kol aš tarsi netyčia pasiekti direktyvos kad aš, nustatytus siekiant anksčiau. 

Bet mes žinome iš mūsų Pseudocode anksčiau, kad ten ši sąvoka yra programavimo ąselę, daro kažką vėl ir vėl. Ir taip aš pamačiau, kad iš jūsų krūva pasiekė, kas įspūdį? Kartokite, kol. Taigi, mes galime padaryti kažką kaip kartokite tol, kol. Ir ką tu kartokite tol, kol tiksliai? 

GERAI. Ir leiskite man eiti su vienu tai šiek tiek paprasčiau tiesiog momentu. Leiskite man eiti į priekį ir tai padaryti. Atkreipkite dėmesį, kad, kaip jūs gali turėti atrado kontroliuojama, ten tai pakartokite blokas, kuri neatrodo kaip tai, kad didelis. Čia nėra daug kambarys tarp šių dviejų geltonų linijų. Bet kaip kai kurie iš jūsų gali turėti pastebėjau, jei jūs vilkite ir upuść, pastebėti, kaip jis auga užpildyti formą. 

Ir jūs netgi galite prisikimšti daugiau. Tai bus tik nuolat auga, jei vilkite ir užveskite pelės žymeklį ant jo. Ir aš nežinau, kas yra geriausia čia, tad man bent jau pakartoti penkis kartus, už atvejis, ir tada grįžti į sceną ir spauskite žalią vėliavą. Ir dabar pastebėsite, kad tai ne visai ten. 

Dabar kai kurie iš jūsų, siūloma, kaip Viktorija ką tik padarė, pakartokite 10 kartų. Ir tai paprastai daro gauti jį visą kelią, Bet ar ne ten būti labiau patikimas būdas nei savavališkai suprasti, kiek juda padaryti? Kas gali būti geriau blokas nei pakartoti 10 kartų būti? 

Taip, tai kodėl gi ne padaryti kažką amžinai? O dabar leiskite man pereiti šį įspūdį viduje yra ir atsikratyti šio vieno. Dabar pastebėti, nesvarbu, kur įbrėžimams prasideda, jis eina į krašto. Ir laimei MIT, kas daro nulio, tiesiog užtikrina, kad jis niekada visiškai išnyksta. Jūs visada galite patraukti savo uodegą. 

Ir tik intuityviai, kodėl jis nuolat juda? Kas čia vyksta? Jis, atrodo, sustojo, bet tada, jei aš pasiimti ir vilkite jis nuolat nori eiti ten. Kodėl taip yra? Tikrai, kompiuteris yra tiesiog ketinate daryti ką pasakyti, daryti. Taigi, jei jūs ją sakė anksčiau padaryti Žemiau dalykas amžinai, perkelti 10 žingsnių, jis ketina nesustoti ir eiti kol aš paspauskite raudoną stop ženklas ir sustabdyti programą apskritai. 

Taigi, net jei tu negali tai padaryti, kaip galėčiau padaryti Scratch judėti greičiau per ekraną? Daugiau žingsniai, tiesa? Taigi užuot 10 metu, kodėl ne mes eiti į priekį ir pakeisti jį to-- ką jūs propose-- 50? Taigi, dabar aš ruošiuosi spustelėkite žalia vėliava, ir iš tiesų, jis eina labai greitai. 

Ir tai, žinoma, yra tik iš animacijos apraiška. Kas yra animacija? Tai tiesiog rodo tau žmogiškai visa krūva nejudančius vaizdus tikrai, tikrai, tikrai greitai. Ir todėl, jei mes tiesiog sakau jam judėti daugiau veiksmų, mes tiesiog efektas būti Pakeisti kur jis yra ekrane visi daugiau greitai per laiko vienetą. 

Dabar kitas uždavinys, kad aš pasiūliau buvo turėti jam Bounce off krašto. Ir nežinant, ką dėlionės vienetų exist-- nes tai gerai jei nenorite gauti į etapas challenge-- ką tu nori daryti intuityviai? Kaip mes turime jam atšokti atgal ir pirmyn, tarp kairės ir dešinės? 

Taip. Taigi mums reikia tam tikros rūšies nuo būklės ir mes atrodo, kad sąlyginių, taip kalbėti, prižiūrint kategorijas. Kuris iš šių blokų mes tikriausiai nori? Taip, gal ", jei vėliau." Taigi pastebėti, kad tarp geltonų blokų mes turime čia, yra tai "jei" ar tai ", jei dar" blokas, kuri bus leidžia mums priimti sprendimą, kaip tai padaryti arba tai padaryti. Ir jūs netgi galite lizdą juos padaryti kelis dalykus. Arba, jei jūs ne dingo čia dar, eiti į priekį, jautriųjų kategorijos and-- pažiūrėkime, jei tai čia. 

Taigi, kas blokas gali būti naudinga čia siekiant nustatyti, ar jis nuo scenos? Taip, pastebėsite, kad kai kurie iš šių blokų gali būti Parametrizuotieji, taip sakant. Jie gali būti tarsi pritaikyti, o ne skirtingai HTML vakar su atributais, kur tie atributai rūšies pritaikyti žymės elgesį. Panašiai čia galiu patraukti šio neliesti blokas, keisti ir užduoti klausimą, tu neliesti pele rodyklė kaip žymeklio ar tu neliesti kraštą? 

Taigi leiskite man eiti ir tai padaryti. Aš ruošiuosi nutolinti akimirką. Leiskite patraukti šio įspūdį čia tai įspūdį tai, ir aš ruošiuosi Maišyti juos tik už momentu. Aš ruošiuosi pereiti tai, pakeisti tai neliesti krašto, ir aš ruošiuosi judesio tai padaryti. Taigi čia yra keletas ingredientų. Manau, aš turiu viską, ką nori. 

Ar kas nors norėtų pasiūlyti, kaip aš gali sujungti šiuos gal iš viršaus į apačią tam, kad rozwiązujesz problema problemą Įbrėžimams Perkelti į dešinę į kairę į dešinę kairės į dešinę į kairę, kiekvienas laikas tik šoktelėti nuo sienos? Ką norite daryti? Kuris blokas turėčiau prisijungti prie "Kai žalia vėliava paspaudėte pirmasis"? 

Gerai, kad galime pradėti su "amžinai". Kas vyksta viduje toliau? Kažkas kitas. Gerai, perkelti veiksmus. Gerai. Kas tada? Taigi tada, jei. Ir pastebėti, nors ji atrodo įtvirtinta kartu sandariai, jis tiesiog auga užpildyti. Jis tiesiog šokinėti kur aš noriu ją. 

Ir ką aš įdėti tarp IF ir tada? Tikriausiai ", jei liečiant krašto." Ir pranešimas, vėlgi, tai per didelis už jį, bet ji bus augti užpildyti. Ir tada pasukite 15 laipsnių? Kiek laipsnių? Taip, taip, 180 suksis man visą kelią aplink. Taigi pažiūrėkime, jei aš šią teisę. Leiskite nutolinti. 

Leiskite vilkite sukrapštyti. Taigi jis yra šiek tiek iškreiptas dabar, bet tai gerai. Kaip aš galiu iš naujo jį lengvai? Aš ruošiuosi šiek tiek apgauti. Taigi, aš pridedant kitą blokas, tiesiog, kad būtų aišku. Aš noriu jį atkreipti 90 laipsnių į pagal nutylėjimą teise, todėl aš tik ketina jam pasakyti padaryti, kad programiškai. Ir čia mes einame. Mes, atrodo, padarė. Tai šiek tiek keista, nes jis vaikšto aukštyn kojom. Tegul vadina, kad per klaidą. Tai yra klaida. Re yra Programoje, klaida logiška klaida, kad aš, žmogus, padarė. Kodėl jis vyksta aukštyn kojom? Ar MIT susukti ar aš? 

Taip, aš turiu galvoje, tai ne MIT kaltės. Jie davė man įspūdį kad sako pasukti šiek tiek laipsnių skaičių. Ir Victoria siūlymu Aš tekinimo 180 laipsnių, kuris yra teisingas intuicija. Bet sukant 180 laipsnių pažodžiui reiškia sukant 180 laipsnių, ir tai tikrai ne ką aš noriu, matyt. Nes bent jau jis į tai dvimatis pasaulis, taip tekinimo iš tiesų vyksta apversti jį aukštyn kojom. 

Aš tikriausiai norite panaudoti tai, ką blokas vietoj to, remiantis ką matote čia? Kaip mes galime išspręsti šią problemą? Taip, taip, mes galime atkreipti priešinga kryptimi. Ir iš tikrųjų, net tai nebus pakankamai nes mes galime tik sunkiai kodas į nukreipta į kairę arba į dešinę. 

Jūs žinote, ką mes galime padaryti? Atrodo, mes turime patogumas blokas čia. Jei aš priartinti, pamatyti kažkas mums patinka čia? Taigi atrodo, kad MIT has an abstrakcija pastatyta čia. Ši skiltis atrodo, būtų lygiavertė prie kurio kiti blokai, daugiskaitos? 

Tai vienas blokas atrodo, būtų lygiavertė į visą šią trio blokų kad mes turime čia. Taigi paaiškėja, galiu supaprastinti mano programa atsikratyti visa tai ir tiesiog įdėti šią nuorodą į čia. Ir dabar jis dar šiek tiek Buggy, ir kad gerai dabar. Mes palikti, kad būtų. Bet mano programa yra net paprastesnė, ir tai, taip pat, Būtų atstovas iš į programming-- tikslas yra idealiai padaryti savo kodą paprastas, kompaktiškas, kaip įmanoma, o vis dar kaip skaitoma, kaip įmanoma. Jūs nenorite, kad jis taip ir glaustai kad sunku suprasti. 

Bet pastebėsite aš pakeisti trys blokai, turintis vieną, ir tai, be abejo, geras dalykas. Aš išgaunamo toli sąvoką patikrinti, ar esate ant krašto su vienu bloku. Dabar mes galime smagiai su tai, tiesą sakant. Tai nereiškia, pridėti tiek daug intelektinės vertė, bet žaismingas vertė. Aš ruošiuosi eiti į priekį ir patraukti šį garsą čia. Taigi leiskite man eiti į priekį ir leiskite man sustabdyti akimirką programą. Aš ruošiuosi įrašyti tokią, galima prieiti prie mano mikrofoną. 

Čia mes einame. Ouch. Pabandykime tai dar kartą. Čia mes einame. Gerai, įrašiau blogas dalykas. Čia mes einame. Ouch. Ouch. Gerai. Dabar man reikia atsikratyti, kad. Gerai. 

Taigi dabar aš turiu įrašymas tik "Ouch". Taigi, dabar aš ruošiuosi eiti į priekį ir tai vadiname "Ouch". Aš ruošiuosi grįžti mano scenarijus, o dabar pranešimas ten tai blokas tai vadinama žaisti Sound "meow" arba žaisti garsą "Ouch". Aš ruošiuosi vilkite tai, ir kur Turėčiau pateikti tai už komiškas efektas? Taip, taip, dabar tai tipo Buggy, nes dabar tai block-- pastebėti, kaip ši ", jei ant krašto, Bounce "rūšies uždaro. Taigi man reikia išspręsti šią problemą. Leiskite man eiti į priekį ir tai padaryti. Leiskite atsikratyti šio ir grįžti mūsų originalas, daugiau tyčinis funkcionalumas. Taigi "jei neliesti kraštą, tada" Aš noriu pasukti, kaip siūloma Viktorija 180 laipsnių. Ir aš noriu žaisti garsas "Ouch" ten? 

Taip, pastebėsite, kad tai ne kad geltona blokas. Todėl tai, taip pat, būtų klaidą, bet aš pastebėjau ją. Taigi, aš ruošiuosi vilkite jį čia ir pranešimas dabar tai viduje ", jei". Taigi "jei" tai tarsi panašaus rankos-kaip dėmė kad tik ketina daryti tai, kas viduje ji. Taigi dabar, jei aš nutolinti bent iš annoying-- rizika 

Kompiuteris: Ouch, Ouch, Ouch. 

DAVID Malan: Ir tai tiesiog tęstis amžinai. Dabar tik paspartinti dalykus čia, leiskite man eiti į priekį ir atverti, tegul say-- leiskite man eiti į kai mano paties stuff iš klasės. Ir leiskite man atverti, tarkim, tai vienas padarė vienas iš mūsų mokymo bičiulių porą metų senumo. Taigi kai kurie iš jūsų gali prisiminti Šis žaidimas iš praeities, ir tai tikrai puikus. Nors mes padarė tą Paprasčiausias programų dabar, aptarkime, kas tai iš tikrųjų atrodo. Leiskite paspausti žaisti. 

Taigi šiame žaidime, mes turime varlė, ir naudojant rodyklę keys-- jis mano didesnių žingsnių, nei aš remember-- Turiu kontroliuoti šio varlė. Ir tikslas yra gauti per užimtas kelių nesukeldama į automobilius. Ir tegul see-- jei man eiti čia, aš turi laukti žurnalas, slinkti. Tai jaučiasi klaidą. Tai rūšies klaidą. Gerai. Aš apie tai čia ten, ir tada jūs nuolat vyksta, kol jūs gausite visus Varlės į lelija trinkelės. Dabar tai gali atrodyti dar labiau kompleksas, bet pabandykime sulaužyti tai žemyn mintyse ir žodžiu į jo sudedamųjų blokų. Taigi ten tikriausiai dėlionės gabalas, kad mes nematėme dar bet tai reaguoti į klavišų, dalykų, aš paspauskite ant klaviatūros. 

Taigi ten tikriausiai kai natūra blokas, kuri sako, jei raktas lygus aukštyn, tada kažką daryti su Scratch-- gal perkelti jį 10 žingsnių šiuo būdu. Jei žemyn paspaudžiamas mygtukas, perkelti 10 žingsnių Tokiu būdu, arba kairėje raktas, perkelti 10 žingsnių Tokiu būdu, 10 žingsnių, kuriuos. Aš aiškiai pasuko katė į varlę. Taigi, kad tik kur kostiumas, kaip Scratch skambučiai it-- mes tik importavo varlės nuotrauką. 

Bet ką dar vyksta? Kas kitas eilučių kodo, ką kiti įspūdį padarė Bleikas, mūsų mokymo kolegos, naudoti šioje programoje, matyt? Kas daro viską move-- kas programavimo statyti? 

Pasiūlymas, sure-- todėl Perkelti blokas, tikrai. Ir kas, kad Perkelti blokas viduje, greičiausiai? Taip, kai kurie iš kilpos natūra, gal amžinai blokuoti, gal pakartokite block-- kartokite tol, kol blokas. Ir tai, kas daro rąstus ir lelija trinkelės ir visa kita Perkelti į priekį ir atgal. Tai tiesiog vyksta be galo. 

Kodėl kai kurie iš automobilių juda greičiau, nei kiti? Kuo skiriasi šių programų? Taip, tikriausiai kai kurie iš jų, atsižvelgiant daugiau veiksmų vienu metu ir kai kurie iš jų mažiau žingsnių vienu metu. Ir vaizdo efektas greitai palyginti lėtai. 

Ką manote atsitiko? Kai aš gavau mano varlė visą kelią per gatvę ir upės ant lelijos trinkelėmis, kažkas Pažymėtina atsitiko. Kas atsitiko, kai aš padariau, kad? Ji sustojo. Tai varlė sustojo, ir Aš turiu antrą varlė. Taigi, kas konstruktas turi būti būdavo, ką funkcija? 

Taip, taip, yra keletas natūra "Jei" sąlyga ten pat. Ir paaiškėja out-- mes nematė this-- bet ten kitas blokų ten, kad galiu pasakyti, jei esate neliesti Kitas dalykas ekrane, jei neliesti lelija bloknotu ", tada". Ir tada, kad kai mes kad antroji varlė atrodo. Taigi, nors šis žaidimas yra tikrai labai d, nors iš pirmo žvilgsnio ten tiek daug vyksta on-- ir Blake nebuvo plakti tai dviem minutėmis, tai tikriausiai užtruko kelis valandos kurti šį žaidimą remiantis jo atmintyje arba video pasekėjai versijos jį. Tačiau visų šių smulkmenų vyksta į izoliacijos ekrano skliautais į tai labai paprasta constructs-- judesiai ir pareiškimai kaip mes aptarėme, kilpos ir sąlygos, ir kad apie jį. Yra keletas kitų mėgėjas funkcijos. Kai kurie iš jų yra grynai estetinis arba garso, kaip garsų aš tiesiog grojo su. Tačiau didžioji dalis, jums turi šia kalba, nulio, visi esminis statybiniai blokai, kad jums turi C, Java, JavaScript, PHP Ruby, Python, ir bet kurį iš kitų kalbomis numeris. Turite klausimų apie nulio? Gerai. Taigi mes nepasakosime pasinerti giliau į nulio, nors esate laukiami šį savaitgalį, ypač jei turite vaikų ar dukterėčios ir sūnėnai ir tokių, supažindinti juos su nulio. Tai tikrai nuostabiai žaismingas aplinka su, kaip jo autoriai sako, labai aukštos lubos. Nors mes pradėjome labai mažo detalės, tikrai galite padaryti gana didelis su juo, ir tai yra galbūt iš būtent tai demonstravimas. 

Bet tegul dabar pereiti prie šiek tiek daugiau sudėtingų problemų, jei bus, žinomas kaip "paieškos" ir "Rūšiavimo" apskritai. Mes turėjome šis telefonas knyga earlier-- čia dar vienas tik discussion-- kad mes galėjome ieškoti efektyviau, nes apie reikšmingą prielaidą. Ir tiesiog, kad būtų aišku, kas prielaida buvo man padaryti ieškant per šią telefonų knygoje? Tai Mike'as Smithas buvo telefonų knyga, nors aš galėtų tvarkyti scenarijus be jo ten, jei aš tiesiog sustojo anksti. Knyga abėcėlės. Ir tai yra labai turtinga prielaida, nes tai reiškia someone-- Aš tipo pjovimo kampą, kaip aš greičiau, nes kažkas kitas padarė daug sunkaus darbo man. 

Bet kas, jei telefonas knyga buvo Nerūšiuotos? Gal Verizon "gavo tingus, tiesiog išmetė kiekvieno žmogaus vardai ir numeriai ten gal ta tvarka, kuria jie užsiregistravau telefono paslauga. Ir kiek laiko tai užtruks mane rasti ką nors panašaus Mike Smith? 1000 puslapis telefonas book-- kiek puslapiai turiu atrodyti per? 

Visi jie. Jūs esate tarsi iš laimės. Jūs tiesiog turite pažvelgti į kiekvieną puslapis, jei telefonas knyga yra tiesiog atsitiktinai rūšiuojami. Jūs galite gauti pasisekė ir sužinoti Mike ant labai pirmajame puslapyje, nes jis buvo pirmasis klientas užsakyti telefono paslaugą. Bet jis galėjo būti paskutinis, taip pat. 

Taigi atsitiktine tvarka nėra gera. Taigi tarkime, turime rūšiuoti telefonų knyga arba apskritai rūšiavimo duomenų kad mes buvo suteikta. Kaip mes galime padaryti? 

Na, leiskite man tiesiog pabandykite paprastas pavyzdys čia. Leiskite man eiti į priekį ir išmesti Keletas numeriai ant lentos. Tarkime, skaičius, mes turime yra, tarkim, keturi, du, vienas, trys. Ir, Benas, rūšiuoti šiuos numerius už mus. 

Gerai. Kaip tu tai padarei? Gerai. Taigi pradėkite nuo mažiausio vertė ir didžiausias, ir tai tikrai gera intuicija. Ir suprasti, kad mes žmonės yra iš tikrųjų labai gerai problemų sprendimo kaip tai, ne mažiau kaip kai duomenys yra palyginti mažas. Kai tik pradėsite turėti šimtus skaičių, tūkstančiai skaičių, Milijonai numeriai, Benas tikriausiai negalėjo padaryti gana, kad greitai, darant prielaidą, kad ten buvo spragų skaičių. Gana lengva suskaičiuoti iki milijono kitaip, tiesiog laiko. 

Taigi algoritmas atrodo kaip Benas naudojami tik dabar buvo ieškoma mažiausio skaičiaus. Taigi, nors mes, žmonės gali imtis į daug informacijos vizualiai, kompiuteris yra iš tikrųjų šiek tiek daugiau ribotas. Kompiuteris gali tik peržvelgsite vienas baitas tuo metu, ar gal keturių baitų vienu LAIKĄ_ šių dienų, o gal 8 baitai vienu LAIKĄ_ bet labai nedaug baitų tam tikru metu. 

Todėl, kad mes tikrai turime keturi atskiri vertės here-- ir jūs galite galvoti apie Ben kaip turintys ne laukai ant jeigu jis buvo kompiuteryje, pavyzdžiui kad jis negali matyti nieko kito nei vieną numerį LAIKĄ_ todėl mes paprastai laikys, kaip ir Anglų, mes skaityti iš dešinės į kairę. Taigi pirmas skaičius Benas tikriausiai atrodė ne buvo keturių ir tada labai greitai supratau, kad gana didelė number-- leiskite nuolat ieško. 

Yra du. Palauk minutę. Du yra mažesnis kaip keturi. Aš ruošiuosi prisiminti. Du dabar mažiausias. Dabar one-- kad netgi geriau. Štai dar mažesnė. Aš ruošiuosi pamiršti apie du ir tiesiog prisiminti dabar. 

Ir jis galėtų sustabdyti ieškote? Na, jis galėtų pagrįsti į šią informaciją, bet verčiau paiešką dėl sąrašo poilsio. Nes kas, jei nulinis buvo sąraše? Ką daryti, jei neigiamas buvo sąraše? Jis tik žino, kad jo atsakymas yra teisingas, jei jis išsamiai patikrinti visą sąrašą. Taigi, mes pažvelgti į tai poilsio. Three-- tai buvo tik laiko švaistymas. Turite nepasisekė, bet aš buvau dar teisingai padaryti. Ir todėl dabar jis matyt pasirinkta mažiausią skaičių ir tiesiog įdėti jį pradžioje sąrašo, nes aš padarysiu čia. Dabar, ką veikei šalia, nors tu negali galvoti apie tai beveik į šį kiek? Pakartokite šį procesą, todėl kai kurie iš kilpos natūra. Yra susipažinę idėja. Taigi čia yra keturi. Štai šiuo metu mažiausias. Štai kandidatas. Jau nebe. Dabar aš mačiau du. Štai kitas mažiausias elementas. Three-- tai ne mažesnis, todėl dabar Benas gali išplėšti iš dviejų. 

Ir dabar mes pakartokite šį procesą ir Žinoma trijų gauna ištraukė toliau. Pakartokite šį procesą. Keturi gauna ištrauktas. Ir dabar mes iš skaičių, todėl sąraše turi būti rūšiuojami. 

Ir iš tiesų, tai yra formalus algoritmas. Kompiuteris mokslininkas būtų tai vadina "atranka rūšiuoti", idėja yra tarsi sąrašą iteratively-- vėl ir vėl ir vėl pasirinkdami mažiausias skaičius. Ir kas malonu apie tai tai tik taip adyti intuityvus. Tai taip paprasta. Ir jūs galite pakartoti tą patį vėl ir vėl operacija. Tai paprasta. 

Šiuo atveju tai buvo greitai, bet kiek laiko ji iš tikrųjų imtis? Leiskite, kad ji atrodo ir jaučiasi šiek tiek daugiau varginantis. Taip vieną, du, tris, keturis, penkis šešių, septynių, aštuonių, devynių, 10, 11, 12, 13, 14, 15, 16-- kokiam. Aš tik norėjau daugiau tai laiko nei tik keturi. Taigi, jei aš turiu visą krūva skaičių now-- ją nėra net nesvarbu ką jie are-- tegul galvoti apie tai, kas tai algoritmas tikrai patinka. 

Tarkime, yra numeriai ten. Vėlgi, nesvarbu kas jie, bet jie atsitiktinai. Aš taikant Ben algoritmas. Man reikia pasirinkti mažiausią skaičių. Ka aš darau? Ir aš ruošiuosi fiziškai tai padaryti šįkart veikti jį. Domina, ieško, ieško, ieško, ieško. Tik iki to laiko gaunu iš sąrašo pabaigoje gali Suprantu mažiausias skaičius buvo du šį kartą. Vienas ne sąraše. Taigi aš pribaigti du. 

Ką daryti toliau? Domina, ieško, ieško, ieško. Dabar radau skaičius septyni, nes ten spragų šių numbers-- bet tiesiog savavališkai. Gerai. Taigi dabar galiu pribaigti septyni. Domina ieško, ieško. 

Dabar aš darant prielaidą, nuo Žinoma, kad Benas nėra turi papildomą RAM, papildomai atminties, nes, žinoma, Žiūriu tuo pačiu numeriu. Žinoma, galėčiau prisiminti visus tuos numerius, ir tai visiškai teisinga. Bet jei Benas prisimena visi iš numerių jis matė, jis nebuvo tikrai padarė esminę pažangą, pasiektą nes jis jau turi gebėjimas paiešką per numerius ant lentos. Prisimindamas visas numeriai nepadeda, nes jis vis dar gali kaip kompiuteris tik pažvelgti, mes pasakė: vieną numerį tuo metu. Taigi nėra jokio cheat rūšiuoti ten, kad jūs galite naudoti. 

Taigi iš tikrųjų, kaip aš nuolat ieško sąrašą, Aš tiesiog turiu tik nesustoti pirmyn ir atgal per jį, skynimas iš Kitas mažiausias skaičius. Ir kaip jūs galite rūšies išvadą iš mano kvailus judesius, Tai tiesiog gauna labai nuobodus labai greitai, ir man atrodo, kad bus grįžta ir pirmyn, pirmyn ir atgal gana šiek tiek. Dabar būtų teisinga, aš neturiu eiti visai taip, gerai, tegul see-- būtų teisinga, Aš neturiu vaikščioti gana kaip daug žingsnių kiekvieną kartą. Nes, žinoma, kaip aš pasirinkti numerius iš sąrašo likusi sąrašas trumpėja. 

Ir todėl galime galvoti apie kiek žingsnių aš iš tikrųjų traipsing per kiekvieną kartą. Be pirmųjų situacijoje mes turėjome 16 numerius, ir taip maximally-- tegul tik tai padaryti už discussion-- Turėjau atrodyti per 16 numeriai rasti mažiausias. Bet kai aš nupeštos iš mažiausias skaičius, kaip ilgai buvo likęs sąrašą, žinoma? Tiesiog 15. Taigi, kaip daugelis numeriai padarė Benas ar turiu ieškoti per antrą kartą aplink? 15, tiesiog eiti ir rasti mažiausias. Bet dabar, žinoma, sąrašas, taip pat mažesni nei buvo anksčiau. Taigi, kiek žingsnių aš turi priimti kitą kartą? 14 ir tada 13 ir tada 12, plius taškų, taškas, taškas, kol aš kairėje su tik vieną. Taigi, dabar kompiuteris mokslininkas būtų paklausti, gerai, ką tai visi lygūs? Tai iš tikrųjų yra lygus keletas konkrečių skaičius, kad galėtume tikrai padaryti aritmetiškai, bet mes norime kalbėti apie algoritmų efektyvumo šiek tiek daugiau formulaically, nepriklausoma nuo to, kaip ilgai sąrašas. 

Ir taip, jūs žinote, ką? Tai 16, bet kaip minėjau anksčiau, tegul tiesiog skambinkite problemos dydį n, kur n yra kai numeris. Gal tai 16, o gal tai trys, gal tai milijoną. Nežinau. Man nerūpi. Ką aš tikrai noriu tai formulė, kad galiu naudoti palyginti šį algoritmą prieš kitus algoritmus kad kas nors gali reikalauti yra geriau ar blogiau. 

Todėl Pasirodo, ir tik aš žinau, tai iš pradinėje mokykloje, kad tai iš tikrųjų veikia iš į tą patį dalykas kaip n per n plius viena virš dviejų. Ir tai atsitinka lygūs, iš Žinoma, n kvadratu plius n virš dviejų. Taigi, jei aš norėjau formulę už kiek žingsnių dalyvavo žiūri visi iš vėl ir vėl tų skaičių ir vėl ir vėl, sakyčiau tai n kvadratu plius n virš dviejų. Bet žinote ką? Tai tik atrodo nepatogus. Aš tiesiog tikrai noriu Apskritai jausmas dalykų. Ir jūs tikriausiai pamenate, kad iš aukštosios mokyklos, kad yra aukščiausios užsakymo terminas sąvoka. Kuris iš šių terminų, n langeliais, su N, ar pusę, turi didžiausią įtaką per tam tikrą laiką? Kuo didesnis n gauna, kuris iš labiausiai šiais klausimais? 

Kitaip tariant, jei aš prijungti iš milijono n kvadratu bus greičiausiai dominuojantis veiksnys, nes milijoną kartų pati yra daug didesnis nei plius vienas papildomas mln. Taigi jūs žinote, ką? Tai yra toks Lāpīt didelis numeris, jei kvadratinių numerį. Tai tikrai ne klausimas. Mes tiesiog ketiname kryžių, kad iš ir pamiršti apie jį. Ir taip kompiuteris mokslininkas pasakytų kad šio algoritmu, efektyvumas yra n tam, squared-- Aš turiu galvoje išties apytikriai. Jis tarsi maždaug n kvadratu. Laikui bėgant, tuo didesnis ir didesni N gauna, tai yra geras įvertinimas už tai, ką efektyvumas arba efektyvumo trūkumas Šio algoritmo iš tikrųjų yra. Ir aš gauti, kad, žinoma, iš tikrųjų daro matematiką. Bet dabar aš tiesiog mojuodami mano rankos, nes aš tiesiog noriu bendrąja prasme šios algoritmas. 

Taigi, naudojant tą pačią logiką, tuo tarpu, aptarkime kitą algoritmą mes jau atrodė at-- linijinis paiešką. Kai aš ieškojau už telefoną book-- nėra rūšiavimas, paieška per telefoną book-- mes nuolat kartojo, kad tai buvo 1000 žingsnių, arba 500 žingsnius. Bet tegul apibendrina, kad. Jei yra n puslapių telefonų knyga, kas važiavimo laikas arba efektyvumas tiesinės paieškos? Tai apie tam kiek žingsnių rasti Mike'as Smithas naudojant tiesinę paiešką, The pirmasis algoritmas, arba net antra? 

Blogiausiu atveju, Mike yra knygos pabaigoje. Taigi, jei telefonas knyga turi 1000 puslapių, sakėme paskutinį kartą, blogiausiu atveju, tai gali užtrukti maždaug kaip daug puslapių rasti Mike? Kaip 1,000. Tai viršutinė riba. Tai blogiausia įmanoma situacija. Bet vėl, mes tolsta iš skaičiais, pavyzdžiui, 1000 dabar. Tai tiesiog n. 

Taigi, kas yra logiška išvada? Ieškoti mike telefoną knyga, kuri turi n puslapių gali užtrukti, o labai blogiausiu atveju, kiek žingsnių dėl n tam? Ir iš tiesų kompiuteris mokslininkas pasakytų kad, veikimo laiką, arba iš nevykdymo ar efektyvumas ar neefektyvumas, kurių, kaip algoritmas linijinis paieška yra n tvarka. Ir mes galime taikyti tą patį logika kirtimo kažką iš kaip aš ką tik padariau antrą algoritmas mes turėjome su telefono knyga, kur mes nuėjome du puslapius vienu metu. 

Taigi 1000 puslapis telefonų knyga galėtų mus 500 puslapis posūkiai, plius vienas jei mes dvigubai atgal truputį. Taigi, jei telefono knyga turi n puslapių, bet mes darome du puslapius vienu metu, tai maždaug kas? N. virš dviejų, kad lyg n per dvi. Bet aš padariau teiginio akimirka prieš, kad N per two-- kad tipo tas pats, kaip tik n. Tai tiesiog pastovus veiksnys, kompiuterių mokslininkai pasakytų. Leiskite tik sutelkti dėmesį į kintamieji, really-- didžiausi kintamieji lygtys. 

Taigi linijinis paieška, ar padaryti vieną puslapis vienu metu arba du puslapiai vienu metu, yra tarsi iš esmės tas pats. Tai vis dar n tvarka. Bet aš teigė su mano paveikslėlyje anksčiau kad trečiasis algoritmas nebuvo linijinis. Tai buvo ne tiesia linija. Ji buvo tai, kad išlenkta linija, ir algebrinė formulė buvo kas? Prisijungti nuo n-- taip logaritmas du n. Ir mes neturime eiti į pernelyg daug detalė logaritmas šiandien bet dauguma kompiuterių mokslininkai nebūtų net pasakyti, kas pagrindas yra. Kadangi visa tai tik nuolatiniai faktoriai, taip sakant, tik šiek tiek skaitmeniniai skirtumai. Ir taip, tai būtų labai dažna būdas ypač formalaus kompiuterio mokslininkai lentos arba programuotojai at baltos lentos iš tikrųjų teigdamas, kuri algoritmas jie būtų naudoti ar ką efektyvumas iš jų algoritmas. 

Ir tai nebūtinai kažkas Jūs aptarti bet labai išsamiai, bet geras programuotojas yra kažkas kas turi tvirtą, oficialų fone. Jis galėtų kalbėti Jums šiame kelyje rūšies ir iš tikrųjų padaryti kokybiniai argumentai kaip kodėl vienas algoritmas arba vienas gabalas programinės įrangos, yra pranašesnis tam tikru būdu į kitą. Kadangi jūs tikrai galėtų tiesiog paleisti vienas žmogus programą ir skaičiuoti sekundžių skaičių ji mano, kad rūšiuoti kai kuriuos skaičius, ir jūs galite paleisti kai kito asmens programa ir skaičiuoti numerį sekundžių užtrunka. Tačiau tai yra daugiau apskritai būdas, kad galite naudoti analizuoti algoritmus, jei bus, tiesiog ant popieriaus ar tiesiog žodžiu. Net paleisti jį be net bando pavyzdžius įėjimai, galite tiesiog samprotauti per ją. Ir taip su nuomos kūrėjas arba jei turintys jam ar jai tarsi teigia, jums kodėl jų algoritmas, jų paslaptis padažas ieško milijardus tinklalapių jūsų Bendrovė yra geriau, tai yra argumentų rūšių jie idealiu atveju turėtų būti suteikta galimybė. Arba bent jau tai yra Daiktų rūšys kad būtų sugalvoti svarstymo metu jau labai formalios diskusijos. Gerai. Taigi Benas pasiūlė kažką vadinamas atranka rūšiuoti. Bet aš ruošiuosi pasiūlyti, kad yra kitų būdų tai padaryti, taip pat. Ką aš nelabai patinka apie Beno algoritmas yra tai, kad jis nuolat vaikščioti, arba to, man vaikščioti, pirmyn ir atgal ir pirmyn ir atgal ir į priekį ir atgal. Ką daryti, jei vietoj aš būčiau daryti kažkas panašaus į šiuos numerius čia ir aš buvo tiesiog susidoroti su kiekvienu skaičius savo ruožtu, kaip aš ją atidavė? 

Kitaip tariant, čia Mano sąrašas numerius. Keturių, vienas, trys, du. Ir aš ruošiuosi daryti toliau. Aš ruošiuosi įrašyti skaičius kur jie priklauso, o , nei pasirinkti jiems vienu metu. Kitaip tariant, čia yra numeris keturi. 

Štai mano originalus sąrašą. Ir aš ruošiuosi išlaikyti iš esmės naujas sąrašas čia. Todėl tai yra senas sąrašas. Tai yra nauja sąrašas. Matau numeris keturi pirmas. Mano naujas sąrašas pradžių tuščias, todėl banaliai atvejis kad keturi dabar asorti sąrašą. Aš tik atsižvelgiant į skaičių aš tikrą, ir aš išleisti jį į mano naują sąrašą. 

Ar ši nauja sąrašas rūšiuojami? Taip. Tai kvaila, nes ten tik vienas elementas, bet jis absoliučiai rūšiuojami. Nėra nieko iš vietos. Tai įdomiau, šis algoritmas, kai aš pereiti prie kito žingsnio. 

Dabar turiu vieną. Taigi vienas, žinoma, priklauso ne pradžioje arba šios naujos sąrašo pabaigoje? Pradžia. Taigi turiu padaryti tam tikrą darbą dabar. Aš jau vartojate kai laisvės su mano persekiotoją tiesiog piešimo dalykus kur aš noriu juos, bet tai tikrai ne tiksli kompiuteryje. Kompiuteris, kaip žinome, turi RAM arba Random Access Memory, ir tai vienas baitas ir kitas baitas o kitas baitas. Ir jei jūs turite GIGABYTE RAM turite milijardas baitų, bet jie fiziškai vienoje vietoje. Jūs negalite tiesiog perkelti stuff aplink traukiant jį ant lentos ten, kur norite. Taigi, jei mano naujas sąrašas keturių vietų atmintyje, deja keturi yra jau į neteisingą vietą. 

Taigi, norint įterpti numeris vienas Aš negaliu tiesiog atkreipti jį čia. Tai atminties vieta neegzistuoja. Tai būtų oszukiwanie, ir aš jau oszukiwanie pavaizduotomis piktogramo- kelias minutes čia. Taigi tikrai, jei noriu įdėti vieną čia Turiu laikinai kopijuoti keturi ir tada įdėti vieną ten. 

Tai gerai, tai teisinga, tai techniškai įmanoma, bet suprantu, kad tai papildomas darbas. Aš ne tiesiog įdėti skaičių vietoje. Aš pirmą kartą buvo deportuoti skaičius, tada įdėti jį į vietą, todėl aš rūšies padvigubėjo mano darbo krūvį. Taigi keep that in mind. 

Bet aš dabar daroma su šio elemento. Dabar aš noriu patraukti numeris trys. Jei žinoma, tai priklauso? Tarp. Aš negaliu apgauti nebėra ir tiesiog padėkite jį ten, nes, vėlgi, šis atminties yra fizinių vietose. Taigi turiu kopijuoti keturi ir įdėti tris čia. Ne big deal. Tai tik vienas papildomas žingsnis again-- jaučiasi labai nebrangu. 

Bet dabar aš pereiti į dvi dalis. Du, žinoma, priklauso čia. Dabar jūs pradėsite matyti, kaip darbas gali sukaupti. Dabar, ką aš turiu daryti? Taip, turiu perkelti keturi, tada turiu kopijuoti trys, ir dabar aš galiu įdėti du. Ir laimikis su šiuo algoritmas, Įdomu, yra tai, kad tarkime turime daugiau ekstremalių atveju, kai jis tarkim aštuoni, septyni, šešių, penkių, keturių, trijų, du, vienas. Tai yra, įvairiomis aplinkybėmis, blogiausiu atveju, nes darn dalykas yra tiesiog atgal. 

Tai tikrai ne įtakos Ben algoritmas, nes Beno atrankos Rūšiuoti jis ketina išlaikyti vyksta ir atgal per sąrašo. Ir todėl, kad jis buvo visada ieškome per visą likusį sąrašą, nesvarbu kur elementai yra. Tačiau šiuo atveju su mano įterpimo approach-- pabandykime tai. 

Taip vieną, du, tris, keturis, penki, šeši, septyni, aštuoni. Vienas du trys keturi, penki, šeši, septyni, aštuoni. Aš ruošiuosi imtis aštuoni, ir kur man jį? Na, bent mano sąrašo pradžioje, nes ši nauja sąrašas surūšiuotas. Ir aš kirsti jį. 

Kur aš įdėti septyni? Darn ją. Reikia eiti ten, todėl Aš turiu padaryti tam tikrą kopijavimą. Ir dabar septyni eina čia. Dabar aš pereiti prie šešių. Dabar tai dar daugiau darbo. 

Aštuoni turi eiti čia. Septyni turi eiti čia. Dabar šešių galite eiti čia. Dabar aš patraukti penki. Dabar aštuonios turi eiti čia septyni turi eiti čia šešių turi eiti čia, ir dabar penki ir pakartokite. Ir aš gana daug perkelti jį nuolat. 

Taigi pabaigoje, tai algorithm-- mes vadina jį įterpimo sort-- tikrųjų turi daug darbo, taip pat. Tai tiesiog skirtingi Darbo pobūdis, nei Benas-aisiais. Ben darbas buvo man vyksta pirmyn ir atgal visą laiką, Pasirinkę kitą mažiausias elementas vėl ir vėl. Taigi tai buvo tai labai vizualiai rūšies darbą. 

Tas kitas algoritmas, kuris yra vis dar correct-- jis gaus darbą done-- tiesiog keičia darbo kiekį. Atrodo, iš pradžių jūs taupyti, nes jūs tiesiog susijusius su kiekvieno elemento priekyje be vaikščioti visi būdas per sąrašą, kaip Ben buvo. Bet problema yra, ypač jų Crazy atvejų, kai visa tai atgal, jūs tiesiog rūšies atidėti sunkų darbą kol jūs turite išspręsti savo klaidų. 

Ir taip, jei jūs galite įsivaizduoti, tai aštuoni septyni, šeši ir penki ir vėliau keturių ir trijų ir dviejų perkelti savo kelią per sąrašą, mes ką tik pasikeitė tipo darbe mes darome. Užuot ją ne pradžioje mano iteracijos, Aš tiesiog tai daro ne pabaigoje kiekvieno pakartojimo. Taigi paaiškėja, kad šio algoritmo, taip pat paprastai vadinamas įterpimo rūšiuoti, yra taip pat dėl ​​tam n kvadrato skerspjūvį. Tai tikrai ne geriau, ne geriau ne visiems. 

Tačiau yra ir trečias kelias Norėčiau paskatinti mus apsvarstyti, kuris yra tai. Taigi tarkime savo sąrašą, paprastumo vėl, yra keturi, vienas, trys, two-- tik keturi skaičiai. Benas turėjo gerą intuiciją, geras žmogaus intuicija anksčiau, pagal kurį mes fiksuoto visa sąrašą eventually-- įterpimo rūšiuoti. Aš coaxed mus kartu. Bet tegul apsvarstyti Paprasčiausias būdas išspręsti šį sąrašą. 

Šis sąrašas nėra rūšiuojamos. Kodėl? Anglų kalba paaiškinti, kodėl tai nėra iš tikrųjų rūšiuojami. Ką tai reiškia negali būti rūšiuojami? 

STUDENTŲ: Tai ne nuoseklusis. 

DAVID Malan: Ne nuoseklusis. Duok man pavyzdį. 

STUDENTŲ: Įdėkite juos tvarka. 

DAVID Malan: Gerai. Duok man daugiau konkretų pavyzdį. 

STUDENTŲ: didėjančia tvarka. DAVID Malan: Ne Didėjančia tvarka. Tiksliau. Aš nežinau, ką reiškia didėjančia tvarka. Kas negerai? 

STUDENTŲ: Mažiausia iš numeriai yra ne pirmoje erdvėje. 

DAVID Malan: Mažiausias skaičius s ne pirmoje erdvėje. Būti konkretesnis. Aš pradedu pagauti. Mes tikimės, tačiau kas iš tam čia? 

STUDENTŲ: skaičių seka. DAVID Malan: skaičių seka. Kiekvieno žmogaus rūšies palaikymo tai here-- labai aukšto lygio. Tiesiog tiesiog pasakykite man, kas negerai kaip penkerių metų senumo jėgomis. 

STUDENTŲ: Plius vienas. 

DAVID Malan: Kas tai? 

STUDENTŲ: Plius vienas. 

DAVID Malan: Ką reiškia plius vienas? Duok man kitoks penkerių metų senumo. Kas negerai, mama? Kas negerai, tėtis? Ką reiškia tai nėra rūšiuojamos? 

STUDENTŲ: Tai nėra tinkama vieta. 

DAVID Malan: Kas nėra reikiamoje vietoje? 

STUDENTŲ: Keturi. DAVID Malan: Gerai, gerai. Taip keturių yra ne ten, kur ji turėtų būti. Visų pirma, tai yra tiesa? Keturių ir vienas, pirmasis du numeriai matau. Ar tai teisinga? Ne, jie iš tam, tiesa? Tiesą sakant, manau, kad dabar apie kompiuterio, taip pat. Tai gali atrodyti tik gal vieną, gal du dalykus once-- ir iš tikrųjų tik vienas dalykas vienu metu, tačiau ji gali bent pažvelgti vienas dalykas tada Kitas dalykas, šalia jo. 

Taigi šitie tam? Žinoma ne. Taigi jūs žinote, ką? Kodėl mes kūdikį žingsniai, kaip sutvarkyti šią problemą užuot šias išgalvotas algoritmai kaip Ben, kur jis tarsi nustatant jį iki apsisukimo per sąrašą užuot ką aš padariau, kur Aš tiesiog rūšies sutaisė, kaip mes einame? Tegul tik pažodžiui sugriauti sąvoka order-- eilės, vadina jį ką want-- į šias poravimas palyginimų. 

Keturi ir vienas. Ar tai teisinga tvarka? Taigi leiskite nustatyti, kad. Vienas ir keturių, ir tada mes tiesiog nukopijuokite kad. Gerai, gerai. Aš fiksuotas vienas ir keturi. Trys ir du? Ne. Tegul mano žodžiai atitiktų mano pirštus. Keturių ir trijų? 

Tai ne tam, kad aš ruošiuosi padaryti vieną, trys, keturios, dvi. Gerai. Dabar keturių ir dviejų? Mums reikia išspręsti šią problemą, taip pat. Taip vienas, trys, du, keturi. Taigi tai rūšiuojami? Ne, bet tai arčiau rūšiuojami? 

Tai, nes jau sutvarkėme tai klaida, jau sutvarkėme šią klaidą, ir mes fiksuoto šią klaidą. Taigi, mes fiksuoto tris klaidas, be abejo. Iki šiol nėra tikrai atrodo rūšiuojamos, bet jis yra objektyviai arčiau Rūšiuota nes jau sutvarkėme kai kurie iš šių klaidų. 

Dabar, ką daryti toliau? I rūšies pasiekė sąrašo pabaigoje. Aš, atrodo, fiksuoto visi klaidų, bet ne. Kadangi šiuo atveju, kai kurie numeriai galėjo burbuliukais arčiau kitų numerių, vis dar iš eilės. Taigi leiskite tai padaryti dar kartą, ir aš just do it vietoje šį kartą. Vienas ir trijų? Viskas gerai. Trys ir du? Žinoma ne, tad pakeisti. Taip du, trys. Trijų ir keturių? O dabar tegul tiesiog būti ypač pedantiškas čia. Ar rūšiuojami? Jūs, žmonės žino, kad manimi rūšiuojami. 

Turėčiau bandykite dar kartą. Taigi Olivia siūlo bandau dar kartą. Kodėl? Dėl to, kad kompiuteris neturi mūsų žmogaus akis prabanga tiesiog skaitydamas back-- Gerai, aš padariau. Kaip veikia kompiuteris nustatyti kad tas sąrašas būtų dabar rūšiuojami? Mechaniškai. 

Turėčiau eiti per dar kartą, ir tik tuomet, jei aš neverskite / rasti jokių klaidų galiu tada sudaryti kaip kompiuteriu, yep, mes gerai eiti. Taigi vienas ir du, du ir trys, trijų ir keturių. Dabar galiu galutinai pasakyti, kad tai yra rūšiuojamos, nes aš padariau jokių pakeitimų. Dabar tai būtų klaida ir tiesiog kvaila, jei aš, kompiuteris, paklausė tuos pačius klausimus vėl tikisi skirtingus atsakymus. Neturėtų atsitikti. 

Ir taip dabar sąrašas surūšiuotas. Deja, bėgimas laiką šis algoritmas taip pat n kvadratu. Kodėl? Kadangi jūs turite N numeriai, o blogiausiu atveju jūs turite perkelti n numerius n kartų, nes jūs turite nesustoti atgal patikrinti ir galbūt nustatyti Šie skaičiai. Ir mes galime padaryti daugiau oficialią analizę, taip pat. 

Taigi visa tai pasakyti mes atlikome trys skirtingi požiūriai, viena iš jų iš karto intuityvus nuo šikšnosparnių nuo Ben mano pasiūlytą įterpimo Rūšiuoti šį vieną kur rūšies pamiršti Už medžių pradžių miškas. Bet tada, jei žengti žingsnį atgal, voila, mes fiksuoto rūšiavimo sąvoką. Taigi, tai yra, Dare pasakyti, Žemesnio lygio gal nei kai kurios kitos algoritmai, bet tegul pamatyti, jei mes negalime įsivaizduoti tai būdu tai. 

Taigi tai yra kai gražus programinė įranga, kad kažkas rašė naudojant spalvinga barai ŠTAI ketina atlikti šiuos mums. Kiekviena iš šių barų reiškia skaičių. Aukštesni juosta, tuo didesnis skaičius, mažesnis baras, tuo mažesnis skaičius. Taigi idealiai norime gražią piramidę kur ji prasideda maži ir gauna didelis, ir tai reikštų, kad šie strypai yra rūšiuojami. Taigi, aš ruošiuosi eiti į priekį ir pasirinkti, Pavyzdžiui, Ben algoritmas first-- pasirinkimas rūšiuoti. 

Ir pastebėsite, ką jis daro. Kaip jie pasirinkote vizualizuoti šį algoritmą yra tai, kad, kaip ir aš buvo vaikščioti per savo sąrašą, Ši programa yra ėjimas per savo sąrašą skaičių, pabrėžiant rožinė kiekvienos skaičius, kad jis žiūri. Ir kas bręsti dabar? 

Mažiausias skaičius, kurį I arba Benas rado staiga pasireiškia perkeltas į sąrašo pradžioje. Ir pranešimas, jie padarė iškeldinti skaičius, kad ten buvo, ir tai visiškai gerai. Aš negavau į tą detalumo lygiu. Bet mums reikia įdėti šis skaičius kažkur, todėl mes tiesiog perkėlė ją į atvira vieta, kuri buvo sukurta. Taigi, aš ruošiuosi pagreitinti šį aukštyn, nes kitaip tampa labai nuobodus greitai. Animacijos speed-- ten einame. Taigi dabar pats principas Man buvo taikyti, bet jūs gali pradėti jaustis algoritmą, jei bus, ar šiek tiek aiškiau matyti. Ir šis algoritmas turi poveikio į Pasirinkę kitą mažiausią elementą, todėl jūs ketinate pradėti matyti kelią iki kairėje. Ir ant kiekvienos iteracijos, kaip aš Siūloma, ji šiek tiek mažiau darbo. Ji neturi eiti visą kelią atgal į kairę sąrašo pabaigoje, nes ji jau žino tie yra rūšiuojami. Taigi rūšies jaučiasi tai paspartinti, net jeigu kiekvienas žingsnis yra atsižvelgiant tą patį laiką. Yra tik mažiau žingsnių likę. Ir dabar jūs galite rūšies jaučiasi algoritmas išvalyti jo pabaigos, ir iš tikrųjų dabar jis rūšiuojami. 

Taigi įterpimo rūšiuoti yra viskas padaryta. Man reikia naujo atsitiktine masyvo. Ir pastebėsite galiu tik išlaikyti randomizuojant ją, ir mes gauti suderinimo Tas pats metodas, įterpimo rūšiuoti. Leiskite lėtai jį žemyn, kad čia. Pradėkime, kad per. Sustabdyti. 

Leiskite praleisti keturi. Čia mes eiti. Atsitiktinė jie masyvo. Ir čia mes go-- įterpimo rūšiuoti. Groti. Atkreipkite dėmesį, kad tai susiję su kiekviena elementas ji susiduria karto, bet jei jis priklauso ir netinkamoje vietoje pranešimas visus darbus, kad turi atsitikti. Mes turime išlaikyti vis didesnę ir daugiau elementų, kad paliktume vietos už vieną norime įdiegti. 

Taigi mes sutelkiant dėmesį į liko galas tik, sąrašą. Reikėtų atkreipti dėmesį, mes net atrodė at-- mes nebuvo pabrėžta rožinė nieko į dešinę. Mes tiesiog bendraujant su problemos, kaip mes einame, bet mes sukuriant daug dirbti sau ramiai. Ir taip, jei mes pagreitinti tai iki dabar eiti iki pabaigos, ji turi skirtingą feel it iš tikrųjų. Tai tiesiog dėmesio kairėje pabaigos, tačiau daro šiek tiek daugiau darbo, kaip needed-- rūšies suglodinimo dalykų daugiau, tvirtinimo dalykų, bet sprendžiant, galiausiai, su kiekvienas elementas vienu metu kol mes gauti gerai padirbėti, mes Visi žinome, kaip tai vyksta iki pabaigos, todėl šiek tiek underwhelming galbūt. 

Tačiau į end-- sąrašas spoiler-- ketina būti rūšiuojami. Taigi pažvelkime vieną paskutinis. Mes negalime tiesiog praleisti dabar. Mes beveik ten. Du eiti, viena eiti. Ir voila. Puikus. 

Taigi dabar padarykime paskutinį vieną, naujo randomizuojant su burbulas rūšiuoti. Ir pastebėsite čia, ypač jei aš lėtai jį žemyn, tai nuolat krenta per. Bet pastebėsite jis tiesiog daro poromis comparisons-- Rūšiuoti vietos sprendimus. Bet kaip tik mes turime Iš rožinių sąrašo pabaigoje, kas teks vėl vyksta? Taip, tai teks pradėti iš naujo, nes tai tik fiksuoto poromis klaidų. Ir tai galėjo atskleidė dar kitus. Ir todėl, jei greitis tai iki, jūs matyti, kad, kiek rodo pats pavadinimas, mažesnių elements-- arba, tiksliau, Didesnės elements-- pradeda burbulas iki viršaus, jei bus. Ir mažesni elementai pradeda burbuliukų žemyn į kairę. Ir iš tiesų, tai kokios vizualinis poveikis, taip pat. Ir todėl tai bus baigti apdailos labai panašiu būdu, taip pat. 

Neturime gyventi dėl šio konkretaus vieną. Leiskite atidaryti tai dabar taip pat. Yra keletas kitų rūšiavimo algoritmai pasaulyje, keletas iš kurių fiksuojamos čia. Ir ypač besimokantiems, kurie nėra nebūtinai vaizdo ar matematinis, kaip mes padarėme anksčiau, mes galime Taip pat tai padaryti audially jei mes susieti garsą tai. Ir tiesiog for fun, čia Keletas skirtingų algoritmų, ir vienas iš jų ypač esate ketina pranešimas vadinamas "sujungti rūšiuoti." 

Ji iš tikrųjų yra iš esmės geriau algoritmas, toks, kad sujungti rūšiuoti, vienas iš tie ketinate pamatyti, nėra tam n kvadratu. Tai ant tvarka n kartų žurnalą n, kuris iš tikrųjų yra mažesnis ir tokiu būdu greičiau nei tų kitų trijų. Ir yra kita pora kvailas tas, kad mes pamatysime. 

Taigi čia mes einame su kai garsas. Tai įterpimo rūšiuoti, todėl vėl tai tiesiog bendraujant su elementais kaip jie ateina. Tai burbulas rūšiuoti, todėl atsižvelgiant jiems porų vienu metu. Ir vėl didžiausi elementai yra burbuliuoja iki viršaus. 

Toliau pasirinkimas rūšiuoti. Tai Ben algoritmas, kur vėl jis pasirinkus keletą kartų Kitas mažiausias elementas. Ir vėl, dabar galite tikrai išgirsti, kad tai paspartinti, tačiau tik tiek, kiek kaip tai daro vis mažiau ir mažiau dirbti ant kiekvieno pakartojimo. Tai greičiau vienas, sujungti rūšiuoti, kuri rūšiavimas grupes skaičiais kartu ir tada sujungti juos. Taigi look-- į kairę pusę jau yra rūšiuojami. 

Dabar ji rūšiavimas tinkamą pusę, o dabar jis ketina juos sujungti į vieną. Tai yra kažkas, vadinamas "Gnome rūšiuoti." Ir jūs galite rūšies matyti, kad tai vyksta ir atgal, nustatymo darbus šiek tiek čia ir ten, prieš tai pereina prie naujos darbo. Štai ir viskas. Yra dar vienas rūšiuoti, kuris yra tikrai tik akademiniais tikslais vadinamas "kvaila rūšiuoti", kuris trunka Jūsų duomenys, rūšiuoja ją atsitiktinai, ir tada patikrina, ar jis yra rūšiuojami. O jei ne, tai vėl rūšiuoja ją atsitiktinai, patikrina, ar tai rūšiuojamos, o jei ne kartoja. Ir teoriškai, probabilistically tai bus užbaigti, bet po gana šiek tiek laiko. Tai nėra pats efektyvus algoritmų. Todėl bet klausimus dėl šių konkretūs algoritmai ar kas buvo susiję, taip pat? 

Na, tegul dabar erzinti išskyrus tai, ką visi Šios linijos yra tai, kad aš piešimo ir ką aš darant prielaidą kompiuterį gali padaryti po gaubtu. Kłóciłbym, kad visi šie skaičiai Aš nuolat drawing-- jie turi gauti kažkur atmintyje. Mes atsikratyti šio vaikino dabar taip pat. 

Taigi atminties gabalas A computer-- taip RAM DIMM yra ką mes ieškoma vakar, dvigubos Inline Memory module-- atrodo taip. Ir kiekvienas iš šių mažai juoda lustai yra keletas baitų skaičius, paprastai. Ir tada aukso kaiščiai yra kaip ir laidai, kad prijungti jį prie kompiuterio, ir žalia silicio lenta yra tik kas išlaiko viską visi kartu. Taigi, ką tai iš tikrųjų reiškia? Jei I rūšies atkreipti tą patį vaizdą, sakykime paprastumo kad tai DIMM, Dual Inline atminties modulis, yra vienas gigabaitas RAM, vienas gigabaitas atmintis, kuri yra kiek baitų, kad bendras? Vienas gigabaitas yra kiek baitų? Daugiau negu, kad. 1124 yra kilogramas, 1000. Mega yra mln. Giga yra mlrd. 

Aš gulėti? Ar mes net perskaityti etiketę? Tai iš tikrųjų 128 GB, todėl daugiau. Bet mes apsimesti, tai yra tik vienas gigabaitas. Taigi tai reiškia, kad ten milijardų baitų atminties man ar 8 mlrd bitai, bet mes ketiname Įsivažiuoja požiūriu baitų dabar judeti i prieki. 

Taigi, ką tai reiškia, kad tai yra vienas baitas, tai yra dar vienas baitas, tai yra dar vienas baitas, ir jei mes tikrai norėjo būti konkrečiai mes turėtume atkreipti milijardą mažai kvadratų. Bet ką tai reiškia? Na, leiskite man tiesiog padidinti į šiame paveikslėlyje. Jei aš turiu kažką, kad atrodo kaip tai dabar, tai keturi baitai. 

Ir taip galėčiau įdėti keturis numerius čia. Vienas du trys keturi. Arba galėčiau įdėti keturis raidės ar simboliai. "Ei!" gali eiti tiesiai ten, nes kiekvienas iš raidžių, aptarėme anksčiau, gali būti atstovaujama su aštuoniais bitais arba ASCII ar baitas. Taigi, kitaip tariant, jūs galite įdėti 8 mlrd dalykų viduje Šio lazdą atminties. Dabar ką tai reiškia įdėti daiktus atgal atgal į atsarginę atminties patinka tai? Tai ką programuotojas vadinčiau "Matricą". Į kompiuterinę programą, jums nereikia galvoti apie pagrindinės įrangos, per se. Jūs tik pagalvokite apie save kaip turintys prieigą prie milijardas baitų viso ir jūs galite ką nors norite su juo. Bet dėl ​​patogumo tai paprastai naudinga išlaikyti savo atminties teisę vienas šalia kito, kaip šis. Taigi, jei aš priartinkite this-- nes mes tikrai neketiname atkreipti milijardą mažai squares-- tarkime, kad ši diskusijų lenta atstovauja kad atminties Stick dabar. Ir aš tiesiog atkreipti kiek mano žymeklis baigiasi duoti man čia. Taigi dabar mes turime lazdą atminties ant lentos kad gavo vieną, du, trys, keturi, penki, šešių, vienas, du, tris, keturis, penkis, šešis, seven-- taigi 42 baitų atminties ekrane iš viso. Ačiū. Taip, tai padarė mano aritmetika teisinga. Taigi 42 baitų atminties čia. Taigi, ką tai iš tikrųjų reiškia? Na, programuotojas iš tikrųjų paprastai manote apie šį atmintyje kaip adresavimo. Kitaip tariant, kiekvienas vienas iš šių vietos atmintyje, aparatūros, turi unikalų adresą. 

Tai nėra taip sudėtinga, kaip One BRATTLE Aikštė, Kembridžas, masę., 02138. Vietoj to, tai tik skaičius. Tai yra baitas skaičius lygus nuliui, tai yra vienas, tai yra du, tai yra trys, ir tai yra 41. Palauk minutę. Maniau sakė 42 metu senumo. Aš pradėjau skaičiuoti nuo nulio, kad iš tikrųjų teisingas. Dabar mes neturime, kad iš tikrųjų ją nupieškite kaip tinklelis, ir, jei pavaizduoti ją kaip tinklelį Manau, viskas iš tikrųjų gauti šiek tiek klaidinantis. Kas programuotojas būtų, jo ar jos pačios nuomone, apskritai manau, tai atmintis, yra kaip juosta, tarsi maskavimo juosta gabalas kad tik eina ir amžinai arba tol, kol jums paleisti iš atminties. Taigi dažniau būdas atkreipti ir tiesiog galvoti apie atminties būtų, kad tai yra baitas nulis, vienas, dviejų, trijų, tada dot, dot, dot. Ir jūs turite 42 tokie baitų iš viso, net nors fiziškai jis iš tiesų gali būti kažkas daugiau, kaip šis. 

Taigi, jei jūs dabar galvoti apie savo atminties kaip tai, taip pat, kaip juosta, Tai yra tai, ką programuotojas vėl būtų skambinti atminties masyvo. O jei norite, kad iš tikrųjų laikyti kažkas kompiuterio atmintyje, Jūs paprastai padaryti parduotuvių dalykus atsargines-to-back atgal-to-back. Taigi, mes jau kalbame apie numerius. Ir kai aš norėjau išspręsti problemas kaip keturių, vienas, trys, du, nors man buvo tiesiog piešimo tik numeriai keturių, vienas, trys, du ant lentos, kompiuteris būtų tikrai turi šią įrangą atmintyje. 

Ir kas būtų šalia du kompiuterio atmintyje? Na, nėra atsakymas į tai. Mes tikrai nežino. Ir iki tol, kol kompiuteryje nėra reikia, ji neturi rūpintis, kas yra šalia su numeriais ji rūpi. Ir kai aš anksčiau sakė, kad kompiuterio gali ieškoti tik vienu adresu vienu metu, tai kokios, kodėl. 

Ne kitaip įrašo grotuvas ir nuskaitymo galvutė tik kad galėtų pažvelgti į tam tikras griovelis fizine senosios mokyklos įrašo vienu metu, panašiai gali kompiuteris dėka jo procesoriaus ir jos "Intel" instrukcijų rinkinys, tarp kurių instrukcijų skaityti iš atminties arba įrašyti į memory-- Kompiuteris gali atrodyti tik ne vienos kurios nors vietos LAIKĄ_ kartais jų derinys, bet tikrai tik vienoje vietoje vienu metu. Taigi, kai mes darome šie įvairūs algoritmai, Aš ne tik raštu ta vacuum-- keturių, vienas, trys, du. Šie skaičiai iš tikrųjų priklauso kažkur fizinės atminties. Taigi yra maža maža tranzistoriai ar tam tikros rūšies Elektronikos po gaubtas saugoti šias vertybes. 

Ir iš viso, kiek bitų yra dalyvauja dabar, tiesiog, kad būtų aišku? Taigi tai yra keturių baitų, arba dabar tai 32 bitai iš viso. Taigi ten iš tikrųjų yra 32 nuliai ir tie komponavimo šiuos keturis dalykus. Yra net daugiau nei čia, bet vėl mes do not care apie tai. 

Taigi dabar leiskite paklausti kitą Klausimas naudojant atminties, nes kad pabaigoje dienos yra dispersija. Nesvarbu, ką mes galime padaryti su kompiuteris, tuo dienos pabaigoje įranga yra vis dar pats po gaubtu. Kaip man laikyti žodį čia? Na, žodis į kompiuterį kaip "Ei!" būtų saugomi kaip tai. Ir jei jūs norėjo ilgesnės Žodis, galite tiesiog perrašyti, kad ir ką nors pasakyti kaip "labas" ir laikyti, kad čia. 

Ir todėl čia taip pat tai contiguousness yra tikrai privalumas, nes kompiuteris gali tiesiog skaityti iš dešinės į kairę. Bet štai klausimas. Šio žodžio kontekste, H-E-L-L-O, šauktukas, kaip gali kompiuteris žinoti, kur Žodis prasideda ir kur žodis baigiasi? Numerių kontekste, kaip veikia kompiuteris žinoti, kiek laiko sekos numeriai yra arba kai jis pradeda? Na, paaiškėja out-- ir mes ne eiti per daug į šią detail-- lygio Kompiuteriai perkelti stuff aplink atminties pažodžiui būdu šių adresus. Taigi kompiuteryje, jei esate rašyti kodą saugoti daiktus kaip sakant, kas esate tikrai daro rašo išraiškas, kad prisiminti, kur į kompiuterio atminties šie žodžiai. Taigi leiskite man padaryti labai, labai paprastas pavyzdys. 

Aš ruošiuosi eiti į priekį ir atverti paprastą tekstinį programą, ir aš ruošiuosi kurti failas vadinamas hello.c. Dauguma šios informacijos mes neisiu į labai išsamiai, bet aš ruošiuosi rašyti Programa toje pačioje kalba C. Tai labiau bauginanti, Norėčiau teigti, nei nulio, bet tai labai panašus į dvasią. Iš tiesų, tai garbanotas braces-- galite rūšies galvoti apie tai, ką aš tiesiog padarė kaip šis. 

Leiskite tai padaryti, iš tikrųjų. Kai žalia vėliava paspaudėte, atlikite šiuos veiksmus. Noriu atsispausdinti "labas". Taigi tai dabar Pseudocode. Aš rūšies nyksta linijas. C, ši kalba aš kalbu apie, ši eilutė Spausdinti Sveiki iš tikrųjų tampa "printf" su kai skliausteliuose ir pusiau dvitaškis. 

Bet tai lygiai toks pats idėja. Ir tai yra labai patogus "Kai žalia vėliava paspaudėte" tampa Daug daugiau Arcane "int main negaliojančiu." Ir tai tikrai neturi žemėlapių, todėl aš tik ketina ignoruoti tai. Bet garbanotas petnešos yra kaip ir išlenkti įspūdį tai patinka. 

Taigi galite rūšies atspėti. Net jei jūs niekada užprogramuotas anksčiau, ką ši programa tikriausiai daryti? Tikriausiai spausdina Sveiki su šauktuku. 

Taigi pabandykime tai. Aš ruošiuosi ją išsaugoti. Ir tai yra, vėl, labai senosios mokyklos aplinka. Aš negaliu spustelėkite, aš negaliu vilkite. Turiu rašyti komandas. Taigi noriu paleisti savo programą, todėl Galiu tai padaryti, kaip hello.c. Štai failas išbėgau. Bet palaukit, aš trūksta žingsnio. Ką mes sakome, yra būtina pakopą, kaip C kalba? Aš ką tik rašytinis šaltinis kodą, bet ką man reikia? Taip, man reikia kompiliatorių. Taigi mano Mac čia, aš turiu programa, vadinama GCC, GNU C kompiliatoriaus, kuri leidžia man daryti this-- posūkis mano kodo į, mes jį vadiname, mašina kodą. 

Ir matau, kad vėl, taip, tai yra nulių ir aš tiesiog sukurtas iš mano kodo, visi nulių ir. O jei aš noriu paleisti Mano program-- tai atsitinka būti vadinamas a.out už istorinis reasons-- "labas". Galiu paleisti jį dar kartą. Labas labas labas. Ir atrodo, kad reikia dirbti. 

Bet tai reiškia, kad kažkur mano Kompiuterio atmintis yra žodžiai H-E-L-L-O, šauktukas. Ir it turns out, kaip panaikinti, ką kompiuteris būtų paprastai padaryti taip, kad jis žino, kur ko pradėti ir end-- tai ketina pateikti specialų simbolį čia. Ir ši Konvencija įdėti skaičius lygiu nuliui žodžio pabaigos taip, kad žinote, kur jis faktiškai baigiasi, todėl, kad jūs nelaikome spausdinti vis daugiau ir daugiau simbolių, nei jūs iš tikrųjų ketina. 

Bet Takeaway čia net nors tai yra gana neaiškus, yra tai, kad galiausiai gana paprasta. Jūs buvo suteikta tarsi juosta, tuščias erdvė, kurioje galite rašyti laiškus. Jūs tiesiog turite turėti specialus simbolis, kaip ir savavališkai skaičius nulis, įdėti pabaigoje tavo žodžiai, kad kompiuteris žino oi, man reikia sustabdyti spausdinimą Matau šauktukas. Nes kitas dalykas yra yra ASCII reikšmė nulio, arba niekinis pobūdis taip kas nors jį vadiname. Bet ten tipo problema čia, ir tegul grįžti numeriais akimirką. Tarkime, kad aš, tiesą sakant, turėti skaičių masyvą, ir manau, kad Programa aš rašau yra kaip kokybės knygos mokytojui ir mokytojai klasėje. Ir ši programa leidžia jį arba ją įveskite savo mokinių balai nuo viktorinos. Ir manau, kad studentas gauna 100 savo pirmąjį viktorina, gal kaip per 80 kito, tada 75, tada 90 ketvirtą testą. 

Taigi šiuo metu į istoriją, masyvas yra dydžio keturi. Yra visiškai daugiau atminties į kompiuteris, bet masyvas, taip sakant, yra dydžio keturi. Tarkime dabar, kad mokytojas nori priskirti penktą Viktorina klasėje. Na, vienas iš dalykų, jis ar ji ketina daryti dabar laikyti papildomą vertę čia. Bet jei masyvo mokytojas turi sukurta šioje programoje yra dydžio, viena iš problemos, susijusios su masyvo yra tai, kad galite ne tik nuolat pridedant į atmintį. Nes kas, jei kitas dalis Programa turi žodį "ei" tiesiai ten? 

Kitaip tariant, atmintis gali būti naudojama nieko programą. Ir jei iš anksto Aš įvedėte, ei, Noriu įvesti keturių viktorinų balai, jie gali eiti čia ir čia. Ir jei staiga persigalvoti vėliau ir pasakyti, kad aš noriu penktą viktorina rezultatas, jūs galite ne tik įdėti jį ten, kur norite, nes kas, jei tai atminties yra naudojamas kažko else-- nors kita programa ar kokios nors kitos programos funkcija kad jūs dirbate? Taigi, jūs turite galvoti iš anksto kaip norite išsaugoti savo duomenis, nes dabar jūs dažytos Būk į skaitmeninį kampe. 

Taigi mokytojas gali vietoj pasakyti rašant programą saugoti jo ar jos rūšių, žinote, ką? Aš einu prašyti, rašant mano programa, kad noriu nulis, vienas, du, trys, keturi, penki, šeši, aštuoni rūšių iš viso. Taip vieną, du, tris, keturis, penki, šeši, septyni, aštuoni. Mokytojas gali tiesiog per paskirstyti atminties rašant jo ar jos programą ir pasakyti, žinote, ką? Aš niekada priskirti daugiau kaip aštuonis viktorinos per semestrą. Tai tiesiog iš proto. Aš niekada skirti tai. Taigi, kad tokiu būdu jis ar ji turi lankstumas parduotuvė studentų balai, kaip 75, 90, o gal vieną papildomą kur studentas gavo papildomą kreditą, 105. 

Bet jei niekada mokytojas naudoja šias tris erdves, ten intuityvus Takeaway čia. Jis arba ji yra tik išsekimo erdvę. Taigi, kitaip tariant, ten tai bendras kompromisas programavimo kur jūs galite skirstyti tiksliai taip, kaip daug atminties, kaip jūs norite, kurio dugnu yra, kad jūs esate super efficient-- nesate yra išlaidavimas ne all-- bet kuri neigiama yra kas, jei jūs pakeisite savo nuomonę, kai naudojant programą, kurią norite išsaugoti daugiau duomenų nei jūs iš pradžių numatyta. 

Tokiu būdu galbūt tirpalas yra, tada, rašyti savo programas tokiu būdu kad jie naudoja daugiau atminties nei jie iš tikrųjų reikia. Tokiu būdu jūs nesiruošia paleisti į šią problemą, Bet jūs yra išlaidavimas. Ir kuo daugiau atminties jūsų programa naudoja, kaip aptarėme vakar, mažiau atmintis, kuri prieinama kitoms programoms, tuo greičiau kompiuteris gali sulėtinti žemyn, nes virtualios atminties. Ir taip idealus sprendimas gali būti, ką? 

Pagal-paskirstant atrodo blogai. Per paskirstantis atrodo blogai. Taigi, kas gali būti geresnis sprendimas? Perskirstyti. Būkite labiau dinamiškas. Neverskite savęs pasirinkti priori pradžioje, ko norite. Ir tikrai ne per paskirstyti, kad nebūtumėte išlaidavimas. 

Ir taip pasiekti šį tikslą, mes reikia mesti šį duomenų struktūrą, taip sakant, toli. Ir taip kas programuotojas paprastai naudoti yra kažkas vadinamas ne masyvas, bet susijęs sąrašas. Kitaip tariant, jis ar ji bus pradėti galvoti apie savo atmintį tiek skiriasi rūšies formos, kad jie galima padaryti tokiu būdu. Jei aš noriu laikyti vieną numerį program-- todėl rugsėjo Aš daviau savo mokiniams viktoriną; Noriu saugoti mokinių pirmąją viktoriną, ir jie gavo 100 nuo it-- I einu paklausti mano kompiuteryje, būdu programą aš parašyta, vienas riekė atmintį. Ir aš ruošiuosi laikyti skaičius 100 jame, ir viskas. 

Tada po kelių savaičių kai aš gausiu antrą testą, ir atėjo laikas įvesti tuo, kad 90%, aš einu paklausti kompiuterį, ei, kompiuteris, galiu turėti kitą atminties riekė? Jis ketina duoti man tai tuščias riekė atmintį. Aš ruošiuosi įdėti į numerį 90, bet mano programa vienaip ar other-- ir mes ne nerimauti sintaksė už this-- man reikia kažkaip grandinės šiuos dalykus kartu. Ir aš grandinės juos kartu su kas atrodo rodykle čia. 

Trečioji viktorina, kad ateina, Aš ruošiuosi pasakyti, ei, kompiuteris, duok man dar vieną atminties riekė. Ir aš ruošiuosi pribaigti Koks jis buvo, kaip 75, ir aš turiu grandinės šio kartu dabar kažkaip. Ketvirta viktorina ateina kartu, o gal tai link semestro pabaigoje. Ir šiuo klausimu mano programa gali būti naudojant atminties visur, visame fiziškai. Ir taip tik prasideda, aš ketina parengti tai pirmyn quiz-- aš pamiršti, kas buvo; aš manau gal 80 ar something-- būdas čia. 

Bet tai gerai, nes su pavaizduotomis piktogramo- Aš ruošiuosi padaryti šią eilutę. Kitaip tariant, iš tikrųjų, jūsų kompiuterio aparatinę įrangą, pirmas balas gali galų gale čia, nes tai į dešinę nuo semestro pradžios. Kitą gali baigtis čia nes šiek tiek laiko praėjo ir programa išlaiko veikia. Kitą rezultatas, kuris buvo 75, gali būti čia. Ir paskutinis rezultatas gali būti 80, kuris yra daugiau nei čia. 

Taigi iš tikrųjų fiziškai, tai gali būti kas kompiuterio atminties atrodo. Bet tai nėra naudinga psichikos paradigma programuotojas. Kodėl jums turėtų rūpintis kur gi jūsų duomenys baigiant? Jūs tiesiog norite išsaugoti duomenis. 

Tai lyg mūsų diskusijų anksčiau piešimo kubą. Kodėl jums rūpi tai, ką kampas yra kubo ir kaip jūs turite kreiptis į ją atkreipti? Jūs tiesiog norite kubą. Panašiai čia jums tiesiog norite klasės knygą. Jūs tiesiog norite galvoti apie tai kaip numerių sąrašo. Who cares, kaip tai įgyvendinamos įrangą? 

Taigi abstrakcija dabar yra ši nuotrauka čia. Tai yra susiję sąrašą, kaip programuotojas būtų jį pavadinti, kiek turite sąrašas, be abejo skaičių. Bet tai susiję su pavaizduotomis piktogramo- būdu šių rodyklėmis, ir visi šie rodyklės are-- po dangtis, jei esate smalsus, Primename, kad mūsų fizinės kompiuterinės įrangos turi adresai nulis, vienas, du, tris, keturis. Visos šios strėlės yra tarsi žemėlapyje ar kryptimis, kur, jei 90 is-- dabar Aš turiu skaičiuoti. 

Nulis, vienas, du, trys, keturi, penki, šeši, septyni. Panašu, kad 90 yra atminties adresas skaičius septyni. Visos šios strėlės yra kaip mažas laužo popieriaus kad manimi duoti nurodymų programa, kuri sako sekti šį žemėlapį patekti į vietą septynių. Ir ten jūs rasite studento antroji viktorina rezultatas. Tuo tarpu, 75-- jei aš ir toliau tai, tai yra septynių, aštuonių, devynių, 10, 11, 12, 13, 14, 15. 

Tai kita rodyklė tiesiog atstovauja žemėlapį į atminties vietą 15. Bet vėl, programuotojas paprastai daro nerūpi šio detalumo lygiu. Ir daugumoje kiekvieną programavimo kalba šiandien, programuotojas bus net nežino, kur į atmintį šie skaičiai iš tikrųjų yra. Viską, ką jis ar ji turi rūpintis yra kad jie yra kaip nors susijusi kartu į duomenų struktūros, kaip tai. 

Tačiau paaiškėja, ne gauti per techninę. Bet tik todėl, kad mes galime galbūt sau leisti turėti šią diskusiją čia tarkime, kad mes naujo šis klausimas čia masyvo. Leiskite pamatyti, jei mes apgailestaujame vyksta čia. Tai yra 100, 90, 75, ir 80. 

Leiskite trumpai padaryti šį reikalavimą. Tai yra matrica, ir dar kartą, Pasisako charakteristika masyvo yra tai, kad visi jūsų duomenys yra Grįžti į atgal atgal į memory-- pažodžiui vienas baitas arba gal keturi baitai, kai nustatoma baitų skaičius toli. Susietoje sąrašo, kuris mes galime padaryti kaip šis, po gaubtu, kuris žino, kur, kad medžiaga yra? Tai net nereikia tekėti kaip šis. Kai kurie duomenys gali būti Atgal į kairę ten. Jums net nereikia žinoti. 

Ir taip su masyvo, turite funkcija žinomas kaip laisvą prieigą. Ir ką laisvosios kreipties būdas yra kad kompiuteris gali pereiti iš karto į bet masyvą vietoje. Kodėl? Kadangi kompiuteris žino kad pirmoji vieta yra nulis, vienas, du, trys. 

Ir todėl, jei norite pereiti nuo šis elementas į kitą elementą, Jūs tiesiogine prasme, į Kompiuterio protas, tiesiog pridėti vieną. Jei norite pereiti į trečiąjį elementą, tiesiog pridėkite one-- kito elemento, tiesiog pridėti. Tačiau, į šią versiją istorijos, tarkime, kompiuteris šiuo metu ieško ne ar bendraujant su numeriu 100. Kaip jūs gaunate į kitą Įvertinimas į klasės knygą? 

Jūs turite imtis septyni žingsnių, kuris yra savavališkas. Norėdami gauti į kitą, jūs turite imtis dar aštuoni laiptai patekti į 15. Kitaip tariant, tai ne pastovus atotrūkis tarp skaičių, ir todėl tereikia kompiuteris daugiau laiko yra taškas. Kompiuteris turi ieškoti per atmintį, siekiant rasti tai, ko jūs ieškote. 

Taigi kadangi masyvo linkęs būti greitas duomenų structure-- nes jūs gali tiesiog tiesiog padaryti paprastą aritmetiką ir gauti ten, kur norite, pridedant vieną, už instance-- susietą sąrašą Jūs paaukoti šią funkciją. Jūs galite ne tik eiti nuo pirmojo prie antro į trečią ketvirtoje. Jūs turite sekti žemėlapį. Jūs turite imtis daugiau veiksmų patekti į šias vertybes, kurios Atrodytų, kad pridedant išlaidas. Taigi, mes mokate kainą, bet tai, kas buvo funkcija, kuri Danas siekė čia? Ką susietą sąrašą matyt leidžia mums daryti, kuris buvo kilmė Tai ypač istorija? 

Tiksliai. Dinaminis dydis į jį. Galime pridėti prie šio sąrašo. Mes netgi gali susitraukti sąrašą, todėl kad mes tik naudojant kiek atminties kaip mes iš tikrųjų nori ir tt mes niekada per paskirstyti. 

Dabar tiesiog tikrai NIT-smulkmeniškas, ten paslėptas išlaidas. Taigi, jūs turėtumėte ne tik leiskite man įtikinti Jums, kad tai yra įtikinamų kompromisas. Yra dar vienas paslėptas kaina čia. Nauda, ​​kad būtų aišku, yra tai, kad mes gauname dinamiškumą. Jei aš noriu dar vieną elementą, galiu tik piešti ir įdėti skaičių ten. Ir tada aš galiu susieti jį su nuotrauka čia kadangi per čia, vėlgi, jei aš dažytos save į kampą, jei kažkas jau naudoja Čia atminties, aš iš laimės. Aš dažytos save į kampą. 

Bet kas paslėpta kaina šiame paveikslėlyje? Tai ne tik suma laiko, kad ji trunka eiti iš čia į čia kuris yra septynių žingsnių, tada Aštuoni žingsniai, kuri yra daugiau nei vienas. Kas kitas paslėptas išlaidas? Ne tik laikas. Papildoma informacija būtina norint pasiekti šią nuotrauką. 

Taip, tai žemėlapis, tas mažai skiautelių popierius, kaip aš nuolat apibūdinant juos kaip. Tai arrows-- tie, kurie nėra nemokama. Computer-- žinote ką kompiuteris turi. Jis turi nulių ir. Jei norite atstovauti rodyklę arba map arba skaičius, jums reikia šiek tiek atminties. Taigi kita kaina, kurią mokėti už susietą sąrašą bendras kompiuterių mokslas išteklių, taip pat vietos. 

Ir iš tiesų taip, taip, paprastai, tarp kompromisų projektuojant programinės įrangos inžinerijos sistemos laikas ir space-- yra du savo sudedamųjų dalių, du Jūsų brangiausių sudedamųjų dalių. Tai kainuoja man daugiau laiko nes turiu sekti šį žemėlapį, bet tai taip pat kainuoja man daugiau vietos nes turiu išlaikyti šį žemėlapį aplink. Taigi viltis, kaip mes rūšies aptarti per vakar ir šiandien, yra tai, kad nauda bus didesnės už išlaidas. 

Tačiau nėra akivaizdus sprendimas čia. Gal tai better-- la greitas ir purvinas, kaip Kareemas pasiūlė earlier-- mesti atmintį problema. Tiesiog pirkti daugiau atminties, manau mažiau sunku apie sprendžiant šią problemą, ir išspręsti jį paprasčiausias būdas. Ir iš tiesų anksčiau, kai mes kalbėjome apie kompromisus, tai buvo ne erdvė kompiuteris ir laikas. Tai buvo kūrėjas laikas, kuris yra dar vienas šaltinis. 

Taigi dar kartą, tai tik balansavimo aktas bando nuspręsti, kuris iš šių dalykų tu nori praleisti? Kuris yra mažiausiai brangus? Kuris duoda geresnius rezultatus? Taip? 

Iš tikrųjų. Šiuo atveju, jei jūs atstovaujanti numerius maps-- jie vadinami įvairiomis kalbomis "patarimų" ar "adresai", - tai dvigubas erdvę. Tai nebūtinai turi būti taip blogai, kaip dvigubai, jei dabar mes tiesiog laikyti numerius. Tarkime, kad mes buvome saugoti pacientų įrašus hospital-- taip Pierson vardus, telefono numerius, socialinio draudimo numeriai, gydytojas istorija. Šis langelis gali būti daug, žymiai didesnis, tokiu atveju mažytis mažas žymeklis, kad adresas Kitas element-- tai ne big deal. Tai toks kutais kaina nesvarbu. Tačiau šiuo atveju, taip, tai padvigubinti. Geras klausimas. 

Pakalbėkime apie kartą, tiek konkrečiau. Koks veikimo laikas ieškoti šį sąrašą? Tarkime, aš norėjau ieškoti per visus mokinių klasėse, ir ten n klases Šioje duomenų struktūros. Čia taip pat galime skolintis iš anksčiau žodyną. Tai yra linijinis duomenų struktūra. 

Didelės O n yra tai, kas reikalinga gauti su šio duomenų struktūros pabaigoje, whereas-- ir mes nematėme tai before-- masyvas suteikia jums kas vadinama konstanta laikas, o tai reiškia, vienas žingsnis ar du žingsniai arba 10 steps-- nesvarbu. Tai fiksuotas skaičius. Tai neturi nieko bendra su masyvo dydis. Ir dėl šios priežasties, vėl, yra laisvosios kreipties. Kompiuteris gali tiesiog iš karto peršokti į kitą vietą, nes jie visi vienodi Atstumas nuo visko. Nėra mąstymas dalyvauja. Gerai. Taigi, jei aš galiu, leiskite man pabandyti dažų dvi paskutines nuotraukas. Labai dažnas vienas žinomas kaip maišos lentelė. Taigi, norint motyvuoti šią diskusiją, tegul mane galvoti apie tai, kaip tai padaryti. 

Taigi, kaip apie tai? Tarkime, kad problema norime išspręsti dabar įgyvendina į dictionary-- taip visa krūva angliškų žodžių ar kas. Ir tikslas yra, kad būtų galima atsakyti į klausimai formos tai žodis? Taigi jūs norite įgyvendinti rašybos tikrintuvas, tiesiog kaip fizinio žodyną kad jūs galite ieškoti dalykų, iki. Tarkime, aš būčiau tai padaryti su masyvo. Galėčiau tai padaryti. 

Ir manau, kad žodžiai yra obuolių ir bananas ir melionas. Ir aš negaliu galvoti apie vaisių kad pradėti su D, todėl mes tiesiog teks tris vaisius. Taigi tai yra masyvas, ir mes saugoti visi šie žodžiai šiame žodyne kaip masyvą. Klausimas, tuomet, tai, kaip kitur gal galėtumėte saugoti šią informaciją? 

Na, aš rūšies sukčiavimas čia, nes kiekviena iš šių raidėmis žodžio yra tikrai individualus baitų. Taigi, jei aš tikrai norėjau būti NIT-smulkmeniškas, aš tikrai turėtų būti dalijant tai aukštyn į daug mažesnius gabaliukus atminties, ir mes galime padaryti būtent tai. Tačiau mes ketiname paleisti į ta pati problema kaip ir anksčiau. Ką daryti, jei, kaip Merriam Webster ar Oksforde daro kas šarvuotuose jie įtraukti žodžius į dictionary-- mes ne visada nori piešti save į kampą su masyvo? 

Taigi vietoj to, gal protingesni požiūris yra įdėti Apple savo mazge ar dėžėje, kaip sakytume, bananų ir tada čia mes turime Kantalupa. Ir mes styginių šie dalykai kartu. Todėl tai yra matrica, ir tai yra susiję sąrašas. Jei negalite gana pamatyti, jis tiesiog sako: "Masyvas", ir tai sako "sąrašą". 

Taigi, mes turime tą patį Tikslios klausimai kaip ir anksčiau, kurią mes dabar turime dinamiškumas mūsų susietą sąrašą. Bet mes turime gana lėtai žodyną. Tarkime, aš noriu ieškoti žodžio. Tai gali užtrukti man didelis O n žingsniai, nes žodis galėtų būti visą kelią pabaigoje sąrašas, kaip ir Kantalupa. Ir paaiškėja, kad programavimo, rūšiuoti šventojo Gralio duomenų struktūros, yra kažkas kuri suteikia jums nuolat laikas kaip masyvo bet vis dar suteikia jums dinamiškumą. 

Taigi galime turėti geriausią iš abiejų pasaulių? Ir iš tiesų, yra kažkas vadinamas maišos lentelė kuri leidžia jums padaryti tiksliai kad, nors apytiksliai. Maišos lentelė yra mėgėjas duomenų struktūra, kad mes galite galvoti kaip kombinacija yra array-- ir aš ruošiuosi jį atkreipti kaip this-- ir tiesinis sąrašas kad aš parengia kaip tai čia. 

Ir taip šis dalykas darbai yra taip. Jei tai now-- maišos table-- yra mano trečią duomenų struktūra, ir aš noriu laikyti žodžiai, aš ne nori tiesiog laikyti visas žodžiai atgal atgal atgal į nugarą. Noriu sverto kai gabalas informacijos apie žodžius, kurie leis man gauti jį ten, kur jis greičiau. 

Taigi, atsižvelgiant į žodžių obuolių ir bananas ir melionas, Aš sąmoningai pasirinkau tuos žodžius. Kodėl? Ką tarsi iš esmės skiriasi apie tris? Kas yra akivaizdu? Jie pradeda su skirtingomis raidėmis. 

Taigi jūs žinote, ką? Užuot įdėti visus mano žodžius tas pats kibiras, taip sakant, kaip vienas didelis sąrašą, kodėl gi ne Aš bent pabandyti optimizaciją ir kad mano sąrašai 1/26 tol. Įtikinamų optimizavimas gali būti kodėl gi ne I-- įdėjus žodį į šią duomenų struktūros, į kompiuterio atmintį, kodėl ne aš įdėti visas "A" žodžius čia visi "b" žodžiai čia, ir visi "C" žodžiai čia? Taigi tai baigiasi išleisti obuolį čia bananų čia Kantalupa čia ir taip toliau. 

Ir jei turiu papildomai Žodis like-- kas kita? "Apple", bananai, kriaušės. Kiekvienas galvoja apie vaisių , kuris prasideda su a, b, arba c? Blueberry-- tobula. Kad ketina baigti čia. Ir taip mes, atrodo, turime nežymiai geresnis sprendimas, nes dabar jei noriu ieškoti obuolių, aš first-- aš ne tik neria į mano duomenų struktūros. Nemanau, pasinerti į savo kompiuterį atmintyje. Aš pirmą kartą pažvelgti į pirmąją raidę. 

Ir tai yra tai, ką kompiuterio mokslininkas pasakytų. Jūs maišos į savo duomenų struktūrą. Jūs imtis savo indėlį, kuris šiuo atveju yra kaip obuolys žodis. Jūs ją analizuoti, žiūri pirmoji raidė šiuo atveju, taip maišos ją. Maišos yra bendras terminas, kuriuo išgėrėte kažką kaip pirkimo ir jūs gaminti tam tikrą produkciją. Ir tuo, kad produkcija atveju yra vieta norite ieškoti, pirmasis vieta, antra vieta, trečia. Taigi indėlis yra obuolių, produkcija yra pirmas. Įvesties yra bananų, The produkcija turėtų būti antras. Įvesties yra Kantalupa, išėjimo turėtų būti trečdaliu. Įvesties yra mėlynių, The produkcija turėtų vėl būti antra. Ir tai, kas padeda jums imtis nuorodos per savo atmintį siekiant gauti žodžių arba duomenų efektyviau. 

Dabar tai mažina mūsų laikas potencialiai iki kiek vienas iš 26, nes jei manyti, kad jūs turėti daug "A" žodžių, kaip "z" žodžiai kaip "Q" žodžiai, kuriuos yra tikrai ne realistic-- jūs ketinate turėti nerijos visoje kai kurios alphabet-- raidės bet tai būtų pavienis požiūris, kad neleidžia jums daug greičiau patekti į žodžių. Ir iš tikrųjų, sudėtinga programa, pasaulio akiniai, Naudotis world-- Facebooks jie naudoja maišos lentelę dėl skirtingų tikslais daug. Bet jie nebūtų tokie naivūs kaip tiesiog pažvelgti į pirmąją raidę obuolių ar bananų arba kriaušių arba Kantalupa, nes, kaip jūs galite pamatyti, tai sąrašus dar gali gauti ilgai. 

Ir taip tai vis dar galėtų būti tarsi iš linear-- taip tarsi lėtas, kaip su dideliu O n kad aptarėme anksčiau. Taigi, kas yra tikrai geras maišos lentelė bus do-- jis turės daug didesnę masyvo. Ir ji naudosis daug daugiau sudėtingas maišos funkcija, taip, kad ji ne tik pažvelgti į "a." Gal tai žiūri "A-P-P-L-e", ir kažkaip paverčia tuos penkis laiškus į vietą, kur "Apple" turėtų būti saugomi. Mes tiesiog naiviai naudojant raide "A" vienas, nes tai malonu ir paprasta. 

Bet maišos lentelė, į pabaiga, jūs galite galvoti iš kaip kartu masyvo, iš kurių kiekvienas turi susietą sąrašą, idealiai turėtų būti kiek įmanoma trumpesnis. Ir tai nėra akivaizdu, tirpalas. Iš tikrųjų, daug tiksliai reguliuojant kad eina po kapotu kada įgyvendinant šias rūšių sudėtingos duomenų struktūros kas yra teisė ilgis masyvo? Kas yra teisė maišos funkcija? Kaip jums laikyti dalykų atmintyje? 

Bet suprasti, kaip greitai Tai tarsi diskusijos pratęstus, arba taip toli, kad tai tipo iš virš galvos šiuo metu, kuris yra gerai. Bet mes pradėjome, prisiminti, su tikrai kažkas žemo lygio ir elektroninės. Ir todėl tai vėl tai tema abstrakcija, kur kadaise pradėdami vartoti už suteikta, gerai, aš turiu it-- ten fizinės atminties, Gerai, supratau, kas fizinė vieta turi adresą, Gerai, aš jį galiu atstovauti tie adresus arrows-- galite labai greitai pradeda turėti sudėtingesnių pokalbiai kad pabaigoje, atrodo, leidžia mums spręsti problemas, kaip ieškoti ir efektyviau rūšiavimas. Ir būkite tikri, too-- nes manau, kad tai yra giliausias mes nuėjo į kai Šių CS pranešimus proper-- dažnai naudoja padaryta per dieną ir per pusę į tai atkreipti ką gali paprastai padaryti per aštuonių savaičių kursas semestrą. 

Turite klausimų apie tai? Ar ne? Gerai. Na, kodėl ne mes pristabdyti ten, pradėti pietūs keletą minučių per anksti, atnaujinti tik apie valandą? Ir aš svyruos šiek tiek su klausimais. Tada aš ruošiuosi eiti užtrukti keletą skambučių, jei tai Gerai. Aš įjungti šiek tiek muzikos tuo tarpu, bet pietūs turėtų būti už kampo.