DAVID Malan: Добре. Така че това е CS50, а това е Сега началото на три седмици. Така че до сега, ние сме писането на програми в C че изглежда малко нещо като това тук. Така че ние имаме няколко остър включва в горната част. Имаме INT, основен, недействителни, и тогава нещо да се направи в средата, някои малко код вътре на тази функция. Но ключ е факта, че ние сме били каза нищожен тук. Така невалидни, всичко това време, уточнява че тази програма, когато тичам, може да се управлява само чрез името си. Вие не можете да въведете други думи или номера след името на програмата, когато тя работи. Така, например, ако програмата бяха компилирано в файл наречен здравей, бихте могли да направите ./hello, но това е то. Единственият начин, по който би могъл предоставя информация за тази програма е като се обадите функция. Например, каква функция сме използвали досега за да получите информация от потребителя? АУДИТОРИЯ: Вземете низ. DAVID Malan: За да получите низ, или получите INT, или сте виждали други, дори ако не сте ги използват все още, като се дълго и подобни. Но да предположим, че ние действително искате да започнете писане на програми, които са малко по- гъвкав, и, честно казано, малко по- като командите, които сте Получавам, да се надяваме, малко свикнали да. Подобно на CD пространство Dropbox. Това, разбира се, промени директория, приемайки вие сте в дома на Джон Харвард директорията, в папката Dropbox. В същото време, команда като тази създава нова директория, наречена pset2, Както може би вече или скоро за проблем ще създаде две. Направете Здравейте, разбира се, е заповед която изгражда една програма, наречена здравей от файл, наречен здравей точка в. И във всяка от тези случаи, сега, сме имали даде аргумент на така наречените командния ред, на мига ред, така че марка знае какво да се изгради и т.н. че защитен режим знае коя папка да се създаде, и така, че CD знае където искате да отидете. Но до сега, ние продължаваме да казва че основната, вашата функция по подразбиране, има израз празнота вътре в тези скоби което означава, че не може да вземе никакви аргументи. Така че, започвайки от днес, това, което ние ще направим е, ние ще започнем подкрепа на неща като това дори. В действителност, в този случай, който ви не обикновено ръчно въвеждате, Уверете се е правил това за нас, там не са един, но един, два, три допълнителни струни след програмата на име трясък. И как ще се постигне това? Е, започвайки от днес, в случаите, когато искаме да даде своя принос чрез т.нар команди, отиваме да започнете да добавяте тук какво има в yellow-- подмяна нищожен с INT argc запетая струнен argv отворена скоба близо скоба. Сега това е интересно в продължение на няколко причини. Едно, че ще ходи да ни пишете програми, които са малко по-динамична. Но, по-интригуващи, това ще се отвори сега един разговор, че да какво масиви наистина може да да се използва, за какво низ наистина е под капака, до следващата седмица, когато ще започнем гмуркане в още по-дълбоко за това как машината е прави всички тези неща работа. Но за сега, нека да се направи, може би, една картина. Когато се напише програма с основен предмет на декларираната По този начин, така че основната отнема два аргумента, с вътр и-- какъв тип данни е вторият аргумент? АУДИТОРИЯ: Array. DAVID Malan: Array. Така изглежда на пръв поглед като че ли е по- низ, но забележите квадратните скоби. Спомнете си последния път, когато се въвежда понятието за масив. И масиви използват квадратни скоби в няколко ситуации. Може да се използва на площада скоби, за да отидат в масив и да получите даден елемент, като скоба 0 или скоба 1 или скоба 2. Но видяхме, ако за кратко, миналата седмица, че вие ​​също използвате тези квадратни скоби до декларират размера на масива, ако знаете предварително колко цели числа или колко струни или каквото и да всъщност искат. Така се оказва, че има трета контекст тук че не разполага с редица вътре на квадратните скоби. Когато сте задали, като имам тук, името на нещо като argv, който е само един луксозен начин на казвайки аргумент вектор, който е друг луксозен начин на казвайки масив от аргументи, отворена скоба близо скоба просто означава, че не е задължително знае предварително колко е голям масива ще бъде, но ти знаеш, че ще бъде масив. Така че, ако не знаете номер не го сложи там, за отворена скоба близо скоба означава, че argv не е низ, но масив от низове. Така синтактично, ако сте мисля върна миналата седмица, това е много подобен на казвайки: нещо като вътр възрасти отворена скоба, и след това нещо след това. И така, какво означава това изглежда? Нека наистина да се направи снимка. Така че, когато стартирате тази програма с Main като два аргумента, определени в на тези скоби, те по същество най-малко две парчета памет подаде на вас под предния капак. One, като аз ще привлича като този правоъгълник, ще се нарича argc. И точно като бърза рекапитулация, какъв е типа данни на argc? Така че това е едно цяло число. Така че един брой ще да отида в argc-- завои , че стои за броене аргумент. Междувременно, аз съм съставен argv като масив. И аз наистина не знам колко време ще бъде, Така че за днешните цели Дот дот точка. Това може да получите на някои дължина. Но аз съм на снимката тук най-малко четири правоъгълници. Така argv парче памет, която съхранява низ низ низ точка, точка точка, и argc е само едно парче памет за цяло число. Така че сега, нека да бъдем малко по-точни. Ако, когато имам струни в този масив, наречен argv, искам да стигна до тях индивидуално, точно както миналата седмица, ние ще използваме нотация като argv конзола 0 за да получите първото нещо масив. Argv скоба 1, за да получите Второто нещо, и така нататък. Ключът тук е, че сме все още 0 indexed-- ние сме все още се брои от 0. Така че сега е нека действително сложи нещо в това. Ако аз трябваше да се състави програма, наречена Здравейте от един файл, наречен здравей точка C, и след това пускам тази програма с точка наклонена черта здравей, какво прави на компютъра ми, моя лаптоп, изглежда като под капака момента, в който стартирате точка наклонена черта здравей и натиснете Enter? Е, това е може би това, което бихме могли да опишем като съдържание на вашия компютър памет, или RAM-- Random Access Memory. С други думи, на компютъра, по някакъв начин за вас магически, поставя номер 1 в argc, AKA argcount, и го слага буквално низа ./hello в argv скоба 0. Нямам представа, честно казано, това, което е в argv скоба 1 или 2, или 3, защото, ако потребителят не разполага с написали нищо освен ./hello, отиваме да се предположи, че тези са най-вероятните стойности за боклук, така да се каже. Тези парчета на паметта съществува, но тя не е до нас да ги гледаш, защото на argcount е само един. Сега, междувременно, ако напиши стартирате друга програма, CD, което е по-правилно команда, в мига prompt-- CD пространство Dropbox-- когато аз тичам, че ефективно, когато програмата CD се управлява, argc, в памет на моя компютър, е за най-кратките секунди номер 2. И тогава argv скоба о има CD, argv конзола 1 има Dropbox, и след това разбира се командата допълва, така че всички на тази памет по същество си отива и се използва за нещо друго. И затова казвам само за частица от секундата. В същото време, ако ние не направим защитен режим pset2, картината изглежда почти същото, но с различни струни вътре argv. Ако го направя трясък тире здравей здравей точка С, същата идея. Повече неща се попълва за argv и argc, разбира се, е 4. С други думи, въпреки че този масив може да бъде точка, точка, точка, на някои променлива дължина, така да се каже, Вие винаги знаете къде в края на това е, защото argc няма да ви кажа, в кой момент трябва да спреш гледаш елементи в argv. Можете да търсите само в четири общо в този случай. Така че нека сега да погледнем, може би, една проста програма. Едно, че просто казва здравей до някой като Zamyla. Така че аз твърдя, аз отивам да се напише програма в един момент, чрез който мога да направя ./hello пространство Zamyla, и след това искам моята програма, за да разпечатате нещо супер-просто като "здравей, Zamyla." Сега в миналото сме използвали getstring. Така че в миналото, дори ако сте нов в програмирането, шансовете са, можете да привличам програма, която използва getstring и след това използва ФОРМАТ да кажа здрасти на Zamyla. Но нека не се използва getstring това време. Нека вместо да отидат в Appliant и не включват стандартни I O точка з. Позволете ми също така да включва CS50 точка з. Сега INT главната, и сега съм Няма да правя недействителен днес. Вместо това, аз ще направя INT argc струнен argv отворена скоба близо скоба, не се посочват редица. И сега тук е моята т.нар да правя. Това, което аз отивам да направя сега е, аз съм Ще направя малко на скок на вярата, Отивам да се предположи, че на потребителя възнамерявате да използвате правилно тази програма, и аз съм просто ще направи ФОРМАТ здравей,% калай. Така че нищо ново там. Но аз искам да се тури каквото и дума за типове потребители след името на програмата. Така че, ако го направя ./hello пространство Zamyla, I Искам по някакъв начин да програмно достъп цитирам цитата "Zamyla." така че аз мога да отида в моя аргумент вектор, ми масив от низове, и ако командата, отново, беше ./hello пространство Zamyla, кой номер искам да се постави в argv тук? АУДИТОРИЯ: 1. DAVID Malan: 1, защото скоба 0 Оказва се, ще бъде на име на програмата, както видяхме. Така конзола 1 е първата дума че аз, потребителя, сте написали. Отивам да вървим напред и да спаси това. Отивам да отидат в моята папка къде съм поставен този файл. Отивам да правя направи здравей 3. OK Comp Йо. ./hello Zamyla Enter. Какво съм направил погрешно? Бях изненада себе си само за миг там. Какво съм направил погрешно? АУДИТОРИЯ: Name. DAVID Malan: Файлът е всъщност нарича hello3.c. И го направих само за консистенция, защото сме имали hello.c има в минало в онлайн код. Така че нека да се определи това ./hello скоба тире 3 Zamyla. Enter. И сега имаме здравей, Zamyla. Междувременно, мога да променя това, за да бъде Роб, или наистина всяка друга дума. Но нека да разгледаме случай корнер. Какво може да очаквате да се случи, ако Аз не въведете име на някого изобщо? АУДИТОРИЯ: Грешка. DAVID Malan: Една грешка от някакъв вид, може би. Нека да видим. Enter. Null. Така ФОРМАТ действително се малко защитен от нас тук, и буквално печат отворени скоба нищожна, но дори и по-лоши неща могат да се случат. И само за да докаже, ви нещо абсолютно не трябва да правят, да вървим в тук и да започнете да изпълзяват наоколо. Така ли е? Ако знам, че картината в памет е по същество това, argv конзола 1 има Zamyla, argv скоба 0 има ./hello или ./hello-3. Какво е в скоба 2? Така че мога да отговоря на този самият въпрос, нали? Мога само да се промени една до две. Сега мога да прекомпилирате здравей 3, ./hello3 Нека да увеличите и натиснете Enter. Опа. Не цитирам марки. Интересно. Така че това е нещо готино да да видим какво друго е тук. Така че какво друго е вътре в моя лаптоп? Нека да го спаси със скоба 3. Направете hello3, ./hello-3. Curious. А сега нека да получите наистина bold-- 50. Така че това е наистина дълбоко гмуркане в памет на моя компютър. 50 индекси вътре. Така направи здравей 3 ./hello-3. Curious. Добре, сега аз съм просто ще получите безразсъдно. Да отидем в 5000. Добре. Така че нека да прекомпилирате. Направете hello3, ./hello-3. OK. Сега някои от вас, има мощ е една крушка излизането. Колко от вас имат виждал това съобщение преди? OK. Така че, защо? Коефициенти are-- и има различни неща, които могат да доведат до това, и ясно, че сте в добро company-- имаме ясно причинено което се нарича сегментиране вина. И дълга история кратко за днес, аз са се докоснали един сегмент на паметта че не трябва да има. Когато сегмент просто означава парче на паметта, че не трябва да има. Сега компютъра гарантира, че ако тичам ./helloZamyla, че мога да се докоснат argv бъде скоба 0 и argv скоба 1. Но argc е на стойност 2, това означава, че аз съм само allowed-- това е нещо на честта system-- да се докоснат скоба 0 и скоба 1. Ако отида по-далеч, има абсолютно щеше да бъде памет там. My RAM съществува физически в компютъра. Но кой знае какво е там? Всъщност, аз съм работят с няколко програми наведнъж. Може би имам seen-- ако не бяха Правейки това на Appliant но на моя Mac или PC-- да имам види съдържанието на електронната поща. Може да съм видял един миг съобщение Аз бях наскоро е изпратил. Всичко, което може да бъде спиращ около в паметта може да са достъпни чрез тази произволна квадратна скоба нотация. Или, още по-лошо, може да се наложи Намерих един от моите пароли че бих наскоро написа в, че програма се съхранява в паметта, така че да ме разпознаете, и тогава просто вид го напусна в RAM, докато не се откажат от тази програма. И наистина, това е един от опасността и един правомощията за използване на език като C. Имате свободен достъп на цялото съдържание памет на дадена програма, и какви лоши момчета може дори направи в тези cases-- особено когато ние стигнем до уеб програмиране към края на семестъра, ние ще преразгледа този topic-- се мушкам наоколо, потенциално, някой е компютър памет и да намерят такива любопитни неща както видяхме там. Или дори още по-лошо, пароли, които той или тя може да използва, за да направи лоши неща. Затова е ясно, че не е трябвало да направи това, защото странни неща започват да се случи. В действителност, това е програма трясък. Това ще бъде равностойността на Mac OS или Windows прозореца на програмата просто изчезват. Възникнала е неочаквана грешка. В средата на командния ред ние виждаме нещо подобно. Но това е защо, е, че съм просто докосване памет, която не принадлежи на мен. Така че нека да се защитава срещу този на малко по различен начин , като погледнете в тази програма тук. Така, отново, скелета че видяхме earlier-- и съм подчертала този път вътр. И през цялото това време основната има наистина връща стойност. Въпреки че в повечето от нашата лекция примери ние никога не съм използвал веднъж върне нещо в основния. Ние просто напишете ФОРМАТ близо фигурна скоба и това е всичко. Но безплатно, какво по съставител е правил за теб, ефективно, се връща 0 за вас. Оказа out-- и че е малко counterintuitive-- че 0 е добро. Това не означава фалшиво по себе си. 0 е добро, и всеки не-0 стойност, светът е решил, може да означава грешка. Така че, ако някога сте побъркани нещо на компютъра си, или програма, току-що е починал от вас и сте придобили някои погрешни прозорец на вашия екран, казвайки грешка отрицателен 49 или грешка 23-- някои привидно произволна value--, че е защото един програмист е трудно кодирани стойност като негативен или позитивен 49 23 да представлява произволен брой, смея да кажа, на 4 милиарда възможни неща , които биха могли да се объркат в една програма. Е, как бих могъл да взема Възползвайте се от това сам? Е, нека да отворим програма че съм написал по-рано, и мушкам около онлайн нарича здравей 4. И това е почти идентични, с изключение на това му трябва малко за проверка на грешки. В този случай, аз съм отново обявена Основната както като два аргумента, но този път по линия 17, известие Правя малко на проверка здрав разум. Аз съм като се уверите, че argc равнява е равно на 2. Защото ако това е, че означава, че можете спокойно да докоснат не само конзола 0, но скоба 1. И да отида напред и да отпечатате, в този случай, Zamyla или Rob или каквото и дума въведох навън. И сега, само за да получите малко по-правилното, Отивам изрично да се върне 0 да означава всичко е добре. Нищо лошо не се е случило. Но по силата на споразумение, аз отивам да върне един, или казано всяко-0 без стойност, ако нещо се обърка. Сега потребителят няма да се наистина забележи какво става. В действителност, ако отида в тази директория, ние увеличавате и правят здравей 4, ./hello-4 Zamyla държи като аз очаквам. Но ако вместо това не напишете нищо, нищо не изглежда да се случи, но тя не се срине. И ако вместо да се направи нещо като Rob е Проктър в Thayer-- споделяне произволна информация. Но забележете, argv 1, 2, 3, 4, и 5, сега следва да съществуват в паметта. Това също не е това, което е моята програма очаква, защото аз проверих дали argc равнява е равно на 2, или не. Така че аз съм сега се защитава срещу това. Сега, като настрана, ние на programmer-- или по-скоро ние на users-- никога не се види, че 0 или 1, но като се използва инструмент, наречен Debugger, или други инструменти, както ще видим, преди да дълъг, можете програмиста може действително да видим какво може да бъде наред вътре на вашата програма. Така че, каквито и да било въпроси относно argc? Да. АУДИТОРИЯ: Аз съм виждал, където те не са имали характер, [недоловим] току-що каза низ звезда г, като характер звездичка запетая. Еквивалентен тук ли са те? DAVID Malan: Те са. Така че въпросът е, че имате понякога виждали програми като това, че не го правят каже низ argv скоба но вместо да каже нещо като Чар скоба звезда argv. А има и още други варианти, които може да се види. Те наистина са еквивалентни. За сега, ние имаме тези вид обучение колела на под формата на низ в CS50 библиотека, но за малко повече от седмица или така че ние отиваме да се премахне, че обструкция напълно и действително погледнете какво Чар и звездата са, и как тези, които се отнасят до паметта представяне като цяло. Така че ние ще се върнем към това. Други въпроси, свързани с нашата argv или argc? Да. АУДИТОРИЯ: Защо го върне грешка [недоловим]? DAVID Malan: Защо го направих върне грешка only-- ох! В предишния случай, когато ние бяха futzing наоколо с памет, защо го върне само грешка когато аз наистина написали голям номер? Краткият отговор е, че просто имам късмет. Най-общо казано, компютър заделя памет в парчета, и тя ми даде достатъчно голямо парче, че Имам далеч, без да бъдат забелязани, докосване скоба 2, 3 конзола, скоба 50, но веднага след като избута късметът ми, аз отидох на отвъдното граници на парчето на паметта операционната система ми беше дал. И това е, когато го притисната надолу и каза, не. Сегментирането грешка. Да. АУДИТОРИЯ: Как компютъра знаят стойността на argc? DAVID Malan: Как действа компютър знаят стойността на argc? Когато стартирате програмата, тази програма, от природата на мига ред, се предава на масива на думи, които са били напечатани в командния ред, това беше въвели в командния ред. И така, това е вашата операционна система, която по същество населяват аргументи основните е за теб. Така че това е една от услугите, че можете да получите, нещо тайно под капака на операционна система. Други въпроси? Да. АУДИТОРИЯ: Какво означава ядро ​​сметището кажеш? DAVID Malan: Какво означава ядро ​​сметището кажеш? Така че това е добър въпрос. И нека да се върнем в тази директория тук. И вие ще забележите, че Имам нов файл там. Това е наистина наречена ядро, и това е всъщност обикновено приличен размер на файла. Това е по същество една моментна снимка на съдържанието на паметта ми програмата или RAM, когато го разби. И това ще бъде полезна, потенциално, диагностично, след като ние говорим в бъдеще лекция и раздел за отстраняване на грешки, защото всъщност можете да направите еквивалент на цифров аутопсия на този файл, за да помогне да разбера какво сте направили погрешно във вашата програма. Да. АУДИТОРИЯ: Дали argc команда в себе си, или може да го назовем нещо? DAVID Malan: Добър въпрос. Дали argc команда само по себе си, или можете ли да го назовем нещо? Това определено не е команда. Това е просто една променлива Име или име на аргумент е, и така абсолютно ние могли да наречем този Foo, бихме могли да наричаме този бар, който са склонни да бъде в движение-на думите, че един компютър учен отива. Но по силата на споразумение, ние използваме argc и argv. Но това е само човешко конвенция, нищо повече. Добре. Така се оказва, че съм бил казвам малко на бял lie-- и честно казано, в бъдеще, ще видите ние сме били казва на другите бели лъжи. Но за сега, отиваме да се бели на едно от тях. В този случай тук, когато по-рано завтече програма като ./hello или ./hello-3 Zamyla, имахме съдържанието на моята паметта на компютъра си търси грубо като това. Но припомни какво е низ. Какво да кажем преди седмица каква низ всъщност се намира под предния капак? АУДИТОРИЯ: масив от символи. DAVID Malan: Това е масив от символи, нали? Така можем да имаме масив от струни, но, от своя страна, низ е набор от символи. Така че, ако наистина искате да бъдете анален, когато рисувам тази картина, Аз наистина трябва да бъде съставянето че е малко повече по този начин, при което във всяка от тези индекси на моя argv масив, там се е цяло низ , който се явява в масив. И сега на бял лъжата ние казваме днес е, че на снимката не изглежда доста по този начин. В действителност, най-малките квадрати са обикновено извън големите правоъгълници там. Но ние ще се върна на това след дълго. Но това е ./hello наклонена черта 0, че да бъдеш специален характер, които разграничава края на низ и ние имаме още една след Име Zamyla е. И така, какво означава това? Е, нека да вървим напред и да отвори два други примери , които са достъпни онлайн. Един от тях е наречен argv1.c а другият е argv2. Това е супер проста програма, която е различен от минали програми в която сега аз съм с argc и argv тук. И сега съм интегриране с линия за в ред 18, от I = 0 на до argc. И какво ще правя с тази линия на код тук? На английски език. Това очевидно показва използване на argc. Но на английски, какво прави го направя, ако стартирате тази програма? Да? АУДИТОРИЯ: Това ще да отпечатате екрана, толкова пъти, колкото искате. DAVID Malan: Точно така. Така че каквото и I думи въведете в командния ред, това е ще повръщам им към мен по един на ред. Така че нека да вървим напред и да направите това. Позволете ми да отида в моята директория и направи да argv1 ./argv1. А сега, нека да го прости. Да не се прави нищо в началото. Тя направи разпечатате едно нещо, и това е наистина името на програмата, защото това е в скоба 0. Ако аз сега кажа Foo, тя ще направи тези двамата, и ако кажа, Foo бар, че ще каже на тези три неща. Сега това е малко по-интересно, може би. Но припомни, че argv е масив от низове, но низ е масив от символи, така че можем да вземем нещата с една степен и прилага този основен логика и да код, който изглежда малко по-загадъчен, разбира се. Но като вложено контур, нещо подобно на това, което може да си припомни от Марио, например, ако ти си го направил по този начин. Така че сега забележи по линия 19, аз съм отново итерации над моите аргументи, от 0 на до argc. И сега, в съответствие 21-- съм заеми трик от миналата week-- Аз съм проверка на това, което е дължина от argv скоба аз. Аз съм съхраняване на този отговор в п. И тогава аз съм интегриране от J на до п, където J е инициализира на 0. Така че, конвенция за броене. След като сте използвали аз, ако имате вложен цикъл, не можете да използвате отново, в противен случай ще смажат, потенциално, стойността извън вътрешния цикъл. Така че аз съм с J по договореност. Ние може да използваме к. Ако имате повече от к, най-вероятно има твърде много гнездене, обикновено. Но сега, забележете ми ФОРМАТ линия е малко по-различен. Аз не съм печат% S, аз съм печат% С, което, разбира се, е контейнер за Чар. И сега забележи този синтаксис. New. Не сме го виждали и преди. Но логично, това просто означава, получите низ Ith в argv и да получите jth какво? АУДИТОРИЯ: Character. DAVID Malan: Герой в този низ. Така че, с помощта на квадратни скоби последвано от квадратни скоби, това е симулация първо в низове argv е, и след това на второ квадратни скоби с J е да се гмурне в героите на че специално низ в argv. И тогава, само за добра мярка, Аз съм отпечатване на нов ред тук. Така че сега нека да вървим напред и да се отвори до малко по-голям прозорец така че можем да видим това в действие. Позволете ми да отида в тази папка. И сега правя направи argv-2-- whoops-- направи argv-2, ./argv 2. Enter. И това е малко трудно да се чете вертикално, но това е наистина името на програма, последвано от един празен ред. Сега нека да вървим напред и да направим Foo. По същия начин е трудно да се чете, но това е наистина отпечатване един символ на ред. И ако го направя, бар, това е вече отпечатване на тези, ред по ред. Така на храна за вкъщи тук е не толкова че, уау, погледнете този чист нов трик където можете да получите в съдържанието на специфични знаци на даден масив, а по-скоро как ние сме като тези основни идеи като индексирането в масив, и след това в индексиране на масив, който е бил в този масив, и точно прилагане на едни и същи идеи за малко по-сложни примери. Но основите наистина не разполагат с променило, дори от миналата седмица. Сега това е нещо на своевременна, в това, че си спомняте, при нулева седмица играхме с телефон книга като тази. И въпреки че това е очевидно физически парчета хартия, можете да вид мисли за телефонния указател като масив. Разбира се, ако ви се налага да reimplement тази парчета тези хартийки в компютър, вероятно можете да използвате нещо като масив за съхранение на всички онези, имена и телефонни номера от целия път чрез Z. Така че това е хубаво, защото тя ни позволява възможност, може би, да се помисли как може да се реалното изпълнение на нещо подобно. Както при серия на врати тук. Така че, ако аз could-- ние се нуждаем един доброволци да идват нагоре. Нека да видим. Непознато лице може би, непознато лице може би. Какво ще кажете за в оранжево? Ето. Orange риза, хайде нагоре. Да вървим напред сега и ход тези врати над към страната, преместите тези от пътя за момент. Как ти е името? AJAY: DAVID Malan: Аджай. Дейвид. Приятно ми е да се запознаем. Добре. Така че ние имаме зад тези шест врати цифровото на screen-- Или по-скоро, седем врати на screen-- цял куп номера. И аз ти казах нищо в advance-- съгласи? AJAY: Нищо по-рано. DAVID Malan: Всичко, което искам да направя сега е да се намери за мен, и за нас, Наистина, броят на 50 г. една стъпка в даден момент. AJAY: Номер 50? DAVID Malan: Броят 50. И вие може да разкрие какво е зад всяка от тези врати просто като го докосва с пръст. Дявол да го вземе. [СМЯХ] [APPLAUSE] Много добре направено. OK. Имаме прекрасен подарък награда за теб тук. Своя избор на филми ние обсъдени миналата седмица. AJAY: О, човече. О, аз никога не съм виждал Spaceballs. DAVID Malan: Spaceballs. Добре. Така че държи само на един момент. How-- нека направим това а поучаем moment-- как да отида за намиране на броя 50? AJAY: Избрах произволно. DAVID Malan: Значи вие избрахте случайно и имам късмет. AJAY: Да. DAVID Malan: OK. Отлично. Така че сега, не трябваше ли намерила късмет, какво друго може да се е случило зад тези врати? Така че, ако аз отида напред и разкрие тези номера тук, те всъщност са в произволен ред. И най-доброто което може да има направено, честно казано, е чрез, в крайна сметка, в най-лошия случай ги проверявам. Така че имаш супер късмет, който Не е това, което ние ще се обади един алгоритъм. Да, поздравления. Но сега let's-- хумор ме, ако можеш. Да отидем в този раздел тук. И тук са числата в ясно това, което изглежда да е случаен ред, и те бяха. Но сега, ако аз вместо иск че зад тези врати са числа, които са сортирани. Целта сега е също ни намерите броя 50. Но го направи алгоритмично, и да ни кажете как ще за него. И ако го намеря, ви държи на филма. Вие не го определят, ти го върна. AJAY: Така че аз отивам да се провери краищата Първо, за да се определи дали there's-- [Смях и APPLAUSE] DAVID Malan: Заповядай. Нека да разгледаме един на предшествениците Аджай е, Шон, който не е бил чак толкова късмет. ОК, така че вашата задача тук, Шон, е следното. I са скрити зад тях врати на числото седем, но закътано в някои от тези врати , както и други не-отрицателни числа. И целта ви е да се мисли за това най-горния ред на номерата като само един масив. Ние сме просто поредица от парчета хартия с номера, които стоят зад тях. И целта ви е, само с помощта на върха масив тук, да ме намери на числото седем. И ние тогава ще критикуваме как да отидете за да го прави. Намерете ни на числото седем, моля. No. 5, 19, 13. Това не е подвеждащ въпрос. 1. В този момент резултатът ви не е много добре, така че може и да продължаваш напред. 3. Продължавай. Честно казано, аз не мога да помогна, но се чудя това, което дори и да мисля за. SEAN: Мога да взема само от най-горния ред. DAVID Malan: Само най-горния ред. Така че имаш три ляво. Така ме намери 7. [АУДИТОРИЯ викове ПРЕДЛОЖЕНИЯ] Така че и двете от тях бяха невероятно за много различни причини. Така че това е мястото, където ние спряло преди малко, и ключовото прозрение тук е тези врати имаха номера зад тях, които са били подредени, идеала храна за вкъщи, за което е, че бихте могли да направите фундаментално по-добре в втората example-- и, разбира се, това беше Шон Първият опит със случайни числа точно както before-- но щом тъй като тези числа се сортират, много прилича на телефонния указател, какво може да ви очевидно направя? Или как може да се възползва, че знанието? Да. АУДИТОРИЯ: Отиваш наполовина [недоловим]. DAVID Malan: Да. Точно така. Така първоначалната инстинкт Аджай беше за проверка на краищата, доколкото си спомням, и тогава ние някак завършен пример бързо. Но ако ние започнахме да правим това по- методично по тези линии, но като се започне може би в средна, защото те са подредени, веднага щом се разкрие номер 16, ние следователно знам-- и нека направим точно че-- ние Затова знам, че 50, в днешния случай, трябва да е в дясно. Така че точно като в нула, когато седмица ние разкъса телефонния указател на половина и хвърли половината от проблем далеч, същата идея тук. Ние може да се хвърли в това полувреме на проблема далеч. И вероятно това, което ви може да направи алгоритмично, след като знаете, че 50 трябва да бъде надясно, ако е навсякъде, е да се опитаме там, в средата на останалите врати. Разбира се, 50 е по-висока от 42, така че ние може да хвърлят тази оставаща тримесечие на проблема далеч, и, накрая, да се идентифицират нещо като 50. Но точно както с телефонния указател, тези номера бяха дадени, за да ни вече в Подредено заповед, която ни оставя с въпроса, как го правиш нещата в подредени поръчка? И, честно казано, на каква цена? Това е едно нещо, за да бъде връчи на телефонния указател и след това впечатлите приятелите си чрез намиране на телефонен номер, наистина бързо, нали? Разкъсването 32 страници, за да се намери човек от 4 милиарда страници, казахме, беше един краен пример. Но колко време ви отне Verizon да сортирате този телефон книга? Колко време ни отне да сортирате тези седем числа? Това е един въпрос, който сме до този момент напълно игнорирани. Така че нека да се отговори на този въпрос сега. И всички ние сме изложени на филми сега, но ние имаме някои стрес топки. Ако, да речем, осем доброволци не би имал нищо против присъедини към нас тук? Да вървим напред и да правим, какво ще кажеш за на четири от вас, три от вас тук? Вземи някои нови лица. И четиримата там ли си? И сега-- не е пристрастие нека тук-- и номер осем тук на края. Хайде нагоре. Добре. Така че това, което имаме тук, за всеки от вас е номер. Ако искате да отидете напред, да вземе този номер. Как ти е името? Арти: Арти. DAVID Malan: Арти, добре. Ти си номер едно. Amin: Амин. DAVID Malan: Амин. Дейвид. Ти си номер 2. И давай, както аз ръка вие листовете хартия, подредят сами в предната част на музиката стои в същия ред, като до там. ANDY: Hi, Анди. DAVID Malan: Анди, това е хубаво да те видя. Номер 3. Яков: Яков. DAVID Malan: Jacob, номер 4. Добре дошли на борда. ГРАНТ: Грант. DAVID Malan: Грант. Номер 5. Алана: Алана. DAVID Malan: Алана, номер 6. FRANCES: Frances. DAVID Malan: Frances, номер 7. И? RACHEL: Рейчъл. DAVID Malan: Рейчъл, номер 8. Добре. Давай напред и да получите себе си в този ред. Позволете ми да сложа една оставащото музика застане на мястото си. Когато имате нужда от стойка? OK. Давай напред и просто да сложиш номера където публиката може да ги видите на, музиката стои изправена навън. И се надяваме, че нашата първа проверка здрав разум тук-- 4, 2, 6. О-о. Чакайте малко. Ние не разполагаме с 8. Трябва да ви изгони от примера по някакъв начин. No. Не, това е ОК. Нека да видим. Ние можем да направим това. Изчакайте. Там отиваме. Правилно. Добре. Така че, сега имаме 8, 1, 3, 7, 5. OK. Отлично. Така че въпросът е на една ръка разстояние, при каква цена, и чрез какъв метод, всъщност можем да сортирате тези номера тук така че можем да вид работа назад, в крайна сметка, и decide-- това е наистина впечатляващ, това е наистина ефективна, че мога да се делят и завладяване на телефонния указател? Наистина ли е ефективен Мога да разделяй и владей тези цифрови парчета хартия на дъската, ако може би това ще ни струва състояние по време или цикъла на енергия или на процесора да се получи в действителност нашите данни в някои сортиран ред? Така че нека да зададеш този въпрос. Така че първото изключване, тези номера са в почти произволен ред, и аз отивам да предложи един алгоритъм, или процес от които можем да сортирате тези хора. Отивам да се приближим това доста наивно. И аз отивам да се признае, че това е вид много за мен да приключи съзнанието ми около определени наведнъж цели данни. Но знаете ли какво? Отивам да се направят някои много прости маргинални поправки. 4 и 2 са изложени на нареждане, ако цел е да се премине от един на до 8. И знаеш ли какво? Отивам да имате момчета разменят, ако превключите физически позиции и от вашите фигури от хартия. Сега 4 и 6, те са в ред. Отивам да напусне онези бъде. 6 и 8, тези, които са в ред. Отивате да напусне ги бъде. 8 и1, от ред. Ако вие двамата не би имал нищо против смяна. Сега 8 и 3, ако вие може да си разменят. 8 и 7, ако вие може да си разменят. И осем и пет, ако вие може да си разменят. Сега, аз съм направил? Не, очевидно не. Но аз не съм направил ситуация по-добре, нали? Какво ти беше името, номер 8? RACHEL: Рейчъл. DAVID Malan: Значи Рейчъл има ефективно бълбукаше доста далеч, чак до края на ми масив от числа тук. И така, този проблем е вид решен. Сега, очевидно, две все още трябва да преместите малко, и 4 и 6 и 1. Но аз изглежда да са придобили малко по-близо до решение. Така че нека да прилага същата тази наивна евристичен отново. 2 и 4, OK. 4 и 6, OK. 6 и 1 мм мм. Нека суап. 6 и 3 мм мм. Нека суап. 6 и 7 е OK. 7 и 5, Не. Нека суап. И сега, 7 и 8. А какво е твоето име отново? FRANCES: Frances. DAVID Malan: Frances. Така че сега Frances е в още по-добра позиция, защото сега 7 и 8 са правилно разпенва до върха. Така че, 2 и 4, OK. 4 и 1, суап Да. 4 и 3, суап Да. 4 и 6, ти си OK. 6 и 5, суап Да. И сега тези момчета са добри. Ние сме почти там. 2 и 1, в ред, така че сменяте. А сега нека да направи проверка на здрав разум. 2 и 3, 3 и 4, 4 и 5, 5 и 6, 6 и 7, 8. ОК, така че сме готови. Но на каква цена го направих сортирате тези номера тук? Е, колко стъпки направих потенциално предприемат при сортиране тези хора? Е, ние ще се върнем към този въпрос. Но, честно казано, ако имаш малко скучно, това е вид, разкриващи в че това не е Може би най-ефективен алгоритъм. И наистина, честно казано, аз се потя още по-ходене напред-назад. Това не се чувствам особено ефективен. Така че нека да опитаме нещо друго. Ако вие може да възстановите себе си на тези осем ценности. Добра работа. Нека да разгледаме по електронен път за просто миг преди да опитам нещо друго, в какво точно се е случило. До тук, вие сте на път да видите визуализация на тези осем човека при която в синьо и червено барове представляват номера. Най-високият бара, С увеличаването на броя. Колкото по-малко на бара, толкова по-малък номер. И това, което ще видите, е в произволен ред повече от осем от тях. Ще видите тези барове Първи сортирано по същия алгоритъм, или набор от инструкции, които ние ще се обадя оттук нататък балон вид. Така забележите, всяка секунда, или така, два бара светят в червено, се сравняват от компютъра. И след това, ако голямата бара и малък бар са в ред, те се разменя за мен. Сега това е изключително досаден да гледате, разбира се, за много дълго, но забележите, че takeaway-- големите барове, които се движат в дясно, малките барове, които се движат в ляво. Да прекратим този процес и ускоряването на този процес да бъде много по-бързо, за да можем да получите усещане за това какво на високо равнище, наистина, балон вид се прави. В действителност, това е кипял до дясната страна на списъка, или масива, по-големите барове. И обратното, малките барове са ври пътя си надолу вляво, макар и с по-бързи темпове отколкото ние по-рано е направил. Така че, по-трудно да се види с хората, но визуално, че е наистина това, което се случва. Но нека се опитаме фундаментално различен подход сега. Нека се опитаме различен алгоритъм, чрез което имате момчета започват в тези оригинални позиции, на която беше тази поръчка тук. И да вървим напред сега. И аз отивам да направя нещо още по-лесно, нали? В ретроспекция, смяна на двойки отново и отново, почти малко умен. Нека да направим нещата още по-наивно, където, ако искам да сортирате тези хора, нека просто продължавайте да търсите за най-малкия елемент. Така че точно сега, 4 е най-малкият брой съм виждал. Отивам да си спомня това. Не, две е по-добре, и не забравяйте това. 1 е още по-малък. 3, 7, 5. OK. Едно-- какво ти е името? Арти: Арти. DAVID Malan: Арти. Така че, Арти, давай напред. Отивам да ви извадя на линията. Ако можеше да се върна тук. И аз трябва да се направи място за него. Имаме точка решение тук. Как бихме могли да направим място за Арти тук в началото, когато номер едно принадлежи? АУДИТОРИЯ: Shift. DAVID Malan: ОК, ние може да се измести всички. Но предлагаме оптимизация. Това се чувства малко досадно за мен да попитам четирима души да се движат по целия път надолу. Какво друго можех да направя? АУДИТОРИЯ: ги включите. DAVID Malan: ги включите. А какво е твоето име отново? Яков: Яков. DAVID Malan: Jacob, преместете. Много по-ефективно, само за да има Места Джейкъб суап с Арти, за разлика от принуждавайки всички четири от тези хора, благодаря ви много, за да правилното им положение. Какво е хубаво за Арти сега, той е в правилната му позиция. Да го направим отново. 2, това е най-малкият брой съм виждал. 3, 7, 5. OK. 2 определено е най-малкият. Не трябва да се направи някаква работа. Да го направим отново. 6. Най-малък? 8. Не. 4? Ooh. Нека се помни 4. 3. Нека се помни 3. 7, 5. Най-малък брой Нямам се вижда на този пропуск е 3. Ако искате излез. Къде отиваме да сложите? А какво е твоето име? Алана: Алана. DAVID Malan: Алана, ние сме Ще трябва да ви изгони. Но това е по-ефективен, просто да сменяте двама души, отколкото да имаш много хора всъщност заобикалям свърши. Сега нека да направим това отново. Отивам да изберете 4, така че хайде навън. И кой ще се движат? Номер 8, разбира се. Ако аз сега намерите номер 5, хайде навън. Номер 8 ще се изгонени отново. Аз съм сега ще намерите номер 6 в място. 7 в място. 8 в място. Това, което току-що е направил в момента е нещо, наречено избор на сортиране, и ако ние се визуализира това, че е ще се чувствам малко по-различно. Да вървим напред и от тази меню тук, това visualization-- Нека променим това да-- хайде, Firefox. Нека да променим това, за да избор на сортиране. И нека да го ускори, както и преди, и да започне визуализацията сега. И този алгоритъм има различно усещане за него. На всяка итерация, честно казано, това е още по-лесно. Аз съм просто избор на най-малкия елемент. Сега, честно казано, аз имам малко късмет, че време, с това, че сортирани супер-бързо. Елементите са случайни. Това не е, както ще в крайна сметка виж, фундаментално по-бързо. Но нека да видим една трета и последна подходим тук за това какво се случва. Така че нека да вървим напред и да ви изчисти момчета една крайно време да бъде в този ред тук. И сега, аз отивам да да е малко по-умен, просто да закръглят нашите алгоритми. Отивам да направя това. Отивам да не отида назад и напред толкова много. Честно казано, аз съм уморен от всичко това обхождане. Аз съм просто ще вземе това, което съм даден в началото на списъка и аз отивам да сортирате че тогава и там. Така че ние сме тук. Номер 4. Отивам да въведете номера 4 подредени в списък. Готово. Аз твърдя, сега, и само за да стане това по- ясно, тази част от моя списък е сортиран. Това е нещо глупаво твърдение, но наистина 4 се подредени в списък с размер един. Сега, аз отивам да поеме номер 2. Номер 2 Аз съм сега ще поставете в правилното място. Е, къде е 2 принадлежи? Очевидно е, че тук. Така че продължавайте напред и да се премести назад, ако можех. И защо не, момчета просто вземат музиката си стои с вас този път. И оставим насилствено вмъкнете в началото на списъка. Така че малко повече работа. Аз трябваше да се движат Jacob наоколо, и какво е вашето име? Amin: Амин. DAVID Malan: Амин. Но поне аз не отиде назад и напред. Аз съм просто като неща, като отида. Аз просто ги поставяте на правилното място. 6, това всъщност е доста лесно. Нека да поставите там, ако сте Просто исках да се движат над леко. Номер 8, също е доста лесно. Точно там. Дявол да го вземе. Номер едно, че не можем просто суап с Amin тук, защото това се случва да се забъркваш поръчката. Така че ние трябва да бъдем малко по-умен. Така че, Арти, ако бихте могли да резервно копие за миг. Да вървим напред и да се измести сега, за разлика от предишните ни алгоритми, за да направи място за Арти точно тук в началото. Така че в края на деня, аз съм вид правят това, което аз исках да се избегне преди. И така ми алгоритъм е нещо на обърната, интелектуално, от това, което първоначално е било. Просто правя изместването в друга точка. Сега съм на 3. О, по дяволите. Трябва да направим повече работа отново. Така че нека да ви пускам. Нека преминем 8, 6, 4-- о ОН-и 3 се ще да отида точно там. Така че най-малко незначителни икономии на този път. 7, не е твърде много работа да се свърши. Така че, ако искате да се появи Обратно, нека да вмъкнете. И накрая, 5, ако Искам да поп обратно, ние Трябва да ти се измести, ти, ви, докато пет е на мястото си. Така че сега, за да видите това на високо ниво графично, нека да направим този алгоритъм визуализация едно допълнително време. Така че това ще наричаме вмъкване вид. Ние ще го изпълним просто като бързо, и да го започнете от тук. И също има различно усещане. Това е нещо все по-добре и по-добре, но тя никога не е перфектен докато вляза и гладка в тези пропуски. Защото, отново, аз съм само като това, което Аз съм се дава от ляво на дясно. Така че аз не се получи толкова щастлив че всичко е перфектно. Ето защо ние трябваше тези малки mispositions че ние фиксирани във времето. Така че всички тези алгоритми изглежда се движи с малко по-различни крачки. В действителност, което ще ви кажа, е, най-доброто или най-бързият досега? Bubble вид, на първо? Избор на вид, на втория? Insertion вид, третият? Чух, че някои видове подбор. Други мисли? Така се оказва, че Всички тези алгоритми са коренно също толкова ефективни като всеки друг свят-- или, обратно, точно както неефективно като всеки друг, защото можем да направим фундаментално по-добре от всички три на тези алгоритми. И това е малко на една бяла лъжа, също. когато казвам, като ефективно или като неефективна, това е най-малко за супер-големи стойности на N. Когато имаме само осем души тук, или може би 50 или така барове на екрана, сте абсолютно ще забележите разликите сред тези три алгоритми. Но тъй като N, броят на хората, или броя на номера, или на броя на хората в телефона книга, или на броя на уеб страници в базата данни на Google стане по-голям и по-голям, ще видим, че всички три от тях алгоритми всъщност са доста бедни. И ние можем да направим фундаментално по-добре от това. Нека да разгледаме най-накрая, в това, което биха могли тези алгоритми звучи като в контекст на няколко други както и чрез този визуализация тук че ще ни запознае с редица алгоритми. Да вървим напред и да поздравя нашите участници тук, всички от които се подредени много добре. Ако искате да се прощален подарък. Можете да запазите номера, както добре. И това, което ще видите, или по-скоро чувам, сега, е, че ние поставяме звуци за всеки един от тези барове и да го асоциирате със софтуера, различна честота на звука, можете да увийте ума си повече audioly около това, което всеки един от тези неща изглежда така. Първият от които е вмъкване на сортиране [ТОНОВЕ] Това е нещо като балон. [ТОНОВЕ] Избор на вид. [ТОНОВЕ] Нещо, наречено сливат вид. [ТОНОВЕ] Gnome вид. [ТОНОВЕ] Това е за CS50. Ние ще се видим в сряда. Разказвач: И сега, "Deep Thoughts, "от Дейвън Farnham. Защо го е за цикъл? Защо не направите по-добре? Бих се направи пет цикъла. [СМЯХ]