DAVID Malan: pob hawl. Rydym yn ôl. Felly, yn y segment hwn ar raglennu beth Yr wyf yn meddwl y bydden ni'n ei wneud yn gymysgedd o bethau. Un, yn gwneud ychydig bach o rywbeth dwylo-ar, er ei ddefnyddio yn fwy chwareus environment-- rhaglennu un sy'n dangosol o yn union y mathau o syniadau rydym wedi bod yn siarad am, ond ychydig yn fwy ffurfiol. Dau, yn edrych ar rai o'r y ffyrdd mwy technegol y byddai rhaglennydd mewn gwirionedd yn datrys problemau fel y broblem chwilio ein bod yn edrych ar blaen ac hefyd yn fwy sylfaenol problem diddorol o ddatrys. 

Rydym yn unig cymryd yn ganiataol o gael mynd bod y llyfr ffôn ei ddidoli, ond ei ben ei hun mewn gwirionedd fath o problem caled gyda llawer o wahanol ffyrdd i'w datrys. Felly byddwn yn defnyddio'r rhain fel dosbarth o broblemau cynrychiolydd o bethau y mae y gellid ei datrys yn gyffredinol. Ac yna byddwn yn siarad am yn eithaf manwl beth Gelwir data structures-- ffyrdd ffansi fel rhestrau cysylltiedig a thablau hash a choed sy'n byddai rhaglennydd mewn gwirionedd defnyddio ac yn gyffredinol yn defnyddio ar y bwrdd gwyn i beintio darlun o'r hyn mae ef neu hi rhagweld ar gyfer gweithredu rhyw darn o feddalwedd. 

Felly gadewch i ni wneud yr ymarferol gyfran gyntaf. Felly, dim ond gael eich dwylo budr gyda amgylchedd a elwir scratch.mit.edu. Mae hwn yn offeryn a ddefnyddiwn yn ein dosbarth israddedig. Hyd yn oed er 'i' gynllunio am 12 ac i fyny oedrannau, rydym yn ei ddefnyddio ar gyfer yr hyd rhan o hynny gryn dipyn gan ei fod yn neis, hwyl ffordd graffigol o ddysgu ychydig rhywbeth am raglenni. Felly ewch at y URL, lle byddwch yn Dylai gweld tudalen eithaf fel hyn, a mynd yn ei flaen a chliciwch Ymunwch Scratch ar dde uchaf a dewis enw defnyddiwr a cyfrinair ac yn y pendraw yn cael eich hun yn scratch.mit.edu account--. Yr wyf yn meddwl y byddwn i'n defnyddio hyn fel cyfle cyntaf i ddangos hyn. Mae cwestiwn yn dod i fyny yn ystod yr egwyl am yr hyn y cod mewn gwirionedd yn edrych fel. Ac rydym yn siarad yn ystod yr egwyl am C, mewn particular-- yn enwedig yn lefel is mewn iaith hŷn. Ac yr wyf yn unig oedd yn gyflym Google yn chwilio i ddod o hyd i cod C ar gyfer chwilio deuaidd, mae'r algorithm yr ydym defnyddio i chwilio y llyfr ffôn yn gynharach. Mae'r enghraifft benodol, wrth gwrs, nid yw'n chwilio llyfr ffôn. 'I jyst yn chwilio criw cyfan o rhifau yn gof y cyfrifiadur. Ond os hoffech i ychydig gael gweledol synnwyr o'r hyn mae rhaglenni gwirioneddol iaith yn edrych fel, mae'n edrych yn rhywbeth bach fel hyn. Felly mae'n tua 20-a mwy, 30 neu felly linellau o god, ond y sgwrs rydym yn yn ei gael dros egwyl yn ymwneud â sut y mae hyn mewn gwirionedd cael morphed i mewn i zeros a rhai ac os nid ydych yn gallu mynd yn ôl hynny prosesu ac yn mynd o seroau a rhai Nôl i cod. 

Yn anffodus, mae'r broses mor trawsnewidiol ei fod yn llawer haws dweud na gwneud. Yr wyf yn mynd yn ei flaen ac yn troi mewn gwirionedd y rhaglen honno, Binary Chwilio, i mewn i zeros a rhai trwy gyfrwng rhaglen o'r enw y Cynullydd fy mod digwydd i gael fan hyn yn iawn ar fy Mac. Ac os ydych yn edrych ar y sgrîn yma, gan ganolbwyntio'n benodol ar y chwe golofnau canol yn unig, byddwch yn gweld dim ond sero a rhai. A'r rheini yw'r sero a rhai sy'n cyfansoddi yn union hynny rhaglen chwilio. 

Ac felly mae pob darn o bum ddarnau, pob beit o sero a rhai yma, yn cynrychioli rhai cyfarwyddyd fel arfer y tu mewn cyfrifiadur. Ac yn wir, os ydych chi wedi clywed y slogan marchnata "Intel tu mewn" - hynny, wrth gwrs, yn unig yn golygu bod gennych Intel CPU neu ymennydd y tu mewn i'r cyfrifiadur. A beth mae hynny'n ei olygu i fod yn CPU yw eich bod yn cael set cyfarwyddyd, felly, i siarad. 

Mae pob CPU yn y byd, mae llawer o eu gwneud gan Intel y dyddiau hyn, yn deall yn gyfyngedig nifer o gyfarwyddiadau. A chyfarwyddiadau hynny yn lefel mor isel fel ychwanegu'r rhain ddau rif at ei gilydd, lluoswch y ddau rif at ei gilydd, yn symud y darn hwn o ddata oddi yma i fan hyn yn y cof, ac eithrio hwn gwybodaeth oddi yma i yma yn y cof, ac felly forth-- felly iawn, iawn -Lefel isel, manylion bron electronig. Ond gyda'r rhai mathemategol gweithrediadau ynghyd â'r hyn yr ydym trafodwyd yn gynharach, cynrychiolaeth data fel zeros a rhai, gall byddwch yn cronni popeth y gall cyfrifiadur ei wneud heddiw, boed mae'n testunol, graffigol, cerddorol, neu fel arall. 

Felly, mae hyn yn hawdd iawn i gael ar goll yn y chwyn o gyflym. Ac mae llawer o heriau cystrawennol lle os ydych yn gwneud y symlaf, stupidest o typos dim un o'r rhaglen bydd yn gweithio o gwbl. Ac felly yn hytrach na defnyddio iaith fel C y bore yma, Yr wyf yn meddwl y byddai'n mwy o hwyl i'w wneud mewn gwirionedd rhywbeth mwy gweledol, a oedd yn tra gynlluniwyd ar gyfer plant mewn gwirionedd yn amlygiad perffaith o raglennu gwirioneddol language-- unig fydd yn digwydd i defnyddio lluniau yn lle testun i gynrychioli syniadau hynny. 

Felly, unwaith y byddwch yn wir yn cael cyfrif ar scratch.mit.edu, cliciwch y botwm Create ar dop chwith y safle. A dylech weld amgylchedd fel yr un rwy'n ar fin ei weld ar fy sgrîn fan hyn. A byddwn yn treulio dim ond ychydig ychydig o amser yn chwarae yma. Gadewch i ni weld os na allwn ni i gyd datrys rhai problemau gyda'i gilydd yn y ffordd ganlynol. 

Felly beth byddwch yn gweld o fewn y environment-- ac mewn gwirionedd dim ond gadael mi oedi. A oes unrhyw un ddim yma? Dim yma? IAWN. Felly, gadewch i mi nodi ychydig nodweddion yr amgylchedd hwn. 

Felly, ar gornel chwith uchaf y sgrin, rydym yn cael cam Scratch, felly i siarad. Scratch nid yn unig yn yr enw o hyn iaith rhaglennu; mae hefyd yn enw'r gath sy'n byddwch yn gweld yn ddiofyn yno mewn oren. Mae'n ar lwyfan, felly yn debyg iawn ddisgrifiais y crwban yn gynharach fel bod mewn amgylchedd bwrdd gwyn hirsgwar. byd hwn cath wedi'i gyfyngu yn gyfan gwbl at y petryal i fyny top yno. 

Yn y cyfamser, ar y dde ochr yma, mae'n dim ond ardal sgriptiau, a llechen wag os mynnwch. Dyma lle rydym yn mynd i ysgrifennu ein rhaglenni mewn dim ond hyn o bryd. Ac mae'r blociau adeiladu sy'n rhaid i ni defnyddio i ysgrifennu hyn program-- y pos darnau, os ydych will-- yn y rhai iawn yma yn y canol, ac maen nhw'n categoreiddio gan functionality. Felly, er enghraifft, dw i'n mynd i fynd yn ei flaen a dangos o leiaf un o'r rhain. Rydw i'n mynd i fynd yn ei flaen a chliciwch y categori Rheoli fyny top. 

Felly mae'r rhain yn y categorïau i fyny top. Rydw i'n mynd i glicio ar y categori Rheoli. Yn hytrach, yr wyf i'n mynd i glicio ar y Digwyddiadau categori, yr un i fyny cyntaf top. Ac os hoffech chi ddilyn ar hyd hyd yn oed fel yr ydym yn gwneud hyn, rydych yn eithaf croeso i. Rydw i'n mynd i glicio a llusgo hwn un cyntaf, "pan baner werdd glicio." Ac yna dwi'n mynd i ollwng 'i jyst yn fras ar dop fy llechi gwag. 

A beth sy'n neis am Scratch yw bod y darn pos, pan cyd-gloi gyda pos arall darnau, yn mynd i'w wneud yn llythrennol pa darnau pos rhai yn dweud ei wneud. Felly, er enghraifft, Scratch yn iawn yn awr ar ganol ei fyd. Rydw i'n mynd i fynd yn ei flaen a dewis yn awr, gadewch i ni ddweud, y categori Motion, os hoffech i wneud y same-- categori Motion. Ac yn awr yn sylwi gen i yn ei gyfanrwydd criw o darnau pos yma bod, unwaith eto, math o wneud yr hyn y maent yn ei ddweud. Ac yr wyf i'n mynd i fynd yn ei flaen a llusgo a gollwng y bloc symud i'r dde dros yma. 

Ac yn sylwi bod cyn gynted ag y byddwch yn ei gael yn agos at waelod y "faner werdd clicio botwm ", rhybudd sut llinell wen yn ymddangos, fel pe ei fod bron magnetig, mae eisiau i fynd yno. Dim ond gadael i fynd, a bydd yn snap gyda'i gilydd a bydd y siapiau yn cyd-fynd. Ac yn awr y gallwch efallai bron ddyfalu ble rydym yn mynd â hyn. 

Os edrychwch chi ar y cam Scratch dros yma ac yn edrych i ben ohono, byddwch yn gweld golau coch, yn rhoi'r gorau i arwyddion, a baner werdd. Ac yr wyf i'n mynd i fynd yn ei flaen a gwylio fy screen-- am ddim ond eiliad, pe gallech. Rydw i'n mynd i glicio ar y baner werdd ar hyn o bryd, a symudodd yr hyn sy'n ymddangos i fod yn 10 cam neu 10 picsel, 10 dotiau, ar y sgrin. 

Ac fel nad yw gyffrous, ond gadewch i mi gynnig heb hyd yn oed yn dysgu hyn, dim ond gan ddefnyddio'r hun eich osod intuition-- eich hun fi yn cynnig eich bod yn ffigwr sut i gwneud taith gerdded Scratch dde oddi ar y llwyfan. Wedi iddo wneud lle ar gyfer yr ochr dde y sgrin, yr holl ffordd i'r dde. Gadewch i mi roi o bryd i chi neu felly i ymgodymu â hynny. Efallai y byddwch am i gymryd golwg mewn categorïau eraill o flociau. Iawn. Felly, dim ond i ailadrodd, pan fydd gennym y faner werdd glicio yma a symud 10 o gamau y mae'r Dim ond cyfarwyddyd, bob tro rwy'n cliciwch y faner werdd, beth sy'n digwydd? Wel, mae hynny'n rhedeg fy rhaglen. Felly gallwn i wneud hyn efallai 10 gwaith llaw, ond mae hyn yn teimlo ychydig yn bit hackish, fel petai, lle Dydw i ddim wir yn ddatrys y broblem. Im 'jyst yn ceisio eto ac eto ac eto ac eto nes i mi fath o ddamweiniol cyflawni'r gyfarwyddeb fy mod wedi bwriadu ei gyflawni yn gynt. 

Ond rydym yn gwybod o'n pseudocode yn gynharach fod yna syniad hwn mewn rhaglennu o dolennu, gwneud rhywbeth eto ac eto. Ac felly yr wyf yn gweld bod criw o chi cyrraedd ar gyfer darn pa pos? Ailadrodd tan. Felly gallem wneud rhywbeth hoffi ailadrodd tan. A beth wnaethoch chi ailadrodd tan yn union? 

IAWN. A gadewch i mi fynd gyda un sy'n braidd yn symlach i ychydig funudau'n. Gadewch i mi fynd yn ei flaen ac yn gwneud hyn. Sylwch fod, fel y gall fod gennych Darganfuwyd dan Reolaeth, mae hwn bloc ailadrodd, a oedd yn nid yw'n edrych fel ei fod yn y mawr. Does dim llawer o le yn rhwng y ddau llinellau melyn. Ond fel y gallai rhai ohonoch sylwi, os ydych yn llusgo a gollwng, sylwi sut mae'n tyfu i lenwi'r siâp. 

A allwch chi hyd yn oed yn gwasgu mwy. Bydd yn jyst cadw yn tyfu os chi llusgo a hofran drosto. Ac nid wyf yn gwybod beth sy'n gorau yma, felly gadewch mi o leiaf ailadrodd bum gwaith, ar gyfer enghraifft, ac yna ewch yn ôl i'r llwyfan a chliciwch ar y faner werdd. Ac yn awr yn sylwi nid mae'n eithaf yno. 

Nawr mae rhai ohonoch arfaethedig, fel y Victoria yn unig oedd, ailadrodd 10 gwaith. A bod yn gyffredinol yn ei wneud gael iddo yr holl ffordd, ond na fyddai yna fwy cadarn ffordd na fympwyol figuring faint o symudiadau i wneud? Beth allai fod yn faen gwell na ailadrodd 10 gwaith fod? 

Yeah, felly beth am wneud rhywbeth am byth? Ac yn awr gadewch i mi symud y darn pos y tu mewn yno a chael gwared ar yr un yma. Nawr yn sylwi ni waeth ble Scratch yn dechrau, mae'n mynd at ymyl. Ac diolch byth MIT, sy'n gwneud Scratch, dim ond yn gwneud yn siwr nad oedd erioed yn diflannu yn gyfan gwbl. Gallwch bob amser chrafangia ei gynffon. 

Ac yn union reddfol, pam ei fod yn cadw i symud? Beth sy'n mynd ymlaen fan hyn? Roedd yn ymddangos i wedi dod i ben, ond Yna, os wyf yn codi a llusgo mae'n cadw am fynd draw yno. Pam hynny? Yn wir, mae cyfrifiadur yn llythrennol mynd i wneud yr hyn yr ydych yn dweud iddo ei wneud. Felly, os ydych yn dweud ei fod yn gynharach gwneud y yn dilyn peth am byth, yn symud 10 cam, mae'n mynd i ddal ati ac yn mynd nes i mi gyrraedd yr arwydd stopio coch ac i atal y rhaglen yn gyfan gwbl. 

