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

2
00:00:10,900 --> 00:00:15,860
>> TALARE 1: Okej, så det här är
CS50 Detta är slutet av veckan fem.

3
00:00:15,860 --> 00:00:19,220
Och minns att förra gången vi
började titta på snyggare uppgifter

4
00:00:19,220 --> 00:00:22,310
strukturer som började lösa
problem, som började införa

5
00:00:22,310 --> 00:00:25,640
nya problem, men nyckeln till detta
var den typ av gäng som vi

6
00:00:25,640 --> 00:00:27,940
började göra från nod till nod.

7
00:00:27,940 --> 00:00:30,085
Så det här är naturligtvis
en enskilt länkad lista.

8
00:00:30,085 --> 00:00:31,960
Och genom att var för sig kopplade,
Jag menar att det finns bara en

9
00:00:31,960 --> 00:00:33,380
tråd mellan var och en av dessa noder.

10
00:00:33,380 --> 00:00:35,890
Slår ut kan du göra snyggare
saker som dubbelt länkade listor

11
00:00:35,890 --> 00:00:38,470
där du har en pil
går i båda riktningarna, vilket

12
00:00:38,470 --> 00:00:40,320
kan hjälpa till med vissa effektivitetsvinster.

13
00:00:40,320 --> 00:00:42,000
Men detta löste problemet?

14
00:00:42,000 --> 00:00:43,500
Vilket problem kunde detta lösa?

15
00:00:43,500 --> 00:00:46,620
Varför vi bryr oss på måndag?

16
00:00:46,620 --> 00:00:49,820
Varför, i teorin, vi bryr oss på måndag?

17
00:00:49,820 --> 00:00:50,630
Vad gör den?

18
00:00:50,630 --> 00:00:51,950
>> PUBLIK: Vi kan dynamiskt ändra storlek på den.

19
00:00:51,950 --> 00:00:53,740
>> TALARE 1: OK, så vi kan
dynamiskt ändra storlek på den.

20
00:00:53,740 --> 00:00:54,710
Bra gjort både av er.

21
00:00:54,710 --> 00:00:57,560
Så du kan dynamiskt ändra storlek här
datastruktur, medan en matris,

22
00:00:57,560 --> 00:01:00,760
minns, måste du veta en
priori hur mycket utrymme du vill

23
00:01:00,760 --> 00:01:03,870
och om du behöver lite mer
utrymme, är du typ av av lycka.

24
00:01:03,870 --> 00:01:05,560
Du måste skapa en helt ny uppsättning.

25
00:01:05,560 --> 00:01:07,893
Du måste flytta alla dina
data från en till den andra,

26
00:01:07,893 --> 00:01:10,600
småningom befria gamla array
om du kan, och sedan fortsätta.

27
00:01:10,600 --> 00:01:13,891
Vilket känns bara mycket kostsamt och mycket
ineffektiv, och faktiskt kan det vara.

28
00:01:13,891 --> 00:01:14,890
Men detta är inte allt bra.

29
00:01:14,890 --> 00:01:18,180
Vi betalar ett pris, vad som var en
av de mer uppenbara priser vi

30
00:01:18,180 --> 00:01:20,550
betala med hjälp av en länkad lista?

31
00:01:20,550 --> 00:01:22,825
>> PUBLIK: Vi måste använda
dubbel utrymme för var och en.

32
00:01:22,825 --> 00:01:25,200
TALARE 1: Ja, så vi behöver
minst dubbelt så mycket plats.

33
00:01:25,200 --> 00:01:27,700
I själva verket, insåg jag att detta bildens
även lite missvisande,

34
00:01:27,700 --> 00:01:32,200
eftersom på CS50 IDE i en hel del modern
datorer, en pekare eller en adress

35
00:01:32,200 --> 00:01:33,700
är i själva verket inte fyra byte.

36
00:01:33,700 --> 00:01:36,090
Det är ofta dessa
dagar åtta byte, som

37
00:01:36,090 --> 00:01:38,530
: den nedersta
rektanglar där i verkligheten

38
00:01:38,530 --> 00:01:40,900
är typ av dubbelt så
stor som vad jag har ritat,

39
00:01:40,900 --> 00:01:44,409
vilket innebär att du använder tre gånger så
mycket utrymme som vi skulle ha annars.

40
00:01:44,409 --> 00:01:46,700
Nu samtidigt, vi är
fortfarande talar byte, eller hur?

41
00:01:46,700 --> 00:01:49,140
Vi är inte nödvändigtvis talar
megabyte eller gigabyte,

42
00:01:49,140 --> 00:01:51,000
såvida dessa uppgifter strukturer blir stora.

43
00:01:51,000 --> 00:01:54,510
>> Och så idag börjar vi att överväga
hur vi kan utforska data

44
00:01:54,510 --> 00:01:57,310
mer effektivt om i
Faktum är att uppgifterna blir större.

45
00:01:57,310 --> 00:02:00,360
Men låt oss försöka canonicalize
verksamheten först

46
00:02:00,360 --> 00:02:02,460
att du kan göra på dessa
typer av datastrukturer.

47
00:02:02,460 --> 00:02:04,790
Så något som en länkad
Listan stöder generellt

48
00:02:04,790 --> 00:02:07,514
operationer gillar bort,
infoga och söka.

49
00:02:07,514 --> 00:02:08,639
Och vad menar jag med det?

50
00:02:08,639 --> 00:02:11,222
Det betyder bara att vanligtvis
om folk använder länkad lista,

51
00:02:11,222 --> 00:02:14,287
de eller någon annan har genomfört
funktioner som radera, infoga,

52
00:02:14,287 --> 00:02:16,120
och söka, så att du kan
faktiskt göra något

53
00:02:16,120 --> 00:02:18,030
användbar med datastrukturen.

54
00:02:18,030 --> 00:02:20,760
Så låt oss ta en snabb titt
på hur vi kan genomföra

55
00:02:20,760 --> 00:02:24,530
lite kod för en länkad lista som följer.

56
00:02:24,530 --> 00:02:27,885
>> Så det här är bara några C-kod,
inte ens ett komplett program

57
00:02:27,885 --> 00:02:29,260
att jag verkligen snabbt piskade upp.

58
00:02:29,260 --> 00:02:32,300
Det är inte online i distributionen
kod, eftersom det kommer faktiskt inte köra.

59
00:02:32,300 --> 00:02:33,790
Men märker jag har bara
med en kommentar sade,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, det finns något
där dot dot dot, något där.

61
00:02:36,130 --> 00:02:38,410
Och låt oss titta bara på
vad saftiga delar.

62
00:02:38,410 --> 00:02:40,790
Så på linje tre,
påminna om att detta är nu

63
00:02:40,790 --> 00:02:45,960
Vi föreslog att förklara en nod sista
tiden, en av de rektangulära föremål.

64
00:02:45,960 --> 00:02:48,790
Den har en int som vi kallar N,
men vi skulle kunna kalla det något,

65
00:02:48,790 --> 00:02:51,920
och sedan en struct nod stjärna kallas nästa.

66
00:02:51,920 --> 00:02:55,520
Och bara för att vara tydlig, det andra
line, on line sex, vad är det?

67
00:02:55,520 --> 00:02:57,930
Vad gör den för oss?

68
00:02:57,930 --> 00:03:01,044
Eftersom det verkligen ser mer
kryptiska än våra vanliga variabler.

69
00:03:01,044 --> 00:03:02,740
>> PUBLIK: Det gör det gå över en.

70
00:03:02,740 --> 00:03:04,650
>> TALARE 1: Det gör det gå över en.

71
00:03:04,650 --> 00:03:08,580
Och för att vara mer exakt,
det kommer att lagra adressen

72
00:03:08,580 --> 00:03:11,582
av den nod som är tänkt att vara
semantiskt bredvid den, eller hur?

73
00:03:11,582 --> 00:03:13,540
Så det kommer inte att
nödvändigtvis flytta någonting.

74
00:03:13,540 --> 00:03:15,290
Det är bara att gå till
lagra ett värde, som är

75
00:03:15,290 --> 00:03:17,170
kommer att vara den adress
av någon annan nod,

76
00:03:17,170 --> 00:03:20,810
och det är därför vi har sagt struct
nod stjärna, stjärnan betecknar

77
00:03:20,810 --> 00:03:22,370
en pekare eller en adress.

78
00:03:22,370 --> 00:03:26,390
OK, så nu om du antar att vi har
denna N tillgängliga för oss, och låt oss

79
00:03:26,390 --> 00:03:29,490
antar att någon annan har
infört en massa heltal

80
00:03:29,490 --> 00:03:30,400
in i en länkad lista.

81
00:03:30,400 --> 00:03:35,640
Och det länkade listan är
pekas på av någon punkt

82
00:03:35,640 --> 00:03:39,040
en variabel som heter lista som är
passerade här som en parameter,

83
00:03:39,040 --> 00:03:43,120
Hur gör jag linje
14 genomförande sökning?

84
00:03:43,120 --> 00:03:45,990
Med andra ord, om jag genomföra
funktion vars syfte i livet

85
00:03:45,990 --> 00:03:48,889
är att ta en int och sedan
början av en länkad lista,

86
00:03:48,889 --> 00:03:50,430
som är en pekare till den länkade listan.

87
00:03:50,430 --> 00:03:52,992
Liksom första, som jag tror David
var vår volontär på måndag,

88
00:03:52,992 --> 00:03:54,700
Han pekade på
hela länkad lista,

89
00:03:54,700 --> 00:03:57,820
det är som om vi passerar
David i vår argument här.

90
00:03:57,820 --> 00:03:59,990
Hur ska vi göra gå igenom den här listan?

91
00:03:59,990 --> 00:04:04,640
Tja, visar det sig att även om
pekare är relativt nya nu till oss,

92
00:04:04,640 --> 00:04:07,010
Vi kan göra detta relativt
rättframt.

93
00:04:07,010 --> 00:04:09,500
>> Jag kommer att gå vidare och
deklarerar en temporär variabel som

94
00:04:09,500 --> 00:04:12,364
enligt praxis är att bara gå
att kallas pekare eller PTR,

95
00:04:12,364 --> 00:04:14,030
men du kan kalla det vad du vill.

96
00:04:14,030 --> 00:04:16,470
Och jag kommer att initiera
det till början av listan.

97
00:04:16,470 --> 00:04:20,050
Så du kan slags tänka på detta
som jag läraren häromdagen,

98
00:04:20,050 --> 00:04:23,580
typ av pekar på någon
bland våra människor som volontärer.

99
00:04:23,580 --> 00:04:26,470
Så jag är en temporär variabel som är
bara pekar på samma sak

100
00:04:26,470 --> 00:04:31,390
att vår tillfällighet namnges
volontär David var också påpeka.

101
00:04:31,390 --> 00:04:35,440
Nu när pekaren
inte null, eftersom återkallelse

102
00:04:35,440 --> 00:04:40,350
att noll är några speciella sentinel värde
den avgränsar slutet av listan,

103
00:04:40,350 --> 00:04:44,280
så medan jag inte pekar på
marken som vår sista volontär

104
00:04:44,280 --> 00:04:47,190
var, låt oss gå vidare
och gör följande.

105
00:04:47,190 --> 00:04:51,820
Om pointer-- och nu har jag slags vill
att göra vad vi gjorde med studenten

106
00:04:51,820 --> 00:04:57,410
structure-- om pekare dot nästa
equals-- snarare, om pekaren dot N är lika

107
00:04:57,410 --> 00:05:02,290
lika med variabeln N, varvid
argument som har förts in,

108
00:05:02,290 --> 00:05:05,370
då jag vill gå vidare
och säga return true.

109
00:05:05,370 --> 00:05:11,020
Jag har hittat antalet N insida
en av noderna i min länkad lista.

110
00:05:11,020 --> 00:05:13,500
Men punkten inte längre
fungerar i detta sammanhang,

111
00:05:13,500 --> 00:05:17,260
eftersom pekare, PTR, är
verkligen en pekare, en adress,

112
00:05:17,260 --> 00:05:20,632
vi faktiskt kan underbart
Använd slutligen en bit av syntax

113
00:05:20,632 --> 00:05:22,590
den typen av fabrikat
intuitiv känsla och faktiskt

114
00:05:22,590 --> 00:05:27,870
Använd en pil här, vilket innebär att gå från
adressen till heltal där i.

115
00:05:27,870 --> 00:05:30,160
Så det är väldigt lika i
anda att punktoperatorn,

116
00:05:30,160 --> 00:05:33,860
men eftersom pekaren är inte en pekare
och inte en faktisk struct själv,

117
00:05:33,860 --> 00:05:35,380
vi använder bara pilen.

118
00:05:35,380 --> 00:05:40,620
>> Så om den aktuella noden att jag,
temporär variabel, am pekar på

119
00:05:40,620 --> 00:05:43,060
är inte N, vad vill jag göra?

120
00:05:43,060 --> 00:05:45,910
Tja, med mina frivilliga försökspersoner
att vi hade här häromdagen,

121
00:05:45,910 --> 00:05:49,710
om mitt första människa är inte den jag
vill, och kanske andra människors inte

122
00:05:49,710 --> 00:05:52,660
den jag vill, och den tredje, jag
behöver för att hålla fysiskt i rörelse.

123
00:05:52,660 --> 00:05:54,690
Liksom hur gör jag stega igenom en lista?

124
00:05:54,690 --> 00:05:57,470
När vi hade en matris, du
just gjorde som jag plus plus.

125
00:05:57,470 --> 00:06:03,660
Men i detta fall är det tillräckligt att
gör pekare blir, pekare, nästa.

126
00:06:03,660 --> 00:06:07,580
Med andra ord, nästa fält
är som alla vänster hand

127
00:06:07,580 --> 00:06:10,880
att våra frivilliga på måndag
använde för att peka på någon annan nod.

128
00:06:10,880 --> 00:06:12,890
Det var deras nästa grannar.

129
00:06:12,890 --> 00:06:17,060
>> Så om jag vill gå igenom den här listan,
Jag kan inte bara jag plus plus längre,

130
00:06:17,060 --> 00:06:20,120
Jag har i stället för att säga
I pekare, går

131
00:06:20,120 --> 00:06:24,650
till lika oavsett nästa fält är,
nästa fält, är nästa fält,

132
00:06:24,650 --> 00:06:28,350
efter alla dessa vänster hand
att vi hade på scenen pekar

133
00:06:28,350 --> 00:06:30,000
till vissa efterföljande värden.

134
00:06:30,000 --> 00:06:32,590
Och om jag får igenom
att hela iteration,

135
00:06:32,590 --> 00:06:39,330
och slutligen, jag slog null inte ha
hittade N ändå, jag tillbaka bara falskt.

136
00:06:39,330 --> 00:06:44,100
Så återigen, allt som vi gör här,
enligt bilden för en stund sedan,

137
00:06:44,100 --> 00:06:47,840
börjar genom att peka på
i början av listan förmodligen.

138
00:06:47,840 --> 00:06:50,970
Och då jag kolla, är värdet
Jag letar efter lika med nio?

139
00:06:50,970 --> 00:06:52,650
Om så är fallet, återvänder jag sanna och jag är klar.

140
00:06:52,650 --> 00:06:56,450
Om inte, uppdaterar jag min hand,
AKA pekare, peka

