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

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Okay.

3
00:00:00,460 --> 00:00:01,094
Vi er tilbage.

4
00:00:01,094 --> 00:00:04,260
Så i dette segment om programmering, hvad
Jeg troede, vi ville gøre, er en blanding af ting.

5
00:00:04,260 --> 00:00:06,340
One, gøre en lille smule
af noget hands-on,

6
00:00:06,340 --> 00:00:08,690
omend bruge en mere legende
programmering environment--

7
00:00:08,690 --> 00:00:11,620
en, der er demonstrative af
præcis den slags ideer

8
00:00:11,620 --> 00:00:14,220
Vi har talt om,
men lidt mere formelt.

9
00:00:14,220 --> 00:00:18,200
To, ser på nogle af
de mere tekniske måder

10
00:00:18,200 --> 00:00:21,520
at en programmør faktisk ville løse
problemer som den søgende problem

11
00:00:21,520 --> 00:00:24,530
at vi kiggede på før og
også en mere grundlæggende

12
00:00:24,530 --> 00:00:26,020
interessant problem sortering.

13
00:00:26,020 --> 00:00:28,840
>> Vi har lige antaget fra Hent gå
at der telefonbog blev sorteret,

14
00:00:28,840 --> 00:00:31,980
men det alene er faktisk slags en
hård problem med mange forskellige måder

15
00:00:31,980 --> 00:00:32,479
at løse det.

16
00:00:32,479 --> 00:00:34,366
Så vi vil bruge disse som
en klasse af problemer

17
00:00:34,366 --> 00:00:36,740
repræsentant for ting,
kan løses generelt.

18
00:00:36,740 --> 00:00:38,980
Og så vil vi tale
om i nogle detaljer, hvad

19
00:00:38,980 --> 00:00:42,360
kaldes data structures--
amatør måder som hægtede lister

20
00:00:42,360 --> 00:00:46,290
og hash tabeller og træer,
en programmør ville faktisk

21
00:00:46,290 --> 00:00:48,890
bruge og generelt bruge
på en tavle til at male

22
00:00:48,890 --> 00:00:51,840
et billede af, hvad han eller hun
forestiller sig for at gennemføre

23
00:00:51,840 --> 00:00:52,980
nogle stykke software.

24
00:00:52,980 --> 00:00:55,130
>> Så lad os gøre det hands-on del først.

25
00:00:55,130 --> 00:01:00,090
Så bare få dine hænder beskidte med en
miljø kaldet scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Dette er et værktøj, vi bruger
i vores bachelor klasse.

27
00:01:02,636 --> 00:01:04,510
Selvom det er designet
for aldre 12 og op,

28
00:01:04,510 --> 00:01:07,570
vi bruge det til op
del af denne ganske lidt

29
00:01:07,570 --> 00:01:10,020
da det er en dejlig, sjov
grafisk måde at lære på

30
00:01:10,020 --> 00:01:12,160
lidt noget om programmering.

31
00:01:12,160 --> 00:01:17,600
Så hovedet til denne webadresse, hvor du
bør se en side helt som denne,

32
00:01:17,600 --> 00:01:23,330
og gå videre og klik
Deltag Scratch øverst til højre

33
00:01:23,330 --> 00:01:28,300
og vælge et brugernavn og en
adgangskode og i sidste ende få dig

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

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

36
00:01:32,165 --> 00:01:34,665
Jeg troede, jeg ville bruge dette som en
mulighed første til at vise dette.

37
00:01:34,665 --> 00:01:39,120
Et spørgsmål kom op i pausen
om, hvad koden ser faktisk gerne.

38
00:01:39,120 --> 00:01:41,315
Og vi talte
i pausen om C,

39
00:01:41,315 --> 00:01:45,060
i particular-- især en
lavere niveau i en ældre sprog.

40
00:01:45,060 --> 00:01:47,750
Og jeg gjorde bare en hurtig
Google-søgning for at finde C-kode

41
00:01:47,750 --> 00:01:51,574
for binær søgning, den algoritme, vi
bruges til at søge at telefonbogen tidligere.

42
00:01:51,574 --> 00:01:54,240
Denne særlige eksempel, selvfølgelig,
søger ikke en telefonbog.

43
00:01:54,240 --> 00:01:57,840
Det bare søger en hel masse
numre i computerens hukommelse.

44
00:01:57,840 --> 00:02:01,000
Men hvis du gerne vil bare få en visuel
fornemmelse af, hvad en egentlig programmering

45
00:02:01,000 --> 00:02:05,370
sprog ligner, det ser
lidt noget som dette.

46
00:02:05,370 --> 00:02:09,759
Så det er omkring 20-plus,
30 eller deromkring linjer kode,

47
00:02:09,759 --> 00:02:12,640
men samtalen vi
havde løbet pause

48
00:02:12,640 --> 00:02:16,000
handlede om, hvordan det rent faktisk
bliver forvandlet til nuller og ettaller

49
00:02:16,000 --> 00:02:19,200
og hvis du ikke bare kan vende det
behandle og gå fra nuller og ettaller

50
00:02:19,200 --> 00:02:20,210
tilbage til kode.

51
00:02:20,210 --> 00:02:22,620
>> Desværre er processen
er så transformative

52
00:02:22,620 --> 00:02:24,890
at det er meget lettere sagt end gjort.

53
00:02:24,890 --> 00:02:29,400
Jeg gik videre og faktisk viste
dette program, binær søgning,

54
00:02:29,400 --> 00:02:32,700
ind nuller og ettaller i form af en
program kaldet The Compiler, at jeg

55
00:02:32,700 --> 00:02:34,400
tilfældigvis har her lige på min Mac.

56
00:02:34,400 --> 00:02:37,850
Og hvis man ser på skærmen
her, der fokuserer specifikt

57
00:02:37,850 --> 00:02:43,520
på disse midterste seks kolonner kun,
vil du kun se nuller og ettaller.

58
00:02:43,520 --> 00:02:48,290
Og det er de nuller og ettaller, der
komponere præcis det søgende program.

59
00:02:48,290 --> 00:02:53,720
>> Og så hver bid af fem bit,
hver byte af nuller og ettaller her,

60
00:02:53,720 --> 00:02:57,310
repræsenterer nogle instruktion
typisk indersiden af ​​en computer.

61
00:02:57,310 --> 00:03:00,730
Og i virkeligheden, hvis du har hørt
markedsføring slogan "Intel inside" - det,

62
00:03:00,730 --> 00:03:04,610
selvfølgelig betyder bare du har en
Intel CPU eller hjerne inde i computeren.

63
00:03:04,610 --> 00:03:08,000
Og hvad det betyder at være en CPU er
at du har en instruktionssæt,

64
00:03:08,000 --> 00:03:08,840
så at sige.

65
00:03:08,840 --> 00:03:11,620
>> Hver CPU i verden, mange af
dem lavet af Intel i disse dage,

66
00:03:11,620 --> 00:03:13,690
forstår et endeligt
antal instruktioner.

67
00:03:13,690 --> 00:03:18,690
Og disse instrukser er så lavt niveau
som tilføje disse to tal sammen,

68
00:03:18,690 --> 00:03:22,560
formere disse to tal sammen,
flytte dette stykke data herfra

69
00:03:22,560 --> 00:03:27,340
til her i hukommelsen, gem denne
information herfra til her i hukommelsen,

70
00:03:27,340 --> 00:03:32,200
og så forth-- så meget, meget
lavt niveau, næsten elektroniske detaljer.

71
00:03:32,200 --> 00:03:34,780
Men med de matematiske
operationer koblede

72
00:03:34,780 --> 00:03:37,410
med det, vi diskuterede tidligere,
repræsentationen af ​​data

73
00:03:37,410 --> 00:03:40,450
som nuller og ettaller, kan
du opbygger alt

74
00:03:40,450 --> 00:03:44,180
at en computer kan gøre i dag, hvad enten
det tekstuelle, grafisk, musical,

75
00:03:44,180 --> 00:03:45,580
for ellers.

76
00:03:45,580 --> 00:03:49,450
>> Så det er meget let at komme
tabt i ukrudt af hurtigt.

77
00:03:49,450 --> 00:03:52,150
Og der er en masse
syntaktiske udfordringer

78
00:03:52,150 --> 00:03:56,630
hvorved hvis du laver den enkleste,
dummeste af stavefejl ingen af ​​programmet

79
00:03:56,630 --> 00:03:57,860
vil arbejde for eksklusionen.

80
00:03:57,860 --> 00:04:00,366
Og så i stedet for at bruge en
sprog som C i morges,

81
00:04:00,366 --> 00:04:02,240
Jeg troede det ville være
sjovere at rent faktisk at gøre

82
00:04:02,240 --> 00:04:04,840
noget mere visuel, hvilket
mens designet til børn

83
00:04:04,840 --> 00:04:08,079
er faktisk en perfekt manifestation
af en egentlig programmering

84
00:04:08,079 --> 00:04:10,370
language-- bare sker for at
bruge billeder i stedet for tekst

85
00:04:10,370 --> 00:04:11,710
at repræsentere disse idéer.

86
00:04:11,710 --> 00:04:15,470
>> Så når du rent faktisk har en
konto på scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
Klik på knappen Opret
øverst til venstre på sitet.

88
00:04:21,070 --> 00:04:24,620
Og du skal se et miljø som
den jeg er ved at se på min skærm

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

90
00:04:26,310 --> 00:04:29,350
Og vi vil bruge bare en lille smule
lidt tid at spille her.

91
00:04:29,350 --> 00:04:34,080
Lad os se, om vi ikke alle kan løse nogle
problemer sammen på følgende måde.

92
00:04:34,080 --> 00:04:39,420
>> Så hvad du vil se i denne
environment-- og faktisk bare lade

93
00:04:39,420 --> 00:04:40,050
mig pause.

94
00:04:40,050 --> 00:04:42,680
Er der nogen der ikke her?

95
00:04:42,680 --> 00:04:45,070
Ikke her?

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

97
00:04:45,800 --> 00:04:49,030
Så lad mig påpege et par
karakteristika dette miljø.

98
00:04:49,030 --> 00:04:55,024
>> Så øverst til venstre på skærmen, vi
har Scratch etape, så at sige.

99
00:04:55,024 --> 00:04:57,440
Scratch er ikke kun navnet
af dette programmeringssprog;

100
00:04:57,440 --> 00:05:00,356
det er også navnet på den kat, der
du ser som standard der i orange.

101
00:05:00,356 --> 00:05:02,160
Han er på en scene, så
meget gerne jeg beskrev

102
00:05:02,160 --> 00:05:05,770
skildpadden tidligere som værende i en
rektangulære whiteboard miljø.

103
00:05:05,770 --> 00:05:09,800
Denne kattens verden er begrænset udelukkende
til dette rektangel op toppen er der.

104
00:05:09,800 --> 00:05:12,210
>> I mellemtiden, til højre
side her, det er

105
00:05:12,210 --> 00:05:15,610
bare et scripts område, en
blank tavle, hvis du vil.

106
00:05:15,610 --> 00:05:18,590
Det er her, vi kommer til at skrive
vores programmer på blot et øjeblik.

107
00:05:18,590 --> 00:05:22,935
Og de byggesten, at vi
bruge til at skrive dette program-- puslespillet

108
00:05:22,935 --> 00:05:25,310
stykker, hvis du will-- er
dem lige her i midten,

109
00:05:25,310 --> 00:05:27,500
og de er kategoriseret
via funktion.

110
00:05:27,500 --> 00:05:31,000
Så, for eksempel, vil jeg gå videre
og demonstrere mindst en af ​​disse.

111
00:05:31,000 --> 00:05:33,690
Jeg har tænkt mig at gå videre og klik
Kontrol kategori op øverst.

112
00:05:33,690 --> 00:05:35,720
>> Så det er disse kategorier op toppen.

113
00:05:35,720 --> 00:05:39,410
Jeg har tænkt mig at klikke Control kategori.

114
00:05:39,410 --> 00:05:44,020
Snarere, jeg har tænkt mig at klikke på Begivenheder
kategorien allerførste op øverst.

115
00:05:44,020 --> 00:05:47,790
Og hvis du gerne vil følge med selv
som vi gør dette, er du helt velkommen til.

116
00:05:47,790 --> 00:05:52,180
Jeg har tænkt mig at klikke og trække dette
første, ", når grønne flag klikkes."

117
00:05:52,180 --> 00:05:58,410
Og så jeg har tænkt mig at slippe det bare
nogenlunde på toppen af ​​mine tomme tavler.

118
00:05:58,410 --> 00:06:01,450
>> Og hvad er rart om Scratch
er, at denne brik, når

119
00:06:01,450 --> 00:06:04,560
sammenlåst med andre puslespil
stykker, kommer til at gøre bogstaveligt

120
00:06:04,560 --> 00:06:06,460
hvad disse puslespilsbrikker sige at gøre.

121
00:06:06,460 --> 00:06:09,710
Så, for eksempel, Scratch er ret
nu i midten af ​​hans verden.

122
00:06:09,710 --> 00:06:14,660
Jeg har tænkt mig at gå videre og vælge
nu, lad os sige, Motion kategori,

123
00:06:14,660 --> 00:06:18,000
hvis du gerne vil gøre det
same-- Motion kategori.

124
00:06:18,000 --> 00:06:20,430
Og nu opdager jeg har en hel
bundt af puslespilsbrikker her

125
00:06:20,430 --> 00:06:23,370
at, igen, slags gør, hvad de siger.

126
00:06:23,370 --> 00:06:28,110
Og jeg har tænkt mig at gå videre og trække og
drop farten blokken lige herovre.

127
00:06:28,110 --> 00:06:31,860
>> Og se, at så snart du får
tæt på bunden af ​​den "grønne flag

128
00:06:31,860 --> 00:06:34,580
klikkede "knappen, varsel
hvordan en hvid streg,

129
00:06:34,580 --> 00:06:36,950
som om det er næsten
magnetisk, det ønsker at gå der.

130
00:06:36,950 --> 00:06:43,070
Bare lad gå, og det vil snap
sammen og formerne vil matche.

131
00:06:43,070 --> 00:06:46,620
Og nu kan du måske næsten
gætte, hvor vi skal hen med dette.

132
00:06:46,620 --> 00:06:51,570
>> Hvis man ser på Scratch stadium
herover og se til toppen af ​​det,

133
00:06:51,570 --> 00:06:55,142
vil du se et rødt lys, en
stoppe tegn, og et grønt flag.

134
00:06:55,142 --> 00:06:57,100
Og jeg har tænkt mig at gå videre
og se mine screen--

135
00:06:57,100 --> 00:06:58,460
for et øjeblik, hvis du kunne.

136
00:06:58,460 --> 00:07:01,960
Jeg har tænkt mig at klikke på
grønt flag lige nu,

137
00:07:01,960 --> 00:07:07,850
og han flyttede, hvad der synes at være 10 trin
eller 10 pixels, 10 prikker, på skærmen.

138
00:07:07,850 --> 00:07:13,390
>> Og så ikke så spændende,
men lad mig foreslå

139
00:07:13,390 --> 00:07:17,440
uden selv at undervise dette, blot
ved hjælp af egen din egen intuition-- lad

140
00:07:17,440 --> 00:07:22,560
mig foreslå, at du finde ud af at
gøre Scratch gåtur lige ned fra scenen.

141
00:07:22,560 --> 00:07:28,700
Har ham gøre plads til den højre side af
skærmen, hele vejen til højre.

142
00:07:28,700 --> 00:07:32,200
Lad mig give dig et øjeblik
eller så at kæmpe med det.

143
00:07:32,200 --> 00:07:37,681
Du vil måske tage et kig
på andre kategorier af blokke.

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

145
00:07:38,180 --> 00:07:41,290
Så bare for at opsummere, når vi har
det grønne flag klikkede her

146
00:07:41,290 --> 00:07:44,850
og flytte 10 trin er
kun instruktion, hver gang jeg

147
00:07:44,850 --> 00:07:46,720
klikke på den grønne flag, hvad sker der?

148
00:07:46,720 --> 00:07:50,070
Nå, der kører mit program.

149
00:07:50,070 --> 00:07:52,450
Så jeg kunne gøre dette
måske 10 gange manuelt,

150
00:07:52,450 --> 00:07:55,130
men det føles lidt
bit hackish, så at sige,

151
00:07:55,130 --> 00:07:57,480
hvorved jeg er ikke rigtig
løse problemet.

152
00:07:57,480 --> 00:08:00,530
Jeg prøver bare igen og
igen og igen og igen

153
00:08:00,530 --> 00:08:03,180
indtil jeg slags uheld
opnå direktivet

154
00:08:03,180 --> 00:08:05,560
at jeg satte sig for at opnå tidligere.

155
00:08:05,560 --> 00:08:08,200
>> Men vi ved fra vores
pseudokode tidligere, at der er

156
00:08:08,200 --> 00:08:11,870
dette begreb i programmering af looping,
gør noget igen og igen.

157
00:08:11,870 --> 00:08:14,888
Og så jeg så, at en flok af jer
nået for, hvad puslespilsbrik?

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

159
00:08:17,870 --> 00:08:18,730
Gentag indtil.

160
00:08:18,730 --> 00:08:21,400
Så vi kunne gøre noget
ligesom gentag indtil.

161
00:08:21,400 --> 00:08:23,760
Og hvad gjorde du gentager indtil præcis?

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

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

164
00:08:28,540 --> 00:08:31,974
Og lad mig gå med en, der er
noget enklere for blot et øjeblik.

165
00:08:31,974 --> 00:08:33,140
Lad mig gå videre og gøre dette.

166
00:08:33,140 --> 00:08:35,559
Bemærk, at, som du kan have
opdaget under kontrol,

167
00:08:35,559 --> 00:08:38,409
der er denne gentagelse blok, som
ligner ikke det er så store.

168
00:08:38,409 --> 00:08:41,039
Der er ikke meget plads i
mellem disse to gule linjer.

169
00:08:41,039 --> 00:08:43,539
Men som nogle af jer måske har
bemærket, hvis du trækker og slipper,

170
00:08:43,539 --> 00:08:45,150
mærke til, hvordan den vokser til at fylde formen.

171
00:08:45,150 --> 00:08:46,274
>> Og du kan endda proppe mere.

172
00:08:46,274 --> 00:08:48,670
Det vil bare holde voksende, hvis
du trækker og svæve over det.

173
00:08:48,670 --> 00:08:51,110
Og jeg ved ikke, hvad der er
bedste her, så lad

174
00:08:51,110 --> 00:08:54,760
mig mindst gentages fem gange, for
eksempel og derefter gå tilbage til scenen

175
00:08:54,760 --> 00:08:56,720
og klik på den grønne flag.

176
00:08:56,720 --> 00:08:59,110
Og nu mærke til det er ikke helt der.

177
00:08:59,110 --> 00:09:02,400
>> Nu nogle af jer foreslog, som
Victoria vidste bare, gentag 10 gange.

178
00:09:02,400 --> 00:09:05,140
Og der generelt gør
få ham hele vejen,

179
00:09:05,140 --> 00:09:10,510
men ville der ikke være en mere robust
måde end vilkårligt regne ud

180
00:09:10,510 --> 00:09:12,640
hvor mange initiativer til at gøre?

181
00:09:12,640 --> 00:09:17,680
Hvad kan være en bedre blok
end gentag 10 gange være?

182
00:09:17,680 --> 00:09:20,380
>> Ja, så hvorfor ikke gøre noget for evigt?

183
00:09:20,380 --> 00:09:24,390
Og lad mig flytte denne brik
inde der og slippe af med denne ene.

184
00:09:24,390 --> 00:09:28,300
Bemærk nu, uanset hvor Scratch
starter, han går til kanten.

185
00:09:28,300 --> 00:09:30,700
Og heldigvis MIT,
der gør Scratch, bare

186
00:09:30,700 --> 00:09:33,190
sørger for, at han aldrig
forsvinder helt.

187
00:09:33,190 --> 00:09:35,360
Du kan altid få fat i halen.

188
00:09:35,360 --> 00:09:37,680
>> Og bare intuitivt,
hvorfor han holde bevægelse?

189
00:09:37,680 --> 00:09:38,892
Hvad sker der her?

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

191
00:09:41,440 --> 00:09:43,824
Han synes at være stoppet, men
så hvis jeg afhente og træk

192
00:09:43,824 --> 00:09:45,240
han holder ønsker at gå derovre.

193
00:09:45,240 --> 00:09:46,123
Hvorfor det?

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

195
00:09:51,610 --> 00:09:54,360
Sandelig, en computer er bogstaveligt talt
kommer til at gøre, hvad du fortæller det til at gøre.

196
00:09:54,360 --> 00:09:58,380
Så hvis du fortalte det tidligere gøre
Følgende ting for evigt, flytte 10 trin,

197
00:09:58,380 --> 00:10:01,860
det kommer til at holde i gang og gå
indtil jeg ramte den røde stopskilt

198
00:10:01,860 --> 00:10:04,620
og stoppe programmet helt.

199
00:10:04,620 --> 00:10:06,610
>> Så selvom du ikke gjorde
gøre dette, hvordan kunne jeg

200
00:10:06,610 --> 00:10:09,510
gøre Scratch flytte hurtigere
over skærmen?

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

202
00:10:12,060 --> 00:10:13,280
Flere trin, right?

203
00:10:13,280 --> 00:10:15,710
Så i stedet for at gøre 10
ad gangen, hvorfor vi ikke

204
00:10:15,710 --> 00:10:20,100
gå videre og ændre det at--
hvad ville du propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Så nu vil jeg til at klikke på den grønne
flag, og ja, han går rigtig hurtigt.

206
00:10:24,410 --> 00:10:27,180
>> Og det er selvfølgelig bare
en manifestation af animation.

207
00:10:27,180 --> 00:10:28,060
Hvad er animation?

208
00:10:28,060 --> 00:10:33,090
Det er bare at vise dig den menneskelige en
hel masse stillbilleder virkelig,

209
00:10:33,090 --> 00:10:34,160
virkelig, virkelig hurtig.

210
00:10:34,160 --> 00:10:36,500
Og så hvis vi bare at fortælle
ham til at flytte flere trin,

