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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: So in CS50, ons het gedek
'n baie verskillende data strukture,

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

4
00:00:09,180 --> 00:00:11,420
Ons het gesien skikkings, en gekoppel
lyste, en hash tabelle,

5
00:00:11,420 --> 00:00:15,210
en drieë, stapels en toue.

6
00:00:15,210 --> 00:00:17,579
Ons sal ook leer 'n bietjie
oor bome en hope,

7
00:00:17,579 --> 00:00:20,120
maar regtig al hierdie dinge net die einde
up om variasies op 'n tema.

8
00:00:20,120 --> 00:00:22,840
Daar is regtig hierdie
soort vier basiese idees

9
00:00:22,840 --> 00:00:25,190
dat alles anders kan neerkom op.

10
00:00:25,190 --> 00:00:28,150
Skikkings, geskakelde lyste,
hash tabelle, en drieë gedruk.

11
00:00:28,150 --> 00:00:30,720
En soos ek gesê het, is daar
variasies op hulle,

12
00:00:30,720 --> 00:00:32,720
maar dit is mooi
veel gaan om op te som

13
00:00:32,720 --> 00:00:38,140
alles wat ons gaan om te praat
oor in hierdie klas in terme van C.

14
00:00:38,140 --> 00:00:40,140
>> Maar hoe doen hulle almal meet aan, reg?

15
00:00:40,140 --> 00:00:44,265
Ons het gepraat oor die voor- en nadele
van elke in afsonderlike video's op hulle

16
00:00:44,265 --> 00:00:46,390
maar daar is 'n baie van die nommers
kry gegooi rond.

17
00:00:46,390 --> 00:00:48,723
Daar is 'n baie algemene
gedagtes kry gegooi rond.

18
00:00:48,723 --> 00:00:51,950
Kom ons probeer en te konsolideer
dit in net een plek.

19
00:00:51,950 --> 00:00:55,507
Kom ons weeg die voor-teen
die nadele en oorweeg

20
00:00:55,507 --> 00:00:57,340
wat data struktuur
dalk die regte data wees

21
00:00:57,340 --> 00:01:01,440
struktuur vir jou spesifieke situasie,
watter soort data wat jy stoor.

22
00:01:01,440 --> 00:01:06,625
Jy hoef nie noodwendig hoef te
gebruik die super vinnige inplanting, skrap,

23
00:01:06,625 --> 00:01:10,761
en lookup van 'n Trie as jy regtig
nie omgee invoeging en verwydering

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

25
00:01:11,260 --> 00:01:13,968
As jy net nodig het vinnig ewekansige
toegang, miskien 'n skikking is beter.

26
00:01:13,968 --> 00:01:15,340
So laat distilleer dit.

27
00:01:15,340 --> 00:01:18,530
Kom ons praat oor elk van die vier
groot soorte data strukture

28
00:01:18,530 --> 00:01:21,720
wat ons het gepraat oor, en
net sien wanneer hulle goed kan wees,

29
00:01:21,720 --> 00:01:23,340
en wanneer hulle dalk nie so goed nie.

30
00:01:23,340 --> 00:01:24,610
So laat ons begin met skikkings.

31
00:01:24,610 --> 00:01:27,300
So inplanting, dit is soort van slegte.

32
00:01:27,300 --> 00:01:31,350
>> Invoeging aan die einde van 'n skikking is OK,
As ons bou 'n skikking soos ons gaan.

33
00:01:31,350 --> 00:01:33,570
Maar as ons nodig het om te voeg
elemente in die middel,

34
00:01:33,570 --> 00:01:35,550
dink terug aan invoeging
soort, daar is 'n baie

35
00:01:35,550 --> 00:01:37,510
van die verskuiwing van 'n element inpas daar.

36
00:01:37,510 --> 00:01:41,170
En so as ons gaan om in te voeg
oral, maar die einde van 'n skikking,

37
00:01:41,170 --> 00:01:43,590
dit is waarskynlik nie so groot.

38
00:01:43,590 --> 00:01:46,710
>> Net so, skrap, tensy ons
verwydering van die einde van 'n skikking,

39
00:01:46,710 --> 00:01:49,810
is waarskynlik ook nie so 'n groot as
Ons wil nie leë gapings te verlaat,

40
00:01:49,810 --> 00:01:50,790
wat gewoonlik doen ons nie.

41
00:01:50,790 --> 00:01:54,700
Ons wil 'n element te verwyder, en
dan soort van te maak dit weer knus.