141
00:06:56,450 --> 00:06:59,540
vid nästa pilen läge, och
sedan nästa pilen läge,

142
00:06:59,540 --> 00:07:00,480
och nästa.

143
00:07:00,480 --> 00:07:03,770
Jag är helt enkelt gå igenom denna uppsättning.

144
00:07:03,770 --> 00:07:06,010
>> Så återigen, vem bryr sig?

145
00:07:06,010 --> 00:07:07,861
Liksom vad är detta en ingrediens för?

146
00:07:07,861 --> 00:07:10,360
Tja, minns att vi införde
begreppet en stapel, som

147
00:07:10,360 --> 00:07:15,400
är en abstrakt datatyp i den mån det är
inte C sak, det är inte en CS50 sak,

148
00:07:15,400 --> 00:07:19,430
Det är en abstrakt idé, denna idé om
stapla saker ovanpå varandra

149
00:07:19,430 --> 00:07:21,820
som kan genomföras i
klasar av olika sätt.

150
00:07:21,820 --> 00:07:25,600
Och ett sätt som vi föreslog var med
en array, eller med en länkad lista.

151
00:07:25,600 --> 00:07:29,570
Och det visar sig att canonically, en
stack stödjer åtminstone två operationer.

152
00:07:29,570 --> 00:07:32,320
Och modeord är push, till
skjut något på stacken,

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

154
00:07:34,770 --> 00:07:39,000
vilket innebär att ta bort den översta
bricka från stapeln i matsalen

155
00:07:39,000 --> 00:07:41,500
hall, och sedan kanske en del
övrig verksamhet samt.

156
00:07:41,500 --> 00:07:45,770
Så hur kan vi definierar strukturen
att vi nu kallar en stapel?

157
00:07:45,770 --> 00:07:50,020
>> Tja, vi har alla erforderliga
syntax till vårt förfogande i C. Jag säger,

158
00:07:50,020 --> 00:07:53,830
ge mig en definition typ av
en struct inne i en stapel,

159
00:07:53,830 --> 00:07:58,030
Jag kommer att säga är en uppsättning av en
massa siffror och sedan storlek.

160
00:07:58,030 --> 00:08:00,930
Så med andra ord, om jag vill
att genomföra detta i koden,

161
00:08:00,930 --> 00:08:03,830
låt mig gå och bara typ av
rita vad det säger.

162
00:08:03,830 --> 00:08:06,317
Så detta säger, ge mig en
struktur som har fått en array,

163
00:08:06,317 --> 00:08:09,400
och jag vet inte vilken egenskap är,
Det är tydligen någon konstant som jag har

164
00:08:09,400 --> 00:08:10,858
definieras på annat håll, och det är bra.

165
00:08:10,858 --> 00:08:15,260
Men antar att det är bara en,
två, tre, fyra, fem.

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

167
00:08:16,700 --> 00:08:21,730
Denna del insidan av min
struktur kommer att kallas nummer.

168
00:08:21,730 --> 00:08:24,020
Och då behöver jag en
annan variabel tydligen

169
00:08:24,020 --> 00:08:27,814
kallas storlek som ursprungligen kommer jag
att föreskriva initieras till noll.

170
00:08:27,814 --> 00:08:29,730
Om det finns inget i
stapeln, storleken är noll,

171
00:08:29,730 --> 00:08:31,420
och det är sopor värden i antal.

172
00:08:31,420 --> 00:08:33,450
Jag har ingen aning om vad som finns där ännu.

173
00:08:33,450 --> 00:08:36,059
>> Så om jag vill driva
något på stacken,

174
00:08:36,059 --> 00:08:40,780
antar att jag kallar funktionen push, och
Jag säger skjuta 50, liksom antalet 50,

175
00:08:40,780 --> 00:08:44,090
var skulle du föreslå
Jag drar det i denna samling?

176
00:08:44,090 --> 00:08:47,124
Det finns fem olika svarsalternativ.

177
00:08:47,124 --> 00:08:48,790
Var vill du att driva antalet 50?

178
00:08:48,790 --> 00:08:51,899
Om målet här, igen, ring
funktions skjuta, passera i ett argument

179
00:08:51,899 --> 00:08:52,940
50, var ska jag uttrycka det?

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

181
00:08:55,680 --> 00:08:59,052
Fem possible-- 20% chans
att gissa korrekt.

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

183
00:08:59,896 --> 00:09:00,740
>> PUBLIK: Längst till höger.

184
00:09:00,740 --> 00:09:01,990
>> TALARE 1: Längst till höger.

185
00:09:01,990 --> 00:09:08,359
Det finns nu en chans 25%
att gissa korrekt.

186
00:09:08,359 --> 00:09:09,650
Så det skulle faktiskt vara bra.

187
00:09:09,650 --> 00:09:12,770
Av konvention, ska jag säga med en array,
Vi skulle i allmänhet börja från vänster,

188
00:09:12,770 --> 00:09:14,519
men vi kunde säkert
starta vid rätt.

189
00:09:14,519 --> 00:09:17,478
Så spoiler här skulle vara jag
förmodligen kommer att dra den till vänster,

190
00:09:17,478 --> 00:09:20,060
precis som i en vanlig array där
Jag börja gå från vänster till höger.

191
00:09:20,060 --> 00:09:21,780
Men om du kan vända
det aritmetiska, bra.

192
00:09:21,780 --> 00:09:23,060
Det är bara inte konventionella.

193
00:09:23,060 --> 00:09:24,880
OK, jag måste göra en
mer förändring men.

194
00:09:24,880 --> 00:09:27,710
Nu när jag har drivit något
på stacken, vad händer nu?

195
00:09:27,710 --> 00:09:29,400
>> Okej, jag måste öka storleken.

196
00:09:29,400 --> 00:09:32,600
Så låt mig gå vidare och bara
uppdatera denna, som var noll.

197
00:09:32,600 --> 00:09:35,950
Och i stället nu, jag ska
att sätta i värdet ett.

198
00:09:35,950 --> 00:09:39,460
Och nu antar att jag trycker en annan
numret på stacken, som 51.

199
00:09:39,460 --> 00:09:42,680
Tja, jag måste göra en mer
förändring, som är upp till storlek två.

200
00:09:42,680 --> 00:09:46,100
Och sedan antar jag trycker en mer
numret på stacken som 61,

201
00:09:46,100 --> 00:09:52,530
Nu måste jag uppdatera storlek ytterligare
tid, och få värdet 3 som storleken.

202
00:09:52,530 --> 00:09:54,690
Och nu antar att jag kallar pop.

203
00:09:54,690 --> 00:09:57,250
Nu pop, enligt konvention,
tar inte ett argument.

204
00:09:57,250 --> 00:10:00,430
Med en stapel, hela
punkt av brickan metafor

205
00:10:00,430 --> 00:10:03,450
är att du inte har handlingsfrihet
att gå få det facket, kan du göra

206
00:10:03,450 --> 00:10:06,330
är pop översta en från
stacken, bara för att.

207
00:10:06,330 --> 00:10:08,010
Det är vad denna datastruktur gör.

208
00:10:08,010 --> 00:10:12,250
>> Så genom denna logik, om jag
säger pop, vad som kommer ut?

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

210
00:10:13,080 --> 00:10:15,402
Så vad som verkligen är datorn
kommer att göra i minnet?

211
00:10:15,402 --> 00:10:16,610
Vad min kod måste göra?

212
00:10:16,610 --> 00:10:20,330
Vad skulle du föreslå
vi ändrar på skärmen?

213
00:10:20,330 --> 00:10:23,410
Vad ska förändras?

214
00:10:23,410 --> 00:10:24,960
Förlåt?

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

216
00:10:26,334 --> 00:10:27,500
Så jag kan definitivt göra det.

217
00:10:27,500 --> 00:10:28,640
Och jag kan bli av med 61.

218
00:10:28,640 --> 00:10:30,980
Och sedan vad andra
förändringen måste ske?

219
00:10:30,980 --> 00:10:33,160
Storlek har antagligen gå tillbaka till två.

220
00:10:33,160 --> 00:10:34,210
Och så går det bra.

221
00:10:34,210 --> 00:10:36,690
Men vänta en minut, storlek
en stund sedan var tre.

222
00:10:36,690 --> 00:10:38,240
Låt oss bara göra en snabb kontroll förstånd.

223
00:10:38,240 --> 00:10:41,810
Hur visste vi att vi
ville bli av med 61?

224
00:10:41,810 --> 00:10:42,760
Eftersom vi poppar.

225
00:10:42,760 --> 00:10:46,450
Och så jag har denna andra fastigheternas storlek.

226
00:10:46,450 --> 00:10:48,470
>> Vänta lite, jag är
tänker tillbaka till vecka två

227
00:10:48,470 --> 00:10:51,660
när vi började prata om
matriser, där detta läge noll,

228
00:10:51,660 --> 00:10:55,920
detta var platsen en, var denna plats
två, detta är platsen tre, fyra,

229
00:10:55,920 --> 00:10:58,460
det ser ut som
förhållande mellan storlek

230
00:10:58,460 --> 00:11:02,780
och element som jag vill ta bort
från gruppen verkar vara det?

231
00:11:02,780 --> 00:11:05,120
Storlek minus ett.

232
00:11:05,120 --> 00:11:07,786
Och så det är hur som människor
vi vet 61 kommer först.

233
00:11:07,786 --> 00:11:09,160
Hur är datorn kommer att veta?

234
00:11:09,160 --> 00:11:11,701
När koden, där du förmodligen
vill göra storlek minus ett,

235
00:11:11,701 --> 00:11:14,950
så tre minus ett är två, och att
innebär att vi vill bli av med 61.

236
00:11:14,950 --> 00:11:18,000
Och då kan vi verkligen uppdatera
storleken så att storlek

237
00:11:18,000 --> 00:11:20,300
går från tre till endast två.

238
00:11:20,300 --> 00:11:24,520
Och bara för att vara pedantisk, jag kommer
att föreslå att jag är klar, eller hur?

239
00:11:24,520 --> 00:11:27,660
Ni föreslog intuitivt
korrekt jag skulle bli av med 61.

240
00:11:27,660 --> 00:11:30,700
Men har jag inte typ av
sorts gjort sig av 61?

241
00:11:30,700 --> 00:11:33,790
Jag har faktiskt glömt
att det är faktiskt där.

242
00:11:33,790 --> 00:11:37,680
Och tänker tillbaka på PSET4, om du har läst
artikeln om kriminalteknik, PDF

243
00:11:37,680 --> 00:11:40,780
att vi hade ni läsa, eller om du
kommer att läsa denna vecka för PSET4.

244
00:11:40,780 --> 00:11:44,300
Minns att detta är faktiskt relevant för
hela idén med dator kriminalteknik.

245
00:11:44,300 --> 00:11:47,820
Vilken dator gör i allmänhet är
det bara glömmer där något är,

246
00:11:47,820 --> 00:11:51,300
men det inte gå in och ut
försöka skrapa ut eller överstyrning

247
00:11:51,300 --> 00:11:54,560
dessa bitar med nollor och ettor
eller någon annan slumpmässigt mönster

248
00:11:54,560 --> 00:11:56,690
om du inte själv göra det medvetet.

249
00:11:56,690 --> 00:11:58,930
Så din intuition var
Okej, låt oss bli av med 61.

250
00:11:58,930 --> 00:12:00,650
Men i verkligheten, har vi inte bry.

251
00:12:00,650 --> 00:12:04,040
Vi behöver bara att glömma att
den finns där genom att ändra vår storlek.

252
00:12:04,040 --> 00:12:05,662
>> Nu finns det ett problem med den här stack.

253
00:12:05,662 --> 00:12:07,620
Om jag hålla driver saker
på stacken, vad är

254
00:12:07,620 --> 00:12:11,167
uppenbarligen kommer att hända
på bara några ögonblick tid?

255
00:12:11,167 --> 00:12:12,500
Vi kommer att köra ut i rymden.

256
00:12:12,500 --> 00:12:13,580
Och vad gör vi?

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

258
00:12:14,680 --> 00:12:19,000
Denna implementering inte låta
oss ändra storlek på matrisen, eftersom att använda

259
00:12:19,000 --> 00:12:21,240
denna syntax, om du
tänker tillbaka på vecka två,

260
00:12:21,240 --> 00:12:23,520
när du har deklarerat
storleken på en array,

261
00:12:23,520 --> 00:12:26,780
Vi har inte sett den mekanism där
Du kan ändra storleken på matrisen.

262
00:12:26,780 --> 00:12:29,020
Och faktiskt C inte har den funktionen.

263
00:12:29,020 --> 00:12:32,524
Om du säger ge mig fem
Nths, kallar dem tal,

264
00:12:32,524 --> 00:12:33,940
det är allt du kommer att få det.

265
00:12:33,940 --> 00:12:38,790
Så vi gör nu som måndagen, har
förmågan att uttrycka en lösning

266
00:12:38,790 --> 00:12:42,480
Men vi behöver bara justera
Definitionen av vår stack

267
00:12:42,480 --> 00:12:46,840
att inte vara en del hårdkodade array,
men bara för att lagra en adress.

268
00:12:46,840 --> 00:12:47,890
>> Nu varför är detta?

269
00:12:47,890 --> 00:12:51,690
Nu har vi bara att vara bekväm med
det faktum att när mitt program körs

270
00:12:51,690 --> 00:12:53,730
Jag förmodligen kommer att
måste be människa,

271
00:12:53,730 --> 00:12:55,110
hur många nummer vill du spara?

272
00:12:55,110 --> 00:12:56,776
Så ingången måste komma någonstans ifrån.

273
00:12:56,776 --> 00:12:59,140
Men när jag vet att
nummer, så jag kan bara

274
00:12:59,140 --> 00:13:02,470
använda vilken funktion att ge
mig en bit av minne?

275
00:13:02,470 --> 00:13:03,580
Jag kan använda malloc.

276
00:13:03,580 --> 00:13:06,710
Och jag kan säga valfritt antal
bytes Jag vill tillbaka för dessa Nths.

277
00:13:06,710 --> 00:13:10,910
Och allt jag har att lagra i siffrorna
variabel här insidan av denna struct

278
00:13:10,910 --> 00:13:13,480
bör vara vad?

279
00:13:13,480 --> 00:13:18,440
Vad som faktiskt går in i
siffror i detta scenario?

280
00:13:18,440 --> 00:13:21,300
Ja, en pekare till den första
byten i den bit av minne,

281
00:13:21,300 --> 00:13:24,940
eller mer specifikt, till adressen
den första av dessa byte.

282
00:13:24,940 --> 00:13:27,300
Spelar ingen roll om det är en
byte eller en miljard byte,

283
00:13:27,300 --> 00:13:28,890
Jag behöver bara bry sig om den första.

284
00:13:28,890 --> 00:13:31,530
För vad malloc garantier och
mitt operativsystem garantier,

285
00:13:31,530 --> 00:13:34,170
är att bit av minnes I
få, det kommer att vara sammanhängande.

286
00:13:34,170 --> 00:13:35,378
Det kommer inte att finnas luckor.

287
00:13:35,378 --> 00:13:38,576
Så om jag har bett om 50
bytes eller 1000 bytes,

288
00:13:38,576 --> 00:13:40,450
De kommer alla att vara
rygg mot rygg mot rygg.

