DAVID MALAN: Selvä. Olemme palanneet. Joten tässä segmentissä ohjelmointia mitä Ajattelin olimme tehdä, on sekoitus asioita. Yksi, tehdä hieman jotain käytännön, vaikkakin käyttäen leikkisämpää ohjelmointi environment-- joka on havainnollinen ja täsmälleen erilaisia ​​ideoita olemme puhuneet, mutta hieman enemmän muodollisesti. Kaksi, tarkastelemme joitakin teknisemmät tapoja että ohjelmoija todella ratkaista ongelmat kuten etsimällä ongelma että me katsoimme ennen ja Myös enemmän pohjimmiltaan mielenkiintoinen ongelma lajittelu. 

Me vain olettaa alusta asti että puhelinluettelo on lajiteltu, mutta se ei yksin oikeastaan ​​eräänlainen kova ongelma monilla eri tavoilla ratkaista se. Joten käytämme näitä luokan ongelmia edustaja asioita, voitaisiin ratkaista yleisesti. Ja sitten jutellaan noin melko yksityiskohtaisesti, mitä kutsutaan data structures-- harrastaja tavoilla, kuten liittyvät luettelot ja hash taulukoita ja puut ohjelmoija olisi todella käyttää ja yleensä käyttää taululle maalata kuva siitä, mitä hän visioi toteuttamiseksi jotkut pala ohjelmisto. 

Joten tehdä käytännön osaan ensin. Joten vain saada kädet likainen kanssa ympäristö nimeltään scratch.mit.edu. Tämä on työkalu, jota käytämme meidän perustutkintoa luokassa. Vaikka se on suunniteltu 12-vuotiaille ja ylöspäin, käytämme sitä ylös osa sitä melkoisesti koska se on mukava, hauska graafinen tapa oppia vähän jotain ohjelmointia. Joten pään että URL, jossa pitäisi nähdä sivun aivan kuten tämä, ja mennä eteenpäin ja valitse Liity Scratch ylhäällä oikealla ja valitse käyttäjänimi ja salasanan ja lopulta saada itse account-- scratch.mit.edu. Ajattelin käyttää tätä mahdollisuus ensin näyttää tämän. Kysymys tuli tauolla mitä koodi todella näyttää. Ja puhuimme tauolla noin C, in particular-- erityisemmin alemman tason vanhempi kielellä. Ja tein nopean Google-haku löytää C-koodia binary search, algoritmi, että me käytettiin hakemaan että puhelinluettelosta aikaisemmin. Tässä nimenomaisessa esimerkissä, tietenkin, ei etsi puhelinluettelosta. Se vain etsii koko joukko numerot tietokoneen muistiin. Mutta jos haluat vain saada visuaalinen tunteen siitä, mitä todellinen ohjelmointi kieli näyttää, se näyttää vähän jotain tällaista. Joten se on noin 20-plus, 30 tai niin riviä koodia, mutta keskustelun me oli ottaa yli break oli miten tämä todella saa morphed nollia ja ykkösiä ja jos et voi vain palata että käsitellä ja menevät nollia ja ykkösiä takaisin koodin. 

Valitettavasti prosessi on niin transformatiivinen että se on paljon helpommin sanottu kuin tehty. Menin eteenpäin ja lopulta kävi että ohjelma, Binary Search, osaksi nollia ja ykkösiä Poiketen ohjelma nimeltä kääntäjä että minä sattuu olemaan täällä juuri Macin. Ja jos tarkastellaan näyttöä täällä, keskittyen erityisesti Näiden keskellä kuusi saraketta vain, näet vain nollia ja ykkösiä. Ja ne ovat nollia ja ykkösiä, jotka säveltää juuri sen etsimistä ohjelmassa. 

Ja niin kukin kimpale viisi bittiä, jokainen tavu nollia ja ykkösiä täällä, muodostavat noin opetus tyypillisesti sisällä tietokoneen. Ja itse asiassa, jos olet kuullut markkinointi iskulause "Intel inside" - että, tietenkin vain tarkoittaa olet Intel CPU tai aivojen tietokoneen sisällä. Ja mitä se tarkoittaa olla CPU on että olet käskykannan, niin sanoakseni. 

Jokainen CPU maailmassa, monet ne tehdään Intel näinä päivinä, ymmärtää rajallinen useita ohjeita. Ja ne ohjeet ovat niin alhaisella tasolla kuten lisätä nämä kaksi lukua yhteen, moninkertaistaa nämä kaksi lukua yhteen, Siirrä tämä pala tiedot tästä tänne muistissa, tallenna tämä tietoa täältä tänne muistiin, ja niin forth-- niin hyvin, hyvin matalan tason, lähes elektroniset tiedot. Mutta näitä matemaattisia toiminnot yhdistettynä mitä me aiemmin todettiin, tietojen esittämisessä kuten nollia ja ykkösiä, voi voit rakentaa kaiken että tietokone voi tehdä tänään, onko se sanallisesti, graafinen, musiikki, tai muuten. 

Joten tämä on erittäin helppo saada hävisi rikkaruohot nopeasti. Ja siellä on paljon syntaktisia haasteet jolloin jos teet yksinkertaisin, tyhmin kirjoitusvirheitä yksikään ohjelman toimii mitään. Ja niin sen sijaan käytetään kieli kuten C tänä aamuna, Luulin, että se olisi hauskempaa itse tehdä jotain enemmän visuaalinen, joka kun taas suunniteltu lapsille on todella täydellinen ilmentymä todellinen ohjelmointi language-- sattuu käytä kuvia tekstin sijaan edustamaan näitä ajatuksia. 

Joten kun olet todellakin on tili scratch.mit.edu, klikkaa Luo-painiketta ylhäällä vasemmalla puolella sivustolla. Ja sinun pitäisi nähdä ympäristön, kuten yksi Olen tulleet tietokoneen näytöllä tässä. Ja me kuluttaa vain vähän vähän aikaa pelaa täällä. Katsotaan jos emme voi kaikki ratkaista joitakin ongelmat yhdessä seuraavasti. 

Joten mitä näet tässä environment-- ja oikeastaan ​​vain antaa minulle tauko. Onko kukaan ei ole täällä? Ei täällä? OK. Joten haluaisin huomauttaa muutamia piirteitä tässä ympäristössä. 

Joten vasemmassa yläkulmassa näytön, me on Scratch lavalla, niin sanotusti. Scratch ei ole vain nimi Tämän ohjelmointikieli; se on myös nimi kissa, joka näet oletuksena siellä oranssi. Hän on lavalla, niin aivan kuten kuvailin kilpikonna aikaisemmin ollessa suorakulmainen valkoinen lauta ympäristössä. Tämä kissan maailma rajoittuu kokonaan kyseiseen suorakulmio ylös siellä. 

Samaan aikaan, oikealla laidalta täällä, se on vain skriptejä alue, pöydältä jos haluatte. Tämä on, jos aiomme kirjoittaa ohjelmiemme vain hetken. Ja rakennuspalikoita, että me käyttää kirjoittamaan tämän program-- palapeli kappaletta, jos will-- ovat ne täällä keskellä, ja ne luokitellaan by toiminnallisuutta. Niinpä esimerkiksi, aion mennä eteenpäin ja osoittaa ainakin yksi näistä. Aion mennä eteenpäin ja valitse Control luokka ylös. 

Nämä ovat siis luokkien ylös. Aion napsauttamalla Control luokka. Pikemminkin, aion klikkaa Tapahtumat tyylinen aivan ensimmäinen ylös. Ja jos haluat seurata pitkin edes kun teemme niin, olet aivan tervetullut. Aion napsauttamalla ja vetämällä tätä Ensimmäinen, "kun vihreä lippu napsautetaan." Ja sitten aion pudottaa se vain karkeasti yläreunassa minun tyhjä laatat. 

Ja mikä mukavaa noin Scratch on, että tämä palapelin pala, kun lukittu muihin palapeli kappaletta, tulee tekemään kirjaimellisesti mitä nämä palapelin palaset sanoa tehdä. Niinpä esimerkiksi, Scratch on oikeassa Nyt keskellä hänen maailmassa. Aion mennä eteenpäin ja valitse nyt, sanokaamme, Motion luokka, Jos haluat tehdä same-- Motion luokka. Ja nyt huomaan on koko nippu palapelin palaset täällä että taas sellainen mitä he sanovat. Ja aion mennä eteenpäin ja vetää ja pudota liikkua lohko oikea täällä. 

Ja huomaa, että heti kun saat lähellä pohjaan "Vihreä lippu napsautetaan "-painiketta, ilmoitus miten valkoinen viiva, kuin se olisi melkein magneettinen, se haluaa mennä sinne. Vain antaa mennä, ja se napsahtaa yhteen ja muodot täsmää. Ja nyt voit ehkä melkein arvata minne olemme menossa tämän. 

Jos tarkastellaan Scratch vaiheessa tänne ja katsoa päälle, näet punaista valoa, joka on stop-merkin, ja vihreä lippu. Ja aion mennä eteenpäin ja katsella minun screen-- vain hetken, jos voisi. Aion napsauttaa Vihreä lippu juuri nyt, ja hän muutti mikä näyttää olevan 10 askelta tai 10 pikseliä, 10 pistettä, ruudulla. 

Ja niin ei se jännittävää, mutta haluan ehdottaa edes opettaa tätä, vain käyttäen omaa oman intuition-- let me ehdotamme, että te selvittää, miten tehdä Scratch kävellä oikeassa lavalta. Onko hänet tieltä oikealle puolelle näytön aina oikealle. Annan teille hetken tai niin painimaan sen kanssa. Haluat ehkä katsoa at muihin lohkoja. Selvä. Joten vain kertaus, kun meillä on vihreä lippu napsautetaan täällä ja siirrä 10 askelta on Ainoa ohje, joka kerta kun napsauttamalla vihreää lippua, mitä tapahtuu? No, joka on käynnissä oma ohjelma. Joten en voisi tehdä tätä ehkä 10 kertaa käsin, mutta tämä tuntuu hieman bittinen hackish, niin sanotusti, jolloin En ole oikeastaan ongelman ratkaisemiseksi. Olen vain yrittää uudestaan ​​ja uudestaan ​​ja uudestaan ​​ja uudestaan kunnes tavallaan vahingossa saavuttaa direktiivin että minä esitetyt saavuttaa aiemmin. 

Mutta me tiedämme meidän pseudokoodi aiemmin, että on olemassa tätä käsitettä ohjelmointiin silmukka, tehdä jotain uudestaan ​​ja uudestaan. Ja niin minä näin, että kasan teitä saavutti mitä palapelin pala? Toista kunnes. Jotta voisimme tehdä jotakin kuten toista kunnes. Ja mitä sinä toista kunnes tarkalleen? 

OK. Ja anna minun mennä yksi, joka on yksinkertaisempia vain hetken. Anna minun mennä eteenpäin ja tehdä tätä. Huomaa, että, kuten ehkä olla löydetty hallinnassa, on tämä toista lohko, joka ei näytä se, että suuri. Ei ole paljon tilaa näiden kahden keltaiset viivat. Mutta jotkut teistä saattaa olla huomannut, jos vetää ja pudottaa, huomaa, miten se kasvaa täyttää muodon. 

Ja voit jopa ahtaa enemmän. Se täytyy vain pitää kasvaa, jos vedät ja viet sen yli. Ja en tiedä mitä paras täällä, joten anna minulle ainakin toista viisi kertaa, ja Esimerkiksi ja palaa lavalle ja klikkaa vihreää lippua. Ja nyt huomaa se ei ole aivan siellä. 

Nyt jotkut teistä ehdotti, kuten Victoria vain ei, toista 10 kertaa. Ja että yleensä tekee saada hänet koko matkan, mutta eikö siellä olla vakaampi tapa kuin mielivaltaisesti kuvauksen, kuinka moni liikkuu tehdä? Mikä voisi olla parempi lohko kuin toista 10 kertaa olla? 

Niin, miksi ei tehdä jotain ikuisesti? Nyt haluan siirtää tätä palapelin pala sisällä siellä ja päästä eroon tästä. Huomaa nyt missä Scratch alkaa, hän menee reunaan. Ja onneksi MIT, joka tekee Scratch, vain varmistaa, että hän ei koskaan häviää kokonaan. Voit aina napata häntäänsä. 

Ja juuri intuitiivisesti, miksi hän pitää liikkua? Mitä täällä tapahtuu? Hän näyttää pysähtyneen, mutta sitten jos olen poimia ja vedä Hän pitää haluavat mennä sinne. Miksi niin? Todella, tietokone on kirjaimellisesti aikoo tehdä mitä kerrot sitä tekemään. Joten jos kertonut sitä aikaisemmin tekemään Seuraavat asia ikuisesti, siirtää 10 askelmaa, se tulee pitää käynnissä ja menemällä kunnes osuin punainen stop sign ja lopettaa ohjelman kokonaan. 

