DAVID МАЛАН: Хорошо. Так что это CS50, и это Теперь начало три недели. Так до сих пор, мы не имею писал программы в C что выглядит немного как то так вот. Итак, мы получили пару Резкое включает в верхней части. У нас есть Int, главная, недействительными, и затем то, чтобы сделать в середине, некоторые кусок кода внутри из этой функции. Но ключ был тот факт, что мы говорили недействительными здесь. Так недействительными, все это время, указывает что эта программа, при запуске, может быть запущен только через его имени. Вы не можете ввести любые другие слова или Цифры после названия программы при запустить его. Так, например, если программа была собраны в файле под названием Привет, вы могли бы сделать ./hello, но что это такое. 

Единственный способ, которым вы могли бы внести свой вклад в эту программу является путем вызова функции. Например, что функция были мы, используя до сих пор для получения данных от пользователя? 

АУДИТОРИЯ: Получить строку. DAVID МАЛАН: Чтобы получить строку, или получить Int, или вы видели других, даже если вы не использовали их еще, как получить много, много и тому подобное. Но предположим, что мы на самом деле хотите, чтобы начать написание программ, которые немного больше универсальный, и, честно говоря, немного больше как команды, что вы получал, как мы надеемся, немного привыкли. Как кд пространства Dropbox. Это, конечно, изменения ваш каталог, предполагая вы находитесь в доме Джона Гарварда каталог, в папку Dropbox. Между тем, команда, как это создает новую папку с именем pset2, как вы, наверное, уже или скоро для задачи установить два. Сделать Привет, конечно, является командой , которая строит программу под названием привет из файла под названием Привет точка с. И в каждом из них случаи, сейчас, у нас было обеспечивают аргумент на так называемый командной строки, мигает быстро, так что марка знает что строить, и так что MkDir знает, что папка, чтобы создать, и так, что CD знает где вы хотите пойти. Но до сих пор, мы постоянно говорят что главная ваша функция по умолчанию, есть выражение пустот внутри этих скобок, Это означает, что его не может принять никаких аргументов. 

Так, начиная с сегодняшнего, то, что мы собираемся сделать есть, мы собираемся начать поддержки такие вещи даже. На самом деле, в этом случае, который вам как правило, не вручную ввести, Сделать делал это для нас, есть не один, а один, два, три дополнительных строки после програмы по имени лязг. Так как же нам этого добиться? 

Ну, начиная с сегодняшнего дня, в тех случаях, когда мы хотим обеспечить ввод через Так называемый командной строки, мы собираемся начать добавлять здесь то, что в yellow-- замена пустоту агдс запятой Строка агду открывающая скобка закрывающая скобка. Теперь это интересно в течение нескольких причин. Один, это будет запишем программы, которые немного более динамичным. Но, более убедительно, он собирается открыть Теперь разговор, чтобы что массивы могут действительно использоваться, для того, что строки действительно находится под капотом, до следующей недели, когда мы не начнем с аквалангом В еще глубже относительно того, как машина делает все эти вещи работы. Но сейчас, давайте рисовать, возможно, картина. 

Когда вы пишете программу с основным заявил В этом случае, таким образом, что основная принимает два аргумента, Int и-- какой тип данных это второй аргумент? 

АУДИТОРИЯ: Array. DAVID МАЛАН: Array. Так это выглядит на первый взгляд, как будто это строка, но обратите внимание на квадратные скобки. Напомним, в последний раз мы ввели Понятие массива. И массивы используют квадратные скобки через пару контекстах. Вы можете использовать площадь кронштейны идти в массив и получить конкретный элемент, как Кронштейн 0 или кронштейн 1 или кронштейн 2. Но мы видели, если кратко, на прошлой неделе, что вы также использовать эти квадратные скобки в объявить размер массива, если вы знаете заранее, сколько Интс или сколько строк или все, что вы на самом деле хотите. Вот и получается, что есть третий контекст здесь что не имеет номера внутри из квадратных скобках. При указании, как у меня здесь, название-то вроде ARGV, , который является просто причудливый способ говоря аргумент вектор, еще один причудливый способ говоря массив аргументов, открывающая скобка закрывающая скобка просто означает, что вам не обязательно заранее знать, как большой Массив будет, но вы знаете, что это собирается быть массивом. Так что, если вы не знаете, число, не ставьте его там, для открытой кронштейна закрывающей скобки означает, что агду не является строкой, но массив строк. Так синтаксически, если вам думаю на прошлой неделе, это очень похоже, что сказать что-то вроде десятичного возрастов открывающейся скобки, а затем то после этого. Итак, что же это похоже? Давайте реально нарисовать картину. Поэтому, когда вы запустите эту программу с основными Наличие двух аргументов определяется внутри из тех скобках, вы существенно, по крайней мере два куска памяти передал вам под капотом. Один, как я буду рисует как этого прямоугольника, собирается назвать агдс. И так же, как быстрой повторение, что тип данных агдс? Так что это внутр. Так ряд собирается пойти в argc-- поворотов , что означает количеством аргументов. Между тем, я нарисовал ARGV как массив. И я действительно не знаю, как долго это будет, так для сегодняшних целей точка точка точка. Это могло бы стать некоторой длины. Но я на фото здесь по меньшей мере, четыре прямоугольников. Так агду кусок памяти, которая хранит строка строка строка точка точка точка, и агдс является лишь одним кусок памяти для целого числа. 

