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

2
00:00:05,259 --> 00:00:08,300
Doug LLOYD: Torej, v CS50, smo iz
veliko različnih podatkovnih struktur,

3
00:00:08,300 --> 00:00:09,180
prav?

4
00:00:09,180 --> 00:00:11,420
Smo videli nizi in povezana
Seznami in hash tabele,

5
00:00:11,420 --> 00:00:15,210
in poskuša, skladi in vrste.

6
00:00:15,210 --> 00:00:17,579
Bomo naučili tudi malo
o drevesih in kupe,

7
00:00:17,579 --> 00:00:20,120
ampak res vsi ti šele na koncu
up pa variacije na temo.

8
00:00:20,120 --> 00:00:22,840
Res so ti
nekako štiri osnovne zamisli

9
00:00:22,840 --> 00:00:25,190
da je vse ostalo lahko zavre navzdol.

10
00:00:25,190 --> 00:00:28,150
Nizi, povezani seznami,
hash tabele, in poskuša.

11
00:00:28,150 --> 00:00:30,720
In kot sem rekel, ni
so variacije na njih,

12
00:00:30,720 --> 00:00:32,720
vendar je to zelo
veliko dogaja povzeti

13
00:00:32,720 --> 00:00:38,140
vse, kar bomo govorili
približno v tem razredu v smislu C.

14
00:00:38,140 --> 00:00:40,140
>> Ampak, kako ti vse ukrep gor, kajne?

15
00:00:40,140 --> 00:00:44,265
Mi smo se pogovarjali o prednostih in slabostih
vsakega v ločenih video posnetke na njih,

16
00:00:44,265 --> 00:00:46,390
ampak tam je veliko številk
pridobivanje vrže okrog.

17
00:00:46,390 --> 00:00:48,723
Tam je veliko splošno
misli pridobivanje vrže okrog.

18
00:00:48,723 --> 00:00:51,950
Poskusimo in utrditi
je v samo enem mestu.

19
00:00:51,950 --> 00:00:55,507
Oglejmo pretehtati prednosti pred
zaporniki, in menijo,

20
00:00:55,507 --> 00:00:57,340
ki je struktura podatkov
je lahko zgodilo podatki

21
00:00:57,340 --> 00:01:01,440
struktura za določeno situacijo,
ne glede na vrsto podatkov, ki ste shranjevanje.

22
00:01:01,440 --> 00:01:06,625
Saj ni nujno, da je vedno treba
uporabiti super hitro insercijo, delecijo

23
00:01:06,625 --> 00:01:10,761
in iskanje za trie, če vas res
ne skrbi, vstavljanje in brisanje

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

25
00:01:11,260 --> 00:01:13,968
Če potrebujete le hitro naključno
dostop, morda niz je bolje.

26
00:01:13,968 --> 00:01:15,340
Torej, kaj je destilirati, da.

27
00:01:15,340 --> 00:01:18,530
Spregovorimo o vsakem od štirih
glavne vrste podatkovnih struktur

28
00:01:18,530 --> 00:01:21,720
da smo se pogovarjali o tem, in
Samo glej, ko bi jih bilo dobro,

29
00:01:21,720 --> 00:01:23,340
in če ne bi bilo tako dobro.

30
00:01:23,340 --> 00:01:24,610
Torej začnimo z nizi.

31
00:01:24,610 --> 00:01:27,300
Torej vstavitev, ki je nekako slabo.

32
00:01:27,300 --> 00:01:31,350
>> Vstavitev konec matrike je v redu,
če gradimo paleto, kot gremo.

33
00:01:31,350 --> 00:01:33,570
Ampak, če bomo morali vstaviti
elementi v sredini,

34
00:01:33,570 --> 00:01:35,550
pomislite na vstavljanje
razvrščanje, tam je veliko

35
00:01:35,550 --> 00:01:37,510
spreminjajočih se prilega element tam.

36
00:01:37,510 --> 00:01:41,170
In tako, če bomo vstavite
kjerkoli, ampak konec array,

37
00:01:41,170 --> 00:01:43,590
da to verjetno ni tako velika.

38
00:01:43,590 --> 00:01:46,710
>> Podobno, izbris, če smo
brisanje od konca matrike,

39
00:01:46,710 --> 00:01:49,810
je verjetno tudi ni tako velik, če
ne želimo pustiti prazne vrzeli,

40
00:01:49,810 --> 00:01:50,790
ki običajno ne bomo.

