DAVID Малання: Добра. Мы вярнуліся. Так што ў гэтым сегменце па праграмаванні, што Я думаў, што мы робім гэта спалучэнне рэчаў. Па-першае, зрабіць трохі пра што-то рукі-на, хоць і з выкарыстаннем больш гуллівы праграмаванне environment-- той, які з'яўляецца паказальным з менавіта тыя віды ідэй мы гаворым пра тое, але трохі больш фармальна. Па-другое, паглядзіце на некаторыя з тым больш тэхнічныя спосабы што праграміст будзе на самой справе вырашыць Праблемы, як у пошуках праблемы што мы разгледзелі да і таксама больш фундаментальна цікавая праблема сартавання. 

Мы толькі выказаў здагадку, што з самага пачатку ісці што гэтая тэлефонная кніга сартавалі, але гэта само па сабе на самай справе добры з складаная праблема з многімі рознымі спосабамі каб вырашыць гэтую праблему. Такім чынам, мы будзем выкарыстоўваць іх як клас задач прадстаўнік рэчаў, можа быць вырашана ў цэлым. І тады мы будзем казаць аб у некаторых дэталях, што называюцца дадзеныя structures-- мудрагелістыя спосабы, як звязаныя спісы і хэш-табліцы і дрэвы, праграміст будзе на самой справе выкарыстоўваць і як правіла, выкарыстоўваюць на дошцы маляваць карціна таго, што ён ці яна прадугледжвае для рэалізацыі некаторыя часткі праграмнага забеспячэння. 

Так што давайце рабіць практычны частцы першай. Так што проста атрымаць вашыя рукі брудныя з навакольнае асяроддзе называецца scratch.mit.edu. Гэта інструмент, які мы выкарыстоўваем у нашым універсітэцкім класе. Нягледзячы на ​​тое, што ён прызначаны для асоб да 12 гадоў і старэй, мы выкарыстоўваем яго для уверх частка гэтага зусім няшмат так як гэта прыемна, весела Графічны спосаб навучання сёе-тое пра праграмаванні. Так ажно да гэтага URL, дзе вы павінны ўбачыць старонку зусім так, і ісці наперад і націсніце Далучайцеся да драпін ў верхнім правым куце і выберыце імя карыстальніка і пароль і ў канчатковым выніку атрымаць сабе account-- scratch.mit.edu. Я думаў, што выкарыстоўваць гэта як магчымасць упершыню паказаць гэта. Пытанне падышоў падчас перапынку аб тым, што код на самай справе выглядае. І мы казалі падчас перапынку аб З, у прыватнасці particular-- больш нізкі ўзровень у больш старым мове. І я проста зрабіў хуткі Google пошук, каб знайсці код C для двайковага пошуку, алгарытм, які мы выкарыстоўваецца для пошуку гэтай тэлефоннай кнігі раней. Гэты канкрэтны прыклад, вядома ж, ня шукае тэлефонную кнігу. Ён проста шукае цэлую кучу Чысла ў памяці кампутара. Але калі вы хочаце, каб проста атрымаць візуальнае адчуванне таго, што фактычнае праграмаванне мова выглядае, гэта выглядае трохі нешта накшталт гэтага. Так што гаворка ідзе пра 20-плюс, 30 або каля таго радкоў кода, але размова мы мелі больш перапынку быў пра тое, як гэта на самай справе атрымлівае трансфармавалася ў нулёў і адзінак і калі вы не можаце проста вярнуцца, што апрацоўваць і ідуць ад нулёў і адзінак назад у код. 

На жаль, працэс настолькі преобразовательных што гэта нашмат лягчэй сказаць, чым зрабіць. Я пайшоў наперад і на самай справе аказалася што праграма, бінарны пошук, ў нулі і адзінкі ў форме далучэння Праграма пад назвай кампілятар, што я здараецца, ёсць тут прама на маім Mac. І калі вы паглядзіце на экран тут, звярнуўшы асаблівую ўвагу на гэтых сярэдніх шасці калон толькі, вы ўбачыце толькі нулі і адзінкі. І тыя нулі і адзінкі, якія скласці менавіта гэтую праграму пошуку. 

І так кожны кавалак пяць бітаў, кожны байт нулёў і адзінак тут, ўяўляюць некаторую інструкцыю як правіла, ўнутры кампутара. І на самай справе, калі вы чулі рэкламны слоган "Intel усярэдзіне" - гэта, вядома, проста азначае, што ў вас ёсць Intel CPU або мозг ўнутры кампутара. І што гэта значыць быць працэсар што ў вас ёсць набор інструкцый, так бы мовіць. 

Кожны працэсар у свеце, многія з яны зроблены Intel у гэтыя дні, разумее канчатковае колькасць інструкцый. І гэтыя інструкцыі настолькі нізкі ўзровень , Як дадаць гэтыя два ліку разам, перамнажаць гэтыя два ліку разам, перамясціць гэтую частку дадзеных тут каб тут, у памяці, захаваць гэты інфармацыя адсюль тут, у памяці, і так forth-- вельмі, вельмі нізкага ўзроўню, амаль электронныя дэталі. Але з тымі, матэматычная аперацыі ў спалучэнні з тым, што мы абмяркоўвалі раней, прадстаўленне даных як нулі і адзінкі, могуць Вы сформируете ўсе што кампутар можа зрабіць сёння, няхай гэта будзе гэта тэкставае, графічнае, музычнае, ці іншым чынам. 

Так што гэта вельмі лёгка атрымаць страцілі ў пустазелля хутка. І ёсць шмат сінтаксічныя праблемы прычым, калі вы зробіце самы просты, дурное памылак друку ніхто з праграмы будзе працаваць наогул. І таму замест таго, каб выкарыстоўваць мова, як C гэтай раніцай, Я думаў, што гэта было б больш задавальнення на самай справе рабіць нешта большае, візуальнае ўспрыманне, у той час як прызначаныя для дзяцей на самай справе з'яўляецца дасканалым праявай фактычнага праграмавання language-- як раз здараецца выкарыстоўваць выявы замест тэксту каб прадставіць гэтыя ідэі. 

Таму, як толькі вы на самой справе мець кошт на scratch.mit.edu, націсніце кнопку Стварыць у левым верхнім куце сайта. І вы павінны ўбачыць навакольнае асяроддзе як адзін я збіраюся бачыць на маім экране тут. І мы выдаткуем трохі крыху часу, гуляючы тут. Давайце паглядзім, калі мы не можам усё вырашыць некаторыя праблемы разам наступным чынам. 

Так што вы ўбачыце ў гэтым environment-- і на самай справе проста дайце мне паўзу. Хто-небудзь не тут? Ня тут? ДОБРА. Такім чынам, дазвольце мне адзначыць некалькі Характарыстыкі гэтага асяроддзя. 

Такім чынам, у верхнім левым куце экрана, мы існуе ўзровень чыстага ліста, так бы мовіць. Драпіны не толькі імя гэтай мовы праграмавання; гэта таксама імя ката, вы бачыце, прадвызначана там у аранжавы колер. Ён знаходзіцца на сцэне, так гэтак жа, як я апісаў чарапаха раней як у прастакутная белая дошка навакольнае асяроддзе. Свет гэтай кошкі абмяжоўваецца выключна на гэты прастакутнік наверсе там. 

У той жа час, справа правая частка тут, гэта толькі вобласць скрыпты, чыстага ліста, калі вы будзеце. Менавіта тут мы будзем пісаць нашы праграмы ў імгненне. І будаўнічыя блокі, якія мы выкарыстоўваць, каб напісаць гэта program-- галаваломкі штук, калі вы will-- з'яўляюцца тыя, прама тут, у цэнтры, і яны класіфікуюцца па функцыянальнасці. Так, напрыклад, я збіраюся ісці наперад і прадэманстраваць, па меншай меры, адзін з іх. Я збіраюся ісці наперад і націсніце катэгорыя кіравання наверсе. 

Так што гэтыя катэгорыі да вяршыні. Я збіраюся націснуць катэгорыю кіравання. Хутчэй за ўсё, я буду націскаць на падзеі катэгорыя, самы першы наверсе. І калі вы хочаце прытрымлівацца нават як мы робім гэта, вы вельмі дабро запрашаем. Я збіраюся націснуць і перацягнуць гэты Першы з іх, "калі зялёны сцяг пстрыкнуў". А потым я збіраюся кінуць яго проста прыкладна ў верхняй частцы маіх пустых сланцы. 

І што прыемна аб пустым месцы з'яўляецца тое, што гэты кавалак галаваломкі, калі узаемазьвязаны з другога галаваломкі штук, збіраецца зрабіць літаральна што гэтыя кавалачкі галаваломкі кажуць рабіць. Так, напрыклад, Драпіны правоў цяпер у сярэдзіне свайго свету. Я збіраюся ісці наперад і выбраць Цяпер, скажам, катэгорыя руху, калі вы хочаце зрабіць same-- катэгорыі руху. А цяпер звярніце ўвагу ў мяне ёсць цэлы куча галаваломкі тут што, зноў жа, рабіць выгляд, што яны гавораць. І я збіраюся ісці наперад і перацягнуць выпусціць блок рухацца прама тут. 

І да вашага ведама, што, як толькі вы атрымаеце блізка да ніжняй часткі "зялёны сцяг націснуў "кнопку, апавяшчэнне як з'яўляецца белая лінія, як быццам гэта амаль магнітныя, ён хоча паехаць туды. Проста адпусціць, і ён будзе хапаць разам і формы будуць супадаць. І цяпер вы можаце, магчыма, амаль адгадаць, дзе мы збіраемся з гэтым. 

Калі вы паглядзіце на сцэну Скрэтч тут і глядзець у верхняй часткі яго, вы ўбачыце чырвонае святло, знак прыпынку, і зялёны сцяг. І я збіраюся ісці наперад і глядзець мае screen-- на імгненне, калі б вы маглі. Я збіраюся націснуць зялёны сцяг прама цяпер, і ён пераехаў, што, як уяўляецца, 10 крокаў або 10 пікселяў, 10 кропак, на экране. 

І так не так цікава, але дазвольце мне прапанаваць нават не вучыў гэтаму, проста выкарыстоўваючы свой уласны intuition-- хай я прапаную вам высветліць, як зрабіць Драпіны шпацыр прама са сцэны. Ці былі яму зрабіць шлях для правага боку экран, ўвесь шлях направа. Дазвольце мне даць вам момант або так, каб змагацца з гэтым. Вы можаце захацець зірнуць на іншыя катэгорыі блокаў. Добра. Так што проста рэзюмаваць, калі мы маем зялёны сьцяг націснуўшы тут і рухацца 10 крокаў з'яўляецца толькі інструкцыя, кожны раз, калі я націсніце зялёны сцяг, што адбываецца? Ну, гэта працуе мая праграма. Так што я мог бы зрабіць гэта можа быць у 10 разоў ўручную, але гэта адчувае сябе крыху трохі Хакам, так бы мовіць, у выніку чаго я на самой справе не рашэнне праблемы. Я проста спрабую зноў і зноў і зноў і зноў пакуль я накшталт выпадкова дасягнуць дырэктывы што я меў намер дасягнуць раней. 

Але мы ведаем з нашага псевдокод раней, што ёсць гэта паняцце ў праграмаванні зацыкленне, рабіць нешта зноў і зноў. І вось я ўбачыў, што звязак з вас пацягнуўся за тое, што кавалак галаваломкі? Паўтарайце датуль. Такім чынам, мы маглі б зрабіць нешта як паўтараць да. І не тое, што вы паўтарыць, пакуль дакладна? 

ДОБРА. І дазвольце мне пайсці з той, які некалькі прасцей за ўсё на імгненне. Дазвольце мне ісці наперад і рабіць гэта. Звярніце ўвагу на тое, што, як вы, магчыма, выявіў пад кантролем, ёсць гэты паўтор блок, які не выглядае, як быццам гэта што вялікі. Там не так шмат месца ў паміж гэтымі двума жоўтымі лініямі. Але так як некаторыя з вас, магчыма, заўважылі, калі вы перацягнуць, звярніце ўвагу, як ён расце, каб запоўніць форму. 

І вы можаце нават ўціснуць больш. Гэта будзе проста працягваць расці, калі перацягванні і парыць над ім. І я не ведаю, што гэта лепш за ўсё тут, так што давайце мне прынамсі паўтарыць пяць разоў, для асобнік, а затым вярнуцца на сцэну і націсніце на зялёны сьцяг. А цяпер звярніце ўвагу, што гэта не зусім там. 

Цяпер некаторыя з вас прапанавалі ў якасці Вікторыя проста, паўторыце 10 разоў. І што ўвогуле робіць атрымаць яго ўвесь шлях, Але хіба не было б больш надзейным спосаб, чым адвольна высветліць, колькі хадоў зрабіць? Што можа быць лепш блок чым паўтарыць 10 разоў быць? 

Ды, дык чаму б не зрабіць нешта назаўжды? А цяпер дазвольце мне перанесці гэты кавалак галаваломкі ўнутры там, і пазбавіцца ад гэтага. Зараз звернеце ўвагу незалежна ад таго, дзе драпіна пачынаецца, ён ідзе да краю. І на шчасце MIT, які робіць нуля, проста не гарантуе, што ён ніколі цалкам знікае. Вы заўсёды можаце схапіць яго за хвост. 