Так что теперь, давайте быть немного более точным. Если, когда у меня есть строки в этом массиве, называется агду, я хочу получить на них индивидуально, так же, как на прошлой неделе, мы собираемся использовать обозначения как агду кронштейна 0 чтобы получить первое, что массив. Агду кронштейн 1, чтобы получить Вторая вещь, и так далее. Ключевым моментом здесь является, что мы по-прежнему 0 indexed-- мы все еще считая от 0. Так что теперь давайте на самом деле положить что-то в этом. Если бы мне пришлось составить программу под названием Привет из файла под названием Привет точка с, а затем я запускаю эту программу с точки слэш привет, что делает мой компьютер, мой ноутбук, выглядеть под капотом момент я бегу точка слэш привет и нажмите Ввод? Ну, это, пожалуй, то, что мы могли бы описать как содержание вашего компьютера памяти, или памяти RAM-- Random Access. Другими словами, компьютер, так или иначе для вас волшебным, ставит цифру 1 в агдс, AKA ARGCOUNT, и это ставит буквально строку ./hello в ARGV кронштейна 0. Я понятия не имею,, честно говоря, то, что нет в ARGV кронштейном 1 или 2 или 3, потому что, если пользователь не имеет набрали ничего, кроме ./hello, мы будем считать, что эти являются наиболее вероятными значениями мусора, так сказать. Эти куски памяти существует, но это не к нам смотреть на них, потому что ARGCOUNT только один. 

Теперь, между тем, если I написать запустить другую программу, кд, что более правильно команда, в вашем мигающим prompt-- пространства кд Dropbox-- когда я запускаю, что, по сути, когда программа кд запускается, агдс, внутри памяти моего компьютера, для наиболее долю секунды число 2. А потом агду кронштейн о имеет кд, агду кронштейн 1 имеет Dropbox, и тогда, конечно, команда завершает, так вся эта память существенно уходит и используется для другого. И вот почему я говорю только на долю секунды. 

Между тем, если мы делаем MKDIR pset2, картина выглядит почти так же, но с разными строками внутри ARGV. Если я делаю лязг тире привет Привет точка с, та же идея. Больше материала заполняется для агду, и агдс, конечно, 4. Таким образом, другими словами, хотя этого массива может быть точка точка точка, из некоторых переменной длины, так сказать, Вы всегда знаете, где его конец является, потому агдс собирается сказать вам в какой момент вы должны остановить глядя на элементов в ARGV. Вы можете смотреть только на четырех в общей сложности в этом случае. 

Итак, давайте взглянем на, возможно, простая программа. Тот, который просто говорит привет кому то нравится Zamyla. Так я утверждаю, что я собираюсь написать программу через минуту, через который я мог сделать ./hello пространство Zamyla, а затем я хочу моя программа распечатать то супер-просто, как "Привет, Zamyla." Теперь в прошлом мы использовали GetString. Так в прошлом, даже если Вы новичок в программировании, наверняка вы могли на скорую руку программа, которая использует GetString а затем использует Printf чтобы сказать привет Zamyla. Но давайте не будем использовать GetString этот раз. Позвольте мне вместо этого пойти в Appliant и не включают в себя стандартные Я O точка час. Позвольте мне также включают CS50 точка час. Теперь тап_п, и теперь я не собирается делать недействительными сегодня. Вместо этого, я собираюсь сделать агдс Строка агду открывающая скобка закрывающая скобка, не указали номер. А теперь вот моя так называемая сделать. То, что я собираюсь сделать сейчас, это, я собирается сделать немного прыжке веры, Я буду считать, что пользователя собирается правильно использовать эту программу, и я просто собираюсь сделать Е привет,% Sn. Так что ничего нового там. Но я хочу, чтобы теперь положить все, что слово пользователь после имени программы. Так что, если я делаю ./hello пространство Zamyla, я хотите-то программно доступ цитировать конец цитаты "Zamyla." поэтому я может пойти в мою аргумента вектора, мой массив строк, и если команды, снова, был ./hello пространство Zamyla, какой номер я хочу положить в ARGV здесь? АУДИТОРИЯ: 1. DAVID МАЛАН: 1, потому что Кронштейн 0 оказывается будет Название программы, как мы видели. Так кронштейн 1 это первое слово что я, пользователь, набрали. Я собираюсь идти вперед и сохранить это. Я собираюсь пойти в мою папку где я разместил этот файл. Я собираюсь сделать сделать привет 3. ОК Comp НЛ. ./hello Zamyla Enter. Что я сделал не так? Я был застигнут врасплох я на мгновение там. Что я сделал не так? 

АУДИТОРИЯ: Имя. 

DAVID МАЛАН: файла на самом деле называется hello3.c. И я сделал это только для консистенция, потому что мы была hello.c находится в мимо в онлайн кода. Так давайте исправим эту ./hello Кронштейн тире 3 Zamyla. Enter. И теперь у нас есть привет, Zamyla. Между тем, я могу изменить это быть Роб, или действительно любое другое слово. 

Но давайте рассмотрим угловой случай. То, что вы могли бы ожидать произойдет, если Я не ввести имя чью вообще? 

АУДИТОРИЯ: Ошибка. 

DAVID МАЛАН: ошибка какой-то, возможно. Посмотрим. Enter. Null. Так Е фактически быть немного защищает нас здесь, и буквально печати открытые Парень нуль, но даже худшие вещи могут случиться. И только продемонстрировать то, что вы абсолютно не следует делать, пойдем в здесь и начать ковыряться. Верно? Если я знаю, что картина в памяти, по существу, это, агду кронштейн 1 имеет Zamyla, ARGV Кронштейн 0 имеет ./hello или ./hello-3. Что в кронштейне 2? Так что я могу ответить, что задаю себе вопрос, не так ли? Я могу просто изменить 1 к 2. Теперь я могу перекомпилировать привет 3, ./hello3 Давайте увеличивать и нажмите Ввод. Упс. Нет кавычки. Интересно. Так что вроде здорово посмотреть, что еще здесь. 

Так что еще находится внутри моего ноутбука? Давайте сохраним его с кронштейна 3. Сделать hello3, ./hello-3. Любопытный. А теперь давайте действительно bold-- 50. Так что на самом деле ныряя глубоко в память моего компьютера. 50 Индексы в. Так что привет 3 ./hello-3. Любопытный. Ладно, сейчас я просто собирается получить безрассудным. Пойдем в 5000. Хорошо. Итак, позвольте мне перекомпилировать. Сделать hello3, ./hello-3. Хорошо. Сейчас некоторые из вас, может быть лампочка уходят. Как многие из вас есть видели это сообщение раньше? Хорошо. Итак, почему? 

