DAVID Malan: Molt bé. Així que aquest és CS50, i això és ara l'inici de la setmana tres. Així que, fins ara, no tenim estat escrivint programes en C aquesta mirada una mica alguna cosa com això aquí. Així que tenim un parell de agut inclou a la part superior. Tenim int, principal, nul, i llavors hi ha alguna cosa que fer en el centre, algun fragment de codi dins d'aquesta funció. Però clau ha estat el fet que que hem estat dient buit aquí. Així buit, tot aquest temps, especifica que aquest programa, quan s'executa, només es pot executar a través del seu nom. No es pot escriure qualsevol altra paraula o números després del nom del programa quan executar-lo. Així, per exemple, si el programa eren compilat en un arxiu anomenat hola, vostè podria fer ./hola, però això és tot. 

L'única manera que vostè podria aportacions a aquest programa és cridant a una funció. Per exemple, ¿quina funció hem estat utilitzant fins ara per obtenir la entrada de l'usuari? 

AUDIÈNCIA: Obtenir cadena. DAVID Malan: Per obtenir la seqüència, o aconseguir int, o has vist a altres, encara que no els ha utilitzat encara, com aconseguir molt, molt i similars. Però suposem que realment vulgui començar escriure programes que són poc més versàtil, i, francament, una mica més igual que els comandaments que vostè ha estat rebent, amb sort, una mica acostumat. Com cd espai Dropbox. Això, per descomptat, els canvis seu directori, assumint ets a la casa de John Harvard directori, a la seva carpeta de Dropbox. Mentrestant, una ordre com aquest crea un nou directori anomenat PSet2, ja que és possible que tingui o aviat per fixar un problema de dos. Fer Hola, per descomptat, és una ordre que construeix un programa que es diu hola des d'un fitxer anomenat hola punt c. I en cada un d'aquests casos, ara, hem tingut proporcionar un argument en l'anomenada línia d'ordres, el símbol parpelleja, perquè faci el que sap construir, i així que mkdir sap quina carpeta per crear, i pel que sap cd on vol anar. Però fins ara, seguim dient que la principal, la seva funció per defecte, té una expressió nul dins d'aquests parèntesis, el que significa que no pot tenir cap argument. 

Així que a partir d'avui, el que farem És a dir, anem a començar suport a aquest tipus de coses, fins i tot. De fet, en aquest cas, que es no solen escriure manualment, Fer que ha estat fent això per a nosaltres, no hi ha un, sinó un, dos, tres addicionals cordes després del programa de trucada so metàl · lic. Llavors, com ho aconseguim? 

Bé, a partir d'avui, en els casos en què volem per proporcionar entrada a través de la l'anomenada línia d'ordres, anem a començar a afegir aquí el que està en Yellow-- substitució de buit amb comes int argc cadena argv claudàtor obert claudàtor de tancament. Ara això és interessant per un parell de raons. Un, que deixarà que ens escrivim programes que són una mica més dinàmic. Però, més convincent, que va a obrir ara una conversa sobre què arranjaments pot realment ser utilitzat, de manera que una cadena realment està sota el capó, fins a la setmana que quan vam començar el busseig encara més profund que fa a com la màquina està fent tota aquesta feina coses. Però per ara, anem a dibuixar, potser, una imatge. 

Quan s'escriu un programa amb principal declarada d'aquesta manera, tal que la principal pren dos arguments, 1 int y-- quin tipus de dades és el segon argument? 

AUDIÈNCIA: Array. DAVID Malan: Array. Així que sembla a primera vista com si fos un cadena, però observi els claudàtors. Recordeu l'última vegada que vam introduir la noció d'una matriu. I matrius utilitzen claudàtors en un parell de contextos. És possible utilitzar la plaça suports per a anar en una matriu i obtenir un element en particular, com Suport de 0 o 1 o suport de muntatge 2. Però vam veure, encara que breument, la setmana passada que també utilitzar aquests claudàtors a declarar la mida d'una matriu, si vostè sap per endavant quants sencers o quantes cordes o el que vostè realment volen. Així que resulta que hi ha tercera context aquí que no té els números de l'interior dels claudàtors. Quan s'especifiqui, com ho he fet aquí, el nom d'una cosa així com argv, que és només una forma elegant de dient argument vector, que és una altra forma elegant de dient una sèrie d'arguments, claudàtor obert claudàtor de tancament només vol dir que no ho fa necessàriament saber per endavant el gran la matriu serà, però vostè sap que serà una matriu. Així que si vostè no sap la nombre no ho posis aquí, per obrir el parèntesi claudàtor de tancament vol dir que argv no és una cadena, però una matriu de cadenes. Així sintàcticament, si pensar de nou la setmana passada, és molt similar a dir una mena int edats suport obert, i després alguna cosa després. Llavors, què s'assembla això? Anem a realment fer un dibuix. Així que quan s'executa aquest programa amb Principal havent dos arguments definida a l'interior d'aquests parèntesi, es essencialment tenir almenys dos trossos de la memòria lliurada a vostè sota de la caputxa. Un, com vaig dibuixa com aquest rectangle, es va a cridar argc. I així com un resum ràpid, Quin és el tipus de dades de argc? Així que és un int. Així que un nombre es va anar per torns argc-- que representa el recompte argument. Mentrestant, he dibuixat argv com una matriu. I jo no ho sé quant de temps serà, així que per als propòsits d'avui dot dot dot. Pot ser que aconsegueixi d'una certa extensió. Però m'he imaginat aquí almenys quatre rectangles. Així argv un tros de memòria que emmagatzema cadena cadena cadena dot dot dot, i argc és només un tros de memòria per a un sencer. 