211
00:10:36,500 --> 00:10:39,750
vi bare have den virkning, være at
forandring, hvor han er på skærmen

212
00:10:39,750 --> 00:10:42,900
desto hurtigere per tidsenhed.

213
00:10:42,900 --> 00:10:46,454
>> Nu er den næste udfordring, som jeg foreslog
var at have ham hoppe ud over kanten.

214
00:10:46,454 --> 00:10:49,120
Og uden at vide hvad puslespil
stykker exist-- fordi det er fint

215
00:10:49,120 --> 00:10:53,030
hvis du ikke komme til
etape af challenge-- hvad

216
00:10:53,030 --> 00:10:54,280
vil du gøre intuitivt?

217
00:10:54,280 --> 00:10:58,030
Hvordan ville vi have ham hoppe tilbage og
frem, mellem venstre og højre?

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
Så vi har brug for en eller anden form
af tilstand, og vi

221
00:11:05,680 --> 00:11:09,710
synes at have betingede, så at
tale, under Control kategori.

222
00:11:09,710 --> 00:11:14,110
Hvilke af disse blokke
vi sikkert gerne?

223
00:11:14,110 --> 00:11:15,200
Ja, måske "hvis, da."

224
00:11:15,200 --> 00:11:18,780
Så bemærke, at blandt de gule blokke
vi har her, er der denne "hvis"

225
00:11:18,780 --> 00:11:23,920
eller denne "hvis ellers" blok, der vil
tillade os at træffe en beslutning til at gøre dette

226
00:11:23,920 --> 00:11:25,000
eller at gøre det.

227
00:11:25,000 --> 00:11:27,380
Og du kan endda reden dem
at gøre flere ting.

228
00:11:27,380 --> 00:11:34,910
Eller hvis du ikke har gået her endnu,
gå videre til Sensing kategori

229
00:11:34,910 --> 00:11:39,612
og-- lad os se om det er her.

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

231
00:11:43,050 --> 00:11:52,050
>> Så hvad blok kan være nyttige her
at opdage, hvis han er fra scenen?

232
00:11:52,050 --> 00:11:56,740
Ja, se, at nogle af disse blokke
kan parametriseret, så at sige.

233
00:11:56,740 --> 00:12:00,706
De kan slags tilpasset, ikke
modsætning HTML i går med attributter,

234
00:12:00,706 --> 00:12:03,330
hvor disse attributter slags
indstille opførslen af ​​et tag.

235
00:12:03,330 --> 00:12:08,880
Ligeledes her, kan jeg få fat i denne rørende
blok og forandring og stille spørgsmålet,

236
00:12:08,880 --> 00:12:11,500
er du rører musen
pointer som markøren

237
00:12:11,500 --> 00:12:13,250
eller er du rører kanten?

238
00:12:13,250 --> 00:12:15,210
>> Så lad mig gå ind og gøre det.

239
00:12:15,210 --> 00:12:18,130
Jeg har tænkt mig at zoome ud et øjeblik.

240
00:12:18,130 --> 00:12:21,320
Lad mig gribe denne brik
her, denne brik dette,

241
00:12:21,320 --> 00:12:24,570
og jeg har tænkt mig at virvar
dem op for et øjeblik.

242
00:12:24,570 --> 00:12:27,620
Jeg har tænkt mig at flytte denne,
ændre dette til rørende kant,

243
00:12:27,620 --> 00:12:38,590
og jeg har tænkt mig at bevægelse gøre dette.

244
00:12:38,590 --> 00:12:40,490
Så her er nogle ingredienser.

245
00:12:40,490 --> 00:12:42,570
Jeg tror, ​​jeg har fået alt, hvad jeg ønsker.

246
00:12:42,570 --> 00:12:47,710
>> Vil nogen gerne foreslå, hvordan jeg
kan forbinde disse måske top til bund

247
00:12:47,710 --> 00:12:52,020
for at løse problemet med
Scratch flytte højre til venstre til højre til

248
00:12:52,020 --> 00:12:57,020
venstre til højre til venstre, hver
tid bare hoppe ned fra væggen?

249
00:12:57,020 --> 00:12:58,050
Hvad ønsker jeg at gøre?

250
00:12:58,050 --> 00:13:01,097
Hvilken blok skal jeg oprette forbindelse til
"Når grønne flag klikkede først"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, så lad os starte med "evigt."

253
00:13:06,200 --> 00:13:07,170
Hvad går inde næste?

254
00:13:07,170 --> 00:13:10,290
En anden.

255
00:13:10,290 --> 00:13:11,850
OK, flytte trin.

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

257
00:13:12,350 --> 00:13:14,470
Hvad så?

258
00:13:14,470 --> 00:13:15,120
Så så hvis.

259
00:13:15,120 --> 00:13:17,720
Og mærke, selvom det ser
klemt sammen stramt,

260
00:13:17,720 --> 00:13:19,500
det vil bare vokse at udfylde.

261
00:13:19,500 --> 00:13:21,500
Det vil bare hoppe i, hvor jeg vil have det.

262
00:13:21,500 --> 00:13:25,920
>> Og hvad jeg sætte imellem
if og derefter?

263
00:13:25,920 --> 00:13:27,180
Sandsynligvis ", hvis røre kant."

264
00:13:27,180 --> 00:13:31,800
Og varsel, igen, det er for stort
for det, men det vil vokse til at udfylde.

265
00:13:31,800 --> 00:13:35,002
Og derefter dreje 15 grader?

266
00:13:35,002 --> 00:13:35,710
Hvor mange grader?

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

268
00:13:38,800 --> 00:13:41,196
Ja, så 180 vil spin
mig hele vejen rundt.

269
00:13:41,196 --> 00:13:42,570
Så lad os se om jeg fik denne ret.

270
00:13:42,570 --> 00:13:43,930
Lad mig zoome ud.

271
00:13:43,930 --> 00:13:45,130
>> Lad mig trække Scratch op.

272
00:13:45,130 --> 00:13:50,030
Så han er lidt forvrænget
nu, men det er fint.

273
00:13:50,030 --> 00:13:52,231
Hvordan kan jeg nulstille ham let?

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

275
00:13:59,879 --> 00:14:01,045
Jeg har tænkt mig at snyde lidt.

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

277
00:14:04,074 --> 00:14:05,990
Så jeg tilføje en anden
blok, bare for at være klar.

278
00:14:05,990 --> 00:14:08,424
Jeg vil have ham til punkt 90 grader
til højre som standard,

279
00:14:08,424 --> 00:14:10,840
så jeg bare at fortælle ham
at gøre det programmeringsmæssigt.

280
00:14:10,840 --> 00:14:11,632
Og her går vi.

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

282
00:14:14,740 --> 00:14:15,740
Vi synes at have gjort det.

283
00:14:15,740 --> 00:14:19,980
Det er lidt underligt, fordi
han gå op og ned.

284
00:14:19,980 --> 00:14:21,250
Lad os kalde det en fejl.

285
00:14:21,250 --> 00:14:22,120
Det er en fejl.

286
00:14:22,120 --> 00:14:27,320
En fejl er en fejl i et program, en
logisk fejl, at jeg, menneskelige, lavet.

287
00:14:27,320 --> 00:14:28,985
Hvorfor skal han på hovedet?

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

289
00:14:33,560 --> 00:14:35,250
Vidste MIT skrue op eller gjorde jeg?

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

291
00:14:38,840 --> 00:14:42,550
>> Ja, jeg mener, det er ikke MIT
fejl. De gav mig et puslespil brik

292
00:14:42,550 --> 00:14:44,970
der siger vende nogle antallet af grader.

293
00:14:44,970 --> 00:14:47,672
Og på Victoria forslag,
Jeg vender 180 grader,

294
00:14:47,672 --> 00:14:48,880
der er den rigtige intuition.

295
00:14:48,880 --> 00:14:53,700
Men dreje 180 grader bogstaveligt
betyder at dreje 180 grader,

296
00:14:53,700 --> 00:14:55,860
og det er ikke rigtig
hvad jeg vil, tilsyneladende.

297
00:14:55,860 --> 00:14:58,026
Fordi han i det mindste er i
dette todimensionale verden,

298
00:14:58,026 --> 00:15:00,740
så drejning der egentlig foregår
at vende ham på hovedet.

299
00:15:00,740 --> 00:15:04,030
>> Jeg vil sandsynligvis at bruge, hvad blok
stedet, baseret på, hvad du ser her?

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

301
00:15:11,890 --> 00:15:14,790
Hvordan kan vi løse dette?

302
00:15:14,790 --> 00:15:18,380
Ja, så vi kunne pege
i den modsatte retning.

303
00:15:18,380 --> 00:15:22,300
Og faktisk selv det er
ikke vil være nok,

304
00:15:22,300 --> 00:15:26,410
fordi vi kan kun hårdt kode
at pege til venstre eller højre.

305
00:15:26,410 --> 00:15:27,920
>> Du ved, hvad vi kunne gøre?

306
00:15:27,920 --> 00:15:30,160
Det ser ud til vi har en
bekvemmelighed blok her.

307
00:15:30,160 --> 00:15:32,987
Hvis jeg zoomer ind, se
noget vi kan lide her?

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

309
00:15:36,120 --> 00:15:40,020
Så det ser ud som MIT har en
abstraktion bygget i her.

310
00:15:40,020 --> 00:15:45,440
Denne blok synes at være ækvivalente
som andre blokke, pluralis?

311
00:15:45,440 --> 00:15:49,510
>> Denne ene blok synes at være ækvivalente
til hele denne trio af blokke

312
00:15:49,510 --> 00:15:50,880
at vi har her.

313
00:15:50,880 --> 00:15:54,670
Så det viser sig, kan jeg forenkle mit
program ved at slippe af alt dette

314
00:15:54,670 --> 00:15:58,270
og bare sætte dette i her.

315
00:15:58,270 --> 00:16:01,620
Og nu er han stadig lidt
buggy, og det er fint for nu.

316
00:16:01,620 --> 00:16:03,370
Vi vil overlade være.

317
00:16:03,370 --> 00:16:06,000
Men mit program er endnu
enklere, og også dette

318
00:16:06,000 --> 00:16:09,060
ville være repræsentativ
af et mål i programming--

319
00:16:09,060 --> 00:16:13,430
er at ideelt set gøre din kode som
enkel, så kompakt som muligt,

320
00:16:13,430 --> 00:16:15,650
mens den stadig er som
læsbare som muligt.

321
00:16:15,650 --> 00:16:20,310
Du ønsker ikke at gøre det så kortfattet
at det er svært at forstå.

322
00:16:20,310 --> 00:16:22,826
>> Men bemærk jeg har erstattet
tre blokke med en,

323
00:16:22,826 --> 00:16:24,200
og det er velsagtens en god ting.

324
00:16:24,200 --> 00:16:27,280
Jeg har indvindes væk begrebet
kontrollere, om du er

325
00:16:27,280 --> 00:16:29,120
på kanten med kun en blok.

326
00:16:29,120 --> 00:16:31,520
Nu kan vi have det sjovt med dette, faktisk.

327
00:16:31,520 --> 00:16:35,790
Dette tilføjer ikke så meget
intellektuel værdi, men legende værdi.

328
00:16:35,790 --> 00:16:39,730
Jeg har tænkt mig at gå videre
og få fat i denne lyd her.

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

330
00:16:42,900 --> 00:16:46,420
Så lad mig gå videre, og lad mig
stoppe programmet et øjeblik.

331
00:16:46,420 --> 00:16:52,070
Jeg har tænkt mig at optage det følgende,
giver adgang til min mikrofon.

332
00:16:52,070 --> 00:16:53,181
>> Nu sker det.

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

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

335
00:16:58,710 --> 00:17:01,140
Lad os prøve det igen.

336
00:17:01,140 --> 00:17:02,279
Nu sker det.

337
00:17:02,279 --> 00:17:03,570
OK, indspillede jeg den forkerte ting.

338
00:17:03,570 --> 00:17:04,580
Nu sker det.

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

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

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

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

343
00:17:09,300 --> 00:17:10,791
Nu behøver jeg at slippe af med den.

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

345
00:17:11,290 --> 00:17:13,950
>> Så nu har jeg en
registrering af blot "Av."

346
00:17:13,950 --> 00:17:18,040
Så nu vil jeg gå
videre og kalder det "Ouch."

347
00:17:18,040 --> 00:17:20,270
Jeg har tænkt mig at gå tilbage
til mine scripts, og nu

348
00:17:20,270 --> 00:17:25,460
varsel er der denne blok, der hedder
spille lyd "meow" eller afspille lyd "Ouch."

349
00:17:25,460 --> 00:17:28,920
Jeg har tænkt mig at trække det, og hvor
skal jeg sætte det for komisk effekt?

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

351
00:17:31,740 --> 00:17:37,860
Ja, så nu er det sådan
buggy, for nu dette block--

352
00:17:37,860 --> 00:17:42,050
mærke til, hvordan denne "hvis på kanten,
bounce "er en slags selvstændig.

353
00:17:42,050 --> 00:17:43,704
Så jeg har brug for at løse dette.

354
00:17:43,704 --> 00:17:44,870
Lad mig gå videre og gøre dette.

355
00:17:44,870 --> 00:17:48,630
Lad mig slippe af med denne og gå tilbage
til vores oprindelige, mere bevidst

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

357
00:17:49,870 --> 00:18:01,080
Så "Hvis røre kant, derefter" jeg vil
at vende, da Victoria foreslog,

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

359
00:18:02,480 --> 00:18:05,497
Og jeg ønsker at spille
lyden "av" der?

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

361
00:18:11,800 --> 00:18:15,580
>> Ja, mærke det er uden
den gule blok.

362
00:18:15,580 --> 00:18:17,680
Så også dette ville være en
bug, men jeg har bemærket det.

363
00:18:17,680 --> 00:18:21,290
Så jeg har tænkt mig at trække det op her,
og bekendtgørelse nu er det inde i "hvis".

364
00:18:21,290 --> 00:18:24,250
Så "hvis" er den slags
ligesom arm-lignende-blot

365
00:18:24,250 --> 00:18:26,260
der er kun kommer til at
gøre, hvad der er inde i den.

366
00:18:26,260 --> 00:18:30,216
Så nu, hvis jeg zoome ud på
risikoen for annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Av, av, av.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: Og det
vil bare blive ved for evigt.

370
00:18:39,910 --> 00:18:44,160
Nu bare for at fremskynde tingene
her, lad mig gå videre og åbne op,

371
00:18:44,160 --> 00:18:50,460
lad os say-- lade mig gå til nogle
af mine egne ting fra klassen.

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

373
00:18:53,000 --> 00:19:00,220
Og lad mig åbne op, lad os sige, dette
en lavet af en af ​​vores undervisning stipendiater

374
00:19:00,220 --> 00:19:01,500
et par år siden.

375
00:19:01,500 --> 00:19:04,732
Så nogle af jer måske husker
dette spil fra gårsdagens,

376
00:19:04,732 --> 00:19:05,940
og det er faktisk bemærkelsesværdigt.

377
00:19:05,940 --> 00:19:08,190
Selvom vi har gjort det
enkleste af programmer lige nu,

378
00:19:08,190 --> 00:19:09,980
Lad os overveje, hvad dette
faktisk ser ud.

379
00:19:09,980 --> 00:19:10,650
Lad mig hit spil.

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

381
00:19:14,210 --> 00:19:18,980
>> Så i dette spil, har vi en
frø, og ved hjælp af pilen keys--

382
00:19:18,980 --> 00:19:23,340
han tager større skridt end jeg remember--
Jeg har kontrol over denne frø.

383
00:19:23,340 --> 00:19:29,630
Og målet er at komme over den travle
vej uden at løbe ind i biler.

384
00:19:29,630 --> 00:19:34,735
Og lad os see-- hvis jeg går op her, jeg
nødt til at vente på en log for at rulle med.

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

386
00:19:38,130 --> 00:19:39,274
Dette føles som en fejl.

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

388
00:19:42,240 --> 00:19:43,495
Dette er lidt af en bug.

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

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

391
00:19:46,480 --> 00:19:51,550
Jeg er på dette her,
der, og så skal du holde

392
00:19:51,550 --> 00:19:54,100
ud, indtil du får alle
Frøerne til lilje puder.

393
00:19:54,100 --> 00:19:55,920
Nu ser måske
desto mere kompleks,

394
00:19:55,920 --> 00:19:57,840
men lad os prøve at bryde
dette ned mentalt

395
00:19:57,840 --> 00:20:00,040
og verbalt i sine blokke.

396
00:20:00,040 --> 00:20:03,910
Så der er nok et puslespil
stykke, som vi ikke har set endnu

397
00:20:03,910 --> 00:20:07,440
men der er reagerer på tastetryk,
til ting, jeg ramt på tastaturet.

398
00:20:07,440 --> 00:20:11,660
>> Så der er nok en slags
blok, der siger, hvis nøglen er lig op,

399
00:20:11,660 --> 00:20:15,965
så gøre noget med Scratch--
måske flytte det 10 trin på denne måde.

400
00:20:15,965 --> 00:20:20,240
Hvis der trykkes på ned-tasten, flytte 10 trin
denne måde, eller venstre tast, flytte 10 trin

401
00:20:20,240 --> 00:20:21,710
denne måde, 10 trin det.

402
00:20:21,710 --> 00:20:23,644
Jeg har klart slået katten til en frø.

403
00:20:23,644 --> 00:20:26,060
Så det er lige hvor den
kostume, som Scratch opkald det-- vi

404
00:20:26,060 --> 00:20:28,440
bare importeret et billede af frøen.

405
00:20:28,440 --> 00:20:29,570
>> Men hvad sker der?

406
00:20:29,570 --> 00:20:32,794
Hvilke andre linjer kode,
hvad andre puslespilsbrikker

407
00:20:32,794 --> 00:20:35,460
gjorde Blake, vores undervisning fyr,
brug i dette program, tilsyneladende?

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

409
00:20:38,320 --> 00:20:42,730
Hvad gør alting move--
hvad programmering konstruere?

410
00:20:42,730 --> 00:20:44,950
>> Motion, sure-- så
flytte blok, for sikker.

411
00:20:44,950 --> 00:20:49,330
Og hvad er det flytte blok
inderside, mest sandsynligt?

412
00:20:49,330 --> 00:20:52,850
Ja, en slags loop, måske en
evigt blokere, måske en gentagelse block--

413
00:20:52,850 --> 00:20:54,070
gentag indtil blok.

414
00:20:54,070 --> 00:20:57,330
Og det er hvad der gør de logfiler og
de lilje puder og alt andet træk

415
00:20:57,330 --> 00:20:57,990
frem og tilbage.

416
00:20:57,990 --> 00:21:00,270
Det er bare sker uendelige.

417
00:21:00,270 --> 00:21:03,180
>> Hvorfor er nogle af bilerne
bevæger sig hurtigere end de andre?

418
00:21:03,180 --> 00:21:06,607
Hvad er anderledes ved disse programmer?

419
00:21:06,607 --> 00:21:09,690
Ja, sandsynligvis nogle af dem tager
flere trin omgående, og nogle af dem

420
00:21:09,690 --> 00:21:10,690
færre trin på én gang.

421
00:21:10,690 --> 00:21:14,670
Og den visuelle virkning
er hurtig versus langsom.

422
00:21:14,670 --> 00:21:16,030
>> Hvad tror du der skete?

423
00:21:16,030 --> 00:21:19,700
Da jeg fik min frog hele vejen
på tværs af gaden og floden

424
00:21:19,700 --> 00:21:23,560
på lilje pad, noget
bemærkelsesværdigt skete.

425
00:21:23,560 --> 00:21:26,540
Hvad skete så snart jeg gjorde det?

426
00:21:26,540 --> 00:21:27,210
Det stoppede.

427
00:21:27,210 --> 00:21:29,680
Det frøen stoppet, og
Jeg fik en anden frø.

428
00:21:29,680 --> 00:21:33,155
Så hvad konstrukt skal være
bruges der, hvad funktion?

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

430
00:21:36,020 --> 00:21:38,660
>> Ja, så der er en form for
"Hvis" betingelse deroppe, også.

431
00:21:38,660 --> 00:21:41,909
Og det viser out-- vi ikke se denne--
men der er andre blokke i der, at

432
00:21:41,909 --> 00:21:45,300
kan sige, hvis du er rørende
en anden ting på skærmen,

433
00:21:45,300 --> 00:21:47,720
Hvis du rører lilje pad "og derefter".

434
00:21:47,720 --> 00:21:50,810
Og så er, når vi
gøre den anden frog vises.

435
00:21:50,810 --> 00:21:54,969
Så selv om dette spil er helt sikkert
meget dateret, selvom ved første øjekast

436
00:21:54,969 --> 00:21:58,010
der er så meget at gå on-- og Blake
ikke piske det op i to minutter,

437
00:21:58,010 --> 00:22:00,390
det sandsynligvis tog ham flere
timer til at skabe dette spil

438
00:22:00,390 --> 00:22:03,850
baseret på hans hukommelse eller videoer
Gårsdagens udgave af det.

439
00:22:03,850 --> 00:22:07,940
Men alle disse små ting
foregår på skærmen isoleret

440
00:22:07,940 --> 00:22:11,550
koges ned til disse meget simpelt
constructs-- bevægelser eller udsagn

441
00:22:11,550 --> 00:22:15,519
ligesom vi har diskuteret, loops og
betingelser, og det er om det.

442
00:22:15,519 --> 00:22:17,060
Der er et par andre mere avanceret funktioner.

443
00:22:17,060 --> 00:22:19,130
Nogle af dem er rent
æstetisk eller akustisk,

444
00:22:19,130 --> 00:22:20,964
ligesom de lyde, Jeg har lige spillet med.

445
00:22:20,964 --> 00:22:23,380
Men for det meste, du
har i dette sprog, Scratch,

446
00:22:23,380 --> 00:22:25,350
alle de grundlæggende
byggesten, som du

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

448
00:22:29,280 --> 00:22:32,960
og et antal andre sprog.

449
00:22:32,960 --> 00:22:36,720
Eventuelle spørgsmål om Scratch?

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

