Давид Малан: У реду. Вратили смо се. Дакле, у овом сегменту о програмима који Мислио сам да бих је мешавина ствари. Један, до мало нешто Хандс-Он, мада користећи више разигран програмирање енвиронмент-- онај који је демонстративни од управо то врсте идеја смо причали, али мало више формално. Два, погледати неке од су више техничке начине да би програмер ствари решити Проблеми попут трага проблем да смо гледали раније и такође више фундаментално Занимљиво проблем сортирање. 

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

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

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

И тако сваки комад пет бита, сваки бајт од нула и јединица овде, представљају неки упутство типично унутар рачунара. И у ствари, ако сте чули маркетиншки слоган "Интел Инсиде" - да, Наравно, само значи да имају ЦПУ или мозак унутар рачунара. И шта то значи бити процесор да имате скуп инструкција, такорећи. 

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

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

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

Дакле, оно што ћете видети у ово енвиронмент-- и заправо пусти на мене. Да ли је неко није овде? Не овде? ОК. Па нека ми истакнем неколико карактеристике ове средине. 

Дакле, у горњем левом углу екрана, ми има фазу Сцратцх је, да тако кажем. Огреботина није само име овог програмског језика; Такође је име мачку која видиш по дефаулту тамо наранџасте боје. Он је на сцени, тако баш као што сам описао корњача раније као битак у правоугаони бели одбор окружење. свет ове мачке је ограничен у потпуности у том правоугаоника до врха тамо. 

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

Дакле, то су категорије до врха. Идем да кликнете на категорију Цонтрол. Уместо тога, ја ћу да кликнете на догађаје категорија, први човек на врху. А ако желите да пратите још као и ми то, ти си сасвим добродошли. Идем кликните и повуците ово Први, "када зелена застава кликне." А онда ћу да га баци само грубо на врху мојих празни листови папира. 

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

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

Ако погледате Сцратцх фази овде и погледајте на врху, видећете црвено светло, А стоп знак, и зелену заставу. И ја идем напред и гледали моје сцреен-- за тренутак, ако можеш. Идем да кликнете на зелена застава сада, и он се преселио како се чини, 10 корака или 10 пиксела, 10 тачака, на екрану. 

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

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

ОК. И пусти ме једном која је нешто једноставније само на тренутак. Пусти ме напред и уради то. Приметите да, као што може имати открили под контролом, ту је ово понављање блок, који не изгледа као да је то велика. Нема много простора у између те две жуте линије. Али, као што неки од вас можда има приметио, ако драг анд дроп, приметити како расте за попуњавање облика. 

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

Сада неки од вас предложено, као Вицториа само није, поновити 10 пута. И то углавном ради да га скроз, али не би ли бити више робустан начин него произвољно смисли колико потеза да? Шта би могао бити бољи блок од понављања 10 пута бити? 

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

И само интуитивно, Зашто стално помера? Шта се дешава овде? Изгледа да је престала, али онда ако сам покупити и отпор он стално жели да иде тамо. Зашто је то? Заиста, компјутер је буквално радити оно што ти ја кажем. Дакле, ако то раније рекли ураде након ствар заувек, крећу 10 корака, да ће наставити и иде док сам ударио црвени стоп знак и зауставити програм у потпуности. 

Дакле, чак и ако није ово, како бих могао да Сцратцх потез брже преко екрана? Више корака, зар не? Дакле, уместо да раде 10 у исто време, зашто не бисмо само напред и променити да-- шта би пропосе-- 50? Дакле, сада ћу да кликнете на зелени застава, и заиста, он иде врло брзо. 

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

Сада следећи изазов који сам предложио је да га одбијају ивицу. И не знајући шта слагалица комада екист-- јер је то у реду ако не добијете до фаза цхалленге-- што желиш да интуитивно радити? Како би смо га одбити и даље, између леве и десне стране? 

Да. Тако да је потребна нека врста стања, и ми Изгледа да имају уређаја, тако да се говоре, у категорији Цонтрол. Која од ових блокова ми вероватно желети? Да, можда "ако, онда." Тако приметити да међу жутим блоковима имамо овде, ту је ово "ако" или ово "ако, други" блок који ће дозвољавају нам да донесе одлуку да се то уради или да то уради. А можете их чак гнездо да раде више ствари. Или ако не отишли ​​овде још, иди на Сенсинг категорији и-- да видимо да ли је то овде. 

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

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

Да ли би неко желео да предложи како сам може да се повеже ове можда врха до дна како би се решио проблем постојања Сцратцх потез десна на лево на право на лева на десно на лево, сваки време само одбијају зида? Оно што желим да урадим? Који блок треба да се повеже са "Када зелена застава кликнули прво"? 

У реду, па почнимо са "заувек." Оно сто иде даље? Неко други. У реду, покрет кораке. У реду. Шта онда? Па онда ако. И приметио, иако изгледа сендвичу заједно чврсто, то ће само расти да попуне. То ће само скочити у којој желим то. 

И шта да ставим између иф и онда? Вероватно "ако додирнете ивицу." И обавештење, опет, то је превелик за то, али ће порасти за попуњавање. А онда окренути за 15 степени? Колико степени? Да, па 180 ће окретати мене све обрнуто. Па да видимо да ли сам добро разумео. Пусти ме умањили. 

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

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