Коэффициенты are-- и есть разные вещи, которые могут привести к этому, и ясно, что ты в хорошей company-- у нас есть четко вызвало то, что называется Сегментация вина. И короче говоря на сегодняшний день, я коснулись сегмента памяти что я не должен иметь. Где сегмент просто означает кусок памяти, что я не должен иметь. Теперь компьютер гарантирует, что, если я запустить ./helloZamyla что я могу коснуться ARGV быть кронштейн 0 и агду кронштейн 1. Но агдс является значение 2, что означает, что я только allowed-- это своего рода честь система-- прикоснуться Кронштейн 0 и кронштейн 1. Если я иду дальше, есть абсолютно будет память есть. Мой RAM существует физически в компьютере. Но кто знает, что там? В самом деле, я бегу кратное программы в одно время. Я мог бы seen-- если бы я не был делать это на Appliant но на моем Mac или PC-- я мог бы видел содержимое электронной почте. Я, возможно, видели мгновение сообщение Я недавно послал. Все, что может быть сохраняющиеся вокруг в памяти можно было бы получить по способу это произвольная квадратная нотация кронштейн. Или, что еще хуже, вы, возможно, нашел одного из моих паролей что я в последнее время набрали в, что Программа была храниться в памяти, так как для аутентификации меня, и то только отчасти оставил его в памяти, пока я не ушел эту программу. 

И в самом деле, это один из опасность и одна полномочия использования языка как С. У вас есть свободный доступ на все содержание памяти программы, и какие плохие парни могут даже сделать в тех cases-- Особенно, когда мы получить на веб-программирования к концу семестра, мы будем вернуться к этому topic-- будет копаться, потенциально, кто это компьютера памяти и найти такие любопытные вещи как мы видели там. Или даже еще хуже, пароли, что он или она может использовать, чтобы делать плохие вещи. 

Итак, ясно, я не должен был делать этого, потому странные вещи начинают происходить. В самом деле, это программа грохот. Это было бы равносильно из Mac OS или в ОС Windows Окно программы просто исчезают. Непредвиденная ошибка. В среде командной строки мы видим нечто подобное. Но именно поэтому, как я, просто прикасаясь памяти, что не принадлежит мне. 

Так что давайте защищаться от этого а Немного по-другому глядя на этой программе. Таким образом, опять же, скелет что мы видели earlier-- и я выделил этот раз Int. И все это время главным имеет В самом деле возвращается значение. Даже при том, что в большинстве наших лекции примеры мы ни разу не использовали ничего возвращать в основной. Мы просто написать PRINTF близко фигурная скобка и вот оно. Но бесплатно, что компилятор делал для вас, эффективно, возвращается 0 для вас. Оказывается out-- и это немного counterintuitive-- что 0 это хорошо. Это не значит, ложь сама по себе. 0 хорошо, и любой не-0 Значение, что мир решил, может означать ошибку. Так что если вы еще не испортил то на вашем компьютере, или программа только что умер от вас и Вы получили некоторые ошибочные окно на экране, говоря об ошибке отрицательное 49 или ошибка 23-- некоторые, казалось бы, произвольное value-- вот потому программист жестко Значение как отрицательный 49 или положительное 23 для представления любого числа, осмелюсь сказать, из 4000000000 возможных вещей что может пойти не так в программе. 

Так как я мог бы взять Преимущество этого я? Ну, позвольте мне открыть программу что я написал заранее, и копаться онлайн называется привет 4. И это почти идентичны, за исключением того, ее получили немного проверки ошибок. В этом случае, я снова заявил Основной, как принимающая два аргумента, но на этот раз, в строке 17, уведомление Я делаю немного для проверки отсутствия ошибок. Я убедившись, что агдс равна равна 2. Потому что если это так, что означает, что я могу безопасно коснуться не только кронштейн 0, но кронштейн 1. И я иду вперед и распечатать, В этом случае, Zamyla или Rob или что слово, которое я напечатал. И теперь только, чтобы получить немного более правильным, Я собираюсь явно вернуться 0 для обозначения все хорошо. Ничего плохого не случилось. 

Но по соглашению, я собираюсь вернуться 1, или откровенно любой не-0 значение, если что пошло не так. Теперь пользователь не собирается замечаете, что происходит. Действительно, если я иду в этот каталог, мы увеличения и делают привет 4, ./hello-4 Zamyla ведет себя, как я ожидаю. Но если я, вместо не вводите ничего, ничего, кажется, произойдет, но это не катастрофа. И если я, вместо то делать как Роб является сопровождающий в Thayer-- обмена произвольная информация. Но заметьте, агду 1, 2, 3, 4, и Теперь 5 должен существовать в памяти. Это тоже не то, что моя программа ожидает, потому что я проверил ли агдс равна равна 2 или нет. Так что я теперь защищает против этого. 

Теперь, как в сторону, мы programmer-- или скорее мы users-- никогда не видеть, что 0 или 1, но с использованием Инструмент под названием отладчик или других инструментов, как мы увидим перед долго, вы программист может увидеть, что может быть происходит не так внутри вашей программы. 

Таким образом, любые вопросы по агдс? Да. 

АУДИТОРИЯ: я видел, где они не имели характер, [неразборчиво] просто сказал строка звезды д, как характер звездочка запятая. Являются ли они эквивалентны здесь? 

DAVID МАЛАН: Они. Таким образом, вопрос, у вас есть иногда видел программы как это, что не говорят строка агду кронштейн но вместо этого что-то сказать как сЬаг звезда агду кронштейна. И есть даже друга варианты, которые вы можете видеть. Они действительно эквивалентны. В настоящее время, у нас есть эти рода подготовки колес на в виде строки в CS50 библиотека, но в чуть более недели или таким образом мы собираемся удалить, что обструкция в целом и на самом деле Посмотрите, что уголь и звезды , и как те, относятся к памяти представление в целом. Таким образом, мы вернемся к этому. 