451
00:22:37,220 --> 00:22:40,303
Så vi vil ikke dykke dybere til Scratch,
selvom du er velkommen denne weekend,

452
00:22:40,303 --> 00:22:42,860
især hvis du har børn eller
niecer og nevøer og sådan,

453
00:22:42,860 --> 00:22:44,220
at introducere dem til Scratch.

454
00:22:44,220 --> 00:22:47,960
Det er faktisk en dejlig legesyg
miljø med, som dens forfattere siger,

455
00:22:47,960 --> 00:22:49,120
meget højt til loftet.

456
00:22:49,120 --> 00:22:51,670
Selvom vi startede med
meget lavt niveau detaljer,

457
00:22:51,670 --> 00:22:54,890
du virkelig kan gøre en hel del
med det, og det er måske

458
00:22:54,890 --> 00:22:57,360
en demonstration af netop dette.

459
00:22:57,360 --> 00:23:02,920
>> Men lad os nu overgangen til nogle mere
sofistikerede problemer, hvis du vil,

460
00:23:02,920 --> 00:23:05,870
kendt som "søgning" og
"Sortering", mere generelt.

461
00:23:05,870 --> 00:23:09,500
Vi havde denne telefonbog earlier-- her
en anden bare for discussion--

462
00:23:09,500 --> 00:23:13,460
at vi var i stand til at søge
mere effektivt, fordi

463
00:23:13,460 --> 00:23:15,270
af en væsentlig forudsætning.

464
00:23:15,270 --> 00:23:17,655
Og bare for at være klar, hvad
antagelse var jeg gør

465
00:23:17,655 --> 00:23:19,280
når du søger gennem denne telefonbog?

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

467
00:23:23,342 --> 00:23:25,300
At Mike Smith var i
telefonbogen, selvom jeg

468
00:23:25,300 --> 00:23:27,410
ville kunne håndtere
scenariet uden ham

469
00:23:27,410 --> 00:23:30,720
der, hvis jeg bare stoppet for tidligt.

470
00:23:30,720 --> 00:23:31,806
Bogen er alfabetisk.

471
00:23:31,806 --> 00:23:33,930
Og det er en meget generøs
antagelse, fordi det

472
00:23:33,930 --> 00:23:36,580
betyder someone-- Jeg er lidt
skære et hjørne,

473
00:23:36,580 --> 00:23:40,580
ligesom jeg hurtigere, fordi nogen
andre gjorde en masse hårdt arbejde for mig.

474
00:23:40,580 --> 00:23:43,120
>> Men hvad hvis telefonen
Bogen blev usorterede?

475
00:23:43,120 --> 00:23:47,050
Måske Verizon fik doven, bare kastede
alles navne og numre derinde

476
00:23:47,050 --> 00:23:50,120
måske i rækkefølge, som de
tilmeldt telefon tjenesten.

477
00:23:50,120 --> 00:23:54,570
Og hvor meget tid tager det mig
at finde en som Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 side telefon book-- hvor mange
sider skal jeg kigge igennem?

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

480
00:23:58,905 --> 00:24:00,030
Du er slags ude af lykke.

481
00:24:00,030 --> 00:24:03,420
Du bogstaveligt talt nødt til at se på alle
side, hvis telefonbogen er bare

482
00:24:03,420 --> 00:24:04,450
sorteres tilfældigt.

483
00:24:04,450 --> 00:24:06,910
Du kan få heldige og finde Mike
på den allerførste side, fordi han

484
00:24:06,910 --> 00:24:08,826
var den første kunde
at bestille telefon tjenesten.

485
00:24:08,826 --> 00:24:10,760
Men han kunne have været den sidste, også.

486
00:24:10,760 --> 00:24:12,500
>> Så tilfældig rækkefølge er ikke god.

487
00:24:12,500 --> 00:24:16,750
Så formoder, at vi er nødt til at sortere
telefonbogen eller generelt sortere data

488
00:24:16,750 --> 00:24:18,520
at vi har fået.

489
00:24:18,520 --> 00:24:19,440
Hvordan kan vi gøre det?

490
00:24:19,440 --> 00:24:21,360
>> Nå, lad mig bare prøve
et simpelt eksempel her.

491
00:24:21,360 --> 00:24:24,290
Lad mig gå videre og kaste en
par numre på tavlen.

492
00:24:24,290 --> 00:24:35,480
Antag numrene vi har, er,
lad os sige, fire, to, en, og tre.

493
00:24:35,480 --> 00:24:38,390
Og, Ben, sortere disse numre for os.

494
00:24:38,390 --> 00:24:39,017
>> Ok godt.

495
00:24:39,017 --> 00:24:39,850
Hvordan gjorde du det?

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

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

498
00:24:43,230 --> 00:24:44,710
Så start med den mindste
og den højeste,

499
00:24:44,710 --> 00:24:46,084
og det er virkelig god intuition.

500
00:24:46,084 --> 00:24:48,080
Og indse, at vi
mennesker er faktisk temmelig

501
00:24:48,080 --> 00:24:49,913
god til at løse problemer
som dette, i det mindste

502
00:24:49,913 --> 00:24:51,810
når dataene er relativt lille.

503
00:24:51,810 --> 00:24:54,860
Så snart du begynder at have hundredvis
af numre, tusindvis af numre,

504
00:24:54,860 --> 00:24:58,440
millioner af numre, Ben sandsynligvis
kunne ikke gøre det helt så hurtigt,

505
00:24:58,440 --> 00:25:00,620
under forudsætning af, at der var
huller i tallene.

506
00:25:00,620 --> 00:25:03,450
Temmelig let at tælle til en million
ellers blot tidskrævende.

507
00:25:03,450 --> 00:25:07,150
>> Så den algoritme det lyder
ligesom Ben bruges lige nu

508
00:25:07,150 --> 00:25:08,930
var søgen efter det mindste tal.

509
00:25:08,930 --> 00:25:12,900
Så selv om vi mennesker kan tage
i en masse oplysninger visuelt,

510
00:25:12,900 --> 00:25:14,830
en computer er faktisk
lidt mere begrænset.

511
00:25:14,830 --> 00:25:17,560
Computeren kan kun
se på en byte ad gangen

512
00:25:17,560 --> 00:25:20,770
eller måske fire bytes på en time--
disse dage måske 8 bytes på en time--

513
00:25:20,770 --> 00:25:24,450
men et meget lille antal
bytes på et givet tidspunkt.

514
00:25:24,450 --> 00:25:28,480
>> Så da vi virkelig har
fire separate værdier her--

515
00:25:28,480 --> 00:25:32,440
og du kan tænke på Ben som havende
skyklapper på, hvis han var en computer,

516
00:25:32,440 --> 00:25:36,450
at han ikke kan se noget andet
end et nummer på en time--

517
00:25:36,450 --> 00:25:39,720
så vi generelt vil antage, ligesom i
Engelsk, vi vil læse fra højre mod venstre.

518
00:25:39,720 --> 00:25:42,870
Så det første nummer Ben sandsynligvis set
på var fire og derefter meget hurtigt

519
00:25:42,870 --> 00:25:44,770
indså, at er en temmelig stor
number-- lad mig holde udkig.

520
00:25:44,770 --> 00:25:45,357
>> Der er to.

521
00:25:45,357 --> 00:25:45,940
Vent et øjeblik.

522
00:25:45,940 --> 00:25:47,070
To er mindre end fire.

523
00:25:47,070 --> 00:25:47,986
Jeg har tænkt mig at huske.

524
00:25:47,986 --> 00:25:49,070
To er nu den mindste.

525
00:25:49,070 --> 00:25:50,417
Nu en-- det er endnu bedre.

526
00:25:50,417 --> 00:25:51,250
Det er endnu mindre.

527
00:25:51,250 --> 00:25:54,000
Jeg har tænkt mig at glemme alt om to
og bare huske én nu.

528
00:25:54,000 --> 00:25:56,550
>> Og han kunne holde op med at kigge?

529
00:25:56,550 --> 00:25:58,360
Nå, kunne han baserede
på disse oplysninger,

530
00:25:58,360 --> 00:26:00,477
men han hellere søgning
resten af ​​listen.

531
00:26:00,477 --> 00:26:02,060
For hvad hvis nul var på listen?

532
00:26:02,060 --> 00:26:03,643
Hvad hvis negativ var på listen?

533
00:26:03,643 --> 00:26:07,720
Han ved kun, at hans svar
er korrekt, hvis han er udtømmende

534
00:26:07,720 --> 00:26:08,729
kontrolleres hele listen.

535
00:26:08,729 --> 00:26:10,020
Så vi ser på resten af ​​denne.

536
00:26:10,020 --> 00:26:11,394
Three-- det var spild af tid.

537
00:26:11,394 --> 00:26:13,540
Fik uheldige, men jeg var
stadig er korrekt at gøre det.

538
00:26:13,540 --> 00:26:17,857
Og så nu er han formentlig
valgt det mindste tal

539
00:26:17,857 --> 00:26:20,440
og bare sætte det i begyndelsen
på listen, som jeg vil gøre her.

540
00:26:20,440 --> 00:26:23,480
Nu hvad gjorde du gøre næste, selvom
du ikke synes om det næsten

541
00:26:23,480 --> 00:26:25,962
i dette omfang?

542
00:26:25,962 --> 00:26:27,670
Gentage processen,
så en slags sløjfe.

543
00:26:27,670 --> 00:26:28,920
Der er en velkendt idé.

544
00:26:28,920 --> 00:26:30,860
Så her er fire.

545
00:26:30,860 --> 00:26:32,110
Det er i øjeblikket den mindste.

546
00:26:32,110 --> 00:26:33,220
Det er en kandidat.

547
00:26:33,220 --> 00:26:33,900
Ikke længere.

548
00:26:33,900 --> 00:26:34,770
Nu har jeg set to.

549
00:26:34,770 --> 00:26:36,630
Det er den næstmindste element.

550
00:26:36,630 --> 00:26:40,800
Three-- det er ikke mindre, så
nu Ben kan plukke ud de to.

551
00:26:40,800 --> 00:26:44,510
>> Og nu er vi gentage processen og
selvfølgelig tre bliver trukket ud næste.

552
00:26:44,510 --> 00:26:45,420
Gentage processen.

553
00:26:45,420 --> 00:26:46,990
Fire bliver trukket ud.

554
00:26:46,990 --> 00:26:50,140
Og nu er vi ude af tal,
så listen skal sorteres.

555
00:26:50,140 --> 00:26:51,960
>> Og ja, det er en formel algoritme.

556
00:26:51,960 --> 00:26:56,610
En datalog ville
kalder dette "valg slags,"

557
00:26:56,610 --> 00:27:00,880
ideen er slags en
liste iteratively-- igen

558
00:27:00,880 --> 00:27:03,807
og igen og igen at vælge
det mindste tal.

559
00:27:03,807 --> 00:27:06,140
Og hvad er nice om det er
det er bare så pokkers intuitivt.

560
00:27:06,140 --> 00:27:07,470
Det er så simpelt.

561
00:27:07,470 --> 00:27:11,100
Og du kan gentage den samme
drift igen og igen.

562
00:27:11,100 --> 00:27:12,150
Det er simpelt.

563
00:27:12,150 --> 00:27:17,170
>> I dette tilfælde var det hurtigt, men
hvor lang tid tager det faktisk tage?

564
00:27:17,170 --> 00:27:19,880
Lad os gøre det synes og
føle sig lidt mere kedelig.

565
00:27:19,880 --> 00:27:24,150
Så en, to, tre, fire, fem seks,
syv, otte, ni, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- vilkårligt antal.

567
00:27:26,160 --> 00:27:28,780
Jeg ville bare mere denne
tid end blot fire.

568
00:27:28,780 --> 00:27:30,780
Så hvis jeg har en hel
bundt af tal nu-- det

569
00:27:30,780 --> 00:27:32,420
ikke engang noget
hvad de are-- lad os

570
00:27:32,420 --> 00:27:34,380
tænke over, hvad dette
algoritme virkelig er.

571
00:27:34,380 --> 00:27:35,857
>> Antag at der er tal der.

572
00:27:35,857 --> 00:27:38,190
Igen, er ligegyldigt, hvad
de er, men de er tilfældige.

573
00:27:38,190 --> 00:27:39,679
Jeg søger Ben algoritme.

574
00:27:39,679 --> 00:27:41,220
Jeg har brug for at vælge det mindste tal.

575
00:27:41,220 --> 00:27:41,761
Hvad skal jeg gøre?

576
00:27:41,761 --> 00:27:44,240
Og jeg har tænkt mig at fysisk
gør det denne gang til at handle det ud.

577
00:27:44,240 --> 00:27:46,099
Ser, ser,
kigge, kigge, kigge.

578
00:27:46,099 --> 00:27:48,140
Kun ved den tid, jeg kommer til
enden af ​​listen kan

579
00:27:48,140 --> 00:27:51,230
Jeg er klar over den mindste
nummer var to denne gang.

580
00:27:51,230 --> 00:27:52,720
Man er ikke i listen.

581
00:27:52,720 --> 00:27:54,400
Så jeg satte to.

582
00:27:54,400 --> 00:27:55,590
>> Hvad gør jeg nu?

583
00:27:55,590 --> 00:27:58,600
Ser, ser, ser, ser.

584
00:27:58,600 --> 00:28:02,250
Nu fandt jeg nummer syv, fordi
Der er huller i disse numbers--

585
00:28:02,250 --> 00:28:03,300
men blot vilkårlig.

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

587
00:28:03,800 --> 00:28:06,030
Så nu kan jeg lægge syv.

588
00:28:06,030 --> 00:28:08,860
Ser kigge, kigge.

589
00:28:08,860 --> 00:28:11,030
>> Nu er jeg antager, af
selvfølgelig, at Ben ikke

590
00:28:11,030 --> 00:28:14,780
har ekstra RAM, ekstra
hukommelse, fordi, selvfølgelig,

591
00:28:14,780 --> 00:28:16,080
Jeg kigger på det samme nummer.

592
00:28:16,080 --> 00:28:18,246
Sikkert jeg kunne have husket
alle disse numre,

593
00:28:18,246 --> 00:28:19,930
og det er helt rigtigt.

594
00:28:19,930 --> 00:28:22,610
Men hvis Ben husker alle
af numrene han har set,

595
00:28:22,610 --> 00:28:24,430
han har ikke rigtig gjort
grundlæggende fremskridt

596
00:28:24,430 --> 00:28:26,170
fordi han allerede har
evnen til at søge

597
00:28:26,170 --> 00:28:27,540
gennem numrene på tavlen.

598
00:28:27,540 --> 00:28:29,373
Huske alle de
numre hjælper ikke,

599
00:28:29,373 --> 00:28:32,490
fordi han kan stadig som en computer
kun se på, vi har sagt, et nummer

600
00:28:32,490 --> 00:28:33,080
på et tidspunkt.

601
00:28:33,080 --> 00:28:35,760
Så der er ingen form for cheat
der, at du kan udnytte.

602
00:28:35,760 --> 00:28:39,170
>> Så i virkeligheden, da jeg
fortsætte med at søge på listen,

603
00:28:39,170 --> 00:28:44,200
Jeg bogstaveligt talt nødt til bare at holde ud
frem og tilbage gennem det, plukning ud

604
00:28:44,200 --> 00:28:45,710
den næstmindste antal.

605
00:28:45,710 --> 00:28:48,810
Og som du kan slags udlede
fra mine dumme bevægelser,

606
00:28:48,810 --> 00:28:50,860
dette bliver bare meget
kedelige meget hurtigt,

607
00:28:50,860 --> 00:28:54,850
og jeg synes at gå tilbage og
tilbage, frem og tilbage ganske lidt.

608
00:28:54,850 --> 00:29:03,220
Nu for at være fair, jeg ikke behøver at gå
ganske som, ja, lad os see-- at være fair,

609
00:29:03,220 --> 00:29:06,310
Jeg behøver ikke at gå helt
så mange skridt hver gang.

610
00:29:06,310 --> 00:29:09,200
Fordi, selvfølgelig, som jeg
vælge numre fra listen,

611
00:29:09,200 --> 00:29:11,860
den resterende liste bliver kortere.

612
00:29:11,860 --> 00:29:14,240
>> Og så lad os tænke over
hvor mange skridt jeg er faktisk

613
00:29:14,240 --> 00:29:16,010
traipsing gennem hver gang.

614
00:29:16,010 --> 00:29:18,950
I den allerførste situation,
vi havde 16 numre,

615
00:29:18,950 --> 00:29:22,210
og så maximally-- lad os bare
gøre dette for en discussion--

616
00:29:22,210 --> 00:29:25,640
Jeg var nødt til at se gennem 16
tallene for at finde den mindste.

617
00:29:25,640 --> 00:29:28,420
Men når jeg plukket ud
det mindste tal, hvordan

618
00:29:28,420 --> 00:29:30,590
længe var den resterende liste, selvfølgelig?

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

620
00:29:31,420 --> 00:29:34,670
Så hvor mange numre gjorde Ben eller jeg har
til at se gennem anden gang rundt?

621
00:29:34,670 --> 00:29:36,832
15, bare at gå og finde den mindste.

622
00:29:36,832 --> 00:29:39,540
Men nu, selvfølgelig, listen er,
Også mindre, end det var før.

623
00:29:39,540 --> 00:29:42,540
Så hvordan mange skridt gjorde jeg
nødt til at tage det næste gang?

624
00:29:42,540 --> 00:29:49,970
14 og derefter 13 og derefter 12, plus prik,
prik, prik, indtil jeg tilbage med kun én.

625
00:29:49,970 --> 00:29:53,146
Så nu en datalog ville
spørge, godt, hvad betyder, at alle er lige?

626
00:29:53,146 --> 00:29:55,770
Det faktisk er lig med nogle konkrete
nummer, som vi kunne helt sikkert

627
00:29:55,770 --> 00:30:00,490
gøre matematisk, men vi ønsker at tale
om effektiviteten af ​​algoritmer

628
00:30:00,490 --> 00:30:04,940
lidt mere formulaically,
uafhængig af hvor lang listen er.

629
00:30:04,940 --> 00:30:06,240
>> Og så ved du hvad?

630
00:30:06,240 --> 00:30:09,860
Dette er 16, men som jeg sagde før,
lad os bare kalde størrelsen af ​​problemet

631
00:30:09,860 --> 00:30:10,970
n, hvor n er et tal.

632
00:30:10,970 --> 00:30:13,220
Måske er det 16, måske er det
tre, måske er det en million.

633
00:30:13,220 --> 00:30:13,761
Jeg ved ikke.

634
00:30:13,761 --> 00:30:14,390
Jeg er ligeglad.

635
00:30:14,390 --> 00:30:16,520
Hvad jeg virkelig ønsker, er
en formel, jeg kan

636
00:30:16,520 --> 00:30:19,420
bruge til at sammenligne denne algoritme
mod andre algoritmer

637
00:30:19,420 --> 00:30:22,350
at nogen måske hævde
er bedre eller værre.

638
00:30:22,350 --> 00:30:25,430
>> Så det viser sig, og kun jeg
kender det fra folkeskolen,

639
00:30:25,430 --> 00:30:34,790
at dette rent faktisk virker ud til den samme
ting som n løbet n plus en over to.

640
00:30:34,790 --> 00:30:40,020
Og det sker til lige, af
Selvfølgelig n kvadreret plus n over to.

641
00:30:40,020 --> 00:30:43,250
Så hvis jeg ønskede en formel
for hvor mange skridt

642
00:30:43,250 --> 00:30:46,330
var involveret i at kigge på alle
af disse numre igen og igen

643
00:30:46,330 --> 00:30:52,681
og igen og igen, vil jeg sige
det er n kvadreret plus n over to.

644
00:30:52,681 --> 00:30:53,430
Men ved du hvad?

645
00:30:53,430 --> 00:30:54,500
Det ser bare rodet.

646
00:30:54,500 --> 00:30:56,470
Jeg bare virkelig ønsker en
generel følelse af ting.

647
00:30:56,470 --> 00:30:58,810
Og du måske husker fra
gymnasiet, at der

648
00:30:58,810 --> 00:31:00,660
er begrebet højeste orden sigt.

649
00:31:00,660 --> 00:31:05,300
Hvilke af disse vilkår, n
kvadreret, n, eller den halve,

650
00:31:05,300 --> 00:31:07,550
har størst virkning over tid?

651
00:31:07,550 --> 00:31:11,920
Jo større n bliver, som
af disse spørgsmål mest?

652
00:31:11,920 --> 00:31:15,560
>> Med andre ord, hvis jeg sætte
i en million, n kvadreret

653
00:31:15,560 --> 00:31:17,900
vil være mest sandsynligt
den dominerende faktor,

654
00:31:17,900 --> 00:31:21,670
fordi en million gange
selv er en meget større

655
00:31:21,670 --> 00:31:23,682
end plus én ekstra million.

656
00:31:23,682 --> 00:31:24,390
Så ved du hvad?

657
00:31:24,390 --> 00:31:27,305
Dette er sådan en pokkers stor
nummer, hvis du firkantet et nummer.

658
00:31:27,305 --> 00:31:28,430
Dette betyder ikke rigtig noget.

659
00:31:28,430 --> 00:31:30,596
Vi bare kryds, der
ud og glemme alt om det.

660
00:31:30,596 --> 00:31:34,250
Og så en datalog vil sige
at effektiviteten af ​​denne algoritme

661
00:31:34,250 --> 00:31:37,850
er af størrelsesordenen n squared--
Jeg mener virkelig en tilnærmelse.

662
00:31:37,850 --> 00:31:40,810
Det er slags groft n potens.

663
00:31:40,810 --> 00:31:44,130
Over tid, jo større
og større n bliver dette

664
00:31:44,130 --> 00:31:47,610
er en god vurdering for, hvad
effektivitet eller mangel på effektivitet

665
00:31:47,610 --> 00:31:49,400
af denne algoritme faktisk er.

666
00:31:49,400 --> 00:31:52,040
Og jeg udlede, at selvfølgelig,
fra faktisk gør det math.

667
00:31:52,040 --> 00:31:54,040
Men nu er jeg bare vinke
mine hænder, fordi jeg bare

