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

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Oke, dus dit is
CS50 Dit is het einde van de week vijf.

3
00:00:15,860 --> 00:00:19,220
En herinneren dat laatste keer dat we
begon te kijken naar de liefhebber gegevens

4
00:00:19,220 --> 00:00:22,310
structuren die begon op te lossen
problemen, die begon te voeren

5
00:00:22,310 --> 00:00:25,640
nieuwe problemen, maar de sleutel tot deze
was het soort threading dat we

6
00:00:25,640 --> 00:00:27,940
begonnen zijn van knooppunt naar knooppunt.

7
00:00:27,940 --> 00:00:30,085
Dus dit is natuurlijk
een enkelvoudig gelinkte lijst.

8
00:00:30,085 --> 00:00:31,960
En afzonderlijk verbonden,
Ik bedoel, er is slechts één

9
00:00:31,960 --> 00:00:33,380
draad tussen elk van deze knooppunten.

10
00:00:33,380 --> 00:00:35,890
Blijkt dat u kunt liefhebber doen
dingen zoals dubbel gelinkte lijsten

11
00:00:35,890 --> 00:00:38,470
waarbij je een pijl
gaan in beide richtingen, waarbij

12
00:00:38,470 --> 00:00:40,320
kunnen helpen met bepaalde efficiëntie.

13
00:00:40,320 --> 00:00:42,000
Maar dit het probleem opgelost?

14
00:00:42,000 --> 00:00:43,500
Welk probleem deed dit op te lossen?

15
00:00:43,500 --> 00:00:46,620
Waarom hebben we de zorg op maandag?

16
00:00:46,620 --> 00:00:49,820
Waarom, in theorie, hebben we de zorg op maandag?

17
00:00:49,820 --> 00:00:50,630
Wat doet het?

18
00:00:50,630 --> 00:00:51,950
>> PUBLIEK: We kunnen dynamisch resize.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, dus we kunnen
dynamisch resize.

20
00:00:53,740 --> 00:00:54,710
Goed gedaan jullie beiden.

21
00:00:54,710 --> 00:00:57,560
Dus je kunt dynamisch dit formaat
datastructuur, terwijl een array,

22
00:00:57,560 --> 00:01:00,760
recall, moet u een weten
priori hoeveel ruimte je wilt

23
00:01:00,760 --> 00:01:03,870
en als je een beetje meer nodig
ruimte, je bent soort van geluk.

24
00:01:03,870 --> 00:01:05,560
Je moet een hele nieuwe serie te maken.

25
00:01:05,560 --> 00:01:07,893
Je moet al beweeg je
gegevens van de ene naar de andere,

26
00:01:07,893 --> 00:01:10,600
uiteindelijk bevrijden van de oude serie
als je kunt, en ga dan verder.

27
00:01:10,600 --> 00:01:13,891
Die voelt gewoon erg duur en zeer
inefficiënt, en inderdaad kan worden.

28
00:01:13,891 --> 00:01:14,890
Maar dit is niet alles goed.

29
00:01:14,890 --> 00:01:18,180
We betalen een prijs, wat was één
van de meer voor de hand liggende prijzen wij

30
00:01:18,180 --> 00:01:20,550
betalen met behulp van een gekoppelde lijst?

31
00:01:20,550 --> 00:01:22,825
>> PUBLIEK: We moeten gebruiken
dubbele ruimte voor een ieder.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Ja, dus we moeten
ten minste tweemaal zoveel ruimte.

33
00:01:25,200 --> 00:01:27,700
In feite, realiseerde ik me van deze foto
zelfs een beetje misleidend,

34
00:01:27,700 --> 00:01:32,200
want op CS50 IDE in een veel moderne
computers, een pointer of een adres

35
00:01:32,200 --> 00:01:33,700
is in feite vier bytes.

36
00:01:33,700 --> 00:01:36,090
Het is heel vaak zijn deze
dagen acht bytes die

37
00:01:36,090 --> 00:01:38,530
: het onderste meest
rechthoeken er in werkelijkheid

38
00:01:38,530 --> 00:01:40,900
zijn een soort van twee keer zo
groot als wat ik heb getekend,

39
00:01:40,900 --> 00:01:44,409
wat betekent dat je gebruikt drie keer zo
zoveel ruimte als we anders zouden kunnen hebben.

40
00:01:44,409 --> 00:01:46,700
Nu op hetzelfde moment, we zijn
nog steeds in gesprek bytes, toch?

41
00:01:46,700 --> 00:01:49,140
We zijn niet per se praten
megabytes of gigabytes,

42
00:01:49,140 --> 00:01:51,000
tenzij deze gegevens structuren te groot.

43
00:01:51,000 --> 00:01:54,510
>> En dus vandaag beginnen we te overwegen
hoe wij gegevens kunnen verkennen

44
00:01:54,510 --> 00:01:57,310
efficiënter als in
feite de gegevens wordt groter.

45
00:01:57,310 --> 00:02:00,360
Maar laten we proberen om canonicalize
de activiteiten eerste

46
00:02:00,360 --> 00:02:02,460
dat je kunt doen op deze
soorten gegevens structuren.

47
00:02:02,460 --> 00:02:04,790
Dus iets als een gekoppelde
lijst algemeen ondersteunt

48
00:02:04,790 --> 00:02:07,514
operaties willen verwijderen,
invoegen en zoeken.

49
00:02:07,514 --> 00:02:08,639
En wat moet ik daarmee?

50
00:02:08,639 --> 00:02:11,222
Dat betekent gewoon dat meestal,
als mensen met behulp van gelinkte lijst,

51
00:02:11,222 --> 00:02:14,287
zij of iemand anders heeft geïmplementeerd
functies zoals verwijderen, invoegen,

52
00:02:14,287 --> 00:02:16,120
en zoeken, zodat u kunt
iets wat eigenlijk doen

53
00:02:16,120 --> 00:02:18,030
nuttig bij de gegevensstructuur.

54
00:02:18,030 --> 00:02:20,760
Dus laten we eens een snelle blik
hoe we kunnen implementeren

55
00:02:20,760 --> 00:02:24,530
een code voor een gekoppelde lijst als volgt.

56
00:02:24,530 --> 00:02:27,885
>> Dus dit is slechts enkele C-code,
zelfs niet een compleet programma

57
00:02:27,885 --> 00:02:29,260
dat ik echt snel opgezweept.

58
00:02:29,260 --> 00:02:32,300
Het is niet online in de distributie
code, omdat het niet kan draaien.

59
00:02:32,300 --> 00:02:33,790
Maar let ik heb net
met een reactie zei,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, er is iets
daar, dot dot dot, daar iets.

61
00:02:36,130 --> 00:02:38,410
En laten we gewoon kijken naar
wat de sappige delen zijn.

62
00:02:38,410 --> 00:02:40,790
Dus op lijn drie,
herinneren dat dit is nu

63
00:02:40,790 --> 00:02:45,960
we voorgesteld waarbij een knooppunt laatste
tijd zo'n rechthoekige objecten.

64
00:02:45,960 --> 00:02:48,790
Het heeft een int dat wij N zullen noemen,
maar we konden het iets noemen,

65
00:02:48,790 --> 00:02:51,920
en riep toen een struct knooppunt ster naast.

66
00:02:51,920 --> 00:02:55,520
En alleen maar om duidelijk te zijn, dat de tweede
regel op regel zes, wat is dat?

67
00:02:55,520 --> 00:02:57,930
Wat doet het voor ons?

68
00:02:57,930 --> 00:03:01,044
Want het ziet er zeker meer
cryptisch dan onze gebruikelijke variabelen.

69
00:03:01,044 --> 00:03:02,740
>> Publiek: Het maakt het bewegen over één.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Het maakt het bewegen over één.

71
00:03:04,650 --> 00:03:08,580
En om precies te zijn,
zal het adres op te slaan

72
00:03:08,580 --> 00:03:11,582
van het knooppunt dat bedoeld is
semantisch ernaast, toch?

73
00:03:11,582 --> 00:03:13,540
Dus het is niet van plan om
noodzakelijkerwijs bewegen iets.

74
00:03:13,540 --> 00:03:15,290
Het gaat gewoon om
opslaan van een waarde, die

75
00:03:15,290 --> 00:03:17,170
naar het adres
van een andere node

76
00:03:17,170 --> 00:03:20,810
en dat is waarom we hebben gezegd struct
knooppunt ster, de ster duidt

77
00:03:20,810 --> 00:03:22,370
een pointer of een adres.

78
00:03:22,370 --> 00:03:26,390
OK, dus nu als je ervan uitgaat dat we
Deze N beschikbaar voor ons, en laten

79
00:03:26,390 --> 00:03:29,490
veronderstellen dat iemand anders
ingevoegd een heleboel getallen

80
00:03:29,490 --> 00:03:30,400
in een gekoppelde lijst.

81
00:03:30,400 --> 00:03:35,640
En dat gekoppelde lijst is
gewezen op een bepaald punt

82
00:03:35,640 --> 00:03:39,040
een variabele genaamd lijst die is
doorgegeven hier als een parameter,

83
00:03:39,040 --> 00:03:43,120
Hoe ga ik over lijn
14 zoekresultaten implementeren?

84
00:03:43,120 --> 00:03:45,990
Met andere woorden, als ik ben de uitvoering
functie waarvan het doel in het leven

85
00:03:45,990 --> 00:03:48,889
is naar een int en vervolgens het nemen
begin van een gekoppelde lijst,

86
00:03:48,889 --> 00:03:50,430
dat is een wijzer naar de gekoppelde lijst.

87
00:03:50,430 --> 00:03:52,992
Net als de eerste, die ik denk dat David
was onze vrijwilligers op maandag,

88
00:03:52,992 --> 00:03:54,700
hij wees naar
de hele gelinkte lijst,

89
00:03:54,700 --> 00:03:57,820
het is alsof we passeren
David in onze argumentatie hier.

90
00:03:57,820 --> 00:03:59,990
Hoe kunnen we gaan over het doorkruisen van dit overzicht?

91
00:03:59,990 --> 00:04:04,640
Nou, het blijkt dat, hoewel
pointers zijn nu relatief nieuw voor ons,

92
00:04:04,640 --> 00:04:07,010
we kunnen deze relatief doen
onomwonden.

93
00:04:07,010 --> 00:04:09,500
>> Ik ga om te gaan en
verklaren een tijdelijke variabele die

94
00:04:09,500 --> 00:04:12,364
volgens afspraak wordt gewoon
wijzer te worden genoemd, of PTR,

95
00:04:12,364 --> 00:04:14,030
maar je kon alles wat je wilt bellen.

96
00:04:14,030 --> 00:04:16,470
En ik ga initialiseren
aan het begin van de lijst.

97
00:04:16,470 --> 00:04:20,050
Dus je kunt soort denken van deze
als ik de leraar de andere dag,

98
00:04:20,050 --> 00:04:23,580
soort wijzend op iemand
onder onze mensen als vrijwilliger.

99
00:04:23,580 --> 00:04:26,470
Dus ik ben een tijdelijke variabele die is
gewoon te wijzen op hetzelfde

100
00:04:26,470 --> 00:04:31,390
dat onze toevallig genoemd
vrijwilliger David werd ook gewezen.

101
00:04:31,390 --> 00:04:35,440
Nu, terwijl aanwijzer
niet ongeldig, omdat recall

102
00:04:35,440 --> 00:04:40,350
dat null is een aantal speciale sentinel waarde
het markeert het einde van de lijst,

103
00:04:40,350 --> 00:04:44,280
dus terwijl ik niet te wijzen op de
grond als onze laatste vrijwilliger

104
00:04:44,280 --> 00:04:47,190
was, laten we gaan vooruit
en doe het volgende.

105
00:04:47,190 --> 00:04:51,820
Als pointer-- en nu ik soort van wil
om te doen wat we deden met de student

106
00:04:51,820 --> 00:04:57,410
structure-- als wijzer stip
equals-- eerder, als wijzer dot N gelijk

107
00:04:57,410 --> 00:05:02,290
gelijk is aan de variabele N, de
argument dat is doorgegeven in,

108
00:05:02,290 --> 00:05:05,370
dan wil ik gaan
en zeggen return true.

109
00:05:05,370 --> 00:05:11,020
Ik heb het nummer N binnenkant van gevonden
één van de knooppunten van mijn gekoppelde lijst.

110
00:05:11,020 --> 00:05:13,500
Maar de dot niet meer
werkt in deze context

111
00:05:13,500 --> 00:05:17,260
omdat wijzer, PTR, is
inderdaad een pointer, een adres,

112
00:05:17,260 --> 00:05:20,632
we eigenlijk kunnen heerlijk
Gebruik tot slot een stuk van de syntaxis

113
00:05:20,632 --> 00:05:22,590
dat soort merken
intuïtief gevoel en eigenlijk

114
00:05:22,590 --> 00:05:27,870
Gebruik een pijl here, waardoor gaan van
dat adres aan de integer daar in.

115
00:05:27,870 --> 00:05:30,160
Dus het is zeer vergelijkbaar in
geest van de puntoperator,

116
00:05:30,160 --> 00:05:33,860
maar omdat pointer geen pointer
en niet een echte structuur zelf,

117
00:05:33,860 --> 00:05:35,380
we gebruiken alleen de pijl.

118
00:05:35,380 --> 00:05:40,620
>> Als het huidige knooppunt I, de
tijdelijke variabele, ben wijzend op

119
00:05:40,620 --> 00:05:43,060
is niet N, wat wil ik doen?

120
00:05:43,060 --> 00:05:45,910
Nou, met mijn menselijke vrijwilligers
dat we hier de andere dag,

121
00:05:45,910 --> 00:05:49,710
als mijn eerste mens is niet degene die ik
willen, en misschien de tweede mens is niet

122
00:05:49,710 --> 00:05:52,660
degene die ik wil, en de derde, ik
moeten fysiek in beweging te houden.

123
00:05:52,660 --> 00:05:54,690
Net als hoe ik stap door een lijst?

124
00:05:54,690 --> 00:05:57,470
Toen hadden we een array u,
net deed alsof ik plus plus.

125
00:05:57,470 --> 00:06:03,660
Maar in dit geval volstaat
doen wijzer, krijgt, wijzer, naast.

126
00:06:03,660 --> 00:06:07,580
Met andere woorden, het volgende veld
is net als alle linker handen

127
00:06:07,580 --> 00:06:10,880
dat onze menselijke vrijwilligers op maandag
werden gebruikt om te wijzen op een ander knooppunt.

128
00:06:10,880 --> 00:06:12,890
Dat waren hun volgende buren.

129
00:06:12,890 --> 00:06:17,060
>> Dus als ik wil om door deze lijst,
Ik kan niet zomaar doen ik plus plus meer,

130
00:06:17,060 --> 00:06:20,120
Ik heb in plaats daarvan te zeggen
Ik, wijzer, gaat

131
00:06:20,120 --> 00:06:24,650
evenaren ongeacht het volgende veld,
het volgende veld is het volgende veld,

132
00:06:24,650 --> 00:06:28,350
na al die linker handen
dat we op het podium pointing

133
00:06:28,350 --> 00:06:30,000
enkele opeenvolgende waarden.

134
00:06:30,000 --> 00:06:32,590
En als ik via
dat hele iteratie,

135
00:06:32,590 --> 00:06:39,330
en tot slot, ik raakte null niet hebben
gevonden N nog, ik heb net return false.

136
00:06:39,330 --> 00:06:44,100
Dus nogmaals, alles wat we hier doen,
zoals in de foto een moment geleden,

137
00:06:44,100 --> 00:06:47,840
begint door te wijzen op de
begin van de lijst vermoedelijk.

138
00:06:47,840 --> 00:06:50,970
En dan heb ik te controleren, is de waarde
Ik ben op zoek naar die gelijk is aan negen?

139
00:06:50,970 --> 00:06:52,650
Als dat zo is, ik terug waar en ik ben klaar.

140
00:06:52,650 --> 00:06:56,450
Zo niet, ik mijn hand te werken,
AKA pointer te wijzen

141
00:06:56,450 --> 00:06:59,540
op de locatie van de volgende pijl's en
dan is de locatie van het volgende pijl's,