І сапраўды гэтак жа інтуітыўна, Чаму ён працягвае рухацца? Што ж тут адбываецца? Ён, здаецца, спынілася, але а затым, калі я падымаю і перацягнуць ён працягвае хацець ісці туды. Чаму гэта? Сапраўды, кампутар літаральна збіраецца рабіць тое, што вы скажаце ёй зрабіць. Так што, калі вы сказалі гэта раней зрабіць наступная рэч назаўжды, рухацца 10 крокаў, гэта будзе працягваць ісці і ісці пакуль я не ўдарыў чырвоны знак стоп і спыніць праграму ў цэлым. 

Так што нават калі вы гэтага не зрабілі зрабіць гэта, як я мог зрабіць Драпіны рухацца хутчэй па экране? Іншыя крокі, ці не так? Такім чынам, замест таго, каб рабіць 10 у той час, чаму б нам не ісці наперад і змяніць яго, мэтай якіх што б вы propose-- 50? Так што цяпер я збіраюся націснуць зялёны сцяг, і на самай справе, ён ідзе вельмі хутка. 

І гэта, вядома ж, гэта проста праява анімацыі. Што такое анімацыя? Гэта проста паказвае вам чалавека A цэлая куча нерухомых малюнкаў на самай справе, на самай справе, вельмі хутка. І таму, калі мы проста распавядаю яму рухацца больш крокаў, мы проста маючы эфект быць змена, дзе ён знаходзіцца на экране ўсё больш хутка за адзінку часу. 

Цяпер наступны выклік, які я прапанаваў павінен быў мець яго адскокваюць ад краю. І не ведаючы, што галаваломкі штук exist--, таму што гэта нармальна калі вы не дабрацца да этап challenge--, што вы хочаце зрабіць інтуітыўна? Як бы мы яго адскочыць назад і наперад, паміж левым і правым? 

Так. Так што нам трэба нейкі стану, і мы як уяўляецца, маюць умоўнымі, так кажуць, пад катэгорыю кіравання. Які з гэтых блокаў мы, верагодна, хочаце? Так, магчыма, "калі, то". Так заўважыць, што сярод жоўтых блокаў мы маем тут, значыць гэта "калі" ці гэта ", калі яшчэ" блок, які будзе дазваляюць нам прыняць рашэнне, каб зрабіць гэта або зрабіць гэта. І вы нават можаце іх гняздо зрабіць некалькі рэчаў. Ці, калі вы не прайшлі яшчэ тут, ісці наперад да катэгорыі Sensing и-- давайце паглядзім, калі ён тут. 

Так што блок можа быць карысным тут каб выявіць, калі ён са сцэны? Так, звярніце ўвагу, што некаторыя з гэтых блокаў могуць быць параметризованы, калі можна так выказацца. Яны могуць быць настроены роду, а не У адрозненне ад HTML ўчора з атрыбутамі, дзе гэтыя атрыбуты роду наладзіць паводзіны тэга. Сапраўды гэтак жа тут, я магу захапіць гэты кранальны блок і змяніць і задаць пытанне, вы дакранаючыся мышшу паказальнік, як курсор ці вы дакрануўшыся да краю? 

Такім чынам, дазвольце мне пайсці і зрабіць гэта. Я збіраюся паменшыць на імгненне. Дазвольце мне захапіць гэты кавалак галаваломкі тут, гэта кавалак галаваломкі гэта, і я збіраюся змешваць яны на імгненне. Я буду рухацца ў гэтым, змяніць гэта кранальнай край, і я збіраюся зрабіць гэта рух. Дык вось некаторыя інгрэдыенты. Я думаю, што ў мяне ёсць усё, што захачу. 

хто-то хацеў бы прапанаваць, як я можа злучыць іх, можа быць, зверху ўніз для таго, каб вырашыць праблему наяўнасці Драпіна рух справа налева направа злева направа, налева, кожны Час якраз адлюстроўваючыся ад сцяны? Што я хачу зрабіць? Які блок я павінен падлучыцца да "Калі зялёны сцяг пстрыкнуў першы"? 

ОК, так што давайце пачнем з «назаўжды». Тое, што адбываецца ўнутры далей? Нехта яшчэ. OK, рухацца крокі. Добра. Тады што? Так то калі. І да вашага ведама, нават калі гэта выглядае заціснутай разам шчыльна, ён проста будзе расці, каб запоўніць. Гэта будзе проста скакаць у тым, дзе я хачу. 

І што ж я стаўлю паміж ІФ і тады? Магчыма ", калі вы датыкаецеся край». І заўважце, зноў жа, гэта занадта вялікі для яе, але яна будзе расці, каб запоўніць. А затым павярнуць на 15 градусаў? Колькі градусаў? Так, так што 180 будзе круціцца мяне ўсё наадварот. Такім чынам, давайце паглядзім, калі я атрымаў гэта права. Дазвольце мне паменшыць малюнак. 

Дазвольце мне перацягнуць наскрэбці. Такім чынам, ён трохі скажаецца зараз, але гэта нармальна. Як я магу скінуць яго лёгка? Я збіраюся трохі падмануць. Такім чынам, я дадаў яшчэ адзін блок, проста каб быць ясным. Я хачу, каб ён паказвае на 90 градусаў направа па змаўчанні, так што я проста хачу, каб сказаць яму, зрабіць гэта праграмна. І тут мы ідзем. Мы, здаецца, зрабілі гэта. Гэта крыху дзіўна, таму што ён ідзе з ног на галаву. Давайце назавем, што памылка. Гэта памылка. Выпраўленая памылка, памылка ў праграме, а лагічная памылка, што я, чалавек, зрабіў. Чаму ён збіраецца з ног на галаву? Апынулася MIT зашрубаваць ці я? 

Так, я маю на ўвазе, гэта не ў MIT няспраўнасць. Яны далі мне кавалак галаваломкі што кажа павярнуць некаторы колькасць градусаў. І па прапанове Вікторыі, Я ператвараюся на 180 градусаў, які з'яўляецца правільным інтуіцыя. Але паварот на 180 градусаў у літаральным сэнсе азначае паварот на 180 градусаў, і гэта на самай справе не што я хачу, па-відаць. Таму што, па меншай меры, ён у гэта двухмерная свет, так што паварот сапраўды адбываецца каб перавярнуць яго з ног на галаву. 

Я, верагодна, хочаце, каб выкарыстаць тое, што блок замест таго, каб, грунтуючыся на тое, што вы бачыце тут? Як мы можам гэта выправіць? Так, такім чынам, мы маглі б пазначыць у процілеглым кірунку. І на самай справе нават гэта не будзе дастаткова, таму што мы можам толькі жорсткі код каб паказваць налева або направа. 

Вы ведаеце, што мы можам зрабіць? Падобна на тое, што ў нас ёсць зручны блок тут. Калі я набліжаць см тое, што мы, як тут? Так гэта выглядае, як MIT мае абстракцыя пабудавана тут. Гэты блок ўяўляецца эквівалентным да якіх іншыя блокі, множны лік? 

Гэты блок ўяўляецца эквівалентным да ўсёй гэтай тройцы блокаў што мы маем тут. Так атрымліваецца, што я магу спрасціць сваю Праграма, пазбавіўшыся ад усяго гэтага і проста паставіць гэта тут. А цяпер ён яшчэ трохі глючыць, і гэта нармальна цяпер. Мы пакінем гэта будзе. Але мая праграма нават прасцей, і гэта таксама, будзе прадстаўнік галы ў programming-- гэта ў ідэале зрабіць свой код, проста, як мага больш кампактным, у той жа час, як чытаным, наколькі гэта магчыма. Вы не хочаце, каб зрабіць гэта так лаканічны што гэта цяжка зразумець. 

Але зьвярніце ўвагу, я замяніў тры блокі з адным, і гэта, магчыма, добрая рэч. Я абстрагуюцца паняцце праверкі, з'яўляецеся Ці Вы на краі з дапамогай толькі аднаго блока. Цяпер мы можам атрымліваць задавальненне з гэтым, на самой справе. Гэта не дадае столькі інтэлектуальныя каштоўнасці, але гуллівая значэнне. Я збіраюся ісці наперад і захапіць гэты гук тут. Такім чынам, дазвольце мне ісці наперад, і хай мяне спыніць праграму на імгненне. Я збіраюся запісаць наступнае, забяспечваючы доступ да майго мікрафону. 

Тут мы ідзем. Нав. Давайце паспрабуем гэта зноў. Тут мы ідзем. ОК, я запісаў няправільныя рэчы. Тут мы ідзем. Нав. Нав. Добра. Цяпер мне трэба, каб пазбавіцца ад гэтага. Добра. 

Так што цяпер у мяне ёсць Запіс толькі "Ой". Так што цяпер я збіраюся пайсці наперад і называем гэта "Уч." Я збіраюся вярнуцца для маіх сцэнарыяў, і цяпер паведамленьне ёсць гэты блок, які называецца гуляць гук "мяу" або прайграваць гук "Уч." Я збіраюся цягнуць гэта, і дзе я павінен паставіць гэта на камічны эфект? Так, так што цяпер гэта свайго роду глючыць, таму што цяпер гэта block-- звярніце ўвагу, як гэта ", калі на краі, адскоку "з'яўляецца свайго роду самадастатковым. Таму мне трэба, каб выправіць гэта. Дазвольце мне ісці наперад і рабіць гэта. Дазвольце мне пазбавіцца ад гэтага і вярнуцца да нашага першапачатковага, больш наўмысным функцыянальнасць. Так што "калі вы датыкаецеся край, а затым" Я хачу павярнуць, як гэта было прапанавана Вікторыя, На 180 градусаў. І я хачу, каб гуляць гук "Уч" ёсць? 

Так, звярніце ўвагу, што гэта за межамі што жоўты блок. Так што гэта таксама быў бы памылка, але я заўважыў гэта. Так што я збіраюся цягнуць яго сюды, і заўважце, цяпер гэта ўнутры «калі». Так што "калі" гэта свайго роду аднайменных рукі, як блоттинга што толькі збіраецца рабіць тое, што ўнутры яго. Так што цяпер, калі я аддаліць ў рызыка annoying-- 

КАМПУТАР: Ой, ой, ой. 

DAVID Малання: І будзе проста працягвацца вечна. Цяпер проста паскорыць рэчы тут, дазвольце мне ісці наперад і адкрыць, давайце say-- адпусціць мяне ў нейкі майго ўласнага матэрыялу ад класа. І дазвольце мне адкрыць, скажам, гэта адзін зроблены адным з нашых навучальных таварышаў пару гадоў таму. Так што некаторыя з вас могуць успомніць гэтая гульня ад мінулых гадоў, і гэта на самай справе выдатна. Нягледзячы на ​​тое, што мы зрабілі Найпростым праграм прама цяпер, давайце разгледзім, што гэта на самай справе выглядае. Дазвольце мне ударыў гуляць. 

Так што ў гэтай гульні, у нас ёсць жабы, і з дапамогай стрэлкі keys-- ён прымае вялікія крокі, чым я remember-- У мяне ёсць кантроль над гэтай жабы. І мэта складаецца ў тым, каб атрымаць праз заняты Дарога без запуску ў аўтамабілях. І давайце see--, калі я іду тут, я прыйдзецца чакаць, пакуль часопіс для пракруткі па. Гэта адчувае, як памылка. Гэта свайго роду памылка. Добра. Я на гэта тут, там, а затым вы трымаеце ісці, пакуль не атрымаеце ўсе жабы ў гарлачыкаў. Зараз гэта можа выглядаць ўсё больш складанымі, але давайце паспрабуем разбіць гэта ўніз думках і вусна на складовыя блокі. Так што, верагодна, галаваломка частка, якую мы яшчэ не бачылі але гэта рэагуе на націск клавіш, да рэчаў, я ўдарыў па клавіятуры. 

Так што там, напэўна, нейкая блок, які кажа, калі ключ роўны ўверх, затым зрабіць што-то з Scratch-- Немагчыма перанесьці яго 10 крокаў такім чынам. Калі ўніз клавіша націснутая, рухацца 10 крокаў такім чынам, ці левая клавіша, рухацца 10 крокаў Такім чынам, 10 крокаў, якія. Я выразна павярнуў котку ў жабу. Дык вось менавіта там, дзе касцюм, як чарнавік званкі it-- мы толькі што імпартавалі карціну жабы. 

Але што яшчэ адбываецца? Якія іншыя радкі кода, што іншыя галаваломкі зрабіў Блэйк, наша вучэнне супрацоўнік, выкарыстоўваць у гэтай праграме, па-відаць? Што робіць усё move-- тое, што праграмаванне пабудаваць? 

Motion, sure-- так перамясціць блок, напэўна. І тое, што гэты крок блок ўнутры, хутчэй за ўсё? Так, нейкі цыкл, можа быць, назаўжды заблакаваць, магчыма паўтарэнне block-- паўтараць да блока. І вось што робіць часопісы і гарлачыкаў і ўсё астатняе рух туды-сюды. Гэта проста адбываецца бясконца. 

Чаму некаторыя з аўтамабіляў рухацца хутчэй, чым іншыя? Што адрознівае гэтых праграм? Ды, верагодна, некаторыя з іх прымаюць больш крокаў адразу і некаторыя з іх менш крокаў адразу. І візуальны эфект вельмі хутка ў параўнанні з павольным. 

Як вы думаеце, што здарылася? Калі я атрымаў маю жабу ўвесь шлях праз дарогу і раку на лілеі пляцоўку, нешта Характэрна, адбылося. Тое, што адбылося, як толькі я зрабіў гэта? Яна спынілася. Гэтая жаба спынілася, і Я атрымаў другую жабу. Так што канструкцыя павінна быць выкарыстоўваецца там, якая функцыя? 