289
00:13:40,450 --> 00:13:44,500
Och så länge jag minns hur stor, hur
mycket jag bad om, allt jag behöver veta

290
00:13:44,500 --> 00:13:46,230
är den första adressen.

291
00:13:46,230 --> 00:13:48,660
>> Så nu har vi möjlighet i koden.

292
00:13:48,660 --> 00:13:51,280
Om än, det kommer att ta oss
mer tid att skriva upp detta,

293
00:13:51,280 --> 00:13:55,900
Vi kunde nu omfördela att minnet av
bara lagra en annan adress där

294
00:13:55,900 --> 00:13:59,060
Om vi ​​vill ha en större eller ens
en mindre bit av minnet.

295
00:13:59,060 --> 00:14:00,170
Så här till en avvägning.

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 fortfarande
contiguousness Jag påstår.

298
00:14:03,350 --> 00:14:05,881
Eftersom malloc kommer att ge oss
en sammanhängande del av minnet.

299
00:14:05,881 --> 00:14:08,630
Men detta kommer att vara en smärta i
nacken för oss, programmeraren,

300
00:14:08,630 --> 00:14:09,770
att faktiskt koda upp.

301
00:14:09,770 --> 00:14:10,730
Det är bara mer arbete.

302
00:14:10,730 --> 00:14:13,930
Vi behöver kod besläktad med vad jag var
banka ut bara för en stund sedan.

303
00:14:13,930 --> 00:14:16,120
Mycket genomförbart, men det tillför komplexitet.

304
00:14:16,120 --> 00:14:19,520
Och så utvecklare tid, programmerare
tid är ännu en resurs

305
00:14:19,520 --> 00:14:22,520
att vi kan behöva tillbringa
lite tid att få nya funktioner.

306
00:14:22,520 --> 00:14:24,020
Och så naturligtvis finns det en kö.

307
00:14:24,020 --> 00:14:26,227
Vi kommer inte att gå in på detta
en i stor detalj.

308
00:14:26,227 --> 00:14:27,560
Men det är väldigt lika i anden.

309
00:14:27,560 --> 00:14:31,220
Jag skulle kunna genomföra en kö, och
dess motsvarande verksamhet,

310
00:14:31,220 --> 00:14:35,660
enqueue eller dequeue, liksom lägga till eller ta bort,
det är bara en finare sätt att säga det,

311
00:14:35,660 --> 00:14:38,100
enqueue eller dequeue, enligt följande.

312
00:14:38,100 --> 00:14:41,170
Jag kan bara ge mig en struct
som återigen har ett antal s array,

313
00:14:41,170 --> 00:14:44,000
som återigen har en storlek,
men varför gör jag nu behöver

314
00:14:44,000 --> 00:14:46,940
att hålla reda på den främre delen av en kö?

315
00:14:46,940 --> 00:14:50,630
Jag behövde inte veta
framsidan av min stack.

316
00:14:50,630 --> 00:14:53,570
Tja, om jag återigen för en
queue-- låt oss bara hårt

317
00:14:53,570 --> 00:14:57,870
koda det som har som fem
heltal i här potentiellt.

318
00:14:57,870 --> 00:15:00,940
Så det här är noll, ett, två, tre, fyra.

319
00:15:00,940 --> 00:15:03,430
Detta kommer att bli
uppringda numren igen.

320
00:15:03,430 --> 00:15:06,940
Och detta kommer att kallas storlek.

321
00:15:06,940 --> 00:15:10,056
>> Varför är det inte tillräckligt
att bara storlek?

322
00:15:10,056 --> 00:15:11,680
Nåväl, låt oss skjuta samma nummer på.

323
00:15:11,680 --> 00:15:14,220
Så jag pushed-- jag kö, eller trycks in.

324
00:15:14,220 --> 00:15:20,150
Nu ska jag köa 50, och sedan
51, och sedan 61, och dot dot dot.

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

326
00:15:21,070 --> 00:15:23,176
Jag kö 50, sedan 51, sedan 61.

327
00:15:23,176 --> 00:15:25,050
Och som ser identisk
till en stapel så här långt,

328
00:15:25,050 --> 00:15:27,190
förutom att jag behöver göra en förändring.

329
00:15:27,190 --> 00:15:33,680
Jag behöver uppdatera denna storlek, så jag går
från noll till en till 2 till tre nu.

330
00:15:33,680 --> 00:15:35,760
Hur gör jag avköa?

331
00:15:35,760 --> 00:15:36,890
Vad händer med dequeue?

332
00:15:36,890 --> 00:15:41,950
Vem ska lossna här listan först
om det är ledningen 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 är typ av svårare den här gången.

335
00:15:44,700 --> 00:15:47,880
Medan förra gången det var super
lätt att bara göra storlek minus ett,

336
00:15:47,880 --> 00:15:51,440
Jag kommer till slutet av min samling effektivt
där siffrorna är, tar bort det 61.

337
00:15:51,440 --> 00:15:52,920
Men jag vill inte ta bort 61.

338
00:15:52,920 --> 00:15:55,030
Jag vill ta 50, som
var där vid 05:00

339
00:15:55,030 --> 00:15:56,790
att rada upp för
ny iPhone eller whatnot.

340
00:15:56,790 --> 00:16:01,200
Och så för att bli av 50, jag
kan inte bara göra det, eller hur?

341
00:16:01,200 --> 00:16:02,547
Jag kan stryka 50.

342
00:16:02,547 --> 00:16:04,380
Men vi sa bara vi
behöver inte vara så anal

343
00:16:04,380 --> 00:16:06,330
att skrapa ut eller dölja data.

344
00:16:06,330 --> 00:16:08,090
Vi kan bara glömma där det är.

345
00:16:08,090 --> 00:16:12,330
>> Men om jag ändrar min storlek nu
två, är detta tillräckligt med information

346
00:16:12,330 --> 00:16:15,711
att veta vad som händer i mitt kön?

347
00:16:15,711 --> 00:16:16,680
Inte riktigt.

348
00:16:16,680 --> 00:16:19,830
Liksom min storlek är två, men
Vari kön börjar,

349
00:16:19,830 --> 00:16:22,980
speciellt om jag har fortfarande
samma nummer i minnet.

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

351
00:16:24,260 --> 00:16:27,090
Så jag måste komma ihåg
nu där den främre är.

352
00:16:27,090 --> 00:16:29,630
Och så jag föreslog upp
där vi har bara kallas

353
00:16:29,630 --> 00:16:33,729
N: te front, vars ursprungliga
värde borde ha varit vad?

354
00:16:33,729 --> 00:16:35,270
Zero, bara början på listan.

355
00:16:35,270 --> 00:16:40,876
Men nu förutom nedräkning
storlek, vi bara öka fronten.

356
00:16:40,876 --> 00:16:42,000
Nu här är ett annat problem.

357
00:16:42,000 --> 00:16:43,030
Så när jag hålla kommer.

358
00:16:43,030 --> 00:16:47,520
Antag att detta är antalet
liknande 121, 124, och sedan, helvete,

359
00:16:47,520 --> 00:16:48,610
Jag är ute i rymden.

360
00:16:48,610 --> 00:16:50,390
Men vänta en minut, jag inte.

361
00:16:50,390 --> 00:16:55,630
Så vid denna tidpunkt i historien,
antar att storleken är en, två,

362
00:16:55,630 --> 00:17:00,370
tre, fyra, så anta att
storlek är fyra, fronten är en,

363
00:17:00,370 --> 00:17:01,621
så 51 är vid fronten.

364
00:17:01,621 --> 00:17:04,329
Jag vill sätta ett annat nummer här,
men, helvete, jag är ute i rymden.

365
00:17:04,329 --> 00:17:06,710
Men jag är inte riktigt, eller hur?

366
00:17:06,710 --> 00:17:11,192
Var kan jag sätta några
mervärde, som 171?

367
00:17:11,192 --> 00:17:13,400
Ja, jag kunde bara typ av
gå tillbaka dit, eller hur?

368
00:17:13,400 --> 00:17:18,161
Och sedan stryka 50, eller
bara skriva det med 171.

369
00:17:18,161 --> 00:17:20,410
Och om du undrar varför
våra siffror fick så slumpmässigt,

370
00:17:20,410 --> 00:17:24,150
dessa är vanligen tas dator
vetenskap kurser på Harvard efter CS50.

371
00:17:24,150 --> 00:17:27,510
Men det var en bra optimering,
för nu jag inte slösa utrymme.

372
00:17:27,510 --> 00:17:30,750
Jag har fortfarande komma ihåg
hur stor denna sak är total.

373
00:17:30,750 --> 00:17:31,500
Det är fem totalt.

374
00:17:31,500 --> 00:17:33,375
Eftersom jag inte vill
börja skriva över 51.

375
00:17:33,375 --> 00:17:36,260
Så nu är jag fortfarande slut på utrymme,
så samma problem som tidigare.

376
00:17:36,260 --> 00:17:39,140
Men du kan se hur nu
i din kod, du förmodligen

377
00:17:39,140 --> 00:17:41,910
måste skriva lite mer
komplexitet för att förverkliga detta.

378
00:17:41,910 --> 00:17:44,510
Och faktiskt, vad operatör
i C förmodligen låter

379
00:17:44,510 --> 00:17:48,110
du magiskt göra detta cirkularitet?

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

381
00:17:50,160 --> 00:17:53,160
Så vad är ganska coolt om en kö,
även om vi håller ritning arrayer

382
00:17:53,160 --> 00:17:56,520
eftersom dessa liknande raka linjer, om du
typ av tycker om detta som krökning

383
00:17:56,520 --> 00:18:00,341
runt som en cirkel, sedan bara
intuitivt det slags fungerar mentalt

384
00:18:00,341 --> 00:18:01,590
Jag tror att en lite renare.

385
00:18:01,590 --> 00:18:05,190
Du skulle fortfarande behöva genomföra
att mental modell i koden.

386
00:18:05,190 --> 00:18:07,550
Så inte så svårt,
i slutändan, att genomföra,

387
00:18:07,550 --> 00:18:12,430
men vi fortfarande förlorar size-- snarare
möjligheten att ändra storlek, om vi inte gör detta.

388
00:18:12,430 --> 00:18:15,310
>> Vi måste bli av med array, vi
ersätta den med en enda pekare,

389
00:18:15,310 --> 00:18:20,010
och sedan någonstans i min kod jag har
ett samtal vilken funktion att faktiskt skapa

390
00:18:20,010 --> 00:18:23,720
arrayen uppringda numren?

391
00:18:23,720 --> 00:18:26,190
Malloc, eller något liknande
funktion, exakt.

392
00:18:26,190 --> 00:18:30,481
Har du frågor om staplar eller köer.

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

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

395
00:18:33,657 --> 00:18:34,240
Bra fråga.

396
00:18:34,240 --> 00:18:35,830
Vad modulo skulle du använda här.

397
00:18:35,830 --> 00:18:38,520
Så generellt, när du använder
mod, skulle du göra det

398
00:18:38,520 --> 00:18:40,620
med storleken av den
Hela datastruktur.

399
00:18:40,620 --> 00:18:44,120
Så något som fem eller kapacitet, om
Det är konstant, är troligen inblandade.

400
00:18:44,120 --> 00:18:47,100
Men bara göra modulo fem
förmodligen inte är tillräckligt,

401
00:18:47,100 --> 00:18:51,380
eftersom vi behöver veta vi
lindas runt här eller här eller här.

402
00:18:51,380 --> 00:18:54,160
Så du är förmodligen också
kommer att vilja engagera

403
00:18:54,160 --> 00:18:57,220
storleken på sak, eller
front variabeln också.

404
00:18:57,220 --> 00:19:00,140
Så det är just detta relativt
enkla aritmetiska uttryck,

405
00:19:00,140 --> 00:19:02,000
men modulo skulle vara den viktigaste ingrediensen.

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

407
00:19:03,330 --> 00:19:05,780
En animering som en del
folks vid ett annat universitet

408
00:19:05,780 --> 00:19:08,060
sätta ihop att vi har
anpassad för denna diskussion.

409
00:19:08,060 --> 00:19:12,630
Det handlar om Jack lära sig
fakta om köer och statistik.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: En gång i tiden,
Det var en kille som heter Jack.

412
00:19:21,890 --> 00:19:25,330
När det kom till att göra vänner,
Jack hade inte en talang.

413
00:19:25,330 --> 00:19:28,220
Så Jack gick att prata med
mest populär kille han kände.

414
00:19:28,220 --> 00:19:30,920
Han gick till Lou och frågade, vad ska jag göra?

415
00:19:30,920 --> 00:19:33,400
Lou såg att hans vän
var verkligen bedrövad.

416
00:19:33,400 --> 00:19:36,050
Tja, började han, precis
se hur du är klädd.

417
00:19:36,050 --> 00:19:38,680
Har du inte ha några kläder
med ett annorlunda utseende?

418
00:19:38,680 --> 00:19:39,660
Ja, säger Jack.

419
00:19:39,660 --> 00:19:40,840
Jag säker gör.

420
00:19:40,840 --> 00:19:43,320
Kom till mitt hus och
Jag ska visa dem till dig.

421
00:19:43,320 --> 00:19:44,550
Så de gick till Jack.

422
00:19:44,550 --> 00:19:47,520
Och Jack visade Lou rutan
där han höll alla hans skjortor,

423
00:19:47,520 --> 00:19:49,260
och hans byxor och hans strumpor.

424
00:19:49,260 --> 00:19:52,290
Lou sa, jag ser att du har
alla dina kläder i en hög.

425
00:19:52,290 --> 00:19:54,870
Varför inte du bära vissa
andra gång på ett tag?

426
00:19:54,870 --> 00:19:58,020
>> Jack sa, ja, när jag
ta bort kläder och strumpor,

427
00:19:58,020 --> 00:20:00,780
Jag tvättar dem och sätta
bort dem i lådan.

428
00:20:00,780 --> 00:20:03,210
Sedan kommer nästa
morgon, och upp mig hopp.

429
00:20:03,210 --> 00:20:06,380
Jag går till lådan och få
mina kläder utanför toppen.

430
00:20:06,380 --> 00:20:09,070
Lou insåg snabbt
problemet med Jack.

431
00:20:09,070 --> 00:20:12,080
Han höll kläder, CD-skivor,
och böcker i stapeln.

432
00:20:12,080 --> 00:20:14,420
När han sträckte sig efter
något att läsa eller att bära,

433
00:20:14,420 --> 00:20:17,100
han skulle välja den övre bok eller underkläder.

434
00:20:17,100 --> 00:20:19,500
Sen när han var klar, han
skulle uttrycka det tillbaka.

435
00:20:19,500 --> 00:20:21,970
Tillbaka det skulle gå, ovanpå stapeln.

436
00:20:21,970 --> 00:20:24,460
Jag vet lösningen,
sade en triumferande Loud.

437
00:20:24,460 --> 00:20:27,090
Du måste lära dig att
börja använda en kö.

438
00:20:27,090 --> 00:20:29,870
Lou tog Jack kläder och
hängde dem i garderoben.

439
00:20:29,870 --> 00:20:32,710
Och när han hade tömt
rutan, han bara kastade den.

440
00:20:32,710 --> 00:20:36,500
>> Då sade han, nu Jack, i slutet av
dagen, sätta dina kläder på vänster

441
00:20:36,500 --> 00:20:37,990
när du lägger undan dem.