Així que ara, serem una mica més precisos. Si, quan tinc cordes en aquesta matriu, anomenat argv, vull arribar-hi de manera individual, igual que la setmana passada, utilitzarem la notació com argv suport 0 per aconseguir el primer una matriu. Argv suport 1 per obtenir el El segon, i així successivament. La clau aquí és que estem encara 0 indexed-- encara estem explicant des de 0. Així que ara anem a realitat posar alguna cosa en això. Si hagués de compilar un programa anomenat hola des d'un fitxer anomenat hola punt c, i després executo aquest programa amb el punt slash hola, el que fa el meu equip, el meu portàtil, veure com sota de la caputxa el moment em trobo dot slash hola i prem intro? Bé, aquest és potser el que podríem descriure com el contingut de l'ordinador de memòria, o memòria d'accés aleatori RAM--. En altres paraules, l'ordinador, d'alguna manera perquè per art de màgia, posa el número 1 en argc, AKA argcount, i posa literalment la cadena ./hola en argv suport 0. No tinc ni idea, la veritat, el que és en el suport argv 1 o 2 o 3, ja que si l'usuari no té escrit res, a més ./hola, anem a suposar que aquests són valors més probables d'escombraries, per així dir-ho. Aquests fragments de memòria existeix, però no depèn de nosaltres mirar-los, perquè la argcount és únic. 

Ara, per la seva banda, si escriure executar un altre programa, cd, que és més adequadament una ordre, en el seu parpellejar espai cd prompt-- Dropbox-- quan corro que, efectivament, quan s'executa el programa de cd, argc, dins de la memòria del meu ordinador, és per el més breu segon el número 2. I després argv suport o té cd, suport argv 1 té Dropbox, i després, per descomptat, la comanda completa, de manera que tot això de memòria essencialment es va i s'utilitza per a una altra cosa. I és per això que dic només una fracció de segon. 

Mentrestant, si fem PSet2 mkdir, la imatge es veu gairebé el mateix, però amb diferents cordes dins argv. Si ho faig tauler Clang hola hola punt c, la mateixa idea. Més coses s'omple per argv i argc, per descomptat, és 4. Així, en altres paraules, tot i que aquesta matriu podria dot dot dot, d'alguna longitud variable, per així dir-ho, que sempre sap on és el final de la mateixa és, perquè argc dirà vostè en quin punt vostè ha de parar mirant als elements en argv. Vostè només pot mirar a les quatre En total en aquest cas. 

Així que ara anem a fer una ullada a, potser, un programa simple. Un que només diu hola per a algú com Zamyla. Així que jo reclam que vaig a escriure un programa en un moment a través de la qual jo podia fer ./hola espai Zamyla, i després vull el meu programa per imprimir alguna cosa super-simple com "hola, Zamyla." Ara bé, en el passat hem fet servir getString. Així que en el passat, fins i tot si vostè és nou en la programació, les probabilitats són que vostè podria preparar una programa que utilitza getString i després utilitza printf saludar Zamyla. Però no usem GetString aquest moment. Déjame en lloc d'entrar a la Appliant i no incloure estàndard I O dot h. Permetin-me també incloc CS50 punt h. Ara int main, i ara estic no farà buit en l'actualitat. En el seu lloc, faré int argc argv cadena claudàtor obert claudàtor de tancament, sense especificar un nombre. I ara aquí està la meva cridat a fer. Què faré ara és que estic farem una mica d'un salt de la fe, Vaig a assumir que l'usuari d' va a utilitzar aquest programa correctament, i simplement vaig a fer printf hola,% sn. Així que res de nou allà. Però vull ara posar qualsevol paraula del usuari escriu després del nom del programa. Així que si ho faig ./hola espai Zamyla, I vulgui alguna manera l'accés mitjançant programació cometes "Zamyla." així que pot entrar en el meu argument vector, la meva matriu de cadenes, i si la comanda, de nou, era ./hola espai Zamyla, quin nombre és el que vull per posar en argv aquí? AUDIÈNCIA: 1. DAVID Malan: 1, perquè Suport de 0 resulta serà la El nom del programa, com vam veure. Així suport 1 és la primera paraula que jo, l'usuari, ha escrit. Vaig a seguir endavant i salvar aquest. Vaig a anar a la carpeta on he posat aquest fitxer. Jo faré que hola març. OK Comp IO. ./hola Zamyla Intro. Què vaig fer malament? Estava atrapat per sorpresa a mi mateix per un moment allà. Què vaig fer malament? 

AUDIÈNCIA: Nom. 

DAVID Malan: L'arxiu de en realitat es diu hello3.c. I ho vaig fer només per consistència, perquè hem tingut de hola.c al passat en el codi en línia. Així que anem a resoldre aquest ./hola suport de tauler 3 Zamyla. Intro. I ara tenim hola, Zamyla. Mentrestant, puc canviar això a ser Rob, o en realitat qualsevol altra paraula. 

Però considerarem un cas cantonada. Què podria esperar que succeirà si Jo no escric el nom de ningú en absolut? 

AUDIÈNCIA: Error. 

DAVID Malan: un error d'algun tipus, potser. Anem a veure. Intro. Null. Així printf és ser realment una mica de protecció de nosaltres aquí, i literalment la impressió parin obertes null, però les coses encara pitjors poden succeir. I només per demostrar cosa que absolutament no ha de fer, anirem a aquí i començar a jugar. ¿Cert? Si jo sé que la imatge de memòria és essencialment això, argv suport 1 té Zamyla, argv suport té 0 ./hola, o ./hola-3. El que està en el suport 2? Així que puc respondre a aquesta qüestionar, oi? Jo només puc canviar l'1 a un 2. Ara puc tornar a compilar hola 3, ./hello3 Anem a apropar i prem enter. Vaja. Sense cometes. Interessant. Així que és una mena de fresc a veure què més hi ha per aquí. 

Llavors, què més hi ha a l'interior del meu portàtil? Salvem amb suport 3. Fer hello3, ./hola-3. Curiós. I ara anem a arribar realment bold-- 50. Així que això és realment busseig profund a la memòria del meu ordinador. 50 índexs en. Així que hola març ./hola-3. Curiós. Molt bé, ara estic sol aconseguirà imprudent. Anem a 5000. Bé. Així que permetin-me recompilar. Fer hello3, ./hola-3. Okay. Ara alguns de vostès, no podria ser una bombeta d'apagar. Quants de vostès tenen vist aquest missatge abans? Okay. Així que, per què? 

