1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Takže ve CS50, jsme probrali
mnoho různých datových struktur,

3
00:00:08,300 --> 00:00:09,180
v pořádku?

4
00:00:09,180 --> 00:00:11,420
Viděli jsme pole, a je spojena
seznamy a hashovací tabulky,

5
00:00:11,420 --> 00:00:15,210
a snaží se, komíny a fronty.

6
00:00:15,210 --> 00:00:17,579
Budeme také dozvědět něco
o stromy a haldách,

7
00:00:17,579 --> 00:00:20,120
ale ve skutečnosti to vše jen konec
up je variace na téma.

8
00:00:20,120 --> 00:00:22,840
Tam opravdu jsou tito
druh čtyř základních myšlenek

9
00:00:22,840 --> 00:00:25,190
že vše ostatní může se redukuje na.

10
00:00:25,190 --> 00:00:28,150
Pole, spojové seznamy,
hashovací tabulky, a snaží se.

11
00:00:28,150 --> 00:00:30,720
A jak jsem řekl, že
jsou variace na nich,

12
00:00:30,720 --> 00:00:32,720
ale to je dost
hodně jít do shrnout

13
00:00:32,720 --> 00:00:38,140
všechno, co budeme mluvit
o v této třídě, pokud jde o C.

14
00:00:38,140 --> 00:00:40,140
>> Ale jak to všechno opatření nahoru, ne?

15
00:00:40,140 --> 00:00:44,265
Mluvili jsme o výhodách a nevýhodách
každé v oddělených videa na nich,

16
00:00:44,265 --> 00:00:46,390
ale je tu spousta čísel
dostat hozen kolem.

17
00:00:46,390 --> 00:00:48,723
Je tu spousta obecné
myšlenky dostat hozen kolem.

18
00:00:48,723 --> 00:00:51,950
Zkusme a konsolidovat
že do jediného místa.

19
00:00:51,950 --> 00:00:55,507
Pojďme zvážit výhody proti
jsou nevýhody, a zvážit

20
00:00:55,507 --> 00:00:57,340
což struktura dat
může být ta pravá dat

21
00:00:57,340 --> 00:01:01,440
struktura pro vaši konkrétní situaci,
bez ohledu na typ dat jste skladování.

22
00:01:01,440 --> 00:01:06,625
Nemusíte nutně vždy nutné
použijte super rychlé vložení, vymazání,

23
00:01:06,625 --> 00:01:10,761
a vyhledávání z trie, pokud opravdu
se nestarají o vkládání a mazání

24
00:01:10,761 --> 00:01:11,260
moc.

25
00:01:11,260 --> 00:01:13,968
Pokud potřebujete jen rychle náhodný
přístup, možná pole je lepší.

26
00:01:13,968 --> 00:01:15,340
Takže pojďme pálit to.

27
00:01:15,340 --> 00:01:18,530
Pojďme se bavit o každé ze čtyř
hlavní druhy datových struktur

28
00:01:18,530 --> 00:01:21,720
že jsme mluvili o, a
prostě vidět, kdy by mohl být dobrý,

29
00:01:21,720 --> 00:01:23,340
a když oni by mohli nebude tak dobrá.

30
00:01:23,340 --> 00:01:24,610
Takže začněme s poli.

31
00:01:24,610 --> 00:01:27,300
Takže vložení, že to trochu špatné.

32
00:01:27,300 --> 00:01:31,350
>> Vložený na konci pole je v pořádku,
pokud stavíme celou řadu, jak jsme jít.

33
00:01:31,350 --> 00:01:33,570
Ale pokud budeme potřebovat vložit
prvky do středu,

34
00:01:33,570 --> 00:01:35,550
Vzpomeňte si na vložení
třídění, je tu spousta

35
00:01:35,550 --> 00:01:37,510
posouvání, aby se vešly prvek tam.

36
00:01:37,510 --> 00:01:41,170
A tak, když budeme vložit
nikde jinde než na konci pole,

37
00:01:41,170 --> 00:01:43,590
že to asi není tak velký.

38
00:01:43,590 --> 00:01:46,710
>> Podobně, mazání, pokud jsme
mazání od konce pole,

39
00:01:46,710 --> 00:01:49,810
je asi také není tak skvělé, pokud
nechceme nechat prázdné mezery,

40
00:01:49,810 --> 00:01:50,790
které obvykle nemáme.

