DAVID Malan: Labi. MÄs esam atpakaÄ¼. TÄtad Å¡ajÄ segmentÄ par programmu, kas Es domÄju, mÄs gribÄtu darÄ«t, ir sajaukums lietas. Viens, darÄ«t mazliet kaut hands-on, lai gan, izmantojot vairÄk rotaÄ¼Ä«gu programmÄÅ¡ana environment-- viens, kas ir uzskatÄms par tieÅ¡i veidiems ideju mÄs esam runÄjuÅ¡i par, bet nedaudz vairÄk formÄli. Divi, apskatÄ«t daÅ¾us no jo vairÄk tehniskie veidi ka programmÄtÄjs faktiski atrisinÄt problÄmas, piemÄram, meklÄtÄjas problÄmu ka mÄs paskatÄ«jÄs pirms un arÄ« plaÅ¡ÄkÄ skatÄ«jumÄ interesanta problÄma Å¡Ä·iroÅ¡anu. 

MÄs tikko pieÅemts no get iet ka tÄlruÅu grÄmata tika sakÄrtoti, bet tas vien ir faktiski sava veida grÅ«ti problÄma ar daudz daÅ¾Ädos veidos atrisinÄt to. TÄpÄc mÄs izmantot tos kÄ klases problÄmas pÄrstÄvis lietÄm, kas varÄtu atrisinÄt vispÄr. Un tad mÄs runÄjam par samÄrÄ detalizÄti, ko sauc datu structures-- mÄ«Ä¼otÄjs veidos, piemÄram, saistÄ«tas saraksti un jaucÄjtabula un koki, kas programmÄtÄjs faktiski izmantot un parasti izmanto uz tÄfeles gleznot priekÅ¡statu par to, ko viÅÅ¡ vai viÅa iedomÄjas Ä«stenoÅ¡anas daÅ¾i gabals programmatÅ«ru. 

TÄtad, pieÅemsim do roku-on daÄ¼u pirmÄs. Tik vienkÄrÅ¡i saÅemt rokas netÄ«ras ar vide sauc scratch.mit.edu. Tas ir instruments, kas mÄs izmantojam mÅ«su bakalaura klasÄ. Pat ja tas ir paredzÄts par vecumu 12 un uz augÅ¡u, mÄs to izmantot, lai uz augÅ¡u daÄ¼a no Å¡Ä«s diezgan daudz jo tas ir jauki, jautri grafiskÄ veidÄ mÄcÄ«Å¡anÄs nedaudz kaut ko par programmÄÅ¡anu. TÄpÄc dodies uz Å¡o URL, kur jums vajadzÄtu redzÄt lapu gluÅ¾i kÄ Å¡is, un iet uz priekÅ¡u un noklikÅ¡Ä·iniet Pievienojies Scratch pie augÅ¡ÄjÄ labajÄ stÅ«rÄ« un izvÄlÄties lietotÄjvÄrdu un parole un galu galÄ iegÅ«t sev account-- scratch.mit.edu. Es domÄju, es gribÄtu izmantot Å¡o kÄ iespÄja pirmo reizi parÄdÄ«t to. JautÄjums nÄca klajÄ pÄrtraukumÄ par to, ko kods tieÅ¡Äm izskatÄs. Un mÄs runÄjÄm PÄrtraukumÄ par C laikÄ, in particular-- Ä«paÅ¡i zemÄks lÄ«menis vecÄku valodÄ. Un es tikko bija Ätri Google meklÄÅ¡anu, lai atrastu C kodu binÄro meklÄÅ¡anu, algoritmu, kas mums izmanto, lai meklÄtu Å¡o telefona grÄmatu agrÄk. Å is konkrÄtais piemÄrs, protams, nav meklÄt tÄlruÅa grÄmatu. Tas tikai meklÄ visu Ä·ekars numurus datora atmiÅÄ. Bet, ja vÄlaties, lai tikai iegÅ«t vizuÄli sajÅ«tu, ko faktisko plÄnoÅ¡anu valoda izskatÄs, tas izskatÄs mazliet kaut kas lÄ«dzÄ«gs Å¡im. TÄtad, tas ir par 20-plus, 30 vai tik koda rindiÅas, bet saruna mums bija, kam pÄri pÄrtraukuma bija par to, kÄ tas patiesÄ«bÄ izpauÅ¾as morphed nullÄm un uzÅÄmumiem un, ja jÅ«s varat ne tikai atgriezties ka apstrÄdÄt un aiziet no nullÄm un uzÅÄmumiem atpakaÄ¼ uz kodu. 

DiemÅ¾Äl Å¡is process ir tik pÄrveidojoÅ¡a ka tas ir daudz vieglÄk pateikt, nekÄ izdarÄ«t. Es devos uz priekÅ¡u un faktiski pagriezÄs ka programma, Binary Search, uz nullÄm un tiem Izdarot programmu, ko sauc kompilators, ka es gadÄ«ties, ka Å¡eit tieÅ¡i par manu Mac. Un, ja paskatÄs uz ekrÄna Å¡eit, jo Ä«paÅ¡i koncentrÄjoties uz Å¡Ä«m vidÄjÄm seÅ¡Äm kolonnÄm tikai, jÅ«s redzÄsiet tikai nullÄm un uzÅÄmumiem. Un tie ir nullÄm un tiem, kas sacerÄt tieÅ¡i ka meklÄÅ¡ana programmu. 

Un tÄ katru rieciens pieciem biti, katrs baits nullÄm un tiem Å¡eit, pÄrstÄv kÄdu instrukcija parasti iekÅ¡pusÄ no datora. Un patiesÄ«bÄ, ja jÅ«s esat dzirdÄjis mÄrketinga sauklis "Intel inside" - tas, protams, tikai nozÄ«mÄ, jums ir Intel CPU vai smadzeÅu iekÅ¡Ä datoru. Un ko tas nozÄ«mÄ bÅ«t par CPU ir ka jums ir instrukciju kopums, tÄ sakot. 

Katram CPU pasaulÄ, daudzi no tos, ko Intel Å¡ajÄs dienÄs, saprot ierobeÅ¾ots skaits norÄdÄ«jumiem. Un Å¡ie norÄdÄ«jumi ir tik zems lÄ«menis kÄ pievienot Å¡os divus skaitÄ¼us kopÄ, pavairot Å¡os divus skaitÄ¼us kopÄ, pÄrvietot Å¡o gabals datus no Å¡ejienes Å¡eit atmiÅÄ, saglabÄjiet Å¡o InformÄcija no Å¡eit, lai Å¡eit atmiÅÄ, un tÄ forth-- tik Ä¼oti, Ä¼oti zema lÄ«meÅa, gandrÄ«z elektroniskÄs detaÄ¼as. Bet ar tiem, matemÄtiskÄs operÄcijas kopÄ ar to, ko mÄs runÄjÄm iepriekÅ¡, attÄlojumu datu kÄ nullÄm un uzÅÄmumiem, var jums veidot visu ka dators var darÄ«t Å¡odien, vai tas ir teksta, grafiskÄ, mÅ«zikas, vai citÄdi. 

TÄtad tas ir Ä¼oti viegli nokÄ¼Å«t zaudÄtas nezÄlÄm ir Ätri. Un tur ir daudz sintaktiskÄs izaicinÄjumi saskaÅÄ ar kuru, ja jÅ«s veicat vienkÄrÅ¡Äkais, stupidest no drukas kÄ¼Å«dÄm neviens no programmas darbosies whatsoever. Un tÄ vietÄ, izmantojot valoda, piemÄram, C Å¡orÄ«t, Es domÄju, ka bÅ«tu vairÄk jautrÄ«bas, lai faktiski darÄ«t kaut kas vairÄk vizuÄli, kas savukÄrt paredzÄtas bÄrniem ir faktiski ideÄls izpausme Ar faktisko plÄnoÅ¡anu language-- vienkÄrÅ¡i notiek, izmantot attÄlus, nevis teksta pÄrstÄvÄt Å¡o ideju. 

TÄtad, kad jÅ«s patieÅ¡Äm ir konts scratch.mit.edu, noklikÅ¡Ä·iniet uz pogas Izveidot augÅ¡Ä pa kreisi no vietas. Un jums vajadzÄtu redzÄt vidi, piemÄram, viens es esmu par to, lai redzÄtu uz mana ekrÄna Å¡eit. Un mÄs tÄrÄt tikai nedaudz mazliet laika spÄlÄjot Å¡eit. Let 's redzÄt, ja mÄs nevaram visu atrisinÄt daÅ¾as problÄmas kopÄ Å¡ÄdÄ veidÄ. 

TÄtad, ko jÅ«s redzÄsiet laikÄ Å¡is environment-- un faktiski tikai Ä¼aujiet man pauze. Vai kÄds nav Å¡eit? Ne Å¡eit? LABI. TÄpÄc Ä¼aujiet man norÄdÄ«t daÅ¾us raksturojums Å¡ajÄ vidÄ. 

TÄpÄc augÅ¡ÄjÄ kreisajÄ stÅ«rÄ«, mÄs ir Scratch stadiju, lai runÄt. Scratch ir ne tikai nosaukums Å Ä« programmÄÅ¡anas valodas; tas ir arÄ« nosaukums, kaÄ·i, kas redzat pÄc noklusÄjuma tur oranÅ¾Ä krÄsÄ. ViÅÅ¡ ir uz skatuves, tÄpÄc daudz, piemÄram, es aprakstÄ«ju bruÅurupucis agrÄk kÄ atraÅ¡anos taisnstÅ«ra baltÄ tÄfele vide. Å Ä« kaÄ·a pasaule ir tikai pilnÄ«bÄ ar Å¡o taisnstÅ«ra up top tur. 

TajÄ paÅ¡Ä laikÄ, pa labi labajÄ pusÄ Å¡eit, tas ir tikai skripti zona, tukÅ¡a Å¡Ä«fera ja Jums gribas. Tas ir, ja mÄs ejam, lai rakstÄ«tu MÅ«su programmas tikai brÄ«di. Un celtniecÄ«bas bloki, ka mÄs izmantot, lai rakstÄ«tu Å¡o program-- puzzle gabali, ja jums will-- ir tiem, tepat pa vidu, un viÅi kategorijÄs ar funkcionalitÄti. TÄ, piemÄram, es esmu gatavojas iet uz priekÅ¡u un apliecina vismaz vienu no Å¡iem. Es ieÅ¡u uz priekÅ¡u un noklikÅ¡Ä·iniet Kontroles kategorija augÅ¡u augÅ¡as. 

TÄtad tie ir kategorijas, lÄ«dz top. Es esmu gatavojas noklikÅ¡Ä·iniet uz Control kategoriju. DrÄ«zÄk, es esmu gatavojas noklikÅ¡Ä·iniet uz Notikumi kategorija, pats pirmais vadÄ«bÄ top. Un, ja jÅ«s vÄlaties, lai sekot lÄ«dzi pat kÄ mÄs to izdarÄ«tu, jÅ«s esat diezgan laipni aicinÄti. Es esmu gatavojas noklikÅ¡Ä·iniet un velciet to Pirmais, "zaÄ¼us karogs uzklikÅ¡Ä·inÄt." Un tad es esmu gatavojas piliens to tikai aptuveni augÅ¡pusÄ manu tukÅ¡o Å¡Ä«feris. 

Un, kas ir jauka par nulles ir tas, ka Å¡Ä« puzzle gabals, kad savstarpÄji saistÄ«ti ar citÄm puzzle gabalus, gatavojas darÄ«t burtiski kÄdi ir Å¡ie puzzle gabalus saku darÄ«t. TÄ, piemÄram, Scratch ir taisnÄ«ba tagad vidÅ« viÅa pasaulÄ. Es ieÅ¡u uz priekÅ¡u un izvÄlÄties Tagad, teiksim, Motion kategorija, ja vÄlaties darÄ«t same-- Motion kategoriju. Un tagad paziÅojums man ir viss Ä·ekars puzzle gabalus Å¡eit ka, atkal, veida darÄ«t to, ko viÅi saka. Un es ieÅ¡u uz priekÅ¡u un velciet un piliens PÄrvietot bloku tiesÄ«bas pÄr Å¡eit. 

Un paziÅo, ka, tiklÄ«dz jÅ«s saÅemsiet tuvu apakÅ¡Ä "zaÄ¼o karogu uzklikÅ¡Ä·inÄt "pogu, paziÅojums kÄ parÄdÄ«ts baltÄs lÄ«nijas, it kÄ tas ir gandrÄ«z magnÄtiskÄ, tÄ vÄlas iet uz turieni. Just let iet, un tas bÅ«s snap kopÄ un formas tiks atrasti. Un tagad jÅ«s varat varbÅ«t gandrÄ«z uzminÄt, kur mÄs ejam ar to. 

Ja paskatÄs Scratch posmÄ nekÄ Å¡eit un skatÄ«ties uz augÅ¡u no tÄ, jÅ«s redzÄsiet sarkanu gaismu A stop zÄ«mi un zaÄ¼o karogu. Un es ieÅ¡u uz priekÅ¡u un skatÄ«ties manu screen-- tikai brÄ«di, ja jÅ«s varÄtu. Es esmu gatavojas noklikÅ¡Ä·iniet uz zaÄ¼Ä karoga tieÅ¡i tagad, un viÅÅ¡ pÄrcÄlÄs ko, Å¡Ä·iet, ir 10 soÄ¼i vai 10 pikseÄ¼i, 10 punkti, uz ekrÄna. 

Un tÄ nav, ka aizraujoÅ¡i, bet Ä¼aujiet man ieteikt pat bez mÄcÄ«Å¡anas, vienkÄrÅ¡i izmantojot paÅ¡u savu intuition-- pieÅemsim es iesaku jums saprast, kÄ padarÄ«t Scratch pastaigÄties pa labi pie skatuves. Vai viÅam veikt ceÄ¼u labajÄ pusÄ ekrÄns, visu ceÄ¼u pa labi. Ä»aujiet man sniegt jums brÄ«di vai arÄ« tÄ cÄ«nÄ«ties ar to. JÅ«s varÄtu vÄlÄties, lai apskatÄ«t citÄs kategorijÄs blokiem. Viss kÄrtÄ«bÄ. Tik vienkÄrÅ¡i, lai AtgÄdinÄjums, kad mums ir zaÄ¼ais karogs uzklikÅ¡Ä·inÄt Å¡eit un pÄrvietot 10 soÄ¼i ir tikai norÄdÄ«jums, katru reizi, kad es noklikÅ¡Ä·iniet uz zaÄ¼o karogu, kas notiek? Nu, kas ir darbojas savu programmu. Lai es varÄtu darÄ«t varbÅ«t 10 reizes manuÄli, bet tas jÅ«tas mazliet bit hackish, tÄ sakot, kuru es neesmu Ä«sti problÄmu risinÄÅ¡anÄ. Es esmu tikai mÄÄ£ina atkal un atkal un atkal un atkal kamÄr es veida nejauÅ¡i sasniegt direktÄ«vu ka es noteikti, lai sasniegtu iepriekÅ¡. 

Bet mÄs zinÄm no mÅ«su pseudocode agrÄk, ka tur ir Å¡is jÄdziens plÄnoÅ¡anas looping, darot kaut ko atkal un atkal. Un tÄ es redzÄju, ka Ä·ekars jums sasniegts ko puzzles gabalu? AtkÄrtojiet, lÄ«dz. Lai mÄs varÄtu kaut ko darÄ«t tÄpat atkÄrto, lÄ«dz. Un ko tu atkÄrto, lÄ«dz tieÅ¡i? 

LABI. Un Ä¼aujiet man iet ar vienu, kas ir nedaudz vienkÄrÅ¡Äku tikai brÄ«di. Ä»aujiet man iet uz priekÅ¡u un darÄ«t to. IevÄrojiet, ka, jo Jums var bÅ«t atklÄja zem Control, ir Å¡Ä« atkÄrtojums bloks, kas neizskatÄs kÄ tas ir, ka liels. Tur nav daudz istabu starp Å¡Ä«m divÄm dzeltenÄm lÄ«nijÄm. Bet, tÄ kÄ daÅ¾i no jums varÄtu bÅ«t pamanÄ«ju, ja jums vilkt un nomest, paziÅojums, kÄ tas aug, lai aizpildÄ«tu formu. 

Un jÅ«s pat varat piestÅ«Ä·Ät vairÄk. Tas bÅ«s tikai turpinÄs pieaugt, ja velkat un lidinÄties pÄr to. Un es nezinu, kas ir labÄkais Å¡eit, tÄpÄc Ä¼aujiet man vismaz atkÄrtot piecas reizes, lai instance, un tad doties atpakaÄ¼ uz skatuves un noklikÅ¡Ä·iniet uz zaÄ¼o karogu. Un tagad paziÅojums tas nav gluÅ¾i tur. 

Tagad daÅ¾i no jums ierosinÄja, kÄ Victoria vienkÄrÅ¡i nav, atkÄrto 10 reizes. Un tas parasti dara saÅemt viÅam visu ceÄ¼u, bet nebÅ«tu tur bÅ«t straujÄka veids, kÄ patvaÄ¼Ä«gi norÄdÄ«tas cik daudz kustas padarÄ«t? Kas varÄtu bÅ«t labÄks bloks nekÄ atkÄrtot 10 reizes bÅ«t? 

JÄ, tad kÄpÄc ne darÄ«t kaut ko uz visiem laikiem? Un tagad Ä¼aujiet man pÄriet Å¡o puzzle gabals iekÅ¡Ä tur un atbrÄ«voties no Å¡o vienu. Tagad paziÅojums vienalga, kur Scratch sÄkas, viÅÅ¡ dodas pie malas. Un par laimi MIT, kurÅ¡ Scratch, tikko pÄrliecinÄs, ka viÅÅ¡ nekad pilnÄ«bÄ izzÅ«d. JÅ«s vienmÄr varat paÄ·ert savu asti. 

