DAVID MALAN: Bine. Ne-am intors. Deci, în acest segment de programare ce Am crezut că vom face este un amestec de lucruri. Unu, face un pic de ceva hands-on, deși folosind un mai jucaus environment-- programare una care este demonstrativ de exact genul de idei am vorbit despre, dar un pic mai mult formal. Doi, uita-te la unele dintre modalitățile mai tehnice că un programator ar rezolva de fapt probleme cum ar fi problema căutarea pe care ne-am uitat la mai înainte și De asemenea, o mai fundamental problemă interesantă de sortare. 

Tocmai ne-am asumat de a lua merge că această carte de telefon a fost sortate, dar că singur este de fapt un fel de problemă greu cu mai multe moduri diferite să-l rezolve. Așa că vom folosi acești o clasă de probleme reprezentativ pentru lucruri care ar putea fi rezolvată în general. Și apoi vom vorbi despre în detaliu ceea ce sunt numite date structures-- moduri, cum ar fi liste crescator legate și tabele de dispersie și copaci, care un programator ar fapt utilizează și în general, utilizați pe o tablă pentru a picta o imagine a ceea ce el sau ea prevede pentru punerea în aplicare a unele bucată de software. 

Așa că hai să facem mâinile-pe prima porțiune. Deci, a lua doar mâini murdare cu un mediu numit scratch.mit.edu. Acesta este un instrument pe care le folosim în clasa noastră de licență. Chiar dacă este proiectat pentru vârstele de 12 și în sus, l-am folosi pentru sus o parte din faptul că destul de un pic deoarece este un frumos, distractiv mod grafic de învățare un pic ceva despre programare. Așa că cap la acea adresă URL, în cazul în care vă ar trebui să vedeți o pagină destul ca acest lucru, și mergeți mai departe și faceți clic Alăturați-vă zero la dreapta sus și alege un nume de utilizator și o parola și în cele din urmă du-te un scratch.mit.edu account--. Am crezut că o să folosesc acest lucru ca oportunitate în primul rând pentru a arăta acest lucru. O întrebare a venit în timpul pauzei despre ce codul de fapt arată. Si am vorbit în timpul pauzei despre C, în particular un particular-- nivel inferior într-o limbă mai veche. Și tocmai am făcut-o rapid Căutarea Google pentru a găsi codul C pentru căutare binară, algoritmul pe care noi folosit pentru a căuta cartea de telefon mai devreme. Acest exemplu special, desigur, nu caută o carte de telefon. Ea doar caută un întreg buchet de Numerele din memoria calculatorului. Dar, dacă doriți să obțineți doar vizual sentiment de o programare reală limba arata ca, se pare un pic ceva de genul asta. Deci, este vorba despre 20-plus, 30 de linii de cod, dar conversația am au fost cu peste pauza a fost despre modul în care acest fapt devine transformat in zero-uri și altele și dacă nu se poate pur și simplu că reveni procesa și du-te de la zero-uri și altele înapoi la cod. 

Din nefericire, procesul este atât de transformare că este mult mai ușor de zis decât de făcut. M-am dus mai departe și sa transformat de fapt acel program, binar de căutare, în zero-uri și altele prin intermediul unei Programul numit compilatorul pe care am se întâmplă să aibă aici chiar pe Mac-ul meu. Și dacă te uiți la ecran aici, concentrându-se în mod specific pe aceste șase coloane de mijloc numai, veți vedea numai zerouri și cele. Iar acestea sunt zerouri și cele care compun exact acel program de căutare. 

Și, astfel încât fiecare bucată de cinci biți, fiecare octet de zero-uri și cele de aici, reprezintă câteva instrucțiuni de obicei în interiorul unui computer. Și, de fapt, dacă ați auzit sloganul de marketing "Intel în interiorul" - care, desigur, pur și simplu înseamnă că aveți un CPU Intel sau creier în interiorul calculatorului. Și ceea ce înseamnă a fi un procesor este că aveți un set de instrucțiuni, ca sa zicem asa. 

Fiecare procesor din lume, multe dintre le-a făcut de Intel în aceste zile, înțelege un finit numărul de instrucțiuni. Iar aceste instrucțiuni sunt la nivel atât de scăzut așa cum se adaugă aceste două numere împreună, multiplica aceste două numere împreună, mutați această bucată de date de aici aici în memorie, salvați această informații de aici până aici, în memorie, și așa forth-- foarte, foarte Low-level, detalii aproape electronice. Dar, cu cele matematice operațiuni cuplate cu ceea ce am discutat mai devreme, reprezentarea datelor ca zero-uri și altele, pot vă construi totul că un calculator poate face astăzi, dacă este textual, grafice, muzicale, sau altfel. 

Deci, acest lucru este foarte ușor pentru a obține a pierdut în buruienile de repede. Și există o mulțime de provocări sintactice prin care, dacă ai face cel mai simplu, nici unul dintre erorile de scriere, mai stupida a programului va lucra nici un fel. Și astfel, în loc de a folosi un cum ar fi limba C în această dimineață, M-am gândit că ar fi mai distractiv de a face de fapt ceva mai vizual, care în timp ce concepute pentru copii este de fapt o manifestare perfectă de programare real language-- doar se întâmplă utilizați imagini în loc de text să reprezinte aceste idei. 

Deci, odată ce aveți într-adevăr, o cont pe scratch.mit.edu, faceți clic pe butonul Creare din partea stanga sus a site-ului. Și ar trebui să vedeți un mediu ca cea Sunt pe cale să văd pe ecran aici. Si vom cheltui doar un pic ceva timp de joc aici. Să vedem dacă nu putem rezolva toate unele problemele împreună în felul următor. 

Deci, ce veți vedea în acest environment-- și de fapt, doar lasa mă întrerupe. Este cineva care nu aici? Nu aici? O.K. Așa că lasă-mă să subliniez câteva caracteristicile acestui mediu. 

Așa că în partea din stânga sus a ecranului, noi au scena Scratch lui, ca să spunem așa. Scratch este nu numai numele a acestui limbaj de programare; este, de asemenea, numele de pisica care vezi implicit acolo, în portocaliu. El se află pe o scenă, așa mult ca am descris broasca mai devreme ca fiind într-un mediu de bord alb dreptunghiular. aceasta lume pisicii este limitată în întregime la acel dreptunghi în sus de sus acolo. 

În același timp, în partea dreaptă partea de mână aici, este doar o zonă de script-uri, un ardezie gol dacă va fi. Acest lucru este în cazul în care vom scrie programele noastre in doar un moment. Și blocurile pe care le vom utilizați pentru a scrie acest program-- puzzle bucăți, în cazul în care sunt will-- cei care chiar aici în mijloc, iar acestea sunt clasificate prin funcționalitate. Așa că, de exemplu, am de gând să merg mai departe și să demonstreze cel puțin una dintre acestea. Mă duc să merg mai departe și faceți clic categoria de control în sus de sus. 

Deci, acestea sunt categoriile de top în sus. Am de gând să faceți clic pe categoria de control. Mai degrabă, am de gând să faceți clic pe Evenimente categorie, prima una în sus de sus. Și, dacă doriți să urmați de-a lungul chiar așa cum vom face acest lucru, tu ești destul de bun venit la. Am de gând să faceți clic și trageți această Prima, "când steagul verde a făcut clic." Și apoi am de gând să-l doar picătură aproximativ la partea de sus a Tăblițe mele goale. 

Și ce e frumos despre zero este faptul că această piesă de puzzle, atunci când interblocată cu alte puzzle piese, va face literalmente ce acele piese de puzzle spun să facă. Astfel, de exemplu, Scratch este corect acum în mijlocul lumii sale. Mă duc să merg mai departe și alege acum, să zicem, categoria Motion, dacă doriți pentru a face same-- categoria Motion. Și acum am observat un întreg grămadă de piese de puzzle aici că, din nou, un fel de a face ceea ce spun ei. Și mă duc să merg mai departe și glisați și picătură bloc mutare chiar aici. 

Și observați că de îndată ce veți obține aproape de partea de jos a "steagul verde click pe "buton, Notă modul în care apare o linie albă, ca și cum este aproape magnetice, vrea să meargă acolo. Lasa doar du-te, și va fixa precum și formele se vor potrivi. Și acum puteți, probabil, aproape ghici unde vom merge cu asta. 

Dacă te uiți la etapa Scratch aici si uita-te la partea de sus a acesteia, veți vedea o lumină roșie, un opri semn, și un steag verde. Si voi merge mai departe și urmăriți-mi screen-- pentru un moment, dacă ai putea. Am de gând să faceți clic pe verde pavilion chiar acum, și sa mutat ceea ce pare a fi de 10 pași sau 10 pixeli, 10 puncte, pe ecran. 

Și așa nu asta interesant, dar permiteți-mi propun chiar fără a învăța acest lucru, pur și simplu folosind propria dvs. Înștiințați intuition-- mă propun ca să îți dai seama cum să face plimbare de zero chiar de pe scenă. L-au pentru a face loc pe partea dreaptă a ecran, tot drumul spre dreapta. Lasă-mă să-ți dau un moment sau astfel încât să se lupte cu asta. S-ar putea dori să ia o privire la alte categorii de blocuri. In regula. Deci, doar să recapitulez, atunci când avem steagul verde dat click aici și pentru a muta 10 etape este cea numai instruire, de fiecare dată când am faceți clic pe steagul verde, ce se întâmplă? Ei bine, asta rulează programul meu. Așa că am putut face acest lucru poate 10 de ori manual, dar acest lucru se simte un pic bit hackish, ca să spunem așa, prin care nu sunt cu adevărat rezolvarea problemei. Eu doar încerc din nou și din nou și din nou și din nou până când am un fel de accidental atinge directiva că am stabilit pentru a realiza mai devreme. 

Dar noi știm de la nostru pseudocod mai devreme că există această noțiune în programarea looping, face ceva din nou și din nou. Și așa am văzut că o grămadă de tine a ajuns pentru piesa ce puzzle? Se repetă până când. Așa că am putea face ceva cum ar fi, până când se repetă. Și ce-ai repeta pana exact? 

O.K. Și lasă-mă să merg cu una singură oarecum mai simplu pentru un moment. Lasă-mă să merg mai departe și fac acest lucru. Observați că, după cum s-ar putea avea descoperit sub control, există acest bloc de repetare, care nu arata ca este atât de mare. Nu există mult loc în între cele două linii galbene. Dar, așa cum unii dintre voi s-ar putea avea a observat, dacă trageți și plasați, observați cum crește pentru a umple forma. 

Și tu poți ghiftui chiar mai mult. Se va păstra doar în creștere în cazul în care trageți și plasați cursorul peste ea. Si eu nu știu ce-i cel mai bine aici, asa ca lasa mine cel puțin repeta de cinci ori, pentru de exemplu, și apoi du-te înapoi la etapa și faceți clic pe steagul verde. Și acum observați că nu e chiar acolo. 

Acum, unii dintre voi a propus, ca Victoria tocmai a, se repetă de 10 ori. Iar aceasta, în general, să-l tot drumul, dar nu ar exista o mai robust mod arbitrar decât imaginind cât de multe mișcări pentru a face? Ce ar putea fi un bloc mai bun decât se repetă de 10 ori mai fie? 

Da, așa că de ce să nu fac ceva pentru totdeauna? Și acum să mă mute această piesă de puzzle acolo înăuntru și a scăpa de asta. Acum observați în cazul în care nu contează zero începe, el merge la margine. Din fericire și MIT, care face zgârieturi, doar face sigur că el nu dispare complet. Puteți apuca întotdeauna coada lui. 

Si doar intuitiv, de ce face el menține în mișcare? Ce se intampla aici? El pare să se fi oprit, dar apoi, dacă mă ridic și să trageți el continuă să vrea să meargă acolo. De ce este asta? Într-adevăr, un calculator este literalmente O să facă ceea ce îi spun să facă. Așa că, dacă ai spus mai devreme este diferența dintre următorul lucru pentru totdeauna, mutați 10 pași, se va menține merge și merge până când am lovit semnul roșu de stop și a opri programul cu totul. 