Felly hyd yn oed os nad ydych yn gwneud gwneud hyn, gallai sut yr wyf yn gwneud symud Scratch gyflymach ar draws y sgrîn? Mwy o gamau, dde? Felly yn hytrach na gwneud 10 ar y tro, beth am yr ydym yn mynd yn ei flaen ac yn ei newid canlynol-- beth fyddech chi'n propose-- 50? Felly, yn awr rwy'n mynd i glicio ar y gwyrdd baner, ac yn wir, mae'n mynd yn gyflym iawn. 

Ac mae hyn, wrth gwrs, yn unig amlygiad o animeiddio. Beth yw animeiddio? 'I' jyst yn dangos i chi y mae dynol criw cyfan o ddelweddau o hyd mewn gwirionedd, iawn, iawn yn gyflym. Ac felly os ydym yn unig yn dweud ef i symud mwy o gamau, rydym yn jyst yn cael yr effaith fydd i newid lle y mae ar y sgrin holl gyflymach fesul uned o amser. 

Nawr bod y sialens nesaf a gynigiais oedd cael ef bownsio oddi ar yr ymyl. Ac heb wybod beth pos darnau exist-- oherwydd mae'n iawn os nad ydych yn cyrraedd y cam o'r challenge-- beth ydych chi eisiau ei wneud yn reddfol? Sut fyddai gennym ef adlam yn ôl a allan, rhwng y chwith a'r dde? 

Yeah. Felly mae angen rhyw fath cyflwr, ac yr ydym fel pe baent wedi conditionals, felly i siarad, o dan y categori Rheoli. Pa un o'r blociau hyn ydym ni yn ôl pob tebyg eisiau? Yeah, efallai "os, yna." Felly sylwi bod ymhlith y blociau melyn gennym yma, mae hyn yn "os" neu'r hyn yn ", arall os" bloc a fydd yn ein galluogi i wneud penderfyniad i wneud hyn neu i wneud hynny. A gallwch hyd yn oed yn nythu yn eu i wneud pethau lluosog. Neu os nad ydych wedi mynd yma eto, fynd yn ei flaen i'r categori Synhwyro ac-- gadewch i ni weld os yw'n yma. 

Felly beth bloc a allai fod yn ddefnyddiol yma i ganfod os ei fod oddi ar y llwyfan? Yeah, yn sylwi bod rhai o'r blociau hyn Gellir parametrized, fel petai. Gellir eu fath o addasu, nid yn wahanol i HTML ddoe gyda nodweddion, lle mae rhinweddau hynny math o addasu ymddygiad tag. Yn yr un modd yma, gallaf chrafangia cyffwrdd hwn bloc a newid a gofyn y cwestiwn, a ydych yn cyffwrdd y llygoden pwyntydd fel y cyrchwr neu a ydych yn cyffwrdd yr ymyl? 

Felly, gadewch i mi fynd i mewn ac yn gwneud hyn. Rydw i'n mynd i chwyddo allan am funud. Gadewch i mi chrafangia darn hwn bos yma, y ​​pos darn hwn, ac rwy'n mynd i sborion nhw i fyny am ychydig funudau'n. Rydw i'n mynd i symud hyn, newid hyn i ymyl cyffwrdd, ac rwy'n mynd i'r cynnig wneud hyn. Felly dyma rai cynhwysion. Rwy'n credu fy mod wedi cael popeth rwyf eisiau. 

A fyddai rhywun yn hoffi cynnig sut yr wyf yn gallu cysylltu y rhain efallai top i'r gwaelod er mwyn datrys y broblem o gael symud Scratch dde i'r chwith i'r dde i chwith i'r dde i'r chwith, pob amser yn bownsio oddi ar y wal? Beth ydw i am ei wneud? Pa bloc ddylwn i gysylltu â "Baner pan werdd clicio gyntaf"? 

Iawn, felly gadewch i ni ddechrau gyda'r "am byth." Beth sy'n digwydd y tu mewn nesaf? Rhywun arall. OK, symud grisiau. Iawn. Wedyn beth? Felly, yna mae'r os. Ac yn sylwi, hyd yn oed er ei fod yn edrych sandwiched gyda'i gilydd yn dynn, bydd yn jyst yn tyfu i'w llenwi. Bydd yn unig neidio mewn lle rwy'n ei eisiau. 

A beth y gallaf oedi rhwng y os a ar y pryd? Mwy na thebyg "os cyffwrdd ymyl." A rhybudd, unwaith eto, mae'n rhy fawr ar ei gyfer, ond bydd yn tyfu i lenwi. Ac yna trowch 15 gradd? Faint o raddau? Yeah, felly bydd 180 troelli mi yr holl ffordd o gwmpas. Felly gadewch i ni weld os cefais hawl hon. Gadewch i mi chwyddo allan. 

Gadewch i mi lusgo Scratch i fyny. Felly mae'n ychydig gwyrgam awr, ond mae hynny'n iawn. Sut y gallaf ailosod ef yn hawdd? Rydw i'n mynd i twyllo ychydig. Felly dwi'n ychwanegu un arall bloc, dim ond i fod yn glir. Rwyf am iddo bwyntio 90 gradd ar y dde at ball, felly Im 'jyst yn mynd i ddweud wrtho i wneud hynny programmatically. A dyma ni yn mynd. Rydym yn ymddangos i wedi gwneud hynny. Mae'n ychydig yn rhyfedd, gan fod mae'n cerdded wyneb i waered. Gadewch i ni alw y nam. Mae hynny'n gamgymeriad. Mae nam yn gamgymeriad mewn rhaglen, mae gwall rhesymegol fy mod i, y dynol, a wnaed. Pam mae e'n mynd ben i waered? Oedd MIT sgriw i fyny neu wnes i? 

Yeah, yr wyf yn golygu, nid yw'n MIT fai. Maent yn rhoi i mi ddarn pos sy'n dweud troi rhyw nifer o raddau. Ac ar awgrym Fictoria, Im 'yn troi 180 gradd, sef y greddf cywir. Ond troi 180 gradd yn llythrennol golygu troi 180 gradd, ac nid yw hynny'n wir yn beth ydw i eisiau, mae'n debyg. Gan fod o leiaf ei fod yn byd dau-ddimensiwn hwn, felly troi yn mynd mewn gwirionedd i troi ef wyneb i waered. 

Rwyf yn ôl pob tebyg am ei defnyddio pa bloc yn lle hynny, ar sail yr hyn a welwch yma? Sut y gallem atgyweiria hon? Yeah, felly gallem dynnu sylw yn y cyfeiriad arall. Ac mewn gwirionedd hyd yn oed dyna ddim yn mynd i fod yn ddigon, oherwydd ein bod dim ond cod caled i bwyntio chwith neu i'r dde. 

Rydych yn gwybod beth y gallem ei wneud? Mae'n edrych fel bod gennym cyfleustra bloc yma. Os byddaf yn chwyddo i mewn, gweler rhywbeth yr ydym yn hoffi yma? Felly mae'n edrych fel MIT Mae gan echdynnu a adeiladwyd i mewn yma. Mae'r bloc yn ymddangos i fod yn gyfwerth y mae blociau eraill, lluosog? 

Mae hyn yn un bloc yn ymddangos i fod yn gyfwerth i'r hwn triawd cyfan o flociau sydd gennym yma. Felly, mae'n troi allan y gallaf symleiddio fy rhaglen drwy gael gwared ar hynny i gyd a dim ond rhoi hyn yn fan hyn. Ac yn awr ei fod yn dal i fod ychydig yn buggy, ac mae hynny'n iawn am y tro. Byddwn yn gadael hynny fod. Ond mae fy rhaglen hyd yn oed symlach, ac mae hyn, hefyd, fyddai cynrychiolydd o gôl mewn programming-- yw gwneud eich cod yn ddelfrydol fel syml, yn gryno ag y bo modd, tra'n parhau i fod mor ddarllenadwy â phosibl. Nid ydych am ei gwneud yn mor gryno ei bod yn anodd ei ddeall. 

Ond sylwi fy mod i wedi disodli tri bloc gydag un, ac mae hynny'n gellid dadlau yn beth da. Rydw i wedi dynnu ymaith y syniad o wirio p'un a ydych yn ar ymyl gydag un bloc yn unig. Nawr gallwn gael hwyl gyda hyn, mewn gwirionedd. Nid yw hyn yn ychwanegu cymaint gwerth deallusol ond gwerth chwareus. Rydw i'n mynd i fynd yn ei flaen ac yn mynnu sain hwn yma. Felly, gadewch i mi fynd yn ei flaen, a gadewch i mi atal y rhaglen am eiliad. Rydw i'n mynd i gofnodi y canlynol, caniatáu mynediad i fy meicroffon. 

Yma rydym yn mynd. Ouch. Gadewch i ni geisio hyn eto. Yma rydym yn mynd. OK, yr wyf yn cofnodi y peth anghywir. Yma rydym yn mynd. Ouch. Ouch. Iawn. Nawr mae angen i mi gael gwared ar hynny. Iawn. 

Felly, yn awr mae gen i cofnodi dim ond "ouch." Felly nawr rwy'n mynd i fynd ymlaen ac yn galw hyn yn "ouch." Rydw i'n mynd i fynd yn ôl i fy sgriptiau, ac yn awr rhybudd mae bloc hwn sy'n cael ei alw chwarae sain "meow" neu chwarae sain "ouch." Rydw i'n mynd i lusgo hyn, a lle ddylwn i roi hyn i greu effaith doniol? Yeah, felly erbyn hyn mae'n fath o buggy, oherwydd erbyn hyn mae hyn block-- sylwi sut mae hyn yn "os ar ymyl, bownsio "yn fath o hunan-gynhwysol. Felly mae angen i mi atgyweiria hon. Gadewch i mi fynd yn ei flaen ac yn gwneud hyn. Gadewch i mi gael gwared o hyn ac yn mynd yn ôl i'n gwreiddiol, yn fwy bwriadol functionality. Felly "os cyffwrdd ymyl, yna" Rwyf am i droi, fel Victoria arfaethedig, 180 gradd. Ac ydw i am chwarae y sain "ouch" yno? 

Yeah, yn sylwi ei fod yn y tu allan y bloc hwnnw melyn. Felly, mae hyn, hefyd, fyddai yn bug, ond rwyf wedi sylwi arno. Felly, yr wyf i'n mynd i lusgo i fyny yma, a rhybudd awron 'i' y tu mewn i'r "os." Felly, y "os" yw math hwn o fel anharddu'r braich tebyg mai dim ond yn mynd i gwneud yr hyn sydd y tu mewn iddo. Felly, yn awr os wyf yn chwyddo allan ar y risg o annoying-- 

CYFRIFIADUR: Ouch, ouch, ouch. 

DAVID Malan: Ac mae'n Bydd dim ond yn mynd ymlaen am byth. Nawr dim ond i gyflymu pethau yma, gadewch i mi fynd yn ei flaen ac yn agor i fyny, gadewch i say-- i adael i mi fynd i rai o fy stwff eu hunain rhag y dosbarth. A gadewch i mi agor i fyny, gadewch i ni ddweud, mae hyn yn un a wnaed gan un o'n cymrodyr addysgu cwpl o flynyddoedd yn ôl. Felly efallai y bydd rhai ohonoch yn cofio y gêm hon o fu, ac mewn gwirionedd mae'n rhyfeddol. Hyd yn oed er ein bod wedi gwneud y symlaf o raglenni ar hyn o bryd, gadewch i ni ystyried beth mae hyn yn mewn gwirionedd yn edrych fel. Gadewch i mi daro chwarae. 

Felly, yn y gêm hon, mae gennym llyffant, a defnyddio'r saeth keys-- mae'n cymryd camau mwy nag yr oeddwn remember-- Mae gen i reolaeth dros broga hwn. A'r nod yw cael ar draws y prysur ffordd heb rhedeg i mewn i'r ceir. A gadewch i ni see-- os byddaf yn mynd i fyny yma, yr wyf yn rhaid i chi aros am log i sgrolio drwy. Mae hyn yn teimlo fel a bug. Mae hwn yn fath o nam. Iawn. Dwi ar hyn yma, yno, ac yna eich bod yn cadw mynd hyd nes y byddwch yn cael yr holl y brogaod i'r padiau lili. Nawr gallai hyn edrych oed yn fwy cymhleth, ond gadewch i ni geisio torri mae hyn i lawr yn feddyliol ac ar lafar i mewn i'w flociau gydran. Felly mae'n debyg pos darn nad ydym wedi gweld eto ond mae hynny'n ymateb i keystrokes, i bethau yr wyf yn taro ar y bysellfwrdd. 

Felly mae'n debyg rhyw fath o bloc sy'n dweud, os allweddol hafal i fyny, yna gwneud rhywbeth gyda Scratch-- efallai ei symud 10 cam y modd hwn. Os allwedd i lawr yn cael ei wasgu, yn symud 10 cam y modd hwn, neu allwedd chwith, yn symud 10 cam y modd hwn, 10 gamau hynny. Rydw i wedi troi yn glir y gath i mewn i broga. Felly dyna yn union ble mae'r gwisgoedd, fel galwadau Scratch iddo- ni dim ond mewnforio llun y broga. 

Ond beth arall sy'n digwydd? Pa llinellau eraill o god, pa darnau pos arall wnaeth Blake, ein cyd-addysgu, defnyddio yn y rhaglen hon, mae'n debyg? Beth sy'n gwneud popeth move-- pa rhaglennu adeiladu? 

Motion, sure-- felly mae'r symud bloc, yn sicr. A beth sy'n bod bloc symud tu mewn, yn fwyaf tebygol? Yeah, rhyw fath o ddolen, efallai am byth bloc, efallai ailadrodd block-- ailadrodd tan bloc. A dyna beth sy'n gwneud y boncyffion a y padiau lili a phopeth arall yn symud yn ôl ac ymlaen. dim ond ei fod yn digwydd ddiddiwedd. 

Pam mae rhai o'r ceir symud yn gyflymach na'r lleill? Beth sy'n wahanol am y rhaglenni hynny? Yeah, yn ôl pob tebyg rhai ohonynt yn cymryd mwy o gamau ar unwaith ac mae rhai ohonynt llai o gamau ar unwaith. A'r effaith weledol yn gyflym yn erbyn araf. 

Beth ydych chi'n meddwl ddigwyddodd? Pan gefais fy broga yr holl ffordd ar draws y stryd a'r afon ar y pad lili, rhywbeth Digwyddodd nodedig. Beth ddigwyddodd cyn gynted ag y gwnes i hynny? Mae'n stopio. rhoi'r gorau i hynny broga, ac Ges i ail broga. Felly beth lluniad fod yn ddefnyddir yno, pa nodwedd? 

