SIARADWR 1: pob hawl, felly mae hyn yn CS50 Dyma ddiwedd yr wythnos pump. Ac yn dwyn i gof bod tro diwethaf i ni dechrau edrych ar y data fancier strwythurau a ddechreuodd i ddatrys problemau, a ddechreuodd i gyflwyno problemau newydd, ond yr allwedd i hyn Roedd y math o edafu yr ydym dechrau gwneud o nod i nod. Felly, mae hyn wrth gwrs yw rhestr cysylltiedig yn unigol. Ac erbyn cysylltiedig yn unigol, Yr wyf yn golygu nid dim ond un edau rhwng pob un o'r nodau hynny. Troi allan y gallwch ei wneud ffansi pethau fel rhestrau cysylltiedig ddwbl lle mae gennych saeth mynd i'r ddau gyfeiriad, a oedd yn Gall helpu gyda rhai arbedion effeithlonrwydd. Ond mae hyn yn datrys y broblem? Pa broblem oedd hyn yn datrys? Pam oeddem yn gofalu ar ddydd Llun? Pam, mewn theori, oedd yr ydym yn gofalu ar ddydd Llun? Beth mae'n ei wneud? 

GYNULLEIDFA: Gallwn ddynamig newid maint iddo. 

SIARADWR 1: Iawn, felly y gallwn ddeinamig newid maint iddo. Da iawn y ddau ohonoch. Felly gallwch ddeinamig newid maint hwn strwythur data, tra amrywiaeth, galw i gof, rhaid i chi wybod a priori faint o le yr ydych am ac os oes angen ychydig o mwy gofod, rydych yn fath o allan o lwc. Mae'n rhaid i chi greu casgliad newydd cyfan. Rhaid i chi symud eich holl data o un i'r llall, yn y pen draw rhad ac am ddim yr hen array os gallwch, ac yna symud ymlaen. A dim ond yn teimlo'n gostus iawn ac yn iawn aneffeithlon, ac yn wir y gall fod. Ond nid yw hyn i gyd yn dda. Rydym yn talu pris, beth oedd un o'r prisiau yn fwy amlwg i ni dalu drwy ddefnyddio rhestr cysylltiedig? 

GYNULLEIDFA: Mae'n rhaid i ni ddefnyddio gofod dwbl ar gyfer pob un. SIARADWR 1: Yeah, felly mae angen o leiaf ddwywaith cymaint o le. A dweud y gwir, yr wyf yn sylweddoli y llun hwn hyd yn oed ychydig yn gamarweiniol, oherwydd ar IDE CS50 mewn llawer o modern cyfrifiaduron, pwyntydd neu gyfeiriad nad yw mewn gwirionedd pedwar bytes. Yn aml iawn mae'r rhain wyth niwrnod bytes, a oedd yn yn golygu y gwaelod fwyaf petryal yno mewn gwirionedd yn fath o ddwywaith yn fawr fel hyn yr wyf wedi tynnu, sy'n golygu eich bod yn defnyddio tair gwaith yn fwy llawer o le ag y gallai fod yn rhaid fel arall. Nawr ar yr un pryd, rydym yn dal i siarad bytes, dde? Nid ydym yn o angenrheidrwydd yn siarad megabeit neu gigabeit, oni bai bod y data hyn yn cael strwythurau mawr. 

Ac felly heddiw rydym yn dechrau ystyried sut y gallem edrych ar ddata yn fwy effeithlon os yn ffaith y data fynd yn fwy. Ond gadewch i ni geisio canonicalize y gweithrediadau yn gyntaf y gallwch ei wneud ar y rhain mathau o strwythurau data. Felly rhywbeth fel cysylltiedig rhestr yn gyffredinol yn cefnogi gweithrediadau yn hoffi dileu, mewnosod, a chwilio. A beth ydw i'n ei olygu wrth hynny? Mae hynny'n ei olygu yw bod fel arfer, os yw pobl yn defnyddio rhestr gysylltiedig, eu bod nhw neu rywun arall wedi gweithredu swyddogaethau fel dileu, mewnosod, a chwilio, fel y gallwch mewn gwirionedd yn gwneud rhywbeth ddefnyddiol gyda'r strwythur data. Felly, gadewch i ni edrych cyflym ar sut y gallem gweithredu rhyw cod ar gyfer restr cysylltiedig fel a ganlyn. 

Felly, mae hyn yn unig yw ychydig cod C, Nid yw hyd yn oed yn rhaglen gyflawn bod Fi 'n sylweddol yn gyflym chwipio i fyny. Dyw hi ddim yn ar-lein yn y dosbarthiad cod, oherwydd ni fydd yn rhedeg mewn gwirionedd. Ond yn sylwi Rwyf newydd gyda dywedodd sylw, dot dot dot, mae rhywbeth yno, dot dot dot, rhywbeth yno. A gadewch i ni dim ond yn edrych ar beth yw'r rhannau llawn sudd yn cael eu. Felly, ar-lein tri, dwyn i gof bod hwn bellach cynigiwyd datgan nod diwethaf amser, un o wrthrychau hirsgwar hynny. Mae ganddo int y byddwn yn galw N, ond y gellid ei alw unrhyw beth, ac yna yn seren nôd struct elwir nesaf. A dim ond i fod yn glir, bod ail llinell, ar-lein chwech, beth yw hynny? Beth mae'n ei wneud i ni? Oherwydd ei fod yn sicr yn edrych yn fwy cryptic na'n newidynnau arferol. 

GYNULLEIDFA: Mae'n ei gwneud yn symud dros un. 

SIARADWR 1: Mae'n ei gwneud yn symud dros un. Ac i fod yn fwy manwl gywir, bydd yn storio y cyfeiriad y nôd sydd wedi golygu i fod semantig nesaf iddo, dde? Felly, nid yw'n mynd i o reidrwydd yn symud unrhyw beth. Dim ond ei fod yn mynd i storio gwerth, sy'n cael ei mynd i fod yn y cyfeiriad o ryw nod arall, a dyna pam yr ydym wedi dweud struct seren nôd, y seren sy'n dynodi pwyntydd neu gyfeiriad. Iawn, felly nawr os ydych yn cymryd yn ganiataol bod gennym N hon ar gael i ni, a gadewch i ni gymryd yn ganiataol bod rhywun arall wedi mewnosod criw cyfan o gyfanrifau i mewn i restr cysylltiedig. A dyna rhestr cysylltiedig yn yn tynnu sylw at gan ryw adeg a elwir yn rhestr newidyn sy'n pasio i mewn yma fel paramedr, sut ydw i'n mynd ati lein 14 gweithredu chwilio? Mewn geiriau eraill, os wyf yn gweithredu swyddogaeth y mae ei bwrpas mewn bywyd yw i gymryd int ac yna'r gan ddechrau o restr cysylltiedig, hynny yw pwyntydd at y rhestr cysylltiedig. Fel y tro cyntaf, pwy yr wyf yn meddwl David oedd ein gwirfoddolwyr ar ddydd Llun, yr oedd yn pwyntio at y cyfan cysylltiedig rhestr, 'i' fel pe rydym yn pasio David mewn fel ein dadl yma. Sut ydym yn mynd ati i croesi y rhestr hon? Wel, mae'n ymddangos fod hyd yn oed er awgrymiadau yn gymharol newydd yn awr i ni, y gallwn wneud hyn yn gymharol yn ddirwystr. 

Rydw i'n mynd i fynd yn ei flaen a ddatgan newidyn dros dro sy'n drwy gonfensiwn yn unig yn mynd i gael ei alw pwyntydd, neu PTR, ond gallech ei alw'n unrhyw beth yr hoffech. Ac yr wyf i'n mynd i ymgychwyn i gychwyn y rhestr. Felly, gallwch chi fath o feddwl am hyn â mi yr athro y diwrnod o'r blaen, math o pwyntio at rywun ymhlith ein pobl fel gwirfoddolwyr. Felly, rwy'n newidyn dros dro sy'n dim ond pwyntio at yr un peth bod ein enwir gyd-ddigwyddiad Roedd gwirfoddolwr David hefyd yn tynnu sylw at. Tra pwyntydd yn Nid null, gan fod galw yn ôl hynny null rhywfaint o werth sentinel arbennig y llinell rhwng diwedd y rhestr, felly er nad i ddim yn pwyntio at y tir fel ein gwirfoddolwr diwethaf oedd, gadewch i ni fynd yn ei flaen ac yn gwneud y canlynol. Os pointer-- ac yn awr yr wyf yn fath o eisiau i wneud yr hyn a wnaethom gyda'r myfyriwr structure-- os pwyntydd dot nesaf equals-- hytrach, os pwyntydd dot N hafal hafal newidyn N, mae'r ddadl bod wedi ei basio i mewn, yna rwyf eisiau mynd yn ei flaen a dweud yn dychwelyd yn wir. Rwyf wedi dod o hyd i'r rhif N tu mewn un o'r nodau o fy rhestr cysylltiedig. Ond mae'r dot mwyach gweithio yn y cyd-destun hwn, gan fod pwyntydd, PTR, yw yn wir pwyntydd, cyfeiriad, o fewn ein gallu rhyfeddol mewn gwirionedd defnyddio yn olaf ddarn o gystrawen y math hwnnw o wneuthuriadau synnwyr greddfol ac mewn gwirionedd Defnyddiwch saeth yma, sy'n golygu mynd o y cyfeiriad hwnnw i'r cyfanrif yno yn. Felly mae'n debyg iawn mewn ysbryd i weithredwr y dot, ond gan nad pwyntydd yn pwyntydd ac nid yn struct ei hun, rydym yn unig yn defnyddio'r saeth. 

Felly, os yw'r nôd presennol fy mod i, mae'r newidyn dros dro, mae'n pwyntio at nid N, beth ydw i am ei wneud? Wel, gyda fy gwirfoddolwyr dynol bod gennym yma y diwrnod o'r blaen, os nad yw fy dynol cyntaf yw'r un yr wyf yn eisiau, ac efallai nad yw'r ail dynol yn yr un yr wyf am, a'r trydydd, yr wyf yn Mae angen i gadw yn gorfforol i symud. Fel sut ydw i'n camu trwy restr? Pan gawsom amrywiaeth, yr ydych yn unig oedd fel fy mod yn ogystal a mwy. Ond yn yr achos hwn, mae'n suffices i gwneud pwyntydd, yn cael, pwyntydd, nesaf. Mewn geiriau eraill, mae'r cae nesaf Mae fel yr holl ddwylo chwith bod ein gwirfoddolwyr dynol ar ddydd Llun Roedd defnyddio i bwynt ar ryw nod arall. Y rhai oedd eu cymdogion nesaf. 