142
00:06:59,540 --> 00:07:00,480
en de volgende.

143
00:07:00,480 --> 00:07:03,770
Ik ben gewoon wandelen door deze array.

144
00:07:03,770 --> 00:07:06,010
>> Dus nogmaals, who cares?

145
00:07:06,010 --> 00:07:07,861
Zoals wat is dit ingrediënt voor?

146
00:07:07,861 --> 00:07:10,360
Nou, herinneren dat we geïntroduceerd
het begrip van een stapel, die

147
00:07:10,360 --> 00:07:15,400
is een abstracte data typen, voor zover het
geen C ding, het is niet een CS50 ding,

148
00:07:15,400 --> 00:07:19,430
het is een abstract idee, dit idee van
stapelen dingen bovenop elkaar

149
00:07:19,430 --> 00:07:21,820
dat kan worden geïmplementeerd
trossen verschillende manieren.

150
00:07:21,820 --> 00:07:25,600
En een manier waarop we voorgesteld was met
een array of een gekoppelde lijst.

151
00:07:25,600 --> 00:07:29,570
En het blijkt dat canoniek, een
stack ondersteunt ten minste twee operaties.

152
00:07:29,570 --> 00:07:32,320
En de buzz woorden zijn duwen, om
duwen iets op de stack,

153
00:07:32,320 --> 00:07:34,770
zoals een nieuwe verpakking in het
eetzaal, of pop,

154
00:07:34,770 --> 00:07:39,000
wat betekent dat de bovenste verwijderen
lade van de stapel in de eetzaal

155
00:07:39,000 --> 00:07:41,500
hal, en dan misschien wat
andere operaties ook.

156
00:07:41,500 --> 00:07:45,770
Dus hoe kunnen we de structuur definiëren
dat we nu belt een stapel?

157
00:07:45,770 --> 00:07:50,020
>> Nou, we hebben allemaal de vereiste
syntax tot onze beschikking in C. zeg ik,

158
00:07:50,020 --> 00:07:53,830
geef me een soort definitie van
een structuur binnenkant van een stapel,

159
00:07:53,830 --> 00:07:58,030
Ik ga zeggen is een array, van een
heleboel nummers en grootte.

160
00:07:58,030 --> 00:08:00,930
Dus met andere woorden, als ik wil
om dit te implementeren in code,

161
00:08:00,930 --> 00:08:03,830
laat me gaan en gewoon een soort van
tekenen wat dit zegt.

162
00:08:03,830 --> 00:08:06,317
Dus dit zegt, geef me een
structuur die heeft een array,

163
00:08:06,317 --> 00:08:09,400
en ik weet niet wat de capaciteit is,
het is blijkbaar een aantal constante die ik heb

164
00:08:09,400 --> 00:08:10,858
elders gedefinieerd, en dat is prima.

165
00:08:10,858 --> 00:08:15,260
Maar veronderstel dat het is slechts een,
twee, drie, vier, vijf.

166
00:08:15,260 --> 00:08:16,700
Dus de capaciteit is 5.

167
00:08:16,700 --> 00:08:21,730
Dit element binnenkant van mijn
structuur wordt opgeroepen nummers.

168
00:08:21,730 --> 00:08:24,020
En dan moet ik een
andere variabele blijkbaar

169
00:08:24,020 --> 00:08:27,814
riep grootte die in eerste instantie ga ik
te bepalen wordt geïnitialiseerd op nul.

170
00:08:27,814 --> 00:08:29,730
Als er niets in
de stack, grootte nul,

171
00:08:29,730 --> 00:08:31,420
en het vuilnis waarden in getallen.

172
00:08:31,420 --> 00:08:33,450
Ik heb geen idee wat er in zit gewoon nog niet.

173
00:08:33,450 --> 00:08:36,059
>> Dus als ik wil duwen
iets wat op de stapel,

174
00:08:36,059 --> 00:08:40,780
veronderstel ik noem de functie push, en
Ik zeg duw 50, net als de nummer 50,

175
00:08:40,780 --> 00:08:44,090
waar zou u voorstellen
Ik trek hem in deze serie?

176
00:08:44,090 --> 00:08:47,124
Er zijn vijf verschillende mogelijke antwoorden.

177
00:08:47,124 --> 00:08:48,790
Waar wil je het nummer 50 te duwen?

178
00:08:48,790 --> 00:08:51,899
Als het doel hier, opnieuw, bel dan de
push-functie, passeren in een argument

179
00:08:51,899 --> 00:08:52,940
50, waar moet ik het zeggen?

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

181
00:08:55,680 --> 00:08:59,052
Vijf possible-- 20% kans
van correct gissen.

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

183
00:08:59,896 --> 00:09:00,740
>> Publiek: Helemaal rechts.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Helemaal rechts.

185
00:09:01,990 --> 00:09:08,359
Er is nu een 25% kans
van correct gissen.

186
00:09:08,359 --> 00:09:09,650
Dus dat zou eigenlijk wel goed.

187
00:09:09,650 --> 00:09:12,770
Volgens afspraak, zeg ik met een array,
We zouden beginnen meestal links,

188
00:09:12,770 --> 00:09:14,519
maar we konden zeker
vanaf rechts.

189
00:09:14,519 --> 00:09:17,478
Zodat de spoiler hier zou ik ben
waarschijnlijk gaan om het trekken aan de linkerkant,

190
00:09:17,478 --> 00:09:20,060
net als in een normale reeks, waar
Ik begin naar links naar rechts.

191
00:09:20,060 --> 00:09:21,780
Maar als je kunt spiegelen
het rekenkundig, prima.

192
00:09:21,780 --> 00:09:23,060
Het is gewoon niet conventioneel.

193
00:09:23,060 --> 00:09:24,880
Oké, ik moet te maken
meer veranderen wel.

194
00:09:24,880 --> 00:09:27,710
Nu dat ik iets heb geduwd
op de stapel, wat is het volgende?

195
00:09:27,710 --> 00:09:29,400
>> Oké, ik heb om de grootte te verhogen.

196
00:09:29,400 --> 00:09:32,600
Dus laat me gaan en gewoon
actualiseren dit, dat nul was.

197
00:09:32,600 --> 00:09:35,950
En in plaats daarvan nu, ga ik
de waarde één zetten.

198
00:09:35,950 --> 00:09:39,460
En nu denk ik nog een duw
nummer op de stapel, zoals 51.

199
00:09:39,460 --> 00:09:42,680
Nou, ik moet nog een maken
verandering, die is aan de grootte van twee.

200
00:09:42,680 --> 00:09:46,100
En dan denk ik duw één
nummer op de stapel, zoals 61,

201
00:09:46,100 --> 00:09:52,530
nu moet ik het formaat werken een meer
tijd, en krijgt de waarde 3 als de grootte.

202
00:09:52,530 --> 00:09:54,690
En nu denk ik bel pop.

203
00:09:54,690 --> 00:09:57,250
Nu pop, volgens afspraak,
geen argument te nemen.

204
00:09:57,250 --> 00:10:00,430
Met een stack, heel
punt van de metafoor tray

205
00:10:00,430 --> 00:10:03,450
is dat je geen inzicht hebt
gaan halen die lade, kan alles wat je doet

206
00:10:03,450 --> 00:10:06,330
is pop de bovenste één van
de stack, gewoon omdat.

207
00:10:06,330 --> 00:10:08,010
Dat is wat deze datastructuur doet.

208
00:10:08,010 --> 00:10:12,250
>> Dus door die logica als ik
zeggen pop, wat komt er uit?

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

210
00:10:13,080 --> 00:10:15,402
Dus wat er werkelijk is de computer
gaan doen in het geheugen?

211
00:10:15,402 --> 00:10:16,610
Wat doet mijn code hoeft te doen?

212
00:10:16,610 --> 00:10:20,330
Wat zou u voorstellen
we veranderen op het scherm?

213
00:10:20,330 --> 00:10:23,410
Wat moet veranderen?

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

215
00:10:24,960 --> 00:10:26,334
Dus krijgen we ontdoen van 61.

216
00:10:26,334 --> 00:10:27,500
Dus kan ik zeker doen.

217
00:10:27,500 --> 00:10:28,640
En ik kan ontdoen van 61.

218
00:10:28,640 --> 00:10:30,980
En dan wat andere
verandering moet gebeuren?

219
00:10:30,980 --> 00:10:33,160
Maat heeft waarschijnlijk terug naar twee.

220
00:10:33,160 --> 00:10:34,210
En dus dat is prima.

221
00:10:34,210 --> 00:10:36,690
Maar wacht eens even, maat
een moment geleden was drie.

222
00:10:36,690 --> 00:10:38,240
Laten we gewoon een snelle sanity check.

223
00:10:38,240 --> 00:10:41,810
Hoe hebben we weten dat we
wilde om zich te ontdoen van 61?

224
00:10:41,810 --> 00:10:42,760
Omdat we knallen.

225
00:10:42,760 --> 00:10:46,450
En dus heb ik deze tweede eigenschap grootte.

226
00:10:46,450 --> 00:10:48,470
>> Wacht even, ik ben
Terugdenkend aan week twee

227
00:10:48,470 --> 00:10:51,660
toen we begonnen te praten over
arrays, waar was locatie nul,

228
00:10:51,660 --> 00:10:55,920
dit was één locatie, dit was de locatie
twee, dit plaats drie, vier,

229
00:10:55,920 --> 00:10:58,460
het lijkt alsof de
relatie tussen de grootte

230
00:10:58,460 --> 00:11:02,780
en het element dat ik wil verwijderen
uit de array lijkt net wat?

231
00:11:02,780 --> 00:11:05,120
Minus één.

232
00:11:05,120 --> 00:11:07,786
En dus dat is hoe als mensen
we weten dat 61 de eerste plaats komt.

233
00:11:07,786 --> 00:11:09,160
Hoe gaat het met de computer te gaan om te weten?

234
00:11:09,160 --> 00:11:11,701
Wanneer uw code, waar u waarschijnlijk
wilt grootte min één te doen,

235
00:11:11,701 --> 00:11:14,950
dus drie min één twee, en dat
betekent dat we willen om zich te ontdoen van 61.

236
00:11:14,950 --> 00:11:18,000
En dan kunnen we inderdaad te werken
de grootte, zodat de grootte nu

237
00:11:18,000 --> 00:11:20,300
gaat van drie naar twee.

238
00:11:20,300 --> 00:11:24,520
En alleen maar om belerend te zijn, ga ik
voor te stellen dat ik klaar ben, toch?

239
00:11:24,520 --> 00:11:27,660
U voorgesteld intuïtief
correct moet ik ontdoen van 61.

240
00:11:27,660 --> 00:11:30,700
Maar heb ik niet soort
soort gekregen ontdoen van 61?

241
00:11:30,700 --> 00:11:33,790
Ik heb effectief vergeten
dat het eigenlijk daar.

242
00:11:33,790 --> 00:11:37,680
En denk terug aan PSET4, als je hebt gelezen
het artikel over forensisch onderzoek, de PDF-

243
00:11:37,680 --> 00:11:40,780
dat we jullie lezen, of u
zal deze week lezen PSET4.

244
00:11:40,780 --> 00:11:44,300
Bedenk dat dit is eigenlijk relevant voor
het hele idee van computer forensics.

245
00:11:44,300 --> 00:11:47,820
Wat een computer algemeen doet is
het gewoon vergeet waar iets is,

246
00:11:47,820 --> 00:11:51,300
maar het gaat niet verder in en net
probeer het uit of override krassen

247
00:11:51,300 --> 00:11:54,560
die bits met nullen en enen
of een ander willekeurig patroon

248
00:11:54,560 --> 00:11:56,690
tenzij u zelf doen met opzet.

249
00:11:56,690 --> 00:11:58,930
Dus je intuïtie was
Goed, laten zich te ontdoen van 61.

250
00:11:58,930 --> 00:12:00,650
Maar in werkelijkheid, hoeven we niet te storen.

251
00:12:00,650 --> 00:12:04,040
We hoeven alleen maar te vergeten dat
het is er door het veranderen van onze omvang.

252
00:12:04,040 --> 00:12:05,662
>> Nu is er een probleem met deze stapel.

253
00:12:05,662 --> 00:12:07,620
Als ik blijf dingen duwen
op de stapel, wat is

254
00:12:07,620 --> 00:12:11,167
uiteraard gaat gebeuren
in slechts een paar momenten de tijd?

255
00:12:11,167 --> 00:12:12,500
We gaan uit van de ruimte om te rennen.

256
00:12:12,500 --> 00:12:13,580
En wat doen we?

257
00:12:13,580 --> 00:12:14,680
We soort geschroefd.

258
00:12:14,680 --> 00:12:19,000
Deze implementatie niet laat
ons het formaat van de matrix, omdat het gebruik van

259
00:12:19,000 --> 00:12:21,240
deze syntax, als u
denk terug aan week twee,

260
00:12:21,240 --> 00:12:23,520
als je eenmaal hebt verklaard
de grootte van een array,

261
00:12:23,520 --> 00:12:26,780
hebben we een mechanisme, waar nog niet gezien
kunt u de grootte van de array te wijzigen.

262
00:12:26,780 --> 00:12:29,020
En inderdaad C heeft niet die functie.

263
00:12:29,020 --> 00:12:32,524
Als je zegt geef me vijf
Nths, noemen ze nummers,

264
00:12:32,524 --> 00:12:33,940
dat is alles wat je gaat om het te krijgen.

265
00:12:33,940 --> 00:12:38,790
Dus we nu doen vanaf maandag, hebben
het vermogen om een ​​oplossing te drukken

266
00:12:38,790 --> 00:12:42,480
hoewel, we hoeven alleen maar te tweaken
de definitie van onze stack

267
00:12:42,480 --> 00:12:46,840
enkele hardcoded matrix niet,
maar gewoon om een ​​adres op te slaan.

268
00:12:46,840 --> 00:12:47,890
>> Waarom is dit?

269
00:12:47,890 --> 00:12:51,690
Nu moeten we gewoon comfortabel met zijn
dat als mijn programma draait,

270
00:12:51,690 --> 00:12:53,730
Ik ben vermoedelijk gaan
moet de menselijke vragen

271
00:12:53,730 --> 00:12:55,110
hoeveel nummers wilt u opslaan?

272
00:12:55,110 --> 00:12:56,776
Dus de ingang moet ergens vandaan komen.

273
00:12:56,776 --> 00:12:59,140
Maar zodra ik weet dat
nummer, dan kan ik alleen maar

274
00:12:59,140 --> 00:13:02,470
Gebruik welke functie te geven
me een brok van geheugen?

275
00:13:02,470 --> 00:13:03,580
Ik kan gebruiken malloc.

276
00:13:03,580 --> 00:13:06,710
En ik kan een aantal zeggen
bytes Ik wil terug voor deze nths.

277
00:13:06,710 --> 00:13:10,910
En alles wat ik heb om op te slaan in de nummers
variabele hier binnenkant van deze structuur

278
00:13:10,910 --> 00:13:13,480
wat zou moeten zijn?

279
00:13:13,480 --> 00:13:18,440
Wat er werkelijk gaat in de
getallen in dit scenario?

280
00:13:18,440 --> 00:13:21,300
Ja, een verwijzing naar het eerste
byte van dat stuk van het geheugen,

281
00:13:21,300 --> 00:13:24,940
of meer specifiek, het adres
de eerste van deze bytes.

282
00:13:24,940 --> 00:13:27,300
Maakt niet uit of het een
byte of een miljard bytes,

283
00:13:27,300 --> 00:13:28,890
Ik moet alleen de zorg over de eerste.

284
00:13:28,890 --> 00:13:31,530
Want wat malloc garanties en
mijn besturingssysteem garanties,

285
00:13:31,530 --> 00:13:34,170
is dat de brok van geheugen I
krijgen, gaat het aaneengesloten te zijn.

286
00:13:34,170 --> 00:13:35,378
Er is niet van plan om hiaten zijn.

287
00:13:35,378 --> 00:13:38,576
Dus als ik 50 ben gevraagd
bytes of 1000 bytes,

288
00:13:38,576 --> 00:13:40,450
ze allemaal gaan worden
rug aan rug aan rug.