442
00:20:37,990 --> 00:20:41,300
Sedan i morgon bitti när du
se solen, få dina kläder

443
00:20:41,300 --> 00:20:43,440
till höger, från slutet av raden.

444
00:20:43,440 --> 00:20:44,880
Ser du inte? sade Lou.

445
00:20:44,880 --> 00:20:46,370
Det ska bli så skönt.

446
00:20:46,370 --> 00:20:49,770
Du kommer att ha allt en gång
innan du bär något två gånger.

447
00:20:49,770 --> 00:20:52,670
Och med allt i köer
i sin garderob och hylla,

448
00:20:52,670 --> 00:20:55,160
Jack började känna
helt säker på sig själv.

449
00:20:55,160 --> 00:20:59,720
Allt tack vare Lou och
hans underbara kö.

450
00:20:59,720 --> 00:21:01,220
TALARE 1: Okej, det är bedårande.

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

452
00:21:05,920 --> 00:21:10,080
Så vad har egentligen kommer
på under huven nu?

453
00:21:10,080 --> 00:21:12,370
Att vi har pekare,
att vi har malloc,

454
00:21:12,370 --> 00:21:15,680
att vi har förmågan att skapa
bitar av minne för oss

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

456
00:21:16,344 --> 00:21:18,510
Så det här är en bild vi
skymtade bara häromdagen.

457
00:21:18,510 --> 00:21:21,180
Vi visste inte riktigt bo
på det, men den här bilden

458
00:21:21,180 --> 00:21:24,180
har pågått under
huven i flera veckor nu.

459
00:21:24,180 --> 00:21:27,050
Och så detta representerar bara
en rektangel som vi har ritat,

460
00:21:27,050 --> 00:21:28,180
datorns minne.

461
00:21:28,180 --> 00:21:31,850
Och kanske din dator, eller CS50
ID, har en gigabyte minne eller RAM

462
00:21:31,850 --> 00:21:33,050
eller två gigabyte eller fyra.

463
00:21:33,050 --> 00:21:34,450
Det spelar egentligen ingen roll.

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

465
00:21:37,240 --> 00:21:41,120
i huvudsak gör ditt program
att tro att det har tillgång

466
00:21:41,120 --> 00:21:42,982
till helheten av
datorns minne,

467
00:21:42,982 --> 00:21:45,440
även om du kanske köra
flera program samtidigt.

468
00:21:45,440 --> 00:21:46,990
Så i verkligheten, som egentligen inte fungerar.

469
00:21:46,990 --> 00:21:49,448
Men det är typ av en illusion
ges till alla dina program.

470
00:21:49,448 --> 00:21:53,110
Så om du hade två gig RAM, detta
är hur datorn kan tänka på det.

471
00:21:53,110 --> 00:21:57,110
>> Nu tillfällighet, en av dessa
saker, ett av dessa segment av minnet,

472
00:21:57,110 --> 00:21:58,350
kallas en stapel.

473
00:21:58,350 --> 00:22:01,680
Och faktiskt helst
hittills i att skriva kod

474
00:22:01,680 --> 00:22:05,900
att du har ringt en
funktion, till exempel huvud.

475
00:22:05,900 --> 00:22:08,410
Minns att varje gång jag har
dragen datorns minne,

476
00:22:08,410 --> 00:22:10,640
Jag drar alltid sorts
hälften av en rektangel här

477
00:22:10,640 --> 00:22:12,520
och inte bryr sig prata
om vad som är ovan.

478
00:22:12,520 --> 00:22:15,980
För när huvud kallas, hävdar jag
att du får den här flisa av minne

479
00:22:15,980 --> 00:22:16,970
som går här nere.

480
00:22:16,970 --> 00:22:20,650
Och om huvud kallas en funktion
som swap, väl swap går här.

481
00:22:20,650 --> 00:22:23,720
Och det visar sig, det är
där det hamna.

482
00:22:23,720 --> 00:22:26,277
På något som kallas en stapel
insidan av din dators minne.

483
00:22:26,277 --> 00:22:28,360
Nu vid slutet av dagen,
detta är bara adresser.

484
00:22:28,360 --> 00:22:30,680
Det är som byte noll,
byte en, byte 2 miljarder kronor.

485
00:22:30,680 --> 00:22:33,130
Men om man tänker på det
eftersom detta rektangulärt föremål,

486
00:22:33,130 --> 00:22:35,130
allt vi gör varje
När vi kallar en funktion är

487
00:22:35,130 --> 00:22:37,180
skiktning en ny skiva minne.

488
00:22:37,180 --> 00:22:41,700
Vi ger denna funktion en skiva
av sitt eget minne för att arbeta med.

489
00:22:41,700 --> 00:22:44,490
>> Och minns nu att detta är viktigt.

490
00:22:44,490 --> 00:22:46,400
För om vi har
något liknande swap

491
00:22:46,400 --> 00:22:51,610
och två lokala variabler som A och B och
vi ändra dessa värden från en och två

492
00:22:51,610 --> 00:22:55,130
till två och en, minns
att när växlings returnerar,

493
00:22:55,130 --> 00:22:58,330
det är som om detta segment
minne är bara borta.

494
00:22:58,330 --> 00:23:00,080
I verkligheten är det fortfarande
där forensically.

495
00:23:00,080 --> 00:23:01,940
Och något är fortfarande faktiskt där.

496
00:23:01,940 --> 00:23:05,410
Men begreppsmässigt är det som
om det är helt borta.

497
00:23:05,410 --> 00:23:10,910
Och så huvud inte känner någon av arbetet
som gjordes i den swap-funktion,

498
00:23:10,910 --> 00:23:14,890
om det är faktiskt gått i dessa
argument från pekare eller med hänvisning.

499
00:23:14,890 --> 00:23:17,790
Nu, den grundläggande lösningen
till det problemet med swap

500
00:23:17,790 --> 00:23:19,970
passerar saker i efter adress.

501
00:23:19,970 --> 00:23:23,250
Men det visar sig också, vad är
pågått över den delen

502
00:23:23,250 --> 00:23:26,330
av rektangeln hela denna tid är
men det finns mer minne uppe.

503
00:23:26,330 --> 00:23:28,790
Och när du dynamiskt
allokera minne,

504
00:23:28,790 --> 00:23:32,020
oavsett om det är inne i getString, som
vi har gjort på dig i CS50

505
00:23:32,020 --> 00:23:34,710
bibliotek, eller om ni
ringa malloc och fråga

506
00:23:34,710 --> 00:23:37,950
operativsystemet för en bit av
minne, men det kommer inte från stapeln.

507
00:23:37,950 --> 00:23:40,960
Den kommer från en annan plats
i datorns minne

508
00:23:40,960 --> 00:23:42,220
som kallas högen.

509
00:23:42,220 --> 00:23:43,430
Och det är inte annorlunda.

510
00:23:43,430 --> 00:23:44,285
Det är samma RAM.

511
00:23:44,285 --> 00:23:45,160
Det är samma minne.

512
00:23:45,160 --> 00:23:49,080
Det är bara RAM som är upp
där i stället för här nere.

513
00:23:49,080 --> 00:23:50,750
>> Så vad betyder det?

514
00:23:50,750 --> 00:23:53,650
Tja, om datorn har
en begränsad mängd minne

515
00:23:53,650 --> 00:23:57,450
och stapeln växer upp, så
att tala, och högen, enligt

516
00:23:57,450 --> 00:23:59,349
till den här pilen, växer ned.

517
00:23:59,349 --> 00:24:01,140
Med andra ord, varje
gång du ringer malloc,

518
00:24:01,140 --> 00:24:03,430
du får en skiva
minne från ovan,

519
00:24:03,430 --> 00:24:06,630
då kanske en lite lägre, sedan lite
lägre, varje gång du ringer malloc,

520
00:24:06,630 --> 00:24:10,100
högen, det är användning,
är typ att växa,

521
00:24:10,100 --> 00:24:11,950
allt närmare och närmare till vad?

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

523
00:24:13,382 --> 00:24:14,840
Det gör detta verka som en bra idé?

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

525
00:24:18,420 --> 00:24:22,140
Jag menar, om det inte är riktigt klart
vad du kan göra om du bara

526
00:24:22,140 --> 00:24:23,910
har en begränsad mängd minne.

527
00:24:23,910 --> 00:24:25,200
Men detta är ju dåligt.

528
00:24:25,200 --> 00:24:27,920
Dessa två pilar är på en
krascha kurs för varandra.

529
00:24:27,920 --> 00:24:31,930
>> Och det visar sig att skurken, folk som
är särskilt bra med programmering,

530
00:24:31,930 --> 00:24:36,140
och försöker hacka in i datorer,
kan utnyttja denna verklighet.

531
00:24:36,140 --> 00:24:38,290
I själva verket, låt oss betrakta
lite kodavsnitt.

532
00:24:38,290 --> 00:24:41,350
Så det här är ett exempel som du kan läsa
om närmare på Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Vi kommer att peka dig i
artikeln om nyfikna.

534
00:24:43,100 --> 00:24:45,650
Men det finns en attack i allmänhet
känd som buffertspill som

535
00:24:45,650 --> 00:24:49,570
har funnits så länge som människor
har haft förmågan att manipulera

536
00:24:49,570 --> 00:24:53,120
datorns minne, i synnerhet i C.
Så det här är ett mycket godtyckligt program,

537
00:24:53,120 --> 00:24:55,130
men låt oss läsa det nerifrån och upp.

538
00:24:55,130 --> 00:24:57,650
Huvud in argC röding stjärna argv.

539
00:24:57,650 --> 00:24:59,830
Så det är ett program som tar
kommandoradsargument.

540
00:24:59,830 --> 00:25:03,620
Och alla huvud gör tydligen är samtal
en funktion, kalla det F för enkelhetens skull.

541
00:25:03,620 --> 00:25:04,610
Och det passerar i vad?

542
00:25:04,610 --> 00:25:05,490
Argv av en.

543
00:25:05,490 --> 00:25:09,320
Så det passerar in F oavsett
ordet är att användaren har skrivit

544
00:25:09,320 --> 00:25:11,500
vid prompten efter
programmets namn alls.

545
00:25:11,500 --> 00:25:15,730
Så mycket som Caesar eller Vigenère, som
Du kanske kommer ihåg att göra med argv.

546
00:25:15,730 --> 00:25:16,680
>> Så vad är F?

547
00:25:16,680 --> 00:25:19,760
F tar i en sträng
som enda argument,

548
00:25:19,760 --> 00:25:22,100
AKA en röding stjärna, samma
sak, som en sträng.

549
00:25:22,100 --> 00:25:24,920
Och det kallas godtyckligt
bar i detta exempel.

550
00:25:24,920 --> 00:25:27,710
Och sedan char c 12,
bara i lekmannaspråk,

551
00:25:27,710 --> 00:25:31,750
vad är char c fästet 12 gör för oss?

552
00:25:31,750 --> 00:25:33,440
Hur är det att göra?

553
00:25:33,440 --> 00:25:36,490
Allokering av minne, speciellt
12 byte för 12 tecken.

554
00:25:36,490 --> 00:25:36,990
Exakt.

555
00:25:36,990 --> 00:25:40,000
Och sedan den sista raden, rör om och
kopia, har du antagligen inte sett.

556
00:25:40,000 --> 00:25:43,360
Detta är en sträng kopia
funktion vars syfte i livet

557
00:25:43,360 --> 00:25:48,160
är att kopiera sitt andra argument
i sitt första argument,

558
00:25:48,160 --> 00:25:51,190
men bara upp till en
visst antal bitgrupper.

559
00:25:51,190 --> 00:25:53,860
Så det tredje argumentet säger,
hur många bytes bör du mig?

560
00:25:53,860 --> 00:25:56,720
Längden på bar,
oavsett användaren har skrivit in.

561
00:25:56,720 --> 00:25:59,320
Och innehållet i
bar, den strängen, är

562
00:25:59,320 --> 00:26:02,330
kopieras till minnet pekade på vid C.

563
00:26:02,330 --> 00:26:04,060
>> Så detta verkar vara lite dum, och det är.

564
00:26:04,060 --> 00:26:06,300
Det är en konstruerad exempel,
men det är representativt

565
00:26:06,300 --> 00:26:10,100
av en klass av attack vektorer
ett sätt att angripa ett program.

566
00:26:10,100 --> 00:26:15,050
Allt är fint och bra om användaren
typer i ett ord som är 11 tecken

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

568
00:26:18,040 --> 00:26:22,830
Vad händer om användaren skriver i mer än
11 eller 12 eller 20 eller 50 tecken?

569
00:26:22,830 --> 00:26:25,090
Vad är det här programmet kommer att göra?

570
00:26:25,090 --> 00:26:29,360
Potentiellt seg fel. Det går
blint kopiera allt i bar upp

571
00:26:29,360 --> 00:26:31,750
med dess längd, som är
bokstavligen allt i bar,

572
00:26:31,750 --> 00:26:36,307
i adress pekade på C. Men C
har endast förebyggande syfte ges som 12 byte.

573
00:26:36,307 --> 00:26:37,640
Men det finns ingen ytterligare kontroll.

574
00:26:37,640 --> 00:26:38,700
Det finns inget om förhållandena.

575
00:26:38,700 --> 00:26:40,580
Det finns ingen felkontroll här.

576
00:26:40,580 --> 00:26:43,270
>> Och så vad detta program är
kommer att göra är bara blint

577
00:26:43,270 --> 00:26:45,750
kopiera en sak till en annan.

578
00:26:45,750 --> 00:26:47,880
Och så om vi dra denna
som en bild, här är

579
00:26:47,880 --> 00:26:49,860
bara en flisa av minnesutrymmet.

580
00:26:49,860 --> 00:26:53,470
Så märker på botten, vi
har den lokala variabeln baren.

581
00:26:53,470 --> 00:26:57,330
Så att pekare som kommer att store--
snarare att lokal argument som är

582
00:26:57,330 --> 00:26:58,672
kommer att lagra strängen bar.

583
00:26:58,672 --> 00:27:00,380
Och sedan märker bara
över den i en stapel,

584
00:27:00,380 --> 00:27:02,505
eftersom varje gång du frågar
för minnes på stacken,

585
00:27:02,505 --> 00:27:04,310
Det går lite
ovanför pictorially,

586
00:27:04,310 --> 00:27:06,270
märker att vi har 12 byte där.

587
00:27:06,270 --> 00:27:10,690
Den övre vänstra är C fäste noll och
det nedre högra en är Ci konsol 11.

588
00:27:10,690 --> 00:27:12,870
Det är bara hur datorerna
kommer att lägga ut det.

589
00:27:12,870 --> 00:27:18,300
Så bara intuitivt, om bar har mer
än 12 tecken totalt, inklusive

590
00:27:18,300 --> 00:27:25,790
backslash noll, där är
12 eller C fästet 12 kommer att gå?

591
00:27:25,790 --> 00:27:28,440
Eller snarare var är den 12: e
förmåga eller 13 tecken,

592
00:27:28,440 --> 00:27:30,900
hundrade karaktär går
att hamna i bilden?

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

594
00:27:33,400 --> 00:27:36,300
>> Höger, för även om
stapeln själv växer uppåt,

595
00:27:36,300 --> 00:27:39,590
När du har lagt saker i
det, konstruktionstekniska skäl,

