1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Okay, så dette er
CS50 Dette er slutningen af ​​ugen fem.

3
00:00:15,860 --> 00:00:19,220
Og minde om, at sidste gang vi
begyndte at se på mere avanceret data

4
00:00:19,220 --> 00:00:22,310
strukturer, der er begyndt at løse
problemer, der begyndte at indføre

5
00:00:22,310 --> 00:00:25,640
nye problemer, men nøglen til denne
var slags gevindskæring, at vi

6
00:00:25,640 --> 00:00:27,940
begyndt at gøre fra knudepunkt til knudepunkt.

7
00:00:27,940 --> 00:00:30,085
Så dette er naturligvis
en enkelt bundet listen.

8
00:00:30,085 --> 00:00:31,960
Og ved enkelt bundet,
Jeg mener der er bare en

9
00:00:31,960 --> 00:00:33,380
tråd mellem hver af disse knudepunkter.

10
00:00:33,380 --> 00:00:35,890
Slår ud kan du gøre mere avanceret
ting som dobbelt hægtede lister

11
00:00:35,890 --> 00:00:38,470
hvorved du har en pil
går i begge retninger, hvilket

12
00:00:38,470 --> 00:00:40,320
kan hjælpe med visse effektiviteter.

13
00:00:40,320 --> 00:00:42,000
Men dette løst problemet?

14
00:00:42,000 --> 00:00:43,500
Hvilket problem har det løse?

15
00:00:43,500 --> 00:00:46,620
Hvorfor har vi bekymrer på mandag?

16
00:00:46,620 --> 00:00:49,820
Hvorfor i teorien, vi pleje på mandag?

17
00:00:49,820 --> 00:00:50,630
Hvad gør den?

18
00:00:50,630 --> 00:00:51,950
>> PUBLIKUM: Vi kan dynamisk ændre størrelsen.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, så vi kan
dynamisk ændre størrelsen.

20
00:00:53,740 --> 00:00:54,710
Godt klaret begge du.

21
00:00:54,710 --> 00:00:57,560
Så du kan dynamisk ændre størrelsen dette
datastruktur, mens et array,

22
00:00:57,560 --> 00:01:00,760
tilbagekaldelse, er du nødt til at kende en
priori hvor meget plads du ønsker

23
00:01:00,760 --> 00:01:03,870
og hvis du har brug for lidt mere
plads, er du slags ude af lykke.

24
00:01:03,870 --> 00:01:05,560
Du er nødt til at skabe en helt ny array.

25
00:01:05,560 --> 00:01:07,893
Du er nødt til at flytte alle dine
data fra den ene til den anden,

26
00:01:07,893 --> 00:01:10,600
vinder frigøre den gamle matrix
hvis du kan, og derefter gå videre.

27
00:01:10,600 --> 00:01:13,891
Som netop føles meget dyrt og meget
ineffektive, og faktisk kan det være.

28
00:01:13,891 --> 00:01:14,890
Men det er ikke alle gode.

29
00:01:14,890 --> 00:01:18,180
Vi betaler en pris, hvad var en
af de mere åbenlyse priser, vi

30
00:01:18,180 --> 00:01:20,550
betale ved hjælp af en sammenkædet liste?

31
00:01:20,550 --> 00:01:22,825
>> PUBLIKUM: Vi er nødt til at bruge
dobbelt plads til hver enkelt.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Ja, så har vi brug for
mindst dobbelt så meget plads.

33
00:01:25,200 --> 00:01:27,700
Faktisk indså jeg dette billede er
endda en smule vildledende,

34
00:01:27,700 --> 00:01:32,200
fordi på CS50 IDE i en masse moderne
computere, en pegepind eller en adresse

35
00:01:32,200 --> 00:01:33,700
er faktisk ikke fire bytes.

36
00:01:33,700 --> 00:01:36,090
Det er meget ofte disse
dage otte bytes, der

37
00:01:36,090 --> 00:01:38,530
betyder bunden mest
rektangler der i virkeligheden

38
00:01:38,530 --> 00:01:40,900
er slags dobbelt så
store som hvad jeg har tegnet,

39
00:01:40,900 --> 00:01:44,409
hvilket betyder, at du bruger tre gange så
meget plads, som vi måske har ellers.

40
00:01:44,409 --> 00:01:46,700
Nu samtidig er vi
stadig taler bytes, ikke?

41
00:01:46,700 --> 00:01:49,140
Vi er ikke nødvendigvis taler
megabyte eller gigabyte,

42
00:01:49,140 --> 00:01:51,000
medmindre disse data strukturer få store.

43
00:01:51,000 --> 00:01:54,510
>> Og så i dag vi begynder at overveje
hvordan vi kan udforske data

44
00:01:54,510 --> 00:01:57,310
mere effektivt, hvis i
Faktisk dataene bliver større.

45
00:01:57,310 --> 00:02:00,360
Men lad os prøve at canonicalize
operationerne første

46
00:02:00,360 --> 00:02:02,460
at du kan gøre på disse
former for datastrukturer.

47
00:02:02,460 --> 00:02:04,790
Så noget som en knyttet
liste generelt understøtter

48
00:02:04,790 --> 00:02:07,514
operationer kan lide slette,
indsætte, og søg.

49
00:02:07,514 --> 00:02:08,639
Og hvad mener jeg med det?

50
00:02:08,639 --> 00:02:11,222
Det betyder blot, at normalt,
hvis folk bruger linket liste,

51
00:02:11,222 --> 00:02:14,287
de eller en anden har implementeret
funktioner som delete, indsætte,

52
00:02:14,287 --> 00:02:16,120
og søg, så du kan
rent faktisk gør noget

53
00:02:16,120 --> 00:02:18,030
nyttige i forbindelse med datastruktur.

54
00:02:18,030 --> 00:02:20,760
Så lad os tage et hurtigt kig
på, hvordan vi måske gennemfører

55
00:02:20,760 --> 00:02:24,530
nogle kode for en forbundet liste som følger.

56
00:02:24,530 --> 00:02:27,885
>> Så dette er blot nogle C-kode,
ikke engang et komplet program

57
00:02:27,885 --> 00:02:29,260
at jeg virkelig hurtigt pisket op.

58
00:02:29,260 --> 00:02:32,300
Det er ikke online i distributionen
kode, fordi det vil faktisk ikke køre.

59
00:02:32,300 --> 00:02:33,790
Men bemærk jeg har bare
med en kommentar sagde,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, er der noget
der, dot dot dot, noget der.

61
00:02:36,130 --> 00:02:38,410
Og lad os bare se på
hvad de saftige dele er.

62
00:02:38,410 --> 00:02:40,790
Så på linje tre,
minde om, at det er nu

63
00:02:40,790 --> 00:02:45,960
Vi foreslog at erklære en node sidste
tid, en af ​​de rektangulære objekter.

64
00:02:45,960 --> 00:02:48,790
Det har en int, som vi vil kalde N,
men vi kunne kalde det noget,

65
00:02:48,790 --> 00:02:51,920
og derefter en struct node stjerne kaldes næste.

66
00:02:51,920 --> 00:02:55,520
Og bare for at være klar, at anden
linie på linie seks, hvad er det?

67
00:02:55,520 --> 00:02:57,930
Hvad er det gør for os?

68
00:02:57,930 --> 00:03:01,044
Fordi det sikkert ser mere
kryptiske end vores sædvanlige variable.

69
00:03:01,044 --> 00:03:02,740
>> PUBLIKUM: Det gør det flytte over én.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Det gør det flytte over én.

71
00:03:04,650 --> 00:03:08,580
Og for at være mere præcis,
det vil gemme adressen

72
00:03:08,580 --> 00:03:11,582
knudens, der er beregnet til at være
semantisk siden af ​​det, ikke?

73
00:03:11,582 --> 00:03:13,540
Så det kommer ikke til at
nødvendigvis flytte noget.

74
00:03:13,540 --> 00:03:15,290
Det er bare at gå til
lagre en værdi, som er

75
00:03:15,290 --> 00:03:17,170
vil være adressen
af en anden node,

76
00:03:17,170 --> 00:03:20,810
og det er derfor, vi har sagt struct
node stjerne, stjernen betegner

77
00:03:20,810 --> 00:03:22,370
en pointer eller en adresse.

78
00:03:22,370 --> 00:03:26,390
OK, så nu, hvis du antager, at vi har
denne N til rådighed for os, og lad os

79
00:03:26,390 --> 00:03:29,490
antage, at en anden har
indsat en hel masse tal

80
00:03:29,490 --> 00:03:30,400
i en sammenkædet liste.

81
00:03:30,400 --> 00:03:35,640
Og der er forbundet liste er
peget på af et tidspunkt

82
00:03:35,640 --> 00:03:39,040
en variabel kaldet liste, der er
bestået i her som en parameter,

83
00:03:39,040 --> 00:03:43,120
hvordan kan jeg gå om linje
14 om gennemførelse søgning?

84
00:03:43,120 --> 00:03:45,990
Med andre ord, hvis jeg gennemføre
funktion, hvis formål i livet

85
00:03:45,990 --> 00:03:48,889
er at tage en int og derefter
begyndelsen af ​​en linket liste,

86
00:03:48,889 --> 00:03:50,430
der er en pegepind til linkede liste.

87
00:03:50,430 --> 00:03:52,992
Ligesom første, som jeg synes David
var vores frivillige på mandag,

88
00:03:52,992 --> 00:03:54,700
Han pegede på
hele linkede liste,

89
00:03:54,700 --> 00:03:57,820
det er som om vi passerer
David som vores argument her.

90
00:03:57,820 --> 00:03:59,990
Hvordan kan vi gå om kørsel denne liste?

91
00:03:59,990 --> 00:04:04,640
Tja, det viser sig, at selv om
pointere er relativt nye nu for os,

92
00:04:04,640 --> 00:04:07,010
vi kan gøre denne relativt
ligefremt.

93
00:04:07,010 --> 00:04:09,500
>> Jeg har tænkt mig at gå videre og
erklære en midlertidig variabel,

94
00:04:09,500 --> 00:04:12,364
konventionelt er bare
at blive kaldt pointer, eller PTR,

95
00:04:12,364 --> 00:04:14,030
men du kan kalde det hvad du vil.

96
00:04:14,030 --> 00:04:16,470
Og jeg har tænkt mig at initialisere
den til starten af ​​listen.

97
00:04:16,470 --> 00:04:20,050
Så du kan slags tænker på dette
som mig læreren den anden dag,

98
00:04:20,050 --> 00:04:23,580
slags peger på en person
blandt vores mennesker som frivillige.

99
00:04:23,580 --> 00:04:26,470
Så jeg er en midlertidig variabel, der er
bare peger på den samme ting

100
00:04:26,470 --> 00:04:31,390
at vores tilfældigvis navngivet
volontør David blev også påpege.

101
00:04:31,390 --> 00:04:35,440
Nu mens markøren er
ikke null, fordi tilbagekaldelse

102
00:04:35,440 --> 00:04:40,350
at null er nogle særlige sentinel værdi
den afgrænser enden af ​​listen,

103
00:04:40,350 --> 00:04:44,280
så mens jeg ikke peger på
jorden som vores sidste frivillige

104
00:04:44,280 --> 00:04:47,190
var, lad os gå videre
og gøre følgende.

105
00:04:47,190 --> 00:04:51,820
Hvis pointer-- og nu jeg slags ønsker
at gøre, hvad vi gjorde med den studerende

106
00:04:51,820 --> 00:04:57,410
structure-- hvis pointer prik ud
equals-- snarere Hvis markøren dot N er lig med

107
00:04:57,410 --> 00:05:02,290
lig den variable N, den
argument, der er blevet vedtaget i,

108
00:05:02,290 --> 00:05:05,370
så jeg ønsker at gå videre
og sige returnere sandt.

109
00:05:05,370 --> 00:05:11,020
Jeg har fundet antallet N indersiden af
en af ​​knudepunkterne i min linkede liste.

110
00:05:11,020 --> 00:05:13,500
Men prikken ikke længere
virker i denne forbindelse,

111
00:05:13,500 --> 00:05:17,260
fordi pointer, PTR, er
faktisk en pegepind, en adresse,

112
00:05:17,260 --> 00:05:20,632
vi faktisk kan vidunderligt
bruge endelig et stykke af syntaks

113
00:05:20,632 --> 00:05:22,590
den slags mærker
intuitiv fornemmelse og faktisk

114
00:05:22,590 --> 00:05:27,870
bruge en pil her, hvilket betyder gå fra
denne adresse til heltal der i.

115
00:05:27,870 --> 00:05:30,160
Så det er meget ens i
ånd til dot operatør,

116
00:05:30,160 --> 00:05:33,860
men fordi markøren er en pegepind
og ikke en egentlig struct selv,

117
00:05:33,860 --> 00:05:35,380
vi bare bruge pilen.

118
00:05:35,380 --> 00:05:40,620
>> Så hvis den aktuelle node at jeg,
midlertidig variabel, am peger på

119
00:05:40,620 --> 00:05:43,060
ikke N, hvad ønsker jeg at gøre?

120
00:05:43,060 --> 00:05:45,910
Nå, med mine frivillige
at vi havde her den anden dag,

121
00:05:45,910 --> 00:05:49,710
hvis min første menneske er ikke den, jeg
ønsker, og måske den anden menneske ikke

122
00:05:49,710 --> 00:05:52,660
den jeg ønsker, og den tredje, jeg
nødt til at holde fysisk at flytte.

123
00:05:52,660 --> 00:05:54,690
Ligesom hvordan kan jeg gå gennem en liste?

124
00:05:54,690 --> 00:05:57,470
Da vi havde en matrix, du
bare kunne lide jeg plus plus.

125
00:05:57,470 --> 00:06:03,660
Men i dette tilfælde er det tilstrækkeligt at
gør pointer, får, pointer, næste.

126
00:06:03,660 --> 00:06:07,580
Med andre ord, det næste felt
er ligesom alle de venstre hånd

127
00:06:07,580 --> 00:06:10,880
at vores frivillige mandag
var at bruge til at pege på nogle andre node.

128
00:06:10,880 --> 00:06:12,890
Det var deres næste naboer.

129
00:06:12,890 --> 00:06:17,060
>> Så hvis jeg ønsker at træde igennem denne liste,
Jeg kan ikke bare gøre jeg plus plus længere,

130
00:06:17,060 --> 00:06:20,120
Jeg i stedet nødt til at sige
I, pointer, der foregår

131
00:06:20,120 --> 00:06:24,650
til lige hvad det næste felt er,
Det næste felt er, det næste felt er,

132
00:06:24,650 --> 00:06:28,350
efter alle disse venstre hånd
at vi havde på scenen peger

133
00:06:28,350 --> 00:06:30,000
til nogle efterfølgende værdier.

134
00:06:30,000 --> 00:06:32,590
Og hvis jeg kommer igennem
at hele iteration,

135
00:06:32,590 --> 00:06:39,330
og endelig, jeg ramte null ikke at have
fundet N endnu, jeg bare return false.

136
00:06:39,330 --> 00:06:44,100
Så igen, alt, hvad vi laver her,
som pr billedet et øjeblik siden,

137
00:06:44,100 --> 00:06:47,840
starter ved at pege på
starten af ​​listen formentlig.

138
00:06:47,840 --> 00:06:50,970
Og så vil jeg tjekke, er værdien
Jeg leder efter lig med ni?

139
00:06:50,970 --> 00:06:52,650
Hvis ja, jeg vender tilbage sandt og jeg er færdig.

140
00:06:52,650 --> 00:06:56,450
Hvis ikke, jeg opdatere min hånd,
AKA pointer, at pege

141
00:06:56,450 --> 00:06:59,540
ved pilen næste beliggenhed, og
derefter den næste pil beliggenhed,

142
00:06:59,540 --> 00:07:00,480
og den næste.