Joten vaikka et ole Tätä miten voisi I tehdä Scratch liikkua nopeammin ruudun poikki? Useampia vaiheita, eikö? Joten sen sijaan tehdä 10 kerrallaan, miksi emme mennä eteenpäin ja muuttaa sitä to-- mitä sinä propose-- 50? Joten nyt aion napsauttamalla vihreää lippu, ja todellakin, hän menee todella nopeasti. 

Ja tämä tietenkin on vain ilmentymä animaatio. Mikä on animaatio? Se on vain näyttämällä ihmiselle läjän pysäytyskuvia todella, todella, todella nopeasti. Ja niin jos me vain kertoa hänet muuttamaan useampia vaiheita, me vain, että niiden vaikutuksesta olla Muutos missä hän on ruudulla kaikki nopeammin aikayksikköä kohti. 

Nyt seuraava haaste, että olen ehdottanut oli saada hänet kimpoavat reunan. Ja tietämättä mitä palapeli kappaletta exist-- koska se on hieno jos et päästä vaiheessa challenge-- mitä haluat tehdä intuitiivisesti? Miten meillä hänet toipua ja eteenpäin, vasemman ja oikean? 

Joo. Joten tarvitsemme jonkinlaista kunnossa, ja me näyttävät conditionals, niin puhua, alle Control luokkaan. Mikä näistä lohkojen me luultavasti halua? Niin, ehkä "jos, niin." Niin huomaa, että joukossa keltaisiin laatikoihin Meillä on täällä, on tämä "jos" tai tämä "jos, muuten" block että tulee antaa meille mahdollisuuden tehdä päätös tehdä tähän tai tehdä niin. Ja voit jopa pesä niistä tehdä useita asioita. Tai jos olet ei mennyt tässä vielä, mennä eteenpäin, että Sensing luokka and-- katsotaanpa jos se on täällä. 

Joten mikä lohko voisi olla hyödyllistä tässä havaita, jos hän lavalta? Niin, huomata, että jotkut näistä lohkoista voidaan parametroida, niin sanotusti. Ne voidaan lajitella räätälöityjä, ei toisin kuin HTML eilen attribuutteja, jos nämä määritteet millaisia muokata käyttäytymistä tunnisteen. Samoin täällä, voin napata tämän koskettavan lohko ja muutos ja kysyä, sinä koskettaa hiirtä osoitin kuten osoitin tai olet koskettaa reunaan? 

Joten anna minun mennä ja tehdä tämän. Aion loitontaa hetkeksi. Saanen tarttua tähän palapelin pala täällä, tämä palapelin pala tätä, ja aion irrallaan niitä vain hetken. Aion siirtää tätä, vaihtaa tämän koskettava reunaan, ja aion liikettä tähän. Joten tässä on joitakin ainesosia. Mielestäni olen saanut kaiken haluan. 

Onko joku ehdottaa, miten I voi yhdistää nämä ehkä ylhäältä alas jotta ongelman ratkaisemiseksi ottaa Scratch siirtyä oikealle vasemmalta oikealle vasemmalta oikealle vasemmalle, jokaisen aikaa vain terhakka pois seinästä? Mitä haluat tehdä? Joka lohko pitäisi yhteyden "Kun vihreä lippu napsautetaan ensin"? 

OK, joten aloitamme kanssa "ikuisesti." Mikä menee sisälle seuraavaksi? Joku muu. OK, liikkuvat vaiheet. Selvä. Mitä sitten? Joten sitten, jos. Ja huomaa, vaikka se näyttää alumiinifoliota yhdessä tiiviisti, se vain kasvaa täyttämään. Se vain hypätä missä haluan sen. 

Ja mitä laitan välillä if ja sitten? Luultavasti "jos koskettaa reuna." Ja ilmoitus, jälleen kerran, se on liian iso sitä, mutta se kasvaa täyttämään. Ja käännä 15 astetta? Kuinka monta astetta? Niin, 180 pyörittää me kaikki päin. Katsotaanpa, jos sain tätä oikeutta. Saanen loitontaa. 

Saanen vedä Scratch ylös. Hän on hieman vääristynyt nyt, mutta se käy hyvin. Miten voin palauttaa hänet helposti? Aion huijata hieman. Joten olen lisäämällä toisen lohko, vain olla selvä. Haluan hänen kohtaan 90 astetta oikealle oletuksena, joten olen juuri menossa kertoa hänelle tehdä niin ohjelmallisesti. Ja tässä mennään. Olemme ilmeisesti tehneet sen. Se on vähän outo, koska Hän kävelee ylösalaisin. Kutsun että vika. Se on virhe. Bugi on virhe ohjelmassa, joka on looginen virhe, että minä, ihmisen, tehty. Miksi hän menee ylösalaisin? Oliko MIT tyriä tai tein? 

Niin, tarkoitan, se ei ole MIT: n vika. He antoivat minulle palapelin pala joka sanoo puolestaan ​​jotkut useita astetta. Ja Victoria ehdotuksen, Olen kääntämällä 180 astetta, mikä on oikea intuitio. Mutta kääntämällä 180 astetta kirjaimellisesti tarkoittaa kääntämällä 180 astetta, ja se ei oikeastaan mitä haluan, ilmeisesti. Koska ainakin hän on Tämän kaksiulotteinen maailmassa, niin käännekohta todella tapahtuu kääntää hänet ylösalaisin. 

Luultavasti halua käyttää mitä lohko sen sijaan, sen perusteella, mitä näet tässä? Kuinka me voimme korjata tämän? Niin, jotta voisimme viitata vastakkaiseen suuntaan. Ja itse asiassa jopa siinä ei tule tarpeeksi, koska voimme vain kovaa koodia toteamaan vasemmalle tai oikealle. 

Tiedät mitä voisimme tehdä? Se näyttää että meillä on mukavuutta lohko täällä. Jos minä zoomata, katso jotain haluamme täällä? Joten se näyttää MIT on abstraktio rakennettu täällä. Tämä lohko näyttää olevan vastaavia johon muut lohkot, monikko? 

Tämä yhden korttelin näyttää olevan vastaavia Tämän koko trio lohkojen että meillä on täällä. Joten se kääntyy pois voin yksinkertaistaa minun Ohjelma hankkiutumalla eroon kaikista, jotka ja vain laittaa tämän tänne. Ja nyt hän on vielä vähän buginen, ja se sopii nyt. Jätämme sen olla. Mutta ohjelma on vielä yksinkertaisempi, ja tämäkin olisi edustava of tavoite programming-- on mieluiten tehdä koodin yksinkertainen, mahdollisimman kompakti, kun vielä niin luettavissa kuin mahdollista. Et halua tehdä niin ytimekäs että on vaikea ymmärtää. 

Mutta huomaa olen korvattu kolme lohkoa yhdellä, ja se on todennäköisesti hyvä asia. Olen otetun pois käsite tarkastaa, onko olet reunalla vain yhden korttelin. Nyt voimme olla hauskaa tätä, itse asiassa. Tämä ei lisää niinkään henkinen arvo mutta leikkisä arvo. Aion mennä eteenpäin ja napata tämä ääni täällä. Joten anna minun mennä eteenpäin, ja haluan lopettaa ohjelman hetkeksi. Aion kirjata seuraavat, päästämällä mikrofoni. 

Nyt sitä mennään. Auts. Yritetään tätä uudelleen. Nyt sitä mennään. OK, Nauhoitin väärin. Nyt sitä mennään. Auts. Auts. Selvä. Nyt minun täytyy päästä eroon siitä. Selvä. 

Joten nyt olen tallennus vain "Auts." Joten nyt aion mennä eteenpäin ja kutsuvat tätä "Auts." Aion palata minun skriptejä, ja nyt ilmoitus on tämä lohko sitä kutsutaan toistaa äänen "miau" tai toistaa äänen "Auts." Aion vetää tämän, ja jos minun pitäisi laittaa tämä koominen vaikutus? Niin, nyt se on eräänlainen buginen, koska nyt tämä block-- huomaa kuinka tämä "jos reunalla, bounce "on sellainen itsenäinen. Joten minun täytyy korjata. Anna minun mennä eteenpäin ja tehdä tätä. Saanen päästä eroon tästä ja palata meidän alkuperäinen, enemmän tarkoituksellinen toiminnallisuus. Eli "jos koskettaa reuna, sitten" Haluan kääntyä, kun Victoria ehdotettu, 180 astetta. Ja tehdä Haluan pelata ääni "Auts" siellä? 

Joo, huomaa se ulkona että keltainen lohko. Joten tämäkin olisi bug, mutta olen huomannut sen. Joten aion vetää sen ylös tänne, ja ilmoitus nyt se sisällä "jos". Joten "jos" on tämmöinen samankaltaisten varsimaisten blot joka on vain menee do mitä sisällä siitä. Joten nyt jos minä loitontaa at riski annoying-- 

COMPUTER: Auts, auts, auts. 

DAVID MALAN: Ja vain loputtomiin. Nyt vain nopeuttaa asioita täällä, anna minun mennä eteenpäin ja avata, Katsotaanpa say-- anna minun mennä joitakin oman tavaraa luokassa. Ja anna minun avata, sanokaamme, tämä yksi tehty yksi opetuksemme stipendiaatit pari vuotta sitten. Joten jotkut teistä saattavat muistaa tämä peli menneiden, ja se on todella merkittävä. Vaikka olemme tehneet Yksinkertaisin ohjelmien juuri nyt, Tarkastellaan mitä tämä todella näyttää. Saanen osuma pelata. 

Joten tässä pelissä meillä on sammakko, ja nuolinäppäimillä keys-- hän ottaa isompi vaiheet kuin I remember-- Minulla on valvoa tämän sammakko. Ja tavoitteena on saada koko kiireinen road törmäämättä autoja. Ja lähdetään see-- jos menen tänne, minä on odotettava lokin vierittää. Tämä tuntuu vika. Tämä on eräänlainen bug. Selvä. Olen täällä, siellä, ja sitten pidät menossa kunnes saat kaikki sammakot on lumpeenlehdet. Nyt tämä voisi näyttää kaikki monimutkaisempi, mutta yritetään rikkoa tämän alas henkisesti ja suullisesti osaksi rakennuspalikkapeli. Joten on luultavasti palapeli pala, emme ole nähneet vielä mutta joka on vastaaminen näppäilyjä, asioita osuin näppäimistöllä. 

Joten on luultavasti jonkinlainen lohko, joka sanoo, jos avain on yhtä suuri kuin ylös, sitten tehdä jotain Scratch-- ehkä siirtää sen 10 askelta tällä tavalla. Jos alas -näppäintä painetaan, siirrä 10 askelta Näin tai vasen-näppäintä, siirrä 10 askelta Tällä tavoin 10 vaiheet, jotka. Olen selvästi kääntyi kissan osaksi sammakko. Niin, että vain jos puku, kuten Scratch puhelut it-- me vain tuotu kuva sammakko. 

Mutta mitä muuta tapahtuu? Mitä muita riviä koodia, mitä muut palapelin palat teki Blake, opetuksemme mies, käyttää tätä ohjelmaa, ilmeisesti? Mikä tekee kaiken move-- mitä ohjelmointi rakentaa? 

Motion, sure-- joten liikkua lohko, varmasti. Ja mikä tuo siirto lohko sisällä, todennäköisin? Joo, jonkinlainen silmukan, ehkä ikuisesti lohko, ehkä toista block-- toista, kunnes lohko. Ja juuri se tekee tukkien ja lilja tyynyt ja kaikkea muuta liikkua edestakaisin. Se on vain tapahtuu loputtomasti. 

Miksi jotkut autot liikkuu nopeammin kuin toiset? Mikä on erilainen noista ohjelmista? Joo, todennäköisesti joitakin niistä ovat ryhtyneet useampia vaiheita kerralla ja joitakin niistä vähemmän vaiheita kerralla. Ja visuaalinen vaikutus on nopea verrattuna hidasta. 

Mitä luulet tapahtuneen? Kun sain sammakko koko matkan kadun ja joen päälle lumpeenlehti, jotain huomionarvoista tapahtui. Mitä tapahtui, kun tein sen? Se pysähtyi. Tämä sammakko pysähtyi, ja Sain toisen sammakko. Joten mitä konstruktio on oltava käytetyt siellä, mitä ominaisuus? 