Felly, os wyf am i gamu drwy'r rhestr hon, Ni allaf ond yn gwneud i mi yn ogystal yn ogystal anymore, Yn lle hynny rhaid i mi ddweud I, pwyntydd, yn mynd i cyfartal beth bynnag y cae nesaf yw, y cae nesaf yw, y cae nesaf yw, yn dilyn pob un o'r rhai a adawodd dwylo a gawsom ar pwyntio llwyfan i rai gwerthoedd dilynol. Ac os caf drwy hynny iteriad cyfan, ac yn olaf, yr wyf yn taro null peidio â chael dod o hyd N eto, Fi jyst yn dychwelyd ffug. Felly unwaith eto, i gyd yr ydym yn ei wneud yma, yn unol â'r darlun funud yn ôl, yn dechrau drwy bwyntio ar y gan ddechrau o'r rhestr yn ôl pob tebyg. Ac yna yr wyf yn gwirio, yw gwerth Dwi'n chwilio am gyfartal i naw? Os felly, yr wyf yn dychwelyd yn wir ac rwy'n ei wneud. Os nad yw, diweddaru fy llaw, AKA pwyntydd, i bwynt yn y lleoliad y saeth nesaf, ac Yna, lleoliad y saeth nesaf, a'r nesaf. Im 'yn syml cerdded trwy amrywiaeth hwn. 

Felly unwaith eto, sy'n gofalu? Fel beth yw hyn cynhwysyn amdano? Wel, yn cofio inni gyflwyno y syniad o stac, a oedd yn yn ddata haniaethol teipiwch i'r graddau y mae'n Nid yw yn beth C, nid ei fod yn beth CS50, ei fod yn syniad haniaethol, y syniad hwn o stacio pethau ar ben ei gilydd y gellir eu rhoi ar waith yn tusw o wahanol ffyrdd. Ac un ffordd yr ydym arfaethedig gyda amrywiaeth, neu gyda rhestr cysylltiedig. Ac mae'n ymddangos bod canonically, mae stac yn cefnogi o leiaf ddau gweithrediadau. A'r geiriau wefr yn gwthio, i gwthio rhywbeth ar y pentwr, fel hambwrdd newydd yn y neuadd fwyta, neu pop, sy'n golygu cael gwared ar y topmost hambwrdd o'r pentwr yn yr ystafell fwyta neuadd, ac yna efallai rhai gweithrediadau eraill yn ogystal. Felly, sut y gallem diffinio strwythur ein bod yn awr yn galw stac? 

Wel, mae gennym yr holl angenrheidiol cystrawen ar gael i ni yn C. wyf yn dweud, roi diffiniad math o fi mae struct tu mewn pentwr, Dw i'n mynd i ddweud yn array, o criw cyfan o rifau ac yna maint. Felly, mewn geiriau eraill, os ydw i eisiau gweithredu hyn mewn cod, gadewch i mi fynd a dim ond math o tynnu beth mae hyn yn ei ddweud. Felly, mae hyn yn ei ddweud, yn rhoi i mi strwythur sy'n got amrywiaeth, ac nid wyf yn gwybod beth yw capasiti, mae'n debyg mae rhai gyson fy mod i wedi ddiffinnir mewn mannau eraill, ac mae hynny'n iawn. Ond mae'n debyg mai dim ond un, dau, tri, pedwar, pump. Felly gallu yn 5. Mae'r elfen hon tu mewn fy Bydd y strwythur yn cael eu galw rhifau. Ac yna angen un i mi newidyn arall yn ôl pob golwg Gelwir maint y lle cyntaf i ddim yn mynd i bennu ei initialized i sero. Os does dim byd yn y pentwr, maint yn sero, ac mae'n gwerthoedd garbage mewn niferoedd. Nid oes gennyf unrhyw syniad beth sydd yno eto. 

Felly, os ydw i eisiau i wthio rhywbeth ar y pentwr, Mae'n debyg imi alw ar y gwthio swyddogaeth, ac Rwy'n dweud gwthio 50, fel y rhif 50, lle y byddech yn cynnig Tynnaf mewn amrywiaeth hon? Mae pum atebion gwahanol posibl. Ble ydych chi eisiau gwthio'r rhif 50? Os bydd y nod yma, unwaith eto, ffoniwch y gwthio swyddogaeth, pasio mewn dadl 50, lle ydw i'n ei roi? Pum possible-- 20% siawns o ddyfalu'n gywir. Do? 

GYNULLEIDFA: Dde pellaf. 

SIARADWR 1: Dde pellaf. Erbyn hyn 25% o siawns o ddyfalu'n gywir. Felly byddai mewn gwirionedd yn iawn. Trwy gonfensiwn, byddaf yn dweud gydag amrywiaeth, byddem yn gyffredinol yn dechrau ar y chwith, ond gallem yn sicr yn dechrau ar y dde. Felly byddai'r spoiler yma fod rwy'n yn ôl pob tebyg yn mynd i dynnu ei ar y chwith, yn union fel mewn amrywiaeth arferol lle Yr wyf yn dechrau mynd i'r chwith i'r dde. Ond os gallwch troi y rhifyddeg, dirwy. Nid dim ond confensiynol. OK, mae angen i mi wneud un mwy o newid er. Nawr fy mod i wedi gwthio rhywbeth ar y pentwr, beth nesaf? 

Mae pob hawl, rhaid i mi gynyddiad y maint. Felly gadewch i mi fynd yn ei flaen a dim ond diweddaru'r hwn, a oedd sero. Ac yn lle nawr, dw i'n mynd i'w roi yn y gwerth un. Ac yn awr yr wyf yn debyg gwthio arall rhif ar y simnai, fel 51. Wel, rhaid i mi wneud un yn fwy newid, sef hyd at faint dau. Ac yna mae'n debyg fy mod yn gwthio un yn fwy rhif ar y stac fel 61, yn awr mae angen i mi ddiweddaru'r maint un yn fwy amser, a chael y gwerth 3 gan fod maint. Ac yn awr mae'n debyg wyf yn galw pop. Nawr pop, gan gonfensiwn, nid yw'n cymryd dadl. Gyda pentwr, y cyfan bwynt y trosiad hambwrdd yw nad oes gennych hawl i fynd gael y hambwrdd, gall pob chi ei wneud yn pop y un topmost o y pentwr, dim ond oherwydd. Dyna beth mae hyn yn strwythur data yn ei wneud. 

Felly, gan y rhesymeg os byddaf dweud pop, beth sy'n dod i ffwrdd? Felly 61. Felly beth mewn gwirionedd yw y cyfrifiadur mynd i'w wneud yn y cof? Beth sydd gan fy cod i wneud? Beth fyddech chi'n ei gynnig rydym yn newid ar y sgrin? Beth ddylai newid? Mae'n ddrwg gennym? Felly, rydym yn cael gwared o 61. Fel y gallaf bendant yn gwneud hynny. A allaf gael gwared ar 61. Ac yna beth arall Mae angen newid i ddigwydd? Yn ôl pob tebyg gan faint i fynd yn ôl i ddau. Ac felly mae hynny'n iawn. Ond arhoswch funud, maint funud yn ôl yn dair. Gadewch i 'jyst gwneud gwiriad bwyll cyflym. Sut oedd rydym yn gwybod ein bod yn Yn eisiau i gael gwared o 61? Oherwydd ein bod yn popping. Ac felly mae gen i ail maint eiddo. 

Arhoswch funud, rwy'n meddwl yn ôl i'r wythnos dau pan fyddwn yn dechrau siarad am araeau, lle'r oedd y lleoliad sero, roedd hyn yn lleoliad un, roedd hyn yn lleoliad dau, mae hyn yn lleoliad tri, pedwar, mae'n edrych yn debyg y berthynas rhwng maint a'r elfen yr wyf am ei dynnu o'r amrywiaeth yn ymddangos i ddim ond fod yn beth? Maint minws un. Ac felly dyna sut fel bodau dynol rydym yn gwybod 61 sy'n dod gyntaf. Sut mae cyfrifiadur yn mynd i wybod? Pan fydd eich cod, lle rydych yn ôl pob tebyg am wneud un maint minws, felly tair llai un yw dau, a bod yn golygu ein bod yn awyddus i gael gwared o 61. Ac yna gallwn yn wir diweddaru maint fel maint hwnnw yn awr mynd o dri i ddim ond dau. A dim ond i fod yn bedantig, dw i'n mynd i gynnig fy mod i'n gwneud hyn, dde? Rydych yn cynnig reddfol yn gywir dylwn i gael gwared o 61. Ond wedi nid wyf yn fath o fath o gotten gwared o 61? Rwyf wedi anghofio effeithiol ei fod mewn gwirionedd yno. Ac yn meddwl yn ôl i PSET4, os ydych wedi darllen mae'r erthygl am fforensig, y PDF ein bod wedi cael chi guys yn darllen, neu os ydych yn Bydd darllen yr wythnos hon ar gyfer PSET4. Dwyn i gof bod hyn mewn gwirionedd germane i yr holl syniad o fforensig cyfrifiadurol. Beth cyfrifiadur yn gyffredinol yn ei wneud yw 'i jyst yn anghofio lle mae rhywbeth yn, ond nid yw'n mynd i mewn ac yn hoffi ceisiwch grafu allan neu gwrthwneud darnau rhai sydd â seroau a rhai neu ryw batrwm eraill ar hap oni bai eich bod chi eich hun yn gwneud hynny yn fwriadol. Felly eich greddf yn hawl, gadewch i ni gael gwared o 61. Ond mewn gwirionedd, nid oes raid i ni trafferthu. Jyst angen i ni anghofio bod ei fod yno trwy newid ein maint. 

Nawr bod yna broblem gyda phentwr hwn. Os byddaf yn cadw gwthio pethau ar y pentwr, beth yn amlwg yn mynd i ddigwydd mewn dim ond amser eiliadau ychydig? Rydym yn mynd i redeg allan o le. A beth ydym yn ei wneud? Rydym yn fath o sgriwio. Nid yw hon ar waith yn gadael ni newid maint y rhesi, gan fod defnyddio cystrawen hwn, os ydych yn meddwl yn ôl i'r wythnos dau, unwaith y byddwch wedi datgan maint amrywiaeth, nid ydym wedi gweld eto mecanwaith lle gallwch newid maint y rhesi. Ac yn wir nid oes gan y nodwedd C. Os ydych yn dweud yn rhoi pump i mi Nths, yn eu galw rhifau, dyna i gyd ydych chi'n mynd i gael. Felly, rydym yn ei wneud yn awr fel Lun, gael y gallu i fynegi ateb fodd bynnag, mae'n rhaid i ni tweak y diffiniad o ein pentwr i beidio â bod rhywfaint o amrywiaeth hard-coded, ond dim ond i storio cyfeiriad. 

