DAVID Malan: Està bé. Hem tornat. Així que en aquest segment de la programació el Vaig pensar que ens agradaria fer és una barreja de coses. Un d'ells, fer una mica d'alguna cosa pràctic, encara que utilitzant una més lúdica ambient- programació un que és demostratiu de exactament el tipus d'idees hem estat parlant, però una mica més formal. Dos, un cop d'ull a algunes de les les formes més tècnics que un programador en realitat resoldre problemes com el problema de la recerca que mirem abans i També una manera més fonamental interessant problema de la classificació. 

Nosaltres assumim des del principi que aquest llibre de telèfon es va solucionar, però que per si sola és en realitat una espècie de problema difícil amb moltes formes diferents per resoldre-ho. Així que utilitzarem aquests com una classe de problemes representant de les coses que podria resoldre en general. I llavors parlarem sobre amb cert detall el es diuen les dades structures-- maneres més elegants com llistes enllaçades i taules hash i arbres que un programador en realitat usar i generalment utilitzar en una pissarra per pintar una imatge del que ell o ella preveu per a la implementació alguna peça de programari. 

Així que farem les mans a la primera part. Pel que només embrutar-se les mans amb una scratch.mit.edu entorn trucada. Aquesta és una eina que utilitzem a la nostra classe de grau. Tot i que està dissenyat per a majors de 12 anys, el fem servir cap amunt part d'això una mica ja que és un agradable, divertit manera gràfica d'aprenentatge una mica d'alguna cosa sobre la programació. Així que el cap a aquesta URL, on Hauria de veure una pàgina com aquest, i seguir endavant i feu clic Unir-se a les ratllades a la part superior dreta i triar un nom d'usuari i una contrasenya i, finalment, s'aconsegueix 1 scratch.mit.edu account--. Vaig pensar que faria ús d'això com una oportunitat de primera per mostrar això. Una pregunta va sorgir durant el descans sobre el que en realitat sembla codi. I estàvem parlant durant el descans sobre C, en particular: en particular, una nivell més baix en una llengua més antiga. I acabo de fer una ràpida Google buscar per trobar el codi C per a la recerca binària, l'algoritme que ens utilitzat per buscar aquest llibre de telèfon anterior. Aquest exemple en particular, per descomptat, no busca una guia telefònica. Simplement busca en un munt de números a la memòria de l'ordinador. Però per obtenir només una representació visual sentit del que és una programació real el llenguatge s'assembla, es veu una mica d'alguna cosa com això. Per tant es tracta de més de 20, 30 o més línies de codi, però la conversa que estaven tenint durant les vacances va ser sobre com aquest fet obté transformat en zeros i uns i si un no pot revertir aquest processar i anar de zeros i uns tornar al codi. 

Desafortunadament, el procés de és tan transformadora que és molt més fàcil dir que fer-ho. Vaig seguir endavant i en realitat va resultar aquest programa, recerca binària, en zeros i uns a manera d'una El programa anomenat compilador que jo passa que té aquí a la dreta en el meu Mac. I si ens fixem en la pantalla aquí, centrant-se específicament sobre aquestes mitjanes sis columnes només, veurà només zeros i uns. I aquests són els zeros i uns que compondre exactament aquest programa de cerca. 

I així, cada tros de cinc bits, cada byte de zeros i uns aquí, representar alguna instrucció normalment dins d'un ordinador. I de fet, si vostè ha sentit el lema publicitari "Intel inside" - que, per descomptat, simplement vol dir que té una CPU Intel o el cervell a l'interior de l'equip. I el que significa ser un CPU és que té un conjunt d'instruccions, per dir-ho així. 

Cada CPU en el món, molts ells fabricats per Intel en aquests dies, comprèn un nombre finit nombre d'instruccions. I aquestes instruccions són tan baix nivell com afegir aquests dos nombres, multiplicar aquests dos nombres, moure aquesta peça d'informació d'aquí d'aquí en memòria, guardar aquest la informació d'aquí fins aquí a la memòria, i així forth-- molt, molt De baix nivell, gairebé detalls electrònics. Però amb els matemàtica operacions acoblada amb el que hem comentat anteriorment, la representació de dades com zeros i uns, pot tot el que s'acumulen que un ordinador pot fer avui, si és textual, gràfica, musical, o d'una altra manera. 

Així que això és molt fàcil d'aconseguir perdut entre la mala herba de forma ràpida. I hi ha una gran quantitat de reptes sintàctics pel que si es fa el més simple, més estúpida d'errors tipogràfics cap dels programes funcionarà en absolut. I així, en lloc d'utilitzar una llenguatge com C aquest matí, Vaig pensar que seria més divertit per fer realitat alguna cosa més visual, que mentre dissenyat per a nens és en realitat una manifestació perfecta d'una programació real language-- només passa a utilitzar imatges en lloc de text per a representar aquestes idees. 

Així que una vegada que de fet té una compte en scratch.mit.edu, feu clic al botó Crear a la part superior esquerra de la pàgina. I cal veure un entorn com el que estic a punt de veure en la meva pantalla aquí. I anem a passar només una mica poc de temps jugant aquí. Vegem si no tots podem resoldre alguns problemes junts de la manera següent. 

Així que el que veurà dins d'aquest ambient- i de fet acaba de deixar M'aturo. Hi ha algú que no és aquí? Aquí no? D'ACORD. Així que permetin-me assenyalar alguns característiques d'aquest entorn. 

Així que a la part superior esquerra de la pantalla, ens L'etapa de tenir ratllades, per dir-ho. Scratch és no només el nom d'aquest llenguatge de programació; que és també el nom del gat que es veus per defecte no en taronja. Ell està en una etapa, per la qual de la mateixa manera que vaig descriure la tortuga anteriorment com a membres d'un rectangular entorn de la targeta blanca. El món d'aquest gat està confinat en la seva totalitat a aquest rectangle sobre de la tapa allà. 

Mentrestant, a la dreta costat aquí, és només una àrea de seqüència, un pissarra en blanc si es vol. Aquí és on anem a escriure els nostres programes en un moment. I els blocs de construcció que hauran utilitzar per escriure aquest program-- el trencaclosques peces, si vostè està voluntat-- els que estan aquí al mig, i estan categoritzats per funcionalitat. Així, per exemple, seguiré endavant i demostrar almenys un d'aquests. Vaig a seguir endavant i feu clic la Categoria de control fins a la part superior. 

Així que aquestes són les categories sobre de la tapa. Vaig a clic a la categoria de control. Més aviat, vaig a feu clic als Esdeveniments categoria, el primer de tots en la superior. I si desitja seguir endavant, fins i tot en fer això, vostè és molt benvingut a. Vaig a fer clic i arrossegar aquest primer, "quan es fa clic a bandera verda." I després vaig a deixar que només més o menys en la part superior de les meves pissarres en blanc. 

I el que és bo de les ratllades és que aquesta peça del trencaclosques, quan enclavada amb un altre trencaclosques peces, es van a fer, literalment, el que aquestes peces del trencaclosques diuen que fer. Així, per exemple, Scratch és correcta ara al centre del seu món. Vaig a seguir endavant i triar Ara, anem a dir, la categoria de moviment, Si desitja fer ho same-- categoria de moviment. I ara noto que tinc en el seu conjunt munt de peces d'un trencaclosques aquí que, de nou, una mena de fer el que diuen. I vaig a seguir endavant i arrossegar i deixar caure el bloc de moviment per aquí. 

I noti que tan aviat com s'obté prop de la part inferior de la "bandera verda fet clic a "botó, l'avís com apareix una línia blanca, com si fos gairebé magnètica, que vol anar-hi. Simplement deixa anar, i s'encaixarà junts i les formes coincidiran. potser i ara gairebé es pot endevinar cap a on anem amb això. 

Si ens fixem en l'etapa de Scratch per aquí i mirar a la part superior de la mateixa, veurà una llum vermella, una senyal de stop, i una bandera verda. I seguiré endavant i veure les meves screen-- per un moment, si pogués. Vaig a fer clic al bandera verda en aquest moment, i es va traslladar el que sembla ser 10 passos o 10 píxels, 10 punts, a la pantalla. 

I el que no és tan emocionant, però permetin-me proposar sense ni tan sols l'ensenyament d'això, només utilitzant l'amo del seu propi let intuition-- Em proposo a esbrinar com fer peu dret esgarrapades fora de l'escenari. Faci que donar pas a la dreta la pantalla, tot el camí a la dreta. Deixeu-me donar-li un moment o pel que lluitar amb això. És possible que vulgueu fer una ullada en altres categories de blocs. Tot bé. Així que per recapitular, quan tenim la bandera verda clic aquí i moure 10 passos és la única instrucció, cada vegada que feu clic a la bandera verda, el que està passant? Bé, això és córrer el meu programa. Pel que podia fer això potser 10 vegades de forma manual, però això se sent una mica hackish poc, per així dir-ho, pel que no estic realment la solució del problema. Només intent una vegada i una una i altra vegada i una altra fins que tipus d'accident aconseguir la directiva que es va proposar aconseguir abans. 

Però sabem per la nostra pseudocodi anterior que hi ha aquesta noció en la programació de bucles, fer alguna cosa una i altra vegada. I així vaig veure que un munt de vostès assolit per la peça de trencaclosques el que? Repetiu fins. Així que podríem fer alguna cosa de la mateixa manera que repetir fins. ¿I què es repeteix fins que exactament? 

D'ACORD. I me n'aniré amb un que és una mica més senzill només per un moment. Déjame seguir endavant i fer això. Recordeu que, ja que pot tenir descobert sota control, hi ha aquest bloc de repetició, la qual cosa no es veu com si fos tan gran. No hi ha molt ambient a entre aquestes dues línies grogues. No obstant això, com alguns de vostès podrien tenir notat, si arrossega i deixar anar, observi com creix per omplir la forma. 

I fins i tot es pot ficar més. Simplement seguirà creixent si s'arrossega i es passa a sobre. I no sé el que és millor aquí, així que anem Em repeteixo almenys cinc vegades, per instància i, a continuació, tornar a l'etapa i feu clic a la bandera verda. I ara es va adonar que no és molt allà. 

Ara alguns de vostès proposen, com Victòria acaba de fer, repetir 10 vegades. I que fa en general portar-lo fins al final, però ¿no hi hauria un més robust de manera arbitrària esbrinar quants moviments per fer? Quin podria ser un bloc millor de repetir 10 vegades? 

Sí, per què no fer alguna cosa per sempre? I ara anem a moure aquest tros del trencaclosques A l'interior hi ha i desfer d'aquest. Ara noti, sense importar on les ratllades obertures, que va fins la vora. I afortunadament el MIT, que fa Scratch, simplement s'assegura que mai desapareix per complet. Sempre es pot agafar la seva cua. 

I de la mateixa manera intuïtiva, ¿Per què segueix en moviment? Què està passant aquí? Ell sembla haver-se aturat, però llavors, si recullo i arrossegament ell segueix volent anar per allà. Perquè és això? En veritat, un ordinador és, literalment, va a fer el que li indica que fer. Així que si vostè li va dir que faci com més aviat El següent per sempre, moure 10 passos, que seguirà i seguir fins que vaig arribar al senyal de stop vermell i aturar el programa complet. 