41
00:01:50,790 --> 00:01:54,700
Želimo, da odstranite element, in
potem nekako bi bilo spet Topel.

42
00:01:54,700 --> 00:01:57,670
In tako brisanju elementov iz
niz, tudi ni tako velika.

43
00:01:57,670 --> 00:01:58,820
>> Iskanje, čeprav je super.

44
00:01:58,820 --> 00:02:00,920
Imamo naključni dostop,
stalen čas lookup.

45
00:02:00,920 --> 00:02:03,800
Pravkar smo rekli, sedem, in gremo
za matrične premestitev sedem.

46
00:02:03,800 --> 00:02:05,907
Pravimo, 20, z pojdite na
Niz premestitev 20.

47
00:02:05,907 --> 00:02:07,240
Nimamo za čez Ponovil.

48
00:02:07,240 --> 00:02:08,630
To je zelo dobro.

49
00:02:08,630 --> 00:02:11,020
>> Polja so tudi relativno enostavno rešiti.

50
00:02:11,020 --> 00:02:14,040
Vsakič, ko smo se pogovarjali o sortiranju
algoritem, kot izbirnega vrste,

51
00:02:14,040 --> 00:02:18,820
Vstavitev vrste, mehurček razvrstite, združiti
nekako smo vedno uporablja nize, da to storite,

52
00:02:18,820 --> 00:02:21,860
ker so nizi zelo enostavno
sortiranje, relativno glede na podatkovne strukture

53
00:02:21,860 --> 00:02:22,970
smo videli doslej.

54
00:02:22,970 --> 00:02:24,320
>> Oni so tudi relativno majhna.

55
00:02:24,320 --> 00:02:25,695
Tam ni veliko dodatnega prostora.

56
00:02:25,695 --> 00:02:29,210
Pravkar ste v prahi natanko toliko
kot ga potrebujete, da imajo svoje podatke,

57
00:02:29,210 --> 00:02:30,320
in to je precej, da.

58
00:02:30,320 --> 00:02:33,180
Torej, oni so precej majhna
in učinkovito na ta način.

59
00:02:33,180 --> 00:02:36,000
Ampak ena negativna, čeprav,
je, da so določeni v velikosti.

60
00:02:36,000 --> 00:02:38,630
Imamo točno izjavi, kako
big želimo naša matrika biti,

61
00:02:38,630 --> 00:02:39,940
in smo dobili le en strel na njo.

62
00:02:39,940 --> 00:02:41,280
Mi ne more rasti in psihiater.

63
00:02:41,280 --> 00:02:44,582
>> Če bomo potrebovali, da raste ali skrči jo imamo
morali razglasiti povsem novo paleto,

64
00:02:44,582 --> 00:02:47,750
kopiranje vseh elementov
Prvi niz v drugega zaporedja.

65
00:02:47,750 --> 00:02:51,410
In če smo se uštel, da
Čas, moramo to storiti še enkrat.

66
00:02:51,410 --> 00:02:52,760
Ni tako velika.

67
00:02:52,760 --> 00:02:58,750
Torej, nizi nam ne daje prožnost
da ima spremenljivo število elementov.

68
00:02:58,750 --> 00:03:01,320
>> Z povezanega seznama,
Vstavitev je zelo enostavno.

69
00:03:01,320 --> 00:03:03,290
Pravkar smo prečenje na sprednji strani.

70
00:03:03,290 --> 00:03:04,892
Izbris je tudi precej enostavno.

71
00:03:04,892 --> 00:03:06,100
Moramo najti elemente.

72
00:03:06,100 --> 00:03:07,270
To vključuje nekaj iskanja.

73
00:03:07,270 --> 00:03:10,270
>> Ampak, ko ste našli element
iščete, vse, kar morate storiti

74
00:03:10,270 --> 00:03:12,830
je spremeniti kazalec,
morda dve, če imate

75
00:03:12,830 --> 00:03:15,151
vezavni list-- dvakrat
povezani seznam, rather--

76
00:03:15,151 --> 00:03:16,650
in potem si lahko samo sprostite vozlišče.

77
00:03:16,650 --> 00:03:18,399
Nimate za premik
vse okoli.

78
00:03:18,399 --> 00:03:22,090
Pravkar ste spremenili dveh kazalcev,
tako da je precej hitro.

79
00:03:22,090 --> 00:03:23,470
>> Iskanje je slabo, čeprav, kajne?

