DAVID Malan: Todo ben. Polo tanto, esta é CS50, e este é agora o inicio da semana tres. Entón, ata agora, temos escribir programas en C que mirar un pouco algo coma isto aquí. Entón, nós temos un par de afiado inclúe, na parte superior. Temos int, principal, nula e entón algo para facer no medio, algún anaco de código dentro desta función. Pero clave foi o feito de que dixemos baleiro aquí. Entón, baleiro, todo este tempo, especifica que este programa, cando se executa, só pode ser executado a través do seu nome. Non pode escribir calquera outras palabras ou números despois do nome do programa cando executalo. Así, por exemplo, se o programa foron compilados nun arquivo chamado Ola, podería facer ./hello, pero é iso. 

O único xeito que podería contribuír a este programa é chamando unha función. Por exemplo, que a función temos benvida a empregar ata agora para entrada de usuario? 

Audiencia: Obter cadea. DAVID Malan: Para obter corda, ou obter int, ou xa viu noutros, mesmo se non telos usado aínda, como obter moito, moito e afíns. Pero supoña que realmente quere comezar escribir programas que son algo máis versátil, e, francamente, un pouco máis como as ordes que recibido, espero, algo afeito. Como cd espazo Dropbox. Isto, por suposto, os cambios seu directorio, asumindo está na casa de John Harvard directorio, na súa carpeta Dropbox. Mentres tanto, un comando coma este crea un novo directorio chamado pset2, como xa pode ter ou pronto para o problema de definir dous. Engadir Ola, por suposto, é unha orde que constrúe un programa chamado Ola a partir dun ficheiro chamado Ola punto c. E en cada un destes casos, agora, tivemos proporcionan unha discusión sobre o chamado liña de comandos, o poder piscando, para que make sabe o que construír, e así por que sabe o que mkdir cartafol para crear, e para que cd sabe onde quere ir. Pero ata agora, seguimos a dicir que o principal, a función estándar, ten unha expresión baleira dentro destes parénteses, o que significa que non pode tomar calquera argumentos. 

Entón, a partir de hoxe, o que imos facer é, imos comezar apoiar cousas como esta mesma. De feito, neste caso, o que lle non adoitan escribir manualmente Fai vén facendo iso para nós, non hai un, pero de un, dous, tres adicional cordas tras o programa de chamada clang. Entón, como imos conseguir isto? 

Ben, a partir de hoxe, nos casos en que queremos para facilitar entrada a través da chamado de liña de comandos, imos comezar a engadir aquí o que está yellow-- substituíndo baleiro con int argc comas corda argv soporte aberto pechar parénteses. Agora isto é interesante por un par de razóns. Un deles, que vai deixar-nos escribir programas que son un pouco máis dinámico. Pero, máis convincente, que vai abrir agora unha conversa acerca de o que matrices poden realmente ser utilizado, para o que unha cadea realmente é debaixo do capó, ata a próxima semana, cando comezamos mergullo no máis profundo de como a máquina está facendo todo este traballo material. Pero, por agora, imos deseñar, quizais, unha imaxe. 

Cando escribe un programa con principal declarada deste xeito, de tal xeito que principal recibe dous argumentos, un int e-- que tipo de datos é o segundo argumento? 

Audiencia: Array. DAVID Malan: Array. Polo tanto, parece a primeira vista como se fose un corda, pero observar os corchetes. Teña en conta que a última vez que introduciu a noción dunha matriz. E matrices usar corchetes nun par de contextos. Podes usar o cadrado soportes para ir nunha matriz e obter un elemento particular, como soporte 0 ou soporte dunha ou soporte 2. Pero vimos, aínda que brevemente, a semana pasada que tamén usar estes corchetes para declarar o tamaño dunha matriz, Se sabe de antemán cantos Ints ou como cadeas de moitos ou o que realmente queren. Entón non é que hai un terceiro contexto aquí que non ten ningún número dentro dos corchetes. Cando especificar, como eu teño aquí, o nome de algo como argv, que é só un xeito elegante de dicindo argumento vector, que é outra forma elegante de dicindo unha matriz de argumentos, soporte aberto pechar parénteses só significa que non precisa necesariamente saber con antelación como gran a matriz será, pero xa sabe que vai ser un array. Entón, se non sabe o número non poñer-lo alí dentro, para soporte aberto pechar parénteses significa que argv non é unha cadea, pero un conxunto de cordas. Entón, sintaticamente, se creo que volta a semana pasada, é moi similar a dicir algo así como int idades soporte aberto, e logo despois diso algo. Entón o que iso parece? Imos realmente sacar unha foto. Entón, cando executar este programa coa principal tendo dous argumentos definido dentro destes parénteses, é esencialmente teñen polo menos dous anacos de memoria entrega a vostede debaixo do capó. Un deles, como eu vou deseña como este rectángulo, será chamado argc. E así como unha rápida recapitulación, cal é o tipo de argc datos? Polo tanto, é un int. Así, un número vai para ir en quendas argc-- que representa o número de argumentos. Mentres tanto, eu deseño argv como unha matriz. E eu realmente non sei canto tempo vai ser, polo tanto, para fins de hoxe dot dot dot. Pode estar de algún tempo. Pero eu teño mostrado aquí polo menos catro rectángulos. Así, argv unha peza de memoria que almacena cadea cadea cadea dot dot dot, e argc é só unha peza de memoria para un número enteiro. 

