DAVID Malan: Bone. Ni estas reen. Do en ĉi tiu segmento de programado kio Mi pensis ke ni faras estas miksaĵo de aĵoj. Unu, do iomete de io manojn-sur, kvankam uzante pli ludema programado environment-- Kiu estas demonstrativo de precize la specoj de ideoj ni parolis pri, sed iom pli formale. Du, rigardu kelkajn el la pli teknika manieroj ke programisto devus reale solvi problemoj kiel la serĉado problemo ke ni rigardis antaŭe kaj ankaŭ pli funde Interesa problemo de ordigado. 

Ni nur supozis de la akiri iri ke tiu telefono libro ordigataj sed tio sole estas fakte speco de peza problemo kun multaj malsamaj manieroj solvi ĝin. Do ni uzos tiujn kiel klaso de problemoj reprezentanto de aĵoj kiuj povus esti solvita en ĝenerala. Kaj poste ni parolos pri detale kion nomas datumoj structures-- amatoro manieroj kiel ligitaj listoj kaj hash tabloj kaj arboj programisto estus reale uzi kaj ĝenerale uzi sur skribtabulo pentri bildon de kion li aŭ ŝi antaŭvidas por efektivigado iu peco de programaro. 

Do ni faru la manojn-sur parto unua. Tiel simple akiri viajn manojn malpuraj kun medio nomita scratch.mit.edu. Tio estas ilo kiu ni uzas en nia studenta klaso. Kvankam ĝi estas desegnita por aĝoj 12 kaj supren, Ni uzu ĝin por la supren parto de tiu sufiĉe ĉar ĝi estas bela, amuza grafika maniero de lernado iom ion pri programado. Tiel gvidi al tiu retadreso, kie vi devus vidi tiun tute tiel, kaj iri antaŭen kaj klaku Aliĝi Scratch ĉe supra dekstra kaj elekti uzantnomon kaj Pasvorto kaj finfine akiri mem an account-- scratch.mit.edu. Mi pensis ke mi uzas tion kiel ŝanco unue montri tion. Demando venis dum la paŭzo pri kio kodo reale aspektas. Kaj ni parolis dum la paŭzo pri C, en particular-- precipe malalta nivelo en pli malnova lingvo. Kaj mi ĵus faris rapidan Google serĉo trovi C kodo por duuma serĉo, la algoritmo ke ni uzata por serĉi tiu telefono libro antaŭe. Tiu aparta ekzemplo, kompreneble, ne serĉu telefono libro. Ĝi nur serĉas tuta fasko de nombroj en la komputilo la memoro. Sed se vi ŝatus nur akiri vidan senco de kio fakta programado lingvo similas, ĝi aspektas iom io tiamaniere. Do ĝi estas ĉirkaŭ 20-plus, 30 aŭ tiel linioj de kodo, sed la konversacio ni estis havanta pli paŭzo estis pri kiel tio fakte iĝas transformis en nuloj kaj kaj se vi ne povas simple restarigu ke procesi kaj pasi de nuloj kaj malantaŭeniri al kodo. 

Bedaŭrinde, la procezo Estas tiom transforma ke estas multe pli facile dirite ol farite. Mi iris antaŭen kaj reale turnis ke programo, Duuma Search, en nuloj kaj pere de programo nomita La compilador mi hazarde havas tie rajton sur mia Mac. Kaj se vi rigardas la ekranon tie, enfokusigante specife sur tiuj meza ses kolumnoj nur, vi vidos nur nuloj kaj aĵoj. Kaj tiuj estas la nuloj kaj ke formi ĝuste tiu serĉado programo. 

Kaj tiel ĉiu eron de kvin bitojn, ĉiu bajto de nuloj kaj tie, reprezenti iun instrukcion tipe ene de komputilo. Kaj fakte, se vi aŭdis la marketing slogano "Intel ene" - kiuj, kompreneble, nur signifas vin havas Intel CPU aŭ cerbo ene la komputilo. Kaj kion tio signifas esti CPU estas ke vi havas aron de instrukcioj, por tiel diri. 

Ĉiu CPU en la mondo, multaj el ili faris por Intel tiuj tagoj, komprenas finia numeron de instrukcioj. Kaj tiuj instrukcioj estas tiel malalta nivelo kiel aldoni tiujn du nombroj kune, multipliki tiuj du nombroj kune, movi tiun pecon de datumoj de ĉi tie por tie en memoro, krom tiu informojn de tie al tie en memoro, kaj tiel forth-- tiel tre, tre malalta nivelo, preskaŭ elektronikajn detalojn. Sed kun tiuj, matematika operacioj kuplita kun kion ni diskutis pli frua, la reprezento de datumoj kiel nuloj kaj, povas vi konstruas ĉion ke komputilo povas fari hodiaŭ, ĉu ĝi estas teksta, grafika, muzika, aŭ alie. 

Do tiu estas tre facila akiri perdita en la maleza de rapide. Kaj ekzistas multe de sintaksaj defioj per kiu se vi faras la plej simpla, stultan de tajperarojn nulo programo laboros ajn. Kaj tiel anstataŭ uzanta lingvo kiel C ĉimatene, Mi pensis ke estus pli amuze vere fari ion pli vida, kiu dum desegnita por infanoj estas efektive perfekta manifestado de fakta programado language-- nur okazas al uzi bildojn anstataŭ teksto reprezenti tiujn ideojn. 

Do iam vi ja havas konton en scratch.mit.edu, klaku Krei butono ĉe supro lasita de la paĝaro. Kaj vi devus vidi medion kiel unu mi volis vidi sur mia ekrano tie. Kaj ni elspezas nur iom iom da tempo ludanta tie. Ni vidu se ni ne povas ĉiuj solvi iun problemoj kune en la sekvanta maniero. 

Do kion vi vidos ene de tiu environment-- kaj reale simple lasu mi paŭzi. Estas iu ne tie? Ne ĉi tie? BONE. Do mi atentigas kelkaj karakterizaĵoj de ĉi tiu medio. 

Tiel supre maldekstre de la ekrano, ni havas Scratch la scenejo, tiel diri. Nulo estas ne nur la nomo de tiu programlingvo; ĝi estas ankaŭ la nomo de la kato kiu vi vidos defaŭlte ekzistas en oranĝo. Li estas sur la scenejo, tiel multe kiel mi priskribis la testudo frue kiel estante en rektangula blanka tabulo medio. Tiu kato mondo estas limigita tute por ke rektangulo ĝis pinto. 

Dume, sur la dekstra flanko tie, estas nur skriptoj areo, malplenan skribtabulo se vi volas. Tie estas kie ni tuj skribos niaj programoj en nur momento. Kaj la konstruelementoj ke ni faros uzas por skribi ĉi program-- la enigmo pecoj, se vi will-- estas tiuj ĉi tie en la mezo, kaj ili estas kategoriigitaj de funcionalidad. Do, ekzemple, mi tuj iros antaŭen kaj pruvi almenaŭ unu el tiuj. Mi tuj iros antaŭen kaj klaku la Kontrolo kategorio supren supro. 

Do jen estas la kategoriojn ĝis supro. Mi tuj klaki la Kontrolo kategorio. Prefere, mi tuj klaku Eventoj kategorio, la unua unu ĝis supro. Kaj se vi ŝatus sekvi kune eĉ kiel ni faras tion, vi tute bonvena. Mi tuj alklaki kaj treni tiun unua, "kiam verda flago clicked." Kaj tiam mi tuj faligis ĝin ĝuste malglate ĉe la supro de mia malplenan ardezoj. 

Kaj kio estas agrable pri Scratch estas ke tiu enigmo pecon, kiam interkroĉitaj kun aliaj enigmo pecoj, tuj faros laŭvorte kio tiuj puzlo pecoj diru fari. Do, ekzemple, Scratch pravas Nun en la mezo de sia mondo. Mi tuj iros antaŭen kaj elekti Nun, ni diru, la Motion kategorio, Se vi ŝatus fari la same-- Moviĝo kategorio. Kaj nun rimarkas mi havas tutajn faskon da puzlo pecoj tie ke, denove, ia fari kion ili diras. Kaj mi tuj iros antaŭen kaj treni kaj faligi la movadon bloko rajton super tie. 

Kaj rimarki ke tuj kiam vi akiras proksime al la fundo de la "verda flago klakis "butonon, avizo kiel blanka linio aperas, kvazaŭ ĝi estas preskaŭ magneta, ĝi volas iri tien. Nur lasu iri, kaj ĝi alkroĉiĝos kune kaj la formoj kongruas. Kaj nun vi povas eble preskaŭ diveni kie ni iras kun tio. 

Se vi rigardas la Scratch stadio tien kaj rigardu al la supro, vi vidos ruĝan lumon, la haltigi signo, kaj verda flago. Kaj mi tuj iros antaŭen kaj rigardi mian screen-- por nur momento, se vi povus. Mi tuj klaku verda flago nun, kaj Li incitis kion ŝajnu esti 10 paŝoj aŭ 10 rastrumeroj, 10 punktoj, sur la ekrano. 

Kaj tial ne ke ekscita, sed mi proponas sen eĉ instrui tion, nur uzante la propran vian propran intuition-- let mi proponas ke vi elkompreni kiel fari Scratch promeno tuj la scenejo. Jam lin faras vojon por la dekstra flanko de la ekrano, la tutan vojon al la dekstra. Mi donos al vi momenton aŭ tiel lukti kun tiu. Vi eble volas preni rigardon ĉe aliaj kategorioj de blokoj. Bone. Do nur por recap, kiam ni havas la verda flago klakis tie kaj movas 10 paŝoj estas la nur instrukcion, ĉiufoje mi klaku la verdan flagon, kio okazas? Nu, jen kurante mia programo. Do mi povus fari tion eble 10 fojojn permane, sed ĉi sentas iom iom hackish, por tiel diri, per kiu mi ne vere solvi la problemon. Mi nur provas denove kaj denove kaj denove kaj denove ĝis mi ian hazarde atingi la directiva ke mi ekiris por atingi pli frue. 

Sed ni scias el niaj _pseudocode_ frue ke ekzistas tiu nocio en programado de looping, fari ion denove kaj denove. Kaj ankaux mi vidis, ke aro da vi atingita por kio enigmo peco? Ripetu ĝis. Do ni povus fari ion kiel ripeti ĝis. Kaj kion vi ripeti ĝis ĝuste? 

BONE. Kaj mi iros kun kiu estas iom pli simpla por nur momento. Lasu min antaŭeniri kaj fari tion. Rimarku, ke kiel vi povas havi malkovritaj sub kontrolo, ekzistas tiu ripeto bloko, kiu ne aspektas kiel ĝi estas tiel granda. Tie ne estas multe ĉambron inter tiuj du flavaj linioj. Sed kiel kelkaj el vi eble havas rimarkis, se vi treni kaj guton, rimarki kiel ĝi kreskas por plenigi la formo. 

Kaj vi povas eĉ Cram pli. Ĝi gardos kreskas se vi treni kaj ŝvebi super ĝi. Kaj mi ne scias kio estas bona ĉi tie, do ni mi almenaŭ ripeti kvinfoje, por Ekzemple, kaj poste reiri al la stadio kaj klaku la verdan flagon. Kaj nun rimarkas ĝi ne estas tre tie. 

Kelkaj el vi proponis, kiel Victoria simple, ripeti 10 fojoj. Kaj ke ĝenerale faras akiri lin la tutan vojon, sed ĉu ne estos pli fortika maniero ol arbitre elŝeligi kiom da movojn fari? Kio povus esti pli bona bloko ol ripeto 10 fojojn esti? 

Jes, do kial ne fari ion por ĉiam? Kaj nun lasu min movi tiun enigmo peco interne tien kaj forigi ĉi tiun. Nun rimarkas negrave kie Scratch komenciĝas, li iras al la rando. Kaj dankeme MIT, kiu faras Scratch, ĵus certigas ke li neniam malaperas tute. Vi povas ĉiam kapti sian voston. 

Kaj ĝuste intuicie, kial li tenas movanta? Kio okazas ĉi tie? Li ŝajnas esti detenita, sed tiam se mi reprenos kaj trenu Li tenas volante iri tien. Kial estas tio? Vere, komputilo estas laŭvorte faros kion vi diros ĝin fari. Do se vi diris ĝin antaŭe fari la sekva ĉiam, movi 10 paŝoj, ĝi tuj plu iri kaj iri ĝis mi batis la ruĝa halto signo kaj ĉesigi la programon tute. 

