[За възпроизвеждане на музика]
>> DAVID Malan: Това е CS50.
И това е, както за началото и end-- като literally-- почти до края
на шестата седмица.
>> Мислех, че ще споделите малко един забавен факт.
Аз бях изтеглен тази изправяне от определени данни минало семестър е.
Може би си спомняте, че ние ви молим за всеки р набор форма, ако сте гледали онлайн
или ако сте присъства лично.
И тук са данните.
Така че днес е много по-предсказуема.
Но ние искахме да прекарат малко от време с вас все пак.
Дали някой искал да предположим защо тази графика е толкова съдран, нагоре надолу, нагоре надолу,
така постоянно?
Какво направи всеки един от върховете и улеи представляват?
>> АУДИТОРИЯ: [недоловим]
DAVID Malan: Наистина.
И по-забавно, не дай боже, ние държим една лекция в петък
в началото на семестъра, това е, което виждаме да се случи.
Така че днес, ние участваме в малко повече за структури от данни.
И за да ви дам повече от солидна мисловен модел за проблеми в пет,
който сега е навън.
Правописни грешки, при което ние ще ви предаде текстов файл някои 100,000
плюс английски думи, и ти започваш да имат
за да разбера как да се умело ги заредите в паметта, в RAM, използвайки някои данни
структура по свой избор.
>> Сега една такава структура на данните може да, но най-вероятно не трябва да бъде,
сравнително опростен свързан списък, които ние въведохме за последен път.
И свързан списък е имал най-малко едно предимство над масив.
Какво е едно предимство на свързан списък може би?
>> АУДИТОРИЯ: вмъкване.
>> DAVID Malan: вмъкване.
Какво искаш да кажеш с това?
>> АУДИТОРИЯ: Anywhere заедно списъка [недоловим].
>> DAVID Malan: Добре.
Така че можете да вмъкнете елемент, където искате в средата на списъка
без да се налага да разбъркате всичко, които ние заключихме, в нашия сортиране
дискусии, не е непременно нещо добро,
защото това отнема време да се действително се движат всички тези хора, наляво или надясно.
И така със свързан списък, можете да просто разпределя с изчистване, нов възел,
и след това да актуализирате няколко pointers-- две, три операции max--
и ние сме в състояние да се промуши човек навсякъде в списък.
>> Какво друго е изгодно за свързан списък?
Така ли?
>> АУДИТОРИЯ: [недоловим]
DAVID Malan: Perfect.
Perfect.
Това наистина е много динамичен.
И че не сте извършва, предварително до известна фиксиран размер
парче от паметта, като вие ще трябва да с масив, нагоре от които
е, че могат да отделят възли само на търсенето като по този начин се използват само най-голямо пространство
като действително се нуждаят.
За разлика от масив, може да случайно се разпределят твърде малко.
И след това просто ще да бъде болка в областта на шията
да преразпредели нов голям масив, копирате всичко свърши, освободи стария масив,
и след това се премести за вашия бизнес.
Или по-лошо, може да се отпусне начин повече памет, отколкото сте в действителност се нуждае,
и така вие ще имате много слабо населени масив, така да се каже.
>> Така свързан списък дава тези предимства на динамика и гъвкавост
с инсерции и делеции.
Но със сигурност трябва да има цена, платена.
Всъщност, една от темите проучени викторина нула
е няколко компромисите сме виждали до този момент.
Така че това, което е платена цена или Недостатъкът на свързан списък?
Да.
>> АУДИТОРИЯ: No произволен достъп.
>> DAVID Malan: No произволен достъп.
Но на кого му пука?
Произволен достъп не звучи убедителна.
>> АУДИТОРИЯ: [недоловим]
DAVID Malan: Точно така.
Ако искате да имате определен algorithm--
и нека действително да предложи търсене двоичен по-специално, което
е едно сме използвали доста bit-- ако не разполагате със свободен достъп,
не можеш да направиш, че проста аритметика за намиране като средния елемент
и скача към него.
Вие вместо да започне в първата елемент и линейно търсене отляво
надясно, ако искате да намерите средата или някакъв друг елемент.
>> АУДИТОРИЯ: Вероятно отнема повече памет.
>> DAVID Malan: отнема повече памет.
Къде е тази допълнителна струва, идващи от паметта?
>> АУДИТОРИЯ: [недоловим]
DAVID Malan: Точно така.
В този случай тук, имахме свързан списък за цели числа,
и все пак ние сме удвояване размера на паметта
ние се нуждаем от и съхраняване на тези насоки.
Сега по-малко от една голяма сделка, както Вашите structs получават по-големи
и сте съхранение не е номер, но може би студент или някакъв друг обект.
Но въпросът със сигурност остава.
И така, някои от операциите на свързани списъци бяха наречени
бяха големи O на, N- линейна.
Неща като вмъкване или търсене или заличаване в случай елемент
се случи да бъде в самия край на списъка независимо дали е сортирано или не.
>> Понякога може да получите късмет и в толкова по-ниски граници на тези операции
може също така да бъде постоянно време, ако сте винаги търсим в първия елемент,
например.
Но в крайна сметка, ние обеща за постигане на Светия Граал
на структури от данни, или някои сближаване него,
по пътя на постоянно време.
Можем ли да намерим елементи или добавяне на елементи или премахване на елементи от списък?
Ние ще видим съвсем скоро.
И се оказва, че един на механизмите, ние сме
ще започне да се използва и днес, годишното потребление в р определя пет,
всъщност е доста познато.
Например, ако това е куп на изпита книги, всеки от които
има студент първи име и фамилия на нея,
и аз си ги вземете от в края на изпита,
и всички те са доста много в произволен ред,
и ние искаме да отидем за сортиране тези изпити, така че веднъж степенуват
това е просто много по-лесно и по-бързо, за да ги предаде обратно
за студенти по азбучен ред.
Какви биха били вашите инстинкти за купчина изпити като този?
>> Е, ако сте като мен, може да се види, че това е m,
така че аз отивам да сортирате сложи това под, ако това е моята маса или ми етаж, където
Аз разпространение неща out-- или моя масив really--
I може да се постави цялата на г-жа там.
О.
Ето един A. Така че бих могъл поставя, както е тук.
О.
Ето още един A. Отивам да сложи това тук.
Ето един Z. Тук е друг M. И така I може да започнете да печелите пилоти като този.
И тогава може би щях да отида в по-късно и нещо много nitpicky-Ly сортиране
отделните купчини.
Но въпросът е, аз ще гледам на входа, че аз съм ръка
и бих искал да се направят някои изчислява решение въз основа на този вход.
Ако тя започва с А, я сложи там.
Ако тя започва с Z, поставете го върху там, и всичко между тях.
>> Така че това е техника, която е известен като hashing-- H-A-S-H--
които най-общо означава да се вземат като въвеждане и използване на този вход, за да се изчисли
стойност, като цяло число, и че номер на индекса в съхранение
контейнер, като масив.
Така че с други думи, може да има хеш функция, както аз правя в главата ми,
че ако видя някой е име, което започва с A,
Отивам да се набележат, че до нула в главата ми.
И ако видя някой с Z, аз съм Ще карта, че до 25 в главата ми
и след това пуснати, че в последната най-купчината.
>> Сега, ако мислите, че не мозъкът ми но програмата C, какви номера могат
вие разчитате, за да се постигне същия резултат?
С други думи, ако сте имаше ASCII символи А,
как да се определи какво кофа, за да го сложи в?
Може би не искате да го постави в кофа 65, което
ще бъде като там без основателна причина.
Къде искате да поставите A по отношение на ASCII стойност?
Къде искаш да направя, за да си ASCII стойност да излезе с по-интелигентна кофа
да го поставите в?
>> АУДИТОРИЯ: Minus A.
>> DAVID Malan: Да.
Така минус A или минус специално 65, ако това е
капитал А. Или 98, ако това е с малки букви а.
И така, това ще ни позволи да, много просто и много аритметично,
сложи нещо в кофа подобно.
Така се оказва, че ние всъщност правим това, както добре дори и с викторини.
>> Така че можете да си спомните, че отбележите си Име на преподаване колега на корицата.
И бяха организирани имена на ТФ в тези колони, по азбучен ред,
Е, вярвате или не, когато всички 80 плюс един от нас
Събрахме се онази вечер до степен, последната стъпка в нашия процес на категоризация
е да се разискват на тестовете в голяма пространство на пода на [недоловим]
и да се викторини на всеки от точно по реда на техните ТФ
имена на корицата, защото тогава е много по-лесно за нас
да търсите чрез които се използва линейна търсите или някакъв вид интелигентност
за TF да намери своя или викторини си студентите.
>> Така че тази идея за хеширане че вие ​​ще видите, е
доста мощен всъщност е доста често срещано и много интуитивен,
подобно може би се разделят и владей е в нула седмица.
Аз бързо напред към Hackathon а преди няколко години.
Това беше Zamyla и няколко други студенти поздравителни персонал
тъй като влезе.
И ние имахме един куп сгъване маси там с табелки с имена.
И бяхме организирани поименните маркери с както и над там
и Zs там.
И така, един от TFS много хитро написах това и инструкциите
за деня.
И в 12-та седмица на семестъра това всички направени перфектни смисъл и всеки
знаех какво да правя.
Но винаги, когато съм наредена на опашка в един и същи начин,
вие сте за прилагане на същото понятие на хашиш.
Така че нека да го прави малко по-официално.
Тук е масив.
Той е съставен да бъде малко широк само да изобрази визуално,
че ние може да сложи струни в нещо като това.
И този масив е ясно на площ от 26 общо.
И нещо, което се нарича маса произволно.
Но това е само интерпретация на един художник на това, което може да бъде хеш таблица.
>> Така хеш таблица сега ще да бъде по-висока структура на данните ниво.
В края на деня ние сме на път да се види, че сте
могат да се реализират на хеш таблица, която е много като чек-ин линия
в Hackathon много прилича това маса се използва за сортиране изпита книги.
Но хеш таблица е вид на това високо ниво
концепция, която може да се използва масив под капака, за да го приложи,
или може да се използва списък с дължина, или дори може би някои други структури от данни.
И сега това е theme-- вземането някои от тези основни съставки
като масив и тази сграда блокират сега на списък с дължина
и виждам какво друго можем да изградим на върха на тези, като съставки
в една рецепта, като все повече и повече интересни и полезни крайните резултати.
>> Така че с хеш таблица бихме могли да го приложат
в памет картинки като тази, но как може тя действително да се кодират до?
Е, може би най-просто е това.
Ако капацитет във всички капачки, е просто някои constant-- например 26,
в продължение на 26 букви от alphabet-- Мога да се обадя ми променлива маса,
и мога да твърдя, че аз отивам да сложи Чар звезди там, или низ.
Така че това е толкова просто, колкото това, ако искат да приложат на хеш таблица.
И все пак, това е наистина само един масив.
Но отново, хеш маса сега е това, което ние ще
наричаме абстрактен тип данни, който е просто сортиране на идеен наслояване на върха
на нещо по-банално Сега искал масив.
>> Сега, как да отидем за решаване на проблеми?
Е, по-рано имах лукса да имат достатъчно пространство за таблици тук
така че може да постави викторини навсякъде исках.
Така че, както може да отидете тук.
Zs могат да отидат тук.
Ms може да отидете тук.
И тогава имах някои допълнително пространство.
Но това е малко на измама полето сега, защото тази таблица, ако наистина
мислеше за него като за масив, е просто ще бъде от определен размер.
>> Така че, технически, ако аз извадя до викторина друг студент
и виж, о, този човек име започва с А също
Някак искам да го сложа там.
Но веднага след като съм го сложил там, ако тази таблица наистина представлява масив,
Отивам да се първостепенни или докара пред който викторина този студент е.
Така ли е?
Ако това е масив, само едно нещо, което може да отидете във всяка една от тези клетки или елементи.
И така, аз вид трябва да избирате.
>> Сега по-рано бях вид измамен и е направил това или I
просто вид на чипове ги един над друг.
Но това няма да летят в код.
Е, къде мога да тури втори студент, чието име
е А ако всичко, което трябваше е това свободна маса пространство?
И аз съм използвал три слота и го изглежда има само няколко други.
Какво можете да направите?
АУДИТОРИЯ: [недоловим]
DAVID Malan: Да.
Може би нека просто да го прости.
Така ли е?
Той не се вписва мястото, където искам да го пуснат.
Така че аз отивам да го слагам технически, където B ще отида.
Сега, разбира се, аз съм се започне да си рисува в ъгъла.
Ако стигнем до студент чието име всъщност е B,
Сега B ще се премести малко напред, тъй като може да се случи, да,
ако това е Б, сега той трябва да премине тук.
>> И така, това много бързо може да стане проблематично,
но това е техника, която всъщност се нарича линеен сондиране,
при което просто помисли си масив да бъде по линията.
А вие просто вид на сонда или инспектира всеки наличен елемент
търси достъпно място.
И веднага след като установите, един, можете да го пуснете там.
>> Сега цената се плаща в момента за това решение е, какво?
Ние имаме фиксиран размер масив, и когато поставите имена
в него, поне в началото, какво е времето за работа на вмъкване
за въвеждане на студентите викторини в правилните кофи?
Big O на какво?
>> АУДИТОРИЯ: п.
DAVID Malan: Чух голям О п.
Не е вярно.
Но ние ще дразни освен Затова в един момент.
Какво друго би могло да бъде?
>> АУДИТОРИЯ: [недоловим]
DAVID Malan: И нека го направим визуално.
Така че предполагам това е буквата S.
>> АУДИТОРИЯ: Това е един.
DAVID Malan: Това е един.
Така ли е?
Това е масив, който означава, че има произволен достъп.
И ако ние мислим за това като нула и това като на 25 г.
и ние осъзнаваме, че, О, тук е моят принос S,
Със сигурност мога да конвертирате S, един ASCII характер,
за съответния брой между нула и 25
и след това незабавно го постави там, където принадлежи.
>> Но, разбира се, веднага след като се стигна до втори човек, който е име е А или B или C
в крайна сметка, ако съм използвал линейни сондиране като моето решение,
времето за работа на вмъкване в най-лошия случай
всъщност ще бъде поверено в какво?
И аз съм го чуете тук правилно в началото на деня.
АУДИТОРИЯ: [недоловим]
DAVID Malan: Така че това е п наистина веднъж имате достатъчно голям набор от данни.
Така, от една страна, ако Вашата масив е достатъчно голям
и данните ви е рядка достатъчно, можете получите тази красива константно време.
Но веднага след като започнете все повече и повече елементи,
и само статистически получавате повече хора с буквата
А, както е тяхното име или на писмото Б, тя може потенциално
прехвърлят в нещо по-линейна.
Така че не е съвсем добра.
Така че бихме могли да направим по-добре?
>> Е, каква е нашата решение преди, когато ние
искам да имам повече динамика от нещо като масив позволено?
АУДИТОРИЯ: [недоловим]
DAVID Malan: Какво ще се въведе?
Да.
Така свързан списък.
Е, нека да видим какво са свързани с списък може да направи за нас, вместо да.
Е, нека да предложи, че ние изготвяне на снимката, както следва.
Сега това е различно картина от пример
от различен текст, всъщност, че всъщност, като се използва набор от размер 31.
И този автор просто реши да хеш струни
не се основава на имена на лицето, но въз основа на техните рождени дати.
Независимо от месец, те измислили ако сте родени на първия ден от месец
или 31 на месец, авторът ще сегментиране въз основа на тази стойност,
така че да се разпространи имената на малко повече от 26 точки могат да позволят.
И може би това е малко по-равномерно да обстрелват с буквени писма,
защото, разбира се, там е най-вероятно повече хора в света с имена
които започват с над сигурност някои други букви от азбуката.
Така че може би това е малко по-равномерно, ако приемем,
равномерно разпределение на бебета в целия месец.
>> Но, разбира се, това все още е несъвършена.
Така ли е?
Ние сме като сблъсъци.
Множество хора в тази структура на данните са все още
със същата рождена дата поне ти си независимо от месец.
Но това, което е направил автора?
Е, изглежда, че имаме масив на лявата ръка, изготвен вертикално,
но това е само интерпретация на един художник.
Няма значение какво посока изготвя масив, тя все още е масив.
Какво е това масив от очевидно?
>> АУДИТОРИЯ: свързан списък.
>> DAVID Malan: Да.
Тя изглежда като това е масив на свързан списък.
Така че отново, до този момент на сортиране за използване на тези структури от данни сега
като съставки за по- интересни решения,
вие може напълно да вземе фундаментални, като масив,
и след това да вземе нещо повече интересно като свързан списък
и дори да ги комбинирате в още по-интересна структура на данните.
И наистина, това също би се нарича хеш таблица,
което масива наистина хеш таблицата,
но това хеш таблица има вериги, така да се каже,
че може да расте или намалява на базата на на брой елементи, който искате да вмъкнете.
>> Сега, съответно, какво е времето за работа сега?
Ако искате да поставите някого чийто рожден ден е 31 октомври
къде е той или тя отиде?
Добре.
На самото дъно, където се казва 31.
И това е перфектно.
Това е константно време.
Но какво, ако ние се намери някой друг чийто рожден ден е, нека да видим,
Октомври, ноември 31 декември?
Къде е той или тя ще отиде?
Същото нещо.
Две стъпка все пак.
Това е постоянен, макар и не е тя?
Добре.
В момента тя е.
Но в общия случай, колкото повече хора, които добавяме,
вероятностно, отиваме за да получите повече и повече сблъсъци.
>> Сега това е малко по- по-добре, защото е технически
сега ми вериги могат да бъдат в най-лошия случай колко дълго?
Ако въведете н хора в това по- сложна структура от данни, п хора,
в най-лошия случай това ще бъде п.
Защо?
>> АУДИТОРИЯ: Защото, ако всеки има същия рожден ден,
те ще бъдат един ред.
DAVID Malan: Perfect.
Тя може да е малко измислен, но наистина в най-лошия случай,
ако всеки има същия рожден ден, предвид входящите данни, които имате,
ти започваш да имат масово дълга верига.
И така, бихте могли да го наричаме хеш таблицата, но наистина това е
просто масивна свързан списък с един куп губи пространство.
Но като цяло, ако приемем, че поне рождени дни са uniform--
и то вероятно не е така.
Аз си го измислям.
Но ако приемем, за заради дискусия
че те са, след това на теория, ако това е вертикално представяне
на масива, и след това се надяваме, че сте ще получите вериги, които са, вие знаете,
приблизително същата дължина, където всеки от това представлява ден на месеца.
>> Сега, ако има 31 дни в месеца, това означава, че моята работа време наистина
е голям О п над 31, които чувства по-добре, отколкото линейна.
Но това, което е един от нашите ангажименти за няколко седмици
Преди, когато става дума за изразяване времето за работа на алгоритъм?
Само погледнете само в срока висок ред.
Така ли е?
31 определено е полезно.
Но това все още е голям O п.
Но една от темите на проблема определя пет
ще бъде да се признаем, че абсолютно,
асимптотично, теоретично тази структура данни
не е по-добре, отколкото просто една масивна свързан списък.
И наистина, в най-лошия случай, това хеш таблица може да бъде поверено в това.
>> Но в реалния свят, с нас, хората че собствените Mac-ове или компютри или каквото и
и се изпълняват в реалния свят софтуер за реалния свят на данни,
които алгоритъм смяташ да предпочитате?
Онзи, който взема крайни мерки или която се приема н разделена на 31 стъпки
да намери някаква част от данните, или да търсите някаква информация?
Искам да кажа, абсолютно 31 марките разлика в реалния свят.
Той е 31 пъти по-бързо.
И ние, хората, със сигурност Ще оценявам това.
>> Така се реализира дихотомията има между действително
Говорим за неща теоретично и асимптотично които определено
има стойност, тъй като сме виждали, но в реалния свят,
ако те е грижа за просто вземане на човека щастлив за общи входове,
може много добре да приемам факта, че, да, това е линейна,
но това е 31 пъти по-бързо от линеен може да бъде.
И още по-добре, ние не само трябва да направя нещо произволно като дата на раждане,
бихме могли да прекарат малко повече време и интелигентност
и да мисля за това, което можем да направим, име и може би едно лице
тяхната дата на раждане, за да се съчетаят тези съставки, за да разбера нещо
че наистина е по- уеднаквено и по-малко съдран,
така да се каже, отколкото тази снимка В момента показва, че може да бъде.
Как бихме могли да приложат това код?
Е, нека да предложи, че ние само назаем някои синтаксис ние сме
използва няколко пъти досега.
И аз отивам да се определи една възлова точка, която отново
е общ термин за само някои контейнер за някаква структура данни.
Отивам да предложи низ се случва там.
Но ние отиваме да започнете да приемате тези обучение колелата сега.
>> Не по-CS50 библиотека Наистина, освен ако не искате
да го използва за своя окончателен проект, което е добре,
но сега отиваме да се отдръпни завеса и да кажа, че това е просто знак звезда.
Така че думата там ще бъде името на лицето под въпрос.
И сега имам връзка тук към следващия възел
така че те да представляват всяка от възли
във веригата, потенциално, на свързан списък.
>> И сега как мога да декларирам Самият хеш таблицата?
Как се декларира цялата тази структура?
Е, наистина, много като аз използвах указател само първият елемент от списък
преди, по същия начин мога само да кажа, Трябва ми само един куп от указатели
да приложи цялата тази хеш таблица.
Отивам да имате масив нарича таблица за хеш таблица.
Тя ще бъде на капацитета размер.
Ето как много елементи могат да се поберат в него.
И всеки от тези елементи в тази масив ще бъде звезда възел.
Защо?
Е, на тази картина, това, което съм прилагане на хеш таблицата като
ефективно в началото е просто този масив, който сме изготвен вертикално,
всеки от чиито квадрати представлява показалка.
Ето тези, които имат черти чрез тях са само нищожна.
И тези, които имат стрелки ще правото
са действителни указатели към действителните възли, Ergo началото на свързан списък.
>> Така че тук, след това, е как можем да прилагане на хеш таблица, която
изпълнява отделна верижното.
Сега можем да направим по-добре?
Добре обещах миналия път, че можем да постигнем постоянен време.
И някак си дал константно време тук,
но тогава не каза наистина константно време, тъй като тя все още е
зависи от общата брой елементи
сте въвеждане в структурата на данните.
Но предполагам, че е направил това.
Позволете ми да се върна на екрана тук.
Позволете ми да проектира този тук, ясно на екрана, и предполагам, че е направил това.
Да предположим, че аз исках да въведете името Daven в в моята структура данни.
>> Така че аз искам да вмъкнете низ Daven в структурата на данните.
Какво става, ако не използвате хеш таблица, но аз използвам
нещо, което е по-дървовидна като родословно дърво, където
имате някакъв корен в отгоре и след това възли и листа
които отиват надолу и навън.
Да предположим тогава, че аз искате да вмъкнете Daven на
в това, което е в момента празен списък.
Отивам да направите следното: Аз съм ще създаде възел в това семейство
дървовидна структура от данни, която изглежда малко по този начин, всеки от които
правоъгълници е, да речем, За сега 26 елементи в него.
И всяка една от клетките в този масив се случва
да представлява буквата на азбуката.
>> По-конкретно, аз отивам за лечение Това е, след това, след това С, след което D,
този тук.
Така че това ще е ефективно представлява буквата D.
Но за да поставите всички Daven на име, което трябва да направя малко повече.
Така че аз съм първият ще хашиш, така да се каже.
Отивам да гледам на първата буква в Daven, която очевидно е D,
и аз отивам да се разпределят възел, който изглежда
като this-- голям правоъгълник голям достатъчно, за да се побере цялата азбука.
>> Сега D е направено.
Сега A. D-A-V-E-N е целта.
Така че сега това, което аз ще направя, е това.
Веднага след като започнах известие D че няма показалка там.
Това е стойности за боклук в момента, или за да го инициализира с нула.
Но позволете ми да продължа с тази идея за изграждане на едно дърво.
Позволете ми да отпусне още един от тях възли, които има 26 елементи в него.
>> И знаеш ли какво?
Ако това е само един възел в паметта, която Аз създадох с изчистване, използвайки структура
тъй като ние скоро ще видите, Отивам да направя this--
Отивам да се направи една стрела от нещото, което представена D надолу
към този нов възел.
И сега, на първо място в следващия писмо, в името Daven е,
V-- D-A-V-- Отивам да вървим напред и да изготви друг възел по този начин,
, при която елементите V тук, които ще изготви за instance-- Опа.
Ние няма да се направи там.
Това ще отидете тук.
>> След това ние ще че това е V.
И тогава тук отиваме към индекс надолу от V в това, което ние ще вземем E.
И след това от тук отиваме да отида имате един от тези възли тук.
И сега имам един въпрос да се отговори.
Трябва да се посочи, че по някакъв начин ние сме в края на низа Daven.
Така че аз може просто да го оставите за нищожна.
>> Но какво, ако имаме Daven на пълно име също, което
е, както казахме, Дейвънпорт?
И какво, ако е Daven всъщност е подниз,
префикс на много по-дълъг низ?
Ние не можем просто постоянно казват, нищо не се случва
да отида там, защото можехме никога не поставяйте дума като Davenport
в тази структура на данните
>> И така, какво можем да направим вместо е лечение на всеки един от тези елементи
като може би с два елементи вътре в тях.
Един от тях е указател, наистина, както съм правил.
Така че всяка една от тези кутии Не е само една клетка.
Но какво, ако на върха one-- долния нечии
ще бъде нулев, тъй като не съществува Davenport, просто все още.
Какво става, ако най-отгоре е някаква особена стойност?
И това ще бъде малко Трудно е да го направи този размер.
Но предполагам, че това е просто една отметка.
Проверка.
D-A-V-E-N е низ в тази структура данни.
>> В същото време, ако имах повече пространство тук, можех да направя P-O-R-T,
и аз може да постави отметка в възел който има буквата T в самия край.
Така че това е масова комплекс изглеждащ структура на данните.
И моят почерк със сигурност не помага.
Но ако исках да вмъкнете нещо друго, помислете за това, което ще направя.
Ако искахме да постави Давид, ние ще следваме същата логика, D-A-V,
но сега искам да посоча в следващия елемент не от E, но от I до D.
Така че там ще бъде повече възли в това дърво.
Ние ще имаме разговор изчистване повече.
Но аз не искам да се направи пълна бъркотия на тази снимка.
Така че нека вместо разгледаме един , която е била предварително формулирани
като тази с не DOT, точка, точки, но съкратените масиви.
Но всеки от възлите в това дърво тук
представлява същия thing-- масив Ray с размер 26.
>> Или ако искаме да бъдем наистина правилно сега, това, което
ако някой име като апостроф, нека
Предполагам, че всеки възел всъщност има като 27 индекси в него, а не само 26.
Така че това сега ще бъде на данни структура, наречена trie-- T-R-I-E.
Синтактично дърво, което се предполага, че исторически умен име за дърво
че е оптимизиран за извличане, което, разбира се,
е изписано с I-E, така че е синтактично дърво.
Но това е историята на Trie.
>> Така синтактично дърво е това дърво, като данните структура като родословно дърво
които в крайна сметка се държи по този начин.
И тук е просто още един пример за цял куп имена на други хора.
Но въпросът сега на ръка е това, което трябва
сме спечелили чрез въвеждане безспорно по- сложна структура данни и един,
честно казано, че използва много памет.
>> Защото, въпреки че, в момента, аз съм само
използване D'и показалеца и А и V и Es и Ns,
Аз губя един чесало на много памет.
Но там, където прекарвам един ресурс, Склонен съм да се получат обратно друга.
Така че, ако аз съм харчат повече пространство, това, което е най-вероятно с надеждата?
Че аз съм харчат по-малко какво?
АУДИТОРИЯ: По-малко време.
DAVID Malan: Time.
А защо може да бъде това?
Е, какво е вмъкването време, от гледна точка на големия O сега,
на име като Daven или Дейвънпорт или Давид?
Е, Daven беше пет стъпки.
Дейвънпорт ще бъде девет стъпки, така че би било още няколко стъпки.
Дейвид ще бъде пет стъпки, както добре.
Така че тези, които са бетон номера, но със сигурност има
горна граница на дължина на името на някого.
И наистина, в проблема групи от пет спецификация,
отиваме да предложи че това е нещо,
това е 40-някои по-странни знаци.
>> Реално, никой няма безкрайно дълго име,
което означава, че дължината на Име или дължината на низ бихме могли
има някои състоянието на структура е може би това, което?
Това е постоянна.
Така ли е?
Тя може да бъде една голяма постоянна като 40-нещо, но е постоянна.
И това не е зависимост от това колко други имена са в тази структура на данните.
С други думи, ако Исках да вмъкнете сега
Колтън или Gabriel или Rob или Zamyla или Алисън или Белинда или всякакви други имена
от персонала в тези данни структура, е времето за изпълнение
на вмъкване други имена щеше да бъде изобщо повлияха
от колко други елементи са в структурата на данните вече?
Това не е така.
Така ли е?
Защото ние сме ефективно използване на тази многопластова хеш таблица.
И времето за работа на всяка от тези операции
не зависи от броя на елементи, които са в структурата на данните
или че в крайна сметка ще да бъде в структурата на данните,
но дължината на какво конкретно?
>> Поредицата е Добавя, което наистина прави
това асимптотично постоянно time-- голям O на една.
И честно казано, само в реалния свят, това
означава вмъкване на име Daven на заема като пет стъпки, или Davenport девет
стъпки, или David пет стъпки.
Това е дяволски много малки експлоатационни пъти.
И наистина, това е много нещо добро, особено когато
не е зависима от общото брой на елементите в там.
И така, как бихме могли да приложат тази вид структура на код?
Това е малко по- сложна, но все пак това е
просто прилагане на основните градивни блокове.
Отивам да се предефинират ни възел, както следва:
булев нарича word-- и това може да се нарече нещо.
Но BOOL представлява това, което привлече като отметка.
Да.
Това е края на низ в тази структура данни.
>> И, разбира се, звездата на възела там се отнася за деца.
И наистина, точно като родословно дърво, можете
ще разгледа възлите които се виси
на дъното на някои майка елемент за деца.
И така децата ще е масив от 27, на 27-ми този
просто е за апостроф.
Отиваме да сортирате на специален случай това.
Така че може да има някои имена с апострофи.
Може би дори тире трябва отида там, но ще
виж в стр комплект 5 ние само грижи за букви и апострофи.
>> И тогава как ще представляват самата структура на данни?
Как сте представител на корена на този Trie, така да се каже?
Е, точно като с свързан списък, трябва указател към първия елемент.
С Trie трябва само един указател към корена на тази синтактично дърво.
И от там можете да хеш пътя си надолу по-дълбоко и по-дълбоко
на всеки друг възел в структурата.
Така че просто с тази кутия ние представляваме, че структура.
>> Сега Meanwhile-- О, въпрос.
>> АУДИТОРИЯ: Какво е булев дума?
>> DAVID Malan: BOOL дума просто това C въплъщение
от това, което е описано по- в тази кутия тук, когато
Започнах разделяне всяка от елементи в две парчета масива.
Един от тях е указател към следващия възел.
Другият трябва да бъде нещо като отметка
да се каже, да, има Думата Daven че свършва тук,
защото ние не искаме, в момента, Дейв.
>> Въпреки че Дейв ще бъде легитимна дума, той не е в Trie
още.
И D не е дума.
И D-A не е дума или име.
Така отметката показва само веднъж
удари този възел е предишния път на героите
всъщност е низ, който сте вмъкнали.
Така че това е всичко, на булев там се прави за нас.
>> Всякакви други въпроси, свързани с опита?
Да.
>> АУДИТОРИЯ: Какво е припокриването?
Какво става, ако имате Dave и Daven?
DAVID Malan: Perfect.
Какво става, ако имате Dave и Daven?
Така че, ако ние вмъкнете, да кажем, псевдоним, за David-- Dave-- D-A-V-E?
Това всъщност е супер проста.
Така че ние само ще отнеме четири стъпки.
D-A-V-E. И какво трябва да се направи веднъж ударих, че четвъртият възел?
Просто щеше да се провери.
Ние вече сте добре да тръгвам.
Готово.
Четири стъпки.
Constant време асимптотично.
И сега ние сме посочили, че и двете Dave и Daven са струни в структурата.
Така че не е проблем.
И забележете как присъствието на Daven не го направи
приемайте повече време или по-малко време за Дейв и обратно.
>> И така, какво друго можем да направим сега?
Ние сме използвали тази метафора преди на корита, представляваща нещо.
Но се оказва, че купчина тави е всъщност
демонстративна на друга абстрактна данни type-- по-висока структура на данните ниво
че в края на деня е просто като масив или свързан списък
или нещо по-банално.
Но това е по-интересно концептуална идея.
A стак, като тези тави тук в Mather,
обикновено се нарича просто that-- комин.
>> И в този тип структура на данните имате две operations--
имате една, наречена тласък за добави нещо към стека,
като да сложиш друга тава обратно на върха на стека.
И тогава се появи, което означава, вземе най-горната тава излитане.
Но това, което е ключово за комин е, че тя има тази любопитна характеристика.
Както персонал столова са пренареждане на тавите за следващото хранене,
какво ще бъде вярно за това как студентите
взаимодействат с тази структура данни?
АУДИТОРИЯ: Те ще се появи еднократно.
DAVID Malan: Те ще поп еднократно, надявам се на върха.
В противен случай това е просто вид на глупав да отидем по целия път до дъното.
Така ли е?
Структурата на данните наистина не позволи можете да вземете долната тава най-малко
лесно.
Така че този любопитен имот на комин
че последният елемент в е ще бъде първият Един.
И компютърни учени наричат това LIFO-- продължи, първа изходяща.
И това всъщност няма интересни приложения.
Това не е задължително, както е очевидно, тъй като някои други, но може наистина да бъдат полезни,
и действително може да се прилага по няколко различни начина.
>> Така един, и всъщност, нека Не ме да се потопите в това.
Нека да направим това вместо това.
Нека разгледаме един, който е почти същата идея, но тя е малко по-справедливо.
Така ли е?
Ако вие сте един от тези фен момчета или момичета, които наистина се интересува от Apple продукти
и се събудих в 3:00 AM да се подредят в някакъв магазин
за да получите най-новите iPhone, можете може да са наредени на опашка по този начин.
>> Сега на опашката е много съзнателно име.
Това е линия, защото там е някаква справедливост към него.
Така ли е?
Би вид смуче, ако сте беше първа в Apple Store
но на практика са най-долен тава, защото служителите на Apple след това
поп последният човек, който всъщност имам в линия.
Така стекове и опашки, въпреки че функционално те са вид на same--
това е само тази колекция на ресурсите, което е
ще расте и shrink-- има тази справедливост аспект към него,
най-малко в реалния свят, където операциите тренирате
са коренно различни.
A stack-- опашка rather-- се казва, че има
две операции: N опашка и г опашката.
Или можете да ги наречем произволен брой неща.
Но вие просто искате да заснемете идеята, че едно е добавянето
и един в крайна сметка се извади.
>> Сега под предния капак, както топчето и опашката могат да бъдат приложени по какъв начин?
Ние няма да отида в кода на Дали защото на по-високо ниво
Идеята е нещо по-очевидна.
Искам да кажа, какво правят хората?
Ако аз съм първият човек в Apple Съхранявайте и това е входната врата,
знаете ли, аз отивам да стоя тук.
И на следващия човек Ще стоя тук.
Така че това, което структурата на данните се поддава на опашка?
>> Аудитория: A опашка.
DAVID Malan: Е, на опашката.
Разбира се.
Какво друго?
>> Аудитория: A свързан списък.
>> DAVID Malan: A свързан Списъкът, който може да се приложи.
И свързан списък е хубаво, защото след това че може да расте произволно дълго в сравнение
да има някакъв определен брой на хората в магазина.
Но може би на фиксиран номер на места е законно.
Защото, ако те имат само около 20 Iphones на първия ден, може би
те само трябва масив на площ 20 да декларирате, че опашката, която
само да кажа, сега, след като ние започнем да говорим за тези по-високи нива на проблеми,
можете да го приложат в произволен брой начини.
И там е най-вероятно просто ще да бъде компромис в пространството и времето
или само в собствения си код сложност.
>> Какво ще кажете за комин?
Е, една купчина, която сме виждали твърде може да бъде само тези тави.
И вие може да приложи този масив.
Но в един момент, ако използвате масив, какво ще се случи с тавите
се опитвате да остави?
Добре.
Вие само ще да бъде в състояние да отиде толкова високо.
И аз мисля, че в Mather те са всъщност издълбана в този отвор.
Така че, наистина, това е почти като Mather използва
масив от фиксиран размер, защото само вие можете да
поберат толкова много тави в тази пролука в стената долу коленете на хората.
И така, това може да бъде казва, че е масив,
но ние със сигурност може да го прилагат по-общо свързан списък.
>> Е, какво да кажем за друга структура данни?
Позволете ми да спра един друг визуален тук.
Нещо като как за този тук?
Защо би могло да бъде полезно да не са нещо като фантазия като синтактично дърво, което
видяхме имаше тези много широки възли, всеки от които е в масив?
Но какво, ако можем да направим нещо по- просто, като старата школа родословно дърво,
всеки един от които възли тук е просто съхраняване на брой.
Вместо име или потомък е просто съхраняване на брой като този.
>> Е, на жаргон ние използваме в структури от данни е двата опита
и дървета, където Trie отново е само един, чиито възли са масиви,
все още е това, което може използвате от началното училище
когато сте направили семейство tree-- листата и корена
на дървото и деца на майка и братя и сестри от тях.
И ние може да изпълни едно дърво, например, като просто като това.
Дърво, ако като възел, един от тези кръгове, че има няколко,
това няма да има една показалка, но две.
И веднага след като добавите втори указател, можете
всъщност сега може да се направи нещо на двумерен данни
структури в паметта.
Много прилича двуизмерен масив, можете да
има вид на двумерен свързани списъци, но такива
които следват един модел където няма цикли.
Това е наистина едно дърво с един дядо път до тук и след това
някои родители и деца и внуци и правнуци.
и така нататък.
>> Но това, което е наистина хубаво за това също, само за да ви дразни с малко код,
изземване рекурсия от известно време назад, при което
пишете функция, която нарича себе си.
Това е една красива възможност да приложи нещо
като рекурсия, тъй като смятат, че това.
>> Това е дърво.
И аз съм бил малко анален с колко Сложих числа на улицата.
Толкова много, така, че да има специална name-- двоично търсене дърво.
Сега сме чували за двоичен търсите, но може да ви
работят назад от името на това нещо е?
Какъв е модела на това как Създава числа в това дърво?
Това не е произволно.
Има някои модел.
Да.
>> АУДИТОРИЯ: по-малки от ляво.
>> DAVID Malan: Да.
По-малките от тях са от ляво.
По-големите от тях са в дясно.
Такава, че вярно твърдение е майка е по-голяма от лявата му дете,
но по-малко от правото си дете.
И че само е дори рекурсивни словесно определение
защото можете да приложите, че същата логика на всеки възел
и то само дъна от базова случай, ако
ще, когато ви удари един от листата, така да се каже,
където отпуск е без деца по-нататък.
>> Сега как може да намерите броя 44?
Можете да започнете от корените и да кажа, хм.
55 не е 44, Така че искам да отида право или искам да тръгнете наляво?
Е, очевидно искате да отидете наляво.
И така, това е точно като на телефона Например книга в двоично търсене
по-общо.
Но ние сме го прилагане сега е малко по-динамично
от масив може да позволи.
И всъщност, ако искате да изглеждате в кода, на пръв поглед сигурно.
Прилича на куп линии.
Но това е изключително лесно.
Ако искате да се приложи функция нарича търсене, чиято цел в живота
е да се търси за стойност като п е цяло число,
и сте преминали през един pointer-- указател към възел на корените,
по-скоро на това дърво, от които можете да получите достъп до всичко останало,
забележите как прямо можете да реализирате логиката.
Ако дървото е нула, очевидно той не е там.
Нека просто да се върне фалшиви.
Така ли е?
Ако го предаде нищо, там няма нищо.
>> Иначе, ако п е по-малко от дърво стрелка, N- сега стрелка п,
спомням ние въведохме супер накратко на другия ден,
и това просто означава, де-позоваването на показалеца и погледнете в областта, наречена п.
Така че това означава, че там и погледнем в областта, наречена п.
Така че, ако п, стойността ти даде, е по-малко от стойността на числото дървета,
Къде искате да отидете?
Вляво.
>> Така че забележите рекурсията.
Аз съм returning-- не е вярно.
Не е лъжа.
Аз съм връщане, независимо от отговора е от разговор с мен, минавайки
п отново, което е излишно, но това, което е малко по-различно сега?
Как ми прави проблема по-малък?
Аз съм преминаване в като втори аргумент, а не на основата на дървото,
но лявата детето в този случай.
Така че аз съм преминаване в лявата детето.
>> Междувременно, ако п е по-голям от възела, Аз съм в момента гледа,
Търся отдясно.
Иначе, ако дървото не е нула, и ако елементът не е вляво
и това не е надясно, това, което е чудесно за случая?
Ние сме всъщност намерих възел в въпрос, и затова се върнете вярно.
>> Така че ние току-що се почеса по повърхността сега някои от тези структури от данни.
При проблем определя пет вие ще проучи тези още по-нататък,
и вие ще се дава своя дизайн избор за това как да отида за това.
Онова, което бих искал да се направи заключение за е само 30 секунди закачка
от това, което очаква през следващата седмица и след това.
>> Както begin-- щастие ви мощ think-- нашия преход бавно
от света на C и по-ниска подробности по изпълнението ниво,
в един свят, в който можем да вземем за даденост, че някой друг е най-накрая
изпълнява тези данни структури за нас,
и ние ще започнем да се разбере реалния свят, означава на изпълнителните
уеб-базирани програми и уебсайтове, по-общо
и също така много сигурността последици, които сме само
започнал да надраскат повърхността на.
Ето какво ни очаква в идните дни.
>> [Възпроизвеждане на видео]
>> -Той Излезе със съобщение, с протокол всичко сам.
Той дойде в един свят на жестока защитни стени, незаинтересовани рутери,
и опасностите далеч по-лоши от смъртта.
Той е бърз.
Той е силен.
Той е TCP / IP, и той има си адрес.
"Войни на мрежата."
[END възпроизвеждане на видео]
DAVID Malan: Очаквайте следващата седмица.
Ние ще ви видя тогава.
[Възпроизвеждане на видео]
-И Сега, "Дълбоки мисли" от Daven Farnham.
-David Винаги започва лекции с: "Добре."
Защо не, "Тук е решението за тази седмица проблем комплект "
или "Ние даваме на всички вас, А?"
[Сайта]
[END възпроизвеждане на видео]