Yeah, felly mae rhyw fath o "Os" cyflwr i fyny yno, hefyd. Ac mae'n troi out-- ni welsom this-- ond mae blociau eraill yn yno y gallu dweud, os ydych yn cyffwrdd beth arall ar y sgrin, os ydych yn cyffwrdd y pad lili, "yna." Ac yna dyna pryd yr ydym yn gwneud yr ail broga yn ymddangos. Felly, hyd yn oed er y gêm hon yn bendant dyddiedig iawn, hyd yn oed er ar yr olwg gyntaf mae cymaint yn mynd Blake on-- a nid oedd yn chwip hyn i fyny mewn dau funud, mae'n debyg cymerodd ef sawl oriau i greu'r gêm hon yn seiliedig ar ei gof neu fideos o fersiwn yesteryear ohoni. Ond pob un o'r pethau bychain hyn mynd ar y sgrîn ei ben ei hun berwi i lawr at y rhain yn syml iawn symudiadau neu ddatganiadau constructs-- fel yr ydym wedi trafod, dolenni a amodau, a dyna am y peth. Mae ychydig o nodweddion ffansi eraill. Mae rhai ohonynt yn unig esthetig neu acwstig, fel y synau Fi jyst chwarae gyda. Ond ar gyfer y rhan fwyaf, yr ydych gennym yn yr iaith hon, Scratch, pob un o'r sylfaenol blociau adeiladu eich bod gael yn C, Java, JavaScript, PHP, Ruby, Python, ac unrhyw nifer o ieithoedd eraill. Unrhyw gwestiynau am Scratch? Iawn. Felly, ni fyddwn yn deifio yn ddyfnach i Scratch, er eich bod yn croesawu y penwythnos hwn, yn enwedig os oes gennych blant neu nithoedd a neiaint ac o'r fath, i'w cyflwyno i Scratch. Mae'n mewn gwirionedd yn chwareus rhyfeddol amgylchedd gyda, fel ei awduron yn dweud, nenfydau uchel iawn. Hyd yn oed er ein bod yn dechrau gyda Manylion iawn lefel isel, gallwch chi wir yn ei wneud cryn dipyn ag ef, ac mae hyn yn bosibl arddangosiad o hynny yn union. 

Ond gadewch i ni yn awr yn newid i rai mwy problemau soffistigedig, os gwnewch, a elwir yn "chwilio" ac "Didoli," yn fwy cyffredinol. Cawsom llyfr ffôn hwn earlier-- dyma un arall yn unig ar gyfer discussion-- ein bod yn gallu chwilio yn fwy effeithlon oherwydd o dybiaeth arwyddocaol. A dim ond i fod yn glir, beth dybiaeth oedd fy mod yn gwneud wrth chwilio trwy llyfr ffôn yma? Dyna oedd Mike Smith yn y llyfr ffôn, er fy mod yn Byddai yn gallu trin y senario heb ef yna os Fi jyst stopio cyn pryd. Mae'r llyfr yn nhrefn yr wyddor. A dyna yn hael iawn dybiaeth, gan fod golygu someone-- Rwy'n garedig o dorri cornel, fel yr wyf yn gyflymach oherwydd bod rhywun arall yn gwneud llawer o waith caled i mi. 

Ond beth os y ffôn llyfr yn cael eu heb eu didoli? Efallai Verizon got ddiog, dim ond taflu enwau a rhifau pawb i mewn 'na efallai yn y drefn y maent yn cofrestru ar gyfer y gwasanaeth ffôn. A faint o amser mae'n ei gymryd i mi i ddod o hyd i rywun fel Mike Smith? 1,000 ffôn dudalen book-- faint o tudalennau oes rhaid i mi edrych drwy? 

Pob un ohonynt. Rydych yn fath o allan o lwc. Mae'n rhaid i chi llythrennol i edrych ar bob dudalen os y llyfr ffôn yn unig didoli hap. Efallai y byddwch yn cael lwcus a dod o hyd Mike ar y dudalen gyntaf iawn, oherwydd ei fod oedd y cwsmer yn gyntaf i archebu gwasanaeth ffôn. Ond gallai fod wedi bod yn yr olaf, hefyd. 

Felly, nid trefn ar hap yn dda. Felly, mae'n debyg rhaid i ni ddatrys y llyfr ffôn neu yn y data didoli cyffredinol yr ydym wedi ei roi. Sut allwn ni wneud hynny? 

Wel, gadewch i mi jyst roi cynnig ar enghraifft syml yma. Gadewch i mi fynd yn ei flaen ac yn taflu yn ychydig rhifau ar y bwrdd. Tybiwch y niferoedd sydd gennym yw, gadewch i ni ddweud, pedwar, dau, un, a thri. Ac, Ben, didoli rhifau hyn i ni. 

Iawn. Sut wnaethoch chi hynny? Iawn. Felly dechreuwch gyda'r lleiaf gwerth a'r uchaf, ac mae hynny'n wir yn greddf da. Ac yn sylweddoli ein bod yn pobl yn mewn gwirionedd yn eithaf yn dda am ddatrys problemau fel hyn, o leiaf pan fydd y data yn gymharol fach. Cyn gynted ag y byddwch yn dechrau i gael gannoedd o rifau, mae miloedd o rifau, miliynau o rifau, Ben yn ôl pob tebyg Ni allai ei wneud yn eithaf hynny yn gyflym, gan dybio bod yna bylchau yn y niferoedd. Pretty hawdd cyfrif at filiwn fel arall, dim ond cymryd llawer o amser. 

Felly mae'r algorithm mae'n swnio fel Ben a ddefnyddir yn unig nawr Roedd chwilio am y nifer lleiaf. Felly hyd yn oed er y gall rydym pobl eu cymryd mewn llawer o wybodaeth ar eu golwg, cyfrifiadur mewn gwirionedd ychydig yn fwy cyfyngedig. Gall y cyfrifiadur yn unig edrych ar un beit ar y tro neu efallai bedwar bytes mewn adeg-- y dyddiau hyn efallai 8 bytes mewn adeg-- ond nifer fach iawn o bytes ar adeg benodol. 

Felly o ystyried ein bod mewn gwirionedd pedwar gwerth wahân Yma-- ac y gallwch feddwl Ben fel rhai blinders ar pe bai'n cyfrifiadur fath nad yw'n gallu gweld unrhyw beth arall nag un rhif ar y adeg-- felly rydym yn gyffredinol bydd yn cymryd yn ganiataol, fel yn Saesneg, byddwn yn darllen o'r dde i'r chwith. Felly, y rhif cyntaf Ben yn ôl pob tebyg yn edrych yn yn bedair ac yna yn gyflym iawn sylweddoli bod 'na eithaf mawr number-- gadewch i mi gadw edrych. 

Mae dau. Arhoswch funud. Mae dau yn llai na phedwar. Rydw i'n mynd i gofio. Two yw'r lleiaf yn awr. Nawr one-- hynny hyd yn oed yn well. Dyna hyd yn oed yn llai. Rydw i'n mynd i anghofio am ddau a dim ond cofio un nawr. 

A gallai efe roi'r gorau i chwilio? Wel, gallai seiliedig ar y wybodaeth hon, ond byddai'n well i mi chwilio gweddill y rhestr. Oherwydd beth os sero oedd yn y rhestr? Beth os yn negyddol un yn y rhestr? Dim ond yn gwybod bod ei ateb yn gywir os ei fod yn drwyadl gwirio'r rhestr gyfan. Felly, rydym yn edrych ar weddill y. Three-- bod yn wastraff amser. Got anlwcus, ond yr oeddwn yn dal yn gywir i wneud hynny. Ac felly yn awr ei fod yn ôl pob tebyg dewis y nifer lleiaf a dim ond yn ei roi ar y dechrau y rhestr, fel y byddaf yn ei wneud yma. Nawr beth wnaethoch chi ei wneud nesaf, er bod nad oeddech yn meddwl am y peth bron i'r graddau hyn? Ailadroddwch y broses, felly rhyw fath o ddolen. Mae 'na syniad cyfarwydd. Felly dyma yw pedwar. Dyna y lleiaf ar hyn o bryd. Dyna yn ymgeisydd. Ddim yn anymore. Nawr rwyf wedi gweld dau. Dyna'r elfen lleiaf nesaf. Three-- nad yw hynny'n llai, felly Bellach, gall Ben tyn allan y ddau. 

Ac yn awr rydym yn ailadrodd y broses, ac wrth gwrs tri yn cael ei dynnu allan nesaf. Ailadroddwch y broses. Mae pedwar yn cael ei dynnu allan. Ac yn awr rydym yn allan o rifau, felly mae'n rhaid i'r rhestr yn cael ei datrys. 

Ac yn wir, mae hwn yn algorithm ffurfiol. Mae gwyddonydd cyfrifiadurol byddai yn galw hyn yn "fath dethol," Y syniad oedd math yn Rhestrwch iteratively-- eto a dewis eto ac eto y nifer lleiaf. A beth sy'n neis am ei fod yn 'i' jyst mor darn athrylithgar. Mae mor syml. A gallwch ailadrodd yr un llawdriniaeth eto ac eto. Mae'n syml. 

Yn yr achos hwn roedd yn gyflym, ond pa mor hir mae'n ei mewn gwirionedd yn cymryd? Gadewch i ni ei gwneud yn ymddangos a teimlo ychydig yn fwy diflas. Felly un, dau, tri, pedwar, pump chwech, saith, wyth, naw, 10, 11, 12, 13, 14, 15, 16-- rhif mympwyol. Fi jyst eisiau mwy hwn amser na dim ond y pedwar. Felly os gen i yn ei gyfanrwydd criw o rifau now-- ei Nid yw hyd yn oed yn ots yr hyn y maent yw-- yn gadael i yn meddwl am beth mae hyn algorithm mewn gwirionedd yn debyg. 

Tybiwch mae niferoedd yno. Unwaith eto, nid oes ots beth y maent, ond maen nhw'n hap. Rwyf yn gwneud cais algorithm Ben. Mae angen i mi ddewis y nifer lleiaf. Beth ydw i'n gwneud? Ac yr wyf i'n mynd i yn gorfforol yn ei wneud y tro hwn i weithredu arno. Wrth edrych, edrych, edrych, edrych, edrych. Dim ond erbyn i mi gyrraedd diwedd y rhestr yn gallu Rwy'n sylweddoli y lleiaf Rhif oedd dau y tro hwn. Nid yw un sydd yn y rhestr. Felly, yr wyf yn rhoi i lawr dau. 

Beth ddylwn i ei wneud nesaf? Wrth edrych, edrych, edrych, yn edrych. Nawr rwy'n dod o hyd i'r rhif saith, gan fod mae bylchau yn y numbers-- hyn ond dim ond mympwyol. Iawn. Felly, yn awr y gallaf roi i lawr saith. Wrth edrych yn edrych, yn edrych. 

Nawr rwy'n tybio, o gwrs, bod Ben nid yw'n cael RAM ychwanegol, yn ychwanegol cof, oherwydd, wrth gwrs, Rwy'n edrych ar yr un rhif. Siawns Gallwn fod wedi cofio pob un o'r niferoedd hynny, ac mae hynny'n hollol wir. Ond os Ben cofio pob o'r rhifau mae'n ei weld, nad yw wedi gwneud mewn gwirionedd cynnydd sylfaenol oherwydd ei fod eisoes y gallu i chwilio drwy'r rhifau ar y bwrdd. Cofio pob un o'r Nid yw niferoedd yn helpu, oherwydd ei fod yn gallu dal fel cyfrifiadur ond yn edrych ar, rydym wedi dweud, un rhif ar y tro. Felly does dim math o twyllo yno y gallwch trosoledd. 

Felly mewn gwirionedd, gan fy mod yn cadw chwilio y rhestr, Mae'n rhaid i mi yn llythrennol i jyst cadw i fynd yn ôl ac ymlaen drwyddo, plicio allan y nifer lleiaf nesaf. Ac fel y gallwch chi fath o awgrymu o fy symudiadau gwirion, mae hyn yn mynd yn iawn 'n faith yn gyflym iawn, ac yr wyf yn ymddangos i fod yn mynd yn ôl ac allan, yn ôl ac ymlaen gryn dipyn. Nawr i fod yn deg, nid oes rhaid i mi fynd yn eithaf fel, yn dda, gadewch i ni see-- i fod yn deg, Nid oes rhaid i mi gerdded yn eithaf cymaint o gamau bob tro. Oherwydd, wrth gwrs, gan fy mod dewiswch rhifau o'r rhestr, y rhestr sydd ar ôl yn mynd yn fyrrach. 

Ac felly gadewch i ni feddwl am faint o gamau rwy'n mewn gwirionedd traipsing drwy bob tro. Yn y sefyllfa cyntaf cawsom rhifau 16, ac felly maximally-- gadewch i jyst gwneud hyn am discussion-- Roedd rhaid i mi edrych drwy 16 rhifau i ddod o hyd i'r lleiaf. Ond ar ôl i mi dynnu allan y nifer lleiaf, sut yn hir y rhestr sydd ar ôl, wrth gwrs? Dim ond 15. yn gwneud hynny faint o rifau Ben neu gen i i edrych trwy'r ail dro o gwmpas? 15, dim ond i fynd a dod o hyd i'r lleiaf. Ond yn awr, wrth gwrs, mae'r rhestr yn, hefyd, yn llai nag yr oedd o'r blaen. Felly faint o gamau y gwnaeth i mi rhaid iddynt gymryd y tro nesaf? 14 ac yna 13 ac yna 12, yn ogystal â dot, dot, dot, hyd nes fy mod i'n gadael gyda dim ond un. Felly nawr byddai gwyddonydd cyfrifiadurol gofyn, yn dda, beth mae hynny'n gyd yn gyfartal? Mae'n mewn gwirionedd yn hafal rhywfaint concrid Rhif y gallem yn sicr gwneud rhifyddol, ond rydym eisiau siarad am effeithlonrwydd o algorithmau ychydig yn fwy formulaically, yn annibynnol o ba mor hir yw'r rhestr yn. 

Ac felly eich bod yn gwybod beth? Mae hyn yn 16 oed, ond fel y dywedais o'r blaen, gadewch i ni ffoniwch maint y broblem n, lle mae n rhywfaint o rif. Efallai ei fod yn 16 oed, efallai ei bod yn tri, efallai ei fod yn miliwn. Nid wyf yn gwybod. Nid wyf yn poeni. Beth Fi 'n sylweddol eisiau yw fformiwla sy'n gallaf defnyddio i gymharu algorithm hwn erbyn algorithmau eraill y gallai rhywun yn hawlio yn well neu'n waeth. 

Felly, mae'n troi allan, ac yr wyf yn unig gwybod hyn o ysgol radd, bod hyn mewn gwirionedd yn gweithio allan at yr un beth â n dros n plws un dros ddwy. Ac mae hyn yn digwydd i cyfartal, o gwrs, n sgwario ynghyd n dros ddwy. Felly, os oeddwn i eisiau fformiwla am faint o gamau yn cymryd rhan mewn edrych ar yr holl o'r niferoedd hynny dro ar ôl tro ac eto ac eto, byddwn yn dweud mae'n sgwâr n plws n dros ddwy. Ond eich bod yn gwybod beth? Mae hyn yn unig yn edrych yn anniben. Fi jyst 'n sylweddol eisiau ymdeimlad cyffredinol o bethau. Ac efallai y byddwch yn cofio o ysgol uwchradd fod yna yw'r syniad o dymor radd uchaf. Pa rai o'r termau hyn, mae'r n sgwâr, mae'r n, neu'r hanner, cael yr effaith fwyaf dros amser? Mae'r n fwy yn cael, sy'n o'r materion hyn fwyaf? 

