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

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Ok, så dette er
CS50 Dette er slutten av uken fem.

3
00:00:15,860 --> 00:00:19,220
Og huske at sist gang vi
begynte å se på mer avansert data

4
00:00:19,220 --> 00:00:22,310
strukturer som begynte å løse
problemer, som begynte å introdusere

5
00:00:22,310 --> 00:00:25,640
nye problemer, men nøkkelen til dette
var slags threading at vi

6
00:00:25,640 --> 00:00:27,940
begynte å gjøre fra node til node.

7
00:00:27,940 --> 00:00:30,085
Så dette er selvfølgelig
en enkeltvis lenket liste.

8
00:00:30,085 --> 00:00:31,960
Og ved enkeltvis knyttet sammen,
Jeg mener det er bare ett

9
00:00:31,960 --> 00:00:33,380
tråden mellom hver av disse nodene.

10
00:00:33,380 --> 00:00:35,890
Det viser seg at du kan gjøre mer avansert
ting som dobbelt lenkede lister

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

12
00:00:38,470 --> 00:00:40,320
kan hjelpe med visse effektivitet.

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

14
00:00:42,000 --> 00:00:43,500
Hva problem gjorde dette løse?

15
00:00:43,500 --> 00:00:46,620
Hvorfor gjorde vi bryr oss på mandag?

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

17
00:00:49,820 --> 00:00:50,630
Hva gjør det?

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

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

20
00:00:53,740 --> 00:00:54,710
Godt gjort dere begge.

21
00:00:54,710 --> 00:00:57,560
Så du kan dynamisk endre størrelsen på dette
datastruktur, mens en matrise,

22
00:00:57,560 --> 00:01:00,760
tilbakekallingen, må du vite
priori hvor mye plass du vil

23
00:01:00,760 --> 00:01:03,870
og hvis du trenger litt mer
plass, er du på en måte ute av lykken.

24
00:01:03,870 --> 00:01:05,560
Du må opprette en helt ny rekke.

25
00:01:05,560 --> 00:01:07,893
Du må flytte alle dine
data fra den ene til den annen,

26
00:01:07,893 --> 00:01:10,600
slutt frigjøre gamle matrise
hvis du kan, og deretter fortsette.

27
00:01:10,600 --> 00:01:13,891
Som bare føles veldig kostbart og svært
ineffektiv, og faktisk det kan være.

28
00:01:13,891 --> 00:01:14,890
Men dette er ikke alt bra.

29
00:01:14,890 --> 00:01:18,180
Vi betaler en pris, det som var en
av de mer åpen prisene vi

30
00:01:18,180 --> 00:01:20,550
betale ved hjelp av en lenket liste?

31
00:01:20,550 --> 00:01:22,825
>> PUBLIKUM: Vi må bruke
dobbel plass for hver enkelt.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Ja, så vi trenger
minst dobbelt så mye plass.

33
00:01:25,200 --> 00:01:27,700
Faktisk, jeg innså at dette bildets
enda litt misvisende,

34
00:01:27,700 --> 00:01:32,200
fordi på CS50 IDE i mange moderne
datamaskiner, en peker eller en adresse

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

36
00:01:33,700 --> 00:01:36,090
Det er veldig ofte disse
dager åtte bytes, som

37
00:01:36,090 --> 00:01:38,530
betyr den nederste
rektangler der i virkeligheten

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

39
00:01:40,900 --> 00:01:44,409
noe som betyr at du bruker tre ganger så
mye plass som vi kan ha noe annet.

40
00:01:44,409 --> 00:01:46,700
Nå på samme tid, er vi
fremdeles snakker bytes, ikke sant?

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

42
00:01:49,140 --> 00:01:51,000
med mindre disse data strukturer bli stor.

43
00:01:51,000 --> 00:01:54,510
>> Og så i dag skal vi begynne å vurdere
hvordan vi kan utforske data

44
00:01:54,510 --> 00:01:57,310
mer effektivt hvis du er i
Faktisk data blir større.

45
00:01:57,310 --> 00:02:00,360
Men la oss prøve å canonicalize
operasjonene første

46
00:02:00,360 --> 00:02:02,460
som du kan gjøre på disse
typer datastrukturer.

47
00:02:02,460 --> 00:02:04,790
Så noe sånt som en koblet
liste støtter generelt

48
00:02:04,790 --> 00:02:07,514
operasjoner liker slette,
sette inn, og søk.

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

50
00:02:08,639 --> 00:02:11,222
Det betyr bare at vanligvis,
hvis folk bruker lenket liste,

51
00:02:11,222 --> 00:02:14,287
de eller noen andre har implementert
funksjoner som å slette, sette inn,

52
00:02:14,287 --> 00:02:16,120
og søk, slik at du kan
faktisk gjøre noe

53
00:02:16,120 --> 00:02:18,030
nyttig med datastrukturen.

54
00:02:18,030 --> 00:02:20,760
Så la oss ta en rask titt
på hvordan vi kan implementere

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

56
00:02:24,530 --> 00:02:27,885
>> Så dette er bare noen C-kode,
ikke engang et komplett program

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

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

59
00:02:32,300 --> 00:02:33,790
Men merker jeg har bare
med en kommentar sa:

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

61
00:02:36,130 --> 00:02:38,410
Og la oss bare se på
hva de saftige delene er.

62
00:02:38,410 --> 00:02:40,790
Så på linje tre,
minne om at dette er nå

63
00:02:40,790 --> 00:02:45,960
Vi foreslo å erklære en node siste
tid, en av de rektangulære objekter.

64
00:02:45,960 --> 00:02:48,790
Den har en int som vi kaller N,
men vi kan kalle det noe,

65
00:02:48,790 --> 00:02:51,920
og deretter en struct node stjerne kalt neste.

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

67
00:02:55,520 --> 00:02:57,930
Hva er det du gjør for oss?

68
00:02:57,930 --> 00:03:01,044
Fordi det ser absolutt mer
kryptisk enn vår vanlige variabler.

69
00:03:01,044 --> 00:03:02,740
>> PUBLIKUM: Det gjør det flytter over en.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Det gjør det flytter over en.

71
00:03:04,650 --> 00:03:08,580
Og for å være mer presis,
det vil lagre adressen

72
00:03:08,580 --> 00:03:11,582
av noden som er ment å være
semantisk ved siden av det, ikke sant?

73
00:03:11,582 --> 00:03:13,540
Så det kommer ikke til å
nødvendigvis bevege seg noe.

74
00:03:13,540 --> 00:03:15,290
Det er bare kommer til
lagrer en verdi, som er

75
00:03:15,290 --> 00:03:17,170
kommer til å være adressen
av en annen node,

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

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

78
00:03:22,370 --> 00:03:26,390
OK, så nå hvis du antar at vi har
dette N tilgjengelig for oss, og la oss

79
00:03:26,390 --> 00:03:29,490
anta at noen andre har
satt inn en hel haug av heltall

80
00:03:29,490 --> 00:03:30,400
inn i en lenket liste.

81
00:03:30,400 --> 00:03:35,640
Og det lenket liste er
peker på et tidspunkt

82
00:03:35,640 --> 00:03:39,040
en variabel kalt liste som er
gått her som en parameter,

83
00:03:39,040 --> 00:03:43,120
hvordan går jeg om linje
14 gjennomføre søk?

84
00:03:43,120 --> 00:03:45,990
Med andre ord, hvis jeg implementere
funksjon hvis formål i livet

85
00:03:45,990 --> 00:03:48,889
er å ta en int, og deretter
begynnelsen av en lenket liste,

86
00:03:48,889 --> 00:03:50,430
som er en peker til lenket liste.

87
00:03:50,430 --> 00:03:52,992
Som første, som jeg tror David
var vår frivillig på mandag,

88
00:03:52,992 --> 00:03:54,700
han peker på
hele lenket liste,

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

90
00:03:57,820 --> 00:03:59,990
Hvordan går vi om å gå gjennom denne listen?

91
00:03:59,990 --> 00:04:04,640
Vel, det viser seg at selv om
pekere er relativt nytt nå til oss,

92
00:04:04,640 --> 00:04:07,010
vi kan gjøre dette relativt
oversiktlig.

93
00:04:07,010 --> 00:04:09,500
>> Jeg kommer til å gå videre og
erklære en midlertidig variabel som

94
00:04:09,500 --> 00:04:12,364
etter konvensjonen er bare kommer
å bli kalt pekeren, eller PTR,

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

96
00:04:14,030 --> 00:04:16,470
Og jeg kommer til å initial
den til starten av listen.

97
00:04:16,470 --> 00:04:20,050
Så du kan slags tenke på dette
som meg læreren den andre dagen,

98
00:04:20,050 --> 00:04:23,580
slags peker på noen
blant våre mennesker som frivillige.

99
00:04:23,580 --> 00:04:26,470
Så jeg er en midlertidig variabel som er
bare å peke på det samme

100
00:04:26,470 --> 00:04:31,390
at vår tilfeldigvis heter
frivillig David ble også peke ut.

101
00:04:31,390 --> 00:04:35,440
Nå mens pekeren er
ikke null, fordi tilbakekalling

102
00:04:35,440 --> 00:04:40,350
at null er noen spesielle sentinel verdi
den avgrenser enden av listen,

103
00:04:40,350 --> 00:04:44,280
så mens jeg ikke peker på
bakken som vår siste frivillig

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

105
00:04:47,190 --> 00:04:51,820
Hvis pointer-- og nå jeg slags ønsker
å gjøre det vi gjorde med studenten

106
00:04:51,820 --> 00:04:57,410
structure-- hvis pekeren dot neste
equals-- heller, hvis pekeren dot N er lik

107
00:04:57,410 --> 00:05:02,290
lik den variable N, jo
argument som er blitt vedtatt i,

108
00:05:02,290 --> 00:05:05,370
så jeg ønsker å gå videre
og si return true.

109
00:05:05,370 --> 00:05:11,020
Jeg har funnet at antallet N innside
en av nodene i min lenket liste.

110
00:05:11,020 --> 00:05:13,500
Men prikken ikke lenger
arbeider i denne sammenheng

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

112
00:05:17,260 --> 00:05:20,632
vi faktisk kan prakt
bruke endelig et stykke syntaks

113
00:05:20,632 --> 00:05:22,590
den slags merker
intuitiv følelse og faktisk

114
00:05:22,590 --> 00:05:27,870
bruke en pil her, som betyr å gå fra
at adressen til det heltall der i.

115
00:05:27,870 --> 00:05:30,160
Så det er svært like i
ånd til dot operatør,

116
00:05:30,160 --> 00:05:33,860
men fordi pekeren er ikke en peker
og ikke en faktisk struct seg selv,

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

118
00:05:35,380 --> 00:05:40,620
>> Så hvis den nåværende node at jeg,
midlertidig variabel, er å peke på

119
00:05:40,620 --> 00:05:43,060
er ikke N, hva jeg ønsker å gjøre?

120
00:05:43,060 --> 00:05:45,910
Vel, med mine frivillige
som vi hadde her om dagen,

121
00:05:45,910 --> 00:05:49,710
Hvis min første mennesket er ikke den jeg
ønsker, og kanskje andre menneske er ikke

122
00:05:49,710 --> 00:05:52,660
den jeg vil ha, og den tredje, jeg
trenger for å holde fysisk bevegelse.

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

124
00:05:54,690 --> 00:05:57,470
Da vi hadde en rekke, du
bare gjorde som jeg pluss pluss.

125
00:05:57,470 --> 00:06:03,660
Men i dette tilfellet er det tilstrekkelig å
gjøre pekeren, får, peker, neste.

126
00:06:03,660 --> 00:06:07,580
Med andre ord, det neste feltet
er som alle de venstre hånd

127
00:06:07,580 --> 00:06:10,880
at våre frivillige på mandag
ble brukt for å peke mot en annen node.

128
00:06:10,880 --> 00:06:12,890
De som var deres nærmeste naboer.

129
00:06:12,890 --> 00:06:17,060
>> Så hvis jeg ønsker å gå gjennom denne listen,
Jeg kan ikke bare gjøre jeg pluss pluss lenger,

130
00:06:17,060 --> 00:06:20,120
Jeg i stedet har å si
Jeg, peker, kommer

131
00:06:20,120 --> 00:06:24,650
til lik uansett neste feltet er,
det neste feltet, er det neste felt,

132
00:06:24,650 --> 00:06:28,350
etter alle disse venstre hånd
som vi hadde på scenen peker

133
00:06:28,350 --> 00:06:30,000
til noen påfølgende verdier.

134
00:06:30,000 --> 00:06:32,590
Og hvis jeg får gjennom
at hele iterasjon,

135
00:06:32,590 --> 00:06:39,330
og til slutt, jeg treffer null ikke å ha
funnet N ennå, jeg bare returnere false.

136
00:06:39,330 --> 00:06:44,100
Så igjen, alt det vi gjør her,
som per i bildet en stund siden,

137
00:06:44,100 --> 00:06:47,840
starter ved å peke på
begynnelsen av listen formodentlig.

138
00:06:47,840 --> 00:06:50,970
Og da jeg sjekke, er verdien
Jeg leter etter lik til ni?

139
00:06:50,970 --> 00:06:52,650
Hvis så, jeg kommer tilbake sant og jeg er ferdig.

140
00:06:52,650 --> 00:06:56,450
Hvis ikke, kan jeg oppdatere min hånd,
AKA pekeren, å peke

141
00:06:56,450 --> 00:06:59,540
ved neste pilen befinner seg, og
så den neste pilen befinner seg,

142
00:06:59,540 --> 00:07:00,480
og den neste.

143
00:07:00,480 --> 00:07:03,770
Jeg er ganske enkelt å gå gjennom denne matrisen.

144
00:07:03,770 --> 00:07:06,010
>> Så igjen, hvem bryr seg?

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

146
00:07:07,861 --> 00:07:10,360
Vel, husker at vi innførte
oppfatningen av en stabel, som

147
00:07:10,360 --> 00:07:15,400
er en abstrakt datatype i den utstrekning det er
ikke en C ting, det er ikke en CS50 ting,

148
00:07:15,400 --> 00:07:19,430
det er en abstrakt idé, denne ideen om
stable ting oppå hverandre