Do eĉ se vi ne fari tion, kiel mi povus tion fari Scratch movon rapida trans la ekrano? Pli paŝojn, dekstra? Do anstataŭ fari 10 samtempe kial ne ni antaŭeniri kaj ŝanĝi ĝin to-- Kion vi propose-- 50? Do nun mi tuj klaku la verdan flago, kaj efektive, li iras vere rapida. 

Kaj tio, kompreneble, estas nur demonstracio de kuraĝigo. Kio estas kuraĝigo? Ĝi simple montranta vin la homa a tuta aro da ankoraŭ bildoj vere, vere, vere rapida. Kaj do se ni nur rakontanta lin moviĝi pli paŝojn, ni nur havi la efikon estu ŝanĝo kie li estas sur la ekrano des pli rapide por unuo de tempo. 

La sekva defio kiun mi proponis estis havi lin rebotar ekstere la rando. Kaj sen scii kion enigmo pecoj exist-- ĉar ĝi estas bone Se vi ne alvenas al la scenejo de la challenge-- kio ĉu vi volas fari intuicie? Kiel ni havi lin rebotar dorso kaj antaŭen, inter la maldekstra kaj dekstra? 

Yeah. Do ni bezonas ian de kondiĉo, kaj ni ŝajnas havi Conditionals, tiel paroli, sub la kontrolo kategorio. Kiu el tiuj blokoj ni probable volas? Yeah, eble "se, tiam." Do rimarki, ke inter la flavaj blokoj ni havas ĉi tie, estas tiu "se" aŭ tiu "se, alie" bloko kiu volas nin permesas fari decidon fari tiun aŭ fari tion. Kaj vi povas eĉ nesto ilin fari plurajn aferojn. Aŭ se vi ne iris tien ankoraŭ, antaŭeniri al la sensado kategorio kaj- ni vidu se ĝi estas tie. 

Do kio bloko povas esti utila tie detekti se li estas de la scenejo? Yeah, rimarki ke iuj de ĉi tiuj blokoj povas parametrigita, por tiel diri. Ili povas esti ia personecigita, ne kontraste HTML hieraŭ kun atributoj, kie tiuj atributoj ia agordi la konduton de etikedo. Simile tie, mi povas ekpreni ĉi kortuŝa bloko kaj ŝanĝo kaj demandi la demandon, vi tuŝi la muso puntero kiel la kursoro aŭ vi tuŝi la randon? 

Do lasu min iri en kaj fari tion. Mi tuj malzomi dum momento. Lasu min ekpreni tiun enigmo peco tie, ĉi enigmo peco ĉi, kaj mi tuj senorda miksaĵo ilin por nur momento. Mi tuj kopii ĉi, ŝanĝi ĉi tion al kortuŝa rando, kaj mi tuj moviĝo fari tion. Do jen kelkaj ingrediencoj. Mi pensas mi havas ĉion kion mi deziras. 

Ĉu iu volas proponi kiel mi povas konekti tiuj eble pinti al fundo Por solvi la problemon de devi Nulo movo dekstre maldekstren al rajton maldekstre dekstren maldekstren, ĉiu tempo simple rebotar ekstere la muro? Kion mi volas fari? Kiu bloko devus ligoj al la "Kiam verda flago clicked unua"? 

Bone, do ni komencu kun la "ĉiam." Kio iras ene poste? Iu alia. OK, movi paŝojn. Bone. Tiam kio? Tial la se. Kaj rimarki, kvankam ĝi aspektas krampitaj kune firme, ĝi nur kreskos plenigi. Ĝi simple salti en kie mi volas. 

Kaj kion mi metu inter la se kaj do? Probable "se tuŝi randon." Kaj avizo, denove, ĝi estas tro granda por ĝi, sed ĝi kreskos plenigi. Kaj tiam turni 15 gradoj? Kiom da gradoj? Jes, do 180 estos ŝpini Min tuta vojo ĉirkaŭ. Do ni vidu se mi akiris tiun rajton. Lasu min malzomi. 

Lasu min treni Scratch supren. Do li estas iom distordita nun, sed tio estas bone. Kiel mi retrovu lin facile? Mi tuj cheat iomete. Do mi aldonas alian bloko, nur por esti klara. Mi volas lin atentigi 90 gradoj dekstren defaŭlte, do mi simple tuj diros lin fari tion programmatically. Kaj tie ni iru. Ŝajne ni faris. Ĝi estas iom bizara, ĉar li promenis renversos. Ni nomas tion cimon. Ke estas eraro. Cimon estas eraro en programo, a logika eraro ke mi, la homo, farita. Kial li iras renverse? Ĉu MIT ŝraŭbo supren aŭ ĉu mi? 

Yeah, Mi volas diri, ne MIT kulpo. Ili donis al mi enigmo peco kiu diras turni iun numeron de gradoj. Kaj ĉe Viktoria sugesto, Mi turnis 180 gradojn, kiu estas dekstre intuicio. Sed turnante 180 gradojn laŭvorte signifas turnante 180 gradojn, kaj tio ne vere kion mi volas, ŝajne. Ĉar almenaŭ li estas en tiu dudimensia mondo, tiel decida estas vere iranta por klaki lin renversos. 

Mi verŝajne volas uzi kion bloko anstataŭe, bazita sur kion vi vidas tie? Kiel povus ni riparos tion? Jes, do ni povus atentigi en la kontraŭa direkto. Kaj fakte eĉ tio ne tuj estos sufiĉa, ĉar ni povas nur malfacile kodo al markante maldekstra aŭ dekstra. 

Vi scias kion ni povus fari? Ĝi aspektas kiel ni havas oportuneco bloko tie. Se mi zomi, vidu iu ni ŝatas tie? Do ĝi aspektas kiel MIT havas abstraktado konstruita tie. Tiu bloko ŝajnas esti ekvivalenta al kiu aliaj blokoj, pluralo? 

Ĉi tiu bloko ŝajnas esti ekvivalenta al tiu tuta triopo de blokoj ke ni havas ĉi tie. Do rezultas mi povas simpligi mian programo de akiranta liverita de ĉiuj de tiu kaj ĵus metis ĉi tien. Kaj nun li ankoraŭ iom kalesxo, kaj tio estas bone nun. Ni lasos tion esti. Sed mia programo estas ankoraŭ simpla, kaj tio, ankaŭ, estus reprezentanto de golo en programming-- estas ideale fari vian kodo kiel simpla, kiel kompakta kiel ebla, dum ankoraŭ estante kiel legebla kiel eblas. Vi ne volas fari ĝin tiel konciza ke ĝi estas malfacile komprenebla. 

Sed rimarkis mi anstataŭis tri blokoj kun unu, kaj tio estas disputeble bona afero. Mi abstraída for la nocio de kontrolanta ĉu vi estas rande per nur unu bloko. Nun ni povas amuzi kun ĉi, fakte. Tiu ne aldonas tiel intelekta valoro sed ludema valoro. Mi tuj iros antaŭen kaj ekpreni ĉi sono tie. Do lasu min antaŭeniri kaj lasi min haltigi la programon dum momento. Mi tuj gravuros la jenan: permesante aliro al miaj mikrofono. 

Tie ni iru. Ouch. Ni provu ĉi denove. Tie ni iru. Okej, mi registris la malĝustan aferon. Tie ni iru. Ouch. Ouch. Bone. Nun mi devas forigi tion. Bone. 

Do nun mi havas registrado de simple "Ouch." Do nun mi tuj iros antaŭen kaj nomas tiun "Ouch." Mi tuj reiros al mia skriptoj, kaj nun avizo ekzistas tiu bloko kiu nomiĝas ludi sonon "meow" aŭ ludi sonon "Ouch." Mi tuj treni ĉi, kaj kie mi metis tion por komika efekto? Jes, do nun ĝi estas ia kalesxon, ĉar nun ĉi block-- Rimarku kiel tiu "se sur randon, resalto "estas speco de mem-enhavita. Do mi devas redifini tiun. Lasu min antaŭeniri kaj fari tion. Lasu min forigi tiun kaj reiru al nia originala, pli intenca funcionalidad. Do "se tuŝi randon, tiam" mi volas turni, kiel Viktorio proponita, 180 gradoj. Kaj mi volas ludi la sono "Ouch" tie? 

Yeah, rimarki ĝi estas ekster ke flava bloko. Do tiu, tro, estus cimo, sed mi rimarkis ĝin. Do mi tuj treni ĝin supren tien, kaj avizo nun ĝi estas ene la "se." Do la "se" estas tiu speco de kiel brako-kiel makulo ke estas nur tuj do kio estas ene de ĝi. Tial nun, se mi malzomi ĉe la risko de annoying-- 

COMPUTER: Ouch, Ouch, Ouch. 

DAVID Malan: Kaj simple daŭrigi eterne. Nun nur akceli aferoj tie, lasu min antaŭeniri kaj malfermu, ni say-- lasu min iri al iuj de miaj propraj aferoj de klaso. Kaj lasu min malfermi, diru, ĉi unu farita de unu el niaj instruado uloj paro de jaroj. Do kelkaj el vi eble memoras tiu ludo de en la pasintaj tempoj, kaj ĝi estas vere rimarkinda. Kvankam ni faris la simplajn programojn nun, ni rigardu, kion ĉi vere aspektas. Lasu min bati teatraĵo. 

Do en ĉi tiu ludo, ni havas rano, kaj uzante la sago keys-- Li prenas grandan paŝojn ol mi remember-- Mi havas kontrolon super tiu rano. Kaj la celo estas atingi tra la okupataj vojo sen turni aŭtojn. Kaj ni see-- se mi iros tien, mi atendi loglibra rulumi per. Tio sentas kiel cimon. Tio estas ia eraro. Bone. Mi estas sur ĉi tie, tie, kaj tiam vi tenas iranta ĝis vi akiras ĉiuj la ranojn al la lilio almohadillas. Nun eble tio aspektos des pli kompleksa, sed ni provu rompi ĉi malsupren mense kaj parole en ĝia komponanto blokoj. Do ekzistas verŝajne enigmo peco kiun ni ne vidis ankoraŭ sed tio respondas al pulsbatoj, por tio mi trafis sur la klavaro. 

Do ekzistas verŝajne ia bloko kiu diras, se klavo egalas supren, tiam fari ion kun Scratch-- eble movi ĝin 10 ŝtupoj tiamaniere. Se malsupren ŝlosilo estas premita, movi 10 paŝoj Tiel, nek maldekstren klavon, movi 10 paŝoj Tiel, la 10-ŝtupoj tio. Mi klare turnis la kato en ranon. Do tio estas nur kie la kostumo, kiel Scratch alvokoj it-- ni nur importitaj bildon de la rano. 

Sed kio alia okazas? Kion aliaj linioj de kodo, kio alia enigmo pecoj faris Blake, nia instruado ulo, uzi en tiu programo, ŝajne? Kio faras ĉiu move-- kion programado konstrui? 

Moviĝo, sure-- do la movi bloko, por certa. Kaj kio estas kio movigxas bloko ene de, plej probable? Yeah, ia buklo, eble ĉiam blokas, eble ripeto block-- ripeti ĝis bloko. Kaj tio estas kio faras la ŝtipoj kaj rozo kusenetoj kaj ĉion alian movon reen. Ĝi simple okazas senfine. 

Kial iuj de la aŭtoj movi pli rapide ol la aliaj? Kio estas malsama pri tiuj programoj? Yeah, probable iuj de ilin prenas pli ŝtupojn samtempe kaj iuj el ili malpli paŝoj tuj. Kaj la vida efiko Estas rapida kontre malrapida. 

Kion vi pensas okazis? Kiam mi akiris miajn rano tuta vojo trans la strato kaj la rivero sur rozo kuseneton, iom notinda okazis. Kio okazis kiam mi faris tion? Ĝi haltis. Ke rano haltis, kaj Mi akiris duan rano. Do kio konstrukcio devas esti uzata tie, kio trajto? 