Другие вопросы по нашей ARGV или агдс? Да. АУДИТОРИЯ: Почему это вернуться Ошибка [неразборчиво]? DAVID МАЛАН: Почему сделал это возвращает ошибку only-- о! В предыдущем случае, когда мы были возиться вокруг с памятью, почему это только возвращает ошибку когда я действительно набрали большое количество? Короткий ответ, мы просто повезло. Вообще говоря, компьютер выделяет память в кусках, и он дал мне достаточно большой кусок, что Я ушел, не будучи замеченным, трогательной кронштейна 2, кронштейна 3, Кронштейн 50, но как только я нажал моя удача, я пошел за Границы кусок памяти операционная система дала мне. И вот, когда его прижимаются и сказал, нет. Ошибка сегментации. Да. 

АУДИТОРИЯ: Как компьютер знать значение агдс? 

DAVID МАЛАН: Как компьютер знать значение агдс? Когда вы запускаете программу, что программа, по характеру мигающей строке передается массив Слова, которые были введенные в командной строке, что было печатается в подсказке. И так это ваша операционная система, которая по существу заполняет аргументы главных для вас. Так вот одна из услуг что вы получите, своего рода тайно под капотом операционной системы. Другие вопросы? Да. 

АУДИТОРИЯ: Что это значит дамп? DAVID МАЛАН: Что это значит дамп? Так что это хороший вопрос. И позвольте мне вернуться в этот каталог здесь. И вы заметите, что У меня есть новый файл там. Это действительно называется ядро, и это на самом деле, как правило, приличного размера файла. То есть по сути снимок содержимое памяти моей программы или ОЗУ, когда он разбился. И это будет полезно, потенциально, диагностически, как только мы говорим в будущей лекции и раздел об отладке, потому что вы можете на самом деле делать эквивалент цифровой вскрытия на этом файле, чтобы помочь выяснить то, что вы сделали не так в вашей программе. Да. 

Зала: агдс команды в Сам, или вы можете назвать это ничего? 

DAVID МАЛАН: Хороший вопрос. Является агдс команды в себе, или вы можете назвать это ничего? Это определенно не является командой. Это просто переменной имя или имя аргумента в, и так абсолютно Можно назвать это Foo, мы могли бы назвать этот бар, которые имеют тенденцию быть выхода на словах, что компьютерные ученый идет в. Но по соглашению, мы используем ARGC и ARGV. Но это всего лишь человек Конвенция, не более того. Хорошо. Так получается, я был говорю немного белого lie-- и, честно говоря, в будущем, вы увидите мы говорили другие белые ложь. Но сейчас, мы собираемся отогните один из них. В этом случае здесь, когда я ранее побежал программу как ./hello или ./hello-3 Zamyla, мы должны были содержимое моего памяти компьютера, глядя примерно как это. Но вспомним, что строка является. Что мы говорим, неделю назад, что строка на самом деле под капотом? АУДИТОРИЯ: Массив символов. DAVID МАЛАН: Это массив символов, не так ли? Таким образом, мы, возможно, есть массив строки, но, в свою очередь, строка это массив символов. Так что, если я действительно хочу быть анал, когда я рисую эту картину, Я должен действительно быть рисунок это немного больше, как это, причем в каждой из них Индексы моей агду массива, существует сама по себе всю строку , что само по себе в массиве. А теперь ложь мы говорим сегодня является то, что картина не выглядят вполне так. В самом деле, небольшие квадраты обычно за пределами больших прямоугольников есть. Но мы вернемся к тому, что в скором времени. Но это ./hello обратный слеш 0, что быть специальный символ, который разграничивает конец строки, и у нас есть еще один за Имя Zamyla в. Так что же это значит? 

Ну, позвольте мне идти вперед и открыть две другие примеры , которые доступны в Интернете. Одна из них называется argv1.c , а другой argv2. Это супер-простая программа, которая отличается от прошлых программ в том, что теперь я использую агдс и ARGV здесь. И теперь я интеграции с цикл в строке 18, от г = 0 на до ARGC. И что же я буду делать с этой строки кода здесь? На английском. Это, очевидно, демонстрирует использование агдс. Но в английском языке, что делает это сделать, если я запустить эту программу? Да? 

АУДИТОРИЯ: Это будет печатать ваши экран столько раз, сколько вы хотите. DAVID МАЛАН: Точно. Поэтому, что бы слова ввода введите в командной строке, это собирается извергнуть им на меня по одному в строке. Так что давайте идти вперед и делать это. Отпусти меня в моем каталоге и делают argv1 ./argv1. А теперь, давайте держать его просто. Давайте ничего не делать в первую очередь. Это сделал распечатать одну вещь, и вот действительно название программы, потому что это в кронштейне 0. Если я сейчас сказать Фу, он собирается сделать эти двое, и если я говорю Foo бар, он собирается сказать эти три вещи. Теперь вот несколько интересно, может быть. Но напомним, что ARGV является массив строк, но строка это массив символов, так что мы можем взять вещи на ступеньку выше и применить, что основная Логика и сделать код, который выглядит немного более загадочным, по общему признанию. Но, имея вложенный цикл, то сродни к тому, что вы, возможно, помните из Марио, например, если вы сделали это таким образом. 

Так что теперь заметить в строке 19, я снова перебора моих аргументов, от 0 на до ARGC. И теперь в соответствии 21-- Я заимствования трюк из последнего week-- Я проверяю, что является Длина агду кронштейна I. Я храню этот ответ в п. А потом я интегрируя от J на до п, где J устанавливается на 0. Так, Конвенция для подсчета. Если вы уже использовали I, если у вас есть вложенный цикл, вы не можете использовать я снова, в противном случае вы будете колошматить, потенциально, значение за пределами внутреннего цикла. Поэтому я использую J по соглашению. Мы могли бы использовать к. Если у вас есть больше, чем к, вы, вероятно, слишком много вложенности, обычно. Но теперь, заметил моего Printf линия немного отличается. Я не печатает% S, я печать% С, что, конечно, является заполнителем для гольца. 