289
00:13:40,450 --> 00:13:44,500
En zolang ik me herinner hoe groot, hoe
veel vroeg ik voor, alles wat ik moet weten

290
00:13:44,500 --> 00:13:46,230
is het eerste adres.

291
00:13:46,230 --> 00:13:48,660
>> Dus nu hebben we de mogelijkheid om in de code.

292
00:13:48,660 --> 00:13:51,280
Zij, het gaat om ons
meer tijd om dit te schrijven op,

293
00:13:51,280 --> 00:13:55,900
we kunnen nu herverdelen dat het geheugen door
gewoon een ander adres op te slaan er

294
00:13:55,900 --> 00:13:59,060
als we willen een groter of zelfs
een kleiner deel van het geheugen.

295
00:13:59,060 --> 00:14:00,170
Dus hier om een ​​afweging.

296
00:14:00,170 --> 00:14:01,360
Nu krijgen we dynamiek.

297
00:14:01,360 --> 00:14:03,350
We hebben nog steeds
contiguousness ik te beweren.

298
00:14:03,350 --> 00:14:05,881
Omdat malloc ons zal geven
een aaneengesloten stuk van het geheugen.

299
00:14:05,881 --> 00:14:08,630
Maar dit gaat om een ​​pijn in zijn
de nek voor ons, de programmeur,

300
00:14:08,630 --> 00:14:09,770
daadwerkelijk coderen up.

301
00:14:09,770 --> 00:14:10,730
Het is gewoon meer werk.

302
00:14:10,730 --> 00:14:13,930
We moeten code verwant aan wat ik was
bonzen uit slechts een moment geleden.

303
00:14:13,930 --> 00:14:16,120
Zeer goed te doen, maar het voegt complexiteit.

304
00:14:16,120 --> 00:14:19,520
En dus ontwikkelaar tijd, programmeur
de tijd is nog een andere bron

305
00:14:19,520 --> 00:14:22,520
dat we nodig zou kunnen hebben om te besteden
wat tijd om nieuwe functies te krijgen.

306
00:14:22,520 --> 00:14:24,020
En dan is er natuurlijk een wachtrij.

307
00:14:24,020 --> 00:14:26,227
We zullen niet in deze te gaan
een in veel detail.

308
00:14:26,227 --> 00:14:27,560
Maar het is zeer vergelijkbaar in de geest.

309
00:14:27,560 --> 00:14:31,220
Ik kon een wachtrij uit te voeren, en
zijn overeenkomstige operaties,

310
00:14:31,220 --> 00:14:35,660
enqueue of dequeue, zoals toevoegen of verwijderen,
het is gewoon een liefhebber manier om te zeggen dat,

311
00:14:35,660 --> 00:14:38,100
enqueue of dequeue, als volgt.

312
00:14:38,100 --> 00:14:41,170
Ik geef mezelf een structuur
heeft dat nog eens serie een aantal's,

313
00:14:41,170 --> 00:14:44,000
heeft dat nog eens een afmeting,
maar waarom moet ik nu nodig

314
00:14:44,000 --> 00:14:46,940
te houden van de voorzijde van een wachtrij bewaren?

315
00:14:46,940 --> 00:14:50,630
Ik hoefde niet te weten
de voorkant van mijn stack.

316
00:14:50,630 --> 00:14:53,570
Nou, als ik opnieuw voor een
queue-- laten we gewoon moeilijk

317
00:14:53,570 --> 00:14:57,870
code het als het hebben als vijf
integers hier mogelijk.

318
00:14:57,870 --> 00:15:00,940
Dus dit nul, één, twee, drie, vier.

319
00:15:00,940 --> 00:15:03,430
Dit gaat worden
riep opnieuw nummers.

320
00:15:03,430 --> 00:15:06,940
En deze zal worden genoemd size.

321
00:15:06,940 --> 00:15:10,056
>> Waarom is het niet voldoende
gewoon formaat hebben?

322
00:15:10,056 --> 00:15:11,680
Nou, laten we duw die dezelfde nummers op.

323
00:15:11,680 --> 00:15:14,220
Dus ik pushed-- ik enqueued, of geduwd.

324
00:15:14,220 --> 00:15:20,150
Nu zal ik enqueue 50, en vervolgens
51 en vervolgens 61, en dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Dus dat is enqueue.

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

327
00:15:23,176 --> 00:15:25,050
En die identiek uitziet
Stapels nu toe,

328
00:15:25,050 --> 00:15:27,190
behalve dat ik geen behoefte aan een verandering te maken.

329
00:15:27,190 --> 00:15:33,680
Ik moet dit formaat te werken, dus ik ga
van nul tot 1 tot 2 tot 3 kaarten.

330
00:15:33,680 --> 00:15:35,760
Hoe kan ik dequeue?

331
00:15:35,760 --> 00:15:36,890
Wat gebeurt er met dequeue?

332
00:15:36,890 --> 00:15:41,950
Wie moet deze lijst eerst komt uit
als het de rij bij de Apple Store?

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

334
00:15:42,780 --> 00:15:44,700
Dus het is een beetje lastiger deze keer.

335
00:15:44,700 --> 00:15:47,880
Overwegende dat de laatste keer dat het was super
gemakkelijk om gewoon te doen grootte minus één,

336
00:15:47,880 --> 00:15:51,440
Ik aan het einde van mijn reeks effectief
waar de nummers zijn, het verwijdert 61.

337
00:15:51,440 --> 00:15:52,920
Maar ik wil niet te verwijderen 61.

338
00:15:52,920 --> 00:15:55,030
Ik wil nemen 50, die
was er op 05:00

339
00:15:55,030 --> 00:15:56,790
in de rij voor de
nieuwe iPhone of zo.

340
00:15:56,790 --> 00:16:01,200
En dus te ontdoen van 50, I
kan dit niet alleen doen, toch?

341
00:16:01,200 --> 00:16:02,547
Ik kan doorstrepen 50.

342
00:16:02,547 --> 00:16:04,380
Maar we zeiden dat we
moeten niet zo anal worden

343
00:16:04,380 --> 00:16:06,330
als uitkrabben of de gegevens te verbergen.

344
00:16:06,330 --> 00:16:08,090
We kunnen gewoon vergeten waar het is.

345
00:16:08,090 --> 00:16:12,330
>> Maar als ik mijn maat veranderen nu
twee, is dit voldoende informatie

346
00:16:12,330 --> 00:16:15,711
om te weten wat er gaande is in mijn wachtrij?

347
00:16:15,711 --> 00:16:16,680
Niet echt.

348
00:16:16,680 --> 00:16:19,830
Net als mijn maat is twee, maar
waar komt de wachtrij begint,

349
00:16:19,830 --> 00:16:22,980
vooral als ik heb nog steeds
die dezelfde nummers in het geheugen.

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

351
00:16:24,260 --> 00:16:27,090
Dus ik moet onthouden
nu waar de voorkant is.

352
00:16:27,090 --> 00:16:29,630
En zo heb ik voorgesteld up
daar zullen we net hebben genoemd

353
00:16:29,630 --> 00:16:33,729
N front, waarvan de eerste
waarde moet wat geweest?

354
00:16:33,729 --> 00:16:35,270
Nul, maar het begin van de lijst.

355
00:16:35,270 --> 00:16:40,876
Maar nu naast decrementeren
de grootte, we verhogen de voorkant.

356
00:16:40,876 --> 00:16:42,000
Nu hier is een ander probleem.

357
00:16:42,000 --> 00:16:43,030
Dus zodra ik blijven gaan.

358
00:16:43,030 --> 00:16:47,520
Veronderstel dat dit is het aantal
zoals 121, 124, en dan, dammit,

359
00:16:47,520 --> 00:16:48,610
Ik ben uit de ruimte.

360
00:16:48,610 --> 00:16:50,390
Maar wacht eens even, ik ben niet.

361
00:16:50,390 --> 00:16:55,630
Dus op dit punt in het verhaal,
veronderstellen dat de grootte één, twee,

362
00:16:55,630 --> 00:17:00,370
drie, vier, zodat veronderstellen dat de
size vier de voorste één,

363
00:17:00,370 --> 00:17:01,621
dus 51 is aan de voorzijde.

364
00:17:01,621 --> 00:17:04,329
Ik wil een ander nummer hier te zetten,
maar, verdomme, ik ben uit de ruimte.

365
00:17:04,329 --> 00:17:06,710
Maar ik ben niet echt, toch?

366
00:17:06,710 --> 00:17:11,192
Waar kan ik een aantal
toegevoegde waarde, zoals 171?

367
00:17:11,192 --> 00:17:13,400
Ja, ik kon gewoon een soort van
ga terug daar, toch?

368
00:17:13,400 --> 00:17:18,161
En dan steken de 50, of
gewoon overschrijven met 171.

369
00:17:18,161 --> 00:17:20,410
En als je je afvraagt ​​waarom
onze nummers werd zo willekeurig,

370
00:17:20,410 --> 00:17:24,150
Deze worden vaak computer taken
wetenschap cursussen op Harvard na CS50.

371
00:17:24,150 --> 00:17:27,510
Maar dat was een goede optimalisatie,
want nu ben ik niet verspillen ruimte.

372
00:17:27,510 --> 00:17:30,750
Ik heb nog steeds te onthouden
hoe groot dit ding is totaal.

373
00:17:30,750 --> 00:17:31,500
Het is vijf in totaal.

374
00:17:31,500 --> 00:17:33,375
Omdat ik het niet wil
start overschrijven 51.

375
00:17:33,375 --> 00:17:36,260
Dus nu ben ik nog steeds uit de ruimte,
dus hetzelfde probleem als voorheen.

376
00:17:36,260 --> 00:17:39,140
Maar je kunt zien hoe nu
in de code, heb je waarschijnlijk

377
00:17:39,140 --> 00:17:41,910
moet je een beetje meer te schrijven
complexiteit om dat te realiseren.

378
00:17:41,910 --> 00:17:44,510
En inderdaad, welke operator
in C waarschijnlijk laat

379
00:17:44,510 --> 00:17:48,110
u dit de circulariteit magisch doen?

380
00:17:48,110 --> 00:17:50,160
Ja, de modulo operator,
het percentage teken.

381
00:17:50,160 --> 00:17:53,160
Dus wat is een soort van cool over een wachtrij,
ook al houden wij tekenen arrays

382
00:17:53,160 --> 00:17:56,520
omdat deze als rechte lijnen, als je
soort van denken over dit als gebogen

383
00:17:56,520 --> 00:18:00,341
rond als een cirkel, dan gewoon
intuïtief dat soort werkt mentaal

384
00:18:00,341 --> 00:18:01,590
Ik denk dat een beetje schoner.

385
00:18:01,590 --> 00:18:05,190
Je zou nog steeds moeten uitvoeren
dat mentale model in de code.

386
00:18:05,190 --> 00:18:07,550
Dus niet zo moeilijk,
uiteindelijk, te implementeren,

387
00:18:07,550 --> 00:18:12,430
maar we nog steeds verliest de omvang-- eerder, de
mogelijkheid om het formaat, tenzij we dit doen.

388
00:18:12,430 --> 00:18:15,310
>> Wij hebben om zich te ontdoen van de array, we
te vervangen door een enkele wijzer,

389
00:18:15,310 --> 00:18:20,010
en dan ergens in mijn code ik heb
een roep welke functie om daadwerkelijk te creëren

390
00:18:20,010 --> 00:18:23,720
de array gebelde nummers?

391
00:18:23,720 --> 00:18:26,190
Malloc, of iets dergelijks
functie, precies.

392
00:18:26,190 --> 00:18:30,481
Vragen over stapels of wachtrijen.

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

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

395
00:18:33,657 --> 00:18:34,240
Goede vraag.

396
00:18:34,240 --> 00:18:35,830
Wat modulo zou u hier te gebruiken.

397
00:18:35,830 --> 00:18:38,520
Dus in het algemeen bij gebruik
mod, zou je het doen

398
00:18:38,520 --> 00:18:40,620
de omvang van de
geheel gegevensstructuur.

399
00:18:40,620 --> 00:18:44,120
Zo iets als vijf of capaciteit, indien
het is constant, is waarschijnlijk betrokken.

400
00:18:44,120 --> 00:18:47,100
Maar gewoon modulo vijf doen
waarschijnlijk onvoldoende,

401
00:18:47,100 --> 00:18:51,380
want we moeten weten doen we
wrap around hier of hier of hier.

402
00:18:51,380 --> 00:18:54,160
Dus je bent waarschijnlijk ook
gaat te willen betrekken

403
00:18:54,160 --> 00:18:57,220
de grootte van het ding of
de voorste variabele ook.

404
00:18:57,220 --> 00:19:00,140
Dus het is gewoon deze relatief
eenvoudige rekenkundige uitdrukking,

405
00:19:00,140 --> 00:19:02,000
maar modulo zou het belangrijkste ingrediënt zijn.

406
00:19:02,000 --> 00:19:03,330
>> Dus korte film als je wil.

407
00:19:03,330 --> 00:19:05,780
Een animatie die sommige
mensen aan een andere universiteit

408
00:19:05,780 --> 00:19:08,060
samen te stellen dat we hebben
aangepast voor deze discussie.

409
00:19:08,060 --> 00:19:12,630
Het gaat om het leren van de Jack
feiten over wachtrijen en statistieken.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Once upon a time,
Er was een jongen genaamd Jack.

412
00:19:21,890 --> 00:19:25,330
Als het ging om het maken van vrienden,
Jack had geen talent.

413
00:19:25,330 --> 00:19:28,220
Dus Jack ging naar de te praten
populairste jongen wist hij.

414
00:19:28,220 --> 00:19:30,920
Hij ging naar Lou en vroeg: Wat moet ik doen?

415
00:19:30,920 --> 00:19:33,400
Lou zag dat zijn vriend
was echt bedroefd.

416
00:19:33,400 --> 00:19:36,050
Nou, begon hij, net
kijk eens hoe je gekleed bent.

417
00:19:36,050 --> 00:19:38,680
Heb je geen kleren
met een andere look?

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

419
00:19:39,660 --> 00:19:40,840
Dat doe ik zeker.

420
00:19:40,840 --> 00:19:43,320
Kom naar mijn huis en
Ik zal ze laten zien.

421
00:19:43,320 --> 00:19:44,550
Dus gingen ze af naar Jack's.

422
00:19:44,550 --> 00:19:47,520
En Jack liet Lou de doos
waar hij hield al zijn overhemden,

423
00:19:47,520 --> 00:19:49,260
en zijn broek en zijn sokken.

424
00:19:49,260 --> 00:19:52,290
Lou zei, ik zie je hebt
al je kleren in een stapel.

425
00:19:52,290 --> 00:19:54,870
Waarom ga je niet dragen wat
anderen af ​​en toe?

426
00:19:54,870 --> 00:19:58,020
>> Jack zei, nou ja, toen ik
verwijder kleding en sokken,

427
00:19:58,020 --> 00:20:00,780
Ik was ze en zet
ze weg in de doos.

428
00:20:00,780 --> 00:20:03,210
Dan komt de volgende
's morgens, en tot ik hop.

429
00:20:03,210 --> 00:20:06,380
Ik ga naar de doos en krijg
mijn kleren uit de top.

430
00:20:06,380 --> 00:20:09,070
Lou snel gerealiseerd
het probleem met Jack.

431
00:20:09,070 --> 00:20:12,080
Hij hield kleding, cd's,
en boeken in de stapel.

432
00:20:12,080 --> 00:20:14,420
Toen hij bereikte voor
iets te lezen of om te dragen,

433
00:20:14,420 --> 00:20:17,100
hij zou kiezen voor de top boek of ondergoed.

434
00:20:17,100 --> 00:20:19,500
Toen hij klaar was, hij
zou het te zetten terug.

435
00:20:19,500 --> 00:20:21,970
Terug zou gaan, boven op de stapel.

436
00:20:21,970 --> 00:20:24,460
Ik weet de oplossing,
zei een triomfantelijke Loud.

437
00:20:24,460 --> 00:20:27,090
Je nodig hebt om te leren
beginnen met een wachtrij.

438
00:20:27,090 --> 00:20:29,870
Lou nam Jack's kleding en
hing ze in de kast.