Mewn geiriau eraill, os wyf yn plwg mewn miliwn, n sgwario yn mynd i fod yn fwyaf tebygol y ffactor dra-arglwyddiaethu, oherwydd bod miliwn o weithiau ei hun yn llawer mwy nag ynghyd ag un miliwn ychwanegol. Felly, rydych yn gwybod beth? Mae hon yn darn mor fawr Rhif os ydych yn sgwario'r rhif. Nid yw hyn yn wirioneddol bwysig. Rydym yn unig yn groes mynd y allan ac anghofio am y peth. Ac felly byddai gwyddonydd cyfrifiadurol yn dweud bod effeithlonrwydd y algorithm hwn ar y drefn n squared-- Yr wyf yn golygu wirioneddol brasamcan. Mae'n cael ei sgwâr fath o fras n. Dros amser, y mwyaf ac yn fwy n cael, mae hyn yn yn amcangyfrif da ar gyfer yr hyn y mae'r effeithlonrwydd neu ddiffyg effeithlonrwydd o algorithm hwn mewn gwirionedd. Ac yr wyf yn deillio hynny, wrth gwrs, o mewn gwirionedd yn gwneud y mathemateg. Ond yn awr Im 'jyst yn chwifio fy nwylo, oherwydd yr wyf yn jyst eisiau ymdeimlad cyffredinol o algorithm hwn. 

Felly gan ddefnyddio'r un rhesymeg, yn y cyfamser, gadewch i ni ystyried algorithm arall rydym eisoes yn edrych at-- chwiliad llinol. Pan oeddwn yn chwilio ar gyfer yr book-- ffôn Nid yw didoli iddo, chwilio drwy'r book-- ffôn rydym yn cadw dweud ei fod yn 1,000 gamau, neu 500 o risiau. Ond gadewch i ni gyffredinoli hynny. Os oes n dudalennau yn y llyfr ffôn, beth yr amser yn rhedeg neu'r effeithlonrwydd chwiliad llinol? Mae'n ar y drefn o faint o gamau i ddod o hyd i Mike Smith gan ddefnyddio chwiliad llinol, mae'r algorithm cyntaf, neu hyd yn oed yr ail? 

Yn yr achos gwaethaf, Mike ar ddiwedd y llyfr. Felly, os y llyfr ffôn Mae 1,000 o dudalennau, dywedasom y tro diwethaf, yn yr achos gwaethaf, gallai gymryd yn fras pa mor mae llawer o dudalennau i ddod o hyd i Mike? Fel 1,000. Mae'n uchaf yn rhwymo. Mae'n sefyllfa waethaf posibl. Ond unwaith eto, rydym yn symud i ffwrdd o rifau fel 1,000 awr. 'I' jyst n. 

Felly beth yw'r casgliad rhesymegol? Dod o hyd i Mike yn ffôn llyfr sydd â thudalennau n Gallai cymryd, yn yr achos gwaethaf iawn, faint o gamau ar y drefn n? Ac yn wir cyfrifiadur Byddai gwyddonydd yn dweud bod yr amser yn rhedeg, neu perfformiad neu effeithlonrwydd neu aneffeithlonrwydd, o algorithm fel chwiliad llinol ar y drefn n. A gallwn gymhwyso'r un rhesymeg groesi rhywbeth allan fel yr wyf yn unig oedd i'r ail algorithm gawsom gyda y llyfr ffôn, lle rydym yn mynd dwy dudalen ar y tro. 

Felly gallai 1,000 dudalen llyfr ffôn mynd â ni 500 tro dudalen, yn ogystal ag un os byddwn yn dyblu ychydig yn ôl. Felly os bydd llyfr ffôn wedi dudalennau n, ond rydym yn ei wneud dwy dudalen ar y tro, dyna yn fras beth? N dros ddwy, felly dyna fel n dros ddwy. Ond yr wyf yn gwneud yr hawliad yn funud yn ôl nad n dros two-- dyna fath o yr un fath ag yn unig n. 'I' jyst yn ffactor cyson, Byddai gwyddonwyr cyfrifiadurol yn dweud. Gadewch i ni dim ond yn canolbwyntio ar newidynnau, really-- newidynnau mwyaf yn yr hafaliad. 

Chwilio Felly llinol, boed gwneud un dudalen ar y tro neu ddwy dudalen ar y tro, yn fath o bôn yr un fath. Mae'n dal i fod ar y drefn o n. Ond yr wyf yn honni gyda fy llun yn gynharach nad oedd y trydydd algorithm oedd llinol. Nid oedd yn llinell syth. Yr oedd y llinell honno crwm, ac mae'r fformiwla algebraidd roedd beth? Log o n-- felly log sylfaen dau o n. Ac nid oes rhaid i ni fynd i ormod cymaint o fanylion ar logarithmau heddiw, ond ni fyddai rhan fwyaf o wyddonwyr cyfrifiadurol hyd yn oed yn dweud wrthych beth y sylfaen yw. Oherwydd ei fod i gyd yn unig Ffactorau gyson, fel petai, dim ond gwahaniaethau rhifol bach. Ac felly byddai hyn yn gyffredin iawn ffordd ar gyfer cyfrifiadur yn arbennig ffurfiol gwyddonwyr yn fwrdd neu rhaglenwyr ar fwrdd gwyn mewn gwirionedd ddadlau pa algorithm byddent yn defnyddio neu beth effeithlonrwydd o'u algorithm yw. 

Ac nid yw hyn o reidrwydd yn rhywbeth fyddwch yn trafod yn fanwl iawn, ond rhaglennydd da yw rhywun sydd â chefndir cadarn, ffurfiol. Mae'n gallu siarad â chi yn y math hwn o ffordd ac mewn gwirionedd yn gwneud dadleuon ansoddol fel pam un algorithm neu un darn o feddalwedd yn well mewn rhyw ffordd i un arall. Oherwydd fe allech chi yn sicr jyst hidla rhaglen un person a chyfrif y nifer o eiliadau mae'n ei gymryd i ddatrys rhai rhifau, a allwch chi redeg rhai rhaglen unigolyn arall a gyfrif y nifer o eiliadau mae'n ei gymryd. Ond mae hyn yn ffordd fwy cyffredinol bod y gallwch eu defnyddio i ddadansoddi algorithmau, os mynnwch, yn union ar papur neu dim ond ar lafar. Heb hyd yn oed yn rhedeg, heb hyd yn oed yn ceisio mewnbynnau sampl, gallwch resymu drwyddo. Ac felly gyda llogi datblygwr neu os cael iddo ef neu hi fath o ddadlau i chi pam eu algorithm, eu cyfrinach saws ar gyfer chwilio biliynau tudalennau gwe ar gyfer eich cwmni yn well, mae'r rhain yn yn y mathau o ddadleuon y maent yn yn ddelfrydol allu gwneud. Neu o leiaf y rhain yn y mathau o bethau a fyddai'n dod i fyny mewn trafodaeth, yn lleiaf mewn trafodaeth ffurfiol iawn. Iawn. Felly Ben arfaethedig rhywbeth Gelwir math dethol. Ond dw i'n mynd i gynnig bod yna ffyrdd eraill o wneud hyn, hefyd. Beth Doeddwn i ddim wir yn hoffi am algorithm Ben yw ei fod yn cadw cerdded, neu ar ôl i mi gerdded, yn ôl ac ymlaen ac yn ôl ac ymlaen ac yn ôl ac ymlaen. Beth os hytrach bawn yn gwneud rhywbeth fel rhifau hyn yma ac bawn yn jyst ymdrin â phob nifer yn ei dro gan fy mod yn ei roi iddo? 

Mewn geiriau eraill, dyma fy rhestr o rifau. Pedwar, un, tri, dau. Ac yr wyf i'n mynd i wneud y canlynol. Rydw i'n mynd i mewnosoder y rhifau lle maent yn perthyn yn hytrach na dewis un ohonynt ar y tro. Mewn geiriau eraill, dyma 'r rhif pedwar. 

Dyma fy rhestr wreiddiol. Ac yr wyf i'n mynd i gynnal hanfod yn rhestr newydd yma. Felly, mae hyn yn y rhestr hen. Mae hyn yn y rhestr newydd. Rwy'n gweld y rhif pedwar cyntaf. Fy rhestr newydd yn y lle cyntaf wag, felly mae'n trivially yn wir bod pedwar yn awr yn rhestr assorted. Im 'jyst yn cymryd y nifer dwi'n rhoi, a dwi'n ei roi yn fy rhestr newydd. 

A yw hyn yn rhestr newydd didoli? Yeah. Mae'n dwp oherwydd mae dim ond un elfen, ond mae'n datrys gwbl. Does dim byd allan o le. Mae'n fwy diddorol, algorithm hwn, pan fyddaf yn symud i'r cam nesaf. 

Nawr mae gen i un. Felly un, wrth gwrs, yn perthyn yn y dechrau neu ddiwedd y rhestr newydd? Y dechrau. Felly rhaid i mi wneud rhywfaint o waith yn awr. Rydw i wedi bod yn cymryd peth rhyddid gyda fy marciwr at jyst yn tynnu pethau lle yr wyf am iddynt, ond nid yw hynny'n wir yn gywir mewn cyfrifiadur. Mae cyfrifiadur, fel y gwyddom, mae gan RAM, neu ar hap Cof Mynediad, a dyna un beit a beit arall a beit arall. Ac os oes gennych gigabeit o RAM, mae gennych biliwn o bytes, ond maent yn gorfforol mewn un lleoliad. nid ydych yn gallu symud o gwmpas pethau trwy dynnu ar y bwrdd ble bynnag y mynnwch. Felly os yw fy rhestr newydd wedi pedwar lleoliad yn y cof, yn anffodus mae'r pedwar yn eisoes yn y lle anghywir. 

Felly, er mwyn mewnosoder y rhif un Ni all Fi jyst dynnu yma. Nid yw hyn lleoliad cof yn bodoli. Byddai hynny'n twyllo, ac yr wyf wedi bod twyllo ddarluniadol am ychydig funudau fan hyn. Felly mewn gwirionedd, os wyf am roi un yma, Mae'n rhaid i mi gopïo'r pedwar dros dro ac yna rhowch y un yno. 

Mae hynny'n iawn, dyna gywir, dyna dechnegol bosibl, ond yn sylweddoli hynny'n gwaith ychwanegol. Doeddwn i ddim jyst roi nifer yn eu lle. Roedd rhaid i mi symud yn gyntaf rhif, yna ei roi ar waith, felly yr wyf yn fath o dyblu fy faint o waith. Felly cadwch hynny mewn cof. 

Ond yr wyf yn awr i'n ei wneud gyda elfen hon. Nawr rwyf am i chrafangia 'r rhif tri. Lle, wrth gwrs, a yw'n perthyn? Yn y canol. Nid wyf yn gallu twyllo anymore a dim ond yn ei roi yno, oherwydd, unwaith eto, cof hon mewn lleoliadau corfforol. Felly rhaid i mi gopïo'r pedwar a rhowch y tri dros yma. Ddim yn beth mawr. Dim ond un cam ychwanegol again-- teimlo'n rhad iawn. 

Ond yn awr yr wyf yn symud ymlaen at y ddau. Mae'r ddau, wrth gwrs, yn perthyn yma. Nawr eich bod yn dechrau gweld sut gall y gwaith pentwr i fyny. Nawr beth sy'n rhaid i mi ei wneud? Yeah, rhaid i mi symud i'r pedwar, Mae'n rhaid i mi wedyn i gopïo'r tri, ac yn awr y gallaf mewnosoder y ddau. Ac mae'r dal gyda hyn algorithm, yn ddiddorol ddigon, yw y mae'n debyg mae gennym fwy eithafol achos lle mae'n gadewch i ni ddweud wyth, saith, chwech, pump, pedwar, tri, dau, un. Mae hyn, mewn sawl cyd-destun, y senario achos gwaethaf, oherwydd y peth darn yn llythrennol ôl. 

Nid yw'n wir yn effeithio ar algorithm Ben, oherwydd mewn detholiad Ben didoli mae'n mynd i gadw yn mynd yn ôl ac ymlaen drwy'r rhestr. Ac oherwydd ei fod yn edrych bob amser drwy'r rhestr sy'n weddill cyfan, does dim ots ble mae'r elfennau yw. Ond yn yr achos hwn gyda fy mewnosod approach-- gadewch i ni geisio hyn. 

Felly un, dau, tri, pedwar, pump, chwech, saith, wyth. Un, dau, tri, pedwar, pump, chwech, saith, wyth. Rydw i'n mynd i gymryd y wyth, a ble ydw i'n ei roi? Wel, ar ddechrau fy rhestr, gan fod hyn yn rhestr newydd yn cael ei datrys. Ac yr wyf yn ei groesi allan. 

Ble ydw i'n rhoi'r saith? Darn iddo. Mae angen iddo fynd yno, felly rhaid i mi wneud rhywfaint o gopïo. Ac yn awr y saith mynd yma. Nawr rwy'n symud ymlaen at y chwech. Nawr mae hyd yn oed mwy o waith. 

Wyth wedi i fynd yma. Saith wedi i fynd yma. Nawr gall y chwe ewch yma. Nawr rwy'n chrafangia 'r pump. Nawr bod y wyth yn gorfod mynd yma, saith wedi i fynd yma, chwech wedi i fynd yma, a yn awr y pum ac ailadrodd. A dwi'n 'n bert lawer symud yn barhaus. 

Felly, ar y diwedd, algorithm-- hwn rydym annhymerus ' alw'n mewnosod sort-- gwirionedd Mae llawer o waith, hefyd. 'I' jyst yn wahanol math o waith na Ben. Roedd gan waith Ben mi fynd yn ôl ac ymlaen drwy'r amser, dewis lleiaf y nesaf elfen eto ac eto. Felly roedd hwn math weledol iawn o waith. 

Mae'r algorithm arall, sydd yn dal correct-- bydd yn cael y swydd done-- jyst yn newid faint o waith. Mae'n edrych fel y dechrau eich bod yn arbed, oherwydd eich bod yn unig ymdrin â phob elfen ymlaen llaw heb gerdded yr holl y ffordd trwy'r rhestr fel Ben oedd. Ond y broblem yw, yn enwedig yn y achosion crazy lle mae'r cyfan yn ôl, eich bod yn unig fath o gohirio'r gwaith caled nes bod yn rhaid i chi drwsio eich camgymeriadau. 

Ac felly os gallwch ddychmygu hyn wyth a saith a chwech a phump ac yn ddiweddarach pedwar a thri a dau symud eu ffordd drwy'r rhestr, rydym wedi newydd newid y math o waith rydym yn ei wneud. Yn hytrach na gwneud hynny ar y gan ddechrau o fy iteriad, Im 'jyst yn gwneud hynny ar y ddiwedd pob ailadrodd. Felly, mae'n troi allan bod algorithm hwn, hefyd, a elwir yn gyffredinol yn fath fewnosod, hefyd ar y drefn n sgwâr. Mae'n mewn gwirionedd yn ddim gwell, ddim gwell o gwbl. 

Fodd bynnag, mae yna drydydd dull Byddwn yn annog i ni eu hystyried, sef hyn. Felly mae'n debyg fy rhestr, er symlrwydd unwaith eto, yn bedwar, un, tri, two-- dim ond pedwar rhif. Roedd gan Ben greddf da, greddf dynol da o'r blaen, a ddefnyddiwn i sefydlog y cyfan Rhestrwch eventually-- math fewnosod. Rwy'n ddenu'n â ni ar hyd. Ond gadewch i ni ystyried y ffordd symlaf at atgyweiria y rhestr hon. 

Nid yw'r rhestr hon yn cael ei datrys. Pam? Yn Saesneg, eglurwch pam nid yw'n datrys mewn gwirionedd. Beth nad yw'n ei olygu i'w didoli? 

