DAVID Humala: Hea küll. Me oleme tagasi. Nii et selles segmendis programmeerimine mida Ma arvasin, et me tahaks teha on segu asju. Üks, teha natuke midagi praktilist, kuigi kasutades rohkem mänguline programmeerimine environment-- üks, mis on demonstratiivne kohta täpselt liiki ideed oleme rääkinud, kuid veidi rohkem formaalselt. Kaks, mõningaid rohkem tehniliste viise et programmeerija tegelikult lahendada probleeme nagu otsides probleem et me vaatasime enne ja Samuti põhilisemalt huvitav probleem sorteerimine. 

Me lihtsalt eeldada saanud minna et see telefoniraamat oli järjestatud, kuid üksi on tegelikult omamoodi raske probleem paljudel erinevatel viisidel seda lahendada. Nii me kasutame neid kui klassi probleeme esindaja asju, mis võiks lahendada üldiselt. Ja siis me räägime umbes üsna üksikasjalikult, mida nimetatakse andmete structures-- Kasvataja viisil nagu ahelloendid ja hash tabelid ja puud, mis Programmeerija tegelikult kasutada ja üldiselt kasutada tahvlile joonistada pildi, mida ta piltlikult ette kujutada rakendamise mõned tükk tarkvara. 

Nii teeme käed-osa esimene. Nii lihtsalt saada oma käed määrdunud koos keskkonda nimetatakse scratch.mit.edu. See on vahend, mida me kasutame Meie bakalaureuse klassi. Kuigi see on mõeldud vanuses 12 ja üles, Me kasutame seda üles osa, et üsna vähe kuna see on kena, lõbus graafiline viis õppimiseks natuke midagi programmeerimisest. Nii pea, et URL, kus te peaks näha lehe päris niimoodi, ja minna ja kliki Liitu Scratch ülevalt paremalt ja valida kasutajanimi ja parooli ning lõpuks saan ise account-- scratch.mit.edu. Ma mõtlesin, et ma kasutada seda kui võimalust esimesena näidata. Küsimus tulid Vaheajal mida koodi tegelikult välja näeb. Ja rääkisime Vaheajal umbes C, aastal particular-- iseäranis madalamal tasemel vanem keel. Ja ma lihtsalt tegin kiire Google'i otsing leida C koodi kahe- otsingu algoritmi, et me kasutatakse otsida, et telefoniraamatus varem. See konkreetne näide muidugi ei otsi telefoniraamatust. See lihtsalt otsib terve hulk numbrite arvuti mällu. Aga kui te soovite lihtsalt saada visuaalne tunnet, mida tegelik programmeerimine keele välja näeb, tundub natuke midagi sellist. Nii et see on umbes 20-pluss, 30 või nii rida koodi, kuid vestlus me olid võttes üle break oli, kuidas see tegelikult saab aga välja ühtede ja nullide ja kui sa ei saa lihtsalt tagasi, et töödelda ja lähevad ühtede ja nullide tagasi üles koodi. 

Kahjuks protsessi on nii teosed et see on palju lihtsam öelda kui teha. Ma läksin edasi ja tegelikult välja et programm, Binary Search, arvesse ühtede ja nullide teel programm nimega kompilaator, et ma juhtumisi on siin just minu Mac. Ja kui te vaatate ekraani siin, keskendudes eelkõige Nende keskel sammastele ainult näete ainult ühtede ja nullide. Ja need on ühtede ja nullide et kirjutada täpselt, et otsimise programmi. 

Ja nii iga tüki viis bitti, Iga bait ühtede ja nullide siin moodustavad umbes juhendamine tüüpiliselt sees arvutis. Ja tegelikult, kui olete kuulnud marketing hüüdlause "Intel inside" -, et Loomulikult tähendab lihtsalt teil on Intel CPU või aju sees arvutit. Ja mida see tähendab olla CPU on et teil on käsustik niiöelda. 

Iga protsessori maailmas, paljud neist valmistatud Intel nendel päevadel, mõistab piiratud arvu juhiseid. Ja need juhised on nii madalal tasemel kui lisada need kaks numbrit kokku korrutab need kaks numbrit kokku seda malendit liigutada andmeid siit Siia mällu salvestada see info siit siiani mälus, ja nii forth-- nii väga madala peaaegu elektroonilise üksikasju. Aga nende matemaatiliste toimingud on ühendatud mida me varem käsitletud, esindatus andmeid kui ühtede ja nullide, saab sa luua kõike et arvuti saab teha täna, kas see on tekstiline, graafiline, muusika-, või muidu. 

Nii et see on väga lihtne saada kadunud umbrohi kiiresti. Ja seal on palju süntaktiline väljakutseid kusjuures, kui sa teed kõige lihtsam, stupidest kirjavigu ükski programm töötab üldse. Ja nii selle asemel keeles nagu C täna hommikul Ma arvasin, et see oleks lõbusam tegelikult teha midagi visuaalset, mis samas mõeldud lastele on tegelikult ideaalne ilming tegeliku programmeerimine language-- lihtsalt juhtub Piltide kasutamine teksti asemel esindada neid ideid. 

Nii et kui sa tõepoolest olla konto scratch.mit.edu, nupu Loo ülevalt vasakult kohas. Ja sa peaksid nägema keskkonnas nagu mida ma olen umbes et näha minu ekraanil siin. Ja me kulutada vaid veidi natuke aega mänginud siin. Vaatame, kas me ei suuda kõiki lahendada mõned probleemid koos järgmisel viisil. 

Nii et mida te näete selles environment-- ja tegelikult lihtsalt lasta mind mõtlema. Kas keegi ei ole siin? Mitte siin? OKEI. Nii et lubage mul rõhutada paari omadusi selles keskkonnas. 

Nii ülaosas vasakul ekraani, me on Scratch etappi, nii rääkida. Kraabi ei ole ainult nimi Selle programmeerimiskeele; see on ka nimi kass, et näed vaikimisi seal oranž. Ta on laval, nii palju nagu ma kirjeldasin kilpkonn varem olles ristkülikukujuline valge tahvel keskkond. See kassi maailma piirdub täielikult Selle ristküliku kuni ülemise seal. 

Vahepeal, paremal pool siin, see on vaid skripte alal, puhtalt lehelt, kui soovite. See on koht, kus me ei kavatse kirjutada Meie programmid hetk. Ja ehituskivid, et me kasuta kirjutada selle program-- puzzle tükki, kui te will-- on need siin keset, ja nad liigitada funktsiooni järgi. Nii näiteks, et ma lähen edasi minna ja annavad vähemalt üks neist. Ma lähen edasi minna ja kliki Control kategooria kuni top. 

Nii et need on kategooriad, kuni top. Ma lähen käsku Control kategooriasse. Pigem ma lähen klõpsake sündmused kategooria, kõige esimene kuni top. Ja kui soovite jälgida mööda isegi nagu me seda teha, sa oled üsna teretulnud. Ma lähen klõpsa ja lohista see Esimene, "kui roheline lipp klõpsatud." Ja siis ma lähen tilk seda lihtsalt umbes ülaosas minu tühi tahvlid. 

Ja mis tore Scratch on see, et see pusletükk, kui blokeerituks teiste puzzle tükki, kavatseb teha sõna otseses mõttes millised need puzzle tükid öelda seda teha. Nii näiteks Scratch on õige nüüd keset oma maailma. Ma lähen edasi minna ja valida Nüüd oletame, Motion kategoorias Kui soovite teha same-- Resolutsiooni kategooriasse. Ja nüüd märgata Mul on terve kamp puzzle tükki siin veel kord, et sellist teha, mida nad ütlevad. Ja ma lähen edasi minna ja tõmmata ja tilk liikuda blokeerida õigus siin. 

Ja märgata, et niipea, kui saad põhja lähedal "rohelise lipu klõpsatud "nuppu, teate kuidas valge joon tundub, nagu ta on peaaegu magnet, ta tahab sinna minna. Lihtsalt lase minna, ja ta haarab koos ja kuju sobib. Ja nüüd saab ehk peaaegu arvan, et kui me läheme seda. 

Kui te vaatate Scratch etapi siin ja vaadata selle peale, näete punane valgus, stop märk ja roheline lipp. Ja ma lähen edasi minna ja vaadata minu screen-- hetkeks, kui saaksid. Ma lähen klõpsa roheline lipp kohe, ja ta kolis mis tundub olevat 10 sammu või 10 pikslit, 10 punkti, ekraanile. 

Ja nii ei ole, et põnev, kuid lubage mul pakkuda isegi õpetades seda, lihtsalt abil ise oma intuition-- let mulle ettepaneku, et te saate aru saada, kuidas teha Scratch Kõnnid laval. Kas ta teha ruumi paremal pool ekraani, kõik viis õigus. Annan hetk või nii maadelda, et. Võiksid vaatleme teiste kategooriate plokid. Hästi. Nii lihtsalt sulgege, kui meil on roheline lipp klõpsatud siin ja liikuda 10 sammu on ainult juhendamise, iga kord, kui ma nuppu roheline lipp, mis toimub? Noh, see töötab minu programm. Nii et ma võiks seda teha võibolla 10 korda käsitsi aga see tundub natuke natuke hackish, nii-öelda kusjuures ma ei ole tõesti probleemi lahendamisele. Ma lihtsalt üritan uuesti ja uuesti ja uuesti ja uuesti kuni ma justkui kogemata saavutada direktiivi et ma sätestatud, et saavutada varem. 

Aga me teame, meie pseudokoodi varem, et seal on seda mõistet programmeerimine kordaminelooping, midagi ikka ja jälle. Ja nii ma nägin, et kamp teile jõudnud, mida pusletükk? Korda kuni. Nii et me võiks teha midagi nagu korrata seni, kuni. Ja mida sa korrata, kuni täpselt? 

OKEI. Ja lase mul minna ühega, mis on mõnevõrra lihtsam hetkeks. Lubage mul minna ja seda teha. Pange tähele, et teil võib olla avastas kontrolli all, on see korduvus plokk, mis ei tundu see nii suur. Seal ei ole palju ruumi Nende kahe kollane jooned. Aga nagu mõned teist võib-olla märganud, kui te lohistada, märgata, kuidas ta kasvab, et täita kuju. 

Ja võite isegi tuupima rohkem. See muudkui kasvab, kui lohistamise ja viid selle üle. Ja ma ei tea, mis on Parim siin, nii et let mulle vähemalt korrata viis korda, sest Näiteks ja siis tagasi minna lavale ja nuppu roheline lipp. Ja nüüd märkate see ei ole päris seal. 

Nüüd mõned teist kavandataval Victoria lihtsalt ei korrata 10 korda. Ja et üldiselt ei saada teda kogu tee, kuid siis ei tekiks tugevam viis kui meelevaldselt figuring kui palju liigub teha? Mis võiks olla parem plokk kordavad 10 korda olla? 

Jah, miks mitte teha midagi igavesti? Ja nüüd lubage mul liikuda selles puzzle tükk sees olemas ja vabaneda seda. Nüüd märkate ükskõik kus Scratch algab, läheb ta serva. Ja õnneks MIT, kes teeb Scratch, lihtsalt tagab, et ta ei ole kunagi kaob täielikult. Teil on alati võimalik haarata oma saba. 

Ja just intuitiivselt, miks ta edasi liikuma? Mis siin toimub? Ta tundub olevat peatunud, kuid siis kui ma kiirenemist ja lohista ta hoiab, kes tahavad minna sinna. Miks nii? Tõesti, arvuti on sõna otseses mõttes kavatseb teha, mida sa öelda tahad. Nii et kui sa ütlesid seda varem teha järgmised asi igavesti liikuma 10 sammu, see läheb edasi minema ja läheb kuni ma tabanud punane stop märk ja lõpetada programmi kokku. 