143
00:07:00,480 --> 00:07:03,770
Jeg blot at gå gennem denne array.

144
00:07:03,770 --> 00:07:06,010
>> Så igen, hvem bekymrer sig?

145
00:07:06,010 --> 00:07:07,861
Ligesom hvad er dette en ingrediens for?

146
00:07:07,861 --> 00:07:10,360
Nå, minde om, at vi introducerede
begrebet en stak, som

147
00:07:10,360 --> 00:07:15,400
er en abstrakt data skrive det omfang det er
ikke en C-ting, det er ikke en CS50 ting,

148
00:07:15,400 --> 00:07:19,430
Det er en abstrakt idé, denne idé om
stabling ting oven på hinanden

149
00:07:19,430 --> 00:07:21,820
der kan gennemføres i
bundter af forskellige måder.

150
00:07:21,820 --> 00:07:25,600
Og en måde, vi foreslog var med
et array, eller med en sammenkædet liste.

151
00:07:25,600 --> 00:07:29,570
Og det viser sig, at canonically, en
stakken understøtter mindst to operationer.

152
00:07:29,570 --> 00:07:32,320
Og brummer ord er skub, til
skubbe noget på stakken,

153
00:07:32,320 --> 00:07:34,770
som en ny bakke i
spisesal, eller pop,

154
00:07:34,770 --> 00:07:39,000
hvilket betyder at fjerne den øverste
bakke fra stakken i spisesalen

155
00:07:39,000 --> 00:07:41,500
hallen, og så måske nogle
andre operationer som godt.

156
00:07:41,500 --> 00:07:45,770
Så hvordan kan vi definerer strukturen
at vi nu kalder en stak?

157
00:07:45,770 --> 00:07:50,020
>> Tja, vi har alle de nødvendige
syntaks til vores rådighed i C. Jeg siger,

158
00:07:50,020 --> 00:07:53,830
give mig en type definition af
en struct inde i en stak,

159
00:07:53,830 --> 00:07:58,030
Jeg har tænkt mig at sige, er et array, en
hel masse tal, og derefter størrelse.

160
00:07:58,030 --> 00:08:00,930
Så med andre ord, hvis jeg vil
at gennemføre denne i kode,

161
00:08:00,930 --> 00:08:03,830
lad mig gå, og bare lidt
tegne, hvad det siger.

162
00:08:03,830 --> 00:08:06,317
Så dette siger, giv mig et
struktur, der har fået et array,

163
00:08:06,317 --> 00:08:09,400
og jeg ved ikke, hvad kapacitet er,
Det er tilsyneladende nogle konstant at jeg har

164
00:08:09,400 --> 00:08:10,858
defineret andetsteds, og det er fint.

165
00:08:10,858 --> 00:08:15,260
Men formoder, det er bare en,
to, tre, fire, fem.

166
00:08:15,260 --> 00:08:16,700
Så kapacitet er 5.

167
00:08:16,700 --> 00:08:21,730
Dette element inde i min
struktur vil blive kaldt numre.

168
00:08:21,730 --> 00:08:24,020
Og så er jeg har brug for en
anden variabel tilsyneladende

169
00:08:24,020 --> 00:08:27,814
kaldet størrelse, der oprindeligt jeg har tænkt mig
at fastsætte initialiseres til nul.

170
00:08:27,814 --> 00:08:29,730
Hvis der ikke er noget i
stakken, størrelse er nul,

171
00:08:29,730 --> 00:08:31,420
og det er skrald værdier i antal.

172
00:08:31,420 --> 00:08:33,450
Jeg har ingen idé om, hvad der er derinde endnu.

173
00:08:33,450 --> 00:08:36,059
>> Så hvis jeg ønsker at presse
noget på stakken,

174
00:08:36,059 --> 00:08:40,780
formoder jeg kalder funktionen skubbe, og
Jeg siger skubbe 50, ligesom antallet 50,

175
00:08:40,780 --> 00:08:44,090
hvor ville du foreslå,
Jeg trækker det i dette array?

176
00:08:44,090 --> 00:08:47,124
Der er fem forskellige mulige svar.

177
00:08:47,124 --> 00:08:48,790
Hvor vil du skubbe nummer 50?

178
00:08:48,790 --> 00:08:51,899
Hvis målet her, igen, så ring til
funktion skubbe, passere i et argument

179
00:08:51,899 --> 00:08:52,940
50, hvor skal jeg sætte det?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Fem possible-- 20% chance
for at gætte rigtigt.

182
00:08:59,052 --> 00:08:59,896
Ja?

183
00:08:59,896 --> 00:09:00,740
>> PUBLIKUM: Yderst til højre.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Yderst til højre.

185
00:09:01,990 --> 00:09:08,359
Der er nu en 25% chance
for at gætte rigtigt.

186
00:09:08,359 --> 00:09:09,650
Så det ville faktisk være fint.

187
00:09:09,650 --> 00:09:12,770
Ved konvention, vil jeg sige med et array,
Vi vil generelt begynde til venstre,

188
00:09:12,770 --> 00:09:14,519
men vi kunne sikkert
starter til højre.

189
00:09:14,519 --> 00:09:17,478
Så spoiler her ville være jeg er
sandsynligvis kommer til at trække det til venstre,

190
00:09:17,478 --> 00:09:20,060
ligesom i en normal vifte hvor
Jeg begynder at gå venstre til højre.

191
00:09:20,060 --> 00:09:21,780
Men hvis du kan bladre
det aritmetiske, fint.

192
00:09:21,780 --> 00:09:23,060
Det er bare ikke konventionelle.

193
00:09:23,060 --> 00:09:24,880
OK, jeg har brug for at lave en
mere forandring selv.

194
00:09:24,880 --> 00:09:27,710
Nu, hvor jeg har skubbet noget
på stakken, hvad det næste?

195
00:09:27,710 --> 00:09:29,400
>> Okay, jeg er nødt til at forøge størrelsen.

196
00:09:29,400 --> 00:09:32,600
Så lad mig gå videre og bare
opdatere denne, som var nul.

197
00:09:32,600 --> 00:09:35,950
Og i stedet nu, jeg har tænkt mig
at sætte i værdien én.

198
00:09:35,950 --> 00:09:39,460
Og nu tror jeg skubber en anden
nummer på stakken, ligesom 51.

199
00:09:39,460 --> 00:09:42,680
Tja, jeg er nødt til at gøre en mere
ændring, som er op til størrelsen to.

200
00:09:42,680 --> 00:09:46,100
Og vel så jeg skubber endnu
nummeret på stakken som 61,

201
00:09:46,100 --> 00:09:52,530
nu har jeg brug for at opdatere størrelse endnu
tid, og få værdien 3 som størrelsen.

202
00:09:52,530 --> 00:09:54,690
Og nu tror jeg kalder pop.

203
00:09:54,690 --> 00:09:57,250
Nu pop, efter sædvane,
tager ikke et argument.

204
00:09:57,250 --> 00:10:00,430
Med en stak, hele
punkt af bakken metafor

205
00:10:00,430 --> 00:10:03,450
er, at du ikke har diskretion
gå få at bakke, kan alt du skal gøre

206
00:10:03,450 --> 00:10:06,330
er pop øverste en fra
stakken, bare fordi.

207
00:10:06,330 --> 00:10:08,010
Det er, hvad disse data struktur gør.

208
00:10:08,010 --> 00:10:12,250
>> Så ved denne logik, hvis jeg
siger pop, hvad der kommer ud?

209
00:10:12,250 --> 00:10:13,080
Så 61.

210
00:10:13,080 --> 00:10:15,402
Så hvad der virkelig er computeren
vil gøre i hukommelsen?

211
00:10:15,402 --> 00:10:16,610
Hvad min kode skal gøre?

212
00:10:16,610 --> 00:10:20,330
Hvad ville du foreslå,
vi ændre på skærmen?

213
00:10:20,330 --> 00:10:23,410
Hvad skal ændres?

214
00:10:23,410 --> 00:10:24,960
Undskyld?

215
00:10:24,960 --> 00:10:26,334
Så vi slippe af med 61.

216
00:10:26,334 --> 00:10:27,500
Så jeg kan helt sikkert gøre det.

217
00:10:27,500 --> 00:10:28,640
Og jeg kan slippe af med 61.

218
00:10:28,640 --> 00:10:30,980
Og hvad andre så
Ændringen skal ske?

219
00:10:30,980 --> 00:10:33,160
Størrelse formentlig har at gå tilbage til to.

220
00:10:33,160 --> 00:10:34,210
Og så det er fint.

221
00:10:34,210 --> 00:10:36,690
Men vent et øjeblik, størrelse
et øjeblik siden var tre.

222
00:10:36,690 --> 00:10:38,240
Lad os bare gøre en hurtig tilregnelighed check.

223
00:10:38,240 --> 00:10:41,810
Hvordan vidste vi, at vi
ønskede at slippe af med 61?

224
00:10:41,810 --> 00:10:42,760
Fordi vi er popping.

225
00:10:42,760 --> 00:10:46,450
Og så jeg har denne anden ejendom størrelse.

226
00:10:46,450 --> 00:10:48,470
>> Vent et øjeblik, jeg er
tænker tilbage til uge to

227
00:10:48,470 --> 00:10:51,660
da vi begyndte at tale om
arrays, hvor dette var placering nul,

228
00:10:51,660 --> 00:10:55,920
dette var placering én, var dette sted
to, dette er placering tre, fire,

229
00:10:55,920 --> 00:10:58,460
det ligner det
forholdet mellem størrelse

230
00:10:58,460 --> 00:11:02,780
og det element, jeg vil fjerne
fra arrayet synes at bare være hvad?

231
00:11:02,780 --> 00:11:05,120
Størrelse minus en.

232
00:11:05,120 --> 00:11:07,786
Og så det er sådan som mennesker
vi ved 61 kommer først.

233
00:11:07,786 --> 00:11:09,160
Hvordan er computeren kommer til at vide?

234
00:11:09,160 --> 00:11:11,701
Når din kode, hvor du sandsynligvis
ønsker at gøre størrelsen minus én,

235
00:11:11,701 --> 00:11:14,950
så tre minus en er to, og at
betyder, at vi ønsker at slippe af med 61.

236
00:11:14,950 --> 00:11:18,000
Og så kan vi faktisk opdatere
størrelsen så størrelse nu

237
00:11:18,000 --> 00:11:20,300
går fra tre til kun to.

238
00:11:20,300 --> 00:11:24,520
Og bare for at være pedantisk, jeg vil
at foreslå, at jeg er færdig, ikke?

239
00:11:24,520 --> 00:11:27,660
Du foreslog intuitivt
korrekt jeg skulle slippe af med 61.

240
00:11:27,660 --> 00:11:30,700
Men har ikke jeg slags
slags sluppet af 61?

241
00:11:30,700 --> 00:11:33,790
Jeg har faktisk glemt
at det faktisk er der.

242
00:11:33,790 --> 00:11:37,680
Og tænker tilbage på PSET4, hvis du har læst
artiklen om retsvidenskab, PDF

243
00:11:37,680 --> 00:11:40,780
at vi havde jer læse, eller du
vil læse denne uge for PSET4.

244
00:11:40,780 --> 00:11:44,300
Husk på, at dette er faktisk relevant for
hele ideen om computer forensics.

245
00:11:44,300 --> 00:11:47,820
Hvad en computer generelt gør, er
det bare glemmer, hvor noget er,

246
00:11:47,820 --> 00:11:51,300
men det går ikke ind og ligesom
forsøge at ridse den ud eller overstyring

247
00:11:51,300 --> 00:11:54,560
disse bit med nuller og ettaller
eller en anden tilfældigt mønster

248
00:11:54,560 --> 00:11:56,690
medmindre du selv gør det med vilje.

249
00:11:56,690 --> 00:11:58,930
Så din intuition var
Okay, lad os slippe af med 61.

250
00:11:58,930 --> 00:12:00,650
Men i virkeligheden, behøver vi ikke at gider.

251
00:12:00,650 --> 00:12:04,040
Vi skal bare glemme, at
det er der ved at ændre vores størrelse.

252
00:12:04,040 --> 00:12:05,662
>> Nu er der et problem med denne stak.

253
00:12:05,662 --> 00:12:07,620
Hvis jeg holde skubbe tingene
på stakken, hvad er

254
00:12:07,620 --> 00:12:11,167
selvfølgelig kommer til at ske
på blot et par øjeblikke tid?

255
00:12:11,167 --> 00:12:12,500
Vi kommer til at løbe tør for plads.

256
00:12:12,500 --> 00:12:13,580
Og hvad gør vi?

257
00:12:13,580 --> 00:12:14,680
Vi er slags skruet.

258
00:12:14,680 --> 00:12:19,000
Denne gennemførelse ikke lade
os ændre størrelsen på array, fordi hjælp

259
00:12:19,000 --> 00:12:21,240
denne syntaks, hvis du
tænke tilbage til uge to,

260
00:12:21,240 --> 00:12:23,520
når du har erklæret
størrelsen af ​​et array,

261
00:12:23,520 --> 00:12:26,780
Vi har ikke set en mekanisme endnu hvor
du kan ændre størrelsen af ​​array.

262
00:12:26,780 --> 00:12:29,020
Og faktisk C ikke har denne funktion.

263
00:12:29,020 --> 00:12:32,524
Hvis du siger give mig fem
Nths, kalder dem numre,

264
00:12:32,524 --> 00:12:33,940
det er alt du vil få det.

265
00:12:33,940 --> 00:12:38,790
Så vi gør nu, som mandag den have
evnen til at udtrykke en opløsning

266
00:12:38,790 --> 00:12:42,480
selv om, vi bare nødt til at nappe
definitionen af ​​vores stack

267
00:12:42,480 --> 00:12:46,840
ikke være nogle hårdkodet array,
men blot at lagre en adresse.

268
00:12:46,840 --> 00:12:47,890
>> Nu, hvorfor er dette?

269
00:12:47,890 --> 00:12:51,690
Nu er vi bare nødt til at være fortrolig med
det faktum, at når mit program kører,

270
00:12:51,690 --> 00:12:53,730
Jeg formentlig vil
nødt til at spørge de menneskelige,

271
00:12:53,730 --> 00:12:55,110
hvor mange numre vil du gemme?

272
00:12:55,110 --> 00:12:56,776
Så input skal komme fra et sted.

273
00:12:56,776 --> 00:12:59,140
Men når jeg ved, at
nummer, så jeg kan bare

274
00:12:59,140 --> 00:13:02,470
bruge hvilken funktion at give
mig en luns af hukommelse?

275
00:13:02,470 --> 00:13:03,580
Jeg kan bruge malloc.

276
00:13:03,580 --> 00:13:06,710
Og jeg kan sige et vilkårligt antal
bytes Jeg vil tilbage til disse Nths.

277
00:13:06,710 --> 00:13:10,910
Og alt jeg har at gemme i numrene
variabel her inde i denne struct

278
00:13:10,910 --> 00:13:13,480
bør være hvad?

279
00:13:13,480 --> 00:13:18,440
Hvad der rent faktisk går ind i
numre i dette scenario?

280
00:13:18,440 --> 00:13:21,300
Ja, en pointer til den første
byte af denne klump hukommelse,

281
00:13:21,300 --> 00:13:24,940
eller mere specifikt, adressen
den første af disse bytes.

282
00:13:24,940 --> 00:13:27,300
Betyder ikke noget, hvis det er en
byte eller en milliard bytes,

283
00:13:27,300 --> 00:13:28,890
Jeg har bare brug for at bekymre sig om den første.

284
00:13:28,890 --> 00:13:31,530
For hvad malloc garantier og
mit operativsystem garantier,

285
00:13:31,530 --> 00:13:34,170
er, at bid af hukommelses I
får, går det at være sammenhængende.

286
00:13:34,170 --> 00:13:35,378
Der kommer ikke til at være huller.

