СПЕАКЕР 1: Добро, тако да је ово ЦС50 Ово је крај недеље пет. И сећам се тог када смо последњи пут почео гледајући одгајивача података структуре који су почели да се реши Проблеми, који су почели да се уведе нови проблеми, али је кључ за ово је врста тхреадинг да почео да радим од чвора до чвора. Дакле, ово је наравно појединачно повезана листа. И по појединачно повезани, Мислим постоји само један нит између сваке од тих чворова. Испоставило се да можете да урадите одгајивач ствари као двоструко повезана листа где имате стрелицу иде у оба правца, који може да помогне са одређеним ефикасности. Али ово решио проблем? Који проблем се то ријешити? Зашто нам је стало у понедељак? Зашто, у теорији, да ли нам је стало у понедељак? Шта он ради? 

ПУБЛИКА: Ми динамички да га променити величину. 

СПЕАКЕР 1: Ок, тако да можемо динамички га величину. Велл доне обоје. Дакле, можете динамички величину ово структура података, док низу, опозив, морате знати да априори колико простора желите и ако је потребно мало више простор, мало си среће. Морате да направите потпуно нову низ. Треба да се померите све своје подаци из једне у другу, на крају ослободи старог низ ако можете, а затим наставите. Што се осећа веома скупо и врло неефикасан, и заиста може бити. Али то није све добро. Ми платити цену, што је био један од више очигледних ценама смо платите помоћу повезану листу? 

ПУБЛИКА: Морамо да користимо двоструко простор за сваког од њих. СПЕАКЕР 1: Да, тако треба најмање два пута толико простора. У ствари, схватио сам ово слика је чак и мало доводи у заблуду, јер на ЦС50 ИДЕ у много модерног компјутери, показивач или адреса није у ствари четири бајта. То је веома често ово дана осам бајтова, што значи дно највише правоугаоника тамо у стварности су врста дупло велика као што сам извући, што значи да користите три пута као много простора као што можда има другачије. Сада истовремено, ми смо још увек говоримо бајтова, зар не? Ми не нужно говоримо мегабајта или гигабајта, осим ако овим подацима структура велика. 

И тако смо данас почети да размотримо како бисмо могли да истражују податке ефикасније ако се у Чињеница подаци добија већи. Али хајде да покушамо да цаноницализе Прве операције да можете учинити на њима врсте структура података. Дакле, нешто као повезана Листа генерално подржава операције воле делете, убаците и претрагу. А шта хоћу да кажем? То само значи да обично, ако људи користе повезану листу, они или неко други је имплементирао функције као што су брисање, инсерт, и претрага, тако да можете стварно уради нешто корисни са структуром података. Дакле, хајде да кратак поглед колико смо могли имплементирати неки код за повезане листе као што следи. 

Дакле, ово је само неки Ц код, ни комплетан програм да сам заиста брзо подизали. То није онлине у дистрибуцији код, јер неће заправо ради. Али приметио сам сам са коментар рекао, Дот Дот Дот, има нешто тамо, Дот Дот Дот, постоји нешто. И хајде да погледамо шта сочно делови. Дакле, на линији три, сећам се да је ово сада предложили смо проглашењу чвор последњи време, једна од тих правоугаоних објеката. Има инт да ћемо звати Н, али можемо га назвати било шта, а затим звезда струцт чвор се зове следећи. И само да буде јасно, да друга линија, он лине шест, шта је то? Шта ради за нас? Зато што свакако изгледа више Цриптиц од наших уобичајених варијабли. 

ПУБЛИКА: То чини помери један. 

СПЕАКЕР 1: То чини помери један. И да будем прецизнији, она ће их сачувати адресу од чвора који је требало да буде семантички поред њега, зар не? Тако да неће нужно кретање ништа. Само ће складиштити вредност, која је ће бити адреса неке друге чвора, и зато што смо рекли, струцт чвор звезда, звезда означава показивач или адреса. У реду, тако да сада ако претпоставимо да имамо ово Н доступни нама, и идемо претпоставимо да неко други има убаци гомилу природних бројева у повезане листе. И то повезано листа указује неком тренутку променљива се зове листа која је донет овде као параметар, Како да идем о линији 14 спровођење претрагу? Другим речима, ако сам имплементацији Функција чија је сврха у животу је да се инт а затим и почетак повезане листе, то је показивач на повезане листе. Као прво, за кога мислим Давид је био наш волонтер у понедељак, Он је показујући на цео линкед лист, то је као да смо у пролазу Давид у као наш аргумент овде. Како идемо о прелажење ову листу? Па, испоставља се да, иако показивачи су релативно нови сад за нас, можемо да урадимо ово релативно искрено. 

Ја идем напред и прогласити привремено променљиву која Конвенцијом се тек тако да се зове показивач, или ПТР, али можете да га звати како год хоћеш. И ја ћу да се покрене је на почетак листе. Дакле, можете некако мисле о томе како ми је наставник неки дан, врста показујући на некога међу нашим људима као волонтери. Дакле, ја сам привремену променљиву која је само указује на исту ствар да је наш случајно назван волонтер Дејвид је такође истакао. Сада док показивач НОТ НУЛЛ, јер опозив да је ништаван неки посебан Сентинел вредност разграничава крај листе, док сам не показујући на земљу као нашег последњег волонтера је, идемо напријед и урадите следеће. Ако поинтер-- и сад сам хтео да радимо оно што смо урадили са студентом струцтуре-- ако показивач тачка следећу екуалс-- а, ако показивач тачка Н, једнако једнак је променљива Н, Аргумент да је донет у, онда желим да наставим и кажу ретурн труе. Нашао сам број н Инсиде оф један од чворова мог повезане листе. Али тачка не ради у овом контексту, јер показивач, ПТР је заиста показивач, адреса, заиста можемо предивно користити на крају комад синтаксе та врста марки интуитиван осећај и заправо користити овде стрелу, што значи иде од та адреса на цео број тамо у. Дакле, то је врло слично у дух оператеру дот, већ зато што показивач није показивач а не сама стварна струцт, ми само користимо стрелицу. 

Дакле, ако је тренутна чвор да сам ја, привремена променљива, указујем на се не Н, оно што желим да урадим? Па, са својим људским добровољцима да смо овде имали неки дан, ако је мој први човек није онај који сам Желим, и можда други људски није онај желим, а трећи, ја треба да физички кретати. Као како сам корак кроз листу? Када смо имали низ вас, Управо сам као да сам плус плус. Али у овом случају, довољно је урадите показивач, гетс, показивач, следећи. Другим речима, следећи поље је као и сви са леве стране руке да су наши људски волонтери у понедељак су користили да укаже на неки други чвор. То су били њихови суседи нект. 

Дакле, ако желим да корак кроз овај списак, Не могу само ја радим плус плус више, Ја уместо да кажем Ја, показивач, иде на једнаку год следећи поље је, следећи поље, следећи поље је, након свих оних који су остали руке да смо имали на сцени указивањем неким каснијим вредностима. И ако се кроз да цела итерација, и на крају, ја нула ударио немају фоунд Н ипак, само сам ретурн фалсе. Дакле, опет, све што радимо овде, по слици малопре, почиње од показујући на почетак листе вероватно. А онда сам провјерити, је вредност Ја сам у потрази за једнак девет? Ако је тако, ја се врате истина и ја сам готов. Ако не, ја ажурирати руку, ТХЕ показивач, да укаже на локацији наредног стрелице, и онда локацији следећег стрела, и следећи. Једноставно ходам кроз овај низ. 

