1
00:00:00,000 --> 00:00:00,030

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Oké.

3
00:00:00,460 --> 00:00:01,094
We zijn terug.

4
00:00:01,094 --> 00:00:04,260
Dus in dit segment op de programmering wat
Ik dacht dat we zouden doen, is een mix van de dingen.

5
00:00:04,260 --> 00:00:06,340
One, doe een beetje
iets hands-on,

6
00:00:06,340 --> 00:00:08,690
zij het met behulp van een meer speelse
programmering environment--

7
00:00:08,690 --> 00:00:11,620
een die demonstratief van
precies het soort ideeën

8
00:00:11,620 --> 00:00:14,220
we hebben het over,
maar een beetje meer formeel.

9
00:00:14,220 --> 00:00:18,200
Twee, kijken naar enkele van
de meer technische mogelijkheden

10
00:00:18,200 --> 00:00:21,520
dat een programmeur eigenlijk zou oplossen
problemen, zoals het zoeken probleem

11
00:00:21,520 --> 00:00:24,530
dat hebben we gekeken naar voor en
ook een meer fundamenteel

12
00:00:24,530 --> 00:00:26,020
interessant probleem van het sorteren.

13
00:00:26,020 --> 00:00:28,840
>> We zijn net uitgegaan van het begin te gaan
dat het telefoonboek werd opgelost,

14
00:00:28,840 --> 00:00:31,980
maar dat alleen is eigenlijk een soort van een
harde probleem met veel verschillende manieren

15
00:00:31,980 --> 00:00:32,479
op te lossen.

16
00:00:32,479 --> 00:00:34,366
Dus we zullen deze te gebruiken als
een categorie problemen

17
00:00:34,366 --> 00:00:36,740
vertegenwoordiger van de dingen die
kunnen worden opgelost in het algemeen.

18
00:00:36,740 --> 00:00:38,980
En dan zullen we praten
over in detail welke

19
00:00:38,980 --> 00:00:42,360
heten data structures--
liefhebber manieren, zoals gelinkte lijsten

20
00:00:42,360 --> 00:00:46,290
en hash tables en bomen die
een programmeur zou eigenlijk

21
00:00:46,290 --> 00:00:48,890
Gebruik en algemeen gebruik
op een whiteboard te schilderen

22
00:00:48,890 --> 00:00:51,840
een beeld van wat hij of zij
voorziet voor de uitvoering van

23
00:00:51,840 --> 00:00:52,980
een stukje software.

24
00:00:52,980 --> 00:00:55,130
>> Dus laten we de hands-on gedeelte eerste.

25
00:00:55,130 --> 00:01:00,090
Dus gewoon je handen vuil met een
milieu genoemd scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Dit is een tool die we gebruiken
in onze undergraduate klasse.

27
00:01:02,636 --> 00:01:04,510
Hoewel het is ontworpen
voor kinderen van 12 jaar en ouder,

28
00:01:04,510 --> 00:01:07,570
we gebruiken voor het up
een deel van dat nogal wat

29
00:01:07,570 --> 00:01:10,020
want het is een mooie, leuke
grafische manier van leren

30
00:01:10,020 --> 00:01:12,160
een beetje iets over programmeren.

31
00:01:12,160 --> 00:01:17,600
Dus ga naar die URL, waar u
moet een pagina te zien heel graag dit,

32
00:01:17,600 --> 00:01:23,330
en ga je gang en klik op
Word lid van Scratch rechtsboven

33
00:01:23,330 --> 00:01:28,300
en kies een gebruikersnaam en een
wachtwoord en uiteindelijk krijg je

34
00:01:28,300 --> 00:01:29,970
een account-- scratch.mit.edu.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Ik dacht dat ik dit als een
gelegenheid eerste om dit aan te tonen.

37
00:01:34,665 --> 00:01:39,120
Een vraag kwam ter sprake tijdens de pauze
over wat code ziet er eigenlijk uitziet.

38
00:01:39,120 --> 00:01:41,315
En we spraken
tijdens de pauze over C,

39
00:01:41,315 --> 00:01:45,060
in het bijzonder een particular--
lager niveau in een oudere taal.

40
00:01:45,060 --> 00:01:47,750
En ik heb gewoon een snelle
Google zoeken naar C-code te vinden

41
00:01:47,750 --> 00:01:51,574
voor binary search, het algoritme dat we
gebruikt om eerder te zoeken die telefoonboek.

42
00:01:51,574 --> 00:01:54,240
Dit specifieke voorbeeld, natuurlijk
niet een telefoonboek te zoeken.

43
00:01:54,240 --> 00:01:57,840
Het zoekt gewoon een hele hoop
nummers in het geheugen van de computer.

44
00:01:57,840 --> 00:02:01,000
Maar als je wilt gewoon een visuele
gevoel van wat een echte programmering

45
00:02:01,000 --> 00:02:05,370
taal eruit ziet, het lijkt
een beetje iets als dit.

46
00:02:05,370 --> 00:02:09,759
Dus het is ongeveer 20-plus,
30 of zo regels code,

47
00:02:09,759 --> 00:02:12,640
maar het gesprek dat we
hadden meer dan break

48
00:02:12,640 --> 00:02:16,000
was over hoe dit werkelijk
wordt veranderd in nullen en enen

49
00:02:16,000 --> 00:02:19,200
en als je kunt niet zomaar terugkeren dat
verwerken en gaan van nullen en enen

50
00:02:19,200 --> 00:02:20,210
terug naar code.

51
00:02:20,210 --> 00:02:22,620
>> Helaas is het proces
is zo transformatieve

52
00:02:22,620 --> 00:02:24,890
dat het een stuk makkelijker gezegd dan gedaan.

53
00:02:24,890 --> 00:02:29,400
Ik ging verder en eigenlijk draaide
dat programma, Binary Search,

54
00:02:29,400 --> 00:02:32,700
in nullen en enen in de vorm van een
programma genaamd de compiler die ik

55
00:02:32,700 --> 00:02:34,400
toevallig hier recht op mijn Mac.

56
00:02:34,400 --> 00:02:37,850
En als je kijkt naar het scherm
hier, met de nadruk in het bijzonder

57
00:02:37,850 --> 00:02:43,520
Op deze middelste zes kolommen alleen,
je zult alleen nullen en enen te zien.

58
00:02:43,520 --> 00:02:48,290
En dat zijn de nullen en enen die
componeren precies dat zoeken programma.

59
00:02:48,290 --> 00:02:53,720
>> En dus elke brok van vijf bits,
elke byte van nullen en enen hier,

60
00:02:53,720 --> 00:02:57,310
vertegenwoordigen wat instructie
typisch in een computer.

61
00:02:57,310 --> 00:03:00,730
En in feite, als je hebt gehoord van de
marketing slogan 'Intel inside' - dat,

62
00:03:00,730 --> 00:03:04,610
Uiteraard betekent gewoon dat je een
Intel CPU of de hersenen in de computer.

63
00:03:04,610 --> 00:03:08,000
En wat dat betekent om een ​​CPU is
dat u een instructie set,

64
00:03:08,000 --> 00:03:08,840
bij wijze van spreken.

65
00:03:08,840 --> 00:03:11,620
>> Elke CPU in de wereld, vele
hen gemaakt door Intel deze dagen,

66
00:03:11,620 --> 00:03:13,690
begrijpt een eindige
aantal instructies.

67
00:03:13,690 --> 00:03:18,690
En die instructies zijn zo laag niveau
als add deze twee getallen bij elkaar,

68
00:03:18,690 --> 00:03:22,560
vermenigvuldigen deze twee getallen elkaar,
bewegen dit stuk van de gegevens van hier

69
00:03:22,560 --> 00:03:27,340
hier in het geheugen, dan deze
Informatie van hier naar hier in het geheugen,

70
00:03:27,340 --> 00:03:32,200
en zo forth-- zo heel erg
low-level, bijna elektronische details.

71
00:03:32,200 --> 00:03:34,780
Maar met de wiskundige
operaties gekoppeld

72
00:03:34,780 --> 00:03:37,410
met wat we eerder hebben besproken,
de representatie van data

73
00:03:37,410 --> 00:03:40,450
als nullen en enen, kan
bouw je alles

74
00:03:40,450 --> 00:03:44,180
dat een computer vandaag de dag kan doen, of
het is tekstueel, grafisch, muzikaal,

75
00:03:44,180 --> 00:03:45,580
of anders.

76
00:03:45,580 --> 00:03:49,450
>> Dus dit is heel makkelijk te krijgen
verloren in het onkruid van snel.

77
00:03:49,450 --> 00:03:52,150
En er is een heleboel
syntactische uitdagingen

78
00:03:52,150 --> 00:03:56,630
waarbij als je de eenvoudigste te maken,
domste van typefouten geen van de programma

79
00:03:56,630 --> 00:03:57,860
zal ook werken.

80
00:03:57,860 --> 00:04:00,366
Etc. in plaats van een
taal als C vanmorgen,

81
00:04:00,366 --> 00:04:02,240
Ik dacht dat het zou zijn
leuker om daadwerkelijk te doen

82
00:04:02,240 --> 00:04:04,840
iets meer visuele, die
terwijl ontworpen voor kinderen

83
00:04:04,840 --> 00:04:08,079
is eigenlijk een perfecte manifestatie
van een daadwerkelijke programmering

84
00:04:08,079 --> 00:04:10,370
language-- toevallig
gebruik maken van foto's in plaats van tekst

85
00:04:10,370 --> 00:04:11,710
om die ideeën vertegenwoordigen.

86
00:04:11,710 --> 00:04:15,470
>> Dus zodra je inderdaad een
-account op scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
klikt u op de knop Create
linksboven van de site.

88
00:04:21,070 --> 00:04:24,620
En je moet een omgeving als te zien
degene die ik sta op het punt om te zien op mijn scherm

89
00:04:24,620 --> 00:04:26,310
hier.

90
00:04:26,310 --> 00:04:29,350
En we zullen gewoon een beetje door te brengen
beetje tijd hier te spelen.

91
00:04:29,350 --> 00:04:34,080
Laten we eens kijken of we kunnen niet alles wat op te lossen
problemen samen als volgt.

92
00:04:34,080 --> 00:04:39,420
>> Dus wat je ziet binnen deze
environment-- en eigenlijk gewoon laten

93
00:04:39,420 --> 00:04:40,050
me pauze.

94
00:04:40,050 --> 00:04:42,680
Is er iemand niet hier?

95
00:04:42,680 --> 00:04:45,070
Niet hier?

96
00:04:45,070 --> 00:04:45,800
OK.

97
00:04:45,800 --> 00:04:49,030
Dus laat me wijzen op een paar
kenmerken van deze omgeving.

98
00:04:49,030 --> 00:04:55,024
>> Dus in de linkerbovenhoek van het scherm, we
hebben stadium Scratch's, om zo te zeggen.

99
00:04:55,024 --> 00:04:57,440
Scratch is niet alleen de naam
van deze programmeertaal;

100
00:04:57,440 --> 00:05:00,356
Het is ook de naam van de kat die
zie je standaard daar in oranje.

101
00:05:00,356 --> 00:05:02,160
Hij is op een podium, zodat
net als ik beschreef

102
00:05:02,160 --> 00:05:05,770
de schildpad eerder als zijnde in een
rechthoekige witte boord omgeving.

103
00:05:05,770 --> 00:05:09,800
werelds Deze kat is volledig afgesloten
dat rechthoek up top daar.

104
00:05:09,800 --> 00:05:12,210
>> Ondertussen, aan de rechterkant
kant hier, het is

105
00:05:12,210 --> 00:05:15,610
slechts een scripts, een
schone lei als je wil.

106
00:05:15,610 --> 00:05:18,590
Dit is waar we heen gaan om te schrijven
onze programma's in slechts een moment.

107
00:05:18,590 --> 00:05:22,935
En de bouwstenen die we zullen
gebruiken om te schrijven dit program-- de puzzel

108
00:05:22,935 --> 00:05:25,310
stukken, als je will-- bent
die hier in het midden,

109
00:05:25,310 --> 00:05:27,500
en ze zijn gecategoriseerd
door functionaliteit.

110
00:05:27,500 --> 00:05:31,000
Dus, bijvoorbeeld, ik ga om verder te gaan
en toont ten minste een van deze.

111
00:05:31,000 --> 00:05:33,690
Ik ga om te gaan en klik op
de categorie Besturing boven.

112
00:05:33,690 --> 00:05:35,720
>> Dus dit zijn de categorieën boven.

113
00:05:35,720 --> 00:05:39,410
Ik ga naar klik op de categorie controle.

114
00:05:39,410 --> 00:05:44,020
Integendeel, ik ga naar de gebeurtenissen op
categorie, de allereerste boven.

115
00:05:44,020 --> 00:05:47,790
En als je wilt volgen langs zelfs
als we dit doen, je bent zeer welkom is.

116
00:05:47,790 --> 00:05:52,180
Ik ga om te klikken en slepen deze
eerste, "als groene vlag geklikt."

117
00:05:52,180 --> 00:05:58,410
En dan ga ik het gewoon laten vallen
ongeveer op de top van mijn lege leien.

118
00:05:58,410 --> 00:06:01,450
>> En wat is er leuk is aan Scratch
is dat dit stukje van de puzzel, wanneer

119
00:06:01,450 --> 00:06:04,560
vergrendeld met andere puzzel
stukken, gaat letterlijk doen

120
00:06:04,560 --> 00:06:06,460
wat die puzzelstukjes zeggen te doen.

121
00:06:06,460 --> 00:06:09,710
Dus, bijvoorbeeld, Scratch heeft gelijk
Nu in het midden van zijn wereld.

122
00:06:09,710 --> 00:06:14,660
Ik ga om te gaan en te kiezen
Nu, laten we zeggen, de categorie Motion,

123
00:06:14,660 --> 00:06:18,000
als je wilt naar het doen
same-- Motion categorie.

124
00:06:18,000 --> 00:06:20,430
En nu zie ik heb een hele
stelletje puzzelstukjes hier

125
00:06:20,430 --> 00:06:23,370
dat, wederom, een soort van doen wat ze zeggen.

126
00:06:23,370 --> 00:06:28,110
En ik ga om verder te gaan en te slepen en
laat de beweging blok rechts over hier.

127
00:06:28,110 --> 00:06:31,860
>> En merk op dat zodra je krijgt
dicht bij de bodem van de "groene vlag

128
00:06:31,860 --> 00:06:34,580
geklikt "-knop, bericht
hoe een witte lijn verschijnt,

129
00:06:34,580 --> 00:06:36,950
alsof het is bijna
magnetisch, het wil er naartoe te gaan.

130
00:06:36,950 --> 00:06:43,070
Gewoon laten gaan, en het zal breken
elkaar en de vormen overeenkomen.

131
00:06:43,070 --> 00:06:46,620
En nu kunt u misschien bijna
raden waar we gaan met dit.

132
00:06:46,620 --> 00:06:51,570
>> Als je kijkt naar de Scratch stadium
hier en kijk naar de top van het,

133
00:06:51,570 --> 00:06:55,142
je een rood licht te zien, een
stopbord en een groene vlag.

134
00:06:55,142 --> 00:06:57,100
En ik ga om verder te gaan
en let op mijn Screen--

135
00:06:57,100 --> 00:06:58,460
voor slechts een moment, als je kon.

136
00:06:58,460 --> 00:07:01,960
Ik ga naar de klik
groene vlag op dit moment,

137
00:07:01,960 --> 00:07:07,850
en hij bewoog wat lijkt op 10 stappen worden
of 10 pixels, 10 punten op het scherm.

138
00:07:07,850 --> 00:07:13,390
>> En dus niet zo spannend,
maar laat me voorstellen

139
00:07:13,390 --> 00:07:17,440
zonder dat dit zelfs het onderwijs, net
het gebruik van de eigen eigen intuition-- let

140
00:07:17,440 --> 00:07:22,560
ik stel voor dat u erachter te komen hoe om te
maken Scratch lopen rechts van het podium af.

141
00:07:22,560 --> 00:07:28,700
Laat hem maken voor de rechterzijde van
het scherm helemaal naar rechts.

142
00:07:28,700 --> 00:07:32,200
Ik geef je een moment
of zo te worstelen met dat.

143
00:07:32,200 --> 00:07:37,681
Wilt u misschien een kijkje te nemen
bij andere categorieën van de blokken.

144
00:07:37,681 --> 00:07:38,180
Okee.

145
00:07:38,180 --> 00:07:41,290
Dus gewoon samen te vatten, als we
de groene vlag geklikt hier

146
00:07:41,290 --> 00:07:44,850
en beweeg 10 stappen wordt het
alleen instructie, elke keer als ik

147
00:07:44,850 --> 00:07:46,720
klik op de groene vlag, wat gebeurt er?

148
00:07:46,720 --> 00:07:50,070
Nou, dat is het uitvoeren van mijn programma.

149
00:07:50,070 --> 00:07:52,450
Dus kon ik dit doen
misschien 10 keer met de hand,

150
00:07:52,450 --> 00:07:55,130
maar dit voelt een beetje
bit hackish, om zo te zeggen,

151
00:07:55,130 --> 00:07:57,480
waarbij ik ben niet echt
oplossen van het probleem.

152
00:07:57,480 --> 00:08:00,530
Ik ben gewoon opnieuw te proberen en
opnieuw en opnieuw en opnieuw

153
00:08:00,530 --> 00:08:03,180
totdat ik een soort van ongeluk
het bereiken van de richtlijn

154
00:08:03,180 --> 00:08:05,560
dat ik uiteengezet om eerder te bereiken.

155
00:08:05,560 --> 00:08:08,200
>> Maar we weten uit onze
pseudocode eerder dat er

156
00:08:08,200 --> 00:08:11,870
dit begrip in de programmering van de looping,
iets te doen opnieuw en opnieuw.

157
00:08:11,870 --> 00:08:14,888
En dus ik zag dat een heleboel van jullie
bereikt voor wat puzzelstukje?

158
00:08:14,888 --> 00:08:17,870

159
00:08:17,870 --> 00:08:18,730
Herhaal dit totdat.

160
00:08:18,730 --> 00:08:21,400
Dus konden we iets doen
achtige herhalen totdat.

161
00:08:21,400 --> 00:08:23,760
En wat heb je herhalen totdat precies?

162
00:08:23,760 --> 00:08:27,720

163
00:08:27,720 --> 00:08:28,540
>> OK.

164
00:08:28,540 --> 00:08:31,974
En laat me gaan met een dat is
wat eenvoudiger voor slechts een moment.

165
00:08:31,974 --> 00:08:33,140
Laat me gaan en dit te doen.

166
00:08:33,140 --> 00:08:35,559
Merk op dat, als je kan hebben
onder controle ontdekt,

167
00:08:35,559 --> 00:08:38,409
Er is deze herhaling blok, dat
ziet er niet uit alsof het zo groot.

168
00:08:38,409 --> 00:08:41,039
Er is niet veel ruimte in
tussen deze twee gele lijnen.

169
00:08:41,039 --> 00:08:43,539
Maar zoals sommigen van u zou kunnen hebben
opgevallen, als je slepen en neerzetten,

170
00:08:43,539 --> 00:08:45,150
merken hoe het groeit om de vorm te vullen.

171
00:08:45,150 --> 00:08:46,274
>> En je kunt nog meer proppen.

172
00:08:46,274 --> 00:08:48,670
Het zal alleen maar blijven groeien als
u sleept en zweven over het.

173
00:08:48,670 --> 00:08:51,110
En ik weet niet wat er is
best hier, dus laat

174
00:08:51,110 --> 00:08:54,760
mij tenminste herhaal vijf keer, voor
Zo, en ga dan terug naar het podium

175
00:08:54,760 --> 00:08:56,720
en klik op de groene vlag.

176
00:08:56,720 --> 00:08:59,110
En nu merken dat het helemaal er niet.

177
00:08:59,110 --> 00:09:02,400
>> Nu een aantal van jullie voorgesteld, zoals
Victoria wist alleen, herhaal 10 keer.

178
00:09:02,400 --> 00:09:05,140
En dat in het algemeen doet
hem de hele weg,

179
00:09:05,140 --> 00:09:10,510
maar zou er niet een meer robuuste zijn
manier dan willekeurig uitzoeken

180
00:09:10,510 --> 00:09:12,640
hoeveel moves te maken?

181
00:09:12,640 --> 00:09:17,680
Wat zou een betere blok
dan herhaal 10 keer zijn?

182
00:09:17,680 --> 00:09:20,380
>> Ja, dus waarom niet iets dat altijd doen?

183
00:09:20,380 --> 00:09:24,390
En nu laat ik verplaats deze puzzelstukje
binnen is er en zich te ontdoen van deze.

184
00:09:24,390 --> 00:09:28,300
Let nu op, ongeacht waar Scratch
begint, gaat hij naar de rand.

185
00:09:28,300 --> 00:09:30,700
En gelukkig MIT,
die maakt Scratch, net

186
00:09:30,700 --> 00:09:33,190
zorgt ervoor dat hij nooit
verdwijnt volledig.

187
00:09:33,190 --> 00:09:35,360
U kunt altijd pak zijn staart.

188
00:09:35,360 --> 00:09:37,680
>> En net intuïtief,
waarom doet hij in beweging blijven?

189
00:09:37,680 --> 00:09:38,892
Wat is hier aan de hand?

190
00:09:38,892 --> 00:09:41,440

191
00:09:41,440 --> 00:09:43,824
Hij lijkt te hebben stilgestaan, maar
dan als ik pick-up en sleep

192
00:09:43,824 --> 00:09:45,240
hij blijft te willen gaan daar.

193
00:09:45,240 --> 00:09:46,123
Waarom is dat?

194
00:09:46,123 --> 00:09:51,610

195
00:09:51,610 --> 00:09:54,360
Waarlijk, een computer is letterlijk
gaan doen wat je hem vertelt wat te doen.

196
00:09:54,360 --> 00:09:58,380
Dus als je het verteld eerder doen het
volgende ding altijd, bewegen 10 stappen,

197
00:09:58,380 --> 00:10:01,860
het gaat om door te gaan en gaan
totdat ik raakte de rode stopbord

198
00:10:01,860 --> 00:10:04,620
en stoppen met het programma helemaal.

199
00:10:04,620 --> 00:10:06,610
>> Dus zelfs als je niet
dit te doen, hoe kon ik

200
00:10:06,610 --> 00:10:09,510
maken Scratch move sneller
over het scherm?

201
00:10:09,510 --> 00:10:12,060

202
00:10:12,060 --> 00:10:13,280
Meer stappen, toch?

203
00:10:13,280 --> 00:10:15,710
Dus in plaats van het doen van 10
op een moment, waarom doen we niet

204
00:10:15,710 --> 00:10:20,100
ga je gang en verander het to--
wat zou je propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Dus nu ga ik klik op de groene
vlag, en inderdaad, hij gaat echt snel.

206
00:10:24,410 --> 00:10:27,180
>> En dit, natuurlijk, is gewoon
een manifestatie van animatie.

207
00:10:27,180 --> 00:10:28,060
Wat is animatie?

208
00:10:28,060 --> 00:10:33,090
Het is gewoon tonen u de mens een
hele hoop foto's echt,