287
00:13:35,378 --> 00:13:38,576
Så hvis jeg har bedt om 50
byte eller 1.000 bytes,

288
00:13:38,576 --> 00:13:40,450
de er alle kommer til at være
tilbage til tilbage til tilbage.

289
00:13:40,450 --> 00:13:44,500
Og så længe jeg kan huske, hvor stor, hvordan
meget jeg bad om, alt hvad jeg behøver at vide

290
00:13:44,500 --> 00:13:46,230
er den første adresse.

291
00:13:46,230 --> 00:13:48,660
>> Så nu har vi mulighed i kode.

292
00:13:48,660 --> 00:13:51,280
Omend, det vil tage os
mere tid til at skrive dette op,

293
00:13:51,280 --> 00:13:55,900
Vi kunne nu omfordele at hukommelsen ved
bare lagring af en anden adresse der

294
00:13:55,900 --> 00:13:59,060
hvis vi ønsker en større eller endda
en mindre bid af hukommelse.

295
00:13:59,060 --> 00:14:00,170
Så her til en afvejning.

296
00:14:00,170 --> 00:14:01,360
Nu får vi dynamik.

297
00:14:01,360 --> 00:14:03,350
Vi har stadig
contiguousness Jeg påstår.

298
00:14:03,350 --> 00:14:05,881
Fordi malloc vil give os
en sammenhængende klump hukommelse.

299
00:14:05,881 --> 00:14:08,630
Men det vil være en smerte i
halsen for os, programmøren,

300
00:14:08,630 --> 00:14:09,770
faktisk at kode.

301
00:14:09,770 --> 00:14:10,730
Det er bare mere arbejde.

302
00:14:10,730 --> 00:14:13,930
Vi har brug for kode beslægtet med, hvad jeg var
hamrer ud bare for et øjeblik siden.

303
00:14:13,930 --> 00:14:16,120
Meget gennemførligt, men det tilføjer kompleksitet.

304
00:14:16,120 --> 00:14:19,520
Og så udvikler tid, programmør
tid er endnu en ressource

305
00:14:19,520 --> 00:14:22,520
at vi måske nødt til at tilbringe
nogen tid at få nye funktioner.

306
00:14:22,520 --> 00:14:24,020
Og så selvfølgelig er der en kø.

307
00:14:24,020 --> 00:14:26,227
Vi vil ikke gå ind i denne
en i mange detaljer.

308
00:14:26,227 --> 00:14:27,560
Men det er meget ens i ånd.

309
00:14:27,560 --> 00:14:31,220
Jeg kunne implementere en kø, og
dens tilsvarende operationer,

310
00:14:31,220 --> 00:14:35,660
Sæt i kø eller dequeue, ligesom tilføje eller fjerne,
det er bare en amatør måde at sige det,

311
00:14:35,660 --> 00:14:38,100
Sæt i kø eller dequeue, som følger.

312
00:14:38,100 --> 00:14:41,170
Jeg kan bare give mig selv en struct
det igen har en række s array,

313
00:14:41,170 --> 00:14:44,000
det igen har en størrelse,
men hvorfor gør jeg nu brug

314
00:14:44,000 --> 00:14:46,940
at holde styr på forsiden af ​​en kø?

315
00:14:46,940 --> 00:14:50,630
Jeg behøvede ikke at vide
forsiden af ​​min stak.

316
00:14:50,630 --> 00:14:53,570
Tja, hvis jeg igen til en
queue-- lad os bare hårdt

317
00:14:53,570 --> 00:14:57,870
kode det som at have ligesom fem
heltal i her potentielt.

318
00:14:57,870 --> 00:15:00,940
Så det er nul, en, to, tre, fire.

319
00:15:00,940 --> 00:15:03,430
Dette vil være
kaldte numre igen.

320
00:15:03,430 --> 00:15:06,940
Og det vil blive kaldt størrelse.

321
00:15:06,940 --> 00:15:10,056
>> Hvorfor er det ikke tilstrækkeligt
at have bare størrelse?

322
00:15:10,056 --> 00:15:11,680
Nå, lad os skubbe de samme numre på.

323
00:15:11,680 --> 00:15:14,220
Så jeg pushed-- jeg kø, eller skubbes.

324
00:15:14,220 --> 00:15:20,150
Nu vil jeg enqueue 50, og derefter
51, og så 61, og dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Så det er enqueue.

326
00:15:21,070 --> 00:15:23,176
I kø 50, derefter 51, derefter 61.

327
00:15:23,176 --> 00:15:25,050
Og der ser identiske
til en stabel hidtil,

328
00:15:25,050 --> 00:15:27,190
bortset fra at jeg har brug for at lave en ændring.

329
00:15:27,190 --> 00:15:33,680
Jeg har brug for at opdatere denne størrelse, så jeg går
fra nul til én til to til tre nu.

330
00:15:33,680 --> 00:15:35,760
Hvordan kan jeg dequeue?

331
00:15:35,760 --> 00:15:36,890
Hvad sker der med dequeue?

332
00:15:36,890 --> 00:15:41,950
Hvem skal komme ud denne liste først
hvis det er den linje på Apple Store?

333
00:15:41,950 --> 00:15:42,780
Så 50.

334
00:15:42,780 --> 00:15:44,700
Så det er lidt tricky denne gang.

335
00:15:44,700 --> 00:15:47,880
Hvorimod sidste gang det var super
let at bare gøre størrelse minus én,

336
00:15:47,880 --> 00:15:51,440
Jeg kommer til slutningen af ​​min matrix effektivt
hvor tallene er, det fjerner 61.

337
00:15:51,440 --> 00:15:52,920
Men jeg ønsker ikke at fjerne 61.

338
00:15:52,920 --> 00:15:55,030
Jeg ønsker at tage 50, som
var der kl 5:00

339
00:15:55,030 --> 00:15:56,790
at line op til
nye iPhone eller whatnot.

340
00:15:56,790 --> 00:16:01,200
Og så for at slippe af med 50, jeg
kan ikke bare gøre det, ikke?

341
00:16:01,200 --> 00:16:02,547
Jeg kan krydse ud 50.

342
00:16:02,547 --> 00:16:04,380
Men vi sagde bare vi
behøver ikke at være så anal

343
00:16:04,380 --> 00:16:06,330
at ridse ud eller skjule data.

344
00:16:06,330 --> 00:16:08,090
Vi kan bare glemme, hvor det er.

345
00:16:08,090 --> 00:16:12,330
>> Men hvis jeg ændre min størrelse nu til
to, er det tilstrækkelig information

346
00:16:12,330 --> 00:16:15,711
at vide, hvad der foregår i mit kø?

347
00:16:15,711 --> 00:16:16,680
Ikke rigtig.

348
00:16:16,680 --> 00:16:19,830
Ligesom min størrelse er to, men
hvor er køen begynder,

349
00:16:19,830 --> 00:16:22,980
især hvis jeg stadig har
de samme numre i hukommelsen.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Så jeg har brug for at huske
nu hvor fronten er.

352
00:16:27,090 --> 00:16:29,630
Og så jeg foreslog op
der, vil vi lige har kaldt

353
00:16:29,630 --> 00:16:33,729
N'te foran, hvis oprindelige
værdi skulle have været hvad?

354
00:16:33,729 --> 00:16:35,270
Zero, blot begyndelsen på listen.

355
00:16:35,270 --> 00:16:40,876
Men nu foruden decrementing
størrelse, vi bare forøge foran.

356
00:16:40,876 --> 00:16:42,000
Nu her er et andet problem.

357
00:16:42,000 --> 00:16:43,030
Så når jeg holde.

358
00:16:43,030 --> 00:16:47,520
Formoder, at dette er antallet af
ligesom 121, 124, og derefter, for fanden,

359
00:16:47,520 --> 00:16:48,610
Jeg er ude af rummet.

360
00:16:48,610 --> 00:16:50,390
Men vent et øjeblik, jeg er ikke.

361
00:16:50,390 --> 00:16:55,630
Så på dette punkt i historien,
Antag, at størrelsen er en, to,

362
00:16:55,630 --> 00:17:00,370
tre, fire, så formode, at
størrelse er fire, foran er en,

363
00:17:00,370 --> 00:17:01,621
så 51 er på forsiden.

364
00:17:01,621 --> 00:17:04,329
Jeg ønsker at sætte et andet nummer her,
men, for fanden, jeg er ude af rummet.

365
00:17:04,329 --> 00:17:06,710
Men jeg er ikke rigtig, vel?

366
00:17:06,710 --> 00:17:11,192
Hvor kunne jeg sætte nogle
yderligere værdi, ligesom 171?

367
00:17:11,192 --> 00:17:13,400
Ja, jeg kunne bare lidt
gå tilbage derovre, ikke?

368
00:17:13,400 --> 00:17:18,161
Og derefter krydse ud 50, eller
bare overskrive den med 171.

369
00:17:18,161 --> 00:17:20,410
Og hvis du undrer dig over, hvorfor
vores tal fik så tilfældig,

370
00:17:20,410 --> 00:17:24,150
disse er almindeligt taget computer
videnskab kurser på Harvard efter CS50.

371
00:17:24,150 --> 00:17:27,510
Men det var en god optimering,
fordi nu er jeg ikke spilde plads.

372
00:17:27,510 --> 00:17:30,750
Jeg har stadig til at huske
hvor stor denne ting er total.

373
00:17:30,750 --> 00:17:31,500
Det er fem i alt.

374
00:17:31,500 --> 00:17:33,375
Fordi jeg ønsker ikke at
begynde at overskrive 51.

375
00:17:33,375 --> 00:17:36,260
Så nu er jeg stadig tør for plads,
så det samme problem som før.

376
00:17:36,260 --> 00:17:39,140
Men du kan se, hvor nu
i din kode, har du sandsynligvis

377
00:17:39,140 --> 00:17:41,910
nødt til at skrive lidt mere
kompleksitet at gøre det ske.

378
00:17:41,910 --> 00:17:44,510
Og i virkeligheden, hvad operatør
i C formentlig lader

379
00:17:44,510 --> 00:17:48,110
du magisk gøre dette cirkularitet?

380
00:17:48,110 --> 00:17:50,160
Ja modulo operatør,
procenttegnet.

381
00:17:50,160 --> 00:17:53,160
Så hvad er slags cool om en kø,
selv om vi holder tegning arrays

382
00:17:53,160 --> 00:17:56,520
da disse som lige linjer, hvis du
slags tænker over dette som krumning

383
00:17:56,520 --> 00:18:00,341
rundt som en cirkel, så bare
intuitivt den slags virker mentalt

384
00:18:00,341 --> 00:18:01,590
Jeg tror lidt mere rent.

385
00:18:01,590 --> 00:18:05,190
Du vil stadig nødt til at gennemføre
at mental model i kode.

386
00:18:05,190 --> 00:18:07,550
Så ikke så svært,
i sidste ende, at gennemføre,

387
00:18:07,550 --> 00:18:12,430
men vi stadig tabe den size-- snarere, det
evne til at ændre størrelse, medmindre vi gør dette.

388
00:18:12,430 --> 00:18:15,310
>> Vi er nødt til at slippe af array, vi
erstatte det med en enkelt pointer,

389
00:18:15,310 --> 00:18:20,010
og så et eller andet sted i min kode jeg har fået
et opkald hvilken funktion til rent faktisk at skabe

390
00:18:20,010 --> 00:18:23,720
array kaldte numre?

391
00:18:23,720 --> 00:18:26,190
Malloc eller en lignende
funktion, nøjagtigt.

392
00:18:26,190 --> 00:18:30,481
Eventuelle spørgsmål om stakke eller køer.

393
00:18:30,481 --> 00:18:30,980
Ja?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Godt spørgsmål.

396
00:18:34,240 --> 00:18:35,830
Hvad modulo ville du bruge her.

397
00:18:35,830 --> 00:18:38,520
Så i almindelighed, når der anvendes
mod, ville du gøre det

398
00:18:38,520 --> 00:18:40,620
med størrelsen af
Hele datastruktur.

399
00:18:40,620 --> 00:18:44,120
Så noget som fem eller kapacitet, hvis
det er konstant, er sandsynligvis involveret.

400
00:18:44,120 --> 00:18:47,100
Men bare gør modulo fem
sandsynligvis ikke er tilstrækkelig,

401
00:18:47,100 --> 00:18:51,380
fordi vi har brug for at vide at gøre vi
wrap omkring her eller her eller her.

402
00:18:51,380 --> 00:18:54,160
Så du er sikkert også
vil ønsker at involvere

403
00:18:54,160 --> 00:18:57,220
størrelsen af ​​ting, eller
den forreste variable samt.

404
00:18:57,220 --> 00:19:00,140
Så det er bare denne relativt
simpelt aritmetisk udtryk,

405
00:19:00,140 --> 00:19:02,000
men modulo ville være den vigtigste ingrediens.

406
00:19:02,000 --> 00:19:03,330
>> Så kortfilm, hvis du vil.

407
00:19:03,330 --> 00:19:05,780
En animation, at nogle
folk på et andet universitet

408
00:19:05,780 --> 00:19:08,060
sat sammen, at vi har
tilpasset til denne diskussion.

409
00:19:08,060 --> 00:19:12,630
Det indebærer Jack lære
fakta om køer og statistik.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Engang,
der var en fyr ved navn Jack.

412
00:19:21,890 --> 00:19:25,330
Da det kom til at få venner,
Jack havde ikke en evne.

413
00:19:25,330 --> 00:19:28,220
Så Jack gik til at tale med
mest populære fyr vidste han.

414
00:19:28,220 --> 00:19:30,920
Han gik til Lou og spurgte, hvad gør jeg?

415
00:19:30,920 --> 00:19:33,400
Lou så, at hans ven
var virkelig bedrøvet.

416
00:19:33,400 --> 00:19:36,050
Nå, begyndte han, bare
se, hvordan du er klædt.

417
00:19:36,050 --> 00:19:38,680
Har du ikke noget tøj
med et andet udseende?

418
00:19:38,680 --> 00:19:39,660
Ja, sagde Jack.

419
00:19:39,660 --> 00:19:40,840
Jeg sikker gør.

420
00:19:40,840 --> 00:19:43,320
Kom til mit hus og
Jeg vil vise dem til dig.

421
00:19:43,320 --> 00:19:44,550
Så de gik ud til Jack.

422
00:19:44,550 --> 00:19:47,520
Og Jack viste Lou kassen
hvor han holdt alle hans skjorter,

423
00:19:47,520 --> 00:19:49,260
og hans bukser, og hans sokker.

424
00:19:49,260 --> 00:19:52,290
Lou sagde, jeg ser du har
alt dit tøj i en bunke.

425
00:19:52,290 --> 00:19:54,870
Hvorfor tager du ikke bære nogle
andre en gang i et stykke tid?

426
00:19:54,870 --> 00:19:58,020
>> Jack sagde, godt, når jeg
Fjern tøj og sokker,

427
00:19:58,020 --> 00:20:00,780
Jeg vasker dem og sætte
dem væk i kassen.

428
00:20:00,780 --> 00:20:03,210
Derefter kommer den næste
morgenen, og op jeg hoppe.

429
00:20:03,210 --> 00:20:06,380
Jeg går til kassen og få
mit tøj fra toppen.

430
00:20:06,380 --> 00:20:09,070
Lou indså hurtigt
problemet med Jack.

431
00:20:09,070 --> 00:20:12,080
Han holdt tøj, cd'er,
og bøger i stakken.

432
00:20:12,080 --> 00:20:14,420
Da han nåede til
noget at læse eller at bære,

433
00:20:14,420 --> 00:20:17,100
han ville vælge den øverste bog eller undertøj.

434
00:20:17,100 --> 00:20:19,500
Så da han var færdig, han
ville sætte det højre back.

435
00:20:19,500 --> 00:20:21,970
Tilbage det ville gå, på toppen af ​​stakken.

