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

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

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

4
00:00:01,094 --> 00:00:04,260
Så i dette segmentet på programmering hva
Jeg trodde vi ville gjøre er en blanding av ting.

5
00:00:04,260 --> 00:00:06,340
One, gjøre litt
noe hands-on,

6
00:00:06,340 --> 00:00:08,690
riktignok ved hjelp av en mer leken
programmering environment--

7
00:00:08,690 --> 00:00:11,620
en som er demonstrative av
nøyaktig hva slags ideer

8
00:00:11,620 --> 00:00:14,220
vi har snakket om,
men litt mer formelt.

9
00:00:14,220 --> 00:00:18,200
To, se på noen av
de mer tekniske måter

10
00:00:18,200 --> 00:00:21,520
at en programmerer faktisk ville løse
problemer som søker problem

11
00:00:21,520 --> 00:00:24,530
som vi så på før og
også en mer fundamentalt

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

13
00:00:26,020 --> 00:00:28,840
>> Vi antok bare fra får gå
som at telefonboken ble sortert,

14
00:00:28,840 --> 00:00:31,980
men det alene er faktisk slags en
vanskelig problem med mange forskjellige måter

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

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

17
00:00:34,366 --> 00:00:36,740
representant for ting som
kan løses generelt.

18
00:00:36,740 --> 00:00:38,980
Og så får vi snakke
om i noen detalj hva

19
00:00:38,980 --> 00:00:42,360
kalles data structures--
avansert måter som lenkede lister

20
00:00:42,360 --> 00:00:46,290
og hash tabeller og trær som
en programmerer ville faktisk

21
00:00:46,290 --> 00:00:48,890
bruke og bruker vanligvis
på en tavle til å male

22
00:00:48,890 --> 00:00:51,840
et bilde av hva han eller hun
ser for seg for å implementere

23
00:00:51,840 --> 00:00:52,980
noen stykke programvare.

24
00:00:52,980 --> 00:00:55,130
>> Så la oss gjøre hands-on delen først.

25
00:00:55,130 --> 00:01:00,090
Så bare få hendene skitne med en
miljø kalt scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Dette er et verktøy som vi bruker
i vår lavere klasse.

27
00:01:02,636 --> 00:01:04,510
Selv om det er utformet
for alderen 12 og oppover,

28
00:01:04,510 --> 00:01:07,570
vi bruker det for opp
del av det ganske mye

29
00:01:07,570 --> 00:01:10,020
siden det er en fin, morsom
grafisk måte å lære på

30
00:01:10,020 --> 00:01:12,160
litt noe om programmering.

31
00:01:12,160 --> 00:01:17,600
Så hodet til denne URLen, der du
bør se en side som dette,

32
00:01:17,600 --> 00:01:23,330
og gå videre og klikk
Bli med Scratch øverst til høyre

33
00:01:23,330 --> 00:01:28,300
og velge et brukernavn og et
passord og til slutt få deg

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 tenkte jeg skulle bruke dette som en
mulighet første til å vise dette.

37
00:01:34,665 --> 00:01:39,120
Et spørsmål kom opp i pausen
om hva koden faktisk ser ut.

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

39
00:01:41,315 --> 00:01:45,060
i particular-- spesielt en
lavere nivå i en eldre språk.

40
00:01:45,060 --> 00:01:47,750
Og jeg bare gjorde en rask
Google-søk for å finne C-kode

41
00:01:47,750 --> 00:01:51,574
for binære søk, algoritmen som vi
brukes til å søke som telefonboken tidligere.

42
00:01:51,574 --> 00:01:54,240
Denne spesielle eksempel er selvfølgelig
søker ikke en telefonkatalog.

43
00:01:54,240 --> 00:01:57,840
Den søker bare en hel haug med
Tallene i datamaskinens minne.

44
00:01:57,840 --> 00:02:01,000
Men hvis du ønsker å bare få en visuell
følelse av hva en faktisk programmering

45
00:02:01,000 --> 00:02:05,370
språket ser ut, det ser ut
litt noe sånt som dette.

46
00:02:05,370 --> 00:02:09,759
Så det handler om 20-plus,
30 eller så linjer med kode,

47
00:02:09,759 --> 00:02:12,640
men samtalen vi
hadde i løpet av pausen

48
00:02:12,640 --> 00:02:16,000
var om hvordan dette faktisk
blir forvandlet til nuller og enere

49
00:02:16,000 --> 00:02:19,200
og hvis du ikke kan bare gå tilbake som
behandle og gå fra nuller og enere

50
00:02:19,200 --> 00:02:20,210
tilbake til koden.

51
00:02:20,210 --> 00:02:22,620
>> Dessverre, prosessen
er så transformative

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

53
00:02:24,890 --> 00:02:29,400
Jeg gikk videre og faktisk slått
det programmet, Binary Search,

54
00:02:29,400 --> 00:02:32,700
til nuller og enere i form av en
program kalt The Compiler at jeg

55
00:02:32,700 --> 00:02:34,400
tilfeldigvis har her rett på min Mac.

56
00:02:34,400 --> 00:02:37,850
Og hvis du ser på skjermen
her, med fokus spesielt

57
00:02:37,850 --> 00:02:43,520
på disse middel seks kolonner bare,
ser du bare nuller og enere.

58
00:02:43,520 --> 00:02:48,290
Og de er de nuller og enere som
komponere akkurat det søker programmet.

59
00:02:48,290 --> 00:02:53,720
>> Og slik at hver del av fem biter,
hver byte av nuller og enere her,

60
00:02:53,720 --> 00:02:57,310
representere noen instruksjon
typisk inne i en datamaskin.

61
00:02:57,310 --> 00:03:00,730
Og faktisk, hvis du har hørt
markedsføring slagord "Intel inside" - det vil si,

62
00:03:00,730 --> 00:03:04,610
selvfølgelig, betyr bare at du har en
Intel CPU eller hjerne inni datamaskinen.

63
00:03:04,610 --> 00:03:08,000
Og hva det betyr å være en CPU er
at du har en instruksjonssett,

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

65
00:03:08,840 --> 00:03:11,620
>> Hver CPU i verden, mange av
dem laget av Intel i disse dager,

66
00:03:11,620 --> 00:03:13,690
forstår et endelig
antall instruksjoner.

67
00:03:13,690 --> 00:03:18,690
Og disse instruksjonene er så lavt nivå
som legger disse to tallene sammen,

68
00:03:18,690 --> 00:03:22,560
multiplisere disse to tallene sammen,
flytte denne stykke data herfra

69
00:03:22,560 --> 00:03:27,340
til her i minnet, lagre denne
informasjon fra her til her i minnet,

70
00:03:27,340 --> 00:03:32,200
og så forth-- så veldig, veldig
lavt nivå, nesten elektroniske detaljer.

71
00:03:32,200 --> 00:03:34,780
Men med de matematiske
operasjoner kombinert

72
00:03:34,780 --> 00:03:37,410
med hva vi snakket om tidligere,
representasjon av dataene

73
00:03:37,410 --> 00:03:40,450
som nuller og enere, kan
du bygger opp alt

74
00:03:40,450 --> 00:03:44,180
at en datamaskin kan gjøre i dag, enten
det er tekstlig, grafisk, musikalsk,

75
00:03:44,180 --> 00:03:45,580
hvis ikke.

76
00:03:45,580 --> 00:03:49,450
>> Så dette er veldig lett å få
tapt i ugress av raskt.

77
00:03:49,450 --> 00:03:52,150
Og det er mye av
syntaktisk utfordringer

78
00:03:52,150 --> 00:03:56,630
der hvis du gjør det enkleste,
dummeste av skrivefeil ingen av programmet

79
00:03:56,630 --> 00:03:57,860
vil fungere overhodet.

80
00:03:57,860 --> 00:04:00,366
Og så i stedet for å bruke en
språk som C i morges,

81
00:04:00,366 --> 00:04:02,240
Jeg trodde det ville være
mer moro å faktisk gjøre

82
00:04:02,240 --> 00:04:04,840
noe mer visuell, som
mens beregnet for barn

83
00:04:04,840 --> 00:04:08,079
er faktisk en perfekt manifestasjon
av en faktisk programmering

84
00:04:08,079 --> 00:04:10,370
language-- bare skjer for å
bruke bilder i stedet for tekst

85
00:04:10,370 --> 00:04:11,710
å representere disse ideene.

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

87
00:04:15,470 --> 00:04:21,070
Klikk på Opprett-knappen
øverst til venstre på siden.

88
00:04:21,070 --> 00:04:24,620
Og du burde se et miljø som
den jeg er i ferd med å se på skjermen min

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

90
00:04:26,310 --> 00:04:29,350
Og vi vil bruke bare litt
litt tid på å spille her.

91
00:04:29,350 --> 00:04:34,080
La oss se om vi ikke kan alle løse noen
problemer sammen på følgende måte.

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

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

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

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

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

97
00:04:45,800 --> 00:04:49,030
Så la meg påpeke noen
egenskapene til dette miljøet.

98
00:04:49,030 --> 00:04:55,024
>> Så øverst til venstre på skjermen, vi
har Scratch etappe, så å si.

99
00:04:55,024 --> 00:04:57,440
Scratch er ikke bare navnet
av denne programmeringsspråk;

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

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

102
00:05:02,160 --> 00:05:05,770
skilpadden tidligere som å være i en
rektangulær hvit bord miljø.

103
00:05:05,770 --> 00:05:09,800
Denne katten verden er begrenset helt
til at rektangelet opp toppen der.

104
00:05:09,800 --> 00:05:12,210
>> I mellomtiden, på høyre
siden her, er det

105
00:05:12,210 --> 00:05:15,610
bare et skript, en
blankt hvis du vil.

106
00:05:15,610 --> 00:05:18,590
Det er der vi kommer til å skrive
våre programmer i bare et øyeblikk.

107
00:05:18,590 --> 00:05:22,935
Og byggesteinene som vi skal
bruke til å skrive denne program-- puslespillet

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

109
00:05:25,310 --> 00:05:27,500
og de er kategorisert
av funksjonalitet.

110
00:05:27,500 --> 00:05:31,000
Så, for eksempel, kommer jeg til å gå videre
og viser i det minste en av disse.

111
00:05:31,000 --> 00:05:33,690
Jeg kommer til å gå videre og klikk
Kontroll kategorien opp toppen.

112
00:05:33,690 --> 00:05:35,720
>> Så dette er kategoriene opp toppen.

113
00:05:35,720 --> 00:05:39,410
Jeg kommer til å klikke kontroll kategorien.

114
00:05:39,410 --> 00:05:44,020
Snarere, jeg kommer til å klikke Hendelser
kategori, den aller første opp toppen.

115
00:05:44,020 --> 00:05:47,790
Og hvis du ønsker å følge med selv
som vi gjør dette, er du veldig velkommen til.

116
00:05:47,790 --> 00:05:52,180
Jeg kommer til å klikke og dra
første, "når grønt flagg klikket."

117
00:05:52,180 --> 00:05:58,410
Og så kommer jeg til å droppe det bare
omtrent på toppen av min blanke ark.

118
00:05:58,410 --> 00:06:01,450
>> Og hva er fint om Scratch
er at dette puslespillet stykke, når

119
00:06:01,450 --> 00:06:04,560
forriglet med andre pusle
stykker, kommer til å gjøre bokstavelig

120
00:06:04,560 --> 00:06:06,460
hva disse brikkene si å gjøre.

121
00:06:06,460 --> 00:06:09,710
Så, for eksempel, er Scratch riktig
nå i midten av sin verden.

122
00:06:09,710 --> 00:06:14,660
Jeg kommer til å gå videre og velge
nå, la oss si, kategori Motion,

123
00:06:14,660 --> 00:06:18,000
Hvis du ønsker å gjøre det
same-- Motion kategori.

124
00:06:18,000 --> 00:06:20,430
Og nå merker jeg har en hel
haug av brikkene her

125
00:06:20,430 --> 00:06:23,370
som, igjen, på en måte gjøre hva de sier.

126
00:06:23,370 --> 00:06:28,110
Og jeg kommer til å gå foran og dra og
slippe farten blokken rett over her.

127
00:06:28,110 --> 00:06:31,860
>> Og legg merke til at så snart du får
nær bunnen av "grønne flagget

128
00:06:31,860 --> 00:06:34,580
klikket "-knappen, varsel
hvordan en hvit strek,

129
00:06:34,580 --> 00:06:36,950
som om det er nesten
magnetisk, ønsker den å gå dit.

130
00:06:36,950 --> 00:06:43,070
Bare la gå, og det vil knipse
sammen og figurene vil matche.

131
00:06:43,070 --> 00:06:46,620
Og nå kan du kanskje nesten
Gjett hvor vi skal med dette.

132
00:06:46,620 --> 00:06:51,570
>> Hvis du ser på Scratch scenen
over her og ser opp til toppen av det,

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

134
00:06:55,142 --> 00:06:57,100
Og jeg kommer til å gå videre
og se mine screen--

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

136
00:06:58,460 --> 00:07:01,960
Jeg kommer til å klikke på
grønt flagg akkurat nå,

137
00:07:01,960 --> 00:07:07,850
og han flyttet det som synes å være 10 trinn
eller 10 piksler, 10 prikker, på skjermen.

138
00:07:07,850 --> 00:07:13,390
>> Og så ikke så spennende,
men la meg foreslå

139
00:07:13,390 --> 00:07:17,440
uten selv å lære dette, bare
ved hjelp av egen din egen intuition-- utleid

140
00:07:17,440 --> 00:07:22,560
meg foreslå at du finne ut hvordan du
gjøre Scratch gå rett av scenen.

141
00:07:22,560 --> 00:07:28,700
Har ham gjøre vei for høyre side av
skjermen, hele veien mot høyre.

142
00:07:28,700 --> 00:07:32,200
La meg gi deg et øyeblikk
eller så for å kjempe med det.

143
00:07:32,200 --> 00:07:37,681
Du ønsker kanskje å ta en titt
på andre kategorier av blokker.

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

145
00:07:38,180 --> 00:07:41,290
Så bare for å oppsummere, når vi har
det grønne flagget klikket her

146
00:07:41,290 --> 00:07:44,850
og flytte 10 trinn er
bare instruksjon, hver gang jeg

147
00:07:44,850 --> 00:07:46,720
Klikk på den grønne flagg, hva skjer?

148
00:07:46,720 --> 00:07:50,070
Vel, som kjører programmet mitt.

149
00:07:50,070 --> 00:07:52,450
Så jeg kunne gjøre dette
kanskje 10 ganger manuelt,

150
00:07:52,450 --> 00:07:55,130
men dette føles litt
bit hackish, så å si,

151
00:07:55,130 --> 00:07:57,480
der jeg er egentlig ikke
å løse problemet.

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

153
00:08:00,530 --> 00:08:03,180
før jeg slags uhell
oppnå direktivet

154
00:08:03,180 --> 00:08:05,560
at jeg ønsket å oppnå tidligere.

155
00:08:05,560 --> 00:08:08,200
>> Men vi vet fra vår
pseudo tidligere at det er

156
00:08:08,200 --> 00:08:11,870
dette begrepet i programmering av looping,
gjør noe igjen og igjen.

157
00:08:11,870 --> 00:08:14,888
Og så så jeg at en haug med deg
nådd for hva puslespill brikke?

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

159
00:08:17,870 --> 00:08:18,730
Gjenta til.

160
00:08:18,730 --> 00:08:21,400
Slik at vi kunne gjøre noe
som gjenta til.

161
00:08:21,400 --> 00:08:23,760
Og hva gjorde du gjenta til nøyaktig?

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

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

164
00:08:28,540 --> 00:08:31,974
Og la meg gå med en som er
noe enklere for bare et øyeblikk.

165
00:08:31,974 --> 00:08:33,140
La meg gå videre og gjøre dette.

166
00:08:33,140 --> 00:08:35,559
Legg merke til at, som du kan ha
oppdaget under kontroll,

167
00:08:35,559 --> 00:08:38,409
det er denne gjenta blokken, hvilken
ser ikke ut som det er så stor.

168
00:08:38,409 --> 00:08:41,039
Det er ikke mye plass i
mellom disse to gule linjer.

169
00:08:41,039 --> 00:08:43,539
Men som noen av dere kanskje har
lagt merke til, hvis du dra og slipp,

170
00:08:43,539 --> 00:08:45,150
Legg merke til hvordan det vokser til å fylle formen.

171
00:08:45,150 --> 00:08:46,274
>> Og du kan selv pugge mer.

172
00:08:46,274 --> 00:08:48,670
Det vil bare fortsette å vokse hvis
du drar og sveve over det.

173
00:08:48,670 --> 00:08:51,110
Og jeg vet ikke hva som er
beste her, så la

174
00:08:51,110 --> 00:08:54,760
meg minst gjenta fem ganger, for
eksempel, og deretter gå tilbake til scenen

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

176
00:08:56,720 --> 00:08:59,110
Og nå legger merke til det er ikke helt der.

177
00:08:59,110 --> 00:09:02,400
>> Nå er noen av dere foreslått, som
Victoria nettopp gjorde, gjenta 10 ganger.

178
00:09:02,400 --> 00:09:05,140
Og som regel gjør
få ham hele veien,

179
00:09:05,140 --> 00:09:10,510
men ville ikke det være en mer robust
måte enn vilkårlig finne ut

180
00:09:10,510 --> 00:09:12,640
hvor mange trekk å gjøre?

181
00:09:12,640 --> 00:09:17,680
Hva kan være en bedre blokk
enn gjenta 10 ganger være?

182
00:09:17,680 --> 00:09:20,380
>> Ja, så hvorfor ikke gjøre noe for alltid?

183
00:09:20,380 --> 00:09:24,390
Og nå la meg flytte dette puslespill brikke
inni der og bli kvitt denne.

184
00:09:24,390 --> 00:09:28,300
Legg merke til nå uansett hvor Scratch
starter, går han til kanten.

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

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

187
00:09:33,190 --> 00:09:35,360
Du kan alltid ta halen.

188
00:09:35,360 --> 00:09:37,680
>> Og akkurat intuitivt,
hvorfor han holder koken?

189
00:09:37,680 --> 00:09:38,892
Hva skjer her?

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

191
00:09:41,440 --> 00:09:43,824
Han synes å ha stoppet, men
så hvis jeg plukker opp og dra

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

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
Sannelig, er en datamaskin bokstavelig talt
kommer til å gjøre det du ber den om.

196
00:09:54,360 --> 00:09:58,380
Så hvis du fortalte det tidligere gjøre
følgende ting alltid, flytte 10 trinn,

197
00:09:58,380 --> 00:10:01,860
det kommer til å fortsette og fortsette
før jeg traff den røde stoppskiltet

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

199
00:10:04,620 --> 00:10:06,610
>> Så selv om du ikke gjorde det
gjør dette, hvordan kunne jeg

200
00:10:06,610 --> 00:10:09,510
gjøre Scratch flytte raskere
over skjermen?

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

202
00:10:12,060 --> 00:10:13,280
Flere trinn, ikke sant?

203
00:10:13,280 --> 00:10:15,710
Så i stedet for å gjøre 10
om gangen, hvorfor gjør ikke vi

204
00:10:15,710 --> 00:10:20,100
gå videre og endre det to--
hva ville du propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Så nå kommer jeg til å klikke på den grønne
flagg, og ja, han går veldig fort.

206
00:10:24,410 --> 00:10:27,180
>> Og dette, selvfølgelig, er bare
en manifestasjon av animasjon.

207
00:10:27,180 --> 00:10:28,060
Hva er animasjon?

208
00:10:28,060 --> 00:10:33,090
Det er bare å vise deg det menneskelige en
hel haug med stillbilder egentlig,

209
00:10:33,090 --> 00:10:34,160
veldig, veldig fort.

210
00:10:34,160 --> 00:10:36,500
Og så hvis vi bare fortelle
ham til å bevege seg flere trinn,

211
00:10:36,500 --> 00:10:39,750
vi bare ha effekten være å
endring der han er på skjermen