149
00:07:19,430 --> 00:07:21,820
som kan implementeres i
bunter av forskjellige måter.

150
00:07:21,820 --> 00:07:25,600
Og en måte vi foreslo var med
en matrise, eller med en lenket liste.

151
00:07:25,600 --> 00:07:29,570
Og det viser seg at kanonisk, en
stabelen støtter i det minste to operasjoner.

152
00:07:29,570 --> 00:07:32,320
Og buzz ord er push, til
skyve noe på stakken,

153
00:07:32,320 --> 00:07:34,770
som et nytt brett i
spisesal, eller pop,

154
00:07:34,770 --> 00:07:39,000
noe som betyr at for å fjerne den øverste
brett fra stabelen i spise

155
00:07:39,000 --> 00:07:41,500
hall, og så kanskje noen
andre operasjoner også.

156
00:07:41,500 --> 00:07:45,770
Så hvordan kan vi definere strukturen
at vi nå kaller en bunke?

157
00:07:45,770 --> 00:07:50,020
>> Vel, vi har alle de nødvendige
syntaks til rådighet i C. sier jeg,

158
00:07:50,020 --> 00:07:53,830
gi meg en type definisjon av
en struct innsiden av en stabel,

159
00:07:53,830 --> 00:07:58,030
Jeg kommer til å si er en matrise, av en
hel haug med tall og deretter størrelse.

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

161
00:08:00,930 --> 00:08:03,830
la meg gå og bare slags
tegne hva denne sier.

162
00:08:03,830 --> 00:08:06,317
Så dette er å si, gi meg en
struktur som har fått en matrise,

163
00:08:06,317 --> 00:08:09,400
og jeg vet ikke hva kapasiteten er,
det er tydeligvis noen konstant at jeg har

164
00:08:09,400 --> 00:08:10,858
definert et annet sted, og det er fint.

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

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

167
00:08:16,700 --> 00:08:21,730
Dette elementet innsiden av mitt
strukturen vil bli kalt tall.

168
00:08:21,730 --> 00:08:24,020
Og da trenger jeg en
andre variable tilsynelatende

169
00:08:24,020 --> 00:08:27,814
kalt størrelsen som opprinnelig kommer jeg
å fastsette er initialisert til null.

170
00:08:27,814 --> 00:08:29,730
Hvis det ikke er noe i
stabelen, størrelse er null,

171
00:08:29,730 --> 00:08:31,420
og det er søppel verdier i tall.

172
00:08:31,420 --> 00:08:33,450
Jeg aner ikke hva som er der ennå.

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

174
00:08:36,059 --> 00:08:40,780
antar jeg kaller funksjonen push, og
Jeg sier presse 50, som nummer 50,

175
00:08:40,780 --> 00:08:44,090
hvor ville du foreslå
Jeg tegner det i denne array?

176
00:08:44,090 --> 00:08:47,124
Det finnes fem forskjellige mulige svar.

177
00:08:47,124 --> 00:08:48,790
Hvor ønsker du å presse nummer 50?

178
00:08:48,790 --> 00:08:51,899
Hvis målet her, igjen, ring
Funksjonen push, passere i en krangel

179
00:08:51,899 --> 00:08:52,940
50, hvor skal jeg plassere den?

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

181
00:08:55,680 --> 00:08:59,052
Fem possible-- 20% sjanse
for å gjette riktig.

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

183
00:08:59,896 --> 00:09:00,740
>> PUBLIKUM: Far høyre.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Far høyre.

185
00:09:01,990 --> 00:09:08,359
Det er nå en 25% sjanse
for å gjette riktig.

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

187
00:09:09,650 --> 00:09:12,770
Ved konvensjonen, vil jeg si med en matrise,
vi ville vanligvis starter på venstre,

188
00:09:12,770 --> 00:09:14,519
men vi kunne sikkert
starter på høyre.

189
00:09:14,519 --> 00:09:17,478
Så spoiler her ville være jeg er
sannsynligvis kommer til å trekke den til venstre,

190
00:09:17,478 --> 00:09:20,060
akkurat som i en vanlig matrise der
Jeg begynne å gå fra venstre til høyre.

191
00:09:20,060 --> 00:09:21,780
Men hvis du kan bla
aritmetisk, fine.

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

193
00:09:23,060 --> 00:09:24,880
OK, jeg trenger å gjøre en
mer endring skjønt.

194
00:09:24,880 --> 00:09:27,710
Nå som jeg har skjøvet noe
på stakken, hva blir det neste?

195
00:09:27,710 --> 00:09:29,400
>> Greit, jeg har for å øke størrelsen.

196
00:09:29,400 --> 00:09:32,600
Så la meg gå videre og bare
oppdatere denne, som var null.

197
00:09:32,600 --> 00:09:35,950
Og i stedet nå, jeg kommer
å sette i verdien en.

198
00:09:35,950 --> 00:09:39,460
Og nå antar jeg trykker en annen
nummeret på stakken, som 51.

199
00:09:39,460 --> 00:09:42,680
Vel, jeg må gjøre en mer
endring, som er opp til størrelsen to.

200
00:09:42,680 --> 00:09:46,100
Og så antar jeg trykker på en mer
nummeret på stakken som 61,

201
00:09:46,100 --> 00:09:52,530
Nå trenger jeg å oppdatere størrelse ett mer
tid, og få verdien 3 som størrelsen.

202
00:09:52,530 --> 00:09:54,690
Og nå antar jeg kaller pop.

203
00:09:54,690 --> 00:09:57,250
Nå pop, etter konvensjonen,
tar ikke et argument.

204
00:09:57,250 --> 00:10:00,430
Med en stabel, hele
punkt av skuffen metafor

205
00:10:00,430 --> 00:10:03,450
er at du ikke har skjønn
å gå får den skuffen, kan alt du gjør

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

207
00:10:06,330 --> 00:10:08,010
Det er det dette datastruktur gjør.

208
00:10:08,010 --> 00:10:12,250
>> Så ved at logikken hvis jeg
si pop, hva kommer av?

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

210
00:10:13,080 --> 00:10:15,402
Så hva er egentlig datamaskinen
kommer til å gjøre i minnet?

211
00:10:15,402 --> 00:10:16,610
Hva gjør koden min har å gjøre?

212
00:10:16,610 --> 00:10:20,330
Hva ville du foreslå
vi endrer på skjermen?

213
00:10:20,330 --> 00:10:23,410
Hva bør endres?

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

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

216
00:10:26,334 --> 00:10:27,500
Så jeg kan definitivt gjøre det.

217
00:10:27,500 --> 00:10:28,640
Og jeg kan bli kvitt 61.

218
00:10:28,640 --> 00:10:30,980
Og så hva andre
endring må skje?

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

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

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

222
00:10:36,690 --> 00:10:38,240
La oss bare gjøre en rask tilregnelighet sjekk.

223
00:10:38,240 --> 00:10:41,810
Hvordan fikk vi vite at vi
ønsket å kvitte seg med 61?

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

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

226
00:10:46,450 --> 00:10:48,470
>> Vent litt, jeg er
tenker tilbake til uke to

227
00:10:48,470 --> 00:10:51,660
da vi begynte å snakke om
matriser, der dette var stedet null,

228
00:10:51,660 --> 00:10:55,920
dette var stedet en, dette var stedet
to, er dette sted tre, fire,

229
00:10:55,920 --> 00:10:58,460
det ser ut som
forholdet mellom størrelse

230
00:10:58,460 --> 00:11:02,780
og elementet som jeg ønsker å fjerne
fra tabellen ser ut til å bare være det?

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

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

233
00:11:07,786 --> 00:11:09,160
Hvordan er datamaskinen kommer til å vite?

234
00:11:09,160 --> 00:11:11,701
Når koden din, der du sannsynligvis
ønsker å gjøre størrelse minus én,

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

236
00:11:14,950 --> 00:11:18,000
Og da kan vi faktisk oppdatere
størrelsen slik at størrelsen nå

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

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

239
00:11:24,520 --> 00:11:27,660
Du foreslo intuitivt
riktig jeg bør kvitte seg med 61.

240
00:11:27,660 --> 00:11:30,700
Men har ikke jeg slags
liksom blitt kvitt 61?

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

242
00:11:33,790 --> 00:11:37,680
Og tenker tilbake til PSET4, hvis du har lest
artikkelen om etterforskning, PDF

243
00:11:37,680 --> 00:11:40,780
at vi måtte dere lese, eller du
vil lese denne uken for PSET4.

244
00:11:40,780 --> 00:11:44,300
Husk at dette er faktisk viktig til
hele ideen om dataetterforskning.

245
00:11:44,300 --> 00:11:47,820
Hva en datamaskin generelt gjør er
det bare glemmer hvor noe er,

246
00:11:47,820 --> 00:11:51,300
men det går ikke inn og ut
prøver å klø den ut eller overstyring

247
00:11:51,300 --> 00:11:54,560
de biter med nuller og enere
eller annen tilfeldig mønster

248
00:11:54,560 --> 00:11:56,690
med mindre du selv gjør det bevisst.

249
00:11:56,690 --> 00:11:58,930
Så din intuisjon var
Greit, la oss bli kvitt 61.

250
00:11:58,930 --> 00:12:00,650
Men i virkeligheten, trenger vi ikke å bry seg.

251
00:12:00,650 --> 00:12:04,040
Vi trenger bare å glemme at
den er der ved å endre vår størrelse.

252
00:12:04,040 --> 00:12:05,662
>> Nå er det et problem med denne bunken.

253
00:12:05,662 --> 00:12:07,620
Hvis jeg holde skyve ting
på stakken, hva er

254
00:12:07,620 --> 00:12:11,167
åpenbart kommer til å skje
i bare noen øyeblikk tid?

255
00:12:11,167 --> 00:12:12,500
Vi kommer til å gå tom for plass.

256
00:12:12,500 --> 00:12:13,580
Og hva gjør vi?

257
00:12:13,580 --> 00:12:14,680
Vi er litt skrudd.

258
00:12:14,680 --> 00:12:19,000
Denne implementeringen ikke lar
oss endre størrelsen på array, fordi du bruker

259
00:12:19,000 --> 00:12:21,240
dette syntaks, hvis du
tenker tilbake til uke to,

260
00:12:21,240 --> 00:12:23,520
når du har erklært
på størrelse med en matrise,

261
00:12:23,520 --> 00:12:26,780
vi har ikke sett en mekanisme ennå hvor
endre størrelsen på matrisen.

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

263
00:12:29,020 --> 00:12:32,524
Hvis du sier gi meg fem-
Nths, kaller dem tall,

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

265
00:12:33,940 --> 00:12:38,790
Så vi gjør nå som av mandag, har
evnen til å uttrykke en løsning

266
00:12:38,790 --> 00:12:42,480
skjønt, vi trenger bare å finpusse
definisjonen av stacken

267
00:12:42,480 --> 00:12:46,840
å ikke være noen hardkodet array,
men bare for å lagre en adresse.

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

269
00:12:47,890 --> 00:12:51,690
Nå er vi bare nødt til å være komfortabel med
det faktum at når min programmet kjører,

270
00:12:51,690 --> 00:12:53,730
Jeg antagelig kommer til å
må spørre den menneskelige,

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

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

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

274
00:12:59,140 --> 00:13:02,470
bruke hvilken funksjon å gi
meg en blings av minne?

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

276
00:13:03,580 --> 00:13:06,710
Og jeg kan si hvilket som helst antall
byte Jeg vil tilbake for disse Nths.

277
00:13:06,710 --> 00:13:10,910
Og alt jeg har å lagre i tallene
variabel her inne i denne struct

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

279
00:13:13,480 --> 00:13:18,440
Hva som faktisk går inn i
Tallene i dette scenariet?

280
00:13:18,440 --> 00:13:21,300
Ja, en peker til den første
byte av den del av minnet,

281
00:13:21,300 --> 00:13:24,940
eller mer spesifikt, den adresse
av den første av disse bytes.

282
00:13:24,940 --> 00:13:27,300
Spiller ingen rolle om det er en
byte eller en milliard bytes,

283
00:13:27,300 --> 00:13:28,890
Jeg trenger bare å bry seg om det første.

284
00:13:28,890 --> 00:13:31,530
Fordi hva malloc garantier og
operativsystemet garantier,

285
00:13:31,530 --> 00:13:34,170
er at den del av minnet jeg
får, kommer det til å være sammenhengende.

286
00:13:34,170 --> 00:13:35,378
Det kommer ikke til å være hull.

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

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

289
00:13:40,450 --> 00:13:44,500
Og så lenge jeg husker hvor stort, hvor
mye jeg ba om, alt jeg trenger å vite

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

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

292
00:13:48,660 --> 00:13:51,280
Riktignok, det kommer til å ta oss
mer tid til å skrive dette opp,

293
00:13:51,280 --> 00:13:55,900
vi kunne nå omdisponere at minnet etter
bare lagre en annen adresse der

294
00:13:55,900 --> 00:13:59,060
hvis vi ønsker en større eller
en mindre del av minnet.

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

296
00:14:00,170 --> 00:14:01,360
Nå får vi dynamikk.

297
00:14:01,360 --> 00:14:03,350
Vi har fortsatt
contiguousness jeg hevde.

298
00:14:03,350 --> 00:14:05,881
Fordi malloc vil gi oss
en sammenhengende mengde minne.

299
00:14:05,881 --> 00:14:08,630
Men dette kommer til å være en smerte i
nakken for oss, programmerer,

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

301
00:14:09,770 --> 00:14:10,730
Det er bare mer arbeid.

302
00:14:10,730 --> 00:14:13,930
Vi trenger kode beslektet med hva jeg var
banging ut bare for et øyeblikk siden.

303
00:14:13,930 --> 00:14:16,120
Veldig gjennomførbart, men det legger kompleksitet.

304
00:14:16,120 --> 00:14:19,520
Og så utvikler tid, programmerer
tid er enda en annen ressurs

305
00:14:19,520 --> 00:14:22,520
at vi kanskje trenger å bruke
litt tid å få nye funksjoner.

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

307
00:14:24,020 --> 00:14:26,227
Vi vil ikke gå inn i denne
en i mye detalj.

308
00:14:26,227 --> 00:14:27,560
Men det er svært like i ånden.