Probabilitats són-- i hi ha diferents coses que poden causar aquest, i és evident que està en bona company-- tenim clarament causat el que s'anomena un error de segmentació. I conte llarg per avui, han tocat un segment de memòria que no hauria de tenir. Quan un segment que només significa un tros de la memòria que no hauria de tenir. Ara, l'equip garanteix que si jo executar ./helloZamyla que puc tocar argv ser suport 0 i argv suport 1. Però argc és el valor 2, que vol dir que sóc només allowed-- és una espècie d'honor system-- a tocar suport 0 i el suport 1. Si vaig més lluny, hi ha absolutament serà la memòria allà. El meu RAM existeix físicament a l'ordinador. Però, ¿qui sap el que hi ha allà? De fet, m'estic quedant múltiple programes al mateix temps. Jo podria haver seen-- si jo no estigués fent això al Appliant però en el meu Mac o PC-- que podria tenir vist el contingut d'un correu electrònic. Jo podria haver vist un instant missatge que he enviat recentment. Qualsevol cosa que pugui ser persistent al voltant en la memòria podria haver estat visitada per mitjà de aquesta arbitrària notació de claudàtors. O, pitjor encara, és possible que tingui trobat un dels meus contrasenyes que jo vaig escriure fa poc en què un programa havia emmagatzemat en la memòria per tal de em autenticar i llavors només una mica deixat en la memòria RAM fins que vaig deixar d'aquest programa. 

I de fet, aquesta és una de el perill i un dels poders de la utilització d'un llenguatge com C. Vostè té accés sense restriccions a la totalitat dels continguts de la memòria d'un programa, i el que els nois dolents poden fins i tot fer en aquests casos-- sobretot quan ens arribar a la programació web cap al final del semestre, anem a revisar aquest topic-- es treu voltant, potencialment, a algú és l'ordinador de memòria i trobar coses tan curioses com vam veure allà. O el que és pitjor encara, les contrasenyes que es o ella pot llavors utilitzar per fer coses dolentes. 

Així que està clar que no hauria d'haver fet això, perquè les coses estranyes comencen a succeir. De fet, aquest és un programa d'estavellar. Això seria l'equivalent de Mac OS o Windows una finestra de programa simplement desaparèixer. S'ha produït un error inesperat. A l'entorn de línia d'ordres veiem alguna cosa com això. Però és per això, és que estic simplement tocant memòria que no em pertany. 

Així que anem a defensar en contra d'aquest 1 mica d'una manera diferent examinat aquest programa aquí. Així, de nou, l'esquelet que vam veure abans els vaig parlar i jo he destacat aquest cop int. I tot aquest temps principal té efectivament retornat un conjunt. Tot i que en la major part de la nostra conferència exemples que hem ni una sola vegada utilitzem tornar res en main. Només escrivim printf prop claudàtor i això és tot. Però de forma gratuïta, el que la compilador estat fent per tu, efectivament, torna 0 per a vostè. Activa sortir-- i que és una mica counterintuitive-- que 0 és bona. Això no vol dir falsa per se. 0 és bo, i qualsevol que no sigui 0 valor, el món ha decidit, pot significar un error. Així que si alguna vegada ha embrutat alguna cosa en el seu equip, o un programa acaba de morir en vostè i vostè ha aconseguit alguna finestra errònia a la pantalla, error que diu negatiu 49 o error 23-- alguns value-- aparentment arbitrari que és pel fet que un programador ha modificable un valor negatiu com 49 o positiu 23 per representar qualsevol nombre, m'atreveixo a dir, de 4 mil milions d'coses possibles que podria anar malament en un programa. 

Llavors, ¿com podria jo prendre avantatge d'això jo mateix? Bé, deixa obro un programa que vaig escriure amb antelació, i furgar en línia anomenat hola 4. I és gairebé idèntic, llevat que La seva aconseguit una mica de comprovació d'errors. En aquest cas, he declarat de nou principal com prendre dos arguments, però aquesta vegada, en la línia 17, la notificació Estic fent una mica d'una comprovació de validesa. M'estic assegurant que argc és igual és igual a 2. Perquè si ho és, que significa que pot de manera segura tocar no només el suport 0, però el suport 1. I segueixo endavant i imprimir, en aquest cas, Zamyla o Rob o qualsevol paraula que he escrit fora. I ara acaba d'arribar una mica més adequada, Em vaig a tornar de forma explícita 0 per significar que tot està bé. Res dolent va succeir. 

Però per convenció, que vaig a retorna 1, o francament qualsevol valor que no sigui 0, si alguna cosa va sortir malament. Ara l'usuari no va a realment adonar del que està passant. De fet si entro en aquest directori, ens acostem i què fem hola 4, ./hola-4 Zamyla comporta com espero. Però si en canvi no ho escric res, res sembla succeir, però que no es desplomi. I si en lloc de fer alguna cosa com Rob és un supervisor en l'intercanvi d'Thayer-- informació arbitrària. Però avís, argv 1, 2, 3, 4, i 5 Ara ha d'existir en la memòria. Això, també, no ho és el meu programa d'espera, perquè jo he comprovat si argc és igual als iguals 2 o no. Així que ara estic defensant en contra d'aquest. 

Ara, en un apart, que la programmer-- o més aviat que la users-- Mai veiem que 0 o 1, però utilitzant un eina anomenada depurador, o altres eines, com veurem abans de llarg, que el programador en realitat pot veure el que podria ser va malament dins del seu programa. 

Així, qualsevol pregunta sobre argc? Sí. 

AUDIÈNCIA: He vist on no han tingut el caràcter, [inaudible] acaba de dir estrella cadena d, com caràcter coma asterisc. Són equivalents aquí? 

DAVID Malan: Són. Així que la pregunta és, vostè té programes de tant en tant es veuen com aquest que no ho fan dir suport argv cadena però en lloc de dir alguna cosa com a suport de carbó argv estrelles. I hi ha fins i tot una altra variants que es poden veure. De fet, són equivalents. Per ara, tenim aquests tipus de rodes d'entrenament en la forma de cadena al CS50 biblioteca, però en poc més d'una setmana o pel que anem a eliminar aquesta obstrucció per complet i, de fet mirar el que el carbó i l'estrella són, i com aquells es refereixen a la memòria representació més general. Així que anem a tornar a això. 