42
00:01:54,700 --> 00:01:57,670
En so die verwydering van elemente
'n skikking, ook nie so groot.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, al is, is groot.

44
00:01:58,820 --> 00:02:00,920
Ons het ewetoeganklike,
konstante tyd lookup.

45
00:02:00,920 --> 00:02:03,800
Ons sê net sewe, en ons gaan
om verskeidenheid hervestiging sewe.

46
00:02:03,800 --> 00:02:05,907
Ons sê 20, met Go om
verskeidenheid hervestiging 20.

47
00:02:05,907 --> 00:02:07,240
Ons hoef nie te oor Itereer.

48
00:02:07,240 --> 00:02:08,630
Dit is redelik goed.

49
00:02:08,630 --> 00:02:11,020
>> Skikkings is ook relatief maklik om te sorteer.

50
00:02:11,020 --> 00:02:14,040
Elke keer as ons gepraat oor 'n sortering
algoritme, soos seleksie soort,

51
00:02:14,040 --> 00:02:18,820
invoeging soort, borrelsortering, saamsmelt
sorteer, het ons altyd gebruik skikkings om dit te doen,

52
00:02:18,820 --> 00:02:21,860
omdat skikkings is redelik maklik om te
soort, relatief tot die data strukture

53
00:02:21,860 --> 00:02:22,970
ons het tot dusver gesien het.

54
00:02:22,970 --> 00:02:24,320
>> Hulle is ook relatief klein.

55
00:02:24,320 --> 00:02:25,695
Daar is nie 'n baie ekstra ruimte.

56
00:02:25,695 --> 00:02:29,210
Jy stel net opsy presies soveel
as jy nodig het om jou data te hou,

57
00:02:29,210 --> 00:02:30,320
en dit is pretty much dit.

58
00:02:30,320 --> 00:02:33,180
So hulle is redelik klein
en doeltreffende op dié manier.

59
00:02:33,180 --> 00:02:36,000
Maar 'n ander nadeel, al is,
is dat hulle vaste grootte.

60
00:02:36,000 --> 00:02:38,630
Ons het presies verklaar hoe
groot wil ons ons verskeidenheid te wees,

61
00:02:38,630 --> 00:02:39,940
en ons kry net een skoot op dit.

62
00:02:39,940 --> 00:02:41,280
Ons kan nie groei en krimp dit.

63
00:02:41,280 --> 00:02:44,582
>> As ons nodig het om te groei of krimp dit, ons
nodig om 'n heeltemal nuwe reeks te verklaar,

64
00:02:44,582 --> 00:02:47,750
kopieer al die elemente van die
eerste reeks in die tweede skikking.

65
00:02:47,750 --> 00:02:51,410
En as ons misreken dat
tyd, moet ons dit weer doen.

66
00:02:51,410 --> 00:02:52,760
Nie so groot.

67
00:02:52,760 --> 00:02:58,750
So skikkings nie gee ons die buigsaamheid
veranderlike getalle elemente.

68
00:02:58,750 --> 00:03:01,320
>> Met 'n geskakelde lys,
invoeging is redelik maklik.

69
00:03:01,320 --> 00:03:03,290
Ons ryg net op die voorkant.

70
00:03:03,290 --> 00:03:04,892
Skrap is ook redelik maklik.

71
00:03:04,892 --> 00:03:06,100
Ons het aan die elemente te vind.

72
00:03:06,100 --> 00:03:07,270
Dit behels 'n soek.

73
00:03:07,270 --> 00:03:10,270
>> Maar sodra jy die element het gevind
jy soek, al wat jy hoef te doen

74
00:03:10,270 --> 00:03:12,830
is verander 'n wyser,
moontlik twee as jy

75
00:03:12,830 --> 00:03:15,151
'n gekoppelde list-- n dubbel
geskakelde lys, rather--

76
00:03:15,151 --> 00:03:16,650
en dan kan jy net vry om die knoop.

77
00:03:16,650 --> 00:03:18,399
Jy hoef nie te skuif
alles rondom.

78
00:03:18,399 --> 00:03:22,090
Jy verander net twee wysers,
so dit is redelik vinnig.

79
00:03:22,090 --> 00:03:23,470
>> Lookup is sleg al is, reg?

80
00:03:23,470 --> 00:03:26,280
Ten einde vir ons om 'n te vind
element in 'n geskakelde lys,

