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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Takže vo CS50, sme prebrali
veľa rôznych dátových štruktúr,

3
00:00:08,300 --> 00:00:09,180
v poriadku?

4
00:00:09,180 --> 00:00:11,420
Videli sme poľa, a je spojená
zoznamy a hashovacie tabuľky,

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

6
00:00:15,210 --> 00:00:17,579
Budeme tiež dozvedieť niečo
o stromy a haldách,

7
00:00:17,579 --> 00:00:20,120
ale v skutočnosti to všetko len koniec
up je variácia na tému.

8
00:00:20,120 --> 00:00:22,840
Tam naozaj sú títo
druh štyroch základných myšlienok

9
00:00:22,840 --> 00:00:25,190
že všetko ostatné môže sa redukuje na.

10
00:00:25,190 --> 00:00:28,150
Pole, spojové zoznamy,
hashovacie tabuľky, a snaží sa.

11
00:00:28,150 --> 00:00:30,720
A ako som povedal, že
sú variácie na nich,

12
00:00:30,720 --> 00:00:32,720
ale to je dosť
veľa ísť do zhrnúť

13
00:00:32,720 --> 00:00:38,140
všetko, čo budeme hovoriť
o v tejto triede, pokiaľ ide o C.

14
00:00:38,140 --> 00:00:40,140
>> Ale ako to všetko opatrenia hore, nie?

15
00:00:40,140 --> 00:00:44,265
Hovorili sme o výhodách a nevýhodách
každé v oddelených videa na nich,

16
00:00:44,265 --> 00:00:46,390
ale je tu veľa čísel
dostať hodená okolo.

17
00:00:46,390 --> 00:00:48,723
Je tu veľa všeobecné
myšlienky dostať hodená okolo.

18
00:00:48,723 --> 00:00:51,950
Skúsme a konsolidovať
že do jediného miesta.

19
00:00:51,950 --> 00:00:55,507
Poďme zvážiť výhody proti
sú nevýhody, a zvážiť

20
00:00:55,507 --> 00:00:57,340
čo štruktúra dát
môže byť tá pravá dát

21
00:00:57,340 --> 00:01:01,440
štruktúra pre vašu konkrétnu situáciu,
bez ohľadu na typ dát ste skladovania.

22
00:01:01,440 --> 00:01:06,625
Nemusíte nutne vždy nutné
použite super rýchle vloženie, vymazanie,

23
00:01:06,625 --> 00:01:10,761
a vyhľadávanie z trie, ak naozaj
sa nestarajú o vkladanie a mazanie

24
00:01:10,761 --> 00:01:11,260
Priveľa.

25
00:01:11,260 --> 00:01:13,968
Ak potrebujete len rýchlo náhodný
prístup, možno pole je lepšie.

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

27
00:01:15,340 --> 00:01:18,530
Poďme sa baviť o každej zo štyroch
hlavné druhy dátových štruktúr

28
00:01:18,530 --> 00:01:21,720
že sme hovorili o, a
jednoducho vidieť, kedy by mohol byť dobrý,

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

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

31
00:01:24,610 --> 00:01:27,300
Takže vloženie, že to trochu zlé.

32
00:01:27,300 --> 00:01:31,350
>> Vložený na konci poľa je v poriadku,
ak staviame celú radu, ako sme ísť.

33
00:01:31,350 --> 00:01:33,570
Ale ak budeme potrebovať vložiť
prvky do stredu,

34
00:01:33,570 --> 00:01:35,550
Spomeňte si na vloženie
triedenie, je tu veľa

35
00:01:35,550 --> 00:01:37,510
posúvanie, aby sa zmestili prvok tam.

36
00:01:37,510 --> 00:01:41,170
A tak, keď budeme vložiť
nikde inde než na konci poľa,

37
00:01:41,170 --> 00:01:43,590
že to asi nie je tak veľký.

38
00:01:43,590 --> 00:01:46,710
>> Podobne, mazanie, ak sme
mazanie od konca poľa,

39
00:01:46,710 --> 00:01:49,810
je asi tiež nie je tak skvelé, ak
nechceme nechať prázdne medzery,

40
00:01:49,810 --> 00:01:50,790
ktoré zvyčajne nemáme.