Un tikai intuitÄ«vi, kÄpÄc viÅÅ¡ saglabÄt pÄrvietojas? Kas Å¡eit notiek? ViÅÅ¡, Å¡Ä·iet, ir pÄrtraukta, bet tad ja es uzÅemt un velciet viÅÅ¡ tur vÄlas doties tur. KÄpÄc ir tÄ, ka? Patiesi, dators ir burtiski gatavojas darÄ«t to, kas jums pateikt to darÄ«t. TÄtad, ja jÅ«s teicis to agrÄk darÄ«t pÄc lieta uz visiem laikiem, pÄrvietot 10 soÄ¼i, tas notiek, lai saglabÄtu turpinÄs un iet kamÄr es hit sarkano stop zÄ«mi un vispÄr pÄrtrauktu programmu. 

TÄtad, pat ja Jums nav izdarÄ«t, kÄ es varÄju padarÄ«t Scratch pÄrvietot ÄtrÄk pa ekrÄnu? VairÄk soÄ¼i, labi? TÄ vietÄ, lai dara 10 laikÄ, kÄpÄc ne mÄs iet uz priekÅ¡u un mainÄ«t kuri paredzÄti, ko tu propose-- 50? TÄpÄc tagad es esmu gatavojas noklikÅ¡Ä·iniet uz zaÄ¼o karogu, un, protams, viÅÅ¡ iet Ä¼oti Ätri. 

Un tas, protams, ir tikai izpausme animÄciju. Kas ir animÄcija? Tas tikai parÄda jums cilvÄka A viss Ä·ekars FotogrÄfiju tieÅ¡Äm, Ä¼oti, Ä¼oti Ätri. Un tÄpÄc, ja mÄs esam tikai spÄcÄ«gi viÅam pÄrcelties papildu pasÄkumus, mÄs esam tikai kam efekts bÅ«t izmaiÅas, kur viÅÅ¡ ir uz ekrÄna vÄl straujÄk laika vienÄ«bÄ. 

Tagad nÄkamais izaicinÄjums, es ierosinÄju bija, ir viÅam piepeÅ¡i pie malas. Un nezinot, kas puzzle gabali exist-- jo tas ir naudas sods ja Jums nav iegÅ«t ar posms challenge-- ko jÅ«s vÄlaties darÄ«t intuitÄ«vi? KÄ mums ir viÅam piepeÅ¡i atpakaÄ¼ un tÄlÄk, starp kreisi un pa labi? 

JÄ. TÄpÄc mums ir zinÄma veida no stÄvokÄ¼a, un mÄs Å¡Ä·iet, ir conditionals, tÄpÄc, lai runÄ, zem Control kategorijÄ. KurÅ¡ no Å¡iem blokiem mÄs, iespÄjams, vÄlas? JÄ, varbÅ«t, "ja, tad." TÄpÄc paziÅojums, ka starp dzeltenajiem blokiem MÄs esam Å¡eit, ir Å¡is "ja" vai Å¡is "ja, cits" bloks, kas bÅ«s Ä¼auj mums pieÅemt lÄmumu, lai to paveiktu vai to darÄ«t. Un jÅ«s pat varat nest tos darÄ«t vairÄkas lietas. Vai, ja jÅ«s esat nav Å¡eit aizgÄjuÅ¡i vÄl, iet uz priekÅ¡u uz uztveres kategoriju and-- pieÅemsim redzÄt, ja tas ir Å¡eit. 

TÄtad, ko bloks varÄtu bÅ«t noderÄ«ga lai noteiktu, vai viÅÅ¡ ir pie skatuves? JÄ, ievÄrosiet, ka daÅ¾i no Å¡iem blokiem var parametrized, lai runÄt. TÄs var kÄrtot pielÄgot, ne atÅ¡Ä·irÄ«bÄ no HTML vakar ar atribÅ«tiem, ja Å¡ie atribÅ«ti veida pielÄgot uzvedÄ«bu tag. TÄpat Å¡eit, es varu paÄ·ert Å¡o pieskaroties bloku un pÄrmaiÅas un uzdot jautÄjumu, JÅ«s pieskaras peles rÄdÄ«tÄju, piemÄram, kursora vai jÅ«s pieskaras malai? 

TÄpÄc Ä¼aujiet man iet un darÄ«t. Es esmu gatavojas tÄlinÄtu uz brÄ«di. Ä»aujiet man paÄ·ert Å¡o puzzle gabals Å¡eit, tas puzzle gabals tas, un es esmu gatavojas sajukt tos tikai brÄ«di. Es esmu gatavojas pÄrvietot to, mainÄ«t uz aizkustinoÅ¡s malai, un es esmu gatavojas kustÄ«bas izdarÄ«t. TÄtad, Å¡eit ir daÅ¾as sastÄvdaÄ¼as. Es domÄju, ka es esam ieguvuÅ¡i visu, ko es gribu. 

Vai kÄds gribÄtu ierosinÄt, kÄ es var savienot Å¡os varbÅ«t augÅ¡as uz leju Lai atrisinÄtu problÄmu, kam Scratch pÄrvietoties pa labi pa kreisi, pa labi, lai kreisÄs uz labÄs uz kreiso, katrs laiku tikai veselÄ«gs pie sienas? Ko es gribu darÄ«t? Kuru bloÄ·Ät man vajadzÄtu savienot ar "ZaÄ¼us karogs uzklikÅ¡Ä·inÄt pirmais"? 

Labi, tÄpÄc sÄksim ar "uz visiem laikiem." Kas iet iekÅ¡Ä nÄkamais? KÄds cits. OK, pÄrvietot darbÄ«bas. Viss kÄrtÄ«bÄ. Tad kas? TÄtad tad, ja. Un paziÅojums, lai gan tas izskatÄs iestiprinÄta kopÄ cieÅ¡i, tas bÅ«s tikai pieaugs aizpildÄ«t. Tas bÅ«s tikai ielÄkt kur es gribu to. 

Un ko es varu ievietot starp IF un tad? IespÄjams, "ja pieskaras malai." Un paziÅojums, atkal, tas ir pÄrÄk liels par to, bet tas pieaugs aizpildÄ«t. Un tad savukÄrt 15 grÄdiem? Cik grÄdiem? JÄ, tÄpÄc 180 bÅ«s spin mani visu ceÄ¼u apkÄrt. TÄtad, pieÅemsim redzÄt, ja es saÅÄmu Å¡Ä«s tiesÄ«bas. Ä»aujiet man attÄlinÄtu. 

Ä»aujiet man velciet Scratch augÅ¡u. TÄpÄc viÅÅ¡ ir nedaudz izkropÄ¼ota tagad, bet tas ir jauki. KÄ es varu reset viÅu viegli? Es esmu gatavojas nedaudz apkrÄptu. TÄpÄc es esmu pievienojot vÄl bloks, tikai, lai bÅ«tu skaidrs. Es gribu, lai viÅÅ¡ norÄda 90 grÄdiem pa labi pÄc noklusÄjuma, tÄpÄc es esmu tikai gatavojas pateikt viÅam to darÄ«t programmiski. Un Å¡eit mÄs ejam. MÄs, Å¡Ä·iet, esam darÄ«juÅ¡i. Tas ir nedaudz dÄ«vaini, jo viÅÅ¡ pastaigÄjas otrÄdi. Sauksim ka bug. Tas ir kÄ¼Å«da. Bug ir kÄ¼Å«da kÄdÄ programmai, loÄ£iska kÄ¼Å«da, ka es, cilvÄka, kas izgatavoti. KÄpÄc viÅÅ¡ iet kÄjÄm gaisÄ? Vai MIT skrÅ«vÄjamu augÅ¡u vai bija man? 

JÄ, es domÄju, tas nav MIT s vaina. ViÅi man iedeva puzzles gabaliÅam ka saka savukÄrt daÅ¾as grÄdiem. Un Viktorijas ierosinÄjumu, Es esmu pagrieziena 180 grÄdiem, kas ir pareizais intuÄ«cija. Bet pagrieÅ¾ot par 180 grÄdiem burtiski nozÄ«mÄ pagrieziena 180 grÄdiem, un tas nav Ä«sti ko es gribu, acÄ«mredzot. TÄpÄc, ka vismaz viÅÅ¡ ir Å Ä« divdimensiju pasaulÄ, tÄpÄc pagrieziena Ä«sti notiek uzsist viÅam otrÄdi. 

Es, iespÄjams, vÄlas izmantot to, ko bloÄ·Ät vietÄ, pamatojoties uz to, ko jÅ«s redzat Å¡eit? KÄ mÄs varÄtu noteikt Å¡o? JÄ, lai mÄs varÄtu norÄdÄ«t pretÄjÄ virzienÄ. Un patiesÄ«bÄ pat tas nebÅ«s pietiekami, tÄpÄc, ka mÄs varam tikai grÅ«ti kods lÄ«dz norÄdot pa kreisi vai pa labi. 

JÅ«s zinÄt, ko mÄs varÄtu darÄ«t? IzskatÄs, mums ir ÄrtÄ«bas bloks Å¡eit. Ja es tuvinÄtu, skatiet kaut kas mums patÄ«k Å¡eit? TÄ izskatÄs MIT ir abstrakcija uzcelta Å¡eit. Å is bloks, Å¡Ä·iet, ir lÄ«dzvÄrtÄ«ga uz kuru citi bloki, daudzskaitlis? 

Tas viens bloks, Å¡Ä·iet, ir lÄ«dzvÄrtÄ«ga uz Å¡o visu trio blokiem ka mÄs esam Å¡eit. TÄtad izrÄdÄs, es varÄtu vienkÄrÅ¡ot manu programma, atbrÄ«vojoties no visa, kas un vienkÄrÅ¡i ielieciet to Å¡eit. Un tagad viÅÅ¡ ir vÄl mazliet buggy, un tas ir labi tagad. MÄs ÅemÅ¡u atvaÄ¼inÄjumu, ka bÅ«s. Bet mana programma ir pat vienkÄrÅ¡Äk, un arÄ« tas, bÅ«tu reprezentatÄ«vi no mÄrÄ·is programming-- ir ideÄli padarÄ«t savu kodu, kÄ vienkÄrÅ¡i, kÄ kompakts vien iespÄjams, kamÄr vÄl ir kÄ lasÄma kÄ iespÄjams. JÅ«s nevÄlaties, lai padarÄ«tu to tik kodolÄ«ga ka tas ir grÅ«ti saprast. 

Bet paziÅojums es esmu aizstÄj trÄ«s bloki ar vienu, un tas varbÅ«t ir laba lieta. Esmu noÅ¡Ä·irts prom jÄdzienu pÄrbaudÄ«t, vai jÅ«s esat no malas ar tikai vienu bloku. Tagad mÄs varam bÅ«t jautri ar Å¡o, patiesÄ«bÄ. Tas nav pievienot tik daudz intelektuÄlÄ vÄrtÄ«ba, bet jautrs vÄrtÄ«ba. Es ieÅ¡u uz priekÅ¡u un paÄ·ert Å¡o skaÅu Å¡eit. TÄpÄc Ä¼aujiet man iet uz priekÅ¡u, un Ä¼aujiet man apturÄt programmu uz brÄ«di. Es esmu gatavojas ierakstÄ«t Å¡Ädu, Ä¼auj piekÄ¼Å«t manam mikrofonam. 

Te nu mÄs esam. Sakta. MÄÄ£inÄsim to atkal. Te nu mÄs esam. Labi, es ierakstÄ«ts nepareizi lieta. Te nu mÄs esam. Sakta. Sakta. Viss kÄrtÄ«bÄ. Tagad man ir nepiecieÅ¡ams, lai atbrÄ«votos no tÄ. Viss kÄrtÄ«bÄ. 

TÄpÄc tagad man ir ierakstÄ«Å¡ana tikai "Sakta". TÄpÄc tagad es ieÅ¡u priekÅ¡u un saucam "sakta". Es esmu gatavojas doties atpakaÄ¼ uz manu skriptu, un tagad paziÅojums tur ir Å¡is bloks, kas sauc atskaÅot skaÅu "Åau" vai atskaÅot skaÅu "sakta". Es esmu gatavojas vilkt to, un, ja Es bÅ«tu jÄliek Å¡is komiski efektu? JÄ, tÄpÄc tagad tas ir sava veida buggy, jo tagad tas block-- paziÅo, cik Å¡is "ja uz malu, Bounce "ir sava veida paÅ¡pietiekams. TÄpÄc man ir nepiecieÅ¡ams noteikt Å¡o. Ä»aujiet man iet uz priekÅ¡u un darÄ«t to. Ä»aujiet man atbrÄ«voties no Å¡o un doties atpakaÄ¼ mÅ«su oriÄ£inÄlam, vairÄk apzinÄta funkcionalitÄti. So ", ja pieskaras malai, tad" es gribu griezties, kÄ ierosinÄts Victoria, 180 grÄdi. Un vÄlos spÄlÄt skaÅa "sakta" tur? 

JÄ, pamanÄt, ka tas ir Ärpus ka dzeltenÄ bloks. TÄtad tas arÄ« bÅ«tu bug, bet es esmu ievÄrojis to. TÄpÄc es esmu gatavojas velciet to Å¡eit, un paziÅojums tagad tas ir iekÅ¡Ä ", ja." TÄtad ", ja" tas ir sava veida LÄ«dzÄ«ga rokas lÄ«dzÄ«gi Blot kas ir tikai gatavojas darÄ«t to, kas ir iekÅ¡pusÄ no tÄ. TÄpÄc tagad, ja es attÄlinÄtu at risks annoying-- 

Dators: Sakta, sakta, sakta. 

DAVID Malan: Un tas bÅ«s tikai iet uz visiem laikiem. Tagad tikai, lai paÄtrinÄtu lietas Å¡eit, Ä¼aujiet man iet uz priekÅ¡u un atvÄrt, pieÅemsim say-- Ä¼aujiet man iet uz kÄdu manas sÄ«kumi no klases. Un Ä¼aujiet man atvÄrt, teiksim, Å¡is viens, viens no mÅ«su mÄcÄ«bu stipendiÄtiem pÄris gadus atpakaÄ¼. TÄpÄc daÅ¾i no jums varÄtu atgÄdinÄt Å¡Ä« spÄle no vakardienas, un tas ir tieÅ¡Äm ievÄrojams. Pat ja mÄs esam darÄ«ts VienkÄrÅ¡Äkais programmu tieÅ¡i tagad, pieÅemsim apsvÄrt, ko tas tieÅ¡Äm izskatÄs. Ä»aujiet man hit spÄli. 

TÄtad Å¡ajÄ spÄlÄ, mums ir varde, un izmantojot bultiÅas keys-- viÅÅ¡ Åem lielÄkus pasÄkumus, nekÄ es remember-- Man ir kontrole pÄr Å¡o varde. Un mÄrÄ·is ir iegÅ«t pÄri aizÅemts ceÄ¼Å¡ bez nokÄ¼Å«Å¡anu automaÅ¡Ä«nÄm. Un pieÅemsim see-- ja es iet uz augÅ¡u Å¡eit, es jÄgaida log lai ritinÄtu lÄ«dz. Tas jÅ«tas kÄ bug. Tas ir sava veida bug. Viss kÄrtÄ«bÄ. Es esmu par to Å¡eit, tur, un tad jÅ«s turÄt iet, kamÄr jums visiem vardes uz lilija spilventiÅi. Tagad tas varÄtu izskatÄ«ties vÄl sareÅ¾Ä£Ä«tÄka, bet pieÅemsim mÄÄ£inÄt lauzt Tas noteikti garÄ«gi un mutiski uz tÄs sastÄvdaÄ¼u blokiem. TÄtad ir iespÄjams, puzzle gabals, kas mÄs neesam redzÄjuÅ¡i vÄl bet tas ir reaÄ£Ät uz keystrokes, uz lietÄm, ko es hit uz klaviatÅ«ras. 

TÄtad tur ir iespÄjams, sava veida bloks, kas saka, ja atslÄga vienÄds augÅ¡u, tad kaut ko darÄ«t ar Scratch-- varbÅ«t pÄrvietot to 10 soÄ¼us Å¡ajÄ virzienÄ. Ja uz leju taustiÅÅ¡ ir nospiests, pÄrvietot 10 soÄ¼i Å¡ÄdÄ veidÄ, vai kreiso taustiÅu, pÄrvietojiet 10 soÄ¼i Å¡ÄdÄ veidÄ, 10 soÄ¼us, kas. Es esmu skaidri pagriezÄs kaÄ·i par varde. TÄtad tas ir tikai tad, ja kostÄ«ms, kÄ Scratch zvani it-- mÄs tikai imports priekÅ¡statu par varde. 

Bet ko vÄl notiek? KÄdi citi koda rindiÅas, ko citi puzzle gabalus darÄ«ja Blake, mÅ«su mÄcÄ«bu kolÄÄ£i, izmanto Å¡ajÄ programmÄ, acÄ«mredzot? Kas padara visu move-- kÄda programmÄÅ¡anas bÅ«vÄt? 

KustÄ«bas, sure-- tÄpÄc pÄrvietot bloku, for sure. Un, kas ir tas gÄjiens bloks iekÅ¡pusÄ, visticamÄk? JÄ, sava veida cilpas, varbÅ«t mÅ«Å¾Ä«gi bloÄ·Ät, varbÅ«t atkÄrtot block-- atkÄrto, lÄ«dz bloku. Un tas, ko ir padarot Å¾urnÄlus un lilija spilventiÅi un viss pÄrÄjais pÄrvietot uz priekÅ¡u un atpakaÄ¼. Tas ir vienkÄrÅ¡i notiek bezgalÄ«gi. 

KÄpÄc daÅ¾i no automaÅ¡Ä«nÄm pÄrvietojas ÄtrÄk nekÄ citi? Kas ir atÅ¡Ä·irÄ«gs par Å¡o programmu? JÄ, iespÄjams, daÅ¾i no tiem ir veikt vairÄk soÄ¼i uzreiz un daÅ¾i no tiem mazÄk soÄ¼i uzreiz. Un vizuÄlo efektu ir Ätra pret lÄns. 

Ko jÅ«s domÄjat noticis? Kad es saÅÄmu savu varde visu ceÄ¼u pÄri ielai un upi uz lilija pad, kaut ievÄrÄ«bas cienÄ«gs noticis. Kas notika, tiklÄ«dz es to izdarÄ«ju? Tas apstÄjÄs. Ka varde apstÄjÄs, un Man otro varde. TÄtad, ko bÅ«vÄt, jÄbÅ«t izmantoti tur, kÄda funkcija? 