596
00:27:39,590 --> 00:27:41,294
sätter minnet från topp till botten.

597
00:27:41,294 --> 00:27:44,460
Så om du har mer än 12 byte,
du kommer att börja skriva bar.

598
00:27:44,460 --> 00:27:47,280
Nu det är en bugg, men det är
egentligen inte en big deal.

599
00:27:47,280 --> 00:27:51,130
Men det är en stor sak, eftersom det finns
mer grejer på gång i minnet.

600
00:27:51,130 --> 00:27:53,074
Så här är hur vi kanske
sätta hej, att vara tydlig.

601
00:27:53,074 --> 00:27:54,490
Om jag skrev i hello vid prompten.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O snedstreck noll, hamnar inom
dessa 12 bytes, och vi är mycket säkra.

603
00:27:59,330 --> 00:28:00,330
Allt är bra.

604
00:28:00,330 --> 00:28:03,020
Men om jag skriver något
längre, potentiellt är det

605
00:28:03,020 --> 00:28:05,860
kommer att krypa in bar utrymme.

606
00:28:05,860 --> 00:28:08,405
Men ännu värre, visar det
ut hela tiden,

607
00:28:08,405 --> 00:28:11,530
även om vi aldrig har talat om
Det är stacken används för andra saker.

608
00:28:11,530 --> 00:28:13,560
Det är inte bara lokala variabler.

609
00:28:13,560 --> 00:28:15,100
>> C är ett språk mycket låg nivå.

610
00:28:15,100 --> 00:28:17,810
Och det slags hemlighet
använder stapeln också

611
00:28:17,810 --> 00:28:21,260
att komma ihåg när ett
funktionen kallas, vad

612
00:28:21,260 --> 00:28:26,040
adressen är av den föregående funktion,
så det kan gå tillbaka till denna funktion.

613
00:28:26,040 --> 00:28:29,980
Så när huvud samtal byta, bland
de saker skjutas på stacken

614
00:28:29,980 --> 00:28:34,380
är inte bara byter lokala variabler,
eller sina argument, också i hemlighet drivit

615
00:28:34,380 --> 00:28:37,510
på stacken såsom representeras
av den röda skivan här,

616
00:28:37,510 --> 00:28:40,520
är adressen till huvud fysiskt
i datorns minne,

617
00:28:40,520 --> 00:28:44,180
så att när växlings är gjort, datorn
vet att jag måste gå tillbaka till huvud

618
00:28:44,180 --> 00:28:46,760
och avsluta exekvera den viktigaste funktionen.

619
00:28:46,760 --> 00:28:51,960
Så det här är farligt nu, för om
användaren skriver på väl mer än hej,

620
00:28:51,960 --> 00:28:57,030
sådan att användarens indata clobbers
eller skriver att röda delen,

621
00:28:57,030 --> 00:28:59,820
logiskt om datorns
bara att blint anta

622
00:28:59,820 --> 00:29:03,830
att de bytes i den röda skiva är
adressen som den ska returnera,

623
00:29:03,830 --> 00:29:09,020
vad händer om motståndaren är smart nog eller
turen att sätta en sekvens av bytes

624
00:29:09,020 --> 00:29:13,450
Det som ser ut som en adress,
men det är adressen till koden

625
00:29:13,450 --> 00:29:18,730
att han eller hon vill ha datorn
att köra i stället för huvud?

626
00:29:18,730 --> 00:29:21,670
>> Med andra ord, om det som
användaren är att skriva vid prompten,

627
00:29:21,670 --> 00:29:23,850
är inte bara något
ofarlig som hej,

628
00:29:23,850 --> 00:29:28,210
men det är faktiskt kod som är likvärdig
att ta bort alla här användarens filer?

629
00:29:28,210 --> 00:29:30,060
Eller mejla sitt lösenord till mig?

630
00:29:30,060 --> 00:29:31,940
Eller börja logga deras
tangenttryckningar, eller hur?

631
00:29:31,940 --> 00:29:34,920
Det finns ett sätt, låt oss fastställa dag,
att de kunde skriva in inte bara hej

632
00:29:34,920 --> 00:29:36,711
värld eller deras namn,
de kunde i huvudsak

633
00:29:36,711 --> 00:29:39,570
passera kod, nollor och
sådana, att datorn

634
00:29:39,570 --> 00:29:43,450
misstag för både kod och en adress.

635
00:29:43,450 --> 00:29:48,950
Så om än något abstrakt, om
användartyper i tillräckligt kontradiktoriska kod

636
00:29:48,950 --> 00:29:52,330
att vi ska generalisera här som
A. A är attack eller motståndare.

637
00:29:52,330 --> 00:29:53,140
Så bara dåliga grejer.

638
00:29:53,140 --> 00:29:55,306
Vi bryr oss inte om
siffror eller nollor och ettor

639
00:29:55,306 --> 00:29:59,470
idag, så att du hamnar
skrivs det röda delen,

640
00:29:59,470 --> 00:30:01,580
märker att bytesekvensen.

641
00:30:01,580 --> 00:30:05,020
O 835 C noll åtta noll.

642
00:30:05,020 --> 00:30:08,960
Och nu som Wikipedias artikel här
har föreslagit, om du nu verkligen börjar

643
00:30:08,960 --> 00:30:12,460
märkning av byte i datorns
minne, vad Wikipedia artikeln

644
00:30:12,460 --> 00:30:19,060
föreslå är att, tänk om adressen
av det övre vänstra byte är 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Med andra ord, om den onde är
smart nog med hans eller hennes kod

646
00:30:22,200 --> 00:30:26,650
att faktiskt sätta ett antal här som
motsvarar adressen av koden

647
00:30:26,650 --> 00:30:29,180
han eller hon injicerade
i datorn, du

648
00:30:29,180 --> 00:30:31,050
kan lura datorn
till att göra någonting.

649
00:30:31,050 --> 00:30:34,140
Ta bort filer, e-post
saker, sniffa din trafik,

650
00:30:34,140 --> 00:30:36,710
bokstavligen allt kan vara
sprutas in i datorn.

651
00:30:36,710 --> 00:30:39,220
Och så en buffer overflow
attack i sin kärna

652
00:30:39,220 --> 00:30:43,530
är bara en dum, dum
tvingande av en matris som

653
00:30:43,530 --> 00:30:45,840
inte har sina gränser kontrolleras.

654
00:30:45,840 --> 00:30:48,850
Och detta är vad är super farligt
och samtidigt super kraftfull

655
00:30:48,850 --> 00:30:52,560
i C är att vi har faktiskt
tillgång till någonstans i minnet.

656
00:30:52,560 --> 00:30:55,320
Det är upp till oss, programmerare,
som skriver den ursprungliga koden

657
00:30:55,320 --> 00:30:59,330
att kontrollera allra längden på
arrayer som vi manipulerar.

658
00:30:59,330 --> 00:31:00,750
Så för att vara tydlig, vad är fix?

659
00:31:00,750 --> 00:31:03,190
Om vi ​​rullar tillbaka till denna
kod, jag borde inte bara

660
00:31:03,190 --> 00:31:08,000
ändra längden på baren, vad
annars ska jag kontrollera?

661
00:31:08,000 --> 00:31:10,620
Vad ska jag göra för att
förhindra denna attack helt?

662
00:31:10,620 --> 00:31:14,110
Jag vill inte bara blint säga
att du bör kopiera så många bytes

663
00:31:14,110 --> 00:31:16,140
som är längden på baren.

664
00:31:16,140 --> 00:31:18,910
Jag vill säga, kopiera som
många bytes som finns i bar

665
00:31:18,910 --> 00:31:24,090
upp till den tilldelade
minne, eller 12 maximalt.

666
00:31:24,090 --> 00:31:27,450
Så jag behöver någon form av om tillstånd
som gör kontrollera längden på baren,

667
00:31:27,450 --> 00:31:32,800
men om den överstiger 12, vi bara hårdkoda
12 som den största möjliga avstånd.

668
00:31:32,800 --> 00:31:35,910
Annars så kallade buffert
overflow attack kan hända.

669
00:31:35,910 --> 00:31:38,451
Längst ner på dessa bilder,
Om du är nyfiken på att läsa mer

670
00:31:38,451 --> 00:31:41,200
är den faktiska ursprungliga artikeln
Om du vill ta en titt.

671
00:31:41,200 --> 00:31:44,550
>> Men nu, bland priserna
betalade här var ineffektivitet.

672
00:31:44,550 --> 00:31:46,680
Så det var en snabb
låg look nivå på vad

673
00:31:46,680 --> 00:31:49,709
problem kan uppstå nu när vi
har tillgång till datorns minne.

674
00:31:49,709 --> 00:31:51,750
Men ett annat problem som vi
redan snubblat på måndag

675
00:31:51,750 --> 00:31:53,800
var bara ineffektivitet
av en länkad lista.

676
00:31:53,800 --> 00:31:56,019
Vi är tillbaka till linjär tid.

677
00:31:56,019 --> 00:31:57,560
Vi har inte längre en sammanhängande matris.

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

679
00:31:58,980 --> 00:32:00,710
Vi kan inte använda klammer notation.

680
00:32:00,710 --> 00:32:04,590
Vi har bokstavligen att använda en while-slinga
som jag skrev för en stund sedan.

681
00:32:04,590 --> 00:32:09,740
Men på måndag, hävdade vi att vi kan
krypa tillbaka in i sfären av effektivitet

682
00:32:09,740 --> 00:32:13,040
uppnå något som är
logaritmisk kanske, eller bästa ännu,

683
00:32:13,040 --> 00:32:16,120
kanske till och med något som är
s.k. konstant tid.

684
00:32:16,120 --> 00:32:19,840
Så hur kan vi göra det genom att använda dessa nya
verktyg, dessa adresser, dessa pekare,

685
00:32:19,840 --> 00:32:22,210
och gäng saker i vår egen?

686
00:32:22,210 --> 00:32:23,960
Tja, antar att
här, det är ett gäng

687
00:32:23,960 --> 00:32:27,170
av siffror som vi vill lagra i en
datastruktur och sökning effektivt.

688
00:32:27,170 --> 00:32:30,960
Vi kan absolut spola tillbaka till vecka
två, kasta dessa i en matris,

689
00:32:30,960 --> 00:32:33,150
och söka dem med binär sökning.

690
00:32:33,150 --> 00:32:34,040
Söndra och härska.

691
00:32:34,040 --> 00:32:37,720
Och i själva verket du skrev
binär sökning i PSET3,

692
00:32:37,720 --> 00:32:40,100
där du genomfört hitta programmet.

693
00:32:40,100 --> 00:32:40,890
Men vet du vad.

694
00:32:40,890 --> 00:32:45,060
Det är lite av en mer
smart sätt att göra detta.

695
00:32:45,060 --> 00:32:47,390
Det är lite mer
sofistikerade och det kanske

696
00:32:47,390 --> 00:32:50,830
tillåter oss att se varför binära
Sökningen är så mycket snabbare.

697
00:32:50,830 --> 00:32:52,980
Låt oss först införa
föreställningen av ett träd.

698
00:32:52,980 --> 00:32:54,730
Vilket även om det i
reality träd typ av

699
00:32:54,730 --> 00:32:57,730
växa så här, i en värld av dator
vetenskap de slags växa nedåt

700
00:32:57,730 --> 00:33:00,830
som ett släktträd, där du har
dina morföräldrar eller stora morföräldrar

701
00:33:00,830 --> 00:33:04,580
eller allt på toppen, patriarken och
matriark av familjen, bara en

702
00:33:04,580 --> 00:33:07,930
s.k. rot, nod, nedan
som är dess barn,

703
00:33:07,930 --> 00:33:11,442
under vilken det är dess barn, eller
dess ättlingar mer allmänt.

704
00:33:11,442 --> 00:33:13,400
Och den hängande
botten av familjen

705
00:33:13,400 --> 00:33:16,070
träd, förutom att vara den
yngst i familjen,

706
00:33:16,070 --> 00:33:19,520
kan också bara vara generiskt
kallas blad av trädet.

707
00:33:19,520 --> 00:33:21,800
>> Så det här är bara ett gäng
ord och definitioner

708
00:33:21,800 --> 00:33:25,790
för något som kallas ett träd i dator
vetenskap, ungefär som ett släktträd.

709
00:33:25,790 --> 00:33:28,770
Men det finns snyggare inkarnationer
av träd, en av vilka

710
00:33:28,770 --> 00:33:30,780
kallas ett binärt sökträd.

711
00:33:30,780 --> 00:33:34,380
Och du kan typ av tease
isär vad den här saken gör.

712
00:33:34,380 --> 00:33:37,180
Tja, det är binär i vilken mening?

713
00:33:37,180 --> 00:33:41,455
Varifrån kommer den binära kommer härifrån?

714
00:33:41,455 --> 00:33:41,955
Förlåt?

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

716
00:33:45,961 --> 00:33:47,210
Det är inte så mycket ett antingen eller.

717
00:33:47,210 --> 00:33:52,000
Det är mer att var och en av noderna har ingen
mer än två barn, som vi ser här.

718
00:33:52,000 --> 00:33:54,990
I allmänhet är ett tree-- och
dina föräldrar och farföräldrar

719
00:33:54,990 --> 00:33:57,640
kan ha så många barn eller
barnbarn som de faktiskt vill,

720
00:33:57,640 --> 00:34:00,820
och så till exempel där har vi tre
barn utanför den högra noden,

721
00:34:00,820 --> 00:34:05,480
men i ett binärt träd, har en nod
noll, en eller två barn maximalt.

722
00:34:05,480 --> 00:34:08,496
Och det är en bra egenskap,
för om det är täckt av två,

723
00:34:08,496 --> 00:34:10,620
vi kommer att kunna
få lite log bas två

724
00:34:10,620 --> 00:34:11,975
åtgärder som pågår här i slutändan.

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

726
00:34:13,350 --> 00:34:14,558
Men mer om det i ett ögonblick.

727
00:34:14,558 --> 00:34:19,810
Sökträd innebär att siffrorna är
anordnade så att den vänstra barnets

728
00:34:19,810 --> 00:34:22,429
värdet är större än roten.

729
00:34:22,429 --> 00:34:26,010
Och dess rätt barn är
större än roten.

730
00:34:26,010 --> 00:34:29,290
Med andra ord, om du tar något av
noder, cirklarna i den här bilden,

731
00:34:29,290 --> 00:34:31,840
och tittar på dess vänstra
barn och dess rätt barn,

732
00:34:31,840 --> 00:34:34,739
den första bör vara mindre än,
den andra bör vara större än.

733
00:34:34,739 --> 00:34:36,159
Så sanity ta 55.

734
00:34:36,159 --> 00:34:37,780
Det som är kvar barnet är 33.

735
00:34:37,780 --> 00:34:38,620
Det är mindre än.

736
00:34:38,620 --> 00:34:40,929
55, är dess högra underordnade 77.

737
00:34:40,929 --> 00:34:41,783
Det är större än.

738
00:34:41,783 --> 00:34:43,199
Och det är en rekursiv definition.

739
00:34:43,199 --> 00:34:46,480
Vi kan kontrollera varenda en av dem
noder och samma mönster skulle hålla.

740
00:34:46,480 --> 00:34:49,389
>> Så vad är trevligt i en
binärt sökträd, är