209
00:10:33,090 --> 00:10:34,160
echt, echt snel.

210
00:10:34,160 --> 00:10:36,500
En dus als we gewoon vertellen
hem om meer stappen te bewegen,

211
00:10:36,500 --> 00:10:39,750
we gewoon het effect te
verandering waar hij op het scherm

212
00:10:39,750 --> 00:10:42,900
des te sneller per tijdseenheid.

213
00:10:42,900 --> 00:10:46,454
>> Nu is de volgende uitdaging die ik voorgesteld
was om hem stuiteren de rand.

214
00:10:46,454 --> 00:10:49,120
En zonder te weten wat de puzzel
stukken exist-- want het is fijn

215
00:10:49,120 --> 00:10:53,030
als je niet naar het krijgen
fase van de challenge-- wat

216
00:10:53,030 --> 00:10:54,280
wil je intuïtief doen?

217
00:10:54,280 --> 00:10:58,030
Hoe zouden we hem terug te stuiteren en
weer, tussen de linker en rechter?

218
00:10:58,030 --> 00:11:02,630

219
00:11:02,630 --> 00:11:03,810
>> Ja.

220
00:11:03,810 --> 00:11:05,680
Dus we moeten een soort
conditie, en we

221
00:11:05,680 --> 00:11:09,710
lijken te conditionals hebben, om zo te
spreken, onder de categorie controle.

222
00:11:09,710 --> 00:11:14,110
Welke van deze blokken
we waarschijnlijk willen?

223
00:11:14,110 --> 00:11:15,200
Ja, misschien 'als, dan. "

224
00:11:15,200 --> 00:11:18,780
Zo merken dat onder de gele blokken
we hier hebben, is er deze "if"

225
00:11:18,780 --> 00:11:23,920
of deze "if, else" blok dat zal
stellen ons in staat om een ​​beslissing om dit te doen

226
00:11:23,920 --> 00:11:25,000
of om dat te doen.

227
00:11:25,000 --> 00:11:27,380
En je kunt zelfs nesten
om meerdere dingen te doen.

228
00:11:27,380 --> 00:11:34,910
Of als je er nog niet bent gegaan,
ga je gang naar de categorie Sensing

229
00:11:34,910 --> 00:11:39,612
en-- laten we eens kijken of het hier.

230
00:11:39,612 --> 00:11:43,050

231
00:11:43,050 --> 00:11:52,050
>> Dus wat blok zou hier nuttig zijn
op te sporen als hij van het podium?

232
00:11:52,050 --> 00:11:56,740
Ja, merken dat sommige van deze blokken
kunnen worden geparametriseerd, om zo te zeggen.

233
00:11:56,740 --> 00:12:00,706
Ze kunnen een soort van worden aangepast, niet
In tegenstelling tot HTML gisteren met attributen,

234
00:12:00,706 --> 00:12:03,330
waar die attributen soort
aanpassen van het gedrag van een tag.

235
00:12:03,330 --> 00:12:08,880
Op dezelfde manier hier, kan ik grijp deze ontroerende
blok en verandering en de vraag stellen:

236
00:12:08,880 --> 00:12:11,500
Bent u de muis aan te raken
pointer als de cursor

237
00:12:11,500 --> 00:12:13,250
of bent u het aanraken van de rand?

238
00:12:13,250 --> 00:12:15,210
>> Dus laat me gaan en dit te doen.

239
00:12:15,210 --> 00:12:18,130
Ik ga om uit te zoomen voor een moment.

240
00:12:18,130 --> 00:12:21,320
Laat ik grijp deze puzzelstukje
Hier, dit puzzelstukje dit,

241
00:12:21,320 --> 00:12:24,570
en ik ga wirwar
ze voor slechts een moment.

242
00:12:24,570 --> 00:12:27,620
Ik ga dit te verplaatsen,
verandert dit ontroerende rand,

243
00:12:27,620 --> 00:12:38,590
en ik ga om beweging te doen.

244
00:12:38,590 --> 00:12:40,490
Dus hier zijn enkele ingrediënten.

245
00:12:40,490 --> 00:12:42,570
Ik denk dat ik alles wat ik wil hebben.

246
00:12:42,570 --> 00:12:47,710
>> Iemand zou willen voorstellen hoe ik
kan verbinden deze misschien van boven naar beneden

247
00:12:47,710 --> 00:12:52,020
om het probleem van oplossen
Scratch beweging rechts naar links naar rechts te

248
00:12:52,020 --> 00:12:57,020
links naar rechts naar links, elk
tijd alleen maar stuiteren van de muur?

249
00:12:57,020 --> 00:12:58,050
Wat wil ik doen?

250
00:12:58,050 --> 00:13:01,097
Welk blok moet ik aansluiten op de
"Wanneer groene vlag geklikt eerste"?

251
00:13:01,097 --> 00:13:04,060

252
00:13:04,060 --> 00:13:06,200
>> OK, dus laten we beginnen met de "voor altijd."

253
00:13:06,200 --> 00:13:07,170
Wat gaat er in de volgende stap?

254
00:13:07,170 --> 00:13:10,290
Iemand anders.

255
00:13:10,290 --> 00:13:11,850
OK, ga stappen.

256
00:13:11,850 --> 00:13:12,350
Okee.

257
00:13:12,350 --> 00:13:14,470
Dan wat?

258
00:13:14,470 --> 00:13:15,120
Dus dan is het zo.

259
00:13:15,120 --> 00:13:17,720
En merk, ook al ziet het er
samen ingeklemd strak,

260
00:13:17,720 --> 00:13:19,500
het zal alleen maar groeien in te vullen.

261
00:13:19,500 --> 00:13:21,500
Het zal gewoon springen in waar ik wil.

262
00:13:21,500 --> 00:13:25,920
>> En wat moet ik tussen
de if en de toenmalige?

263
00:13:25,920 --> 00:13:27,180
Waarschijnlijk "als het aanraken van de rand."

264
00:13:27,180 --> 00:13:31,800
En let op, nogmaals, het is te groot
voor, maar het zal groeien te vullen.

265
00:13:31,800 --> 00:13:35,002
En vervolgens 15 graden?

266
00:13:35,002 --> 00:13:35,710
Hoeveel graden?

267
00:13:35,710 --> 00:13:38,800

268
00:13:38,800 --> 00:13:41,196
Ja, dus 180 zal draaien
me helemaal rond.

269
00:13:41,196 --> 00:13:42,570
Dus laten we eens kijken als ik dit recht.

270
00:13:42,570 --> 00:13:43,930
Laat me uitzoomen.

271
00:13:43,930 --> 00:13:45,130
>> Laat me slepen Scratch up.

272
00:13:45,130 --> 00:13:50,030
Dus hij is een beetje vervormd
nu, maar dat is prima.

273
00:13:50,030 --> 00:13:52,231
Hoe kan ik gemakkelijk resetten hem?

274
00:13:52,231 --> 00:13:59,879

275
00:13:59,879 --> 00:14:01,045
Ik ga een beetje vals te spelen.

276
00:14:01,045 --> 00:14:04,074

277
00:14:04,074 --> 00:14:05,990
Dus ik ben het toevoegen van een ander
blok, alleen maar om duidelijk te zijn.

278
00:14:05,990 --> 00:14:08,424
Ik wil dat hij 90 graden punt
om de juiste standaard,

279
00:14:08,424 --> 00:14:10,840
dus ik ben gewoon gaan om hem te vertellen
dat programmatisch doen.

280
00:14:10,840 --> 00:14:11,632
En hier gaan we.

281
00:14:11,632 --> 00:14:14,740

282
00:14:14,740 --> 00:14:15,740
We lijken te hebben gedaan.

283
00:14:15,740 --> 00:14:19,980
Het is een beetje raar, want
Hij loopt op zijn kop.

284
00:14:19,980 --> 00:14:21,250
Laten we noemen dat een bug.

285
00:14:21,250 --> 00:14:22,120
Dat is een vergissing.

286
00:14:22,120 --> 00:14:27,320
Een bug is een fout in een programma, een
logische fout dat ik, de mens, maakte.

287
00:14:27,320 --> 00:14:28,985
Waarom gaat hij op zijn kop?

288
00:14:28,985 --> 00:14:33,560

289
00:14:33,560 --> 00:14:35,250
Heeft MIT verknallen of heb ik?

290
00:14:35,250 --> 00:14:38,840

291
00:14:38,840 --> 00:14:42,550
>> Ja, ik bedoel, het is niet het MIT
fout. Ze gaf me een stukje van de puzzel

292
00:14:42,550 --> 00:14:44,970
dat zegt draaien sommige aantal graden.

293
00:14:44,970 --> 00:14:47,672
En op voorstel van Victoria's,
Ik ben het draaien van 180 graden,

294
00:14:47,672 --> 00:14:48,880
welke de juiste intuïtie.

295
00:14:48,880 --> 00:14:53,700
Maar het draaien van 180 graden letterlijk
betekent dat het draaien van 180 graden,

296
00:14:53,700 --> 00:14:55,860
en dat is niet echt
wat ik wil, blijkbaar.

297
00:14:55,860 --> 00:14:58,026
Omdat in ieder geval is hij in
Dit tweedimensionale wereld,

298
00:14:58,026 --> 00:15:00,740
dus draaien gaat werkelijk
om hem ondersteboven spiegelen.

299
00:15:00,740 --> 00:15:04,030
>> Ik wil waarschijnlijk wat blok gebruiken
in plaats daarvan, op basis van wat u hier ziet?

300
00:15:04,030 --> 00:15:11,890

301
00:15:11,890 --> 00:15:14,790
Hoe kunnen we dit oplossen?

302
00:15:14,790 --> 00:15:18,380
Ja, dus we konden wijzen
in de tegengestelde richting.

303
00:15:18,380 --> 00:15:22,300
En eigenlijk zelfs dat is
zal niet genoeg zijn,

304
00:15:22,300 --> 00:15:26,410
want we kunnen alleen vaste code
te wijzen links of rechts.

305
00:15:26,410 --> 00:15:27,920
>> Weet je wat we kunnen doen?

306
00:15:27,920 --> 00:15:30,160
Het lijkt erop dat we een
gemak blok hier.

307
00:15:30,160 --> 00:15:32,987
Als ik in te zoomen, zie
iets wat we hier van?

308
00:15:32,987 --> 00:15:36,120

309
00:15:36,120 --> 00:15:40,020
Dus het lijkt erop dat MIT heeft een
abstractie gebouwd in hier.

310
00:15:40,020 --> 00:15:45,440
Dit blok lijkt gelijk te zijn
waaraan andere blokken, meervoud?

311
00:15:45,440 --> 00:15:49,510
>> Dat een blok lijkt gelijk te zijn
dit hele trio blokken

312
00:15:49,510 --> 00:15:50,880
dat we hier hebben.

313
00:15:50,880 --> 00:15:54,670
Dus het blijkt dat ik kan vereenvoudigen mijn
programma door zich te ontdoen van al die

314
00:15:54,670 --> 00:15:58,270
en zet deze in hier.

315
00:15:58,270 --> 00:16:01,620
En nu is hij nog steeds een beetje
buggy, en dat is prima voor nu.

316
00:16:01,620 --> 00:16:03,370
We laten dat.

317
00:16:03,370 --> 00:16:06,000
Maar mijn programma is zelfs
eenvoudiger en ook dit

318
00:16:06,000 --> 00:16:09,060
representatief zou
van een doelpunt in programming--

319
00:16:09,060 --> 00:16:13,430
is ideaal om uw code
eenvoudig, zo compact mogelijk,

320
00:16:13,430 --> 00:16:15,650
terwijl het nog steeds als
leesbaar mogelijk.

321
00:16:15,650 --> 00:16:20,310
Je wilt niet om het zo beknopt te maken
dat het moeilijk is om te begrijpen.

322
00:16:20,310 --> 00:16:22,826
>> Maar let op, ik heb vervangen
drie blokken met één,

323
00:16:22,826 --> 00:16:24,200
en dat is misschien wel een goede zaak.

324
00:16:24,200 --> 00:16:27,280
Ik heb weg geabstraheerd het begrip
te controleren of u bent

325
00:16:27,280 --> 00:16:29,120
Aan de rand met slechts één blok.

326
00:16:29,120 --> 00:16:31,520
Nu kunnen we veel plezier met deze, in feite.

327
00:16:31,520 --> 00:16:35,790
Dit betekent niet zozeer toe te voegen
intellectuele waarde, maar speelse waarde.

328
00:16:35,790 --> 00:16:39,730
Ik ga om verder te gaan
en hier grijp deze sound.

329
00:16:39,730 --> 00:16:42,900

330
00:16:42,900 --> 00:16:46,420
Dus laat me ga je gang, en laat me
stoppen met het programma voor een moment.

331
00:16:46,420 --> 00:16:52,070
Ik ga naar het volgende op te nemen,
waardoor toegang tot mijn microfoon.

332
00:16:52,070 --> 00:16:53,181
>> Daar gaan we.

333
00:16:53,181 --> 00:16:53,680
Ouch.

334
00:16:53,680 --> 00:16:58,710

335
00:16:58,710 --> 00:17:01,140
Laten we proberen dit opnieuw.

336
00:17:01,140 --> 00:17:02,279
Daar gaan we.

337
00:17:02,279 --> 00:17:03,570
OK, nam ik de verkeerde dingen.

338
00:17:03,570 --> 00:17:04,580
Daar gaan we.

339
00:17:04,580 --> 00:17:05,080
Ouch.

340
00:17:05,080 --> 00:17:07,910

341
00:17:07,910 --> 00:17:08,800
Ouch.

342
00:17:08,800 --> 00:17:09,300
Okee.

343
00:17:09,300 --> 00:17:10,791
Nu moet ik om zich te ontdoen van.

344
00:17:10,791 --> 00:17:11,290
Okee.

345
00:17:11,290 --> 00:17:13,950
>> Dus nu heb ik een
opname van enkel "ouch."

346
00:17:13,950 --> 00:17:18,040
Dus nu ga ik om te gaan
vooruit en noemen dit "ouch."

347
00:17:18,040 --> 00:17:20,270
Ik ga om terug te gaan
mijn scripts en nu

348
00:17:20,270 --> 00:17:25,460
Opmerking Er is dit blok dat heet
spelen geluid 'miauw' of speel het geluid "ouch."

349
00:17:25,460 --> 00:17:28,920
Ik ga dit te slepen, en waar de
moet ik dit voor het komische effect?

350
00:17:28,920 --> 00:17:31,740

351
00:17:31,740 --> 00:17:37,860
Ja, dus nu is het soort
buggy, want nu deze block--

352
00:17:37,860 --> 00:17:42,050
merk op hoe dit "als aan de rand,
bounce "is een soort van self-contained.

353
00:17:42,050 --> 00:17:43,704
Dus ik nodig om dit te bevestigen.

354
00:17:43,704 --> 00:17:44,870
Laat me gaan en dit te doen.

355
00:17:44,870 --> 00:17:48,630
Laat me te ontdoen van deze en ga terug
naar onze oorspronkelijke, meer weloverwogen

356
00:17:48,630 --> 00:17:49,870
functionaliteit.

357
00:17:49,870 --> 00:18:01,080
Dus "als het aanraken van de rand, dan" Ik wil
te draaien, zoals voorgesteld Victoria,

358
00:18:01,080 --> 00:18:02,480
180 graden.

359
00:18:02,480 --> 00:18:05,497
En ik wil spelen
het geluid "ouch" daar?

360
00:18:05,497 --> 00:18:11,800

361
00:18:11,800 --> 00:18:15,580
>> Ja, ziet het buiten
die gele blok.

362
00:18:15,580 --> 00:18:17,680
Dus ook dit zou een
bug, maar ik heb het gezien.

363
00:18:17,680 --> 00:18:21,290
Dus ik ga het slepen hier,
en merk nu is het in de "als."

364
00:18:21,290 --> 00:18:24,250
Dus de "als" is dit soort
van soortgelijke arm-achtige vlek

365
00:18:24,250 --> 00:18:26,260
dat wordt alleen maar
doen wat binnen van het.

366
00:18:26,260 --> 00:18:30,216
Dus nu als ik uitzoomen op
het risico van annoying--

367
00:18:30,216 --> 00:18:32,860

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Auw, auw, auw.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: En het
zal gewoon eeuwig doorgaan.

370
00:18:39,910 --> 00:18:44,160
Nu alleen om dingen te versnellen
Hier, laat me ga je gang en open te stellen,

371
00:18:44,160 --> 00:18:50,460
laten we say-- laat me gaan om een ​​aantal
van mijn eigen spullen uit de klas.

372
00:18:50,460 --> 00:18:53,000

373
00:18:53,000 --> 00:19:00,220
En laat me open te stellen, laten we zeggen, dit
één gemaakt door een van ons onderwijs fellows

374
00:19:00,220 --> 00:19:01,500
een paar jaar geleden.

375
00:19:01,500 --> 00:19:04,732
Dus sommigen van jullie misschien herinneren
dit spel van weleer,

376
00:19:04,732 --> 00:19:05,940
en het is eigenlijk opmerkelijk.

377
00:19:05,940 --> 00:19:08,190
Hoewel we hebben gedaan de
eenvoudigste programma's op dit moment,

378
00:19:08,190 --> 00:19:09,980
laten we eens kijken wat dit
daadwerkelijk uitziet.

379
00:19:09,980 --> 00:19:10,650
Laat me hit te spelen.

380
00:19:10,650 --> 00:19:14,210

381
00:19:14,210 --> 00:19:18,980
>> Dus in dit spel, we hebben een
kikker, en het gebruik van de pijl keys--

382
00:19:18,980 --> 00:19:23,340
Hij neemt grotere stappen dan ik remember--
Ik heb controle over deze kikker.

383
00:19:23,340 --> 00:19:29,630
En het doel is over het aan de slag
weg zonder in de auto's.

384
00:19:29,630 --> 00:19:34,735
En laten we see-- als ik ga hier, ik
moeten wachten op een logboek om door te bladeren.

385
00:19:34,735 --> 00:19:38,130

386
00:19:38,130 --> 00:19:39,274
Dit voelt als een bug.

387
00:19:39,274 --> 00:19:42,240

388
00:19:42,240 --> 00:19:43,495
Dit is een soort van een bug.

389
00:19:43,495 --> 00:19:45,980

390
00:19:45,980 --> 00:19:46,480
Okee.

391
00:19:46,480 --> 00:19:51,550
Ik ben op dit hier,
daar, en dan houdt u

392
00:19:51,550 --> 00:19:54,100
doorgaan tot je alles
de kikkers naar de waterlelies.

393
00:19:54,100 --> 00:19:55,920
Nu is dit zou kunnen kijken
des te complexer,

394
00:19:55,920 --> 00:19:57,840
maar laten we proberen in te breken
dit neer mentaal

395
00:19:57,840 --> 00:20:00,040
en verbaal in zijn samenstellende blokken.

396
00:20:00,040 --> 00:20:03,910
Dus er is waarschijnlijk een puzzel
stuk dat we nog niet hebben gezien

397
00:20:03,910 --> 00:20:07,440
maar dat is het reageren op toetsaanslagen,
om dingen die ik hit op het toetsenbord.

398
00:20:07,440 --> 00:20:11,660
>> Dus er is waarschijnlijk een soort van
blok dat zegt, als sleutel gelijk op,

399
00:20:11,660 --> 00:20:15,965
dan is er iets met Scratch-- doen
misschien verplaatsen 10 stappen op deze manier.

400
00:20:15,965 --> 00:20:20,240
Als omlaag toets wordt ingedrukt, bewegen 10 stappen
op deze manier, of links-toets, beweeg 10 stappen

401
00:20:20,240 --> 00:20:21,710
op deze manier, 10 stappen.

402
00:20:21,710 --> 00:20:23,644
Ik heb duidelijk draaide de kat in een kikker.

403
00:20:23,644 --> 00:20:26,060
Dus dat is precies waar de
kostuum, zoals Scratch oproepen het-- we

404
00:20:26,060 --> 00:20:28,440
gewoon een foto van de kikker geïmporteerd.

405
00:20:28,440 --> 00:20:29,570
>> Maar wat gebeurt er?

406
00:20:29,570 --> 00:20:32,794
Welke andere regels code,
wat andere puzzelstukjes

407
00:20:32,794 --> 00:20:35,460
deed Blake, ons onderwijs collega,
Gebruik in dit programma, blijkbaar?

408
00:20:35,460 --> 00:20:38,320

409
00:20:38,320 --> 00:20:42,730
Wat is het maken van alles move--
Wat de programmering te bouwen?

410
00:20:42,730 --> 00:20:44,950
>> Motion, sure-- zodat de
Verplaats blok, zeker.

411
00:20:44,950 --> 00:20:49,330
En wat is dat beweging blok
Binnenin, waarschijnlijk?

412
00:20:49,330 --> 00:20:52,850
Ja, een soort lus, misschien een
voor altijd te blokkeren, misschien een herhaling block--

413
00:20:52,850 --> 00:20:54,070
herhaal tot blok.

414
00:20:54,070 --> 00:20:57,330
En dat is wat het maken van de logs en
de waterlelies en al het andere verplaatsen

415
00:20:57,330 --> 00:20:57,990
heen en weer.

416
00:20:57,990 --> 00:21:00,270
Het is gewoon eindeloos gebeurt.

417
00:21:00,270 --> 00:21:03,180
>> Waarom zijn sommige van de auto's
bewegen sneller dan de anderen?

418
00:21:03,180 --> 00:21:06,607
Wat is er anders aan deze programma's?

419
00:21:06,607 --> 00:21:09,690
Ja, waarschijnlijk een aantal van hen nemen
meer stappen tegelijk en sommige

420
00:21:09,690 --> 00:21:10,690
minder stappen tegelijk.

421
00:21:10,690 --> 00:21:14,670
En het visuele effect
is snel versus langzaam.

422
00:21:14,670 --> 00:21:16,030
>> Wat denk je dat er gebeurd is?

423
00:21:16,030 --> 00:21:19,700
Toen ik mijn kikker helemaal
overkant van de straat en de rivier

424
00:21:19,700 --> 00:21:23,560
op het lelieblad, iets
Opmerkelijk is gebeurd.

425
00:21:23,560 --> 00:21:26,540
Wat is er gebeurd zodra ik dat deed?

426
00:21:26,540 --> 00:21:27,210
Het is gestopt.

427
00:21:27,210 --> 00:21:29,680
Dat kikker gestopt, en
Ik kreeg een tweede kikker.

428
00:21:29,680 --> 00:21:33,155
Dus wat construct moet zijn
er gebruikt, welke functie?

429
00:21:33,155 --> 00:21:36,020

430
00:21:36,020 --> 00:21:38,660
>> Ja, dus er is een soort van
"If" conditioneren daar ook.

431
00:21:38,660 --> 00:21:41,909
En het blijkt out-- we niet zien dit--
maar er zijn andere blokken in dat er

432
00:21:41,909 --> 00:21:45,300
kan zeggen, als je aanraakt
een ander ding op het scherm,

433
00:21:45,300 --> 00:21:47,720
als je het aanraken van het lelieblad, "dan."