41
00:01:50,790 --> 00:01:54,700
Chceme odstranit prvek, a
pak tak nějak, aby to znovu pohodlný.

42
00:01:54,700 --> 00:01:57,670
A tak mazání prvků z
pole, také není tak velký.

43
00:01:57,670 --> 00:01:58,820
>> Vyhledávání, i když, je skvělá.

44
00:01:58,820 --> 00:02:00,920
Máme náhodný přístup,
konstantní čas vyhledávání.

45
00:02:00,920 --> 00:02:03,800
Právě jsme se říci, sedm, a půjdeme
do pole přemístění sedm.

46
00:02:03,800 --> 00:02:05,907
My říkáme 20, s Jdi na
array přemístění 20.

47
00:02:05,907 --> 00:02:07,240
Nemáme k iterovat přes.

48
00:02:07,240 --> 00:02:08,630
To je docela dobrý.

49
00:02:08,630 --> 00:02:11,020
>> Pole jsou také relativně snadno třídit.

50
00:02:11,020 --> 00:02:14,040
Pokaždé, když jsme mluvili o třídění
algoritmus, jako je výběr druhu,

51
00:02:14,040 --> 00:02:18,820
insertion sort, bublinkové řazení, sloučit
třídění, jsme vždycky pole, jak to udělat,

52
00:02:18,820 --> 00:02:21,860
protože pole jsou docela snadné
třídění, vzhledem k datové struktury

53
00:02:21,860 --> 00:02:22,970
jsme dosud viděli.

54
00:02:22,970 --> 00:02:24,320
>> Jsou to také poměrně malý.

55
00:02:24,320 --> 00:02:25,695
Tam není moc větší prostor.

56
00:02:25,695 --> 00:02:29,210
Právě jste zrušil přesně tolik, kolik
jak budete potřebovat držet vaše data,

57
00:02:29,210 --> 00:02:30,320
a to je do značné míry to.

58
00:02:30,320 --> 00:02:33,180
Takže jsou to docela malé
a efektivní tímto způsobem.

59
00:02:33,180 --> 00:02:36,000
Ale další nevýhodou, i když,
je to, že jsou stanoveny v velikost.

60
00:02:36,000 --> 00:02:38,630
Musíme přiznat, jak přesně
big chceme naše pole být,

61
00:02:38,630 --> 00:02:39,940
a my jen jeden pokus na to.

62
00:02:39,940 --> 00:02:41,280
Nemůžeme růst a zmenšit ji.

63
00:02:41,280 --> 00:02:44,582
>> Pokud potřebujeme pěstovat nebo zmenšit to, my
je třeba vyhlásit zcela novou řadu,

64
00:02:44,582 --> 00:02:47,750
zkopírujte všechny prvků
První pole do druhého pole.

65
00:02:47,750 --> 00:02:51,410
A pokud se přepočítal, že
čas, musíme to udělat znovu.

66
00:02:51,410 --> 00:02:52,760
Moc dobře ne.

67
00:02:52,760 --> 00:02:58,750
Takže pole nedávají nám flexibilitu
mít variabilní počet prvků.

68
00:02:58,750 --> 00:03:01,320
>> S Google seznamu
vložení je docela snadné.

69
00:03:01,320 --> 00:03:03,290
Prostě jsme připnout na přední straně.

70
00:03:03,290 --> 00:03:04,892
Vypuštění je také docela snadné.

71
00:03:04,892 --> 00:03:06,100
Musíme najít prvky.

72
00:03:06,100 --> 00:03:07,270
Které se týkají nějaké vyhledávání.

73
00:03:07,270 --> 00:03:10,270
>> Ale jakmile jste našli element
hledáte, vše, co musíte udělat vy

74
00:03:10,270 --> 00:03:12,830
Je-li změnit ukazatel,
možná dva, pokud máte

75
00:03:12,830 --> 00:03:15,151
propojené list-- dvojnásobně
spojový seznam, rather--

76
00:03:15,151 --> 00:03:16,650
a pak stačí uvolnit uzel.

77
00:03:16,650 --> 00:03:18,399
Nemusíte k posunu
všechno kolem.

78
00:03:18,399 --> 00:03:22,090
Ty stačí změnit dva ukazatele,
tak to je docela rychlý.

79
00:03:22,090 --> 00:03:23,470
>> Vyhledávání je špatné, že?

80
00:03:23,470 --> 00:03:26,280
Aby nám najít
prvek v Google seznamu