741
00:34:49,389 --> 00:34:52,204
att man kan vi genomföra det
med en struct, precis som detta.

742
00:34:52,204 --> 00:34:54,620
Och även om vi kastar
massor av strukturer på din,

743
00:34:54,620 --> 00:34:56,560
de är något
intuitiv nu förhoppningsvis.

744
00:34:56,560 --> 00:35:00,570
Syntaxen är fortfarande svårbegripliga för säker,
men innehållet i en nod i detta

745
00:35:00,570 --> 00:35:02,786
context-- och vi håller
använda ordet nod,

746
00:35:02,786 --> 00:35:04,910
oavsett om det är en rektangel
på skärmen eller en cirkel,

747
00:35:04,910 --> 00:35:08,970
Det är bara några generiska behållare,
i detta fall av ett träd, som en

748
00:35:08,970 --> 00:35:11,780
vi såg, vi behöver ett heltal
i var och en av noderna

749
00:35:11,780 --> 00:35:15,460
och då jag behöver två pekare pekar
till vänster barnet och högra underordnade,

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

751
00:35:16,590 --> 00:35:20,730
Så det är hur vi kanske
genomföra detta i en struct.

752
00:35:20,730 --> 00:35:22,315
Och hur kan jag genomföra det i koden?

753
00:35:22,315 --> 00:35:26,730
Nåväl, låt oss ta en snabb
titta på denna lilla exempel.

754
00:35:26,730 --> 00:35:29,820
Det är inte funktionell, men jag har
kopierat och klistrat denna struktur.

755
00:35:29,820 --> 00:35:33,510
Och om min funktion för en binär
sökträd kallas sökning,

756
00:35:33,510 --> 00:35:36,980
och detta tar två argument,
ett heltal N och en pekare

757
00:35:36,980 --> 00:35:41,400
till en nod, så en pekare till trädet
eller en pekare till roten av ett träd,

758
00:35:41,400 --> 00:35:43,482
Hur gör jag för att söka efter N?

759
00:35:43,482 --> 00:35:45,440
Tja, först, eftersom jag är
behandlar pekare,

760
00:35:45,440 --> 00:35:46,750
Jag kommer att göra en sanity check.

761
00:35:46,750 --> 00:35:54,279
Om träd jämlikar är lika med noll, är N
I det här trädet eller inte i detta träd?

762
00:35:54,279 --> 00:35:55,070
Det kan inte vara rätt?

763
00:35:55,070 --> 00:35:56,870
Om jag förbi null,
det finns inget där.

764
00:35:56,870 --> 00:35:59,230
Jag kan lika gärna bara
blint säger return false.

765
00:35:59,230 --> 00:36:04,050
Om du ger mig ingenting, jag kan ju inte
hitta valfritt antal N. Så vad mer jag kan

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

767
00:36:04,750 --> 00:36:12,830
Jag kommer att säga bra annars om N är
mindre än vad som är på trädet noden

768
00:36:12,830 --> 00:36:16,300
att jag har gått i arv N-värdet.

769
00:36:16,300 --> 00:36:20,270
Med andra ord, om numret är jag
söker, N, är mindre än den nod

770
00:36:20,270 --> 00:36:21,340
att jag tittar på.

771
00:36:21,340 --> 00:36:23,190
Och noden jag ser
vid kallas träd,

772
00:36:23,190 --> 00:36:26,370
och minns från föregående exempel
att komma åt värdet i en pekare,

773
00:36:26,370 --> 00:36:28,310
Jag använder pilen notation.

774
00:36:28,310 --> 00:36:35,960
Så om N är mindre än träd pil
N, jag vill begrepps gå vänster.

775
00:36:35,960 --> 00:36:38,590
Hur gör jag uttrycker SÖKA kvar?

776
00:36:38,590 --> 00:36:41,560
För att vara tydlig, om detta är
bilden i fråga,

777
00:36:41,560 --> 00:36:44,612
och jag har gått att översta
arrow som är pekar nedåt.

778
00:36:44,612 --> 00:36:45,570
Det är mitt träd pekare.

779
00:36:45,570 --> 00:36:48,060
Jag pekar på roten av trädet.

780
00:36:48,060 --> 00:36:52,100
Och jag ser att säga, för
siffran 44, godtyckligt.

781
00:36:52,100 --> 00:36:55,300
Är 44 mindre än eller
större än 55 självklart?

782
00:36:55,300 --> 00:36:56,360
Så det är mindre än.

783
00:36:56,360 --> 00:36:58,760
Och så detta om villkor gäller.

784
00:36:58,760 --> 00:37:03,981
Så begreppsmässigt, vad jag vill
Sök nästa om jag letar efter 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Just det, jag vill
söka i vänstra underordnade,

788
00:37:11,100 --> 00:37:12,789
eller vänster underträd av denna bild.

789
00:37:12,789 --> 00:37:14,830
Och i själva verket, låt mig igenom
bilden här nere

790
00:37:14,830 --> 00:37:17,770
för bara ett ögonblick, eftersom
Jag kan inte repa detta.

791
00:37:17,770 --> 00:37:21,150
Om jag börjar här vid 55, och
Jag vet att värdet 44

792
00:37:21,150 --> 00:37:23,180
Jag letar efter är att
vänster, det är typ

793
00:37:23,180 --> 00:37:26,010
som att riva telefonboken i
halv eller riva trädet på mitten.

794
00:37:26,010 --> 00:37:29,660
Jag behöver inte längre bry sig om
hela denna hälften av trädet.

795
00:37:29,660 --> 00:37:33,270
Och ändå, märkligt i termer av
struktur, denna sak hit att

796
00:37:33,270 --> 00:37:36,682
börjar med 33, som i sig
är ett binärt sökträd.

797
00:37:36,682 --> 00:37:39,890
Jag sa ordet rekursiva innan eftersom
faktiskt detta är en datastruktur som

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

799
00:37:41,707 --> 00:37:44,540
Du kanske har ett träd som det här
stor, men var och en av sina barn

800
00:37:44,540 --> 00:37:46,870
representerar ett träd bara lite mindre.

801
00:37:46,870 --> 00:37:50,910
I stället för att det är morfar
eller mormor, nu är det bara mamma

802
00:37:50,910 --> 00:37:54,300
eller-- jag kan inte säga-- inte mamma
eller pappa, skulle det vara konstigt.

803
00:37:54,300 --> 00:37:59,000
Istället de två barnen där
skulle vara som bror och syskon.

804
00:37:59,000 --> 00:38:01,120
En ny generation av släktträdet.

805
00:38:01,120 --> 00:38:02,900
Men strukturellt, det är samma idé.

806
00:38:02,900 --> 00:38:06,790
Och det visade sig att jag har en funktion
som jag kan söka en binär sökning

807
00:38:06,790 --> 00:38:07,290
träd.

808
00:38:07,290 --> 00:38:08,680
Det kallas sökning.

809
00:38:08,680 --> 00:38:17,870
Jag söker efter N träd pil vänster
annars om N är större än värdet

810
00:38:17,870 --> 00:38:18,870
att jag är för närvarande på.

811
00:38:18,870 --> 00:38:20,800
55 i berättelsen för en stund sedan.

812
00:38:20,800 --> 00:38:23,780
Jag har en funktion som kallas
sökmotor som jag kan bara

813
00:38:23,780 --> 00:38:29,660
passera N detta och rekursivt söka
sub-trädet och bara avkastning

814
00:38:29,660 --> 00:38:30,620
vad det svaret.

815
00:38:30,620 --> 00:38:33,530
Annars har jag några slutliga bas fallet här.

816
00:38:33,530 --> 00:38:35,310
>> Vad är det sista fallet?

817
00:38:35,310 --> 00:38:36,570
Tree är antingen noll.

818
00:38:36,570 --> 00:38:39,980
Värdet jag antingen letar efter är
mindre än den eller större än den

819
00:38:39,980 --> 00:38:42,610
eller lika med det.

820
00:38:42,610 --> 00:38:44,750
Och jag kunde säga lika
lika, men logiskt är det

821
00:38:44,750 --> 00:38:46,500
motsvarar bara säga annat här.

822
00:38:46,500 --> 00:38:49,150
Så sant är hur jag hittar något.

823
00:38:49,150 --> 00:38:51,710
Så förhoppningsvis är ett
ännu mer övertygande exempel

824
00:38:51,710 --> 00:38:54,900
än den dumma sigma funktionen
Vi gjorde några föreläsningar tillbaka,

825
00:38:54,900 --> 00:38:58,360
där det var lika enkelt att använda en slinga
att räkna upp alla nummer från en

826
00:38:58,360 --> 00:39:02,390
till N. Här med en datastruktur
som i sig själv är rekursivt

827
00:39:02,390 --> 00:39:07,050
definierade och rekursivt dras, nu vi
har förmågan att uttrycka oss

828
00:39:07,050 --> 00:39:09,780
i kod som själv är rekursiv.

829
00:39:09,780 --> 00:39:12,580
Så det här är exakt samma kod här.

830
00:39:12,580 --> 00:39:14,400
>> Så vad andra problem kan vi lösa?

831
00:39:14,400 --> 00:39:18,160
Så en snabb steg bort från
träd för bara ett ögonblick.

832
00:39:18,160 --> 00:39:20,130
Här är, säger den tyska flaggan.

833
00:39:20,130 --> 00:39:22,020
Och det är helt klart en
mönstret till denna flagga.

834
00:39:22,020 --> 00:39:23,811
Och det finns massor av
flaggor i världen som

835
00:39:23,811 --> 00:39:27,560
är så enkla som detta i termer
av deras färger och mönster.

836
00:39:27,560 --> 00:39:31,930
Men antag att detta lagras som en
GIF, eller JPEG eller bitmapp, eller en ping,

837
00:39:31,930 --> 00:39:34,240
något grafiskt filformat
som du är bekant,

838
00:39:34,240 --> 00:39:36,460
varav vi är
leka med i PSET4.

839
00:39:36,460 --> 00:39:41,550
Detta verkar inte värt att lagra
svart pixel, svart pixel, svart pixel,

840
00:39:41,550 --> 00:39:44,790
dot, punkt, punkt, en massa
svarta pixlar för den första avsökningsraden,

841
00:39:44,790 --> 00:39:47,430
eller rad, sedan en massa
densamma, sedan en hel drös

842
00:39:47,430 --> 00:39:49,530
av densamma, och sedan en
massa röda pixlar,

843
00:39:49,530 --> 00:39:53,020
röda pixlar, röda pixlar, sedan en hel
gäng gula pixlar, gul, eller hur?

844
00:39:53,020 --> 00:39:55,050
>> Det är en sådan ineffektivitet här.

845
00:39:55,050 --> 00:39:59,040
Hur skulle du intuitivt
komprimera den tyska flaggan

846
00:39:59,040 --> 00:40:01,320
om att genomföra det som en fil?

847
00:40:01,320 --> 00:40:04,940
Liksom vilken information kan vi inte
bry lagring på disk för

848
00:40:04,940 --> 00:40:08,040
att minska vår filstorleken från liknande
en megabyte till ett kilobyte, något

849
00:40:08,040 --> 00:40:09,430
mindre?

850
00:40:09,430 --> 00:40:13,130
Vari ligger redundans
här för att vara klart?

851
00:40:13,130 --> 00:40:13,880
Vad kan du göra?

852
00:40:13,880 --> 00:40:14,380
Yeah?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Exakt.

855
00:40:21,970 --> 00:40:24,550
Varför inte i stället minnas
färgen på varje darn pixel

856
00:40:24,550 --> 00:40:28,200
precis som du gör i PSET4
med bitmap-format,

857
00:40:28,200 --> 00:40:32,060
varför inte du bara representera
vänstra kolumnen av pixlar, t.ex.

858
00:40:32,060 --> 00:40:35,370
ett gäng svarta pixlar, ett gäng
rött, och ett gäng gul,

859
00:40:35,370 --> 00:40:39,210
och sedan bara något koda
idé upprepa detta 100 gånger

860
00:40:39,210 --> 00:40:41,020
eller upprepa detta 1000 gånger?

861
00:40:41,020 --> 00:40:43,430
Där 100 eller 1000 är
bara ett heltal, så att du

862
00:40:43,430 --> 00:40:47,290
kan komma undan med bara ett enda nummer
i stället för hundratals eller tusentals

863
00:40:47,290 --> 00:40:48,270
av ytterligare pixlar.

864
00:40:48,270 --> 00:40:50,990
Och faktiskt, det är hur vi
kan komprimera den tyska flaggan.

865
00:40:50,990 --> 00:40:51,490
Och

866
00:40:51,490 --> 00:40:53,470
Nu vad om fransk flagg?

867
00:40:53,470 --> 00:40:58,930
Och lite något slags
mental träning, vilken flagga

868
00:40:58,930 --> 00:41:01,040
kan komprimeras mer på disk?

869
00:41:01,040 --> 00:41:05,720
Den tyska flaggan eller franska
flagga, om vi tar detta synsätt?

870
00:41:05,720 --> 00:41:08,490
Den tyska flaggan, eftersom det finns
mer övergripande redundans.

871
00:41:08,490 --> 00:41:12,190
Och genom design, många grafiska filen
format gör verkligen fungerar som sveplinjer

872
00:41:12,190 --> 00:41:12,830
horisontellt.

873
00:41:12,830 --> 00:41:14,674
De kunde arbeta
vertikalt, precis mänskligheten

874
00:41:14,674 --> 00:41:17,090
beslutade år sedan att vi ska
i allmänhet tänka på saker rad

875
00:41:17,090 --> 00:41:18,880
genom rad istället för kolumn för kolumn.

876
00:41:18,880 --> 00:41:20,820
Så ja om du var
att titta på filen

877
00:41:20,820 --> 00:41:24,670
storleken på en tysk flagga och en fransk
flagga, så länge som upplösningen är

878
00:41:24,670 --> 00:41:27,530
samma, samma bredd
och höjd, här

879
00:41:27,530 --> 00:41:31,580
här kommer att bli större, eftersom du
måste upprepa dig tre gånger.

880
00:41:31,580 --> 00:41:35,570
Du måste ange blått, upprepa
själv, vit, upprepa dig själv, rött,

881
00:41:35,570 --> 00:41:36,740
upprepa dig själv.

882
00:41:36,740 --> 00:41:39,000
Du kan inte bara gå alla
vägen till höger.

883
00:41:39,000 --> 00:41:41,200
Och som en sidoreplik, att göra
rensa kompression

884
00:41:41,200 --> 00:41:43,910
är överallt, om dessa
fyra bildrutor från en video-- du

885
00:41:43,910 --> 00:41:45,890
kanske kommer ihåg att en film
eller video är i allmänhet

886
00:41:45,890 --> 00:41:47,286
som 29 eller 30 bilder per sekund.

887
00:41:47,286 --> 00:41:50,410
Det är som en liten blädderbok där du
bara se bild, bild, bild, bild,

888
00:41:50,410 --> 00:41:54,410
image bara supersnabb så det ser ut
aktörerna på skärmen rör sig.

889
00:41:54,410 --> 00:41:57,130
Här är en humla på
toppen av en blombukett.

890
00:41:57,130 --> 00:41:59,790
Och även om det kan vara typ av
svårt att se vid första anblicken,

891
00:41:59,790 --> 00:42:04,020
det enda som rör sig i
den här filmen är biet.