41
00:01:50,790 --> 00:01:54,700
Chceme odstrániť prvok, a
potom tak nejako, aby to znova pohodlný.

42
00:01:54,700 --> 00:01:57,670
A tak mazanie prvkov z
pole, tiež nie je tak veľký.

43
00:01:57,670 --> 00:01:58,820
>> Vyhľadávania, aj keď, je skvelá.

44
00:01:58,820 --> 00:02:00,920
Máme náhodný prístup,
konštantný čas vyhľadávania.

45
00:02:00,920 --> 00:02:03,800
Práve sme sa povedať, sedem, a pôjdeme
do poľa premiestnenie sedem.

46
00:02:03,800 --> 00:02:05,907
My hovoríme 20, s Choď na
array premiestnenie 20.

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

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

49
00:02:08,630 --> 00:02:11,020
>> Polia sú tiež relatívne ľahko triediť.

50
00:02:11,020 --> 00:02:14,040
Zakaždým, keď sme hovorili o triedení
algoritmus, ako je výber druhu,

51
00:02:14,040 --> 00:02:18,820
insertion sort, bublinkové radenie, zlúčiť
triedenie, sme vždy poľa, ako to urobiť,

52
00:02:18,820 --> 00:02:21,860
pretože pole sú celkom jednoduché
triedenie, vzhľadom k dátovej štruktúry

53
00:02:21,860 --> 00:02:22,970
sme doteraz videli.

54
00:02:22,970 --> 00:02:24,320
>> Sú to tiež pomerne malý.

55
00:02:24,320 --> 00:02:25,695
Tam nie je moc väčší priestor.

56
00:02:25,695 --> 00:02:29,210
Práve ste zrušil presne toľko, koľko
ako budete potrebovať držať vaše dáta,

57
00:02:29,210 --> 00:02:30,320
a to je do značnej miery to.

58
00:02:30,320 --> 00:02:33,180
Takže sú to celkom malé
a efektívne týmto spôsobom.

59
00:02:33,180 --> 00:02:36,000
Ale ďalšie nevýhodou, aj keď,
je to, že sú stanovené v veľkosť.

60
00:02:36,000 --> 00:02:38,630
Musíme priznať, ako presne
big chceme naše polia byť,

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

62
00:02:39,940 --> 00:02:41,280
Nemôžeme rast a zmenšiť ju.

63
00:02:41,280 --> 00:02:44,582
>> Ak potrebujeme pestovať alebo zmenšiť to, my
je potrebné vyhlásiť úplne nový rad,

64
00:02:44,582 --> 00:02:47,750
skopírujte všetky prvkov
Prvé pole do druhého poľa.

65
00:02:47,750 --> 00:02:51,410
A ak sa prepočítal, že
čas, musíme to urobiť znovu.

66
00:02:51,410 --> 00:02:52,760
Nie je to tak veľký.

67
00:02:52,760 --> 00:02:58,750
Takže pole nedávajú nám flexibilitu
mať variabilný počet prvkov.

68
00:02:58,750 --> 00:03:01,320
>> S Google zoznamu
vloženie je celkom jednoduché.

69
00:03:01,320 --> 00:03:03,290
Jednoducho sme pripnúť na prednej strane.

70
00:03:03,290 --> 00:03:04,892
Vypustenie je tiež celkom jednoduché.

71
00:03:04,892 --> 00:03:06,100
Musíme nájsť prvky.

72
00:03:06,100 --> 00:03:07,270
Ktoré sa týkajú nejaké vyhľadávanie.

73
00:03:07,270 --> 00:03:10,270
>> Ale akonáhle ste našli element
hľadáte, všetko, čo musíte urobiť vy

74
00:03:10,270 --> 00:03:12,830
Ak je zmeniť ukazovateľ,
možno dva, ak máte

75
00:03:12,830 --> 00:03:15,151
prepojené list-- dvojnásobne
spájať zoznam, rather--

76
00:03:15,151 --> 00:03:16,650
a potom stačí uvoľniť uzol.

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

78
00:03:18,399 --> 00:03:22,090
Tie stačí zmeniť dva ukazovatele,
tak to je celkom rýchly.

79
00:03:22,090 --> 00:03:23,470
>> Vyhľadávanie je zlé, že?

80
00:03:23,470 --> 00:03:26,280
Aby nám nájsť
prvok v Google zozname

