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 täckt
en massa olika datastrukturer,

3
00:00:08,300 --> 00:00:09,180
höger?

4
00:00:09,180 --> 00:00:11,420
Vi har sett arrayer, och länkade
listor och hashtabeller,

5
00:00:11,420 --> 00:00:15,210
och försöker, stackar och köer.

6
00:00:15,210 --> 00:00:17,579
Vi kommer också att lära sig lite
om träd och högar,

7
00:00:17,579 --> 00:00:20,120
men egentligen alla dessa bara sluta
upp att vara variationer på ett tema.

8
00:00:20,120 --> 00:00:22,840
Det finns verkligen dessa
typ av fyra grundläggande idéer

9
00:00:22,840 --> 00:00:25,190
att allt annat kan koka ner till.

10
00:00:25,190 --> 00:00:28,150
Arrayer, länkade listor,
hashtabeller och försöker.

11
00:00:28,150 --> 00:00:30,720
Och som sagt, det
är variationer på dem,

12
00:00:30,720 --> 00:00:32,720
men detta är ganska
mycket kommer att sammanfatta

13
00:00:32,720 --> 00:00:38,140
allt vi ska prata
om i denna klass när det gäller C.

14
00:00:38,140 --> 00:00:40,140
>> Men hur gör alla dessa mått upp, eller hur?

15
00:00:40,140 --> 00:00:44,265
Vi har pratat om för- och nackdelar
av varje i separata videor på dem,

16
00:00:44,265 --> 00:00:46,390
men det finns en massa siffror
få kastas runt.

17
00:00:46,390 --> 00:00:48,723
Det finns en hel del allmän
tankar blir kastas runt.

18
00:00:48,723 --> 00:00:51,950
Låt oss försöka konsolidera
det till ett och samma ställe.

19
00:00:51,950 --> 00:00:55,507
Låt oss väga proffsen mot
nackdelar, och överväga

20
00:00:55,507 --> 00:00:57,340
vilken datastruktur
kan vara rätt uppgifter

21
00:00:57,340 --> 00:01:01,440
struktur för just din situation,
oavsett typ av data du lagrar.

22
00:01:01,440 --> 00:01:06,625
Du behöver inte nödvändigtvis alltid behöver
använda supersnabba insertion, deletion,

23
00:01:06,625 --> 00:01:10,761
och uppslagning av en trie om du verkligen
bryr sig inte om infoga och ta bort

24
00:01:10,761 --> 00:01:11,260
för mycket.

25
00:01:11,260 --> 00:01:13,968
Om du behöver bara snabbt slumpmässig
tillgång, en array är kanske bättre.

26
00:01:13,968 --> 00:01:15,340
Så låt oss destillera det.

27
00:01:15,340 --> 00:01:18,530
Låt oss tala om var och en av de fyra
stora grupper av datastrukturer

28
00:01:18,530 --> 00:01:21,720
att vi har pratat om, och
bara se när de kan vara bra,

29
00:01:21,720 --> 00:01:23,340
och när de kanske inte är så bra.

30
00:01:23,340 --> 00:01:24,610
Så låt oss börja med arrayer.

31
00:01:24,610 --> 00:01:27,300
Så insättning, det är typ av dåligt.

32
00:01:27,300 --> 00:01:31,350
>> Insättning vid slutet av en array är OK,
Om vi ​​bygger en array som vi går.

33
00:01:31,350 --> 00:01:33,570
Men om vi behöver sätta in
element i mitten,

34
00:01:33,570 --> 00:01:35,550
tänker tillbaka på insättning
sort, det finns en hel del

35
00:01:35,550 --> 00:01:37,510
att flytta för att passa en del i det.

36
00:01:37,510 --> 00:01:41,170
Och så om vi ska infoga
helst men i slutet av en array,

37
00:01:41,170 --> 00:01:43,590
det är nog inte så stor.

38
00:01:43,590 --> 00:01:46,710
>> På samma sätt, radering, om vi är
radera från slutet av en array,

