[Музыка, играющая]
>> DAVID Маланом: Это CS50.
И это как начало и end-- как literally-- почти до конца
из шестой неделе.
>> Я думал, я бы поделиться Немного веселья самом деле.
Я вытащил этот от установить данные прошлой семестра.
Вы можете вспомнить, что мы просим вас на каждый р установленной формы, если вы смотрели онлайн
или если вы присутствовали лично.
А вот данные.
Так что сегодня было очень много предсказуемым.
Но мы хотели, чтобы потратить немного времени с вами, тем не менее.
Кто-нибудь предположить, почему это График настолько пьяный, вверх вниз, вверх вниз,
так последовательно?
Что делать каждому из пиков и желоба представляют?
>> АУДИТОРИЯ: [неразборчиво]
DAVID Маланом: Действительно.
И еще забавно, не дай бог, мы проводим одну лекцию в пятницу
в начале семестра, это то, что мы видим случиться.
Поэтому сегодня, когда мы принимаем в немного больше о структурах данных.
И, чтобы дать вам более твердого тела Ментальная модель для задач в пять,
который в настоящее время вне.
Орфографические ошибки, в котором мы будем вручить вам текстовый файл некоторые 100000
плюс английские слова, и Вы будете иметь,
чтобы выяснить, как ловко загружать их в память, в оперативной памяти, используя некоторые данные
Структура вашего выбора.
>> Теперь одна такая структура данных может быть, но, вероятно, не должно быть,
довольно упрощенно связанный список, которые мы ввели в прошлый раз.
И связанный список, по крайней мере, Одно из преимуществ над массивом.
Что одно преимущество связанный список, возможно?
>> АУДИТОРИЯ: Вставка.
>> DAVID Маланом: Вставка.
Что вы имеете в виду?
>> АУДИТОРИЯ: Где угодно вместе Список [неразборчиво].
>> DAVID Маланом: Хорошо.
Таким образом, вы можете вставить элемент там, где это Вы хотите в середине списка
без перетасовать ничего, которые мы заключили, в нашем сортировки
дискуссии, не обязательно хорошо,
потому что это занимает время, чтобы действительно двигаться все эти человека влево или вправо.
И так со связанным списком, вы можете просто выделить с таНос, новый узел,
а затем обновить пару pointers-- два, три операции max--
и мы в состоянии слот кого в любом месте в списке.
>> Что еще было выгодно о связанном списке?
Да?
>> АУДИТОРИЯ: [неразборчиво]
DAVID Маланом: Прекрасно.
Идеальный.
Это действительно динамичным.
И что вы не совершает, заранее, до некоторой фиксированного размера
участок памяти, как вам придется чтобы с массивом, вверх из которых
является то, что вы можете выделить узлы только на Спрос, таким образом, используя только столько места
как вы на самом деле нужно.
В отличие от массива, вы могли бы случайно выделить слишком мало.
А потом он просто будет быть боль в шее
перераспределить новый больший массив, копировать все более, освободить старый массив,
а затем перейти о вашем бизнесе.
Или еще хуже, вы можете выделить путь больше памяти, чем вы на самом деле нужно,
и таким образом, вы будете иметь очень малонаселенной массив, так сказать.
>> Так связанный список дает эти Преимущества динамизм и гибкость
с вставки и удаления.
Но, безусловно, должна быть цена, заплаченная.
На самом деле, одна из тем, исследовали на викторине нулевой
было пару компромиссов мы видели до сих пор.
Так что цена, заплаченная или Недостатком связанного списка?
Да.
>> АУДИТОРИЯ: Нет произвольного доступа.
>> DAVID Маланом: Нет произвольного доступа.
Но кого это волнует?
Произвольный доступ звучит не убедительно.
>> АУДИТОРИЯ: [неразборчиво]
DAVID Маланом: Совершенно верно.
Если вы хотите иметь определенная algorithm--
и позвольте мне на самом деле предлагают бинарный поиск, в частности, что
является одним мы использовали довольно bit-- если у вас нет случайного доступа,
Вы не можете сделать что простую арифметику найти как средний элемент
и прыгает прямо к нему.
Вы вместо этого начать в первый элемент и линейно поиск слева
направо, если вы хотите найти средний или любой другой элемент.
>> АУДИТОРИЯ: Это, вероятно, займет больше памяти.
>> DAVID Маланом: займет больше памяти.
Где, что дополнительный Стоимость прибывающий из памяти?
>> АУДИТОРИЯ: [неразборчиво]
DAVID Маланом: Совершенно верно.
В этом случае здесь, у нас были связанный список для целых чисел,
и еще мы удваиваем объем памяти
мы должны также путем хранения эти указатели.
Теперь менее крупной сделки, как Ваши Структуры получить больше
и вы храните не ряд, но может быть, студент или какой-то другой объект.
Но дело, конечно, остается.
И так число операций на связанных списках назывались
были большими вывода N-- линейной.
Такие вещи, как вставки или поиска или удаление в случае элемента
оказался в самом конце Список будь то сортируются или нет.
>> Иногда может повезти и в так нижние границы этих операций
также может быть постоянной времени, если вы всегда смотрит на первом элементе,
например.
Но, в конечном счете, мы обещали для достижения Святой Грааль
структур данных, или некоторые приближение их,
путем постоянной времени.
Можем ли мы найти элементы или добавлять элементы или удалять элементы из списка?
Мы увидим совсем скоро.
И получается, что один механизмов мы
собирается начать использовать сегодня, Годовое потребление в р установлено пять,
на самом деле довольно знакомым.
Например, если это связка экзаменационные книг, каждая из которых
имеет студент сначала имя и фамилия на ней,
и я забрать их из в конце экзамена,
и все они довольно много в случайном порядке,
и мы хотим идти о сортировке эти экзамены, так что, как только оцениваются
это просто намного легче и быстрее сдать их обратно
для студентов по алфавиту.
Что бы ваши инстинкты быть для кучи экзаменов, как это?
>> Ну, если вы, как я, вы могли бы видеть, что это м,
так что я собираюсь рода поставить это в, если это мой стол или мой этаж, где
Я распространении вещи out-- или мой массив really--
Я мог бы поставить все Ms там.
О.
Вот А. Таким образом, я мог бы положить As здесь.
О.
Вот еще А. Я собираюсь положить, что здесь.
Вот З. Вот еще М. И так Я мог бы начать делать сваи, как это.
И тогда, возможно, я бы в дальнейшем и своего рода очень nitpicky-лы рода
отдельные сваи.
Но дело в том, я хотел бы посмотреть на входе, что я руками
и я хотел бы сделать некоторые рассчитывается Решение основано на этом входе.
Если он начинается с, положил его там.
Если он начинается с Z, поставить его на там, и все между ними.
>> Так что это техника, это как правило, известны как hashing-- Н-A-S-Н-
Обычно это означает, взяв в качестве вход и с помощью этого вход для расчета
Значение, как правило, количество, и что число является индексом в хранении
Контейнер, как массив.
Итак, другими словами, я мог бы Хэш функция, как и я, в моей голове,
что, если я вижу кого-то это Название, кто начинает с А,
Я собираюсь карту, что к нулю в моей голове.
И если я вижу кого-то, с Z, я собирается карту, что до 25 у меня в голове
а затем положить, что в последний наиболее куча.
>> Теперь, если вы думаете о не мой мозг но программа C, какие номера могли
Вы полагаетесь на для достижения этой же результат?
Другими словами, если вас имел ASCII символов A,
как вы определяете, что ведро положить его в?
Вы, наверное, не хотите, чтобы положить его в ведро 65, который
будет, как там без уважительной причины.
Где вы хотите поставить с точки зрения его стоимости ASCII?
Где вы хотите сделать его ASCII Значение придумать умнее ведра
поставить его в?
>> АУДИТОРИЯ: Минус А.
>> DAVID Маланом: Да.
Так минус-минус специально 65, если это
Столица А. Или 98, если это строчная.
И так, что позволит нам, очень просто и очень арифметически,
положить что-то в ведро, как, что.
Вот и получается, что мы на самом деле это также еще с викторины.
>> Таким образом, вы, возможно, помните, вы кружил ваш Название преподавательского стипендиата на обложке.
И имена ТФ были организованы в этих колонках по алфавиту,
хорошо, верить этому или нет, когда все 80 плюс из нас
собрались в тот вечер в классе, Последний шаг в нашем процессе аттестации
является хэш викторины в большой пространство пола в [неразборчиво]
и заложить викторины всеобщие из точно соблюдать порядок их TF-х
Имена на обложке, потому что то это намного легче для нас
искать в этом с помощью линейных поиск или какой-то хитрости
для TF найти его или викторины ней студентов.
>> Так эта идея хеширования что вы увидите это
довольно мощный на самом деле довольно обычным и очень интуитивным,
так же, как, возможно, разделить и захват был нулевой неделе.
Я перенесемся в Hackathon Пару лет назад.
Это было Zamyla и пару Другие студенты персонал поздравительные
как они вошли.
И у нас был целый букет складывания столы там с бейджи.
И мы теги имен организован с как как над там
и Zs там.
И поэтому один из ТФ очень умно написал это как инструкции
в течение дня.
И в 12-й неделе семестра этом все имело смысл, и все
знал, что делать.
Но в любое время вы имеете очередь таким же образом,
вы реализуете же понятие хэш.
Так что давайте формализовать это немного.
Вот это массив.
Это обращается, чтобы быть немного Широкий просто изобразить, визуально,
что мы могли бы поставить струны в чем-то вроде этого.
И этот массив явно размер 26 всего.
И дело называется Таблица произвольно.
Но это всего лишь исполнение художника того, что может быть хэш-таблицу.
>> Так хэш-таблицу теперь собирается быть выше, структура данных уровня.
В конце дня мы собираемся, чтобы увидеть, что вас
может реализовать хэш-таблицу, которая это так же, как регистрация в линии
на Hackathon так же, как это Таблица используется для сортировки экзаменационные книги.
Но таблица хэш рода этом высоком уровне
Концепция, которая может использовать массив под капот, чтобы реализовать его,
или это может использовать список длины, или даже возможно, некоторые другие структуры данных.
А теперь вот theme-- взятие некоторые из этих фундаментальных ингредиентов
как массив и этого здания блокировать сейчас из списка длины
и, увидев, что еще мы можем построить поверх тех, как ингредиенты
в рецепте, что делает все более и более интересные и полезные окончательные результаты.
>> Так с хэш-таблицы мы могли бы реализовать его
в памяти наглядно, как это, но как может он на самом деле быть закодированы до?
Ну, может быть, как просто это.
Если ПОТЕНЦИАЛ заглавными буквами, это просто некоторые constant-- например 26,
для 26 букв alphabet-- Я мог бы назвать свою таблицу переменных,
и я мог бы утверждать, что я собираюсь положить текстовые звезды в там, или строки.
Так что это так просто, как это, если вы хотите реализовать хэш-таблицу.
И все же, это действительно просто массив.
Но, опять же, хэш Таблица теперь то, что мы будем
называют абстрактный тип данных, это только рода концептуальной слоев сверху
о чем-то более мирской Теперь хотелось массив.
>> Теперь, как мы идем о решении проблем?
Ну, раньше я была роскошь иметь достаточно места таблицы здесь
так что я мог бы поставить викторины где угодно, я хотел.
Так, как может идти здесь.
Zs может идти здесь.
Г-жа может идти здесь.
А потом у меня было некоторое дополнительное пространство.
Но это что-то вроде обмана права Теперь из-за этого стола, если я действительно
думал об этом как массив, просто будет какого-либо фиксированного размера.
>> Технически, если я тяну до викторины другого студента
и увидеть, о, это человек-х Имя начинается с А также,
Я вроде хочу поставить его там.
Но как только я положил его туда, если эта таблица действительно представляет собой массив,
Я собираюсь быть переопределение или удалив кто викторина этот студент является.
Не так ли?
Если это массив, только одна вещь может перейти в каждой из этих клеток или элементов.
И так я вроде есть выбирать.
>> Теперь ранее я вроде обманули и сделали это, или я
только отчасти укладываются их друг над другом.
Но что не собирается лететь в коде.
Так где я мог бы поставить Второй студент, чье имя
это если все, что я имел это доступны табличного пространства?
И я использовал три слота и его Похоже, есть только несколько других.
Что вы могли бы сделать?
АУДИТОРИЯ: [неразборчиво]
DAVID Маланом: Да.
Может быть, давайте просто держать его просто.
Не так ли?
Это не укладывается, где я хочу поставить его.
Так что я собираюсь поставить его технически, где B пойдет.
Теперь, конечно, я начинаю рисовать себя в угол.
Если я доберусь до студента чье имя на самом деле B,
Теперь B собирается быть немного сдвинулся вперед, как может случиться, да,
если это B, теперь он должен пройти здесь.
>> И так это очень быстро может стать проблематичным,
но это техника, которая на самом деле упоминается как линейная зондирования,
в котором вы просто оценить уровень своих Массив быть вдоль линии.
И вы только отчасти зонд или проверять каждый доступный элемент
поиск свободного места.
И как только вы найдете один, вы поместите его в там.
>> Теперь, цена уделяется сейчас для этого решения является то, что?
У нас есть массив фиксированного размера, и когда я вставляю имена
в нее, по крайней мере, на начальном этапе, что время работы вставки
для сдачи студентов викторины в правильных ведра?
Big O чего?
>> АУДИТОРИЯ: н.
DAVID Маланом: Я слышал, большой O п.
Это не так.
Но мы будем дразнить друг от друга почему через минуту.
Что еще это может быть?
>> АУДИТОРИЯ: [неразборчиво]
DAVID Маланом: И позвольте мне сделать это визуально.
Так, предположим, это буква S.
>> АУДИТОРИЯ: Это один.
DAVID Маланом: Это один.
Не так ли?
Это массив, который значит у нас есть произвольный доступ.
И если мы думаем, что это как ноль и это как 25,
и мы понимаем, что, ой, вот мой вклад S,
Я могу, конечно, конвертировать S, ASCII символов,
на соответствующий номер между нулем и 25
, а затем немедленно положить его где она принадлежит.
>> Но, конечно, как только я доберусь до Второй человек, который зовут А или В или С
в конце концов, если я использовал линейный зондирования в качестве моего решения,
время работы вставки в худшем случае
на самом деле происходит, чтобы превратится в чем?
И я слышу его здесь Правильно рано.
АУДИТОРИЯ: [неразборчиво]
DAVID Маланом: Так это н действительно когда-то у вас есть достаточно большой набор данных.
Так, с одной стороны, если ваш массив достаточно велик
и ваши данные достаточно редки, вы получить эту красивую постоянное время.
Но как только вы начинаете все больше и больше элементов,
и только статистически Вы получаете больше людей с буквой
Как их имя или письмо B, это может потенциально
переходит во что-то более линейными.
Так что не совсем идеально.
Так мы могли сделать лучше?
>> Ну, то, что было нашим Решение раньше, когда мы
хотят иметь больший динамизм, чем что-то вроде массива разрешено?
АУДИТОРИЯ: [неразборчиво]
DAVID Маланом: Что мы вводим?
Да.
Так связанный список.
Ну, давайте посмотрим, что связано Список может сделать для нас, а не.
Ну, позвольте мне предложить, что мы рисовать картину следующим образом.
Теперь это уже другая картинка из примера
с другой текст, на самом деле, что на самом деле, используя массив размером 31.
И этот автор просто решил хэш строки
не на основе имен этого лица, но на основе их даты рождения.
Независимо от месяца, они полагали, если вы родились с первого месяца
или 31-е число месяца, автор будет хэш на основе этого значения,
с тем, чтобы распространить имена из немного больше, чем просто 26 пятна могут позволить.
И, возможно, это немного более равномерное чем идти с букв алфавита,
потому что, конечно, есть, вероятно, Чем больше людей в мире с именами
что начало с чем, конечно, некоторые другие буквы алфавита.
Так, может быть, это немного более равномерное, предполагая
Равномерное распределение младенцев через месяц.
>> Но, конечно, это все еще несовершенны.
Не так ли?
Мы с коллизии.
Несколько человек в это Структура данных по-прежнему
имеющий ту же дату рождения, по крайней мере Вы, независимо от месяца.
Но то, что автор сделал?
Ну, похоже, что мы имеем массив на левой стороне, проведенной вертикально,
но вот только исполнение художника.
Это не имеет значения, в каком направлении вам обратить массив, это все-таки массив.
Что это массив, по-видимому?
>> АУДИТОРИЯ: связанный список.
>> DAVID Маланом: Да.
Похоже, что это Массив связанного списка.
Итак, еще раз, на этот момент рода использования этих структур данных сейчас
в качестве ингредиентов в более интересные решения,
Вы можете абсолютно взять фундаментальная, как массив,
а затем взять что-то больше Интересно, как связанный список
и даже объединить их в еще более интересным структура данных.
И в самом деле, это тоже будет назвать хэш-таблицу,
в результате чего массив действительно хеш-таблица,
но, что хеш-таблица имеет цепи, так сказать,
что может расти или уменьшаться на основе Количество элементов вы хотите вставить.
>> Теперь, соответственно, что время работы в настоящее время?
Если я хочу, чтобы вставить кого- чей день рождения 31 октября
где он или она?
Хорошо.
В самом низу, где он говорит 31.
И это прекрасно.
Это было постоянное время.
Но что, если мы находим кого-то другого чей день рождения, давайте посмотрим,
Октябрь, ноябрь 31 декабря?
Где он собирается идти?
То же самое.
Двухступенчатая же.
Это постоянная, хотя не так ли?
Хорошо.
На данный момент он является.
Но в общем случае, чем больше людей мы добавляем,
вероятностно, мы собираемся чтобы получить больше и больше столкновений.
>> Теперь это немного лучше, потому что технически
Теперь мои цепи может быть в в худшем случае, как долго?
Если я вставляю русский народ в это более сложная структура данных, русский народ,
в худшем случае это будет н.
Почему?
>> АУДИТОРИЯ: Потому что, если все имеет тот же день рождения,
они собираются быть одна линия.
DAVID Маланом: Прекрасно.
Это может быть немного надуманный, но действительно, в худшем случае,
если каждый человек имеет тот же день рождения, учитывая входы у вас есть,
Вы будете иметь, массово длинная цепочка.
И так, вы могли бы назвать это хэш-таблицу, но на самом деле это
просто массивный связанный список с в целом много неиспользуемого пространства.
Но в целом, если считать, что по крайней мере, дни рождения uniform--
и это, вероятно, нет.
Я делаю это.
Но если предположить, для ради обсуждения
что они, то в теории, если Это вертикальное представление
из массива, а затем, надеюсь, вы собирается получить цепей, которые являются, вы знаете,
примерно такой же длины, где каждый из это представляет собой день месяца.
>> Теперь, если есть 31 дней в месяц, что означает мое время работы действительно
большой вывода п над 31, которые чувствует себя лучше, чем линейный.
Но то, что было одним из наших Обязательства пару недель
назад, когда он пришел к выражению время работы алгоритма?
Просто только посмотрите на высоком срок заказа.
Не так ли?
31, безусловно, полезно.
Но это по-прежнему большой O п.
Но одна из тем, из проблем установить пять
будет в признать, что абсолютно,
асимптотически, теоретически Эта структура данных
нет лучше, чем просто один массивный связанный список.
И в самом деле, в худшем случае, это хеш-таблицы может превратится в что.
>> Но в реальном мире, с нами люди что собственных компьютерах Mac или ПК или что
и работаете реальный мир Программное обеспечение на реальных данных,
какой алгоритм вы собираетесь предпочитаете?
Тот, который принимает конечные шаги или тот, который берет н делится на 31 шагов
найти какой-то фрагмент данных или искать некоторую информацию?
Я имею в виду, абсолютно те 31 марок Разница в реальном мире.
Это в 31 раз быстрее.
И мы, люди, конечно, понравится, что.
>> Так понимаю, дихотомию там между фактически
говорить о том, теоретически и асимптотически которые определенно
имеет значение, как мы видели, но в реальном мире,
если вы заботитесь о просто сделать человек счастлив по общим входам,
Вы могли бы очень хорошо хотят принимать Дело в том, что, да, это линейная,
но это в 31 раз быстрее чем линейная может быть.
А еще лучше, мы не просто должны сделать что-то произвольное, как дата рождения,
мы могли бы потратить немного Чем больше времени и ум
и думаю о том, что мы могли бы сделать, имя человека и, может быть,
их дата рождения объединить тех, ингредиенты, чтобы выяснить что-то
что это действительно больше, равномерное и менее пьяный,
так сказать, чем этой картине В настоящее время предполагает, что это могло бы быть.
Как мы могли реализовать это в коде?
Ну, позвольте мне предложить, что мы просто одолжить синтаксис мы
использовать пару раз до сих пор.
И я собираюсь определить Узел, который снова
это общий термин для только некоторые Контейнер по какой структуре данных.
Я собираюсь предложить, чтобы строка будет там.
Но мы собираемся начать принимать те, обучение колес от теперь.
>> Нет больше CS50 библиотека действительно, если вы не хотите
использовать его для вашего финале Проект, который прекрасен,
но сейчас мы собираемся отступать занавес и говорят, что это всего лишь символ звезды.
Так слова там будет имя человека в вопросе.
И теперь у меня есть связь Здесь к следующему узлу
так, что они представляют каждый из узлов
в цепи, потенциально, из связанного списка.
>> А теперь, как я заявляю, саму таблицу?
Как объявить всю эту структуру?
Ну, на самом деле, так же, как я использовал указатель чтобы только первый элемент списка
до, так же я могу только сказать, Мне просто нужно кучу указателей
осуществить весь этот хэш-таблицу.
Я собираюсь есть массив называется таблица для хэш-таблицы.
Это собирается быть емкости размера.
Вот сколько элементов может поместиться в него.
И каждый из этих элементов в этом Массив будет узел звезда.
Почему?
Ну, за эту картину, то, что я реализации хэш-таблицу в качестве
эффективно в начало всего это массив, который мы нарисовали вертикально,
каждый из которых квадратов представляет собой указатель.
Это те, которые имеют косую черту через них просто нулевым.
И те, которые имеют Стрелки, идущие справа
фактические указатели на фактические узлов, Ergo начало связанного списка.
>> Так вот, то, как мы могли бы реализации хэш-таблицу, что
реализует отдельный цепочки.
Теперь мы можем сделать лучше?
Ладно, я обещал в прошлый раз, что мы могли бы добиться постоянного времени.
И я как бы дал вам постоянная времени здесь,
но тогда не сказал на самом деле Постоянная времени, потому что это все-таки
зависит от общего Количество элементов
Вы ввода в Структура данных.
Но предположим, что мы сделали это.
Позвольте мне вернуться к экрану здесь.
Позвольте мне также проецировать это здесь, очевидно, экран, и предположим, что я сделал это.
Предположим, что я хотел, чтобы вставить имя Daven в в моей структуре данных.
>> Поэтому я хочу, чтобы вставить строку Daven в структуре данных.
Что делать, если я не использую хэш-таблицы, но я использую
что-то, что больше древовидная как родословной, где
у вас есть корень в Верхняя и затем узлы и листья
что идти вниз и наружу.
Предположим, то, что я хотите вставить Daven-х
в то, что в настоящее время пустой список.
Я собираюсь сделать следующее: я собирается создать узел в этой семье
древовидная структура данных, которая выглядит немного как это, каждый из которых
прямоугольники уже, скажем, а пока 26 элементов в нем.
И каждый из клеток в этом массиве будет
представлять букву алфавита.
>> В частности, я собираюсь лечить это, то В, то С, затем D,
этот здесь.
Так это будет эффективно представляют букву D.
Но, чтобы вставить все Daven-х назвать мне нужно сделать немного больше.
Так что я сначала буду хэш, так сказать.
Я собираюсь посмотреть на первую букву в Daven, который, очевидно, является D,
и я собираюсь выделить узел, который выглядит
как this-- большой прямоугольник большой достаточно, чтобы соответствовать весь алфавит.
>> Теперь D делается.
Теперь А. Д-А-В-Е-Н и является целью.
Так что теперь я собираюсь сделать это.
Как только я начал D уведомление нет указателя там.
Это ценности мусора на данный момент, или я мог бы инициализировать его до нуля.
Но позвольте мне продолжать идти с эта идея построения дерева.
Позвольте мне выделить еще один из них узлы, которые имеет 26 элементов в нем.
>> И знаете что?
Если это всего лишь узел в памяти, что Я создал с таНос, используя-структуру
как мы скоро увидим, Я собираюсь сделать this--
Я собираюсь нарисовать стрелку от вещь, которая представлена ​​D вниз
в этом новом узле.
А теперь, во-первых рядом Письмо на имя Daven в,
V-- D-A-V-- я собираюсь идти вперед и сделать еще один узел, как это,
в результате чего, в V элементы здесь, которые мы будем рисовать для instance-- возгласами.
Мы не будем рисовать там.
Это собирается идти сюда.
>> Тогда мы идем к считают, что это В.
А потом сюда мы собираемся индекса по сравнению с V в то, что мы будем рассматривать E.
А потом отсюда мы собираемся пойти иметь один из этих узлов здесь.
И теперь у нас есть вопрос, чтобы ответить.
Мне нужно как-то указать, что мы в конце строки Daven.
Так что я мог просто оставить его пустым.
>> Но что делать, если у нас есть Daven-х ФИО также, что
это, как мы уже говорили, Дэвенпорт?
Так что, если Daven является фактически подстрока,
префиксом гораздо более длинной строки?
Мы не можем просто постоянно сказать ничего не происходит
туда, потому что мы могли никогда не вставить слово, как Давенпорт
в этой структуре данных
>> Так что мы можем сделать, а не является лечения каждого из этих элементов
как может быть, имея два элементы внутри них.
Одним из них является указателем, в самом деле, как я делал.
Таким образом, каждый из этих ящиков это не просто одна клетка.
Но что делать, если верхняя одно-- нижний-х
будет нулевым, потому что нет Дэвенпорт только пока.
Что делать, если верхний это какая-то особая ценность?
И это будет немного трудно сделать это этот размер.
Но предполагаю, что это просто галочка.
Проверьте.
Д-А-В-Е-Н представляет собой строку В этой структуры данных.
>> Между тем, если бы я имел больше места здесь, что я мог сделать P-O-R-T,
и я мог бы поставить проверку в узле что есть буква Т в самом конце.
Так что это массово Комплекс вид структуры данных.
И мой почерк конечно, не поможет.
Но если бы я хотел, чтобы вставить что-то еще, подумайте, что мы будем делать.
Если бы мы хотели поставить Давида в, мы следовать той же логике, D-A-V,
но сейчас я хотел бы отметить в следующем Элемент не от Е, но от I до D.
Так что это будет больше узлов в этом дереве.
Мы собираемся иметь вызова таНос более.
Но я не хочу, чтобы сделать полный беспорядок изображения.
Итак, давайте вместо этого смотреть в одном который был предварительно сформулированы
как это с не точка, точка, точки, но только сокращенные массивы.
Но каждый из узлов в этом дереве здесь
представляет тот же thing-- Массив Луч размера 26.
>> Или, если мы хотим быть действительно правильное сейчас, что
если кто-то имя, как апостроф, давайте
Предположим, что каждый узел имеет фактически как 27 индексов в этом, а не только 26.
Так что это теперь будет данных Структура называется trie-- T-R-I-Е.
Trie, который, предположительно, исторически умный имя для дерева
который оптимизирован для поиск, который конечно же,
пишется с I-Е так это Trie.
Но это история синтаксического дерева.
>> Так Trie это древовидная данных Структура как родословной
что в конечном счете ведет себя так.
А вот еще один пример целая куча имен других людей.
Но вопрос сейчас под рукой то, что есть
мы получили путем введения возможно более сложной структурой данных, и один,
честно говоря, что использует много памяти.
>> Потому что даже при том, что, на данный момент, я только
с помощью указателя Д и И V и Es и Ns,
Я тратить чертовски много памяти.
Но где я провожу один ресурс, Я, как правило, ничего получить назад другой.
Так что, если я трачу больше места, что, вероятно, надежда?
Это я трачу меньше чем?
АУДИТОРИЯ: Меньше времени.
DAVID Маланом: Время.
Теперь, почему это может быть?
Ну, то, что является вставка время, с точки зрения большой O теперь,
имени, как Daven или Дэвенпорт или Дэвид?
Ну, Daven было пять шагов.
Дэвенпорт будет девять шагов, так что было бы несколько шагов.
Дэвид будет пять шагов, а также.
Так что те, конкретны номера, но, безусловно, есть
верхняя граница Длина чье-то имя.
И действительно, в задаче наборы пяти спецификации,
мы собираемся предложить что это что-то
это 40-некоторые с лишним персонажей.
>> Реально, никто не имеет бесконечно длинное имя,
который должен сказать, что длина назвать или длина строки мы могли бы
есть определенная состояние Структура, возможно, что?
Это постоянная.
Не так ли?
Это может быть большой постоянной, как 40-то, но это константа.
И это не имеет никакого зависимость от того, сколько другие названия являются в этой структуре данных.
Другими словами, если I хотел сейчас вставить
Колтон или Габриэль или Роб или Zamyla или Элисон или Белинда или любые другие имена
от персонала в этих данных Структура, является время работы
вставки и другие названия будет вообще влияние
по тому, как и многие другие элементы являются в структуре данных, уже?
Это не так.
Не так ли?
Потому что мы эффективно использовать это многослойная хеш-таблицы.
И время работы любой из этих операций
зависит не от количества элементы, которые в структуре данных
или что в конечном итоге происходит чтобы быть в структуре данных,
но по длине, что конкретно?
>> Строка быть вставлен, который делает
это асимптотически постоянным time-- большой O одного.
И, честно говоря, просто в реальный мир, это
означает вставки название Daven берет как пять шагов, или Дэвенпорт девять
шаги, или Дэвид пять шагов.
Это чертовски маленькие раз ходовые.
И, действительно, это очень хорошая вещь, особенно когда
это не зависит от общей Количество элементов в там.
Так как мы можем это реализовать Такая структура в коде?
Это немного больше, Комплекс, но все-таки это
только применение основные строительные блоки.
Я собираюсь пересмотреть нам узел следующим образом:
Ьоо называется word-- и это можно было бы назвать что-нибудь.
Но Ьоо представляет то, что я обратил как галочкой.
Да.
Это конец строки В этой структуры данных.
>> И, конечно, узел звезда там имеет в виду детей.
И, в самом деле, так же, как генеалогическое дерево, вы
рассмотрит узлы что висят от
из нижней части какой-то из родителей Элемент быть дети.
И поэтому дети собирается быть массивом 27, 27 один
просто быть для апострофа.
Мы собираемся, чтобы разобраться Особый случай этого.
Таким образом, вы можете иметь определенный Имена участников апострофы.
Может быть, даже дефис должны идти туда, но вы будете
см в р наборе 5 мы только ухода о письмах и апострофы.
>> А потом, как вы представляете сама структура данных?
Как вы представляете корень этого синтаксического дерева, так сказать?
Ну, точно так же как с связанного списка, вы нужен указатель на первый элемент.
С синтаксического дерева нужно просто один указатель на корень этого синтаксического дерева.
И оттуда вы можете хэш Ваш путь вниз все глубже и глубже
для каждого другого узла в структуре.
Так просто с этой банкой мы представляем, что-структуру.
>> Теперь Meanwhile-- О, вопрос.
>> АУДИТОРИЯ: Что Ьоо слово?
>> DAVID Маланом: Bool слово просто это C воплощение
из того, что я описал в этом поле здесь, когда
Я начал разделения каждой из элементы массива на две части.
Одним из них является указателем на следующий узел.
Другой должен быть что-то вроде флажка
сказать да, есть Слово Daven что здесь заканчивается,
потому что мы не хотим, на данный момент, Дэйв.
>> Даже при том, что Дэйв будет законным слово, что он не в синтаксического дерева
еще.
И D нет ни слова.
И D-это не то слово или имя.
Так галочкой указывает только один раз вас
ударил этот узел предыдущая путь персонажей
на самом деле это строка, как вы вставили.
Так что все Ьоо там делает для нас.
>> Любые другие вопросы о попытках?
Да.
>> АУДИТОРИЯ: Что такое перекрытие?
Что делать, если у вас есть Дэйва и Daven?
DAVID Маланом: Прекрасно.
Что делать, если у вас есть Дэйва и Daven?
Так что, если мы вставляем, говорят прозвище, для David-- Dave-- D-A-V-E?
На самом деле это супер просто.
Таким образом, мы только собираемся предпринять четыре шага.
Д-А-В-Е. И то, что мне нужно сделать, как только я ударил, что четвертый узел?
Просто собираюсь проверить.
Мы уже хорошо идти.
Готово.
Четыре шага.
Постоянное время асимптотически.
И теперь мы показали, что оба Dave и Daven являются строками в структуре.
Так не проблема.
И обратите внимание, как присутствие из Daven не сделать это
взять больше времени или меньше Время для Дэйва, и наоборот.
>> Так что еще мы можем сейчас сделать?
Мы использовали эту метафору до лотков, представляющий что-то.
Но оказывается, что стопка лотков на самом деле
демонстративное другого абстрактного данных type-- более высокую структуру данных уровня
что в конце дня это просто как массив или связанный список
или что-то более приземленным.
Но это более интересно концептуальное понятие.
Стек, как это Лотки здесь в Мазер,
как правило, называют просто that-- стек.
>> И в этом типе структуры данных у вас есть два operations--
у вас есть один под названием толчок для добавляя что-то в стек,
как положить еще один лоток Вернувшись на вершине стека.
И тогда поп, который означает, что вы взять верхний офф лотка.
Но то, что ключ о стека является то, что он получил эту любопытную характеристику.
Как столовой персонала переставляя лотки для следующего приема пищи,
что будет правда о том, как студенты
взаимодействовать с этой структурой данных?
АУДИТОРИЯ: Они собираются поп прочь.
DAVID Маланом: Они собираются поп прочь, мы надеемся на вершину.
В противном случае это просто какая-то глупая чтобы пройти весь путь до дна.
Не так ли?
Структура данных на самом деле не позволяют Вы, чтобы захватить нижнюю лоток, по крайней мере
легко.
Так что это любопытно Свойство к стеку
что последний элемент в это будет первым из.
И компьютерные ученые называют это LIFO-- последним пришел, первым вышел.
И это на самом деле есть интересные приложения.
Это не обязательно так очевидно, как некоторые и другие, но он может, конечно, быть полезным,
и оно может, в самом деле, быть реализованы через пару-разному.
>> Так что, и на самом деле, пусть мне не нырять в том, что.
Давайте сделаем это вместо этого.
Давайте посмотрим на тот, который почти Та же идея, но это немного более справедливым.
Не так ли?
Если вы один из этих мальчиков вентиляторов или девочки, что действительно любит продукты компании Apple
и вы проснулись в 3:00 выстраиваться в какой-то магазин
чтобы получить самую последнюю iPhone, вы возможно, в очереди, как это.
>> Теперь очередь очень сознательно назвал.
Это линия, потому что есть некоторые справедливость к нему.
Не так ли?
Было бы вид сосал если у вас есть получил там первый в Apple Store
но вы эффективно нижний Лоток, потому что сотрудники Apple, затем
поп последний человек, который на самом деле попал в линию.
Так стеков и очередей, хотя функционально они вроде в same--
это просто эта коллекция ресурсов, что это
будет расти и shrink-- там Этот аспект справедливости к нему,
по крайней мере, в реальном мире, где операции вы тренируетесь
принципиально отличаются.
Stack-- очереди rather--, как говорят,
две операции: очереди н и очередей d.
Или вы можете позвонить им любое количество вещей.
Но вы просто хотите, чтобы захватить понятие, что человек добавления
и, в конечном счете один вычитания.
>> Теперь под капотом, как стек и очередь может быть реализован как?
Мы не будем вдаваться в коде это потому, что чем выше уровень
Идея является своего рода более очевидным.
Я имею в виду, что ты это делают люди?
Если я первый человек в компании Apple Храните и это входная дверь,
Вы знаете, что я собираюсь стоять здесь.
И следующий человек собираюсь стоять здесь.
Так что структура данных поддается очереди?
>> АУДИТОРИЯ: Очередь.
DAVID Маланом: Ну, очереди.
Конечно.
Что еще?
>> АУДИТОРИЯ: связанный список.
>> DAVID Маланом: связаны список можно реализовать.
И связанный список хорошо, потому что тогда она может расти сколь угодно долго, в отличие
к тому, некоторое фиксированное число людей в магазине.
Но, может быть, фиксированное число мест является законным.
Потому что, если у них только есть, как 20 IPhones в первый день, может быть,
они должны только массив размера 20 чтобы представить эту очередь, которая
только сказать сейчас, как только мы начинаем говорить об этих высоких задач на уровне,
Вы можете реализовать его в любом числе путей.
И там, наверное, только собираюсь быть компромисс в пространстве и времени
или просто в собственном сложности кода.
>> А как насчет стека?
Ну, стек, мы видели слишком может быть просто эти лотки.
И вы могли бы реализовать этот массив.
Но в какой-то момент, если вы используете массив, что произойдет с лотков
Вы пытаетесь подавить?
Хорошо.
Вы только собираетесь быть в состоянии пойти так высоко.
И я думаю, что в Mather они фактически встраиваемые в это отверстие.
Так на самом деле, это почти как Mather использует
массив фиксированного размера, потому что вы можете только
подходят так много лотков в этом открытии в стена внизу колени людей.
И так, что может быть говорят, массив,
но мы, безусловно, может реализовать, что в более общем с связанного списка.
>> Ну, то, что о другой структуре данных?
Позвольте мне подтянуть один другой визуальный здесь.
Что-то вроде, как об этом один здесь?
Почему это может быть полезно иметь не что-то фантазии, как синтаксического дерева, которое
мы видели бы эти очень широкие узлы, каждый из которых находится в массиве?
Но что, если мы делаем что-то более просто, как старый школьный родословной,
каждый из которых узлы здесь только сохранении номера.
Вместо имени или потомка просто сохранении номера вроде этого.
>> Ну, жаргон мы используем в структуры данных является обе попытки
и деревья, где Trie, опять же, только один, узлы которого являются массивы,
еще, что вы могли бы использовать из начальной школы
когда вы сделали семью tree-- листья и корень
из дерева и детей родитель и их братья и сестры.
И мы могли бы реализовать дерево, Например, как просто, как это.
Дерево, если он в виде узла, один из эти круги, что имеет ряд,
это не будет иметь один указатель, а два.
И как только вы добавляете Второй указатель, вы
может на самом деле сейчас сделать вид двумерного данных
структуры в памяти.
Многое, как двумерный Массив, вы можете
есть вид двумерных связанные списки, но те,
что следуют образцу где нет никаких циклов.
Это действительно дерево с одним прародитель путь сюда, а затем
некоторые родители и дети, и внуки и правнуки.
и так далее.
>> Но то, что действительно опрятно об этом тоже, просто чтобы подразнить вас с немного кода,
Напомним рекурсия от некоторое время назад, в результате чего
Вы пишете функцию, которая называет себя.
Это красивая возможность осуществить то,
как рекурсии, потому что считаю это.
>> Это дерево.
И я был немного анальный с тем, как Я положил целые числа на улицу.
Настолько, что она имеет специальный name-- дерево двоичного поиска.
Теперь мы слышали о двоичный поиск, но вы можете
работать в обратном направлении от имени Эта вещь?
Что такое шаблон, как я вставляется целые числа в этом дереве?
Это не произвольная.
Там какая-то картина.
Да.
>> АУДИТОРИЯ: Небольшие те, что слева.
>> DAVID Маланом: Да.
Меньшие из них слева.
Большие из них по праву.
Такой, что истинное утверждение является родитель превышает его левой ребенка,
но меньше, чем его правой ребенка.
И что в одиночку даже рекурсивный словесное определение
потому что вы можете применить, что Та же самая логика для каждого узла
И это только днища вне, базовый вариант, если вам
будет, когда вы нажмете одну из листья, так сказать,
где отпуск не имеет детей дальше.
>> Теперь, как вы могли бы найти номер 44?
Вы бы начать в корне и сказать, хм.
55 не 44 Так что я хочу пойти правильно или я хочу пойти налево?
Ну, очевидно, вы хотите пойти налево.
И так это просто, как телефон Пример книга в бинарного поиска
в целом.
Но мы его реализации Теперь немного более динамично
чем массив может позволить.
И в самом деле, если вы хотите посмотреть на код, на первый взгляд, что.
Похоже, целой кучей линий.
Но это красиво просто.
Если вы хотите реализовать функцию называется поиск, цель которого в жизни
является поиск значения как п, целое число,
и вы прошли в одной pointer-- указатель на узел корней,
скорее, из этого дерева, из которого Вы можете получить доступ все остальное,
обратите внимание, как прямо Вы можете реализовать логику.
Если дерево является пустым, Очевидно, что это не есть.
Давайте просто вернуться ложным.
Не так ли?
Если вы не передать ему ничего, там ничего нет.
>> В противном случае, если п меньше Дерево стрелки N-- теперь стрелка н,
Напомним, мы ввели супер кратко на днях,
и это просто означает, де-ссылку на указатель и посмотреть на месте, называемом н.
Так это значит, пойти туда и посмотреть на поле под названием п.
Так что, если п, значение вы дали, меньше чем значение в целое число деревьев,
где вы хотите пойти?
Налево.
>> Так заметить рекурсию.
Я returning-- не верно.
Не ложь.
Я возвращаюсь независимо ответ от звонка в себя, проходя
п снова, который является избыточным, но то, что немного отличается теперь?
Как я делаю проблему меньше?
Я передаю в качестве второго Аргумент, не корень дерева,
но левая ребенок в этом случае.
Так я передаю в левом ребенка.
>> Между тем, если п больше, чем узел В настоящее время я, глядя на,
Я поиск правую сторону.
В противном случае, если дерево не является нулевым, и если элемент не влево
и это не право, что удивительно дело?
Мы фактически обнаружили узел в Вопрос, а так мы возвращаемся верно.
>> Так мы только поцарапали поверхность Теперь некоторые из этих структур данных.
В проблема установить пять вы будете исследовать эти еще дальше,
и вам будет предоставлена ​​ваш дизайн Выбор, как идти об этом.
То, что я хотел бы завершить на это просто второй тизер 30
о том, что ждет на следующей неделе, и за его пределами.
>> Как мы begin-- счастью вы могли бы think-- наш переход медленно
из мира C и ниже Детали реализации уровня,
в мире, в котором мы можем взять для разумеющимся, что кто-то наконец-
реализованы эти данные сооружения для нас,
и мы начнем понимать, Реальный мир означает реализации
программы веб-основе и сайты в более общем
а также очень безопасности Последствия, которые мы только
начали царапать поверхность.
Вот что нас ждет в ближайшие дни.
>> [ВИДЕОВОСПРОИЗВЕДЕНИЕ]
>> -Он Пришел с сообщением, с протоколом все свое.
Он пришел в мир жесток брандмауэры, незаботливым маршрутизаторы,
и опасности гораздо хуже, чем смерть.
Он быстро.
Он сильный.
Он TCP / IP, и у него есть свой адрес.
«Воины Сети".
[END ВИДЕОВОСПРОИЗВЕДЕНИЕ]
DAVID Маланом: Coming следующей неделе.
Мы будем видеть вас тогда.
[ВИДЕОВОСПРОИЗВЕДЕНИЕ]
-А Теперь, "Глубокие мысли" по Daven Фарнэме.
Дэвид всегда начинается лекции с "Хорошо".
Почему не "Вот решение на этой неделе проблемы набора "
или "Мы даем все вы?"
[Смеется]
[END ВИДЕОВОСПРОИЗВЕДЕНИЕ]