MYFYRIWR: Nid yw'n dilyniannol. 

DAVID Malan: Ddim dilyniannol. Rhowch enghraifft i mi. 

MYFYRIWR: Rhowch nhw mewn trefn. 

DAVID Malan: OK. Rhowch enghraifft mwy penodol i mi. 

MYFYRIWR: trefn Esgynnol. DAVID Malan: Ddim esgynnol drefn. Bod yn fwy manwl gywir. Nid wyf yn gwybod beth yr ydych yn ei olygu wrth esgyn. Beth sy'n bod? 

MYFYRIWR: Y lleiaf o'r Nid yw niferoedd yn y gofod cyntaf. 

DAVID Malan: Rhif Lleiaf yn Nid yw yn y gofod cyntaf. Fod yn fwy penodol. Dwi'n dechrau i ddal ar. Rydym yn cyfrif, ond beth sydd allan o drefn yma? 

MYFYRIWR: dilyniant rhifiadol. DAVID Malan: dilyniant rhifiadol. math pawb o gadw mae'n Yma-- lefel uchel iawn. Dim ond yn llythrennol ddweud wrthyf beth sydd anghywir fel gallai pum-mlwydd-oed. 

MYFYRIWR: Plus un. 

DAVID Malan: Beth sy'n bod? 

MYFYRIWR: Plus un. 

DAVID Malan: Beth ydych chi'n ei olygu un a mwy? Dyro i mi wahanol pum-mlwydd-oed. Beth sy'n bod, mom? Beth sy'n bod, dad? Beth ydych chi'n ei olygu nad yw hyn yn datrys? 

MYFYRIWR: Dyw hi ddim yn y lle iawn. 

DAVID Malan: Beth nid yn y lle iawn? 

MYFYRIWR: Four. DAVID Malan: OK, yn dda. Felly, nid pedwar lle y dylai fod. Yn benodol, a yw hyn yn iawn? Pedair ac un, y cyntaf dau rif Rwy'n gweld. A yw hyn yn gywir? Na, maen nhw'n allan o drefn, dde? Yn wir, yn meddwl yn awr am gyfrifiadur, hefyd. Gall ond edrych ar efallai un, efallai dau beth ar once-- ac mewn gwirionedd dim ond un peth ar y tro, ond mae'n gallu o leiaf yn edrych ar un peth, yna mae'r peth nesaf i'r dde nesaf iddo. 

Felly mae hyn mewn trefn? Wrth gwrs ddim. Felly, rydych yn gwybod beth? Pam nad ydym yn cymryd baban camau atgyweirio y broblem hon yn hytrach na gwneud hyn ffansi algorithmau fel Ben, lle ei fod yn fath o osod iddo gan dolennu drwy'r rhestr yn hytrach na gwneud yr hyn a wneuthum, lle Fi jyst fath o mae'n sefydlog wrth i ni fynd? Gadewch i 'jyst yn llythrennol yn torri i lawr y syniad o drefn rifiadol order--, ei alw beth bynnag yr ydych want-- mewn cymariaethau pairwise hyn. 

Pedair ac un. A yw hyn yn y drefn gywir? Felly gadewch i ni atgyweiria bod. Un a phedwar, ac yna byddwn yn jyst adysgrifia hynny. Mae pob hawl, yn dda. Yr wyf yn sefydlog un a phedwar. Tri a dau? No. Gadewch fy ngeiriau cyfateb fy mysedd. Pedwar a thri? 

Dyw hi ddim yn mewn trefn, felly dwi'n mynd i wneud un, tri, pedwar, dau. Iawn. Nawr pedwar a dau? Mae angen i ni atgyweiria hon, hefyd. Felly un, tri, dau, pedwar. Felly mae'n cael ei datrys? Nac oes, ond a yw'n agosach at datrys? 

Mae'n, oherwydd ein sefydlog hwn camgymeriad, rydym yn sefydlog camgymeriad hwn, ac rydym yn sefydlog camgymeriad hwn. Felly, rydym yn sefydlog tri camgymeriadau gellir dadlau. Still nid yw'n wir yn edrych ddidoli, ond mae'n wrthrychol nes at ddidoli oherwydd ein bod yn sefydlog rhai o'r camgymeriadau hynny. 

Nawr beth ddylwn i ei wneud nesaf? Wyf yn fath o cyrraedd diwedd y rhestr. Rwyf yn ymddangos i wedi sefydlog holl gamgymeriadau, ond dim. Oherwydd yn yr achos, rhai rhifau allai fod wedi bubbled fyny yn nes i rifau eraill sy'n yn dal i fod allan o drefn. Felly gadewch i ni wneud hynny eto, a 'n annhymerus' dim ond yn ei wneud yn ei le y tro hwn. Un a thri? Mae'n iawn. Tri a dau? Wrth gwrs ddim, felly gadewch i ni newid hynny. Felly dau, tri. Tri a phedwar? Ac yn awr gadewch i ni dim ond yn arbennig o bedantig yma. A yw'n datrys? Rydych yn bodau dynol yn gwybod ei fod yn datrys. 

dylwn i geisio eto. Felly Olivia yn cynnig yr wyf yn ceisio eto. Pam? Oherwydd nad oes gan gyfrifiadur moethusrwydd ein llygaid dynol o ychydig glancing back-- OK, dwi'n ei wneud. Sut mae'r cyfrifiadur yn penderfynu bod y rhestr yn awr yn datrys? Fecanyddol. 

dylwn i fynd drwy'r unwaith eto, a dim ond os byddaf peidiwch â gwneud / dod o hyd i unrhyw gamgymeriadau y gallaf Yna, yn dod i'r casgliad fod y cyfrifiadur, yep, rydym yn dda i fynd. Felly un a dau, dau a tri, tri a phedwar. Nawr gallaf ddweud yn bendant mae hyn yn didoli, oherwydd yr wyf yn gwneud unrhyw newidiadau. Nawr, byddai'n bug a dim ond ynfyd os wyf i, y cyfrifiadur, Gofynnodd un cwestiynau hynny eto disgwyl atebion gwahanol. Os na ddigwydd. 

Ac felly yn awr y rhestr yn cael ei datrys. Yn anffodus, yn rhedeg amser algorithm hwn hefyd yn n sgwâr. Pam? Oherwydd bod gennych rifau n, ac yn y achos gwaethaf rhaid i chi symud rhifau n Amseroedd n gan fod yn rhaid i chi gadw i fynd yn ôl i wirio ac o bosibl atgyweiria rhifau hyn. A gallwn wneud mwy dadansoddiad ffurfiol, hefyd. 

Felly, mae hyn i gyd i ddweud ein bod wedi cymryd tri dull gwahanol, un ohonynt ar unwaith sythweledol oddi ar y ystlumod o Ben i fy mewnosod a awgrymwyd math i hwn lle rydych yn fath o golli golwg ar y goedwig ar gyfer y coed yn y lle cyntaf. Ond yna os ydych yn cymryd cam yn ôl, voila, rydym wedi sefydlog y syniad didoli. Felly, mae hyn yn, mentraf ddweud, lefel is o bosibl na rhai o'r rhai eraill algorithmau, ond gadewch i ni weld os na allwn dychmygu hyn drwy gyfrwng hwn. 

Felly, mae hyn yn rhai 'n glws meddalwedd bod rhywun Ysgrifennodd gan ddefnyddio bariau lliwgar sy'n mynd i wneud y canlynol i ni. Mae pob un o fariau hyn cynrychioli nifer. Talach y bar, y mwyaf nifer, llai o faint y bar, y lleiaf yw'r rhif. Felly, yn ddelfrydol rydym am pyramid 'n glws lle mae'n dechrau fach ac yn cael mawr, a fyddai'n golygu y bariau hyn yn cael eu didoli. Felly, yr wyf i'n mynd i fynd yn ei flaen ac yn ei ddewis, er enghraifft, algorithm Ben math dethol first--. 

A sylwi ar yr hyn mae'n ei wneud. Mae'r ffordd y maent wedi eu dewis i ddelweddu algorithm hwn yw bod, yn union fel yr oeddwn yn cerdded trwy fy rhestr, y rhaglen hon yn cerdded drwy ei restr o rifau, gan amlygu mewn pinc mhob Rhif ei fod yn edrych arno. A beth fin digwydd ar hyn o bryd? 

Y nifer lleiaf sy'n I neu Ben dod o hyd yn sydyn yn cael ei symud i gychwyn y rhestr. Ac rhybudd wnaethant troi allan y nifer a oedd yno, ac mae hynny'n berffaith iawn. Doeddwn i ddim yn mynd i mewn y lefel honno o fanylder. Ond mae angen i roi y rhif hwnnw yn rhywle, felly rydym yn unig yn symud i'r fan a'r lle agored a grëwyd. Felly, yr wyf i'n mynd i gyflymu'r hwn i fyny, gan ei fod fel arall yn dod yn ddiflas iawn yn gyflym. Animeiddio speed-- dyna ni. Felly nawr un egwyddor Yr oeddwn yn gwneud cais, ond rydych yn Gall dechrau teimlo'n algorithm, os ydych yn fydd, neu yn ei weld ychydig yn fwy clir. Ac mae algorithm hwn yn cael yr effaith o gan ddewis yr elfen lleiaf nesaf, felly rydych yn mynd i ddechrau i weld yn ramp i fyny ar y chwith. Ac ar bob iteriad, gan fy mod yn arfaethedig, nid yw'n gwneud llawer llai o waith. nid oes rhaid iddo fynd yr holl ffordd ôl i ddiwedd chwith y rhestr, oherwydd ei fod yn barod yn gwybod hynny yn cael eu didoli. Felly mae'n fath o teimlo fel ei fod yn cyflymu, er bod pob cam yn cymryd yr un faint o amser. Mae ychydig yn llai camau sy'n weddill. Ac yn awr y gallwch chi fath o teimlo y algorithm glanhau y diwedd, ac yn wir yn awr mae'n cael ei sortio. 

Felly fath rhoi i mewn yw wneud i gyd. Mae angen i mi ail-randomize y rhesi. Ac yn sylwi Fi jyst yn gallu cadw randomizing iddo, a byddwn yn cael ddynesiad yr un dull, math mewnosod. Gadewch i mi ei arafu i fan hyn. Gadewch i ni ddechrau fod dros. Stop. 

Gadewch i sgip pedwar. Dyna ni. Randomize y maent yn arae. A dyma ni go-- fath fewnosod. Chwarae. Sylwch ei fod yn ymdrin â phob elfen y mae'n dod ar eu traws ar unwaith, ond os yw'n perthyn yn yr hysbysiad lle anghywir yr holl waith sydd i ddigwydd. Mae'n rhaid i ni gadw symud mwy a mwy o elfennau i wneud lle ar gyfer yr un yr ydym am ei roi ar waith. 

Felly, rydym yn canolbwyntio ar y pen chwith y rhestr yn unig. Rhybudd nid ydym wedi hyd yn oed yn edrych at-- ni Nid wedi tynnu sylw mewn unrhyw beth pinc i'r dde. Rydym yn unig yn delio â y problemau wrth i ni fynd, ond rydym yn creu llawer o gweithio i ni ein hunain o hyd. Ac felly os ydym gyflymu'r hyn i fyny yn awr i fynd i'r cwblhau, mae ganddo deimlad gwahanol iddo yn wir. Mae'n canolbwyntio ar y pen chwith ond yn gwneud ychydig mwy o waith fel needed-- math o bethau llyfnu drosodd, gosod pethau, ond yn y pen draw yn ymdrin â pob elfen un ar y tro tan i ni gyrraedd the-- dda, rydym yn i gyd yn gwybod sut mae hyn yn mynd i ben, felly mae'n ychydig underwhelming efallai. 

Ond mae'r rhestr yn y end-- spoiler-- yn mynd i gael eu datrys. Felly gadewch i ni edrych ar un un diwethaf. Ni allwn yn unig sgip yn awr. Rydym yn bron yno. Dwy i fynd, un i fynd. A voila. Ardderchog. 

Felly nawr gadewch i ni wneud un yr un olaf, ail-randomizing gyda'r math swigen. Ac yn sylwi yma, yn enwedig os byddaf yn arafu ei i lawr, mae hyn yn cadw yn disgyn drwy'r. Ond yn sylwi 'i jyst yn gwneud pairwise math comparisons-- o atebion lleol. Ond, cyn gynted ag y cawn i diwedd y rhestr mewn pinc, beth sy'n mynd i gael i ddigwydd eto? Yeah, mae'n mynd i gael i dechrau drosodd, oherwydd ei fod yn unig camgymeriadau pairwise sefydlog. Ac a allai fod wedi datgelu eraill eto. Ac felly os ydych yn cyflymu'r hyn i fyny, wnewch chi helpu weld hynny, gymaint fel yr awgryma'r enw, y lleiaf elements-- neu yn hytrach, y elements-- mwy o faint yn dechrau ffrwtian i fyny i ben, os mynnwch. A'r elfennau llai yn dechrau ffrwtian lawr i'r chwith. Ac yn wir, dyna fath o yr effaith weledol yn ogystal. Ac felly y bydd hyn yn y pen draw gorffen mewn ffordd debyg iawn, hefyd. 

Nid oes rhaid i ni drigo ar yr un yma penodol. Gadewch i mi agor hyn yn awr, hefyd. Mae ychydig o algorithmau didoli eraill yn y byd, mae ychydig ohonynt yn cael eu dal yma. Ac yn enwedig ar gyfer dysgwyr nad ydynt yn o reidrwydd yn y golwg neu fathemategol, fel y gwnaethom o'r blaen, y gallwn wneud hyn hefyd audially os rydym yn eu cysylltu sain gyda hyn. A dim ond am hwyl, dyma ychydig gwahanol algorithmau, ac un ohonynt yn benodol eich bod yn mynd i hysbysiad cael ei alw'n "math uno." 

Mae'n mewn gwirionedd yn y bôn gwell algorithm, fel bod uno fath, un o y rhai yr ydych chi ar fin gweld, Nid yw trefn n sgwâr. Mae'n ar y drefn o n amseroedd log o n, sydd mewn gwirionedd yn llai ac felly gyflymach na'r rhai tri arall. Ac mae cwpl arall rhai gwirion a gawn ni weld. 

Felly dyma ni gyda rhywfaint o sain. Mae hwn yn fath fewnosod, felly unwaith eto 'i' jyst ymdrin â'r elfennau wrth iddynt ddod. Mae hwn yn fath swigod, felly mae'n ystyried parau ar y tro arnynt. Ac eto, yr elfennau mwyaf yn byrlymu i fyny i ben. 

Nesaf i fyny math dethol. Mae hyn yn algorithm Ben, lle mae eto ei fod yn ddewis ailadroddol yr elfen lleiaf nesaf. Ac eto, yn awr gallwch mewn gwirionedd yn clywed bod mae'n cyflymu ond dim ond i'r graddau gan ei fod yn gwneud llai a llai yn gweithio ar bob fersiwn. Mae hyn yn y cyflymach un, uno yn didoli, sydd yn didoli clystyrau o rifau gyda'i gilydd ac yna eu cyfuno. Felly look-- y chwith hanner eisoes yn cael ei datrys. 