Altres preguntes sobre la nostra argv o argc? Sí. AUDIÈNCIA: Per què tornar un error [inaudible]? DAVID Malan: Per què ho va fer retornarà un error only-- oh! En el cas anterior, quan van ser barallar una mica amb la memòria, ¿Per què només es retorna un error quan realment vaig escriure un gran nombre? Resposta curta és, vam tenir sort. En termes generals, un ordinador assigna memòria en trossos, i em va donar un tros bastant gran que Em vaig allunyar, sense ser notat, de tocar el suport 2, suport 3, suport de 50, però quan em vaig empènyer la meva sort, em va anar més enllà de la límits de la quantitat de memòria el sistema operatiu m'havia donat. I va ser llavors quan es pres mesures dràstiques i va dir no. Segmentació d'error. Sí. 

AUDIÈNCIA: Com funciona l'ordinador conèixer el valor de argc? 

DAVID Malan: Com funciona el equip sap el valor de argc? Quan s'executa un programa, aquest programa, per la naturalesa de la petició de parpellejar, se li passa el conjunt de paraules que van ser teclejades en l'indicador, que va ser teclejat a l'indicador. I el que és el seu funcionament sistema que essencialment omple els arguments dels principals per a vostè. Així que aquest és un dels serveis que vostè aconsegueix, més o menys en secret sota de la caputxa de un sistema operatiu. Altres preguntes? Sí. 

AUDIÈNCIA: Què significa bolcat de memòria? DAVID Malan: Què significa bolcat de memòria? Així que aquesta és una bona pregunta. I m'ho dius a mi tornar a aquest directori aquí. I t'adonaràs que Tinc un arxiu nou allà. Ha fet crida nucli, i és en realitat sol ser un arxiu de mida decent. Això és essencialment una instantània de el contingut de la memòria del meu programa o RAM quan es va estavellar. I això serà útil, potencialment, diagnòstica, una vegada que es parla en una conferència futura i la secció sobre la depuració, perquè en realitat es pot fer el equivalent a una autòpsia digitals en aquest arxiu per ajudar a determinar el que va fer malament en el seu programa. Sí. 

AUDIÈNCIA: És argc una ordre a en si, o podeu nomenar que res? 

DAVID Malan: Bona pregunta. És argc una ordre en si mateix, o pots cridar alguna cosa? Definitivament no és una ordre. Es tracta simplement d'una variable d' nom o el nom d'un argument, i tan absolutament que podria anomenar aquest foo, podríem anomenar a aquest bar, que tendeixen ser el go-a les paraules que un ordinador científic va. Però per convenció, utilitzem argc i argv. Però això és només un ésser humà convenció, res més. Bé. Així resulta, he estat comptant una mica d'un lie-- blanc i francament, en el futur, vostè veurà hem estat dient a altres mentides piadoses. Però per ara, anem per pelar un d'aquests. En aquest cas aquí quan prèviament córrer un programa com ./hola o ./hola-3 Zamyla, vam tenir el contingut del meu la memòria de l'ordinador buscant més o menys igual això. Però recordem el que una cadena és. Què vam dir fa una setmana el que un cadena en realitat està sota el capó? AUDIÈNCIA: Arsenal de caràcters. DAVID Malan: És una matriu de caràcters, no? Així que pot ser que tinguem una sèrie de cadenes, però, al seu torn, una cadena és una sèrie de caràcters. Així que si jo realment vull ser anal quan dibuix aquesta imatge, Realment hauria d'estar dibuixant una mica de la mateixa família, pel que en cada un d'aquests índexs de la meva matriu argv, no és en si mateix una cadena completa que sí que està en una matriu. I ara la mentida blanca li estem dient avui és que la imatge no mirar com aquest. De fet, les petites places són normalment fora dels grans rectangles Ja està. Però anem a tornar a que en poc temps. Però això és ./hola barra invertida 0, que sent el caràcter especial que demarca el final d'una cadena, i tenim un altre després El nom de Zamyla. Així que què vol dir això? 

Bé, deixa anar endavant i obrir altres dos exemples que estan disponibles en línia. Un es diu argv1.c i l'altre és argv2. És un programa súper simple que és diferent dels programes anteriors que ara estic fent servir argc i argv aquí. I ara m'estic integrant amb un bucle for en la línia 18, des de i = 0 en un màxim de argc. I què faré amb aquesta línia de codi en aquesta llista? En Anglès. Això demostra òbviament ús de argc. Però en anglès, el que fa de fer si em quedo aquest programa? Sí? 

AUDIÈNCIA: Es va a imprimir el seu pantalla tantes vegades com vulguis. DAVID Malan: Exactament. Així que el que sigui que paraules escrigui en l'indicador, és anar a regurgitar ells em un per línia. Així que seguirem endavant i fer això. Deixa anar al meu directori fer i fan ./argv1 argv1. I ara, anem a mantenir simple. Anem a fer res al principi. Ho va fer imprimir una cosa, i això és de fet el nom del programa, perquè això és en suport 0. Si ara dic foo, que farà els dos, i si dic foo bar, que dirà aquestes tres coses. Això sí que és una cosa interessant, potser. Però recordar que argv és una matriu de cadenes, però una cadena és una sèrie de caràcters, perquè puguem prendre les coses a un nivell superior i aplicar aquest bàsica lògica i fer que el codi que es veu una mica més críptic, cal reconèixer-ho. Però al tenir un imbricada bucle, una cosa semblant al que es pot recordar de Mario, per exemple, si ho va fer d'aquesta manera. 

Així que ara noto a la línia 19, que sóc de nou la iteració en els meus arguments, des de 0 fins a argc. I ara en línia 21-- estic demanar prestat un truc d'última setmana-- Estic comprovant el que és la longitud del suport argv i. Estic emmagatzemant la resposta en el núm. I llavors estic integrant des j en fins n, on j s'inicialitza a 0. Així, la convenció per al recompte. Una vegada que hagis utilitzat i, si vostè té un bucle niat, no es pot usar i de nou, en cas contrari et Clobber, potencialment, el valor fora del bucle intern. Així que estic fent servir j per convenció. Podríem utilitzar k. Si vostè té més de k, és probable que tenir massa d'implantació, en general. Però ara, notar la meva printf línia és lleugerament diferent. No estic imprimint% s, estic impressió% c, que, per descomptat, és un marcador de posició per a un char. 