Па опет, кога брига? Као што је то састојак за? Па, сећам се да смо увели појам стеку, који је апстрактна подаци тип утолико што је не, Ц ствар, то није ствар ЦС50, то је апстрактна идеја, ова идеја слагање ствари на један на други које се могу имплементирати у гомиле различитих начина. И један начин смо предложили је био са низ, или повезане листе. И испоставило се да је канонски, а стек подржава најмање две операције. И бузз речи су гурнути, да пусх нешто на стек, као нови фиоке у трпезарија, или поп, што значи да уклоните највиши траи из стека у ручавање хала, а онда можда неки остале операције као добро. Па како бисмо могли дефинисати структуру да се сада зову гомилу? 

Па, имамо све потребне синтакса на располагању у Ц. кажем, дај ми дефиницију типа струцт унутар стеку, Ја ћу рећи је низ, олуја са гомила бројева, а онда величина. Другим речима, ако желим да спроведе ово у коду, пусти ме и некако драв чему се говори. Дакле, ово је говорећи ми дајте структура која има низ, а ја не знам шта је капацитет, је очигледно нека константа која имам дефинисан на другом месту, и то је у реду. Али, претпоставимо да је само један, два, три, четири, пет. Дакле, капацитет је 5. Овај елемент у мом Структура ће се звати бројеве. А онда ми је потребан друга променљива очигледно назива величине која је првобитно идем да прописују се иницијализује на нулу. Ако нема ништа у стацк, величина је нула, и то је вредности за смеће у бројкама. Немам појма шта је унутра још. 

Дакле, ако желим да гура нешто на стек, Претпостављам да позовем функцију пусх, и Кажем гурати 50, као и број 50, где би ви предлажете Ја га нацртати у овом низу? Постоји пет различитих могућих одговора. Где желиш да се број 50? Ако је циљ овде, опет, позовите Функција Пусх, пролазе у аргумента од 50, где сам га ставио? Пет поссибле-- 20% Могуће да нагађамо исправно. Да? 

ПУБЛИКА: Далеко у праву. 

СПЕАКЕР 1: Далеко у праву. Сада постоји 25% шансе да нагађамо исправно. Дакле, то би заправо бити у реду. По конвенцији, рећи ћу с низом, ми бисмо обично почети са леве стране, али смо свакако могли почиње на десној страни. Дакле, спојлер овде ће бити сам Вероватно ће то извући са леве стране, баш као у нормалном низу где Ја кренути с лева на десно. Али ако се окрене аритметичка, у реду. То једноставно није конвенционално. У реду, морам да направим један више промена ипак. Сада када сам гурнуо нешто на стек, шта је следеће? 

У реду, морам да повећате величину. Па нека ми само напред и само упдате то, што је нула. И уместо сада, идем ставити у вредности једног. И сада Претпостављам да гурнути још број на стек, као и 51. Па, морам да један измена која се до велицине два. И онда претпостављам да гурнути још један број на стек као 61, Сада морам да ажурирају величину још један време, и да вредност 3 као величине. И сада Претпостављам да позовем поп. Сада поп, по обичају, не узима аргумент. Са стеку, цела тачка метафоре траи да немате дискрецију да одем послужавник, све можете да урадите се поп на највишем један од стек, само зато. То је оно што ова структура података ради. 

Дакле, до тој логици ако кажу, поп, оно што долази са? Тако 61. Дакле, оно што је заиста рачунар урадити у меморији? Шта мој број треба да урадим? Шта би ви предлажете мењамо на екрану? Шта треба променити? Молим? Тако се ослободимо 61. Тако да дефинитивно могу то да урадим. И могу отарасити 61. И онда шта друго промене треба да се деси? Величина вероватно има да се вратим на два. И то је у реду. Али чекај мало, величину Малопре је три. Хајде да урадимо брзо проверу исправности. Како знамо да смо зелео да се ослободи од 61? Зато што смо искакање. И тако ја имам ову другу величину имовине. 

Чекај мало, ја сам мислећи назад на недељу две када смо почели да причају о низови, где је ово локација нула, ово је једна локација, то је локација Два, ово је локација три, четири, Изгледа да је однос између величине и елемент који сам желите да уклоните из низа изгледа да само бити шта? Величина минус један. И то је начин као људи знамо 61 на првом месту. Како рачунар ће знати? Када је ваш код, где сте вјероватно желите да урадите величина минус један, Дакле, три минус један су два, а то значи желимо да се ослободимо 61. И онда заиста можете ажурирати величина, тако да сада величине иде од три до само два. И само да буде педантан, идем предложити да сам урадио, зар не? Ви предложили интуитивно исправно би требало да се отарасим 61. Али нису некако некако се отарасили 61? Ја сам заборавио ефикасно да је заиста тамо. И мислим назад у ПСЕТ4, ако сте прочитали чланак о форензика, ПДФ да смо имали ви прочитали, или ти ће прочитати ове недеље ПСЕТ4. Подсетимо се да је ово заправо Германе да цела идеја компјутерске форензике. Какав компјутер углавном ради је то је само заборавља где је нешто, али не иде у и слично покушајте да га огребе од или прекидач те бита са нуле и јединице или неког другог насумичним осим ако вас се уради намерно. Дакле, твоја интуиција је Добро, хајде да се отараси 61. Али у стварности, не морамо да бринемо. Ми само треба да заборавимо да тамо је променом наше величине. 

Сада постоји проблем са овим стацк. Ако стално гура ствари на стек, шта је Очигледно ће се догодити у само неколико тренутака време? Ми ћемо остати без простора. А шта ми радимо? Некако смо најебали. Ова имплементација не дозволи нас величину низа, јер користећи ово синтакса, ако вас сетите се у недељу две, Једном сте прогласили величина низа, нисмо видели механизам још гдје можете да промените величину низа. И заиста, Ц нема ту функцију. Ако кажете гиве ме фиве НЛХС их позивате бројеве, То је све што ћеш да га добити. Тако да ћемо сада да радимо од понедељка, има способност да изрази решење ипак, само треба да подесите дефиниција нашег стацк да не буде неки хард-цодед низ, али само за похрану адресу. 

Зашто је ово? Сада само морамо да будемо задовољни чињеница да када мој програм ради, Ја вероватно идем у морам да питам људске, колико бројева желиш да сачувате? Дакле, улаз мора да дође однекуд. Али када знам да број, онда ја могу само користе оно што функционише дати ми комад меморије? Могу да користим маллоц. И могу да кажем било који број бајтова сам се за ове НТХС желе. И све што имам да сачувате у бројевима променљива овде унутар ове струцт треба да буде шта? Шта се заправо улази у бројеви у том сценарију? Да, показивач на прву бајт тог комад сећања, или, прецизније, адреса првог тих бајтова. Није битно да ли је то један бите или милијарду бајтова, Само треба да се брине о првом месту. Јер оно што маллоц гаранције и моје гаранције оперативног система, је да је комад меморије И да, то ће бити суседни. Неће бити празнине. Дакле, ако сам тражио 50 бајтова или 1000 бајтова, сви ћемо бити бацк то бацк то бацк. И тако док се сећам колико је велик, како много сам тражио, све што треба да знам је први такав адреса. 