Так, так што ёсць нейкая "Калі" стан там, таксама. І атрымліваецца out-- мы не ўбачылі this-- але ёсць і іншыя блокі там Можна сказаць, калі вы датыкаецеся Іншая справа, на экране, калі вы датыкаючыся да гарлачыка ", а затым". І тады, калі мы зрабіць другі жабы з'яўляюцца. Так што, хоць гэтая гульня, безумоўна, вельмі састарэлі, хоць на першы погляд ёсць так шмат адбываецца on-- і Блэйк ня хвастаць гэта ў дзве хвіліны, ён, верагодна, узяў яго некалькі гадзін, каб стварыць гэтую гульню заснаваны на яго памяці або відэа версіі учорашняга дня пра яго. Але ўсе гэтыя дробязі адбываецца на экране ў ізаляцыі зводзяцца да іх вельмі проста constructs-- руху або заявы як мы ўжо абмяркоўвалі, завесы і ўмовы, і менавіта пра гэта. Там у некалькі іншых асаблівасцяў аматар. Некаторыя з іх з'яўляюцца чыста эстэтычныя або акустычныя, як гукі я проста гуляў. Але па большай частцы, вы ёсць у гэтай мове, на пустым месцы, усе фундаментальныя будаўнічыя блокі, якія вам ёсць у C, Java, JavaScript, PHP, Ruby, Python, і любую колькасць іншых моў. Любыя пытанні на пустым месцы? Добра. Таму мы не будзем апускацца глыбей падрапаць, хоць вы заўсёды можаце ў гэтыя выхадныя, асабліва калі ў вас ёсць дзеці ці пляменніцы і пляменнікі і такія, пазнаёміць іх з нуля. Гэта на самай справе дзіўна гуллівы серада з, як кажуць яго аўтары, вельмі высокія столі. Нягледзячы на ​​тое, што мы пачалі з вельмі нізкаўзроўневых дэталяў, вы сапраўды можаце зрабіць зусім трохі з ім, і гэта, мабыць, дэманстрацыя менавіта гэта. 

Але давайце цяпер перайсці да некаторых больш складаныя праблемы, калі вы будзеце, вядомы як "пошук" і "Сартаванне" у больш агульным плане. У нас была гэтая тэлефонная кніга earlier-- тут яшчэ адзін раз для discussion-- што мы змаглі знайсці больш эфектыўна, таму што значнага здагадкі. І проста быць зразумела, што Меркавалася, што робіць я пры пошуку праз гэтую тэлефонную кнігу? Гэта Майк Сміт быў у тэлефонная кніга, хоць я будзе мець магчымасць апрацоўваць сцэнар без яго там, калі я проста спыніўся заўчасна. Кніга ў алфавітным парадку. І гэта вельмі шчодры здагадка, таму што азначае someone-- Я накшталт рэзкі кут, як я хутчэй, таму што хто-то яшчэ зрабіў шмат цяжкай працы для мяне. 

Але што, калі тэлефон Кніга была малокомплектных? Можа быць, Verizon стаў лянівы, проста кінуў імёны і нумары кожнага ў там можа быць, у тым парадку, у якім яны падпісаўся на тэлефон службы. А колькі часу займае мяне каб знайсці каго-то накшталт Майка Сміта? 1000 старонак тэлефон book-- колькі старонкі я павінен паглядзець? 

Усе яны. Ты вроде не пашанцавала. Вы літаральна павінны глядзець на кожны старонка, калі тэлефонная кніга проста выпадковым чынам сартуюцца. Вы можаце атрымаць пашанцавала і знайсці Mike на самай першай старонцы, таму што ён быў першым заказчыкам замовіць паслугу па тэлефоне. Але ён, магчыма, быў апошнім, таксама. 

Так у выпадковым парадку не добра. Таму выкажам здагадку, што мы павінны сартаваць Тэлефонная кніга або ў агульных дадзеных сартавання што мы далі. Як мы можам зрабіць гэта? 

Што ж, дазвольце мне паспрабаваць просты прыклад тут. Дазвольце мне ісці наперад і кінуць Некалькі нумароў на дошцы. Хай колькасці ў нас ёсць ёсць, скажам, чатыры, два, адзін і тры. І, Бэн, сартаваць гэтыя лічбы для нас. 

Добра, добра. Як ты гэта зрабіў? Добра. Так што пачніце з самым маленькім значэнне і высокі, і гэта сапраўды добрая інтуіцыя. І разумеем, што мы людзі на самай справе даволі добра на рашэнне праблем як гэта, па меншай меры, калі дадзеныя адносна малая. Як толькі вы пачынаеце мець сотні лікаў, тысячы лікаў, мільёны лікаў, Бэн, верагодна, не мог зрабіць гэта досыць хутка, што, калі выказаць здагадку, што існуюць прабелы ў лічбах. Даволі лёгка падлічыць да мільёна у адваротным выпадку проста адымае шмат часу. 

Такім чынам, алгарытм гэта гучыць як Бэн выкарыстоўваецца толькі цяпер быў пошук найменшага колькасці. Так што, хоць мы, людзі могуць прыняць ў вялікай колькасці інфармацыі візуальна, кампутар на самай справе крыху больш за абмежаваным. Кампутар можа толькі глядзець на адзін байт у той час, або, можа быць чатыры байта за time-- у гэтыя дні, можа быць 8 байт за time-- але вельмі невялікі лік байтаў ў дадзены момант часу. 

Таму, улічваючы, што мы сапраўды маем чатыры асобныя значэння here-- і вы можаце думаць аб Бэн як мае шоры, калі б ён быў кампутар тыпу што ён не можа бачыць нічога іншага чым адзін нумар у каталогу time-- таму мы звычайна будзем лічыць, як і ў Англійская, мы будзем чытаць справа налева. Такім чынам, першы нумар Бэн, верагодна, выглядаў на было чатыры гады, а затым вельмі хутка зразумеў, што гэта даволі вялікі number-- дазвольце мне працягваць пошукі. 

Там два. Пачакай хвіліну. Два менш чатырох. Я буду памятаць. Два ў цяперашні час з'яўляецца найменшай. Цяпер одно-- гэта яшчэ лепш. Гэта нават менш. Я збіраюся забыцца пра двух і проста ўспомніць яго цяпер. 

І ён мог перастаць глядзець? Ну, ён мог на аснове на гэтай інфармацыі, але ён лепш бы пошук астатняя частка спісу. Таму што, калі нуль былі ў спісе? Што рабіць, калі адмоўны былі ў спісе? Ён ведае толькі, што яго адказ з'яўляецца правільным, калі ён вычарпальна праверыў ўвесь спіс. Такім чынам, мы глядзім на астатняй частцы гэтага. Three--, што гэта пустая трата часу. Не повезло, але я быў да гэтага часу правільна зрабіць гэта. І вось цяпер ён, верагодна, выбіраецца найменшая колькасць і проста пакласці яго ў пачатку са спісу, як я буду тут рабіць. Цяпер тое, што вы рабілі далей, нягледзячы на ​​тое, Вы не думалі пра гэта амаль да такой ступені? Паспрабуйце гэты працэс, таму які-то цыкл. Там знаёмая ідэя. Дык вось чатыры. Гэта ў цяперашні час самы маленькі. Гэта кандыдат. Не болей. Цяпер я бачыў два. Гэта наступны найменшы элемент. Three--, што не менш, так Цяпер Бэн можа вырываць два. 

І зараз мы паўтараем працэс, а вядома тры атрымлівае выцягнуў наступны. Паўтарыце працэс. Чатыры атрымлівае выцягнуў. А зараз мы з лікаў, так што спіс павінен быць адсартаваны. 

І на самай справе, гэта фармальны алгарытм. Кампутар навуковец будзе называем гэта "выбар роду" ідэя ў тым, сартаваць па спіс iteratively-- зноў і зноў і зноў выбар найменшая колькасць. І што прыемна пра яго гэта проста так па-чартоўску інтуітыўным. Гэта так проста. І вы можаце паўтарыць тое ж самае аперацыя зноў і зноў. Гэта проста. 

У гэтым выпадку гэта было хутка, але як доўга гэта на самай справе ўзяць? Давайце зробім гэта, здаецца, і адчуваць сябе крыху больш стомным. Так што адзін, два, тры, чатыры, пяць, шэсць ,, сем, восем, дзевяць, 10, 11, 12, 13, 14, 15, 16-- адвольнае лік. Я проста хацеў больш гэтага Час, чым проста чатыры. Так што, калі ў мяне ёсць цэлае звязак лікаў now-- яго нават не мае значэння што яны are-- давайце думаць пра тое, што гэта Алгарытм вельмі падобны. 

Выкажам здагадку, што існуюць колькасці там. Зноў жа, не мае значэння, што яны ёсць, але яны выпадковым чынам. Я ўжываю алгарытм Бэн. Мне трэба, каб выбраць найменшае лік. Што я раблю? І я збіраюся фізічна зрабіць гэта на гэты раз, каб дзейнічаць яго. Гледзячы, гледзячы, гледзячы, гледзячы, гледзячы. Толькі да таго часу я атрымліваю канец спісу можа Я разумею, што самы маленькі лік было два на гэты раз. Адзін не ў спісе. Так што я паклаў два. 

Што рабіць далей? Гледзячы, гледзячы, гледзячы, гледзячы. Цяпер я знайшоў нумар сем, таму што ёсць прабелы ў гэтых numbers-- а проста адвольна. Добра. Так што цяпер я магу пакласці ўніз сем. Гледзячы гледзячы, гледзячы. 

Цяпер я мяркую, з Вядома ж, што Бэн не маюць дадатковую аператыўную памяць, дадатковыя памяць, таму што, вядома ж, Я гляджу на той жа нумар. Вядома, я мог бы памятаць, усе гэтыя лічбы, і гэта абсалютна дакладна. Але калі Бен памятае ўсё з нумара, якія ён бачыў, ён на самай справе не зрабіў фундаментальны прагрэс таму што ў яго ўжо ёсць магчымасць пошуку па нумарах на дошцы. Успамінаючы ўсё з нумары не дапамагае, таму што ён усё яшчэ можа як кампутар толькі глядзець, мы ўжо казалі, адзін нумар ў той час. Так што няма ніякага роду читов там, што вы можаце выкарыстоўваць. 

Так што на самой справе, як я працягваць пошук у спісе, Я літаральна павінен проста працягваць ісці туды-сюды праз яе, выскубанне наступны найменшая колькасць. І, як вы можаце збольшага зрабіць выснову ад маіх дурных рухаў, гэта проста становіцца вельмі стомна вельмі хутка, і я, здаецца, ідзе назад і наперад, туды-сюды, зусім няшмат. Зараз, каб быць справядлівым, я не павінен ісці зусім як, ну, давайце see-- быць справядлівым, Я не прыйдзецца хадзіць даволі столькі крокаў, кожны раз. Таму што, вядома ж, як я выбраць нумары з спісу, пакінуты спіс становіцца ўсё карацей. 

Так што давайце думаць пра колькі крокаў я на самой справе тащась праз кожны раз. У першай сітуацыі у нас было 16 нумароў, і так maximally-- давайце проста зрабіць гэта для discussion-- Я павінен быў глядзець праз 16 гадоў нумары, каб знайсці самы маленькі. Але як толькі я б вырвалі найменшая колькасць, як доўгі час быў пакінуты спіс, вядома? Толькі 15. Дык колькі лікаў зрабіў Бэн ці ў мяне ёсць пагартаць ў другі раз вакол? 15, проста пайсці і знайсці самы маленькі. Але цяпер, вядома, спіс, таксама менш, чым гэта было раней. Дык колькі крокаў зрабіў я павінны ўзяць на сябе ў наступны раз? 14, а затым 13, а затым 12, плюс кропка, кропка, кропка, пакуль я не застанецца толькі адзін. Так што цяпер кампутарны навуковец будзе спытаеце, ну, што ж, што ўсе роўныя? Гэта на самай справе роўна некаторыя канкрэтныя лік, якое мы маглі б, вядома, рабіць арыфметычна, але мы хочам пагаварыць аб эфектыўнасці алгарытмаў крыху больш за formulaically, не залежыць ад таго, як доўга гэты спіс. 

І вы ведаеце, што? Гэта 16, але як я ўжо сказаў раней, давайце проста назваць памер праблемы п, дзе п некаторы лік. Можа быць, гэта 16, можа быць, гэта тры, можа быць, гэта мільён. Я не ведаю. Я не клапачуся. Тое, што я сапраўды хачу, формула, я магу выкарыстоўваць для параўнання гэты алгарытм супраць іншых алгарытмаў што хто-то можа прэтэндаваць лепш ці горш. 

Так што атрымліваецца, і я толькі ведаю, што гэта з пачатковай школы, што гэта на самай справе працуе, да таго ж рэч, як п па п плюс адзін больш за два. І гэта адбываецца ў роўных умовах, Вядома ж, п квадрат плюс п над імі. Так што, калі я хацеў формулу На колькі крокаў былі ўцягнутыя ў гледзячы на ​​ўсе аб зноў і зноў гэтыя лічбы і зноў і зноў, я б сказаў, гэта п квадрат плюс п над імі. Але вы ведаеце, што? Гэта проста выглядае неакуратна. Я проста вельмі хачу Агульны сэнс рэчаў. І вы можаце ўспомніць з сярэдняй школы, што там з'яўляецца паняцце тэрміна вышэйшага парадку. Які з гэтых тэрмінаў, п квадрат, руская, або палову, мае найбольшы ўплыў з цягам часу? Чым больш п атрымлівае, што з гэтых пытанняў больш за ўсё? 

