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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Så i CS50, har vi dekket
en rekke forskjellige datastrukturer,

3
00:00:08,300 --> 00:00:09,180
ikke sant?

4
00:00:09,180 --> 00:00:11,420
Vi har sett arrays, og knyttes
lister og hash tabeller,

5
00:00:11,420 --> 00:00:15,210
og prøver, stabler og køer.

6
00:00:15,210 --> 00:00:17,579
Vi vil også lære litt
om trær og hauger,

7
00:00:17,579 --> 00:00:20,120
men egentlig alle disse bare ende
opp som variasjoner over et tema.

8
00:00:20,120 --> 00:00:22,840
Det virkelig er disse
form av fire grunnleggende ideer

9
00:00:22,840 --> 00:00:25,190
at alt annet kan koke ned til.

10
00:00:25,190 --> 00:00:28,150
Arrays, lenkede lister,
hash tabeller og prøver.

11
00:00:28,150 --> 00:00:30,720
Og som jeg sa, det
er variasjoner på dem,

12
00:00:30,720 --> 00:00:32,720
men dette er ganske
mye kommer til å oppsummere

13
00:00:32,720 --> 00:00:38,140
alt vi kommer til å snakke
om i denne klassen når det gjelder C.

14
00:00:38,140 --> 00:00:40,140
>> Men hvordan gjør alle disse måler opp, ikke sant?

15
00:00:40,140 --> 00:00:44,265
Vi har snakket om fordeler og ulemper
av hver i separate videoer på dem,

16
00:00:44,265 --> 00:00:46,390
men det er mye av tall
å bli kastet rundt.

17
00:00:46,390 --> 00:00:48,723
Det er mye av generell
tanker å bli kastet rundt.

18
00:00:48,723 --> 00:00:51,950
La oss prøve og konsolidere
den inn i bare ett sted.

19
00:00:51,950 --> 00:00:55,507
La oss veie fordeler mot
cons, og vurdere

20
00:00:55,507 --> 00:00:57,340
som datastruktur
kan være det riktige data

21
00:00:57,340 --> 00:01:01,440
struktur for din situasjon,
uansett hva slags data du lagrer.

22
00:01:01,440 --> 00:01:06,625
Du trenger ikke nødvendigvis alltid trenger å
bruke super rask innsetting, sletting,

23
00:01:06,625 --> 00:01:10,761
og oppslag av en trie hvis du virkelig
ikke bryr seg om å sette inn og slette

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

25
00:01:11,260 --> 00:01:13,968
Hvis du bare trenger raskt tilfeldig
tilgang til, kanskje en matrise er bedre.

26
00:01:13,968 --> 00:01:15,340
Så la oss destillere det.

27
00:01:15,340 --> 00:01:18,530
La oss snakke om hver av de fire
store typer datastrukturer

28
00:01:18,530 --> 00:01:21,720
at vi har snakket om, og
bare se når de kan være bra,

29
00:01:21,720 --> 00:01:23,340
og når de ikke kan være så bra.

30
00:01:23,340 --> 00:01:24,610
Så la oss starte med arrays.

31
00:01:24,610 --> 00:01:27,300
Så innsetting, er den slags dårlig.

32
00:01:27,300 --> 00:01:31,350
>> Innsetting i enden av en matrise er OK,
hvis vi bygger en matrise som vi går.

33
00:01:31,350 --> 00:01:33,570
Men hvis vi trenger å sette inn
elementer i midten,

34
00:01:33,570 --> 00:01:35,550
tenker tilbake til innsetting
sortere, det er mye

35
00:01:35,550 --> 00:01:37,510
av skiftende for å passe et element i det.

36
00:01:37,510 --> 00:01:41,170
Og så hvis vi kommer til å sette inn
hvor som helst, men i enden av en matrise,

37
00:01:41,170 --> 00:01:43,590
det er nok ikke så stor.

38
00:01:43,590 --> 00:01:46,710
>> Tilsvarende sletting, med mindre vi er
sletting fra enden av en matrise,

39
00:01:46,710 --> 00:01:49,810
er trolig heller ikke så stor hvis
vi ønsker ikke å la tomme hull,

40
00:01:49,810 --> 00:01:50,790
som vanligvis vi ikke.