668
00:31:54,040 --> 00:31:55,790
ønsker en generel følelse af denne algoritme.

669
00:31:55,790 --> 00:31:58,850
>> Så bruger den samme logik, i mellemtiden,
Lad os overveje en anden algoritme

670
00:31:58,850 --> 00:32:01,162
vi allerede kigget at-- lineær søgning.

671
00:32:01,162 --> 00:32:02,870
Da jeg søgte
til telefonen book--

672
00:32:02,870 --> 00:32:05,980
ikke sortering af den, søgning
via telefonen book--

673
00:32:05,980 --> 00:32:09,197
Vi holdt siger, at det var
1.000 trin eller 500 trin.

674
00:32:09,197 --> 00:32:10,280
Men lad os generalisere det.

675
00:32:10,280 --> 00:32:12,860
Hvis der er n sider i
telefonbogen, hvad er

676
00:32:12,860 --> 00:32:17,250
køretiden eller
effektiviteten af ​​lineær søgning?

677
00:32:17,250 --> 00:32:19,750
Det er på rækkefølgen af
hvor mange skridt til at finde

678
00:32:19,750 --> 00:32:24,210
Mike Smith ved lineær søgning, den
første algoritme, eller endda den anden?

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

680
00:32:27,240 --> 00:32:31,710
>> I værste fald, Mike
er i slutningen af ​​bogen.

681
00:32:31,710 --> 00:32:35,590
Så hvis telefonbogen har 1.000 sider,
vi sagde sidste gang, i værste fald,

682
00:32:35,590 --> 00:32:38,380
det kan tage nogenlunde hvordan
mange sider for at finde Mike?

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

684
00:32:38,990 --> 00:32:39,830
Det er en øvre grænse.

685
00:32:39,830 --> 00:32:41,790
Det er en værst mulige situation.

686
00:32:41,790 --> 00:32:44,410
Men igen, vi flytter væk
fra numre som 1000 nu.

687
00:32:44,410 --> 00:32:45,730
Det er bare n.

688
00:32:45,730 --> 00:32:47,470
>> Så hvad er den logiske konklusion?

689
00:32:47,470 --> 00:32:50,210
Finde Mike i en telefon
bog, der har n-sider

690
00:32:50,210 --> 00:32:55,280
kan tage, i værste fald,
hvor mange trin i størrelsesordenen n?

691
00:32:55,280 --> 00:32:58,110
Og faktisk en computer
videnskabsmand ville sige

692
00:32:58,110 --> 00:33:02,340
at køretiden, eller
ydelse eller effektivitet

693
00:33:02,340 --> 00:33:07,470
eller ineffektivitet, af en algoritme som
en lineær søgning er af størrelsesordenen n.

694
00:33:07,470 --> 00:33:10,010
Og vi kan anvende den samme
logik krydse noget ud

695
00:33:10,010 --> 00:33:13,170
som jeg lige gjorde til den anden
algoritme, vi havde med telefonbogen,

696
00:33:13,170 --> 00:33:16,040
hvor vi gik to sider ad gangen.

697
00:33:16,040 --> 00:33:20,120
>> Så 1000 side telefonbog måske
tage os 500 sider sving, plus en

698
00:33:20,120 --> 00:33:21,910
hvis vi fordoble en smule tilbage.

699
00:33:21,910 --> 00:33:26,590
Så hvis en telefonbog har n-sider, men
vi laver to sider ad gangen,

700
00:33:26,590 --> 00:33:28,900
det er hvad groft?

701
00:33:28,900 --> 00:33:33,190
N over to, så det er ligesom n over to.

702
00:33:33,190 --> 00:33:38,490
Men jeg gjorde kravet en
øjeblik siden, at n løbet to--

703
00:33:38,490 --> 00:33:41,060
der er slags det samme som bare n.

704
00:33:41,060 --> 00:33:44,050
Det er bare en konstant faktor,
dataloger ville sige.

705
00:33:44,050 --> 00:33:45,970
Lad os kun fokusere på
variablerne, really--

706
00:33:45,970 --> 00:33:47,780
de største variabler i ligningen.

707
00:33:47,780 --> 00:33:52,530
>> Så lineær søgning, uanset om gøres en
side ad gangen eller to sider ad gangen,

708
00:33:52,530 --> 00:33:54,810
er slags grundlæggende de samme.

709
00:33:54,810 --> 00:33:56,880
Det er stadig på rækkefølgen af ​​n.

710
00:33:56,880 --> 00:34:01,930
Men jeg hævdede med mit billede tidligere
at den tredje algoritme var ikke

711
00:34:01,930 --> 00:34:02,480
lineær.

712
00:34:02,480 --> 00:34:03,605
Det var ikke en lige linje.

713
00:34:03,605 --> 00:34:08,659
Det var denne krumme linie, og
algebraisk formel der var hvad?

714
00:34:08,659 --> 00:34:11,812
Log af n- så logge basis to af n.

715
00:34:11,812 --> 00:34:14,520
Og vi behøver ikke at gå ind for
mange detaljer om logaritmer i dag,

716
00:34:14,520 --> 00:34:17,394
men de fleste dataloger ville ikke
endda fortælle dig, hvad basen er.

717
00:34:17,394 --> 00:34:20,639
Fordi det hele er bare
konstante faktorer, så at sige,

718
00:34:20,639 --> 00:34:22,659
kun små numeriske forskelle.

719
00:34:22,659 --> 00:34:31,179
Og så det ville være en meget almindelig
måde for særligt formelle computer

720
00:34:31,179 --> 00:34:33,949
forskere ved et bord eller
programmører på en hvid bord

721
00:34:33,949 --> 00:34:36,889
faktisk argumenterer som
algoritme de ville bruge

722
00:34:36,889 --> 00:34:39,500
eller hvad effektiviteten
af deres algoritme er.

723
00:34:39,500 --> 00:34:42,960
>> Og det er ikke nødvendigvis noget
du diskutere i nogen stor detalje,

724
00:34:42,960 --> 00:34:47,889
men en god programmør er nogen
der har en solid, formel baggrund.

725
00:34:47,889 --> 00:34:50,120
Han er i stand til at tale med
dig i denne slags måde

726
00:34:50,120 --> 00:34:53,350
og faktisk gøre
kvalitative argumenter som

727
00:34:53,350 --> 00:34:56,870
hvorfor en algoritme eller
ét stykke software

728
00:34:56,870 --> 00:35:00,165
er overlegen i nogle måde til en anden.

729
00:35:00,165 --> 00:35:02,540
Fordi du kunne sikkert
bare køre én persons program

730
00:35:02,540 --> 00:35:04,980
og tælle antallet af sekunder
det tager at sortere nogle tal,

731
00:35:04,980 --> 00:35:06,710
og du kan køre nogle
anden persons program

732
00:35:06,710 --> 00:35:08,418
og tælle antallet
sekunder det tager.

733
00:35:08,418 --> 00:35:12,840
Men det er en mere generel måde,
du kan bruge til at analysere algoritmer,

734
00:35:12,840 --> 00:35:15,520
hvis du vil, bare på
papir eller bare verbalt.

735
00:35:15,520 --> 00:35:18,430
Uden selv kører det uden
selv forsøger prøve indgange,

736
00:35:18,430 --> 00:35:20,180
du kan bare ræsonnere igennem den.

737
00:35:20,180 --> 00:35:24,670
Og så med at ansætte en udvikler, eller hvis
have ham eller hende slags argumentere for dig

738
00:35:24,670 --> 00:35:28,460
hvorfor deres algoritme, deres hemmelighed
sauce til at søge milliarder

739
00:35:28,460 --> 00:35:30,580
af websider til din
Virksomheden er bedre, disse

740
00:35:30,580 --> 00:35:33,302
er den slags argumenter, de
bør ideelt set være i stand til at gøre.

741
00:35:33,302 --> 00:35:35,010
Eller i det mindste disse er
den slags ting

742
00:35:35,010 --> 00:35:40,211
der ville komme op i debat på
mindst i en meget formelle diskussion.

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

744
00:35:40,710 --> 00:35:44,400
Så Ben foreslog noget
kaldet udvælgelse slags.

745
00:35:44,400 --> 00:35:48,200
Men jeg har tænkt mig at foreslå, at der er
andre måder at gøre dette, også.

746
00:35:48,200 --> 00:35:50,400
Hvad jeg ikke kan virkelig godt lide
om Ben algoritme

747
00:35:50,400 --> 00:35:54,400
er, at han holdt walking, eller
have mig gå frem og tilbage

748
00:35:54,400 --> 00:35:56,930
og frem og tilbage og frem og tilbage.

749
00:35:56,930 --> 00:36:04,130
Hvad hvis i stedet jeg skulle gøre
noget som disse numre her

750
00:36:04,130 --> 00:36:08,200
og jeg skulle bare beskæftige sig med hver
nummer igen, som jeg givet det?

751
00:36:08,200 --> 00:36:10,780
>> Med andre ord, her er
min liste over numre.

752
00:36:10,780 --> 00:36:12,944
Fire, en, tre, to.

753
00:36:12,944 --> 00:36:14,360
Og jeg har tænkt mig at gøre følgende.

754
00:36:14,360 --> 00:36:17,230
Jeg har tænkt mig at indsætte numrene
hvor de hører snarere

755
00:36:17,230 --> 00:36:18,980
end at vælge dem én ad gangen.

756
00:36:18,980 --> 00:36:20,820
Med andre ord, her er nummer fire.

757
00:36:20,820 --> 00:36:22,430
>> Her er min oprindelige liste.

758
00:36:22,430 --> 00:36:25,290
Og jeg har tænkt mig at opretholde
hovedsageligt en ny liste her.

759
00:36:25,290 --> 00:36:26,710
Så dette er den gamle liste.

760
00:36:26,710 --> 00:36:28,560
Dette er den nye liste.

761
00:36:28,560 --> 00:36:30,220
Jeg ser nummer fire første.

762
00:36:30,220 --> 00:36:34,500
Min nye liste er oprindeligt tom,
så det er trivielt tilfældet

763
00:36:34,500 --> 00:36:36,410
at fire er nu assorteret liste.

764
00:36:36,410 --> 00:36:39,560
Jeg er bare tage antallet jeg givet,
og jeg sætte det i min nye liste.

765
00:36:39,560 --> 00:36:41,460
>> Er denne nye liste sorteret?

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

767
00:36:41,990 --> 00:36:45,090
Det er dumt, fordi der er bare én
element, men det er absolut sorteres.

768
00:36:45,090 --> 00:36:46,390
Der er ikke noget ud af sted.

769
00:36:46,390 --> 00:36:49,290
Det er mere interessant, denne algoritme,
når jeg flytter til næste trin.

770
00:36:49,290 --> 00:36:50,550
>> Nu har jeg en.

771
00:36:50,550 --> 00:36:55,430
Så en selvfølgelig tilhører på det
begyndelsen eller slutningen af ​​denne nye liste?

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

773
00:36:56,360 --> 00:36:58,530
Så jeg er nødt til at gøre noget arbejde nu.

774
00:36:58,530 --> 00:37:01,410
Jeg har taget nogle
friheder med min markør

775
00:37:01,410 --> 00:37:03,120
ved blot at trække ting
hvor jeg vil have dem,

776
00:37:03,120 --> 00:37:05,320
men det er ikke rigtig
præcise i en computer.

777
00:37:05,320 --> 00:37:08,530
En computer, som vi ved, har
RAM eller Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
og det er en byte og
anden byte og en anden byte.

779
00:37:12,411 --> 00:37:14,910
Og hvis du har en gigabyte
RAM, har du en milliard bytes,

780
00:37:14,910 --> 00:37:16,680
men de er fysisk på ét sted.

781
00:37:16,680 --> 00:37:19,540
Du kan ikke bare flytte ting rundt
ved at trække det på tavlen

782
00:37:19,540 --> 00:37:20,750
hvorend du vil.

783
00:37:20,750 --> 00:37:24,090
Så hvis min nye liste har
fire steder i hukommelsen,

784
00:37:24,090 --> 00:37:27,480
Desværre fire er
allerede på det forkerte sted.

785
00:37:27,480 --> 00:37:30,410
>> Så for at indsætte nummer et
Jeg kan ikke bare trække det her.

786
00:37:30,410 --> 00:37:31,901
Denne hukommelse placering findes ikke.

787
00:37:31,901 --> 00:37:35,150
Det ville være snyd, og jeg har været
snyd billedligt i et par minutter

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

789
00:37:35,800 --> 00:37:40,950
Så virkelig, hvis jeg ønsker at sætte en her,
Jeg er nødt til midlertidigt at kopiere fire

790
00:37:40,950 --> 00:37:43,030
og derefter sætte den ene der.

791
00:37:43,030 --> 00:37:45,500
>> Det er fint, det er korrekt,
det er teknisk muligt,

792
00:37:45,500 --> 00:37:48,410
men indse det er ekstra arbejde.

793
00:37:48,410 --> 00:37:50,460
Jeg har ikke bare sætter antallet på plads.

794
00:37:50,460 --> 00:37:53,026
Jeg først måtte flytte en
nummer, og derefter sætte det på plads,

795
00:37:53,026 --> 00:37:54,650
så jeg slags fordoblet mit mængde arbejde.

796
00:37:54,650 --> 00:37:55,660
Så hold det i tankerne.

797
00:37:55,660 --> 00:37:57,120
>> Men jeg er nu færdig med dette element.

798
00:37:57,120 --> 00:37:59,056
Nu vil jeg få fat i nummer tre.

799
00:37:59,056 --> 00:38:00,430
Hvor naturligvis hører det?

800
00:38:00,430 --> 00:38:01,480
Ind imellem.

801
00:38:01,480 --> 00:38:03,650
Jeg kan ikke snyde længere
og bare sætte det der,

802
00:38:03,650 --> 00:38:06,770
fordi igen, denne hukommelse
er i fysiske lokaliteter.

803
00:38:06,770 --> 00:38:10,900
Så jeg er nødt til at kopiere fire
og sætte tre herovre.

804
00:38:10,900 --> 00:38:11,550
Ikke noget særligt.

805
00:38:11,550 --> 00:38:14,610
Det er bare et ekstra skridt
igen-- føles meget billig.

806
00:38:14,610 --> 00:38:16,445
>> Men nu jeg gå videre til de to.

807
00:38:16,445 --> 00:38:17,820
De to naturligvis hører her.

808
00:38:17,820 --> 00:38:20,990
Nu begynder du at se, hvordan
arbejdet kan hobe sig op.

809
00:38:20,990 --> 00:38:23,520
Nu, hvad skal jeg gøre?

810
00:38:23,520 --> 00:38:28,570
Ja, jeg er nødt til at flytte de fire,
Jeg så nødt til at kopiere de tre,

811
00:38:28,570 --> 00:38:31,200
og nu kan jeg indsætte de to.

812
00:38:31,200 --> 00:38:34,460
Og fangsten med dette
algoritme, interessant nok,

813
00:38:34,460 --> 00:38:41,050
er der formoder, at vi har en mere ekstrem
tilfælde, hvor det er lad os sige otte, syv,

814
00:38:41,050 --> 00:38:45,150
seks, fem, fire, tre, to, en.

815
00:38:45,150 --> 00:38:49,450
Dette er, i mange sammenhænge,
det værst tænkelige scenarie,

816
00:38:49,450 --> 00:38:51,570
fordi darn ting
er bogstaveligt talt bagud.

817
00:38:51,570 --> 00:38:53,670
>> Det gør ikke rigtig
påvirke Ben algoritme,

818
00:38:53,670 --> 00:38:55,940
fordi i Ben udvælgelse
sortere han vil holde

819
00:38:55,940 --> 00:38:58,359
gå frem og tilbage gennem listen.

820
00:38:58,359 --> 00:39:01,150
Og fordi han altid var på udkig
gennem hele resterende liste,

821
00:39:01,150 --> 00:39:02,858
det gør ikke noget
hvor elementerne er.

822
00:39:02,858 --> 00:39:05,630
Men i dette tilfælde med min indsættelse
approach-- lad os prøve dette.

823
00:39:05,630 --> 00:39:08,616
>> Så en, to, tre, fire,
fem, seks, syv, otte.

824
00:39:08,616 --> 00:39:11,630
En to tre fire,
fem, seks, syv, otte.

825
00:39:11,630 --> 00:39:14,320
Jeg har tænkt mig at tage otte,
og hvor kan jeg sætte det?

826
00:39:14,320 --> 00:39:17,260
Nå, i begyndelsen af ​​min liste,
fordi denne nye liste sorteres.

827
00:39:17,260 --> 00:39:18,760
Og jeg krydse den ud.

828
00:39:18,760 --> 00:39:20,551
>> Hvor skal jeg placere syv?

829
00:39:20,551 --> 00:39:21,050
Pokkers.

830
00:39:21,050 --> 00:39:23,174
Det skal gå der, så
Jeg er nødt til at gøre nogle kopiering.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Og nu syv går her.

833
00:39:28,480 --> 00:39:29,860
Nu jeg gå videre til seks.

834
00:39:29,860 --> 00:39:30,980
Nu er det endnu mere arbejde.

835
00:39:30,980 --> 00:39:32,570
>> Otte har at gå her.

836
00:39:32,570 --> 00:39:33,920
Syv har at gå her.

837
00:39:33,920 --> 00:39:35,450
Nu seks kan gå her.

838
00:39:35,450 --> 00:39:37,950
Nu jeg fat i fem.

839
00:39:37,950 --> 00:39:40,560
Nu otte skal gå
her, syv har at gå her,

840
00:39:40,560 --> 00:39:43,650
seks har at gå her, og
nu fem og gentag.

841
00:39:43,650 --> 00:39:46,610
Og jeg er temmelig meget
flytte den hele tiden.

842
00:39:46,610 --> 00:39:52,950
>> Så i slutningen, denne algorithm-- vi får
kalder det indsættelse sort-- faktisk

843
00:39:52,950 --> 00:39:55,020
har en masse arbejde, også.

844
00:39:55,020 --> 00:39:56,970
Det er bare anderledes
slags arbejde end Ben.

845
00:39:56,970 --> 00:40:00,090
Ben arbejde havde mig gå
frem og tilbage hele tiden,

846
00:40:00,090 --> 00:40:03,510
vælge den næstmindste
element igen og igen.

847
00:40:03,510 --> 00:40:06,660
Så det var denne meget visuelle form for arbejde.

848
00:40:06,660 --> 00:40:10,600
>> Denne anden algoritme, som stadig
correct-- det vil få jobbet done--

849
00:40:10,600 --> 00:40:12,800
bare ændrer mængden af ​​arbejde.

850
00:40:12,800 --> 00:40:15,420
Det ligner oprindeligt er du
besparelse, fordi du er bare

851
00:40:15,420 --> 00:40:19,190
beskæftiger sig med hvert element
op foran uden at gå alt

852
00:40:19,190 --> 00:40:20,930
vejen gennem listen ligesom Ben var.

853
00:40:20,930 --> 00:40:25,300
Men problemet er, især i disse
skøre sager, hvor det hele er bagud,

854
00:40:25,300 --> 00:40:27,830
du er bare sådan
udskyde det hårde arbejde

855
00:40:27,830 --> 00:40:30,360
indtil du nødt til at ordne dine fejl.

856
00:40:30,360 --> 00:40:33,919
>> Og så hvis du kan forestille dig dette
otte og syv og seks og fem

857
00:40:33,919 --> 00:40:36,710
og senere fire og tre og to
flytter deres vej gennem listen,

858
00:40:36,710 --> 00:40:39,060
Vi har netop ændret
type arbejde, vi laver.

859
00:40:39,060 --> 00:40:42,340
Stedet for at gøre det på
begyndelsen af ​​min iteration,

860
00:40:42,340 --> 00:40:45,250
Jeg er bare at gøre det på
slutningen af ​​hver iteration.

861
00:40:45,250 --> 00:40:50,550
Så det viser sig, at denne algoritme,
Også generelt kaldes indsættelsessortering,

862
00:40:50,550 --> 00:40:52,190
er også af størrelsesordenen n potens.

863
00:40:52,190 --> 00:40:56,480
Det er faktisk ikke bedre,
ikke bedre overhovedet.

864
00:40:56,480 --> 00:41:00,810
>> Men der er en tredje tilgang
Jeg vil opfordre os til at overveje,

865
00:41:00,810 --> 00:41:02,970
som er dette.

866
00:41:02,970 --> 00:41:07,850
Så formoder min liste, for enkelhed
igen, er fire, en, tre,

867
00:41:07,850 --> 00:41:11,080
to-- blot fire numre.

868
00:41:11,080 --> 00:41:13,300
Ben havde god intuition,
godt menneske intuition

869
00:41:13,300 --> 00:41:16,340
før, hvorved fast vi hele
liste eventually-- indsættelsessortering.

870
00:41:16,340 --> 00:41:18,020
Jeg lokkede os sammen.

871
00:41:18,020 --> 00:41:22,530
Men lad os betragte
enkleste måde at løse denne liste.

872
00:41:22,530 --> 00:41:24,110
>> Denne liste er ikke sorteres.

873
00:41:24,110 --> 00:41:26,130
Hvorfor?

874
00:41:26,130 --> 00:41:31,920
På engelsk, forklare, hvorfor
Det er faktisk ikke sorteres.

875
00:41:31,920 --> 00:41:33,400
Hvad betyder det ikke skal sorteres?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: Det er ikke sekventiel.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Ikke sekventiel.

878
00:41:34,990 --> 00:41:35,822
Giv mig et eksempel.

879
00:41:35,822 --> 00:41:37,180
>> STUDENT: Sæt dem i rækkefølge.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Giv mig et mere konkret eksempel.

882
00:41:38,790 --> 00:41:39,832
>> STUDENT: Stigende rækkefølge.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Ikke stigende rækkefølge.

884
00:41:41,206 --> 00:41:42,100
Være mere præcis.

885
00:41:42,100 --> 00:41:45,190
Jeg ved ikke, hvad du mener med stigende.

886
00:41:45,190 --> 00:41:47,150
Hvad er der galt?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: Den mindste af de
numre er ikke i det første rum.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: Mindste antal er
ikke i det første rum.