Іншымі словамі, калі я падлучу на мільён, п квадрат будзе, хутчэй за ўсё, дамінуючым фактарам, таму што ў мільён разоў сама па сабе нашмат больш чым плюс адзін дадатковы мільён. Такім чынам, вы ведаеце, што? Гэта такая вялікая штопка нумар, калі вы квадратуры нумар. Гэта не мае ніякага значэння. Мы проста крыж, , І забыцца пра гэта. І таму навуковец сказаў бы што эфектыўнасць гэтага алгарытму складае парадку п squared-- Я маю на ўвазе сапраўды набліжэнне. Гэта свайго роду груба п ў квадраце. З цягам часу, тым больш і больш п атрымлівае, гэта з'яўляецца добрай адзнакай для таго, што эфектыўнасць або адсутнасць эфектыўнасці гэтага алгарытму на самай справе. І я атрымаць, што, вядома ж, ад фактычна робіць матэматыку. Але цяпер я проста махаў мае рукі, таму што я проста хочаце агульны сэнс гэтага алгарытму. 

Такім чынам, выкарыстоўваючы тую ж логіку, тым часам, давайце разгледзім іншы алгарытм мы ўжо разгледзелі at-- лінейны пошук. Калі я шукаў для тэлефона book-- ня сартаваць яе, пошук праз тэлефонную book-- мы працягвалі казаць, што гэта было 1000 захадаў або 500 крокаў. Але давайце абагульнім гэта. Калі ёсць п старонак тэлефонная кніга, што бягучы час ці эфектыўнасць лінейнага пошуку? Гэта на парадак колькі крокаў, каб знайсці Майк Сміт, выкарыстоўваючы лінейны пошук, то Першы алгарытм, або нават другая? 

У горшым выпадку, Майк знаходзіцца ў канцы кнігі. Так што, калі тэлефонная кніга мае 1000 старонак, мы гаварылі ў мінулы раз, у самым горшым выпадку, гэта можа заняць прыкладна як шмат старонак, каб знайсці Майк? Як і 1000. Гэта верхняя мяжа. Гэта горшы з магчымых сітуацый. Але зноў жа, мы аддаляючыся з ліку, як 1000 цяпер. Гэта проста п. 

Дык што ж лагічны выснову? Знаходжанне Майк ў тэлефоне Кніга, якая мае п старонак можа спатрэбіцца, у самым горшым выпадку, колькі крокаў па парадку п? І на самай справе кампутар вучоны сказаў бы што час працы, або прадукцыйнасць або эфектыўнасць або неэфектыўнасць алгарытму як лінейны пошук па парадку п. І мы можам прымяніць той жа логіка перасячэння нешта як я толькі што зрабіў на другі Алгарытм мы мелі з тэлефоннай кнігай, куды мы пайшлі дзве старонкі адначасова. 

Так што 1000 старонка Тэлефонная кніга можа ўзяць нас 500 старонак паваротаў, плюс адзін калі мы захіліць няшмат. Так што, калі тэлефонная кніга мае п старонак, але мы робім дзве старонкі ў той час, гэта прыкладна тое, што? N больш чым два, так што як п над імі. Але я зрабіў патрабаваць хвіліну назад, што п над two-- гэта свайго роду такі ж, як толькі п. Гэта проста пастаянны множнік, кампутарныя навукоўцы сказалі б. Давайце акцэнтаваць увагу толькі на зменныя, really-- самыя вялікія зменныя ў раўнанні. 

Такім чынам, лінейны пошук, ці то зрабіў адзін старонкі ў той час, ці дзве старонкі ў той час, з'яўляецца свайго роду прынцыпова тое ж самае. Гэта па-ранейшаму парадку п. Але я сцвярджаў з маім малюнкам раней што трэці алгарытм ня быў лінейны. Гэта была не прамая лінія. Гэта было тое, што выгнутыя лініі, і алгебраічная формула была што? Часопіс так зайсці N-, падстава два п. І мы не павінны ўдавацца ў шмат дэталяў на лагарыфмаў сёння, але большасць кампутарных навукоўцаў не будзе нават сказаць вам, што база. Таму што гэта ўсё проста пастаяннымі фактарамі, так бы мовіць, толькі нязначныя лікавыя адрозненні. І вось гэта было б вельмі распаўсюджанай з'явай спосаб асабліва фармальнага кампутара навуковыя работнікі на дошцы або праграмісты белай дошкі на самай справе сцвярджаючы, які Алгарытм яны будуць выкарыстоўваць або тое, што каэфіцыент карыснага дзеяння з іх алгарытм. 

І гэта не абавязкова нешта вы будзеце абмяркоўваць у любым дэталях, але добры праграміст хтосьці які мае салідны, фармальны фон. Ён у стане гаварыць Вы ў гэтым выглядзе шляху і на самай справе зрабіць якасныя аргументы, чаму адзін алгарытм або адна частка праграмнага забеспячэння пераўзыходзіць ў нейкай меры да іншага. Таму што вы маглі б, вядома, проста запусціць праграму аднаго чалавека і падлічыць колькасць секунд патрабуецца, каб сартаваць некаторыя лічбы, і вы можаце запусціць некаторыя праграма іншага чалавека і падлічыць колькасць секунд патрабуецца. Але гэта больш агульны спосаб, які вы можаце выкарыстоўваць для аналізу алгарытмаў, калі вы будзеце, як раз на папера ці проста ў вуснай форме. Нават не запусціць яго без нават спрабаваць ўваходы выбаркі, вы можаце проста разважаць праз яго. І так з найманнем распрацоўшчык або калі маючы яго ці яе роду сцвярджаюць, вам чаму іх алгарытм, іх сакрэт соус для пошуку мільярды вэб-старонак для кампанія лепш, гэтыя з'яўляюцца віды аргументаў, якія яны у ідэале павінны быць у стане зрабіць. Ці, па меншай меры, гэта віды рэчаў што б прыйсці ў дыскусіі на хаця б у вельмі фармальнай дыскусіі. Добра. Так што Бэн прапанаваў нешта называецца выбар роду. Але я збіраюся прапанаваць, што ёсць іншыя спосабы зрабіць гэта, таксама. Тое, што я не вельмі падабаецца пра алгарытм Бэн у тым, што ён працягваў ісці, або то, як я іду, туды-сюды і ўзад і наперад і назад і наперад. Што рабіць, калі замест таго, каб я павінен быў зрабіць нешта накшталт гэтых лікаў тут і я павінен быў проста мець справу з кожным нумар, у сваю чаргу, як я даў яму? 

Іншымі словамі, тут мой спіс нумароў. Чатыры, адзін, тры, два. І я збіраюся зрабіць наступнае. Я збіраюся ўставіць лічбы дзе яны належаць хутчэй чым выбіраючы іх па адным за раз. Іншымі словамі, вось нумар чатыры. 

Вось мой першапачатковы спіс. І я буду падтрымліваць па сутнасці, новы спіс тут. Так што гэта стары спіс. Гэта новы спіс. Я бачу нумар чатыры ў першую чаргу. Мой новы спіс першапачаткова пусты, таму трывіяльным выпадак што чатыры цяпер сартавалі спіс. Я проста прымаючы лік я даў, і я стаўлю яго ў сваім новым спісе. 

Пасартаваны гэты новы спіс? Так. Гэта глупства, таму што ёсць толькі адзін элемент, але гэта абсалютна адсартаваны. Там няма нічога, недарэчныя. Гэта больш цікава, гэты алгарытм, калі я пераходжу да наступнага кроку. 

Цяпер у мяне ёсць адзін. Так што, вядома ж, належыць на пачатак ці канец гэтага новага спісу? Пачатак. Так што я павінен зрабіць некаторыя працы ў цяперашні час. Я прымаю некаторыя вольнасці з маім маркерам на проста малюнак рэчаў дзе я хачу іх, але гэта не зусім дакладным у кампутары. Кампутар, як мы ведаем, мае Аператыўная памяць, або Random Access Memory, і гэта адзін байт і іншы байт і яшчэ адзін байт. І калі ў вас ёсць гігабайта RAM, у вас ёсць мільярд байтаў, але яны фізічна ў адным месцы. Вы не можаце проста перамяшчаць рэчы вакол намаляваўшы яе на дошцы дзе вы хочаце. Так што, калі мой новы спіс мае чатыры месцы ў памяці, на жаль, чатыры з'яўляецца ўжо ў няправільным месцы. 

Такім чынам, каб ўставіць нумар адзін Я не магу проста зрабіць гэта тут. Гэта месца памяці не існуе. Гэта было б падман, і я быў Здрады выяўленча на працягу некалькіх хвілін тут. Так на самой справе, калі я хачу паставіць адзін тут, Я павінен часова скапіяваць чатыры а затым пакласці адзін там. 

Гэта добра, гэта правільна, што гэта тэхнічна магчыма, але разумею, што гэта дадатковая праца. Я не проста паставіць нумар на месцы. Спачатку я павінен быў рухацца нумар, а затым пакласці яго на месцы, так што я свайго роду падвоіў сваю аб'ём працы. Так што майце гэта на ўвазе. 

Але цяпер я зрабіў з гэтым элементам. Цяпер я хачу, каб захапіць нумар тры. Там, дзе, вядома ж, яно належыць? Паміж. Я не магу падмануць больш і проста паставіць яго там, таму што, зноў жа, гэтая памяць у фізічных месцах. Так што я павінен скапіяваць чатыры і паставіць тры тут. Не вялікае справа. Гэта ўсяго толькі адзін дадатковы крок again-- адчувае сябе вельмі нядорага. 

Але цяпер я пераходжу да двух. Два, вядома ж, належыць тут. Цяпер вы пачынаеце бачыць, як праца можа назапашвацца. Цяпер тое, што я павінен рабіць? Так, я павінен перамясціць чатыры, Затым я павінен скапіяваць тры, і цяпер я магу ўставіць два. І ўлоў з гэтым Алгарытм, досыць цікава, з'яўляецца тое, што выкажам здагадку, у нас ёсць больш экстрэмальны выпадак, калі гэта, скажам, восем, сем, шэсць, пяць, чатыры, тры, два, адзін. Гэта, у многіх кантэкстах, у горшым выпадку, таму што цыраваць рэч літаральна ў зваротным кірунку. 

Гэта сапраўды не мае ўплывае на алгарытм Бэн, таму што ў адборы Бэн свайго роду ён збіраецца трымаць ходзіць туды-сюды па спісе. І таму, што ён заўсёды шукаў праз увесь астатні спіс, няважна дзе элементы. Але ў гэтым выпадку з маёй ўстаўкі approach-- давайце паспрабуем гэта. 

Так адзін, два, тры, чатыры, пяць, шэсць, сем, восем. Адзін, два, тры, чатыры, пяць, шэсць, сем, восем. Я збіраюся ўзяць восем, і дзе я магу гэта сказаць? Ну, у самым пачатку майго спісу, таму што гэты новы спіс адсартаваны. І я перасякаў яго. 

Дзе я паставіў сем? Чорт яго. Ён павінен ісці туды, так Я павінен зрабіць некаторыя капіявання. А цяпер сем ідзе тут. Цяпер я пераходжу да шасці. Цяпер стала яшчэ больш працы. 

Восем павінен ісці тут. Сем павінен ісці сюды. Зараз шэсць можа пайсці сюды. Цяпер я захапіць пяць. Цяпер восем павінен ісці тут, сем даводзіцца ісці сюды, шэсць павінен ісці тут, і Цяпер пяць і паўторыце. І я даволі шмат перамяшчаючы яго пастаянна. 

Такім чынам, у рэшце рэшт, гэта algorithm-- мы будзем назваць яго ўстаўкі sort-- на самай справе мае шмат працы, таксама. Гэта проста розныя выгляд працы, чым Бэн. Праца Бэн прымусіў мяне ісці назад і наперад ўвесь час, выбіраючы наступны найменшы элемент зноў і зноў. Так што гэта было вельмі візуальны выгляд працы. 

Гэты іншы алгарытм, які па-ранейшаму correct-- ён атрымае працу done-- проста змяняе аб'ём працы. Падобна на тое, што першапачаткова вы эканоміі, таму што вы проста маем справу з кожным элементам фронт без хадзіць усё шлях праз спіс, як Бэн. Але праблема ў тым, асабліва ў гэтыя вар'яты выпадкі, калі гэта ўсё ў зваротным кірунку, вы проста выгляд адкладаючы цяжкую працу пакуль вы не павінны выправіць свае памылкі. 

І так, калі вы можаце сабе гэта восем і сем і шэсць і пяць а затым чатыры і тры і два перамяшчаючы іх шлях праз спіс, мы толькі што змянілі тып працы, якую мы робім. Замест таго, каб рабіць гэта на пачатак маёй ітэрацыі, Я проста раблю гэта на канец кожнай ітэрацыі. Так атрымліваецца, што гэты алгарытм, таксама, як правіла, называецца сартаванне устаўкай, Таксама на парадак п квадрата. Гэта не на самай справе не лепш, ці не лепш наогул. 

Тым не менш, ёсць і трэці падыход Я хацеў бы заклікаць нас да разгляду, што гэта. Такім чынам, хай мой спіс, для прастаты зноў жа, чатыры, адзін, тры, two-- усяго чатыры нумары. Бэн меў добрую інтуіцыю, добрая чалавечая інтуіцыя да таго, з дапамогай якога мы фіксавалі ўвесь спіс eventually-- ўстаўкі сартавання. Я ўгаварыў нас наперад. Але давайце разгледзім Найпросты спосаб выправіць гэты спіс. 

Гэты спіс не адсартаваны. Чаму? У ангельскай мове растлумачыць, чаму гэта на самай справе не сартуецца. Што гэта значыць не быць адсартаваныя? 