I ara noti aquesta sintaxi. Nou. Nosaltres no hem vist abans. Però lògicament, això només significa obtenir la cadena i-èsim en argv i obtenir el jth què? AUDIÈNCIA: Caràcter. DAVID Malan: Personatge en aquesta cadena. Així mitjançant l'ús de claudàtors seguit de claudàtors, aquest és el busseig primer en cadenes de argv, i després el segon claudàtors amb j és submergir-se en els personatges de aquesta cadena en particular a argv. I llavors, només per si de cas, Estic imprimint una nova línia aquí. Així que ara em deixis anar endavant i obrir una finestra una mica més gran pel que podem veure això en acció. Déjame anar a aquesta carpeta. I ara el que argv 2-- whoops-- fer argv-2, ./argv 2. Intro. I és una mica difícil llegir verticalment, però això és de fet el nom de la programa, seguit per una línia en blanc. Ara vaig a seguir endavant i fer foo. De la mateixa manera difícil de llegir, però és de fet imprimir un caràcter per línia. I si ho faig bar, ara és impressió dels línia per línia. Així que el menjar per emportar aquí no és tant que, wow, mira aquest nou truc on es pot obtenir en els continguts de caràcters específics d'una matriu, sinó més aviat com ho estem tenint aquests bàsics idees com la indexació en una matriu, i després la indexació en un matriu que estava en aquesta matriu, i simplement aplicar les mateixes idees a exemples lleugerament més sofisticats. Però els fonaments realment no tenen canviat, fins i tot des de la setmana passada. 

Ara bé, això és una cosa puntual, que, recordem, en la setmana zero juguem amb un llibre telèfon com aquest. I encara que això és òbviament peces físiques de paper, vostè pot tipus de pensar un directori telefònic com una matriu. Certament, si anés a reimplementar aquestes peces aquestes peces de paper en un ordinador, probablement vostè utilitzaria alguna cosa com una matriu per emmagatzemar totes les noms i números de la A fins al final a la Z. Així que això és bo, perquè ens permet una oportunitat, potser, a considerar com podria realment posar en pràctica una cosa així. Igual que amb una sèrie de portes aquí. Així que si jo could-- en necessitem un voluntari per venir a endavant. Anem a veure. Un rostre desconegut potser, cara desconeguda, potser. Què tal en taronja? Aquí. Camisa taronja, anem a dalt. 

Seguirem endavant ara i moviment aquestes portes a un costat, moure'ls fora del camí per un moment. Quin és el teu nom? 

AJAY: 

DAVID Malan: Ajay. David. Encantada de conèixer-te. Bé. Així que tenim darrere d'aquests sis portes digitalment a la screen-- o, millor dit, set portes al screen-- un munt de nombres. I jo li he dit res en advance-- acord? AJAY: Res per endavant. DAVID Malan: Tot el que vull que facis ara és trobar per a mi, i per a nosaltres, Realment, el número 50, un pas a la vegada. 

AJAY: Nombre 50? 

DAVID Malan: El número 50. I vostè pot revelar el que hi ha darrere de cadascuna d'aquestes portes simplement tocant amb un dit. Maleïda sigui. [Rialles] 

[Aplaudiments] 

Molt ben fet. Okay. Tenim un regal preciós premi per a vostè aquí. La seva selecció de pel · lícules que discutit la setmana passada. 

AJAY: Oh, home. Oh, mai he vist Spaceballs. 

DAVID Malan: Spaceballs. Bé. Així que aguanta només un moment. Com-- fem que això 1 moment-- ensenyable com va ser el procés de trobar el número 50? AJAY: Vaig triar a l'atzar. DAVID Malan: Així que vostè va triar atzar i vam tenir sort. AJAY: Sí. DAVID Malan: OK. Excel · lent. Així que ara, no tenia tingut sort, què més podria haver passat darrere d'aquestes portes? Així que si segueixo endavant i revelar aquests nombres aquí, el que realment són en ordre aleatori. I el millor que podria tenir fet, francament, és per, en última instància, en el pitjor dels casos, la comprovació de tots ells. Així que tens súper afortunat, que no és el que diríem un algorisme. Sí, felicitats. Però ara let's-- humor jo, si pogués. Anem a anar a aquesta fitxa aquí. I aquí estan els números en clar el que sembla ser un ordre aleatori, i que eren. Però ara si en lloc reclamació que darrere d'aquestes portes són nombres que s'ordenen. L'objectiu ara és també nosaltres trobar el número 50. Però fer-ho algorítmicament, i dir-nos com va en això. I si ho troba, es manté la pel · lícula. No ho trobes, t'ho tornaré. AJAY: Així que vaig a comprovar els extrems primer, per determinar si ha-- [Riures i aplaudiments] DAVID Malan: Aquí tens. Fem una ullada a un dels predecessors de Ajay, Siguin, que no va ser tan afortunat. Acceptar, pel que la seva tasca aquí, Siguin, és el següent. M'he amagat darrere d'aquests portes del número set, però amagat en alguna d'aquestes portes així són altres números no negatius. I el seu objectiu és pensar en aquest fila superior dels nombres com només una matriu. Estem a només una seqüència de peces de paper amb números darrere d'ells. I el seu objectiu és, només amb la part superior array aquí, em trobar el número set. I estem llavors anem a criticar com es van fent sobre ell. Trobi'ns el número set, si us plau. No 5, 19, 13. No és una pregunta capciosa. 1. En aquest punt, la seva puntuació no és molt bo, perquè així pugui seguir endavant. 3. Endavant. Francament, no puc evitar preguntar-me el que estàs tan sols pensar. 

SIGUIN: Puc prendre de només la fila superior. DAVID Malan: Només la fila superior. Així que tens tres esquerra. Així que trobar 7. 