Тако да сада имамо могућност у коду. Додусе, то ће нас одвести више времена да пишем ово, сада могли преусмјерити тај меморију само чување другу адресу тамо ако желимо већи или чак мањи комад меморије. Дакле, овде на компромис. Сада долазимо динамику. Имамо још цонтигуоуснесс тврдим. Због маллоц ће нам дати суседни комад меморије. Али ово ће бити бол у врат за нас, програмер, да заправо кодира горе. То је само још посла. Морамо код сличан ономе што сам био изда малопре. Врло изводљиво, али додаје комплексност. И тако време програмер, програмер Сада је још један ресурс да бисмо могли да проведемо треба неко време да се нове функције. И наравно да постоји ред. Нећемо ићи у ово један у много детаља. Али то је врло слично у духу. Могао бих провести ред, и своје одговарајуће операције, енкуеуе или декуеуе, као што додати или уклонити, то је само одгајивач начин да се то каже, енкуеуе или декуеуе, као што следи. Ја само могу себи дати градитеља, то опет има низ један број је, то опет има величину, али зашто ми сада треба да пратите предњем делу реда? Нисам морам да знам предњи део мог стека. Па, ако сам опет за куеуе-- хајде да тешко законика, као што као пет целих бројева у ту потенцијално. Дакле, ово је нула, један, два, три, четири. Ово ће бити Опет нас је звала бројеви. И то ће бити позван величина. 

Зашто је то није довољно да само величину? Па, хајде да гурају те исте бројеве на. Тако сам ја пусхед-- енкуеуед, или гурнуо. Сада ћу енкуеуе 50, а затим 51, а затим 61, и Дот Дот Дот. Дакле, то је енкуеуе. Ја енкуеуед 50, а потом 51, затим 61. И то изгледа идентично на стек до сада, осим требам да једну промену. Морам да ажурира ове величине, тако да идем од нуле до један до два до три. Како да декуеуе? Шта се дешава са декуеуе? Ко би требало да дође са ове листе први ако је линија на Аппле Сторе? Тако 50. Тако некако је компликованије овај пут. Док последњи пут је то било супер лако само ради величина минус један, Ја се до краја мог низа ефикасно где су бројеви, отклања 61. Али ја не желим да уклоните 61. Желим да се 50, који Био сам тамо у 5:00 да се построје за нови иПхоне или шта све не. И тако да се ослободи од 50, ја Не мозес да радис ово, зар не? Ја могу прецртати 50. Али ми смо управо рекли не мора да буде тако анални како би се огребе од или сакријете податке. Можемо заборавити одакле је. 

Али ако променим величину сада два, је ли ово довољно информација да знају шта се дешава у мом реду? Не баш. Као мој број је два, али одакле је ред почне, поготово ако још увек имам ти исти бројеви у меморији. 50, 51, 61. Зато морам да се сетим Сада где је фронт. И тако сам предложио горе ту, ми ћемо управо назвао Нтх напред, чија је почетна вредност треба да буде шта? Нула, само почетак листе. Али сада Поред децрементинг величина, управо смо повећајте фронт. Сада овде је још један проблем. Тако сам једном наставимо. Претпоставимо да је ово број попут 121, 124, и онда, дођавола, Ја сам из свемира. Али чекај мало, ја нисам. Дакле, у овом тренутку у причи, Претпостављам да је величина је један, два, три, четири, па претпостављам да је величина је четири, предњи је један, тако да 51 је спреда. Желим да ставим други број овде, али, дођавола, ја сам из свемира. Али ја нисам стварно, зар не? Где би Ставио сам неке додатна вредност, као и 171? Да, могао некако вратимо тамо, зар не? А онда пређу кроз 50 или само препиши са 171. А ако се питате зашто наш број је толико случајна, они су обично узимају рачунар наука курсеви на Харварду после ЦС50. Али то је била добра оптимизација, јер сада не губим простор. Још увек имам да се сетим колико ова ствар је тотално. То је пет укупно. Зато што не желим да старт преписивање 51. Дакле, сада сам још увек ван простора, тако да исти проблем као и пре. Али можете да видите како сад у коду, вероватно треба да мало више писати комплексност да се то догоди. И, у ствари, оно што оператер у Ц вероватно летс ви магично урадите ово циркуларност? Да оператор модулу, проценат знак. Дакле, шта је кул о реду, иако смо стално цртање низова јер ови попут правих линија, ти ако врста мисли о овоме као кривљења око као круг, онда само интуитивно је врста радова ментално Мислим да је мало чисто. Ви би и даље морати да спроведе да ментални модел у коду. Дакле, то није тешко, на крају, да спроведе, али ми и даље изгубити сизе-- радије, Способност да промените величину, осим ако то урадимо. 

Морамо да се ослободимо низа ми замените га са једним показивачем, а онда негде у мом коду имам на позив шта функционише да стварно створе Низ бираних бројева? Маллоц, или неки сличан функција, тачно. Сва питања на гомиле или редовима. Да? Добро питање. Шта модулу би ви користите овде. Дакле генерално, када се користи Мод, ти би то урадио са величином Цела структура података. Дакле, нешто као пет или капацитета, ако то је константа, је вероватно укључен. Али само ради по модулу пет Вероватно није довољно, јер морамо да знамо и ми врап овде или овде или овде. Дакле, ви сте вероватно такође желети да укључи величина ствари, или предњи променљива као добро. Дакле, то је само ово релативно Једноставна математика израз, али по модулу ће бити кључни састојак. 

Дакле, кратки филм, ако хоћете. Анимација да неки људи на другом универзитету саставио које смо прилагођени за ову расправу. То укључује Џек учење Чињенице о редовима и статистика. 

Филм: Једном давно, је био неки тип по имену Џек. Када је дошао у дружењу, Џек није имао таленат. Дакле, Џек отишао да разговара до најпопуларнији лик је знао. Он је отишао у Лоу и питао, шта да радим? Лу је видео да је његов пријатељ је стварно узнемирен. Па, он је почео, само погледај како си обучен. Зар немаш никакве одећу са другим изгледу? Да, рекао је Џек. Сигуран сам да урадим. Дођи у моју кућу и Ја ћу им показати. Тако су они отишли ​​да Јацк. И Јацк је показао лоу кутију где је задржао све своје кошуље, и његове панталоне, и његови чарапе. Лоу рекао, видим да имате сву одећу у гомили. Зашто не носите неке др времена на време? 

Јацк је рекао, добро, кад уклоните одећу и чарапе, Ја сам их опрати и ставити их у гостима у кутији. Затим долази следећа јутро, и горе сам хоп. Ја идем у кутију и добити скинем врха. Лу је брзо схватио проблем са Џеком. Стално одећу, ЦД, и књиге у стеку. Када је посегнуо за нешто за читање или да носе, да ће изабрати топ књигу или доњи веш. Онда када је завршио, он би ставио враћам. Назад да ће то ићи, на врху гомиле. Знам решење, рекао је тријумфални Гласно. Мораш да научиш да почнете да користите редове. Лу је Јацк одећу и висио их у ормару. И када је испражњен Тхе Бок, само га бацио. 