Entón, agora, imos ser un pouco máis preciso. Se, cando eu teño cordas Nesta matriz, chamado argv, quero chegar a eles individualmente, así como a semana pasada, imos usar a notación como soporte argv 0 para obter o primeiro que un array. Argv soporte 1 para obter a segundo lugar, e así por diante. A clave aquí é que aínda estamos 0 indexed-- aínda estamos contando a partir de 0. Entón agora imos realmente poñer algo nese sentido. Se eu fose para compilar un programa chamado Hola a partir dun ficheiro chamado Ola punto c, e entón eu executar este programa con punto barra Ola, que é o que o meu ordenador, o meu portátil, parecer debaixo do capó no momento en que realizar dot reducir Ola e prema Intro? Ben, este é, quizais, o que poderiamos describir como o contido do seu ordenador de memoria, ou memoria de acceso aleatorio RAM--. Noutras palabras, o ordenador, dalgún xeito para que pase de máxica, pon o número 1 en argc, aka argcount, e pon literalmente a cadea ./hello en argv soporte 0. Eu non teño idea, francamente, o que é no soporte argv 1 ou 2 ou 3, porque, se o usuario non ten ingresaran somente ./hello, imos supor que estes son valores de lixo máis probables, por así dicir. Estes anacos de memoria existen, pero non cabe a nós de ollar para eles, porque o argcount é un só. 

Agora, mentres tanto, se eu escribir executar outro programa, cd, que é máis adecuadamente un comando, no seu espazo de palpebrar cd prompt-- Dropbox-- cando corro que, efectivamente, cando o programa é executado cd, argc, dentro da memoria do meu ordenador, é a o máis breve segundo o número 2. E, a continuación, o soporte ten argv cd, soporte argv 1 ten Dropbox, e despois, por suposto, o comando conclúe, entón todo isto de memoria esencialmente vai e se usa para outra cousa. E é por iso que eu digo só unha fracción de segundo. 

Mentres tanto, se facemos mkdir pset2, o cadro é case o mesmo, pero con diferentes cadeas dentro argv. Se eu fai clang trazo Ola Ola punto c, a mesma idea. Máis material é cuberto para argv e argc, por suposto, é 4. Así, noutras palabras, aínda que esta matriz pode ser dot dot dot, dalgún de lonxitude variable, por así dicir, sempre sabe onde a fin de todo é, pois argc vai dicir en que punto ten que deixar mirando para elementos en argv. Só podes ollar catro en total, neste caso. 

Entón, imos agora dar un ollo, quizais, un programa sinxelo. Un que di Ola para alguén como Zamyla. Entón, eu afirmo que vou escribir un programa en só un momento, a través do cal eu podería facer ./hello espazo Zamyla, e entón eu quero meu programa para imprimir algo super-sinxelo, como "Ola, Zamyla." Agora, no pasado usamos getString. Polo tanto, no pasado, aínda que vostede é novo en programación, posibilidades son que pode preparar unha programa que usa getString e entón usa printf para dicir ola para Zamyla. Pero non imos usar GetString neste momento. Déixeme en vez de ir ao Appliant e que inclúen estándar S dot h. Déixeme tamén inclúen CS50 punto h. Agora int main, e agora eu son non vai facer baleiro hoxe. Pola contra, eu vou facer int argc corda argv soporte aberto pechar parénteses, non especificar un número. E agora, aquí está o meu chamado para facer. O que eu vou facer agora é, eu son vai facer un pouco de un salto de fe, Vou asumir que o usuario do vai utilizar este programa correctamente, e eu estou indo simplemente para facer printf Ola,% sn. Polo tanto, nada novo nisto. Pero quero agora poñer calquera palabra que o tipo de usuarios despois do nome do programa. Entón, se eu fai ./hello espazo Zamyla, I quere dalgún xeito programática acceso entre comiñas "Zamyla." entón eu pode ir ao meu argumento vector, miña matriz de cadeas, e se a orde, de novo, foi ./hello espazo Zamyla, o número que quero para poñer en argv aquí? Audiencia: 1. DAVID Malan: 1, porque soporte 0 botan será o nome do programa, como vimos. Entón soporte 1 é a primeira palabra que eu, o usuario, escribiu. Eu estou indo a ir adiante e salva este. Eu estou indo a ir a miña carpeta onde eu teño este ficheiro. Vou facer facer Ola 3. Aceptar da Comp IO. ./hello Zamyla Intro. O que eu fixen de malo? Eu fun pego de sorpresa me por un momento alí. O que eu fixen de malo? 

Audiencia: Nome. 

DAVID Malan: O ficheiro de realmente chamado hello3.c. E eu fixen iso só para consistencia, porque tiveron ola.c de no pasado no código en liña. Entón imos solucionar isto ./hello soporte trazo 3 Zamyla. Intro. E agora temos Ola, Zamyla. Mentres tanto, podo cambiar isto ser Rob, é realmente calquera outra palabra. 

Pero imos considerar un caso de canto. O que podería esperar que terá lugar se Non escriba o nome de quen queira que sexa? 

Audiencia: Error. 

DAVID Malan: un erro dalgunha sorte, quizais. Imos ver. Intro. Null. Entón printf está realmente sendo un pouco de protección de nós aquí, e, literalmente, imprimir paréntese aberta null, pero as cousas aínda peores poden ocorrer. E só para demostrar algo que absolutamente non debe facer, imos entrar aquí e empezar a picar arredor. Correcto? Se eu sei que a imaxe memoria é esencialmente iso, argv franxa 1 ten Zamyla, argv soporte 0 ten ./hello, ou ./hello-3. Que é da clase 2? Entón, podo responder a esta cuestionar-me, non? Podo só cambiar o 1 á 2. Agora podo recompilar Ola 3, ./hello3 Imos ampliar e prema Intro. Whoops. Sen comiñas. Interesante. Entón, iso é ben legal para ver o que máis está aquí. 

Entón o que máis está dentro do meu portátil? Imos salvalo con soporte 3. Fai hello3, ./hello-3. Curioso. E agora imos realmente bold-- 50. Entón, iso é realmente profundo mergullo na memoria do meu ordenador. 50 en índices. Entón faga Ola 3 ./hello-3. Curioso. Todo ben, agora eu son só vai conseguir boa idea. Imos para 5000. Todo correcto. Entón deixe-me recompilar. Fai hello3, ./hello-3. Está ben. Agora algúns de vostedes, non pode ser unha lámpada a saír. Como moitos de vostedes teñen ver esta mensaxe antes? Está ben. Entón, por que? 