41
00:01:50,790 --> 00:01:54,700
Vi ønsker å fjerne et element, og
da liksom gjøre det tett igjen.

42
00:01:54,700 --> 00:01:57,670
Og så slette elementer fra
en matrise, heller ikke så stor.

43
00:01:57,670 --> 00:01:58,820
>> Oppslag, skjønt, er stor.

44
00:01:58,820 --> 00:02:00,920
Vi har random access,
konstant tid oppslag.

45
00:02:00,920 --> 00:02:03,800
Vi bare si syv, og vi går
å rekke flytting sju.

46
00:02:03,800 --> 00:02:05,907
Vi sier 20, med farten til
matrise flytting 20.

47
00:02:05,907 --> 00:02:07,240
Vi har for å iterere over.

48
00:02:07,240 --> 00:02:08,630
Det er ganske bra.

49
00:02:08,630 --> 00:02:11,020
>> Arrays er også relativt enkelt å sortere.

50
00:02:11,020 --> 00:02:14,040
Hver gang vi snakket om en sortering
algoritme, slik som valg sort,

51
00:02:14,040 --> 00:02:18,820
innsetting sortere, boble sortere, flette
sortere, vi alltid brukt matriser til å gjøre det,

52
00:02:18,820 --> 00:02:21,860
fordi arrays er ganske lett å
sort, i forhold til datastrukturene

53
00:02:21,860 --> 00:02:22,970
vi har sett så langt.

54
00:02:22,970 --> 00:02:24,320
>> De er også forholdsvis liten.

55
00:02:24,320 --> 00:02:25,695
Det er ikke mye ekstra plass.

56
00:02:25,695 --> 00:02:29,210
Du bare satt akkurat så mye
som du trenger for å holde dine data,

57
00:02:29,210 --> 00:02:30,320
og det er ganske mye det.

58
00:02:30,320 --> 00:02:33,180
Så de er ganske små
og effektiv på den måten.

59
00:02:33,180 --> 00:02:36,000
Men en annen ulempe, skjønt,
er at de er løst i størrelse.

60
00:02:36,000 --> 00:02:38,630
Vi må erklære nøyaktig hvordan
big vi ønsker vår rekke å være,

61
00:02:38,630 --> 00:02:39,940
og vi får bare ett skudd på den.

62
00:02:39,940 --> 00:02:41,280
Vi kan ikke vokse og krympe det.

63
00:02:41,280 --> 00:02:44,582
>> Hvis vi trenger å vokse eller krympe det, vi
trenger å erklære en helt ny rekke,

64
00:02:44,582 --> 00:02:47,750
kopiere alle elementene i den
første rekke inn i den andre matrisen.

65
00:02:47,750 --> 00:02:51,410
Og hvis vi feilberegnet at
tid, må vi gjøre det igjen.

66
00:02:51,410 --> 00:02:52,760
Ikke så stor.

67
00:02:52,760 --> 00:02:58,750
Så arrays ikke gir oss fleksibilitet
å ha variable antall elementer.

68
00:02:58,750 --> 00:03:01,320
>> Med en lenket liste,
innsetting er ganske enkelt.

69
00:03:01,320 --> 00:03:03,290
Vi tack bare på forsiden.

70
00:03:03,290 --> 00:03:04,892
Sletting er også ganske lett.

71
00:03:04,892 --> 00:03:06,100
Vi må finne elementene.

72
00:03:06,100 --> 00:03:07,270
Som involverer noen søker.

73
00:03:07,270 --> 00:03:10,270
>> Men når du har funnet elementet
du leter etter, alt du trenger å gjøre

74
00:03:10,270 --> 00:03:12,830
er å endre en peker,
muligens to hvis du har

75
00:03:12,830 --> 00:03:15,151
en koblet list-- en dobbelt
lenket liste, rather--

76
00:03:15,151 --> 00:03:16,650
og da kan du bare frigjøre node.

77
00:03:16,650 --> 00:03:18,399
Du trenger ikke å skifte
alt rundt.

78
00:03:18,399 --> 00:03:22,090
Du bare endre to pekere,
så det er ganske rask.

79
00:03:22,090 --> 00:03:23,470
>> Oppslag er dårlig skjønt, ikke sant?