Вероватно желим да користим шта блок уместо тога, на основу онога што видите овде? Како бисмо могли поправити ово? Да, тако да смо могли указати у супротном смеру. И заправо ни то неће бити довољно, јер можемо само тешко код да показује лево или десно. 

Знаш шта можемо да урадимо? Изгледа да имамо погодност блок овде. Ако зумирам, погледајте нешто што се овде? Тако да изгледа као МИТ-хас ан апстракција изграђен овде. Овај блок изгледа еквивалент на које друге блокове, множина? 

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

Али приметио сам заменио три блока са једне, и то је вероватно добра ствар. Ја сам захваћене далеко појам провере да ли сте на граници са само једним блоком. Сада можемо да се забавимо са овим, у ствари. То не додати толико интелектуална вредност али разигран вредност. Ја идем напред и ухватите тај звук овде. Тако да ме само напред, и пусти ме стоп програм за тренутак. Ја ћу снимити следеће, омогућавајући приступ микрофоном. 

Идемо. Јао. Хајде да покушамо поново. Идемо. У реду, снимио сам погрешну ствар. Идемо. Јао. Јао. У реду. Сада морам да се отарасим тога. У реду. 

Тако да сада имам снимање само "јао." Зато сада идем напред и зову "јао." Ја ћу да се вратим мојим скрипте, и сада Обавештење ту је блок који се зове плаи соунд "меов" или репродукцију звука "јао." Ја ћу ја то, и где да кажем за комичне ефекат? Да, а сада је некако луд, јер сада ово блоцк-- како се овај "ако на ивици, Боунце "је врста самосталан. Зато морам да поправим ово. Пусти ме напред и уради то. Пусти ме да решим ово и да се вратим на нашем оригиналу, више намерна функционалност. Дакле, "ако додиривање ивица, онда" Желим да се окрену, као Викторија предложено, 180 степени. И желим да играм звук "јао" тамо? 

Да, приметио је напољу та жута блок. Тако да, такође, ће бити буба, али сам приметио. Па ћу га ја овде, и обавештење сада је унутар "ако". Дакле, "ако" је та врста Као руке попут блот анализе да ће само оно што је у њему. Па сад ако умањили у ризик анноиинг-- 

Цомпутер: Јао, јао, јао. 

Давид Малан: И ће само наставити заувек. Сада само да убрза ствари овде, пусти ме само напред и отвори, хајде да говоре-- пусти ме на неке од своје ствари из класе. И пусти ме отвори, рецимо, ово један је од стране једног од наших наставних другова Пре неколико година. Дакле, неки од вас можда сетити ова игра из прошлих времена, и то је заправо изузетна. Иако смо урадили Најједноставнији програма одмах, Хајде да размотримо шта ово заправо изгледа. Пусти ме хит представу. 

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

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

Али шта друго што се дешава? Које друге линија кода, шта други пуззле пиецес јесте Блејк, наш демонстратор, користити у овом програму, очигледно? Шта је све што мове-- шта програмирање изградити? 

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

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

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

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

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

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

Сви они. Ти си некако среће. Имате буквално да погледате сваки страна ако је телефон књига је само насумично поредани. Можда ти се посрећи и наћи Мике на првој страни, јер он је прва муштерија да нареди телефонску службу. Али је можда био последњи, такође. 

Тако насумично поредак није добро. Претпостављам да имамо да учини нешто телефонски именик или у општем методу података да смо добили. Како то да урадимо? 

Па, хајде да пробам једноставан пример овде. Пусти ме напред и баците неколико бројева на табли. Претпоставимо бројеве које имамо су, рецимо, четири, два, један, и три. И, Бен, сложити бројеве за нас. 

Добро. Како си то урадио? У реду. Дакле, почните са најмањим вредност и највиша, и то је стварно добро интуиција. И схватити да смо ми људи су заправо прилично добар у решавању проблема овако бар када су подаци релативно мали. Чим почнете да стотине бројева, хиљаде бројева, милиони бројева Бен вероватно не бих могла сасвим тако брзо, под претпоставком да је било празнине у броју. Прилично лако да бројим до милион иначе, троши само време. 

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

Дакле, с обзиром да заиста имамо четири одвојене вредности овде- а можете мислити о Бен као да амове да је био рачунар тако да не може да види ништа друго од једног броја има у једном-- тако да ће генерално претпоставити, као у Енглески, ми ћемо читати са десна на лево. Дакле, први број Бен вероватно изгледало на било четири и онда веома брзо схватили да је прилично велика нумбер-- пусти ме да тражим. 

Има два. Сачекај минут. Два мања од четири. Идем да се сетим. Два је сада најмањи. Сада једног-- то је још боље. То је још мања. Ја ћу да заборавим два и само се сетите једног сада. 

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

И сада понављамо процес, и наравно три буде извучена следећи. Поновите поступак. Четири буде извучена. А сада смо ван бројева, па морају уредити листа. 

И заиста, ово је формални алгоритам. Компјутерски научник би ово називају "селекције врсту," идеја је била Сортирај А лист итеративели-- поново и опет и опет избора најмањи број. А шта је лепо у вези је то је тако проклето интуитивно. То је тако једноставно. И можете поновити исти операција опет и опет. То је једноставно. 