Nii et isegi kui sa ei ole Selleks, kuidas ma teha Scratch liikuda kiiremini üle ekraani? Rohkem samme, eks? Nii et selle asemel tee 10 korraga, miks me ei minna ja muuta see mina-- mida sa propose-- 50? Nüüd ma lähen nuppu roheline lipp ja tõepoolest, ta läheb väga kiiresti. 

Ja see muidugi on lihtsalt ilming animatsiooni. Mis on animatsioon? See lihtsalt näitab teile Inimese terve hunnik pilte tõesti, tõesti, tõesti kiire. Ja kui me lihtsalt ütlen teda liigutada rohkem samme, me lihtsalt võttes mõju olema muutus, kus ta on ekraanil kõik kiiremini ajaühikus. 

Nüüd järgmine väljakutse, et ma pakutud pidi ta põrgatama off serval. Ja teadmata, mida puzzle tükki exist--, sest see on hea kui te ei saada etapi challenge-- mida sa tahad teha intuitiivselt? Kuidas me teda põrge tagasi ja edasi, vahel vasakule ja paremale? 

Jah. Seega on meil vaja mingisugust seisundis, ja me tundub, et on conditionals, nii et rääkida, kontrolli all kategooriasse. Milline neist plokid me ilmselt tahavad? Jah, võib-olla ", kui siis." Nii märgata, et üks kollane plokid meil siin on see "kui" või seda ", kui muidu" plokk, mis võimaldab meil teha otsus seda teha või seda teha. Ja võite isegi istutada teha mitu asja. Või kui olete ei läinud siin veel, minna kuni Sensing kategooria Ja-- vaatame, kas see on siin. 

Mida plokk võib olla kasulik siin avastada, kui ta on laval? Jah, märkate, et mõned neist plokid saab parametriseerisin, nii rääkida. Neid saab omamoodi kohandatud, ei Erinevalt HTML eile atribuute, kus need atribuudid liiki kohandada käitumist silt. Samamoodi siin, ma saan rüütama see liigutav blokeerida ja muutmine ning küsida, sa puudutamata hiir osuti nagu kursor või on teil puudutamata serva? 

Nii et lubage mul minna ja seda teha. Ma lähen välja suumida hetkeks. Lubage mul rüütama see pusletükk siin see pusletükk seda, ja ma lähen pudi-padi neid hetkeks. Ma lähen liikuda selles, muuta see liigutav serva, ja ma lähen algatusel seda teha. Nii et siin on mõned koostisosad. Ma arvan, et mul on kõik, mida ma tahan. 

Kas keegi tahaks pakkuda, kuidas ma saab ühendada neid võibolla ülevalt alla et lahendada probleemi, millel Scratch liikuda paremalt vasakule paremale vasakult paremale vasakule, iga aega lihtsalt kopsakas seina? Mida ma tahan teha? Mis blokeerivad ma peaksin ühendada "Kui roheline lipp klõpsatud esimene"? 

OK, nii et alustame koos "igavesti." Mis läheb sees edasi? Keegi teine. OK, liikuda samme. Hästi. Siis mida? Nii siis, kui. Ja märgata, kuigi see näeb kihi tihedalt kokku, see lihtsalt kasvab täita. See lihtsalt hüpata, kui ma tahan seda. 

Ja mida ma panen vahel IF ja siis? Ilmselt ", kui liigutav serva." Ja teate, jälle, see on liiga suur seda, kuid see kasvab täita. Ja siis keera 15 kraadi? Mitu kraadi? Jah, nii et 180 on spin mul kõik vastupidi. Vaatame, kas ma sain selle õige. Lubage mul suumimiseks. 

Lubage mul lohistada Scratch üles. Nii ta on natuke moonutatud nüüd, kuid see on hea. Kuidas nullida teda lihtsalt? Ma lähen petta kergelt. Nii et ma olen lisades teise plokk, vaid peab olema selge. Ma tahan, et ta punktist 90 kraadi paremale vaikimisi nii et ma lihtsalt lähen talle öelda mida teha, et programmiliselt. Ja siin me läheme. Tundub, et me oleme seda teinud. See on natuke imelik, sest ta kõnnib tagurpidi. Kutsume mis viga. See on viga. Viga on viga programmi, ilmub loogikaviga, et mina, inimene, tehtud. Miks ta läheb tagurpidi? Kas MIT kruvi üles või tegi olen? 

Jah, ma mõtlen, et see ei ole MIT süü. Nad andsid mulle pusletükk mis ütleb omakorda mõned arvu kraadi. Ja Victoria ettepanekut, Ma keeran 180 kraadi, mis on õige intuitsiooni. Aga keerates 180 kraadi sõna otseses mõttes tähendab keerates 180 kraadi, ja see ei ole tõesti mida ma tahan, ilmselt. Sest vähemalt ta on See kahemõõtmeline maailm, nii pöördepunkt tegelikult toimub klapp teda tagurpidi. 

Ma ilmselt soovite kasutada milline plokk selle asemel, selle põhjal, mida te näete siin? Kuidas võiks me seda parandada? Jah, nii et me võiks juhtida vastupidises suunas. Ja tegelikult isegi see ei kavatse olla piisavalt, sest saame ainult kõva koodi juhtides vasakule või paremale. 

Sa tead, mida me võiksime teha? Tundub, et meil on Mugavuse plokk siin. Kui ma suumida, vaata midagi meile meeldib siin? Seega tundub, MIT on võtmiseks ehitatud siin. See plokk tundub olevat samaväärne millele teised plokid, mitmuses? 

See üks plokk tundub olevat samaväärne et kogu see kolmik plokid et meil on siin. Nii selgub võin lihtsustada minu Programm vabanemiseks kõik, et ja lihtsalt panna see siia. Ja nüüd on ta ikka natuke lollakas, ja see on hea nüüd. Me jätan selle olla. Aga minu programm on isegi lihtsamad ning ka see Oleks esindaja on eesmärk programming-- on ideaalis teha oma koodi lihtne, võimalikult kompaktne, ja samal ajal kui loetav kui võimalik. Sa ei taha, et see nii sisutihedat et see on raske aru saada. 

Aga märgata Olen asendatakse kolme ploki ühe, ja see on vaieldamatult hea. Olen ammutatud minema ettekujutuse kontrollida, kas sa oled äärel vaid ühe ploki. Nüüd saame nautige seda tegelikult. See ei lisa nii palju intellektuaalne väärtus, kuid mänguline väärtus. Ma lähen edasi minna ja haarata seda heli siin. Nii et lubage mul minna ja las ma stop programm hetkeks. Ma lähen salvestama, võimaldades juurdepääsu oma mikrofoni. 

Siin me läheme. Ai. Proovime uuesti. Siin me läheme. OK, ma salvestatud vale asi. Siin me läheme. Ai. Ai. Hästi. Nüüd on mul vaja vabaneda sellest. Hästi. 

Nüüd on mul salvestamine lihtsalt "Ai". Nüüd ma lähen käia ja nimetame seda "Ai". Ma lähen tagasi minu skripte ja nüüd teate seal on see plokk, mis nimetatakse mängida heli "mjäu" või mängida heli "Ai". Ma lähen lohista see, ja kus ma peaksin seda koomilise efekti? Jah, nii et nüüd on selline lollakas, sest nüüd on see block-- märgata, kuidas see "kui serv, põrge "on selline iseseisev. Nii et ma pean seda parandada. Lubage mul minna ja seda teha. Lubage mul vabaneda sellest ja mine tagasi meie originaal, tahtlik funktsionaalsust. Nii "kui liigutav serva, siis" Ma tahan pöörduda, kui Victoria ettepaneku, 180 kraadi. Ja ma tahan mängida heli "Ai" on? 

Jah, märgata on väljaspool et kollane plokk. Nii ka see oleks viga, aga ma olen märganud seda. Nii et ma lähen lohista see siia üles ja teate nüüd on see sees "kui". Nii et "kui" on selline samasuguse käe-like blot See on ainult kavatse seda, mida on sees on. Nüüd, kui ma välja suumida juures riski annoying-- 

Arvuti: Ai, Ai, Ai. 

DAVID Humala: Ja lihtsalt kesta igavesti. Nüüd lihtsalt kiirendada asju siin, las ma minna ja avada, olgem say-- lase mul minna mõnele minu enda kraami klassi. Ja las ma avada, oletame, et see üks tehtud üks meie õpetamise stipendiaatide paar aastat tagasi. Nii et mõned teist võib meenutada Selle mängu Läinud, ja see on tegelikult märkimisväärne. Kuigi me oleme teinud Lihtsaim programmide kohe, Vaatleme, mida see tegelikult välja näeb. Las ma tabanud mängida. 

Nii et selles mängus on meil konn ja noole abil keys-- Ta võtab suuremaid samme, kui ma mäletada Mul on kontroll selle konn. Ja eesmärk on saada kogu hõivatud tee ilma ulatuvad autod. Ja olgem see-- kui ma lähen siin, ma pea ootama logi kerida. See tunne on viga. See on selline viga. Hästi. Ma olen seda siin, seal, ja siis hoida läheb kuni sa saad kõik konnad lily padjad. Nüüd see võib tunduda kõik keerulisemas aga proovime murda Selle alla vaimselt verbaalselt koostisosadeks plokid. Nii et ilmselt puzzle tükk, et me ei ole näinud veel kuid see on vastates klahvivajutusi asju ma tabanud klaviatuuril. 

Nii et ilmselt mingi plokk, mis ütleb, kui võti on võrdne üles tehke midagi Scratch-- võibolla liigutada 10 sammu sel viisil. Kui alla vajutatakse, liikuda 10 sammu Nii või vasakule võti, liikuda 10 sammu Sel moel 10 sammu, et. Olen selgelt välja, et kass konn. Nii et just seal, kus kostüüm, nagu Scratch kõned see-- me lihtsalt imporditud pilt konn. 

Aga mida muud toimub? Mis muu rida koodi, mida teised puzzle tükki tegid Blake, meie õpetamise mehe, kasutada seda programmi, ilmselt? Mida tehes kõike move-- Mis programmeerimise ehitada? 

Motion, sure-- nii liikuda plokk, kindlasti. Ja mis see on liikuda plokkide sees, kõige tõenäolisemalt? Jah, mingi loop, võibolla igavesti blokeerida, võibolla korrata block-- korrata, kuni plokk. Ja see on, mis teeb palke ja liilia padjad ja kõike muud liikuda edasi-tagasi. See on lihtsalt juhtub lõputult. 

Miks on mõned autod liigub kiiremini kui teised? Erinevus seisneb selles need programmid? Jah, ilmselt mõned neist võtavad rohkem sammu korraga ja mõned neist vähem etappe korraga. Ja visuaalne efekt on kiire vs aeglane. 

Mis te arvate juhtus? Kui sain konn kõik viis üle tänava ja jõe peale liilia pad, midagi Tähelepanuväärne juhtus. Mis juhtus, niipea kui ma tegin seda? See peatunud. See konn peatunud ja Ma sain teise konn. Nii et mida ehitada tuleb kasutatakse seal, mida funktsioon? 