81
00:03:26,280 --> 00:03:29,154
of een-een of dubbel gekoppel,
ons moet lineêre soek nie.

82
00:03:29,154 --> 00:03:32,320
Ons moet begin by die begin en
beweeg die einde, of begin aan die einde skuif

83
00:03:32,320 --> 00:03:33,860
na die begin.

84
00:03:33,860 --> 00:03:35,474
Ons het nie ewetoeganklike meer nie.

85
00:03:35,474 --> 00:03:37,265
So as ons 'n doen
baie soek, miskien

86
00:03:37,265 --> 00:03:39,830
'n geskakelde lys is nie
heeltemal so goed vir ons.

87
00:03:39,830 --> 00:03:43,750
>> Hulle is ook baie
moeilik om te sorteer, reg?

88
00:03:43,750 --> 00:03:45,666
Die enigste manier wat jy kan
regtig 'n geskakelde lys te sorteer

89
00:03:45,666 --> 00:03:47,870
is om dit te sorteer as jy dit op te rig.

90
00:03:47,870 --> 00:03:50,497
Maar as jy dit sorteer as wat jy
bou dit, jy nie meer

91
00:03:50,497 --> 00:03:51,830
die maak van vinnige invoegings nie.

92
00:03:51,830 --> 00:03:53,746
Jy is nie net 'tacking
dinge op die voorkant.

93
00:03:53,746 --> 00:03:55,710
Jy het die vind
regte plek om dit te sit,

94
00:03:55,710 --> 00:03:57,820
en dan jou te voeg
raak net oor so sleg

95
00:03:57,820 --> 00:03:59,390
die invoeging in 'n skikking.

96
00:03:59,390 --> 00:04:03,130
So geskakelde lyste is nie
so groot vir sortering van data.

97
00:04:03,130 --> 00:04:05,830
>> Hulle is ook redelik klein, grootte-wyse.

98
00:04:05,830 --> 00:04:08,496
Dubbel geskakelde lys effens
groter as enkel geskakelde lyste,

99
00:04:08,496 --> 00:04:10,620
wat effens groter is
as skikkings, maar dit is nie

100
00:04:10,620 --> 00:04:13,330
'n groot hoeveelheid van die gemors ruimte.

101
00:04:13,330 --> 00:04:18,730
So as ruimte is teen 'n premie, maar
nie 'n baie intense premie,

102
00:04:18,730 --> 00:04:22,180
hierdie dalk die regte manier om te gaan.

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

104
00:04:23,330 --> 00:04:25,850
Invoeging in 'n hash tafel
is redelik eenvoudig.

105
00:04:25,850 --> 00:04:26,980
Dit is 'n twee-stap proses.

106
00:04:26,980 --> 00:04:30,700
Eerstens moet ons ons data loop deur
'n hash funksie om 'n hash-kode te kry,

107
00:04:30,700 --> 00:04:37,550
en dan voeg ons die element in die
hash tafel op daardie hash kode plek.

108
00:04:37,550 --> 00:04:40,879
>> Skrap, soortgelyk aan gekoppel lys
is maklik as jy die element te vind.

109
00:04:40,879 --> 00:04:43,170
Jy moet dit eerste te vind,
maar dan wanneer jy dit verwyder,

110
00:04:43,170 --> 00:04:45,128
Jy hoef net te ruil
'n paar van wysers,

111
00:04:45,128 --> 00:04:47,250
As jy met behulp van aparte aaneenskakeling.

112
00:04:47,250 --> 00:04:49,942
As jy met behulp van indringende,
of as jy nie

113
00:04:49,942 --> 00:04:51,650
gebruik van chaining ten alle
in jou hash tafel,

114
00:04:51,650 --> 00:04:53,040
skrap is eintlik baie maklik.

115
00:04:53,040 --> 00:04:57,134
Al wat jy hoef te doen, is die hash
data, en dan gaan jy na die plek.

116
00:04:57,134 --> 00:04:58,925
En die veronderstelling dat jy dit nie doen nie
enige botsings,

117
00:04:58,925 --> 00:05:01,650
jy sal in staat wees om baie vinnig te verwyder.

118
00:05:01,650 --> 00:05:04,930
>> Nou, lookup is waar dinge
kry 'n bietjie meer ingewikkeld.

119
00:05:04,930 --> 00:05:06,910
Dit is op die gemiddelde beter
as geskakelde lyste.