39
00:01:46,710 --> 00:01:49,810
är förmodligen inte heller så bra om
Vi vill inte lämna tomma luckor,

40
00:01:49,810 --> 00:01:50,790
som vanligtvis gör vi inte.

41
00:01:50,790 --> 00:01:54,700
Vi vill ta bort ett element, och
då sorts göra det ordentligt igen.

42
00:01:54,700 --> 00:01:57,670
Och så ta bort element från
en array, också inte så stor.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, är dock stor.

44
00:01:58,820 --> 00:02:00,920
Vi har direktåtkomst,
konstant tid lookup.

45
00:02:00,920 --> 00:02:03,800
Vi säger bara sju, och vi går
till array omlokalisering sju.

46
00:02:03,800 --> 00:02:05,907
Vi säger 20, med gå till
array omlokalisering 20.

47
00:02:05,907 --> 00:02:07,240
Vi behöver inte iterera över.

48
00:02:07,240 --> 00:02:08,630
Det är ganska bra.

49
00:02:08,630 --> 00:02:11,020
>> Arrayer är också relativt lätt att sortera.

50
00:02:11,020 --> 00:02:14,040
Varje gång vi talade om en sortering
algoritm, såsom val sortera,

51
00:02:14,040 --> 00:02:18,820
insättningssortering, bubbelsortering, slå samman
sort, vi alltid använt arrayer för att göra det,

52
00:02:18,820 --> 00:02:21,860
eftersom arrayer är ganska lätt att
sortera, i förhållande till datastrukturerna

53
00:02:21,860 --> 00:02:22,970
vi har sett hittills.

54
00:02:22,970 --> 00:02:24,320
>> De är också relativt små.

55
00:02:24,320 --> 00:02:25,695
Det finns inte en hel del extra utrymme.

56
00:02:25,695 --> 00:02:29,210
Du bara avsätta exakt så mycket
som du behöver för att hålla dina data,

57
00:02:29,210 --> 00:02:30,320
och det är ganska mycket det.

58
00:02:30,320 --> 00:02:33,180
Så de är ganska små
och effektivt på detta sätt.

59
00:02:33,180 --> 00:02:36,000
Men en annan nackdel, men,
är att de är fixerade i storlek.

60
00:02:36,000 --> 00:02:38,630
Vi måste förklara exakt hur
stora vi vill att vår array vara,

61
00:02:38,630 --> 00:02:39,940
och vi får endast ett skott på det.

62
00:02:39,940 --> 00:02:41,280
Vi kan inte växa och krympa den.

63
00:02:41,280 --> 00:02:44,582
>> Om vi ​​behöver för att växa eller krympa det, vi
måste förklara en helt ny array,

64
00:02:44,582 --> 00:02:47,750
kopiera alla delar av
första uppsättningen in i den andra uppsättningen.

65
00:02:47,750 --> 00:02:51,410
Och om vi missbedömde att
tid, vi måste göra det igen.

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

67
00:02:52,760 --> 00:02:58,750
Så arrayer inte ger oss flexibilitet
att ha varierande antal element.

68
00:02:58,750 --> 00:03:01,320
>> Med en länkad lista,
insättning är ganska lätt.

69
00:03:01,320 --> 00:03:03,290
Vi slår bara på framsidan.

70
00:03:03,290 --> 00:03:04,892
Strykning är också ganska lätt.

71
00:03:04,892 --> 00:03:06,100
Vi måste hitta elementen.

72
00:03:06,100 --> 00:03:07,270
Som involverar vissa sökning.

73
00:03:07,270 --> 00:03:10,270
>> Men när du har hittat elementet
du letar efter, allt du behöver göra

74
00:03:10,270 --> 00:03:12,830
är att ändra en pekare,
möjligen två om du har

75
00:03:12,830 --> 00:03:15,151
en länkad list-- en dubbelt
länkad lista, rather--

76
00:03:15,151 --> 00:03:16,650
och sedan kan du bara befria noden.

77
00:03:16,650 --> 00:03:18,399
Du behöver inte flytta
allt runt.

78
00:03:18,399 --> 00:03:22,090
Du ändrar bara två pekare,
så det är ganska snabbt.