439
00:20:29,870 --> 00:20:32,710
En toen hij had geleegd
de doos, hij gooide het.

440
00:20:32,710 --> 00:20:36,500
>> Toen zei hij, nu Jack, aan het einde van
de dag, zet je kleren aan de linkerkant

441
00:20:36,500 --> 00:20:37,990
wanneer je ze weg.

442
00:20:37,990 --> 00:20:41,300
Dan morgen ochtend als je
zie de zon, krijg je kleren

443
00:20:41,300 --> 00:20:43,440
aan de rechterkant, vanaf het einde van de lijn.

444
00:20:43,440 --> 00:20:44,880
Zie je niet? zei Lou.

445
00:20:44,880 --> 00:20:46,370
Het zal zo leuk zijn.

446
00:20:46,370 --> 00:20:49,770
U vindt alles een keer te dragen
voordat je iets twee keer te dragen.

447
00:20:49,770 --> 00:20:52,670
En met alles in de rij
in zijn kast en plank,

448
00:20:52,670 --> 00:20:55,160
Jack begon te voelen
helemaal zeker van zichzelf.

449
00:20:55,160 --> 00:20:59,720
Alle dank aan Lou en
zijn prachtige wachtrij.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Oké, het is schattig.

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

452
00:21:05,920 --> 00:21:10,080
Dus wat er werkelijk aan de hand
op onder de motorkap nu?

453
00:21:10,080 --> 00:21:12,370
Dat we pointers,
dat wij malloc,

454
00:21:12,370 --> 00:21:15,680
dat we de mogelijkheid om te creëren
brokken van het geheugen voor onszelf

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

456
00:21:16,344 --> 00:21:18,510
Dus dit is een beeld dat wij
glimp net de andere dag.

457
00:21:18,510 --> 00:21:21,180
We hebben niet echt wonen
op, maar deze foto

458
00:21:21,180 --> 00:21:24,180
is er aan de hand eronder
de kap voor weken nu.

459
00:21:24,180 --> 00:21:27,050
En dus dit betekent, net
een rechthoek die we hebben getrokken,

460
00:21:27,050 --> 00:21:28,180
geheugen van uw computer.

461
00:21:28,180 --> 00:21:31,850
En misschien uw computer, of CS50
ID, heeft een gigabyte aan geheugen of RAM

462
00:21:31,850 --> 00:21:33,050
of twee gigabyte of vier.

463
00:21:33,050 --> 00:21:34,450
Het maakt eigenlijk niet uit.

464
00:21:34,450 --> 00:21:37,240
Uw besturingssysteem
Windows of Mac OS of Linux,

465
00:21:37,240 --> 00:21:41,120
maakt in wezen het programma
om te denken dat het heeft toegang

466
00:21:41,120 --> 00:21:42,982
het geheel van
geheugen van uw computer,

467
00:21:42,982 --> 00:21:45,440
hoewel je zou worden uitgevoerd
meerdere programma's tegelijk.

468
00:21:45,440 --> 00:21:46,990
Dus in werkelijkheid, dat werkt niet echt.

469
00:21:46,990 --> 00:21:49,448
Maar het is een soort van een illusie
gegeven om al uw programma's.

470
00:21:49,448 --> 00:21:53,110
Dus als je had twee optredens van RAM-geheugen, deze
is hoe de computer zou kunnen denken.

471
00:21:53,110 --> 00:21:57,110
>> Nu toevallig een van deze
dingen, een van deze segmenten van het geheugen,

472
00:21:57,110 --> 00:21:58,350
wordt een stapel.

473
00:21:58,350 --> 00:22:01,680
En inderdaad elk moment
tot nu toe in het schrijven van code

474
00:22:01,680 --> 00:22:05,900
dat u wel een
functie, bijvoorbeeld de belangrijkste.

475
00:22:05,900 --> 00:22:08,410
Herinneren dat elke keer dat ik heb
het geheugen van de computer getrokken,

476
00:22:08,410 --> 00:22:10,640
Ik trek altijd een soort van
de helft van een rechthoek hier

477
00:22:10,640 --> 00:22:12,520
en niet de moeite praten
over wat er boven.

478
00:22:12,520 --> 00:22:15,980
Want als belangrijkste wordt genoemd, ik beweer
dat u deze strook van het geheugen krijgen

479
00:22:15,980 --> 00:22:16,970
dat gaat hier beneden.

480
00:22:16,970 --> 00:22:20,650
Als belangrijkste noemde functie
als ruilmiddel, goed swap gaat hier.

481
00:22:20,650 --> 00:22:23,720
En het blijkt, dat is
waar het belanden.

482
00:22:23,720 --> 00:22:26,277
Op iets genaamd een stapel
binnenkant van het geheugen van uw computer.

483
00:22:26,277 --> 00:22:28,360
Nu aan het eind van de dag,
dit is gewoon adressen.

484
00:22:28,360 --> 00:22:30,680
Het is net als byte nul,
één byte, byte 2 miljard.

485
00:22:30,680 --> 00:22:33,130
Maar als je erover nadenkt
aangezien dit rechthoekig voorwerp,

486
00:22:33,130 --> 00:22:35,130
alle we elke doen
tijd noemen we een functie

487
00:22:35,130 --> 00:22:37,180
gelaagdheid een nieuw stukje van het geheugen.

488
00:22:37,180 --> 00:22:41,700
We geven die functie een plak
eigen geheugen werken.

489
00:22:41,700 --> 00:22:44,490
>> En herinner me nu dat dit belangrijk is.

490
00:22:44,490 --> 00:22:46,400
Want als we hebben
iets als swap

491
00:22:46,400 --> 00:22:51,610
en twee lokale variabelen zoals A en B
we de waarden van de ene en twee

492
00:22:51,610 --> 00:22:55,130
twee en één, recall
dat wanneer swap terugkeert,

493
00:22:55,130 --> 00:22:58,330
het is alsof dit stukje
van het geheugen is gewoon weg.

494
00:22:58,330 --> 00:23:00,080
In werkelijkheid, het is nog steeds
er forensisch.

495
00:23:00,080 --> 00:23:01,940
En wat is er eigenlijk nog steeds.

496
00:23:01,940 --> 00:23:05,410
Maar conceptueel, het is zo
al is het helemaal weg.

497
00:23:05,410 --> 00:23:10,910
En zo de belangrijkste kent geen van de werkzaamheden
die werd gedaan doordat swap functie,

498
00:23:10,910 --> 00:23:14,890
tenzij daadwerkelijk die wordt doorgegeven
argumenten wijzer of door verwijzing.

499
00:23:14,890 --> 00:23:17,790
Nu, de fundamentele oplossing
om dat probleem met de swap

500
00:23:17,790 --> 00:23:19,970
passeert dingen op adres.

501
00:23:19,970 --> 00:23:23,250
Maar het blijkt ook, wat is
er aan de hand boven dat deel

502
00:23:23,250 --> 00:23:26,330
van de rechthoek al die tijd is
maar er is er meer geheugen.

503
00:23:26,330 --> 00:23:28,790
En als je dynamisch
geheugen toewijzen,

504
00:23:28,790 --> 00:23:32,020
of het nu de binnenkant van GetString, waarvan
we hebben gedaan voor u in de CS50

505
00:23:32,020 --> 00:23:34,710
bibliotheek, of als jullie
bellen malloc en vragen

506
00:23:34,710 --> 00:23:37,950
het besturingssysteem voor een brok van
geheugen, komt niet uit de stapel.

507
00:23:37,950 --> 00:23:40,960
Het komt uit een andere plaats
in het geheugen van de computer

508
00:23:40,960 --> 00:23:42,220
dat heet de heap.

509
00:23:42,220 --> 00:23:43,430
En dat is niet anders.

510
00:23:43,430 --> 00:23:44,285
Het is hetzelfde RAM.

511
00:23:44,285 --> 00:23:45,160
Het is hetzelfde geheugen.

512
00:23:45,160 --> 00:23:49,080
Het is gewoon het RAM-geheugen dat is up
er in plaats van hier beneden.

513
00:23:49,080 --> 00:23:50,750
>> En wat betekent dat?

514
00:23:50,750 --> 00:23:53,650
Nou, als uw computer
een beperkte hoeveelheid geheugen

515
00:23:53,650 --> 00:23:57,450
en de stapel groeit, dus
te spreken, en de hoop, volgens

516
00:23:57,450 --> 00:23:59,349
deze pijl, groeit naar beneden.

517
00:23:59,349 --> 00:24:01,140
Met andere woorden, elke
keer dat je malloc noemen,

518
00:24:01,140 --> 00:24:03,430
je wordt gegeven een plak
geheugen van boven,

519
00:24:03,430 --> 00:24:06,630
dan misschien een beetje lager, dan een beetje
lager, elke keer als je belt malloc,

520
00:24:06,630 --> 00:24:10,100
de hoop, het gebruik,
is soort groeit,

521
00:24:10,100 --> 00:24:11,950
groeien dichter en dichter bij wat?

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

523
00:24:13,382 --> 00:24:14,840
Betekent dit lijkt een goed idee?

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

525
00:24:18,420 --> 00:24:22,140
Ik bedoel, waar het niet echt duidelijk
wat je kunt doen als je maar

526
00:24:22,140 --> 00:24:23,910
een beperkte hoeveelheid geheugen.

527
00:24:23,910 --> 00:24:25,200
Maar dit is zeker slecht.

528
00:24:25,200 --> 00:24:27,920
Die twee pijlen zijn op een
Stoomcursus voor elkaar.

529
00:24:27,920 --> 00:24:31,930
>> En het blijkt dat de bad guy, mensen die
zijn bijzonder goed met de programmering,

530
00:24:31,930 --> 00:24:36,140
en proberen om inbreken in computers,
kan deze realiteit te exploiteren.

531
00:24:36,140 --> 00:24:38,290
In feite, laten we eens kijken
een klein fragment.

532
00:24:38,290 --> 00:24:41,350
Dus dit is een voorbeeld kunt u lezen
over meer in detail op Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Wij zullen u wijzen op de
artikel als nieuwsgierig.

534
00:24:43,100 --> 00:24:45,650
Maar er is een aanval over het algemeen
bekend als buffer overflow dat

535
00:24:45,650 --> 00:24:49,570
bestaat zolang mensen
het vermogen om te manipuleren hebben gehad

536
00:24:49,570 --> 00:24:53,120
De computergeheugen, vooral in C.
Dit is dus een willekeurig programma,

537
00:24:53,120 --> 00:24:55,130
maar laten we het lezen van onder naar boven.

538
00:24:55,130 --> 00:24:57,650
Hoofd in argc char ster argv.

539
00:24:57,650 --> 00:24:59,830
Dus het is een programma dat duurt
command line argumenten.

540
00:24:59,830 --> 00:25:03,620
En alle belangrijke blijkbaar is bellen
een functie, noem het F voor eenvoud.

541
00:25:03,620 --> 00:25:04,610
En het gaat in wat?

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

543
00:25:05,490 --> 00:25:09,320
Het gaat dus in F, ongeacht
het woord is dat de gebruiker getypte

544
00:25:09,320 --> 00:25:11,500
bij de prompt na de
naam van het programma's op alle.

545
00:25:11,500 --> 00:25:15,730
Zoveel als Caesar of Vigenere, die
je zou herinneren doen met argv.

546
00:25:15,730 --> 00:25:16,680
>> Dus wat is F?

547
00:25:16,680 --> 00:25:19,760
F neemt in een string
als enige argument,

548
00:25:19,760 --> 00:25:22,100
AKA een char ster, dezelfde
ding, als een string.

549
00:25:22,100 --> 00:25:24,920
En het is willekeurig heet
bar in dit voorbeeld.

550
00:25:24,920 --> 00:25:27,710
En dan char c 12,
alleen in termen van de leek,

551
00:25:27,710 --> 00:25:31,750
Wat is char c beugel 12 voor ons doet?

552
00:25:31,750 --> 00:25:33,440
Wat is er te doen?

553
00:25:33,440 --> 00:25:36,490
Toewijzen van geheugen, in het bijzonder
12 bytes 12 tekens.

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

555
00:25:36,990 --> 00:25:40,000
En dan de laatste regel, roer en
kopiëren, hebt u waarschijnlijk niet gezien.

556
00:25:40,000 --> 00:25:43,360
Dit is een string kopie
functie waarvan het doel in het leven

557
00:25:43,360 --> 00:25:48,160
is haar tweede argument kopiëren
in zijn eerste argument,

558
00:25:48,160 --> 00:25:51,190
maar slechts tot een
aantal bytes.

559
00:25:51,190 --> 00:25:53,860
Dus de derde argument zegt:
hoeveel bytes moet je mij?

560
00:25:53,860 --> 00:25:56,720
De lengte van de bar,
ongeacht de gebruiker getypt.

561
00:25:56,720 --> 00:25:59,320
En de inhoud van
bar, die string, zijn

562
00:25:59,320 --> 00:26:02,330
in het geheugen gekopieerde wees op bij C.

563
00:26:02,330 --> 00:26:04,060
>> Dus dit lijkt soort dom, en het is.

564
00:26:04,060 --> 00:26:06,300
Het is een gekunsteld voorbeeld
maar het is representatief

565
00:26:06,300 --> 00:26:10,100
van een klasse van aanvalsvectoren,
een manier van het aanvallen van een programma.

566
00:26:10,100 --> 00:26:15,050
Alles is prima en goed als de gebruiker
types in een woord, dat is 11 tekens

567
00:26:15,050 --> 00:26:18,040
of minder, plus de backslash nul.

568
00:26:18,040 --> 00:26:22,830
Wat als de gebruiker soorten in meer dan
11 of 12 of 20 of 50 tekens?

569
00:26:22,830 --> 00:26:25,090
Wat is dit programma gaan doen?

570
00:26:25,090 --> 00:26:29,360
Potentieel seg fout. Het gaat
blindelings alles in de bar up kopiëren

571
00:26:29,360 --> 00:26:31,750
zijn lengte, wat
letterlijk alles in de bar,

572
00:26:31,750 --> 00:26:36,307
in de adresbalk wees bij C. Maar C
slechts preventief gegeven als 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Maar er is geen extra controle.

574
00:26:37,640 --> 00:26:38,700
Er is geen als de omstandigheden.

575
00:26:38,700 --> 00:26:40,580
Er is geen fout hier controleren.

576
00:26:40,580 --> 00:26:43,270
>> En dus wat dit programma is
gaan doen is gewoon blindelings

577
00:26:43,270 --> 00:26:45,750
kopiëren een ding naar de andere.

578
00:26:45,750 --> 00:26:47,880
En dus als we deze trekken
als beeld, hier is

579
00:26:47,880 --> 00:26:49,860
slechts een splinter van de geheugenruimte.

580
00:26:49,860 --> 00:26:53,470
Zo merkt aan de onderkant, we
hebben de lokale variabele bar.

581
00:26:53,470 --> 00:26:57,330
Zodat pointer dat gaat store--
eerder dat lokale argument dat is

582
00:26:57,330 --> 00:26:58,672
naar de string bar slaan.

583
00:26:58,672 --> 00:27:00,380
En dan merk gewoon
daarboven in een stack,

584
00:27:00,380 --> 00:27:02,505
want elke keer als je vragen
voor geheugen op de stack,

585
00:27:02,505 --> 00:27:04,310
het gaat een beetje
erboven pictorially,

586
00:27:04,310 --> 00:27:06,270
bericht dat we daar hebben 12 bytes.

587
00:27:06,270 --> 00:27:10,690
Linksboven is men C beugel nul en
rechtsonder men C beugel 11.

588
00:27:10,690 --> 00:27:12,870
Dat is gewoon hoe de computers
gaat om het uit te leggen.

589
00:27:12,870 --> 00:27:18,300
Dus gewoon intuïtief, als bar heeft meer
dan 12 tekens in totaal, inclusief

590
00:27:18,300 --> 00:27:25,790
de backslash nul, waar is de
12 of de C beugel 12 gaan om te gaan?

591
00:27:25,790 --> 00:27:28,440
Of liever gezegd waar is de 12e
vermogen of de 13de karakter,

592
00:27:28,440 --> 00:27:30,900
de honderdste karakter gaan
om te eindigen op de foto?