Odds é-- e hai diferentes cousas que poden causar iso, e é evidente que está en boa company-- temos claramente causou o que se chama un fallo de segmento. E short longo da historia para hoxe, eu tocar un segmento de memoria que eu non debería ter. Sempre que un segmento significa só unha peza de memoria que eu non debería ter. Agora, o equipo asegura que, se I realizar ./helloZamyla que podo tocar argv ser soporte 0 e argv soporte 1. Pero argc é o valor 2, isto significa que eu son só allowed-- é unha especie de honor system-- tocar soporte 0 e soporte 1. Se eu ir máis lonxe, hai absolutamente será memoria alí. A miña memoria RAM hai fisicamente no ordenador. Pero quen sabe o que está aí? En realidade, eu estou correndo múltiple programas de unha soa vez. Eu podería seen-- se eu non estivese facendo iso no Appliant pero no meu Mac ou PC-- eu podería ver o contido dun correo electrónico. Podería ver un instante Mensaxe Eu recentemente enviou. Calquera cousa que poida ser persistente en torno á memoria podía ser accedido a través de esta notación corchete arbitraria. Ou, peor aínda, pode que atopou unha das miñas claves que recentemente introduciu, que unha programa tiña almacenado na memoria de forma para me rexistrar e logo só un tipo de esquerda que na memoria RAM ata que deixei ese programa. 

E, de feito, este é un dos o perigo e un dos poderes de usar unha linguaxe como C. Ten acceso sen restricións a todo o contido da memoria dun programa, eo que bandidos poden mesmo facer nesas cases-- especialmente cando comeza a programación web ata o final do semestre, imos revisitar este topic-- é bisbilhotar, potencialmente, alguén é o ordenador de memoria e atopar tales cousas curiosas como vimos alí. Ou peor aínda, os contrasinais que ou ela pode usar para facer cousas malas. 

Entón, claramente, que eu non debería ter feito isto, porque cousas estrañas empezan a ocorrer. En realidade, este é un programa que deixa de funcionar. Isto sería equivalente a Mac OS ou Windows unha fiestra de programa simplemente desaparecer. Houbo un erro inesperado. No ámbito de liña de comandos vemos algo como isto. Pero é por iso, é que estou simplemente tocando memoria que non pertence a min. 

Entón imos defender contra este un pouco dun xeito diferente mirando para este programa. Así, unha vez máis, o esqueleto que vimos earlier-- e teño destaque esta vez int. E todo este tempo principal ten en realidade, retornou un valor. Aínda que na maior parte do noso charla exemplos que xamais usados volver nada na principal. Acaba de escribir printf preto chaveta e é iso. Pero de balde, o que o compilador feito para ti, efectivamente, está retornando 0 para ti. Acontece out-- e é un pouco counterintuitive-- que 0 é bo. Iso non significa falso en si. 0 é bo, e calquera non-0 valor, o mundo decidiu, pode significar un erro. Entón, se xa mexeu algo no seu ordenador, ou un programa acaba de morrer en ti e que obteña algunha fiestra incorrecta na pantalla dicindo erro negativo 49 ou erro 23-- algúns value-- arbitraria que é por un programador-codificado un valor como negativo ou positivo 49 23 para representar calquera número, atrévome a dicir, de 4 millóns de cousas posibles que pode dar mal en un programa. 

Entón, como eu podería vantaxe deste a min mesmo? Ben, deixe-me abrir un programa que escribín antes, e bisbilhotar liña chamado Ola 4. E é case idéntico, salvo que o ten un pouco de verificación de erros. Neste caso, eu de novo declarada principal como tendo dous argumentos, pero esta vez, na liña 17, a notificación Eu estou facendo un pouco de verificación de sanidade. Estou facendo-se de que argc coincide é igual a 2. Porque se é, que significa que podo con seguridade tocar non só soporte 0, pero soporte 1. E eu vou adiante e imprimir, neste caso, Zamyla ou Rob ou con calquera palabra que eu escriba. E agora só para conseguir algo máis axeitada, Vou volver explicitamente 0 para indicar que todo está ben. Nada de malo aconteceu. 

Pero por convención, vou volver 1, ou francamente calquera valor diferente de 0, si algo dese mal. Agora, o usuario non vai realmente entender o que está pasando. En realidade, se eu entrar nese directorio, nós zoom in e fan Ola 4, ./hello-4 Zamyla compórtase como eu esperaba. Pero se eu, no canto non escriba nada, nada parece ocorrer, pero non falla. E se eu non facer algo como Rob é un inspector no reparto Thayer-- información arbitraria. Pero aviso, argv 1, 2, 3, 4, e 5 agora debe existir na memoria. Isto, tamén, non o que é meu programa de espera, porque eu teño comprobado se argc coincide é igual a 2 ou non. Entón, eu estou agora a defensa contra iso. 

Agora, como un aparte, que o programmer-- ou mellor, o users-- nunca ver que 0 ou 1, pero utilizando unha ferramenta chamada Debugger, ou outras ferramentas, como veremos antes tempo, o programador Pode realmente ver o que se pode pasando mal dentro do seu programa. 

Entón, calquera dúbida sobre argc? Si. 

Audiencia: Vin onde non tiveron o personaxe, [inaudível] só dixo corda estrela d, como asterisco comas. Son equivalentes aquí? 

DAVID Malan: Son. Entón a pregunta é, ten programas ocasionalmente vistos así que non forman din soporte secuencia argv pero dicir algo como carbón soporte estrela argv. E hai aínda outro variantes que se pode ver. Son de feito equivalentes. Por agora temos estes tipo de Rodas pequenas sobre o xeito de cadea no CS50 biblioteca, pero en pouco máis dunha semana ou entón nós imos eliminar este obstrución totalmente e efectivamente ollar para o que o carbón ea estrela son, e como os que se refiren á memoria representación máis xeral. Entón, imos volver a iso. 