Jes, do ekzistas ia "Se" kondiĉi tie supre, ankaŭ. Kaj ĝi rezultas fjordon ni ne vidis this-- sed ekzistas aliaj blokoj en tie povas diri, se vi estas kortuŝa alia aĵo sur la ekrano, Se vi tuŝis la lilio kuseneto, "tiam". Kaj tiam tio estas kiam ni fari la duan rano aperi. Do eĉ se tiu ludo estas certe tre datita, kvankam unuavide Tie estas tiel iranta on-- kaj Blake ne vipi ĉi supre en du minutoj, ĝi verŝajne prenis lin plurajn horoj por krei tiun ludon bazita sur sia memoro aŭ filmetoj de pasintaj tempoj versio de ĝi. Sed ĉiu el tiuj malgrandaj aferoj irante sur la ekrano en izolado bolas malsupren al tiuj tre simplaj constructs-- movadoj aŭ deklaroj kiel ni diskutis, loops kaj kondiĉoj, kaj tio estas pri ĝi. Ekzistas kelkaj aliaj amatoro karakterizaĵoj. Iuj el ili estas pure estetika aŭ akustiko, kiel la sonoj mi ĵus ludis kun. Sed plejparte, vi havas en tiu lingvo, Scratch, ĉiujn fundamentajn konstruelementoj ke vi havas en C, Java, JavaScript, PHP, Ruby, Python, kaj kiom ajn da aliaj lingvoj. Demandojn pri Scratch? Bone. Do ni ne plonĝi en profundan al Scratch, kvankam vi estas bonvena ĉi semajnfino, speciale se vi havas infanojn aŭ nevinoj kaj nevoj kaj tia, enkonduki ilin al Scratch. Estas vere mirinde ludema medio kun, kiel liaj aŭtoroj diras, tre altaj plafonoj. Kvankam ni komencis kun tre malalta nivelo detaloj, vi povas vere fari sufiĉe per ĝi, kaj tio estas eble manifestacio ĝuste tiun. 

Sed ni nun transiro al iu pli kompleksaj problemoj, se vi volas, konata kiel "serĉado" kaj "Ordigado" pli ĝenerale. Ni havis tiun telefonon libro earlier-- jen alia simple por discussion-- ke ni povis serĉi pli efike ĉar de signifa supozo. Kaj nur por esti klara, kio supozo mi faras kiam serĉanta tra tiu telefono libro? Ke Mike Smith estis en la telefono libro, kvankam mi estus kapabla pritrakti la scenaro sen li tie se mi nur haltis trofrue. La libro estas alfabeta. Kaj tio estas tre donacema supozo, ĉar tiu signifas someone-- Mi speco tranĉi angulo, kiel mi estas rapida ĉar iu alia faris multa malfacila laboro por mi. 

Sed kion se la telefono libro estis Neordigita? Eble Verizon havas mallaborema, ĵus ĵetis ĉies nomojn kaj numerojn en tie eble en la ordo en kiu ili subskribinta por telefono servo. Kaj kiom da tempo estas preni min trovi iun kiel Mike Smith? 1.000 paĝo telefonon book-- kiom paĝojn mi devas trarigardi? 

Ĉiuj ili. Vi estas ia el sorton. Vi laŭvorte devas rigardi ĉiun paĝo se la telefono libro estas nur hazarde ordo. Vi eble ricevos bonŝanca kaj trovi Mike sur la unua paĝo, ĉar li estis la unua kliento ordigi telefono servo. Sed eble estis la lasta, ankaŭ. 

Tiel hazarda ordo estas ne bona. Do eble ni devas ordigi la telefono libro aŭ ĝenerale speco datumoj ke ni estis donita. Kiel ni faru tion? 

Nu, lasu min nur provu simpla ekzemplo tie. Lasu min antaÅ­eniri kaj rulos kiel kelkaj nombroj sur la tabulo. Supozi la numerojn ni estas, diru, kvar, du, unu, tri. Kaj Ben, ordigi tiujn numerojn por ni. 

OK bone. Kiel vi faris tion? Bone. Do komencu per la plej malgranda valoro kaj la plej alta, kaj tio estas vere bona intuicio. Kaj rimarki ke ni homoj estas vere bela bona ĉe solvi problemojn tiel, almenaŭ Kiam la datumoj estas relative malgranda. Kiam vi komencas havi centojn de nombroj, miloj de nombroj, Milionoj de nombroj, Ben probable povis fari ĝin sufiĉe ke rapida, supozante ke ekzistis breĉoj en la nombroj. Sufiĉe facile kalkuli en miliono alie, nur la tempo konsumanta. 

Tial la algoritmo sonas kiel Ben uzata ĝuste nun Estis serĉo por la plej malgranda nombro. Do eĉ se ni homoj povas preni en multajn informojn vide, komputilo estas fakte iom pli limigita. La komputilo povas nur rigardi unu bajton je fojo aŭ eble kvar bajtoj je time-- tiuj tagoj eble 8 bajtoj en time-- sed tre malgranda nombro de bajtoj je donita tempo. 

Tiel donita ke ni vere havas kvar apartaj valoroj here-- kaj vi povas pensi de Ben kiel havado blinders sur se li estus komputilo tia ke li ne povas vidi ion ajn alia ol unu numeron ĉe time-- do ni ĝenerale supozos, kiel en English, ni legis de dekstra al maldekstra. Do la unua numero Ben probable rigardis ĉe kvar kaj tiam tre rapide komprenis ke estas sufiĉe granda number-- lasu min teni rigardanta. 

Ekzistas du. Atendu minuton. Du estas pli malgranda ol kvar. Mi tuj memoris. Du estas nun la plej malgranda. Nun one-- jen eĉ pli bona. Jen eĉ pli malgranda. Mi tuj forgesas pri du kaj nur memoras unu nun. 

Kaj li povis halti rigardanta? Nu, li povus bazita sur tiu informo, sed prefere serĉo la resto de la listo. Ĉar se nulo estis en la listo? Kio se negativa estis en la listo? Li nur scias ke lia respondo estas ĝusta, se li estas ĝisfunde kontrolis la tutan liston. Do ni rigardu la resto de ĉi tiu. Three-- ke estis malŝparo de tempo. Got malfeliĉa, sed mi ankoraŭ ĝentile fari tion. Kaj do nun li supozeble selektis la plej malgranda nombro kaj ĵus metis komence de la listo, mi faros ĉi tie. Kion vi faris poste, kvankam vi ne pensas pri ĝi preskaŭ al tiu mezuro? Ripetu la procezon, tiel ia buklo. Estas familiara ideo. Do tie estas kvar. Jen nun la plej malgranda. Jen kandidato. Ne plu. Nun mi vidis du. Jen la sekva plej malgranda ero. Three-- tio ne pli malgranda, do nun Ben povas desxiri la du. 

Kaj nun ni ripeti la procezon, kaj kompreneble tri iĝas eltiris sekva. Ripeti la procezon. Kvar iĝas eltiris. Kaj nun ni estas ekstere de nombroj, do la listo devas esti ordo. 

Kaj efektive, tio estas formala algoritmo. Komputila sciencisto farus nomas tiun "selektado varon," la ideo estanta speco de listo iteratively-- denove kaj denove kaj denove elektante la plej malgranda nombro. Kaj kio estas agrable pri ĝi estas nur tiom Darn intuicia. Ĝi estas tiel simpla. Kaj vi povas ripeti la saman agon denove kaj denove. Ĝi estas simpla. 

En tiu kazo ĝi estis rapida, sed kiom longe? i vere preni? Ni faras ĝin ŝajni kaj sentas iom pli teda. Do unu, du, tri, kvar, kvin ses, sep, ok, naŭ, 10, 11, 12, 13, 14, 15 16-- arbitra nombro. Mi nur volis pli ĉi tempo ol nur kvar. Do se mi havas tutajn faskon de nombroj now-- ĝi ne gravas kion ili are-- ni pripensi kion tio algoritmo vere ŝatas. 

Supozi ekzistas nombroj ekzistas. Denove, ne gravas kio Ili estas, sed ili estas hazardaj. Mi aplikanta Ben algoritmo. Mi devas elekti la plej malgrandan numeron. Kion mi faras? Kaj mi tuj fizike faru tiun fojon agi ĝin. Rigardante, rigardante, rigardante, rigardante, rigardanta. Nur per la tempo mi akiras Fine de la listo povas Mi konscias la plej malgranda nombro estis du ĉi tempo. Oni ne estas en la listo. Do mi metis malsupren du. 

Kion mi faru? Rigardante, rigardante, rigardante, rigardanta. Nun mi trovis la nombro sep, ĉar ekzistas mankoj en tiuj numbers-- sed nur arbitra. Bone. Do nun mi povas meti malsupren sep. Rigardante rigardis, rigardis. 

Nun Mi supozas, de Kompreneble, Ben ne havas kroman RAM, ekstra memoro, ĉar, kompreneble, Mi serĉas en la sama nombro. Certe mi povus rememoris ĉiuj tiuj nombroj, kaj tio estas absolute vera. Sed se Ben memoras cxiujn de la nombroj li vidis, Li ne vere faris fundamenta progreso ĉar li jam havas la eblo serĉi tra la nombroj sur la tabulo. Memorante ĉiuj nombroj ne helpas, ĉar li povas ankoraŭ kiel komputilo nur rigardi, ni diris unu nombro samtempe. Do ekzistas nenia trompanto tie ke vi povas utiligi. 

Do fakte, kiel mi teni serĉanta la listo, Mi laŭvorte devas nur plu iri reen tra ĝi, elsxirintaj la sekva plej malgranda nombro. Kaj kiel vi povas ia konkludi mia stulta movadoj, ĉi ĵus ricevas tre teda tre rapide, kaj mi ŝajnas esti revenanta kaj reen, tien kaj reen sufiĉe. Nun esti justa, mi ne devas iri tiom, nu, ni see-- esti bela, Mi ne devas iri tre kiel multaj paŝoj ĉiufoje. Ĉar, kompreneble, kiel mi elekti numeroj de la listo, la ceteraj listo estas akiranta pli mallonga. 

Kaj do ni pensu pri kiom da paŝoj mi reale traipsing tra ĉiu tempo. En la unua situacio Ni havis 16 numerojn, kaj tiel maximally-- ni nur fari tion dum discussion-- Mi devis serĉi tra 16 nombroj trovi la plej malgranda. Sed unufoje mi elsxirintaj la plej malgranda nombro, kiom longe estis la ceteraj listo, kompreneble? Nur 15. Tiom kiom nombroj faris Ben aŭ mi rigardi tra la dua tempo ĉirkaŭe? 15, nur por iri kaj trovi la plej malgranda. Sed nun, kompreneble, la listo estas, Ankaŭ malgranda ol ĝi estis antaŭe. Do kiom da ŝtupoj faris mi devas preni la venontan fojon? 14 kaj tiam 13 kaj tiam 12, krom streketo streketo dot, ĝis mi forlasis kun nur unu. Do nun komputila sciencisto farus petu, nu, kio faras ke ĉiuj egalaj? Ĝi vere egalas iun konkretan numero kiun ni povis certe fari aritmetike, sed ni volas paroli pri la efikeco de algoritmoj iom pli formulaically, sendependa de kiom longa la lerta estas. 

Kaj tiel vi scias kion? Tio estas 16, sed kiel mi diris antaÅ­e, ni simple nomas la grandeco de la problemo n, kie n estas iu nombro. Eble estas 16, eble estas tri, eble estas miliono. Mi ne scias. Mi ne zorgas. Kion mi vere volas estas formulo kiu mi povas uzi kompari tiun algoritmon kontraÅ­ aliaj algoritmoj ke iu povus aserti estas bona aux malbona. 

Do rezultas, kaj mi nur scias tion de lernojaro lernejo, ke tio efektive funkcias al la sama aĵo kiel n super n plus unu super du. Kaj tio okazas egali, de Kompreneble, n kvadratoj plus n super du. Do se mi volis formulon cxar kiom da ŝtupoj estis implikitaj en rigardante ĉiujn de tiuj nombroj multfoje kaj denove kaj denove, mi dirus ĝi estas n kvadratoj plus n super du. Sed vi scias kion? Ĉi nur aspektas senorda. Mi nur vere volas ĝenerala senco de aĵoj. Kaj vi eble memoras de alta lernejo kiu ekzistas estas la nocio de Superaj termino. Kiu el tiuj terminoj, la n kvadrato, la n, aŭ la duono, havas la plej trafo tempo? La granda n prenas, kio pri tiaj aferoj la plej? 