Jah, nii et seal on mingi "Kui" tingimus seal ka. Ja selgub out-- me ei näe see-- kuid seal on teised plokid olemas, et Võib öelda, kui teil on liigutav teine ​​asi ekraanil kui sa puudutamata liilia pad ", siis." Ja siis see, kui me teha teine ​​konn ilmuda. Nii et kuigi see mäng on kindlasti väga kuupäevaga, kuigi esmapilgul seal on nii palju läheb nüüd-- ja Blake ei piitsutama selle üles kahe minuti jooksul, see ilmselt võttis ta mitu tundi, et luua seda mängu põhineb tema mälu või videod Läinud versioon sellest. Aga kõik need väikesed asjad läheb ekraanil eraldi Keeta neid väga lihtne constructs-- liikumise või avaldused nagu me oleme arutanud, silmad ja tingimused ja see ongi kõik. Seal on mõned muud Kasvataja funktsioone. Mõned neist on puhtalt esteetiline või akustiliste, nagu kõlab Ma lihtsalt mängitakse. Aga enamasti, siis on selles keeles, Scratch, kõik põhiõiguste ehitusplokke, et sa on C, Java, JavaScript, PHP, Ruby, Python, ja mis tahes mitmeid teisi keeli. Küsimusi Scratch? Hästi. Seepärast ei hakka me sukelduda sügavamale Scratch, kuigi sa oled teretulnud sel nädalavahetusel, eriti kui sul on lapsed või õelapsed ja õe ja sellised, tutvustada neile Scratch. See on tegelikult imeliselt mänguline keskkonda, kui selle autorid ütlevad, väga kõrged laed. Kuigi alustasime väga madala üksikasjad, saab tõesti teha üsna natuke koos, ja see on ehk tutvustamise just nii. 

Kuid olgem nüüd üleminek veidi rohkem keerulisi probleeme, kui soovite, tuntud kui "otsimise" ja "Sorteerimine" üldisemalt. Meil oli see telefoniraamat earlier-- siin teine ​​lihtsalt discussion-- et suutsime otsida tõhusamalt sest olulise eelduse. Ja just olema selge, mida Eeldus, ma muutes otsides läbi selle telefoni raamat? See Mike Smith oli telefoniraamat, kuigi ma oleks suuteline käitlema stsenaarium ilma temata seal, kui ma just lõpetanud enneaegselt. Raamatus on tähestiku. Ja see on väga helde eeldusel, sest see tähendab someone-- ma olen selline lõikamine nurgas, nagu ma olen kiirem, sest keegi teine ​​tegi palju tööd minu jaoks. 

Aga mis siis, kui telefon Raamat oli sortimata? Võib-olla Verizon sain laisk, lihtsalt viskas kõik nimed ja numbrid olemas võibolla järjekorras, milles nad registreerusin telefoni teenust. Ja kui palju aega see võtab mind et leida keegi, nagu Mike Smith? 1000 lk telefoni book-- mitu lehekülge pean vaatama läbi? 

Kõik nemad. Sa oled justkui läbi õnne. Sa sõna otseses mõttes pea otsima igal lehele, kui telefoniraamatus on lihtsalt juhuslikult järjestatud. Te võite saada õnnelik ja leida Mike juba esimesel lehel, sest ta oli esimene klient tellida telefoni teenust. Aga ta oleks võinud viimase ka. 

Nii juhuslikus järjekorras ei ole hea. Nii Oletame, et meil sorteerida telefoniraamat või üldiselt omamoodi andmeid et me oleme saanud. Kuidas me saame seda teha? 

Noh, lubage mul proovida Lihtne näide siin. Lubage mul minna ja Toss mõned numbrid laual. Oletame, et numbrid on meil on, oletame, neli, kaks, üks, kolm. Ja Ben, sorteeri need numbrid meile. 

Hästi. Kuidas sa seda tegid? Hästi. Seega tuleb alustada väikseima hinna ja kõrgeim, ja see on tõesti hea intuitsioon. Ja mõista, et me Inimestel on tegelikult päris hea probleemide lahendamise niimoodi, vähemalt kui andmed on suhteliselt väike. Niipea kui hakkad sadu Numbrite tuhandeid numbrid, miljoneid numbrid, Ben ilmselt ei saanud seda teha päris nii kiiresti, eeldades, et seal olid lüngad numbrid. Päris lihtne loota miljon Vastasel juhul lihtsalt aega. 

Nii algoritm see kõlab nagu Ben kasutada just oli Otsi kõige vähem. Nii et kuigi meie, inimesed saavad aastal palju informatsiooni visuaalselt, arvuti on tegelikult veidi rohkem piiratud. Arvuti saab ainult vaadata ühe baidi korraga või äkki nelja baiti juures AEG_ tänapäeval võibolla 8 baiti juures AEG_ aga väga väike arv baitide ajahetkel. 

Nii, arvestades, et meil on tõesti neli erinevat väärtuste siin-- ja sa ei mõtle Ben, millel silmaklapid, kui ta oli arvuti nagu et ta ei näe midagi muud kui üks number juures AEG_ nii et me üldjuhul eeldada, nagu Inglise, me lugeda paremalt vasakule. Nii et esimene number Ben ilmselt tundus kell oli neli ja seejärel väga kiiresti aru, et on päris suur number-- lase mul hoida otsin. 

Seal on kaks. Oota hetk. Kaks on väiksem kui neli. Ma mäletan. Kaks on nüüd kõige väiksem. Nüüd one-- see on isegi parem. See on veelgi väiksem. Ma lähen unustada kahte ja just mäleta nüüd. 

Ja kas ta peatus otsin? Noh, ta võiks aluseks Selle teabe kuid ta sõimanud otsing Ülejäänud nimekirjas. Sest mis siis, kui null olid nimekirjas? Mida teha, kui negatiivne olid nimekirjas? Ta teab, et tema vastus on õige, kui ta on ammendavalt kontrollida kogu nimekirja. Nii me vaatame ülejäänud seda. Three--, mis oli aja raiskamine. On õnnetu, aga ma olin ikka õige seda teha. Ja nii nüüd ta arvatavasti valitud väikseim arv ja lihtsalt pane see alguses nimekirja, kui ma teen siin. Nüüd, mida sa järgmisena teha, kuigi sa ei mõtle selle peale peaaegu selles osas? Korrake protsessi, nii mingi loop. Seal on tuttav idee. Nii et siin on neli. See on praegu kõige väiksem. See kandidaat. Enam mitte. Nüüd ma olen näinud kahte. See on järgmise väikseim element. Three-- see pole väiksem, nii et Nüüd Ben võib kiskuda kaks. 

Ja nüüd korrake protsessi ja Loomulikult kolm saab tõmmatud kõrval. Korrake protsessi. Neli saab välja tõmmata. Ja nüüd oleme välja numbrid, nii nimekirjas tuleb sorteerida. 

Ja tõepoolest, see on ametlik algoritm. Arvuti teadlane oleks nimetame seda "Valiksortimine" idee on sorteerida nimekirja iteratively-- jälle ja ikka ja jälle valides Kõige vähem. Ja mis tore on see on lihtsalt nii paganama arusaadavad. See on nii lihtne. Ja võid korrata sama toimingut uuesti ja uuesti. See on lihtne. 

Sel juhul oli kiire, kuid kui kaua see tegelikult aega võtab? Teeme tundub ja tunnen veidi tüütu. Nii üks, kaks, kolm, neli, viis kuus, seitse, kaheksa, üheksa, 10, 11, 12, 13, 14, 15, 16-- suvaline number. Tahtsin rohkem see aega kui lihtsalt neli. Nii et kui mul on kogu hunnik numbreid now-- see isegi ei loe mida nad are-- olgem mõelda, mida see algoritm tõesti ei meeldi. 

Oletatakse, et numbrid seal. Jällegi, ei ole oluline milliseid nad on, kuid nad juhuslikult. Ma esitan Ben algoritm. Mul on vaja valida väiksema arvu. Mida teha? Ja ma lähen füüsiliselt seda seekord tegutseda välja. Vaadates, otsin, otsin, otsin, otsin. Ainult selleks ajaks saan lõpuks saab nimekirja Ma saan aru, väikseim number oli kaks seekord. Üks ei ole nimekirjas. Nii et ma panema kaks. 

Mida teha edasi? Vaadates, otsin, otsin, otsin. Nüüd leidsin number seitse, sest seal on lüngad nendes numbers-- vaid lihtsalt suvaline. Hästi. Nüüd võin panema seitse. Vaadates otsin, otsin. 

Nüüd ma olen eeldades, ning Muidugi, et Ben ei on ekstra RAM, extra mälu, sest loomulikult Otsin sama number. Kindlasti ma oleks võinud meelde kõik need numbrid, ja see on täiesti tõsi. Aga kui Ben mäletab kõiki Numbrite ta on näinud, ta ei ole tõesti tehtud olulistest edusammudest sest ta on juba võime otsida läbi numbrid laual. Meenutades kõik numbrid ei aita, sest ta saab ikka nii arvuti ainult vaadata, me oleme öelnud, üks number korraga. Nii pole mingi cheat seal, et saate kasutada. 

Nii tegelikult, nagu ma hoida otsivad nimekirja, Ma sõna otseses mõttes pea muudkui läheb edasi-tagasi läbi, kitkumise välja Järgmise väikseim arv. Ja kui saad mingi järeldavad minu rumal liigutused, see lihtsalt muutub väga tüütu väga kiiresti, ja ma tundub, et läheb tagasi ja edasi, edasi ja tagasi üsna vähe. Nüüd oleks õiglane, ma ei pea minema päris nii hästi, olgem see-- oleks õiglane, Ma ei pea käima üsna kui palju samme iga kord. Sest, muidugi, nagu ma vali number loendist, Ülejäänud nimekirjas on üha lühemaks. 

Ja nii mõtleme kui palju samme ma olen tegelikult traipsing läbi iga kord. Kõige esimene olukord meil oli 16 numbrit, ja nii maximally-- olgem lihtsalt Selleks jaoks discussion-- Pidin otsima läbi 16 numbrid leida kõige väiksema. Aga kui ma välja kiskunud väikseim arv, kuidas pikk oli ülejäänud nimekirja, muidugi? Just 15. Nii mitu numbrit ei Ben või mul vaadata läbi teist korda ümber? 15, lihtsalt minna ja leida kõige väiksemad. Aga nüüd, muidugi, nimekiri on, Ka väiksem kui see oli enne. Nii mitu sammu tegin ma võtma järgmine kord? 14 ja siis 13 ja siis 12 pluss dot, dot, dot, kuni ma jäänud vaid üks. Nüüd arvuti teadlane oleks küsida, noh, mida see kõik võrdsed? See tegelikult võrdub mõne konkreetse number, et me võiks kindlasti teha aritmeetiliselt, kuid me tahame rääkida tõhususe kohta algoritmid veidi rohkem formulaically, sõltumatu, kui kaua nimekiri on. 

Ja nii sa tead, mida? See on 16, aga nagu ma ütlesin enne, Kutsume suuruse probleem n, kus n on mõned number. Võibolla on see 16, võib-olla see on kolm, võib-olla see miljon. Ma ei tea. Mind ei huvita. Mida ma tegelikult tahan on valem, mis suudan kasuta võrrelda seda algoritmi võrreldes teiste algoritmide et keegi võiks väita, on parem või halvem. 

Nii selgub, ja ma ainult Seda teame algkool, et see tegelikult toimib läbi sama asi nagu n üle n pluss üks üle kahe. Ja see juhtub võrdsed, ning Muidugi, n ruudus pluss n üle kahe. Nii et kui ma tahtsin valem Kui suure sammu osalesid vaadates kõik need numbrid ikka ja jälle ja ikka ja jälle, ma ütleks see on n ruudus pluss n üle kahe. Aga tead mis? See lihtsalt tundub segane. Ma tõesti tahan üldises mõttes asju. Ja võite tagasikutsumise keskkooli, et on mõiste kõrgeima järjekorras perspektiivis. Millised need tingimused, n ruudus, n, või pool, on kõige suurem mõju aja jooksul? Mida suurem n saab, mis nendes küsimustes kõige rohkem? 