80
00:03:23,470 --> 00:03:26,280
Da bi za nas, da bi našli
element povezan seznamu

81
00:03:26,280 --> 00:03:29,154
ali enkrat ali dvakrat povezana,
moramo linearna ga iščete.

82
00:03:29,154 --> 00:03:32,320
Moramo začeti na začetku in
premaknite konec, ali začeti na koncu poti

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

84
00:03:33,860 --> 00:03:35,474
Nimamo naključni dostop več.

85
00:03:35,474 --> 00:03:37,265
Torej, če smo početje
veliko iskanja, morda

86
00:03:37,265 --> 00:03:39,830
vezavni seznam ni
tako zelo dobro za nas.

87
00:03:39,830 --> 00:03:43,750
>> Oni so tudi v resnici
težko razvrstiti, kajne?

88
00:03:43,750 --> 00:03:45,666
Edini način, da lahko
Res razvrstiti povezanega seznama

89
00:03:45,666 --> 00:03:47,870
je, da ga rešiti, kot jo zgraditi.

90
00:03:47,870 --> 00:03:50,497
Ampak, če ste ga rešiti, kot ste
zgraditi jo, nisi več

91
00:03:50,497 --> 00:03:51,830
kar hitro vstavljanje več.

92
00:03:51,830 --> 00:03:53,746
Nisi samo prečenjem
stvari na sprednji strani.

93
00:03:53,746 --> 00:03:55,710
Moraš najti
pravem mestu, da ga proda,

94
00:03:55,710 --> 00:03:57,820
in potem vaš vstavljanje
postane skoraj tako slab

95
00:03:57,820 --> 00:03:59,390
kot vstavite v array.

96
00:03:59,390 --> 00:04:03,130
Torej, povezani seznami niso
tako super za sortiranje podatkov.

97
00:04:03,130 --> 00:04:05,830
>> Oni so tudi zelo majhne, ​​velikost-pametno.

98
00:04:05,830 --> 00:04:08,496
Dvakrat povezani seznam nekoliko
večja kot posamično povezanih seznamov,

99
00:04:08,496 --> 00:04:10,620
ki so nekoliko večje
kot nizi, vendar to ni

100
00:04:10,620 --> 00:04:13,330
ogromno zapravili prostora.

101
00:04:13,330 --> 00:04:18,730
Torej, če je prostor na premijo, vendar
ni res intenzivna premium,

102
00:04:18,730 --> 00:04:22,180
to je lahko prava pot.

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

104
00:04:23,330 --> 00:04:25,850
Vstavljanje v hash tabelo
je dokaj enostavna.

105
00:04:25,850 --> 00:04:26,980
To je dvostopenjski postopek.

106
00:04:26,980 --> 00:04:30,700
Najprej moramo teči naše podatke preko
funkcija hash, da bi dobili kodo razpršitve,

107
00:04:30,700 --> 00:04:37,550
in potem vstavimo elementa v
hash tabela na tej hash kode lokacije.

108
00:04:37,550 --> 00:04:40,879
>> Izbris, podobno povezani seznam,
je enostavno, ko boste našli element.

109
00:04:40,879 --> 00:04:43,170
Moraš najprej najti,
ampak potem ko ga izbrisati,

110
00:04:43,170 --> 00:04:45,128
morate samo za izmenjavo
Nekaj ​​nasvetov,

111
00:04:45,128 --> 00:04:47,250
če uporabljate ločeno veriženje.

112
00:04:47,250 --> 00:04:49,942
Če uporabljate sondiranje,
ali če niste

113
00:04:49,942 --> 00:04:51,650
uporablja verižni sploh
V vašem hash tabele,

114
00:04:51,650 --> 00:04:53,040
Črtanje je pravzaprav zelo preprost.

115
00:04:53,040 --> 00:04:57,134
Vse, kar morate storiti, je razpršitev
podatkov, nato pa pojdite na to lokacijo.

116
00:04:57,134 --> 00:04:58,925
In ob predpostavki, da ne
imate trčenja,

117
00:04:58,925 --> 00:05:01,650
boste lahko zelo hitro izbrisati.

118
00:05:01,650 --> 00:05:04,930
>> Zdaj, lookup je, če stvari
dobili malo bolj zapletena.

119
00:05:04,930 --> 00:05:06,910
To je v povprečju bolje
kot povezanih seznamov.