212
00:10:39,750 --> 00:10:42,900
alle de hurtigere per tidsenhet.

213
00:10:42,900 --> 00:10:46,454
>> Nå er neste utfordring som jeg foreslo
var å ha ham sprette utenfor kanten.

214
00:10:46,454 --> 00:10:49,120
Og uten å vite hva puslespill
stykker exist-- fordi det er greit

215
00:10:49,120 --> 00:10:53,030
hvis du ikke får til
stadium av challenge-- hva

216
00:10:53,030 --> 00:10:54,280
ønsker du å gjøre intuitivt?

217
00:10:54,280 --> 00:10:58,030
Hvordan ville vi ha ham sprette tilbake og
videre, mellom venstre og høyre?

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

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

220
00:11:03,810 --> 00:11:05,680
Så vi trenger noen form
tilstand, og vi

221
00:11:05,680 --> 00:11:09,710
ser ut til å ha conditionals, så å
snakke, under kategorien Control.

222
00:11:09,710 --> 00:11:14,110
Hvilke av disse blokkene
vi sannsynligvis vil?

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

224
00:11:15,200 --> 00:11:18,780
Så legger merke til at blant de gule blokkene
vi har her, det er denne "hvis"

225
00:11:18,780 --> 00:11:23,920
eller denne "if, else" blokk som vil
tillate oss å gjøre en beslutning om å gjøre dette

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

227
00:11:25,000 --> 00:11:27,380
Og du kan til og med hekker dem
å gjøre flere ting.

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

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

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

231
00:11:43,050 --> 00:11:52,050
>> Så hva blokk kan være nyttig her
å oppdage hvis han er av scenen?

232
00:11:52,050 --> 00:11:56,740
Ja, merker at noen av disse blokkene
kan parametrized, så å si.

233
00:11:56,740 --> 00:12:00,706
De kan liksom tilpasset, ikke
i motsetning til HTML i går med attributter,

234
00:12:00,706 --> 00:12:03,330
hvor disse attributtene type
tilpasse atferden til en tag.

235
00:12:03,330 --> 00:12:08,880
Tilsvar her, kan jeg ta denne rørende
blokk og endring og stiller spørsmålet,

236
00:12:08,880 --> 00:12:11,500
er du berøre musen
pekeren som markøren

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

238
00:12:13,250 --> 00:12:15,210
>> Så la meg gå inn og gjøre dette.

239
00:12:15,210 --> 00:12:18,130
Jeg kommer til å zoome ut for et øyeblikk.

240
00:12:18,130 --> 00:12:21,320
La meg ta dette puslespill brikke
her, dette puslespillet stykke dette,

241
00:12:21,320 --> 00:12:24,570
og jeg kommer til å virvar
dem opp for bare et øyeblikk.

242
00:12:24,570 --> 00:12:27,620
Jeg kommer til å flytte denne,
endre dette til rørende kant,

243
00:12:27,620 --> 00:12:38,590
og jeg kommer til å bevegelse gjøre dette.

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

245
00:12:40,490 --> 00:12:42,570
Jeg tror jeg har fått alt jeg vil.

246
00:12:42,570 --> 00:12:47,710
>> Vil noen liker å foreslå hvordan jeg
kan koble disse kanskje topp til bunn

247
00:12:47,710 --> 00:12:52,020
for å løse problemet med å måtte
Scratch flytte høyre til venstre til høyre for å

248
00:12:52,020 --> 00:12:57,020
venstre til høyre til venstre, hvert
tid bare sprette av veggen?

249
00:12:57,020 --> 00:12:58,050
Hva ønsker jeg å gjøre?

250
00:12:58,050 --> 00:13:01,097
Hvilken blokk skal jeg koble til
"Når grønne flagget klikket først"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, så la oss starte med "evig".

253
00:13:06,200 --> 00:13:07,170
Hva går inne neste?

254
00:13:07,170 --> 00:13:10,290
Noen andre.

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

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

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

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

259
00:13:15,120 --> 00:13:17,720
Og legg merke til, selv om det ser ut
klemt tett sammen,

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

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

262
00:13:21,500 --> 00:13:25,920
>> Og hva gjør jeg satt mellom
IF og da?

263
00:13:25,920 --> 00:13:27,180
Sannsynligvis "hvis berøre kanten."

264
00:13:27,180 --> 00:13:31,800
Og legg merke til, igjen, det er for stort
for det, men det vil vokse til å fylle.

265
00:13:31,800 --> 00:13:35,002
Og så slår 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 spinne
meg hele veien rundt.

269
00:13:41,196 --> 00:13:42,570
Så la oss se om jeg fikk denne retten.

270
00:13:42,570 --> 00:13:43,930
La meg zoome ut.

271
00:13:43,930 --> 00:13:45,130
>> La meg dra Scratch opp.

272
00:13:45,130 --> 00:13:50,030
Så han er litt forvrengt
nå, men det er fint.

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

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

275
00:13:59,879 --> 00:14:01,045
Jeg kommer til å jukse litt.

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

277
00:14:04,074 --> 00:14:05,990
Så jeg legger en annen
blokk, bare for å være klar.

278
00:14:05,990 --> 00:14:08,424
Jeg vil at han skal peke 90 grader
til høyre som standard,

279
00:14:08,424 --> 00:14:10,840
så jeg skal bare fortelle ham
å gjøre det programmatisk.

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 ser ut til å ha gjort det.

283
00:14:15,740 --> 00:14:19,980
Det er litt rart, fordi
han går opp ned.

284
00:14:19,980 --> 00:14:21,250
La oss kalle det en bug.

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

286
00:14:22,120 --> 00:14:27,320
En bug er en feil i et program, en
logiske feil som jeg, mennesket, gjort.

287
00:14:27,320 --> 00:14:28,985
Hvorfor er han går opp ned?

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

289
00:14:33,560 --> 00:14:35,250
Har MIT skru opp 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 MITs
feil. De ga meg en puslespillbrikke

292
00:14:42,550 --> 00:14:44,970
som sier slå noen antall grader.

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

294
00:14:47,672 --> 00:14:48,880
som er riktig intuisjon.

295
00:14:48,880 --> 00:14:53,700
Men å snu 180 grader bokstavelig
betyr å dreie 180 grader

296
00:14:53,700 --> 00:14:55,860
og det er egentlig ikke
hva jeg vil, tilsynelatende.

297
00:14:55,860 --> 00:14:58,026
Fordi minst han er i
Dette to-dimensjonal verden,

298
00:14:58,026 --> 00:15:00,740
så vende som egentlig skjer
å vende ham opp ned.

299
00:15:00,740 --> 00:15:04,030
>> Jeg vil trolig bruke hva blokk
i stedet, basert på det du ser her?

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

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

302
00:15:14,790 --> 00:15:18,380
Ja, så vi kunne peke
i motsatt retning.

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

304
00:15:22,300 --> 00:15:26,410
fordi vi kan bare hardt kode
å peke venstre eller høyre.

305
00:15:26,410 --> 00:15:27,920
>> Du vet hva vi kan gjøre?

306
00:15:27,920 --> 00:15:30,160
Det ser ut som vi har en
bekvemmelighet blokk her.

307
00:15:30,160 --> 00:15:32,987
Hvis jeg zoomer inn, kan du se
noe vi liker her?

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

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

310
00:15:40,020 --> 00:15:45,440
Denne blokken synes å være ekvivalent
til hvilken andre blokker, flertall?

311
00:15:45,440 --> 00:15:49,510
>> Denne blokk synes å være ekvivalent
til hele denne trioen av blokker

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

313
00:15:50,880 --> 00:15:54,670
Så det viser seg kan jeg forenkle min
program ved å bli kvitt alt dette

314
00:15:54,670 --> 00:15:58,270
og bare sette dette inn her.

315
00:15:58,270 --> 00:16:01,620
Og nå er han fortsatt litt
buggy, og det er greit for nå.

316
00:16:01,620 --> 00:16:03,370
Vi skal la det være.

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

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

319
00:16:09,060 --> 00:16:13,430
er ideelt sett gjøre koden som
enkel, så kompakt som mulig,

320
00:16:13,430 --> 00:16:15,650
samtidig som den er så
leselig som mulig.

321
00:16:15,650 --> 00:16:20,310
Du ønsker ikke å gjøre det så fyndig
at det er vanskelig å forstå.

322
00:16:20,310 --> 00:16:22,826
>> Men merker jeg har erstattet
tre blokker med en,

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

324
00:16:24,200 --> 00:16:27,280
Jeg har abstrahert bort forestillingen
for å sjekke om du er

325
00:16:27,280 --> 00:16:29,120
på kanten med bare ett kvartal.

326
00:16:29,120 --> 00:16:31,520
Nå kan vi ha det gøy med dette, faktisk.

327
00:16:31,520 --> 00:16:35,790
Dette legger ikke så mye
intellektuell verdi, men leken verdi.

328
00:16:35,790 --> 00:16:39,730
Jeg kommer til å gå videre
og ta denne lyden her.

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

330
00:16:42,900 --> 00:16:46,420
Så la meg gå videre, og la meg
stoppe programmet for et øyeblikk.

331
00:16:46,420 --> 00:16:52,070
Jeg kommer til å ta opp følgende,
gir tilgang til mikrofonen min.

332
00:16:52,070 --> 00:16:53,181
>> Her går vi.

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

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

335
00:16:58,710 --> 00:17:01,140
La oss prøve dette igjen.

336
00:17:01,140 --> 00:17:02,279
Her går vi.

337
00:17:02,279 --> 00:17:03,570
OK, jeg spilte feil ting.

338
00:17:03,570 --> 00:17:04,580
Her går vi.

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

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

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

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

343
00:17:09,300 --> 00:17:10,791
Nå må jeg bli kvitt det.

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

345
00:17:11,290 --> 00:17:13,950
>> Så nå har jeg en
innspilling av bare "au".

346
00:17:13,950 --> 00:17:18,040
Så nå kommer jeg til å gå
videre og kaller dette "au".

347
00:17:18,040 --> 00:17:20,270
Jeg kommer til å gå tilbake
til mine skript, og nå

348
00:17:20,270 --> 00:17:25,460
innkalling det er denne blokken som heter
spille av lyd "meow" eller spille av lyd "au".

349
00:17:25,460 --> 00:17:28,920
Jeg kommer til å dra dette, og hvor
skal jeg sette dette for komisk effekt?

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

351
00:17:31,740 --> 00:17:37,860
Ja, så nå er det slags
buggy, fordi nå dette block--

352
00:17:37,860 --> 00:17:42,050
Legg merke til hvordan denne "hvis på kanten,
bounce "er slags selvstendig.

353
00:17:42,050 --> 00:17:43,704
Så jeg trenger å fikse dette.

354
00:17:43,704 --> 00:17:44,870
La meg gå videre og gjøre dette.

355
00:17:44,870 --> 00:17:48,630
La meg bli kvitt dette og gå tilbake
til vår opprinnelige, mer bevisst

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

357
00:17:49,870 --> 00:18:01,080
Så "hvis berøre kanten, deretter" Jeg vil ha
å svinge, som Victoria foreslått,

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

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

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

361
00:18:11,800 --> 00:18:15,580
>> Ja, merker det er utenfor
den gule blokken.

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

363
00:18:17,680 --> 00:18:21,290
Så jeg kommer til å dra den opp her,
og innkalling nå er det inne i "hvis".

364
00:18:21,290 --> 00:18:24,250
Så "hvis" er denne typen
av som arm-lignende blot

365
00:18:24,250 --> 00:18:26,260
det er bare kommer til å
gjøre det som er på innsiden av det.

366
00:18:26,260 --> 00:18:30,216
Så nå hvis jeg zoomer ut på
risikoen for annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Au, au, au.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: Og det
vil bare fortsette i det uendelige.

370
00:18:39,910 --> 00:18:44,160
Nå bare å akselerere ting
her, la meg gå videre og åpne opp,

371
00:18:44,160 --> 00:18:50,460
la oss say-- la meg gå til noen
av mine egne ting fra klassen.

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

373
00:18:53,000 --> 00:19:00,220
Og la meg åpne opp, la oss si, dette
en laget av en av våre undervisnings fellows

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

375
00:19:01,500 --> 00:19:04,732
Så noen av dere kanskje husker
dette spillet fra en svunnen tid,

376
00:19:04,732 --> 00:19:05,940
og det er faktisk bemerkelsesverdig.

377
00:19:05,940 --> 00:19:08,190
Selv om vi har gjort
enkleste av programmer akkurat nå,

378
00:19:08,190 --> 00:19:09,980
la oss vurdere hva dette
faktisk ser ut.

379
00:19:09,980 --> 00:19:10,650
La meg trykke play.

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

381
00:19:14,210 --> 00:19:18,980
>> Så i dette spillet, har vi en
frosk, og bruke pil keys--

382
00:19:18,980 --> 00:19:23,340
han tar større skritt enn jeg remember--
Jeg har kontroll over denne frosken.

383
00:19:23,340 --> 00:19:29,630
Og målet er å komme over den travle
veien uten å kjøre inn i biler.

384
00:19:29,630 --> 00:19:34,735
Og la oss see-- hvis jeg går opp her, jeg
må vente på en logg for å bla forbi.

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

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

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

388
00:19:42,240 --> 00:19:43,495
Dette er en type insekt.

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

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

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

392
00:19:51,550 --> 00:19:54,100
til du får alle
Froskene til lily pads.

393
00:19:54,100 --> 00:19:55,920
Nå kan dette se
alle de mer komplekse,

394
00:19:55,920 --> 00:19:57,840
men la oss prøve å bryte
dette ned mentalt

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

396
00:20:00,040 --> 00:20:03,910
Så det er nok et puslespill
brikke som vi ikke har sett ennå

397
00:20:03,910 --> 00:20:07,440
men det er å svare på tastetrykk,
til ting jeg traff på tastaturet.

398
00:20:07,440 --> 00:20:11,660
>> Så det er nok en slags
blokk som sier, hvis nøkkelen er lik opp,

399
00:20:11,660 --> 00:20:15,965
deretter gjøre noe med Scratch--
kanskje flytte den 10 meter på denne måten.

400
00:20:15,965 --> 00:20:20,240
Hvis ned-tasten trykkes inn, flytte 10 trinn
denne måten, eller venstre tast, flytte 10 trinn

401
00:20:20,240 --> 00:20:21,710
denne måten, 10 trinn som.

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

403
00:20:23,644 --> 00:20:26,060
Så det er bare der
kostyme, som skrape samtaler it-- vi

404
00:20:26,060 --> 00:20:28,440
bare importert et bilde av frosken.

405
00:20:28,440 --> 00:20:29,570
>> Men hva annet som skjer?

406
00:20:29,570 --> 00:20:32,794
Hvilke andre linjer med kode,
hva andre brikkene

407
00:20:32,794 --> 00:20:35,460
gjorde Blake, vår undervisning stipendiat,
bruker i dette programmet, tilsynelatende?

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

409
00:20:38,320 --> 00:20:42,730
Hva gjør alt move--
hva programmering konstruere?

410
00:20:42,730 --> 00:20:44,950
>> Motion, sure-- så
flytte blokken, sikkert.

411
00:20:44,950 --> 00:20:49,330
Og hva er det trekk blokk
innside, mest sannsynlig?

412
00:20:49,330 --> 00:20:52,850
Ja, en slags loop, kanskje en
alltid blokkere, kanskje en gjentakelse block--

413
00:20:52,850 --> 00:20:54,070
gjenta til blokken.

414
00:20:54,070 --> 00:20:57,330
Og det er det som gjør loggene og
lily pads og alt annet trekk

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

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

417
00:21:00,270 --> 00:21:03,180
>> Hvorfor er noen av bilene
beveger seg raskere enn de andre?

418
00:21:03,180 --> 00:21:06,607
Hva er annerledes med disse programmene?

419
00:21:06,607 --> 00:21:09,690
Ja, sannsynligvis noen av dem tar
flere trinn på en gang, og noen av dem

420
00:21:09,690 --> 00:21:10,690
færre trinn på en gang.

421
00:21:10,690 --> 00:21:14,670
Og den visuelle effekten
er rask versus treg.

422
00:21:14,670 --> 00:21:16,030
>> Hva tror du skjedde?

423
00:21:16,030 --> 00:21:19,700
Da jeg fikk min frosk hele veien
over gaten og elven

424
00:21:19,700 --> 00:21:23,560
på lilje pad, noe
bemerkelsesverdig skjedde.

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

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

427
00:21:27,210 --> 00:21:29,680
Det frosk stoppet, og
Jeg fikk en andre frosk.

428
00:21:29,680 --> 00:21:33,155
Så hva konstruksjonen må være
brukes der, hva funksjonen?

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

430
00:21:36,020 --> 00:21:38,660
>> Ja, så det er en slags
"Hvis" tilstand der oppe også.

431
00:21:38,660 --> 00:21:41,909
Og det viser out-- vi ikke se dette--
men det er andre blokker i det som

432
00:21:41,909 --> 00:21:45,300
kan si, hvis du er rørende
en annen ting på skjermen,

433
00:21:45,300 --> 00:21:47,720
hvis du berører den lilje pad ", da."

434
00:21:47,720 --> 00:21:50,810
Og så det er når vi
gjøre andre frosken vises.

435
00:21:50,810 --> 00:21:54,969
Så selv om dette spillet er absolutt
svært datert, selv om ved første øyekast

436
00:21:54,969 --> 00:21:58,010
det er så mye som skjer on-- og Blake
ikke piske dette opp i to minutter,

437
00:21:58,010 --> 00:22:00,390
det sannsynligvis tok ham flere
timer å lage dette spillet

438
00:22:00,390 --> 00:22:03,850
basert på hans minne eller videoer
av en svunnen versjon av den.

439
00:22:03,850 --> 00:22:07,940
Men alle disse små tingene
kommer på skjermen i isolasjon

440
00:22:07,940 --> 00:22:11,550
koke ned til disse svært enkle
constructs-- bevegelser eller uttalelser

441
00:22:11,550 --> 00:22:15,519
som vi har diskutert, sløyfer og
forhold, og det er omtrent det.

442
00:22:15,519 --> 00:22:17,060
Det er et par andre mer avansert funksjoner.

443
00:22:17,060 --> 00:22:19,130
Noen av dem er utelukkende
estetisk eller akustisk,

444
00:22:19,130 --> 00:22:20,964
som lydene jeg bare spilt med.

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

446
00:22:23,380 --> 00:22:25,350
alle de fundamentale
byggeklosser 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 en rekke andre språk.

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

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

451
00:22:37,220 --> 00:22:40,303
Så vi vil ikke dykke i dypere til Scratch,
om du er velkommen denne helgen,

452
00:22:40,303 --> 00:22:42,860
spesielt hvis du har barn eller
nieser og nevøer og slikt,

453
00:22:42,860 --> 00:22:44,220
å introdusere dem til å klø.

454
00:22:44,220 --> 00:22:47,960
Det er faktisk en fantastisk leken
miljø med, som sine forfattere sier,

455
00:22:47,960 --> 00:22:49,120
svært høye tak.

456
00:22:49,120 --> 00:22:51,670
Selv om vi startet med
svært lavt nivå detaljer,

457
00:22:51,670 --> 00:22:54,890
du virkelig kan gjøre ganske mye
med det, og dette er kanskje

458
00:22:54,890 --> 00:22:57,360
en demonstrasjon av nettopp det.

459
00:22:57,360 --> 00:23:02,920
>> Men la oss nå gå over til litt mer
sofistikerte problemer, om du vil,

460
00:23:02,920 --> 00:23:05,870
kjent som "søker" og
"Sortering", mer generelt.

461
00:23:05,870 --> 00:23:09,500
Vi hadde denne telefonboken earlier-- her er
en annen bare for discussion--

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

463
00:23:13,460 --> 00:23:15,270
av en betydelig forutsetning.

464
00:23:15,270 --> 00:23:17,655
Og bare for å være klar, hva
forutsetningen var jeg gjør

465
00:23:17,655 --> 00:23:19,280
når du søker gjennom denne telefonboken?

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