Онда је он рекао, сада Џек, на крају дан, обуци са леве стране када их склони. Онда сутра ујутро, када вас види сунцу, скидај на десној страни, од краја линије. Зар не видиш? рекао је Лу. То ће бити тако лепо. Ти ћеш једном носити све пре него што двапут носите нешто. И са свиме у редовима у свом ормару и полици, Џек је почео да се осећа сасвим сигуран у себе. Све захваљујући Лоу и његова дивна ред. СПЕАКЕР 1: Добро, то је дивно. Дакле, оно што је заиста дешава на испод хаубе сада? То имамо путоказе, да имамо маллоц, да имамо могућност креирања комади меморије за себе динамички. Дакле, ово је слика коју угледа пре неки дан. Нисмо баш задржавати , али ова слика има се дешава испод аспиратор већ недељама. И тако то представља само правоугаоник који смо извући, меморија рачунара. А можда ваш рачунар или ЦС50 ИД, има гигабајт меморије или РАМ или два гигабајта или четири. Није битно. Ваш оперативни систем Виндовс или Мац ОС или Линук, у суштини омогућава ваш програм да мислим да има приступ у целини Меморија рачунара, иако сте можда ради више програма одједном. Дакле, у стварности, то баш и не делује. Али, то је нека врста илузије с обзиром на све програме. Дакле, ако сте имали два наступе РАМ, ово је како рачунар може мислити о томе. 

Сада случајно, један од тих ствари, један од ових сегмената меморије, назива се стек. И заиста сваки пут до сада у писаном коду да сте назвали функција, на пример маин. Подсетимо се да сваки пут имам Меморија Дравн рачунара, Увек сам некако извући пола правоугаоника овде и не смета говори шта је горе. Јер, када се зове главни, ја тврдим да ти овај делић меморије да иде доле. А ако главна зове функција као свап, и замена иде овде. И испоставило се да је где је заврши. На нечега што се зове гомила унутар меморије рачунара. Сада на крају дана, ово је само бави. То је као бајт нула, бајт један, бајт 2 милијарде. Али ако мислите о томе као овај објекат правоугаоне, све што радимо сваки време је да позовемо функција је лаиеринг нови комад меморије. Дајемо ту функцију кришка властитог меморије за рад. 

И сетим да је то важно. Јер ако немате нешто као свап и две локалне променљиве као што су А и Б и мењамо те вредности од једног и два да два и опозива, када размена врати, то је као да овај комад меморије је управо отишао. У стварности, то је још увек тамо форензички. И нешто је још увек у ствари тамо. Али концептуално, то је као Иако је потпуно нестао. И тако главни не знам ништа о раду које је урађено у тој свап функцији, осим ако је заиста прошло у оних аргументи по показивачем или као референца. Сада, основна решење да тај проблем са свап пролази ствари у по адреси. Али испоставило се, такође, шта је се дешава изнад тог дела правоугаоника све ово време је ипак тамо нема више меморије горе. А када динамички доделите меморију, да ли је унутар ГетСтринг који смо радили за вас у ЦС50 библиотека, или ако ви момци позовите маллоц и питам оперативни систем за комад меморија, то не долази из стека. Она долази из другог места у меморији рачунара то се зове гомила. И то није ништа другачије. То је исто РАМ-а. То је иста меморија. То је само РАМ то до тамо уместо овде. 

И шта то значи? Па, ако ваш рачунар има коначан количина меморије и стек расте, тако да говори, а гомила, у складу овом стрелом, расте доле. Другим речима, сваки Време ви зовете маллоц, ти да си добио парче памћења одозго, онда можда мало мање, онда мало нижи, сваки пут кад зовем маллоц, ХЕАП, то је употреба, је врста расте, расте ближе и ближе шта? Стека. Да ли то чини као добра идеја? Мислим, где то није стварно јасно шта друго можете да урадите ако само имају ограничен количину меморије. Али, то је сигурно лоша. Ове две стрелице су на убрзани курс једни за друге. 

И испоставило се да је лош момак, људи који су посебно добри са програмирањем, и покушава да упадне у рачунаре, може да искористи ову реалност. У ствари, размотримо мало фрагмент. Дакле, ово је пример можете прочитати о детаљније о Википедиа. Видимо тачке на чланак ако радознали. Али постоји један напад генерално познат као буффер оверфлов да постоји онолико дуго као људи имали способност да манипулише меморија рачунара, посебно у Ц. Дакле, ово је врло произвољна програма, али хајде да га прочитам одоздо на горе. Главни у аргц Чар стар аргв. Дакле, то је програм који узима командне линије аргументи. И све то главни очигледно је позив функција, то назвати Ф за једноставност. И испуњава неке у шта? Аргв једног. Тако да прелази у Ф год реч је да је корисник откуца на линији, након што је Име програма уопште. Толико као Цезара или Вигенере, који можда се сећате радите са аргв. 

Дакле, шта је Ф? П узима у низу као свог јединог аргумента, Ака Чар звезда, исто ствар, као стринг. И то је произвољно зове бар у овом примеру. А онда цхар ц 12, само у лаички, шта је цхар ц носач 12 ради за нас? Шта ради? Додела меморије, посебно 12 бајтова за 12 карактера. Baš tako. А онда у последњем реду, промешајте и копија, вероватно сте нисте видели. Ово је стринг копија Функција чија је сврха у животу је да копирате свој други аргумент у свом првом аргументу, али само до одређени број бајтова. Дакле, Трећи аргумент каже, колико бајтова треба да копирате? Дужина бара, год корисник унесе. И садржај бар, ту серију, су копирати у меморију указао на на Ц. 

Дакле, ово изгледа некако глупо, и то је то. То је неприродно пример, али је представник класе напада вектора, начин нападачки програма. Све је у реду и добро ако корисник типа у једном речју да је 11 знакова или мање, плус обрнута коса црта нула. Шта ако корисник укуцава више од 11 или 12 или 20 или 50 знакова? Шта је овај програм да уради? Потенцијално сец кривица. Иде да слепо копирање све у бару до дужини, која је буквално све у бару, у адресу указао на Ц. Али Ц је само превентивно даје као 12 бајтова. Али нема додатних провера. Нема ако условима. Нема грешке проверу овде. 

И шта је овај програм урадити само слепо цопи једно до другог. И тако ако ово нацртао као слику, ево Јуст а Сливер из меморије. Дакле приметите на дну, смо има локалну променљиву бар. Тако да показивач који ће да сторе-- а тој локалној аргумент који је да сачувате бар стринг. А онда приметио само изнад ње наслагане једна на другу, јер сваки пут кад питате за меморију на стек, то иде мало изнад њега ликовно, Обавештење да имамо 12 бајтова тамо. Горња лева је Ц носач нула и у доњем десном један је Ц носач 11. То је само како су компјутери да га нокаутирати. Дакле, само интуитивно, ако бар има више од 12 знакова укупно, укључујући инверзна коса нула, где је 12 или Ц носач 12 отићи? Односно, где је 12. карактер или 13. карактера, стота карактер иде завршити на слици? Изнад или испод? 