309
00:14:27,560 --> 00:14:31,220
Jeg kunne gjennomføre en kø, og
sine tilsvarende operasjoner,

310
00:14:31,220 --> 00:14:35,660
enqueue eller dequeue, som legger til eller fjerner,
det er bare en mer avansert måte å si det,

311
00:14:35,660 --> 00:14:38,100
enqueue eller dequeue, som følger.

312
00:14:38,100 --> 00:14:41,170
Jeg kan bare gi meg selv en struct
som igjen har en rekke matrise,

313
00:14:41,170 --> 00:14:44,000
som igjen har en størrelse,
men hvorfor gjør jeg nå trenger

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

315
00:14:46,940 --> 00:14:50,630
Jeg trenger ikke å vite
forsiden av stabelen min.

316
00:14:50,630 --> 00:14:53,570
Vel, hvis jeg igjen for en
queue-- la oss bare vanskelig

317
00:14:53,570 --> 00:14:57,870
kode det som å ha som fem
heltall i her potensielt.

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

319
00:15:00,940 --> 00:15:03,430
Dette kommer til å være
numrene igjen.

320
00:15:03,430 --> 00:15:06,940
Og dette vil bli kalt størrelse.

321
00:15:06,940 --> 00:15:10,056
>> Hvorfor er det ikke tilstrekkelig
å ha bare størrelse?

322
00:15:10,056 --> 00:15:11,680
Vel, la oss presse de samme tallene på.

323
00:15:11,680 --> 00:15:14,220
Så jeg pushed-- jeg enqueued, eller dyttet.

324
00:15:14,220 --> 00:15:20,150
Nå skal jeg Enqueue 50, og deretter
51, og deretter 61, og dot dot dot.

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

326
00:15:21,070 --> 00:15:23,176
Jeg enqueued 50, deretter 51, deretter 61.

327
00:15:23,176 --> 00:15:25,050
Og som ser identisk
til en stabel så langt,

328
00:15:25,050 --> 00:15:27,190
bortsett fra at jeg trenger å gjøre en endring.

329
00:15:27,190 --> 00:15:33,680
Jeg trenger å oppdatere denne størrelsen, så jeg går
fra null til en til 02:58 nå.

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

331
00:15:35,760 --> 00:15:36,890
Hva skjer med dequeue?

332
00:15:36,890 --> 00:15:41,950
Hvem skal komme ut denne listen først
hvis det er kø på Apple Store?

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

334
00:15:42,780 --> 00:15:44,700
Så det er litt vanskeligere denne gangen.

335
00:15:44,700 --> 00:15:47,880
Mens forrige gang det var super
lett å bare gjøre størrelse minus én,

336
00:15:47,880 --> 00:15:51,440
Jeg kommer til slutten av min matrise effektivt
der tallene er, fjerner det 61.

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

338
00:15:52,920 --> 00:15:55,030
Jeg ønsker å ta 50, som
var der på 5:00

339
00:15:55,030 --> 00:15:56,790
å stille opp for
ny iPhone eller whatnot.

340
00:15:56,790 --> 00:16:01,200
Og så å kvitte seg med 50, jeg
kan ikke bare gjøre dette, ikke sant?

341
00:16:01,200 --> 00:16:02,547
Jeg kan krysse ut 50.

342
00:16:02,547 --> 00:16:04,380
Men vi sa vi
trenger ikke å være så anal

343
00:16:04,380 --> 00:16:06,330
som å klø seg eller skjule data.

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

345
00:16:08,090 --> 00:16:12,330
>> Men hvis jeg endrer størrelse nå
to, er dette tilstrekkelig informasjon

346
00:16:12,330 --> 00:16:15,711
å vite hva som skjer i min kø?

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

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

349
00:16:19,830 --> 00:16:22,980
spesielt hvis jeg fortsatt har
de samme tallene i minnet.

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

351
00:16:24,260 --> 00:16:27,090
Så jeg trenger å huske
nå hvor fronten er.

352
00:16:27,090 --> 00:16:29,630
Og så så jeg foreslo opp
der, vil vi nettopp har kalt

353
00:16:29,630 --> 00:16:33,729
Nth front, som første
Verdien skal ha vært hva?

354
00:16:33,729 --> 00:16:35,270
Zero, bare begynnelsen av listen.

355
00:16:35,270 --> 00:16:40,876
Men nå i tillegg til å minske
størrelsen, vi bare øke foran.

356
00:16:40,876 --> 00:16:42,000
Nå her er et annet problem.

357
00:16:42,000 --> 00:16:43,030
Så når jeg holder det gående.

358
00:16:43,030 --> 00:16:47,520
Antar at dette er antall
som 121, 124, og så, for faen,

359
00:16:47,520 --> 00:16:48,610
Jeg er tom for plass.

360
00:16:48,610 --> 00:16:50,390
Men vent litt, jeg er ikke det.

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

362
00:16:55,630 --> 00:17:00,370
tre, fire, slik at det antar
Størrelsen er fire, foran er én,

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

364
00:17:01,621 --> 00:17:04,329
Jeg ønsker å sette et annet nummer her,
men, faen, jeg er tom for plass.

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

366
00:17:06,710 --> 00:17:11,192
Hvor kan jeg sette noen
tilleggsverdi, som 171?

367
00:17:11,192 --> 00:17:13,400
Ja, jeg kunne bare slags
gå tilbake dit, ikke sant?

368
00:17:13,400 --> 00:17:18,161
Og deretter krysse ut 50, eller
bare overskrive den med 171.

369
00:17:18,161 --> 00:17:20,410
Og hvis du lurer på hvorfor
våre tall ble så tilfeldig,

370
00:17:20,410 --> 00:17:24,150
disse blir ofte tatt datamaskin
vitenskap kurs ved Harvard etter CS50.

371
00:17:24,150 --> 00:17:27,510
Men det var en god optimalisering,
fordi nå er jeg ikke kaste bort plass.

372
00:17:27,510 --> 00:17:30,750
Jeg har fortsatt å huske
hvor stor denne saken er total.

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

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

375
00:17:33,375 --> 00:17:36,260
Så nå er jeg fortsatt tom for plass,
så det samme problemet som før.

376
00:17:36,260 --> 00:17:39,140
Men du kan se hvordan nå
i koden din, har du sannsynligvis

377
00:17:39,140 --> 00:17:41,910
må skrive litt mer
kompleksitet å gjøre det skje.

378
00:17:41,910 --> 00:17:44,510
Og faktisk, hvilken operatør
i C sannsynligvis lar

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

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

381
00:17:50,160 --> 00:17:53,160
Så hva er litt kult om en kø,
selv om vi holder tegning arrays

382
00:17:53,160 --> 00:17:56,520
som disse som rette linjer, hvis du
slags tenke på dette som kurvet

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

384
00:18:00,341 --> 00:18:01,590
Jeg tror litt mer renslig.

385
00:18:01,590 --> 00:18:05,190
Du ville fortsatt å implementere
som mental modell i kode.

386
00:18:05,190 --> 00:18:07,550
Så det er ikke så vanskelig,
til slutt, for å implementere,

387
00:18:07,550 --> 00:18:12,430
men vi har fortsatt miste size-- snarere
evne til å endre størrelse, hvis vi ikke gjør dette.

388
00:18:12,430 --> 00:18:15,310
>> Vi må bli kvitt den array, vi
erstatte den med en enkelt peker,

389
00:18:15,310 --> 00:18:20,010
og deretter et sted i koden min har jeg fått
en kaller det fungere å faktisk lage

390
00:18:20,010 --> 00:18:23,720
array kalt tall?

391
00:18:23,720 --> 00:18:26,190
Malloc, eller en lignende
funksjon, akkurat.

392
00:18:26,190 --> 00:18:30,481
Eventuelle spørsmål om stabler 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
Godt spørsmål.

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

397
00:18:35,830 --> 00:18:38,520
Så generelt, når du bruker
mod, ville du gjøre det

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

399
00:18:40,620 --> 00:18:44,120
Så noe sånt som fem eller kapasitet, hvis
det er konstant, er trolig involvert.

400
00:18:44,120 --> 00:18:47,100
Men bare gjør modulo five
sannsynligvis ikke er tilstrekkelig,

401
00:18:47,100 --> 00:18:51,380
fordi vi trenger å vite gjør vi
vikle rundt her eller her eller her.

402
00:18:51,380 --> 00:18:54,160
Så du er sannsynligvis også
kommer til å ønske å involvere

403
00:18:54,160 --> 00:18:57,220
størrelsen av ting, eller
den fremre variable i tillegg.

404
00:18:57,220 --> 00:19:00,140
Så det er bare denne relativt
enkle aritmetiske uttrykk,

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

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

407
00:19:03,330 --> 00:19:05,780
En animasjon som noen
folk på et annet universitet

408
00:19:05,780 --> 00:19:08,060
satt sammen at vi har
tilpasset for denne diskusjonen.

409
00:19:08,060 --> 00:19:12,630
Det innebærer Jack læring
fakta om køer og statistikk.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Det var en gang,
det var en fyr som heter Jack.

412
00:19:21,890 --> 00:19:25,330
Når det kom til å få venner,
Jack ikke har en egen evne.

413
00:19:25,330 --> 00:19:28,220
Så Jack gikk for å snakke med
mest populære fyren han visste.

414
00:19:28,220 --> 00:19:30,920
Han gikk til Lou og spurte: Hva gjør jeg?

415
00:19:30,920 --> 00:19:33,400
Lou så at hans venn
var veldig fortvilet.

416
00:19:33,400 --> 00:19:36,050
Vel, begynte han, bare
se hvordan du er kledd.

417
00:19:36,050 --> 00:19:38,680
Har du ikke noen klær
med et annet utseende?

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

419
00:19:39,660 --> 00:19:40,840
Jeg er sikker på do.

420
00:19:40,840 --> 00:19:43,320
Kom til huset mitt og
Jeg skal vise dem til deg.

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

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

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

424
00:19:49,260 --> 00:19:52,290
Lou sa, jeg ser du har
alle klærne i en haug.

425
00:19:52,290 --> 00:19:54,870
Hvorfor ikke ha noen
andre gang på en stund?

426
00:19:54,870 --> 00:19:58,020
>> Jack sa, vel, da jeg
Fjern klær og sokker,

427
00:19:58,020 --> 00:20:00,780
Jeg vasker dem og sette
dem bort i esken.

428
00:20:00,780 --> 00:20:03,210
Så kommer neste
morgenen, og opp jeg hoppe.

429
00:20:03,210 --> 00:20:06,380
Jeg går til boksen og få
klærne mine utenfor toppen.

430
00:20:06,380 --> 00:20:09,070
Lou skjønte raskt
problemet med Jack.

431
00:20:09,070 --> 00:20:12,080
Han holdt klær, CD-er,
og bøker i bunken.

432
00:20:12,080 --> 00:20:14,420
Da han kom for
noe å lese eller å bære,

433
00:20:14,420 --> 00:20:17,100
han ville velge toppen bok eller undertøy.

434
00:20:17,100 --> 00:20:19,500
Så når han var ferdig, han
ville sette den rett tilbake.

435
00:20:19,500 --> 00:20:21,970
Tilbake det ville gå, på toppen av bunken.

436
00:20:21,970 --> 00:20:24,460
Jeg vet løsningen,
sa en triumfer Loud.

437
00:20:24,460 --> 00:20:27,090
Du trenger å lære å
begynne å bruke en kø.

438
00:20:27,090 --> 00:20:29,870
Lou tok Jack klær og
hang dem i skapet.

439
00:20:29,870 --> 00:20:32,710
Og da han hadde tømt
boksen, han bare kastet den.

440
00:20:32,710 --> 00:20:36,500
>> Så sa han, nå Jack, på slutten av
dagen, sette klærne på venstre

441
00:20:36,500 --> 00:20:37,990
når du setter dem bort.

442
00:20:37,990 --> 00:20:41,300
Så i morgen tidlig når du
se solen, få klærne

443
00:20:41,300 --> 00:20:43,440
på høyre, fra slutten av linjen.

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

445
00:20:44,880 --> 00:20:46,370
Det blir så fint.

446
00:20:46,370 --> 00:20:49,770
Du vil ha alt en gang
før du bruker noe to ganger.

447
00:20:49,770 --> 00:20:52,670
Og med alt i køer
i sitt skap og hylle,

448
00:20:52,670 --> 00:20:55,160
Jack begynte å føle
ganske sikker på seg selv.

449
00:20:55,160 --> 00:20:59,720
All takk til Lou og
hans fantastiske køen.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Greit, det er søtt.

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

452
00:21:05,920 --> 00:21:10,080
Så hva er egentlig skjer
på under panseret nå?

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

454
00:21:12,370 --> 00:21:15,680
at vi har evnen til å skape
biter av minne for oss selv

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

456
00:21:16,344 --> 00:21:18,510
Så dette er et bilde vi
skimtes bare den andre dagen.

457
00:21:18,510 --> 00:21:21,180
Vi gjorde egentlig ikke dvele
på det, men dette bildet

458
00:21:21,180 --> 00:21:24,180
har pågått under
panseret i flere uker nå.

459
00:21:24,180 --> 00:21:27,050
Og så dette representerer, bare
et rektangel som vi har trukket,

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

461
00:21:28,180 --> 00:21:31,850
Og kanskje din datamaskin, eller CS50
ID, har en gigabyte minne eller RAM

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

463
00:21:33,050 --> 00:21:34,450
Det spiller egentlig ingen rolle.

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
hovedsak gjør at programmet
å tro at det har tilgang

466
00:21:41,120 --> 00:21:42,982
til helheten av
datamaskinens minne,

467
00:21:42,982 --> 00:21:45,440
selv om du kan kjøre
flere programmer samtidig.

468
00:21:45,440 --> 00:21:46,990
Så i virkeligheten, som ikke egentlig fungerer.

469
00:21:46,990 --> 00:21:49,448
Men det er slags en illusjon
gitt til alle programmene dine.

470
00:21:49,448 --> 00:21:53,110
Så hvis du hadde to gigabyte RAM, dette
er hvordan datamaskinen kan tenke på det.

471
00:21:53,110 --> 00:21:57,110
>> Nå tilfeldigvis, en av disse
ting, en av disse segmentene av minne,

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