Outras preguntas sobre a nosa argv ou argc? Si. Audiencia: Por que volver un erro [inaudível]? DAVID Malan: Por que fixo iso voltar un erro only-- oh! No caso anterior, cando foron futzing volta coa memoria, por que só volverá un erro cando realmente escribiu un número grande? A resposta curta é que só tivo sorte. Dun modo xeral, un ordenador aloca memoria en anacos, e el me deu unha peza grande abondo que Eu fun aínda que, sen ser notado, de soporte de tocar 2, o soporte 3, soporte de 50, pero así que eu empurre a miña sorte, eu fun alá do límites do bloque de memoria o sistema operativo tiña me deu. E foi aí que axustado para abaixo e dixo: non. Erro de segmentación. Si. 

Audiencia: Como funciona o ordenador saber o valor de argc? 

DAVID Malan: Como é que o ordenador sabe o valor de argc? Cando executa un programa, este programa, pola natureza da solicitude de palpebrar, se entrega a matriz de palabras que foron escritas na liña, que era ingresaran no prompt. E así é o seu funcionamento sistema que esencialmente enche os argumentos de principais para ti. Entón ese é un dos servizos que recibe, máis ou menos en segredo debaixo da capa de un sistema operativo. Outras cuestións? Si. 

Audiencia: Qué dump de memoria significa? DAVID Malan: Qué dump de memoria significa? Así que esta é unha boa pregunta. E déixeme volver este directorio aquí. E vai entender que Eu teño un novo ficheiro alí. É, en realidade chámase núcleo, e é en realidade, normalmente un arquivo de tamaño decente. Isto é esencialmente unha instantánea de o contido da memoria do meu programa ou RAM cando caeu. E iso vai ser útil, potencialmente, diagnosticamente, unha vez que se fala nunha charla futuro e sección sobre a depuración, porque realmente pode facer o equivalente a unha autopsia dixitais nese arquivo para axudar a descubrir o que fixo de malo no seu programa. Si. 

Audiencia: É argc unha orde no si mesmo, ou pode nomealo de algo? 

DAVID Malan: Boa pregunta. Argc é unha orde, en si, ou pode chamalo de algo? Definitivamente non é un comando. É simplemente unha variable de nome ou o nome dun argumento, e de xeito absolutamente nós podería chamar este foo, poderiamos chamar este bar, que tenden ser o go-to palabras que un ordenador científico vai. Pero, por convención, usan argc e argv. Pero isto é só un ser humano convención, nada máis. Todo correcto. Así acaba, eu estiven contando un pouco de lie-- branco e, a verdade, no futuro, verá vimos dicir outras mentiras brancas. Pero, por agora, imos para pelar un destes. Neste caso aquí, cando anteriormente correu un programa como ./hello ou ./hello-3 Zamyla tivemos o contido do meu memoria do ordenador a buscar máis ou menos como este. Pero lembre que unha cadea é. O que dixemos hai unha semana que un corda realmente é debaixo do capó? Audiencia: matriz de caracteres. DAVID Malan: É unha matriz de caracteres, non? Así, poderiamos ter unha matriz de cadeas, pero, á súa vez, unha cadea é un array de caracteres. Entón, se eu realmente quero ser anal cando aproveitar esta foto, Realmente debería estar chegando algo máis así, polo que, en cada unha delas índices de miña matriz argv, non é en si toda unha serie que está nunha matriz. E agora a mentira estamos dicindo hoxe é que a imaxe non mira como esta. De feito, os pequenos cadrados son normalmente fóra dos grandes rectángulos Alí. Pero imos voltar a iso en pouco tempo. Pero iso é ./hello barra invertida 0, que sendo o carácter especial que demarca o fin dunha secuencia de caracteres, e temos outro despois Nome do Zamyla. Entón o que significa isto? 

Ben, deixe-me ir adiante e abre-se dous outros exemplos que están dispoñibles en liña. Un chámase argv1.c e outro é argv2. É un programa super-sinxelo que é diferente de programas anteriores en que agora está a usar argc e argv aquí. E agora eu estou integrando-se con un loop na liña 18, a partir de i = 0 en ata ARGC. E que é o que eu vou facer con esta liña de código aquí? En inglés. Isto, obviamente, demostra a utilización de argc. Pero en inglés, o que fai Que facer se eu executar este programa? Si? 

Audiencia: Vai imprimir o seu pantalla cantas veces quixer. DAVID Malan: Exactamente. Entón o que palabras I escriba na liña de comandos, é vai regurgitar los para min un por liña. Entón, imos seguir adiante e facelo. Déixeme ir ao meu directorio e fan ./argv1 argv1. E agora, imos mantelo simple. Imos facer nada en primeiro lugar. Fixo imprimir unha cousa, e que é de feito o nome do programa, porque é na franxa 0. Se eu agora dicir foo, que vai facer aqueles dous, e se eu digo bar foo, vai dicir estas tres cousas. Agora que é un pouco interesante, quizais. Pero lembre que argv é unha matriz de cadeas, pero unha cadea é un array de caracteres, para que poidamos levar as cousas por riba de un entalhe e aplicar ese básica lóxica e facer o código que parece un pouco máis crítico, en realidade. Pero por un aninhado loop, algo semellante para o que pode lembrar de Mario, por exemplo, se o fixo deste xeito. 

Entón agora notar na liña 19, eu son novo a iteración sobre os meus argumentos, de 0 a ata ARGC. E agora, en liña 21-- estou préstamo de un truco de última week-- Estou comprobando o que é o lonxitude de soporte argv i. Eu son almacenar esa resposta no n. E entón eu estou integrando desde j en ata n, onde j é inicializar a 0. Entón, convención para a conta. Xa que usou i, se ten un loop aninhado, non pode usar i novo, se non vai espancar, potencialmente, o valor fóra do loop interno. Entón, eu estou usando j por convención. Podemos usar k. Se ten máis de k, probablemente ten moito asentamento, normalmente. Pero agora, teña en conta a miña printf A liña é un pouco diferente. Eu non estou imprimindo% s, estou imprimir c%, o que, evidentemente, é un espazo reservado para un char. 