434
00:21:47,720 --> 00:21:50,810
En dan is dat wanneer we
maken de tweede kikker verschijnen.

435
00:21:50,810 --> 00:21:54,969
Dus ook al is dit spel zeker
zeer gedateerd, hoewel op het eerste gezicht

436
00:21:54,969 --> 00:21:58,010
Er is zoveel gaande on-- en Blake
heeft dit niet zweep in twee minuten,

437
00:21:58,010 --> 00:22:00,390
het kostte hem waarschijnlijk meerdere
uren om dit spel te maken

438
00:22:00,390 --> 00:22:03,850
op basis van zijn geheugen of video's
van versie ervan weleer.

439
00:22:03,850 --> 00:22:07,940
Maar al deze kleine dingen
gaande scherm afzonderlijk

440
00:22:07,940 --> 00:22:11,550
neer deze zeer eenvoudige
constructs-- bewegingen of verklaringen

441
00:22:11,550 --> 00:22:15,519
zoals we hebben besproken, loops en
omstandigheden, en dat is het zo'n beetje.

442
00:22:15,519 --> 00:22:17,060
Er is een paar andere liefhebber functies.

443
00:22:17,060 --> 00:22:19,130
Sommige zijn zuiver
esthetisch of akoestische,

444
00:22:19,130 --> 00:22:20,964
net als de geluiden die ik alleen met gespeeld.

445
00:22:20,964 --> 00:22:23,380
Maar voor het grootste deel, je
hebben in deze taal, Scratch,

446
00:22:23,380 --> 00:22:25,350
alle fundamentele
bouwstenen die u

447
00:22:25,350 --> 00:22:29,280
hebben in C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
en een aantal andere talen.

449
00:22:32,960 --> 00:22:36,720
Heeft u vragen over Scratch?

450
00:22:36,720 --> 00:22:37,220
Okee.

451
00:22:37,220 --> 00:22:40,303
Dus zullen we niet duiken in dieper naar Scratch,
al ben je van harte welkom dit weekend,

452
00:22:40,303 --> 00:22:42,860
vooral als je kinderen hebt of
nichten en neven en dergelijke,

453
00:22:42,860 --> 00:22:44,220
om hen kennis te laten Scratch.

454
00:22:44,220 --> 00:22:47,960
Het is eigenlijk een heerlijk speelse
omgeving met, zoals de auteurs zeggen,

455
00:22:47,960 --> 00:22:49,120
zeer hoge plafonds.

456
00:22:49,120 --> 00:22:51,670
Hoewel we begonnen met
zeer low-level details

457
00:22:51,670 --> 00:22:54,890
kan je echt doen nogal een beetje
mee, en dit is wellicht

458
00:22:54,890 --> 00:22:57,360
een demonstratie van precies dat.

459
00:22:57,360 --> 00:23:02,920
>> Maar laten we nu overgaan naar wat meer
verfijnde problemen, als je wil,

460
00:23:02,920 --> 00:23:05,870
bekend als "zoeken" en
"Sorteren" algemeen.

461
00:23:05,870 --> 00:23:09,500
We hadden deze telefoon boek earlier-- hier
een andere enkel voor discussion--

462
00:23:09,500 --> 00:23:13,460
dat we in staat waren om te zoeken
efficiënter omdat

463
00:23:13,460 --> 00:23:15,270
een belangrijke aanname.

464
00:23:15,270 --> 00:23:17,655
En alleen maar om duidelijk te zijn, wat
veronderstelling was ik het maken van

465
00:23:17,655 --> 00:23:19,280
bij het zoeken door middel van deze telefoon boeken?

466
00:23:19,280 --> 00:23:23,342

467
00:23:23,342 --> 00:23:25,300
Dat Mike Smith was in
het telefoonboek, hoewel ik

468
00:23:25,300 --> 00:23:27,410
kunnen verwerken zou zijn
het scenario zonder hem

469
00:23:27,410 --> 00:23:30,720
er als ik voortijdig gestopt gewoon.

470
00:23:30,720 --> 00:23:31,806
Het boek is alfabetisch.

471
00:23:31,806 --> 00:23:33,930
En dat is een zeer royale
veronderstelling, want dat

472
00:23:33,930 --> 00:23:36,580
betekent someone-- Ik ben een beetje
van het snijden van een hoek,

473
00:23:36,580 --> 00:23:40,580
zoals ik ben sneller omdat iemand
anders deed veel hard werk voor mij.

474
00:23:40,580 --> 00:23:43,120
>> Maar wat als de telefoon
boek werden ongesorteerd?

475
00:23:43,120 --> 00:23:47,050
Misschien Verizon kreeg lui, gooiden
iedereen de namen en nummers in daar

476
00:23:47,050 --> 00:23:50,120
misschien in de volgorde waarin ze
aangemeld voor telefoon service.

477
00:23:50,120 --> 00:23:54,570
En hoeveel tijd kost het me
iemand als Mike Smith vinden?

478
00:23:54,570 --> 00:23:58,160
1000 pagina telefoon book-- hoeveel
pagina's moet ik om door te kijken?

479
00:23:58,160 --> 00:23:58,905
>> Allemaal.

480
00:23:58,905 --> 00:24:00,030
Je bent een soort van pech.

481
00:24:00,030 --> 00:24:03,420
Je moet letterlijk bij elke look
pagina als het telefoonboek is gewoon

482
00:24:03,420 --> 00:24:04,450
willekeurig gesorteerd.

483
00:24:04,450 --> 00:24:06,910
Je zou je geluk en vind Mike
op de eerste pagina, omdat hij

484
00:24:06,910 --> 00:24:08,826
was de eerste klant
naar de telefoon dienst bestelt.

485
00:24:08,826 --> 00:24:10,760
Maar hij zou de laatste zijn geweest, ook.

486
00:24:10,760 --> 00:24:12,500
>> Dus willekeurige volgorde is niet goed.

487
00:24:12,500 --> 00:24:16,750
Dus stel dat we moeten het sorteren
telefoonboek of in het algemeen soort data

488
00:24:16,750 --> 00:24:18,520
die we hebben gekregen.

489
00:24:18,520 --> 00:24:19,440
Hoe kunnen we dat doen?

490
00:24:19,440 --> 00:24:21,360
>> Nou, laat me gewoon proberen
een eenvoudig voorbeeld hier.

491
00:24:21,360 --> 00:24:24,290
Laat me ga je gang en gooi een
paar nummers op het bord.

492
00:24:24,290 --> 00:24:35,480
Stel de nummers we zijn,
laten we zeggen, vier, twee, één en drie.

493
00:24:35,480 --> 00:24:38,390
En, Ben, sorteren van deze nummers voor ons.

494
00:24:38,390 --> 00:24:39,017
>> OK goed.

495
00:24:39,017 --> 00:24:39,850
Hoe heb je dat gedaan?

496
00:24:39,850 --> 00:24:42,731

497
00:24:42,731 --> 00:24:43,230
Okee.

498
00:24:43,230 --> 00:24:44,710
Dus beginnen met de kleinste
waarde en de hoogste,

499
00:24:44,710 --> 00:24:46,084
en dat is echt een goede intuïtie.

500
00:24:46,084 --> 00:24:48,080
En beseffen dat we
mensen zijn eigenlijk vrij

501
00:24:48,080 --> 00:24:49,913
goed in het oplossen van problemen
als dit, op zijn minst

502
00:24:49,913 --> 00:24:51,810
wanneer de data is relatief klein.

503
00:24:51,810 --> 00:24:54,860
Zodra je begint te honderden hebben
getallen duizenden getallen,

504
00:24:54,860 --> 00:24:58,440
miljoenen nummers, waarschijnlijk Ben
kon het niet helemaal zo snel doen,

505
00:24:58,440 --> 00:25:00,620
ervan uitgaande dat er
gaten in de getallen.

506
00:25:00,620 --> 00:25:03,450
Vrij gemakkelijk te tellen tot een miljoen
anders alleen tijdrovend.

507
00:25:03,450 --> 00:25:07,150
>> Dus het algoritme het klinkt
zoals Ben gebruikt net nu

508
00:25:07,150 --> 00:25:08,930
was zoeken naar het kleinste getal.

509
00:25:08,930 --> 00:25:12,900
Dus hoewel wij mensen kunnen nemen
in veel informatie visueel,

510
00:25:12,900 --> 00:25:14,830
een computer is eigenlijk
wat beperkter.

511
00:25:14,830 --> 00:25:17,560
De computer kan alleen
kijken naar een byte in een tijd

512
00:25:17,560 --> 00:25:20,770
of misschien vier bytes op een tijd--
deze dagen misschien 8 bytes bij een tijd--

513
00:25:20,770 --> 00:25:24,450
maar een zeer klein aantal
van bytes op een gegeven moment.

514
00:25:24,450 --> 00:25:28,480
>> Dus gezien het feit dat we echt
vier afzonderlijke waarden hier--

515
00:25:28,480 --> 00:25:32,440
en je kunt bedenken Ben als hebbende
oogkleppen op als hij een computer,

516
00:25:32,440 --> 00:25:36,450
dat hij niet anders kan zien
dan één nummer bij een tijd--

517
00:25:36,450 --> 00:25:39,720
dus we zullen in de regel aannemen, zoals in
Engels, zullen we lezen van rechts naar links.

518
00:25:39,720 --> 00:25:42,870
Dus het eerste nummer Ben waarschijnlijk leek
bij was vier en dan heel snel

519
00:25:42,870 --> 00:25:44,770
besefte dat is een vrij grote
number-- laat me blijven zoeken.

520
00:25:44,770 --> 00:25:45,357
>> Er zijn twee.

521
00:25:45,357 --> 00:25:45,940
Wacht even.

522
00:25:45,940 --> 00:25:47,070
Twee kleiner is dan vier.

523
00:25:47,070 --> 00:25:47,986
Ik ga om te onthouden.

524
00:25:47,986 --> 00:25:49,070
Twee is nu de kleinste.

525
00:25:49,070 --> 00:25:50,417
Nu een-- dat is nog beter.

526
00:25:50,417 --> 00:25:51,250
Dat is nog kleiner.

527
00:25:51,250 --> 00:25:54,000
Ik ga over twee vergeten
en slechts een herinneren nu.

528
00:25:54,000 --> 00:25:56,550
>> En kon hij stoppen met zoeken?

529
00:25:56,550 --> 00:25:58,360
Wel, hij kon op basis van
van deze informatie,

530
00:25:58,360 --> 00:26:00,477
maar hij zou beter zoeken
de rest van de lijst.

531
00:26:00,477 --> 00:26:02,060
Want wat als nul waren in de lijst?

532
00:26:02,060 --> 00:26:03,643
Wat als negatief waren in de lijst?

533
00:26:03,643 --> 00:26:07,720
Hij weet alleen dat zijn antwoord
klopt als hij uitputtend

534
00:26:07,720 --> 00:26:08,729
controleerde de hele lijst.

535
00:26:08,729 --> 00:26:10,020
Dus kijken we naar de rest van dit.

536
00:26:10,020 --> 00:26:11,394
Drie: dat was een verspilling van tijd.

537
00:26:11,394 --> 00:26:13,540
Pech, maar ik was
nog juist te doen.

538
00:26:13,540 --> 00:26:17,857
En nu hij vermoedelijk
selecteerde de kleinste getal

539
00:26:17,857 --> 00:26:20,440
en zet ze gewoon aan het begin
van de lijst, zoals ik hier doe.

540
00:26:20,440 --> 00:26:23,480
Nu, wat heb je nu doen, ook al
je hebt lang niet over nadenken

541
00:26:23,480 --> 00:26:25,962
In zoverre?

542
00:26:25,962 --> 00:26:27,670
Herhaal het proces,
dus een soort lus.

543
00:26:27,670 --> 00:26:28,920
Er is een bekend idee.

544
00:26:28,920 --> 00:26:30,860
Dus hier is vier.

545
00:26:30,860 --> 00:26:32,110
Dat is op dit moment de kleinste.

546
00:26:32,110 --> 00:26:33,220
Dat is een kandidaat.

547
00:26:33,220 --> 00:26:33,900
Niet meer.

548
00:26:33,900 --> 00:26:34,770
Nu heb ik twee gezien.

549
00:26:34,770 --> 00:26:36,630
Dat is de volgende kleinste element.

550
00:26:36,630 --> 00:26:40,800
Drie: dat is niet kleiner, dus
Ben nu kunnen rukken uit de twee.

551
00:26:40,800 --> 00:26:44,510
>> En nu zijn we herhalen het proces, en
Uiteraard krijgt drie volgende uitgetrokken.

552
00:26:44,510 --> 00:26:45,420
Herhaal dit proces.

553
00:26:45,420 --> 00:26:46,990
Vier wordt uitgetrokken.

554
00:26:46,990 --> 00:26:50,140
En nu zijn we uit van de nummers,
dus de lijst moeten worden gesorteerd.

555
00:26:50,140 --> 00:26:51,960
>> Inderdaad is dit een formele algoritme.

556
00:26:51,960 --> 00:26:56,610
Een computer wetenschapper zou doen
noemen dit "selectie sorteren,"

557
00:26:56,610 --> 00:27:00,880
het idee is een soort
lijst iteratively-- weer

558
00:27:00,880 --> 00:27:03,807
en weer selecteren
het kleinste nummer.

559
00:27:03,807 --> 00:27:06,140
En wat is leuk over het is
het is gewoon zo darn intuïtief.

560
00:27:06,140 --> 00:27:07,470
Het is zo simpel.

561
00:27:07,470 --> 00:27:11,100
En u kunt hetzelfde herhalen
bewerking opnieuw en opnieuw.

562
00:27:11,100 --> 00:27:12,150
Het is makkelijk.

563
00:27:12,150 --> 00:27:17,170
>> In dit geval was het snel, maar
hoe lang duurt het eigenlijk doen?

564
00:27:17,170 --> 00:27:19,880
Laten we het erop en
voel me een beetje vervelend.

565
00:27:19,880 --> 00:27:24,150
Dus één, twee, drie, vier, vijf zes,
zeven, acht, negen, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- willekeurig aantal.

567
00:27:26,160 --> 00:27:28,780
Ik wilde alleen maar meer dit
tijd dan alleen de vier.

568
00:27:28,780 --> 00:27:30,780
Dus als ik een hele heb
stelletje getallen now-- te

569
00:27:30,780 --> 00:27:32,420
zelfs niet uit
wat ze zijn-- laten

570
00:27:32,420 --> 00:27:34,380
na te denken over wat dit
algoritme is echt leuk.

571
00:27:34,380 --> 00:27:35,857
>> Stel dat er nummers zijn.

572
00:27:35,857 --> 00:27:38,190
Nogmaals, maakt niet uit wat
ze zijn, maar ze zijn willekeurig.

573
00:27:38,190 --> 00:27:39,679
Ik ben het aanbrengen van Ben's algoritme.

574
00:27:39,679 --> 00:27:41,220
Ik moet het kleinste getal te selecteren.

575
00:27:41,220 --> 00:27:41,761
Wat zal ik doen?

576
00:27:41,761 --> 00:27:44,240
En ik ga fysiek
doe het dit keer om het uit te treden.

577
00:27:44,240 --> 00:27:46,099
Kijken, kijken,
kijken, kijken, kijken.

578
00:27:46,099 --> 00:27:48,140
Alleen tegen de tijd dat ik bij
het einde van de lijst kan

579
00:27:48,140 --> 00:27:51,230
Ik besef dat de kleinste
nummer twee was dit keer.

580
00:27:51,230 --> 00:27:52,720
Men is niet in de lijst.

581
00:27:52,720 --> 00:27:54,400
Dus ik zette twee.

582
00:27:54,400 --> 00:27:55,590
>> Wat moet ik nu doen?

583
00:27:55,590 --> 00:27:58,600
Kijken, kijken, kijken, kijken.

584
00:27:58,600 --> 00:28:02,250
Nu vond ik het getal zeven, want
er hiaten in deze numbers--

585
00:28:02,250 --> 00:28:03,300
maar gewoon willekeurig.

586
00:28:03,300 --> 00:28:03,800
Okee.

587
00:28:03,800 --> 00:28:06,030
Dus nu kan ik neer te zetten zeven.

588
00:28:06,030 --> 00:28:08,860
Op zoek naar kijken, kijken.

589
00:28:08,860 --> 00:28:11,030
>> Nu ben ik ervan uit, van
Natuurlijk, dat Ben niet

590
00:28:11,030 --> 00:28:14,780
extra RAM, extra
geheugen, omdat, natuurlijk,

591
00:28:14,780 --> 00:28:16,080
Ik ben op zoek naar hetzelfde nummer.

592
00:28:16,080 --> 00:28:18,246
Voorwaar, ik zou hebben gedacht
al deze getallen,

593
00:28:18,246 --> 00:28:19,930
en dat is absoluut waar.

594
00:28:19,930 --> 00:28:22,610
Maar als Ben al onthoudt
van de nummers die hij heeft gezien,

595
00:28:22,610 --> 00:28:24,430
Hij heeft niet echt gemaakt
fundamentele vooruitgang

596
00:28:24,430 --> 00:28:26,170
want hij heeft al
een zoekfunctie

597
00:28:26,170 --> 00:28:27,540
door de nummers op het bord.

598
00:28:27,540 --> 00:28:29,373
Remembering alle van de
getallen niet helpt,

599
00:28:29,373 --> 00:28:32,490
want hij kan nog steeds als een computer
alleen kijken naar, we hebben gezegd, één nummer

600
00:28:32,490 --> 00:28:33,080
tegelijk.

601
00:28:33,080 --> 00:28:35,760
Dus er is geen soort van cheat
er zijn die u kunt benutten.

602
00:28:35,760 --> 00:28:39,170
>> Dus in werkelijkheid, zoals ik
blijven zoeken in de lijst,

603
00:28:39,170 --> 00:28:44,200
Ik heb letterlijk om gewoon door te gaan
heen en weer door het, plukken uit

604
00:28:44,200 --> 00:28:45,710
de volgende kleinste getal.

605
00:28:45,710 --> 00:28:48,810
En zoals je kunt soort afleiden
uit mijn domme bewegingen,

606
00:28:48,810 --> 00:28:50,860
dit wordt gewoon heel
vervelend heel snel,

607
00:28:50,860 --> 00:28:54,850
en ik lijken om terug te gaan en
weer, heen en weer nogal wat.

608
00:28:54,850 --> 00:29:03,220
Nu om eerlijk te zijn, heb ik niet te gaan
zo, nou ja, laten we see-- om eerlijk te zijn,

609
00:29:03,220 --> 00:29:06,310
Ik heb niet heel lopen
zoveel stappen elke keer.

610
00:29:06,310 --> 00:29:09,200
Want natuurlijk ik
Selecteer nummers uit de lijst,

611
00:29:09,200 --> 00:29:11,860
de rest van de lijst wordt steeds korter.

612
00:29:11,860 --> 00:29:14,240
>> En dus laten we nadenken over
hoeveel stappen Ik ben eigenlijk

613
00:29:14,240 --> 00:29:16,010
gesjouw door elke keer.

614
00:29:16,010 --> 00:29:18,950
In de eerste situatie
hadden we 16 nummers,

615
00:29:18,950 --> 00:29:22,210
en zo maximally-- laten we gewoon
doe dit voor een discussion--

616
00:29:22,210 --> 00:29:25,640
Ik moest om te kijken tot en met 16
nummers aan de kleinste vinden.

617
00:29:25,640 --> 00:29:28,420
Maar zodra ik uitgerukt
het kleinste getal, hoe

618
00:29:28,420 --> 00:29:30,590
lang was de resterende lijst, natuurlijk?

619
00:29:30,590 --> 00:29:31,420
Slechts 15.

620
00:29:31,420 --> 00:29:34,670
Dus hoeveel nummers deed Ben of ik heb
om te kijken door de tweede keer?

621
00:29:34,670 --> 00:29:36,832
15, gewoon om te gaan en vind de kleinste.

622
00:29:36,832 --> 00:29:39,540
Maar nu natuurlijk, de lijst is,
Ook kleiner dan voorheen.

623
00:29:39,540 --> 00:29:42,540
Dus hoeveel stappen heb ik
moet u de volgende keer?

624
00:29:42,540 --> 00:29:49,970
14 en daarna 13 en vervolgens 12, plus punt,
dot, dot, totdat ik ben links met slechts één.

625
00:29:49,970 --> 00:29:53,146
Dus nu een computer wetenschapper zou doen
vragen, nou ja, wat doet dat allemaal gelijk?

626
00:29:53,146 --> 00:29:55,770
Het is gelijk aan eigenlijk een aantal betonnen
getal dat we konden zeker

627
00:29:55,770 --> 00:30:00,490
doen rekenkundig, maar we willen praten
de efficiëntie van algoritmen

628
00:30:00,490 --> 00:30:04,940
een beetje meer formulaically,
ongeacht hoe lang de lijst.

629
00:30:04,940 --> 00:30:06,240
>> En dus weet je wat?

630
00:30:06,240 --> 00:30:09,860
Dit is 16, maar zoals ik al eerder zei,
laten we gewoon bellen met de omvang van het probleem

631
00:30:09,860 --> 00:30:10,970
n, waarbij n een getal.

632
00:30:10,970 --> 00:30:13,220
Misschien is het 16, misschien is het
drie, misschien is het een miljoen.

633
00:30:13,220 --> 00:30:13,761
Ik weet het niet.

634
00:30:13,761 --> 00:30:14,390
Kan me niet schelen.

635
00:30:14,390 --> 00:30:16,520
Wat ik echt wil is
een formule die ik kan

636
00:30:16,520 --> 00:30:19,420
om dit algoritme vergelijken
tegen andere algoritmen

637
00:30:19,420 --> 00:30:22,350
dat iemand zou kunnen claimen
zijn beter of slechter.

638
00:30:22,350 --> 00:30:25,430
>> Dus het blijkt, en alleen ik
weten dit uit de lagere school,

639
00:30:25,430 --> 00:30:34,790
dat dit werkt eigenlijk naar hetzelfde
zoiets als n meer dan n plus één meer dan twee.

640
00:30:34,790 --> 00:30:40,020
En dit gebeurt evenaren, of
Natuurlijk, n kwadraat plus n meer dan twee.

641
00:30:40,020 --> 00:30:43,250
Dus als ik wilde een formule
voor hoeveel stappen

642
00:30:43,250 --> 00:30:46,330
waren betrokken bij naar alle
van die nummers weer

643
00:30:46,330 --> 00:30:52,681
en opnieuw en opnieuw, zou ik zeggen
het is n kwadraat plus n meer dan twee.

644
00:30:52,681 --> 00:30:53,430
Maar weet je wat?

645
00:30:53,430 --> 00:30:54,500
Dit ziet er gewoon rommelig.

646
00:30:54,500 --> 00:30:56,470
Ik heb echt een
algemeen gevoel van dingen.

647
00:30:56,470 --> 00:30:58,810
En je zou kunnen herinneren uit
middelbare school dat er

648
00:30:58,810 --> 00:31:00,660
is de notie van de hoogste orde termijn.

649
00:31:00,660 --> 00:31:05,300
Welke van deze voorwaarden, de n
kwadraat, de n, of de helft,

650
00:31:05,300 --> 00:31:07,550
heeft de meeste invloed in de tijd?