81
00:03:26,280 --> 00:03:29,154
ať už jednotlivě nebo dvakrát spojeny,
musíme lineární hledat to.

82
00:03:29,154 --> 00:03:32,320
Musíme začít od začátku a
přesunout na konec, nebo začít na konci pohybu

83
00:03:32,320 --> 00:03:33,860
na začátek.

84
00:03:33,860 --> 00:03:35,474
Nemáme náhodný přístup ještě.

85
00:03:35,474 --> 00:03:37,265
Takže pokud Děláme
Hodně vyhledávání, možná

86
00:03:37,265 --> 00:03:39,830
propojeného seznam není
až tak dobré pro nás.

87
00:03:39,830 --> 00:03:43,750
>> Jsou také velmi
obtížné třídit, že jo?

88
00:03:43,750 --> 00:03:45,666
Jediný způsob, jak můžete
Opravdu třídit propojeného seznamu

89
00:03:45,666 --> 00:03:47,870
je třídit, jak jste si ji postaví.

90
00:03:47,870 --> 00:03:50,497
Ale pokud si ho seřadit jak vy
postavit to, že jste již

91
00:03:50,497 --> 00:03:51,830
Díky rychlé vkládání ještě.

92
00:03:51,830 --> 00:03:53,746
Nejste jen připínání
věci na přední.

93
00:03:53,746 --> 00:03:55,710
Musíte najít
správné místo, aby to,

94
00:03:55,710 --> 00:03:57,820
a pak se vaše vložení
stane se jen o tak špatné,

95
00:03:57,820 --> 00:03:59,390
jako vložení do matice.

96
00:03:59,390 --> 00:04:03,130
Takže propojené seznamy nejsou
tak velký pro třídění dat.

97
00:04:03,130 --> 00:04:05,830
>> Jsou také docela malý, velikost-moudrý.

98
00:04:05,830 --> 00:04:08,496
Dvojnásob mírně spojeno seznam
větší než jednotlivě provázané seznamy,

99
00:04:08,496 --> 00:04:10,620
, které jsou o něco větší
než pole, ale není to

100
00:04:10,620 --> 00:04:13,330
obrovské množství nevyužité místo.

101
00:04:13,330 --> 00:04:18,730
Takže pokud prostor je za vysokou cenu, ale
Není to opravdu intenzivní prémie,

102
00:04:18,730 --> 00:04:22,180
to může být ta správná cesta, jak jít.

103
00:04:22,180 --> 00:04:23,330
>> Hash stoly.

104
00:04:23,330 --> 00:04:25,850
Vložení do hash tabulky
je poměrně jednoduchá.

105
00:04:25,850 --> 00:04:26,980
Je to dvoustupňový proces.

106
00:04:26,980 --> 00:04:30,700
Nejprve je potřeba spustit naše data prostřednictvím
funkce hash získat hash kód,

107
00:04:30,700 --> 00:04:37,550
a pak vložíme prvek do
hash tabulky v tomto hash kód Umístění.

108
00:04:37,550 --> 00:04:40,879
>> Vypuštění, podobně jako Google seznamu
je snadné, jakmile zjistíte prvek.

109
00:04:40,879 --> 00:04:43,170
Musíte ji nejprve najít,
ale pak, když jej odstranit,

110
00:04:43,170 --> 00:04:45,128
stačí vyměnit
pár ukazatelů,

111
00:04:45,128 --> 00:04:47,250
pokud používáte samostatné řetězení.

112
00:04:47,250 --> 00:04:49,942
Pokud používáte snímání,
nebo pokud si nejste

113
00:04:49,942 --> 00:04:51,650
za použití řetězení vůbec
v hash tabulce,

114
00:04:51,650 --> 00:04:53,040
vypuštění je vlastně rychlé.

115
00:04:53,040 --> 00:04:57,134
Vše, co musíte udělat, je hash
dat, a pak jít na dané místo.

116
00:04:57,134 --> 00:04:58,925
A za předpokladu, že ne
máte nějaké kolize,

117
00:04:58,925 --> 00:05:01,650
budete moci velmi rychle odstranit.

118
00:05:01,650 --> 00:05:04,930
>> Nyní, vyhledávání je místo, kde se věci
trochu složitější.

119
00:05:04,930 --> 00:05:06,910
To je v průměru lepší
než spojových seznamů.