Així que encara que no ho va fer fer això, com podria fer-ho fer que les ratllades es mouen més ràpid a través de la pantalla? Més passos, oi? Així que en lloc de fer 10 alhora, per què no seguir endavant i canviar-A-- ¿Què li propose-- 50? Així que ara vaig a fer clic al verd bandera, i, de fet, va molt ràpid. 

I això, per descomptat, és només una manifestació de l'animació. Quina és l'animació? És només que mostra l'ésser humà manat sencer d'imatges fixes en realitat, molt, molt ràpid. I així, si només estem dient que es mogui més passos, només estem tenint l'efecte sigui on el canvi és a la pantalla tant més ràpidament per unitat de temps. 

Ara, el següent repte que vaig proposar anava a haver de rebot fora de la vora. I sense saber què trencaclosques la qual existeixen peces, ja que està ben si no s'arriba a la etapa del challenge-- el Què vol fer intuïtivament? Com hauríem de rebot cap enrere i etc., entre l'esquerra i la dreta? 

Sí. Així que necessitem algun tipus de la condició, i semblen tenir condicionals, de manera que parlar, en la categoria de control. Quin d'aquests blocs és el que probablement volem? Sí, potser "si, llavors". Així notar que entre els blocs grocs tenim aquí, no és aquest "si" o aquest "si, en cas contrari" bloc que ens permeten fer una decisió per fer això o per fer això. I fins i tot es pot niar fer diverses coses. O si no has anat aquí encara, seguir endavant amb la categoria de detecció i- veurem si és aquí. 

Llavors, què bloc podria ser útil aquí per detectar si està fora de l'escenari? Sí, adonar-se que alguns d'aquests blocs pot ser parametritzada, per dir-ho. Poden ser una mena de personalitzar-se, no a diferència d'HTML ahir amb atributs, on aquests atributs tipus de personalitzar el comportament d'una variable. De la mateixa manera aquí, puc agafar aquesta commovedora bloc i el canvi i fer la pregunta, estàs tocant el ratolí punter de la mateixa manera que el cursor o està tocant la vora? 

Així que permetin-me anar i fer això. Vaig a allunyar per un moment. Permetin-me aprofitar aquesta peça del trencaclosques aquí, aquesta peça del trencaclosques d'això, i vaig a Jumble cap amunt per un moment. Vaig a moure això, canviar això a tocar la vora, i vaig a fer això de moviment. Així que aquí estan alguns dels ingredients. Crec que tinc tot el que vull. 

Algú vol proposar com es pot connectar aquests potser de dalt a baix per tal de resoldre el problema de tenir Scratch dreta a esquerra a dreta per moure d'esquerra a dreta a esquerra, cadascuna temps només rebotant a la paret? Què vull fer? Què bloc s'ha de connectar a la "Bandera verda quan es fa clic en primer lloc"? 

OK, així que començarem amb el "per sempre". El que va dins de la propera? Algu altre. OK, moure els passos. Tot bé. Llavors què? Amb això, el cas. I noti, tot i que sembla intercalat juntes fermament, només creixerà per omplir. S'acaba d'entrar en on el vull. 

I què és el que va posar entre el si i el llavors? Probablement "si tocar la vora." I avís, de nou, és massa gran per a això, però que creixerà per omplir. I després girar 15 graus? Quants graus? Sí, per la qual cosa 180 girarà amb mi tot el camí al voltant. Així que anem a veure si tinc aquest dret. Permetin-me Allunyar. 

Permetin-me arrossego fins esgarrinxada. Així que és una mica distorsionada ara, però que està bé. Com li puc restablir fàcilment? Jo us vaig a enganyar una mica. Així que estic afegint una altra bloc, per ser clars. Vull que el punt 90 graus a la dreta per defecte, així que només vaig a dir-li de fer-ho mitjançant programació. I aquí anem. Sembla que hem fet. És una mica estrany, perquè ell està caminant a l'inrevés. Anem a trucar a que un error. Això és un error. Un error és un error en un programa, una error lògic que jo, l'ésser humà, vaig fer. Per què es va a l'inrevés? ¿Es cargol MIT dalt o feia jo? 

Sí, vull dir, no és de MIT criticar. Em van donar una peça del trencaclosques diu que al seu torn certa quantitat de graus. I per suggeriment de Victòria, Estic girant 180 graus, que és la intuïció correcta. Però convertir 180 graus literalment significa girar 180 graus, i això no és veritat el que jo vull, pel que sembla. A causa de que almenys està en aquest món de dues dimensions, de manera decisiva és realment va a ell voltejar l'inrevés. 

Probablement vull usar el que el bloc en canvi, en base al que es veu aquí? Com podem fer això? Sí, pel que podríem assenyalar en la direcció oposada. I, de fet, fins i tot això és no serà suficient, perquè només podem codificar que apunta cap a l'esquerra o cap a la dreta. 

Ja saps el que podríem fer? Sembla que tenim una bloc de conveniència aquí. Si faig zoom, consulteu una cosa que ens agrada aquí? Així que sembla que el MIT té una abstracció construïda aquí. Aquest bloc sembla ser equivalent a la qual altres blocs, plural? 

Aquesta a una quadra sembla ser equivalent a tot aquest trio de blocs que tenim aquí. Així que resulta que puc simplificar la meva programa per desfer-se de tot això i només cal posar això aquí. I ara està encara una mica amb errors, i això està bé per ara. Anem a deixar que sigui. Però el meu programa és encara més simple, i això, també, seria representativa d'un objectiu en programming-- és fer idealment com el seu codi simple, el més compacte possible, sense deixar de ser tan llegibles com sigui possible. No vol fer-ho de manera succinta que és difícil d'entendre. 

Però cal notar que he substituït tres blocs amb un, i això és sens dubte una bona cosa. He abstreu la noció de comprovar si estàs a la vora amb un sol bloc. Ara podem tenir diversió amb això, de fet. Això no afegeix tant valor intel·lectual però el valor lúdic. Vaig a seguir endavant i apoderar-se de aquest so aquí. Així que permetin-me anar per davant, i em va deixar aturar el programa per un moment. Vaig a gravar el següent, permetent l'accés al micròfon. 

Aquí anem. Ouch. Anem a intentar-ho de nou. Aquí anem. OK, he gravat el que no devia. Aquí anem. Ouch. Ouch. Tot bé. Ara necessito per desfer-això. Tot bé. 

Així que ara tinc una gravació de només "ouch". Així que ara vaig a anar endavant i cridar a aquest "ai". Vaig a tornar als meus guions, i ara notificació no aquest bloc que es diu jugar "miol" so o reproduir so "ai". Vaig a arrossegar aquest, i on hauria de posar això per l'efecte còmic? Sí, de manera que ara és una espècie de amb errors, perquè ara aquesta block-- notar com aquest "si a la vora, rebot "és una espècie d'auto-contingut. Així que he de arreglar això. Déjame seguir endavant i fer això. Permetin-me desfer-se d'aquest i tornar al nostre original, més deliberat funcionalitat. Pel que "si toca la vora, a continuació," Vull al seu torn, com es va proposar Victòria, 180 graus. I és el que vull per jugar el so "ai" hi ha? 

Sí, observi que està fora aquest bloc groc. Així que això també seria una insecte, però m'he adonat d'això. Així que vaig a arrossegar-la fins aquí, i l'avís que ara està dins de la "si". Pel que el "si" és aquesta classe com de transferència en forma de braç que només va a fer el que hi ha dins d'ella. Així que ara si Allunyar a el risc de annoying-- 

ORDINADOR: Ai, ai, ai. 

DAVID Malan: I només durarà per sempre. Ara només per accelerar les coses aquí, deixa anar per davant i obrir, anem a dir-- m'ho dius a mi anar a alguna del meu propi material de la classe. I m'ho dius a mi obrir fins, diguem, aquest 1 feta per un dels nostres companys d'ensenyament Fa un parell d'anys. Pel que alguns de vostès poden recordar aquest joc d'antany, i de fet és notable. Tot i que hem fet el més simple dels programes en aquest moment, anem a considerar el que aquest que en realitat sembla. Em Hit joc. 

Així que en aquest joc, tenim una granota, i l'ús de la fletxa keys-- presa passos més grans del que remember-- Tinc control sobre aquesta granota. I l'objectiu és aconseguir a través de l'ocupada camí sense caure en els cotxes. I anem a veure-- si vaig fins aquí, haver d'esperar que un registre per desplaçar-se per. Això se sent com un insecte. Aquesta és una espècie d'insecte. Tot bé. Estic en això aquí, allà, i després es manté avançant fins a arribar tot les granotes a les fulles de nenúfar. Ara bé, això pot tenir un aspecte tot el més complex, però tractarem de trencar això baix mentalment i verbalment en els seus blocs de components. Així que és probable que hi hagi un trencaclosques peça que no hem vist encara però això és respondre a les pulsacions de teclat, a les coses em va colpejar en el teclat. 

Així que és probable que hi hagi algun tipus de bloc que diu, que la clau és igual a, a continuació, fer alguna cosa amb Scratch-- potser moure-10 passos d'aquesta manera. Si es prem la tecla cap avall, moure 10 passos d'aquesta manera, o la tecla esquerra, es mouen 10 passos D'aquesta manera, els passos que 10. M'he convertit clarament el gat en una granota. Així que això és just on el vestit, com trucades de Scratch que it-- acaba d'importar una imatge de la granota. 

Però el que més està succeint? Quines altres línies de codi, la resta peces del trencaclosques Blake va fer, els nostres companys de l'ensenyament, utilitzar en aquest programa, pel que es veu? El que està fent tot el move-- el que la programació de la construcció? 

Moviment, per la qual cosa el sure-- moure el bloc, segur. I el que és aquest bloc de moviment A dins, més probable? Sí, algun tipus de bucle, potser una sempre bloquejar, potser una repetició block-- repetir fins que el bloc. I això és el que està fent els registres i les fulles de nenúfar i tota la resta jugada d'aquí cap allà. És només succeint sense fi. 

Per què són alguns dels cotxes mou més ràpid que els altres? El que és diferent sobre aquests programes? Sí, probablement alguns d'ells estan prenent més passos alhora i algunes d'elles un menor nombre de passos alhora. I l'efecte visual és ràpid front lent. 

Què creus que va passar? Quan vaig arribar al meu granota de tot el camí creuar el carrer i el riu en el coixinet de lliri, alguna cosa digne de menció va passar. Què va passar tan aviat com ho vaig fer? Es va aturar. Que la granota es va aturar, i Tinc una segona granota. Llavors, quin ha de ser constructe utilitzat allà, quina funció? 