651
00:31:07,550 --> 00:31:11,920
Hoe groter krijgt n, waarin
van deze zaken het meest?

652
00:31:11,920 --> 00:31:15,560
>> Met andere woorden, als ik stop
op een miljoen, n kwadraat

653
00:31:15,560 --> 00:31:17,900
zal hoogstwaarschijnlijk
de dominerende factor,

654
00:31:17,900 --> 00:31:21,670
omdat een miljoen keer
zelf is een stuk groter

655
00:31:21,670 --> 00:31:23,682
dan plus een extra miljoen.

656
00:31:23,682 --> 00:31:24,390
Dus weet je wat?

657
00:31:24,390 --> 00:31:27,305
Dit is zo'n groot darn
nummer als u vierkant een nummer.

658
00:31:27,305 --> 00:31:28,430
Dit maakt eigenlijk niet uit.

659
00:31:28,430 --> 00:31:30,596
We gaan gewoon kruis dat
out en vergeet het.

660
00:31:30,596 --> 00:31:34,250
En dus een computer wetenschapper zou zeggen
dat de efficiëntie van dit algoritme

661
00:31:34,250 --> 00:31:37,850
in de orde van n squared--
Ik bedoel echt een benadering.

662
00:31:37,850 --> 00:31:40,810
Het is een soort van ongeveer n kwadraat.

663
00:31:40,810 --> 00:31:44,130
Na verloop van tijd, hoe groter
en n groter wordt, dit

664
00:31:44,130 --> 00:31:47,610
is een goede schatting voor wat
efficiency of gebrek aan efficiëntie

665
00:31:47,610 --> 00:31:49,400
van dit algoritme eigenlijk.

666
00:31:49,400 --> 00:31:52,040
En ik afleiden dat, uiteraard,
van daadwerkelijk doen van de wiskunde.

667
00:31:52,040 --> 00:31:54,040
Maar nu ben ik gewoon zwaaien
mijn handen, omdat ik net

668
00:31:54,040 --> 00:31:55,790
wil een algemeen gevoel van dit algoritme.

669
00:31:55,790 --> 00:31:58,850
>> Dus met behulp van dezelfde logica, ondertussen,
laten we eens kijken naar een ander algoritme

670
00:31:58,850 --> 00:32:01,162
we keken al at-- lineair zoeken.

671
00:32:01,162 --> 00:32:02,870
Toen ik op zoek was
de telefoon book--

672
00:32:02,870 --> 00:32:05,980
niet sorteren het, zoeken
via de telefoon book--

673
00:32:05,980 --> 00:32:09,197
we bleef maar zeggen dat het was
1000 stappen, of 500 stappen.

674
00:32:09,197 --> 00:32:10,280
Maar laten we generaliseren dat.

675
00:32:10,280 --> 00:32:12,860
Als er n pagina's in
het telefoonboek, wat is

676
00:32:12,860 --> 00:32:17,250
de rijtijden of de
efficiëntie van lineair zoeken?

677
00:32:17,250 --> 00:32:19,750
Het is aan de orde van
hoeveel stappen vinden

678
00:32:19,750 --> 00:32:24,210
Mike Smith met behulp van lineaire zoeken, de
eerste algoritme, of zelfs de tweede?

679
00:32:24,210 --> 00:32:27,240

680
00:32:27,240 --> 00:32:31,710
>> In het ergste geval, Mike
is aan het eind van het boek.

681
00:32:31,710 --> 00:32:35,590
Dus als het telefoonboek heeft 1.000 pagina's,
we zei vorige keer, in het ergste geval,

682
00:32:35,590 --> 00:32:38,380
Het zou kunnen nemen ongeveer hoe
vele pagina's om Mike te vinden?

683
00:32:38,380 --> 00:32:38,990
Net als 1000.

684
00:32:38,990 --> 00:32:39,830
Het is een bovengrens.

685
00:32:39,830 --> 00:32:41,790
Het is een slechtst denkbare situatie.

686
00:32:41,790 --> 00:32:44,410
Maar nogmaals, we zijn afgestapt
van nummers zoals 1000 nu.

687
00:32:44,410 --> 00:32:45,730
Het is gewoon n.

688
00:32:45,730 --> 00:32:47,470
>> Dus wat is de logische conclusie?

689
00:32:47,470 --> 00:32:50,210
Het vinden van Mike in een telefoon
boek dat n pagina's heeft

690
00:32:50,210 --> 00:32:55,280
zou kunnen nemen, in het ergste geval,
hoeveel stappen in de orde van n?

691
00:32:55,280 --> 00:32:58,110
En inderdaad een computer
wetenschapper zou zeggen

692
00:32:58,110 --> 00:33:02,340
dat de looptijd, of
prestaties of de efficiëntie

693
00:33:02,340 --> 00:33:07,470
of inefficiëntie, van een algoritme zoals
een lineair zoeken is in de orde van n.

694
00:33:07,470 --> 00:33:10,010
En we kunnen hetzelfde van toepassing
logica van iets uit het oversteken

695
00:33:10,010 --> 00:33:13,170
zoals ik net deed naar de tweede
algoritme we hadden met de telefoon boek,

696
00:33:13,170 --> 00:33:16,040
waar we gingen twee pagina's tegelijk.

697
00:33:16,040 --> 00:33:20,120
>> Dus 1.000 pagina telefoonboek zou
neem ons 500 pagina bochten, plus één

698
00:33:20,120 --> 00:33:21,910
als we het dubbele van een stukje terug.

699
00:33:21,910 --> 00:33:26,590
Dus als een telefoonboek heeft n pagina's, maar
we doen twee pagina's tegelijk,

700
00:33:26,590 --> 00:33:28,900
Dat is ongeveer wat?

701
00:33:28,900 --> 00:33:33,190
N over twee, dus dat is net als n meer dan twee.

702
00:33:33,190 --> 00:33:38,490
Maar ik maakte de vordering een
ogenblik geleden dat n meer dan two--

703
00:33:38,490 --> 00:33:41,060
dat is een beetje hetzelfde als gewoon n.

704
00:33:41,060 --> 00:33:44,050
Het is gewoon een constante factor,
informatici zou zeggen.

705
00:33:44,050 --> 00:33:45,970
Laten we alleen richten op
de variabelen, really--

706
00:33:45,970 --> 00:33:47,780
de belangrijkste variabelen in de vergelijking.

707
00:33:47,780 --> 00:33:52,530
>> Dus lineair zoeken, of gedaan één
pagina per keer of twee pagina's tegelijk,

708
00:33:52,530 --> 00:33:54,810
is een soort van wezen hetzelfde.

709
00:33:54,810 --> 00:33:56,880
Het is nog steeds aan de orde van n.

710
00:33:56,880 --> 00:34:01,930
Maar ik had met mijn foto eerdere
dat de derde algoritme niet

711
00:34:01,930 --> 00:34:02,480
lineair.

712
00:34:02,480 --> 00:34:03,605
Het was niet een rechte lijn.

713
00:34:03,605 --> 00:34:08,659
Het was dat de gebogen lijn, en de
algebraïsche formule er was wat?

714
00:34:08,659 --> 00:34:11,812
Log van N-- dus meld basis twee van n.

715
00:34:11,812 --> 00:34:14,520
En we hoeven niet in te gaan
veel detail op logaritmes vandaag,

716
00:34:14,520 --> 00:34:17,394
maar de meeste computer wetenschappers zou niet
zelfs je vertellen wat de basis is.

717
00:34:17,394 --> 00:34:20,639
Want het is allemaal
constanten, zo te zeggen,

718
00:34:20,639 --> 00:34:22,659
slechts kleine numerieke verschillen.

719
00:34:22,659 --> 00:34:31,179
En dus dit zou een zeer gemeenschappelijk zijn
manier voor met name formele computer

720
00:34:31,179 --> 00:34:33,949
wetenschappers op een bord of
programmeurs op een wit bord

721
00:34:33,949 --> 00:34:36,889
eigenlijk ruzie die
algorithme zouden gebruiken

722
00:34:36,889 --> 00:34:39,500
of wat de efficiëntie
hun algoritme is.

723
00:34:39,500 --> 00:34:42,960
>> En dit is niet per se iets
u bespreken in elk detail,

724
00:34:42,960 --> 00:34:47,889
maar een goede programmeur is iemand
die heeft een stevige, formele achtergrond.

725
00:34:47,889 --> 00:34:50,120
Hij is in staat om te spreken
je in dit soort manier

726
00:34:50,120 --> 00:34:53,350
en eigenlijk maken
kwalitatieve argumenten

727
00:34:53,350 --> 00:34:56,870
waarom een ​​algoritme of
een stukje software

728
00:34:56,870 --> 00:35:00,165
superieur in zekere zin naar de andere.

729
00:35:00,165 --> 00:35:02,540
Omdat je zeker kon
alleen nog maar programma van één persoon

730
00:35:02,540 --> 00:35:04,980
en tel het aantal seconden
het duurt om een ​​aantal nummers te sorteren,

731
00:35:04,980 --> 00:35:06,710
en je kunt een aantal draaien
programma andere persoon

732
00:35:06,710 --> 00:35:08,418
en tel het aantal
seconden duurt.

733
00:35:08,418 --> 00:35:12,840
Maar dit is een meer algemene zin dat
u kunt gebruiken om algoritmen te analyseren,

734
00:35:12,840 --> 00:35:15,520
als je wil, net aan
papier of gewoon verbaal.

735
00:35:15,520 --> 00:35:18,430
Zonder zelfs het runnen van het, zonder
zelfs maar te proberen sample-ingangen,

736
00:35:18,430 --> 00:35:20,180
je kunt gewoon redeneren doorheen.

737
00:35:20,180 --> 00:35:24,670
En dus met het inhuren van een ontwikkelaar of indien
met hem of haar soort pleiten voor u

738
00:35:24,670 --> 00:35:28,460
waarom hun algoritme, hun geheime
saus voor het zoeken miljarden

739
00:35:28,460 --> 00:35:30,580
van webpagina's voor uw
bedrijf is beter, deze

740
00:35:30,580 --> 00:35:33,302
zijn de soorten argumenten die zij
Idealiter kunnen maken.

741
00:35:33,302 --> 00:35:35,010
Of in ieder geval deze zijn
het soort dingen

742
00:35:35,010 --> 00:35:40,211
die zou komen in de discussie, op
althans in een zeer formele discussie.

743
00:35:40,211 --> 00:35:40,710
Okee.

744
00:35:40,710 --> 00:35:44,400
Dus Ben voorgestelde iets
genaamd selectie sorteren.

745
00:35:44,400 --> 00:35:48,200
Maar ik ga voor te stellen dat er
andere manieren om dit te doen, ook.

746
00:35:48,200 --> 00:35:50,400
Wat ik niet echt leuk
over Ben's algoritme

747
00:35:50,400 --> 00:35:54,400
is dat hij liep, of
hebben me lopen, heen en weer

748
00:35:54,400 --> 00:35:56,930
en heen en weer en heen en weer.

749
00:35:56,930 --> 00:36:04,130
Wat als in plaats ik moest doen
zoiets als deze nummers hier

750
00:36:04,130 --> 00:36:08,200
en ik waren gewoon met elkaar omgaan
nummer op zijn beurt als ik het gezien?

751
00:36:08,200 --> 00:36:10,780
>> Met andere woorden, hier
mijn lijst van nummers.

752
00:36:10,780 --> 00:36:12,944
Vier, een, drie, twee.

753
00:36:12,944 --> 00:36:14,360
En ik ga het volgende doen.

754
00:36:14,360 --> 00:36:17,230
Ik ga naar de nummers in te lassen
waar ze horen in plaats

755
00:36:17,230 --> 00:36:18,980
dan ze een voor een hebt geselecteerd.

756
00:36:18,980 --> 00:36:20,820
Met andere woorden, hier is de nummer vier.

757
00:36:20,820 --> 00:36:22,430
>> Hier is mijn originele lijst.

758
00:36:22,430 --> 00:36:25,290
En ik ga behouden
in wezen een nieuwe lijst hier.

759
00:36:25,290 --> 00:36:26,710
Dus dit is de oude lijst.

760
00:36:26,710 --> 00:36:28,560
Dit is de nieuwe lijst.

761
00:36:28,560 --> 00:36:30,220
Ik zie de nummer vier eerste.

762
00:36:30,220 --> 00:36:34,500
Mijn nieuwe lijst is aanvankelijk leeg,
dus is triviaal het geval

763
00:36:34,500 --> 00:36:36,410
dat vier is nu assorti lijst.

764
00:36:36,410 --> 00:36:39,560
Ik ben gewoon het nemen van de nummer Ik ben gegeven,
en Ik zet het in mijn nieuwe lijst.

765
00:36:39,560 --> 00:36:41,460
>> Is dit nieuwe lijst gesorteerd?

766
00:36:41,460 --> 00:36:41,990
Ja.

767
00:36:41,990 --> 00:36:45,090
Het is dom, want er is slechts één
element, maar het is absoluut gesorteerd.

768
00:36:45,090 --> 00:36:46,390
Er is niets op zijn plaats.

769
00:36:46,390 --> 00:36:49,290
Het is meer interessant, dit algoritme,
toen ik naar de volgende stap.

770
00:36:49,290 --> 00:36:50,550
>> Nu heb ik een.

771
00:36:50,550 --> 00:36:55,430
Dus een natuurlijk behoort bij de
begin of het einde van deze nieuwe lijst?

772
00:36:55,430 --> 00:36:56,360
Het begin.

773
00:36:56,360 --> 00:36:58,530
Dus ik moet wat werk nu te doen.

774
00:36:58,530 --> 00:37:01,410
Ik heb het nemen van een aantal
vrijheden met mijn marker

775
00:37:01,410 --> 00:37:03,120
door gewoon te tekenen dingen
waar ik wil dat ze,

776
00:37:03,120 --> 00:37:05,320
maar dat is niet echt
nauwkeurig in een computer.

777
00:37:05,320 --> 00:37:08,530
Een computer, zoals we weten, heeft
RAM of Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
en dat is een byte en
een byte en een byte.

779
00:37:12,411 --> 00:37:14,910
En als je een gigabyte aan
RAM, heb je een miljard bytes,

780
00:37:14,910 --> 00:37:16,680
maar ze zijn fysiek op één locatie.

781
00:37:16,680 --> 00:37:19,540
Je kunt niet zomaar verplaatsen stuff
door het tekenen op het bord

782
00:37:19,540 --> 00:37:20,750
waar je maar wilt.

783
00:37:20,750 --> 00:37:24,090
Dus als mijn nieuwe lijst heeft
vier locaties in het geheugen,

784
00:37:24,090 --> 00:37:27,480
helaas is de vier is
al op de verkeerde plaats.

785
00:37:27,480 --> 00:37:30,410
>> Dus om het nummer in te voegen één
Ik kan niet zomaar hier tekenen.

786
00:37:30,410 --> 00:37:31,901
Deze geheugenplaats bestaat niet.

787
00:37:31,901 --> 00:37:35,150
Dat zou bedriegen, en ik ben geweest
vreemdgaan pictorially voor een paar minuten

788
00:37:35,150 --> 00:37:35,800
hier.

789
00:37:35,800 --> 00:37:40,950
Dus echt, als ik wil er hier te zetten,
Ik moet de vier tijdelijk kopiëren

790
00:37:40,950 --> 00:37:43,030
en zet dan de één daar.

791
00:37:43,030 --> 00:37:45,500
>> Dat is prima, dat klopt,
Dat is technisch mogelijk,

792
00:37:45,500 --> 00:37:48,410
maar beseffen dat is extra werk.

793
00:37:48,410 --> 00:37:50,460
Ik heb niet gewoon het nummer op zijn plaats.

794
00:37:50,460 --> 00:37:53,026
Ik moest eerst een te verplaatsen
nummer, zet het dan op zijn plaats,

795
00:37:53,026 --> 00:37:54,650
dus ik soort verdubbelde mijn hoeveelheid werk.

796
00:37:54,650 --> 00:37:55,660
Dus hou dat in gedachten.

797
00:37:55,660 --> 00:37:57,120
>> Maar ik ben nu klaar met dit element.

798
00:37:57,120 --> 00:37:59,056
Nu wil ik de nummer drie te grijpen.

799
00:37:59,056 --> 00:38:00,430
Waar, natuurlijk, behoort het?

800
00:38:00,430 --> 00:38:01,480
Tussenin.

801
00:38:01,480 --> 00:38:03,650
Ik kan niet bedriegen meer
en zet ze gewoon daar,

802
00:38:03,650 --> 00:38:06,770
want, nogmaals, dit geheugen
in fysieke locaties.

803
00:38:06,770 --> 00:38:10,900
Dus ik moet de vier kopiëren
en zet de drie hier.

804
00:38:10,900 --> 00:38:11,550
Niet een groot probleem.

805
00:38:11,550 --> 00:38:14,610
Het is gewoon een extra stap
again-- voelt erg goedkoop.

806
00:38:14,610 --> 00:38:16,445
>> Maar nu moet ik gaan naar de twee.

807
00:38:16,445 --> 00:38:17,820
De twee natuurlijk hoort hier.

808
00:38:17,820 --> 00:38:20,990
Nu begin je te zien hoe
het werk kan opstapelen.

809
00:38:20,990 --> 00:38:23,520
Nu, wat moet ik doen?

810
00:38:23,520 --> 00:38:28,570
Ja, ik heb de vier te bewegen,
Ik moet dan de drie kopiëren,

811
00:38:28,570 --> 00:38:31,200
en nu kan ik de twee plaatsen.

812
00:38:31,200 --> 00:38:34,460
En de vangst met deze
algoritme, interessant genoeg,

813
00:38:34,460 --> 00:38:41,050
is dat veronderstellen we hebben een meer extreme
geval waar het laten we zeggen acht, zeven,

814
00:38:41,050 --> 00:38:45,150
zes, vijf, vier, drie, twee, één.

815
00:38:45,150 --> 00:38:49,450
Dit is in veel contexten
het ergste geval,

816
00:38:49,450 --> 00:38:51,570
omdat de darn ding
letterlijk achteruit.

817
00:38:51,570 --> 00:38:53,670
>> Het maakt eigenlijk niet
invloed op Ben's algoritme,

818
00:38:53,670 --> 00:38:55,940
omdat in Ben's selectie
sort hij gaat houden

819
00:38:55,940 --> 00:38:58,359
ga heen en weer door de lijst.

820
00:38:58,359 --> 00:39:01,150
En omdat hij was altijd op zoek
door de hele resterende lijst,

821
00:39:01,150 --> 00:39:02,858
het maakt niet uit
waarbij de elementen.

822
00:39:02,858 --> 00:39:05,630
Maar in dit geval met mijn invoegen
approach-- laten we proberen dit.

823
00:39:05,630 --> 00:39:08,616
>> Dus één, twee, drie, vier,
vijf, zes, zeven, acht.

824
00:39:08,616 --> 00:39:11,630
Een twee drie vier,
vijf, zes, zeven, acht.

825
00:39:11,630 --> 00:39:14,320
Ik ga naar de acht te nemen,
en waar moet ik het zeggen?

826
00:39:14,320 --> 00:39:17,260
Nou, aan het begin van mijn lijst,
omdat deze nieuwe lijst wordt gesorteerd.

827
00:39:17,260 --> 00:39:18,760
En ik steek het uit.

828
00:39:18,760 --> 00:39:20,551
>> Waar vind ik de zeven?

829
00:39:20,551 --> 00:39:21,050
Verdomme.

830
00:39:21,050 --> 00:39:23,174
Het moet er naartoe te gaan, dus
Ik moet wat doen kopiëren.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
En nu de zeven gaat hier.

833
00:39:28,480 --> 00:39:29,860
Nu gaan I op de zes.

834
00:39:29,860 --> 00:39:30,980
Nu is het nog meer werk.

835
00:39:30,980 --> 00:39:32,570
>> Acht heeft om hier te gaan.

836
00:39:32,570 --> 00:39:33,920
Seven heeft om hier te gaan.

837
00:39:33,920 --> 00:39:35,450
Nu de zes kunt hier terecht.

838
00:39:35,450 --> 00:39:37,950
Nu pak ik de vijf.

839
00:39:37,950 --> 00:39:40,560
Nu de acht moet gaan
hier, zeven heeft hier te gaan,

840
00:39:40,560 --> 00:39:43,650
zes heeft hier te gaan, en
nu de vijf en herhaal.

841
00:39:43,650 --> 00:39:46,610
En ik ben er vrij veel
voortdurend in beweging is.

842
00:39:46,610 --> 00:39:52,950
>> Dus aan het eind, dit algorithm-- we zullen
noem het inbrengen sort-- eigenlijk

843
00:39:52,950 --> 00:39:55,020
heeft een hoop werk, ook.

844
00:39:55,020 --> 00:39:56,970
Het is gewoon anders
soort werk dan Ben's.

845
00:39:56,970 --> 00:40:00,090
het werk van Ben had me op de been
heen en weer de hele tijd,

846
00:40:00,090 --> 00:40:03,510
het selecteren van de kleinste
element opnieuw en opnieuw.

847
00:40:03,510 --> 00:40:06,660
Dus het was dit heel visuele soort werk.

848
00:40:06,660 --> 00:40:10,600
>> Deze andere algoritme, dat nog
correct-- zal de baan te krijgen done--

849
00:40:10,600 --> 00:40:12,800
net verandert de hoeveelheid werk.

850
00:40:12,800 --> 00:40:15,420
Het lijkt erop dat in eerste instantie ben je
besparing, omdat je gewoon bent

851
00:40:15,420 --> 00:40:19,190
behandeling van elk element
up front zonder te lopen alle

852
00:40:19,190 --> 00:40:20,930
de weg door de lijst zoals Ben was.

853
00:40:20,930 --> 00:40:25,300
Maar het probleem is, zeker in deze
gek gevallen waarin het allemaal achteruit,

854
00:40:25,300 --> 00:40:27,830
je bent gewoon een soort van
uitstellen van het harde werk

855
00:40:27,830 --> 00:40:30,360
totdat je je fouten te repareren.

856
00:40:30,360 --> 00:40:33,919
>> En dus als je kunt deze voorstellen
acht en zeven en zes en vijf

857
00:40:33,919 --> 00:40:36,710
en later vier en drie en twee
bewegen hun weg door de lijst,

858
00:40:36,710 --> 00:40:39,060
we hebben net veranderde de
soort werk dat we doen.

859
00:40:39,060 --> 00:40:42,340
In plaats van het doen van het op de
begin van mijn iteratie,

860
00:40:42,340 --> 00:40:45,250
Ik ben gewoon te doen aan de
einde van elke iteratie.

861
00:40:45,250 --> 00:40:50,550
Zo blijkt dat dit algoritme
Ook het algemeen genoemd insertion sort,

862
00:40:50,550 --> 00:40:52,190
Ook in de orde van n kwadraat.

863
00:40:52,190 --> 00:40:56,480
Het is eigenlijk niet beter,
niet beter helemaal.

864
00:40:56,480 --> 00:41:00,810
>> Echter, er is een derde benadering
Ik zou ons aanmoedigen om te overwegen,