E agora observe esta sintaxe. Novo. Non vimos isto antes. Pero, loxicamente, isto significa só obter a secuencia om en argv e obter o j o que? Audiencia: Personaxe. DAVID Malan: Personaxe en que secuencia. Entón, usando corchetes seguido por corchetes, este é o mergullo primeiro en cadeas de argv, e, a continuación, o segundo corchetes con j é mergullar nos personaxes de que determinada secuencia en argv. E entón, só para unha boa medida, Estou imprimindo unha nova liña aquí. Entón, agora deixe-me ir adiante e abrir unha fiestra un pouco maior así que podemos ver iso en acción. Déixeme ir esa carpeta. E agora fan argv-2-- whoops-- facer argv-2, ./argv 2. Intro. E é algo difícil ler vertical, pero iso é en realidade o nome do programa, seguido por unha liña en branco. Agora, deixe-me ir adiante e facer foo. Igualmente difícil de ler, pero é en realidade imprimir un carácter por liña. E se eu fai bar, é agora imprimir os liña por liña. Así, o takeaway aquí non é tanto que, wow, mirar para este novo truco onde pode obter o contido de caracteres específicos dunha matriz, pero como estamos tomando estes básico ideas como a indexación nunha matriz, e logo, a indexación nunha matriz que estaba nesa matriz, e só aplicar as mesmas ideas para exemplos lixeiramente máis sofisticados. Pero o básico realmente non ten modificado, mesmo desde a semana pasada. 

Agora, esta é unha especie de oportuna, en que, lembre, a semana de cero xogamos cunha axenda telefónica como esta. E aínda que este é, obviamente, pezas físicas do papel, pode tipo de pensar unha lista telefónica como unha matriz. Certamente, se fose para reimplementar este pezas destes anacos de papel nun ordenador, probablemente usaría algo como unha matriz para almacenar todos aqueles nomes e números dunha todo o camiño a Z. Entón, iso é bo, porque permítenos unha oportunidade, quizais, a pensar en como pode realmente implementar algo parecido. Igual que unha serie de portas aquí. Entón, se eu could-- necesitamos unha voluntarios que se aproximase. Imos ver. Unha cara descoñecida quizais rostro descoñecido, quizais. Como sobre a laranxa? Aquí. Camisa laranxa, imos cara arriba. 

Imos adiante agora e movemento estas portas ao lado, mover los para fora do camiño por un momento. Cal é o seu nome? 

Ajay: 

DAVID Malan: Ajay. David. Pracer en coñece-lo. Todo correcto. Polo tanto, temos detrás destas seis portas dixitalmente no screen-- Ou mellor, sete portas no screen-- unha morea de números. E eu lle dixen nada en advance-- acordo? Ajay: Nada de antelación. DAVID Malan: Todo o que quero que faga agora é atopar a min, e para nós, realmente, o número 50, un paso de cada vez. 

Ajay: Número 50? 

DAVID Malan: Número 50. E pode revelar o que está detrás de cada unha destas portas simplemente tocando o con un dedo. Caramba. [Risas] 

[Aplausos] 

Moi ben feito. Está ben. Temos un fermoso agasallo premio para ti aquí. A súa elección de películas que discutido a semana pasada. 

Ajay: Oh, cara. Oh, eu nunca vin Spaceballs. 

DAVID Malan: Spaceballs. Todo correcto. Polo tanto, manteña en só un momento. How-- imos facelo un moment-- ensinável como é que vai facer sobre atopar o número 50? Ajay: Eu escollín aleatoriamente. DAVID Malan: Entón escolleu azar e tivo sorte. Ajay: Si. DAVID Malan: Aceptar. Excelente. Entón, agora, se non tivese tido sorte, o que máis podería acontecer detrás desas portas? Entón, se eu ir adiante e revelar estes números aquí, realmente están en orde aleatoria. E o mellor que pode ter feito, a verdade, é de, en última instancia, no peor dos casos, alomenos todos eles. Entón tes super-sorte, o que Non é o que chamaría de un algoritmo. Si, parabéns. Pero agora let's-- humor min, se puidese. Imos para esta guía aquí. E aquí están os números en clara o que parece ser unha orde aleatoria, e eles foron. Pero agora, se eu en vez reivindicación que detrás desas portas son números que son clasificados. O obxectivo agora é tamén atopar-nos no número 50. Pero facelo a través de algoritmos e di-nos como está indo con iso. E se atopala, a manter a película. Non atopalo, darlle de volta. Ajay: Entón, eu vou dar un ollo nos extremos en primeiro lugar, para determinar se there's-- [Risas e aplausos] DAVID Malan: Velaquí. Imos dar un ollo a un dos antecesores de Ajay, Sean, que non foi tan afortunado. OK, así que a súa tarefa aquí, Sean, é o seguinte. Eu escondín detrás destes portas do número sete, pero escondido nalgunhas desas portas tamén son outros números non-negativos. E o seu obxectivo é pensar desta liña superior de números como só unha matriz. Somos só unha secuencia de pezas de papel cos números detrás delas. E o seu obxectivo é, usando só o principio matriz aquí, atopar-me o número sete. E nós estamos indo axiña para criticar como vai facer sobre iso. Atopar-nos o número sete, por favor. N º 5, 19, 13. Non é unha pregunta capciosa. 1. Neste punto, a súa puntuación non é moi bo, entón pode moi ben seguir. 3. Dalle. Francamente, eu non podo axudar, pero pregunta o que está mesmo a pensar. 

SEAN: Podo tomar só o principio de liña. DAVID Malan: Só a liña superior. Entón tes tres esquerda. Entón, atopar-me 7. 