Alivorte, se mi plug en miliono, n kvadratoj tuj estos plej verŝajne la domina faktoro, ĉar miliono fojojn mem estas multe pli granda ol plie unu kroma miliono. Do vi scias kion? Jen tia Darn granda numeron se vi akordas numero. Tio ne vere gravas. Ni ĵus tuj kruco kiu eksteren kaj forgesi pri ĝi. Kaj tiel komputila sciencisto dirus ke la efikeco de tiu algoritmo estas sur la ordo de n squared-- Mi signifas vere estas proksimuma kalkulado. Ĝi estas ia krude n kvadratoj. Dum tempo, la pli granda kaj granda n prenas, tiu Estas bona takso por kio la efikeco aŭ manko de efikeco de tiu algoritmo reale estas. Kaj mi derivi ke, kompreneble, de reale fari la math. Sed nun mi simple svingante miaj manoj, ĉar mi nur volas ĝenerala senco de tiu algoritmo. 

Tiel uzante la sama logiko, dume, ni pripensu alian algoritmo ni jam rigardis at-- lineara serĉo. Kiam mi estis serĉanta por la telefono book-- Ne ordigado ĝin serĉado tra la telefono book-- ni tenis dirante ke ĝi estis 1.000 ŝtupoj, aŭ 500 ŝtupoj. Sed ni ĝeneraligi tion. Se estas n paĝoj la telefono libro, kio estas la rula tempo aŭ la efikeco de lineara serĉo? Ĝi estas sur la ordo de kiom da paŝoj trovi Mike Smith uzanta lineara serĉo, la unua algoritmo, aŭ eĉ la duan? 

En la plej malbona kazo, Mike Estas fine de la libro. Do se la telefono libro havas 1.000 paĝojn, ni diris lastan fojon, en la plej malbona kazo, ĝi povus preni malglate kiom multaj paĝoj por trovi Mike? Kiel 1,000. Ĝi estas supera baro. Ĝi estas plej malbona ebla situacio. Sed denove, ni malproksimigi de nombroj kiel 1,000 nun. Estas nur n. 

Do kio estas la logika konkludo? Trovanta Mike en telefono Libro kiu havas n paĝoj povus preni, en la plej malbona kazo, kiom da paŝoj sur la ordo de n? Kaj fakte komputilo sciencisto dirus ke la rula tempo, aŭ la rendimenton aŭ la efikecon aŭ senefikeco, de algoritmo kiel lineara serĉo estas sur la ordo de n. Kaj ni povas apliki la samajn logiko de transirante ion kiel mi ĵus faris por la dua algoritmo ni havis kun la telefono libro, kie ni iris du paĝojn samtempe. 

Do 1,000 paĝo telefono libro eble nin 500 paĝo turnoj, plus unu se ni duobligi dorson iomete. Do se telefono libro havas n paĝoj, sed ni faras du paĝojn samtempe, jen malglate kio? N super du, tiel ke estas kiel n super du. Sed mi faris la aserto de antaŭ momento ke n super two-- jen speco de la sama kiel ĵus n. Estas nur konstanta faktoro, komputilo sciencistoj dirus. Ni nur enfokusigi la variabloj, really-- la plej granda variabloj en la ekvacio. 

Do lineara serĉo, ĉu faris unu paĝo samtempe du paĝojn samtempe, estas ia fundamente la sama. Ĝi estas ankoraŭ sur la ordo de n. Sed mi asertis kun mia bildo pli frue ke la tria algoritmo ne lineara. Ĝi ne estis rekta linio. Estis tiu kurba linio, kaj la algebra formulo estis kio? Protokolo de n-- tiel ensaluti bazo du de n. Kaj ni ne devas iri en tro multe detalon sur logaritmoj hodiaŭ, sed plej komputilo sciencistoj ne volis eĉ al vi, kion la bazo estas. Ĉar ĝi estas ĉiuj nur konstanta faktoroj, tiel diri, nur iometa nombraj diferencoj. Kaj tial ĉi estus tre komuna maniero por aparte formala komputilo sciencistoj ĉe tabulo aŭ programistoj ĉe blanka tabulo fakte argumentante ke algoritmo uzus kia la efikecon ilia algoritmo estas. 

Kaj tio ne nepre io vi diskuti en ajna granda detalo, sed bona programisto estas iu kiu havas solidan, formala fono. Li estas kapabla paroli al vi en tiu speco de vojo kaj fakte faras kvalita argumentoj kial unu algoritmo aŭ unu peco de programaro estas supera iel alia. Ĉar vi povus certe nur kuri unu persono programo kaj kalkulu la numeron de duaj ĝi prenas ordigi iujn numerojn, kaj vi povas kuri iuj alia persono programo kaj kalkulu la numeron de duaj prenas. Sed tio estas pli ĝenerala maniero, ke vi povas uzi analizi algoritmojn, Se vi volas, nur sur papero aŭ nur parole. Sen eĉ kurante ĝin, sen eĉ provas specimeno enigoj, vi povas simple rezoni per ĝi. Kaj tiel per dunganta ellaboranto aŭ se havi lin aŭ ŝin ia argumenti al vi kial ilia algoritmo, iliajn sekretajn saŭco por serĉado miliardoj de retpaĝoj por via entrepreno estas bona, ĉi tiuj estas la specoj de argumentoj ili devus ideale povos fari. Aŭ almenaŭ tiuj estas la specoj de aferoj kiu venus supren en diskuto, ĉe almenaŭ en tre formala diskuto. Bone. Kaj Ben proponis ion nomita selektado varon. Sed mi tuj proponi ke ekzistas aliaj manieroj fari tion, ankaŭ. Kion mi ne vere ŝatas pri Ben algoritmo estas ke li tenis piediranta aŭ esti mi marsxas tien kaj reen kaj reen kaj reen. Kio se anstataŭe mi devis fari ion similan nombroj tie kaj mi devis nur trakti ĉiun numeron laŭvice kiel mi destinis? 

Alivorte, jen mian liston de nombroj. Kvar, unu, tri, du. Kaj mi tuj faru la sekvajn. Mi tuj enigi la numerojn kie ili apartenas prefere ol elektanta ilin unuope. Alivorte, jen la numero kvar. 

Jen mia originala listo. Kaj mi tuj subteni esence nova listo tie. Do tiu estas la malnova listo. Tiu estas la nova listo. Mi vidas la numeron kvar unuaj. Mia nova listo estas komence malplena, tial estas bagatele la kazo ke kvar estas nun varia listo. Mi nur prenante la numeron mi donita, kaj mi metis ĝin en mian novan liston. 

Estas ĉi tiu nova lerta ordo? Yeah. Ĝi estas stulta ĉar estas nur unu elemento, sed ĝi estas absolute ordo. Nenio estas maloportune. Ĝi estas pli interesa, ĉi tiu algoritmo, kiam mi movas al la sekva paŝo. 

Nun mi havas unu. Tial oni kompreneble apartenas ĉe la komencante aŭ la fino de ĉi tiu nova listo? La komenco. Do mi devas fari iun laboron nun. Mi estis prenanta iun liberecojn kun mia markilo por nur desegni aferojn kie mi volas ilin, sed tio ne estas vere precizaj en komputilo. Komputila, kiel ni scias, ĝi havas RAM aŭ Hazarda Aliro Memoro, kaj jen unu bajto kaj alia bajto kaj alia bajto. Kaj se vi havas gigabajto de RAM, vi havas miliardoj bajtoj, sed ili estas fizike en unu loko. Vi povas ne nur movi aĵojn ĉirkaŭe strekante ĝin sur la tabulon kien ajn vi volas. Tial se mia nova listo havas kvar lokoj en memoro, bedaŭrinde la kvar estas jam en la malĝusta loko. 

Do enmeti la numeron unu Mi ne povas simple desegni ĝin tien. Tiu memoro loko ne ekzistas. Ke estus trompado, kaj mi estis trompado bilde dum kelkaj minutoj tie. Do vere, se mi volas meti tie, Mi devas provizore kopiu la kvar kaj surmetu la tie. 

Tio estas bone, ke estas ĝusta, tio teknike eblas, sed rimarkas ke estas ekstra laboro. Mi ne simple metu la nombro en loko. Mi unue devis movi nombro, tiam metis ĝin en loko, do mi specon de duobligis mian kvanto de laboro. Observu do, ke en menso. 

Sed mi nun faris kun tiu elemento. Nun mi volas ekpreni la numero tri. Kie, kompreneble, ĝi apartenas? Inter. Mi ne povas trompi anymore kaj nur meti ĝin tie, ĉar, denove, ĉi tiu memoro estas en fizika lokoj. Do mi devas kopii la kvar kaj metis la tri super tie. Ne granda interkonsento. Estas nur unu kroma paŝo again-- sentas tre malmultekosta. 

Sed nun mi pluiru al la du. Ambaŭ kompreneble apartenas tie. Nun vi komencas vidi kiel la laboro povas amasiĝas. Nun kion mi devas fari? Yeah, Mi devi movi la kvar, Mi tiam devas kopii la tri, kaj nun mi povas enmeti la du. Kaj la kaptaĵo kun ĉi algoritmo, interese sufiĉe, estas ke eble ni havas pli ekstremaj kazo kie ĝi diru ok, sep, ses, kvin, kvar, tri, du, unu. Tio estas, en multaj kuntekstoj, la plej malbona kazo scenaro, ĉar la darn afero Estas laŭvorte malantaŭen. 

Fakte ne tuŝas Ben algoritmo, ĉar Ben selektado ia li tuj teni irante tien kaj reen tra la listo. Kaj ĉar li ĉiam rigardanta tra la tutaj ceteraj lerta, ne gravas kie la elementoj estas. Sed en ĉi tiu kazo kun mia enmeto approach-- ni provu tion. 

Do unu, du, tri, kvar, kvin, ses, sep, ok. Unu, du, tri, kvar, kvin, ses, sep, ok. Mi tuj prenos la ok, kaj kie mi metis ĝin? Nu, je la komenco de mia listo, ĉar tiu nova listo estas ordigita. Kaj mi transiras ĝin. 

Kie mi metis la sep? Darn ĝin. Bezonas iri tien, tiel Mi devas fari iun kopiado. Kaj nun la sep iras tien. Nun mi pluiru al la ses. Nun ĝi estas eĉ pli laboro. 

Ok devas iri tien. Sep devas iri tien. Nun la ses povas iri tien. Nun mi havigu la kvin. La ok devas iri tie sep devas iri tie, ses devas iri tien, kaj nun kvin ripeto. Kaj mi preskaux movante ĝin senĉese. 

Do fine, ĉi algorithm-- ni nomas ĝin inserción sort-- reale havas multe da laboro, tro. Estas nur malsamaj speco de laboro ol Ben. Ben laboro havis mi iras reen la tutan tempon, elektante la sekvanta malgranda elemento denove kaj denove. Tiel okazis tio tre vida ia laboro. 

Tiu alia algoritmo, kiu estas ankoraŭ correct-- ĝi ricevos la laboron done-- nur ŝanĝas la kvanton de laboro. Aspektas kiel komence vi ŝparante, ĉar vi estas nur kontraktanta kun ĉiu elemento supren fronto sen marŝante ĉiuj la vojo tra la listo kiel Ben estis. Sed la problemo estas, speciale en tiuj freneza kazoj kie ĉio dorsdirekte vi estas nur ia prokrasti la laboremo ĝis vi devas fiksi vian erarojn. 

Kaj do se vi povas imagi tiun ok kaj sep kaj ses kaj kvin kaj poste kvar kaj tri kaj du movi sin tra la listo, ni ĵus ŝanĝis la tipo de laboro ni faras. Anstataŭ fari ĝin en la komencante de mia ripeto, Mi nur faras ĝin en la Fine de ĉiu ripeto. Do rezultas ke tiu algoritmo, Ankaŭ ĝenerale nomita inserción varon, estas ankaŭ sur la ordo de n kvadratoj. Ĝi estas fakte ne pli bona, ne bona ĉe ĉiuj. 

Tamen, ekzistas tria alproksimiĝo Mi kuraĝigus ni konsideri, kio estas tio. Do supozu mia lerta, por simpleco denove, estas kvar, unu, tri, two-- nur kvar numeroj. Ben havis bonan intuicion, bona homa intuicio antaŭe, por kiuj ni fiksis la tuta listo eventually-- inserción varo. Mi kaĵolis ni kune. Sed ni konsideru la simpla maniero ripari tiun liston. 

Tiu listo ne estas ordigitaj. Kial? En la angla, klarigas kial ĝi ne vere ordo. Kion tio signifas ne esti ordo? 

Lernanto: Tio ne secuencial. 

DAVID Malan: Ne secuencial. Donu al mi ekzemplon. 

Lernanto: Metu ilin en ordo. 

DAVID Malan: Bone. Donu al mi pli specifa ekzemplo. 