81
00:03:26,280 --> 00:03:29,154
či už jednotlivo alebo dvakrát spojené,
musíme lineárne hľadať to.

82
00:03:29,154 --> 00:03:32,320
Musíme začať od začiatku a
presunúť na koniec, alebo začať na konci pohybu

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

84
00:03:33,860 --> 00:03:35,474
Nemáme náhodný prístup ešte.

85
00:03:35,474 --> 00:03:37,265
Takže ak Robíme
Veľa vyhľadávania, možno

86
00:03:37,265 --> 00:03:39,830
prepojeného zoznam nie je
až tak dobré pre nás.

87
00:03:39,830 --> 00:03:43,750
>> Sú tiež veľmi
ťažké triediť, že jo?

88
00:03:43,750 --> 00:03:45,666
Jediný spôsob, ako môžete
Naozaj triediť prepojeného zoznamu

89
00:03:45,666 --> 00:03:47,870
je triediť, ako ste si ju postaví.

90
00:03:47,870 --> 00:03:50,497
Ale ak si ho zoradiť ako vy
postaviť to, že ste už

91
00:03:50,497 --> 00:03:51,830
Vďaka rýchle vkladanie ešte.

92
00:03:51,830 --> 00:03:53,746
Nie ste len pripínanie
veci na prednej.

93
00:03:53,746 --> 00:03:55,710
Musíte nájsť
správne miesto, aby to,

94
00:03:55,710 --> 00:03:57,820
a potom sa vaše vloženie
stane sa len o tak zlé,

95
00:03:57,820 --> 00:03:59,390
ako vloženie do matice.

96
00:03:59,390 --> 00:04:03,130
Takže prepojené zoznamy nie sú
tak veľký pre triedenie dát.

97
00:04:03,130 --> 00:04:05,830
>> Sú tiež celkom malý, veľkosť-múdry.

98
00:04:05,830 --> 00:04:08,496
Dvojnásobne mierne spojené zoznam
väčšie ako jednotlivo previazané zoznamy,

99
00:04:08,496 --> 00:04:10,620
, Ktoré sú o niečo väčšie
ako pole, ale nie je to

100
00:04:10,620 --> 00:04:13,330
obrovské množstvo nevyužité miesto.

101
00:04:13,330 --> 00:04:18,730
Takže ak priestor je za vysokú cenu, ale
Nie je to naozaj intenzívne prémie,

102
00:04:18,730 --> 00:04:22,180
to môže byť tá správna cesta, ako ísť.

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

104
00:04:23,330 --> 00:04:25,850
Vloženie do hash tabuľky
je pomerne jednoduchá.

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

106
00:04:26,980 --> 00:04:30,700
Najprv je potrebné spustiť naše dáta prostredníctvom
funkcia hash získať hash kód,

107
00:04:30,700 --> 00:04:37,550
a potom vložíme prvok do
hash tabuľky v tomto hash kód Umiestnenie.

108
00:04:37,550 --> 00:04:40,879
>> Vypustenie, podobne ako Google zoznamu
je ľahké, akonáhle zistíte prvok.

109
00:04:40,879 --> 00:04:43,170
Musíte ju najprv nájsť,
ale potom, keď ho odstrániť,

110
00:04:43,170 --> 00:04:45,128
stačí vymeniť
pár ukazovateľov,

111
00:04:45,128 --> 00:04:47,250
ak používate samostatné reťazenie.

112
00:04:47,250 --> 00:04:49,942
Ak používate snímanie,
alebo ak si nie ste

113
00:04:49,942 --> 00:04:51,650
za použitia reťazenie vôbec
v hash tabuľke,

114
00:04:51,650 --> 00:04:53,040
vypustenie je vlastne rýchle.

115
00:04:53,040 --> 00:04:57,134
Všetko, čo musíte urobiť, je hash
dát, a potom ísť na dané miesto.

116
00:04:57,134 --> 00:04:58,925
A za predpokladu, že nie
máte nejaké kolízie,

117
00:04:58,925 --> 00:05:01,650
budete môcť veľmi rýchlo odstrániť.

118
00:05:01,650 --> 00:05:04,930
>> Teraz, vyhľadávanie je miesto, kde sa veci
trochu zložitejšie.