Deci, chiar dacă nu-i face acest lucru, cum aș putea face mișcare Scratch mai repede pe ecran? Mai mulți pași, nu? Deci, în loc de a face 10 la un moment dat, de ce nu ne mergeți mai departe și schimbați-l sa-- ce-ai propose-- 50? Așa că acum am de gând să faceți clic pe verde pavilion, și într-adevăr, el merge foarte repede. 

Și acest lucru, desigur, este doar o manifestare de animație. Ce este animația? Doar că vă arată un om grămadă de imagini statice într-adevăr, într-adevăr, foarte repede. Și așa, dacă ne povesteam l să se miște mai mulți pași, noi suntem doar având ca efect să fie la schimbare în cazul în care el este pe ecran tot mai rapid pe unitatea de timp. 

Acum, următoarea provocare pe care am propus a fost să-l sări de pe margine. Și, fără să știe ce puzzle piese de exist-- pentru că e în regulă dacă nu ajungi la etapă a challenge-- ce vrei să faci intuitiv? Cum trebuie să-l sări înapoi și mai departe, între stânga și dreapta? 

Da. Așa că avem nevoie de un fel de stare, și noi par să aibă condiționale, astfel încât să vorbesc, în categoria de control. Care dintre aceste blocuri face, probabil, ne dorim? Da, poate ", dacă, atunci." Așa că observați că printre blocurile galbene avem aici, nu există acest "dacă" sau acest lucru ", în cazul în care, altfel", bloc care va ne permit să ia o decizie de a face acest lucru sau de a face acest lucru. Și tu poți chiar să le cuib pentru a face mai multe lucruri. Sau, dacă nu ai plecat încă aici, merge mai departe la categoria Sensing si-- să vedem dacă e aici. 

Deci, ce blocul ar putea fi de ajutor aici pentru a detecta dacă el e pe scenă? Da, observați că unele dintre aceste blocuri poate fi parametrizat, ca să spunem așa. Ele pot fi un fel de personalizat, nu spre deosebire de HTML ieri cu atribute, în cazul în care aceste atribute un fel de personaliza comportamentul unei etichete. În mod similar aici, pot apuca această ating bloc și schimbare și de a pune întrebarea, te atinge mouse-ul pointer la fel ca cursorul sau te ating marginea? 

Așa că lasă-mă să intru și să facă acest lucru. Voi micșora pentru un moment. Lasă-mă apuca de această piesă de puzzle aici, acest puzzle bucata asta, și mă duc la talmeș-balmeș le doar pentru un moment. Am de gând să se mute acest lucru, schimba acest lucru la margine atinge, și voi face asta de mișcare. Deci, aici sunt unele ingrediente. Cred că am tot ce vreau. 

Cineva ar dori să propună modul în care am se poate conecta aceste poate de sus in jos în scopul de a rezolva problema de a avea Zgârietură muta dreapta la stânga la dreapta la la stânga la dreapta la stânga, fiecare timp doar cade de pe perete? Ce vreau să fac? Care blocul ar trebui să se conecteze la "Pavilion verde atunci când a făcut clic mai întâi"? 

OK, așa că hai să începem cu "pentru totdeauna." Ce merge în interiorul următor? Altcineva. OK, mutați pași. In regula. Atunci ce? Așa că, atunci dacă este. Și observați, chiar dacă pare sandwich strâns împreună, aceasta va crește doar pentru a umple. Acesta va sari doar în cazul în care l-am dorit. 

Și ce am pus între IF și atunci? Probabil "dacă atinge margine." Și observați, din nou, este prea mare pentru ea, dar va creste pentru a umple. Și apoi rândul său, de 15 de grade? Câte grade? Da, deci 180 se va roti mă tot drumul în jurul valorii. Așa că hai să vedem dacă am acest drept. Lasă-mă micșora. 

Lasă-mă să trageți Scratch în sus. Deci, el e un pic distorsionat acum, dar asta e bine. Cum pot să-l reseta cu ușurință? Am de gând să trișeze ușor. Deci, eu sunt adăugarea de un alt bloc, trebuie doar să fie clar. Vreau ca el să punctul 90 de grade la dreapta în mod implicit, așa că doar o să-i spun pentru a face acest lucru în mod programatic. Si aici vom merge. Se pare că au făcut-o. E un pic ciudat, pentru că Merge cu susul în jos. Hai să-i spunem că o eroare. Asta-i o greșeală. Un bug este o greșeală într-un program, eroare logică pe care eu, omul, a făcut. De ce se întâmplă cu susul în jos? Au șurub MIT sau nu-i așa? 

Da, vreau să spun, nu e MIT vina. Mi-au dat o bucată de puzzle care spune rândul său, unele număr de grade. Iar la sugestia Victoria, Sunt de cotitură la 180 de grade, care este intuiția corectă. Dar, de cotitură 180 de grade literalmente înseamnă cotitură 180 de grade, și că nu este cu adevărat ceea ce vreau, aparent. Pentru că cel puțin el e în această lume cu două dimensiuni, astfel încât de cotitură este într-adevăr merge să-l răsturna cu susul în jos. 

Probabil că vreau să folosesc ceea ce bloc în schimb, bazat pe ceea ce vezi aici? Cum ne-am putea rezolva această problemă? Da, așa că am putea arăta în direcția opusă. Și, de fapt, chiar asta nu va fi de ajuns, pentru că putem doar cod greu la arătând spre stânga sau spre dreapta. 

Știi ce am putea face? Se pare că avem un bloc de confort aici. În cazul în care pot mări, a se vedea ceva ce ne place aici? Deci, se pare ca MIT are un abstracție construită aici. Acest bloc pare a fi echivalent la care alte blocuri, plural? 

Acesta bloc pare să fie echivalentă pentru tot acest trio de blocuri pe care o avem aici. Deci, se pare că pot simplifica meu Programul prin eliminarea de toate astea și tocmai a pus asta aici. Și acum el este încă un pic buggy, și asta e bine acum. Vom lăsa asta să fie. Dar programul meu este chiar mai simplu, și acest lucru, de asemenea, ar fi reprezentativ de un gol în programming-- este de a face în mod ideal codul ca simplu, cât mai compactă, în timp ce încă ca citibil posibil. Tu nu vrei să-l atât de succintă că este greu de înțeles. 

Dar observați am înlocuit trei blocuri cu unul, și asta e, fără îndoială, un lucru bun. Am captată departe noțiunea de a verifica dacă sunteți pe margine, cu doar un singur bloc. Acum ne putem distra cu acest lucru, de fapt. Acest lucru nu adaugă atât de mult valoare intelectuală, dar valoarea jucaus. Mă duc să merg mai departe și apuca acest sunet aici. Așa că lasă-mă să merg mai departe, și lasă-mă opri programul pentru un moment. Mă duc să înregistreze următoarele, permițând accesul la microfonul meu. 

Începem. Aoleu. Hai să încercăm din nou. Începem. OK, am înregistrat un lucru greșit. Începem. Aoleu. Aoleu. In regula. Acum trebuie să scap de asta. In regula. 

Așa că acum am un înregistrarea doar "Ouch." Așa că acum am de gând să merg înainte și numesc acest lucru "Ouch." Mă duc să mă întorc la scripturile mele, iar acum Notă există acest bloc care se numește reda un sunet "miau", sau să joace un sunet "Ouch." Voi trage acest lucru, și în cazul în care ar trebui să pun acest lucru pentru un efect comic? Da, așa că acum e un fel de trăsură pentru două persoane, pentru că acum această block-- observați cum acest lucru ", în cazul în care pe muchie, sări "este un fel de sine stătătoare. Așa că am nevoie pentru a rezolva această problemă. Lasă-mă să merg mai departe și fac acest lucru. Lasă-mă să scap de asta și du-te înapoi cu originalul nostru, în mod deliberat mai mult funcționalitate. Deci, "dacă atinge margine, atunci" Vreau la rândul său, așa cum a propus Victoria, 180 de grade. Si vreau sa joace sunetul "Ouch" acolo? 

Da, observați că e afară că blocul galben. Deci, acest lucru, de asemenea, ar fi bug-ul, dar l-am observat. Așa că am de gând să-l trage în sus aici, și acum este o notificare in interiorul "daca". Prin urmare, "dacă" este acest tip cum ar fi de pată-braț ca că doar va face ceea ce este în interiorul acestuia. Așa că acum, dacă am zoom out la riscul de annoying-- 

COMPUTER: Ouch, aoleu, aoleu. 

DAVID MALAN: Și va merge doar la nesfârșit. Acum, pur și simplu pentru a accelera lucrurile aici, lasă-mă să merg mai departe și să se deschidă, Să say-- lasă-mă să merg la unele din lucrurile mele proprii de la clasă. Și lasă-mă să deschid în sus, să spunem, acest lucru una făcută de unul dintre semenii noștri de predare acum cativa ani. Așa că unii dintre voi s-ar putea aminti acest joc de odinioară, și este de fapt remarcabil. Chiar dacă ne-am făcut mai simplu de programe chiar acum, să ia în considerare ce acest lucru de fapt, arată. Lasă-mă să lovit joc. 

Deci, în acest joc, avem broască, și utilizând săgeata keys-- el ia măsuri mai mari decât mi-am amintește-ți Am controlul asupra acestei broaște. Iar scopul este de a obține peste ocupat rutier fără să fie difuzate în vagoane. Și să see-- dacă mă duc aici, am trebuie să aștepte un jurnal pentru a derula. Acest lucru se simte ca un bug. Acesta este un fel de bug. In regula. Sunt pe asta aici, acolo, și apoi păstrați merge până când obțineți toate broaste pentru tampoane crin. Acum, acest lucru ar putea arata tot mai complexe, dar să încercăm să rupă acest lucru în jos mental verbal și în blocurile sale componente. Deci, există, probabil, un puzzle piesa pe care nu le-am văzut încă dar care răspunde la intrarile de la tastatura, la lucruri am lovit pe tastatură. 

Deci, nu există, probabil, un fel de bloc care spune, în cazul în care cheia este egal în sus, apoi face ceva cu rămășițe poate muta 10 pași în acest fel. Dacă se apasă tasta în jos, mutați 10 pași în acest fel, sau tasta stânga, mutați 10 pași Astfel, 10 pași care. M-am transformat în mod clar pisica într-o broască. Deci asta e unde se trage costum, ca în cazul apelurilor răzuibile it-- noi doar importate o imagine de broasca. 

Dar ce altceva se întâmplă? Ce alte linii de cod, ce alte piese de puzzle a făcut Blake, colegul nostru de predare, utilizați în acest program, aparent? Ce se face totul move-- Ce programare construct? 

Propunerea, sure-- așa muta bloc, sigur. Si ce e acel bloc de mișcare interiorul, cel mai probabil? Da, un fel de buclă, poate pentru totdeauna bloca, poate o repetare block-- se repetă până la bloc. Și asta e ceea ce face jurnalele și tampoane crin și totul altceva muta Înainte şi înapoi. Se întâmplă doar la nesfârșit. 

De ce sunt unele dintre masini se deplasează mai repede decât ceilalți? Ceea ce este diferit despre aceste programe? Da, probabil, unele dintre ele sunt luati mai multe etape dintr-o dată, iar unele dintre ele mai puține etape dintr-o dată. Iar efectul vizual este rapid versus lent. 

Ce crezi că sa întâmplat? Când m-am luat broasca mea tot drumul peste drum și râul pe planșa de crin, ceva demn de menționat sa întâmplat. Ce sa întâmplat imediat ce am făcut asta? S-a oprit. Că broasca sa oprit, și Am primit oa doua broască. Deci, ce trebuie să fie construct folosit acolo, ce facilitate? 

