DAVID MALAN: Oke.
Dus dit is CS50, en dit is nu het begin van week drie.
>> Dus tot nu toe, we hebben het schrijven van programma's in C
dat ziet er een beetje zoiets als dit hier.
Dus hebben we een paar kreeg scherpe omvat bovenaan.
We hebben int, belangrijkste, leegte gekregen, en dan is er iets te doen in het midden,
enkele bit van de code binnen van die functie.
Maar belangrijkste is dat we hebben gezegd hier leegte.
Dus leegte, al die tijd, specificeert dat dit programma, wanneer deze wordt uitgevoerd,
kan alleen worden uitgevoerd via de naam.
U kunt geen andere woorden te typen of getallen achter de naam van het programma, wanneer
actief is.
Dus, bijvoorbeeld, als het programma was gecompileerd in een bestand genaamd hello,
je kon ./hello doen, maar dat is het.
>> De enige manier waarop je zou kunnen geven input voor dit programma
is door te bellen naar een functie.
Bijvoorbeeld, welke functie gebruiken we al tot nu toe
om input van de gebruiker te krijgen?
>> PUBLIEK: Get string.
DAVID MALAN: Om draad te krijgen, of krijgen int, of je hebt anderen gezien,
zelfs als je dat nog niet hebt gebruikt, zoals te lange, lange en dergelijke.
Maar stel dat we eigenlijk willen beginnen
het schrijven van programma's die weinig meer zijn veelzijdig, en, eerlijk gezegd, een beetje meer
zoals de commando's die je hebt gekregen, hopelijk,
een beetje gewend.
Zoals cd ruimte Dropbox.
Dit, natuurlijk, veranderingen uw telefoonboek, in de veronderstelling
je bent in het huis van John Harvard directory, om je Dropbox-map.
Ondertussen, een commando als dit maakt een nieuwe directory genaamd pset2,
zoals je misschien al of zal binnenkort voor het probleem set twee.
Maak Hallo, is natuurlijk een commando dat een programma genaamd bouwt hello
van een bestand genaamd hello punt c.
En in elk van deze gevallen, nu, we hebben gehad
geven een argument zogenaamde command line, de knipperende prompt,
dus dat merk weet wat op te bouwen, en zo dat mkdir weet welke map te creëren,
en zodat cd weet waar je naartoe wilt.
Maar tot nu toe houden we zeggen dat de belangrijkste, je standaard functie,
heeft een leegte uitdrukking binnenkant van deze haakjes
wat betekent dat het kan geen argumenten nemen.
>> Dus vanaf vandaag, wat we gaan doen
is, gaan we beginnen dingen ondersteunen als deze zelfs.
In feite, in dit geval, waar je meestal niet handmatig invoeren,
Maken is dit te doen voor ons, zijn er niet
een maar een, twee, drie extra snaren na het programma met de naam
Clang.
Dus hoe kunnen we dit bereiken?
>> Nou, vanaf vandaag, in gevallen waar we willen
om input te geven via het zogenaamde opdrachtregel
we gaan beginnen met het toevoegen hier wat er in yellow--
leegte te vervangen door int argc komma reeks argv haakje openen haakje sluiten.
Nu is dit interessant voor een paar redenen.
Een, het gaat om ons te laten schrijven programma's die iets dynamischer.
Maar, meer dwingend, het gaat om het openstellen van
Nu een gesprek over wat arrays kan echt
worden gebruikt, wat een tekenreeks echt onder de motorkap,
tot volgende week, wanneer we beginnen met duiken in nog dieper hoe de machine
het maken van al deze dingen werken.
Maar voor nu, laten trekken, misschien een foto.
>> Wanneer u een programma te schrijven met de belangrijkste verklaard
op deze manier, zodat main heeft twee argumenten, een int
en-- welk gegevenstype is het tweede argument?
>> PUBLIEK: Array.
DAVID MALAN: Array.
Dus het ziet er op het eerste gezicht alsof het een snaar, maar let op de vierkante haakjes.
Herinneren de laatste keer dat we geïntroduceerd de notie van een array.
En arrays gebruiken vierkante haken in een paar contexten.
Je zou het plein gebruiken beugels in een array gaan
en krijg een bepaald element, zoals beugel 0 of beugel 1 of beugel 2.
Maar we zagen, als het kort, vorige week dat u ook
Gebruik deze vierkante haken te verklaren de grootte van een array,
als je weet van tevoren hoeveel ints of hoeveel strings of wat je
eigenlijk willen.
Zo blijkt er's een derde context here
dat heeft geen nummer binnen van de vierkante haken.
Wanneer u opgeeft, zoals ik hier heb, de naam van iets als argv,
dat is gewoon een mooie manier om zeggend argument vector, welke
is een mooie manier om te zeggen een reeks van argumenten,
haakje openen haakje sluiten gewoon betekent dat je per se niet
van tevoren weten hoe groot de matrix gaat worden,
maar je weet dat het gaat om een ​​array zijn.
Dus als je niet weet wat de nummer zet het niet daar,
voor de open beugel haakje sluiten betekent dat argv is niet een string,
maar een array van strings.
Dus syntactisch, als je denk vorige week terug,
het is zeer vergelijkbaar met zeggen iets als int leeftijden haakje openen,
en dan is er iets daarna.
Dus wat heeft dit eruit?
Laten we nu een foto te trekken.
Dus als je dit programma met Hoofd draaien hebben twee argumenten binnenkant gedefinieerd
van die haakjes, u hoofdzakelijk ten minste twee brokken
geheugen overhandigd aan u onder de motorkap.
Een, zoals ik kom trekt als deze rechthoek, gaat argc genoemd te worden.
En net als een korte samenvatting, wat is het datatype van argc?
Dus het is een int.
Dus een aantal gaat om te gaan in argc-- bochten
dat staat voor argumenten tellen.
Ondertussen heb ik getekend argv als een array.
En ik weet niet echt hoe lang het gaat worden,
dus met het oog op de huidige dot dot dot.
Het zou kunnen krijgen van wat lengte.
Maar ik heb hier afgebeeld ten minste vier rechthoeken.
Dus argv een stuk van het geheugen dat winkels snaar snaar snaar dot dot dot,
en argc is slechts een brok geheugen voor een geheel getal.
>> Dus nu, laten we een beetje nauwkeuriger.
Als, als ik strings in deze array, genaamd
argv, ik wil bij hen te komen individueel, net als vorige week,
we gaan notatie als argv beugel 0
om het eerste wat krijgen een array.
Argv beugel 1 naar het krijgen tweede ding, enzovoort.
De sleutel is hier dat we nog steeds 0 indexed-- we zijn nog aan het tellen vanaf 0.
Dus laten we nu eigenlijk zet iets in deze.
Als ik een programma genaamd compileren hello van een bestand met de naam hello dot c,
en dan heb ik dat programma uit te voeren met dot slash hallo,
wat doet mijn computer, mijn laptop, lijken onder de motorkap
het moment dat ik run dot slash hallo en druk op Enter?
Nou, dit is misschien wel wat we zouden kunnen omschrijven
als de inhoud van uw computer geheugen, of RAM-- Random Access Memory.
Met andere woorden, de computer, een of andere manier voor u op magische wijze,
zet de nummer 1 in argc, AKA argcount, en het brengt letterlijk de string
./hello in argv beugel 0.
Ik heb geen idee, eerlijk gezegd, wat is in argv beugel 1 of 2 of 3,
want als de gebruiker niet typte iets anders ./hello,
We gaan ervan uit dat deze hoogstwaarschijnlijk vuilnis waarden
zo te zeggen.
Die delen van het geheugen bestaan, maar het is niet aan ons
om te kijken naar hen, omdat de argcount is slechts een.
>> Nu, ondertussen, als ik schrijf een ander programma uit te voeren,
cd, die juister een opdracht in uw knipperende prompt-- cd ruimte
Dropbox-- wanneer ik dat, effectief, wanneer de cd-programma wordt uitgevoerd, argc,
binnenkant van het geheugen van mijn computer, is voor de meest kortste tweede het nummer 2.
En dan argv beugel o heeft cd, argv beugel 1 heeft Dropbox,
en dan natuurlijk het commando voltooit, zodat al dit geheugen
gaat in wezen weg en wordt gebruikt voor iets anders.
En dat is waarom ik zeg slechts een fractie van een seconde.
>> Ondertussen, als we dat doen mkdir pset2, de foto ziet er bijna hetzelfde,
maar met verschillende snaren binnenin argv.
Als ik dat doe clang dash hello hello dot c, hetzelfde idee.
Meer spullen wordt ingevuld voor argv en argc natuurlijk is 4.
Dus met andere woorden, ofschoon deze array
misschien dot dot dot, van sommige variabele lengte, om zo te zeggen,
weet u altijd waar het einde van het is, omdat argc zal u vertellen
op welk punt moet je stoppen te kijken naar elementen in argv.
Je kunt alleen kijken naar vier in totaal in dit geval.
>> Dus laten we nu eens kijken naar, misschien een eenvoudig programma.
Een die gewoon zegt hallo iemand als Zamyla.
Dus ik beweer ik ga een programma te schrijven in slechts een moment via die ik kon doen
./hello ruimte Zamyla, en dan wil ik mijn programma om uit te printen iets
super-simpels als "hallo, Zamyla."
Nu in het verleden hebben we gebruikt getString.
Dus in het verleden, zelfs indien je nieuw bent in het programmeren bent,
kans groot dat u zou kunnen zweep een programma dat gebruik maakt van getString
en gebruikt vervolgens printf goeiedag te zeggen tegen Zamyla.
Maar laten we niet te gebruiken getString deze tijd.
Laat me maar gaan in de Appliant en weet zijn standaard I O dot h.
Laat me ook CS50 dot h.
Int nu de belangrijkste, en nu ben ik niet van plan nietig te doen vandaag.
In plaats daarvan ga ik int argc doen reeks argv geopend beugel dicht beugel,
een aantal niet te specificeren.
En nu hier is mijn zogenaamde te doen.
Wat ik nu ga doen is, ik ben ga een beetje een sprong van het geloof te doen,
Ik ga ervan uit dat de gebruiker ga dit programma correct te gebruiken,
en ik ben gewoon naar doen printf hello,% sn.
Dus niets nieuws.
Maar ik wil nu zetten wat het woord van de types gebruiker achter de naam van het programma.
Dus als ik het doe ./hello ruimte Zamyla, I willen een of andere manier programmatisch toegang
citeer unquote "Zamyla." dus ik kan gaan in mijn betoog vector,
mijn array van strings, en als de opdracht, nogmaals, was ./hello ruimte Zamyla,
Welk nummer moet ik wil hier in argv te zetten?
PUBLIEK: 1.
DAVID MALAN: 1, omdat beugel 0 blijkt
gaat het worden naam van het programma is, zoals we zagen.
Dus beugel 1 is het eerste woord dat ik, de gebruiker heeft getypt.
Ik ga om te gaan en sla dit.
Ik ga in mijn map te gaan waar ik dit bestand heb geplaatst.
Ik ga doen maken hello 3.
OK Comp IO's.
./hello Zamyla Enter.
Wat heb ik verkeerd gedaan?
Ik was verrast mezelf voor slechts een moment daar.
Wat heb ik verkeerd gedaan?
>> PUBLIEK: Naam.
>> DAVID MALAN: Het bestand eigenlijk heet hello3.c.
En ik deed dat alleen voor consistentie, want we hebben
had hello.c's in de verleden in de online code.
Dus laten we dit oplossen ./hello beugel dash 3 Zamyla.
Enter.
En nu hebben we gedag, Zamyla.
Ondertussen kan ik dit veranderen naar zijn Rob, of eigenlijk een ander woord.
>> Maar laten we eens kijken naar een hoek geval.
Wat zou je verwachten dat er zal gebeuren als Ik weet niet de naam van iemand typt op alle?
>> PUBLIEK: Fout.
>> DAVID MALAN: Er is een fout van een soort, misschien.
Laten we eens kijken.
Enter.
Null.
Dus printf wordt daadwerkelijk een beetje beschermend van ons
hier, en letterlijk afdrukken geopend paren null, maar nog erger dingen kunnen gebeuren.
En alleen maar om aan te tonen iets wat je absoluut
niet moet doen, laten we gaan in hier en beginnen rondneuzen.
Rechts?
Als ik weet dat de foto in geheugen wezen dit
argv beugel 1 heeft Zamyla, argv beugel 0 heeft ./hello of ./hello-3.
Wat is in de beugel 2?
Dus ik kan antwoorden dat vraag ik me af, toch?
Ik kan alleen maar veranderen de 1 naar een 2.
Ik kan nu opnieuw compileren hello 3, ./hello3 Laten we in te zoomen en druk op Enter.
Whoops.
Geen aanhalingsteken.
Interessant.
Dus dat is wel cool om te te zien wat er nog meer in hier.
>> Dus wat is de binnenkant van mijn laptop?
Laten we redden het met beugel 3.
Maak hello3, ./hello-3.
Nieuwsgierig.
En laten we nu echt bold-- 50.
Dus dat is echt diep duiken in het geheugen van mijn computer.
50 indexen in.
Dus zorg hello 3 ./hello-3.
Nieuwsgierig.
Oke, nu ben ik gewoon gaat roekeloos krijgen.
Laten we gaan naar 5000.
Oke.
Dus laat me opnieuw te compileren.
Maak hello3, ./hello-3.
OK.
Nu sommigen van jullie, er zou zijn een gloeilamp afgaat.
Hoeveel van jullie hebben eerder gezien dit bericht?
OK.
Ja, waarom?
>> Odds zijn-- en er is anders dingen die dit kan veroorzaken
en duidelijk je in goede company-- we hebben duidelijk
veroorzaakt wat heet een segmentation fault.
En lang verhaal kort te maken voor vandaag, ik een segment van het geheugen aangeraakt
dat ik niet zou moeten hebben.
Wanneer een segment betekent gewoon een brok van het geheugen dat ik niet moeten doen.
Nu de computer garandeert dat als ik lopen ./helloZamyla dat ik argv kan aanraken
zijn beugel 0 en argv beugel 1.
Maar argc waarde 2, dat betekent dat ik ben alleen allowed-- het is een soort van de eer
system-- aan te raken bracket 0 en beugel 1.
Als ik verder ga, is er absoluut gaat geheugen er zijn.
Mijn RAM fysiek bestaan in de computer.
Maar wie weet wat er staat?
Inderdaad, ik ben het uitvoeren van meerdere programma's in een keer.
Ik zou seen-- heb als ik niet Daarbij op Appliant
maar op mijn Mac of PC-- ik zou kunnen hebben gezien de inhoud van de email.
Ik zou een instant hebben gezien boodschap die ik onlangs heb gestuurd.
Iets dat zou kunnen zijn slepende rond in het geheugen
had kunnen worden bereikt door de Deze willekeurige vierkante haakjesnotering.
Of, erger nog, misschien heb je vond een van mijn wachtwoorden
die ik onlangs had getypt in, dat een programma in het geheugen was opgeslagen dat
om me te authenticeren, en dan gewoon een soort van liet het
in RAM totdat ik stop dat programma.
>> En inderdaad, dit is een van het gevaar en een van de bevoegdheden
van het gebruik van een taal als C U heeft vrije toegang
om de volledige inhoud geheugen een programma,
en wat slechteriken kan zelfs doen in die cases--
vooral wanneer we naar web programmeren
tegen het einde van het semester, zullen we Bezoek deze topic-- wordt rondneuzen,
potentieel, iemands computer geheugen en vind zulke merkwaardige dingen
zoals we zagen er.
Of nog erger, wachtwoorden die hij of zij kan vervolgens gebruiken om slechte dingen te doen.
>> Zo duidelijk dat ik niet heb dit gedaan, omdat vreemde dingen beginnen te gebeuren.
Inderdaad is dit een programma crashen.
Dit zou het equivalent zijn van Mac OS of Windows
een programmavenster gewoon verdwijnen.
Er is een onverwachte fout opgetreden.
In de command-line omgeving We zien iets als dit.
Maar dat is de reden waarom, is dat ik gewoon aan te raken geheugen dat niet van mij.
>> Dus laten we verdedigen tegen deze een iets op een andere manier
door te kijken naar het programma hier.
Dus nogmaals, het skelet dat zagen we earlier--
en ik heb deze keer int gemarkeerd.
En al die tijd centraal heeft inderdaad terug een waarde.
Alhoewel in de meeste van onze lezing voorbeelden hebben we nog nooit een keer gebruikt
alles in de belangrijkste terug.
We schrijven printf dicht accolade en dat is het.
Maar gratis, wat de compiler gedaan voor u,
effectief, is terug 0 voor u.
Blijkt out-- en het is een beetje counterintuitive-- dat 0 is goed.
Het betekent niet dat valse per se.
0 is goed, en eventuele niet-0 waarde, heeft de wereld besloten,
kan een fout betekenen.
Dus als je ooit hebt geknoeid iets op uw computer,
of een programma is net overleden op u en u een aantal foutieve raam heb gekregen
op uw scherm, zeggende fout negatieve 49 of fout 23--
sommige schijnbaar willekeurige value-- dat is omdat een programmeur is hard-coded
een waarde als negatief 49 of positief 23 aan een aantal vertegenwoordigen, durf te zeggen,
van 4 miljard mogelijke dingen dat kan het mis in een programma gaan.
>> Dus hoe zou ik nemen voordeel van deze zelf?
Nou, laat ik het openen van een programma dat schreef ik op voorhand,
en snuffel rond in online genaamd hello 4.
En het is bijna identiek, behalve dat het heeft een beetje van de foutcontrole.
In dit geval heb ik weer verklaard belangrijkste als het nemen van twee argumenten,
maar deze keer, op lijn 17, mededeling Ik ben bezig met een beetje een sanity check.
Ik zorg ervoor dat argc gelijk aan gelijk aan 2.
Want als het is, dat betekent dat ik kan veilig
raken niet alleen beugel 0, maar beugel 1.
En ik ga je gang en uit te printen, in dit geval, Zamyla of Rob
of wat dan ook word ik uitgetypt.
En nu alleen maar om iets meer goede,
Ik ga expliciet terug 0 om aan te geven dat alles goed.
Niets ergs gebeurd.
>> Maar volgens afspraak, ik ga return 1, of eerlijk gezegd een niet-waarde 0,
als er iets mis ging.
Nu kan de gebruiker is niet van plan om echt merken wat er gaande is.
Inderdaad, als ik ga in deze map, zoomen we in en doen maken hello 4,
./hello-4 Zamyla gedraagt ​​zoals ik verwacht.
Maar als ik in plaats daarvan niet typen niets, niets lijkt te gebeuren,
maar het niet crasht.
En als ik in plaats daarvan iets doen als Rob is een surveillant
in Thayer-- sharing willekeurige gegevens.
Maar let op, argv 1, 2, 3, 4, en 5 moet nu bestaan ​​in het geheugen.
Ook dat is niet wat mijn programma verwacht,
want ik heb gecontroleerd of argc evenaart gelijken 2 of niet.
Dus ik ben nu verdedigen tegen deze.
>> Nu, als een terzijde, we de programmer-- of liever wij users--
nooit zien dat 0 of 1, maar met behulp van een tool genaamd Debugger, of andere hulpmiddelen,
zoals we zullen zien voordat lang, je de programmeur
daadwerkelijk kan zien wat er zou kunnen zijn fout gaat binnenkant van uw programma.
>> Dus, vragen over argc?
Yeah.
>> PUBLIEK: Ik heb gezien waar ze hebben niet het karakter had, [onverstaanbaar]
net zei reeks ster d, zoals karakter sterretje komma.
Zijn ze gelijk hier?
>> DAVID MALAN: Ze zijn.
Dus de vraag is, heb je af en toe gezien programma's
als deze dat niet doen zeggen reeks argv beugel
maar in plaats daarvan iets te zeggen zoals char ster argv beugel.
En er is zelfs andere varianten die je zou kunnen zien.
Ze zijn inderdaad gelijk.
Voor nu, hebben we deze soort zijwieltjes
op in de vorm van een tekenreeks in de CS50 bibliotheek, maar in iets meer dan een week
of dus we gaan verwijderen die obstructie helemaal en eigenlijk
kijken naar wat de char en de ster zijn, en hoe deze betrekking hebben op het geheugen
representatie algemeen.
Dus we zullen hierop terugkomen.
>> Andere vragen over onze argv of argc?
Yeah.
PUBLIEK: Waarom heeft het terug een fout [onverstaanbaar]?
DAVID MALAN: Waarom deed het een fout terug only-- oh!
In het vorige geval, wanneer we werden rond gepruts met geheugen,
waarom heeft het alleen een fout geretourneerd toen ik echt getypt een groot aantal?
Korte antwoord is, dat we geluk hebben gehad.
Algemeen een computer wijst geheugen in brokken,
en het gaf me een groot genoeg stuk dat Ik kreeg weg, zonder te worden opgemerkt,
aanraken beugel 2, beugel 3, beugel 50, maar zodra ik duwde
mijn geluk, ik ging verder dan de grenzen van het stuk van het geheugen
het besturingssysteem me had gegeven.
En dat is wanneer het geklemd beneden en zei, nee.
Segmentatie fout.
Yeah.
>> Publiek: Hoe werkt de computer kennen de waarde van argc?
>> DAVID MALAN: Hoe werkt het computer kennen de waarde van argc?
Wanneer u een programma te starten, dat programma, door de aard van de knipperende prompt,
wordt overhandigd de array van woorden die zijn getypt
op de prompt, dat was getypt op de prompt.
En zo is uw besturingssysteem systeem dat hoofdzakelijk
bevolkt argumenten belangrijkste is voor jou.
Dus dat is een van de diensten die je krijgt, een soort van geheim
onder de motorkap van een besturingssysteem.
Andere vragen?
Yeah.
>> Publiek: Wat betekent core dump betekenen?
DAVID MALAN: Wat betekent core dump betekenen?
Dus dat is een goede vraag.
En laat me terug gaan in deze map hier.
En je zult merken dat Ik heb een nieuw bestand daar.
Het is inderdaad genoemd kern, en het is eigenlijk meestal een redelijk grote file.
Dat is in wezen een momentopname van de inhoud van het geheugen van mijn programma's
of RAM toen het neerstortte.
En dit zal nuttig zijn, potentieel, diagnostisch,
als we praten in een toekomstig college en sectie over debuggen,
want je kunt eigenlijk doen de equivalent van een digitale autopsie
op dat bestand te helpen erachter te komen wat je fout in je programma deed.
Yeah.
>> PUBLIEK: Is argc een opdracht in zelf, of kun je het noemen iets?
>> DAVID MALAN: Goede vraag.
Is argc een opdracht op zich, of kunt u noemt het iets?
Het is zeker niet een opdracht.
Het is gewoon een variabele naam of de naam van een argument is,
en zo absoluut we kon dit foo noemen,
konden we deze bar, die de neiging hebben te bellen om de go-to woorden die een computer
wetenschapper gaat naar.
Maar volgens afspraak, gebruiken we argc en argv.
Maar dat is slechts een mens conventie, niets meer.
Oke.
Zo blijkt, ben ik geweest vertellen een beetje een witte lie--
en eerlijk gezegd, in de toekomst, je zult zien we hebben verteld andere witte leugens.
Maar voor nu, we gaan om terug te pellen van een van deze.
In dit geval hier toen ik eerder liep een programma zoals ./hello of ./hello-3
Zamyla, hadden we de inhoud van mijn het geheugen van de computer te kijken ongeveer als
deze.
Maar herinneren wat een string is.
Wat hebben we zeggen een week geleden wat een reeks is eigenlijk onder de motorkap?
PUBLIEK: Serie van chars.
DAVID MALAN: Het is een reeks van tekens, toch?
Dus kunnen we een scala aan hebben koorden, maar op zijn beurt een string
een reeks tekens.
Dus als ik echt wil zijn anaal toen ik deze foto te trekken,
Ik moet echt tekenen het een beetje meer als dit,
waarbij in elk van deze indexen van mijn argv array,
er is zelf een hele reeks dat zelf in een array.
En nu het leugentje om bestwil die we vandaag vertellen
is dat het beeld niet kijk dit heel graag.
In feite, de kleine vierkanten meestal buiten de grote rechthoeken
er.
Maar we komen terug om dat vóór lang.
Maar dit is ./hello backslash 0, dat wordt het speciale teken dat
markeert het einde van een koord, en we hebben nog een na kreeg
Naam Zamyla's.
Dus wat betekent dit?
>> Nou, laat me gaan en het openstellen van twee andere voorbeelden
die online beschikbaar zijn.
Een heet argv1.c en de andere is argv2.
Het is een super-eenvoudig programma dat is anders dan het verleden programma's
in dat nu ik gebruik argc en argv hier boven.
En nu ben ik de integratie met een lus in lijn 18, van i = 0 op maximaal argc.
En wat ga ik doen met deze lijn van code hier?
In het Engels.
Dit toont duidelijk het gebruik van argc.
Maar in het Engels, wat doet het doen als ik dit programma uit te voeren?
Yeah?
>> PUBLIEK: Het gaat om afdrukken van uw scherm zo vaak als je wilt.
DAVID MALAN: Precies.
Dus wat woorden die ik Typ bij de prompt, het is
gaat braken ze me aan een per regel.
Dus laten we verder gaan en doen dit.
Laat me gaan in mijn directory en doen maken argv1 ./argv1.
En nu, laten we het simpel houden.
Laten we niets doen op het eerste.
Het deed uitprinten een ding, en dat inderdaad de naam van het programma,
want dat is in beugel 0.
Als ik nu foo zeggen, het gaat om te doen die twee, en als ik zeg foo bar,
het gaat om die drie dingen zeggen.
Nu dat is enigszins interessant, misschien.
Maar herinneren dat argv is een array van strings,
maar een string is een array van chars, zodat we dingen kunnen nemen een inkeping
en toe te passen dat de fundamentele logica en maak beveiligingscode
ziet er een beetje meer cryptisch, toegegeven.
Maar door het hebben van een geneste lus, iets dat verwant is
tot wat je zou herinneren van Mario, bijvoorbeeld, als je dat deed het op deze manier.
>> Dus let nu op lijn 19, ik ben opnieuw itereren over mijn argumenten,
vanaf 0 op maximaal argc.
En nu in de rij 21-- ik ben lenen van een truc van vorig week--
Ik ben het controleren van wat is de lengte van argv beugel i.
Ik ben het opslaan van dat antwoord in n.
En dan ben ik het integreren van j op tot en met n, waarbij j wordt geïnitialiseerd op 0.
Dus, conventie voor het tellen.
Als je eenmaal die ik heb gebruikt, als u een geneste lus, je kunt niet ik opnieuw te gebruiken,
anders zul je afranselen, potentieel, de waarde buiten de binnenste lus.
Dus ik ben met behulp van j volgens afspraak.
We kunnen gebruik maken van k.
Als je meer hebt dan k, heb je waarschijnlijk hebben te veel nesten, meestal.
Maar nu, merkt mijn printf lijn is iets anders.
Ik ben niet aan het afdrukken% s, ik ben bedrukt% c, die natuurlijk
is een tijdelijke aanduiding voor een char.
>> En let nu op deze syntaxis.
Nieuw.
We hebben het nog niet eerder gezien.
Maar logisch, dit betekent gewoon krijgen de i-string argv
en krijgen de j wat?
PUBLIEK: Karakter.
DAVID MALAN: Karakter in die string.
Dus door het gebruik van vierkante haken gevolgd door vierkante haken,
Dit is het duiken eerst in strings argv's,
en vervolgens de tweede vierkante haken met j
is duiken in de karakters van die bepaalde tekenreeks in argv.
En dan, net voor een goede maatregel, Ik ben het afdrukken van een nieuwe lijn hier.
Dus laat me nu gaan en openen een iets groter venster
dus we kunnen dit zien in actie.
Laat me gaan naar die map.
En nu maken argv-2-- whoops-- argv-2 te maken, ./argv 2.
Enter.
En het is een beetje moeilijk verticaal lezen,
maar dat wel de naam van de programma, gevolgd door een lege regel.
Laat me nu ga je gang en doe foo.
Zo ook moeilijk te lezen, maar het is inderdaad het afdrukken van een karakter per regel.
En als ik de bar doen, het is nu bedrukt deze regel voor regel.
Dus het afhaalrestaurant hier is niet zozeer dat, wow, kijk eens naar deze keurige nieuwe truc
waar je kunt krijgen op de inhoud van een reeks van specifieke personages,
maar eerder hoe we nemen deze fundamentele ideeën zoals het indexeren in een array,
en vervolgens indexeren in een array was in die array,
en gewoon het toepassen van dezelfde ideeën te iets meer geavanceerde voorbeelden.
Maar de basis moet echt niet veranderd, zelfs sinds vorige week.
>> Nu is dit soort van tijdige, in dat, herinneren, in week nul
We speelden met een telefoon boek als dit.
En ook al is dit natuurlijk fysieke stukjes papier,
U kunt soort bedenken een telefoonboek als een array.
Zeker, als je om herimplementeren deze stukken deze stukjes papier
in een computer, waarschijnlijk zou je iets gebruiken
als een array al die slaan namen en nummers van een hele weg
door Z. Dus dit is leuk, omdat het stelt ons in de gelegenheid,
misschien, om te overwegen hoe je misschien zoiets daadwerkelijk te implementeren.
Als een reeks deuren here.
Dus als ik could-- we er een nodig hebben vrijwilliger om op te komen.
Laten we eens kijken.
Een onbekend gezicht misschien, onbekende gezicht misschien.
Hoe zit het in oranje?
Hier.
Oranje shirt, kom naar boven.
>> Laten we nu gaan en vooruit deze deuren aan de kant,
gaan deze uit de weg voor een moment.
Wat is je naam?
>> AJAY:
>> DAVID MALAN: Ajay.
David.
Leuk je te ontmoeten.
Oke.
Dus hebben we achter deze zes deuren digitaal op de screen--
of, beter gezegd, zeven deuren aan de screen-- een hele hoop nummers.
En ik heb je niets verteld in advance-- overeengekomen?
AJAY: Niets op voorhand.
DAVID MALAN: Alles wat ik wil dat je doet nu is te vinden voor mij, en voor ons,
echt, het nummer 50, een stap op een moment.
>> AJAY: Nummer 50?
>> DAVID MALAN: Het nummer 50.
En je kan onthullen wat is achter elk van deze deuren
gewoon door het aanraken van het met een vinger.
Damn it. [Lachen]
>> [Applaus]
>> Zeer goed gedaan.
OK.
We hebben een mooie gift prijs voor u hier.
Uw keuze uit films die we besproken vorige week.
>> AJAY: Oh, man.
Oh, ik heb nog nooit gezien Spaceballs.
>> DAVID MALAN: Spaceballs.
Oke.
Dus houd op slechts een moment.
How-- laten we deze een leerzaam moment--
hoe heb je over het vinden van het nummer 50?
AJAY: Ik koos willekeurig.
DAVID MALAN: Dus je hebt gekozen willekeurig en had geluk.
AJAY: Ja.
DAVID MALAN: OK.
Excellent.
Dus nu, had je niet geluk gehad, wat anders
zou achter deze deuren zijn gebeurd?
Dus als ik ga je gang en onthullen deze nummers hier,
ze in werkelijkheid zijn in willekeurige volgorde.
En het beste wat je zou kunnen hebben gedaan, eerlijk gezegd, is door, uiteindelijk,
in het ergste geval, het controleren van ze allemaal.
Dus je hebt super-geluk, dat is niet wat we een algoritme zou noemen.
Ja, congrats.
Maar nu let's-- humor me, als je kon.
Laten we naar het tabblad hier.
En hier zijn de nummers in duidelijk wat lijkt op een willekeurige volgorde zijn,
en ze waren.
Maar nu als ik in plaats daarvan aanspraak dat er achter deze deuren
zijn getallen die zijn gesorteerd.
Het doel is nu om ook vinden wij het getal 50.
Maar doe het algoritmisch, en vertel ons hoe je gaat erover.
En als je het vindt, houdt u de film.
Je vind het niet, geef je het terug.
AJAY: Dus ik ga aan de uiteinden te controleren eerst, om te bepalen of there's--
[Gelach en applaus]
DAVID MALAN: Hier ga je.
Laten we eens een kijkje nemen op een van Ajay's voorgangers,
Sean, die niet zo gelukkig was.
OK, dus even je taak, Sean, is het volgende.
Ik heb achter deze verborgen deuren van de nummer zeven,
maar weggestopt in een aantal van deze deuren alsook andere niet-negatieve getallen.
En je doel is om te denken van deze bovenste rij getallen als onder array.
We zijn gewoon een opeenvolging van stukken papier met nummers achter hen.
En je doel is, alleen met behulp van de top serie hier, vind ik het getal zeven.
En we zijn vervolgens naar kritiek hoe je het gaan doen.
Vind ons het getal zeven, alstublieft.
Nee
5, 19, 13.
Het is geen strikvraag.
1.
Op dit punt je score is niet erg goed, dus je kan net zo goed blijven gaan.
3.
Ga op.
Eerlijk gezegd, ik kan het niet helpen, maar vraag me af wat je ook denkt over.
>> SEAN: ik kan nemen van alleen de bovenste rij.
DAVID Malan: Alleen de bovenste rij.
Dus je hebt drie links.
Dus vind ik 7.
>> [PUBLIEK SCHREEUWT SUGGESTIES]
Dus zowel van die waren geweldig om zeer verschillende redenen.
Dus dit is waar we ophield een moment geleden,
en de sleutel inzicht hier werd deze deuren hadden nummers
achter hen die werden naargelang de ideale afhaalrestaurant waarvoor is dat je zou kunnen doen
fundamenteel beter deze tweede example--
en, inderdaad, dat was Sean's eerste poging met willekeurige getallen
even before-- maar zodra Deze nummers worden gesorteerd,
net als in het telefoonboek, wat kan je natuurlijk doen?
Of hoe kun je die kennis te benutten?
Yeah.
>> PUBLIEK: Je gaat halverwege [onverstaanbaar].
DAVID MALAN: Ja.
Precies.
Dus eerste instinct Ajay was aan de uiteinden te controleren, als ik me goed herinner,
en dan hebben we een soort van afgewerkte voorbeeld snel.
Maar als we begonnen om dit meer te doen methodisch volgens die lijnen,
maar uitgaande misschien in de midden, omdat ze gesorteerd zijn,
zodra we onthullen de nummer 16, we daarom weten--
en laten we precies doen dat-- we Daarom weten dat 50 wordt voor de huidige,
heeft om naar rechts.
Dus net als in week nul wanneer we scheurde het telefoonboek in de helft
en gooide de helft van de probleem weg, hetzelfde idee hier.
We kunnen dit de helft te gooien het probleem weg.
En waarschijnlijk wat u kan algoritmisch doen,
als je eenmaal weet dat 50 moet zijn naar rechts, als het overal,
is te proberen er, in het midden van de overige deuren.
Natuurlijk, 50 hoger dan 42, dus we kunnen
gooi deze resterende kwart van het probleem weg,
en tenslotte identificeren iets als 50.
Maar net als bij de telefoonboek, deze nummers
waren ons reeds gesorteerde volgorde, die ons verlaat
met de vraag, hoe doe je om dingen in de gesorteerde volgorde?
En, eerlijk gezegd, tegen welke kosten?
Het is een ding om te zijn overhandigde het telefoonboek
en dan indruk op je vrienden door het vinden van een telefoonnummer heel snel, toch?
Tranende 32 pagina's uit om een ​​vondst persoon van 4 miljard pagina's,
we zeiden was een extreem voorbeeld.
Maar hoeveel tijd heeft het geduurd Verizon aan dat telefoonboek sorteren?
Hoeveel tijd heeft het ons deze zeven nummers sorteren?
Dat is een vraag die we hebben tot nu toe volledig genegeerd.
>> Dus laten we het antwoord op deze vraag is nu.
En we zijn allemaal uit films nu, maar we hebben wel wat stress ballen.
Als, zeg, acht vrijwilligers zou het niet erg om met ons mee hier?
Laten we verder gaan en doen, wat dacht je van jullie vier, drie van jullie hier?
Krijg een aantal nieuwe gezichten.
En de vier van je daar?
En nu-- laten we niet vooringenomenheid hier-- en nummer acht hier op het einde.
Kom maar naar boven.
Oke.
Dus wat we hier hebben voor ieder van jullie is een nummer.
Als je wilt om te gaan vooruit, neemt dit aantal.
Wat is je naam?
>> ARTIE: Artie.
>> DAVID MALAN: Artie, oke.
Je bent nummer 1.
>> AMIN: Amin.
DAVID MALAN: Amin.
David.
Je bent nummer 2.
En ga je gang, als ik de hand u de vellen papier,
line-up zelf voor de muziek staat in dezelfde volgorde als boven.
>> ANDY: Hoi, Andy.
>> DAVID MALAN: Andy, het is leuk om je te zien.
Nummer 3.
>> JACOB: Jacob.
>> DAVID MALAN: Jacob, nummer 4.
Welkom aan boord.
GRANT: Grant.
DAVID MALAN: Grant.
Nummer 5.
>> ALANNA: Alanna.
>> DAVID MALAN: Alanna, nummer 6.
>> FRANCES: Frances.
DAVID MALAN: Frances, nummer 7.
En?
>> RACHEL: Rachel.
>> DAVID MALAN: Rachel, nummer 8.
Oke.
Ga je gang en krijg je in deze volgorde.
Laat ik een resterende muziekstandaard op zijn plaats.
Waar vind je een stand nodig?
OK.
Ga je gang en zet uw nummers waar het publiek ze kan zien op,
de muziek staan ​​naar buiten gericht.
En hopelijk, onze eerste sanity check hier-- 4, 2, 6.
Oh-oh.
Wacht eens even.
We hebben niet een 8.
Ik moet u te verdrijven uit voorbeeld ergens.
Nee
Nee, dat is OK.
Laten we eens kijken.
We kunnen dit doen.
Stand-by.
Daar gaan we.
Correct.
Oke.
Zo, nu hebben we 8, 1, 3 7, 5.
OK.
Excellent.
>> Dus de vraag aan de hand is, op welke kosten, en via welke methode,
kunnen we eigenlijk sorteren van deze nummers hier zodat wij type terug kunnen werken,
uiteindelijk, en decide-- is het echt indrukwekkend, is het echt efficiënt,
die ik kan verdelen en een telefoonboek te veroveren?
Is het echt efficiënt dat Ik kan verdelen en heersen
die digitale stukken papier op het bord,
of misschien het gaat kosten ons een fortuin in de tijd of energie of CPU-cycli
onze gegevens daadwerkelijk te krijgen in een aantal gesorteerde volgorde?
Dus laten we die vraag stellen.
>> Dus ten eerste, deze nummers zijn in vrijwel willekeurige volgorde,
en ik ga voor te stellen een algoritme, of proces
waarmee we kunnen sorteren van deze mensen.
Ik ga om te benaderen deze vrij naïef.
En ik ga om te erkennen dat is het soort veel voor mij
naar mijn mening wikkel rond de gehele dataset tegelijk.
Maar weet je wat?
Ik ga wat doen heel simpel marginale fixes.
4 en 2 zijn niet in orde, als de doel is om van 1 op maximaal 8.
Dus weet je wat?
Ik ga u hebt jongens wisselen, indien je kiest
fysiek posities en je stukjes papier.
Nu 4 en 6, deze zijn in orde.
Ik ga om te vertrekken die zijn.
6 en 8, die in orde.
Gaan laat ze zijn.
8 and1, buiten de orde.
Als u twee zou het niet erg te ruilen.
Nu 8 en 3, als jullie konden wisselen.
8 en 7, als jullie konden wisselen.
En 8 en 5, als jullie konden wisselen.
>> Nu ben ik klaar?
Nee, natuurlijk niet.
Maar ik heb gemaakt van de situatie beter, toch?
Wat was je naam ook alweer, nummer 8?
>> RACHEL: Rachel.
DAVID MALAN: Dus Rachel heeft effectief borrelde vrij ver,
helemaal tot het einde van mijn matrix van getallen hier.
En dus dat probleem is een beetje opgelost.
Nu duidelijk, 2 moet nog verplaatsen van een bit, en 4 en 6 en 1.
Maar ik schijn te hebben gekregen van een iets dichter bij de oplossing.
Dus laten we deze zelfde toepassing naïeve heuristische weer.
2 en 4, op OK.
4 en 6, OK.
6 en 1 mm mm.
Laten we ruilen.
6 en 3 mm-mm.
Laten we ruilen.
6 en 7 is OK.
7 en 5, nope.
Laten we ruilen.
En nu 7 en 8.
En hoe heet je ook alweer?
FRANCES: Frances.
DAVID MALAN: Frances.
Dus nu Frances is zelfs een betere positie, want nu 7 en 8
correct borrelde omhoog naar de top.
Dus 2 en 4, op OK.
4 en 1, swap laten we.
4 en 3, swap laten we.
4 en 6, jij bent OK.
6 en 5, swap laten we.
En nu die jongens zijn goed.
We zijn er bijna.
2 en 1, in de juiste volgorde, dus wisselen.
En nu laat ik doe een sanity check.
2 en 3, 3 en 4, 4 en 5, 5 en 6, 6 en 7, 8.
OK, dus we zijn klaar.
>> Maar tegen welke prijs heb ik sorteren van deze nummers hier?
Nou, hoeveel stappen heb ik potentieel nemen bij het sorteren van deze mensen?
Nou, we komen zeker terug op die vraag komen.
Maar, eerlijk gezegd, als je echt een beetje vervelen, dat is
soort onthullen in dat dit niet was misschien wel de meest efficiënte algoritme.
En inderdaad, eerlijk gezegd, ik zweet des heen en weer.
Dat voelde niet bijzonder efficiënt.
Dus laten we iets anders proberen.
Als jullie kunnen resetten jezelf aan deze acht waarden.
Good job.
>> Laten we eens een kijkje nemen digitaal, voor slechts even voordat we iets anders proberen,
bij wat er net gebeurd.
Hier, op het punt om een ​​te zien ben je visualisatie van deze acht mensen
waarbij blauw en rood balken geven getallen.
Hoe hoger de balk, hoe groter het getal.
Hoe korter de balk, hoe kleiner het getal.
En wat je gaat zien is in willekeurige volgorde meer dan acht van hen.
Je gaat naar deze bars te zien krijgen naargelang hun datzelfde algoritme,
of een reeks van instructies, die we zullen voortaan noemen bubble sort.
Dus merken, elke seconde of zo, twee bars zijn verlichting in rood,
worden vergeleken door de computer.
En als de grote bar en kleine bar zijn buiten de orde,
ze worden geruild voor mij.
>> Nu is dit ongelooflijk vervelend dit kijken maar,
voor heel lang, maar let op de takeaway-- grote balken naar rechts beweegt,
kleine bars naar links te bewegen.
Laten we breken dit proces en dit niet sneller
om veel sneller te zijn, zodat we kunnen krijgen een hoog niveau begrijpen wat,
inderdaad, bubble sort doet.
Inderdaad, het borrelen aan de rechterkant van de lijst,
of de matrix, de grotere bars.
En omgekeerd, de kleine bars zijn borrelende hun weg naar beneden naar links,
zij het in een sneller tempo dan we voorheen deden.
Dus, moeilijker te zien met mensen, maar visueel dat is inderdaad wat
er gebeurde.
>> Maar laten we proberen een fundamenteel andere aanpak nu.
Laten we proberen een andere algoritme waarbij we u
jongens beginnen in deze originele posities, die deze opdracht hier was.
En laten we gaan nu vooruit.
En ik ga iets doen nog eenvoudiger, toch?
Achteraf weer swappen paarsgewijze en weer, bijna een beetje slim.
Laten we de dingen doen, zelfs meer naïef, waar als ik wil deze mensen te sorteren,
laat me gewoon blijven kijken het kleinste element.
Dus op dit moment, 4 is de kleinste aantal die ik heb gezien.
Ik ga om te onthouden.
Nee, 2 is beter, en onthoud dat.
1 nog kleiner.
3, 7, 5.
OK.
Een-- hoe heet je ook alweer?
>> ARTIE: Artie.
>> DAVID MALAN: Artie.
Dus, Artie, ga je gang.
Ik ga je uit de lijn.
Als je hier terug zou komen.
En ik moet om ruimte te maken voor hem.
We hebben een beslissing punt hier.
Hoe kunnen we ruimte maken voor Artie hier aan het begin waar de nummer 1 hoort?
>> PUBLIEK: Shift.
>> DAVID MALAN: OK, we iedereen kan verschuiven.
Maar stel een optimalisatie.
Dat voelt een beetje vervelend voor mij om vier mensen te vragen
om helemaal naar beneden te verplaatsen.
Wat kon ik doen?
>> PUBLIEK: Schakel hen.
>> DAVID MALAN: Schakel hen.
En hoe heet je ook alweer?
>> JACOB: Jacob.
DAVID MALAN: Jacob, te verplaatsen.
Veel efficiënter alleen maar om Jacob swap locaties met Artie,
tegenover dwingen alle vier van deze mensen,
dank u zeer, om de juiste positie.
Wat er leuk is aan Artie nu, hij is in zijn juiste positie.
Laten we dit nog een keer doen.
2, dat is het kleinste aantal die ik heb gezien.
3, 7, 5.
OK.
2 is zeker de kleinste.
Hoeft niet aan een werk te doen.
Laten we het nog eens doen.
6.
Kleinst?
8.
Nope.
4?
Ooh.
Laat me herinneren 4.
3.
Laat me niet vergeten 3.
7, 5.
Kleinste getal Ik heb gezien op deze pas is 3.
Als je uit zou komen op.
Waar gaan we je?
En wat is uw naam?
>> ALANNA: Alanna.
>> DAVID MALAN: Alanna, we zijn gaat te hebben om u te verdrijven.
Dat is efficiënter, om gewoon ruilen twee mensen,
dan meerdere mensen eigenlijk omzeilen via.
Laten we nu weer doen.
Ik ga om 4, dus kom naar buiten.
En wie gaat verhuizen?
Nummer 8, natuurlijk.
Als ik nu nummer 5, kom naar buiten.
Nummer 8 gaat meer de weg gezet.
Ik ga nu naar nummer 6 vinden op zijn plaats.
7 op zijn plaats.
8 plaats.
>> Wat we nu hebben is gewoon iets genaamd selectie sorteren
en als we dit te visualiseren, is het gaat een beetje anders te voelen.
Laten we verder gaan en uit deze menu hier, dit visualization--
laten we dit veranderen om-- kom op, Firefox.
Laten we dit veranderen in selectie sorteren.
En laten we het versnellen als voorheen, en nu beginnen de visualisatie.
En dit algoritme heeft een andere sfeer.
Op elke iteratie, eerlijk gezegd, is het nog eenvoudiger.
Ik ben gewoon het selecteren van het kleinste element.
Nu, eerlijk gezegd, ik heb een beetje geluk gehad dat tijd, omdat het gesorteerd supersnelle.
De elementen waren willekeurig.
Het is niet, zoals we zullen uiteindelijk zie fundamenteel sneller.
Maar laten we eens kijken een derde en laatste benaderen hier over wat er gaande is.
Dus laten we verder gaan en reset jullie een laatste keer te zijn in deze orde hier.
>> En nu, ik ga een beetje slimmer,
gewoon voor de ronde van onze algoritmes.
Ik ga dit doen.
Ik ga niet gaan heen en weer zo veel.
Eerlijk gezegd, ik ben moe van dit alles het oversteken.
Ik ga gewoon om te nemen wat ik ben gegeven aan het begin van de lijst
en ik ga om te sorteren dat toen en daar.
Dus hier zijn we.
Nummer 4.
Ik ga cijfer wilt invoegen 4 in een gesorteerde lijst.
Gedaan.
Ik eis nu, en alleen maar om dit meer te maken duidelijk, is dit deel van mijn lijst gesorteerd worden.
Het is een beetje een domme claim, maar inderdaad 4 wordt gesorteerd in een lijst van maat one.
Nu ga ik op nummer 2 te nemen.
Nummer 2 Ik ga nu invoegen in de goede plaats.
Dus waar komt 2 thuis?
Uiteraard, hier.
Dus ga je gang en terug te gaan, als je kon.
En waarom gaan jullie niet gewoon uw muziek staat met je deze keer.
En laten we met kracht plaatst u in het begin van de lijst.
Dus een beetje meer werk.
Ik moest Jacob bewegen, en wat is uw naam?
>> AMIN: Amin.
>> DAVID MALAN: Amin.
Maar in ieder geval heb ik niet heen en weer gaan.
Ik ben gewoon het nemen van dingen als ik ga.
Ik ga ze gewoon invoegen op de juiste plaats.
6, dit is eigenlijk vrij eenvoudig.
Laten steek je daar, als je wilde alleen maar iets meer dan te bewegen.
Nummer 8, ook vrij gemakkelijk.
Daar.
Damn it.
Nummer 1 kunnen we niet alleen ruilen met Amin hier,
want dat gaat te verknoeien de orde.
Dus we moeten een beetje slimmer zijn.
Dus, Artie, als je zou kunnen een back-up voor een moment.
Laten we verder gaan en shift nu, in tegenstelling tot onze eerdere algoritmen,
om ruimte voor Artie maken hier bij het begin.
Dus aan het eind van de dag, ik ben een beetje doen wat ik wilde voordat vermijden.
En dus mijn algoritme is een soort of omgekeerd, intellectueel,
van wat het oorspronkelijk was.
Ik doe gewoon het verschuiven op een ander punt.
Nu ben ik op 3.
Oh, verdomme.
We moeten meer werk opnieuw te doen.
Dus laten we duwen je uit.
Laten we verder gaan 8, 6, 4-- oh oh-- en 3 gaat naar daar te gaan.
Dus op zijn minst lichte besparingen deze keer.
7, niet te veel werk te doen.
Dus als je wilt pop terug, laten we u invoegt.
En tot slot, 5, als je terug willen knallen, we
moet je verschuiven, u, u, tot vijf is op zijn plaats.
>> Dus nu om dit te zien op een hoog niveau grafisch,
laten we dit algoritme visualisatie een extra tijd.
Zo zullen deze wij insertion sort noemen.
We zullen het uit te voeren net zo snel, en hier begint het.
En het ook, heeft een ander gevoel.
Het is een soort van steeds beter en beter, maar het is nooit perfect
totdat ik naar binnen en glad in deze lacunes.
Want, nogmaals, ik ben alleen te nemen wat Ik word gezien van links naar rechts.
Dus ik heb niet zo gelukkig krijgen dat alles perfect was.
Daarom hebben we deze kleine had mispositions dat we vast in de tijd.
>> Dus al deze algoritmen lijken draaien op iets verschillend tempo.
In feite, wat zou je dan zeggen is de beste of de snelste tot nu toe?
Bubble sort, de eerste?
Selectie soort, de tweede?
Insertion sort, de derde?
Ik hoor sommige selectie soorten.
Andere gedachten?
>> Dus het blijkt dat al deze algoritmes
fundamenteel net zo efficiënt als elke other-- of, omgekeerd, zoals
inefficiënt elkaar, omdat wij fundamenteel doen
beter dan alle drie van deze algoritmen.
En dat is een beetje een leugentje om bestwil, ook.
als ik zeg zo efficiënt of als inefficiënt,
dat althans super-grote waarden van n.
Toen we hebben slechts acht mensen hier, of misschien 50 of zo balken op het scherm,
u zult absoluut merken verschillen tussen deze drie algoritmen.
Maar als n, het aantal mensen, of het aantal getallen,
of het aantal mensen dat in de telefoon boek, of het aantal webpagina's
in Google's databank wordt groter en groter,
we zullen zien dat alle drie van deze algoritmen zijn eigenlijk vrij slecht.
En we fundamenteel kunnen doen beter dan dat.
>> Laten we eens een kijkje nemen, ten slotte, wat deze algoritmen misschien
klinken in de context van een paar anderen
alsmede via deze visualisatie hier
die ons laat kennismaken met een aantal algoritmen.
Laten we verder gaan en feliciteren onze deelnemers hier, die allen
naargelang zich heel goed.
Indien u graag een afscheidscadeau te nemen.
U kunt uw nummers blijven ook.
En wat je ziet, of liever hoort nu,
is dat als we stellen geluiden elk van deze staven
en associëren het met de software, verschillende geluidsfrequenties,
u kunt uw gedachten meer audioly wrap rond wat elk van deze dingen
lijken.
De eerste is insertion sort
>> [MELODIE]
>> Dit is bubble sort.
>> [MELODIE]
>> Selectie soort.
>> [MELODIE]
>> Iets genaamd merge sort.
>> [MELODIE]
>> Gnome soort.
>> [MELODIE]
>> Dat is het voor CS50.
Wij zullen u op woensdag.
>> Verteller: En nu, "Deep Gedachten, "door Daven Farnham.
Waarom is het een lus?
Waarom niet het beter te maken?
Ik zou een vijf lus te maken.
>> [Lachen]