Yn awr pam? Nawr rydym yn unig rhaid i ni fod yn gyfforddus gyda y ffaith bod pan oedd fy rhaglen yn rhedeg, Yn ôl pob tebyg dwi'n mynd i rhaid gofyn i'r bobl, faint o rifau ydych chi am i storio? Felly mae'r mewnbwn yn gorfod dod o rywle. Ond ar ôl i mi yn gwybod bod rhif, yna gallaf jyst defnyddio'r hyn swyddogaeth i roi mi darn o gof? Gallaf ddefnyddio malloc. A gallaf ddweud unrhyw nifer o bytes Rwyf am yn ôl ar gyfer Nths hyn. A'r holl rhaid i mi gadw yn y niferoedd newidyn yma tu mewn struct hwn Dylai fod yn beth? Yr hyn mewn gwirionedd yn mynd i mewn i'r rhifau yn y senario hwn? Yeah, pwyntydd i'r cyntaf beit o fod darn o gof, neu yn fwy penodol, y cyfeiriad o'r cyntaf bytes hynny. Nid yw'n ots os yw'n un beit neu biliwn bytes, Fi jyst angen i ofalu am y cyntaf. Oherwydd hyn y gwarantau malloc a fy gwarantau system weithredu, yw bod y darn o gof i mi ei gael, mae'n mynd i fod yn gyffiniol. Nid oes yn mynd i fod bylchau. Felly os dwi wedi gofyn am 50 bytes neu 1,000 o bytes, maen nhw i gyd yn mynd i fod gefn wrth gefn wrth gefn. Ac ar yr amod fy mod yn cofio pa mor fawr, sut cymaint yr wyf yn gofyn amdano, y cyfan sydd angen i mi ei wybod yw cyfeiriad cyntaf o'r fath. 

Felly, yn awr mae gennym y gallu yn y cod. Er, mae'n mynd i fynd â ni mwy o amser i ysgrifennu hyn i fyny, gallem yn awr yn ailddyrannu y cof gan dim ond storio cyfeiriad gwahanol yno os ydym am gael mwy neu hyd yn oed cyfran lai o gof. Felly dyma i ffwrdd masnach. Nawr rydym yn cael egni. Rydym yn dal i gael contiguousness Rydw i'n hawlio. Gan y bydd malloc yn rhoi i ni darn cydgyffwrdd o gof. Ond mae hyn yn mynd i fod yn boen yn y gwddf i ni, y rhaglennydd, i mewn gwirionedd godio i fyny. 'I' jyst mwy o waith. Mae arnom angen cod debyg i hyn yr wyf yn curo allan ychydig funudau'n ôl. Doable iawn, ond mae'n ychwanegu cymhlethdod. Ac felly amser datblygwr, rhaglennydd mae amser yn adnodd arall eto y gallai fod angen i ni ei wario peth amser i gael nodweddion newydd. Ac yna, wrth gwrs, mae ciw. Ni fyddwn yn mynd i mewn i hyn un mewn cymaint o fanylion. Ond mae'n debyg iawn o ran ysbryd. Gallwn i weithredu ciw, ac ei weithrediadau cyfatebol, enqueue neu dequeue, fel ychwanegu neu ddileu, 'i' jyst yn ffordd ffansi o ddweud ei fod, enqueue neu dequeue, fel a ganlyn. Gallaf roi struct fy hun hynny eto mae amrywiaeth nifer o, hynny eto mae gan faint, ond pam ydw i'n awr mae angen i gadw golwg ar flaen ciw? Nid oedd angen i mi ei wybod flaen fy pentwr. Wel, os wyf eto am queue-- gadewch i jyst galed cod ei fel rhai sydd fel phum gyfanrifau mewn yma o bosibl. Felly, mae hyn yn sero, un, dau, tri, pedwar. Mae hyn yn mynd i fod Gelwir rhifau eto. A bydd hyn yn cael eu galw maint. 

Pam ei fod nid yn ddigonol i gael faint yn unig? Wel, gadewch i wthio un niferoedd hynny ar. Felly, yr wyf pushed-- fy mod enqueued, neu eu gwthio. Nawr byddaf yn enqueue 50, ac yna 51, ac yna 61, a dot dot dot. Felly dyna enqueue. Yr wyf yn enqueued 50, yna 51, yna 61. Ac mae hynny'n edrych yn union yr un fath i stac hyd yn hyn, ac eithrio mae angen i mi wneud un newid. Mae angen i mi ddiweddaru maint hwn, felly yr wyf yn mynd o sero i un to 02:58 awr. Sut mae dequeue? Beth fydd yn digwydd gyda dequeue? Pwy ddylai ddod oddi ar y rhestr hon yn gyntaf os mai dyma'r lein yn y Storfa Apple? Felly 50. Felly mae'n fath o anoddach y tro hwn. Tra tro diwethaf yr oedd yn super hawdd i ychydig wneud un maint minws, Rwy'n cael i ddiwedd fy array yn effeithiol lle mae'r niferoedd yn, mae'n cael gwared 61. Ond dwi ddim am gael gwared 61. Rwyf am gymryd 50, sy'n oedd yno ar 05:00 i linell i fyny ar gyfer y iPhone neu whatnot newydd. Ac felly i gael gwared o 50, yr wyf yn Ni all dim ond gwneud hyn, dde? Gallaf groesi allan 50. Ond rydym newydd ei ddweud ein bod Nid oes rhaid i fod mor rhefrol ag i grafu allan neu'n cuddio y data. Allwn anghofio lle y mae. 

Ond os byddaf yn newid fy maint yn awr i dau, a yw hyn yn ddigon o wybodaeth i wybod beth sy'n digwydd yn fy ciw? Ddim mewn gwirionedd. Fel fy maint yw dau, ond lle mae'r ciw yn dechrau, yn enwedig os wyf yn dal i gael yr un niferoedd hynny yn y cof. 50, 51, 61. Felly mae angen i mi gofio Erbyn hyn lle y tu blaen yn. Ac felly gan fy mod yn cynnig i fyny yno, byddwn yn newydd o'r enw Blaen nfed, y mae eu cychwynnol Dylai gwerth wedi bod yn beth? Zero, dim ond y dechrau y rhestr. Ond yn awr yn ychwanegol at decrementing maint, rydym yn unig cynyddiad y tu blaen. Nawr dyma broblem arall. Felly, unwaith Rwy'n cadw i fynd. Gadewch i ni dybio hyn yw nifer y fel 121, 124, ac yna, dammit, Rwy'n allan o le. Ond arhoswch funud, dydw i ddim. Felly, yn y fan hon yn y stori, Mae'n debyg bod maint yn un, dau, tri, pedwar, felly mae'n debyg bod y faint yw pedwar, y tu blaen yn un, felly 51 yw yn y tu blaen. Rwyf eisiau rhoi rhif arall yma, ond, dammit, rwy'n allan o le. Ond dydw i ddim mewn gwirionedd, dde? Ble gallwn i roi rhai gwerth ychwanegol, fel 171? Yeah, gallwn unig fath o mynd yn ôl dros yno, dde? Ac yna linell drwy'r 50, neu jyst ysgrifennu drosti gyda 171. Ac os ydych yn meddwl pam ein niferoedd got mor hap, mae'r rhain yn cael eu cymryd gan gyfrifiadur yn gyffredin cyrsiau gwyddoniaeth yn Harvard ar ôl CS50. Ond yr oedd hynny'n Optimization da, oherwydd erbyn hyn dydw i ddim yn gwastraffu gofod. Rhaid i mi gofio pa mor fawr beth mae hyn yn gyfanswm. Mae'n bum cyfanswm. Oherwydd nad wyf am dechrau trosysgrifo 51. Felly, yn awr yr wyf yn dal allan o le, felly yr un broblem ag o'r blaen. Ond gallwch weld pa mor nawr yn eich cod, mae'n debyg rhaid i ysgrifennu ychydig mwy cymhlethdod i wneud i hynny ddigwydd. Ac yn wir, pa weithredwr yn ôl pob tebyg yn gadael i C rydych hudol yn gwneud hyn mae'r cylchogrwydd? Yeah gweithredwr modulo, yr arwydd y cant. Felly, beth sydd fath o cŵl am ciw, er ein bod yn cadw tynnu araeau gan fod y rhain llinellau tebyg syth, os ydych yn math o feddwl am hyn fel crwm o gwmpas fel cylch, yna dim ond reddfol mae'n fath o yn gweithio'n feddyliol Yr wyf yn meddwl ychydig yn fwy lân. Byddai'n rhaid i chi dal i weithredu model hwnnw meddwl mewn cod. Fel nad yw yn galed, yn y pen draw, i weithredu, ond yr ydym yn dal i golli yr size-- hytrach, mae'r y gallu i newid maint, oni bai ein bod yn gwneud hyn. 

Mae'n rhaid i ni gael gwared ar y array, rydym yn ddisodli gydag pwyntydd sengl, ac yna rhywle yn fy cod gen a galw yr hyn swyddogaeth i greu mewn gwirionedd yr amrywiaeth o'r enw rhifau? Malloc, neu ryw tebyg swyddogaeth, yn union. Unrhyw gwestiynau am staciau neu ciwiau. Yeah? Cwestiwn da. Pa modulo fyddech chi'n ei ddefnyddio yma. Felly ar y cyfan, wrth ddefnyddio mod, byddech yn ei wneud gyda maint y strwythur data cyfan. Felly rhywbeth fel pump neu alluedd, os mae'n gyson, yn ôl pob tebyg yn cymryd rhan. Ond dim ond gwneud modulo pump yn ôl pob tebyg yn ddigonol, oherwydd mae angen i ni wybod a ydym cofleidiol yma neu yma neu yma. Felly, mae'n debyg eich bod hefyd mynd i eisiau cynnwys maint y peth, neu y newidyn blaen hefyd. Felly dim ond mae hyn yn gymharol mynegiant rhifyddeg syml, ond byddai modulo yn y cynhwysyn allweddol. 

Ffilm mor fyr os mynnwch. Animeiddiad bod rhai Folks mewn prifysgol arall rhoi at ei gilydd yr ydym wedi haddasu ar gyfer y drafodaeth hon. Mae'n cynnwys Jack dysgu'r ffeithiau am giwiau ac ystadegau. 

FFILM: Un tro, roedd dyn o'r enw Jack. Pan ddaeth i wneud ffrindiau, Nid oedd gan Jack ddawn. Felly aeth Jack i siarad â'r mwyaf poblogaidd guy ei fod yn gwybod. Aeth i Lou a gofyn, Beth ddylwn i ei wneud? Gwelodd Lou fod ei gyfaill Roedd yn ofidus. Wel, dechreuodd, dim ond edrych sut yr ydych yn gwisgo. Peidiwch â gennych unrhyw ddillad gyda golwg wahanol? Ie, meddai Jack. Yr wyf yn siŵr yn ei wneud. Dewch i fy nhŷ a 'N annhymerus' yn eu dangos i chi. Felly hwy a aethant i ffwrdd i Jac. A Jack Dangosodd Lou y blwch lle y cadwai ei holl crysau, ac mae ei pants, a'i sanau. Dywedodd Lou, yr wyf yn gweld eich bod wedi eich holl ddillad mewn pentwr. Pam na wnewch chi wisgo rhai eraill unwaith mewn dro? 

Meddai Jack, yn dda, pan oeddwn cael gwared ar ddillad a sanau, Yr wyf yn eu golchi ac yn rhoi nhw i ffwrdd yn y blwch. Yna daw'r nesaf bore, ac i fyny yr wyf yn hop. Rwy'n mynd i'r blwch a chael fy nillad oddi ar y top. Lou gwireddu yn gyflym y broblem gyda Jack. Cadwodd dillad, cryno ddisgiau, a llyfrau yn y pentwr. Pan fydd yn cyrraedd ar gyfer rhywbeth i'w ddarllen neu i'w wisgo, byddai'n dewis y llyfr uchaf neu isaf. Yna, pan gafodd ei wneud, efe a Byddai ei gywiro yn ôl. Yn ôl y byddai'n mynd, ar ben y pentwr. Yr wyf yn gwybod yr ateb, dywedodd Loud buddugoliaethus. Mae angen i chi ddysgu sut i dechrau defnyddio ciw. Cymerodd Lou dillad Jac a eu hongian yn y cwpwrdd. Ac wedi iddo wagio y bocs, e jyst taflu ef. 