120
00:05:06,910 --> 00:05:09,560
Pokud používáte zřetězení,
stále máte propojeného seznamu,

121
00:05:09,560 --> 00:05:13,170
což znamená, že stále mají
Hledání úkor propojeného seznamu.

122
00:05:13,170 --> 00:05:18,390
Ale protože jste při vaší spojené
Seznam a to rozdělení více než 100 nebo 1000

123
00:05:18,390 --> 00:05:25,380
nebo n elementy ve vašem hash tabulce, jste
spojové seznamy jsou jedním nth velikosti.

124
00:05:25,380 --> 00:05:27,650
Všichni jsou podstatně menší.

125
00:05:27,650 --> 00:05:32,080
Jste n spojeny seznamy namísto
jednoho spojového seznamu velikosti n.

126
00:05:32,080 --> 00:05:34,960
>> A tak to real-svět konstantní
faktorem, který jsme se obecně

127
00:05:34,960 --> 00:05:39,730
nemluví o v časové složitosti to,
dělá ve skutečnosti něco změnit zde.

128
00:05:39,730 --> 00:05:43,020
Takže vyhledávání je stále lineární
podívejte se, zda používáte zřetězení,

129
00:05:43,020 --> 00:05:46,780
ale délka seznamu
hledáte prostřednictvím

130
00:05:46,780 --> 00:05:50,080
je velmi, velmi krátké srovnání.

131
00:05:50,080 --> 00:05:52,995
Opět platí, že pokud je třídění vašich
cílem zde, hash tabulky

132
00:05:52,995 --> 00:05:54,370
asi není správná cesta.

133
00:05:54,370 --> 00:05:56,830
Stačí použít pole, pokud třídění
je pro vás opravdu důležité.

134
00:05:56,830 --> 00:05:58,590
>> A mohou oscilují velikosti.

135
00:05:58,590 --> 00:06:01,640
Je těžké říci, zda je
hash tabulka je malý nebo velký,

136
00:06:01,640 --> 00:06:04,110
protože to opravdu záleží na
jak velký je váš hash tabulky je.

137
00:06:04,110 --> 00:06:07,340
Pokud jste jen bude uložení
pět prvků ve vašem hash tabulky,

138
00:06:07,340 --> 00:06:10,620
a máte hash tabulku
s 10.000 elementy v tom,

139
00:06:10,620 --> 00:06:12,614
jste pravděpodobně plýtvání hodně prostoru.

140
00:06:12,614 --> 00:06:15,030
Kontrast je také
mají velmi kompaktní hash tabulky,

141
00:06:15,030 --> 00:06:18,720
ale menší vaše hash tabulky dostane,
každé z těchto spojových seznamů delší

142
00:06:18,720 --> 00:06:19,220
dostane.

143
00:06:19,220 --> 00:06:22,607
A tak tam opravdu žádný způsob, jak definovat
přesně velikost hash tabulky,

144
00:06:22,607 --> 00:06:24,440
ale to je pravděpodobně bezpečné
říkat, že je to obecně

145
00:06:24,440 --> 00:06:27,990
Bude větší, než spojený
Seznam ukládání stejná data,

146
00:06:27,990 --> 00:06:30,400
ale menší než trie.

147
00:06:30,400 --> 00:06:32,720
>> A snaží se o čtvrtou
z těchto struktur

148
00:06:32,720 --> 00:06:34,070
že jsme mluvili o.

149
00:06:34,070 --> 00:06:36,450
Vkládání do trie je složitý.

150
00:06:36,450 --> 00:06:38,400
Je tu hodně dynamický
alokace paměti,

151
00:06:38,400 --> 00:06:40,780
zvláště na začátku,
jak jste začínají stavět.

152
00:06:40,780 --> 00:06:43,700
Ale je to konstantní čas.

153
00:06:43,700 --> 00:06:47,690
Je to jen lidský element
tady, že dělá to složitější.

154
00:06:47,690 --> 00:06:53,250
S setkat ukazatele null, malloc
prostor, tam, možná malloc prostor

155
00:06:53,250 --> 00:06:54,490
odtamtud znovu.

156
00:06:54,490 --> 00:06:58,880
Druh zastrašování faktoru
ukazatele v dynamického přidělování paměti

157
00:06:58,880 --> 00:07:00,130
je překážka zmizí.

158
00:07:00,130 --> 00:07:04,550
Ale jakmile jste ji přečetl, vkládání
vlastně přijde docela jednoduché,