JÄ, tÄpÄc tur ir sava veida "Ja" stÄvoklÄ« tur, too. Un izrÄdÄs out-- mÄs neredzÄju this-- bet tur ir citi bloki tur, ka var teikt, ja jums ir aizkustinoÅ¡s cita lieta, uz ekrÄna, ja jÅ«s pieskaras lilija spilventiÅu ", tad." Un tad tas ir tad, kad mÄs padarÄ«t otrais varde parÄdÄs. TÄtad, pat ja Å¡Ä« spÄle ir noteikti Ä¼oti datÄta, lai gan pÄc pirmÄ acu uzmetiena tur ir tik daudz kas notiek on-- un Blake nebija pÄtagu Å¡o augÅ¡u divÄs minÅ«tÄs, tas, iespÄjams, veica viÅam vairÄkas stundas, lai radÄ«tu Å¡o spÄli pamatojoties uz viÅa atmiÅÄ vai video vakardienas versiju par to. Bet visiem Å¡iem sÄ«kumiem notiek uz ekrÄna izolÄti vÄrÄ«ties uz leju, lai tie Ä¼oti vienkÄrÅ¡i constructs-- kustÄ«bas vai paziÅojumi kÄ mÄs esam apspriests, cilpas un nosacÄ«jumi, un tas ir par to. Ir daÅ¾i citi mÄ«Ä¼otÄjs iezÄ«mes. DaÅ¾as no tÄm ir tÄ«ri estÄtiska vai akustisko, tÄpat skaÅÄm es tikko spÄlÄja ar. Bet lielÄkÄ daÄ¼a, jÅ«s ir Å¡ajÄ valodu, nulles, visas pamata celtniecÄ«bas bloki, kas jums ir C, Java, JavaScript, PHP, Ruby, Python, un jebkÄdu skaitu citÄs valodÄs. Visus jautÄjumus par nulles? Viss kÄrtÄ«bÄ. TÄpÄc mÄs ne dziÄ¼Äk nirt lÄ«dz nulles, ja jÅ«s esat laipni Å¡Ä«s nedÄÄ¼as nogalÄ, it Ä«paÅ¡i, ja jums ir bÄrni vai nieces un brÄÄ¼a un tÄdi, iepazÄ«stinÄt viÅus ar nulles. Tas ir tieÅ¡Äm lieliski jautrs vide ar, jo tÄ autori saka, Ä¼oti augstie griesti. Pat ja mÄs sÄkÄm ar Ä¼oti zema lÄ«meÅa detaÄ¼as, jÅ«s tieÅ¡Äm var izdarÄ«t diezgan daudz ar to, un tas, iespÄjams, demonstrÄÅ¡ana tieÅ¡i tÄ. 

Bet pieÅemsim tagad pÄriet uz kÄdu vairÄk sareÅ¾Ä£Ä«tas problÄmas, ja jÅ«s, pazÄ«stams kÄ "meklÄÅ¡ana" un "Å Ä·iroÅ¡anas," kopumÄ. Mums bija Å¡is tÄlrunis grÄmata earlier-- Å¡eit vÄl viena tikai discussion-- ka mÄs varÄjÄm meklÄt efektÄ«vÄk, jo par bÅ«tisku pieÅÄmumu. Un tikai, lai bÅ«tu skaidrs, ko pieÅÄmums bija I padarot ja meklÄ, izmantojot Å¡o tÄlruÅa grÄmatu? Tas Mike Smith bija tÄlrunis grÄmatu, lai gan I varÄtu rÄ«koties scenÄrijs bez viÅa tur, ja es vienkÄrÅ¡i apstÄjÄs priekÅ¡laicÄ«gi. GrÄmata ir alfabÄta. Un tas ir Ä¼oti dÄsna pieÅÄmums, jo tas nozÄ«mÄ someone-- es esmu veida grieÅ¡anas stÅ«ri, piemÄram, es esmu ÄtrÄk, jo kÄdam cits darÄ«ja daudz smaga darba par mani. 

Bet ko tad, ja tÄlrunis GrÄmata tika NesaÅ¡Ä·irotas? VarbÅ«t Verizon got slinks, vienkÄrÅ¡i izmeta ikviena vÄrdi un numuri, kas tur varbÅ«t tÄdÄ secÄ«bÄ, kÄdÄ tie pierakstÄ«jies tÄlruÅa pakalpojums. Un cik daudz laika tas mani atrast kÄdu, piemÄram, Mike Smith? 1,000 lapa tÄlrunis book-- cik lapas man ir skatÄ«ties cauri? 

Visus. JÅ«s esat veida no luck. JÅ«s burtiski ir jÄskatÄs uz katru lapa, ja tÄlrunis grÄmata ir tikai nejauÅ¡i sakÄrtoti. JÅ«s varÄtu saÅemt laimÄ«gs un atrast Mike par paÅ¡u pirmo lapu, jo viÅÅ¡ bija pirmais klients pasÅ«tÄ«t tÄlruÅa pakalpojums. Bet viÅÅ¡ varÄtu bÅ«t pÄdÄjais, too. 

TÄtad izlases rÄ«kojums nav labs. TÄtad pieÅemsim, ka mums ir sakÄrtot tÄlruÅu grÄmatu vai vispÄr kÄrtoÅ¡anas datiem ka mÄs esam dota. KÄ mÄs varam darÄ«t? 

Nu, Ä¼aujiet man tikai mÄÄ£inÄt vienkÄrÅ¡s piemÄrs Å¡eit. Ä»aujiet man iet uz priekÅ¡u un mÄtÄt daÅ¾i skaitÄ¼i uz kuÄ£a. PieÅemsim, ciparus mums ir, ir, teiksim, Äetri, divi, viens, un trÄ«s. Un, Ben, kÄrtot Å¡os skaitÄ¼us par mums. 

Labi. KÄ tu to izdarÄ«ji? Viss kÄrtÄ«bÄ. TÄtad, sÄkt ar mazÄko vÄrtÄ«ba un augstÄkais, un tas ir patieÅ¡Äm labs intuÄ«cija. Un saprast, ka mÄs cilvÄki ir faktiski diezgan labi problÄmu risinÄÅ¡ana piemÄram, tas, vismaz kad dati ir salÄ«dzinoÅ¡i neliels. TiklÄ«dz jÅ«s sÄkat ir simtiem skaitÄ¼u, tÅ«kstoÅ¡iem numuru, miljoniem numuru, Ben iespÄjams nevar darÄ«t to gluÅ¾i tik Ätri, pieÅemot, ka tur bija nepilnÄ«bas numuriem. Diezgan viegli saskaitÄ«t uz miljonu pretÄjÄ gadÄ«jumÄ, tikai laikietilpÄ«ga. 

TÄtad algoritms izklausÄs tÄpat Ben izmanto tikai tagad bija meklÄt mazÄko numuru. TÄtad, pat ja mÄs cilvÄkiem varam veikt ir daudz informÄcijas vizuÄli, dators ir faktiski nedaudz vairÄk ierobeÅ¾ota. Dators var tikai apskatÄ«t vienu baits laikÄ vai varbÅ«t Äetri baiti at a LAIKU_ Å¡ajÄs dienÄs varbÅ«t 8 baiti at a LAIKU_ bet Ä¼oti neliels skaits baitu noteiktÄ laikÄ. 

TÄpÄc, ka mums tieÅ¡Äm ir Äetras atseviÅ¡Ä·as vÄrtÄ«bas here-- un jÅ«s varat iedomÄties Ben kÄ ar acu aizsegi uz ja viÅÅ¡ bÅ«tu dators, piemÄram ka viÅÅ¡ nevar redzÄt neko citu nekÄ vienu numuru pie LAIKU_ tÄpÄc mÄs parasti pieÅemam, tÄpat kÄ AngÄ¼u, mÄs lasÄ«t no labÄs uz kreiso. TÄtad pirmais numurs Ben iespÄjams izskatÄ«jÄs at bija Äetri, un tad Ä¼oti Ätri sapratu, ka ir diezgan liels number-- Ä¼aujiet man glabÄt meklÄjat. 

Tur ir divi. Uzgaidi minÅ«ti. Divi ir mazÄks nekÄ Äetri. Es esmu gatavojas atcerÄties. Divi Å¡obrÄ«d ir mazÄkais. Tagad one-- tas ir pat labÄk. Tas ir vÄl mazÄka. Es esmu gatavojas aizmirst par divÄm un tikai atcerieties vienu tagad. 

Un viÅÅ¡ varÄja apstÄties meklÄ? Nu, viÅÅ¡ varÄja balstÄ«ta uz Å¡o informÄciju, bet viÅÅ¡ labÄk meklÄÅ¡anu pÄrÄjÄ saraksta. Jo ko tad, ja nulles bija sarakstÄ? Ko darÄ«t, ja negatÄ«vs viens bija sarakstÄ? ViÅÅ¡ tikai zina, ka viÅa atbildi ir pareiza, ja viÅÅ¡ ir izsmeÄ¼oÅ¡i pÄrbauda visu sarakstu. TÄtad mÄs skatÄmies uz pÄrÄjo Å¡o. Three-- tas bija laika izÅ¡Ä·ieÅ¡ana. Got nelaimÄ«gs, bet es biju vÄl pareizi to darÄ«t. Un tÄpÄc tagad viÅÅ¡, iespÄjams, izvÄlÄts mazÄkais skaits un vienkÄrÅ¡i ielieciet to sÄkumÄ no saraksta, jo es darÄ«Å¡u Å¡eit. Tagad to, ko jÅ«s darÄ«t tÄlÄk, lai gan Jums nav jÄdomÄ par to gandrÄ«z tÄdÄ mÄrÄ? AtkÄrtojiet Å¡o procesu, tÄpÄc daÅ¾i veida cilpu. Tur ir pazÄ«stams ideja. TÄtad, Å¡eit ir Äetri. PaÅ¡laik tas ir mazÄkais. Tas ir kandidÄts. Vairs nÄ. Tagad es esmu redzÄjis divus. Tas ir nÄkamais mazÄkais elements. Three-- tas nav mazÄks, tÄpÄc Tagad Ben var raut ÄrÄ divas. 

Un tagad mÄs atkÄrtojiet procesu, un protams trÄ«s izpauÅ¾as izvilka nÄkamo. AtkÄrtojiet procesu. Äetri izpauÅ¾as velk ÄrÄ. Un tagad mÄs esam ÄrÄ no skaitÄ¼iem, tÄdÄÄ¼ saraksts ir sakÄrtots. 

Un tieÅ¡Äm, tas ir formÄls algoritms. Dators zinÄtnieks bÅ«tu aicinu Å¡o "atlases veida," ideja ir sava uzskaitÄ«t iteratively-- atkal un atkal un atkal izvÄloties mazÄkais skaits. Un, kas ir jauki, par to ir tas ir tikai tik darn intuitÄ«vs. Tas ir tik vienkÄrÅ¡i. Un jÅ«s varat atkÄrtot to paÅ¡u darbÄ«ba atkal un atkal. Tas ir vienkÄrÅ¡i. 

Å ajÄ gadÄ«jumÄ tÄ bija Ätri, bet cik ilgi tas tieÅ¡Äm Åemt? PadarÄ«sim to, Å¡Ä·iet, un justies mazliet vairÄk garlaicÄ«gs. TÄtad, viens, divi, trÄ«s, Äetri, pieci seÅ¡i, septiÅi, astoÅi, deviÅi, 10, 11, 12, 13, 14, 15, 16-- jebkuram skaitam. Es tikai gribÄju vÄl Å¡o laiks nekÄ tikai Äetri. TÄtad, ja es esam ieguvuÅ¡i visu Ä·ekars numuriem now-- to nav pat svarÄ«gi ko viÅi are-- pieÅemsim domÄju par to, ko tas algoritms tieÅ¡Äm ir lÄ«dzÄ«gi. 

PieÅemsim, ka skaitÄ¼i tur. Atkal, nav svarÄ«gi, ko viÅi ir, bet viÅi nejauÅ¡i. Es esmu piemÄrojot Ben algoritmu. Man vajag, lai izvÄlÄtos mazÄko numuru. Ko man darÄ«t? Un es esmu gatavojas fiziski darÄ«t to Å¡oreiz rÄ«koties to ÄrÄ. Looking, looking, looking, looking, looking. Tikai ar laiku es nokÄ¼Å«t beigÄm, sarakstu var Es saprotu, mazÄkais skaits bija divi Å¡oreiz. Viens nav sarakstÄ. TÄpÄc es nolikt divi. 

Ko man darÄ«t tÄlÄk? Looking, looking, looking, looking. Tagad es atradu numurs septiÅi, jo tur ir nepilnÄ«bas Å¡ajÄs numbers-- bet tikai patvaÄ¼Ä«gi. Viss kÄrtÄ«bÄ. TÄpÄc tagad es varu nolikt septiÅi. Raugoties meklÄ, meklÄ. 

Tagad es esmu pieÅemot, no Protams, ka Ben nav ir papildus RAM, extra atmiÅa, jo, protams, Es skatos uz to paÅ¡u numuru. Protams, es varÄtu bÅ«t atcerÄjos visiem Å¡iem numuriem, un tas ir absolÅ«ti patiess. Bet, ja Ben atceras visu no numuriem, viÅÅ¡ ir redzÄjis, viÅÅ¡ nav Ä«sti veikts bÅ«tisks progress jo viÅÅ¡ jau ir spÄja, lai meklÄtu cauri numuriem uz kuÄ£a. Atceroties visi numuri nepalÄ«dz, jo viÅÅ¡ vÄl var kÄ dators tikai apskatÄ«t, mÄs esam teica, viens numurs laikÄ. TÄpÄc nav sava veida apkrÄptu tur, ka jÅ«s varat sviras. 

TÄtad patiesÄ«bÄ, jo es turpinÄt meklÄÅ¡anu sarakstu, Es burtiski ir tikai glabÄt iet un atpakaÄ¼ caur to, noplÅ«kÅ¡anas out nÄkamais mazÄkais skaits. Un, kÄ jÅ«s varat veida secinÄt no manas dumjÅ¡ kustÄ«bas, tas tikai kÄ¼Å«st Ä¼oti garlaicÄ«gs Ä¼oti Ätri, un man Å¡Ä·iet, iet atpakaÄ¼ un tÄlÄk, un atpakaÄ¼ pavisam nedaudz. Tagad, lai bÅ«tu godÄ«gi, man nav jÄiet gluÅ¾i kÄ, labi, pieÅemsim see-- tÄ bÅ«tu godÄ«ga, Man nav staigÄt diezgan jo daudzi soÄ¼i katru reizi. Jo, protams, kÄ es izvÄlÄties numurus no saraksta, atlikuÅ¡ais saraksts kÄ¼Å«st Ä«sÄks. 

Un tÄpÄc pieÅemsim domÄt par cik soÄ¼us es esmu patieÅ¡Äm traipsing caur katru reizi. PaÅ¡Ä pirmajÄ situÄcijÄ mums bija 16 numuri, un tÄ maximally-- pieÅemsim tikai izdarÄ«t par discussion-- Man nÄcÄs meklÄt caur 16 numurus, lai atrastu vismazÄko. Bet tad, kad es noplÅ«ktas out mazÄkais skaits, kÄ sen bija atlikuÅ¡o sarakstu, protams? Tikai 15. Tik, cik skaitÄ¼u darÄ«ja Ben vai man ir meklÄt, izmantojot otro reizi apkÄrt? 15, vienkÄrÅ¡i iet un atrast mazÄko. Bet tagad, protams, saraksts, ArÄ«, mazÄks nekÄ tas bija agrÄk. Tik cik soÄ¼us darÄ«ja I ir jÄÅem nÄkamreiz? 14 un pÄc tam 13 un pÄc tam 12, plus dot, dot, dot, kamÄr es esmu palicis tikai ar vienu. TÄpÄc tagad dators zinÄtnieks bÅ«tu jautÄt, labi, ko dara, ka visi vienlÄ«dzÄ«gi? Tas faktiski ir vienÄds ar kÄdu konkrÄtu numurs, kas mÄs varÄtu noteikti do aritmÄtiski, bet mÄs gribam runÄt par efektivitÄti algoritmu vairÄk formulaically maz, neatkarÄ«gi no cik ilgi saraksts ir. 

Un, lai jÅ«s zinÄt, ko? Tas ir 16, bet, piemÄram, es teicu iepriekÅ¡, pieÅemsim tikai zvanÄ«t izmÄru problÄmas n, kur n ir daÅ¾i numurs. VarbÅ«t tas ir 16, varbÅ«t tÄ ir trÄ«s, varbÅ«t tas ir miljons. Es nezinu. Man vienalga. Ko es tieÅ¡Äm gribu ir formula, kas es varu izmantot, lai salÄ«dzinÄtu Å¡o algoritmu pret citiem algoritmiem ka kÄds varÄtu apgalvot ir labÄk vai sliktÄk. 

TÄtad izrÄdÄs, un tikai es zinÄm no pakÄpÄ skolÄ, ka tas faktiski darbojas, lai pats lieta kÄ n pÄr n plus viens pa diviem. Un tas notiek ar vienÄds, no Protams, n brusas plus n pa diviem. TÄtad, ja es gribÄju formulu uz cik soÄ¼iem tika iesaistÄ«ti meklÄ vispÄr no Å¡iem numuriem atkal un atkal un atkal un atkal, es teiktu tas n brusas plus n pa diviem. Bet jÅ«s zinÄt, ko? Tas tikai izskatÄs netÄ«rs. Es tikai tieÅ¡Äm gribu vispÄrÄjÄ sajÅ«ta lietÄm. Un jÅ«s varÄtu atgÄdinÄt no vidusskola, ka ir jÄdziens augstÄko pasÅ«tÄ«juma termiÅÄ. KurÅ¡ no Å¡iem noteikumiem, tad n brusas, N, vai pusi, ir vislielÄkÄ ietekme laika gaitÄ? Jo lielÄks n izpauÅ¾as, kas no Å¡iem jautÄjumiem visvairÄk? 