СТУДЭНТЫ: Гэта не паслядоўны. 

DAVID Малання: Ці не паслядоўны. Дайце мне прыклад. 

СТУДЭНТЫ: Змесціце іх у парадку. 

DAVID Малання: OK. Дайце мне больш канкрэтны прыклад. 

СТУДЭНЦКАЯ парадку ўзрастання. DAVID Малання: Не в парадку ўзрастання. Быць больш дакладным. Я не ведаю, што вы маеце на ўвазе па ўзрастанні. Што здарылася? 

СТУДЭНТЫ: Самы маленькі з лічбы не ў першым прасторы. 

DAVID Малання: Найменшы нумары мадэлі не ў першым прасторы. Будзьце больш канкрэтнымі. Я пачынаю лавіць на. Мы разлічваем, але што з ладу тут? 

СТУДЭНТЫ: лікавая паслядоўнасць. DAVID Малання: лікавая паслядоўнасць. выгляд кожнага чалавека ўтрымлівання яна here-- вельмі высокі ўзровень. Проста літаральна сказаць мне, што не так, як пяць-гадовай моцы. 

СТУДЭНТЫ: Плюс адзін. 

DAVID Малання: Што гэта? 

СТУДЭНТЫ: Плюс адзін. 

DAVID Малання: Што вы маеце на ўвазе плюс адзін? Дайце мне адной пяць гадоў. Што здарылася, мама? Што здарылася, тата? Што вы маеце на ўвазе гэта не адсартаваны? 

СТУДЭНТЫ: Гэта не месца. 

DAVID Малання: Што не ў патрэбным месцы? 

СТУДЭНТЫ: Чатыры. DAVID Малання: Добра, добра. Так чатыры не там, дзе яна павінна быць. У прыватнасці, гэта праўда? Чатыры і адзін, першы два ліку, якія я бачу. Ці правільна гэта? Не, яны не ў парадку, ці не так? На самай справе, думаю, што цяпер аб кампутары, таксама. Ён можа глядзець толькі на адну, можа быць, можа быць, дзве рэчы ў once-- а на самай справе толькі адна рэч, у той час, але ён можа па крайняй меры, паглядзець на адну рэч, то Наступнае, што прама побач з ім. 

Гэтак жа гэтыя ў парадку? Канешне не. Такім чынам, вы ведаеце, што? Чаму б нам не ўзяць дзіцяці крокі ліквідаваць гэтую праблему замест таго, каб рабіць гэтыя фантазіі алгарытмы, такія як Бэн, дзе ён накшталт фіксуючы яго прабягаем па спісе замест таго, каб рабіць тое, што я зрабіў, дзе Я толькі збольшага ўсталяваў яго, як мы ідзем? Давайце проста літаральна зламаць Паняцце order-- лікавага парадку, назваць гэта ўсё, што вы want-- у гэтых парных параўнанняў. 

Чатыры і адзін. Ці з'яўляецца гэта правільны парадак? Такім чынам, давайце выправім гэта. Адзін і чатыры, а затым мы проста скапіяваць гэта. Добра, добра. Я усталяваў адзін і чатыры. Тры і два? Няма. Хай мае словы супадаюць мае пальцы. Чатыры і тры? 

Гэта не ў парадку, так што я збіраюся каб зрабіць адзін, тры, чатыры, два. Добра, добра. Зараз чатыры і два? Нам трэба, каб выправіць гэта, таксама. Так адзін, тры, два, чатыры. Дык гэта сартуецца? Няма, але гэта бліжэй да адсартаваны? 

Гэта, таму што мы гэта выправіў памылка, мы выправілі гэтую памылку, і мы выправілі гэтую памылку. Такім чынам, мы зафіксавалі тры памылкі, магчыма. Тым не менш не выглядае адсартаваны, але яна аб'ектыўна бліжэй да адсартаваны таму што мы зафіксавалі некаторыя з гэтых памылак. 

Цяпер тое, што мне рабіць далей? Я збольшага дасягнуў канца спісу. Я, здавалася, замацавалася усе памылкі, але няма. Таму што ў гэтым выпадку, некаторыя нумары магчыма, бурбалкі бліжэй на іншыя нумары, якія па-ранейшаму не ў парадку. Так што давайце рабіць гэта зноў, і я буду проста зрабіць гэта на месцы на гэты раз. Адзін і тры? Гэта нармальна. Тры і два? Вядома, няма, так што давайце змяніць гэтую сітуацыю. Так два, тры. Тры і чатыры? А цяпер давайце проста асабліва педантычным тут. сартуецца Ці гэта? Вы, людзі ведаюць, што гэта сартуецца. 

Я павінен паспрабаваць яшчэ раз. Так што Алівія прапануе мне паспрабаваць яшчэ раз. Чаму? Паколькі кампутар не мае раскоша нашых чалавечых вачэй проста зірнуўшы back-- ОК, я зрабіў. Як кампутар вызначае што спіс зараз адсартаваны? Механічна. 

Я павінен прайсці праз яшчэ раз, і толькі тады, калі я не робяць / знайсці якія-небудзь памылкі, я магу затым зрабіць выснову, як кампутар, так, мы добра ісці. Так адзін і два, два і тры, тры і чатыры. Цяпер я магу канчаткова сказаць, што гэта сартуюць, таму што я не зрабіў ніякіх зменаў. Цяпер гэта будзе памылка і проста па-дурному, калі я, кампутар, зноў спытаў тыя ж пытанні чакаючы розныя адказы. Не павінна адбыцца. 

І вось цяпер спіс адсартаваны. На жаль, бег часу гэты алгарытм таксама N ў квадраце. Чаму? Паколькі ў вас ёсць п колькасці, а ў горшым выпадку вы павінны рухацца п лікаў п раз, таму што вы павінны працягваць ісці назад, каб праверыць і выправіць патэнцыйна гэтыя лічбы. І мы можам зрабіць больш фармальны аналіз таксама. 

Так што гэта ўсё, каб сказаць, што мы зрабілі тры розных падыходу, адзін з іх адразу ж інтуітыўна ад лятучай мышы ад Ben да майго прапанаванага ўключэння сартаваць да гэтага дзе вы, здаецца, выпускаць з-пад увагі лес за дрэвамі на пачатковым этапе. Але тады, калі вы зрабіць крок назад, вуаля, мы выправілі сартавальны паняцце. Так што гэта, адважуся сказаць, больш нізкі ўзровень, магчыма, чым некаторыя з тых іншых алгарытмы, але давайце убачыць, калі мы не можам ўявіць сабе яны праз гэта. 

Так што гэта нейкі добры праграмнае забеспячэнне, якое нехта напісаў, выкарыстоўваючы маляўнічыя бары, што гэта збіраецца зрабіць наступнае для нас. Кожны з гэтых стрыжняў ўяўляе сабой лік. Taller слупок, тым больш лік, менш бар, тым менш лік. Так што ў ідэале мы хочам добрую піраміду дзе яна пачынаецца з малога і становіцца вялікі, і гэта будзе азначаць, што гэтыя бары сартуюцца. Так што я збіраюся ісці наперад і выбіраць, напрыклад, алгарытм Бэн first-- выбар сартавання. 

І заўважце, што ён робіць. Тое, як яны выбралі візуалізаваць гэты алгарытм у тым, што, гэтак жа, як я быў хадзіць праз мой спіс, гэтая праграма ідзе праз свой спіс нумароў, вылучаючы ў ружовы колер кожнага лік, якое ён глядзіць. А што павінна адбыцца прама цяпер? 

Найменшая колькасць, Я або Бэн выявіў раптам атрымлівае перамяшчаецца ў пачатак спісу. І да вашага ведама, што яны зрабілі выселіць нумар, які быў там, і гэта выдатна. Я не патрапіў у гэты ўзровень дэталізацыі. Але нам трэба паставіць што лік недзе, так што мы проста перамясціў яго да адкрытае месца, якое было створана. Так што я збіраюся паскорыць гэты працэс уверх, таму што ў адваротным выпадку ён становіцца вельмі стомным хутка. Анімацыя speed-- там мы ідзем. Так што цяпер жа прынцып Я ўжывала, але вы можа пачаць адчуваць сябе алгарытм, калі вы будзе, ці ўбачыць яго крыху больш выразна. І гэты алгарытм мае эфект выбіраючы наступны найменшы элемент, так што вы збіраецеся пачаць Ён устае на левай баку. І на кожнай ітэрацыі, як я прапанаваў, ён робіць трохі менш працы. Ён не павінен прайсці ўвесь шлях назад да левага канца спісу, таму што гэта ўжо ведае тых, сартуюцца. Так што гэта свайго роду адчувае, як гэта паскарэння, хоць кожны крок прымаючы такое ж колькасць часу. Там у тыя, што засталіся за ўсё менш крокаў. І цяпер вы можаце збольшага адчуваю Алгарытм ачысткі ў канцы яго, і на самой справе зараз гэта сартуецца. 

Такім чынам, сартаванне устаўкай усё гэта робіцца. Мне трэба паўторна рандомизации масіў. І заўважце, я магу проста трымаць яго рандомизации, і мы атрымаем набліжэнне той жа падыход, сартаванне устаўкай. Дазвольце мне запаволіць яго сюды. Давайце пачнем, што больш. Стоп. 

Давайце прапусціць чатыры. Там мы ідзем. Змяшайце іх масіў. І тут мы go-- ўстаўкі роду. Гуляць. Звярніце ўвагу на тое, што ён мае справу з кожным элемент ён сустракае адразу ж, але калі яна належыць няправільнае месца апавяшчэнне усе працы, што павінна адбыцца. Мы павінны працягваць пераход больш і больш элементаў, каб вызваліць месца для таго, што мы хочам, каб паставіць на месца. 

Такім чынам, мы засяроджваецца на левы канец толькі спіс. Заўважце, што мы нават не глядзелі at-- мы не выдзелены ружовым колерам што-небудзь направа. Мы проста маем справу з праблемы, як мы ідзем, але мы ствараем шмат працаваць для сябе да гэтага часу. І таму, калі мы паскорыць гэты працэс Зараз, каб перайсці да завяршэння, яна мае іншае пачуццё да яго на самай справе. Гэта проста засяродзіцца на левым канцы, але рабіць трохі больш працы, як needed-- выгляд якія згладжваюць рэчаў больш, фіксуючы рэчы, але справа ў канчатковым рахунку, з кожны элемент па адным за раз пакуль мы не атрымаем добра the--, мы усе ведаюць, як гэта збіраецца скончыцца, так што гэта крыху руйнаваўся магчыма. 

Але спіс у end-- spoiler-- збіраецца быць адсартаваныя. Такім чынам, давайце разгледзім адзін апошні. Мы не можам проста прапусціць гэты. Мы амаль там. Два ісці, адзін ісці. І вуаля. Выдатна. 

Так што цяпер давайце зробім адну апошнюю, паўторна рандомизации з пузырьковый сартавання. І заўважце тут, асабліва калі я запаволіць яго ўніз, гэта трымаць парылы да канца. Але зьвярніце ўвагу, гэта толькі робіць парна comparisons-- роду лакальных рашэнняў. Але як толькі мы атрымліваем канец спісу ў ружовы, што прыйдзецца здарыцца зноў? Так, гэта прыйдзецца пачаць усё спачатку, таму што гэта толькі Нерухомыя парамі памылкі. І гэта, магчыма, выявілі яшчэ іншыя. І таму, калі вы паскорыць гэты працэс, вы будзеце бачым, што, падобна таму як вынікае з назвы, тым менш elements-- ці, дакладней, вялікія elements-- пачынаюць тапырыцца да самага верху, калі вы будзеце. А больш дробныя элементы пачынаючы тапырыцца ўніз налева. І на самай справе, гэта свайго роду візуальны эфект, а таксама. І такім чынам гэта будзе ў канчатковым выніку аздабленне ў вельмі падобным чынам, таксама. 

Мы не павінны спыняцца па гэтым канкрэтнаму аднаму. Дазвольце мне адкрыць гэта цяпер, таксама. Там у некалькі іншых алгарытмаў сартавання ў свеце, некаторыя з якіх захопліваюцца тут. І адмыслова для вучняў, якiя не з'яўляюцца абавязкова візуальнае або матэматычнае, як мы рабілі раней, мы можам таксама зрабіць гэта audially калі параўноўваць гук з гэтым. І проста для задавальнення, вось некалькі розных алгарытмаў, і адзін з іх, у прыватнасці, вы заўважыць, называецца "сартаванне зліццём." 

Гэта на самай справе прынцыпова лепш алгарытм, такім чынам, што сартаванне зліццём, адзін з тыя, з якімі вы хочаце бачыць, ня парадак п ў квадраце. Гэта аб парадку п раз Лагарыфм N, якая на самай справе менш, і, такім чынам, хутчэй, чым астатнія тры. І ёсць пара іншы дурныя тыя, што мы будзем бачыць. 

Так што тут мы ідзем з некаторым гукам. Гэта сартаванне устаўкай, так што зноў гэта проста справа з элементамі як яны прыходзяць. Гэта свайго роду бурбалка, так што лічачы іх пары адначасова. І зноў жа, самыя вялікія элементы прарываецца да самага верху. 

Далей выбар сартавання. Гэта алгарытм Бэн, дзе зноў ён итеративно выбару наступны найменшы элемент. І зноў жа, зараз вы можаце сапраўды пачуць, што гэта паскарэнне, але толькі ў той ступені, як гэта робіць усё менш і менш працаваць на кожнай ітэрацыі. Гэта больш хуткае, сартаванне зліццём, які сартуе кластары лікаў разам, а затым аб'ядноўваючы іх. Так look-- левы палова ўжо адсартаваныя. 