Da, deci există un fel de "În cazul în care" condiționează acolo, de asemenea. Și se pare out-- nu am văzut astea-- dar există și alte blocuri acolo, care se poate spune, în cazul în care se ating un alt lucru pe ecran, dacă vă atingeți pad crin ", apoi". Și apoi asta e atunci când ne face să apară de-a doua broasca. Deci, chiar dacă acest joc este cu siguranță foarte datat, chiar dacă la prima vedere există atât de mult merge pe Blake on-- și nu a bici acest lucru în două minute, probabil a luat-l de mai multe ore pentru a crea acest joc bazat pe memorie sau videoclipurile sale din versiunea lui de odinioară ea. Dar toate aceste lucruri mici merge pe ecran în mod izolat se fierbe în jos la aceste foarte simplu mișcări constructs-- sau declarații așa cum am discutat, bucle și condiții, și asta e despre asta. Există alte câteva caracteristici columbofil. Unele dintre ele sunt pur estetice sau acustice, cum ar fi sunetele tocmai am jucat cu. Dar pentru cea mai mare parte, tu au în această limbă, Scratch, toate fundamentale blocuri de construcție pe care le au în C, Java, JavaScript, PHP, Ruby, Python, precum și orice număr de alte limbi. Întrebări cu privire la zero? In regula. Așa că nu ne vom scufunda mai adânc la zero, deși sunteți binevenit acest week-end, mai ales dacă aveți copii sau nepoții și nepoatele și astfel, pentru a le introduce la zero. Este de fapt un minunat jucaus mediu cu, după cum spun autorii săi, tavane foarte înalte. Chiar dacă am început cu foarte multe detalii de nivel scăzut, puteți face într-adevăr destul de un pic cu ea, iar acest lucru este probabil o demonstrație de exact asta. 

Dar, hai acum trecerea la unele mai multe probleme sofisticate, dacă va fi, cunoscut sub numele de "căutarea" și "Sortare", mai general. Am avut această carte de telefon e aici earlier-- un altul doar pentru discussion-- că am fost capabili să caute mai eficient deoarece a unei ipoteze semnificative. Și ca să fie clar, ceea ce ipoteză am fost de luare atunci când se caută prin această carte de telefon? Mike Smith a fost în cartea de telefon, deși am s-ar putea să se ocupe scenariul fără el acolo dacă pur și simplu m-am oprit prematur. Cartea e în ordine alfabetică. Si asta e un foarte generos ipoteză, pentru că înseamnă someone-- Sunt un fel de tăiere a unui colt, ca eu sunt mai repede pentru că cineva altcineva a făcut o mulțime de muncă grea pentru mine. 

Dar, ce se întâmplă dacă telefonul carte au fost nesortate? Poate că Verizon a primit leneș, tocmai a aruncat numele și numerele fiecăruia acolo poate, în ordinea în care acestea semnat pentru serviciul telefonic. Și cât de mult timp nu-l ia-mi pentru a găsi pe cineva ca Mike Smith? 1.000 pagina de telefon book-- câte Paginile trebuie să mă uit prin ea? 

Toti. Tu ești un fel de noroc. Ai literalmente să se uite la fiecare pagina în cazul în care cartea de telefon este doar sortate aleatoriu. S-ar putea avea noroc și să găsească Mike pe prima pagină, pentru că el a fost primul client pentru a comanda un serviciu telefonic. Dar el ar fi fost ultimul, de asemenea. 

Astfel încât ordine aleatorie nu este bun. Așa că să presupunem că trebuie să Sortafli agenda telefonica sau date generale de sortare pe care le-am dat. Cum putem face asta? 

Ei bine, lasă-mă să încerc un exemplu simplu aici. Lasă-mă să merg mai departe și să arunci o câteva numere de pe bord. Să presupunem că numerele pe care le avem sunt, să zicem, patru, doi, unu și trei. Si, Ben, a sorta aceste numere pentru noi. 

OK bine. Cum ai făcut asta? In regula. Deci, începe cu cea mai mică valoare și cea mai mare, și asta e foarte bună intuiție. Și ne dăm seama că oamenii sunt de fapt destul bun la rezolvarea problemelor ca aceasta, cel puțin în cazul în care datele sunt relativ mici. De îndată ce începe să aibă sute numerelor, mii de numere, milioane de numere, Ben, probabil, nu s-ar putea face destul de rapid, presupunând că au existat decalaje în numere. Destul de ușor să numere până la un milion în caz contrar, doar consumatoare de timp. 

Asa ca algoritmul suna cum ar fi Ben folosit doar acum a fost căutarea pentru cel mai mic număr. Deci, chiar dacă noi, oamenii pot lua într-o mulțime de informații vizuale, un calculator este de fapt un pic mai limitat. Computerul poate doar uita-te la un octet la un moment dat sau poate patru octeți de la un time-- în aceste zile, poate, 8 octeți de la un time-- dar un număr foarte mic de octeți la un moment dat. 

Așa că având în vedere că avem cu adevărat patru valori distincte aici-- și vă puteți gândi la Ben ca având ochelari de cal, dacă ar fi fost un astfel de calculator că el nu poate vedea nimic altceva peste un număr de la un time-- așa că, în general, va presupune, la fel ca în Engleză, vom citi de la dreapta la stânga. Deci, primul număr Ben, probabil, sa uitat la patru a fost apoi foarte repede a dat seama că e destul de mare number-- lasă-mă să continui să cauți. 

Sunt doi. Așteptaţi un minut. Două este mai mică decât patru. Mă duc să-mi amintesc. Doi este cel mai mic. Acum, asta e chiar Unu mai bine. Asta e chiar mai mic. Am de gând să uit de două și amintiți-vă doar unul acum. 

Și ar putea să nu se mai uite? Ei bine, el ar putea bazat aceste informații, dar el mai bine-ar căutare restul listei. Pentru că ce se întâmplă dacă zero ar fi fost în listă? Ce se întâmplă dacă unul negativ au fost în listă? El știe doar că răspunsul lui este corect dacă el este în mod exhaustiv verificat întreaga listă. Așa că ne uităm la restul. Three-- că a fost o pierdere de timp. Avut ghinion, dar am fost încă corect de a face acest lucru. Și așa acum el probabil selectat cel mai mic număr și pune-l doar la început din listă, așa cum voi face aici. Acum, ce-ai făcut în continuare, chiar dacă te-ai gândit la asta aproape în această măsură? Se repetă procesul, astfel încât un fel de buclă. E o idee familiară. Deci, aici este de patru. Asta e în prezent, cele mai mici. Asta e un candidat. Nu mai. Acum am văzut două. Asta e urmatorul cel mai mic element. Three-- că nu este mai mică, așa acum Ben poate scoate cele două. 

Și acum vom repeta procesul și desigur, trei devine tras afară următor. Se repetă procedeul. Patru devine tras afară. Și acum nu mai avem numere, astfel încât lista trebuie să fie sortate. 

Și într-adevăr, acest lucru este un algoritm formal. Un om de știință de calculator ar numesc acest lucru "selecție sortare" ideea fiind un fel de lista iteratively-- din nou și selectând din nou și din nou cel mai mic număr. Și ce e frumos despre el este este doar naibii de intuitiv. Este atât de simplu. Și tu poți repeta același lucru operațiune din nou și din nou. E simplu. 

În acest caz, a fost rapid, dar cât timp durează de fapt? Hai să facem să pară și simt un pic mai plictisitor. Deci unul, doi, trei, patru, cinci și șase, șapte, opt, nouă, 10, 11, 12, 13, 14, 15, 16-- număr arbitrar. Am vrut doar mai mult acest lucru timp decât doar patru. Așa că, dacă am un întreg grămadă de numere l now-- chiar nu contează ceea ce ei are-- lui lasa gândiți-vă ce acest lucru Algoritmul este într-adevăr ca. 

Să presupunem că există un număr de acolo. Din nou, nu contează ce ele sunt, dar sunt aleatorii. Sunt aplicarea algoritmului lui Ben. Am nevoie pentru a selecta cel mai mic număr. Ce fac? Și mă duc la punct de vedere fizic fă-o de data aceasta să-l interpreteze. Cautam, cherestea, Cautam, cautati, cautati. Numai când am ajunge la la sfârșitul listei poate Îmi dau seama cel mai mic numarul doi a fost de data asta. Nu mai e în listă. Așa că am pus jos două. 

Ce trebuie să fac în continuare? Cautam, Cautam, cherestea, cautati. Acum am găsit numărul șapte, deoarece există lacune în aceste Numere ci pur și simplu arbitrar. In regula. Așa că acum pot pune în jos șapte. Looking Cautam, caut. 

Acum, eu sunt presupunând, Desigur, că Ben nu au memorie RAM suplimentar, suplimentar memorie, pentru că, desigur, Mă uit la același număr. Cu siguranță aș fi putut aminti toate aceste numere, și asta e absolut adevărat. Dar, dacă Ben își aduce aminte toate a numerelor a văzut, el nu și-a făcut într-adevăr un progres fundamental pentru că el are deja capacitatea de a căuta prin numerele de pe bord. Amintindu cele de mai Numerele nu ajută, pentru că el încă se poate ca un computer uita-te doar, ne-am spus, un singur număr la un moment dat. Deci, nu există nici un fel de ieftin acolo pe care le puteți pârghie. 

Așa că, în realitate, așa cum am continuați căutarea lista, Eu pur și simplu trebuie să păstreze doar merge înainte și înapoi prin ea, jumulire afară următorul număr mai mic. Și, după cum se poate deduce un fel de din mișcările mele stupide, acest lucru devine doar foarte plictisitor foarte repede, și mi se pare să fie merge înapoi și mai departe, înainte și înapoi destul de un pic. Acum, pentru a fi corect, nu trebuie să merg destul ca, de asemenea, să see-- să fie echitabil, Nu trebuie să meargă destul de cât mai multe etape de fiecare dată. Pentru că, desigur, așa cum am selectați numerele din listă, lista rămasă se scurtează. 

Și așa să ne gândim la câți pași sunt de fapt eu traipsing prin fiecare dată. În prima situație am avut 16 numere, și așa mai maximally-- lui lasa doar face acest lucru pentru o discussion-- A trebuit să se uite prin 16 Numerele pentru a găsi cele mai mici. Dar, odată ce am smuls cel mai mic număr, cum lung a fost lista rămasă, desigur? Doar 15. Deci, cât de multe numere de făcut Ben sau am să se uite prin a doua oară în jurul valorii de? 15, doar pentru a merge și de a găsi cele mai mici. Dar acum, desigur, lista este, de asemenea, mai mică decât era înainte. Deci, cum mulți pași a făcut eu trebuie să ia data viitoare? 14 și apoi 13 și apoi 12, plus punct, punct, punct, până când am rămas doar cu unul. Deci, acum, un om de știință de calculator ar întreba, bine, ce înseamnă că toți egali? Ea este egală cu de fapt, unele din beton număr pe care am putea cu siguranță do aritmetic, dar vrem să vorbim despre eficiența algoritmilor un pic mai mult formulaically, independent de cât timp este lista. 

Și așa, știi ce? Acest lucru este de 16, dar cum am spus mai înainte, Să numim doar dimensiunea problemei n, unde n este un număr. Poate că e 16, poate că e trei, poate e un milion. Nu știu. Nu-mi pasă. Ceea ce eu doresc cu adevărat este o formulă pe care eu pot utilizați pentru a compara acest algoritm împotriva altor algoritmi că cineva ar putea pretinde sunt mai bune sau mai rele. 

Deci, se pare, și numai eu știu acest lucru de la școală grad, că acest fapt funcționează la fel lucru ca n peste n plus unu peste doi. Și acest lucru se întâmplă să fie egal, de Desigur, n plus la pătrat n peste două. Deci, dacă am vrut o formulă pentru cât de multe etape au fost implicați în căutarea la toate din aceste numere din nou și din nou și din nou și din nou, aș spune este n plus la pătrat n peste două. Dar știi ce? Acest lucru pur și simplu arată murdar. Vreau doar într-adevăr o sens general al lucrurilor. Si s-ar putea aminti de liceu că acolo este noțiunea de cea mai înaltă pe termen ordine. Care dintre acești termeni, n patrat, n, sau jumătate, are cel mai mare impact asupra timpului? Cu cat mai mare n devine, care din aceste chestiuni cel mai mult? 