Lernanto: Supreniranta ordo. DAVID Malan: Ne suprenirante ordo. Esti pli preciza. Mi ne scias kion vi celas diri per supreniranta. Kio okazas? 

Lernanto: La plej malgranda de la nombroj ne en la unua spaco. 

DAVID Malan: La plej malgranda nombro de Ne en la unua spaco. Esti pli specifaj. Mi komencas populariĝis. Ni rakonti, sed kio estas el ordo tie? 

Lernanto: Nombraj sekvenco. DAVID Malan: Nombraj sekvenco. Ĉies ia plenumado ĝi here-- tre alta nivelo. Nur laŭvorte diri min kio estas erara kiel kvin-jaraĝa forto. 

Lernanto: Plus unu. 

DAVID Malan: Kio estas tio? 

Lernanto: Plus unu. 

DAVID Malan: Kion signifas plus unu? Donu malsama kvin-jaraĝa. Kio okazas, panjo? Kio okazas, paĉjo? Kion signifas ĉi tio ne ordo? 

Lernanto: Ĝi ne estas la gxusta loko. 

DAVID Malan: Kio estas ne en la ĝusta loko? 

Lernanto: Kvar. DAVID Malan: Bone, bone. Do kvar ne kie ĝi devus esti. Aparte, estas tiu rajto? Dudek unu, la unua du nombroj mi vidas. Estas ĉi tiu rajto? Ne, ili estas el ordo, ĉu ne? Fakte, pensas nun pri komputilo, ankaŭ. Ĝi povas nur rigardi eble unu, eble du aferojn ĉe once-- kaj fakte nur unu afero samtempe, sed povas almenaŭ rigardi unu afero tiam la sekva afero tuj apud ĝi. 

Tiaj estas tiuj en ordo? Kompreneble ne. Do vi scias kion? Kial ni ne prenos bebo paŝoj fiksi tiun problemon anstataŭ fari tiujn fancy algoritmoj kiel Ben, kie li ia fiksi ĝin looping tra la listo anstataŭ fari kion mi faris, kie Mi nur ia fiksita kiel ni iros? Ni nur laŭvorte detruu la nocio de order-- nombra ordo, nomas ĝin kion ajn vi want-- en tiuj paroj komparoj. 

Kvar kaj unu. Estas ĉi la ĝusta ordo? Do ni ripari tiun. Unu kaj kvar, kaj poste ni simple kopiu tion. Bone, bone. Mi riparis unu kaj kvar. Tri kaj du? Ne Lasu miajn vortojn kongrui miajn fingrojn. Dudek tri? 

Ĝi estas ne en ordo, do mi tuj fari unu, tri, kvar, du. OK bone. Nun dudek du? Ni devas redifini tiun ankaŭ. Do unu, tri, du, kvar. Tiel estas ĝi ordo? Ne, sed ĉu ĝi pli proksima al ordo? 

Estas, ĉar ni fiksis ĉi eraro, ni fiksis la miskompreno, kaj ni fiksis ĉi eraras. Do ni fiksis tri erarojn disputeble. Ankoraŭ ne vere aspektas ordo, sed ĝi estas objektive pli proksima al ordo ĉar ni fiksis kelkaj el tiuj eraroj. 

Nun kion mi faru? Mi ia atingis la finon de la listo. Mi ŝajnis esti fiksita ĉiuj eraroj, sed ne. Ĉar tiukaze, iuj nombroj eble bobelis proksimaj aliaj nombroj ke ankoraŭ el ordo. Do ni faru ĝin denove, kaj Mi instruos vin simple fari ĝin en loko ĉi tempo. Unu kaj tri? Estas bone. Tri kaj du? Kompreneble ne, do ni ŝanĝu tion. Tial du, tri. Tri kaj kvar? Kaj nun ni nur esti aparte pedanta tie. Ĉu ordo? Vi homoj scias ĝi estas ordo. 

Mi devas provi denove. Tiel Olivia proponas mi reprovu. Kial? Ĉar komputilo ne havas la lukso de niaj homaj okuloj de nur rigardante back-- OK, mi faris. Kiel la komputilo determinas ke la listo estas jam ordo? Mekanike. 

Mi devus iri tra refoje, kaj nur se mi ne fari / trovos erarojn mi tiam konkludi kiel la komputilo, Yep, Ni estas bone iri. Do unu kaj du po tri, tri kaj kvar. Nun mi povas definitive diri ĉi estas ordo, ĉar mi nenion ŝanĝas. GXi estus nun cimon kaj ĵus malsaĝa se mi, la komputilo, demandis tiujn samajn demandojn denove atendante malsamajn respondojn. Ne devus okazi. 

Kaj do nun la listo estas ordigita. Bedaŭrinde, veturtempo de tiu algoritmo estas ankaŭ n kvadratoj. Kial? Ĉar vi havas n nombroj, kaj en la plej malbona kazo vi devas movi n nombroj n fojoj ĉar vi devos teni iranta reen por kontroli kaj potenciale ripari tiuj nombroj. Kaj ni povas fari pli formalan analizon, tro. 

Do tiu estas la tuta diri ni prenis tri malsamaj aliroj, oni ili tuj intuicia la batilon de Ben al mia proponita inserción speco al ĉi tiu kie ia forgesu la arbaro por la arboj komence. Sed poste se vi preni retropaŝon, voilà, ni fiksis la ordigado nocio. Do tiu estas, kuraĝas diri, suba nivelo eble ol iuj el tiuj aliaj algoritmoj, sed ni vidu se ni ne povas visualizar tiuj tra ĉi. 

Do tiu estas iu bela programaro kiu iu skribis uzante bunta stangoj kiuj estas tuj fari la sekvan por ni. Ĉiu de ĉi tiuj stangoj reprezentas nombron. Taller la trinkejo, la pli granda la nombro, pli malgranda la trinkejo, la pli malgranda la nombro. Do ideale ni volas belan piramido kie komenciĝas malgrandaj kaj ricevas grandan, kaj tio signifus ke tiuj stangoj estas ordo. Do mi tuj iros antaŭen kaj elekti, ekzemple Ben algoritmo first-- selektado varon. 

Kaj rimarki kio ĝi estas faranta. La vojo ili elektis al bildigi tiun algoritmon estas ke, same kiel mi estis promenante tra mia lerta, tiu programo estas piediranta tra lia lerta de numeroj, elstarante en rozkolora ĉiu numeron ke ĝi rigardas. Kaj kio estas ronde okazi ĝuste nun? 

La plej malgranda nombro kiu Mi nek Ben trovis subite iĝas proponita al la komenco de la listo. Kaj rimarki oni faris elhejmigi la nombro kiu estis tie, kaj tio estas perfekte bone. Mi ne eniros en tiu nivelo de detalo. Sed ni devas meti ke nombro ie, Do ni simple kopiis ĝin al la malfermita loko kiu estis kreita. Do mi tuj rapidi ĉi supren, ĉar alie ĝi iĝas tre teda rapide. Kuraĝigo speed-- tie ni iru. Tial nun sama principo Mi aplikis, sed vi povas komenci senti la algoritmo, se vi volo, aŭ vidi ĝin iom pli klare. Kaj tiu algoritmo havas la efikon de elektante la sekva plej malgranda elemento, tiel vi tuj komencos vidu deklivirejo supre maldekstre. Kaj sur ĉiu ripeto, kiel mi proponis, ĝi faras iom malpli laboro. Ĝi ne devas iri la tutan vojon reen al la maldekstra fino de la listo, ĉar ĝi jam konas tiujn estas ordo. Do speco de sentas estas akceli, kvankam ĉiu paŝo estas prenante la sama kvanto de tempo. Ekzistas nur malmultaj paŝoj ceteraj. Kaj nun vi povas ia sentas la algoritmo purigi la fino de ĝi, kaj ja nun ĝi estas ordo. 

Tiel inserción varo estas ĉiuj farita. Mi bezonas re-randomize la tabelo. Kaj rimarkos mi povas nur teni randomizing ŝin, kaj ni akiros proksimuma kalkulado de la sama alproksimiĝo, inserción varo. Lasu min malrapidigi ĝin malsupren ĉi tien. Komencu ke super. Halti. 

Ni salti kvar. Tie ni iru. Randomize ili tabelo. Kaj tie ni go-- inserción varo. Ludi. Rimarki ke ĝi estas kontraktanta kun ĉiu elementon i renkontas tuj, sed se ĝi apartenas en la malĝusta loko avizo ĉiuj de la laboro kiu devas okazi. Ni devas konservi sxangxigxantaj pli kaj pli elementoj por fari lokon por la unu ni volas meti en lokon. 

Do ni koncentranta sur la maldekstra fino de la listo nur. Rimarku ni eĉ ne rigardis at-- ni ne elstarigita en rozkolora ion dekstre. Ni nur pritraktas la problemoj ni iros, sed ni kreas multajn labori por ni mem ankoraŭ. Kaj do se ni akceli ĉi supren nun iri al kompletiĝo, ĝi havas malsaman senton al ĝi efektive. Ĝi simple koncentranta sur la maldekstra fino sed faras iom pli da laboro kiel needed-- ia glatigante aferoj super, fiksi aferojn, sed kontraktanta finfine kun ĉiu elemento unuope ĝis ni atingos estas- bone, ni ĉiuj scias ke tiu tuj finos, do ĝi estas iom underwhelming eble. 

Sed la lerta en la end-- spoiler-- tuj estos ordo. Do ni rigardu tiun lasta. Ni ne povas simple salti nun. Ni estas preskaŭ tie. Du iri, oni iros. Kaj voilà. Bonega. 

Do nun ni faru unu lasta, re-randomizing kun bobelo varo. Kaj rimarki tie, precipe se mi malrapidigos ĝin malsupren, ĉi tio konservi rapidas tra. Sed rimarki ĝin nur faras duope comparisons-- ia lokaj solvoj. Sed tuj kiam ni atingos Fine de la listo en rozkolora, kion tuj devos okazi denove? Yeah, ĝi tuj devas rekomencos, ĉar nur fiksa duope erarojn. Kaj ke eble malkaŝis ankoraŭ aliaj. Kaj do se vi akceli ĉi supren, vi vidu, kiom la nomo implicas, la malgrandaj elements-- aŭ pli ĝuste, la grandaj elements-- komencas al bobelo ĝis la supro, se vi volas. Kaj la pli malgrandaj elementoj estas komencantaj bobelo malsupren maldekstren. Kaj efektive, jen speco de la vida efekto ankaŭ. Kaj tiel tiu finos finante en tre simila maniero, ankaŭ. 

Ni ne devas logxi sur tiu aparta. Lasu min malfermi ĉi nun, tro. Ekzistas kelkaj aliaj ordigado algoritmoj en la mondo, kelkaj el kiuj estas kaptitaj tie. Kaj speciale por lernantoj kiuj ne nepre vida aŭ matematika, kiel ni faris antaŭe, ni povas Ankaŭ tion audially se ni asocias sono kun tiu. Kaj simple por amuzo, jen kelkaj malsamaj algoritmoj, kaj unu el ili precipe vi tuj rimarkos nomiĝas "merge varon." 

Ĝi estas fakte principe bona algoritmo, tia ke kunfandi varon, unu el tiujn vi estas estonta vidi, ne ordo de n kvadratoj. Ĝi estas sur la ordo de n fojoj logo de n, kiu estas vere malgranda kaj tiel rapide ol tiuj aliaj tri. Kaj ekzistas kelkaj aliaj malsaĝa kiuj vidos. 

Do jen ni iras kun iuj sono. Jen inserción varo, do denove ĝi estas nur pritraktas la elementoj kiel ili venis. Tio estas bobelo varo, do estas konsiderante ilin paroj samtempe. Kaj denove, la plej grandaj elementoj estas bobelis ĝis la supro. 

Poste supre selektado varon. Tio Ben algoritmo, kie denove li elektanta ripete la sekva plej malgranda ero. Kaj denove, nun vi povas vere aŭdi tion ĝi estas rapidigo sed nur tiom kiel ĝi estas fari malpli kaj malpli labori sur ĉiu ripeto. Tiu estas la pli rapida unu, kunfandi varon, kiu ordigado kukojn nombroj kune kaj tiam kombini ilin. Tiel look-- maldekstren duono estas jam ordo. 