Sí, per la qual cosa hi ha algun tipus de "Si" condició fins allà, també. I resulta out-- no vam veure això- però hi ha altres blocs en què hi ha es pot dir, si vostè està tocant una altra cosa a la pantalla, si vostè està tocant el full de lliri, "llavors". I llavors és quan ens fer aparèixer la segona granota. Així que tot i que aquest joc és sens dubte molt antiquat, tot i que a primera vista hi ha tantes coses que passen i Blake en-- no assotar això en dos minuts, és probable que l'hi va portar a diversos hores per crear aquest joc basat en la seva memòria o vídeos de la versió d'antany de la mateixa. Però totes aquestes petites coses va a la pantalla en forma aïllada es redueixen a aquests molt simple constructs-- moviments o estats com hem comentat, els bucles i condicions, i això és tot. Hi ha algunes altres característiques més elegants. Alguns d'ells són purament estètica o acústica, com els sons que jo en el amb. Però en la seva major part, es tenen en aquest idioma, Scratch, tot de la fonamental blocs de construcció que es tenir en C, Java, JavaScript, PHP, Ruby, Python, i qualsevol nombre d'altres idiomes. Una pregunta sobre el principi? Tot bé. Així que no anem a bussejar més profundament a l'alçada, encara que de res aquest cap de setmana, especialment si vostè té nens o nebots i altres, per introduir-los a les ratllades. En realitat és un meravellosament lúdic medi ambient, amb, com diuen els seus autors, sostres molt alts. Tot i que vam començar amb mateixos detalls de baix nivell, realment es pot fer una mica amb això, i això és potser una demostració d'exactament això. 

Però ara anem transició a una mica més de problemes sofisticats, si es vol, coneguda com "cerca" i "Classificació", en termes més generals. Hem tingut aquest llibre de telèfon abans els vaig parlar aquí està una altra plantilla només per discussion-- que hem estat capaços de buscar de manera més eficient perquè d'un suposat significatiu. I només perquè quedi clar, el Se suposava que fer quan es busca a través d'aquesta guia de telèfons? Que Mike Smith estava en la guia de telèfons, encara que seria capaç de gestionar l'escenari sense ell allà si només es va aturar prematurament. El llibre és alfabètic. I això és un molt generós descomptat, perquè això significa algú-- Sóc una mena de tallar un cantó, com jo sóc més ràpid perquè algú més va fer un munt de treball dur per a mi. 

Però, i si el telèfon llibre van ser sense ordenar? Potser Verizon va obtenir mandrós, acaba de llançar noms i números de tot el món allà potser en l'ordre en què es signat per al servei telefònic. I quant de temps es em porti trobar algú com Mike Smith? 1.000 telefònic pàgina book-- quants pàgines he de mirar a través de? 

Tots ells. Ets una espècie de fora de sort. Literalment has de mirar cada pàgina si la guia telefònica és només ordenats aleatòriament. Podria ser necessari sort i trobi Mike a la primera pàgina, perquè ell va ser el primer client per ordenar el servei telefònic. Però podria haver estat l'última, també. 

Així ordre aleatori no és bo. Així que suposem que tenim per ordenar la directori telefònic o en dades generals espècie que se'ns ha donat. Com podem fer això? 

Bé, deixa només tracte aquí un exemple senzill. Déjame anar endavant i llançar una uns números al tauler. Suposem que els números que tenim són, diguem, quatre, dos, un-tres. I, Ben, ordenar aquests números per a nosaltres. 

D'acord. Com ho has fet? Tot bé. Així que comença amb els més petits el valor i la més alta, i això és molt bona intuïció. I adonar-se que els éssers humans són en realitat bastant bo en la solució de problemes d'aquesta manera, almenys quan les dades és relativament petit. Tan aviat com vostè comença a tenir centenars de nombres, milers de nombres, milions de números, Ben probablement No podria fer-ho bastant ràpid que, suposant que no eren llacunes en els números. Bastant fàcil d'explicar fins a un milió en cas contrari, només consumeix molt de temps. 

Així que l'algoritme que sona com Ben utilitza ara va ser buscar el nombre més petit. Així que tot i que els éssers humans podem tenir en una gran quantitat d'informació visual, un ordinador és en realitat una mica més limitada. L'equip només pot mirar a un byte a la vegada o potser quatre bytes a la vegada-- en aquests dies potser 8 bytes a la vegada-- però un nombre molt petit de bytes en un moment donat. 

Per tant, atès que realment tenim quatre valors separats aquí-- i que es pugui imaginar Ben com tenir bena als ulls si fos un ordinador, com que ell no pot veure una altra cosa d'un nombre a un temps-- pel que generalment s'assumeix, com en Anglès, llegirem de dreta a esquerra. Així que el primer nombre Ben probablement es veia a era quatre i després molt ràpidament es van adonar que és una bastant gran number-- m'ho dius a mi seguir buscant. 

Hi ha dos. Espera un minut. Dos és menor que quatre. Vaig a recordar. Dos és ara el més petit. Ara un-- que és fins i tot millor. Això és encara més petit. Vaig a oblidar-se de dues i només recorda una ara. 

I podia deixar de mirar? Bé, ell podria basada en aquesta informació, però serà millor que la recerca la resta de la llista. Perquè el que si eren zero a la llista? Què passa si un fos negatiu a la llista? Només sap que la seva resposta és correcte si ell és exhaustiva verificat la llista sencera. Així que ens fixem en la resta d'aquest. Tres-- que era una pèrdua de temps. Tinc mala sort, però jo estava sent correcta per fer-ho. I pel que ara és de suposar seleccionat el nombre més petit i només cal posar al principi de la llista, ja que vaig a fer aquí. Ara ho va fer després, tot i que que no pensa en això gairebé en aquesta mesura? Repetiu el procés, així que algun tipus de bucle. Hi ha una idea familiar. Així que aquí és quatre. Això és actualment el més petit. Això és un candidat. No més. Ara que he vist dues. Aquest és el següent element més petit. Tres-- això no és menor, per la qual Ara Ben pot extirpar a tots dos. 

I ara repetim el procés, i per descomptat, es tira a terme tres següent. Repetir el procés. Quatre es va retirar. I ara que estem fora dels nombres, de manera que la llista ha de ser ordenada. 

I, en efecte, es tracta d'un algoritme formal. Un científic de la computació faria anomenar aquesta "ordenació per selecció" amb la idea d'una espècie iteratively-- enumerar de nou i una altra vegada i una altra seleccionant el nombre més petit. I el que és agradable sobre ell és és tan rematadament intuïtiva. És tan simple. I es pot repetir el mateix operació una vegada i una altra. És molt senzill. 

En aquest cas va ser ràpid, però Quant de temps es prengui realment? Farem que sembli i sentir una mica més tediós. Així que un, dos, tres, quatre, cinc-sis, set, vuit, nou, 10, 11, 12, 13, 14, 15, 16-- nombre arbitrari. Només volia més aquest temps de què només el quatre. Així que si tinc un tot munt de nombres que ara-- Ni tan sols importa el que es tracti: de deixar pensar en el que aquesta algoritme és molt similar. 

Suposem que hi ha un nombre allà. Un cop més, no importa el que són, però són a l'atzar. Estic aplicant l'algoritme de Ben. Necessito seleccionar el nombre més petit. Què faig? I vaig a físicament fer que aquest moment d'actuar cap a fora. Buscant, buscant, mira, mira, mira. Només de moment d'arribar a Al final de la llista es pot Sóc conscient dels més petits número dos va ser aquesta vegada. Un no està a la llista. Així que vaig posar a sota 2. 

Què faig ara? Mirant, mirant, mirant, mirant. Ara he trobat el número set, perquè hi ha llacunes en aquests numbers-- però només arbitrària. Tot bé. Així que ara puc posar 07:00. Mirant mirant, mirant. 

Ara estic suposant, Per descomptat, que Ben no té RAM addicional, extra memòria, perquè, per descomptat, Estic mirant el mateix nombre. Segurament que podria haver recordat tots aquests números, i això és absolutament cert. Però si Ben recorda tot dels números que ha vist, en realitat no ha fet avenços fonamentals perquè ja té la capacitat de buscar a través dels nombres en el tauler. Recordant a tots els els números no ajuda, perquè ell pot encara com un ordinador Només mira, ho hem dit, un nombre en un moment. Així que no hi ha cap tipus de trucs aquí que pot aprofitar. 

Així que en realitat, com ja seguir buscant la llista, Jo, literalment, tinc que acaba de seguir endavant d'anada i tornada a través d'ell, arrencant el nombre immediatament inferior. I com es pot inferir tipus de de les meves moviments ximples, Això es posa molt tediós molt ràpidament, i em sembla estar anant i endavant, enrere i endavant una mica. Ara, per ser justos, no he d'anar tan, bé, anem a veure-- per ser justos, No he de caminar força tants passos cada vegada. Perquè, és clar, com jo seleccionar els números de la llista, la llista restant es fa més curt. 

I així pensarem la quantitat de passos que estic realment penosament a través de cada vegada. En la primera situació teníem 16 nombres, i així només anem a maximally-- fer això per un discussion-- Havia de mirar a través de 16 números per trobar la més petita. Però una vegada que vaig arrencar el nombre més petit, com sempre va ser la llista restant, per descomptat? Només 15. Llavors, quants nombres de Ben va fer o que tenen per mirar a través de la segona vegada? 15, només per anar a buscar els més petits. Però ara, per descomptat, la llista és, també, més petita del que era abans. Llavors, com ho van fer molts passos ha de prendre la propera vegada? 14 i després 13 i després 12, més punt, punt, punt, fins que em quedo amb un de sol. Així que ara ho faria un científic de la computació preguntar, bé, el que fa que tots iguals? En realitat, és igual a poc de concret nombre que sens dubte podríem fem aritmèticament, però volem parlar sobre l'eficiència dels algoritmes una mica més formulaically, independent de la durada de la llista és. 

I perquè sàpiga què? Això és 16, però com he dit abans, Anem a cridar la mida del problema n, on n és un nombre. Potser sigui 16, potser és 3, potser és un milió. No ho sé. No m'importa. El que realment vull és una fórmula que pugui utilitzar per comparar aquest algoritme contra altres algoritmes que algú podria reclamar són millors o pitjors. 

Així que resulta, i només jo saber això des de l'escola primària, que això realment funciona a la mateixa cosa com n sobre núm més un més de dos. I això passa a ser igual, de Per descomptat, n al quadrat més n més de dos. Així que si volia una fórmula De quants passos van participar en l'estudi de tots d'aquests números una i altra vegada i una altra vegada i una altra, jo diria que està n al quadrat més n més de dos. Però saps què? Això només es veu desordenat. Jo realment vull una sentit general de les coses. I es pot recordar de l'escola secundària que hi ha és la noció de terme més alt ordre. Quin d'aquests termes, el núm quadrat, el n, o la meitat, té el major impacte en el temps? Com més gran n aconsegueix, que d'aquests assumptes més? 