Зараз гэта сартаванне правую палову, і Цяпер ён збіраецца аб'яднаць іх у адно цэлае. Гэта тое, што называецца "Гном роду." І вы можаце збольшага бачыць, што ён ходзіць туды-сюды, фіксуючы працу трохі тут і там, перш чым ён прыступае да новай працы. І гэта ўсё. Там у іншы від, які сапраўды толькі для акадэмічных мэтаў, называецца "дурным роду", які прымае Вашы дадзеныя, сартуе яго ў выпадковым парадку, а затым правярае, ці з'яўляецца яна сартуецца. І калі гэта не так, то ізноў сартуе яго выпадковым чынам, правярае, ці з'яўляецца яна сартуецца, і калі не паўтараецца. І ў тэорыі, імавернасна гэта будзе завершана, але пасля таго, як зусім няшмат часу. Гэта не самы эфектыўнасць алгарытмаў. Так што любыя пытанні аб тых, канкрэтныя алгарытмы або што-небудзь звязаных там таксама? 

Што ж, давайце зараз дражняць адзін ад аднаго, што ўсе гэтыя лініі, якія я малюю і тое, што я мяркую, што кампутар можа зрабіць пад капотам. Я лічу, што ўсе гэтыя лічбы Я трымаю drawing-- яны павінны атрымаць захоўваецца дзесьці ў памяці. Мы пазбавіцца ад гэтага хлопца зараз таксама. 

Такім чынам, частка памяці ў computer-- так RAM памяці складае тое, што мы шукалі ўчора, двайны убудаваная памяць module-- выглядае наступным чынам. І кожны з гэтых маленькіх чорных фішак некаторы колькасць байтаў, як правіла. А потым залатыя шпількі падобныя да драты, якія падключаюцца да кампутара, і зялёная дошка крэмнія проста што трымае ўсе разам. Дык што ж гэта на самай справе азначае? Калі я як бы зрабіць такі ж карціну, давайце выкажам здагадку для прастаты што гэты модуль DIMM, двайны убудаваны модуль памяці, адзін гігабайт аператыўнай памяці, адзін гігабайт памяць, якая, колькі ўсяго байт? Адзін гігабайт гэта колькі байт? Больш за тое. 1124 з'яўляецца кілаграм, 1000. Мега млн. Гіга гэта мільярд. 

Я ляжу? Ці можам мы нават чытаць этыкетку? Гэта на самай справе 128 гігабайты, так што гэта больш. Але мы будзем рабіць выгляд, гэта гэта толькі адзін гігабайт. Так што азначае, што ёсць мільярд байт памяці, даступнай для мяне ці 8 мільярдаў біт, але мы збіраемся казаць у тэрмінах байтаў ў цяперашні час, рухацца наперад. 

Так што гэта значыць, гэта адзін байт, гэта яшчэ адзін байт, гэта яшчэ адзін байт, і калі мы сапраўды хацелі каб быць канкрэтным, мы б прыцягнуць мільярд маленькіх квадратаў. Але што гэта значыць? Што ж, дазвольце мне проста павялічыць у гэтай фатаграфіі. Калі ў мяне ёсць нешта, што выглядае як гэта цяпер, гэта чатыры байта. 

І такім чынам я мог бы паставіць чатыры чысла тут. Адзін, два, тры, чатыры. Ці я мог бы паставіць чатыры літары або сімвалы. "Гэй!" можа пайсці прама там, таму што кожная з літар, мы абмяркоўвалі раней, можа быць прадстаўлена з васьмю бітамі або ASCII або байт. Такім чынам, іншымі словамі, вы можаце паставіў 8 мільярдаў рэчы ўнутры гэтай адной палкі памяці. Цяпер тое, што гэта значыць, каб пакласці рэчы назад каб спіна да спіны ў памяці, як гэта? Гэта тое, што праграміст маглі б назваць "масіў". У кампутарнай праграме, вы не думаеце, аб асноўных апаратных сродкаў, само па сабе. Вы проста думаеце пра сябе як якія маюць доступ да агульнай складанасці ў мільярд байтаў, і вы можаце ўсё, што вы хочаце з ім. Але для зручнасці гэта наогул карысна каб захаваць сваё права памяці побач адзін з адным, як гэта. Так што калі я павялічыць на this-- таму што мы, вядома, не збіраецца прыцягнуць мільярд маленькіх squares-- давайце выкажам здагадку, што гэтая плата ўяўляе што палка памяці ў цяперашні час. І я проста зрабіць так шмат, як мой Маркер заканчваецца тым, што даў мне тут. Так што цяпер у нас ёсць палка памяці на борце што ёсць адзін, два, тры, чатыры, пяць, шэсць, адзін, два, тры, чатыры, пяць, шэсць, seven-- каля таго 42 байта Памяць на агульнай экрана. Дзякуй. Так, зрабіў мой арыфметыка правільна. Так 42 байт памяці тут. Дык што ж гэта на самай справе азначае? Ну, кампутарны праграміст будзе на самой справе, як правіла думаць аб гэтай памяці як адрасна. Іншымі словамі, кожны з іх месца ў памяці, у апаратных сродках, мае унікальны адрас. 

Гэта не так складана, як адзін Brattle Плошчу, Кембрыдж, штат Масачусэтс., 02138. Замест гэтага, гэта проста лік. Гэта байт з нумарам нуль, гэта адзін, гэта два, гэта тры, і гэта 41. Пачакай хвіліну. Я думаў, што я сказаў, 42 хвіліну таму. Я пачаў адлік з нуля, так што гэта на самай справе правільна. Зараз мы не павінны фактычна зрабіць яго у выглядзе сеткі, і калі вы малюеце яго ў выглядзе сеткі Я думаю, што рэчы на ​​самай справе атрымаць трохі ўводзіць у зман. Які праграміст, ў сваім уласным розуме, як правіла, думаюць пра гэта памяці, як гэта так жа, як стужкі, як кавалак ліпкай стужкай што проста ідзе далей і далей назаўжды або пакуль не скончацца памяці. Такім чынам, больш распаўсюджаным спосабам прыцягнуць і думаць толькі пра памяць было б, што гэта байта нуль, адзін, два, тры, а затым кропка, кропка, кропка. І ў вас ёсць ўсяго 42 такіх байтаў, нават хоць фізічна ён можа на самай справе быць чымсьці больш, як гэта. 

Так што калі вы зараз думаеце пра вашай памяці, так як гэта, гэтак жа, як стужкі, гэта тое, што праграміст зноў назвалі б масіў памяці. І калі вы сапраўды хочаце захаваць нешта ў памяці кампутара, Вы ўвогуле робіце захоўвання рэчаў спіна да спіны спіна да спіны. Такім чынам, мы гаворым пра лічбы. І калі я хацеў, каб вырашыць праблемы як чатыры, адзін, тры, два, хоць я быў проста малюнак толькі лічбы чатыры, адзін, тры, два на борце, кампутар сапраўды гэтую ўстаноўку ў памяці. 

А што было б побач з два ў памяці кампутара? Ну, няма ніякага адказу на гэта. Мы сапраўды не ведаем. І да таго часу пакуль кампутар не патрэбны, ён не павінен клапаціцца, што будзе далей да лікаў гэта сапраўды клапоціцца аб. І калі я ўжо казаў раней, што кампутар можна глядзець толькі па адным адрасе ў той час, гэта свайго роду чаму. 

Не ў адрозненне ад запісу плэер і счытвальная галоўка толькі будучы ў стане глядзець на пэўны канаўка ў фізічнай запісы старой школы у той час, аналагічным чынам можа кампутар дзякуючы яе цэнтральнага працэсара і яго камплект Intel інструкцыя, сярод якіх інструкцыі счытваецца з памяці або захаваць memory-- кампутар можа толькі глядзець у адным месцы пры time-- часам іх спалучэнне, але на самой справе толькі ў адным месцы ў той час. Таму, калі мы робім гэтыя розныя алгарытмы, Я не проста пісаць у vacuum-- чатыры, адзін, тры, два. Гэтыя лічбы на самай справе належаць дзесьці фізічнай памяці. Так што ёсць малюсенькае транзістараў або нейкі электронікі пад капот захоўвання гэтых значэнняў. 

А ў агульнай складанасці, колькі біт ўдзел прама зараз, каб быць ясна? Так што гэта чатыры байта, або зараз гэта ўсяго 32 біта. Так што ёсць на самой справе 32 нулёў і тыя складнікі гэтыя чатыры рэчы. Там нават больш тут, але зноў мы не клапоцімся пра гэта. 

Так што цяпер давайце зададзім іншы Пытанне выкарыстання памяці, таму што гэта ў канцы дня ў дысперсіі. Незалежна ад таго, што мы маглі б зрабіць з кампутар, у канцы дня апаратныя сродкі па-ранейшаму тое ж самае пад капотам. Як бы я трымацца слова тут? Ну, слова ў кампутары, як "Гэй!" будзе захоўвацца так жа, як гэта. І калі вы хацелі больш слова, вы можаце проста перазапісаць, што і сказаць нешта як "прывітанне" і крама, які тут. 

І вось тут таксама, гэта contiguousness на самай справе з'яўляецца перавагай, таму што кампутар можа проста чытаць справа налева. Але вось пытанне. У кантэксце гэтага слова, ч-е-л-л-о, клічніка, як, магчыма, кампутар ведае, дзе слова пачынаецца і дзе канчаецца слова? У кантэксце лікаў, як робіць кампутар ведаю, як доўга паслядоўнасць нумара або дзе яна пачынаецца? Што ж, аказваецца out-- і мы не будзем занадта шмат у гэты ўзровень detail-- кампутары перамяшчаць рэчы вакол у памяці літаральна праз гэтыя адрасы. Такім чынам, у кампутары, калі вы напісанне кода для захоўвання рэчаў як і словы, што вы на самой справе робіць друкуе Выразы, якія памятаюць, дзе ў памяць кампутара гэтыя словы. Такім чынам, дазвольце мне зрабіць вельмі, вельмі просты прыклад. 

Я збіраюся ісці наперад і адкрыць простую тэкставую праграму, і я збіраюся стварыць файл з імем hello.c. Большая частка гэтай інфармацыі мы Не буду ўдавацца ў вельмі падрабязна, але я збіраюся напісаць Праграма ў тым жа самым мове, C. Гэта значна больш страшным, Я б сказаў, чым нуля, але гэта вельмі падобна па духу. На самай справе, гэтыя фігурная braces-- вы можаце выгляд думаю пра тое, што я толькі што зрабіў, як гэта. 

Давайце зробім гэта, на самой справе. Калі зялёны сцяг пстрыкнуў, выканайце наступныя дзеянні. Я хачу, каб раздрукаваць "прывітанне". Так што цяпер гэта псевдокод. Я збольшага размываючы мяжы. У C, гэтая мова я кажу О, гэтая лінія друку прывітанне фактычна становіцца "Printf" з некаторыя круглыя ​​дужкі і кропка з коскі. 

Але гэта дакладна такая ж ідэя. І гэта вельмі зручна "Калі зялёны сцяг пстрыкнуў" становіцца значна больш аркан "INT галоўны несапраўдным." І гэта на самай справе не мае ніякага адлюстравання, так што я буду проста ігнараваць гэта. Але фігурныя дужкі падобныя да выгнутыя часткі галаваломкі, як гэта. 

Так што вы можаце адгадаць выгляд. Нават калі вы ніколі не праграмавалі раней, што робіць гэтая праграма, верагодна, рабіць? Магчыма друкуе прывітанне з клічнікам. 

Дык давайце паспрабуем гэта. Я збіраюся захаваць яго. І гэта, зноў жа, вельмі старая школьная среда. Я не магу націснуць, я не магу перацягнуць. Я павінен ўводзіць каманды. Таму я хачу, каб запусціць сваю праграму, так што Я мог бы зрабіць гэта, як hello.c. Гэта файл я пабег. Але пачакайце, я прапускаю крок. Што мы гаворым, з'яўляецца неабходным крок для мовы як C? Я толькі што напісаў крыніца код, але што мне трэба зрабіць? Так, мне патрэбен кампілятар. Так што на маім Mac тут, у мяне ёсць Праграма пад назвай GCC, GNU C кампілятар, якая дазваляе мне рабіць this-- паварот мой зыходны код у, мы будзем называць яго, машынны код. 

І я бачу, што, яшчэ раз, як паказана ніжэй, гэтыя з'яўляюцца нулі і адзінкі я проста створаны з майго зыходнага кода, усе нулі і адзінкі. І калі я хачу працаваць мой program-- гэта адбываецца называцца a.out для гістарычныя reasons-- "прывітанне". Я магу запусціць яго зноў. Прывітанне, прывітанне, прывітанне. І гэта, здаецца, працуе. 

Але гэта азначае, што дзесьці ў маім памяць кампутара словы ч-е-л-л-о, клічнікам. І аказваецца, гэтак жа, як і ў бок, што такое кампутар, як правіла, зрабіць так, што ён ведае, дзе рэчы пачынаюць і end-- гэта збіраецца паставіць спецыяльны сімвал тут. І канвенцыя павінна паставіць нумар нуль у канцы слова так што вы ведаеце, дзе гэта на самай справе сканчаецца, так што вы ня працягваць друкаваць больш і больш сімвалаў, чым вы на самой справе маюць намер. 