У овом случају то је био брз, али колико то заправо траје? Хајде да се чини и Осећам се мало више досадан. Дакле, један, два, три, четири, пет шест, седам, осам, девет, 10, 11, 12, 13, 14, 15, 16 произвољан број. Само сам хтео више ово Време од само четири. Дакле, ако имам једну целину гомила бројева је сада-- чак ни не битно оно што су- ЛЕТ'С размислите о томе шта ово алгоритам заиста изгледа. 

Претпостављам да су бројеви тамо. Опет, није битно шта они су, али су случајно. Пријављујем Бен алгоритам. Морам да изаберете најмањи број. Шта да радим? И ја ћу физички уради ово време да се делује ван. Гледајући, гледајући, гледа, гледа, гледа. Само се ја не да крај листе може Схватам најмањи број је два овај пут. Један није на листи. Па сам спустио два. 

Шта даље да радим? Гледајући, гледајући, гледајући, гледајући. Сада сам нашао број седам, јер има недостаци у овим нумберс-- али само произвољна. У реду. Тако да сада могу спустити седам. Гледајући гледајући, гледајући. 

Сада претпостављам, од Наравно, да је Бен не има додатни РАМ, екстра меморије, јер, наравно, Гледам истог броја. Сигурно сам могао сетио све те бројеве, и то је апсолутно тачно. Али, ако Бен сећа све бројева што је видео, он није заиста направио основни напредак јер већ има могућност претраживања кроз бројеве на табли. Сећање све од Бројеви не помаже, јер је још увек може као рачунар само погледати, што смо рекли, један број у време. Тако да нема нека врста варалице тамо да можете искористити. 

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

Па Размислимо колико корака Ја сам у ствари траипсинг кроз сваки пут. У првом стању имали смо 16 бројева, и тако макималли-- хајде да Од овога дисцуссион-- Морао сам да погледам кроз 16 Бројеви наћи најмањи. Али када сам извукао најмањи број, како док је преосталих листи, наравно? Само 15. Дакле, колико бројева је Бен или морам да погледа кроз други пут око? 15, само да одем и наћи најмањи. Али сада, наравно, списак је, такође, мањи него раније. Дакле, колико корака зар не узети следећи пут? 14 и потом 13 и онда 12 плус тачка, тачка, тачка, док сам отишао са само једним. Тако да сада компјутер научник би питај, па, шта то сви једнаки? То је заправо једнако неким конкретним број који смо могли сигурно до аритметички, али желимо да говоримо о ефикасности алгоритама мало више формулаицалли, независно од колико је листа. 

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

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

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

Дакле, користећи исту логику, у међувремену, Размотримо још један алгоритам већ гледали ат-- линеарно претрагу. Када сам тражио за телефонски боок-- не сортирање, претраживање преко телефона боок-- ми је говорила да је 1.000 корака, или 500 корака. Али хајде да генерализовати то. Ако постоји н странице у телефонски именик, што је прирастао време или Ефикасност линеарне претраге? То је реда колико корака да пронађете Мајк Смит користећи линеарно претрагу, Први алгоритам, или чак други? 

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

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

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

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

И то не мора да буде нешто ви расправљати детаље, али добар програмер је неко који има солидну, формално позадину. Он је у стању да разговара са Ви у оваквом путу и заправо чине квалитативне аргументи као зашто један алгоритам или један комад софтвера супериоран на неки начин у другу. Зато што сте могли сигурно само покренути програм једне особе и броји секунди је потребно за сортирање неке бројеве, а можете покренути неки друге особе програм и изброји секунди је потребно. Али ово је више општи начин на који можете користити за анализу алгоритама, ако хоћете, само на папир или само усмено. Чак и без ради, без Чак покушава узорака улаза, само се уразумити кроз њега. И тако са ангажовањем програмер или ако да га или њу некако тврде да вам зашто је њихов алгоритам, њихова тајна сос за претраживање милијарде веб страница за ваш Компанија је бољи, ови су врсте аргумената они би идеално моћи да. Или бар су Врсте ствари да ће доћи у дискусији, у бар у веома формалне расправе. У реду. И Бен је предложио нешто зове избор врста. Али ја ћу предложити да постоји други начини да се ово уради, такодје. Оно што нисам волела о Беновом алгоритам је да је стално хода, или што да ходам, напред и назад и назад и напред и назад и напред. Шта ако уместо тога требало да урадим нешто попут ових бројева овде и ја смо се само баве са сваким број заузврат како сам га дао? 

Другим речима, овде је мој списак бројева. Четири, један, три, два. И ја ћу да урадите следеће. Ја ћу убацити бројеве где су радије припадају од одабира их једну по једну. Другим речима, овде је број четири. 

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

Да ли је ово нова листа поредани? Да. То је глупо, јер постоји само један елеменат, али то је апсолутно поредани. Не постоји ништа на свом месту. То је још занимљивије, овај алгоритам, када сам прећи на следећи корак. 

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

Тако да унесете број један Не могу само да скренем овде. Овај меморијски простор не постоји. То би било варање, и ја сам био варање ликовно за неколико минута овде. Дакле стварно, ако желим да ставим један овде, Морам да привремено копирање четири а затим ставити ону тамо. 

То је у реду, то је тачно, То је технички могуће, али схватите да је то додатни посао. Нисам само ставити број на месту. Први пут сам морао да померим број, а затим га ставити на место, па сам некако удвостручио своју количину посла. Дакле, имајте то на уму. 