En altres paraules, si el connecto en un milió, n al quadrat serà més probable el factor dominant, perquè un milió de vegades en si és molt més gran que més un addicional milions. Així que ja saben què? Aquest és un donaran tan gran nombre si s'eleva al quadrat un nombre. Això en realitat no importa. Només anem creu que i oblidar-se'n. I pel que un científic de la computació diria que l'eficàcia d'aquest algoritme és de l'ordre de n squared-- Em refereixo a realment una aproximació. És una espècie de més o menys n al quadrat. Amb el temps, com més gran i més gran que n es fa, això és una bona estimació del que el l'eficiència o la manca d'eficiència d'aquest algoritme és en realitat. I va derivar que, per descomptat, pel que fa a realitzar els càlculs. Però ara només estic agitant les meves mans, perquè acabo desitjar un sentit general d'aquest algoritme. 

Així, utilitzant la mateixa lògica, per la seva banda, considerarem un altre algoritme ja trobem at-- cerca lineal. Quan jo estava buscant per a la book-- telèfon No arreglármelo, buscant a través de la book-- telèfon vam mantenir dient que era 1.000 passos, o 500 passos. Però anem a generalitzar això. Si hi ha n pàgines en la guia de telèfons, el que és el temps d'execució o la eficiència de cerca lineal? És de l'ordre de la quantitat de passos per trobar Mike Smith mitjançant la recerca lineal, la primer algoritme, o fins i tot el segon? 

En el pitjor dels casos, Mike està a l'extrem del llibre. Així que si el directori té 1.000 pàgines, vam dir l'última vegada, en el pitjor dels casos, que podria prendre la forma més o menys moltes pàgines per trobar Mike? Igual que 1,000. És un límit superior. És una pitjor situació possible. Però, de nou, ens estem allunyant de 1.000 números com ara. És només n. 

Quina és la conclusió lògica? Trobar Mike en un telèfon llibre que té n pàgines podria portar, en el pitjor dels casos, el nombre de passos en l'ordre dels n? I de fet un ordinador científic diria que el temps d'execució, o la rendiment o l'eficiència o ineficiència, d'un algoritme com una recerca lineal és de l'ordre de n. I podem aplicar el mateix lògica de creuar alguna cosa fora com acabo de fer a la segona algoritme que vam tenir amb la guia telefònica, on vam ser dues pàgines alhora. 

Així 1,000 pàgina de la guia telefònica podria portar-nos a 500 voltes de pàgina, més un si doblem una mica cap enrere. Així que si un directori té n pàgines, però que estem fent dues pàgines alhora, que és més o menys què? N més de dos, pel que és com n més de dos. Però vaig fer el reclam d'una Fa moment en què n sobre dos-- això és una mica el mateix que acaba de n. És només un factor constant, els informàtics dirien. Anem només se centren en les variables, realmente-- els majors variables en l'equació. 

recerca de manera lineal, ja es faci una pàgina alhora o dues pàgines alhora, és una espècie de fonamentalment els mateixos. Encara és de l'ordre de n. Però jo deia amb el meu quadre anterior que la tercera algorisme no era lineal. No era una línia recta. Va ser aquesta línia corba, i la fórmula algebraica no hi havia què? Registre de n- tan logaritme en base dues de n. I no hem d'entrar en massa molts detalls sobre els logaritmes d'avui, però la majoria dels informàtics no ho faria fins i tot li dirà el que és la base. A causa de que tot és només factors constants, per així dir-ho, només lleugeres diferències numèriques. I així, aquesta seria una molt comuns camí per ordinador particular formals els científics en una junta o programadors en un tauler blanc En realitat l'argument dels quals algoritme que usarien o el que l'eficiència de la seva algoritme és. 

I això no és necessàriament una cosa es discuteix en gran detall, però un bon programador és algú que té un fons sòlid i formal. Ell és capaç de parlar amb que en aquest tipus de camí i fer de arguments qualitatius com de per què un algoritme o una peça de programari és superior en alguna forma a una altra. A causa de que certament es podria n'hi ha prou amb executar el programa d'una persona i comptar el nombre de segons que es necessita per solucionar alguns nombres, i es pot executar alguns El programa d'una altra persona i comptar el nombre de de segons que triga. Però aquesta és una manera més general que es pot utilitzar per analitzar els algoritmes, si es vol, només en paper o només verbalment. Sense ni tan sols executar-lo, sense fins i tot tractant d'entrades de mostra, només pot raonar a través d'ell. I així, amb la contractació d'un desenvolupador o si que ell o ella una mena de discutir amb vostè Per això el seu algoritme, el seu secret salsa per buscar milers de milions de pàgines web per al seu empresa és millor, aquests són els tipus d'arguments que idealment hauria de ser capaç de fer. O, almenys, aquests són el tipus de coses que hauria sorgit en la discussió, en menys en una discussió molt formal. Tot bé. Així Ben proposar alguna cosa anomenada ordenació per selecció. Però vaig a proposar que hi ha altres maneres de fer això, també. El que no m'agrada molt sobre l'algoritme de Ben és que ell va seguir caminant, o havent a caminar, d'anada i tornada i d'anada i tornada i d'anada i tornada. ¿I si en comptes hagués de fer alguna cosa així com aquests números aquí i hagués de bregar només amb cadascun nombre al seu torn que a mi es dóna? 

En altres paraules, aquí està la meva llista de nombres. Quatre, un, tres, dos. I vaig a fer el següent. Vaig a inserir els números a la qual pertanyen més aviat que seleccionant-les una a la vegada. En altres paraules, aquest és el número quatre. 

Aquí està la meva llista original. I vaig a mantenir essencialment una nova llista aquí. Així que aquesta és la llista d'edat. Aquesta és la llista nova. Veig el número quatre en primer lloc. La meva nova llista està buida inicialment, pel que és trivial el cas què quatre està ara llista variats. Només estic prenent el número que em donen, i ho estic posant en la meva nova llista. 

S'ordena aquesta nova llista? Sí. És estúpid perquè només hi ha una element, però és absolutament ordenada. No hi ha res fora de lloc. És més interessant, aquest algoritme, quan moc a la següent etapa. 

Ara tinc un. Així que, per descomptat, pertany a la principi o al final d'aquesta nova llista? El començament. Així que he de fer un treball ara. He estat prenent alguns llibertats amb el meu marcador amb només dibuixar coses on els vull, però això no és realment exacta en un ordinador. Un equip que, com se sap, té RAM, o memòria d'accés aleatori, i això és un byte i un altre byte i un altre byte. I si té un gigabyte de RAM, que té mil milions de bytes, però estan físicament en un sol lloc. No es pot simplement moure coses d'una banda dibuixant a la pissarra on vulguis. Així que si la meva nova llista té quatre ubicacions a la memòria, per desgràcia, el quatre és Ja en el lloc equivocat. 

Així que per inserir el número u No puc dibuixar aquí. Aquesta posició de memòria no existeix. Això seria fer trampa, i han estat trampa pictòricament durant uns minuts aquí. Així que en realitat, si jo vull posar un aquí, He de copiar temporalment els quatre i després posar l'un allà. 

Això està bé, això és correcte, això és tècnicament possible, però s'adonen que és una feina extra. Jo no només cal posar el nombre al seu lloc. La primera vegada que vaig haver de moure una nombre, a continuació, posar al seu lloc, així que tipus de vaig doblegar el meu quantitat de treball. Així que vés amb això en compte. 

Però ara estic fet amb aquest element. Ara vull agafar el número tres. On, per descomptat, pertany? Entremig. No puc enganyar més i només cal posar-hi, perquè, de nou, aquesta memòria està en ubicacions físiques. Així que he de copiar els quatre i posar el tres per aquí. No és gran cosa. És només un pas addicional nou-- se sent molt barat. 

Però ara de passar a tots dos. Els dos, per descomptat, pertany aquí. Ara es comença a veure com el treball pot acumular-se. Ara, què he de fer? Sí, he de moure els quatre, llavors he de copiar els tres, i ara puc portar en ambdues. I la captura amb aquest algoritme, curiosament, és que suposem que tenim una manera més extrema cas en el qual és diguem vuit, set, sis, cinc, quatre, tres, dos, un. Això és, en molts contextos, el pitjor dels casos, perquè la maleïda cosa és literalment cap enrere. 

En realitat no afectarà algoritme de Ben, perquè en la selecció de Ben espècie que va a mantenir anar amunt i avall per la llista. I pel fet que estava sempre a la recerca a través de tota la llista restant, no importa on els elements són. Però en aquest cas amb la meva inserció approach-- anem a provar això. 

Així que un, dos, tres, quatre, cinc, sis, set, vuit. Un dos tres quatre, cinc, sis, set, vuit. Vaig a prendre el vuit, i on ho poso? Bé, al principi de la llista, ja que aquesta nova llista està ordenada. I creuo cap a fora. 

On poso els set? Maleïda sigui. Ha d'anar-hi, per la qual He de fer algunes còpies. I ara els set va aquí. Ara de passar als sis. Ara és encara més feina. 

La vuitena ha d'anar aquí. Set ha d'anar aquí. Ara el 6 poden anar aquí. Ara m'agafa el cinc. Ara els vuit ha d'anar aquí, set ha d'anar aquí, 6 ha d'anar aquí, i Ara els cinc i repetir. I estic més o menys movent constantment. 

Així que al final, això anem a algorithm-- cridar inserció sort-- realitat té un munt de treball, també. És simplement diferent tipus de treball que Ben. El treball de Ben m'havia torno d'anada i tornada tot el temps, la selecció de la següent més petita element i una altra. Pel que era aquest tipus molt visual de l'obra. 

Aquest altre algoritme, que encara està correct-- que aconseguirà la feina done-- Només canvia la quantitat de treball. Sembla que inicialment ets l'estalvi, perquè estàs sol tractar amb cada element a la bestreta sense haver de caminar tot el camí a través de la llista com Ben era. Però el problema és, sobretot en aquests boges casos en què és tot a l'inrevés, ets només una mica posposar el treball dur fins que hagi de corregir els seus errors. 

I pel que si es pot imaginar això 08:07-sis i cinc i més tard de quatre i 03:02 moure el seu camí a través de la llista, que acaba de canviar el tipus de treball que estem fent. En lloc de fer-ho al a partir del meu iteració, Només estic fent en el final de cada iteració. Així que resulta que aquest algorisme, també, generalment es diu ordenació per inserció, També està en l'ordre de n al quadrat. En realitat no és millor, no són millors per a tothom. 

No obstant això, hi ha un tercer enfocament Jo ens animaria a considerar, que és això. Així que suposo que la meva llista, per simplicitat de nou, és de quatre, un, tres, dos-- només quatre números. Ben tenia bona intuïció, bona intuïció humana abans, pel qual es va fixar la totalitat eventually-- llista d'ordenació per inserció. Jo ens engatusé llarg. Però considerarem la forma més senzilla de solucionar aquesta llista. 

Aquesta llista no està ordenada. Per què? En Anglès, explicar per què En realitat no és ordenada. Què vol dir que ser resolt? 

ESTUDIANT: No és seqüencial. 

DAVID Malan: no seqüencial. Dóna'm un exemple. 

ESTUDIANT: Posar en ordre. 

DAVID Malan: OK. Dóna'm un exemple més específic. 