889
00:41:51,140 --> 00:41:52,120
Vær mere specifik.

890
00:41:52,120 --> 00:41:55,000
Jeg begynder at fange den.

891
00:41:55,000 --> 00:41:59,470
Vi regner, men
hvad der er ude af drift her?

892
00:41:59,470 --> 00:42:00,707
>> STUDENT: Numerisk sekvens.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: Numerisk sekvens.

894
00:42:02,040 --> 00:42:04,248
Alles slags holde
det her-- meget højt niveau.

895
00:42:04,248 --> 00:42:07,450
Bare bogstaveligt fortælle mig, hvad der er
forkert som en fem-årig magt.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: Plus en.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Hvad er det?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: Plus en.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Hvad mener du plus en?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Giv mig en anden fem-årig.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Hvad er der galt, mor?

904
00:42:18,330 --> 00:42:19,940
Hvad er der galt, far?

905
00:42:19,940 --> 00:42:22,808
Hvad mener du dette er ikke sorteres?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: Det er ikke det rigtige sted.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Hvad er
ikke på det rigtige sted?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Fire.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, godt.

910
00:42:27,090 --> 00:42:29,110
Så fire er ikke hvor det skal være.

911
00:42:29,110 --> 00:42:30,590
Især er denne ret?

912
00:42:30,590 --> 00:42:33,000
Fire og en, den første
to tal, jeg ser.

913
00:42:33,000 --> 00:42:34,930
Er det her rigtigt?

914
00:42:34,930 --> 00:42:36,427
Nej, de er ude af drift, ikke?

915
00:42:36,427 --> 00:42:38,135
Faktisk tror nu
om en computer, også.

916
00:42:38,135 --> 00:42:40,824
Det kan kun se på måske en,
måske to ting på once--

917
00:42:40,824 --> 00:42:43,240
og faktisk kun én ting
på et tidspunkt, men det kan i det mindste

918
00:42:43,240 --> 00:42:45,790
se på en ting derefter
næste ting lige ved siden af ​​den.

919
00:42:45,790 --> 00:42:47,380
>> Så er disse i orden?

920
00:42:47,380 --> 00:42:48,032
Selvfølgelig ikke.

921
00:42:48,032 --> 00:42:48,740
Så ved du hvad?

922
00:42:48,740 --> 00:42:51,020
Hvorfor vi ikke tage barnet
trin fastsættelse dette problem

923
00:42:51,020 --> 00:42:53,410
stedet for at gøre disse fancy
algoritmer som Ben, hvor

924
00:42:53,410 --> 00:42:56,440
han slags fastsættelse det ved
looping gennem listen

925
00:42:56,440 --> 00:42:59,670
stedet for at gøre, hvad jeg gjorde, hvor
Jeg lige slags fast det, som vi går?

926
00:42:59,670 --> 00:43:03,650
Lad os bare bogstaveligt nedbryde
begrebet order-- nummerorden,

927
00:43:03,650 --> 00:43:06,990
kalde det hvad du want--
ind i disse parvise sammenligninger.

928
00:43:06,990 --> 00:43:07,590
>> Fire og én.

929
00:43:07,590 --> 00:43:09,970
Er det den rigtige rækkefølge?

930
00:43:09,970 --> 00:43:11,310
Så lad os ordne det.

931
00:43:11,310 --> 00:43:14,700
One og fire, og derefter
vi bare kopiere det.

932
00:43:14,700 --> 00:43:15,560
Okay, godt.

933
00:43:15,560 --> 00:43:17,022
Jeg fast én og fire.

934
00:43:17,022 --> 00:43:18,320
Tre og to?

935
00:43:18,320 --> 00:43:18,820
Ingen.

936
00:43:18,820 --> 00:43:21,690
Lad mine ord matcher mine fingre.

937
00:43:21,690 --> 00:43:23,695
Fire og tre?

938
00:43:23,695 --> 00:43:27,930
>> Det er ikke i orden, så jeg har tænkt mig
at gøre én, tre, fire, to.

939
00:43:27,930 --> 00:43:28,680
Ok godt.

940
00:43:28,680 --> 00:43:32,310
Nu fire og to?

941
00:43:32,310 --> 00:43:33,370
Vi er nødt til at løse dette, også.

942
00:43:33,370 --> 00:43:36,700
Så en, tre, to, fire.

943
00:43:36,700 --> 00:43:39,820
Så er det sorteret?

944
00:43:39,820 --> 00:43:43,170
Nej, men er det tættere på sorteres?

945
00:43:43,170 --> 00:43:48,930
>> Det er, fordi vi fast dette
fejl, vi fast denne fejl,

946
00:43:48,930 --> 00:43:50,370
og vi fast denne fejl.

947
00:43:50,370 --> 00:43:52,420
Så vi fast tre fejltagelser velsagtens.

948
00:43:52,420 --> 00:43:58,100
Stadig ikke rigtig ser sorterede, men
det objektivt tættere på sorterede

949
00:43:58,100 --> 00:44:00,080
fordi vi fast nogle af disse fejl.

950
00:44:00,080 --> 00:44:02,047
>> Nu hvad gør jeg nu?

951
00:44:02,047 --> 00:44:03,630
Jeg slags nået enden af ​​listen.

952
00:44:03,630 --> 00:44:05,680
Jeg syntes at have fast
alle de fejl, men nej.

953
00:44:05,680 --> 00:44:08,510
Fordi i denne sag, nogle numre
kunne have boblet op tættere

954
00:44:08,510 --> 00:44:10,410
til andre numre,
er stadig ude af drift.

955
00:44:10,410 --> 00:44:12,951
Så lad os gøre det igen, og jeg vil
bare gøre det på plads denne gang.

956
00:44:12,951 --> 00:44:14,170
One og tre?

957
00:44:14,170 --> 00:44:14,720
Det er fint.

958
00:44:14,720 --> 00:44:16,070
Tre og to?

959
00:44:16,070 --> 00:44:17,560
Selvfølgelig nej, så lad os ændre det.

960
00:44:17,560 --> 00:44:19,160
Så to, tre.

961
00:44:19,160 --> 00:44:21,340
Tre og fire?

962
00:44:21,340 --> 00:44:24,370
Og lad os nu bare være
især pedantisk her.

963
00:44:24,370 --> 00:44:26,350
Er det sorteret?

964
00:44:26,350 --> 00:44:29,280
Du mennesker ved, at det sorteres.

965
00:44:29,280 --> 00:44:30,400
>> Jeg skal prøve igen.

966
00:44:30,400 --> 00:44:31,900
Så Olivia foreslår jeg prøve igen.

967
00:44:31,900 --> 00:44:32,530
Hvorfor?

968
00:44:32,530 --> 00:44:35,810
Fordi en computer ikke har
den luksus af vores menneskelige øjne

969
00:44:35,810 --> 00:44:38,080
af bare forbigående tilbage-- OK, jeg færdig.

970
00:44:38,080 --> 00:44:41,610
Hvordan computeren bestemme
at listen nu sorteres?

971
00:44:41,610 --> 00:44:44,590
Mekanisk.

972
00:44:44,590 --> 00:44:47,650
>> Jeg skal gå igennem
en gang mere, og kun hvis jeg

973
00:44:47,650 --> 00:44:51,190
ikke gør / finde nogen fejl kan jeg
derefter konkludere som computeren, jep,

974
00:44:51,190 --> 00:44:51,980
vi er gode til at gå.

975
00:44:51,980 --> 00:44:54,850
Så en og to, to og
tre, tre og fire.

976
00:44:54,850 --> 00:44:58,030
Nu kan jeg endeligt sige dette er
sorteres, fordi jeg ikke foretages ændringer.

977
00:44:58,030 --> 00:45:01,940
Nu ville det være en fejl, og bare
dum hvis jeg, computeren

978
00:45:01,940 --> 00:45:05,640
stillede de samme spørgsmål igen
forventer forskellige svar.

979
00:45:05,640 --> 00:45:07,110
Bør ikke ske.

980
00:45:07,110 --> 00:45:08,600
>> Og så nu listen er sorteret.

981
00:45:08,600 --> 00:45:12,630
Desværre driftstid
denne algoritme er også N potens.

982
00:45:12,630 --> 00:45:13,130
Hvorfor?

983
00:45:13,130 --> 00:45:19,520
Fordi du har n tal, og i
værste tilfælde du nødt til at flytte n tal

984
00:45:19,520 --> 00:45:23,637
n gange, fordi du er nødt til at holde ud
tilbage til at kontrollere og potentielt fastsætte

985
00:45:23,637 --> 00:45:24,220
disse numre.

986
00:45:24,220 --> 00:45:26,280
Og vi kan gøre en mere
formel analyse, også.

987
00:45:26,280 --> 00:45:29,530
>> Så dette er alle at sige, vi har taget
tre forskellige tilgange, en

988
00:45:29,530 --> 00:45:32,210
af dem straks intuitiv
off bat fra Ben

989
00:45:32,210 --> 00:45:35,170
til min foreslåede indsættelse
slags til denne ene

990
00:45:35,170 --> 00:45:38,540
hvor du slags glemme
skoven for bare træer oprindeligt.

991
00:45:38,540 --> 00:45:41,760
Men så hvis du tager et skridt tilbage,
voila, vi har rettet sortering begreb.

992
00:45:41,760 --> 00:45:43,824
Så dette er, tør sige,
et lavere niveau måske

993
00:45:43,824 --> 00:45:45,740
end nogle af de andre
algoritmer, men lad os

994
00:45:45,740 --> 00:45:48,550
se, om vi ikke kan visualisere
disse ved hjælp af dette.

995
00:45:48,550 --> 00:45:51,450
>> Så dette er nogle nice
software, at nogen

996
00:45:51,450 --> 00:45:56,110
skrev hjælp farverige barer, der er
kommer til at gøre følgende for os.

997
00:45:56,110 --> 00:45:57,736
Hver af disse stænger repræsenterer et tal.

998
00:45:57,736 --> 00:46:00,026
Taller baren, jo større
nummeret, mindre bar,

999
00:46:00,026 --> 00:46:00,990
jo færre.

1000
00:46:00,990 --> 00:46:05,880
Så ideelt set ønsker vi en dejlig pyramide
hvor det begynder lille og får store,

1001
00:46:05,880 --> 00:46:08,330
og det ville betyde, at
disse stænger er sorteret.

1002
00:46:08,330 --> 00:46:11,200
Så jeg har tænkt mig at gå videre og vælge,
for eksempel, Ben algoritme

1003
00:46:11,200 --> 00:46:13,990
first-- udvælgelse slags.

1004
00:46:13,990 --> 00:46:16,220
>> Og mærke til, hvad det gør.

1005
00:46:16,220 --> 00:46:18,670
Den måde, de har valgt at
visualisere denne algoritme

1006
00:46:18,670 --> 00:46:22,090
er, at, ligesom jeg var
gå gennem min liste,

1007
00:46:22,090 --> 00:46:24,710
dette program er at gå
gennem sin liste over numre,

1008
00:46:24,710 --> 00:46:28,160
fremhæver i pink hver
nummer, som det er at se på.

1009
00:46:28,160 --> 00:46:32,360
Og hvad er ved at ske lige nu?

1010
00:46:32,360 --> 00:46:35,154
>> Det mindste tal, der
I eller Ben fandt pludselig

1011
00:46:35,154 --> 00:46:36,820
bliver flyttet til begyndelsen af ​​listen.

1012
00:46:36,820 --> 00:46:40,037
Og varsel, de gjorde evict
det nummer, der var der,

1013
00:46:40,037 --> 00:46:41,120
og det er helt fint.

1014
00:46:41,120 --> 00:46:42,600
Jeg fik ikke ind i denne detaljeringsgrad.

1015
00:46:42,600 --> 00:46:44,308
Men vi har brug for at sætte
dette nummer eller andet sted,

1016
00:46:44,308 --> 00:46:47,775
så vi lige flyttet det til
åben plet, der blev oprettet.

1017
00:46:47,775 --> 00:46:49,900
Så jeg har tænkt mig at fremskynde denne
op, fordi det ellers

1018
00:46:49,900 --> 00:46:51,871
bliver meget trættende hurtigt.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animation fart- der vi gå.

1021
00:46:58,600 --> 00:47:01,850
Så nu samme princip
Jeg anvender, men du

1022
00:47:01,850 --> 00:47:06,540
kan begynde at føle den algoritme, hvis du
vil, eller se det lidt mere klart.

1023
00:47:06,540 --> 00:47:13,190
Og denne algoritme har den virkning,
vælge den næste mindste element,

1024
00:47:13,190 --> 00:47:16,422
så du vil begynde at
se det rampe op til venstre.

1025
00:47:16,422 --> 00:47:19,130
Og på hver iteration, da jeg
foreslået, det gør lidt mindre arbejde.

1026
00:47:19,130 --> 00:47:21,921
Det behøver ikke at gå hele vejen
tilbage til den venstre ende af listen,

1027
00:47:21,921 --> 00:47:23,900
fordi den allerede
kender dem sorteres.

1028
00:47:23,900 --> 00:47:28,129
Så den slags føles ligesom det er
accelererende, selv om hvert trin er

1029
00:47:28,129 --> 00:47:29,420
idet den samme mængde tid.

1030
00:47:29,420 --> 00:47:31,600
Der er bare færre trin tilbage.

1031
00:47:31,600 --> 00:47:35,240
Og nu kan du slags føler
algoritme oprydning i slutningen af ​​det,

1032
00:47:35,240 --> 00:47:37,040
og faktisk nu er det ordnet.

1033
00:47:37,040 --> 00:47:41,620
>> Så indsættelsessortering er alle gjort.

1034
00:47:41,620 --> 00:47:43,600
Jeg har brug for at re-randomisere array.

1035
00:47:43,600 --> 00:47:45,940
Og opdager jeg kan bare
holde randomisering det,

1036
00:47:45,940 --> 00:47:50,630
og vi får en tilnærmelse af
den samme fremgangsmåde, indsættelsessortering.

1037
00:47:50,630 --> 00:47:55,050
Lad mig bremse den ned til her.

1038
00:47:55,050 --> 00:47:56,915
Lad os starte at over.

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
>> Lad os springe fire.

1042
00:48:02,410 --> 00:48:03,200
Sådan der.

1043
00:48:03,200 --> 00:48:04,190
Randomisere de array.

1044
00:48:04,190 --> 00:48:05,555
Og her go-- vi indsættelsessortering.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Spil.

1047
00:48:12,800 --> 00:48:17,280
Bemærk at det er behandling af hver enkelt
element det støder det samme,

1048
00:48:17,280 --> 00:48:20,282
men hvis det tilhører i
det forkerte sted varsel

1049
00:48:20,282 --> 00:48:21,740
alt det arbejde, der skal ske.

1050
00:48:21,740 --> 00:48:24,700
Vi er nødt til at holde skiftende mere
og flere elementer for at gøre plads

1051
00:48:24,700 --> 00:48:27,340
for den, vi ønsker at sætte på plads.

1052
00:48:27,340 --> 00:48:30,740
>> Så vi fokuserer på
venstre ende af kun listen.

1053
00:48:30,740 --> 00:48:34,460
Bemærker vi har ikke engang kigget at-- vi
har ikke fremhævet i lyserødt noget

1054
00:48:34,460 --> 00:48:35,610
til højre.

1055
00:48:35,610 --> 00:48:38,180
Vi er bare beskæftiger sig med
de problemer, som vi går,

1056
00:48:38,180 --> 00:48:40,430
men vi er ved at oprette en masse
arbejde for os selv endnu.

1057
00:48:40,430 --> 00:48:44,410
Og så hvis vi fremskynde dette op
nu at løbe til ende,

1058
00:48:44,410 --> 00:48:46,210
det har en anden føler for det faktisk.

1059
00:48:46,210 --> 00:48:50,150
Det er bare at fokusere på den venstre ende, men
gøre lidt mere arbejde som needed--

1060
00:48:50,150 --> 00:48:53,230
slags udjævning tingene
overstået, fastsættelse ting,

1061
00:48:53,230 --> 00:48:58,350
men beskæftiger sig i sidste ende med
hvert element en ad gangen

1062
00:48:58,350 --> 00:49:07,740
indtil vi får til-- godt, vi
ved alle, hvordan det vil ende,

1063
00:49:07,740 --> 00:49:09,700
så det er lidt underwhelming måske.

1064
00:49:09,700 --> 00:49:12,830
>> Men listen i end--
spoiler-- vil blive sorteret.

1065
00:49:12,830 --> 00:49:15,300
Så lad os se på en sidste.

1066
00:49:15,300 --> 00:49:16,840
Vi kan ikke bare springe nu.

1067
00:49:16,840 --> 00:49:18,000
Vi er der næsten.

1068
00:49:18,000 --> 00:49:19,980
To til at gå, en til at gå.

1069
00:49:19,980 --> 00:49:22,680
Og voila.

1070
00:49:22,680 --> 00:49:23,450
Fremragende.

1071
00:49:23,450 --> 00:49:27,220
>> Så lad os nu gøre et sidste,
re-randomisering med boblesortering.

1072
00:49:27,220 --> 00:49:31,690
Og bemærke her, især hvis jeg langsomt det
ned, betyder det holde swooping igennem.

1073
00:49:31,690 --> 00:49:36,830
Men bemærk det bare gør parvis
comparisons-- slags lokale løsninger.

1074
00:49:36,830 --> 00:49:39,050
Men så snart vi kommer til
enden af ​​listen i pink,

1075
00:49:39,050 --> 00:49:40,690
hvad der kommer til at ske igen?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ja, det kommer til at have til
starte forfra, fordi den kun

1078
00:49:46,830 --> 00:49:49,870
faste parvise fejltagelser.

1079
00:49:49,870 --> 00:49:53,120
Og som kunne have afsløret endnu andre.

1080
00:49:53,120 --> 00:49:58,950
Og så hvis du fremskynde det op, vil du
se, meget som navnet antyder,

1081
00:49:58,950 --> 00:50:01,870
den mindre elements-- eller rettere,
de større elements-- er begyndt

1082
00:50:01,870 --> 00:50:03,740
at boble op til toppen, hvis du vil.

1083
00:50:03,740 --> 00:50:07,380
Og de mindre elementer er
begynder at boble ned til venstre.

1084
00:50:07,380 --> 00:50:10,780
Og ja, der er slags
den visuelle effekt samt.

1085
00:50:10,780 --> 00:50:17,150
Og så dette vil ende med efterbehandling
i en meget lignende måde, også.

1086
00:50:17,150 --> 00:50:19,160
>> Vi behøver ikke at bo
på denne særlige én.

1087
00:50:19,160 --> 00:50:21,010
Lad mig åbne det nu, også.

1088
00:50:21,010 --> 00:50:24,040
Der er et par andre sortering algoritmer
i verden, hvoraf nogle få

1089
00:50:24,040 --> 00:50:25,580
fanges her.

1090
00:50:25,580 --> 00:50:29,960
Og især for elever, der ikke er
nødvendigvis visuel eller matematisk,

1091
00:50:29,960 --> 00:50:31,930
som vi gjorde før, kan vi
også gøre dette audially

1092
00:50:31,930 --> 00:50:34,210
hvis vi knytte en lyd med dette.

1093
00:50:34,210 --> 00:50:36,990
Og bare for sjov, her er en
par forskellige algoritmer,

1094
00:50:36,990 --> 00:50:40,950
og en af ​​dem i særdeleshed du er
kommer til at lægge mærke til, kaldes "merge slags."

1095
00:50:40,950 --> 00:50:43,250
>> Det er faktisk en fundamentalt
bedre algoritme,

1096
00:50:43,250 --> 00:50:45,860
således at mergesort, en af
dem, du er ved at se,

1097
00:50:45,860 --> 00:50:49,170
er ikke rækkefølgen af ​​n potens.

1098
00:50:49,170 --> 00:50:57,280
Det er på rækkefølgen af ​​n gange logge af
n, som er faktisk mindre og dermed

1099
00:50:57,280 --> 00:50:58,940
hurtigere end de andre tre.

1100
00:50:58,940 --> 00:51:00,670
Og der er en anden par
fjollet dem, vi vil se.

1101
00:51:00,670 --> 00:51:01,933
>> Så her går vi med nogle lyd.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Dette er indsættelsessortering, så igen
det er bare beskæftiger sig med elementerne

1104
00:51:10,490 --> 00:51:13,420
som de kommer.

1105
00:51:13,420 --> 00:51:17,180
Dette er boblesortering, så det er
overvejer dem parvis ad gangen.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Og igen, de største elementer
er gennemstrømning op til toppen.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Næste op udvælgelse slags.

1110
00:51:41,710 --> 00:51:45,420
Dette er Ben algoritme, hvor
igen han vælge iterativt

1111
00:51:45,420 --> 00:51:46,843
den næstmindste element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Og igen, nu kan du virkelig høre, at
det er hurtigere, men kun i det omfang

1114
00:51:53,900 --> 00:51:58,230
som det gør mindre og mindre
arbejde på hver iteration.

1115
00:51:58,230 --> 00:52:04,170
Dette er den hurtigere en, mergesort,
som er sortering klynger af numre

1116
00:52:04,170 --> 00:52:05,971
sammen og derefter kombinere dem.

1117
00:52:05,971 --> 00:52:07,720
Så look-- venstre
halvdelen er allerede sorteret.

1118
00:52:07,720 --> 00:52:14,165
>> Nu er det sortering den højre halvdel, og
nu det kommer til at kombinere dem i én.

1119
00:52:14,165 --> 00:52:19,160
Dette er noget, der hedder "Gnome slags."

1120
00:52:19,160 --> 00:52:23,460
Og du kan slags se, at
det går frem og tilbage,

1121
00:52:23,460 --> 00:52:27,950
fastsættelse arbejde en lille smule her og
der, før det fortsætter til nyt arbejde.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Og det er det.

1124
00:52:33,692 --> 00:52:36,400
Der er en anden slags, som er
virkelig bare til akademiske formål,

1125
00:52:36,400 --> 00:52:40,980
kaldet "dumme slags", som tager
dine data, sorterer det tilfældigt,

1126
00:52:40,980 --> 00:52:43,350
og kontrollerer derefter, hvis det er sorteret.