473
00:21:58,350 --> 00:22:01,680
Og faktisk helst
så langt i å skrive kode

474
00:22:01,680 --> 00:22:05,900
at du har kalt en
funksjon, for eksempel hoved.

475
00:22:05,900 --> 00:22:08,410
Husk at hver gang jeg har
trukket datamaskinens minne,

476
00:22:08,410 --> 00:22:10,640
Jeg har alltid trekke liksom
halvdelen av et rektangel her

477
00:22:10,640 --> 00:22:12,520
og ikke bry snakker
om hva som er ovenfor.

478
00:22:12,520 --> 00:22:15,980
Fordi når hoved kalles, hevder jeg
at du får denne snev av minne

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

480
00:22:16,970 --> 00:22:20,650
Og hvis hoved kalles en funksjon
som swap, vel swap går her.

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

482
00:22:23,720 --> 00:22:26,277
På noe som kalles en stabel
innsiden av datamaskinens minne.

483
00:22:26,277 --> 00:22:28,360
Nå ved slutten av dagen,
dette er bare adresser.

484
00:22:28,360 --> 00:22:30,680
Det er som å byte null,
byte en, byte 2 milliarder kroner.

485
00:22:30,680 --> 00:22:33,130
Men hvis du tenker på det
da dette rektangulært objekt,

486
00:22:33,130 --> 00:22:35,130
alt vi gjør hver
tid kaller vi en funksjon er

487
00:22:35,130 --> 00:22:37,180
lagdeling en ny bit av minne.

488
00:22:37,180 --> 00:22:41,700
Vi gir den funksjonen en skive
av sin egen hukommelse for å arbeide med.

489
00:22:41,700 --> 00:22:44,490
>> Og husker nå at dette er viktig.

490
00:22:44,490 --> 00:22:46,400
Fordi hvis vi har
noe som swap

491
00:22:46,400 --> 00:22:51,610
og to lokale variabler som A og B og
vi endre disse verdiene fra en og to

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

493
00:22:55,130 --> 00:22:58,330
det er som om dette stykke
minne er bare borte.

494
00:22:58,330 --> 00:23:00,080
I virkeligheten er det fortsatt
det forensically.

495
00:23:00,080 --> 00:23:01,940
Og noe er fortsatt faktisk det.

496
00:23:01,940 --> 00:23:05,410
Men konseptuelt, er det som
om det er helt borte.

497
00:23:05,410 --> 00:23:10,910
Og så hoved ikke kjenner noe av arbeidet
som ble gjort i det swap funksjon

498
00:23:10,910 --> 00:23:14,890
med mindre det er faktisk vedtatt i de
argumenter med pekeren eller ved referanse.

499
00:23:14,890 --> 00:23:17,790
Nå har den grunnleggende løsning
til det problemet med swap

500
00:23:17,790 --> 00:23:19,970
passerer ting på etter adresse.

501
00:23:19,970 --> 00:23:23,250
Men det viser seg også, hva som er
pågått over at en del

502
00:23:23,250 --> 00:23:26,330
av rektangelet hele denne tiden er
men det er mer minne der oppe.

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

504
00:23:28,790 --> 00:23:32,020
enten det er innsiden av GetString, som
vi har gjort for deg i CS50

505
00:23:32,020 --> 00:23:34,710
bibliotek, eller hvis dere
kalle malloc og spør

506
00:23:34,710 --> 00:23:37,950
operativsystemet for en del av
minne, betyr det ikke kommer fra bunken.

507
00:23:37,950 --> 00:23:40,960
Det kommer fra et annet sted
i datamaskinens minne

508
00:23:40,960 --> 00:23:42,220
som heter haugen.

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

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

511
00:23:44,285 --> 00:23:45,160
Det er det samme minne.

512
00:23:45,160 --> 00:23:49,080
Det er bare RAM som er opp
der i stedet for her nede.

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

514
00:23:50,750 --> 00:23:53,650
Vel, hvis datamaskinen har
en begrenset mengde minne

515
00:23:53,650 --> 00:23:57,450
og stabelen vokser opp, så
til å snakke, og haugen, ifølge

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

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

518
00:24:01,140 --> 00:24:03,430
du blir gitt en skive
minne ovenfra,

519
00:24:03,430 --> 00:24:06,630
så kanskje litt lavere, så litt
lavere, hver gang du ringer malloc,

520
00:24:06,630 --> 00:24:10,100
haugen, det er bruk,
er slags vokser,

521
00:24:10,100 --> 00:24:11,950
voksende nærmere og nærmere til hva?

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

523
00:24:13,382 --> 00:24:14,840
Så betyr dette virke som en god idé?

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

525
00:24:18,420 --> 00:24:22,140
Jeg mener, hvor det er egentlig ikke klar
hva annet du kan gjøre hvis du bare

526
00:24:22,140 --> 00:24:23,910
har en begrenset mengde minne.

527
00:24:23,910 --> 00:24:25,200
Men dette er sikkert dårlig.

528
00:24:25,200 --> 00:24:27,920
De to pilene er på en
Crash Course for hverandre.

529
00:24:27,920 --> 00:24:31,930
>> Og det viser seg at slemmingen, folk som
er spesielt bra med programmering,

530
00:24:31,930 --> 00:24:36,140
og prøver å hacke inn i datamaskiner,
kan utnytte denne virkeligheten.

531
00:24:36,140 --> 00:24:38,290
Faktisk, la oss vurdere
en liten bit.

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

533
00:24:41,350 --> 00:24:43,100
Vi vil peke deg på
artikkelen hvis nysgjerrig.

534
00:24:43,100 --> 00:24:45,650
Men det er et angrep generelt
kjent som buffer overflow som

535
00:24:45,650 --> 00:24:49,570
har eksistert så lenge som mennesker
har hatt muligheten til å manipulere

536
00:24:49,570 --> 00:24:53,120
datamaskinens minne, særlig i C.
Så dette er en svært vilkårlig program,

537
00:24:53,120 --> 00:24:55,130
men la oss lese det fra bunnen opp.

538
00:24:55,130 --> 00:24:57,650
Hoved inn argc røye stjerners argv.

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

540
00:24:59,830 --> 00:25:03,620
Og alle de viktigste ikke er tilsynelatende samtale
en funksjon, kaller det F for enkelhet.

541
00:25:03,620 --> 00:25:04,610
Og det går i det?

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

543
00:25:05,490 --> 00:25:09,320
Så det går over i F uansett
ordet er at brukeren har skrevet

544
00:25:09,320 --> 00:25:11,500
ved ledeteksten etter
programmets navn i det hele tatt.

545
00:25:11,500 --> 00:25:15,730
Så mye som Cæsar eller Vigenère, som
du kanskje husker gjør med argv.

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

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

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

549
00:25:22,100 --> 00:25:24,920
Og det heter vilkårlig
bar i dette eksemplet.

550
00:25:24,920 --> 00:25:27,710
Og så char c 12,
bare i lekmann vilkår,

551
00:25:27,710 --> 00:25:31,750
hva er char c brakett 12 gjør for oss?

552
00:25:31,750 --> 00:25:33,440
Hva er det å gjøre?

553
00:25:33,440 --> 00:25:36,490
Tildele minne, spesielt
12 byte for 12 chars.

554
00:25:36,490 --> 00:25:36,990
Nøyaktig.

555
00:25:36,990 --> 00:25:40,000
Og så den siste linjen, rør og
kopiere, har du sannsynligvis ikke sett.

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

557
00:25:43,360 --> 00:25:48,160
er å kopiere sin andre argument
inn i sin første argument,

558
00:25:48,160 --> 00:25:51,190
men bare opp til en
visst antall byte.

559
00:25:51,190 --> 00:25:53,860
Så det tredje argumentet sier:
hvor mange bytes bør du kopiere?

560
00:25:53,860 --> 00:25:56,720
Lengden på bar,
hva brukeren skrev inn.

561
00:25:56,720 --> 00:25:59,320
Og innholdet
bar, som streng, er

562
00:25:59,320 --> 00:26:02,330
kopiert inn i minnet pekte på at C.

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

564
00:26:04,060 --> 00:26:06,300
Det er en contrived eksempel
men det er representative

565
00:26:06,300 --> 00:26:10,100
av en klasse av angrepsvektorer,
en måte å angripe et program.

566
00:26:10,100 --> 00:26:15,050
Alt er fint og bra hvis brukeren
typer i et ord som er 11 tegn

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

568
00:26:18,040 --> 00:26:22,830
Hva om brukeren skriver inn mer enn
11 eller 12 eller 20 eller 50 tegn?

569
00:26:22,830 --> 00:26:25,090
Hva er dette programmet kommer til å gjøre?

570
00:26:25,090 --> 00:26:29,360
Potensielt SEG feil. Det kommer
å blindt kopiere alt i bar opp

571
00:26:29,360 --> 00:26:31,750
til dens lengde, som er
bokstavelig talt alt i bar,

572
00:26:31,750 --> 00:26:36,307
i adresse rettet mot C. Men C
har bare preemptively gitt som 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Men det er ingen ekstra sjekk.

574
00:26:37,640 --> 00:26:38,700
Det er ikke noe om forholdene.

575
00:26:38,700 --> 00:26:40,580
Det er ingen feilkontroll her.

576
00:26:40,580 --> 00:26:43,270
>> Og så hva dette programmet er
kommer til å gjøre er å bare blindt

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

578
00:26:45,750 --> 00:26:47,880
Og så hvis vi trekker dette
som et bilde, her

579
00:26:47,880 --> 00:26:49,860
bare en snev av plass i minnet.

580
00:26:49,860 --> 00:26:53,470
Så legger merke til på bunnen, vi
har lokal variabel bar.

581
00:26:53,470 --> 00:26:57,330
Slik at pekeren som kommer til å store--
heller at lokale argument som er

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

583
00:26:58,672 --> 00:27:00,380
Og deretter legge merke
over den i en stabel,

584
00:27:00,380 --> 00:27:02,505
fordi hver gang du spør
for minne på stakken,

585
00:27:02,505 --> 00:27:04,310
det går litt
ovenfor det billedlig,

586
00:27:04,310 --> 00:27:06,270
merke til at vi har fått 12 bytes der.

587
00:27:06,270 --> 00:27:10,690
Øverst til venstre ene er C brakett null og
nederst til høyre en er C brakett 11.

588
00:27:10,690 --> 00:27:12,870
Det er bare hvordan datamaskinene
kommer til å legge den ut.

589
00:27:12,870 --> 00:27:18,300
Så bare intuitivt, hvis bar har mer
enn 12 tegn totalt, inkludert

590
00:27:18,300 --> 00:27:25,790
backslash null, hvor er
12 eller C brakett 12 kommer til å gå?

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

592
00:27:28,440 --> 00:27:30,900
hundrede karakter kommer
å ende opp i bildet?

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

594
00:27:33,400 --> 00:27:36,300
>> Høyre, fordi selv om
stakken vokser oppover,

595
00:27:36,300 --> 00:27:39,590
når du har satt ting i
det, for design grunner,

596
00:27:39,590 --> 00:27:41,294
setter minne fra topp til bunn.

597
00:27:41,294 --> 00:27:44,460
Så hvis du har mer enn 12 bytes,
du kommer til å begynne å overskrive bar.

598
00:27:44,460 --> 00:27:47,280
Nå det er en bug, men det er
egentlig ikke en stor avtale.

599
00:27:47,280 --> 00:27:51,130
Men det er en stor avtale, fordi det er
flere ting som skjer i minnet.

600
00:27:51,130 --> 00:27:53,074
Så her er hvordan vi kan
sette hallo, for å være klar.

601
00:27:53,074 --> 00:27:54,490
Hvis jeg skrev i hallo ved ledeteksten.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash null, ender opp i
disse 12 bytes, og vi er super trygg.

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

604
00:28:00,330 --> 00:28:03,020
Men hvis jeg skriver noe
lenger, potensielt det er

605
00:28:03,020 --> 00:28:05,860
kommer til å krype inn i bar plass.

606
00:28:05,860 --> 00:28:08,405
Men enda verre, viser det
ut hele denne tiden,

607
00:28:08,405 --> 00:28:11,530
selv om vi aldri har snakket om
det er stabelen brukes til andre ting.

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

609
00:28:13,560 --> 00:28:15,100
>> C er et meget lavt nivå språk.

610
00:28:15,100 --> 00:28:17,810
Og den slags hemmelighet
bruker stabelen også

611
00:28:17,810 --> 00:28:21,260
å huske på når en
funksjonen kalles, hva

612
00:28:21,260 --> 00:28:26,040
adressen er av den foregående funksjon,
slik at den kan hoppe tilbake til denne funksjonen.

613
00:28:26,040 --> 00:28:29,980
Så når hoved samtaler bytte, blant
de tingene presset på stakken

614
00:28:29,980 --> 00:28:34,380
er ikke bare bytter lokale variabler,
eller sine argumenter, også hemmelighet skjøvet

615
00:28:34,380 --> 00:28:37,510
over stabelen som representert
ved den røde skive her,

616
00:28:37,510 --> 00:28:40,520
er adressen til hoved fysisk
i datamaskinens minne,

617
00:28:40,520 --> 00:28:44,180
slik at når swap er gjort, datamaskinen
vet at jeg trenger å gå tilbake til hoved

618
00:28:44,180 --> 00:28:46,760
og avslutt gjennomføre den viktigste funksjonen.

619
00:28:46,760 --> 00:28:51,960
Så dette er farlig nå, fordi hvis
brukeren skriver i tillegg mer enn hei,

620
00:28:51,960 --> 00:28:57,030
slik at brukerens input clobbers
eller overskriver den røde delen,

621
00:28:57,030 --> 00:28:59,820
logisk hvis datamaskinens
bare kommer til å blindt anta

622
00:28:59,820 --> 00:29:03,830
at byte i at rødt skive er
adressen som det skal returnere,

623
00:29:03,830 --> 00:29:09,020
hva om motstanderen er smart nok eller
heldig nok til å sette en sekvens av bytes

624
00:29:09,020 --> 00:29:13,450
Det som ser ut som en adresse,
men det er adressen til koden

625
00:29:13,450 --> 00:29:18,730
at han eller hun ønsker datamaskinen
å kjøre i stedet for hoved?