Nawr mae'n didoli'r hanner cywir, a erbyn hyn mae'n mynd i cyfuno i mewn i un. Mae hyn yn rhywbeth o'r enw "Gnome fath." A gallwch fath o weld bod mae'n mynd yn ôl ac ymlaen, gosod gwaith ychydig yma ac yno cyn iddo symud ymlaen i waith newydd. A dyna ni. Mae math arall, sef mewn gwirionedd dim ond at ddibenion academaidd, o'r enw "didoli dwp," sy'n cymryd eich data, yn didoli ei hap, ac yna gwirio os yw'n cael ei datrys. Ac os nad yw, mae'n ail-didoli'r ei ar hap, gwirio os yw'n didoli, ac os nad yw ailadrodd. Ac mewn theori, probabilistically bydd hyn yn cwblhau, ond ar ôl cryn dipyn o amser. Dyw hi ddim yn y rhan fwyaf o effeithlon o algorithmau. Felly unrhyw gwestiynau ar y rhai algorithmau neu unrhyw beth penodol cysylltiedig yno, hefyd? 

Wel, gadewch i bellach yn tynnu ar wahân beth i gyd llinellau hyn yn fy mod i wedi bod yn tynnu a beth rwy'n tybio y cyfrifiadur yn gallu ei wneud o dan y cwfl. Byddwn yn dadlau bod pob un o'r rhifau hyn Rwy'n cadw drawing-- mae angen iddynt gael storio yn rhywle yn y cof. Byddwn yn cael gwared ar y boi yn awr, hefyd. 

Felly darn o gof mewn computer-- felly RAM DIMM yw yr hyn yr ydym yn chwilio am ddoe, deuol cof inline module-- edrych fel hyn. A phob un o'r sglodion du bychain hyn rhywfaint o nifer o bytes, fel arfer. Ac yna y pinnau aur yn debyg y gwifrau sy'n cysylltu i'r cyfrifiadur, a'r bwrdd silicon gwyrdd yn unig beth yn cadw popeth i gyd gyda'i gilydd. Felly beth mae hyn yn ei olygu? Os wyf yn fath o dynnu un llun hwn, gadewch i ni dybio ar gyfer symlrwydd bod DIMM hwn, deuol modiwl cof inline, yn un gigabyte o RAM, un gigabeit o cof, a dyna faint o gyfanswm beit? Mae un gigabeit yw faint o bytes? Mwy na hynny. 1,124 yn kilo, 1,000. Mega yw miliwn. Giga yn biliwn. 

Ydw i'n dweud celwydd? A allwn ni hyd yn oed yn darllen y label? Mae hyn mewn gwirionedd 128 gigabeit, felly mae'n fwy. Ond byddwn yn esgus hwn Dim ond un gigabeit. Felly mae hynny'n golygu mae 'na biliwn bytes o gof ar gael i mi neu 8 biliwn o ddarnau, ond rydym yn mynd i siarad yn nhermau bytes yn awr, symud ymlaen. 

Felly beth mae hynny'n ei olygu yw hyn yn un beit, mae hyn yn beit arall, mae hyn yn beit arall, ac os ydym eisiau mewn gwirionedd i fod yn benodol y byddai'n rhaid i ni tynnu ychydig o biliwn o sgwariau. Ond beth mae hynny'n ei olygu? Wel, gadewch i mi jyst chwyddo mewn ar y llun yma. Os gen i rywbeth sy'n edrych fel hyn yn awr, dyna pedwar bytes. 

Ac felly y gallwn i roi pedwar rhif yma. Un, dau, tri, pedwar. Neu gallwn i roi pedwar llythyr neu symbolau. "Hey!" allai fynd i'r dde yno, gan fod pob un o'r llythyrau, buom yn trafod yn gynharach, Gellid cael eu cynrychioli gydag wyth darnau neu ASCII neu beit. Felly, mewn geiriau eraill, gallwch rhoi 8 biliwn o bethau y tu mewn o hyn un ffon o gof. Nawr, beth mae'n ei olygu i roi pethau yn ôl i yn ôl i yn ôl yn y cof fel hyn? Dyma beth yn rhaglennydd Byddai galw yn "array." Mewn rhaglen gyfrifiadurol, nad ydych yn meddwl am y caledwedd sylfaenol, fel y cyfryw. Rydych yn unig yn meddwl amdanoch eich hun fel un sydd mynediad at gyfanswm biliwn beit, a allwch chi unrhyw beth yr hoffech ag ef. Ond er cyfleustra yn gyffredinol mae'n ddefnyddiol i gadw eich hawl cof nesaf at ei gilydd fel hyn. Felly os wyf yn chwyddo i mewn ar this-- oherwydd yn sicr nid ydym yn mynd i dynnu ychydig biliwn squares-- gadewch i ni dybio bod y bwrdd hwn yn cynrychioli y ffon o gof yn awr. A byddaf yn jyst yn tynnu cymaint â fy marciwr yn dod i ben i fyny gan roi i mi yma. Felly, yn awr mae gennym ffon o gof ar y bwrdd sy'n got un, dau, tri, pedwar, pump, chwech, un, dau, tri, pedwar, pump, chwech, seven-- felly 42 bytes o cof ar gyfanswm y sgrin. Diolch. Do, gwnaeth fy rhifyddeg gywir. Felly 42 bytes o gof yma. Felly beth mae hyn yn ei olygu mewn gwirionedd? Wel, yn rhaglennydd cyfrifiadurol byddai mewn gwirionedd yn gyffredinol feddwl o gof hwn fel gyfeiriedig. Mewn geiriau eraill, mae pob un o'r rhain lleoliadau mewn cof, mewn caledwedd, Mae gan gyfeiriad unigryw. 

nid yw mor gymhleth ag Un Brattle Square, Caergrawnt, Mass., 02138. Yn lle hynny, dim ond rhif. Mae hwn yn rhif beit sero, mae hyn yn un, mae hyn yn dau, mae hyn yn dri, ac mae hyn yn 41. Arhoswch funud. Roeddwn i'n meddwl y dywedais 42 funud yn ôl. Dechreuais cyfrif ar sero, fel eu bod mewn gwirionedd yn gywir. Nawr, nid oes rhaid i ni mewn gwirionedd yn tynnu fel grid, ac os ydych yn tynnu fel grid Yr wyf yn meddwl pethau mewn gwirionedd yn cael ychydig yn gamarweiniol. Beth fyddai yn rhaglennydd, yn ei feddwl ei hun, Yn gyffredinol, yn meddwl am hyn cof yn union fel tâp, fel darn o dâp masgio mai dim ond yn mynd ymlaen ac ymlaen am byth neu hyd nes y byddwch yn rhedeg allan o gof. Felly ffordd fwy cyffredin i dynnu a dim ond meddwl am y cof fyddai bod hyn yn beit sero, un, dau, tri, ac yna dot, dot, dot. Ac mae gennych cyfanswm 42 bytes o'r fath, hyd yn oed er corfforol y gallai mewn gwirionedd fod yn rhywbeth mwy fel hyn. 

Felly, os ydych yn awr yn meddwl am eich cof gan fod hyn, yn union fel tâp, mae hyn yn beth yn rhaglennydd eto Byddai galw amrywiaeth o gof. A phan ydych am i storio mewn gwirionedd rhywbeth mewn cof cyfrifiadur, rydych yn gyffredinol yn gwneud pethau siop cefn wrth cefn wrth gefn-wrth-gefn. Felly rydym wedi bod yn siarad am rifau. A phan oeddwn i eisiau i ddatrys problemau fel pedwar, un, tri, dau, hyd yn oed er fy mod yn jyst tynnu dim ond y rhifau pedwar, un, tri, dau ar y bwrdd, a fyddai y cyfrifiadur mewn gwirionedd yn cael setup hwn mewn cof. 

A beth fyddai'r nesaf i'r dau yn gof y cyfrifiadur? Wel, does dim ateb i hynny. Dydyn ni ddim yn gwybod. Ac cyhyd ag y bo'r Nid oes angen cyfrifiadur iddo, nid oes rhaid iddo i ofalu beth sydd nesaf at y niferoedd y mae'n ei wneud gofal am. A phan ddywedais yn gynharach fod cyfrifiadur dim ond edrych ar un cyfeiriad ar y tro, mae hyn yn fath o pam. 

Nid annhebyg cofnod chwaraewr a phen darllen dim ond yn gallu edrych ar rai rhigol mewn cofnod hen-ysgol corfforol ar y tro, yn yr un modd gall cyfrifiadur diolch at ei CPU a'i set cyfarwyddyd Intel, ymhlith y mae eu cyfarwyddyd yn cael ei ddarllen o gof neu arbed i memory-- yn Gall cyfrifiadur ond edrych mewn un lleoliad mewn adeg-- weithiau gyfuniad ohonynt, ond mewn gwirionedd dim ond un lleoliad ar y tro. Felly, pan oeddem yn gwneud algorithmau amrywiol hyn, nid Im 'jyst yn ysgrifennu mewn vacuum-- pedwar, un, tri, dau. niferoedd hynny mewn gwirionedd yn perthyn rhywle corfforol mewn cof. Felly mae yna ychydig bach transistorau neu ryw fath o electroneg o dan y cwfl storio gwerthoedd hyn. 

Ac i gyd, faint o ddarnau yn cael eu cymryd rhan ar hyn o bryd, dim ond i fod yn glir? Felly dyma pedwar bytes, neu nawr mae'n gyfanswm 32 ddarnau. Felly, mae mewn gwirionedd yn 32 o zeros a rhai cyfansoddi rhain pedwar peth. Mae hyd yn oed yn fwy dros yma, ond eto nid ydym yn poeni am hynny. 

Felly nawr gadewch i ofyn un arall cwestiwn gan ddefnyddio cof, oherwydd hynny ar y diwedd y dydd yn amrywiant. Ni waeth beth y gallem ei wneud gyda y cyfrifiadur, ar ddiwedd y dydd y caledwedd yn dal i fod y un peth o dan y cwfl. Sut fyddwn i'n storio gair i mewn yma? Wel, gair mewn cyfrifiadur fel "Hey!" Byddai yn cael ei storio yn union fel hyn. Ac os ydych eisiau mwy o amser gair, yn syml y gallwch trosysgrifo hynny a dweud rhywbeth fel "helo" a storfa hynny yma. 

Ac felly yma, hefyd, contiguousness hwn mewn gwirionedd yn fantais, oherwydd y gall cyfrifiadur yn unig darllen o'r dde i'r chwith. Ond dyma gwestiwn. Yng nghyd-destun y gair hwn, h-e-l-l-o, pwynt ebychnod, sut y gallai'r cyfrifiadur yn gwybod ble mae'r gair yn dechrau a ble mae'r gair yn dod i ben? Yng nghyd-destun o rifau, sut mae'r cyfrifiadur gwybod pa mor hir y dilyniant o rhifau yw neu pan fydd yn dechrau? Wel, mae'n troi out-- ac ni fyddwn yn mynd yn ormod i mewn i lefel hon o detail-- cyfrifiaduron symud pethau o gwmpas yn y cof llythrennol drwy gyfrwng cyfeiriadau hyn. Felly, mewn cyfrifiadur, os ydych chi'n cod ysgrifennu i storio pethau fel geiriau, yr hyn rydych yn 'n sylweddol ei wneud yw teipio mynegiadau sy'n cofio ble yn gof y cyfrifiadur geiriau hyn yn cael eu. Felly, gadewch i mi wneud iawn, Enghraifft syml iawn. 

Rydw i'n mynd i fynd yn ei flaen a agor rhaglen testun syml, a dw i'n mynd i greu ffeil o'r enw hello.c. Mae'r rhan fwyaf o'r wybodaeth hon i ni ni fydd yn mynd i mewn yn fanwl iawn, ond dwi'n mynd i ysgrifennu rhaglen yn yr un iaith, C. Mae hyn yn llawer mwy bygythiol, byddwn yn dadlau, na Scratch, ond mae'n debyg iawn o ran ysbryd. Yn wir, mae'r rhain cyrliog braces-- gallwch math o meddwl am yr hyn yr wyf yn unig oedd gan fod hyn. 

Gadewch i ni wneud hyn, mewn gwirionedd. Pan glicio baner werdd, wneud y canlynol. Rwyf eisiau argraffu allan "helo." Felly, mae hyn yn awr yn pseudocode. Im 'yn fath o cymylu'r llinellau. Yn C, yr iaith hon rwy'n siarad am, mae hyn yn print llinell helo mewn gwirionedd yn dod yn "printf" gyda rhai cromfachau a hanner colon. 

Ond mae'n yr un syniad union. Ac mae hyn yn iawn hawdd ei ddefnyddio "Pan baner werdd glicio" yn dod y llawer mwy dirgel "prif ddi-rym int." Ac mae hyn yn wir nid oes gan mapio, felly Im 'jyst yn mynd i anwybyddu hynny. Ond mae'r braces cyrliog yn debyg y darnau pos crwm fel hyn. 

Felly gallwch math o ddyfalu. Hyd yn oed os nad ydych erioed wedi ei raglennu o'r blaen, beth mae rhaglen hon yn ôl pob tebyg yn ei wneud? Mwy na thebyg printiau helo gyda phwynt ebychnod. 

Felly gadewch i ni geisio hynny. Rydw i'n mynd i achub. Ac mae hyn yn, unwaith eto, mae iawn hen amgylchedd yr ysgol. Ni allaf glicio, ni allaf lusgo. Mae'n rhaid i mi deipio gorchmynion. Felly, yr wyf am redeg fy rhaglen, felly efallai y byddwn yn gwneud hyn, fel hello.c. Dyna y ffeil Rwy'n rhedeg. Ond arhoswch, rwy'n ar goll cam. Yr hyn a wnaethom ei ddweud yn angenrheidiol camu ar gyfer iaith fel C? Rwyf newydd ffynhonnell ysgrifenedig cod, ond yr hyn sydd ei angen arnaf? Yeah, mae angen casglwr wyf. Felly, ar fy Mac yma, mae gen i rhaglen o'r enw GCC, GNU C casglwr, sy'n caniatáu i mi wneud this-- dro fy cod ffynhonnell i mewn, byddwn yn ei alw, cod peiriant. 

A gallaf weld hynny, eto, fel a ganlyn, mae'r rhain yw'r zeros a rhai Fi jyst a grëwyd gan fy cod ffynhonnell, pob un o'r sero a rhai. Ac os wyf eisiau rhedeg fy program-- mae'n digwydd i gael ei alw a.out am reasons-- hanesyddol "helo." Gallaf redeg eto. Helo, helo, helo. Ac mae'n ymddangos i fod yn gweithio. 

Ond mae hynny'n golygu rhywle yn fy gof cyfrifiadur yw'r geiriau h-e-l-l-o, pwynt ebychnod. Ac mae'n troi allan, yn union fel o'r neilltu, beth fyddai cyfrifiadur nodweddiadol gwneud fel ei fod yn gwybod lle pethau'n dechrau ac end-- ei fod yn mynd i roi symbol arbennig yma. Ac y confensiwn yw rhoi'r rhif sero ar ddiwedd gair fel eich bod yn gwybod lle y mae'n mewn gwirionedd yn dod i ben, er mwyn i chi peidiwch â chadw argraffu mwy a mwy cymeriadau na chi mewn gwirionedd yn bwriadu. 