А теперь обратите внимание этот синтаксис. Новый. Мы не видели его раньше. Но логически, это просто означает, получить-ю строку в ARGV и получить JTH какой? АУДИТОРИЯ: Характер. DAVID МАЛАН: Характер в этой строке. Так с помощью квадратных скобок затем квадратных скобках, это дайвинг первый в строки ARGV в, , а затем второй квадратные скобки с J дайвинг в характерах что определенная строка в ARGV. А потом, для ровного счета, Я печатаю новую линию здесь. Так что теперь позвольте мне идти вперед и открыть до немного большего окне так что мы можем увидеть это в действии. Отпусти меня в этой папке. А теперь делают агду-2-- whoops-- сделать ARGV-2, ./argv 2. Enter. И это немного трудно читать вертикально, но это действительно имя Программа, после чего пустой строке. Теперь позвольте мне идти вперед и делать нечто. Аналогично трудно читать, но это действительно печати одного символа в строке. А если я бар, то теперь печать те построчно. Так вынос здесь не столько что, ничего себе, смотреть на этой аккуратной новый трюк где вы можете получить на содержимое специфических букв массив в, а то, как мы принимаем это основная идеи, как индексирование в массив, а затем индексации в Массив, который был в этом массиве, и просто применяя те же идеи немного более сложные примеры. Но основы действительно не изменилось, даже с прошлой недели. 

Теперь это своего рода своевременно, в том, что, напомним, в нулевой неделе мы играли с телефонной книгой, как это. И хотя это, очевидно, физические кусочки бумаги, Вы можете рода думать Телефонная книга в виде массива. Конечно, если бы вы были повторно реализовать это кусочки эти бумажки в компьютере, возможно вы должны использовать то как массив для хранения всех тех, имена и номера из всех пути до Z. Так что это хорошо, потому что это позволяет нам возможность, возможно, рассмотреть, как вы могли бы на самом деле реализовать нечто подобное. Как и в серии дверей здесь. Так что, если я could-- нам нужно один добровольно прийти на до. Посмотрим. Незнакомое лицо, возможно, незнакомое лицо, возможно. Как насчет оранжевым цветом? Вот. Оранжевый рубашка, давай до. 

Давайте пойдем дальше теперь и ход эти двери на сторону, двигаться их из пути на мгновение. Как тебя зовут? 

AJAY: 

DAVID МАЛАН: Аджай. Дэвид. Приятно познакомиться. Хорошо. Итак, мы имеем за эти шесть Двери в цифровом виде screen-- или, скорее, семь дверей на screen-- целую кучу цифр. И я не сказал вам ничего в advance-- согласился? AJAY: Ничего заранее. DAVID МАЛАН: Все, что я хочу, чтобы ты Теперь, чтобы найти для меня, и для нас, действительно, число 50, один шаг за один раз. 

AJAY: Номер 50? 

DAVID МАЛАН: 50 Число. И вы можете показать то, что это За каждым из этих дверей просто прикасаясь к нему пальцем. Черт возьми. [Смех] 

[Аплодисменты] 

Очень хорошо сделано. Хорошо. У нас есть прекрасный подарок Приз для вас здесь. Ваш выбор фильмов мы обсудили на прошлой неделе. 

AJAY: О, Боже. О, я никогда не видел SpaceBalls. 

DAVID МАЛАН: Космические яйца. Хорошо. Так держать только на один момент. How-- давайте сделаем это обучаемы moment-- как вы идти о нахождение количества 50? AJAY: Я выбрал случайно. DAVID МАЛАН: Таким образом, вы выбрали случайно и повезло. AJAY: Да. DAVID МАЛАН: ОК. Отлично. Так что теперь, было вам не стали удачливыми, что еще могло бы произойти за этими дверями? Так что, если я иду вперед и выявить эти цифры здесь, они на самом деле в случайном порядке. И лучшее, что вы могли бы иметь сделано, честно говоря, по, в конечном счете,, в худшем случае, проверка их всех. Таким образом, вы получили супер-повезло, что не то, что мы назвали бы алгоритм. Да, поздравляю. Но теперь let's-- юмора меня, если бы вы могли. Пойдем в этой вкладке здесь. А вот цифры в четко что, кажется, случайный порядок, , и они были. Но теперь, если я вместо претензии что за этими дверями это числа, которые сортируются. Сейчас целью является также найти нам номер 50. Но сделать это алгоритмически, и расскажите, как вы собираетесь об этом. И если вы найдете его, вы держите фильм. Вы не находите это, вы даете его обратно. AJAY: Так что я собираюсь проверить концы во-первых, чтобы определить, there's-- [Смех и аплодисменты] DAVID МАЛАН: Здесь вы идете. Давайте взглянем на один предшественников Аджая, Шон, который был не столь удачлив. Итак, ваша задача здесь, Шон, состоит в следующем. Я скрывается за них Двери число семь, но убранный в некоторых из этих дверей а другие неотрицательные числа. И ваша цель думать об этом Верхний ряд чисел, как только массив. Мы просто последовательность частей бумаги с номерами за ними. И ваша цель, только с помощью верхней Массив здесь, найти мне номер семь. И мы тогда будем критиковать как вы ходите делать это. Найти нам номер семь, пожалуйста. Количество 5, 19, 13. Это не вопрос с подвохом. 1. В этот момент ваш счет не очень хорошо, так что вы могли бы также продолжать идти. 3. Продолжай. Честно говоря, я не могу не задаться вопросом, то, что вы даже думать о. 

ШОН: Я могу взять только из верхнего ряда. DAVID МАЛАН: только верхний ряд. Итак, вы получили три осталось. Так найдите мне 7. 

[Аудитория кричит ПРЕДЛОЖЕНИЯ] Так как из них были удивительно по очень разным причинам. Так что это, где мы остановились минуту назад, и ключевых идей здесь было эти двери были номера за ними, которые были отсортированы, идеальным вынос, для которых является то, что вы могли бы сделать принципиально лучше в этот второй example-- и, действительно, это было Шона Первая попытка с случайных чисел так же, как before--, но как только как эти цифры сортируются, так же, как в телефонной книге, что вы можете, очевидно, делать? Или, как можно использовать эти знания? Да. 