Niin, siellä on jonkinlainen "Jos" kunnossa ylös sielläkin. Ja se osoittautuu out-- emme nähneet this-- mutta on muiden lohkojen siellä, että voi sanoa, jos olet koskematta toinen asia ruudulla, jos olet koskettaa lumpeenlehti, "sitten." Ja sitten silloin me tehdä toinen sammakko näkyviin. Joten vaikka tämä peli on varmasti hyvin päivätty, vaikka ensi silmäyksellä siellä on niin paljon meneillään on-- ja Blake ei piiska tähän asti kahdessa minuutissa, se luultavasti vei hänet usean tuntia luoda tämän pelin perustuu hänen muistiin tai videoita menneen n version. Mutta kaikki nämä pienet asiat käynnissä ruudulla erillään pohjimmiltaan nämä hyvin yksinkertainen constructs-- liikkeitä tai lausunnot kuten olemme keskustelleet, silmukat ja olosuhteet, ja se siitä. On muutamia muita harrastaja ominaisuuksia. Jotkut niistä ovat puhtaasti esteettiset tai akustinen, kuten äänet olen juuri pelataan. Mutta suurin osa, sinun ovat tällä kielellä, Scratch, kaikki perustavaa laatua rakennuspalikoita, jotka olet on C, Java, JavaScript, PHP, Ruby, Python, ja useita muita kieliä. Kysyttävää Scratch? Selvä. Joten emme sukeltaa syvemmälle Scratch, vaikka olet tervetullut tänä viikonloppuna, varsinkin jos sinulla on lapsia tai veljen ja veljen ja tällainen, esitellä niitä Scratch. Se on oikeastaan ​​ihanan leikkisä ympäristön, koska sen kirjoittajat sanovat, erittäin korkeat katot. Vaikka aloitimme hyvin matalan tason yksityiskohdat, voit todella tehdä melko vähän sen kanssa, ja tämä on ehkä osoitus juuri näin. 

Mutta katsotaan nyt siirtymistä lisää hienostunut ongelmia, jos haluatte, tunnetaan nimellä "etsiminen" ja "Lajittelu" yleisemmin. Meillä oli tämä puhelinluettelo earlier-- tässä toinen vain discussion-- että pystyimme etsimään tehokkaammin koska merkittävän olettamus. Ja vain olla selvä, mitä Oletuksena oli, I tehdä etsiessään kautta puhelinluettelo? Mike Smith oli puhelinluettelosta, vaikka en pystyisi käsittelemään skenaariossa ilman häntä siellä jos vain katkaista kesken. Kirja on aakkosellinen. Ja se on hyvin antelias olettamus, koska se tarkoittaa someone-- Olen sellainen leikkaus nurkkaan, kuten olen nopeammin, koska joku muuten teki paljon työtä minulle. 

Mutta mitä jos puhelin kirja oli lajittelematta? Ehkä Verizon sai laiska, vain heitti kaikkien nimet ja numerot siellä Ehkä siinä järjestyksessä, jossa ne rekisteröitynyt puhelinpalvelua. Ja kuinka paljon aikaa se vie minut löytää joku Mike Smith? 1000 sivu puhelin book-- montako sivuilla minun täytyy käydä läpi? 

Ne kaikki. Olet tavallaan poissa onnea. Kirjaimellisesti täytyy katsoa jokaisen sivu, jos puhelinluettelo on aivan satunnaisesti lajitellaan. Saatat saada onnekas ja löytää Mike on aivan ensimmäisellä sivulla, koska hän oli ensimmäinen asiakas tilata puhelinpalvelusta. Mutta hän olisi ollut viimeinen, too. 

Joten satunnaisessa järjestyksessä ei ole hyvä. Joten kai meidän täytyy lajitella puhelinluettelo tai yleensä lajitella data että meille on annettu. Miten voimme tehdä? 

No, haluan vain yrittää yksinkertainen esimerkki tästä. Anna minun mennä eteenpäin ja nakata Muutama numerot taululle. Oletetaan numerot olemme ovat sanokaamme, neljä, kaksi, yksi, ja kolme. Ja Ben, lajitella nämä numerot meille. 

Okei hyvä. Miten teit tuon? Selvä. Joten aloittaa pienin arvo ja korkein, ja se on todella hyvä intuitio. Ja ymmärtää, että me ihmiset ovat oikeastaan ​​aika Hyvä ratkaisemaan ongelmia näin ainakin kun data on suhteellisen pieni. Heti kun alkaa olla satoja numeroita, tuhansia numeroita, miljoonia numeroita, Ben luultavasti voinut tehdä sitä aivan niin nopeasti, olettaen, että oli aukkoja numerot. Melko helppo laskea miljoona muuten vain aikaa vievää. 

Joten algoritmi se kuulostaa kuten Ben käytetty juuri nyt oli etsiä pienin määrä. Joten vaikka me ihmiset voivat ottaa on paljon tietoa visuaalisesti, tietokone on todella hieman suppeampi. Tietokone voi vain katso yksi tavu kerrallaan tai ehkä neljä tavua klo time-- näinä päivinä ehkä 8 tavua klo time-- mutta hyvin pieni määrä tavujen tiettynä ajankohtana. 

Joten koska meillä on todellakin neljä erillistä arvoa here-- ja voit ajatella Ben olevan blinders jos hän olisi tietokoneen tällaisia että hän ei voi nähdä mitään muuta kuin yhden numeron yhdellä time-- niin me yleensä olettaa, kuten Englanti, me luetaan oikealta vasemmalle. Joten ensimmäinen numero Ben luultavasti näytti at oli neljä ja sitten nopeasti ymmärtäneet, että on aika iso number-- anna minun pitää näköinen. 

On kaksi. Odota hetki. Kaksi on pienempi kuin neljä. Aion muistaa. Kaksi on nyt pienin. Nyt one-- se on vielä parempi. Se on vielä pienempi. Aion unohtaa kaksi ja vain muistaa yksi nyt. 

Ja hän voisi lopettaa näköinen? No, hän voisi perustuva Tämän tiedon mutta parasta haku loput luettelosta. Sillä mitä jos nolla olivat listassa? Mitä jos kielteisen olivat listassa? Hän vain tietää, että hänen vastauksensa on oikein, jos hän on tyhjentävästi tarkastetaan koko listan. Joten katsomme loput tästä. Three-- joka oli ajanhukkaa. Sai epäonninen, mutta olin silti oikein tehdä niin. Ja niin nyt hän oletettavasti valitaan pienin määrä ja vain laittaa sen alussa luettelon, koska minä teen täällä. Nyt mitä teit seuraavaksi, vaikka et ajattele sitä melkein tässä suhteessa? Toista prosessi, joten jonkinlainen silmukan. Siellä on tuttu idea. Joten tässä on neljä. Se on tällä hetkellä pienin. Se on ehdokas. Ei enää. Nyt olen nähnyt kaksi. Se on seuraavaksi pienin elementti. Three-- se ei ole pienempi, joten Nyt Ben voi nyppiä pois kaksi. 

Ja nyt toista prosessi, ja tietenkin kolmesta saa vedetty ulos seuraavaksi. Toista prosessi. Neljä saa vedetty ulos. Ja nyt olemme poissa numerot, joten lista on lajiteltava. 

Ja todellakin, tämä on muodollinen algoritmi. Tietokone tiedemies olisi kutsuvat tätä "valinta lajitella," Ajatuksena on lajitella luetella iteratively-- uudelleen ja uudestaan ​​ja uudestaan ​​valitsemalla pienin määrä. Ja mikä on mukavaa siitä on se on vain niin hiton intuitiivinen. Se on niin yksinkertaista. Ja voit toistaa saman toiminta uudelleen ja uudelleen. Se on yksinkertaista. 

Tässä tapauksessa se oli nopea, mutta kuinka kauan se todella kestää? Tehdään se näyttää ja tuntuu hieman tylsiä. Joten yksi, kaksi, kolme, neljä, viisi kuudesta, seitsemän, kahdeksan, yhdeksän, 10, 11, 12, 13, 14, 15, 16-- mielivaltaisen määrän. Halusin lisää tästä aika kuin vain neljä. Joten jos minulla koko kasan numeroita now-- se ei edes väliä mitä he are-- katsotaanpa miettiä, mitä tämä algoritmi todella on. 

Oletetaan on numeroita siellä. Jälleen, ei ole väliä mitä ne ovat, mutta ne ovat satunnaisia. Haen Ben algoritmi. Minun täytyy valita pienin määrä. Mitä teen? Ja aion fyysisesti tee se tällä kertaa toimimaan sitä. Katse, etsii, etsivät, etsivät, etsivät. Vain aika saan loppuun listan voi Ymmärrän pienin Määrä oli kaksi tällä kertaa. Yksi ei luettelossa. Joten laitoin alas kaksi. 

Mitä teen seuraavaksi? Näköinen, etsivät, etsivät, etsivät. Nyt olen löytänyt numero seitsemän, koska siellä on aukkoja näissä numbers-- mutta vain mielivaltainen. Selvä. Nyt voin laittaa alas seitsemän. Katsoo looking, etsivät. 

Nyt olen olettaen Tietenkin, että Ben ei on ylimääräistä RAM, extra muistin, koska tietenkin, Etsin sama määrä. Varmasti olen voinut muistaa kaikki nämä luvut, ja se on aivan totta. Mutta jos Ben muistaa kaikki numeroista hän on nähnyt, hän ei ole oikeastaan ​​tehnyt olennaisesta kehityksestä koska hän on jo kyky hakea läpi numerot taululle. Muistaa kaikki numeroita ei auta, koska hän voi silti kuin tietokone vain katsoa, ​​olemme sanoneet, yksi numero kerrallaan. Joten ei ole sellainen huijata siellä, että voit hyödyntää. 

Joten todellisuudessa, koska olen jatkaa etsimistä luettelosta Olen kirjaimellisesti täytyy vain pitää käynnissä edestakaisin sen läpi, nyppiminen pois seuraavaksi pienin numero. Ja koska voit sellaista päätellä minun typerä liikkeitä, Tämä vain saa hyvin ikävä hyvin nopeasti, ja minä näyttävät olevan menossa takaisin ja edestakaisin, edestakaisin melko vähän. Nyt on oikeudenmukainen, minun ei tarvitse mennä aivan niin, no, sanotaan see-- olla oikeudenmukainen, Minun ei tarvitse kävellä melko niin monta vaihetta joka kerta. Koska, tietenkin, kuten minä Valitse numerot luettelosta, jäljellä lista lyhenee. 

Ja niin Ajatellaanpa kuinka monta askelta Olen oikeastaan traipsing läpi joka kerta. Aivan ensimmäinen tilanne meillä oli 16 numeroa, ja niin maximally-- sanotaan vain Tätä varten discussion-- Jouduin katsoa läpi 16 numerot löytää pienin. Mutta kun minä temmattu pienin määrä, miten pitkä oli jäljellä lista, tietenkin? Vain 15. Joten kuinka monta numeroa teki Ben tai Minulla käydä läpi toisella kerralla? 15, vain mennä ja löytää pienin. Mutta nyt, tietenkin, lista on, Myös pienempi kuin se oli ennen. Joten kuinka monta askelta tein on otettava seuraavan kerran? 14 ja sitten 13 ja sitten 12, plus piste, piste, piste, kunnes olen jäänyt vain yksi. Joten nyt tietojenkäsittelytieteessä olisi kysyä, hyvin, mitä se kaikki samanarvoisia? Se todellakin on yhtä konkreettisia numero että voisimme varmasti do aritmeettisesti, mutta haluamme puhua tehokkuudesta algoritmien hieman formulaically, riippumatta siitä, miten kauan luettelo on. 

Ja niin tiedät mitä? Tämä on 16, mutta kuten aiemmin sanoin, Haluan vain soittaa koko ongelman n, jossa n on jokin numero. Ehkä se on 16, ehkä se kolme, ehkä se miljoona. Minä en tiedä. En välitä. Mitä todella haluan on kaava, joka voin käyttää vertaamaan tätä algoritmia toisia algoritmeja että joku saattaa vaatia ovat parempia tai huonompia. 

Joten se kääntyy pois, ja minä vain tietävät tämän alkaen alakoulussa, että tämä todella toimii samaan asia kuin n yli n plus yksi yli kaksi. Ja tämä tapahtuu yhtä, ja Tietenkin n potenssiin plus n yli kaksi. Joten jos halusin kaava kuinka monta askelta olivat mukana tarkastellaan kaikkia Näiden numeroiden uudestaan ​​ja uudestaan ja uudestaan ​​ja uudestaan, sanoisin se n potenssiin plus n yli kaksi. Mutta tiedätkö mitä? Tämä vain näyttää sotkuinen. Olen vain todella haluavat yleinen käsitys asioista. Ja ehkä muistatte lukion että on käsite huipputasolla aikavälillä. Mitkä näistä ehdoista, n potenssiin, n, tai puoli, on eniten vaikutusta ajan myötä? Isompi n saa, joka Näiden asioiden eniten? 

Toisin sanoen, jos kytken miljoonasta, n potenssiin tulee olemaan todennäköisesti hallitseva tekijä, koska miljoona kertaa itsessään on paljon suurempi kuin plus yksi ylimääräinen miljoona. Joten tiedätkö mitä? Tämä on niin hiton iso numero, jos neliön useita. Tämä ei ole niin väliä. Olemme juuri menossa ristikkokappaleenkanssa pois ja unohtaa sen. Ja niin tietojenkäsittelytieteessä sanoisi että tehokkuus tämän algoritmin on suuruusluokkaa n squared-- Siis todella approksimaatio. Se on tavallaan karkeasti n neliö. Ajan, isompi ja isompi n saa, tämä on hyvä arvio siitä, mitä tehokkuus tai tehottomuus Tämän algoritmin todella on. Ja minä johtaa se, tietenkin, alkaen todella tekee matematiikka. Mutta nyt olen vain heiluttaa käteni, koska olen juuri haluavat yleinen käsitys tämän algoritmin. 