467
00:23:23,342 --> 00:23:25,300
At Mike Smith var i
telefonboken, selv om jeg

468
00:23:25,300 --> 00:23:27,410
ville være i stand til å håndtere
scenariet uten ham

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

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

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

472
00:23:33,930 --> 00:23:36,580
betyr someone-- Jeg er litt
for å kutte et hjørne,

473
00:23:36,580 --> 00:23:40,580
som jeg er raskere fordi noen
andre gjorde mye hardt arbeid for meg.

474
00:23:40,580 --> 00:23:43,120
>> Men hva hvis telefonen
Boken ble usortert?

475
00:23:43,120 --> 00:23:47,050
Kanskje Verizon fikk lat, bare kastet
alles navn og numre i det

476
00:23:47,050 --> 00:23:50,120
kanskje i den rekkefølgen de
meldt seg på telefonen.

477
00:23:50,120 --> 00:23:54,570
Og hvor lang tid tar det meg
å finne noen som Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 side telefon book-- hvor mange
sidene må jeg se gjennom?

479
00:23:58,160 --> 00:23:58,905
>> Alle sammen.

480
00:23:58,905 --> 00:24:00,030
Du er liksom ute av lykken.

481
00:24:00,030 --> 00:24:03,420
Du har bokstavelig talt å se på hver
siden hvis telefonboken er bare

482
00:24:03,420 --> 00:24:04,450
tilfeldig sortert.

483
00:24:04,450 --> 00:24:06,910
Du kan ha flaks og finne Mike
på den aller første siden, fordi han

484
00:24:06,910 --> 00:24:08,826
var den første kunden
å bestille telefonen tjenesten.

485
00:24:08,826 --> 00:24:10,760
Men han kan ha vært den siste, også.

486
00:24:10,760 --> 00:24:12,500
>> Så tilfeldig rekkefølge er ikke bra.

487
00:24:12,500 --> 00:24:16,750
Så antar at vi må sortere
telefonboken eller generelt slags data

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

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

490
00:24:19,440 --> 00:24:21,360
>> Vel, la meg bare prøve
et enkelt eksempel her.

491
00:24:21,360 --> 00:24:24,290
La meg gå videre og kaste en
få tall på bordet.

492
00:24:24,290 --> 00:24:35,480
Anta at tallene vi har er,
la oss si, fire, to, en, og tre.

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

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

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
Greit.

498
00:24:43,230 --> 00:24:44,710
Så starte med den minste
verdi og den høyeste,

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

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

501
00:24:48,080 --> 00:24:49,913
flink til å løse problemer
som dette, i det minste

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

503
00:24:51,810 --> 00:24:54,860
Så snart du begynner å ha hundrevis
av tall, tusenvis av tall,

504
00:24:54,860 --> 00:24:58,440
millioner av tall, Ben sannsynligvis
kunne ikke gjøre det ganske så fort,

505
00:24:58,440 --> 00:25:00,620
når det ses
hull i tallene.

506
00:25:00,620 --> 00:25:03,450
Ganske enkelt å telle til en million
ellers bare tidkrevende.

507
00:25:03,450 --> 00:25:07,150
>> Så algoritmen det høres
som Ben brukes akkurat nå

508
00:25:07,150 --> 00:25:08,930
var jakten på det minste tallet.

509
00:25:08,930 --> 00:25:12,900
Så selv om vi mennesker kan ta
i mye informasjon visuelt,

510
00:25:12,900 --> 00:25:14,830
en datamaskin er faktisk
en litt mer begrenset.

511
00:25:14,830 --> 00:25:17,560
Den kan datamaskinen bare
se på en byte om gangen

512
00:25:17,560 --> 00:25:20,770
eller kanskje fire byte på en tid--
disse dager kanskje 8 byte på en tid--

513
00:25:20,770 --> 00:25:24,450
men et meget lite antall
av bytes på et gitt tidspunkt.

514
00:25:24,450 --> 00:25:28,480
>> Så gitt at vi virkelig har
fire separate verdier her--

515
00:25:28,480 --> 00:25:32,440
og du kan tenke på Ben som å ha
skylapper på om han var en datamaskin slik

516
00:25:32,440 --> 00:25:36,450
at han ikke kan se noe annet
enn ett nummer om tid--

517
00:25:36,450 --> 00:25:39,720
så vi vanligvis vil anta, som i
Engelsk, vil vi lese fra høyre mot venstre.

518
00:25:39,720 --> 00:25:42,870
Så det første nummeret Ben sannsynligvis sett
på var fire og deretter svært raskt

519
00:25:42,870 --> 00:25:44,770
innsett at det er en ganske stor
number-- la meg holde utkikk.

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

521
00:25:45,357 --> 00:25:45,940
Vent litt.

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

523
00:25:47,070 --> 00:25:47,986
Jeg kommer til å huske.

524
00:25:47,986 --> 00:25:49,070
To er nå den minste.

525
00:25:49,070 --> 00:25:50,417
Nå one-- som er enda bedre.

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

527
00:25:51,250 --> 00:25:54,000
Jeg kommer til å glemme to
og bare husk en nå.

528
00:25:54,000 --> 00:25:56,550
>> Og kan han slutte å se?

529
00:25:56,550 --> 00:25:58,360
Vel, han kunne basert
på denne informasjonen,

530
00:25:58,360 --> 00:26:00,477
men han hadde bedre søk
resten av listen.

531
00:26:00,477 --> 00:26:02,060
Fordi hva om null var på listen?

532
00:26:02,060 --> 00:26:03,643
Hva om negativt var på listen?

533
00:26:03,643 --> 00:26:07,720
Han vet bare at hans svar
er riktig hvis han er uttømmende

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

535
00:26:08,729 --> 00:26:10,020
Så vi ser på resten av dette.

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

537
00:26:11,394 --> 00:26:13,540
Fikk uheldig, men jeg var
fortsatt er riktig å gjøre det.

538
00:26:13,540 --> 00:26:17,857
Og så nå er han antagelig
valgt minste tallet

539
00:26:17,857 --> 00:26:20,440
og bare sette den i begynnelsen
av listen, som jeg skal gjøre her.

540
00:26:20,440 --> 00:26:23,480
Nå hva gjorde du gjøre videre, selv om
du ikke tenke på det nesten

541
00:26:23,480 --> 00:26:25,962
i denne grad?

542
00:26:25,962 --> 00:26:27,670
Gjenta prosessen,
så en slags loop.

543
00:26:27,670 --> 00:26:28,920
Det er en kjent 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 for tiden den minste.

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

547
00:26:33,220 --> 00:26:33,900
Ikke nå lenger.

548
00:26:33,900 --> 00:26:34,770
Nå har jeg sett to.

549
00:26:34,770 --> 00:26:36,630
Det er den nest minste element.

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

551
00:26:40,800 --> 00:26:44,510
>> Og nå gjentar vi prosessen, og
selvfølgelig tre blir trukket ut neste.

552
00:26:44,510 --> 00:26:45,420
Gjenta prosessen.

553
00:26:45,420 --> 00:26:46,990
Fire blir trukket ut.

554
00:26:46,990 --> 00:26:50,140
Og nå er vi ute av tall,
så listen skal sorteres.

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

556
00:26:51,960 --> 00:26:56,610
En datamaskin vitenskapsmann ville
kaller dette "valget sort,"

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

558
00:27:00,880 --> 00:27:03,807
og igjen og igjen velge
det minste tallet.

559
00:27:03,807 --> 00:27:06,140
Og hva er fint om det er
det er bare så utrolig intuitiv.

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

561
00:27:07,470 --> 00:27:11,100
Og du kan gjenta det samme
drift igjen og igjen.

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

563
00:27:12,150 --> 00:27:17,170
>> I dette tilfellet var det raskt, men
hvor lang tid det faktisk tar?

564
00:27:17,170 --> 00:27:19,880
La oss gjøre det virke og
føler meg litt mer kjedelig.

565
00:27:19,880 --> 00:27:24,150
Så en, to, tre, fire, fem seks,
syv, åtte, ni, ti, elleve, tolv, tretten, fjorten,

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

567
00:27:26,160 --> 00:27:28,780
Jeg ville bare mer dette
tid enn bare de fire.

568
00:27:28,780 --> 00:27:30,780
Så hvis jeg har en hel
haug av tall now-- det

569
00:27:30,780 --> 00:27:32,420
ikke engang saken
hva de are-- la oss

570
00:27:32,420 --> 00:27:34,380
tenke på hva dette
algoritmen egentlig er.

571
00:27:34,380 --> 00:27:35,857
>> Anta at det er tall der.

572
00:27:35,857 --> 00:27:38,190
Igjen, spiller ingen rolle hva
de er, men de er tilfeldige.

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

574
00:27:39,679 --> 00:27:41,220
Jeg må velge det minste tallet.

575
00:27:41,220 --> 00:27:41,761
Hva gjør jeg?

576
00:27:41,761 --> 00:27:44,240
Og jeg kommer til fysisk
gjøre det denne gangen til å handle det ut.

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

578
00:27:46,099 --> 00:27:48,140
Bare av den tiden jeg får til
enden av listen kan

579
00:27:48,140 --> 00:27:51,230
Jeg skjønner de minste
tallet var to denne gangen.

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 ned to.

582
00:27:54,400 --> 00:27:55,590
>> Hva gjør jeg nå?

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

584
00:27:58,600 --> 00:28:02,250
Nå fant jeg nummer syv, fordi
det er hull i disse numbers--

585
00:28:02,250 --> 00:28:03,300
men bare tilfeldig.

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

587
00:28:03,800 --> 00:28:06,030
Så nå kan jeg legge ned syv.

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

589
00:28:08,860 --> 00:28:11,030
>> Nå er jeg forutsatt,
Selvfølgelig, at Ben ikke

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

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

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

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

594
00:28:19,930 --> 00:28:22,610
Men hvis Ben husker alle
av tallene han har sett,

595
00:28:22,610 --> 00:28:24,430
Han har egentlig ikke gjort
fundamental fremgang

596
00:28:24,430 --> 00:28:26,170
fordi han allerede har
muligheten til å søke

597
00:28:26,170 --> 00:28:27,540
gjennom tallene på brettet.

598
00:28:27,540 --> 00:28:29,373
Huske alle
tallene ikke hjelper,

599
00:28:29,373 --> 00:28:32,490
fordi han kan stille som en datamaskin
bare se på, vi har sagt, ett tall

600
00:28:32,490 --> 00:28:33,080
på en gang.

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

602
00:28:35,760 --> 00:28:39,170
>> Så i virkeligheten, som jeg
fortsette å søke i listen,

603
00:28:39,170 --> 00:28:44,200
Jeg har bokstavelig talt å bare holde det gående
frem og tilbake gjennom det, plukker ut

604
00:28:44,200 --> 00:28:45,710
neste minste tallet.

605
00:28:45,710 --> 00:28:48,810
Og som du kan slags antyde
fra mine dumme bevegelser,

606
00:28:48,810 --> 00:28:50,860
dette blir bare veldig
kjedelige veldig raskt,

607
00:28:50,860 --> 00:28:54,850
og jeg synes å være å gå tilbake og
frem, frem og tilbake ganske mye.

608
00:28:54,850 --> 00:29:03,220
Nå for å være rettferdig, jeg må gå
ganske så, vel, la oss see-- å være rettferdig,

609
00:29:03,220 --> 00:29:06,310
Jeg trenger ikke å gå helt
så mange skritt hver gang.

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

611
00:29:09,200 --> 00:29:11,860
de resterende listen blir kortere.

612
00:29:11,860 --> 00:29:14,240
>> Og så la oss tenke på
hvor mange skritt jeg faktisk

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

614
00:29:16,010 --> 00:29:18,950
I den aller første situasjonen
vi hadde 16 tall,

615
00:29:18,950 --> 00:29:22,210
og så maximally-- la oss bare
gjør dette for en discussion--

616
00:29:22,210 --> 00:29:25,640
Jeg måtte se gjennom 16
tall for å finne den minste.

617
00:29:25,640 --> 00:29:28,420
Men når jeg plukket ut
det minste tallet, hvor

618
00:29:28,420 --> 00:29:30,590
lenge var de resterende liste, selvfølgelig?

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

620
00:29:31,420 --> 00:29:34,670
Så hvor mange tall gjorde Ben eller jeg har
å se gjennom den andre gangen?

621
00:29:34,670 --> 00:29:36,832
15, bare for å gå og finne den minste.

622
00:29:36,832 --> 00:29:39,540
Men nå, selvfølgelig, er på listen,
også, er mindre enn det var før.

623
00:29:39,540 --> 00:29:42,540
Så hvor mange skritt gjorde jeg
nødt til å ta det neste gang?

624
00:29:42,540 --> 00:29:49,970
14 og deretter 13 og så 12, pluss dot,
prikk, prikk, før jeg sitter igjen med kun én.

625
00:29:49,970 --> 00:29:53,146
Så nå en datamaskin vitenskapsmann ville
spør, vel, hva gjør det alle like?

626
00:29:53,146 --> 00:29:55,770
Det faktisk er lik noen konkrete
nummer som vi kunne sikkert

627
00:29:55,770 --> 00:30:00,490
gjøre arithmetically, men vi ønsker å snakke
om effektiviteten av algoritmer

628
00:30:00,490 --> 00:30:04,940
litt mer formulaically,
uavhengig av hvor lang listen er.

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

630
00:30:06,240 --> 00:30:09,860
Dette er 16, men som jeg sa før,
la oss bare kalle størrelsen på problemet

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

632
00:30:10,970 --> 00:30:13,220
Kanskje det er 16, kanskje det er
tre, kanskje det er en million.

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

634
00:30:13,761 --> 00:30:14,390
Jeg bryr meg ikke.

635
00:30:14,390 --> 00:30:16,520
Det jeg egentlig ønsker er
en formel som jeg kan

636
00:30:16,520 --> 00:30:19,420
bruke til å sammenligne denne algoritmen
mot andre algoritmer

637
00:30:19,420 --> 00:30:22,350
at noen kan hevde
er bedre eller verre.

638
00:30:22,350 --> 00:30:25,430
>> Så det viser seg, og jeg bare
vet dette fra grunnskolen,

639
00:30:25,430 --> 00:30:34,790
at dette faktisk funker til det samme
ting som n på n pluss en over to.

640
00:30:34,790 --> 00:30:40,020
Og dette skjer til lik, av
Selvfølgelig n kvadrat pluss n over to.

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

642
00:30:43,250 --> 00:30:46,330
var involvert i å se i det hele tatt
av disse tallene igjen og igjen

643
00:30:46,330 --> 00:30:52,681
og igjen og igjen, vil jeg si
det er n kvadrat pluss n over to.

644
00:30:52,681 --> 00:30:53,430
Men vet du hva?

645
00:30:53,430 --> 00:30:54,500
Dette ser bare rotete.

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

647
00:30:56,470 --> 00:30:58,810
Og du kanskje husker fra
videregående skole at det

648
00:30:58,810 --> 00:31:00,660
er oppfatningen av høyeste orden sikt.

649
00:31:00,660 --> 00:31:05,300
Hvilke av disse vilkårene, n
kvadrat, n, eller den halve,

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

651
00:31:07,550 --> 00:31:11,920
Jo større n blir, som
av disse teller mest?

652
00:31:11,920 --> 00:31:15,560
>> Med andre ord, hvis jeg kobler
i en million, n squared

653
00:31:15,560 --> 00:31:17,900
kommer til å være mest sannsynlig
den dominerende faktor,

654
00:31:17,900 --> 00:31:21,670
en million fordi ganger
i seg selv er mye større

655
00:31:21,670 --> 00:31:23,682
enn pluss en ekstra million.

656
00:31:23,682 --> 00:31:24,390
Så vet du hva?

657
00:31:24,390 --> 00:31:27,305
Dette er en så darn stor
nummer hvis du kvadrere et tall.

658
00:31:27,305 --> 00:31:28,430
Dette spiller ingen rolle.

659
00:31:28,430 --> 00:31:30,596
Vi kommer bare til korset som
ut og glemme det.

660
00:31:30,596 --> 00:31:34,250
Og så en datamaskin vitenskapsmann vil si
at virkningsgraden av denne algoritmen

661
00:31:34,250 --> 00:31:37,850
er i størrelsesorden n squared--
Jeg mener virkelig en tilnærming.

662
00:31:37,850 --> 00:31:40,810
Det er liksom omtrent n squared.

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

664
00:31:44,130 --> 00:31:47,610
er et godt anslag for hva
effektivitet eller mangel på effektivitet

665
00:31:47,610 --> 00:31:49,400
av denne algoritmen faktisk er.

666
00:31:49,400 --> 00:31:52,040
Og jeg utlede det, selvfølgelig,
fra faktisk gjør regnestykket.

667
00:31:52,040 --> 00:31:54,040
Men nå er jeg bare vinke
hendene mine, fordi jeg bare

668
00:31:54,040 --> 00:31:55,790
ønsker en generell følelse av denne algoritmen.

669
00:31:55,790 --> 00:31:58,850
>> Så bruker den samme logikken, i mellomtiden,
la oss vurdere en annen algoritme

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

671
00:32:01,162 --> 00:32:02,870
Når jeg søker
for telefonen book--

672
00:32:02,870 --> 00:32:05,980
ikke sortere det, søking
gjennom telefonen book--

673
00:32:05,980 --> 00:32:09,197
Vi fortsatte å si at det var
1000 trinn, eller 500 trinn.

674
00:32:09,197 --> 00:32:10,280
Men la oss generalisere det.

675
00:32:10,280 --> 00:32:12,860
Hvis det er n sider
telefonboken, hva er

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

677
00:32:17,250 --> 00:32:19,750
Det er i størrelsesorden
hvor mange skritt for å finne

678
00:32:19,750 --> 00:32:24,210
Mike Smith ved hjelp av lineær søk, jo
første algoritme, eller til og med den andre?

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

680
00:32:27,240 --> 00:32:31,710
>> I verste fall, Mike
er ved slutten av boken.

681
00:32:31,710 --> 00:32:35,590
Så hvis telefonboken har 1000 sider,
vi sa sist gang, i verste fall,

682
00:32:35,590 --> 00:32:38,380
det kan ta omtrent hvor
mange sider for å finne Mike?

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

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

685
00:32:39,830 --> 00:32:41,790
Det er en verst tenkelige situasjon.

686
00:32:41,790 --> 00:32:44,410
Men igjen, vi beveger seg bort
fra tall som 1000 nå.

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

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

689
00:32:47,470 --> 00:32:50,210
Finne Mike i en telefon
bok som har n sider

690
00:32:50,210 --> 00:32:55,280
kan ta, i det aller verste fall
hvor mange trinn i størrelsesorden av n?

691
00:32:55,280 --> 00:32:58,110
Og faktisk en datamaskin
vitenskapsmann vil si

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

693
00:33:02,340 --> 00:33:07,470
eller ineffektivitet, av en algoritme som
en lineær søk er i størrelsesorden n.

694
00:33:07,470 --> 00:33:10,010
Og vi kan bruke den samme
Logikken i krysset noe ut

695
00:33:10,010 --> 00:33:13,170
som jeg nettopp gjorde med den andre
algoritme vi hadde med telefonboken,

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

697
00:33:16,040 --> 00:33:20,120
>> Så tusen side telefonbok kanskje
ta oss 500 side svinger, pluss en

698
00:33:20,120 --> 00:33:21,910
hvis vi dobbelt tilbake litt.

699
00:33:21,910 --> 00:33:26,590
Så hvis en telefon bok har n sider, men
vi gjør to sider om gangen,

700
00:33:26,590 --> 00:33:28,900
det er omtrent hva?

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

702
00:33:33,190 --> 00:33:38,490
Men jeg gjorde krav en
øyeblikk siden at n løpet two--

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

704
00:33:41,060 --> 00:33:44,050
Det er bare en konstant faktor,
IT-forskere vil si.

705
00:33:44,050 --> 00:33:45,970
La oss bare fokusere på
variablene, really--

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