865
00:41:00,810 --> 00:41:02,970
wat dit.

866
00:41:02,970 --> 00:41:07,850
Dus stel mijn lijst, voor de eenvoud
opnieuw, vier, één, drie,

867
00:41:07,850 --> 00:41:11,080
two-- slechts vier nummers.

868
00:41:11,080 --> 00:41:13,300
Ben had een goede intuïtie,
goede menselijke intuïtie

869
00:41:13,300 --> 00:41:16,340
voor, waardoor we vast heel
lijst eventually-- insertion sort.

870
00:41:16,340 --> 00:41:18,020
Ik overgehaald ons mee.

871
00:41:18,020 --> 00:41:22,530
Maar laten we eens kijken naar de
eenvoudigste manier om deze lijst te bevestigen.

872
00:41:22,530 --> 00:41:24,110
>> Deze lijst is niet gesorteerd.

873
00:41:24,110 --> 00:41:26,130
Waarom?

874
00:41:26,130 --> 00:41:31,920
In het Engels, uitleggen waarom
het is niet echt opgelost.

875
00:41:31,920 --> 00:41:33,400
Wat betekent het niet te sorteren?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: Het is niet sequentieel.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: niet op volgorde.

878
00:41:34,990 --> 00:41:35,822
Geef me een voorbeeld.

879
00:41:35,822 --> 00:41:37,180
>> STUDENT: Leg ze in orde.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Geef me een meer specifiek voorbeeld.

882
00:41:38,790 --> 00:41:39,832
>> STUDENT: oplopende volgorde.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Niet oplopende volgorde.

884
00:41:41,206 --> 00:41:42,100
Wees nauwkeuriger.

885
00:41:42,100 --> 00:41:45,190
Ik weet niet wat je bedoelt met oplopende.

886
00:41:45,190 --> 00:41:47,150
Wat is er mis?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: De kleinste van de
getallen is niet in de eerste ruimte.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: Kleinste-nummer
niet in de eerste ruimte.

889
00:41:51,140 --> 00:41:52,120
Wees specifieker.

890
00:41:52,120 --> 00:41:55,000
Ik ben beginnen aan te slaan.

891
00:41:55,000 --> 00:41:59,470
We rekenen, maar
wat is niet in orde hier?

892
00:41:59,470 --> 00:42:00,707
>> STUDENT: numerieke volgorde.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: Numerieke volgorde.

894
00:42:02,040 --> 00:42:04,248
Ieders soort boekhouding
Het hier-- zeer hoog niveau.

895
00:42:04,248 --> 00:42:07,450
Gewoon letterlijk me vertellen wat er
verkeerd als een vijf-jaar-oude macht.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: Plus één.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Wat is dat?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: Plus één.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Wat bedoel je plus één?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Geef me een ander vijf jaar oud.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Wat is er mis, mama?

904
00:42:18,330 --> 00:42:19,940
Wat is er mis, vader?

905
00:42:19,940 --> 00:42:22,808
Wat bedoel je dit niet gesorteerd?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: Het is niet de juiste plaats.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Wat is
niet op de juiste plaats?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Four.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, goed.

910
00:42:27,090 --> 00:42:29,110
Dus vier is niet waar het zou moeten zijn.

911
00:42:29,110 --> 00:42:30,590
In het bijzonder is dit recht?

912
00:42:30,590 --> 00:42:33,000
Vier en een, de eerste
twee nummers die ik zie.

913
00:42:33,000 --> 00:42:34,930
Is dit juist?

914
00:42:34,930 --> 00:42:36,427
Nee, ze zijn niet in orde, toch?

915
00:42:36,427 --> 00:42:38,135
In feite, denk nu
om een ​​computer, ook.

916
00:42:38,135 --> 00:42:40,824
Het kan alleen maar kijken naar misschien één,
misschien twee dingen op once--

917
00:42:40,824 --> 00:42:43,240
en eigenlijk maar één ding
tegelijk, maar het kan ten minste

918
00:42:43,240 --> 00:42:45,790
kijken naar een ding dan de
volgende ding ernaast.

919
00:42:45,790 --> 00:42:47,380
>> Dus zijn deze in orde?

920
00:42:47,380 --> 00:42:48,032
Natuurlijk niet.

921
00:42:48,032 --> 00:42:48,740
Dus weet je wat?

922
00:42:48,740 --> 00:42:51,020
Waarom gaan we niet nemen kindje
stappen vaststelling van dit probleem

923
00:42:51,020 --> 00:42:53,410
in plaats van het doen van deze buitensporige
algoritmen als Ben, waarbij

924
00:42:53,410 --> 00:42:56,440
hij is een soort van de vaststelling van het door
doorlussen de lijst

925
00:42:56,440 --> 00:42:59,670
in plaats van te doen wat ik deed, waar de
Ik gewoon een soort van vaste het als we gaan?

926
00:42:59,670 --> 00:43:03,650
Laten we gewoon letterlijk breken de
notie van order-- numerieke volgorde,

927
00:43:03,650 --> 00:43:06,990
noem het wat je want--
in deze paarsgewijze vergelijkingen.

928
00:43:06,990 --> 00:43:07,590
>> Vier en één.

929
00:43:07,590 --> 00:43:09,970
Is dit de juiste volgorde?

930
00:43:09,970 --> 00:43:11,310
Dus laten we dat oplossen.

931
00:43:11,310 --> 00:43:14,700
Eén en vier, en dan
we zullen gewoon kopiëren dat.

932
00:43:14,700 --> 00:43:15,560
Oké, goed.

933
00:43:15,560 --> 00:43:17,022
Ik bevestigde een en vier.

934
00:43:17,022 --> 00:43:18,320
Drie en twee?

935
00:43:18,320 --> 00:43:18,820
Nee.

936
00:43:18,820 --> 00:43:21,690
Laat mijn woorden niet overeen met mijn vingers.

937
00:43:21,690 --> 00:43:23,695
Vier en drie?

938
00:43:23,695 --> 00:43:27,930
>> Het is niet in orde, dus ik ga
één, drie, vier, twee doen.

939
00:43:27,930 --> 00:43:28,680
OK goed.

940
00:43:28,680 --> 00:43:32,310
Nu vier en twee?

941
00:43:32,310 --> 00:43:33,370
We moeten dit op te lossen, ook.

942
00:43:33,370 --> 00:43:36,700
Dus één, drie, twee, vier.

943
00:43:36,700 --> 00:43:39,820
Dus wordt het opgelost?

944
00:43:39,820 --> 00:43:43,170
Nee, maar is het dichter bij gesorteerd?

945
00:43:43,170 --> 00:43:48,930
>> Het is, omdat we dit vast
fout, vaste we deze fout,

946
00:43:48,930 --> 00:43:50,370
en we vaste deze fout.

947
00:43:50,370 --> 00:43:52,420
Dus vaste we drie fouten aantoonbaar.

948
00:43:52,420 --> 00:43:58,100
Nog steeds niet echt kijken gesorteerde, maar
het objectief dichter bij gesorteerde

949
00:43:58,100 --> 00:44:00,080
omdat we vast een aantal van die fouten.

950
00:44:00,080 --> 00:44:02,047
>> Nu, wat moet ik nu doen?

951
00:44:02,047 --> 00:44:03,630
Ik soort van aan het einde van de lijst.

952
00:44:03,630 --> 00:44:05,680
Ik leek te hebben vastgesteld
alle fouten, maar nee.

953
00:44:05,680 --> 00:44:08,510
Omdat in dit geval een aantal nummers
zou hebben geborreld dichterbij

954
00:44:08,510 --> 00:44:10,410
andere nummers die
zijn nog steeds niet in orde.

955
00:44:10,410 --> 00:44:12,951
Dus laten we het opnieuw doen, en ik zal
doe het gewoon op zijn plaats deze tijd.

956
00:44:12,951 --> 00:44:14,170
Een en drie?

957
00:44:14,170 --> 00:44:14,720
Het is goed.

958
00:44:14,720 --> 00:44:16,070
Drie en twee?

959
00:44:16,070 --> 00:44:17,560
Natuurlijk niet, dus laten we dat veranderen.

960
00:44:17,560 --> 00:44:19,160
Dus twee, drie.

961
00:44:19,160 --> 00:44:21,340
Drie en vier?

962
00:44:21,340 --> 00:44:24,370
En laten we nu gewoon
vooral pedant hier.

963
00:44:24,370 --> 00:44:26,350
Is het opgelost?

964
00:44:26,350 --> 00:44:29,280
U, mensen weet dat het opgelost.

965
00:44:29,280 --> 00:44:30,400
>> Ik zou het opnieuw te proberen.

966
00:44:30,400 --> 00:44:31,900
Dus Olivia stelt Ik probeer het opnieuw.

967
00:44:31,900 --> 00:44:32,530
Waarom?

968
00:44:32,530 --> 00:44:35,810
Omdat een computer niet heeft
de luxe van onze menselijke ogen

969
00:44:35,810 --> 00:44:38,080
van slechts vluchtig back-- Oké, ik ben klaar.

970
00:44:38,080 --> 00:44:41,610
Hoe werkt de computer vast te stellen
dat de lijst nu wordt gesorteerd?

971
00:44:41,610 --> 00:44:44,590
Mechanisch.

972
00:44:44,590 --> 00:44:47,650
>> Ik moet gaan door
eens te meer, en alleen als ik

973
00:44:47,650 --> 00:44:51,190
niet maken / vinden geen fouten kan ik
dan is de conclusie als de computer, yep,

974
00:44:51,190 --> 00:44:51,980
we zijn goed om te gaan.

975
00:44:51,980 --> 00:44:54,850
Dus een en twee, twee en
drie, drie en vier.

976
00:44:54,850 --> 00:44:58,030
Nu kan ik definitief zeggen dat dit
gesorteerd, omdat ik geen wijzigingen aangebracht.

977
00:44:58,030 --> 00:45:01,940
Nu zou het een bug te zijn en gewoon
dwaas als ik, de computer,

978
00:45:01,940 --> 00:45:05,640
vroeg diezelfde vragen opnieuw
verwacht verschillende antwoorden.

979
00:45:05,640 --> 00:45:07,110
Zou niet mogen gebeuren.

980
00:45:07,110 --> 00:45:08,600
>> En nu de lijst wordt gesorteerd.

981
00:45:08,600 --> 00:45:12,630
Helaas, speelduur van
dit algoritme wordt ook N kwadraat.

982
00:45:12,630 --> 00:45:13,130
Waarom?

983
00:45:13,130 --> 00:45:19,520
Want je hebt n getallen, en in de
ergste geval moet je n nummers bewegen

984
00:45:19,520 --> 00:45:23,637
n keer want je hebt om door te gaan
terug om te controleren en eventueel op te lossen

985
00:45:23,637 --> 00:45:24,220
deze getallen.

986
00:45:24,220 --> 00:45:26,280
En we kunnen meer doen
formele analyse, ook.

987
00:45:26,280 --> 00:45:29,530
>> Dus dit is allemaal te zeggen dat we hebben genomen
drie benaderingen, een

988
00:45:29,530 --> 00:45:32,210
van hen onmiddellijk intuïtief
van de vleermuis van Ben

989
00:45:32,210 --> 00:45:35,170
aan mijn voorgestelde invoeging
sorteren naar deze ene

990
00:45:35,170 --> 00:45:38,540
waar je een soort uit het oog verliezen
de bos door de bomen aanvankelijk.

991
00:45:38,540 --> 00:45:41,760
Maar dan als je een stap terug te nemen,
voila, we hebben de sortering begrip vast.

992
00:45:41,760 --> 00:45:43,824
Dus dit is, durf te zeggen,
een lager niveau misschien

993
00:45:43,824 --> 00:45:45,740
dan sommige van de andere
algoritmes, maar laten we

994
00:45:45,740 --> 00:45:48,550
kijken of we niet kunnen visualiseren
die door middel van deze.

995
00:45:48,550 --> 00:45:51,450
>> Dus dit is een aantal leuke
software die iemand

996
00:45:51,450 --> 00:45:56,110
schreef het gebruik van kleurrijke bars dat is
gaan naar de volgende te doen voor ons.

997
00:45:56,110 --> 00:45:57,736
Elk van deze staven een getal.

998
00:45:57,736 --> 00:46:00,026
Taller de bar, hoe groter
het getal, hoe kleiner de bar,

999
00:46:00,026 --> 00:46:00,990
hoe kleiner het aantal.

1000
00:46:00,990 --> 00:46:05,880
Dus idealiter willen we een mooie piramide
waar het begint klein en krijgt grote,

1001
00:46:05,880 --> 00:46:08,330
en dat zou betekenen dat
deze bars worden gesorteerd.

1002
00:46:08,330 --> 00:46:11,200
Dus ik ga om te gaan en te kiezen,
Zo Ben's algoritme

1003
00:46:11,200 --> 00:46:13,990
first-- selectie sorteren.

1004
00:46:13,990 --> 00:46:16,220
>> En let op wat het doet.

1005
00:46:16,220 --> 00:46:18,670
De manier waarop ze hebt ervoor gekozen om
visualiseren dit algoritme

1006
00:46:18,670 --> 00:46:22,090
is dat, net zoals ik was
wandelen door mijn lijst,

1007
00:46:22,090 --> 00:46:24,710
dit programma loopt
door middel van haar lijst van nummers,

1008
00:46:24,710 --> 00:46:28,160
markeren in roze elk
getal dat het kijken naar.

1009
00:46:28,160 --> 00:46:32,360
En wat er gaat nu gebeuren?

1010
00:46:32,360 --> 00:46:35,154
>> Het kleinste getal dat
I of Ben plotseling

1011
00:46:35,154 --> 00:46:36,820
wordt verplaatst naar het begin van de lijst.

1012
00:46:36,820 --> 00:46:40,037
En merkt dat ze deden verdrijven
het getal dat er,

1013
00:46:40,037 --> 00:46:41,120
en dat is prima.

1014
00:46:41,120 --> 00:46:42,600
Ik heb niet in die mate van detail.

1015
00:46:42,600 --> 00:46:44,308
Maar we moeten zetten
dat nummer ergens,

1016
00:46:44,308 --> 00:46:47,775
dus we net verhuisd naar de
open plek die is gemaakt.

1017
00:46:47,775 --> 00:46:49,900
Dus ik ga dit te versnellen
up, omdat anders

1018
00:46:49,900 --> 00:46:51,871
wordt al snel erg vervelend.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animatie snelheid- daar gaan we.

1021
00:46:58,600 --> 00:47:01,850
Dus nu hetzelfde principe
Ik was de toepassing, maar u

1022
00:47:01,850 --> 00:47:06,540
kunnen beginnen met het algoritme te voelen, als je
zal, of zie het een beetje duidelijker.

1023
00:47:06,540 --> 00:47:13,190
En dit algoritme tot gevolg heeft
het selecteren van de volgende kleinste element,

1024
00:47:13,190 --> 00:47:16,422
dus je gaat om te beginnen met
zie het opvoeren aan de linkerkant.

1025
00:47:16,422 --> 00:47:19,130
En elke iteratie ik
voorgesteld, het doet een beetje minder werk.

1026
00:47:19,130 --> 00:47:21,921
Het hoeft niet de hele weg te gaan
terug naar de linkerkant van de lijst,

1027
00:47:21,921 --> 00:47:23,900
omdat het al
kent hen zijn gesorteerd.

1028
00:47:23,900 --> 00:47:28,129
Dus het soort voelt alsof het
versnellen, hoewel elke stap

1029
00:47:28,129 --> 00:47:29,420
waarbij dezelfde hoeveelheid tijd.

1030
00:47:29,420 --> 00:47:31,600
Er is gewoon minder stappen overgebleven.

1031
00:47:31,600 --> 00:47:35,240
En nu kunt u soort voelen de
algoritme voor het opruimen van het einde ervan,

1032
00:47:35,240 --> 00:47:37,040
en ook nu is het opgelost.

1033
00:47:37,040 --> 00:47:41,620
>> Dus insertion sort is allemaal gedaan.

1034
00:47:41,620 --> 00:47:43,600
Ik moet opnieuw willekeurig de array.

1035
00:47:43,600 --> 00:47:45,940
En let op, ik kan het gewoon
houden randomizing het,

1036
00:47:45,940 --> 00:47:50,630
en we zullen een benadering van krijgen
dezelfde aanpak, insertion sort.

1037
00:47:50,630 --> 00:47:55,050
Laat me langzaam naar beneden om hier.

1038
00:47:55,050 --> 00:47:56,915
Laten we beginnen dat voorbij.

1039
00:47:56,915 --> 00:47:57,414
Stop.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Laten we overslaan vier.

1042
00:48:02,410 --> 00:48:03,200
Daar gaan we.

1043
00:48:03,200 --> 00:48:04,190
Willekeurig ze array.

1044
00:48:04,190 --> 00:48:05,555
En hier gaan-- we insertion sort.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Spelen.

1047
00:48:12,800 --> 00:48:17,280
Merk op dat het omgaan met elkaar
element zij tegenkomt meteen,

1048
00:48:17,280 --> 00:48:20,282
maar indien het behoort in
de verkeerde plaats bericht

1049
00:48:20,282 --> 00:48:21,740
al het werk dat moet gebeuren.

1050
00:48:21,740 --> 00:48:24,700
We moeten blijven verschuiven meer
en nog veel meer elementen om ruimte te maken

1051
00:48:24,700 --> 00:48:27,340
voor degene die willen we in te voeren.

1052
00:48:27,340 --> 00:48:30,740
>> Dus we focussen op de
linkereinde van alleen de lijst.

1053
00:48:30,740 --> 00:48:34,460
Merken we nog niet eens gekeken at-- we
zijn niet gemarkeerd in roze iets

1054
00:48:34,460 --> 00:48:35,610
naar rechts.

1055
00:48:35,610 --> 00:48:38,180
We hebben alleen te maken met
de problemen als we gaan,

1056
00:48:38,180 --> 00:48:40,430
maar we zijn het creëren van een heleboel
werken voor onszelf nog steeds.

1057
00:48:40,430 --> 00:48:44,410
En dus als we versnellen dit op
nu laten voltooien,

1058
00:48:44,410 --> 00:48:46,210
het heeft een ander gevoel aan het inderdaad.

1059
00:48:46,210 --> 00:48:50,150
Het is gewoon te focussen op de linker einde, maar
het doen van een beetje meer werk als needed--

1060
00:48:50,150 --> 00:48:53,230
soort dingen glad te strijken
over, de vaststelling van dingen,

1061
00:48:53,230 --> 00:48:58,350
maar uiteindelijk omgaan met
elk element een voor een

1062
00:48:58,350 --> 00:49:07,740
tot we bij goed the--, we
weten allemaal hoe dit gaat eindigen,

1063
00:49:07,740 --> 00:49:09,700
dus het is een beetje underwhelming misschien.

1064
00:49:09,700 --> 00:49:12,830
>> Maar de lijst in de end--
spoiler-- zal worden gesorteerd.

1065
00:49:12,830 --> 00:49:15,300
Dus laten we eens kijken naar een laatste.

1066
00:49:15,300 --> 00:49:16,840
We kunnen niet gewoon overslaan nu.

1067
00:49:16,840 --> 00:49:18,000
We zijn er bijna.

1068
00:49:18,000 --> 00:49:19,980
Twee om te gaan, een te gaan.

1069
00:49:19,980 --> 00:49:22,680
En voila.

1070
00:49:22,680 --> 00:49:23,450
Uitstekend.

1071
00:49:23,450 --> 00:49:27,220
>> Dus nu laten we een laatste,
opnieuw randomizing met bubble sort.

1072
00:49:27,220 --> 00:49:31,690
En merk hier, vooral als ik langzaam naar
naar beneden, dit betekent houden stoten door.

1073
00:49:31,690 --> 00:49:36,830
Maar let op het maakt paarsgewijs
comparisons-- soort van lokale oplossingen.

1074
00:49:36,830 --> 00:49:39,050
Maar zodra we krijgen
het einde van de lijst in roze,

1075
00:49:39,050 --> 00:49:40,690
wat er gaat nog een keer gebeuren?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ja, het gaat om te hebben
opnieuw, omdat het alleen

1078
00:49:46,830 --> 00:49:49,870
vaste paarsgewijs fouten.

1079
00:49:49,870 --> 00:49:53,120
En dat zou weer anderen hebben geopenbaard.

1080
00:49:53,120 --> 00:49:58,950
En dus als je dit te versnellen, zul je
zien dat, net zoals de naam impliceert,

1081
00:49:58,950 --> 00:50:01,870
de kleinere elements-- of liever,
de grotere elements-- beginnen

1082
00:50:01,870 --> 00:50:03,740
te borrelen naar de top, als je wil.

1083
00:50:03,740 --> 00:50:07,380
En de kleinere elementen
begint te borrelen naar links.

1084
00:50:07,380 --> 00:50:10,780
En inderdaad, dat is een soort van
het visuele effect ook.

1085
00:50:10,780 --> 00:50:17,150
En dus dit zal eindigen afwerking
op soortgelijke wijze ook.

1086
00:50:17,150 --> 00:50:19,160
>> We hoeven niet te blijven stilstaan
op dit ene.

1087
00:50:19,160 --> 00:50:21,010
Laat me dit nu te openen, ook.

1088
00:50:21,010 --> 00:50:24,040
Er is een paar andere sorteeralgoritmen
in de wereld, een paar van die

1089
00:50:24,040 --> 00:50:25,580
Hier worden gevangen.

1090
00:50:25,580 --> 00:50:29,960
En vooral voor leerlingen die niet
noodzakelijkerwijs visuele of wiskundige,

1091
00:50:29,960 --> 00:50:31,930
zoals we eerder deden, kunnen wij
Dit doen ook audially

1092
00:50:31,930 --> 00:50:34,210
als we associëren een geluid met deze.

1093
00:50:34,210 --> 00:50:36,990
En gewoon voor de lol, hier is een
aantal verschillende algoritmen,

1094
00:50:36,990 --> 00:50:40,950
en een van hen in het bijzonder je bent
gaan merken heet "merge sort."

1095
00:50:40,950 --> 00:50:43,250
>> Het is eigenlijk een fundamenteel
beter algoritme,

1096
00:50:43,250 --> 00:50:45,860
zodanig dat soort fuseren, een van
degene die je gaat zien,

1097
00:50:45,860 --> 00:50:49,170
is niet orde van n kwadraat.

1098
00:50:49,170 --> 00:50:57,280
Het is aan de orde van n keer in te loggen of
n, die in feite kleiner en dus

1099
00:50:57,280 --> 00:50:58,940
sneller dan de andere drie.

1100
00:50:58,940 --> 00:51:00,670
En er is een ander koppel
domme degenen die we zullen zien.

1101
00:51:00,670 --> 00:51:01,933
>> Dus hier gaan we met een geluid.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Dit is insertion sort, dus nogmaals
het is alleen te maken met de elementen

1104
00:51:10,490 --> 00:51:13,420
als ze komen.

1105
00:51:13,420 --> 00:51:17,180
Dit is bubble sort, dus het is
die ze als paren tegelijk.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
En nogmaals, de grootste elementen
borrelen naar de top.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Next up selectie sorteren.