Joten käyttäen samaa logiikkaa, sillä välin, Tarkastellaan toista algoritmia me jo tutustunut at-- lineaarista hakua. Kun hain puhelimen book-- ei lajittelu, etsimistä puhelimitse book-- me sanoivat, että se oli 1000 vaiheita, tai 500 vaiheet. Mutta nyt yleistää että. Jos on n sivuja puhelinluettelosta, mitä käyntiaika tai tehokkuutta lineaarinen haku? Se on suuruusluokkaa kuinka monta askelta löytää Mike Smith käyttäen lineaarista haku, Ensimmäinen algoritmi, tai jopa toinen? 

Pahimmassa tapauksessa Mike on lopussa kirjan. Joten jos puhelinluettelo on 1000 sivua, sanoimme viime kerralla, pahimmassa tapauksessa, se saattaa kestää suunnilleen kuinka monta sivua löytää Mike? Like 1000. Se on yläraja. Se on pahin mahdollinen tilanne. Mutta jälleen kerran, me luopumassa numeroista kuten 1000 nyt. Se on vain n. 

Mikä siis looginen johtopäätös? Löytäminen Mike puhelimessa kirja, joka on n sivut voi kestää, aivan pahimmassa tapauksessa, kuinka monta askelta määräyksestä n? Ja todellakin tietokone tiedemies sanoisi että ajoaika, tai suorituskykyä tai tehokkuutta tai tehottomuus, algoritmin kuten lineaarinen haku on suuruusluokkaa n. Ja voimme soveltaa samoja logiikka rajan jotain kuten tein toiseen algoritmi meillä oli puhelinluettelosta, jossa menimme kaksi sivua kerrallaan. 

Joten 1000 sivu puhelinluettelo saattaisi vie meidät 500 sivun kierrosta, plus yksi jos taittaa hieman. Joten jos puhelinluettelo on n sivuja, mutta teemme kaksi sivua kerrallaan, se suunnilleen mitä? N yli kaksi, niin että on kuin n yli kaksi. Mutta tein vaatia hetki sitten, että n yli two-- se on eräänlainen sama kuin juuri n. Se on vain vakio tekijä, tietotekniikan tutkijoita sanoisi. Katsotaan vain keskittyä muuttujat, really-- suurin muuttujat yhtälössä. 

Joten lineaarista hakua, onko tehty yksi sivu kerrallaan tai kaksi sivua kerrallaan, on eräänlainen pohjimmiltaan sama. Se on edelleen suuruusluokkaa n. Mutta minä väitti minun kuva aikaisemmin että kolmas algoritmi ei ollut lineaarinen. Se ei suoraviivaisesti. Se oli, että kaareva viiva, ja matemaattisessa muodossa oli mitä? Loki n- niin log pohja kaksi n. Ja meidän ei tarvitse mennä liian paljon yksityiskohtia logaritmit tänään, mutta useimmat tietotekniikan tutkijoita ei olisi edes kertoa mikä pohja on. Koska se kaikki on vain vakio tekijät, niin sanotusti, vain vähäisiä numeerinen eroja. Ja niin tämä olisi hyvin yleinen tietä erityisen muodollisia tietokone tutkijat hallituksen tai ohjelmoijat valkoinen lauta oikeastaan ​​väittäen joka algoritmi he käyttäisivät tai mitä tehokkuus niiden algoritmi on. 

Ja tämä ei ole välttämättä jotain keskustelette kovin yksityiskohtaisesti, mutta hyvä ohjelmoija on joku joka on vankka, muodollinen tausta. Hän pystyy puhumaan teitä tässä sellainen tapa ja todella tehdä laadulliset argumentit miksi yksi algoritmin tai yksi pala ohjelmisto on parempi jollakin tavalla toiseen. Koska te voisi varmasti vain ajaa yhden henkilön ohjelma ja laskea, kuinka monta sekuntia se vie lajitella joitakin numeroita, ja voit käyttää joitakin toisen henkilön ohjelma ja laskea, kuinka monta sekuntia kuluu. Mutta tämä on enemmän yleisesti, että voit analysoida algoritmeja, jos haluatte, juuri paperi- tai vain suullisesti. Ilman edes juoksevaa sitä ilman edes yrittää näyte tuloa, voit vain syystä sen läpi. Ja niin on palkata kehittäjä tai jos ottaa häntä tavallaan väittävät teille miksi niiden algoritmi, salaiset kastike etsimiseen miljardeja web-sivuja Yhtiö on parempi, nämä ovat erilaisia ​​argumentteja he Ihanteellista olisi voitava tehdä. Tai ainakin nämä ovat erilaisia ​​asioita jotka tulevat esille keskustelussa, osoitteessa ainakin hyvin muodollinen keskustelu. Selvä. Joten Ben ehdotettu jotain nimeltään valinta lajitella. Mutta aion ehdottaa, että on olemassa muita tapoja tehdä tämä, too. Mitä En todellakaan pidä Benistä algoritmi on, että hän piti kävely, tai ottaa minut kävelemään, edestakaisin ja edestakaisin ja edestakaisin. Mitä jos sen sijaan tekisin jotain nämä numerot tähän ja minä vain käsitellä kutakin numero puolestaan ​​kuin olen antanut sille? 

Toisin sanoen, tässä listallani numeroita. Neljä, yksi, kolme, kaksi. Ja aion tehdä seuraavaa. Aion lisätä numeroita jos ne kuuluvat melko kuin valitsemalla ne yksi kerrallaan. Toisin sanoen, tässä on numero neljä. 

Tässä on alkuperäinen lista. Ja aion säilyttää pohjimmiltaan uusi lista täällä. Joten tämä on vanha lista. Tämä on uusi lista. Näen numero neljä ensimmäistä. Oma uusi lista on aluksi tyhjä, joten se on triviaalisti tapauksessa että neljä on nyt valikoituja lista. Olen vain ottaen määrä olen antanut, ja olen laskemisesta sitä minun uusi lista. 

Onko tämä uusi luettelo lajitellaan? Joo. Se tyhmä, koska siellä on vain yksi elementti, mutta se on ehdottomasti lajitellaan. Ei mitään pois paikaltaan. Se on enemmän mielenkiintoista, tämä algoritmi, kun siirrytään seuraavaan vaiheeseen. 

Nyt minulla on yksi. Joten tietenkin kuuluu tällä alkuun tai loppuun tämän uuden luettelon? Alku. Joten minun täytyy tehdä töitä nyt. Olen ottanut joitakin vapauksia minun merkki vain hieman piirtämällä asioita jossa olen halua niitä, mutta se ei oikeastaan tarkka tietokoneessa. Tietokone, kuten tiedämme, on RAM tai Random Access Memory, ja se on yksi tavu ja toinen tavu ja toinen tavu. Ja jos sinulla on gigatavu RAM, olet miljardi tavua, mutta ne ovat fyysisesti yhdessä paikassa. Et voi vain siirtää tavaraa ympäri piirtämällä taululle missä vain haluat. Joten jos uusi lista on neljällä paikkakunnalla muistiin, valitettavasti neljä on jo väärässä paikassa. 

Joten lisätä ykkönen En voi vain vetää sitä täällä. Tämä muistipaikka ei ole olemassa. Se olisi huijausta, ja olen ollut huijaaminen kuvallisesti muutaman minuutin tässä. Siis todella, jos haluan esittää yhden täällä, Minun täytyy tilapäisesti kopioida neljä ja sitten laittaa yksi siellä. 

Se on hyvä, pitää paikkansa, se on teknisesti mahdollista, mutta ymmärtää, että on ylimääräistä työtä. En vain laittaa numeron paikallaan. I oli ensin siirtää numero, sitten laittaa se paikalleen, joten olen sellainen kaksinkertaisti työmäärän. Niin pitää tämä mielessä. 

Mutta olen nyt tehnyt tätä elementtiä. Nyt haluan napata numero kolme. Jos tietenkin se kuuluu? Välissä. En voi huijata enää ja vain laittaa sen sinne, koska, jälleen, tämä muisti on fyysinen sijainti. Joten minun täytyy kopioida neljä ja laita kolme tänne. Ei iso juttu. Se on vain yksi ylimääräinen vaihe again-- tuntuu erittäin edullinen. 

Mutta nyt siirtyä kaksi. Kaksi, tietenkin, kuuluu tässä. Nyt alkaa nähdä, miten työ voi kasaantuvat. Nyt mitä minun täytyy tehdä? Joo, minun täytyy siirtää neljä, Sitten täytyy kopioida kolme, ja nyt voin lisätä kaksi. Ja saalis tähän algoritmi, kiinnostavaa kyllä, on että kai meillä on enemmän äärimmäisiä Tapauksessa, jossa se on sanokaamme kahdeksan, seitsemän, kuusi, viisi, neljä, kolme, kaksi, yksi. Tämä on monissa yhteyksissä, pahimmassa tapauksessa, koska hiton asia on kirjaimellisesti taaksepäin. 

Se ei oikeastaan vaikuttaa Ben algoritmi, koska Ben valikoimassa sort hän aikoo pitää menee edestakaisin läpi listan. Ja koska hän oli aina etsimässä läpi koko jäljellä lista, sillä ei ole väliä jossa elementit ovat. Mutta tässä tapauksessa minun upotetun approach-- Kokeillaan tätä. 

Joten yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän, kahdeksan. Yksi kaksi kolme neljä, viisi, kuusi, seitsemän, kahdeksan. Aion ottaa kahdeksan, ja mistä voin laittaa sen? No, alussa listallani, koska tämä uusi luettelo lajitellaan. Ja kuljen sen. 

Mihin laitan seitsemän? Hitsi. Se tarvitsee mennä sinne, niin Minun täytyy tehdä joitakin kopiointia. Ja nyt seitsemän menee täällä. Nyt olen siirtyä kuuteen. Nyt on entistä enemmän työtä. 

Kahdeksan on mennä tänne. Seitsemän on mennä tänne. Nyt kuusi voi mennä täällä. Nyt nappaan viisi. Nyt kahdeksan on mentävä täällä, seitsemän on mennä tänne, kuusi on mennä tänne, ja nyt viisi ja toista. Ja olen melko paljon siirtämällä sitä jatkuvasti. 

Joten lopussa, tämä algorithm-- me will kutsuvat sitä paikoilleen sort-- todellisuudessa on paljon työtä, too. Se on vain erilainen tällaista työtä kuin Ben. Ben työ oli minulle menossa edestakaisin koko ajan, valitaan seuraavaksi pienin elementti uudestaan ​​ja uudestaan. Joten se oli tämän hyvin visuaalinen tällaista työtä. 

Tämä toinen algoritmi, joka on edelleen correct-- se saa työn done-- vain muuttaa työmäärä. Näyttää siltä, ​​aluksi olet säästö, koska olet vain käsittelevät kunkin elementin edessä ilman kävelyä kaikki läpi listan kuten Ben oli. Mutta ongelma on, erityisesti näissä hullu silloin kun se kaikki taaksepäin, olet juuri sellainen lykätään kovaa työtä kunnes olet korjata virheitä. 

Ja joten jos voit kuvitella tämän kahdeksan ja seitsemän ja kuusi ja viisi ja myöhemmin neljä ja kolme ja kaksi liikkuvat läpi listan, Olemme juuri muuttaneet tyyppistä työtä teemme. Sen sijasta, että se on alkaa minun iteraation Teen vain sitä on lopussa jokaisen iteraation. Joten käy ilmi, että tämä algoritmi, Myös yleensä kutsutaan lisäyslajittelun, on myös suuruusluokkaa n neliö. Se on oikeastaan ​​ole parempi, mitään parempaa ollenkaan. 

Kuitenkin on olemassa kolmas lähestymistapa Haluan kannustaa pohtimaan, joka on tässä. Joten kai listalta, yksinkertaisuuden jälleen, on neljä, yksi, kolme, two-- vain neljä numeroa. Ben oli hyvä intuitio, hyvä ihmisen intuitio ennen, jolla korjasimme koko luetella eventually-- lisäyslajittelun. Olen houkutteli meidät pitkin. Mutta Tarkastellaan Yksinkertaisin tapa korjata tämä lista. 

Tämä luettelo ei ole lajiteltu. Miksi? Englanti, miksi se ei ole oikeastaan ​​lajitella. Mitä se tarkoittaa ei lajitella? 

Opiskelija: Se eivät ole järjestyksessä. 

DAVID MALAN: Ei peräkkäinen. Anna minulle esimerkki. 

OPISKELIJA: Laita ne järjestyksessä. 

DAVID MALAN: OK. Anna minulle tarkempi esimerkki. 