1127
00:52:43,350 --> 00:52:47,880
Og hvis det ikke er, det re-sorterer det
tilfældigt, tjekker, om det er sorteret,

1128
00:52:47,880 --> 00:52:49,440
og hvis ikke gentager.

1129
00:52:49,440 --> 00:52:52,660
Og i teorien, probalistisk
dette vil fuldføre,

1130
00:52:52,660 --> 00:52:54,140
men efter ganske lidt tid.

1131
00:52:54,140 --> 00:52:56,930
Det er ikke den mest
effektive af algoritmer.

1132
00:52:56,930 --> 00:53:02,550
Så spørgsmål om dem,
særlige algoritmer eller noget

1133
00:53:02,550 --> 00:53:04,720
relateret, også?

1134
00:53:04,720 --> 00:53:09,430
>> Nå, lad os nu drille hinanden, hvad alle
disse linjer er, at jeg har været tegning

1135
00:53:09,430 --> 00:53:15,090
og hvad jeg går ud af computeren
kan gøre under emhætten.

1136
00:53:15,090 --> 00:53:18,650
Jeg vil hævde, at alle disse tal
Jeg holder drawing-- de behøver for at få

1137
00:53:18,650 --> 00:53:21,330
gemt et sted i hukommelsen.

1138
00:53:21,330 --> 00:53:24,130
Vi vil slippe af med denne fyr nu, også.

1139
00:53:24,130 --> 00:53:30,110
>> Så et stykke hukommelse i en
computer-- så RAM DIMM er

1140
00:53:30,110 --> 00:53:35,480
hvad vi søgte efter i går, dual
Inline Memory module-- ser sådan ud.

1141
00:53:35,480 --> 00:53:39,370
Og hver af disse små sorte chips
er nogle antal byte, typisk.

1142
00:53:39,370 --> 00:53:44,380
Og så guld ben er ligesom
ledninger, der forbinder den til computeren,

1143
00:53:44,380 --> 00:53:47,521
og den grønne silicium bord er bare
hvad der holder alting sammen.

1144
00:53:47,521 --> 00:53:48,770
Så hvad betyder det egentlig?

1145
00:53:48,770 --> 00:53:53,180
Hvis jeg slags tegne samme billede,
Lad os antage for enkelhed

1146
00:53:53,180 --> 00:53:55,280
at denne DIMM, dual
inline hukommelsesmodul,

1147
00:53:55,280 --> 00:54:00,530
er en gigabyte RAM, en gigabyte
hukommelse, hvilket er hvor mange bytes alt?

1148
00:54:00,530 --> 00:54:02,100
En gigabyte er, hvor mange bytes?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Mere end det.

1151
00:54:06,030 --> 00:54:09,960
1124 er kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega er millioner.

1153
00:54:11,730 --> 00:54:14,570
Giga er en milliard.

1154
00:54:14,570 --> 00:54:15,070
>> Er jeg lyver?

1155
00:54:15,070 --> 00:54:16,670
Kan vi selv læse etiketten?

1156
00:54:16,670 --> 00:54:19,920
Dette er faktisk 128
gigabyte, så det er mere.

1157
00:54:19,920 --> 00:54:22,130
Men vi vil lade dette
er blot én gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Så det betyder, at der er en milliard
bytes af hukommelse til rådighed for mig

1159
00:54:25,640 --> 00:54:29,770
eller 8 milliarder bits, men vi vil
at tale i form af bytes nu,

1160
00:54:29,770 --> 00:54:30,750
Bevæger sig fremad.

1161
00:54:30,750 --> 00:54:36,330
>> Så hvad det betyder er det er
én byte, det er en anden byte,

1162
00:54:36,330 --> 00:54:38,680
det er en anden byte,
og hvis vi virkelig ønskede

1163
00:54:38,680 --> 00:54:43,280
at være specifik vi skulle
tegne en milliard små firkanter.

1164
00:54:43,280 --> 00:54:44,320
Men hvad betyder det?

1165
00:54:44,320 --> 00:54:46,420
Nå, lad mig bare zoome
i på dette billede.

1166
00:54:46,420 --> 00:54:50,900
Hvis jeg har noget, der ser
som dette nu, det er fire bytes.

1167
00:54:50,900 --> 00:54:53,710
>> Og så jeg kunne sætte fire numre her.

1168
00:54:53,710 --> 00:54:54,990
En to tre fire.

1169
00:54:54,990 --> 00:55:00,170
Eller jeg kunne sætte fire bogstaver eller symboler.

1170
00:55:00,170 --> 00:55:02,620
"Hej!" kunne gå lige der,
fordi hver af bogstaverne,

1171
00:55:02,620 --> 00:55:04,370
vi diskuterede tidligere,
kunne være repræsenteret

1172
00:55:04,370 --> 00:55:06,650
med otte bit eller ASCII eller en byte.

1173
00:55:06,650 --> 00:55:09,370
Så med andre ord kan du
sætte 8 milliarder ting inde

1174
00:55:09,370 --> 00:55:11,137
af denne ene pind af hukommelse.

1175
00:55:11,137 --> 00:55:14,345
Nu hvad betyder det at sætte tingene tilbage
til tilbage til tilbage i hukommelsen som denne?

1176
00:55:14,345 --> 00:55:17,330
Det er, hvad en programmør
ville kalde en "array."

1177
00:55:17,330 --> 00:55:21,250
I et computerprogram, tror du ikke
om den underliggende hardware, per se.

1178
00:55:21,250 --> 00:55:24,427
Du tror bare på dig selv som havende
adgang til en milliard bytes alt,

1179
00:55:24,427 --> 00:55:26,010
og du kan noget, du vil med det.

1180
00:55:26,010 --> 00:55:27,880
Men for nemheds skyld
det er generelt anvendelig

1181
00:55:27,880 --> 00:55:31,202
at holde din hukommelse højre
ved siden af ​​hinanden på denne måde.

1182
00:55:31,202 --> 00:55:33,660
Så hvis jeg zoome ind på denne--
fordi vi bestemt ikke gå

1183
00:55:33,660 --> 00:55:39,310
at tegne en milliard små squares--
Lad os antage, at dette board repræsenterer

1184
00:55:39,310 --> 00:55:40,610
at pind af hukommelse nu.

1185
00:55:40,610 --> 00:55:43,800
Og jeg vil bare trække så mange som min
markør ender med at give mig her.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Så nu har vi en pind
hukommelse på tavlen

1188
00:55:52,300 --> 00:55:56,400
der er har en, to, tre, fire, fem,
seks, en, to, tre, fire, fem, seks,

1189
00:55:56,400 --> 00:56:01,130
seven-- så 42 bytes af
hukommelse på den totale skærmen.

1190
00:56:01,130 --> 00:56:01,630
Tak.

1191
00:56:01,630 --> 00:56:02,838
Ja, gjorde min aritmetiske højre.

1192
00:56:02,838 --> 00:56:05,120
Så 42 bytes af hukommelse her.

1193
00:56:05,120 --> 00:56:06,660
Så hvad betyder det egentlig?

1194
00:56:06,660 --> 00:56:09,830
Tja, en computer programmør
ville faktisk generelt

1195
00:56:09,830 --> 00:56:12,450
tænke på denne hukommelse som adresserbare.

1196
00:56:12,450 --> 00:56:16,630
Med andre ord, hver enkelt af disse
steder i hukommelsen, i hardware,

1197
00:56:16,630 --> 00:56:18,030
har en unik adresse.

1198
00:56:18,030 --> 00:56:22,020
>> Det er ikke så kompliceret som One Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
I stedet er det bare et tal.

1200
00:56:23,830 --> 00:56:27,930
Dette er byte tallet nul, er dette
en, dette er to, er det tre,

1201
00:56:27,930 --> 00:56:30,327
og dette er 41.

1202
00:56:30,327 --> 00:56:30,910
Vent et øjeblik.

1203
00:56:30,910 --> 00:56:32,510
Jeg troede, jeg sagde 42 for et øjeblik siden.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Jeg begyndte at tælle på nul,
så det er faktisk korrekt.

1206
00:56:37,772 --> 00:56:40,980
Nu har vi ikke til rent faktisk at trække det
som et gitter, og hvis du tegner det som et gitter

1207
00:56:40,980 --> 00:56:43,520
Jeg tror tingene faktisk
få en smule misvisende.

1208
00:56:43,520 --> 00:56:46,650
Hvad en programmør ville,
i hans eller hendes eget sind,

1209
00:56:46,650 --> 00:56:50,310
generelt tænker på denne
hukommelse som er ligesom et bånd,

1210
00:56:50,310 --> 00:56:53,340
som et stykke malertape
der bare bliver ved og ved for evigt

1211
00:56:53,340 --> 00:56:54,980
eller indtil du løber tør for hukommelse.

1212
00:56:54,980 --> 00:56:59,200
Så en mere almindelig måde at trække
og bare tænke på hukommelse

1213
00:56:59,200 --> 00:57:03,710
ville være, at det er byte nul, et,
to, tre, og derefter prik, prik, prik.

1214
00:57:03,710 --> 00:57:07,650
Og du har 42 sådanne bytes alt, selv
selvom fysisk det måske faktisk

1215
00:57:07,650 --> 00:57:09,480
være noget mere som denne.

1216
00:57:09,480 --> 00:57:12,850
>> Så hvis du nu tænker på din
hukommelse som dette, ligesom et bånd,

1217
00:57:12,850 --> 00:57:17,640
dette er hvad en programmør igen
ville kalde en vifte af hukommelse.

1218
00:57:17,640 --> 00:57:20,660
Og når du vil rent faktisk gemme
noget i en computers hukommelse,

1219
00:57:20,660 --> 00:57:23,290
du generelt gør gemme ting
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Så vi har talt om tal.

1221
00:57:25,010 --> 00:57:30,880
Og når jeg ønskede at løse problemer
ligesom fire, en, tre, to,

1222
00:57:30,880 --> 00:57:33,820
selvom jeg bare tegne
kun de numre, fire, en, tre,

1223
00:57:33,820 --> 00:57:39,490
to på bordet, computeren ville
virkelig har denne opsætning i hukommelsen.

1224
00:57:39,490 --> 00:57:43,347
>> Og hvad ville være ved siden af
to i computerens hukommelse?

1225
00:57:43,347 --> 00:57:44,680
Tja, der er ikke noget svar på det.

1226
00:57:44,680 --> 00:57:45,770
Vi ved ikke rigtig.

1227
00:57:45,770 --> 00:57:48,200
Og så længe den
Computeren har ikke brug for det,

1228
00:57:48,200 --> 00:57:51,440
det behøver ikke at bekymre sig, hvad der er næste
til numrene det gør sig om.

1229
00:57:51,440 --> 00:57:55,130
Og da jeg sagde tidligere, at en computer
kan kun se på én adresse ad gangen,

1230
00:57:55,130 --> 00:57:56,170
dette er lidt hvorfor.

1231
00:57:56,170 --> 00:57:59,490
>> Ikke ulig en rekord
afspiller og et læsehoved

1232
00:57:59,490 --> 00:58:03,030
kun at kunne se på en bestemt
rille i en fysisk old-school rekord

1233
00:58:03,030 --> 00:58:06,500
på et tidspunkt, på lignende måde
kan en computer tak

1234
00:58:06,500 --> 00:58:09,810
til dens CPU og dens
Intel instruktionssæt,

1235
00:58:09,810 --> 00:58:12,480
blandt hvis instruktion
læses fra hukommelsen

1236
00:58:12,480 --> 00:58:15,590
eller gemme til memory-- en
computer kan kun se

1237
00:58:15,590 --> 00:58:19,210
på ét sted ad time--
undertiden en kombination af dem,

1238
00:58:19,210 --> 00:58:21,770
men egentlig bare ét sted ad gangen.

1239
00:58:21,770 --> 00:58:24,770
Så når vi lavede
disse forskellige algoritmer,

1240
00:58:24,770 --> 00:58:28,110
Jeg er ikke bare skrive i en
vacuum-- fire, en, tre, to.

1241
00:58:28,110 --> 00:58:30,849
Disse tal faktisk tilhører
et sted fysisk i hukommelsen.

1242
00:58:30,849 --> 00:58:32,890
Så der er lillebitte
transistorer eller anden form

1243
00:58:32,890 --> 00:58:35,840
af elektronik nedenunder
hætte lagring disse værdier.

1244
00:58:35,840 --> 00:58:40,460
>> Og i alt, hvor mange bit er
involveret lige nu, bare for at være klar?

1245
00:58:40,460 --> 00:58:45,580
Så dette er fire bytes, eller
nu er det 32 ​​bit alt.

1246
00:58:45,580 --> 00:58:49,280
Så der er faktisk 32 nuller og
dem komponere disse fire ting.

1247
00:58:49,280 --> 00:58:52,070
Der er endnu mere herovre, men
igen vi er ligeglad om det.

1248
00:58:52,070 --> 00:58:55,120
>> Så lad os nu spørge en anden
spørgsmål ved hjælp hukommelse,

1249
00:58:55,120 --> 00:58:57,519
fordi der ved udgangen
af dagen er i varians.

1250
00:58:57,519 --> 00:59:00,310
Ligegyldigt hvad vi kan gøre med
computeren, ved slutningen af ​​dagen

1251
00:59:00,310 --> 00:59:02,560
hardwaren er stadig den
samme under emhætten.

1252
00:59:02,560 --> 00:59:04,670
Hvordan ville jeg opbevare et ord i her?

1253
00:59:04,670 --> 00:59:09,710
Tja, et ord i en computer som
"Hej!" vil kunne lagres ligesom dette.

1254
00:59:09,710 --> 00:59:12,300
Og hvis du ønskede en længere
ord, kan du blot

1255
00:59:12,300 --> 00:59:19,120
overskrive det og sige noget
ligesom "hej" og butik, der her.

1256
00:59:19,120 --> 00:59:23,930
>> Og så også her denne contiguousness
er faktisk en fordel,

1257
00:59:23,930 --> 00:59:26,530
fordi en computer kan bare
læses fra højre mod venstre.

1258
00:59:26,530 --> 00:59:28,680
Men her er et spørgsmål.

1259
00:59:28,680 --> 00:59:33,480
I forbindelse med dette ord,
h-e-l-l-o, udråbstegn,

1260
00:59:33,480 --> 00:59:38,740
hvordan kan computeren ved, hvor den
ord begynder og hvor ordet ender?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
I forbindelse med numre,
hvordan gør computeren

1263
00:59:43,800 --> 00:59:48,396
hvor længe sekvensen af
tal er, eller hvor det starter?

1264
00:59:48,396 --> 00:59:50,270
Tja, det viser out--
og vi vil ikke gå for meget

1265
00:59:50,270 --> 00:59:54,970
i dette niveau af detail--
computere flytte ting rundt i hukommelsen

1266
00:59:54,970 --> 00:59:57,800
bogstaveligt i form af disse adresser.

1267
00:59:57,800 --> 01:00:02,080
Så i en computer, hvis du er
skrive kode til at gemme ting

1268
01:00:02,080 --> 01:00:05,800
ligesom ord, hvad du er
virkelig gør er at skrive

1269
01:00:05,800 --> 01:00:11,320
udtryk, der husker hvor i
computerens hukommelse disse ord er.

1270
01:00:11,320 --> 01:00:14,370
Så lad mig gøre en meget,
meget simpelt eksempel.

1271
01:00:14,370 --> 01:00:18,260
>> Jeg har tænkt mig at gå videre og
åbne op for en simpel tekst-program,

1272
01:00:18,260 --> 01:00:20,330
og jeg har tænkt mig at skabe
en fil kaldet hello.c.

1273
01:00:20,330 --> 01:00:22,849
De fleste af disse oplysninger, vi
vil ikke gå ind i detaljer,

1274
01:00:22,849 --> 01:00:25,140
men jeg har tænkt mig at skrive en
program i samme sprog,

1275
01:00:25,140 --> 01:00:31,140
C. Det er langt mere skræmmende,
Jeg vil hævde, end Scratch,

1276
01:00:31,140 --> 01:00:32,490
men det er meget ens i ånd.

1277
01:00:32,490 --> 01:00:34,364
I virkeligheden er disse krøllet
braces-- kan du slags

1278
01:00:34,364 --> 01:00:37,820
tænke på, hvad jeg lige gjorde, som dette.

1279
01:00:37,820 --> 01:00:39,240
>> Lad os gøre det, faktisk.

1280
01:00:39,240 --> 01:00:45,100
Når grønt flag klikkede,
gøre følgende.

1281
01:00:45,100 --> 01:00:50,210
Jeg ønsker at udskrive "Hej."

1282
01:00:50,210 --> 01:00:51,500
Så dette er nu pseudokode.

1283
01:00:51,500 --> 01:00:53,000
Jeg er lidt sløring linjerne.

1284
01:00:53,000 --> 01:00:56,750
I C, dette sprog jeg taler
om, denne linje print hej

1285
01:00:56,750 --> 01:01:01,940
faktisk bliver "printf" med
nogle parenteser og et semikolon.

1286
01:01:01,940 --> 01:01:03,480
>> Men det er nøjagtig samme idé.

1287
01:01:03,480 --> 01:01:06,730
Og denne meget brugervenligt
"Når grønne flag klikket" bliver

1288
01:01:06,730 --> 01:01:10,182
den langt mere mystiske "int main tomrum."

1289
01:01:10,182 --> 01:01:12,890
Og det har virkelig ingen kortlægning,
så jeg bare at ignorere det.

1290
01:01:12,890 --> 01:01:17,210
Men de krøllede parenteser er ligesom
buede puslespilsbrikker som denne.

1291
01:01:17,210 --> 01:01:18,700
>> Så du kan slags gætte.

1292
01:01:18,700 --> 01:01:22,357
Selv hvis du aldrig har programmeret før,
hvad betyder dette program sandsynligvis gøre?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Sandsynligvis udskriver hej
med et udråbstegn.

1295
01:01:28,000 --> 01:01:29,150
>> Så lad os prøve det.

1296
01:01:29,150 --> 01:01:30,800
Jeg har tænkt mig at gemme det.

1297
01:01:30,800 --> 01:01:34,000
Og det er, igen, en meget
gamle skole miljø.

1298
01:01:34,000 --> 01:01:35,420
Jeg kan ikke klikke, jeg kan ikke trække.

1299
01:01:35,420 --> 01:01:36,910
Jeg er nødt til at skrive kommandoer.

1300
01:01:36,910 --> 01:01:41,320
Så jeg vil køre mit program, så
Jeg kan gøre dette, ligesom hello.c.

1301
01:01:41,320 --> 01:01:42,292
Det er den fil, jeg løb.

1302
01:01:42,292 --> 01:01:43,500
Men vent, jeg mangler et trin.

1303
01:01:43,500 --> 01:01:46,470
Hvad gjorde vi siger, er en nødvendig
trin til et sprog som C?

1304
01:01:46,470 --> 01:01:49,470
Jeg har lige skrevet kilde
kode, men hvad skal jeg bruge?

1305
01:01:49,470 --> 01:01:50,670
Ja, jeg har brug for en compiler.

1306
01:01:50,670 --> 01:01:57,670
Så på min Mac her, jeg har en
program kaldet GCC, GNU C compiler,

1307
01:01:57,670 --> 01:02:03,990
som tillader mig at gøre denne-- tur
min kilde kode i, vil vi kalde det,

1308
01:02:03,990 --> 01:02:04,930
maskinkode.

1309
01:02:04,930 --> 01:02:10,180
>> Og jeg kan se, at,
igen, som følger, er disse

1310
01:02:10,180 --> 01:02:14,090
er de nuller og ettaller I bare
skabt ud fra min kildekode,

1311
01:02:14,090 --> 01:02:15,730
alle de nuller og ettaller.

1312
01:02:15,730 --> 01:02:17,770
Og hvis jeg vil køre
min program-- det sker

1313
01:02:17,770 --> 01:02:23,010
at blive kaldt a.out for
historiske reasons-- "Hej."

1314
01:02:23,010 --> 01:02:24,070
Jeg kan køre det igen.

1315
01:02:24,070 --> 01:02:25,690
Hej hej hej.

1316
01:02:25,690 --> 01:02:27,430
Og det ser ud til at virke.

1317
01:02:27,430 --> 01:02:31,000
>> Men det betyder et eller andet sted i min
computerens hukommelse er de ord

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, udråbstegn.

1319
01:02:35,279 --> 01:02:38,070
Og det viser sig, lige som en sidebemærkning,
hvad en computer ville typisk

1320
01:02:38,070 --> 01:02:40,550
gøre, så den ved, hvor
tingene begynder og end-- det er

1321
01:02:40,550 --> 01:02:42,460
vil sætte et særligt symbol her.

1322
01:02:42,460 --> 01:02:46,064
Og konventionen er at sætte
nummer nul ved slutningen af ​​et ord

1323
01:02:46,064 --> 01:02:48,230
så du ved, hvor det
faktisk afsluttes, så du

1324
01:02:48,230 --> 01:02:52,750
ikke holde udskrive mere og mere
tegn end du rent faktisk har til hensigt.

1325
01:02:52,750 --> 01:02:55,400
>> Men takeaway her, selv
selvom dette er temmelig mystisk,

1326
01:02:55,400 --> 01:02:58,140
er, at det er i sidste ende
relativt simpelt.

1327
01:02:58,140 --> 01:03:04,550
Du fik en slags tape, en tom
plads, hvor du kan skrive breve.

1328
01:03:04,550 --> 01:03:07,150
Du er simpelthen nødt til at have en
særligt symbol, som vilkårligt

1329
01:03:07,150 --> 01:03:10,316
tallet nul, for at sige ved udgangen af
dine ord, så computeren kender,

1330
01:03:10,316 --> 01:03:13,410
Åh, jeg skal stoppe udskrivningen, efter
Jeg ser udråbstegn.

1331
01:03:13,410 --> 01:03:16,090
Fordi den næste ting der
er en ASCII værdi på nul,

1332
01:03:16,090 --> 01:03:19,125
eller null karakter som
nogen ville kalde det.

1333
01:03:19,125 --> 01:03:21,500
Men der er lidt af et problem
her, og lad os vende tilbage