Yna dywedodd, yn awr Jack, ar ddiwedd y y dydd, rhowch eich dillad ar y chwith pan fyddwch yn eu rhoi i ffwrdd. Yna, bore fory pan fyddwch yn gweld yr haul, yn cael eich dillad ar y dde, o ddiwedd y llinell. Peidiwch â chi'n ei weld? Dywedodd Lou. Bydd yn mor braf. Byddwch yn gwisgo popeth unwaith cyn i chi wisgo rhywbeth ddwywaith. A gyda phopeth mewn ciwiau yn ei closet a silff, Dechreuodd Jack i deimlo'n hollol sicr o ei hun. Pob diolch i Lou a ei ciw gwych. SIARADWR 1: pob hawl, mae'n annwyl. Felly, beth sydd wedi bod yn mynd yn wirioneddol ar dan y cwfl yn awr? Bod gennym awgrymiadau, bod gennym malloc, bod gennym y gallu i greu darnau o gof i ni ein hunain ddynamig. Felly, mae hwn yn ddarlun i ni cipolwg dim ond y diwrnod o'r blaen. Doedden ni ddim yn trigo arno, ond y llun yma Mae bod yn mynd ymlaen o dan y cwfl am wythnosau nawr. Ac felly mae hyn yn cynrychioli, dim ond petryal yr ydym wedi tynnu, cof eich cyfrifiadur. Ac efallai eich cyfrifiadur, neu CS50 ID, mae gan gigabyte o gof neu RAM neu ddau gigabeit neu bedwar. Nid oes llawer o bwys. Eich system weithredu Windows neu Mac OS neu Linux, ei hanfod yn caniatáu eich rhaglen i feddwl bod ganddi fynediad at holl cof eich cyfrifiadur, hyd yn oed er efallai y byddwch yn rhedeg lluosog raglenni ar unwaith. Felly, mewn gwirionedd, nid yw hynny'n wir yn gweithio. Ond mae'n fath o rhith a roddir i bob un o'ch rhaglenni. Felly, os ydych wedi cael dau gigs o RAM, mae hyn yn yw sut y gallai'r cyfrifiadur yn meddwl amdano. 

Nawr gyd-ddigwyddiad, un o'r rhain pethau, un o'r segmentau hyn o gof, yn cael ei alw'n pentwr. Ac yn wir unrhyw adeg hyd yn hyn mewn cod ysgrifen eich bod wedi galw yn swyddogaeth, er enghraifft brif. Dwyn i gof bod unrhyw bryd rwyf wedi cof cyfrifiadurol a dynnwyd yn, Rwyf bob amser yn tynnu fath o hanner petryal yma ac nid ydynt yn trafferthu siarad ynglŷn â'r hyn sydd uchod. Oherwydd pan fydd prif gelwir, i hawlio eich bod yn cael sliver hwn o gof sy'n mynd i lawr fan hyn. Ac os brif elwir yn swyddogaeth fel cyfnewid, yn dda cyfnewid yn mynd yma. Ac mae'n troi allan, dyna ble mae'n dod i ben i fyny. Ar rywbeth a elwir pentwr tu mewn cof eich cyfrifiadur. Nawr ar ddiwedd y dydd, mae hyn yn unig yn mynd i'r afael. Mae fel beit sero, beit un, beit 2000000000. Ond os ydych yn meddwl am y peth gan fod hyn yn gwrthrych petryal, cyfan yr ydym yn ei wneud pob amser yr ydym yn galw swyddogaeth yw haenu tafell newydd o gof. Rydym yn rhoi cyfran swyddogaeth honno o'i gof ei hun i weithio gyda nhw. 

A dwyn i gof yn awr bod hyn yn bwysig. Oherwydd os ydym yn cael rhywbeth fel cyfnewid a dau newidyn lleol fel A a B a ni newid gwerthoedd hynny o un a dau i ddau ac un, galw i gof pan cyfnewid yn dychwelyd, 'i' fel pe bai sleisen hwn o gof wedi mynd yn unig. Mewn gwirionedd, mae'n dal i fod yno fforensig. A rhywbeth o hyd mewn gwirionedd yno. Ond yn gysyniadol, mae fel er ei fod wedi mynd yn llwyr. Ac felly nid prif yn gwybod unrhyw ran o'r gwaith a gafodd ei wneud yn y swyddogaeth cyfnewid, oni bai ei fod yn mynd heibio mewn gwirionedd yn y rhai dadleuon drwy pwyntydd neu drwy gyfeirio. Yn awr, yr ateb sylfaenol i'r broblem honno gyda cyfnewid yn mynd heibio pethau yn ôl cyfeiriad. Ond mae'n troi allan, hefyd, beth sydd bod yn mynd ymlaen uwchben y rhan honno y petryal i gyd y tro hwn yw ond eto mae mwy o gof i fyny yno. A phan fyddwch yn ddynamig dyrannu cof, boed y tu mewn o GetString, a oedd yn rydym wedi bod yn ei wneud ar eich cyfer yn y CS50 llyfrgell, neu os ydych guys ffoniwch malloc a gofyn y system weithredu ar gyfer darn o cof, nid yw'n dod o'r simnai. Mae'n dod o le arall er cof am eich cyfrifiadur sy'n cael ei alw y domen. Ac nid dyna'r unrhyw wahanol. Mae yr un RAM. Mae yr un cof. Dim ond y RAM sydd ar i fyny yna yn lle i lawr yma. 

Ac felly beth yw ystyr hynny? Wel, os oes gan eich cyfrifiadur swm cyfyngedig o gof ac y das yn tyfu i fyny, felly i siarad, ac mae'r domen, yn ôl i saeth hwn, yn tyfu i lawr. Mewn geiriau eraill, mae pob tro y byddwch yn galw malloc, eich bod yn cael ei rhoi sleisen o gof oddi uchod, yna efallai ychydig yn is, yna ychydig yn is, bob tro y byddwch yn galw malloc, y domen, 'i' defnydd, yn fath o dyfu, tyfu yn nes ac yn nes at yr hyn? Mae'r stac. Felly, mae hyn yn ymddangos yn syniad da? Yr wyf yn golygu, lle nad yw'n wir glir beth arall y gallwch ei wneud os ydych yn unig fod â swm cyfyngedig o gof. Ond mae hyn yn sicr yn ddrwg. Mae'r ddau saethau bod ar damwain cwrs am ei gilydd. 

Ac mae'n troi allan y dyn drwg, Folks sy'n yn arbennig o dda gyda rhaglennu, ac yn ceisio hacio i mewn cyfrifiaduron, Gall fanteisio realiti hwn. Yn wir, gadewch i ni ystyried ychydig o snippet. Felly, mae hyn yn enghraifft gallwch ddarllen am yn fanylach ar Wikipedia. Byddwn yn eich cyfeirio at y erthygl os chwilfrydig. Ond mae ymosodiad yn gyffredinol a elwir yn gorlif byffer sy'n wedi bodoli cyhyd ag y bodau dynol wedi cael y gallu i drin gof cyfrifiadur, yn enwedig yn C. Felly, mae hon yn rhaglen mympwyol iawn, ond gadewch i ni ei ddarllen o'r gwaelod i fyny. Main mewn i seren argC torgoch argV. Felly mae'n rhaglen sy'n cymryd dadleuon llinell orchymyn. A'r holl brif yn ôl pob golwg yn galw swyddogaeth, ei alw'n F am symlrwydd. Ac mae'n mynd yn yr hyn? ArgV o un. Felly mae'n mynd i mewn beth bynnag F y gair yw bod y defnyddiwr yn teipio wrth yr anogwr ar ôl y Enw'r rhaglen o gwbl. Mae cymaint fel Cesar neu Vigenere, a oedd yn efallai y byddwch yn cofio ei wneud gyda argV. 

Felly beth yw F? F yn cymryd mewn llinyn fel ei unig ddadl, AKA yn seren torgoch, yr un beth, fel llinyn. Ac fe'i gelwir fympwyol bar yn yr enghraifft hon. Ac yna torgoch c 12, dim ond mewn termau lleyg, beth yw torgoch c braced 12 wneud i ni? Beth sy'n ei wneud? Dyrannu cof, yn benodol 12 bytes am 12 chars. Yn union. Ac yna y llinell olaf, droi a copi, nad ydych yn ôl pob tebyg wedi ei weld. Dyma gopi llinyn swyddogaeth y mae ei bwrpas mewn bywyd yw i gopïo ei ail ddadl yn ei ddadl gyntaf, ond dim ond hyd at nifer penodol o bytes. Felly mae'r drydedd ddadl yn dweud, faint o bytes ddylech chi gopïo? Mae hyd y bar, beth bynnag y defnyddiwr deipio i mewn. A chynnwys bar, hynny llinyn, yn copïo i mewn i'r cof sylw at ym C. 

Felly, mae hyn yn ymddangos yn fath o dwp, ac y mae. Mae'n enghraifft contrived, ond mae'n gynrychioliadol o ddosbarth fectorau ymosodiad, ffordd o ymosod rhaglen. Mae pob yn iawn ac yn dda os bydd y defnyddiwr mathau mewn gair dyna 11 o gymeriadau neu lai, yn ogystal â'r slaes sero. Beth os bydd y mathau defnyddwyr mewn mwy na 11 neu 12 neu 20 neu 50 cymeriadau? Beth yw rhaglen hon yn mynd i wneud? Fai a allai fod yn SEG. Mae'n mynd i blindly gopïo popeth ym mar fyny at ei hyd, sydd yn llythrennol popeth yn bar, i mewn i'r cyfeiriad bwyntio at C. Ond C dim ond preemptively roi fel 12 bytes. Ond does dim gwiriad ychwanegol. Does dim os bydd amodau. Does dim gwall gwirio yma. 

Ac felly yr hyn y mae'r rhaglen hon yn mynd i'w wneud yn unig blindly copïo un peth i'r llall. Ac felly os ydym yn tynnu hyn fel llun, dyma dim ond sliver o'r lle cof. Felly, yn sylwi ar y gwaelod, rydym yn yn cael y bar newidyn lleol. Er mwyn i pwyntydd hynny'n mynd i store-- yn hytrach y ddadl lleol sy'n mynd i storio'r bar llinyn. Ac yna yn sylwi yn unig uwch ei ben mewn pentwr, oherwydd bob tro y byddwch yn gofyn ar gyfer cof ar y corn, mae'n mynd ychydig bach uwch ei ben ar ffurf lluniau, rhybudd bod gennym 12 o bytes yno. Yr un chwith uchaf yw C braced sero a yr un cywir waelod yw C braced 11. Dyna sut y cyfrifiaduron mynd i osod allan. Felly dim ond reddfol, os oes bar wedi mwy na 12 cymeriadau i gyd, gan gynnwys y slaes sero, ble mae'r 12 neu y braced C 12 mynd i fynd? Neu yn hytrach ble mae'r 12fed cymeriad neu gymeriad 13eg, cymeriad canfed mynd i roi diwedd ar i fyny yn y llun? Yn uwch neu'n is? 

