[Музика, яка грає]
>> 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 відеовідтворення]