120
00:05:06,910 --> 00:05:09,560
As jy met behulp van aaneenskakeling,
jy nog 'n geskakelde lys,

121
00:05:09,560 --> 00:05:13,170
wat beteken dat jy nog steeds die
soek nadeel 'n geskakelde lys.

122
00:05:13,170 --> 00:05:18,390
Maar omdat jy die neem van jou gekoppel
lys en verdeel dit oor 100 of 1000

123
00:05:18,390 --> 00:05:25,380
of n elemente in jou hash tafel, jy
geskakelde lyste is almal een nde die grootte.

124
00:05:25,380 --> 00:05:27,650
Hulle is almal aansienlik kleiner.

125
00:05:27,650 --> 00:05:32,080
Jy het n geskakelde lyste plaas
een gekoppel lys van grootte n.

126
00:05:32,080 --> 00:05:34,960
>> En so gaan dit die werklike wêreld konstante
faktor, wat oor die algemeen ons

127
00:05:34,960 --> 00:05:39,730
praat nie oor in die tyd kompleksiteit, is dit
nie eintlik 'n verskil te maak hier.

128
00:05:39,730 --> 00:05:43,020
So lookup nog lineêre
soek as jy die gebruik aaneenskakeling,

129
00:05:43,020 --> 00:05:46,780
maar die lengte van die lys
jy soek deur

130
00:05:46,780 --> 00:05:50,080
is baie, baie kort in vergelyking.

131
00:05:50,080 --> 00:05:52,995
Weereens, as sortering is jou
doel hier, hash tafel se

132
00:05:52,995 --> 00:05:54,370
waarskynlik nie die regte manier om te gaan.

133
00:05:54,370 --> 00:05:56,830
Net gebruik 'n verskeidenheid as sortering
is regtig belangrik vir jou.

134
00:05:56,830 --> 00:05:58,590
>> En hulle kan die spektrum van die grootte hardloop.

135
00:05:58,590 --> 00:06:01,640
Dit is moeilik om te sê of 'n
hash tafel is klein of groot,

136
00:06:01,640 --> 00:06:04,110
want dit hang af van
hoe groot jou hash tafel is.

137
00:06:04,110 --> 00:06:07,340
As jy net gaan stoor
vyf elemente in jou hash tafel,

138
00:06:07,340 --> 00:06:10,620
en jy het 'n hash tafel
met 10.000 elemente in dit,

139
00:06:10,620 --> 00:06:12,614
jy waarskynlik mors 'n baie ruimte.

140
00:06:12,614 --> 00:06:15,030
Kontrasteer om jy kan ook
het 'n baie kompakte hash tabelle,

141
00:06:15,030 --> 00:06:18,720
maar die kleiner jou hash tafel kry,
die langer elkeen van daardie geskakelde lyste

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

143
00:06:19,220 --> 00:06:22,607
En so is daar werklik geen manier om te definieer
presies die grootte van 'n hash tafel,

144
00:06:22,607 --> 00:06:24,440
maar dit is waarskynlik veilig
om te sê dit is oor die algemeen

145
00:06:24,440 --> 00:06:27,990
gaan groter as 'n gekoppelde wees
lys die stoor van die dieselfde data,

146
00:06:27,990 --> 00:06:30,400
maar kleiner as 'n Trie.

147
00:06:30,400 --> 00:06:32,720
>> En drieë is die vierde
van hierdie strukture

148
00:06:32,720 --> 00:06:34,070
dat ons het gepraat oor.

149
00:06:34,070 --> 00:06:36,450
Invoeging in 'n Trie is kompleks.

150
00:06:36,450 --> 00:06:38,400
Daar is 'n baie dinamiese
toekenning geheue,

151
00:06:38,400 --> 00:06:40,780
veral aan die begin,
as jy begin om te bou.

152
00:06:40,780 --> 00:06:43,700
Maar dit is konstante tyd.

153
00:06:43,700 --> 00:06:47,690
Dit is net die menslike element
hier wat maak dit moeilik.

154
00:06:47,690 --> 00:06:53,250
Om te null pointer teëkom, malloc
ruimte, daar gaan, moontlik malloc ruimte

155
00:06:53,250 --> 00:06:54,490
van daar weer.

156
00:06:54,490 --> 00:06:58,880
Die soort van intimidasie faktor van
wysers in dinamiese geheuetoekenning

157
00:06:58,880 --> 00:07:00,130
is die hekkie om skoon te maak.