1110
00:51:41,710 --> 00:51:45,420
Dit is Ben's algoritme, waarbij
nogmaals dat hij de selectie van iteratief

1111
00:51:45,420 --> 00:51:46,843
de volgende kleinste element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
En nogmaals, nu kun je echt horen dat
het is versnellen, maar alleen voor zover

1114
00:51:53,900 --> 00:51:58,230
want het doet steeds minder
werken op elke iteratie.

1115
00:51:58,230 --> 00:52:04,170
Dit is de snellere, samenvoegen sorteren,
die sorteert clusters getallen

1116
00:52:04,170 --> 00:52:05,971
elkaar en vervolgens te combineren.

1117
00:52:05,971 --> 00:52:07,720
Dus look-- links
de helft is al opgelost.

1118
00:52:07,720 --> 00:52:14,165
>> Nu is het sorteren van de rechterhelft, en
nu het gaat om ze te combineren tot één.

1119
00:52:14,165 --> 00:52:19,160
Dit is iets genaamd "Gnome sort."

1120
00:52:19,160 --> 00:52:23,460
En je kunt soort zien dat
het is heen en weer,

1121
00:52:23,460 --> 00:52:27,950
vaststelling van het werk een beetje hier en
er voordat het overgaat tot nieuw werk.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
En dat is het.

1124
00:52:33,692 --> 00:52:36,400
Er is een ander soort, dat is
echt alleen voor academische doeleinden,

1125
00:52:36,400 --> 00:52:40,980
genaamd "domme soort," waarbij rekening
uw gegevens, sorteert het willekeurig,

1126
00:52:40,980 --> 00:52:43,350
en controleert vervolgens of het wordt gesorteerd.

1127
00:52:43,350 --> 00:52:47,880
En als het niet is, herordent is
willekeurig, controleert of het wordt gesorteerd,

1128
00:52:47,880 --> 00:52:49,440
en zo niet herhaalt.

1129
00:52:49,440 --> 00:52:52,660
En in theorie, probabilistisch
dit zal voltooien,

1130
00:52:52,660 --> 00:52:54,140
maar na heel wat tijd.

1131
00:52:54,140 --> 00:52:56,930
Het is niet de meest
efficiënte algoritmen.

1132
00:52:56,930 --> 00:53:02,550
Dus vragen op die
bijzonder algoritmen of iets

1133
00:53:02,550 --> 00:53:04,720
daar verwant zijn, ook?

1134
00:53:04,720 --> 00:53:09,430
>> Nou, laten we nu plagen elkaar wat er allemaal
deze lijnen zijn die ik heb al getekend

1135
00:53:09,430 --> 00:53:15,090
en wat ik ervan uitgaande dat de computer
kunnen doen onder de motorkap.

1136
00:53:15,090 --> 00:53:18,650
Ik zou zeggen dat al deze nummers
Ik blijf drawing-- ze moeten krijgen

1137
00:53:18,650 --> 00:53:21,330
ergens in het geheugen opgeslagen.

1138
00:53:21,330 --> 00:53:24,130
We zullen zich te ontdoen van deze man krijgt nu ook.

1139
00:53:24,130 --> 00:53:30,110
>> Dus een stuk geheugen in een
computer-- dus RAM DIMM is

1140
00:53:30,110 --> 00:53:35,480
wat wij zochten naar gisteren, dual
inline memory module-- ziet er als volgt uit.

1141
00:53:35,480 --> 00:53:39,370
En elk van deze kleine zwarte chips
is bepaald aantal bytes, typisch.

1142
00:53:39,370 --> 00:53:44,380
En dan is de gouden pinnen zijn als de
draden die aansluiten op de computer,

1143
00:53:44,380 --> 00:53:47,521
en de groene silicium bord is gewoon
wat houdt alles in elkaar.

1144
00:53:47,521 --> 00:53:48,770
Dus wat betekent dit eigenlijk?

1145
00:53:48,770 --> 00:53:53,180
Als ik soort van hetzelfde beeld te schetsen,
Laten we veronderstellen voor de eenvoud

1146
00:53:53,180 --> 00:53:55,280
dat deze DIMM, dual
inline memory module,

1147
00:53:55,280 --> 00:54:00,530
is één gigabyte RAM-geheugen, één gigabyte
geheugen, dat is hoeveel bytes in totaal?

1148
00:54:00,530 --> 00:54:02,100
Een gigabyte is hoeveel bytes?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Meer dan dat.

1151
00:54:06,030 --> 00:54:09,960
1124 is kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega is miljoen.

1153
00:54:11,730 --> 00:54:14,570
Giga is een miljard.

1154
00:54:14,570 --> 00:54:15,070
>> Ben ik liegen?

1155
00:54:15,070 --> 00:54:16,670
Kunnen we het etiket te lezen, zelfs?

1156
00:54:16,670 --> 00:54:19,920
Dit is eigenlijk 128
gigabytes, dus het is nog veel meer.

1157
00:54:19,920 --> 00:54:22,130
Maar wij zullen dit doen alsof
is slechts één gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Dus dat betekent dat er een miljard
bytes van het geheugen beschikbaar voor mij

1159
00:54:25,640 --> 00:54:29,770
of 8 miljard bits, maar we gaan
om te praten in termen van bytes nu,

1160
00:54:29,770 --> 00:54:30,750
vooruit gaan.

1161
00:54:30,750 --> 00:54:36,330
>> Dus wat dat betekent is dit
een byte, is een byte,

1162
00:54:36,330 --> 00:54:38,680
dit is een ander byte,
en als we echt wilden

1163
00:54:38,680 --> 00:54:43,280
specifieke we zouden moeten zijn
trek je een miljard pleintjes.

1164
00:54:43,280 --> 00:54:44,320
Maar wat betekent dat?

1165
00:54:44,320 --> 00:54:46,420
Nou, laat me gewoon te zoomen
in op deze foto.

1166
00:54:46,420 --> 00:54:50,900
Als ik iets heb dat eruit ziet
zoals dit nu, dat is vier bytes.

1167
00:54:50,900 --> 00:54:53,710
>> En dus kon ik vier nummers hier te zetten.

1168
00:54:53,710 --> 00:54:54,990
Een twee drie vier.

1169
00:54:54,990 --> 00:55:00,170
Of ik kon vier letters of symbolen te zetten.

1170
00:55:00,170 --> 00:55:02,620
"Hey!" kon daar gaan,
omdat elk van de letters,

1171
00:55:02,620 --> 00:55:04,370
we eerder hebben besproken,
kan worden vertegenwoordigd

1172
00:55:04,370 --> 00:55:06,650
met acht bits of ASCII of een byte.

1173
00:55:06,650 --> 00:55:09,370
Dus met andere woorden, kunt u
zet 8 miljard dingen binnen

1174
00:55:09,370 --> 00:55:11,137
van deze stok van het geheugen.

1175
00:55:11,137 --> 00:55:14,345
Nu, wat betekent het om dingen terug te zetten
aan rug aan rug in het geheugen als deze?

1176
00:55:14,345 --> 00:55:17,330
Dit is wat een programmeur
zou een "array." noemen

1177
00:55:17,330 --> 00:55:21,250
In een computerprogramma, denk je niet
de onderliggende hardware, per se.

1178
00:55:21,250 --> 00:55:24,427
Je denkt alleen maar aan jezelf als het hebben van
toegang tot een miljard bytes totaal,

1179
00:55:24,427 --> 00:55:26,010
en je kunt alles wat je wilt met haar.

1180
00:55:26,010 --> 00:55:27,880
Maar voor het gemak
het is over het algemeen nuttig

1181
00:55:27,880 --> 00:55:31,202
om uw geheugen rechts houden
naast elkaar als deze.

1182
00:55:31,202 --> 00:55:33,660
Dus als ik inzoomen op dit--
omdat we zeker niet van plan

1183
00:55:33,660 --> 00:55:39,310
een miljard beetje squares-- trekken
Laten we veronderstellen dat deze raad vertegenwoordigt

1184
00:55:39,310 --> 00:55:40,610
die stok van het geheugen nu.

1185
00:55:40,610 --> 00:55:43,800
En ik zal gewoon te trekken zo veel als mijn
marker eindigt hier geeft me.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Dus nu hebben we een stok
van het geheugen op het bord

1188
00:55:52,300 --> 00:55:56,400
dat heeft een, twee, drie, vier, vijf,
zes, een, twee, drie, vier, vijf, zes,

1189
00:55:56,400 --> 00:56:01,130
seven-- dus 42 bytes
geheugen op het totale scherm.

1190
00:56:01,130 --> 00:56:01,630
Dank je.

1191
00:56:01,630 --> 00:56:02,838
Ja, deed mijn rekenkunde rechts.

1192
00:56:02,838 --> 00:56:05,120
Dus 42 bytes geheugen in.

1193
00:56:05,120 --> 00:56:06,660
Dus wat betekent dit eigenlijk?

1194
00:56:06,660 --> 00:56:09,830
Nou ja, een computerprogrammeur
zou eigenlijk in het algemeen

1195
00:56:09,830 --> 00:56:12,450
denk aan dit geheugen als adresseerbare.

1196
00:56:12,450 --> 00:56:16,630
Met andere woorden, elk van deze
locaties in het geheugen, in hardware,

1197
00:56:16,630 --> 00:56:18,030
heeft een uniek adres.

1198
00:56:18,030 --> 00:56:22,020
>> Het is niet zo complex als One Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
In plaats daarvan, het is gewoon een nummer.

1200
00:56:23,830 --> 00:56:27,930
Dit is byte getal nul, is
heeft weergegeven, twee, drie is,

1201
00:56:27,930 --> 00:56:30,327
en dit is 41.

1202
00:56:30,327 --> 00:56:30,910
Wacht even.

1203
00:56:30,910 --> 00:56:32,510
Ik dacht dat ik zei 42 een moment geleden.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Ik begon te tellen bij nul,
dus dat is eigenlijk juist.

1206
00:56:37,772 --> 00:56:40,980
Nu hoeven we niet om daadwerkelijk te tekenen
als een raster, en als je het te tekenen als een raster

1207
00:56:40,980 --> 00:56:43,520
Ik denk dat dingen eigenlijk
een beetje misleidend.

1208
00:56:43,520 --> 00:56:46,650
Wat een programmeur zou doen,
in zijn of haar eigen geest,

1209
00:56:46,650 --> 00:56:50,310
over het algemeen denken van deze
geheugen is net als een tape,

1210
00:56:50,310 --> 00:56:53,340
als een stuk afplakband
dat gaat gewoon door en voor altijd

1211
00:56:53,340 --> 00:56:54,980
of totdat u opraken van het geheugen.

1212
00:56:54,980 --> 00:56:59,200
Dus een meer gebruikelijke manier om te tekenen
en denk maar over het geheugen

1213
00:56:59,200 --> 00:57:03,710
zou zijn dat dit byte nul, een,
twee, drie, en toen puntje, puntje, puntje.

1214
00:57:03,710 --> 00:57:07,650
En je hebt zo'n 42 bytes totaal, zelfs
hoewel fysiek het misschien eigenlijk

1215
00:57:07,650 --> 00:57:09,480
iets meer als dit.

1216
00:57:09,480 --> 00:57:12,850
>> Dus als je nu denken van uw
geheugen als deze, net als een tape,

1217
00:57:12,850 --> 00:57:17,640
dit is wat een programmeur weer
zou een reeks geheugencellen noemen.

1218
00:57:17,640 --> 00:57:20,660
En als je wilt eigenlijk te slaan
iets in een computergeheugen,

1219
00:57:20,660 --> 00:57:23,290
je over het algemeen doen slaan dingen
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Dus we hebben gesproken over getallen.

1221
00:57:25,010 --> 00:57:30,880
En toen ik wilde om problemen op te lossen
zoals vier, één, drie, twee,

1222
00:57:30,880 --> 00:57:33,820
hoewel ik was gewoon tekenen
alleen de nummers vier, een, drie,

1223
00:57:33,820 --> 00:57:39,490
twee op het bord, de computer zou
echt deze opstelling in het geheugen.

1224
00:57:39,490 --> 00:57:43,347
>> En wat zou naast het zijn
twee in het geheugen van de computer?

1225
00:57:43,347 --> 00:57:44,680
Nou, er is geen antwoord op.

1226
00:57:44,680 --> 00:57:45,770
We weten niet echt.

1227
00:57:45,770 --> 00:57:48,200
En zolang de
computer heeft het niet nodig,

1228
00:57:48,200 --> 00:57:51,440
het hoeft niet te schelen wat er is
om de nummers doet de zorg over.

1229
00:57:51,440 --> 00:57:55,130
En toen ik zei eerder dat een computer
kan alleen maar kijken naar een adres in een tijd,

1230
00:57:55,130 --> 00:57:56,170
dit is een soort van waarom.

1231
00:57:56,170 --> 00:57:59,490
>> Niet in tegenstelling tot een record
-speler en een leeskop

1232
00:57:59,490 --> 00:58:03,030
alleen in staat om te kijken naar een bepaald
groef in een fysieke old-school plaat

1233
00:58:03,030 --> 00:58:06,500
tegelijkertijd, eveneens
Kan een computer dankzij

1234
00:58:06,500 --> 00:58:09,810
om de CPU en de
Intel-instructieset,

1235
00:58:09,810 --> 00:58:12,480
onder wie de instructie
wordt gelezen uit het geheugen

1236
00:58:12,480 --> 00:58:15,590
of op te slaan naar een memory--
computer kan alleen maar kijken

1237
00:58:15,590 --> 00:58:19,210
op één locatie bij een tijd--
soms een combinatie daarvan,

1238
00:58:19,210 --> 00:58:21,770
maar eigenlijk gewoon één plaats tegelijk.

1239
00:58:21,770 --> 00:58:24,770
Dus toen we aan het doen waren
deze verschillende algoritmes,

1240
00:58:24,770 --> 00:58:28,110
Ik ben niet alleen schrijven in een
vacuum-- vier, één, drie, twee.

1241
00:58:28,110 --> 00:58:30,849
Die aantallen eigenlijk behoren
ergens fysiek in het geheugen.

1242
00:58:30,849 --> 00:58:32,890
Dus er zijn piepkleine
transistors of een soort

1243
00:58:32,890 --> 00:58:35,840
elektronica onder de
hood opslaan van deze waarden.

1244
00:58:35,840 --> 00:58:40,460
>> En in het totaal, hoeveel bits
die betrokken zijn op dit moment, alleen maar om duidelijk te zijn?

1245
00:58:40,460 --> 00:58:45,580
Dus dit is vier bytes, of
nu is het 32 ​​bits in totaal.

1246
00:58:45,580 --> 00:58:49,280
Er zijn dus eigenlijk 32 nullen en
degenen die het samenstellen van deze vier dingen.

1247
00:58:49,280 --> 00:58:52,070
Er is zelfs nog meer dan hier, maar
weer hebben we niet schelen.

1248
00:58:52,070 --> 00:58:55,120
>> Dus nu laten we vragen een ander
vraag het gebruik van het geheugen,

1249
00:58:55,120 --> 00:58:57,519
omdat aan het einde
van de dag in variantie.

1250
00:58:57,519 --> 00:59:00,310
Het maakt niet uit wat we zouden kunnen doen met
de computer, aan het eind van de dag

1251
00:59:00,310 --> 00:59:02,560
de hardware blijft de
Hetzelfde onder de motorkap.

1252
00:59:02,560 --> 00:59:04,670
Hoe zou ik slaan een woord hier?

1253
00:59:04,670 --> 00:59:09,710
Nou ja, een woord in een computer, zoals
"Hey!" zouden worden opgeslagen, net als dit.

1254
00:59:09,710 --> 00:59:12,300
En als je wilde een langere
Word kunt u eenvoudig

1255
00:59:12,300 --> 00:59:19,120
overschrijven dat en iets te zeggen
zoals "hallo" en winkel die hier.

1256
00:59:19,120 --> 00:59:23,930
>> En dus ook hier deze contiguousness
is juist een voordeel,

1257
00:59:23,930 --> 00:59:26,530
want een computer kan gewoon
van rechts naar links.

1258
00:59:26,530 --> 00:59:28,680
Maar hier is een vraag.

1259
00:59:28,680 --> 00:59:33,480
In het kader van dit woord,
h-e-l-l-o, uitroepteken,

1260
00:59:33,480 --> 00:59:38,740
hoe kan de computer laten weten waar de
woord begint en waar het woord eindigt?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
In de context van getallen,
hoe werkt de computer

1263
00:59:43,800 --> 00:59:48,396
hoe lang de reeks
getallen is of wanneer het begint?

1264
00:59:48,396 --> 00:59:50,270
Nou, het blijkt out--
en we zullen niet te veel gaan

1265
00:59:50,270 --> 00:59:54,970
in dit niveau van detail--
computers bewegen spullen rond in het geheugen

1266
00:59:54,970 --> 00:59:57,800
letterlijk door middel van deze adressen.

1267
00:59:57,800 --> 01:00:02,080
Dus in een computer, als je
het schrijven van code om dingen op te slaan

1268
01:00:02,080 --> 01:00:05,800
zoals woorden, wat je bent
eigenlijk doet is aan het typen

1269
01:00:05,800 --> 01:00:11,320
uitdrukkingen die onthouden waar in
geheugen van de computer deze woorden zijn.

1270
01:00:11,320 --> 01:00:14,370
Dus laat me een zeer,
eenvoudig voorbeeld.

1271
01:00:14,370 --> 01:00:18,260
>> Ik ga om te gaan en
het openen van een eenvoudige tekst-programma,

1272
01:00:18,260 --> 01:00:20,330
en ik ga om te creëren
een bestand genaamd hello.c.

1273
01:00:20,330 --> 01:00:22,849
De meeste van deze gegevens wordt
zal niet in te gaan tot in detail,

1274
01:00:22,849 --> 01:00:25,140
maar ik ga naar een schrijven
programma in diezelfde taal,

1275
01:00:25,140 --> 01:00:31,140
C. Dit is veel meer intimiderend,
Ik zou zeggen, dan Scratch,

1276
01:00:31,140 --> 01:00:32,490
maar het is zeer vergelijkbaar in de geest.

1277
01:00:32,490 --> 01:00:34,364
In feite zijn deze curly
braces-- je kunt soort

1278
01:00:34,364 --> 01:00:37,820
denk aan wat ik net gedaan als dit.

1279
01:00:37,820 --> 01:00:39,240
>> Laten we dit doen, eigenlijk.

1280
01:00:39,240 --> 01:00:45,100
Als groene vlag geklikt,
doe het volgende.

1281
01:00:45,100 --> 01:00:50,210
Ik wil om uit te printen "hallo."

1282
01:00:50,210 --> 01:00:51,500
Dus dit is nu pseudocode.

1283
01:00:51,500 --> 01:00:53,000
Ik ben soort van het vervagen van de lijnen.

1284
01:00:53,000 --> 01:00:56,750
In C, deze taal ik spreek
over, deze lijn druk hello

1285
01:00:56,750 --> 01:01:01,940
eigenlijk wordt "printf" met
wat haakjes en een puntkomma.

1286
01:01:01,940 --> 01:01:03,480
>> Maar het is precies hetzelfde idee.

1287
01:01:03,480 --> 01:01:06,730
En deze zeer gebruiksvriendelijk
"Wanneer groene vlag geklikt" wordt

1288
01:01:06,730 --> 01:01:10,182
de veel meer mysterieuze "int main leegte."

1289
01:01:10,182 --> 01:01:12,890
En dit heeft echt geen mapping,
dus ik ga gewoon negeren dat.

1290
01:01:12,890 --> 01:01:17,210
Maar de accolades zijn als de
gebogen puzzelstukjes als deze.

1291
01:01:17,210 --> 01:01:18,700
>> Zo kun je soort raden.

1292
01:01:18,700 --> 01:01:22,357
Zelfs als je nog nooit hebt geprogrammeerd,
wat heeft dit programma waarschijnlijk nog doen?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Waarschijnlijk drukt hello
met een uitroepteken.

1295
01:01:28,000 --> 01:01:29,150
>> Dus laten we proberen dat.

1296
01:01:29,150 --> 01:01:30,800
Ik ga om het op te slaan.

1297
01:01:30,800 --> 01:01:34,000
Dit is, nogmaals, een zeer
oude school omgeving.

1298
01:01:34,000 --> 01:01:35,420
Ik kan het niet klikt, kan ik niet slepen.

1299
01:01:35,420 --> 01:01:36,910
Ik moet commando's typen.

1300
01:01:36,910 --> 01:01:41,320
Dus ik wil mijn programma uit te voeren, zodat
Ik kan dit doen, zoals hello.c.

1301
01:01:41,320 --> 01:01:42,292
Dat is het bestand dat ik liep.

1302
01:01:42,292 --> 01:01:43,500
Maar wacht, ik mis een stap.

1303
01:01:43,500 --> 01:01:46,470
Wat deden we zeggen is een noodzakelijke
stap voor een taal als C?

1304
01:01:46,470 --> 01:01:49,470
Ik heb net geschreven bron
code, maar wat heb ik nodig?

1305
01:01:49,470 --> 01:01:50,670
Ja, ik heb een compiler.

1306
01:01:50,670 --> 01:01:57,670
Dus op mijn Mac hier, ik heb een
programma genaamd GCC, GNU C-compiler,

1307
01:01:57,670 --> 01:02:03,990
waardoor ik dit-- beurt doen
mijn source code in, zullen we het noemen,

1308
01:02:03,990 --> 01:02:04,930
machine code.

1309
01:02:04,930 --> 01:02:10,180
>> En ik kan zien dat,
opnieuw, als hieronder, deze

1310
01:02:10,180 --> 01:02:14,090
zijn de nullen en enen ik gewoon
gemaakt op basis van mijn broncode,

1311
01:02:14,090 --> 01:02:15,730
alle nullen en enen.

1312
01:02:15,730 --> 01:02:17,770
En als ik wil lopen
mijn program-- het gebeurt

1313
01:02:17,770 --> 01:02:23,010
a.out te worden uitgenodigd voor
historische reasons-- "hallo."

1314
01:02:23,010 --> 01:02:24,070
Ik kan het opnieuw uit te voeren.

1315
01:02:24,070 --> 01:02:25,690
Hallo hallo hallo.

1316
01:02:25,690 --> 01:02:27,430
En het lijkt te werken.

1317
01:02:27,430 --> 01:02:31,000
>> Maar dat betekent dat ergens in mijn
geheugen van de computer zijn de woorden

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, uitroepteken.

1319
01:02:35,279 --> 01:02:38,070
En het blijkt, net als een terzijde,
wat een computer zouden in het algemeen

1320
01:02:38,070 --> 01:02:40,550
doen zodat het weet wanneer
dingen beginnen en end-- het is

1321
01:02:40,550 --> 01:02:42,460
gaat naar een speciaal symbool hier zetten.

1322
01:02:42,460 --> 01:02:46,064
En de conventie is om het te zetten
cijfer nul aan het einde van een woord

1323
01:02:46,064 --> 01:02:48,230
zodat u weet waar het
daadwerkelijk eindigt, zodat u

1324
01:02:48,230 --> 01:02:52,750
houden niet uit te printen meer en meer
personages dan je eigenlijk van plan bent.