593
00:27:30,900 --> 00:27:33,400
Boven of onder?

594
00:27:33,400 --> 00:27:36,300
>> Juist, want hoewel
de stapel zelf groeit omhoog,

595
00:27:36,300 --> 00:27:39,590
zodra je spullen hebt gezet in
het, het voor het ontwerp redenen,

596
00:27:39,590 --> 00:27:41,294
zet het geheugen van boven naar beneden.

597
00:27:41,294 --> 00:27:44,460
Dus als je hebt meer dan 12 bytes,
je gaat om te beginnen met bar overschrijven.

598
00:27:44,460 --> 00:27:47,280
Nu is dat een bug, maar het is
niet echt een groot probleem.

599
00:27:47,280 --> 00:27:51,130
Maar het is een groot probleem, want er is
meer dingen gaande in het geheugen.

600
00:27:51,130 --> 00:27:53,074
Dus hier is hoe we misschien
zet hello, om duidelijk te zijn.

601
00:27:53,074 --> 00:27:54,490
Als ik getypt in hallo de prompt.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash nul eindigt binnen
die 12 bytes, en we zijn super veilig.

603
00:27:59,330 --> 00:28:00,330
Alles is goed.

604
00:28:00,330 --> 00:28:03,020
Maar als ik iets typt
langer mogelijk is het

605
00:28:03,020 --> 00:28:05,860
gaat kruipen in bar ruimte.

606
00:28:05,860 --> 00:28:08,405
Maar erger nog, het blijkt
al die tijd,

607
00:28:08,405 --> 00:28:11,530
ook al hebben we nog nooit gesproken over
het, wordt de stapel gebruikt voor andere dingen.

608
00:28:11,530 --> 00:28:13,560
Het is niet alleen lokale variabelen.

609
00:28:13,560 --> 00:28:15,100
>> C is een zeer laag niveau taal.

610
00:28:15,100 --> 00:28:17,810
En het soort van geheim
gebruikt de stapel ook

611
00:28:17,810 --> 00:28:21,260
om te onthouden wanneer een
functie wordt aangeroepen, welke

612
00:28:21,260 --> 00:28:26,040
het adres van de vorige functie,
dus het kan terug naar die functie springen.

613
00:28:26,040 --> 00:28:29,980
Dus als belangrijkste gesprekken te wisselen, onder
de dingen die duwde op de stapel

614
00:28:29,980 --> 00:28:34,380
zijn niet alleen swaps lokale variabelen,
of ook in het geheim duwde zijn argumenten,

615
00:28:34,380 --> 00:28:37,510
op de stapel zoals weergegeven
door hier de plak rood,

616
00:28:37,510 --> 00:28:40,520
is het adres van de belangrijkste fysisch
in het geheugen van uw computer,

617
00:28:40,520 --> 00:28:44,180
zodat wanneer swap wordt uitgevoerd, de computer
weet dat ik nodig om terug te gaan naar de belangrijkste

618
00:28:44,180 --> 00:28:46,760
en eindig het uitvoeren van de belangrijkste functie.

619
00:28:46,760 --> 00:28:51,960
Dus dit is nu gevaarlijk, omdat als
de gebruiker types in goed meer dan hallo,

620
00:28:51,960 --> 00:28:57,030
zodanig dat invoer van de gebruiker clobbers
of overschrijft dat rode gedeelte,

621
00:28:57,030 --> 00:28:59,820
logisch als de computer
gewoon blindelings veronderstellen

622
00:28:59,820 --> 00:29:03,830
dat de bytes die rode slice zijn
het adres waar het zou moeten terugkeren,

623
00:29:03,830 --> 00:29:09,020
wat als de tegenstander is slim genoeg of
gelukkig genoeg om een ​​opeenvolging van bytes gezet

624
00:29:09,020 --> 00:29:13,450
daar dat eruit ziet als een adres,
maar het is het adres van de code

625
00:29:13,450 --> 00:29:18,730
dat hij wil dat de computer
uit te voeren in plaats van de belangrijkste?

626
00:29:18,730 --> 00:29:21,670
>> Met andere woorden, als wat
gebruiker te typen op de prompt,

627
00:29:21,670 --> 00:29:23,850
is niet alleen iets
onschuldig als hello,

628
00:29:23,850 --> 00:29:28,210
maar het is eigenlijk de code dat is gelijk
om alle bestanden van deze gebruiker wilt verwijderen?

629
00:29:28,210 --> 00:29:30,060
Of e-mail hun wachtwoord voor mij?

630
00:29:30,060 --> 00:29:31,940
Of beginnen te loggen hun
toetsaanslagen, toch?

631
00:29:31,940 --> 00:29:34,920
Er is een manier, laten we vandaag bepalen,
dat ze kon typen in niet alleen gedag

632
00:29:34,920 --> 00:29:36,711
wereld of hun naam,
ze konden wezen

633
00:29:36,711 --> 00:29:39,570
passeren in de code, nullen en
degenen, die de computer

634
00:29:39,570 --> 00:29:43,450
fouten voor zowel code en een adres.

635
00:29:43,450 --> 00:29:48,950
Dus hoewel enigszins abstracte wijze als de
types gebruiker genoeg hoor en wederhoor code

636
00:29:48,950 --> 00:29:52,330
dat we hier zullen generaliseren
A. A is aanval of tegenstanders.

637
00:29:52,330 --> 00:29:53,140
Dus gewoon slechte dingen.

638
00:29:53,140 --> 00:29:55,306
We niet de zorg over de
nummers of de nullen of degenen

639
00:29:55,306 --> 00:29:59,470
vandaag de dag, zodat je uiteindelijk
overschrijven dat rode gedeelte,

640
00:29:59,470 --> 00:30:01,580
merken dat reeks bytes.

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

642
00:30:05,020 --> 00:30:08,960
En nu als Wikipedia's artikel hier
heeft voorgesteld, als je nu echt beginnen

643
00:30:08,960 --> 00:30:12,460
labelen van de bytes in uw computer
geheugen, wat het artikel Wikipedia is

644
00:30:12,460 --> 00:30:19,060
voorstelt, is dat wat als het adres
van die linksboven byte is 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Met andere woorden, indien het bad guy is
slim genoeg om met zijn of haar code

646
00:30:22,200 --> 00:30:26,650
om daadwerkelijk zet hier een nummer dat
overeen met het adres van de code

647
00:30:26,650 --> 00:30:29,180
hij geïnjecteerd
in de computer, je

648
00:30:29,180 --> 00:30:31,050
kan de computer truc
in iets te doen.

649
00:30:31,050 --> 00:30:34,140
Het verwijderen van bestanden, e-mailen
dingen, snuiven uw verkeer,

650
00:30:34,140 --> 00:30:36,710
letterlijk alles zou kunnen zijn
geïnjecteerd in de computer.

651
00:30:36,710 --> 00:30:39,220
En zo een buffer overflow
aanval in de kern

652
00:30:39,220 --> 00:30:43,530
is gewoon een stom, stom
dwingende van een array die

653
00:30:43,530 --> 00:30:45,840
had niet de grenzen gecontroleerd.

654
00:30:45,840 --> 00:30:48,850
En dit is wat is super gevaarlijk
en tegelijkertijd super krachtig

655
00:30:48,850 --> 00:30:52,560
in C is dat we hebben inderdaad
toegang tot overal in het geheugen.

656
00:30:52,560 --> 00:30:55,320
Het is aan ons, de programmeurs,
die de oorspronkelijke code te schrijven

657
00:30:55,320 --> 00:30:59,330
aan de darn lengte van een eventuele controle
arrays die wij manipuleren.

658
00:30:59,330 --> 00:31:00,750
Dus om duidelijk te zijn, wat is de oplossing?

659
00:31:00,750 --> 00:31:03,190
Als we teruggaan naar deze
code, zou ik niet alleen

660
00:31:03,190 --> 00:31:08,000
verandert de lengte van de bar, wat
anders moet ik controleren?

661
00:31:08,000 --> 00:31:10,620
Wat moet ik doen om
volledig te voorkomen deze aanval?

662
00:31:10,620 --> 00:31:14,110
Ik wil niet alleen maar blindelings zeggen
dat je zoveel bytes moeten kopiëren

663
00:31:14,110 --> 00:31:16,140
zoals de lengte van de balk.

664
00:31:16,140 --> 00:31:18,910
Ik wil zeggen, kopiëren als
veel bytes net als in de bar

665
00:31:18,910 --> 00:31:24,090
tot aan de toegewezen
geheugen, of 12 maximaal.

666
00:31:24,090 --> 00:31:27,450
Dus ik moet een soort van als voorwaarde
dat doet controleert de lengte van de bar,

667
00:31:27,450 --> 00:31:32,800
maar als het 12, we gewoon moeilijk code overschrijdt
12 als de maximaal mogelijke afstand.

668
00:31:32,800 --> 00:31:35,910
Anders wordt de zogenaamde buffer
overflow aanval kan gebeuren.

669
00:31:35,910 --> 00:31:38,451
Onderaan deze slides,
als je nieuwsgierig bent om meer te lezen

670
00:31:38,451 --> 00:31:41,200
is de eigenlijke oorspronkelijke artikel
als je wilt om een ​​kijkje te nemen.

671
00:31:41,200 --> 00:31:44,550
>> Maar nu, onder de prijzen
hier betaald was inefficiënties.

672
00:31:44,550 --> 00:31:46,680
Dus dat was een snelle
lage niveau kijken naar wat

673
00:31:46,680 --> 00:31:49,709
problemen kunnen ontstaan ​​nu dat we
hebben toegang tot het geheugen van de computer.

674
00:31:49,709 --> 00:31:51,750
Maar een ander probleem dat we
al op maandag struikelde

675
00:31:51,750 --> 00:31:53,800
was gewoon de inefficiëntie
van een gekoppelde lijst.

676
00:31:53,800 --> 00:31:56,019
We zijn terug naar de lineaire tijd.

677
00:31:56,019 --> 00:31:57,560
We hebben een aaneengesloten reeks niet meer.

678
00:31:57,560 --> 00:31:58,980
We hebben geen random access.

679
00:31:58,980 --> 00:32:00,710
We kunnen geen gebruik maken van vierkante haakjesnotering.

680
00:32:00,710 --> 00:32:04,590
We hebben letterlijk een tijdje lus
zoals degene die ik schreef een moment geleden.

681
00:32:04,590 --> 00:32:09,740
Maar op maandag, we beweerden dat we kunnen
kruipen terug in het rijk van de efficiëntie

682
00:32:09,740 --> 00:32:13,040
het bereiken van iets dat
logaritmische misschien, of best nog,

683
00:32:13,040 --> 00:32:16,120
misschien zelfs iets dat
zogenaamde constante tijd.

684
00:32:16,120 --> 00:32:19,840
Dus hoe kunnen we dat doen met behulp van deze nieuwe
gereedschap, deze adressen, die pointers,

685
00:32:19,840 --> 00:32:22,210
en threading dingen van onze eigen?

686
00:32:22,210 --> 00:32:23,960
Nou, stel dat
Hier, dit zijn een stelletje

687
00:32:23,960 --> 00:32:27,170
van de nummers die we willen opslaan in een
datastructuur en zoeken efficiënt.

688
00:32:27,170 --> 00:32:30,960
We kunnen absoluut terugspoelen tot week
twee, gooi deze in een array,

689
00:32:30,960 --> 00:32:33,150
en zoeken ze met behulp van binaire zoeken.

690
00:32:33,150 --> 00:32:34,040
Verdeel en heers.

691
00:32:34,040 --> 00:32:37,720
En in feite schreef
binary search in PSET3,

692
00:32:37,720 --> 00:32:40,100
waar u de vondst programma uitgevoerd.

693
00:32:40,100 --> 00:32:40,890
Maar weet je wat.

694
00:32:40,890 --> 00:32:45,060
Er is een soort van een meer
slimme manier om dit te doen.

695
00:32:45,060 --> 00:32:47,390
Het is een beetje meer
geavanceerd en wellicht

696
00:32:47,390 --> 00:32:50,830
laat ons toe om te zien waarom binaire
zoeken is zo veel sneller.

697
00:32:50,830 --> 00:32:52,980
Laten we eerst eens introduceren
het begrip boom.

698
00:32:52,980 --> 00:32:54,730
Die ook al in
werkelijkheid bomen soort

699
00:32:54,730 --> 00:32:57,730
groeien als deze, in de wereld van de computer
wetenschap zij soort neerwaartse groeien

700
00:32:57,730 --> 00:33:00,830
als een stamboom, waar je
uw grootouders of overgrootouders

701
00:33:00,830 --> 00:33:04,580
of wat aan de top, de patriarch en
de matriarch van de familie, maar een

702
00:33:04,580 --> 00:33:07,930
zogenaamde root node hieronder
die zijn kinderen,

703
00:33:07,930 --> 00:33:11,442
waaronder zijn de kinderen, of
haar nakomelingen in het algemeen.

704
00:33:11,442 --> 00:33:13,400
En iedereen opknoping uit
de onderkant van de familie

705
00:33:13,400 --> 00:33:16,070
tree, naast de
jongste in het gezin,

706
00:33:16,070 --> 00:33:19,520
kan ook gewoon generiek zijn
genaamd de bladeren van de boom.

707
00:33:19,520 --> 00:33:21,800
>> Dus dit is gewoon een stelletje
woorden en definities

708
00:33:21,800 --> 00:33:25,790
voor iets genaamd een boom in de computer
wetenschap, net als een stamboom.

709
00:33:25,790 --> 00:33:28,770
Maar er is liefhebber incarnaties
bomen, waarvan

710
00:33:28,770 --> 00:33:30,780
wordt een binaire zoekboom.

711
00:33:30,780 --> 00:33:34,380
En u kunt soort tease
behalve wat dit ding doet.

712
00:33:34,380 --> 00:33:37,180
Nou, het is binaire in welke zin?

713
00:33:37,180 --> 00:33:41,455
Waar komt de binaire vandaan hier?

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
Het is niet zozeer een van beide of.

717
00:33:47,210 --> 00:33:52,000
Het is meer dat elk van de knooppunten geen
meer dan twee kinderen, zoals we hier zien.

718
00:33:52,000 --> 00:33:54,990
In het algemeen, een tree-- en
je ouders en grootouders

719
00:33:54,990 --> 00:33:57,640
kan zo veel kinderen hebben of
kleinkinderen als ze eigenlijk willen,

720
00:33:57,640 --> 00:34:00,820
en zo bijvoorbeeld er drie hebben we
kinderen uit dat rechterhand knooppunt

721
00:34:00,820 --> 00:34:05,480
maar in een binaire boom, een knooppunt
nul, één of twee kinderen maximaal.

722
00:34:05,480 --> 00:34:08,496
En dat is een mooie eigenschap,
want als het wordt afgedekt door twee,

723
00:34:08,496 --> 00:34:10,620
we gaan om te kunnen
een beetje log base twee

724
00:34:10,620 --> 00:34:11,975
actie gebeurt hier uiteindelijk.

725
00:34:11,975 --> 00:34:13,350
Dus we hebben iets logaritmische.

726
00:34:13,350 --> 00:34:14,558
Maar meer op dat in een moment.

727
00:34:14,558 --> 00:34:19,810
Zoekboom betekent dat de nummers zijn
zodanig ingericht dat de linker kind

728
00:34:19,810 --> 00:34:22,429
waarde groter is dan de wortel.

729
00:34:22,429 --> 00:34:26,010
En zijn recht kind
groter dan de wortel.

730
00:34:26,010 --> 00:34:29,290
Met andere woorden, als u een van de te nemen
knooppunten, de cirkels in deze foto,

731
00:34:29,290 --> 00:34:31,840
en kijkt naar zijn linker
kind en zijn recht kind,

732
00:34:31,840 --> 00:34:34,739
het eerste lager dient te zijn dan,
de tweede moet groter zijn dan.

733
00:34:34,739 --> 00:34:36,159
Dus sanity check 55.

734
00:34:36,159 --> 00:34:37,780
Het linker kind is 33.

735
00:34:37,780 --> 00:34:38,620
Het is minder dan.

736
00:34:38,620 --> 00:34:40,929
55, haar recht kind is 77.