79
00:03:22,090 --> 00:03:23,470
>> Lookup är dåligt men, eller hur?

80
00:03:23,470 --> 00:03:26,280
För för oss att hitta en
element i en länkad lista,

81
00:03:26,280 --> 00:03:29,154
vare sig ensamma eller dubbellänkad,
Vi måste linjär söka det.

82
00:03:29,154 --> 00:03:32,320
Vi måste börja från början och
flytta slutet, eller starta i slutet flytta

83
00:03:32,320 --> 00:03:33,860
till början.

84
00:03:33,860 --> 00:03:35,474
Vi har inte random access längre.

85
00:03:35,474 --> 00:03:37,265
Så om vi gör en
mycket söka, kanske

86
00:03:37,265 --> 00:03:39,830
en länkad lista är inte
ganska så bra för oss.

87
00:03:39,830 --> 00:03:43,750
>> De är också riktigt
svårt att sortera, eller hur?

88
00:03:43,750 --> 00:03:45,666
Det enda sättet du kan
verkligen sortera en länkad lista

89
00:03:45,666 --> 00:03:47,870
är att sortera det som du bygga den.

90
00:03:47,870 --> 00:03:50,497
Men om du sorterar det som du
konstruera det, du är inte längre

91
00:03:50,497 --> 00:03:51,830
göra snabba insättningar längre.

92
00:03:51,830 --> 00:03:53,746
Du är inte bara kryss
saker på framsidan.

93
00:03:53,746 --> 00:03:55,710
Du måste hitta
rätt plats för att uttrycka det,

94
00:03:55,710 --> 00:03:57,820
och sedan ditt insättning
blir ungefär lika illa

95
00:03:57,820 --> 00:03:59,390
som att sätta in i en matris.

96
00:03:59,390 --> 00:04:03,130
Så länkade listor är inte
så bra för sortering av data.

97
00:04:03,130 --> 00:04:05,830
>> De är också ganska liten, storleksmässigt.

98
00:04:05,830 --> 00:04:08,496
Listan dubbellänkad något
större än var för sig länkade listor,

99
00:04:08,496 --> 00:04:10,620
som är något större
än arrayer, men det är inte

100
00:04:10,620 --> 00:04:13,330
en enorm mängd oanvänt utrymme.

101
00:04:13,330 --> 00:04:18,730
Så om utrymmet är begränsat, men
inte riktigt intensiv premie,

102
00:04:18,730 --> 00:04:22,180
Detta kan vara rätt väg att gå.

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

104
00:04:23,330 --> 00:04:25,850
Införande i en hash-tabell
är ganska enkel.

105
00:04:25,850 --> 00:04:26,980
Det är en tvåstegsprocess.

106
00:04:26,980 --> 00:04:30,700
Först måste vi driva våra data genom
en hashfunktion för att få en hash-kod,

107
00:04:30,700 --> 00:04:37,550
och sedan in vi elementet i
hashtabell vid denna hash-kod plats.

108
00:04:37,550 --> 00:04:40,879
>> Strykning, liknande länkad lista,
Det är lätt när du hittar elementet.

109
00:04:40,879 --> 00:04:43,170
Du måste hitta den först,
men sedan när du tar bort det,

110
00:04:43,170 --> 00:04:45,128
du behöver bara byta
ett par pekare,

111
00:04:45,128 --> 00:04:47,250
Om du använder separat kedja.

112
00:04:47,250 --> 00:04:49,942
Om du använder sondering,
eller om du inte

113
00:04:49,942 --> 00:04:51,650
användning kedja alls
i hashtabell,

114
00:04:51,650 --> 00:04:53,040
Strykningen är faktiskt riktigt enkelt.

115
00:04:53,040 --> 00:04:57,134
Allt du behöver göra är att hasha
uppgifter, och sedan gå till den platsen.

116
00:04:57,134 --> 00:04:58,925
Och förutsatt att du inte
har några kollisioner,

117
00:04:58,925 --> 00:05:01,650
kommer du att kunna ta bort mycket snabbt.