436
00:20:21,970 --> 00:20:24,460
Jeg kender løsningen,
sagde en triumferende Loud.

437
00:20:24,460 --> 00:20:27,090
Du er nødt til at lære at
begynde at bruge en kø.

438
00:20:27,090 --> 00:20:29,870
Lou tog Jack tøj og
hang dem i skabet.

439
00:20:29,870 --> 00:20:32,710
Og da han havde tømt
kassen, han bare smed det.

440
00:20:32,710 --> 00:20:36,500
>> Så sagde han, nu Jack, i slutningen af
dagen, sætte dit tøj til venstre

441
00:20:36,500 --> 00:20:37,990
når du lægger dem væk.

442
00:20:37,990 --> 00:20:41,300
Så i morgen tidlig, når du
se solskin, får dit tøj

443
00:20:41,300 --> 00:20:43,440
til højre, fra slutningen af ​​linjen.

444
00:20:43,440 --> 00:20:44,880
Kan du ikke se? sagde Lou.

445
00:20:44,880 --> 00:20:46,370
Det vil være så rart.

446
00:20:46,370 --> 00:20:49,770
Du vil bære alt en gang
før du bære noget to gange.

447
00:20:49,770 --> 00:20:52,670
Og med alt i kø
i hans skab og hylde,

448
00:20:52,670 --> 00:20:55,160
Jack begyndte at føle
helt sikker på sig selv.

449
00:20:55,160 --> 00:20:59,720
Alle takket være Lou og
hans vidunderlige kø.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Okay, det er bedårende.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Så hvad der er blevet virkelig foregår
på under kølerhjelmen nu?

453
00:21:10,080 --> 00:21:12,370
At vi har pointere,
at vi har malloc,

454
00:21:12,370 --> 00:21:15,680
at vi har evnen til at skabe
bidder af hukommelse til os

455
00:21:15,680 --> 00:21:16,344
dynamisk.

456
00:21:16,344 --> 00:21:18,510
Så dette er et billede, vi
skimtes lige den anden dag.

457
00:21:18,510 --> 00:21:21,180
Vi har ikke rigtig dvæle
på det, men dette billede

458
00:21:21,180 --> 00:21:24,180
har stået på undersiden
hætten i uger nu.

459
00:21:24,180 --> 00:21:27,050
Og så dette repræsenterer, bare
et rektangel, som vi har tegnet,

460
00:21:27,050 --> 00:21:28,180
computerens hukommelse.

461
00:21:28,180 --> 00:21:31,850
Og måske din computer eller CS50
Id, har en gigabyte hukommelse eller RAM

462
00:21:31,850 --> 00:21:33,050
eller to gigabyte eller fire.

463
00:21:33,050 --> 00:21:34,450
Det gør ikke rigtig noget.

464
00:21:34,450 --> 00:21:37,240
Dit operativsystem
Windows eller Mac OS eller Linux,

465
00:21:37,240 --> 00:21:41,120
væsentlige giver dit program
at tro, at den har adgang

466
00:21:41,120 --> 00:21:42,982
til hele
computerens hukommelse,

467
00:21:42,982 --> 00:21:45,440
selvom du måske køre
flere programmer på én gang.

468
00:21:45,440 --> 00:21:46,990
Så i virkeligheden, er der ikke rigtig fungere.

469
00:21:46,990 --> 00:21:49,448
Men det er sådan en illusion
givet til alle dine programmer.

470
00:21:49,448 --> 00:21:53,110
Så hvis du havde to koncerter RAM, dette
er, hvordan computeren kan tænke på det.

471
00:21:53,110 --> 00:21:57,110
>> Nu tilfældigvis, en af ​​disse
ting, en af ​​disse segmenter af hukommelse,

472
00:21:57,110 --> 00:21:58,350
kaldes en stabel.

473
00:21:58,350 --> 00:22:01,680
Og faktisk enhver tid
hidtil skriftligt kode

474
00:22:01,680 --> 00:22:05,900
at du har kaldt en
funktion, for eksempel main.

475
00:22:05,900 --> 00:22:08,410
Husk på, at enhver tid jeg har
trukket computerens hukommelse,

476
00:22:08,410 --> 00:22:10,640
Jeg har altid trækker slags
halvdelen af ​​et rektangel her

477
00:22:10,640 --> 00:22:12,520
og ikke gider at tale
om hvad der er ovenfor.

478
00:22:12,520 --> 00:22:15,980
For når vigtigste kaldes, hævder jeg
at du får denne splint af hukommelse

479
00:22:15,980 --> 00:22:16,970
der går ned her.

480
00:22:16,970 --> 00:22:20,650
Og hvis vigtigste kaldes en funktion
Ligesom swap, godt swap går her.

481
00:22:20,650 --> 00:22:23,720
Og det viser sig, det er
hvor det ender.

482
00:22:23,720 --> 00:22:26,277
På noget, der hedder en stak
indersiden af ​​computerens hukommelse.

483
00:22:26,277 --> 00:22:28,360
Nu ved slutningen af ​​dagen,
dette er blot adresser.

484
00:22:28,360 --> 00:22:30,680
Det er ligesom byte nul,
byte én byte 2 mia.

485
00:22:30,680 --> 00:22:33,130
Men hvis du tænker over det
da dette rektangulære objekt,

486
00:22:33,130 --> 00:22:35,130
alt, hvad vi laver hver
gang vi kalder en funktion er

487
00:22:35,130 --> 00:22:37,180
lagdeling en ny skive hukommelse.

488
00:22:37,180 --> 00:22:41,700
Vi giver denne funktion en skive
af sin egen hukommelse at arbejde med.

489
00:22:41,700 --> 00:22:44,490
>> Og huske nu, at dette er vigtigt.

490
00:22:44,490 --> 00:22:46,400
For hvis vi har
noget som swap

491
00:22:46,400 --> 00:22:51,610
og to lokale variabler som A og B og
vi ændre disse værdier fra et og to

492
00:22:51,610 --> 00:22:55,130
til to og en, tilbagekaldelse
at når swap vender tilbage,

493
00:22:55,130 --> 00:22:58,330
det er som om denne skive
hukommelse er lige gået.

494
00:22:58,330 --> 00:23:00,080
I virkeligheden, er det stadig
der retsmedicinsk.

495
00:23:00,080 --> 00:23:01,940
Og noget er stadig faktisk er der.

496
00:23:01,940 --> 00:23:05,410
Men begrebsmæssigt, er det så
selvom det er helt væk.

497
00:23:05,410 --> 00:23:10,910
Og så main kender ikke nogen af ​​arbejdet
der blev gjort i denne swap funktion,

498
00:23:10,910 --> 00:23:14,890
medmindre det faktisk er gået i dem
argumenter ved pointer eller ved henvisning.

499
00:23:14,890 --> 00:23:17,790
Nu er den grundlæggende løsning
på dette problem med swap

500
00:23:17,790 --> 00:23:19,970
passerer ting efter adresse.

501
00:23:19,970 --> 00:23:23,250
Men det viser sig også, hvad der er
stået på ovenstående den del

502
00:23:23,250 --> 00:23:26,330
af rektanglet al denne tid er
men der er mere hukommelse deroppe.

503
00:23:26,330 --> 00:23:28,790
Og når du dynamisk
allokere hukommelse,

504
00:23:28,790 --> 00:23:32,020
uanset om det er inde i getString, som
vi har gjort for dig i CS50

505
00:23:32,020 --> 00:23:34,710
bibliotek, eller hvis du fyre
kalder malloc og spørge

506
00:23:34,710 --> 00:23:37,950
Operativsystemet for en luns af
hukommelse, betyder det ikke kommer fra stakken.

507
00:23:37,950 --> 00:23:40,960
Det kommer fra et andet sted
i computerens hukommelse

508
00:23:40,960 --> 00:23:42,220
der hedder bunke.

509
00:23:42,220 --> 00:23:43,430
Og det er ikke anderledes.

510
00:23:43,430 --> 00:23:44,285
Det er den samme RAM.

511
00:23:44,285 --> 00:23:45,160
Det er den samme hukommelse.

512
00:23:45,160 --> 00:23:49,080
Det er bare den RAM, der er op
der i stedet for hernede.

513
00:23:49,080 --> 00:23:50,750
>> Og så hvad betyder det?

514
00:23:50,750 --> 00:23:53,650
Tja, hvis din computer har
en begrænset mængde hukommelse

515
00:23:53,650 --> 00:23:57,450
og stakken vokser op, så
til at tale, og den bunke, i henhold

516
00:23:57,450 --> 00:23:59,349
til denne pil, vokser ned.

517
00:23:59,349 --> 00:24:01,140
Med andre ord, hver
gang du kalder malloc,

518
00:24:01,140 --> 00:24:03,430
du får en skive
hukommelse ovenfra,

519
00:24:03,430 --> 00:24:06,630
så måske en smule lavere, så lidt
lavere, hver gang du kalder malloc,

520
00:24:06,630 --> 00:24:10,100
den bunke, det er skik,
er slags vokser,

521
00:24:10,100 --> 00:24:11,950
vokser tættere og tættere på hvad?

522
00:24:11,950 --> 00:24:13,382
Stakken.

523
00:24:13,382 --> 00:24:14,840
Så betyder det synes som en god idé?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Jeg mener, hvor det er egentlig ikke klar
hvad du kan gøre, hvis du kun

526
00:24:22,140 --> 00:24:23,910
har en begrænset mængde hukommelse.

527
00:24:23,910 --> 00:24:25,200
Men det er helt sikkert dårligt.

528
00:24:25,200 --> 00:24:27,920
Disse to pile er på en
lynkursus for hinanden.

529
00:24:27,920 --> 00:24:31,930
>> Og det viser sig, at dårlige fyr, folk, der
er særligt godt med programmering,

530
00:24:31,930 --> 00:24:36,140
og forsøger at hacke sig ind computere,
kan udnytte denne virkelighed.

531
00:24:36,140 --> 00:24:38,290
Faktisk lad os overveje
lidt uddrag.

532
00:24:38,290 --> 00:24:41,350
Så dette er et eksempel kan du læse
om nærmere på Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Vi vil pege dig i
hvis nysgerrige artiklen.

534
00:24:43,100 --> 00:24:45,650
Men der er et angreb generelt
kendt som buffer overflow, der

535
00:24:45,650 --> 00:24:49,570
har eksisteret så længe mennesker
har haft evnen til at manipulere

536
00:24:49,570 --> 00:24:53,120
computerens hukommelse, især i C.
Så det er en meget vilkårlig program,

537
00:24:53,120 --> 00:24:55,130
men lad os læse det op fra bunden.

538
00:24:55,130 --> 00:24:57,650
Main ind argC char stjerne argv.

539
00:24:57,650 --> 00:24:59,830
Så det er et program, der tager
kommandolinjeargumenter.

540
00:24:59,830 --> 00:25:03,620
Og alle vigtigste er tilsyneladende opkald
en funktion, kalder det F for enkelhed.

541
00:25:03,620 --> 00:25:04,610
Og det passerer i hvad?

542
00:25:04,610 --> 00:25:05,490
Argv for én.

543
00:25:05,490 --> 00:25:09,320
Så det passerer ind F uanset
ordet er, at brugeren har indtastet

544
00:25:09,320 --> 00:25:11,500
ved prompten efter
programmets navn på alle.

545
00:25:11,500 --> 00:25:15,730
Så meget gerne Cæsar eller Vigenere, som
du måske huske at gøre med argv.

546
00:25:15,730 --> 00:25:16,680
>> Så hvad er F?

547
00:25:16,680 --> 00:25:19,760
F tager i en streng
som sit eneste argument,

548
00:25:19,760 --> 00:25:22,100
AKA en char stjerne, samme
ting, som en streng.

549
00:25:22,100 --> 00:25:24,920
Og det hedder vilkårligt
bar i dette eksempel.

550
00:25:24,920 --> 00:25:27,710
Og så char c 12,
bare i lægmandssprog,

551
00:25:27,710 --> 00:25:31,750
hvad der er char c beslag 12 gør for os?

552
00:25:31,750 --> 00:25:33,440
Hvad er det så?

553
00:25:33,440 --> 00:25:36,490
Allokering hukommelse, specielt
12 bytes for 12 tegn.

554
00:25:36,490 --> 00:25:36,990
Præcis.

555
00:25:36,990 --> 00:25:40,000
Og så den sidste linje, rør rundt og
kopi, har du sikkert ikke set.

556
00:25:40,000 --> 00:25:43,360
Dette er en streng kopi
funktion, hvis formål i livet

557
00:25:43,360 --> 00:25:48,160
er at kopiere sit andet argument
i sin første argument,

558
00:25:48,160 --> 00:25:51,190
men kun op til et
række bytes.

559
00:25:51,190 --> 00:25:53,860
Så den tredje argument siger,
hvor mange bytes skal du kopierer?

560
00:25:53,860 --> 00:25:56,720
Længden af ​​bar,
hvad brugeren har skrevet i.

561
00:25:56,720 --> 00:25:59,320
Og indholdet af
bar, at streng, er

562
00:25:59,320 --> 00:26:02,330
kopieres i hukommelsen pegede på ved C.

563
00:26:02,330 --> 00:26:04,060
>> Så det synes slags dumme, og det er.

564
00:26:04,060 --> 00:26:06,300
Det er en konstrueret eksempel,
men det er repræsentativt

565
00:26:06,300 --> 00:26:10,100
af en klasse af angrebsvektorer,
en måde at angribe et program.

566
00:26:10,100 --> 00:26:15,050
Alt er fint og godt, hvis brugeren
typer i et ord, der er 11 tegn

567
00:26:15,050 --> 00:26:18,040
eller færre, plus backslash nul.

568
00:26:18,040 --> 00:26:22,830
Hvad hvis brugeren skriver i mere end
11 eller 12 eller 20 eller 50 tegn?

569
00:26:22,830 --> 00:26:25,090
Hvad er dette program kommer til at gøre?

570
00:26:25,090 --> 00:26:29,360
Potentielt seg fejl. Det kommer
til blindt at kopiere alt i baren op

571
00:26:29,360 --> 00:26:31,750
dens længde, som er
bogstaveligt talt alt i baren,

572
00:26:31,750 --> 00:26:36,307
i adressefeltet pegede på C. Men C
har kun givet som forebyggende 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Men der er ingen yderligere kontrol.

574
00:26:37,640 --> 00:26:38,700
Der er ingen, hvis forholdene.

575
00:26:38,700 --> 00:26:40,580
Der er ingen fejlkontrol her.

576
00:26:40,580 --> 00:26:43,270
>> Og så hvad dette program er
kommer til at gøre, er bare blindt

577
00:26:43,270 --> 00:26:45,750
kopiere en ting til den anden.

578
00:26:45,750 --> 00:26:47,880
Og så hvis vi trækker denne
som et billede, her er

579
00:26:47,880 --> 00:26:49,860
blot en splint af hukommelsesplads.

580
00:26:49,860 --> 00:26:53,470
Så meddelelse nederst, vi
have den lokale variable bar.

581
00:26:53,470 --> 00:26:57,330
Så pointer, der kommer til store--
snarere, at lokale argument, der er

582
00:26:57,330 --> 00:26:58,672
skal opbevares strengen bar.

583
00:26:58,672 --> 00:27:00,380
Og så opdager bare
over den i en stabel,

584
00:27:00,380 --> 00:27:02,505
fordi hver gang du spørger
til hukommelsen på stakken,

585
00:27:02,505 --> 00:27:04,310
det går lidt
over det billedligt,

586
00:27:04,310 --> 00:27:06,270
varsel, at vi har fået 12 byte der.

587
00:27:06,270 --> 00:27:10,690
Den øverste venstre ene er C beslag nul og
nederst til højre man er C beslag 11.

588
00:27:10,690 --> 00:27:12,870
Det er bare, hvordan computerne
kommer til at lægge det ud.