737
00:34:40,929 --> 00:34:41,783
Het is groter dan.

738
00:34:41,783 --> 00:34:43,199
En dat is een recursieve definitie.

739
00:34:43,199 --> 00:34:46,480
Konden we elk een van die controleren
knooppunten en hetzelfde patroon zou houden.

740
00:34:46,480 --> 00:34:49,389
>> Dus wat is leuk in een
binaire zoekboom, is

741
00:34:49,389 --> 00:34:52,204
dat men, kunnen we het uit te voeren
met een structuur, net als dit.

742
00:34:52,204 --> 00:34:54,620
En hoewel we gooien
veel van de structuren op uw,

743
00:34:54,620 --> 00:34:56,560
ze zijn enigszins
intuïtieve nu hopelijk.

744
00:34:56,560 --> 00:35:00,570
De syntax is nog steeds geheimzinnig zeker,
maar de inhoud van een knooppunt in dit

745
00:35:00,570 --> 00:35:02,786
context-- en we houden
gebruik van het woord knooppunt

746
00:35:02,786 --> 00:35:04,910
of het een rechthoek
op het scherm of een cirkel,

747
00:35:04,910 --> 00:35:08,970
het is gewoon een aantal generieke container,
in dit geval van een boom, zoals die

748
00:35:08,970 --> 00:35:11,780
we zagen we een integer nodig
in elk van de knooppunten

749
00:35:11,780 --> 00:35:15,460
en dan moet ik twee pointers wijzen
naar links kind en het juiste kind,

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

751
00:35:16,590 --> 00:35:20,730
Dus dat is hoe we misschien
implementeren die in een structuur.

752
00:35:20,730 --> 00:35:22,315
En hoe zou ik kunnen implementeren in de code?

753
00:35:22,315 --> 00:35:26,730
Nou, laten we eens een snelle
kijk naar dit kleine voorbeeld.

754
00:35:26,730 --> 00:35:29,820
Het is niet functioneel, maar ik heb
gekopieerd en geplakt die structuur.

755
00:35:29,820 --> 00:35:33,510
En als mijn functie een binaire
zoeken boom zoeken genoemd,

756
00:35:33,510 --> 00:35:36,980
en dit duurt twee argumenten,
N een integer en een pointer

757
00:35:36,980 --> 00:35:41,400
een knooppunt, zodat een pointer naar de boom
of een verwijzing naar de wortel van een boom,

758
00:35:41,400 --> 00:35:43,482
Hoe ga ik over op zoek naar N?

759
00:35:43,482 --> 00:35:45,440
Nou, ten eerste, want ik ben
omgaan met pointers,

760
00:35:45,440 --> 00:35:46,750
Ik ga een sanity check doen.

761
00:35:46,750 --> 00:35:54,279
Als boom gelijken gelijk aan nul, is N
in deze boom dan niet in deze boom?

762
00:35:54,279 --> 00:35:55,070
Het kan niet, toch?

763
00:35:55,070 --> 00:35:56,870
Als ik voorbij null,
er is niets daar.

764
00:35:56,870 --> 00:35:59,230
Ik kan net zo goed
blindelings zeggen return false.

765
00:35:59,230 --> 00:36:04,050
Als je me niets, ik kan toch niet
vindt een aantal N. Dus wat zou ik

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

767
00:36:04,750 --> 00:36:12,830
Ik ga ook anders als N zeggen
minder dan wat er bij de boom knooppunt

768
00:36:12,830 --> 00:36:16,300
dat ik heb ingeleverd N waarde.

769
00:36:16,300 --> 00:36:20,270
Met andere woorden, wanneer het aantal ik
zoekt, N lager is dan de knoop

770
00:36:20,270 --> 00:36:21,340
dat ik ben op zoek naar.

771
00:36:21,340 --> 00:36:23,190
En het knooppunt ik zoek
op boom wordt genoemd,

772
00:36:23,190 --> 00:36:26,370
en op te roepen uit het vorige voorbeeld
de waarde om in een pointer,

773
00:36:26,370 --> 00:36:28,310
Ik gebruik de pijl notatie.

774
00:36:28,310 --> 00:36:35,960
Als n kleiner is dan tree arrow
N, ik wil conceptueel gaan links.

775
00:36:35,960 --> 00:36:38,590
Hoe kan ik de uitdrukkelijke searching over?

776
00:36:38,590 --> 00:36:41,560
Om duidelijk te zijn, als dit
de foto in kwestie,

777
00:36:41,560 --> 00:36:44,612
en ik heb doorgegeven dat bovenste
arrow dat is naar beneden gericht.

778
00:36:44,612 --> 00:36:45,570
Dat is mijn boom pointer.

779
00:36:45,570 --> 00:36:48,060
Ik wees naar de wortel van de boom.

780
00:36:48,060 --> 00:36:52,100
En ik ben op zoek zeggen, voor
het nummer 44, willekeurig.

781
00:36:52,100 --> 00:36:55,300
44 is kleiner dan of
groter dan 55 natuurlijk?

782
00:36:55,300 --> 00:36:56,360
Dus het is minder dan.

783
00:36:56,360 --> 00:36:58,760
En dus dit als voorwaarde geldt.

784
00:36:58,760 --> 00:37:03,981
Dus conceptueel, wat wil ik aan
zoek volgende als ik ben op zoek naar 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Precies, ik wil
zoeken in de linker kind,

788
00:37:11,100 --> 00:37:12,789
of de linker sub-boom van deze foto.

789
00:37:12,789 --> 00:37:14,830
En in feite, laat me door
de foto hier beneden

790
00:37:14,830 --> 00:37:17,770
voor slechts een moment, omdat
Ik kan dit niet uitkrabben.

791
00:37:17,770 --> 00:37:21,150
Als ik begin hier op 55 en
Ik weet dat de waarde 44

792
00:37:21,150 --> 00:37:23,180
Ik ben op zoek naar is om
links, het is een soort

793
00:37:23,180 --> 00:37:26,010
van zoals scheuren het telefoonboek in
de helft of scheuren van de boom in de helft.

794
00:37:26,010 --> 00:37:29,660
Ik heb niet langer zorgen te maken over
deze hele helft van de boom.

795
00:37:29,660 --> 00:37:33,270
En toch, vreemd genoeg in termen van de
structuur, dit ding hier dat

796
00:37:33,270 --> 00:37:36,682
begint met 33, die zich
is een binaire zoekboom.

797
00:37:36,682 --> 00:37:39,890
Ik zei het woord recursieve voordat omdat
inderdaad dit is een gegevensstructuur die

798
00:37:39,890 --> 00:37:41,707
per definitie recursieve.

799
00:37:41,707 --> 00:37:44,540
Je zou een boom die dit hebben
groot, maar ieder van haar kinderen

800
00:37:44,540 --> 00:37:46,870
vertegenwoordigt een boom net iets kleiner.

801
00:37:46,870 --> 00:37:50,910
In plaats van dat het opa
of oma, nu is het gewoon moeder

802
00:37:50,910 --> 00:37:54,300
of-- Ik kan niet say-- niet mom
of vader, dat zou raar zijn.

803
00:37:54,300 --> 00:37:59,000
In plaats van de twee kinderen is er
zou zijn als broer en zus.

804
00:37:59,000 --> 00:38:01,120
Een nieuwe generatie van de stamboom.

805
00:38:01,120 --> 00:38:02,900
Maar structureel, het is hetzelfde idee.

806
00:38:02,900 --> 00:38:06,790
En het blijkt dat ik een functie hebben
waarmee ik een binaire zoekopdracht kan zoeken

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

808
00:38:07,290 --> 00:38:08,680
Het is zoeken genoemd.

809
00:38:08,680 --> 00:38:17,870
Ik zoek naar N in boom pijl links
anders als N groter is dan de waarde

810
00:38:17,870 --> 00:38:18,870
dat ik momenteel op.

811
00:38:18,870 --> 00:38:20,800
55 in het verhaal een ogenblik geleden.

812
00:38:20,800 --> 00:38:23,780
Ik heb een functie genaamd
zoeken die ik kan gewoon

813
00:38:23,780 --> 00:38:29,660
passeren N deze en recursief zoeken
de sub-boom en net terug

814
00:38:29,660 --> 00:38:30,620
wat dat antwoord.

815
00:38:30,620 --> 00:38:33,530
Else Ik heb wat laatste base case kreeg hier.

816
00:38:33,530 --> 00:38:35,310
>> Wat is het laatste geval is?

817
00:38:35,310 --> 00:38:36,570
Boom is ofwel null.

818
00:38:36,570 --> 00:38:39,980
De waarde die ik ofwel zoek is
minder dan of groter dan die

819
00:38:39,980 --> 00:38:42,610
of gelijk aan.

820
00:38:42,610 --> 00:38:44,750
En ik kon gelijk zeggen
gelijk, maar het is logisch

821
00:38:44,750 --> 00:38:46,500
gelijk aan gewoon hier zeggen anders.

822
00:38:46,500 --> 00:38:49,150
Zo waar is hoe ik iets vind.

823
00:38:49,150 --> 00:38:51,710
Dus hopelijk is dit een
nog meer overtuigend voorbeeld

824
00:38:51,710 --> 00:38:54,900
dan de domme sigma-functie
we hebben een paar lezingen terug,

825
00:38:54,900 --> 00:38:58,360
waar het was net zo gemakkelijk om een ​​lus te gebruiken
optellen alle nummers een

826
00:38:58,360 --> 00:39:02,390
N. hier met een gegevensstructuur
dat zelf is recursief

827
00:39:02,390 --> 00:39:07,050
gedefinieerd en recursief getrokken, nu zijn we
hebben de mogelijkheid om onszelf te uiten

828
00:39:07,050 --> 00:39:09,780
in de code dat zichzelf is recursieve.

829
00:39:09,780 --> 00:39:12,580
Dus dit is exact dezelfde code hier.

830
00:39:12,580 --> 00:39:14,400
>> Dus wat andere problemen kunnen we oplossen?

831
00:39:14,400 --> 00:39:18,160
Dus snel een stap verwijderd van
bomen voor een ogenblik.

832
00:39:18,160 --> 00:39:20,130
Hier is, zeggen de Duitse vlag.

833
00:39:20,130 --> 00:39:22,020
En er is duidelijk een
patroon om deze vlag.

834
00:39:22,020 --> 00:39:23,811
En er is veel
vlaggen in de wereld die

835
00:39:23,811 --> 00:39:27,560
zijn zo simpel als dit in termen
hun kleuren en patronen.

836
00:39:27,560 --> 00:39:31,930
Maar stel dat wordt opgeslagen als een
GIF, of JPEG, of bitmap of een ping,

837
00:39:31,930 --> 00:39:34,240
een grafisch bestandsformaat
waarmee je bekend bent,

838
00:39:34,240 --> 00:39:36,460
waarvan sommige we
spelen met in PSET4.

839
00:39:36,460 --> 00:39:41,550
Dit lijkt niet zinvol te slaan
zwarte pixel, zwarte pixel, zwarte pixel,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, een hele hoop
zwarte pixels voor de eerste scanline,

841
00:39:44,790 --> 00:39:47,430
of rij, dan een hele hoop
hetzelfde, dan een hele hoop

842
00:39:47,430 --> 00:39:49,530
dezelfde, en vervolgens een
heleboel rode pixels,

843
00:39:49,530 --> 00:39:53,020
rode pixels, rode pixels, vervolgens geheel
stelletje gele pixels, geel, toch?

844
00:39:53,020 --> 00:39:55,050
>> Er is hier een dergelijke inefficiëntie.

845
00:39:55,050 --> 00:39:59,040
Hoe zou je intuïtief
comprimeren de Duitse vlag

846
00:39:59,040 --> 00:40:01,320
als de uitvoering ervan als een bestand?

847
00:40:01,320 --> 00:40:04,940
Net als wat informatie kunnen we niet
moeite het opslaan op de harde schijf in orde

848
00:40:04,940 --> 00:40:08,040
om ons bestand te verkleinen, zoals uit
een megabyte naar een kilobyte, iets

849
00:40:08,040 --> 00:40:09,430
kleiner?

850
00:40:09,430 --> 00:40:13,130
Waarin ligt de redundantie
hier om duidelijk te zijn?

851
00:40:13,130 --> 00:40:13,880
Wat zou je doen?

852
00:40:13,880 --> 00:40:14,380
Ja?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Precies.

855
00:40:21,970 --> 00:40:24,550
Waarom niet eerder dan herinneren
de kleur van elke pixel darn

856
00:40:24,550 --> 00:40:28,200
net zoals je doet in PSET4
met de bitmap-bestandsformaat,

857
00:40:28,200 --> 00:40:32,060
waarom ga je niet gewoon vertegenwoordigen de
meest linkse kolom van pixels, bijvoorbeeld

858
00:40:32,060 --> 00:40:35,370
een bos van zwarte pixels, een bos
rood, en een bos van geel,

859
00:40:35,370 --> 00:40:39,210
en dan gewoon een of andere manier coderen
idee van herhaal dit 100 keer

860
00:40:39,210 --> 00:40:41,020
of herhaal dit 1000 keer?

861
00:40:41,020 --> 00:40:43,430
Waarbij 100 of 1000 is
gewoon een integer, zodat u

862
00:40:43,430 --> 00:40:47,290
kan wegkomen met slechts een enkel nummer
in plaats van honderden of duizenden

863
00:40:47,290 --> 00:40:48,270
extra pixels.

864
00:40:48,270 --> 00:40:50,990
En inderdaad, dat is hoe we
kon de Duitse vlag te comprimeren.

865
00:40:50,990 --> 00:40:51,490
En

866
00:40:51,490 --> 00:40:53,470
Nu wat over de Franse vlag?

867
00:40:53,470 --> 00:40:58,930
En een beetje een soort van
mentale oefening, die de vlag

868
00:40:58,930 --> 00:41:01,040
Meer op de schijf worden gecomprimeerd?

869
00:41:01,040 --> 00:41:05,720
De Duitse vlag of de Franse
vlag, als we die aanpak?

870
00:41:05,720 --> 00:41:08,490
De Duitse vlag, omdat er
meer horizontale redundantie.

871
00:41:08,490 --> 00:41:12,190
En door het ontwerp, veel grafische bestanden
formaten inderdaad werken zoals scan-lijnen

872
00:41:12,190 --> 00:41:12,830
horizontaal.

873
00:41:12,830 --> 00:41:14,674
Ze kunnen werken
verticaal, maar de mensheid

874
00:41:14,674 --> 00:41:17,090
besloot jaren geleden dat we
over het algemeen denken aan dingen rij

875
00:41:17,090 --> 00:41:18,880
per rij in plaats van kolom voor kolom.

876
00:41:18,880 --> 00:41:20,820
Dus inderdaad als je
om te kijken naar het bestand

877
00:41:20,820 --> 00:41:24,670
grootte van een Duitse vlag en een Franse
vlag, mits de resolutie

878
00:41:24,670 --> 00:41:27,530
hetzelfde, dezelfde breedte
en hoogte, deze

879
00:41:27,530 --> 00:41:31,580
hier zal groter zijn, omdat je
moet je drie keer te herhalen.

880
00:41:31,580 --> 00:41:35,570
Je moet blauw, herhaal opgeven
uzelf, wit, herhaal je voor, rood,

881
00:41:35,570 --> 00:41:36,740
herhaal jezelf.

882
00:41:36,740 --> 00:41:39,000
Je kunt niet zomaar gaan allemaal
helemaal naar rechts.

883
00:41:39,000 --> 00:41:41,200
En als een terzijde, te maken
duidelijk de compressie

884
00:41:41,200 --> 00:41:43,910
overal, als deze
vier frames van een video-- u

885
00:41:43,910 --> 00:41:45,890
misschien herinneren dat een film
of video in het algemeen

886
00:41:45,890 --> 00:41:47,286
zoals 29 of 30 frames per seconde.

887
00:41:47,286 --> 00:41:50,410
Het is net een klein flip boek waar u
afbeelding, beeld, beeld, zien,

888
00:41:50,410 --> 00:41:54,410
het super snel, dus het ziet er net als
de acteurs op het scherm te bewegen.