Тако је, јер иако сама стек расте на горе, Једном сте ставили ствари у је, је за дизајн разлога, ставља меморију од врха до дна. Дакле, ако имате више од 12 бајтова, ћеш почети да се препише бар. Сада када је грешка, али је није баш велика ствар. Али, то је велика ствар, јер је више ствари дешава у меморији. Ево како бисмо могли пут здраво, да би било јасно. Ако откуца поздрав на линији. В-е-л-л-о обрнута коса црта нула, завршава у те 12 бајтова, а ми смо супер безбедни. Све је добро. Али ако откуцате нешто дуже, потенцијално је да црееп у бар простору. Али још горе, испада од свег овог времена, иако ми никада нисмо причали о да, стек се користи за друге ствари. То није само локалне променљиве. 

Ц је веома низак ниво језика. И некако тајно користи стек такође да се сетим када је Функција се зове, шта адреса је претходног функције, тако да може да скочи назад на ту функцију. Дакле, када главни позиви свап, медју ствари гурнуо на стек нису само мења локалних променљивих, или његови аргументи, и тајно гурнуо на стек као што је приказано црвеном слице овде, је адреса главни физички у меморији рачунара, тако да када замена врши, рачунар зна Морам да се вратим на главни и завршетак извршења своју основну функцију. Дакле, ово је опасан, јер ако које корисник укуцава и више од здраво, тако да улаз на корисника цлобберс или преписује ту црвену део, логично ако компјутер само да слепо претпоставити да су у том црвеном бајтова слице су адреса на коју треба да се врати, шта ако је противник довољно паметан или довољно среће да стави низ бајтова има да изгледа као адресу, али то је адреса кода да он или она жели компјутер да извршава уместо главни? 

Другим речима, ако је оно што је корисник је куцање на промпт, није само нешто као безопасно здраво, али то је заправо код који је еквивалент да бисте избрисали све фајлове овог корисника је? Или емаил своју лозинку за мене? Или старт логгинг њиховог типке, зар не? Постоји начин, хајде да прописују данас, да би могли да укуцајте не само здраво свет или њихово име, они у суштини могли пролазе у коду, нула и Они, који рачунар грешке за оба кода и адресу. Тако мада помало апстрактно, ако корисник укуцава довољно адверсарном код да ћемо генерализовати овде као А. је напад или противници. Дакле, само лоше ствари. Ми не брига о бројева или нуле или они данас, тако да завршиш замени ту црвену део, приметити да редослед бајтова. О 835 Ц нула нула осам. И сада као Википедиа чланку овде је предложио, ако сад стварно почети означавање бајтова у вашем рачунару меморије, што је Википедија чланак је предлагање је да, шта ако је адреса те горњем левом бајт је 80 ° Ц 0 3508. 

Другим речима, ако је лош момак је довољно паметан са његовом или њеном код да стварно стави број овде да одговара на адресу кодекса он или она убризга у рачунару, може преварити рачунар у ради ништа. Уклањање датотека, слање е-маила ствари, њушка свој саобраћај, буквално било шта може бити убризган у рачунар. И тако се бафера Напад у својој сржи је само глупи, глупи превасходни од низа који није имао своје границе цхецкед. И то је оно што је супер опасна и истовремено супер моћан у Ц је да заиста немам приступ било где у меморији. То је до нас, програмери, који пишу оригинални код да проверите дужину проклети било којег низови да смо манипулише. Дакле, да би било јасно, шта је поправити? Ако се вратимо на ово ролл код, не би требало само променити дужину бара, што друго треба да се проверава? Шта још треба да се ради на спречи овај напад у потпуности? Не желим да кажем само слепо да копирате онолико бајтова као што је дужина бара. Хоћу да кажем, копирање и многи бајтова као у бару па све до издвојила меморија, или 12 максимално. Зато ми треба неки ако услов да не проверите дужину бара, али ако прелази 12, ми смо само хард код 12 као максимално могуће растојање. Иначе тзв буффер преливање напад може да се деси. На дну тих слајдове, Ако сте радознали да сазнате више је стварни оригинални чланак Ако желите да погледате. 

Али сада, међу цени плаћени овде је неефикасности. Дакле, то је било брзо Низак ниво поглед на оно што Проблеми могу настати сада да смо имају приступ меморији рачунара. Али друга ми проблема већ наишао је у понедељак је само неефикасност од повезане листе. Вратили смо се у линеарном времену. Ми више нема сусједном низ. Ми немамо случајан приступ. Ми не можемо да користимо квадратни конзоле запис. Ми буквално морамо да користимо вхиле петља као један сам написао пре неколико тренутака. Али у понедељак, тврдио смо да можемо црееп врати у царство ефикасности постизање нешто што је логаритамске можда, или још најбоље, можда чак и нешто што је тзв константа тиме. Дакле, како можемо учинити помоћу ове нове алати, ове адресе, ови показивачи, и тхреадинг ствари сами? Па, претпостављам да Овде, ово је гомила бројева који желимо да Чувати на структура података и ефикасно претраживање. Ми апсолутно може ревинд у недељу два, баци их у низ, иу њима помоћу бинарног претрагу. Завади па владај. А у ствари сте написали бинарни тражи у ПСЕТ3, где сте имплементиран налаза програм. Али, знаш шта. Постоји нека врста више паметан начин да то урадите. То је мало више софистициран и можда омогућава нам да видимо зашто бинарни Претрага је тако много брже. Прво, хајде да представимо појам дрвета. Који иако у реалити дрвеће врста расте овако, у свету рачунара науке су врста расту надоле као породично стабло, где имате твоји баба и деда или баба и деда велики или шта све не на врху, патријарха и Матриарцх породице, само један тзв корен, чвор, испод које су њене деце, испод којих су њени деца, или његови потомци уопште. И свако висиле дно породице дрво, поред тога што је Најмлађи у породици, такође може бити само генерички под називом лишће дрвета. 

Дакле, ово је само гомила речи и дефиниција за нешто што се зове дрво у рачунару наука, слично као породично стабло. Али ту је одгајивач инкарнације дрвећа, од којих се зове бинарно стабло претраге. И можете некако теасе Осим што ово ради. Па, то је бинарни у ком смислу? Одакле долази бинарни одавде? Молим? Није толико ни или. То је више да сваки од чворова нема више од двоје деце, као што видимо овде. У принципу, трее-- и твоји родитељи, бабе и деде могу имати онолико деце или унуци као они заправо желе, и тако, на пример, тамо имамо три Деца са тог десни чвора, али у бинарном стаблу, чвор има нула, један или двоје деце максимално. И то је лепо имовина, јер ако је капом по двоје, ћемо бити у стању да се мало лог базу два Акција се овде дешава на крају. Дакле, имамо нешто логаритамске. Али више о томе у овом тренутку. Тражи дрво значи да су бројеви уређено тако да је лева детета вредност већа од корена. И његово право дете већи од корена. Другим речима, ако узмете било који од чворови, кругови у овој слици, и гледа на свом лево дете и његово право дете, прво треба бити мања од, други треба да буде већа. Дакле, разум цхецк 55. То је остало дете је 33. То је мање од. 55, његово право дете је 77. То је већи од. И то је рекурзивна дефиниција. Можемо проверити сваки од ових чворова и исти образац ће одржати. 