589
00:27:12,870 --> 00:27:18,300
Så bare intuitivt, hvis bar har mere
end 12 tegn i alt, herunder

590
00:27:18,300 --> 00:27:25,790
det omvendt skråstreg nul, hvor er den
12 eller C beslag 12 kommer til at gå?

591
00:27:25,790 --> 00:27:28,440
Eller rettere hvor er det 12.
tegn eller det 13. tegn,

592
00:27:28,440 --> 00:27:30,900
den hundrededel karakter går
at ende i billedet?

593
00:27:30,900 --> 00:27:33,400
Over eller under?

594
00:27:33,400 --> 00:27:36,300
>> Ret, fordi selvom
stakken selv vokser opad,

595
00:27:36,300 --> 00:27:39,590
når du har lagt ting i
det, det konstruktionsmæssige grunde

596
00:27:39,590 --> 00:27:41,294
sætter hukommelsen fra top til bund.

597
00:27:41,294 --> 00:27:44,460
Så hvis du har fået mere end 12 bytes,
du vil begynde at overskrive bar.

598
00:27:44,460 --> 00:27:47,280
Nu, er en fejl, men det er
ikke virkelig en big deal.

599
00:27:47,280 --> 00:27:51,130
Men det er en big deal, fordi der er
flere ting foregår i hukommelsen.

600
00:27:51,130 --> 00:27:53,074
Så her er hvordan vi kan
sætte hej, skal være klar.

601
00:27:53,074 --> 00:27:54,490
Hvis jeg har skrevet i goddag ved prompten.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O skråstreg nul, ender inden
de 12 bytes, og vi er super sikker.

603
00:27:59,330 --> 00:28:00,330
Alt er godt.

604
00:28:00,330 --> 00:28:03,020
Men hvis jeg skriver noget
længere, er det potentielt

605
00:28:03,020 --> 00:28:05,860
kommer til at snige sig ind bar plads.

606
00:28:05,860 --> 00:28:08,405
Men værre endnu, viser det sig
ud al denne tid,

607
00:28:08,405 --> 00:28:11,530
selv om vi aldrig har talt om
det bliver stakken bruges til andre ting.

608
00:28:11,530 --> 00:28:13,560
Det er ikke bare lokale variable.

609
00:28:13,560 --> 00:28:15,100
>> C er et meget lavt niveau sprog.

610
00:28:15,100 --> 00:28:17,810
Og det slags hemmeligt
bruger stablen også

611
00:28:17,810 --> 00:28:21,260
at huske, når en
funktion kaldes, hvad

612
00:28:21,260 --> 00:28:26,040
adressen af ​​den tidligere funktion,
så det kan springe tilbage til denne funktion.

613
00:28:26,040 --> 00:28:29,980
Så når vigtigste opkald bytte, blandt
de ting skubbet på stakken

614
00:28:29,980 --> 00:28:34,380
er ikke bare swaps lokale variable,
eller sine argumenter, også hemmeligt skubbet

615
00:28:34,380 --> 00:28:37,510
på stakken som vist
ved den røde skive her,

616
00:28:37,510 --> 00:28:40,520
er adressen på vigtigste fysisk
i computerens hukommelse,

617
00:28:40,520 --> 00:28:44,180
således at når swap er gjort, computeren
kender jeg nødt til at gå tilbage til hovedsiden

618
00:28:44,180 --> 00:28:46,760
og slut udfører den primære funktion.

619
00:28:46,760 --> 00:28:51,960
Så det er farligt nu, fordi hvis
brugeren skriver i godt mere end goddag,

620
00:28:51,960 --> 00:28:57,030
således at brugerens input clobbers
eller overskriver at rød sektion,

621
00:28:57,030 --> 00:28:59,820
logisk, hvis computerens
bare gå til blindt antage

622
00:28:59,820 --> 00:29:03,830
at de bytes i den røde skive er
den adresse, hvortil den skal returnere,

623
00:29:03,830 --> 00:29:09,020
hvad hvis modstanderen er smart nok eller
heldig nok til at sætte en sekvens af bytes

624
00:29:09,020 --> 00:29:13,450
der, der ligner en adresse,
men det er adressen på koden

625
00:29:13,450 --> 00:29:18,730
at han eller hun ønsker computeren
til at udføre i stedet for main?

626
00:29:18,730 --> 00:29:21,670
>> Med andre ord, hvis det,
bruger er at skrive ved prompten,

627
00:29:21,670 --> 00:29:23,850
er ikke bare noget
uskadeligt ligesom goddag,

628
00:29:23,850 --> 00:29:28,210
men det er faktisk kode, der er tilsvarende
at slette alle denne brugers filer?

629
00:29:28,210 --> 00:29:30,060
Eller email deres adgangskode til mig?

630
00:29:30,060 --> 00:29:31,940
Eller begynde at logge deres
tastetryk, right?

631
00:29:31,940 --> 00:29:34,920
Der er en måde, lad os fastsætte dag,
at de kunne skrive i ikke bare hej

632
00:29:34,920 --> 00:29:36,711
verden eller deres navn,
de kunne i det væsentlige

633
00:29:36,711 --> 00:29:39,570
passere i kode, nuller og
dem, at computeren

634
00:29:39,570 --> 00:29:43,450
fejltagelser for både kode og en adresse.

635
00:29:43,450 --> 00:29:48,950
Så omend lidt abstrakt, hvis
brugertyper i nok kontradiktorisk kode

636
00:29:48,950 --> 00:29:52,330
at vi vil generalisere her som
A. A er angreb eller modstandere.

637
00:29:52,330 --> 00:29:53,140
Så bare dårlige ting.

638
00:29:53,140 --> 00:29:55,306
Vi er ligeglade med om
tal eller nuller eller dem

639
00:29:55,306 --> 00:29:59,470
i dag, sådan at du ender
overskrive den røde sektion,

640
00:29:59,470 --> 00:30:01,580
Bemærk, at sekvensen af ​​bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C nul otte nul.

642
00:30:05,020 --> 00:30:08,960
Og nu da Wikipedias artikel her
har foreslået, hvis du rent faktisk nu begynde

643
00:30:08,960 --> 00:30:12,460
mærkning af bytes i computerens
hukommelse, hvad Wikipedia-artikel er

644
00:30:12,460 --> 00:30:19,060
foreslår, er, at, hvad hvis adressen
af, at den øverste venstre byte er 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Med andre ord, hvis den dårlige fyr er
smart nok med hans eller hendes kode

646
00:30:22,200 --> 00:30:26,650
faktisk løber nummeret her som
svarer til adressen på koden

647
00:30:26,650 --> 00:30:29,180
han eller hun injiceret
i computeren, du

648
00:30:29,180 --> 00:30:31,050
kan narre computeren
til at gøre noget.

649
00:30:31,050 --> 00:30:34,140
Fjernelse af filer, e-mail
ting, sniffing din trafik,

650
00:30:34,140 --> 00:30:36,710
bogstaveligt talt noget kunne være
sprøjtes ind i computeren.

651
00:30:36,710 --> 00:30:39,220
Og så en buffer overflow
angreb på sin kerne

652
00:30:39,220 --> 00:30:43,530
er bare en dum, dum
altoverskyggende af et array, der

653
00:30:43,530 --> 00:30:45,840
havde ikke sine grænser kontrolleret.

654
00:30:45,840 --> 00:30:48,850
Og det er det, er super farlig
og samtidig super stærk

655
00:30:48,850 --> 00:30:52,560
i C er, at vi faktisk har
adgang til alle steder i hukommelsen.

656
00:30:52,560 --> 00:30:55,320
Det er op til os, de programmører,
der skriver den oprindelige kode

657
00:30:55,320 --> 00:30:59,330
at kontrollere darn længden af ​​en eventuel
arrays, at vi manipulerer.

658
00:30:59,330 --> 00:31:00,750
Så for at være klar, hvad er fix?

659
00:31:00,750 --> 00:31:03,190
Hvis vi ruller tilbage til denne
kode, jeg skal ikke bare

660
00:31:03,190 --> 00:31:08,000
ændre længden af ​​linjen, hvilket
ellers skal jeg være kontrol?

661
00:31:08,000 --> 00:31:10,620
Hvad skal jeg gøre for at
forhindre dette angreb helt?

662
00:31:10,620 --> 00:31:14,110
Jeg ønsker ikke at bare blindt sige
at du skal kopiere så mange bytes

663
00:31:14,110 --> 00:31:16,140
som er længden af ​​linjen.

664
00:31:16,140 --> 00:31:18,910
Jeg vil gerne sige, at kopiere som
mange bytes som er i bar

665
00:31:18,910 --> 00:31:24,090
op til den tildelte
hukommelse, eller 12 maksimalt.

666
00:31:24,090 --> 00:31:27,450
Så jeg har brug for en form for hvis betingelse
der gør kontrollere længden af ​​baren,

667
00:31:27,450 --> 00:31:32,800
men hvis den overstiger 12, vi bare hårdt kode
12 som den maksimale mulige afstand.

668
00:31:32,800 --> 00:31:35,910
Ellers såkaldte puffer
overflow angreb kan ske.

669
00:31:35,910 --> 00:31:38,451
I bunden af ​​disse objektglas,
Hvis du er nysgerrig for at læse mere

670
00:31:38,451 --> 00:31:41,200
er den faktiske oprindelige artikel
Hvis du gerne vil tage et kig.

671
00:31:41,200 --> 00:31:44,550
>> Men nu, blandt de priser
betalt her var ineffektivitet.

672
00:31:44,550 --> 00:31:46,680
Så det var en hurtig
lavt niveau kig på, hvad

673
00:31:46,680 --> 00:31:49,709
problemer kan opstå nu, at vi
har adgang til computerens hukommelse.

674
00:31:49,709 --> 00:31:51,750
Men et andet problem, vi
allerede snublede på mandag

675
00:31:51,750 --> 00:31:53,800
var bare den ineffektivitet
en sammenkædet liste.

676
00:31:53,800 --> 00:31:56,019
Vi er tilbage til lineær tid.

677
00:31:56,019 --> 00:31:57,560
Vi har ikke længere en sammenhængende array.

678
00:31:57,560 --> 00:31:58,980
Vi har ikke random access.

679
00:31:58,980 --> 00:32:00,710
Vi kan ikke bruge firkantede beslag notation.

680
00:32:00,710 --> 00:32:04,590
Vi bogstaveligt talt nødt til at bruge en while-løkke
som den jeg skrev for et øjeblik siden.

681
00:32:04,590 --> 00:32:09,740
Men på mandag, vi påstod, at vi kan
krybe tilbage i realm af effektivitet

682
00:32:09,740 --> 00:32:13,040
opnå noget, der er
logaritmisk måske, eller bedste endnu,

683
00:32:13,040 --> 00:32:16,120
måske endda noget, der er
såkaldte konstant tid.

684
00:32:16,120 --> 00:32:19,840
Så hvordan kan vi gøre det ved hjælp af disse nye
værktøj, disse adresser, disse pejlemærker,

685
00:32:19,840 --> 00:32:22,210
og gevindskæring ting i vores eget?

686
00:32:22,210 --> 00:32:23,960
Nå, formoder, at
her, disse er en flok

687
00:32:23,960 --> 00:32:27,170
af numre, som vi ønsker at gemme i et
datastruktur og søge effektivt.

688
00:32:27,170 --> 00:32:30,960
Vi kan absolut tilbage til uge
to, smid dem i et array,

689
00:32:30,960 --> 00:32:33,150
og søg dem ved hjælp af binær søgning.

690
00:32:33,150 --> 00:32:34,040
Opdel og erobre.

691
00:32:34,040 --> 00:32:37,720
Og i virkeligheden, du skrev
søgning binære i PSET3,

692
00:32:37,720 --> 00:32:40,100
hvor du implementeret finde programmet.

693
00:32:40,100 --> 00:32:40,890
Men ved du hvad.

694
00:32:40,890 --> 00:32:45,060
Der er sådan en mere
smart måde at gøre det på.

695
00:32:45,060 --> 00:32:47,390
Det er lidt mere
sofistikeret og det måske

696
00:32:47,390 --> 00:32:50,830
tillader os at se, hvorfor binær
søgning er så meget hurtigere.

697
00:32:50,830 --> 00:32:52,980
Først, lad os indføre
begrebet et træ.

698
00:32:52,980 --> 00:32:54,730
Hvilket skønt i
reality træer slags

699
00:32:54,730 --> 00:32:57,730
vokser som denne, i en verden af ​​computeren
videnskaben, de form for bliver nedadgående

700
00:32:57,730 --> 00:33:00,830
ligesom et stamtræ, hvor du har
dine bedsteforældre eller oldeforældre

701
00:33:00,830 --> 00:33:04,580
eller whatnot i toppen, patriarken og
matriarch af familien, bare én

702
00:33:04,580 --> 00:33:07,930
såkaldte rod, node, nedenfor
som er dens børn,

703
00:33:07,930 --> 00:33:11,442
under hvilken er dens børn, eller
sine efterkommere mere generelt.

704
00:33:11,442 --> 00:33:13,400
Og enhver hængende
bunden af ​​familien

705
00:33:13,400 --> 00:33:16,070
træ, ud over at være
yngste i familien,

706
00:33:16,070 --> 00:33:19,520
kan også bare være generisk
kaldes bladene af træet.

707
00:33:19,520 --> 00:33:21,800
>> Så dette er bare en flok
af ord og definitioner

708
00:33:21,800 --> 00:33:25,790
til noget, der hedder et træ i computer
videnskab, meget gerne et stamtræ.

709
00:33:25,790 --> 00:33:28,770
Men der er mere avanceret inkarnationer
træer, hvoraf den ene

710
00:33:28,770 --> 00:33:30,780
kaldes en binær søgning træ.

711
00:33:30,780 --> 00:33:34,380
Og du kan slags drille
fra hinanden, hvad denne ting gør.

712
00:33:34,380 --> 00:33:37,180
Tja, det er binære i hvilken forstand?

713
00:33:37,180 --> 00:33:41,455
Hvor kommer den binære kommer herfra?

714
00:33:41,455 --> 00:33:41,955
Undskyld?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Det er ikke så meget et enten eller.

717
00:33:47,210 --> 00:33:52,000
Det er mere, at hver af knudepunkterne har nogen
mere end to børn, som vi ser her.

718
00:33:52,000 --> 00:33:54,990
Generelt er en tree-- og
dine forældre og bedsteforældre

719
00:33:54,990 --> 00:33:57,640
kan have så mange børn eller
børnebørnene, som de rent faktisk ønsker,

720
00:33:57,640 --> 00:34:00,820
og så for eksempel der har vi tre
børn det højre hånd knude,

721
00:34:00,820 --> 00:34:05,480
men i et binært træ, en knude har
nul, en eller to børn maksimalt.

722
00:34:05,480 --> 00:34:08,496
Og det er en nice egenskab,
fordi hvis det er udjævnet med to,

723
00:34:08,496 --> 00:34:10,620
vi vil være i stand til
få en lille log bund to

724
00:34:10,620 --> 00:34:11,975
handling foregår her i sidste ende.

725
00:34:11,975 --> 00:34:13,350
Så vi har noget logaritmisk.

726
00:34:13,350 --> 00:34:14,558
Men mere om det i et øjeblik.

727
00:34:14,558 --> 00:34:19,810
Søgetræet betyder, at tallene er
anbragt således, at venstre barnets

728
00:34:19,810 --> 00:34:22,429
værdi er større end roden.

729
00:34:22,429 --> 00:34:26,010
Og dens højre barn er
større end roden.

730
00:34:26,010 --> 00:34:29,290
Med andre ord, hvis du tager nogen af ​​de
noder, cirklerne i dette billede,

731
00:34:29,290 --> 00:34:31,840
og ser på dens venstre
barn og dets ret barn,

732
00:34:31,840 --> 00:34:34,739
den første bør være mindre end,
den anden skal være større end.