707
00:33:47,780 --> 00:33:52,530
>> Så lineær søk, enten gjort en
side om gangen eller to sider om gangen,

708
00:33:52,530 --> 00:33:54,810
er liksom fundamentalt det samme.

709
00:33:54,810 --> 00:33:56,880
Det er fortsatt i størrelsesorden n.

710
00:33:56,880 --> 00:34:01,930
Men jeg hevdet med mitt bilde 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 rett linje.

713
00:34:03,605 --> 00:34:08,659
Det var den buede linje, og den
algebraisk formel det var det?

714
00:34:08,659 --> 00:34:11,812
Logg av N- så log base to av n.

715
00:34:11,812 --> 00:34:14,520
Og vi trenger ikke å gå inn i for
mye detaljer på logaritmer i dag,

716
00:34:14,520 --> 00:34:17,394
men de fleste dataforskere ville ikke
også fortelle deg hva basen er.

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

718
00:34:20,639 --> 00:34:22,659
bare små numeriske forskjeller.

719
00:34:22,659 --> 00:34:31,179
Og så dette ville være en svært vanlig
måte for spesielt formell datamaskin

720
00:34:31,179 --> 00:34:33,949
forskere ved et bord eller
programmerere på et hvitt bord

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

722
00:34:36,889 --> 00:34:39,500
eller hva virkningsgraden
av sin algoritme er.

723
00:34:39,500 --> 00:34:42,960
>> Og dette er ikke nødvendigvis noe
du diskutere i noen stor detalj,

724
00:34:42,960 --> 00:34:47,889
men en god programmerer er noen
som har en solid, formell bakgrunn.

725
00:34:47,889 --> 00:34:50,120
Han er i stand til å snakke med
deg i denne slags måte

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

727
00:34:53,350 --> 00:34:56,870
hvorfor en algoritme eller
ett stykke programvare

728
00:34:56,870 --> 00:35:00,165
er overlegen på noen måte til en annen.

729
00:35:00,165 --> 00:35:02,540
Fordi du kan sikkert
bare kjøre en persons program

730
00:35:02,540 --> 00:35:04,980
og telle antall sekunder
det tar å sortere noen tall,

731
00:35:04,980 --> 00:35:06,710
og du kan kjøre noen
andre personens program

732
00:35:06,710 --> 00:35:08,418
og telle antall
sekunder det tar.

733
00:35:08,418 --> 00:35:12,840
Men dette er en mer generell måte at
du kan bruke til å analysere algoritmer,

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

735
00:35:15,520 --> 00:35:18,430
Uten engang å kjøre det, uten
selv prøver prøve innganger,

736
00:35:18,430 --> 00:35:20,180
du kan bare resonnere gjennom den.

737
00:35:20,180 --> 00:35:24,670
Og så med å ansette en utvikler eller hvis
å ha ham eller henne liksom argumentere for deg

738
00:35:24,670 --> 00:35:28,460
hvorfor deres algoritme, deres hemmelighet
saus for å søke milliarder

739
00:35:28,460 --> 00:35:30,580
av websider for din
Selskapet er bedre, disse

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

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

742
00:35:35,010 --> 00:35:40,211
som ville komme opp i diskusjonen, ved
det minste i en meget formell diskusjon.

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

744
00:35:40,710 --> 00:35:44,400
Så Ben foreslått noe
kalt utvalg slag.

745
00:35:44,400 --> 00:35:48,200
Men jeg kommer til å foreslå at det er
andre måter å gjøre dette, også.

746
00:35:48,200 --> 00:35:50,400
Hva jeg ikke liker
om Ben algoritme

747
00:35:50,400 --> 00:35:54,400
er at han fortsatte å gå, eller
ha meg til å gå frem og tilbake

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

749
00:35:56,930 --> 00:36:04,130
Hva om i stedet jeg skulle gjøre
noe sånt som disse tallene her

750
00:36:04,130 --> 00:36:08,200
og jeg skulle bare forholde seg til hverandre
Tallet i sving som jeg får det?

751
00:36:08,200 --> 00:36:10,780
>> Med andre ord, her
min liste med tall.

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

753
00:36:12,944 --> 00:36:14,360
Og jeg kommer til å gjøre følgende.

754
00:36:14,360 --> 00:36:17,230
Jeg kommer til å sette inn tallene
der de hører heller

755
00:36:17,230 --> 00:36:18,980
Bortsett fra å velge dem en om 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 mitt opprinnelige listen.

758
00:36:22,430 --> 00:36:25,290
Og jeg kommer til å opprettholde
hovedsak en ny liste her.

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

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 listen er i utgangspunktet tom,
slik det er trivielt tilfellet

763
00:36:34,500 --> 00:36:36,410
at fire er nå assortert listen.

764
00:36:36,410 --> 00:36:39,560
Jeg er bare å ta antall jeg får,
og jeg setter det i min nye liste.

765
00:36:39,560 --> 00:36:41,460
>> Er dette nye listen sortert?

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

767
00:36:41,990 --> 00:36:45,090
Det er dumt, fordi det er bare en
element, men det er absolutt sortert.

768
00:36:45,090 --> 00:36:46,390
Det er ikke noe malplassert.

769
00:36:46,390 --> 00:36:49,290
Det er mer interessant, denne algoritmen,
når jeg flytter til neste trinn.

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

771
00:36:50,550 --> 00:36:55,430
Så en, selvfølgelig, hører i
begynnelse eller slutten av denne nye listen?

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

773
00:36:56,360 --> 00:36:58,530
Så jeg må gjøre noe arbeid nå.

774
00:36:58,530 --> 00:37:01,410
Jeg har tatt noen
friheter med markør min

775
00:37:01,410 --> 00:37:03,120
ved bare å tegne ting
der jeg vil ha dem,

776
00:37:03,120 --> 00:37:05,320
men det er egentlig ikke
nøyaktig i en datamaskin.

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

778
00:37:08,530 --> 00:37:12,411
og det er en byte og
en annen byte og en annen 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å ett sted.

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

782
00:37:19,540 --> 00:37:20,750
når du vil.

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

784
00:37:24,090 --> 00:37:27,480
dessverre fire er
allerede på feil sted.

785
00:37:27,480 --> 00:37:30,410
>> Så for å sette inn nummer én
Jeg kan ikke bare trekke den her.

786
00:37:30,410 --> 00:37:31,901
Denne minneområde finnes ikke.

787
00:37:31,901 --> 00:37:35,150
Det ville være juks, og jeg har vært
juks billedlig i noen minutter

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

789
00:37:35,800 --> 00:37:40,950
Så egentlig, hvis jeg ønsker å sette en her,
Jeg må midlertidig kopiere fire

790
00:37:40,950 --> 00:37:43,030
og deretter sette den der.

791
00:37:43,030 --> 00:37:45,500
>> Det er greit, det er riktig,
det er teknisk mulig,

792
00:37:45,500 --> 00:37:48,410
men skjønner det er ekstra arbeid.

793
00:37:48,410 --> 00:37:50,460
Jeg hadde ikke bare sette tall på plass.

794
00:37:50,460 --> 00:37:53,026
Jeg først måtte flytte en
nummer, og deretter sette den på plass,

795
00:37:53,026 --> 00:37:54,650
så jeg slags doblet mengden arbeid.

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

797
00:37:55,660 --> 00:37:57,120
>> Men jeg er nå ferdig med dette elementet.

798
00:37:57,120 --> 00:37:59,056
Nå ønsker jeg å ta tak i nummer tre.

799
00:37:59,056 --> 00:38:00,430
Der er selvfølgelig hører det?

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

801
00:38:01,480 --> 00:38:03,650
Jeg kan ikke jukse lenger
og bare sette den der,

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

803
00:38:06,770 --> 00:38:10,900
Så jeg må kopiere fire
og sette tre over her.

804
00:38:10,900 --> 00:38:11,550
Ikke noe viktig.

805
00:38:11,550 --> 00:38:14,610
Det er bare ett ekstra trinn
igjen-- føles veldig billig.

806
00:38:14,610 --> 00:38:16,445
>> Men nå går jeg videre til de to.

807
00:38:16,445 --> 00:38:17,820
De to selvfølgelig hører her.

808
00:38:17,820 --> 00:38:20,990
Nå kan du begynne å se hvordan
arbeidet kan hope seg opp.

809
00:38:20,990 --> 00:38:23,520
Nå hva må jeg gjøre?

810
00:38:23,520 --> 00:38:28,570
Ja, jeg må flytte de fire,
Jeg må da kopiere de tre,

811
00:38:28,570 --> 00:38:31,200
og nå kan jeg sette inn to.

812
00:38:31,200 --> 00:38:34,460
Og fangsten med denne
algoritme, interessant nok,

813
00:38:34,460 --> 00:38:41,050
er at anta at vi har en mer ekstrem
tilfelle der det er la oss si åtte, sju,

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 sammenhenger,
worst case scenario,

816
00:38:49,450 --> 00:38:51,570
fordi det darn tingen
er bokstavelig talt bakover.

817
00:38:51,570 --> 00:38:53,670
>> Det gjør egentlig ikke
påvirke Ben algoritme,

818
00:38:53,670 --> 00:38:55,940
fordi i Bens utvalg
liksom han kommer til å holde

819
00:38:55,940 --> 00:38:58,359
går frem og tilbake gjennom listen.

820
00:38:58,359 --> 00:39:01,150
Og fordi han var alltid på utkikk
gjennom hele resten av listen,

821
00:39:01,150 --> 00:39:02,858
det spiller ingen rolle
hvor elementene er.

822
00:39:02,858 --> 00:39:05,630
Men i dette tilfellet med min innsetting
approach-- la oss prøve dette.

823
00:39:05,630 --> 00:39:08,616
>> Så en, to, tre, fire,
fem, seks, sju, åtte.

824
00:39:08,616 --> 00:39:11,630
En to tre fire,
fem, seks, sju, åtte.

825
00:39:11,630 --> 00:39:14,320
Jeg kommer til å ta åtte,
og hvor finner jeg si det?

826
00:39:14,320 --> 00:39:17,260
Vel, i begynnelsen av listen min,
fordi denne nye listen er sortert.

827
00:39:17,260 --> 00:39:18,760
Og jeg krysser den ut.

828
00:39:18,760 --> 00:39:20,551
>> Hvor plasserer jeg de sju?

829
00:39:20,551 --> 00:39:21,050
Filler'n.

830
00:39:21,050 --> 00:39:23,174
Det er behov for å gå dit, så
Jeg må gjøre noen kopiering.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Og nå syv går her.

833
00:39:28,480 --> 00:39:29,860
Nå går jeg videre til seks.

834
00:39:29,860 --> 00:39:30,980
Nå er det enda mer arbeid.

835
00:39:30,980 --> 00:39:32,570
>> Åtte har å gå her.

836
00:39:32,570 --> 00:39:33,920
Seven har å gå her.

837
00:39:33,920 --> 00:39:35,450
Nå seks kan gå her.

838
00:39:35,450 --> 00:39:37,950
Nå ta jeg de fem.

839
00:39:37,950 --> 00:39:40,560
Nå åtte må gå
her, har syv å gå her,

840
00:39:40,560 --> 00:39:43,650
seks har å gå her, og
nå fem og gjenta.

841
00:39:43,650 --> 00:39:46,610
Og jeg er ganske mye
flytte det hele tiden.

842
00:39:46,610 --> 00:39:52,950
>> Så på slutten, dette algorithm-- vi vil
kalle det innsetting sort-- faktisk

843
00:39:52,950 --> 00:39:55,020
har mye arbeid, også.

844
00:39:55,020 --> 00:39:56,970
Det er bare annerledes
slags arbeid enn Ben.

845
00:39:56,970 --> 00:40:00,090
Ben arbeid hadde meg gående
frem og tilbake hele tiden,

846
00:40:00,090 --> 00:40:03,510
velge den nest minste
element igjen og igjen.

847
00:40:03,510 --> 00:40:06,660
Så det var dette veldig visuell type arbeid.

848
00:40:06,660 --> 00:40:10,600
>> Denne andre algoritme, som fremdeles
correct-- det vil få jobben done--

849
00:40:10,600 --> 00:40:12,800
bare endrer mengden av arbeid.

850
00:40:12,800 --> 00:40:15,420
Det ser ut som i utgangspunktet du er
besparende, fordi du er bare

851
00:40:15,420 --> 00:40:19,190
arbeider med hvert element
opp foran uten å gå hele

852
00:40:19,190 --> 00:40:20,930
veien gjennom listen som Ben var.

853
00:40:20,930 --> 00:40:25,300
Men problemet er, spesielt i disse
gale tilfeller der det er alt bakover,

854
00:40:25,300 --> 00:40:27,830
du er bare slags
utsette det harde arbeidet

855
00:40:27,830 --> 00:40:30,360
før du må fikse dine feil.

856
00:40:30,360 --> 00:40:33,919
>> Og så hvis du kan forestille deg dette
åtte og sju og seks og fem

857
00:40:33,919 --> 00:40:36,710
og senere fire og tre og to
beveger seg gjennom listen,

858
00:40:36,710 --> 00:40:39,060
Vi har nettopp endret
type arbeid vi gjør.

859
00:40:39,060 --> 00:40:42,340
I stedet for å gjøre det på
begynnelsen av min iterasjon,

860
00:40:42,340 --> 00:40:45,250
Jeg bare gjør det på
slutten av hver iterasjon.

861
00:40:45,250 --> 00:40:50,550
Så det viser seg at denne algoritmen,
også, vanligvis kalt innsetting sortere,

862
00:40:50,550 --> 00:40:52,190
er også i størrelsesorden n squared.

863
00:40:52,190 --> 00:40:56,480
Det er faktisk ikke noe bedre,
ikke noe bedre i det hele tatt.

864
00:40:56,480 --> 00:41:00,810
>> Men det er en tredje tilnærming
Jeg vil oppfordre oss til å vurdere,

865
00:41:00,810 --> 00:41:02,970
som er denne.

866
00:41:02,970 --> 00:41:07,850
Så antar at min liste, for enkelhet
igjen, er fire, én, tre,

867
00:41:07,850 --> 00:41:11,080
two-- bare fire tall.

868
00:41:11,080 --> 00:41:13,300
Ben hadde god intuisjon,
god menneskelig intuisjon

869
00:41:13,300 --> 00:41:16,340
før, som vi festet hele
liste eventually-- innsetting slag.

870
00:41:16,340 --> 00:41:18,020
Jeg siktet oss sammen.

871
00:41:18,020 --> 00:41:22,530
Men la oss vurdere
enkleste måten å løse denne listen.

872
00:41:22,530 --> 00:41:24,110
>> Denne listen er ikke sortert.

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 sortert.

875
00:41:31,920 --> 00:41:33,400
Hva betyr det ikke skal sorteres?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: Det er ikke i rekkefølge.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Ikke sekvensiell.

878
00:41:34,990 --> 00:41:35,822
Gi meg et eksempel.

879
00:41:35,822 --> 00:41:37,180
>> STUDENT: Sett dem i rekkefølge.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Gi meg et mer konkret eksempel.

882
00:41:38,790 --> 00:41:39,832
>> STUDENT: stigende rekkefølge.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Ikke stigende rekkefølge.

884
00:41:41,206 --> 00:41:42,100
Være mer presis.

885
00:41:42,100 --> 00:41:45,190
Jeg vet ikke hva du mener med stigende.

886
00:41:45,190 --> 00:41:47,150
Hva er galt?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: Den minste av
tall er ikke i den første plass.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: Minste antall er
ikke i den første plass.

889
00:41:51,140 --> 00:41:52,120
Være mer spesifikk.

890
00:41:52,120 --> 00:41:55,000
Jeg begynner å ta på.

891
00:41:55,000 --> 00:41:59,470
Vi teller, men
hva som er i ustand her?

892
00:41:59,470 --> 00:42:00,707
>> STUDENT: Numerisk rekkefølge.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: Numerisk rekkefølge.

894
00:42:02,040 --> 00:42:04,248
Alles slags regnskap
det her-- svært høyt nivå.

895
00:42:04,248 --> 00:42:07,450
Bare bokstavelig fortelle meg hva som er
feil som en fem-åring makt.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: Pluss én.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Hva er det?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: Pluss én.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Hva mener du pluss en?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Gi meg en annen fem år gammel.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Hva er galt, mamma?

904
00:42:18,330 --> 00:42:19,940
Hva er galt, pappa?

905
00:42:19,940 --> 00:42:22,808
Hva mener du dette er ikke sortert?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: Det er ikke rett sted.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Hva er
ikke på rett sted?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Four.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, bra.

910
00:42:27,090 --> 00:42:29,110
Så fire er ikke der den skal være.

911
00:42:29,110 --> 00:42:30,590
Spesielt er dette sant?

912
00:42:30,590 --> 00:42:33,000
Fire og en, den første
to tallene jeg ser.

913
00:42:33,000 --> 00:42:34,930
Er dette riktig?

914
00:42:34,930 --> 00:42:36,427
Nei, de er ute av drift, ikke sant?

915
00:42:36,427 --> 00:42:38,135
Faktisk tror nå
om en datamaskin, også.

916
00:42:38,135 --> 00:42:40,824
Det kan bare se på kanskje en,
kanskje to ting på once--

917
00:42:40,824 --> 00:42:43,240
og faktisk bare én ting
på en gang, men det kan i det minste

918
00:42:43,240 --> 00:42:45,790
ser på en ting da
neste ting rett ved siden av 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å vet du hva?

922
00:42:48,740 --> 00:42:51,020
Hvorfor kan ikke vi ta babyen
trinn fikse dette problemet

923
00:42:51,020 --> 00:42:53,410
stedet for å gjøre disse fancy
algoritmer som Ben, der

924
00:42:53,410 --> 00:42:56,440
han er liksom fikse det ved
looping gjennom listen

925
00:42:56,440 --> 00:42:59,670
i stedet for å gjøre det jeg gjorde, hvor
Jeg bare slags fast det som vi går?

926
00:42:59,670 --> 00:43:03,650
La oss bare bokstavelig talt bryte ned
oppfatningen av order-- numerisk rekkefølge,

927
00:43:03,650 --> 00:43:06,990
kalle det hva du want--
inn i disse parvise sammenligninger.

928
00:43:06,990 --> 00:43:07,590
>> Fire og en.

929
00:43:07,590 --> 00:43:09,970
Er dette riktig rekkefølge?

930
00:43:09,970 --> 00:43:11,310
Så la oss fikse det.

931
00:43:11,310 --> 00:43:14,700
Ett og fire, og deretter
vi vil bare kopiere det.

932
00:43:14,700 --> 00:43:15,560
Greit, bra.

933
00:43:15,560 --> 00:43:17,022
Jeg fikset en og fire.

934
00:43:17,022 --> 00:43:18,320
Tre og to?

935
00:43:18,320 --> 00:43:18,820
Nei.

936
00:43:18,820 --> 00:43:21,690
La mine ord matche 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 kommer
å gjøre en, tre, fire, to.

939
00:43:27,930 --> 00:43:28,680
Ok bra.

940
00:43:28,680 --> 00:43:32,310
Nå fire og to?

941
00:43:32,310 --> 00:43:33,370
Vi trenger å fikse 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 sortert?

944
00:43:39,820 --> 00:43:43,170
Nei, men er det nærmere sortert?

945
00:43:43,170 --> 00:43:48,930
>> Det er fordi vi løst dette
feil, fikset vi denne feilen,

946
00:43:48,930 --> 00:43:50,370
og vi fikset denne feilen.

947
00:43:50,370 --> 00:43:52,420
Så vi fikset tre feil uten tvil.

948
00:43:52,420 --> 00:43:58,100
Fortsatt ikke egentlig ser sorterte, men
det er objektivt nærmere sorterte

949
00:43:58,100 --> 00:44:00,080
fordi vi fikset noen av disse feilene.

950
00:44:00,080 --> 00:44:02,047
>> Nå hva gjør jeg nå?

951
00:44:02,047 --> 00:44:03,630
I slags nådd enden av listen.

952
00:44:03,630 --> 00:44:05,680
Jeg syntes å ha løst
alle feilene, men nei.