[Audiencia berros SUXESTIÓNS] Así, estes dous eran incrible por razóns moi diferentes. Polo tanto, este é o lugar onde nós parou un instante atrás, ea introspección clave aquí foi estas portas tiñan números detrás deles, que foron clasificadas, o ideal takeaway para que é que pode facer fundamentalmente mellor Nesta segunda example-- e, de feito, que foi de Sean primeiro intento con números aleatorios así como antes-- pero así como eses números son clasificadas, moi parecido ao libro de teléfono, o que pode, obviamente, facer? Ou como pode aproveitar este coñecemento? Si. 

Audiencia: Vai no medio do camiño [inaudível]. DAVID Malan: Yeah. Exactamente. Entón instinto inicial de Ajay foi para comprobar os extremos, se ben me lembra, e entón nós medio que acaba o exemplo rapidamente. Pero se comezamos a facelo máis metodicamente ao longo destas liñas, pero empezando talvez no medio, porque están ordenados, así que revelan a número 16, que, polo tanto, sabe-- e imos facer exactamente que-- nós polo tanto, saber que o 50, no caso de hoxe, ten que ser á dereita. Así como a semana cero cando que resgou o libro de teléfono pola metade e xogou a metade do problema de distancia, mesma idea aquí. Podemos xogar nesta parte do problema de distancia. E, probablemente, o que pode facer a través de algoritmos, cando vostede sabe que o 50 debe ser á dereita, se é en calquera lugar, é tentar alí, no medio das restantes portas. Por suposto, o 50 é maior de 42, para que poidamos xogar este remanente trimestre do problema de distancia, e, finalmente, identificar algo así como 50. Pero, así como co lista telefónica, eses números foron dadas a nós xa en orde de clasificación, o que nos deixa coa cuestión, como facer as cousas en orde de clasificación? E, francamente, a que custo? É unha cousa para ser entregou o libro de teléfono e impresionar os seus amigos por atopar un número de teléfono moi rapidamente, non? Rasgar 32 páxinas para atopar un persoa de 4 mil millóns de páxinas, dixemos foi un exemplo extremo. Pero canto tempo tardou Verizon para ordenar que o libro de teléfono? Canto tempo tardou para nós para clasificar estes sete números? Esta é unha pregunta que temos ata agora totalmente ignorado. 

Entón, imos responder a esta pregunta agora. E estamos todos de películas agora, pero temos algunhas bolas de estrés. Se, por exemplo, oito voluntarios Non me importaría unirse a nós aquí enriba? Imos adiante e facer, como sobre vostedes catro, tres de vós aquí? Vexa algunhas caras novas. E os catro de alí? E agora-- non imos viés aqui-- e número oito alí ao final. Imos cara arriba. Todo correcto. Entón o que temos aquí para cada un de vós é un número. Se quere ir adiante, cara este número. Cal é o seu nome? 

Artie: Artie. 

DAVID Malan: Artie, ok. Vostede é o número 1. 

Amin: Amin. DAVID Malan: Amin. David. Vostede é o número 2. E vai adiante, como eu entrego que as follas de papel, aliñan-se diante da música está no mesmo orde como se alí. 

Andy: Ola, Andy. 

DAVID Malan: Andy, é bo te ver. Número 3. 

JACOB: Jacob. 

DAVID Malan: Jacob, número 4. Benvido a bordo. GRANT: Grant. DAVID Malan: Grant. Número 5. 

Alanna: Alanna. 

DAVID Malan: Alanna, número 6. 

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

RACHEL: Rachel. 

DAVID Malan: Rachel, número 8. Todo correcto. Dalle obter-se, por esta orde. Deixe-me poñer un remanente música estar no lugar. Onde é que precisa dun soporte? Está ben. Dalle só poñer os seus números onde o público pode velos en, música estar volto para fóra. E espero que, o noso primeiro verificación de sanidade aqui-- 4, 2, 6. Oh-oh. Espere un minuto. Non temos un 8. Necesito despejo-lo do o exemplo de algunha maneira. N º Non, iso é OK. Imos ver. Podemos facelo. Estar por. Alí imos nós. Correcto. Todo correcto. Entón, agora temos 8, 1, 3 7, 5. Está ben. Excelente. 

Polo tanto, a cuestión en apreciado é, en que custo, e vía o que o método, podemos realmente resolver estes números aquí para que poidamos tipo de traballo cara atrás, en última instancia, e decide-- é realmente impresionante, é realmente eficiente, que eu poida dividir e conquistar un libro de teléfono? Será que é realmente eficaz que Podo dividir e conquistar estas pezas dixitais de papel no taboleiro, se cadra iso vai custa-nos fortuna no tempo ou ciclos de enerxía ou de CPU para realmente obter os nosos datos nalgunha orde de clasificación? Entón, imos facer esta pregunta. 

Entón, en primeiro lugar, estas cifras son en orde aleatoria practicamente, e eu vou propoñer un algoritmo, ou proceso polo cal podemos clasificar estas persoas. Vou abordar esta moi inxenuamente. E eu vou recoñecer que é unha especie de unha chea para min implicar miña mente en torno á datos enteiros axustar dunha vez. Pero vostede sabe o que? Vou facer algunhas correccións marxinais moi sinxelo. 4 e 2 están fóra de orde, se o obxectivo é ir de un a ata 8. Entón vostede sabe o que? Vou ter vostede caras cambiar, se cambiar fisicamente posicións e os anacos de papel. Agora, 4 e 6, estes son, en orde. Vou deixar os ser. 6 e 8, aqueles están en orde. Indo para deixalos ser. 8 e1, fóra de orde. Se vostedes dous non lle importaría trocar. Agora 8 e 3, se vostedes poderían cambiar. 8 e 7, se vostedes poderían cambiar. E 8 e 5, se vostedes poderían cambiar. 

Agora, eu estou listo? Non, evidentemente non. Pero eu fixen o situación mellor, non? Cal era o seu nome, número 8? 

