[CHWARAE CERDDORIAETH] DAVID Malan: Mae hyn yn CS50. Ac mae hyn yn yn y dechrau a'r end-- fel literally-- bron diwedd o wythnos chwech. Roeddwn i'n meddwl y byddwn i'n rhannu ychydig bach o ffeithiau hwyl. Rydw i wedi tynnu hyn i fyny o gosod data semester gorffennol. Efallai y cofiwch ein bod yn gofyn i chi ar bob Ffurflen set p os ydych wedi gwylio ar-lein neu os ydych wedi mynychu yn bersonol. A dyma yw'r data. Felly heddiw yn llawer iawn rhagweladwy. Ond rydym yn awyddus i dreulio ychydig o amser gyda chi serch hynny. Hoffai unrhyw un dyfalu pam mae hyn graff mor jaggy, i fyny i lawr, i fyny i lawr, mor gyson? Beth yw ystyr pob un o'r copaon a chafnau gynrychioli? GYNULLEIDFA: [Anghlywadwy] DAVID Malan: Yn wir. Ac yn fwy amusingly, duw a'n gwaredo, rydym yn cynnal un ddarlith ar ddydd Gwener ar ddechrau'r semester, dyna beth yr ydym yn ei weld yn digwydd. Felly heddiw, rydym yn cymryd rhan mewn ychydig mwy am strwythurau data. Ac i roi mwy o solid i chi model meddwl ar gyfer problemau yn bump, sydd bellach allan. Gamsillafu, yr hwn, rydym annhymerus law ffeil testun i chi rai 100,000 yn ogystal â geiriau Saesneg, ac ydych yn mynd i gael at chyfrif i maes sut i'w llwytho cleverly i mewn i gof, i mewn i RAM, gan ddefnyddio rhywfaint o ddata strwythur eich dewis. Nawr gallai un strwythur data o'r fath fod, ond yn ôl pob tebyg ni ddylai fod, y rhestr gysylltiedig eithaf syml, yr ydym yn cyflwyno tro diwethaf. A rhestr gysylltiedig o leiaf un fantais dros arae. Beth sydd un fantais o rhestr cysylltiedig dadlau? GYNULLEIDFA: Mewnosod. DAVID Malan: Mewnosod. Beth ydych chi'n ei olygu wrth hynny? GYNULLEIDFA: Unrhyw le ar hyd y rhestr [Anghlywadwy]. DAVID Malan: Da. Felly gallwch mewnosod elfen lle bynnag ydych am yng nghanol y rhestr heb orfod siffrwd unrhyw beth, hynny daethom i'r casgliad, yn ein didoli trafodaethau, nid yw o reidrwydd yn beth da, oherwydd mae'n cymryd amser i symud mewn gwirionedd pob un o'r bobl y rhai chwith neu i'r dde. Ac felly gyda rhestr cysylltiedig, gallwch jyst dyrannu gyda malloc, mae nod newydd, ac yna diweddaru un neu ddau o pointers-- dau, tri gweithrediadau max-- ac rydym yn gallu slotio rhywun mewn unrhyw le i mewn i restr. Beth arall oedd yn fanteisiol am restr cysylltiedig? Yeah? GYNULLEIDFA: [Anghlywadwy] DAVID Malan: Perffaith. Perffaith. Mae'n wirioneddol ddeinamig. Ac nad ydych yn cyflawni, ymlaen llaw, i ryw faint sefydlog darn o gof, fel y byddech yn cael i gydag amrywiaeth, y upside o'r rhain yw y gallwch ddyrannu nodau yn unig ar galw a thrwy hynny gan ddefnyddio dim ond cymaint o le wrth i chi ei angen mewn gwirionedd. Ar y llaw arall gydag amrywiaeth, gallech chi yn ddamweiniol yn dyrannu digon o. Ac yna mae'n dim ond yn mynd i fod yn boen yn y gwddf i ailddyrannu amrywiaeth mwy newydd, copïo popeth drosodd, rhad ac am ddim yr hen array, ac yna symud am eich busnes. Neu yn waeth, efallai y byddwch yn dyrannu ffordd mwy o gof nag yr ydych ei angen mewn gwirionedd, ac felly rydych yn mynd i gael iawn prin eu poblogaeth array, fel petai. Felly mae rhestr cysylltiedig yn rhoi hyn i chi manteision o egni a hyblygrwydd gyda fewnosodiadau a dileadau. Ond yn sicr rhaid cael pris a dalwyd. Yn wir, un o'r themâu archwilio ar y cwis sero Roedd un neu ddau o'r cyfaddawdau rydym wedi gweld hyd yn hyn. Felly beth yw pris a dalwyd neu Anfantais o restr cysylltiedig? Yeah. GYNULLEIDFA: Dim mynediad ar hap. DAVID Malan: Dim mynediad ar hap. Ond sy'n gofalu? Nid yw mynediad ar hap yn swnio'n gymhellol. GYNULLEIDFA: [Anghlywadwy] DAVID Malan: Yn union. Os ydych am gael a algorithm-- penodol a gadewch i mi mewn gwirionedd yn cynnig chwiliad deuaidd yn arbennig, a oedd yn yn un rydym wedi defnyddio tipyn o bit-- os nad oes gennych fynediad ar hap, Ni allwch wneud hynny rhifyddeg syml o ddod o hyd fel yr elfen canol ac yn neidio i'r dde i iddo. Yn lle hynny rhaid i chi ddechrau ar y cyntaf elfen a'r llinol chwilio o chwith i'r dde os ydych am ddod o hyd y canol neu unrhyw elfen arall. GYNULLEIDFA: Mae'n fwy na thebyg yn cymryd mwy o gof. DAVID Malan: Yn cymryd mwy o gof. Ble yw hynny'n ychwanegol gost yn dod o mewn cof? GYNULLEIDFA: [Anghlywadwy] DAVID Malan: Yn union. Yn yr achos yma, rydym yn cael rhestr cysylltiedig ar gyfer chyfanrifau, ac eto rydym yn dyblu y swm o gof mae angen drwy hefyd storio awgrymiadau hyn. Nawr llai o llawer fawr fel eich structs cael mwy o faint ac rydych yn storio nad oedd nifer ond efallai yn fyfyriwr neu ryw wrthrych arall. Ond y pwynt yn sicr yn parhau i fod. Ac felly mae nifer o'r gweithrediadau ar restrau cysylltiedig eu galw Roedd O fawr o llinellol n--. Pethau fel gosod neu chwilio neu ddileu rhag ofn elfen yn digwydd bod ar ddiwedd y y rhestr boed yn didoli neu beidio. Weithiau, efallai y byddwch yn cael lwcus ac yn terfynau felly yn is ar y gweithrediadau hyn Gallai hefyd fod yn amser gyson os ydych chi'n bob amser yn edrych ar yr elfen gyntaf, er enghraifft. Ond yn y pen draw, rydym yn addo i gyrraedd y greal sanctaidd o strwythurau data, neu rhywfaint ohono brasamcan, drwy gyfrwng amser cyson. Gallwn ddod o hyd elfennau neu ychwanegu elfennau neu ddileu elfennau o restr? Cawn weld yn weddol fuan. Ac mae'n troi allan bod un o'r mecanweithiau rydym yn mynd i ddechrau i ddefnyddio heddiw, defnydd blynyddol mewn p osodwyd pump, mewn gwirionedd yn eithaf cyfarwydd. Er enghraifft, os yw hyn yn griw o lyfrau arholiad, pob un ohonynt Mae myfyriwr yn gyntaf enwi ac enw olaf arno, ac yr wyf yn eu casglu oddi wrth ar ddiwedd arholiad, ac maen nhw i gyd 'n bert llawer mewn trefn ar hap, ac rydym am fynd ati i ddidoli arholiadau hyn fel y unwaith yn graddio 'i' jyst yn llawer haws ac yn gyflymach i law yn ôl allan i fyfyrwyr yn nhrefn yr wyddor. Beth fyddai eich greddf yn am bentwr o arholiadau fel hyn? Wel, os ydych chi fel fi, rydych Efallai y gwelwch fod hyn yn m, felly dw i'n mynd i fath o roi hyn mewn, os yw hyn yn fy tabl neu fy lawr lle Im 'yn lledaenu pethau out-- neu fy array really-- Efallai fy mod yn rhoi pob un o'r Ms mewn 'na. Oh. Dyma A. Felly, yr wyf efallai rhowch y Fel dros yma. Oh. Dyma A. arall dwi'n mynd i roi hynny dros yma. Dyma Z. Dyma M. arall Ac felly Efallai y byddwn yn dechrau gwneud pentyrrau fel hyn. Ac yna efallai byddwn i'n mynd yn nes ymlaen a math o nitpicky ly-iawn fath y pentyrrau unigol. Ond y pwynt yw y byddwn yn edrych yn y mewnbwn fy mod handed a byddwn yn gwneud rhywfaint o gyfrifo yn seiliedig ar fewnbwn y penderfyniad. Os yw'n dechrau gyda A, yn ei roi dros yno. Os yw'n dechrau gyda Z, yn ei roi dros yno, a phopeth yn y canol. Felly, mae hyn yn dechneg sy'n a adwaenir yn gyffredinol fel hashing-- H-A-S-H-- sydd yn gyffredinol yn golygu cymryd fel mewnbwn a defnyddio'r mewnbwn i gyfrifo gwerth, ar y cyfan mae nifer, a bod rhif yw'r mynegai i mewn i storio cynhwysydd, fel arae. Felly, mewn geiriau eraill, efallai y byddwn yn cael swyddogaeth hash, fel yr wyf yn ei wneud yn fy mhen, os wyf yn gweld rhywun yn enw sy'n dechrau gyda A, Rydw i'n mynd i fapio hynny i ddim yn fy mhen. Ac os wyf yn gweld rhywun sydd â Z, rwy'n mynd i fapio hynny i 25 yn fy mhen ac wedyn yn rhoi hynny ar y mwyaf pentwr diwethaf. Yn awr, os ydych yn meddwl am nad yw fy ymennydd ond gallai rhaglen C, pa rifau ydych yn dibynnu ar i gyflawni hynny un canlyniad? Mewn geiriau eraill, os ydych yn Roedd gan y cymeriad ASCII A, sut ydych chi'n penderfynu pa bwced i'w roi mewn? Mae'n debygol nad ydych eisiau roi mewn bwced 65, a oedd yn Byddai fod yn debyg dros yno heb reswm da. Ble ydych chi eisiau rhoi A o ran ei werth ASCII? Ble ydych chi am ei wneud at ei ASCII gwerth i ddod i fyny gyda bwced callach i'w roi i mewn? GYNULLEIDFA: Minws A. DAVID Malan: Yeah. Felly minws A neu finws benodol 65 os yw'n cyfalaf A. Neu 98 os mae'n llythrennau bach a a. Ac felly byddai hynny'n caniatáu i ni, iawn yn syml ac yn rhifyddol iawn, rhoi rhywbeth i mewn i fwced fel 'na. Felly, mae'n troi allan yr ydym yn ei wneud mewn gwirionedd hwn yn ogystal hyd yn oed gyda'r cwisiau. Felly, efallai y byddwch yn cofio i chi cylch eich addysgu gyd yn enw ar y clawr. Ac enwau y TF yn cael eu trefnu i mewn i colofnau hyn yn nhrefn yr wyddor, yn dda, credwch neu beidio, pan fydd pob un o'r 80 a mwy o ohonom at ei gilydd y noson o'r blaen i radd, y cam olaf yn ein proses graddio yw hash y cwisiau i mewn i mawr gofod llawr yn y [Anghlywadwy] ac i osod cwisiau pawb allan yn union yr nhrefn eu TF yn enwau ar y clawr, oherwydd Yna, mae'n llawer haws i ni i chwilio drwy fod defnyddio llinellol chwilio neu ryw fath o glyfrwch am TF i ddod o hyd ef neu cwisiau ei myfyrwyr. Felly, y syniad hwn o stwnsio y byddwch yn gweld yn eithaf pwerus yn eithaf mewn gwirionedd gyffredin a sythweledol iawn, yn debyg o bosibl rhannu a Roedd Conquer yn wythnos sero. I ymlaen yn gyflym at y hackathon cwpl o flynyddoedd yn ôl. Roedd hyn Zamyla a chwpl o myfyrwyr cyfarchiad staff eraill fel y maent yn dod i mewn. Ac rydym wedi cael criw cyfan o plygu tablau yno gyda tagiau enw. Ac roeddem wedi y tagiau enw a drefnwyd â thebyg y Fel dros yno ac mae'r ZS dros yno. Ac felly un o'r TFS glyfar iawn ysgrifennodd hyn gan fod y cyfarwyddiadau ar gyfer y diwrnod. Ac yn wythnos 12 o'r semester hwn i gyd yn gwneud synnwyr perffaith ac mae pawb yn gwybod beth i'w wneud. Ond ar unrhyw adeg eich bod wedi ciw yn yr un modd, eich bod yn gweithredu'r yr un syniad o hash. Felly gadewch i ni ffurfioli ei fod ychydig bach. Dyma arae. Mae wedi tynnu i fod ychydig yn eang yn unig i ddarlunio, yn weledol, y gallem roi llinynnau mewn rhywbeth fel hyn. Ac mae amrywiaeth hwn yw yn amlwg o faint 26 cyfanswm. Ac yn cael ei alw'n y peth tabl fympwyol. Ond mae hyn yn unig yw rendition artist o'r hyn a allai tabl hash fod. Felly tabl hash nawr yn mynd i fod yn strwythur data lefel uwch. Ar ddiwedd y dydd rydym chi ar fin i weld bod chi Gall gweithredu tabl hash, a oedd yn debyg iawn i'r llinell siec i mewn mewn hackathon llawer fel hyn tabl a ddefnyddir ar gyfer didoli llyfrau arholiad. Ond tabl hash yn fath o lefel uchel hon cysyniad a allai ddefnyddio amrywiaeth o dan y cwfl i'w weithredu, neu gallai ddefnyddio rhestr hyd, neu hyd yn oed efallai rhai strwythurau data arall. Ac yn awr dyna cymryd theme-- mae rhai o'r cynhwysion sylfaenol hyn fel amrywiaeth ac adeilad hwn bloc nawr o restr hyd a gweld beth arall y gallwn adeiladu ar ben hynny, fel cynhwysion i mewn rysáit, gan wneud mwy a mwy canlyniadau terfynol yn ddiddorol a defnyddiol. Felly, gyda y tabl hash gallem ei roi ar waith er cof ddarluniadol fel hyn, ond sut y gallai fod mewn gwirionedd yn cael ei godio i fyny? Wel, efallai mor syml yw hyn. Os GALLU ym mhob gapiau, yn unig rhywfaint constant-- er enghraifft 26, am 26 llythrennau'r alphabet-- Efallai y byddwn yn galw fy mwrdd amrywiol, ac efallai y byddwn yn honni bod fy mod i'n mynd i rhoi sêr char i mewn 'na, neu linyn. Felly mae'n mor syml â hyn os ydych yn awyddus i weithredu tabl hash. Ac eto, mae hyn yn wir yn unig arae. Ond unwaith eto, mae hash tabl yn awr yr hyn yr ydym chi helpu ffoniwch math data haniaethol bod yn unig math o haenau cysyniadol ar ei ben o rywbeth mwy cyffredin Bellach hoffi arae. Nawr, sut ydyn ni'n mynd am ddatrys problemau? Wel, yn gynharach cefais y moethus o gael digon o le tabl yma fel y gallwn i roi'r cwisiau unrhyw le roeddwn i eisiau. Felly efallai Fel ewch yma. Gallai ZS ewch yma. Gallai Ms ewch yma. Ac yna roedd rhaid i mi ychydig o le ychwanegol. Ond mae hyn yn dipyn o hawl twyllo yn awr oherwydd y tabl hwn, os Fi 'n sylweddol yn meddwl am y peth fel amrywiaeth, yn unig mynd i fod o ryw faint sefydlog. Felly dechnegol, os wyf yn tynnu fyny cwis myfyriwr arall a gweld, oh, person hwn enw yn dechrau gyda A hefyd, Wyf yn fath o eisiau ei roi yno. Ond cyn gynted ag yr wyf yn ei roi yno, os y tabl hwn yn wir yn cynrychioli arae, Rydw i'n mynd i gael ei ddisodli nac clobbering pwy bynnag cwis myfyriwr hwn yw. Hawl? Os yw hyn yn arae, gall dim ond un peth mynd ym mhob un o gelloedd neu elfennau hyn. Ac felly yr wyf yn fath o gael i ddewis a dethol. Nawr gynharach wyf yn fath o twyllo ac yn gwneud hyn neu I jyst fath o pentyrru nhw uwchben ei gilydd. Ond nid yw hynny'n mynd i hedfan yn y cod. Felly, lle y gallwn i roi'r ail fyfyriwr y mae ei enw A yw os bydd yr holl wyf oedd yn hyn gofod tabl sydd ar gael? Ac yr wyf wedi defnyddio tri slotiau ac mae'n edrych fel mae dim ond ychydig o rai eraill. Beth allech chi ei wneud? GYNULLEIDFA: [Anghlywadwy] DAVID Malan: Yeah. Efallai gadewch i ni jyst cadw pethau'n syml. Hawl? Nid yw'n cyd-fynd lle'r wyf am ei roi. Felly, dw i'n mynd i roi dechnegol lle byddai B yn mynd. Yn awr, wrth gwrs, rwy'n dechrau i beintio fy hun i mewn i gornel. Os byddaf yn mynd i fyfyriwr y mae ei enw mewn gwirionedd B, nawr B yn mynd i gael ei symud ychydig ymlaen, fel y gallai ddigwydd, yep, os yw hyn yn B, erbyn hyn mae'n rhaid iddo fynd yma. Ac felly mae hyn yn gyflym iawn Gallai fod yn broblematig, ond mae'n dechneg sydd mewn gwirionedd y cyfeirir ato fel llinellol treiddgar, lle 'ch jyst yn ystyried eich arae i fod ar hyd y llinell. A 'ch jyst fath o ymchwilio neu arolygu pob elfen ar gael chwilio am fan a'r lle sydd ar gael. A chyn gynted ag y byddwch yn dod o hyd un, ydych am ei ddefnyddio mewn 'na. Yn awr, y pris yn cael ei dalu yn awr am ateb hwn yw beth? Mae gennym amrywiaeth maint sefydlog, a pan fyddaf yn mewnosod enwau i mewn iddo, o leiaf i ddechrau, beth sydd yr amser yn rhedeg o mewnosod am roi i'r myfyrwyr ' cwisiau yn y bwcedi cywir? Big O am yr hyn? GYNULLEIDFA: n. DAVID Malan: Clywais O fawr o n. Ddim yn wir. Ond byddwn yn tynnu ar wahân pam mewn dim ond eiliad. Beth arall y gallai fod? GYNULLEIDFA: [Anghlywadwy] DAVID Malan: A gadewch i mi wneud hynny ar eu golwg. Felly, mae'n debyg mai dyma'r llythyren S. GYNULLEIDFA: Mae'n un. DAVID Malan: Mae'n un. Hawl? Mae hwn yn array, a oedd yn golygu ein bod yn cael mynediad ar hap. Ac os ydym yn meddwl o hyn fel sero ac mae hyn fel 25, ac yr ydym yn sylweddoli hynny, oh, dyma fy mewnbwn S, Yn sicr, gallaf drosi S, cymeriad ASCII, i nifer cyfatebol rhwng sero a 25 ac yna yn syth roi yn lle y mae'n perthyn. Ond wrth gwrs, cyn gynted ag y gallaf gael i'r ail berson pwy enw i yw A neu B neu C yn y pen draw, os ydw i wedi defnyddio'r llinol treiddgar fel fy ateb, yr amser yn rhedeg o mewnosod yn yr achos gwaethaf mewn gwirionedd yn mynd i ddatganoli i mewn i beth? A chlywais ef yma yn gywir yn gynnar. GYNULLEIDFA: [Anghlywadwy] DAVID Malan: Felly mae'n n wir unwaith mae gennych set ddata digon mawr. Felly, ar y naill law, os eich amrywiaeth yn ddigon mawr a bod eich data yn ddigon prin, rydych cael y tro hwn cyson hardd. Ond cyn gynted ag y byddwch yn dechrau mynd yn fwy a mwy o elfennau, a dim ond yn ystadegol byddwch yn cael mwy o bobl gyda'r llythyr A gan fod eu henw neu y llythyr B, gallai o bosibl yn datganoli i mewn i rywbeth mwy llinol. Felly, ddim yn hollol berffaith. Gallai Felly, rydym yn ei wneud yn well? Wel, beth oedd ein ateb o'r blaen pan fyddwn am gael mwy deinamig nag rhywbeth fel arae ganiateir? GYNULLEIDFA: [Anghlywadwy] DAVID Malan: Beth wnaethon ni gyflwyno? Yeah. Felly rhestr cysylltiedig. Wel, gadewch i ni weld beth a cysylltiedig Efallai y rhestr yn ei wneud i ni yn lle hynny. Wel, gadewch i mi gynnig ein bod yn tynnu y llun fel a ganlyn. Nawr mae hyn yn wahanol llun o enghraifft o destun gwahanol, mewn gwirionedd, bod mewn gwirionedd gan ddefnyddio amrywiaeth o maint 31. Ac awdur hwn yn syml Penderfynodd i hash llinynnau Nid yw yn seiliedig ar enwau y person, ond yn seiliedig ar eu birthdates. Heb ystyried y mis, maent yn cyfrifedig os ydych yn geni ar y cyntaf o fis neu y 31ain o fis, mae'r awdur Bydd hash yn seiliedig ar y gwerth hwnnw, fel y gellir rhannu enwau allan ychydig yn fwy na dim ond y gallai 26 o smotiau yn caniatáu. Ac efallai ei fod yn ychydig yn fwy o unffurf na mynd gyda llythrennau yn nhrefn yr wyddor, oherwydd wrth gwrs mae yna fwy na thebyg mwy o bobl yn y byd gydag enwau sy'n dechrau gyda A nag yn sicr rhai llythrennau eraill o'r wyddor. Felly, efallai fod hyn yn ychydig yn mwy unffurf, gan dybio dosbarthiad unffurf o fabanod ar draws y mis. Ond, wrth gwrs, mae hyn yn dal i fod yn amherffaith. Hawl? Rydym yn cael gwrthdrawiadau. Pobl lluosog yn hyn strwythur data yn dal i cael yr un dyddiad geni, o leiaf eich bod yn waeth beth yw mis. Ond beth y mae'r awdur ei wneud? Wel, mae'n edrych fel gennym amrywiaeth ar yr ochr chwith a dynnwyd yn fertigol, ond dim ond rendition artist. Does dim ots pa gyfeiriad yr ydych tynnu amrywiaeth, mae'n dal i fod arae. Beth yw hyn amrywiaeth o ôl pob golwg? GYNULLEIDFA: Rhestr Cysylltiedig. DAVID Malan: Yeah. Mae'n edrych fel ei fod yn amrywiaeth o restr cysylltiedig. Felly, unwaith eto, at y pwynt hwn o fath o ddefnyddio strwythurau data hyn bellach fel cynhwysion i fwy datrysiadau diddorol, gallwch hollol gymryd sylfaenol, fel amrywiaeth, ac yna cymryd rhywbeth mwy diddorol fel rhestr cysylltiedig a hyd yn oed eu cyfuno i mewn i hyd yn oed strwythur data yn fwy diddorol. Ac yn wir, mae hyn hefyd y byddai gael ei alw tabl hash, lle yr amrywiaeth yn 'n sylweddol y tabl hash, ond y tabl hash wedi cadwyni, fel petai, sy'n gallu tyfu neu grebachu yn seiliedig ar y nifer o elfennau rydych am ei fewnosod. Yn awr, yn unol â hynny, beth sy'n yr amser yn rhedeg nawr? Os ydw i eisiau i fewnosod rywun y mae eu pen-blwydd yn 31 Hydref, lle y mae ef neu hi yn mynd? Mae pob hawl. Ar y gwaelod lle mae'n dweud 31. Ac mae hynny'n berffaith. Dyna oedd amser cyson. Ond beth os ydym yn dod o hyd i rywun arall y mae eu pen-blwydd yn cael ei, gadewch i ni weld, Hydref, Tachwedd, 31 Rhagfyr? Ble mae ef neu hi yn mynd i fynd? Un peth. Mae dau gam er. Mae hynny'n gyson ond yn tydi? Mae pob hawl. Ar hyn o bryd y mae. Ond yn yr achos cyffredinol, po fwyaf o bobl rydym yn ychwanegu, probabilistically, rydym yn mynd i gael mwy a mwy o wrthdrawiadau. Nawr mae hyn yn ychydig well oherwydd dechnegol Erbyn hyn gallai fy cadwyni fod mewn yr achos gwaethaf pa mor hir? Os byddaf yn mewnosod n bobl i mewn i hyn yn fwy strwythur data soffistigedig, n phobl, yn yr achos gwaethaf mae'n mynd i fod yn n. Pam? GYNULLEIDFA: Oherwydd os pawb yr un pen-blwydd, maen nhw'n mynd i fod yn un llinell. DAVID Malan: Perffaith. Gallai fod yn ychydig yn contrived, ond yn wir yn yr achos gwaethaf, os oes gan bawb yr un pen-blwydd, o ystyried y mewnbynnau sydd gennych, ydych yn mynd i gael cadwyn aruthrol hir. Ac felly, fe allech chi alw yn hash tabl, ond mewn gwirionedd 'i' dim ond rhestr cysylltiedig enfawr gyda llawer gyfan o le gwastraffu. Ond yn gyffredinol, os byddwn yn cymryd yn ganiataol bod o leiaf penblwyddi yn uniform-- ac mae'n debyg nad yw'n. Fy mod yn gwneud hynny i fyny. Ond os ydym yn tybio, er mwyn trafod eu bod, yna mewn theori, os hwn yw'r gynrychiolaeth fertigol y rhesi, yn dda yna gobeithio eich bod yn mynd i gael cadwyni sydd, chi'n gwybod, fwy neu lai yr un hyd lle mae pob un o'r mae'r rhain yn cynrychioli diwrnod o'r mis. Nawr, os oes 31 diwrnod yn y mis, mae hynny'n golygu fy amser rhedeg 'n sylweddol yw O fawr o n dros 31, a oedd yn teimlo'n well na llinellol. Ond beth oedd yn un o'n ymrwymiadau cwpl o wythnosau yn ôl pryd bynnag y daeth i fynegi yr amser yn rhedeg o algorithm? Dim ond dim ond yn edrych ar y term trefn uchel. Hawl? 31 yn bendant o gymorth. Ond mae hyn yn dal i fod yn O fawr o n. Ond mae un o'r themâu o broblem a osodwyd bump yn mynd i fod i cydnabod hynny gwbl, asymptotically, yn ddamcaniaethol y strwythur data dim yn well na dim ond un rhestr gysylltiedig enfawr. Ac yn wir, yn yr achos gwaethaf, mae hyn Efallai y tabl hash datganoli i mewn i hynny. Ond yn y byd go iawn, gyda ni bodau dynol bod Macs neu gyfrifiaduron eu hunain neu beth bynnag ac yn rhedeg y byd go iawn meddalwedd ar ddata byd go iawn, pa algorithm ydych chi'n mynd i well gan? Yr un sy'n cymryd camau pen neu'r un sy'n cymryd ei rannu n erbyn 31 cam i ddod o hyd i ddarn o ddata neu i chwilio am ychydig o wybodaeth? Yr wyf yn golygu, yn hollol y 31 o wneuthuriadau gwahaniaeth yn y byd go iawn. Mae'n yw 31 gwaith yn gyflymach. Ac rydym pobl yn sicr mynd i werthfawrogi hynny. Felly, yn sylweddoli y ddeuoliaeth yno rhwng gwirionedd siarad am bethau mewn theori a asymptotically sy'n bendant Mae gan werth fel yr ydym wedi gweld, ond yn y byd go iawn, os ydych yn gofalu am jyst gwneud y hapus dynol ar gyfer mewnbynnau cyffredinol, efallai y byddwch yn dda iawn am dderbyn y ffaith bod, ie, mae hyn yn llinol, ond mae'n 31 gwaith yn gyflymach Efallai na llinol fod. Ac yn well eto, nid ydym yn rhaid i gwneud rhywbeth mympwyol fel dyddiad geni, gallem dreulio ychydig mwy o amser a glyfrwch a meddwl am yr hyn y gallem ei wneud, Rhoddir enw person ac efallai eu dyddiad geni, i gyfuno rhai cynhwysion i chyfrif i maes rhywbeth sydd yn wirioneddol yn fwy unffurf ac yn llai jaggy, fel petai na hyn darlun Ar hyn o bryd yn awgrymu y gallai fod. Sut y gallem weithredu hyn yn y cod? Wel, gadewch i mi gynnig ein bod yn dim ond benthyg rhywfaint o gystrawen rydym wedi Defnyddir cwpl o weithiau hyd yn hyn. Ac yr wyf i'n mynd i ddiffinio a nod, sydd unwaith eto yn derm cyffredinol ar gyfer dim ond rhai cynhwysydd ar gyfer rhywfaint o strwythur data. Rydw i'n mynd i gynnig bod llinyn yn mynd i mewn 'na. Ond rydym yn mynd i ddechrau cymryd rhai sy'n hyfforddi olwynion i ffwrdd nawr. Dim llyfrgell CS50 mwy mewn gwirionedd, oni bai eich bod am i'w ddefnyddio ar gyfer eich derfynol project, sy'n iawn, ond erbyn hyn rydyn ni'n mynd i dynnu yn ôl i'r llenni ac yn dweud mai dim ond seren torgoch. Felly y gair yno yn mynd i fod enw'r person dan sylw. Ac yn awr mae gen i gyswllt yma at y nod nesaf fel bod y rhain yn cynrychioli pob un o'r nodau yn y gadwyn, o bosibl, o restr cysylltiedig. Ac yn awr sut ydw i'n datgan y tabl hash ei hun? Sut ydw i'n datgan strwythur cyfan hwn? Wel, mewn gwirionedd, yn debyg iawn i mi defnyddio pwyntydd i ddim ond yr elfen gyntaf o restr o'r blaen, yn yr un modd y gallaf ddweud Fi jyst angen criw o awgrymiadau i weithredu'r tabl hwn hash cyfan. Rydw i'n mynd i gael amrywiaeth Gelwir tabl ar gyfer tabl hash. Mae'n mynd i fod o gapasiti maint. Dyna faint o elfennau y gall ffitio i mewn iddo. Ac mae pob un o'r elfennau hynny yn hyn arae yn mynd i fod yn seren nod. Pam? Wel, fesul y llun, yr hyn rwy'n gweithredu'r tabl hash fel effeithiol yn y dechrau yn unig arae hwn yr ydym wedi tynnu yn fertigol, pob un o'r sgwariau y mae eu cynrychioli pwyntydd. Bod rhai sydd â slaes drwyddynt yn unig null. A'r rhai sydd â saethau mynd i'r dde yn awgrymiadau gwirioneddol i nodau gwirioneddol, Ergo ddechrau rhestr cysylltiedig. Felly dyma, felly, yw sut y gallem gweithredu tabl hash sy'n gweithredu gadwyno wahân. Nawr gallwn ni ei wneud yn well? Mae pob hawl Addewais tro diwethaf y gallem gyflawni amser cyson. Ac yr wyf yn fath o yn rhoi i chi amser cyson yma, ond yna ni ddywedodd mewn gwirionedd amser cyson am ei fod yn dal i fod yn dibynnu ar y cyfanswm nifer o elfennau eich bod yn cyfrannu at strwythur data. Ond mae'n debyg ein bod yn gwneud hyn. Gadewch i mi fynd yn ôl i'r sgrin dros yma. Gadewch i mi hefyd yn rhagweld hyn i fyny yma, yn glir y sgrin, ac mae'n debyg fy mod yn gwneud hyn. Gadewch i ni dybio Roeddwn i eisiau i roi enw Daven mewn i mewn i fy strwythur data. Felly, rwyf am i fewnosod llinyn Daven i mewn i strwythur data. Beth os nad wyf yn defnyddio hash tabl, ond yr wyf yn defnyddio rhywbeth sy'n fwy tebyg i goeden fel coeden deulu, lle gennych rywfaint gwreiddiau yn y top ac yna nodau a dail sy'n mynd ar i lawr ac allan. Tybiwch Yna, fy mod eisiau i fewnosod Daven yn i mewn i beth rhestr wag ar hyn o bryd. Rydw i'n mynd i wneud y canlynol: Rwy'n mynd i greu nod yn y teulu hwn coed-fel strwythur data sy'n edrych ychydig fel hyn, pob un ohonynt petryal wedi, gadewch i ni ddweud, am y tro 26 elfen ynddo. A phob un o'r celloedd yn y arae hyn yn mynd i gynrychioli llythyr o wyddor. Yn benodol, yr wyf i'n mynd i drin mae hyn yn A, yna B, yna C, yna D, yr un yma fan hyn. Felly, mae hyn yn mynd i yn effeithiol gynrychioli'r llythyren D. Ond i fewnosod gyd Daven yn enwi angen i mi wneud ychydig mwy. Felly dwi'n mynd yn gyntaf i hash, fel petai. Rydw i'n mynd i edrych ar y llythyr cyntaf yn Daven sydd yn amlwg yn D, ac yr wyf i'n mynd i ddyrannu a nod sy'n edrych fel this-- petryal mawr mawr ddigon i gyd-fynd â'r wyddor i gyd. Nawr D yn cael ei wneud. Nawr A. D-A-V-E-N yw'r nod. Felly nawr yr hyn yr wyf i'n mynd i wneud yw hyn. Cyn gynted ag y dechreuais rhybudd D does dim pwyntydd yno. Mae'n gwerthoedd garbage ar hyn o bryd, neu efallai y byddwn ymgychwyn iddo null. Ond gadewch i mi gadw i fynd gyda syniad hwn o adeiladu coeden. Gadewch i mi yn dyrannu un arall o'r rhain nodau sydd â 26 o elfennau ynddo. A ydych yn gwybod beth? Os yw hyn yn unig yw nod mewn cof bod I greu gyda malloc, gan ddefnyddio struct gan y byddwn yn fuan yn gweld, Rydw i'n mynd i wneud this-- Rydw i'n mynd i dynnu saeth o y peth sy'n cynrychioli D i lawr i'r nod newydd. Ac yn awr, yn gyntaf y nesaf llythyr yn enw'r Daven yn, V-- D-A-V-- Rydw i'n mynd i fynd yn ei flaen a thynnu nod arall fel hyn, lle, mae'r elfennau V yma, a oedd byddwn yn tynnu i whoops instance--. Ni fyddwn yn tynnu yno. Mae'n mynd i fynd yma. Yna rydym yn mynd i ystyried hyn yn V. Ac yna i lawr yma rydym yn mynd i mynegai i lawr o V i mewn i hyn a byddwn yn ystyried E. Ac yna o fan hyn rydym yn mynd i mynd yn cael un o'r nodau hyn yn fan hyn. Ac yn awr mae gennym gwestiwn i'w ateb. Mae angen i I rhywsut yn dangos bod rydym yn ar ddiwedd y llinyn Daven. Er mwyn i mi ei adael null. Ond beth os ydym wedi Daven yn enw llawn hefyd, a oedd yn yw, fel yr ydym wedi dweud, Davenport? Felly beth os Daven yw mewn gwirionedd is- linyn, rhagddodiad o gyfres llawer hirach? Ni allwn yn unig yn barhaol yn dweud dim byd yn mynd i fynd yno, oherwydd gallem byth yn mewnosod gair fel Davenport i mewn i'r Strwythur data Felly, yr hyn y gallem ei wneud yn lle hynny yw yn trin pob un o'r elfennau hyn fel efallai gael dau elfennau y tu mewn ohonynt. Mae un yn pwyntydd, yn wir, gan fy mod i wedi bod yn ei wneud. Felly mae pob un o'r blychau hyn Nid yw un gell yn unig. Ond beth os bydd y top one-- yr un isaf o mynd i fod yn null, oherwydd nid oes unrhyw Davenport eto. Beth os bydd yr un uchaf mae rhywfaint o werth arbennig? Ac mae'n mynd i fod ychydig yn anodd i dynnu ei maint hwn. Ond mae'n debyg mai dim ond marc siec. Gwirio. D-A-V-E-N yn llinyn yn y strwythur data. Yn y cyfamser, os oedd gennyf mwy o le fan hyn, gallwn i wneud P-O-R-T, a gallwn roi siec yn y nod fod gan y llythyren T ar y diwedd un. Felly mae hwn yn aruthrol cymhleth sy'n edrych strwythur data. A fy llawysgrifen yn sicr nid yw'n helpu. Ond os oeddwn i eisiau i fewnosod rhywbeth arall, yn ystyried yr hyn y byddem yn ei wneud. Os ydym yn awyddus i roi David i mewn, byddem yn dilyn yr un rhesymeg, D-A-V, ond erbyn hyn byddwn yn rhoi ar y nesaf Elfen nid o E, ond o I i D. Felly, mae mynd i fod yn mwy o nodau yn y goeden hon. Rydym yn mynd i gael galwad malloc mwy. Ond dwi ddim eisiau gwneud llanast cyflawn o'r darlun hwn. Felly, gadewch i ni yn lle edrych ar un sydd wedi ei lunio cyn- fel hyn gyda beidio dot, dot, dotiau, ond araeau unig talfyrru. Ond mae pob un o'r nodau yn y goeden hon hyd yma yn cynrychioli'r un thing-- amrywiaeth Ray o faint 26. Neu, os ydym am fod wir yn briodol yn awr, beth os yw enw rhywun fel collnod, gadewch i ni cymryd yn ganiataol bod pob nod mewn gwirionedd wedi fel 27 mynegeion ynddo, nid dim ond 26. Felly, mae hyn yn awr yn mynd i fod yn ddata strwythur a elwir yn trie-- T-R-I-E. Mae trie, sydd yn sôn, hanesyddol enw clyfar i goeden sy'n ei optimeiddio ar gyfer adfer, sydd wrth gwrs, ei sillafu gyda I-E felly mae'n trie. Ond mae hynny'n hanes y trie. Felly mae trie yw hyn data tebyg i goeden Strwythur fel coeden deulu yn y pen draw yn ymddwyn fel 'na. A dyma yn unig yw enghraifft arall o criw cyfan o enwau pobl eraill. Ond mae'r cwestiwn yn awr wrth law yn yr hyn sydd rydym yn ennill drwy gyflwyno Gellir dadlau bod mwy strwythur data cymhleth, ac un, dweud y gwir, sy'n defnyddio llawer o gof. Oherwydd hyd yn oed er, ar hyn o bryd, rwy'n dim ond gan ddefnyddio pwyntydd D a A a V a Es a Ns, Rydw i'n gwastraffu yn andros o lot o gof. Ond lle rwy'n treulio un adnodd, Dwi'n tueddu i ddim yn ennill yn ôl un arall. Felly, os ydw i'n treulio mwy o le, beth sydd yn ôl pob tebyg y gobaith? Fy mod i'n gwario llai beth? GYNULLEIDFA: Llai o amser. DAVID Malan: Time. Nawr pam y gallai hynny fod? Wel, beth yw gosod amser, o ran O mawr yn awr, o enw fel Daven neu Davenport neu David? Wel, roedd Daven pum cam. Byddai Davenport yn naw cam, felly byddai'n ychydig mwy o gamau. Byddai David fod pum cam yn ogystal. Felly, y rhai yn concrid rhifau, ond yn sicr mae 'na uchaf yn rhwymo ar y hyd yr enw rhywun. Ac yn wir, yn y broblem setiau o bump fanyleb, rydym yn mynd i gynnig ei fod yn rhywbeth dyna cymeriadau 40-rhai-od. Yn realistig, nid oes neb wedi enw anfeidrol hir, sef i ddweud bod hyd a enwi neu hyd llinyn gallem rhaid i rai cyflwr strwythur yn dadlau beth? Mae'n gyson. Hawl? Gallai fod yn gyson mawr fel 40-rhywbeth, ond mae'n gyson. Ac nid oes ganddo unrhyw ddibyniaeth ar faint o enwau eraill yn y strwythur data. Mewn geiriau eraill, os byddaf eisiau nawr mewnosod Colton neu Gabriel neu Rob neu Zamyla neu Alison neu Belinda neu unrhyw enwau eraill o'r staff yn ddata hon strwythur, yw'r amser yn rhedeg o mewnosod enwau eraill mynd i fod o gwbl effeithio gan faint o elfennau eraill yn yn y strwythur data yn barod? Dyw hi ddim. Hawl? Oherwydd ein bod yn ei ddefnyddio yn effeithiol y tabl hwn hash aml-haen. A'r amser yn rhedeg o unrhyw agwedd ar y yn dibynnu nid ar nifer y elfennau sydd yn y strwythur data neu sy'n mynd yn y pen draw i fod yn y strwythur data, ond ar y hyd y beth yn benodol? Mae'r llinyn yn cael mewnosod, sydd yn gwneud mae hyn asymptotically gyson O fawr adeg-- o un. A dweud y gwir, dim ond mewn y byd go iawn, mae hyn yn yn golygu gosod enw Daven yn cymryd fel pum cam, neu Davenport naw grisiau, neu David pum cam. Dyna 'n bert darn amseroedd rhedeg bach. Ac, yn wir, mae hynny'n iawn beth da, yn enwedig pan fydd nid yw'n dibynnu ar y cyfanswm Nifer o elfennau i mewn 'na. Felly, sut y gallwn weithredu hyn fath o strwythur yn y cod? Mae'n ychydig yn fwy cymhleth, ond yn dal 'i' unig gais o blociau adeiladu sylfaenol. Rydw i'n mynd i ailddiffinio nod ni fel a ganlyn: bool gelwir word-- ac mae hyn yn Gellid eu galw unrhyw beth. Ond mae'r bool yn cynrychioli beth tynnais fel arwydd siec. Ie. Mae hyn yn y pen llinyn yn y strwythur data. Ac, wrth gwrs, mae'r seren nôd mae yn cyfeirio at blant. Ac, yn wir, yn union fel coeden deulu, rydych Byddai ystyried y nodau sy'n cael eu hongian off o waelod rhyw rhiant elfen i fod yn blant. Ac felly mae'r plant yn mynd i fod amrywiaeth o 27, yr un 27 dim ond bod am collnod. Rydym yn mynd i ddatrys o achos arbennig hwnnw. Felly, gallwch gael rhai enwau gyda collnodau. Efallai dylai hyd yn oed cysylltnod mynd i mewn yno, ond wnewch chi helpu gweld mewn p set 5 yn unig gofal yr ydym yn am lythrennau a chollnod. Ac yna sut ydych chi'n cynrychioli strwythur data ei hun? Sut ydych chi'n cynrychioli y gwraidd y trie hwn, fel petai? Wel, yn union fel gyda rhestr cysylltiedig, rydych angen pwyntydd at yr elfen gyntaf. Gyda trie 'ch jyst angen un pwyntydd at wraidd trie hwn. Ac oddi yno gallwch hash eich ffordd i lawr yn ddyfnach ac yn ddyfnach i bob nod arall yn y strwythur. Felly yn syml gyda'r can hwn rydym yn cynrychioli y struct. Nawr Meanwhile-- O, cwestiwn. GYNULLEIDFA: Beth yw gair bool? DAVID Malan: word Bool yn dim ond hyn C ymgnawdoliad o'r hyn yr wyf yn ei ddisgrifio yn y blwch yma, pan Dechreuais rhannu pob un o'r elfennau amrywiaeth i mewn i ddau ddarn. Mae un yn pwyntydd i'r nod nesaf. Mae'r llall wedi i fod rhywbeth fel blwch gwirio i ddweud ie, mae 'na word Daven sy'n dod i ben yma, oherwydd nid ydym am, ar hyn o bryd, Dave. Er bod Dave yn mynd i fod yn Gair dilys, nid ei fod yn y trie eto. Ac nid yw D yn air. Ac nid yw D-A yn air neu enw. Felly y marc siec yn dangos ar ôl i chi yn unig taro nod hwn yw'r llwybr blaenorol o gymeriadau mewn gwirionedd yn llinyn eich bod wedi mewnosod. Felly dyna i gyd y bool mae yn ei wneud i ni. Unrhyw gwestiynau eraill ar gais? Yeah. GYNULLEIDFA: Beth yw'r gorgyffwrdd? Beth os oes gennych Dave a Daven? DAVID Malan: Perffaith. Beth os oes gennych Dave a Daven? Felly os ydym yn mewnosod, yn dweud llysenw, am David-- Dave-- D-A-V-E? Mae hyn mewn gwirionedd super syml. Felly, rydym yn unig yn mynd i gymryd pedwar cam. D-A-V-E. A beth sydd yn rhaid i I yn ei wneud ar ôl i mi daro y pedwerydd nod? Dim ond yn mynd i wirio. Rydym eisoes yn dda i fynd. Done. Pedwar cam. Amser Cyson asymptotically. Ac yn awr rydym wedi dangos bod y ddau Dave ac Daven yn llinynnau yn y strwythur. Felly nid problem. Ac yn sylwi sut y mae'r presenoldeb o Daven nid oedd yn ei gwneud yn gymryd unrhyw mwy o amser neu lai amser ar gyfer Dave ac i'r gwrthwyneb. Felly, beth arall y gallwn ei wneud yn awr? Rydym wedi defnyddio trosiad hwn o'r blaen o hambyrddau yn cynrychioli rhywbeth. Ond mae'n troi allan bod yn pentwr o hambyrddau mewn gwirionedd dangosol o ddata haniaethol arall type-- strwythur data lefel uwch bod ar ddiwedd y dydd yn unig fel arae neu restr cysylltiedig neu rywbeth mwy cyffredin. Ond ei fod yn fwy diddorol cysyniad cysyniadol. Pentwr, fel y rhain hambyrddau yma yn Mather, yn cael eu galw yn gyffredinol jyst that-- pentwr. Ac yn y math hwn o strwythur data gennych ddau operations-- oes gennych un gwthio yn galw am gan ychwanegu rhywbeth at y simnai, fel rhoi hambwrdd arall yn ôl ar ben y pentwr. Ac yna pop, sy'n golygu eich bod gymryd y oddi ar hambwrdd topmost. Ond yr hyn sy'n allweddol am stac yw bod 'i' got y nodwedd chwilfrydig. Gan fod y staff ffreutur yn aildrefnu'r hambyrddau ar gyfer y pryd nesaf, beth sy'n mynd i fod yn wir am sut mae myfyrwyr rhyngweithio gyda'r strwythur data? GYNULLEIDFA: Maent yn mynd i pop un off. DAVID Malan: Maent yn mynd i pop un off, gobeithio y top. Fel arall, 'i' jyst fath o dwp i fynd yr holl ffordd i'r gwaelod. Hawl? Nid yw'r strwythur data ddim yn caniatáu i chi chrafangia 'r hambwrdd gwaelod o leiaf yn hawdd. Felly mae hyn yn chwilfrydig eiddo i'r stac bod yr eitem olaf ynddo yw mynd i fod yr un allan gyntaf. A gwyddonwyr cyfrifiadurol yn galw LIFO-- hyn bara i mewn, cyntaf allan. Ac mae'n mewn gwirionedd oes gan ceisiadau diddorol. Dyw hi ddim o reidrwydd mor amlwg â rhai eraill, ond gall, yn wir, fod yn ddefnyddiol, a gall, yn wir, yn cael eu rhoi ar waith mewn un neu ddau o wahanol ffyrdd. Felly un, ac mewn gwirionedd, gadewch mi beidio i ddeifio i mewn i hynny. Gadewch i ni wneud hyn yn lle hynny. Gadewch i ni edrych ar un dyna bron y un syniad, ond mae'n ychydig yn decach. Hawl? Os ydych yn un o fechgyn ffan hyn neu merched sydd wir yn hoffi cynnyrch Apple ac rydych nes i ddeffro am 03:00 i linell i fyny ar ryw siop i gael y iPhone diweddaraf yn iawn, byddwch yn allai fod wedi ciw i fyny fel hyn. Erbyn hyn, mae ciw yn cael ei enwi yn fwriadol iawn. Mae'n llinell oherwydd bod rhywfaint tegwch iddo. Hawl? Byddai'n fath o sugno os ydych wedi cyrraedd yno gyntaf yn y Storfa Apple ond eich bod yn effeithiol yw'r bottommost hambwrdd oherwydd bod y gweithwyr Apple, yna pop y person olaf sy'n got mewn gwirionedd yn unol. Felly staciau a ciwiau, er bod swyddogaethol eu bod yn fath o yr same-- 'i' jyst y casgliad hwn o adnoddau sy'n mynd i dyfu a shrink-- mae ' yr agwedd tegwch iddo, o leiaf yn y byd go iawn, lle gwneir unrhyw waith rydych yn ymarfer yn sylfaenol wahanol. A stack-- ciw rather-- dywedwyd ei fod wedi dau gweithrediadau: n ciw a d ciw. Neu gallwch eu ffonio unrhyw nifer o bethau. Ond 'ch jyst eisiau ei gipio y syniad bod un yn cael ei ychwanegu ac mae un yn y pen draw tynnu. Yn awr o dan y cwfl, mae'r pentwr a gellid ciw eu gweithredu sut? Ni fyddwn yn mynd i mewn i'r cod oherwydd y lefel uwch syniad yn fath o yn fwy amlwg. Hynny yw, beth mae pobl yn ei wneud? Os Fi yw'r person cyntaf yn y Apple Storiwch a dyma'r drws ffrynt, eich bod yn gwybod, yr wyf i'n mynd i sefyll yma. A'r person nesaf mynd i sefyll yma. A'r person nesaf mynd i sefyll yma. Felly pa strwythur data cynnig ei hun i ciw? GYNULLEIDFA: A ciw. DAVID Malan: Wel, ciw. Cadarn. Beth arall? GYNULLEIDFA: Mae rhestr cysylltiedig. DAVID Malan: A cysylltiedig rhestrwch y gallech rhoi ar waith. A rhestr cysylltiedig yn braf oherwydd wedyn gall dyfu fympwyol o amser yn hytrach na i gael rhywfaint o nifer a bennwyd o bobl yn y siop. Ond efallai yn nifer penodedig o leoedd yn gyfreithlon. Achos os mai dim ond yn hoffi 20 iPhones ar y diwrnod cyntaf, efallai maent ond angen amrywiaeth o faint 20 i gynrychioli y ciw, sy'n dim ond i ddweud yn awr ar ôl i ni ddechrau siarad am y problemau ar lefel uwch, gallwch ei roi ar waith mewn unrhyw nifer o ffyrdd. Ac mae pob tebyg dim ond yn mynd i fod yn fasnach i ffwrdd yn y gofod ac amser neu dim ond yn eich cymhlethdod cod eich hun. Beth am stac? Wel, pentwr, rydym wedi gweld yn rhy Gallai dim ond fod yn hambyrddau hyn. A allech chi roi hyn ar waith arae. Ond ar ryw adeg, os ydych yn defnyddio amrywiaeth, beth sy'n mynd i ddigwydd i'r hambyrddau ydych yn ceisio ei roi i lawr? Mae pob hawl. Rydych yn unig yn mynd i yn gallu mynd mor uchel. Ac yr wyf yn meddwl yn Mather eu bod yn cilfachog mewn gwirionedd yn yr agoriad. Felly, yn wir, mae bron yn fel Mather yn defnyddio amrywiaeth o faint penodol, oherwydd eich bod dim ond ffitio cymaint o hambyrddau yn y agoriad yn y wal i lawr yn is na'r pengliniau pobl. Ac felly a allai fod yn Dywedodd i fod yn array, ond gallem yn sicr yn gweithredu hynny yn fwy cyffredinol gyda rhestr cysylltiedig. Wel, beth am strwythur data arall? Gadewch i mi dynnu i fyny un arall weledol yma. Rhywbeth fel beth am yr un yma? Pam y gallai fod yn ddefnyddiol i beidio â chael rhywbeth mor ffansi fel trie, a oedd gwelsom roedd gan y rhain nodau eang iawn, pob un ohonynt yn mewn arae? Ond beth os ydym yn ei wneud rhywbeth mwy yn syml, fel hen goeden deulu ysgolion, mae pob un o'i nodau yma yn unig storio rhif. Yn lle enw neu un o ddisgynyddion yn unig storio rhif fel hyn. Wel, mae'r jargon a ddefnyddiwn yng strwythurau data yn y ddwy ceisiau a choed, lle mae trie, unwaith eto, yn dim ond un y mae ei nodau yn arrays, yn dal i fod yr hyn yr ydych efallai defnyddio o radd ysgol pan fyddwch yn gwneud teulu dail tree-- ac mae'r gwraidd y goeden a phlant yr rhieni a brodyr a chwiorydd o hynny. Ac efallai y byddwn yn gweithredu coeden, er enghraifft, mor syml fel hyn. Mae coeden, os yw'n fel nod, un o cylchoedd hyn sydd â rhif, nid yw'n mynd i gael un pwyntydd, ond dau. A chyn gynted ag y byddwch yn ychwanegu ail pwyntydd, rydych Gall mewn gwirionedd yn awr yn gwneud math o ddata dau ddimensiwn strwythurau yn y cof. Mae llawer fel dau ddimensiwn array, gallwch yn cael y math o dau-ddimensiwn rhestrau cysylltiedig ond mae rhai sy'n dilyn patrwm lle nad oes cylchoedd. Mae'n wir goeden gydag un ffordd nain neu daid i fyny yma ac yna rhai rhieni a phlant a wyrion a gor-wyrion. ac yn y blaen. Ond yr hyn sy'n wir yn daclus am hyn hefyd, dim ond i chi canfod gydag ychydig o god, recursion galw yn ôl o dro yn ôl, lle byddwch yn ysgrifennu swyddogaeth sy'n galw ei hun. Mae hwn yn gyfle hyfryd i weithredu rhywbeth fel recursion, gan fod yn ystyried hyn. Mae hwn yn goeden. Ac rwyf wedi bod ychydig o rhefrol â sut Rhoddais y cyfanrifau i'r stryd. Cymaint felly fel bod ganddi arbennig name-- coeden chwiliad deuaidd. Nawr rydym wedi clywed am deuaidd chwilio, ond gallwch chi gweithio tuag yn ôl o'r enw peth hwn? Beth yw'r patrwm o sut yr wyf yn mewnosodir y cyfanrifau i mewn i goeden hon? Dyw hi ddim yn fympwyol. Mae rhywfaint o batrwm. Yeah. GYNULLEIDFA: rhai llai ar y chwith. DAVID Malan: Yeah. Rhai llai ar y chwith. Rhai mwy ar y dde. Fel bod ddatganiad cywir yn rhiant yn fwy na'r ei phlentyn ar y chwith, ond yn llai na ei phlentyn yn iawn. A bod ei ben ei hun hyd yn oed yn diffiniad llafar recursive oherwydd gallwch wneud cais bod un rhesymeg i bob nod ac mae'n dim ond gwaelodion allan, mae achos sylfaenol os ydych yn fydd, pan fyddwch yn taro un o y dail, fel petai, lle mae absenoldeb nad oes gan blant ymhellach. Nawr sut y gallech ddod o hyd i'r rhif 44? Byddech yn dechrau yn y gwraidd ac yn dweud, EM. 55 Nid yw 44 Felly ydw i eisiau mynd hawl neu ydw i am fynd ar ôl? Wel, yn amlwg ydych am fynd chwith. Ac felly mae'n union fel y ffôn Enghraifft lyfr chwilio deuaidd yn fwy cyffredinol. Ond rydym yn ei weithredu Erbyn hyn ychydig yn fwy ddeinamig nag y gallai amrywiaeth ganiatáu. Ac yn wir, os ydych am edrych yn y cod, ar yr olwg gyntaf yn siwr. Mae'n edrych fel criw cyfan o linellau. Ond mae'n hyfryd syml. Os ydych am i weithredu swyddogaeth Gelwir chwilio sydd â'r diben mewn bywyd yw i chwilio am werth fel n, yn gyfanrif, ac rydych yn pasio mewn un pointer-- pwyntydd at y nôd y gwreiddiau, yn hytrach, o'r goeden o ba gallwch gael mynediad i popeth arall, yn sylwi pa mor ddirwystr gallwch weithredu'r rhesymeg. Os yw coeden yn null, yn amlwg nid yw'n yno. Gadewch i jyst yn dychwelyd ffug. Hawl? Os ydych yn ei roi dim byd, does dim byd yno. Else, os n yn llai na arrow coed n-- bellach saeth n, cofio gwnaethom gyflwyno super yn fyr y diwrnod o'r blaen, ac mai dim ond yn golygu de-gyfeirio y pwyntydd ac edrych ar y cae a elwir yn n. Felly, mae'n golygu mynd yno ac edrych ar y cae o'r enw n. Felly os n, mae'r gwerth a roddir i chi, yn llai na gwerth yn y cyfanrif coed, ble ydych chi eisiau mynd? Ar y chwith. Felly, yn sylwi ar y recursion. Im 'yn returning-- ddim yn wir. Ddim yn ffug. Dw i'n dychwelyd beth bynnag yr ateb yn dod o alwad i mi fy hun, gan fynd heibio mae n unwaith eto, sydd yn ddiangen, ond beth sydd ychydig yn wahanol nawr? Sut ydw i'n gwneud y broblem yn llai? Im 'yn pasio i mewn fel yr ail ddadl, nid wraidd y goeden, ond mae'r plentyn chwith yn yr achos hwn. Felly rwy'n pasio yn y plentyn chwith. Yn y cyfamser, os n yn fwy na y nod ar hyn o bryd rwy'n edrych ar, Rwy'n chwilio yr ochr dde. Else, os nad yw'r goeden yn null, ac os nad yw'r elfen sydd i'r chwith ac nid yw ar y dde, yr hyn sy'n rhyfeddol yn wir? Mewn gwirionedd rydym wedi dod o hyd y nod yn cwestiwn, ac felly rydym yn dychwelyd yn wir. Felly, rydym newydd crafu'r wyneb Erbyn hyn mae rhai o'r strwythurau data. Mewn problem yn gosod pum wnewch chi helpu archwilio'r rhain ymhellach eto, a byddwch yn cael eich dyluniad dewis o sut i fynd o'i chwmpas hi. Beth hoffwn i ddod i'r casgliad ar yn unig yw ail teaser 30 o'r hyn sy'n aros am yr wythnos nesaf a thu hwnt. Wrth i ni begin-- diolch byth gallech chi think-- ein trosglwyddo yn araf o fyd C ac is Manylion gweithredu lefel, i'r byd lle y gallwn eu cymryd i yn ganiataol bod rhywun arall wedi o'r diwedd rhoi ar waith y data hyn strwythurau i ni, a byddwn yn dechrau deall y byd go iawn yn golygu o weithredu rhaglenni ar y we a gwefannau yn fwy cyffredinol a hefyd yr union diogelwch goblygiadau mai rydym wedi dim ond dechrau crafu wyneb. Dyma beth disgwyl i ni yn y dyddiau sydd i ddod. [VIDEO Playback] -He Ddaeth gyda'r neges, â phrotocol ei holl hun. Daeth i fyd o greulon waliau tân, llwybryddion yn ddidaro, a pheryglon llawer gwaeth na marwolaeth. Mae'n gyflym. Mae'n gryf. Mae'n TCP / IP, ac mae ganddo eich cyfeiriad. "Warriors y Net." [DIWEDD VIDEO Playback] DAVID Malan: Yn dod yr wythnos nesaf. Cewch eich gweld o hynny. [VIDEO Playback] -ac Yn awr, "Thoughts Deep" gan Daven Farnham. -David Bob amser yn dechrau darlithoedd gyda, "Mae pob hawl." Pam na wnewch chi, "Dyma y datrysiad i broblem set yr wythnos hon " neu "Rydym yn rhoi pob un ohonoch yn A?" [Chwerthin] [DIWEDD VIDEO Playback]