953
00:44:05,680 --> 00:44:08,510
Fordi i dette tilfellet, noe nummer
kanskje har boblet opp nærmere

954
00:44:08,510 --> 00:44:10,410
til andre tall som
er fortsatt ute av drift.

955
00:44:10,410 --> 00:44:12,951
Så la oss gjøre det igjen, og jeg skal
bare gjøre det på plass denne gangen.

956
00:44:12,951 --> 00:44:14,170
Ett og tre?

957
00:44:14,170 --> 00:44:14,720
Det er i orden.

958
00:44:14,720 --> 00:44:16,070
Tre og to?

959
00:44:16,070 --> 00:44:17,560
Selvfølgelig ikke, så la oss endre 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 nå la oss bare være
spesielt pedantisk her.

963
00:44:24,370 --> 00:44:26,350
Er det sortert?

964
00:44:26,350 --> 00:44:29,280
Du mennesker vet at det sortert.

965
00:44:29,280 --> 00:44:30,400
>> Jeg skal prøve igjen.

966
00:44:30,400 --> 00:44:31,900
Så Olivia foreslår jeg prøve igjen.

967
00:44:31,900 --> 00:44:32,530
Hvorfor?

968
00:44:32,530 --> 00:44:35,810
Fordi en datamaskin ikke har
luksusen av våre menneskelige øyne

969
00:44:35,810 --> 00:44:38,080
av bare skotter back-- OK, er jeg ferdig.

970
00:44:38,080 --> 00:44:41,610
Hvordan datamaskinen bestemme
at listen er nå sortert?

971
00:44:41,610 --> 00:44:44,590
Mekanisk.

972
00:44:44,590 --> 00:44:47,650
>> Jeg skal gå gjennom
en gang, og bare hvis jeg

973
00:44:47,650 --> 00:44:51,190
ikke gjør / finne noen feil kan jeg
deretter konkludere som datamaskinen, Jepp,

974
00:44:51,190 --> 00:44:51,980
vi er flink til å 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
Nå kan jeg definitivt si at dette er
sortert, fordi jeg har gjort noen endringer.

977
00:44:58,030 --> 00:45:01,940
Nå ville det være en feil og bare
tåpelig hvis jeg, datamaskinen

978
00:45:01,940 --> 00:45:05,640
spurte de samme spørsmålene igjen
venter forskjellige svar.

979
00:45:05,640 --> 00:45:07,110
Bør ikke skje.

980
00:45:07,110 --> 00:45:08,600
>> Og så nå listen er sortert.

981
00:45:08,600 --> 00:45:12,630
Dessverre, kjøretiden til
denne algoritmen er også N kvadrat.

982
00:45:12,630 --> 00:45:13,130
Hvorfor?

983
00:45:13,130 --> 00:45:19,520
Fordi du har n antall, og i
verste fall må du flytte n antall

984
00:45:19,520 --> 00:45:23,637
n ganger fordi du må holde det gående
tilbake for å sjekke og eventuelt fastsette

985
00:45:23,637 --> 00:45:24,220
disse tallene.

986
00:45:24,220 --> 00:45:26,280
Og vi kan gjøre en mer
formell analyse, også.

987
00:45:26,280 --> 00:45:29,530
>> Så dette er alt å si at vi har tatt
tre ulike tilnærminger, en

988
00:45:29,530 --> 00:45:32,210
av dem umiddelbart intuitivt
av baksten fra Ben

989
00:45:32,210 --> 00:45:35,170
til min foreslåtte innsetting
sort til dette

990
00:45:35,170 --> 00:45:38,540
hvor du slags miste av syne
skogen for bare trær utgangspunktet.

991
00:45:38,540 --> 00:45:41,760
Men så hvis du tar et skritt tilbake,
voila, vi har løst sorterings forestillingen.

992
00:45:41,760 --> 00:45:43,824
Så dette blir, tør si,
et lavere nivå kanskje

993
00:45:43,824 --> 00:45:45,740
enn noen av de andre
algoritmer, men la oss

994
00:45:45,740 --> 00:45:48,550
se om vi ikke kan visualisere
disse ved hjelp av denne.

995
00:45:48,550 --> 00:45:51,450
>> Så dette er noe hyggelig
programvare som noen

996
00:45:51,450 --> 00:45:56,110
skrev ved hjelp av fargerike barer som er
kommer til å gjøre følgende for oss.

997
00:45:56,110 --> 00:45:57,736
Hver av disse linjene representerer et tall.

998
00:45:57,736 --> 00:46:00,026
Taller baren, jo større
nummeret, mindre tverr

999
00:46:00,026 --> 00:46:00,990
det mindre tall.

1000
00:46:00,990 --> 00:46:05,880
Så ideelt sett ønsker vi en hyggelig pyramide
hvor den starter i det små, og blir stor,

1001
00:46:05,880 --> 00:46:08,330
og det ville bety at
disse barene er sortert.

1002
00:46:08,330 --> 00:46:11,200
Så jeg kommer til å gå videre og velge,
for eksempel, Ben algoritme

1003
00:46:11,200 --> 00:46:13,990
first-- utvalg slag.

1004
00:46:13,990 --> 00:46:16,220
>> Og legg merke til hva det gjør.

1005
00:46:16,220 --> 00:46:18,670
Måten de har valgt å
visualisere denne algoritmen

1006
00:46:18,670 --> 00:46:22,090
er det, akkurat som jeg var
gå gjennom listen min,

1007
00:46:22,090 --> 00:46:24,710
dette programmet er å vandre
gjennom sin liste med tall,

1008
00:46:24,710 --> 00:46:28,160
fremhever i rosa hver
nummer som det er å se på.

1009
00:46:28,160 --> 00:46:32,360
Og hva er i ferd med å skje nå?

1010
00:46:32,360 --> 00:46:35,154
>> Den minste tall som
Jeg eller Ben plutselig funnet

1011
00:46:35,154 --> 00:46:36,820
blir flyttet til begynnelsen av listen.

1012
00:46:36,820 --> 00:46:40,037
Og legg merke til de gjorde kaste ut
nummeret som var der,

1013
00:46:40,037 --> 00:46:41,120
og det er helt greit.

1014
00:46:41,120 --> 00:46:42,600
Jeg fikk ikke komme inn i den detaljnivå.

1015
00:46:42,600 --> 00:46:44,308
Men vi trenger å sette
det tallet et sted,

1016
00:46:44,308 --> 00:46:47,775
så vi flyttet den til
åpen plass som ble opprettet.

1017
00:46:47,775 --> 00:46:49,900
Så jeg kommer til å fremskynde denne
opp, fordi ellers

1018
00:46:49,900 --> 00:46:51,871
blir veldig kjedelig raskt.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animasjon speed-- der vi går.

1021
00:46:58,600 --> 00:47:01,850
Så nå samme prinsipp
Jeg søkte, men du

1022
00:47:01,850 --> 00:47:06,540
kan begynne å føle algoritmen, hvis du
vil, eller se det litt mer tydelig.

1023
00:47:06,540 --> 00:47:13,190
Og denne algoritmen har den virkning
å velge den neste minste element,

1024
00:47:13,190 --> 00:47:16,422
så du kommer til å begynne å
ser det rampen opp til venstre.

1025
00:47:16,422 --> 00:47:19,130
Og på hver iterasjon, som jeg
foreslått, gjør det litt mindre arbeid.

1026
00:47:19,130 --> 00:47:21,921
Det trenger ikke å gå hele veien
tilbake til den venstre ende av listen

1027
00:47:21,921 --> 00:47:23,900
fordi det allerede
vet de er sortert.

1028
00:47:23,900 --> 00:47:28,129
Så det slags føles som om det er
akselererende, selv om hvert trinn er

1029
00:47:28,129 --> 00:47:29,420
tar like mye tid.

1030
00:47:29,420 --> 00:47:31,600
Det er bare færre trinn gjenstår.

1031
00:47:31,600 --> 00:47:35,240
Og nå kan du på en måte føler
algoritme rydde opp i slutten av det,

1032
00:47:35,240 --> 00:47:37,040
og faktisk nå er det ordnet.

1033
00:47:37,040 --> 00:47:41,620
>> Så innsetting typen er ferdig.

1034
00:47:41,620 --> 00:47:43,600
Jeg trenger å re-randomisere array.

1035
00:47:43,600 --> 00:47:45,940
Og legg merke til jeg kan bare
holde randomisering det,

1036
00:47:45,940 --> 00:47:50,630
og vi får en tilnærming til
samme tilnærming, innsetting slag.

1037
00:47:50,630 --> 00:47:55,050
La meg sakte ned til her.

1038
00:47:55,050 --> 00:47:56,915
La oss starte som over.

1039
00:47:56,915 --> 00:47:57,414
Stoppe.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> La oss hoppe over fire.

1042
00:48:02,410 --> 00:48:03,200
Det vi går.

1043
00:48:03,200 --> 00:48:04,190
Tilfeldig de array.

1044
00:48:04,190 --> 00:48:05,555
Og her Vær så god vi innsetting slag.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Spille.

1047
00:48:12,800 --> 00:48:17,280
Legg merke til at det er arbeider med hver
element den støter på en gang,

1048
00:48:17,280 --> 00:48:20,282
men hvis det hører til i
feil sted varsel

1049
00:48:20,282 --> 00:48:21,740
alt arbeidet som må skje.

1050
00:48:21,740 --> 00:48:24,700
Vi må holde skiftende mer
og flere elementer for å gjøre plass

1051
00:48:24,700 --> 00:48:27,340
for en ønsker vi å få på plass.

1052
00:48:27,340 --> 00:48:30,740
>> Så vi fokuserer på
venstre ende av listen bare.

1053
00:48:30,740 --> 00:48:34,460
Legg merke til at vi ikke har selv sett at-- vi
har ikke markert i rosa noe

1054
00:48:34,460 --> 00:48:35,610
til høyre.

1055
00:48:35,610 --> 00:48:38,180
Vi er bare å gjøre med
problemene som vi går,

1056
00:48:38,180 --> 00:48:40,430
men vi skaper mye
arbeide for oss selv fortsatt.

1057
00:48:40,430 --> 00:48:44,410
Og så hvis vi fremskynde dette opp
nå å gå til ferdigstillelse,

1058
00:48:44,410 --> 00:48:46,210
den har en annen føler for det faktisk.

1059
00:48:46,210 --> 00:48:50,150
Det er bare å fokusere på venstre slutten, men
gjøre litt mer arbeid som needed--

1060
00:48:50,150 --> 00:48:53,230
slags glatte ting
over, fikse ting,

1061
00:48:53,230 --> 00:48:58,350
men arbeider til slutt med
hvert element en om gangen

1062
00:48:58,350 --> 00:49:07,740
før vi kommer til folk flest i vel, vi
alle vet hvordan dette kommer til å ende,

1063
00:49:07,740 --> 00:49:09,700
så det er litt uimponerende kanskje.

1064
00:49:09,700 --> 00:49:12,830
>> Men listen i end--
spoiler-- kommer til å bli sortert.

1065
00:49:12,830 --> 00:49:15,300
Så la oss se på en siste.

1066
00:49:15,300 --> 00:49:16,840
Vi kan ikke bare hoppe over dette nå.

1067
00:49:16,840 --> 00:49:18,000
Vi er nesten der.

1068
00:49:18,000 --> 00:49:19,980
To til å gå, en å gå.

1069
00:49:19,980 --> 00:49:22,680
Og voila.

1070
00:49:22,680 --> 00:49:23,450
Utmerket.

1071
00:49:23,450 --> 00:49:27,220
>> Så nå la oss gjøre en siste,
re-randomisering med boblesortering.

1072
00:49:27,220 --> 00:49:31,690
Og legg merke til her, spesielt hvis jeg roe det
ned, betyr dette holde swooping gjennom.

1073
00:49:31,690 --> 00:49:36,830
Men legg merke til det bare gjør parvise
comparisons-- slags lokale løsninger.

1074
00:49:36,830 --> 00:49:39,050
Men så snart vi får
enden av listen i rosa,

1075
00:49:39,050 --> 00:49:40,690
hva som kommer til å skje igjen?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ja, det er nødt til å
begynne på nytt, fordi det bare

1078
00:49:46,830 --> 00:49:49,870
faste parvise feil.

1079
00:49:49,870 --> 00:49:53,120
Og som kanskje har avslørt ennå andre.

1080
00:49:53,120 --> 00:49:58,950
Og så hvis du fart opp dette, vil du
se at mye som navnet tilsier,

1081
00:49:58,950 --> 00:50:01,870
den mindre elements-- eller rettere sagt,
de større elements-- starter

1082
00:50:01,870 --> 00:50:03,740
å boble opp til toppen, hvis du vil.

1083
00:50:03,740 --> 00:50:07,380
Og de mindre elementene
begynner å boble ned til venstre.

1084
00:50:07,380 --> 00:50:10,780
Og ja, det er slags
den visuelle effekten også.

1085
00:50:10,780 --> 00:50:17,150
Og så dette vil ende opp slutt
i en svært lik måte, også.

1086
00:50:17,150 --> 00:50:19,160
>> Vi trenger ikke å dvele
på denne ene.

1087
00:50:19,160 --> 00:50:21,010
La meg åpne dette nå, også.

1088
00:50:21,010 --> 00:50:24,040
Det er et par andre sortering algoritmer
i verden, noen av dem

1089
00:50:24,040 --> 00:50:25,580
fanges her.

1090
00:50:25,580 --> 00:50:29,960
Og spesielt for elever som ikke er
nødvendigvis visuelt eller matematisk,

1091
00:50:29,960 --> 00:50:31,930
som vi gjorde før, kan vi
også gjø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 moro skyld, her er en
noen forskjellige algoritmer,

1094
00:50:36,990 --> 00:50:40,950
og en av dem spesielt du er
kommer til å merke kalles "merge sort."

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
slik at flettesortering, en av
de du er i ferd med å se,

1097
00:50:45,860 --> 00:50:49,170
er ikke orden n squared.

1098
00:50:49,170 --> 00:50:57,280
Det er i størrelsesorden n ganger logg av
n, som faktisk er mindre og dermed

1099
00:50:57,280 --> 00:50:58,940
raskere enn de andre tre.

1100
00:50:58,940 --> 00:51:00,670
Og det er et annet par
dumme de som vi får se.

1101
00:51:00,670 --> 00:51:01,933
>> Så her går vi med litt lyd.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Dette er innsetting sort, så igjen
det er bare å gjøre med elementene

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
vurderer dem parvis på en gang.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Og igjen, de største elementene
er bobler opp til toppen.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Neste opp valg slag.

1110
00:51:41,710 --> 00:51:45,420
Dette er Ben algoritme, hvor
igjen han velge iterativt

1111
00:51:45,420 --> 00:51:46,843
den nest minste element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Og igjen, nå kan du virkelig høre at
det er påskynde, men bare i den utstrekning

1114
00:51:53,900 --> 00:51:58,230
som det gjør mindre og mindre
jobbe med hver iterasjon.

1115
00:51:58,230 --> 00:52:04,170
Dette er raskere en, flettesortering,
som sortering klynger av tall

1116
00:52:04,170 --> 00:52:05,971
sammen og deretter kombinere dem.

1117
00:52:05,971 --> 00:52:07,720
Så look-- venstre
halvparten er allerede sortert.

1118
00:52:07,720 --> 00:52:14,165
>> Nå er det sortering høyre halvdel, og
Nå kommer det til å kombinere dem til én.

1119
00:52:14,165 --> 00:52:19,160
Dette er noe som kalles "Gnome slag."

1120
00:52:19,160 --> 00:52:23,460
Og du kan slags se at
det går frem og tilbake,

1121
00:52:23,460 --> 00:52:27,950
fikse arbeidet litt her og
der før den fortsetter til nytt arbeid.

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
Det er en annen form, som er
egentlig bare for akademiske formål,

1125
00:52:36,400 --> 00:52:40,980
kalt "dum liksom", som tar
dataene, sorterer det tilfeldig,

1126
00:52:40,980 --> 00:52:43,350
og deretter sjekker om det er sortert.

1127
00:52:43,350 --> 00:52:47,880
Og hvis det ikke er, det re-sorterer
tilfeldig, sjekker om det er sortert,

1128
00:52:47,880 --> 00:52:49,440
og hvis ikke gjentar seg.

1129
00:52:49,440 --> 00:52:52,660
Og i teorien, basert på sannsynlighets
Dette vil fullføre,

1130
00:52:52,660 --> 00:52:54,140
men etter litt av en bit av tid.

1131
00:52:54,140 --> 00:52:56,930
Det er ikke den mest
effektive av algoritmer.

1132
00:52:56,930 --> 00:53:02,550
Så noen spørsmål om de
spesielle algoritmer eller noe

1133
00:53:02,550 --> 00:53:04,720
relatert der også?

1134
00:53:04,720 --> 00:53:09,430
>> Vel, la oss nå erte hverandre hva alle
disse linjene er at jeg har vært tegning

1135
00:53:09,430 --> 00:53:15,090
og hva jeg antar datamaskinen
kan gjøre under panseret.

1136
00:53:15,090 --> 00:53:18,650
Jeg vil hevde at alle disse tallene
Jeg holder drawing-- de trenger å få

1137
00:53:18,650 --> 00:53:21,330
lagret et sted i minnet.

1138
00:53:21,330 --> 00:53:24,130
Vi vil bli kvitt denne fyren nå, også.

1139
00:53:24,130 --> 00:53:30,110
>> Så en del av minnet i en
computer-- så RAM DIMM er

1140
00:53:30,110 --> 00:53:35,480
hva vi søkte etter i går, dual
Inline Memory module-- ser slik ut.

1141
00:53:35,480 --> 00:53:39,370
Og hver av disse små svarte brikker
er et antall av bytes, typisk.

1142
00:53:39,370 --> 00:53:44,380
Og så gullpinnene er som
ledningene som kobler den til datamaskinen,

1143
00:53:44,380 --> 00:53:47,521
og den grønne silisium styret er bare
det som holder alt sammen.

1144
00:53:47,521 --> 00:53:48,770
Så hva betyr dette egentlig?

1145
00:53:48,770 --> 00:53:53,180
Hvis jeg slags tegne dette samme bildet,
La oss anta at for enkelhet

1146
00:53:53,180 --> 00:53:55,280
at dette DIMM, dual
Inline Memory Module,

1147
00:53:55,280 --> 00:54:00,530
er en gigabyte RAM, en gigabyte
minne, som er hvor mange byte totalt?

1148
00:54:00,530 --> 00:54:02,100
En gigabyte er hvor mange byte?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Mer enn 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 lese etiketten?

1156
00:54:16,670 --> 00:54:19,920
Dette er faktisk 128
gigabyte, det er så mye mer.

1157
00:54:19,920 --> 00:54:22,130
Men vi skal late som dette
er bare én gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Så det betyr at det er en milliard
byte minne tilgjengelig for meg

1159
00:54:25,640 --> 00:54:29,770
eller 8 milliarder biter, men vi skal
å snakke i form av bytes nå,

1160
00:54:29,770 --> 00:54:30,750
går videre.

1161
00:54:30,750 --> 00:54:36,330
>> Så hva det betyr er at dette er
en byte, er dette en annen byte,

1162
00:54:36,330 --> 00:54:38,680
Dette er en annen byte,
og hvis vi virkelig ønsket

1163
00:54:38,680 --> 00:54:43,280
å være konkret vil vi måtte
tegne en milliard små firkanter.

1164
00:54:43,280 --> 00:54:44,320
Men hva betyr det?

1165
00:54:44,320 --> 00:54:46,420
Vel, la meg bare zoome
i på dette bildet.

1166
00:54:46,420 --> 00:54:50,900
Hvis jeg har noe som ser
som dette nå, det er fire byte.

1167
00:54:50,900 --> 00:54:53,710
>> Og så jeg kunne sette fire tall 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 sette fire bokstaver eller symboler.

1170
00:55:00,170 --> 00:55:02,620
"Hei!" kunne gå rett der,
fordi hver av bokstavene,