Citiem vÄrdiem sakot, ja es plug no miljona, n kvadrÄtÄ bÅ«s, visticamÄk, dominÄjoÅ¡ais faktors, jo miljons reiÅ¾u pati par sevi ir daudz lielÄks nekÄ plus vienu papildu miljoni. TÄtad, jÅ«s zinÄt, ko? Tas ir tik darn liels numurs, ja jÅ«s kvadrÄtveida numuru. Tas nav Ä«sti jautÄjums. MÄs esam tikai gatavojas Å¡Ä·Ärsot ÄrÄ un aizmirst par to. Un tÄ dators zinÄtnieks teiktu ka efektivitÄte Å¡ajÄ algoritma ir par kÄrtÄ«bu n squared-- Es domÄju patiesi tuvinÄÅ¡anu. TÄ ir sava veida rupji n brusas. Laika gaitÄ, jo lielÄka un lielÄka n izpauÅ¾as, Å¡is ir labs novÄrtÄjums par to, ko efektivitÄte vai trÅ«kums efektivitÄtes Å Ä« algoritma patiesÄ«bÄ ir. Un es iegÅ«tu, ka, protams, no faktiski dara math. Bet tagad es esmu tikai vicinÄÅ¡anu manas rokas, jo es tikko vÄlas vispÄrÄju sajÅ«tu Å¡o algoritmu. 

TÄtad, izmantojot to paÅ¡u loÄ£iku, tikmÄr, pieÅemsim apsvÄrt citu algoritmu mÄs jau izskatÄ«jÄs at-- lineÄru meklÄÅ¡anu. Kad man bija meklÄjot par tÄlruni book-- ne Å¡Ä·iroÅ¡anu to, meklÄjot pa tÄlruni book-- mÄs tur saka, ka tas bija 1000 pakÄpieni, vai 500 pakÄpieni. Bet pieÅemsim vispÄrinÄt to. Ja tur ir n lapas tÄlrunis grÄmatu, kas ir darbÄ«bas laiks vai efektivitÄte lineÄro meklÄt? Tas ir par kÄrtÄ«bu cik soÄ¼us, lai atrastu Mike Smith izmantojot lineÄro meklÄÅ¡anu, tad Pirmais algoritms, vai pat otrais? 

SliktÄkajÄ gadÄ«jumÄ, Mike ir beigÄs grÄmatas. TÄtad, ja tÄlrunis grÄmata ir 1000 lappuses, mÄs teicÄm pÄdÄjo reizi, sliktÄkajÄ gadÄ«jumÄ, tas var aizÅemt aptuveni cik daudzas lapas, lai atrastu Mike? TÄpat 1000. Tas augÅ¡Äjo robeÅ¾u. Tas ir iespÄjams, vissliktÄkÄ situÄcija. Bet atkal, mÄs esam pÄrvietojas prom no skaitÄ¼iem, piemÄram, 1000 tagad. Tas ir tikai n. 

TÄtad, kas ir loÄ£isks secinÄjums? MeklÄjot Mike ar tÄlruni GrÄmata, kas ir n lapas varÄtu veikt, jo Ä¼oti sliktÄkajÄ gadÄ«jumÄ, cik soÄ¼us par kÄrtÄ«bu n? Un tieÅ¡Äm dators zinÄtnieks teiktu ka braukÅ¡anas laikÄ, vai sniegumu vai efektivitÄte vai neefektivitÄti, par algoritmu, piemÄram, lineÄra meklÄÅ¡anu ir kÄrtÄ«bÄ no n. Un mÄs varam piemÄrot vienÄdi loÄ£ika Å¡Ä·Ärsojot kaut ko kÄ es tikko darÄ«ju uz otro algoritms mums bija ar tÄlruÅa grÄmatu, kur mÄs devÄmies divas lapas vienlaikus. 

TÄtad 1000 lapa tÄlruÅu grÄmata varÄtu mÅ«s 500 lapa pagriezienus, plus viens ja mÄs dubultÄ atpakaÄ¼ mazliet. TÄtad, ja tÄlrunis grÄmata ir n lapas, bet mÄs darÄm divas lapas vienlaicÄ«gi, tas ir aptuveni, ko? N virs diviem, tÄ ka ir kÄ n pÄr diviem. Bet es sniedza pieprasÄ«t pirms brÄ«Å¾a ka n pÄr two-- tas ir sava veida tÄds pats kÄ tikai n. Tas ir tikai nemainÄ«gs faktors, datorzinÄtnieku teiktu. PieÅemsim tikai koncentrÄties uz mainÄ«gie lielumi, really-- lielÄkais mainÄ«gie vienÄdojumu. 

TÄtad lineÄrÄ meklÄt, vai izdarÄ«t vienu lapu laikÄ, vai divas lappuses tÄdÄ laikÄ, ir sava veida bÅ«tÄ«bÄ ir tas pats. Tas joprojÄm ir par kÄrtÄ«bu n. Bet es pieprasÄ«ja ar manu attÄlu agrÄk ka treÅ¡ais algoritms nebija lineÄrs. Tas nebija taisna lÄ«nija. Tas bija, ka izliekta lÄ«nija, kÄ arÄ« algebriskÄ formula tur bija tas, ko? Log N- tÄ log n bÄzi divi. Un mums nav iedziÄ¼inÄties pÄrÄk daudz sÄ«kÄk par logaritmu Å¡odien, bet lielÄkÄ daÄ¼a datoru zinÄtnieki nebÅ«tu pat pateikt, kÄda bÄze ir. Jo tas viss ir tikai konstante faktori, tÄ sakot, tikai nelielas ciparu atÅ¡Ä·irÄ«bas. Un tÄ tas bÅ«tu Ä¼oti bieÅ¾i veids, Ä«paÅ¡i formÄlÄs datoru zinÄtnieki kuÄ£a vai programmÄtÄji pie baltÄ tÄfele faktiski apgalvojot kas algoritms viÅi varÄtu izmantot vai kÄds efektivitÄte par to algoritms ir. 

Un tas ne vienmÄr ir kaut kas jÅ«s apspriest jebkurÄ detalizÄti, bet labs programmÄtÄjs ir kÄds, kas ir ciets, oficiÄlu fona. ViÅÅ¡ ir spÄjÄ«gs runÄt Jums Å¡Äda veida veidÄ un faktiski padara kvalitatÄ«vi argumenti par kÄpÄc viens algoritms vai viens gabals programmatÅ«ru ir pÄrÄka kaut kÄdÄ veidÄ uz citu. TÄpÄc, ka jÅ«s varÄtu noteikti ieskriet viena cilvÄka programmu un saskaitÄ«t sekundes kas nepiecieÅ¡ams, lai kÄrtotu daÅ¾us numurus, un jÅ«s varat palaist kÄdu otras personas programma un saskaitÄ«t SekunÅ¾u tas aizÅem. Bet tas ir vispÄrÄ«gÄks tÄ, ka JÅ«s varat izmantot, lai analizÄtu algoritmus, ja jÅ«s, vienkÄrÅ¡i uz papÄ«ra vai tikai mutiski. Bez pat rÄdÄ«t to, bez pat mÄÄ£ina izlases ieejas, JÅ«s varat vienkÄrÅ¡i iemesls caur to. Un tÄ ar nomu attÄ«stÄ«tÄjs vai ja kam viÅam vai viÅai veida apgalvo, lai jums kÄpÄc to algoritmu, viÅu noslÄpums mÄrce meklÄÅ¡anai miljardiem web lapas savam UzÅÄmums ir labÄk, Å¡ie ir par argumentu veidus tie ideÄli bÅ«tu iespÄja izdarÄ«t. Vai vismaz tie ir veidu lietas kas nÄks klajÄ diskusijÄ, at Vismaz Ä¼oti formÄlu diskusiju. Viss kÄrtÄ«bÄ. TÄtad Ben ierosinÄja kaut ko sauc izvÄle kÄrtoÅ¡anas. Bet es esmu gatavojas ierosinÄt, ka tur ir citi veidi, kÄ to izdarÄ«t, too. Ko man nav tieÅ¡Äm patÄ«k par Bena algoritmu ir tas, ka viÅÅ¡ tur kÄjÄm, vai kam man iet, un atpakaÄ¼ un uz priekÅ¡u un atpakaÄ¼ un uz priekÅ¡u un atpakaÄ¼. Ko darÄ«t, ja tÄ vietÄ, es bÅ«tu darÄ«t kaut kas lÄ«dzÄ«gs Å¡iem skaitÄ¼iem Å¡eit un man bija tikai nodarbojas ar katru skaits, savukÄrt, kÄ es esmu izdarÄ«jusi? 

Citiem vÄrdiem sakot, Å¡eit ir mans saraksts numuru. Äetri, viens, trÄ«s, divi. Un es esmu gatavojas darÄ«t turpmÄk. Es esmu gatavojas ievietot numurus kur tie pieder drÄ«zÄk nekÄ izvÄloties tos pa vienam. Citiem vÄrdiem sakot, Å¡eit ir numurs Äetri. 

Te ir mana sÄkotnÄjÄ sarakstÄ. Un es esmu gatavojas, lai saglabÄtu bÅ«tÄ«bÄ jaunu sarakstu Å¡eit. TÄtad tas ir vecais saraksts. Tas ir jauns saraksts. Es redzu skaits Äetri pirmÄs. Mans jaunais saraksts ir sÄkotnÄji tukÅ¡s, tÄpÄc tas ir trivially gadÄ«jums ka Äetri tagad asorti sarakstu. Es esmu tikai Åemot skaitu es esmu dota, un es varÄÅ¡u to manÄ jaunajÄ sarakstÄ. 

Vai Å¡is jaunais saraksts sakÄrtots? JÄ. Tas ir muÄ¼Ä·Ä«gi, jo tur ir tikai viens elements, bet tas ir absolÅ«ti sakÄrtoti. Nav nekas nevietÄ. Tas ir daudz interesantÄk, Å¡is algoritms, kad es pÄriet uz nÄkamo soli. 

Tagad man ir viens. TÄtad viena, protams, pieder pie sÄkumÄ vai beigÄs Å¡Ä« jaunÄ saraksta? SÄkums. TÄpÄc man ir darÄ«t kÄdu darbu tagad. Esmu bijis Åemot daÅ¾i brÄ«vÄ«bu ar manu marÄ·ieri , tikai zÄ«mÄÅ¡anas lietas kur es gribu viÅus, bet tas nav Ä«sti precÄ«zs datorÄ. Dators, kÄ mÄs zinÄm, ir RAM vai Random Access Memory, un tas ir viens baits un citu baitu un citu baitu. Un, ja jums ir gigabaita RAM, jums ir miljards baitu, bet viÅi fiziski vienÄ vietÄ. JÅ«s varat ne tikai pÄrvietot sÄ«kumi apkÄrt vÄrÅ¡ot to uz kuÄ£a kur vien tu vÄlies. TÄtad, ja mans jaunais saraksts ir Äetras vietas atmiÅÄ, diemÅ¾Äl Äetri ir jau nepareizÄ vietÄ. 

TÄtad, lai ievietotu numuru viens Es nevaru vienkÄrÅ¡i izdarÄ«t to Å¡eit. Å Ä« vieta atmiÅÄ neeksistÄ. Tas bÅ«tu krÄpÅ¡anos, un man ir bijis krÄpÅ¡anos gleznieciski uz daÅ¾Äm minÅ«tÄm Å¡eit. Tik tieÅ¡Äm, ja es gribu, lai vienu Å¡eit, Man ir uz laiku kopÄt Äetri un tad ielieciet vienu tur. 

Tas ir jauki, ka ir pareizi, tas ir tehniski iespÄjams, bet saprotu, ka ir papildu darbs. Es neesmu vienkÄrÅ¡i ielieciet numuru vietÄ. Es pirmo reizi nÄcÄs pÄrcelties numurs, tad ielieciet to vietÄ, tÄpÄc es veida dubultojies manu darba apjomu. Lai saglabÄtu, ka prÄtÄ. 

Bet es esmu tagad darÄ«ts ar Å¡o elementu. Tagad es gribu, lai greifers numuru trÄ«s. Kur, protams, tas pieder? Starp. Es nevaru pievilt vairs un vienkÄrÅ¡i ielieciet to tur, jo, atkal, Å¡Ä« atmiÅa ir fiziskÄs atraÅ¡anÄs vietas. TÄpÄc man ir kopÄt Äetriem un nodot trÄ«s vairÄk nekÄ Å¡eit. Nav liels darÄ«jumu. Tas ir tikai viens papildu solis again-- jÅ«tas Ä¼oti lÄti. 

Bet tagad es pÄriet uz diviem. Abi, protams, pieder Å¡eit. Tagad jÅ«s sÄkat redzÄt, kÄ darbu var uzkrÄt. Tagad to, kas man ir jÄdara? JÄ, man ir, lai pÄrvietotu Äetri, Man tad ir kopÄt trÄ«s, un tagad es varu ievietot divas. Un loms ar Å¡o algoritms, interesanti ir tas, ir tas, ka pieÅemsim, mums ir vairÄk ekstrÄms gadÄ«jums, kad tas ir teiksim astoÅi, septiÅi, seÅ¡i, pieci, Äetri, trÄ«s, divi, viens. Tas ir, daudzos kontekstos, sliktÄkajÄ gadÄ«jumÄ, jo darn lieta ir burtiski atpakaÄ¼. 

Tas nav Ä«sti ietekmÄt Ben algoritmu, jo Bena atlasÄ KÄrtot viÅÅ¡ gatavojas glabÄt iet uz priekÅ¡u un atpakaÄ¼ pa sarakstu. Un tÄpÄc, ka viÅÅ¡ vienmÄr meklÄ cauri visai atlikuÅ¡o sarakstÄ, tas nav svarÄ«gi kur elementi ir. Bet Å¡ajÄ gadÄ«jumÄ ar manu ievietojot approach-- pamÄÄ£inÄsim Å¡o. 

TÄtad, viens, divi, trÄ«s, Äetri, pieci, seÅ¡i, septiÅi, astoÅi. Viens divi trÄ«s Äetri, pieci, seÅ¡i, septiÅi, astoÅi. Es esmu gatavojas pieÅemt astoÅiem, un kur es varu likt to? Nu, sÄkumÄ manu sarakstu, jo Å¡is jaunais saraksts ir sakÄrtots. Un es Å¡Ä·Ärsot to ÄrÄ. 

Kur es varu nodot septiÅi? Darn to. Tas nepiecieÅ¡ams, lai iet tur, tÄpÄc Man ir darÄ«t kÄdu kopÄÅ¡anu. Un tagad septiÅi iet Å¡eit. Tagad es pÄriet uz seÅ¡iem. Tagad tas ir vÄl vairÄk darba. 

AstoÅi ir iet Å¡eit. Seven ir iet Å¡eit. Tagad seÅ¡i varÄtu iet Å¡eit. Tagad es greifers pieci. Tagad astoÅi ir jÄiet Å¡eit, septiÅi ir iet Å¡eit, seÅ¡i ir iet Å¡eit, un tagad pieci un atkÄrtot. Un es esmu diezgan daudz pÄrvietojot to pastÄvÄ«gi. 

TÄtad beigÄs, Å¡is algorithm-- mÄs ÅemÅ¡u sauc to ievietoÅ¡anas sort-- faktiski ir daudz darba, too. Tas ir tikai atÅ¡Ä·irÄ«gs veida darbu nekÄ Ben s. Bena darbs bija man iet uz priekÅ¡u un atpakaÄ¼ visu laiku, IzvÄloties nÄkamais mazÄkais elements atkal un atkal. TÄtad tas bija Å¡Ä« Ä¼oti vizuÄla veida darbu. 

Å Ä« otra algoritmu, kas ir joprojÄm correct-- tas iegÅ«s darbu done-- vienkÄrÅ¡i maina darba apjomu. IzskatÄs, sÄkotnÄji tu esi ietaupot, jo tu esi tikai nodarbojas ar katra elementa uzreiz bez kÄjÄm visu ceÄ¼u cauri sarakstam kÄ Ben bija. Bet problÄma ir, it Ä«paÅ¡i tÄs traki gadÄ«jumi, kad tas viss ir atpakaÄ¼, JÅ«s esat tikko veida atliekot smago darbu kamÄr jums ir noteikt savas kÄ¼Å«das. 

Un tÄpÄc, ja jÅ«s varat iedomÄties Å¡o astoÅi un septiÅi un seÅ¡i un pieci un vÄlÄk Äetras un trÄ«s un divi pÄrvietojas savu ceÄ¼u cauri sarakstam, mÄs esam tikai mainÄ«jusies darba veids mÄs darÄm. TÄ vietÄ, darot to pie sÄkumÄ mana atkÄrtojuma, Es esmu tikai darot to pie beigÄm katra atkÄrtojuma. TÄtad izrÄdÄs, ka Å¡o algoritmu, ArÄ« parasti sauc ievietoÅ¡anas kÄrtoÅ¡anas, ir arÄ« par kÄrtÄ«bu n brusas. Tas tieÅ¡Äm nav labÄka, nav labÄka vispÄr. 

TomÄr, tur ir treÅ¡Ä pieeja Es aicinu mÅ«s apsvÄrt, kas ir Å¡Ä«. TÄtad pieÅemsim, ka manu sarakstu, vienkÄrÅ¡Ä«bas labad atkal, ir Äetri, viens, trÄ«s, two-- tikai Äetri numuri. Ben bija laba intuÄ«cija, labs cilvÄks intuÄ«cija pirms, ar kuru mÄs fiksÄtu visa uzskaitÄ«t eventually-- ievietoÅ¡anas veida. Es coaxed mums lÄ«dzi. Bet pieÅemsim apsvÄrt VienkÄrÅ¡Äkais veids, kÄ noteikt Å¡o sarakstu. 

Å is saraksts nav sakÄrtots. KÄpÄc? AngÄ¼u, paskaidrojiet, kÄpÄc tas nav reÄli sakÄrtoti. Ko nozÄ«mÄ nav sakÄrtoti? 

STUDENT: Tas nav secÄ«gi. 

DAVID Malan: Nav secÄ«gi. Dodiet man piemÄru. 