Дакле, оно што је лепо у А бинарно стабло претраге је да је један, можемо имплементирати са струцт, само овако. И иако смо бацање много објеката у твој, они су донекле интуитивно сада надам се. Синтакса је и даље волшебни сигурно, али садржај чвор у ово цонтект-- и чувамо користи реч чвор, да ли је правоугаоник на екрану или круга, то је само неки генерички контејнер, у овом случају дрвета, као што је овај видели смо, морамо цео број у сваком од чворова и онда морам два показивача Указујући на левој дете и десне детета, респективно. Па тако бисмо могли спроводи то у Струцт. И како би га спровести у коду? Па, узмимо брзо погледај овог малог примера. То није функционална, али сам копирати и ту структуру. А ако моја функција за бинарни претрага дрво се зове претрага, и то узима два аргумента, цео број Н и показивач у чвор, тако да показивач на дрвету или показивач на корен дрвета, Како да идем о потрази за Н? Па, прво, зато што сам ради са показивачима, Ја ћу да урадим проверу исправности. Ако трее једнаки износи нула, је Н у овом дрвету или не у овом дрвету? То не може бити, зар не? Ако сам прошлост нулл, нема ништа. Могао бих као и само слепо кажу ретурн фалсе. Ако ми даш ништа, ја сигурно не могу наћи било који нумерички Н. Па шта сам друго могао цхецк сада? Ја ћу рећи и друго ако је Н мање него оно што је на дрвету чвор да сам предао Н вриједност. Другим речима, ако је број сам лоокинг фор, Н, мањи од чвора да ја гледам. И чвор тражим у се зове дрво, и сећам се из претходног примера да се на вредности у показивач, Ја користим стрелице запис. Дакле, ако је Н мања од дрвета стрелица Н, желим да идем лево концептуално. Како да изражавају сеарцхинг оставио? Да буде јасно, ако је ово слика у питању, и ја сам положио је највиши арров да је окренут надоле. То је моја дрво показивач. Ја сам показујући на корен дрвета. И тражим рецимо, за број 44, произвољно. Да ли је 44 или мање од већи од 55 оцигледно? Дакле, то је мање од. И то ако услов важи. Дакле, концептуално, шта хоћу да тражење следеће ако сам у потрази за 44? Да? 

Тачно, желим да тражење леви дете, или лево под-стабло ову слику. И у ствари, пустите ме да прођем слика доле за тренутак, јер Ја не могу огребати ово. Ако овде се крећу од 55, и Знам да је вредност 44 Ја тражим је да лева, некако је Као цепања телефонског именика у пола или кидање дрво на пола. Ја више не морају да брину о цела ова половина дрвета. Па ипак, радознало во однос на структура, ова ствар овде која почиње са 33, који сам по себи је бинарно стабло претраге. Рекао сам да је реч рекурзиван раније, јер заиста ово је структура података која по дефиницији је рекурзивна. Ви можда има дрво које је ово велика, али свако од своје деце представља дрво само мало мањи. Уместо тога буде деда или бака, сад је само мама или-- Не могу говоре-- не мама или тата, то би било чудно. Уместо тога, двоје деце тамо би било као брат и рођак. Нова генерација породичног стабла. Али структурално, то је иста идеја. И испоставило се да имам функцију са којима могу тражити бинарни претрагу дрво. То се зове претрага. И сеарцх фор Н у дрвету стрелице лево иф Н е већи од вредности да сам тренутно у. 55 у причи малопре. Имам функцију која се зове претрага да могу само прође Н ово и рекурзивно претрагу суб-дрво и само повратак шта год да одговор. Друго имам неку коначну базу случај овде. 

Шта је крајњи случај? Дрво је било нула. Вредност Ја ни тражим је мање него или већа од оне или једнако њега. И могу да кажем једнака једнаки, али логично је еквивалент само казем друго овде. Дакле, истина је како сам наћи нешто. Дакле, надамо се да је ово још више убедљив пример од глупог функције сигма Урадили смо неколико предавања назад, где је исто тако једноставан за коришћење петљу да изброји све бројеве из једне да Н. овде са структуром података да је и сама је рекурсивно дефинисан и рекурсивно извући, сада имају способност да се изрази у шифрама да је и сама је рекурзивна. Дакле, ово је потпуно исти број овде. 

Дакле, шта друго проблеми можемо да решимо? Тако брзо корак даље од стабала за само тренутак. Ево, рецимо, немачки заставу. И јасно је да је образац за том заставом. А ту је и много заставе у свету који су једноставна као ова у погледу њихових боја и дезена. Али претпоставимо да је ово чува као ГИФ, или ЈПЕГ или Битмап, или пинг, свака графички формат датотеке са којим сте упознати, од којих су неки смо играње са у ПСЕТ4. Ово не изгледа исплати да сачувате црна пиксела, црна пиксела, црна пиксела, тачка, тачка, тачка, цела гомила црни пиксели за прву Сцанлине, или ред, а затим гомила исто, онда гомила истог, а затим и гомила црвених пиксела, ред пиксела, црвени пиксела, онда цела гомила жутих пиксела, жута, зар не? 

Овде има таква неефикасност. Како би сте интуитивно цомпресс немачку заставу ако га примени као фајл? Као што можемо да информације смета складиштење на диску како да се смањи нашу величину датотеке из слично мегабајтом у КБ, нешто мањи? У чему је вишак запослених овде да буде јасно? Шта би ти урадио? Да? Baš tako. Зашто не пре него се сетим боја сваког пиксела проклетом баш као да радите у ПСЕТ4 са форматом битмап датотеке, Зашто једноставно не представљају левој колони пиксела, на пример, гомила црних пиксела, гомила црвене, и гомила жуте, и онда само некако кодирање Идеја Поновите ово 100 пута или поновити ово 1000 пута? Где 100 или 1.000 је само цео број, тако да вас могу да се извуку са само једним бројем уместо стотина или хиљада од додатних пиксела. И заиста, тако смо може да сабије немачку заставу. И Сада шта је са француском заставом? И мало нека врста ментална вежба, која застава може се сажети више на диску? Немачки заставу или француски застава, ако узмемо тај приступ? Немачки застава, јер је више хоризонтално редундантност. И по дизајну, многи графички фајл формати доиста раде као скенирања линије хоризонтално. Они су могли да раде вертикално, само човечанство пре одлучиле година да ћемо генерално мислим на ствари реда по ред уместо колумна колоне. И заиста, ако сте били да погледате датотеке величина немачке заставе и француском језику застава, докле год је резолуција исто, исте ширине и висина, ова Овде ће бити већи, јер вас морам да поновим себи три пута. Морате навести плава, понављање сами, бела, понављам се, црвена, Понављам себе. Не можеш тек тако све пут са десне стране. И успут, да јасно компресију је свуда, ако су четири оквира из једног видео-- сте Можда се сећате да је филм или видео генерално као 29 или 30 фрејмова у секунди. То је као мала флип књигу где си само погледајте слике, слика, слике, слика, слика само супер брзо, тако да изгледа као глумци на екрану се креће. Овде је бумбар на врх гомиле цвећа. И мада то може бити нека врста тешко да види на први поглед, једина ствар креће у Овај филм је пчела. 