1171
00:55:02,620 --> 00:55:04,370
vi diskutert tidligere,
kan være representert

1172
00:55:04,370 --> 00:55:06,650
med åtte biter eller ASCII eller en byte.

1173
00:55:06,650 --> 00:55:09,370
Så med andre ord, kan du
sette 8 milliarder ting inni

1174
00:55:09,370 --> 00:55:11,137
av dette en stokk med minne.

1175
00:55:11,137 --> 00:55:14,345
Nå hva betyr det å sette ting tilbake
til rygg mot rygg i minnet som dette?

1176
00:55:14,345 --> 00:55:17,330
Dette er hva en programmerer
vil kalle en "array".

1177
00:55:17,330 --> 00:55:21,250
I et dataprogram, ikke du tror
om det underliggende metall, per se.

1178
00:55:21,250 --> 00:55:24,427
Du bare tenke på deg selv som har
tilgang til en milliard byte totalt,

1179
00:55:24,427 --> 00:55:26,010
og du kan alt du vil med den.

1180
00:55:26,010 --> 00:55:27,880
Men for enkelhets skyld
det er generelt nyttig

1181
00:55:27,880 --> 00:55:31,202
å holde minnet retten
ved siden av hverandre som dette.

1182
00:55:31,202 --> 00:55:33,660
Så hvis jeg zoome inn på dette--
fordi vi er sikkert ikke kommer

1183
00:55:33,660 --> 00:55:39,310
å trekke en milliard små squares--
la oss anta at dette forumet representerer

1184
00:55:39,310 --> 00:55:40,610
som stick minne nå.

1185
00:55:40,610 --> 00:55:43,800
Og jeg vil bare trekke så mange som min
markør ender opp med å gi meg her.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Så nå har vi en pinne
minne på brettet

1188
00:55:52,300 --> 00:55:56,400
som har fått en, to, tre, fire, fem,
seks, en, to, tre, fire, fem, seks,

1189
00:55:56,400 --> 00:56:01,130
seven-- så 42 byte
minne på skjermen total.

1190
00:56:01,130 --> 00:56:01,630
Takk skal du ha.

1191
00:56:01,630 --> 00:56:02,838
Ja, det gjorde min regning rett.

1192
00:56:02,838 --> 00:56:05,120
Så 42 byte minne her.

1193
00:56:05,120 --> 00:56:06,660
Så hva betyr dette egentlig?

1194
00:56:06,660 --> 00:56:09,830
Vel, en dataprogrammerer
ville faktisk generelt

1195
00:56:09,830 --> 00:56:12,450
tenk på dette minnet som adresserbare.

1196
00:56:12,450 --> 00:56:16,630
Med andre ord, hver og en av disse
steder i minnet, i maskinvare,

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å komplisert som en Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
I stedet, det er bare et tall.

1200
00:56:23,830 --> 00:56:27,930
Dette er byte nummer null, er denne
en, dette er to, dette er tre,

1201
00:56:27,930 --> 00:56:30,327
og dette er 41.

1202
00:56:30,327 --> 00:56:30,910
Vent litt.

1203
00:56:30,910 --> 00:56:32,510
Jeg trodde jeg sa 42 for et øyeblikk siden.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Jeg begynte å telle på null,
så det er faktisk riktig.

1206
00:56:37,772 --> 00:56:40,980
Nå har vi ikke trenger å faktisk trekke det
som et rutenett, og hvis du tegner det som et rutenett

1207
00:56:40,980 --> 00:56:43,520
Jeg tror ting faktisk
få litt misvisende.

1208
00:56:43,520 --> 00:56:46,650
Hva en programmerer ville,
i hans eller hennes eget sinn,

1209
00:56:46,650 --> 00:56:50,310
vanligvis tenker på dette
minne som er akkurat som en tape,

1210
00:56:50,310 --> 00:56:53,340
som et stykke maskeringstape
som bare fortsetter og fortsetter for alltid

1211
00:56:53,340 --> 00:56:54,980
eller til du går tom for minne.

1212
00:56:54,980 --> 00:56:59,200
Slik at en mer vanlig måte å trekke
og bare tenke på minne

1213
00:56:59,200 --> 00:57:03,710
ville være at dette er byte null, en,
to, tre, og deretter dot, dot, dot.

1214
00:57:03,710 --> 00:57:07,650
Og du har 42 slike bytes totalt, selv
om fysisk det kan faktisk

1215
00:57:07,650 --> 00:57:09,480
være noe mer som dette.

1216
00:57:09,480 --> 00:57:12,850
>> Så hvis du nå tenker på
minne som dette, akkurat som en tape,

1217
00:57:12,850 --> 00:57:17,640
Dette er hva en programmerer på nytt
vil kalle en rekke minne.

1218
00:57:17,640 --> 00:57:20,660
Og når du ønsker å faktisk lagre
noe i datamaskinens minne,

1219
00:57:20,660 --> 00:57:23,290
du vanligvis gjør store ting
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Så vi har snakket om tall.

1221
00:57:25,010 --> 00:57:30,880
Og når jeg ønsket å løse problemer
som fire, én, tre, to,

1222
00:57:30,880 --> 00:57:33,820
selv om jeg var bare tegning
bare tall fire, én, tre,

1223
00:57:33,820 --> 00:57:39,490
to på bordet, ville datamaskinen
virkelig har dette oppsettet i minnet.

1224
00:57:39,490 --> 00:57:43,347
>> Og hva ville være ved siden av
to i datamaskinens minne?

1225
00:57:43,347 --> 00:57:44,680
Vel, det er ikke noe svar på det.

1226
00:57:44,680 --> 00:57:45,770
Vi vet egentlig ikke.

1227
00:57:45,770 --> 00:57:48,200
Og så lenge
Maskinen virker ikke trenger det,

1228
00:57:48,200 --> 00:57:51,440
det trenger ikke å bry seg hva som er neste
til tallene den gjør seg om.

1229
00:57:51,440 --> 00:57:55,130
Og da jeg sa tidligere at en datamaskin
kan bare se på én adresse om gangen,

1230
00:57:55,130 --> 00:57:56,170
dette er slags hvorfor.

1231
00:57:56,170 --> 00:57:59,490
>> Ikke ulikt en rekord
spiller og et lesehode

1232
00:57:59,490 --> 00:58:03,030
bare å kunne se på en viss
groove i en fysisk gamle skolen rekord

1233
00:58:03,030 --> 00:58:06,500
om gangen, tilsvar
kan en datamaskin takket

1234
00:58:06,500 --> 00:58:09,810
til sin CPU og dens
Intel instruksjonssett,

1235
00:58:09,810 --> 00:58:12,480
blant hvis instruksjon
blir lest fra minnet

1236
00:58:12,480 --> 00:58:15,590
eller lagre til memory-- en
Datamaskinen kan bare se

1237
00:58:15,590 --> 00:58:19,210
på ett sted i en tid--
noen ganger en kombinasjon av dem,

1238
00:58:19,210 --> 00:58:21,770
men egentlig bare ett sted om gangen.

1239
00:58:21,770 --> 00:58:24,770
Så når vi gjorde
disse ulike algoritmer,

1240
00:58:24,770 --> 00:58:28,110
Jeg er ikke bare å skrive i en
vacuum-- fire, én, tre, to.

1241
00:58:28,110 --> 00:58:30,849
Disse tallene faktisk tilhører
et eller annet sted fysisk minne.

1242
00:58:30,849 --> 00:58:32,890
Så det er bitte liten
transistorer eller annen form

1243
00:58:32,890 --> 00:58:35,840
av elektronikk under den
hette lagre disse verdiene.

1244
00:58:35,840 --> 00:58:40,460
>> Og totalt, hvor mange biter er
involvert akkurat nå, bare for å være klar?

1245
00:58:40,460 --> 00:58:45,580
Så dette er fire byte, eller
nå er det 32 ​​biter totalt.

1246
00:58:45,580 --> 00:58:49,280
Så det er faktisk 32 nuller og
de komponere disse fire tingene.

1247
00:58:49,280 --> 00:58:52,070
Det er enda mer over her, men
igjen vi ikke bryr seg om det.

1248
00:58:52,070 --> 00:58:55,120
>> Så nå la oss be en annen
spørsmålet ved hjelp av minne,

1249
00:58:55,120 --> 00:58:57,519
fordi at på slutten
i dag er i varians.

1250
00:58:57,519 --> 00:59:00,310
Uansett hva vi kan gjøre med
maskinen, på slutten av dagen

1251
00:59:00,310 --> 00:59:02,560
maskinvaren er fremdeles
samme under panseret.

1252
00:59:02,560 --> 00:59:04,670
Hvordan skulle jeg lagre et ord her inne?

1253
00:59:04,670 --> 00:59:09,710
Vel, et ord i en datamaskin som
"Hei!" ville bli lagret akkurat som dette.

1254
00:59:09,710 --> 00:59:12,300
Og hvis du ønsket en lengre
ord, kan du bare

1255
00:59:12,300 --> 00:59:19,120
skrive det og si noe
som "Hei" og butikk som her.

1256
00:59:19,120 --> 00:59:23,930
>> Og så her også, dette contiguousness
er faktisk en fordel,

1257
00:59:23,930 --> 00:59:26,530
fordi en datamaskin kan bare
leses fra høyre mot venstre.

1258
00:59:26,530 --> 00:59:28,680
Men her er et spørsmål.

1259
00:59:28,680 --> 00:59:33,480
I sammenheng med dette ordet,
h-e-l-l-o, utropstegn,

1260
00:59:33,480 --> 00:59:38,740
hvordan kan datamaskinen vet hvor
ord begynner og hvor ordet slutter?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
I sammenheng med tall,
hvordan gjør datamaskinen

1263
00:59:43,800 --> 00:59:48,396
vet hvor lang sekvens av
tallene er eller hvor den starter?

1264
00:59:48,396 --> 00:59:50,270
Vel, det viser out--
og vi vil ikke gå for mye

1265
00:59:50,270 --> 00:59:54,970
inn i dette nivået av detail--
datamaskiner flytte ting rundt i minne

1266
00:59:54,970 --> 00:59:57,800
bokstavelig ved hjelp av disse adressene.

1267
00:59:57,800 --> 01:00:02,080
Så i en datamaskin, hvis du er
skrive kode for å lagre ting

1268
01:00:02,080 --> 01:00:05,800
som ord, hva du er
egentlig gjør er å skrive

1269
01:00:05,800 --> 01:00:11,320
uttrykk som husker hvor i
datamaskinens minne disse ordene er.

1270
01:00:11,320 --> 01:00:14,370
Så la meg gjøre en veldig,
veldig enkelt eksempel.

1271
01:00:14,370 --> 01:00:18,260
>> Jeg kommer til å gå videre og
åpne opp en enkel tekstprogram,

1272
01:00:18,260 --> 01:00:20,330
og jeg kommer til å skape
en fil som heter hello.c.

1273
01:00:20,330 --> 01:00:22,849
Mesteparten av denne informasjonen vi
vil ikke gå inn i stor detalj,

1274
01:00:22,849 --> 01:00:25,140
men jeg kommer til å skrive et
program i den samme språk,

1275
01:00:25,140 --> 01:00:31,140
C. Dette er langt mer skremmende,
Jeg vil hevde, enn Scratch,

1276
01:00:31,140 --> 01:00:32,490
men det er svært like i ånden.

1277
01:00:32,490 --> 01:00:34,364
Faktisk er dette krøllete
braces-- du kan slags

1278
01:00:34,364 --> 01:00:37,820
tenke på hva jeg nettopp gjorde som dette.

1279
01:00:37,820 --> 01:00:39,240
>> La oss gjøre dette, faktisk.

1280
01:00:39,240 --> 01:00:45,100
Når grønne flagget klikket,
gjør følgende.

1281
01:00:45,100 --> 01:00:50,210
Jeg ønsker å skrive ut "hei."

1282
01:00:50,210 --> 01:00:51,500
Så dette er nå pseudokode.

1283
01:00:51,500 --> 01:00:53,000
Jeg er litt uskarphet linjene.

1284
01:00:53,000 --> 01:00:56,750
I C, dette språket jeg snakker
om, denne linjen print hallo

1285
01:00:56,750 --> 01:01:01,940
faktisk blir "printf" med
noen parenteser og et semikolon.

1286
01:01:01,940 --> 01:01:03,480
>> Men det er nøyaktig samme idé.

1287
01:01:03,480 --> 01:01:06,730
Og dette svært brukervennlig
"Når grønne flagget klikket" blir

1288
01:01:06,730 --> 01:01:10,182
den mye mer uforståelige "int main ugyldig."

1289
01:01:10,182 --> 01:01:12,890
Og dette har virkelig ingen kartlegging,
så jeg skal bare ignorere det.

1290
01:01:12,890 --> 01:01:17,210
Men klammeparentes er som
buede brikkene som dette.

1291
01:01:17,210 --> 01:01:18,700
>> Så du kan slags gjette.

1292
01:01:18,700 --> 01:01:22,357
Selv om du aldri har programmert før,
hva betyr dette programmet sannsynligvis gjøre?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Trolig skriver hallo
med et utropstegn.

1295
01:01:28,000 --> 01:01:29,150
>> Så la oss prøve det.

1296
01:01:29,150 --> 01:01:30,800
Jeg kommer til å redde den.

1297
01:01:30,800 --> 01:01:34,000
Og dette er, igjen, en veldig
old school miljø.

1298
01:01:34,000 --> 01:01:35,420
Jeg kan ikke klikke, jeg kan ikke dra.

1299
01:01:35,420 --> 01:01:36,910
Jeg må skrive kommandoer.

1300
01:01:36,910 --> 01:01:41,320
Så jeg ønsker å kjøre mitt program, så
Jeg kan gjøre dette, som hello.c.

1301
01:01:41,320 --> 01:01:42,292
Det er filen jeg kjørte.

1302
01:01:42,292 --> 01:01:43,500
Men vent, jeg mangler et trinn.

1303
01:01:43,500 --> 01:01:46,470
Hva gjorde vi si er en nødvendig
trinn for et språk som C?

1304
01:01:46,470 --> 01:01:49,470
Jeg har nettopp skrevet kilde
kode, men hva trenger jeg?

1305
01:01:49,470 --> 01:01:50,670
Ja, jeg trenger en kompilator.

1306
01:01:50,670 --> 01:01:57,670
Så på min Mac her, jeg har en
Programmet heter GCC, GNU C-kompilator,

1307
01:01:57,670 --> 01:02:03,990
som tillater meg å gjøre dette-- turn
min kildekoden til, vil vi kaller det,

1308
01:02:03,990 --> 01:02:04,930
maskinkode.

1309
01:02:04,930 --> 01:02:10,180
>> Og jeg kan se det,
igjen, som følger, disse

1310
01:02:10,180 --> 01:02:14,090
er nuller og enere jeg bare
laget fra min kildekoden,

1311
01:02:14,090 --> 01:02:15,730
alle de nuller og enere.

1312
01:02:15,730 --> 01:02:17,770
Og hvis jeg vil kjøre
min program-- det skjer

1313
01:02:17,770 --> 01:02:23,010
å bli kalt a.out for
historiske reasons-- "hei."

1314
01:02:23,010 --> 01:02:24,070
Jeg kan kjøre den på nytt.

1315
01:02:24,070 --> 01:02:25,690
Hallo hallo hallo.

1316
01:02:25,690 --> 01:02:27,430
Og det ser ut til å virke.

1317
01:02:27,430 --> 01:02:31,000
>> Men det betyr at et sted i min
maskinens minne er ordene

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, utropstegn.

1319
01:02:35,279 --> 01:02:38,070
Og det viser seg, akkurat som en side,
hva en datamaskin ville vanligvis

1320
01:02:38,070 --> 01:02:40,550
gjøre slik at den vet der
ting begynner og end-- det er

1321
01:02:40,550 --> 01:02:42,460
kommer til å sette et spesielt symbol her.

1322
01:02:42,460 --> 01:02:46,064
Og konvensjonen er å sette
nummeret null ved slutten av et ord

1323
01:02:46,064 --> 01:02:48,230
slik at du vet hvor det
faktisk ender, slik at du

1324
01:02:48,230 --> 01:02:52,750
ikke holde å skrive ut mer og mer
tegn enn du faktisk har tenkt.

1325
01:02:52,750 --> 01:02:55,400
>> Men takeaway her, selv
selv om dette er ganske uforståelige,

1326
01:02:55,400 --> 01:02:58,140
er at det er slutt
forholdsvis enkel.

1327
01:02:58,140 --> 01:03:04,550
Du fikk liksom en tape, en blank
plass hvor du kan skrive brev.

1328
01:03:04,550 --> 01:03:07,150
Du bare må ha en
spesielt symbol, som vilkårlig

1329
01:03:07,150 --> 01:03:10,316
tallet null, for å sette på slutten av
dine ord slik at datamaskinen vet,

1330
01:03:10,316 --> 01:03:13,410
åh, jeg skal slutte å skrive ut etter
Jeg ser utropstegnet.

1331
01:03:13,410 --> 01:03:16,090
Fordi den neste tingen der
er en ASCII-verdi på null,

1332
01:03:16,090 --> 01:03:19,125
eller nulltegnet så
noen vil kalle det.

1333
01:03:19,125 --> 01:03:21,500
Men det er litt av et problem
her, og la oss gå tilbake

1334
01:03:21,500 --> 01:03:23,320
til tall for et øyeblikk.

1335
01:03:23,320 --> 01:03:28,720
Anta at jeg gjør det, faktisk,
har en rekke tall,

1336
01:03:28,720 --> 01:03:30,730
og anta at
Programmet jeg skriver er

1337
01:03:30,730 --> 01:03:34,680
som en karakterboken for en lærer
og lærere i klasserommet.

1338
01:03:34,680 --> 01:03:38,720
Og dette programmet gjør ham eller henne
å skrive i elevenes score

1339
01:03:38,720 --> 01:03:39,960
på spørrekonkurranser.

1340
01:03:39,960 --> 01:03:43,750
Og anta at studenten får
100 på deres første quiz, kanskje

1341
01:03:43,750 --> 01:03:49,920
som en 80 på den neste, deretter en
75, deretter en 90 på den fjerde prøven.

1342
01:03:49,920 --> 01:03:54,150
>> Så på dette punktet i historien,
matrisen er av størrelse fire.

1343
01:03:54,150 --> 01:03:58,470
Det er absolutt mer minne i
datamaskin, men matrisen, så å si,

1344
01:03:58,470 --> 01:04:00,350
er av størrelse fire.

1345
01:04:00,350 --> 01:04:06,060
Anta nå at læreren ønsker
å tildele en femte quiz til klassen.

1346
01:04:06,060 --> 01:04:08,510
Vel, en av de tingene han
eller hun blir nødt til å gjøre

1347
01:04:08,510 --> 01:04:10,650
er nå lagre en ekstra verdi her.

1348
01:04:10,650 --> 01:04:15,490
Men hvis matrisen læreren har
laget i dette programmet er av størrelse for,

1349
01:04:15,490 --> 01:04:22,440
en av problemet med en matrise som er
du kan ikke bare fortsette å legge til minne.

1350
01:04:22,440 --> 01:04:26,470
For hva hvis en annen del av
Programmet har ordet "hei" rett der?

1351
01:04:26,470 --> 01:04:29,650
>> Med andre ord, kan min hukommelse være
brukes til noe i et program.

1352
01:04:29,650 --> 01:04:33,250
Og hvis på forhånd jeg skrev inn, hei,
Jeg ønsker å legge inn fire quiz score,

1353
01:04:33,250 --> 01:04:34,784
de kan gå her og her.

1354
01:04:34,784 --> 01:04:37,700
Og hvis du plutselig ombestemmer deg
senere og si at jeg vil ha en femte quiz

1355
01:04:37,700 --> 01:04:40,872
poengsum, kan du ikke bare
sette den hvor du vil,

1356
01:04:40,872 --> 01:04:42,580
fordi hva om dette
hukommelse blir brukt