Cu alte cuvinte, dacă am conectați într-un milion, n-patrat va fi cel mai probabil factorul dominant, pentru că un milion de ori în sine este mult mai mare decât plus un milion suplimentar. Deci, tu ce știi? Aceasta este o astfel de darn mare număr, dacă aveți un număr pătrat. Acest lucru nu contează cu adevărat. Vom merge doar cruce care afară și uită de asta. Și astfel, un om de știință calculator ar spune că eficiența acestui algoritm este de ordinul n squared-- Vreau să spun cu adevărat o aproximare. Este un fel de aproximativ n la pătrat. De-a lungul timpului, cu atat mai mare și mai mare n devine, acest lucru este o estimare bună pentru ceea ce eficiența sau lipsa de eficiență din acest algoritm este de fapt. Iar eu derivă că, desigur, de la a face de fapt matematica. Dar acum eu sunt doar fluturand mâinile mele, pentru că eu doar doresc un sens general al acestui algoritm. 

Așa că, folosind aceeași logică, între timp, Să considerăm un alt algoritm am uitat deja at-- căutare liniară. Când am fost în căutarea pentru book-- telefonului nu-l sortarea, căutarea prin intermediul telefonului book-- am continuat spunând că acesta a fost 1000 trepte, sau 500 de pași. Dar, să generalizăm asta. În cazul în care există n pagini în cartea de telefon, ceea ce este timpul de rulare sau eficiența de căutare liniară? Este pe ordinea cât de mulți pași pentru a găsi Mike Smith, folosind căutarea liniară, The primul algoritm, sau chiar a doua? 

În cel mai rău caz, Mike se află la sfârșitul cărții. Așa că în cazul în care cartea de telefon are 1.000 de pagini, am spus ultima oară, în cel mai rău caz, ar putea dura aproximativ cât mai multe pagini pentru a găsi Mike? Ca 1000. Este o limită superioară. Este o situație cel mai rău posibil. Dar, din nou, ne mișcăm departe de la numere ca 1000 acum. Este pur și simplu n. 

Deci, ce este concluzia logică? Găsirea Mike într-un telefon carte care are n pagini s-ar putea lua, în cel mai rău caz, câți pași pe ordinea de n? Și, într-adevăr, un calculator om de știință ar spune că timpul de funcționare, sau performanța sau eficiența sau ineficiența, a unui algoritm similar o căutare liniară este de ordinul n. Si putem aplica la fel Logica de trecere ceva așa cum tocmai am făcut-o la a doua algoritm am avut-o cu cartea de telefon, în cazul în care ne-am dus două pagini la un moment dat. 

Așa că 1.000 de pagini de carte de telefon s-ar putea să ne ia 500 de pagini se transformă, plus unu dacă ne replia un pic. Așa că, dacă o carte de telefon are n pagini, dar facem două pagini la un moment dat, asta e cam ce? N peste două, astfel încât e ca n peste doi. Dar am făcut revendica un momentul în urmă că N pe parcursul two-- asta e cam la fel ca și pur și simplu n. Este doar un factor constant, oamenii de știință de calculator ar spune. Să ne concentrăm numai asupra variabilele, really-- cele mai mari variabile în ecuație. 

căutare atât de liniar, dacă unul făcut pagină la un moment dat sau două pagini la un moment dat, este un fel de fundamental același. Este încă pe ordinea de n. Dar am susținut cu poza mea anterioară că al treilea algoritm nu a fost liniar. Nu a fost o linie dreaptă. Era acea linie curbă, iar algebrică cu formula acolo ce era? Jurnal de bază log, astfel N- doi n. Si noi nu trebuie să intru în prea multe detalii despre logaritmi astăzi, dar cei mai mulți oameni de știință de calculator nu ar chiar îți spun ce baza este. Pentru că e totul doar factori constant, ca să spunem așa, doar diferențe numerice ușoare. Și, astfel încât acest lucru ar fi un foarte frecvente mod de calculator deosebit formale oamenii de știință de la un consiliu sau programatori de la o tablă albă de fapt, argumentând care Algoritmul le-ar folosi sau ce eficiența a algoritmului lor este. 

Și acest lucru nu este neapărat ceva discuți în orice detaliu, dar un programator bun este cineva care are un background solid, formal. El este capabil să vorbească vă în acest fel de mod și de fapt, face argumente calitative ca de ce un singur algoritm sau o singură bucată de software este superior într-un fel la altul. Pentru că ai putea cu siguranță doar rulați programul unei singure persoane și numără numărul de secunde este nevoie pentru a sorta unele numere, și puteți rula unele Programul altei persoane și conta numărul secunde este nevoie. Dar acesta este un mod mai general, că puteți utiliza pentru a analiza algoritmi, dacă va fi, pur și simplu pe hârtie sau pur și simplu verbal. Chiar fără să fie difuzate, fără chiar încercarea de intrări de probă, te poți înțelege pur și simplu prin ea. Și așa mai departe cu angajarea unui dezvoltator sau dacă având în el sau ea un fel de tine pentru a argumenta de ce algoritmul lor, secretul lor sos pentru căutarea miliarde de pagini web pentru dumneavoastra companie este mai bine, acestea sunt tipurile de argumentele pe care le ar trebui să fie în mod ideal, capabil să facă. Sau cel puțin acestea sunt tipurile de lucruri care ar veni în discuție, la cel puțin într-o discuție foarte formală. In regula. Așa că Ben a propus ceva numita selecție de sortare. Dar voi propune ca acolo alte moduri de a face acest lucru, de asemenea. Ceea ce nu am place foarte mult despre algoritmul lui Ben este că el a continuat mersul pe jos, sau după ce mă mers pe jos, înainte și înapoi și înainte și înapoi și înainte și înapoi. Ce se întâmplă dacă în schimb ar fi să fac ceva de genul aceste numere de aici și am fost să se ocupe doar cu fiecare număr la rândul său, așa cum am dat-o? 

Cu alte cuvinte, aici e lista mea de numere. Patru, una, trei, doi. Si eu voi face următoarele. Voi insera numerele în cazul în care acestea aparțin mai degrabă decât selectarea lor unul la un moment dat. Cu alte cuvinte, aici e numărul patru. 

Aici e lista mea originală. Și voi menține în esență, o nouă listă aici. Deci, aceasta este lista veche. Aceasta este noua listă. Eu văd numărul patru întâi. Noua mea Lista este inițial goală, așa că este trivial cazul că patru este acum lista de asortat. Eu doar iau numărul I-am dat, si eu o pune în noua mea listă. 

Este sortata această nouă listă? Da. E o prostie pentru că există doar un singur Element, dar este absolut sortate. Nu e nimic din loc. Este mai interesant, acest algoritm, când am trece la pasul următor. 

Acum am unul. Așa că unul, desigur, aparține la cele mai începutul sau la sfârșitul acestei noi liste? Inceputul. Așa că trebuie să fac ceva de lucru acum. Am luat niște libertăți cu markerul prin tragere la doar lucruri în cazul în care le-am dorit, dar asta nu e cu adevărat exacte într-un calculator. Un calculator, după cum știm, are RAM sau Random Access Memory, și asta e un octet și un alt octet și un alt octet. Și, dacă aveți un gigabyte de RAM, ai un miliard de bytes, dar sunt fizic într-o singură locație. Nu te poți mișca doar lucruri în jurul valorii de prin tragere-l pe placa oriunde vrei. Așa că, dacă noua mea listă are patru locații în memorie, din păcate, cele patru este deja în locul greșit. 

Deci, pentru a se introduce numărul unu Nu pot desena aici. Această locație de memorie nu există. Asta ar fi inselat, și am fost inseala pictural pentru câteva minute aici. Așa că într-adevăr, dacă vreau să pun unul aici, Trebuie să copiați temporar cele patru și a pus apoi pe cel de acolo. 

E în regulă, asta e corect, că este posibil punct de vedere tehnic, dar dau seama că e muncă suplimentară. Nu am pus doar numărul în loc. Am avut mai întâi să se miște un număr, apoi pus în aplicare, așa că am cam dublat suma mea de muncă. Astfel încât să păstreze în minte. 

Dar eu sunt acum terminat cu acest element. Acum vreau să apuca numărul trei. În cazul în care, desigur, nu-i aparține? Intre. Nu mai pot înșela și pune-l doar acolo, pentru că, din nou, această memorie se află în locații fizice. Așa că trebuie să copiați cele patru și a pus trei aici. Nu e mare lucru. Este doar un pas suplimentar again-- se simte foarte ieftin. 

Dar acum mă mut la cei doi. Cei doi, desigur, aparține aici. Acum începe să vedeți cum munca poate aduna. Acum, ce trebuie să fac? Da, trebuie să se mute cele patru, atunci am să copiați trei, iar acum pot insera cele două. Și captura cu această algoritm, destul de interesant, este că să presupunem că avem mai extreme cazul în care este să zicem opt, șapte, șase, cinci, patru, trei, doi, unu. Acest lucru este, în multe contexte, cel mai rău scenariu, pentru că darn lucru este literalmente înapoi. 

Ea nu prea afectează algoritmul lui Ben, pentru că în selecția lui Ben sortare el va păstra merge înainte și înapoi prin listă. Și, pentru că el a fost mereu în căutarea prin toata lista rămasă, nu contează în cazul în care elementele sunt. Dar, în acest caz, cu inserarea mea approach-- să încercăm. 

Deci unul, doi, trei, patru, cinci, șase, șapte, opt. Unu doi trei patru, cinci, șase, șapte, opt. Mă duc să iau cele opt, și unde am pus-o? Ei bine, la începutul listei mele, deoarece această nouă listă este sortată. Si eu l trec afară. 

Unde am pus șapte? La naiba. Este nevoie să meargă acolo, așa Trebuie să fac niște copiere. Și acum cei șapte merge aici. Acum am trece la șase. Acum este și mai mult de lucru. 

Opt trebuie să meargă aici. Șapte trebuie să meargă aici. Acum, cei șase pot merge aici. Acum am apuca cinci. Acum opt trebuie să meargă aici, șapte trebuie să meargă aici, șase trebuie să meargă aici, și acum cinci și se repetă. Și eu sunt destul de mult se deplasează în mod constant. 

Deci, la final, această algorithm-- ne vom numesc inserție de fapt sort-- are o mulțime de muncă, de asemenea. E doar diferit un fel de muncă decât cea a lui Ben. munca lui Ben a avut-mi merge înainte și înapoi, tot timpul, selectarea următoarea cea mai mică Element din nou și din nou. Deci, a fost acest tip foarte vizual de muncă. 

Celălalt algoritm, care este încă correct-- va primi slujba done-- schimba doar cantitatea de muncă. Se pare că inițial ești de economisire, pentru că tu ești doar care se ocupă cu fiecare element în față, fără a mers pe jos toate drum prin listă ca Ben a fost. Dar problema este, mai ales în aceste cazuri nebune unde e totul în spate, tu esti doar un fel de amânarea munca grea până când trebuie să repare greșelile. 

Și astfel, dacă vă puteți imagina acest lucru opt și șapte și șase și cinci și mai târziu, patru și trei și doi se deplasează prin modul lor listă, tocmai am schimbat tipul de muncă ce facem. În loc de a face-o la începând din iterație mea, Eu doar o fac la cele mai sfârșitul termenului de fiecare iterație. Deci, se pare că acest algoritm, de asemenea, în general, numit inserare de sortare, este, de asemenea, pe ordinea de n pătrat. Este de fapt nu mai bine, nu mai bine deloc. 

Cu toate acestea, există oa treia abordare Eu ne-ar încuraja să ia în considerare, care este aceasta. Așa că să presupunem că lista mea, pentru simplitate din nou, este de patru, unul, trei, two-- doar patru numere. Ben a avut intuiție bună, intuiție umană bună mai înainte, prin care ne-am fixat întreg lista eventually-- sortare inserare. Eu ne-au convins de-a lungul. Dar haideți să considerăm modalitate simplă de a rezolva această listă. 

Această listă nu este sortat. De ce? În limba engleză, explica de ce nu este de fapt sortate. Ce înseamnă să nu fie sortate? 

ELEVUL: Nu este secvențială. 

DAVID MALAN: Nu secvențială. Dă-mi un exemplu. 