RACHEL: Rachel. DAVID Malan: Entón Rachel ten efectivamente borbulhava moi lonxe, todo o camiño para a fin de miña matriz de números aquí. E así que é o tipo de problema resolto. Agora, claro, dúas aínda que mover un pouco, e 4 e 6 e 1. Pero paréceme obter un pouco máis preto da solución. Entón, imos aplicar esta mesma heurística inxenuo novo. 2 e 4, OK. 4 e 6, Aceptar. 6 e 1, mm-mm. Imos cambiar. 6 e 3, mm-mm. Imos cambiar. 6 e 7 é OK. 7 e 5, Nope. Imos cambiar. E agora 7 e 8. E cal é o seu nome? FRANCES: Frances. DAVID Malan: Frances. Polo tanto, agora é en Frances mesmo unha mellor posición, porque agora 7 e 8 están correctamente abrollou ata o cumio. Entón, 2 e 4, OK. 4 e 1, cambio de let. 4 e 3, cambio de let. 4 e 6, está OK. 6 e 5, cambio de let. E agora estes faces son bos. Estamos case alí. 2 e 1, fóra de orde, entón cambiar. E agora déixeme facer unha proba de sanidade. 2 e 3, 3 e 4, 4 e 5, 5 e 6, 6 e 7, 8. OK, entón estamos a facer. 

Pero a que prezo fixen Ordenar estas cifras aquí? Ben, cantos pasos fixen potencialmente levar ao clasificar esas persoas? Ben, imos voltar a esta pregunta. Pero, francamente, se ten algo aburrido, que é tipo de revelar en que iso non era quizais o algoritmo máis eficiente. E, de feito, a verdade, estou suando aínda máis camiñando cara atrás e cara adiante. Iso non me sinto especialmente eficiente. Entón, imos tratar outra cousa. Se vostedes poderían axustar vos a estes oito valores. Bo traballo. 

Imos dar un ollo dixital, para só un momento antes de outra cousa, co que acababa de acontecer. Ata aquí, está a piques de ver unha visualización destes oito seres humanos cal azul e vermello barras representan números. O máis alto do bar, canto maior sexa o número. Canto máis curto o bar, canto menor sexa o número. E o que vai ver é en azar máis que oito deles. Vai ver estas barras sendo clasificado por ese mesmo algoritmo, ou un conxunto de instrucións, o cal imos chamar adiante bubble sort. Entón, observe, cada segundo ou así, dous bares están acendendo en vermello, están a ser comparados polo ordenador. E entón, se o gran bar eo pequeno bar están fóra de orde, están sendo trocados por min. 

Agora iso é incrible entediante para asistir a este, certamente, por moito tempo, pero observar o takeaway-- grandes bares que se cambiar para a dereita, pequenos bares que se desprazan á esquerda. Imos abortar este proceso e acelerar o proceso ser moito máis rápido, para que poidamos ter unha noción de alto nivel que, de feito, bubble sort está facendo. En realidade, está borbulhando ata a lado dereito da lista, ou a matriz, as barras maiores. E, inversamente, os pequenos bares están burbullas seu camiño cara á esquerda, aínda que a un ritmo máis rápido do que xa fixo. Entón, máis difícil de ver cos seres humanos, pero visualmente que é de feito o que estaba a ocorrer. 

Pero imos tratar unha fundamentalmente visión diferente agora. Imos tentar un distinto algoritmo polo cal temos que caras comezan nestes orixinais posicións, o que foi esta orde. E imos adiante agora. E eu vou facer algo aínda máis sinxelo, non? En retrospectiva, o intercambio de parellas novo e, de novo, case un pouco intelixente. Imos facer as cousas aínda máis inxenuamente, onde se quere clasificar estas persoas, déixeme seguir buscando para o elemento máis pequeno. Entón, agora, é o 4 menor número que eu xa vin. Vou me lembrar diso. Non, dous é mellor, e lembre-se diso. 1 é aínda máis reducida. 3, 7, 5. Está ben. Um-- cal é o seu nome? 

Artie: Artie. 

DAVID Malan: Artie. Entón, Artie, vai adiante. Vou puxa-lo para fóra da liña. Se puidese volver aquí. E eu teño para facer o cuarto para el. Temos un punto de decisión aquí. Como podemos dar espazo para Artie aquí en principio, onde o número 1 pertence? 

Audiencia: Shift. 

DAVID Malan: OK, nós podería cambiar todo. Pero propoñer unha optimización. Isto parece un pouco aburrido para min pedir catro persoas para mover todo o camiño. Que máis podería facer? 

Audiencia: muda-los. 

DAVID Malan: muda-los. E cal é o seu nome? 

JACOB: Jacob. DAVID Malan: Jacob, mover. Moito máis eficiente só de ter Lugares de intercambio Jacob con Artie, en oposición a forzar todas estas catro persoas, moitas grazas, a súa posición correcta. Que é agradable sobre Artie agora, está na súa posición correcta. Imos facer iso de novo. 2, que é o menor número que eu xa vin. 3, 7, 5. Está ben. 2 é sempre menor. Non ten que facer ningún traballo. Imos facer iso de novo. 6. Menor? 8. Non. 4? Ooh. Que eu me lembre 4. 3. Que eu me lembre 3. 7, 5. O menor número que teño ver nesta pasaxe é 3. Se ven para fóra. Onde é que imos poñer-lo? E cal o seu nome? 

Alanna: Alanna. 

DAVID Malan: Alanna, estamos terá que despejo-lo. Pero isto é máis eficiente, só para cambiar dúas persoas, que ter varias persoas realmente evitar over. Agora imos facelo de novo. Vou seleccionar 4, entón imos alí para fóra. E quen é o que vai cambiar? Número 8, claro. Se eu agora atopar o número 5, vén para fóra. Número 8 se ve despexados novo. Estou indo agora para atopar o número 6 no lugar. 7 no lugar. 8 no lugar. 