1357
01:04:42,580 --> 01:04:45,990
for noe else-- noen andre program
eller en annen funksjon i programmet

1358
01:04:45,990 --> 01:04:46,910
at du kjører?

1359
01:04:46,910 --> 01:04:50,650
Så du må tenke på forhånd
hvordan du ønsker å lagre dine data,

1360
01:04:50,650 --> 01:04:54,480
fordi nå har du malt
selv inn i en digital hjørne.

1361
01:04:54,480 --> 01:04:57,280
>> Så en lærer kan i stedet
si når du skriver et program

1362
01:04:57,280 --> 01:04:59,360
å lagre hans eller hennes
karakterer, vet du hva?

1363
01:04:59,360 --> 01:05:04,180
Jeg kommer til å be om,
når du skriver mitt program,

1364
01:05:04,180 --> 01:05:12,070
at jeg vil ha null, en, to, tre,
fire, fem, seks, åtte karakterer totalt.

1365
01:05:12,070 --> 01:05:15,320
Så en, to, tre, fire,
fem, seks, sju, åtte.

1366
01:05:15,320 --> 01:05:18,612
Læreren kan bare over bevilge
minne når du skriver hans eller hennes program

1367
01:05:18,612 --> 01:05:19,570
og si, vet du hva?

1368
01:05:19,570 --> 01:05:22,236
Jeg kommer aldri til å tildele mer
enn åtte quizer i et semester.

1369
01:05:22,236 --> 01:05:23,130
Det er bare tull.

1370
01:05:23,130 --> 01:05:24,470
Jeg vil aldri fordele det.

1371
01:05:24,470 --> 01:05:28,270
Slik at denne måten han eller hun har
fleksibilitet til å lagre student score,

1372
01:05:28,270 --> 01:05:33,010
som 75, 90, og kanskje en ekstra der
studenten fikk ekstra kreditt, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Men hvis læreren aldri
bruker disse tre områder,

1374
01:05:36,130 --> 01:05:38,860
det er en intuitiv takeaway her.

1375
01:05:38,860 --> 01:05:41,410
Han eller hun er bare sløse plass.

1376
01:05:41,410 --> 01:05:44,790
Så med andre ord, det er denne
felles kompromisset i programmering

1377
01:05:44,790 --> 01:05:48,241
der du enten kan tildele
akkurat så mye minne som du vil,

1378
01:05:48,241 --> 01:05:51,490
oppsiden av dem er at du er super
efficient-- du ikke er bortkastet

1379
01:05:51,490 --> 01:05:54,640
på alle-- men ulempen som
er hva hvis du ombestemmer deg når

1380
01:05:54,640 --> 01:05:58,780
bruke programmet som du ønsker å lagre
mer data enn du opprinnelig hadde tenkt.

1381
01:05:58,780 --> 01:06:03,030
>> Så kanskje løsningen er, da,
skrive programmene dine på en slik måte

1382
01:06:03,030 --> 01:06:05,605
at de bruker mer minne
enn de faktisk trenger.

1383
01:06:05,605 --> 01:06:07,730
På denne måten kommer du ikke
å kjøre inn det problemet,

1384
01:06:07,730 --> 01:06:09,730
men du blir sløsing.

1385
01:06:09,730 --> 01:06:12,960
Og jo mer minne programmet bruker,
som vi diskuterte i går, jo mindre

1386
01:06:12,960 --> 01:06:15,410
minne som er tilgjengelig
for andre programmer,

1387
01:06:15,410 --> 01:06:18,790
jo raskere datamaskinen kan bremse
ned på grunn av virtuelt minne.

1388
01:06:18,790 --> 01:06:22,670
Og så den ideelle løsningen kan være det?

1389
01:06:22,670 --> 01:06:24,610
>> Under-allokering virker dårlig.

1390
01:06:24,610 --> 01:06:27,030
Over-allokering virker dårlig.

1391
01:06:27,030 --> 01:06:31,120
Så hva kan være en bedre løsning?

1392
01:06:31,120 --> 01:06:32,390
Reallocating.

1393
01:06:32,390 --> 01:06:33,590
Være mer dynamisk.

1394
01:06:33,590 --> 01:06:37,520
Ikke tving deg selv til å velge en
priori, i begynnelsen, hva du ønsker.

1395
01:06:37,520 --> 01:06:41,370
Og absolutt ikke over-tildele,
så dere ikke være bortkastet.

1396
01:06:41,370 --> 01:06:45,770
>> Og så for å oppnå dette målet, vi
må kaste denne datastrukturen,

1397
01:06:45,770 --> 01:06:48,100
så å si, bort.

1398
01:06:48,100 --> 01:06:51,080
Og så hva en programmerer
vil vanligvis bruke

1399
01:06:51,080 --> 01:06:55,940
er noe som kalles ikke en
matrise men en lenket liste.

1400
01:06:55,940 --> 01:07:00,860
Med andre ord, vil han eller hun vil
begynner å tenke på deres minne

1401
01:07:00,860 --> 01:07:05,280
som en slags form som de
kan trekke på følgende måte.

1402
01:07:05,280 --> 01:07:08,520
Hvis jeg ønsker å lagre ett nummer i
en program-- så det er september

1403
01:07:08,520 --> 01:07:12,600
Jeg har gitt mine studenter en quiz; Jeg ønsker
å lagre studentenes første quiz,

1404
01:07:12,600 --> 01:07:16,220
og de fikk en 100 på det-- jeg
kommer til å spørre min datamaskin,

1405
01:07:16,220 --> 01:07:19,540
ved hjelp av det programmet jeg har
skrevet, for en del av minnet.

1406
01:07:19,540 --> 01:07:22,570
Og jeg kommer til å lagre
nummer 100 i den, og det er det.

1407
01:07:22,570 --> 01:07:24,820
>> Så noen uker senere
når jeg får mitt andre quiz,

1408
01:07:24,820 --> 01:07:27,890
og det er på tide å skrive
i at 90%, jeg kommer

1409
01:07:27,890 --> 01:07:32,129
å spørre datamaskinen, hei, datamaskin,
kan jeg ha en annen del av minne?

1410
01:07:32,129 --> 01:07:34,170
Det kommer til å gi meg denne
tom mengde minne.

1411
01:07:34,170 --> 01:07:39,370
Jeg kommer til å sette i nummer 90,
men i mitt program eller annen måte eller other--

1412
01:07:39,370 --> 01:07:42,100
og vi vil ikke bekymre
syntaksen for dette-- jeg trenger

1413
01:07:42,100 --> 01:07:44,430
å liksom kjeden disse tingene sammen.

1414
01:07:44,430 --> 01:07:47,430
Og jeg vil kjede dem sammen med
det ser ut som en pil her.

1415
01:07:47,430 --> 01:07:50,050
>> Den tredje quiz som kommer opp,
Jeg kommer til å si hei, datamaskin,

1416
01:07:50,050 --> 01:07:51,680
gi meg en annen del av minnet.

1417
01:07:51,680 --> 01:07:54,660
Og jeg kommer til å legge ned
uansett hva det var, i likhet med 75,

1418
01:07:54,660 --> 01:07:56,920
og jeg må kjede dette
sammen nå liksom.

1419
01:07:56,920 --> 01:08:00,290
Fjerde quiz kommer sammen, og kanskje
det er mot slutten av semesteret.

1420
01:08:00,290 --> 01:08:03,140
Og ved det punktet mitt program
kan være å bruke minne

1421
01:08:03,140 --> 01:08:05,540
over alt, over fysisk.

1422
01:08:05,540 --> 01:08:08,170
Og så bare for morro skyld, jeg er
kommer til å trekke dette fram

1423
01:08:08,170 --> 01:08:11,260
quiz-- jeg glemmer hva det var; jeg
tror kanskje en 80 eller something--

1424
01:08:11,260 --> 01:08:12,500
måte over her.

1425
01:08:12,500 --> 01:08:15,920
>> Men det er greit, fordi billedlig
Jeg kommer til å trekke denne linjen.

1426
01:08:15,920 --> 01:08:19,063
Med andre ord, i virkeligheten,
i datamaskinens maskinvare,

1427
01:08:19,063 --> 01:08:20,979
det første resultatet kanskje
ende opp her fordi det er

1428
01:08:20,979 --> 01:08:22,529
helt i starten av semesteret.

1429
01:08:22,529 --> 01:08:25,810
Den neste kan ende opp her
fordi en bit av tid har gått

1430
01:08:25,810 --> 01:08:27,210
og programmet fortsetter å kjøre.

1431
01:08:27,210 --> 01:08:30,060
Den neste score, som var
75, kan være over her.

1432
01:08:30,060 --> 01:08:33,420
Og det siste resultatet kan være
80, som er over her.

1433
01:08:33,420 --> 01:08:38,729
>> Så i virkeligheten, fysisk, dette kan være
hva datamaskinens minne ser ut.

1434
01:08:38,729 --> 01:08:41,569
Men dette er ikke en nyttig mental
paradigme for en dataprogrammerer.

1435
01:08:41,569 --> 01:08:44,649
Hvorfor skulle du bry deg der
pokker dataene er å ende opp?

1436
01:08:44,649 --> 01:08:46,200
Du ønsker bare å lagre data.

1437
01:08:46,200 --> 01:08:49,390
>> Dette er typen som vår diskusjon
tidligere for å trekke kuben.

1438
01:08:49,390 --> 01:08:52,200
Hvorfor bryr du deg hva
vinkelen er av kuben

1439
01:08:52,200 --> 01:08:53,740
og hvordan du må slå for å tegne det?

1440
01:08:53,740 --> 01:08:54,950
Du vil bare ha en kube.

1441
01:08:54,950 --> 01:08:57,359
På samme måte her, du
bare ønsker å karakterboken.

1442
01:08:57,359 --> 01:08:59,559
Du ønsker bare å tenke på
dette som en liste med tall.

1443
01:08:59,559 --> 01:09:01,350
Hvem bryr seg hvordan det er
implementert i maskinvare?

1444
01:09:01,350 --> 01:09:05,180
>> Så abstraksjon nå
er dette bildet her.

1445
01:09:05,180 --> 01:09:07,580
Dette er en lenket liste, som
en programmerer vil kalle det,

1446
01:09:07,580 --> 01:09:10,640
i den grad du har en
listen, åpenbart med tall.

1447
01:09:10,640 --> 01:09:14,990
Men det er knyttet billedlig
ved hjelp av pilene,

1448
01:09:14,990 --> 01:09:18,510
og alle disse pilene are-- under
panseret, hvis du er nysgjerrig,

1449
01:09:18,510 --> 01:09:23,210
minne om at vår fysiske maskinvaren har
adresser null, en, to, tre, fire.

1450
01:09:23,210 --> 01:09:28,465
Alle disse pilene er er som et kart
eller retninger, der hvis 90 er-- nå

1451
01:09:28,465 --> 01:09:29,090
Jeg fikk til å telle.

1452
01:09:29,090 --> 01:09:31,750
>> Zero, en, to, tre,
fire, fem, seks, syv.

1453
01:09:31,750 --> 01:09:35,640
Det ser ut som 90 er på
minneadresse nummer syv.

1454
01:09:35,640 --> 01:09:38,460
Alle disse pilene er er
som en liten papirlapp

1455
01:09:38,460 --> 01:09:42,439
som gir anvisninger til
program som sier følger dette kartet

1456
01:09:42,439 --> 01:09:43,880
å komme til stedet sju.

1457
01:09:43,880 --> 01:09:46,680
Og der vil du finne
studentens andre quiz poengsum.

1458
01:09:46,680 --> 01:09:52,100
I mellomtiden 75-- hvis jeg fortsetter dette,
Dette er syv, åtte, ni, ti, elleve, tolv,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Denne andre pilen bare representerer
et kart til minneområde 15.

1461
01:09:59,080 --> 01:10:02,550
Men igjen, programmerer vanligvis gjør
ikke bryr seg om dette detaljnivået.

1462
01:10:02,550 --> 01:10:05,530
Og i de fleste hver programmering
språket i dag, programmerer

1463
01:10:05,530 --> 01:10:10,490
vil ikke engang vet hvor i minnet
Disse tallene faktisk er.

1464
01:10:10,490 --> 01:10:14,830
Alt han eller hun har å bry seg om er
at de er en eller annen måte forbundet med hverandre

1465
01:10:14,830 --> 01:10:18,390
i en datastruktur som dette.

1466
01:10:18,390 --> 01:10:21,580
>> Men det viser seg ikke
å bli for teknisk.

1467
01:10:21,580 --> 01:10:27,430
Men bare fordi vi kan kanskje
råd til å ha denne diskusjonen her,

1468
01:10:27,430 --> 01:10:33,630
anta at vi besøker
dette problemet her av en matrise.

1469
01:10:33,630 --> 01:10:35,780
La oss se om vi angrer kommer 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
>> La meg kort hevde dette.

1472
01:10:44,980 --> 01:10:48,980
Dette er en matrise, og igjen,
fremtredende karakteristikk av en matrise

1473
01:10:48,980 --> 01:10:52,400
er at alle dataene er tilbake til
rygg mot rygg i memory-- bokstavelig

1474
01:10:52,400 --> 01:10:56,830
én byte eller kanskje fire bytes,
noen fast antall bytes bort.

1475
01:10:56,830 --> 01:11:00,710
I en lenket liste, som vi kan trekke
som dette, under panseret som

1476
01:11:00,710 --> 01:11:02,000
vet hvor de greiene er?

1477
01:11:02,000 --> 01:11:03,630
Det trenger ikke engang trenger å flyte som dette.

1478
01:11:03,630 --> 01:11:06,050
Noen data kan være
Tilbake til venstre opp der.

1479
01:11:06,050 --> 01:11:07,530
Du vet ikke engang.

1480
01:11:07,530 --> 01:11:15,430
>> Og så med en rekke, har du en
funksjon som kalles tilfeldig tilgang.

1481
01:11:15,430 --> 01:11:20,570
Og hva random access midler er
at datamaskinen kan hoppe umiddelbart

1482
01:11:20,570 --> 01:11:22,730
til hvilket som helst sted i en matrise.

1483
01:11:22,730 --> 01:11:23,580
Hvorfor?

1484
01:11:23,580 --> 01:11:26,000
Fordi datamaskinen vet
at den første plasseringen er

1485
01:11:26,000 --> 01:11:29,540
null, en, to og tre.

1486
01:11:29,540 --> 01:11:33,890
>> Og så hvis du ønsker å gå fra
dette element til det neste element,

1487
01:11:33,890 --> 01:11:36,099
du bokstavelig talt, i
datamaskin sinn, bare legge en.

1488
01:11:36,099 --> 01:11:39,140
Hvis du vil gå til det tredje elementet,
bare legge one-- neste element, bare

1489
01:11:39,140 --> 01:11:40,290
legge en.

1490
01:11:40,290 --> 01:11:42,980
Men i denne versjon
av historien, antar

1491
01:11:42,980 --> 01:11:46,080
datamaskinen er for tiden på jakt
ved eller arbeider med nummer 100.

1492
01:11:46,080 --> 01:11:49,770
Hvordan får du til neste
karakter i karakterboken?

1493
01:11:49,770 --> 01:11:52,560
>> Du må ta syv
trinn, noe som er vilkårlig.

1494
01:11:52,560 --> 01:11:58,120
For å komme til den neste, må du
ta ytterligere åtte trinn for å komme til 15.

1495
01:11:58,120 --> 01:12:02,250
Med andre ord, det er ikke en
konstant gap mellom tallene,

1496
01:12:02,250 --> 01:12:04,857
og slik at det bare tar
datamaskinen mer tid er poenget.

1497
01:12:04,857 --> 01:12:06,940
Datamaskinen må lete
gjennom minnet for

1498
01:12:06,940 --> 01:12:08,990
for å finne det du leter etter.

1499
01:12:08,990 --> 01:12:14,260
>> Så mens en matrise har en tendens til å være en
rask data structure-- fordi du

1500
01:12:14,260 --> 01:12:17,610
kan bokstavelig talt bare gjøre enkel aritmetikk
og komme dit du vil ved å legge til en,

1501
01:12:17,610 --> 01:12:21,300
for instance-- en lenket liste,
du ofre den funksjonen.

1502
01:12:21,300 --> 01:12:24,020
Du kan ikke bare gå fra første
til andre til tredje til fjerde plass.

1503
01:12:24,020 --> 01:12:25,240
Du må følge kartet.

1504
01:12:25,240 --> 01:12:28,160
Du må ta flere skritt
for å komme til de verdier som

1505
01:12:28,160 --> 01:12:30,230
ville synes å være å tilsette en kostnad.

1506
01:12:30,230 --> 01:12:35,910
Så vi betaler en pris, men det som var
funksjonen som Dan var søker her?

1507
01:12:35,910 --> 01:12:38,110
Hva gjør en lenket liste
tilsynelatende tillate oss å gjøre,

1508
01:12:38,110 --> 01:12:40,240
som var opprinnelsen til
denne historien?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Nøyaktig.

1511
01:12:43,830 --> 01:12:46,220
En dynamisk størrelse til det.

1512
01:12:46,220 --> 01:12:48,040
Vi kan legge til denne listen.

1513
01:12:48,040 --> 01:12:51,430
Vi kan også krympe på listen, så
at vi bare bruker så mye minne

1514
01:12:51,430 --> 01:12:55,560
som vi faktisk vil og så
vi er aldri over-allokering.

1515
01:12:55,560 --> 01:12:58,470
>> Nå bare å være virkelig nit-kresen,
det er en skjult kostnad.

1516
01:12:58,470 --> 01:13:01,980
Så du bør ikke bare la meg overbevise
du at dette er en overbevisende kompromisset.

1517
01:13:01,980 --> 01:13:04,190
Det er en annen skjulte kostnader her.

1518
01:13:04,190 --> 01:13:06,550
Den fordel, for å være klar,
er at vi får dynamikk.

1519
01:13:06,550 --> 01:13:10,359
Hvis jeg vil ha et annet element, kan jeg bare
tegne det og sette et tall på det.

1520
01:13:10,359 --> 01:13:12,150
Og så kan jeg koble den
med et bilde her,

1521
01:13:12,150 --> 01:13:14,970
mens over her, igjen, hvis jeg har
malt meg selv inn i et hjørne,

1522
01:13:14,970 --> 01:13:19,410
hvis noe annet er allerede bruker
minnet her, jeg er ute av lykken.

1523
01:13:19,410 --> 01:13:21,700
Jeg har malt meg inn i hjørnet.

1524
01:13:21,700 --> 01:13:24,390
>> Men hva er den skjulte
koste i dette bildet?

1525
01:13:24,390 --> 01:13:27,690
Det er ikke bare mengden
av tiden det tar

1526
01:13:27,690 --> 01:13:29,870
å gå herfra til her,
som er sju trinn, deretter

1527
01:13:29,870 --> 01:13:32,820
åtte trinn, som er mer enn en.

1528
01:13:32,820 --> 01:13:34,830
Hva er en annen skjulte kostnader?

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
Ytterligere informasjon er
nødvendig for å oppnå dette bildet.

1532
01:13:49,940 --> 01:13:53,210
>> Ja, det kartet, de små utklipp av
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 vite
hva en datamaskin har.

1535
01:13:57,660 --> 01:13:58,790
Den har nuller og enere.

1536
01:13:58,790 --> 01:14:03,170
Hvis du ønsker å representere en pil eller et
kart eller et tall, trenger du noe minne.

1537
01:14:03,170 --> 01:14:05,950
Så den andre prisen du
betale for en lenket liste,

1538
01:14:05,950 --> 01:14:09,070
en felles informatikk
ressurs, er også plass.

1539
01:14:09,070 --> 01:14:11,710
>> Og faktisk så, så ofte,
blant de avveininger

1540
01:14:11,710 --> 01:14:15,580
i utformingen av software engineering
systemer er tid og space--

1541
01:14:15,580 --> 01:14:18,596
er to av ingrediensene, to
av de mest kostbare ingredienser.

1542
01:14:18,596 --> 01:14:21,220
Dette koster meg mer tid
fordi jeg må følge dette kartet,

