1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [CHWARAE CERDDORIAETH] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: Mae hyn yn CS50. 5 00:00:14,010 --> 00:00:18,090 Ac mae hyn yn yn y dechrau a'r end-- fel literally-- bron diwedd 6 00:00:18,090 --> 00:00:18,825 o wythnos chwech. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Roeddwn i'n meddwl y byddwn i'n rhannu ychydig bach o ffeithiau hwyl. 9 00:00:22,640 --> 00:00:25,370 Rydw i wedi tynnu hyn i fyny o gosod data semester gorffennol. 10 00:00:25,370 --> 00:00:29,710 Efallai y cofiwch ein bod yn gofyn i chi ar bob Ffurflen set p os ydych wedi gwylio ar-lein 11 00:00:29,710 --> 00:00:31,580 neu os ydych wedi mynychu yn bersonol. 12 00:00:31,580 --> 00:00:33,020 A dyma yw'r data. 13 00:00:33,020 --> 00:00:34,710 Felly heddiw yn llawer iawn rhagweladwy. 14 00:00:34,710 --> 00:00:37,126 Ond rydym yn awyddus i dreulio ychydig o amser gyda chi serch hynny. 15 00:00:37,126 --> 00:00:40,599 Hoffai unrhyw un dyfalu pam mae hyn graff mor jaggy, i fyny i lawr, i fyny i lawr, 16 00:00:40,599 --> 00:00:41,265 mor gyson? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Beth yw ystyr pob un o'r copaon a chafnau gynrychioli? 19 00:00:45,130 --> 00:00:46,005 >> GYNULLEIDFA: [Anghlywadwy] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: Yn wir. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Ac yn fwy amusingly, duw a'n gwaredo, rydym yn cynnal un ddarlith ar ddydd Gwener 24 00:00:55,480 --> 00:00:58,960 ar ddechrau'r semester, dyna beth yr ydym yn ei weld yn digwydd. 25 00:00:58,960 --> 00:01:03,430 Felly heddiw, rydym yn cymryd rhan mewn ychydig mwy am strwythurau data. 26 00:01:03,430 --> 00:01:06,660 Ac i roi mwy o solid i chi model meddwl ar gyfer problemau yn bump, 27 00:01:06,660 --> 00:01:07,450 sydd bellach allan. 28 00:01:07,450 --> 00:01:10,817 Gamsillafu, yr hwn, rydym annhymerus law ffeil testun i chi rai 100,000 29 00:01:10,817 --> 00:01:12,650 yn ogystal â geiriau Saesneg, ac ydych yn mynd i gael 30 00:01:12,650 --> 00:01:17,770 at chyfrif i maes sut i'w llwytho cleverly i mewn i gof, i mewn i RAM, gan ddefnyddio rhywfaint o ddata 31 00:01:17,770 --> 00:01:19,330 strwythur eich dewis. 32 00:01:19,330 --> 00:01:22,470 >> Nawr gallai un strwythur data o'r fath fod, ond yn ôl pob tebyg ni ddylai fod, 33 00:01:22,470 --> 00:01:25,630 y rhestr gysylltiedig eithaf syml, yr ydym yn cyflwyno tro diwethaf. 34 00:01:25,630 --> 00:01:29,220 A rhestr gysylltiedig o leiaf un fantais dros arae. 35 00:01:29,220 --> 00:01:32,096 Beth sydd un fantais o rhestr cysylltiedig dadlau? 36 00:01:32,096 --> 00:01:32,950 >> GYNULLEIDFA: Mewnosod. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Mewnosod. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Beth ydych chi'n ei olygu wrth hynny? 40 00:01:35,196 --> 00:01:37,872 >> GYNULLEIDFA: Unrhyw le ar hyd y rhestr [Anghlywadwy]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Da. 42 00:01:38,770 --> 00:01:42,090 Felly gallwch mewnosod elfen lle bynnag ydych am yng nghanol y rhestr 43 00:01:42,090 --> 00:01:45,490 heb orfod siffrwd unrhyw beth, hynny daethom i'r casgliad, yn ein didoli 44 00:01:45,490 --> 00:01:47,630 trafodaethau, nid yw o reidrwydd yn beth da, 45 00:01:47,630 --> 00:01:51,200 oherwydd mae'n cymryd amser i symud mewn gwirionedd pob un o'r bobl y rhai chwith neu i'r dde. 46 00:01:51,200 --> 00:01:55,540 Ac felly gyda rhestr cysylltiedig, gallwch jyst dyrannu gyda malloc, mae nod newydd, 47 00:01:55,540 --> 00:01:58,385 ac yna diweddaru un neu ddau o pointers-- dau, tri gweithrediadau max-- 48 00:01:58,385 --> 00:02:01,480 ac rydym yn gallu slotio rhywun mewn unrhyw le i mewn i restr. 49 00:02:01,480 --> 00:02:03,550 >> Beth arall oedd yn fanteisiol am restr cysylltiedig? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Yeah? 52 00:02:05,659 --> 00:02:06,534 >> GYNULLEIDFA: [Anghlywadwy] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Malan: Perffaith. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perffaith. 57 00:02:11,090 --> 00:02:12,070 Mae'n wirioneddol ddeinamig. 58 00:02:12,070 --> 00:02:15,100 Ac nad ydych yn cyflawni, ymlaen llaw, i ryw faint sefydlog 59 00:02:15,100 --> 00:02:18,750 darn o gof, fel y byddech yn cael i gydag amrywiaeth, y upside o'r rhain 60 00:02:18,750 --> 00:02:22,455 yw y gallwch ddyrannu nodau yn unig ar galw a thrwy hynny gan ddefnyddio dim ond cymaint o le 61 00:02:22,455 --> 00:02:23,330 wrth i chi ei angen mewn gwirionedd. 62 00:02:23,330 --> 00:02:26,830 Ar y llaw arall gydag amrywiaeth, gallech chi yn ddamweiniol yn dyrannu digon o. 63 00:02:26,830 --> 00:02:28,871 Ac yna mae'n dim ond yn mynd i fod yn boen yn y gwddf 64 00:02:28,871 --> 00:02:32,440 i ailddyrannu amrywiaeth mwy newydd, copïo popeth drosodd, rhad ac am ddim yr hen array, 65 00:02:32,440 --> 00:02:33,990 ac yna symud am eich busnes. 66 00:02:33,990 --> 00:02:37,479 Neu yn waeth, efallai y byddwch yn dyrannu ffordd mwy o gof nag yr ydych ei angen mewn gwirionedd, 67 00:02:37,479 --> 00:02:40,520 ac felly rydych yn mynd i gael iawn prin eu poblogaeth array, fel petai. 68 00:02:40,520 --> 00:02:44,350 >> Felly mae rhestr cysylltiedig yn rhoi hyn i chi manteision o egni a hyblygrwydd 69 00:02:44,350 --> 00:02:46,080 gyda fewnosodiadau a dileadau. 70 00:02:46,080 --> 00:02:48,000 Ond yn sicr rhaid cael pris a dalwyd. 71 00:02:48,000 --> 00:02:50,000 Yn wir, un o'r themâu archwilio ar y cwis sero 72 00:02:50,000 --> 00:02:52,430 Roedd un neu ddau o'r cyfaddawdau rydym wedi gweld hyd yn hyn. 73 00:02:52,430 --> 00:02:56,161 Felly beth yw pris a dalwyd neu Anfantais o restr cysylltiedig? 74 00:02:56,161 --> 00:02:56,660 Yeah. 75 00:02:56,660 --> 00:02:57,560 >> GYNULLEIDFA: Dim mynediad ar hap. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: Dim mynediad ar hap. 77 00:02:58,809 --> 00:02:59,540 Ond sy'n gofalu? 78 00:02:59,540 --> 00:03:01,546 Nid yw mynediad ar hap yn swnio'n gymhellol. 79 00:03:01,546 --> 00:03:02,421 >> GYNULLEIDFA: [Anghlywadwy] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Yn union. 82 00:03:05,740 --> 00:03:07,580 Os ydych am gael a algorithm-- penodol 83 00:03:07,580 --> 00:03:10,170 a gadewch i mi mewn gwirionedd yn cynnig chwiliad deuaidd yn arbennig, a oedd yn 84 00:03:10,170 --> 00:03:12,600 yn un rydym wedi defnyddio tipyn o bit-- os nad oes gennych fynediad ar hap, 85 00:03:12,600 --> 00:03:15,516 Ni allwch wneud hynny rhifyddeg syml o ddod o hyd fel yr elfen canol 86 00:03:15,516 --> 00:03:16,530 ac yn neidio i'r dde i iddo. 87 00:03:16,530 --> 00:03:20,239 Yn lle hynny rhaid i chi ddechrau ar y cyntaf elfen a'r llinol chwilio o chwith 88 00:03:20,239 --> 00:03:22,780 i'r dde os ydych am ddod o hyd y canol neu unrhyw elfen arall. 89 00:03:22,780 --> 00:03:24,410 >> GYNULLEIDFA: Mae'n fwy na thebyg yn cymryd mwy o gof. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: Yn cymryd mwy o gof. 91 00:03:25,040 --> 00:03:27,464 Ble yw hynny'n ychwanegol gost yn dod o mewn cof? 92 00:03:27,464 --> 00:03:28,339 >> GYNULLEIDFA: [Anghlywadwy] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Yn union. 95 00:03:33,440 --> 00:03:35,679 Yn yr achos yma, rydym yn cael rhestr cysylltiedig ar gyfer chyfanrifau, 96 00:03:35,679 --> 00:03:37,470 ac eto rydym yn dyblu y swm o gof 97 00:03:37,470 --> 00:03:39,680 mae angen drwy hefyd storio awgrymiadau hyn. 98 00:03:39,680 --> 00:03:42,090 Nawr llai o llawer fawr fel eich structs cael mwy o faint 99 00:03:42,090 --> 00:03:45,320 ac rydych yn storio nad oedd nifer ond efallai yn fyfyriwr neu ryw wrthrych arall. 100 00:03:45,320 --> 00:03:46,880 Ond y pwynt yn sicr yn parhau i fod. 101 00:03:46,880 --> 00:03:49,421 Ac felly mae nifer o'r gweithrediadau ar restrau cysylltiedig eu galw 102 00:03:49,421 --> 00:03:50,570 Roedd O fawr o llinellol n--. 103 00:03:50,570 --> 00:03:54,730 Pethau fel gosod neu chwilio neu ddileu rhag ofn elfen 104 00:03:54,730 --> 00:03:57,720 yn digwydd bod ar ddiwedd y y rhestr boed yn didoli neu beidio. 105 00:03:57,720 --> 00:04:01,167 >> Weithiau, efallai y byddwch yn cael lwcus ac yn terfynau felly yn is ar y gweithrediadau hyn 106 00:04:01,167 --> 00:04:04,250 Gallai hefyd fod yn amser gyson os ydych chi'n bob amser yn edrych ar yr elfen gyntaf, 107 00:04:04,250 --> 00:04:05,070 er enghraifft. 108 00:04:05,070 --> 00:04:09,360 Ond yn y pen draw, rydym yn addo i gyrraedd y greal sanctaidd 109 00:04:09,360 --> 00:04:12,630 o strwythurau data, neu rhywfaint ohono brasamcan, 110 00:04:12,630 --> 00:04:14,290 drwy gyfrwng amser cyson. 111 00:04:14,290 --> 00:04:17,579 Gallwn ddod o hyd elfennau neu ychwanegu elfennau neu ddileu elfennau o restr? 112 00:04:17,579 --> 00:04:19,059 Cawn weld yn weddol fuan. 113 00:04:19,059 --> 00:04:21,100 Ac mae'n troi allan bod un o'r mecanweithiau rydym yn 114 00:04:21,100 --> 00:04:23,464 mynd i ddechrau i ddefnyddio heddiw, defnydd blynyddol mewn p osodwyd pump, 115 00:04:23,464 --> 00:04:24,630 mewn gwirionedd yn eithaf cyfarwydd. 116 00:04:24,630 --> 00:04:27,430 Er enghraifft, os yw hyn yn griw o lyfrau arholiad, pob un ohonynt 117 00:04:27,430 --> 00:04:29,660 Mae myfyriwr yn gyntaf enwi ac enw olaf arno, 118 00:04:29,660 --> 00:04:31,820 ac yr wyf yn eu casglu oddi wrth ar ddiwedd arholiad, 119 00:04:31,820 --> 00:04:33,746 ac maen nhw i gyd 'n bert llawer mewn trefn ar hap, 120 00:04:33,746 --> 00:04:36,370 ac rydym am fynd ati i ddidoli arholiadau hyn fel y unwaith yn graddio 121 00:04:36,370 --> 00:04:38,661 'i' jyst yn llawer haws ac yn gyflymach i law yn ôl allan 122 00:04:38,661 --> 00:04:40,030 i fyfyrwyr yn nhrefn yr wyddor. 123 00:04:40,030 --> 00:04:42,770 Beth fyddai eich greddf yn am bentwr o arholiadau fel hyn? 124 00:04:42,770 --> 00:04:45,019 >> Wel, os ydych chi fel fi, rydych Efallai y gwelwch fod hyn yn m, 125 00:04:45,019 --> 00:04:48,505 felly dw i'n mynd i fath o roi hyn mewn, os yw hyn yn fy tabl neu fy lawr lle 126 00:04:48,505 --> 00:04:50,650 Im 'yn lledaenu pethau out-- neu fy array really-- 127 00:04:50,650 --> 00:04:52,210 Efallai fy mod yn rhoi pob un o'r Ms mewn 'na. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Dyma A. Felly, yr wyf efallai rhowch y Fel dros yma. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Dyma A. arall dwi'n mynd i roi hynny dros yma. 132 00:04:57,980 --> 00:05:02,490 Dyma Z. Dyma M. arall Ac felly Efallai y byddwn yn dechrau gwneud pentyrrau fel hyn. 133 00:05:02,490 --> 00:05:06,620 Ac yna efallai byddwn i'n mynd yn nes ymlaen a math o nitpicky ly-iawn fath 134 00:05:06,620 --> 00:05:07,710 y pentyrrau unigol. 135 00:05:07,710 --> 00:05:11,300 Ond y pwynt yw y byddwn yn edrych yn y mewnbwn fy mod handed 136 00:05:11,300 --> 00:05:14,016 a byddwn yn gwneud rhywfaint o gyfrifo yn seiliedig ar fewnbwn y penderfyniad. 137 00:05:14,016 --> 00:05:15,640 Os yw'n dechrau gyda A, yn ei roi dros yno. 138 00:05:15,640 --> 00:05:18,980 Os yw'n dechrau gyda Z, yn ei roi dros yno, a phopeth yn y canol. 139 00:05:18,980 --> 00:05:22,730 >> Felly, mae hyn yn dechneg sy'n a adwaenir yn gyffredinol fel hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 sydd yn gyffredinol yn golygu cymryd fel mewnbwn a defnyddio'r mewnbwn i gyfrifo 141 00:05:26,550 --> 00:05:30,940 gwerth, ar y cyfan mae nifer, a bod rhif yw'r mynegai i mewn i storio 142 00:05:30,940 --> 00:05:32,260 cynhwysydd, fel arae. 143 00:05:32,260 --> 00:05:35,490 Felly, mewn geiriau eraill, efallai y byddwn yn cael swyddogaeth hash, fel yr wyf yn ei wneud yn fy mhen, 144 00:05:35,490 --> 00:05:37,940 os wyf yn gweld rhywun yn enw sy'n dechrau gyda A, 145 00:05:37,940 --> 00:05:40,190 Rydw i'n mynd i fapio hynny i ddim yn fy mhen. 146 00:05:40,190 --> 00:05:44,160 Ac os wyf yn gweld rhywun sydd â Z, rwy'n mynd i fapio hynny i 25 yn fy mhen 147 00:05:44,160 --> 00:05:46,220 ac wedyn yn rhoi hynny ar y mwyaf pentwr diwethaf. 148 00:05:46,220 --> 00:05:50,990 >> Yn awr, os ydych yn meddwl am nad yw fy ymennydd ond gallai rhaglen C, pa rifau 149 00:05:50,990 --> 00:05:53,170 ydych yn dibynnu ar i gyflawni hynny un canlyniad? 150 00:05:53,170 --> 00:05:55,594 Mewn geiriau eraill, os ydych yn Roedd gan y cymeriad ASCII A, 151 00:05:55,594 --> 00:05:57,510 sut ydych chi'n penderfynu pa bwced i'w roi mewn? 152 00:05:57,510 --> 00:05:59,801 Mae'n debygol nad ydych eisiau roi mewn bwced 65, a oedd yn 153 00:05:59,801 --> 00:06:01,840 Byddai fod yn debyg dros yno heb reswm da. 154 00:06:01,840 --> 00:06:04,320 Ble ydych chi eisiau rhoi A o ran ei werth ASCII? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Ble ydych chi am ei wneud at ei ASCII gwerth i ddod i fyny gyda bwced callach 157 00:06:08,920 --> 00:06:09,480 i'w roi i mewn? 158 00:06:09,480 --> 00:06:10,206 >> GYNULLEIDFA: Minws A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Yeah. 160 00:06:10,956 --> 00:06:13,190 Felly minws A neu finws benodol 65 os yw'n 161 00:06:13,190 --> 00:06:18,240 cyfalaf A. Neu 98 os mae'n llythrennau bach a a. 162 00:06:18,240 --> 00:06:21,300 Ac felly byddai hynny'n caniatáu i ni, iawn yn syml ac yn rhifyddol iawn, 163 00:06:21,300 --> 00:06:23,260 rhoi rhywbeth i mewn i fwced fel 'na. 164 00:06:23,260 --> 00:06:26,010 Felly, mae'n troi allan yr ydym yn ei wneud mewn gwirionedd hwn yn ogystal hyd yn oed gyda'r cwisiau. 165 00:06:26,010 --> 00:06:29,051 >> Felly, efallai y byddwch yn cofio i chi cylch eich addysgu gyd yn enw ar y clawr. 166 00:06:29,051 --> 00:06:32,270 Ac enwau y TF yn cael eu trefnu i mewn i colofnau hyn yn nhrefn yr wyddor, 167 00:06:32,270 --> 00:06:34,400 yn dda, credwch neu beidio, pan fydd pob un o'r 80 a mwy o ohonom 168 00:06:34,400 --> 00:06:37,800 at ei gilydd y noson o'r blaen i radd, y cam olaf yn ein proses graddio 169 00:06:37,800 --> 00:06:41,830 yw hash y cwisiau i mewn i mawr gofod llawr yn y [Anghlywadwy] 170 00:06:41,830 --> 00:06:45,110 ac i osod cwisiau pawb allan yn union yr nhrefn eu TF yn 171 00:06:45,110 --> 00:06:47,700 enwau ar y clawr, oherwydd Yna, mae'n llawer haws i ni 172 00:06:47,700 --> 00:06:51,290 i chwilio drwy fod defnyddio llinellol chwilio neu ryw fath o glyfrwch 173 00:06:51,290 --> 00:06:54,050 am TF i ddod o hyd ef neu cwisiau ei myfyrwyr. 174 00:06:54,050 --> 00:06:56,060 >> Felly, y syniad hwn o stwnsio y byddwch yn gweld yn 175 00:06:56,060 --> 00:07:00,520 eithaf pwerus yn eithaf mewn gwirionedd gyffredin a sythweledol iawn, 176 00:07:00,520 --> 00:07:03,000 yn debyg o bosibl rhannu a Roedd Conquer yn wythnos sero. 177 00:07:03,000 --> 00:07:05,250 I ymlaen yn gyflym at y hackathon cwpl o flynyddoedd yn ôl. 178 00:07:05,250 --> 00:07:08,040 Roedd hyn Zamyla a chwpl o myfyrwyr cyfarchiad staff eraill 179 00:07:08,040 --> 00:07:09,030 fel y maent yn dod i mewn. 180 00:07:09,030 --> 00:07:12,680 Ac rydym wedi cael criw cyfan o plygu tablau yno gyda tagiau enw. 181 00:07:12,680 --> 00:07:15,380 Ac roeddem wedi y tagiau enw a drefnwyd â thebyg y Fel dros yno 182 00:07:15,380 --> 00:07:16,690 ac mae'r ZS dros yno. 183 00:07:16,690 --> 00:07:20,350 Ac felly un o'r TFS glyfar iawn ysgrifennodd hyn gan fod y cyfarwyddiadau 184 00:07:20,350 --> 00:07:21,030 ar gyfer y diwrnod. 185 00:07:21,030 --> 00:07:24,480 Ac yn wythnos 12 o'r semester hwn i gyd yn gwneud synnwyr perffaith ac mae pawb 186 00:07:24,480 --> 00:07:25,310 yn gwybod beth i'w wneud. 187 00:07:25,310 --> 00:07:27,900 Ond ar unrhyw adeg eich bod wedi ciw yn yr un modd, 188 00:07:27,900 --> 00:07:30,272 eich bod yn gweithredu'r yr un syniad o hash. 189 00:07:30,272 --> 00:07:31,730 Felly gadewch i ni ffurfioli ei fod ychydig bach. 190 00:07:31,730 --> 00:07:32,890 Dyma arae. 191 00:07:32,890 --> 00:07:36,820 Mae wedi tynnu i fod ychydig yn eang yn unig i ddarlunio, yn weledol, 192 00:07:36,820 --> 00:07:38,920 y gallem roi llinynnau mewn rhywbeth fel hyn. 193 00:07:38,920 --> 00:07:41,970 Ac mae amrywiaeth hwn yw yn amlwg o faint 26 cyfanswm. 194 00:07:41,970 --> 00:07:43,935 Ac yn cael ei alw'n y peth tabl fympwyol. 195 00:07:43,935 --> 00:07:48,930 Ond mae hyn yn unig yw rendition artist o'r hyn a allai tabl hash fod. 196 00:07:48,930 --> 00:07:52,799 >> Felly tabl hash nawr yn mynd i fod yn strwythur data lefel uwch. 197 00:07:52,799 --> 00:07:54,840 Ar ddiwedd y dydd rydym chi ar fin i weld bod chi 198 00:07:54,840 --> 00:07:58,700 Gall gweithredu tabl hash, a oedd yn debyg iawn i'r llinell siec i mewn 199 00:07:58,700 --> 00:08:02,059 mewn hackathon llawer fel hyn tabl a ddefnyddir ar gyfer didoli llyfrau arholiad. 200 00:08:02,059 --> 00:08:03,850 Ond tabl hash yn fath o lefel uchel hon 201 00:08:03,850 --> 00:08:08,250 cysyniad a allai ddefnyddio amrywiaeth o dan y cwfl i'w weithredu, 202 00:08:08,250 --> 00:08:11,890 neu gallai ddefnyddio rhestr hyd, neu hyd yn oed efallai rhai strwythurau data arall. 203 00:08:11,890 --> 00:08:15,590 Ac yn awr dyna cymryd theme-- mae rhai o'r cynhwysion sylfaenol hyn 204 00:08:15,590 --> 00:08:18,310 fel amrywiaeth ac adeilad hwn bloc nawr o restr hyd 205 00:08:18,310 --> 00:08:21,740 a gweld beth arall y gallwn adeiladu ar ben hynny, fel cynhwysion 206 00:08:21,740 --> 00:08:26,550 i mewn rysáit, gan wneud mwy a mwy canlyniadau terfynol yn ddiddorol a defnyddiol. 207 00:08:26,550 --> 00:08:28,680 >> Felly, gyda y tabl hash gallem ei roi ar waith 208 00:08:28,680 --> 00:08:32,540 er cof ddarluniadol fel hyn, ond sut y gallai fod mewn gwirionedd yn cael ei godio i fyny? 209 00:08:32,540 --> 00:08:33,789 Wel, efallai mor syml yw hyn. 210 00:08:33,789 --> 00:08:38,270 Os GALLU ym mhob gapiau, yn unig rhywfaint constant-- er enghraifft 26, 211 00:08:38,270 --> 00:08:42,030 am 26 llythrennau'r alphabet-- Efallai y byddwn yn galw fy mwrdd amrywiol, 212 00:08:42,030 --> 00:08:45,630 ac efallai y byddwn yn honni bod fy mod i'n mynd i rhoi sêr char i mewn 'na, neu linyn. 213 00:08:45,630 --> 00:08:49,880 Felly mae'n mor syml â hyn os ydych yn awyddus i weithredu tabl hash. 214 00:08:49,880 --> 00:08:51,490 Ac eto, mae hyn yn wir yn unig arae. 215 00:08:51,490 --> 00:08:53,198 Ond unwaith eto, mae hash tabl yn awr yr hyn yr ydym chi helpu 216 00:08:53,198 --> 00:08:57,470 ffoniwch math data haniaethol bod yn unig math o haenau cysyniadol ar ei ben 217 00:08:57,470 --> 00:09:00,780 o rywbeth mwy cyffredin Bellach hoffi arae. 218 00:09:00,780 --> 00:09:02,960 >> Nawr, sut ydyn ni'n mynd am ddatrys problemau? 219 00:09:02,960 --> 00:09:06,980 Wel, yn gynharach cefais y moethus o gael digon o le tabl yma 220 00:09:06,980 --> 00:09:09,460 fel y gallwn i roi'r cwisiau unrhyw le roeddwn i eisiau. 221 00:09:09,460 --> 00:09:10,620 Felly efallai Fel ewch yma. 222 00:09:10,620 --> 00:09:12,100 Gallai ZS ewch yma. 223 00:09:12,100 --> 00:09:13,230 Gallai Ms ewch yma. 224 00:09:13,230 --> 00:09:14,740 Ac yna roedd rhaid i mi ychydig o le ychwanegol. 225 00:09:14,740 --> 00:09:18,740 Ond mae hyn yn dipyn o hawl twyllo yn awr oherwydd y tabl hwn, os Fi 'n sylweddol 226 00:09:18,740 --> 00:09:22,720 yn meddwl am y peth fel amrywiaeth, yn unig mynd i fod o ryw faint sefydlog. 227 00:09:22,720 --> 00:09:25,380 >> Felly dechnegol, os wyf yn tynnu fyny cwis myfyriwr arall 228 00:09:25,380 --> 00:09:28,490 a gweld, oh, person hwn enw yn dechrau gyda A hefyd, 229 00:09:28,490 --> 00:09:30,980 Wyf yn fath o eisiau ei roi yno. 230 00:09:30,980 --> 00:09:34,740 Ond cyn gynted ag yr wyf yn ei roi yno, os y tabl hwn yn wir yn cynrychioli arae, 231 00:09:34,740 --> 00:09:37,840 Rydw i'n mynd i gael ei ddisodli nac clobbering pwy bynnag cwis myfyriwr hwn yw. 232 00:09:37,840 --> 00:09:38,340 Hawl? 233 00:09:38,340 --> 00:09:41,972 Os yw hyn yn arae, gall dim ond un peth mynd ym mhob un o gelloedd neu elfennau hyn. 234 00:09:41,972 --> 00:09:43,680 Ac felly yr wyf yn fath o gael i ddewis a dethol. 235 00:09:43,680 --> 00:09:45,735 >> Nawr gynharach wyf yn fath o twyllo ac yn gwneud hyn neu I 236 00:09:45,735 --> 00:09:47,526 jyst fath o pentyrru nhw uwchben ei gilydd. 237 00:09:47,526 --> 00:09:49,170 Ond nid yw hynny'n mynd i hedfan yn y cod. 238 00:09:49,170 --> 00:09:52,260 Felly, lle y gallwn i roi'r ail fyfyriwr y mae ei enw 239 00:09:52,260 --> 00:09:54,964 A yw os bydd yr holl wyf oedd yn hyn gofod tabl sydd ar gael? 240 00:09:54,964 --> 00:09:57,880 Ac yr wyf wedi defnyddio tri slotiau ac mae'n edrych fel mae dim ond ychydig o rai eraill. 241 00:09:57,880 --> 00:09:58,959 Beth allech chi ei wneud? 242 00:09:58,959 --> 00:09:59,834 GYNULLEIDFA: [Anghlywadwy] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Yeah. 245 00:10:01,315 --> 00:10:02,370 Efallai gadewch i ni jyst cadw pethau'n syml. 246 00:10:02,370 --> 00:10:02,660 Hawl? 247 00:10:02,660 --> 00:10:04,243 Nid yw'n cyd-fynd lle'r wyf am ei roi. 248 00:10:04,243 --> 00:10:07,450 Felly, dw i'n mynd i roi dechnegol lle byddai B yn mynd. 249 00:10:07,450 --> 00:10:09,932 Yn awr, wrth gwrs, rwy'n dechrau i beintio fy hun i mewn i gornel. 250 00:10:09,932 --> 00:10:11,890 Os byddaf yn mynd i fyfyriwr y mae ei enw mewn gwirionedd B, 251 00:10:11,890 --> 00:10:14,840 nawr B yn mynd i gael ei symud ychydig ymlaen, fel y gallai ddigwydd, yep, 252 00:10:14,840 --> 00:10:17,530 os yw hyn yn B, erbyn hyn mae'n rhaid iddo fynd yma. 253 00:10:17,530 --> 00:10:20,180 >> Ac felly mae hyn yn gyflym iawn Gallai fod yn broblematig, 254 00:10:20,180 --> 00:10:23,850 ond mae'n dechneg sydd mewn gwirionedd y cyfeirir ato fel llinellol treiddgar, 255 00:10:23,850 --> 00:10:26,650 lle 'ch jyst yn ystyried eich arae i fod ar hyd y llinell. 256 00:10:26,650 --> 00:10:29,680 A 'ch jyst fath o ymchwilio neu arolygu pob elfen ar gael 257 00:10:29,680 --> 00:10:31,360 chwilio am fan a'r lle sydd ar gael. 258 00:10:31,360 --> 00:10:34,010 A chyn gynted ag y byddwch yn dod o hyd un, ydych am ei ddefnyddio mewn 'na. 259 00:10:34,010 --> 00:10:38,390 >> Yn awr, y pris yn cael ei dalu yn awr am ateb hwn yw beth? 260 00:10:38,390 --> 00:10:41,300 Mae gennym amrywiaeth maint sefydlog, a pan fyddaf yn mewnosod enwau 261 00:10:41,300 --> 00:10:44,059 i mewn iddo, o leiaf i ddechrau, beth sydd yr amser yn rhedeg o mewnosod 262 00:10:44,059 --> 00:10:46,350 am roi i'r myfyrwyr ' cwisiau yn y bwcedi cywir? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O am yr hyn? 265 00:10:50,002 --> 00:10:51,147 >> GYNULLEIDFA: n. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: Clywais O fawr o n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Ddim yn wir. 269 00:10:54,300 --> 00:10:56,490 Ond byddwn yn tynnu ar wahân pam mewn dim ond eiliad. 270 00:10:56,490 --> 00:10:57,702 Beth arall y gallai fod? 271 00:10:57,702 --> 00:10:58,755 >> GYNULLEIDFA: [Anghlywadwy] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: A gadewch i mi wneud hynny ar eu golwg. 273 00:11:00,380 --> 00:11:04,720 Felly, mae'n debyg mai dyma'r llythyren S. 274 00:11:04,720 --> 00:11:05,604 >> GYNULLEIDFA: Mae'n un. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: Mae'n un. 276 00:11:06,520 --> 00:11:06,710 Hawl? 277 00:11:06,710 --> 00:11:08,950 Mae hwn yn array, a oedd yn golygu ein bod yn cael mynediad ar hap. 278 00:11:08,950 --> 00:11:11,790 Ac os ydym yn meddwl o hyn fel sero ac mae hyn fel 25, 279 00:11:11,790 --> 00:11:13,800 ac yr ydym yn sylweddoli hynny, oh, dyma fy mewnbwn S, 280 00:11:13,800 --> 00:11:16,350 Yn sicr, gallaf drosi S, cymeriad ASCII, 281 00:11:16,350 --> 00:11:18,540 i nifer cyfatebol rhwng sero a 25 282 00:11:18,540 --> 00:11:20,910 ac yna yn syth roi yn lle y mae'n perthyn. 283 00:11:20,910 --> 00:11:26,120 >> Ond wrth gwrs, cyn gynted ag y gallaf gael i'r ail berson pwy enw i yw A neu B neu C 284 00:11:26,120 --> 00:11:29,300 yn y pen draw, os ydw i wedi defnyddio'r llinol treiddgar fel fy ateb, 285 00:11:29,300 --> 00:11:31,360 yr amser yn rhedeg o mewnosod yn yr achos gwaethaf 286 00:11:31,360 --> 00:11:33,120 mewn gwirionedd yn mynd i ddatganoli i mewn i beth? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 A chlywais ef yma yn gywir yn gynnar. 289 00:11:36,045 --> 00:11:36,920 GYNULLEIDFA: [Anghlywadwy] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Felly mae'n n wir unwaith mae gennych set ddata digon mawr. 291 00:11:41,620 --> 00:11:44,410 Felly, ar y naill law, os eich amrywiaeth yn ddigon mawr 292 00:11:44,410 --> 00:11:48,287 a bod eich data yn ddigon prin, rydych cael y tro hwn cyson hardd. 293 00:11:48,287 --> 00:11:50,620 Ond cyn gynted ag y byddwch yn dechrau mynd yn fwy a mwy o elfennau, 294 00:11:50,620 --> 00:11:53,200 a dim ond yn ystadegol byddwch yn cael mwy o bobl gyda'r llythyr 295 00:11:53,200 --> 00:11:56,030 A gan fod eu henw neu y llythyr B, gallai o bosibl 296 00:11:56,030 --> 00:11:57,900 yn datganoli i mewn i rywbeth mwy llinol. 297 00:11:57,900 --> 00:11:59,640 Felly, ddim yn hollol berffaith. 298 00:11:59,640 --> 00:12:00,690 Gallai Felly, rydym yn ei wneud yn well? 299 00:12:00,690 --> 00:12:03,210 >> Wel, beth oedd ein ateb o'r blaen pan fyddwn 300 00:12:03,210 --> 00:12:06,820 am gael mwy deinamig nag rhywbeth fel arae ganiateir? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 GYNULLEIDFA: [Anghlywadwy] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Beth wnaethon ni gyflwyno? 304 00:12:10,030 --> 00:12:10,530 Yeah. 305 00:12:10,530 --> 00:12:11,430 Felly rhestr cysylltiedig. 306 00:12:11,430 --> 00:12:14,430 Wel, gadewch i ni weld beth a cysylltiedig Efallai y rhestr yn ei wneud i ni yn lle hynny. 307 00:12:14,430 --> 00:12:17,630 Wel, gadewch i mi gynnig ein bod yn tynnu y llun fel a ganlyn. 308 00:12:17,630 --> 00:12:19,620 Nawr mae hyn yn wahanol llun o enghraifft 309 00:12:19,620 --> 00:12:24,750 o destun gwahanol, mewn gwirionedd, bod mewn gwirionedd gan ddefnyddio amrywiaeth o maint 31. 310 00:12:24,750 --> 00:12:28,220 Ac awdur hwn yn syml Penderfynodd i hash llinynnau 311 00:12:28,220 --> 00:12:32,430 Nid yw yn seiliedig ar enwau y person, ond yn seiliedig ar eu birthdates. 312 00:12:32,430 --> 00:12:35,680 Heb ystyried y mis, maent yn cyfrifedig os ydych yn geni ar y cyntaf o fis 313 00:12:35,680 --> 00:12:39,580 neu y 31ain o fis, mae'r awdur Bydd hash yn seiliedig ar y gwerth hwnnw, 314 00:12:39,580 --> 00:12:44,154 fel y gellir rhannu enwau allan ychydig yn fwy na dim ond y gallai 26 o smotiau yn caniatáu. 315 00:12:44,154 --> 00:12:47,320 Ac efallai ei fod yn ychydig yn fwy o unffurf na mynd gyda llythrennau yn nhrefn yr wyddor, 316 00:12:47,320 --> 00:12:50,236 oherwydd wrth gwrs mae yna fwy na thebyg mwy o bobl yn y byd gydag enwau 317 00:12:50,236 --> 00:12:54,020 sy'n dechrau gyda A nag yn sicr rhai llythrennau eraill o'r wyddor. 318 00:12:54,020 --> 00:12:56,380 Felly, efallai fod hyn yn ychydig yn mwy unffurf, gan dybio 319 00:12:56,380 --> 00:12:58,640 dosbarthiad unffurf o fabanod ar draws y mis. 320 00:12:58,640 --> 00:12:59,990 >> Ond, wrth gwrs, mae hyn yn dal i fod yn amherffaith. 321 00:12:59,990 --> 00:13:00,370 Hawl? 322 00:13:00,370 --> 00:13:01,370 Rydym yn cael gwrthdrawiadau. 323 00:13:01,370 --> 00:13:04,680 Pobl lluosog yn hyn strwythur data yn dal i 324 00:13:04,680 --> 00:13:08,432 cael yr un dyddiad geni, o leiaf eich bod yn waeth beth yw mis. 325 00:13:08,432 --> 00:13:09,640 Ond beth y mae'r awdur ei wneud? 326 00:13:09,640 --> 00:13:13,427 Wel, mae'n edrych fel gennym amrywiaeth ar yr ochr chwith a dynnwyd yn fertigol, 327 00:13:13,427 --> 00:13:15,010 ond dim ond rendition artist. 328 00:13:15,010 --> 00:13:18,009 Does dim ots pa gyfeiriad yr ydych tynnu amrywiaeth, mae'n dal i fod arae. 329 00:13:18,009 --> 00:13:20,225 Beth yw hyn amrywiaeth o ôl pob golwg? 330 00:13:20,225 --> 00:13:21,500 >> GYNULLEIDFA: Rhestr Cysylltiedig. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Yeah. 332 00:13:21,650 --> 00:13:23,490 Mae'n edrych fel ei fod yn amrywiaeth o restr cysylltiedig. 333 00:13:23,490 --> 00:13:26,490 Felly, unwaith eto, at y pwynt hwn o fath o ddefnyddio strwythurau data hyn bellach 334 00:13:26,490 --> 00:13:28,550 fel cynhwysion i fwy datrysiadau diddorol, 335 00:13:28,550 --> 00:13:30,862 gallwch hollol gymryd sylfaenol, fel amrywiaeth, 336 00:13:30,862 --> 00:13:33,320 ac yna cymryd rhywbeth mwy diddorol fel rhestr cysylltiedig 337 00:13:33,320 --> 00:13:36,660 a hyd yn oed eu cyfuno i mewn i hyd yn oed strwythur data yn fwy diddorol. 338 00:13:36,660 --> 00:13:39,630 Ac yn wir, mae hyn hefyd y byddai gael ei alw tabl hash, 339 00:13:39,630 --> 00:13:42,610 lle yr amrywiaeth yn 'n sylweddol y tabl hash, 340 00:13:42,610 --> 00:13:45,600 ond y tabl hash wedi cadwyni, fel petai, 341 00:13:45,600 --> 00:13:50,220 sy'n gallu tyfu neu grebachu yn seiliedig ar y nifer o elfennau rydych am ei fewnosod. 342 00:13:50,220 --> 00:13:52,990 >> Yn awr, yn unol â hynny, beth sy'n yr amser yn rhedeg nawr? 343 00:13:52,990 --> 00:13:58,030 Os ydw i eisiau i fewnosod rywun y mae eu pen-blwydd yn 31 Hydref, 344 00:13:58,030 --> 00:13:59,040 lle y mae ef neu hi yn mynd? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Mae pob hawl. 347 00:14:01,030 --> 00:14:02,819 Ar y gwaelod lle mae'n dweud 31. 348 00:14:02,819 --> 00:14:03,610 Ac mae hynny'n berffaith. 349 00:14:03,610 --> 00:14:05,060 Dyna oedd amser cyson. 350 00:14:05,060 --> 00:14:08,760 Ond beth os ydym yn dod o hyd i rywun arall y mae eu pen-blwydd yn cael ei, gadewch i ni weld, 351 00:14:08,760 --> 00:14:10,950 Hydref, Tachwedd, 31 Rhagfyr? 352 00:14:10,950 --> 00:14:12,790 Ble mae ef neu hi yn mynd i fynd? 353 00:14:12,790 --> 00:14:13,290 Un peth. 354 00:14:13,290 --> 00:14:13,970 Mae dau gam er. 355 00:14:13,970 --> 00:14:15,303 Mae hynny'n gyson ond yn tydi? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Mae pob hawl. 358 00:14:16,860 --> 00:14:17,840 Ar hyn o bryd y mae. 359 00:14:17,840 --> 00:14:20,570 Ond yn yr achos cyffredinol, po fwyaf o bobl rydym yn ychwanegu, 360 00:14:20,570 --> 00:14:23,790 probabilistically, rydym yn mynd i gael mwy a mwy o wrthdrawiadau. 361 00:14:23,790 --> 00:14:26,820 >> Nawr mae hyn yn ychydig well oherwydd dechnegol 362 00:14:26,820 --> 00:14:34,580 Erbyn hyn gallai fy cadwyni fod mewn yr achos gwaethaf pa mor hir? 363 00:14:34,580 --> 00:14:38,890 Os byddaf yn mewnosod n bobl i mewn i hyn yn fwy strwythur data soffistigedig, n phobl, 364 00:14:38,890 --> 00:14:41,080 yn yr achos gwaethaf mae'n mynd i fod yn n. 365 00:14:41,080 --> 00:14:41,815 Pam? 366 00:14:41,815 --> 00:14:43,332 >> GYNULLEIDFA: Oherwydd os pawb yr un pen-blwydd, 367 00:14:43,332 --> 00:14:44,545 maen nhw'n mynd i fod yn un llinell. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Perffaith. 369 00:14:45,420 --> 00:14:47,480 Gallai fod yn ychydig yn contrived, ond yn wir yn yr achos gwaethaf, 370 00:14:47,480 --> 00:14:50,117 os oes gan bawb yr un pen-blwydd, o ystyried y mewnbynnau sydd gennych, 371 00:14:50,117 --> 00:14:51,950 ydych yn mynd i gael cadwyn aruthrol hir. 372 00:14:51,950 --> 00:14:54,241 Ac felly, fe allech chi alw yn hash tabl, ond mewn gwirionedd 'i' 373 00:14:54,241 --> 00:14:56,810 dim ond rhestr cysylltiedig enfawr gyda llawer gyfan o le gwastraffu. 374 00:14:56,810 --> 00:15:00,460 Ond yn gyffredinol, os byddwn yn cymryd yn ganiataol bod o leiaf penblwyddi yn uniform-- 375 00:15:00,460 --> 00:15:01,750 ac mae'n debyg nad yw'n. 376 00:15:01,750 --> 00:15:02,587 Fy mod yn gwneud hynny i fyny. 377 00:15:02,587 --> 00:15:04,420 Ond os ydym yn tybio, er mwyn trafod 378 00:15:04,420 --> 00:15:07,717 eu bod, yna mewn theori, os hwn yw'r gynrychiolaeth fertigol 379 00:15:07,717 --> 00:15:11,050 y rhesi, yn dda yna gobeithio eich bod yn mynd i gael cadwyni sydd, chi'n gwybod, 380 00:15:11,050 --> 00:15:15,880 fwy neu lai yr un hyd lle mae pob un o'r mae'r rhain yn cynrychioli diwrnod o'r mis. 381 00:15:15,880 --> 00:15:19,930 >> Nawr, os oes 31 diwrnod yn y mis, mae hynny'n golygu fy amser rhedeg 'n sylweddol 382 00:15:19,930 --> 00:15:25,230 yw O fawr o n dros 31, a oedd yn teimlo'n well na llinellol. 383 00:15:25,230 --> 00:15:27,950 Ond beth oedd yn un o'n ymrwymiadau cwpl o wythnosau 384 00:15:27,950 --> 00:15:31,145 yn ôl pryd bynnag y daeth i fynegi yr amser yn rhedeg o algorithm? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Dim ond dim ond yn edrych ar y term trefn uchel. 387 00:15:35,190 --> 00:15:35,690 Hawl? 388 00:15:35,690 --> 00:15:37,400 31 yn bendant o gymorth. 389 00:15:37,400 --> 00:15:39,610 Ond mae hyn yn dal i fod yn O fawr o n. 390 00:15:39,610 --> 00:15:41,730 Ond mae un o'r themâu o broblem a osodwyd bump 391 00:15:41,730 --> 00:15:43,950 yn mynd i fod i cydnabod hynny gwbl, 392 00:15:43,950 --> 00:15:47,320 asymptotically, yn ddamcaniaethol y strwythur data 393 00:15:47,320 --> 00:15:50,470 dim yn well na dim ond un rhestr gysylltiedig enfawr. 394 00:15:50,470 --> 00:15:53,550 Ac yn wir, yn yr achos gwaethaf, mae hyn Efallai y tabl hash datganoli i mewn i hynny. 395 00:15:53,550 --> 00:15:57,620 >> Ond yn y byd go iawn, gyda ni bodau dynol bod Macs neu gyfrifiaduron eu hunain neu beth bynnag 396 00:15:57,620 --> 00:16:01,240 ac yn rhedeg y byd go iawn meddalwedd ar ddata byd go iawn, 397 00:16:01,240 --> 00:16:03,260 pa algorithm ydych chi'n mynd i well gan? 398 00:16:03,260 --> 00:16:09,180 Yr un sy'n cymryd camau pen neu'r un sy'n cymryd ei rannu n erbyn 31 cam 399 00:16:09,180 --> 00:16:12,900 i ddod o hyd i ddarn o ddata neu i chwilio am ychydig o wybodaeth? 400 00:16:12,900 --> 00:16:16,580 Yr wyf yn golygu, yn hollol y 31 o wneuthuriadau gwahaniaeth yn y byd go iawn. 401 00:16:16,580 --> 00:16:18,540 Mae'n yw 31 gwaith yn gyflymach. 402 00:16:18,540 --> 00:16:20,880 Ac rydym pobl yn sicr mynd i werthfawrogi hynny. 403 00:16:20,880 --> 00:16:23,004 >> Felly, yn sylweddoli y ddeuoliaeth yno rhwng gwirionedd 404 00:16:23,004 --> 00:16:25,920 siarad am bethau mewn theori a asymptotically sy'n bendant 405 00:16:25,920 --> 00:16:28,760 Mae gan werth fel yr ydym wedi gweld, ond yn y byd go iawn, 406 00:16:28,760 --> 00:16:32,930 os ydych yn gofalu am jyst gwneud y hapus dynol ar gyfer mewnbynnau cyffredinol, 407 00:16:32,930 --> 00:16:36,010 efallai y byddwch yn dda iawn am dderbyn y ffaith bod, ie, mae hyn yn llinol, 408 00:16:36,010 --> 00:16:38,360 ond mae'n 31 gwaith yn gyflymach Efallai na llinol fod. 409 00:16:38,360 --> 00:16:41,610 Ac yn well eto, nid ydym yn rhaid i gwneud rhywbeth mympwyol fel dyddiad geni, 410 00:16:41,610 --> 00:16:44,030 gallem dreulio ychydig mwy o amser a glyfrwch 411 00:16:44,030 --> 00:16:47,140 a meddwl am yr hyn y gallem ei wneud, Rhoddir enw person ac efallai 412 00:16:47,140 --> 00:16:50,130 eu dyddiad geni, i gyfuno rhai cynhwysion i chyfrif i maes rhywbeth 413 00:16:50,130 --> 00:16:52,720 sydd yn wirioneddol yn fwy unffurf ac yn llai jaggy, 414 00:16:52,720 --> 00:16:56,250 fel petai na hyn darlun Ar hyn o bryd yn awgrymu y gallai fod. 415 00:16:56,250 --> 00:16:57,750 Sut y gallem weithredu hyn yn y cod? 416 00:16:57,750 --> 00:17:00,280 Wel, gadewch i mi gynnig ein bod yn dim ond benthyg rhywfaint o gystrawen rydym wedi 417 00:17:00,280 --> 00:17:01,799 Defnyddir cwpl o weithiau hyd yn hyn. 418 00:17:01,799 --> 00:17:03,590 Ac yr wyf i'n mynd i ddiffinio a nod, sydd unwaith eto 419 00:17:03,590 --> 00:17:06,812 yn derm cyffredinol ar gyfer dim ond rhai cynhwysydd ar gyfer rhywfaint o strwythur data. 420 00:17:06,812 --> 00:17:09,020 Rydw i'n mynd i gynnig bod llinyn yn mynd i mewn 'na. 421 00:17:09,020 --> 00:17:11,369 Ond rydym yn mynd i ddechrau cymryd rhai sy'n hyfforddi olwynion i ffwrdd nawr. 422 00:17:11,369 --> 00:17:13,230 >> Dim llyfrgell CS50 mwy mewn gwirionedd, oni bai eich bod am 423 00:17:13,230 --> 00:17:15,230 i'w ddefnyddio ar gyfer eich derfynol project, sy'n iawn, 424 00:17:15,230 --> 00:17:18,569 ond erbyn hyn rydyn ni'n mynd i dynnu yn ôl i'r llenni ac yn dweud mai dim ond seren torgoch. 425 00:17:18,569 --> 00:17:22,069 Felly y gair yno yn mynd i fod enw'r person dan sylw. 426 00:17:22,069 --> 00:17:25,079 Ac yn awr mae gen i gyswllt yma at y nod nesaf 427 00:17:25,079 --> 00:17:28,170 fel bod y rhain yn cynrychioli pob un o'r nodau 428 00:17:28,170 --> 00:17:30,950 yn y gadwyn, o bosibl, o restr cysylltiedig. 429 00:17:30,950 --> 00:17:34,090 >> Ac yn awr sut ydw i'n datgan y tabl hash ei hun? 430 00:17:34,090 --> 00:17:36,660 Sut ydw i'n datgan strwythur cyfan hwn? 431 00:17:36,660 --> 00:17:40,960 Wel, mewn gwirionedd, yn debyg iawn i mi defnyddio pwyntydd i ddim ond yr elfen gyntaf o restr 432 00:17:40,960 --> 00:17:44,510 o'r blaen, yn yr un modd y gallaf ddweud Fi jyst angen criw o awgrymiadau 433 00:17:44,510 --> 00:17:46,270 i weithredu'r tabl hwn hash cyfan. 434 00:17:46,270 --> 00:17:49,484 Rydw i'n mynd i gael amrywiaeth Gelwir tabl ar gyfer tabl hash. 435 00:17:49,484 --> 00:17:50,900 Mae'n mynd i fod o gapasiti maint. 436 00:17:50,900 --> 00:17:52,525 Dyna faint o elfennau y gall ffitio i mewn iddo. 437 00:17:52,525 --> 00:17:56,180 Ac mae pob un o'r elfennau hynny yn hyn arae yn mynd i fod yn seren nod. 438 00:17:56,180 --> 00:17:56,810 Pam? 439 00:17:56,810 --> 00:18:00,160 Wel, fesul y llun, yr hyn rwy'n gweithredu'r tabl hash fel 440 00:18:00,160 --> 00:18:04,330 effeithiol yn y dechrau yn unig arae hwn yr ydym wedi tynnu yn fertigol, 441 00:18:04,330 --> 00:18:06,820 pob un o'r sgwariau y mae eu cynrychioli pwyntydd. 442 00:18:06,820 --> 00:18:09,170 Bod rhai sydd â slaes drwyddynt yn unig null. 443 00:18:09,170 --> 00:18:11,410 A'r rhai sydd â saethau mynd i'r dde 444 00:18:11,410 --> 00:18:16,140 yn awgrymiadau gwirioneddol i nodau gwirioneddol, Ergo ddechrau rhestr cysylltiedig. 445 00:18:16,140 --> 00:18:19,050 >> Felly dyma, felly, yw sut y gallem gweithredu tabl hash sy'n 446 00:18:19,050 --> 00:18:21,580 gweithredu gadwyno wahân. 447 00:18:21,580 --> 00:18:22,840 Nawr gallwn ni ei wneud yn well? 448 00:18:22,840 --> 00:18:25,632 Mae pob hawl Addewais tro diwethaf y gallem gyflawni amser cyson. 449 00:18:25,632 --> 00:18:27,381 Ac yr wyf yn fath o yn rhoi i chi amser cyson yma, 450 00:18:27,381 --> 00:18:29,850 ond yna ni ddywedodd mewn gwirionedd amser cyson am ei fod yn dal i fod 451 00:18:29,850 --> 00:18:31,890 yn dibynnu ar y cyfanswm nifer o elfennau 452 00:18:31,890 --> 00:18:34,500 eich bod yn cyfrannu at strwythur data. 453 00:18:34,500 --> 00:18:35,980 Ond mae'n debyg ein bod yn gwneud hyn. 454 00:18:35,980 --> 00:18:39,550 Gadewch i mi fynd yn ôl i'r sgrin dros yma. 455 00:18:39,550 --> 00:18:44,520 Gadewch i mi hefyd yn rhagweld hyn i fyny yma, yn glir y sgrin, ac mae'n debyg fy mod yn gwneud hyn. 456 00:18:44,520 --> 00:18:49,300 Gadewch i ni dybio Roeddwn i eisiau i roi enw Daven mewn i mewn i fy strwythur data. 457 00:18:49,300 --> 00:18:52,100 >> Felly, rwyf am i fewnosod llinyn Daven i mewn i strwythur data. 458 00:18:52,100 --> 00:18:54,370 Beth os nad wyf yn defnyddio hash tabl, ond yr wyf yn defnyddio 459 00:18:54,370 --> 00:18:56,980 rhywbeth sy'n fwy tebyg i goeden fel coeden deulu, lle 460 00:18:56,980 --> 00:18:59,670 gennych rywfaint gwreiddiau yn y top ac yna nodau a dail 461 00:18:59,670 --> 00:19:01,440 sy'n mynd ar i lawr ac allan. 462 00:19:01,440 --> 00:19:04,450 Tybiwch Yna, fy mod eisiau i fewnosod Daven yn 463 00:19:04,450 --> 00:19:06,430 i mewn i beth rhestr wag ar hyn o bryd. 464 00:19:06,430 --> 00:19:09,780 Rydw i'n mynd i wneud y canlynol: Rwy'n mynd i greu nod yn y teulu hwn 465 00:19:09,780 --> 00:19:15,170 coed-fel strwythur data sy'n edrych ychydig fel hyn, pob un ohonynt 466 00:19:15,170 --> 00:19:19,640 petryal wedi, gadewch i ni ddweud, am y tro 26 elfen ynddo. 467 00:19:19,640 --> 00:19:21,650 A phob un o'r celloedd yn y arae hyn yn mynd 468 00:19:21,650 --> 00:19:23,470 i gynrychioli llythyr o wyddor. 469 00:19:23,470 --> 00:19:28,190 >> Yn benodol, yr wyf i'n mynd i drin mae hyn yn A, yna B, yna C, yna D, 470 00:19:28,190 --> 00:19:29,310 yr un yma fan hyn. 471 00:19:29,310 --> 00:19:32,940 Felly, mae hyn yn mynd i yn effeithiol gynrychioli'r llythyren D. 472 00:19:32,940 --> 00:19:36,040 Ond i fewnosod gyd Daven yn enwi angen i mi wneud ychydig mwy. 473 00:19:36,040 --> 00:19:37,840 Felly dwi'n mynd yn gyntaf i hash, fel petai. 474 00:19:37,840 --> 00:19:41,049 Rydw i'n mynd i edrych ar y llythyr cyntaf yn Daven sydd yn amlwg yn D, 475 00:19:41,049 --> 00:19:42,840 ac yr wyf i'n mynd i ddyrannu a nod sy'n edrych 476 00:19:42,840 --> 00:19:45,570 fel this-- petryal mawr mawr ddigon i gyd-fynd â'r wyddor i gyd. 477 00:19:45,570 --> 00:19:47,140 >> Nawr D yn cael ei wneud. 478 00:19:47,140 --> 00:19:49,720 Nawr A. D-A-V-E-N yw'r nod. 479 00:19:49,720 --> 00:19:51,220 Felly nawr yr hyn yr wyf i'n mynd i wneud yw hyn. 480 00:19:51,220 --> 00:19:54,027 Cyn gynted ag y dechreuais rhybudd D does dim pwyntydd yno. 481 00:19:54,027 --> 00:19:56,860 Mae'n gwerthoedd garbage ar hyn o bryd, neu efallai y byddwn ymgychwyn iddo null. 482 00:19:56,860 --> 00:19:59,630 Ond gadewch i mi gadw i fynd gyda syniad hwn o adeiladu coeden. 483 00:19:59,630 --> 00:20:04,260 Gadewch i mi yn dyrannu un arall o'r rhain nodau sydd â 26 o elfennau ynddo. 484 00:20:04,260 --> 00:20:05,150 >> A ydych yn gwybod beth? 485 00:20:05,150 --> 00:20:09,130 Os yw hyn yn unig yw nod mewn cof bod I greu gyda malloc, gan ddefnyddio struct 486 00:20:09,130 --> 00:20:11,240 gan y byddwn yn fuan yn gweld, Rydw i'n mynd i wneud this-- 487 00:20:11,240 --> 00:20:14,450 Rydw i'n mynd i dynnu saeth o y peth sy'n cynrychioli D i lawr 488 00:20:14,450 --> 00:20:15,860 i'r nod newydd. 489 00:20:15,860 --> 00:20:19,240 Ac yn awr, yn gyntaf y nesaf llythyr yn enw'r Daven yn, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- Rydw i'n mynd i fynd yn ei flaen a thynnu nod arall fel hyn, 491 00:20:24,150 --> 00:20:30,150 lle, mae'r elfennau V yma, a oedd byddwn yn tynnu i whoops instance--. 492 00:20:30,150 --> 00:20:31,020 Ni fyddwn yn tynnu yno. 493 00:20:31,020 --> 00:20:31,936 Mae'n mynd i fynd yma. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Yna rydym yn mynd i ystyried hyn yn V. 496 00:20:35,712 --> 00:20:44,920 Ac yna i lawr yma rydym yn mynd i mynegai i lawr o V i mewn i hyn a byddwn yn ystyried E. 497 00:20:44,920 --> 00:20:50,100 Ac yna o fan hyn rydym yn mynd i mynd yn cael un o'r nodau hyn yn fan hyn. 498 00:20:50,100 --> 00:20:52,930 Ac yn awr mae gennym gwestiwn i'w ateb. 499 00:20:52,930 --> 00:20:57,840 Mae angen i I rhywsut yn dangos bod rydym yn ar ddiwedd y llinyn Daven. 500 00:20:57,840 --> 00:20:59,490 Er mwyn i mi ei adael null. 501 00:20:59,490 --> 00:21:02,670 >> Ond beth os ydym wedi Daven yn enw llawn hefyd, a oedd yn 502 00:21:02,670 --> 00:21:04,280 yw, fel yr ydym wedi dweud, Davenport? 503 00:21:04,280 --> 00:21:06,970 Felly beth os Daven yw mewn gwirionedd is- linyn, 504 00:21:06,970 --> 00:21:08,960 rhagddodiad o gyfres llawer hirach? 505 00:21:08,960 --> 00:21:11,450 Ni allwn yn unig yn barhaol yn dweud dim byd yn mynd 506 00:21:11,450 --> 00:21:14,410 i fynd yno, oherwydd gallem byth yn mewnosod gair fel Davenport 507 00:21:14,410 --> 00:21:15,840 i mewn i'r Strwythur data 508 00:21:15,840 --> 00:21:19,560 >> Felly, yr hyn y gallem ei wneud yn lle hynny yw yn trin pob un o'r elfennau hyn 509 00:21:19,560 --> 00:21:22,170 fel efallai gael dau elfennau y tu mewn ohonynt. 510 00:21:22,170 --> 00:21:24,810 Mae un yn pwyntydd, yn wir, gan fy mod i wedi bod yn ei wneud. 511 00:21:24,810 --> 00:21:27,100 Felly mae pob un o'r blychau hyn Nid yw un gell yn unig. 512 00:21:27,100 --> 00:21:29,855 Ond beth os bydd y top one-- yr un isaf o 513 00:21:29,855 --> 00:21:32,230 mynd i fod yn null, oherwydd nid oes unrhyw Davenport eto. 514 00:21:32,230 --> 00:21:34,197 Beth os bydd yr un uchaf mae rhywfaint o werth arbennig? 515 00:21:34,197 --> 00:21:36,530 Ac mae'n mynd i fod ychydig yn anodd i dynnu ei maint hwn. 516 00:21:36,530 --> 00:21:38,130 Ond mae'n debyg mai dim ond marc siec. 517 00:21:38,130 --> 00:21:38,920 Gwirio. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N yn llinyn yn y strwythur data. 519 00:21:44,230 --> 00:21:48,350 >> Yn y cyfamser, os oedd gennyf mwy o le fan hyn, gallwn i wneud P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 a gallwn roi siec yn y nod fod gan y llythyren T ar y diwedd un. 521 00:21:52,650 --> 00:21:55,460 Felly mae hwn yn aruthrol cymhleth sy'n edrych strwythur data. 522 00:21:55,460 --> 00:21:57,210 A fy llawysgrifen yn sicr nid yw'n helpu. 523 00:21:57,210 --> 00:22:00,043 Ond os oeddwn i eisiau i fewnosod rhywbeth arall, yn ystyried yr hyn y byddem yn ei wneud. 524 00:22:00,043 --> 00:22:03,370 Os ydym yn awyddus i roi David i mewn, byddem yn dilyn yr un rhesymeg, D-A-V, 525 00:22:03,370 --> 00:22:08,802 ond erbyn hyn byddwn yn rhoi ar y nesaf Elfen nid o E, ond o I i D. 526 00:22:08,802 --> 00:22:10,760 Felly, mae mynd i fod yn mwy o nodau yn y goeden hon. 527 00:22:10,760 --> 00:22:12,325 Rydym yn mynd i gael galwad malloc mwy. 528 00:22:12,325 --> 00:22:14,700 Ond dwi ddim eisiau gwneud llanast cyflawn o'r darlun hwn. 529 00:22:14,700 --> 00:22:17,710 Felly, gadewch i ni yn lle edrych ar un sydd wedi ei lunio cyn- 530 00:22:17,710 --> 00:22:21,810 fel hyn gyda beidio dot, dot, dotiau, ond araeau unig talfyrru. 531 00:22:21,810 --> 00:22:23,950 Ond mae pob un o'r nodau yn y goeden hon hyd yma 532 00:22:23,950 --> 00:22:26,700 yn cynrychioli'r un thing-- amrywiaeth Ray o faint 26. 533 00:22:26,700 --> 00:22:28,860 >> Neu, os ydym am fod wir yn briodol yn awr, beth 534 00:22:28,860 --> 00:22:30,790 os yw enw rhywun fel collnod, gadewch i ni 535 00:22:30,790 --> 00:22:35,560 cymryd yn ganiataol bod pob nod mewn gwirionedd wedi fel 27 mynegeion ynddo, nid dim ond 26. 536 00:22:35,560 --> 00:22:42,020 Felly, mae hyn yn awr yn mynd i fod yn ddata strwythur a elwir yn trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 Mae trie, sydd yn sôn, hanesyddol enw clyfar i goeden 538 00:22:46,120 --> 00:22:49,040 sy'n ei optimeiddio ar gyfer adfer, sydd wrth gwrs, 539 00:22:49,040 --> 00:22:50,870 ei sillafu gyda I-E felly mae'n trie. 540 00:22:50,870 --> 00:22:52,710 Ond mae hynny'n hanes y trie. 541 00:22:52,710 --> 00:22:55,860 >> Felly mae trie yw hyn data tebyg i goeden Strwythur fel coeden deulu 542 00:22:55,860 --> 00:22:57,510 yn y pen draw yn ymddwyn fel 'na. 543 00:22:57,510 --> 00:23:00,890 A dyma yn unig yw enghraifft arall o criw cyfan o enwau pobl eraill. 544 00:23:00,890 --> 00:23:03,540 Ond mae'r cwestiwn yn awr wrth law yn yr hyn sydd 545 00:23:03,540 --> 00:23:08,070 rydym yn ennill drwy gyflwyno Gellir dadlau bod mwy strwythur data cymhleth, ac un, 546 00:23:08,070 --> 00:23:09,870 dweud y gwir, sy'n defnyddio llawer o gof. 547 00:23:09,870 --> 00:23:11,703 >> Oherwydd hyd yn oed er, ar hyn o bryd, rwy'n dim ond 548 00:23:11,703 --> 00:23:15,050 gan ddefnyddio pwyntydd D a A a V a Es a Ns, 549 00:23:15,050 --> 00:23:16,700 Rydw i'n gwastraffu yn andros o lot o gof. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Ond lle rwy'n treulio un adnodd, Dwi'n tueddu i ddim yn ennill yn ôl un arall. 552 00:23:22,660 --> 00:23:26,020 Felly, os ydw i'n treulio mwy o le, beth sydd yn ôl pob tebyg y gobaith? 553 00:23:26,020 --> 00:23:27,407 Fy mod i'n gwario llai beth? 554 00:23:27,407 --> 00:23:28,240 GYNULLEIDFA: Llai o amser. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Time. 556 00:23:28,990 --> 00:23:30,320 Nawr pam y gallai hynny fod? 557 00:23:30,320 --> 00:23:33,880 Wel, beth yw gosod amser, o ran O mawr yn awr, 558 00:23:33,880 --> 00:23:37,660 o enw fel Daven neu Davenport neu David? 559 00:23:37,660 --> 00:23:39,340 Wel, roedd Daven pum cam. 560 00:23:39,340 --> 00:23:42,350 Byddai Davenport yn naw cam, felly byddai'n ychydig mwy o gamau. 561 00:23:42,350 --> 00:23:44,250 Byddai David fod pum cam yn ogystal. 562 00:23:44,250 --> 00:23:47,230 Felly, y rhai yn concrid rhifau, ond yn sicr mae 'na 563 00:23:47,230 --> 00:23:49,550 uchaf yn rhwymo ar y hyd yr enw rhywun. 564 00:23:49,550 --> 00:23:52,240 Ac yn wir, yn y broblem setiau o bump fanyleb, 565 00:23:52,240 --> 00:23:54,050 rydym yn mynd i gynnig ei fod yn rhywbeth 566 00:23:54,050 --> 00:23:55,470 dyna cymeriadau 40-rhai-od. 567 00:23:55,470 --> 00:23:58,180 >> Yn realistig, nid oes neb wedi enw anfeidrol hir, 568 00:23:58,180 --> 00:24:01,542 sef i ddweud bod hyd a enwi neu hyd llinyn gallem 569 00:24:01,542 --> 00:24:03,750 rhaid i rai cyflwr strwythur yn dadlau beth? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Mae'n gyson. 572 00:24:06,250 --> 00:24:06,430 Hawl? 573 00:24:06,430 --> 00:24:09,310 Gallai fod yn gyson mawr fel 40-rhywbeth, ond mae'n gyson. 574 00:24:09,310 --> 00:24:13,752 Ac nid oes ganddo unrhyw ddibyniaeth ar faint o enwau eraill yn y strwythur data. 575 00:24:13,752 --> 00:24:15,460 Mewn geiriau eraill, os byddaf eisiau nawr mewnosod 576 00:24:15,460 --> 00:24:20,540 Colton neu Gabriel neu Rob neu Zamyla neu Alison neu Belinda neu unrhyw enwau eraill 577 00:24:20,540 --> 00:24:23,940 o'r staff yn ddata hon strwythur, yw'r amser yn rhedeg 578 00:24:23,940 --> 00:24:26,750 o mewnosod enwau eraill mynd i fod o gwbl effeithio 579 00:24:26,750 --> 00:24:30,220 gan faint o elfennau eraill yn yn y strwythur data yn barod? 580 00:24:30,220 --> 00:24:31,040 Dyw hi ddim. 581 00:24:31,040 --> 00:24:31,540 Hawl? 582 00:24:31,540 --> 00:24:36,150 Oherwydd ein bod yn ei ddefnyddio yn effeithiol y tabl hwn hash aml-haen. 583 00:24:36,150 --> 00:24:38,280 A'r amser yn rhedeg o unrhyw agwedd ar y 584 00:24:38,280 --> 00:24:41,510 yn dibynnu nid ar nifer y elfennau sydd yn y strwythur data 585 00:24:41,510 --> 00:24:43,090 neu sy'n mynd yn y pen draw i fod yn y strwythur data, 586 00:24:43,090 --> 00:24:44,714 ond ar y hyd y beth yn benodol? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Mae'r llinyn yn cael mewnosod, sydd yn gwneud 589 00:24:49,200 --> 00:24:52,580 mae hyn asymptotically gyson O fawr adeg-- o un. 590 00:24:52,580 --> 00:24:54,720 A dweud y gwir, dim ond mewn y byd go iawn, mae hyn yn 591 00:24:54,720 --> 00:24:58,380 yn golygu gosod enw Daven yn cymryd fel pum cam, neu Davenport naw 592 00:24:58,380 --> 00:25:00,100 grisiau, neu David pum cam. 593 00:25:00,100 --> 00:25:03,071 Dyna 'n bert darn amseroedd rhedeg bach. 594 00:25:03,071 --> 00:25:05,320 Ac, yn wir, mae hynny'n iawn beth da, yn enwedig pan fydd 595 00:25:05,320 --> 00:25:08,126 nid yw'n dibynnu ar y cyfanswm Nifer o elfennau i mewn 'na. 596 00:25:08,126 --> 00:25:10,500 Felly, sut y gallwn weithredu hyn fath o strwythur yn y cod? 597 00:25:10,500 --> 00:25:12,900 Mae'n ychydig yn fwy cymhleth, ond yn dal 'i' 598 00:25:12,900 --> 00:25:15,050 unig gais o blociau adeiladu sylfaenol. 599 00:25:15,050 --> 00:25:17,830 Rydw i'n mynd i ailddiffinio nod ni fel a ganlyn: 600 00:25:17,830 --> 00:25:21,100 bool gelwir word-- ac mae hyn yn Gellid eu galw unrhyw beth. 601 00:25:21,100 --> 00:25:23,970 Ond mae'r bool yn cynrychioli beth tynnais fel arwydd siec. 602 00:25:23,970 --> 00:25:24,490 Ie. 603 00:25:24,490 --> 00:25:26,720 Mae hyn yn y pen llinyn yn y strwythur data. 604 00:25:26,720 --> 00:25:30,702 >> Ac, wrth gwrs, mae'r seren nôd mae yn cyfeirio at blant. 605 00:25:30,702 --> 00:25:32,410 Ac, yn wir, yn union fel coeden deulu, rydych 606 00:25:32,410 --> 00:25:34,370 Byddai ystyried y nodau sy'n cael eu hongian off 607 00:25:34,370 --> 00:25:36,920 o waelod rhyw rhiant elfen i fod yn blant. 608 00:25:36,920 --> 00:25:40,510 Ac felly mae'r plant yn mynd i fod amrywiaeth o 27, yr un 27 609 00:25:40,510 --> 00:25:41,680 dim ond bod am collnod. 610 00:25:41,680 --> 00:25:43,390 Rydym yn mynd i ddatrys o achos arbennig hwnnw. 611 00:25:43,390 --> 00:25:45,400 Felly, gallwch gael rhai enwau gyda collnodau. 612 00:25:45,400 --> 00:25:47,399 Efallai dylai hyd yn oed cysylltnod mynd i mewn yno, ond wnewch chi helpu 613 00:25:47,399 --> 00:25:50,330 gweld mewn p set 5 yn unig gofal yr ydym yn am lythrennau a chollnod. 614 00:25:50,330 --> 00:25:52,990 >> Ac yna sut ydych chi'n cynrychioli strwythur data ei hun? 615 00:25:52,990 --> 00:25:56,454 Sut ydych chi'n cynrychioli y gwraidd y trie hwn, fel petai? 616 00:25:56,454 --> 00:25:59,620 Wel, yn union fel gyda rhestr cysylltiedig, rydych angen pwyntydd at yr elfen gyntaf. 617 00:25:59,620 --> 00:26:04,270 Gyda trie 'ch jyst angen un pwyntydd at wraidd trie hwn. 618 00:26:04,270 --> 00:26:07,290 Ac oddi yno gallwch hash eich ffordd i lawr yn ddyfnach ac yn ddyfnach 619 00:26:07,290 --> 00:26:10,460 i bob nod arall yn y strwythur. 620 00:26:10,460 --> 00:26:13,440 Felly yn syml gyda'r can hwn rydym yn cynrychioli y struct. 621 00:26:13,440 --> 00:26:15,877 >> Nawr Meanwhile-- O, cwestiwn. 622 00:26:15,877 --> 00:26:17,220 >> GYNULLEIDFA: Beth yw gair bool? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: word Bool yn dim ond hyn C ymgnawdoliad 624 00:26:20,490 --> 00:26:22,920 o'r hyn yr wyf yn ei ddisgrifio yn y blwch yma, pan 625 00:26:22,920 --> 00:26:26,000 Dechreuais rhannu pob un o'r elfennau amrywiaeth i mewn i ddau ddarn. 626 00:26:26,000 --> 00:26:27,600 Mae un yn pwyntydd i'r nod nesaf. 627 00:26:27,600 --> 00:26:30,280 Mae'r llall wedi i fod rhywbeth fel blwch gwirio 628 00:26:30,280 --> 00:26:33,770 i ddweud ie, mae 'na word Daven sy'n dod i ben yma, 629 00:26:33,770 --> 00:26:35,610 oherwydd nid ydym am, ar hyn o bryd, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Er bod Dave yn mynd i fod yn Gair dilys, nid ei fod yn y trie 631 00:26:39,320 --> 00:26:39,830 eto. 632 00:26:39,830 --> 00:26:40,950 Ac nid yw D yn air. 633 00:26:40,950 --> 00:26:42,770 Ac nid yw D-A yn air neu enw. 634 00:26:42,770 --> 00:26:45,020 Felly y marc siec yn dangos ar ôl i chi yn unig 635 00:26:45,020 --> 00:26:48,190 taro nod hwn yw'r llwybr blaenorol o gymeriadau 636 00:26:48,190 --> 00:26:50,700 mewn gwirionedd yn llinyn eich bod wedi mewnosod. 637 00:26:50,700 --> 00:26:53,660 Felly dyna i gyd y bool mae yn ei wneud i ni. 638 00:26:53,660 --> 00:26:55,500 >> Unrhyw gwestiynau eraill ar gais? 639 00:26:55,500 --> 00:26:56,215 Yeah. 640 00:26:56,215 --> 00:26:58,035 >> GYNULLEIDFA: Beth yw'r gorgyffwrdd? 641 00:26:58,035 --> 00:26:59,945 Beth os oes gennych Dave a Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Perffaith. 643 00:27:00,820 --> 00:27:02,580 Beth os oes gennych Dave a Daven? 644 00:27:02,580 --> 00:27:06,240 Felly os ydym yn mewnosod, yn dweud llysenw, am David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Mae hyn mewn gwirionedd super syml. 647 00:27:08,700 --> 00:27:10,325 Felly, rydym yn unig yn mynd i gymryd pedwar cam. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. A beth sydd yn rhaid i I yn ei wneud ar ôl i mi daro y pedwerydd nod? 650 00:27:15,847 --> 00:27:16,680 Dim ond yn mynd i wirio. 651 00:27:16,680 --> 00:27:18,000 Rydym eisoes yn dda i fynd. 652 00:27:18,000 --> 00:27:18,840 Done. 653 00:27:18,840 --> 00:27:19,750 Pedwar cam. 654 00:27:19,750 --> 00:27:21,590 Amser Cyson asymptotically. 655 00:27:21,590 --> 00:27:26,300 Ac yn awr rydym wedi dangos bod y ddau Dave ac Daven yn llinynnau yn y strwythur. 656 00:27:26,300 --> 00:27:27,710 Felly nid problem. 657 00:27:27,710 --> 00:27:30,200 Ac yn sylwi sut y mae'r presenoldeb o Daven nid oedd yn ei gwneud yn 658 00:27:30,200 --> 00:27:34,750 gymryd unrhyw mwy o amser neu lai amser ar gyfer Dave ac i'r gwrthwyneb. 659 00:27:34,750 --> 00:27:36,000 >> Felly, beth arall y gallwn ei wneud yn awr? 660 00:27:36,000 --> 00:27:40,680 Rydym wedi defnyddio trosiad hwn o'r blaen o hambyrddau yn cynrychioli rhywbeth. 661 00:27:40,680 --> 00:27:43,380 Ond mae'n troi allan bod yn pentwr o hambyrddau mewn gwirionedd 662 00:27:43,380 --> 00:27:47,187 dangosol o ddata haniaethol arall type-- strwythur data lefel uwch 663 00:27:47,187 --> 00:27:49,770 bod ar ddiwedd y dydd yn unig fel arae neu restr cysylltiedig 664 00:27:49,770 --> 00:27:50,970 neu rywbeth mwy cyffredin. 665 00:27:50,970 --> 00:27:53,270 Ond ei fod yn fwy diddorol cysyniad cysyniadol. 666 00:27:53,270 --> 00:27:56,440 Pentwr, fel y rhain hambyrddau yma yn Mather, 667 00:27:56,440 --> 00:27:58,750 yn cael eu galw yn gyffredinol jyst that-- pentwr. 668 00:27:58,750 --> 00:28:02,540 >> Ac yn y math hwn o strwythur data gennych ddau operations-- 669 00:28:02,540 --> 00:28:05,880 oes gennych un gwthio yn galw am gan ychwanegu rhywbeth at y simnai, 670 00:28:05,880 --> 00:28:08,320 fel rhoi hambwrdd arall yn ôl ar ben y pentwr. 671 00:28:08,320 --> 00:28:11,350 Ac yna pop, sy'n golygu eich bod gymryd y oddi ar hambwrdd topmost. 672 00:28:11,350 --> 00:28:16,210 Ond yr hyn sy'n allweddol am stac yw bod 'i' got y nodwedd chwilfrydig. 673 00:28:16,210 --> 00:28:19,560 Gan fod y staff ffreutur yn aildrefnu'r hambyrddau ar gyfer y pryd nesaf, 674 00:28:19,560 --> 00:28:21,380 beth sy'n mynd i fod yn wir am sut mae myfyrwyr 675 00:28:21,380 --> 00:28:22,856 rhyngweithio gyda'r strwythur data? 676 00:28:22,856 --> 00:28:24,480 GYNULLEIDFA: Maent yn mynd i pop un off. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Maent yn mynd i pop un off, gobeithio y top. 678 00:28:26,550 --> 00:28:28,910 Fel arall, 'i' jyst fath o dwp i fynd yr holl ffordd i'r gwaelod. 679 00:28:28,910 --> 00:28:29,070 Hawl? 680 00:28:29,070 --> 00:28:31,620 Nid yw'r strwythur data ddim yn caniatáu i chi chrafangia 'r hambwrdd gwaelod o leiaf 681 00:28:31,620 --> 00:28:32,520 yn hawdd. 682 00:28:32,520 --> 00:28:35,040 Felly mae hyn yn chwilfrydig eiddo i'r stac 683 00:28:35,040 --> 00:28:39,730 bod yr eitem olaf ynddo yw mynd i fod yr un allan gyntaf. 684 00:28:39,730 --> 00:28:43,400 A gwyddonwyr cyfrifiadurol yn galw LIFO-- hyn bara i mewn, cyntaf allan. 685 00:28:43,400 --> 00:28:45,540 Ac mae'n mewn gwirionedd oes gan ceisiadau diddorol. 686 00:28:45,540 --> 00:28:50,090 Dyw hi ddim o reidrwydd mor amlwg â rhai eraill, ond gall, yn wir, fod yn ddefnyddiol, 687 00:28:50,090 --> 00:28:54,040 a gall, yn wir, yn cael eu rhoi ar waith mewn un neu ddau o wahanol ffyrdd. 688 00:28:54,040 --> 00:28:58,550 >> Felly un, ac mewn gwirionedd, gadewch mi beidio i ddeifio i mewn i hynny. 689 00:28:58,550 --> 00:28:59,860 Gadewch i ni wneud hyn yn lle hynny. 690 00:28:59,860 --> 00:29:03,700 Gadewch i ni edrych ar un dyna bron y un syniad, ond mae'n ychydig yn decach. 691 00:29:03,700 --> 00:29:04,200 Hawl? 692 00:29:04,200 --> 00:29:07,560 Os ydych yn un o fechgyn ffan hyn neu merched sydd wir yn hoffi cynnyrch Apple 693 00:29:07,560 --> 00:29:10,130 ac rydych nes i ddeffro am 03:00 i linell i fyny ar ryw siop 694 00:29:10,130 --> 00:29:14,150 i gael y iPhone diweddaraf yn iawn, byddwch yn allai fod wedi ciw i fyny fel hyn. 695 00:29:14,150 --> 00:29:15,800 >> Erbyn hyn, mae ciw yn cael ei enwi yn fwriadol iawn. 696 00:29:15,800 --> 00:29:18,190 Mae'n llinell oherwydd bod rhywfaint tegwch iddo. 697 00:29:18,190 --> 00:29:18,690 Hawl? 698 00:29:18,690 --> 00:29:21,690 Byddai'n fath o sugno os ydych wedi cyrraedd yno gyntaf yn y Storfa Apple 699 00:29:21,690 --> 00:29:25,700 ond eich bod yn effeithiol yw'r bottommost hambwrdd oherwydd bod y gweithwyr Apple, yna 700 00:29:25,700 --> 00:29:28,189 pop y person olaf sy'n got mewn gwirionedd yn unol. 701 00:29:28,189 --> 00:29:31,230 Felly staciau a ciwiau, er bod swyddogaethol eu bod yn fath o yr same-- 702 00:29:31,230 --> 00:29:33,105 'i' jyst y casgliad hwn o adnoddau sy'n 703 00:29:33,105 --> 00:29:36,210 mynd i dyfu a shrink-- mae ' yr agwedd tegwch iddo, 704 00:29:36,210 --> 00:29:39,634 o leiaf yn y byd go iawn, lle gwneir unrhyw waith rydych yn ymarfer 705 00:29:39,634 --> 00:29:40,800 yn sylfaenol wahanol. 706 00:29:40,800 --> 00:29:43,360 A stack-- ciw rather-- dywedwyd ei fod wedi 707 00:29:43,360 --> 00:29:45,320 dau gweithrediadau: n ciw a d ciw. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Neu gallwch eu ffonio unrhyw nifer o bethau. 710 00:29:48,090 --> 00:29:50,770 Ond 'ch jyst eisiau ei gipio y syniad bod un yn cael ei ychwanegu 711 00:29:50,770 --> 00:29:53,230 ac mae un yn y pen draw tynnu. 712 00:29:53,230 --> 00:29:58,840 >> Yn awr o dan y cwfl, mae'r pentwr a gellid ciw eu gweithredu sut? 713 00:29:58,840 --> 00:30:01,390 Ni fyddwn yn mynd i mewn i'r cod oherwydd y lefel uwch 714 00:30:01,390 --> 00:30:03,387 syniad yn fath o yn fwy amlwg. 715 00:30:03,387 --> 00:30:04,470 Hynny yw, beth mae pobl yn ei wneud? 716 00:30:04,470 --> 00:30:07,030 Os Fi yw'r person cyntaf yn y Apple Storiwch a dyma'r drws ffrynt, 717 00:30:07,030 --> 00:30:08,130 eich bod yn gwybod, yr wyf i'n mynd i sefyll yma. 718 00:30:08,130 --> 00:30:09,750 A'r person nesaf mynd i sefyll yma. 719 00:30:09,750 --> 00:30:11,500 A'r person nesaf mynd i sefyll yma. 720 00:30:11,500 --> 00:30:13,792 Felly pa strwythur data cynnig ei hun i ciw? 721 00:30:13,792 --> 00:30:14,542 >> GYNULLEIDFA: A ciw. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: Wel, ciw. 723 00:30:15,667 --> 00:30:16,390 Cadarn. 724 00:30:16,390 --> 00:30:16,920 Beth arall? 725 00:30:16,920 --> 00:30:17,600 >> GYNULLEIDFA: Mae rhestr cysylltiedig. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: A cysylltiedig rhestrwch y gallech rhoi ar waith. 727 00:30:18,990 --> 00:30:22,500 A rhestr cysylltiedig yn braf oherwydd wedyn gall dyfu fympwyol o amser yn hytrach na 728 00:30:22,500 --> 00:30:24,880 i gael rhywfaint o nifer a bennwyd o bobl yn y siop. 729 00:30:24,880 --> 00:30:27,030 Ond efallai yn nifer penodedig o leoedd yn gyfreithlon. 730 00:30:27,030 --> 00:30:30,350 Achos os mai dim ond yn hoffi 20 iPhones ar y diwrnod cyntaf, efallai 731 00:30:30,350 --> 00:30:33,930 maent ond angen amrywiaeth o faint 20 i gynrychioli y ciw, sy'n 732 00:30:33,930 --> 00:30:37,070 dim ond i ddweud yn awr ar ôl i ni ddechrau siarad am y problemau ar lefel uwch, 733 00:30:37,070 --> 00:30:38,890 gallwch ei roi ar waith mewn unrhyw nifer o ffyrdd. 734 00:30:38,890 --> 00:30:42,030 Ac mae pob tebyg dim ond yn mynd i fod yn fasnach i ffwrdd yn y gofod ac amser 735 00:30:42,030 --> 00:30:43,950 neu dim ond yn eich cymhlethdod cod eich hun. 736 00:30:43,950 --> 00:30:45,380 >> Beth am stac? 737 00:30:45,380 --> 00:30:48,190 Wel, pentwr, rydym wedi gweld yn rhy Gallai dim ond fod yn hambyrddau hyn. 738 00:30:48,190 --> 00:30:50,007 A allech chi roi hyn ar waith arae. 739 00:30:50,007 --> 00:30:53,090 Ond ar ryw adeg, os ydych yn defnyddio amrywiaeth, beth sy'n mynd i ddigwydd i'r hambyrddau 740 00:30:53,090 --> 00:30:54,173 ydych yn ceisio ei roi i lawr? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Mae pob hawl. 743 00:30:55,670 --> 00:30:57,490 Rydych yn unig yn mynd i yn gallu mynd mor uchel. 744 00:30:57,490 --> 00:31:00,156 Ac yr wyf yn meddwl yn Mather eu bod yn cilfachog mewn gwirionedd yn yr agoriad. 745 00:31:00,156 --> 00:31:01,950 Felly, yn wir, mae bron yn fel Mather yn defnyddio 746 00:31:01,950 --> 00:31:03,783 amrywiaeth o faint penodol, oherwydd eich bod dim ond 747 00:31:03,783 --> 00:31:08,302 ffitio cymaint o hambyrddau yn y agoriad yn y wal i lawr yn is na'r pengliniau pobl. 748 00:31:08,302 --> 00:31:10,010 Ac felly a allai fod yn Dywedodd i fod yn array, 749 00:31:10,010 --> 00:31:14,300 ond gallem yn sicr yn gweithredu hynny yn fwy cyffredinol gyda rhestr cysylltiedig. 750 00:31:14,300 --> 00:31:16,390 >> Wel, beth am strwythur data arall? 751 00:31:16,390 --> 00:31:18,760 Gadewch i mi dynnu i fyny un arall weledol yma. 752 00:31:18,760 --> 00:31:24,710 Rhywbeth fel beth am yr un yma? 753 00:31:24,710 --> 00:31:28,920 Pam y gallai fod yn ddefnyddiol i beidio â chael rhywbeth mor ffansi fel trie, a oedd 754 00:31:28,920 --> 00:31:32,370 gwelsom roedd gan y rhain nodau eang iawn, pob un ohonynt yn mewn arae? 755 00:31:32,370 --> 00:31:35,740 Ond beth os ydym yn ei wneud rhywbeth mwy yn syml, fel hen goeden deulu ysgolion, 756 00:31:35,740 --> 00:31:38,110 mae pob un o'i nodau yma yn unig storio rhif. 757 00:31:38,110 --> 00:31:42,180 Yn lle enw neu un o ddisgynyddion yn unig storio rhif fel hyn. 758 00:31:42,180 --> 00:31:45,250 >> Wel, mae'r jargon a ddefnyddiwn yng strwythurau data yn y ddwy ceisiau 759 00:31:45,250 --> 00:31:49,510 a choed, lle mae trie, unwaith eto, yn dim ond un y mae ei nodau yn arrays, 760 00:31:49,510 --> 00:31:51,680 yn dal i fod yr hyn yr ydych efallai defnyddio o radd ysgol 761 00:31:51,680 --> 00:31:53,860 pan fyddwch yn gwneud teulu dail tree-- ac mae'r gwraidd 762 00:31:53,860 --> 00:31:57,250 y goeden a phlant yr rhieni a brodyr a chwiorydd o hynny. 763 00:31:57,250 --> 00:32:03,670 Ac efallai y byddwn yn gweithredu coeden, er enghraifft, mor syml fel hyn. 764 00:32:03,670 --> 00:32:07,420 Mae coeden, os yw'n fel nod, un o cylchoedd hyn sydd â rhif, 765 00:32:07,420 --> 00:32:09,947 nid yw'n mynd i gael un pwyntydd, ond dau. 766 00:32:09,947 --> 00:32:11,780 A chyn gynted ag y byddwch yn ychwanegu ail pwyntydd, rydych 767 00:32:11,780 --> 00:32:13,905 Gall mewn gwirionedd yn awr yn gwneud math o ddata dau ddimensiwn 768 00:32:13,905 --> 00:32:14,780 strwythurau yn y cof. 769 00:32:14,780 --> 00:32:16,660 Mae llawer fel dau ddimensiwn array, gallwch 770 00:32:16,660 --> 00:32:18,904 yn cael y math o dau-ddimensiwn rhestrau cysylltiedig ond mae rhai 771 00:32:18,904 --> 00:32:20,820 sy'n dilyn patrwm lle nad oes cylchoedd. 772 00:32:20,820 --> 00:32:24,487 Mae'n wir goeden gydag un ffordd nain neu daid i fyny yma ac yna 773 00:32:24,487 --> 00:32:27,320 rhai rhieni a phlant a wyrion a gor-wyrion. 774 00:32:27,320 --> 00:32:28,370 ac yn y blaen. 775 00:32:28,370 --> 00:32:32,390 >> Ond yr hyn sy'n wir yn daclus am hyn hefyd, dim ond i chi canfod gydag ychydig o god, 776 00:32:32,390 --> 00:32:35,370 recursion galw yn ôl o dro yn ôl, lle 777 00:32:35,370 --> 00:32:38,220 byddwch yn ysgrifennu swyddogaeth sy'n galw ei hun. 778 00:32:38,220 --> 00:32:41,140 Mae hwn yn gyfle hyfryd i weithredu rhywbeth 779 00:32:41,140 --> 00:32:42,920 fel recursion, gan fod yn ystyried hyn. 780 00:32:42,920 --> 00:32:43,860 >> Mae hwn yn goeden. 781 00:32:43,860 --> 00:32:48,040 Ac rwyf wedi bod ychydig o rhefrol â sut Rhoddais y cyfanrifau i'r stryd. 782 00:32:48,040 --> 00:32:51,020 Cymaint felly fel bod ganddi arbennig name-- coeden chwiliad deuaidd. 783 00:32:51,020 --> 00:32:53,460 Nawr rydym wedi clywed am deuaidd chwilio, ond gallwch chi 784 00:32:53,460 --> 00:32:55,180 gweithio tuag yn ôl o'r enw peth hwn? 785 00:32:55,180 --> 00:32:59,280 Beth yw'r patrwm o sut yr wyf yn mewnosodir y cyfanrifau i mewn i goeden hon? 786 00:32:59,280 --> 00:33:00,696 Dyw hi ddim yn fympwyol. 787 00:33:00,696 --> 00:33:01,570 Mae rhywfaint o batrwm. 788 00:33:01,570 --> 00:33:02,090 Yeah. 789 00:33:02,090 --> 00:33:03,370 >> GYNULLEIDFA: rhai llai ar y chwith. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Yeah. 791 00:33:03,690 --> 00:33:05,062 Rhai llai ar y chwith. 792 00:33:05,062 --> 00:33:06,270 Rhai mwy ar y dde. 793 00:33:06,270 --> 00:33:12,940 Fel bod ddatganiad cywir yn rhiant yn fwy na'r ei phlentyn ar y chwith, 794 00:33:12,940 --> 00:33:14,850 ond yn llai na ei phlentyn yn iawn. 795 00:33:14,850 --> 00:33:17,750 A bod ei ben ei hun hyd yn oed yn diffiniad llafar recursive 796 00:33:17,750 --> 00:33:20,500 oherwydd gallwch wneud cais bod un rhesymeg i bob nod 797 00:33:20,500 --> 00:33:23,080 ac mae'n dim ond gwaelodion allan, mae achos sylfaenol os ydych yn 798 00:33:23,080 --> 00:33:25,740 fydd, pan fyddwch yn taro un o y dail, fel petai, 799 00:33:25,740 --> 00:33:28,580 lle mae absenoldeb nad oes gan blant ymhellach. 800 00:33:28,580 --> 00:33:30,614 >> Nawr sut y gallech ddod o hyd i'r rhif 44? 801 00:33:30,614 --> 00:33:32,280 Byddech yn dechrau yn y gwraidd ac yn dweud, EM. 802 00:33:32,280 --> 00:33:35,690 55 Nid yw 44 Felly ydw i eisiau mynd hawl neu ydw i am fynd ar ôl? 803 00:33:35,690 --> 00:33:37,190 Wel, yn amlwg ydych am fynd chwith. 804 00:33:37,190 --> 00:33:40,060 Ac felly mae'n union fel y ffôn Enghraifft lyfr chwilio deuaidd 805 00:33:40,060 --> 00:33:41,099 yn fwy cyffredinol. 806 00:33:41,099 --> 00:33:43,390 Ond rydym yn ei weithredu Erbyn hyn ychydig yn fwy ddeinamig 807 00:33:43,390 --> 00:33:45,339 nag y gallai amrywiaeth ganiatáu. 808 00:33:45,339 --> 00:33:48,130 Ac yn wir, os ydych am edrych yn y cod, ar yr olwg gyntaf yn siwr. 809 00:33:48,130 --> 00:33:49,671 Mae'n edrych fel criw cyfan o linellau. 810 00:33:49,671 --> 00:33:51,220 Ond mae'n hyfryd syml. 811 00:33:51,220 --> 00:33:54,490 Os ydych am i weithredu swyddogaeth Gelwir chwilio sydd â'r diben mewn bywyd 812 00:33:54,490 --> 00:33:57,290 yw i chwilio am werth fel n, yn gyfanrif, 813 00:33:57,290 --> 00:34:01,756 ac rydych yn pasio mewn un pointer-- pwyntydd at y nôd y gwreiddiau, 814 00:34:01,756 --> 00:34:04,380 yn hytrach, o'r goeden o ba gallwch gael mynediad i popeth arall, 815 00:34:04,380 --> 00:34:08,850 yn sylwi pa mor ddirwystr gallwch weithredu'r rhesymeg. 816 00:34:08,850 --> 00:34:10,880 Os yw coeden yn null, yn amlwg nid yw'n yno. 817 00:34:10,880 --> 00:34:11,880 Gadewch i jyst yn dychwelyd ffug. 818 00:34:11,880 --> 00:34:12,000 Hawl? 819 00:34:12,000 --> 00:34:14,040 Os ydych yn ei roi dim byd, does dim byd yno. 820 00:34:14,040 --> 00:34:17,900 >> Else, os n yn llai na arrow coed n-- bellach saeth n, 821 00:34:17,900 --> 00:34:20,670 cofio gwnaethom gyflwyno super yn fyr y diwrnod o'r blaen, 822 00:34:20,670 --> 00:34:25,100 ac mai dim ond yn golygu de-gyfeirio y pwyntydd ac edrych ar y cae a elwir yn n. 823 00:34:25,100 --> 00:34:27,690 Felly, mae'n golygu mynd yno ac edrych ar y cae o'r enw n. 824 00:34:27,690 --> 00:34:33,810 Felly os n, mae'r gwerth a roddir i chi, yn llai na gwerth yn y cyfanrif coed, 825 00:34:33,810 --> 00:34:35,449 ble ydych chi eisiau mynd? 826 00:34:35,449 --> 00:34:36,389 Ar y chwith. 827 00:34:36,389 --> 00:34:37,780 >> Felly, yn sylwi ar y recursion. 828 00:34:37,780 --> 00:34:39,860 Im 'yn returning-- ddim yn wir. 829 00:34:39,860 --> 00:34:40,989 Ddim yn ffug. 830 00:34:40,989 --> 00:34:45,670 Dw i'n dychwelyd beth bynnag yr ateb yn dod o alwad i mi fy hun, gan fynd heibio 831 00:34:45,670 --> 00:34:50,100 mae n unwaith eto, sydd yn ddiangen, ond beth sydd ychydig yn wahanol nawr? 832 00:34:50,100 --> 00:34:51,989 Sut ydw i'n gwneud y broblem yn llai? 833 00:34:51,989 --> 00:34:54,920 Im 'yn pasio i mewn fel yr ail ddadl, nid wraidd y goeden, 834 00:34:54,920 --> 00:34:59,616 ond mae'r plentyn chwith yn yr achos hwn. 835 00:34:59,616 --> 00:35:00,990 Felly rwy'n pasio yn y plentyn chwith. 836 00:35:00,990 --> 00:35:04,720 >> Yn y cyfamser, os n yn fwy na y nod ar hyn o bryd rwy'n edrych ar, 837 00:35:04,720 --> 00:35:06,690 Rwy'n chwilio yr ochr dde. 838 00:35:06,690 --> 00:35:10,880 Else, os nad yw'r goeden yn null, ac os nad yw'r elfen sydd i'r chwith 839 00:35:10,880 --> 00:35:13,240 ac nid yw ar y dde, yr hyn sy'n rhyfeddol yn wir? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Mewn gwirionedd rydym wedi dod o hyd y nod yn cwestiwn, ac felly rydym yn dychwelyd yn wir. 842 00:35:18,440 --> 00:35:21,490 >> Felly, rydym newydd crafu'r wyneb Erbyn hyn mae rhai o'r strwythurau data. 843 00:35:21,490 --> 00:35:24,370 Mewn problem yn gosod pum wnewch chi helpu archwilio'r rhain ymhellach eto, 844 00:35:24,370 --> 00:35:27,250 a byddwch yn cael eich dyluniad dewis o sut i fynd o'i chwmpas hi. 845 00:35:27,250 --> 00:35:30,250 Beth hoffwn i ddod i'r casgliad ar yn unig yw ail teaser 30 846 00:35:30,250 --> 00:35:32,080 o'r hyn sy'n aros am yr wythnos nesaf a thu hwnt. 847 00:35:32,080 --> 00:35:35,390 >> Wrth i ni begin-- diolch byth gallech chi think-- ein trosglwyddo yn araf 848 00:35:35,390 --> 00:35:38,680 o fyd C ac is Manylion gweithredu lefel, 849 00:35:38,680 --> 00:35:42,090 i'r byd lle y gallwn eu cymryd i yn ganiataol bod rhywun arall wedi o'r diwedd 850 00:35:42,090 --> 00:35:44,010 rhoi ar waith y data hyn strwythurau i ni, 851 00:35:44,010 --> 00:35:47,570 a byddwn yn dechrau deall y byd go iawn yn golygu o weithredu 852 00:35:47,570 --> 00:35:50,560 rhaglenni ar y we a gwefannau yn fwy cyffredinol 853 00:35:50,560 --> 00:35:52,910 a hefyd yr union diogelwch goblygiadau mai rydym wedi dim ond 854 00:35:52,910 --> 00:35:54,850 dechrau crafu wyneb. 855 00:35:54,850 --> 00:35:57,320 Dyma beth disgwyl i ni yn y dyddiau sydd i ddod. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO Playback] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -He Ddaeth gyda'r neges, â phrotocol ei holl hun. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Daeth i fyd o greulon waliau tân, llwybryddion yn ddidaro, 861 00:36:30,894 --> 00:36:33,368 a pheryglon llawer gwaeth na marwolaeth. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Mae'n gyflym. 864 00:36:36,236 --> 00:36:37,980 Mae'n gryf. 865 00:36:37,980 --> 00:36:42,830 Mae'n TCP / IP, ac mae ganddo eich cyfeiriad. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors y Net." 868 00:36:48,074 --> 00:36:49,660 [DIWEDD VIDEO Playback] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: Yn dod yr wythnos nesaf. 870 00:36:50,910 --> 00:36:51,880 Cewch eich gweld o hynny. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO Playback] 873 00:36:56,060 --> 00:36:59,240 -ac Yn awr, "Thoughts Deep" gan Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Bob amser yn dechrau darlithoedd gyda, "Mae pob hawl." 876 00:37:05,820 --> 00:37:08,750 Pam na wnewch chi, "Dyma y datrysiad i broblem set yr wythnos hon " 877 00:37:08,750 --> 00:37:12,180 neu "Rydym yn rhoi pob un ohonoch yn A?" 878 00:37:12,180 --> 00:37:13,380 [Chwerthin] 879 00:37:13,380 --> 00:37:15,530 [DIWEDD VIDEO Playback]