[EXCLAMACIONS SUGGERIMENTS] Així doncs, tant dels que eren increïbles per raons molt diferents. Així que aquí és on ens deixem fa un moment, i la idea clau aquí Van ser aquestes portes tenien nombres darrere d'ells que es van ordenar, l'ideal menjar per emportar per el qual és que es pot fer fonamentalment millor en aquest segon exemple-- i, de fet, això era de Sean primer intent amb nombres aleatoris així com abans-- però tan aviat ja que aquests nombres estan ordenats, igual que la guia telefònica, ¿Què es pot òbviament fer? O com es pot aprofitar aquest coneixement? Sí. 

AUDIÈNCIA: Vostè va a mig camí [inaudible]. DAVID Malan: Si. Exactament. Així instint inicial d'Ajay era per comprovar els extrems, pel que recordo, i després ens tipus d'acabat l'exemple ràpidament. Però si comencem a fer això més metòdicament al llarg d'aquestes línies, però partint potser en el mitjà, ja que estan ordenats, tan aviat com ens revelem la número 16, per tant, sabes-- i farem exactament això-- ens per tant, saber que el 50, en el cas d'avui, ha de ser a la dreta. Així que igual que en la setmana zero quan vam trencar la guia telefònica a la meitat i va llançar la meitat de la problema de distància, la mateixa idea aquí. Podem llançar aquest mitjà que el problema desaparegui. I probablement el que podria fer algorítmicament, un cop heu escoltat que el 50 ha de ser a la dreta, si és en qualsevol lloc, és provar allà, al mig de les portes restants. Per descomptat, 50 és més gran el 42, pel que podem tirar això restant trimestre del problema de distància, i, finalment, identificar alguna cosa com 50. Però igual que amb la guia telefònica, aquests nombres se'ls va donar a nosaltres ja en forma ordenada, el que ens deixa amb la pregunta, com fer les coses en ordre ordenats? I, francament, ¿a quin cost? Una cosa és ser lliurar la guia telefònica i després impressionar als teus amics mitjançant la recerca de un nombre de telèfon molt ràpid, oi? Esquinçant 32 pàgines per trobar una persona de cada 4 mil milions de pàgines, vam dir era un exemple extrem. Però, quant de temps li va prendre a Verizon per ordenar que guia telefònica? Quant de temps ens va prendre per ordenar aquests set números? Aquesta és una pregunta que ens hem fins ara ignorat completament. 

Així que anem a respondre a aquesta pregunta ara. I tots estem de pel · lícules ara, però sí tenim algunes boles d'estrès. Si, per exemple, vuit voluntaris no li importaria acompanyar-nos fins aquí? Seguirem endavant i fer, què tal vostès quatre, tres de vostès aquí? Obtenir algunes cares noves. I els quatre de vostès allà? I ara-- deixar no de biaix aquí-- i número vuit d'aquí al final. Anem amunt. Bé. Així que el que tenim aquí per cada un de vosaltres és un nombre. Si vol anar Endavant, pren aquest número. Quin és el teu nom? 

Artie: Artie. 

DAVID Malan: Artie, està bé. Ets el número 1. 

AMIN: Amin. DAVID Malan: Amin. David. Ets el número 2. I seguir endavant, com em lliuro que els fulls de paper, alinear vosaltres mateixos davant de la música es troba en el mateix ordre com allà dalt. 

ANDY: Hola, Andy. 

DAVID Malan: Andy, és bo veure't. Número 3. 

JACOB: Jacob. 

DAVID Malan: Jacob, número 4. Benvingut a bord. GRANT: Grant. DAVID Malan: Grant. Número 5. 

ALANNA: Alanna. 

DAVID Malan: Alanna, número 6. 

FRANCES: Frances. DAVID Malan: Frances, número 7. I? 

RACHEL: Rachel. 

DAVID Malan: Rachel, número 8. Bé. Vagi per davant i s'aconsegueix en aquest ordre. Permetin-me posar un romanent faristol al seu lloc. On necessita un estand? Okay. Vagi per davant i només cal posar els números on el públic pot veure en, el faristol cap a fora. I és d'esperar, el nostre primer comprovació de validesa aquí-- 4, 2, 6. Oh-oh. Espera un minut. No tenim agost 1. Necessito desallotjar del l'exemple d'alguna manera. No No, això està bé. Anem a veure. Podem fer això. Col·locar. Això és. Correcta. Bé. Així doncs, ara tenim 8, 1, 3 7, 5. Okay. Excel · lent. 

Així que la pregunta en qüestió és, en quin cost, i per mitjà de quin mètode, podem realment ordenar aquests números aquí perquè puguem tipus de treball cap enrere, en última instància, i decide-- és realment impressionant, és realment eficaç, que puc dividir i conquerir una guia telefònica? És realment eficient que Puc dividir i conquerir aquestes peces digitals de paper al tauler, si potser ens costarà un fortuna en el temps o els cicles d'energia o de CPU per aconseguir realment les nostres dades en certa manera ordenada? Així que anem a aquesta pregunta. 

Així que per començar, aquests nombres són en més o menys a l'atzar, i jo vaig a proposar un algorisme o procés pel qual podem classificar aquestes persones. Vaig a abordar aquesta força ingènuament. I vaig a reconèixer que és una espècie d'un munt per a mi per embolicar la meva ment al voltant de la dades sencers estableixen alhora. Però saps què? Vaig a fer una mica de correccions marginals molt simples. 4 i 2 són fora de servei, si el objectiu és passar d'1 a un màxim de 8. Així que ja saps què? Vaig a haver de nois intercanvien, si canvia físicament i posicions seus trossos de paper. Ara 4 i 6, aquests són en ordre. Vaig a deixar als ser. 6 i 8, els que estan en ordre. L'anar a deixar-los ser. 8 and1, fora d'ordre. Si vostès dos no li importaria intercanvi. Ara 8 i 3, si vostès poguessin intercanviar. 8 i 7, si vostès poguessin intercanviar. I 8 i 5, si vostès poguessin intercanviar. 

Ara, estic fet? No, òbviament no. Però he pres la situació millor, oi? Quin era el teu nom, número 8? 