626
00:29:18,730 --> 00:29:21,670
>> Med andre ord, hvis hva
brukeren skriver på spørsmål,

627
00:29:21,670 --> 00:29:23,850
er ikke bare noe
ufarlige som hallo,

628
00:29:23,850 --> 00:29:28,210
men det er faktisk kode som er tilsvarende
for å slette alle denne brukerens filer?

629
00:29:28,210 --> 00:29:30,060
Eller send passordet sitt til meg?

630
00:29:30,060 --> 00:29:31,940
Eller starte logging deres
tastetrykk, ikke sant?

631
00:29:31,940 --> 00:29:34,920
Det er en måte, la oss fastsetter i dag,
at de kunne skrive inn ikke bare hallo

632
00:29:34,920 --> 00:29:36,711
verden eller deres navn,
de kunne hovedsak

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

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

635
00:29:43,450 --> 00:29:48,950
Så riktignok litt abstrakt, hvis
brukertyper i nok motstandere kode

636
00:29:48,950 --> 00:29:52,330
at vi skal generalisere her som
A. A er angrepet eller motstandere.

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

638
00:29:53,140 --> 00:29:55,306
Vi bryr oss ikke om
tall eller nuller og ettall

639
00:29:55,306 --> 00:29:59,470
i dag, slik at du ender opp
skrive den røde delen,

640
00:29:59,470 --> 00:30:01,580
Legg merke til at sekvens av bytes.

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

642
00:30:05,020 --> 00:30:08,960
Og nå som Wikipedias artikkel her
har foreslått, hvis du nå faktisk begynner

643
00:30:08,960 --> 00:30:12,460
merking av byte i din datamaskin
minne, hva Wikipedia-artikkelen er

644
00:30:12,460 --> 00:30:19,060
foreslår er det, hva hvis adressen
av det øvre venstre byte er 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Med andre ord, hvis skurken er
smart nok med hans eller hennes kode

646
00:30:22,200 --> 00:30:26,650
å faktisk sette et tall her at
svarer til adressen til kode

647
00:30:26,650 --> 00:30:29,180
han eller hun injisert
inn i datamaskinen, du

648
00:30:29,180 --> 00:30:31,050
kan lure datamaskinen
til å gjøre noe.

649
00:30:31,050 --> 00:30:34,140
Fjerne filer, e-post
ting, sniffing trafikken,

650
00:30:34,140 --> 00:30:36,710
bokstavelig talt noe kunne være
injiseres inn i datamaskinen.

651
00:30:36,710 --> 00:30:39,220
Og så en buffer overflow
angrepet i sin kjerne

652
00:30:39,220 --> 00:30:43,530
er bare en dum, dum
ordnede av en matrise som

653
00:30:43,530 --> 00:30:45,840
ikke har sine grenser kontrollert.

654
00:30:45,840 --> 00:30:48,850
Og dette er hva som er super farlig
og samtidig super kraftig

655
00:30:48,850 --> 00:30:52,560
i C er at vi faktisk har
adgang til hvor som helst i lageret.

656
00:30:52,560 --> 00:30:55,320
Det er opp til oss, programmerere,
som skriver den opprinnelige koden

657
00:30:55,320 --> 00:30:59,330
å sjekke darn lengden på eventuelle
arrays at vi manipulere.

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

659
00:31:00,750 --> 00:31:03,190
Hvis vi rulle tilbake til dette
kode, skal jeg ikke bare

660
00:31:03,190 --> 00:31:08,000
endre lengden på baren, hva
annet bør jeg sjekke?

661
00:31:08,000 --> 00:31:10,620
Hva annet skal jeg gjøre for å
hindre dette angrepet helt?

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

663
00:31:14,110 --> 00:31:16,140
som er lengden på bar.

664
00:31:16,140 --> 00:31:18,910
Jeg ønsker å si, kopier som
mange bytes som er i bar

665
00:31:18,910 --> 00:31:24,090
opp til den tilordnede
minne, eller 12 maksimalt.

666
00:31:24,090 --> 00:31:27,450
Så jeg trenger noen form for hvis tilstanden
som gjør sjekke lengden på bar,

667
00:31:27,450 --> 00:31:32,800
men dersom den overstiger 12, vi bare vanskelig kode
12 som den maksimalt mulige avstand.

668
00:31:32,800 --> 00:31:35,910
Ellers såkalt buffer
flow angrep kan skje.

669
00:31:35,910 --> 00:31:38,451
På bunnen av disse slides,
hvis du er glad i å lese mer

670
00:31:38,451 --> 00:31:41,200
er selve opprinnelige artikkelen
Hvis du ønsker å ta en titt.

671
00:31:41,200 --> 00:31:44,550
>> Men nå, blant de prisene
betalt her var ineffektivitet.

672
00:31:44,550 --> 00:31:46,680
Så det var en rask
lavt nivå titt på hva

673
00:31:46,680 --> 00:31:49,709
problemer kan oppstå nå som vi
har tilgang til datamaskinens minne.

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

675
00:31:51,750 --> 00:31:53,800
var bare ineffektivitet
av en lenket liste.

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

677
00:31:56,019 --> 00:31:57,560
Vi har ikke lenger en sammenhengende matrise.

678
00:31:57,560 --> 00:31:58,980
Vi har ikke tilfeldig tilgang.

679
00:31:58,980 --> 00:32:00,710
Vi kan ikke bruke hakeparentes notasjon.

680
00:32:00,710 --> 00:32:04,590
Vi har bokstavelig talt å bruke en stund loop
som den jeg skrev for et øyeblikk siden.

681
00:32:04,590 --> 00:32:09,740
Men på mandag, vi hevdet at vi kan
krype tilbake til området for effektivitet

682
00:32:09,740 --> 00:32:13,040
å oppnå noe som er
logaritmisk kanskje, eller det aller beste,

683
00:32:13,040 --> 00:32:16,120
kanskje til og med noe som er
såkalt konstant tid.

684
00:32:16,120 --> 00:32:19,840
Så hvordan kan vi gjøre det ved hjelp av disse nye
verktøy, disse adressene, disse pekere,

685
00:32:19,840 --> 00:32:22,210
og threading ting i vår egen?

686
00:32:22,210 --> 00:32:23,960
Vel, antar at
her, dette er en gjeng

687
00:32:23,960 --> 00:32:27,170
av tall som vi ønsker å lagre i en
datastruktur og søk effektivt.

688
00:32:27,170 --> 00:32:30,960
Vi kan absolutt spole tilbake til uke
to, kaste disse inn i en matrise,

689
00:32:30,960 --> 00:32:33,150
og søke i dem ved hjelp av binære søk.

690
00:32:33,150 --> 00:32:34,040
Splitt og hersk.

691
00:32:34,040 --> 00:32:37,720
Og faktisk du skrev
binært søk i PSET3,

692
00:32:37,720 --> 00:32:40,100
hvor du implementert finne programmet.

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

694
00:32:40,890 --> 00:32:45,060
Det er på en måte en mer
smart måte å gjøre dette.

695
00:32:45,060 --> 00:32:47,390
Det er litt mer
sofistikert og det kanskje

696
00:32:47,390 --> 00:32:50,830
tillater oss å se hvorfor binære
Søket er så mye raskere.

697
00:32:50,830 --> 00:32:52,980
Først, la oss introdusere
oppfatningen av et tre.

698
00:32:52,980 --> 00:32:54,730
Som selv om det i
reality trær slags

699
00:32:54,730 --> 00:32:57,730
vokse som dette, i verden av datamaskinen
vitenskap de slags vokser nedover

700
00:32:57,730 --> 00:33:00,830
som et familietre, hvor du har
dine besteforeldre eller oldeforeldre

701
00:33:00,830 --> 00:33:04,580
eller whatnot på toppen, patriarken og
matriarch av familien, bare ett

702
00:33:04,580 --> 00:33:07,930
såkalte rot, node, nedenfor
som er dens barn,

703
00:33:07,930 --> 00:33:11,442
nedenfor som er dets barn, eller
sine etterkommere mer generelt.

704
00:33:11,442 --> 00:33:13,400
Og noen henging
bunnen av familien

705
00:33:13,400 --> 00:33:16,070
tre, foruten å være den
yngste i familien,

706
00:33:16,070 --> 00:33:19,520
kan også bare være generisk
kalt bladene på treet.

707
00:33:19,520 --> 00:33:21,800
>> Så dette er bare en haug
av ord og definisjoner

708
00:33:21,800 --> 00:33:25,790
for noe som kalles et tre i datamaskinen
vitenskap, mye som et familietre.

709
00:33:25,790 --> 00:33:28,770
Men det er mer avansert inkarnasjoner
av trær, hvorav

710
00:33:28,770 --> 00:33:30,780
kalles et binært søketre.

711
00:33:30,780 --> 00:33:34,380
Og du kan slags tease
hverandre hva denne tingen gjør.

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

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

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

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

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

717
00:33:47,210 --> 00:33:52,000
Det er mer at hver av nodene har ingen
mer enn to barn, som vi ser her.

718
00:33:52,000 --> 00:33:54,990
Generelt, en tree-- og
dine foreldre og besteforeldre

719
00:33:54,990 --> 00:33:57,640
kan ha så mange barn eller
barnebarna som de faktisk ønsker,

720
00:33:57,640 --> 00:34:00,820
og så for eksempel der har vi tre
barn off at høyre hånd node,

721
00:34:00,820 --> 00:34:05,480
men i et binært tre, har en node
null, én eller to barn maksimalt.

722
00:34:05,480 --> 00:34:08,496
Og det er en fin egenskap,
fordi hvis det er avkortet med to,

723
00:34:08,496 --> 00:34:10,620
vi kommer til å være i stand til å
få en liten tømmer basen to-

724
00:34:10,620 --> 00:34:11,975
handlingen foregår her til slutt.

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

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

727
00:34:14,558 --> 00:34:19,810
Søketre betyr at tallene er
anordnet slik at den venstre barnets

728
00:34:19,810 --> 00:34:22,429
verdien er større enn ved roten.

729
00:34:22,429 --> 00:34:26,010
Og sin rett barnet er
større enn roten.

730
00:34:26,010 --> 00:34:29,290
Med andre ord, hvis du tar noen av de
noder, sirklene i dette bildet,

731
00:34:29,290 --> 00:34:31,840
og ser på sitt venstre
barn og sin rett barnet,

732
00:34:31,840 --> 00:34:34,739
det første bør være mindre enn,
det andre bør være større enn.

733
00:34:34,739 --> 00:34:36,159
Så tilregnelighet sjekk 55.

734
00:34:36,159 --> 00:34:37,780
Det er igjen barnet er 33.

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

736
00:34:38,620 --> 00:34:40,929
55, er det rett barnet 77.

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

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

739
00:34:43,199 --> 00:34:46,480
Vi kunne sjekke hver og en av dem
noder og det samme mønsteret ville holde.

740
00:34:46,480 --> 00:34:49,389
>> Så hva er fint i en
binært søketre, er

741
00:34:49,389 --> 00:34:52,204
at man kan vi gjennomføre det
med en struct, akkurat som dette.

742
00:34:52,204 --> 00:34:54,620
Og selv om vi kaster
massevis av strukturer på din,

743
00:34:54,620 --> 00:34:56,560
de er noe
intuitive nå forhåpentligvis.

744
00:34:56,560 --> 00:35:00,570
Syntaksen er fortsatt uforståelige sikkert,
men innholdet av et knutepunkt i denne

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

746
00:35:02,786 --> 00:35:04,910
enten det er et rektangel
på skjermen eller en sirkel,

747
00:35:04,910 --> 00:35:08,970
det er bare noen generiske container,
i dette tilfelle av et tre, slik at en

748
00:35:08,970 --> 00:35:11,780
vi så, vi trenger et heltall
i hver av nodene

749
00:35:11,780 --> 00:35:15,460
og da trenger jeg to pekere peker
til venstre barnet og retten barnet,

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

751
00:35:16,590 --> 00:35:20,730
Så det er hvordan vi kan
implementere det i en struct.

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

753
00:35:22,315 --> 00:35:26,730
Vel, la oss ta en rask
se på dette lille eksempelet.

754
00:35:26,730 --> 00:35:29,820
Det er ikke funksjonell, men jeg har
kopiert og limt den strukturen.

755
00:35:29,820 --> 00:35:33,510
Og hvis min funksjon for en binær
søketre kalles søk,

756
00:35:33,510 --> 00:35:36,980
og dette tar to argumenter,
et heltall N og en peker

757
00:35:36,980 --> 00:35:41,400
til en node, så en peker til treet
eller en peker til roten av et tre,

758
00:35:41,400 --> 00:35:43,482
hvordan går jeg om å lete etter N?

759
00:35:43,482 --> 00:35:45,440
Vel, først, fordi jeg er
arbeider med pekere,

760
00:35:45,440 --> 00:35:46,750
Jeg kommer til å gjøre en mental helse sjekk.

761
00:35:46,750 --> 00:35:54,279
Hvis tre likeverdige lik null, er N
i dette treet eller ikke i dette treet?

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

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

764
00:35:56,870 --> 00:35:59,230
Jeg kan like godt bare
blindt si return false.

765
00:35:59,230 --> 00:36:04,050
Hvis du gir meg ingenting, jeg sikkert ikke kan
finne en rekke N. Så hva annet jeg kan

766
00:36:04,050 --> 00:36:04,750
Sjekk nå?

767
00:36:04,750 --> 00:36:12,830
Jeg kommer til å si vel annet hvis N er
mindre enn det som er på trenode

768
00:36:12,830 --> 00:36:16,300
at jeg har blitt overlevert N verdi.

769
00:36:16,300 --> 00:36:20,270
Med andre ord, hvis tallet er jeg
leter etter, N, er mindre enn noden

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

771
00:36:21,340 --> 00:36:23,190
Og node jeg ser
på kalles treet,

772
00:36:23,190 --> 00:36:26,370
og husker fra forrige eksempel
å få på verdien i en peker,

773
00:36:26,370 --> 00:36:28,310
Jeg bruker pilen notasjon.

774
00:36:28,310 --> 00:36:35,960
Så hvis N er mindre enn tre pilen
N, ønsker jeg å konseptuelt gå venstre.