1334
01:03:21,500 --> 01:03:23,320
til tal for et øjeblik.

1335
01:03:23,320 --> 01:03:28,720
Antag, at jeg gør, i virkeligheden,
har en matrix af tal,

1336
01:03:28,720 --> 01:03:30,730
og antage, at
program jeg skriver, er

1337
01:03:30,730 --> 01:03:34,680
som en karakterbog for en lærer
og en lærere klasseværelse.

1338
01:03:34,680 --> 01:03:38,720
Og dette program giver ham eller hende
til at skrive i deres elevers score

1339
01:03:38,720 --> 01:03:39,960
på quizzer.

1340
01:03:39,960 --> 01:03:43,750
Og formoder, at den studerende får
100 på deres første quiz, måske

1341
01:03:43,750 --> 01:03:49,920
som en 80 på den næste, derefter en
75, derefter en 90 på den fjerde quiz.

1342
01:03:49,920 --> 01:03:54,150
>> Så på dette tidspunkt i historien,
arrayet er af størrelse fire.

1343
01:03:54,150 --> 01:03:58,470
Der er absolut mere hukommelse i
computer, men arrayet, så at sige,

1344
01:03:58,470 --> 01:04:00,350
er af størrelse fire.

1345
01:04:00,350 --> 01:04:06,060
Antag nu, at læreren ønsker
at tildele en femte quiz til klassen.

1346
01:04:06,060 --> 01:04:08,510
Tja, en af ​​de ting, han
eller hun vil have at gøre

1347
01:04:08,510 --> 01:04:10,650
er nu at gemme en ekstra værdi her.

1348
01:04:10,650 --> 01:04:15,490
Men hvis arrayet læreren
skabt i dette program er af størrelse for,

1349
01:04:15,490 --> 01:04:22,440
en af ​​problemet med et array er, at
du kan ikke bare holde tilføje til hukommelsen.

1350
01:04:22,440 --> 01:04:26,470
For hvad hvis en anden del af
Programmet har ordet "hej" lige der?

1351
01:04:26,470 --> 01:04:29,650
>> Med andre ord, kan min hukommelse være
bruges til noget i et program.

1352
01:04:29,650 --> 01:04:33,250
Og hvis i forvejen, jeg har skrevet i, hey,
Jeg vil indtaste fire quiz scores,

1353
01:04:33,250 --> 01:04:34,784
de kunne gå her og her.

1354
01:04:34,784 --> 01:04:37,700
Og hvis du pludselig skifter mening
senere og sige, at jeg vil have en femte quiz

1355
01:04:37,700 --> 01:04:40,872
score, kan du ikke bare
sætte det hvor du vil,

1356
01:04:40,872 --> 01:04:42,580
fordi det, hvis dette
hukommelse bliver brugt

1357
01:04:42,580 --> 01:04:45,990
for noget else-- et andet program
eller nogle andre træk ved programmet

1358
01:04:45,990 --> 01:04:46,910
at du kører?

1359
01:04:46,910 --> 01:04:50,650
Så du er nødt til at tænke på forhånd
hvordan du ønsker at gemme dine data,

1360
01:04:50,650 --> 01:04:54,480
fordi nu har du malet
dig ind i en digital hjørne.

1361
01:04:54,480 --> 01:04:57,280
>> Så lærer måske i stedet
sige, når du skriver et program

1362
01:04:57,280 --> 01:04:59,360
at lagre hans eller hendes
kvaliteter, ved du hvad?

1363
01:04:59,360 --> 01:05:04,180
Jeg vil anmode om,
når du skriver mit program,

1364
01:05:04,180 --> 01:05:12,070
at jeg ønsker nul, en, to, tre,
fire, fem, seks, otte kvaliteter alt.

1365
01:05:12,070 --> 01:05:15,320
Så en, to, tre, fire,
fem, seks, syv, otte.

1366
01:05:15,320 --> 01:05:18,612
Læreren kan bare over-allokere
hukommelse, når du skriver hans eller hendes program

1367
01:05:18,612 --> 01:05:19,570
og sige, ved du hvad?

1368
01:05:19,570 --> 01:05:22,236
Jeg kommer aldrig til at tildele mere
end otte quizzer i et semester.

1369
01:05:22,236 --> 01:05:23,130
Det er bare vanvittigt.

1370
01:05:23,130 --> 01:05:24,470
Jeg vil aldrig tildele det.

1371
01:05:24,470 --> 01:05:28,270
Så at denne måde, han eller hun har
fleksibilitet til at gemme elevernes resultater,

1372
01:05:28,270 --> 01:05:33,010
ligesom 75, 90, og måske en ekstra hvor
eleven fik ekstra kredit, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Men hvis læreren aldrig
bruger disse tre rum,

1374
01:05:36,130 --> 01:05:38,860
der er en intuitiv takeaway her.

1375
01:05:38,860 --> 01:05:41,410
Han eller hun bare spilde plads.

1376
01:05:41,410 --> 01:05:44,790
Så med andre ord, der er denne
fælles tradeoff i programmering

1377
01:05:44,790 --> 01:05:48,241
hvor du enten kan tildele
præcis så meget hukommelse som du ønsker,

1378
01:05:48,241 --> 01:05:51,490
opadrettede af som er, at du er super
efficient-- du ikke at være ødsel

1379
01:05:51,490 --> 01:05:54,640
på all-- men bagsiden af ​​medaljen, som
er, hvad hvis du ændrer mening, når

1380
01:05:54,640 --> 01:05:58,780
ved hjælp af programmet, som du vil gemme
flere data end du oprindeligt beregnet.

1381
01:05:58,780 --> 01:06:03,030
>> Så måske er løsningen, da
skrive dine programmer på en sådan måde

1382
01:06:03,030 --> 01:06:05,605
at de bruger mere hukommelse
end de faktisk har brug for.

1383
01:06:05,605 --> 01:06:07,730
Denne måde du ikke kommer
at løbe ind i det problem,

1384
01:06:07,730 --> 01:06:09,730
men du bliver spild.

1385
01:06:09,730 --> 01:06:12,960
Og jo mere hukommelse dit program bruger,
som vi diskuterede i går, jo mindre

1386
01:06:12,960 --> 01:06:15,410
hukommelse, der er til rådighed
for andre programmer,

1387
01:06:15,410 --> 01:06:18,790
jo før din computer kan bremse
ned på grund af virtuel hukommelse.

1388
01:06:18,790 --> 01:06:22,670
Og så den ideelle løsning kunne være, hvad?

1389
01:06:22,670 --> 01:06:24,610
>> Under-fordeling synes dårligt.

1390
01:06:24,610 --> 01:06:27,030
Over-fordeling synes dårligt.

1391
01:06:27,030 --> 01:06:31,120
Så hvad kunne være en bedre løsning?

1392
01:06:31,120 --> 01:06:32,390
Omfordeling.

1393
01:06:32,390 --> 01:06:33,590
Være mere dynamisk.

1394
01:06:33,590 --> 01:06:37,520
Må ikke tvinge dig selv til at vælge en
priori, i begyndelsen, hvad du ønsker.

1395
01:06:37,520 --> 01:06:41,370
Og bestemt ikke over-allokere,
lest du være spild.

1396
01:06:41,370 --> 01:06:45,770
>> Og så for at nå dette mål, vi
nødt til at kaste denne datastruktur,

1397
01:06:45,770 --> 01:06:48,100
så at sige, væk.

1398
01:06:48,100 --> 01:06:51,080
Og så hvad en programmør
vil typisk bruge

1399
01:06:51,080 --> 01:06:55,940
er noget, der hedder ikke en
matrix men en sammenkædet liste.

1400
01:06:55,940 --> 01:07:00,860
Med andre ord, vil han eller hun
begynde at tænke på deres hukommelse

1401
01:07:00,860 --> 01:07:05,280
som værende slags en form, som de
kan trække på følgende måde.

1402
01:07:05,280 --> 01:07:08,520
Hvis jeg ønsker at gemme et nummer i
en program-- så det er september

1403
01:07:08,520 --> 01:07:12,600
Jeg har givet mine elever en quiz; jeg vil
til at gemme de studerendes første quiz,

1404
01:07:12,600 --> 01:07:16,220
og de fik en 100 på it-- I
jeg vil bede min computer,

1405
01:07:16,220 --> 01:07:19,540
ved hjælp af det program, jeg har
skrevet, for én luns af hukommelse.

1406
01:07:19,540 --> 01:07:22,570
Og jeg har tænkt mig at gemme
nummer 100 i den, og det er det.

1407
01:07:22,570 --> 01:07:24,820
>> Så et par uger senere
når jeg får min anden quiz,

1408
01:07:24,820 --> 01:07:27,890
og det er tid til at skrive
i, at 90%, vil jeg

1409
01:07:27,890 --> 01:07:32,129
at spørge computeren, hey, computer,
kan jeg have en anden luns af hukommelse?

1410
01:07:32,129 --> 01:07:34,170
Det kommer til at give mig denne
tom luns af hukommelse.

1411
01:07:34,170 --> 01:07:39,370
Jeg har tænkt mig at sætte i antallet 90,
men i mit program på en eller other--

1412
01:07:39,370 --> 01:07:42,100
og vi vil ikke bekymre dig om
syntaksen for denne-- jeg har brug for

1413
01:07:42,100 --> 01:07:44,430
en eller anden måde kæde disse ting sammen.

1414
01:07:44,430 --> 01:07:47,430
Og jeg vil kæde dem sammen med
hvad der ligner en pil her.

1415
01:07:47,430 --> 01:07:50,050
>> Den tredje quiz, der kommer op,
Jeg har tænkt mig at sige, hey, computer,

1416
01:07:50,050 --> 01:07:51,680
give mig en anden luns af hukommelse.

1417
01:07:51,680 --> 01:07:54,660
Og jeg har tænkt mig at sætte ned
uanset hvad det var, ligesom 75,

1418
01:07:54,660 --> 01:07:56,920
og jeg er nødt til at kæde dette
sammen nu en eller anden måde.

1419
01:07:56,920 --> 01:08:00,290
Fjerde quiz kommer sammen, og måske
det er mod slutningen af ​​semestret.

1420
01:08:00,290 --> 01:08:03,140
Og ved dette punkt mit program
kan være ved hjælp af hukommelse

1421
01:08:03,140 --> 01:08:05,540
over det hele, hele fysisk.

1422
01:08:05,540 --> 01:08:08,170
Og så bare for spark, jeg er
vil trække denne ud

1423
01:08:08,170 --> 01:08:11,260
quiz-- Jeg glemmer, hvad det var; jeg
tror måske en 80 eller something--

1424
01:08:11,260 --> 01:08:12,500
vej herover.

1425
01:08:12,500 --> 01:08:15,920
>> Men det er fint, fordi billedligt
Jeg har tænkt mig at trække denne linje.

1426
01:08:15,920 --> 01:08:19,063
Med andre ord, i virkeligheden,
i computerens hardware,

1427
01:08:19,063 --> 01:08:20,979
den første score might
ender her, fordi det er

1428
01:08:20,979 --> 01:08:22,529
lige i starten af ​​semesteret.

1429
01:08:22,529 --> 01:08:25,810
Den næste kan ende her
fordi en smule tid der er gået

1430
01:08:25,810 --> 01:08:27,210
og programmet holder kører.

1431
01:08:27,210 --> 01:08:30,060
Den næste score, som var
en 75, måske herovre.

1432
01:08:30,060 --> 01:08:33,420
Og den sidste score kunne være
en 80, hvilket er over her.

1433
01:08:33,420 --> 01:08:38,729
>> Så i virkeligheden, fysisk, dette kan være
hvad computerens hukommelse ser ud.

1434
01:08:38,729 --> 01:08:41,569
Men dette er ikke en nyttig mental
paradigme for en computer programmør.

1435
01:08:41,569 --> 01:08:44,649
Hvorfor skal du pleje, hvor
dælen dine data er ender?

1436
01:08:44,649 --> 01:08:46,200
Du vil bare gemme data.

1437
01:08:46,200 --> 01:08:49,390
>> Dette er lidt ligesom vores diskussion
tidligere at trække terningen.

1438
01:08:49,390 --> 01:08:52,200
Hvorfor bekymrer du dig, hvad
vinklen er af terningen

1439
01:08:52,200 --> 01:08:53,740
og hvordan du skal slå til at trække det?

1440
01:08:53,740 --> 01:08:54,950
Du vil bare en terning.

1441
01:08:54,950 --> 01:08:57,359
På samme måde her, du
blot ønsker at karakterbog.

1442
01:08:57,359 --> 01:08:59,559
Du vil bare at tænke på
dette som en liste af tal.

1443
01:08:59,559 --> 01:09:01,350
Hvem bekymrer sig, hvordan det er
implementeres i hardware?

1444
01:09:01,350 --> 01:09:05,180
>> Så indvinding nu
er dette billede her.

1445
01:09:05,180 --> 01:09:07,580
Dette er en linket liste, som
en programmør ville kalde det,

1446
01:09:07,580 --> 01:09:10,640
det omfang du har en
liste, naturligvis af tal.

1447
01:09:10,640 --> 01:09:14,990
Men det er forbundet billedligt
ved hjælp af disse pile,

1448
01:09:14,990 --> 01:09:18,510
og alle disse pile are-- nedenunder
hætten, hvis du er nysgerrig,

1449
01:09:18,510 --> 01:09:23,210
minde om, at vores fysiske hardware har
adresser nul, en, to, tre, fire.

1450
01:09:23,210 --> 01:09:28,465
Alle disse pile er er ligesom et kort
eller retninger, hvor hvis 90 is-- nu

1451
01:09:28,465 --> 01:09:29,090
Jeg fik at tælle.

1452
01:09:29,090 --> 01:09:31,750
>> Nul, en, to, tre,
fire, fem, seks, syv.

1453
01:09:31,750 --> 01:09:35,640
Det ser ud til 90 er på
hukommelse adresse nummer syv.

1454
01:09:35,640 --> 01:09:38,460
Alle disse pile er er
som en lille lap papir

1455
01:09:38,460 --> 01:09:42,439
der er at give anvisninger til
program, der siger at følge dette kort

1456
01:09:42,439 --> 01:09:43,880
at komme til placering syv.

1457
01:09:43,880 --> 01:09:46,680
Og der vil du finde
studerendes anden quiz score.

1458
01:09:46,680 --> 01:09:52,100
I mellemtiden er den 75-- hvis jeg fortsætter dette,
dette er syv, otte, ni, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Denne anden pil bare repræsenterer
et kort til hukommelsesplacering 15.

1461
01:09:59,080 --> 01:10:02,550
Men igen, programmøren generelt gør
ikke bekymre sig om dette niveau af detaljer.

1462
01:10:02,550 --> 01:10:05,530
Og i de fleste hver programmering
sprog i dag, programmøren

1463
01:10:05,530 --> 01:10:10,490
vil ikke engang, hvor i hukommelsen
disse tal egentlig er.

1464
01:10:10,490 --> 01:10:14,830
Alt, hvad han eller hun har at bekymre sig om, er
at de på en måde er bundet sammen

1465
01:10:14,830 --> 01:10:18,390
i en datastruktur som denne.

1466
01:10:18,390 --> 01:10:21,580
>> Men det viser sig ikke
at få alt for teknisk.

1467
01:10:21,580 --> 01:10:27,430
Men bare fordi vi kan måske
råd til at have denne diskussion her,

1468
01:10:27,430 --> 01:10:33,630
antage, at vi revidere
dette problem her af et array.

1469
01:10:33,630 --> 01:10:35,780
Lad os se, om vi beklager går her.

1470
01:10:35,780 --> 01:10:42,950
Dette er 100, 90, 75, og 80.

1471
01:10:42,950 --> 01:10:44,980
>> Lad mig kort gøre denne påstand.

1472
01:10:44,980 --> 01:10:48,980
Dette er et array, og igen,
iøjnefaldende egenskab ved et array

1473
01:10:48,980 --> 01:10:52,400
er, at alle dine data er tilbage til
ryg mod ryg i memory-- bogstaveligt

1474
01:10:52,400 --> 01:10:56,830
én byte eller måske fire bytes,
nogle fast antal bytes væk.

1475
01:10:56,830 --> 01:11:00,710
I en sammenkædet liste, som vi kunne trække
som dette, under hætten, der

1476
01:11:00,710 --> 01:11:02,000
ved, hvor at ting er?

1477
01:11:02,000 --> 01:11:03,630
Det behøver ikke engang at flyde som dette.

1478
01:11:03,630 --> 01:11:06,050
Nogle af dataene kunne være
tilbage til venstre op dér.

1479
01:11:06,050 --> 01:11:07,530
Du behøver ikke engang kender.

1480
01:11:07,530 --> 01:11:15,430
>> Og så med et array, du har en
funktion kaldet random access.

1481
01:11:15,430 --> 01:11:20,570
Og hvad random access midler er
at computeren kan springe øjeblikkeligt

1482
01:11:20,570 --> 01:11:22,730
til enhver placering i et array.

1483
01:11:22,730 --> 01:11:23,580
Hvorfor?

1484
01:11:23,580 --> 01:11:26,000
Fordi computeren ved
at den første placering er

1485
01:11:26,000 --> 01:11:29,540
nul, et, to, og tre.

1486
01:11:29,540 --> 01:11:33,890
>> Og så hvis du ønsker at gå fra
dette element til det næste element,

1487
01:11:33,890 --> 01:11:36,099
du bogstaveligt talt, i
computers sind, bare tilføje en.

1488
01:11:36,099 --> 01:11:39,140
Hvis du ønsker at gå til det tredje element,
blot tilføje en-- næste element, bare

1489
01:11:39,140 --> 01:11:40,290
tilføje en.

1490
01:11:40,290 --> 01:11:42,980
Men i denne version
af historien, formoder

1491
01:11:42,980 --> 01:11:46,080
computeren er i øjeblikket på udkig
ved eller beskæftiger sig med nummer 100.

1492
01:11:46,080 --> 01:11:49,770
Hvordan du kommer til det næste
lønklasse i karakterbogen?

1493
01:11:49,770 --> 01:11:52,560
>> Du er nødt til at tage syv
trin, som er vilkårlig.

1494
01:11:52,560 --> 01:11:58,120
For at komme til den næste, skal du
tage yderligere otte trin for at komme til 15.

1495
01:11:58,120 --> 01:12:02,250
Med andre ord, det er ikke en
konstant afstand mellem tallene,

1496
01:12:02,250 --> 01:12:04,857
og så det bare tager den
computeren mere tid er det punkt.

1497
01:12:04,857 --> 01:12:06,940
Computeren har for at søge
gennem hukommelse for

1498
01:12:06,940 --> 01:12:08,990
at finde det, du leder efter.

1499
01:12:08,990 --> 01:12:14,260
>> Så mens et array tendens til at være en
hurtige data structure-- fordi du

1500
01:12:14,260 --> 01:12:17,610
kan bogstaveligt talt bare gøre simple aritmetiske
og få, hvor du vil ved at tilføje en,

1501
01:12:17,610 --> 01:12:21,300
til instance-- en sammenkædet liste,
du ofrer denne funktion.

1502
01:12:21,300 --> 01:12:24,020
Du kan ikke bare gå fra første
til anden til tredje til fjerde.

1503
01:12:24,020 --> 01:12:25,240
Du er nødt til at følge kortet.

1504
01:12:25,240 --> 01:12:28,160
Du er nødt til at tage flere skridt
at komme til de værdier, som

1505
01:12:28,160 --> 01:12:30,230
synes at være at tilføje en omkostning.

1506
01:12:30,230 --> 01:12:35,910
Så vi betaler en pris, men hvad var
den funktion, Dan søgte her?

1507
01:12:35,910 --> 01:12:38,110
Hvad betyder en linket liste
tilsyneladende tillade os at gøre,

1508
01:12:38,110 --> 01:12:40,240
som var oprindelsen til
denne historie?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Nøjagtig.

1511
01:12:43,830 --> 01:12:46,220
En dynamisk størrelse til den.

1512
01:12:46,220 --> 01:12:48,040
Vi kan tilføje til denne liste.

1513
01:12:48,040 --> 01:12:51,430
Vi kan endda skrumpe listen, så
at vi kun bruger så meget hukommelse

1514
01:12:51,430 --> 01:12:55,560
som vi rent faktisk ønsker, og så
vi er aldrig over-fordeling.

1515
01:12:55,560 --> 01:12:58,470
>> Nu bare for at være virkelig nit-betyder,
der er en skjult omkostning.

1516
01:12:58,470 --> 01:13:01,980
Så du skal ikke bare lade mig overbevise
dig, at dette er en overbevisende afvejning.

1517
01:13:01,980 --> 01:13:04,190
Der er en anden skjulte omkostninger her.

1518
01:13:04,190 --> 01:13:06,550
Fordelen, at være klar,
er, at vi får dynamik.

1519
01:13:06,550 --> 01:13:10,359
Hvis jeg vil et andet element, kan jeg bare
trække det og sætte et nummer derinde.

1520
01:13:10,359 --> 01:13:12,150
Og så kan jeg linke det
med et billede her,

1521
01:13:12,150 --> 01:13:14,970
mens herovre, igen, hvis jeg har
malede mig i et hjørne,

1522
01:13:14,970 --> 01:13:19,410
hvis noget andet er allerede bruger
hukommelsen her, jeg er ude af lykke.

1523
01:13:19,410 --> 01:13:21,700
Jeg har malet mig ind i hjørnet.

1524
01:13:21,700 --> 01:13:24,390
>> Men hvad er den skjulte
koste i dette billede?

1525
01:13:24,390 --> 01:13:27,690
Det er ikke kun det beløb,
tid, det tager

1526
01:13:27,690 --> 01:13:29,870
at gå fra her til her,
hvilket er syv trin, så

1527
01:13:29,870 --> 01:13:32,820
otte trin, hvilket er mere end én.

1528
01:13:32,820 --> 01:13:34,830
Hvad er en anden skjulte omkostninger?

1529
01:13:34,830 --> 01:13:35,440
Ikke bare tid.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Yderligere oplysninger er
nødvendigt for at nå dette billede.