ESTUDIANT: ordre ascendent. DAVID Malan: fi de no ascendir. Ser més precisos. No sé què vol dir amb ascendent. Que passa? 

ESTUDIANT: El més petit de la números no és en el primer espai. 

DAVID Malan: nombre més petit de no en el primer espai. Ser més específic. Estic començant a fer-se popular. Estem comptant, però el que està fora d'aquí? 

ESTUDIANT: seqüència numèrica. DAVID Malan: seqüència numèrica. tipus de manteniment de tot el món que aquí-- nivell molt alt. Només literalment, digues-me el que és malament com ho faria una-cinc anys d'edat. 

ESTUDIANT: més un. 

DAVID Malan: Què és això? 

ESTUDIANT: més un. 

DAVID Malan: Què vol dir que un més? Dóna'm una diferent de cinc anys d'edat. Què passa, mama? Què passa, pare? Què vol dir això no està ordenada? 

ESTUDIANT: No és el lloc correcte. 

DAVID Malan: Quin és no en el lloc correcte? 

ESTUDIANT: Quatre. DAVID Malan: OK, bo. Així que 4 no és on ha d'estar. En particular, és això correcte? Quatre i un, el primer dos nombres que veig. ¿Això és correcte? No, estan fora d'ordre, oi? De fet, pensa ara sobre un equip, també. Només pot mirar potser un, potser dues coses a la vegada-- i en realitat només una cosa alhora, però almenys pot mirar a una cosa, llavors el El següent que just al costat d'ella. 

Així són aquests per tal? Esclar que no. Així que ja saben què? Per què no prenem nadó etapes de fixació d'aquest problema en lloc de fer aquests de luxe algoritmes com Ben, on És una espècie de fixació per bucle a través de la llista en comptes de fer el que vaig fer, on Jo només tipus de fix que a mesura que avancem? Anem a trencar, literalment, per la noció d'ordre numèric order--, cridar el que want-- en aquestes comparacions per parells. 

Quatre i un. És aquest l'ordre correcte? Així que arreglarem això. Un i quatre, i després només haurem de copiem. Molt bé, molt bé. Em fixo 01:04. Tres i dos? No. Que les meves paraules coincideixin amb els dits. Quatre i tres? 

No és la fi, així que vaig fer un, tres, quatre, dos. D'acord. Ara 04:02? Hem d'arreglar això, també. Així que un, tres, dos, quatre. Així li ho va arreglar? No, però és el més a prop ordenats? 

És, doncs hem arreglat aquest error, hem arreglat aquest error, i hem arreglat aquest error. Així que podria dir-se que ho van arreglar tres errors. Encara en realitat no mirar ordenada, però és objectivament més a prop ordenada perquè hem arreglat alguns d'aquests errors. 

Ara, què faig ara? Jo com que va arribar al final de la llista. Em semblava haver fixat tots els errors, però no. Perquè en aquest cas, alguns números podria haver bombollejava més a prop a altres nombres que encara estan fora de servei. Així que anem a fer-ho de nou, i vaig a només ho fan en el seu lloc aquesta vegada. Un i tres? Està bé. Tres i dos? Per descomptat que no, així que anem a canviar. Així que dos, tres. Tres i quatre? I ara serem particularment pedant aquí. L'hi va arreglar? Vostè sap que és l'ésser humà ordenades. 

Hauria intentar-ho de nou. Així que Olivia està proposant ho intento de nou. Per què? A causa de que un equip no té el luxe dels ulls humans de simplement fent una ullada esquena; OK, he acabat. Com determina l'equip que la llista està ordenada ara? Mecànicament. 

Hauria d'anar a través una vegada més, i només si No fer / algun comentari sobre errors puc llavors la conclusió que l'equip, sip, som bons per anar. Així ui dos, dos i 3, tres i quatre. Ara definitivament puc dir que és ordenats, perquè he fet cap canvi. Ara bé, seria un error i just ximple si jo, l'equip, fet aquestes mateixes preguntes 1 esperant respostes diferents. no hauria de succeir. 

I pel que ara s'ordena la llista. Desafortunadament, el temps de funcionament de aquest algoritme és n al quadrat. Per què? A causa que té un nombre n, i al pitjor dels casos s'ha de moure un nombre n n vegades perquè cal seguir endavant tornar a comprovar i corregir potencialment aquests nombres. I podem fer un major anàlisi formal, també. 

Així que això és tot el que dir que hem pres 3 enfocaments diferents, un d'ells immediatament intuïtiva del pal de Ben al meu s'ha suggerit, ordenar a aquesta on tipus d'perd de vista el bosc pels arbres inicialment. Però llavors, si vostè pren un pas enrere, voilà, hem fixat la noció de classificació. Així que això és, s'atreveix a dir, un nivell més baix potser que alguns dels altres algoritmes, però anem a veure si no podem visualitzar aquests per mitjà d'això. 

Així que això és una bona programari que algú va escriure usant barres de colors que de anem a fer el següent per a nosaltres. Cadascuna d'aquestes barres representa un nombre. Taller de la barra, més el nombre, més petita és la barra, com menor sigui el nombre. Pel que idealment volem un bon piràmide on comença petit i s'omple gran, i això significaria que aquestes barres estan ordenats. Així que vaig a seguir endavant i triar, per exemple, l'algorisme de Ben la selecció primer-- tipus. 

I observi el que està fent. La forma en que han triat visualitzar aquest algoritme és que, igual que jo caminant a través de la cistella, aquest programa està caminant a través de la seva llista de nombres, destacant en rosa cada nombre que s'està mirant. I el que va a ocórrer ara? 

El nombre més petit que Em vaig trobar de sobte o Ben obté mogut al principi de la llista. I l'avís que van fer evict el número que hi era, i que està perfectament bé. No em fico en aquest nivell de detall. Però hem de posar aquest nombre en algun lloc, pel que acabem de mudar a la lloc obert que va ser creat. Així que vaig a accelerar aquest , Perquè en cas contrari, es torna molt tediós ràpidament. Animació speed-- hagi d'anar. Així que ara mateix principi Jo estava aplicant, però pot començar a sentir l'algoritme, si voluntat, ni es veu una mica més clarament. I aquest algoritme té l'efecte de seleccionar el següent element més petit, pel que començarem a veure que la rampa sobre de l'esquerra. I en cada iteració, com jo proposat, es fa una mica menys de treball. No ha d'anar tot el camí de nou a l'extrem esquerre de la llista, perquè ja coneix als s'ordenen. Així que tipus de se sent com si fos accelerant, tot i que cada pas és tenint la mateixa quantitat de temps. Només hi ha un menor nombre de passos restants. I ara es pot sentir el tipus de algoritme de neteja al final d'ella, i de fet ara s'ha solucionat. 

Així ordenació per inserció es fa tot. He de tornar a canviar aleatòriament la matriu. I noti que només pot mantenir l'aleatorització d'ella, i ens posarem una aproximació de el mateix enfocament, l'ordenació per inserció. Permetin-me retardar fins aquí. Anem a començar que més. Atura. 

Anem a saltar 04:00. Allà anem. Selecció aleatòria d'ells matriu. I aquí vaya-- ordenació per inserció. Jugar. Recordeu que es tracta de cadascun element que troba de forma immediata, però si pertany a el lloc equivocat avís tota la feina que ha de succeir. Hem de seguir desplaçant més i més elements per a fer lloc per al qual volem posar al seu lloc. 

Així que ens estem centrant en el extrem esquerre de la llista única. Avís ni tan sols hem vist que at-- no han posat en relleu en rosa res a la dreta. Estem davant els problemes a mesura que avancem, però estem creant una gran quantitat de treballar per a nosaltres mateixos encara. I pel que si accelerar això ara anar fins a la seva finalització, té una sensació diferent a ell de fet. És només centrant-se en l'extrem esquerre, però fent una mica més de treball com needed-- tipus de coses suavitzat sobre, arreglar coses, però en última instància es tracta amb cada element d'una en una fins a arribar a ell-- bo, Tots sabem com va a acabar, així que és una mica decebedor, potser. 

Però la llista en el end-- spoiler-- va a ser resolt. Així que anem a veure una última un. No podem simplement saltar ara. Ja gairebé hem arribat. Queden dos, un per anar. I llest. Excel · lent. 

Així que ara anem a fer una última, tornar a l'aleatorització amb l'ordenació de bombolla. I noto aquí, especialment si retardar baix, això lliscant per mantenir. Però cal notar que només té 2-2 comparisons-- tipus de solucions locals. Però tan aviat com s'arriba a Al final de la llista en rosa, el que va a haver de passar de nou? Sí, va a haver de començar de nou, ja que només errors fixos per parells. I que podria haver revelat encara altres. I pel que si accelerar aquest procés, se li veure que, tant com el nom implica, la més petita elements-- o més aviat, elements-- els més grans estan començant que pugen a la part superior, si es vol. I els elements més petits són començant a bombolla cap a baix a l'esquerra. I, en efecte, que és una mena de l'efecte visual. I així, això va a acabar l'acabat d'una manera molt similar, també. 

No tenim habitar en aquest cas en particular. Permetin-me obrir això ara, també. Hi ha alguns altres algoritmes d'ordenació en el món, alguns dels quals són capturats aquí. I especialment per als estudiants que no estan necessàriament visual o matemàtica, com ho vam fer abans, podem També fer això audially si associar un so a això. I només per diversió, he aquí una uns algoritmes diferents, i un d'ells, en particular, que està notarà que es diu "fusió espècie." 

En realitat, és una forma fonamentalment millor algoritme, de tal manera que es fonen espècie, una de els que estan a punt de veure, No és la fi de n al quadrat. És de l'ordre de n vegades de registre n, que és en realitat més petit i per tant més ràpid que els altres tres. I hi ha un parell d'un altre els ximples que ja veurem. 

Així que aquí anem amb una mica de so. Aquesta és l'ordenació per inserció, així que de nou és només tractar amb els elements com vénen. Es tracta d'una espècie de bombolla, pel que és tenint en compte els parells alhora. I de nou, els elements més importants estan bombollejant fins a la part superior. 

Selecció El següent tipus. Aquest és l'algoritme de Ben, on De nou s'ha de seleccionar de forma iterativa l'element immediatament inferior. I de nou, ara es pot escoltar que realment està accelerant, però només en la mesura com ho està fent cada vegada menys treballar en cada iteració. Aquest és el més ràpid, combinar espècie, que es classificar grups de nombres combinant junts i després ells. Així look-- l'esquerra la meitat ja està ordenada. 

Ara està la classificació de la meitat dreta, i Ara es va a combinar en una sola. Això és una cosa que es diu "Gnome tipus." I es pot veure que tipus de que va d'anada i tornada, la fixació de treball una mica aquí i no abans de procedir al nou treball. I ja està. Hi ha un altre tipus, que és en realitat només amb fins acadèmics, anomenada "classe estúpida", que té les seves dades, que ordena a l'atzar, i després comprova si està ordenada. I si no ho és, es tornarà a ordenar que a l'atzar, comprova si està ordenada, i si no es repeteix. I, en teoria, probabilísticament Això completarà, però després d'una mica de temps. No és el més eficient dels algoritmes. Així que qualsevol pregunta sobre els algoritmes o qualsevol particulars relacionada amb elles, també? 