RACHEL: Rachel. DAVID Malan: Així que Rachel té efectivament bombollejava bastant lluny, tot el camí fins al final de la meva sèrie de nombres aquí. I així, aquest problema és una espècie de resoldre. Ara, clarament, 2 encara ha de moure una mica, i 4 i 6 i 1. Però em sembla que han aconseguit una mica més a prop de la solució. Així que anem a aplicar aquest mateix heurística ingènua de nou. 2 i 4, a D'acord. 4 i 6, a D'acord. 6 i 1, mm-mm. D'intercanvi Let. 6 i 3, mm-mm. D'intercanvi Let. 6 i 7 està bé. 7 i 5, doncs no. D'intercanvi Let. I ara 7 i 8. I quin és el teu nom? FRANCES: Frances. DAVID Malan: Frances. Així que ara és Frances, fins i tot en una millor posició, perquè ara 7 i 8 es bombollejava correctament fins al cim. Així que 2 i 4, a D'acord. 4 i 1, d'intercanvi d'let. 4 i 3, d'intercanvi d'let. 4 i 6, que estàs bé. 6 i 5, d'intercanvi d'let. I ara aquests tipus són bons. Ja gairebé arribem. 2 i 1, fora de servei, de manera que canviar. I ara m'ho dius a mi fer una comprovació de validesa. 2 i 3, 3 i 4, 4 i 5, 5 i 6, 6 i 7, 8. OK, així que hem acabat. 

Però a quin preu em va fer ordenar aquests números aquí? Bé, quants passos va fer que potencialment prendre en ordenar aquestes persones? Bé, anem a tornar a aquesta pregunta. Però, francament, si tens una mica avorrit, això és tipus de revelador en què això no era potser l'algorisme més eficient. I, de fet, francament, estic suant tant més anant i venint. Que no se sentia particularment eficient. Així que anem a intentar alguna cosa més. Si vostès poguessin restablir vosaltres mateixos a aquests vuit valors. Bon treball. 

Fem una ullada digitalment, per només un moment abans d'intentar una altra cosa, al que acaba de succeir. Fins aquí, estàs a punt de veure una visualització d'aquests vuit éssers humans pel qual blau i vermell barres representen els números. La més alta la barra, com més gran és el nombre. Com més curta sigui la barra, com menor sigui el nombre. I el que vas a veure és en ordre aleatori més de vuit d'ells. Vostè va a veure aquestes barres sent ordenat pel mateix algoritme, o conjunt d'instruccions, que que anomenarem d'ara endavant espècie de bombolla. Així que notar, cada segon més o menys, dues barres s'il·luminen en vermell, es comparen per l'ordinador. I llavors, si la gran barra i la petit bar estan fora d'ordre, que estan sent intercanviats per mi. 

Ara bé, això és increïblement tediós al veure això, sens dubte, per molt temps, però noti la takeaway-- grans barres en moviment a la dreta, petites barres en moviment a l'esquerra. Anem a avortar aquest procés i accelerar aquest procés ser molt més ràpid, pel que podem aconseguir un sentit d'alt nivell del que, de fet, una mena de bombolla que està fent. De fet, està bombollejant a la costat dret de la llista, o la matriu, els bars més grans. I per contra, els petits bars són bombollejar el seu camí cap a baix a l'esquerra, encara que a un ritme més ràpid que vam fer prèviament. Per tant, més difícils de veure amb els éssers humans, però visualment això és precisament el que que estava succeint. 

Però anem a tractar d'una manera fonamentalment enfocament diferent ara. Anem a provar un diferent algorisme mitjançant el qual hem de nois comencen a aquests originals posicions, que era aquest ordre aquí. I seguirem endavant ara. I jo vaig a fer alguna cosa encara més simple, oi? En retrospectiva, l'intercanvi de parells de nou i una altra, gairebé una mica intel · ligent. Anem a fer les coses encara més ingènuament, on si vull classificar aquestes persones, m'ho dius a mi seguir buscant per l'element més petit. Així que ara mateix, 4 és el nombre més petit que he vist. Recordaré això. No, 2 és millor, i record. 1 és encara menor. 3, 7, 5. Okay. Un-- quin és el teu nom? 

Artie: Artie. 

DAVID Malan: Artie. Així, Artie, endavant. Jo vaig a sortir de la línia. Si poguessis tornar aquí. I he de fer lloc per a ell. Tenim un punt de decisió aquí. Com podem fer espai per Artie aquí al començament, on el número 1 pertany? 

AUDIÈNCIA: Shift. 

DAVID Malan: OK, ens podria canviar tot el món. Però proposar una optimització. Això se sent una mica molest perquè li pregunti a quatre persones per moure tot el camí. Quina altra cosa podia fer? 

AUDIÈNCIA: Interruptor d'ells. 

DAVID Malan: Interruptor ells. I quin és el teu nom? 

JACOB: Jacob. DAVID Malan: Jacob, es va moure. Molt més eficient només per tenir Llocs d'intercanvi Jacob amb Artie, en lloc de forçar els quatre d'aquestes persones, moltes gràcies, a la seva posició correcta. El millor d'Artie ara, està en la seva posició correcta. Anem a fer això de nou. 2, que és el nombre més petit que he vist. 3, 7, 5. Okay. 2 és sens dubte la més petita. No ha de fer cap treball. Anem a fer-ho de nou. 6. Més petit? 8. Nop. 4? Ooh. Permetin-me recordar abril. 3. Que recordi 3. 7, 5. Menor nombre que he vist en aquest pas és 3. Si vens en endavant. On posarem vostè? I quin és el teu nom? 

ALANNA: Alanna. 

DAVID Malan: Alanna, estem haurà de desallotjar. Però això és més eficient, a només intercanviar dues persones, de tenir diverses persones en realitat eludir acabat. Ara anem a fer això de nou. Vaig a seleccionar 4, així que anem a terme. I qui va a moure? Número 8, és clar. Si ara em trobo amb el número 5, anem a terme. Número 8 quedarà desallotjat de nou. Ara em vaig a trobar el número 6 en el seu lloc. 7 en el seu lloc. 8 en el seu lloc. 