733
00:34:34,739 --> 00:34:36,159
Så tilregnelighed tjekke 55.

734
00:34:36,159 --> 00:34:37,780
Det er tilbage barn er 33.

735
00:34:37,780 --> 00:34:38,620
Det er mindre end.

736
00:34:38,620 --> 00:34:40,929
55, dens højre barn er 77.

737
00:34:40,929 --> 00:34:41,783
Det er større end.

738
00:34:41,783 --> 00:34:43,199
Og det er en rekursiv definition.

739
00:34:43,199 --> 00:34:46,480
Vi kunne kontrollere hver en af ​​dem
noder og det samme mønster ville holde.

740
00:34:46,480 --> 00:34:49,389
>> Så hvad er rart i en
binær søgning træ, er

741
00:34:49,389 --> 00:34:52,204
at man kan vi gennemføre den
med en struct, ligesom dette.

742
00:34:52,204 --> 00:34:54,620
Og selvom vi smider
masser af strukturer på din,

743
00:34:54,620 --> 00:34:56,560
de er noget
intuitiv nu forhåbentlig.

744
00:34:56,560 --> 00:35:00,570
Syntaksen er stadig mystisk sikker,
men indholdet af en knude i denne

745
00:35:00,570 --> 00:35:02,786
context-- og vi holder
bruge ordet node,

746
00:35:02,786 --> 00:35:04,910
uanset om det er et rektangel
på skærmen eller en cirkel,

747
00:35:04,910 --> 00:35:08,970
det er bare nogle generiske beholder,
i dette tilfælde af et træ, som den

748
00:35:08,970 --> 00:35:11,780
vi så, vi har brug for et heltal
i hvert af knudepunkterne

749
00:35:11,780 --> 00:35:15,460
og så jeg har brug for to pointere peger
til venstre barnet og retten barn,

750
00:35:15,460 --> 00:35:16,590
henholdsvis.

751
00:35:16,590 --> 00:35:20,730
Så det er, hvordan vi måske
gennemføre det i en struct.

752
00:35:20,730 --> 00:35:22,315
Og hvordan kan jeg gennemføre det i koden?

753
00:35:22,315 --> 00:35:26,730
Nå, lad os tage en hurtig
se på dette lille eksempel.

754
00:35:26,730 --> 00:35:29,820
Det er ikke funktionel, men jeg har
kopieres og indsættes denne struktur.

755
00:35:29,820 --> 00:35:33,510
Og hvis min funktion for en binær
søgetræet kaldes søgning,

756
00:35:33,510 --> 00:35:36,980
og det tager to argumenter,
et heltal N og en pointer

757
00:35:36,980 --> 00:35:41,400
til et knudepunkt, så en pointer til træet
eller en pointer til roden af ​​et træ,

758
00:35:41,400 --> 00:35:43,482
hvordan kan jeg gå om at søge efter N?

759
00:35:43,482 --> 00:35:45,440
Nå, først, fordi jeg er
beskæftiger sig med pointere,

760
00:35:45,440 --> 00:35:46,750
Jeg har tænkt mig at gøre en sanity check.

761
00:35:46,750 --> 00:35:54,279
Hvis træet ligemænd lig nul, er N
i dette træ eller ikke i dette træ?

762
00:35:54,279 --> 00:35:55,070
Det kan ikke være, ikke?

763
00:35:55,070 --> 00:35:56,870
Hvis jeg forbi null,
der er ikke noget der.

764
00:35:56,870 --> 00:35:59,230
Jeg kan lige så godt bare
blindt sige return false.

765
00:35:59,230 --> 00:36:04,050
Hvis du giver mig noget, jeg kan vel ikke
finde nogen tal N. Så hvad ellers kunne jeg

766
00:36:04,050 --> 00:36:04,750
Tjek nu?

767
00:36:04,750 --> 00:36:12,830
Jeg har tænkt mig at sige godt andet, hvis N er
mindre end hvad der er på træet node

768
00:36:12,830 --> 00:36:16,300
at jeg har været afleveret N-værdi.

769
00:36:16,300 --> 00:36:20,270
Med andre ord, hvis antallet er jeg
søger, N, er mindre end den node

770
00:36:20,270 --> 00:36:21,340
at jeg ser på.

771
00:36:21,340 --> 00:36:23,190
Og node jeg søger
på kaldes træ,

772
00:36:23,190 --> 00:36:26,370
og husker fra det foregående eksempel
at komme på værdien i en pegepind,

773
00:36:26,370 --> 00:36:28,310
Jeg bruger pilen notation.

774
00:36:28,310 --> 00:36:35,960
Så hvis N er mindre end træ pil
N, jeg ønsker at begrebsmæssigt gå til venstre.

775
00:36:35,960 --> 00:36:38,590
Hvordan formulerer jeg du søger, tilbage?

776
00:36:38,590 --> 00:36:41,560
For at være klar, hvis det er
billedet pågældende

777
00:36:41,560 --> 00:36:44,612
og jeg har bestået, at øverste
arrow der er pegende nedad.

778
00:36:44,612 --> 00:36:45,570
Det er mit træ pointer.

779
00:36:45,570 --> 00:36:48,060
Jeg peger på roden af ​​træet.

780
00:36:48,060 --> 00:36:52,100
Og jeg leder sige, for
antallet 44, vilkårligt.

781
00:36:52,100 --> 00:36:55,300
Er 44 mindre end eller
på over 55 naturligvis?

782
00:36:55,300 --> 00:36:56,360
Så det er mindre end.

783
00:36:56,360 --> 00:36:58,760
Og så dette, hvis betingelse gælder.

784
00:36:58,760 --> 00:37:03,981
Så begrebsmæssigt, hvad ønsker jeg at
søge næste hvis jeg leder efter 44?

785
00:37:03,981 --> 00:37:04,480
Ja?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Præcis, jeg ønsker at
søg venstre barn,

788
00:37:11,100 --> 00:37:12,789
eller venstre undertræ af dette billede.

789
00:37:12,789 --> 00:37:14,830
Og i virkeligheden, så lad mig igennem
billedet hernede

790
00:37:14,830 --> 00:37:17,770
for bare et øjeblik, da
Jeg kan ikke ridse det ud.

791
00:37:17,770 --> 00:37:21,150
Hvis jeg starter her ved 55, og
Jeg ved, at værdien 44

792
00:37:21,150 --> 00:37:23,180
Jeg leder efter, er at
venstre, det er sådan

793
00:37:23,180 --> 00:37:26,010
ligesom rive telefonbog
halvdelen eller rive træet i halve.

794
00:37:26,010 --> 00:37:29,660
Jeg behøver ikke længere at bekymre sig om
hele denne halvdel af træet.

795
00:37:29,660 --> 00:37:33,270
Og dog, mærkeligt med hensyn til
struktur, denne ting herovre, at

796
00:37:33,270 --> 00:37:36,682
starter med 33, at selv
er en binær søgning træ.

797
00:37:36,682 --> 00:37:39,890
Jeg sagde ordet rekursive før, fordi
faktisk er det en datastruktur,

798
00:37:39,890 --> 00:37:41,707
per definition er rekursiv.

799
00:37:41,707 --> 00:37:44,540
Du har måske et træ, der er det
store, men hver eneste af sine børn

800
00:37:44,540 --> 00:37:46,870
repræsenterer et træ bare lidt mindre.

801
00:37:46,870 --> 00:37:50,910
I stedet for at det er bedstefar
eller bedstemor, nu er det bare mor

802
00:37:50,910 --> 00:37:54,300
eller-- jeg kan ikke say-- ikke mor
eller far, der ville være underligt.

803
00:37:54,300 --> 00:37:59,000
I stedet de to børn der
ville være som bror og søster.

804
00:37:59,000 --> 00:38:01,120
En ny generation af stamtræet.

805
00:38:01,120 --> 00:38:02,900
Men strukturelt, det er den samme idé.

806
00:38:02,900 --> 00:38:06,790
Og det viser sig jeg har en funktion
som kan jeg søge en binær søgning

807
00:38:06,790 --> 00:38:07,290
træ.

808
00:38:07,290 --> 00:38:08,680
Det kaldes søgning.

809
00:38:08,680 --> 00:38:17,870
Jeg søger efter N i træ pil til venstre
ellers hvis N er større end værdien

810
00:38:17,870 --> 00:38:18,870
at jeg er i øjeblikket på.

811
00:38:18,870 --> 00:38:20,800
55 i historien for et øjeblik siden.

812
00:38:20,800 --> 00:38:23,780
Jeg har en funktion kaldet
søgning, som jeg kan bare

813
00:38:23,780 --> 00:38:29,660
pass N dette, og rekursivt søge
sub-træet og bare tilbagevenden

814
00:38:29,660 --> 00:38:30,620
hvad det så svaret.

815
00:38:30,620 --> 00:38:33,530
Else Jeg har fået nogle endelige base case her.

816
00:38:33,530 --> 00:38:35,310
>> Hvad er det sidste tilfældet?

817
00:38:35,310 --> 00:38:36,570
Tree er enten nul.

818
00:38:36,570 --> 00:38:39,980
Værdien jeg enten leder efter, er
mindre end det eller større end den

819
00:38:39,980 --> 00:38:42,610
eller lig med den.

820
00:38:42,610 --> 00:38:44,750
Og jeg kunne sige lige
lige, men det er logisk

821
00:38:44,750 --> 00:38:46,500
svarende til blot at sige andet her.

822
00:38:46,500 --> 00:38:49,150
Så sandt er, hvordan jeg finder noget.

823
00:38:49,150 --> 00:38:51,710
Så forhåbentlig dette er en
endnu mere overbevisende eksempel

824
00:38:51,710 --> 00:38:54,900
end den dumme sigma-funktionen
vi gjorde et par foredrag tilbage,

825
00:38:54,900 --> 00:38:58,360
hvor det var lige så let at bruge en løkke
at tælle op alle de numre fra én

826
00:38:58,360 --> 00:39:02,390
til N. Her med en datastruktur
at selv er rekursivt

827
00:39:02,390 --> 00:39:07,050
defineret og rekursivt trukket, nu er vi
har evnen til at udtrykke os

828
00:39:07,050 --> 00:39:09,780
i kode, selv er rekursivt.

829
00:39:09,780 --> 00:39:12,580
Så dette er nøjagtig den samme kode her.

830
00:39:12,580 --> 00:39:14,400
>> Så hvilke andre problemer kan vi løse?

831
00:39:14,400 --> 00:39:18,160
Så en hurtig skridt væk fra
træer for bare et øjeblik.

832
00:39:18,160 --> 00:39:20,130
Her er, siger den tyske flag.

833
00:39:20,130 --> 00:39:22,020
Og der er helt klart en
mønster dette flag.

834
00:39:22,020 --> 00:39:23,811
Og der er masser af
flag i verden, der

835
00:39:23,811 --> 00:39:27,560
er så simpelt som dette i form
af deres farver og mønstre.

836
00:39:27,560 --> 00:39:31,930
Men formoder, at dette er lagret som en
.GIF Eller en JPEG eller bitmap, eller en ping,

837
00:39:31,930 --> 00:39:34,240
enhver grafisk filformat
som du er fortrolig,

838
00:39:34,240 --> 00:39:36,460
hvoraf vi er
spiller med i PSET4.

839
00:39:36,460 --> 00:39:41,550
Dette synes ikke værd at gemme
sort pixel, sort pixel, sort pixel,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, en hel masse
sorte pixels for første scanlinie,

841
00:39:44,790 --> 00:39:47,430
eller række, så en hel masse
det samme, så en hel masse

842
00:39:47,430 --> 00:39:49,530
af det samme, og derefter en
hel masse røde pixels,

843
00:39:49,530 --> 00:39:53,020
røde pixels, rød pixel, så en hel
bundt af gule pixels, gul, ikke?

844
00:39:53,020 --> 00:39:55,050
>> Der er sådan ineffektivitet her.

845
00:39:55,050 --> 00:39:59,040
Hvordan ville du intuitivt
komprimere tyske flag

846
00:39:59,040 --> 00:40:01,320
hvis gennemføre det som en fil?

847
00:40:01,320 --> 00:40:04,940
Ligesom Hvilke oplysninger kan vi ikke
gider at lagre på disk for

848
00:40:04,940 --> 00:40:08,040
at mindske vores filstørrelsen fra ligesom
en megabyte til en kilobyte, noget

849
00:40:08,040 --> 00:40:09,430
mindre?

850
00:40:09,430 --> 00:40:13,130
Hvori ligger den redundans
her for at være klar?

851
00:40:13,130 --> 00:40:13,880
Hvad kunne du gøre?

852
00:40:13,880 --> 00:40:14,380
Ja?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Præcis.

855
00:40:21,970 --> 00:40:24,550
Hvorfor ikke i stedet huske
farven på hver pixel darn

856
00:40:24,550 --> 00:40:28,200
ligesom du laver i PSET4
med bitmap filformat,

857
00:40:28,200 --> 00:40:32,060
hvorfor du ikke bare repræsenterer
kolonnen længst til venstre af pixels, for eksempel

858
00:40:32,060 --> 00:40:35,370
en flok sorte pixels, en flok
af rødt, og en flok gul,

859
00:40:35,370 --> 00:40:39,210
og så bare en eller anden måde at kode
idé af Gentag dette 100 gange

860
00:40:39,210 --> 00:40:41,020
eller gentage dette 1.000 gange?

861
00:40:41,020 --> 00:40:43,430
Hvor 100 eller 1.000 er
bare et heltal, så du

862
00:40:43,430 --> 00:40:47,290
kan slippe af sted med blot et enkelt nummer
i stedet for hundreder eller tusinder

863
00:40:47,290 --> 00:40:48,270
yderligere pixels.

864
00:40:48,270 --> 00:40:50,990
Og ja, det er, hvordan vi
kunne komprimere den tyske flag.

865
00:40:50,990 --> 00:40:51,490
Og

866
00:40:51,490 --> 00:40:53,470
Nu hvad med fransk flag?

867
00:40:53,470 --> 00:40:58,930
Og lidt en slags
mental øvelse, som flag

868
00:40:58,930 --> 00:41:01,040
kan komprimeres mere på disken?

869
00:41:01,040 --> 00:41:05,720
Det tyske flag eller fransk
flag, hvis vi tager denne fremgangsmåde?

870
00:41:05,720 --> 00:41:08,490
Den tyske flag, fordi der er
mere horisontal redundans.

871
00:41:08,490 --> 00:41:12,190
Og ved design, mange grafiske fil
formater rent faktisk arbejde som skanderingslinier

872
00:41:12,190 --> 00:41:12,830
vandret.

873
00:41:12,830 --> 00:41:14,674
De kunne arbejde
lodret, lige menneskeheden

874
00:41:14,674 --> 00:41:17,090
besluttet år siden, at vi vil
generelt tænke på ting rækken

875
00:41:17,090 --> 00:41:18,880
rækkevis i stedet for søjle for søjle.

876
00:41:18,880 --> 00:41:20,820
Så ja, hvis du var
at se på filen

877
00:41:20,820 --> 00:41:24,670
størrelse med en tysk flag og en fransk
flag, så længe opløsningen er

878
00:41:24,670 --> 00:41:27,530
det samme, den samme bredde
og højde, denne ene

879
00:41:27,530 --> 00:41:31,580
her vil være større, fordi du
nødt til at gentage dig selv tre gange.

880
00:41:31,580 --> 00:41:35,570
Du skal angive blå, gentag
dig selv, hvid, gentage dig selv, rød,

881
00:41:35,570 --> 00:41:36,740
gentage dig selv.

882
00:41:36,740 --> 00:41:39,000
Du kan ikke bare gå hele
vejen til højre.

883
00:41:39,000 --> 00:41:41,200
Og som en sidebemærkning, at gøre
rydde komprimering

884
00:41:41,200 --> 00:41:43,910
er overalt, hvis disse er
fire rammer fra en video-- du