Али ја сам сада завршио са овим елементом. Сада желим да зграбите број три. Где је, наравно, то припада? Између. Не могу варати више и само стави тамо, јер, опет, ове меморије је у физичке локације. Тако да морам да копира четири и ставити три овде. Није велика ствар. То је само један додатни корак Поново: осећа веома јефтин. 

Али сада сам прешао на њих. Њих двојица, наравно, припада овде. Сада можете почети да видите како рад се гомилају. Сада шта ја треба да урадим? Да, морам да померите четири, онда морам да копира три, а сада могу убацити два. А проблем са овим алгоритам, занимљиво, је да претпоставимо да имамо као екстремну случај где је рецимо осам, седам, шест, пет, четири, три, два, један. Ово је, у многим контекстима, најгори сценарио, јер је проклета ствар је буквално уназад. 

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

Дакле, један, два, три, четири, пет, шест, седам, осам. Један два три четири, пет, шест, седам, осам. Ја ћу узети осам, и где да га ставим? Па, на почетку мог списка, јер ова нова листа је сортирана. И ја га прецртати. 

Где да ставим седам? Проклетство. Он мора да оде тамо, тако Морам да мало копирање. А сада седам иде овде. Сада прелазим на шест. Сада је још више посла. 

Осам мора да иде овде. Седам мора да иде овде. Сада је шест може ићи овде. Сада сам узми пет. Сада осам мора да оде овде, седам мора да иде овде, шест мора да иде овде, и сада пет и понављања. И ја сам прилично се кретати стално. 

Тако да је на крају, ово алгоритхм-- ћемо зову га уметање сорт-- заправо има пуно посла, такође. То је само другачије врста посла него Бен. Бен рад си ме преварио напред и назад све време, избор следећи најмањи Елемент изнова и изнова. Тако да је ово веома визуелни врста посла. 

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

Па ако можете замислити ово осам и седам и шест и пет а потом четири и три и два креће свој пут кроз листу, смо управо промени врста посла радимо. Уместо да се то уради На почетак мог итерације, Ја само то радио на крај сваког итерација. Тако испада да овог алгоритма, такође, уопштено назван сортирање уметањем, је такође реда од н на квадрат. То је заправо ништа боље, нема бољег уопште. 

Међутим, постоји трећи приступ Ја бих и да размотримо, који је ово. Претпостављам моју листу, због једноставности опет, четири, један, три, два-- само четири броја. Бен је имао добру интуицију, добро људској интуицији пре, којим смо фикед цела лист евентуалли-- сортирање уметањем. наговорили да нас заједно. Али хајде да размотри Најједноставнији начин да се поправи ову листу. 

Ова листа се не сортира. Зашто? На енглеском, објаснити зашто није заправо поредани. Шта то не значи да се сортирају? 

СТУДЕНТСКИ: Није узастопна. 

Давид Малан: Не узастопна. Дајте ми један пример. 

СТУДЕНТСКИ: Ставите их у ред. 

Давид Малан: У реду. Дај ми више конкретан пример. 

СТУДЕНТСКИ: растућим редоследом. Давид Малан: Не узлазним редоследом. Будем прецизнији. Не знам шта ви подразумевате под успону. Шта није у реду? 

СТУДЕНТСКИ: Најмањи од Бројеви није у првом простору. 

Давид Малан: Најмањи број је не у првом простору. Бити прецизнији. Поцињем да ухватим на. Ми рачунамо, али шта је у квару овде? 

СТУДЕНТСКИ: Нумерички секвенца. Давид Малан: Нумеричка секвенца. Свачија врста чувања то овдје-- врло висок ниво. Само ми буквално рећи шта је погрешно као пет-годишњи моћи. 

СТУДЕНТСКИ: Плус један. 

Давид Малан: Шта је то? 

СТУДЕНТСКИ: Плус један. 

Давид Малан: Како то мислиш плус један? Дај ми другачији од пет година. Шта није у реду, мама? Шта није у реду, тата? Шта ти мислиш да се не сортира? 

СТУДЕНТСКИ: То није право место. 

Давид Малан: Шта је не на правом месту? 

СТУДЕНТСКИ: Четири. Давид Малан: У реду, добро. Дакле, четири је не где би требало да буде. Посебно, је ли тако? Четири и једна, први два броја видим. Да ли је то у реду? Не, они су ван употребе, зар не? У ствари, мислим да сада о рачунару, такође. То може само погледати можда једном, можда две ствари на једном-- а заправо само једна ствар истовремено, али може бар погледај једну ствар онда Следећа ствар одмах поред њега. 

Тако је ово у реду? Наравно да не. Дакле, знате шта? Зашто не узмемо бебу кораци за причвршћивање овај проблем уместо да ради у овим модерним алгоритми попут Бен, где Он је на неки начин га фиксирање петље кроз листу уместо да ради оно што сам урадио, где Само сам то поправио док идемо? Хајде да се буквално сломити Појам ордер-- нумеричком редоследу, назовите га како год глупане-- у овим паровима поређења. 

Четири и један. Да ли је ово исправна наредба? Дакле, хајде да поправимо то. Један и четири, а затим ми ћемо само цопи то. У реду, добро. Сам поправио један и четири. Три и два? Не. Нека моје речи одговара прсте. Четири и три? 

То није у реду, па идем да до један, три, четири, два. Добро. Сада четири и два? Морамо да поправимо ово. Тако један, три, два, четири. Тако је то поредани? Не, али да ли је ближе поредани? 