775
00:36:35,960 --> 00:36:38,590
Hvordan kan jeg uttrykke søkingen igjen?

776
00:36:38,590 --> 00:36:41,560
For å være klar, hvis dette er
bildet i spørsmålet,

777
00:36:41,560 --> 00:36:44,612
og jeg har blitt vedtatt at øverste
arrow som er peker nedover.

778
00:36:44,612 --> 00:36:45,570
Det er mitt tre spisser.

779
00:36:45,570 --> 00:36:48,060
Jeg peker på roten av treet.

780
00:36:48,060 --> 00:36:52,100
Og jeg ser si, for
antall 44, vilkårlig.

781
00:36:52,100 --> 00:36:55,300
Er 44 mindre enn eller
større enn 55 åpenbart?

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

783
00:36:56,360 --> 00:36:58,760
Og så dette hvis tilstanden gjelder.

784
00:36:58,760 --> 00:37:03,981
Så konseptuelt, hva ønsker jeg å
søke neste hvis jeg leter etter 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
>> Akkurat, jeg ønsker å
søke venstre barnet,

788
00:37:11,100 --> 00:37:12,789
eller venstre sub-tre av dette bildet.

789
00:37:12,789 --> 00:37:14,830
Og faktisk, la meg gjennom
bildet her nede

790
00:37:14,830 --> 00:37:17,770
for bare et øyeblikk siden
Jeg kan ikke avlyse dette ut.

791
00:37:17,770 --> 00:37:21,150
Hvis jeg begynner her på 55, og
Jeg vet at verdien 44

792
00:37:21,150 --> 00:37:23,180
Jeg leter etter er å
venstre, det er slags

793
00:37:23,180 --> 00:37:26,010
som å rive telefonboken i
halvparten eller rive treet i to.

794
00:37:26,010 --> 00:37:29,660
Jeg har ikke lenger å bry seg om
Hele denne halvdelen av treet.

795
00:37:29,660 --> 00:37:33,270
Og likevel, merkelig i forhold til
struktur, denne tingen over her at

796
00:37:33,270 --> 00:37:36,682
starter med 33, som selv
er et binært søketre.

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

798
00:37:39,890 --> 00:37:41,707
per definisjon er rekursivt.

799
00:37:41,707 --> 00:37:44,540
Du har kanskje et tre som er denne
stor, men hver og en av sine barn

800
00:37:44,540 --> 00:37:46,870
representerer et tre bare litt mindre.

801
00:37:46,870 --> 00:37:50,910
I stedet for at det blir bestefar
eller bestemor, nå er det bare mamma

802
00:37:50,910 --> 00:37:54,300
or-- Jeg kan ikke say-- ikke mamma
eller far, det ville være rart.

803
00:37:54,300 --> 00:37:59,000
I stedet de to barna der
ville være som bror og søsken.

804
00:37:59,000 --> 00:38:01,120
En ny generasjon av slektstreet.

805
00:38:01,120 --> 00:38:02,900
Men strukturelt, er det den samme ideen.

806
00:38:02,900 --> 00:38:06,790
Og det viser seg at jeg har en funksjon
som jeg kan søke en binær søk

807
00:38:06,790 --> 00:38:07,290
treet.

808
00:38:07,290 --> 00:38:08,680
Det kalles søk.

809
00:38:08,680 --> 00:38:17,870
Jeg søker etter N i treet pil venstre
annet hvis N er større enn verdien

810
00:38:17,870 --> 00:38:18,870
at jeg er for tiden på.

811
00:38:18,870 --> 00:38:20,800
55 i historien et øyeblikk siden.

812
00:38:20,800 --> 00:38:23,780
Jeg har en funksjon som heter
søk som jeg kan bare

813
00:38:23,780 --> 00:38:29,660
passere N dette og rekursivt søk
sub-treet og bare retur

814
00:38:29,660 --> 00:38:30,620
uansett hva det svaret.

815
00:38:30,620 --> 00:38:33,530
Annet jeg har fått noen endelige base case her.

816
00:38:33,530 --> 00:38:35,310
>> Hva er det siste tilfelle?

817
00:38:35,310 --> 00:38:36,570
Treet er enten null.

818
00:38:36,570 --> 00:38:39,980
Verdien jeg heller leter etter er
mindre enn eller større enn det

819
00:38:39,980 --> 00:38:42,610
eller lik den.

820
00:38:42,610 --> 00:38:44,750
Og jeg kan si lik
like, men logisk er det

821
00:38:44,750 --> 00:38:46,500
tilsvarer bare si annet her.

822
00:38:46,500 --> 00:38:49,150
Så sant er hvordan jeg finner noe.

823
00:38:49,150 --> 00:38:51,710
Så forhåpentligvis er dette en
enda mer overbevisende eksempel

824
00:38:51,710 --> 00:38:54,900
enn den dumme sigma funksjonen
vi gjorde noen forelesninger tilbake,

825
00:38:54,900 --> 00:38:58,360
hvor det var like enkelt å bruke en løkke
å telle opp alle tallene fra én

826
00:38:58,360 --> 00:39:02,390
til N. Her med en datastruktur
som i seg selv er rekursivt

827
00:39:02,390 --> 00:39:07,050
definert og rekursivt trukket, nå er vi
har evnen til å uttrykke oss

828
00:39:07,050 --> 00:39:09,780
i koden som selv er rekursiv.

829
00:39:09,780 --> 00:39:12,580
Så dette er nøyaktig samme kode her.

830
00:39:12,580 --> 00:39:14,400
>> Så hva andre problemer kan vi løse?

831
00:39:14,400 --> 00:39:18,160
Så en rask steg unna
trær for bare et øyeblikk.

832
00:39:18,160 --> 00:39:20,130
Her er, sier den tyske flagget.

833
00:39:20,130 --> 00:39:22,020
Og det er helt klart en
Mønsteret til dette flagget.

834
00:39:22,020 --> 00:39:23,811
Og det er massevis av
flagg i verden som

835
00:39:23,811 --> 00:39:27,560
er så enkelt som dette i form
av sine farger og mønstre.

836
00:39:27,560 --> 00:39:31,930
Men antar at dette er lagret som en
GIF eller JPEG eller bitmap, eller en ping,

837
00:39:31,930 --> 00:39:34,240
noe grafisk filformat
som du er kjent,

838
00:39:34,240 --> 00:39:36,460
noen som vi er
spille med i PSET4.

839
00:39:36,460 --> 00:39:41,550
Dette virker ikke verdt å lagre
svart piksel, svart piksel, svart piksel,

840
00:39:41,550 --> 00:39:44,790
prikk, prikk, prikk, en hel haug med
svarte piksler for første avsøkningslinje,

841
00:39:44,790 --> 00:39:47,430
eller rad, deretter en hel haug med
det samme, da en hel haug

842
00:39:47,430 --> 00:39:49,530
av de samme, og deretter en
hel haug med røde piksler,

843
00:39:49,530 --> 00:39:53,020
røde piksler, røde piksler, deretter en hel
haug med gule piksler, gul, ikke sant?

844
00:39:53,020 --> 00:39:55,050
>> Det er slik ineffektivitet her.

845
00:39:55,050 --> 00:39:59,040
Hvordan ville du intuitivt
komprimere det tyske flagget

846
00:39:59,040 --> 00:40:01,320
hvis implementere det som en fil?

847
00:40:01,320 --> 00:40:04,940
Som hva informasjon kan vi ikke
bry lagre på disk for

848
00:40:04,940 --> 00:40:08,040
å redusere vår filstørrelsen fra lignende
en megabyte til en kilobyte, noe

849
00:40:08,040 --> 00:40:09,430
mindre?

850
00:40:09,430 --> 00:40:13,130
Hvori ligger redundans
her å være klar?

851
00:40:13,130 --> 00:40:13,880
Hva kan du gjøre?

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
Nøyaktig.

855
00:40:21,970 --> 00:40:24,550
Hvorfor ikke heller enn å huske
fargen på hver darn pixel

856
00:40:24,550 --> 00:40:28,200
akkurat som du gjør i PSET4
med bitmap fil format,

857
00:40:28,200 --> 00:40:32,060
hvorfor ikke bare representerer
lengst til venstre kolonne av bildeelementer, f.eks

858
00:40:32,060 --> 00:40:35,370
en haug av svarte piksler, en haug
rødt, og en haug med gule,

859
00:40:35,370 --> 00:40:39,210
og så bare liksom kode
Ideen om gjenta dette 100 ganger

860
00:40:39,210 --> 00:40:41,020
eller gjenta dette 1000 ganger?

861
00:40:41,020 --> 00:40:43,430
Hvor 100 eller 1000 er
bare et tall, så du

862
00:40:43,430 --> 00:40:47,290
kan komme unna med bare et enkelt tall
istedenfor hundrevis eller tusenvis

863
00:40:47,290 --> 00:40:48,270
ekstra piksler.

864
00:40:48,270 --> 00:40:50,990
Og ja, det er hvordan vi
kunne komprimere den tyske flagget.

865
00:40:50,990 --> 00:40:51,490
Og

866
00:40:51,490 --> 00:40:53,470
Hva nå om det franske flagget?

867
00:40:53,470 --> 00:40:58,930
Og en liten en slags
mental trening, som flagg

868
00:40:58,930 --> 00:41:01,040
kan komprimeres mer på disken?

869
00:41:01,040 --> 00:41:05,720
Den tyske flagg eller fransk
flagg, hvis vi tar som tilnærming?

870
00:41:05,720 --> 00:41:08,490
Den tyske flagget, fordi det er
mer horisontal redundans.

871
00:41:08,490 --> 00:41:12,190
Og ved design, mange grafiske fil
formater gjør faktisk fungerer som skanningslinjer

872
00:41:12,190 --> 00:41:12,830
horisontalt.

873
00:41:12,830 --> 00:41:14,674
De kunne arbeide
vertikalt, bare menneskelighet

874
00:41:14,674 --> 00:41:17,090
besluttet år siden at vi vil
vanligvis tenker på ting rad

875
00:41:17,090 --> 00:41:18,880
av raden i stedet for en kolonne etter kolonne.

876
00:41:18,880 --> 00:41:20,820
Så ja hvis du var
å se på filen

877
00:41:20,820 --> 00:41:24,670
Størrelsen på en tysk flagg og en fransk
flagg, så lenge som oppløsningen er

878
00:41:24,670 --> 00:41:27,530
den samme, den samme bredde
og høyde, dette en

879
00:41:27,530 --> 00:41:31,580
her kommer til å bli større, fordi du
må gjenta deg selv tre ganger.

880
00:41:31,580 --> 00:41:35,570
Du må spesifisere blå, gjentar
selv, hvit, gjentar deg selv, rød,

881
00:41:35,570 --> 00:41:36,740
gjenta deg selv.

882
00:41:36,740 --> 00:41:39,000
Du kan ikke bare gå hele
helt til høyre.

883
00:41:39,000 --> 00:41:41,200
Og som en digresjon, for å gjøre
tømme komprimering

884
00:41:41,200 --> 00:41:43,910
er overalt, hvis disse er
fire rammer fra en video-- deg

885
00:41:43,910 --> 00:41:45,890
kan huske at en film
eller video er vanligvis

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 er som en liten flip bok hvor du
bare se image, image, image, image,

888
00:41:50,410 --> 00:41:54,410
image bare super fort så det ser ut som
skuespillerne på skjermen beveger seg.

889
00:41:54,410 --> 00:41:57,130
Her er en humlen på
toppen av en haug med blomster.

890
00:41:57,130 --> 00:41:59,790
Og selv om det kan være slags
vanskelig å se ved første øyekast,

891
00:41:59,790 --> 00:42:04,020
det eneste som beveger seg i
denne filmen er bee.

892
00:42:04,020 --> 00:42:06,880
>> Hva er dum om lagring
video ukomprimert?

893
00:42:06,880 --> 00:42:11,420
Det er litt bortkastet å lagre video
som fire nesten identiske bilder som

894
00:42:11,420 --> 00:42:13,670
skiller seg bare i den utstrekning der bee er.

895
00:42:13,670 --> 00:42:16,280
Du kan kaste bort mest
av denne informasjonen

896
00:42:16,280 --> 00:42:20,190
og husk bare, for eksempel,
det første bildet og det siste bildet,

897
00:42:20,190 --> 00:42:22,180
nøkkelbilder hvis du har
hørt ordet,

898
00:42:22,180 --> 00:42:24,337
og bare lagre i
midten der bee er.

899
00:42:24,337 --> 00:42:26,170
Og du trenger ikke å
lagre alle de rosa,

900
00:42:26,170 --> 00:42:28,330
og det blå, og den
grønne verdier også.

901
00:42:28,330 --> 00:42:31,200
Så dette er å bare si at
Kompresjonen er overalt.

902
00:42:31,200 --> 00:42:34,900
Det er en teknikk vi bruker ofte
eller tar for gitt i disse dager.

903
00:42:34,900 --> 00:42:38,750
>> Men hvordan komprimere du teksten?

904
00:42:38,750 --> 00:42:40,450
Hvordan du går om å komprimere tekst på?

905
00:42:40,450 --> 00:42:45,410
Vel, hver av karakterene i
Ascii er én byte, eller åtte biter.

906
00:42:45,410 --> 00:42:47,360
Og det er slags dum, ikke sant?

907
00:42:47,360 --> 00:42:51,160
Fordi du sannsynligvis type A
og E og jeg og O og U mye

908
00:42:51,160 --> 00:42:55,270
oftere enn som W eller Q eller Z,
avhengig av hvilket språk

909
00:42:55,270 --> 00:42:56,610
du skriver sikkert.

910
00:42:56,610 --> 00:42:59,600
Og så hvorfor bruker vi
åtte biter for hver bokstav,

911
00:42:59,600 --> 00:43:02,040
inkludert minst
populære bokstaver, ikke sant?

912
00:43:02,040 --> 00:43:05,300
Hvorfor ikke bruke færre bits for
de super populære bokstaver,

913
00:43:05,300 --> 00:43:07,760
som E, de tingene du gjette
først i Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
og bruke flere biter for
de mindre populære bokstavene?

915
00:43:10,450 --> 00:43:10,950
Hvorfor?