Nun ĝi estas ordigado la dekstra duono, kaj nun ĝi tuj kombini ilin en unu. Tio estas iu nomita "Gnome varo." Kaj vi povas ia vidi ke ĝi tuj reen, fiksinte laboro iomete tie kaj tie antaŭ ĝi procedas al nova laboro. Kaj tio estas ĝi. Ekzistas alia speco, kiu estas vere nur por akademiaj celoj, nomita "stulta speco", kiu prenas viajn datumojn, ordigas ŝin hazarde, kaj tiam kontrolas se estas ordigitaj. Kaj se ne, ĝi re-ordigas ŝin hazarde, kontrolas se ĝi estas ordo, kaj se ne ripetas. Kaj en teorio, _probabilistically_ tio kompletigos, sed post tre iom de tempo. Ĝi ne estas la plej eficiente de algoritmoj. Tiel demandojn sur tiuj aparta algoritmoj aŭ io rilata tie ankaŭ? 

Nu, ni nun turmentus aparte kion ĉiuj tiuj linioj estas ke mi estis tiranta kaj kion mi supozas la komputilo povas fari sub la kapuĉo. Mi argumentus ke ĉiuj tiuj nombroj Mi daŭre drawing-- ili bezonos akiri stokitaj ie en memoro. Ni forigi ĉi ulo nun, tro. 

Do pecon de memoro en computer-- tiel RAM DIMM estas kion ni serĉis hieraŭ, duala inline memoro module-- aspektas jene. Kaj ĉiu el tiuj malgrandaj nigraj pecetoj estas iu nombro da bajtoj, tipe. Kaj tiam la oro pingloj estas kiel la dratoj kiuj konektas ĝin al la komputilo, kaj la verda silicon estraro estas nur kio tenas ĉiun ĉiuj kune. Do kion signifas tio vere signifas? Se mi specon de desegni ĉi tiu bildo, ni supozu por simpleco ke DIMM, duala inline memoro modulo, Estas unu gigabajto de RAM, unu gigabajto de memoro, kiu estas kiom da bitokoj entute? Unu gigabajto estas kiom da bitokoj? Pli ol tio. 1,124 estas kilogramo, 1.000. Mega estas miliono. Giga estas miliardo. 

Ĉu mi mensogis? Ni povas eĉ legi la etikedon? Tiu estas fakte 128 gigabajtoj, do estas pli. Sed ni ŝajnigi ĉi Estas nur unu gigabajto. Do tio signifas ke estas miliardoj bajtoj de memoro havebla al mi aŭ 8 miliardoj bitoj, sed ni iras paroli en terminoj de bajtoj nun, movanta antaŭen. 

Do kion tio signifas estas tio unu bajto, ĉi tio estas alia bajto, tiu estas alia bajto, kaj se ni vere volis esti specifa ni devus desegni miliardoj iom kvadratoj. Sed kion tio signifas? Nu, lasu min nur zomi en sur ĉi tiu bildo. Se mi havas iun kiu aspektas tiel nun, jen kvar bajtoj. 

Kaj tiel mi povis meti kvar numerojn tie. Unu, du, tri, kvar. Aŭ mi povus meti kvar literojn aŭ simboloj. "Hej!" povus iri rekte tie, ĉar ĉiu de la literoj, ni diskutis pli frua, povus esti reprezentata kun ok bitoj aŭ ASCII aŭ bajto. Do alivorte, vi povas metis 8 miliardoj aferojn interne de ĉi tiu bastono de memoro. Kion tio signifas meti aferojn reen malantaŭeniri por malantaŭeniri en memoro tiel? Jen kion programisto nomus "tabelo". En komputila programo, vi ne kredas pri la subkuŝanta aparataro, en si mem. Vi nur pensu pri vi mem kiel havado aliro al miliardoj bajtoj Entute kaj vi povas ion vi volas kun ĝi. Sed pro konveneco ĝi estas ĝenerale utila teni vian memoron dekstra apud la alia tiel. Do se mi zomi en sur this-- ĉar ni ja ne iras desegni miliardoj iom squares-- ni supozu ke tiu tabulo reprezentas ke bastono de memoro nun. Kaj mi nur tiri nekredeblaj mia markilo finas donante min ĉi tie. Do nun ni havas bastono de memoro sur la tabulo ke estas atingis unu, du, tri, kvar, kvin, ses, unu, du, tri, kvar, kvin, ses, seven-- do 42 bajtoj de memoro sur la ekrano entute. Dankon. Jes, ĉu mia aritmetiko dekstra. Do 42 bajtoj de memoro tie. Do kion signifas ĉi reale signifas? Nu, komputilprogramisto ĉu vere ĝenerale pensi pri tiu memoro direccionable. Alivorte, ĉiu el tiuj lokoj en memoro, en aparataro, havas unikan adreson. 

Ĝi ne estas tiel kompleksa kiel Unu Brattle Kvadrata, Kembriĝo, Meso., 02138. Anstataŭe, ĝi estas nur nombro. Tiu estas bajto nombro nulo, ĉi tiu estas unu, jen du, jen tri, kaj tio estas 41. Atendu minuton. Mi pensis, ke mi diris 42 antaŭ momento. Mi komencis rakonti al nulo, do tio estas vere ĝentilaj. Nun ni ne devas reale desegni ĝin kiel krado, kaj se vi tiros gxin kiel krado Mi pensas aferojn reale akiri iom iluzia. Kio programisto volas; en sia propra menso, ĝenerale opinias pri tio memoro kiel estas ĝuste kiel bendo, Kiel peco de maskante bendo ke nur daŭras por ĉiam aŭ ĝis vi elĉerpas de memoro. Tiom pli komuna maniero tiri kaj nur pensas pri memoro estus tiu ĉi estas bajto nulo, unu, du, tri, kaj poste pentras, punkto, ĝi pentras. Kaj vi havas 42 tiajn bajtoj entute, eĉ kvankam fizike ĝi povus reale esti io pli da kiel tio. 

Do se vi nun opinias pri via memoro kiel tiu, kiel bendo, jen kion programisto denove vokus tabelo de memoro. Kaj kiam vi volas reale stoki io en komputila memoro, vi ĝenerale faras vendejo aferoj back-to-back to back-to-back. Do ni parolis pri nombroj. Kaj kiam mi volis solvi problemoj kiel kvar, unu, tri, du, kvankam mi estis nur desegnante nur la nombroj kvar, unu, tri, du sur la tabulo, la komputilo estus vere havas ĉi aranĝo en memoro. 

Kaj kio estus apud la du en la komputilo la memoro? Nu, ne estas respondo al tiu. Ni ne vere scias. Kaj tiel longe kiel la komputilo ne bezonas ĝin, ĝi ne devas zorgi kio estas proksima la nombroj jes prizorgo pri. Kaj kiam mi diris antaŭe ke komputilo povas nur rigardi unu Adreso samtempe, tio estas speco de kio. 

Ne malsimile al rekordo ludanto kaj legado kapo nur povante rigardi certa sulko en fizika malnova lernejo rekordo samtempe, simile povas komputilo danke lia CPU kaj lia Intel instrukciaro, inter kies instrukcioj legas de memoro aŭ savi al memory-- a komputilo povas nur rigardi ĉe unu loko je time-- kelkfoje kombino de ili, sed vere nur unu loko samtempe. Do kiam ni faris tiuj diversaj algoritmoj, Mi ne nur skribis en vacuum-- kvar, unu, tri, du. Tiuj nombroj reale aparteni ie fizika en memoro. Do estas eta transistoroj aŭ ian de elektroniko sub la kapuĉo stokante tiujn valorojn. 

Kaj entute, kiom da bitoj estas implikita nun, nur por esti klara? Do tiu estas kvar bajtoj, aŭ nun ĝi estas 32 bitoj entute. Do estas fakte 32 nuloj kaj tiuj formas tiujn kvar aferojn. Ekzistas eĉ pli tie, sed denove ni ne zorgas pri tio. 

Do nun ni demandas alia demandon uzanta memoro, ĉar fine de la tago estas en varianco. Negrave kion ni povus fari kun la komputilo, fine de la tago la aparataro estas ankoraŭ la sama sub la kapuĉo. Kiel mi stoki vorto en tie? Nu, vorto en komputilo kiel "Hey!" estus stokitaj samkiel ĉi. Kaj se vi volas pli longa vorto, vi povas simple anstataŭigi tion kaj diri ion kiel "saluton" kaj provizoj, kiujn tie. 

Kaj tiel ankaŭ ĉi tiu contiguousness fakte avantaĝo, ĉar komputilo povas nur legi de dekstre maldekstren. Sed jen demando. En la kunteksto de tiu vorto, h-kaj-l-l-o, ekkrion punkto, kiel povus la komputilo scias kie vorto komencas kaj kie la vorto finiĝas? En la kunteksto de nombroj, kiel faras la komputilo scias kiom longe la sekvencon de nombroj estas aŭ kie komencas? Nu, tio rezultas fjordon kaj ni ne iru tro multe en tiu nivelo de detail-- komputiloj movi aĵojn ĉirkaŭe en memoro laŭvorte tra tiuj adresoj. Tiel en komputilo, se vi estas skribi kodon por stoki aferojn kiel vortoj, kion vi vere faras estas tajpanta esprimoj kiuj memoras kie en la komputilo la memoro tiuj vortoj estas. Do lasu min fari tre, tre simpla ekzemplo. 

Mi tuj iros antaŭen kaj malfermu simpla teksto programo, kaj mi tuj kreos dosiero nomata hello.c. Plej el tiu informo ni ne eniros en granda detalo, sed mi tuj skribos programo en tiu sama lingvo, C. Jen nun pli timiganta, Mi argumentas, ke Scratch, sed estas tre simila en spirito. Fakte, tiuj buklaj braces-- vi povas ia elpensi kion mi ĵus faris, kiel tiu. 

Ni faru tion, fakte. Kiam verda flago clicked, fari la sekvan. Mi volas presi "saluton." Do tiu estas nun _pseudocode_. Mi ia neklara la linioj. En C, tiu lingvo mi parolas pri tiu linio presita saluton fakte fariĝas "printf" kun iuj krampoj kaj semi-dupunkto. 

Sed ĝi estas la ĝusta sama ideo. Kaj tiu tre uzantamika "Kiam verda flago klakis" iĝas la multe pli arcano "int ĉefa malplenon." Kaj tio vere havas nenian surĵeto, do mi simple tuj ignori tion. Sed la krispa krampoj estas kiel la kurba puzlo pecoj kiel ĉi. 

Do vi povas ia diveni. Eĉ se vi neniam planita antaŭe, kion tiu programo probable faros? Probable presas saluton kun krio punkto. 

Do ni provu tion. Mi tuj savos. Kaj tio estas, denove, tre malnova lernejo medio. Mi ne povas klaki, mi ne povas treni. Mi devas tajpi komandojn. Do mi volas kuri mia programo, do Mi povus fari tion, kiel hello.c. Jen la dosieron mi kuris. Sed atendu, mi mankas paŝo. Kion ni diras estas necesa paŝi por lingvo kiel C? Mi ĵus skribis fonto kodo, sed kion mi bezonas? Yeah, Mi bezonas tradukilon. Tiel sur mia Mac ĉi tie, mi havas programo nomita GCC, GNU C kompililo, kiu min permesas fari this-- victurno mia fontkodon en, ni nomas ĝin, maŝino kodo. 

Kaj mi povas vidi ke, denove, kiel sekvas, tiuj estas la nuloj kaj mi ĵus kreita de mia fontkodon, ĉiuj nuloj kaj aĵoj. Kaj se mi volas kuri mia program-- okazas esti nomata a.out por historia reasons-- "saluton." Mi povas kuri ĝin denove. Saluton, saluton, saluton. Kaj ŝajnas esti laborante. 

Sed tio signifas ie en mia komputilo la memoro estas la vortoj h-kaj-l-l-o, ekkrion punkto. Kaj ĝi rezultas, kiel flanken, kion komputilo volus tipe fari por ke ĝi scias kie aĵoj komencas kaj end-- estas tuj metos specialan simbolon tie. Kaj la konvencio estas meti la nombro nulo je la fino de vorto por ke vi sciu kie fakte finas, por ke vi ne malhelpu presi el pli kaj pli karakteroj ol vi efektive intencas. 