Iawn, oherwydd hyd yn oed er y pentwr ei hun yn tyfu i fyny, unwaith y byddwch wedi rhoi pethau yn y peth, am resymau dylunio, rhoi'r cof o'r top i'r gwaelod. Felly, os oes gennych fwy na 12 bytes, ydych yn mynd i ddechrau ysgrifennu dros y bar. Nawr bod 'na nam, ond mae'n ddim wir yn beth mawr. Ond mae'n beth mawr, oherwydd mae mwy o bethau yn mynd ymlaen yn y cof. Felly dyma sut gallem rhoi helo, i fod yn glir. Os byddaf yn teipio yn helo wrth yr anogwr. Slaes sero H-E-L-L-O, yn dod i ben i fyny o fewn y rhai 12 bytes, ac rydym yn super ddiogel. Popeth yn iawn. Ond os wyf yn teipio rhywbeth yn hwy, o bosibl ei fod yn mynd i ymlusgo i'r gofod bar. Ond yn waeth hyd yn hyn, mae'n troi allan yr holl amser hwn, hyd yn oed er nad ydym wedi siarad am iddo, y das yn cael ei ddefnyddio ar gyfer pethau eraill. Nid dim ond newidynnau lleol. 

C yn iaith lefel isel iawn. Ac mae'n fath o gyfrinachol defnyddio'r corn hefyd i'w cofio pan fydd Gelwir swyddogaeth yn cael, beth y cyfeiriad yn y swyddogaeth blaenorol, fel y gall neidio yn ôl at y swyddogaeth honno. Felly, pan fydd prif alwadau cyfnewid, ymhlith y pethau gwthio ar y pentwr nid yn unig yn cyfnewid newidynnau lleol, neu ei ddadleuon, hefyd gwthio yn gyfrinachol ar y pentwr a gynrychiolir gan y dafell coch yma, yw cyfeiriad brif gorfforol er cof am eich cyfrifiadur, felly pan cyfnewid yn cael ei wneud, y cyfrifiadur yn gwybod yn rhaid i mi fynd yn ôl at brif a gorffen gweithredu'r prif swyddogaeth. Felly, mae hyn yn beryglus yn awr, oherwydd os y mathau defnyddiwr yn dda yn fwy na helo, fel bod mewnbwn y defnyddiwr yn clobbers neu overwrites adran honno coch, rhesymegol os bydd y cyfrifiadur jyst yn mynd i gymryd yn ganiataol 'n ddall bod y bytes yn y sleisen coch yn y cyfeiriad y dylid ei ddychwelyd, beth os yw'r gwrthwynebwr yn ddigon smart neu ddigon ffodus i roi dilyniant o bytes yna sy'n edrych fel cyfeiriad, ond mae'n y cyfeiriad cod ei fod ef neu hi am y cyfrifiadur i weithredu yn lle prif? 

Mewn geiriau eraill, os yw'r hyn y defnyddiwr yn teipio wrth yr anogwr, Nid yn unig yw rhywbeth fel diniwed helo, ond mewn gwirionedd cod sy'n cyfateb i ddileu'r holl ffeiliau defnyddwyr hwn? Neu e-bostio eu cyfrinair i mi? Neu ddechrau cofnodi eu keystrokes, dde? Mae ffordd, gadewch i ni nodi heddiw, y gallent deipio i mewn nid yn unig helo byd neu eu henw, gallent ei hanfod pasio mewn cod, zeros a rhai, bod y cyfrifiadur camgymeriadau ar gyfer y ddau cod a chyfeiriad. Felly, er bod hynny braidd yn haniaethol, os bydd y mathau o ddefnyddwyr yn ddigon cod gwrthwynebus y byddwn yn cyffredinoli yma fel A. A yn ymosodiad neu gwrthwynebwyr. Pethau felly dim ond drwg. Nid ydym yn poeni am y rhifau neu y sero neu rai heddiw, fel y byddwch yn trosysgrifo yr adran honno coch, sylwi bod dilyniant o bytes. O 835 C sero wyth sero. Ac yn awr fel erthygl Wicipedia yma wedi cynnig, os ydych yn awr mewn gwirionedd yn dechrau labelu'r bytes yn eich cyfrifiadur cof, yr hyn y mae'r erthygl Wicipedia yw cynnig yw bod, beth os y cyfeiriad o hynny top chwith beit yw 80 C 0 3508. 

Mewn geiriau eraill, os bydd y dyn drwg yn ddigon craff â'i cod i mewn gwirionedd yn rhoi nifer yma y yn cyfateb i gyfeiriad y cod ef neu hi chwistrellu i mewn i'r cyfrifiadur, byddwch yn Gall castia y cyfrifiadur i wneud unrhyw beth. Cael gwared ffeiliau, e-bostio pethau, ffroeni eich traffig, yn llythrennol Gallai unrhyw beth fod yn chwistrellu i mewn i'r cyfrifiadur. Ac felly gorlif byffer ymosodiad yn greiddiol yn unig yw dwp, dwp gor-redol amrywiaeth sy'n Nid oedd gan wirio ei ffiniau. Ac mae hyn yn beth yw super beryglus ac ar yr un pryd super pwerus yn C yw ein bod yn wir oes gennym mynediad i unrhyw le yn y cof. Mae i fyny i ni, y rhaglenwyr, sy'n ysgrifennu y cod gwreiddiol i wirio hyd darn o unrhyw araeau yr ydym yn trin. Felly, er mwyn bod yn glir, beth yw'r atgyweiria? Os byddwn gofrestr yn ôl at hyn cod, nid wyf ddylai unig newid hyd bar, beth arall ddylwn i fod yn gwirio? Beth arall ddylwn i fod yn ei wneud i atal yr ymosodiad hwn yn gyfan gwbl? Nid wyf am i ddim ond blindly dweud y dylech gopïo cynifer o bytes fel y mae hyd y bar. Rwyf am ei ddweud, copïo fel mae llawer o bytes fel y mae ym mar i fyny at y ddyrannwyd cof, neu 12 maximally. Felly, mae angen i mi rhyw fath o os yw cyflwr sy'n gwneud gwiriwch hyd y bar, ond os yw'n fwy na 12, yr ydym cod unig caled 12 gan fod y pellter mwyaf posibl. Fel arall y byffer hyn a elwir yn Gall trawiad ar y gorlif ddigwydd. Ar waelod y sleidiau hynny, os ydych yn chwilfrydig i ddarllen mwy yw'r erthygl gwreiddiol gwirioneddol os hoffech i gymryd golwg. 

Ond yn awr, ymhlith y prisiau dalu yma oedd aneffeithlonrwydd. Felly yr oedd hynny'n gyflym edrych lefel isel ar yr hyn gall problemau godi yn awr ein bod yn yn cael mynediad i gof cyfrifiadur. Ond broblem arall yr ydym yn eisoes yn stumbled ar ddydd Llun yn unig oedd yr aneffeithlonrwydd o restr cysylltiedig. Rydym yn ôl i amser llinol. Nid ydym bellach yn cael amrywiaeth cyffiniol. Nid oes gennym fynediad hap. Ni allwn ddefnyddio nodiant braced sgwâr. Mae'n rhaid i ni llythrennol i ddefnyddio dolen tra fel yr un ysgrifennais eiliad yn ôl. Ond ar ddydd Llun, yr ydym yn honni y gallwn ymlusgo yn ôl i mewn i'r deyrnas o effeithlonrwydd cyflawni rhywbeth sy'n logarithmig efallai, neu gorau hyd yn hyn, efallai hyd yn oed rhywbeth sy'n hyn a elwir yn amser cyson. Felly, sut y gallwn wneud hynny drwy ddefnyddio'r rhain newydd offer, cyfeiriadau hyn, awgrymiadau hyn, ac edafu pethau ein hunain? Wel, mae'n debyg bod yma, mae'r rhain yn griw o rifau yr ydym am i storio mewn strwythur data a chwilio yn effeithlon. Gallwn gwbl ailddirwyn i wythnos dau, taflu rhain i amrywiaeth, a chwilio eu defnyddio chwiliad deuaidd. Rhannwch a gorchfygu. Ac yn wir i chi ysgrifennu chwilio deuaidd yn PSET3, lle rydych yn rhoi ar waith y rhaglen darganfyddiad. Ond eich bod yn gwybod beth. Mae fath o mwy ffordd glyfar o wneud hyn. Mae'n ychydig yn fwy soffistigedig ac mae'n bosibl yn ein galluogi i weld pam deuaidd chwilio mor llawer cyflymach. Yn gyntaf, gadewch i ni gyflwyno y syniad o goeden. Pa er bod yn coed realiti fath o tyfu fel hyn, ym myd y cyfrifiadur gwyddoniaeth maent yn fath o yn tyfu i lawr fel coeden deulu, lle mae gennych eich teidiau a neiniau neu deidiau a neiniau mawr neu whatnot ar y brig, y patriarch a y matriarch y teulu, un yn unig hyn a elwir yn gwraidd, nod, isod sydd yn ei blant, isod sy'n yw ei blant, neu ei ddisgynyddion yn fwy cyffredinol. Ac unrhyw un yn hongian oddi ar waelod y teulu coed, yn ogystal â bod y ieuengaf yn y teulu, Gall hefyd jyst yn gyffredinol Gelwir ddail y goeden. 

Felly, mae hyn yn unig yw criw o eiriau a diffiniadau am rywbeth o'r enw coeden mewn cyfrifiadur gwyddoniaeth, yn debyg iawn i coeden deulu. Ond mae ymgnawdoliadau ffansi o goed, un ohonynt gelwir coeden chwiliad deuaidd. Ac gallwch fath o hudo ar wahân yr hyn y peth hyn yn ei wneud. Wel, mae'n deuaidd yn mha ystyr? O ble mae'r deuaidd yn dod o fan hyn? Mae'n ddrwg gennym? Nid yw'n gymaint yn naill neu'r llall neu'r. Mae'n fwy bod pob un o'r nodau Nid oes mwy na dau o blant, wrth i ni weld yma. Yn gyffredinol, mae tree-- a eich rhieni a neiniau a theidiau gall gael cymaint o blant neu grandkids fel y maent mewn gwirionedd yn eisiau, ac felly, er enghraifft, mae gennym dri plant oddi ar y nod llaw dde, ond mewn coeden binary, mae nod wedi sero, un, neu ddau o blant maximally. A dyna eiddo 'n glws, oherwydd os caiff ei gapio gan ddau, rydym yn mynd i fod yn gallu cael sylfaen log bach dau camau gweithredu yn digwydd yma yn y pen draw. Felly mae gennym rywbeth logarithmig. Ond yn fwy am hynny yn y man. Chwilio coed yn golygu bod y niferoedd yn trefnu fel bod y plentyn chwith yn gwerth yn fwy na'r gwraidd. Ac mae ei plentyn cywir yn fwy na'r gwraidd. Mewn geiriau eraill, os ydych yn cymryd unrhyw un o'r nodau, y cylchoedd yn y llun, ac yn edrych ar ei ochr chwith plentyn a'i phlentyn yn iawn, dylai'r cyntaf fod yn llai na, dylai'r ail fod yn fwy na. Felly sanity yn gwirio 55. Mae wedi gadael plentyn yn 33. Mae'n llai na. 55, ei blentyn iawn yn 77. Mae'n fwy na. A dyna diffiniad ailadroddus. Gallem wirio pob un o'r rhai a nodau ac mae'r un patrwm a fyddai'n dal. 