OPISKELIJA: Nouseva järjestys. DAVID MALAN: Ei nousevassa järjestyksessä. Oltava täsmällisempi. En tiedä mitä tarkoitat nouseva. Mikä on vialla? 

OPISKELIJA: Pienin numeroita ei ole ensimmäinen avaruudessa. 

DAVID MALAN: Pienin numero n ei ensimmäiseen tilaan. Tarkemmin. Olen alkanut tarttua. Luotamme, mutta mitä epäkunnossa täällä? 

OPISKELIJA: numerojärjestyksessä. DAVID MALAN: numerojärjestyksessä. Kaikkien sellainen pitäminen se here-- erittäin korkealla tasolla. Vain kirjaimellisesti kertoa minulle, mitä väärä kuin viisi vuotta vanha voimin. 

OPISKELIJA: Plus yksi. 

DAVID MALAN: Mikä tämä on? 

OPISKELIJA: Plus yksi. 

DAVID MALAN: Mitä tarkoitat plus yksi? Anna minulle toinen viiden-vuotias. Mikä hätänä, äiti? Mikä hätänä, isä? Mitä tarkoitat tämä ei lajitella? 

Opiskelija: Se ei ole oikea paikka. 

DAVID MALAN: Mikä ei oikeassa paikassa? 

OPISKELIJAN: Neljä. DAVID MALAN: OK, hyvä. Eli neljä ei ole, jos se olisi. Erityisesti on tämä oikeus? Neljä ja yksi, ensimmäinen kaksi numeroa näen. Onko tämä oikein? Ei, he epäkunnossa, eikö? Itse asiassa, ajatella nyt noin tietokoneen, too. Se voi vain katsoa ehkä yksi, ehkä kaksi asiaa once-- ja oikeastaan ​​vain yksi asia kerrallaan, mutta se voi ainakin katsokaa yksi asia sitten Seuraava asia aivan sen vieressä. 

Niinpä nämä kunnossa? Ei tietenkään. Joten tiedätkö mitä? Miksi emme ota vauva vaiheet ongelman korjaamiseen sen sijaan tehdä näistä fancy algoritmeja kuten Ben, jossa Hän tavallaan vahvistaa sen läpiohjaus luettelossa sen sijaan tehdä mitä tein, jossa Olen juuri sellainen kiinteiden sitä mennään? Toivotaan vain kirjaimellisesti murtamaan käsitteeseen order-- numerojärjestyksessä, kutsua sitä mitä want-- näihin pareittain vertailuissa. 

Neljä ja yksi. Onko tämä oikea järjestys? Joten korjata sen. Yksi ja neljä, ja sitten me vain kopioi. Selvä, hyvä. Korjasin yhdestä neljään. Kolme ja kaksi? Ei. Anna minun sanani vastaavat sormiani. Neljä ja kolme? 

Se ei ole kunnossa, joten aion tehdä yksi, kolme, neljä, kaksi. Okei hyvä. Nyt neljä ja kaksi? Meidän täytyy korjata tämäkin. Joten yksi, kolme, kaksi, neljä. Joten on se lajitellaan? Ei, mutta on se lähempänä lajitellaan? 

On, koska olemme kiinteä tätä virhe, korjasimme tätä virhettä, ja korjasimme tämän virheen. Joten me kiinteä kolme virhettä luultavasti. Silti ei oikeastaan ​​katsoa lajiteltua, mutta on objektiivisesti lähempänä lajitellut koska korjasimme joitakin näistä virheistä. 

Nyt mitä teen seuraavaksi? Olen sellainen lopussa luettelosta. Olen näytti kiinteät kaikki virheet, mutta ei. Koska tässä tapauksessa, joitakin numeroita saattanut kuplina ylös lähemmäksi muihin numerot ovat edelleen epäkunnossa. Joten tehdä sen uudestaan, ja minä tee se paikalleen tällä kertaa. Yksi ja kolme? Se on okei. Kolme ja kaksi? Tietenkään ei, joten tehdään muuttaa. Joten kaksi, kolme. Kolme ja neljä? Ja nyt Haluan vain olla Erityisen pikkutarkka täällä. Onko se lajitellaan? Te ihmiset tietävät se lajitellaan. 

Minun pitäisi yrittää uudelleen. Joten Olivia ehdottaa yritän uudelleen. Miksi? Koska tietokone ei ole ylellisyyttä meidän ihmisten silmissä vain vilkaisi back-- OK, olen valmis. Miten tietokone määrittää että luettelossa on nyt lajitellaan? Mekaanisesti. 

Minun pitäisi mennä läpi kerran, ja vain jos I eivät tee / löydät virheitä voin sitten tehdä kuin tietokone, juu, olemme hyvä mennä. Joten yksi ja kaksi, kaksi ja kolme, kolme ja neljä. Nyt voin lopullisesti sanoa, tämä on lajiteltu, koska en tehnyt mitään muutoksia. Nyt olisi vika ja vain typerää jos en, tietokone, pyysi näitä samoja kysymyksiä uudestaan odottaa erilaisia ​​vastauksia. Ei pitäisi tapahtua. 

Ja niin nyt luettelo on järjestetty. Valitettavasti ajoaika Tämä algoritmi on myös N potenssiin. Miksi? Koska olet n numerot, ja pahimmassa tapauksessa sinun täytyy siirtää n numerot n kertaa, koska sinun täytyy pitää käynnissä takaisin tarkistaa ja mahdollisesti korjata näitä numeroita. Ja voimme tehdä enemmän muodollinen analyysi, too. 

Tämä kaikki on siis sanoa olemme ottaneet kolmea eri lähestymistapaa, yksi niistä välittömästi intuitiivinen suoralta kädeltä Ben minun lisätään ehdotettu lajitella tähän yhteen jossa tällainen unohtaa metsän puilta aluksi. Mutta sitten jos ottaa askel taaksepäin, voila, olemme korjanneet lajittelu käsite. Joten tämä on, uskalla sanoa, alemmalla tasolla ehkä kuin joidenkin muiden algoritmeja, mutta katsotaan katso jos emme voi visualisoida nämä Poiketen tämän. 

Joten tämä on kivoja ohjelmisto, että joku kirjoitti käyttämällä värikkäitä baareja se aikoo tehdä seuraavat meille. Kukin näistä baareja on luku. Taller baarissa, isompi numero, pienempi bar, pienempi numero. Joten mieluiten haluamme mukavaa pyramidi jos se alkaa pieni ja saa iso, ja se merkitsisi, että nämä palkit lajitellaan. Joten aion mennä eteenpäin ja valita, Esimerkiksi Ben algoritmin first-- valinta lajitella. 

Ja huomaa, mitä se tekee. Tapa he ovat valinneet visualisoida tämä algoritmi on että, aivan kuten olin kävelevän listalta, tämä ohjelma on kävely kautta listan numeroita, korostaen vaaleanpunainen kussakin numero että se etsii. Ja mitä tulee tapahtumaan juuri nyt? 

Pienin määrä, joka I tai Ben löytyi yllättäen saa siirtää listan alkuun. Ja varoitusajalla he tekivät häätää määrä, joka oli siellä, ja se on täysin kunnossa. En saanut tuohon taso. Mutta meidän täytyy laittaa että määrä jonnekin, niin me juuri muuttanut sen avoin paikka, joka luotiin. Joten aion nopeuttaa tätä up, koska muuten tulee erittäin ikävä nopeasti. Animaatio speed-- siellä mennään. Joten nyt samaa periaatetta Olin hakemassa, mutta voi alkaa tuntea algoritmin, jos tulee, tai nähdä hieman selvemmin. Ja tämä algoritmi on se vaikutus, valitsemalla seuraavaksi pienin elementti, joten aiot alkaa nähdä sen ylösajo vasemmalla. Ja jokaisen iteraation, kuten minä Ehdotettu, se hieman vähemmän työtä. Sen ei tarvitse mennä koko matkan takaisin vasemmalle listan loppuun, koska se on jo tuntee ne lajitellaan. Joten se tavallaan tuntuu se kiihtyy, vaikka jokainen askel on ottaen saman verran aikaa. On vain vähemmän vaiheita jäljellä. Nyt voit sellaista tuntea algoritmi siivota sen lopussa, ja todellakin nyt se lajitellaan. 

Joten lisäyslajittelun on kaikki tehty. Minun täytyy uudelleen satunnaisiksi array. Ja huomaa voin vain pitää randomizing se, ja saamme approksimaatio samaa lähestymistapaa, lisäyslajittelun. Anna minun hidastaa tänne. Aloitetaan että yli. Stop. 

Jätetään neljä. Siellä mennään. Satunnaista ne array. Ja tässä me jää tänne lisäyslajittelun. Pelata. Huomaa, että se käsittelee jokaisen elementti se kohtaa heti, mutta jos se kuuluu väärässä paikassa ilmoitus kaiken työn, joka on tapahduttava. Meidän täytyy pitää siirtymässä enemmän ja enemmän elementtejä tehdä tilaa että yksi haluamme käyttöön. 

Olemme siis keskittyy vasen listan loppuun vain. Huomaatko emme ole edes tutkinut at-- me eivät ole korostettu vaaleanpunainen mitään oikealle. Olemme juuri tekemisissä ongelmat kuten mennään, mutta Luomme paljon työskentelevät itse edelleen. Ja niin jos me nopeuttaa yhteyden muodostumista nyt mennä loppuun, sillä on erilainen tuntea sen todellakin. Se on vain keskittymällä vasemmalla päähän, mutta tekee hieman enemmän työtä kuin needed-- Tällainen tasoitus asioita yli, Korjausten, mutta käsittelevät lopulta kanssa kukin elementti yksi kerrallaan kunnes saamme tyylillisesti hyvin, me kaikki tiedämme, miten tämä tulee päättymään, niin se on vähän underwhelming ehkä. 

Mutta alalta end-- spoiler-- tulee lajitella. Joten katsokaamme yksi viimeinen. Emme voi hypätä nyt. Olemme melkein perillä. Kaksi mennä, yksi mennä. Ja voila. Erinomainen. 

Joten nyt Tehdäänpä yksi viimeinen, uudelleen randomizing kanssa kuplalajittelu. Ja huomaa täällä, varsinkin jos olen hidas se alas, tämä ei pidä swooping kautta. Mutta huomaa vain tekee pareittain comparisons-- tavallaan paikallisia ratkaisuja. Mutta heti kun saamme loppuun luettelon vaaleanpunainen, mitä täytyy tapahtua uudelleen? Joo, se täytyy aloittaa alusta, koska se vain kiinteä pairwise virheitä. Ja joka olisi saattanut paljastanut vielä toiset. Jos siis nopeuttaa sitä, luultavasti nähdä, että paljon kuten nimikin kertoo, pienempi elements-- tai pikemminkin suuremmat elements-- alkavat kupla ylös, jos haluatte. Ja pienemmät elementit ovat alkaa kupla alas vasemmalle. Ja todellakin, se on eräänlainen visuaalinen vaikutus samoin. Ja niin tämä päätyvät viimeistely hyvin samalla tavalla, too. 

Meillä ei tarvitse asua tämän erityisen yksi. Saanen avata tämän nytkin. On muutamia muita lajittelualgoritmeja maailmassa, joista muutamat ovat kiinni täällä. Ja erityisesti opiskelijoille, jotka eivät ole välttämättä visuaalinen tai matemaattisten, kuten teimme aikaisemmin, voimme myös tehdä tämän audially jos me liittää äänen tähän. Ja vain huvin vuoksi, tässä on muutama eri algoritmeja, ja yksi niistä erityisesti olet huomaamaan kutsutaan "lomituslajittelu." 

Se on itse asiassa olennaisesti parempi algoritmi, niin että lomituslajittelu, yksi ne olet tulleet, ei ole järjestyksessä n potenssiin. Se on suuruusluokkaa n kertaa päiväkirjaa n, joka on itse asiassa pienempi ja siten nopeammin kuin muut kolme. Ja siellä on pari muuta typerä ne, jotka näemme. 

Joten tässä sitä mennään hieman ääntä. Tämä on lisäyslajittelun, niin jälleen se vain käsittelee elementtejä kuin ne tulevat. Tämä on kuplalajittelu, joten se on harkitsee niitä paria kerrallaan. Ja vielä, suurin elementit ovat kuplivaa ylös. 

Seuraavaksi valinta lajitella. Tämä on Ben algoritmi, jossa jälleen hän valitsemalla iteratiivisesti seuraavaksi pienin elementti. Ja taas, nyt voit todella kuulla, että se nopeuttaa mutta vain siltä osin koska se tekee vähemmän ja vähemmän työskennellä jokaisen iteraation. Tämä on nopeampaa yksi, lomituslajittelu, joka lajittelee klustereita numeroiden yhteen ja sitten yhdistämällä ne. Joten look-- vasemmalla puolet on jo järjestetty. 