Ond mae'r tecawê yma, hyd yn oed er bod hyn yn weddol dirgel, yw ei fod yn y pen draw gymharol syml. A roddwyd i chi fath o dâp, yn wag lle y gallwch ysgrifennu llythyrau. yn syml rhaid i chi gael symbol arbennig, fel fympwyol y rhif sero, i roi ar ddiwedd y eich geiriau fel bod y cyfrifiadur yn gwybod, oh, ddylwn i roi'r gorau argraffu ar ôl Rwy'n gweld y pwynt ebychnod. Oherwydd bod y peth nesaf yno yn werth ASCII o sero, neu gymeriad null fel byddai rhywun yn ei alw. Ond mae math o broblem yma, a gadewch i ni fynd yn ôl i rifau am eiliad. Tybiwch fy mod yn ei wneud, mewn gwirionedd, cael amrywiaeth o rifau, ac mae'n debyg bod y rhaglen Rwy'n ysgrifennu yn fel llyfr gradd ar gyfer athro ac ystafell ddosbarth athrawon. Ac mae'r rhaglen hon yn caniatáu iddo ef neu hi teipio mewn sgorau eu myfyrwyr ar gwisiau. Ac mae'n debyg bod y myfyriwr yn cael 100 ar eu cwis cyntaf, efallai fel 80 ar yr un nesaf, yna 75, yna 90 ar y pedwerydd cwis. 

Felly, yn y fan hon yn y stori, yr amrywiaeth o faint pedwar. Mae gwbl mwy o gof yn y cyfrifiadur, ond yr amrywiaeth, fel petai, yw o faint pedwar. Tybiwch yn awr bod yr athro eisiau i neilltuo pumed gwis i'r dosbarth. Wel, un o'r pethau mae'n neu hi yn mynd i gael i wneud yn awr yn storio gwerth ychwanegol yma. Ond os bydd y arae gan yr athro a grëwyd yn y rhaglen hon o faint ar gyfer, un o'r broblem gydag amrywiaeth yw bod nid ydych yn gallu cadw ychwanegu at cof. Oherwydd beth os rhan arall o'r rhaglen mae gan y gair "hey" iawn yno? 

Mewn geiriau eraill, gall fy nghof fod a ddefnyddir ar gyfer unrhyw beth mewn rhaglen. Ac os o flaen llaw i mi deipio i mewn, hey, Rwyf am fewnbwn pedwar sgoriau cwis, Efallai y byddant yn mynd yma ac yma. Ac os byddwch yn sydyn yn newid eich meddwl yn ddiweddarach a dweud yr wyf am un rhan o bump cwis sgôr, ni allwch unig roi ble bynnag y mynnwch, oherwydd yr hyn os yw hyn cof yn cael ei ddefnyddio am rywbeth else-- ryw raglen arall neu ryw nodwedd arall o'r rhaglen eich bod yn rhedeg? Felly, rhaid i chi feddwl o flaen llaw sut yr ydych am i storio eich data, oherwydd erbyn hyn eich bod wedi paentio eich hun i mewn i gornel digidol. 

Felly athro gallai yn lle hynny dweud wrth ysgrifennu rhaglen i storio ei graddau, eich bod yn gwybod beth? Yr wyf yn mynd i wneud cais, wrth ysgrifennu fy rhaglen, yr wyf am sero, un, dau, tri, cyfanswm pedwar, pump, chwech, wyth graddau. Felly un, dau, tri, pedwar, pump, chwech, saith, wyth. Gall yr athro ychydig dros-ddyrannu cof wrth ysgrifennu ei raglen ac yn dweud, eich bod yn gwybod beth? Nid wyf erioed i'n mynd i aseinio mwy nag wyth cwisiau mewn semester. Mae hynny'n unig crazy. Wna i byth yn dyrannu hynny. Fel bod y ffordd hon ganddo ef neu hi yr hyblygrwydd i sgorau storio myfyrwyr, fel 75, 90, ac efallai un ychwanegol pan y myfyriwr got credyd ychwanegol, 105. 

Ond os yw'r athro byth defnyddio'r rhain tri lle, mae 'na cludfwyd reddfol yma. Mae ef neu hi yn unig gwastraffu gofod. Felly, mewn geiriau eraill, mae hyn yn tradeoff cyffredin mewn rhaglennu lle y gallwch naill ai ddyrannu yn union gymaint o gof ag y dymunwch, y upside o'r rhain yw eich bod yn super efficient-- nad ydych yn bod yn wastraffus yn all-- ond mae'r anfantais ohonynt beth os byddwch yn newid eich meddwl pan gan ddefnyddio'r rhaglen yr ydych am i storio mwy o ddata nag yr oeddech fwriadwyd yn wreiddiol. 

Felly efallai yr ateb yw, yna, ysgrifennu eich rhaglenni yn y fath fodd eu bod yn defnyddio mwy o gof nag y maent ei angen mewn gwirionedd. Mae hyn yn ffordd nad ydych yn mynd i redeg i mewn i broblem honno, ond eich bod yn wastraffus. Ac mae'r cof yn fwy eich rhaglen yn defnyddio, fel y trafodwyd ddoe, mae'r llai cof sydd ar gael ar gyfer rhaglenni eraill, y cynharaf y gallai eich cyfrifiadur yn araf i lawr oherwydd y cof rhithwir. Ac felly efallai yr ateb delfrydol fyddai beth? 

Dan-dyrannu yn ymddangos yn ddrwg. Dros-dyrannu yn ymddangos yn ddrwg. Felly yr hyn a allai fod yn ateb gwell? Ailddyrannu. Bod yn fwy deinamig. Peidiwch â gorfodi eich hun i ddewis priori, ar y dechrau, yr hyn yr ydych ei eisiau. Ac yn sicr nid ydynt yn gor-ddyrannu, rhag i chi fod yn wastraffus. 

Ac felly i gyrraedd y nod, rydym Mae angen i daflu strwythur data hwn, fel petai, i ffwrdd. Ac felly beth yn rhaglennydd Bydd fel arfer yn defnyddio nid yw rhywbeth o'r enw arae ond rhestr cysylltiedig. Mewn geiriau eraill, mae ef neu hi fydd ddechrau meddwl am eu cof fel math bod o siâp y maent Gall dynnu yn y ffordd ganlynol. Os ydw i eisiau i storio un rhif yn yn program-- felly mae'n mis Medi, Rydw i wedi rhoi cwis fy myfyrwyr; Rwyf am i storio cwis cyntaf y myfyrwyr, ac maent yn cael 100 ar iddo-- wyf wyf yn mynd i ofyn i fy nghyfrifiadur, drwy gyfrwng y rhaglen rwyf wedi ysgrifenedig, ar gyfer un darn o gof. Ac yr wyf i'n mynd i storio'r rhif 100 ynddo, a dyna ni. 

Yna ychydig wythnosau yn ddiweddarach pan fyddaf yn cael fy ail cwis, ac mae'n amser i deipio yn hynny o 90%, yr wyf yn mynd i ofyn i'r cyfrifiadur, hey, cyfrifiaduron, alla i gael darn arall o gof? Mae'n mynd i roi hyn i mi darn gwag o gof. Rydw i'n mynd i roi yn y nifer 90, ond yn fy rhaglen rywsut neu other-- ac ni fyddwn yn poeni am y cystrawen ar gyfer this-- angen arnaf i rhywsut cadwyn pethau hyn gyda'i gilydd. A byddaf yn eu cadwyn ynghyd â hyn sy'n edrych fel saeth yma. 

Y trydydd cwis sy'n dod i fyny, Rydw i'n mynd i ddweud, hey, cyfrifiaduron, rhoi darn arall o gof i mi. Ac yr wyf i'n mynd i roi i lawr beth bynnag oedd hi, fel 75, ac yr wyf yn rhaid i gadwyn hon gyda'i gilydd yn awr rywsut. cwis Pedwerydd dod ynghyd, ac efallai dyna tuag at ddiwedd y semester. Ac erbyn hynny fy rhaglen allai fod yn defnyddio cof dros y lle, i gyd dros gorfforol. Ac felly yn unig ar gyfer cychwyn, rwy'n mynd i dynnu hyn allan quiz-- byddaf yn anghofio beth oedd; Yr wyf yn meddwl efallai o 80 neu something-- ffordd dros yma. 

Ond mae hynny'n iawn, oherwydd ddarluniadol Rydw i'n mynd i dynnu llinell hon. Mewn geiriau eraill, mewn gwirionedd, mewn caledwedd eich cyfrifiadur, gallai'r sgôr cyntaf yn y pen draw fan hyn am ei fod yn i'r dde ar ddechrau'r semester. Gallai'r un nesaf yn y pen draw fan hyn oherwydd ychydig o amser wedi mynd heibio ac mae'r rhaglen yn cadw rhedeg. Y sgôr nesaf, a oedd yn 75, a allai fod dros yma. Ac efallai y sgôr olaf yn 80, sydd dros yma. 

Felly, mewn gwirionedd, yn gorfforol, mae hyn allai fod pa cof eich cyfrifiadur yn edrych fel. Ond nid yw hyn yn meddwl defnyddiol patrwm ar gyfer rhaglennydd cyfrifiadur. Pam ddylech chi ofalu ble mae'r Heck eich data yn dod i ben i fyny? Wyt ti am i storio data. 

Mae hyn yn fath o fel ein trafodaeth cynharach o dynnu ciwb. Pam ydych chi'n poeni beth ongl yw y ciwb a sut mae'n rhaid i chi droi i dynnu ef? 'Ch jyst eisiau ciwb. Yn yr un modd yma, rydych yn jyst eisiau llyfr gradd. Rydych yn unig am feddwl am hyn fel rhestr o rifau. Pwy sy'n poeni sut mae'n rhoi ar waith mewn caledwedd? 

Felly mae'r tyniad yn awr yn y darlun hwn yma. Mae hyn yn rhestr cysylltiedig, fel y Byddai rhaglennydd ei alw, i'r graddau y bydd gennych rhestr, yn amlwg o rifau. Ond mae'n cysylltu'n ddarluniadol drwy gyfrwng saethau hyn, a phob saethau hyn yw-- oddi tano y cwfl, os ydych yn chwilfrydig, dwyn i gof bod ein caledwedd ffisegol wedi cyfeiriadau sero, un, dau, tri, pedwar. Mae'r holl saethau hyn yn yn debyg i fap neu gyfarwyddiadau, lle os 90 yw-- bellach Ges i gyfrif. 

Zero, un, dau, tri, pedwar, pump, chwech, saith. Mae'n edrych fel y 90 ar cof rhif gyfeiriad saith. Mae'r holl saethau hyn yw fel ychydig o sgrap o bapur sy'n rhoi cyfarwyddiadau i'r rhaglen sy'n dweud dilynwch y map i gyrraedd leoliad saith. Ac yno y byddwch yn dod o hyd i'r ail sgôr cwis myfyriwr. Yn y cyfamser, mae'r 75-- os byddaf yn parhau i wneud hyn, mae hyn yn saith, wyth, naw, 10, 11, 12, 13, 14, 15. 

Mae'r saeth arall yn unig yn cynrychioli map i leoliad cof 15. Ond unwaith eto, mae'r rhaglennydd yn gyffredinol yn ei wneud ydynt yn poeni am lefel hon o fanylder. Ac yn y rhan fwyaf mhob rhaglennu iaith heddiw, mae'r rhaglennydd Ni fydd hyd yn oed yn gwybod ble yn y cof rhifau hyn mewn gwirionedd. Mae pob ef neu hi wedi i ofalu am ei eu bod yn cael eu cysylltu rywsut gyda'i gilydd mewn strwythur data fel hyn. 

Ond mae'n troi allan nad yw â mynd yn rhy dechnegol. Ond dim ond oherwydd ein bod efallai yn gallu fforddio cael y drafodaeth hon yma, Mae'n debyg ein bod yn ailedrych y mater hwn yma o amrywiaeth. Gadewch i ni weld os byddwn yn difaru mynd yma. Mae hwn yn 100, 90, 75, a 80. 

Gadewch imi wneud yn fyr honiad hwn. Mae hwn yn array, ac unwaith eto, mae'r nodwedd amlwg o amrywiaeth yw bod eich holl ddata yn ôl i gefn wrth gefn yn memory-- llythrennol un beit neu efallai bedwar bytes, rhyw nifer penodol o bytes ffwrdd. Mewn rhestr cysylltiedig, y gallem dynnu fel hyn, o dan y cwfl sydd yn gwybod ble y pethau y mae? Nid oes hyd yn oed yn rhaid iddo lifo fel hyn. Gallai rhai o'r data fod yn yn ôl i'r chwith i fyny yno. Dydych chi ddim hyd yn oed yn gwybod. 

Ac felly gydag amrywiaeth, mae gennych nodwedd a elwir yn fynediad hap. A beth hapgyrch modd yn y gall y cyfrifiadur neidio yn syth i unrhyw leoliad mewn amrywiaeth. Pam? Oherwydd bod y cyfrifiadur yn gwybod bod y lleoliad cyntaf yw sero, un, dau, a thri. 

Ac felly os ydych chi am i fynd o elfen hon at yr elfen nesaf, yn llythrennol, yn y meddwl cyfrifiadur, dim ond ychwanegu un. Os ydych am fynd at y drydedd elfen, dim ond ychwanegu one-- elfen nesaf, dim ond ychwanegu un. Fodd bynnag, yn y fersiwn hwn y stori, mae'n debyg y cyfrifiadur yn edrych ar hyn o bryd ar neu ddelio â'r rhif 100. Sut ydych chi gyrraedd y nesaf gradd yn y llyfr radd? 

rhaid i chi gymryd saith grisiau, sydd yn fympwyol. I gyrraedd yr un nesaf, rhaid i chi cymryd wyth cam arall i gyrraedd 15. Mewn geiriau eraill, nid yw'n bwlch cyson rhwng y rhifau, ac felly mae'n cymryd dim ond y cyfrifiadur mwy o amser yw'r pwynt. Mae'r cyfrifiadur wedi i chwilio drwy gof er mwyn i ddod o hyd i'r hyn rydych chi'n chwilio amdano. 

Felly, tra bod amrywiaeth yn tueddu i fod yn structure-- data cyflym oherwydd eich Gall llythrennol dim ond gwneud rhifyddeg syml a chael lle rydych chi eisiau drwy ychwanegu un, am instance-- rhestr cysylltiedig, byddwch yn aberth y nodwedd honno. nid ydych yn gallu mynd o yn gyntaf i ail i drydydd i'r pedwerydd. rhaid i chi ddilyn y map. Mae'n rhaid i chi gymryd mwy o gamau i gyrraedd y gwerthoedd hynny, sydd Byddai ymddangos yn ychwanegu cost. Felly, rydym yn talu pris, ond beth oedd y nodwedd sy'n Dan yn ceisio yma? Beth mae rhestr cysylltiedig yn ôl pob golwg yn caniatáu i ni wneud, sef y tarddiad y stori arbennig? 

Yn union. Mae maint deinamig iddo. Gallwn ychwanegu at y rhestr hon. Gallwn hyd yn oed yn crebachu y rhestr, felly ein bod yn unig yn defnyddio cymaint o gof gan ein bod mewn gwirionedd yn eisiau, ac felly rydym yn byth dros-dyrannu. 

Nawr dim ond i fod beiau-picky gwirionedd, mae 'na gost gudd. Felly, ni ddylech dim ond gadewch i mi argyhoeddi chi fod hwn yn tradeoff gymhellol. Mae cost gudd arall yma. Mae'r budd-dal, i fod yn glir, yw ein bod yn cael egni. Os ydw i eisiau elfen arall, dim ond gallaf dynnu a rhoi nifer i mewn 'na. Ac yna gallaf gysylltu gyda llun yma, tra dros yma, unwaith eto, os wyf i wedi paentio fy hun i mewn i gornel, os rhywbeth arall eisoes yn defnyddio y cof yma, rwy'n allan o lwc. Rwyf wedi paentio fy hun i mewn i'r gornel. 