158
00:07:00,130 --> 00:07:04,550
Maar sodra jy dit skoongemaak, voeg
kom eintlik heel eenvoudig,

159
00:07:04,550 --> 00:07:06,810
en dit is beslis 'n konstante tyd.

160
00:07:06,810 --> 00:07:07,680
>> Skrap is maklik.

161
00:07:07,680 --> 00:07:11,330
Al wat jy hoef te doen, is opgevolg af 'n
paar wenke en vry om die knoop,

162
00:07:11,330 --> 00:07:12,420
so dit is redelik goed.

163
00:07:12,420 --> 00:07:13,930
Lookup is ook redelik vinnig.

164
00:07:13,930 --> 00:07:16,780
Dit is net gebaseer op die
lengte van jou data.

165
00:07:16,780 --> 00:07:19,924
So as al jou data is
vyf karakterstringe,

166
00:07:19,924 --> 00:07:22,590
byvoorbeeld, jy stoor vyf
karakterstringe in jou Trie,

167
00:07:22,590 --> 00:07:25,439
dit neem slegs vyf stappe om
vind wat jy soek.

168
00:07:25,439 --> 00:07:28,480
Vyf is net 'n konstante faktor, so
weer, inplanting, skrap, en soek

169
00:07:28,480 --> 00:07:31,670
Hier is al konstante tyd effektief.

170
00:07:31,670 --> 00:07:34,880
>> Nog 'n ding is dat jou Trie is
eintlik soort van reeds gesorteer, reg?

171
00:07:34,880 --> 00:07:36,800
Op grond van hoe ons
invoeging elemente,

172
00:07:36,800 --> 00:07:40,060
deur te gaan letter vir letter van die
sleutel, of deur syfer syfer van die sleutel,

173
00:07:40,060 --> 00:07:45,084
Tipies, jou Trie beland
soort gesorteer as jy dit bou.

174
00:07:45,084 --> 00:07:47,250
Dit maak nie regtig maak
sin om te dink oor die sortering

175
00:07:47,250 --> 00:07:49,874
in dieselfde manier waarop ons dink oor
met skikkings, of geskakelde lyste,

176
00:07:49,874 --> 00:07:51,070
of hash tabelle.

177
00:07:51,070 --> 00:07:54,780
Maar in 'n sekere sin, jou
Trie gesorteer soos jy gaan.

178
00:07:54,780 --> 00:07:58,630
>> Die nadeel, natuurlik, is dat
'n Trie vinnig raak groot.

179
00:07:58,630 --> 00:08:02,970
Uit elke kruising punt, kan jy
have-- as jou sleutel bestaan ​​uit syfers,

180
00:08:02,970 --> 00:08:04,880
jy het 10 ander
plekke wat jy kan gaan, wat

181
00:08:04,880 --> 00:08:07,490
beteken dat elke node
bevat inligting

182
00:08:07,490 --> 00:08:11,440
oor die data wat jy wil om op te slaan
op daardie node, plus 10 wenke.

183
00:08:11,440 --> 00:08:14,430
Wat op CS50 IDE, is 80 grepe.

184
00:08:14,430 --> 00:08:17,220
So dit is ten minste 80 grepe vir
elke node wat jy skep,

185
00:08:17,220 --> 00:08:19,240
en dit is nie eens tel data.

186
00:08:19,240 --> 00:08:24,950
En as jou nodes is
letters in plaas van syfers,

187
00:08:24,950 --> 00:08:27,825
nou het jy 26 wenke
uit elke plek.

188
00:08:27,825 --> 00:08:32,007
En 26 keer 8 is waarskynlik 200
grepe, of iets soos dit.

189
00:08:32,007 --> 00:08:33,840
En jy het kapitaal
en lowercase-- kan jy

190
00:08:33,840 --> 00:08:35,381
sien waar ek gaan met hierdie, reg?

191
00:08:35,381 --> 00:08:37,500
Jou nodes kan regtig
groot, en so die Trie

192
00:08:37,500 --> 00:08:40,470
self, algehele, kan
kry regtig groot, te.

193
00:08:40,470 --> 00:08:42,630
So as ruimte is op 'n hoë
premie op jou stelsel,

194
00:08:42,630 --> 00:08:45,830
'n Trie dalk die regte manier om nie
gaan, selfs al is sy ander voordele

195
00:08:45,830 --> 00:08:47,780
kom in die spel.

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

197
00:08:48,710 --> 00:08:50,740
Dit is CS50.

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