Bé, ara anem a esmicolar el que tots aquestes línies són que he estat dibuixant i el que estic suposant que l'ordinador pot fer sota de la campana. Jo diria que tots aquests números Segueixo drawing-- que necessiten per obtenir emmagatzemat en algun lloc de la memòria. Anem a desfer-nos d'aquest tipus ara, també. 

Així que una peça de la memòria en una computer-- pel DIMM RAM és el que es van realitzar cerques d'ahir, dual module-- de memòria en línia té aquest aspecte. I cadascuna d'aquestes petites fitxes negres és un nombre de bytes, en general. I a continuació, les agulles d'or són com el cables que es connecten a l'ordinador, i la placa de silici verd és només el que manté tot junt. Llavors, què significa això realment? Si aquest tipus de dibuix mateixa imatge, Suposem per simplicitat que aquest DIMM, dual mòdul de memòria en línia, és un gigabyte de memòria RAM, un giga de memòria, que és el nombre de bytes en total? Un gigabyte és el nombre de bytes? Més que això. 1.124 és el quilo, 1.000. Mega és milions. Giga és un mil milions. 

Estic mentint? Podem fins i tot llegir l'etiqueta? Això és en realitat 128 gigabytes, pel que és molt més. Però anem a pretendre aquest és només un gigabyte. Per la qual cosa significa que hi ha 1000000000 bytes de memòria disponibles per a mi o 8 mil milions de bits, però anem per parlar en termes de bytes ara, avançant. 

Així que el que això significa és que això és un byte, això és un altre byte, aquest és un altre byte, i si realment volíem per ser específics, hauríem de dibuixar un bilió de petits quadrats. Però què vol dir això? Bé, permetin-me zoom en aquesta imatge. Si tinc alguna cosa que sembla així ara, això és quatre bytes. 

I pel que podria posar quatre nombres aquí. Un dos tres quatre. O podria posar quatre lletres o símbols. "Hey!" podria anar-hi, perquè cadascuna de les lletres, hem comentat anteriorment, podria ser representat amb vuit bits o ASCII o un byte. Així, en altres paraules, es pot posar 8 mil milions de coses a l'interior d'aquest un pal de memòria. Ara, què significa per a posar les coses amb esquena amb esquena a la memòria d'aquesta manera? Això és el que un programador diria una "matriu". En un programa d'ordinador, que no crec sobre el maquinari subjacent, per se. Vostè només pensa en si mateix com tenint accés a un total de mil milions de bytes, i es pot el que vulgui amb ella. Però per conveniència generalment és útil per mantenir el seu dret de memòria un al costat de l'altre com aquest. Així que si faig zoom sobre això- perquè per descomptat no anem per dibuixar un bilió de petits squares-- anem a suposar que aquest tauler representa que pal de la memòria ara. I només vaig a assenyalar a tots els que el meu marcador acaba per donar-me aquí. Així que ara tenim un pal de memòria de la placa això té un, dos, tres, quatre, cinc, sis, un, dos, tres, quatre, cinc, sis, seven-- així que 42 bytes de memòria en el total de la pantalla. Gràcies. Sí, ho va fer el meu aritmètica dreta. Pel que 42 bytes de memòria aquí. Llavors, què significa això realment? Bé, un programador d'ordinadors en realitat generalment pensar en aquesta memòria com direccionable. En altres paraules, cada un d'aquests ubicacions a la memòria, en maquinari, té una adreça única. 

No és tan complex com un Brattle Square, Cambridge, Mass., 02138. En canvi, és només un nombre. Aquest és el nombre de bytes zero, és a dir un, això és dues, això és tres, i això és 41. Espera un minut. Vaig pensar que vaig dir fa un moment 42. Vaig començar a comptar des de zero, pel que és realment correcte. Ara no hem de cridar la realitat com una reixeta, i si ho dibuixa com una quadrícula Crec que les coses realment ser una mica enganyós. Què faria un programador, en la seva pròpia ment, en general, pensar en això la memòria com és com una cinta, com un tros de cinta adhesiva això és només una vegada i una altra per sempre o fins que s'esgoti la memòria. Així que d'una manera més comuna per dibuixar i només pensar en la memòria seria que això és byte zero, un, dos, tres, i després del punt, punt, punt. I vostè té 42 d'aquests bytes en total, fins i tot encara que físicament en realitat podria ser alguna cosa més semblant a això. 

Així que si vostè ara pensa en el seu la memòria, ja que, igual que una cinta, això és el que un programador nou cridaria a una matriu de memòria. I quan es desitja emmagatzemar en realitat alguna cosa a la memòria d'un ordinador, en general, es deu conservar les coses esquena amb esquena amb esquena amb esquena. Així que hem estat parlant de nombres. I quan jo volia per resoldre problemes com quatre, un, tres, dos, tot i que jo estava dibuixant només el número quatre, un, tres, dues de la taula, l'ordinador realment tenen aquesta configuració en la memòria. 

I el que seria al costat de la dos a la memòria de l'ordinador? Bé, no hi ha una resposta a això. No se sap molt bé. I sempre que la equip no ho necessita, que no ha de preocupar del que és el proper als números que es preocupa per. I quan he dit abans que un ordinador només pot mirar en una direcció a la vegada, això és una espècie de per què. 

No a diferència d'un registre jugador i un capçal de lectura només ser capaç de mirar a una certa ranura en un registre físic de la vella escola a la vegada, de manera similar pot un ordinador gràcies a la seva UPC i la seva conjunt d'instruccions Intel, entre les instruccions es llegeix de la memòria o guardar en un memory-- equip només pot mirar en un lloc en un temps-- de vegades una combinació d'ells, però en realitat un sol lloc alhora. Així que quan fèiem aquests diversos algoritmes, No només estic escrivint en una vacuum-- quatre, un, tres, dos. Aquests nombres pertanyen en realitat en algun lloc físic en la memòria. Així que hi ha diminut transistors o algun tipus de l'electrònica sota de la campana d'emmagatzematge d'aquests valors. 

I en total, el nombre de bits involucrat en aquest moment, només per ser clars? Així que això és de quatre bytes, o ara és 32 bits en total. Així que en realitat hi ha 32 zeros i els que componen aquestes quatre coses. Hi ha encara més per aquí, però de nou, no es preocupen per això. 

Així que ara anem a demanar una altra pregunta usant la memòria, perquè que al final del dia és la variància. No importa el que podríem fer amb l'equip, al final del dia el maquinari és encara el mateixa sota de la campana. Com anava a emmagatzemar una paraula en aquesta llista? Doncs bé, una paraula en un equip com "Hey!" s'emmagatzemaria com aquest. I si volia una més llarga paraula, només ha de sobreescriure i que dir alguna cosa així com "hola" i botiga que aquí. 

I així, també, aquesta contigüitat és en realitat un avantatge, pel fet que un equip pot simplement llegeix de dreta a esquerra. Però vet aquí una pregunta. En el context d'aquesta paraula, h-e-l-l-o, signe d'exclamació, Com podria l'equip saber on és el paraula comença i on acaba la paraula? En el context dels nombres, Com funciona l'equip saber quant de temps la seqüència de nombres és o on comença? Bé, resulta out-- i no anirem massa en aquest nivell de detail-- computadores mouen la matèria al voltant en la memòria literalment, a través d'aquestes direccions. Així que en un ordinador, si estàs escriure codi per emmagatzemar coses com les paraules, el que està fent en realitat està escrivint expressions que recorden a on la memòria de l'ordinador aquestes paraules són. Així que permetin-me fer un molt, exemple molt senzill. 

Vaig a seguir endavant i obrir un programa de text simple, i jo vaig a crear un arxiu anomenat hola.c. La major part d'aquesta informació, No entraré en gran detall, però vaig a escriure una programa en el mateix idioma, C. Això és molt més intimidatori, Jo diria, que gratar, però és molt similar en esperit. De fet, aquests arrissat braces-- puguis tipus de pensar en el que he fet com aquest. 

Anem a fer això, en realitat. Quan fa clic a bandera verda, fer el següent. Vull imprimir "hola". Així que això és ara pseudocodi. Sóc una mena de desdibuixar les línies. En C, aquest idioma estic parlant aproximadament, aquesta línia d'impressió hola en realitat es converteix en "printf" amb alguns parèntesi i un punt i coma. 

Però és la mateixa idea exacta. I això molt fàcil d'utilitzar "Quan es fa clic a bandera verda" es converteix el més arcà "void main int." I això realment sense cap assignació, així que només vaig a ignorar això. No obstant això, les claus són com el peces del trencaclosques corbes d'aquest tipus. 

Pel que pot tipus d'endevinar. Fins i tot si mai has programat abans, ¿Què fa aquest programa probablement fer? Probablement imprimeix hola amb un signe d'exclamació. 

Així que anem a tractar d'això. Vaig a guardar-lo. I això és, de nou, una molt entorn de la vella escola. No puc fer clic, no puc arrossegar. He de escriure ordres. Per això vull córrer el meu programa, per la qual Jo podria fer això, de la mateixa manera que hola.c. Aquest és l'arxiu em vaig trobar. Però espera, que em falta un pas. Què vam dir és una condició necessària pas per a un llenguatge com C? He font acaba d'escriure codi, però què necessito? Sí, necessito un compilador. Així que en el meu Mac aquí, tinc una programa anomenat GCC, GNU compilador de C, el que em permet fer això- al seu torn el meu codi font en, l'anomenarem, codi màquina. 

I puc veure que, de nou, de la següent manera, aquests són els zeros i uns I només creat a partir de la meva codi font, tots els zeros i uns. I si vull córrer el meu program-- succeeix per a ser anomenat a.out per reasons-- històrica "hola". Puc córrer de nou. Hola Hola hola. I sembla estar funcionant. 

Però això vol dir que en algun lloc de la meva la memòria de l'ordinador són les paraules h-e-l-l-o, signe d'exclamació. I resulta que, igual que un a part, el que un ordinador faria normalment fer perquè sàpiga on les coses comencen i és end-- posarà un símbol especial aquí. I la convenció és posar el número zero al final d'una paraula perquè sàpiga on en realitat acaba, per la qual cosa no seguir imprimint més i més caràcters dels que en realitat es proposen. 

Però el menjar per emportar aquí, fins i tot encara que això és bastant arcà, és que és en última instància, relativament simple. Se li va donar una mena de cinta, un espai en blanc espai en el qual pot escriure lletres. Vostè simplement ha de tenir una símbol especial, igual que de manera arbitrària el número zero, per posar al final de les seves paraules perquè l'ordinador sap, Oh, hauria aturar la impressió després de Veig el signe d'exclamació. Perquè el següent que hi ha és un valor ASCII de zero, o el caràcter nul com algú en diria. Però hi ha una espècie d'un problema aquí, i anem a tornar de nou als números per un moment. Suposem que faig, de fet, disposarà d'un conjunt de nombres, i suposem que la programa que estic escrivint és com un llibre de qualificacions d'un mestre i una aula de professors. I aquest programa li permet per escriure en les puntuacions dels estudiants en les proves. I suposem que l'estudiant obté 100 en el seu primer concurs, potser com un 80 en la pròxima, a continuació, una 75, després a 90 en la quarta prova. 