STUDENT: Put tos kÄrtÄ«bÄ. 

DAVID Malan: OK. Dodiet man vairÄk konkrÄtu piemÄru. 

STUDENT: augoÅ¡Ä secÄ«bÄ. DAVID Malan: Nav augoÅ¡Ä secÄ«bÄ. PrecÄ«zÄk. Es nezinu, ko tu domÄ ar augoÅ¡Ä. Kas noticis? 

STUDENT: mazÄkais no skaitÄ¼i ir ne pirmajÄ telpÄ. 

DAVID Malan: VismazÄk s ne pirmajÄ telpÄ. BÅ«t konkrÄtÄks. Es esmu sÄk aizÄ·ert. MÄs paÄ¼aujamies, bet kÄda ir no rÄ«kojuma Å¡eit? 

STUDENT: ciparu secÄ«bu. DAVID Malan: ciparu secÄ«bu. Ikviena veida turÄÅ¡anai tas here-- Ä¼oti augstÄ lÄ«menÄ«. VienkÄrÅ¡i burtiski man pateikt, kas ir nepareizi, piemÄram, piecus gadus vecs varenÄ«bu. 

STUDENT: Plus viens. 

DAVID Malan: Kas tas ir? 

STUDENT: Plus viens. 

DAVID Malan: Ko tu ar to domÄ plus viens? Dodiet man cits piecus gadus vecs. Kas ir nepareizi, mamma? Kas ir nepareizi, tÄtis? Ko nozÄ«mÄ tas nav sakÄrtots? 

STUDENT: TÄ nav Ä«stÄ vieta. 

DAVID Malan: Kas nav Ä«stajÄ vietÄ? 

STUDENT: Four. DAVID Malan: Labi, labi. TÄtad Äetri nav kur tam vajadzÄtu bÅ«t. Jo Ä«paÅ¡i, tas ir labi? Äetri un viens, pirmais divi skaitÄ¼i I See. Vai tas ir labi? NÄ, viÅi no rÄ«kojuma, vai ne? PatiesÄ«bÄ, domÄju, ka tagad par datoru, too. To var apskatÄ«t varbÅ«t tikai vienÄ, varbÅ«t divas lietas once-- un patiesÄ«bÄ ir tikai viena lieta laikÄ, bet tas var vismaz apskatÄ«t viena lieta, tad NÄkamÄ lieta, blakus tai. 

TÄtad tie ir kÄrtÄ«bÄ? Protams ka nÄ. TÄtad, jÅ«s zinÄt, ko? KÄpÄc mÄs mazuli soÄ¼i noteikt Å¡o problÄmu nevis uz Å¡iem iedomÄtÄ algoritmi, piemÄram, Ben, kur viÅÅ¡ veida nosaka to, looping cauri sarakstam tÄ vietÄ, lai darÄ«t to, ko es darÄ«ju, kur Es tikko veida noteikti to, kÄ mÄs ejam? PieÅemsim tikai burtiski nojauktu jÄdziens order-- skaitliskÄ secÄ«bÄ, sauc to ko jÅ«s want-- Å¡ajÄs pairwise salÄ«dzinÄjumus. 

Äetri un viens. Vai Å¡is ir pareizais pasÅ«tÄ«jumu? TÄtad, pieÅemsim noteikt, ka. Viens un Äetri, un pÄc tam mÄs vienkÄrÅ¡i kopÄt to. Labi, labi. Es noteikti viens un Äetri. TrÄ«s un divi? NÄ. Ä»aujiet mani vÄrdi atbilstu manu pirkstiem. Äetri un trÄ«s? 

Tas nav kÄrtÄ«bÄ, tÄpÄc es esmu gatavojas darÄ«t vienu, trÄ«s, Äetri, divi. Labi. Tagad Äetri un divi? Mums ir nepiecieÅ¡ams, lai to labotu, too. TÄtad, viens, trÄ«s, divi, Äetri. TÄtad tas ir sakÄrtoti? NÄ, bet tas ir tuvÄk sakÄrtoti? 

Tas ir, jo mÄs fiksÄts Å¡is kÄ¼Å«da, mÄs fiksÄto Å¡o kÄ¼Å«du, un mÄs fiksÄto Å¡o kÄ¼Å«du. TÄpÄc mÄs fiksÄto trÄ«s kÄ¼Å«das apstrÄ«dami. JoprojÄm nav Ä«sti izskatÄs sakÄrtots, bet tas ir objektÄ«vi tuvÄk sakÄrtoti jo mÄs fiksÄto daÅ¾i no Å¡Ä«m kÄ¼Å«dÄm. 

Tagad to, ko man darÄ«t tÄlÄk? Es veida sasnieguÅ¡i sarakstÄ. Man Å¡Ä·iet, ir noteikta visas kÄ¼Å«das, bet ne. Jo Å¡ajÄ gadÄ«jumÄ, daÅ¾i skaitÄ¼i varÄtu bÅ«t burbuÄ¼ojot up tuvÄk uz citiem numuriem, joprojÄm ir bojÄtas. TÄtad, pieÅemsim to darÄ«t atkal, un es ÅemÅ¡u vienkÄrÅ¡i darÄ«t to vietÄ Å¡oreiz. Viena un trÄ«s? Ir labi. TrÄ«s un divi? Protams nÄ, tÄpÄc pieÅemsim mainÄ«t. TÄtad divi, trÄ«s. TrÄ«s un Äetru? Un tagad pieÅemsim tikai bÅ«t Ä«paÅ¡i pedantiska Å¡eit. Vai tas ir sakÄrtoti? JÅ«s cilvÄki zina, tas ir sakÄrtoti. 

Man vajadzÄtu mÄÄ£inÄt vÄlreiz. TÄtad Olivia ierosina es mÄÄ£inÄtu vÄlreiz. KÄpÄc? Jo dators nav luksusa mÅ«su cilvÄka acÄ«m no tikai glancing back-- Labi, es esmu darÄ«ts. KÄ dators noteikt ka saraksts tagad sakÄrtoti? MehÄniski. 

Man vajadzÄtu iet cauri vÄlreiz, un tikai tad, ja es nepadara / atrast nekÄdas kÄ¼Å«das es varu tad secinÄt kÄ datoru, yep, mÄs esam labi iet. Tik viens un divi, divi un trÄ«s, trÄ«s un Äetri. Tagad es varu pilnÄ«gi teikt, tas ir sakÄrtoti, jo es nekÄdas izmaiÅas. Tagad tas bÅ«tu kÄ¼Å«da, un tikai muÄ¼Ä·Ä«gi, ja es, dators, lÅ«dza Å¡os paÅ¡us jautÄjumus atkal gaida daÅ¾Ädas atbildes. NedrÄ«kst notikt. 

Un tÄpÄc tagad saraksts ir sakÄrtots. DiemÅ¾Äl, darba laiks Å¡is algoritms ir arÄ« n brusas. KÄpÄc? TÄpÄc, ka jums ir n skaitÄ¼i, un tad, sliktÄkajÄ gadÄ«jumÄ jums ir pÄrvietot n numuriem n reizes, jo jums ir, lai saglabÄtu turpinÄs atpakaÄ¼, lai pÄrbaudÄ«tu un potenciÄli noteikt Å¡ie skaitÄ¼i. Un mÄs varam darÄ«t vairÄk formÄla analÄ«ze, too. 

TÄtad tas ir viss, ko teikt, mÄs esam veikuÅ¡i trÄ«s daÅ¾Ädas pieejas, kas ir viens no viÅiem uzreiz intuitÄ«vi pie sikspÄrÅu no Ben uz manu ierosinÄjumu iekÄ¼aut KÄrtot uz Å¡o vienu kur jÅ«s veida aizmirst meÅ¾a par kokiem sÄkotnÄji. Bet tad, ja jÅ«s veikt soli atpakaÄ¼, voila, mÄs esam noteica Å¡Ä·iroÅ¡anas jÄdzienu. TÄtad tas ir, uzdroÅ¡inÄs teikt, zemÄks lÄ«menis varbÅ«t kÄ daÅ¾i no tiem citu algoritmi, bet pieÅemsim redzÄt, ja mÄs nevaram iztÄloties Å¡ie veidÄ Å¡o. 

TÄtad Å¡is ir daÅ¾i jauki programmatÅ«ra, ka kÄds rakstÄ«ja izmantojot krÄsains bÄri, kas ir gatavojas darÄ«t Å¡Ädi mums. Katrs no Å¡iem bÄriem apzÄ«mÄ skaitli. Taller stabiÅÅ¡, jo lielÄks skaits, mazÄks ir bÄrs, jo mazÄks skaits. Tik ideÄli mÄs gribam skaistu piramÄ«du kur tÄ sÄkas mazs un kÄ¼Å«st liels, un tas nozÄ«mÄtu, ka Å¡ie stieÅi ir sakÄrtoti. TÄpÄc es esmu gatavojas iet uz priekÅ¡u un izvÄlÄties, piemÄram, Bena algoritms first-- izvÄle kÄrtoÅ¡anas. 

Un paziÅojums, ko tas dara. Veids, kÄ tie esam izvÄlÄjuÅ¡ies iztÄloties Å¡o algoritmu ir tas, ka, tÄpat kÄ es biju ejot caur manu sarakstu, Å¡Ä« programma ir ieÅ¡ana izmantojot savu numuru sarakstÄ, uzsverot rozÄ katrÄ numurs, kas tas meklÄ. Un, kas ir aptuveni notikt tieÅ¡i tagad? 

MazÄkais skaits, kas I vai Ben atklÄju pÄkÅ¡Åi izpauÅ¾as pÄrvietots uz saraksta sÄkumÄ. Un paziÅojums viÅi darÄ«ja izlikt numuru, kas bija tur, un tas ir perfekti labi. Man nav iekÄ¼uvuÅ¡i Å¡ajÄ detalizÄcijas pakÄpi. Bet mums ir nepiecieÅ¡ams, lai ka numurs kaut kur, tÄpÄc mÄs vienkÄrÅ¡i pÄrcÄla to uz open vietas, kas tika izveidots. TÄpÄc es esmu gatavojas, lai paÄtrinÄtu Å¡o augÅ¡u, jo pretÄjÄ gadÄ«jumÄ tas kÄ¼Å«st Ä¼oti garlaicÄ«gs Ätri. AnimÄcija speed-- tur mÄs ejam. TÄpÄc tagad pats princips Man bija piemÄrojot, bet tu var sÄkt justies algoritmu, ja jÅ«s bÅ«s, vai redzÄt to mazliet skaidrÄk. Un Å¡is algoritms ir sekas IzvÄloties nÄkamo mazÄko elementu, tÄpÄc jÅ«s gatavojas sÄkt redzÄt to rampas lÄ«dz kreisajÄ pusÄ. Un katrÄ atkÄrtojumÄ, kÄ es ierosinÄja, tas nedaudz mazÄk darba. Tas nav iet visu ceÄ¼u atpakaÄ¼ uz kreiso saraksta beigÄm, jo tas jau zina, tie ir sakÄrtoti. TÄtad tas veids uzskata, tÄpat kÄ tas ir paÄtrinot, kaut arÄ« katrs solis ir Åemot tÄdu paÅ¡u laiku. Tur atlikuÅ¡ie tikai mazÄk soÄ¼us. Un tagad jÅ«s varat veida sajust algoritms tÄ«rÄ«Å¡anas galu uz augÅ¡u tÄ, un tieÅ¡Äm tagad tas ir sakÄrtoti. 

TÄtad ievietoÅ¡anas kÄrtoÅ¡anas ir viss darÄ«ts. Man nepiecieÅ¡ams atkÄrtoti randomize masÄ«vs. Un paziÅojums Es varu tikai paturÄt randomizing to, un mÄs saÅemsiet tuvinÄÅ¡anu TÄda pati pieeja, ievietoÅ¡anas kÄrtoÅ¡anas. Ä»aujiet man lÄni to Å¡eit. SÄksim, ka vairÄk nekÄ. ApstÄties. 

PieÅemsim izlaist Äetri. Tur mÄs ejam. Randomize tie masÄ«vs. Un Å¡eit mÄs go-- ievietoÅ¡anas veida. Play. IevÄrojiet, ka tas nodarbojas ar katru elements tai rodas uzreiz, bet, ja tas pieder nepareizÄ vietÄ paziÅojums visu darbu, kas ir noticis. Mums ir saglabÄt novirzot vairÄk un vairÄki elementi, lai padarÄ«tu telpu par kÄdu mÄs vÄlamies ieviest. 

TÄtad mÄs esam koncentrÄjoties uz atstÄja beigas tikai saraksta. PaziÅojums mÄs neesam pat izskatÄ«jÄs at-- mÄs nav iezÄ«mÄts rozÄ neko pa labi. MÄs esam tikai nodarbojas ar problÄmas, kÄ mums iet, bet mÄs esam radot daudz strÄdÄt par sevi vÄl. Un tÄpÄc, ja mÄs paÄtrinÄtu Å¡o augÅ¡u tagad iet lÄ«dz galam, tas ir atÅ¡Ä·irÄ«gs justies uz to patieÅ¡Äm. Tas ir tikai koncentrÄties uz kreisÄs beigÄm, bet darot nedaudz vairÄk darba kÄ needed-- veida nogludinÄÅ¡anas lietÄm vairÄk, nosakot lietas, bet nodarbojas galu galÄ ar katrs elements vienam kamÄr mÄs nokÄ¼Å«t the-- labi, mÄs visi zinÄm, cik tas beigsies, tÄpÄc tas ir mazliet underwhelming varbÅ«t. 

Bet saraksts end-- spoiler-- tiks sakÄrtoti. TÄtad aplÅ«kosim vienu pÄdÄjais. MÄs nevaram vienkÄrÅ¡i izlaist. MÄs esam gandrÄ«z tur. Divi iet, viens iet. Un voila. Excellent. 

TÄpÄc tagad pieÅemsim darÄ«t vienu pÄdÄjais, atkÄrtoti randomizing ar burbulis Å¡Ä·irot. Un paziÅojums Å¡eit, it Ä«paÅ¡i, ja es lÄni to uz leju, tas saglabÄ swooping cauri. Bet paziÅojums tas tikai padara pairwise comparisons-- veida vietÄjiem risinÄjumiem. Bet, tiklÄ«dz mÄs nokÄ¼Å«t beigÄm saraksta rozÄ, kas notiek, lai bÅ«tu neatkÄrtotos? JÄ, tas nÄksies sÄkt no jauna, jo tas tikai nefiksÄtu pairwise kÄ¼Å«das. Un kas varÄtu bÅ«t atklÄts vÄl citus. Un tÄdÄÄ¼, ja jums paÄtrinÄt Å¡o augÅ¡u, jÅ«s redzÄt, ka, tÄpat kÄ norÄda nosaukums, mazÄks elements-- vai drÄ«zÄk, lielÄkÄs elements-- sÄk burbulis augÅ¡u uz augÅ¡u, ja jÅ«s. Un mazÄki elementi ir sÄk burbulis uz leju pa kreisi. Un tieÅ¡Äm, tas ir sava veida vizuÄlo efektu, kÄ arÄ«. Un tÄ tas galu galÄ apdares Ä¼oti lÄ«dzÄ«gÄ veidÄ, too. 

Mums nav kavÄties par Å¡o konkrÄto vienu. Ä»aujiet man atvÄrt Å¡o tagad, too. Ir daÅ¾as citas Å¡Ä·iroÅ¡anas algoritmi visÄ pasaulÄ, no kuriem daÅ¾i tiek notverti Å¡eit. Un jo Ä«paÅ¡i izglÄ«tojamajiem, kuri nav obligÄti vizuÄlÄ vai matemÄtiskÄ, kÄ mÄs to darÄ«jÄm iepriekÅ¡, mÄs varam arÄ« izdarÄ«t audially ja mÄs saistÄ«t skaÅu ar Å¡o. Un tikai par jautru, Å¡eit ir daÅ¾i atÅ¡Ä·irÄ«gi algoritmi, un viens no tiem, jo ââÄ«paÅ¡i jÅ«s esat gatavojas paziÅojums sauc par "apvienot kÄrtoÅ¡anas." 

Tas ir tieÅ¡Äm fundamentÄli labÄks algoritms, tÄds, kas apvienojas veida, kas ir viens no tie, jÅ«s gatavojaties redzÄt, nav kÄrtÄ«bÄ n brusas. Tas ir par kÄrtÄ«bu n reizes Å¾urnÄlu n, kas ir pat nedaudz mazÄks, un tÄdÄjÄdi ÄtrÄk nekÄ Å¡ajÄs citÄs trim. Un tur ir pÄris citu dumjÅ¡ tie, kas mÄs redzÄsim. 

TÄtad, Å¡eit mÄs iet ar kÄdu skaÅu. Tas ir ievietoÅ¡anas kÄrtot, lai atkal tas ir tikai nodarbojas ar elementiem kÄ viÅi nÄk. Tas ir burbulis kÄrtot, tÄpÄc tas ir uzskatot tos pÄrus vienlaikus. Un atkal, lielÄkais elementi tiek burbuÄ¼oÅ¡ana uz augÅ¡u uz augÅ¡u. 

NÄkamÄ atlase kÄrtoÅ¡anas. Tas ir Bena algoritms, kur atkal viÅÅ¡ izvÄloties iteratÄ«vi nÄkamais mazÄkais elements. Un atkal, tagad jÅ«s tieÅ¡Äm var dzirdÄt, ka tas ir paÄtrinÄt, bet tikai tad, ja jo tas dara mazÄk un mazÄk strÄdÄt par katru atkÄrtojuma. Å is ir viens ÄtrÄk, apvienot kÄrtot, kas Å¡Ä·iroÅ¡anas kopas numuru kopÄ un tad apvienojot tos. TÄtad look-- kreiso puse jau ir sakÄrtoti. 