889
00:41:54,410 --> 00:41:57,130
Hier is een hommel op
top van een bos bloemen.

890
00:41:57,130 --> 00:41:59,790
En al is het misschien soort zijn
moeilijk te zien op het eerste gezicht,

891
00:41:59,790 --> 00:42:04,020
de enige bewegen
deze film is de bijen.

892
00:42:04,020 --> 00:42:06,880
>> Wat is stom over het opslaan
video ongecomprimeerd?

893
00:42:06,880 --> 00:42:11,420
Het is een soort van een verspilling om video op te slaan
vier bijna identieke beelden die

894
00:42:11,420 --> 00:42:13,670
verschillen alleen in zoverre waar de bijen is.

895
00:42:13,670 --> 00:42:16,280
U kunt weggooien meest
van die informatie

896
00:42:16,280 --> 00:42:20,190
en herinner me alleen, bijvoorbeeld,
het eerste frame en het laatste frame,

897
00:42:20,190 --> 00:42:22,180
keyframes Als je hebt
ooit gehoord van het woord,

898
00:42:22,180 --> 00:42:24,337
en gewoon opslaan in de
midden waar het bij is.

899
00:42:24,337 --> 00:42:26,170
En je hoeft niet te
opslaan van alle van de roze,

900
00:42:26,170 --> 00:42:28,330
en de blauwe en de
groene waarden ook.

901
00:42:28,330 --> 00:42:31,200
Dus dit is alleen dat
compressie is overal.

902
00:42:31,200 --> 00:42:34,900
Het is een techniek die we vaak gebruiken
of voor lief nemen deze dagen.

903
00:42:34,900 --> 00:42:38,750
>> Maar hoe doe je tekst te comprimeren?

904
00:42:38,750 --> 00:42:40,450
Hoe ga je over de tekst te comprimeren?

905
00:42:40,450 --> 00:42:45,410
Nou ja, elk van de personages in
ASCII is een byte, of acht bits.

906
00:42:45,410 --> 00:42:47,360
En dat is een beetje dom, toch?

907
00:42:47,360 --> 00:42:51,160
Omdat je waarschijnlijk type A
en E en I en O en U veel

908
00:42:51,160 --> 00:42:55,270
vaker dan als W of Q of Z,
afhankelijk van de taal waarin

909
00:42:55,270 --> 00:42:56,610
je bent zeker het schrijven.

910
00:42:56,610 --> 00:42:59,600
En dus waarom maken we gebruik
acht bits voor elke letter,

911
00:42:59,600 --> 00:43:02,040
waaronder de minst
populaire brieven, toch?

912
00:43:02,040 --> 00:43:05,300
Waarom niet minder bits voor gebruik
de super populaire brieven,

913
00:43:05,300 --> 00:43:07,760
zoals E, de dingen die je denk
eerst in Rad van Fortuin,

914
00:43:07,760 --> 00:43:10,450
en gebruiken meer bits voor
de minder populaire letters?

915
00:43:10,450 --> 00:43:10,950
Waarom?

916
00:43:10,950 --> 00:43:13,130
Omdat we gewoon gaan
gebruiken ze minder vaak.

917
00:43:13,130 --> 00:43:15,838
>> Nou, het blijkt dat daar
zijn pogingen gedaan om dit te doen.

918
00:43:15,838 --> 00:43:18,630
En als u zich herinneren van de rang
school of middelbare school, morse code.

919
00:43:18,630 --> 00:43:20,400
Morsecode heeft puntjes
en streepjes die kunnen worden

920
00:43:20,400 --> 00:43:24,270
overgebracht langs een draad als
geluiden of signalen van een soort.

921
00:43:24,270 --> 00:43:25,930
Maar Morse code is een super schoon.

922
00:43:25,930 --> 00:43:29,010
Het is een soort van een binair systeem
dat u stippen of streepjes.

923
00:43:29,010 --> 00:43:30,977
Maar als je, bijvoorbeeld, twee punten.

924
00:43:30,977 --> 00:43:33,810
Of als u denkt terug aan de exploitant
die gaat als piep, piep, piep,

925
00:43:33,810 --> 00:43:36,760
piep, het raken van een kleine trekker
dat een signaal,

926
00:43:36,760 --> 00:43:40,360
Als u de ontvanger, krijgt twee
stippen, welke boodschap heb je gekregen?

927
00:43:40,360 --> 00:43:43,490
Volkomen willekeurig.

928
00:43:43,490 --> 00:43:44,450
>> Ik?

929
00:43:44,450 --> 00:43:45,060
Ik?

930
00:43:45,060 --> 00:43:47,500
Of wat about-- of ik?

931
00:43:47,500 --> 00:43:49,570
Misschien was het gewoon twee rechte E's?

932
00:43:49,570 --> 00:43:52,480
Dus er is dit probleem
van decodeerbaarheid met Morse

933
00:43:52,480 --> 00:43:54,890
code, waarbij tenzij
persoon kan u het bericht

934
00:43:54,890 --> 00:43:59,510
eigenlijk pauzeert zodat u kunt sorteren van
zien of horen de kloof tussen letters,

935
00:43:59,510 --> 00:44:02,990
het is niet voldoende om alleen
stuur dan een stroom van nullen en enen,

936
00:44:02,990 --> 00:44:05,610
of puntjes en streepjes,
omdat er onduidelijkheid.

937
00:44:05,610 --> 00:44:08,640
E is een enkele punt, dus als je
zie twee punten of hoort twee punten,

938
00:44:08,640 --> 00:44:11,254
misschien is het twee E's of misschien is het een I.

939
00:44:11,254 --> 00:44:13,670
Dus hebben we een systeem dat is een behoefte
iets slimmer dan dat.

940
00:44:13,670 --> 00:44:16,851
Dus een man genaamd Huffman jaar
geleden kwam met precies dit.

941
00:44:16,851 --> 00:44:18,600
Dus we gaan gewoon
om een ​​snelle blik te nemen

942
00:44:18,600 --> 00:44:20,114
hoe bomen zijn relevant voor deze.

943
00:44:20,114 --> 00:44:22,530
Veronderstel dat dit sommige
dom bericht dat u wilt verzenden,

944
00:44:22,530 --> 00:44:26,342
samengesteld alleen A, B, C's D's en E's,
maar er is veel redundantie hier.

945
00:44:26,342 --> 00:44:27,550
Het is niet de bedoeling in het Engels zijn.

946
00:44:27,550 --> 00:44:28,341
Het is niet versleuteld.

947
00:44:28,341 --> 00:44:30,540
Het is gewoon een dom bericht
met veel herhaling.

948
00:44:30,540 --> 00:44:34,010
Dus als je eigenlijk tellen alle
A, B, C's, D's en E's, hier

949
00:44:34,010 --> 00:44:34,890
de frequentie.

950
00:44:34,890 --> 00:44:37,800
20% van de letters
A, 45% van de letters

951
00:44:37,800 --> 00:44:39,660
zijn E's, en drie andere frequenties.

952
00:44:39,660 --> 00:44:41,960
We telden daar handmatig
en net deed de wiskunde.

953
00:44:41,960 --> 00:44:44,579
>> Dus het blijkt dat
Huffman, enige tijd geleden,

954
00:44:44,579 --> 00:44:46,620
besefte dat, je weet
wat, als ik begin gebouw

955
00:44:46,620 --> 00:44:51,172
een boom, of een bos van bomen, als je wil,
als volgt, kan ik het volgende doen.

956
00:44:51,172 --> 00:44:53,880
Ik ga een knooppunt aan elk geven
van de brieven die ik de zorg over

957
00:44:53,880 --> 00:44:55,530
en ik ga om te slaan
binnenin dat knooppunt

958
00:44:55,530 --> 00:44:58,610
de frequenties als floating point
waarde, of je kan het gebruiken van een N, ook,

959
00:44:58,610 --> 00:45:00,210
maar we zullen gewoon gebruik maken hier een vlotter.

960
00:45:00,210 --> 00:45:03,100
En het algoritme dat
stelde hij, is dat je

961
00:45:03,100 --> 00:45:07,210
neem dit woud van enkele knoop
bomen, dus super korte bomen,

962
00:45:07,210 --> 00:45:11,920
en je begint ze te verbinden met
nieuwe groepen, nieuwe ouders, als je wil.

963
00:45:11,920 --> 00:45:16,150
En u dit doen door te kiezen voor de
twee kleinste frequenties tegelijk.

964
00:45:16,150 --> 00:45:18,110
Dus nam ik de 10% en 10%.

965
00:45:18,110 --> 00:45:19,090
Ik maak een nieuw knooppunt.

966
00:45:19,090 --> 00:45:20,910
En ik roep de nieuwe knooppunt 20%.

967
00:45:20,910 --> 00:45:22,750
>> Die twee knooppunten combineer ik de volgende stap?

968
00:45:22,750 --> 00:45:23,810
Het is een beetje dubbelzinnig.

969
00:45:23,810 --> 00:45:26,643
Dus er is een hoekje gevallen
beschouwen, maar om dingen vrij te houden,

970
00:45:26,643 --> 00:45:29,300
Ik ga om uit te kiezen 20% -
Ik negeer nu de kinderen.

971
00:45:29,300 --> 00:45:33,640
Ik ga om uit te kiezen 20% en
15% en trekken twee nieuwe randen.

972
00:45:33,640 --> 00:45:35,624
En nu die twee knooppunten
ik logisch combineren?

973
00:45:35,624 --> 00:45:38,540
Negeer alle kinderen, alle
kleinkinderen, kijk maar naar de wortels

974
00:45:38,540 --> 00:45:39,070
nu.

975
00:45:39,070 --> 00:45:42,220
Welke twee knopen heb ik samen te binden?

976
00:45:42,220 --> 00:45:44,530
Punt twee en 0,35.

977
00:45:44,530 --> 00:45:45,890
Dus laat me trekken twee nieuwe randen.

978
00:45:45,890 --> 00:45:47,570
En dan heb ik maar één links.

979
00:45:47,570 --> 00:45:48,650
Dus hier is een boom.

980
00:45:48,650 --> 00:45:51,160
En het is met opzet opgesteld
te kijken soort van mooie,

981
00:45:51,160 --> 00:45:55,870
maar merken dat de randen
Ook bestempeld nul en één.

982
00:45:55,870 --> 00:45:59,510
Dus alle linkerranden nul
willekeurig, maar consequent.

983
00:45:59,510 --> 00:46:01,170
Alle rechterrand zijn degenen.

984
00:46:01,170 --> 00:46:05,070
>> En dus wat Hoffman voorgesteld is,
als je wilt een B vertegenwoordigen,

985
00:46:05,070 --> 00:46:10,080
plaats geven het aantal 66 als
Een ASCII die hele acht bits,

986
00:46:10,080 --> 00:46:13,360
weet je wat, gewoon winkel
het patroon nul, nul, nul,

987
00:46:13,360 --> 00:46:17,030
nul, want dat is de weg
uit mijn boom, Mr. Huffman de boom,

988
00:46:17,030 --> 00:46:18,600
aan het blad van de wortel.

989
00:46:18,600 --> 00:46:20,970
Als je wilt naar een winkel
E daarentegen niet

990
00:46:20,970 --> 00:46:26,290
stuur acht bits die een E. vertegenwoordigen
In plaats daarvan stuurt welk patroon bits?

991
00:46:26,290 --> 00:46:26,890
Een.

992
00:46:26,890 --> 00:46:30,410
En wat is er leuk is aan dit
dat E is de meest populaire letter,

993
00:46:30,410 --> 00:46:32,340
en je bent met behulp van de
kortste code voor het.

994
00:46:32,340 --> 00:46:34,090
De volgende meest populaire
brief lijkt alsof het

995
00:46:34,090 --> 00:46:37,380
was A. En hoeveel bits
heeft hij voorgesteld met behulp van voor dat?

996
00:46:37,380 --> 00:46:38,270
Nul, één.

997
00:46:38,270 --> 00:46:41,060
>> En omdat het uitgevoerd
als deze boom, voor nu

998
00:46:41,060 --> 00:46:43,350
laat me bepalen is er
geen dubbelzinnigheid zoals in Morse

999
00:46:43,350 --> 00:46:46,090
code, omdat alle
brieven u de zorg over

1000
00:46:46,090 --> 00:46:48,780
aan het einde van deze randen.

1001
00:46:48,780 --> 00:46:50,580
Dus dat is slechts een
toepassing van een boom.

1002
00:46:50,580 --> 00:46:52,538
Dit is-- en ik zal zwaaien
mijn hand op deze manier waarop u

1003
00:46:52,538 --> 00:46:55,570
kan dit implementeren als C constructie.

1004
00:46:55,570 --> 00:46:58,260
We hoeven alleen maar te combineren
een symbool, zoals een char,

1005
00:46:58,260 --> 00:46:59,910
en de frequentie links en rechts.

1006
00:46:59,910 --> 00:47:02,510
Maar laten we eens kijken naar twee
laatste voorbeelden die je zult

1007
00:47:02,510 --> 00:47:06,070
behoorlijk vertrouwd met na
quiz nul probleem van de vijf.

1008
00:47:06,070 --> 00:47:09,210
>> Dus er is de datastructuur
bekend als een hashtabel.

1009
00:47:09,210 --> 00:47:12,247
En een hash-tabel is een soort van
afkoelen doordat het bakken.

1010
00:47:12,247 --> 00:47:14,830
En stel dat er vier emmers
hier, slechts vier spaties.

1011
00:47:14,830 --> 00:47:20,830
Hier is een spel kaarten, en hier is
club, spade, club, diamanten, club,

1012
00:47:20,830 --> 00:47:25,960
diamanten, club, diamanten,
clubs-- dus dit is het willekeurig.

1013
00:47:25,960 --> 00:47:30,330
Harten, Hearts-- dus ik ben
bucketizing alle ingangen in.

1014
00:47:30,330 --> 00:47:32,430
En een hash table behoeften
te kijken naar uw input,

1015
00:47:32,430 --> 00:47:34,850
en dan zet het in een bepaalde
plaats op basis van wat je ziet.

1016
00:47:34,850 --> 00:47:35,600
Het is een algoritme.

1017
00:47:35,600 --> 00:47:37,980
En ik was met behulp van een super
eenvoudige visuele algoritme.

1018
00:47:37,980 --> 00:47:40,030
Het moeilijkste deel van die
herinneren wat de foto's waren.

1019
00:47:40,030 --> 00:47:41,590
En dan is er nog vier in totaal dingen.

1020
00:47:41,590 --> 00:47:45,440
>> Nu werden de stapels groeien, waarbij
is een bewuste ontwerp ding hier.

1021
00:47:45,440 --> 00:47:46,540
Maar wat zou ik doen?

1022
00:47:46,540 --> 00:47:49,080
Dus eigenlijk hier hebben we een
stelletje oude school examen boeken.

1023
00:47:49,080 --> 00:47:51,240
Stel dat een stelletje
studenten namen zijn hier.

1024
00:47:51,240 --> 00:47:52,570
Hier is een groter hash tafel.

1025
00:47:52,570 --> 00:47:54,867
In plaats van vier emmers,
Ik heb, laten we zeggen 26.

1026
00:47:54,867 --> 00:47:57,950
En we niet willen gaan lenen 26
dingen van buiten [? Annenberg?], Dus

1027
00:47:57,950 --> 00:48:00,289
hier is vijf die vertegenwoordigen
A tot Z. En als ik

1028
00:48:00,289 --> 00:48:03,580
zie een leerling wiens achternaam begint met A,
Ik ga naar zijn of haar quiz daar te zetten.

1029
00:48:03,580 --> 00:48:08,850
Als iemand begint met C, daar,
A-- eigenlijk niet willen doen.

1030
00:48:08,850 --> 00:48:10,060
B gaat over hier.

1031
00:48:10,060 --> 00:48:13,390
Dus ik heb A en B en C. En
nu hier is nog een student.

1032
00:48:13,390 --> 00:48:16,212
Maar als dit hash tafel
uitgevoerd met een matrix,

1033
00:48:16,212 --> 00:48:17,920
Ik ben soort geschroefd
op dit punt, toch?

1034
00:48:17,920 --> 00:48:19,510
Ik heb soort om dit ergens te zetten.

