DAVID MALAN: Okej. Så detta är CS50, och detta är nu i början av vecka tre. Så fram till nu, vi har skrivit program i C att se lite något som detta här. Så vi har ett par skarp innefattar upptill. Vi har int, huvud, tomrum, och då något att göra i mitten, viss bit kod inuti av denna funktion. Men nyckeln har varit det faktum att Vi har sagt tomrum här. Så ogiltiga, all denna tid, anger att detta program, när det körs, kan endast köras via dess namn. Du kan inte skriva något annat ord eller siffror efter programmets namn när kör den. Så, till exempel om programmet var sammanställs i en fil som heter hej, du kunde göra ./hello, men det är det. Det enda sättet som du kan bidra till detta program är genom att ringa en funktion. Till exempel, vad funktion har vi använt hittills att få input från användaren? PUBLIK: Få sträng. DAVID MALAN: För att få strängen, eller får int, eller du har sett andra, även om du inte har använt dem ännu, som blir lång, lång och liknande. Men anta att vi egentligen vill starta skriva program som är lite mer mångsidig, och, ärligt talat, lite mer liksom de kommandon som du har varit att få, förhoppningsvis, lite vana vid. Liksom cd utrymme Dropbox. Detta, naturligtvis, förändringar din katalog, förutsatt du är i John Harvard hem katalog, till din Dropbox-mapp. Under tiden ett kommando som detta skapar en ny katalog som heter pset2, som ni kanske redan har eller kommer snart att problemet satt två. Gör Hej, naturligtvis, är ett kommando som bygger ett program som heter hello från en fil som heter hej dot c. Och i vart och ett av dessa fall nu, vi har haft ger ett argument på den så kallade kommandoraden, den blinkande prompten så att göra vet vad man ska bygga, och så att mkdir vet vad mapp för att skapa, och så att cd vet där du vill gå. Men fram till nu, vi fortsätter att säga det viktigaste, din standardfunktion, har en hålrums uttryck insidan av dessa parenteser, vilket innebär att den kan inte ta några argument. Så från och med idag, vad vi ska göra är, ska vi börja stödja saker som detta ännu. Faktum är att i det här fallet, som ni vanligtvis inte manuellt skriva, Gör har gjort detta för oss, det finns inte en men en, två, tre ytterligare strängar efter programmets namngiven klang. Så hur ska vi uppnå detta? Tja, med start idag, i de fall där vi vill att ge input via så kallad kommandoraden, vi ska börja lägga här vad som finns i yellow-- ersätta tomrummet med int argc kommatecken string argv öppen konsol nära fästet. Nu är det här intressant för ett par anledningar. Ett, det kommer att låta oss skriva program som är lite mer dynamiskt. Men, mer tvingande, det kommer att öppna upp nu en konversation som till vad arrayer kan verkligen användas, till vilken en sträng verkligen är under huven, till nästa vecka när vi börjar dyka i ännu djupare på hur maskinen är gör allt det här arbetet. Men för nu, låt oss dra, kanske en bild. När du skriver ett program med huvud deklarerade på detta sätt, så att huvud tar två argument, en int och-- vilken datatyp är det andra argumentet? PUBLIKEN: Array. DAVID MALAN: Array. Så det ser ut vid första anblicken ut att vara en sträng, men märker hakparenteserna. Minns förra gången vi införde föreställningen om en array. Och arrayer använder hakparenteser i ett par sammanhang. Du kan använda torget parentes för att gå in i en matris och få ett visst element, som konsol 0 eller konsol 1 eller konsol 2. Men vi såg, om kortvarigt, förra veckan att man även använda dessa hakparenteser till förklara storleken på en matris, om du vet i förväg hur många Ints eller hur många strängar eller vad du faktiskt vill. Så visar det sig att det finns en tredje kontext här som inte har någon numrerar insida av hakparenteserna. När du anger, som jag har här, namnet på något liknande argv, som är bara ett finare sätt att säger argumentet vektor, vilken är ett annat fint sätt att säger en array med argument, öppen fäste stäng fäste bara innebär att du inte nödvändigtvis i förväg veta hur stor arrayen kommer att bli, men du vet att det kommer att vara en array. Så om du inte känner till nummer inte lägga den där, för öppen konsol nära fästet innebär att argv inte är en sträng, men en array av strängar. Så syntaktiskt, om du tänker tillbaka förra veckan, Det är mycket likt att säga något som int åldrar öppna fäste, och sedan något därefter. Så hur ser det här ut som? Låt oss faktiskt rita en bild. Så när du kör det här programmet med huvud att ha två argument definieras inuti av dessa parenteser, du väsentligen har minst två bitar minne överlämnas till dig under huven. Ett, som jag ska drar som denna rektangel, kommer att kallas argc. Och precis som en snabb resumé, vad är datatyp argc? Så det är en int. Så ett antal går att gå in argc-- varv ut som står för argument räknas. Under tiden har jag dragit argv som en matris. Och jag vet inte riktigt hur lång tid det kommer att bli, så för dagens ändamål dot dot dot. Det kan komma en del längd. Men jag har på bilden åtminstone fyra rektanglar. Så argv en bit av minne som lagrar sträng sträng sträng dot dot dot, och argc är bara en bit minne för ett heltal. Så nu, låt oss vara lite mer exakt. Om, när jag har strängar i denna matris, som kallas argv, jag vill komma åt dem individuellt, precis som förra veckan, vi kommer att använda notation liknande argv bygel 0 att få den första som en array. Argv fäste 1 för att få den andra saken, och så vidare. Det viktigaste här är vi fortfarande 0 indexed-- vi fortfarande räkna från 0. Så nu ska vi faktiskt sätta något i detta. Om jag skulle sammanställa ett program som kallas Hej från en fil som heter hej dot c, och då jag kör det programmet med dot snedstreck Hej, vad gör min dator, min laptop, se ut under huven nu jag kör dot slash hej och tryck Enter? Nåväl, detta är kanske vad vi skulle kunna beskriva som innehållet i datorns minne, eller RAM-- Random Access Memory. Med andra ord, om datorn, något för dig magiskt, sätter nummer 1 i argc, AKA argcount, och det sätter bokstav strängen ./hello i argv bygel 0. Jag har ingen aning, ärligt talat, vad är i argv fäste 1 eller 2 eller 3, för om användaren har inte skrivit någonting förutom ./hello, vi kommer att anta att dessa är mest sannolika skräp värden, så att säga. Dessa bitar av minnet finns, men det är inte upp till oss att titta på dem, eftersom den argcount finns bara en. Nu, under tiden, om jag skriver kör ett annat program, CD, vilket är mer korrekt ett kommando, i ditt blinkande prompt-- cd utrymme Dropbox-- när jag kör det, på ett effektivt sätt, när cd programmet körs, argc, insidan av datorns minne, är för mest kortaste andra siffran 2. Och sedan argv fäste o har cd, argv fäste 1 har Dropbox, och då naturligtvis kommandot avslutar, så allt detta minne huvudsak går bort och används för något annat. Och det är därför jag säger bara en bråkdels sekund. Under tiden, om vi gör mkdir pset2, bilden ser nästan samma, men med olika strängar inne argv. Om jag gör klang streck hello hello dot c, samma idé. Mer saker fylls i för argv och argc, naturligtvis, är fyra. Så med andra ord, även om denna array kanske dot dot dot, av något variabel längd, så att säga, du alltid vet var i slutet av den är, eftersom argc kommer att berätta för dig vid vilken tidpunkt du måste sluta tittar på element i argv. Du kan bara titta på fyra totalt i detta fall. Så låt oss nu ta en titt på, kanske, ett enkelt program. En som bara säger hej till någon som Zamyla. Så jag hävdar jag ska skriva ett program på bara ett ögonblick via vilket jag kunde göra ./hello utrymme Zamyla, och då jag vill ha mitt program för att skriva ut något super enkelt som "Hej, Zamyla." Nu i det förflutna som vi har använt getString. Så i det förflutna, även om du är ny till programmering, oddsen är att du kan piska upp en program som använder getString och sedan använder printf att säga hej till Zamyla. Men låt oss inte använda GetString här gången. Låt mig i stället gå in i Appliant och inkluderar standard I O dot h. Låt mig också inkludera CS50 dot h. Nu int main, och nu är jag kommer inte att göra ogiltiga idag. Istället kommer jag att göra int argc string argv öppen fäste stäng fäste, inte ange ett nummer. Och nu här är min så kallade att göra. Vad jag ska göra nu är, jag är kommer att göra lite av ett språng i tro, Jag kommer att anta att användarens kommer att använda det här programmet på rätt sätt, och jag bara går till gör printf hej,% sn. Så inget nytt där. Men jag vill nu lägga allt vad ordet det användartyper efter programmets namn. Så om jag gör ./hello utrymme Zamyla, jag vill på något sätt prog tillgång citera unquote "Zamyla." så jag kan gå in i min argumentation vektor, min array med strängar, och om kommandot, återigen, var ./hello utrymme Zamyla, vilket nummer jag vill ha att sätta i argv här? PUBLIKEN: 1. DAVID MALAN: 1, eftersom fäste 0 visar sig kommer att bli den programmets namn, som vi såg. Så fäste 1 är det första ordet att jag som användare har skrivit. Jag kommer att gå vidare och spara denna. Jag kommer att gå in i min mapp där jag har placerat den här filen. Jag kommer att göra göra hello 3. Comp IO är OK. ./hello Zamyla Enter. Vad gjorde jag för fel? Jag blev överraskade mig själv för en stund där. Vad gjorde jag för fel? PUBLIKEN: Namn. DAVID MALAN: Filens faktiskt kallas hello3.c. Och jag gjorde det bara för enhetlighet, eftersom vi har hade hej.c si tidigare i online koden. Så låt oss fixa detta ./hello bygel streck 3 Zamyla. Enter. Och nu har vi hej, Zamyla. Under tiden kan jag ändra detta till vara Rob, eller egentligen något annat ord. Men låt oss betrakta ett hörn fall. Vad kan du förvänta dig kommer att hända om Jag inte skriver någons namn alls? PUBLIKEN: Fel. DAVID MALAN: Ett fel av något slag, kanske. Låt oss se. Enter. Null. Så printf faktiskt vara lite skyddande av oss Här, och bokstavligen skriva ut öppna Paren null, men ännu värre saker kan hända. Och bara för att visa att något som du absolut inte bör göra, låt oss gå in här och börja peta runt. Rätt? Om jag vet att bilden minnet är i huvudsak denna, argv fäste 1 har Zamyla, argv fäste 0 har ./hello eller ./hello-3. Vad finns i konsolen 2? Så jag kan svara på det ifrågasätta mig själv, eller hur? Jag kan bara ändra 1 till 2. Jag kan nu kompilera hello 3, ./hello3 Låt oss zooma in och tryck på Retur. Whoops. Ingen citattecken. Intressant. Så det är ganska coolt att se vad annat är här. Så vad är inne i min laptop? Låt oss spara den med fäste 3. Gör hello3, ./hello-3. Nyfiken. Och nu ska vi få riktigt bold-- 50. Så det är verkligen dyka djupt i datorns minne. 50 index in. Så gör hello 3 ./hello-3. Nyfiken. Okej, nu är jag bara kommer att få vårdslös. Låt oss gå till 5.000. Okej. Så låt mig kompilera. Gör hello3, ./hello-3. OK. Nu några av er, det kanske vara en glödlampa gick av. Hur många av er har sett detta meddelande förut? OK. Så, varför? Odds är-- och det finns olika saker som kan orsaka detta, och tydligt att du är i god company-- vi har tydligt orsakade vad som kallas en segmentering fel. Och lång historia kort för idag, jag har berört ett segment av minne att jag inte borde ha. Om ett segment betyder bara en bit minne som jag inte borde ha. Nu garanterar dator som om jag köra ./helloZamyla att jag kan röra argv vara fästet 0 och argv fäste 1. Men argc är värdet 2, betyder att jag är Endast allowed-- det är typ av äran system-- röra fäste 0 och fäste 1. Om jag går något längre, det finns absolut kommer att vara minnet där. Lagda Min RAM fysiskt i datorn. Men vem vet vad som finns där? Faktiskt, jag kör flera program på en gång. Jag kanske har seen-- om jag inte göra detta på Appliant men på min Mac eller PC-- jag kanske har sett innehållet i ett e-post. Jag kanske har sett en omedelbar budskap Jag har nyligen skickats. Allt som kan vara dröjande runt i minnet kunde ha visats genom denna godtyckliga klammer notation. Eller, ännu värre, kanske du har hittade en av mina lösenord att jag nyligen hade skrivit in, att en Programmet hade lagrats i minnet som att autentisera mig, och sedan bara slags lämnat det i RAM tills jag avslutar det programmet. Och faktiskt, det här är en av faran och en de befogenheter av att använda ett språk som C. Du har fri tillgång till hela innehållet av ett program minne, och vilka skurkar kan göra även i de cases-- särskilt när vi komma till webbprogrammering mot slutet av terminen, vi ska besök det här topic-- är rota runt, potentiellt, är någon dator minne och hitta sådana underliga saker som vi såg där. Eller ännu värre ändå, lösenord som han eller hon kan sedan använda för att göra dåliga saker. Så klart jag inte borde ha gjort det här, eftersom konstiga saker börjar hända. Detta är faktiskt ett program kraschar. Detta skulle motsvara Mac OS eller Windows ett programfönster bara försvinna. Ett oväntat fel har uppstått. På kommandoraden miljö Vi ser ut ungefär så här. Men det är därför, är att jag helt enkelt röra minne som inte tillhör mig. Så låt oss försvara mot detta en lite på ett annat sätt genom att titta på det här programmet här. Så, återigen, skelettet som vi såg earlier-- och jag har markerat denna gång int. Och hela denna tid huvud har faktiskt return värde. Även om det i de flesta av våra föredrag exempel vi har aldrig en gång använts tillbaka något i main. Vi skriver bara printf stäng klammerparentes och det är det. Men gratis, vad kompilator gjort för dig, effektivt, återvänder 0 för dig. Slår out-- och det är lite counterintuitive-- att 0 är bra. Det betyder inte att falskt per se. 0 är bra, och alla icke-0 värde, har världen beslutat, kan betyda ett fel. Så om du någonsin har trasslat upp något på din dator, eller ett program har just dött på dig och du har fått en del felaktiga fönster på skärmen, säger fel negativ 49 eller fel 23-- några till synes godtyckligt value-- som är eftersom en programmerare har hårdkodad ett värde som negativt 49 eller positivt 23 för att representera valfritt antal, vågar säga, 4 miljarder möjliga saker som kan gå fel i ett program. Så hur kan jag ta Fördelen med detta själv? Nåväl, låt mig öppna ett program som jag skrev i förväg, och rota runt på nätet som heter hello 4. Och det är nästan identiska, förutom att dess fått en liten bit av felkontroll. I det här fallet har jag återigen förklarade Huvud som att ta två argument, men denna gång, på linje 17, tillkännagivande Jag gör lite av en sanity check. Jag ser till att argc lika lika med 2. För om det är att betyder att jag kan säkert Rör inte bara konsolen 0, men konsolen 1. Och jag gå vidare och skriva ut, i det här fallet, Zamyla eller Rob eller vad ord jag skrivit ut. Och nu bara för att få lite mer korrekt, Jag ska uttryckligen återvända 0 att betyda allt är bra. Inget dåligt hände. Men av konvention, kommer jag att returnera 1, eller ärligt talat alla icke-0 värde, om något gick fel. Nu användaren inte kommer att verkligen märker vad som händer. Faktiskt om jag går in i den här katalogen, vi zooma in och gör hello 4, ./hello-4 Zamyla uppför sig som jag förväntar mig. Men om jag istället inte skriva någonting, ingenting verkar hända, men inte kraschar. Och om jag i stället göra något som Rob är en proctor i Thayer-- delning godtycklig information. Men varsel, argv 1, 2, 3, 4, och 5 ska nu finnas i minnet. Det är också inte vad mitt program förväntar sig, eftersom jag har kontrollerat om argc lika jämlikar 2 eller inte. Så jag nu försvarar mot detta. Nu, som en sidoreplik, vi programmer-- eller snarare vi den users-- aldrig se att 0 eller 1 men med användning av en verktyg som kallas Debugger, eller andra verktyg, som vi får se innan länge, du programmeraren kan faktiskt se vad som kan vara går fel inne i ditt program. Så, några frågor om argc? Yeah. PUBLIK: Jag har sett där de har inte haft karaktären, [ohörbart] sa bara string stjärna d, liksom tecken asterisk kommatecken. Är de likvärdiga här? DAVID MALAN: De är. Så frågan är, har du ibland sett program som denna som inte gör det säga sträng argv bygel utan i stället säga något liknande char stjärna argv fästet. Och det finns även andra varianter som du kan se. De är verkligen likvärdiga. För nu har vi dessa slags utbildning hjul på i form av sträng i CS50 bibliotek, men i drygt en vecka eller så kommer vi att ta bort det obstruktion helt och faktiskt titta på vad röding och stjärnan är, och hur de avser minnet representation i allmänhet. Så vi ska återkomma till det. Övriga frågor om vår argv eller argc? Yeah. PUBLIK: Varför tog det tillbaka ett fel [ohörbart]? DAVID MALAN: Varför gjorde det returnera ett fel only-- oh! I det tidigare fallet, när vi var futzing runt med minne, varför tog det bara returnera ett fel när jag skrev verkligen ett stort nummer? Kort svar är, vi har bara tur. Generellt sett, en dator allokerar minne i bitar, och det gav mig en tillräckligt stor bit som Jag kom undan, utan att det märks, av beröring fäste 2, fäste 3, fäste 50, men så fort jag knuffade min tur, jag gick förbi gränserna för den bit av minnet operativsystemet hade gett mig. Och det är då det klämmas ner och sade nej. Segmente fel. Yeah. PUBLIK: Hur fungerar datorn vet värdet av argc? DAVID MALAN: Hur fungerar Datorn vet värdet av argc? När du kör ett program, det programmet, som på grund av den blinkande prompten är handed uppsättningen av ord som skrivits vid prompten, det var skrivit vid prompten. Och så är det ditt operativsystem system som i huvudsak fyller huvudsakliga argument för dig. Så det är en av de tjänster som att du får, typ av hemlighet under huven av ett operativsystem. Övriga frågor? Yeah. PUBLIK: Vad innebär core dump detta? DAVID MALAN: Vad innebär core dump detta? Så det är en bra fråga. Och låt mig gå tillbaka till här katalogen här. Och du kommer att märka att Jag har en ny fil där. Det verkligen kallas kärna, och det är faktiskt oftast en skaplig storlek fil. Det är i huvudsak en ögonblicksbild av innehållet i min programmets minne eller RAM när den kraschade. Och det ska vara användbart, potentiellt, diagnostiskt, när vi talar i en framtida föreläsning och avsnittet om felsökning, eftersom du faktiskt kan göra det motsvarar ett digitalt obduktion på den filen för att räkna ut vad du gjorde fel i ditt program. Yeah. PUBLIK: Är argc ett kommando i själv, eller kan du namnge det något? DAVID MALAN: Bra fråga. Är argc ett kommando i sig, eller kan du namnge det något? Det är definitivt inte ett kommando. Det är helt enkelt en variabels namn eller ett argument namn, och så absolut vi skulle kunna kalla detta foo, Vi kan kalla detta bar, som tenderar att vara go-to ord som en dator forskare går till. Men av konvention, använder vi argc och argv. Men det är bara en människa konvention, inget mer. Okej. Så visar sig, jag har varit berätta lite av en vit lie-- och ärligt talat, i framtiden, ser du Vi har sagt till andra vita lögner. Men för nu, vi ska att skala upp en av dessa. I det här fallet här när jag tidigare körde ett program som ./hello eller ./hello-3 Zamyla hade vi innehållet i min datorns minne ser ungefär som detta. Men minns vad en sträng är. Vad gjorde vi säga en vecka sedan vad en sträng egentligen är under huven? PUBLIK: Array av tecken. DAVID MALAN: Det är en samling av tecken, eller hur? Så vi kanske har en matris med strängar, men, i sin tur, en sträng är en samling av tecken. Så om jag verkligen vill vara anal när jag drar den här bilden, Jag borde verkligen dra det lite mer så här, varvid i var och en av dessa index av min argv array, det är i sig en hel sträng som själv är i en array. Och nu den vita lögnen Vi säger till idag är att bilden inte ser ganska så här. Faktum är de små rutorna är vanligtvis utanför de stora rektanglar där. Men vi ska återkomma till det inom kort. Men detta är ./hello bakstreck 0, att vara den speciella karaktär som avgränsar änden av en sträng, och vi har en annan efter Zamyla namn. Så vad betyder det? Nåväl, låt mig gå vidare och öppna upp två andra exempel som finns tillgängliga online. En kallas argv1.c och den andra är argv2. Det är ett super-enkelt program som skiljer sig från tidigare program i det nu jag använder argc och argv här uppe. Och nu ska jag integrera med en for-loop i linje 18, från i = 0 på upp till argc. Och vad ska jag göra med denna kodrad här? På engelska. Detta visar uppenbarligen användningen av argc. Men på engelska, vad gör det göra om jag kör det här programmet? Yeah? PUBLIK: Det kommer att skriva ut skärmen så många gånger du vill. DAVID MALAN: Exakt. Så vad ord I skriver vid prompten, det är kommer att spy dem på mig en per rad. Så låt oss gå vidare och göra det. Låt mig gå in i min katalog och gör att argv1 ./argv1. Och nu, låt oss hålla det enkelt. Låt oss inte göra något i början. Det gjorde skriva ut en sak, och det är faktiskt namnet på programmet, eftersom det är i fästet 0. Om jag nu säger foo, det kommer att göra dessa två, och om jag säger foo bar, det kommer att säga dessa tre saker. Nu är något intressant, kanske. Men minns att argv är en array med strängar, men en sträng är en array med tecken, så att vi kan ta upp saker ett snäpp och tillämpa grundläggande logik och gör kod som ser lite mer kryptiskt, visserligen. Men genom att ha en kapslad loop, något som liknar vad du kanske minns från Mario, till exempel, om du gjorde det här sättet. Så nu märker på rad 19, jag är igen iterera över mina argument, från 0 till högst argc. Och nu i linje 21-- jag är låna ett trick från förra week-- Jag kontroll vad som är längd argv bygel i. Jag lagrar det svaret i n. Och då jag integrera från j på upp till n, där j initieras till 0. Så, konvent för räkning. När du har använt i, om du har en kapslad loop, kan du inte använda mig igen, annars kommer du clobber, potentiellt, värdet utsidan av den inre slingan. Så jag använder j av konvention. Vi kan använda k. Om du har mer än k, du förmodligen har för mycket att bygga bo, typiskt. Men nu märker jag printf linjen är något annorlunda. Jag tänker inte skriva ut% s, jag är printing% C, vilket, naturligtvis, är en platshållare för en röding. Och nu märker denna syntax. Nytt. Vi har inte sett det förut. Men logiskt, det betyder bara får den i: e strängen i argv och få den j: te vad? PUBLIKEN: Tecken. DAVID MALAN: Tecken på den strängen. Så genom att använda hakparenteser följt av hakparenteser, detta är dykning först in i argv strängar, och sedan den andra hakparenteser med j är dykning i karaktärerna i att särskild sträng i argv. Och sedan, bara för bra åtgärd, Jag skriver ut en ny linje här. Så nu vill jag gå vidare och öppna upp ett något större fönster så att vi kan se detta i handling. Låt mig gå in i den mappen. Och nu gör att argv-2-- whoops-- göra argv-2, ./argv 2. Enter. Och det är lite svårt att läsas vertikalt, men det är faktiskt namnet på programmet, följt av en tom rad. Låt mig gå vidare och göra foo. På samma sätt svårt att läsa, men det är faktiskt skriver ut ett tecken per rad. Och om jag gör bar, är det nu skriva ut dem rad för rad. Så den takeaway här är inte så mycket att, wow, titta på det här snyggt nya trick där du kan få på innehållet av en array specifika karaktärer, utan snarare hur vi tar dessa grundläggande idéer som indexering i en matris, och sedan indexera in i en array som var i den matris, och bara tillämpa samma idéer till något mer sofistikerade exempel. Men grunderna har verkligen inte ändras, även sedan förra veckan. Nu är detta slags lägligt, i det, minns, i vecka noll vi spelade med en telefonbok som denna. Och även om det inte är uppenbart fysiska papperslappar, du kan slags tänka på en telefonbok som en matris. Visst, om du skulle reimplement denna lappar dessa bitar av papper i en dator, troligen du skulle använda något som en matris för att lagra alla de som namn och nummer från A hela vägen genom Z. Så det här är trevligt, eftersom det tillåter oss en möjlighet, kanske, att tänka på hur du kanske faktiskt genomföra något liknande. Som med ett antal dörrar här. Så om jag kan-- vi behöver en frivilligt att komma vidare upp. Låt oss se. En obekant ansikte kanske, obekant ansikte kanske. Vad sägs om i orange? Här. Orange skjorta, kom upp. Låt oss gå vidare nu och flytta dessa dörrar över åt sidan, flytta dem ur vägen för ett ögonblick. Vad heter du? AJAY: DAVID MALAN: Ajay. David. Trevligt att träffas. Okej. Så vi har bakom dessa sex dörrar digitalt på screen-- eller snarare sju dörrar på screen-- en massa siffror. Och jag har sagt någonting i advance-- överens? AJAY: Ingenting i förväg. DAVID MALAN: Allt jag vill att du gör nu är att hitta för mig, och för oss, verkligen, antalet 50, ett steg i taget. AJAY: Number 50? DAVID MALAN: Antalet 50. Och du kan avslöja vad som finns bakom var och en av dessa dörrar helt enkelt genom att röra den med ett finger. Fan också. [LAUGHTER] [Applåder] Mycket bra gjort. OK. Vi har en härlig present Priset för dig här. Ditt val av filmer som vi diskuterade förra veckan. AJAY: Oh, man. Åh, jag har aldrig sett Spaceballs. DAVID MALAN: Space. Okej. Så håll på bara ett ögonblick. How-- låt oss göra det här en teachable moment-- Hur gick ni tillväga hitta nummer 50? AJAY: Jag valde slumpmässigt. DAVID MALAN: Så du valde slumpmässigt och hade tur. AJAY: Ja. DAVID MALAN: OK. Utmärkt. Så nu hade du inte fått tur, vad annars kan ha hänt bakom dessa dörrar? Så om jag går vidare och avslöja dessa siffror här, de faktiskt är i slumpmässig ordning. Och det bästa du kan ha gjort, ärligt talat, är med i slutändan, i värsta fall, kontroll dem alla. Så du fick super lucky, vilket är inte vad vi skulle kalla en algoritm. Ja, grattis. Men nu let's-- humor mig, om du kunde. Låt oss gå till den här fliken här. Och här skiljer sig siffrorna i tydligt vad som verkar vara en slumpmässig ordning, och de var. Men nu när jag istället anspråk att bakom dessa dörrar är siffror som sorteras. Målet är nu att även hittar oss på numret 50. Men gör det algoritmiskt, och berätta hur du ska om det. Och om du tycker det, hålla dig filmen. Du tycker inte att den, du ger tillbaka den. AJAY: Så jag ska kolla ändarna första, att bestämma om there's-- [Skratt och applåder] DAVID MALAN: Varsågod. Låt oss ta en titt på en av Ajay föregångare, Sean, som inte var riktigt lika tur. OK, så din uppgift här, Sean, är följande. Jag har gömt bakom dessa dörrar nummer sju, men undanstoppad i en del av dessa dörrar liksom även andra icke-negativa tal. Och ditt mål är att tänka på detta övre raden av siffror som bara en array. Du kan en sekvens av bitar papper med siffror bakom sig. Och ditt mål är, bara använder toppen array här, hitta mig på nummer sju. Och vi sedan kommer att kritisera hur du går om att göra det. Hitta oss på nummer sju, tack. Nej 5, 19, 13. Det är inte en kuggfråga. 1. Vid denna punkt är din poäng inte mycket bra, så du kan lika gärna fortsätta. 3. Fortsätt. Ärligt talat, jag kan inte låta bli att undra vad du ens tänka på. SEAN: Jag kan ta från endast den översta raden. DAVID MALAN: Endast den översta raden. Så du har tre kvar. Så hitta mig 7. [PUBLIK ropar FÖRSLAG] Så båda dessa var fantastisk för mycket olika skäl. Så det är där vi slutade för en stund sedan, och nyckeln insikt här var dessa dörrar hade siffror bakom dem som sorterades, den ideala takeaway som är att du kan göra i grunden bättre i denna andra example-- och, faktiskt, var Seans att första försök med slumptal lika before-- men så snart eftersom dessa siffror är sorterade, ungefär som i telefonboken, vad kan du givetvis göra? Eller hur kan du utnyttja den kunskapen? Yeah. PUBLIK: Du går halvvägs [ohörbart]. DAVID MALAN: Ja. Exakt. Så Ajay ursprungliga instinkt var att kontrollera ändarna, som jag minns, och sedan vi slags färdiga exemplet snabbt. Men om vi började göra detta mer metodiskt i den stilen, men börjar kanske i mitten, eftersom de är sorterade, så snart vi avslöja nummer 16, vi därför vet-- och låt oss göra precis det-- vi Därför vet att 50, i dagens fall, har fått vara till höger. Så precis som i vecka noll när Vi slet telefonboken i hälften och kastade hälften av problemet borta, samma idé här. Vi kan kasta Halv av problemet bort. Och förmodligen vad du kan göra algoritmiskt, när du vet att 50 måste vara till höger, om det är någonstans, är försök där, i mitten av de återstående luckorna. Naturligtvis är 50 högre än 42, så vi kan kasta denna återstående fjärdedel av problemet borta, och slutligen identifiera ungefär 50. Men precis som med telefonbok, dessa siffror gavs till oss redan i sorterad ordning, vilket lämnar oss med frågan, hur gör du få saker i sorterade ordning? Och, ärligt talat, till vilket pris? Det är en sak att vara räckte telefonboken och sedan imponera på dina vänner genom att hitta ett telefonnummer riktigt snabbt, eller hur? Riva 32 sidor ut för att hitta en personen av 4000 miljoner sidor, vi sade var ett extremt exempel. Men hur mycket tid tog det Verizon att sortera som telefonbok? Hur lång tid tog det oss att sortera dessa sju siffror? Det är en fråga som vi har hittills helt ignoreras. Så låt oss svara på den frågan nu. Och vi är alla av filmer nu, men vi har en del stress bollar. Om, säg, åtta frivilliga skulle inte ha något emot att gå med oss ​​här uppe? Låt oss gå vidare och göra, vad sägs om fyra av er, tre av er här? Få några nya ansikten. Och fyra av er där? Och nu-- låt oss inte fördomar här-- och nummer åtta hit på slutet. Kom upp. Okej. Så vad vi har för här var och en av er är ett nummer. Om du vill gå framåt, ta det här numret. Vad heter du? ARTIE: Artie. DAVID MALAN: Artie, okej. Du är nummer 1. AMIN: Amin. DAVID MALAN: Amin. David. Du är nummer 2. Och gå vidare, så jag lämnar du pappersarken, rada upp er framför musiken står i samma ordning som där uppe. ANDY: Hej, Andy. DAVID MALAN: Andy, det är trevligt att se dig. Nummer 3. JACOB: Jacob. DAVID MALAN: Jacob, nummer 4. Välkommen ombord. GRANT: Grant. DAVID MALAN: Grant. Nummer 5. Alanna: Alanna. DAVID MALAN: Alanna, nummer 6. FRANCES: Frances. DAVID MALAN: Frances, nummer 7. Och? RACHEL: Rachel. DAVID MALAN: Rachel, nummer 8. Okej. Gå vidare och skaffa dig i denna ordning. Låt mig sätta en återstående notstället på plats. Var behöver du ett stativ? OK. Gå vidare och bara sätta dina nummer där publiken kan se dem, musiken står vänd utåt. Och förhoppningsvis vår första sanity check här-- 4, 2, 6. Oh-oh. Vänta lite. Vi har inte en åtta. Jag behöver vräka dig från exemplet på något sätt. Nej Nej, det är OK. Låt oss se. Vi kan göra detta. Avvakta. Sådär. Korrekt. Okej. Så, nu har vi 8, 1, 3 7, 5. OK. Utmärkt. Så frågan till hands är, på vilken kostnad, och via vilken metod, kan vi faktiskt sortera dessa siffror här så att vi typ av kan arbeta baklänges, i slutändan, och decide-- är det verkligen imponerande, det är verkligen effektiv, att jag kan dela och erövra en telefonbok? Är det verkligen effektivt att Jag kan dela och erövra dessa digitala bitar av papper på bordet, om kanske det kommer att kosta oss en förmögenhet i tid eller energi eller processorcykler att faktiskt få våra data i någon sorterad ordning? Så låt oss ställa den frågan. Så först av, dessa siffror är i ganska mycket slumpmässig ordning, och jag kommer att föreslå en algoritm, eller process som vi kan sortera dessa folks. Jag kommer att närma sig detta ganska naivt. Och jag kommer att känna igen att det är lite av en hel del för mig att linda mig runt hela datauppsättning samtidigt. Men vet du vad? Jag kommer att göra några mycket enkla marginella korrigeringar. 4 och 2 är i ordning, om Målet är att gå från en på upp till 8. Så vet du vad? Jag kommer att ha dig killar byta, om du växlar fysiskt positioner och dina papperslappar. Nu 4 och 6, dessa är i ordning. Jag kommer att lämna dem vara. 6 och 8, som är i ordning. Kommer att lämna dem vara. 8 och1, i ordning. Om ni inte skulle ha något emot att byta. Nu 8 och 3, om ni kunde byta. 8 och 7, om ni kunde byta. Och 8 och 5, om ni kunde byta. Nu är jag klar? Nej, uppenbarligen inte. Men jag har gjort situationen bättre, eller hur? Vad var ditt namn igen, nummer 8? RACHEL: Rachel. DAVID MALAN: Så Rachel har effektivt bubblade upp ganska långt, hela vägen till slutet av min samling av siffror här. Och så att problemet är typ av löst. Nu, helt klart, 2 behöver fortfarande flytta en bit, och 4 samt 6 och 1. Men jag verkar ha fått en lite närmare lösningen. Så låt oss tillämpa samma naiv heuristiska igen. 2 och 4, OK. 4 och 6, OK. 6 och 1, mm-mm. Låt oss byta. 6 och 3, mm-mm. Låt oss byta. 6 och 7 är OK. 7 och 5, nix. Låt oss byta. Och nu 7 och 8. Och vad heter du nu igen? FRANCES: Frances. DAVID MALAN: Frances. Så nu Frances är i ännu bättre ställning, för nu 7 och 8 är korrekt bubblade upp till toppen. Så 2 och 4, OK. 4 och 1, Låt oss byta. 4 och 3, Låt oss byta. 4 och 6, du är OK. 6 och 5, Låt oss byta. Och nu dessa killar är bra. Vi är nästan där. 2 och 1, i ordning, så byta. Och nu vill jag göra en sanity check. 2 och 3, 3 och 4, 4 och 5, 5 och 6, 6 och 7, 8. OK, så vi är klara. Men till vilket pris jag gjorde sortera dessa siffror här? Nå, hur många steg jag gjorde potentiellt tar vid sortering dessa människor? Tja, ska vi återkomma till den frågan. Men, ärligt talat, om du fick lite uttråkad, det är typ av avslöjande i att detta inte var kanske den mest effektiva algoritmen. Och faktiskt, ärligt talat, jag svettas desto mer vandra fram och tillbaka. Det kändes inte särskilt effektiv. Så låt oss prova något annat. Om ni skulle kunna återställas er till dessa åtta värden. Bra jobbat. Låt oss ta en titt digitalt, för bara en stund innan vi prova något annat, på vad som just hände. Här uppe, du är på väg att se en visualisering av dessa åtta människor vari blått och rött barer representera tal. Den högre stapel, det större antalet. Ju kortare bar, desto mindre antal. Och vad du kommer att se är i slumpmässig ordning mer än åtta av dem. Du kommer att se dessa stänger bli sorterade efter samma algoritm, eller en uppsättning instruktioner som vi kallar hädan bubbla slag. Så märker, varje sekund eller så, två barer att tända upp i rött, jämförs av datorn. Och sedan om den stora baren och lilla baren är i ordning, de blir bytte för mig. Nu är det här otroligt tråkiga att titta på detta, förvisso, särskilt länge, men märker takeaway-- stora barer flyttar till höger, små barer som flyttar till vänster. Låt oss avbryta denna process och påskynda denna att vara mycket snabbare, så vi kan få en hög nivå känsla för vad, ja, är bubbelsorterings gör. I själva verket, det bubblar upp till högra sidan av listan, eller matrisen, de större barerna. Och omvänt, de små barer är bubblande sig ner till vänster, om än i en snabbare takt än vad vi tidigare gjorde. Så, svårare att se med människor, men visuellt det är faktiskt det som hände. Men låt oss prova en i grunden annan strategi nu. Låt oss prova en annan algoritm där vi har du Killarna börjar i dessa original positioner, vilket var denna ordning här. Och låt oss gå vidare nu. Och jag kommer att göra något ännu enklare, eller hur? I efterhand byta parvis igen och igen, nästan lite smart. Låt oss göra det hela ännu mer naivt, där om jag vill sortera dessa människor, låt mig bara fortsätta leta för det minsta elementet. Så just nu är 4 på minsta antalet jag sett. Jag kommer att komma ihåg det. Nej, 2 är bättre, och kom ihåg att. 1 är ännu mindre. 3, 7, 5. OK. En-- vad heter du nu igen? ARTIE: Artie. DAVID MALAN: Artie. Så, Artie, gå vidare. Jag kommer att dra dig ur linjen. Om du kunde komma tillbaka hit. Och jag måste göra plats för honom. Vi har en beslutspunkt här. Hur kan vi göra plats för Artie här i början var antalet 1 hör hemma? PUBLIKEN: Shift. DAVID MALAN: OK, vi kunde flytta alla. Men föreslå en optimering. Det känns lite irriterande för mig att fråga fyra personer att flytta hela vägen ner. Vad mer kan jag göra? PUBLIK: Slå dem. DAVID MALAN: Slå dem. Och vad heter du nu igen? JACOB: Jacob. DAVID MALAN: Jacob, flytta. Mycket effektivare bara för att ha Jacob swap platser med Artie, i motsats till att tvinga alla fyra av dessa människor, tack så mycket, till deras rätt läge. Vad är trevligt om Artie nu, han är i sitt rätta läge. Nu gör vi det igen. 2, det är det minsta antalet som jag har sett. 3, 7, 5. OK. 2 är definitivt den minsta. Har du inte göra något arbete. Låt oss göra det igen. 6. Minsta? 8. Nope. 4? Ooh. Låt mig komma ihåg 4. 3. Låt mig komma ihåg 3. 7, 5. Minsta antalet jag har ses på detta pass är 3. Om du skulle komma på ut. Vart ska vi sätta dig? Och vad heter du? Alanna: Alanna. DAVID MALAN: Alanna, vi är kommer att behöva vräka dig. Men det är mer effektiv, att bara byta två personer, än att ha flera personer faktiskt kringgå över. Nu ska göra detta igen. Jag kommer att välja 4, så kom ut. Och vem ska flytta? Nummer 8, förstås. Om jag nu hitta nummer 5, kom ut. Nummer 8 kommer att bli vräkta igen. Nu ska jag hitta nummer 6 på plats. 7 på plats. 8 på plats. Vad vi gjorde just nu är något som kallas val sortera, och om vi visualisera detta, det är kommer att kännas lite annorlunda. Låt oss gå vidare och från denna meny här, här visualization-- låt oss ändra detta att-- kom igen, Firefox. Låt oss ändra detta till val slag. Och låt oss påskynda det som tidigare, och starta visualisering nu. Och denna algoritm har en annan känsla. Vid varje iteration, ärligt talat, är det ännu enklare. Jag är bara att välja det minsta elementet. Nu, ärligt talat, jag fick lite tur att tid, i det att det sorterade supersnabb. Elementen var slumpmässiga. Det är inte, som vi ska så småningom se, i grunden snabbare. Men låt oss se en tredje och sista närmar här om vad som händer. Så låt oss gå vidare och återställa er en sista gång för att vara i denna ordning här. Och nu ska jag vara lite mer smart, bara för att spetsa våra algoritmer. Jag ska göra det här. Jag ska inte gå fram och tillbaka så mycket. Ärligt talat, jag är trött på all denna förflyttnings. Jag kommer bara att ta vad jag är ges i början av listan, och jag kommer att sortera det där och då. Så här är vi. Nummer 4. Jag ska in nummer 4 in i en sorterad lista. Klar. Jag påstår nu, och bara för att göra det mer klart, är denna del av min lista sortering. Det är lite av en dum fordran, utan faktiskt 4 sorteras i en lista med storlek ett. Nu ska jag ta på nummer 2. Nummer 2 Jag kommer nu att sätt in på rätt plats. Så varifrån kommer 2 hör hemma? Självklart, här borta. Så sätt igång och flytta tillbaka, om du kunde. Och varför inte ni bara ta musiken står med dig den här gången. Och låt oss med våld sätter dig i början av listan. Så lite mer arbete. Jag var tvungen att flytta Jacob runt, och vad heter du? AMIN: Amin. DAVID MALAN: Amin. Men åtminstone jag inte gå fram och tillbaka. Jag tar bara saker som jag går. Jag bara sätta in dem på rätt plats. 6, detta är faktiskt ganska lätt. Låt oss sätta in dig där borta, om du ville bara flytta över något. Nummer 8, också ganska lätt. Där borta. Fan också. Nummer 1 kan vi inte bara byta med Amin här, eftersom det kommer att röra upp ordern. Så vi måste vara lite smartare. Så, Artie, om du kunde backa upp för ett ögonblick. Låt oss gå vidare och flytta nu, Till skillnad från våra tidigare algoritmer, att skapa utrymme för Artie just här i början. Så i slutet av dagen, jag är typ av göra vad jag ville undvika tidigare. Och så min algoritm är en slags i omvänd, intellektuellt, från vad det ursprungligen var. Jag gör bara växlingen vid en annan punkt. Nu är jag på 3. Åh, fan. Vi måste göra mer arbete igen. Så låt oss trycka ut dig. Låt oss gå 8, 6, 4-- oh oh-- och 3 kommer att gå där. Så åtminstone små besparingar den här gången. 7, inte för mycket arbete att göra. Så om du vill att pop tillbaka, låt oss sätta in dig. Och slutligen, 5, om du vill pop tillbaka, vi behöver flytta dig, dig, dig, tills fem är på plats. Så nu för att se detta vid en hög nivå grafiskt, låt oss göra denna algoritm visualisering en extra gång. Så skall det vi kallar insättnings slag. Vi ska köra det precis som snabbt, och starta det här. Och den också har en annan känsla. Det slags blir bättre och bättre, men det är aldrig perfekt tills jag går in och smidigt i dessa luckor. Därför att, återigen, jag bara tar det som Jag ges från vänster till höger. Så fick jag inte så lycklig att allt var perfekt. Det är därför vi hade dessa små mispositions som vi fast med tiden. Så alla dessa algoritmer verkar kör på lite olika takt. I själva verket, vilket skulle du säga är den bästa eller den snabbaste hittills? Bubble sort, den första? Urval sortera, den andra? Insticks sortera, den tredje? Jag hör vissa urvals sorterar. Andra tankar? Så visar det sig att alla dessa algoritmer i grunden är lika effektiva som varje other-- eller omvänt, precis som ineffektiv som varandra, eftersom vi kan göra i grunden bättre än alla tre av dessa algoritmer. Och det är lite av en vit lögn, för. när jag säger så effektivt eller som ineffektiv, det är åtminstone för super stora värden på n. När vi har bara åtta personer här, eller kanske ett 50-tal barer på skärmen, Du kommer absolut att märka skillnader bland dessa tre algoritmer. Men som n, antalet personer, eller antalet siffror, eller antalet personer i telefonens bok, eller antalet webbsidor i Googles databas blir större och större, vi får se till att alla dessa tre algoritmer är faktiskt ganska dålig. Och vi kan göra i grunden bättre än så. Låt oss ta en titt, slutligen, på vad dessa algoritmer kanske låter som i samband med några andra såväl i form av detta visualisering här som kommer att presentera oss för ett antal algoritmer. Låt oss gå vidare och gratulerar våra deltagare här, som alla sorterade sig väl. Om du skulle vilja ta en avskedsgåva. Du kan behålla dina nummer också. Och vad du ser, eller snarare hör, nu, är att när vi sätter ljud till var och en av dessa stänger och associera den med programvaran, olika frekvens av ljud, du kan svepa dig mer audioly kring vad var och en av dessa saker se ut. Den första är inför sort [TONER] Det är bubblan slag. [TONER] Urval slag. [TONER] Något som kallas merge sort. [TONER] Gnome slag. [TONER] Det var allt för CS50. Vi kommer att se dig på onsdag. BERÄTTARE: Och nu, "Djupt Tankar, "vid Daven Farnham. Varför är det en for-loop? Varför inte göra det bättre? Jag skulle göra en fem loop. [LAUGHTER]