1532
01:13:49,940 --> 01:13:53,210
>> Ja, det kort, de små papirlapper
papir, som jeg holder beskriver dem som.

1533
01:13:53,210 --> 01:13:55,650
Disse arrows-- de er ikke gratis.

1534
01:13:55,650 --> 01:13:57,660
En computer-- du kender
hvad en computer har.

1535
01:13:57,660 --> 01:13:58,790
Det har nuller og ettaller.

1536
01:13:58,790 --> 01:14:03,170
Hvis du ønsker at repræsentere en pil eller et
kort eller et nummer, du har brug for noget hukommelse.

1537
01:14:03,170 --> 01:14:05,950
Så den anden pris, du
betale for en forbundet liste,

1538
01:14:05,950 --> 01:14:09,070
en fælles computer science
ressource, er også plads.

1539
01:14:09,070 --> 01:14:11,710
>> Og faktisk så, så almindeligt,
blandt kompromiser

1540
01:14:11,710 --> 01:14:15,580
i at designe software engineering
systemer er tid og space--

1541
01:14:15,580 --> 01:14:18,596
er to af dine ingredienser, to
af dine mest kostbare ingredienser.

1542
01:14:18,596 --> 01:14:21,220
Dette koster mig mere tid
fordi jeg er nødt til at følge dette kort,

1543
01:14:21,220 --> 01:14:25,730
men det er også koster mig mere plads
fordi jeg nødt til at holde dette kort rundt.

1544
01:14:25,730 --> 01:14:28,730
Så det håb, som vi har slags
drøftede i går og i dag,

1545
01:14:28,730 --> 01:14:31,720
er, at fordelene
vil opveje omkostningerne.

1546
01:14:31,720 --> 01:14:33,870
>> Men der er ingen oplagte løsning her.

1547
01:14:33,870 --> 01:14:35,870
Måske er det better--
a la hurtig og beskidt,

1548
01:14:35,870 --> 01:14:38,660
som Kareem foreslog earlier--
at kaste hukommelse på problemet.

1549
01:14:38,660 --> 01:14:42,520
Bare købe mere hukommelse, tror mindre
hårdt om at løse problemet,

1550
01:14:42,520 --> 01:14:44,595
og løse det på en lettere måde.

1551
01:14:44,595 --> 01:14:46,720
Og faktisk tidligere, da
vi talte om kompromiser,

1552
01:14:46,720 --> 01:14:49,190
det ikke var plads i
computeren og tid.

1553
01:14:49,190 --> 01:14:51,810
Det var udvikleren tid, som
er endnu en ressource.

1554
01:14:51,810 --> 01:14:54,829
>> Så igen, det er denne balancegang
forsøger at beslutte, hvilke af disse ting

1555
01:14:54,829 --> 01:14:55,870
er du villig til at betale?

1556
01:14:55,870 --> 01:14:57,380
Hvilket er den billigste?

1557
01:14:57,380 --> 01:15:01,040
Hvilket giver de bedre resultater?

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
>> Ja.

1561
01:15:12,580 --> 01:15:15,970
I dette tilfælde, hvis du er
repræsenterer numre i maps--

1562
01:15:15,970 --> 01:15:18,820
disse kaldes på mange sprog
"pointers" eller "adresser" -

1563
01:15:18,820 --> 01:15:20,390
det er dobbelt plads.

1564
01:15:20,390 --> 01:15:24,390
Det behøver ikke være så slemt som dobbelt, hvis
lige nu er vi bare opbevaring numre.

1565
01:15:24,390 --> 01:15:27,410
Antag, at vi opbevaring
patientjournaler i en hospital--

1566
01:15:27,410 --> 01:15:30,870
så Pierson navne, telefonnumre,
CPR-numre, læge

1567
01:15:30,870 --> 01:15:31,540
historie.

1568
01:15:31,540 --> 01:15:34,160
Denne boks kan være meget,
meget større, i hvilket tilfælde

1569
01:15:34,160 --> 01:15:38,000
en lille smule pointer, adressen på
den næste element-- det er ikke en big deal.

1570
01:15:38,000 --> 01:15:40,620
Det er sådan en marginal
koster det gør ikke noget.

1571
01:15:40,620 --> 01:15:43,210
Men i dette tilfælde, ja, det er en fordobling.

1572
01:15:43,210 --> 01:15:45,290
Godt spørgsmål.

1573
01:15:45,290 --> 01:15:47,900
>> Lad os tale om gang en
lidt mere konkret.

1574
01:15:47,900 --> 01:15:50,380
Hvad er køretiden
søge denne liste?

1575
01:15:50,380 --> 01:15:53,640
Antag jeg ønskede at søge
gennem alle de studerendes kvaliteter,

1576
01:15:53,640 --> 01:15:55,980
og der er n kvaliteter
i denne datastruktur.

1577
01:15:55,980 --> 01:15:58,830
Også her kan vi låne
ordforråd tidligere.

1578
01:15:58,830 --> 01:16:00,890
Dette er en lineær datastruktur.

1579
01:16:00,890 --> 01:16:04,570
>> Big O i n er, hvad der kræves for at få
til slutningen af ​​denne datastruktur,

1580
01:16:04,570 --> 01:16:08,410
whereas-- og vi har ikke set
dette before-- et array giver dig

1581
01:16:08,410 --> 01:16:13,555
hvad der kaldes konstant tid, hvilket betyder,
et trin eller to trin eller 10 steps--

1582
01:16:13,555 --> 01:16:14,180
betyder ikke noget.

1583
01:16:14,180 --> 01:16:15,440
Det er et fast antal.

1584
01:16:15,440 --> 01:16:17,440
Det har intet at gøre med
størrelsen af ​​array.

1585
01:16:17,440 --> 01:16:20,130
Og grunden til, at
igen, er random access.

1586
01:16:20,130 --> 01:16:23,180
Computeren kan bare straks
hoppe til en anden placering,

1587
01:16:23,180 --> 01:16:27,770
fordi de er alle de samme
afstand fra alt andet.

1588
01:16:27,770 --> 01:16:29,112
Der er ingen tænkning involveret.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Okay.

1591
01:16:32,400 --> 01:16:39,230
Så hvis jeg kan, så lad mig prøve at
male to sidste billeder.

1592
01:16:39,230 --> 01:16:42,830
En meget almindelig en såkaldt hash tabel.

1593
01:16:42,830 --> 01:16:51,120
Så for at motivere denne diskussion,
lad mig tænke over, hvordan du gør dette.

1594
01:16:51,120 --> 01:16:52,610
>> Så hvad med dette?

1595
01:16:52,610 --> 01:16:55,160
Antag, at problemet
vi ønsker at løse nu

1596
01:16:55,160 --> 01:16:58,360
gennemfører i en dictionary--
så en hel masse engelske ord

1597
01:16:58,360 --> 01:16:59,330
eller hvad.

1598
01:16:59,330 --> 01:17:02,724
Og målet er at være i stand til at besvare
spørgsmål af formen er det et ord?

1599
01:17:02,724 --> 01:17:04,640
Så du ønsker at gennemføre
en stavekontrol, bare

1600
01:17:04,640 --> 01:17:07,220
som en fysisk ordbog
at du kan se tingene op i.

1601
01:17:07,220 --> 01:17:10,490
Antag jeg skulle gøre dette med et array.

1602
01:17:10,490 --> 01:17:12,590
Jeg kunne gøre dette.

1603
01:17:12,590 --> 01:17:20,756
>> Og formoder ordene er æble
og banan og cantaloupe.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Og jeg kan ikke tænke på frugt
som starter med d, så vi er bare

1606
01:17:26,465 --> 01:17:27,590
vil have tre frugter.

1607
01:17:27,590 --> 01:17:31,510
Så dette er en matrix, og vi er
lagring af alle disse ord

1608
01:17:31,510 --> 01:17:34,200
i denne ordbog som en matrix.

1609
01:17:34,200 --> 01:17:39,350
Spørgsmålet er så, hvordan ellers
kunne du gemme disse oplysninger?

1610
01:17:39,350 --> 01:17:43,160
>> Nå, jeg slags snyd her, fordi
hver af disse bogstaver i ordet

1611
01:17:43,160 --> 01:17:44,490
er virkelig en individuel byte.

1612
01:17:44,490 --> 01:17:46,740
Så hvis jeg virkelig ønskede at være
nit-betyder, bør jeg virkelig

1613
01:17:46,740 --> 01:17:49,600
være at opdele dette op i meget
mindre bidder af hukommelse,

1614
01:17:49,600 --> 01:17:51,289
og vi kunne gøre netop dette.

1615
01:17:51,289 --> 01:17:53,580
Men vi kommer til at løbe ind i
det samme problem som før.

1616
01:17:53,580 --> 01:17:56,674
Hvad nu hvis, som Merriam Webster eller Oxford
gør hvert year-- de tilføje ord

1617
01:17:56,674 --> 01:17:59,340
til dictionary-- vi ikke
nødvendigvis ønsker at male os selv

1618
01:17:59,340 --> 01:18:00,780
i et hjørne med et array?

1619
01:18:00,780 --> 01:18:05,710
>> Så i stedet, måske en smartere tilgang
er at sætte æble i sin egen node eller kasse,

1620
01:18:05,710 --> 01:18:11,190
som vi ville sige, banan, og
så her har vi cantaloupe.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Og vi strengen disse ting sammen.

1623
01:18:16,790 --> 01:18:19,980
Så dette er matrixen, og
dette er den linkede liste.

1624
01:18:19,980 --> 01:18:23,300
Hvis du ikke kan helt se, det bare
siger "matrix", og det siger "liste."

1625
01:18:23,300 --> 01:18:25,780
>> Så vi har den samme
præcise spørgsmål som før,

1626
01:18:25,780 --> 01:18:28,600
hvorved vi nu har
dynamik i vores linkede liste.

1627
01:18:28,600 --> 01:18:31,090
Men vi har en temmelig langsom ordbog.

1628
01:18:31,090 --> 01:18:32,870
Antag jeg ønsker at se et ord op.

1629
01:18:32,870 --> 01:18:35,430
Det kan tage mig store O i n
trin, fordi ordet måske

1630
01:18:35,430 --> 01:18:37,840
være hele vejen ved udgangen af
listen, ligesom cantaloupe.

1631
01:18:37,840 --> 01:18:40,600
Og det viser sig, at
i programmering, sortere

1632
01:18:40,600 --> 01:18:42,700
af den hellige gral af data
strukturer, er noget

1633
01:18:42,700 --> 01:18:46,620
der giver dig konstant
tid som et array

1634
01:18:46,620 --> 01:18:50,870
men som stadig giver dig dynamik.

1635
01:18:50,870 --> 01:18:52,940
>> Så kan vi få det bedste fra begge verdener?

1636
01:18:52,940 --> 01:18:55,570
Og ja, der er noget
kaldet hash tabellen

1637
01:18:55,570 --> 01:18:59,320
der tillader dig at gøre præcis
der, selv tilnærmelsesvis.

1638
01:18:59,320 --> 01:19:03,140
En hash tabel er en mere avanceret
datastruktur, vi

1639
01:19:03,140 --> 01:19:06,340
kan tænke på som
kombination af en array--

1640
01:19:06,340 --> 01:19:12,390
og jeg har tænkt mig at trække det
ligesom denne-- og hægtede lister

1641
01:19:12,390 --> 01:19:17,310
at jeg vil trække på denne måde herovre.

1642
01:19:17,310 --> 01:19:19,760
>> Og den måde, denne ting
værker er som følger.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Hvis dette nu-- hash table--
er min tredje datastruktur,

1645
01:19:29,540 --> 01:19:32,590
og jeg vil gemme
ord i denne, det gør jeg ikke

1646
01:19:32,590 --> 01:19:35,440
bare ønsker at gemme alle de
ord tilbage til tilbage til tilbage til tilbage.

1647
01:19:35,440 --> 01:19:37,430
Jeg ønsker at udnytte nogle
stykke information

1648
01:19:37,430 --> 01:19:40,330
om de ord, der vil lade
mig med at få det, hvor det er hurtigere.

1649
01:19:40,330 --> 01:19:43,666
>> Så givet ord æble
og banan og melon,

1650
01:19:43,666 --> 01:19:45,040
Jeg valgte bevidst disse ord.

1651
01:19:45,040 --> 01:19:45,340
Hvorfor?

1652
01:19:45,340 --> 01:19:47,631
Hvad er slags fundamentalt
anderledes ved de tre?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Hvad er det indlysende?

1655
01:19:51,484 --> 01:19:52,900
De starter med forskellige bogstaver.

1656
01:19:52,900 --> 01:19:53,900
>> Så ved du hvad?

1657
01:19:53,900 --> 01:19:57,120
I stedet lægge alle mine ord i
den samme spand, så at sige,

1658
01:19:57,120 --> 01:20:00,390
ligesom i en stor liste, hvorfor ikke
Jeg i det mindste prøve en optimering

1659
01:20:00,390 --> 01:20:04,180
og gøre mine lister 1/26 så længe.

1660
01:20:04,180 --> 01:20:07,440
En overbevisende optimering
måske hvorfor ikke

1661
01:20:07,440 --> 01:20:10,650
Jeg-- når du sætter et ord
i denne datastruktur,

1662
01:20:10,650 --> 01:20:14,300
i computerens hukommelse, hvorfor
jeg ikke sætte alle a-ord her,

1663
01:20:14,300 --> 01:20:17,270
alle de B-ord her,
og alle C-ord her?

1664
01:20:17,270 --> 01:20:24,610
Så det ender med at sætte et æble
her, banan her, cantaloupe her,

1665
01:20:24,610 --> 01:20:25,730
og så videre.

1666
01:20:25,730 --> 01:20:31,700
>> Og hvis jeg har en ekstra
ord like-- hvad er en anden?

1667
01:20:31,700 --> 01:20:36,640
Apple, banan, pære.

1668
01:20:36,640 --> 01:20:39,370
Nogen tænker på en frugt
der starter med a, b eller c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- perfekt.

1670
01:20:40,570 --> 01:20:43,990
Det kommer til at ende op her.

1671
01:20:43,990 --> 01:20:47,530
Og så vi synes at have en
marginalt bedre opløsning,

1672
01:20:47,530 --> 01:20:50,820
fordi nu hvis jeg vil
at søge efter æble, jeg

1673
01:20:50,820 --> 01:20:53,200
first-- jeg ikke bare dykke
ind i min datastruktur.

1674
01:20:53,200 --> 01:20:54,850
Jeg kan ikke dykke ned i min computers hukommelse.

1675
01:20:54,850 --> 01:20:56,530
Jeg først se på det første bogstav.

1676
01:20:56,530 --> 01:20:58,610
>> Og dette er, hvad en computer
videnskabsmand ville sige.

1677
01:20:58,610 --> 01:21:00,760
Du hash ind i din datastruktur.

1678
01:21:00,760 --> 01:21:04,100
Du tager dit input, der i
dette tilfælde er et ord som æble.

1679
01:21:04,100 --> 01:21:07,150
Du analyserer det, ser på
det første bogstav i denne sag,

1680
01:21:07,150 --> 01:21:08,340
hvorved hashing det.

1681
01:21:08,340 --> 01:21:10,950
Hashing er en generel betegnelse, hvorved
du tager noget som input

1682
01:21:10,950 --> 01:21:12,116
og du producerer nogle output.

1683
01:21:12,116 --> 01:21:15,090
Og outputtet ved, at
tilfælde er placeringen

1684
01:21:15,090 --> 01:21:18,150
du vil søge, den første
beliggenhed, anden placering, tredje.

1685
01:21:18,150 --> 01:21:22,160
Så indgangen er æble,
produktionen er først.

1686
01:21:22,160 --> 01:21:25,054
Inputtet er banan, den
output skal være andet.

1687
01:21:25,054 --> 01:21:27,220
Inputtet er cantaloupe,
output bør være tredjedel.

1688
01:21:27,220 --> 01:21:30,320
Inputtet er blåbær, den
output skal igen være andet.

1689
01:21:30,320 --> 01:21:34,010
Og det er, hvad hjælper du tager
genveje gennem din hukommelse

1690
01:21:34,010 --> 01:21:39,050
for at komme til ord
eller data mere effektivt.

1691
01:21:39,050 --> 01:21:43,330
>> Nu skærer ned vores tid potentielt
med så meget som en ud af 26,

1692
01:21:43,330 --> 01:21:45,850
fordi hvis du antager, at du
have så mange "a" ord som "z"

1693
01:21:45,850 --> 01:21:48,080
ord som "Q" ord, som
er egentlig ikke realistic--

1694
01:21:48,080 --> 01:21:50,830
du kommer til at have skew tværs
visse bogstaver i alphabet--

1695
01:21:50,830 --> 01:21:53,204
men dette ville være en trinvis
tilgang, der tillader

1696
01:21:53,204 --> 01:21:55,930
dig at komme til ord meget hurtigere.

1697
01:21:55,930 --> 01:21:59,660
Og i virkeligheden, en sofistikeret
programmet, Googles af verden,

1698
01:21:59,660 --> 01:22:02,180
Den Facebooks af verden-
de ville bruge en hash tabel

1699
01:22:02,180 --> 01:22:03,740
for mange forskellige formål.

1700
01:22:03,740 --> 01:22:06,590
Men de ville ikke være så naive,
bare se på det første bogstav

1701
01:22:06,590 --> 01:22:09,700
i æble eller banan eller
pærer eller cantaloupe,

1702
01:22:09,700 --> 01:22:13,420
fordi som du kan se disse
lister kan stadig få lange.

1703
01:22:13,420 --> 01:22:17,130
>> Og så dette kan stadig være sort
af linear-- så slags langsom,

1704
01:22:17,130 --> 01:22:19,980
Ligesom med den store O i n
at vi diskuterede tidligere.

1705
01:22:19,980 --> 01:22:25,290
Så hvad en rigtig god hash tabel vil
do-- det vil have en meget større array.

1706
01:22:25,290 --> 01:22:28,574
Og det vil bruge en langt mere
sofistikeret hashingfunktion,

1707
01:22:28,574 --> 01:22:30,240
så det ikke bare se på "a".

1708
01:22:30,240 --> 01:22:35,480
Måske ser på "en-p-p-l-e" og
en eller anden måde omdanner disse fem bogstaver

1709
01:22:35,480 --> 01:22:38,400
i den placering, hvor
æble skal opbevares.

1710
01:22:38,400 --> 01:22:42,660
Vi er lige naivt at bruge bogstavet »a«
alene, fordi det er rart og enkel.

1711
01:22:42,660 --> 01:22:44,600
>> Men en hash tabel, i
sidste ende, kan du tror

1712
01:22:44,600 --> 01:22:47,270
som en kombination af
et array, som hver

1713
01:22:47,270 --> 01:22:51,700
har en sammenkædet liste, der ideelt set
bør være så kort som muligt.

1714
01:22:51,700 --> 01:22:54,364
Og dette er ikke en indlysende løsning.

1715
01:22:54,364 --> 01:22:57,280
Faktisk er meget af finindstillingen
der foregår under kølerhjelmen, når

1716
01:22:57,280 --> 01:22:59,654
gennemførelsen af ​​disse former for
sofistikerede datastrukturer

1717
01:22:59,654 --> 01:23:01,640
er det, er den rigtige
længden af ​​array?

1718
01:23:01,640 --> 01:23:03,250
Hvad er den rigtige hash funktion?

1719
01:23:03,250 --> 01:23:04,830
Hvordan gemme ting i hukommelsen?

1720
01:23:04,830 --> 01:23:07,249
>> Men indse, hvor hurtigt
denne form for diskussion

1721
01:23:07,249 --> 01:23:10,540
eskalerede, enten så langt, at det er sådan
af over hovedet på dette tidspunkt, som

1722
01:23:10,540 --> 01:23:11,360
er fint.

1723
01:23:11,360 --> 01:23:18,820
Men vi startede, husker, med virkelig
noget lavt niveau og elektronisk.

1724
01:23:18,820 --> 01:23:20,819
Og så det igen er dette
temaet abstraktion,

1725
01:23:20,819 --> 01:23:23,610
hvor når du begynder at tage for
givet, OK, har jeg fået it-- der er

1726
01:23:23,610 --> 01:23:26,680
fysisk hukommelse, OK, fik det, hver
fysiske placering har en adresse,

1727
01:23:26,680 --> 01:23:29,910
OK, jeg fik det, kan jeg repræsenterer
disse adresser som arrows--

1728
01:23:29,910 --> 01:23:34,650
kan du meget hurtigt begynde at have
mere sofistikerede samtaler,

1729
01:23:34,650 --> 01:23:38,360
i sidste ende synes at være at lade os
til at løse problemer som søger

1730
01:23:38,360 --> 01:23:41,620
og sortering mere effektivt.

1731
01:23:41,620 --> 01:23:44,190
Og være sikker på, too--
fordi jeg tror, ​​det

1732
01:23:44,190 --> 01:23:48,700
er den dybeste vi har gået ind i nogle
af disse CS emner proper-- vi ve

1733
01:23:48,700 --> 01:23:51,880
gøres på en dag og en halv på dette
pege hvad du måske typisk gøre løbet

1734
01:23:51,880 --> 01:23:55,520
løbet af otte uger i et semester.

1735
01:23:55,520 --> 01:23:59,670
>> Eventuelle spørgsmål om disse?

1736
01:23:59,670 --> 01:24:01,100
Ingen?

1737
01:24:01,100 --> 01:24:01,940
Okay.

1738
01:24:01,940 --> 01:24:05,610
Tja, hvorfor vi ikke pause der,
starte frokost et par minutter tidligt,

1739
01:24:05,610 --> 01:24:07,052
genoptages i næsten en time?

1740
01:24:07,052 --> 01:24:08,760
Og jeg vil blive hængende i
lidt med spørgsmål.

1741
01:24:08,760 --> 01:24:11,343
Så jeg har tænkt mig at have til at gå
tage et par opkald, hvis det er OK.

1742
01:24:11,343 --> 01:24:15,000
Jeg vil tænde noget musik i mellemtiden,
men frokost skal være rundt om hjørnet.

1743
01:24:15,000 --> 01:24:17,862