Але тут ежа на дом, нават хоць гэта даволі аркан, з'яўляецца тое, што гэта ў канчатковым рахунку адносна проста. Вы атрымалі выгляд стужкі, нарыхтоўкі прастору, на якім можна пісаць лісты. Вы проста павінны мець спецыяльны сімвал, як заўгодна лік нуль, каб пакласці ў канцы вашы словы так, што кампутар ведае, ой, я павінен спыніць друк пасля таго, як Я бачу клічнік. Таму што наступная рэч там гэта значэнне ASCII нуля, або нулявы сімвал, як хтосьці назаве яго. Але ёсць свайго роду праблемы тут, і давайце вярнуцца чыслах на хвіліну. Выкажам здагадку, што я, на самай справе, ёсць масіў лікаў, і выкажам здагадку, што Праграма Я пішу гэта як клас кніга для настаўніка і настаўнікаў класе. І гэтая праграма дазваляе яму ці ёй каб набраць балы сваіх вучняў на віктарынах. І выкажам здагадку, што студэнт атрымлівае 100 на іх першай віктарыны, можа быць, як 80 на наступны, то 75, а затым 90 на чацвёртай віктарыны. 

Такім чынам, у гэты момант у гісторыі, масіў мае памер чатыры. Там абсалютна больш памяці ў кампутар, але масіў, так бы мовіць, мае памер чатыры. Выкажам здагадку зараз, што настаўнік хоча прызначыць пяты тэст на клас. Ну, адна з рэчаў, якія ён ці яна будзе мець, каб зрабіць цяпер захоўваць дадатковую каштоўнасць тут. Але калі масіў настаўнік мае Створаны ў гэтай праграме, бо яго аб'ём для, адна з праблем з масівам з'яўляецца тое, што Вы не можаце проста працягваць дадаваць да памяці. Таму што, калі іншая частка Праграма мае слова "эй" прама там? 

Іншымі словамі, памяць можа быць выкарыстоўваецца для чаго-небудзь у праграме. А калі загадзя я надрукаваў, эй, Я хачу, каб ўвод чатырох балаў віктарыны, яны маглі б пайсці тут і тут. І калі вы раптам перадумаеце пазней і сказаць, што я хачу пяты віктарыны кошт, вы не можаце проста пакласці яго туды, куды вы хочаце, таму што, калі гэта памяці выкарыстоўваецца для чаго-то else-- іншую праграму ці якой-небудзь іншай асаблівасцю праграмы што вы працуеце? Такім чынам, вы павінны думаць загадзя як вы хочаце захоўваць вашыя дадзеныя, таму што цяпер вы пафарбаваныя сябе ў лічбавай кут. 

Такім чынам, замест таго, каб настаўнік мог бы кажуць, пры напісанні праграмы захоўваць яго ці яе класаў, вы ведаеце, што? Я буду прасіць, пры напісанні маёй праграмы, што я хачу, нуль, адзін, два, тры, чатыры, пяць, шэсць, восем класаў у агульнай складанасці. Так адзін, два, тры, чатыры, пяць, шэсць, сем, восем. Выкладчык можа проста празмерна вылучаць памяці пры напісанні сваю праграму і сказаць, вы ведаеце, што? Я ніколі не буду прызначаць больш чым праз восем віктарын на працягу семестра. Гэта проста вар'яцтва. Я ніколі не буду вылучаць гэта. Так што такім чынам ён ці яна мае гнуткасць для захоўвання студэнцкіх балаў, як 75, 90, і, магчыма, адзін дадатковы, дзе студэнт атрымаў дадатковы крэдыт, 105. 

Але калі настаўнік ніколі выкарыстоўвае гэтыя тры прасторы, ёсць інтуітыўнае навынос тут. Ён ці яна проста марнаваць прастору. Такім чынам, іншымі словамі, ёсць гэты агульны кампраміс у праграмаванні дзе вы можаце альбо вылучыць роўна столькі памяці, колькі вы хочаце, патэнцыял росту якога з'яўляецца тое, што ты супер efficient-- вы не быць марнатраўным на all-- але ніжняя бок якога з'яўляецца тое, што калі вы зменіце сваё меркаванне, калі з дапамогай праграмы, якую вы хочаце захаваць больш дадзеных, чым першапачаткова меркавалася. 

Таму, магчыма, гэта рашэнне, то, пісаць свае праграмы такім чынам, што яны выкарыстоўваюць больш памяці чым яны на самой справе трэба. Такім чынам, вы не збіраецеся нарвацца на гэтую праблему, але вы быць марнатраўным. І чым больш памяці ваша праграма выкарыстоўвае, як мы абмяркоўвалі ўчора, тым менш памяць, якая даступная для іншых праграм, тым хутчэй ваш кампутар можа запаволіць ўніз з-за віртуальнай памяці. І таму ідэальным рашэннем можа быць тое, што? 

Пад-вылучаюць здаецца дрэнным. Празмерная здаецца дрэнна Вылучэнне. Так што можа быць лепшым рашэннем? Пераразмеркаванне. Будзьце больш дынамічным. Не прымушаць сябе выбраць апрыёры, у самым пачатку, што вы хочаце. І, вядома, не празмерна вылучаць, каб ня быць марнатраўным. 

І так, каб дасягнуць гэтай мэты, мы трэба кінуць гэтую структуру дадзеных, так бы мовіць, прэч. І так, што праграміст як правіла, выкарыстоўваюць нешта не называецца масіў, але звязаны спіс. Іншымі словамі, ён ці яна будзе пачынаюць думаць аб сваёй памяці як які з'яўляецца свайго роду форму, што яны можна зрабіць наступным чынам. Калі я хачу, каб захаваць нумар у program-- таму верасня Я даў маім студэнтам віктарыны; мне трэба для захоўвання першай віктарыны студэнтаў, і яны атрымалі 100 на it-- I задам мой кампутар, шляхам праграмы я напісана, для аднаго кавалка памяці. І я буду захоўваць нумар 100 у ім, і гэта ўсё. 

Затым некалькі тыдняў праз калі я атрымаю свой другі віктарыны, і настаў час, каб набраць у тым, што 90%, я збіраюся каб спытаць кампутар, эй, кампутар, можа ў мяне ёсць яшчэ адзін кавалак памяці? Гэта збіраецца даць мне гэта пусты кавалак памяці. Я збіраюся паставіць у лік 90, але ў маёй праграме неяк або other-- і мы не будзем турбавацца аб Сінтаксіс this-- мне трэба неяк ланцуг гэтыя рэчы разам. І я прыкаваць іх разам з што выглядае як страла тут. 

Трэці тэст, які прыходзіць, Я збіраюся сказаць, эй, кампутар, дайце мне яшчэ адзін кавалак памяці. І я збіраюся пакласці ўніз Як бы там ні было, як 75, і я павінен ланцуга гэтай разам зараз неяк. Чацвёрты віктарыны прыходзіць разам, і, магчыма, што гэта бліжэй да канца семестра. І да таго моманту мая праграма можа быць з выкарыстаннем памяці паўсюль, ва ўсім фізічна. І вось як раз для пінкоў, я збіраецца зрабіць гэта наперад quiz-- я забыўся, што гэта было; Я думаю, можа быць, 80 або something-- шлях тут. 

Але гэта нармальна, таму што выяўленча Я збіраюся намаляваць гэтую лінію. Іншымі словамі, у рэчаіснасці, у апаратным забеспячэнні вашага кампутара, першы рахунак можа у канчатковым выніку тут, таму што гэта прама ў пачатку семестра. Наступным можа ў канчатковым выніку тут таму што крыху часу прайшло і праграма працягвае працаваць. Наступны паказчык, які быў 75, можа быць тут. І апошняя ацэнка можа быць 80, які знаходзіцца тут. 

Такім чынам, у рэчаіснасці, фізічна, гэта можа быць якая памяць кампутара выглядае наступным чынам. Але гэта не з'яўляецца карысным псіхічнага парадыгма для праграміста. Чаму вы павінны клапаціцца, дзе клямка вашыя дадзеныя ў канчатковым выніку? Вы проста жадаеце захаваць дадзеныя. 

Гэта накшталт як нашай дыскусіі раней малявання куба. Чаму вы ўсё роўна, што кут куба і як трэба павярнуць, каб прыцягнуць яго? Вы проста хочаце куб. Сапраўды гэтак жа тут, вы проста хачу, каб клас кнігі. Вы проста хочаце, каб думаць аб гэта як спіс нумароў. Хто клапоціцца, як гэта рэалізаваны ў апаратных сродках? 

Такім чынам, абстракцыя ў цяперашні час гэтая карціна тут. Гэта звязана спіс, як і праграміст назваў бы гэта, паколькі ў вас ёсць спіс, відавочна лікаў. Але гэта звязана выяўленча пасродкам гэтых стрэлак, і ўсе гэтыя стрэлкі are-- пад капот, калі вам цікава, Нагадаем, што наша фізічнае абсталяванне мае адрасы нуль, адзін, два, тры, чатыры. Усе гэтыя стрэлы як карта або накіравання, дзе, калі 90 is-- прама цяпер Я павінен разлічваць. 

Нуль, адзін, два, тры, чатыры, пяць, шэсць, сем. Падобна на тое, што 90 знаходзіцца памяць адрас нумар сем. Усе гэтыя стрэлы з'яўляецца як маленькі кавалак паперы які дае напрамках да праграма, якая кажа, што справядліва гэтай карце каб дабрацца да месца сем. І там вы знойдзеце другі студэнцкі віктарыны рахунак. Між тым, 75-- калі я буду працягваць гэта, гэта сем, восем, дзевяць, 10, 11, 12, 13, 14, 15. 

Гэтая іншая стрэлка проста ўяўляе карта памяці на месца 15. Але зноў жа, як правіла, праграміст робіць не клапоцяцца пра гэта узроўні дэталізацыі. І ў большасці кожнага праграмавання мова сёння, праграміст нават не будзе ведаць, дзе ў памяці гэтыя лічбы на самай справе. Усё, што ён ці яна павінен клапаціцца пра тое, што яны нейкім чынам звязаны адзін з адным ў структуры дадзеных, як гэта. 

Але аказваецца, не каб атрымаць занадта тэхнічны. Але толькі таму, што мы можам, магчыма, дазволіць сабе мець гэтую дыскусію тут, Выкажам здагадку, што мы зноў гэтае пытанне тут масіва. Давайце паглядзім, калі мы збіраемся тут шкадуюць. Гэта 100, 90, 75, і 80. 

Дазвольце мне коратка зрабіць гэтую заяву. Гэта масіў, і зноў, характэрнай прыкметай якіх масіва з'яўляецца тое, што ўсе вашыя дадзеныя назад спіна да спіны ў memory-- літаральна адзін байт або, можа быць чатыры байта, некаторы фіксаваны лік байтаў прэч. У звязаным спісе, які мы маглі б зрабіць як гэта, пад капотам, які ведае дзе, што матэрыял? Ён нават не трэба паступаць так. Некаторыя дадзеныя могуць быць назад налева там. Вы нават не ведаеце. 

І так з масівам, у вас ёсць асаблівасць вядомая як выпадковага доступу. А якія сродкі адвольнага доступу што кампутар можа скакаць імгненна у любое месца ў масіве. Чаму? Паколькі кампутар ведае што першае месцазнаходжанне нуль, адзін, два, і тры. 

І таму, калі вы хочаце, каб перайсці ад гэты элемент да наступнага элементу, вы ў літаральным сэнсе, у розум кампутара, проста дадайце адзін. Калі вы хочаце, каб перайсці да трэцяга элементу, проста дадайце одно-- наступны элемент, проста дадайце. Тым не менш, у гэтай версіі гісторыі, выкажам здагадку, кампутар у цяперашні час шукае на або маем справу з нумарам 100. Як вы атрымліваеце да наступнага клас у класе кнігі? 

Вы павінны прыняць сем крокі, якія адвольна. Для таго, каб дабрацца да наступнай, вы павінны прыняць яшчэ восем крокаў, каб дабрацца да 15. Іншымі словамі, гэта не пастаянны зазор паміж лікамі, і таму ён проста бярэ Кампутар больш часу кропка. Кампутар павінен шукаць праз памяць у парадку каб знайсці тое, што вы шукаеце. 

Такім чынам, у той час як масіў мае тэндэнцыю быць хутка дадзеныя structure-- таму што вы можа літаральна зрабіць простую арыфметыку і трапіць туды, куды вы хочаце, дадаўшы да яго адзін, для instance-- звязаны спіс, вы ахвяруеце гэтую функцыю. Вы не можаце проста ісці ад першай на другі трэці чацвёрты. Вы павінны прытрымлівацца карце. Вы павінны зрабіць дадатковыя крокі, каб дабрацца да тых значэнняў, якія Здавалася б, даданне кошту. Такім чынам, мы плацім цану, але тое, што было асаблівасць, што Дэн шукаў тут? Што робіць звязаны спіс па-відаць, дазваляюць нам рабіць, які быў паходжанне гэтая канкрэтная гісторыя? 

Вы маеце рацыю. Дынамічны памер для яго. Мы можам дадаць да гэтага спісу. Мы можам нават скараціць спіс, так што мы толькі выкарыстоўваючы столькі памяці як мы на самай справе хочам і так мы ніколі не празмерна размеркавання. 

Цяпер проста, каб быць сапраўды NIT-пераборлівыя, ёсць скрытыя выдаткі. Такім чынам, вы не павінны проста дайце мне пераканаць вы, што гэта з'яўляецца пераканаўчым кампрамісам. Там іншая прыхаваная кошт тут. Перавага, каб быць ясна, з'яўляецца тое, што мы атрымліваем дынамічнасць. Калі я хачу яшчэ адзін элемент, я магу проста намаляваць яго і паставіць шэраг там. І тады я магу звязаць яго з выявай тут, у той час як тут, зноў жа, калі я афарбаваны сябе ў кут, калі нешта яшчэ ўжо выкарыстоўвае памяць тут, я не пашанцавала. Я намаляваў сябе ў кут. 