ELEVUL: Pune-le în ordine. 

DAVID MALAN: OK. Da-mi un exemplu mai specific. 

ELEVUL: ordine crescătoare. DAVID MALAN: Nu sunt ordine crescătoare. Mai precis. Nu știu ce vrei să spui ascendent. Ce s-a întâmplat? 

Elev: Cel mai mic dintre Numerele nu este în primul spațiu. 

DAVID MALAN: Cel mai mic număr de Nu în primul spațiu. Fii mai clar. Încep să mă prindă. Contăm, dar ce e de ordine aici? 

ELEVUL: secvență numerică. DAVID MALAN: secvență numerică. un fel tuturor de păstrare l aici-- nivel foarte ridicat. Doar literalmente spune-mi ce-i greșit ca o putere de cinci ani. 

ELEVUL: Plus unul. 

DAVID MALAN: Ce-i asta? 

ELEVUL: Plus unul. 

DAVID MALAN: Ce vrei să spui, plus unul? Dă-mi un alt copil de cinci ani. Ce sa întâmplat, mamă? Ce sa întâmplat, tată? Ce vrei sa spui acest lucru nu este sortat? 

ELEVUL: Nu e locul potrivit. 

DAVID MALAN: Ce este nu în locul potrivit? 

ELEVUL: Patru. DAVID MALAN: OK, bine. Așa că patru nu este în cazul în care ar trebui să fie. În special, este acest drept? Patru și unul, primele două numere pe care le văd. Este corect? Nu, sunt de ordine, nu? De fapt, cred că acum despre un computer, de asemenea. Ea se poate uita doar la unul, poate, poate două lucruri la once-- și de fapt, doar un singur lucru la un moment dat, dar poate cel puțin uita-te la un singur lucru interceptează Următorul lucru chiar lângă el. 

Sunt acestea în ordine? Desigur că nu. Deci, tu ce știi? De ce nu luăm copilul pași de fixare această problemă în loc de a face aceste fantezie algoritmi cum ar fi Ben, unde el e un fel de ea de fixare looping prin lista în loc de a face ceea ce am făcut, în cazul în care Am doar un fel de reparat așa cum vom merge? Să ne rupe doar literalmente în jos Noțiunea de ordine numerică order--, numesc orice ai o doresti în aceste comparații perechi. 

Patru și unu. Este aceasta ordinea corectă? Așa că hai să repare asta. Unu și patru, și apoi vom copia doar asta. Bine, bine. Am fixat unul și patru. Trei și doi? Nu. Cuvintele mele se potrivesc degetele mele. Patru și trei? 

Nu e în ordine, așa că voi pentru a face una, trei, patru, doi. OK bine. Acum patru și doi? Avem nevoie pentru a remedia acest lucru, de asemenea. Deci una, trei, doi, patru. Deci este sortat? Nu, dar este mai aproape de sortate? 

Este, pentru că am stabilit acest lucru greșeală, am remediat această greșeală, și am stabilit această greșeală. Așa că ne-am fixat trei greșeli, fără îndoială. Nu arată cu adevărat sortat, dar aceasta este în mod obiectiv mai aproape de sortat pentru că ne-am fixat unele dintre aceste greșeli. 

Acum, ce să fac în continuare? Am cam ajuns la sfârșitul listei. Mi se părea că am fixat toate greșelile, dar nu. Pentru că în acest caz, unele numere ar fi barbotat în sus mai aproape la alte numere care sunt încă în ordine. Așa că hai să o facem din nou, și eu voi doar face acest lucru în loc de data asta. Unul și trei? Este bine. Trei și doi? Bineînțeles că nu, așa că hai să schimbăm asta. Deci doi, trei. Trei și patru? Si acum sa fie doar în special pedant aici. Este sortate? Voi, oamenii știu că e sortate. 

Ar trebui să încerc din nou. Așa că Olivia își propune să încerc din nou. De ce? Pentru că un calculator nu are luxul de ochii noștri umani de doar uitându-se back-- OK, am terminat. Cum determină computerul că lista este acum sortate? Mechanically. 

Ar trebui să treacă prin încă o dată, și numai dacă nu fac / găsi orice greșeli pot apoi încheie ca calculator, Yep, suntem bine să mergem. Deci, unu și doi, doi trei, trei și patru. Acum pot spune definitiv acest lucru este sortate, pentru că am făcut nici o schimbare. Acum ar fi un bug și doar prostie dacă eu, computerul, a cerut din nou aceste întrebări aceleași așteptând răspunsuri diferite. Nu ar trebui să se întâmple. 

Și așa acum lista este sortată. Din păcate, timpul de funcționare acest algoritm este, de asemenea, n la pătrat. De ce? Pentru că aveți n numere, și în cel mai rău caz, trebuie să se mute n numere n ori mai mult pentru că trebuie să continui înapoi pentru a verifica și repara potențial aceste numere. Si putem face o mai mult analiză formală, de asemenea. 

Deci, acest lucru este tot să spunem că ne-am luat trei abordări diferite, una dintre ele imediat intuitiv off BAT de la Ben la inserare mi-au sugerat un fel la aceasta în cazul în care te cam pierde din vedere pădurea de copaci inițial. Dar, apoi, dacă luați un pas înapoi, voila, ne-am stabilit notiunea de sortare. Deci, aceasta este, îndrăznesc să spun, un nivel mai scăzut, probabil, decât unele dintre aceste alte algoritmi, dar să a se vedea dacă nu putem vizualiza acestea prin intermediul acestui. 

Deci, acest lucru este un frumos software-ul pe care cineva a scris folosind bare colorate, care e O să facă următoarele pentru noi. Fiecare dintre aceste bare reprezintă un număr. Bara de mai înalți, cu atât mai mare numărul, mai mic bar, este mai mic numărul. Așa că în mod ideal, ne dorim o piramidă frumos în cazul în care începe mici și devine mare, și asta ar însemna că aceste bare sunt sortate. Așa că am de gând să merg mai departe și să aleagă, de exemplu, algoritmul lui Ben selecție sortare first--. 

Și observați ce face. Modul în care au ales să vizualizează acest algoritm este că, la fel ca și cum am fost mersul pe jos prin lista mea, acest program este mersul pe jos prin lista de numere, subliniind în roz fiecare număr care se uită la. Și ce e pe cale să se întâmple chiar acum? 

Cel mai mic număr care I sau Ben găsit pe neașteptate devine mutat la începutul listei. Și remarcați cu ei a făcut evacua numărul care a fost acolo, și asta e foarte bine. N-am intrat în acel nivel de detaliu. Dar avem nevoie pentru a pune acest număr undeva, așa că tocmai a fost mutat în în loc deschis, care a fost creat. Așa că voi grăbi în sus, pentru că în caz contrar devine foarte plictisitor repede. Animație speed-- acolo vom merge. Deci, acum același principiu Am fost aplicarea, dar tu poate începe să se simtă algoritmul, în cazul în care va, sau pentru a vedea un pic mai clar. Și acest algoritm are ca efect selectarea elementului următor cel mai mic, astfel încât vei începe să vedea rampa din stânga. Și în fiecare iterație, după cum am a propus, face un pic mai puțin de lucru. Aceasta nu trebuie să meargă tot drumul înapoi la capătul din stânga al listei, deoarece deja îi cunoaște pe cei sunt sortate. Deci, este un fel de simt ca este accelerare, chiar dacă fiecare pas este luând aceeași cantitate de timp. Există doar mai puțini pași rămași. Și acum poți fel de Simt Algoritmul de curățare până la sfârșitul anului acesta, și într-adevăr, acum este sortat. 

Așa că inserare de sortare este terminat. Trebuie să re-randomiza matrice. Si eu pot observa doar păstrați randomizing-l, și vom obține o aproximare a aceeași abordare, inserare de sortare. Lasă-mă să-l încetinească aici. Să începem că peste. Stop. 

Hai să sari peste patru. Acolo mergem. Randomiza ei matrice. Si aici ne go-- de inserare sortare. Joaca. Observați că se ocupă cu fiecare elementul întâmpină imediat, dar, în cazul în care aparține anunțul loc greșit toată munca pe care trebuie să se întâmple. Trebuie să continuăm să redirecționează și mai multe elemente pentru a face loc pentru cel care vrem să pună în aplicare. 

Deci, suntem concentrându-se pe capătul din stânga, numai lista. Observati nu ne-am uitat chiar at-- noi nu s-au evidențiat în nimic roz la dreapta. Noi doar de-a face cu problemele pe măsură ce mergem, dar vom crea o mulțime de lucra pentru noi încă. Și, așa că, dacă vom grăbi acum pentru a merge la finalizare, ea are un simt diferit de ea, într-adevăr. Este doar concentrandu-se pe capătul din stânga, dar face un pic de lucru mai mult ca needed-- un fel de lucruri de netezire peste, lucruri de fixare, dar în cele din urmă se ocupă cu fiecare element de unul la un moment dat până când vom ajunge la the-- bine, noi toate știu cum acest lucru se va termina, așa că e un pic SCENARIUL, probabil. 

Dar lista din end-- spoiler-- va fi sortate. Deci, să ne uităm la o ultimă unul. Noi nu putem sări peste acum. Suntem aproape acolo. Două pentru a merge, unul pentru a merge. Și voila. Excelent. 

Așa că acum hai să facem o ultima, re-randomizare cu sortare cu bule. Și observați aici, mai ales dacă am lent în jos, acest lucru nu ține picaj prin. Dar observați face doar pairwise un fel de comparisons-- soluții locale. Dar, de îndată ce vom ajunge la la sfârșitul listei în roz, ce se va trebui să se întâmple din nou? Da, va trebui să începe peste, deoarece numai greșeli fixe. pereche Si care ar fi dezvăluit încă altele. Și, așa că, dacă viteza asta, tu vei a se vedea că, la fel cum sugerează și numele, mai mici elements-- sau, mai degrabă, cele mai mari sunt elements-- de pornire să bule până la partea de sus, dacă vreți. Și elementele sunt mai mici încep să bule în jos spre stânga. Și într-adevăr, asta e un fel de efectul vizual, de asemenea. Și, astfel încât aceasta va încheia finisare într-un mod foarte asemănător, de asemenea. 

Noi nu trebuie să locuiască pe aceasta anume. Lasă-mă să deschid acest lucru acum, de asemenea. Există o sortare alți câțiva algorithms în lume, unele dintre ele sunt capturate aici. Și, mai ales pentru cei care învață, care nu sunt în mod necesar vizual sau matematic, așa cum am făcut-o mai înainte, putem De asemenea, face acest lucru audially dacă vom asocia un sunet cu asta. Și doar pentru distracție, aici este o câțiva algoritmi diferiți, și unul dintre ei, în special, sunteți O să observați se numește "îmbinare sortare." 

Este de fapt un mod fundamental mai bine algoritm, astfel încât îmbinare un fel, unul dintre cele pe care le vei vedea, nu este ordinea de n la pătrat. Este pe ordinea de n ori log de n, care este de fapt mai mică și, prin urmare, mai repede decât cele trei alte. Și există un alt cuplu cele stupide pe care le vom vedea. 

Deci, aici vom merge cu un sunet. Acesta este un fel de inserție, deci din nou este doar de-a face cu elementele așa cum au venit. Acesta este un fel cu bule, deci este considerându-le perechi la un moment dat. Și din nou, cele mai mari elemente sunt barbotare până la partea de sus. 

Următorul selecție sortare. Acesta este algoritmul lui Ben, unde din nou, el selectând iterativ următorul mai mic element. Și din nou, acum poți auzi cu adevărat că este accelerarea, dar numai în măsura în care deoarece face mai puțin și mai puțin lucrează la fiecare iterație. Acesta este cel mai rapid unul, îmbinare sortare, care este sortarea grupuri de numere împreună și apoi combinarea lor. Așa că look-- la stânga jumătate este deja sortat. 