Teisisõnu, kui ma plug miljon, n ruudus saab olema kõige tõenäolisem Valdavaks tegur, sest miljon korda ise on palju suurem kui pluss üks miljon. Nii et sa tead, mida? See on nii paganama suur number kui te ruudu number. See ei ole tegelikult küsimus. Me elame rist, et välja ja unusta see. Ja nii arvuti teadlane ütleks et tõhususe seda algoritmi on järjekorras n ruudus Ma mõtlen tõesti ligikaudne. See on omamoodi umbes n ruudus. Aja jooksul suurem ja suurem n saab, seda on hea prognoosida, mida tõhususe või ebatõhus Selle algoritmi tegelikult on. Ja ma tuletada, et loomulikult, alates tegelikult seda matemaatikat. Aga nüüd ma lihtsalt viipab käed, sest ma lihtsalt taha üldises mõttes seda algoritmi. 

Nii kasutades sama loogikat, vahepeal Vaatleme teise algoritmi me juba tundus at-- lineaarne otsing. Kui ma otsisin telefoni book-- ei sorteerimine, otsides läbi telefoni book-- me muudkui rääkisid, et see oli 1000 samme, või 500 sammu. Kuid olgem üldistada, et. Kui seal on n lehekülge telefoniraamatus, mis on Tööaja või tõhusust lineaarne otsing? See on järjekorras kui palju samme, et leida Mike Smith, kasutades lineaarset otsida, Esimene algoritmi või isegi teine? 

Halvimal juhul, Mike on lõpus raamat. Nii et kui telefoniraamatus on 1000 lehekülge, ütlesime viimane kord, halvimal juhul, see võib võtta umbes kuidas mitu lehekülge leida Mike? Nagu 1000. See on ülemine piir. See on halvim võimalik olukord. Aga jälle, me liigume eemale alates numbrid nagu 1000 praegu. See on lihtsalt n. 

Mis siis loogiline järeldus? Leida Mike telefon raamat, mis on n lehekülge võib võtta, et väga halvimal juhul kui palju samme selleks, n? Ja tõepoolest arvuti teadlane ütleks et sõiduaega või täitmise või efektiivsuse või ebaefektiivsus, algoritmi nagu lineaarne otsing on järjekorras n. Ja me saame rakendada sama loogika ületamisel midagi välja nagu ma just tegin teise algoritm oli meil telefoniraamatust kus me käisime kaks lehekülge korraga. 

Nii 1000 lehekülge telefoniraamat võiks meid 500 lk pöördeid, pluss üks kui me topelt tagasi natuke. Nii et kui telefoniraamatus on n lehekülge, kuid me teeme kaks lehekülge korraga, see on umbes siis? N üle kahe, nii et on nagu n üle kahe. Aga ma tegin Nõude hetk tagasi, et n üle two-- see on omamoodi sama lihtsalt n. See on lihtsalt konstandiks, arvuti teadlased öelda. Olgem keskenduda vaid muutujad, really-- suurim muutujate võrrand. 

Nii lineaarne otsing, kas teha üks lehte korraga või kaks lehekülge korraga, on omamoodi põhimõtteliselt sama. See on ikka tellimusel n. Aga ma väita minu pilt varem et kolmas algoritm ei olnud lineaarne. See ei olnud sirge. See oli see, et tõusva joone ja algebralist valemit oli siis? Logi n-- nii sisse baasi kaks n. Ja me ei pea minema liiga palju detaile logaritmide täna kuid enamik arvuti teadlased ei teeks isegi öelda, mida alus on. Sest see kõik on lihtsalt pidev tegurid, nii et rääkida, lihtsalt väike numbriline erinevusi. Ja nii see oleks väga sage teed eriti formaalse arvutis teadlased juhatuse või programmeerijad Wideboard tegelikult väites, mis algoritm nad kasutavad või mida tõhusust oma algoritmi. 

Ja see ei pruugi midagi sa arutada mingil väga täpselt, aga hea programmeerija on keegi kes on tugev, ametliku taustal. Ta on võimeline rääkima sa sellist teed ja tegelikult teha kvalitatiivne argumente miks üks algoritmi või üks tükk tarkvara on parem kuidagi teise. Sest sa võiks kindlasti lihtsalt joosta ühe inimese programmi ja loendada sekundit kulub sorteerida mõned numbrid, ja saate käivitada mõned teise inimese programmi ja loendada sekundit kulub. Aga see on üldisem nii, et mida saab kasutada, et analüüsida algoritme, kui soovite, lihtsalt paberist või lihtsalt verbaalselt. Ilma isegi töötab see ilma isegi üritab proovi sisendid, saab põhjuseta läbi. Ja nii rentides arendaja või kui võttes teda justkui väita, et sa miks nende algoritm, oma saladus kaste otsima miljardeid veebilehti oma Ettevõte on parem, neid on erinevaid väiteid, mida nad peaks ideaalis olema võimeline tegema. Või vähemalt need asju, mida et oleks tulla aruteluga juures vähemalt väga formaalne diskussioon. Hästi. Nii Ben pakutud midagi nimetatakse Valiksortimine. Aga ma lähen ettepaneku, et seal on teiste viise, liiga. Mida ma tegelikult ei meeldi umbes Ben algoritm on see, et ta pidas jalgsi või olles mul kõndida, edasi-tagasi ja edasi-tagasi ja edasi ja tagasi. Mis siis, kui selle asemel ma tegema midagi need numbrid siin ja ma lihtsalt suhtleb iga number omakorda nagu ma olen andnud talle? 

Teisisõnu, siin minu nimekirja numbrid. Neli, üks, kolm, kaks. Ja ma lähen tegema järgmist. Ma lähen sisestada numbrid kuhu nad kuuluvad pigem kui neid valides ühe korraga. Teisisõnu, siin on number neli. 

Siin on minu esialgses nimekirjas. Ja ma lähen hoida sisuliselt uue nimekirja siin. Nii et see on vana nimekirjast. See on uue nimekirja. Näen number neli esimest. Minu uus nimekiri on esialgu tühjad, nii et see on triviaalselt puhul et neli on nüüd assortii nimekirja. Ma lihtsalt tunnen arvu ma antud, ja ma panen ta oma uues nimekirjas. 

Kas see uus nimekiri järjestatud? Jah. Tobe, sest seal on ainult üks element, kuid see on absoluutselt järjestatud. Ei ole midagi kohatu. See on huvitav, see algoritm, kui ma liikuda järgmisse etappi. 

Nüüd on mul üks. Nii üks muidugi kuulub hetkel alguses või lõpus uue nimekirja? Algus. Nii et ma pean tegema mõned tööd nüüd. Olen võtnud mõned vabadusi minu marker lihtsalt joonistus asju kus ma tahan neid, kuid see ei ole tõesti täpne arvutis. Arvuti, nagu me teame, on RAM või Random Access Memory, ja see on üks bait ja teine ​​bait ja teise baidi. Ja kui sul on GB RAM, teil on miljard baiti, kuid nad füüsiliselt ühes kohas. Sa ei saa lihtsalt liikuda kraami ümber juhtides seda laual kus iganes soovite. Nii et kui minu uue nimekirja neljas kohas mälus Kahjuks neli on juba vales kohas. 

Nii et sisestada number üks Ma ei saa lihtsalt teha siit. See mälu asukohta ei eksisteeri. See oleks petmine, ja ma olen olnud petmine piltlikult mõne minuti siin. Nii et tõesti, kui ma tahan panna ühte siin, Mul on ajutiselt kopeerida neli ja siis pane kedagi. 

See on hea, see on õige, see on tehniliselt võimalik, aga aru, et see lisatööd. Ma ei ole lihtsalt pane number kohas. Ma esimest pidi liikuma number, siis pane see koht, nii et ma mingi kahekordistunud minu töö hulka. Nii et hoidke seda silmas pidades. 

Aga ma olen nüüd teinud selle elemendi. Nüüd ma tahan haarata number kolm. Kui muidugi see kuulub? Vahel. Ma ei saa petta enam ja lihtsalt panna sinna, sest jällegi seda mälu on füüsilist asukohta. Nii et ma pean kopeerima neli ja pane kolme siin. Ei ole suur asi. See on lihtsalt üks lisatööd again-- tundub väga odav. 

Aga nüüd ma liikuda kaks. Kaks muidugi kuulub siia. Nüüd hakkate näha, kuidas töö saab kuhjuma. Mida ma nüüd tegema pean? Jah, mul on liikuda neli, Siis on kopeerida kolm, ja nüüd ma ei sisesta kaks. Ja saagi seda algoritm, huvitaval kombel on, et oletame, et meil on rohkem äärmuslikke Juhul, kui see on oletame kaheksa, seitse, kuue, viie, nelja, kolm, kaks, üks. See on paljudel kontekstides Halvimal juhul, sest paganama asi on sõna otseses mõttes tagurpidi. 

See ei ole tegelikult mõjutada Ben algoritm, sest Ben valikut Sorteeri ta läheb, et hoida läheb edasi ja tagasi läbi nimekirja. Ja kuna ta oli alati otsinud läbi kogu ülejäänud nimekirja, see ei ole oluline kus elemendid on. Aga sel juhul minu sisestamine approach-- proovime seda. 

Nii üks, kaks, kolm, neli, viis, kuus, seitse, kaheksa. Üks kaks kolm neli, viis, kuus, seitse, kaheksa. Ma lähen võtma kaheksa, ja kus ma pane see? Noh, alguses minu nimekirja, kuna selle uue nimekirja sorteeritakse. Ja ma ületada seda. 

Kust ma panin seitse? Paganama ta. See vajab sinna minna, nii et Mul on teha mõned kopeerimist. Ja nüüd seitse läheb siia. Nüüd ma liikuda kuus. Nüüd on isegi rohkem tööd. 

Kaheksa on minna siin. Seitse on minna siin. Nüüd kuue võib minna siin. Nüüd ma haarata viis. Nüüd kaheksast peab minema siin seitse on minna siin, kuus on minna siin, ja nüüd viie ja korrata. Ja ma olen päris palju liigutades seda pidevalt. 

Nii lõpus, see algorithm-- jagame nimetame seda sisestamise sort-- tegelikult on palju tööd ka. See on lihtsalt erinevad sellist tööd, kui Ben. Ben töö oli mulle läheb edasi-tagasi kogu aeg, valides järgmise väikseim element ja jälle. Nii et see oli see väga visuaalne töö. 

See teine ​​algoritm, mis on endiselt correct-- ta saab selle töökoha done-- lihtsalt muudab töö mahtu. Tundub, et esialgu sa oled kokkuhoid, sest sa oled lihtsalt tegelevad iga element kuni ees ilma kõndides kõik Muide nimekiri läbi nagu Ben oli. Probleem on aga selles, eriti nendes hull juhul, kui see on kõik tagurpidi sa oled lihtsalt selline edasilükkamine tööd kuni teil määrata oma vigu. 

Ja kui te võite ette kujutada seda kaheksa ja seitse ja kuus ja viis ja hiljem neli ja kolm ja kaks liigub oma teed läbi nimekirja, oleme lihtsalt muutnud töö liik me teeme. Selle asemel, et seda teevad juures alguses minu korduse Ma lihtsalt teen seda kell lõpus iga iteratsiooni. Nii selgub, et see algoritm, Ka üldiselt nimetatakse sisestamise sorteerida, Samuti on suurusjärgus n ruudus. See on tegelikult midagi paremat, no parem üldse. 

Kuid seal on kolmas lähenemisviis Tahaksin julgustada meid kaaluma, mis on see. Nii oletame minu nimekirja, lihtsuse jällegi neli, üks, kolm, two-- vaid neli numbrit. Ben oli hea intuitsioon, hea inimese intuitsioon enne, mille me fikseeritud kogu nimekirja eventually-- sisestamise omamoodi. Ma coaxed meist mööda. Aga Vaatleme Lihtsaim viis probleemi nimekirja. 

See loetelu ei ole järjestatud. Miks? Inglise keeles, miks see ei ole tegelikult järjestatud. Mis see tähendab mitte sorteerida? 

Üliõpilane: See ei ole järjestikune. 

DAVID Humala: Mitte järjestikune. Anna mulle üks näide. 