El que acabem de fer ara és cosa que es diu ordenament per selecció, i si visualitzem això, és va a sentir una mica diferent. Seguirem endavant i d'aquesta menú aquí, aquest visualization-- anem a canviar aquest A-- anem, Firefox. Anem a canviar això a la selecció de classificació. I anem a accelerar com abans, i començar la visualització ara. I aquest algorisme té una sensació diferent a ell. A cada iteració, francament, és encara més senzill. Només estic seleccionant l'element més petit. Ara, francament, tinc una mica de sort que temps, en què ho resolt súper ràpid. Els elements van ser a l'atzar. No és, com veurem, finalment, veure, fonamentalment més ràpid. Però anem a veure una tercera i última acostar aquí pel que fa al que està passant. Així que seguirem endavant i restablir nois una última vegada per estar en aquest ordre aquí. 

I ara, me'n vaig a ser una mica més intel · ligent, només per arrodonir els nostres algorismes. Vaig a fer això. Me'n vaig per no anar anada i tornada tant. Francament, estic cansat de tot això de desplaçament. Jo només vaig a prendre el que sóc donat al principi de la llista, i jo vaig a ordenar que llavors i allà. Així que aquí estem. Número 4. Vaig a citar el nombre 4 en una llista ordenada. Fet. Reclam ara, i només per fer això més clar, aquesta part de la cistella està ordenada. És una espècie d'un reclam estúpid, però de fet 4 s'ordena en una llista de mida d'un. Ara, jo vaig a prendre en el número 2. Número 2 Ara estic anant a inserir en el lloc correcte. Llavors, on 2 pertanyen? Òbviament, aquí. Així que endavant i tornar, si poguessis. ¿I per què no s'acaba de prendre la seva música està amb vosaltres en aquesta ocasió. I anem a la força que inseriu en el principi de la llista. Així que una mica més de treball. Vaig haver de moure al voltant de Jacob, i quin és el teu nom? 

AMIN: Amin. 

DAVID Malan: Amin. Però almenys no vaig ser cap enrere i endavant. Només estic prenent les coses a mesura que avanço. Només estic inserint en el lloc correcte. 6, això és realment molt fàcil. Anem a inserir per allà, si només volia passar més lleugerament. Número 8, també és bastant fàcil. Just aquí. Maleïda sigui. Número 1 no podem simplement intercanviar amb Amin aquí, perquè això està passant fer malbé l'ordre. Així que hem de ser una mica més intel · ligent. Així, Artie, si pogués una còpia de seguretat per un moment. Seguirem endavant i canviï ara, a diferència dels algoritmes anteriors, per deixar espai a Artie aquí mateix, al principi. Així que al final del dia, jo sóc una mena de fent el que volia evitar abans. I pel que el meu algorisme és una espècie de revertir, intel · lectual, del que era originalment. Només estic fent el canvi en un punt diferent. Ara estic en el 3. Oh, maleïda sigui. Hem de fer més feina de nou. Així que anem a que empeny cap a fora. Anem a passar 8, 6, 4-- oh OH- i 3 va a anar a la dreta allà. Així que almenys els estalvis lleus aquest moment. 7, no gaire feina per fer. Així que si vols fer esclatar volta, anem a inserir. I, finalment, 5, si vostè voler pop tornar, ens hagi de canviar tu, tu, que, fins a les cinc està en el seu lloc. 

Així que ara a veure això en un alt nivell gràficament, farem aquest algorisme visualització d'una vegada addicional. Així que això que anomenarem ordenació per inserció. Farem només com ràpid, i començar des d'aquí. I és, també, té una sensació diferent. És una espècie de millora i millor, però mai és perfecta fins que entro i suau en aquestes llacunes. Perquè, de nou, només estic prenent el Estic sent donat d'esquerra a dreta. Així que no he tingut tanta sort que tot era perfecte. És per això que vam tenir aquests petits mispositions que fixa el pas del temps. 

Així que tots aquests algoritmes semblen córrer a lleugerament diferents ritmes. De fet, quin diria que és el millor o el més ràpid fins a la data? Ordenament de bombolla, la primera? Selecció espècie, la segona? Tipus d'inserció, la tercera? He sentit algunes classes de selecció. Altres pensaments? 

Així que resulta que tots aquests algoritmes són fonamentalment igual d'eficient que cada altre-- o, per contra, igual que ineficaç com els altres, perquè podem fer fonamentalment millor que els tres d'aquests algoritmes. I això és una mica d'una mentida blanca, també. quan dic tan eficient o com ineficient, això és almenys per super-grans valors de n. Quan tenim només vuit persones aquí, o potser 50 o més barres a la pantalla, t'adonaràs absolutament diferències entre aquests tres algorismes. Però com n, el nombre de persones, o el nombre de nombres, o el nombre de persones al telèfon llibre, o el nombre de pàgines web base de dades de Google es fa més gran i més gran, veurem que els tres d'aquests algorismes són en realitat bastant pobre. I podem fer-ho fonamentalment millor que això. 

Anem a fer una ullada, finalment, el que aquests algorismes poden sonar com a la context d'alguns altres així com per mitjà d'aquest visualització aquí que ens introduirà en una sèrie d'algorismes. Seguirem endavant i felicitar nostres participants aquí, tots els quals ordenats de manera molt adequada. Si voleu donar un regal de comiat. Vostè pot mantenir els seus números també. I el que veuràs, o més aviat sentir, ara, és que a mesura que posem sons a cadascuna d'aquestes barres i associar-lo amb el programari, diferents freqüències de so, vostè pot embolicar la seva ment més audioly al voltant del que cadascuna d'aquestes coses sembla. El primer d'ells és l'ordenació per inserció 

[TONS] 

Aquesta és una espècie de bombolla. 

[TONS] 

Selecció espècie. 

[TONS] 

Una cosa anomenada merge sort. 

[TONS] 

Tipus Gnome. 

[TONS] 

Això és tot per CS50. Ens veiem dimecres. 

NARRADOR: I ara, "Deep Pensaments ", per Daven Farnham. Per què és un bucle? Per què no fer-ho millor? M'agradaria fer un bucle de cinc. 

[Rialles]