Sed la takeaway tie, eĉ kvankam tiu estas sufiĉe arcane, estas ke ĝi estas finfine relative simpla. Vi ricevis ian bendo, malplenan spaco sur kiu vi povas skribi leterojn. Vi simple devas havi speciala simbolo, kiel arbitre la nombro nulo, meti je la fino de viajn vortojn tiel ke la komputilo scias, ho, mi devas halti impreso post Mi vidas la ekkrio punkto. Ĉar la sekva afero tie Estas ASCII valoro de nulo, aŭ la nula karaktero iu nomus ĝin. Sed estas ia problemo tie, kaj ni restarigu reen al nombroj momente. Supozi ke mi faras, fakte, havas tabelo de nombroj, kaj supozu ke la programo mi skribas estas kiel grado libro por instruisto kaj instruistojn klasĉambro. Kaj ĉi programo ebligas al li aŭ ŝi tajpi en siaj studentaj partituroj sur kvizojn. Kaj supozu ke la studento ricevas 100 en lia unua kvizo, eble kiel 80 sur la sekvanta unu, tiam 75, tiam 90 sur la kvara kvizo. 

Do je ĉi tiu punkto en la rakonto, la tabelo estas de amplekso kvar. Ekzistas absolute pli memoro en la komputilo, sed la tabelo, por tiel diri, Estas de grandeco kvar. Supozu nun ke la instruisto volas atribui kvina kvizo al la klaso. Nu, unu el la aĵoj li aŭ ŝi tuj devas fari nun stoki kroman valoron tie. Sed se la tabelo la instruisto havas kreitaj en tiu programo estas de grandeco por, unu el la problemo kun tabelo estas ke Vi ne povas simple observu aldonante al memoro. Ĉar se alia parto de la programo havas la vorton "hey" Dekstre? 

Alivorte, mian memoron povas esti uzata por io en programo. Kaj se anticipe mi tajpita en, hej, Mi volas enigi kvar kvizo partituroj, ili povus iri tien kaj tien. Kaj se vi subite ŝanĝas vian menson poste kaj diru mi volas kvinan kvizo partituro, vi ne povas simple metis ĝin kie ajn vi volas, ĉar se ĉi memoro estas uzata ion else-- alian programon aŭ alian karakterizaĵon de la programo ke vi uzas? Do vi devas pensi anticipe kiom vi volas konservi viajn datumojn, ĉar nun vi pentris vin en cifereca angulo. 

Do instruisto povus anstataŭe diru kiam skribanta programon stoki siajn gradoj, vi scias kion? Mi intencas peti, kiam skribanta mian programon, ke mi volas nulo, unu, du, tri, kvar, kvin, ses, ok gradoj entute. Do unu, du, tri, kvar, kvin, ses, sep, ok. La instruisto povas nur tro asigni memoro verkante sian programon kaj diri, vi scias kion? Mi neniam tuj asigni pli ol ok kvizojn en sesmonato. Tio estas nur freneza. Mi neniam rezervu tion. Por ke tiel li aŭ ŝi havas la fleksebleco vendejo studento partituroj, kiel 75, 90, kaj eble unu ekstra kie la studento akiris kroman krediton, 105. 

Sed se la instruisto neniam uzas tiujn tri spacoj, ekzistas intuicia takeaway tie. Li aŭ ŝi estas nur malŝparanta spaco. Do alivorte, ne estas tio komuna tradeoff en programado kie vi povas aŭ asigni ĝuste tiel memoro kiel vi volas, la supra parto de kiu estas ke vi estas súper efficient-- vi ne malŝparema ĉe all-- sed la malavantaĝo de kiu Estas kio se vi ŝanĝas vian menson kiam uzante la programo ke vi volas konservi pli datumoj ol vi originale celis. 

Do eble la solvo estas, ĉar, skribi viajn programojn en tia vojo ke ili uzas pli da memoro ol ili vere bezonas. Tiel vi ne tuj kolizii tiu problemo, sed vi estis malŝparema. Kaj la pli memoro via programo uzas, kiel ni diskutis hieraŭ, la malpli memoro kiu estas disponeblaj por aliaj programoj, ju pli baldaŭ via komputilo povus malrapidigi malsupren pro virtuala memoro. Kaj tiel la ideala solvo povus esti kio? 

Sub-atribuo ŝajnas malbona. Super-atribuo ŝajnas malbona. Do kio povus esti pli bona solvo? Reallocating. Esti pli dinamika. Ne perfortu vin al elekti priori, komence, kion vi volas. Kaj certe ne tro atribui, ke vi estu malŝparema. 

Kaj tiel atingi tiun celon, ni bezonas ĵeti ĉi datumstrukturo, tiel diri, sin. Kaj tiel kion programisto tipe uzas Estas io nomata ne tabelo sed ligillisto. Alivorte, li aŭ ŝi volas komenci pensi pri ilia memoro kiel esti speco de formo ke ili povas desegni en la sekvanta maniero. Se mi volas konservi unu numeron en oni program-- do estas septembro, Mi donis mian studentoj kvizon; mi volas stoki la studentaj unua kvizo kaj ili ricevis 100 sur it-- mi iras por peti mian komputilon, tra la programo mi havas skribita, unu eron de memoro. Kaj mi tuj stoki la numero 100 en ĝi, kaj tio estas ĝi. 

Tiam kelkajn semajnojn poste kiam mi akiras miajn dua kvizo, kaj ĝi estas tempo por tajpi en tiu 90%, mi iras demandi la komputilo, hej, Komputilo, mi havas alian eron de memoro? Ĝi tuj donu al mi tiun malplena eron de memoro. Mi tuj metis en la numero 90, sed en mian programon iel aŭ alia lando kaj ni ne zorgu pri la sintakso por this-- mi bezonas iel ĉenas tion kune. Kaj mi ĉenas ilin kune kun kio aspektas kiel sago tie. 

La tria kvizo venintan, Mi tuj diru, hej, Komputilo, donu al mi alian eron de memoro. Kaj mi tuj metis malsupren kio ajn ĝi estis, kiel 75, kaj mi havas ĉeni tiun kune nun iel. Kvara kvizo venas kune, kaj eble jen al la fino de la semestro. Kaj de tiu punkto mia programo povus esti uzante memoro ĉie, ĉie fizike. Kaj tiel nur por piedbatoj, mi estas tuj tiri tiun antaŭen quiz-- Mi forgesas, kio gxi; mi pensas eble 80 aŭ something-- vojo ĉi tien. 

Sed tio estas bone, ĉar bilde Mi tuj tiri tiun linion. Alivorte, en realo, en via komputilo aparataro, la unua partituro povus finas tie ĉar ĝi estas ĝuste en la komenco de la semestro. La venonta unu povus fini tie ĉar iom da tempo pasis kaj la programo subtenas kurante. La sekva poentaro, kiu estis 75, povus esti ĉi tie. Kaj la lasta partituro povus esti 80, kiu estas tie. 

Do fakte, fizike, tiu povus esti kion via komputilo la memoro aspektas. Sed tio ne estas utila mensa paradigmo por komputila programisto. Kial vi zorgas kie la heck viajn datumojn estas fini? Vi nur volas konservi datumoj. 

Tiu estas speco de kiel nia diskuto fruaj tiri la kubo. Kial vi zorgas kia la angulo estas de la kubo kaj kiel vi devas turni al desegni ĝin? Vi nur volas kubo. Simile tie, vi Nur volas lernojaro libron. Vi nur volas pensi tiu kiel listo de nombroj. Kiu zorgas kiom ĝi estas implementado en aparataro? 

Tiel la abstracción nun estas ĉi tiu bildo ĉi tie. Tio estas ligillisto, kiel programisto nomus ĝin, mezuro vi havas listo, evidente de nombroj. Sed ĝi estas ligitaj bilde tra tiuj sagoj, kaj ĉiuj tiuj sagoj are-- sub la kapuĉo, se vi estas scivola, memoras ke nia fizika aparataro havas adresoj nulo, unu, du, tri, kvar. Ĉiuj tiuj sagoj estas estas kiel mapo aŭ direktoj, kie se 90 is-- nun Mi alvenis al havi. 

Nulo, unu, du, tri, kvar, kvin, ses, sep. Ĝi aspektas kiel la 90 estas ĉe memoro Adreso numero sep. Ĉiuj tiuj sagoj estas estas kiel malgranda peceto de papero kiu estas donante direktoj al la programo kiu diras sekvi tiun mapo atingi lokon sep. Kaj tie vi trovos la studento dua kvizo partituro. Dume, la 75-- se mi daŭrigos ĉi, tio estas sep, ok, naŭ, 10, 11, 12, 13, 14, 15. 

Tiu alia sago ĵus reprezentas mapon por memoro loko 15. Sed denove, la programisto ĝenerale faras Ne gravas pri ĉi tiu nivelo de detalo. Kaj en plej ĉiu programado lingvo hodiaŭ, la programisto ne eĉ scias kie en memoro tiuj nombroj reale estas. Ĉiuj li aŭ ŝi devas zorgi pri estas ke ili estas iel kunligitaj en datumstrukturo kiel ĉi. 

Sed rezultas ne akiri tro teknika. Sed nur ĉar ni povas eble permesi havi tiun diskuton ĉi tie, supozu ke ni reviziti tiu temo ĉi tie de tabelo. Ni vidu se ni bedaŭras iras tien. Tio estas 100, 90, 75, kaj 80. 

Lasu min mallonge klarigu aserto. Jen tabelo, kaj denove, la elstaraĵo karakteriza de tabelo Estas ke ĉiuj viaj datumoj estas al reen malantaŭeniri en memory-- laŭvorte unu bajto aŭ eble kvar bajtoj, iu fiksita nombro de bajtoj for. En ligillisto, kiun ni povus tiri tiel, sub la kapuĉo, kiu scias kie tiu materialo estas? Ĝi eĉ ne devas flui kiel tiu. Iuj de la datumoj povus esti reen al la maldekstra supre. Vi eĉ ne scias. 

Kaj tiel kun tabelo, vi havas trajto konata kiel hazarda aliro. Kaj kion hazarda aliro rimedoj estas ke la komputilo povas salti senprokraste al ajna loko en tabelo. Kial? Ĉar la komputilo scias ke la unua loko estas nulo, unu, du, tri. 

Do se vi volas iri de tiu elemento al la sekva elemento, vi laŭvorte, en la komputilo menso, nur aldoni unu. Se vi volas iri al la tria ero, nur aldoni one-- sekva elemento, ĝuste aldoni unu. Tamen, en tiu versio de la rakonto, supozu la komputilo estas nun rigardanta ĉe aŭ pritraktas la numeron 100. Kiel vi akiras la sekva grado en la lernojaro libron? 

Vi devi preni sep ŝtupoj, kiuj estas arbitra. Akiri al la sekvanta unu, Vi devi prenu alian ok ŝtupoj por atingi 15. Alivorte, ĝi ne estas konstanta interspaco inter la numerojn, kaj tiel ĝi nur prenas la komputilo pli tempo estas la punkto. La komputilo devas serĉi tra memoro por trovi kion vi estas serĉanta. 

Do dum tabelo emas esti rapida datumoj structure-- ĉar vi povas laŭvorte nur fari simplan aritmetikan kaj akiri kie vi volas aldonante unu, por instance-- ligillisto, vi oferas ke trajto. Vi ne povas simple foriri de unua por dua al tria al kvara. Vi devas sekvi la mapo. Vi devas preni pli paŝoj por atingi tiujn valorojn, kiuj ŝajnus esti aldonanta kosto. Do ni pagas prezon, sed kio la trajto kiu Dan sercxis tie? Kion faras ligillisto ŝajne permesas nin fari, kiu estis la origino de tiun apartan historion? 

Ĝuste. Dinamika grandeco al ĝi. Ni povas aldoni al tiu listo. Ni povas eĉ ŝrumpi la listo, do ke ni nur uzas tiel memoro kiel ni efektive volas do ni neniam super-atribuo. 

Nun nur esti vere nit-elektema, Tie estas kaŝita kosto. Do vi ne donos al mi konvinki vi, ke tio estas konvinka tradeoff. Ekzistas alia kaŝita kosto tie. Profito, esti klara, estas ke ni akiras dinamismo. Se mi volas alia elemento, mi povas nur tiros gxin kaj metis kelkajn tie. Kaj tiam mi povas ligi ĝin kun foto tie, dum ĉi tie, denove, se mi havas pentris mem en angulon, se io alia estas jam uzanta la memoro tie, mi estas el sorton. Mi pentris mem en angulon. 

Sed kio estas la kaŝita kostis en tiu bildo? Ĝi estas ne nur la kvanto de tempo ke ĝi prenas iri de ĉi tie al tie, kiu estas sep ŝtupoj, ĉar ok ŝtupoj, kiuj estas pli ol unu. Kio alia kaŝita kosto? Ne nur la tempo. Aldona informo necesa por atingi tiun bildon. 

