1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [MUSIC SPILLE] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID MALAN: Dette er CS50. 5 00:00:14,010 --> 00:00:18,090 Og dette er både starten og end-- som literally-- nesten slutten 6 00:00:18,090 --> 00:00:18,825 av uke seks. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Jeg tenkte jeg skulle dele en litt av en morsom faktum. 9 00:00:22,640 --> 00:00:25,370 Jeg har trukket dette opp fra en siste semesterets datasett. 10 00:00:25,370 --> 00:00:29,710 Du husker kanskje at vi ber dere på hver p fastsatt skjema dersom du har sett på nettet 11 00:00:29,710 --> 00:00:31,580 eller hvis du har deltatt i person. 12 00:00:31,580 --> 00:00:33,020 Og her er dataene. 13 00:00:33,020 --> 00:00:34,710 Så i dag var veldig mye forutsigbar. 14 00:00:34,710 --> 00:00:37,126 Men vi ønsket å tilbringe litt tid med deg likevel. 15 00:00:37,126 --> 00:00:40,599 Vil noen liker å formodning hvorfor dette Grafen er så jaggy, opp ned, opp ned, 16 00:00:40,599 --> 00:00:41,265 så konsekvent? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Hva gjør hver av toppene og trau representerer? 19 00:00:45,130 --> 00:00:46,005 >> PUBLIKUM: [uhørbart] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: Ja. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Og mer morsom måte, gud forby, vi holder en forelesning på en fredag 24 00:00:55,480 --> 00:00:58,960 i begynnelsen av semesteret, det er hva vi ser skje. 25 00:00:58,960 --> 00:01:03,430 Så i dag, vi tar del i en bit mer om datastrukturer. 26 00:01:03,430 --> 00:01:06,660 Og for å gi deg mer av en solid mental modell for problemer på fem, 27 00:01:06,660 --> 00:01:07,450 som nå er ute. 28 00:01:07,450 --> 00:01:10,817 Feilstavelser, hvor vil vi hånd du en tekstfil noen 100.000 29 00:01:10,817 --> 00:01:12,650 pluss engelske ord, og du kommer til å ha 30 00:01:12,650 --> 00:01:17,770 å finne ut hvordan å smart laste dem inn i minnet, i RAM, ved hjelp av noen data 31 00:01:17,770 --> 00:01:19,330 strukturen av ditt valg. 32 00:01:19,330 --> 00:01:22,470 >> Nå er en slik datastruktur kunne være, men sannsynligvis bør ikke være, 33 00:01:22,470 --> 00:01:25,630 ganske forenklede lenket liste, som vi innførte forrige gang. 34 00:01:25,630 --> 00:01:29,220 Og en lenket liste hadde minst en fordel i forhold til en matrise. 35 00:01:29,220 --> 00:01:32,096 Hva er en fordel med en lenket liste kanskje? 36 00:01:32,096 --> 00:01:32,950 >> PUBLIKUM: Insertion. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: Insertion. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Hva mener du med det? 40 00:01:35,196 --> 00:01:37,872 >> PUBLIKUM: Anywhere sammen listen [uhørbart]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: Good. 42 00:01:38,770 --> 00:01:42,090 Så du kan sette inn et element hvor du vil i midten av listen 43 00:01:42,090 --> 00:01:45,490 uten å måtte stokke noe, som vi konkluderte, etter vår sortering 44 00:01:45,490 --> 00:01:47,630 diskusjoner, er ikke nødvendigvis en god ting, 45 00:01:47,630 --> 00:01:51,200 fordi det tar tid å faktisk flytte alle disse menneskene til venstre eller høyre. 46 00:01:51,200 --> 00:01:55,540 Og så med en lenket liste, kan du bare bevilge med malloc, en ny node, 47 00:01:55,540 --> 00:01:58,385 og deretter oppdatere et par pointers-- to, tre operasjoner max-- 48 00:01:58,385 --> 00:02:01,480 og vi er i stand til å spor noens i hvor som helst i en liste. 49 00:02:01,480 --> 00:02:03,550 >> Hva annet var en fordel om en lenket liste? 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 >> PUBLIKUM: [uhørbart] 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 Perfect. 57 00:02:11,090 --> 00:02:12,070 Det er veldig dynamisk. 58 00:02:12,070 --> 00:02:15,100 Og at du ikke forplikter, på forhånd, til en viss fast størrelse 59 00:02:15,100 --> 00:02:18,750 blings av minne, som du ville ha til med en rekke, oppsiden som 60 00:02:18,750 --> 00:02:22,455 er at du kan tildele noder bare på etterspørsel og dermed bruke bare så mye plass 61 00:02:22,455 --> 00:02:23,330 som du faktisk trenger. 62 00:02:23,330 --> 00:02:26,830 Derimot med en rekke, kanskje du uhell bevilge for lite. 63 00:02:26,830 --> 00:02:28,871 Og da er det bare å gå å være en smerte i nakken 64 00:02:28,871 --> 00:02:32,440 å omfordele en ny større array, kopiere alt over, frigjøre den gamle array, 65 00:02:32,440 --> 00:02:33,990 og deretter gå om virksomheten din. 66 00:02:33,990 --> 00:02:37,479 Eller verre, kan du fordele måte mer minne enn du faktisk trenger, 67 00:02:37,479 --> 00:02:40,520 og så kommer du til å ha en veldig grisgrendt array, så å si. 68 00:02:40,520 --> 00:02:44,350 >> Så en lenket liste gir deg disse fordelene av dynamikk og fleksibilitet 69 00:02:44,350 --> 00:02:46,080 med innsettinger og slettinger. 70 00:02:46,080 --> 00:02:48,000 Men sikkert det må være en pris som er betalt. 71 00:02:48,000 --> 00:02:50,000 Faktisk et av temaene utforskes på quiz null 72 00:02:50,000 --> 00:02:52,430 var et par av de avveiningene vi har sett så langt. 73 00:02:52,430 --> 00:02:56,161 Så hva er en pris som er betalt eller Ulempen med en lenket liste? 74 00:02:56,161 --> 00:02:56,660 Yeah. 75 00:02:56,660 --> 00:02:57,560 >> PUBLIKUM: Ingen random access. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: Ingen random access. 77 00:02:58,809 --> 00:02:59,540 Men hvem bryr seg? 78 00:02:59,540 --> 00:03:01,546 Random access høres ikke overbevisende. 79 00:03:01,546 --> 00:03:02,421 >> PUBLIKUM: [uhørbart] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Nettopp. 82 00:03:05,740 --> 00:03:07,580 Hvis du vil ha en viss algorithm-- 83 00:03:07,580 --> 00:03:10,170 og la meg faktisk foreslå binært søk i særdeleshet, hvilke 84 00:03:10,170 --> 00:03:12,600 er en vi har brukt ganske bit-- hvis du ikke har random access, 85 00:03:12,600 --> 00:03:15,516 du kan ikke gjøre det enkel aritmetikk for å finne ut midt element 86 00:03:15,516 --> 00:03:16,530 og hoppe rett til det. 87 00:03:16,530 --> 00:03:20,239 Du har i stedet for å begynne på det første element og lineært søke fra venstre 88 00:03:20,239 --> 00:03:22,780 til høyre hvis du ønsker å finne midten eller noe annet element. 89 00:03:22,780 --> 00:03:24,410 >> PUBLIKUM: Det tar nok mer minne. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: Tar mer minne. 91 00:03:25,040 --> 00:03:27,464 Hvor er det ekstra kostet kommer fra i minnet? 92 00:03:27,464 --> 00:03:28,339 >> PUBLIKUM: [uhørbart] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Nettopp. 95 00:03:33,440 --> 00:03:35,679 I dette tilfellet her, vi hadde en lenket liste for heltall, 96 00:03:35,679 --> 00:03:37,470 og likevel er vi dobling mengden minne 97 00:03:37,470 --> 00:03:39,680 vi trenger ved også å lagre disse pekerne. 98 00:03:39,680 --> 00:03:42,090 Nå mindre av en stor avtale som dine structs få større 99 00:03:42,090 --> 00:03:45,320 og du lagrer ikke et tall, men kanskje en student eller en annen gjenstand. 100 00:03:45,320 --> 00:03:46,880 Men poenget forblir sikkert. 101 00:03:46,880 --> 00:03:49,421 Og så en rekke av operasjoner på lenkede lister ble kalt 102 00:03:49,421 --> 00:03:50,570 var stor O av N- lineær. 103 00:03:50,570 --> 00:03:54,730 Ting som innsetting eller søk eller sletting i tilfelle et element 104 00:03:54,730 --> 00:03:57,720 skjedde til å være helt på slutten av listen enten det er sortert eller ikke. 105 00:03:57,720 --> 00:04:01,167 >> Noen ganger kan du ha flaks og i så nedre grense på disse operasjonene 106 00:04:01,167 --> 00:04:04,250 kanskje også konstant tid hvis du er alltid ser på det første elementet, 107 00:04:04,250 --> 00:04:05,070 f.eks. 108 00:04:05,070 --> 00:04:09,360 Men til slutt, vi lovet for å oppnå den hellige gral 109 00:04:09,360 --> 00:04:12,630 av datastrukturer, eller et anslag av disse, 110 00:04:12,630 --> 00:04:14,290 ved hjelp av konstant tid. 111 00:04:14,290 --> 00:04:17,579 Kan vi finne elementer eller legge til elementer eller fjerne elementer fra en liste? 112 00:04:17,579 --> 00:04:19,059 Vi skal se ganske snart. 113 00:04:19,059 --> 00:04:21,100 Og det viser seg at en av de mekanismene vi er 114 00:04:21,100 --> 00:04:23,464 kommer til å begynne å bruke i dag, årlig bruk i p satt fem, 115 00:04:23,464 --> 00:04:24,630 er faktisk ganske kjent. 116 00:04:24,630 --> 00:04:27,430 For eksempel, hvis dette er en gjeng av eksamens bøker, hver av hvilke 117 00:04:27,430 --> 00:04:29,660 har en student først navn og etternavn på den, 118 00:04:29,660 --> 00:04:31,820 og jeg plukke dem opp fra ved slutten av en undersøkelse, 119 00:04:31,820 --> 00:04:33,746 og de er alle ganske mye i en tilfeldig rekkefølge, 120 00:04:33,746 --> 00:04:36,370 og vi ønsker å gå om sortering disse eksamenene slik at når gradert 121 00:04:36,370 --> 00:04:38,661 det er bare mye enklere og raskere å levere dem ut igjen 122 00:04:38,661 --> 00:04:40,030 til studenter alfabetisk. 123 00:04:40,030 --> 00:04:42,770 Hva ville instinktene dine være for en haug av eksamener som dette? 124 00:04:42,770 --> 00:04:45,019 >> Vel, hvis du er som meg, du kan se at dette er m, 125 00:04:45,019 --> 00:04:48,505 så jeg kommer til å liksom sette dette inn i, hvis dette er mitt bord eller min etasje der 126 00:04:48,505 --> 00:04:50,650 Jeg sprer ting out-- eller min matrise really-- 127 00:04:50,650 --> 00:04:52,210 Jeg kan sette alle Ms der inne. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Her er en A. Så jeg kan sette Som over her. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Her er en annen A. Jeg kommer å sette det over her. 132 00:04:57,980 --> 00:05:02,490 Her er en Z. Her er en annen M. Og så Jeg kan begynne å lage hauger som dette. 133 00:05:02,490 --> 00:05:06,620 Og så kanskje jeg ville gå inn senere og liksom veldig pirkete-ly sort 134 00:05:06,620 --> 00:05:07,710 de enkelte hauger. 135 00:05:07,710 --> 00:05:11,300 Men poenget er at jeg ville se på inngangen at jeg er overlevert 136 00:05:11,300 --> 00:05:14,016 og jeg ville gjøre noen beregnes beslutning basert på den inngangen. 137 00:05:14,016 --> 00:05:15,640 Hvis den starter med A, sette den over der. 138 00:05:15,640 --> 00:05:18,980 Hvis den starter med Z, sette den over der, og alt i mellom. 139 00:05:18,980 --> 00:05:22,730 >> Så dette er en teknikk som er generelt kjent som hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 som betyr vanligvis tar som innspill og hjelp som innspill til å beregne 141 00:05:26,550 --> 00:05:30,940 en verdi, vanligvis et tall, og at nummeret er indeksen til en lagrings 142 00:05:30,940 --> 00:05:32,260 beholder, som en matrise. 143 00:05:32,260 --> 00:05:35,490 Så med andre ord, jeg kan ha en hash-funksjon, som jeg gjør i mitt hode, 144 00:05:35,490 --> 00:05:37,940 at hvis jeg ser noen er navn som starter med A, 145 00:05:37,940 --> 00:05:40,190 Jeg kommer til å kartlegge at til null i hodet mitt. 146 00:05:40,190 --> 00:05:44,160 Og hvis jeg ser noen med Z, jeg er kommer til å kartlegge det til 25 i hodet mitt 147 00:05:44,160 --> 00:05:46,220 og deretter sette det inn den siste mest haug. 148 00:05:46,220 --> 00:05:50,990 >> Nå, hvis du tenker på ikke hjernen min men et C-program, hva tallene kunne 149 00:05:50,990 --> 00:05:53,170 du er avhengig av for å oppnå det samme resultatet? 150 00:05:53,170 --> 00:05:55,594 Med andre ord, hvis du hadde ASCII karakter A, 151 00:05:55,594 --> 00:05:57,510 hvordan kan du bestemme hva bøtte til å sette den i? 152 00:05:57,510 --> 00:05:59,801 Du har sannsynligvis ikke vil sette det inn i bøtte 65, som 153 00:05:59,801 --> 00:06:01,840 ville være der borte for ingen god grunn. 154 00:06:01,840 --> 00:06:04,320 Hvor ønsker du å sette A i form av sin ASCII-verdi? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Hvor ønsker du å gjøre til sin ASCII verdi å komme opp med en smartere bøtte 157 00:06:08,920 --> 00:06:09,480 å sette den i? 158 00:06:09,480 --> 00:06:10,206 >> PUBLIKUM: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Yeah. 160 00:06:10,956 --> 00:06:13,190 Så minus A eller minus spesielt 65 hvis det er 161 00:06:13,190 --> 00:06:18,240 en kapital A. Eller 98 dersom det er en liten bokstav a. 162 00:06:18,240 --> 00:06:21,300 Og slik som ville tillate oss å, veldig enkelt og veldig arithmetically, 163 00:06:21,300 --> 00:06:23,260 sette noe inn i en bøtte sånn. 164 00:06:23,260 --> 00:06:26,010 Så det viser seg at vi faktisk gjør dette så godt selv med spørrekonkurranser. 165 00:06:26,010 --> 00:06:29,051 >> Så du kanskje husker du sirklet din undervisning stipendiat navn på omslaget. 166 00:06:29,051 --> 00:06:32,270 Og TF s navn ble organisert i disse kolonnene alfabetisk, 167 00:06:32,270 --> 00:06:34,400 vel, tro det eller ei, når alle 80 pluss av oss 168 00:06:34,400 --> 00:06:37,800 kom sammen den andre natt til klasse, det siste trinnet i vår sensureringen 169 00:06:37,800 --> 00:06:41,830 er til hasj quizer inn i en stor plass på bakken ved [uhørbart] 170 00:06:41,830 --> 00:06:45,110 og å legge alles quizer ut i nøyaktig rekkefølge av deres TF største 171 00:06:45,110 --> 00:06:47,700 navn på omslaget, fordi da er det mye enklere for oss 172 00:06:47,700 --> 00:06:51,290 å søke gjennom at bruk av lineær søke eller annen form for klokskap 173 00:06:51,290 --> 00:06:54,050 for en TF å finne hans eller hennes studentenes quizer. 174 00:06:54,050 --> 00:06:56,060 >> Så denne ideen om hashing at du får se er 175 00:06:56,060 --> 00:07:00,520 ganske kraftig er faktisk ganske vanlig og svært intuitivt, 176 00:07:00,520 --> 00:07:03,000 mye som kanskje dele og erobring var i uke null. 177 00:07:03,000 --> 00:07:05,250 Jeg spoler frem til hackathon et par år siden. 178 00:07:05,250 --> 00:07:08,040 Dette var Zamyla og et par andre gratulasjons ansatte studenter 179 00:07:08,040 --> 00:07:09,030 som de kom. 180 00:07:09,030 --> 00:07:12,680 Og vi hadde en hel haug med folding tabeller det med navnelapper. 181 00:07:12,680 --> 00:07:15,380 Og vi hadde navneskilt organisert med som som der borte 182 00:07:15,380 --> 00:07:16,690 og Zs der borte. 183 00:07:16,690 --> 00:07:20,350 Og så en av TFS veldig smart skrev dette som instruksjonene 184 00:07:20,350 --> 00:07:21,030 for dagen. 185 00:07:21,030 --> 00:07:24,480 Og i uke 12 av semesteret dette alle gjort perfekt forstand og alle 186 00:07:24,480 --> 00:07:25,310 visste hva de skal gjøre. 187 00:07:25,310 --> 00:07:27,900 Men når du har i kø på samme måte, 188 00:07:27,900 --> 00:07:30,272 du implementere samme oppfatningen av en hash. 189 00:07:30,272 --> 00:07:31,730 Så la oss formalisere det litt. 190 00:07:31,730 --> 00:07:32,890 Her er en matrise. 191 00:07:32,890 --> 00:07:36,820 Det er trukket til å være litt wide bare for å skildre, visuelt, 192 00:07:36,820 --> 00:07:38,920 at vi kan sette strenger i noe sånt som dette. 193 00:07:38,920 --> 00:07:41,970 Og denne matrisen er klart av størrelse 26 totalt. 194 00:07:41,970 --> 00:07:43,935 Og ting blir kalt Tabellen vilkårlig. 195 00:07:43,935 --> 00:07:48,930 Men dette er bare en kunstners gjengivelse av hva en hash tabell kan være. 196 00:07:48,930 --> 00:07:52,799 >> Så en hash table nå kommer til å være et høyere nivå datastruktur. 197 00:07:52,799 --> 00:07:54,840 På slutten av dagen vi er i ferd med å se at du 198 00:07:54,840 --> 00:07:58,700 kan implementere en hash table, som er mye som check-in line 199 00:07:58,700 --> 00:08:02,059 på et hackathon mye som dette Tabellen brukes til sortering eksamen bøker. 200 00:08:02,059 --> 00:08:03,850 Men en hash table er slag av dette høye nivået 201 00:08:03,850 --> 00:08:08,250 konsept som kan bruke en matrise under panseret til å gjennomføre det, 202 00:08:08,250 --> 00:08:11,890 eller det kan brukes en lengde liste, eller enda kanskje noen andre datastrukturer. 203 00:08:11,890 --> 00:08:15,590 Og nå som er den theme-- taking noen av disse grunnleggende ingredienser 204 00:08:15,590 --> 00:08:18,310 som en matrise og denne bygningen blokkerer nå en lengde liste 205 00:08:18,310 --> 00:08:21,740 og se hva annet vi kan bygge på toppen av dem, som ingredienser 206 00:08:21,740 --> 00:08:26,550 inn i en oppskrift, som gjør mer og mer interessante og nyttige endelige resultatene. 207 00:08:26,550 --> 00:08:28,680 >> Så med hash table vi kan gjennomføre det 208 00:08:28,680 --> 00:08:32,540 i minnet billedlig som dette, men hvordan kan det faktisk være kodet opp? 209 00:08:32,540 --> 00:08:33,789 Vel, kanskje så enkelt er dette. 210 00:08:33,789 --> 00:08:38,270 Hvis KAPASITET i store bokstaver, er bare noen constant-- for eksempel 26, 211 00:08:38,270 --> 00:08:42,030 for 26 bokstavene i det alphabet-- Jeg kan kalle min variabel tabellen, 212 00:08:42,030 --> 00:08:45,630 og jeg kan hevde at jeg kommer til å sette char stjerner der, eller streng. 213 00:08:45,630 --> 00:08:49,880 Så det er så enkelt som dette hvis du ønsker å implementere en hash table. 214 00:08:49,880 --> 00:08:51,490 Og likevel, dette er egentlig bare en matrise. 215 00:08:51,490 --> 00:08:53,198 Men igjen, en hash Bordet er nå hva vi vil 216 00:08:53,198 --> 00:08:57,470 kalle en abstrakt datatype som er bare liksom en konseptuell lagdeling på toppen 217 00:08:57,470 --> 00:09:00,780 på noe mer dagligdagse nå liker en matrise. 218 00:09:00,780 --> 00:09:02,960 >> Nå, hvordan kan vi gå om å løse problemer? 219 00:09:02,960 --> 00:09:06,980 Vel, tidligere hadde jeg luksusen for å ha nok tabellplass her 220 00:09:06,980 --> 00:09:09,460 slik at jeg kunne sette quizer hvor som helst jeg ville. 221 00:09:09,460 --> 00:09:10,620 Så som kan gå her. 222 00:09:10,620 --> 00:09:12,100 Zs kan gå her. 223 00:09:12,100 --> 00:09:13,230 Ms kan gå her. 224 00:09:13,230 --> 00:09:14,740 Og da jeg hadde litt ekstra plass. 225 00:09:14,740 --> 00:09:18,740 Men dette er litt av en utro retten nå fordi denne tabellen, hvis jeg virkelig 226 00:09:18,740 --> 00:09:22,720 tenkte på det som en matrise, er bare kommer til å være av noen fast størrelse. 227 00:09:22,720 --> 00:09:25,380 >> Så teknisk sett, hvis jeg drar opp en annen student quiz 228 00:09:25,380 --> 00:09:28,490 og se, oh, denne personens navn som begynner med en A også, 229 00:09:28,490 --> 00:09:30,980 Jeg ønsker slags å sette det der. 230 00:09:30,980 --> 00:09:34,740 Men så snart jeg satte den der, hvis denne tabellen faktisk representerer en matrise, 231 00:09:34,740 --> 00:09:37,840 Jeg kommer til å være overordnede eller clobbering hvem denne studentens quiz er. 232 00:09:37,840 --> 00:09:38,340 Høyre? 233 00:09:38,340 --> 00:09:41,972 Hvis dette er en matrise, bare én ting kan gå i hver av disse celler eller elementer. 234 00:09:41,972 --> 00:09:43,680 Og så jeg slags har å velge og vrake. 235 00:09:43,680 --> 00:09:45,735 >> Nå tidligere Jeg slags jukset og gjorde dette eller jeg 236 00:09:45,735 --> 00:09:47,526 bare slags stablet dem over hverandre. 237 00:09:47,526 --> 00:09:49,170 Men det kommer ikke til å fly i kode. 238 00:09:49,170 --> 00:09:52,260 Så hvor kan jeg sette andre eleven hvis navn 239 00:09:52,260 --> 00:09:54,964 er A hvis alt jeg hadde er dette tilgjengelig tabellplass? 240 00:09:54,964 --> 00:09:57,880 Og jeg har brukt tre spilleautomater og det ser ut som det er bare noen få andre. 241 00:09:57,880 --> 00:09:58,959 Hva kan du gjøre? 242 00:09:58,959 --> 00:09:59,834 PUBLIKUM: [uhørbart] 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 Kanskje la oss bare holde det enkelt. 246 00:10:02,370 --> 00:10:02,660 Høyre? 247 00:10:02,660 --> 00:10:04,243 Det passer ikke der jeg ønsker å sette den. 248 00:10:04,243 --> 00:10:07,450 Så jeg kommer til å si det teknisk hvor en B ville gå. 249 00:10:07,450 --> 00:10:09,932 Nå, selvfølgelig, jeg begynner å male meg selv inn i et hjørne. 250 00:10:09,932 --> 00:10:11,890 Hvis jeg får til en student hvis navn er faktisk B, 251 00:10:11,890 --> 00:10:14,840 nå B kommer til å bli flyttet litt fremover, som kan skje, Jepp, 252 00:10:14,840 --> 00:10:17,530 Hvis dette er en B, nå har det å gå her. 253 00:10:17,530 --> 00:10:20,180 >> Og så dette svært raskt kan bli problematisk, 254 00:10:20,180 --> 00:10:23,850 men det er en teknikk som faktisk er henvist til som lineær sentret, 255 00:10:23,850 --> 00:10:26,650 der du bare vurdere din array å være langs linjen. 256 00:10:26,650 --> 00:10:29,680 Og du bare slags sonde eller inspisere alle tilgjengelige element 257 00:10:29,680 --> 00:10:31,360 på jakt etter en ledig flekk. 258 00:10:31,360 --> 00:10:34,010 Og så snart du finner en, slippe deg det der. 259 00:10:34,010 --> 00:10:38,390 >> Nå, prisen blir betalt nå til denne løsningen er hva? 260 00:10:38,390 --> 00:10:41,300 Vi har en fast størrelse matrise, og når jeg setter navn 261 00:10:41,300 --> 00:10:44,059 inn i det, i hvert fall i utgangspunktet, hva som er kjøretiden til innsetting 262 00:10:44,059 --> 00:10:46,350 for å sette studentenes quizer i de rette skuffer? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O av hva? 265 00:10:50,002 --> 00:10:51,147 >> PUBLIKUM: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Jeg hørte big O av n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Ikke sant. 269 00:10:54,300 --> 00:10:56,490 Men vi skal erte hverandre hvorfor i bare et øyeblikk. 270 00:10:56,490 --> 00:10:57,702 Hva annet kan det være? 271 00:10:57,702 --> 00:10:58,755 >> PUBLIKUM: [uhørbart] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN: Og la meg gjøre det visuelt. 273 00:11:00,380 --> 00:11:04,720 Så antar at dette er bokstaven S. 274 00:11:04,720 --> 00:11:05,604 >> PUBLIKUM: Det er én. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Det er én. 276 00:11:06,520 --> 00:11:06,710 Høyre? 277 00:11:06,710 --> 00:11:08,950 Dette er en matrise, hvilke betyr at vi har random access. 278 00:11:08,950 --> 00:11:11,790 Og hvis vi tenker på dette som null, og dette som 25, 279 00:11:11,790 --> 00:11:13,800 og vi innser det, oh, her er mitt innspill S, 280 00:11:13,800 --> 00:11:16,350 Jeg kan sikkert konvertere S, en ASCII-tegn, 281 00:11:16,350 --> 00:11:18,540 til et tilsvarende antall mellom null og 25 282 00:11:18,540 --> 00:11:20,910 og deretter umiddelbart sette det der det hører hjemme. 283 00:11:20,910 --> 00:11:26,120 >> Men selvfølgelig, så snart jeg får til andre personen som har navnet er A eller B eller C 284 00:11:26,120 --> 00:11:29,300 til slutt, hvis jeg har brukt lineær sondering som min løsning, 285 00:11:29,300 --> 00:11:31,360 kjøretiden til innsetting i verste fall 286 00:11:31,360 --> 00:11:33,120 faktisk kommer til å tilfalle inn i hva? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Og jeg fikk høre det her riktig tidlig. 289 00:11:36,045 --> 00:11:36,920 PUBLIKUM: [uhørbart] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: Så det er n faktisk en gang du har et tilstrekkelig stort datasett. 291 00:11:41,620 --> 00:11:44,410 Så, på den ene side, hvis klyngen er stor nok 292 00:11:44,410 --> 00:11:48,287 og dataene dine er sparsom nok, du få denne vakre konstant tid. 293 00:11:48,287 --> 00:11:50,620 Men så snart du begynner få flere og flere elementer, 294 00:11:50,620 --> 00:11:53,200 og bare statistisk du får flere mennesker med bokstaven 295 00:11:53,200 --> 00:11:56,030 En som navnet eller bokstaven B, det kunne potensielt 296 00:11:56,030 --> 00:11:57,900 tilfaller til noe mer lineær. 297 00:11:57,900 --> 00:11:59,640 Så ikke helt perfekt. 298 00:11:59,640 --> 00:12:00,690 Så kan vi gjøre bedre? 299 00:12:00,690 --> 00:12:03,210 >> Vel, hva var vår løsning før når vi 300 00:12:03,210 --> 00:12:06,820 vil ha mer dynamikk enn noe sånt som en matrise tillatt? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 PUBLIKUM: [uhørbart] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: Hva gjorde vi innføre? 304 00:12:10,030 --> 00:12:10,530 Yeah. 305 00:12:10,530 --> 00:12:11,430 Så en lenket liste. 306 00:12:11,430 --> 00:12:14,430 Vel, la oss se hva en koblet Listen kan gjøre for oss i stedet. 307 00:12:14,430 --> 00:12:17,630 Vel, la meg foreslå at vi tegne bildet som følger. 308 00:12:17,630 --> 00:12:19,620 Nå er dette en annerledes bilde fra et eksempel 309 00:12:19,620 --> 00:12:24,750 fra en annen tekst, faktisk, at er faktisk å bruke en matrise av størrelse 31. 310 00:12:24,750 --> 00:12:28,220 Og denne forfatteren rett og slett bestemte seg til hasj strenger 311 00:12:28,220 --> 00:12:32,430 ikke basert på personens navn, men basert på deres fødselsdatoer. 312 00:12:32,430 --> 00:12:35,680 Uavhengig av måneden, de skjønte hvis du er født på den første i en måned 313 00:12:35,680 --> 00:12:39,580 eller den 31. i en måned, forfatteren vil hash basert på denne verdien, 314 00:12:39,580 --> 00:12:44,154 for derved å spre navnene ut en smule mer enn bare 26 flekker kan tillate. 315 00:12:44,154 --> 00:12:47,320 Og kanskje det er litt mer ensartet enn å gå med alfabetiske bokstaver, 316 00:12:47,320 --> 00:12:50,236 fordi selvfølgelig er det sannsynligvis flere mennesker i verden med navn 317 00:12:50,236 --> 00:12:54,020 som starter med A enn absolutt noen andre bokstaver i alfabetet. 318 00:12:54,020 --> 00:12:56,380 Så kanskje dette er litt mer ensartet, forutsatt 319 00:12:56,380 --> 00:12:58,640 en jevn fordeling av babyer over en måned. 320 00:12:58,640 --> 00:12:59,990 >> Men, selvfølgelig, dette er fortsatt mangelfull. 321 00:12:59,990 --> 00:13:00,370 Høyre? 322 00:13:00,370 --> 00:13:01,370 Vi har kollisjoner. 323 00:13:01,370 --> 00:13:04,680 Flere mennesker i denne datastruktur er fortsatt 324 00:13:04,680 --> 00:13:08,432 som har samme fødsels minst du er uavhengig av måned. 325 00:13:08,432 --> 00:13:09,640 Men hva har forfatteren gjort? 326 00:13:09,640 --> 00:13:13,427 Vel, det ser ut som om vi har en rekke på venstre side trekkes vertikalt, 327 00:13:13,427 --> 00:13:15,010 men det er bare en kunstners gjengivelse. 328 00:13:15,010 --> 00:13:18,009 Det spiller ingen rolle hvilken retning du tegne en matrise, er det fortsatt en matrise. 329 00:13:18,009 --> 00:13:20,225 Hva er dette en rekke tilsynelatende? 330 00:13:20,225 --> 00:13:21,500 >> PUBLIKUM: Linked-listen. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Yeah. 332 00:13:21,650 --> 00:13:23,490 Det ser ut som det er en utvalg av lenket liste. 333 00:13:23,490 --> 00:13:26,490 Så igjen, til dette punktet sortering å bruke disse datastrukturer nå 334 00:13:26,490 --> 00:13:28,550 som ingredienser til mer interessante løsninger, 335 00:13:28,550 --> 00:13:30,862 du kan absolutt ta en fundamental, som en matrise, 336 00:13:30,862 --> 00:13:33,320 og deretter ta noe mer interessant som en lenket liste 337 00:13:33,320 --> 00:13:36,660 og selv sette dem sammen til en enda mer interessant datastruktur. 338 00:13:36,660 --> 00:13:39,630 Og ja, dette også ville kalles en hash table, 339 00:13:39,630 --> 00:13:42,610 hvorved matrisen er egentlig hash table, 340 00:13:42,610 --> 00:13:45,600 men at hash tabellen har kjeder, så å si, 341 00:13:45,600 --> 00:13:50,220 som kan vokse eller krympe basert på antall elementer du vil sette inn. 342 00:13:50,220 --> 00:13:52,990 >> Nå følgelig hva som er kjøretiden nå? 343 00:13:52,990 --> 00:13:58,030 Hvis jeg ønsker å sette inn noen som har bursdag 31. oktober 344 00:13:58,030 --> 00:13:59,040 hvor kommer han eller hun gå? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 OK. 347 00:14:01,030 --> 00:14:02,819 Helt nederst der det står 31. 348 00:14:02,819 --> 00:14:03,610 Og det er perfekt. 349 00:14:03,610 --> 00:14:05,060 Det var konstant tid. 350 00:14:05,060 --> 00:14:08,760 Men hva hvis vi finner noen andre som har bursdag er, la oss se, 351 00:14:08,760 --> 00:14:10,950 Oktober, november, desember 31? 352 00:14:10,950 --> 00:14:12,790 Hvor er han eller hun kommer til å gå? 353 00:14:12,790 --> 00:14:13,290 Samme greia. 354 00:14:13,290 --> 00:14:13,970 To skritt skjønt. 355 00:14:13,970 --> 00:14:15,303 Det er konstant skjønt er det ikke? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 OK. 358 00:14:16,860 --> 00:14:17,840 I øyeblikket er det. 359 00:14:17,840 --> 00:14:20,570 Men i det generelle tilfelle, jo flere mennesker vi legger til, 360 00:14:20,570 --> 00:14:23,790 sannsynlighets, skal vi å få flere og flere kollisjoner. 361 00:14:23,790 --> 00:14:26,820 >> Nå er dette en liten bedre fordi teknisk 362 00:14:26,820 --> 00:14:34,580 nå mine kjedene kan være i verste fall hvor lenge? 363 00:14:34,580 --> 00:14:38,890 Hvis jeg setter n folk inn i dette mer sofistikert datastruktur, n mennesker, 364 00:14:38,890 --> 00:14:41,080 i verste fall kommer det til å være n. 365 00:14:41,080 --> 00:14:41,815 Hvorfor? 366 00:14:41,815 --> 00:14:43,332 >> PUBLIKUM: Fordi hvis alle har samme bursdag, 367 00:14:43,332 --> 00:14:44,545 de kommer til å være en linje. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Perfect. 369 00:14:45,420 --> 00:14:47,480 Det kan være litt contrived, men virkelig i verste fall 370 00:14:47,480 --> 00:14:50,117 hvis alle har samme bursdag, gitt de inngangene du har, 371 00:14:50,117 --> 00:14:51,950 du kommer til å ha en massivt lang kjede. 372 00:14:51,950 --> 00:14:54,241 Og så, kan du kalle det en hash table, men egentlig er det 373 00:14:54,241 --> 00:14:56,810 bare en massiv lenket liste med en hel masse bortkastet plass. 374 00:14:56,810 --> 00:15:00,460 Men generelt, hvis vi antar at minst bursdager er uniform-- 375 00:15:00,460 --> 00:15:01,750 og det er sannsynligvis ikke. 376 00:15:01,750 --> 00:15:02,587 Jeg gjør det opp. 377 00:15:02,587 --> 00:15:04,420 Men hvis vi antar, for skyld diskusjonen 378 00:15:04,420 --> 00:15:07,717 at de er, da i teorien, hvis Dette er den vertikale representasjon 379 00:15:07,717 --> 00:15:11,050 av tabellen, vel så forhåpentligvis du er kommer til å få kjeder som er, vet du, 380 00:15:11,050 --> 00:15:15,880 omtrent samme lengde, hvor hver av disse representerer en dag i måneden. 381 00:15:15,880 --> 00:15:19,930 >> Nå hvis det er 31 dager i måneden, det betyr at min kjøretid virkelig 382 00:15:19,930 --> 00:15:25,230 er stor O av n over 31, som føles bedre enn lineær. 383 00:15:25,230 --> 00:15:27,950 Men hva var en av våre forpliktelser et par uker 384 00:15:27,950 --> 00:15:31,145 siden når det kom til å uttrykke kjøretiden til en algoritme? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Bare bare se på høy ordre sikt. 387 00:15:35,190 --> 00:15:35,690 Høyre? 388 00:15:35,690 --> 00:15:37,400 31 er definitivt nyttig. 389 00:15:37,400 --> 00:15:39,610 Men dette er fortsatt stor O av n. 390 00:15:39,610 --> 00:15:41,730 Men et av temaene av problemet satt fem 391 00:15:41,730 --> 00:15:43,950 kommer til å være til erkjenner at absolutt, 392 00:15:43,950 --> 00:15:47,320 asymptotisk, teoretisk dette datastruktur 393 00:15:47,320 --> 00:15:50,470 er ikke bedre enn bare en massiv lenket liste. 394 00:15:50,470 --> 00:15:53,550 Og ja, i verste fall, dette hash table kan tilfalle inn i det. 395 00:15:53,550 --> 00:15:57,620 >> Men i den virkelige verden, med oss ​​mennesker at egne Mac eller PC eller hva 396 00:15:57,620 --> 00:16:01,240 og kjører virkelige verden programvare på virkelige verden data, 397 00:16:01,240 --> 00:16:03,260 hvilken algoritme du kommer til å foretrekke? 398 00:16:03,260 --> 00:16:09,180 Den som tar slutt fremgangsmåte eller en som tar n dividert med 31 trinn 399 00:16:09,180 --> 00:16:12,900 å finne noen stykke data eller å lete opp litt informasjon? 400 00:16:12,900 --> 00:16:16,580 Jeg mener, absolutt de 31 merker en forskjell i den virkelige verden. 401 00:16:16,580 --> 00:16:18,540 Det er 31 ganger raskere. 402 00:16:18,540 --> 00:16:20,880 Og vi mennesker er sikkert kommer til å sette pris på det. 403 00:16:20,880 --> 00:16:23,004 >> Så skjønner motsetningen der mellom faktisk 404 00:16:23,004 --> 00:16:25,920 snakke om ting teoretisk og asymptotisk som definitivt 405 00:16:25,920 --> 00:16:28,760 har verdi som vi har sett, men i den virkelige verden, 406 00:16:28,760 --> 00:16:32,930 Hvis du bryr deg om bare å gjøre menneskelig glad for generelle innganger, 407 00:16:32,930 --> 00:16:36,010 du kan godt vil godta det faktum at, ja, dette er lineær, 408 00:16:36,010 --> 00:16:38,360 men det er 31 ganger raskere enn lineær kan være. 409 00:16:38,360 --> 00:16:41,610 Og enda bedre, vi trenger ikke bare å gjøre noe vilkårlig som en fødselsdato, 410 00:16:41,610 --> 00:16:44,030 vi kunne bruke litt mer tid og kløkt 411 00:16:44,030 --> 00:16:47,140 og tenke på hva vi kan gjøre, gitt en persons navn og kanskje 412 00:16:47,140 --> 00:16:50,130 deres fødselsdato for å kombinere de ingredienser for å finne ut noe 413 00:16:50,130 --> 00:16:52,720 som er virkelig mer enhetlig og mindre jaggy, 414 00:16:52,720 --> 00:16:56,250 så å si enn dette bildet tiden antyder det kan være. 415 00:16:56,250 --> 00:16:57,750 Hvordan kan vi implementere dette i koden? 416 00:16:57,750 --> 00:17:00,280 Vel, la meg foreslå at vi bare låne noen syntaks vi har 417 00:17:00,280 --> 00:17:01,799 brukt et par ganger så langt. 418 00:17:01,799 --> 00:17:03,590 Og jeg kommer til å definere en node, som igjen 419 00:17:03,590 --> 00:17:06,812 er en fellesbetegnelse for bare noen container for noen datastruktur. 420 00:17:06,812 --> 00:17:09,020 Jeg kommer til å foreslå at en streng som skjer der inne. 421 00:17:09,020 --> 00:17:11,369 Men vi kommer til å begynne å ta de som trening hjul av nå. 422 00:17:11,369 --> 00:17:13,230 >> Ingen flere CS50 biblioteket egentlig, med mindre du vil 423 00:17:13,230 --> 00:17:15,230 å bruke den for den endelige Prosjektet, som er greit, 424 00:17:15,230 --> 00:17:18,569 men nå skal vi trekke tilbake gardin og sier det er bare en char stjerne. 425 00:17:18,569 --> 00:17:22,069 Så ordet det kommer til å være personens navn i spørsmålet. 426 00:17:22,069 --> 00:17:25,079 Og nå har jeg en link her til den neste noden 427 00:17:25,079 --> 00:17:28,170 slik at disse representerer hver av nodene 428 00:17:28,170 --> 00:17:30,950 i kjeden, eventuelt, av en lenket liste. 429 00:17:30,950 --> 00:17:34,090 >> Og nå hvordan kan jeg erklære hash bordet selv? 430 00:17:34,090 --> 00:17:36,660 Hvordan erklærer jeg hele denne strukturen? 431 00:17:36,660 --> 00:17:40,960 Vel, egentlig, mye som jeg brukte en peker til bare det første element i en liste 432 00:17:40,960 --> 00:17:44,510 før, på samme måte kan jeg bare si Jeg trenger bare en haug med pekere 433 00:17:44,510 --> 00:17:46,270 å gjennomføre hele denne hash table. 434 00:17:46,270 --> 00:17:49,484 Jeg kommer til å ha en rekke kalt tabell for hash table. 435 00:17:49,484 --> 00:17:50,900 Det kommer til å være av størrelse kapasitet. 436 00:17:50,900 --> 00:17:52,525 Det er hvor mange elementer kan passe i den. 437 00:17:52,525 --> 00:17:56,180 Og hvert av disse elementer i denne matrise kommer til å være en node stjerne. 438 00:17:56,180 --> 00:17:56,810 Hvorfor? 439 00:17:56,810 --> 00:18:00,160 Vel, per dette bildet, hva jeg er implementere hash table som 440 00:18:00,160 --> 00:18:04,330 effektivt i begynnelsen er bare denne matrisen som vi har trukket vertikalt, 441 00:18:04,330 --> 00:18:06,820 hver av hvis firkanter representerer en peker. 442 00:18:06,820 --> 00:18:09,170 At de som har skråstreker gjennom dem er bare null. 443 00:18:09,170 --> 00:18:11,410 Og de som har piler som går til høyre 444 00:18:11,410 --> 00:18:16,140 er faktiske pekere til faktiske noder, ergo starten på en lenket liste. 445 00:18:16,140 --> 00:18:19,050 >> Så her er altså hvordan vi kan implementere en hash tabell som 446 00:18:19,050 --> 00:18:21,580 implementerer separat kjeding. 447 00:18:21,580 --> 00:18:22,840 Nå kan vi gjøre bedre? 448 00:18:22,840 --> 00:18:25,632 Greit jeg lovet sist gang vi kunne oppnå konstant tid. 449 00:18:25,632 --> 00:18:27,381 Og jeg slags ga deg konstant tid her, 450 00:18:27,381 --> 00:18:29,850 men da sa egentlig ikke konstant tid fordi det er fremdeles 451 00:18:29,850 --> 00:18:31,890 avhengig av den totale antall elementer 452 00:18:31,890 --> 00:18:34,500 du legge inn i datastrukturen. 453 00:18:34,500 --> 00:18:35,980 Men sett at vi gjorde dette. 454 00:18:35,980 --> 00:18:39,550 La meg gå tilbake til skjermen over her. 455 00:18:39,550 --> 00:18:44,520 La meg også projisere dette opp her, klar skjermen, og antar at jeg gjorde dette. 456 00:18:44,520 --> 00:18:49,300 Anta at jeg ønsket å påføre navnet Daven i inn i min datastruktur. 457 00:18:49,300 --> 00:18:52,100 >> Så jeg ønsker å sette inn en streng Daven inn i datastrukturen. 458 00:18:52,100 --> 00:18:54,370 Hva om jeg ikke bruker en hash table, men jeg bruker 459 00:18:54,370 --> 00:18:56,980 noe som er mer trelignende som et familietre, der 460 00:18:56,980 --> 00:18:59,670 du har litt rot på toppen og deretter noder og bladene 461 00:18:59,670 --> 00:19:01,440 som går nedover og utover. 462 00:19:01,440 --> 00:19:04,450 Anta så at jeg vil sette inn Daven s 463 00:19:04,450 --> 00:19:06,430 i hva som er i dag en tom liste. 464 00:19:06,430 --> 00:19:09,780 Jeg kommer til å gjøre følgende: Jeg er kommer til å skape en node i denne familien 465 00:19:09,780 --> 00:19:15,170 trelignende datastruktur som ser litt som denne, hver av hvilke 466 00:19:15,170 --> 00:19:19,640 rektangler har, la oss si, for nå 26 elementer i den. 467 00:19:19,640 --> 00:19:21,650 Og hver av cellene i denne matrisen kommer 468 00:19:21,650 --> 00:19:23,470 å representere bokstaven i et alfabet. 469 00:19:23,470 --> 00:19:28,190 >> Spesielt kommer jeg til å behandle dette er A, så B, så C, deretter D, 470 00:19:28,190 --> 00:19:29,310 denne her. 471 00:19:29,310 --> 00:19:32,940 Så dette kommer til å effektivt representerer bokstaven D. 472 00:19:32,940 --> 00:19:36,040 Men for å sette inn alle Daven s nevne jeg trenger å gjøre litt mer. 473 00:19:36,040 --> 00:19:37,840 Så jeg først kommer til hasj, så å si. 474 00:19:37,840 --> 00:19:41,049 Jeg kommer til å se på den første bokstaven i Daven s, som er åpenbart en D, 475 00:19:41,049 --> 00:19:42,840 og jeg kommer til å tildele en node som ser 476 00:19:42,840 --> 00:19:45,570 som dette-- en stor rektangel stor nok til å passe hele alfabetet. 477 00:19:45,570 --> 00:19:47,140 >> Nå D er gjort. 478 00:19:47,140 --> 00:19:49,720 Nå A. D-A-V-E-N er målet. 479 00:19:49,720 --> 00:19:51,220 Så nå hva jeg kommer til å gjøre dette. 480 00:19:51,220 --> 00:19:54,027 Så snart jeg begynte D varsel det er ingen pekeren der. 481 00:19:54,027 --> 00:19:56,860 Det er søppel verdier i øyeblikket, eller jeg kan initialisere den til null. 482 00:19:56,860 --> 00:19:59,630 Men la meg holde det gående med denne ideen om å bygge et tre. 483 00:19:59,630 --> 00:20:04,260 La meg fordele enda en av disse noder som har 26 elementer i den. 484 00:20:04,260 --> 00:20:05,150 >> Og vet du hva? 485 00:20:05,150 --> 00:20:09,130 Hvis dette bare er en node i minnet som Jeg opprettet med malloc, ved hjelp av en struct 486 00:20:09,130 --> 00:20:11,240 som vi vil snart se, Jeg kommer til å gjøre dette-- 487 00:20:11,240 --> 00:20:14,450 Jeg kommer til å trekke en pil fra det som representerte D ned 488 00:20:14,450 --> 00:20:15,860 til denne nye node. 489 00:20:15,860 --> 00:20:19,240 Og nå, først neste brev i Daven navn, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- jeg kommer til å gå videre og tegne en annen node som dette, 491 00:20:24,150 --> 00:20:30,150 hvorved, de V-elementer, som her vi vil trekke for instance-- whoops. 492 00:20:30,150 --> 00:20:31,020 Vi vil ikke trekke det. 493 00:20:31,020 --> 00:20:31,936 Det kommer til å gå her. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Så skal vi til anser dette for å være V. 496 00:20:35,712 --> 00:20:44,920 Og deretter ned her vi kommer til å indeksere ned fra V inn i hva vi vil vurdere E. 497 00:20:44,920 --> 00:20:50,100 Og så herfra vi kommer til å gå har en av disse nodene her. 498 00:20:50,100 --> 00:20:52,930 Og nå har vi et spørsmål å besvare. 499 00:20:52,930 --> 00:20:57,840 Jeg må liksom vise at vi er på slutten av strengen Daven. 500 00:20:57,840 --> 00:20:59,490 Så jeg kunne bare la det null. 501 00:20:59,490 --> 00:21:02,670 >> Men hva hvis vi har Daven s fullt navn også, som 502 00:21:02,670 --> 00:21:04,280 er, som vi har sagt, Davenport? 503 00:21:04,280 --> 00:21:06,970 Så hva om Daven er faktisk en delstreng, 504 00:21:06,970 --> 00:21:08,960 et prefiks på en mye lengre streng? 505 00:21:08,960 --> 00:21:11,450 Vi kan ikke bare permanent sier ingenting kommer 506 00:21:11,450 --> 00:21:14,410 å gå dit, fordi vi kunne aldri sette inn et ord som Davenport 507 00:21:14,410 --> 00:21:15,840 inn i dette datastruktur 508 00:21:15,840 --> 00:21:19,560 >> Så hva vi kunne gjøre i stedet er behandling av hvert av disse elementene 509 00:21:19,560 --> 00:21:22,170 så kanskje å ha to elementer på innsiden av dem. 510 00:21:22,170 --> 00:21:24,810 Den ene er en peker, ja, som jeg har gjort. 511 00:21:24,810 --> 00:21:27,100 Slik at hver av disse boksene er ikke bare en celle. 512 00:21:27,100 --> 00:21:29,855 Men hva hvis toppen one-- bunnen ens 513 00:21:29,855 --> 00:21:32,230 kommer til å være null, fordi det er ingen Davenport ennå. 514 00:21:32,230 --> 00:21:34,197 Hva om den øverste er noen spesiell verdi? 515 00:21:34,197 --> 00:21:36,530 Og det kommer til å være litt vanskelig å trekke det på denne størrelsen. 516 00:21:36,530 --> 00:21:38,130 Men antar at det er bare en hake. 517 00:21:38,130 --> 00:21:38,920 Sjekk. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N er en streng i dette datastruktur. 519 00:21:44,230 --> 00:21:48,350 >> I mellomtiden, hvis jeg hadde mer plass her, kunne jeg gjøre P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 og jeg kunne sette innsjekking noden som har bokstaven T helt på slutten. 521 00:21:52,650 --> 00:21:55,460 Så dette er et massivt kompleks utseende datastruktur. 522 00:21:55,460 --> 00:21:57,210 Og min håndskrift absolutt ikke hjelpe. 523 00:21:57,210 --> 00:22:00,043 Men hvis jeg ønsket å sette inn noe annet, vurdere hva vi ville gjøre. 524 00:22:00,043 --> 00:22:03,370 Hvis vi ønsket å sette David inn, vi vil følge samme logikk, D-A-V, 525 00:22:03,370 --> 00:22:08,802 men nå vil jeg peke på det neste element ikke fra E, men fra jeg til D. 526 00:22:08,802 --> 00:22:10,760 Så det kommer til å bli flere noder i dette treet. 527 00:22:10,760 --> 00:22:12,325 Vi kommer til å ha samtale malloc mer. 528 00:22:12,325 --> 00:22:14,700 Men jeg ønsker ikke å gjøre en komplett rot av dette bildet. 529 00:22:14,700 --> 00:22:17,710 Så la oss i stedet se på en som er blitt pre-formulert 530 00:22:17,710 --> 00:22:21,810 som dette med ikke prikk, prikk, prikker, men bare forkortede arrays. 531 00:22:21,810 --> 00:22:23,950 Men hver av nodene i dette treet her oppe 532 00:22:23,950 --> 00:22:26,700 representerer den samme thing-- en rekke Ray størrelse 26. 533 00:22:26,700 --> 00:22:28,860 >> Eller hvis vi ønsker å være virkelig riktig nå, hva 534 00:22:28,860 --> 00:22:30,790 hvis noen navn som en apostrof, la oss 535 00:22:30,790 --> 00:22:35,560 anta at hver node har faktisk som 27 indekser i den, ikke bare 26. 536 00:22:35,560 --> 00:22:42,020 Så dette nå kommer til å være en data struktur kalt en trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 En trie, som er visstnok historisk et smart navn for et tre 538 00:22:46,120 --> 00:22:49,040 som er optimalisert for gjenfinning, som selvfølgelig 539 00:22:49,040 --> 00:22:50,870 er stavet med en jeg-E, så det er trie. 540 00:22:50,870 --> 00:22:52,710 Men det er historien om den trie. 541 00:22:52,710 --> 00:22:55,860 >> Så en trie er dette trelignende data struktur som et familietre 542 00:22:55,860 --> 00:22:57,510 som til slutt oppfører seg sånn. 543 00:22:57,510 --> 00:23:00,890 Og her er bare et eksempel på en hel haug med andre personers navn. 544 00:23:00,890 --> 00:23:03,540 Men spørsmålet nå på hånden er hva har 545 00:23:03,540 --> 00:23:08,070 vi oppnådd ved å innføre uten tvil en mer komplisert datastruktur, og en, 546 00:23:08,070 --> 00:23:09,870 ærlig, bruker den mye minne. 547 00:23:09,870 --> 00:23:11,703 >> For selv om, i øyeblikket, jeg er bare 548 00:23:11,703 --> 00:23:15,050 ved hjelp av D's pekeren og A og V og Es og Ns, 549 00:23:15,050 --> 00:23:16,700 Jeg kaster bort en pokker for mye minne. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Men hvor jeg tilbringer en ressurs, Jeg pleier å gjøre å få tilbake en annen. 552 00:23:22,660 --> 00:23:26,020 Så hvis jeg tilbringer mer plass, hva er nok håp? 553 00:23:26,020 --> 00:23:27,407 At jeg tilbringer mindre hva? 554 00:23:27,407 --> 00:23:28,240 PUBLIKUM: Mindre tid. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Tid. 556 00:23:28,990 --> 00:23:30,320 Nå hvorfor kan det være? 557 00:23:30,320 --> 00:23:33,880 Vel, hva er innsetting tid, i form av store O nå, 558 00:23:33,880 --> 00:23:37,660 av et navn som Daven eller Davenport eller David? 559 00:23:37,660 --> 00:23:39,340 Vel, Daven var fem trinn. 560 00:23:39,340 --> 00:23:42,350 Davenport ville være ni trinn, så det ville være noen flere trinn. 561 00:23:42,350 --> 00:23:44,250 David ville være fem trinn også. 562 00:23:44,250 --> 00:23:47,230 Så de er konkrete tall, men sikkert er det 563 00:23:47,230 --> 00:23:49,550 en øvre grense på Lengden på noens navn. 564 00:23:49,550 --> 00:23:52,240 Og ja, i problemet sett av fem spesifikasjonen, 565 00:23:52,240 --> 00:23:54,050 vi kommer til å foreslå at det er noe 566 00:23:54,050 --> 00:23:55,470 det er 40-some-odd tegn. 567 00:23:55,470 --> 00:23:58,180 >> Realistisk, har ingen en uendelig langt navn, 568 00:23:58,180 --> 00:24:01,542 det vil si at lengden av en navngi eller lengden på en streng vi kan 569 00:24:01,542 --> 00:24:03,750 har visse tilstanden strukturen er uten tvil hva? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Det er konstant. 572 00:24:06,250 --> 00:24:06,430 Høyre? 573 00:24:06,430 --> 00:24:09,310 Det kan være en stor konstant som 40-noe, men det er konstant. 574 00:24:09,310 --> 00:24:13,752 Og det har ingen avhengighet av hvor mange andre navn er i denne datastruktur. 575 00:24:13,752 --> 00:24:15,460 Med andre ord, hvis jeg ønsket å nå sette 576 00:24:15,460 --> 00:24:20,540 Colton eller Gabriel eller Rob eller Zamyla eller Alison eller Belinda eller noen andre navn 577 00:24:20,540 --> 00:24:23,940 fra de ansatte i disse dataene struktur, er kjøretiden 578 00:24:23,940 --> 00:24:26,750 med å sette inn andre navn kommer til å være på alle påvirket 579 00:24:26,750 --> 00:24:30,220 av hvor mange andre elementer er i datastrukturen allerede? 580 00:24:30,220 --> 00:24:31,040 Det er ikke. 581 00:24:31,040 --> 00:24:31,540 Høyre? 582 00:24:31,540 --> 00:24:36,150 Fordi vi er effektivt ved hjelp Dette multi-layer hash table. 583 00:24:36,150 --> 00:24:38,280 Og kjøretiden til en hvilken som helst av disse operasjoner 584 00:24:38,280 --> 00:24:41,510 ikke er avhengig av antall elementer som er i datastrukturen 585 00:24:41,510 --> 00:24:43,090 eller som eventuelt kommer å være i datastrukturen, 586 00:24:43,090 --> 00:24:44,714 men av lengden av det spesifikt? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Strengen blir settes inn, noe som gjør gjøre 589 00:24:49,200 --> 00:24:52,580 dette asymptotisk konstant tid-- big O av en. 590 00:24:52,580 --> 00:24:54,720 Og ærlig talt, bare i den virkelige verden, dette 591 00:24:54,720 --> 00:24:58,380 betyr å sette inn Daven navn tar som fem trinn, eller Davenport ni 592 00:24:58,380 --> 00:25:00,100 trinn, eller David fem trinn. 593 00:25:00,100 --> 00:25:03,071 Det er ganske utrolig små løpetider. 594 00:25:03,071 --> 00:25:05,320 Og, ja, det er en veldig god ting, spesielt når 595 00:25:05,320 --> 00:25:08,126 det er ikke avhengig av den totale antall elementer i det. 596 00:25:08,126 --> 00:25:10,500 Så hvordan kan vi implementere dette slags struktur i koden? 597 00:25:10,500 --> 00:25:12,900 Det er litt mer kompleks, men fortsatt er det 598 00:25:12,900 --> 00:25:15,050 bare en anvendelse av grunnleggende byggesteiner. 599 00:25:15,050 --> 00:25:17,830 Jeg kommer til å omdefinere oss node som følger: 600 00:25:17,830 --> 00:25:21,100 bool kalt word-- og dette kan kalles noe. 601 00:25:21,100 --> 00:25:23,970 Men bool representerer hva jeg trakk som en hake. 602 00:25:23,970 --> 00:25:24,490 Ja. 603 00:25:24,490 --> 00:25:26,720 Dette er slutten av en streng i dette datastruktur. 604 00:25:26,720 --> 00:25:30,702 >> Og, selvfølgelig, noden stjerne Det er med henvisning til barn. 605 00:25:30,702 --> 00:25:32,410 Og, ja, akkurat som et familietre, du 606 00:25:32,410 --> 00:25:34,370 ville vurdere nodene som henger utenfor 607 00:25:34,370 --> 00:25:36,920 av bunnen av en moder element til å være barn. 608 00:25:36,920 --> 00:25:40,510 Og slik at barna kommer til å være en matrise på 27, den 27. en 609 00:25:40,510 --> 00:25:41,680 bare å være for apostrof. 610 00:25:41,680 --> 00:25:43,390 Vi kommer til å sortere av spesiell sak det. 611 00:25:43,390 --> 00:25:45,400 Så du kan ha visse navn med apostrofer. 612 00:25:45,400 --> 00:25:47,399 Kanskje til og med bindestrek bør gå inn der, men du vil 613 00:25:47,399 --> 00:25:50,330 se i p sett fem vi bare omsorg om bokstaver og apostrofer. 614 00:25:50,330 --> 00:25:52,990 >> Og så hvordan gjør du representerer datastrukturen i seg selv? 615 00:25:52,990 --> 00:25:56,454 Hvordan kan representere deg roten av dette trie, så å si? 616 00:25:56,454 --> 00:25:59,620 Vel, akkurat som med en lenket liste, du trenger en peker til det første elementet. 617 00:25:59,620 --> 00:26:04,270 Med en trie du trenger bare én Peker til roten av dette trie. 618 00:26:04,270 --> 00:26:07,290 Og derfra kan du hasj vei ned dypere og dypere 619 00:26:07,290 --> 00:26:10,460 til alle andre knutepunktet i strukturen. 620 00:26:10,460 --> 00:26:13,440 Så enkelt med denne boksen vi representerer at struct. 621 00:26:13,440 --> 00:26:15,877 >> Nå Meanwhile-- Oh, spørsmålet. 622 00:26:15,877 --> 00:26:17,220 >> PUBLIKUM: Hva er bool ord? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: Bool ordet er nettopp dette C inkarnasjon 624 00:26:20,490 --> 00:26:22,920 av hva jeg beskrev I denne boksen her, når 625 00:26:22,920 --> 00:26:26,000 Jeg begynte å splitte hver av de tabellens elementer i to deler. 626 00:26:26,000 --> 00:26:27,600 Den ene er en peker til den neste noden. 627 00:26:27,600 --> 00:26:30,280 Den andre har til å bli noe sånt som en avkrysningsboks 628 00:26:30,280 --> 00:26:33,770 å si ja, det er en Ordet Daven som ender her, 629 00:26:33,770 --> 00:26:35,610 fordi vi ikke ønsker, i øyeblikket, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Selv om Dave kommer til å bli en legitime ord, han er ikke i trie 631 00:26:39,320 --> 00:26:39,830 ennå. 632 00:26:39,830 --> 00:26:40,950 Og D er ikke et ord. 633 00:26:40,950 --> 00:26:42,770 Og D-A er ikke et ord eller et navn. 634 00:26:42,770 --> 00:26:45,020 Så hake indikerer bare når du 635 00:26:45,020 --> 00:26:48,190 treffe denne node er forrige banen tegn 636 00:26:48,190 --> 00:26:50,700 faktisk en streng som du har satt inn. 637 00:26:50,700 --> 00:26:53,660 Så det er all bool det gjør for oss. 638 00:26:53,660 --> 00:26:55,500 >> Eventuelle andre spørsmål på prøver? 639 00:26:55,500 --> 00:26:56,215 Yeah. 640 00:26:56,215 --> 00:26:58,035 >> PUBLIKUM: Hva er overlapping? 641 00:26:58,035 --> 00:26:59,945 Hva hvis du har en Dave og Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Perfect. 643 00:27:00,820 --> 00:27:02,580 Hva hvis du har en Dave og Daven? 644 00:27:02,580 --> 00:27:06,240 Så hvis vi setter inn, sier et kallenavn, for David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Dette er faktisk super enkelt. 647 00:27:08,700 --> 00:27:10,325 Så vi bare kommer til å ta fire trinn. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Og hva må jeg gjøre når jeg treffer det fjerde node? 650 00:27:15,847 --> 00:27:16,680 Bare kommer til å sjekke. 651 00:27:16,680 --> 00:27:18,000 Vi er allerede godt å gå. 652 00:27:18,000 --> 00:27:18,840 Ferdig. 653 00:27:18,840 --> 00:27:19,750 Fire trinn. 654 00:27:19,750 --> 00:27:21,590 Konstant tid asymptotisk. 655 00:27:21,590 --> 00:27:26,300 Og nå har vi indikert at både Dave og Daven er strenger i strukturen. 656 00:27:26,300 --> 00:27:27,710 Så det er ikke et problem. 657 00:27:27,710 --> 00:27:30,200 Og legg merke til hvordan tilstedeværelsen av Daven ikke gjøre det 658 00:27:30,200 --> 00:27:34,750 ta noe mer tid eller mindre tid for Dave og vice versa. 659 00:27:34,750 --> 00:27:36,000 >> Så hva annet kan vi nå gjøre? 660 00:27:36,000 --> 00:27:40,680 Vi har brukt denne metaforen før av skuffer som representerer noe. 661 00:27:40,680 --> 00:27:43,380 Men det viser seg at en stabel med magasiner er faktisk 662 00:27:43,380 --> 00:27:47,187 demonstrative av en annen abstrakt data type-- et høyere nivå datastrukturen 663 00:27:47,187 --> 00:27:49,770 at på slutten av dagen er bare som en matrise eller en lenket liste 664 00:27:49,770 --> 00:27:50,970 eller noe mer verdslig. 665 00:27:50,970 --> 00:27:53,270 Men det er en mer interessant konseptuelle konsept. 666 00:27:53,270 --> 00:27:56,440 En stabel, som disse skuffer her i Mather, 667 00:27:56,440 --> 00:27:58,750 er generelt kalt bare at-- en stabel. 668 00:27:58,750 --> 00:28:02,540 >> Og i denne type datastruktur du har to operations-- 669 00:28:02,540 --> 00:28:05,880 du har en som heter push for legge noe til stakken, 670 00:28:05,880 --> 00:28:08,320 som å sette en annen skuff Tilbake på toppen av bunken. 671 00:28:08,320 --> 00:28:11,350 Og så pop, som betyr at du ta den øverste skuffen av. 672 00:28:11,350 --> 00:28:16,210 Men hva er nøkkelen om en stabel er at det har denne merkelige kjennetegn. 673 00:28:16,210 --> 00:28:19,560 Som spisesalen ansatte er omorganisere skuffene for neste måltid, 674 00:28:19,560 --> 00:28:21,380 hva som kommer til å være sant om hvordan elevene 675 00:28:21,380 --> 00:28:22,856 samhandle med denne datastruktur? 676 00:28:22,856 --> 00:28:24,480 PUBLIKUM: De kommer til å sprette en av. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: De kommer til å pop en av, forhåpentligvis toppen. 678 00:28:26,550 --> 00:28:28,910 Ellers er det bare slags dum å gå helt ned til bunnen. 679 00:28:28,910 --> 00:28:29,070 Høyre? 680 00:28:29,070 --> 00:28:31,620 Datastrukturen ikke virkelig tillate du å ta tak i nederste skuff minst 681 00:28:31,620 --> 00:28:32,520 enkelt. 682 00:28:32,520 --> 00:28:35,040 Så det er denne merke egenskapen til en stabel 683 00:28:35,040 --> 00:28:39,730 at det siste elementet i er kommer til å bli den første ut. 684 00:28:39,730 --> 00:28:43,400 Og dataforskere kaller Dette LIFO-- sist inn, først ut. 685 00:28:43,400 --> 00:28:45,540 Og det faktisk har interessante programmer. 686 00:28:45,540 --> 00:28:50,090 Det er ikke nødvendigvis så opplagt som noen andre, men det kan faktisk være nyttig, 687 00:28:50,090 --> 00:28:54,040 og det kan faktisk bli implementert i et par forskjellige måter. 688 00:28:54,040 --> 00:28:58,550 >> Så en, og faktisk, la meg ikke til å dykke inn i den. 689 00:28:58,550 --> 00:28:59,860 La oss gjøre dette i stedet. 690 00:28:59,860 --> 00:29:03,700 La oss se på en som er nesten det samme idé, men det er litt mer rettferdig. 691 00:29:03,700 --> 00:29:04,200 Høyre? 692 00:29:04,200 --> 00:29:07,560 Hvis du er en av disse fan gutter eller jenter som virkelig liker Apple-produkter 693 00:29:07,560 --> 00:29:10,130 og du våknet opp på 3:00 til å stille opp på noen butikk 694 00:29:10,130 --> 00:29:14,150 å få den aller nyeste iPhone, du kan ha kø som dette. 695 00:29:14,150 --> 00:29:15,800 >> Nå en kø er veldig bevisst navngitt. 696 00:29:15,800 --> 00:29:18,190 Det er en linje fordi det er noen rettferdighet til det. 697 00:29:18,190 --> 00:29:18,690 Høyre? 698 00:29:18,690 --> 00:29:21,690 Det ville slags sugd hvis du har fikk det først på Apple Store 699 00:29:21,690 --> 00:29:25,700 men du er effektivt den nederste skuffen fordi Apple ansatte deretter 700 00:29:25,700 --> 00:29:28,189 pop den siste personen som fikk faktisk i kø. 701 00:29:28,189 --> 00:29:31,230 Så stabler og køer, selv om det funksjonelt de er slag av same-- 702 00:29:31,230 --> 00:29:33,105 det er bare denne samlingen av ressurser som finnes i 703 00:29:33,105 --> 00:29:36,210 kommer til å vokse og shrink-- det har denne rettferdighet aspekt til det, 704 00:29:36,210 --> 00:29:39,634 i hvert fall i den virkelige verden, hvor operasjonene du trener 705 00:29:39,634 --> 00:29:40,800 er fundamentalt forskjellig. 706 00:29:40,800 --> 00:29:43,360 En stack-- en kø rather-- sies å ha 707 00:29:43,360 --> 00:29:45,320 to operasjoner: n køen og d køen. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Eller du kan ringe dem en rekke ting. 710 00:29:48,090 --> 00:29:50,770 Men du bare ønsker å fange forestillingen om at man legger til 711 00:29:50,770 --> 00:29:53,230 og én er til syvende og sist å subtrahere. 712 00:29:53,230 --> 00:29:58,840 >> Nå under panseret, både stakken og en kø kunne gjennomføres hvordan? 713 00:29:58,840 --> 00:30:01,390 Vi vil ikke gå inn koden det fordi høyere nivå 714 00:30:01,390 --> 00:30:03,387 Tanken er liksom mer opplagt. 715 00:30:03,387 --> 00:30:04,470 Jeg mener, hva gjør mennesker? 716 00:30:04,470 --> 00:30:07,030 Hvis jeg er den første personen på Apple Lagre og dette er inngangsdøren, 717 00:30:07,030 --> 00:30:08,130 du vet, jeg kommer til å stå her. 718 00:30:08,130 --> 00:30:09,750 Og neste persons kommer til å stå her. 719 00:30:09,750 --> 00:30:11,500 Og neste persons kommer til å stå her. 720 00:30:11,500 --> 00:30:13,792 Så hva datastruktur gir seg til en kø? 721 00:30:13,792 --> 00:30:14,542 >> PUBLIKUM: En kø. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Vel, en kø. 723 00:30:15,667 --> 00:30:16,390 Jada. 724 00:30:16,390 --> 00:30:16,920 Hva annet? 725 00:30:16,920 --> 00:30:17,600 >> PUBLIKUM: En lenket liste. 726 00:30:17,600 --> 00:30:18,990 >> DAVID MALAN: Et koblet listen du kan implementere. 727 00:30:18,990 --> 00:30:22,500 Og en lenket liste er fint fordi da den kan vokse vilkårlig lange motsetning 728 00:30:22,500 --> 00:30:24,880 å ha noen fast antall mennesker i butikken. 729 00:30:24,880 --> 00:30:27,030 Men kanskje et fast antall plasser er legitim. 730 00:30:27,030 --> 00:30:30,350 Fordi hvis de bare har som 20 iPhones på den første dagen, kanskje 731 00:30:30,350 --> 00:30:33,930 de trenger bare et utvalg av størrelse 20 for å representere at køen, som 732 00:30:33,930 --> 00:30:37,070 er bare å si nå når vi begynner å snakke om disse høyere nivå problemer, 733 00:30:37,070 --> 00:30:38,890 du kan gjennomføre det i en rekke måter. 734 00:30:38,890 --> 00:30:42,030 Og det er sannsynligvis bare kommer til å være en avveining i rom og tid 735 00:30:42,030 --> 00:30:43,950 eller bare i din egen kode kompleksitet. 736 00:30:43,950 --> 00:30:45,380 >> Hva med en stabel? 737 00:30:45,380 --> 00:30:48,190 Vel, en stabel, vi har sett altfor kan bare være disse skuffene. 738 00:30:48,190 --> 00:30:50,007 Og du kan implementere dette en matrise. 739 00:30:50,007 --> 00:30:53,090 Men på et tidspunkt hvis du bruker en matrise, hva kommer til å skje med magasinene 740 00:30:53,090 --> 00:30:54,173 du prøver å legge ned? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 OK. 743 00:30:55,670 --> 00:30:57,490 Du bare kommer til være i stand til å gå så høyt. 744 00:30:57,490 --> 00:31:00,156 Og jeg tror i Mather de er faktisk innfelt i den åpningen. 745 00:31:00,156 --> 00:31:01,950 Så ja, det er nesten som Mather bruker 746 00:31:01,950 --> 00:31:03,783 en rekke fast størrelse, fordi du bare kan 747 00:31:03,783 --> 00:31:08,302 passe så mange skuffer i at åpningen i veggen ned under folks knær. 748 00:31:08,302 --> 00:31:10,010 Og slik som kan være sies å være en matrise, 749 00:31:10,010 --> 00:31:14,300 men vi kunne sikkert implementere at mer generelt med en lenket liste. 750 00:31:14,300 --> 00:31:16,390 >> Vel, hva om en annen datastruktur? 751 00:31:16,390 --> 00:31:18,760 La meg trekke opp en annen visuell her. 752 00:31:18,760 --> 00:31:24,710 Noe sånt hva med denne her? 753 00:31:24,710 --> 00:31:28,920 Hvorfor kan det være nyttig å ha ikke noe så fancy som en trie, som 754 00:31:28,920 --> 00:31:32,370 vi så hadde disse svært brede noder, som hver er i en matrise? 755 00:31:32,370 --> 00:31:35,740 Men hva hvis vi gjør noe mer ganske enkelt, som en gammel skole familietre, 756 00:31:35,740 --> 00:31:38,110 hver av hvis noder her er bare lagrer et nummer. 757 00:31:38,110 --> 00:31:42,180 I stedet for et navn eller en etterkommer er bare lagrer et nummer som dette. 758 00:31:42,180 --> 00:31:45,250 >> Vel, sjargong vi bruker i datastrukturer er både tries 759 00:31:45,250 --> 00:31:49,510 og trær, der en trie, igjen, er bare en som noder er arrays, 760 00:31:49,510 --> 00:31:51,680 er fortsatt hva du kanskje bruke fra grunnskolen 761 00:31:51,680 --> 00:31:53,860 når du har gjort en familie tree-- blader og rot 762 00:31:53,860 --> 00:31:57,250 av treet og barn av foreldre og søsken av disse. 763 00:31:57,250 --> 00:32:03,670 Og vi kan gjennomføre et tre, for eksempel, som rett og slett som dette. 764 00:32:03,670 --> 00:32:07,420 Et tre, hvis det som en node, en av disse sirklene som har en rekke, 765 00:32:07,420 --> 00:32:09,947 det er ikke til å ha en peker, men to. 766 00:32:09,947 --> 00:32:11,780 Og så snart du legger til en andre peker, du 767 00:32:11,780 --> 00:32:13,905 faktisk kan nå gjøre liksom av to-dimensjonale data 768 00:32:13,905 --> 00:32:14,780 strukturer i minnet. 769 00:32:14,780 --> 00:32:16,660 Mye som en todimensjonal array, kan du 770 00:32:16,660 --> 00:32:18,904 har form av to-dimensjonale lenkede lister, men de 771 00:32:18,904 --> 00:32:20,820 som følger et mønster hvor det er ingen sykluser. 772 00:32:20,820 --> 00:32:24,487 Det er virkelig et tre med en forelder vei opp her og deretter 773 00:32:24,487 --> 00:32:27,320 noen foreldre og barn, og barnebarn og oldebarn. 774 00:32:27,320 --> 00:32:28,370 og så videre. 775 00:32:28,370 --> 00:32:32,390 >> Men hva er egentlig pen om dette også, bare for å erte deg med en bit av koden, 776 00:32:32,390 --> 00:32:35,370 tilbakekalling rekursjon fra en stund tilbake, der 777 00:32:35,370 --> 00:32:38,220 du skriver en funksjon som kaller seg. 778 00:32:38,220 --> 00:32:41,140 Dette er en vakker mulighet å gjennomføre noe 779 00:32:41,140 --> 00:32:42,920 som rekursjon, fordi vurdere dette. 780 00:32:42,920 --> 00:32:43,860 >> Dette er et tre. 781 00:32:43,860 --> 00:32:48,040 Og jeg har vært litt anal med hvordan Jeg satte heltall inn i gaten. 782 00:32:48,040 --> 00:32:51,020 Så mye at den har en spesiell name-- et binært søketre. 783 00:32:51,020 --> 00:32:53,460 Nå har vi hørt om binære søk, men kan du 784 00:32:53,460 --> 00:32:55,180 jobbe bakover fra denne tingen navn? 785 00:32:55,180 --> 00:32:59,280 Hva er mønsteret av hvordan jeg satt heltallene inn i dette treet? 786 00:32:59,280 --> 00:33:00,696 Det er ikke tilfeldig. 787 00:33:00,696 --> 00:33:01,570 Det er noen mønster. 788 00:33:01,570 --> 00:33:02,090 Yeah. 789 00:33:02,090 --> 00:33:03,370 >> PUBLIKUM: Small de på venstre. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Yeah. 791 00:33:03,690 --> 00:33:05,062 Mindre de er på venstre side. 792 00:33:05,062 --> 00:33:06,270 Større de er på rett. 793 00:33:06,270 --> 00:33:12,940 Slik at et sant utsagn er en forelder er større enn dens venstre barn, 794 00:33:12,940 --> 00:33:14,850 men mindre enn sin rett barnet. 795 00:33:14,850 --> 00:33:17,750 Og det alene er enda en rekursiv verbal definisjon 796 00:33:17,750 --> 00:33:20,500 fordi du kan bruke det samme logikken til hver node 797 00:33:20,500 --> 00:33:23,080 og det bare bunner ut, en base case hvis du 798 00:33:23,080 --> 00:33:25,740 vil, når du treffer en av bladene, så å si, 799 00:33:25,740 --> 00:33:28,580 der en permisjon har ingen barn lenger. 800 00:33:28,580 --> 00:33:30,614 >> Nå hvordan kan du finne nummeret 44? 801 00:33:30,614 --> 00:33:32,280 Du vil starte ved roten og si, hm. 802 00:33:32,280 --> 00:33:35,690 55 er ikke 44 Så gjør jeg ønsker å gå høyre eller ønsker jeg å gå til venstre? 803 00:33:35,690 --> 00:33:37,190 Vel, selvsagt ønsker å gå til venstre. 804 00:33:37,190 --> 00:33:40,060 Og så er det akkurat som telefonen Boken eksempel i binær søk 805 00:33:40,060 --> 00:33:41,099 mer generelt. 806 00:33:41,099 --> 00:33:43,390 Men vi implementere det nå litt mer dynamisk 807 00:33:43,390 --> 00:33:45,339 enn en matrise kan tillate. 808 00:33:45,339 --> 00:33:48,130 Og faktisk, hvis du ønsker å se på koden, ved første øyekast sikker. 809 00:33:48,130 --> 00:33:49,671 Det ser ut som en hel haug med linjer. 810 00:33:49,671 --> 00:33:51,220 Men det er vakkert enkel. 811 00:33:51,220 --> 00:33:54,490 Hvis du ønsker å implementere en funksjon kalles søk hvis formål i livet 812 00:33:54,490 --> 00:33:57,290 er å søke etter en verdi som n, er et heltall, 813 00:33:57,290 --> 00:34:01,756 og du er gått i ett pointer-- en peker til noden av røttene, 814 00:34:01,756 --> 00:34:04,380 heller, for det treet som du kan få tilgang til alt annet, 815 00:34:04,380 --> 00:34:08,850 merke til hvor oversiktlig du kan implementere logikken. 816 00:34:08,850 --> 00:34:10,880 Hvis treet er null, tydeligvis er det ikke der. 817 00:34:10,880 --> 00:34:11,880 La oss bare return false. 818 00:34:11,880 --> 00:34:12,000 Høyre? 819 00:34:12,000 --> 00:34:14,040 Hvis du leverer det ingenting, det er ingenting der. 820 00:34:14,040 --> 00:34:17,900 >> Annet, hvis n er mindre enn treet pil N- nå arrow n, 821 00:34:17,900 --> 00:34:20,670 husker vi introduserte super kort om dagen, 822 00:34:20,670 --> 00:34:25,100 og det betyr bare de-referanse pekeren og se på feltet kalt n. 823 00:34:25,100 --> 00:34:27,690 Så det betyr gå dit og se på feltet kalt n. 824 00:34:27,690 --> 00:34:33,810 Så hvis n, verdien du får, er mindre enn verdien i trær heltall, 825 00:34:33,810 --> 00:34:35,449 hvor ønsker du å reise? 826 00:34:35,449 --> 00:34:36,389 Til venstre. 827 00:34:36,389 --> 00:34:37,780 >> Så merker rekursjonen. 828 00:34:37,780 --> 00:34:39,860 Jeg returning-- ikke sant. 829 00:34:39,860 --> 00:34:40,989 Ikke falske. 830 00:34:40,989 --> 00:34:45,670 Jeg er tilbake uansett svaret er fra en samtale til meg selv, passerer 831 00:34:45,670 --> 00:34:50,100 en n på nytt, noe som er redundante, men hva er litt annerledes nå? 832 00:34:50,100 --> 00:34:51,989 Hvordan skal jeg gjøre problemet mindre? 833 00:34:51,989 --> 00:34:54,920 Jeg passerer som den andre argument, ikke roten av treet, 834 00:34:54,920 --> 00:34:59,616 men venstre barnet i dette tilfellet. 835 00:34:59,616 --> 00:35:00,990 Så jeg har bestått i venstre barnet. 836 00:35:00,990 --> 00:35:04,720 >> I mellomtiden, hvis n er større enn noden Jeg er for tiden å se på, 837 00:35:04,720 --> 00:35:06,690 Jeg søker på høyre side. 838 00:35:06,690 --> 00:35:10,880 Else, hvis treet er ikke null, og hvis elementet er ikke til venstre 839 00:35:10,880 --> 00:35:13,240 og det er ikke til høyre, hva er fantastisk tilfelle? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Vi har faktisk funnet node i spørsmålet, og så vi returnere true. 842 00:35:18,440 --> 00:35:21,490 >> Så vi har bare skrapet overflaten nå noen av disse datastrukturer. 843 00:35:21,490 --> 00:35:24,370 I oppgavesettet fem du vil utforske disse ennå videre, 844 00:35:24,370 --> 00:35:27,250 og du vil bli gitt design Valget av hvordan du går om dette. 845 00:35:27,250 --> 00:35:30,250 Det jeg ønsker å konkludere på er bare en 30 sekunders teaser 846 00:35:30,250 --> 00:35:32,080 av hva som venter i neste uke og utover. 847 00:35:32,080 --> 00:35:35,390 >> Som vi begin-- heldigvis du kanskje think-- vår overgang sakte 848 00:35:35,390 --> 00:35:38,680 fra verden av C og lavere nivå gjennomføring detaljer, 849 00:35:38,680 --> 00:35:42,090 til en verden der vi kan ta for gitt at noen andre har endelig 850 00:35:42,090 --> 00:35:44,010 implementert disse dataene strukturer for oss, 851 00:35:44,010 --> 00:35:47,570 og vi vil begynne å forstå virkelige verden betyr å implementere 852 00:35:47,570 --> 00:35:50,560 web-baserte programmer og nettsteder mer generelt 853 00:35:50,560 --> 00:35:52,910 og også selve sikkerhets implikasjoner som vi har bare 854 00:35:52,910 --> 00:35:54,850 begynt å skrape i overflaten av. 855 00:35:54,850 --> 00:35:57,320 Her er hva som venter oss i dagene som kommer. 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 >> -Han Kom med en melding, med en protokoll all sin egen. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Han kom til en verden av grusom brannmurer, uncaring rutere, 861 00:36:30,894 --> 00:36:33,368 og farer langt verre enn døden. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Han er rask. 864 00:36:36,236 --> 00:36:37,980 Han er sterk. 865 00:36:37,980 --> 00:36:42,830 Han er TCP / IP, og han fikk adressen. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors of the Net". 868 00:36:48,074 --> 00:36:49,660 [END VIDEO PLAYBACK] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: Kommer neste uke. 870 00:36:50,910 --> 00:36:51,880 Vi vil se deg da. 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 -Og Nå, "Deep Thoughts" av Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Starter alltid forelesninger med, "All right." 876 00:37:05,820 --> 00:37:08,750 Hvorfor ikke, "Her er løsningen til denne ukens problem set " 877 00:37:08,750 --> 00:37:12,180 eller "Vi gir dere alle en A?" 878 00:37:12,180 --> 00:37:13,380 [Ler] 879 00:37:13,380 --> 00:37:15,530 [END VIDEO PLAYBACK]