892
00:42:04,020 --> 00:42:06,880
>> Vad är dum om att lagra
video okomprimerad?

893
00:42:06,880 --> 00:42:11,420
Det är typ av avfall för att lagra video
som fyra nästan identiska bilder som

894
00:42:11,420 --> 00:42:13,670
skiljer sig endast i den mån där biet är.

895
00:42:13,670 --> 00:42:16,280
Du kan kasta bort det mesta
av denna information

896
00:42:16,280 --> 00:42:20,190
och minns bara, till exempel,
den första ramen och den sista ramen,

897
00:42:20,190 --> 00:42:22,180
nyckelrutor Om du har
någonsin hört ordet,

898
00:42:22,180 --> 00:42:24,337
och bara lagra i
mitten där biet är.

899
00:42:24,337 --> 00:42:26,170
Och du behöver inte
lagra alla rosa,

900
00:42:26,170 --> 00:42:28,330
och det blå, och
gröna värden.

901
00:42:28,330 --> 00:42:31,200
Så detta är att bara säga att
komprimering är överallt.

902
00:42:31,200 --> 00:42:34,900
Det är en teknik som vi använder ofta
eller tar för givet dessa dagar.

903
00:42:34,900 --> 00:42:38,750
>> Men hur gör du komprimera text?

904
00:42:38,750 --> 00:42:40,450
Hur går du om att komprimera texten?

905
00:42:40,450 --> 00:42:45,410
Tja, vart och ett av tecknen i
ASCII är en bitgrupp, eller åtta bitar.

906
00:42:45,410 --> 00:42:47,360
Och det är ganska dum, eller hur?

907
00:42:47,360 --> 00:42:51,160
Eftersom du förmodligen typ A
och E och I och O och U mycket

908
00:42:51,160 --> 00:42:55,270
oftare än som W eller Q eller Z,
beroende på vilket språk

909
00:42:55,270 --> 00:42:56,610
du skriver verkligen.

910
00:42:56,610 --> 00:42:59,600
Och så varför använder vi
åtta bitar för varje bokstav,

911
00:42:59,600 --> 00:43:02,040
inklusive minst
populära bokstäver, eller hur?

912
00:43:02,040 --> 00:43:05,300
Varför inte använda färre bitar för
super populära bokstäver,

913
00:43:05,300 --> 00:43:07,760
som E, de saker du gissa
först i Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
och använda fler bitar för
mindre populära breven?

915
00:43:10,450 --> 00:43:10,950
Varför?

916
00:43:10,950 --> 00:43:13,130
Eftersom vi bara kommer att
använder dem mindre ofta.

917
00:43:13,130 --> 00:43:15,838
>> Tja, visar det sig att det har
kommit försök gjorts för att göra detta.

918
00:43:15,838 --> 00:43:18,630
Och om du minns från årskurs
skolan eller gymnasiet, morsekod.

919
00:43:18,630 --> 00:43:20,400
Morsekod har prickar
och streck som kan vara

920
00:43:20,400 --> 00:43:24,270
överförs utmed en tråd som
ljud eller signaler av någon form.

921
00:43:24,270 --> 00:43:25,930
Men morsekod är en super clean.

922
00:43:25,930 --> 00:43:29,010
Det är lite av en binär system
att du har prickar eller streck.

923
00:43:29,010 --> 00:43:30,977
Men om du ser, till exempel, två punkter.

924
00:43:30,977 --> 00:43:33,810
Eller om du tänker tillbaka till operatören
som går som pip, pip, pip,

925
00:43:33,810 --> 00:43:36,760
pip, slå en liten trigger
som sänder en signal,

926
00:43:36,760 --> 00:43:40,360
om du, mottagaren, får två
prickar, vilket budskap har du fått?

927
00:43:40,360 --> 00:43:43,490
Helt godtyckligt.

928
00:43:43,490 --> 00:43:44,450
>> Jag?

929
00:43:44,450 --> 00:43:45,060
Jag?

930
00:43:45,060 --> 00:43:47,500
Eller vad about-- eller jag?

931
00:43:47,500 --> 00:43:49,570
Kanske var det bara två E rätt?

932
00:43:49,570 --> 00:43:52,480
Så det finns detta problem
av decodability med Morse

933
00:43:52,480 --> 00:43:54,890
kod, varmed om inte den
person som skickar meddelandet du

934
00:43:54,890 --> 00:43:59,510
faktiskt paus så att du kan sortera av
se eller höra klyftorna mellan bokstäverna,

935
00:43:59,510 --> 00:44:02,990
det är inte tillräckligt att endast
skicka en ström av ettor och nollor,

936
00:44:02,990 --> 00:44:05,610
eller prickar och streck,
eftersom det finns tvetydighet.

937
00:44:05,610 --> 00:44:08,640
E är en enda prick, så om du
se två punkter eller höra två punkter,

938
00:44:08,640 --> 00:44:11,254
kanske är det två E: s eller kanske är det ett I.

939
00:44:11,254 --> 00:44:13,670
Så vi behöver ett system som är en
lite mer smart än så.

940
00:44:13,670 --> 00:44:16,851
Så en man vid namn Huffman år
sedan kom fram till just detta.

941
00:44:16,851 --> 00:44:18,600
Så vi ska bara
att ta en snabb blick

942
00:44:18,600 --> 00:44:20,114
hur träden är relevant för detta.

943
00:44:20,114 --> 00:44:22,530
Antag att detta är någon
dum meddelande som du vill skicka,

944
00:44:22,530 --> 00:44:26,342
sammansatt av bara A, B, C: s D: s och E: s,
men det finns en hel del redundans här.

945
00:44:26,342 --> 00:44:27,550
Det är inte tänkt att vara engelska.

946
00:44:27,550 --> 00:44:28,341
Det är inte krypterad.

947
00:44:28,341 --> 00:44:30,540
Det är bara en dum meddelande
med massor av upprepning.

948
00:44:30,540 --> 00:44:34,010
Så om du verkligen räkna ut alla
A: s, B: s, C: s, D's, och E-talet, här är

949
00:44:34,010 --> 00:44:34,890
frekvensen.

950
00:44:34,890 --> 00:44:37,800
20% av bokstäverna är
A: s, 45% av bokstäverna

951
00:44:37,800 --> 00:44:39,660
är E-talet, och tre andra frekvenser.

952
00:44:39,660 --> 00:44:41,960
Vi räknade upp det manuellt
och bara gjorde matten.

953
00:44:41,960 --> 00:44:44,579
>> Så visar det sig att
Huffman, för en tid sedan,

954
00:44:44,579 --> 00:44:46,620
insett att du vet
vad, om jag börjar byggnad

955
00:44:46,620 --> 00:44:51,172
ett träd eller skog av träd, om ni så vill,
enligt följande, kan jag göra följande.

956
00:44:51,172 --> 00:44:53,880
Jag kommer att ge en nod för varje
av de brev som jag bryr mig om

957
00:44:53,880 --> 00:44:55,530
och jag kommer att lagra
insidan av denna nod

958
00:44:55,530 --> 00:44:58,610
frekvenserna som ett flyttal
värde, eller så kan du använda det en N, också,

959
00:44:58,610 --> 00:45:00,210
men vi bara använda en flottör här.

960
00:45:00,210 --> 00:45:03,100
Och algoritmen som
han föreslog är att du

961
00:45:03,100 --> 00:45:07,210
ta denna skog av enda nod
träd, så super korta träd,

962
00:45:07,210 --> 00:45:11,920
och du börjar ansluta dem med
nya grupper, nya föräldrar, om du kommer.

963
00:45:11,920 --> 00:45:16,150
Och du gör det genom att välja
två minsta frekvenserna åt gången.

964
00:45:16,150 --> 00:45:18,110
Så jag tog 10% och 10%.

965
00:45:18,110 --> 00:45:19,090
Jag skapar en ny nod.

966
00:45:19,090 --> 00:45:20,910
Och jag kallar den nya noden 20%.

967
00:45:20,910 --> 00:45:22,750
>> Vilka två noder jag kombinera nästa?

968
00:45:22,750 --> 00:45:23,810
Det är lite tvetydigt.

969
00:45:23,810 --> 00:45:26,643
Så det finns vissa hörn fall till
överväga, men att hålla saker ganska,

970
00:45:26,643 --> 00:45:29,300
Jag kommer att välja 20% -
Jag ignorerar nu barnen.

971
00:45:29,300 --> 00:45:33,640
Jag kommer att välja 20% och
15% och rita två nya kanter.

972
00:45:33,640 --> 00:45:35,624
Och nu som två noder
jag logiskt kombinera?

973
00:45:35,624 --> 00:45:38,540
Ignorera alla barn, alla
barnbarn, titta bara på rötterna

974
00:45:38,540 --> 00:45:39,070
nu.

975
00:45:39,070 --> 00:45:42,220
Vilka två noder jag knyta ihop?

976
00:45:42,220 --> 00:45:44,530
Punkt två och 0,35.

977
00:45:44,530 --> 00:45:45,890
Så låt mig rita två nya kanter.

978
00:45:45,890 --> 00:45:47,570
Och då har jag bara fått en vänster.

979
00:45:47,570 --> 00:45:48,650
Så här är ett träd.

980
00:45:48,650 --> 00:45:51,160
Och det dragits medvetet
att titta slags söt,

981
00:45:51,160 --> 00:45:55,870
men märker att kanterna har
även märkts noll och ett.

982
00:45:55,870 --> 00:45:59,510
Så alla de vänsterkant är noll
godtyckligt, men konsekvent.

983
00:45:59,510 --> 00:46:01,170
Alla högra kanten är sådana.

984
00:46:01,170 --> 00:46:05,070
>> Och så vad Hoffman föreslagna,
Om du vill representera en B,

985
00:46:05,070 --> 00:46:10,080
snarare än representerar antal 66 som
en ASCII som är åtta hela bitar,

986
00:46:10,080 --> 00:46:13,360
vet du vad, bara butiken
mönstret noll, noll, noll,

987
00:46:13,360 --> 00:46:17,030
noll, eftersom det är den väg
från mitt träd, Mr. Huffman träd,

988
00:46:17,030 --> 00:46:18,600
till bladet från roten.

989
00:46:18,600 --> 00:46:20,970
Om du vill spara en
E, däremot, inte

990
00:46:20,970 --> 00:46:26,290
skicka åtta bitar som representerar ett E.
Istället skickar vilket mönster bitar?

991
00:46:26,290 --> 00:46:26,890
En.

992
00:46:26,890 --> 00:46:30,410
Och vad är trevligt om det här är
att E är den mest populära brev,

993
00:46:30,410 --> 00:46:32,340
och du använder
kortaste kod för det.

994
00:46:32,340 --> 00:46:34,090
Den näst mest populära
brev ser ut som det

995
00:46:34,090 --> 00:46:37,380
var A. Och så hur många bitar
gjorde han föreslår att använda för det?

996
00:46:37,380 --> 00:46:38,270
Noll, en.

997
00:46:38,270 --> 00:46:41,060
>> Och eftersom det är genomförs
som detta träd, för nu

998
00:46:41,060 --> 00:46:43,350
Låt mig fastställa att det finns
ingen tvetydighet som i Morse

999
00:46:43,350 --> 00:46:46,090
kod, eftersom alla
bokstäver du bryr dig om

1000
00:46:46,090 --> 00:46:48,780
är i slutet av dessa kanter.

1001
00:46:48,780 --> 00:46:50,580
Så det är bara en
applicering av ett träd.

1002
00:46:50,580 --> 00:46:52,538
Detta är-- och jag våg
min hand på hur du

1003
00:46:52,538 --> 00:46:55,570
kan genomföra detta som en C-struktur.

1004
00:46:55,570 --> 00:46:58,260
Vi behöver bara kombinera
en symbol, som en röding,

1005
00:46:58,260 --> 00:46:59,910
och frekvensen i vänster och höger.

1006
00:46:59,910 --> 00:47:02,510
Men låt oss titta på två
slutliga exempel som du kan

1007
00:47:02,510 --> 00:47:06,070
bli ganska bekant med efter
quiz noll problem set fem.

1008
00:47:06,070 --> 00:47:09,210
>> Så det finns datastrukturen
känd som en hashtabell.

1009
00:47:09,210 --> 00:47:12,247
Och en hashtabell är typ av
kyla genom att den har hinkar.

1010
00:47:12,247 --> 00:47:14,830
Och antar att det finns fyra hinkar
Här, bara fyra tomma utrymmen.

1011
00:47:14,830 --> 00:47:20,830
Här är en kortlek, och här är
klubb, spade, klubba, diamanter, klubba,

1012
00:47:20,830 --> 00:47:25,960
diamanter, klubba, diamanter,
clubs-- så detta är slumpmässigt.

1013
00:47:25,960 --> 00:47:30,330
Hearts, Hearts-- så jag är
bucketizing alla ingångarna här.

1014
00:47:30,330 --> 00:47:32,430
Och en hashtabell behöver
att titta på din input,

1015
00:47:32,430 --> 00:47:34,850
och sedan lägga den i en viss
Placera baserat på vad du ser.

1016
00:47:34,850 --> 00:47:35,600
Det är en algoritm.

1017
00:47:35,600 --> 00:47:37,980
Och jag använde en super
enkel visuell algoritm.

1018
00:47:37,980 --> 00:47:40,030
Den svåraste delen av som var
komma ihåg vad bilderna var.

1019
00:47:40,030 --> 00:47:41,590
Och sedan finns det fyra totalt saker.

1020
00:47:41,590 --> 00:47:45,440
>> Nu travar växte, vilket
är en avsiktlig konstruktion sak här.

1021
00:47:45,440 --> 00:47:46,540
Men vad kan jag göra?

1022
00:47:46,540 --> 00:47:49,080
Så faktiskt här vi har en
gäng gamla skolan examen böcker.

1023
00:47:49,080 --> 00:47:51,240
Antag att ett gäng
elevernas namn är här.

1024
00:47:51,240 --> 00:47:52,570
Här är en större hash-tabell.

1025
00:47:52,570 --> 00:47:54,867
I stället för fyra hinkar,
Jag har, låt oss säga 26.

1026
00:47:54,867 --> 00:47:57,950
Och vi ville inte gå låna 26
saker från utsidan [? Annenberg?], Så

1027
00:47:57,950 --> 00:48:00,289
Här är fem som representerar
A till Z. Och om jag

1028
00:48:00,289 --> 00:48:03,580
se en student vars namn börjar med A,
Jag kommer att sätta sin frågesport där.

1029
00:48:03,580 --> 00:48:08,850
Om någon börjar med C, där borta,
A-- faktiskt, inte vill göra det.

1030
00:48:08,850 --> 00:48:10,060
B går hit.

1031
00:48:10,060 --> 00:48:13,390
Så jag har A och B och C. And
nu här är en annan student.

1032
00:48:13,390 --> 00:48:16,212
Men om detta hash-tabell är
genomförs med en array,

1033
00:48:16,212 --> 00:48:17,920
Jag slags skruvad
vid denna tidpunkt, eller hur?

1034
00:48:17,920 --> 00:48:19,510
Jag slags behöver för att sätta den här någonstans.

1035
00:48:19,510 --> 00:48:24,380
>> Så ett sätt jag kan lösa detta är, allt
höger, är en upptagen, B är upptagen, C är upptagen.