Üliõpilane: Pane järjekorras. 

DAVID Humala: OK. Anna mulle rohkem konkreetse näite. 

Üliõpilane: Kasvav järjekord. DAVID Humala: Mitte tõusvas järjekorras. Ole täpsem. Ma ei tea, mida te mõtlete kasvavalt. Mis viga? 

Üliõpilane: Väikseim numbrid ei ole esimeses ruumis. 

DAVID Humala Väikseim number on mitte esimesest ruumi. Olla täpsem. Ma olen hakanud saaki. Me arvestame, kuid Mis rikkis siin? 

Üliõpilane: numbriline jada. DAVID Humala: numbriline jada. Igaühe selline pidamine see siin-- väga kõrgel tasemel. Lihtsalt sõna otseses mõttes mulle öelda, mis on vale nagu viie-aastane võiks. 

Üliõpilane: pluss üks. 

DAVID Humala: Mis see on? 

Üliõpilane: pluss üks. 

DAVID Humala: Mida sa mõtled pluss üks? Anna mulle erinevas viie-aastane. Mis viga, ema? Mis viga, isa? Mida sa mõtled seda ei järjestatud? 

Üliõpilane: See ei ole õige koht. 

DAVID Humala: Mis ei õiges kohas? 

Üliõpilane: Neli. DAVID Humala: OK, hea. Nii neli ei ole, kus see peaks olema. Eelkõige on see õige? Neli ja üks esimene kaks numbrit näen. See õigus? Ei, nad on rikkis, eks? Tegelikult arvan, et nüüd umbes arvuti ka. Seda saab vaadata ainult võibolla üks, võibolla kahte asja once-- ja tegelikult ainult üks asi korraga, kuid see võib vähemalt vaata üks asi siis Järgmine asi õige kõrval. 

Nii on need, et? Muidugi mitte. Nii et sa tead, mida? Miks me ei võta laps samme selle probleemi lahendamisega selle asemel, et teeme need väljamõeldud algoritme nagu Ben, kus Ta on omamoodi millega see silmukoiminen läbi nimekirja selle asemel, et seda, mida ma tegin, kus Ma lihtsalt mingi fikseeritud see, kui me minna? Ütleme nii sõna otseses mõttes murda mõiste order-- numbrilises järjekorras nimetame seda mida iganes sa want-- neisse paarikaupa võrdlusi. 

Neli ja üks. Kas see on õige, et? Nii saab määrata, et. Üks neli, ja seejärel me lihtsalt kopeerida seda. Olgu, hea. I fikseeritud üks kuni neli. Kolm ja kaks? Ei. Lase mu sõnad sobivad minu sõrmed. Neli ja kolm? 

See ei ole, et, nii et ma lähen teha ühte, kolm, neli, kaks. Hästi. Nüüd neli ja kaks? Meil on vaja kindlaks määrata ka see. Nii üks, kolm, kaks, neli. Nii on see järjestatud? Ei, aga see on lähemal järjestatud? 

On, sest me fikseeritud käesoleva viga, me fikseeritud see viga, ja me fikseeritud see viga. Nii et me fikseeritud kolm vigu väidetavalt. Ikka ei ole tegelikult otsima sorteeritud, kuid see on objektiivselt lähemale sorteeritud sest meil fikseeritud mõned neist vigu. 

Mida ma nüüd edasi tegema? I tüüpi jõudnud lõpuks nimekiri. Ma tundus, et on fikseeritud kõik vead, aga ei. Kuna antud juhul mõned numbrid võis mullidena lähemale teiste numbreid veel rikkis. Nii teeme seda uuesti, ja ma just seda paika seekord. Üks ja kolm? Kõik on korras. Kolm ja kaks? Muidugi ei ole, nii et vaatame seda muuta. Nii kaks, kolm. Kolm ja neli? Ja nüüd lähme lihtsalt eriti pedantne siin. Kas see on järjestatud? Sa inimestel tean, et see järjestatud. 

Uuesti proovida. Nii Olivia ettepaneku ma proovige uuesti. Miks? Kuna arvuti ei ole luksus meie inimeste silmad lihtsalt riivav back-- OK, ma olen teinud. Kuidas arvuti kindlaks et nimekiri on nüüd järjestatud? Mehaaniliselt. 

Ma peaks läbi minema veelkord ja ainult siis I ei tee / leida vigu ma saan siis järeldada, nagu arvuti, eks, Me oled hea minna. Nii et üks ja kaks, kaks ja kolm, kolme ja nelja. Nüüd ma saan lõplikult öelda, see on sorteeritud, sest ma ei teinud muutusi. Nüüd oleks viga ja lihtsalt rumal kui ma arvuti, küsis samu küsimusi uuesti ootab erinevaid vastuseid. Ei tohiks juhtuda. 

Ja nii nüüd nimekirja sorteeritakse. Kahjuks sõiduaega See algoritm on ka n ruudus. Miks? Kuna teil on n numbrid, ja Halvimal juhul sa pead liikuma n numbrid n korda, sest sa pead edasi minema tagasi vaadata ja potentsiaalselt määrata Neid numbreid. Ja me saame teha rohkem ametliku analüüsi ka. 

Nii et see on kõik öelda, et me oleme võtnud kolm erinevat lähenemist, üks neist kohe intuitiivne Kohe Ben minu pakutud sisestamise Sorteeri selle ühe kus sa sellist unustada metsa puid esialgu. Aga siis, kui te võtate samm tagasi, voila, oleme probleemi sorteerimine mõiste. Nii et see on, julgen öelda, madalamal tasemel ehk kui mõned nende muude algoritme, kuid olgem näha, kui me ei saa visualiseerida Nende teel seda. 

Nii et see on mõne kena tarkvara, et keegi kirjutas kasutades värvilisi baarid, mis on kavatsevad teha järgmise meile. Igaüks neist baarid tähistab number. Pikem riba, seda suurem arvu, väiksema baari, väiksem arv. Nii ideaalis soovime kena püramiid kus see algab väike ja saab suur, ja see tähendaks, et Nende baarid on järjestatud. Nii et ma lähen edasi minna ja valida, Näiteks Ben algoritm first-- Valiksortimine. 

Ja pane tähele, mis ta teeb. See, kuidas nad on otsustanud visualiseerida seda algoritmi on see, et, nagu ma olin jalgsi läbi minu nimekirja, Selle programmi kõnnib läbi selle jadaga, rõhutades roosa igas number, et ta vaatab. Ja mis hakkab juhtuma just nüüd? 

Väikseim number, mis I või Ben leitud äkki saab liigutada loendi alguses. Ja teate, nad tegid Evict arvu, mis oli seal, ja see on täiesti korras. Ma ei hakka sellesse detailsus. Aga me peame et number kusagil nii me lihtsalt liikus see avatud koha, mis oli loodud. Nii et ma lähen kiirendada selle üles, sest vastasel juhul muutub väga tüütu kiiresti. Animatsioon speed-- seal me läheme. Nüüd sama põhimõte Olin kohaldades, aga sa saab hakata end algoritmi, kui te hakkab, ega näe seda veidi selgemalt. Ja see algoritm mõjub valides järgmise väikseim element, nii et sa lähed alustada vaata see ramp üles vasakule. Ja iga iteratsiooni, kui ma pakutud, see natuke vähem tööd. See ei pea minema nii tagasi vasakule nimekirja lõppu, sest see on juba tunneb neid on järjestatud. Seega selline tunne see on kiireneb, kuigi iga samm on võttes samal aja jooksul. Seal on lihtsalt vähem etappe jäänud. Ja nüüd saab selline tunne algoritm puhastamiseks lõpuks see, ja tõepoolest nüüd on järjestatud. 

Nii sisestamise sorteerida on kõik tehtud. Mul on vaja uuesti juhuslikult massiivi. Ja teate ma lihtsalt hoida juhuvaliku see, Võtame ühtlustamise Sama lähenemist sisestamise omamoodi. Lubage mul seda aeglustada siin. Alustame et üle. Stopp. 

Olgem vahele neli. Seal me läheme. Randomize nad massiivi. Ja siin me go-- sisestamise omamoodi. Esita. Pange tähele, et see tegeleb iga element tal tekib kohe, aga kui see kuulub vales kohas teate kõik tööd, mis peab juhtuma. Me peame nihkub rohkem ja mitu elementi, et teha ruumi üks, me tahame paika panna. 

Nii et me keskendudes vasakule nimekirja lõppu ainult. Märgata ei ole me isegi tundus at-- me ei ole esile toodud roosad midagi paremale. Me lihtsalt tegelevad probleeme, kui me minna, kuid me luua palju töötada ennast ikka. Ja kui me seda kiirendada nüüd kulgeda lõpuni, sellel on teistsugune tunne, et see tõepoolest. See on lihtsalt keskendudes vasakul lõpuni, kuid teed natuke rohkem tööd needed-- Selline silumiseks asju üle, millega asju, kuid tegelevad lõpuks koos iga element ühe korraga kuni saame the-- hästi, me kõik teame, kuidas see lõppeb, nii et see on natuke underwhelming ehk. 

Aga nimekiri väljatöötamiseni spoiler-- läheb välja sorteerida. Nii vaatame ühte viimane. Me ei saa lihtsalt praegu vahele. Me oleme peaaegu kohal. Kaks minna, üks minna. Ja voila. Suurepärane. 

Nüüd teeme ühe viimane, uuesti juhuvaliku koos Mullsortimine. Ja märkate siin, eriti kui ma aeglane see maha, see hoiab swooping läbi. Aga pane seda lihtsalt teeb paarikaupa comparisons-- omamoodi kohalikke lahendusi. Aga niipea, kui saame lõpuks nimekiri roosa, Mis läheb on korduda? Jah, see läheb pea alustada otsast peale, sest see ainult fikseeritud paarikaupa vigu. Ja mis võisid veel avaldunud teised. Ja kui sa seda kiirendada, saate näha, et palju nagu nimigi ütleb, väiksem elements-- või pigem suurem elements-- hakkavad mulksuma üles, kui soovite. Ja väiksemad elemendid on hakanud mull alla vasakul. Ja tõepoolest, see on omamoodi visuaalne efekt samuti. Ja nii see lõpuks viimistlus väga sarnaselt ka. 

Me ei pea elama selle konkreetse ühe. Lubage mul avada see nüüd ka. Seal on mõned muud Sortimisalgoritm maailmas, millest vähesed on püütud siin. Ja eriti õppijatele, kes ei ole tingimata visuaalset või matemaatilise, nagu tegime enne, saame seda teha ka audially Kui me seostame heli seda. Ja lihtsalt lõbu, siin on vähe erinevaid algoritme, ja üks neist eriti sa oled läheb teade nimetatakse "Mestimissortimine." 

See on tegelikult täiesti parem algoritm, nii et Mestimissortimine, üks need, mida sa parasjagu näha, ei ole järjekorras n ruudus. See on suurusjärgus n korda samamoodi n, mis on tegelikult väiksem ja seega kiiremini kui need teised kolm. Ja seal on paar teiste rumal need, mis me näeme. 

Nii et siin me läheme mõne heli. See on sisestamise sorteerida, nii et jälle see on lihtsalt tegemist elemendid kui nad tulevad. See on mull sorteerida, nii et see on pidades neid paari korraga. Ja jälle, suurim elemendid on vahustamine kuni tippu. 

Järgmisena Valiksortimine. See on Ben algoritm, kus jälle ta valides korduvalt Järgmise väikseim element. Ja jälle, nüüd saab tõesti kuulda, et see on kiirendades kuid ainult niivõrd, sest see teeb vähem töötada iga iteratsiooni. See on kiirem üks, Mestimissortimine, mis sorteerimine klastrite numbrid kokku ja siis ühendab neid. Nii look-- vasakul pool on juba järjestatud. 