80
00:03:23,470 --> 00:03:26,280
For at vi skal finne en
element i en lenket liste,

81
00:03:26,280 --> 00:03:29,154
enten enkeltvis eller dobbelt koblet,
vi må lineær søke den.

82
00:03:29,154 --> 00:03:32,320
Vi må begynne på begynnelsen og
flytte til slutt, eller starte i slutten farten

83
00:03:32,320 --> 00:03:33,860
til begynnelsen.

84
00:03:33,860 --> 00:03:35,474
Vi har ikke random access lenger.

85
00:03:35,474 --> 00:03:37,265
Så hvis vi gjør en
Mange søker, kanskje

86
00:03:37,265 --> 00:03:39,830
en lenket liste er ikke
ganske så bra for oss.

87
00:03:39,830 --> 00:03:43,750
>> De er også veldig
vanskelig å sortere, ikke sant?

88
00:03:43,750 --> 00:03:45,666
Den eneste måten du kan
virkelig sortere en lenket liste

89
00:03:45,666 --> 00:03:47,870
er å sortere det som du konstruere den.

90
00:03:47,870 --> 00:03:50,497
Men hvis du sortere det som du
konstruere det, er du ikke lenger

91
00:03:50,497 --> 00:03:51,830
gjøre raske innsett lenger.

92
00:03:51,830 --> 00:03:53,746
Du er ikke bare overvinne
ting på forsiden.

93
00:03:53,746 --> 00:03:55,710
Du må finne den
rett sted for å si det,

94
00:03:55,710 --> 00:03:57,820
og deretter din innsetting
blir omtrent like ille

95
00:03:57,820 --> 00:03:59,390
som du setter inn i en matrise.

96
00:03:59,390 --> 00:04:03,130
Så lenkede lister er ikke
så stor for å sortere data.

97
00:04:03,130 --> 00:04:05,830
>> De er også ganske liten, størrelse-messig.

98
00:04:05,830 --> 00:04:08,496
Dobbelt lenket liste litt
større enn enkeltvis lenkede lister,

99
00:04:08,496 --> 00:04:10,620
som er litt større
enn arrays, men det er ikke

100
00:04:10,620 --> 00:04:13,330
en enorm mengde bortkastet plass.

101
00:04:13,330 --> 00:04:18,730
Så hvis plassen er på en premie, men
ikke en veldig intens premie,

102
00:04:18,730 --> 00:04:22,180
dette kan være den rette veien å gå.

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

104
00:04:23,330 --> 00:04:25,850
Innsetting i en hash table
er ganske grei.

105
00:04:25,850 --> 00:04:26,980
Det er en to-trinns prosess.

106
00:04:26,980 --> 00:04:30,700
Først må vi kjøre våre data gjennom
en hash-funksjon for å få en hash-kode,

107
00:04:30,700 --> 00:04:37,550
og deretter vi sett elementet inn i
hash table på at hash-kode plassering.

108
00:04:37,550 --> 00:04:40,879
>> Sletting, ligner lenket liste,
er lett når du finner elementet.

109
00:04:40,879 --> 00:04:43,170
Du må finne det først,
men så når du sletter den,

110
00:04:43,170 --> 00:04:45,128
du trenger bare å utveksle
et par tips,

111
00:04:45,128 --> 00:04:47,250
hvis du bruker separat kjeding.

112
00:04:47,250 --> 00:04:49,942
Hvis du bruker sondering,
eller hvis du ikke

113
00:04:49,942 --> 00:04:51,650
bruker kjeding i det hele tatt
i hash table,

114
00:04:51,650 --> 00:04:53,040
sletting er faktisk veldig enkelt.

115
00:04:53,040 --> 00:04:57,134
Alt du trenger å gjøre er hasj den
data, og deretter gå til stedet.

116
00:04:57,134 --> 00:04:58,925
Og forutsatt at du ikke gjør det
har noen kollisjoner,

117
00:04:58,925 --> 00:05:01,650
vil du være i stand til å slette svært raskt.

118
00:05:01,650 --> 00:05:04,930
>> Nå er oppslag hvor ting
få litt mer komplisert.

119
00:05:04,930 --> 00:05:06,910
Det er i gjennomsnitt bedre
enn lenkede lister.