Acum este sortarea jumătatea din dreapta, și acum o să le combine într-una singură. Acest lucru este ceva numit "Gnom un fel." Și tu poți fel de a vedea că se merge înainte și înapoi, de stabilire de muncă un pic aici și acolo înainte de a trece la noua lucrare. Si asta e. Există un alt soi, care este într-adevăr doar pentru scopuri academice, numit "un fel de prost", care ia datele, sortează la întâmplare, și apoi verifică dacă este sortat. Și dacă nu este, se re-sorteaza-l la întâmplare, verifică dacă este sortat, și în cazul în care nu se repetă. Și, în teorie, probabilist acest lucru se va finaliza, dar după destul de un pic de timp. Nu e cel mai mult eficientă a algoritmilor. Astfel încât orice întrebări cu privire la acele algoritmi speciale sau orice legate de acolo, de asemenea? 

Ei bine, hai acum tachineze in afara ce toate aceste linii sunt că am fost de desen și ceea ce eu sunt presupunând computerul se poate face sub capota. Aș argumenta că toate aceste numere Am păstra drawing-- care au nevoie pentru a obține stocat undeva în memorie. O să scăpăm de tipul ăsta acum, de asemenea. 

Deci, o bucată de memorie într-un computer-- astfel încât RAM DIMM este ceea ce am căutat ieri, cu dublă inline memory module-- arata ca acest lucru. Și fiecare dintre aceste chip-uri mici negre este un număr de octeți, în mod tipic. Și apoi pinii de aur sunt ca fire care se conectează la calculator, iar placa de siliciu verde este doar ceea ce ține totul împreună. Deci, ce înseamnă cu adevărat? Dacă aș fi un fel de remiză aceeași imagine, Să presupunem, pentru simplitate că acest DIMM, dublă modul de memorie în linie, este un gigabyte de memorie RAM, o gigabyte de de memorie, care este cât de mulți octeți totală? Gigaoctet este cât de mulți octeți? Mai mult decat atat. 1124 este kilogram, 1000. Mega este milioane. Giga este un miliard. 

Sunt eu mint? Putem citi chiar eticheta? Aceasta este de fapt 128 gigaocteți, deci este mai mult. Dar ne vom prefacem că este doar un gigabyte. Deci asta înseamnă că există un miliard octeți de memorie disponibile pentru mine sau 8 miliarde de biți, dar vom pentru a vorbi în termeni de octeți acum, a merge inainte. 

Deci, ceea ce înseamnă că este acest lucru este un octet, acesta este un alt octet, acesta este un alt octet, și dacă ne-am dorit cu adevărat să fie specifice ne-ar trebui să trage un miliard de mici pătrate. Dar ce înseamnă asta? Ei bine, lasă-mă doar zoom în? Pe aceasta imagine. Dacă am ceva care arată ca acest lucru acum, asta e patru octeți. 

Și așa am putut pune patru numere aici. Unu doi trei patru. Sau aș putea pune patru litere sau simboluri. "Hei!" ar putea merge chiar acolo, pentru că fiecare dintre litere, am discutat mai devreme, poate fi reprezentat cu opt biți sau ASCII sau de un octet. Deci, cu alte cuvinte, poți a pus 8 miliarde de lucruri în interiorul din aceasta stick de memorie. Acum, ce înseamnă a pune lucrurile înapoi to back to back în memorie ca asta? Aceasta este ceea ce un programator ar numi o "matrice". Într-un program de calculator, nu crezi despre hardware-ul de bază, per se. Tocmai ai gândi la tine ca având acces la un total de miliard de bytes, și poți tot ce vrei cu ea. Dar, pentru comoditate este în general util pentru a păstra dreptul de memorie unul lângă altul ca asta. Deci, dacă am zoom pe astea-- pentru că cu siguranță nu vom să atragă un miliard de mici squares-- Să presupunem că acest consiliu reprezintă care se lipesc de memorie acum. Și eu voi trage la fel de multe ca meu marcator sfârșește prin a da-mi aici. Așa că acum avem un băț de memorie de pe placa că are unul, doi, trei, patru, cinci, șase, unu, doi, trei, patru, cinci, șase, seven-- astfel încât 42 octeți memorie pe total ecran. Mulțumesc. Da, a făcut aritmetica mea dreapta. Deci 42 bytes de memorie. Deci, ce înseamnă de fapt? Ei bine, un programator de calculator ar fi, de fapt, în general, cred că de această memorie ca adresabile. Cu alte cuvinte, fiecare dintre acestea locații în memorie, în hardware, are o adresă unică. 

Nu este la fel de complex ca un Brattle Pătrat, Cambridge, Mass., 02138. În schimb, este doar un număr. Acesta este numărul de octeți zero, acest lucru este unul, aceasta este de două, acest lucru este de trei, iar acest lucru este de 41. Așteptaţi un minut. Am crezut că am spus 42 un moment în urmă. Am început de numărare la zero, astfel încât este de fapt corect. Acum, noi nu trebuie să-l atragă de fapt ca o grilă, iar dacă îl trage ca grilă Cred că de fapt lucrurile obține un pic înșelătoare. Ce un programator ar fi, în propria mintea lui sau ei, în general, cred că de acest lucru memorie este la fel ca o bandă, ca o bucată de bandă de mascare că doar merge mai departe și pentru totdeauna sau până când a alerga afară de memorie. Deci, un mod mai comun de a desena Gândiți-vă doar despre memorie ar fi că acest lucru este octet zero, unu, doi, trei, și apoi punct, punct, punct. Și tu ai 42 de astfel de bytes totală, chiar deși fizic s-ar putea de fapt să fie ceva mai mult ca acest lucru. 

Așa că, dacă te gândești acum al tău memorie ca acest lucru, la fel ca și o bandă, aceasta este ceea ce un programator din nou ar numi o serie de memorie. Iar atunci când doriți să stocați de fapt, ceva în memoria unui calculator, ai face, în general, magazin lucruri back-to-back to back-to-back. Așa că am vorbit despre numere. Iar când am vrut să rezolve problemele cum ar fi patru, unul, trei, doi, chiar dacă am fost doar desen numai patru numere, una, trei, două pe bord, computerul ar au într-adevăr această configurare în memorie. 

Și ce ar fi lângă opțiunea două în memoria calculatorului? Ei bine, nu există nici un răspuns la asta. Noi nu știm cu adevărat. Și, atâta vreme cât computerul nu are nevoie de ea, nu trebuie să aibă grijă de ceea ce este urmatorul la numerele de face pasa. Iar când am spus mai devreme că un calculator se pot uita doar la o singură adresă la un moment dat, acest lucru este un fel de ce. 

Nu spre deosebire de un record player și un cap de citire doar să fii capabil să se uite la un anumit canelură într-un record de școală veche fizică la un moment dat, în mod similar poate un calculator multumesc CPU și ei set de instrucțiuni Intel, printre ale căror instruire se citește din memorie sau pentru a salva o memory-- computer poate privi doar la o locație la time-- uneori o combinație a acestora, dar într-adevăr doar o singură locație la un moment dat. Așa că, atunci când făceam acești diverși algoritmi, Nu am scris doar într-un vacuum-- patru, unul, trei, doi. Aceste numere aparțin de fapt undeva fizic în memorie. Prin urmare, există minuscul tranzistori sau un fel de electronice de sub hota stocarea acestor valori. 

Și, în total, câți biți sunt implicat chiar acum, trebuie doar să fie clar? Deci, acest lucru este de patru octeți, sau acum este de 32 de biți totală. Prin urmare, există de fapt 32 de zerouri, cei care compun aceste patru lucruri. Există chiar și mai mult aici, dar din nou, nu ne pasă de asta. 

Așa că acum să ceară un alt întrebare folosind memorie, pentru că la sfârșitul anului a zilei este în dezacord. Nu contează ce am putea face cu computerul, la sfârșitul zilei hardware-ul este încă aceeași sub capota. Cum aș păstra un cuvânt aici? Ei bine, un cuvânt într-un calculator cum ar fi "Hei!" ar fi stocate la fel ca asta. Și, dacă ai vrut o mai cuvânt, puteți pur și simplu suprascrie acest lucru și spune ceva cum ar fi "Bună ziua" și magazin care aici. 

Și așa aici, de asemenea, această contiguousness este de fapt un avantaj, pentru că un calculator poate doar citit de la dreapta la stânga. Dar iată o întrebare. În contextul acestui cuvânt, h-e-l-l-O, punctul de exclamare, cum s-ar putea computerul știe unde cuvânt începe și unde se termină cuvântul? În cadrul numerelor, cum face computerul știu cât timp secvența Numerele este sau în cazul în care acesta începe? Ei bine, se pare out-- și nu vom merge prea mult în acest nivel de detail-- computerele muta lucrurile în jurul valorii în memorie literalmente prin intermediul acestor adrese. Deci, într-un calculator, dacă sunteți scrierea de cod pentru a stoca lucruri cum ar fi cuvinte, ceea ce ești într-adevăr faci este tastarea expresii care amintesc în cazul în care, în memoria calculatorului aceste cuvinte sunt. Așa că lasă-mă să fac un foarte, exemplu foarte simplu. 

Mă duc să merg mai departe și deschide un program de text simplu, și voi crea un fișier numit hello.c. Cele mai multe dintre aceste informații noi nu va intra în în detaliu, dar am de gând să scrie program, în aceeași limbă, C. Acest lucru este mult mai intimidant, Aș argumenta, decât zero, dar este foarte similar în spirit. De fapt, aceste creț braces-- poți fel de cred că de ce am făcut ca acest lucru. 

Hai să facem asta, de fapt. Atunci când steagul verde face clic, procedați în felul următor. Vreau să imprime "salut". Deci, acest lucru este acum pseudocode. Sunt un fel de estomparea liniilor. În C, această limbă vorbesc despre, această linie de imprimare salut devine de fapt "printf" cu unele paranteze și un semi-colon. 

Dar e aceeași idee exactă. Și acest lucru foarte user-friendly "Când steagul verde a făcut clic" devine mult mai arcana "void main int." Și acest lucru are într-adevăr nici o mapare, așa că doar o să ignore asta. Dar, acolade sunt ca piese de puzzle curbate, cum ar fi acest lucru. 

Așa că poți fel de ghici. Chiar dacă nu ați programat mai înainte, ce face acest program, probabil, nu? Probabil tipărește salut cu un punct de exclamare. 

Așa că hai să încercăm. Mă duc să-l salvez. Și acest lucru este, din nou, o foarte mediul școlar vechi. Nu pot să faceți clic, nu pot trage. Trebuie să tastați comenzi. Așa că vreau să rulați programul meu, asa S-ar putea face acest lucru, cum ar fi hello.c. Asta e fișierul am fugit. Dar stai, îmi lipsește un pas. Ce am spus este o condiție necesară pas pentru o limbă ca C? Tocmai am scris sursa cod, dar ce am nevoie? Da, am nevoie de un compilator. Deci, pe Mac-ul meu aici, am o program numit CCG, GNU C compilator, ceea ce-mi permite să fac asta-- rândul său, codul meu sursă în, îl vom numi, cod mașină. 

Și eu pot vedea că, din nou, după cum urmează, acestea sunt zerouri și cele am doar create din codul meu sursă, toate zerouri și cele. Și, dacă vreau să curgă meu program-- se întâmplă să fie numit a.out pentru reasons-- istoric "salut". Pot să-l rula din nou. Salut salut salut. Și se pare a fi de lucru. 

Dar asta înseamnă undeva în meu memoriei calculatorului sunt cuvintele h-e-l-l-O, punctul de exclamare. Și se pare că, la fel ca și o parte, ce un calculator ar fi în mod tipic face astfel încât să știe unde lucrurile vor începe și end-- este va pune un simbol special aici. Iar convenția este de a pune numărul zero la sfârșitul unui cuvânt astfel încât să știi unde de fapt, se termină, astfel încât să nu păstrați imprimarea mai mult caractere decât cele pe care de fapt intenționați. 