1325
01:02:52,750 --> 01:02:55,400
>> Maar de afhaalmaaltijd hier, zelfs
al is dit vrij mysterieus,

1326
01:02:55,400 --> 01:02:58,140
is dat het uiteindelijk
relatief eenvoudig.

1327
01:02:58,140 --> 01:03:04,550
Je kreeg een soort van band, een lege
ruimte waar je letters kunt schrijven.

1328
01:03:04,550 --> 01:03:07,150
Je moet gewoon een hebben
speciaal symbool, zoals willekeurig

1329
01:03:07,150 --> 01:03:10,316
het getal nul, tot eind gezet
je woorden zodat de computer weet,

1330
01:03:10,316 --> 01:03:13,410
oh, ik moet stoppen met afdrukken na
Ik zie het uitroepteken.

1331
01:03:13,410 --> 01:03:16,090
Omdat het volgende wat er
is een ASCII-waarde van nul,

1332
01:03:16,090 --> 01:03:19,125
of het null karakter
iemand zou noemen.

1333
01:03:19,125 --> 01:03:21,500
Maar er is een soort van een probleem
hier, en laten we keren terug

1334
01:03:21,500 --> 01:03:23,320
om nummers voor een moment.

1335
01:03:23,320 --> 01:03:28,720
Stel dat ik doe, in feite,
een matrix van getallen,

1336
01:03:28,720 --> 01:03:30,730
en veronderstellen dat de
programma dat ik aan het schrijven ben is

1337
01:03:30,730 --> 01:03:34,680
als een cijfer boek voor een leraar
en leraren klaslokaal.

1338
01:03:34,680 --> 01:03:38,720
En dit programma maakt hem of haar
te typen in scores van hun leerlingen

1339
01:03:38,720 --> 01:03:39,960
op quizzen.

1340
01:03:39,960 --> 01:03:43,750
En stel dat de student krijgt
100 op hun eerste quiz, misschien

1341
01:03:43,750 --> 01:03:49,920
als een 80 op de volgende, dan
75, dan is een 90 op de vierde quiz.

1342
01:03:49,920 --> 01:03:54,150
>> Dus op dit punt in het verhaal,
de array van grootte vier.

1343
01:03:54,150 --> 01:03:58,470
Er is absoluut meer geheugen in de
computer, maar de matrix, bij wijze van spreken,

1344
01:03:58,470 --> 01:04:00,350
is de omvang van vier.

1345
01:04:00,350 --> 01:04:06,060
Veronderstel nu dat de leraar wil
een vijfde quiz aan de klasse toe te wijzen.

1346
01:04:06,060 --> 01:04:08,510
Nou, een van de dingen die hij
of zij zal moeten doen

1347
01:04:08,510 --> 01:04:10,650
is nu een extra waarde op te slaan in.

1348
01:04:10,650 --> 01:04:15,490
Maar als de array de leraar
gemaakt in dit programma is van de grootte voor,

1349
01:04:15,490 --> 01:04:22,440
een van de problemen met een array is dat
je kunt niet zomaar blijven toevoegen aan het geheugen.

1350
01:04:22,440 --> 01:04:26,470
Want wat als een ander deel van de
programma heeft het woord "hey" daar?

1351
01:04:26,470 --> 01:04:29,650
>> Met andere woorden, kan mijn geheugen
gebruikt voor alles in een programma.

1352
01:04:29,650 --> 01:04:33,250
En als op voorhand Ik typte in, hey,
Ik wil invoeren vier quiz scores,

1353
01:04:33,250 --> 01:04:34,784
ze misschien hier en hier te gaan.

1354
01:04:34,784 --> 01:04:37,700
En als je opeens van gedachten verandert
later en zeggen dat ik wil een vijfde quiz

1355
01:04:37,700 --> 01:04:40,872
score, kun je niet zomaar
zet het waar u maar wilt,

1356
01:04:40,872 --> 01:04:42,580
want wat als dit
geheugen wordt gebruikt

1357
01:04:42,580 --> 01:04:45,990
iets else-- een ander programma
of een ander kenmerk van het programma

1358
01:04:45,990 --> 01:04:46,910
dat je draait?

1359
01:04:46,910 --> 01:04:50,650
Dus je moet denken bij voorbaat
hoe u wilt uw gegevens op te slaan,

1360
01:04:50,650 --> 01:04:54,480
want nu heb geschilderd
jezelf in een digitale hoek.

1361
01:04:54,480 --> 01:04:57,280
>> Dus een leraar zou in plaats daarvan
zeggen wanneer het schrijven van een programma

1362
01:04:57,280 --> 01:04:59,360
opslaan diens
rangen, weet je wat?

1363
01:04:59,360 --> 01:05:04,180
Ik ga vragen,
bij het schrijven van mijn programma,

1364
01:05:04,180 --> 01:05:12,070
dat wil nul, één, twee, drie,
vier, vijf, zes, acht graden totaal.

1365
01:05:12,070 --> 01:05:15,320
Dus één, twee, drie, vier,
vijf, zes, zeven, acht.

1366
01:05:15,320 --> 01:05:18,612
De leerkracht kan gewoon over-toewijzen
geheugen bij het schrijven van zijn of haar programma

1367
01:05:18,612 --> 01:05:19,570
en zeggen: weet je wat?

1368
01:05:19,570 --> 01:05:22,236
Ik ga nooit meer toe te wijzen
dan acht quizzen in een semester.

1369
01:05:22,236 --> 01:05:23,130
Dat is gewoon gek.

1370
01:05:23,130 --> 01:05:24,470
Ik zal nooit meer toe te wijzen dat.

1371
01:05:24,470 --> 01:05:28,270
Zodat deze manier hij of zij de
flexibiliteit opslaan student scores,

1372
01:05:28,270 --> 01:05:33,010
als 75, 90, en misschien een extra, waar
de student kreeg extra krediet, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Maar als de leraar nooit
gebruikt deze drie ruimten,

1374
01:05:36,130 --> 01:05:38,860
er is een intuïtieve afhaalmaaltijd hier.

1375
01:05:38,860 --> 01:05:41,410
Hij of zij is gewoon verspilling van ruimte.

1376
01:05:41,410 --> 01:05:44,790
Dus met andere woorden, er is dit
gemeenschappelijke afruil in de programmering

1377
01:05:44,790 --> 01:05:48,241
waar u ook kunt toewijzen
precies zoveel geheugen als je wilt,

1378
01:05:48,241 --> 01:05:51,490
de positieve kant daarvan is dat je super bent
efficient-- je bent het niet verkwistend

1379
01:05:51,490 --> 01:05:54,640
bij all-- maar de keerzijde van die
is wat als je van gedachten verandert wanneer

1380
01:05:54,640 --> 01:05:58,780
met behulp van het programma dat u wilt opslaan
meer data dan je oorspronkelijk de bedoeling was.

1381
01:05:58,780 --> 01:06:03,030
>> Dus misschien de oplossing is, dan,
schrijf uw programma zodanig

1382
01:06:03,030 --> 01:06:05,605
die ze gebruiken meer geheugen
dan ze eigenlijk nodig hebben.

1383
01:06:05,605 --> 01:06:07,730
Op deze manier zul je niet
te lopen in dit probleem,

1384
01:06:07,730 --> 01:06:09,730
maar je wordt verspilling.

1385
01:06:09,730 --> 01:06:12,960
En hoe meer geheugen van uw programma gebruikt,
zoals we gisteren besproken, minder

1386
01:06:12,960 --> 01:06:15,410
geheugen dat beschikbaar is
voor andere programma's,

1387
01:06:15,410 --> 01:06:18,790
hoe eerder uw computer kunnen vertragen
naar beneden als gevolg van virtueel geheugen.

1388
01:06:18,790 --> 01:06:22,670
En dus is de ideale oplossing zou wat zijn?

1389
01:06:22,670 --> 01:06:24,610
>> Under-verdeling lijkt slecht.

1390
01:06:24,610 --> 01:06:27,030
Over-verdeling lijkt slecht.

1391
01:06:27,030 --> 01:06:31,120
Dus wat zou een betere oplossing zijn?

1392
01:06:31,120 --> 01:06:32,390
Herschikking.

1393
01:06:32,390 --> 01:06:33,590
Be dynamischer.

1394
01:06:33,590 --> 01:06:37,520
Doe jezelf niet dwingen om te kiezen voor een
priori, in het begin, wat je wilt.

1395
01:06:37,520 --> 01:06:41,370
En zeker niet over-toewijzen,
opdat u verspilling.

1396
01:06:41,370 --> 01:06:45,770
>> En zo om dat doel te bereiken, we
moeten deze datastructuur te gooien,

1397
01:06:45,770 --> 01:06:48,100
zo te zeggen, weg.

1398
01:06:48,100 --> 01:06:51,080
En wat een programmeur
Doorgaans gebruikt

1399
01:06:51,080 --> 01:06:55,940
is zoiets als geen
-array maar een gekoppelde lijst.

1400
01:06:55,940 --> 01:07:00,860
Met andere woorden, zal hij of zij
beginnen te denken van hun geheugen

1401
01:07:00,860 --> 01:07:05,280
als een soort van een vorm die zij
kan trekken op de volgende manier.

1402
01:07:05,280 --> 01:07:08,520
Als ik wil een nummer op te slaan in
een program-- dus het is september,

1403
01:07:08,520 --> 01:07:12,600
Ik heb mijn leerlingen een quiz gegeven; ik wil
eerst quiz van de studenten op te slaan,

1404
01:07:12,600 --> 01:07:16,220
en ze kregen een 100 op het-- I
ga mijn computer te vragen,

1405
01:07:16,220 --> 01:07:19,540
door middel van het programma dat ik heb
geschreven, één stuk geheugen.

1406
01:07:19,540 --> 01:07:22,570
En ik ga naar de winkel
nummer 100 in, en dat is het.

1407
01:07:22,570 --> 01:07:24,820
>> Dan een paar weken later
als ik mijn tweede quiz,

1408
01:07:24,820 --> 01:07:27,890
en het is tijd om te typen
in dat 90%, ga ik

1409
01:07:27,890 --> 01:07:32,129
om de computer te vragen, hey, computer,
kan ik nog een brok van geheugen?

1410
01:07:32,129 --> 01:07:34,170
Het gaat om me geven deze
leeg stuk van het geheugen.

1411
01:07:34,170 --> 01:07:39,370
Ik ga in het nummer 90 te zetten,
maar in mijn programma een of andere manier of other--

1412
01:07:39,370 --> 01:07:42,100
en we zullen niet zorgen te maken over
de syntaxis voor dit-- ik nodig

1413
01:07:42,100 --> 01:07:44,430
een of andere manier keten deze dingen samen.

1414
01:07:44,430 --> 01:07:47,430
En ik zal ze samen met ketting
wat lijkt op een pijl hier.

1415
01:07:47,430 --> 01:07:50,050
>> De derde quiz die omhoog komt,
Ik ga zeggen, hey, computer,

1416
01:07:50,050 --> 01:07:51,680
geef me nog een stuk van het geheugen.

1417
01:07:51,680 --> 01:07:54,660
En ik ga neer te zetten
wat het ook was, zoals 75,

1418
01:07:54,660 --> 01:07:56,920
en ik moet deze keten
nu samen een of andere manier.

1419
01:07:56,920 --> 01:08:00,290
Vierde quiz komt langs, en misschien
Dat is tegen het einde van het semester.

1420
01:08:00,290 --> 01:08:03,140
En op dat moment mijn programma
misschien met behulp van het geheugen

1421
01:08:03,140 --> 01:08:05,540
all over the place, heel fysiek.

1422
01:08:05,540 --> 01:08:08,170
En dus gewoon voor de lol, ik ben
gaat deze voort te trekken

1423
01:08:08,170 --> 01:08:11,260
quiz-- ik vergeten wat het was; ik
denk dat een 80 of something--

1424
01:08:11,260 --> 01:08:12,500
hierheen.

1425
01:08:12,500 --> 01:08:15,920
>> Maar dat is prima, want pictorially
Ik ga deze lijn te trekken.

1426
01:08:15,920 --> 01:08:19,063
Met andere woorden, in werkelijkheid,
in de hardware van uw computer,

1427
01:08:19,063 --> 01:08:20,979
de eerste score zou
uiteindelijk hier, want het is

1428
01:08:20,979 --> 01:08:22,529
meteen aan het begin van het semester.

1429
01:08:22,529 --> 01:08:25,810
De volgende zou kunnen eindigen hier
omdat er een beetje van de tijd is verstreken

1430
01:08:25,810 --> 01:08:27,210
en het programma blijft draaien.

1431
01:08:27,210 --> 01:08:30,060
De volgende score, die was
een 75, misschien wel meer dan hier.

1432
01:08:30,060 --> 01:08:33,420
En de laatste score zou kunnen zijn
een 80, dat is meer dan hier.

1433
01:08:33,420 --> 01:08:38,729
>> Dus in werkelijkheid, fysiek, dit zou kunnen
wat geheugen van uw computer eruit ziet.

1434
01:08:38,729 --> 01:08:41,569
Maar dit is niet een nuttig mentaal
paradigma voor computerprogrammeur.

1435
01:08:41,569 --> 01:08:44,649
Waarom zou u de zorg waar de
heck uw gegevens belanden?

1436
01:08:44,649 --> 01:08:46,200
Je wil gewoon gegevens op te slaan.

1437
01:08:46,200 --> 01:08:49,390
>> Dit is net zoiets als onze discussie
eerder van het tekenen van de kubus.

1438
01:08:49,390 --> 01:08:52,200
Waarom heb je schelen wat
de hoek van de kubus

1439
01:08:52,200 --> 01:08:53,740
en hoe je moet draaien om het te tekenen?

1440
01:08:53,740 --> 01:08:54,950
Je wil gewoon een kubus.

1441
01:08:54,950 --> 01:08:57,359
Op dezelfde manier hier, je
ik wil gewoon naar de rang boek.

1442
01:08:57,359 --> 01:08:59,559
Je wilt alleen maar te denken aan
dit als een lijst van nummers.

1443
01:08:59,559 --> 01:09:01,350
Who cares hoe het
geïmplementeerd in hardware?

1444
01:09:01,350 --> 01:09:05,180
>> Dus de abstractie nu
is deze foto hier.

1445
01:09:05,180 --> 01:09:07,580
Dit is een gekoppelde lijst, zoals
een programmeur zou noemen,

1446
01:09:07,580 --> 01:09:10,640
voor zover u een
lijst uiteraard getallen.

1447
01:09:10,640 --> 01:09:14,990
Maar het is pictorially gekoppeld
door middel van deze pijlen,

1448
01:09:14,990 --> 01:09:18,510
en al deze pijlen zijn-- eronder
de kap, als je nieuwsgierig bent,

1449
01:09:18,510 --> 01:09:23,210
herinneren dat onze fysieke hardware heeft
adressen nul, één, twee, drie, vier.

1450
01:09:23,210 --> 01:09:28,465
Al deze pijlen zijn is als een kaart
of richtingen, waar als 90 is-- nu

1451
01:09:28,465 --> 01:09:29,090
Ik kreeg te tellen.

1452
01:09:29,090 --> 01:09:31,750
>> Nul, één, twee, drie,
vier, vijf, zes, zeven.

1453
01:09:31,750 --> 01:09:35,640
Het lijkt erop dat de 90 is op
geheugenadres nummer zeven.

1454
01:09:35,640 --> 01:09:38,460
Al deze pijlen zijn is
als een klein stukje papier

1455
01:09:38,460 --> 01:09:42,439
dat is het geven van een routebeschrijving naar het
programma dat zegt dat deze kaart volgen

1456
01:09:42,439 --> 01:09:43,880
om plaats zeven te krijgen.

1457
01:09:43,880 --> 01:09:46,680
En daar zult u de vondst
student tweede quiz score.

1458
01:09:46,680 --> 01:09:52,100
Intussen is de 75-- als ik doorga dit,
Deze zeven, acht, negen, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Deze andere pijl gewoon vertegenwoordigt
een kaart om het geheugen locatie 15.

1461
01:09:59,080 --> 01:10:02,550
Maar nogmaals, de programmeur het algemeen doet
niet om dit niveau van detail.

1462
01:10:02,550 --> 01:10:05,530
En in de meeste elke programmering
taal van vandaag, de programmeur

1463
01:10:05,530 --> 01:10:10,490
zal niet eens weten waar in het geheugen
deze nummers eigenlijk zijn.

1464
01:10:10,490 --> 01:10:14,830
Het enige wat hij of zij moet de zorg over is
dat ze ergens elkaar verbonden

1465
01:10:14,830 --> 01:10:18,390
in een datastructuur als deze.

1466
01:10:18,390 --> 01:10:21,580
>> Maar het blijkt niet
te technisch te worden.

1467
01:10:21,580 --> 01:10:27,430
Maar gewoon omdat we kunnen misschien
veroorloven om deze discussie hier,

1468
01:10:27,430 --> 01:10:33,630
veronderstellen dat we terugkomen
deze kwestie hier van een array.

1469
01:10:33,630 --> 01:10:35,780
Laten we eens kijken of we hier spijt van gaan.

1470
01:10:35,780 --> 01:10:42,950
Dit is 100, 90, 75 en 80.

1471
01:10:42,950 --> 01:10:44,980
>> Laat me even deze claim te maken.

1472
01:10:44,980 --> 01:10:48,980
Dit is een matrix, en opnieuw, de
opvallende kenmerk van een array

1473
01:10:48,980 --> 01:10:52,400
is dat al uw gegevens terug naar
rug aan rug in memory-- letterlijk

1474
01:10:52,400 --> 01:10:56,830
één byte of misschien vier bytes,
sommige vast aantal bytes afstand.

1475
01:10:56,830 --> 01:11:00,710
In een gelinkte lijst, die we kunnen trekken
als dit, onder de motorkap, die

1476
01:11:00,710 --> 01:11:02,000
weet waar dat spul is?

1477
01:11:02,000 --> 01:11:03,630
Het hoeft niet eens te stromen als dit.

1478
01:11:03,630 --> 01:11:06,050
Sommige gegevens kunnen zijn
terug naar links daar.

1479
01:11:06,050 --> 01:11:07,530
Je weet niet eens.

1480
01:11:07,530 --> 01:11:15,430
>> En dus met een array, heb je een
feature bekend als random access.

1481
01:11:15,430 --> 01:11:20,570
En wat random access betekent is
dat de computer direct kan springen

1482
01:11:20,570 --> 01:11:22,730
op elke locatie in de matrix.

1483
01:11:22,730 --> 01:11:23,580
Waarom?

1484
01:11:23,580 --> 01:11:26,000
Omdat de computer weet
dat de eerste locatie

1485
01:11:26,000 --> 01:11:29,540
nul, één, twee en drie.

1486
01:11:29,540 --> 01:11:33,890
>> En dus als je wilt gaan uit
dit element naar het volgende element,

1487
01:11:33,890 --> 01:11:36,099
je letterlijk, in de
geest computer, voeg een.

1488
01:11:36,099 --> 01:11:39,140
Als u wilt gaan naar het derde element,
voeg een-- volgende element, net

1489
01:11:39,140 --> 01:11:40,290
Voeg een toe.

1490
01:11:40,290 --> 01:11:42,980
Echter, in deze versie
van het verhaal, veronderstel

1491
01:11:42,980 --> 01:11:46,080
de computer is momenteel op zoek
op of omgaan met het nummer 100.

1492
01:11:46,080 --> 01:11:49,770
Hoe krijg je naar het volgende
rang in de rang boek?

1493
01:11:49,770 --> 01:11:52,560
>> Je moet nemen zeven
stappen, die willekeurig.

1494
01:11:52,560 --> 01:11:58,120
naar de volgende te krijgen, moet je
neem een ​​andere acht stappen om 15 te komen.

1495
01:11:58,120 --> 01:12:02,250
Met andere woorden, het is niet een
constante spleet tussen de nummers,

1496
01:12:02,250 --> 01:12:04,857
en zo het gewoon neemt de
computer meer tijd is het punt.

1497
01:12:04,857 --> 01:12:06,940
De computer heeft om te zoeken
door het geheugen in orde

1498
01:12:06,940 --> 01:12:08,990
om te vinden wat je zoekt.

1499
01:12:08,990 --> 01:12:14,260
>> Dus terwijl een array heeft de neiging om een ​​te zijn
snelle data structure-- omdat je

1500
01:12:14,260 --> 01:12:17,610
kan letterlijk gewoon doen eenvoudige rekenkundige
en komen waar je wilt door het toevoegen van een,

1501
01:12:17,610 --> 01:12:21,300
voor instance-- een gekoppelde lijst,
U offeren die functie.

1502
01:12:21,300 --> 01:12:24,020
Je kunt niet zomaar gaan van de eerste
naar de tweede naar de derde naar de vierde.

1503
01:12:24,020 --> 01:12:25,240
Je moet de kaart te volgen.

1504
01:12:25,240 --> 01:12:28,160
Je moet meer stappen te ondernemen
deze waarden, om welke

1505
01:12:28,160 --> 01:12:30,230
lijkt het toevoegen van een vergoeding.

1506
01:12:30,230 --> 01:12:35,910
Dus we betalen een prijs, maar wat was
de functie die hier Dan zocht?

1507
01:12:35,910 --> 01:12:38,110
Wat doet een gekoppelde lijst
blijkbaar kunnen we doen,

1508
01:12:38,110 --> 01:12:40,240
die de oorsprong van
dit verhaal?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Precies.

1511
01:12:43,830 --> 01:12:46,220
Een dynamische maat aan.

1512
01:12:46,220 --> 01:12:48,040
We kunnen aan deze lijst toevoegen.

1513
01:12:48,040 --> 01:12:51,430
We kunnen zelfs krimpen de lijst, dus
dat we alleen gebruik maakt van zoveel geheugen

1514
01:12:51,430 --> 01:12:55,560
zoals we eigenlijk willen en zo
we zijn nooit over-verdeling.

1515
01:12:55,560 --> 01:12:58,470
>> Nu alleen maar om echt spitsvondigheid kieskeurig,
er is een verborgen kosten.

1516
01:12:58,470 --> 01:13:01,980
Dus je moet niet alleen laat me overtuigen
je dat dit een dwingende afweging.

1517
01:13:01,980 --> 01:13:04,190
Er is een andere verborgen kosten hier.

1518
01:13:04,190 --> 01:13:06,550
Het voordeel, om duidelijk te zijn,
is dat we dynamiek.

1519
01:13:06,550 --> 01:13:10,359
Als ik wil een ander element, kan ik alleen maar
tekenen en zet een aantal in.

1520
01:13:10,359 --> 01:13:12,150
En dan kan ik het koppelen
met een foto hier,

1521
01:13:12,150 --> 01:13:14,970
overwegende dat meer dan hier, nogmaals, als ik heb
geschilderd mezelf in een hoekje,

1522
01:13:14,970 --> 01:13:19,410
als er iets anders wordt al gebruikt
het geheugen hier, ben ik pech.

1523
01:13:19,410 --> 01:13:21,700
Ik heb mezelf geschilderd in de hoek.

1524
01:13:21,700 --> 01:13:24,390
>> Maar wat is de verborgen
kosten in dit plaatje?