119
00:05:04,930 --> 00:05:06,910
To je v priemere lepšie
než spojových zoznamov.

120
00:05:06,910 --> 00:05:09,560
Ak používate zreťazenie,
stále máte prepojeného zoznamu,

121
00:05:09,560 --> 00:05:13,170
čo znamená, že stále majú
Hľadanie úkor prepojeného zoznamu.

122
00:05:13,170 --> 00:05:18,390
Ale pretože ste pri vašej spojenej
Zoznam a to rozdelenie viac ako 100 alebo 1000

123
00:05:18,390 --> 00:05:25,380
alebo n elementy vo vašom hash tabuľke, ste
spojové zoznamy sú jedným nth veľkosti.

124
00:05:25,380 --> 00:05:27,650
Všetci sú podstatne menšie.

125
00:05:27,650 --> 00:05:32,080
Ste n spojené zoznamy namiesto
jedného spojovaceho zoznamu veľkosti n.

126
00:05:32,080 --> 00:05:34,960
>> A tak to real-svet konštantný
faktorom, ktorý sme sa všeobecne

127
00:05:34,960 --> 00:05:39,730
nehovorí o v časovej zložitosti to,
robí v skutočnosti niečo zmeniť tu.

128
00:05:39,730 --> 00:05:43,020
Takže vyhľadávanie je stále lineárny
pozrite sa, či používate zreťazenie,

129
00:05:43,020 --> 00:05:46,780
ale dĺžka zoznamu
hľadáte prostredníctvom

130
00:05:46,780 --> 00:05:50,080
je veľmi, veľmi krátke porovnanie.

131
00:05:50,080 --> 00:05:52,995
Opäť platí, že ak je triedenie vašich
cieľom tu, hash tabuľky

132
00:05:52,995 --> 00:05:54,370
asi nie je správna cesta.

133
00:05:54,370 --> 00:05:56,830
Stačí použiť pole, ak triedenie
je pre vás naozaj dôležité.

134
00:05:56,830 --> 00:05:58,590
>> A môžu oscilujú veľkosti.

135
00:05:58,590 --> 00:06:01,640
Je ťažké povedať, či je
hash tabuľka je malý alebo veľký,

136
00:06:01,640 --> 00:06:04,110
pretože to naozaj záleží na
aký veľký je váš hash tabuľky je.

137
00:06:04,110 --> 00:06:07,340
Ak ste len bude uloženie
päť prvkov vo vašom hash tabuľky,

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

139
00:06:10,620 --> 00:06:12,614
ste pravdepodobne plytvanie veľa priestoru.

140
00:06:12,614 --> 00:06:15,030
Kontrast je tiež
majú veľmi kompaktný hash tabuľky,

141
00:06:15,030 --> 00:06:18,720
ale menšie vaše hash tabuľky dostane,
každej z týchto spojových zoznamov dlhšiu

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

143
00:06:19,220 --> 00:06:22,607
A tak tam naozaj žiadny spôsob, ako definovať
presne veľkosť hash tabuľky,

144
00:06:22,607 --> 00:06:24,440
ale to je pravdepodobne bezpečné
hovoriť, že je to všeobecne

145
00:06:24,440 --> 00:06:27,990
Bude väčší ako pripojený
Zoznam ukladanie rovnaké dáta,

146
00:06:27,990 --> 00:06:30,400
ale menšie ako trie.

147
00:06:30,400 --> 00:06:32,720
>> A snaží sa o štvrtú
z týchto štruktúr

148
00:06:32,720 --> 00:06:34,070
že sme hovorili o.

149
00:06:34,070 --> 00:06:36,450
Vkladanie do trie je zložitý.

150
00:06:36,450 --> 00:06:38,400
Je tu veľa dynamický
alokácie pamäti,

151
00:06:38,400 --> 00:06:40,780
najmä na začiatku,
ako ste začínajú stavať.

152
00:06:40,780 --> 00:06:43,700
Ale je to konštantná čas.

153
00:06:43,700 --> 00:06:47,690
Je to len ľudský element
tu, že robí to zložitejšie.

154
00:06:47,690 --> 00:06:53,250
S stretnúť ukazovatele null, malloc
priestor, tam, možno malloc priestor

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

156
00:06:54,490 --> 00:06:58,880
Druh zastrašovania faktora
ukazovatele v dynamického prideľovanie pamäte