Dar aici takeaway, chiar deși acest lucru este destul de obscură, este că este în cele din urmă relativ simplu. Ai fost dat un fel de bandă, un gol spațiu pe care le puteți scrie scrisori. Pur și simplu trebuie să aibă un simbol special, cum ar fi în mod arbitrar numărul de zero, pentru a pune la sfârșitul anului cuvintele tale, astfel încât computerul să știe, oh, ar trebui să se oprească după imprimare Eu văd punctul de exclamare. Pentru că următorul lucru pe acolo este o valoare ASCII de la zero, sau caracterul nul ca cineva ar suna. Dar există un fel de problemă aici, și să revină înapoi la numere pentru un moment. Să presupunem că eu fac, de fapt, au o serie de numere, și presupunem că Programul am scris este ca o carte de grad pentru un profesor și o clasă. Iar acest program permite el sau ea pentru a introduce în scorurile elevilor lor pe chestionare. Și să presupunem că studentul devine 100, pe primul lor test, poate ca un 80 pe următoarea, apoi 75, apoi 90 la al patrulea test. 

Astfel încât în ​​acest moment în poveste, matrice este de marimea patru. Nu există absolut mai mult de memorie în calculator, dar matrice, ca să spunem așa, este de mărime patru. Să presupunem acum că profesorul dorește pentru a atribui un al cincilea test la clasa. Ei bine, unul dintre lucrurile pe care el sau ea va trebui să facă este stoca o valoare suplimentară aici. Dar, în cazul în care matrice profesorul are creat în acest program este de dimensiune pentru, una dintre problema cu o matrice este că nu se poate păstra doar adăugarea la memorie. Pentru că ce se întâmplă dacă o altă parte a Programul are cuvântul "hei" chiar acolo? 

Cu alte cuvinte, memoria mea poate fi utilizat pentru orice într-un program. Și dacă în prealabil am tastat, hei, Vreau să introducă patru scoruri test, ei s-ar putea merge aici și aici. Și dacă vă schimbați brusc mintea ta mai târziu și spun că doresc un al cincilea test scor, nu poți pune-l oriunde doriți, pentru că ceea ce în cazul în care acest lucru memorie este utilizat pentru ceva else-- un alt program sau o altă caracteristică a programului că difuzați? Deci, va trebui să se gândească în avans modul în care doriți să stocați datele, pentru că acum ai pictat te într-un colț digital. 

Deci, un profesor poate în schimb spune atunci când scrieți un program de pentru a stoca sale clase, știi ce? Am de gând să solicite, atunci când scrieți programul meu, că vreau zero, unu, doi, trei, patru, cinci, șase, opt clase în total. Deci unul, doi, trei, patru, cinci, șase, șapte, opt. Profesorul poate doar peste aloca memorie atunci când scrieți programul său și spune, știi ce? Nu voi să alocați mai mult mult de opt teste într-un semestru. Asta e doar o nebunie. Nu voi aloca asta. Astfel că în acest fel el sau ea are flexibilitate la scoruri magazin de student, cum ar fi 75, 90, și poate unul suplimentar în cazul în care studentul a primit credite în plus, 105. 

Dar, dacă profesorul nu utilizează aceste trei spații, există un takeaway intuitiv aici. El sau ea este pur și simplu pierdem spațiu. Deci, cu alte cuvinte, există această tradeoff comună în programare în cazul în care puteți fie aloca exact la fel de mult de memorie așa cum doriți, în sensul creșterii din care este că ești super- efficient-- nu ești risipitor la all--, dar dezavantajul care este ce se întâmplă dacă vă schimbați mintea atunci când folosind programul pe care doriți să stocați mai multe date decât ați intenționat inițial. 

Deci, poate soluția este, atunci, scrie programe în așa fel pe care le utilizează mai multă memorie decât au de fapt nevoie. In acest fel nu vei pentru a rula în această problemă, dar tu ești risipitor. Și mai multă memorie de program utilizează, așa cum am discutat ieri, cu atât mai puțin memorie care este disponibil pentru alte programe, cu atât mai repede calculatorul poate încetini jos, din cauza memoriei virtuale. Și astfel, soluția ideală ar putea fi ceea ce? 

Sub-pare rău Alocarea. Supraevaluare pare rău. Deci, ce ar putea fi o soluție mai bună? Realocării. Fii mai dinamic. Nu te forta pentru a alege un a priori, la început, ceea ce vrei. Și, cu siguranță, nu supra-alocarea, ca nu cumva să fie risipitor. 

Și astfel, pentru a atinge acest obiectiv, Trebuie să arunce această structură de date, ca să spunem așa, departe. Și ce un programator se va folosi în mod tipic nu este un numit ceva matrice ci o listă legată. Cu alte cuvinte, el sau ea va începe să se gândească la memoria lor ca fiind un fel de formă pe care le se pot desena în felul următor. Dacă vreau să stocați un singur număr în un program-- deci este septembrie I-am dat elevilor mei un test; eu vreau pentru a stoca primul test al studenților, și au primit 100 pe I it-- am de gând să ceară calculatorul meu, prin intermediul programului I-am în scris, pentru o bucată de memorie. Si voi pentru a stoca 100 în el number, și asta este. 

Apoi, câteva săptămâni mai târziu când am obține al doilea test meu, și este timpul să tastați în 90%, voi pentru a cere computerul, hei, calculator, pot avea o altă bucată de memorie? O să-mi dau asta bucată goală de memorie. Mă duc să pun în numărul 90, dar în programul meu într-un fel sau other-- și nu vom face griji cu privire la sintaxa pentru astea-- am nevoie cumva să înlănțui aceste lucruri împreună. Și eu voi le lega împreună cu ceea ce arata ca o săgeată aici. 

Al treilea test care vine în sus, Am de gând să spun, hei, calculator, da-mi o altă bucată de memorie. Și voi pune în jos orice ar fi fost, cum ar fi 75, și am să lanț de această împreună acum într-un fel. În al patrulea rând test vine de-a lungul, și poate că e spre sfârșitul semestrului. Și, până la acel punct programul meu ar putea fi utilizați de memorie peste tot, peste tot fizic. Și așa doar pentru lovituri, eu sunt O să atragă acest lucru mai departe quiz-- Am uitat ce era; eu cred că poate un 80 sau something-- drum aici. 

Dar asta e bine, pentru că pictural Voi trage această linie. Cu alte cuvinte, în realitate, în hardware-ul computerului, primul scor ar putea sfârșesc aici pentru că e chiar la începutul semestrului. Următorul termen s-ar putea încheia aici pentru că un pic de timp a trecut iar programul continuă să funcționeze. Urmatorul scor, care a fost 75, ar putea fi aici. Iar ultimul scor ar putea fi un 80, care este aici. 

Deci, în realitate, punct de vedere fizic, acest lucru ar putea fi ce memoria computerului arată. Dar acest lucru nu este o mentală utilă paradigmă pentru un programator de calculator. De ce ar trebui să vă pese cazurilor în care Heck datele se termină în sus? Vrei doar pentru a stoca date. 

Acest lucru este un fel de discuția noastră mai devreme de desen cub. De ce îți pasă ce unghiul este cubului și modul în care trebuie să activați să-l atragă? Vrei doar un cub. În mod similar aici, vreau doar sa carte de grad. Vrei doar să se gândească la acest lucru ca o listă de numere. Cui îi pasă cum e implementat în hardware-ul? 

Așa că abstracția acum este această imagine aici. Aceasta este o listă legată, după cum un programator ar numi, în măsura în care aveți listă, în mod evident de numere. Dar este legat pictural prin intermediul acestor săgeți, și toate aceste săgeți are-- dedesubt capota, daca esti curios, Reamintim că hardware-ul nostru fizic are adrese zero, unu, doi, trei, patru. Toate aceste săgeți sunt este ca o hartă sau instrucțiuni de ghidare, în cazul în care în cazul în care 90 este-- acum Trebuie să conta. 

Zero, unu, doi, trei, patru, cinci, șase, șapte. Se pare ca 90 este la memorie număr de șapte adrese. Toate aceste săgeți sunt este ca un pic resturi de hârtie care dă indicații pentru a ajunge program care spune urmați această hartă pentru a ajunge la poziția șapte. Și acolo vei gasi al doilea scor test student. Între timp, 75-- dacă voi continua acest lucru, acest lucru este de șapte, opt, nouă, 10, 11, 12, 13, 14, 15. 

Această altă săgeată reprezintă doar o hartă în memoria locație 15. Dar, din nou, programator face în general Nu pasă de acest nivel de detaliu. Și, în cele mai multe fiecare programare limbă astăzi, programator chiar nu va ști unde în memorie aceste numere sunt de fapt. Tot el sau ea trebuie să aibă grijă este că acestea sunt legate între ele într-un fel într-o structură de date ca aceasta. 

Dar se pare că nu pentru a obține prea tehnic. Dar, tocmai pentru că putem, probabil, permite să aibă această discuție aici, să presupunem că revizuim această problemă aici, dintr-o matrice. Să vedem dacă vom regreta merge aici. Acest lucru este de 100, 90, 75 și 80. 

Lasă-mă să fac această afirmație pe scurt. Aceasta este o matrice, și, din nou, Caracteristica proeminentă a unei matrice este faptul că toate datele sunt înapoi spate în spate în memory-- literalmente un octet sau poate patru octeți, un numar fix de bytes departe. Într-o listă legată, pe care am putea trage ca aceasta, sub capota, care știe unde chestia asta e? Ea nu are nevoie chiar să curgă așa. Unele dintre aceste date ar putea fi înapoi la stânga sus acolo. Nici măcar nu știu. 

Și astfel, cu o matrice, aveți caracteristică cunoscută sub numele de acces aleatoriu. Și ce înseamnă acces aleator este că computerul poate sări instantaneu la orice locație într-o matrice. De ce? Deoarece computerul știe că prima locație este zero, unu, doi și trei. 

Și, așa că, dacă vrei să mergi la acest element la elementul următor, literalmente, în mintea lui de calculator, trebuie doar să adăugați unul. Dacă doriți ca să mergi la al treilea element, trebuie doar să adăugați elementul următor Unu, doar adaugă unul. Cu toate acestea, în această versiune din poveste, să presupunem că computerul este în prezent în căutarea la sau care se ocupă cu numărul 100. Cum ajungi la următorul gradul în cartea de grad? 

Trebuie să iei șapte trepte, care este arbitrară. Pentru a ajunge la următoarea, trebuie să ia încă opt pași pentru a ajunge la 15. Cu alte cuvinte, nu e decalaj constantă între numere, și așa că doar ia calculator mai mult timp este punctul. Computerul trebuie să caute prin memorie în ordine pentru a găsi ceea ce căutați. 

Așadar, în timp o matrice tinde să fie un structure-- rapid de date, deoarece vă poate literalmente face doar aritmetică simplă și pentru a obține în cazul în care doriți prin adăugarea de unul, pentru instance-- o listă legată, sacrifici acea caracteristică. Nu poți merge de la prima la două la treia la al patrulea. Trebuie să urmați hartă. Trebuie să iei mai mulți pași pentru a ajunge la acele valori, care S-ar părea a fi adăugarea de un cost. Deci ne plătește un preț, dar ceea ce a fost caracteristica pe care Dan căuta aici? Ce face o listă legată aparent ne permit să facem, care a fost originea această poveste specială? 

Exact. O dimensiune dinamică la acesta. Putem adăuga la această listă. Putem micsora chiar si lista, asa că suntem folosind doar la fel de mult de memorie ca de fapt ne-o dorim și așa suntem niciodată supraevaluare. 

Acum, doar pentru a fi cu adevărat niți-pretentios, există un cost ascuns. Deci, tu nu trebuie doar să mă convingă vă că acesta este un compromis convingător. Nu există un alt cost ascuns aici. Beneficiul, să fie clar, este că obținem dinamism. Dacă vreau un alt element, eu pot doar trage-l și a pus un număr acolo. Și apoi eu pot lega cu o imagine aici, întrucât aici, din nou, dacă am ma pictat într-un colț, dacă ceva este deja folosind memorie aici, am noroc. M-am pictat în colț. 

Dar ceea ce este ascuns cost cu o schimbare în această imagine? Nu este vorba doar suma de timp în care este nevoie pentru a merge de aici până aici, care este de șapte trepte, atunci opt trepte, care este mai mult de unul. Ce este un alt cost ascuns? Nu doar timp. Informații suplimentare este necesare pentru a realiza această imagine. 