120
00:05:06,910 --> 00:05:09,560
Hvis du bruker kjeding,
du har fortsatt en lenket liste,

121
00:05:09,560 --> 00:05:13,170
som betyr at du fortsatt har
søk skade en lenket liste.

122
00:05:13,170 --> 00:05:18,390
Men fordi du tar din linket
liste og dele det over 100 eller 1000

123
00:05:18,390 --> 00:05:25,380
eller n elementer i hash table, er du
lenkede lister er alle ett NTH størrelsen.

124
00:05:25,380 --> 00:05:27,650
De er alle vesentlig mindre.

125
00:05:27,650 --> 00:05:32,080
Du har n knyttet lister i stedet
av én lenket liste av størrelse n.

126
00:05:32,080 --> 00:05:34,960
>> Og så dette real-world konstant
faktor, som vi vanligvis

127
00:05:34,960 --> 00:05:39,730
ikke snakke om i tide kompleksitet, det
gjør faktisk en forskjell her.

128
00:05:39,730 --> 00:05:43,020
Så oppslag er fortsatt lineær
søke hvis du bruker kjeding,

129
00:05:43,020 --> 00:05:46,780
men lengden av listen
du søker gjennom

130
00:05:46,780 --> 00:05:50,080
er veldig, veldig kort i sammenligning.

131
00:05:50,080 --> 00:05:52,995
Igjen, hvis sorteringen er din
Målet her, hash tabellen

132
00:05:52,995 --> 00:05:54,370
sannsynligvis ikke den rette veien å gå.

133
00:05:54,370 --> 00:05:56,830
Bare bruk en matrise hvis sortering
er virkelig viktig for deg.

134
00:05:56,830 --> 00:05:58,590
>> Og de kan kjøre gamut av størrelsen.

135
00:05:58,590 --> 00:06:01,640
Det er vanskelig å si om en
hash table er liten eller stor,

136
00:06:01,640 --> 00:06:04,110
fordi det er egentlig avhengig av
hvor stor hash table er.

137
00:06:04,110 --> 00:06:07,340
Hvis du bare skal lagre
fem elementer i hash table,

138
00:06:07,340 --> 00:06:10,620
og du har en hash table
med 10.000 elementer i det,

139
00:06:10,620 --> 00:06:12,614
er du sannsynligvis kaste bort mye plass.

140
00:06:12,614 --> 00:06:15,030
Kontrast til at du kan også
har veldig kompakte hash tabeller,

141
00:06:15,030 --> 00:06:18,720
men mindre din hash table blir,
jo lenger hver av disse lenkede lister

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

143
00:06:19,220 --> 00:06:22,607
Og så det er egentlig ingen måte å definere
nøyaktig størrelsen på en nøkkeltabell,

144
00:06:22,607 --> 00:06:24,440
men det er nok trygt
å si at det er generelt

145
00:06:24,440 --> 00:06:27,990
kommer til å bli større enn en koblet
listen lagrer de samme data,

146
00:06:27,990 --> 00:06:30,400
men mindre enn en trie.

147
00:06:30,400 --> 00:06:32,720
>> Og prøver er den fjerde
av disse strukturene

148
00:06:32,720 --> 00:06:34,070
at vi har snakket om.

149
00:06:34,070 --> 00:06:36,450
Sette inn en trie er kompleks.

150
00:06:36,450 --> 00:06:38,400
Det er mye av dynamisk
minnetildeling,

151
00:06:38,400 --> 00:06:40,780
særlig i begynnelsen,
som du begynner å bygge.

152
00:06:40,780 --> 00:06:43,700
Men det er konstant tid.

153
00:06:43,700 --> 00:06:47,690
Det er bare det menneskelige element
her som gjør det vanskelig.

154
00:06:47,690 --> 00:06:53,250
Å måtte møte nullpeker, malloc
plass, går det, muligens malloc plass

155
00:06:53,250 --> 00:06:54,490
derfra igjen.

156
00:06:54,490 --> 00:06:58,880
Den slags trusler faktor på
pekere i dynamisk minne allokering

157
00:06:58,880 --> 00:07:00,130
er hinderet for å fjerne.