Nyt se lajittelun oikea puoli, ja Nyt se tulee yhdistää ne yhdeksi. Tämä on jotain nimeltä "Gnome sort." Ja voit sellaista nähdä, että se menee edestakaisin, vahvistamisesta työ vähän täällä ja siellä ennen edetään uutta työtä. Ja siinä se. On toinenkin lajitella, mikä on oikeastaan ​​vain tutkintoa varten, nimeltään "tyhmä lajitella", joka vie tietosi, lajittelee sen satunnaisesti, ja sitten tarkistaa, onko se lajitellaan. Ja jos se ei ole, se uudelleen lajittelee ne satunnaisesti, jos niitä on lajiteltu, ja jos ei toistaa. Ja teoriassa, toden- näköisesti tämä täydentää, mutta sen jälkeen melko vähän aikaa. Se ei ole kaikkein tehokas algoritmien. Joten kysyttävää näistä Erityisesti algoritmeja tai jotain liittyvä sielläkin? 

No, nyt kammata toisistaan ​​mitä kaikki nämä linjat ovat, että olen piirtänyt ja mitä olen olettaen tietokone voi tehdä alla huppu. Väittäisin, että kaikki nämä luvut Pidän drawing-- he tarvitsevat tallennettu jonnekin muistiin. Me päästä eroon tästä kaveri nytkin. 

Joten pala muistia on computer-- joten RAM DIMM on mitä etsimme eilen, dual Inline Memory module-- näyttää tältä. Ja jokainen näistä pieni musta pelimerkkejä on joitakin tavujen lukumäärä, tyypillisesti. Ja sitten kulta nastat ovat kuin johtoja, jotka kytkevät sen tietokoneeseen, ja vihreä piin hallitus on aivan mitä pitää kaiken kaikki yhdessä. Mitä tämä oikeastaan ​​tarkoittaa? Jos olen sellainen piirtää tämä sama kuva, Oletetaan yksinkertaisuuden että tämä DIMM, dual inline muistimoduuli, on yksi gigatavu RAM-muistia, yksi gigatavu muistin, joka on se, kuinka monta tavua yhteensä? Yksi gigatavu on, kuinka monta tavua? Enemmän kuin se. 1124 on kiloa, 1000. Mega on milj. Giga on miljardi. 

Olenko valehtelee? Voimmeko edes lukea etiketti? Tämä on itse asiassa 128 gigatavua, joten se on enemmän. Mutta me teeskennellä tämän on vain yksi gigatavu. Joten se tarkoittaa, että on miljardi tavua muistia käytettävissä minulle tai 8 miljardia bittiä, mutta aiomme puhuttava tavujen nyt, siirtyä eteenpäin. 

Joten mitä se tarkoittaa on tämä on yksi tavu, tämä on toinen tavu, tämä on toinen tavu, ja jos me halusimme se on erityistä meidän täytyisi piirtää miljardi vähän neliöitä. Mutta mitä se tarkoittaa? No, haluan vain zoomata in tässä kuvassa. Jos minulla jotain, joka näyttää näin nyt, se on neljä tavua. 

Ja niin voisin laittaa neljä numerot tähän. Yksi kaksi kolme neljä. Tai voisin laittaa neljä kirjaimia tai symboleja. "Hei!" voisi mennä oikeassa, koska kunkin kirjaimet, keskustelimme aiemmin, voisi edustaa kahdeksan bittiä tai ASCII tai tavu. Eli toisin sanoen, voit laittaa 8000000000 asioita sisällä Tämän yhden tikku muistia. Nyt mitä tarkoittaa laittaa asiat takaisin takaisin takaisin muistiin näin? Tämä on mitä ohjelmoija kutsuisin "array." Tietokoneohjelmaan, et usko perusteena oleviin laitteisto, sinänsä. Sinä vain ajatella itse olevan pääsy miljardi tavua yhteensä, ja voit mitä haluat sen kanssa. Mutta mukavuussyistä tämä on usein hyödyllistä pitää muistin oikea vierekkäin, kuten tämä. Jos siis zoomata this-- koska me todellakaan aio piirtää miljardiin hieman squares-- Oletetaan, että tämä hallitus edustaa että tikku muistin nyt. Ja minä vain vetää peräti minun merkki päätyy antamaan minut tänne. Joten nyt meillä on stick muistia taululle että sai yhden, kaksi, kolme, neljä, viisi, kuusi, yksi, kaksi, kolme, neljä, viisi, kuusi, seven-- joten 42 tavua muisti ruudulla koko. Kiitos. Kyllä, tein aritmeettinen oikeassa. Joten 42 tavua muistia täällä. Mitä tämä oikeastaan ​​tarkoittaa? No, tietokoneohjelmoija itse asiassa yleensä ajatella tämän muistiin osoitteellinen. Toisin sanoen, jokainen näistä paikoista muistissa, laitteisto, on ainutlaatuinen osoite. 

Se ei ole niin monimutkainen kuin One Brattle Square, Cambridge, Mass., 02138. Sen sijaan, se on vain numero. Tämä on tavun numero nolla, tämä on yksi, tämä on kaksi, tämä on kolme, ja tämä on 41. Odota hetki. Vaikka olen sanonut 42 hetki sitten. Olen alkoi laskea nollaan, niin se on todella oikea. Nyt meidän ei tarvitse itse piirtää ruudukkona, ja jos piirtää sen grid Mielestäni asiat todella saada hieman harhaanjohtava. Mikä ohjelmoija olisi, hänen tai hänen omassa mielessään, yleensä ajatella tämän muisti on aivan kuten nauha, kuin pala maalarinteippiä että vain jatkuu ja jatkuu ikuisesti tai kunnes muisti loppuu. Joten yleisempää tapa kiinnittää ja vain ajatella muistia olisi, että tämä on tavu nolla, yksi, kaksi, kolme, ja sitten piste, piste, dot. Ja teillä on 42 tällaista tavua yhteensä, vaikka vaikka fyysisesti se saattaisi olla jotain enemmän kuin tämä. 

Joten jos nyt ajatella oman muistia kuin tämä, kuten nauha, tämä on mitä ohjelmoija uudelleen kutsuisi joukko muisti. Ja kun haluat todella tallentaa jotain tietokoneen muistin, te yleensä tehdä tallentaa asioita back-to-back to back-to-back. Siksi olemme puhuneet numeroita. Ja kun halusin ratkaista ongelmia kuten neljä, yksi, kolme, kaksi, vaikka olin vain piirustus vain numeroita neljä, yksi, kolme, kaksi pöydällä, tietokone olisi todella on tämä setup muistiin. 

Ja mikä olisi vieressä kaksi tietokoneen muistiin? No, ei ole vastausta tähän. Emme oikeastaan ​​tiedä. Ja niin kauan kuin tietokone ei tarvitse sitä, sen ei tarvitse välittää, mitä on seuraavaksi numeroiden se välitä. Ja kun sanoin aiemmin, että tietokone voi vain katsoa yhden osoitteen kerrallaan, tämä on tavallaan miksi. 

Ei toisin kirjaa soitin ja lukupää vain pysty katsomaan tiettyyn ura fyysisessä vanhan koulun ennätys kerrallaan, vastaavasti voi tietokone kiitos sen CPU ja sen Intel käskykanta, keskuudessa jonka opetus luetaan muistista tai tallentaa memory-- tietokone voi vain katsoa on yhdessä paikassa time-- joskus niiden yhdistelmää, mutta oikeastaan ​​vain yhdessä paikassa kerrallaan. Joten kun teimme Näiden eri algoritmeja, En vain kirjallisesti on vacuum-- neljä, yksi, kolme, kaksi. Nuo luvut kuuluvat oikeastaan jossain fyysisen muistin. Joten on pikku transistoreita tai jonkinlainen Elektroniikan alla huppu tallentamiseen näitä arvoja. 

Ja yhteensä, kuinka monta bittiä mukana nyt, vain olla selvä? Joten tämä on neljä tavua, tai Nyt se on 32 bittiä yhteensä. Joten on todella 32 nollia ja ne säveltäminen nämä neljä asiaa. On vieläkin täällä, mutta taas emme välitä siitä. 

Nyt Katsotaanpa pyytää toista kysymys käyttämällä muistia, sillä, että lopussa Päivän on varianssi. Ei ole väliä mitä voisimme tehdä tietokoneen, lopussa päivän laitteisto on edelleen Sama alla huppu. Kuinka voisin tallentaa sanan täällä? No, sana tietokoneella kuten "Hei!" tallennettaisiin juuri tällainen. Ja jos halusi pidemmän sana, voit yksinkertaisesti korvata, että ja sanoa jotain kuten "hei" ja tallentaa, että täällä. 

Ja niin tässäkin tämä contiguousness on itse asiassa etu, koska tietokone voi vain luetaan oikealta vasemmalle. Mutta tässä on kysymys. Yhteydessä tämän sanan, h-e-l-l-o, huutomerkki, miten voisi tietokone tiedä missä sana alkaa ja missä sana loppuu? Yhteydessä numeroita, miten tietokone tiedä kuinka kauan sekvenssi numerot on tai missä se alkaa? No, se kääntyy out-- ja emme mene liikaa tähän tasoon detail-- tietokoneet liikkua tavaraa ympäri muistissa kirjaimellisesti Poiketen näistä osoitteista. Joten tietokoneessa, jos olet kirjoittaa koodia tallentaa asioita kuten sanoja, mitä olet todella tekee on kirjoittaa ilmaisuja muistaa missä tietokoneen muistiin nämä sanat ovat. Joten anna minun tehdä hyvin, hyvin yksinkertainen esimerkki. 

Aion mennä eteenpäin ja avata yksinkertaisen tekstin ohjelma, ja aion luoda tiedoston nimeltä hello.c. Suurin osa tiedoista me aio mennä hyvin yksityiskohtaisesti, mutta aion kirjoittaa ohjelman että samaa kieltä, C. Tämä on paljon enemmän uhkaava, Väitän, kuin Scratch, mutta se on hyvin samanlainen hengessä. Itse asiassa nämä kihara braces-- voit eräänlainen ajatella, mitä tein kuin tämä. 

Tehdään tämä, todella. Kun vihreä lippu napsautetaan, toimi seuraavasti. Haluan tulostaa "hei." Joten tämä on nyt pseudokoodit. Olen sellainen hämärtää linjat. C, tällä kielellä puhun noin, tämä linja tulosta hei todella tulee "printf" kanssa Joissakin suluissa ja puolipisteellä. 

Mutta se on täsmälleen sama ajatus. Ja tämä erittäin käyttäjäystävällinen "Kun vihreä lippu napsautetaan" tulee paljon enemmän mystistä "int main mitätön." Ja tämä ei oikeastaan ​​kartoitus, joten olen juuri menossa sivuuttaa sitä. Mutta aaltosulkumerkkien ovat kuin kaareva palapelin palaset näin. 

Joten voit sellaista arvata. Vaikka et ole koskaan ohjelmoitu aiemmin, Mitä tämä ohjelma todennäköisesti tehdä? Luultavasti tulostaa hei huutomerkillä. 

Joten kokeilla. Aion tallentaa sitä. Ja tämä on, jälleen, hyvin vanhan koulun ympäristössä. En voi klikata, en voi vetää. Minun täytyy kirjoittaa komentoja. Joten haluan ajaa minun ohjelma, niin En voisi tehdä tämän, kuten hello.c. Se tiedosto juoksin. Mutta hetkinen, olen puuttuu askel. Mitä sanomme on välttämätön vaihe kieli kuten C? Olen juuri kirjoittanut lähde koodi, mutta mitä tarvitsen? Joo, Tarvitsen kääntäjä. Joten minun Mac täällä, olen ohjelma nimeltä GCC, GNU C-kääntäjä, jossa voin tehdä this-- puolestaan minun lähdekoodia, me kutsumme sitä, konekielelle. 

Ja näen, että jälleen, seuraavasti, nämä ovat nollia ja ykkösiä minä vain luotu minun lähdekoodia, kaikki nollia ja ykkösiä. Ja jos haluan juosta Minun program-- se tapahtuu kutsua a.out varten historiallinen reasons-- "hei." Voin käyttää sitä uudelleen. Hei hei hei. Ja se näyttää toimivan. 

Mutta se tarkoittaa jossain omassa tietokoneen muistiin ovat sanoja h-e-l-l-o, huutomerkki. Ja se osoittautuu, aivan kuin syrjään, mitä tietokone tyypillisesti niin että se tietää minne asiat alkavat ja end-- sen menossa laittaa erityinen symboli täällä. Ja sopimus on laittaa numero nolla lopussa sanan jotta tiedät missä se tosiasiallisesti päättyy, niin että te eivät pidä tulostamalla enemmän ja enemmän merkkejä kuin todellisuudessa tarkoitus. 