Així que en aquest punt de la història, la matriu és d'una grandària 04:00. No hi ha absolutament més memòria al ordinador, però la matriu, per així dir-ho, és de mida quatre. Suposem ara que el professor vol per assignar una cinquena prova per a la classe. Bé, una de les coses que ell o ella va a haver de fer ara és emmagatzemar un valor addicional aquí. Però si la matriu té el mestre creat en aquest programa és de mida per, un dels problemes amb una matriu que és no es pot simplement seguir afegint a la memòria. Perquè el que si una altra part de la programa té la paraula "hey" just aquí? 

En altres paraules, la memòria pot ser utilitzat per a qualsevol cosa en un programa. I si per endavant teclegi, hey, Vull entrada de quatre puntuacions de les proves, que podrien anar aquí i aquí. I si canvia de parer ràpidament més tard i dir que vull un cinquè concurs puntuació, no es pot simplement ja que més li convingui, perquè el que si aquesta s'utilitza la memòria per alguna cosa else-- algun altre programa o alguna altra característica del programa que s'està executant? Així que cal pensar per endavant la forma en la qual desitja emmagatzemar les seves dades, perquè ara s'ha pintat a si mateix en una cantonada digital. 

Pel que un professor pot en canvi dir en escriure un programa per emmagatzemar el seu graus, saben què? Vaig a sol·licitar, en escriure el meu programa, Vull que zero, un, dos, tres, quatre, cinc, sis, vuit graus en total. Així que un, dos, tres, quatre, cinc, sis, set, vuit. El professor pot simplement sobreasigne la memòria en escriure el seu programa i dir, saben què? Mai vaig a assignar més de vuit proves en un semestre. Això és una bogeria. Mai vaig a assignar aquest. Així que d'aquesta manera ell o ella té la flexibilitat a la puntuació de botiga dels estudiants, com 75, 90, i potser un addicional on l'estudiant té el crèdit addicional, 105. 

Però si el mestre mai utilitza aquests tres espais, hi ha una menjar per emportar intuïtiva aquí. Ell o ella està perdent espai. Així, en altres paraules, hi ha una desavantatge comú en la programació on pot assignar exactament com la quantitat de memòria que desitgi, l'alça dels quals és que ets molt efficient-- no estàs sent un malbaratament en sobretot-- però el desavantatge dels quals és el que si canvia d'opinió quan usant el programa que voleu emmagatzemar més dades que els que originalment previst. 

Així que potser la solució és, doncs, escriure els seus programes de tal manera que utilitzen més memòria del que realment necessiten. D'aquesta manera no vas a executar en aquest problema, però estàs sent un malbaratament. I com més memòria utilitza el seu programa, com vam dir ahir, menys la memòria que està disponible per altres programes, com més aviat millor l'equip podria alentir a causa de la memòria virtual. I així, la solució ideal podria ser què? 

Sota-es reparteixen sembla malament. Sobre-el qual es reparteixen sembla malament. Llavors, què podria ser una solució millor? La reassignació. Ser més dinàmic. No s'obligui a escollir un a priori, al principi, el que volen. I certament no sobreasigne, perquè no sigui un malbaratament. 

I així, per aconseguir aquest objectiu, necessitar descarregar a aquesta estructura de dades, per així dir-ho, de distància. I així el que un programador normalment utilitzarà és una cosa que es diu no és una matriu, però una llista enllaçada. En altres paraules, ell o ella començar a pensar en la seva memòria com una mena de manera que es pot treure de la següent manera. Si vull emmagatzemar un nombre en 1 program-- pel que és de setembre M'he donat als meus estudiants un qüestionari; vull per emmagatzemar la primera prova dels estudiants, i van aconseguir un 100 a it-- I demanaré al meu equip, per mitjà del programa que he per escrit, per un tros de memòria. I vaig a emmagatzemar el número 100 en el mateix, i això és tot. 

A continuació, unes setmanes més tard quan arribo a la meva segona prova, i és el moment d'escriure en el qual el 90%, vaig preguntar a l'equip, hey, ordinador, puc tenir un altre tros de memòria? Es em va a donar a aquest tros buit de la memòria. Vaig a posar en el nombre 90, però en el meu programa d'una manera o altre-- i no anem a preocupar-se per la sintaxi per això- que necessito d'alguna manera encadenar aquestes coses juntes. I els vaig a encadenar amb el que sembla una sola fletxa. 

El tercer qüestionari que apareix, Vaig a dir, escolta, ordinador, dóna'm una altra part de la memòria. I vaig a posar a terra el que fos, igual que 75, i he de aquesta cadena de junts ara d'alguna manera. Quarta prova ve, i potser això és cap al final del semestre. I en aquest moment el meu programa podria ser l'ús de la memòria per tot el lloc, tot físicament. I així, només per diversió, jo sóc traurà aquesta volta quiz-- m'oblido del que era; jo pensar que potser un 80 o alguna cosa-- fins aquí. 

Però això està bé, perquè pictòricament Vaig a traçar aquesta línia. En altres paraules, en la realitat, en el maquinari de l'ordinador, la primera puntuació podria acaben aquí perquè és just al començament del semestre. El proper podria acabar aquí perquè una mica de temps ha passat i el programa segueix funcionant. La puntuació següent, que era un 75, podria ser aquí. I l'última puntuació podria ser un 80, que és per aquí. 

Així que, en realitat, físicament, això podria ser el que la memòria del seu ordinador es sembla. Però això no és un trastorn mental útil paradigma per a un programador d'ordinadors. Per què ha de tenir cura quan l' diables seves dades està acabant cap amunt? El que desitja és emmagatzemar dades. 

Això és una cosa així com la nostra discussió abans de treure el cub. Per què t'importa el l'angle és de la galleda i com s'ha de donar volta a dibuixar? El que desitja és un cub. De la mateixa manera aquí, només volen llibre de qualificacions. El que vol és pensar això com una llista de nombres. A qui li importa com és implementat en maquinari? 

Així que l'abstracció ara És aquesta imatge aquí. Aquesta és una llista vinculada, com un programador en diria, en la mesura que té una llista, òbviament, dels nombres. Però està vinculat pictòricament per mitjà d'aquestes fletxes, i totes aquestes fletxes sota són-- el capó, si tens curiositat, recordar que el nostre maquinari físic té adreces zero, un, dos, tres, quatre. Totes aquestes fletxes són és com un mapa o direccions, en la qual si ara 90 és-- He de explicar. 

Zero, un, dos, tres, quatre, cinc, sis, set. Sembla que el 90 és a memòria de nombre de direcció de set. Totes aquestes fletxes són és com un petit tros de paper que és donar instruccions a la programa que diu segueix aquest mapa per arribar al lloc de set. I allà es troba el segona puntuació de la prova de Student. Mentrestant, el 75-- si continuo això, això és set, vuit, nou, 10, 11, 12, 13, 14, 15. 

Aquesta altra fletxa representa només un mapa d'ubicació de la memòria 15. Però, de nou, el programador fa generalment no es preocupen per aquest nivell de detall. I en la majoria de cada programació llenguatge d'avui, el programador ni tan sols saber on en la memòria aquests números són en realitat. Tot el que ell o ella ha de tenir en compte és que d'alguna manera estan vinculats entre si en una estructura de dades com aquest. 

Però resulta que no per aconseguir massa tècnic. Però el fet que potser pot permetre el luxe de tenir aquesta discussió aquí, Suposem que tornem aquesta qüestió aquí d'una matriu. Ja veurem si ens penedim anar aquí. Això és 100, 90, 75, i 80. 

Permetin-me breument fer aquesta afirmació. Aquesta és una matriu, i de nou, la característica destacada d'una matriu és que totes les seves dades estan de nou a esquena amb esquena a memory-- literalment Un byte o potser quatre bytes, un nombre fix de bytes de distància. En una llista enllaçada, que podríem anomenar la així, a sota de la campana que sap on és això? Ni tan sols es necessita per fluir com aquest. Algunes de les dades podria ser de volta a l'esquerra fins allà. Ni tan sols sap. 

I així, amb una matriu, que té una característica coneguda com accés aleatori. I el que els mitjans d'accés aleatori és que l'equip pot saltar a l'instant a qualsevol lloc d'una matriu. Per què? A causa de que l'ordinador sap que la primera ubicació és zero, un, dos, i tres. 

I així que si vols anar de aquest element al següent element, que, literalment, en el la ment de l'ordinador, només ha d'afegir un. Si vols anar al tercer element, només ha d'afegir un-- següent element, simplement afegir un. No obstant això, en aquesta versió de la història, suposi l'equip està buscant actualment en o per tractar amb el número 100. Com s'arriba a la següent grau en el llibre de qualificacions? 

Vostè ha de prendre 7 passos, que és arbitrari. Per arribar a la següent, cal prendre altres vuit passos per arribar a 15. En altres paraules, no és una distància constant entre els números, i per tant només es necessita la equip més temps és el punt. L'equip ha de buscar a través de la memòria amb la finalitat per trobar el que estàs buscant. 

Així, mentre una matriu tendeix a ser una structure-- ràpida de dades, ja que literalment, pot simplement fer aritmètica simple i obtenir en la qual desitja mitjançant l'addició d'un, instance-- d'una llista enllaçada, se sacrifica aquesta característica. No es pot simplement passar de la primera la segona a tercera a la quarta. Vostè ha de seguir el mapa. Vostè ha de prendre més mesures per arribar a aquests valors, els quals semblaria ser l'addició d'un cost. Així que estem pagant un preu, però el que es la característica que Dan estava buscant aquí? Com és una llista enllaçada pel que sembla, ens permet fer, que va ser l'origen de aquesta història en particular? 

Exactament. Una mida de dinàmica a la mateixa. Podem afegir a aquesta llista. Fins i tot podem reduir la llista, per la qual que només estem utilitzant tanta memòria ja que en realitat volem i per mai estem sobre-el qual es reparteixen. 

Ara acaba de ser molt primmirats, hi ha un cost ocult. Així que no ha de deixar a convèncer que aquest és un compromís convincent. Hi ha un altre cost ocult aquí. El benefici, per ser clar, és que tenim dinamisme. Si vull un altre element, només pot elaborar i posar un nombre en aquest país. I llavors puc vincular amb una imatge aquí, mentre que aquí, de nou, si tinc mi mateix pintat en una cantonada, si alguna cosa més ja està utilitzant la memòria aquí, estic fora de sort. Jo mateix he pintat a la cantonada. 

Però el que és l'ocult costaria en aquesta imatge? No és només la quantitat de temps que es triga per anar des d'aquí fins aquí, que és set passos, llavors vuit passos, que és més d'un. Quin és altra cost ocult? No només el temps. Informació addicional està necessàries per aconseguir aquesta imatge. 