Оно што је глупо о складиштењу Видео некомпримовани? То је нека врста отпада за складиштење видео као четири скоро идентичне слике које разликују само онолико колико где је пчела је. Можете бацити највише те информације и памте само, на пример, први оквир и последњи кадар, кључне оквири ако сте икада чуо реч, и само похранити у средњи где је пчела је. И не морате да чување свих розе, и плаво, и зелени вредности као добро. Дакле, ово је само да кажем да компресија је свуда. То је техника често користимо или узимају здраво за готово ових дана. 

Али како компресију текст? Како идете о сажимање текста? Па, сваки од ликова у АСЦИИ се један бајт, или осам бита. И то је некако глупо, зар не? Зато што вероватно тип А и Е и ја и О и У много чешће него као В или К или З, у зависности од језика на којем пишеш сигурно. И зашто се користимо осам битова за сваку писму, укључујући најмање популарне писма, зар не? Зашто не користе мање бита за Супер популарне писма, као Е, ствари да погодите прво у Вхеел оф Фортуне, и користити више бита за су мање популарни писма? Zašto? Јер, ми ћемо само да да их користите ређе. 

Па, испоставља се да има било покушаја да то урадите. А ако се сећате из разреда школа или гимназија, Морзеова азбука. Морзеова азбука има тачке и црте то може бити преноси дуж жице као звукова или сигнали неке врсте. Али Морзеова азбука је супер чист. То је нека врста бинарном систему у да ли имате тачке или црте. Али ако видиш, на пример, два тачке. Или, ако мислите назад на оператора који иде овако бип, бип, бип, бип, ударање мало окидач који преноси сигнал, ако вас, прималац, добија два тачака, коју поруку сте добили? Потпуно произвољна. 

Ја? Ја? Или шта о-- или ја? Можда је то била само два Е у праву? Тако да је овај проблем од Могућност декодирања са Морсе код, при чему осим ако Лице вам шаљу поруку стварно паузира тако да можете сортирати у видим или чујем јаз између слова, није довољно само да послати ток од нула и јединица, или тачке и цртице, јер је двосмисленост. Е је један тачка, па ако вас види две тачке или чути две тачке, можда је два Е или можда један И. Дакле, потребан нам је систем који је мало паметнији од тога. Дакле, човек по имену Хуффман година пре смислио управо то. Дакле, ми ћемо само да се завири колико дрвеће Германе на ово. Претпоставимо да је ово неки глупа порука коју желите да пошаљете, састављена од само А, Б, Ц је Д'с и Е је, али има доста вишка запослених овде. То не значи да је енглески. Није кодиран. То је само глупа поруку са пуно понављања. Дакле, ако сте заиста рачунати од свих А, б, ц је, Д'с, и Е је, ево фреквенција. 20% од писама су А да, 45% од писама су Е, и три друге фреквенције. Избројао смо тамо ручно и само урадио математику. 

Тако испада да Хуффман пре извесног времена, схватио да, знате шта, ако почнем зграду дрво, или шума дрвећа, ако хоћете, као што следи, могу да урадим следеће. Ја ћу дати чвор једни од писама које ми је стало и ја ћу да сачувате унутар тог чвора фреквенције као покретним зарезом вредност, или можете да га користите је Н, такође, али само ћемо користити флоат овде. И алгоритам који он је предложио је да се Користим ову шуму чвор дрвеће, тако супер кратке дрвеће, и почнете повезивање са нове групе, нове родитеље, ако хоћете. И ово урадите одабиром Најмање два фреквенције у исто време. Зато сам узео 10% и 10%. Ја стварам нови чвор. И ја називам нови чвор 20%. 

Која два чворови сам поред комбиновати? Мало је двосмислен. Тако да је неком углу предмете размотрити, али да ствари прилично, Идем да изаберете 20% - Сада игноришу децу. Идем да изаберете 20% и 15% и нацртајте два нова ивице. И сад које два чвора да логички комбинује? Игноре сву децу, све унуци, само завирити у Сада. Која два чворови да вежем заједно? Под два и 0,35. Дакле, допустите да вам скренем два нова ивице. И онда имам само једну. Дакле, овде је дрво. И то је намерно дравн да изгледа лепо, не приметим да су ивице имају Такође је обележена нула и један. Дакле, сви су напустили ивице су нула произвољно, али доследно. Сви десну ивицу су они. 

И шта Хофман је предложила јест, Ако желите да представљају Б, уместо да представљају број 66 ас АСЦИИ што је осам читаве бита, Знаш шта, само сторе образац нула, нула, нула, нула, јер је то пут из мог дрвета, господина Хуффман је дрво, на лист из корена. Ако желите да сачувате Е, с друге стране, не сенд осам битова који представљају Е. Уместо тога, пошаљите шта образац бита? Један. А шта је лепо у вези овога је да је Е најпопуларнији писмо, а ти користећи најкраћи код за то. Следећи најпопуларнији Писмо тако изгледа је А. И тако колико бита да ли је он предлаже користи за то? Нула, један. 

И зато што је имплементиран као ово дрво, за сада дозволите ми да прописују нема двосмислености као иу Морсе код, јер су сви од писма ти је стало су на крају ових ивица. Дакле, то је само једна примена дрвета. Ово је-- а ја ћу махати моја рука на то како вас Можда спроводи ово као Ц структуре. Само морамо да комбинујемо симбол, као цхар, и учесталост у лево и десно. Али, хајде да погледамо два Коначни примери које ћете добити прилично упознати са након Квиз нула проблема сет пет. 

Тако да је структура података познат као хеш табели. И хасх табела је некако охлади у томе што има кашике. И претпостављам да је четири кашике овде, само четири размаке. Ево шпил карата, и овде се клуб, лопата, клуб, дијаманти, клуб, дијаманти, клуб, дијаманти, цлубс-- тако да је случајна. Срца, хеартс-- па сам буцкетизинг све улаза овде. А потребе хасх табле да погледате вашу улаз, а затим га ставити у одређени поставите на основу онога што видиш. То је алгоритам. И сам користио супер једноставна визуелна алгоритам. Најтежи део који је био сјећања на оно што су слике биле. А ту је и четири укупно ствари. 

Сада су димњаци су расле, што је намерно дизајн ствар овде. Али шта друго могу да урадим? Дакле, у ствари овде имамо гомила старих школа испитних књига. Претпоставимо да гомила студенти су имена овде. Ево већа хеш табеле. Уместо четири кашике, Ја сам, рецимо 26. И нисмо хтели да идемо позајми 26 ствари из спољашњег [? Анненберг?], Тако Овде је пет који заступају А до З. А ако ја види студента чије име почиње са А, Ја ћу његову или њену квиз ставио тамо. Ако неко почне са Ц, тамо, А-- заправо, није хтео то да урадим. Б иде овамо. Дакле, имам А и Б и Ц. И Сада овде је још један студент. Али, ако је ово сто је хеш реализује уз низа, Некако сам сјебан У овом тренутку, зар не? Некако треба да стави ово негдје. 