Nüüd on sorteerimine paremal pool, ja Nüüd siis läheb neid kombineerida ühte. See on midagi, mida nimetatakse "Gnome omamoodi." Ja saab sellist näha, et see läheb edasi ja tagasi, millega tööd natuke siin ja seal enne, kui see toimub, siis uus töö. Ja see ongi kõik. On veel üks sort, mis on tõesti ainult akadeemilistel eesmärkidel, nn "loll omamoodi", mis võtab Oma andmete sorteerib ta juhuslikult, ja siis kontrollib, kui see on järjestatud. Ja kui see ei ole, see uuesti sorteerib see juhuslikult, kontrollib, kas see on järjestatud, ja kui ei kordub. Ja teoreetiliselt tõenäosuslikult Selle ülesande täidetud kuid pärast üsna natuke aega. See ei ole kõige tõhus algoritme. Nii tekib küsimusi nende Eelkõige algoritme või midagi seotud ka seal? 

Noh, nüüd kiusa peale mida kõik need read on, et ma olen joonistus ja mida ma olen eeldades arvuti saab teha all kapuuts. Ma väidan, et kõik need numbrid Hoian drawing-- nad vajavad, et saada salvestatud kusagil mälu. Me saame sellest mehest lahti nüüd ka. 

Nii tükk mälu on computer-- nii RAM DIMM on mida otsisime eile, dual inline mälu module-- näeb välja selline. Ja kõik need vähe must laastud on mõned baitide arvu, tavaliselt. Ja siis kulla sõrmed on nagu juhtmed, et ühendada see arvuti, ja roheline räni pardal on lihtsalt mis hoiab kõike koos. Mida see tegelikult tähendab? Kui ma sellist teha seda sama pilt, oletame lihtsuse et see DIMM, Dual mälumoodul, on üks gigabait mälu, gigabaidi mälu, mis on mitu baiti kokku? Üks gigabait on mitu baiti? Enamat. 1124 on kilo, 1000. Mega on miljon. Giga miljardit. 

Kas ma pikali? Kas me isegi lugeda etikett? See on tegelikult 128 gigabaiti, nii et see on rohkem. Aga me teeselda, et see on vaid üks gigabait. Nii et see tähendab seal miljardit baiti mälu minule või 8 miljardit bitti, kuid me ei kavatse rääkida nii baiti nüüd, edasi liikuma. 

Mida see tähendab, et see on Ühebaidiline see järjekordne bait, See on veel üks bait, ja kui me tõesti tahtsid olema konkreetsed oleks meil joonistada miljardit ruudukesed. Aga mida see tähendab? Noh, las ma suurendamiseks aastal selle pildi kohta. Kui mul on midagi, mis tundub niimoodi nüüd, et on neli baiti. 

Ja nii ma võiks panna neli numbrit siin. Üks kaks kolm neli. Või ma võiks panna neli tähte või sümbolit. "Hei!" võiks minna seal, sest iga tähed, Arutasime varem võiks olla esindatud Kaheksa bitti või ASCII või bait. Nii teisisõnu, saate panna 8 miljardit asjad sees Selle üks pulk mälu. Nüüd, mida see tähendab, et panna asju tagasi et seljad mälu niimoodi? See on see, mida programmeerija nimetaksime "massiivi." Arvutiprogrammi, siis ei usu selle aluseks oleva riistvara, per se. Sa mõtle ise, kellel juurdepääs miljard baiti kokku ja te saate midagi tahad sellega. Aga mugavamaks see on üldiselt kasulik hoida oma mälu õigus üksteise kõrval niimoodi. Nii et kui ma suumida see-- sest me kindlasti ei lähe tõmmata miljardit vähe squares-- oletame, et see esindab amet et pulk mälu nüüd. Ja ma lihtsalt teha nii palju kui minu marker jõuab andis mulle siin. Nüüd on meil kinni mälu laual et ju üks, kaks, kolm, neli, viis, kuue, üks, kaks, kolm, neli, viis, kuus, seven-- nii 42 baiti mälu ekraanil kokku. Aitäh. Jah, tegin aritmeetiline õigus. Nii 42 baiti mälu siin. Mida see tegelikult tähendab? Noh, programmeerija tegelikult üldiselt mõtle seda mälu adresseeritav. Teisisõnu, igaüks neist kohtades mälu, riistvara, on unikaalne aadress. 

See ei ole nii keeruline kui üks Brattle Square, Cambridge, Mass., 02138. Selle asemel, et see on lihtsalt number. See on bait number null, on see üks on see kaks, see on kolm, ja see on 41. Oota hetk. Ma arvasin, et ma ütlesin 42 hetk tagasi. Hakkasin nullist, nii see on tegelikult õige. Nüüd ei pea tegelikult joonistada ruudustik, ja kui te joonistada ruudustik Ma arvan, et asjad tegelikult natuke eksitav. Mis Programmeerija, tema enda meeles, üldiselt arvan sellest mälu on nagu lint, nagu tükk maalriteip et lihtsalt läheb ja igavesti või kuni sa otsa mälu. Nii palju levinum viis juhtida ja mõelge mälu Oleks, et see on bait null, üks, kaks, kolm, ja siis dot, dot, dot. Ja sul on 42 sellised baiti kokku, isegi Kuigi füüsiliselt võib see tegelikult olla midagi enamat niimoodi. 

Nii et kui te nüüd arvate teie mälu, kuna see, nagu lindi, See on see, mida programmeerija uuesti kutsuks hulga mälu. Ja kui sa tahad tegelikult salvestada midagi arvuti mälus, sa tavaliselt teha poest asju back-to-back to back-to-back. Nii oleme rääkinud numbrid. Ja kui ma tahtsin, et lahendada probleeme nagu neli, üks, kolm, kaks, kuigi ma just joonistus ainult numbrid neli, üks, kolm, kaks laual, arvuti oleks tõesti on see setup mälu. 

Ja mis oleks kõrval kaks arvuti mällu? Noh, ei ole vastust. Me tõesti ei tea. Ja nii kaua, kui arvuti ei vaja seda, see ei pea hooli, mis on järgmine numbritele see hoolivad. Ja kui ma ütlesin, et arvuti saab vaadata ainult ühel aadressil korraga See on selline, miks. 

Mitte erinevalt rekord mängija ja lugemispea ainult suuda vaadata teatud soon füüsilise vana kooli rekord korraga, sarnaselt Kas arvuti tänu oma CPU ja selle Intel käsustik hulgast, kelle juhendamise loetakse mälust või salvestada memory-- arvuti saab vaadata ainult ühes kohas kell AEG_ mõnikord nende kombinatsiooni, aga tõesti ainult ühes kohas korraga. Nii et kui me teeme Nende erinevate algoritmide Ma ei ole lihtsalt kirjalikult oma vacuum-- neli, üks, kolm, kaks. Need numbrid tegelikult kuuluvad kusagil füüsilist mälu. Seega on tilluke transistorid või mingi elektroonika all kapuutsi ladustamiseks neid väärtusi. 

Ja kokku, kui palju bitid seotud just nüüd, just olema selge? Nii et see on neli baiti, või nüüd on 32 bitti kokku. Nii on tegelikult 32 nullid ja need moodustavad need neli asja. Seal on isegi rohkem siin, kuid jälle me ei hooli sellest. 

Vaatame nüüd küsida teise küsimus mälust, sest et lõpus päeval on vastuolus. Ükskõik, mida me võiksime teha arvuti, lõpus päeval riistvara on ikka Sama all kapuuts. Kuidas ma Hoida sõna siin? Noh, sõna arvuti nagu "Hei!" oleks salvestatud lihtsalt niimoodi. Ja kui sa tahad pikemat Ühesõnaga, saate lihtsalt kirjutatakse seda ja öelda midagi nagu "tere" ja pood siin. 

Ja nii ka siin see contiguousness on tegelikult ära, sest arvuti saab lihtsalt lugeda paremalt vasakule. Aga siin on küsimus. Seoses selle sõna h-e-L-l-o, hüüumärk, kuidas võiks arvuti tea, kus Sõna algab ja kus sõna lõpeb? Seoses numbrid, Kuidas arvuti tea, kui kaua jada numbrid on või kus see algab? Noh, selgub out-- ja me ei lähe liiga palju sellesse tase detail-- arvutid liikuda kraami ringi mälu sõna otseses mõttes teel need aadressid. Nii arvuti, kui sa oled kirjalikult koodi salvestada asju nagu sõnad, mida sa tõesti teevad kirjutab väljendeid mäletavad, kus on arvuti mällu need sõnad on. Nii et lubage mul teha väga, väga lihtsa näite. 

Ma lähen edasi minna ja avada lihtsa teksti programmi ja ma lähen, et luua fail nimega hello.c. Suurem osa sellest informatsioonist, mida me ei hakka väga täpselt, aga ma lähen kirjutada Programm samas keeles, C. See on palju rohkem hirmutav, Ma väidan, kui Scratch, aga see on väga sarnase sisuga. Tegelikult need lokkis braces-- saate liiki mõelda, mida ma tegin, sest see. 

Teeme seda tegelikult. Kui roheline lipp klõpsates teha järgmist. Ma tahan välja printida "tere." Nii et see on nüüd pseudokoodi. Ma olen selline hägustumas jooned. In C, selles keeles Ma räägin umbes, see rida print tere tegelikult muutub "printf" koos mõned sulud ja semikooloniga. 

Aga see on täpselt sama mõte. Ja seda väga kasutajasõbralik "Kui roheline lipp klõpsatud" muutub märksa kauge "int main void." Ja see on tõesti ei ole kaardistamine, nii et ma lihtsalt lähen ignoreerida seda. Aga looksulg on nagu kaardus puzzle tükki niimoodi. 

Nii saab mingi arvata. Isegi kui sa pole kunagi programmeeritud enne, Mida see programm ilmselt teha? Tõenäoliselt prindib tere hüüumärk. 

Nii proovime seda. Ma lähen seda salvestada. Ja see on jällegi väga vana kooli keskkonnas. Ma ei saa klõpsata, ma ei saa tõmmata. Ma pean käske. Ma tahan joosta minu programmi, nii et Ma võiks seda teha, nagu hello.c. See fail jooksin. Aga oota, ma puudu samm. Mida me ütleme, on vaja samm keeles nagu C? Ma olen lihtsalt kirjutatud allikas koodi, aga mida ma vajan? Jah, mul on vaja koostaja. Nii minu Mac siin, mul on programmi nimega GCC GNU C kompilaator, mis võimaldab mul teha see-- omakorda minu lähtekoodi, me nimetame seda, masinkoodi. 

Ja ma näen, et jälle järgmiselt need on ühtede ja nullide ma lihtsalt loodud minu lähtekoodi kõik ühtede ja nullide. Ja kui ma jooksen minu program-- see juhtub mida nimetatakse a.out eest ajalooline reasons-- "tere." Ma saan käivitada uuesti. Tere, tere, tere. Ja tundub toimivat. 

Aga see tähendab, et kuskil minu Arvuti mälu on sõnad h-e-L-l-o, hüüumärk. Ja selgub, niisama kõrvale, Mis arvuti on tavaliselt seda, et ta teab, kus asjad hakkavad ja väljatöötamiseni see panen eriline sümbol siin. Ja konventsiooni eesmärk on panna number null lõpus sõna nii et sa tead, kus see tegelikult lõpeb, nii et sa ei hoia väljatrükk rohkem tegelased kui sa tegelikult kavatsevad. 