Tagad tas ir Å¡Ä·iroÅ¡ana pareizo pusi, un tagad tas notiek, lai tos apvienot vienÄ. Tas ir kaut kas ko sauc par "RÅ«Ä·Ä«tis kÄrtoÅ¡anas." Un jÅ«s varat veida redzÄt, ka tas notiek uz priekÅ¡u un atpakaÄ¼, Nosakot darbu mazliet Å¡eit un tur pirms tÄ ieÅÄmumus, lai jaunu darbu. Un tas arÄ« viss. Tur ir cita veida, kas ir tieÅ¡Äm tikai akadÄmiskiem mÄrÄ·iem, sauc par "stulba veida", kas notiek jÅ«su dati, sakÄrto to nejauÅ¡i, un pÄc tam pÄrbauda, ââvai tÄ ir sakÄrtots. Un, ja tas tÄ nav, tas atkal sakÄrto to nejauÅ¡i, pÄrbauda, ââvai tas ir sakÄrtoti, un, ja nav atkÄrto. Un teorÄtiski, probabilistically tas tiks pabeigta, bet pÄc diezgan daudz laika. Tas nav pats efektÄ«vu algoritmu. TÄtad kÄdi jautÄjumi par tiem Ä«paÅ¡i algoritmus vai neko tur saistÄ«ti, too? 

Nu, pieÅemsim tagad kaitinÄt intervÄlu, ko visi Å¡Ä«s lÄ«nijas ir, ka es esmu zÄ«mÄÅ¡anas un to, ko es esmu pieÅemot datoru var darÄ«t zem motora pÄrsega. Es gribÄtu apgalvot, ka visi no Å¡iem numuriem Es turpinu drawing-- viÅiem ir nepiecieÅ¡ams, lai saÅemtu glabÄti kaut kur atmiÅÄ. MÄs atbrÄ«voties no Å¡Ä«s puisis tagad, too. 

TÄtad gabals atmiÅas A computer-- tÄpÄc RAM DIMM ir ko mÄs meklÄja vakar, dual inline atmiÅas module-- izskatÄs Å¡Ädi. Un katrs no Å¡iem maz melnÄ mikroshÄmas ir daÅ¾i baitu skaitu, parasti. Un tad zelta tapas ir tÄpat kÄ vadi, kas savieno to ar datoru, un zaÄ¼Å¡ silÄ«cija padome ir tikai ko tur viss kopÄ. TÄtad, ko tas Ä«sti nozÄ«mÄ? Ja es veida izdarÄ«t Å¡o paÅ¡u attÄlu, pieÅemsim vienkÄrÅ¡Ä«bu ka Å¡is DIMM, dual inline atmiÅas modulis, ir viena gigabaita RAM, viena gigabaita atmiÅa, kas ir, cik daudz baitu kopÄjais? Viens gigabaitu ir, cik daudz baiti? VairÄk nekÄ tas. 1124 ir kilo, 1000. Mega ir miljoni. Giga ir miljards. 

Es guÄ¼us? Vai mÄs varam pat lasÄ«t etiÄ·eti? Tas ir tieÅ¡Äm 128 gigabaitiem, tÄpÄc tas ir vairÄk. Bet mÄs izlikties Å¡is ir tikai viena gigabaita. TÄtad tas nozÄ«mÄ, ka ir miljards baiti atmiÅas pieejami mani vai 8 miljardi biti, bet mÄs ejam runÄt ziÅÄ baitu tagad, kustÄties uz priekÅ¡u. 

TÄtad, ko tas nozÄ«mÄ, tas ir viens baits, tas ir vÄl viens baits, Tas ir vÄl viens baits, un, ja mÄs patieÅ¡Äm vÄlÄjÄs par Ä«paÅ¡u mums bÅ«tu izdarÄ«t miljardu maz kvadrÄtu. Bet ko tas nozÄ«mÄ? Nu, Ä¼aujiet man tikai tuvinÄtu kas par Å¡o attÄlu. Ja man kaut ko, kas izskatÄs piemÄram, tas tagad, tas ir Äetri baiti. 

Un tÄ es varÄtu likt Äetrus ciparus Å¡eit. Viens divi trÄ«s Äetri. Vai es varÄtu likt Äetri burti vai simboli. "Hei!" varÄtu iet labi tur, jo katrs no burtiem, mÄs runÄjÄm iepriekÅ¡, varÄtu pÄrstÄvÄt ar astoÅiem bitiem vai ASCII vai baitu. TÄtad citiem vÄrdiem sakot, jÅ«s varat likts 8 miljardi lietas iekÅ¡Ä Å Ä« viena stick atmiÅas. Tagad ko tas nozÄ«mÄ nodot lietas atpakaÄ¼ atpakaÄ¼ atpakaÄ¼ atmiÅÄ kÄ Å¡Ä«? Tas ir tas, ko programmÄtÄjs sauktu par "masÄ«vs." In datorprogrammu, jÅ«s nedomÄju par pamatÄ esoÅ¡o aparatÅ«ru, per se. Tu tikai domÄ par sevi kÄ ar piekÄ¼uve miljards baitu kopÄ, un jÅ«s varat kaut ko vÄlaties ar to. Bet ÄrtÄ«bas labad tas parasti noderÄ«gi lai saglabÄtu atmiÅas tiesÄ«bas blakus viens otram, piemÄram, Å¡is. TÄtad, ja es tuvinÄtu this-- jo mÄs noteikti nebrauksim izdarÄ«t miljardu maz squares-- pieÅemsim, ka Å¡Ä« padome ir ka stick atmiÅas tagad. Un es ÅemÅ¡u tikai izdarÄ«t tik daudz, cik mans marÄ·ieris nonÄks sniedzot mani Å¡eit. TÄpÄc tagad mums ir stick atmiÅas uz kuÄ£a kas ieguva vienu, divas, trÄ«s, Äetri, pieci, seÅ¡i, viens, divi, trÄ«s, Äetri, pieciem, seÅ¡iem, seven-- tik 42 baiti atmiÅas uz ekrÄna kopÄ. Paldies. JÄ, bija mans aritmÄtika labi. TÄtad 42 baiti atmiÅas Å¡eit. TÄtad, ko tas patiesÄ«bÄ nozÄ«mÄ? Nu, dators programmÄtÄjs tieÅ¡Äm parasti domÄ par Å¡o atmiÅÄ kÄ AdreÅ¡u. Citiem vÄrdiem sakot, katrs no Å¡iem vietas atmiÅÄ, aparatÅ«ras, ir unikÄla adrese. 

Tas nav tik sareÅ¾Ä£Ä«ti kÄ One BRATTLE Square, Cambridge, Mass., 02138. TÄ vietÄ, tas ir tikai skaitlis. Tas ir baitu skaitlis nulle, tas ir viens, tas ir divi, tas ir trÄ«s, un tas ir 41. Uzgaidi minÅ«ti. Es domÄju, ka es pirms brÄ«Å¾a teica 42. Es sÄku skaitÄ«Å¡anas nulles lÄ«menÄ«, tÄ ka ir faktiski pareiza. Tagad mums nav reÄli izdarÄ«t to kÄ reÅ¾Ä£i, un, ja jÅ«s izdarÄ«t to kÄ reÅ¾Ä£i Es domÄju, ka lietas tieÅ¡Äm iegÅ«t mazliet maldinoÅ¡s. KÄds programmÄtÄjs bÅ«tu, viÅa vai viÅas prÄtÄ, parasti domÄ par Å¡o atmiÅa kÄ ir tÄpat kÄ lentes, kÄ gabals maskÄÅ¡anas lentu ka tikai tÄlÄk un tÄlÄk uz visiem laikiem vai lÄ«dz brÄ«dim, kad jÅ«s darbinÄt no atmiÅas. TÄtad bieÅ¾Äk veids, kÄ pievÄrst un tikai domÄ par atmiÅu varÄtu bÅ«t, ka tas ir baits nulle, viens, divi, trÄ«s, un tad dot, dot, dot. Un jums ir 42 Å¡Ädas baiti KopumÄ pat gan fiziski tas varÄtu reÄli bÅ«t kaut kas vairÄk, kÄ Å¡is. 

TÄtad, ja jÅ«s tagad domÄjat par jÅ«su atmiÅa, jo tas, tÄpat kÄ lentes, tas ir tas, ko programmÄtÄjs atkal sauktu masÄ«vu atmiÅas. Un, ja jÅ«s vÄlaties, lai faktiski uzglabÄt kaut kas datora atmiÅÄ, jÅ«s parasti darÄ«t veikalu lietas back-to-back to back-to-back. TÄpÄc mÄs esam runÄjuÅ¡i par skaitÄ¼iem. Un, kad es gribÄju, lai atrisinÄtu problÄmas piemÄram, Äetri, viens, trÄ«s, divi, kaut gan man bija tikai zÄ«mÄÅ¡anas tikai skaitÄ¼i Äetri, viens, trÄ«s, divi uz klÄja, dators bÅ«tu tieÅ¡Äm ir Å¡o iestatÄ«jumu atmiÅÄ. 

Un kÄds bÅ«tu blakus divi datora atmiÅÄ? Nu, tur ir ar to nav atbildes. MÄs Ä«sti nezinÄm. Un tik ilgi, kamÄr dators nav nepiecieÅ¡ams to, tas nav vienalga, kas ir nÄkamais ar skaitÄ¼iem tas rÅ«p. Un, kad es teicu iepriekÅ¡, ka ar datoru var tikai aplÅ«kot vienÄ adresÄ vienlaicÄ«gi, Tas ir sava veida kÄpÄc. 

Nav atÅ¡Ä·irÄ«bÄ ieraksts atskaÅotÄjs un lasÄ«Å¡anas galvu tikai to var apskatÄ«t noteiktu groove tÄdÄ fiziskÄ vecÄs skolas ierakstu laikÄ, lÄ«dzÄ«gi var dators pateicÄ«ba tÄs CPU un tÄs Intel instrukciju komplekts, starp kuras instrukciju nolasa no atmiÅas vai saglabÄt memory-- dators var tikai apskatÄ«t vienÄ vietÄ pie LAIKU_ daÅ¾reiz kombinÄcija no tiem, bet tieÅ¡Äm tikai viena vieta laikÄ. TÄtad, kad mÄs darÄm Å¡ie daÅ¾Ädie algoritmi, Es esmu ne tikai rakstiskÄ formÄ vacuum-- Äetri, viens, trÄ«s, divi. Å ie skaitÄ¼i faktiski pieder kaut kur fiziskÄ atmiÅÄ. TÄtad ir niecÄ«ga maz tranzistori vai kÄda veida elektronikas zem pÄrsegs uzglabÄÅ¡anai Å¡Ä«s vÄrtÄ«bas. 

Un kopumÄ, cik bitus iesaistÄ«ts tieÅ¡i tagad, tikai, lai bÅ«tu skaidrs? TÄtad Å¡is ir Äetri baiti, vai tagad tas ir 32 bitu kopÄ. TÄtad faktiski ir 32 nullÄm un tie, kas veido Å¡Ä«s Äetras lietas. Tur pat vÄl vairÄk nekÄ Å¡eit, bet atkal mÄs vienalga par to. 

TÄpÄc tagad pieÅemsim lÅ«gt citu JautÄjums, izmantojot atmiÅu, jo ka beigÄs Dienas ir pretrunÄ. Nav svarÄ«gi, ko mÄs varÄtu darÄ«t ar dators, beigÄs, dienÄ aparatÅ«ras joprojÄm pats zem motora pÄrsega. KÄ es uzglabÄt vÄrdu Å¡eit? Nu, vÄrdu datorÄ, piemÄram, "Hey!" bÅ«tu jÄglabÄ tÄpat kÄ Å¡o. Un, ja jÅ«s vÄlÄtos ilgÄku vÄrds, jÅ«s varat vienkÄrÅ¡i pÄrrakstÄ«t kas un teikt kaut ko piemÄram, "hello" un veikals, kas Å¡eit. 

Un tÄ arÄ« Å¡eit, Å¡ajÄ contiguousness faktiski priekÅ¡rocÄ«ba, jo dators var vienkÄrÅ¡i lasa no labÄs uz kreiso. Bet Å¡eit ir jautÄjums. SaistÄ«bÄ ar Å¡o vÄrdu, h-e-l-l-o, izsaukuma zÄ«me, kÄ varÄtu dators zina, kur vÄrds sÄkas un kur vÄrds beidzas? SaistÄ«bÄ ar skaitÄ¼iem, kÄ tas dators zinÄt, cik ilgi secÄ«ba numuri ir vai ja tas sÄkas? Nu, izrÄdÄs out-- un mÄs neko pÄrÄk daudz Å¡ajÄ lÄ«menÄ« detail-- datori pÄrvietoties sÄ«kumi apkÄrt atmiÅÄ burtiski veidÄ Å¡Ä«m adresÄm. TÄtad datoru, ja jÅ«s esat rakstot kodu, lai uzglabÄtu lietas piemÄram, vÄrdiem, ko tu esi patieÅ¡Äm dara, ir rakstÄ«t izteicienus, ka atcerÄties, kur atrodas datora atmiÅa Å¡ie vÄrdi ir. TÄpÄc Ä¼aujiet man darÄ«t Ä¼oti, Ä¼oti vienkÄrÅ¡s piemÄrs. 

Es ieÅ¡u uz priekÅ¡u un atvÄrt vienkÄrÅ¡u teksta programmu, un es esmu gatavojas, lai radÄ«tu fails sauc hello.c. LielÄkÄ daÄ¼a no Å¡Ä«s informÄcijas mÄs neieÅ¡u Ä¼oti detalizÄti, bet es esmu gatavojas rakstÄ«t programma tajÄ paÅ¡Ä valodÄ, C. Tas ir daudz biedÄjoÅ¡a, Es teiktu, nekÄ nulles, bet tas ir Ä¼oti lÄ«dzÄ«gs garÄ. PatiesÄ«bÄ, Å¡ie cirtaini braces-- varat veida domÄ par to, ko es tikko darÄ«ju, jo tas. 

DarÄ«sim to, faktiski. Kad zaÄ¼ais karogs uzklikÅ¡Ä·inÄt, rÄ«koties Å¡Ädi. Es gribu izdrukÄt "sveiki". TÄpÄc tagad tas ir pseudocode. Es esmu veida nojauc lÄ«nijas. C, Å¡Ä« valoda es runÄju par, Å¡Ä« lÄ«nija print sveiki faktiski kÄ¼Å«st "printf" ar daÅ¾as iekavas un semikolu. 

Bet tas ir tieÅ¡i tÄ pati ideja. Un Å¡is draudzÄ«ga Ä¼oti "ZaÄ¼us karogs uzklikÅ¡Ä·inÄt" kÄ¼Å«st tik Ä¼oti vairÄk arcane "int galvenais spÄkÄ neesoÅ¡u." Un tas tieÅ¡Äm nav kartÄÅ¡anu, tÄpÄc es esmu tikai gatavojas ignorÄt to. Bet cirtaini bikÅ¡turi ir tÄpat kÄ izliektÄs puzzle gabalus, kÄ Å¡is. 

TÄtad jÅ«s varat veida uzminÄt. Pat ja jÅ«s nekad neesmu ieprogrammÄts agrÄk, KÄda Å¡Ä« programma iespÄjams darÄ«t? IespÄjams drukÄ sveiki ar izsaukuma zÄ«mi. 

TÄtad, pieÅemsim mÄÄ£inÄt to. Es esmu gatavojas, lai saglabÄtu to. Un tas ir, atkal, Ä¼oti vecÄs skolas vide. Es nevaru klikÅ¡Ä·i, es nevaru vilkt. Man ir rakstÄ«t komandas. TÄpÄc es gribu palaist savu programmu, lai Es varÄtu darÄ«t, piemÄram hello.c. Tas ir fails I ilga. Bet pagaidiet, es esmu trÅ«kst soli. Ko mÄs sakÄm, ir nepiecieÅ¡ams solis uz valodu, piemÄram, C? Esmu tikko uzrakstÄ«jis avotu kods, bet ko man vajag? JÄ, man ir nepiecieÅ¡ams kompilatoru. TÄtad par manu Mac Å¡eit, man ir programmu, ko sauc GCC, GNU C kompilatoru, kas Ä¼auj man darÄ«t this-- pagriezienu mans source kodu, mÄs to saucam, maÅ¡Ä«nu kodu. 

Un es redzu, ka, atkal, jo Å¡Ädi, tie ir nullÄm un tie, es tikko izveidots no mana pirmkodu, visi nullÄm un uzÅÄmumiem. Un, ja es gribu palaist mans program-- tas notiek saukt a.out par vÄsturiskÄ reasons-- "sveiki". Es varu palaist vÄlreiz. Sveiks, sveiks, sveiks. Un tas, Å¡Ä·iet, darbojas. 

Bet tas nozÄ«mÄ, ka kaut kur manÄ Datora atmiÅa ir vÄrdi h-e-l-l-o, izsaukuma zÄ«me. Un izrÄdÄs, tÄpat kÄ malÄ, ko dators bÅ«tu tipiski darÄ«t, ka tÄ zina, kur lietas sÄk un end-- tas ir gatavojas likt Ä«paÅ¡u simbolu Å¡eit. Un konvencija ir likt skaitlis nulle beigÄs vÄrda lai jÅ«s zinÄt, kur tas faktiski beidzas, lai jÅ«s neturiet izdrukÄÅ¡anu vairÄk un vairÄk zÄ«mes, nekÄ jÅ«s faktiski paredzÄjis. 

Bet takeaway Å¡eit, pat lai gan tas ir diezgan mistiskÄ, ir tas, ka tas galu galÄ samÄrÄ vienkÄrÅ¡s. Jums tika dota veida lentes, tukÅ¡u telpa, kurÄ jÅ«s varat rakstÄ«t vÄstules. Jums vienkÄrÅ¡i ir, lai bÅ«tu Ä«paÅ¡s simbols, piemÄram, patvaÄ¼Ä«gi skaits nulle, lai beigÄs jÅ«su vÄrdi lai dators zina, oh, man vajadzÄtu pÄrtraukt drukÄÅ¡anu pÄc Es redzu izsaukuma zÄ«mi. Jo nÄkamais lieta tur ir ASCII vÄrtÄ«ba ir nulle, vai null raksturs kÄ kÄds varÄtu to sauc. Bet tur ir sava veida problÄmu Å¡eit, un pieÅemsim atgriezties uz numuriem brÄ«di. PieÅemsim, ka man, patiesÄ«bÄ, ir masÄ«vs numuru, un pieÅemsim, ka Programma es esmu rakstiski ir kÄ grade grÄmata par skolotÄju un skolotÄji klasÄ. Un Å¡Ä« programma Ä¼auj viÅam vai viÅai rakstÄ«t savu skolÄnu rezultÄtus uz viktorÄ«nas. Un pieÅemsim, ka students saÅem 100 par savu pirmo viktorÄ«nu, varbÅ«t piemÄram, 80 uz nÄkamo, tad 75, tad 90 uz ceturto viktorÄ«nÄ. 