То је, јер фиксни ово грешка, фиксна смо ову грешку, и ми фиксне ову грешку. Тако да фиксна три грешке вероватно. Још увек не изгледа сортирана, али је објективно ближе сортирана јер фиксни неке од тих грешака. 

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

Требало би да покушате поново. Па Оливија предлаже да покушам поново. Зашто? Јер рачунар нема луксуз наших људских очију да само гледајући натраг-- реду, готов сам. Како компјутер одреди да је листа сада сортиране? Механички. 

Морам да идем кроз још једном, и само ако не прави / нађете неку грешку могу онда закључити као компјутер, Да, ми смо добро иде. Дакле, један и два, два и три, три и четири. Сада сам дефинитивно могу рећи да је ово поредани, јер сам се никакве промене. Сада би било грешка и само глупо ако И, рачунар, опет питао те исте питања очекујући различите одговоре. не би требало да се деси. 

Па сада Листа је сортирана. На жалост, руннинг време Овај алгоритам је такође Н квадрат. Зашто? Јер имате н бројева, ау у најгорем случају морате да преместите н бројева н пута јер треба да наставимо назад на провери и потенцијално поправити ови бројеви. И можемо учинити више формална анализа, такође. 

Дакле, ово је све да кажем да сам узео три различита приступа, један од њих одмах интуитиван искључити шишмиш из Бен у мом предложена уметања врста на овај где сте некако изгубити из вида шума за дрвеће у почетку. Али онда, ако се корак уназад, Воила, ми смо фиксни појам сортирања. Дакле, ово је, усуђујем се рећи, нижи ниво можда него неки од њих остало алгоритми, али да види ако не може замислити ови путем овог. 

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

И приметити шта ради. Начин на који су они изабрали да Смештен алгоритам је да, као што сам био ходање по мојој листи, овај програм хода кроз листу бројева, наглашавајући ин пинк сваком број да се гледа. А шта је о сада да се деси? 

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

Дакле, сортирање уметањем је све урађено. Морам да поново насумично низ. И приметио могу само кееп ит случајности, и ми ћемо добити апроксимацију исти приступ, сортирање уметањем. Пусти ме да успорим да овде. Почнимо да преко. Зауставити. 

Да прескочимо четири. Ево га. Рандомизе су низ. И овде иде-- сортирање уметањем. Плаи. Приметите да то раде једни с Елемент се сусретне одмах, али ако спада у погрешно обавештење место сав посао који треба да се деси. Морамо да мјењају стално више и више елемената да би се направио простор за оне желимо да успостави. 

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

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

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

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

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

Дакле, идемо са неким звуком. Ово је сортирање уметањем, па опет то је само ради са елементима како долазе. То је балон врста, тако да је с обзиром им парова у исто време. И опет, највећи елементи се кључа до врха. 

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

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

Па, хајде да сада задиркују, осим што све ове линије су да сам цртеж и шта ја претпостављам компјутер може да испод хаубе. Ја бих рекао да све ове бројке Стално дравинг-- морају да се чува негде у меморији. Ми ћемо се отарасити овог типа сада, такође. 

Дакле, комад меморију у цомпутер-- тако РАМ-ДИММ оно што смо тражили јуче, два меморијски модуле-- изгледа овако. И свака од ових малих црних чипова је неки број бајтова, типично. А онда су златне игле су као да је жице које га повезују са рачунаром и зелени силицијум одбор је само шта држи све заједно. Дакле, шта то заправо значи? Ако некако извући ову исту слику, претпоставимо ради једноставности да ово СО-ДИММ, Дуал меморијски модул, је један гигабајт РАМ меморије, један гигабајт меморија, која је колико бајтова укупно? Један гигабајт је колико бајтова? Више од тога. 1.124 је килограм, 1.000. Мега је милион. Гига је милијарду. 

Лажем? Можемо чак прочитати етикету? Ово је заправо 128 гигабајта, тако да је више. Али ћемо се претварати ово је само један гигабајт. Тако да значи да је милијарду бајтова меморије на располагању за мене или 8 милијарди битова, али идемо сада причају о бајтова, напредовати. 

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

И тако сам могао ставити четири броја овде. Један два три четири. Или бих могао ставити четири слова или симболе. "Хеј!" Могао бих да стигнем тамо, јер сваки од слова, разговарали смо раније, могу бити представљени са осам бита или АСЦИИ или бајт. Другим речима, можете пут 8 милијарди ствари унутра овог једног штапа меморије. Дакле, шта значи да се ствари вратити враћа се назад у меморији овако? То је оно што програмер позвати хитну "низ." У компјутерском програму, не мислиш о хардверу у основи, по себи. Ти само мислиш о себи као да приступ милијарду бајтова укупно а, и можете било шта желите са њом. Али, ради лакшег то је генерално корисно да би меморијске право један поред другог овако. Дакле, ако сам зумира ово-- јер ми никако не иде да скрене милијарду мало скуарес-- претпоставимо да је ова плоча представља да штап меморије сада. И ја ћу извући онолико колико мој маркера завршава ми дали овде. Тако да сада имамо штап меморије на плочи да има један, два, три, четири, пет, шест, један, два, три, четири, пет, шест, севен---так 42 бајтова меморија на укупно екрану. Хвала вам. Да, јесте моја аритметика у праву. Дакле 42 бајтова меморије овде. Дакле, шта то заправо значи? Па, компјутерски програмер би заправо уопште да ове меморије као Адресабилна. Другим речима, сваки од њих локације у меморији, у хардвер, има јединствену адресу. 