O que acabamos de facer agora é algo chamado de selección de clasificación, e se ver isto, é Vai sentirse un pouco diferente. Imos adiante e esta menú aquí, este visualization-- imos cambiar este para-- veña, Firefox. Imos cambiar isto para a selección de clasificación. E imos acelera-lo como antes, e iniciar a visualización agora. E este algoritmo teña unha sensación diferente. En cada iteración, francamente, é aínda máis sinxela. Eu só estou seleccionando o menor elemento. Agora, francamente, eu teño un pouco de sorte que tempo, na medida en que ordenados super-rápido. Os elementos foron aleatorias. Non é, como veremos, finalmente, ver, fundamentalmente máis rápido. Pero imos ver un terceiro e último abordar aquí, como o que está a suceder. Entón, imos adiante e axustar vostedes unha última vez para ser nesta orde aquí. 

E agora, eu vou ser un pouco máis intelixente, só para completar os nosos algoritmos. Vou facelo. Eu estou indo a non ir adiante e cara atrás tanto. Francamente, estou cansa de todo este desprazamento. Eu só vou ter o que eu son dada no inicio da lista, e eu estou indo a clasificar que alí mesmo. Entón aquí estamos nós. Número 4. Eu estou indo a introducir o número 4 nunha lista ordenada. Feito. Eu reivindico agora, e só para facelo máis suposto, esta parte da miña lista é ordenada. É unha especie de unha proposta estúpido, pero de feito 4 están clasificados nunha lista de tamaño dun. Agora, eu vou tomar o número 2. Número 2 agora eu vou introducir no lugar seguro. Entón onde é que dous pertencen? Obviamente, aquí. Entón vai adiante e volver, se puidese. E por que non pode ter caras súa música está con vostede neste momento. E imos forzar a entrada que ao comezo da lista. Entón, un pouco máis de traballo. Tiven que cambiar Jacob arredor, e cal é o seu nome? 

Amin: Amin. 

DAVID Malan: Amin. Pero polo menos eu non fun para atrás e para adiante. Eu só estou levando as cousas como eu ir. Estou só inserir-los no lugar seguro. 6, este é realmente moi fácil. Imos introducir ti alí, se só quería pasar un pouco. Número 8, tamén moi fácil. Ben alí. Caramba. Número 1, non podemos simplemente intercambiar con Amin aquí, porque o que está a suceder para interferir a orde. Entón, temos que ser un pouco máis intelixente. Entón, Artie, se puidese facer a copia de seguridade por un momento. Imos adiante e cambiar agora, Ao contrario dos nosos algoritmos anteriores, para dar espazo para Artie aquí no inicio. Así, ao final do día, eu son o tipo de facendo o que eu quería evitar antes. E así o meu algoritmo é unha especie de revertido, intelectualmente, do que era orixinalmente. Eu só estou facendo o desprazamento nun punto distinto. Agora estou no 3. Oh, maldito. Temos que facer máis traballo de novo. Entón, imos empurralo para fóra. Imos pasar 8, 6, 4-- oh Oh-- e 3 vai dar certo alí. Entón, pequenas economías menos esta vez. 7, moito traballo non se debe facer. Entón, se quere pop de volta, imos introducir-lo. E, para rematar, 5, se quere aparecer de novo, nós que cambiar ti, ti, ti, ata cinco está no lugar. 

Entón agora a ver isto nun alto nivel gráficamente imos facer ese algoritmo visualización dun tempo adicional. Entón iso chamaremos de inserción tipo. Imos executa-lo só como rápido, e inicia-lo aquí. E, tamén, ten unha sensación diferente. É unha especie de ir mellor e mellor, pero nunca é perfecto ata eu entrar e lisa esas lagoas. Porque, unha vez máis, eu estou só tomando o que Estou a ser dado a partir de esquerda a dereita. Entón, eu non tiven tanta sorte que todo foi perfecto. É por iso que tivemos estes pequenos mispositions que fixos ao longo do tempo. 

Entón, todos estes algoritmos parecen executado en un pouco diferentes ritmos. En realidade, o que diría se o mellor é o máis rápido ata o momento? Bubble sort, o primeiro? Tipo de selección, a segunda? Tipo de inserción, o terceiro? Ouzo algúns tipos de selección. Outros pensamentos? 

Así, verifícase que todos estes algoritmos son fundamentalmente tan eficiente canto cada outro-- ou, pola contra, só como ineficiente como o outro, porque podemos facer fundamentalmente mellor que os tres destes algoritmos. E iso é un pouco de unha mentira, tamén. cando digo que o máis eficiente ou como ineficiente, que é, como mínimo, a super-grandes valores de n. Cando temos só oito persoas aquí, ou quizais 50 ou máis barras na pantalla, vai absolutamente notar diferenzas entre estes tres algoritmos. Pero como n, o número de persoas, ou o número de números, ou o número de persoas no teléfono libro, ou o número de páxinas web na base de datos de Google fica cada vez maior, veremos que os tres destes algoritmos son realmente moi pobre. E podemos facer fundamentalmente mellor que iso. 

Imos dar un ollo, por fin, en que estes algoritmos pode soar como no contexto dalgúns outros así como por medio do presente visualización aquí que vai presentar a un número de algoritmos. Imos adiante e parabenizar nosos participantes aquí, os cales clasificadas-se moi ben. Se quere dar un regalo de despedida. Pode manter os seus números tamén. E o que vai ver, ou mellor, escoitar, agora, é que, como poñemos sons cada unha destas barras e asocia-lo co software, diferentes frecuencias de son, pode implicar a súa mente máis audioly arredor do que cada unha destas cousas parece. A primeira das cales é a ordenación por inserción 

[Tons] 

Este é bubble sort. 

[Tons] 

Tipo de selección. 

[Tons] 

Algo chamado merge sort. 

[Tons] 

Tipo Gnome. 

[Tons] 

Isto é todo para CS50. Imos velo na Mércores. 

Narrador: E agora, "Deep Pensamentos ", de Daven Farnham. Por que é un loop? Por que non facelo mellor? Eu faría un circuíto de cinco. 

[Risas]