Дакле, један начин да реши ово је, све Добро, А је заузета, Б је заузет, Ц је заузет. Ја ћу га ставити у Д. Дакле, прво, имам случајан брзи приступ да сваки од кашике за студенте. Али сада је некако пренета у нешто линеарне, јер ако желим да тражите некога чије име почиње са А, да проверим овде. Али, ако ово није Студент сам у потрази за, Некако морају да почну проверу у кашике, јер оно што сам урадио био нека врста линеарно испитују структуру података. Глупа начин да се каже само погледајте по првог доступног отварања, и стави као План Б, да тако кажем, или план Д у овом случају, вредност на тој локацији уместо. Ово је само тако да ако сте Имам 26 локација и студенти са именом К или З, или нешто слично да, барем да користите простор. 

Али већ смо видели више паметне решења овде, зар не? Шта би ти умјесто тога ако имате судар? Ако двоје људи имају име А шта би да је био паметнији или више интуитивно решење него само Стављање где је Год требало да буде? Зашто не само да изван [? Анненберг?], као маллоц, други чвор, стави овде, а затим ставити да студент овде. Тако да сам у суштини нека низа, или можда и више елегантно као да смо Почињем да видим повезану листу. 

И тако хасх табела је структура да изгледају овако, али више паметно, ти нешто што се зове одвојено Уланчавање, при чему хасх табела једноставно је низ, свака од чији елементи није број, је само по себи повезана листа. Тако да добијате супер брз приступ одлучивања где да хасх своју вредност. Слично као на примеру картице, Направио сам супер брзе одлуке. Срца се овде, дијаманти иде овде. Исто овде, иде овде, Д иде овде, Б иде овде. Тако супер брзи поглед-упс, и ако вам се деси да налетите на предмету где сте имам судара, два људи са истим именом, па онда почнете да их повезује. И можда би држати их поредани по абецедном реду, можда не. Али барем сада имамо динамику. Дакле, с једне стране имамо супер брз константа време и врсту линеарног времена укључени ако овим повезаних листи почну да се мало дуго. 

Дакле, ова врста глупо, Гееки јоке пре много година. На ЦС50 Хацк-А-Тхон, када су студенти цхецк ин, неки РЦ или ЦА сваке године мисли да је смешно да трпим знак овако, где се само значи ако је твоје име почиње са А, овуда. Ако ваше име почиње са Б, идите ово-- реду, то је смешно можда касније у семестру. Али постоји и други начин да то урадите, превише. Врати се на то. 

Тако да је ово структура. А ово је наша последња структура за данас, што је нешто што се зове трие. Т-Р-И-Е, који из неког разлога је кратко за проналажење, али то се зове трие. Дакле, трие је још један занимљив мешавина много ових идеја. То је дрво, које смо раније видели. То није бинарно стабло претраге. То је дрво са било којим бројем деце, али сваки од деце у Трие је низ. Низ величине, рецимо, 26 или можда 27 Ако желите да подржите хипхенатед имена или апострофа у именима људи. 

И то је структура података. И ако погледате одозго до дна, као да вас погледамо горњи чвор тамо, М, је указујући на крајњој левој ствари тамо, који је затим А, Кс, В, Е, Л, Л. Тхис ис само структура података која произвољно је чување имена људи. И Максвел је чува само следеће пут од низа до низа до низа. Али оно што је невероватно о трие је да, док повезане листе, па чак и низ, најбољи који смо икада добили је линеарног времена или логаритамске време у потрази неко горе. У овој структури података у Трие, ако моја структура података има само једно име у њој и ја тражим Маквелл, ја сам ће га наћи прилично брзо. Ја гледам за М-А-Кс-В-Е-Л-Л. Ako ова структура података, с друге стране, ако је Н је милион, ако постоји милион имена у овом структуром података, Максвел је и даље ће бити видљив након само П-А-Кс-Ш-Е-Л-Л кораци. Анд Давид-- Д-А-В-И-Д корака. Другим ријечима, изградњом структура података која је добили од којих свих ових низовима, алл издржавају случајан приступ, Могу почети лоокинг уп Народне наме користећи количину времена које је сразмерно броју не ствари у структури података, Као милиона постојећих имена. Износ време ми је потребно да нађемо М-А-Кс-Е-е-л-Л у овој структури података је пропорционална није до величини објекта података, већ са дужином имена. А реално имена гледамо горе никада неће бити луди дуго. Можда неко има 10 карактера наме, 20 име карактера. То је свакако коначно, зар не? Постоји људско на Земљи који има најдужи могући име, али то име је константа Дужина вредност, зар не? Она не варира у било ком смислу. Дакле, на овај начин, ми смо остварили структуру података То је константна време лоок-уп. То се предузму низ корака зависно од дужине улаз, али не и број имена у структури података. Дакле, ако удвостручити број имена наредне године од милијарду до две милијарде, налаз Максвел ће узети потпуно исти број седам корака да га пронађу. И тако изгледа да смо постигли наш свети грал времена рада. 

Дакле пар брзих обавештења. Квиз нула долази. Више о томе на сајту току је у наредних неколико дана. У понедељак лецтуре-- То је празник овде на Харварду у понедељак. Није у Нев Хавен, тако да узимамо разред у Њу Хејвен за предавања у понедељак. Све ће бити снимљен и стримовано као и обично, али хајде да заврши данас са 30 секунди клипа називају "Дееп Тхоугхтс" од Давен Фарнама, који је инспирисан прошле године у суботу Нигхт Ливе "је Дееп Тхоугхтс" Јацк Ханди, који би сада смисла. 

ФИЛМ: А сада, "Дубоко Мисли "по Давен Фарнама. Хасх табела. 

СПЕАКЕР 1: Добро, то је то за сада. Видимо се следеће недеље. 

Даг: Да га видимо у акцији. Дакле, хајде да погледамо то сада. Дакле, овде, имамо неразврстан низ. 

Иан: Даг, можеш ићи напред и Рестарт ово само један секунд, молим вас. У реду, камере су ваљање, тако Акција кад год сте спремни, Даг, у реду? Даг: У реду, па шта смо имам овде је низ мусиц. И ја сам обојена све елементе црвене до указују да је, у ствари, мусиц. Дакле, сећам се да смо прва ствар коју уради је да сортирају левој половини низа. Онда смо некако право половини низа. А иа-Да иа-Да иа-Да, их спојити заједно. И имамо потпуно сортирану низ. Па тако спојити Сортирај дела. 

Иан: Опа, опа, опа, рез, рез, рез, рез. Даг, не можеш само Иа-Да иа-Да, Иа-Да, свој пут кроз стапања врсте. 

Даг: Управо јесам. Уреду је. Ми смо добро иде. Само будимо ваљање. И тако, 

Иан: Морате објаснити да потпуније од тога. То једноставно није довољно. Даг Иан, ми не да се вратим на један. Уреду је. У сваком слуцају, ако наставимо са мерге-- Иан смо усред снимања. 

Иан: Знам. И не можемо само Иа-Да иа-Да, Иа-Да, кроз цео процес. Морате да објасни како је Две стране се заједно спојили. 

Даг: Али већ смо објаснио како два сидес-- 

Иан: Управо сте приказано им Стапање низ. Даг: Знају процес. Они су добро. Прешли смо преко њега десет пута. 

Иан: Само Прескочио њега. Враћамо се на један, ви не можеш Иа-Да иа-да преко њега. У реду, назад на један. 

Даг: Морам да се вратим кроз све слајдове? Боже. То је као шести пут, Иан. Уреду је. 

Иан: У реду. Јесте ли спремни? Велики. Акција.