Mutta takeaway täällä, vaikka vaikka tämä on melko mystistä, on se, että se on viime kädessä suhteellisen yksinkertainen. Sait eräänlainen nauha, tyhjä tila, johon voit kirjoittaa kirjaimia. Sinun on vain oltava erityinen tunnusmerkki, kuten mielivaltaisesti numero nolla, laittaa lopussa sanasi niin, että tietokone tietää, oh, minun pitäisi lopettaa tulostuksen jälkeen Näen huutomerkki. Koska seuraava asia siellä on ASCII-arvo on nolla, tai null luonne joku voisi kutsua sitä. Mutta on sellainen ongelma täällä, ja nyt palata numeroihin hetkeksi. Oletetaan, että minä, itse asiassa, on joukko numeroita, ja olettaa, että Ohjelma Kirjoitan on kuten asteen kirja opettajalle ja opettajat luokkahuoneessa. Ja tämä ohjelma antaa hänelle kirjoittamaan oppilaiden tulokset on tietokilpailuja. Ja olettaa, että opiskelija saa 100 heidän ensimmäinen tietokilpailu, ehkä kuten 80 seuraava, sitten 75, sitten 90 neljäntenä tietokilpailu. 

Joten tässä vaiheessa tarinan, array on kooltaan neljä. On ehdottomasti enemmän muistia tietokone, mutta array, niin sanotusti, on koko neljä. Oletetaan nyt, että opettaja haluaa määrittää viidennen tietokilpailu luokkaan. No, yksi niistä asioista hän tai hän joutuu tekemään on nyt tallentaa ylimääräinen arvo tähän. Mutta jos jono opettajan on luotu tähän ohjelmaan on kooltaan, yksi ongelma joukko on se, että et voi vain pitää lisäämällä muistia. Sillä mitä jos toinen osa Ohjelma on sana "hei" oikeassa? 

Toisin sanoen, minun muisti voi olla käytetty mitään ohjelmaa. Jos etukäteen olen kirjoittanut, hei, Haluan syöttää neljä tietokilpailu tulokset, he pääsivät tänne ja tänne. Ja jos yhtäkkiä muuttaa mieltään myöhemmin ja sanoa haluan viidesosa tietokilpailu pisteet, et voi vain laittaa sen mihin tahansa, sillä mitä jos tämä muisti on käytössä jotain else-- jokin muu ohjelma tai jokin muu piirre ohjelmassa että näytät? Joten sinun täytyy ajatella etukäteen miten haluat tallentaa tiedot, koska nyt olet maalannut itse digitaaliseksi nurkkaan. 

Joten opettaja voisi sen sijaan sanoa kirjoitettaessa ohjelma tallentaa hänen laadut, tiedätkö mitä? Aion pyytää, kirjoitettaessa minun ohjelma, että haluan nolla, yksi, kaksi, kolme, neljä, viisi, kuusi, kahdeksan laadut yhteensä. Joten yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän, kahdeksan. Opettaja voi hieman yli kohdentaa muisti kirjoittaessaan hänen ohjelma ja sanoa, tiedätkö mitä? En koskaan antaa enemmän kuin kahdeksan tietokilpailuja lukukauden. Se on vain hullu. En koskaan jakaa sitä. Niin että tällä tavalla hän on joustavuutta tallentaa opiskelijan tulokset, kuten 75, 90, ja ehkä yksi ylimääräinen jossa opiskelija sai lisäoppitunteihin, 105. 

Mutta jos opettaja ei koskaan käyttää näitä kolmea tiloja, siellä intuitiivinen takeaway täällä. Hän on vain tuhlaa tilaa. Eli toisin sanoen, on tämä yhteinen kompromissi ohjelmointi jossa voit joko jakaa juuri niin paljon muistia kuin haluat, ylösalaisin on se, että olet Super efficient-- et tuhlailevaksi at all-- mutta haittapuoli, joka on mitä jos muutat mielesi, kun sillä ohjelmalla, jolla haluat tallentaa enemmän tietoa kuin alun perin tarkoitettu. 

Joten ehkä ratkaisu on, niin, kirjoita ohjelmat siten että ne käyttävät enemmän muistia kuin he todella tarvitsevat. Näin et tule törmätä että ongelma, mutta olet tuhlailevaksi. Ja mitä enemmän muistia ohjelma käyttää, kuten olemme keskustelleet eilen, sitä vähemmän muistin, joka on saatavilla muita ohjelmia, ennemmin tietokone saattaa hidastua alas, koska virtuaalimuistin. Ja niin ihanteellinen ratkaisu voisi olla mitä? 

Under-allokoinnin näyttää huono. Yli-allokoinnin näyttää huono. Joten mikä voisi olla parempi ratkaisu? Uudelleen kohdentamiseen. Olla dynaamisempi. Älä pakota itseäsi valita priori alussa, mitä haluat. Ja eivät varmasti yli kohdentaa, ettette olla epätaloudellista. 

Ja niin tämän tavoitteen saavuttamiseksi, me täytyy heittää tämän tietorakenne, niin sanotusti pois. Ja niin mitä ohjelmoija tyypillisesti käyttää ei jotain kutsutaan ole array mutta linkitetty lista. Toisin sanoen, hän tulee alkaa ajatella niiden muistia olevan sellainen muoto, että ne voi piirtää seuraavalla tavalla. Jos haluan tallentaa yksi numero program-- joten se on syyskuu, Olen antanut oppilaitani tietokilpailu; Haluan tallentaa opiskelijan ensimmäinen tietokilpailu, ja he saivat 100 it-- I Aion kysyä tietokoneeseen, Poiketen ohjelman olen kirjoitettu, yhden palan muistia. Ja aion tallentaa numero 100, ja se on siinä. 

Sitten muutamaa viikkoa myöhemmin kun saan toisen tietokilpailu, ja on aika kirjoittaa että 90%, aion kysyä tietokone, hei, tietokone, voin olla toinen möhkäle muistia? Se tulee antaa minulle tämän tyhjä murikka muistia. Aion laittaa numero 90, mutta minun ohjelma jotenkin tai other-- emmekä välitä syntaksi this-- tarvitsen jotenkin ketjuttaa nämä asiat yhdessä. Ja minä ketjun ne yhdessä mikä näyttää nuoli täällä. 

Kolmas tietokilpailu, joka tulee, Aion sanoa, hei, tietokone, antaa minulle toisen palan muistia. Ja aion laittaa alas mitä se oli, kuten 75, ja minun täytyy ketju tähän yhdessä nyt jotenkin. Neljäs tietokilpailu tulee pitkin, ja ehkä se loppupuolella lukukauden. Ja tässä vaiheessa minun ohjelma ehkä käyttää muistia koko paikka, koko fyysisesti. Ja niin huvin, olen menossa tehdä tämän esiin quiz-- Unohdan mitä se oli; minä ajattelevat ehkä 80 tai something-- tapa tänne. 

Mutta se on hienoa, koska kuvallisesti Aion vetää tätä linjaa. Toisin sanoen, todellisuudessa, tietokoneen laitteiston, ensimmäinen pisteet saattaisi päätyvät tänne, koska se on heti alussa lukukauden. Seuraava saattavat päätyä tähän koska vähän aikaa on kulunut ja ohjelma pitää käynnissä. Seuraava tilanne, joka oli 75, saattaa olla täällä. Ja viimeinen pisteet voisi olla 80, joka on täällä. 

Joten todellisuudessa, fyysisesti, tämä saattaa olla mitä tietokoneen muistiin näyttää. Mutta tämä ei ole mielekäs henkinen paradigman ohjelmoija. Miksi välität missä pahus tietosi päätyy? Haluat vain tallentaa tietoja. 

Tämä on ikään kuin meidän keskustelua aikaisemmin piirustus kuution. Miksi välität mitä kulma on kuution ja miten sinun täytyy kääntyä vetää sitä? Haluat vain kuutio. Samoin täällä, haluavat vain asteen kirja. Haluat vain ajatella tämä luettelo numeroita. Kuka välittää kuinka se toteuttaa laitteistossa? 

Joten ottoon nyt tämä kuva täällä. Tämä on linkitetty lista, kuten ohjelmoija kutsuisi sitä, jos olet lista, tietenkin numeroita. Mutta se liittyy kuvallisesti Poiketen näistä nuolet, ja kaikki nämä nuolet are-- alla huppu, jos olet kiinnostunut, muistuttaa, että meidän fyysisessä laitteistossa on osoitteet nolla, yksi, kaksi, kolme, neljä. Kaikki nämä nuolet ovat on kuin kartta tai ohjeet, joissa jos 90 is-- nyt Sain laskea. 

Nolla, yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän. Näyttää siltä, ​​että 90 on muistipaikan numero seitsemän. Kaikki nämä nuolet ovat on kuin pieni arvottomaksi joka on antaa ajo-ohjeita ohjelma, joka kertoo seurata tätä karttaa päästä sijainti seitsemään. Ja siellä löydät Opiskelijan toinen tietokilpailu pisteet. Samaan aikaan 75-- jos jatkan tätä, Tämä on seitsemän, kahdeksan, yhdeksän, 10, 11, 12, 13, 14, 15. 

Tämä toinen nuoli juuri edustaa kartan muistipaikka 15. Mutta jälleen kerran, ohjelmoija yleensä tekee välitä tämän tason yksityiskohtia. Ja melkein joka ohjelmointi kieli tänään, ohjelmoija ei edes tiedä missä muistissa nämä luvut todellisuudessa ovat. Kaikki hänellä on välitä on että ne ovat jotenkin liittyvät toisiinsa tietorakenteeseen näin. 

Mutta näyttää siltä ei saada liian tekninen. Mutta juuri siksi me voimme kenties varaa olla tämän keskustelun täällä, Oletetaan, että palaamme tämä kysymys array. Katsotaan me pahoillani menossa täällä. Tämä on 100, 90, 75, ja 80. 

Saanen lyhyesti tehdä tätä väitettä. Tämä on joukko, ja uudelleen, keskeisiä ominaisuus array on, että kaikki tiedot on takaisin takaisin takaisin memory-- kirjaimellisesti yksi tavu tai ehkä neljä tavua, jotkut kiinteä määrä tavuja pois. Vuonna linkitetty lista, jonka voisimme tehdä näin, alla huppu, joka tietää missä että tavaraa on? Se ei edes tarvitse virrata kuin tämä. Osa tiedoista voi olla takaisin vasemmalle ylös. Et edes tiedä. 

Ja niin jossa joukko, olet ominaisuutta kutsutaan random access. Ja mitä random access välineet on että tietokone voi hypätä heti minne tahansa jono. Miksi? Koska tietokone tietää että ensimmäinen paikka on nolla, yksi, kaksi ja kolme. 

Ja joten jos haluat mennä Tämän elementin seuraavaan elementtiin, kirjaimellisesti, että Tietokoneen mieli, lisää vain yksi. Jos haluat mennä kolmanteen elementtiin, vain lisätä one-- seuraavaan elementtiin, vain lisätä yhden. Kuitenkin tässä versiossa tarina, olettaa tietokone on parhaillaan at tai käsittelevät numero 100. Miten päästä seuraavalle arvosana asteen kirja? 

Sinun täytyy ottaa seitsemän vaiheita, joka on mielivaltainen. Päästä seuraavaan, sinun täytyy ottaa toisen kahdeksan askeleen päästä 15. Toisin sanoen, se ei ole jatkuva kuilu numerot, ja niin se vain vie tietokone enemmän aikaa on piste. Tietokone on etsiä kautta muistille löytää mitä etsit. 

Joten kun taas matriisin taipumus olla nopea data structure-- koska olet voi kirjaimellisesti vain tehdä yksinkertainen aritmeettinen ja minne haluat lisäämällä yksi, for instance-- linkitettynä listana, te uhrata että ominaisuus. Et voi vain mennä ensimmäisestä ja toinen-kolmas ja neljäs. Sinun täytyy seurata karttaa. Sinun täytyy ottaa useampia vaiheita päästä niihin arvoihin, jotka näyttäisi olevan lisäämällä kustannuksia. Niinpä me ne maksavat, mutta mikä oli ominaisuus, joka Dan pyrki täällä? Mitä linkitetty lista ilmeisesti jotta voisimme tehdä, joka oli alkuperä tässä tarina? 

Täsmälleen. Dynaaminen kokoa sitä. Voimme lisätä tähän luetteloon. Voimme jopa kutistua listalle niin että me vain käyttää niin paljon muistia koska me todella haluavat ja niin emme ole koskaan liikaa kohdentamisessa. 

Nyt vain olla todella kinastelemme-nirso, siellä on piilotettu kustannuksia. Joten kannattaa ei anna minun vakuuttaa teille, että tämä on vakuuttava kompromissi. On toinenkin piilokustannuksia täällä. Hyöty, tehtävä selväksi, että saamme dynamiikkaa. Jos en halua toista elementtiä, voin vain piirtää sen ja laittaa numero siellä. Ja sitten voin linkittää sen kuvalla täällä, kun taas tänne, uudelleen, jos olen maalattu itse nurkkaan, jos jotain muuta on jo käytössä muisti täällä, olen pois onnea. Olen maalannut itseni nurkkaan. 