Але тое, што схаваны стаіць у гэтай карціне? Гэта не проста сума часу, якое патрабуецца ісці адсюль тут, які сем крокаў, а затым восем крокаў, што больш чым адзін. Што яшчэ адна прыхаваная кошт? Не толькі час. дадатковая інфармацыя неабходна для дасягнення гэтай фатаграфіі. 

Так, гэтая карта, гэтыя маленькія шматкі паперы, як я працягваю апісваць іх як. Гэтыя arrows-- тыя не з'яўляюцца свабоднымі. Computer-- вы ведаеце, тое, што кампутар мае. Ён мае нулі і адзінкі. Калі вы хочаце, каб прадстаўляць стралу або А карту або нумар, вам трэба некаторы колькасць памяці. Так што з другога цаной, якую вы плаціць за звязанага спісу, агульная інфарматыка рэсурс, таксама прастору. 

І на самай справе так, так часта, сярод кампрамісы у распрацоўцы праграмнай інжынерыі сістэмы час і space-- два з вашых інгрэдыентаў, два з вашых самых дарагіх інгрэдыентаў. Гэта каштавала мне больш часу таму што я павінен прытрымлівацца гэтай карце, але гэта таксама стаіць мне больш месца таму што я павінен трымаць гэтую карту вакол. Такім чынам, надзея, як мы свайго роду абмяркоўваўся на працягу ўчорашняга дня і сёння, у тым, што выгады пераважаць выдаткі. 

Але няма ніякага відавочнага рашэння тут. Можа быць, гэта better-- а-ля хуткі і брудны, а Карым прапанаваў earlier-- кінуць памяць на праблему. Проста купіце больш памяці, менш думаць цяжка аб рашэнні праблемы, і вырашыць яе ў больш просты спосаб. І сапраўды раней, калі мы гаварылі пра кампрамісы, яно не было месца ў кампутар і час. Гэта быў час, распрацоўшчык, які гэта яшчэ адзін рэсурс. 

Такім чынам, яшчэ раз, менавіта гэтае ўраўнаважванне спрабуючы вырашыць, які з гэтых рэчаў вы гатовыя выдаткаваць? Які з'яўляецца найменш дарагім? Што дае лепшыя вынікі? Так? 

Сапраўды. У гэтым выпадку, калі вы прадстаўлення лікаў у maps-- іх называюць на многіх мовах "Паказальнікі" ці "адраса" - гэта падвойнае прастору. Гэта не павінна быць так дрэнна, як двайны, калі Прама зараз мы проста захоўвання лікаў. Выкажам здагадку, што мы захоўвалі запісы пацыента ў hospital-- так называе Пірсана, нумары тэлефонаў, нумары сацыяльнага страхавання, доктар гісторыя. Гэта поле можа быць шмат, значна больш, і ў гэтым выпадку малюсенькая паказальнік, адрас наступная element-- гэта не мае вялікага значэння. Гэта такая махры кошт не мае значэння. Але ў гэтым выпадку, так, гэта падваенне. Добрае пытанне. 

Давайце пагаворым пра той час, а ледзь больш канкрэтна. Што час працы пошуку гэты спіс? Выкажам здагадку, што я хацеў шукаць праз усе класы студэнтаў, і ёсць п класаў ў гэтай структуры дадзеных. Тут, таксама, мы можам пазычаць слоўнікавы запас раней. Гэта лінейная структура дадзеных. 

Big O п з'яўляецца тое, што патрабуецца, каб атрымаць да канца гэтай структуры дадзеных, whereas-- і мы не бачылі гэта before-- масіў дае вам што называецца сталай часу, што азначае, адзін крок ці два кроку або 10 steps-- не мае значэння. Гэта фіксаваны лік. Яна не мае нічога агульнага з памер масіва. І прычына гэтага, зноў жа, з адвольным доступам. Кампутар можа проста неадкладна перайсці на іншае месца, таму што яны ўсё роўна адлегласць ад усяго астатняга. Там няма мыслення ўдзельнічае. Добра. Так што, калі я магу, я паспрабую намаляваць два фінальных малюнкаў. Вельмі часта адзін вядомы як хэш-табліцу. Такім чынам, каб матываваць гэтую дыскусію, дайце мне падумаць пра тое, як гэта зрабіць. 

Так як наконт гэтага? Выкажам здагадку, што задача мы хочам вырашыць прама цяпер ажыццяўляе ў dictionary-- так цэлая куча ангельскіх слоў або любы іншы. І мэта складаецца ў тым, каб быць у стане адказаць пытанні форме гэтае слова? Так што вы хочаце рэалізаваць праграма праверкі арфаграфіі, проста як фізічны слоўнік што вы можаце паглядзець рэчы ст. Выкажам здагадку, я зрабіць гэта з дапамогай масіва. Я мог бы зрабіць гэта. 

І выкажам здагадку, што словы яблык і банан і дыня. І я не магу думаць пра садавіну якія пачынаюцца з D, так што мы проста будзе мець тры садавіны. Так што гэта масіў, і мы захоўваць усе гэтыя словы у гэтым слоўніку як масіў. Пытанне, тады, як яшчэ Вы маглі б захоўваць гэтую інфармацыю? 

Ну, я свайго роду падман тут, таму што кожная з гэтых літар у слове сапраўды індывідуальны байт. Так што, калі я сапраўды хацеў быць Ніт-пераборлівыя, я павінен сапраўды быць падзяліўшы гэта ўверх у значна меншыя кавалкі памяці, і мы маглі б зрабіць менавіта гэта. Але мы будзем працаваць у тая ж праблема, як і раней. Што калі, як Merriam Webster або Оксфард робіць кожны год-- яны дадаюць слова да dictionary-- мы не робім абавязкова хочуць маляваць сябе у кут з масівам? 

Так што замест таго, каб, можа быць, разумней падыход гэта пакласці яблык у сваім уласным вузле або скрынцы, як бы мы сказалі, банан, і то тут мы маем дыню. І мы струна гэтыя рэчы разам. Так што гэта масіў, гэта звязаны спіс. Калі вы не можаце досыць бачыць, гэта проста кажа "масіў", і гэта кажа, што "спіс." 

Такім чынам, мы маем тое ж самае дакладныя пытанні, як і раней, у выніку чаго мы цяпер маем дынамізм ў нашым звязаным спісе. Але ў нас ёсць даволі павольны слоўнік. Выкажам здагадку, я хачу, каб шукаць слова. Гэта можа заняць мне вялікую O п крокі, таму што слова можа быць ўвесь шлях у канцы спіс, як дыня. І атрымліваецца, што у праграмаванні, сартаваць Грааля дадзеных структуры, нешта што дае вам пастаяннае час як масіў але гэта па-ранейшаму дае вам дынамізм. 

Так што мы можам мець лепшае з абодвух сьветаў? І на самай справе, ёсць нешта называецца хэш-табліцу што дазваляе рабіць менавіта што, хоць і прыблізна. Хэш-табліца ўяўляе сабой спрактыкаваней Структура дадзеных, якія мы можа думаць, як спалучэнне array-- і я збіраюся намаляваць яго як this-- і звязаныя спісы што я буду маляваць, як гэта тут. 

І тое, як гэтая рэч працуе наступным чынам. Калі гэты now-- хэш table-- мая трэцяя структура дадзеных, і я хачу, каб захаваць Слова ў гэтым, я не хачу проста захоўваць усе словы спіна да спіны, каб спіна да спіны. Я хачу выкарыстоўваць некаторыя частка інфармацыі пра словы, якія дазволяць мне атрымаць яго там, дзе гэта хутчэй. 

Так што, улічваючы словы яблык і бананы і дыня, Я наўмысна выбраў гэтыя словы. Чаму? Нешта прынцыпова адрозніваецца аб трох? Што відавочна? Яны пачынаюцца з розных літар. 

Такім чынам, вы ведаеце, што? Замест таго, каб змясціць усе мае словы ў той жа вядро, так бы мовіць, як у адным вялікім спісе, чаму не Я па крайняй меры паспрабаваць аптымізацыю і зрабіць мае спісы 1/26 датуль. пераканаўчы аптымізацыя можа быць, чаму не Я-- пры ўстаўцы словы у гэтую структуру дадзеных, ў памяць кампутара, чаму я не аддаў усё 'а' словы тут, усе 'Коммерсанта' словы тут, і ўсё 'C' словы тут? Так што гэта ў канчатковым выніку пакласці яблык тут, банан тут, дыню тут, і гэтак далей. 

І калі ў мяне ёсць дадатковы Слова like-- што іншае? Яблык, банан, груша. Любы думаю плёну якая пачынаецца з А, У або З? Blueberry-- дасканалым. Гэта будзе ў канчатковым выніку тут. І таму мы, здаецца, ёсць нязначна лепшае рашэнне, таму што цяпер, калі я хачу шукаць яблык, я first-- Я не проста апусканне ў маёй структуры дадзеных. Я не апускаецеся у памяць майго кампутара. Я першы погляд на першую літару. 

І гэта тое, што кампутар вучоны сказаў бы. Вы хэш ў вашай структуры дадзеных. Вы бераце свой уклад, які ў гэты выпадак з'яўляецца слова, як яблык. Вы аналізуеце яго, гледзячы на першая літара ў гэтым выпадку, тым самым хэшавання. Хэш ўяўляе сабой агульны тэрмін, у выніку чаго вы бераце нешта ў якасці ўваходных дадзеных і вы робіце некаторы выснову. І выхад у тым, выпадак размяшчэнне Вы хочаце знайсці, першы месца, другое месца, трэцяе месца. Такім чынам, уваход яблык, выхад першага. Уваход банан, Выснова павінен быць другім. Уваход дыня, выснова павінен быць трэцім. Уваход чарніца, Выснова павінен зноў быць другім. І гэта тое, што дапаможа вам прыняць цэтлікі праз вашу памяць для таго, каб дабрацца да слоў або дадзеныя больш эфектыўна. 

Зараз гэта скарачае наш час патэнцыйна па столькі, колькі адзін з 26, таму што калі выказаць здагадку, што вы мець столькі «а» словы, як "Z" словы, як "Q" слоў, якія на самай справе не realistic-- вы будзеце мець перакос па некаторыя літары alphabet-- але гэта было б інкрыментны Падыход, які сапраўды дазваляе вы, каб дабрацца да слоў значна хутчэй. І на самай справе, складаны праграма, то Googles свету, Facebooks з world-- яны будуць выкарыстоўваць хэш-табліцу для многіх розных мэтаў. Але яны не былі б настолькі наіўны, каб проста паглядзець на першую літару у яблык ці банан ці груша або дыня, таму што, як вы можаце бачыць гэтыя спісы могуць атрымаць яшчэ доўга. 

І так што гэта яшчэ можа быць свайго роду з linear-- так накшталт павольна, як з вялікім O п што мы абмяркоўвалі раней. Так што рэальная добрая Хэш-табліца будзе do-- ён будзе мець значна большы масіў. І гэта будзе выкарыстоўваць значна больш складаныя функцыі хэшавання, так што гэта не проста глядзець на "а". Можа быць, ён глядзіць на "а-р-р-л-е" і нейкім чынам пераўтворыць гэтыя пяць літар у тым месцы, дзе яблык павінна быць захавана. Мы проста па наіўнасці, выкарыстоўваючы літару 'A' у адзіночку, таму што гэта проста і прыгожа. 

Але хэш-табліцу, у канец, вы можаце думаць ў выглядзе камбінацыі масіў, кожны з якіх мае звязаны спіс, што ў ідэале павінна быць як мага карацей. І гэта не з'яўляецца відавочным рашэннем. На самай справе, большая частка тонкай налады што адбываецца пад капот, калі ажыццяўленне гэтых відаў складаныя структуры дадзеных гэта тое, што з'яўляецца правільным даўжыня масіва? Што такое правільны хэш-функцыя? Як вы захоўваеце рэчы ў памяці? 

Але зразумець, наколькі хутка такога роду дыскусіі ўзрасталі, альбо да гэтага часу, што гэта свайго роду з над галавой у гэты момант, які гэта добра. Але мы пачалі, нагадаем, з праўдзіва нешта нізкага ўзроўню і электронныя. І так гэта зноў-такі гэта тэма абстракцыі, дзе, як толькі вы пачнеце прымаць для як належнае, у парадку, у мяне ёсць it-- фізічнай памяці, ОК, атрымаў яго, кожны фізічнае размяшчэнне мае адрас, ОК, я атрымаў яго, я магу ўявіць гэтыя адрасы як arrows-- Вы можаце вельмі хутка пачаць мець больш складаныя размовы аб тым, у рэшце рэшт, здаецца, што дазваляе нам вырашаць праблемы, такія як пошук і сартавання больш эфектыўна. І будзьце ўпэўненыя, too-- таму што я думаю, што гэта з'яўляецца самым глыбокім мы пайшлі ў некаторыя з гэтых тэм CS proper-- мы зроблена ў паўтара дня на гэты паказаць, што вы, магчыма, як правіла, робяць больш працягу васьмі тыдняў на працягу семестра. 

Любыя пытанні па гэтым? Няма? Добра. Ну, чаму б нам не зрабіць паўзу там, пачаць абед на некалькі хвілін раней, рэзюмэ усяго каля гадзіны? І я буду затрымлівацца трохі з пытаннямі. Тады я буду павінен ісці узяць пару званкоў, калі гэта нармальна. Я ўключу музыку ў той жа час, але абед павінен быць за вуглом.