159
00:07:04,550 --> 00:07:06,810
a to jistě je konstantní čas.

160
00:07:06,810 --> 00:07:07,680
>> Mazání je snadné.

161
00:07:07,680 --> 00:07:11,330
Vše, co musíte udělat, je pohybovat dolů
několik ukazatelů a volného uzlu,

162
00:07:11,330 --> 00:07:12,420
tak to je docela dobré.

163
00:07:12,420 --> 00:07:13,930
Vyhledávání je také velmi rychlý.

164
00:07:13,930 --> 00:07:16,780
Je to jen na základě
Délka vašich dat.

165
00:07:16,780 --> 00:07:19,924
Takže pokud všechna vaše data je
pět řetězce znaků,

166
00:07:19,924 --> 00:07:22,590
Například, že jste ukládání pět
řetězce znaků ve vašem trie,

167
00:07:22,590 --> 00:07:25,439
to trvá jen pět kroků na
najít to, co hledáte.

168
00:07:25,439 --> 00:07:28,480
Five je jen konstantní faktor, tak
Znovu, vkládání, mazání a vyhledávání

169
00:07:28,480 --> 00:07:31,670
Zde jsou všechny konstantní čas, efektivně.

170
00:07:31,670 --> 00:07:34,880
>> Další věc je, že vaše trie je
vlastně druh již řazeno, že jo?

171
00:07:34,880 --> 00:07:36,800
Na základě toho, jak jsme
vkládání prvků,

172
00:07:36,800 --> 00:07:40,060
tím, že jde písmeno dopisem z
klíč, nebo po jednotlivých číslicích klíče,

173
00:07:40,060 --> 00:07:45,084
typicky Vaše trie skončí jako
druh řazeny, jak si ho postavit.

174
00:07:45,084 --> 00:07:47,250
To není opravdu dělá
smysl přemýšlet o tom, třídění

175
00:07:47,250 --> 00:07:49,874
Stejným způsobem si myslíme, že o
to s poli, nebo provázané seznamy,

176
00:07:49,874 --> 00:07:51,070
nebo hashovací tabulky.

177
00:07:51,070 --> 00:07:54,780
Ale v jistém smyslu, vaše
Trie je řazen as you go.

178
00:07:54,780 --> 00:07:58,630
>> Nevýhodou ovšem je, že
Trie rychle stává obrovský.

179
00:07:58,630 --> 00:08:02,970
Z každého křižovatce, můžete
have-- pokud váš klíč se skládá z číslic,

180
00:08:02,970 --> 00:08:04,880
máte 10 dalších
místa, můžete jít, což

181
00:08:04,880 --> 00:08:07,490
Znamená to, že každý uzel
obsahuje informace

182
00:08:07,490 --> 00:08:11,440
o datech, které chcete uložit
v tomto uzlu, plus 10 ukazatelů.

183
00:08:11,440 --> 00:08:14,430
Což, na CS50 IDE, je 80 bytů.

184
00:08:14,430 --> 00:08:17,220
Takže to je alespoň 80 bajtů pro
každý uzel, který vytvoříte,

185
00:08:17,220 --> 00:08:19,240
a to ani počítání data.

186
00:08:19,240 --> 00:08:24,950
A pokud vaše uzly
dopisy místo číslic,

187
00:08:24,950 --> 00:08:27,825
Nyní máte 26 ukazatele
z každého místa.

188
00:08:27,825 --> 00:08:32,007
A 26 krát 8 je asi 200
bajtů, nebo něco takového.

189
00:08:32,007 --> 00:08:33,840
A máte kapitál
a lowercase-- vám může

190
00:08:33,840 --> 00:08:35,381
vidět, kam jdu s tím, že jo?

191
00:08:35,381 --> 00:08:37,500
Vaše uzly může dostat opravdu
velký, a tak trie

192
00:08:37,500 --> 00:08:40,470
sám, celkově může
opravdu velká, taky.

193
00:08:40,470 --> 00:08:42,630
Takže pokud prostor je za vysokou
prémie na vašem systému,

194
00:08:42,630 --> 00:08:45,830
Trie nemusí být správný způsob, jak
jít, i když jeho další výhody

195
00:08:45,830 --> 00:08:47,780
vstupují do hry.

196
00:08:47,780 --> 00:08:48,710
Jsem Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
To je CS50.

198
00:08:50,740 --> 00:08:52,316