157
00:06:58,880 --> 00:07:00,130
je prekážka zmizne.

158
00:07:00,130 --> 00:07:04,550
Ale akonáhle ste ju prečítal, vkladanie
vlastne príde celkom jednoduché,

159
00:07:04,550 --> 00:07:06,810
a to iste je konštantná čas.

160
00:07:06,810 --> 00:07:07,680
>> Mazanie je ľahké.

161
00:07:07,680 --> 00:07:11,330
Všetko, čo musíte urobiť, je pohybovať dole
niekoľko ukazovateľov a voľného uzla,

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

163
00:07:12,420 --> 00:07:13,930
Vyhľadávanie je tiež veľmi rýchly.

164
00:07:13,930 --> 00:07:16,780
Je to len na základe
Dĺžka vašich dát.

165
00:07:16,780 --> 00:07:19,924
Takže ak všetky vaše dáta je
päť reťazca znakov,

166
00:07:19,924 --> 00:07:22,590
Napríklad, že ste ukladanie päť
reťazce znakov vo vašom trie,

167
00:07:22,590 --> 00:07:25,439
to trvá len päť krokov na
nájsť to, čo hľadáte.

168
00:07:25,439 --> 00:07:28,480
Five je len konštantný faktor, tak
Znova, vkladanie, mazanie a vyhľadávanie

169
00:07:28,480 --> 00:07:31,670
Tu sú všetky konštantné čas, efektívne.

170
00:07:31,670 --> 00:07:34,880
>> Ďalšia vec je, že vaše trie je
vlastne druh už je zoradený, že jo?

171
00:07:34,880 --> 00:07:36,800
Na základe toho, ako sme
vkladanie prvkov,

172
00:07:36,800 --> 00:07:40,060
tým, že ide písmeno listom z
kľúč, alebo po jednotlivých čísliciach kľúče,

173
00:07:40,060 --> 00:07:45,084
typicky Vaša trie skončí ako
druh radené, ako si ho postaviť.

174
00:07:45,084 --> 00:07:47,250
To nie je naozaj robí
zmysel premýšľať o tom, triedenie

175
00:07:47,250 --> 00:07:49,874
Rovnakým spôsobom si myslíme, že o
to s poli, alebo previazané zoznamy,

176
00:07:49,874 --> 00:07:51,070
alebo hashovacie tabuľky.

177
00:07:51,070 --> 00:07:54,780
Ale v istom zmysle, vaše
Trie je radený as you go.

178
00:07:54,780 --> 00:07:58,630
>> Nevýhodou však je, že
Trie rýchlo stáva obrovský.

179
00:07:58,630 --> 00:08:02,970
Z každého križovatke, môžete
have-- ak váš kľúč sa skladá z číslic,

180
00:08:02,970 --> 00:08:04,880
máte 10 ďalších
miesta, môžete ísť, čo

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

182
00:08:07,490 --> 00:08:11,440
o dátach, ktoré chcete uložiť
v tomto uzle, plus 10 ukazovateľov.

183
00:08:11,440 --> 00:08:14,430
Čo, na CS50 IDE, je 80 bytov.

184
00:08:14,430 --> 00:08:17,220
Takže to je aspoň 80 bajtov pre
každý uzol, ktorý vytvoríte,

185
00:08:17,220 --> 00:08:19,240
a to ani počítanie dáta.

186
00:08:19,240 --> 00:08:24,950
A ak vaše uzly
listy miesto číslic,

187
00:08:24,950 --> 00:08:27,825
Teraz máte 26 ukazovatele
z každého miesta.

188
00:08:27,825 --> 00:08:32,007
A 26 krát 8 je asi 200
bajtov, alebo niečo také.

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
vidieť, kam idem s tým, že jo?

191
00:08:35,381 --> 00:08:37,500
Vaša uzly môže dostať naozaj
veľký, a tak trie

192
00:08:37,500 --> 00:08:40,470
sám, celkovo môže
naozaj veľká, taky.

193
00:08:40,470 --> 00:08:42,630
Takže ak priestor je za vysokú
prémie na vašom systéme,

194
00:08:42,630 --> 00:08:45,830
Trie nemusí byť správny spôsob, ako
ísť, aj keď jeho ďalšie výhody

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

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

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

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