Ond beth yw'r cudd gostio yn y llun hwn? Nid dim ond y swm o amser y mae'n ei gymryd i fynd oddi yma i fan hyn, sef saith cam, yna wyth cam, sy'n fwy nag un. Beth yw cost gudd arall? Nid dim ond amser. Gwybodaeth ychwanegol yw angenrheidiol i gyflawni llun hwn. 

Yeah, y map, darnau bychain hynny o papur, gan fy mod yn cadw eu disgrifio fel. Nid yw'r rhain arrows-- hynny yn rhad ac am ddim. Mae computer-- eich bod yn gwybod beth cyfrifiadur wedi. Mae ganddo zeros a rhai. Os ydych am i gynrychioli saeth neu map neu nifer, mae angen rhywfaint o cof. Felly, y pris arall i chi talu am restr cysylltiedig, mae gwyddoniaeth gyfrifiadurol gyffredin adnoddau, lle hefyd. 

Ac yn wir felly, felly yn gyffredin, ymhlith y cyfaddawdu wrth ddylunio peirianneg meddalwedd systemau yn amser a space-- mae dau o'ch cynhwysion, dau o'ch cynhwysion mwyaf costus. Mae hyn yn costio i mi yn fwy o amser gan fod rhaid i mi ddilyn y map hwn, ond mae hefyd yn costio mwy o le i mi oherwydd bod yn rhaid i mi gadw y map o gwmpas. Felly, y gobaith, fel y mae gennym y math o Trafododd dros ddoe a heddiw, yw bod y manteision Bydd yn drech na'r costau. 

Ond does dim ateb amlwg yma. Efallai ei fod yn better-- cyflym la a budr, fel Kareem arfaethedig earlier-- i daflu cof ar y broblem. Dim ond prynu mwy o gof, yn meddwl llai caled ati i ddatrys y broblem, a datrys mewn ffordd haws. Ac yn wir yn gynharach, pan buom yn siarad am cyfaddawdu, nid oedd le yn y cyfrifiadur ac amser. Roedd hi'n amser datblygwr, sy'n yn adnodd arall eto. 

Felly eto, mae'n cydbwysedd hwn geisio penderfynu pa un o'r pethau hynny a ydych yn barod i wario? Pa un yw'r lleiaf drud? Pa gynnyrch canlyniadau gwell? Yeah? 

Yn wir. Yn yr achos hwn, os ydych yn cynrychioli rhifau yn y maps-- gelwir y rhain mewn sawl iaith "Awgrymiadau" neu "gyfeiriadau" - mae'n dwbl y gofod. Nid oes angen hynny fod mor ddrwg fel dwbl os ar hyn o bryd rydym yn unig storio rhifau. Tybiwch ein bod yn storio cofnodion cleifion mewn hospital-- felly enwau Pierson, a rhifau ffôn, rhifau nawdd cymdeithasol, meddyg hanes. Efallai y blwch hwn fod yn llawer, llawer mwy, ac yn yr achos pwyntydd bach bach, cyfeiriad element-- y nesaf nid yw'n beth mawr. Mae'n ymylol o'r fath costio does dim ots. Ond yn yr achos hwn, ie, ei fod yn dyblu. Cwestiwn da. 

Gadewch i ni siarad am amser a ychydig yn fwy diriaethol. Beth yw'r amser yn rhedeg o chwilio'r rhestr hon? Gadewch i ni dybio Roeddwn i eisiau i chwilio drwy bob gradd myfyrwyr, ac mae graddau n yn y strwythur data. Yma, hefyd, gallwn fenthyg geirfa gynharach. Mae hwn yn strwythur data llinol. 

O Big n yw hyn sydd ei angen i gael i ddiwedd y strwythur data, whereas-- ac nid ydym wedi gweld mae hyn before-- arae yn rhoi i chi hyn a elwir amser cyson, sy'n golygu un cam neu ddau gam neu 10 steps-- nid yw o bwys. Mae'n nifer penodol. Mae ganddo ddim i'w wneud â maint y rhesi. A'r rheswm am hynny, unwaith eto, yn mynediad hap. Gall y cyfrifiadur yn unig ar unwaith neidio i leoliad arall, oherwydd eu bod i gyd yr un fath pellter o'r popeth arall. Nid oes unrhyw ffordd o feddwl sy'n gysylltiedig. Iawn. Felly os gallaf, gadewch i mi geisio paent dau lluniau terfynol. Mae un cyffredin iawn a elwir yn dabl hash. Felly, er mwyn cymell y drafodaeth hon, gadewch i mi feddwl am sut i wneud hyn. 

Felly beth am hyn? Gadewch i ni dybio bod y broblem rydym am ddatrys yn awr yn gweithredu mewn dictionary-- felly criw cyfan o eiriau Saesneg neu beth bynnag. A'r nod yw bod yn gallu ateb cwestiynau y ffurflen yw hon gair? Felly rydych chi am weithredu gwirydd sillafu, dim ond fel eiriadur corfforol y gallwch edrych pethau i fyny yn. Gadewch i ni dybio bawn yn gwneud hyn gydag amrywiaeth. Gallwn wneud hyn. 

Ac yn debyg y geiriau yn cael eu afal a banana a cantaloupe. Ac ni allaf feddwl am ffrwythau sy'n dechrau gyda d, felly rydym yn unig mynd i gael tri ffrwythau. Felly mae hwn yn array, ac rydym yn storio pob un o'r geiriau hyn mewn geiriadur hwn fel arae. Y cwestiwn, felly, yw sut arall gallech storio'r wybodaeth hon? 

Wel, dwi'n fath o dwyllo yma, oherwydd pob un o'r llythyrau hyn yn y gair yn wir yn beit unigol. Felly, os Fi 'n sylweddol eisiau bod yn nit-picky, dylwn 'n sylweddol fod yn rhannu'r hyn i fyny i mewn i lawer ddarnau llai o gof, a gallem wneud yn union hynny. Ond rydym yn mynd i redeg i mewn i yr un broblem ag o'r blaen. Beth os, fel Merriam Webster neu Rhydychen yn gwneud pob year-- maent yn ychwanegu geiriau i'r dictionary-- nid ydym yn ei wneud o reidrwydd eisiau i beintio ein hunain mewn cornel gydag amrywiaeth? 

Felly yn lle hynny, efallai ymagwedd graffach yw rhoi afal yn ei nod neu flwch ei hun, fel y byddem yn ei ddweud, banana, ac yna dyma gennym cantaloupe. A llinyn yr ydym pethau hyn gyda'n gilydd. Felly, mae hyn yn y casgliad, ac hwn yw'r rhestr gysylltiedig. Os nad ydych yn gallu hollol weld, 'i jyst dweud "array," ac mae hyn yn dweud "rhestr." 

Felly, rydym yn cael yr un union faterion fel o'r blaen, lle mae gennym bellach dynamiaeth yn ein rhestr cysylltiedig. Ond mae gennym geiriadur eithaf araf. Tybiwch Rwyf am i chwilio am air. Gallai gymryd i mi O fawr o n camau, oherwydd gallai'r gair fod yr holl ffordd ar ddiwedd y y rhestr, fel cantaloupe. Ac mae'n troi allan y mewn rhaglenni, didoli o greal sanctaidd o ddata strwythurau, yn rhywbeth sy'n rhoi i chi yn gyson amser fel arae ond mae hynny'n dal i roi egni i chi. 

Felly, gallwn gael y gorau o ddau fyd? Ac yn wir, mae yna rywbeth Gelwir y tabl hash sy'n eich galluogi i wneud yn union hynny, er tua. Mae tabl hash yn ffansi strwythur data sydd gennym gallu meddwl am fel y cyfuniad o array-- ac rwy'n mynd i dynnu ei fel this-- a rhestrau cysylltiedig y byddaf yn tynnu fel hyn dros yma. 

A'r ffordd y peth hyn gweithiau fel a ganlyn. Os now-- hyn hash table-- yw fy nhrydydd strwythur data, ac yr wyf am i storio geiriau yn hyn, nid wyf yn ei wneud eisiau i ddim ond storio'r holl geiriau cefn wrth gefn wrth gefn wrth gefn. Rwyf am i trosoledd rhai darn o wybodaeth am y geiriau a fydd yn gadael mi ei gael ble mae'n gyflymach. 

Felly o ystyried y geiriau afal a banana a cantaloupe, Dewisais fwriadol geiriau hynny. Pam? Beth sydd fath o sylfaenol yn wahanol am y tri? Beth yw'r amlwg? Maent yn dechrau gyda gwahanol lythrennau. 

Felly, rydych yn gwybod beth? Yn hytrach na rhoi fy holl eiriau yn yr un bwced, fel petai, tebyg yn un rhestr hir, pam na gwneud Rwyf o leiaf roi cynnig ar Optimization a gwneud fy rhestrau 1/26 mor hir. A Optimization cymhellol allai fod pam na gwneud I-- wrth fewnosod gair i mewn i hyn strwythur data, i mewn i gof y cyfrifiadur, pam peidiwch â wyf yn rhoi'r holl 'a' geiriau yma, holl eiriau 'b' yma, a'r holl 'c' geiriau yma? Felly, mae hyn yn dod i ben i fyny gan roi afal yma, banana yma, cantaloupe yma, ac yn y blaen. 

Ac os oes gennyf ychwanegol gair like-- beth arall? Afal, banana, gellygen. Unrhyw un feddwl am ffrwythau sy'n dechrau gyda, b, neu c? perffaith Blueberry--. Mae hynny yn mynd i roi diwedd ar i fyny yma. Ac felly rydym yn ymddangos i fod â ychydig yn well ateb, oherwydd erbyn hyn os ydw i eisiau i chwilio am afal, yr wyf yn first-- Dydw i wneud yn union deifio i mewn i fy strwythur data. Dydw i ddim yn plymio i mewn i gof fy cyfrifiadur. Yr wyf yn edrych yn gyntaf ar y llythyr cyntaf. 

Ac mae hyn yn beth cyfrifiadur Byddai gwyddonydd yn dweud. Rydych hash i mewn i'ch strwythur data. Byddwch yn cymryd eich cyfraniad, sydd yn ei yr achos hwn yw gair fel afal. Rydych yn dadansoddi, gan edrych ar y llythyr cyntaf yn yr achos hwn, a thrwy hynny stwnsio iddo. Mae stwnsio yn lle derm cyffredinol eich bod yn cymryd rhywbeth fel mewnbwn a ydych yn cynhyrchu rhywfaint o allbwn. Ac mae'r allbwn yn y achos yn y lleoliad rydych am ei chwilio, y cyntaf lleoliad, ail leoliad, yn drydydd. Felly mae'r mewnbwn yn afal, mae'r allbwn yn gyntaf. Mae'r mewnbwn yn banana, mae'r Dylai allbwn fod yn ail. Mae'r mewnbwn yn cantaloupe, Dylai'r allbwn fod yn drydydd. Mae'r mewnbwn yn llus, mae'r Dylai allbwn eto fod yn ail. A dyna beth yn eich helpu i gymryd llwybrau byr trwy eich cof er mwyn cael at eiriau neu ddata yn fwy effeithiol. 

Yn awr mae hyn yn torri i lawr ein hamser o bosibl gan gymaint â un allan o 26, oherwydd os byddwch yn cymryd yn ganiataol y byddwch yn gael cymaint "a" geiriau fel "z" geiriau fel "q" geiriau, a oedd yn Nid yw 'n sylweddol realistic-- rydych yn mynd i gael gogwydd ar draws llythyrau penodol o'r alphabet-- ond byddai hyn yn gynyddrannol dull yw'n caniatáu i chi fynd i eiriau yn gyflymach o lawer. Ac mewn gwirionedd, mae soffistigedig rhaglen, mae'r Googles y byd, y Facebooks y world-- byddent yn defnyddio tabl hash am lawer o wahanol ddibenion. Ond ni fyddent yn mor naïf fel i dim ond yn edrych ar y llythyr cyntaf mewn afal neu fanana neu gellygen neu cantaloupe, oherwydd fel y gallwch weld y rhain Gallai rhestrau yn dal i gael hir. 

Ac felly gallai hyn yn dal i fod yn fath o linear-- felly math o araf, fel gyda O mawr o n ein bod yn trafod yn gynharach. Felly beth tabl hash da go iawn a fydd do-- bydd yn cael llawer mwy o amrywiaeth. A bydd yn defnyddio llawer mwy swyddogaeth stwnsio soffistigedig, fel nad yw dim ond yn edrych ar y "a." Efallai ei fod yn edrych ar "a-p-p-l-e" a rywsut yn trosi y rhai pum llythyr i mewn i'r lleoliad lle Dylai afal yn cael ei storio. Rydym yn unig yn ddiniwed gan ddefnyddio'r llythyren 'a' ei ben ei hun, am ei fod yn neis ac yn syml. 

Ond tabl hash, yn y diwedd, gallwch chi feddwl o fel cyfuniad o amrywiaeth, pob un ohonynt Mae rhestr cysylltiedig yn ddelfrydol Dylai fod mor fyr ag y bo modd. Ac nid yw hyn yn ateb amlwg. Yn wir, mae llawer o'r mireinio sy'n mynd ymlaen o dan y cwfl pan gweithredu'r mathau hyn o strwythurau data soffistigedig yw'r hyn yw'r hawl hyd y rhesi? Beth yw swyddogaeth hash iawn? Sut ydych chi'n cadw pethau mewn cof? 

Ond yn sylweddoli pa mor gyflym y math hwn o drafodaeth dwysáu, naill ai hyd yn hyn ei fod yn garedig o dros un o ben ar y pwynt hwn, a oedd yn yn iawn. Ond rydym yn dechrau, galw i gof, gyda wirioneddol rhywbeth lefel isel ac electronig. Ac felly mae hyn eto yw hyn thema tynnu dŵr, lle ar ôl i chi ddechrau cymryd yn ganiataol, OK, mae gen iddo-- mae cof corfforol, OK, got it, bob lleoliad ffisegol Mae cyfeiriad, OK, yr wyf yn got it, gallaf gynrychioli cyfeiriadau hynny fel arrows-- gallwch ddechrau gyflym iawn i gael sgyrsiau mwy soffistigedig sy'n yn y pen draw yn ymddangos i fod ganiatáu i ni i ddatrys problemau fel chwilio a didoli yn fwy effeithiol. Ac yn sicr, too-- am fy mod yn credu bod hyn yw'r dyfnaf ein bod wedi mynd i mewn i rai o'r rhain pynciau CS proper-- rydym wedi wneud mewn diwrnod a hanner ar hyn pwyntio beth y gallech fel arfer yn wneud dros cwrs wyth wythnos mewn semester. 

Unrhyw gwestiynau am y rhain? Na? Iawn. Wel, pam nad ydym yn oedi yno, dechrau cinio ychydig funudau yn gynnar, ailddechrau mewn dim ond tua awr? A byddaf yn aros am ychydig gyda chwestiynau. Yna mi i'n mynd i gael i fynd cymryd galwadau cwpl os mae hynny'n iawn. 'N annhymerus' droi ar gerddoriaeth yn y cyfamser, ond dylai cinio fod rownd y gornel.