То није као сложен као један БРАТТЛЕ Скуаре, Цамбридге, МА., 02138. Уместо тога, то је само број. Ово је бајт број нула, ово је једна, ово је два, ово је три, а ово је 41. Сачекај минут. Мислио сам рекао 42 малопре. Почео сам да бројим на нули, тако да је заправо у праву. Сада не морамо да заиста и извући као мрежу, а ако га извући као мрежа Мислим да ствари стварно да помало збуњује. Шта програмер би, у свом сопственом уму, генерално мислите о овоме меморија као што је као траке, као комад заштитне траке да само иде даље и даље заувек или док не понестане меморије. Дакле, чешће начин да се скрене и само мислим о меморији би да је ово бите нула, један, два, три, а онда тачка, тачка, тачка. И имате укупно 42 таквих бајтова, чак иако физички је заправо можда бити нешто више овако. 

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

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

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

И укупно, колико битова умешан сада, само да буде јасно? Дакле, ово је четири бајта, или сада је укупно 32 бита. Тако да заправо постоје 32 нуле и Они састављање ове четири ствари. Има још овде, али Опет ми не бринемо о томе. 

Дакле, хајде да питам неког другог Питање користи меморију, јер то на крају дана је у супротности. Без обзира шта бисмо могли да урадимо са рачунар, на крају дана хардвер је и даље Исто испод хаубе. Како би чувам реч овде? Па, реч у компјутеру као "Хеј!" би се чувају само овако. А ако желиш дужи реч, можете једноставно преписати да и рећи нешто као "здраво" и продавница које овде. 

И тако овде, такође, овај цонтигуоуснесс је заправо предност, јер компјутер могу само читати са десна на лево. Али овде је питање. У контексту ове речи, Х-Е-Л-Л-О, знак узвика, како би рачунар зна где је реч почиње и где се завршава реч? У контексту бројева, како се рачунар знам колико дуго редослед Бројеви или где почиње? Па, испоставило се оут-- и нећемо ићи превише у овом нивоу детаил-- рачунари крећу ствари унаоколо у меморији буквално путем ове адресе. Дакле, у рачунару, ако сте писање кода за чување ствари као речи, шта си стварно ради куца изрази који памте где у меморија рачунара ове речи су. Дакле, пусти ме да је веома, врло једноставан пример. 

Ја идем напред и отвори једноставан текст програма, и ја ћу створити фајл под хелло.ц. Већина ових информација ми Нећу ићи у веома детаљно, али ја ћу написати Програм на том истом језику, Ц. Ово је далеко више застрашујуће, Ја бих рекао, него Сцратцх, али то је врло слично у духу. У ствари, то коврџава брацес-- можете некако мислим на оно што сам урадио, јер то. 

Хајде да урадимо ово, заправо. Када зелена застава кликне, урадите следеће. Желим да одштампате "здраво." Дакле, ово је сада Псеудокод. Некако сам замагљују линије. У Ц, овај језик ја говорим о, ова линија штампа здраво заправо постаје "принтф" са неки заграде и полу-дебелог црева. 

Али то је потпуно исти идеја. И то врло разумљив "Када зелена застава кликне" постаје Много више волшебни "маин празнина." А ово стварно нема мапирање, па ја ћу игнорисати то. Али великих заграда су као да је закривљене пуззле пиецес лике тхис. 

Тако да можете некако претпостављам. Чак и ако никада нисте програмирали раније, Шта овај програм вероватно не? Вероватно штампа здраво са знаком узвика. 

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

И видим да, Поново, као што следи, ови су нуле и јединице И само направљена од мог изворног кода, све нуле и јединице. И ако желите да покренете мој програм-- се дешава да се зове а.оут за историјски реасонс-- "здраво". Могу га поново покренути. Здраво здраво здраво. И чини се да ради. 

Али то значи негде у мом меморија рачунара су речи Х-Е-Л-Л-О, знак узвика. И испоставило се да, баш као страну, шта је компјутер би типично учини да зна где ствари почињу и енд-- је ће ставити посебан симбол овде. А конвенција је ставио број нула на крају речи тако да знате где је заправо завршава, тако да не води штампање више и више ликови од тебе заиста намеравају. 

Али понети овде, чак и мада је то прилично волшебни, је да је на крају релативно једноставна. Ви сте добили неку врсту траке, празна простор на којима можете писати писма. Једноставно морају да имају Посебан симбол, као произвољно број нула, ставити на крају твоје речи тако да рачунар зна, Ох, ја треба да престану штампу после Видим узвичник. Зато што је следећа ствар тамо је АСЦИИ вредност нула, или нулти карактер као неко би га назвати. Али нека врста проблема овде, и идемо вратити на бројеве за тренутак. Претпоставимо да радим, у ствари, има низ бројева, и претпоставимо да је Програм пишем је као разред књига за учитеља и наставницима. И овај програм њега или њу дозвољава да унесете резултате својих ученика на тестовима. И претпоставимо да је ученик добија 100 на свом првом квизу, можда као 80 на следећи, а затим и 75, затим 90 на четвртом квизу. 