916
00:43:10,950 --> 00:43:13,130
Fordi vi bare kommer til å
bruke dem sjeldnere.

917
00:43:13,130 --> 00:43:15,838
>> Vel, det viser seg at det har
vært forsøk gjort for å gjøre dette.

918
00:43:15,838 --> 00:43:18,630
Og hvis du husker fra klasse
skole eller videregående skole, morse.

919
00:43:18,630 --> 00:43:20,400
Morse har prikker
og streker som kan være

920
00:43:20,400 --> 00:43:24,270
sendes langs en wire som
lyder eller signaler av noe slag.

921
00:43:24,270 --> 00:43:25,930
Men morse er en super clean.

922
00:43:25,930 --> 00:43:29,010
Det er litt av en binær system i
at du har prikker eller streker.

923
00:43:29,010 --> 00:43:30,977
Men hvis du ser, for eksempel, to prikker.

924
00:43:30,977 --> 00:43:33,810
Eller hvis du tenker tilbake til operatøren
som går som pip, pip, pip,

925
00:43:33,810 --> 00:43:36,760
pip, treffer en liten trigger
som sender et signal,

926
00:43:36,760 --> 00:43:40,360
Hvis du, mottakeren, får to
prikker, hva meldingen du har fått?

927
00:43:40,360 --> 00:43:43,490
Helt vilkårlig.

928
00:43:43,490 --> 00:43:44,450
>> Jeg?

929
00:43:44,450 --> 00:43:45,060
Jeg?

930
00:43:45,060 --> 00:43:47,500
Eller hva om-- eller jeg?

931
00:43:47,500 --> 00:43:49,570
Kanskje var det bare to-E er rett?

932
00:43:49,570 --> 00:43:52,480
Så det er dette problemet
av decodability med Morse

933
00:43:52,480 --> 00:43:54,890
kode, hvorved mindre
person å sende deg meldingen

934
00:43:54,890 --> 00:43:59,510
faktisk tar en pause slik at du kan sortere på
se eller høre hullene mellom bokstavene,

935
00:43:59,510 --> 00:44:02,990
det er ikke tilstrekkelig bare å
sende en strøm av nuller og enere,

936
00:44:02,990 --> 00:44:05,610
eller prikker og streker,
fordi det er tvetydighet.

937
00:44:05,610 --> 00:44:08,640
E er et enkelt punkt, så hvis du
se to prikker eller høre to prikker,

938
00:44:08,640 --> 00:44:11,254
kanskje det er to E-eller kanskje det er en I.

939
00:44:11,254 --> 00:44:13,670
Så vi trenger et system som er en
litt mer avanserte enn som så.

940
00:44:13,670 --> 00:44:16,851
Så en mann som heter Huffman år
siden kom opp med akkurat dette.

941
00:44:16,851 --> 00:44:18,600
Så vi bare skal
å ta et raskt blikk

942
00:44:18,600 --> 00:44:20,114
hvor trærne er relevante for dette.

943
00:44:20,114 --> 00:44:22,530
Anta at dette er noen
dum meldingen du vil sende,

944
00:44:22,530 --> 00:44:26,342
sammensatt av bare A, B, C er D's og E er,
men det er mye redundans her.

945
00:44:26,342 --> 00:44:27,550
Det er ikke ment å være engelsk.

946
00:44:27,550 --> 00:44:28,341
Det er ikke kryptert.

947
00:44:28,341 --> 00:44:30,540
Det er bare en dum melding
med mye repetisjon.

948
00:44:30,540 --> 00:44:34,010
Så hvis du faktisk regne ut alle
A, B, C, i D's, og E er, her

949
00:44:34,010 --> 00:44:34,890
frekvensen.

950
00:44:34,890 --> 00:44:37,800
20% av bokstavene er
A, 45% av bokstavene

951
00:44:37,800 --> 00:44:39,660
er E 's, og tre andre frekvenser.

952
00:44:39,660 --> 00:44:41,960
Vi telles opp manuelt
og bare gjorde matte.

953
00:44:41,960 --> 00:44:44,579
>> Så det viser seg at
Huffman, for en tid siden,

954
00:44:44,579 --> 00:44:46,620
skjønte det, vet du
hva, hvis jeg begynner bygning

955
00:44:46,620 --> 00:44:51,172
et tre, eller skog av trær, om du vil,
som følger, kan jeg gjøre følgende.

956
00:44:51,172 --> 00:44:53,880
Jeg kommer til å gi en node til hver
av brevene som jeg bryr meg om

957
00:44:53,880 --> 00:44:55,530
og jeg kommer til å lagre
innsiden av at node

958
00:44:55,530 --> 00:44:58,610
frekvensene som et flyttall
verdi, eller du kan bruke det en N, også,

959
00:44:58,610 --> 00:45:00,210
men vi vil bare bruke en dupp her.

960
00:45:00,210 --> 00:45:03,100
Og algoritme som
foreslo han er at du

961
00:45:03,100 --> 00:45:07,210
ta denne skogen av enkelt node
trær, så super korte trær,

962
00:45:07,210 --> 00:45:11,920
og du begynner å koble dem med
nye grupper, nye foreldre, hvis du vil.

963
00:45:11,920 --> 00:45:16,150
Og du gjør dette ved å velge
minste to frekvenser samtidig.

964
00:45:16,150 --> 00:45:18,110
Så tok jeg 10% og 10%.

965
00:45:18,110 --> 00:45:19,090
Jeg oppretter en ny node.

966
00:45:19,090 --> 00:45:20,910
Og jeg kaller den nye noden 20%.

967
00:45:20,910 --> 00:45:22,750
>> Hvilke to noder jeg kombinere neste?

968
00:45:22,750 --> 00:45:23,810
Det er litt tvetydig.

969
00:45:23,810 --> 00:45:26,643
Så det er noen hjørne tilfeller til
vurdere, men å holde ting pen,

970
00:45:26,643 --> 00:45:29,300
Jeg kommer til å velge 20% -
Jeg nå ignorere barn.

971
00:45:29,300 --> 00:45:33,640
Jeg kommer til å velge 20% og
15% og tegne to nye kanter.

972
00:45:33,640 --> 00:45:35,624
Og nå som to noder
kan jeg logisk kombinere?

973
00:45:35,624 --> 00:45:38,540
Ignorer alle barna, alle de
barnebarn, bare se på røttene

974
00:45:38,540 --> 00:45:39,070
nå.

975
00:45:39,070 --> 00:45:42,220
Hvilke to noder ikke knytte jeg sammen?

976
00:45:42,220 --> 00:45:44,530
Punkt to og 0,35.

977
00:45:44,530 --> 00:45:45,890
Så la meg tegne to nye kanter.

978
00:45:45,890 --> 00:45:47,570
Og da har jeg bare fått én igjen.

979
00:45:47,570 --> 00:45:48,650
Så her er et tre.

980
00:45:48,650 --> 00:45:51,160
Og det er blitt trukket bevisst
å se hva slags pen,

981
00:45:51,160 --> 00:45:55,870
men merker at kantene har
også blitt merket null og en.

982
00:45:55,870 --> 00:45:59,510
Så alle venstrekantene er null
vilkårlig, men konsekvent.

983
00:45:59,510 --> 00:46:01,170
Alle de rette kantene er de.

984
00:46:01,170 --> 00:46:05,070
>> Og så hva Hoffman foreslått er,
Hvis du ønsker å representere en B,

985
00:46:05,070 --> 00:46:10,080
i stedet representerer antall 66 som
en Ascii som er åtte hele biter,

986
00:46:10,080 --> 00:46:13,360
vet du hva, bare butikken
mønsteret null, null, null,

987
00:46:13,360 --> 00:46:17,030
null, fordi det er den veien
fra min treet, Mr. Huffman treet,

988
00:46:17,030 --> 00:46:18,600
til bladet fra roten.

989
00:46:18,600 --> 00:46:20,970
Hvis du vil lagre en
E, derimot, ikke

990
00:46:20,970 --> 00:46:26,290
send åtte biter som representerer en E.
I stedet sender hva mønster av biter?

991
00:46:26,290 --> 00:46:26,890
En.

992
00:46:26,890 --> 00:46:30,410
Og hva er fint om dette er
at E er den mest populære brev,

993
00:46:30,410 --> 00:46:32,340
og du bruker
kortest kode for det.

994
00:46:32,340 --> 00:46:34,090
Den nest mest populære
brev ser ut som det

995
00:46:34,090 --> 00:46:37,380
var A. Og så hvor mange biter
gjorde han foreslår å bruke for det?

996
00:46:37,380 --> 00:46:38,270
Zero, en.

997
00:46:38,270 --> 00:46:41,060
>> Og fordi det er iverksatt
da dette treet, for nå

998
00:46:41,060 --> 00:46:43,350
la meg fastsette det
ingen tvetydighet som i Morse

999
00:46:43,350 --> 00:46:46,090
kode, fordi alle
bokstavene du bryr deg om

1000
00:46:46,090 --> 00:46:48,780
er ved enden av disse kanter.

1001
00:46:48,780 --> 00:46:50,580
Så det er bare ett
anvendelse av et tre.

1002
00:46:50,580 --> 00:46:52,538
Dette er-- og jeg skal vinke
min hånd på hvordan du

1003
00:46:52,538 --> 00:46:55,570
kan implementere dette som en C-struktur.

1004
00:46:55,570 --> 00:46:58,260
Vi trenger bare å kombinere
et symbol, som en char,

1005
00:46:58,260 --> 00:46:59,910
og frekvensen i venstre og høyre.

1006
00:46:59,910 --> 00:47:02,510
Men la oss se på to-
endelige eksempler som du vil

1007
00:47:02,510 --> 00:47:06,070
bli ganske kjent med etter
quiz null i oppgavesettet fem.

1008
00:47:06,070 --> 00:47:09,210
>> Så det er datastrukturen
kjent som en hash table.

1009
00:47:09,210 --> 00:47:12,247
Og en hash table er slags
avkjøle i at den har bøtter.

1010
00:47:12,247 --> 00:47:14,830
Og antar at det er fire bøtter
her, bare fire mellomrom.

1011
00:47:14,830 --> 00:47:20,830
Her er en kortstokk, og her er
klubb, spade, klubb, diamanter, klubb,

1012
00:47:20,830 --> 00:47:25,960
diamanter, klubb, diamanter,
clubs-- slik dette er tilfeldig.

1013
00:47:25,960 --> 00:47:30,330
Hjerter, hearts-- så jeg er
bucketizing alle inngangene her.

1014
00:47:30,330 --> 00:47:32,430
Og en hash table behov
å se på dine innspill,

1015
00:47:32,430 --> 00:47:34,850
og deretter sette den i en viss
plassere basert på hva du ser.

1016
00:47:34,850 --> 00:47:35,600
Det er en algoritme.

1017
00:47:35,600 --> 00:47:37,980
Og jeg var bruker en super
enkel visuell algoritme.

1018
00:47:37,980 --> 00:47:40,030
Den vanskeligste delen av som var
huske hva bildene var.

1019
00:47:40,030 --> 00:47:41,590
Og så er det fire totalt ting.

1020
00:47:41,590 --> 00:47:45,440
>> Nå stabler vokste, som
er en bevisst utforming ting her.

1021
00:47:45,440 --> 00:47:46,540
Men hva annet kan jeg gjøre?

1022
00:47:46,540 --> 00:47:49,080
Så egentlig her har vi en
haug med gamle skoleeksamen bøker.

1023
00:47:49,080 --> 00:47:51,240
Anta at en haug med
elevenes navn er på her.

1024
00:47:51,240 --> 00:47:52,570
Her er en større hash table.

1025
00:47:52,570 --> 00:47:54,867
I stedet for fire bøtter,
Jeg har, la oss si 26.

1026
00:47:54,867 --> 00:47:57,950
Og vi ønsker ikke å gå låne 26
ting fra utsiden [? Annenberg?], Så

1027
00:47:57,950 --> 00:48:00,289
her er fem som representerer
A til Z. Og hvis jeg

1028
00:48:00,289 --> 00:48:03,580
se en student med navn som starter med A,
Jeg kommer til å sette hans eller hennes quiz der.

1029
00:48:03,580 --> 00:48:08,850
Hvis noen begynner med C, der borte,
A-- faktisk, ønsker ikke å gjøre det.

1030
00:48:08,850 --> 00:48:10,060
B går over her.

1031
00:48:10,060 --> 00:48:13,390
Så jeg har fått A og B og C. Og
Nå her er en annen student.

1032
00:48:13,390 --> 00:48:16,212
Men hvis dette hash table er
implementert med en matrise,

1033
00:48:16,212 --> 00:48:17,920
Jeg er litt skrudd
på dette punktet, ikke sant?

1034
00:48:17,920 --> 00:48:19,510
Jeg slags behov for å sette dette et sted.

1035
00:48:19,510 --> 00:48:24,380
>> Så en måte jeg kan løse dette er, alt
rett, er en travel, B er opptatt, C er opptatt.

1036
00:48:24,380 --> 00:48:28,880
Jeg kommer til å sette ham i D. Så på
først må jeg tilfeldig umiddelbar tilgang

1037
00:48:28,880 --> 00:48:31,064
til hver av bøtter for studentene.

1038
00:48:31,064 --> 00:48:33,230
Men nå er det slags baklegns
til noe lineær,

1039
00:48:33,230 --> 00:48:36,750
fordi hvis jeg ønsker å søke etter en person
med navn som starter med A, jeg sjekke her.

1040
00:48:36,750 --> 00:48:38,854
Men hvis dette ikke er A
student jeg leter etter,

1041
00:48:38,854 --> 00:48:41,520
Jeg slags må begynne å sjekke
bøtter, fordi det jeg gjorde

1042
00:48:41,520 --> 00:48:44,530
var liksom lineært
undersøke datastrukturen.

1043
00:48:44,530 --> 00:48:47,710
En dum måte å si bare se
for den første tilgjengelige åpning,

1044
00:48:47,710 --> 00:48:51,850
og satt som en plan B, så å si,
eller plan D i dette tilfellet verdien

1045
00:48:51,850 --> 00:48:53,340
i at plasseringen i stedet.

1046
00:48:53,340 --> 00:48:56,470
Dette er bare slik at hvis du har
fikk 26 steder og ingen studenter

