1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Přehrávání hudby] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: To je CS50. 5 00:00:14,010 --> 00:00:18,090 A to je jak začátek a end-- jako literally-- téměř do konce 6 00:00:18,090 --> 00:00:18,825 týdne šest. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Myslel jsem, že bych sdílet trochu zábavné skutečnosti. 9 00:00:22,640 --> 00:00:25,370 Jsem vytáhl to až z nastavit údaje minulého semestru. 10 00:00:25,370 --> 00:00:29,710 Možná si vzpomenete, že jsme se vás zeptat na každém p set formulář, pokud jste sledovali on-line 11 00:00:29,710 --> 00:00:31,580 nebo pokud jste se zúčastnili osobně. 12 00:00:31,580 --> 00:00:33,020 A tady je v datech. 13 00:00:33,020 --> 00:00:34,710 Takže dnes byl velmi předvídatelný. 14 00:00:34,710 --> 00:00:37,126 Ale my jsme chtěli strávit trochu času s vámi nicméně. 15 00:00:37,126 --> 00:00:40,599 Chtěl by někdo dohadu, proč se to graf je tak Jaggy, nahoru dolů, nahoru dolů, 16 00:00:40,599 --> 00:00:41,265 tak důsledně? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Co každý z vrcholů a žlaby představují? 19 00:00:45,130 --> 00:00:46,005 >> Diváků: [neslyšitelné] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: Opravdu. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 A více zábavně, nedej bože, máme jednu přednášku v pátek 24 00:00:55,480 --> 00:00:58,960 na začátku semestru, že to, co vidíme, se stalo. 25 00:00:58,960 --> 00:01:03,430 Takže dnes jsme se zapojit do trochu Další informace o datových strukturách. 26 00:01:03,430 --> 00:01:06,660 A dát vám více pevné látky mentální model pro problémy, které v pěti, 27 00:01:06,660 --> 00:01:07,450 který je nyní ven. 28 00:01:07,450 --> 00:01:10,817 Pravopisné chyby, kde budeme předat vám textový soubor někteří 100.000 29 00:01:10,817 --> 00:01:12,650 a anglická slova, a budete mít 30 00:01:12,650 --> 00:01:17,770 přijít na to, jak chytře je načíst do paměti, do paměti RAM, pomocí některé údaje 31 00:01:17,770 --> 00:01:19,330 Struktura vašeho výběru. 32 00:01:19,330 --> 00:01:22,470 >> Právě jedna taková datová struktura by mohla být, ale pravděpodobně by neměla být, 33 00:01:22,470 --> 00:01:25,630 poměrně zjednodušující spojový seznam, které jsme uvedli minule. 34 00:01:25,630 --> 00:01:29,220 A spojový seznam měl alespoň jedna výhoda oproti matici. 35 00:01:29,220 --> 00:01:32,096 Co je jedna z výhod spojový seznam pravděpodobně? 36 00:01:32,096 --> 00:01:32,950 >> Diváků: Vložení. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Vložení. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Co tím myslíš? 40 00:01:35,196 --> 00:01:37,872 >> Diváků: Anywhere spolu seznam [neslyšitelné]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Dobrý. 42 00:01:38,770 --> 00:01:42,090 Takže můžete vložit prvek, kdekoli Chcete uprostřed seznamu 43 00:01:42,090 --> 00:01:45,490 aniž by museli zamíchat cokoliv, které jsme uzavřeli v našem třídění 44 00:01:45,490 --> 00:01:47,630 diskuse, není nutně dobrá věc, 45 00:01:47,630 --> 00:01:51,200 protože to vyžaduje určitý čas, aby skutečně pohybovat všechny ty lidi vlevo nebo vpravo. 46 00:01:51,200 --> 00:01:55,540 A tak se spojový seznam, můžete jen přidělit s malloc, nový uzel, 47 00:01:55,540 --> 00:01:58,385 a pak aktualizovat pár pointers-- dva, tři operace max-- 48 00:01:58,385 --> 00:02:01,480 a jsme schopni slot někoho kdekoliv do seznamu. 49 00:02:01,480 --> 00:02:03,550 >> Co jiného bylo výhodné o propojeném seznamu? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Jo? 52 00:02:05,659 --> 00:02:06,534 >> Diváků: [neslyšitelné] 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 Je to opravdu dynamický. 58 00:02:12,070 --> 00:02:15,100 A že nejste spáchání, předem, do určité pevné velikosti 59 00:02:15,100 --> 00:02:18,750 kus paměti, jako byste mít se s pole, proinflační které 60 00:02:18,750 --> 00:02:22,455 je, že můžete přidělovat uzly pouze na poptávka a tím používat pouze tolik místa 61 00:02:22,455 --> 00:02:23,330 jak skutečně potřebujete. 62 00:02:23,330 --> 00:02:26,830 Na rozdíl od pole, můžete náhodně rozdělit příliš málo. 63 00:02:26,830 --> 00:02:28,871 A pak je to jen bude být bolest v krku 64 00:02:28,871 --> 00:02:32,440 přerozdělit nové větší pole, zkopírujte všechno skončí, uvolnit staré pole, 65 00:02:32,440 --> 00:02:33,990 a pak se přesunout o vaší firmě. 66 00:02:33,990 --> 00:02:37,479 Nebo ještě hůře, můžete přidělit cestu více paměti, než skutečně potřebujete, 67 00:02:37,479 --> 00:02:40,520 a tak budete mít velmi řídce osídlené pole, abych tak řekl. 68 00:02:40,520 --> 00:02:44,350 >> Takže spojový seznam vám tyto Výhody dynamiky a flexibility 69 00:02:44,350 --> 00:02:46,080 s inzercí a delecí. 70 00:02:46,080 --> 00:02:48,000 Ale určitě tam musí být zaplacená cena. 71 00:02:48,000 --> 00:02:50,000 Ve skutečnosti, jedním z témat prozkoumat testu nulové 72 00:02:50,000 --> 00:02:52,430 byl pár z kompromisů jsme viděli doposud. 73 00:02:52,430 --> 00:02:56,161 Takže to, co je cena, kterou zaplatil nebo Nevýhodou propojeného seznamu? 74 00:02:56,161 --> 00:02:56,660 Jo. 75 00:02:56,660 --> 00:02:57,560 >> Diváků: Ne náhodný přístup. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: No náhodný přístup. 77 00:02:58,809 --> 00:02:59,540 Ale koho to zajímá? 78 00:02:59,540 --> 00:03:01,546 Náhodný přístup nezní přesvědčivé. 79 00:03:01,546 --> 00:03:02,421 >> Diváků: [neslyšitelné] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Přesně tak. 82 00:03:05,740 --> 00:03:07,580 Chcete-li mít určité algorithm-- 83 00:03:07,580 --> 00:03:10,170 a dovolte mi, abych ve skutečnosti navrhnout binární vyhledávání, zejména, což 84 00:03:10,170 --> 00:03:12,600 je ta, kterou jsme použili docela bit-- pokud nemáte náhodný přístup, 85 00:03:12,600 --> 00:03:15,516 můžete to udělat jednoduchou aritmetiku nalezení jako prostřední prvek 86 00:03:15,516 --> 00:03:16,530 a skákání na něj právo. 87 00:03:16,530 --> 00:03:20,239 Místo toho budete muset začít v první element a lineárně vyhledávání zleva 88 00:03:20,239 --> 00:03:22,780 doprava, chcete-li najít střední nebo jakýkoli jiný prvek. 89 00:03:22,780 --> 00:03:24,410 >> Diváků: Asi potřebuje více paměti. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: bere více paměti. 91 00:03:25,040 --> 00:03:27,464 Kde je ten další náklady přicházející z paměti? 92 00:03:27,464 --> 00:03:28,339 >> Diváků: [neslyšitelné] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Přesně tak. 95 00:03:33,440 --> 00:03:35,679 V tomto případě je zde, měli jsme spojový seznam pro celá čísla, 96 00:03:35,679 --> 00:03:37,470 a přesto jsme zdvojnásobení množství paměti 97 00:03:37,470 --> 00:03:39,680 musíme tím, že také uložení těchto ukazatelů. 98 00:03:39,680 --> 00:03:42,090 Nyní méně velký problém, jak Vaše structs se zvětší 99 00:03:42,090 --> 00:03:45,320 a vy jste ukládání není číslo, ale Možná student nebo nějaký jiný předmět. 100 00:03:45,320 --> 00:03:46,880 Ale jde samozřejmě zůstává. 101 00:03:46,880 --> 00:03:49,421 A tak počet operací na spojových seznamů byli povoláni 102 00:03:49,421 --> 00:03:50,570 Byly velké-O n- lineární. 103 00:03:50,570 --> 00:03:54,730 Věci jako vložení nebo hledání nebo delece v případě, že prvek 104 00:03:54,730 --> 00:03:57,720 se stalo, že na samém konci Seznam ať už je to tříděného či nikoliv. 105 00:03:57,720 --> 00:04:01,167 >> Někdy můžete mít štěstí a takže spodní meze těchto operací 106 00:04:01,167 --> 00:04:04,250 může být také konstantní čas, pokud jste vždy při pohledu na první prvek, 107 00:04:04,250 --> 00:04:05,070 například. 108 00:04:05,070 --> 00:04:09,360 Ale nakonec jsme slíbili k dosažení svatý grál 109 00:04:09,360 --> 00:04:12,630 datových struktur, nebo některé aproximace této smlouvy, 110 00:04:12,630 --> 00:04:14,290 prostřednictvím konstantním čase. 111 00:04:14,290 --> 00:04:17,579 Můžeme najít prvky, nebo přidat prvky nebo odebrání prvků ze seznamu? 112 00:04:17,579 --> 00:04:19,059 Uvidíme již brzy. 113 00:04:19,059 --> 00:04:21,100 A ukázalo se, že jeden mechanismů jsme 114 00:04:21,100 --> 00:04:23,464 začnou používat dnes, roční spotřeba v p nastavit pět, 115 00:04:23,464 --> 00:04:24,630 je vlastně docela známé. 116 00:04:24,630 --> 00:04:27,430 Například, pokud je to banda zkoušky knih, z nichž každý 117 00:04:27,430 --> 00:04:29,660 má student je první Jméno a příjmení na tom, 118 00:04:29,660 --> 00:04:31,820 a já jsem vyzvednout z jejich na konci zkoušky, 119 00:04:31,820 --> 00:04:33,746 a všichni jsou dost hodně v náhodném pořadí, 120 00:04:33,746 --> 00:04:36,370 a chceme jít o třídění Tyto zkoušky tak, že jakmile se stupněm 121 00:04:36,370 --> 00:04:38,661 je to prostě mnohem jednodušší a rychleji předat je zpátky 122 00:04:38,661 --> 00:04:40,030 studentům abecedy. 123 00:04:40,030 --> 00:04:42,770 Co by vaše instinkty se na hromadu zkoušek, jako je tento? 124 00:04:42,770 --> 00:04:45,019 >> No, pokud jste jako já, může vidět, že se jedná m, 125 00:04:45,019 --> 00:04:48,505 tak budu nějak dát to do, pokud je to můj stůl nebo můj patra, kde 126 00:04:48,505 --> 00:04:50,650 Jsem šíří věci out-- nebo moje pole really-- 127 00:04:50,650 --> 00:04:52,210 Mohl bych dát všechny Ms tam. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Zde je A. Takže bych mohl dát jako tady. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Zde je další A. jdu dát to sem. 132 00:04:57,980 --> 00:05:02,490 Zde je Z. Zde je další M. A tak Mohl bych začít dělat piloty, jako je tento. 133 00:05:02,490 --> 00:05:06,620 A pak možná bych jít později a druh velmi nitpicky-ly sort 134 00:05:06,620 --> 00:05:07,710 jednotlivé piloty. 135 00:05:07,710 --> 00:05:11,300 Ale jde o to bych se na vstupu, že jsem rukou 136 00:05:11,300 --> 00:05:14,016 a já bych se některé vypočítá rozhodnutí založené na tomto vstupu. 137 00:05:14,016 --> 00:05:15,640 Pokud se začíná, dát to tam. 138 00:05:15,640 --> 00:05:18,980 Pokud se začne s Z, dal ji tam, a všechno mezi tím. 139 00:05:18,980 --> 00:05:22,730 >> Takže to je technika, která je všeobecně známé jako hashing-- H-A-S-H- 140 00:05:22,730 --> 00:05:26,550 což obecně znamená, že jako vstup a pomocí tohoto vstupu pro výpočet 141 00:05:26,550 --> 00:05:30,940 hodnotu, obvykle číslo, a že číslo je index do skladu 142 00:05:30,940 --> 00:05:32,260 Nádoba, jako pole. 143 00:05:32,260 --> 00:05:35,490 Takže jinými slovy, mohl bych mít hash funkce, jako já v mé hlavě, 144 00:05:35,490 --> 00:05:37,940 že když vidím někoho to Název, který začíná, 145 00:05:37,940 --> 00:05:40,190 Chystám se mapa, která na nulu v mé hlavě. 146 00:05:40,190 --> 00:05:44,160 A když vidím někoho s Z, jsem bude mapovat, že až 25 v mé hlavě 147 00:05:44,160 --> 00:05:46,220 a pak to dát do poslední nejvíce hromada. 148 00:05:46,220 --> 00:05:50,990 >> Teď, když se nad tím zamyslíte není můj mozek ale program v jazyce C, která čísla by mohla 149 00:05:50,990 --> 00:05:53,170 se spolehnout na dosažení tohoto stejného výsledku? 150 00:05:53,170 --> 00:05:55,594 Jinými slovy, pokud máte měl ASCII znak A, 151 00:05:55,594 --> 00:05:57,510 Jak zjistíte, co kbelík, aby to v? 152 00:05:57,510 --> 00:05:59,801 Pravděpodobně nebudete chtít dát do kbelíku 65, který 153 00:05:59,801 --> 00:06:01,840 by bylo jako tam bez dobrého důvodu. 154 00:06:01,840 --> 00:06:04,320 Kde chcete dát pokud jde o jeho ASCII hodnota? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Kam chceš udělat, aby jeho ASCII hodnota přijít s chytřejší kbelíku 157 00:06:08,920 --> 00:06:09,480 aby ji v? 158 00:06:09,480 --> 00:06:10,206 >> Diváků: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Jo. 160 00:06:10,956 --> 00:06:13,190 Takže minus nebo minus konkrétně 65, pokud je to 161 00:06:13,190 --> 00:06:18,240 kapitál A. Nebo 98, pokud je to malé. 162 00:06:18,240 --> 00:06:21,300 A tak, že by nám umožňují velmi jednoduše a velmi aritmeticky, 163 00:06:21,300 --> 00:06:23,260 dát něco do kbelíku takhle. 164 00:06:23,260 --> 00:06:26,010 Tak to dopadá, že jsme vlastně dělat to stejně is kvízy. 165 00:06:26,010 --> 00:06:29,051 >> Takže si možná pamatujete si kroužil vaše Název Výuka Kolegové se na obálce. 166 00:06:29,051 --> 00:06:32,270 A byly organizovány jména TF se do těchto sloupců podle abecedy, 167 00:06:32,270 --> 00:06:34,400 No, věřte tomu nebo ne, když všichni 80 a nás 168 00:06:34,400 --> 00:06:37,800 se dali dohromady v noci do platové třídy, poslední krok v našem procesu třídění, 169 00:06:37,800 --> 00:06:41,830 je hash kvízy do velké prostor podlahy na [neslyšitelné] 170 00:06:41,830 --> 00:06:45,110 a položit kvízy Každý by přesně pořadí jejich TF let 171 00:06:45,110 --> 00:06:47,700 jména na obálce, protože pak je to mnohem jednodušší pro nás 172 00:06:47,700 --> 00:06:51,290 prohledávat že pomocí lineární vyhledávání nebo nějaký chytrosti 173 00:06:51,290 --> 00:06:54,050 pro TF najít jeho nebo kvízy svých studentů. 174 00:06:54,050 --> 00:06:56,060 >> Takže tato myšlenka z hash které uvidíte, je 175 00:06:56,060 --> 00:07:00,520 docela silný je vlastně docela samozřejmostí a velmi intuitivní, 176 00:07:00,520 --> 00:07:03,000 podobně jako třeba rozdělit a dobytí bylo v týdnu nula. 177 00:07:03,000 --> 00:07:05,250 I rychle vpřed na Hackathon před pár lety. 178 00:07:05,250 --> 00:07:08,040 To byl Zamyla a pár Ostatní zaměstnanci pozdrav studenti 179 00:07:08,040 --> 00:07:09,030 jak přišli. 180 00:07:09,030 --> 00:07:12,680 A měli jsme spoustu skládání Stoly s jmenovkami. 181 00:07:12,680 --> 00:07:15,380 A my jsme měli jmenovky organizované se jako jak přes tu 182 00:07:15,380 --> 00:07:16,690 a Zs tam. 183 00:07:16,690 --> 00:07:20,350 A tak jedním z TFS velmi šikovně psal to jako návod 184 00:07:20,350 --> 00:07:21,030 na den. 185 00:07:21,030 --> 00:07:24,480 A v 12. týdnu semestru tohoto vše dávalo smysl a všechny 186 00:07:24,480 --> 00:07:25,310 věděl, co má dělat. 187 00:07:25,310 --> 00:07:27,900 Ale kdykoliv jsem frontě stejným způsobem, 188 00:07:27,900 --> 00:07:30,272 budete se provádí Stejný pojem hash. 189 00:07:30,272 --> 00:07:31,730 Takže pojďme formalizovat to trochu. 190 00:07:31,730 --> 00:07:32,890 Zde je pole. 191 00:07:32,890 --> 00:07:36,820 Je vypracován, aby se trochu široký jen líčit, vizuálně, 192 00:07:36,820 --> 00:07:38,920 že bychom mohli dát řetězce v něčem, jako je tohle. 193 00:07:38,920 --> 00:07:41,970 A toto pole je zjevně velikost 26 celkem. 194 00:07:41,970 --> 00:07:43,935 A věc se nazývá Tabulka libovolně. 195 00:07:43,935 --> 00:07:48,930 Ale to je jen umělce ztvárnění o tom, co by mohlo být hash tabulky. 196 00:07:48,930 --> 00:07:52,799 >> Takže hash tabulka nyní se chystá být vyšší strukturu dat na úrovni. 197 00:07:52,799 --> 00:07:54,840 Konec konců chystáme vidět, že vás 198 00:07:54,840 --> 00:07:58,700 mohou implementovat hash tabulku, která je podobně jako check-v souladu 199 00:07:58,700 --> 00:08:02,059 na Hackathon podobně jako tento Tabulka slouží k třídění zkoušku knih. 200 00:08:02,059 --> 00:08:03,850 Ale hash tabulka druh této vysoké úrovni 201 00:08:03,850 --> 00:08:08,250 koncept, který by mohl použít pole pod kryt k jeho provedení, 202 00:08:08,250 --> 00:08:11,890 nebo použít seznam délky, nebo dokonce možná některé další datové struktury. 203 00:08:11,890 --> 00:08:15,590 A teď to theme-- převzetí některé z těchto základních složek 204 00:08:15,590 --> 00:08:18,310 jako pole a budovy Blokovat nyní ze seznamu délky 205 00:08:18,310 --> 00:08:21,740 a vidět, co ještě můžeme stavět nad ty, jako přísady 206 00:08:21,740 --> 00:08:26,550 na recept, takže stále více a více zajímavé a užitečné konečné výsledky. 207 00:08:26,550 --> 00:08:28,680 >> Tak s hash tabulky můžeme ho zavést 208 00:08:28,680 --> 00:08:32,540 v paměti obrazově takhle, ale jak by to vlastně být kódovány up? 209 00:08:32,540 --> 00:08:33,789 No, možná, protože prostě je to. 210 00:08:33,789 --> 00:08:38,270 Pokud KAPACITA ve všech velkých písmenech, je jen někteří constant-- například 26, 211 00:08:38,270 --> 00:08:42,030 26 písmen alphabet-- Mohl bych zavolat své variabilní stůl, 212 00:08:42,030 --> 00:08:45,630 a mohl bych tvrdit, že budu dát char hvězdy tam, nebo řetězec. 213 00:08:45,630 --> 00:08:49,880 Takže je to tak jednoduché, jak to, pokud chtějí zavést hash tabulky. 214 00:08:49,880 --> 00:08:51,490 A přesto, je to opravdu jen pole. 215 00:08:51,490 --> 00:08:53,198 Ale opět, hash Tabulka je nyní, co budeme 216 00:08:53,198 --> 00:08:57,470 zavolejte abstraktní datový typ, který je stejně druh koncepčního vrstvení na vrcholu 217 00:08:57,470 --> 00:09:00,780 něco více světského Nyní mi pole. 218 00:09:00,780 --> 00:09:02,960 >> A teď, jak máme jít o řešení problémů? 219 00:09:02,960 --> 00:09:06,980 No, dříve jsem měl luxus mít dostatek tabulkový prostor zde 220 00:09:06,980 --> 00:09:09,460 tak, že bych mohl dát kvízy nikde jsem chtěl. 221 00:09:09,460 --> 00:09:10,620 Tak, aby mohla jít sem. 222 00:09:10,620 --> 00:09:12,100 Zs může jít sem. 223 00:09:12,100 --> 00:09:13,230 Paní může jít sem. 224 00:09:13,230 --> 00:09:14,740 A pak jsem měl nějaké extra prostor. 225 00:09:14,740 --> 00:09:18,740 Ale to je trochu cheat práva teď, protože této tabulce, jestli jsem opravdu 226 00:09:18,740 --> 00:09:22,720 myslel na to jako pole, je jen bude nějaké pevné velikosti. 227 00:09:22,720 --> 00:09:25,380 >> Takže technicky, když jsem vytáhnout do jiného studenta kvíz 228 00:09:25,380 --> 00:09:28,490 a vidět, oh, tato osoba je Název začíná příliš, 229 00:09:28,490 --> 00:09:30,980 Tak nějak jsem chtěl dát to tam. 230 00:09:30,980 --> 00:09:34,740 Ale jakmile jsem to tam dal, je-li tato tabulka skutečně představuje pole, 231 00:09:34,740 --> 00:09:37,840 Chystám se být převažující nebo přepisování kdo tento student kvíz je. 232 00:09:37,840 --> 00:09:38,340 Je to tak? 233 00:09:38,340 --> 00:09:41,972 Pokud se jedná o pole, jen jedna věc může jít v každé z těchto buněk nebo prvků. 234 00:09:41,972 --> 00:09:43,680 A tak nějak jsem se vybrat a zvolit. 235 00:09:43,680 --> 00:09:45,735 >> Teď dříve jsem tak trochu podváděl a dělal to nebo I 236 00:09:45,735 --> 00:09:47,526 jen tak na sebe je nad sebou. 237 00:09:47,526 --> 00:09:49,170 Ale to nebude létat v kódu. 238 00:09:49,170 --> 00:09:52,260 Tak, kde jsem mohl dát Druhý student, jehož jméno 239 00:09:52,260 --> 00:09:54,964 Je-li vše, co jsem měl, je to k dispozici tabulkový prostor? 240 00:09:54,964 --> 00:09:57,880 A já jsem použil tři sloty a to vypadá to, že je to jen několik dalších. 241 00:09:57,880 --> 00:09:58,959 Co jsi to mohl udělat? 242 00:09:58,959 --> 00:09:59,834 Diváků: [neslyšitelné] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Jo. 245 00:10:01,315 --> 00:10:02,370 Možná, řekněme, aby to jednoduché. 246 00:10:02,370 --> 00:10:02,660 Je to tak? 247 00:10:02,660 --> 00:10:04,243 To se nehodí tam, kde chci, aby to. 248 00:10:04,243 --> 00:10:07,450 Takže jdu dát technicky kde by B jít. 249 00:10:07,450 --> 00:10:09,932 Teď, samozřejmě, já začínám malovat sám sebe do kouta. 250 00:10:09,932 --> 00:10:11,890 Pokud se dostanu na studenta jehož jméno je vlastně B, 251 00:10:11,890 --> 00:10:14,840 Nyní B bude pohybovat trochu dopředu, jak by se mohlo stát, jo, 252 00:10:14,840 --> 00:10:17,530 pokud je to B, teď to musí jít sem. 253 00:10:17,530 --> 00:10:20,180 >> A tak se velmi rychle by se mohlo stát problematickým, 254 00:10:20,180 --> 00:10:23,850 ale je to technika, která ve skutečnosti je označován jako lineární snímání, 255 00:10:23,850 --> 00:10:26,650 kdy stačí zvážit své pole, že podél čáry. 256 00:10:26,650 --> 00:10:29,680 A právě typ čidla, nebo zkontrolujte každou dostupné prvek 257 00:10:29,680 --> 00:10:31,360 hledá k dispozici na místě. 258 00:10:31,360 --> 00:10:34,010 A jakmile zjistíte, jedno, co si jen kapka tam. 259 00:10:34,010 --> 00:10:38,390 >> Nyní je cena v dnešní době věnováno pro toto řešení je to, co? 260 00:10:38,390 --> 00:10:41,300 Máme pevnou velikost pole, a při vložení jména 261 00:10:41,300 --> 00:10:44,059 do něj, alespoň zpočátku, co je doba chodu vložení 262 00:10:44,059 --> 00:10:46,350 pro uvedení studentů " kvízy na správných kbelíky? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O co? 265 00:10:50,002 --> 00:10:51,147 >> Diváků: n. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: Slyšel jsem, že velký O n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 To není pravda. 269 00:10:54,300 --> 00:10:56,490 Ale budeme dráždit sebe proč za chvíli. 270 00:10:56,490 --> 00:10:57,702 Co jiného by to mohlo být? 271 00:10:57,702 --> 00:10:58,755 >> Diváků: [neslyšitelné] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: A dovolte mi, abych to vizuálně. 273 00:11:00,380 --> 00:11:04,720 Takže předpokládám, že je to písmeno S. 274 00:11:04,720 --> 00:11:05,604 >> Diváků: Je to jedna. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: Je to jedno. 276 00:11:06,520 --> 00:11:06,710 Je to tak? 277 00:11:06,710 --> 00:11:08,950 To je pole, které znamená, že máme náhodný přístup. 278 00:11:08,950 --> 00:11:11,790 A pokud si myslíme, že to na nulu a to až 25, 279 00:11:11,790 --> 00:11:13,800 a my jsme si uvědomili, že, oh, tady je můj vstup S, 280 00:11:13,800 --> 00:11:16,350 Já určitě převést S, znak ASCII, 281 00:11:16,350 --> 00:11:18,540 do odpovídajícího počtu mezi nulou a 25 282 00:11:18,540 --> 00:11:20,910 a pak se okamžitě dát tam, kam patří. 283 00:11:20,910 --> 00:11:26,120 >> Ale samozřejmě, jakmile se dostanu do Druhá osoba, která se jmenuje A nebo B nebo C 284 00:11:26,120 --> 00:11:29,300 nakonec, pokud jsem použil lineární snímání jak mé řešení, 285 00:11:29,300 --> 00:11:31,360 Doba chodu vložení v nejhorším případě 286 00:11:31,360 --> 00:11:33,120 bude skutečně přenést do čeho? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 A já jsem slyšel zde správně brzy. 289 00:11:36,045 --> 00:11:36,920 Diváků: [neslyšitelné] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Tak to je opravdu n jednou máte dostatečně velký soubor dat. 291 00:11:41,620 --> 00:11:44,410 Tak, na jedné straně, pokud vaše pole je dostatečně velký 292 00:11:44,410 --> 00:11:48,287 a vaše data je řídké dost, vy si tento krásný konstantní čas. 293 00:11:48,287 --> 00:11:50,620 Ale jakmile začnete stále více a více prvků, 294 00:11:50,620 --> 00:11:53,200 a jen statisticky dostanete více lidí s písmenem 295 00:11:53,200 --> 00:11:56,030 Jak jejich jméno nebo písmeno B, mohlo by to potenciálně 296 00:11:56,030 --> 00:11:57,900 přejít na něco více lineární. 297 00:11:57,900 --> 00:11:59,640 Takže není úplně dokonalá. 298 00:11:59,640 --> 00:12:00,690 Tak bychom mohli dělat lépe? 299 00:12:00,690 --> 00:12:03,210 >> No, co bylo naše řešení, než když jsme se 300 00:12:03,210 --> 00:12:06,820 Chcete mít větší dynamiku než něco jako pole dovoleno? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 Diváků: [neslyšitelné] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Co jsme představit? 304 00:12:10,030 --> 00:12:10,530 Jo. 305 00:12:10,530 --> 00:12:11,430 Takže spojový seznam. 306 00:12:11,430 --> 00:12:14,430 No, uvidíme, co souvisí Seznam může udělat pro nás místo. 307 00:12:14,430 --> 00:12:17,630 No, dovolte mi, abych navrhuji, abychom nakreslit obrázek takto. 308 00:12:17,630 --> 00:12:19,620 Nyní je to jiná obrázek z příkladu 309 00:12:19,620 --> 00:12:24,750 z jiného textu, ve skutečnosti, že je ve skutečnosti pomocí pole o velikosti 31. 310 00:12:24,750 --> 00:12:28,220 A to autor prostě rozhodl hash řetězce 311 00:12:28,220 --> 00:12:32,430 nejsou založeny na jména této osoby, ale na základě jejich narozeniny. 312 00:12:32,430 --> 00:12:35,680 Bez ohledu na měsíce, ale přišel pokud jste se narodil na první měsíc 313 00:12:35,680 --> 00:12:39,580 nebo 31. v měsíci, autor hash bude na základě této hodnoty, 314 00:12:39,580 --> 00:12:44,154 tak, aby se rozšířila jména se trochu více než jen 26 míst, by mohly umožnit. 315 00:12:44,154 --> 00:12:47,320 A možná je to trochu jednotnější než jít s písmeny abecedy, 316 00:12:47,320 --> 00:12:50,236 protože samozřejmě je to asi více lidí na celém světě se jmény 317 00:12:50,236 --> 00:12:54,020 které začínají než jistě některé další písmena abecedy. 318 00:12:54,020 --> 00:12:56,380 Takže možná je to trochu jednotnější, za předpokladu, že 319 00:12:56,380 --> 00:12:58,640 rovnoměrné rozložení kojenců po celé měsíce. 320 00:12:58,640 --> 00:12:59,990 >> Ale, samozřejmě, je to stále nedokonalé. 321 00:12:59,990 --> 00:13:00,370 Je to tak? 322 00:13:00,370 --> 00:13:01,370 Budeme mít kolize. 323 00:13:01,370 --> 00:13:04,680 Více lidí v této datové struktury jsou stále 324 00:13:04,680 --> 00:13:08,432 mají stejný datum narození nejméně jste bez ohledu na měsíc. 325 00:13:08,432 --> 00:13:09,640 Ale co se autor udělal? 326 00:13:09,640 --> 00:13:13,427 No, vypadá to, že máme celou řadu na levé straně tažené vertikálně, 327 00:13:13,427 --> 00:13:15,010 ale to je jen umělce ztvárnění. 328 00:13:15,010 --> 00:13:18,009 Nezáleží na tom, jakým směrem se vás čerpat řadu, je to ještě pole. 329 00:13:18,009 --> 00:13:20,225 Co je to pole zdánlivě? 330 00:13:20,225 --> 00:13:21,500 >> Diváků: spojový seznam. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Jo. 332 00:13:21,650 --> 00:13:23,490 Vypadá to, jako by to pole propojeného seznamu. 333 00:13:23,490 --> 00:13:26,490 Takže znovu, do tohoto bodu druhu použití těchto datových struktur nyní 334 00:13:26,490 --> 00:13:28,550 jako přísady do více zajímavé řešení, 335 00:13:28,550 --> 00:13:30,862 můžete mít naprosto Základní, stejně jako pole, 336 00:13:30,862 --> 00:13:33,320 a pak něco víc zajímavé jako spojový seznam 337 00:13:33,320 --> 00:13:36,660 a dokonce spojit je do ještě zajímavější datové struktury. 338 00:13:36,660 --> 00:13:39,630 A skutečně, taky by to se nazývá hash tabulky, 339 00:13:39,630 --> 00:13:42,610 přičemž pole je opravdu hash tabulka, 340 00:13:42,610 --> 00:13:45,600 ale to hash tabulka řetězy, abych tak řekl, 341 00:13:45,600 --> 00:13:50,220 že může růst nebo zmenšit na základě počet prvků, který chcete vložit. 342 00:13:50,220 --> 00:13:52,990 >> Nyní tedy, co je doba chodu teď? 343 00:13:52,990 --> 00:13:58,030 Pokud chci vložit někoho jehož narozeniny 31. října, 344 00:13:58,030 --> 00:13:59,040 kde se on nebo ona jít? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Dobrá. 347 00:14:01,030 --> 00:14:02,819 Na samém dně, kde se říká, že 31. 348 00:14:02,819 --> 00:14:03,610 A to je perfektní. 349 00:14:03,610 --> 00:14:05,060 To bylo konstantní čas. 350 00:14:05,060 --> 00:14:08,760 Ale co když najdeme někoho jiného jehož narozeniny, pojďme se podívat, 351 00:14:08,760 --> 00:14:10,950 Říjen, listopad k 31? 352 00:14:10,950 --> 00:14:12,790 Pokud se on nebo ona jít? 353 00:14:12,790 --> 00:14:13,290 Totéž. 354 00:14:13,290 --> 00:14:13,970 Dvoustupňová ačkoli. 355 00:14:13,970 --> 00:14:15,303 To je konstantní i když je to tak? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Dobrá. 358 00:14:16,860 --> 00:14:17,840 V současné době to je. 359 00:14:17,840 --> 00:14:20,570 Ale v obecném případě, čím více lidí přidáme, 360 00:14:20,570 --> 00:14:23,790 pravděpodobnostně, jdeme aby se více a více ke kolizím. 361 00:14:23,790 --> 00:14:26,820 >> Teď je to trochu lepší, protože technicky 362 00:14:26,820 --> 00:14:34,580 teď moje řetězy mohou být v v nejhorším případě, jak dlouho? 363 00:14:34,580 --> 00:14:38,890 Mám-li vložit n lidi do toho více sofistikované datové struktury, n lidí, 364 00:14:38,890 --> 00:14:41,080 V nejhorším případě to bude n. 365 00:14:41,080 --> 00:14:41,815 Proč? 366 00:14:41,815 --> 00:14:43,332 >> Diváků: Protože kdyby každý má narozeniny ve stejný den, 367 00:14:43,332 --> 00:14:44,545 že budeš jeden řádek. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Perfect. 369 00:14:45,420 --> 00:14:47,480 To by mohlo být trochu nepřirozený, ale skutečně v nejhorším případě, 370 00:14:47,480 --> 00:14:50,117 pokud každý má narozeniny ve stejný den, s ohledem na vstupy máte, 371 00:14:50,117 --> 00:14:51,950 budete mít masivně dlouhým řetězcem. 372 00:14:51,950 --> 00:14:54,241 A ano, můžete ho hovoru hash tabulky, ale ve skutečnosti je to 373 00:14:54,241 --> 00:14:56,810 jen masivní spojový seznam s spousta nevyužitého místa. 374 00:14:56,810 --> 00:15:00,460 Ale obecně, pokud budeme předpokládat, že alespoň narozeniny jsou uniform-- 375 00:15:00,460 --> 00:15:01,750 a to asi není. 376 00:15:01,750 --> 00:15:02,587 Dělám, že až. 377 00:15:02,587 --> 00:15:04,420 Ale pokud budeme předpokládat, pro Z důvodu diskuse 378 00:15:04,420 --> 00:15:07,717 že jsou, pak teoreticky, pokud To je vertikální reprezentace 379 00:15:07,717 --> 00:15:11,050 matice, no a pak doufejme, že jste dostane řetězců, které jsou, jak víte, 380 00:15:11,050 --> 00:15:15,880 zhruba stejnou délku, kde každý z to představuje den v měsíci. 381 00:15:15,880 --> 00:15:19,930 >> Nyní, když je tam 31 dnů v měsíci, to znamená, že moje doba chodu opravdu 382 00:15:19,930 --> 00:15:25,230 je velký O n více než 31, což cítí lépe než lineární. 383 00:15:25,230 --> 00:15:27,950 Ale to, co byl jeden z našich Závazky pár týdnů 384 00:15:27,950 --> 00:15:31,145 Před když to přišlo k vyjadřování doba chodu algoritmu? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Stačí jen podívat na vysokou objednávky termínu. 387 00:15:35,190 --> 00:15:35,690 Je to tak? 388 00:15:35,690 --> 00:15:37,400 31 je určitě užitečné. 389 00:15:37,400 --> 00:15:39,610 Ale je to stále velký O n. 390 00:15:39,610 --> 00:15:41,730 Ale jedním z témat o problém nastavit pět 391 00:15:41,730 --> 00:15:43,950 bude na na vědomí, že absolutně, 392 00:15:43,950 --> 00:15:47,320 asymptoticky, teoreticky Tato datová struktura 393 00:15:47,320 --> 00:15:50,470 není o nic lepší, než jen jeden masivní spojový seznam. 394 00:15:50,470 --> 00:15:53,550 A skutečně, v nejhorším případě to hash tabulka může přejít do toho. 395 00:15:53,550 --> 00:15:57,620 >> Ale v reálném světě, s námi lidé že vlastní Macintoshe nebo PC, nebo cokoliv 396 00:15:57,620 --> 00:16:01,240 a běží v reálném světě software z reálných dat, 397 00:16:01,240 --> 00:16:03,260 které algoritmus budete preferovat? 398 00:16:03,260 --> 00:16:09,180 Ten, který má koncové kroky nebo ten, který trvá n děleno 31 stupňů 399 00:16:09,180 --> 00:16:12,900 najít nějakou část dat nebo vyhledat nějaké informace? 400 00:16:12,900 --> 00:16:16,580 Myslím, že absolutně 31 značek rozdíl v reálném světě. 401 00:16:16,580 --> 00:16:18,540 To je 31 krát rychlejší. 402 00:16:18,540 --> 00:16:20,880 A my lidé jsou jistě jít si uvědomit, že. 403 00:16:20,880 --> 00:16:23,004 >> Takže si uvědomit rozpor tam mezi skutečně 404 00:16:23,004 --> 00:16:25,920 mluví o tom, co teoreticky a asymptoticky, které rozhodně 405 00:16:25,920 --> 00:16:28,760 má hodnotu, jak jsme viděli, ale v reálném světě, 406 00:16:28,760 --> 00:16:32,930 pokud vám záleží jen dělat člověk šťastný pro obecné vstupy, 407 00:16:32,930 --> 00:16:36,010 můžete velmi dobře chcete přijmout skutečnost, že ano, je to lineární, 408 00:16:36,010 --> 00:16:38,360 ale to je 31 krát rychlejší než může být lineární. 409 00:16:38,360 --> 00:16:41,610 A ještě lépe, nebudeme muset něco libovolného jako datum narození, 410 00:16:41,610 --> 00:16:44,030 bychom mohli strávit trochu více času a chytrost 411 00:16:44,030 --> 00:16:47,140 a přemýšlet o tom, co bychom mohli udělat, křestní jméno člověka, a možná 412 00:16:47,140 --> 00:16:50,130 Jejich datum narození kombinovat ty, složky na něco vymyslíme 413 00:16:50,130 --> 00:16:52,720 je to opravdu více jednotná a méně Jaggy, 414 00:16:52,720 --> 00:16:56,250 abych tak řekl, než tento obrázek V současné době naznačuje, že by mohlo být. 415 00:16:56,250 --> 00:16:57,750 Jak bychom mohli realizovat to v kódu? 416 00:16:57,750 --> 00:17:00,280 No, dovolte mi, abych navrhuji, abychom jen půjčit nějaké syntaxi jsme 417 00:17:00,280 --> 00:17:01,799 použitý párkrát tak daleko. 418 00:17:01,799 --> 00:17:03,590 A já budu definovat uzel, který opět 419 00:17:03,590 --> 00:17:06,812 je obecný termín pro jen některé Kontejner pro některé datové struktury. 420 00:17:06,812 --> 00:17:09,020 Chystám se navrhnout, aby řetězec se děje tam. 421 00:17:09,020 --> 00:17:11,369 Ale budeme začnete těch koleček off teď. 422 00:17:11,369 --> 00:17:13,230 >> Žádné další CS50 knihovna Opravdu, pokud budete chtít 423 00:17:13,230 --> 00:17:15,230 jej použít pro finále Projekt, který je v pořádku, 424 00:17:15,230 --> 00:17:18,569 ale teď budeme táhnout zpět záclony a říkají, že je to jen znak hvězda. 425 00:17:18,569 --> 00:17:22,069 Takže slovo se bude jméno osoby v otázce. 426 00:17:22,069 --> 00:17:25,079 A teď mám odkaz zde k dalšímu uzlu 427 00:17:25,079 --> 00:17:28,170 tak, že tyto představují Každý z uzlů 428 00:17:28,170 --> 00:17:30,950 v řetězci, případně, propojeného seznamu. 429 00:17:30,950 --> 00:17:34,090 >> A teď jak se Prohlašuji hash tabulka sám? 430 00:17:34,090 --> 00:17:36,660 Jak mohu prohlásit celou tuto strukturu? 431 00:17:36,660 --> 00:17:40,960 No, opravdu, stejně jako jsem použila ukazatel se pouze první prvek seznamu 432 00:17:40,960 --> 00:17:44,510 předtím, podobně mohu jen říci, Prostě potřebuju spoustu ukazatelů 433 00:17:44,510 --> 00:17:46,270 realizovat celý tento hash tabulky. 434 00:17:46,270 --> 00:17:49,484 Budu mít celou řadu volal tabulka hash tabulky. 435 00:17:49,484 --> 00:17:50,900 Bude to mít velikost kapacity. 436 00:17:50,900 --> 00:17:52,525 To je to, kolik prvků se vejde do něj. 437 00:17:52,525 --> 00:17:56,180 A každý z těchto prvků v tomto pole bude uzel hvězda. 438 00:17:56,180 --> 00:17:56,810 Proč? 439 00:17:56,810 --> 00:18:00,160 No, na obrázku je to, co jsem provádění hash tabulku jako 440 00:18:00,160 --> 00:18:04,330 účinně na začátku je jen Toto pole, které jsme vypracován ve svislém směru, 441 00:18:04,330 --> 00:18:06,820 každý z jehož náměstí představuje ukazatel. 442 00:18:06,820 --> 00:18:09,170 Že ty, které mají lomítka mezi nimi jsou jen null. 443 00:18:09,170 --> 00:18:11,410 A ty, které mají šipky jdou doprava 444 00:18:11,410 --> 00:18:16,140 jsou skutečné ukazatele na skutečných uzlů, ergo začátek spojového seznamu. 445 00:18:16,140 --> 00:18:19,050 >> Tak tady tedy je, jak bychom mohli realizovat hash tabulku, která 446 00:18:19,050 --> 00:18:21,580 implementuje samostatný řetězení. 447 00:18:21,580 --> 00:18:22,840 Nyní můžeme dělat lépe? 448 00:18:22,840 --> 00:18:25,632 V pořádku jsem slíbil minule, že bychom mohli dosáhnout konstantní čas. 449 00:18:25,632 --> 00:18:27,381 A nějak jsem ti dal konstantní čas tady, 450 00:18:27,381 --> 00:18:29,850 ale pak řekl, že opravdu konstantní čas, protože je to stále 451 00:18:29,850 --> 00:18:31,890 v závislosti na celkové počet prvků 452 00:18:31,890 --> 00:18:34,500 jste vklad do datová struktura. 453 00:18:34,500 --> 00:18:35,980 Ale předpokládejme, že jsme to udělali. 454 00:18:35,980 --> 00:18:39,550 Dovolte mi, abych se vrátit na obrazovku sem. 455 00:18:39,550 --> 00:18:44,520 Dovolte mi, abych také promítat to tady, jasné, obrazovky, a předpokládám, že jsem to udělal. 456 00:18:44,520 --> 00:18:49,300 Dejme tomu, že jsem chtěl vložit jméno Daven v do mé datové struktury. 457 00:18:49,300 --> 00:18:52,100 >> Tak jsem chtěl vložit řetězec Daven do datové struktury. 458 00:18:52,100 --> 00:18:54,370 Co když nemám používat hash tabulky, ale já používám 459 00:18:54,370 --> 00:18:56,980 něco, co je víc stromová jako rodokmen, kde 460 00:18:56,980 --> 00:18:59,670 máte nějaké kořeny na Horní a pak uzly a listy 461 00:18:59,670 --> 00:19:01,440 které jdou dolů a ven. 462 00:19:01,440 --> 00:19:04,450 Předpokládejme tedy, že já chcete vložit Daven je 463 00:19:04,450 --> 00:19:06,430 na to, co je v současné době prázdný seznam. 464 00:19:06,430 --> 00:19:09,780 Chystám se provést následující kroky: Já jsem bude vytvářet uzel v této rodině 465 00:19:09,780 --> 00:19:15,170 stromová datová struktura, která vypadá trochu jako je tento, z nichž každý 466 00:19:15,170 --> 00:19:19,640 obdélníky se, řekněme, Pro tuto chvíli 26 prvků v něm. 467 00:19:19,640 --> 00:19:21,650 A každý z buněk V tomto poli se děje 468 00:19:21,650 --> 00:19:23,470 reprezentovat písmeno abecedy. 469 00:19:23,470 --> 00:19:28,190 >> Konkrétně se budu léčit to je, pak B, pak C, pak D, 470 00:19:28,190 --> 00:19:29,310 tohle tady. 471 00:19:29,310 --> 00:19:32,940 Takže to bude účinně představují písmeno D. 472 00:19:32,940 --> 00:19:36,040 Ale vložit všechny Daven je jméno musím udělat trochu víc. 473 00:19:36,040 --> 00:19:37,840 Takže jsem poprvé bude hash, abych tak řekl. 474 00:19:37,840 --> 00:19:41,049 Jdu se podívat na první písmeno v Daven je, což je zřejmě D, 475 00:19:41,049 --> 00:19:42,840 a budu přidělit uzel, který vypadá 476 00:19:42,840 --> 00:19:45,570 jako tohle-- velký obdélník velký tak, aby se vešly na celou abecedu. 477 00:19:45,570 --> 00:19:47,140 >> Nyní D je hotovo. 478 00:19:47,140 --> 00:19:49,720 Nyní A. D-A-E-V-N je cíl. 479 00:19:49,720 --> 00:19:51,220 Takže co teď budu dělat, je to. 480 00:19:51,220 --> 00:19:54,027 Jakmile jsem začal D oznámení Je tam žádný ukazatel. 481 00:19:54,027 --> 00:19:56,860 Je to nesmyslné hodnoty v okamžiku, nebo bych mohl inicializovat na hodnotu null. 482 00:19:56,860 --> 00:19:59,630 Ale dovolte mi, abych dál s Tato myšlenka vybudování stromu. 483 00:19:59,630 --> 00:20:04,260 Dovolte mi, abych přidělit další z nich uzly, které má 26 prvků v ní. 484 00:20:04,260 --> 00:20:05,150 >> A víte co? 485 00:20:05,150 --> 00:20:09,130 Pokud je to jen uzel v paměti, že Vytvořil jsem s malloc pomocí struct 486 00:20:09,130 --> 00:20:11,240 jak brzy uvidíte, Chystám se dělat tohle-- 487 00:20:11,240 --> 00:20:14,450 Budu čerpat šipku z to, co reprezentoval D dolů 488 00:20:14,450 --> 00:20:15,860 do tohoto nového uzlu. 489 00:20:15,860 --> 00:20:19,240 A nyní, nejprve další písmeno Daven jménem, 490 00:20:19,240 --> 00:20:24,150 V- D-A-V- Chystám se jít dopředu a čerpat další uzel takhle, 491 00:20:24,150 --> 00:20:30,150 přičemž jsou zde prvky V, které budeme čerpat pro instance-- Ups. 492 00:20:30,150 --> 00:20:31,020 Nebudeme tam kreslit. 493 00:20:31,020 --> 00:20:31,936 Bude to naleznete zde. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Pak jedeme do Považujeme to za V. 496 00:20:35,712 --> 00:20:44,920 A pak tady budeme indexu dolů z V na to, co budeme považovat E. 497 00:20:44,920 --> 00:20:50,100 A pak zde budeme jít jeden z těchto uzlů zde. 498 00:20:50,100 --> 00:20:52,930 A teď tu máme otázku odpovědět. 499 00:20:52,930 --> 00:20:57,840 Musím nějak vyplývá, že jsme na konci řetězce Daven. 500 00:20:57,840 --> 00:20:59,490 Takže jsem mohl jen nechat null. 501 00:20:59,490 --> 00:21:02,670 >> Ale co když máme Daven je celé jméno také, což 502 00:21:02,670 --> 00:21:04,280 je, jak jsme řekli, Davenport? 503 00:21:04,280 --> 00:21:06,970 Takže co když je Daven vlastně podřetězec, 504 00:21:06,970 --> 00:21:08,960 prefix mnohem delší řetězec? 505 00:21:08,960 --> 00:21:11,450 Nemůžeme jen trvale říkají, nic se děje 506 00:21:11,450 --> 00:21:14,410 tam jít, protože jsme mohli Nikdy nevkládejte slovo jako Davenport 507 00:21:14,410 --> 00:21:15,840 do této datové struktury 508 00:21:15,840 --> 00:21:19,560 >> Takže to, co bychom mohli udělat, místo toho je zacházet s každým z těchto prvků 509 00:21:19,560 --> 00:21:22,170 jako možná mít dva prvky uvnitř nich. 510 00:21:22,170 --> 00:21:24,810 Jedním z nich je ukazatel, opravdu, jak jsem dělal. 511 00:21:24,810 --> 00:21:27,100 Takže každá z těchto krabic není jen jedna buňka. 512 00:21:27,100 --> 00:21:29,855 Ale co v případě, že horní one-- spodní něčí 513 00:21:29,855 --> 00:21:32,230 bude nulový, protože není Davenport ještě ne. 514 00:21:32,230 --> 00:21:34,197 Co v případě, že jeden vrchol je nějaký zvláštní hodnota? 515 00:21:34,197 --> 00:21:36,530 A to bude trochu obtížné stanovit, že tato velikost. 516 00:21:36,530 --> 00:21:38,130 Ale předpokládám, že je to jen značka zaškrtnutí. 517 00:21:38,130 --> 00:21:38,920 Podívejte se. 518 00:21:38,920 --> 00:21:44,230 D-E-V-N-je řetězec V této datové struktury. 519 00:21:44,230 --> 00:21:48,350 >> Mezitím, kdybych měl více prostoru tady jsem mohl dělat P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 a já jsem mohl dát šek v uzlu který má na písmeno T na samém konci. 521 00:21:52,650 --> 00:21:55,460 Tak tohle je masivně komplexní vypadající strukturu dat. 522 00:21:55,460 --> 00:21:57,210 A můj rukopis rozhodně nepomůže. 523 00:21:57,210 --> 00:22:00,043 Ale když jsem chtěl vložit něco jiný, zvažte, co budeme dělat. 524 00:22:00,043 --> 00:22:03,370 Pokud bychom chtěli, aby Davida, bychom následovat stejnou logiku, D-A-V, 525 00:22:03,370 --> 00:22:08,802 ale teď bych upozornit na další prvek, který z E, ale od I do D. 526 00:22:08,802 --> 00:22:10,760 Takže tam to bude více uzly tohoto stromu. 527 00:22:10,760 --> 00:22:12,325 Budeme mít volání malloc více. 528 00:22:12,325 --> 00:22:14,700 Ale já nechci, aby se naprostý zmatek obrázku. 529 00:22:14,700 --> 00:22:17,710 Takže pojďme se podívat na místo jednoho která byla předem formulována 530 00:22:17,710 --> 00:22:21,810 takhle se není tečka, tečka, tečky, ale jen zkráceně pole. 531 00:22:21,810 --> 00:22:23,950 Avšak každý z uzlů v tomto zde stromu nahoru 532 00:22:23,950 --> 00:22:26,700 představuje stejný thing-- pole Ray velikosti 26. 533 00:22:26,700 --> 00:22:28,860 >> Nebo chceme-li být opravdu správné teď, co 534 00:22:28,860 --> 00:22:30,790 pokud někdo název, apostrof, pojďme 535 00:22:30,790 --> 00:22:35,560 Předpokládejme, že každý uzel má ve skutečnosti jako 27 indexy v něm, ne jen 26 let. 536 00:22:35,560 --> 00:22:42,020 Tak to teď bude dat Struktura nazývá trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 Trie, která je údajně historicky chytrý název pro dřevo 538 00:22:46,120 --> 00:22:49,040 , který je optimalizován pro vyhledávání, což samozřejmě, 539 00:22:49,040 --> 00:22:50,870 se píše s I-E, takže je to trie. 540 00:22:50,870 --> 00:22:52,710 Ale to je historie trie. 541 00:22:52,710 --> 00:22:55,860 >> Takže trie je to stromová údaje struktura jako rodinný strom 542 00:22:55,860 --> 00:22:57,510 že nakonec se chová takhle. 543 00:22:57,510 --> 00:23:00,890 A tady je jen dalším příkladem toho, celá parta jmen jiných lidí. 544 00:23:00,890 --> 00:23:03,540 Ale otázka nyní na dosah ruky je to, co mají 545 00:23:03,540 --> 00:23:08,070 jsme získali zavedením pravděpodobně více složitá struktura dat, a jeden, 546 00:23:08,070 --> 00:23:09,870 upřímně, že používá hodně paměti. 547 00:23:09,870 --> 00:23:11,703 >> Vzhledem k tomu, i když, v tuto chvíli, já jsem jen 548 00:23:11,703 --> 00:23:15,050 pomocí D je ukazatel a A V a Es a Ns, 549 00:23:15,050 --> 00:23:16,700 Jsem plýtvání sakra hodně paměti. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Ale tam, kde jsem strávil jeden zdroj, Mám ve zvyku se získat zpět další. 552 00:23:22,660 --> 00:23:26,020 Takže když jsem trávit více prostoru, co je asi naděje? 553 00:23:26,020 --> 00:23:27,407 Že jsem strávil méně co? 554 00:23:27,407 --> 00:23:28,240 Diváků: Méně času. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Čas. 556 00:23:28,990 --> 00:23:30,320 A proč by to mohlo být? 557 00:23:30,320 --> 00:23:33,880 No, a co je vložení čas, pokud jde o velký O nyní, 558 00:23:33,880 --> 00:23:37,660 jména, jako je Daven nebo Davenport nebo David? 559 00:23:37,660 --> 00:23:39,340 No, Daven byl pět kroků. 560 00:23:39,340 --> 00:23:42,350 Davenport by devět kroků, tak to by bylo ještě několik kroků. 561 00:23:42,350 --> 00:23:44,250 David by byl pět kroků stejně. 562 00:23:44,250 --> 00:23:47,230 To jsou konkrétní čísla, ale jistě je tu 563 00:23:47,230 --> 00:23:49,550 horní mez Délka něčí jméno. 564 00:23:49,550 --> 00:23:52,240 A skutečně, v problému sady pěti specifikace, 565 00:23:52,240 --> 00:23:54,050 budeme navrhovat že je to něco, 566 00:23:54,050 --> 00:23:55,470 to je 40-některé-liché znaky. 567 00:23:55,470 --> 00:23:58,180 >> Realisticky, nikdo nemá nekonečně dlouhý název, 568 00:23:58,180 --> 00:24:01,542 což znamená, že délka jméno nebo délka řetězce bychom mohli 569 00:24:01,542 --> 00:24:03,750 mají určitý stav Struktura je pravděpodobně to, co? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Je to konstantní. 572 00:24:06,250 --> 00:24:06,430 Je to tak? 573 00:24:06,430 --> 00:24:09,310 Mohlo by to být velký jako konstantní 40-něco, ale to je konstantní. 574 00:24:09,310 --> 00:24:13,752 A to nemá závislosti na tom, kolik Ostatní názvy v této datové struktuře. 575 00:24:13,752 --> 00:24:15,460 Jinými slovy, když jsem chtěl nyní vložit 576 00:24:15,460 --> 00:24:20,540 Colton nebo Gabriel nebo Rob nebo Zamyla nebo Alison nebo Belinda nebo jiné názvy 577 00:24:20,540 --> 00:24:23,940 z řad zaměstnanců do těchto údajů struktura, je doba chodu 578 00:24:23,940 --> 00:24:26,750 vložení další jména bude vůbec ovlivněny 579 00:24:26,750 --> 00:24:30,220 podle toho, jak mnoho dalších prvků, jsou v datové struktuře již? 580 00:24:30,220 --> 00:24:31,040 To ne. 581 00:24:31,040 --> 00:24:31,540 Je to tak? 582 00:24:31,540 --> 00:24:36,150 Vzhledem k tomu, že jsme efektivně používat Tento multi-layer hash tabulky. 583 00:24:36,150 --> 00:24:38,280 A běží čas některé z těchto operací 584 00:24:38,280 --> 00:24:41,510 nezávisí na počtu prvky, které jsou v datové struktuře 585 00:24:41,510 --> 00:24:43,090 nebo že se nakonec bude být v datové struktuře, 586 00:24:43,090 --> 00:24:44,714 ale na délce co konkrétně? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Řetězec je vložena, který přece dělá 589 00:24:49,200 --> 00:24:52,580 tento asymptoticky konstantní time-- velký O jedné. 590 00:24:52,580 --> 00:24:54,720 A upřímně řečeno, právě v reálném světě, to 591 00:24:54,720 --> 00:24:58,380 znamená vložení Daven jméno se jako pěti krocích, nebo Davenport devět 592 00:24:58,380 --> 00:25:00,100 kroky, nebo David pět kroků. 593 00:25:00,100 --> 00:25:03,071 To je zatraceně malá provozní doby. 594 00:25:03,071 --> 00:25:05,320 A opravdu, je to velmi dobrá věc, zvláště když 595 00:25:05,320 --> 00:25:08,126 to není závislé na celkové počet prvků v tam. 596 00:25:08,126 --> 00:25:10,500 Tak jak můžeme realizovat tento druh struktury v kódu? 597 00:25:10,500 --> 00:25:12,900 Je to trochu víc složité, ale přesto je to 598 00:25:12,900 --> 00:25:15,050 jen aplikace základní stavební kameny. 599 00:25:15,050 --> 00:25:17,830 Chystám se znovu definovat nás uzel takto: 600 00:25:17,830 --> 00:25:21,100 bool volal word--, a to by se dalo nazvat cokoliv. 601 00:25:21,100 --> 00:25:23,970 Ale bool představuje to, co jsem nakreslil jako zaškrtnutí. 602 00:25:23,970 --> 00:25:24,490 Ano. 603 00:25:24,490 --> 00:25:26,720 To je konec řetězce V této datové struktury. 604 00:25:26,720 --> 00:25:30,702 >> A samozřejmě, uzel hvězda se odkazuje na děti. 605 00:25:30,702 --> 00:25:32,410 A opravdu, stejně jako rodokmen, budete 606 00:25:32,410 --> 00:25:34,370 by zvážit uzly které visí 607 00:25:34,370 --> 00:25:36,920 dna některých rodiče element být děti. 608 00:25:36,920 --> 00:25:40,510 A tak se děti se chystá být pole 27, 27. jedna 609 00:25:40,510 --> 00:25:41,680 být jen pro apostrof. 610 00:25:41,680 --> 00:25:43,390 Budeme třídit o zvláštní případ, že. 611 00:25:43,390 --> 00:25:45,400 Takže můžete mít jisté jména s apostrofy. 612 00:25:45,400 --> 00:25:47,399 Možná i pomlčkou musí tam jít, ale budete 613 00:25:47,399 --> 00:25:50,330 viz str sadě 5 my jen péče o dopisů a apostrofy. 614 00:25:50,330 --> 00:25:52,990 >> A pak jak si představují datová struktura sama o sobě? 615 00:25:52,990 --> 00:25:56,454 Jak si představují kořen tohoto trie, abych tak řekl? 616 00:25:56,454 --> 00:25:59,620 No, stejně jako s propojeného seznamu, vždy jej potřebují ukazatel na první prvek. 617 00:25:59,620 --> 00:26:04,270 S trie stačí jeden ukazatel na kořen tohoto trie. 618 00:26:04,270 --> 00:26:07,290 A odtud můžete hash vaše cesta dolů hlouběji a hlouběji 619 00:26:07,290 --> 00:26:10,460 pro každý uzel ve struktuře. 620 00:26:10,460 --> 00:26:13,440 Tak jednoduše se to může představujeme, že struct. 621 00:26:13,440 --> 00:26:15,877 >> Nyní Meanwhile-- Oh, otázku. 622 00:26:15,877 --> 00:26:17,220 >> Diváků: Co je bool slovo? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: BOOL slovo právě tato inkarnace C 624 00:26:20,490 --> 00:26:22,920 z toho, co jsem popsal V tomto boxu tady, když 625 00:26:22,920 --> 00:26:26,000 Začal jsem rozdělení každého z prvky pole do dvou částí. 626 00:26:26,000 --> 00:26:27,600 Jedním z nich je ukazatel na další uzel. 627 00:26:27,600 --> 00:26:30,280 Jiný musí být něco jako zaškrtávací políčko 628 00:26:30,280 --> 00:26:33,770 říct, že ano, je tu Slovo Daven, že zde končí, 629 00:26:33,770 --> 00:26:35,610 protože nechceme, v okamžiku, Dave. 630 00:26:35,610 --> 00:26:39,320 >> I když Dave bude legitimní slovo, že to není v trie 631 00:26:39,320 --> 00:26:39,830 ještě. 632 00:26:39,830 --> 00:26:40,950 A D není ani slovo. 633 00:26:40,950 --> 00:26:42,770 A D-není slovo nebo jméno. 634 00:26:42,770 --> 00:26:45,020 Takže zaškrtnutí označuje pouze jednou vás 635 00:26:45,020 --> 00:26:48,190 hit tento uzel předchozí cesta znaků 636 00:26:48,190 --> 00:26:50,700 vlastně řetězec, který jste vložili. 637 00:26:50,700 --> 00:26:53,660 Tak to je vše bool tam dělá pro nás. 638 00:26:53,660 --> 00:26:55,500 >> Jakékoliv další dotazy týkající se pokusů? 639 00:26:55,500 --> 00:26:56,215 Jo. 640 00:26:56,215 --> 00:26:58,035 >> Diváků: Co je přesah? 641 00:26:58,035 --> 00:26:59,945 Co když máte Dave a Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Perfect. 643 00:27:00,820 --> 00:27:02,580 Co když máte Dave a Daven? 644 00:27:02,580 --> 00:27:06,240 Pokud tedy vložíte, řekněme přezdívku, pro David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 To je vlastně super jednoduché. 647 00:27:08,700 --> 00:27:10,325 Takže jsme jen bude trvat čtyři kroky. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. A co mám dělat, až jsem narazila, že čtvrtý uzel? 650 00:27:15,847 --> 00:27:16,680 Jen tak pro kontrolu. 651 00:27:16,680 --> 00:27:18,000 Už jsme dobré jít. 652 00:27:18,000 --> 00:27:18,840 Hotovo. 653 00:27:18,840 --> 00:27:19,750 Čtyři kroky. 654 00:27:19,750 --> 00:27:21,590 Konstantní čas asymptoticky. 655 00:27:21,590 --> 00:27:26,300 A teď jsme ukázaly, že oba Dave a Daven jsou řetězce ve struktuře. 656 00:27:26,300 --> 00:27:27,710 Takže není problém. 657 00:27:27,710 --> 00:27:30,200 A všimněte si, jak přítomnost z Daven to nezvládli 658 00:27:30,200 --> 00:27:34,750 mít více času, nebo méně čas pro Dave a naopak. 659 00:27:34,750 --> 00:27:36,000 >> Takže co jiného můžeme nyní dělat? 660 00:27:36,000 --> 00:27:40,680 Použili jsme tuto metaforu před zásobníků představuje něco. 661 00:27:40,680 --> 00:27:43,380 Ale ukazuje se, že sloupec podložek je vlastně 662 00:27:43,380 --> 00:27:47,187 demonstrativní jiného abstraktní údajů type-- vyšší datovou strukturu úrovně 663 00:27:47,187 --> 00:27:49,770 že na konci dne je jen jako pole nebo spojového seznamu 664 00:27:49,770 --> 00:27:50,970 nebo něco prozaičtější. 665 00:27:50,970 --> 00:27:53,270 Ale je to mnohem zajímavější koncepční pojetí. 666 00:27:53,270 --> 00:27:56,440 Stack, jako jsou tyto žlaby tady v Mather, 667 00:27:56,440 --> 00:27:58,750 se obecně nazývají jen that-- stoh. 668 00:27:58,750 --> 00:28:02,540 >> A v tomto typu datové struktury Máte dvě operations-- 669 00:28:02,540 --> 00:28:05,880 máte jednu s názvem Push pro přidat něco do zásobníku, 670 00:28:05,880 --> 00:28:08,320 jako dávat jiný zásobník Zpět na vrchol zásobníku. 671 00:28:08,320 --> 00:28:11,350 A pak pop, který vás znamená vzít nejvrchnější zásobníku off. 672 00:28:11,350 --> 00:28:16,210 Ale to, co je klíčem k stack je, že to dostal tuto kuriózní vlastnost. 673 00:28:16,210 --> 00:28:19,560 Jako zaměstnanci jídelny jsou přeskupit zásobníky na další jídlo, 674 00:28:19,560 --> 00:28:21,380 co se bude pravda o tom, jak studenti 675 00:28:21,380 --> 00:28:22,856 interagují s touto datovou strukturou? 676 00:28:22,856 --> 00:28:24,480 Diváků: Chystají se pop jednorázové. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Chystají se pop jednorázové, doufejme, že na vrchol. 678 00:28:26,550 --> 00:28:28,910 V opačném případě je to jen trochu hloupý jít celou cestu až na dno. 679 00:28:28,910 --> 00:28:29,070 Je to tak? 680 00:28:29,070 --> 00:28:31,620 Datová struktura není ve skutečnosti umožňuje uchopit spodní zásobník alespoň 681 00:28:31,620 --> 00:28:32,520 snadno. 682 00:28:32,520 --> 00:28:35,040 Takže tam je to zvědavý vlastnost stohu 683 00:28:35,040 --> 00:28:39,730 že poslední položka je bude první ven. 684 00:28:39,730 --> 00:28:43,400 A počítačoví odborníci říkají tento LIFO-- poslední dovnitř, první ven. 685 00:28:43,400 --> 00:28:45,540 A to ve skutečnosti nemá mít zajímavé aplikace. 686 00:28:45,540 --> 00:28:50,090 To není nutně tak zřejmé, jak někteří jiní, ale může skutečně být užitečné, 687 00:28:50,090 --> 00:28:54,040 a může skutečně být provedena v několika různými způsoby. 688 00:28:54,040 --> 00:28:58,550 >> Takže člověk, a ve skutečnosti, ať mě ne se ponořit do toho. 689 00:28:58,550 --> 00:28:59,860 Jdeme na to místo. 690 00:28:59,860 --> 00:29:03,700 Pojďme se podívat na ten, který je téměř Stejný nápad, ale je to trochu spravedlivější. 691 00:29:03,700 --> 00:29:04,200 Je to tak? 692 00:29:04,200 --> 00:29:07,560 Pokud jste některý z těchto ventilátorů chlapecké nebo dívky, které opravdu rád Apple produkty 693 00:29:07,560 --> 00:29:10,130 a probudil ve 3:00 se seřadí v nějakém obchodě 694 00:29:10,130 --> 00:29:14,150 získat nejnovější iPhone, budete mohl frontě takhle. 695 00:29:14,150 --> 00:29:15,800 >> Nyní fronta je velmi záměrně jmenován. 696 00:29:15,800 --> 00:29:18,190 Je to čára, protože tam je některé spravedlnost k němu. 697 00:29:18,190 --> 00:29:18,690 Je to tak? 698 00:29:18,690 --> 00:29:21,690 Bylo by trochu nasává, pokud jste tam dostal nejprve na Apple Store 699 00:29:21,690 --> 00:29:25,700 ale vy jste skutečně nejspodnější zásobník, protože zaměstnanci Apple pak 700 00:29:25,700 --> 00:29:28,189 pop poslední osoba, která vlastně dostal do vedení. 701 00:29:28,189 --> 00:29:31,230 Tak komíny a fronty, i když funkčně jsou druh na same-- 702 00:29:31,230 --> 00:29:33,105 je to právě tato kolekce zdrojů, které je 703 00:29:33,105 --> 00:29:36,210 tam bude růst a shrink-- se Tato spravedlnost aspekt k tomu, 704 00:29:36,210 --> 00:29:39,634 alespoň v reálném světě, kde tyto operace cvičíte 705 00:29:39,634 --> 00:29:40,800 jsou zásadně odlišné. 706 00:29:40,800 --> 00:29:43,360 Stack-- fronta rather-- je řekl, aby měl 707 00:29:43,360 --> 00:29:45,320 dvě operace: n fronty a d fronty. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Nebo je můžete volat libovolný počet věcí. 710 00:29:48,090 --> 00:29:50,770 Ale jen chcete zachytit Představa, že člověk je přidání 711 00:29:50,770 --> 00:29:53,230 a jeden je nakonec odečtením. 712 00:29:53,230 --> 00:29:58,840 >> Nyní pod pokličku, jak stack a fronta by mohla být prováděna jak na to? 713 00:29:58,840 --> 00:30:01,390 Nebudeme zacházet do kódu to proto, že vyšší úroveň 714 00:30:01,390 --> 00:30:03,387 nápad je trochu více zřejmé. 715 00:30:03,387 --> 00:30:04,470 Chci říct, co lidé dělají? 716 00:30:04,470 --> 00:30:07,030 Pokud jsem první člověk na Apple Uložte a to je přední dveře, 717 00:30:07,030 --> 00:30:08,130 víš, já budu stát tady. 718 00:30:08,130 --> 00:30:09,750 A další osoby bude tady stát. 719 00:30:09,750 --> 00:30:11,500 A další osoby bude tady stát. 720 00:30:11,500 --> 00:30:13,792 Takže to, co datová struktura lze uplatnit na frontě? 721 00:30:13,792 --> 00:30:14,542 >> Diváků: fronta. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: No, fronta. 723 00:30:15,667 --> 00:30:16,390 Jistě. 724 00:30:16,390 --> 00:30:16,920 Co ještě? 725 00:30:16,920 --> 00:30:17,600 >> Diváků: spojový seznam. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: souvisí seznam, který by mohl realizovat. 727 00:30:18,990 --> 00:30:22,500 A spojový seznam je pěkné, protože pak může růst libovolně dlouho, na rozdíl 728 00:30:22,500 --> 00:30:24,880 se mít nějaký pevný počet lidí v obchodě. 729 00:30:24,880 --> 00:30:27,030 Ale možná, že pevně stanovený počet míst je legitimní. 730 00:30:27,030 --> 00:30:30,350 Vzhledem k tomu, pokud mají jen jako 20 iPhone první den, možná 731 00:30:30,350 --> 00:30:33,930 oni jen potřebují řadu velikostí 20 představují, že frontu, která 732 00:30:33,930 --> 00:30:37,070 je pouze říci teď, jakmile začneme mluvit o těchto problémech vyšší úrovni, 733 00:30:37,070 --> 00:30:38,890 můžete ji implementovat v mnoha různými způsoby. 734 00:30:38,890 --> 00:30:42,030 A je to asi jen tak být kompromis v prostoru a čase 735 00:30:42,030 --> 00:30:43,950 nebo jen ve svém vlastním kódu složitosti. 736 00:30:43,950 --> 00:30:45,380 >> Co stohu? 737 00:30:45,380 --> 00:30:48,190 No, zásobník, jsme viděli příliš může být jen tyto zásobníky. 738 00:30:48,190 --> 00:30:50,007 A ty by mohly realizovat toto pole. 739 00:30:50,007 --> 00:30:53,090 Ale v určitém okamžiku, pokud používáte pole, co se bude dít na zásobníky 740 00:30:53,090 --> 00:30:54,173 se snažíte dát dolů? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Dobrá. 743 00:30:55,670 --> 00:30:57,490 Budeš jen moci jít tak vysoko. 744 00:30:57,490 --> 00:31:00,156 A myslím, že v Mather, že jsou skutečně zapuštěné v tomto otvoru. 745 00:31:00,156 --> 00:31:01,950 Takže ve skutečnosti, to je téměř jako Mather používá 746 00:31:01,950 --> 00:31:03,783 pole pevné velikosti, protože můžete jen 747 00:31:03,783 --> 00:31:08,302 vejde tolik zásobníky v tomto otvoru v stěny dolů pod kolena lidí. 748 00:31:08,302 --> 00:31:10,010 A tak, aby mohla být říká, že je pole, 749 00:31:10,010 --> 00:31:14,300 ale mohli bychom jistě realizovat, že obecněji s propojeného seznamu. 750 00:31:14,300 --> 00:31:16,390 >> No, co jiného datové struktury? 751 00:31:16,390 --> 00:31:18,760 Dovolte mi, abych vytáhnout jeden jiný vizuální zde. 752 00:31:18,760 --> 00:31:24,710 Něco jako, jak o tomhle tady? 753 00:31:24,710 --> 00:31:28,920 Proč by mohlo být užitečné mít ne něco tak nóbl jako trie, která 754 00:31:28,920 --> 00:31:32,370 viděli jsme měli tyto velmi široké uzly, z nichž každý je v poli? 755 00:31:32,370 --> 00:31:35,740 Ale co když uděláme něco víc jednoduše, jako staré školy rodokmenu, 756 00:31:35,740 --> 00:31:38,110 jejichž jednotlivé uzly zde právě ukládání čísel. 757 00:31:38,110 --> 00:31:42,180 Místo názvu nebo potomka právě ukládání čísel, jako je tento. 758 00:31:42,180 --> 00:31:45,250 >> No, žargon používáme v datové struktury je oba snaží 759 00:31:45,250 --> 00:31:49,510 a stromy, kde Trie, opět, je jen ten, jehož uzly jsou pole, 760 00:31:49,510 --> 00:31:51,680 je stále to, co by mohlo používat od základní škole 761 00:31:51,680 --> 00:31:53,860 když jste se rodina tree-- listy a kořen 762 00:31:53,860 --> 00:31:57,250 stromu a děti mateřská a jejich sourozenci. 763 00:31:57,250 --> 00:32:03,670 A my bychom mohli realizovat strom, například, jak jednoduše jako to. 764 00:32:03,670 --> 00:32:07,420 Strom, pokud to jako uzel, jeden z Tyto kruhy, které má číslo, 765 00:32:07,420 --> 00:32:09,947 že to nebude mít jeden ukazatel, ale dva. 766 00:32:09,947 --> 00:32:11,780 A jakmile přidáte Druhý ukazatel, můžete 767 00:32:11,780 --> 00:32:13,905 nyní mohou skutečně udělat trochu dvourozměrného údajů 768 00:32:13,905 --> 00:32:14,780 struktury v paměti. 769 00:32:14,780 --> 00:32:16,660 Stejně jako dvojrozměrný pole, můžete 770 00:32:16,660 --> 00:32:18,904 mít takovou dvou-dimenzionální spojové seznamy, ale ty 771 00:32:18,904 --> 00:32:20,820 že následovat vzor tam, kde je žádné cykly. 772 00:32:20,820 --> 00:32:24,487 Je to opravdu strom s jedním prarodič až sem a pak 773 00:32:24,487 --> 00:32:27,320 někteří rodiče a děti a vnoučata a pravnoučata. 774 00:32:27,320 --> 00:32:28,370 a tak dále. 775 00:32:28,370 --> 00:32:32,390 >> Ale co je opravdu hezké o tom taky, jen proto, aby tě škádlit s trochou kódu, 776 00:32:32,390 --> 00:32:35,370 odvolání rekurze od chvíli zpět, přičemž 777 00:32:35,370 --> 00:32:38,220 můžete napsat funkci, která volá sama sebe. 778 00:32:38,220 --> 00:32:41,140 To je krásná příležitost provádět něco 779 00:32:41,140 --> 00:32:42,920 jako rekurze, protože to považují. 780 00:32:42,920 --> 00:32:43,860 >> Jedná se o strom. 781 00:32:43,860 --> 00:32:48,040 A byl jsem trochu anální s tím, jak Dal jsem celá čísla na ulici. 782 00:32:48,040 --> 00:32:51,020 Natolik, že to má zvláštní name-- binární vyhledávací strom. 783 00:32:51,020 --> 00:32:53,460 Nyní jsme slyšeli o binární hledat, ale můžete 784 00:32:53,460 --> 00:32:55,180 pozpátku ze jména ta věc je? 785 00:32:55,180 --> 00:32:59,280 Co je vzor, ​​jak jsem vložena celá čísla do tohoto stromu? 786 00:32:59,280 --> 00:33:00,696 To není libovolná. 787 00:33:00,696 --> 00:33:01,570 Tam je nějaký vzor. 788 00:33:01,570 --> 00:33:02,090 Jo. 789 00:33:02,090 --> 00:33:03,370 >> Diváků: menší na levé straně. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Jo. 791 00:33:03,690 --> 00:33:05,062 Menší jsou na levé straně. 792 00:33:05,062 --> 00:33:06,270 Ty větší jsou na pravé straně. 793 00:33:06,270 --> 00:33:12,940 Tak, že pravdivé tvrzení je rodič je větší než jeho levé dítě, 794 00:33:12,940 --> 00:33:14,850 ale méně než pravém dítě. 795 00:33:14,850 --> 00:33:17,750 A to samo o sobě je ještě rekurzivní slovní definice 796 00:33:17,750 --> 00:33:20,500 protože můžete použít, že Stejná logika se ke každému uzlu 797 00:33:20,500 --> 00:33:23,080 a to jen dna out, referenční případ, pokud vás 798 00:33:23,080 --> 00:33:25,740 bude, když narazí jeden z listy, abych tak řekl, 799 00:33:25,740 --> 00:33:28,580 kde dovolená má žádné děti dál. 800 00:33:28,580 --> 00:33:30,614 >> Nyní, jak můžete najít číslo 44? 801 00:33:30,614 --> 00:33:32,280 Ty by začít u kořene a říct, hm. 802 00:33:32,280 --> 00:33:35,690 55 není 44 Tak to já chci jít právo nebo nechci jít doleva? 803 00:33:35,690 --> 00:33:37,190 No, samozřejmě budete chtít jít doleva. 804 00:33:37,190 --> 00:33:40,060 A tak je to stejně jako telefon Kniha příklad v binární vyhledávání 805 00:33:40,060 --> 00:33:41,099 obecněji. 806 00:33:41,099 --> 00:33:43,390 Ale my jsme jeho provádění Nyní trochu více dynamicky 807 00:33:43,390 --> 00:33:45,339 než pole může dovolit. 808 00:33:45,339 --> 00:33:48,130 A ve skutečnosti, pokud se chcete podívat na kód, na první pohled jistě. 809 00:33:48,130 --> 00:33:49,671 Vypadá to, že spoustu linek. 810 00:33:49,671 --> 00:33:51,220 Ale je to krásně jednoduché. 811 00:33:51,220 --> 00:33:54,490 Chcete-li implementovat funkci volal hledání, jehož smysl života 812 00:33:54,490 --> 00:33:57,290 je hledat hodnotu jako je N, celé číslo, 813 00:33:57,290 --> 00:34:01,756 a ty jsi prošel v jednom pointer-- ukazatel na uzel kořenů, 814 00:34:01,756 --> 00:34:04,380 spíše z toho stromu, z něhož můžete přistupovat všechno ostatní, 815 00:34:04,380 --> 00:34:08,850 Všimněte si, jak přímočaře můžete implementovat logiku. 816 00:34:08,850 --> 00:34:10,880 Pokud je strom je null, samozřejmě, že to tam není. 817 00:34:10,880 --> 00:34:11,880 Řekněme, vrátí false. 818 00:34:11,880 --> 00:34:12,000 Je to tak? 819 00:34:12,000 --> 00:34:14,040 Pokud to ruce nic, tam nic není. 820 00:34:14,040 --> 00:34:17,900 >> Jinak, jestliže n je menší než strom šipka n- nyní šipka n, 821 00:34:17,900 --> 00:34:20,670 vzpomínám jsme zavedli Super Krátce na druhý den, 822 00:34:20,670 --> 00:34:25,100 a to jen znamená, že de-reference ukazatel a podívejte se na pole s názvem n. 823 00:34:25,100 --> 00:34:27,690 Takže to znamená, tam a podívejte se na pole s názvem n. 824 00:34:27,690 --> 00:34:33,810 Takže pokud n, hodnota, kterou jste daný, je méně než hodnota v korunách stromů číslo, 825 00:34:33,810 --> 00:34:35,449 kam chcete jít? 826 00:34:35,449 --> 00:34:36,389 Doleva. 827 00:34:36,389 --> 00:34:37,780 >> Takže si všimnout rekurzi. 828 00:34:37,780 --> 00:34:39,860 Já returning-- není pravda. 829 00:34:39,860 --> 00:34:40,989 Ne false. 830 00:34:40,989 --> 00:34:45,670 Vracím se bez ohledu na odpověď je z volání sebe, kolem 831 00:34:45,670 --> 00:34:50,100 opět n, která je nadbytečná, ale to, co je teď trochu jinak? 832 00:34:50,100 --> 00:34:51,989 Jak mám dělat problém menší? 833 00:34:51,989 --> 00:34:54,920 Jsem předáním jako druhý Argument není kořen stromu, 834 00:34:54,920 --> 00:34:59,616 ale levá dítě v tomto případě. 835 00:34:59,616 --> 00:35:00,990 Takže jsem kolem v levém dítěte. 836 00:35:00,990 --> 00:35:04,720 >> Mezitím, pokud n je větší než uzel Jsem v současné době při pohledu na, 837 00:35:04,720 --> 00:35:06,690 Jsem hledat na pravé straně. 838 00:35:06,690 --> 00:35:10,880 Jinak, v případě, že strom není null, a V případě, že prvek není doleva 839 00:35:10,880 --> 00:35:13,240 a není to na pravé straně, co je nádherně případ? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Jsme skutečně našli uzel v otázka, a tak jsme se vrátit true. 842 00:35:18,440 --> 00:35:21,490 >> Tak jsme právě poškrábaný povrch nyní některé z těchto datových struktur. 843 00:35:21,490 --> 00:35:24,370 V problém nastavit pět budete prozkoumat tyto ještě dále, 844 00:35:24,370 --> 00:35:27,250 a budete mít váš návrh Volba, jak jít o to. 845 00:35:27,250 --> 00:35:30,250 Co bych chtěl na závěr o je jen 30 sekund teaser 846 00:35:30,250 --> 00:35:32,080 o tom, co čeká příští týden a mimo ni. 847 00:35:32,080 --> 00:35:35,390 >> Jak jsme begin-- naštěstí byste mohli think-- náš přechod pomalu 848 00:35:35,390 --> 00:35:38,680 ze světa C a nižší detaily implementace na úrovni, 849 00:35:38,680 --> 00:35:42,090 do světa, v němž si můžeme pro samozřejmé, že někdo jiný má konečně 850 00:35:42,090 --> 00:35:44,010 realizovány tyto údaje struktury pro nás, 851 00:35:44,010 --> 00:35:47,570 a začneme chápat reálný svět prostřednictvím prováděcích 852 00:35:47,570 --> 00:35:50,560 web-based programy a Webové stránky obecně 853 00:35:50,560 --> 00:35:52,910 a také velmi bezpečnostní důsledky, které jsme jen 854 00:35:52,910 --> 00:35:54,850 začal poškrábat povrch. 855 00:35:54,850 --> 00:35:57,320 Zde je to, co nás čeká v příštích dnech. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO PŘEHRÁVÁNÍ] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Je Přišel se zprávou, s protokolem všichni jeho vlastní. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Přišel na svět krutý firewally, routery, bezcitný 861 00:36:30,894 --> 00:36:33,368 a nebezpečí daleko horší než smrt. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Je rychlý. 864 00:36:36,236 --> 00:36:37,980 On je silný. 865 00:36:37,980 --> 00:36:42,830 Je to TCP / IP, a on má svou adresu. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Válečníci sítě." 868 00:36:48,074 --> 00:36:49,660 [END VIDEOPŘEHRÁVÁNÍ] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: Již příští týden. 870 00:36:50,910 --> 00:36:51,880 Uvidíme se pak. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO PŘEHRÁVÁNÍ] 873 00:36:56,060 --> 00:36:59,240 -A Teď, "hluboké myšlenky" od Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Vždy začíná přednášky se, "v pořádku." 876 00:37:05,820 --> 00:37:08,750 Proč ne, "Tady je řešení na tento týden problém set " 877 00:37:08,750 --> 00:37:12,180 nebo "Dáváme všechny z vás?" 878 00:37:12,180 --> 00:37:13,380 [Smích] 879 00:37:13,380 --> 00:37:15,530 [END VIDEOPŘEHRÁVÁNÍ]