120
00:05:06,910 --> 00:05:09,560
Če uporabljate verižni,
imate še vedno povezani seznam,

121
00:05:09,560 --> 00:05:13,170
kar pomeni, da še vedno imajo
Iskanje oškodovanje povezanega seznama.

122
00:05:13,170 --> 00:05:18,390
Ampak zato, ker ste ob vaš povezano
seznam in ga razdelite čez 100 ali 1000

123
00:05:18,390 --> 00:05:25,380
ali n elementi v vašem hash tabele, ste
povezani seznami so vsi ena n velikosti.

124
00:05:25,380 --> 00:05:27,650
Oni so vsi bistveno manjši.

125
00:05:27,650 --> 00:05:32,080
Da ste n namesto povezane sezname
enega povezanega seznama velikosti n.

126
00:05:32,080 --> 00:05:34,960
>> In tako je to v realnem svetu konstanta
dejavnik, ki smo na splošno

127
00:05:34,960 --> 00:05:39,730
Ne govori o časovnih zahtevnosti ga,
pa dejansko narediti razliko tukaj.

128
00:05:39,730 --> 00:05:43,020
Tako iskanje je še vedno linearna
iskanje če uporabljate verižni,

129
00:05:43,020 --> 00:05:46,780
vendar je dolžina seznama
iščete s pomočjo

130
00:05:46,780 --> 00:05:50,080
Zelo, zelo kratek v primerjavi.

131
00:05:50,080 --> 00:05:52,995
Še enkrat, če sortiranje je vaša
cilj tukaj, razpršena tabela je

132
00:05:52,995 --> 00:05:54,370
verjetno ni prava pot.

133
00:05:54,370 --> 00:05:56,830
Samo uporabite array če sortiranje
je zelo pomembno za vas.

134
00:05:56,830 --> 00:05:58,590
>> In lahko se spreminjajo velikosti.

135
00:05:58,590 --> 00:06:01,640
Težko je reči, ali je
hash tabela je majhna ali velika,

136
00:06:01,640 --> 00:06:04,110
ker je res odvisno od
kako velik je vaš hash tabela.

137
00:06:04,110 --> 00:06:07,340
Če ste šele tekoč, da bo shranjevanje
pet elementov v vašem hash tabele,

138
00:06:07,340 --> 00:06:10,620
in imate razpršene tabele
s 10.000 elementi v njej,

139
00:06:10,620 --> 00:06:12,614
ste verjetno izgubljamo veliko prostora.

140
00:06:12,614 --> 00:06:15,030
Kontrast vam pa lahko tudi
imajo zelo kompaktnih hash tabele,

141
00:06:15,030 --> 00:06:18,720
vendar manjša vaš hash tabela dobi,
daljša vsaka od teh povezanih seznamov

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

143
00:06:19,220 --> 00:06:22,607
In tako je res ni način, da se opredelijo
ravno velikost hash tabele,

144
00:06:22,607 --> 00:06:24,440
ampak to je verjetno varno
reči, da je v splošnem

145
00:06:24,440 --> 00:06:27,990
bo večja kot povezan
Seznam shranjevanje enake podatke,

146
00:06:27,990 --> 00:06:30,400
vendar manjše od trie.

147
00:06:30,400 --> 00:06:32,720
>> In poskuša so četrti
teh struktur

148
00:06:32,720 --> 00:06:34,070
da smo se pogovarjali o tem.

149
00:06:34,070 --> 00:06:36,450
Vstavljanje v Trie je zapleten.

150
00:06:36,450 --> 00:06:38,400
Tam je veliko dinamično
dodeljevanje pomnilnika,

151
00:06:38,400 --> 00:06:40,780
zlasti na začetku,
kot ste začeli graditi.

152
00:06:40,780 --> 00:06:43,700
Ampak to je konstanta čas.

153
00:06:43,700 --> 00:06:47,690
To je le človeški element
tukaj, zaradi česar je težavno.

154
00:06:47,690 --> 00:06:53,250
Ob srečujejo null kazalec, malloc
prostor, tja, morda malloc prostor

155
00:06:53,250 --> 00:06:54,490
od tam spet.

156
00:06:54,490 --> 00:06:58,880
Neke vrste ustrahovanja faktorjem
kazalci v dinamično dodeljevanje pomnilnika

157
00:06:58,880 --> 00:07:00,130
je ovira za počistiti.

158
00:07:00,130 --> 00:07:04,550
Ampak, ko ste jo izbil, vstavljanje
pravzaprav je precej preprost,