1047
00:48:56,470 --> 00:49:00,600
med navnet Q eller Z, eller noe sånt
at minst du bruker plassen.

1048
00:49:00,600 --> 00:49:03,140
>> Men vi har allerede sett mer
smarte løsninger her, ikke sant?

1049
00:49:03,140 --> 00:49:04,870
Hva ville du gjøre i stedet
hvis du har en kollisjon?

1050
00:49:04,870 --> 00:49:06,670
Hvis to personer har
navnet A, hva ville

1051
00:49:06,670 --> 00:49:09,160
har vært en smartere eller mer
intuitiv løsning enn bare

1052
00:49:09,160 --> 00:49:12,840
Sette en der D er ment å være?

1053
00:49:12,840 --> 00:49:14,810
Hvorfor kan jeg ikke bare gå
utenfor [? Annenberg?]

1054
00:49:14,810 --> 00:49:19,960
som malloc, en annen node, sette det
her, og deretter sette at en student her.

1055
00:49:19,960 --> 00:49:22,120
Slik at jeg i hovedsak har
noen form for en matrise,

1056
00:49:22,120 --> 00:49:25,590
eller kanskje mer elegant som vi er
begynner å se en lenket liste.

1057
00:49:25,590 --> 00:49:29,520
>> Og så en hash table er en struktur
som kan se ut akkurat som dette,

1058
00:49:29,520 --> 00:49:33,900
men mer smart, du noe som heter
separat kjeding, der en hash table

1059
00:49:33,900 --> 00:49:38,340
ganske enkelt er en matrise, idet hver av
og hvor elementene ikke er et tall,

1060
00:49:38,340 --> 00:49:40,470
er i seg selv en lenket liste.

1061
00:49:40,470 --> 00:49:45,080
Slik at du får super rask tilgang
bestemmer hvor du skal hash verdien til.

1062
00:49:45,080 --> 00:49:48,059
Mye som med kort eksempel
Jeg gjorde super raske beslutninger.

1063
00:49:48,059 --> 00:49:49,600
Hjerter går her, diamanter går her.

1064
00:49:49,600 --> 00:49:52,180
Samme her, går A her,
D går her, B går her.

1065
00:49:52,180 --> 00:49:55,740
Så super rask look-ups, og hvis
du tilfeldigvis støter på en sak

1066
00:49:55,740 --> 00:49:59,429
hvor du har fått kollisjoner, to
mennesker med samme navn, vel da

1067
00:49:59,429 --> 00:50:00,970
du bare begynne å koble dem sammen.

1068
00:50:00,970 --> 00:50:03,900
Og kanskje du holde dem sortert
alfabetisk, kanskje du ikke gjør det.

1069
00:50:03,900 --> 00:50:05,900
Men minst nå har vi dynamikk.

1070
00:50:05,900 --> 00:50:10,250
Så på den ene siden har vi superrask
konstant tid, og hva slags lineær tid

1071
00:50:10,250 --> 00:50:14,110
involvert hvis disse lenkede lister
begynner å bli litt lang.

1072
00:50:14,110 --> 00:50:16,880
>> Så denne typen en dum,
nerdete spøk år siden.

1073
00:50:16,880 --> 00:50:19,590
På CS50 hack-a-thon,
når elevene sjekke inn,

1074
00:50:19,590 --> 00:50:22,040
noen TF eller CA hvert år
synes det er morsomt å sette opp

1075
00:50:22,040 --> 00:50:27,772
et skilt som dette, hvor det bare
betyr at hvis navnet ditt starter med en A,

1076
00:50:27,772 --> 00:50:28,870
gå på denne måten.

1077
00:50:28,870 --> 00:50:31,110
Hvis navnet ditt starter
med en B, gå dette-- OK,

1078
00:50:31,110 --> 00:50:33,290
det er morsomt kanskje senere i semesteret.

1079
00:50:33,290 --> 00:50:36,420
Men det er en annen
måte å gjøre dette, også.

1080
00:50:36,420 --> 00:50:37,410
Komme tilbake til det.

1081
00:50:37,410 --> 00:50:38,600
>> Så det er denne strukturen.

1082
00:50:38,600 --> 00:50:40,420
Og dette er vår siste
struktur for i dag,

1083
00:50:40,420 --> 00:50:42,400
som er noe som kalles en trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, hvor det av en eller annen grunn er korte
for gjenfinning, men det heter trie.

1085
00:50:47,140 --> 00:50:51,389
Så en trie er et annet interessant
amalgam av mange av disse ideene.

1086
00:50:51,389 --> 00:50:52,930
Det er et tre, som vi har sett før.

1087
00:50:52,930 --> 00:50:54,180
Det er ikke et binært søketre.

1088
00:50:54,180 --> 00:50:58,410
Det er et tre med en rekke barn,
men hver av barna i en trie

1089
00:50:58,410 --> 00:51:00,090
er en matrise.

1090
00:51:00,090 --> 00:51:04,790
En rekke størrelser, sier, 26 eller kanskje 27
Hvis du ønsker å støtte bindestreksnavn

1091
00:51:04,790 --> 00:51:06,790
eller apostrofer i folks navn.

1092
00:51:06,790 --> 00:51:08,280
>> Og så dette er en datastruktur.

1093
00:51:08,280 --> 00:51:10,290
Og hvis du ser fra toppen
til bunn, som hvis du

1094
00:51:10,290 --> 00:51:13,710
ser på toppen node der, M, er
peker til den nest siste tingen der,

1095
00:51:13,710 --> 00:51:17,665
som deretter A, X, W, E, L, L. Dette er
bare en datastruktur som vilkårlig

1096
00:51:17,665 --> 00:51:19,120
er lagring av folks navn.

1097
00:51:19,120 --> 00:51:25,720
Og Maxwell er lagret ved bare å følge
en sti av array til array til array.

1098
00:51:25,720 --> 00:51:30,050
Men hva er fantastisk om en trie er
at mens en lenket liste, og selv

1099
00:51:30,050 --> 00:51:34,520
en matrise, det beste vi noen gang har fått er
lineær tid eller logaritmisk tid på å lete

1100
00:51:34,520 --> 00:51:35,600
noen opp.

1101
00:51:35,600 --> 00:51:40,530
I denne datastruktur av et trie, hvis
min datastruktur har ett navn i det

1102
00:51:40,530 --> 00:51:43,720
og jeg ser for Maxwell, jeg er
kommer til å finne ham ganske raskt.

1103
00:51:43,720 --> 00:51:47,910
Jeg bare ser for M-A-X-W-E-L-L. Om
denne datastrukturen, derimot,

1104
00:51:47,910 --> 00:51:51,830
Hvis N er en million, hvis det er en
million navnene i denne datastruktur,

1105
00:51:51,830 --> 00:51:57,100
Maxwell er fortsatt kommer til å være
synlig etter bare M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
trinn.

1107
00:51:58,090 --> 00:52:01,276
Og David-- D-A-V-I-D-trinn.

1108
00:52:01,276 --> 00:52:03,400
Med andre ord, ved å bygge
en datastruktur som er

1109
00:52:03,400 --> 00:52:07,240
har alle disse matriser, som alle
seg støtte random access,

1110
00:52:07,240 --> 00:52:11,090
Jeg kan begynne å se opp folks
navngi ved hjelp av en mengde tid det er

1111
00:52:11,090 --> 00:52:14,340
proporsjonal ikke antallet
ting i datastrukturen,

1112
00:52:14,340 --> 00:52:16,330
som en million eksisterende navnene.

1113
00:52:16,330 --> 00:52:20,135
Tiden det tar meg å finne
M-A-X-W-E-L-L i denne datastruktur er

1114
00:52:20,135 --> 00:52:22,260
proporsjonal ikke i
størrelsen av datastrukturen,

1115
00:52:22,260 --> 00:52:25,930
men til lengden av navnet.

1116
00:52:25,930 --> 00:52:28,440
Og realistisk det
Navnene vi leter opp

1117
00:52:28,440 --> 00:52:29,970
aldri kommer til å bli gal lenge.

1118
00:52:29,970 --> 00:52:32,600
Kanskje noen har en 10 tegn
navn, 20 tegn navn.

1119
00:52:32,600 --> 00:52:33,900
Det er absolutt begrenset, ikke sant?

1120
00:52:33,900 --> 00:52:37,110
Det er et menneske på jorden som
har den lengste mulige navnet

1121
00:52:37,110 --> 00:52:39,920
men det navnet er en konstant
verdi lengde, ikke sant?

1122
00:52:39,920 --> 00:52:41,980
Det varierer ikke i noen forstand.

1123
00:52:41,980 --> 00:52:45,090
Så på denne måten, har vi
oppnås en datastruktur

1124
00:52:45,090 --> 00:52:47,800
som er konstant tids look-up.

1125
00:52:47,800 --> 00:52:50,670
Det tar en rekke tiltak
avhengig av lengden av tilførselen

1126
00:52:50,670 --> 00:52:54,250
men ikke antallet navnet
i datastrukturen.

1127
00:52:54,250 --> 00:52:58,700
Så hvis vi dobler antall navn
neste år fra en milliard til to milliarder kroner,

1128
00:52:58,700 --> 00:53:03,720
funn Maxwell kommer til å ta
det samme antall av syv skritt

1129
00:53:03,720 --> 00:53:04,650
for å finne ham.

1130
00:53:04,650 --> 00:53:08,810
Og så vi synes å ha oppnådd
vår hellige gral av kjøretiden.

1131
00:53:08,810 --> 00:53:10,860
>> Så et par korte beskjeder.

1132
00:53:10,860 --> 00:53:11,850
Quiz null kommer opp.

1133
00:53:11,850 --> 00:53:14,600
Mer om det på kurset hjemmeside
i løpet av de neste par dagene.

1134
00:53:14,600 --> 00:53:17,120
Mandagens lecture-- det er en ferie
her ved Harvard på mandag.

1135
00:53:17,120 --> 00:53:18,850
Det er ikke i New Haven,
så vi tar klassen

1136
00:53:18,850 --> 00:53:20,310
til New Haven for forelesning på mandag.

1137
00:53:20,310 --> 00:53:22,550
Alt vil bli filmet
og streamet live som vanlig,

1138
00:53:22,550 --> 00:53:24,900
men la oss avslutte i dag
med en 30 sekunders klipp

1139
00:53:24,900 --> 00:53:26,910
kalt "Deep Thoughts"
av Daven Farnham, som

1140
00:53:26,910 --> 00:53:30,850
ble inspirert fjor av lørdag
Night Lives "Deep Thoughts"

1141
00:53:30,850 --> 00:53:35,700
av Jack Handy, som
skal nå være fornuftig.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Og nå, "Deep
Tanker "av Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash table.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Greit, det er det for nå.

1147
00:53:47,660 --> 00:53:48,805
Vi sees neste uke.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: For å se den i aksjon.

1150
00:53:56,680 --> 00:53:58,304
Så la oss ta en titt på det akkurat nå.

1151
00:53:58,304 --> 00:53:59,890
Så her har vi en usortert array.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, kan du gå videre og starte på nytt
dette for bare ett sekund, takk.

1153
00:54:04,860 --> 00:54:08,562
Greit, er kameraene rulle, så
handling når du er klar, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Greit, så hva vi
har her er en usortert array.

1155
00:54:11,020 --> 00:54:13,960
Og jeg har farget alle elementene
rødt for å angi at det er faktisk

1156
00:54:13,960 --> 00:54:14,460
usortert.

1157
00:54:14,460 --> 00:54:17,960
Så husker at det første vi gjør
er vi sortere venstre halvdel av tabellen.

1158
00:54:17,960 --> 00:54:20,630
Da vi sortere riktig
halvparten av tabellen.

1159
00:54:20,630 --> 00:54:22,830
Og ya-da, ya-da, ya-da,
vi flette dem sammen.

1160
00:54:22,830 --> 00:54:24,520
Og vi har en helt sortert array.

1161
00:54:24,520 --> 00:54:25,360
Så det er sånn flette slags fungerer.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, whoa, whoa,
klippe, klippe, klippe, klippe.

1163
00:54:27,109 --> 00:54:30,130
Doug, kan du ikke bare ya-da, ya-da,
ya-da, din vei gjennom merge sort.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Jeg bare gjorde det.

1165
00:54:31,970 --> 00:54:32,832
Det er i orden.

1166
00:54:32,832 --> 00:54:33,540
Vi er godt å gå.

1167
00:54:33,540 --> 00:54:34,760
La oss bare holde rulle.

1168
00:54:34,760 --> 00:54:35,380
Så uansett,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Du må forklare
den mer fullstendig enn det.

1170
00:54:37,800 --> 00:54:39,999
Det er bare ikke nok.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, gjør vi ikke
trenger å gå tilbake til en.

1172
00:54:41,790 --> 00:54:42,350
Det er i orden.

1173
00:54:42,350 --> 00:54:45,690
Så uansett, hvis vi fortsetter med merge--
Ian, vi er i midten av filming.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Jeg vet.

1175
00:54:46,612 --> 00:54:49,320
Og vi kan ikke bare ya-da, ya-da,
ya-da, gjennom hele prosessen.

1176
00:54:49,320 --> 00:54:52,200
Du må forklare hvordan
to sidene bli slått sammen.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Men vi har allerede
forklarte hvordan de to sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Du har nettopp vist
dem et flette array.

1179
00:54:55,321 --> 00:54:56,486
DOUG: De kjenner prosessen.

1180
00:54:56,486 --> 00:54:57,172
De er fine.

1181
00:54:57,172 --> 00:54:58,380
Vi har gått over det ti ganger.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Du bare hoppet rett over den.

1183
00:55:00,330 --> 00:55:03,360
Vi går tilbake til en, du
kan ikke du ya-da, ya-da over det.

1184
00:55:03,360 --> 00:55:05,480
Greit, tilbake til en.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Jeg må gå tilbake
gjennom alle lysbildene?

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 er som for sjette gang, Ian.

1189
00:55:13,004 --> 00:55:13,940
Det er i orden.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: All right.

1191
00:55:15,200 --> 00:55:16,590
Er du klar?

1192
00:55:16,590 --> 00:55:17,400
Flott.

1193
00:55:17,400 --> 00:55:18,950
Handling.