Felly beth braf mewn coeden chwilio deuaidd, yn bod un, gallwn roi ar waith gyda struct, yn union fel hyn. A hyd yn oed er ein bod ni'n taflu llawer o strwythurau yn eich, eu bod braidd yn sythweledol yn awr, gobeithio. Mae'r gystrawen yn dal i fod yn ddirgel yn sicr, ond mae'r cynnwys y nod yn hyn context-- ac rydym yn cadw defnyddio'r gair nôd, boed yn petryal ar y sgrin neu gylch, 'i' dim ond rhai cynhwysydd generig, yn yr achos hwn o goeden, fel yr un welsom, mae angen yn gyfanrif ym mhob un o'r nodau ac yna mae angen pwyntio dau awgrymiadau yr wyf yn i'r plentyn chwith a'r plentyn cywir, yn y drefn honno. Felly dyna sut gallem gweithredu hynny mewn struct. A sut y gallwn roi ar waith yn y cod? Wel, gadewch i ni yn gyflym yn edrych ar enghraifft bach hwn. Dyw hi ddim yn ymarferol, ond rwyf wedi copïo a gludo y strwythur hwnnw. Ac os yw fy swyddogaeth i gael deuaidd Gelwir coeden chwiliad yn chwilio, ac mae hyn yn cymryd dwy ddadl, yn gyfanrif N ac pwyntydd i nod, felly pwyntydd i'r goeden neu pwyntydd i wraidd coeden, sut mae mynd ati i chwilio am N? Wel, yn gyntaf, oherwydd fy mod i'n delio â chyfeiriadau, Rydw i'n mynd i wneud gwiriad bwyll. Os hafal coed hafal null, yn N yn y goeden hon ai peidio yn y goeden hon? Ni all fod yn, dde? Os wyf heibio null, does dim byd yno. Wyf yn gallai yn ogystal yn unig blindly dweud dychwelyd ffug. Os byddwch yn rhoi dim byd i mi, yr wyf nid yn sicr yn gallu dod o hyd i unrhyw rif N. Felly beth arall gallai wyf yn gwiriwch yn awr? Rydw i'n mynd i ddweud dda arall os N yn llai na beth bynnag sydd ar y nôd coed fy mod i wedi bod yn rhoi gwerth N. Mewn geiriau eraill, os yw'r rhif dwi'n chwilio am, N, yn llai na 'r nôd mod i'n edrych ar. Ac y nôd dwi'n edrych yn cael ei alw'n coed, ac yn cofio o'r enghraifft flaenorol i fynd ar werth mewn pwyntydd, Rwy'n defnyddio'r nodiant saeth. Felly os N yn llai na saeth coed E, yr wyf eisiau mynd chwith gysyniadol. Sut ydw i'n mynegi chwilio ar ôl? I fod yn glir, os yw hyn yn y darlun o dan sylw, ac rwyf wedi bod yn pasio bod topmost arrow sy'n pwyntio i lawr. Dyna fy pwyntydd coed. Im 'yn pwyntio at wraidd y goeden. A dwi'n chwilio dyweder, am rhif 44, fympwyol. A yw 44 yn llai na neu'n fwy na 55 amlwg? Felly mae'n llai na. Ac felly mae hyn os yw cyflwr yn berthnasol. Felly gysyniadol, beth ddylwn i ei eisiau chwilio nesaf os dwi'n chwilio am 44? Yeah? 

Yn union, yr wyf am chwilio'r plentyn chwith, neu'r is-goed chwith y llun. Ac yn wir, gadewch i mi drwy y darlun lawr yma am ddim ond eiliad, gan fod Ni allaf crafu hyn allan. Os byddaf yn dechrau yma yn 55, a Gwn fod y gwerth 44 Rwy'n chwilio am yw y chwith, mae'n fath o fel rhwygo y llyfr ffôn yn hanner neu rhwygo y goeden yn ei hanner. Mae gennyf i ofalu am mwyach yr hanner cyfan y goeden. Ac eto, yn rhyfedd ddigon o ran y strwythur, y peth hyn dros yma bod yn dechrau gyda 33, fod ei hun yn goeden chwiliad deuaidd. Dywedais y gair ailadroddus blaen oherwydd yn wir mae hyn yn strwythur data y trwy ddiffiniad yn ailadroddus. Efallai y bydd gennych goeden dyna hwn mawr, ond mae pob un o'i blant yn cynrychioli coeden dim ond ychydig yn llai. Yn hytrach na ei fod grandpa neu nain, erbyn hyn dim ond mom or-- ni allaf beidio say-- mom neu dad, byddai hynny'n rhyfedd. Yn lle hynny mae'r ddau blentyn yno Byddai bod fel brawd a chwaer. Mae cenhedlaeth newydd o goeden deulu. Ond yn strwythurol, mae'n yr un syniad. Ac mae'n troi allan gen i swyddogaeth Gallaf chwilio chwiliad deuaidd â hwy coeden. Fe'i gelwir chwilio. Rwy'n chwilio am N yng saeth coed y chwith arall os N yn fwy na'r gwerth fy mod ar hyn o bryd. 55 yn y stori funud yn ôl. Mae gen i swyddogaeth o'r enw chwilio sy'n gallaf jyst pasio N hyn a chwilio recursively yr is-goed a dychwelyd yn unig beth bynnag yr ateb hwnnw. Arall gen i achos sylfaenol terfynol yma. 

Beth yw'r achos terfynol? Tree naill ai'n null. Mae gwerth Im 'naill ai yn chwilio amdano yw yn llai nag yr neu'n fwy na hynny neu'n hafal iddo. A gallwn ddweud gyfartal cyfartal, ond yn rhesymegol mae'n sy'n cyfateb i ddim ond dweud arall yma. Felly yn wir yw sut yr wyf yn dod o hyd i rywbeth. Felly gobeithio y mae hyn yn hyd yn oed yn enghraifft fwy cymhellol na'r swyddogaeth sigma dwp gwnaethom ychydig o ddarlithoedd yn ôl, lle'r oedd yr un mor hawdd i'w ddefnyddio dolen i gyfrif hyd holl rifau o un i N. Yma gyda strwythur data fod ei hun yn recursively diffiniedig a thynnu recursively, yn awr rydym y gallu i fynegi ein hunain mewn cod sy'n ei hun yn ailadroddus. Felly, mae hyn yn yr un cod union fan hyn. 

Felly, pa broblemau eraill y gallwn ddatrys? Felly cam cyflym i ffwrdd oddi wrth coed am ddim ond ennyd. Yma yw, yn dweud, mae'r faner yr Almaen. Ac mae yn amlwg yn patrwm i dynnu sylw hwn. Ac mae llawer o baneri yn y byd sydd mor syml â hyn o ran o'u lliwiau a phatrymau. Ond mae'n debyg bod hyn yn cael ei storio fel Gif, neu JPEG, neu bitmap, neu ping, unrhyw fformat ffeil graffigol eich bod yn gyfarwydd â hi, rhai ohonynt rydym yn chwarae gyda mewn PSET4. Nid yw hyn yn ymddangos yn werth chweil i storio picsel du, du picsel, picsel du, dot, dot, dot, criw cyfan o pixels du ar gyfer y scanline cyntaf, neu res, yna criw cyfan o yr un fath, yna criw cyfan o'r un peth, ac yna criw cyfan o picsel coch, picsel coch, picsel coch, yna yn ei gyfanrwydd criw o picsel melyn, melyn, dde? 

Mae aneffeithlonrwydd o'r fath yma. Sut byddech chi yn reddfol cywasgu'r faner yr Almaen os weithredu fel ffeil? Fel pa wybodaeth na allwn ni trafferthu storio ar ddisg er mwyn i leihau ein maint y ffeil o hoffi yn megabeit i cilobeit, rhywbeth llai o faint? Yr hon yn gorwedd y diswyddo yma i fod yn glir? Beth allech chi ei wneud? Yeah? Yn union. Pam na wnewch chi yn hytrach na chofio y lliw pob picsel darn yn union fel chi yn ei wneud yn PSET4 gyda'r fformat ffeil didfap, pam na wnewch chi jyst yn cynrychioli'r colofn leftmost o picsel, er enghraifft criw o picsel du, criw o goch, a bagad o melyn, ac yna dim ond rhywsut amgodio y syniad o ailadrodd hwn 100 gwaith neu ailadrodd hyn 1,000 o weithiau? Lle 100 neu 1,000 yn dim ond yn gyfanrif, er mwyn i chi Gall gael i ffwrdd gyda dim ond un rhif yn hytrach na gannoedd neu filoedd picseli o ychwanegol. Ac yn wir, dyna sut yr ydym Gallai cywasgu y faner yr Almaen. A Nawr beth am y faner Ffrengig? Ac ychydig rhyw fath o ymarfer meddyliol, a oedd baner Gellir cywasgu mwy ar ddisg? Mae'r faner Almaeneg neu Ffrangeg baner, os byddwn yn cymryd y dull? Mae'r faner Almaeneg, oherwydd mae mwy diswyddo llorweddol. A thrwy dylunio, mae llawer o ffeiliau graffigol fformatau ddim wir yn gweithio llinellau fel sgan yn llorweddol. Gallent weithio fertigol, dim ond dynoliaeth flynyddoedd yn ôl, penderfynodd yr ydym chi helpu Yn gyffredinol, yn meddwl am bethau rhes trwy res yn lle golofn drwy golofn. Felly yn wir, os oeddech yn i edrych ar y ffeil maint y faner Almaeneg a Ffrangeg baner, ar yr amod bod y penderfyniad yn yr un fath, yr un lled ac uchder, yr un yma yma yn mynd i fod yn fwy, oherwydd eich bod rhaid ailadrodd eich hun dair gwaith. Rhaid i chi nodi glas, dro ar ôl tro chi eich hun, gwyn, ailadrodd eich hun, coch, ailadrodd eich hun. Ni allwch jyst yn mynd i gyd y ffordd i'r dde. Ac wrth fynd heibio, er mwyn gwneud clirio'r cywasgu ym mhobman, os yw'r rhain yn pedwar fframiau o video-- chi Efallai cofio i ffilm neu fideo yn gyffredinol fel 29 neu 30 fframiau yr eiliad. Mae fel llyfr fflip bach lle rydych yn ond yn gweld llun, delwedd, delwedd, delwedd, image dim ond super gyflym felly mae'n edrych yn debyg mae'r actorion ar y sgrin yn symud. Dyma wenynen ar ben tusw o flodau. Ac er y gallai fod yn fath o anodd gweld ar yr olwg gyntaf, yr unig beth sy'n symud yn y ffilm hon yw'r gwenyn. 