АУДИТОРИЯ: Вы идете на полпути [неразборчиво]. DAVID МАЛАН: Да. Точно. Так начальная инстинкт Аджая было проверить концы, насколько я помню, а затем мы вроде отделкой Пример быстро. Но если мы начали делать это более методично вдоль этих линий, но начиная, возможно, в средний, потому что они сортируются, как только мы открываем номер 16, поэтому мы знаю-- и давайте делать то, that-- мы Поэтому знаю, что 50, в сегодняшнем случае, надо быть справа. Так же, как в нулевом, когда неделю мы разорвали телефонную книгу пополам и бросил половину Проблема же, та же идея здесь. Мы можем бросить эту половину проблемы далеко. И, наверное, то, что вас может сделать алгоритмически, как только вы знаете, что 50 должно быть вправо, если это в любом месте, это попытаться там, в середине из оставшихся дверей. Конечно, 50 выше чем 42, поэтому мы можем бросить это остальные четверть проблемы в сторону, и, наконец, определить что-то вроде 50. Но так же, как с Телефонная книга, эти цифры были даны нам уже в отсортированный порядок, который оставляет нас с вопросом, как вам получить вещи в определенном порядке? И, честно говоря, по какой стоимости? Это одна вещь, чтобы быть передал телефонную книгу а затем произвести впечатление на своих друзей, находя номер телефона действительно быстро, не так ли? Разрывая 32 страниц, чтобы найти человек из 4 миллиардов страниц, мы сказали был одним ярким примером. Но сколько времени это займет Verizon для сортировки телефонной книги? Сколько времени это займет нас сортировать эти семь цифр? Это вопрос, который мы до сих пор полностью игнорируются. 

Так что давайте ответить на этот вопрос сейчас. И мы все из фильмов сейчас, но у нас есть некоторые стресс шары. Если, скажем, восемь добровольцев Не возражал бы присоединиться к нам здесь? Давайте идти вперед и делать, как о вы четверо, трое из вас здесь? Получить новые лица. И четыре из вас есть? И now-- давайте не смещения здесь-- и номер восемь сюда на конце. Поднимайтесь. Хорошо. Итак, что мы имеем здесь для каждый из вас является число. Если вы хотели бы пойти вперед, взять этот номер. Как тебя зовут? 

Арти: Арти. 

DAVID МАЛАН: Арти, ладно. Ты число 1. 

AMIN: Амин. DAVID МАЛАН: Амин. Дэвид. Ты число 2. И идти вперед, а я передаю Вы листы бумаги, выстраиваются себя в передней части музыки выступает в том же порядке, что и там. 

ANDY: Привет, Энди. 

DAVID МАЛАН: Энди, это приятно видеть вас. Номер 3. 

JACOB: Иаков. 

DAVID МАЛАН: Иаков, число 4. Добро пожаловать на борт. ГРАНТ: Грант. DAVID МАЛАН: Грант. Номер 5. 

Аланна: Аланна. 

DAVID МАЛАН: Аланна, число 6. 

ФРАНЧЕСКА: Фрэнсис. DAVID МАЛАН: Фрэнсис, число 7. И? 

Рейчел: Рэйчел. 

DAVID МАЛАН: Рэйчел, число 8. Хорошо. Идем дальше и получить себе в этом порядке. Позвольте мне сказать одну остальные музыка стоит на месте. Где вам нужен стенд? Хорошо. Идем дальше и просто поставить свои номера где зрители могут увидеть их на, пюпитр наружу. И, надеюсь, наша первая проверка исправности здесь-- 4, 2, 6. Ой-ой. Подожди минуту. Мы не имеем 8. Мне нужно выселить вас из Пример-то. Количество Нет, это нормально. Посмотрим. Мы можем сделать это. Ожидание. Там мы идем. Правильно. Хорошо. Итак, теперь у нас есть 8, 1, 3 7, 5. Хорошо. Отлично. 

Так что вопрос в руке, в какой ценой, и через то, что метод, мы можем на самом деле разобраться эти цифры здесь так что мы можем отчасти работать в обратном направлении, в конечном счете, и decide-- это действительно впечатляет, это действительно эффективным, что я могу разделить и завоевать телефонную книгу? Это действительно эффективно, что Я могу разделяй и властвуй эти цифровые штук бумаги на борту, если возможно, это будет стоить нам состояние во времени или энергии или циклы процессора на самом деле получить наши данные в какой определенном порядке? Так что давайте задать этот вопрос. 

Так прежде всего, эти цифры в значительной степени случайном порядке, и я собираюсь предложить один алгоритм, или процесс , с помощью которого мы можем разобраться этих людей. Я собираюсь подойти это довольно наивно. И я собираюсь признавать что это вроде много для меня обернуть свой ум вокруг установить целые данные сразу. Но вы знаете, что? Я собираюсь сделать некоторые очень простые предельные исправления. 4 и 2 вышли из строя, если цель состоит в том, чтобы перейти от 1 до от 8. Таким образом, вы знаете, что? Я буду иметь вас ребята поменять, если вы переключитесь физически позиции и Ваши кусочки бумаги. Теперь 4 и 6, это в порядке. Я собираюсь оставить те быть. 6 и 8, те, в порядке. Going, чтобы оставить их в покое. 8 and1, не в порядке. Если вы два не возражал бы замены. Теперь 8 и 3, если вы, ребята, могли обменять. 8 и 7, если вы, ребята, могли обменять. И 8 и 5, если вы, ребята, могли обменять. 

Теперь, я сделал? Нет, очевидно, нет. Но я сделал Ситуация лучше, не так ли? Как там ваше имя, номер 8? 