Aga Buffee siin, isegi kuigi see on üsna kauge, on, et see lõpuks suhteliselt lihtne. Sa said omamoodi lint, tühja ruumi, kus saab kirjutada kirju. Sa lihtsalt pead olema erisümboliga nagu suvaliselt number null, panna lõpus oma sõnu nii, et arvuti teab, oh, ma peaksin lõpetama printimist pärast Näen hüüumärk. Kuna järgmine asi seal on ASCII väärtus null, või null iseloomu keegi oleks seda nimetada. Aga seal on mingi probleem siin, ja olgem siis tagasi Numbrite hetkeks. Oletame, et ma tegelikult on massiivi numbrid, ja oletame, et Programm Ma kirjutan on nagu klass raamat õpetaja ja õpetajad klassiruumis. Ja see programm võimaldab tal kirjuta oma õpilaste hinded kohta viktoriine. Ja oletame, et üliõpilane saab 100 oma esimesele viktoriin, võibolla nagu 80 järgmise üks, siis 75, siis 90 neljanda viktoriini. 

Nii siinkohal lugu, massiiv on suuruse neli. Seal on absoluutselt rohkem mälu arvuti, kuid massiiv, nii et rääkida, on suurus neli. Oletame nüüd, et õpetaja tahab määrata viiendiku viktoriin klassis. Noh, üks asju, mida ta või ta läheb tegema Nüüd on hoida lisaväärtust siin. Aga kui massiivi õpetajal on loodud see programm on suurus, üks probleem array on see, et sa ei saa lihtsalt hoida lisades mälu. Sest mis siis, kui teine ​​osa Programm on sõna "hei" seal? 

Teisisõnu, mu mälu võib olla kasutatakse millegi programmi. Ja kui enne ma kirjutada, hei, Ma tahan, et sisestada neli viktoriini skoorid, nad võivad minna siin ja siin. Ja kui sa äkki meelt muuta hiljem ja öelda, et ma tahan viiendiku viktoriin skoor, sa ei saa lihtsalt pane see kus iganes soovite, sest mis siis, kui see mälu on kasutusel midagi else-- mõne muu programmi või mõni muu element programmis et sa kasutad? Nii et sa pead mõtlema enne kuidas soovite salvestada oma andmeid, sest nüüd olete värvitud ise digitaalseks nurgas. 

Nii võib õpetaja asemel öelda, kui kirjalikult programmi salvestada tema klassid, tead mis? Ma küsida, kirjutamise ajal oma programm, et ma tahan null, üks, kaks, kolm, nelja, viie, kuue, kaheksa klassid kokku. Nii üks, kaks, kolm, neli, viis, kuus, seitse, kaheksa. Õpetaja võib lihtsalt üle jaotada mälu, kui kirjalikult oma programmi ja öelda, et tead, mida? Ma ei kavatse määrata rohkem kui kaheksa viktoriinid semestris. See on lihtsalt hull. Ma ei saa kunagi eraldada seda. Nii et sel viisil ta on paindlikkust poest õpilase hinded, nagu 75, 90, ja võib-olla üks ekstra kus õpilane sai lisapunkte, 105. 

Aga kui õpetaja kunagi kasutab neid kolme ruumid, seal on intuitiivne Buffee siin. Ta on lihtsalt raiskab ruumi. Nii teisisõnu, seal on see ühise Miinuseks programmeerimine kus saab kas eraldada täpselt nii palju mälu, kui soovite, tagurpidi, mis seisneb selles, et sa oled super efficient-- et sa ei ole raiskav kell all-- kuid negatiivseid millest ongi, kui muudad oma meelt, kui kasutades programmi, mida soovite salvestada rohkem andmeid, kui sa algselt mõeldud. 

Ehk lahendus on, siis kirjuta oma programmides nii et nad kasutavad rohkem mälu kui nad tegelikult vajavad. Nii sa ei kavatse joosta, et probleem, Aga Sa oled raiskav. Ja mida rohkem mälu oma programm kasutab, kui me arutasime eile, seda vähem mälu, mis on saadaval teisi programme, varem arvuti võib aeglustada alla, sest virtuaalmälu. Ja nii ideaalne lahendus võiks olla see, mida? 

Vastavalt jaotada tundub halb. Üle jaotada tundub halb. Mis võiks olla parem lahendus? Ümberjaotamine. Ole dünaamilisemaks. Ärge suruge ennast valida priori alguses, mida sa tahad. Ja kindlasti ei üle jaotada, muidu sa raiskamine. 

Ja nii, et selle eesmärgi saavutamiseks oleme vaja visata andmete struktuuri, nii-öelda ära. Ja mis siis programmeerija tüüpiliselt kasutada on midagi, mida nimetatakse mitte massiivi kuid ahelloend. Teisisõnu, ta saab hakata mõtlema oma mälu nagu oleks mingi kuju, et nad saab juhtida järgmisel viisil. Kui ma tahan salvestada ühe numbri program-- nii et see on septembril Ma olen andnud oma õpilastele viktoriin; tahan salvestada õpilaste esimesele viktoriin, ja nad said 100 see-- ma küsin minu arvuti, teel programm Olen kirjutatud, ühe tüki mälu. Ja ma lähen salvestada number 100, ja ongi kõik. 

Siis paar nädalat hiljem kui ma saan teist viktoriin, ja see on aeg, et sisestada et 90%, ma lähen küsida arvuti, hei, arvuti, saan teise patakas mälu? See läheb mulle seda tühja patakas mälu. Ma panen arvu 90, kuid minu programmi kuidagi või other-- ja me ei pea muretsema süntaks see-- vajan kuidagi kett need asjad kokku. Ja ma kett neile koos mis näeb välja nagu nool siin. 

Kolmas viktoriin, mis kerkib, Ma lähen öelda, hei, arvuti, anna mulle veel patakas mälu. Ja ma lähen panema mis iganes see oli, nagu 75, ja ma pean kett seda koos nüüd kuidagi. Neljas viktoriin jõuab mööda, ja võib-olla see on poole semestri lõpuks. Ja selles punktis oma programmi Võib olla kasutades mälu kõikjal, üle kogu füüsiliselt. Ja nii lihtsalt peksab, ma olen läheb juhtida seda edasi quiz-- ma unustan, mis see oli; mina arvan, võibolla 80 või midagi-- kuidas siin. 

Aga see on hea, sest piltlikult Ma lähen juhtida seda joont. Teisisõnu, et tegelikkuses arvuti riistvara, esimene tulemus võiks lõpuks siin, sest see on kohe alguses poolaastal. Järgmise üks sattuda siin sest natuke aega on möödas ja programm peab näitama. Järgmine tulemus, mis oli 75, võib olla siin. Ja viimane tulemus võib olla 80, mis on siin. 

Nii et tegelikkuses füüsiliselt, see võib olla mida teie arvuti mälu välja näeb. Kuid see ei ole kasulik vaimse paradigma programmeerija. Miks peaks sul kus Heck oma andmed jõuavad? Sa tahad salvestada andmeid. 

See on selline nagu meie arutelu varem joonistamise kuubik. Miks sa huvita, mida nurk on kuubik ja kuidas teil pöörduda joonistada? Sa tahad kuubik. Samamoodi siin, siis tahan hinne raamat. Sa tahad mõelda seda nimekirja numbrid. Keda huvitab, kuidas see rakendatakse riistvara? 

Nii võtmiseks nüüd on see pilt siin. See on seotud nimekirja, kuna programmeerija oleks seda nimetada, kuivõrd teil on nimekirja, ilmselt numbreid. Aga see on seotud piltlikult teel Nende nooled, ja kõik need nooled are-- all kapuutsi, kui sa oled uudishimulik, Tuletame meelde, et meie füüsilise riistvara on aadressid null, üks, kaks, kolm, neli. Kõik need nooled on on nagu kaart või suundades, kus kui 90 on-- nüüd Sain loota. 

Null, üks, kaks, kolm, nelja, viie, kuue, seitsme. Tundub, et 90 on mälu aadressi number seitse. Kõik need nooled on on nagu väike paberiribad mis on andes suunad programm, mis ütleb, järgige selle kaardiga saada asukohta seitse. Ja seal leiad õpilane teise viktoriini tulemus. Vahepeal 75-- kui ma jätkuvalt seda, see on seitse, kaheksa, üheksa, 10, 11, 12, 13, 14, 15. 

See teine ​​nool lihtsalt esindab kaart, mäluasukoha 15. Aga jälle, programmeerija üldjuhul ei ei hooli sellest detailsus. Ja kõige iga programmeerimine keelt täna, programmeerija isegi ei tea, kus mälu need numbrid tegelikult on. Kõik on tal hoolivad on et nad on mingil viisil omavahel seotud andmestruktuur niimoodi. 

Selgub aga mitte saada liiga tehniline. Aga kuna me saame olla endale lubada seda arutelu siin, Oletame, et meil vaadata Selle probleemi siin massiivi. Vaatame, kas meil on kahju, läheb siin. See on 100, 90, 75, ja 80. 

Lubage mul lühidalt teha selle nõude. See on massiiv, ja jälle väljapaistev iseloomulik massiivi on see, et kõik andmed on tagasi seljad in memory-- sõna otseses mõttes üks bait või hoopis neli baiti, mõned fikseeritud baitide arv kaugusel. Ühes seotud nimekirja, mida võiksime teha niimoodi, all kapuuts, kes teab, kus see kraam on? See ei pea isegi voolu niimoodi. Mõned andmed võivad olla ka tagasi vasakule seal. Sa ei tea isegi. 

Ja nii array, teil on funktsioon tuntud muutmälu. Ja mis muutmälu vahendid on et arvuti saab hüpata koheselt kõikjale massiivi. Miks? Kuna arvuti teab et esimene asukoht on null, üks, kaks, ja kolm. 

Ja kui sa tahad minna Selle elemendi järgmisele element, sa sõna otseses mõttes, et arvuti meeles, lihtsalt lisage esimene kommentaar. Kui soovite minna kolmas element, lihtsalt lisada one-- järgmine element, vaid lisage esimene kommentaar. Kuid selles versioonis lugu oletame arvuti on praegu otsin kell või tegelevad number 100. Kuidas sa saad järgmisele klassi klassi raamat? 

Sa pead võtma seitse samme, mis on meelevaldne. Et saada järgmise üks, sa pead võtab veel kaheksa sammu, et saada 15. Teisisõnu, see ei ole konstantne lõhet numbrid, ja nii see lihtsalt võtab Arvuti rohkem aega mõtet. Arvutil on otsida läbi mälu, et leida, mida te otsite. 

Nii arvestades massiivi kipub olema kiire andmeside structure-- sest sa võib sõna otseses mõttes lihtsalt teha lihtsa aritmeetilise ja saada kuhu tahad, lisades ühe, jaoks instance-- ahelloend, sa ohverdama, et funktsioon. Sa ei saa lihtsalt minna esimest et teiselt kolmandale neljandale. Sa pead järgima kaardil. Sa pead võtma rohkem samme saada need väärtused, mis tundub olevat lisades kulu. Nii et me maksab ka, aga mis oli funktsioon, mis Dan otsis siin? Mida ahelloend ilmselt võimaldab meil teha, mis oli päritolu see konkreetne lugu? 

Täpselt. Dünaamiline suurus ta. Me võime lisada sellesse nimekirja. Me isegi kahaneb nimekirja, nii et et me ainult kasutades nii palju mälu nagu me tegelikult tahame ja nii me kunagi üle jaotada. 

Nüüd lihtsalt olla tõesti tobu valiv, seal on varjatud kulud. Nii et sa ei tohiks lihtsalt lase mul veenda teile, et see on mõjuv Miinuseks. On veel üks varjatud kulusid siin. Kasu, et oleks selge, on see, et me saame dünaamikat. Kui ma tahan veel üks element, ma lihtsalt joonistada ja pani number seal. Ja siis ma saan siduda see koos pilti siin samas siin jälle, kui ma olen värvitud ennast nurka, kui midagi muud juba kasutab mälu siin, ma olen läbi õnne. Olen värvitud ennast nurka. 