Sí, aquest mapa, aquests petits trossos de paper, com segueixo descrivint-los com. Aquests arrows-- els que no són lliures. Un computer-- saps el que té un ordinador. Compta amb zeros i uns. Si vol representar una fletxa o un mapa o un nombre, es necessita una mica de memòria. Així que l'altre preu que pagar per una llista enllaçada, una informàtica comuna de recursos, és també l'espai. 

I de fet és així, comunament, entre les compensacions en el disseny de l'enginyeria de programari sistemes requereix temps i espai-- són dos dels seus ingredients, dues dels seus ingredients més costosos. Això m'està costant més temps perquè tinc que segueix aquest mapa, Però també em costa més espai perquè he de mantenir aquest mapa voltant. Pel que la esperança, com hem tipus de discutit sobre l'ahir i avui, és que els beneficis seran més grans que els costos. 

Però no hi ha una solució òbvia aquí. Potser és millor-- a la ràpida i bruta, com Kareem va proposar abans els he parlat a tirar de memòria en el problema. Acaba de comprar més memòria, pensar menys estès sobre la solució del problema, i resoldre-ho de una manera més fàcil. I, de fet abans, quan parlem sobre les compensacions, no hi havia espai en equip i l'hora. Era temps de desenvolupament, la qual cosa és un recurs més. 

Així que de nou, és aquest acte d'equilibri tractant de decidir quina d'aquestes coses ¿Està disposat a gastar? Què és el menys costós? Que produeix els millors resultats? Sí? 

En efecte. En aquest cas, si estàs en representació de nombres en el maps-- aquests són cridats en molts idiomes "Punters" o "direccions" - que és el doble d'espai. Això no té per què ser tan dolent com el doble si en aquest moment només estem emmagatzemar nombres. Suposem que s'emmagatzemaven registres dels pacients en un hospital-- pel que els noms de Pierson, números de telèfon, números de seguretat social, metge història. Aquest quadre pot ser molt, molt més gran, en aquest cas un diminut punter, la direcció de la propera element-- que no és un gran problema. És una franja tals costa no importa. Però en aquest cas, sí, és una duplicació. Bona pregunta. 

Anem a parlar d'una vegada poc més concreta. Què és el temps d'execució de cercar aquesta llista? Suposem que es vol buscar a través de tots els graus dels estudiants, i hi ha n graus en aquesta estructura de dades. Aquí, també, podem demanar prestat el vocabulari de l'anterior. Aquesta és una estructura de dades lineal. 

O gran de n és el que es requereix per aconseguir al final d'aquesta estructura de dades, whereas-- i no hem vist això abans-- una matriu que dóna el que s'anomena constant de temps, el que significa un pas o dos passos o 10 steps-- no importa. És un nombre fix. No té res a veure amb la mida de la matriu. I la raó que, de nou, és d'accés aleatori. L'ordinador pot simplement immediatament saltar a una altra ubicació, perquè són tots iguals distància de tota la resta. No hi ha pensament involucrat. Tot bé. Així que si puc, vaig a tractar pintar dos quadres finals. Un molt comú coneguda com una taula hash. Així que per motivar aquesta discussió, m'ho dius a mi pensar sobre com fer això. 

Així que què tal això? Suposem que el problema volem resoldre ara està duent a terme en un dictionary-- de manera que un munt de paraules en anglès o el que sigui. I l'objectiu és ser capaç de respondre preguntes de la forma es tracta d'una paraula? Pel que desitja aplicar un corrector ortogràfic, just com un diccionari física que es pot mirar les coses en. Suposem que jo anés a fer això amb una matriu. Podria fer això. 

I suposem que les paraules són la poma i el plàtan i meló. I no puc pensar en les fruites que comencen amb D., de manera que només estem va a tenir tres fruites. Així que aquesta és una matriu, i estem emmagatzemar totes aquestes paraules en aquest diccionari com una matriu. La pregunta és, llavors, ¿de quina altra es pot emmagatzemar aquesta informació? 

Bé, estic tipus de parany aquí, perquè cadascuna d'aquestes lletres de la paraula és realment un byte individual. Així que si realment volia ser nit-exigent, que realment hauria es divideix això en gran part trossos més petits de la memòria, i podríem fer exactament això. Però anem a executar en el mateix problema que abans. Què passa si, com Merriam Webster o Oxford Té cada any-- afegeixen paraules a la dictionary-- no ho fem necessàriament vol pintar-nos en una cantonada amb una matriu? 

Així que en comptes, potser un enfocament més intel·ligent és posar poma en el seu propi node o caixa, com diríem, plàtan, i llavors aquí tenim meló. I la cadena que aquestes coses juntes. Així que aquesta és la matriu, i aquesta és la llista enllaçada. Si no pot veure bé, només diu "matriu", i això diu "llista". 

Així que tenim la mateixa qüestions exactes com abans, de manera que ara tenim dinamisme a la nostra llista enllaçada. Però tenim un diccionari bastant lent. Suposem que vull buscar una paraula. Em podria tenir gran O de n passos, perquè la paraula podria ser tot el camí al final de la llista, igual que el meló. I resulta que en la programació, més o menys del Sant Grial de les dades estructures, és una cosa que li dóna constant temps com una matriu però que encara li dóna dinamisme. 

Així podem tenir el millor d'ambdós mons? I, en efecte, hi ha alguna cosa diu la taula hash que li permet fer exactament que, encara que aproximadament. Una taula hash és un columbòfil estructura de dades que ens es pot pensar en com el combinació d'un array-- i vaig a treure, així- i llistes enllaçades que vaig a dibuixar com això aquí. 

I la forma en què aquesta cosa obres és com segueix. Si això ara-- el hash table-- és la tercera estructura de dades, i vull emmagatzemar paraules d'aquest, no ho sé voler simplement emmagatzemar tota la paraules esquena amb esquena amb esquena amb esquena. Vull aprofitar alguna peça d'informació sobre les paraules que li permetrà jo entenc on és més ràpid. 

Per tant, donada la poma paraules i el plàtan i meló, Vaig triar deliberadament aquestes paraules. Per què? El que és una espècie de, fonamentalment, diferent en els tres? Què és el que és obvi? Comencen amb diferents lletres. 

Així que ja saben què? En lloc de posar totes les meves paraules el mateix cub, per així dir-ho, com en una llista molt llarga, ¿per què no fer Jo, almenys, tracte a una optimització i fer les meves llistes 1/26 sempre. Una optimització convincent podria ser per què no fer Jo-- en inserir una paraula en aquesta estructura de dades, en la memòria de l'ordinador, per què No vaig posar totes les paraules 'a' aquí, totes les paraules 'b' aquí, i totes les paraules 'c' aquí? Així que això acaba posant una poma aquí, plàtan aquí, meló aquí, i així successivament. 

I si tinc un addicional paraula com- quin és l'altra? Poma, plàtan, pera. Algú pensa d'una fruita que comença amb A, B, o C? Blueberry-- perfecta. Això va a acabar aquí. I pel que sembla que tenen una marginalment millor solució, perquè ara si vull per buscar la poma, em primer-- no m'acaba de busseig en el meu estructura de dades. No em submergeixo en la memòria del meu ordinador. La primera vegada que miro la primera lletra. 

I això és el que un ordinador científic diria. Vostè comprovació aleatòria, l'estructura de dades. Vostè pren la seva entrada, que al seu aquest cas és una paraula com la poma. Vostè ho analitza, mirant la primera lletra en aquest cas, hash d'aquesta manera. Hashing mitjançant el qual és un terme general preses alguna cosa com a entrada i produir una sortida. I la sortida en aquest cas és la ubicació que voleu cercar, el primer ubicació, segona ubicació, tercer. Així que l'entrada és de poma, la sortida és primer. L'entrada és plàtan, la sortida ha de ser segon. L'entrada és meló, la sortida ha de ser tercer. L'entrada és el nabiu, la sortida ha de tornar a ser segon. I això és el que l'ajuda a prendre accessos directes a través de la memòria per tal d'arribar a les paraules o les dades de manera més eficaç. 

Ara bé, això redueix el nostre temps potencialment per tant com un de cada 26, perquè si s'assumeix que vostè tenir tants "a" paraules com "z" paraules com a paraules "q", que no és realment realistic-- vas a tenir biaix en tots certes lletres del alphabet-- però això seria un increment enfocament que permet vostè pugui arribar a dir molt més ràpidament. I en realitat, un sofisticat programa, el Googles del món, la Facebooks del món-- usarien una taula hash per a una gran quantitat de propòsits diferents. Però ells no serien tan ingenus com a tan sols mirar la primera lletra a la poma o un plàtan o pera o el meló, ja que com es pot veure aquests llistes encara podien fer llarga. 

I així, això encara podria ser una espècie de manera linear-- espècie de lent, de la mateixa manera que amb el gran O de n que hem comentat anteriorment. Així que el que és una veritable bona voluntat taula hash fer-- que tindrà una gamma molt més gran. I va a utilitzar una forma molt més sofisticada funció hash, de manera que no es limita a considerar la "a". Potser es veu en "a-p-p-l-i" i d'alguna manera converteix aquestes cinc lletres en la ubicació on poma ha de ser emmagatzemat. Estem ingènuament utilitzant la lletra "a" sol, perquè és agradable i senzilla. 

Però una taula hash, en Al final, es pot pensar de com una combinació de una matriu, cada un dels quals té una llista enllaçada que, idealment, ha de ser el més curt possible. I això no és una solució òbvia. De fet, gran part de la sintonització fina que continua sota de la caputxa quan la implementació d'aquest tipus de estructures de dades sofisticades és el que és el dret longitud de la matriu? Quina és la funció hash correcte? Com es pot emmagatzemar en la memòria les coses? 

Però adonar-se del ràpid aquest tipus de discussió escalada, o bé fins al moment que és una espècie de sobre el cap d'un en aquest punt, que està bé. Però comencem, memòria, amb veritat alguna cosa de baix nivell i l'electrònica. I pel que aquest nou és aquest el tema de l'abstracció, on una vegada que comenci a prendre per concedida, OK, he it-- vaig arribar allà és memòria física, OK, ho va aconseguir, cada ubicació física té una adreça, OK, el tinc, puc representar aquestes adreces com arrows-- pot començar molt ràpidament a tenir converses més sofisticades que al final sembla que són el que ens per resoldre problemes com la recerca i classificar de manera més eficaç. I pot estar segur, també- perquè crec que això és la més profunda que hem anat en alguna d'aquests temes CS proper-- que hem fet en un dia i mig en aquest apuntar el que normalment podria fer més de el curs de vuit setmanes en un semestre. 

Qualsevol pregunta sobre aquests? No? Tot bé. Bé, per què no ens aturem allà, començar el dinar uns minuts abans, reprendre en tan sols al voltant d'una hora? I vaig a romandre durant una mica amb preguntes. A continuació, vaig a haver d'anar prendre un parell de trucades si això està bé. Vaig al seu torn una mica de música en el interí, però el dinar ha de ser la volta de la cantonada.