Yeah, ke mapo, tiuj malgrandaj pecetoj de papero, kiel mi gardas priskribante ilin kiel. Tiuj arrows-- tiuj ne estas liberaj. A computer-- vi scias kion komputilo havas. Ĝi havas nuloj kaj aĵoj. Se vi volas reprezenti sago aŭ mapi aŭ nombro, vi bezonas iun memoron. Do la aliaj prezo pagi ligillisto, komuna komputiko rimedo, estas ankaŭ spaco. 

Kaj ja tial, tiel ofte, inter la tradeoffs en dizajnado programado sistemoj estas tempo kaj space-- Estas du de viaj ingrediencoj, du de via plej multekostajn ingrediencojn. Tio kostas min pli tempo ĉar mi devos sekvi tiun mapon, sed ĝi ankaŭ kostas min pli spaco ĉar mi devas gardi ĉi Mapo ĉirkaŭe. Do la espero, kiel ni ia diskutis pri hieraŭ kaj hodiaŭ, estas ke la profitoj estos superpezas la kostojn. 

Sed estas neniu evidenta solvo tie. Eble estas better-- a la rapida kaj malpura, kiel Kareem proponita earlier-- ĵeti memoro ĉe la problemon. Nur aĉeti pli memoro, opinias malpli forte pri solvi la problemon, kaj solvi ĝin en facila maniero. Kaj ja pli frue, kiam ni parolis pri tradeoffs, ĝi ne estis spaco en la komputilo kaj tempo. Estis programisto tempo, kiun Estas ankoraŭ alia rimedo. 

Tiom pli, ĝi estas tio ekvilibriganta ago provas decidi kiu el tiuj aferoj ĉu vi pretas elspezi? Kiu estas la malplej multekosta? Kiu rendimenta bonajn rezultojn? Yeah? 

Fakte. En tiu kazo, se vi estas reprezentantaj nombrojn en la maps-- tiuj estas nomitaj en multaj lingvoj "Punteros" aŭ "adresoj" - ĝi estas duobla la spaco. Ke ne bezonas esti tiel malbona kiel duobla se nun ni nur stoki nombroj. Supozu ke ni stokante paciento rekordojn en hospital-- tiel Pierson nomoj, telefonnumerojn, socia sekureco nombroj, kuracisto historio. Tiu skatolo povu multe, multe pli granda, en kies kazo eta montrilo, la adreso de la sekva element-- ĝi ne estas granda interkonsento. Ĝi estas tia franĝo kostis ne gravas. Sed en ĉi tiu kazo, jes, ĝi estas duobligo. Bona demando. 

Ni parolu pri tempo iom pli konkrete. Kio estas la rula tempo esplorrigardi tiu listo? Supozu mi volis serĉi tra ĉiuj studentoj 'kvalifikojn, kaj ekzistas n gradoj en ĉi datumstrukturo. Ankaŭ tie ni povas deprunti la vortprovizo de pli fruaj. Tio estas lineara datumstrukturo. 

Granda a de n estas kio postulita akiri al la fino de tiu datumstrukturo, whereas-- kaj ni ne vidis ĉi before-- tabelo donas kio nomiĝas konstanta tempo, kio signifas unu paŝo aŭ du paŝoj aŭ 10 steps-- Ne gravas. Ĝi estas fiksa nombro. Ĝi havas nenion komunan kun la grandeco de la tabelo. Kaj la kialo por tio, denove, estas hazarda aliro. La komputilo povas simple tuj salti al alia loko, ĉar ili estas tutegale distanco de ĉiu alia. Ne ekzistas pensado implikitaj. Bone. Do se mi povos, mi provos pentri du finaj bildoj. Tre komuna nomata hash tablo. Tiel motivi ĉi diskuto, mi pensas pri kiel fari tion. 

Do kion pri cxi tiu? Supozu ke la problemo ni volas solvi nun estas implementando en dictionary-- tiel tutan faskon da anglaj vortoj aŭ kio ajn. Kaj la celo estas povi respondi demandoj de la formo estas tiu vorto? Do vi volas apliki sorĉas Kontrolilo, ĵus kiel fizika vortaro ke vi povas rigardi aĵojn en. Eble mi devis fari tion kun tabelo. Mi povus fari tion. 

Kaj supozu la vortoj estas pomo kaj banano kaj melono. Kaj mi ne povas pensi pri fruktoj kiuj komencas kun d, tial ni estas nur havos tri fruktoj. Do tiu estas tabelo kaj ni stokante ĉiuj vortoj en tiu vortaro kiel tabelo. La demando do estas kiel alie povus stoki tiun informon? 

Nu, mi specon de trompado tie, ĉar ĉiu el tiuj literoj en la vorto estas vere individuo bajto. Do se mi vere volis esti nit-elektema, mi devus vere esti dividanta ĉi supre en multa malgrandaj pecoj de memoro, kaj ni povus fari ĝuste tion. Sed ni tuj kolizii la saman problemon antaŭe. Kio se, kiel Merriam Webster aŭ Oxford faras ĉiun year-- ili aldonu vortojn al la dictionary-- ni ne nepre volas pentri mem en angulon kun tabelo? 

Do anstataŭe, eble pli lerta alproksimiĝo estas meti pomon en lia propra nodo aŭ skatolo, kiel ni dirus, banano, kaj tiam tie ni havas melono. Kaj ni ŝnuro tion kune. Do tiu estas la tabelo, kaj tio estas la ligillisto. Se vi ne tute povas vidi, ĝi nur diras "tabelo", kaj tiu diras "listo." 

Do ni havas la samajn ĝusta temoj kiel antaŭe, per kiu ni jam havas dinamismo en nia ligillisto. Sed ni havas sufiĉe malrapidan vortaro. Supozu mi volas serĉi ion. Ĝi povus kapti min granda a de n paŝojn, ĉar la vorto eble esti tute fine de la lerta, kiel melono. Kaj ĝi rezultas ke en programado, speco de la sankta grail de datumoj strukturoj, estas io kiu donas al vi konstantan tempo kiel tabelo sed kiu ankoraŭ donas dinamismo. 

Do ni povas havi la plej bonan de ambaŭ mondoj? Kaj ja ekzistas io nomata hash tablo kiu permesas fari ĝuste ke, kvankam proksimume. Al hash tablo estas amatoro datumstrukturo ke ni povas pensi kiel la kombino de tabelo kaj mi tuj desegni ĝin kiel this-- kaj ligitaj listoj ke mi desegni kiel ĉi tie. 

Kaj la vojon tion verkoj estas kiel sekvas. Se tiu now-- hash table-- Estas mia tria datumstrukturo, kaj mi volas konservi vortoj en tio, mi ne faras volas nur konservi ĉiujn vortoj malantaŭo al malantaŭo al malantaŭo al dorso. Mi volas utiligi iun peco de informo pri la vortoj kiuj lasos mi ricevas ĝin kie ĝi estas pli rapida. 

Tiel donitaj la vortoj pomon kaj banano kaj melono, Mi intence elektis tiujn vortojn. Kial? Kio estas ia fundamente malsama pri la tri? Kio estas evidenta? Ili komencas kun malsamaj literoj. 

Do vi scias kion? Anstataŭ meti ĉiujn miajn vortojn en la sama sitelo, por tiel diri, kiel en unu granda listo, kial ne Mi almenaŭ provu optimumiga Kaj purigus miajn listojn 1/26 kiel longe. A konvinkaj optimumigo povus esti kial ne I-- kiam enmeto vorton en ĉi datumstrukturo, en la komputilo la memoro, kial ne mi metis ĉiujn a vortojn tie, ĉiuj b vortojn tie, kaj ĉiuj 'c' vortoj tie? Do tiu finas metante pomon tie, banano tie, melono tie, kaj tiel plu. 

Kaj se mi havas kroman vorto like-- kio estas alia? Pomo, banano, piro. Iu pensas de frukto kiu komencas kun a, b, aŭ c? Blueberry-- perfekta. Kiu tuj finos tie. Kaj tiel ni ŝajnas havi marĝene pli bona solvo, ĉar nun se mi volas serĉi pomon, mi first-- mi ne nur dive en mian datumstrukturo. Mi ne plonĝi en mia komputilo memoro. Mi unue rigardu la unuan literon. 

Kaj tio estas kion komputilo sciencisto dirus. Vi hash en vian datumstrukturo. Vi prenas vian enigon, kiu en tiu kazo estas vorto kiel pomo. Vi analizi ĝin, rigardante la unua letero en tiu kazo, tiel hashing ĝin. Regionoj estas ĝenerala termino por kiu vi prenas ion kiel enigo kaj vi produkti iuj eligo. Kaj la eligo en tiu kazo estas la loko vi volas serĉi, la unua loko, dua loko, tria. Do la enigo estas pomo, la eligo estas unua. La enigo estas banano, la eligo devus esti dua. La enigo estas melono, la eligo estu tria. La enigo estas Blueberry, la eligo devus denove esti dua. Kaj tio helpas vin preni ŝparvojoj tra via memoro por akiri al vortoj aŭ datumojn pli efike. 

Nun ĉi tranĉas malsupren nia tempo potenciale per kiom unu el 26, ĉar se vi supozas ke vi havi tiom da "al" vortoj kiel "z" vortoj kiel "q" vortoj, kiujn ne vere realistic-- vi tuj havos esviaje trans iuj literoj de la aboco sed tio estus dumtajpa alproksimiĝo tio permesas vi atingos vortoj multe pli rapide. Kaj fakte, kompleksa programo, la Googles de la mondo, la Facebooks de la world-- ili uzus hash tablo por multaj malsamaj celoj. Sed ili ne estus tiel naiva kiel nur rigardu la unuan literon en pomo aŭ banano aŭ piro aŭ melono, ĉar kiel vi povas vidi ĉi tiujn listoj povus ankoraŭ atingi longa. 

Kaj tiel ĉi povus ankoraŭ esti ia de linear-- do ia malrapida, kiel kun la granda a de n ke ni diskutis antaŭe. Do kion realan bonon hash tablo volo do-- havos multe pli granda tabelo. Kaj ĝi uzos multe pli malnaiva kradanta funkcio, tiel ke ĝi ne nur rigardi la "a." Eble rigardas "al-p-p-l-e" kaj iel konvertas tiujn kvin literoj en la loko kie pomo estas konservataj. Ni nur naive uzante la literon 'a' sola, ĉar ĝi estas bela kaj simpla. 

Sed hash tablo, en Fine, vi povas pensi de kiel kombinaĵo de tabelo, ĉiu el kiuj havas ligillisto ke ideale devus esti kiel mallonga kiel ebla. Kaj tio ne estas evidenta solvo. Fakte, granda parto de la ĝustigas fajna okazanta sub la kapuĉo kiam efektivigado tiuj specoj de kompleksaj datumstrukturoj Estas kio estas la dekstra longo de la tabelo? Kio estas la dekstra hash funkcio? Kiel vi stoki aferojn en memoro? 

Sed konscias kiom rapide ĉi tia diskuto eskaladis, ĉu ĝis nun ke ĝi estas speco de super onies kapo ĉe tiu punkto, kiu Estas bone. Sed ni komencis, revokon, kun vere io malalta nivelo kaj elektronika. Kaj tiel ĉi denove estas ĉi temo de abstraktado, kie iam vi komencas preni por permesite, OK, Mi havas it-- ekzistas fizika memoro, OK, havas ĝin, ĉiu fizika loko havas adreson, Okej, mi havas ĝin, mi povas reprezenti tiujn adresojn kiel arrows-- Vi povas tre rapide komencas havi pli altnivela konversaciojn kiuj en la fino ŝajnas esti permesante nin solvi problemojn kiel serĉado kaj ordigado pli efike. Kaj estu certaj, ankaŭ kontraŭ ĉar mi pensas ĉi estas la plej profunda ni iris en iun de tiuj CS temoj proper-- ni havas farita en tago kaj duono ĉe tiu atentigi kion vi eble tipe fari super la kurso de ok semajnoj en semestro. 

Demandojn pri tiuj? Ne? Bone. Nu, kial ni ne paŭzi tie, komenci tagmanĝo kelkajn minutojn frua, rekomenci en nur ĉirkaŭ unu horon? Kaj mi restadi dum iom kun demandoj. Tiam mi tuj devos iri preni kelkajn vokojn se tio estas bone. Mi turnos sur iu muziko intertempe, sed lunĉo devus esti ĉirkaŭ la angulo.