Yr hyn sy'n fud am storio 'n fideo heb ei gywasgu? Mae'n fath o wastraff i storio fideo â phedwar delweddau bron yn union yr un fath a yn wahanol dim ond i'r graddau lle mae'r gwenyn yn. Gallwch daflu y rhan fwyaf o o'r wybodaeth honno a chofiwch yn unig, er enghraifft, y ffrâm cyntaf a'r ffrâm olaf, fframiau allweddol os ydych chi wedi erioed wedi clywed y gair, a dim ond storio yn y canol lle mae'r gwenyn yn. A does dim rhaid i chi storio'r holl pinc, a'r glas, a'r gwerthoedd gwyrdd hefyd. Felly, mae hyn yw dim ond dweud bod cywasgu ym mhobman. Mae'n dechneg rydym yn aml yn defnyddio neu eu cymryd yn ganiataol y dyddiau hyn. 

Ond sut ydych chi'n cywasgu testun? Sut ydych chi'n mynd ati i gywasgu testun? Wel, pob un o'r cymeriadau yn ASCII yn un beit, neu wyth did. A dyna fath o fud, dde? Oherwydd eich bod yn ôl pob tebyg deipio A ac E ac I ac O ac U llawer yn amlach na fel W neu Q neu Z, yn dibynnu ar yr iaith y eich bod yn ysgrifennu yn sicr. Ac felly pam yr ydym yn defnyddio wyth did ar gyfer pob llythyren, gan gynnwys y lleiaf llythyrau poblogaidd, dde? Beth am ddefnyddio llai o ddarnau ar gyfer y llythrennau super poblogaidd, fel E, y pethau yr ydych yn dyfalu gyntaf yng Olwyn Ffawd, ac yn defnyddio mwy o ddarnau ar gyfer y llythrennau llai poblogaidd? Pam? Oherwydd ein bod yn jyst yn mynd i yn eu defnyddio yn llai aml. 

Wel, mae'n troi allan bod wedi ymdrechion i wneud hyn wedi bod. Ac os ydych yn cofio o radd ysgol neu ysgol uwchradd, cod Morse. Mae Cod Morse dotiau a llinellau toriad a all fod yn drosglwyddir ar hyd gwifren fel synau neu signalau o ryw fath. Ond cod Morse yn super glân. Mae'n fath o system deuaidd mewn bod gennych dotiau neu llinellau toriad. Ond os ydych yn gweld, er enghraifft, dau dotiau. Neu os ydych yn meddwl yn ôl at y gweithredwr sy'n mynd fel Canu, Canu, Canu, Canu, taro ychydig o sbardun sy'n trawsyrru signal, os ydych chi, y derbynnydd, yn derbyn dau dotiau, pa neges yr ydych wedi eu derbyn? Hollol mympwyol. 

I? I? Neu beth about-- neu i? Efallai ei fod yn dim ond dwy hawl E? Felly mae 'na broblem hon o decodability gyda Morse cod, lle oni bai bod y sawl sy'n anfon y neges yr ydych mewn gwirionedd yn seibiau er mwyn i chi drefnu o gweld neu'n clywed y bylchau rhwng llythrennau, nid yw'n ddigon dim ond i anfon ffrwd o zeros a rhai, neu ddotiau a llinellau toriad, oherwydd mae amwysedd. E yn un dot, felly os ydych yn gweld dau dotiau neu glywed dau ddotiau, efallai ei bod yn ddwy E neu efallai ei fod yn un I. Felly mae angen system sy'n 'na ychydig yn fwy clyfar na hynny. Felly dyn o'r enw Huffman flynyddoedd yn ôl feddyliodd am yr union hyn. Felly rydym yn jyst yn mynd i gymryd cipolwg cyflym ar sut y coed yn germane i hyn. Gadewch i ni dybio bod hyn yn rhai Neges dwp ydych chi am anfon, cynnwys dim ond A, B, C D's ac E, ond mae llawer o gael eu diswyddo yma. Dyw hi ddim yn golygu i fod yn Saesneg. Dyw hi ddim yn amgryptio. 'I' jyst neges dwp gyda llawer o ailadrodd. Felly, os ydych mewn gwirionedd yn cyfrif yr holl A, B, C, D, ac E, dyma pa mor aml. 20% o'r llythyrau yn A, 45% o'r llythyrau yn E, a thri amleddau eraill. Rydym yn cyfrif i fyny yno â llaw a dim ond gwnaeth y mathemateg. 

Felly, mae'n ymddangos bod Huffman, beth amser yn ôl, sylweddoli eich bod, yn gwybod beth, os byddaf yn dechrau adeiladu coeden, neu goedwig o goed, os gwnewch, fel a ganlyn, gallaf wneud y canlynol. Rydw i'n mynd i roi nod i bob o'r llythyrau yr wyf yn poeni am ac yr wyf i'n mynd i storio tu mewn y nôd yr amleddau fel pwynt arnawf gwerth, neu gallech ei ddefnyddio yn N, hefyd, ond byddwn yn jyst yn defnyddio fflôt yma. Ac mae'r algorithm sy'n cynigiodd yw eich bod cymryd y goedwig hon o nod sengl coed, coed mor super byr, a'ch bod yn dechrau eu cysylltu â grwpiau newydd, rhieni newydd, os mynnwch. A ydych yn gwneud hyn trwy ddewis y dau amleddau lleiaf ar y tro. Felly yr wyf yn cymryd 10% a 10%. Yr wyf yn creu nod newydd. Ac yr wyf yn galw y nôd newydd o 20%. 

Pa ddau nodau wyf yn cyfuno nesaf? Mae'n ychydig yn amwys. Felly mae yna rhai achosion cornel i ystyried, ond i gadw pethau 'n bert, Rydw i'n mynd i ddewis 20% - Yr wyf yn awr yn anwybyddu'r plant. Rydw i'n mynd i ddewis 20% a 15% a thynnu dau ymylon newydd. Ac yn awr mae dwy nodau ydw i'n cyfuno rhesymegol? Anwybyddwch y plant i gyd, yr holl wyrion, dim ond yn edrych ar y gwreiddiau yn awr. Pa ddau nodau ydw i'n clymu at ei gilydd? Pwynt dau a 0.35. Felly gadewch i mi dynnu dau ymylon newydd. Ac yna yr wyf wedi dim ond got un chwith. Felly dyma coeden. Ac mae wedi cael ei dynnu yn fwriadol i edrych yn fath o 'n bert, ond yn sylwi bod yr ymylon yn cael hefyd wedi cael eu labelu sero ac un. Felly pob un o'r ymylon chwith yn sero fympwyol, ond yn gyson. Mae pob un o'r ymylon cywir yn rhai. 

Ac felly yr hyn a gynigir Hoffman yw, os ydych am i gynrychioli B, yn hytrach na cynrychioli nifer 66 fel mae ASCII sydd yn wyth did cyfan, eich bod yn gwybod beth, storio yn unig patrwm sero, sero, sero, sero, oherwydd dyna y llwybr gan fy goeden, coeden Mr. Huffman yn, i'r ddeilen oddi wrth y gwraidd. Os ydych am storio E, mewn cyferbyniad, peidiwch anfon wyth did sy'n cynrychioli E. Yn lle hynny, anfonwch pa batrwm o ddarnau? Un. A beth sy'n neis am hyn yw bod E yw'r llythyr mwyaf poblogaidd, ac eich bod yn defnyddio'r Cod byrraf ar ei gyfer. Y nesaf mwyaf poblogaidd llythyr edrych fel ei fod Roedd A. Ac felly faint o ddarnau oedd yn cynnig defnyddio ar gyfer hynny? Zero, un. 

Ac oherwydd ei fod yn rhoi ar waith fel goeden hon, am y tro gadewch i mi nodi mae dim amwysedd fel yn Morse cod, gan fod pob un o'r llythyrau ydych yn gofalu am ar ddiwedd y ymylon hyn. Felly dyna dim ond un cymhwyso goeden. Mae hyn yn yw-- a byddaf yn chwifio fy llaw ar hyn o sut yr ydych yn Gallai gweithredu hyn fel strwythur C. Jyst angen i ni gyfuno symbol, fel torgoch, ac amlder yn chwith ac i'r dde. Ond gadewch i ni edrych ar ddau enghreifftiau terfynol eich bod chi helpu gael yn eithaf gyfarwydd â ar ôl cwis sero yn broblem a osodwyd pump. 

Felly mae strwythur y data a elwir yn tabl hash. A thabl hash yn fath o oeri mewn bod ganddo bwcedi. Ac Tybiwch mae pedwar bwcedi yma, dim ond pedwar lle gwag. Dyma dec o gardiau, ac yma yn clwb, rhaw, clwb, diamonds, clybiau, diamonds, clwb, diamonds, clubs-- felly dyma'r hap. Calonnau, hearts-- felly rwy'n bucketizing pob un o'r mewnbynnau yma. A anghenion tabl hash i edrych ar eich mewnbwn, ac yna ei roi mewn rhai gosod yn seiliedig ar yr hyn a welwch. Mae'n algorithm. Ac yr wyf yn defnyddio super algorithm gweledol syml. Y rhan anoddaf o'r rhain oedd cofio beth oedd y lluniau oedd. Ac yna mae pedwar cyfanswm bethau. 

Nawr bod y cyrn yn tyfu, a oedd yn yn beth dylunio bwriadol yma. Ond beth arall a allai i ei wneud? Felly, mewn gwirionedd dyma mae gennym criw o hen lyfrau arholiadau ysgol. Tybiwch fod criw o Enwau myfyrwyr ar yma. Dyma dabl hash mwy. Yn hytrach na bedwar bwcedi, Rwyf wedi, gadewch i ni ddweud 26. Ac nid oeddem eisiau mynd fenthyg 26 pethau o'r tu allan [? Annenberg?], Felly dyma pump sy'n cynrychioli A drwy Z. Ac os wyf yn gweld i fyfyriwr y mae ei enw yn dechrau gyda A, Rydw i'n mynd i roi ei cwis yno. Os bydd rhywun yn dechrau gyda C, dros yno, A-- mewn gwirionedd, nid oedd am wneud hynny. B yn mynd dros yma. Felly mae gen i A a B ac C. A Erbyn hyn dyma myfyriwr A arall. Ond os y tabl hash hwn rhoi ar waith gydag amrywiaeth, Im 'yn fath o sgriwio yn y fan hon, dde? Yr wyf yn fath o angen inni roi hyn yn rhywle. 