1543
01:14:21,220 --> 01:14:25,730
men det er også koster meg mer plass
fordi jeg må holde dette kartet rundt.

1544
01:14:25,730 --> 01:14:28,730
Så det håp, som vi har på en måte
diskutert i løpet av i går og i dag,

1545
01:14:28,730 --> 01:14:31,720
er at fordelene
vil oppveie kostnadene.

1546
01:14:31,720 --> 01:14:33,870
>> Men det er ingen åpenbare løsningen her.

1547
01:14:33,870 --> 01:14:35,870
Kanskje det er better--
a la rask og skitne,

1548
01:14:35,870 --> 01:14:38,660
som Kareem slått earlier--
å kaste minne på problemet.

1549
01:14:38,660 --> 01:14:42,520
Bare kjøpe mer minne, tror mindre
hardt om å løse problemet,

1550
01:14:42,520 --> 01:14:44,595
og løse det på en enklere måte.

1551
01:14:44,595 --> 01:14:46,720
Og faktisk tidligere, da
vi snakket om avveininger,

1552
01:14:46,720 --> 01:14:49,190
Det var ikke plass i
maskinen og tid.

1553
01:14:49,190 --> 01:14:51,810
Det var utvikler tid, noe
er enda en annen ressurs.

1554
01:14:51,810 --> 01:14:54,829
>> Så igjen, det er denne balansegangen
prøver å bestemme hvilke av disse tingene

1555
01:14:54,829 --> 01:14:55,870
er du villig til å bruke?

1556
01:14:55,870 --> 01:14:57,380
Som er den minst kostbare?

1557
01:14:57,380 --> 01:15:01,040
Som gir 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
>> Faktisk.

1561
01:15:12,580 --> 01:15:15,970
I dette tilfellet, hvis du er
representerer tallene i maps--

1562
01:15:15,970 --> 01:15:18,820
disse kalles på mange språk
"pekere" eller "adresser" -

1563
01:15:18,820 --> 01:15:20,390
det er dobbelt plass.

1564
01:15:20,390 --> 01:15:24,390
Det trenger ikke være så ille som dobbel om
akkurat nå er vi bare lagring av numre.

1565
01:15:24,390 --> 01:15:27,410
Anta at vi lagret
pasientjournaler i en hospital--

1566
01:15:27,410 --> 01:15:30,870
så Pierson navn, telefonnumre,
personnummer, lege

1567
01:15:30,870 --> 01:15:31,540
historie.

1568
01:15:31,540 --> 01:15:34,160
Denne boksen kan være mye,
mye større, i hvilket tilfelle

1569
01:15:34,160 --> 01:15:38,000
en bitte liten peker, adressen
neste element-- det er ikke en stor avtale.

1570
01:15:38,000 --> 01:15:40,620
Det er slik en utkant
koster det spiller ingen rolle.

1571
01:15:40,620 --> 01:15:43,210
Men i dette tilfellet, ja, det er en dobling.

1572
01:15:43,210 --> 01:15:45,290
Godt spørsmål.

1573
01:15:45,290 --> 01:15:47,900
>> La oss snakke om tid en
Litt mer konkret.

1574
01:15:47,900 --> 01:15:50,380
Hva er kjøretiden
for å søke denne listen?

1575
01:15:50,380 --> 01:15:53,640
Anta at jeg ønsket å søke
gjennom alle elevenes karakterer,

1576
01:15:53,640 --> 01:15:55,980
og det er n karakterer
i dette datastruktur.

1577
01:15:55,980 --> 01:15:58,830
Også her kan vi låne
vokabular av 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 n er hva som kreves for å få
til enden av denne datastruktur,

1580
01:16:04,570 --> 01:16:08,410
whereas-- og vi har ikke sett
dette before-- en rekke gir deg

1581
01:16:08,410 --> 01:16:13,555
det som kalles konstant tid, noe som betyr at
ett trinn eller to trinn, eller 10 steps--

1582
01:16:13,555 --> 01:16:14,180
spiller ingen rolle.

1583
01:16:14,180 --> 01:16:15,440
Det er et fast antall.

1584
01:16:15,440 --> 01:16:17,440
Det har ingenting å gjøre med
størrelsen av matrisen.

1585
01:16:17,440 --> 01:16:20,130
Og grunnen til det,
igjen, er tilfeldig tilgang.

1586
01:16:20,130 --> 01:16:23,180
Datamaskinen kan bare umiddelbart
hopp til et annet sted,

1587
01:16:23,180 --> 01:16:27,770
fordi de er alle like
avstand fra alt annet.

1588
01:16:27,770 --> 01:16:29,112
Det er ingen tenkning involvert.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Greit.

1591
01:16:32,400 --> 01:16:39,230
Så hvis jeg kan, la meg prøve å
male to siste bildene.

1592
01:16:39,230 --> 01:16:42,830
En veldig vanlig en kjent som en hash table.

1593
01:16:42,830 --> 01:16:51,120
Så for å motivere denne diskusjonen,
la meg tenke på hvordan du gjør dette.

1594
01:16:51,120 --> 01:16:52,610
>> Så hva med denne?

1595
01:16:52,610 --> 01:16:55,160
Anta at problemet
vi ønsker å løse nå

1596
01:16:55,160 --> 01:16:58,360
gjennomfører i et dictionary--
så en hel haug med engelske ord

1597
01:16:58,360 --> 01:16:59,330
eller hva.

1598
01:16:59,330 --> 01:17:02,724
Og målet er å være i stand til å svare
spørsmål i skjemaet er dette et ord?

1599
01:17:02,724 --> 01:17:04,640
Så du ønsker å implementere
en stavekontroll, bare

1600
01:17:04,640 --> 01:17:07,220
som en fysisk ordbok
som du kan se ting opp i.

1601
01:17:07,220 --> 01:17:10,490
Anta at jeg skulle gjøre dette med en matrise.

1602
01:17:10,490 --> 01:17:12,590
Jeg kunne gjøre dette.

1603
01:17:12,590 --> 01:17:20,756
>> Og antar at ordene er eple
og banan og honningmelon.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Og jeg kan ikke tenke på frukt
som begynner med d, så vi er bare

1606
01:17:26,465 --> 01:17:27,590
kommer til å ha tre frukter.

1607
01:17:27,590 --> 01:17:31,510
Så dette er en matrise, og vi er
lagring av alle disse ordene

1608
01:17:31,510 --> 01:17:34,200
i denne ordboken som en matrise.

1609
01:17:34,200 --> 01:17:39,350
Spørsmålet er da hvordan ellers
kan du lagre denne informasjonen?

1610
01:17:39,350 --> 01:17:43,160
>> Vel, jeg slags juks her, fordi
hver av disse bokstavene i ordet

1611
01:17:43,160 --> 01:17:44,490
er virkelig en person byte.

1612
01:17:44,490 --> 01:17:46,740
Så hvis jeg virkelig ønsket å være
nit-kresen, skal jeg virkelig

1613
01:17:46,740 --> 01:17:49,600
være å dele dette opp i mye
mindre biter av minne,

1614
01:17:49,600 --> 01:17:51,289
og vi kunne gjøre akkurat det.

1615
01:17:51,289 --> 01:17:53,580
Men vi kommer til å kjøre inn
det samme problemet som før.

1616
01:17:53,580 --> 01:17:56,674
Hva om, som Merriam Webster eller Oxford
gjør hver year-- de legger ord

1617
01:17:56,674 --> 01:17:59,340
til dictionary-- gjør vi ikke
nødvendigvis ønsker å male oss selv

1618
01:17:59,340 --> 01:18:00,780
inn i et hjørne med en rekke?

1619
01:18:00,780 --> 01:18:05,710
>> Så i stedet, kanskje en smartere tilnærming
er å sette eple i en egen node eller boks,

1620
01:18:05,710 --> 01:18:11,190
som vi ville si, banan, og
så her har vi honningmelon.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Og vi streng disse tingene sammen.

1623
01:18:16,790 --> 01:18:19,980
Så dette er tabellen, og
Dette er lenket liste.

1624
01:18:19,980 --> 01:18:23,300
Hvis du ikke helt kan se, er det bare
sier "array", og dette sier "-liste."

1625
01:18:23,300 --> 01:18:25,780
>> Så vi har det samme
eksakte spørsmål som før,

1626
01:18:25,780 --> 01:18:28,600
hvor vi har nå
dynamikk i vår lenket liste.

1627
01:18:28,600 --> 01:18:31,090
Men vi har en ganske treg ordbok.

1628
01:18:31,090 --> 01:18:32,870
Anta at jeg ønsker å slå opp et ord.

1629
01:18:32,870 --> 01:18:35,430
Det kan ta meg stor O av n
trinn, fordi ordet makt

1630
01:18:35,430 --> 01:18:37,840
være plassert helt ved enden av
listen, som honningmelon.

1631
01:18:37,840 --> 01:18:40,600
Og det viser seg at
i programmering, sortere

1632
01:18:40,600 --> 01:18:42,700
den hellige gral av data
strukturer, er noe

1633
01:18:42,700 --> 01:18:46,620
som gir deg konstant
tid som en matrise

1634
01:18:46,620 --> 01:18:50,870
men som likevel gir deg dynamikk.

1635
01:18:50,870 --> 01:18:52,940
>> Så kan vi ha det beste fra begge verdener?

1636
01:18:52,940 --> 01:18:55,570
Og ja, det er noe
kalt hash table

1637
01:18:55,570 --> 01:18:59,320
som lar deg gjøre akkurat
det, om enn ca.

1638
01:18:59,320 --> 01:19:03,140
En hash table er en mer avansert
datastruktur som vi

1639
01:19:03,140 --> 01:19:06,340
kan tenke på som
Kombinasjonen av en array--

1640
01:19:06,340 --> 01:19:12,390
og jeg kommer til å trekke det
som dette-- og lenkede lister

1641
01:19:12,390 --> 01:19:17,310
at jeg skal tegne som dette over her.

1642
01:19:17,310 --> 01:19:19,760
>> Og måten denne saken
verkene er som følger.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Hvis dette now-- hasj table--
er mitt tredje datastrukturen,

1645
01:19:29,540 --> 01:19:32,590
og jeg ønsker å lagre
ord i dette, gjør jeg ikke

1646
01:19:32,590 --> 01:19:35,440
ønsker å bare lagre alle
ord rygg mot rygg mot rygg mot rygg.

1647
01:19:35,440 --> 01:19:37,430
Jeg ønsker å utnytte noen
opplysning

1648
01:19:37,430 --> 01:19:40,330
om ordene som vil la
meg å få det der det er raskere.

1649
01:19:40,330 --> 01:19:43,666
>> Så gitt ord eple
og banan og honningmelon,

1650
01:19:43,666 --> 01:19:45,040
Jeg valgte bevisst disse ordene.

1651
01:19:45,040 --> 01:19:45,340
Hvorfor?

1652
01:19:45,340 --> 01:19:47,631
Hva er liksom fundamentalt
annerledes om de tre?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Hva er det åpenbare?

1655
01:19:51,484 --> 01:19:52,900
De starter med forskjellige bokstaver.

1656
01:19:52,900 --> 01:19:53,900
>> Så vet du hva?

1657
01:19:53,900 --> 01:19:57,120
I stedet for å sette alle mine ord i
det samme bøtte, så å si,

1658
01:19:57,120 --> 01:20:00,390
som i en stor liste, hvorfor ikke
Jeg i det minste prøve en optimalisering

1659
01:20:00,390 --> 01:20:04,180
og gjøre mine lister 1/26 så lenge.

1660
01:20:04,180 --> 01:20:07,440
En overbevisende optimalisering
kan være grunnen ikke

1661
01:20:07,440 --> 01:20:10,650
I-- når du setter inn et ord
inn i denne datastrukturen,

1662
01:20:10,650 --> 01:20:14,300
inn i datamaskinens minne, hvorfor
jeg ikke sette 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å dette ender opp med å sette et eple
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
Ordet like-- hva som er en annen?

1667
01:20:31,700 --> 01:20:36,640
Apple, banan, pære.

1668
01:20:36,640 --> 01:20:39,370
Alle som tenker på en frukt
som 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 å ende opp her.

1671
01:20:43,990 --> 01:20:47,530
Og så vi synes å ha en
marginalt bedre løsning,

1672
01:20:47,530 --> 01:20:50,820
fordi nå hvis jeg vil
for å søke etter eple, jeg

1673
01:20:50,820 --> 01:20:53,200
first-- jeg ikke bare dykke
inn i mitt datastruktur.

1674
01:20:53,200 --> 01:20:54,850
Jeg vet ikke dykke inn i datamaskinens minne.

1675
01:20:54,850 --> 01:20:56,530
Første gang jeg ser på den første bokstaven.

1676
01:20:56,530 --> 01:20:58,610
>> Og dette er hva en datamaskin
vitenskapsmann ville si.

1677
01:20:58,610 --> 01:21:00,760
Du hasj inn i datastrukturen.

1678
01:21:00,760 --> 01:21:04,100
Du tar dine innspill, som i
dette tilfellet er et ord som eple.

1679
01:21:04,100 --> 01:21:07,150
Du analysere den, ser på
den første bokstav i dette tilfellet

1680
01:21:07,150 --> 01:21:08,340
dermed hashing det.

1681
01:21:08,340 --> 01:21:10,950
Hashing er et generelt begrep der
du tar noe som input

1682
01:21:10,950 --> 01:21:12,116
og du produserer noen utgang.

1683
01:21:12,116 --> 01:21:15,090
Og utgang i at
Saken er plasseringen

1684
01:21:15,090 --> 01:21:18,150
du vil søke etter, den første
beliggenhet, andre plassering, tredje.

1685
01:21:18,150 --> 01:21:22,160
Så inngangen er eple,
utgangen er først.

1686
01:21:22,160 --> 01:21:25,054
Inngangen er banan, den
Utgangen skal være andre.

1687
01:21:25,054 --> 01:21:27,220
Inngangen er cantaloupe,
utdataene skal være tredje.

1688
01:21:27,220 --> 01:21:30,320
Inngangen er blåbær, den
utgang bør igjen være andre.

1689
01:21:30,320 --> 01:21:34,010
Og det er det som hjelper deg å ta
snarveier gjennom hukommelsen

1690
01:21:34,010 --> 01:21:39,050
For å få til ord
eller data på en mer effektiv måte.

1691
01:21:39,050 --> 01:21:43,330
>> Nå kutter ned vår tid potensielt
med så mye som én av 26,

1692
01:21:43,330 --> 01:21:45,850
fordi hvis du anta at du
har så mange "en" 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 å ha skew tvers
enkelte bokstavene i alphabet--

1695
01:21:50,830 --> 01:21:53,204
men dette ville være en inkrementell
tilnærming som tillater

1696
01:21:53,204 --> 01:21:55,930
du komme til ord mye raskere.

1697
01:21:55,930 --> 01:21:59,660
Og i virkeligheten, en sofistikert
program, Googles av verden,

1698
01:21:59,660 --> 01:22:02,180
den Facebooks av world--
de ville bruke en hash table

1699
01:22:02,180 --> 01:22:03,740
for en rekke forskjellige formål.

1700
01:22:03,740 --> 01:22:06,590
Men de ville ikke være så naiv som
å bare se på den første bokstaven

1701
01:22:06,590 --> 01:22:09,700
i eple eller banan eller
pære eller honningmelon,

1702
01:22:09,700 --> 01:22:13,420
fordi som du kan se disse
lister kan fortsatt få lang.

1703
01:22:13,420 --> 01:22:17,130
>> Og så dette kan fortsatt være sort
av linear-- så slags langsom,

1704
01:22:17,130 --> 01:22:19,980
som med stor O av n
som vi diskuterte tidligere.

1705
01:22:19,980 --> 01:22:25,290
Så hva en virkelig god hash table vil
do-- det vil ha en mye større utvalg.

1706
01:22:25,290 --> 01:22:28,574
Og det vil bruke en mye mer
sofistikert hashing funksjon,

1707
01:22:28,574 --> 01:22:30,240
slik at det ikke bare se på "a".

1708
01:22:30,240 --> 01:22:35,480
Kanskje den ser på "a-p-p-l-e" og
liksom konverterer disse fem bokstaver

1709
01:22:35,480 --> 01:22:38,400
i stedet der
Apple bør lagres.

1710
01:22:38,400 --> 01:22:42,660
Vi er bare naivt å bruke bokstaven 'a'
alene, det er fordi fin og enkel.

1711
01:22:42,660 --> 01:22:44,600
>> Men en hash table, i
Til slutt kan du tror

1712
01:22:44,600 --> 01:22:47,270
som en kombinasjon av
en matrise, hver av hvilke

1713
01:22:47,270 --> 01:22:51,700
har en lenket liste som ideelt sett
bør være så kort som mulig.

1714
01:22:51,700 --> 01:22:54,364
Og dette er ikke en åpenbar løsning.

1715
01:22:54,364 --> 01:22:57,280
Faktisk mye av den fine tuning
som går på under panseret når

1716
01:22:57,280 --> 01:22:59,654
implementere slike
sofistikerte datastrukturer

1717
01:22:59,654 --> 01:23:01,640
er hva som er riktig
Lengden av matrisen?

1718
01:23:01,640 --> 01:23:03,250
Hva er riktig hash-funksjon?

1719
01:23:03,250 --> 01:23:04,830
Hvordan du lagre ting i minnet?

1720
01:23:04,830 --> 01:23:07,249
>> Men skjønner hvor raskt
denne typen diskusjon

1721
01:23:07,249 --> 01:23:10,540
eskalerte, enten så langt at det er slag
av over hodet på dette punktet, hvilken

1722
01:23:10,540 --> 01:23:11,360
er greit.

1723
01:23:11,360 --> 01:23:18,820
Men vi startet, husker, med virkelig
noe lav-nivå og elektronisk.

1724
01:23:18,820 --> 01:23:20,819
Og så dette igjen er dette
Temaet for abstraksjon,

1725
01:23:20,819 --> 01:23:23,610
der en gang du begynner å ta for
innvilget, OK, jeg har it-- det er

1726
01:23:23,610 --> 01:23:26,680
fysisk minne, OK, fikk den, hver
fysisk plassering har en adresse,

1727
01:23:26,680 --> 01:23:29,910
OK, jeg fikk den, kan jeg representere
disse adressene som arrows--

1728
01:23:29,910 --> 01:23:34,650
kan du raskt begynne å ha
mer sofistikerte samtaler som

1729
01:23:34,650 --> 01:23:38,360
til slutt ser ut til å bli slik at vi
å løse problemer som søker

1730
01:23:38,360 --> 01:23:41,620
og sortering mer effektivt.

1731
01:23:41,620 --> 01:23:44,190
Og vær trygg, også--
fordi jeg tror dette

1732
01:23:44,190 --> 01:23:48,700
er den dypeste vi har gått inn i noen
av disse CS temaene proper-- vi har

1733
01:23:48,700 --> 01:23:51,880
gjort på en og en halv dag på dette
peke på hva du kan vanligvis gjøre over

1734
01:23:51,880 --> 01:23:55,520
I løpet av åtte uker i et semester.

1735
01:23:55,520 --> 01:23:59,670
>> Eventuelle spørsmål om disse?

1736
01:23:59,670 --> 01:24:01,100
Nei?

1737
01:24:01,100 --> 01:24:01,940
Greit.

1738
01:24:01,940 --> 01:24:05,610
Vel, hvorfor ikke vi stoppe der,
starte lunsj et par minutter for tidlig,

1739
01:24:05,610 --> 01:24:07,052
fortsette i omtrent en time?

1740
01:24:07,052 --> 01:24:08,760
Og jeg skal dvele for
litt med spørsmål.

1741
01:24:08,760 --> 01:24:11,343
Så jeg kommer til å gå
ta et par samtaler hvis det er OK.

1742
01:24:11,343 --> 01:24:15,000
Jeg skal skru på litt musikk i mellomtiden,
men lunsj bør være rundt hjørnet.

1743
01:24:15,000 --> 01:24:17,862