885
00:41:43,910 --> 00:41:45,890
kunne huske, at en film
eller video er generelt

886
00:41:45,890 --> 00:41:47,286
ligesom 29 eller 30 billeder i sekundet.

887
00:41:47,286 --> 00:41:50,410
Det er ligesom en lille flip bog, hvor du
bare se billedet, billede, billede, billede,

888
00:41:50,410 --> 00:41:54,410
billede bare super hurtigt, så det ligner
aktørerne på skærmen bevæger sig.

889
00:41:54,410 --> 00:41:57,130
Her er en humlebi på
toppen af ​​en buket blomster.

890
00:41:57,130 --> 00:41:59,790
Og selv om det kan være slags
svært at se ved første øjekast,

891
00:41:59,790 --> 00:42:04,020
det eneste, der bevæger sig i
denne film er bi.

892
00:42:04,020 --> 00:42:06,880
>> Hvad er dum om opbevaring
video komprimeret?

893
00:42:06,880 --> 00:42:11,420
Det er lidt spild at gemme video
som fire næsten identiske billeder,

894
00:42:11,420 --> 00:42:13,670
adskiller sig kun i det omfang, hvor Bee.

895
00:42:13,670 --> 00:42:16,280
Du kan smide de fleste
af disse oplysninger

896
00:42:16,280 --> 00:42:20,190
og husker kun, for eksempel,
den første ramme og den sidste ramme,

897
00:42:20,190 --> 00:42:22,180
keyframes Hvis du har
nogensinde hørt ordet,

898
00:42:22,180 --> 00:42:24,337
og bare gemme i
midten, hvor bien er.

899
00:42:24,337 --> 00:42:26,170
Og du behøver ikke at
gemme alle de lyserøde,

900
00:42:26,170 --> 00:42:28,330
og den blå, og
grønne værdier.

901
00:42:28,330 --> 00:42:31,200
Så det er kun at sige, at
komprimering er overalt.

902
00:42:31,200 --> 00:42:34,900
Det er en teknik, vi ofte bruger
eller tage for givet disse dage.

903
00:42:34,900 --> 00:42:38,750
>> Men hvordan kan du komprimere tekst?

904
00:42:38,750 --> 00:42:40,450
Hvordan kan du gå om at komprimere tekst?

905
00:42:40,450 --> 00:42:45,410
Nå, hver af personerne i
ASCII er én byte eller otte bits.

906
00:42:45,410 --> 00:42:47,360
Og der er slags dum, ikke?

907
00:42:47,360 --> 00:42:51,160
Fordi du sandsynligvis type A
og E og I og O og U en masse

908
00:42:51,160 --> 00:42:55,270
oftere end som W eller Q eller Z,
afhængigt af hvilket sprog

909
00:42:55,270 --> 00:42:56,610
du skriver sikkert.

910
00:42:56,610 --> 00:42:59,600
Og så hvorfor bruger vi
otte bits for hvert bogstav,

911
00:42:59,600 --> 00:43:02,040
herunder de mindst
populære breve, ikke?

912
00:43:02,040 --> 00:43:05,300
Hvorfor ikke bruge færre bit til
super populære bogstaver,

913
00:43:05,300 --> 00:43:07,760
Ligesom E, de ting du gætte
først i Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
og bruge flere bit for
de mindre populære bogstaver?

915
00:43:10,450 --> 00:43:10,950
Hvorfor?

916
00:43:10,950 --> 00:43:13,130
Fordi vi bare gå til
bruge dem mindre hyppigt.

917
00:43:13,130 --> 00:43:15,838
>> Tja, det viser sig, at der har
været forsøg på at gøre dette.

918
00:43:15,838 --> 00:43:18,630
Og hvis du husker fra lønklasse
skole eller gymnasium, morsekode.

919
00:43:18,630 --> 00:43:20,400
Morsekode har prikker
og streger, der kan være

920
00:43:20,400 --> 00:43:24,270
overføres langs en ledning som
lyde eller signaler af en slags.

921
00:43:24,270 --> 00:43:25,930
Men Morse kode er en super ren.

922
00:43:25,930 --> 00:43:29,010
Det er lidt af et binært system
at du har prikker eller streger.

923
00:43:29,010 --> 00:43:30,977
Men hvis du ser for eksempel, to prikker.

924
00:43:30,977 --> 00:43:33,810
Eller hvis du tænker tilbage til operatøren
der går sådan bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
bip, rammer en lille trigger
der overfører et signal,

926
00:43:36,760 --> 00:43:40,360
Hvis du, modtageren modtager to
prikker, hvilket budskab har du modtaget?

927
00:43:40,360 --> 00:43:43,490
Helt vilkårlig.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Eller hvad om-- eller jeg?

931
00:43:47,500 --> 00:43:49,570
Måske var det blot to E ret?

932
00:43:49,570 --> 00:43:52,480
Så der er dette problem
af decodability med Morse

933
00:43:52,480 --> 00:43:54,890
kode, hvorved medmindre
person, sende dig beskeden

934
00:43:54,890 --> 00:43:59,510
faktisk holder pause, så du kan sortere på
se eller høre hullerne mellem bogstaverne,

935
00:43:59,510 --> 00:44:02,990
det er ikke nok bare at
sende en strøm af nuller og ettaller,

936
00:44:02,990 --> 00:44:05,610
eller prikker og streger,
fordi der er tvetydighed.

937
00:44:05,610 --> 00:44:08,640
E er en enkelt prik, så hvis du
se to prikker eller hører to prikker,

938
00:44:08,640 --> 00:44:11,254
måske er det to E 's eller måske er det en I.

939
00:44:11,254 --> 00:44:13,670
Så vi har brug for et system, der er en
lidt mere klog end det.

940
00:44:13,670 --> 00:44:16,851
Så en mand ved navn Huffman år
siden kom op med netop dette.

941
00:44:16,851 --> 00:44:18,600
Så vi bare
at tage et hurtigt blik

942
00:44:18,600 --> 00:44:20,114
hvordan træer er relevant for dette.

943
00:44:20,114 --> 00:44:22,530
Antag, at dette er en
dumme meddelelse, du vil sende,

944
00:44:22,530 --> 00:44:26,342
sammensat af lige A, B, C s D's og E s,
men der er en masse redundans her.

945
00:44:26,342 --> 00:44:27,550
Det er ikke ment til at være engelsk.

946
00:44:27,550 --> 00:44:28,341
Det er ikke krypteret.

947
00:44:28,341 --> 00:44:30,540
Det er bare en dum besked
med masser af gentagelser.

948
00:44:30,540 --> 00:44:34,010
Så hvis du faktisk regne ud hele
A s, BS, C'er, D's og E s, her er

949
00:44:34,010 --> 00:44:34,890
frekvensen.

950
00:44:34,890 --> 00:44:37,800
20% af bogstaverne er
A 's, 45% af bogstaverne

951
00:44:37,800 --> 00:44:39,660
er E s, og tre andre frekvenser.

952
00:44:39,660 --> 00:44:41,960
Vi tælles op der manuelt
og bare gjorde det math.

953
00:44:41,960 --> 00:44:44,579
>> Så det viser sig, at
Huffman, for nogen tid siden,

954
00:44:44,579 --> 00:44:46,620
indså, at, du ved
hvad, hvis jeg begynder bygning

955
00:44:46,620 --> 00:44:51,172
et træ eller skov af træer, hvis du vil,
som følger, kan jeg gøre følgende.

956
00:44:51,172 --> 00:44:53,880
Jeg har tænkt mig at give en node til hver
af de breve, som jeg holder af

957
00:44:53,880 --> 00:44:55,530
og jeg har tænkt mig at gemme
indersiden af ​​det pågældende knudepunkt

958
00:44:55,530 --> 00:44:58,610
frekvenserne som floating point
værdi, eller du kan bruge det en N, også,

959
00:44:58,610 --> 00:45:00,210
men vi vil bare bruge en float her.

960
00:45:00,210 --> 00:45:03,100
Og algoritmen, som
foreslog han er, at du

961
00:45:03,100 --> 00:45:07,210
tager denne skov af enkelt node
træer, så super korte træer,

962
00:45:07,210 --> 00:45:11,920
og du begynder at forbinde dem med
nye grupper, nye forældre, hvis du vil.

963
00:45:11,920 --> 00:45:16,150
Og du gør dette ved at vælge den
to mindste frekvenser ad gangen.

964
00:45:16,150 --> 00:45:18,110
Så jeg tog 10% og 10%.

965
00:45:18,110 --> 00:45:19,090
Jeg opretter en ny knude.

966
00:45:19,090 --> 00:45:20,910
Og jeg kalder den nye knude 20%.

967
00:45:20,910 --> 00:45:22,750
>> Hvilke to knuder jeg kombinere næste?

968
00:45:22,750 --> 00:45:23,810
Det er lidt tvetydig.

969
00:45:23,810 --> 00:45:26,643
Så der er nogle hjørne sager til
overveje, men at holde tingene smuk,

970
00:45:26,643 --> 00:45:29,300
Jeg har tænkt mig at vælge 20% -
Jeg vil nu ignorere børnene.

971
00:45:29,300 --> 00:45:33,640
Jeg har tænkt mig at vælge 20% og
15% og tegne to nye kanter.

972
00:45:33,640 --> 00:45:35,624
Og nu hvor to knuder
kan jeg logisk kombinere?

973
00:45:35,624 --> 00:45:38,540
Ignorere alle børnene, alle de
børnebørn, bare se på rødderne

974
00:45:38,540 --> 00:45:39,070
nu.

975
00:45:39,070 --> 00:45:42,220
Hvilke to knudepunkter skal jeg binde sammen?

976
00:45:42,220 --> 00:45:44,530
Punkt to og 0,35.

977
00:45:44,530 --> 00:45:45,890
Så lad mig tegne to nye kanter.

978
00:45:45,890 --> 00:45:47,570
Og så har jeg kun fik én til venstre.

979
00:45:47,570 --> 00:45:48,650
Så her er et træ.

980
00:45:48,650 --> 00:45:51,160
Og det er blevet trukket med vilje
at se slags smuk,

981
00:45:51,160 --> 00:45:55,870
men bemærker, at kanterne har
også blevet mærket nul og én.

982
00:45:55,870 --> 00:45:59,510
Så alle de venstre kanter er nul
vilkårligt, men konsekvent.

983
00:45:59,510 --> 00:46:01,170
Alle højre kanter er dem.

984
00:46:01,170 --> 00:46:05,070
>> Og så hvad Hoffman foreslået er,
hvis du ønsker at repræsentere et B,

985
00:46:05,070 --> 00:46:10,080
i stedet repræsenterer antallet 66 som
en ASCII som er otte hele bits,

986
00:46:10,080 --> 00:46:13,360
ved du hvad, bare butik
mønsteret nul, nul, nul,

987
00:46:13,360 --> 00:46:17,030
nul, fordi det er den vej
fra mit træ, Hr Huffman s træet,

988
00:46:17,030 --> 00:46:18,600
til bladet fra roden.

989
00:46:18,600 --> 00:46:20,970
Hvis du ønsker at gemme en
E derimod ikke

990
00:46:20,970 --> 00:46:26,290
Send otte bits, der repræsenterer en E.
I stedet sende hvad mønster af bits?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
Og hvad er nice om dette er
at E er den mest populære skrivelse,

993
00:46:30,410 --> 00:46:32,340
og du bruger den
korteste kode til det.

994
00:46:32,340 --> 00:46:34,090
Det næste mest populære
brev ligner det

995
00:46:34,090 --> 00:46:37,380
var A. Og så hvor mange bits
han foreslår at bruge til det?

996
00:46:37,380 --> 00:46:38,270
Zero, en.

997
00:46:38,270 --> 00:46:41,060
>> Og fordi det er implementeret
som dette træ, for nu

998
00:46:41,060 --> 00:46:43,350
lad mig fastsætte der er
ingen tvetydighed som i Morse

999
00:46:43,350 --> 00:46:46,090
kode, fordi alle
bogstaver, du holder af

1000
00:46:46,090 --> 00:46:48,780
er i slutningen af ​​disse kanter.

1001
00:46:48,780 --> 00:46:50,580
Så det er bare en
anvendelse af et træ.

1002
00:46:50,580 --> 00:46:52,538
Dette is-- og jeg vil bølge
min hånd på dette, hvordan du

1003
00:46:52,538 --> 00:46:55,570
kunne gennemføre denne som en C-struktur.

1004
00:46:55,570 --> 00:46:58,260
Vi skal bare nødt til at kombinere
et symbol, som en char,

1005
00:46:58,260 --> 00:46:59,910
og frekvensen i venstre og højre.

1006
00:46:59,910 --> 00:47:02,510
Men lad os se på to
endelige eksempler, som du vil

1007
00:47:02,510 --> 00:47:06,070
få helt fortrolig med efter
quiz nul i problemet sæt fem.

1008
00:47:06,070 --> 00:47:09,210
>> Så der er datastrukturen
kendt som en hash tabel.

1009
00:47:09,210 --> 00:47:12,247
Og en hash tabel er slags
afkøles i, at det har spande.

1010
00:47:12,247 --> 00:47:14,830
Og formoder, at der er fire spande
her, kun fire tomme rum.

1011
00:47:14,830 --> 00:47:20,830
Her er et spil kort, og her er
klub, spade, klub, diamanter, klub,

1012
00:47:20,830 --> 00:47:25,960
diamanter, klub, diamanter,
clubs-- så dette er tilfældigt.

1013
00:47:25,960 --> 00:47:30,330
Hjerter, Hearts-- så jeg er
bucketizing alle de input her.

1014
00:47:30,330 --> 00:47:32,430
Og en hash tabel behov
til at se på dit input,

1015
00:47:32,430 --> 00:47:34,850
og derefter sætte det i en vis
placere baseret på, hvad du ser.

1016
00:47:34,850 --> 00:47:35,600
Det er en algoritme.

1017
00:47:35,600 --> 00:47:37,980
Og jeg var ved hjælp af en super
simpel visuel algoritme.

1018
00:47:37,980 --> 00:47:40,030
Den sværeste del af som var
huske, hvad billederne var.

1019
00:47:40,030 --> 00:47:41,590
Og så er der fire i alt ting.

1020
00:47:41,590 --> 00:47:45,440
>> Nu stablerne voksede, som
er en bevidst design ting her.

1021
00:47:45,440 --> 00:47:46,540
Men hvad kan jeg gøre?

1022
00:47:46,540 --> 00:47:49,080
Så faktisk her har vi en
bunke af gamle skole eksamen bøger.

1023
00:47:49,080 --> 00:47:51,240
Antag, at en flok
elevernes navne er på her.

1024
00:47:51,240 --> 00:47:52,570
Her er en større hash tabel.

1025
00:47:52,570 --> 00:47:54,867
I stedet for fire skovle,
Jeg har, lad os sige 26.

1026
00:47:54,867 --> 00:47:57,950
Og vi ønskede ikke at gå låne 26
ting udefra [? Annenberg?], Så

1027
00:47:57,950 --> 00:48:00,289
her er fem, der repræsenterer
En gennem Z. Og hvis jeg

1028
00:48:00,289 --> 00:48:03,580
se en studerende, hvis navn starter med A,
Jeg har tænkt mig at sætte hans eller hendes quiz der.

1029
00:48:03,580 --> 00:48:08,850
Hvis nogen begynder med C, derovre,
En-- faktisk, ønskede ikke at gøre det.

1030
00:48:08,850 --> 00:48:10,060
B går herovre.

1031
00:48:10,060 --> 00:48:13,390
Så jeg har fået A og B og C. Og
nu her er en anden En studerende.

1032
00:48:13,390 --> 00:48:16,212
Men hvis denne hash tabel er
gennemføres med et array,

1033
00:48:16,212 --> 00:48:17,920
Jeg slags skruet
på dette tidspunkt, ikke?