Рейчел: Рэйчел. DAVID МАЛАН: Так Рэйчел эффективно пузырились довольно далеко, весь путь до конца мой массив чисел здесь. И так, что проблема отчасти решена. Теперь, очевидно, 2 все еще нуждается в двигаться немного, и 4 и 6 и 1. Но я, кажется, получили чуть ближе к решению. Так давайте применим этот же наивно эвристический снова. 2 и 4, ОК. 4 и 6, ОК. 6 и 1, мм мм. Давайте своп. 6 и 3, мм мм. Давайте своп. 6 и 7 в порядке. 7 и 5, Нет. Давайте своп. А теперь 7 и 8. И то, что тебя зовут? ФРАНЧЕСКА: Фрэнсис. DAVID МАЛАН: Фрэнсис. Так что теперь Фрэнсис находится в еще лучше Положение, потому что теперь 7 и 8 правильно пропускают до вершины. Так 2 и 4, ОК. 4 и 1, своп давай. 4 и 3, своп давай. 4 и 6, что ты в порядке. 6 и 5, своп давай. И теперь эти ребята хороши. Мы почти на месте. 2 и 1, из того, так поменять. А теперь сделаем простой тест. 2 и 3, 3 и 4, 4 и 5, 5 и 6, 6 и 7, 8. Итак, мы закончили. 

Но какой ценой я тоже сортировать здесь эти цифры? Ну, сколько шагов я тоже потенциально принять при сортировке этих людей? Ну, мы еще вернемся к этому вопросу. Но, честно говоря, если вы получили немного скучно, вот и вид выявление в том, что это не было может быть, самый эффективный алгоритм. И в самом деле, если честно, я потею тем более идти назад и вперед. Это не чувствовал себя особенно эффективным. Так давайте попробуем что-то еще. Если вы, ребята, могли сбросить сами в этих восьми значений. Отличная работа. 

Давайте взглянем в цифровом виде, для всего Секунду назад мы попробовать что-то еще, на то, что только что произошло. Здесь, наверху, вы сейчас увидите визуализация этих восьми людей в результате чего синий и красный бары представлять числа. Чем выше полоска индикатора, Чем больше число. Чем короче бар, чем меньше число. И то, что вы будете видеть в случайном порядке более восьми из них. Вы будете видеть эти бары получать отсортирован по этому же алгоритму, или набор инструкций, которые мы будем называть в дальнейшем пузырьковой сортировки. Так заметить, каждую секунду или около того, два бара освещая красным, сравниваются компьютером. И потом, если большой бар и небольшой бар вышли из строя, они могли быть обменены для меня. 

Теперь это невероятно утомительно смотреть это, конечно, очень долго, но обратите внимание, takeaway-- большие бары, движущихся вправо, небольшие бары движущиеся влево. Давайте остановить этот процесс и ускорить этот процесс чтобы быть намного быстрее, поэтому мы можем получить высокого уровня чувство что, действительно, пузырьковой сортировки делает. В самом деле, это бьется, чтобы Правая часть списка, или массив, тем больше баров. И наоборот, маленькие бары пузырится свой путь вниз влево, хотя в более быстром темпе чем мы ранее сделали. Так, сложнее увидеть с людьми, но визуально это действительно то, что происходило. 

Но давайте попробуем принципиально Другой подход сейчас. Давайте попробуем другой Алгоритм, которым мы должны вас парни начинают в них оригинальный позиции, которая была такой порядок здесь. И давайте идти вперед сейчас. И я собираюсь сделать то еще проще, не так ли? В ретроспективе, обмен попарно раз и снова, почти немного умен. Давайте делать вещи еще более наивно, где, если я хочу, чтобы отсортировать эти люди, позвольте мне продолжать смотреть для наименьшего элемента. Так прямо сейчас, 4 является наименьшее число я видел. Я буду помнить это. Нет, 2 лучше, и помните, что. 1 еще меньше. 3, 7, 5. Хорошо. Одно-- как тебя зовут снова? 

Арти: Арти. 

DAVID МАЛАН: Арти. Так, Арти, идти вперед. Я собираюсь вытащить вас из линии. Если бы вы могли вернуться сюда. И мне нужно, чтобы освободить место для него. У нас есть точки принятия решения здесь. Как мы могли бы освободить место для Арти здесь В начале, когда число 1 принадлежит? 

АУДИТОРИЯ: Shift. 

DAVID МАЛАН: Хорошо, мы может сместить всех. Но предложить оптимизацию. Это чувствует себя немного раздражает для меня, чтобы спросить четыре человека двигаться весь путь вниз. Что еще я мог сделать? 

АУДИТОРИЯ: Переключатель их. 

DAVID МАЛАН: Переключатель их. И то, что тебя зовут? 

JACOB: Иаков. DAVID МАЛАН: Иаков, двигаться. Гораздо более эффективным только, чтобы иметь Места своп Иаков с Арти, в отличие от вынуждает все четыре из этих людей, большое спасибо, чтобы их правильное положение. Что приятно о Арти сейчас, он в своей правильной позиции. Давайте сделаем это снова. 2, это наименьшее число, что я видел. 3, 7, 5. Хорошо. 2, безусловно, самый маленький. Не нужно делать любую работу. Давайте сделаем это снова. 6. Наименьший? 8. Не-а. 4? Ох. Позвольте мне вспомнить 4. 3. Позвольте мне вспомнить 3. 7, 5. Самое маленькое число У меня видел на этом проходе есть 3. Если вы хотите выходи. Куда мы идем, чтобы поставить вас? И как тебя зовут? 

Аланна: Аланна. 

DAVID МАЛАН: Аланна, мы придется выселить вас. Но что является более эффективным, чтобы просто поменять двух человек, чем иметь несколько человек на самом деле обойти более. Теперь давайте сделаем это снова. Я собираюсь выбрать 4, так выходи. А кто будет двигаться? Номер 8, конечно. Если я сейчас найти номер 5, выходи. Номер 8 собирается получить снова выселяют. Теперь я собираюсь найти номер 6 на месте. 7 на месте. 8 на месте. 