158
00:07:00,130 --> 00:07:04,550
Men når du har ryddet det, innsetting
kommer faktisk ganske enkelt,

159
00:07:04,550 --> 00:07:06,810
og det absolutt er konstant tid.

160
00:07:06,810 --> 00:07:07,680
>> Sletting er enkelt.

161
00:07:07,680 --> 00:07:11,330
Alt du trenger å gjøre er å navigere ned en
par pekere og gratis noden,

162
00:07:11,330 --> 00:07:12,420
så det er ganske bra.

163
00:07:12,420 --> 00:07:13,930
Oppslag er også ganske fort.

164
00:07:13,930 --> 00:07:16,780
Det er bare basert på den
lengden av dine data.

165
00:07:16,780 --> 00:07:19,924
Så hvis alle dine data er
fem tegnstrenger,

166
00:07:19,924 --> 00:07:22,590
for eksempel, du lagrer five
tegnstrenger i din trie,

167
00:07:22,590 --> 00:07:25,439
det tar bare fem trinn til
finne det du leter etter.

168
00:07:25,439 --> 00:07:28,480
Five er bare en konstant faktor, så
igjen, innsetting, sletting, og oppslag

169
00:07:28,480 --> 00:07:31,670
her er alle konstant tid, effektivt.

170
00:07:31,670 --> 00:07:34,880
>> En annen ting er at din trie er
faktisk slags allerede sortert, ikke sant?

171
00:07:34,880 --> 00:07:36,800
I kraft av hvordan vi er
sette inn elementer,

172
00:07:36,800 --> 00:07:40,060
ved å gå bokstav for bokstav i
tasten eller tall for tall av nøkkelen,

173
00:07:40,060 --> 00:07:45,084
vanligvis ender opp som din trie
slags sortert som du bygger den.

174
00:07:45,084 --> 00:07:47,250
Det gjør egentlig ikke gjør
fornuftig å tenke på sortering

175
00:07:47,250 --> 00:07:49,874
på samme måte som vi tenker på
det med matriser, eller lenkede lister,

176
00:07:49,874 --> 00:07:51,070
eller hash tabeller.

177
00:07:51,070 --> 00:07:54,780
Men på en måte, din
trie er sortert som du går.

178
00:07:54,780 --> 00:07:58,630
>> Ulempen er selvfølgelig at
en trie raskt blir enorme.

179
00:07:58,630 --> 00:08:02,970
Fra hvert knutepunkt, kanskje du
have-- hvis nøkkelen består av tall,

180
00:08:02,970 --> 00:08:04,880
du har 10 andre
steder du kan gå, som

181
00:08:04,880 --> 00:08:07,490
betyr at hver node
inneholder informasjon

182
00:08:07,490 --> 00:08:11,440
om dataene du ønsker å lagre
på at node, pluss 10 pekere.

183
00:08:11,440 --> 00:08:14,430
Som på CS50 IDE, er 80 byte.

184
00:08:14,430 --> 00:08:17,220
Så det er minst 80 byte for
hver node som du oppretter,

185
00:08:17,220 --> 00:08:19,240
og det er ikke engang telle data.

186
00:08:19,240 --> 00:08:24,950
Og hvis nodene er
bokstaver i stedet for tall,

187
00:08:24,950 --> 00:08:27,825
nå har du 26 tips
fra hvert sted.

188
00:08:27,825 --> 00:08:32,007
Og 26 ganger 8 er trolig 200
byte, eller noe sånt.

189
00:08:32,007 --> 00:08:33,840
Og du har kapital
og lowercase-- du kan

190
00:08:33,840 --> 00:08:35,381
se hvor jeg kommer med dette, ikke sant?

191
00:08:35,381 --> 00:08:37,500
Dine noder kan bli virkelig
stor, og slik at trie

192
00:08:37,500 --> 00:08:40,470
selv, samlet, kan
får virkelig stor, også.

193
00:08:40,470 --> 00:08:42,630
Så hvis plass er på et høyt
premie på systemet,

194
00:08:42,630 --> 00:08:45,830
en trie er kanskje ikke den rette måten å
gå, selv om de andre fordelene

195
00:08:45,830 --> 00:08:47,780
spiller inn.

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

197
00:08:48,710 --> 00:08:50,740
Dette er CS50.

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