Da, acea hartă, acele resturi mici de hârtie, așa cum am păstra le ca fiind. Aceștia arrows-- cei care nu sunt liberi. Un computer-- știi ce un computer are. Ea are zerouri și cele. Dacă doriți ca să reprezinte o săgeată sau hartă sau un număr, aveți nevoie de memorie. Așa că celălalt preț vă să plătească pentru o listă legată, o știință comună calculator resursă, este de asemenea spațiu. 

Și într-adevăr așa, atât de frecvent, printre compromisurile în proiectarea inginerie software sisteme este timpul și space-- sunt două dintre ingredientele, două dintre ingredientele cele mai costisitoare. Acest lucru ma costa mai mult timp pentru că trebuie să urmeze această hartă, dar este, de asemenea, ma costa mai mult spațiu pentru că trebuie să păstreze această hartă în jurul valorii. Așa că speranța, așa cum ne-am un fel de a discutat mai mult de ieri și de azi, este că beneficiile vor depăși costurile. 

Dar nu e nici o soluție evidentă aici. Poate că este better-- o rapidă și la murdar, așa cum a propus Kareem earlier-- pentru a arunca memorie la problema. Doar cumpăra mai multă memorie, cred că mai puțin greu cu privire la rezolvarea problemei, și rezolva într-un mod mai ușor. Și, într-adevăr, mai devreme, atunci când am vorbit despre compromisurile, nu era spațiu în computer și timpul. A fost timp de dezvoltator, care este încă o altă resursă. 

Deci, din nou, este acest act de echilibrare încercând să decidă care dintre aceste lucruri ești dispus să-și petreacă? Care este cel mai scump? Care dă rezultate mai bune? Da? 

Intr-adevar. În acest caz, dacă sunteți reprezentând numere în maps-- acestea sunt numite în mai multe limbi "indicii" sau "adrese" - este dublu spațiu. Acest lucru nu trebuie să fie la fel de rău ca dublu în cazul în care chiar acum suntem doar numere de stocare. Să presupunem că am fost stocarea înregistrările pacienților într-un hospital-- așa că numele Pierson, numere de telefon, numere de securitate socială, medicul istorie. Această casetă ar putea fi mult, mult mai mare, caz în care un pic pointer minuscul, adresa în următorii element-- nu e mare lucru. Este un astfel de franjuri cost cu o schimbare nu contează. Dar, în acest caz, da, este o dublare. Buna intrebare. 

Hai să vorbim despre timp o puțin mai concret. Care este timpul de funcționare de a căuta această listă? Să presupunem că am vrut să caute prin toate clasele elevilor, și există n clase în această structură de date. Aici, de asemenea, putem împrumuta vocabularul anterior. Aceasta este o structură de date liniară. 

O mare n este ceea ce este necesar pentru a obține la sfârșitul acestei structuri de date, whereas-- și nu am văzut acest before-- o matrice vă oferă ceea ce se numește timp constant, ceea ce înseamnă cu un pas sau doi pași sau 10 steps-- nu contează. Este un număr fix. Nu are nimic de-a face cu dimensiunea tabloului. Și motivul pentru care, din nou, este de acces aleatoriu. Computerul poate pur și simplu imediat sări într-o altă locație, pentru că acestea sunt toate la fel distanta de la orice altceva. Nu există nici o gândire implicate. In regula. Așa că, dacă eu pot, lasă-mă să încerc să pictează două imagini finale. Un foarte comun cunoscut ca un tabel hash. Deci, pentru a motiva această discuție, Stai să mă gândesc cum să facă acest lucru. 

Deci, cum zici de asta? Să presupunem că problema vrem să rezolve acum implementează într-un dictionary-- astfel încât o grămadă de cuvinte în limba engleză sau orice altceva. Iar scopul este de a fi capabil să răspundă întrebări din formular este acesta un cuvânt? Astfel încât să doriți să pună în aplicare un corector ortografic, doar ca un dicționar fizic că te poți uita lucrurile în. Să presupunem că ar fi să fac acest lucru cu o matrice. Aș putea face asta. 

Și să presupunem că cuvintele sunt măr și banane și pepene galben. Si eu nu pot gândi la fructe care începe cu d, așa că suntem doar va avea trei fructe. Deci, aceasta este o matrice, și suntem stocarea toate aceste cuvinte în acest dicționar ca o matrice. Întrebarea, atunci, este cum altfel ai putea stoca aceste informații? 

Ei bine, eu sunt un fel de înșelăciune aici, pentru că fiecare dintre aceste litere în cuvântul este într-adevăr un octet individuale. Așa că, dacă într-adevăr am vrut să fiu lindină-pretentios, eu ar trebui într-adevăr să fie împărțirea asta în mult bucăți mai mici de memorie, și am putea face exact acest lucru. Dar noi vom rula în aceeași problemă ca și mai înainte. Ce se întâmplă dacă, după cum Merriam Webster sau Oxford face fiecare year-- ei adăuga cuvinte la dictionary-- noi nu facem doresc neapărat să ne picteze într-un colț cu o matrice? 

Deci, în loc, poate o abordare mai inteligentă este de a pune mere în propriul său nod sau cutie, așa cum s-ar spune, banane, și atunci aici avem cantalup. Si noi șir aceste lucruri împreună. Deci, acesta este matrice, și aceasta este lista legată. Dacă nu se poate vedea destul, pur și simplu spune "matrice", iar acest lucru spune "listă." 

Așa că avem aceleași aspecte exacte ca înainte, prin care avem acum dinamism în lista noastră legată. Dar avem un dicționar destul de lent. Să presupunem că vreau să se uite un cuvânt. s-ar putea să dureze O mare de n pași, deoarece cuvântul ar putea fie tot drumul la sfârșitul lista, cum ar fi pepenele galben. Și se pare că în programare, sortare din Sfântul Graal al datelor structuri, este ceva care vă oferă constant timp ca o matrice dar care încă vă oferă dinamism. 

Deci, putem avea cel mai bun din ambele lumi? Și într-adevăr, există ceva numit tabel hash care vă permite să faceți exact că, deși aproximativ. Un tabel hash este un columbofil Structura de date pe care le se poate gândi ca despre combinație a unui array-- și am de gând să-l atragă cum ar fi astea-- și liste legate că voi trage ca asta aici. 

Și modul în care acest lucru lucrări este după cum urmează. În cazul în care acest now-- hash table-- este structura mea de date a treia, și vreau să stocheze cuvinte în această, eu nu fac doriți să stocați doar cele de mai cuvinte spate în spate la spate în spate. Vreau să pârghie unele informaţie despre cuvintele care vă va permite mi-l în cazul în care este mai rapid. 

Așa că, având în vedere cuvintele mere și banane și pepene galben, Am ales în mod deliberat aceste cuvinte. De ce? Ce este un fel de fundamental diferite despre cele trei? Ce e evident? Ei încep cu litere diferite. 

Deci, tu ce știi? Mai degrabă decât a pune toate cuvintele mele în aceeași găleată, ca să spunem așa, cum ar fi într-o listă mare, de ce nu Eu cel puțin încerc o optimizare și face listele mele 1/26, atâta timp. O optimizare convingătoare ar putea fi de ce nu Eu-- la introducerea unui cuvânt în această structură de date, în memoria calculatorului, de ce nu am pus toate cuvintele "un" aici, toate "b" cuvinte aici, și toate "c" cuvintele aici? Deci, acest lucru sfârșește prin a pune un mar aici, banana aici, cantalup aici, si asa mai departe. 

Și, dacă am o suplimentare cuvânt like-- ce-o alta? Mere, banane, pere. Oricine se gândească la un fruct care începe cu a, b, sau c? perfectă Blueberry--. Care se va încheia aici. Și așa se pare că avem un marginal soluție mai bună, pentru că acum, dacă vreau pentru a căuta mere, I first-- Eu nu doar se arunca cu capul în structura mea de date. Nu se arunca cu capul în memoria computerului meu. Mă uit mai întâi la prima literă. 

Și acest lucru este ceea ce un calculator om de știință s-ar spune. Vă hash în structura dvs. de date. Vă luați datele introduse, care în acest caz este un cuvânt ca și mere. Ai analiza, uita la prima literă în acest caz, prin aceasta hashing. Hashing este un termen general prin care să luați ceva ca intrare și ai produce unele ieșire. Și ieșire în caz este locația pe care doriți să căutați, primul locație, a doua locație, a treia. Așa că de intrare este de mere, de ieșire este mai întâi. De intrare este banana, The ieșire ar trebui să fie în al doilea rând. De intrare este pepenele galben, producția ar trebui să fie al treilea. De intrare este de afine, The ieșire ar trebui să fie din nou în al doilea rând. Și asta te ajută să luați comenzile rapide prin memorie în scopul de a ajunge la cuvinte sau date mai eficient. 

Acum, acest lucru taie timpul nostru potențial de la fel de mult ca și unul din 26, pentru că dacă presupunem că au cât mai multe "o" cuvinte ca "z" cuvinte ca și cuvinte "q", care nu este într-adevăr realistic-- vei avea oblic peste anumite scrisori ale alphabet-- dar acest lucru ar fi un incremental abordare care permite tu pentru a ajunge la cuvinte mult mai repede. Și, în realitate, un sofisticat program, Googles lumii, Facebooks a world-- ei s-ar folosi un tabel hash pentru o mulțime de scopuri diferite. Dar ei n-ar fi atât de naiv încât să se uite doar la prima literă în mere sau banane sau pere sau pepenele galben, pentru că așa cum puteți vedea aceste liste ar putea obține încă mult timp. 

Și, astfel încât acest lucru ar putea fi încă un fel de linear--, astfel un fel de lent, cum ar fi cu mare O n pe care am discutat mai devreme. Deci, ce un adevărat tabel hash bun va do-- va avea o matrice mult mai mare. Și se va folosi o mult mai Funcția hashing sofisticate, astfel încât să nu se uita doar la "a." Poate că se uită la "o-p-p-l-e" și cumva convertește aceste cinci litere în locul unde Apple ar trebui să fie stocate. Noi doar în mod naiv folosind litera "a" singur, pentru că e frumos și simplu. 

Dar un tabel hash, în la sfârșitul anului, vă puteți gândi ca o combinație de o matrice, fiecare dintre acestea are o listă legată în mod ideal, care ar trebui să fie cât mai scurt posibil. Și acest lucru nu este o soluție evidentă. De fapt, o mare parte din reglajul fin care merge pe sub capota atunci când punerea în aplicare a acestor tipuri de structuri de date sofisticate este ceea ce este dreptul Lungimea de matrice? Care este funcția hash dreapta? Cum vă stocați lucruri în memorie? 

Dar, dau seama cât de repede acest tip de discuție a escaladat, fie atât de departe încât e un fel de deasupra capului, în acest moment, care e bine. Dar, am început, amintesc, cu adevărat ceva de nivel scăzut și electronic. Și așa este din nou Tema de abstracție, în cazul în care odată ce începe să luați pentru acordat, OK, am it-- acolo memorie fizică, OK, am înțeles, fiecare locația fizică are o adresă, OK, am înțeles, eu pot reprezenta aceste adrese ca arrows-- puteți începe foarte repede pentru a avea conversații mai sofisticate în cele din urmă par să fie permițându-ne pentru a rezolva probleme cum ar fi căutarea și sortarea mai eficient. Și fiți siguri, too-- deoarece cred că acest lucru este cea mai adâncă ne-am dus într-o anumită din aceste subiecte CS proper-- le considerăm, făcut într-o zi și jumătate de la această punctul ceea ce s-ar putea face de obicei peste parcursul a opt săptămâni într-un semestru. 

Orice întrebări cu privire la acestea? Nu? In regula. Ei bine, de ce nu ne oprim acolo, a începe masa de prânz câteva minute mai devreme, relua în doar aproximativ o oră? Iar eu voi persista un pic cu întrebări. Apoi am de gând să trebuie să meargă să ia câteva apeluri dacă e în regulă. Voi activa niște muzică în același timp, dar masa de prânz ar trebui să fie în jurul valorii de colț.