То, что мы только что сделали сейчас то, что называется выбор рода, и если мы себе это, это будете чувствовать себя немного по-другому. Давайте пойдем дальше и от этого Меню здесь, это visualization-- давайте изменим этот to-- давай, Firefox. Давайте изменим это в мой выбор рода. И давайте ускорить его, как и прежде, и начать визуализацию сейчас. И этот алгоритм имеет другое чувство к нему. На каждой итерации, честно говоря, это еще более простым. Я просто выбрав самый маленький элемент. Теперь, честно говоря, я немного повезло, что Время, в том, что он сортируются очень быстро. Элементы были случайными. Это не так, как мы будем в конечном итоге см, принципиально быстрее. Но давайте посмотрим, третий и последний подходить здесь относительно того, что происходит. Так что давайте идти вперед и сбросить вас, ребята в последний раз, чтобы быть в этом порядке здесь. 

А теперь, я собираюсь быть немного более умным, просто чтобы закруглить наши алгоритмы. Я собираюсь сделать это. Я собираюсь не идти назад и вперед так много. Честно говоря, я устал от все это перемещения. Я просто хочу, чтобы принять то, что я дано в начале списка, и я собираюсь разобраться что тогда и там. И вот мы. Номер 4. Я собираюсь вставить номер 4 в отсортированный список. Готово. Я утверждаю, сейчас, и просто сделать это более ясно, эта часть моего списка сортируется. Это своего рода глупой претензии, но на самом деле 4 сортируется в список размере одной. Теперь, я собираюсь взять на числа 2. Номер 2 я теперь собираюсь вставить в нужном месте. Так где же 2 принадлежат? Очевидно, здесь. Так что вперед и вернуться, если бы мог. И почему вы, ребята просто взять Ваша музыка стоит с вами на этот раз. А давайте насильно вставить вам в начале списка. Так немного больше работы. Я должен был переместить Иакова вокруг, и как тебя зовут? 

AMIN: Амин. 

DAVID МАЛАН: Амин. Но по крайней мере я не идти вперед и назад. Я просто принимать вещи, как я иду. Я просто вставляя их в нужном месте. 6, это на самом деле довольно легко. Давайте вставить вам там, если вы просто хотел отодвинуться немного. Номер 8, также довольно легко. Право там. Черт возьми. Номер 1 мы не можем просто поменять с Амином здесь, потому что это будет испортить заказа. Поэтому мы должны быть немного умнее. Так, Арти, если бы вы могли резервное копирование на мгновение. Давайте пойдем дальше и переложить сейчас, в отличие от наших предыдущих алгоритмов, чтобы освободить место для Арти прямо здесь в начале. Так, в конце концов, я отчасти делать то, что я хотел избежать прежде. И так мой алгоритм является своего рода из вспять, интеллектуально, от того, что он изначально был. Я просто делаю перемену в другой точке. Теперь я на 3. О, черт. Мы должны делать больше работы снова. Так что давайте толкать вас. Давайте перейдем 8, 6, 4-- о oh-- и 3 будет идти прямо там. Так по крайней мере небольшие сбережения на этот раз. 7, не слишком много работы предстоит сделать. Так что если вы хотите, чтобы совать назад, давайте вставим вас. И, наконец, 5, если вам хотите трещать назад, мы необходимо перенести вас, вас, Вы, до пяти на месте. 

Так что теперь, чтобы увидеть это в Высокий уровень графически, давайте сделаем этот алгоритм визуализации одного дополнительного времени. Так что это мы будем называть вставки рода. Мы будем запускать его как быстро, и начать его здесь. И это тоже имеет различные чувства. Это своего рода становится все лучше и лучше, но это никогда не идеально пока я не пойти и гладкой в ​​этих пробелов. Потому что, опять же, я только брать то, что Я уделяется слева направо. Так что я не так повезло что все было идеально. Вот почему мы должны были это немного mispositions что мы фиксированные во времени. 

Таким образом, все эти алгоритмы, кажется, работать на слегка разными темпами. На самом деле, что бы вы сказать, лучший или самый быстрый на данный момент? Bubble рода, в первую очередь? Сортировать Выбор, второй? Вносимые рода, третий? Я слышал, некоторые выбора сорта. Другие мысли? 

Вот и получается, что все эти алгоритмы принципиально так же, как эффективно, как каждый other-- или, наоборот, как неэффективной, так как друг с другом, потому что мы можем сделать принципиально лучше, чем все три из этих алгоритмов. И это немного белого лежат тоже. когда я говорю, как эффективно или неэффективной, что, по крайней мере для супер-большие значения п. Когда у нас есть всего восемь человек здесь, или, может быть, 50 или около того баров на экране, вы абсолютно заметить различия Среди этих трех алгоритмов. Но, как п, число людей, или количество цифр, или число людей в телефоне Книга, или количество веб-страниц в базе данных компании Google становится больше и больше, мы увидим, что все три из них алгоритмы на самом деле очень плохо. И мы можем сделать принципиально лучше, чем это. 

Давайте взглянем, наконец, на то, что эти алгоритмы могут походить в контекст нескольких других а также путем этом визуализация здесь что будет представлять нас количество алгоритмов. Давайте пойдем дальше и поздравить наши участники здесь, все из которых сортируются себя очень хорошо. Если вы хотели бы взять прощальный подарок. Вы можете хранить ваши номера, а также. И то, что вы увидите, или, вернее, слышать, теперь, является то, что, как мы ставим звуки в каждом из этих стержней и связать его с программным обеспечением, отличается частота звука, Вы можете обернуть свой ум больше audioly вокруг того, что каждая из этих вещей Выглядит как. Первый из которых является сортировка вставками 

[TONES] 

Это пузырьковой сортировки. 

[TONES] 

Сортировать Выбор. 

[TONES] 

То, что называется сортировка слиянием. 

[TONES] 

Гном рода. 

[TONES] 

Вот именно для CS50. Мы будем видеть Вас в среду. 

Рассказчик: И теперь, "Deep Мысли ", по Daven Фарнэме. Почему это для петли? Почему бы не сделать его лучше? Я бы сделать пять петлю. 

[Смех]