Mutta mikä on piilotettu maksaa tässä kuvassa? Se ei ole vain määrästä aika, joka kuluu lähteä täältä täältä, joka on seitsemän vaihetta, niin kahdeksan vaihetta, jotka on enemmän kuin yksi. Mikä toinen piilokustannuksia? Ei vain kerran. Lisätietoja on saavuttamiseksi tarpeen tätä kuvaa. 

Niin, että kartta, niitä pieniä vieraskirjatekstit paperi, koska pidän heidät määritellään. Nämä arrows-- ne eivät ole ilmaisia. Computer-- tiedät mitä tietokoneessa on. Se on nollia ja ykkösiä. Jos haluat edustaa nuoli tai kartta tai useita, tarvitaan jonkin verran muistia. Joten muut hinta te maksaa linkitettynä listana, yhteinen tietotekniikassa resurssi, on myös tilaa. 

Ja todellakin niin, niin yleisesti, joukossa kompromissit suunnittelussa ohjelmistotuotannossa järjestelmiin on aikaa ja space-- ovat kaksi ainekset, kaksi oman kalleimpia ainesosia. Tämä maksaa minulle enemmän aikaa koska minun täytyy seurata tätä karttaa, mutta se on myös maksaa minulle enemmän tilaa koska minun täytyy pitää tämä kartan ympärillä. Joten toivon, sillä olemme tavallaan keskusteltu yli eilen ja tänään, on, että hyödyt ovat suuremmat kuin kustannukset. 

Mutta ei ole selvää ratkaisua. Ehkä se on better-- a la nopea ja likainen, kuten Kareem ehdotettu earlier-- heittää muisti ongelmaa. Just ostaa lisää muistia, ajatella vähemmän ankarasti ongelman ratkaisemiseksi, ja ratkaista sen helpommin. Ja todellakin aiemmin, kun puhuimme kompromissit, se ei ollut tilaa tietokone ja aikaa. Se oli kehittäjä aika, joka on vielä toinen resurssi. 

Joten jälleen, se on tämä tasapainoilua yrittää päättää, mitä näistä asioista olet valmis maksamaan? Joka on edullisin? Joka tuottaa parempia tuloksia? Joo? 

Todellakin. Tässä tapauksessa, jos olet edustaa numeroita maps-- näitä kutsutaan monilla kielillä "Viitteitä" tai "osoitteita" - se kaksinkertainen tilaa. Se ei tarvitse olla niin huono kuin kaksinkertainen, jos nyt me vain tallentaminen. Oletetaan, että olimme tallentamiseen potilastietoja on hospital-- joten Pierson nimet, puhelinnumerot, sosiaaliturvatunnuksia, lääkäri historia. Tämä laatikko voi olla paljon, paljon suurempi, jolloin pikku osoitin, osoite seuraava element-- se ei ole iso juttu. Se on niin hapsut maksaa sillä ei ole väliä. Mutta tässä tapauksessa, joo, se kaksinkertaistamista. Hyvä kysymys. 

Puhutaanpa kertaa hieman konkreettisemmin. Mikä käyntiaika etsiä tästä luettelosta? Oletetaan Halusin etsiä läpi kaikki opiskelijoiden laadut, ja siellä on n laadut tässä tietorakenteessa. Tässäkin voimme lainata sanastoa aiemmin. Tämä on lineaarinen tietorakenne. 

Big O n on mitä tarvitaan, jotta saat loppuun tämän datarakenteen, whereas-- ja emme ole nähneet Tämän before-- array antaa sinulle mitä kutsutaan vakio aikaa, mikä tarkoittaa, yhdessä vaiheessa tai kahdessa vaiheessa tai 10 steps-- ei ole väliä. Se on kiinteä määrä. Sillä ei ole mitään tekemistä sen kanssa koko jono. Ja syy siihen, uudelleen, on random access. Tietokone voi vain välittömästi hypätä toiseen paikkaan, koska ne ovat kaikki samanlaisia etäisyyden kaikki muu. Ei ole ajattelua mukana. Selvä. Joten jos voin, haluan yrittää maalata kaksi viimeistä kuvaa. Hyvin yleinen yksi tunnettu hajautustaulua. Joten motivoida tähän keskusteluun, haluan miettiä, miten tämä tehdään. 

Miten tästä? Oletetaan, että ongelma haluamme ratkaista nyt toteuttaa joka dictionary-- niin koko joukko Englanti sanat tai miten vaan. Ja tavoitteena on pystyä vastaamaan kysymyksiä lomake on tämä sana? Joten haluat toteuttaa oikeinkirjoituksen tarkistus, vain kuten fyysinen sanakirja että voit katsoa asioita ylös. Kai oli tehdä tämä jono. Voisin tehdä tätä. 

Ja olettaa sanat ovat omena ja banaani ja fenkoli. Enkä voi ajatella hedelmiä jotka alkavat d, joten olemme vain menossa on kolme hedelmää. Joten tämä on joukko, ja olemme tallentaa kaikki nämä sanat Tässä sanakirjassa taulukkona. Kysymys onkin, miten muuten voisi tallentaa tämän tiedon? 

No, minä tavallaan pettää täällä, koska kukin näistä sanan kirjainten on todella yksilöllinen tavu. Joten jos halusin olla NIT-nirso, minun pitäisi oikeastaan voidaan jakaa tämä ylös paljon pienempiä paloina muistia, ja voisimme tehdä juuri näin. Mutta emme aio törmätä sama ongelma kuin ennen. Mitä jos, kuten Merriam Webster tai Oxford tekee joka year-- he lisätä sanoja että dictionary-- emme välttämättä halua maalata itse nurkkaan jossa joukko? 

Joten sen sijaan, ehkä älykkäämpi lähestymistapa on laittaa omena omassa solmussa tai laatikko, kuten me sanoisimme, banaani, ja niin tässä meillä on fenkoli. Ja me merkkijono nämä asiat yhdessä. Joten tämä on jono, ja tämä on linkitetty lista. Jos et voi täysin nähdä, se vain sanoo "array", ja tämä sanoo "lista." 

Joten meillä on sama tarkka asioita kuin ennen, jolloin meillä on nyt dynamiikkaa meidän linkitetty lista. Meillä on kuitenkin melko hidasta sanakirja. Oletetaan Haluan etsiä sanan. Saattaa kestää minua ison O n vaiheita, koska sana voisi on aina lopussa luettelosta, kuten melonia. Ja käy ilmi, että ohjelmointi, sort Graalin malja tietojen rakenteet, on jotain joka antaa sinulle jatkuvaa aikaa kuin array mutta silti antaa sinulle dynamiikkaa. 

Joten voimme olla molempien maailmojen parhaat puolet? Ja todellakin, siellä on jotain nimeltään tiiviste jonka avulla voit tehdä juuri että, vaikkakin noin. Hash-taulukko on hienompaa tietorakenne että me voi ajatella kuin yhdistelmä array-- ja aion tehdä sitä tämän kaltaisia ​​osia ja linkitettyjen listojen että minä piirtää näin tänne. 

Ja miten tämä asia teokset on seuraava. Jos tämä now-- hash table-- on kolmas datarakenne, ja haluan tallentaa sanoja tässä, en haluavat vain tallentaa kaikki sanat takaisin takaisin takaisin takaisin. Haluan hyödyntää joitakin tieto sanoista, jonka avulla minua saamaan sen, missä se on nopeampi. 

Joten annetaan sanat omena ja banaani ja fenkoli, Olen tietoisesti valinnut nuo sanat. Miksi? Mikä on tavallaan pohjimmiltaan Eri noin kolme? Mikä on selvää? Ne alkavat eri kirjaimilla. 

Joten tiedätkö mitä? Sen sijaan laittaa kaikki minun sanat sama ämpäri, niin sanotusti, kuten yksi iso lista, miksi ei En edes yrittää optimointi ja tehdä minun luettelot 1/26 niin kauan. Pakottava optimointi ehkä miksi ei I-- lisättäessä sana tähän tietorakenne, tietokoneen muistiin, miksi älä Laitoin kaikki "a" sanoja täällä, kaikki "b" sanoja täällä, ja kaikki "c" sanoja täällä? Joten tämä päätyy laskemisesta omena täällä, banaani täällä, fenkoli täällä, ja niin edelleen. 

Ja jos olen ylimääräinen Sana like-- mitä toinen? Apple, banaani, päärynä. Jokainen ajatella hedelmän joka alkaa a, b tai c? Blueberry-- täydellinen. Tämä on menossa päätyä tänne. Ja niin me näyttää olevan marginaalisesti parempi ratkaisu, koska nyt jos haluan etsiä omena, minä first-- En syvenny minun tietorakennetta. En sukeltaa minun tietokoneen muistiin. En ensin katsoa ensimmäinen kirjain. 

Ja tämä on mitä tietokone tiedemies sanoisi. Sinä hash osaksi tietorakennetta. Otat syöte, joka Tässä tapauksessa on sana kuin omena. Sinä analysoida sitä, katsomalla ensimmäinen kirjain tässä tapauksessa, Näin hajautus se. Hajautusta on yleinen termi, jolla otat jotain syötteenä ja te tuottaa noin tuotos. Ja lähtö kyseisessä asia on sijainti haluat etsiä, ensimmäinen sijainti, toisessa paikassa, kolmas. Joten tulo on omena, lähtö on ensimmäinen. Syöte on banaani, The tuotos olisi toinen. Panos on cantaloupe, tuotos olisi kolmas. Syöte on mustikka, The tuotos on jälleen oltava toinen. Ja se mitä auttaa pitämään pikakuvakkeet kautta muistin saadakseen sanoihin tai tietoja tehokkaammin. 

Nyt tämä supistetaan aikamme potentiaalisesti peräti yksi 26, koska jos oletetaan, että olet niin monta "a" sanoja kuin "z" sanoja kuin "q" sanoja, jotka ei oikeastaan ​​realistic-- olet menossa on vinossa yli tietyt kirjaimet alphabet-- mutta tämä olisi vähitellen lähestymistapa, joka ei salli voit saada sanoja paljon nopeammin. Ja todellisuudessa, hienostunut ohjelman Googles maailman, Facebooks on world-- he käyttäisivät hajautustaulua sillä paljon eri tarkoituksiin. Mutta he eivät olisi niin naiivi kuin ja katsokaa ensimmäinen kirjain omena tai banaani tai päärynä tai cantaloupe, koska kuten näette nämä luettelot voi silti saada pitkä. 

Ja niin tämä saattaa silti olla eräänlainen of linear-- joten tavallaan hitaasti, kuten isolla O n että keskustelimme aiemmin. Joten mitä todella hyvä hash taulukon do-- sillä on paljon suurempi joukko. Ja se käyttää paljon hienostunut hajautusfunktio, niin että se ei katsokaa "a." Ehkä se katsoo "a-p-p-l-e" ja jotenkin muuntaa ne viisi kirjainta osaksi paikka, jossa omena tulisi säilyttää. Olemme vain sinisilmäisesti käyttämällä kirjain "a" yksin, koska se on mukava ja yksinkertainen. 

Mutta tiiviste, vuonna Lopulta voit ajatella of yhdistelmänä joukko, joista jokainen on linkitetty lista, että ihannetapauksessa tulisi olla mahdollisimman lyhyt. Ja tämä ei ole ilmeinen ratkaisu. Itse asiassa suuri osa hienosäätöä joka jatkuu alla huppu, kun täytäntöön tällaisia hienostunut tietorakenteet on mikä on oikea pituus array? Mikä on oikea hajautusfunktio? Miten tallentaa asioita muistiin? 

Mutta ymmärtää, kuinka nopeasti tällaista keskustelua kiristynyt, joko niin pitkälle, että se on eräänlainen Yli päänsä tässä vaiheessa, mikä on hyvin. Mutta aloitimme, recall, jossa todella jotain matalan tason ja elektroninen. Ja niin tämä taas on tämä teema abstraktio, jossa kun alkaa itsestään myönnetty, OK, minulla it-- siellä fyysistä muistia, Selvä, joka fyysinen sijainti on osoite, OK, sain sen, voin edustaa nämä osoitteet arrows-- voit nopeasti alkaa olla kehittyneempiä keskustelut lopulta näyttävät antaa meille ratkaisemaan ongelmia, kuten hakuja ja lajittelu tehokkaammin. Ja varma, too-- koska mielestäni tämä on syvin olemme menneet jonkin verran Näiden CS aiheiden proper-- olemme tehdään päivässä ja puoli tässä kohta mitä voisi yleensä tehdä yli aikana kahdeksan viikkoa lukukauden. 

Kysyttävää näistä? Ei? Selvä. No, miksi emme keskeytä siellä, Aloita lounas muutaman minuuttia etuajassa, Jatka vain noin tunnin? Ja minä viipyä hieman kysymyksiä. Sitten aion mennä kestää muutaman puhelut, jos se on OK. Tulen päälle musiikkia tällä välin mutta lounas pitäisi olla nurkan takana.