Felly, un ffordd y gallaf ddatrys hyn yw, i gyd dde, A yn brysur, B yn brysur, C yn brysur. Dw i'n mynd i roi iddo yn D. Felly, ar yn gyntaf, yr wyf yn cael mynediad ar unwaith ar hap i bob un o'r bwcedi ar gyfer y myfyrwyr. Ond erbyn hyn mae'n fath o ddatganoli i mewn i rywbeth llinol, oherwydd os wyf eisiau chwilio am rywun enw y mae ei dechrau gyda A, yr wyf yn gwirio yma. Ond os nad yw hyn yn A myfyriwr dwi'n chwilio am, Wyf yn fath o yn rhaid i ddechrau wirio y bwcedi, oherwydd yr hyn a wnaeth i mi Roedd fath o llinol ymchwilio i strwythur data. Ffordd dwp o ddweud dim ond yn edrych ar gyfer yr agoriad cyntaf sydd ar gael, a'i roi fel cynllun a B, fel petai, neu gynllun D yn yr achos hwn, mae'r gwerth yn y lleoliad hwnnw yn lle hynny. Mae hyn yn unig, felly os oes gennych got 26 o leoliadau a dim fyfyrwyr gydag enw Q neu Z, neu rywbeth tebyg hynny, o leiaf eich bod yn defnyddio'r gofod. 

Ond rydym eisoes wedi gweld mwy atebion clyfar yma, dde? Beth fyddech chi'n ei wneud yn lle hynny os oes gennych gwrthdrawiad? Os oes dau o bobl yn cael yr enw A, beth fyddai wedi bod yn fwy craff neu'n fwy ateb 'n athrylithgar na dim ond rhoi A pan fo D yn dybiedig i fod? Pam nad ydw i'n jyst yn mynd tu allan [? Annenberg?], fel malloc, nod arall, rhowch ef yma, ac yna ei roi bod i fyfyriwr yma. Felly, yr wyf yn y bôn yn cael rhyw fath o amrywiaeth, neu efallai yn fwy cain gan ein bod yn dechrau gweld rhestr cysylltiedig. 

Ac felly tabl hash yn strwythur a allai edrych yn union fel hyn, ond yn fwy glyfar, byddwch yn rhywbeth a elwir gadwyno ar wahân, lle tabl hash yn syml yw amrywiaeth, pob un y mae ei elfennau na yn rhif, yn rhestr cysylltiedig ei hun. Felly eich bod yn cael mynediad cyflym super penderfynu ble i hash eich gwerth i. Yn debyg iawn gyda'r enghraifft cardiau, Yr wyf yn gwneud penderfyniadau super gyflym. Hearts goes here, diamonds yn mynd yma. Un peth yma, A mynd yma, D goes here, B mynd yma. Felly gyflym super edrych-ups, ac os ydych yn digwydd i redeg i mewn i achos gwrthdrawiadau lle gennych, dau pobl gyda'r un enw, yn dda yna 'ch jyst yn dechrau eu cysylltu â'i gilydd. Ac efallai eich bod yn cadw eu didoli yn nhrefn yr wyddor, efallai nad ydych yn ei wneud. Ond o leiaf yn awr mae gennym y ddynamiaeth. Felly, ar y naill law mae gennym gyflym super amser cyson, a math o amser llinol dan sylw os rhestrau cysylltiedig hyn dechrau cael ychydig yn hir. 

Felly y math hwn o wirion, flynyddoedd jôc geeky yn ôl. Yn y CS50 darnia-a-thon, pan fydd myfyrwyr yn gwirio i mewn, rhyw TF neu CA bob blwyddyn meddwl ei fod yn ddoniol i roi i fyny arwydd fel hyn, lle mae'n jyst yn golygu os bydd eich enw yn dechrau gyda A, mynd y ffordd hon. Os yw'ch enw yn dechrau gyda B, ewch this-- OK, mae'n ddoniol efallai yn ddiweddarach yn y semester. Ond mae un arall ffordd o wneud hyn, hefyd. Dewch yn ôl at hynny. 

Felly mae yna strwythur hwn. Ac mae hyn yn ein olaf strwythur ar gyfer heddiw, sy'n rhywbeth a elwir yn trie. T-R-I-E, sydd, am ryw reswm yn fyr ar gyfer adfer, ond fe'i gelwir trie. Felly mae trie yn ddiddorol arall amalgam o lawer o syniadau hyn. Mae'n goeden, yr ydym wedi gweld o'r blaen. Dyw hi ddim yn goeden chwiliad deuaidd. Mae'n goeden gydag unrhyw nifer o blant, ond mae pob un o'r plant mewn trie yn arae. Amrywiaeth o faint, yn dweud, 26 neu efallai 27 os ydych chi eisiau cefnogi enwau chysylltnod neu collnod mewn enwau pobl. 

Ac felly mae hwn yn strwythur data. Ac os ydych yn edrych o'r top i'r gwaelod, fel os ydych yn edrych ar y nod uchaf yno, M, yn gan dynnu sylw at y peth leftmost yno, sy'n cael ei wedyn yn A, X, C, E, L, L. Mae hyn yn dim ond strwythur data sy'n fympwyol yn storio enwau pobl. A Maxwell yn cael ei storio gan dim ond dilyn llwybr o amrywiaeth i amrywiaeth i amrywiaeth. Ond yr hyn sy'n rhyfeddol am trie yn hynny, tra rhestr cysylltiedig a hyd yn oed amrywiaeth, y gorau yr ydym wedi gotten erioed yw amser llinol neu amser logarithmig chwilio rhywun i fyny. Yn y strwythur data o trie, os fy strwythur data wedi un enw ynddo ac dwi'n chwilio am Maxwell, rwy'n mynd i ddod o hyd iddo yn weddol gyflym. Fi jyst yn edrych am M-A-X-W-E-L-L. Os y strwythur data, mewn cyferbyniad, os N yw miliwn, os oes miliwn o enwau yn y strwythur data, Maxwell yn dal i fynd i fod yn discoverable ar ôl dim ond M-A-X-W-E-L-L grisiau. A grisiau David-- D-A-V-I-D. Mewn geiriau eraill, trwy adeiladu strwythur data sy'n cael yr holl o'r araeau hyn, pob un ohonynt eu hunain yn cefnogi mynediad ar hap, Gallaf ddechrau edrych i fyny pobl enwi gan ddefnyddio swm o amser sy'n gyfrannol i nad yw'r nifer o bethau yn y strwythur data, fel miliwn o enwau presennol. Mae faint o amser mae'n ei gymryd i mi i ddod o hyd M-A-X-W-E-L-L yn y strwythur data hwn yn gyfrannol nid i'r maint y strwythur data, ond i hyd yr enw. Ac yn realistig y Enwau rydym yn edrych i fyny byth yn mynd i fod yn wallgof hir. Efallai rywun gymeriad 10 enw, 20 enw cymeriad. Mae'n sicr yn gyfyngedig, dde? Mae gan bobl ar y Ddaear sydd Mae gan yr enw hiraf posibl, ond yr enw hwnnw yn gysonyn Hyd gwerth, dde? Nid yw'n amrywio mewn unrhyw ystyr. Felly, yn y modd hwn, rydym wedi cyflawni strwythur data hynny yw amser yn gyson am-edrych. Mae'n gwneud cymryd nifer o gamau yn dibynnu ar hyd y mewnbwn, ond nid y nifer o enw yn y strwythur data. Felly, os ydym yn dyblu nifer y henwau y flwyddyn nesaf o biliwn i ddau biliwn, canfyddiad Maxwell yn mynd i gymryd yr un nifer yn union o saith cam i ddod o hyd iddo. Ac felly rydym yn ymddangos i wedi cyflawni ein greal sanctaidd o redeg amser. 

Felly, un neu ddau o gyhoeddiadau gyflym. Cwis sero yn dod i fyny. Mwy am hynny ar wefan y cwrs yn dros yr ychydig ddyddiau nesaf. Dydd Llun lecture-- ei fod yn wyliau yma yn Harvard ddydd Llun. Dyw hi ddim yn yn New Haven, felly rydym yn cymryd y dosbarth i New Haven ar gyfer darlith ar ddydd Llun. Bydd popeth yn cael ei ffilmio a ffrydio'n fyw yn ôl yr arfer, ond gadewch i ben heddiw gydag ail clip 30 o'r enw "Thoughts Deep" gan Daven Farnham, a oedd yn Ysbrydolwyd y llynedd erbyn dydd Sadwrn "Thoughts Deep" Night Live gan Jack Handy, a oedd yn Dylai bellach yn gwneud synnwyr. 

FFILM: Ac yn awr, "Deep Meddyliau "gan Daven Farnham. Tabl Hash. 

SIARADWR 1: pob hawl, dyna ni am y tro. Byddwn yn gweld chi yr wythnos nesaf. 

DOUG: I weld ei waith. Felly, gadewch i ni edrych ar hynny ar hyn o bryd. Felly dyma, mae gennym amrywiaeth heb eu didoli. 

IAN: Doug, gallwch chi fynd yn ei flaen a restart hwn am ddim ond un eiliad, os gwelwch yn dda. Mae pob hawl, camerâu yn cael eu rholio, felly gweithredu pryd bynnag y byddwch yn barod, Doug, OK? DOUG: pob hawl, felly yr hyn yr ydym gennym yma yw amrywiaeth heb eu didoli. Ac yr wyf i wedi lliw holl elfennau coch i ddangos ei fod yn, mewn gwirionedd, heb eu didoli. Felly yn cofio bod y peth cyntaf rydym yn ei wneud yw ein didoli hanner chwith y rhesi. Yna rydym yn didoli'r hawl hanner y rhesi. Ac ya-da, ya-da, ya-da, yr ydym yn eu cyfuno gyda'i gilydd. Ac mae gennym amrywiaeth cwbl didoli. Felly dyna sut uno fath yn gweithio. 

IAN: Whoa, Whoa, Whoa, torri, torri, torri, torri. Doug, nad ydych yn gallu dim ond ya-da, ya-da, ya-da, eich ffordd drwy'r fath uno. 

DOUG: Fi jyst yn gwneud. Mae'n iawn. Rydym yn dda i fynd. Gadewch i ni jyst cadw dreigl. Felly beth bynnag, 

IAN: rhaid i chi esbonio mae'n llawnach na hynny. Dyw hynny ddim yn unig yn ddigon. DOUG: Ian, nid ydym yn ei wneud Mae angen i fynd yn ôl i un. Mae'n iawn. Felly beth bynnag, os byddwn yn parhau â merge-- Ian, rydym yn yng nghanol y ffilmio. 

IAN: Yr wyf yn gwybod. Ac ni allwn dim ond ya-da, ya-da, ya-da, trwy'r broses gyfan. Mae'n rhaid i chi egluro sut mae'r ddwy ochr yn cael eu cyfuno gyda'i gilydd. 

DOUG: Ond rydym wedi eisoes esbonio sut mae'r ddau sides-- 

IAN: Yr ydych chi newydd ei ddangos nhw amrywiaeth uno. DOUG: Maent yn gwybod y broses. Maen nhw'n iawn. Rydym wedi mynd dros ei ddeg gwaith. 

IAN: Yr ydych newydd hepgor hawl drosto. Rydym yn mynd yn ôl i un, yr ydych Ni allwch chi ya-da, ya-da drosto. Mae pob hawl, yn ôl i un. 

DOUG: Rhaid i mi fynd yn ôl drwy bob un o'r sleidiau? Fy Nuw. Mae fel yr amser dosbarth, Ian. Mae'n iawn. 

IAN: Pob hawl. Rydych yn barod? Great. Gweithredu.