1034
00:48:17,920 --> 00:48:19,510
Jeg slags nødt til at sætte dette sted.

1035
00:48:19,510 --> 00:48:24,380
>> Så en måde jeg kan løse dette er, alt
højre, A er optaget, B er optaget, C er optaget.

1036
00:48:24,380 --> 00:48:28,880
Jeg har tænkt mig at sætte ham i D. Så på
først, jeg har random øjeblikkelig adgang

1037
00:48:28,880 --> 00:48:31,064
til hver af skovle til de studerende.

1038
00:48:31,064 --> 00:48:33,230
Men nu er det sådan decentrale
til noget lineær,

1039
00:48:33,230 --> 00:48:36,750
fordi hvis jeg ønsker at søge efter en person
hvis navn starter med A, jeg tjekke her.

1040
00:48:36,750 --> 00:48:38,854
Men hvis dette ikke er A
elev, jeg leder efter,

1041
00:48:38,854 --> 00:48:41,520
Jeg slags nødt til at begynde at kontrollere
spande, fordi det, jeg gjorde

1042
00:48:41,520 --> 00:48:44,530
var slags lineært
probe datastrukturen.

1043
00:48:44,530 --> 00:48:47,710
En dum måde at sige bare se
for den første tilgængelige åbning,

1044
00:48:47,710 --> 00:48:51,850
og lægge så en plan B, så at sige,
eller plan D i denne sag, at værdien

1045
00:48:51,850 --> 00:48:53,340
i denne placering i stedet.

1046
00:48:53,340 --> 00:48:56,470
Det er bare så, at hvis du har
fik 26 steder og ingen studerende

1047
00:48:56,470 --> 00:49:00,600
med navnet Q eller Z, eller noget lignende
at du i det mindste bruger rummet.

1048
00:49:00,600 --> 00:49:03,140
>> Men vi har allerede set mere
smarte løsninger her, ikke?

1049
00:49:03,140 --> 00:49:04,870
Hvad ville du gøre i stedet
hvis du har en kollision?

1050
00:49:04,870 --> 00:49:06,670
Hvis to mennesker har
navnet A, hvad ville

1051
00:49:06,670 --> 00:49:09,160
har været en mere intelligent eller flere
intuitiv løsning end blot

1052
00:49:09,160 --> 00:49:12,840
sætte A hvor D formodes at være?

1053
00:49:12,840 --> 00:49:14,810
Hvorfor kan jeg ikke bare gå
uden [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
Ligesom malloc, anden node, sætte det
her, og derefter sætte, at en studerende her.

1055
00:49:19,960 --> 00:49:22,120
Så jeg har i det væsentlige
en slags et array,

1056
00:49:22,120 --> 00:49:25,590
eller måske mere elegant, som vi er
begyndt at se en linket liste.

1057
00:49:25,590 --> 00:49:29,520
>> Og så en hash tabel er en struktur
der kunne se lige sådan ud,

1058
00:49:29,520 --> 00:49:33,900
men mere smart, du noget, der hedder
separat kæde, hvorved en hash tabel

1059
00:49:33,900 --> 00:49:38,340
ganske enkelt er en matrix, hvor hver af
hvis elementer er ikke et tal,

1060
00:49:38,340 --> 00:49:40,470
selv er en sammenkædet liste.

1061
00:49:40,470 --> 00:49:45,080
Så du får super hurtig adgang
afgør, hvor at hash din værdi til.

1062
00:49:45,080 --> 00:49:48,059
Meget gerne med kort eksempel,
Jeg lavede super hurtige beslutninger.

1063
00:49:48,059 --> 00:49:49,600
Hjerter går her, diamanter går her.

1064
00:49:49,600 --> 00:49:52,180
Samme her, A går her,
D går her, B går her.

1065
00:49:52,180 --> 00:49:55,740
Så super hurtige opslag, og hvis
du tilfældigvis løbe ind i en sag

1066
00:49:55,740 --> 00:49:59,429
hvor du har fået kollisioner, to
mennesker med samme navn, ja så

1067
00:49:59,429 --> 00:50:00,970
du bare begynde at linke dem sammen.

1068
00:50:00,970 --> 00:50:03,900
Og måske du holde dem ordnet
alfabetisk, måske du ikke gør.

1069
00:50:03,900 --> 00:50:05,900
Men i det mindste nu har vi dynamik.

1070
00:50:05,900 --> 00:50:10,250
Så på den ene side har vi super hurtig
konstant tid, og art lineær tid

1071
00:50:10,250 --> 00:50:14,110
involveret, hvis disse linkede lister
begynder at få lidt lang.

1072
00:50:14,110 --> 00:50:16,880
>> Så denne slags en fjollet,
nørdede joke år siden.

1073
00:50:16,880 --> 00:50:19,590
På CS50 hack-a-thon,
når eleverne tjekke,

1074
00:50:19,590 --> 00:50:22,040
nogle TF eller CA hvert år
synes det er sjovt at sætte op

1075
00:50:22,040 --> 00:50:27,772
et skilt som dette, hvor det bare
betyder, at hvis dit navn starter med et A,

1076
00:50:27,772 --> 00:50:28,870
gå denne vej.

1077
00:50:28,870 --> 00:50:31,110
Hvis dit navn starter
med et B, gå denne-- OK,

1078
00:50:31,110 --> 00:50:33,290
det er sjovt måske senere i semesteret.

1079
00:50:33,290 --> 00:50:36,420
Men der er en anden
måde at gøre det, også.

1080
00:50:36,420 --> 00:50:37,410
Kom tilbage til.

1081
00:50:37,410 --> 00:50:38,600
>> Så der er denne struktur.

1082
00:50:38,600 --> 00:50:40,420
Og dette er vores sidste
struktur for i dag,

1083
00:50:40,420 --> 00:50:42,400
hvilket er noget, der hedder en trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, som en eller anden grund er kort
til hentning, men det hedder trie.

1085
00:50:47,140 --> 00:50:51,389
Så en trie er et andet interessant
sammensmeltning af en masse af disse ideer.

1086
00:50:51,389 --> 00:50:52,930
Det er et træ, som vi har set før.

1087
00:50:52,930 --> 00:50:54,180
Det er ikke en binær søgning træ.

1088
00:50:54,180 --> 00:50:58,410
Det er et træ med et vilkårligt antal børn,
men hver af børnene i en trie

1089
00:50:58,410 --> 00:51:00,090
er en matrix.

1090
00:51:00,090 --> 00:51:04,790
En vifte af størrelse, siger, 26 eller måske 27
Hvis du ønsker at støtte bindestreg navne

1091
00:51:04,790 --> 00:51:06,790
eller apostroffer i folks navne.

1092
00:51:06,790 --> 00:51:08,280
>> Og så dette er en datastruktur.

1093
00:51:08,280 --> 00:51:10,290
Og hvis man ser fra top
til bund, ligesom hvis du

1094
00:51:10,290 --> 00:51:13,710
se øverst node der, M, er
peger på den venstre ting der,

1095
00:51:13,710 --> 00:51:17,665
som derefter A, X, W, E, L, L. Dette er
blot en datastruktur, der vilkårligt

1096
00:51:17,665 --> 00:51:19,120
er at gemme folks navne.

1097
00:51:19,120 --> 00:51:25,720
Og Maxwell er gemt ved blot at følge
en sti af array til array til array.

1098
00:51:25,720 --> 00:51:30,050
Men hvad er forbløffende om en trie er
at, mens en linket liste, og selv

1099
00:51:30,050 --> 00:51:34,520
et array, det bedste, vi nogensinde har fået, er
lineær tid eller logaritmisk tid på at lede

1100
00:51:34,520 --> 00:51:35,600
person op.

1101
00:51:35,600 --> 00:51:40,530
I denne datastruktur i en trie, hvis
min datastruktur har et navn i det

1102
00:51:40,530 --> 00:51:43,720
og jeg leder efter Maxwell, jeg er
kommer til at finde ham temmelig hurtigt.

1103
00:51:43,720 --> 00:51:47,910
Jeg bare kigge efter M-A-X-W-E-L-L. Hvis
denne datastruktur, derimod,

1104
00:51:47,910 --> 00:51:51,830
Hvis N er en million, hvis der er en
million navne i denne datastruktur,

1105
00:51:51,830 --> 00:51:57,100
Maxwell stadig vil være
synlig efter blot M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
trin.

1107
00:51:58,090 --> 00:52:01,276
Og David-- D-A-V-I-D trin.

1108
00:52:01,276 --> 00:52:03,400
Med andre ord, ved at bygge
en datastruktur, der er

1109
00:52:03,400 --> 00:52:07,240
fik alle disse arrays, som alle
selv understøtter random access,

1110
00:52:07,240 --> 00:52:11,090
Jeg kan begynde at kigge op folks
navn med en mængde tid, der er

1111
00:52:11,090 --> 00:52:14,340
proportional med ikke antallet
af ting i datastrukturen,

1112
00:52:14,340 --> 00:52:16,330
som en million eksisterende navne.

1113
00:52:16,330 --> 00:52:20,135
Den tid, det tager mig at finde
M-A-X-W-E-L-L i denne datastruktur er

1114
00:52:20,135 --> 00:52:22,260
proportional ikke til
størrelsen af ​​den datastruktur,

1115
00:52:22,260 --> 00:52:25,930
men til længden af ​​navnet.

1116
00:52:25,930 --> 00:52:28,440
Og realistisk
navne, vi leder op

1117
00:52:28,440 --> 00:52:29,970
aldrig kommer til at være vanvittigt lange.

1118
00:52:29,970 --> 00:52:32,600
Måske nogen har en 10 tegn
navn, 20 tegnnavn.

1119
00:52:32,600 --> 00:52:33,900
Det er helt sikkert finite, ikke?

1120
00:52:33,900 --> 00:52:37,110
Der er et menneske på Jorden, der
har den længst mulige navn,

1121
00:52:37,110 --> 00:52:39,920
men dette navn er en konstant
værdi længde, ikke?

1122
00:52:39,920 --> 00:52:41,980
Det betyder ikke varierer i nogen forstand.

1123
00:52:41,980 --> 00:52:45,090
Så på denne måde, vi har
opnået en datastruktur

1124
00:52:45,090 --> 00:52:47,800
der er konstant tid look-up.

1125
00:52:47,800 --> 00:52:50,670
Det tager en række skridt
afhængigt af længden af ​​input,

1126
00:52:50,670 --> 00:52:54,250
men ikke antallet af navn
i datastrukturen.

1127
00:52:54,250 --> 00:52:58,700
Så hvis vi fordoble antallet af navne
næste år fra en milliard til to milliarder,

1128
00:52:58,700 --> 00:53:03,720
fund Maxwell vil tage
nøjagtig samme antal syv trin

1129
00:53:03,720 --> 00:53:04,650
at finde ham.

1130
00:53:04,650 --> 00:53:08,810
Og så synes vi at have opnået
vores hellige gral af køretid.

1131
00:53:08,810 --> 00:53:10,860
>> Så Et par hurtige udmeldinger.

1132
00:53:10,860 --> 00:53:11,850
Quiz nul kommer op.

1133
00:53:11,850 --> 00:53:14,600
Mere om det på kursets hjemmeside
løbet af de næste par dage.

1134
00:53:14,600 --> 00:53:17,120
Mandagens lecture-- det er en ferie
her på Harvard i mandags.

1135
00:53:17,120 --> 00:53:18,850
Det er ikke i New Haven,
så vi tager klassen

1136
00:53:18,850 --> 00:53:20,310
til New Haven til foredrag på mandag.

1137
00:53:20,310 --> 00:53:22,550
Alt vil blive filmet
og streamet live som sædvanlig,

1138
00:53:22,550 --> 00:53:24,900
men lad os slutte i dag
med en 30 sekunders klip

1139
00:53:24,900 --> 00:53:26,910
kaldet "dybe tanker"
af Daven Farnham, som

1140
00:53:26,910 --> 00:53:30,850
var inspireret sidste år ved lørdag
Night Lives "Deep Thoughts"

1141
00:53:30,850 --> 00:53:35,700
af Jack Handy, som
bør nu give mening.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Og nu, "Deep
Tanker "af Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tabellen.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Okay, det er det for nu.

1147
00:53:47,660 --> 00:53:48,805
Vi vil se dig i næste uge.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: For at se det i aktion.

1150
00:53:56,680 --> 00:53:58,304
Så lad os tage et kig på det lige nu.

1151
00:53:58,304 --> 00:53:59,890
Så her har vi en usorteret array.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, kan du gå videre og genstart
dette for bare et sekund, tak.

1153
00:54:04,860 --> 00:54:08,562
Okay, der er kameraer rullende, så
handling, når du er klar, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Okay, så hvad vi
har her er en usorteret array.

1155
00:54:11,020 --> 00:54:13,960
Og jeg har farvet alle de elementer
rødt for at indikere, at det er i virkeligheden,

1156
00:54:13,960 --> 00:54:14,460
usorteret.

1157
00:54:14,460 --> 00:54:17,960
Så minde om, at det første, vi gør
er vi sortere venstre halvdel af array.

1158
00:54:17,960 --> 00:54:20,630
Så vi sortere det rigtige
halvdelen af ​​arrayet.

1159
00:54:20,630 --> 00:54:22,830
Og ya-da, ya-da, ya-da,
vi flette dem sammen.

1160
00:54:22,830 --> 00:54:24,520
Og vi har en helt sorterede array.

1161
00:54:24,520 --> 00:54:25,360
Så det er sådan mergesort fungerer.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, whoa, whoa,
snit, skære, snit, skære.

1163
00:54:27,109 --> 00:54:30,130
Doug, ikke kan du bare ya-da, ya-da,
ya-da, din vej gennem mergesort.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Jeg har lige gjorde.

1165
00:54:31,970 --> 00:54:32,832
Det er fint.

1166
00:54:32,832 --> 00:54:33,540
Vi er gode til at gå.

1167
00:54:33,540 --> 00:54:34,760
Lad os bare holde rullende.

1168
00:54:34,760 --> 00:54:35,380
Så alligevel,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Du er nødt til at forklare
det mere fuldstændigt end det.

1170
00:54:37,800 --> 00:54:39,999
Det er bare ikke nok.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, gør vi ikke
nødt til at gå tilbage til en.

1172
00:54:41,790 --> 00:54:42,350
Det er fint.

1173
00:54:42,350 --> 00:54:45,690
Så alligevel, hvis vi fortsætter med merge--
Ian, vi er midt i optagelserne.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Jeg kender.

1175
00:54:46,612 --> 00:54:49,320
Og vi kan ikke bare ya-da, ya-da,
ya-da, gennem hele processen.

1176
00:54:49,320 --> 00:54:52,200
Du er nødt til at forklare, hvordan
to sider bliver slået sammen.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Men vi har allerede
forklarede, hvordan de to sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Du har lige vist
dem en sammenfletning array.

1179
00:54:55,321 --> 00:54:56,486
DOUG: De kender processen.

1180
00:54:56,486 --> 00:54:57,172
De er fint.

1181
00:54:57,172 --> 00:54:58,380
Vi har gået over det ti gange.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Du har lige sprunget lige over det.

1183
00:55:00,330 --> 00:55:03,360
Vi kommer tilbage til en, du
kan du ikke ya-da, ya-da over det.

1184
00:55:03,360 --> 00:55:05,480
Okay, tilbage til én.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Jeg er nødt til at gå tilbage
gennem alle dias?

1186
00:55:07,833 --> 00:55:08,332
Min Gud.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Det er ligesom det sjette gang, Ian.

1189
00:55:13,004 --> 00:55:13,940
Det er fint.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Okay.

1191
00:55:15,200 --> 00:55:16,590
Er du klar?

1192
00:55:16,590 --> 00:55:17,400
Great.

1193
00:55:17,400 --> 00:55:18,950
Handling.