118
00:05:01,650 --> 00:05:04,930
>> Nu är lookup där saker
få lite mer komplicerat.

119
00:05:04,930 --> 00:05:06,910
Det är i genomsnitt bättre
än länkade listor.

120
00:05:06,910 --> 00:05:09,560
Om du använder kedja,
du fortfarande har en länkad lista,

121
00:05:09,560 --> 00:05:13,170
vilket innebär att du fortfarande har
sök förfång en länkad lista.

122
00:05:13,170 --> 00:05:18,390
Men eftersom du tar din länkade
lista och dela den över 100 eller 1000

123
00:05:18,390 --> 00:05:25,380
eller n element i hash tabellen, är du
länkade listor är alla en n: te storlek.

124
00:05:25,380 --> 00:05:27,650
De är alla betydligt mindre.

125
00:05:27,650 --> 00:05:32,080
Du har n länkade listor i stället
av en länkad lista av storlek n.

126
00:05:32,080 --> 00:05:34,960
>> Och så denna verkliga konstant
faktor, som vi vanligtvis

127
00:05:34,960 --> 00:05:39,730
inte tala om i tid komplexitet, det
gör faktiskt en skillnad här.

128
00:05:39,730 --> 00:05:43,020
Så lookup är fortfarande linjär
söka om du använder kedja,

129
00:05:43,020 --> 00:05:46,780
men längden av listan
du söker igenom

130
00:05:46,780 --> 00:05:50,080
är mycket, mycket kort i jämförelse.

131
00:05:50,080 --> 00:05:52,995
Återigen, om sorteringen är ditt
Målet här, hash tabellens

132
00:05:52,995 --> 00:05:54,370
antagligen inte rätt väg att gå.

133
00:05:54,370 --> 00:05:56,830
Använd bara en array om sortering
är verkligen viktigt för dig.

134
00:05:56,830 --> 00:05:58,590
>> Och de kan köra spektrat av storlek.

135
00:05:58,590 --> 00:06:01,640
Det är svårt att säga om en
hash tabellen är liten eller stor,

136
00:06:01,640 --> 00:06:04,110
eftersom det verkligen beror på
hur stor din hash tabellen är.

137
00:06:04,110 --> 00:06:07,340
Om du bara kommer att lagra
fem element i hash tabellen,

138
00:06:07,340 --> 00:06:10,620
och du har en hashtabell
med 10.000 element i det,

139
00:06:10,620 --> 00:06:12,614
du förmodligen ett slöseri med utrymme.

140
00:06:12,614 --> 00:06:15,030
Kontrast är kan du också
har mycket kompakta hashtabeller,

141
00:06:15,030 --> 00:06:18,720
men mindre din hash tabellen blir,
ju längre var och en av dessa länkade listor

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

143
00:06:19,220 --> 00:06:22,607
Och så det finns verkligen inget sätt att definiera
exakt storleken på en hash-tabell,

144
00:06:22,607 --> 00:06:24,440
men det är nog säkert
säga att det är i allmänhet

145
00:06:24,440 --> 00:06:27,990
kommer att bli större än en länkad
lista lagrar samma uppgifter,

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

147
00:06:30,400 --> 00:06:32,720
>> Och försök är den fjärde
av dessa strukturer

148
00:06:32,720 --> 00:06:34,070
att vi har pratat om.

149
00:06:34,070 --> 00:06:36,450
Sätta in en trie är komplex.

150
00:06:36,450 --> 00:06:38,400
Det finns en hel del dynamiskt
minnesallokering,

151
00:06:38,400 --> 00:06:40,780
särskilt i början,
som du börjar bygga.

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

153
00:06:43,700 --> 00:06:47,690
Det är bara den mänskliga faktorn
här som gör det knepigt.

154
00:06:47,690 --> 00:06:53,250
Att behöva möta nollpekare, malloc
utrymme, åka dit, möjligen malloc utrymme

155
00:06:53,250 --> 00:06:54,490
därifrån igen.