Aga mis on peidetud maksab see pilt? See ei ole lihtsalt summa aega, mis kulub minna siit siiani, mis on seitse sammu, siis kaheksa astet, mis on rohkem kui üks. Mis on veel üks varjatud kulusid? Mitte lihtsalt aega. Lisainfot selle eesmärgi saavutamiseks vajalik pilt. 

Jah, see kaart, need väikesed sissekannet paberi, nagu ma hoida kirjeldavad neid. Need arrows-- need ei ole vabad. Computer-- tead mida arvutil on. See on ühtede ja nullide. Kui soovite esindavad nool või map või mitu, teil on vaja mõned mälu. Nii teine ​​hind, mida maksma ahelloend, ühine infotehnoloogia ressurss, on ka ruumi. 

Ja tõepoolest nii, nii tavaliselt, hulgast kompromissidega kavandamisel tarkvaratehnika süsteemid on aega ja space-- On kaks oma koostisosade, kaks oma kõige kallima koostisosi. See maksab mulle rohkem aega sest mul on jälgida seda kaardil aga see on ka maksab mulle rohkem ruumi sest mul on hoida selle kaardi ümber. Nii et lootust, kui me oleme omamoodi arutati üle eile ja täna on see, et kasu kaalub üles kulud. 

Aga seal ei ilmne lahendus siin. Võib-olla on better-- a la kiire ja määrdunud, nagu Kareem pakutud earlier-- visata mälu probleem. Lihtsalt osta rohkem mälu, arvan vähem kõvasti probleemi lahendamisel, ja lahendada seda lihtsam viis. Ja tõepoolest varem, kui me rääkisime kompromissidega, see ei olnud ruumi arvuti ja aega. See oli arendaja aega, mis On veel üks ressurss. 

Nii jälle, see on see tasakaal püüavad otsustada, milline neist asjadest kas te olete nõus kulutama? Milline on kõige kallim? Mis annab paremaid tulemusi? Jah? 

Tõepoolest. Sel juhul, kui sa oled esindavad numbrid maps-- nimetatakse neid paljudes keeltes "Osuti" või "aadressid" - see on topelt ruumi. See ei pea olema nii halb, kui topelt, kui kohe me lihtsalt ladustamiseks numbrid. Oletame, et me talletame Patsient dokumendikogumid hospital-- nii Pierson nimed, telefoninumbrid, sotsiaalkindlustuse numbrid, arst ajaloos. See kast võiks olla palju, palju suurem, mispuhul tilluke pointer, aadress Järgmise element-- see ei ole suur asi. See on nii erisoodustuse hind ei ole oluline. Aga sel juhul, jah, see on kahekordistamist. Hea küsimus. 

Räägime korda vähe konkreetsemalt. Mis sõiduaega otsides seda nimekirja? Oletame, tahtsin otsida läbi kõik õpilaste klassid, ja seal on n klassid Selles andmestruktuur. Siingi saame laenata sõnavara varem. See on lineaarne andmestruktuur. 

Big O n on, milline on vajalik saada lõpuni käesoleva andmestruktuur, whereas-- ja me ei ole näinud See before-- massiivi annab teile mida nimetatakse konstantset aega, mis tähendab, üks samm või kaks sammu või 10 steps-- Ei ole oluline. See on kindel arv. See on midagi pistmist suurusest massiivist. Ja põhjus, et jälle on muutmälu. Arvuti saab lihtsalt kohe hüpata ühest kohast teise, sest nad on kõik ühesugused kaugusele kõike muud. Ei ole mõtlemine seotud. Hästi. Nii et kui suudan, las ma proovida värvida kaks viimast pilti. Väga levinud üks tuntud hash tabelis. Nii et motiveerida Selle arutelu las ma mõtlen, kuidas seda teha. 

Niisiis, kuidas see on? Oletame, et probleem me tahame lahendada nüüd rakendab oma dictionary-- nii terve hulk inglise sõnad või mis iganes. Ja eesmärgiks on olla võimeline vastama küsimuste näol on see sõna? Nii et sa tahad ellu õigekirjakontrolli, lihtsalt nagu füüsilise sõnastik et saad vaadata asju üles. Oletame, ma oleks seda teha koos hulga. Ma ei suutnud seda teha. 

Ja oletame, et sõnad on õun ja banaan ja melon. Ja ma ei saa mõelda puuviljad mis algavad d, nii et me oleme lihtsalt läheb on kolm puuviljad. Nii et see on maatriks, ja me oleme säilitada kogu nende sõnade Selles sõnaraamatus massiiv. Küsimus on siis, kuidas muidu sa võisid seda teavet säilitada? 

Noh, ma olen selline petmine siin, sest kõik need tähed sõna on tõesti individuaalne bait. Nii et kui ma tõesti tahtsin olla ting-valiv, ma tõesti olla jagades selle üles võetud palju väikesteks tükkideks mälu ja me võime teha just nii. Aga me ei kavatse joosta sama probleem nagu enne. Mis siis, kui nagu Merriam Webster või Oxford teeb iga year-- nad lisavad sõnad kuni dictionary-- me ei tingimata soovite värvi ise nurka array? 

Nii et selle asemel, võib-olla targem lähenemine on panna õuna oma sõlme või kast kui me ütleks, banaan, ja siis siin on meil cantaloupe. Ja me string need asjad kokku. Nii et see on massiiv, ja see on seotud nimekirja. Kui te ei ole päris näha, see lihtsalt ütleb "massiiv" ja see ütleb "nimekirja." 

Nii et meil on sama täpse küsimusi nagu enne, kusjuures meil on nüüd dünaamikat meie ahelloendid. Aga meil on suhteliselt aeglane sõnastik. Oletame, ma tahan otsida sõna. See võib võtta mulle suur O n samme, sest sõna võiks olla kogu tee lõpus nimekirjas, nagu melon. Ja selgub, et programmeerimine, omamoodi Püha Graal andmeid struktuure, on midagi mis annab teile pideva aega nagu massiivi kuid see annab ikkagi dünaamikat. 

Nii saame olla parim nii maailmad? Ja tõepoolest, seal on midagi nimetatakse hash tabelis mis võimaldab teil teha just et ehkki umbes. Hash tabelis on Kasvataja andmestruktuur, et me ei mõtle nagu kombinatsiooni array-- ja ma lähen joonistada nagu see-- ja ahelloendid et ma joonistan, nagu see siin. 

Ja kuidas see asi teoste on järgmine. Kui see now-- hash table-- on minu kolmas andmestruktuur, ja ma tahan hoida sõnu, ma ei ole tahan lihtsalt salvestada kõik sõnad seljad et seljad. Ma tahan ära mõned tükk info sõnade kohta, mis võimaldab ma saan seda, kui see on kiirem. 

Nii antakse sõna õun ja banaan ja melon, Valisin teadlikult neid sõnu. Miks? Mis on omamoodi fundamentaalselt erinevates umbes kolm? Mis on ilmne? Nad hakkavad erinevate tähtedega. 

Nii et sa tead, mida? Selle asemel, et panna kõik oma sõnad sama kopp, nii et rääkida, nagu üks suur nimekiri, miks mitte Ma vähemalt proovida optimeerimise ja teha oma nimekirjad 1/26 nii kaua. Meelitav optimeerimine Võib olla, miks mitte I-- sisestamisel sõna sellesse andmestruktuur, arvesse arvuti mällu, miks ma ei pane kõiki "a" sõnadega siin, kõiki "b" sõnadega siin, ja kõik "c" sõnadega siin? Nii et see jõuab panna õuna siin, banaan siin, melon siin ja nii edasi. 

Ja kui mul on veel Sõna like-- mida on veel? Apple, banaan, pirn. Igaüks mõelda puu mis algab a, b, või c? Blueberry-- täiuslik. See läheb lõpuks siin. Ja nii me tundub, et on natuke parem lahendus, sest nüüd, kui ma tahan otsida õun, ma first-- Ma ei ole lihtsalt sukelduda minu andmete struktuuri. Ma ei sukelduda minu arvuti mällu. Ma esimene pilk esimene täht. 

Ja see on see, mida arvuti teadlane ütleks. Sa hash oma andmete struktuuri. Sa võta oma panus, mis Sel juhul on sõna nagu õun. Sa seda analüüsida, vaadeldes esitäht sel juhul, seeläbi ülessulamise ta. Tärkimine on üldine termin, millega te võtate midagi sisendina ja sa toota mõned väljund. Ja väljund, mis juhul on asukoht soovite otsida, esimene asukoht, teine ​​asukoht, kolmas. Nii sisend on õun, väljund on esimene. Sisend on banaan, on väljund peaks olema teine. Sisend on melon, väljund peaks olema kolmas. Sisend on mustika on väljund peaks jälle teine. Ja see on see, mis aitab teil võtta otseteed läbi oma mälu selleks, et saada sõna või andmete tõhusamalt. 

Nüüd on see kergendab meie aja potentsiaalselt nii palju kui üks 26st, sest kui sa eeldada, et sa on nii palju "a" sõnadega nagu "z" sõnad nagu "q" sõnad, mis ei ole tõesti realistic-- sa lähed on viltune üle teatud tähed alphabet-- kuid see oleks lisanduvate lähenemisviisi, mis ei võimalda sa saada sõnad palju kiiremini. Ja tegelikult keeruline Programmi Googles maailma Facebooks on world-- nad kasutavad hash tabelis jaoks palju erinevaid eesmärke. Aga nad ei oleks nii naiivne, nagu lihtsalt vaadata algustäht Apple või banaan või pirni või melon, sest nagu näete neid nimekirju oleks ikka pikk. 

Ja nii see võib siiski olla omamoodi ning linear-- nii omamoodi aeglane, nagu suurte O n et meil arutatud ka varem. Mis siis väga hea hash tabel do-- see on palju suurem massiiv. Ja ta kasutab palju kogenud segamist funktsiooni nii, et see ei ole lihtsalt vaadata "a." Võib-olla see vaatleb "a-p-p-l-e" ja kuidagi teisendab need viis tähte arvesse asukohta, kus Apple tuleb hoida. Me lihtsalt naiivselt kasutades täht "a" üksi, sest see on tore ja lihtne. 

Kuid hash tabelis asendatakse Lõpuks saab mõelda AS kombinatsioon massiivi, millest igaüks on seotud nimekirja, et ideaalis peaks olema nii lühike kui võimalik. Ja see ei ole ilmne lahendus. Tegelikult palju täpsustamisel et läheb all kapuuts, kui rakendatakse selliseid kogenud andmestruktuurid on see, mis on õige pikkus array? Mis on õige hash funktsiooni? Kuidas sa asju hoida mälu? 

Aga aru, kui kiiresti selline arutelu eskaleerunud, kas nii kaugele, et see on selline üle ühe pea sel hetkel, mis on hea. Aga me alustasime, mäletate, tõeliselt midagi madala ja elektrooniline. Ja nii see jälle on see teema võtmiseks, kus kord, kui hakkate kasutama eest antud, OK, mul see-- seal füüsiline mälu, Sain aru, iga füüsilist asukohta on aadress, OK, ma sain selle, ma ei esinda need aadressid arrows-- saab väga kiiresti hakkavad olema keerukamaid vestluste lõpuks tundub, et see võimaldab meil lahendada probleeme, nagu otsides ja sorteerimine tõhusamalt. Ja kindel, too-- sest ma arvan, et see on sügavaim oleme läinud mõned Nende CS teemasid proper-- me oleme teha päevas ja pool selles meelde, mida sa võib tavaliselt teha üle käigus kaheksa nädala jooksul semestri. 

Kõik küsimused on need? Ei? Hästi. Noh, miks me ei peatamiseks on olemas, alustada lõunasööki minutit varem, jätkata vaid umbes tund aega? Ja ma jõlkuma natuke küsimusi. Siis ma lähen minema võtta paar kõned, kui see on OK. Ma lülitage muusikat vahepeal kuid lõunasöök peaks olema ümber nurga.