1525
01:13:24,390 --> 01:13:27,690
Het is niet alleen de hoeveelheid
tijd die het duurt

1526
01:13:27,690 --> 01:13:29,870
te gaan van hier naar hier,
die zeven stappen, dan

1527
01:13:29,870 --> 01:13:32,820
acht stappen, die meer dan één.

1528
01:13:32,820 --> 01:13:34,830
Wat is een ander verborgen kosten?

1529
01:13:34,830 --> 01:13:35,440
Niet alleen de tijd.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Aanvullende informatie is
moet deze beeldkwaliteit.

1532
01:13:49,940 --> 01:13:53,210
>> Ja, die kaart, die kleine stukjes
papier, want ik houd het beschrijven van hen.

1533
01:13:53,210 --> 01:13:55,650
Deze arrows-- dat zijn niet gratis.

1534
01:13:55,650 --> 01:13:57,660
Een computer-- je weet
wat een computer heeft.

1535
01:13:57,660 --> 01:13:58,790
Het heeft nullen en enen.

1536
01:13:58,790 --> 01:14:03,170
Wilt u een pijl of een vertegenwoordigen
kaart of een nummer, u wat geheugen nodig.

1537
01:14:03,170 --> 01:14:05,950
Dus de andere prijs die u
betalen voor een gelinkte lijst,

1538
01:14:05,950 --> 01:14:09,070
een gemeenschappelijke computer science
resource, is ook ruimte.

1539
01:14:09,070 --> 01:14:11,710
>> En inderdaad zo, zo vaak,
onder de afwegingen

1540
01:14:11,710 --> 01:14:15,580
in het ontwerpen van software engineering
systemen is de tijd en space--

1541
01:14:15,580 --> 01:14:18,596
twee van ingrediënten, twee
van uw meest kostbare ingrediënten.

1542
01:14:18,596 --> 01:14:21,220
Dit kost me meer tijd
want ik heb deze kaart te volgen,

1543
01:14:21,220 --> 01:14:25,730
maar het is ook kost me meer ruimte
want ik heb deze kaart in de buurt te houden.

1544
01:14:25,730 --> 01:14:28,730
Dus de hoop, zoals we hebben soort
besproken meer dan gisteren en vandaag,

1545
01:14:28,730 --> 01:14:31,720
is dat de voordelen
zal opwegen tegen de kosten.

1546
01:14:31,720 --> 01:14:33,870
>> Maar er is geen voor de hand liggende oplossing.

1547
01:14:33,870 --> 01:14:35,870
Misschien is het better--
a la quick and dirty,

1548
01:14:35,870 --> 01:14:38,660
als Kareem voorgesteld earlier--
om het geheugen te gooien naar het probleem.

1549
01:14:38,660 --> 01:14:42,520
Gewoon kopen meer geheugen, denken minder
hard over het oplossen van het probleem,

1550
01:14:42,520 --> 01:14:44,595
en lossen het op een eenvoudiger manier.

1551
01:14:44,595 --> 01:14:46,720
En inderdaad eerder, toen
spraken we over compromissen,

1552
01:14:46,720 --> 01:14:49,190
Het was niet ruimte
de computer en de tijd.

1553
01:14:49,190 --> 01:14:51,810
Het was ontwikkelaar tijd, die
is een andere bron.

1554
01:14:51,810 --> 01:14:54,829
>> Dus nogmaals, het is deze evenwichtsoefening
proberen om te beslissen welke van die dingen

1555
01:14:54,829 --> 01:14:55,870
bent u bereid te besteden?

1556
01:14:55,870 --> 01:14:57,380
Wat is de minst dure?

1557
01:14:57,380 --> 01:15:01,040
Die geeft betere resultaten?

1558
01:15:01,040 --> 01:15:01,540
Ja?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Inderdaad.

1561
01:15:12,580 --> 01:15:15,970
In dit geval, als je
die getallen in de maps--

1562
01:15:15,970 --> 01:15:18,820
deze worden genoemd in vele talen
"Pointers" of "adressen" -

1563
01:15:18,820 --> 01:15:20,390
het is het dubbele van de ruimte.

1564
01:15:20,390 --> 01:15:24,390
Dat hoeft niet zo slecht als dubbel zo zijn
op dit moment zijn we gewoon het opslaan van nummers.

1565
01:15:24,390 --> 01:15:27,410
Stel dat we het opslaan
patiëntendossiers in een hospital--

1566
01:15:27,410 --> 01:15:30,870
dus namen Pierson's, telefoonnummers,
sofi-nummers, arts

1567
01:15:30,870 --> 01:15:31,540
geschiedenis.

1568
01:15:31,540 --> 01:15:34,160
Deze doos kan veel,
veel groter, waarbij

1569
01:15:34,160 --> 01:15:38,000
een klein beetje wijzer, het adres van
de volgende element-- het is niet een big deal.

1570
01:15:38,000 --> 01:15:40,620
Het is zo'n pony
kost het maakt niet uit.

1571
01:15:40,620 --> 01:15:43,210
Maar in dit geval, ja, het is een verdubbeling.

1572
01:15:43,210 --> 01:15:45,290
Goede vraag.

1573
01:15:45,290 --> 01:15:47,900
>> Laten we praten over een tijd
beetje meer concreet.

1574
01:15:47,900 --> 01:15:50,380
Wat is de looptijd
van het zoeken in dit overzicht?

1575
01:15:50,380 --> 01:15:53,640
Stel dat ik wilde om te zoeken
door middel van alle kwaliteiten van de studenten,

1576
01:15:53,640 --> 01:15:55,980
en er is n kwaliteiten
in deze datastructuur.

1577
01:15:55,980 --> 01:15:58,830
Ook hier kunnen we lenen
de woordenschat van eerder.

1578
01:15:58,830 --> 01:16:00,890
Dit is een lineaire datastructuur.

1579
01:16:00,890 --> 01:16:04,570
>> Big O van n is wat er nodig is om te krijgen
aan het einde van deze gegevensstructuur,

1580
01:16:04,570 --> 01:16:08,410
whereas-- en we hebben niet gezien
Dit before-- een matrix geeft je

1581
01:16:08,410 --> 01:16:13,555
wat heet constante tijd, wat betekent dat
een stap of twee stappen of 10 steps--

1582
01:16:13,555 --> 01:16:14,180
maakt niet uit.

1583
01:16:14,180 --> 01:16:15,440
Het is een vast aantal.

1584
01:16:15,440 --> 01:16:17,440
Het heeft niets te maken met
de grootte van de matrix.

1585
01:16:17,440 --> 01:16:20,130
En de reden daarvoor,
opnieuw, is willekeurige toegang.

1586
01:16:20,130 --> 01:16:23,180
De computer kan gewoon meteen
springen naar een andere locatie,

1587
01:16:23,180 --> 01:16:27,770
want ze zijn allemaal hetzelfde
afstand van alles.

1588
01:16:27,770 --> 01:16:29,112
Er is geen denken bij betrokken.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Okee.

1591
01:16:32,400 --> 01:16:39,230
Dus als ik kan, laat me proberen te
verf laatste twee foto's.

1592
01:16:39,230 --> 01:16:42,830
Een veel voorkomende een bekend als een hash tabel.

1593
01:16:42,830 --> 01:16:51,120
Dus om deze discussie te motiveren,
laat me denken over hoe dit te doen.

1594
01:16:51,120 --> 01:16:52,610
>> Dus hoe zit dit?

1595
01:16:52,610 --> 01:16:55,160
Stel dat het probleem
we willen nu op te lossen

1596
01:16:55,160 --> 01:16:58,360
implementeert in een dictionary--
dus een hele hoop van het Engels woorden

1597
01:16:58,360 --> 01:16:59,330
of wat dan ook.

1598
01:16:59,330 --> 01:17:02,724
En het doel is om te kunnen beantwoorden
vragen van het formulier is dat een woord?

1599
01:17:02,724 --> 01:17:04,640
Dus u wilt implementeren
een spellingscontrole, net

1600
01:17:04,640 --> 01:17:07,220
als een fysieke woordenboek
dat je kunt dingen opzoeken in.

1601
01:17:07,220 --> 01:17:10,490
Stel dat ik dit doen met een array.

1602
01:17:10,490 --> 01:17:12,590
Ik zou dit te doen.

1603
01:17:12,590 --> 01:17:20,756
>> En stel dat de woorden zijn appel
en banaan en meloen.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
En ik kan niet denken van vruchten
die beginnen met d, dus we zijn gewoon

1606
01:17:26,465 --> 01:17:27,590
gaat drie vruchten hebben.

1607
01:17:27,590 --> 01:17:31,510
Dus dit is een array, en we zijn
opslaan van al deze woorden

1608
01:17:31,510 --> 01:17:34,200
in dit woordenboek als een matrix.

1609
01:17:34,200 --> 01:17:39,350
De vraag is dus hoe anders
zou je deze informatie op te slaan?

1610
01:17:39,350 --> 01:17:43,160
>> Nou, ik ben een beetje vals spelen hier, want
elk van deze letters in het woord

1611
01:17:43,160 --> 01:17:44,490
is echt een individuele byte.

1612
01:17:44,490 --> 01:17:46,740
Dus als ik echt wilde zijn
nit-kieskeurig, zou ik echt

1613
01:17:46,740 --> 01:17:49,600
te verdelen deze op in veel
kleinere delen van het geheugen,

1614
01:17:49,600 --> 01:17:51,289
en we konden precies dat te doen.

1615
01:17:51,289 --> 01:17:53,580
Maar we gaan tegenkomen
hetzelfde probleem als voorheen.

1616
01:17:53,580 --> 01:17:56,674
Wat als, zoals Merriam Webster of Oxford
doet elke jaar-- ze woorden toevoegen

1617
01:17:56,674 --> 01:17:59,340
de dictionary-- doen we niet
per se willen onszelf te schilderen

1618
01:17:59,340 --> 01:18:00,780
in een hoek met een serie?

1619
01:18:00,780 --> 01:18:05,710
>> Dus in plaats daarvan, misschien een slimmere aanpak
is om appel in haar eigen knoop of doos,

1620
01:18:05,710 --> 01:18:11,190
zoals wij zouden zeggen, banaan, en
dan is hier hebben we cantaloupe.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
En we touwtje deze dingen samen.

1623
01:18:16,790 --> 01:18:19,980
Dus dit is de matrix en
Dit is het gelinkte lijst.

1624
01:18:19,980 --> 01:18:23,300
Als je niet helemaal kunt zien, het is gewoon
zegt "array", en dit zegt "lijst."

1625
01:18:23,300 --> 01:18:25,780
>> Dus we hebben dezelfde
exact kwesties als voorheen,

1626
01:18:25,780 --> 01:18:28,600
waardoor we nu
dynamiek in onze gelinkte lijst.

1627
01:18:28,600 --> 01:18:31,090
Maar we hebben een vrij traag woordenboek.

1628
01:18:31,090 --> 01:18:32,870
Stel dat ik wil een woord opzoeken.

1629
01:18:32,870 --> 01:18:35,430
Het zou me grote O n
stappen, omdat het woord misschien

1630
01:18:35,430 --> 01:18:37,840
zijn helemaal aan het eind
de lijst, zoals meloen.

1631
01:18:37,840 --> 01:18:40,600
En het blijkt dat
in de programmering, sorteren

1632
01:18:40,600 --> 01:18:42,700
van de heilige graal van data
structuren, is iets

1633
01:18:42,700 --> 01:18:46,620
dat geeft je een constante
tijd als een array

1634
01:18:46,620 --> 01:18:50,870
maar dat geeft je nog steeds dynamiek.

1635
01:18:50,870 --> 01:18:52,940
>> Zo kunnen we het beste van beide werelden?

1636
01:18:52,940 --> 01:18:55,570
En inderdaad, er is iets
genaamd de hash table

1637
01:18:55,570 --> 01:18:59,320
die u toelaat om precies te doen
dat zij bij benadering.

1638
01:18:59,320 --> 01:19:03,140
Een hash tabel is een liefhebber
gegevensstructuur die we

1639
01:19:03,140 --> 01:19:06,340
maar kunt bedenken als het
combinatie van een array--

1640
01:19:06,340 --> 01:19:12,390
en ik ga om het te tekenen
zoals dit-- en gelinkte lijsten

1641
01:19:12,390 --> 01:19:17,310
dat ik zal trekken als dit hier.

1642
01:19:17,310 --> 01:19:19,760
>> En de manier waarop deze zaak
werkt als volgt.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Als dit now-- hash table--
is mijn derde datastructuur,

1645
01:19:29,540 --> 01:19:32,590
en ik wil op te slaan
woorden in deze, dat doe ik niet

1646
01:19:32,590 --> 01:19:35,440
willen gewoon allemaal van de winkel
woorden rug aan rug aan rug aan rug.

1647
01:19:35,440 --> 01:19:37,430
Ik wil een hefboomeffect
wat informatie

1648
01:19:37,430 --> 01:19:40,330
over de woorden die zal laten
me get it waar het sneller.

1649
01:19:40,330 --> 01:19:43,666
>> Dus gezien de woorden apple
en banaan en meloen,

1650
01:19:43,666 --> 01:19:45,040
Ik koos bewust voor die woorden.

1651
01:19:45,040 --> 01:19:45,340
Waarom?

1652
01:19:45,340 --> 01:19:47,631
Wat is een soort van fundamenteel
anders over de drie?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Wat is de voor de hand liggende?

1655
01:19:51,484 --> 01:19:52,900
Ze beginnen met verschillende letters.

1656
01:19:52,900 --> 01:19:53,900
>> Dus weet je wat?

1657
01:19:53,900 --> 01:19:57,120
In plaats van al mijn woorden in
dezelfde emmer, om zo te zeggen,

1658
01:19:57,120 --> 01:20:00,390
net als in een grote lijst, waarom niet
Ik op zijn minst proberen een optimalisatie

1659
01:20:00,390 --> 01:20:04,180
en mijn lijsten 26/01 zo lang te maken.

1660
01:20:04,180 --> 01:20:07,440
Een meeslepend optimalisatie
misschien waarom niet

1661
01:20:07,440 --> 01:20:10,650
Ik-- bij het plaatsen van een woord
in deze gegevensstructuur,

1662
01:20:10,650 --> 01:20:14,300
in het geheugen van de computer, waarom
weet ik niet al de 'a' woorden hier,

1663
01:20:14,300 --> 01:20:17,270
alle 'b' woorden hier
en alle 'c' woorden hier?

1664
01:20:17,270 --> 01:20:24,610
Zo eindigt deze putting een appel
hier, hier banaan, meloen hier,

1665
01:20:24,610 --> 01:20:25,730
enzovoorts.

1666
01:20:25,730 --> 01:20:31,700
>> En als ik een extra
woord like-- wat is een ander?

1667
01:20:31,700 --> 01:20:36,640
Appel, banaan, peer.

1668
01:20:36,640 --> 01:20:39,370
Iedereen denken van een vrucht
die begint met een a, b of c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- perfect.

1670
01:20:40,570 --> 01:20:43,990
Dat gaat uiteindelijk hier.

1671
01:20:43,990 --> 01:20:47,530
En dus lijken we een hebben
marginaal betere oplossing,

1672
01:20:47,530 --> 01:20:50,820
want nu als ik wil
om te zoeken naar apple, I

1673
01:20:50,820 --> 01:20:53,200
first-- ik niet alleen duik
in mijn datastructuur.

1674
01:20:53,200 --> 01:20:54,850
Ik weet niet duik in het geheugen van mijn computer.

1675
01:20:54,850 --> 01:20:56,530
Ik kijk eerst naar de eerste letter.

1676
01:20:56,530 --> 01:20:58,610
>> En dit is wat een computer
wetenschapper zou zeggen.

1677
01:20:58,610 --> 01:21:00,760
Je hash in uw datastructuur.

1678
01:21:00,760 --> 01:21:04,100
Je neemt je input, die in
dit geval is een woord als appel.

1679
01:21:04,100 --> 01:21:07,150
Je analyseert het, kijkend naar
de eerste letter in casu

1680
01:21:07,150 --> 01:21:08,340
waardoor hash is.

1681
01:21:08,340 --> 01:21:10,950
Hashing is een algemene term waarbij
je iets als input nemen

1682
01:21:10,950 --> 01:21:12,116
en produceer je wat output.

1683
01:21:12,116 --> 01:21:15,090
En de output van die
geval is de locatie

1684
01:21:15,090 --> 01:21:18,150
u wilt zoeken, de eerste
locatie, de tweede plaats, de derde plaats.

1685
01:21:18,150 --> 01:21:22,160
Zodat de ingang appel,
de eerste uitgang.

1686
01:21:22,160 --> 01:21:25,054
De ingang is banaan, de
output moet seconde.

1687
01:21:25,054 --> 01:21:27,220
De ingang is cantaloupe,
de productie moet derde zijn.

1688
01:21:27,220 --> 01:21:30,320
De ingang is bosbessen, de
output moet weer tweede.

1689
01:21:30,320 --> 01:21:34,010
En dat is wat helpt u mee
shortcuts door je geheugen

1690
01:21:34,010 --> 01:21:39,050
om woorden te krijgen
of gegevens efficiënter te maken.

1691
01:21:39,050 --> 01:21:43,330
>> Nu snijdt deze naar beneden onze tijd mogelijk
zelfs met een op de 26,

1692
01:21:43,330 --> 01:21:45,850
want als je ervan uitgaat dat je
zo veel "a" woorden als "z"

1693
01:21:45,850 --> 01:21:48,080
woorden als "q" woorden, die
is niet echt realistic--

1694
01:21:48,080 --> 01:21:50,830
je gaat scheef over hebben
bepaalde letters van het alphabet--

1695
01:21:50,830 --> 01:21:53,204
maar dit zou een incrementele
aanpak die toelaat

1696
01:21:53,204 --> 01:21:55,930
je veel sneller om woorden te krijgen.

1697
01:21:55,930 --> 01:21:59,660
En in werkelijkheid een verfijnd
programma de Googles van de wereld,

1698
01:21:59,660 --> 01:22:02,180
de Facebooks van de wereld--
ze zouden een hash-tabel gebruiken

1699
01:22:02,180 --> 01:22:03,740
voor veel verschillende doeleinden.

1700
01:22:03,740 --> 01:22:06,590
Maar zij zouden niet zo naïef zijn
gewoon kijken naar de eerste letter

1701
01:22:06,590 --> 01:22:09,700
in appel of banaan of
peer of meloen,

1702
01:22:09,700 --> 01:22:13,420
want zoals u deze kunt zien
lijsten kon nog steeds lang.

1703
01:22:13,420 --> 01:22:17,130
>> En dus dit kan nog steeds soort zijn
van linear-- dus een soort van trage,

1704
01:22:17,130 --> 01:22:19,980
zoals bij de grote O n
dat we eerder besproken.

1705
01:22:19,980 --> 01:22:25,290
Dus wat een echte goede hash tafel zal
doen-- het zal een veel grotere array.

1706
01:22:25,290 --> 01:22:28,574
En het zal een veel gebruikt
verfijnde hashing-functie,

1707
01:22:28,574 --> 01:22:30,240
zodat het niet alleen kijken naar de "a."

1708
01:22:30,240 --> 01:22:35,480
Misschien kijkt naar "a-p-p-l-e" en
een of andere manier zet die vijf letters

1709
01:22:35,480 --> 01:22:38,400
in de plaats waar
appel moeten worden opgeslagen.

1710
01:22:38,400 --> 01:22:42,660
We zijn gewoon naïef met de letter 'a'
alleen, want het is leuk en eenvoudig.

1711
01:22:42,660 --> 01:22:44,600
>> Maar een hash-tabel, in
het einde, kunt u denkt

1712
01:22:44,600 --> 01:22:47,270
of als een combinatie van
een matrix, die elk

1713
01:22:47,270 --> 01:22:51,700
heeft een gekoppelde lijst die idealiter
moet zo kort mogelijk zijn.

1714
01:22:51,700 --> 01:22:54,364
En dit is niet voor de hand.

1715
01:22:54,364 --> 01:22:57,280
In feite, veel van de fijnafstemming
dat gaat onder de kap als

1716
01:22:57,280 --> 01:22:59,654
de uitvoering van dit soort
geavanceerde data structuren

1717
01:22:59,654 --> 01:23:01,640
is wat de juiste
lengte van de array?

1718
01:23:01,640 --> 01:23:03,250
Wat is de juiste hash-functie?

1719
01:23:03,250 --> 01:23:04,830
Hoe doe je opslaan dingen in het geheugen?

1720
01:23:04,830 --> 01:23:07,249
>> Maar beseffen hoe snel
dit soort discussie

1721
01:23:07,249 --> 01:23:10,540
escaleerde, ofwel zo ver dat het is een soort
van boven het hoofd op dit punt, die

1722
01:23:10,540 --> 01:23:11,360
is prima.

1723
01:23:11,360 --> 01:23:18,820
Maar we begonnen, rappel, met werkelijk
iets low-level en elektronisch.

1724
01:23:18,820 --> 01:23:20,819
En dus dit is ook dit
thema van de abstractie,

1725
01:23:20,819 --> 01:23:23,610
waar eens je begint te nemen voor
verleend, OK, ik heb het-- heb er

1726
01:23:23,610 --> 01:23:26,680
fysiek geheugen, OK, kreeg het, elke
fysieke locatie heeft een adres,

1727
01:23:26,680 --> 01:23:29,910
OK, ik heb het, kan ik vertegenwoordig
deze adressen als arrows--

1728
01:23:29,910 --> 01:23:34,650
kun je heel snel aan de slag te hebben
verfijndere gesprekken die

1729
01:23:34,650 --> 01:23:38,360
in het einde lijkt ons te worden zodat
om problemen zoals het zoeken op te lossen

1730
01:23:38,360 --> 01:23:41,620
en sorteren efficiënter te maken.

1731
01:23:41,620 --> 01:23:44,190
En wees gerust, too--
omdat ik denk dat dit

1732
01:23:44,190 --> 01:23:48,700
is de diepste we gegaan in een aantal
Deze CS onderwerpen proper-- we hebben

1733
01:23:48,700 --> 01:23:51,880
in één dag en een half in dit
punt wat je zou normaal meer dan doen

1734
01:23:51,880 --> 01:23:55,520
de loop van acht weken in een semester.

1735
01:23:55,520 --> 01:23:59,670
>> Heeft u vragen over deze?

1736
01:23:59,670 --> 01:24:01,100
Nee?

1737
01:24:01,100 --> 01:24:01,940
Okee.

1738
01:24:01,940 --> 01:24:05,610
Nou, waarom niet we daar te pauzeren,
starten lunch een paar minuten te vroeg,

1739
01:24:05,610 --> 01:24:07,052
hervatten in slechts ongeveer een uur?

1740
01:24:07,052 --> 01:24:08,760
En ik zal blijven hangen
een beetje met vragen.

1741
01:24:08,760 --> 01:24:11,343
Dan ga ik moeten gaan
neem een ​​paar oproepen als dat is OK.

1742
01:24:11,343 --> 01:24:15,000
Ik zet wat muziek in de tussentijd,
maar de lunch moet rond de hoek.

1743
01:24:15,000 --> 01:24:17,862