Дакле, у овом тренутку у причи, низ је величине четири. Нема апсолутно више меморије у рачунар, али низ, да тако кажем, је величине четири. Претпоставимо сада да наставник жели доделити пети квиз на класу. Па, једна од ствари које је или она ће морати да уради сада је похранити додатну вредност овде. Али ако низу наставник има створена у овом програму је величине за, један од проблема са низа је то Ви не можете само задржати додајући да меморију. Јер, шта ако други део је Програм има реч "хеј" тамо? 

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

Дакле, наставник може уместо тога кажу приликом писања програма за чување његово оцене, знаш шта? Ја ћу тражити, приликом писања мој програм, да желим нула, један, два, три, четири, пет, шест, осам разреда укупно. Дакле, један, два, три, четири, пет, шест, седам, осам. Наставник може само преко расподјелу меморија приликом писања своје програм и рећи, знаш шта? Никад нећу да додели више од осам квизова у једном семестру. То је лудо. Никада нећу издвојити то. Тако да на тај начин он или она има флексибилност у продавнице студентских резултата, као 75, 90, и можда један екстра где студент добио додатне поене, 105. 

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

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

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

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

Затим неколико недеља касније кад добијем други квиз, и да је време да куцате У том 90%, идем то аск рачунар, хеј, рачунар, могу ли добити још једну комад меморије? То ће ми дати ово празан комад меморије. Ја ћу ставити у броју 90, али у свом програму некако или отхер-- и нећемо бринути о синтакса на овоме-- ми треба некако везати ове ствари заједно. И ја ћу их ланце заједно са оно што изгледа као стрела овде. 

Трећи квиз да се појави, Ја ћу рећи, хеј, рачунар, дај ми још једну меморију. И ја ћу спустити шта год да је, као 75, и морам да ланац овом заједно сада некако. Четврто квиз дође, и можда То је крајем семестра. И тада ми је програм можда користи меморију свуда, свуда физички. И тако за сваки случај, ја сам намеру да ово напред куиз-- сам заборавити шта је било; ја да је можда од 80 или нешто-- начин овде. 

Али то је у реду, јер сликовито Ја ћу повући ову линију. Другим речима, у стварности, у хардверу рачунара, први резултат могао завршити овде јер је Право на почетку семестра. Следећег би се могло завршити овде јер мало је времена прошло и програм наставља да тече. Следећи резултат, што је од 75, можда овде. А последњи резултат може бити од 80, која је овде. 

Дакле, у стварности, физички, ово може бити шта меморије рачунара изгледа. Али ово није корисна ментална парадигма за компјутерски програмер. Зашто би требало да занима где је врага ти подаци се не заврши? Желите само за складиштење података. 

Ово је нешто попут нашег разговора раније цртања коцку. Шта тебе брига шта је угао коцке и како да се окренемо се извући? Желите само коцку. Слично томе овде, ти Само желим да граде књизи. Ти само желиш да мислим о ово као листу бројева. Кога брига како је то имплементира у хардверу? 

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

Нула, један, два, три, четири, пет, шест, седам. Изгледа да је 90 је у меморија адреса број седам. Све ове стрелице су је као мала комад папира који даје упутства до Програм који каже да прате ову карту да се на локацију седам. И тамо ћете наћи студента други квиз резултат. У међувремену, 75-- ако наставим ово, ово је седам, осам, девет, 10, 11, 12, 13, 14, 15. 

Овај други стрелица само представља мапа на меморијској локацији 15. Али опет, програмер уопште не није стало до овог нивоа детаља. И у већини сваком програму језика данас, програмер неће ни знати где у меморији ови бројеви заправо. Све он или она мора да брине само о да су некако повезани у структури података као што је овај. 

Али испоставило се да није да се превише технички. Али само зато што можемо можда приуштити да имају ову дискусију овде, Претпостављам да смо поново ово питање овде од низа. Хајде да видимо да ли жалим иде овде. Ово је 100, 90, 75, и 80. 

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

И тако са низом, имате карактеристика позната као случајним приступом. А шта директног приступа средствима је да рачунар може да скочи одмах на било којој локацији у низу. Зашто? Јер компјутер зна да је прва локација нула, један, два и три. 

Па ако желим да идем из овај елемент на следећи елемент, Ви буквално, у рачунара ум, само додајте једну. Ако желите да одете на трећи елемент, само додајте једног-- следећег елемента, само додате. Међутим, у овој верзији приче, претпостављам рачунар тренутно тражи у или се баве бројем 100. Како добити на следећи разред у разреду књизи? 

Морате узети седам кораци, који је произвољан. Да се ​​на следећи, морате да потребно још осам корака да се до 15. Другим речима, то није константа јаз између бројева, и тако то само узима рачунар више времена је поента. Рачунар мора да тражи кроз сећања како би да пронађете оно што тражите. 

Према томе, док низ има тенденцију да буде брзо подаци струцтуре-- јер тебе могу буквално само до простом математиком и одвести тамо где желите додавањем једног, за инстанце-- повезану листу, ви жртвовати ту особину. Не можете само да од првог на други на трећем у четврти. Морате да пратите мапу. Морате узети више корака доћи до тих вредности, које изгледа да се додавањем трошкова. Дакле, ми плаћамо цену, али оно што је било функција која Дан је тражи овде? Шта повезану листу очигледно нам омогућити да радимо, што је порекло ова прича? 