TÄtad Å¡ajÄ brÄ«dÄ« stÄsts, masÄ«vs ir izmÄru Äetri. Ir absolÅ«ti vairÄk atmiÅu dators, bet masÄ«vs, tÄ sakot, ir izmÄra Äetri. PieÅemsim tagad, ka skolotÄjs vÄlas pieÅ¡Ä·irt piekto viktorÄ«na uz klasi. Nu, viena no lietÄm, ko viÅÅ¡ vai viÅai nÄksies darÄ«t tagad uzglabÄt papildu vÄrtÄ«bu Å¡eit. Bet, ja masÄ«va skolotÄjs ir izveidots Å¡ajÄ programmÄ ir izmÄrs, viens no problÄmas ar masÄ«va, ka JÅ«s varat ne tikai saglabÄt pievienojot atmiÅÄ. Jo ko tad, ja otra daÄ¼a no Programma ir vÄrds "hey" labi tur? 

Citiem vÄrdiem sakot, mana atmiÅa var bÅ«t izmantot kaut kÄdÄ programmÄ. Un, ja iepriekÅ¡ es drukÄti, hey, Es gribu ievadi Äetriem viktorÄ«nu rÄdÄ«tÄjus, viÅi varÄtu iet Å¡eit un Å¡eit. Un, ja jÅ«s pÄkÅ¡Åi mainÄ«t savas domas vÄlÄk, un teikt, es gribu piekto viktorÄ«na rezultÄts, jÅ«s varat ne tikai ielieciet to, kur jÅ«s vÄlaties, jo ko tad, ja tas atmiÅa tiek izmantota kaut else-- kÄdu citu programmu vai kÄda cita iezÄ«me programmas ka jÅ«s strÄdÄjat? TÄtad jums ir jÄdomÄ iepriekÅ¡ kÄ jÅ«s vÄlaties, lai saglabÄtu savus datus, jo tagad jÅ«s esat krÄsotas sevi par digitÄlo stÅ«rÄ«. 

TÄtad skolotÄjs varÄtu vietÄ teikt, rakstot programmu uzglabÄt viÅa vai viÅas pakÄpes, jÅ«s zinÄt, ko? Es esmu gatavojas lÅ«gt, rakstot savu programmu, ka es gribu nulle, viens, divi, trÄ«s, Äetri, pieci, seÅ¡i, astoÅi pakÄpes kopÄ. TÄtad, viens, divi, trÄ«s, Äetri, pieci, seÅ¡i, septiÅi, astoÅi. SkolotÄjs var tikai nedaudz vairÄk, pieÅ¡Ä·irt atmiÅas, rakstot savu programmu un teikt, jÅ«s zinÄt, ko? Es nekad gatavojas pieÅ¡Ä·irt vairÄk kÄ astoÅus viktorÄ«nas Å¡ajÄ semestrÄ«. Tas ir vienkÄrÅ¡i traks. Es nekad pieÅ¡Ä·irt to. TÄ, ka Å¡ÄdÄ veidÄ viÅÅ¡ vai viÅa ir tÄda elastÄ«ba, lai uzglabÄtu studentu rÄdÄ«tÄjus, piemÄram, 75, 90, un varbÅ«t kÄdu papildu kur students ieguva papildu kredÄ«tu, 105. 

Bet, ja skolotÄjs nekad izmanto Å¡os trÄ«s telpas, tur ir intuitÄ«vs takeaway Å¡eit. ViÅÅ¡ vai viÅa ir tikai izÅ¡Ä·ÄrdÄt vietu. TÄtad citiem vÄrdiem sakot, tur ir Å¡is bieÅ¾i tradeoff programmÄÅ¡anÄ kur var vai nu pieÅ¡Ä·irt tieÅ¡i tÄ, kÄ daudz atmiÅas, kÄ jÅ«s vÄlaties, otrÄdi, kura ir tÄ, ka tu esi super efficient-- jÅ«s neesat to izÅ¡Ä·ÄrdÄ«gs at all-- bet negatÄ«vie kuru ir tas, kas, ja jÅ«s mainÄt jÅ«su prÄtÄ, kad izmantojot programmu, kuru vÄlaties saglabÄt vairÄk datu, nekÄ jÅ«s sÄkotnÄji paredzÄts. 

TÄtad, varbÅ«t risinÄjums ir, tad, rakstÄ«t savu programmu tÄdÄ veidÄ, ka viÅi izmanto vairÄk atmiÅas nekÄ viÅi tieÅ¡Äm ir nepiecieÅ¡ams. TÄdÄ veidÄ jÅ«s nebrauksim uzskriet Å¡o problÄmu, bet jÅ«s ir izÅ¡Ä·ÄrdÄ«gs. Un jo vairÄk atmiÅas jÅ«su programma izmanto, kÄ mÄs apspriedÄm vakar, jo mazÄk atmiÅu, kas ir pieejams uz citÄm programmÄm, jo ÄtrÄk jÅ«su dators varÄtu palÄninÄt uz leju, jo virtuÄlo atmiÅu. Un tÄ ideÄls risinÄjums varÄtu bÅ«t tas, ko? 

Nepietiekami izlietoÅ¡anai Å¡Ä·iet slikti. Over-pieÅ¡Ä·irot Å¡Ä·iet slikti. TÄtad, kÄdi varÄtu bÅ«t labÄks risinÄjums? PÄrdalÄ«t. Esiet dinamiskÄku. Nespiediet sevi izvÄlÄties priori, sÄkumÄ, ko jÅ«s vÄlaties. Un, protams, nav pÄrÄk pieÅ¡Ä·irt, lai jums bÅ«tu izÅ¡Ä·ÄrdÄ«gs. 

Un tÄ, lai sasniegtu Å¡o mÄrÄ·i, mÄs nepiecieÅ¡ams, lai mest Å¡o datu struktÅ«ru, tÄ sakot, prom. Un tÄ, ko programmÄtÄjs parasti izmanto ir kaut kas sauc nav masÄ«vs bet saistÄ«ts saraksts. Citiem vÄrdiem sakot, viÅÅ¡ vai viÅa bÅ«s sÄk domÄt par savu atmiÅu jo pagaidÄm veida formas, ka viÅi var izdarÄ«t Å¡ÄdÄ veidÄ. Ja es gribu, lai saglabÄtu vienu numuru program-- tÄpÄc tas ir septembrÄ« Es esmu devis mani skolÄni viktorÄ«na; Es gribu uzglabÄt studentu pirmo testu, un viÅi ieguva 100 par it-- I esmu gatavojas lÅ«gt manu datoru, veidÄ programmas es esmu rakstÄ«ts, vienam rieciens atmiÅas. Un es esmu gatavojas glabÄt numurs 100 tajÄ, un tas arÄ« viss. 

Tad daÅ¾as nedÄÄ¼as vÄlÄk kad es varu saÅemt savu otro testu, un ir pienÄcis laiks, lai rakstÄ«tu Å¡ajÄ 90%, es dodos lÅ«gt datoru, hey, dators, es varu bÅ«t vÄl rieciens atmiÅas? Tas notiek, lai dotu man Å¡o tukÅ¡s rieciens atmiÅas. Es esmu gatavojas Ä«stenot numuru 90, bet manÄ programmÄ kaut vai other-- un mums nebÅ«s jÄuztraucas par sintakse par this-- man vajag kaut kÄ Ä·Äde Å¡Ä«s lietas kopÄ. Un es Ä·Ädi kopÄ ar kas izskatÄs kÄ bulta Å¡eit. 

TreÅ¡Ä spÄle kas nÄk uz augÅ¡u, Es esmu gatavojas teikt, hey, dators, dod man vÄl vienu gabalu no atmiÅas. Un es esmu gatavojas, lai apspiestu kÄds tas bija, piemÄram, 75, un man ir Ä·Ädes Å¡im kopÄ tagad kaut kÄ. CeturtkÄrt viktorÄ«na nÄk kopÄ, un varbÅ«t kas ir pret semestra noslÄgumÄ. Un Å¡ajÄ brÄ«dÄ« mana programma varÄtu bÅ«t, izmantojot atmiÅu visas vietas, visÄ fiziski. Un tÄ tikai sÄkas, es esmu gatavojas izdarÄ«t Å¡o tÄlÄk quiz-- es aizmirst to, ko tÄ bija; es domÄju, ka varbÅ«t 80 vai something-- kÄ nekÄ Å¡eit. 

Bet tas ir labi, jo gleznieciski Es esmu gatavojas izdarÄ«t Å¡o lÄ«niju. Citiem vÄrdiem sakot, patiesÄ«bÄ, jÅ«su datora aparatÅ«ru, pirmais rezultÄts varÄtu galu galÄ Å¡eit, jo tas ir labi sÄkumÄ semestra. NÄkamais varÄtu nonÄkt Å¡eit jo mazliet laika ir pagÄjis un programma turpina darboties. NÄkamais rezultÄts, kas bija 75, varÄtu bÅ«t vairÄk nekÄ Å¡eit. Un pÄdÄjais rezultÄts varÄtu bÅ«t 80, kas ir vairÄk nekÄ Å¡eit. 

TÄtad patiesÄ«bÄ, fiziski, tas varÄtu bÅ«t kÄda datora atmiÅÄ izskatÄs. Bet tas nav noderÄ«gs garÄ«gÄs paradigmu datoru programmÄtÄjs. KÄpÄc jums vajadzÄtu aprÅ«pi, kur heck jÅ«su dati ir beidzot? JÅ«s vienkÄrÅ¡i vÄlaties, lai uzglabÄtu datus. 

Tas ir veida, piemÄram, mÅ«su diskusijas agrÄk zÄ«mÄÅ¡anas kubu. KÄpÄc tu vienalga, ko leÅÄ·is ir no kuba un kÄ jums ir pÄrvÄrst to izdarÄ«t to? JÅ«s vienkÄrÅ¡i vÄlaties kubu. TÄpat Å¡eit, jums vienkÄrÅ¡i vÄlaties pakÄpÄ grÄmatu. JÅ«s vienkÄrÅ¡i vÄlaties, lai padomÄtu par to kÄ numuru sarakstÄ. Who cares, kÄ tas ir Ä«stenoti aparatÅ«ru? 

TÄtad abstrakcija tagad ir Å¡o attÄlu Å¡eit. Tas ir saistÄ«ts sarakstu, kÄ programmÄtÄjs to sauktu, ciktÄl jums ir sarakstu, protams skaitÄ¼u. Bet tas ir saistÄ«ts gleznieciski Åemot vÄrÄ Å¡os bultas, un visas Å¡Ä«s bultas are-- zem kapuci, ja jÅ«s esat ieinteresÄti, atgÄdinÄt, ka mÅ«su fiziskÄ aparatÅ«ras ir adreses nulle, viens, divi, trÄ«s, Äetri. Visas Å¡Ä«s bultas ir ir kÄ karti vai norÄdes, kur, ja 90 is-- tagad Man skaitÄ«t. 

Nulle, viens, divi, trÄ«s, Äetriem, pieciem, seÅ¡iem, septiÅiem. IzskatÄs, ka 90 ir atmiÅas adrese numurs septiÅi. Visas Å¡Ä«s bultas ir ir kÄ maza lÅ«Å¾Åi papÄ«ra ka dodot rÄ«kojumus programma, kas saka sekot Å¡o karti nokÄ¼Å«t uz vietu septiÅi. Un tur jÅ«s atradÄ«siet studenta otrais viktorÄ«na rezultÄts. TikmÄr 75-- ja es turpinu to, tas ir septiÅi, astoÅi, deviÅi, 10, 11, 12, 13, 14, 15. 

Tas cita arrow tikai atspoguÄ¼o karti, lai atmiÅas vietÄ 15. Bet atkal, programmÄtÄjs parasti dara vienalga par Å¡o detalizÄcijas pakÄpi. Un vairumÄ katrÄ programmÄÅ¡anas valoda Å¡odien, programmÄtÄjs nav pat zinÄt, kur atmiÅÄ Å¡ie skaitÄ¼i patiesÄ«bÄ ir. Viss, ko viÅÅ¡ vai viÅa ir rÅ«pÄties par ir ka tie ir kaut kas saistÄ«ti kopÄ tÄdÄ datu struktÅ«ra, kÄ Å¡is. 

Bet izrÄdÄs, nav iegÅ«t pÄrÄk tehnisks. Bet tikai tÄpÄc, ka mÄs varam, iespÄjams, atÄ¼auties Å¡o diskusiju Å¡eit, pieÅemsim, ka mÄs vÄlreiz Å¡is jautÄjums Å¡eit no masÄ«va. Let 's redzÄt, ja mÄs noÅ¾Älojam iet Å¡eit. Tas ir 100, 90, 75, un 80. 

Ä»aujiet man Ä«si padara Å¡o apgalvojumu. Tas ir masÄ«vs, un atkal, spilgta raksturÄ«ga masÄ«va ir tas, ka visas jÅ«su datu atpakaÄ¼ atpakaÄ¼ atpakaÄ¼ in memory-- burtiski vienu baitu vai varbÅ«t Äetri baiti, daÅ¾i noteikts skaits baitu prom. In saistÄ«ta sarakstÄ, ko mÄs varÄtu izdarÄ«t kÄ Å¡is, zem motora pÄrsega, kas zina, kur tas sÄ«kumi ir? Tas nav pat nepiecieÅ¡ams, lai plÅ«st kÄ Å¡is. DaÅ¾i dati var bÅ«t atpakaÄ¼ pa kreisi tur. Jums nav pat zinÄt. 

Un tÄ ar masÄ«vu, jums ir iezÄ«me pazÄ«stams kÄ izlases piekÄ¼uvi. Un ko brÄ«vpiekÄ¼uves lÄ«dzekÄ¼i ir ka dators var lÄkt uzreiz uz jebkuru vietu masÄ«vÄ. KÄpÄc? Jo dators zina ka pirmÄ vieta ir nulle, viens, divi, un trÄ«s. 

Un tÄdÄÄ¼, ja jÅ«s vÄlaties, lai iet no Å¡is elements uz nÄkamo elementu, JÅ«s burtiski, jo datora prÄts, vienkÄrÅ¡i pievienot vienu. Ja jÅ«s vÄlaties doties uz treÅ¡o elementu, vienkÄrÅ¡i pievienojiet one-- nÄkamo elementu, tikko pievienot vienu. TomÄr, Å¡ajÄ versijÄ stÄsts, pieÅemsim dators paÅ¡laik meklÄ at vai nodarbojas ar numuru 100. KÄ jÅ«s nokÄ¼Å«t uz nÄkamo pakÄpÄ pakÄpei grÄmatÄ? 

Jums ir jÄÅem septiÅi pakÄpieni, kas ir patvaÄ¼Ä«ga. Lai nokÄ¼Å«tu uz nÄkamo, jums ir veikt vÄl astoÅi soÄ¼i, lai saÅemtu 15. Citiem vÄrdiem sakot, tas nav pastÄvÄ«ga plaisa starp skaitÄ¼iem, un tÄpÄc tas tikai Åem dators vairÄk laika ir punkts. Dators ir meklÄt caur atmiÅu, lai atrast to, ko jÅ«s meklÄjat. 

TÄtad, tÄ kÄ masÄ«vs mÄdz bÅ«t Ätru datu structure-- jo jums var burtiski vienkÄrÅ¡i darÄ«t vienkÄrÅ¡u aritmÄtisko un saÅemtu, kur jÅ«s vÄlaties, pievienojot vienu, par instance-- saistÄ«tu sarakstu, jÅ«s upurÄt Å¡o funkciju. JÅ«s varat ne tikai iet no pirmÄ uz otro treÅ¡o uz ceturto. Jums ir jÄievÄro karti. Jums ir veikt papildu pasÄkumus, nokÄ¼Å«t uz tÄm vÄrtÄ«bÄm, kas Å Ä·iet, ka pievienojot izmaksas. TÄtad mÄs esam maksÄjot cenu, bet to, kas bija lÄ«dzeklis, kas Dan tika meklÄ Å¡eit? KÄda saistÄ«tu sarakstu acÄ«mredzot Ä¼auj mums darÄ«t, kas bija izcelsmes Å¡is konkrÄtais stÄsts? 

TieÅ¡i tÄ. Dinamiska lielums uz to. MÄs varam pievienot Å¡im sarakstam. MÄs pat varam sarukt sarakstu, lai ka mÄs esam tikai izmantojot tik daudz atmiÅu kÄ mÄs tieÅ¡Äm gribam, un tÄ mÄs nekad pÄrÄk izlietoÅ¡anai. 

Tagad tikai, lai bÅ«tu patiesi gnÄ«da-picky, tur ir slÄptÄs izmaksas. TÄtad jums vajadzÄtu ne tikai let me pÄrliecinÄt Jums, ka tas ir pÄrliecinoÅ¡s tradeoff. Ir vÄl viens slÄptÄs izmaksas Å¡eit. Pabalsts, lai bÅ«tu skaidrs, ir tas, ka mÄs dinamismu. Ja es gribu vÄl vienu elementu, es varu tikai izdarÄ«t to un nodot numuru tur. Un tad es varu saistÄ«t ar attÄlu Å¡eit, tÄ kÄ vairÄk nekÄ Å¡eit, atkal, ja es esmu krÄsotas sevi kaktÄ, ja kaut kas cits jau izmanto atmiÅas Å¡eit, es esmu no luck. Esmu gleznojis sevi stÅ«rÄ«. 