159
00:07:04,550 --> 00:07:06,810
in gotovo je konstantna čas.

160
00:07:06,810 --> 00:07:07,680
>> Izbris je enostavno.

161
00:07:07,680 --> 00:07:11,330
Vse kar morate storiti je, pluti navzdol
Nekaj ​​kazalcev in prosti vozlišča,

162
00:07:11,330 --> 00:07:12,420
tako da je zelo dober.

163
00:07:12,420 --> 00:07:13,930
Iskanje je tudi precej hitro.

164
00:07:13,930 --> 00:07:16,780
To temelji le na
dolžina vaših podatkov.

165
00:07:16,780 --> 00:07:19,924
Torej, če vse vaše podatke, je
pet nizi znakov,

166
00:07:19,924 --> 00:07:22,590
na primer, ste shranjevanje pet
nizi znakov v vašem Trie,

167
00:07:22,590 --> 00:07:25,439
je samo pet korakov do
našli tisto, kar iščete.

168
00:07:25,439 --> 00:07:28,480
Pet je le konstanten faktor, tako
še enkrat, vstavljanje, brisanje in iskanje

169
00:07:28,480 --> 00:07:31,670
Tukaj so vsi konstantni čas, učinkovito.

170
00:07:31,670 --> 00:07:34,880
>> Druga stvar je, da je vaša trie
pravzaprav nekako že razporejene, kajne?

171
00:07:34,880 --> 00:07:36,800
V skladu s tem, kako smo
vstavljanje elementi,

172
00:07:36,800 --> 00:07:40,060
ki ga bo pismo z dopisom od
Ključ ali števka ključa,

173
00:07:40,060 --> 00:07:45,084
Značilno je, da vaš trie konča pa
nekako razporejene kot jo gradijo.

174
00:07:45,084 --> 00:07:47,250
To ni res naredi
Občutek, da razmišljajo o sortiranje

175
00:07:47,250 --> 00:07:49,874
na enak način razmišljamo o
je z nizi ali povezanih seznamov,

176
00:07:49,874 --> 00:07:51,070
ali hash tabele.

177
00:07:51,070 --> 00:07:54,780
Toda v nekem smislu, vaša
trie je razvrščen kot greš.

178
00:07:54,780 --> 00:07:58,630
>> Slaba stran je seveda, da je
trie hitro postane velik.

179
00:07:58,630 --> 00:08:02,970
Iz vsake stični točki, boste morda
have-- če vaš ključ je sestavljen iz številk,

180
00:08:02,970 --> 00:08:04,880
imate 10 drugih
krajev, lahko greš, ki

181
00:08:04,880 --> 00:08:07,490
pomeni, da je vsako vozlišče
vsebuje informacije

182
00:08:07,490 --> 00:08:11,440
o podatkih, ki jih želite shraniti
v tistem vozlišču, plus 10 kazalcev.

183
00:08:11,440 --> 00:08:14,430
Ki na CS50 IDE, je 80 bajtov.

184
00:08:14,430 --> 00:08:17,220
Torej, to je najmanj 80 bajtov za
vsako vozlišče, ki ga ustvarjajo,

185
00:08:17,220 --> 00:08:19,240
in da je niti ne računam podatkov.

186
00:08:19,240 --> 00:08:24,950
In če so vaši vozlišča
črke namesto številk,

187
00:08:24,950 --> 00:08:27,825
Zdaj imate 26 kazalcev
iz vsake lokacije.

188
00:08:27,825 --> 00:08:32,007
In 26-krat 8 je verjetno 200
bajte, ali nekaj takega.

189
00:08:32,007 --> 00:08:33,840
In imaš kapital
in vam lowercase-- lahko

190
00:08:33,840 --> 00:08:35,381
vidite, kam grem s tem, kajne?

191
00:08:35,381 --> 00:08:37,500
Vaši vozlišča lahko dobite res
velika, zato je trie

192
00:08:37,500 --> 00:08:40,470
sam na splošno, lahko
zares veliko, preveč.

193
00:08:40,470 --> 00:08:42,630
Torej, če je prostor na visoko
Premija na vašem sistemu,

194
00:08:42,630 --> 00:08:45,830
trie morda ni pravi način za
iti, čeprav njegove druge ugodnosti

195
00:08:45,830 --> 00:08:47,780
pridejo v poštev.

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

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

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