1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Mūzikas atskaņošanai] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: Tas ir CS50. 5 00:00:14,010 --> 00:00:18,090 Un tas ir gan sākums un end-- tāpat literally-- gandrīz beigām 6 00:00:18,090 --> 00:00:18,825 Nedēļas seši. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Es domāju, ka man dalīties Mazliet jautru faktu. 9 00:00:22,640 --> 00:00:25,370 Esmu velk to uz augšu no pagājušā semestra datu kopa. 10 00:00:25,370 --> 00:00:29,710 Jūs varat atgādināt, ka mēs lūdzam jūs uz katru p komplekts forma, ja esat noskatījos internetā 11 00:00:29,710 --> 00:00:31,580 vai arī, ja esat apmeklējis personīgi. 12 00:00:31,580 --> 00:00:33,020 Un šeit ir dati. 13 00:00:33,020 --> 00:00:34,710 Tātad šodien bija ļoti prognozējama. 14 00:00:34,710 --> 00:00:37,126 Bet mēs vēlējāmies pavadīt mazliet laika ar jums tomēr. 15 00:00:37,126 --> 00:00:40,599 Vai kāds vēlētos minējumus, kāpēc šis diagramma ir tik jaggy, uz augšu uz leju, uz augšu uz leju, 16 00:00:40,599 --> 00:00:41,265 tik konsekventi? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Ko katrs no virsotnēm un siles pārstāv? 19 00:00:45,130 --> 00:00:46,005 >> Mērķauditorija: [dzirdams] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: Patiesi. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Un vēl Saistošs, nedod Dievs, mēs tur vienu lekciju piektdienā 24 00:00:55,480 --> 00:00:58,960 sākumā semestra, ka tas, ko mēs redzam notikt. 25 00:00:58,960 --> 00:01:03,430 Tātad šodien, mēs baudām mazliet vairāk par datu struktūras. 26 00:01:03,430 --> 00:01:06,660 Un, lai dotu jums vairāk cieta garīgās modelis problēmām pēc pieciem, 27 00:01:06,660 --> 00:01:07,450 kas tagad ir ārā. 28 00:01:07,450 --> 00:01:10,817 Pārrakstīšanās, kur, mēs rokas jums teksta failu daži 100,000 29 00:01:10,817 --> 00:01:12,650 plus angļu vārdus, un jūs nāksies 30 00:01:12,650 --> 00:01:17,770 izdomāt, kā gudri ielādēt tos atmiņā, RAM, izmantojot dažus datus 31 00:01:17,770 --> 00:01:19,330 struktūra jūsu izvēles. 32 00:01:19,330 --> 00:01:22,470 >> Tagad viens no šādiem datu struktūra varētu būt, bet, iespējams, nevajadzētu būt, 33 00:01:22,470 --> 00:01:25,630 Vienkāršota saistīts saraksts, kuru mēs iepazīstinājām pēdējo reizi. 34 00:01:25,630 --> 00:01:29,220 Un saistīts saraksts bija vismaz viena priekšrocība pār masīva. 35 00:01:29,220 --> 00:01:32,096 Kas ir viena priekšrocība saistīts saraksts varbūt? 36 00:01:32,096 --> 00:01:32,950 >> AUDITORIJA: ievietošana. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: ievietošana. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Ko jūs ar to domājat? 40 00:01:35,196 --> 00:01:37,872 >> AUDITORIJA: Anywhere kopā saraksts [nedzirdama]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Labi. 42 00:01:38,770 --> 00:01:42,090 Tātad jūs varat ievietot elementu, kur vien vēlaties vidū saraksta 43 00:01:42,090 --> 00:01:45,490 bez shuffle neko, ko mēs secināja, mūsu šķirošanā 44 00:01:45,490 --> 00:01:47,630 diskusijas, nav vienmēr ir laba lieta, 45 00:01:47,630 --> 00:01:51,200 jo ir nepieciešams laiks, lai faktiski pārvietotos visiem šiem cilvēkiem pa kreisi vai pa labi. 46 00:01:51,200 --> 00:01:55,540 Un tā ar saistīta sarakstu, jūs varat vienkārši piešķirt ar malloc, jaunu mezglu, 47 00:01:55,540 --> 00:01:58,385 un pēc tam atjaunināt pāris pointers-- divi, trīs operācijas max-- 48 00:01:58,385 --> 00:02:01,480 un mēs esam spējīgi slots kādu jebkur stāšanās sarakstā. 49 00:02:01,480 --> 00:02:03,550 >> Kas vēl bija izdevīgi par saistītajā sarakstā? 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 >> Mērķauditorija: [dzirdams] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Malan: Perfect. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfekta. 57 00:02:11,090 --> 00:02:12,070 Tas ir patiešām dinamisks. 58 00:02:12,070 --> 00:02:15,100 Un ka jūs neesat izdarījuši, iepriekš, uz kādu fiksētu lielumu 59 00:02:15,100 --> 00:02:18,750 rieciens atmiņas, kā jūs varētu būt līdz ar masīvu, augšupvērsti kura 60 00:02:18,750 --> 00:02:22,455 ir tas, ka jūs varat piešķirt mezglu tikai pieprasījums tādējādi izmantojot tikai tik daudz vietas 61 00:02:22,455 --> 00:02:23,330 kā jums tiešām ir nepieciešams. 62 00:02:23,330 --> 00:02:26,830 Pretstatā ar masīvu, jūs varētu nejauši piešķirt pārāk maz. 63 00:02:26,830 --> 00:02:28,871 Un tad tas ir tikai gatavojas būt sāpes kaklā 64 00:02:28,871 --> 00:02:32,440 pārdalīt jaunu lielāku masīvs, kopēt viss vairāk, atbrīvot veco masīvs, 65 00:02:32,440 --> 00:02:33,990 un tad pāriet par jūsu biznesu. 66 00:02:33,990 --> 00:02:37,479 Vai vēl ļaunāk, jūs varētu piešķirt ceļu vairāk atmiņas nekā jums tiešām ir nepieciešams, 67 00:02:37,479 --> 00:02:40,520 un tāpēc jums nāksies ļoti mazapdzīvotos masīvs, lai runāt. 68 00:02:40,520 --> 00:02:44,350 >> Tātad saistīts saraksts dod jums šos priekšrocības dinamisma un elastības 69 00:02:44,350 --> 00:02:46,080 ar ievietošanas un svītrojumiem. 70 00:02:46,080 --> 00:02:48,000 Bet, protams, ir jābūt cena, ko maksā. 71 00:02:48,000 --> 00:02:50,000 Patiesībā, viena no tēmām izpētīts ar viktorīnu nulles 72 00:02:50,000 --> 00:02:52,430 bija pāris no kompromisiem mēs esam redzējuši līdz šim. 73 00:02:52,430 --> 00:02:56,161 Tātad, kāda ir cena, kas samaksāta vai negatīvie saistītajā sarakstā? 74 00:02:56,161 --> 00:02:56,660 Yeah. 75 00:02:56,660 --> 00:02:57,560 >> Mērķauditorija: Nav brīvpiekļuves. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: Nav brīvpiekļuves. 77 00:02:58,809 --> 00:02:59,540 Bet kurš rūpējas? 78 00:02:59,540 --> 00:03:01,546 Brīvpiekļuves neizklausās pārliecinoši. 79 00:03:01,546 --> 00:03:02,421 >> Mērķauditorija: [dzirdams] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Tieši tā. 82 00:03:05,740 --> 00:03:07,580 Ja jūs vēlaties, lai būtu noteiktu algorithm-- 83 00:03:07,580 --> 00:03:10,170 un ļaujiet man tiešām ierosinās bināro meklēšanu it īpaši, kas 84 00:03:10,170 --> 00:03:12,600 ir viens, mēs esam izmanto diezgan bit-- Ja jums nav izlases piekļuves, 85 00:03:12,600 --> 00:03:15,516 Jūs nevarat darīt, ka vienkāršu aritmētiku atrast līdzīgi vidējā elementa 86 00:03:15,516 --> 00:03:16,530 un lekt tiesības uz to. 87 00:03:16,530 --> 00:03:20,239 Jums tā vietā ir jāsāk pie pirmā elements, un lineāri meklēt no kreisās 88 00:03:20,239 --> 00:03:22,780 uz labo pusi, ja jūs vēlaties, lai atrastu vidējā vai jebkurš cits elements. 89 00:03:22,780 --> 00:03:24,410 >> Mērķauditorija: Tas, iespējams, aizņem vairāk atmiņas. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: Stājas vairāk atmiņas. 91 00:03:25,040 --> 00:03:27,464 Kur ir tas, ka papildu izmaksas nāk no atmiņas? 92 00:03:27,464 --> 00:03:28,339 >> Mērķauditorija: [dzirdams] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Tieši tā. 95 00:03:33,440 --> 00:03:35,679 Tādā gadījumā šeit, mums bija saistīts saraksts veseliem skaitļiem, 96 00:03:35,679 --> 00:03:37,470 un tomēr mēs esam divkāršojies atmiņas apjomu, 97 00:03:37,470 --> 00:03:39,680 mums vajag, ko arī uzglabājot šīs norādes. 98 00:03:39,680 --> 00:03:42,090 Tagad mazāk liels darījumu, kā Jūsu structs get lielāks 99 00:03:42,090 --> 00:03:45,320 un jūs uzglabātu nevis numuru, bet varbūt students vai kādu citu objektu. 100 00:03:45,320 --> 00:03:46,880 Bet jautājums, protams, paliek. 101 00:03:46,880 --> 00:03:49,421 Un tā vairākas darbībām uz saistītiem sarakstiem tika saukta 102 00:03:49,421 --> 00:03:50,570 bija lielais O N- lineāra. 103 00:03:50,570 --> 00:03:54,730 Lietas, piemēram, ievietošanas vai meklēšanas vai dzēšanu, ja elementu 104 00:03:54,730 --> 00:03:57,720 gadījās būt pašās beigās sarakstu, vai tas ir sakārtoti vai ne. 105 00:03:57,720 --> 00:04:01,167 >> Dažreiz jūs varētu saņemt laimīgs un tā apakšējā robeža par šīm darbībām 106 00:04:01,167 --> 00:04:04,250 varētu būt arī nemainīgs laiku, ja jūs esat vienmēr meklē pirmo elementu, 107 00:04:04,250 --> 00:04:05,070 piemēram. 108 00:04:05,070 --> 00:04:09,360 Bet galu galā, mēs apsolījām lai sasniegtu Svētais Grāls 109 00:04:09,360 --> 00:04:12,630 datu struktūras, vai tuvinot to, 110 00:04:12,630 --> 00:04:14,290 veidā pastāvīgu laiku. 111 00:04:14,290 --> 00:04:17,579 Vai mēs varam atrast elementus vai pievienot elementus vai noņemt elementus no saraksta? 112 00:04:17,579 --> 00:04:19,059 Mēs redzēsim pavisam drīz. 113 00:04:19,059 --> 00:04:21,100 Un izrādās, ka viens mehānismu, mēs esam 114 00:04:21,100 --> 00:04:23,464 gatavojas sākt lietot jau šodien, Gada izmantošana p noteikti pieci, 115 00:04:23,464 --> 00:04:24,630 faktiski ir diezgan pazīstams. 116 00:04:24,630 --> 00:04:27,430 Piemēram, ja tas ir ķekars no eksāmenu grāmatas, katrs no kuriem 117 00:04:27,430 --> 00:04:29,660 ir studentu pirmā vārds un uzvārds, par to, 118 00:04:29,660 --> 00:04:31,820 un es tos paceltu no beigās eksāmenu, 119 00:04:31,820 --> 00:04:33,746 un viņi visi ir diezgan daudz nejaušā secībā, 120 00:04:33,746 --> 00:04:36,370 un mēs gribam, lai iet par šķirošanas šie eksāmeni tā, ka pēc tam, kad šķirotas 121 00:04:36,370 --> 00:04:38,661 tas ir tikai daudz vieglāk un ātrāk nodot tos atpakaļ ārā 122 00:04:38,661 --> 00:04:40,030 studentiem alfabēta. 123 00:04:40,030 --> 00:04:42,770 Kādi būtu jūsu instinkti būs par kaudzi eksāmeniem kā šis? 124 00:04:42,770 --> 00:04:45,019 >> Nu, ja jūs, piemēram, man, jūs var redzēt, ka tas ir m, 125 00:04:45,019 --> 00:04:48,505 tāpēc es esmu gatavojas veida nodot to vērā, ja šī ir mana galda vai manu grīdas kur 126 00:04:48,505 --> 00:04:50,650 Es esmu izplatās lietas out-- vai manu masīvs really-- 127 00:04:50,650 --> 00:04:52,210 Es varētu nodot visas MS tur. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Lūk A. Tāpēc es varētu ielieciet As nekā šeit. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Lūk, vēl viens A. Es eju likt, ka vairāk nekā šeit. 132 00:04:57,980 --> 00:05:02,490 Lūk Z. Šeit ir vēl viens M. Un tā Es varētu sākt pelnīt kaudzēm, kā šis. 133 00:05:02,490 --> 00:05:06,620 Un tad varbūt es gribētu iet vēlāk un kārtot ļoti nitpicky-ly kārtošanas 134 00:05:06,620 --> 00:05:07,710 individuālie pāļi. 135 00:05:07,710 --> 00:05:11,300 Bet jautājums ir es varētu meklēt pie ieejas, ka es esmu roku 136 00:05:11,300 --> 00:05:14,016 un es varētu veikt dažas aprēķināts lēmumu, pamatojoties uz šo ieguldījumu. 137 00:05:14,016 --> 00:05:15,640 Ja tas sākas ar, ielieciet to tur. 138 00:05:15,640 --> 00:05:18,980 Ja tas sākas ar Z, ielieciet to vairāk tur, un viss pa vidu. 139 00:05:18,980 --> 00:05:22,730 >> Tātad tas ir paņēmiens, kas ir parasti sauc par hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 kas parasti nozīmē, ņemot par ievadi, un, izmantojot šo ieguldījumu, lai aprēķinātu 141 00:05:26,550 --> 00:05:30,940 vērtība, parasti skaitlis, un ka skaits ir indekss par glabāšanā 142 00:05:30,940 --> 00:05:32,260 konteineru, tāpat kā masīvs. 143 00:05:32,260 --> 00:05:35,490 Tātad citiem vārdiem sakot, es varētu būt hash funkcija, kā es to daru manā galvā, 144 00:05:35,490 --> 00:05:37,940 ka, ja es redzu, kāds ir vārds, kas sākas ar A, 145 00:05:37,940 --> 00:05:40,190 Es esmu gatavojas karti, ka līdz nullei manā galvā. 146 00:05:40,190 --> 00:05:44,160 Un, ja es redzu kādu ar Z, es esmu dodas uz karti, kas līdz 25 manā galvā 147 00:05:44,160 --> 00:05:46,220 un pēc tam nodot, ka pēdējais visvairāk kaudzes. 148 00:05:46,220 --> 00:05:50,990 >> Tagad, ja jūs domājat par to nav manas smadzenes bet C programmu, kas varētu numuri 149 00:05:50,990 --> 00:05:53,170 Jūs paļauties uz, lai sasniegtu to pašu rezultātu? 150 00:05:53,170 --> 00:05:55,594 Citiem vārdiem sakot, ja jums bija ASCII rakstzīmju A, 151 00:05:55,594 --> 00:05:57,510 kā jūs noteikt ko spainis likt to? 152 00:05:57,510 --> 00:05:59,801 Jūs, iespējams, nevēlaties ieliec spaini 65, kas 153 00:05:59,801 --> 00:06:01,840 būtu kā tur nesaprotamu iemeslu dēļ. 154 00:06:01,840 --> 00:06:04,320 Ja jūs vēlaties, lai izveidotu attiecībā uz tās ASCII vērtība? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Ja jūs vēlaties darīt, lai tās ASCII vērtība nākt klajā ar gudrāku kausu 157 00:06:08,920 --> 00:06:09,480 nodot to? 158 00:06:09,480 --> 00:06:10,206 >> AUDITORIJA: Mīnus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Jā. 160 00:06:10,956 --> 00:06:13,190 Tātad mīnus vai mīnus īpaši 65, ja tas ir 161 00:06:13,190 --> 00:06:18,240 kapitāla A. Vai 98, ja tas ir mazie burti. 162 00:06:18,240 --> 00:06:21,300 Un lai ļautu mums, ir ļoti vienkārši un ļoti aritmētiski, 163 00:06:21,300 --> 00:06:23,260 likts kaut spainī, piemēram, ka. 164 00:06:23,260 --> 00:06:26,010 Tātad izrādās, mēs faktiski darīt Tas, kā arī pat ar viktorīnas. 165 00:06:26,010 --> 00:06:29,051 >> Lai jūs varētu atgādināt jums riņķoja savu mācīšana Fellow vārds uz vāka. 166 00:06:29,051 --> 00:06:32,270 Un tika organizētas TF ir nosaukumi šajās slejās pēc alfabēta, 167 00:06:32,270 --> 00:06:34,400 labi, ticiet vai ne, kad visi 80 plus mums 168 00:06:34,400 --> 00:06:37,800 sanāca kopā citiem nakts pakāpē, pēdējais solis mūsu šķirošanas procesā 169 00:06:37,800 --> 00:06:41,830 ir hash viktorīnas uz lielas telpu grīdas pie [dzirdams] 170 00:06:41,830 --> 00:06:45,110 un likt ikviena viktorīnas out tieši to TF Rīkojuma 171 00:06:45,110 --> 00:06:47,700 vārdi vāka, jo tad tas ir daudz vieglāk mums 172 00:06:47,700 --> 00:06:51,290 meklēt, izmantojot šim, izmantojot lineāru meklēt vai sava veida gudrība 173 00:06:51,290 --> 00:06:54,050 par TF, lai atrastu viņa vai viņas studentu viktorīnas. 174 00:06:54,050 --> 00:06:56,060 >> Tātad šī ideja sajaukšanai ka jūs redzēsiet, ir 175 00:06:56,060 --> 00:07:00,520 diezgan spēcīgs, faktiski ir diezgan parasts un ļoti intuitīvu, 176 00:07:00,520 --> 00:07:03,000 līdzīgi varbūt sadalīt un Iekarot bija nedēļā nulles. 177 00:07:03,000 --> 00:07:05,250 Es ātri uz priekšu, lai hackathon pirms pāris gadiem. 178 00:07:05,250 --> 00:07:08,040 Tas bija Zamyla un pāris pārējie darbinieki apsveikuma studenti 179 00:07:08,040 --> 00:07:09,030 jo tie nāca. 180 00:07:09,030 --> 00:07:12,680 Un mums bija visu ķekars salocīšanu galdi tur ar nosaukumu atzīmēm. 181 00:07:12,680 --> 00:07:15,380 Un mums bija nosaukums tagus organizēja ar patīk, jo vairāk nekā tur 182 00:07:15,380 --> 00:07:16,690 un Zs tur. 183 00:07:16,690 --> 00:07:20,350 Un tāpēc viens no TFS ļoti gudri rakstīja to kā instrukciju 184 00:07:20,350 --> 00:07:21,030 par dienu. 185 00:07:21,030 --> 00:07:24,480 Un 12. nedēļā semestra šā visi, kas perfektu sajūtu un visiem 186 00:07:24,480 --> 00:07:25,310 zināja, ko darīt. 187 00:07:25,310 --> 00:07:27,900 Bet jebkurā laikā jūs esat ievietots rindā tādā pašā veidā, 188 00:07:27,900 --> 00:07:30,272 jūs īstenojot pats jēdziens hash. 189 00:07:30,272 --> 00:07:31,730 Tāpēc pieņemsim formalizēt tas mazliet. 190 00:07:31,730 --> 00:07:32,890 Šeit ir masīvs. 191 00:07:32,890 --> 00:07:36,820 Tas ir izstrādāts, lai būtu nedaudz plata tikai attēlot vizuāli, 192 00:07:36,820 --> 00:07:38,920 ka mēs varētu nodot stīgas kaut kas līdzīgs šim. 193 00:07:38,920 --> 00:07:41,970 Un tas ir masīvs acīmredzami izmērs 26 kopā. 194 00:07:41,970 --> 00:07:43,935 Un lieta tiek saukta galda patvaļīgi. 195 00:07:43,935 --> 00:07:48,930 Taču tas ir tikai mākslinieka pārsūtīšanu par to hash tabulu varētu būt. 196 00:07:48,930 --> 00:07:52,799 >> Tātad hash tabulu, tagad gatavojas būt augstāka līmeņa datu struktūras. 197 00:07:52,799 --> 00:07:54,840 Beigās dienas mēs esam par to, lai pārliecinātos, ka jums 198 00:07:54,840 --> 00:07:58,700 var īstenot hash tabulu, kurā ir daudz, piemēram check-in line 199 00:07:58,700 --> 00:08:02,059 pie hackathon daudz kā šis tabula izmanto šķirošanas eksāmenu grāmatas. 200 00:08:02,059 --> 00:08:03,850 Bet hash tabula ir kārtot šo augsto līmeni 201 00:08:03,850 --> 00:08:08,250 jēdziens, kas varētu izmantot masīvu zem motora pārsegs, lai to īstenotu, 202 00:08:08,250 --> 00:08:11,890 vai tas varētu izmantot garuma sarakstu, vai pat varbūt daži citi datu struktūras. 203 00:08:11,890 --> 00:08:15,590 Un tagad tas ir theme-- ņemšana dažas no šīm galvenajām sastāvdaļām 204 00:08:15,590 --> 00:08:18,310 piemēram, masīvu un šīs ēkas bloķēt tagad garuma saraksta 205 00:08:18,310 --> 00:08:21,740 un redzēt to, ko vēl mēs varam veidot uz augšu no tiem, piemēram, sastāvdaļas 206 00:08:21,740 --> 00:08:26,550 uz recepti, padarot vairāk un vairāk interesantas un noderīgas galīgie rezultāti. 207 00:08:26,550 --> 00:08:28,680 >> Tātad ar hash tabulu mēs varētu īstenot 208 00:08:28,680 --> 00:08:32,540 atmiņā gleznieciski kā šis, bet cik tas varētu tiešām būt kodēti uz augšu? 209 00:08:32,540 --> 00:08:33,789 Nu, varbūt, jo vienkārši tas ir. 210 00:08:33,789 --> 00:08:38,270 Ja jauda visos cepures, ir tikai daži constant-- piemēram 26, 211 00:08:38,270 --> 00:08:42,030 26 burti alphabet-- Es varētu piezvanīt savai mainīgo galda, 212 00:08:42,030 --> 00:08:45,630 un es varētu apgalvot, ka es esmu gatavojas likts char zvaigznes tur, vai auklas. 213 00:08:45,630 --> 00:08:49,880 Tāpēc tas ir tik vienkārši, kā tas, ja jūs vēlamies īstenot hash tabulu. 214 00:08:49,880 --> 00:08:51,490 Un tomēr, tas ir patiešām vienkārši masīvs. 215 00:08:51,490 --> 00:08:53,198 Bet atkal, hash Tagad tabula ir tas, ko mēs 216 00:08:53,198 --> 00:08:57,470 zvaniet abstrakts datu tips, kas ir tikai veida konceptuāla layering uz augšu 217 00:08:57,470 --> 00:09:00,780 kaut ko vairāk ikdienišķa Tagad patīk masīvs. 218 00:09:00,780 --> 00:09:02,960 >> Tagad, kā mēs iet par problēmu risināšanai? 219 00:09:02,960 --> 00:09:06,980 Nu, agrāk man bija greznība no pietiekoši galda telpa šeit 220 00:09:06,980 --> 00:09:09,460 lai es varētu likt viktorīnas jebkur es gribēju. 221 00:09:09,460 --> 00:09:10,620 Tātad, kā varētu iet šeit. 222 00:09:10,620 --> 00:09:12,100 Zs varētu iet šeit. 223 00:09:12,100 --> 00:09:13,230 Ms varētu iet šeit. 224 00:09:13,230 --> 00:09:14,740 Un tad man bija dažas papildu telpas. 225 00:09:14,740 --> 00:09:18,740 Bet tas ir mazliet apkrāptu tiesības tagad, jo šajā tabulā, ja es patiešām 226 00:09:18,740 --> 00:09:22,720 domāja par to, kā masīvu, ir tikai būs par kādu fiksētu izmēru. 227 00:09:22,720 --> 00:09:25,380 >> Tātad tehniski, ja es pull up cita studenta viktorīnas 228 00:09:25,380 --> 00:09:28,490 un redzēt, ak, šis personas vārds sākas ar A pārāk, 229 00:09:28,490 --> 00:09:30,980 Es veida gribu likt to tur. 230 00:09:30,980 --> 00:09:34,740 Bet tiklīdz man to tur, ja šī tabula tiešām ir masīvs, 231 00:09:34,740 --> 00:09:37,840 Es esmu būs svarīgi vai clobbering kurš šī studenta viktorīna ir. 232 00:09:37,840 --> 00:09:38,340 Taisnība? 233 00:09:38,340 --> 00:09:41,972 Ja tas ir masīvs, tikai viena lieta, var iet uz katru no šīm šūnām vai elementu. 234 00:09:41,972 --> 00:09:43,680 Un tāpēc es veida ir atlasīt un izvēlēties. 235 00:09:43,680 --> 00:09:45,735 >> Tagad agrāk es veida cheated un izdarīja tā, vai I 236 00:09:45,735 --> 00:09:47,526 tikko veida kaudzē tos virs otra. 237 00:09:47,526 --> 00:09:49,170 Bet tas nav gatavojas lidot kodu. 238 00:09:49,170 --> 00:09:52,260 Tātad, kur es varētu likt otrais students, kura vārds 239 00:09:52,260 --> 00:09:54,964 ir, ja visi man bija tas pieejami galda telpa? 240 00:09:54,964 --> 00:09:57,880 Un es esmu, ko izmanto trīs slots un to izskatās, ka tur ir tikai daži citi. 241 00:09:57,880 --> 00:09:58,959 Ko jūs varētu darīt? 242 00:09:58,959 --> 00:09:59,834 Mērķauditorija: [dzirdams] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Jā. 245 00:10:01,315 --> 00:10:02,370 Varbūt pieņemsim tikai glabā to vienkārši. 246 00:10:02,370 --> 00:10:02,660 Taisnība? 247 00:10:02,660 --> 00:10:04,243 Tas neiederas, kur es gribu, lai to. 248 00:10:04,243 --> 00:10:07,450 Tāpēc es esmu gatavojas nodot to tehniski kur B varētu iet. 249 00:10:07,450 --> 00:10:09,932 Tagad, protams, es esmu sāk gleznot sevi stūrī. 250 00:10:09,932 --> 00:10:11,890 Ja es nokļūt studentam kura vārds ir faktiski B, 251 00:10:11,890 --> 00:10:14,840 Tagad B tiks pārcelts nedaudz priekšu, kā varētu notikt, yep, 252 00:10:14,840 --> 00:10:17,530 ja tas ir B, tagad tas ir iet šeit. 253 00:10:17,530 --> 00:10:20,180 >> Un tā tas ļoti ātri varētu kļūt problemātiska, 254 00:10:20,180 --> 00:10:23,850 bet tas ir paņēmiens, kas faktiski ir minēta kā lineāra zondēšana, 255 00:10:23,850 --> 00:10:26,650 kurā jūs tikai apsvērt savu masīvs būt pa līniju. 256 00:10:26,650 --> 00:10:29,680 Un jūs vienkārši veida zonde vai pārbauda katru pieejamo elementu 257 00:10:29,680 --> 00:10:31,360 meklē pieejams uz vietas. 258 00:10:31,360 --> 00:10:34,010 Un, tiklīdz jūs atradīsiet viens, jūs piliens to tur. 259 00:10:34,010 --> 00:10:38,390 >> Tagad cena ir samaksāta tagad šo risinājumu ir tas, ko? 260 00:10:38,390 --> 00:10:41,300 Mums ir fiksēta izmēra masīvs, un, kad es ievietot vārdus 261 00:10:41,300 --> 00:10:44,059 uz to, vismaz sākumā, kas ir darba laiks ievietošanas 262 00:10:44,059 --> 00:10:46,350 liekot studentiem " viktorīnas Labajā spaiņiem? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O, ko? 265 00:10:50,002 --> 00:10:51,147 >> AUDITORIJA: n. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: Es dzirdēju Big O n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Nav taisnība. 269 00:10:54,300 --> 00:10:56,490 Bet mēs kaitināt intervālu kāpēc tikai brīdi. 270 00:10:56,490 --> 00:10:57,702 Kas vēl tas varētu būt? 271 00:10:57,702 --> 00:10:58,755 >> Mērķauditorija: [dzirdams] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: Un ļaujiet man darīt to vizuāli. 273 00:11:00,380 --> 00:11:04,720 Tātad pieņemsim, ka šī ir vēstule S. 274 00:11:04,720 --> 00:11:05,604 >> Mērķauditorija: Tas ir viens. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: Tas ir viens. 276 00:11:06,520 --> 00:11:06,710 Taisnība? 277 00:11:06,710 --> 00:11:08,950 Tas ir masīvs, kas nozīmē, ka mums ir brīva piekļuve. 278 00:11:08,950 --> 00:11:11,790 Un, ja mēs domājam par to kā nulle, un tas, kā 25, 279 00:11:11,790 --> 00:11:13,800 un mēs saprotam, ka, ak, šeit ir mana ieejas S, 280 00:11:13,800 --> 00:11:16,350 Es, protams, var pārvērst S, ASCII raksturs, 281 00:11:16,350 --> 00:11:18,540 ar attiecīgu skaitu no nulles līdz 25 282 00:11:18,540 --> 00:11:20,910 un tad uzreiz nodot to, ja tā pieder. 283 00:11:20,910 --> 00:11:26,120 >> Bet, protams, tiklīdz es nokļūt Otrs cilvēks, kurš vārds ir vai B vai C 284 00:11:26,120 --> 00:11:29,300 galu galā, ja es esmu, ko izmanto lineārs zondēšana kā manu risinājumu, 285 00:11:29,300 --> 00:11:31,360 darba laiks ievietošana sliktākajā gadījumā 286 00:11:31,360 --> 00:11:33,120 ir faktiski gatavojas pāriet uz ko? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Un es to dzirdu to šeit pareizi sākumā. 289 00:11:36,045 --> 00:11:36,920 Mērķauditorija: [dzirdams] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Tātad tas ir n patiešām reiz Jums ir pietiekami lielu datu kopu. 291 00:11:41,620 --> 00:11:44,410 Tātad, no vienas puses, ja Jūsu masīvs ir pietiekami liels 292 00:11:44,410 --> 00:11:48,287 un jūsu dati ir maz pietiekami, jūs saņemt šo skaisto pastāvīgu laiku. 293 00:11:48,287 --> 00:11:50,620 Bet, tiklīdz jūs sākat arvien vairāk un vairāk elementu, 294 00:11:50,620 --> 00:11:53,200 un tikai statistiski jums vairāk cilvēku ar burtu 295 00:11:53,200 --> 00:11:56,030 Kā to vārds vai burts B, tas var potenciāli 296 00:11:56,030 --> 00:11:57,900 pāriet uz kaut ko vairāk lineāra. 297 00:11:57,900 --> 00:11:59,640 Tāpēc ne gluži ideāls. 298 00:11:59,640 --> 00:12:00,690 Lai mēs varētu darīt labāk? 299 00:12:00,690 --> 00:12:03,210 >> Nu, kāda bija mūsu risinājums, pirms kad mēs 300 00:12:03,210 --> 00:12:06,820 vēlas, lai būtu vairāk nekā dinamiku kaut kā masīva atļauts? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 Mērķauditorija: [dzirdams] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Ko mēs ieviest? 304 00:12:10,030 --> 00:12:10,530 Yeah. 305 00:12:10,530 --> 00:12:11,430 Tātad saistīts saraksts. 306 00:12:11,430 --> 00:12:14,430 Nu, pieņemsim redzēt, kas saistīta sarakstu varētu darīt mums vietā. 307 00:12:14,430 --> 00:12:17,630 Nu, ļaujiet man ierosinu izdarīt attēlu šādi. 308 00:12:17,630 --> 00:12:19,620 Tagad tas ir atšķirīgs bilde no piemēru 309 00:12:19,620 --> 00:12:24,750 no cita teksta, faktiski, ka ir faktiski izmantojot masīvu izmēru 31. 310 00:12:24,750 --> 00:12:28,220 Un šis autors vienkārši nolēma hash virknes 311 00:12:28,220 --> 00:12:32,430 nevis pamatojoties uz personas vārdu, bet, pamatojoties uz to birthdates. 312 00:12:32,430 --> 00:12:35,680 Neatkarīgi no mēneša, viņi skatīja Ja jūs esat dzimis no pirmā mēneša 313 00:12:35,680 --> 00:12:39,580 vai 31. mēnesi, autors būs hash, pamatojoties uz šo vērtību, 314 00:12:39,580 --> 00:12:44,154 lai izplatītu vārdus out mazliet vairāk nekā tikai 26 punkti varētu pieļaut. 315 00:12:44,154 --> 00:12:47,320 Un varbūt tas ir nedaudz vairāk vienota nekā iet ar alfabēta burtiem, 316 00:12:47,320 --> 00:12:50,236 jo, protams, tur ir iespējams vairāk cilvēku pasaulē ar vārdiem 317 00:12:50,236 --> 00:12:54,020 ka sākt ar nekā noteikti daži citi alfabēta burti. 318 00:12:54,020 --> 00:12:56,380 Tāpēc varbūt tas ir nedaudz vienotāka, pieņemot 319 00:12:56,380 --> 00:12:58,640 vienota izplatīšanas zīdaiņu visā mēnesī. 320 00:12:58,640 --> 00:12:59,990 >> Bet, protams, tas joprojām ir nepilnīgs. 321 00:12:59,990 --> 00:13:00,370 Taisnība? 322 00:13:00,370 --> 00:13:01,370 Mēs esam, kam sadursmes. 323 00:13:01,370 --> 00:13:04,680 Vairāki cilvēki šo datu struktūra joprojām 324 00:13:04,680 --> 00:13:08,432 ar tādu pašu dzimšanas vismaz jūs esat neatkarīgi no mēneša. 325 00:13:08,432 --> 00:13:09,640 Bet ko ir autors darījis? 326 00:13:09,640 --> 00:13:13,427 Nu, izskatās, ka mums ir masīvs kreisajā pusē novilkta vertikāli, 327 00:13:13,427 --> 00:13:15,010 bet tas ir tikai mākslinieka atveidojumu. 328 00:13:15,010 --> 00:13:18,009 Tas nav svarīgi, kādā virzienā jūs izdarīt masīvs, tas joprojām ir masīvs. 329 00:13:18,009 --> 00:13:20,225 Kas tas ir masīvs acīmredzot? 330 00:13:20,225 --> 00:13:21,500 >> Mērķauditorija: Saistīts saraksts. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Jā. 332 00:13:21,650 --> 00:13:23,490 Izskatās, ka tas ir masīvs saistīts saraksts. 333 00:13:23,490 --> 00:13:26,490 Tātad vēlreiz, lai šī viedokļa veida Izmantot šo datu struktūras tagad 334 00:13:26,490 --> 00:13:28,550 kā sastāvdaļas uz vairāk interesanti risinājumi, 335 00:13:28,550 --> 00:13:30,862 Jūs varat veikt absolūti būtisks, tāpat kā masīvs, 336 00:13:30,862 --> 00:13:33,320 un tad kaut ko vairāk interesanti kā saistīts saraksts 337 00:13:33,320 --> 00:13:36,660 un pat apvienot tos pat interesantāku datu struktūra. 338 00:13:36,660 --> 00:13:39,630 Un tiešām, tas arī būtu saukt hash tabulu, 339 00:13:39,630 --> 00:13:42,610 kuru masīvs ir tiešām hash tabulu, 340 00:13:42,610 --> 00:13:45,600 bet hash tabulu ir ķēdes, tā sakot, 341 00:13:45,600 --> 00:13:50,220 kas var augt vai sarukšana, pamatojoties uz elementu skaits vēlaties ievietot. 342 00:13:50,220 --> 00:13:52,990 >> Tagad, attiecīgi, kas ir darbības laiks tagad? 343 00:13:52,990 --> 00:13:58,030 Ja es gribu, lai ievietotu kādu kuru dzimšanas diena ir 31. oktobris, 344 00:13:58,030 --> 00:13:59,040 kur viņš vai viņa iet? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Labi. 347 00:14:01,030 --> 00:14:02,819 Tajā pašā apakšā, kur ir teikts 31. 348 00:14:02,819 --> 00:14:03,610 Un tas ir lieliski. 349 00:14:03,610 --> 00:14:05,060 Tas bija nemainīgs laiks. 350 00:14:05,060 --> 00:14:08,760 Bet ko tad, ja mēs atrast kādu citu kuru dzimšanas diena ir, pieņemsim redzēt, 351 00:14:08,760 --> 00:14:10,950 Oktobris, novembris, decembris 31? 352 00:14:10,950 --> 00:14:12,790 Ja viņš vai viņa gatavojas doties? 353 00:14:12,790 --> 00:14:13,290 Pats. 354 00:14:13,290 --> 00:14:13,970 Divi solis gan. 355 00:14:13,970 --> 00:14:15,303 Tas ir nemainīgs, lai gan nav tā? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Labi. 358 00:14:16,860 --> 00:14:17,840 Šobrīd tas ir. 359 00:14:17,840 --> 00:14:20,570 Tomēr vispārējā gadījumā, jo vairāk cilvēku, mēs pievienot, 360 00:14:20,570 --> 00:14:23,790 probabilistically, mēs ejam lai iegūtu vairāk un vairāk sadursmes. 361 00:14:23,790 --> 00:14:26,820 >> Tagad tas ir maz labāk, jo tehniski 362 00:14:26,820 --> 00:14:34,580 tagad mana ķēdes varētu būt sliktākajā gadījumā, cik ilgi? 363 00:14:34,580 --> 00:14:38,890 Ja es ievietot n cilvēkus šo vairāk sarežģītu datu struktūru, n cilvēki, 364 00:14:38,890 --> 00:14:41,080 sliktākajā gadījumā tas būs n. 365 00:14:41,080 --> 00:14:41,815 Kāpēc? 366 00:14:41,815 --> 00:14:43,332 >> Mērķauditorija: Jo, ja visi ir tāda pati dzimšanas, 367 00:14:43,332 --> 00:14:44,545 viņi būs viena rinda. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Perfect. 369 00:14:45,420 --> 00:14:47,480 Tas varētu būt nedaudz izdomāts, bet patiesi sliktākajā gadījumā, 370 00:14:47,480 --> 00:14:50,117 ja visi ir tāda pati dzimšanas diena, ņemot vērā ieejas jums ir, 371 00:14:50,117 --> 00:14:51,950 jūs nāksies masveidā garu ķēdi. 372 00:14:51,950 --> 00:14:54,241 Un tā, jūs varētu to sauc par hash tabulu, bet patiesībā tas ir 373 00:14:54,241 --> 00:14:56,810 tikai masveida saistīts saraksts ar visai daudz izšķērdēta telpu. 374 00:14:56,810 --> 00:15:00,460 Bet vispār, ja mēs pieņemam, ka vismaz dzimšanas dienas ir uniform-- 375 00:15:00,460 --> 00:15:01,750 un tas, iespējams, nav. 376 00:15:01,750 --> 00:15:02,587 Es esmu padarot šo augšu. 377 00:15:02,587 --> 00:15:04,420 Bet, ja mēs pieņemam, lai labad diskusijas 378 00:15:04,420 --> 00:15:07,717 ka tie ir, tad teorētiski, ja tas ir vertikāla pārstāvība 379 00:15:07,717 --> 00:15:11,050 masīva, labi, tad, cerams, jūs esat gatavojas saņemt ķēdes, kas ir, jūs zināt, 380 00:15:11,050 --> 00:15:15,880 aptuveni vienāda garuma, kur katrs no tie veido mēneša dienu. 381 00:15:15,880 --> 00:15:19,930 >> Tagad, ja tur ir 31 dienas mēnesī, tas nozīmē, ka mana darba laika patiešām 382 00:15:19,930 --> 00:15:25,230 ir liels O n bija 31, kas jūtas labāk nekā lineāra. 383 00:15:25,230 --> 00:15:27,950 Bet to, kas bija viens no mūsu saistības pāris nedēļām 384 00:15:27,950 --> 00:15:31,145 atpakaļ, kad tas nonāca pie izteikšanu darba laiks algoritmu? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Tikai tikai apskatīt lielo pasūtījumu termiņā. 387 00:15:35,190 --> 00:15:35,690 Taisnība? 388 00:15:35,690 --> 00:15:37,400 31 noteikti ir noderīga. 389 00:15:37,400 --> 00:15:39,610 Bet tas joprojām ir liels O n. 390 00:15:39,610 --> 00:15:41,730 Bet viena no tēmām problemātisko noteikti pieci 391 00:15:41,730 --> 00:15:43,950 būs uz atzīst, ka absolūti, 392 00:15:43,950 --> 00:15:47,320 asimptotiski, teorētiski šo datu struktūra 393 00:15:47,320 --> 00:15:50,470 nav labāka nekā tikai viens masveida saistīts saraksts. 394 00:15:50,470 --> 00:15:53,550 Un tiešām, sliktākajā gadījumā, tas hash tabulu var pāriet uz to. 395 00:15:53,550 --> 00:15:57,620 >> Bet reālajā pasaulē, ar mums cilvēki ka pašu Mac vai PC, vai kāds 396 00:15:57,620 --> 00:16:01,240 un darbojas reālajā pasaulē programmatūras reālās pasaules datiem, 397 00:16:01,240 --> 00:16:03,260 kas algoritms jūs plānojat dot priekšroku? 398 00:16:03,260 --> 00:16:09,180 Viens, ka notiek gala pasākumus vai viens, kas ņem n dalot ar 31 soļiem 399 00:16:09,180 --> 00:16:12,900 atrast kādu gabals datu vai uzmeklēt kādu informāciju? 400 00:16:12,900 --> 00:16:16,580 Es domāju, absolūti 31 marku atšķirība reālajā pasaulē. 401 00:16:16,580 --> 00:16:18,540 Tas ir 31 reizes ātrāk. 402 00:16:18,540 --> 00:16:20,880 Un mēs, cilvēki, protams, gatavojas novērtējam. 403 00:16:20,880 --> 00:16:23,004 >> Tātad realizēt dihotomiju tur starp faktiski 404 00:16:23,004 --> 00:16:25,920 runājam par lietām teorētiski un asimptotiski kas noteikti 405 00:16:25,920 --> 00:16:28,760 ir vērtība, kā mēs esam redzējuši, bet reālajā pasaulē, 406 00:16:28,760 --> 00:16:32,930 ja jums rūp tikai veicot Cilvēka priecīgi par vispārīgiem ieguldījumiem, 407 00:16:32,930 --> 00:16:36,010 jūs varētu ļoti labi vēlēties pieņemt Fakts, ka, jā, tas ir lineāra, 408 00:16:36,010 --> 00:16:38,360 bet tas ir 31 reizes ātrāks nekā lineāra varētu būt. 409 00:16:38,360 --> 00:16:41,610 Un vēl labāk, mēs ne tikai ir darīt kaut patvaļīgu kā dzimšanas datumu, 410 00:16:41,610 --> 00:16:44,030 mēs varētu tērēt nedaudz vairāk laika un gudrība 411 00:16:44,030 --> 00:16:47,140 un domāt par to, ko mēs varētu darīt, ņemot vērā personas vārds un varbūt 412 00:16:47,140 --> 00:16:50,130 viņu dzimšanas datums apvienot tos, sastāvdaļas izdomāt kaut ko 413 00:16:50,130 --> 00:16:52,720 kas ir patiesi daudz vienota un mazāk jaggy, 414 00:16:52,720 --> 00:16:56,250 lai runāt par šo bildi Pašlaik liecina tas varētu būt. 415 00:16:56,250 --> 00:16:57,750 Kā mēs varētu īstenot šo kodu? 416 00:16:57,750 --> 00:17:00,280 Nu, ļaujiet man ierosinu vienkārši aizņemties kādu sintakse mēs esam 417 00:17:00,280 --> 00:17:01,799 izmanto pāris reizes līdz šim. 418 00:17:01,799 --> 00:17:03,590 Un es esmu gatavojas, lai definētu mezglu, kas atkal 419 00:17:03,590 --> 00:17:06,812 ir vispārējs termins, tikai daži konteiners kādu datu struktūra. 420 00:17:06,812 --> 00:17:09,020 Es esmu gatavojas ierosināt string notiek tur. 421 00:17:09,020 --> 00:17:11,369 Bet mēs esam gatavojas sākt lietot tiem mācību riteņiem off tagad. 422 00:17:11,369 --> 00:17:13,230 >> Ne vairāk CS50 bibliotēka tiešām, ja jūs vēlaties 423 00:17:13,230 --> 00:17:15,230 izmantot to savā finālā projekts, kas ir labi, 424 00:17:15,230 --> 00:17:18,569 bet tagad mēs esam gatavojas pull atpakaļ aizkaru un saka, ka tas ir tikai char zvaigzne. 425 00:17:18,569 --> 00:17:22,069 Tātad vārds tur būs personas vārds jautājumā. 426 00:17:22,069 --> 00:17:25,079 Un tagad man ir saite šeit uz nākamo mezglu 427 00:17:25,079 --> 00:17:28,170 tā, ka šie ir katrs no mezgliem 428 00:17:28,170 --> 00:17:30,950 ķēdē, iespējams, no saistītajā sarakstā. 429 00:17:30,950 --> 00:17:34,090 >> Un tagad, kā es varu paziņot hash pati tabula? 430 00:17:34,090 --> 00:17:36,660 Kā es varu atzīt šo visu struktūru? 431 00:17:36,660 --> 00:17:40,960 Nu, tiešām, daudz, piemēram, es izmantoti rādītāju uz tikai uz saraksta pirmo elementu 432 00:17:40,960 --> 00:17:44,510 pirms, tāpat es varu tikai teikt Man tikai vajag ķekars norādes 433 00:17:44,510 --> 00:17:46,270 lai īstenotu šo visu hash tabulu. 434 00:17:46,270 --> 00:17:49,484 Es esmu nāksies masīvs aicināja tabula hash tabulu. 435 00:17:49,484 --> 00:17:50,900 Tas būs no lieluma jaudu. 436 00:17:50,900 --> 00:17:52,525 Tas, cik daudz elementu var ietilpt tajā. 437 00:17:52,525 --> 00:17:56,180 Un katrs no šiem elementiem šajā masīvs būs mezglu zvaigzne. 438 00:17:56,180 --> 00:17:56,810 Kāpēc? 439 00:17:56,810 --> 00:18:00,160 Nu, par šo attēlu, ko es esmu Īstenojot hash tabulu kā 440 00:18:00,160 --> 00:18:04,330 efektīvi sākums ir tikai šis masīvs, ka mēs esam izdarīt vertikāli, 441 00:18:04,330 --> 00:18:06,820 Katrā no kuru kvadrātu pārstāv rādītāju. 442 00:18:06,820 --> 00:18:09,170 Ka tie, kas ir slīpsvītras caur tiem ir tikai null. 443 00:18:09,170 --> 00:18:11,410 Un tie, kas ir bultas iet uz labo pusi 444 00:18:11,410 --> 00:18:16,140 ir faktiskas norādes uz faktiskajiem mezgliem, ergo sākumu saistītajā sarakstā. 445 00:18:16,140 --> 00:18:19,050 >> Tātad šeit, tad ir, kā mēs varētu īstenot hash tabulu, kas 446 00:18:19,050 --> 00:18:21,580 īsteno atsevišķu Ķēžu. 447 00:18:21,580 --> 00:18:22,840 Tagad mēs varam darīt labāk? 448 00:18:22,840 --> 00:18:25,632 Visas tiesības Es apsolīju pēdējo reizi mēs varētu panākt pastāvīgu laiku. 449 00:18:25,632 --> 00:18:27,381 Un es veida deva jums nemainīgs laika šeit, 450 00:18:27,381 --> 00:18:29,850 bet tad teica, ka nav īsti nemainīgs laiks, jo tas joprojām ir 451 00:18:29,850 --> 00:18:31,890 atkarīgs no kopējā elementu skaits 452 00:18:31,890 --> 00:18:34,500 jūs ievadot stājas datu struktūra. 453 00:18:34,500 --> 00:18:35,980 Bet pieņemsim, ka mēs to darījām. 454 00:18:35,980 --> 00:18:39,550 Ļaujiet man iet atpakaļ uz ekrāna vairāk nekā šeit. 455 00:18:39,550 --> 00:18:44,520 Ļaujiet man arī projicēt šo šeit, skaidra ekrāns, un domāju, ka es to izdarīja. 456 00:18:44,520 --> 00:18:49,300 Pieņemsim, ka es gribēju, lai ievietotu vārdu Daven jo manā datu struktūra. 457 00:18:49,300 --> 00:18:52,100 >> Tāpēc es gribu, lai ievietotu virkni Daven uz datu struktūru. 458 00:18:52,100 --> 00:18:54,370 Ko darīt, ja man nav lietot hash tabulu, bet es izmantoju 459 00:18:54,370 --> 00:18:56,980 kaut kas ir vairāk kokveida kā ģimenes koks, kur 460 00:18:56,980 --> 00:18:59,670 Jums ir dažas saknes pie top un tad mezgli un lapas 461 00:18:59,670 --> 00:19:01,440 ka iet uz leju un uz āru. 462 00:19:01,440 --> 00:19:04,450 Pieņemsim, ka tad, ka es vēlaties ievietot Daven s 463 00:19:04,450 --> 00:19:06,430 par to, kas šobrīd ir tukšs saraksts. 464 00:19:06,430 --> 00:19:09,780 Es esmu gatavojas darīt sekojošo: Es esmu notiek, lai izveidotu mezglu šīs saimes 465 00:19:09,780 --> 00:19:15,170 kokveida datu struktūra, kas izskatās nedaudz, piemēram, tas, katrs no kuriem 466 00:19:15,170 --> 00:19:19,640 taisnstūri ir, teiksim, Tagad 26 elementu tajā. 467 00:19:19,640 --> 00:19:21,650 Un katrs no šūnām šajā masīvā gatavojas 468 00:19:21,650 --> 00:19:23,470 pārstāvēt vēstuli ar alfabētu. 469 00:19:23,470 --> 00:19:28,190 >> Konkrēti, es esmu gatavojas, lai ārstētu Tas ir, tad B, tad C, tad D, 470 00:19:28,190 --> 00:19:29,310 šo vienu šeit. 471 00:19:29,310 --> 00:19:32,940 Tātad, tas notiek, lai efektīvi pārstāv vēstuli D. 472 00:19:32,940 --> 00:19:36,040 Bet, lai ievietotu visu Daven s nosaukt man jādara mazliet vairāk. 473 00:19:36,040 --> 00:19:37,840 Tāpēc es esmu pirmo reizi gatavojas hash, lai runāt. 474 00:19:37,840 --> 00:19:41,049 Es esmu gatavojas apskatīt pirmo burtu in Daven s, kas ir acīmredzami D, 475 00:19:41,049 --> 00:19:42,840 un es esmu gatavojas piešķirt mezgls, kas izskatās 476 00:19:42,840 --> 00:19:45,570 tāpat this-- lielu taisnstūri liels pietiekami, lai ietilptu visu alfabētu. 477 00:19:45,570 --> 00:19:47,140 >> Tagad D tiek darīts. 478 00:19:47,140 --> 00:19:49,720 Tagad A. D-A-V-E-N ir mērķis. 479 00:19:49,720 --> 00:19:51,220 Tāpēc tagad, ko es esmu gatavojas darīt, ir tas. 480 00:19:51,220 --> 00:19:54,027 Tiklīdz es sāku D paziņojumu tur nav rādītājs tur. 481 00:19:54,027 --> 00:19:56,860 Tas ir atkritumu vērtības brīdī, vai es varētu inicializēt to null. 482 00:19:56,860 --> 00:19:59,630 Bet ļaujiet man saglabāt notiek ar šī ideja veidot koku. 483 00:19:59,630 --> 00:20:04,260 Ļaujiet man piešķirt vēl vienu no šiem mezglus, kas ir 26 elementi tajā. 484 00:20:04,260 --> 00:20:05,150 >> Un jūs zināt, ko? 485 00:20:05,150 --> 00:20:09,130 Ja tas ir tikai mezglā atmiņā, ka Es radīju ar malloc, izmantojot struct 486 00:20:09,130 --> 00:20:11,240 kā mēs drīz redzēt, Es esmu gatavojas darīt this-- 487 00:20:11,240 --> 00:20:14,450 Es esmu gatavojas izdarīt bultiņu no lieta, kas pārstāvēja D uz leju 488 00:20:14,450 --> 00:20:15,860 uz šo jauno mezglu. 489 00:20:15,860 --> 00:20:19,240 Un tagad, pirmkārt nākamais burts Daven vārda, 490 00:20:19,240 --> 00:20:24,150 V-- D--V-- es esmu gatavojas iet uz priekšu un izdarīt vēl vienu mezglu, piemēram, tas, 491 00:20:24,150 --> 00:20:30,150 saskaņā ar kuru, tad V elementi šeit, kas mēs izdarīt par instance-- whoops. 492 00:20:30,150 --> 00:20:31,020 Mēs nevarēsim izdarīt tur. 493 00:20:31,020 --> 00:20:31,936 Tas notiek, lai iet šeit. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Tad mēs ejam uzskatām, ka tas ir V. 496 00:20:35,712 --> 00:20:44,920 Un tad noteikti šeit mēs ejam indeksēt leju no V uz to, ko mēs uzskatām E. 497 00:20:44,920 --> 00:20:50,100 Un tad no šeit mēs ejam aiziet ir viens no šiem mezgliem šeit. 498 00:20:50,100 --> 00:20:52,930 Un tagad mums ir jautājums, lai atbildētu. 499 00:20:52,930 --> 00:20:57,840 Man vajag, lai kaut kā norādīt, ka mēs beigās string Daven. 500 00:20:57,840 --> 00:20:59,490 Lai es varētu vienkārši atstāt to null. 501 00:20:59,490 --> 00:21:02,670 >> Bet ko tad, ja mums ir Daven s pilns nosaukums ir arī, kas 502 00:21:02,670 --> 00:21:04,280 ir, kā mēs jau teicām, Davenport? 503 00:21:04,280 --> 00:21:06,970 Tātad, ko tad Daven ir faktiski apakšvirkni, 504 00:21:06,970 --> 00:21:08,960 priedēklis daudz ilgāku string? 505 00:21:08,960 --> 00:21:11,450 Mēs varam ne tikai neatgriezeniski saka, nekas notiek 506 00:21:11,450 --> 00:21:14,410 iet uz turieni, jo mēs varētu nekad ievietotu vārdu, piemēram, Davenport 507 00:21:14,410 --> 00:21:15,840 šajā datu struktūra 508 00:21:15,840 --> 00:21:19,560 >> Tātad, ko mēs varētu darīt tā vietā, ir izturamies pret katru no šiem elementiem 509 00:21:19,560 --> 00:21:22,170 kā varbūt ar divām elementi iekšpusē no tiem. 510 00:21:22,170 --> 00:21:24,810 Viens no tiem ir rādītājs, protams, kā es esmu darījis. 511 00:21:24,810 --> 00:21:27,100 Tātad, katrs no šiem kastes ir ne tikai viena šūna. 512 00:21:27,100 --> 00:21:29,855 Bet ko tad, ja top one-- apakšā vienu s 513 00:21:29,855 --> 00:21:32,230 būs nulle, jo nav Davenport tikai yet. 514 00:21:32,230 --> 00:21:34,197 Ko darīt, ja top viens Ir dažas īpašas vērtība? 515 00:21:34,197 --> 00:21:36,530 Un tas būs nedaudz grūti izdarīt tā šo lielumu. 516 00:21:36,530 --> 00:21:38,130 Bet pieņemsim, ka tas ir tikai atzīme. 517 00:21:38,130 --> 00:21:38,920 Pārbaudīt. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N ir virkne šajā datu struktūra. 519 00:21:44,230 --> 00:21:48,350 >> Tikmēr, ja man būtu vairāk vietas šeit, es varētu darīt P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 un es varētu likt pārbaudi mezglā kas ir burtu T pašās beigās. 521 00:21:52,650 --> 00:21:55,460 Tātad tas ir ievērojami sarežģīts izskata datu struktūra. 522 00:21:55,460 --> 00:21:57,210 Un mans rokraksts protams, nepalīdz. 523 00:21:57,210 --> 00:22:00,043 Bet, ja es gribēju, lai ievietotu kaut ko cits, jāapsver, ko mēs varētu darīt. 524 00:22:00,043 --> 00:22:03,370 Ja mēs vēlējāmies, lai Dāvids, mēs gribētu ievērot to pašu loģiku, D-A-V, 525 00:22:03,370 --> 00:22:08,802 bet tagad es gribētu norādīt uz nākamo elements, nevis no E, bet no I līdz D 526 00:22:08,802 --> 00:22:10,760 Tātad tur būs vairāk mezgliem šajā kokā. 527 00:22:10,760 --> 00:22:12,325 Mēs ejam, lai būtu zvanu malloc vairāk. 528 00:22:12,325 --> 00:22:14,700 Bet es nevēlos, lai padarītu pilnīgs haoss no šo attēlu. 529 00:22:14,700 --> 00:22:17,710 Tātad, pieņemsim, nevis apskatīt vienu kas ir bijis iepriekš formulēti 530 00:22:17,710 --> 00:22:21,810 kā šis ar ne dot, dot, punkti, bet tikai saīsinātus bloki. 531 00:22:21,810 --> 00:22:23,950 Bet katrs no mezgliem Šajā koku šeit 532 00:22:23,950 --> 00:22:26,700 pārstāv to pašu thing-- masīvs Ray izmēru 26. 533 00:22:26,700 --> 00:22:28,860 >> Vai, ja mēs gribam būt īsti pareizi tagad, ko 534 00:22:28,860 --> 00:22:30,790 ja kāds ir nosaukums, apostrofs, pieņemsim 535 00:22:30,790 --> 00:22:35,560 pieņemu, ka katrs mezgls patiesībā ir tāpat kā 27 indeksu tajā, ne tikai 26. 536 00:22:35,560 --> 00:22:42,020 Tātad tagad tas būs dati struktūru sauc trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 Trie, kas ir it vēsturiski gudrs nosaukums koku 538 00:22:46,120 --> 00:22:49,040 kas ir optimizēta atgūšana, kas, protams, 539 00:22:49,040 --> 00:22:50,870 ir uzrakstīti ar I-E, lai tas ir trie. 540 00:22:50,870 --> 00:22:52,710 Bet tas ir vēsture TRIE. 541 00:22:52,710 --> 00:22:55,860 >> Tātad trie tas kokveida dati struktūra, piemēram, ģimenes koks 542 00:22:55,860 --> 00:22:57,510 kas galu galā uzvedas tāpat. 543 00:22:57,510 --> 00:23:00,890 Un šeit ir tikai vēl viens piemērs viss ķekars citu cilvēku vārdiem. 544 00:23:00,890 --> 00:23:03,540 Bet jautājums tagad pie rokas ir tas, kas ir 545 00:23:03,540 --> 00:23:08,070 ieguvām ieviešot apstrīdami vairāk sarežģīta datu struktūra, un viens, 546 00:23:08,070 --> 00:23:09,870 atklāti sakot, kas izmanto daudz atmiņas. 547 00:23:09,870 --> 00:23:11,703 >> Jo, pat ja, brīdī, es esmu tikai 548 00:23:11,703 --> 00:23:15,050 izmantojot D's rādītāju un Un V un Es un Ns, 549 00:23:15,050 --> 00:23:16,700 Es esmu izšķērdēt heck atmiņas partijas. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Bet kur es pavadu viens resurss, Man ir tendence darīt iegūt atpakaļ citu. 552 00:23:22,660 --> 00:23:26,020 Tātad, ja es esmu izdevumu vairāk vietas, to, kas ir iespējams, cerība? 553 00:23:26,020 --> 00:23:27,407 Ka es esmu tērē mazāk, ko? 554 00:23:27,407 --> 00:23:28,240 Mērķauditorija: Mazāk laika. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Laiks. 556 00:23:28,990 --> 00:23:30,320 Tagad, kāpēc varētu būt? 557 00:23:30,320 --> 00:23:33,880 Nu, kas ir ievietošanas laiks, runājot par lielo O tagad, 558 00:23:33,880 --> 00:23:37,660 ar nosaukumu, piemēram, Daven vai Davenport vai Dāvids? 559 00:23:37,660 --> 00:23:39,340 Nu, Daven bija pieci soļi. 560 00:23:39,340 --> 00:23:42,350 Davenport būs deviņi posmi, lai tā būtu vēl dažus soļus. 561 00:23:42,350 --> 00:23:44,250 David būtu pieci soļi, kā arī. 562 00:23:44,250 --> 00:23:47,230 Tātad tie ir konkrēti skaitļi, bet, protams, tur ir 563 00:23:47,230 --> 00:23:49,550 augšējo robežu uz garums kāda vārda. 564 00:23:49,550 --> 00:23:52,240 Un tiešām, problēmā komplekti piecu specifikāciju, 565 00:23:52,240 --> 00:23:54,050 mēs esam gatavojas ierosināt ka tas ir kaut kas 566 00:23:54,050 --> 00:23:55,470 kas ir 40-dažas-nepāra zīmes. 567 00:23:55,470 --> 00:23:58,180 >> Reāli, neviens nav bezgalīgi garš nosaukums, 568 00:23:58,180 --> 00:24:01,542 kas ir teikt, ka garums vārdu vai garums string mēs varētu 569 00:24:01,542 --> 00:24:03,750 ir pārliecināts stāvoklis struktūra ir apstrīdami, ko? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Tas ir nemainīgs. 572 00:24:06,250 --> 00:24:06,430 Taisnība? 573 00:24:06,430 --> 00:24:09,310 Tas varētu būt liels konstante, piemēram, 40-kaut ko, bet tas ir nemainīgs. 574 00:24:09,310 --> 00:24:13,752 Un tas nav atkarība, cik citi vārdi ir šajā datu struktūrā. 575 00:24:13,752 --> 00:24:15,460 Citiem vārdiem sakot, ja es gribēju tagad ievietot 576 00:24:15,460 --> 00:24:20,540 Colton vai Gabriel vai Rob vai Zamyla vai Alison vai Belinda, vai kādi citi nosaukumi 577 00:24:20,540 --> 00:24:23,940 no darbiniekiem, uz šo datu struktūra, ir darbības laiks 578 00:24:23,940 --> 00:24:26,750 ievietojot citiem nosaukumiem būs vispār triecienu 579 00:24:26,750 --> 00:24:30,220 pēc tā, cik daudziem citiem elementiem ir kas jau datu struktūru? 580 00:24:30,220 --> 00:24:31,040 Tas nav. 581 00:24:31,040 --> 00:24:31,540 Taisnība? 582 00:24:31,540 --> 00:24:36,150 Tāpēc, ka mēs esam efektīvi izmantot šis daudzslāņu hash tabulu. 583 00:24:36,150 --> 00:24:38,280 Un darbības laiks jebkura no šīm darbībām 584 00:24:38,280 --> 00:24:41,510 ir atkarīga ne uz skaitu elementus, kas ar datu struktūru 585 00:24:41,510 --> 00:24:43,090 vai kuras ir beidzot gatavojas būt datu struktūru, 586 00:24:43,090 --> 00:24:44,714 bet no garuma, ko tieši? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Stīgu ir ievietota, kas tas padara 589 00:24:49,200 --> 00:24:52,580 šis asimptotiski konstante LAIKU_ lielais O viens. 590 00:24:52,580 --> 00:24:54,720 Un godīgi sakot, tikai reālajā pasaulē, šis 591 00:24:54,720 --> 00:24:58,380 nozīmē, ievietojot Daven vārds notiek piemēram, pieci soļi, vai Davenport deviņi 592 00:24:58,380 --> 00:25:00,100 pakāpieni, vai Deivids pieci soļi. 593 00:25:00,100 --> 00:25:03,071 Tas ir diezgan darn mazie gaitas reizes. 594 00:25:03,071 --> 00:25:05,320 Un, protams, tas ir ļoti laba lieta, it īpaši, ja 595 00:25:05,320 --> 00:25:08,126 tas nav atkarīgs no kopējā apjoma vairāki elementi tur. 596 00:25:08,126 --> 00:25:10,500 Tātad, kā mēs varētu īstenot šo veida struktūras kodu? 597 00:25:10,500 --> 00:25:12,900 Tas ir nedaudz vairāk sarežģīts, bet tomēr tas ir 598 00:25:12,900 --> 00:25:15,050 tikai piemērošana pamatelementiem. 599 00:25:15,050 --> 00:25:17,830 Es esmu gatavojas pārskatīt mums mezgla šādi: 600 00:25:17,830 --> 00:25:21,100 bool sauc word-- un tas varētu saukt jebko. 601 00:25:21,100 --> 00:25:23,970 Bet bool pārstāv ko es vērsa kā atzīmi. 602 00:25:23,970 --> 00:25:24,490 Jā. 603 00:25:24,490 --> 00:25:26,720 Tas ir beigu virknes šajā datu struktūra. 604 00:25:26,720 --> 00:25:30,702 >> Un, protams, mezglu zvaigzne tur ir kas attiecas uz bērniem. 605 00:25:30,702 --> 00:25:32,410 Un, protams, tāpat kā ciltskoku, jūs 606 00:25:32,410 --> 00:25:34,370 apsvērtu mezglus kas ir piekārtiem off 607 00:25:34,370 --> 00:25:36,920 no apakšas kāda vecāka elements ir bērni. 608 00:25:36,920 --> 00:25:40,510 Un tā bērni gatavojas būt masīvs 27., 27. viens 609 00:25:40,510 --> 00:25:41,680 tikai pastāvēt apostrofam. 610 00:25:41,680 --> 00:25:43,390 Mēs ejam, lai kārtotu īpašu gadījumu šī. 611 00:25:43,390 --> 00:25:45,400 Tātad jūs varat būt pārliecināti, vārdus ar apostrofu. 612 00:25:45,400 --> 00:25:47,399 Varbūt pat domu vajadzētu iet tur, bet jūs 613 00:25:47,399 --> 00:25:50,330 redzēt p komplektā 5 mēs tikai aprūpes par vēstuļu un apostrofu. 614 00:25:50,330 --> 00:25:52,990 >> Un tad kā jūs pārstāvēt pati datu struktūra? 615 00:25:52,990 --> 00:25:56,454 Kā jūs pārstāvat saknes Šīs TRIE, lai runāt? 616 00:25:56,454 --> 00:25:59,620 Nu, tāpat kā ar saistīta sarakstu, jūs nepieciešams rādītāju uz pirmo elementu. 617 00:25:59,620 --> 00:26:04,270 Ar TRIE jūs vienkārši nepieciešams viens rādītāju uz pamatā šo TRIE. 618 00:26:04,270 --> 00:26:07,290 Un no turienes jūs varat hash savu ceļu uz leju, dziļāk un dziļāk 619 00:26:07,290 --> 00:26:10,460 uz katru citu mezglu struktūrā. 620 00:26:10,460 --> 00:26:13,440 Tik vienkārši ar to var mēs pārstāvam šo struct. 621 00:26:13,440 --> 00:26:15,877 >> Tagad Meanwhile-- Ak, jautājumu. 622 00:26:15,877 --> 00:26:17,220 >> Mērķauditorija: Kas ir bool vārdu? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: Bool vārds ir tikai šo C iemiesojums 624 00:26:20,490 --> 00:26:22,920 no tā, ko es aprakstīju Šajā ailē šeit, kad 625 00:26:22,920 --> 00:26:26,000 Es sāku sadalot katra Array s elementi divās daļās. 626 00:26:26,000 --> 00:26:27,600 Viens no tiem ir rādītājs uz nākamo mezglu. 627 00:26:27,600 --> 00:26:30,280 Citi ir jābūt kaut kas līdzīgs rūtiņu 628 00:26:30,280 --> 00:26:33,770 teikt jā, tur ir Vārds Daven ka beidzas šeit, 629 00:26:33,770 --> 00:26:35,610 jo mēs negribam, brīdī, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Pat ja Dave būs likumīga vārdu, viņš nevis TRIE 631 00:26:39,320 --> 00:26:39,830 vēl. 632 00:26:39,830 --> 00:26:40,950 Un D ir ne vārds. 633 00:26:40,950 --> 00:26:42,770 Un D-nav vārds vai nosaukums. 634 00:26:42,770 --> 00:26:45,020 Tātad atzīmes norāda tikai vienu reizi jums 635 00:26:45,020 --> 00:26:48,190 skāra šis mezgls ir iepriekšējais ceļš rakstzīmju 636 00:26:48,190 --> 00:26:50,700 faktiski virkne, kas jūs esat ievietots. 637 00:26:50,700 --> 00:26:53,660 Tā ka viss ir bool tur dara mums. 638 00:26:53,660 --> 00:26:55,500 >> Jebkādi citi jautājumi, par mēģinājumiem? 639 00:26:55,500 --> 00:26:56,215 Yeah. 640 00:26:56,215 --> 00:26:58,035 >> Mērķauditorija: Kas ir pārklājas? 641 00:26:58,035 --> 00:26:59,945 Ko darīt, ja jums ir Dave un Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Perfect. 643 00:27:00,820 --> 00:27:02,580 Ko darīt, ja jums ir Dave un Daven? 644 00:27:02,580 --> 00:27:06,240 Tātad, ja mēs ievietotu, teiksim segvārdu, par David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Tas ir tiešām super vienkārši. 647 00:27:08,700 --> 00:27:10,325 Tātad, mēs esam tikai gatavojas veikt četrus soļus. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Un ko man ir darīt, kad es hit, ka ceturtais mezglu? 650 00:27:15,847 --> 00:27:16,680 Tikai gatavojas pārbaudīt. 651 00:27:16,680 --> 00:27:18,000 Mēs esam jau labi iet. 652 00:27:18,000 --> 00:27:18,840 Darīts. 653 00:27:18,840 --> 00:27:19,750 Četri soļi. 654 00:27:19,750 --> 00:27:21,590 Constant laiks asimptotiski. 655 00:27:21,590 --> 00:27:26,300 Un tagad mēs esam norādīja, ka gan Dave un Daven ir virknes struktūrā. 656 00:27:26,300 --> 00:27:27,710 Tāpēc nav problēma. 657 00:27:27,710 --> 00:27:30,200 Un paziņojums, kā klātbūtni no Daven nebija darīt to 658 00:27:30,200 --> 00:27:34,750 veikt vairāk laika vai mazāk laiks Dave un otrādi. 659 00:27:34,750 --> 00:27:36,000 >> Tātad, ko vēl mēs varam tagad darīt? 660 00:27:36,000 --> 00:27:40,680 Mēs esam izmantojuši šo metaforu pirms paplātes, kas pārstāv kaut ko. 661 00:27:40,680 --> 00:27:43,380 Bet izrādās, ka kaudze paplātes ir faktiski 662 00:27:43,380 --> 00:27:47,187 norādāmais cita abstraktu datu type-- augstāka līmeņa datu struktūra 663 00:27:47,187 --> 00:27:49,770 ka beigās diena ir tikai piemēram, masīvu vai saistītajā sarakstā 664 00:27:49,770 --> 00:27:50,970 vai kaut kas vairāk ikdienišķa. 665 00:27:50,970 --> 00:27:53,270 Bet tas ir interesantāk konceptuāls jēdziens. 666 00:27:53,270 --> 00:27:56,440 Kaudze, piemēram, šo renes šeit Mather, 667 00:27:56,440 --> 00:27:58,750 parasti sauc vienkārši that-- kaudze. 668 00:27:58,750 --> 00:28:02,540 >> Un šāda veida datu struktūras Jums ir divas operations-- 669 00:28:02,540 --> 00:28:05,880 Jums ir viens sauc stimuls pievienojot kaut ko kaudze, 670 00:28:05,880 --> 00:28:08,320 piemēram, liekot citu padevi atpakaļ uz augšu kaudze. 671 00:28:08,320 --> 00:28:11,350 Un tad pop, kas nozīmē, ka jūs ņemt augšējais paplātes off. 672 00:28:11,350 --> 00:28:16,210 Bet kas ir galvenais par kaudze ir tas, ka tas ir ieguvuši šo ziņkārīgs īpašība. 673 00:28:16,210 --> 00:28:19,560 Kā ēdamzālē darbinieki ir pārkārtojot paplātes nākamo maltīti, 674 00:28:19,560 --> 00:28:21,380 to, kas būs taisnība par to, kā skolēniem 675 00:28:21,380 --> 00:28:22,856 mijiedarboties ar šo datu struktūru? 676 00:28:22,856 --> 00:28:24,480 Mērķauditorija: Viņi gatavojas pop vienreizējs. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Viņi gatavojas pop vienreizējs, cerams top. 678 00:28:26,550 --> 00:28:28,910 Pretējā gadījumā tas ir tikai sava veida stulba lai iet visu ceļu uz leju. 679 00:28:28,910 --> 00:28:29,070 Taisnība? 680 00:28:29,070 --> 00:28:31,620 Datu struktūra nav īsti ļaut jums greifers apakšējo paplāti vismaz 681 00:28:31,620 --> 00:28:32,520 viegli. 682 00:28:32,520 --> 00:28:35,040 Tātad tur ir šis ziņkārīgs īpašums, kaudze 683 00:28:35,040 --> 00:28:39,730 ka pēdējais prece ir būs pirmais ārā. 684 00:28:39,730 --> 00:28:43,400 Un datoru zinātnieki sauc tas LIFO-- pēdējais iekšā, pirmais ārā. 685 00:28:43,400 --> 00:28:45,540 Un tas tiešām ir interesanti pieteikumi. 686 00:28:45,540 --> 00:28:50,090 Tas ne vienmēr ir tik acīmredzama, kā daži citi, bet tā var, protams, būt noderīga, 687 00:28:50,090 --> 00:28:54,040 un tā var, protams, ir jāīsteno pāris dažādos veidos. 688 00:28:54,040 --> 00:28:58,550 >> Tik viens, un faktiski, ļaujiet man nav nodoties to. 689 00:28:58,550 --> 00:28:59,860 Darīsim šo vietā. 690 00:28:59,860 --> 00:29:03,700 Apskatīsim vienu, kas ir gandrīz pati ideja, bet tas ir nedaudz godīgāka. 691 00:29:03,700 --> 00:29:04,200 Taisnība? 692 00:29:04,200 --> 00:29:07,560 Ja jūs esat viens no šiem fanu zēnu vai meitenes, kas tiešām patīk Apple produktiem 693 00:29:07,560 --> 00:29:10,130 un jūs pamodos pulksten 3:00 rindā kādā veikalā 694 00:29:10,130 --> 00:29:14,150 lai saņemtu pašu jaunāko iPhone, jūs varētu būt ievietots rindā uz augšu, kā šis. 695 00:29:14,150 --> 00:29:15,800 >> Tagad rinda ir ļoti apzināti nosaukts. 696 00:29:15,800 --> 00:29:18,190 Tā ir līnija, jo tur ir daži godīgums uz to. 697 00:29:18,190 --> 00:29:18,690 Taisnība? 698 00:29:18,690 --> 00:29:21,690 Tā būtu sava veida iesūc, ja esat got tur pirmais pie Apple Store 699 00:29:21,690 --> 00:29:25,700 bet jums ir efektīvi viszemākais paplāte jo Apple darbinieki tad 700 00:29:25,700 --> 00:29:28,189 pop pēdējo personu, kas faktiski ieguva rindā. 701 00:29:28,189 --> 00:29:31,230 Tātad skursteņi un rindas, lai gan funkcionāli viņi sava veida same-- 702 00:29:31,230 --> 00:29:33,105 tas ir tikai šī kolekcija resursu, kas ir 703 00:29:33,105 --> 00:29:36,210 gatavojas augt un shrink-- tur šis taisnīguma aspekts uz to, 704 00:29:36,210 --> 00:29:39,634 vismaz reālajā pasaulē, kur operācijas jūs izmantot 705 00:29:39,634 --> 00:29:40,800 būtiski atšķiras. 706 00:29:40,800 --> 00:29:43,360 Stack-- rinda rather-- ir teikt, ka 707 00:29:43,360 --> 00:29:45,320 divas operācijas: n rindā un d rindā. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Vai jūs varat zvanīt viņiem kāds no lietas numurs. 710 00:29:48,090 --> 00:29:50,770 Bet jūs vienkārši vēlaties, lai attēlotu Priekšstats, ka viens ir pievienojot 711 00:29:50,770 --> 00:29:53,230 un viens galu galā atņemot. 712 00:29:53,230 --> 00:29:58,840 >> Tagad zem motora pārsega, gan kaudze un rinda varētu īstenot kā? 713 00:29:58,840 --> 00:30:01,390 Mēs neiešu kodā tas tāpēc, ka augstāka līmeņa 714 00:30:01,390 --> 00:30:03,387 ideja ir sava veida vairāk acīmredzama. 715 00:30:03,387 --> 00:30:04,470 Es domāju, ko darīt cilvēkiem darīt? 716 00:30:04,470 --> 00:30:07,030 Ja es esmu pirmais cilvēks pie Apple Uzglabāt un tas ir priekšējās durvis, 717 00:30:07,030 --> 00:30:08,130 jūs zināt, es esmu gatavojas stāvēt šeit. 718 00:30:08,130 --> 00:30:09,750 Un nākamais personas gatavojas stāvēt šeit. 719 00:30:09,750 --> 00:30:11,500 Un nākamais personas gatavojas stāvēt šeit. 720 00:30:11,500 --> 00:30:13,792 Tātad, kādi datu struktūra aizdod sevi rindā? 721 00:30:13,792 --> 00:30:14,542 >> Mērķauditorija: rindā. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: Nu, rindā. 723 00:30:15,667 --> 00:30:16,390 Pārliecināts. 724 00:30:16,390 --> 00:30:16,920 Kas vēl? 725 00:30:16,920 --> 00:30:17,600 >> Mērķauditorija: saistīts saraksts. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: saistīta uzskaitīt jūs varētu īstenot. 727 00:30:18,990 --> 00:30:22,500 Un saistīts saraksts ir jauki, jo tad tā var pieaugt patvaļīgi ilgi pretstatā 728 00:30:22,500 --> 00:30:24,880 lai ar kādu noteiktu skaitu cilvēku veikalā. 729 00:30:24,880 --> 00:30:27,030 Bet varbūt noteikts skaits vietu ir likumīgs. 730 00:30:27,030 --> 00:30:30,350 Jo, ja tie ir tikai, piemēram, 20 iPhone pirmajā dienā, varbūt 731 00:30:30,350 --> 00:30:33,930 tie tikai nepieciešams masīvs izmēra 20 pārstāvēt šo rindā, kurā 732 00:30:33,930 --> 00:30:37,070 tikai teikt, tagad, kad mēs sākam runāt par šīm augstāka līmeņa problēmas, 733 00:30:37,070 --> 00:30:38,890 Jūs varat īstenot jebkurā vairākos veidos. 734 00:30:38,890 --> 00:30:42,030 Un tur ir iespējams tikai gatavojas būt tirdzniecības off telpā un laikā 735 00:30:42,030 --> 00:30:43,950 vai vienkārši savā kodu sarežģītību. 736 00:30:43,950 --> 00:30:45,380 >> Kas par kaudze? 737 00:30:45,380 --> 00:30:48,190 Nu, kaudze, mēs esam redzējuši pārāk varētu vienkārši šie paplātes. 738 00:30:48,190 --> 00:30:50,007 Un jūs varētu īstenot šo masīvs. 739 00:30:50,007 --> 00:30:53,090 Bet kādā brīdī, ja jūs izmantot masīvu, to, kas notiks ar paplātēm 740 00:30:53,090 --> 00:30:54,173 jūs cenšaties nolikt? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Labi. 743 00:30:55,670 --> 00:30:57,490 Jūs tikai gatavojas varēs iet tik augstu. 744 00:30:57,490 --> 00:31:00,156 Un es domāju, ka Mather viņi faktiski padziļinājumā šajā atvēršanu. 745 00:31:00,156 --> 00:31:01,950 Tik tiešām, tas ir gandrīz tāpat Mather izmanto 746 00:31:01,950 --> 00:31:03,783 masīvs fiksētu lielumu, tāpēc, ka jūs varat tikai 747 00:31:03,783 --> 00:31:08,302 fit tik daudz paplātes šajā atvēršana siena lejā cilvēku ceļgaliem. 748 00:31:08,302 --> 00:31:10,010 Un tā tas varētu būt varētu būt masīva, 749 00:31:10,010 --> 00:31:14,300 bet mēs, protams, var ieviest, ka vairāk parasti ar saistītajā sarakstā. 750 00:31:14,300 --> 00:31:16,390 >> Nu, ko par citu datu struktūras? 751 00:31:16,390 --> 00:31:18,760 Ļaujiet man uzvilkt vienu citu vizuālo šeit. 752 00:31:18,760 --> 00:31:24,710 Kaut ko līdzīgu kā par šeit šo vienu? 753 00:31:24,710 --> 00:31:28,920 Kāpēc tas varētu būt noderīgi, lai būtu ne kaut kā fancy kā TRIE, kas 754 00:31:28,920 --> 00:31:32,370 mēs redzējām bija šīs ļoti plašas mezglus, katrs no kuriem ir masīvs? 755 00:31:32,370 --> 00:31:35,740 Bet ko tad mēs darām kaut ko vairāk vienkārši, kā vecs skola ciltskoku, 756 00:31:35,740 --> 00:31:38,110 Katrā no kura mezgli šeit ir tikai glabāšanai numuru. 757 00:31:38,110 --> 00:31:42,180 Vietā nosaukumu vai pēcnācējs ir tikai uzglabāt vairākus kā šis. 758 00:31:42,180 --> 00:31:45,250 >> Nu, žargons mēs izmantojam datu struktūras ir abi mēģina 759 00:31:45,250 --> 00:31:49,510 un koki, kur trie, atkal, ir tikai viens, kura mezgli ir bloki, 760 00:31:49,510 --> 00:31:51,680 joprojām ir tas, ko jūs varētu izmantot no pakāpē skolā 761 00:31:51,680 --> 00:31:53,860 ja jūs veicāt ģimeni tree-- lapas un saknes 762 00:31:53,860 --> 00:31:57,250 koku un bērniem mātes un to vecvecākus. 763 00:31:57,250 --> 00:32:03,670 Un mēs varētu ieviest koku, piemēram, kā vienkārši kā šī. 764 00:32:03,670 --> 00:32:07,420 Koks, ja to kā mezglu, viens no šajās aprindās, kurai ir vairāki, 765 00:32:07,420 --> 00:32:09,947 tas nav nāksies viens rādītājs, bet divi. 766 00:32:09,947 --> 00:32:11,780 Un, tiklīdz jūs pievienot Otrs rādītājs, jums 767 00:32:11,780 --> 00:32:13,905 faktiski var tagad darīt kārtošanas divdimensiju datiem 768 00:32:13,905 --> 00:32:14,780 struktūras atmiņā. 769 00:32:14,780 --> 00:32:16,660 Daudz, piemēram, divdimensiju masīvs, jūs varat 770 00:32:16,660 --> 00:32:18,904 ir sava veida no divdimensiju saistītie saraksti, bet tie, 771 00:32:18,904 --> 00:32:20,820 kas seko modelis ja tur nav ciklus. 772 00:32:20,820 --> 00:32:24,487 Tas ir patiesi koks ar vienu vecvecāks ceļu šeit, un tad 773 00:32:24,487 --> 00:32:27,320 daži vecāki un bērni, un mazbērni un mazmazbērni. 774 00:32:27,320 --> 00:32:28,370 un tā tālāk. 775 00:32:28,370 --> 00:32:32,390 >> Bet to, kas ir patiešām veikls par šo pārāk, tikai ķircināt jums ar mazliet kodu, 776 00:32:32,390 --> 00:32:35,370 atsaukums rekursijas no awhile atpakaļ, saskaņā ar kuru 777 00:32:35,370 --> 00:32:38,220 Jums uzrakstīt funkciju, kas sevi sauc. 778 00:32:38,220 --> 00:32:41,140 Tā ir skaista iespēja ieviest kaut ko 779 00:32:41,140 --> 00:32:42,920 tāpat recursion, jo uzskata, ka tas. 780 00:32:42,920 --> 00:32:43,860 >> Tas ir koks. 781 00:32:43,860 --> 00:32:48,040 Un es esmu bijis nedaudz anālais ar to, kā Man veselos skaitļus uz ielas. 782 00:32:48,040 --> 00:32:51,020 Tik daudz tā, ka tā ir īpaša name-- bināro meklēšanas koku. 783 00:32:51,020 --> 00:32:53,460 Tagad mēs esam dzirdējuši par bināro meklēt, bet jūs varat 784 00:32:53,460 --> 00:32:55,180 strādāt atpakaļ no šī lieta vārdu? 785 00:32:55,180 --> 00:32:59,280 Kāds ir modelis, kā es ievietota veselos skaitļus šajā kokā? 786 00:32:59,280 --> 00:33:00,696 Tas nav patvaļīgs. 787 00:33:00,696 --> 00:33:01,570 Tur ir daži modelis. 788 00:33:01,570 --> 00:33:02,090 Yeah. 789 00:33:02,090 --> 00:33:03,370 >> Mērķauditorija: mazākie kreisajā pusē. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Jā. 791 00:33:03,690 --> 00:33:05,062 Mazākie ir pa kreisi. 792 00:33:05,062 --> 00:33:06,270 Lielāks tiem ir labajā pusē. 793 00:33:06,270 --> 00:33:12,940 Tā, ka patiess apgalvojums ir vecāks ir lielāks par kreisajiem bērns, 794 00:33:12,940 --> 00:33:14,850 bet mazāk nekā tās labajā bērnu. 795 00:33:14,850 --> 00:33:17,750 Un tas vien ir pat rekursīvs verbālā definīcija 796 00:33:17,750 --> 00:33:20,500 tāpēc, ka jūs varat pieteikties, ka Tāda pati loģika katram mezglā 797 00:33:20,500 --> 00:33:23,080 un tas tikai dibeni out, gadījumu, ja jums 798 00:33:23,080 --> 00:33:25,740 būs, kad jūs hit viens no lapas, tā sakot, 799 00:33:25,740 --> 00:33:28,580 ja atvaļinājums nav bērnu tālāk. 800 00:33:28,580 --> 00:33:30,614 >> Tagad, kā jūs varētu atrast numuru 44? 801 00:33:30,614 --> 00:33:32,280 Jūs varētu sākt saknē un teikt, hm. 802 00:33:32,280 --> 00:33:35,690 55 nav 44 Tāpēc es gribu iet tiesības vai es gribu, lai iet pa kreisi? 803 00:33:35,690 --> 00:33:37,190 Nu, protams, jūs vēlaties, lai iet pa kreisi. 804 00:33:37,190 --> 00:33:40,060 Un tā tas ir tāpat kā tālruni grāmata piemērs bināro meklēšanu 805 00:33:40,060 --> 00:33:41,099 kopumā. 806 00:33:41,099 --> 00:33:43,390 Bet mēs esam to īsteno Tagad nedaudz vairāk dinamiski 807 00:33:43,390 --> 00:33:45,339 nekā masīvs varētu atļaut. 808 00:33:45,339 --> 00:33:48,130 Un patiesībā, ja jūs vēlaties meklēt pie koda, pēc pirmā acu uzmetiena pārliecināts. 809 00:33:48,130 --> 00:33:49,671 Izskatās, ka visu ķekars līnijas. 810 00:33:49,671 --> 00:33:51,220 Bet tas ir skaisti vienkārši. 811 00:33:51,220 --> 00:33:54,490 Ja jūs vēlaties, lai īstenotu funkciju aicināja meklēt kuras mērķis dzīvē 812 00:33:54,490 --> 00:33:57,290 ir meklēt vērtību piemēram, n, vesels skaitlis, 813 00:33:57,290 --> 00:34:01,756 un jūs esat izturējis kādā vienā pointer-- rādītāju uz mezgla saknes, 814 00:34:01,756 --> 00:34:04,380 drīzāk, šī koka, no kura Jūs varat piekļūt visu citu, 815 00:34:04,380 --> 00:34:08,850 paziņojums, kā vienkāršākā Jūs varat īstenot loģiku. 816 00:34:08,850 --> 00:34:10,880 Ja koks ir nulle, protams, tas nav tur. 817 00:34:10,880 --> 00:34:11,880 Pieņemsim tikai atgriezties viltus. 818 00:34:11,880 --> 00:34:12,000 Taisnība? 819 00:34:12,000 --> 00:34:14,040 Ja jūs puses, tas nekas, tur nekā nav. 820 00:34:14,040 --> 00:34:17,900 >> Cits, ja n ir mazāks nekā koks arrow N- tagad arrow n, 821 00:34:17,900 --> 00:34:20,670 atgādināt mēs iepazīstinājām super īsi otro dienu, 822 00:34:20,670 --> 00:34:25,100 un tas tikai nozīmē, ka de-atsauci rādītāju un apskatīt lauka sauc n. 823 00:34:25,100 --> 00:34:27,690 Tātad tas nozīmē, iet tur un apskatīt lauka sauc n. 824 00:34:27,690 --> 00:34:33,810 Tātad, ja n, vērtību, jūs esat dota, ir mazāks par vērtību koku skaitlim, 825 00:34:33,810 --> 00:34:35,449 kur jūs vēlaties doties? 826 00:34:35,449 --> 00:34:36,389 Pa kreisi. 827 00:34:36,389 --> 00:34:37,780 >> Tātad paziņojums rekursijas. 828 00:34:37,780 --> 00:34:39,860 Es esmu returning-- nav taisnība. 829 00:34:39,860 --> 00:34:40,989 Nav nepatiesa. 830 00:34:40,989 --> 00:34:45,670 Es esmu atpakaļ neatkarīgi atbildi No sarunas ar sevi, iet 831 00:34:45,670 --> 00:34:50,100 n atkal, kas ir lieks, bet to, kas ir nedaudz savādāka? 832 00:34:50,100 --> 00:34:51,989 Kā man padarīt mazāku problēmu? 833 00:34:51,989 --> 00:34:54,920 Es esmu iet tik otro argumentu, nevis saknes koku, 834 00:34:54,920 --> 00:34:59,616 bet pa kreisi bērns šajā gadījumā. 835 00:34:59,616 --> 00:35:00,990 Tāpēc es esmu iet kreisajā bērnam. 836 00:35:00,990 --> 00:35:04,720 >> Tikmēr, ja n ir lielāks nekā mezglu Es esmu šobrīd meklē, 837 00:35:04,720 --> 00:35:06,690 Es meklētu labajā pusē. 838 00:35:06,690 --> 00:35:10,880 Cits, ja koks nav spēkā, un ja elements nav pa kreisi 839 00:35:10,880 --> 00:35:13,240 un tas nav labi, kāda ir lieliski gadījums? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Mēs esam patiešām atraduši mezglu jautājums, un tāpēc mēs atgrieztos taisnība. 842 00:35:18,440 --> 00:35:21,490 >> Tātad mēs esam tikai scratched virsmas Tagad daži no šiem datu struktūras. 843 00:35:21,490 --> 00:35:24,370 Jo problēma noteikti pieci jums izpētīt šos vēl vairāk, 844 00:35:24,370 --> 00:35:27,250 un jums tiks dota jūsu dizains izvēle, kā iet par to. 845 00:35:27,250 --> 00:35:30,250 Ko es gribētu, lai izdarītu secinājumus par ir tikai 30 sekunžu teaser 846 00:35:30,250 --> 00:35:32,080 par to, kas gaida nākamajā nedēļā un ārpus tās. 847 00:35:32,080 --> 00:35:35,390 >> Kā mēs begin-- laimi jums varētu think-- mūsu pāreju lēni 848 00:35:35,390 --> 00:35:38,680 no pasaules C un zemākā līmeņa īstenošanas detaļas, 849 00:35:38,680 --> 00:35:42,090 uz pasauli, kurā mēs varam veikt, lai pašsaprotamu, ka kāds cits ir beidzot 850 00:35:42,090 --> 00:35:44,010 īsteno šos datus konstrukcijas mums, 851 00:35:44,010 --> 00:35:47,570 un mēs sāksim saprast reālā pasaule ir īstenot 852 00:35:47,570 --> 00:35:50,560 tīmekļa programmas un mājas lapas plašāk 853 00:35:50,560 --> 00:35:52,910 un arī ļoti drošība sekas, ka mēs esam tikai 854 00:35:52,910 --> 00:35:54,850 sākuši saskrāpēt virsmu. 855 00:35:54,850 --> 00:35:57,320 Te ir tas, kas mūs sagaida dienās nāk. 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 >> -Viņš Nāca ar ziņu, ar protokolu, visu savu. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Viņš nāca pasaulē nežēlīga ugunsmūri, uncaring maršrutētāji, 861 00:36:30,894 --> 00:36:33,368 un briesmas daudz ļaunāks par nāvi. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Viņš ir ātrs. 864 00:36:36,236 --> 00:36:37,980 Viņš ir spēcīga. 865 00:36:37,980 --> 00:36:42,830 Viņš ir TCP / IP, un viņš dabūja savu adresi. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors of Net." 868 00:36:48,074 --> 00:36:49,660 [END VIDEO PLAYBACK] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: Coming nākamnedēļ. 870 00:36:50,910 --> 00:36:51,880 Mēs redzēsim jūs tam. 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 -Un Tagad, "Deep Domas" ko Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Vienmēr sākas lekcijas ar "viss ir labi." 876 00:37:05,820 --> 00:37:08,750 Kāpēc ne, "Lūk risinājums līdz šīs nedēļas problēmu kopumu " 877 00:37:08,750 --> 00:37:12,180 vai "Mēs dodam jums visiem?" 878 00:37:12,180 --> 00:37:13,380 [Smejas] 879 00:37:13,380 --> 00:37:15,530 [END VIDEO PLAYBACK]