Bet kas ir slÄptÄ izmaksÄt Å¡o attÄlu? Tas ir ne tikai daudzums laiks, kas nepiecieÅ¡ams, aiziet no Å¡ejienes uz Å¡eit, kas ir septiÅi soÄ¼i, tad astoÅi posmi, kas ir vairÄk nekÄ viens. Kas ir vÄl viens slÄptÄs izmaksas? Ne tikai laiks. Papildu informÄcija vajadzÄ«gi, lai sasniegtu Å¡o attÄlu. 

Yeah, ka karte, Å¡ie maz lÅ«Å¾Åi papÄ«rs, kÄ es glabÄt apraksta tos kÄ. Tie arrows-- tie nav bezmaksas. Computer-- jÅ«s zinÄt ko dators ir. TÄ ir nullÄm un uzÅÄmumiem. Ja jÅ«s vÄlaties, lai pÄrstÄvÄtu bultu vai saistÄ«to karti vai vairÄki, jums ir nepiecieÅ¡ams daÅ¾as atmiÅas. TÄtad otrÄ cenu, jÅ«s maksÄt par saistÄ«tÄ sarakstÄ kopÄ«ga datorzinÄtnes resurss, ir arÄ« telpa. 

Un tieÅ¡Äm tÄ, tik bieÅ¾i, starp kompromisus projektÄÅ¡anas programmatÅ«ras inÅ¾enierijas sistÄmas ir laiks un space-- ir divi no jÅ«su sastÄvdaÄ¼Äm, divi Sava visdÄrgÄkajÄm sastÄvdaÄ¼Äm. Tas maksÄ man vairÄk laika jo man ir sekot Å¡o karti, bet tas arÄ« maksÄ man vairÄk vietas jo man ir, lai saglabÄtu Å¡o karti apkÄrt. TÄtad cerÄ«ba, jo mÄs esam sava veida apsprieda vairÄk nekÄ vakar un Å¡odien, ir tas, ka ieguvumi atsvÄrs izmaksas. 

Bet tur nav acÄ«mredzams risinÄjums Å¡eit. VarbÅ«t tas ir better-- a la Ätri un netÄ«rs, kÄ Kareem ierosinÄts earlier-- mest atmiÅu problÄmu. VienkÄrÅ¡i nopirkt vairÄk atmiÅas, domÄju mazÄk grÅ«ti par atrisinÄtu problÄmu, un atrisinÄt to vieglÄk veidÄ. Un tieÅ¡Äm agrÄk, kad mÄs runÄjÄm par kompromisus, tas nebija telpu dators un laiks. Tas bija attÄ«stÄ«tÄjs laiks, kas ir vÄl viens resurss. 

TÄtad vÄlreiz, tas ir Å¡is balansÄÅ¡anas akts cenÅ¡oties izlemt, kuru no Å¡Ä«m lietÄm jÅ«s esat gatavi tÄrÄt? KurÅ¡ ir vislÄtÄkais? Kas dod labÄkus rezultÄtus? Yeah? 

PatieÅ¡Äm. TÄdÄ gadÄ«jumÄ, ja JÅ«s esat pÄrstÄvot numurus ar maps-- tos sauc daudzÄs valodÄs "norÄdes" vai "adreses" - tas ir divreiz telpu. Tas nav jÄbÅ«t tik slikti, kÄ dubultÄ, ja tagad mÄs esam tikai glabÄÅ¡anai numurus. PieÅemsim, ka mums bija glabÄÅ¡anai pacientu ierakstus hospital-- tÄpÄc Pierson s vÄrdus, tÄlruÅu numurus, sociÄlÄs apdroÅ¡inÄÅ¡anas numuri, Ärsts vÄsture. Å ajÄ ailÄ var bÅ«t daudz, daudz lielÄka, un tÄdÄ gadÄ«jumÄ niecÄ«ga maz rÄdÄ«tÄjs, adrese nÄkamais element-- tas nav liels darÄ«jumu. Tas ir tik bÄrkstis maksÄ tas nav svarÄ«gi. Bet Å¡ajÄ gadÄ«jumÄ, jÄ, tas ir divkÄrÅ¡ojies. Labs jautÄjums. 

ParunÄsim par reize mazliet konkrÄtÄk. Kas ir darba laiks meklÄjot Å¡o sarakstu? PieÅemsim, ka es gribÄju, lai meklÄtu cauri visiem studentu pakÄpes, un tur ir n atzÄ«mes Å ajÄ datu struktÅ«ra. ArÄ« Å¡eit mÄs varam aizÅemties vÄrdu krÄjums no agrÄk. Tas ir lineÄra datu struktÅ«ra. 

Big O n ir to, kas nepiecieÅ¡ams, lai saÅemtu lÄ«dz beigÄm Å¡o datu struktÅ«ra, whereas-- un mÄs neesam redzÄjuÅ¡i Tas before-- masÄ«vs dod jums ko sauc nemainÄ«gs laiks, kas nozÄ«mÄ, vienu soli vai divus soÄ¼us vai 10 steps-- nav nozÄ«mes. Tas ir fiksÄts skaitlis. Tam nav nekÄda sakara ar lielums masÄ«va. Un iemesls tam, atkal, ir brÄ«vpiekÄ¼uves. Dators var vienkÄrÅ¡i uzreiz pÄrietu uz citu vietu, jo viÅi visi vienÄdi attÄlums no viss pÄrÄjais. Nav domÄÅ¡ana iesaistÄ«ti. Viss kÄrtÄ«bÄ. TÄtad, ja es varÄtu, Ä¼aujiet man mÄÄ£inÄt gleznot pÄdÄjie divi attÄli. Ä»oti bieÅ¾i viens pazÄ«stams kÄ hash tabulu. TÄtad, lai motivÄtu Å¡o diskusiju, Ä¼aujiet man domÄt par to, kÄ to izdarÄ«t. 

TÄ kÄ par Å¡o? PieÅemsim, ka problÄma mÄs vÄlamies atrisinÄt tagad Ä«steno ar dictionary-- tÄpÄc viss Ä·ekars angÄ¼u vÄrdiem vai neatkarÄ«gi. Un mÄrÄ·is ir, lai varÄtu atbildÄt jautÄjumi veidlapas ir tas vÄrds? TÄtad jÅ«s vÄlaties, lai Ä«stenotu pareizrakstÄ«bas pÄrbaudÄ«tÄjs, tikko kÄ fiziska vÄrdnÄ«cu ka jÅ«s varat meklÄt lietas pat. PieÅemsim, ka es bÅ«tu to darÄ«t ar masÄ«vu. Es varÄtu darÄ«t. 

Un domÄju, ka vÄrdi ir Äbolu un banÄnu un cantaloupe. Un es nevaru iedomÄties augÄ¼iem kas sÄkas ar D, tÄpÄc mÄs esam tikai nÄksies trÄ«s augÄ¼us. TÄtad Å¡Ä« ir masÄ«vs, un mÄs esam uzglabÄtu visus Å¡os vÄrdus Å¡ajÄ vÄrdnÄ«cÄ kÄ masÄ«va. JautÄjums, tad ir, kÄ cits jÅ«s varÄtu uzglabÄt Å¡o informÄciju? 

Nu, es esmu veida krÄpÅ¡anos Å¡eit, jo katrs no Å¡iem burtiem vÄrdu ir patieÅ¡Äm individuÄls baitu. TÄtad, ja es patieÅ¡Äm gribÄju bÅ«t gnÄ«da-picky, es tieÅ¡Äm bÅ«t sadalot to augÅ¡up daudz mazÄkos gabalos atmiÅas, un mÄs varÄtu darÄ«t tieÅ¡i tÄ. Bet mÄs ejam uzskriet pati problÄma kÄ iepriekÅ¡. Ko darÄ«t, ja, kÄ Merriam Webster vai Oxford Vai katrs year-- viÅi pievienot vÄrdus uz dictionary-- mums nav vienmÄr vÄlas gleznot sevi kaktÄ ar masÄ«vu? 

TÄ vietÄ, varbÅ«t gudrÄki pieeja ir likt Äbolu savÄ mezglÄ vai kastÄ, kÄ mÄs teiktu, banÄnu, un tad Å¡eit mums ir kantalupe. Un mÄs string Å¡Ä«s lietas kopÄ. TÄtad tas ir masÄ«vs, un tas ir saistÄ«ts saraksts. Ja jÅ«s nevar gluÅ¾i redzÄt, tas tikai saka "masÄ«vs", un tas saka "sarakstu." 

TÄpÄc mums ir tÄds pats PrecÄ«zi jautÄjumi kÄ agrÄk, ar ko mums tagad ir dinamika mÅ«su saistÄ«ta sarakstÄ. Bet mums ir diezgan lÄns vÄrdnÄ«cu. PieÅemsim, ka es gribu, lai sameklÄtu vÄrdu. Tas var aizÅemt man Big O n soÄ¼i, jo vÄrds varÄtu bÅ«t visu ceÄ¼u beigÄs saraksts, piemÄram, melones. Un izrÄdÄs, ka plÄnoÅ¡anÄ, kÄrtot no SvÄtais GrÄls datu struktÅ«ras, ir kaut kas kas dod jums konstante laiks, piemÄram, masÄ«vs bet kas joprojÄm sniedz jums dinamismu. 

Lai mÄs varÄtu bÅ«t labÄkais no abÄm pasaulÄm? Un tieÅ¡Äm, tur ir kaut kas sauc hash tabulu kas Ä¼auj jums darÄ«t tieÅ¡i ka, lai gan apmÄram. Hash tabula ir mÄ«Ä¼otÄjs datu struktÅ«ra, kas mums var iedomÄties kÄ kombinÄcija no array-- un es esmu gatavojas izdarÄ«t to tÄpat this-- un saistÄ«ti saraksti ka es izdarÄ«t kÄ Å¡is vairÄk nekÄ Å¡eit. 

Un kÄ Å¡Ä« lieta darbi ir Å¡Äds. Ja Å¡is now-- hash table-- ir mans treÅ¡ais datu struktÅ«ra, un es gribu, lai saglabÄtu vÄrdi tas, man nav vÄlÄties, lai tikai saglabÄtu visu iepriekÅ¡ vÄrdus atpakaÄ¼ atpakaÄ¼ atpakaÄ¼ atpakaÄ¼. Es gribu, lai piesaistÄ«tu kÄdu informÄcijas vienÄ«bu par vÄrdiem, kas Ä¼aus me get to, ja tas ir ÄtrÄk. 

TÄtad, Åemot vÄrÄ vÄrdus Äbolu un banÄnu un cantaloupe, Es apzinÄti izvÄlÄjos Å¡os vÄrdus. KÄpÄc? Kas veida fundamentÄli atÅ¡Ä·irÄ«gs par trÄ«s? Kas ir skaidrs? ViÅi sÄk ar daÅ¾Ädiem burtiem. 

TÄtad, jÅ«s zinÄt, ko? Nevis likt visus Savus vÄrdus pats spainis, tÄ sakot, tÄpat vienÄ lielÄ sarakstÄ, kÄpÄc ne Es vismaz mÄÄ£inÄt optimizÄciju un lai manas saraksti 26/01 tik ilgi. PÄrliecinoÅ¡i optimizÄcija varÄtu bÅ«t, kÄpÄc nav I-- Ievietojot vÄrdu Å¡ajÄ datu struktÅ«ru, uz datora atmiÅÄ, kÄpÄc nav man visu "A" vÄrdus Å¡eit, visi "b" vÄrdi Å¡eit, un visi "c" vÄrdi Å¡eit? TÄtad tas beidzas lÄ«dz liekot Äbolu Å¡eit, banÄnu Å¡eit, kantalupe Å¡eit, un tÄ tÄlÄk. 

Un, ja man ir papildu VÄrds like-- kas ir vÄl viens? Apple, banÄnu, bumbieru. Ikviens domÄ par augÄ¼u kas sÄkas ar A, B, vai C? Blueberry-- perfekta. Kas notiek, lai galu galÄ Å¡eit. Un tÄ mÄs, Å¡Ä·iet, ir nedaudz labÄks risinÄjums, jo tagad, ja es gribu meklÄt Äbolu, es first-- man nav tikai nirt manÄ datu struktÅ«ras. Man nav nodoties sava datora atmiÅÄ. Es vispirms apskatÄ«t pirmo burtu. 

Un tas ir tas, ko dators zinÄtnieks teiktu. JÅ«s hash jÅ«su datu struktÅ«ras. JÅ«s veikt savu ieguldÄ«jumu, kas Å¡Ä« lieta ir vÄrds, piemÄram, Äbolu. AnalizÄt to, aplÅ«kojot pirmais burts Å¡ajÄ gadÄ«jumÄ, tÄdÄjÄdi sajaukÅ¡anai to. SajaukÅ¡anai ir vispÄrÄjs termins, ar kuru JÅ«s lietojat kaut kÄ priekÅ¡nodokli un jÅ«s raÅ¾ot kÄdu produkciju. Un izejas, jo lieta ir vieta jÅ«s vÄlaties meklÄt, pirmais vietu, otrais vietu, treÅ¡ais. TÄtad ieguldÄ«jums ir Äbolu, produkcija ir pirmais. IeguldÄ«jums ir banÄnu, tad produkcija bÅ«tu otrais. IeguldÄ«jums ir cantaloupe, produkcija bÅ«tu treÅ¡ais. IeguldÄ«jums ir melleÅu, tad produkcija bÅ«tu atkal bÅ«s otrais. Un tas ir tas, kas palÄ«dz jums veikt Ä«sceÄ¼us caur savu atmiÅu Lai saÅemtu vÄrdiem vai datu efektÄ«vÄk. 

Tagad tas saÄ«sina savu laiku potenciÄli ar tik daudz kÄ viens no 26, jo, ja jÅ«s pieÅemt, ka jums ir tik daudz "A" vÄrdus kÄ "z" vÄrdi kÄ "Q" vÄrdus, kas nav Ä«sti realistic-- Jums nÄksies Å¡Ä·Ä«bs pÄri daÅ¾i burti alphabet-- bet tas bÅ«tu papildu pieeja tas Ä¼auj jums nokÄ¼Å«t vÄrdiem daudz ÄtrÄk. Un patiesÄ«bÄ, sareÅ¾Ä£Ä«tu programmu, Googles no pasaules, Facebooks no world-- viÅi varÄtu izmantot hash tabulu par daudz daÅ¾Ädiem mÄrÄ·iem. Bet tie nebÅ«tu tik naivi, tikai apskatÄ«t pirmo burtu Äbolu vai banÄnu vai bumbieru vai cantaloupe, jo, kÄ jÅ«s varat redzÄt Å¡os sarakstus joprojÄm varÄtu saÅemt ilgi. 

Un tÄ tas tomÄr varÄtu bÅ«t sava veida no linear-- tik veida lÄns, kÄ ar lielo O n ka mÄs apspriests agrÄk. TÄtad, ko reÄlu labs hash tabulu bÅ«s do-- tas bÅ«s daudz lielÄks masÄ«vs. Un tÄ izmantos daudz vairÄk sareÅ¾Ä£Ä«ta sajaukÅ¡anai funkcija, tÄpÄc, ka tas nav tikai apskatÄ«t "a." VarbÅ«t tas aplÅ«ko "a-p-p-l-e" un kaut kÄ pÄrvÄrÅ¡ Å¡Ä«s piecas vÄstules uz vietu, kur Äbolu jÄuzglabÄ. MÄs vienkÄrÅ¡i naivi, izmantojot burtu "a" viens pats, jo tas ir jauki un vienkÄrÅ¡i. 

Bet hash tabulu, kas beigÄm, jÅ«s varat domÄt no kÄ kombinÄcija masÄ«vs, katrs no kuriem ir saistÄ«ts saraksts, kas ideÄli jÄbÅ«t pÄc iespÄjas Ä«sÄkam. Un tas nav acÄ«mredzams risinÄjums. PatiesÄ«bÄ, daudz smalkas tuning kas iet uz zem motora pÄrsega, kad Äªstenojot Å¡os veidus sareÅ¾Ä£Ä«tas datu struktÅ«ras ir tas, kas ir pareizÄ garums masÄ«va? KÄda ir pareizÄ hash funkcija? KÄ jÅ«s uzglabÄt lietas atmiÅÄ? 

Bet saproti, cik Ätri Å¡Äda veida diskusijas saasinÄjÄs, nu tik tÄlu, ka tas ir sava veida no virs galvas Å¡ajÄ brÄ«dÄ«, kas ir labi. Bet mÄs sÄkÄm, atgÄdinÄt, ar patiesi kaut zema lÄ«meÅa un elektroniski. Un tÄ tas atkal ir Å¡is tÄma abstrakcijas, kur reiz sÄkat lietot, lai pieÅ¡Ä·irts, OK, es esam ieguvuÅ¡i it-- tur fiziskÄ atmiÅa, Labi, sapratu, ik fiziskÄ atraÅ¡anÄs vieta ir piegÄdes adrese, Labi, es saÅÄmu to, es varu pÄrstÄvÄt Å¡ie adreses kÄ arrows-- JÅ«s varat Ä¼oti Ätri sÄkt bÅ«t sareÅ¾Ä£Ä«tÄkus sarunas, kas beigÄs, Å¡Ä·iet, ir Ä¼aut mums lai risinÄtu problÄmas, piemÄram, meklÄjot un Å¡Ä·iroÅ¡anas efektÄ«vÄk. Un esiet droÅ¡i, too-- jo es domÄju, ka tas ir dziÄ¼Äkais mÄs esam aizgÄjuÅ¡i par daÅ¾Äm Å o CS tÄmÄm proper--, esam darÄ«ts dienÄ un pusi pie Å¡Ä« norÄdÄ«t, ko jÅ«s varÄtu parasti darÄ«t pÄri kurss astoÅas nedÄÄ¼as semestrÄ«. 

Visus jautÄjumus par Å¡o? NÄ? Viss kÄrtÄ«bÄ. Nu, kÄpÄc nav mÄs pauze tur, sÄkt pusdienas daÅ¾as minÅ«tes sÄkumÄ, atsÄkt tikai par stundu? Un es kavÄties mazliet ar jautÄjumiem. Tad es esmu nÄksies iet veikt pÄris zvanus, ja tas ir OK. Es ieslÄgt kÄdu mÅ«ziku pa to laiku, bet pusdienas bÅ«tu ap stÅ«ri.