1035
00:48:19,510 --> 00:48:24,380
>> Dus een manier waarop ik kan dit op te lossen is, alle
rechts, A is druk, B bezet is, C is bezet.

1036
00:48:24,380 --> 00:48:28,880
Ik ga hem in D. zetten Dus op
eerste, heb ik willekeurig direct toegang

1037
00:48:28,880 --> 00:48:31,064
elk van de bakken voor de leerlingen.

1038
00:48:31,064 --> 00:48:33,230
Maar nu is het soort decentrale
iets lineaire,

1039
00:48:33,230 --> 00:48:36,750
want als ik wil om te zoeken naar iemand
waarvan de naam begint met A, controleer ik hier.

1040
00:48:36,750 --> 00:48:38,854
Maar indien dit niet het A
student Ik ben op zoek naar,

1041
00:48:38,854 --> 00:48:41,520
Ik heb soort te beginnen met het controleren
de emmers, want wat ik deed

1042
00:48:41,520 --> 00:48:44,530
was een soort van lineair
sonde de gegevensstructuur.

1043
00:48:44,530 --> 00:48:47,710
Een domme manier om te zeggen kijk maar
voor de eerste beschikbare opening,

1044
00:48:47,710 --> 00:48:51,850
en bevestigd op een plan B, zogezegd,
of plan D in dit geval de waarde

1045
00:48:51,850 --> 00:48:53,340
op die locatie plaats.

1046
00:48:53,340 --> 00:48:56,470
Dit is gewoon zo dat als je hebt
kreeg 26 locaties en geen studenten

1047
00:48:56,470 --> 00:49:00,600
met de naam Q of Z, of iets dergelijks
dat, in ieder geval dat je het gebruik van de ruimte.

1048
00:49:00,600 --> 00:49:03,140
>> Maar we hebben al meer gezien
slimme oplossingen hier, toch?

1049
00:49:03,140 --> 00:49:04,870
Wat zou je doen in plaats
als je een aanrijding?

1050
00:49:04,870 --> 00:49:06,670
Als twee mensen hebben
de naam A, wat zou

1051
00:49:06,670 --> 00:49:09,160
hebben een slimmere of meer geweest
intuïtieve oplossing dan alleen

1052
00:49:09,160 --> 00:49:12,840
putting Een waarbij D hoort te zijn?

1053
00:49:12,840 --> 00:49:14,810
Waarom heb ik niet zomaar gaan
buiten [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
zoals malloc, een ander knooppunt, zet het
hier, en vervolgens dat een student hier.

1055
00:49:19,960 --> 00:49:22,120
Zodat ik in wezen
een soort van een array,

1056
00:49:22,120 --> 00:49:25,590
of misschien meer elegant als we
begint een gekoppelde lijst te zien.

1057
00:49:25,590 --> 00:49:29,520
>> En zo een hash-tabel is een structuur
dat kan er net als dit,

1058
00:49:29,520 --> 00:49:33,900
maar slim, je iets te noemen
aparte chaining, waarbij een hash table

1059
00:49:33,900 --> 00:49:38,340
eenvoudigweg een array, elke
waarvan de elementen geen getal,

1060
00:49:38,340 --> 00:49:40,470
is zelf een gelinkte lijst.

1061
00:49:40,470 --> 00:49:45,080
Zodat je super snelle toegang
beslissen waar je waarde hash aan.

1062
00:49:45,080 --> 00:49:48,059
Net als met de kaarten bijvoorbeeld,
Ik heb super snelle beslissingen.

1063
00:49:48,059 --> 00:49:49,600
Harten gaat hier, diamanten gaat hier.

1064
00:49:49,600 --> 00:49:52,180
Same here, A gaat hier,
D gaat hier, B komt hier.

1065
00:49:52,180 --> 00:49:55,740
Zo super snel look-ups, en als
je toevallig te lopen in een zaak

1066
00:49:55,740 --> 00:49:59,429
waar je hebt botsingen, twee
mensen met dezelfde naam, nou dan

1067
00:49:59,429 --> 00:50:00,970
je gewoon beginnen met elkaar te koppelen.

1068
00:50:00,970 --> 00:50:03,900
En misschien heb je houd ze naargelang
alfabetisch, misschien heb je niet.

1069
00:50:03,900 --> 00:50:05,900
Maar in ieder geval nu hebben we de dynamiek.

1070
00:50:05,900 --> 00:50:10,250
Dus aan de ene kant hebben we super snel
constante tijd, en soort van lineaire tijd

1071
00:50:10,250 --> 00:50:14,110
die betrokken zijn als deze gekoppeld lijsten
begin een beetje lang te komen.

1072
00:50:14,110 --> 00:50:16,880
>> Dus dit soort een dwaas,
geeky grap jaar geleden.

1073
00:50:16,880 --> 00:50:19,590
Op de CS50 hack-a-thon,
wanneer de studenten in te checken,

1074
00:50:19,590 --> 00:50:22,040
sommige TF of CA jaarlijks
denkt dat het is grappig om te zetten

1075
00:50:22,040 --> 00:50:27,772
een teken als dit, waar het net
betekent dat als je naam begint met een A,

1076
00:50:27,772 --> 00:50:28,870
gaan op deze manier.

1077
00:50:28,870 --> 00:50:31,110
Als uw naam begint
met een B, ga dit-- OK,

1078
00:50:31,110 --> 00:50:33,290
het is grappig misschien later in het semester.

1079
00:50:33,290 --> 00:50:36,420
Maar er is een andere
manier om dit te doen, ook.

1080
00:50:36,420 --> 00:50:37,410
Kom terug naar dat.

1081
00:50:37,410 --> 00:50:38,600
>> Dus er is deze structuur.

1082
00:50:38,600 --> 00:50:40,420
En dit is onze laatste
structuur voor vandaag,

1083
00:50:40,420 --> 00:50:42,400
dat is zoiets als een trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, die om wat voor reden kort
voor het ophalen, maar het heet trie.

1085
00:50:47,140 --> 00:50:51,389
Dus een trie is een ander interessant
amalgaam van veel van deze ideeën.

1086
00:50:51,389 --> 00:50:52,930
Het is een boom, die we eerder hebben gezien.

1087
00:50:52,930 --> 00:50:54,180
Het is niet een binaire zoekboom.

1088
00:50:54,180 --> 00:50:58,410
Het is een boom met een aantal kinderen,
maar elk van de kinderen in een trie

1089
00:50:58,410 --> 00:51:00,090
een matrix.

1090
00:51:00,090 --> 00:51:04,790
Een array van grootte, zeg, 26 of misschien 27
als je wilt koppelteken namen ondersteunen

1091
00:51:04,790 --> 00:51:06,790
of apostrof in de namen van mensen.

1092
00:51:06,790 --> 00:51:08,280
>> En dus dit is een datastructuur.

1093
00:51:08,280 --> 00:51:10,290
En als je kijkt van boven
naar beneden, alsof je

1094
00:51:10,290 --> 00:51:13,710
kijk naar de bovenste knooppunt daar, M, is
wijzend naar de meest linkse ding daar,

1095
00:51:13,710 --> 00:51:17,665
dat dan A, X, W, E, L, L. Zo
slechts een gegevensstructuur die willekeurig

1096
00:51:17,665 --> 00:51:19,120
is het opslaan van namen van mensen.

1097
00:51:19,120 --> 00:51:25,720
En Maxwell wordt opgeslagen door net na
een pad van array array array.

1098
00:51:25,720 --> 00:51:30,050
Maar wat is verbazingwekkend om een ​​trie is
dat, terwijl een gelinkte lijst en zelfs

1099
00:51:30,050 --> 00:51:34,520
een array, de beste die we ooit hebben gekregen is
lineaire tijd of logaritmische tijd op zoek

1100
00:51:34,520 --> 00:51:35,600
iemand.

1101
00:51:35,600 --> 00:51:40,530
In deze gegevensstructuur van een trie, indien
mijn datastructuur heeft één naam erin

1102
00:51:40,530 --> 00:51:43,720
en ik ben op zoek naar Maxwell, ik ben
ga hem vrij snel te vinden.

1103
00:51:43,720 --> 00:51:47,910
Ik kijk voor M-A-X-W-E-L-L. Als
Deze gegevensstructuur, daarentegen,

1104
00:51:47,910 --> 00:51:51,830
indien N een miljoen, als er een
miljoen namen in deze datastructuur,

1105
00:51:51,830 --> 00:51:57,100
Maxwell is nog steeds gaat worden
detecteerbaar na slechts M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
stappen.

1107
00:51:58,090 --> 00:52:01,276
En David-- D-A-V-I-D stappen.

1108
00:52:01,276 --> 00:52:03,400
Met andere woorden, door het bouwen
een gegevensstructuur die

1109
00:52:03,400 --> 00:52:07,240
kreeg al deze arrays, die
zichzelf te onderhouden random access,

1110
00:52:07,240 --> 00:52:11,090
Ik kan beginnen te kijken van mensen
noem het gebruik van een hoeveelheid tijd die

1111
00:52:11,090 --> 00:52:14,340
evenredig aan het aantal niet
dingen in de gegevensstructuur,

1112
00:52:14,340 --> 00:52:16,330
als een miljoen bestaande namen.

1113
00:52:16,330 --> 00:52:20,135
De hoeveelheid tijd die het kost me te vinden
M-A-X-W-E-L-L in deze gegevensstructuur

1114
00:52:20,135 --> 00:52:22,260
niet evenredig met de
omvang van de datastructuur,

1115
00:52:22,260 --> 00:52:25,930
maar de lengte van de naam.

1116
00:52:25,930 --> 00:52:28,440
En realistisch de
namen we opzoeken

1117
00:52:28,440 --> 00:52:29,970
zijn nooit te lang gek zijn.

1118
00:52:29,970 --> 00:52:32,600
Misschien heeft iemand een 10 karakter
te noemen, 20 karakter naam.

1119
00:52:32,600 --> 00:52:33,900
Het is zeker eindig, toch?

1120
00:52:33,900 --> 00:52:37,110
Er is een mens op aarde die
de langste mogelijke naam,

1121
00:52:37,110 --> 00:52:39,920
maar die naam is een constante
waarde lengte, toch?

1122
00:52:39,920 --> 00:52:41,980
Het varieert niet in enige zin.

1123
00:52:41,980 --> 00:52:45,090
Dus op deze manier, we hebben
bereikte een datastructuur

1124
00:52:45,090 --> 00:52:47,800
die constante tijd look-up.

1125
00:52:47,800 --> 00:52:50,670
Het vergt wel een aantal stappen
afhankelijk van de lengte van de input,

1126
00:52:50,670 --> 00:52:54,250
maar niet het aantal naam
in de gegevensstructuur.

1127
00:52:54,250 --> 00:52:58,700
Dus als we het dubbele van het aantal namen
volgend jaar een miljard tot twee miljard,

1128
00:52:58,700 --> 00:53:03,720
bevinding Maxwell gaat nemen
precies hetzelfde aantal zeven stappen

1129
00:53:03,720 --> 00:53:04,650
om hem te vinden.

1130
00:53:04,650 --> 00:53:08,810
En dus we lijken te hebben bereikt
onze heilige graal van de looptijd.

1131
00:53:08,810 --> 00:53:10,860
>> Dus een paar aankondigingen.

1132
00:53:10,860 --> 00:53:11,850
Quiz nul is coming up.

1133
00:53:11,850 --> 00:53:14,600
Meer daarover op de website van de cursus
in de komende paar dagen.

1134
00:53:14,600 --> 00:53:17,120
Maandag lecture-- het is een vakantie
hier bij Harvard op maandag.

1135
00:53:17,120 --> 00:53:18,850
Het is niet in New Haven,
dus we nemen de klasse

1136
00:53:18,850 --> 00:53:20,310
naar New Haven voor de lezing op maandag.

1137
00:53:20,310 --> 00:53:22,550
Alles wordt gefilmd
en live gestreamd zoals gebruikelijk,

1138
00:53:22,550 --> 00:53:24,900
maar laten we eindigen vandaag
met een 30 seconden clip

1139
00:53:24,900 --> 00:53:26,910
genaamd "Diepe Gedachten"
door Daven Farnham, die

1140
00:53:26,910 --> 00:53:30,850
werd geïnspireerd vorig jaar op zaterdag
Night Live "Diepe Gedachten"

1141
00:53:30,850 --> 00:53:35,700
door Jack Handy, die
moet nu zinvol.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: En nu, "Deep
Gedachten "door Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tabel.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Oké, dat is het voor nu.

1147
00:53:47,660 --> 00:53:48,805
We zien je volgende week.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Om het in actie te zien.

1150
00:53:56,680 --> 00:53:58,304
Dus laten we een kijkje nemen op dat moment.

1151
00:53:58,304 --> 00:53:59,890
Dus hier hebben we een ongesorteerde array.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, kun je gaan en herstarten
dit voor slechts een seconde, alsjeblieft.

1153
00:54:04,860 --> 00:54:08,562
Oké, zijn camera's rollen, dus
actie wanneer je klaar, Doug bent, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Oké, dus wat we
hier hebben is een ongesorteerde array.

1155
00:54:11,020 --> 00:54:13,960
En ik heb alle elementen gekleurde
om aan te geven dat het in feite

1156
00:54:13,960 --> 00:54:14,460
ongesorteerd.

1157
00:54:14,460 --> 00:54:17,960
Zo herinneren dat het eerste wat we doen
is sorteren we de linkerhelft van de array.

1158
00:54:17,960 --> 00:54:20,630
Vervolgens sorteren we de juiste
de helft van de array.

1159
00:54:20,630 --> 00:54:22,830
En ya-da, da-ya, ya-da,
we ze samen te voegen.

1160
00:54:22,830 --> 00:54:24,520
En we hebben een volledig gesorteerde array.

1161
00:54:24,520 --> 00:54:25,360
Dus dat is hoe fuseren soort werkt.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, whoa, whoa,
knippen, snijden, knippen, snijden.

1163
00:54:27,109 --> 00:54:30,130
Doug, kun je niet zomaar ya-da, ya-da,
ya-da, je een weg door merge soort.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Ik heb net gedaan.

1165
00:54:31,970 --> 00:54:32,832
Het is goed.

1166
00:54:32,832 --> 00:54:33,540
We zijn goed om te gaan.

1167
00:54:33,540 --> 00:54:34,760
Laten we gewoon blijven rollen.

1168
00:54:34,760 --> 00:54:35,380
Dus hoe dan ook,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Je moet uitleggen
deze breder dan dat.

1170
00:54:37,800 --> 00:54:39,999
Dat is gewoon niet genoeg.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, we doen niet
nodig hebben om terug te gaan naar één.

1172
00:54:41,790 --> 00:54:42,350
Het is goed.

1173
00:54:42,350 --> 00:54:45,690
Maar goed, als we doorgaan met merge--
Ian, we zijn in het midden van filmen.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Ik weet het.

1175
00:54:46,612 --> 00:54:49,320
En we kunnen niet zomaar ya-da, ya-da,
ya-da, door het hele proces.

1176
00:54:49,320 --> 00:54:52,200
Je moet uitleggen hoe de
twee kanten krijgen samengevoegd.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Maar we hebben al
legde uit hoe de twee sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Je hebt net getoond
hen samenvoegen array.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Ze weten het proces.

1180
00:54:56,486 --> 00:54:57,172
Ze zijn prima.

1181
00:54:57,172 --> 00:54:58,380
We hebben meer dan het tien keer gegaan.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Je overgeslagen precies goed overheen.

1183
00:55:00,330 --> 00:55:03,360
We gaan terug naar een, je
kan je niet ya-da, ya-DA over.

1184
00:55:03,360 --> 00:55:05,480
Oké, terug naar één.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Ik heb om terug te gaan
door alle van de dia's?

1186
00:55:07,833 --> 00:55:08,332
Mijn God.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Het is net als de zesde keer, Ian.

1189
00:55:13,004 --> 00:55:13,940
Het is goed.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Oké.

1191
00:55:15,200 --> 00:55:16,590
Ben je klaar?

1192
00:55:16,590 --> 00:55:17,400
Grote.

1193
00:55:17,400 --> 00:55:18,950
Actie.