156
00:06:54,490 --> 00:06:58,880
Den typ av hotelser faktor
pekare i dynamisk minnesallokering

157
00:06:58,880 --> 00:07:00,130
är hindret för att rensa.

158
00:07:00,130 --> 00:07:04,550
Men när du har rensat det, insättning
kommer faktiskt ganska enkelt,

159
00:07:04,550 --> 00:07:06,810
och det är verkligen konstant tid.

160
00:07:06,810 --> 00:07:07,680
>> Radering är lätt.

161
00:07:07,680 --> 00:07:11,330
Allt du behöver göra är att navigera ned en
par pekare och gratis noden,

162
00:07:11,330 --> 00:07:12,420
så det är ganska bra.

163
00:07:12,420 --> 00:07:13,930
Lookup är också ganska fort.

164
00:07:13,930 --> 00:07:16,780
Det är bara baserad på
längden på dina data.

165
00:07:16,780 --> 00:07:19,924
Så om alla dina data är
fem teckensträngar,

166
00:07:19,924 --> 00:07:22,590
till exempel, du lagra fem
teckensträngar i din trie,

167
00:07:22,590 --> 00:07:25,439
det tar bara fem steg till
hitta det du letar efter.

168
00:07:25,439 --> 00:07:28,480
Fem är bara en konstant faktor, så
igen, insertion, deletion och lookup

169
00:07:28,480 --> 00:07:31,670
här är alla konstant tid, effektivt.

170
00:07:31,670 --> 00:07:34,880
>> En annan sak är att din trie är
faktiskt ganska redan sorterats, eller hur?

171
00:07:34,880 --> 00:07:36,800
På grund av hur vi är
infoga element,

172
00:07:36,800 --> 00:07:40,060
genom att gå bokstav för bokstav för
nyckel, eller siffra för siffra av nyckeln,

173
00:07:40,060 --> 00:07:45,084
typiskt, slutar upp att vara din trie
typ av sorteras som du bygger det.

174
00:07:45,084 --> 00:07:47,250
Det spelar egentligen ingen gör
meningsfullt att tänka på sortering

175
00:07:47,250 --> 00:07:49,874
på samma sätt som vi tycker om
det med arrayer, eller länkade listor,

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

177
00:07:51,070 --> 00:07:54,780
Men i någon mening, ditt
trie sorteras som du går.

178
00:07:54,780 --> 00:07:58,630
>> Nackdelen är naturligtvis är att
en trie blir snabbt stora.

179
00:07:58,630 --> 00:08:02,970
Från varje knutpunkt, kanske du
have-- om din nyckel består av siffror,

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

181
00:08:04,880 --> 00:08:07,490
innebär att varje nod
innehåller information

182
00:08:07,490 --> 00:08:11,440
om de data du vill spara
vid denna nod, plus 10 pekare.

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

184
00:08:14,430 --> 00:08:17,220
Så det är åtminstone 80 byte för
varje nod som du skapar,

185
00:08:17,220 --> 00:08:19,240
och som inte är ens räkna data.

186
00:08:19,240 --> 00:08:24,950
Och om dina noder är
bokstäver i stället för siffror,

187
00:08:24,950 --> 00:08:27,825
nu har du 26 tips
från varje plats.

188
00:08:27,825 --> 00:08:32,007
Och 26 gånger 8 är förmodligen 200
byte, eller nåt sånt.

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

190
00:08:33,840 --> 00:08:35,381
se vart jag ska med detta, eller hur?

191
00:08:35,381 --> 00:08:37,500
Dina noder kan bli riktigt
stora, och så trie

192
00:08:37,500 --> 00:08:40,470
själv, totalt sett, kan
bli riktigt stora, alltför.

193
00:08:40,470 --> 00:08:42,630
Så om utrymmet är en hög
premie på ditt system,

194
00:08:42,630 --> 00:08:45,830
en trie kanske inte är rätt sätt att
gå, även om dess övriga förmåner

195
00:08:45,830 --> 00:08:47,780
spelar in.

196
00:08:47,780 --> 00:08:48,710
Jag är Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Detta är CS50.

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