1036
00:48:24,380 --> 00:48:28,880
Jag kommer att sätta honom i D. Så vid
först, jag har random omedelbar tillgång

1037
00:48:28,880 --> 00:48:31,064
till var och en av skopor till eleverna.

1038
00:48:31,064 --> 00:48:33,230
Men nu är det typ av decentraliserade
till något linjär,

1039
00:48:33,230 --> 00:48:36,750
för om jag vill söka efter någon
vars namn börjar med A, kolla jag här.

1040
00:48:36,750 --> 00:48:38,854
Men om detta inte är en
elev jag letar efter,

1041
00:48:38,854 --> 00:48:41,520
Jag slags måste börja kontrollera
hinkar, eftersom vad jag gjorde

1042
00:48:41,520 --> 00:48:44,530
var typ av linjärt
sond datastrukturen.

1043
00:48:44,530 --> 00:48:47,710
En dum sätt att säga bara titta
för första tillgängliga öppningen,

1044
00:48:47,710 --> 00:48:51,850
och satte som en plan B, så att säga,
eller en plan D i detta fall värdet

1045
00:48:51,850 --> 00:48:53,340
på den platsen i stället.

1046
00:48:53,340 --> 00:48:56,470
Detta är bara så att om du har
fick 26 platser och inga studenter

1047
00:48:56,470 --> 00:49:00,600
med namnet Q eller Z, eller något liknande
att åtminstone du använder utrymmet.

1048
00:49:00,600 --> 00:49:03,140
>> Men vi har redan sett mer
smarta lösningar här, eller hur?

1049
00:49:03,140 --> 00:49:04,870
Vad skulle du göra istället
Om du har en kollision?

1050
00:49:04,870 --> 00:49:06,670
Om två personer har
namnet A, vad skulle

1051
00:49:06,670 --> 00:49:09,160
har varit ett smartare eller mer
intuitiv lösning än bara

1052
00:49:09,160 --> 00:49:12,840
sätta A där D är tänkt att vara?

1053
00:49:12,840 --> 00:49:14,810
Varför jag inte bara gå
utanför [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
som malloc, en annan nod, uttryckte det
här, och sedan lägga att en student här.

1055
00:49:19,960 --> 00:49:22,120
Så att jag har väsentligen
någon form av en matris,

1056
00:49:22,120 --> 00:49:25,590
eller kanske mer elegant som vi är
börjar se en länkad lista.

1057
00:49:25,590 --> 00:49:29,520
>> Och så en hashtabell är en struktur
som kan se ut precis som detta,

1058
00:49:29,520 --> 00:49:33,900
men mer skickligt, du något som kallas
separat kedja, varvid en hashtabell

1059
00:49:33,900 --> 00:49:38,340
helt enkelt är en array, vart och ett av
vars element är inte ett nummer,

1060
00:49:38,340 --> 00:49:40,470
själv är en länkad lista.

1061
00:49:40,470 --> 00:49:45,080
Så att du får supersnabb tillgång
besluta om att hash ditt värde för.

1062
00:49:45,080 --> 00:49:48,059
Ungefär som med kort exempel
Jag gjorde super snabba beslut.

1063
00:49:48,059 --> 00:49:49,600
Hjärtan går här, diamanter går här.

1064
00:49:49,600 --> 00:49:52,180
Samma här, går A här,
D går här, B går här.

1065
00:49:52,180 --> 00:49:55,740
Så supersnabb uppslagningar, och om
du råkar stöta på ett fall

1066
00:49:55,740 --> 00:49:59,429
där du har fått kollisioner, två
personer med samma namn, ja då

1067
00:49:59,429 --> 00:50:00,970
du bara börja länka ihop dem.

1068
00:50:00,970 --> 00:50:03,900
Och kanske du hålla dem sorterade
alfabetiskt, kanske du inte.

1069
00:50:03,900 --> 00:50:05,900
Men åtminstone nu har vi dynamik.

1070
00:50:05,900 --> 00:50:10,250
Så å ena sidan har vi supersnabb
konstant tid, och typ av linjär tid

1071
00:50:10,250 --> 00:50:14,110
inblandade om dessa länkade listor
börjar bli lite lång.

1072
00:50:14,110 --> 00:50:16,880
>> Så denna typ av en dum,
geeky skämt år sedan.

1073
00:50:16,880 --> 00:50:19,590
Vid CS50 hacka-a-thon,
när eleverna checkar in,

1074
00:50:19,590 --> 00:50:22,040
vissa TF eller CA varje år
tycker att det är roligt att sätta upp

1075
00:50:22,040 --> 00:50:27,772
ett tecken som detta, där det bara
innebär att om ditt namn börjar med en A,

1076
00:50:27,772 --> 00:50:28,870
gå denna väg.

1077
00:50:28,870 --> 00:50:31,110
Om ditt namn börjar
med ett B, gå this-- OK,

1078
00:50:31,110 --> 00:50:33,290
det är roligt kanske senare under terminen.

1079
00:50:33,290 --> 00:50:36,420
Men det finns en annan
sätt att göra detta också.

1080
00:50:36,420 --> 00:50:37,410
Kom tillbaka till det.

1081
00:50:37,410 --> 00:50:38,600
>> Så det finns denna struktur.

1082
00:50:38,600 --> 00:50:40,420
Och detta är vår sista
struktur för idag,

1083
00:50:40,420 --> 00:50:42,400
vilket är något som kallas en trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, som av någon anledning är kort
för hämtning, men det heter trie.

1085
00:50:47,140 --> 00:50:51,389
Så en trie är en annan intressant
blandning av en hel del av dessa idéer.

1086
00:50:51,389 --> 00:50:52,930
Det är ett träd, som vi har sett förut.

1087
00:50:52,930 --> 00:50:54,180
Det är inte ett binärt sökträd.

1088
00:50:54,180 --> 00:50:58,410
Det är ett träd med valfritt antal barn,
men vart och ett av barnen i en trie

1089
00:50:58,410 --> 00:51:00,090
är en array.

1090
00:51:00,090 --> 00:51:04,790
En array av storlek, säger, 26 eller kanske 27
Om du vill stödja bindestreck namn

1091
00:51:04,790 --> 00:51:06,790
eller apostrofer i människors namn.

1092
00:51:06,790 --> 00:51:08,280
>> Och så detta är en datastruktur.

1093
00:51:08,280 --> 00:51:10,290
Och om man tittar uppifrån
till botten, precis som om du

1094
00:51:10,290 --> 00:51:13,710
titta på toppnoden där, M, är
pekar på vänstra sak där,

1095
00:51:13,710 --> 00:51:17,665
vilken sedan A, X, W, E, L, L. Detta är
bara en datastruktur som godtyckligt

1096
00:51:17,665 --> 00:51:19,120
lagrar människors namn.

1097
00:51:19,120 --> 00:51:25,720
Och Maxwell lagras genom att bara följa
en väg av matris till matris till matris.

1098
00:51:25,720 --> 00:51:30,050
Men vad som är fantastiskt om en trie är
att, medan en länkad lista och även

1099
00:51:30,050 --> 00:51:34,520
en array, är det bästa som vi någonsin har fått
linjär tid eller logaritmisk tid på att leta

1100
00:51:34,520 --> 00:51:35,600
upp någon.

1101
00:51:35,600 --> 00:51:40,530
I denna datastruktur av en trie, om
min datastruktur har ett namn i det

1102
00:51:40,530 --> 00:51:43,720
och jag letar efter Maxwell, jag
kommer att hitta honom ganska snabbt.

1103
00:51:43,720 --> 00:51:47,910
Jag ser bara för M-A-X-W-E-L-L. Om
denna datastruktur, däremot,

1104
00:51:47,910 --> 00:51:51,830
Om N är en miljon, om det finns en
miljoner namn i denna datastruktur,

1105
00:51:51,830 --> 00:51:57,100
Maxwell fortfarande kommer att vara
upptäckbar efter bara M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
steg.

1107
00:51:58,090 --> 00:52:01,276
Och David-- D-A-V-l-D steg.

1108
00:52:01,276 --> 00:52:03,400
Med andra ord, genom att bygga
en datastruktur som är

1109
00:52:03,400 --> 00:52:07,240
fick alla dessa matriser, vilka alla
själva stöder random access,

1110
00:52:07,240 --> 00:52:11,090
Jag kan börja leta upp människors
namn med en tid som är

1111
00:52:11,090 --> 00:52:14,340
proportionell mot inte antalet
saker i datastrukturen,

1112
00:52:14,340 --> 00:52:16,330
som en miljon befintliga namn.

1113
00:52:16,330 --> 00:52:20,135
Hur lång tid det tar mig att hitta
M-A-X-W-E-L-L i denna datastruktur är

1114
00:52:20,135 --> 00:52:22,260
proportionell inte till den
storleken av den datastruktur,

1115
00:52:22,260 --> 00:52:25,930
men till längden av namnet.

1116
00:52:25,930 --> 00:52:28,440
Och realistiskt
namn vi letar upp

1117
00:52:28,440 --> 00:52:29,970
kommer aldrig att vara galen lång.

1118
00:52:29,970 --> 00:52:32,600
Kanske någon har en 10 tecken
namn, 20 teckennamn.

1119
00:52:32,600 --> 00:52:33,900
Det är verkligen begränsad, eller hur?

1120
00:52:33,900 --> 00:52:37,110
Det finns en människa på jorden som
har den längsta möjliga namn,

1121
00:52:37,110 --> 00:52:39,920
men det namnet är en konstant
värde längd, eller hur?

1122
00:52:39,920 --> 00:52:41,980
Det varierar inte på något sätt.

1123
00:52:41,980 --> 00:52:45,090
Så på detta sätt, vi har
uppnått en datastruktur

1124
00:52:45,090 --> 00:52:47,800
som är konstant tidsuppslags.

1125
00:52:47,800 --> 00:52:50,670
Det tar ett antal steg
beroende på längden av den ingående,

1126
00:52:50,670 --> 00:52:54,250
men inte antalet namn
i datastrukturen.

1127
00:52:54,250 --> 00:52:58,700
Så om vi fördubbla antalet namn
nästa år från en miljard till två miljarder kronor,

1128
00:52:58,700 --> 00:53:03,720
slutsats Maxwell kommer att ta
exakt samma antal sju steg

1129
00:53:03,720 --> 00:53:04,650
att hitta honom.

1130
00:53:04,650 --> 00:53:08,810
Och så vi tycks ha uppnått
vår heliga graal gångtid.

1131
00:53:08,810 --> 00:53:10,860
>> Så ett par snabba meddelanden.

1132
00:53:10,860 --> 00:53:11,850
Quiz noll kommer upp.

1133
00:53:11,850 --> 00:53:14,600
Mer om det på kursens hemsida
under de kommande dagarna.

1134
00:53:14,600 --> 00:53:17,120
Måndagens lecture-- det är en helgdag
här på Harvard på måndag.

1135
00:53:17,120 --> 00:53:18,850
Det är inte i New Haven,
så vi tar klassen

1136
00:53:18,850 --> 00:53:20,310
New Haven för föreläsning på måndag.

1137
00:53:20,310 --> 00:53:22,550
Allt kommer att filmas
och streamas live som vanligt,

1138
00:53:22,550 --> 00:53:24,900
men låt oss avsluta idag
med en 30 sekunders klipp

1139
00:53:24,900 --> 00:53:26,910
kallade "djupa tankar"
av Daven Farnham, som

1140
00:53:26,910 --> 00:53:30,850
inspirerades förra året med lördag
Night Live: s "djupa tankar"

1141
00:53:30,850 --> 00:53:35,700
av Jack Handy, som
bör nu vara meningsfullt.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Och nu, "Djup
Tankar "av Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hashtabell.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> TALARE 1: Okej, det är det för nu.

1147
00:53:47,660 --> 00:53:48,805
Vi ses nästa vecka.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: För att se det i handling.

1150
00:53:56,680 --> 00:53:58,304
Så låt oss ta en titt på det just nu.

1151
00:53:58,304 --> 00:53:59,890
Så här har vi en osorterad array.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, kan du gå vidare och starta om
detta för bara en sekund, snälla.

1153
00:54:04,860 --> 00:54:08,562
Okej, är kamerorna rullar, så
åtgärd när du är klar, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Okej, så vad vi
har här är en osorterad array.

1155
00:54:11,020 --> 00:54:13,960
Och jag har färgat alla element
rött för att indikera att det är i själva verket,

1156
00:54:13,960 --> 00:54:14,460
osorterat.

1157
00:54:14,460 --> 00:54:17,960
Så minns att det första vi gör
är vi sorterar vänstra halvan av gruppen.

1158
00:54:17,960 --> 00:54:20,630
Då kan vi sortera rätt
halv av arrayen.

1159
00:54:20,630 --> 00:54:22,830
Och ya-da, ya-da, ya-da,
Vi sammanfoga dem tillsammans.

1160
00:54:22,830 --> 00:54:24,520
Och vi har en helt sorterad array.

1161
00:54:24,520 --> 00:54:25,360
Så det är hur merge sort fungerar.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, whoa, whoa,
cut, cut, cut, cut.

1163
00:54:27,109 --> 00:54:30,130
Doug kan du inte bara ya-da, ya-da,
ya-da, din väg genom sammanslagning slag.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Jag gjorde bara.

1165
00:54:31,970 --> 00:54:32,832
Det är bra.

1166
00:54:32,832 --> 00:54:33,540
Vi är bra att gå.

1167
00:54:33,540 --> 00:54:34,760
Låt oss bara hålla rullande.

1168
00:54:34,760 --> 00:54:35,380
Så hur som helst,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Du måste förklara
det mera fullständigt än så.

1170
00:54:37,800 --> 00:54:39,999
Det är bara inte tillräckligt.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, gör vi inte
behöver gå tillbaka till en.

1172
00:54:41,790 --> 00:54:42,350
Det är bra.

1173
00:54:42,350 --> 00:54:45,690
Så hur som helst, om vi fortsätter med merge--
Ian, vi är mitt i inspelningen.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Jag vet.

1175
00:54:46,612 --> 00:54:49,320
Och vi kan inte bara ya-da, ya-da,
ya-da, genom hela processen.

1176
00:54:49,320 --> 00:54:52,200
Du måste förklara hur
två sidor slås ihop.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Men vi har redan
förklarade hur de två sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Du har just visat
dem en sammanfogning matris.

1179
00:54:55,321 --> 00:54:56,486
DOUG: De vet processen.

1180
00:54:56,486 --> 00:54:57,172
De är bra.

1181
00:54:57,172 --> 00:54:58,380
Vi har gått över den tio gånger.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Du hoppade precis rätt över det.

1183
00:55:00,330 --> 00:55:03,360
Vi kommer tillbaka till en,
kan du inte ya-da, ya-da över den.

1184
00:55:03,360 --> 00:55:05,480
Okej, tillbaka till en.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Jag måste gå tillbaka
igenom alla bilderna?

1186
00:55:07,833 --> 00:55:08,332
Herregud.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Det är som sjätte gången, Ian.

1189
00:55:13,004 --> 00:55:13,940
Det är bra.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Okej.

1191
00:55:15,200 --> 00:55:16,590
Är du redo?

1192
00:55:16,590 --> 00:55:17,400
Bra.

1193
00:55:17,400 --> 00:55:18,950
Action.