Баш тако. Динамичка величина у томе. Можемо додати овој листи. Чак можемо смањити листу, тако да смо само користи више меморије као што заправо желимо и тако никада нисмо превише алокацију. 

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

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

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

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

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

Дакле, поново, то је ово балансирање покушавају да одлуче која од тих ствари да ли сте спремни да потрошите? Који је најјефтинији? Који се добијају бољи резултати? Да? 

Заиста. У том случају, ако сте представља бројеве у мапс-- то се зове на многим језицима "показивачи" или "адресе" - то је двоструко више простора. То не мора да буде тако лоше као двоструки да сада смо само чување бројева. Претпоставимо да смо складиштење записа о пацијентима ин а хоспитал-- па Пирсон је имена, телефонске бројеве, бројеви социјалног осигурања, лекар историја. Ова кутија могла да буде много, много већи, у ком случају мали мали показивач, адреса следећи елемент-- то није велика ствар. То је тако крилни коштати није битно. Али у овом случају, да, то је дуплирање. Добро питање. 

Хајде да причамо о времену а мало конкретније. Шта је покренут време трагања ову листу? Претпоставимо да сам хтео да претражите кроз све оцена студената, и ту је н оцене У овом података структури. Овде, такође, можемо да позајмимо вокабулар раније. Ово је линеарна структура података. 

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

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

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

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

Умјесто тога, можда паметнији приступ је да се стави јабуку у свом чвору или кутији, као што би рекли, банане, и онда овде имамо диња. И ми смо низ заједно ове ствари. Дакле, ово је низ, и ово је листа повезана. Ако не могу да видим, то само каже "низ", а овај каже "листу." 

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

Тако да можемо имати најбоље од оба света? И заиста, постоји нешто назива хасх табела који вам омогућава да тачно урадити да, иако отприлике. Хеш табела је одгајивач структура података које смо могу да замислим како је Комбинација арраи-- и ја ћу га извући овако-- и повезаних листи да ћу извући овако овде. 

И начин на који ово Радови је следећи. Ако је ово сада-- хасх табле-- ми је трећа структура података, и ја желите да сачувате речи у овој, не знам Желим да само чување свих речи бацк то бацк то бацк то бацк. Желим да искористе неки податак о речима које ће омогућавају ми да га где је брже. 

Дакле, имајући у виду речи јабуку и банана и диња, Намерно сам изабрао те речи. Зашто? Шта је нека врста основи различито о три? Шта је очигледно? Почну са различитим словима. 

Дакле, знате шта? Уместо да стави све моје речи иста кофа, да тако кажем, као у једној великој листи, зашто не Ја барем покушати оптимизацију и да моје листе 1/26 докле год. Убедљив оптимизација можда зашто не Ја када уметања речи у овом података структуру, у меморију рачунара, зашто не би дала све 'А' речи овде, сви 'Б' речи овде, и све 'Ц' речи овде? Дакле, ово завршава стављање јабуку овде, банане овде, диња овде, и тако даље. 

И ако имам додатних Реч као-- шта је друго? Јабука, банана, крушка. Свако мисли на воће који почиње са, Б или Ц? Блуеберри-- савршен. То ће завршити овде. Па изгледа да имамо незнатно боље решење, јер сада ако желим да тражи јабуке, ја фирст-- не знам само диве у мом структуре података. Ја не роним у меморију мог рачунара. Ја први поглед на првом слову. 

И то је оно што рачунара научник би рекао. Ви хасх у својој структури података. Узмеш унос, који у овај случај је реч попут јабука. Га анализирају, гледајући прво слово у овом случају, чиме је хасхинг. Хеаирање је општи термин којим узмете нешто као улаз и произведе неки излаз. И излаз у томе Случај је локација желите да претражите, први локација, друга локација, трећи. Дакле, улаз је јабука, излаз је први. Улаз је Банана, тхе излаз би требао бити други. Улаз је диња, излаз би требао бити трећи. Улаз је боровница је излаз би требао поново бити други. И то је оно што помаже да се пречица до вашег сећања како би дошли до речи или подаци ефикасније. 

Сада то смањује наше време потенцијално чак и једно од укупно 26, јер ако претпоставимо да ти имају што више "а" речи као "з" речи као "К" речи, које није баш реалистиц-- ћеш имати скев преко поједини слова у алпхабет-- али то би био постепен приступ који допушта да дођете до речи много брже. А у стварности, софистицирани програм, Наочаре света, Фацебоокс од ворлд-- они ће користити хасх табелу за многе различите намене. Али они не би били толико наивни само да погледамо прво слово јабуке или банане или крушка или диња, јер као што видите ово Листе ипак могао дуго. 

И то можда још врста од линеар-- тако некако споро, као и са великим О од н да смо разговарали раније. Дакле, шта је стварно добар хеш сто це урадиш-- да ће имати много већи низ. И то ће користити много софистициран функција хеширање, тако да то није само погледате "А". Можда то изгледа на "А-п-П-Л-Е" и некако претвара тих пет слова на место где јабука треба чувати. Ми смо само наивно користе слово 'А' сама, јер је лепо и једноставно. 

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

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

Има ли питања о овим? Не? У реду. Па, зашто не бисмо застати, старт ручак неколико минута раније, наставити у само око сат времена? А ја ћу задржавају за мало са питањима. Онда ћу морати да иде узети пар позива ако је то у реду. Ја ћу окренути на неку музику у међувремену, али ручак би требало да буде иза угла.