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

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

3
00:00:00,460 --> 00:00:01,094
Vi är tillbaka.

4
00:00:01,094 --> 00:00:04,260
Så i detta segment på programmering vad
Jag trodde vi skulle göra är en blandning av saker.

5
00:00:04,260 --> 00:00:06,340
En gör lite
något hands-on,

6
00:00:06,340 --> 00:00:08,690
om än med hjälp av en mer lekfull
programmering environment--

7
00:00:08,690 --> 00:00:11,620
en som är demonstrativa av
exakt vilka typer av idéer

8
00:00:11,620 --> 00:00:14,220
vi har talat om,
men lite mer formellt.

9
00:00:14,220 --> 00:00:18,200
Två, titta på några av
de mer tekniska sätt

10
00:00:18,200 --> 00:00:21,520
att en programmerare faktiskt skulle lösa
problem som den söker problem

11
00:00:21,520 --> 00:00:24,530
att vi tittat på tidigare och
också en mer fundamentalt

12
00:00:24,530 --> 00:00:26,020
intressant problem att sortera.

13
00:00:26,020 --> 00:00:28,840
>> Vi har just antagit från get gå
att denna telefonbok sorterades,

14
00:00:28,840 --> 00:00:31,980
men att ensam är faktiskt typ av en
hård problem med många olika sätt

15
00:00:31,980 --> 00:00:32,479
att lösa det.

16
00:00:32,479 --> 00:00:34,366
Så vi kommer att använda dessa som
en klass av problem

17
00:00:34,366 --> 00:00:36,740
representativ för saker som
kan lösas i allmänhet.

18
00:00:36,740 --> 00:00:38,980
Och då kommer vi att tala
om i detalj vad

19
00:00:38,980 --> 00:00:42,360
kallas uppgifter structures--
finare sätt som länkade listor

20
00:00:42,360 --> 00:00:46,290
och hashtabeller och träd som
en programmerare skulle faktiskt

21
00:00:46,290 --> 00:00:48,890
använda och allmänt använda
på en whiteboard för att måla

22
00:00:48,890 --> 00:00:51,840
en bild av vad han eller hon
föreställer sig för att genomföra

23
00:00:51,840 --> 00:00:52,980
någon mjukvara.

24
00:00:52,980 --> 00:00:55,130
>> Så låt oss göra hands-on del först.

25
00:00:55,130 --> 00:01:00,090
Så bara få händerna smutsiga med en
miljö kallas scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Detta är ett verktyg som vi använder
i vårt grundklass.

27
00:01:02,636 --> 00:01:04,510
Även om den är utformad
för åldrarna 12 och uppåt,

28
00:01:04,510 --> 00:01:07,570
Vi använder det för upp
en del av detta ganska lite

29
00:01:07,570 --> 00:01:10,020
eftersom det är en trevlig, rolig
grafiskt sätt att lära

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

31
00:01:12,160 --> 00:01:17,600
Så bege dig till webbadressen där du
bör se en sida ganska så här,

32
00:01:17,600 --> 00:01:23,330
och gå vidare och klicka
Gå med Scratch uppe till höger

33
00:01:23,330 --> 00:01:28,300
och välja ett användarnamn och ett
lösenord och i slutändan få dig

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

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

36
00:01:32,165 --> 00:01:34,665
Jag trodde jag skulle använda detta som en
tillfälle först att visa detta.

37
00:01:34,665 --> 00:01:39,120
En fråga kom upp i pausen
om vilken kod som faktiskt ser ut.

38
00:01:39,120 --> 00:01:41,315
Och vi talade
pausen om C,

39
00:01:41,315 --> 00:01:45,060
i particular-- speciellt en
lägre nivå i en äldre språk.

40
00:01:45,060 --> 00:01:47,750
Och jag gjorde bara en snabb
Google-sökning för att hitta C-kod

41
00:01:47,750 --> 00:01:51,574
för binär sökning, den algoritm som vi
används för att söka att telefonboken tidigare.

42
00:01:51,574 --> 00:01:54,240
Detta speciella exempel, naturligtvis,
inte söka en telefonbok.

43
00:01:54,240 --> 00:01:57,840
Den söker bara en massa
nummer i datorns minne.

44
00:01:57,840 --> 00:02:01,000
Men om du vill bara få en visuell
känsla av vad en verklig programmering

45
00:02:01,000 --> 00:02:05,370
språket ser ut, ser det
en liten sak som denna.

46
00:02:05,370 --> 00:02:09,759
Så det handlar om 20-plus,
30-tal rader kod,

47
00:02:09,759 --> 00:02:12,640
men samtalet vi
hade över paus

48
00:02:12,640 --> 00:02:16,000
handlade om hur detta faktiskt
blir förvandlats till nollor och ettor

49
00:02:16,000 --> 00:02:19,200
och om du inte bara kan återställa det
bearbeta och gå från nollor och ettor

50
00:02:19,200 --> 00:02:20,210
tillbaka till koden.

51
00:02:20,210 --> 00:02:22,620
>> Tyvärr, processen
är så omvandlande

52
00:02:22,620 --> 00:02:24,890
att det är mycket lättare sagt än gjort.

53
00:02:24,890 --> 00:02:29,400
Jag gick vidare och faktiskt visade
det programmet, Binary Search,

54
00:02:29,400 --> 00:02:32,700
i nollor och ettor i form av en
program som kallas kompilatorn som jag

55
00:02:32,700 --> 00:02:34,400
råkar ha här rätt på min Mac.

56
00:02:34,400 --> 00:02:37,850
Och om man tittar på skärmen
här, med särskild inriktning

57
00:02:37,850 --> 00:02:43,520
på dessa mitten sex kolumner endast
du ser bara nollor och ettor.

58
00:02:43,520 --> 00:02:48,290
Och de är nollor och ettor som
komponera exakt som söker programmet.

59
00:02:48,290 --> 00:02:53,720
>> Och så varje bit av fem bitar,
varje byte av nollor och ettor här,

60
00:02:53,720 --> 00:02:57,310
representerar några instruktion
typiskt insidan av en dator.

61
00:02:57,310 --> 00:03:00,730
Och i själva verket, om du har hört
marknadsföring slogan "Intel inside" - det,

62
00:03:00,730 --> 00:03:04,610
Naturligtvis betyder bara att du har en
Intel CPU eller hjärnan inuti datorn.

63
00:03:04,610 --> 00:03:08,000
Och vad det betyder att vara en CPU är
att du har en instruktionsuppsättning,

64
00:03:08,000 --> 00:03:08,840
så att säga.

65
00:03:08,840 --> 00:03:11,620
>> Varje CPU i världen, många av
dem gjordes av Intel dessa dagar,

66
00:03:11,620 --> 00:03:13,690
förstår en ändlig
antal instruktioner.

67
00:03:13,690 --> 00:03:18,690
Och dessa instruktioner är så låg nivå
som lägga till dessa två siffror tillsammans,

68
00:03:18,690 --> 00:03:22,560
multiplicera dessa två siffror tillsammans,
flytta denna bit data härifrån

69
00:03:22,560 --> 00:03:27,340
hit i minnet, spara
Information härifrån till här i minnet,

70
00:03:27,340 --> 00:03:32,200
och så forth-- så mycket, mycket
låg nivå, nästan elektroniska detaljer.

71
00:03:32,200 --> 00:03:34,780
Men med de matematiska
operationer kopplade

72
00:03:34,780 --> 00:03:37,410
med vad vi diskuterat tidigare,
representation av data

73
00:03:37,410 --> 00:03:40,450
som nollor och ettor, kan
du bygger upp allt

74
00:03:40,450 --> 00:03:44,180
att en dator kan göra idag, om
det är text, grafisk, musikal,

75
00:03:44,180 --> 00:03:45,580
eller annars.

76
00:03:45,580 --> 00:03:49,450
>> Så detta är mycket lätt att få
vilse i ogräs snabbt.

77
00:03:49,450 --> 00:03:52,150
Och det finns en hel del
syntaktiska utmaningar

78
00:03:52,150 --> 00:03:56,630
där om du gör det enklaste,
stupidest stavfel ingen av programmet

79
00:03:56,630 --> 00:03:57,860
kommer att fungera alls.

80
00:03:57,860 --> 00:04:00,366
Och så istället för att använda en
språk som C i morse,

81
00:04:00,366 --> 00:04:02,240
Jag trodde det skulle vara
roligare att faktiskt göra

82
00:04:02,240 --> 00:04:04,840
något mer visuella, som
medan avsedd för barn

83
00:04:04,840 --> 00:04:08,079
är faktiskt en perfekt manifestation
med en verklig programmering

84
00:04:08,079 --> 00:04:10,370
language-- bara råkar
använda bilder istället för text

85
00:04:10,370 --> 00:04:11,710
att representera dessa idéer.

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

87
00:04:15,470 --> 00:04:21,070
klicka på knappen Skapa
överst till vänster på webbplatsen.

88
00:04:21,070 --> 00:04:24,620
Och du bör se en miljö som
den jag är på väg att se på min skärm

89
00:04:24,620 --> 00:04:26,310
här.

90
00:04:26,310 --> 00:04:29,350
Och vi kommer att tillbringa bara lite
lite tid att spela här.

91
00:04:29,350 --> 00:04:34,080
Låt oss se om vi inte alla kan lösa några
problem tillsammans på följande sätt.

92
00:04:34,080 --> 00:04:39,420
>> Så vad du ser i detta
environment-- och faktiskt bara låta

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

94
00:04:40,050 --> 00:04:42,680
Är det någon som inte här?

95
00:04:42,680 --> 00:04:45,070
Inte här?

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

97
00:04:45,800 --> 00:04:49,030
Så låt mig påpeka några
egenskaperna hos denna miljö.

98
00:04:49,030 --> 00:04:55,024
>> Så längst upp till vänster på skärmen, vi
har Scratch scen, så att säga.

99
00:04:55,024 --> 00:04:57,440
Scratch är inte bara namnet
av denna programmeringsspråk;

100
00:04:57,440 --> 00:05:00,356
Det är också namnet på katten som
du ser som standard där i orange.

101
00:05:00,356 --> 00:05:02,160
Han är på en scen, så
mycket som jag beskrev

102
00:05:02,160 --> 00:05:05,770
sköldpaddan tidigare som i en
rektangulär whiteboard miljö.

103
00:05:05,770 --> 00:05:09,800
Denna katt värld begränsas helt
som rektangel uppe där.

104
00:05:09,800 --> 00:05:12,210
>> Samtidigt, på höger
sidan här är det

105
00:05:12,210 --> 00:05:15,610
bara ett skript område, en
oskrivet blad om du vill.

106
00:05:15,610 --> 00:05:18,590
Det är där vi kommer att skriva
våra program på bara ett ögonblick.

107
00:05:18,590 --> 00:05:22,935
Och de byggstenar som vi skall
använder för att skriva detta program-- pusslet

108
00:05:22,935 --> 00:05:25,310
bitar, om du will-- är
de här i mitten,

109
00:05:25,310 --> 00:05:27,500
och de är kategoriserade
av funktionalitet.

110
00:05:27,500 --> 00:05:31,000
Så, till exempel, kommer jag att gå vidare
och visa åtminstone en av dessa.

111
00:05:31,000 --> 00:05:33,690
Jag kommer att gå vidare och klicka
kontroll kategorin där uppe.

112
00:05:33,690 --> 00:05:35,720
>> Så dessa är de kategorier där uppe.

113
00:05:35,720 --> 00:05:39,410
Jag kommer att klicka på kategoristyrning.

114
00:05:39,410 --> 00:05:44,020
Snarare kommer jag att klicka på Händelser
kategori, den allra första en där uppe.

115
00:05:44,020 --> 00:05:47,790
Och om du vill följa med
som vi gör detta, är du mycket välkommen till.

116
00:05:47,790 --> 00:05:52,180
Jag kommer att klicka och dra detta
första ", när grön flagg klickade."

117
00:05:52,180 --> 00:05:58,410
Och då kommer jag att släppa det bara
ungefär på toppen av min tomma skiffer.

118
00:05:58,410 --> 00:06:01,450
>> Och vad är trevligt om Scratch
är att denna pusselbit när

119
00:06:01,450 --> 00:06:04,560
sammankopplad med andra pussel
bitar, kommer att göra bokstavligen

120
00:06:04,560 --> 00:06:06,460
vad dessa pusselbitar säger att göra.

121
00:06:06,460 --> 00:06:09,710
Så, till exempel, är Scratch rätt
nu i mitten av hans värld.

122
00:06:09,710 --> 00:06:14,660
Jag kommer att gå vidare och välja
nu, låt oss säga, Motion kategori,

123
00:06:14,660 --> 00:06:18,000
Om du vill göra
same-- Motion kategori.

124
00:06:18,000 --> 00:06:20,430
Och nu märker jag har en hel
massa pusselbitar här

125
00:06:20,430 --> 00:06:23,370
att, återigen, typ av gör vad de säger.

126
00:06:23,370 --> 00:06:28,110
Och jag kommer att gå vidare och dra och
släppa flytta blocket här borta.

127
00:06:28,110 --> 00:06:31,860
>> Och märker att så fort du får
nära botten av de "gröna flaggan

128
00:06:31,860 --> 00:06:34,580
klickade "-knappen, meddelande
hur en vit linje visas,

129
00:06:34,580 --> 00:06:36,950
som om det är nästan
magnetisk, vill att det ska gå dit.

130
00:06:36,950 --> 00:06:43,070
Bara släppa taget, och det kommer att gå
tillsammans och formerna kommer att matcha.

131
00:06:43,070 --> 00:06:46,620
Och nu kan du kanske nästan
gissa om vi är på väg med detta.

132
00:06:46,620 --> 00:06:51,570
>> Om man tittar på Scratch stadiet
hit och se till toppen av det,

133
00:06:51,570 --> 00:06:55,142
du ser ett rött ljus, en
stoppskylt, och en grön flagga.

134
00:06:55,142 --> 00:06:57,100
Och jag kommer att gå vidare
och titta på mina Screen--

135
00:06:57,100 --> 00:06:58,460
för ett ögonblick, om du kunde.

136
00:06:58,460 --> 00:07:01,960
Jag kommer att klicka på
gröna flaggan just nu,

137
00:07:01,960 --> 00:07:07,850
och han flyttade vad som verkar vara 10 steg
eller 10 pixlar, 10 prickar, på skärmen.

138
00:07:07,850 --> 00:07:13,390
>> Och så inte så spännande,
men låt mig föreslå

139
00:07:13,390 --> 00:07:17,440
utan att ens lära detta, bara
med hjälp av egen din egen intuition-- låt

140
00:07:17,440 --> 00:07:22,560
mig föreslår att du räkna ut hur man
göra Scratch gå precis utanför scenen.

141
00:07:22,560 --> 00:07:28,700
Har honom ge plats åt den högra sidan av
skärmen, hela vägen till höger.

142
00:07:28,700 --> 00:07:32,200
Låt mig ge dig en stund
eller så att brottas med.

143
00:07:32,200 --> 00:07:37,681
Du kanske vill ta en titt
vid andra typer av block.

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

145
00:07:38,180 --> 00:07:41,290
Så bara för att sammanfatta, när vi har
den gröna flaggan klickade här

146
00:07:41,290 --> 00:07:44,850
och flytta 10 steg är
bara instruktion, varje gång jag

147
00:07:44,850 --> 00:07:46,720
klicka på den gröna flaggan, vad som händer?

148
00:07:46,720 --> 00:07:50,070
Tja, som körs mitt program.

149
00:07:50,070 --> 00:07:52,450
Så jag kunde göra detta
kanske 10 gånger manuellt,

150
00:07:52,450 --> 00:07:55,130
men det känns lite
bitars hackish, så att säga,

151
00:07:55,130 --> 00:07:57,480
där jag är inte riktigt
att lösa problemet.

152
00:07:57,480 --> 00:08:00,530
Jag försöker bara igen och
igen och igen och igen

153
00:08:00,530 --> 00:08:03,180
tills jag slags misstag
uppnå direktivet

154
00:08:03,180 --> 00:08:05,560
att jag föresatt sig att uppnå tidigare.

155
00:08:05,560 --> 00:08:08,200
>> Men vi vet från vår
pseudokod tidigare att det finns

156
00:08:08,200 --> 00:08:11,870
detta begrepp i programmering av looping,
gör något om och om igen.

157
00:08:11,870 --> 00:08:14,888
Och så såg jag att ett gäng du
sträckte sig efter vad pusselbit?

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

159
00:08:17,870 --> 00:08:18,730
Upprepa tills.

160
00:08:18,730 --> 00:08:21,400
Så vi kunde göra något
som upprepas tills.

161
00:08:21,400 --> 00:08:23,760
Och vad gjorde du upprepa tills exakt?

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
Och låt mig gå med en som är
något enklare för ett ögonblick.

165
00:08:31,974 --> 00:08:33,140
Låt mig gå vidare och göra det.

166
00:08:33,140 --> 00:08:35,559
Lägg märke till att du kan ha
upptäckt under kontroll,

167
00:08:35,559 --> 00:08:38,409
det är denna upprepning block, vilket
ser inte ut som det är så stor.

168
00:08:38,409 --> 00:08:41,039
Det finns inte mycket utrymme i
mellan dessa två gula linjer.

169
00:08:41,039 --> 00:08:43,539
Men som en del av er kanske har
märkt, om du dra och släppa,

170
00:08:43,539 --> 00:08:45,150
märker hur det växer för att fylla formen.

171
00:08:45,150 --> 00:08:46,274
>> Och du kan även klämma mer.

172
00:08:46,274 --> 00:08:48,670
Det ska bara fortsätta växa om
du drar och sväva över den.

173
00:08:48,670 --> 00:08:51,110
Och jag vet inte vad som är
bäst här, så låt

174
00:08:51,110 --> 00:08:54,760
mig åtminstone upprepa fem gånger, för
Exempelvis och sedan gå tillbaka till scenen

175
00:08:54,760 --> 00:08:56,720
och klicka på den gröna flaggan.

176
00:08:56,720 --> 00:08:59,110
Och nu märker det inte riktigt där.

177
00:08:59,110 --> 00:09:02,400
>> Nu några av er föreslås som
Victoria just gjorde, upprepa 10 gånger.

178
00:09:02,400 --> 00:09:05,140
Och som i allmänhet gör
få honom hela vägen,

179
00:09:05,140 --> 00:09:10,510
men skulle det inte finnas en mer robust
sätt än godtyckligt räkna ut

180
00:09:10,510 --> 00:09:12,640
hur många drag att göra?

181
00:09:12,640 --> 00:09:17,680
Vad kan vara en bättre kvarter
än upprepa 10 gånger vara?

182
00:09:17,680 --> 00:09:20,380
>> Ja, så varför inte göra något för evigt?

183
00:09:20,380 --> 00:09:24,390
Och nu vill jag flytta pusselbit
därinne och bli av med detta.

184
00:09:24,390 --> 00:09:28,300
Nu märker oavsett var Scratch
startar, går han till kanten.

185
00:09:28,300 --> 00:09:30,700
Och tack och lov MIT,
som gör Scratch, bara

186
00:09:30,700 --> 00:09:33,190
ser till att han aldrig
försvinner helt.

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

188
00:09:35,360 --> 00:09:37,680
>> Och bara intuitivt,
varför han hålla sig i rörelse?

189
00:09:37,680 --> 00:09:38,892
Vad händer här?

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

191
00:09:41,440 --> 00:09:43,824
Han verkar ha stannat, men
sedan om jag plocka upp och dra

192
00:09:43,824 --> 00:09:45,240
han håller vilja gå dit.

193
00:09:45,240 --> 00:09:46,123
Varför är det så?

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

195
00:09:51,610 --> 00:09:54,360
Sannerligen, är en dator bokstavligen
kommer att göra det du ber den att göra.

196
00:09:54,360 --> 00:09:58,380
Så om du berättade det tidigare göra
Följande sak för evigt, flytta 10 steg,

197
00:09:58,380 --> 00:10:01,860
det kommer att hålla på och gå
tills jag slog den röda stoppskylt

198
00:10:01,860 --> 00:10:04,620
och stoppa programmet helt och hållet.

199
00:10:04,620 --> 00:10:06,610
>> Så även om du inte
gör det, hur kunde jag

200
00:10:06,610 --> 00:10:09,510
göra Scratch flytta snabbare
över skärmen?

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

202
00:10:12,060 --> 00:10:13,280
Fler steg, eller hur?

203
00:10:13,280 --> 00:10:15,710
Så istället för att göra 10
vid en tid, varför inte vi

204
00:10:15,710 --> 00:10:20,100
gå vidare och ändra det att--
vad skulle du propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Så nu ska jag klicka på den gröna
flagga, och faktiskt, går han riktigt snabbt.

206
00:10:24,410 --> 00:10:27,180
>> Och detta är naturligtvis bara
en manifestation av animation.

207
00:10:27,180 --> 00:10:28,060
Vad är animation?

208
00:10:28,060 --> 00:10:33,090
Det är bara visar dig människa en
massa stillbilder verkligen,

209
00:10:33,090 --> 00:10:34,160
riktigt, riktigt snabbt.

210
00:10:34,160 --> 00:10:36,500
Och så om vi bara berättar
honom att flytta flera steg,

211
00:10:36,500 --> 00:10:39,750
vi bara har effekten vara att
förändring där han är på skärmen

212
00:10:39,750 --> 00:10:42,900
allt snabbare per tidsenhet.

213
00:10:42,900 --> 00:10:46,454
>> Nu nästa utmaning som jag föreslog
var att ha honom studsa kanten.

214
00:10:46,454 --> 00:10:49,120
Och utan att veta vad pussel
bitar exist-- eftersom det är bra

215
00:10:49,120 --> 00:10:53,030
om du inte får till
skede av challenge-- vad

216
00:10:53,030 --> 00:10:54,280
vill du göra intuitivt?

217
00:10:54,280 --> 00:10:58,030
Hur skulle vi ha honom studsa tillbaka och
framåt, mellan vänster och höger?

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

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

220
00:11:03,810 --> 00:11:05,680
Så vi behöver någon form
av tillstånd, och vi

221
00:11:05,680 --> 00:11:09,710
verkar ha villkorssatser, så att
tala, under kategorin Control.

222
00:11:09,710 --> 00:11:14,110
Vilken av dessa block
vi förmodligen vill?

223
00:11:14,110 --> 00:11:15,200
Ja, kanske "om, då."

224
00:11:15,200 --> 00:11:18,780
Så märker att bland de gula blocken
vi har här, det är detta "om"

225
00:11:18,780 --> 00:11:23,920
eller detta "om, annars" block som kommer
tillåter oss att fatta ett beslut att göra detta

226
00:11:23,920 --> 00:11:25,000
eller att göra det.

227
00:11:25,000 --> 00:11:27,380
Och du kan även bo dem
att göra flera saker.

228
00:11:27,380 --> 00:11:34,910
Eller om du inte har gått här ännu,
gå vidare till Sensing kategori

229
00:11:34,910 --> 00:11:39,612
och-- låt oss se om det är här.

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

231
00:11:43,050 --> 00:11:52,050
>> Så vad blocket kan vara till hjälp här
att upptäcka om han är utanför scenen?

232
00:11:52,050 --> 00:11:56,740
Ja, märker att vissa av dessa block
kan parametrized, så att säga.

233
00:11:56,740 --> 00:12:00,706
De kan slags anpassas, inte
Till skillnad från HTML igår med attribut,

234
00:12:00,706 --> 00:12:03,330
där dessa attribut typ av
skräddarsy beteendet hos en tagg.

235
00:12:03,330 --> 00:12:08,880
På samma sätt här, kan jag ta tag i detta gripande
blocket och förändring och ställa frågan,

236
00:12:08,880 --> 00:12:11,500
du röra musen
pekare som markören

237
00:12:11,500 --> 00:12:13,250
eller är du vidrör kanten?

238
00:12:13,250 --> 00:12:15,210
>> Så låt mig gå in och göra detta.

239
00:12:15,210 --> 00:12:18,130
Jag kommer att zooma ut för ett ögonblick.

240
00:12:18,130 --> 00:12:21,320
Låt mig ta denna pusselbit
här, denna pusselbit detta,

241
00:12:21,320 --> 00:12:24,570
och jag kommer att virrvarr
dem för ett ögonblick.

242
00:12:24,570 --> 00:12:27,620
Jag kommer att flytta,
ändra detta till beröring kant,

243
00:12:27,620 --> 00:12:38,590
och jag ska rörelse göra detta.

244
00:12:38,590 --> 00:12:40,490
Så här är några ingredienser.

245
00:12:40,490 --> 00:12:42,570
Jag tror att jag har allt jag vill ha.

246
00:12:42,570 --> 00:12:47,710
>> Skulle någon vilja föreslå hur jag
kan ansluta dessa kanske toppen till botten

247
00:12:47,710 --> 00:12:52,020
i syfte att lösa problemet med att ha
Scratch flytta från höger till vänster till höger för att

248
00:12:52,020 --> 00:12:57,020
vänster till höger till vänster, varvid varje
tid bara studsade väggen?

249
00:12:57,020 --> 00:12:58,050
Vad vill jag göra?

250
00:12:58,050 --> 00:13:01,097
Vilket block ska jag ansluta till
"När grön flagg klickade först"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, så låt oss börja med "evigt."

253
00:13:06,200 --> 00:13:07,170
Vad går in nästa?

254
00:13:07,170 --> 00:13:10,290
Någon annan.

255
00:13:10,290 --> 00:13:11,850
OK, flytta steg.

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

257
00:13:12,350 --> 00:13:14,470
Sen då?

258
00:13:14,470 --> 00:13:15,120
Så då om.

259
00:13:15,120 --> 00:13:17,720
Och lägg märke till, även om det ser
inklämt tillsammans tätt,

260
00:13:17,720 --> 00:13:19,500
Det kommer bara att växa för att fylla.

261
00:13:19,500 --> 00:13:21,500
Det kommer bara att hoppa i där jag vill ha det.

262
00:13:21,500 --> 00:13:25,920
>> Och vad lägger jag mellan
if och då?

263
00:13:25,920 --> 00:13:27,180
Förmodligen "om att röra kanten."

264
00:13:27,180 --> 00:13:31,800
Och meddelande, återigen, det är för stor
för det, men det kommer att växa för att fylla.

265
00:13:31,800 --> 00:13:35,002
Och sedan vända 15 grader?

266
00:13:35,002 --> 00:13:35,710
Hur många grader?

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

268
00:13:38,800 --> 00:13:41,196
Ja, så 180 kommer att snurra
mig hela vägen runt.

269
00:13:41,196 --> 00:13:42,570
Så låt oss se om jag fick denna rätt.

270
00:13:42,570 --> 00:13:43,930
Låt mig zooma ut.

271
00:13:43,930 --> 00:13:45,130
>> Låt mig dra Scratch upp.

272
00:13:45,130 --> 00:13:50,030
Så han är lite förvrängd
nu, men det är bra.

273
00:13:50,030 --> 00:13:52,231
Hur kan jag återställa honom lätt?

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

275
00:13:59,879 --> 00:14:01,045
Jag kommer att fuska lite.

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

277
00:14:04,074 --> 00:14:05,990
Så jag lägga till en annan
kvarter, bara för att vara tydlig.

278
00:14:05,990 --> 00:14:08,424
Jag vill att han ska peka 90 grader
till höger som standard,

279
00:14:08,424 --> 00:14:10,840
så jag ska bara tala om för honom
att göra det programmatiskt.

280
00:14:10,840 --> 00:14:11,632
Och nu kör vi.

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

282
00:14:14,740 --> 00:14:15,740
Vi verkar ha gjort det.

283
00:14:15,740 --> 00:14:19,980
Det är lite konstigt, eftersom
han går upp och ned.

284
00:14:19,980 --> 00:14:21,250
Låt oss kalla det en bugg.

285
00:14:21,250 --> 00:14:22,120
Det är ett misstag.

286
00:14:22,120 --> 00:14:27,320
En bugg är ett misstag i ett program, en
logiskt fel som jag, människan, gjort.

287
00:14:27,320 --> 00:14:28,985
Varför han går upp och ner?

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

289
00:14:33,560 --> 00:14:35,250
Har MIT skruva upp eller gjorde jag?

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

291
00:14:38,840 --> 00:14:42,550
>> Ja, jag menar, det är inte MIT: s
fel. De gav mig en pusselbit

292
00:14:42,550 --> 00:14:44,970
som säger vända ett visst antal grader.

293
00:14:44,970 --> 00:14:47,672
Och på Victoria förslag,
Jag vänder 180 grader,

294
00:14:47,672 --> 00:14:48,880
vilket är den rätta intuition.

295
00:14:48,880 --> 00:14:53,700
Men att vända 180 grader bokstavligen
innebär att vrida 180 grader,

296
00:14:53,700 --> 00:14:55,860
och det är inte riktigt
vad jag vill, tydligen.

297
00:14:55,860 --> 00:14:58,026
Eftersom åtminstone är han i
Detta tvådimensionella värld,

298
00:14:58,026 --> 00:15:00,740
så vänd verkligen kommer
att vända honom upp och ned.

299
00:15:00,740 --> 00:15:04,030
>> Jag vill nog att använda det blocket
istället, baserat på vad du ser här?

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

301
00:15:11,890 --> 00:15:14,790
Hur kan vi åtgärda detta?

302
00:15:14,790 --> 00:15:18,380
Ja, så vi kunde peka
i den motsatta riktningen.

303
00:15:18,380 --> 00:15:22,300
Och faktiskt även det är
kommer inte att vara tillräckligt,

304
00:15:22,300 --> 00:15:26,410
eftersom vi bara kan hårdkoda
att peka åt vänster eller höger.

305
00:15:26,410 --> 00:15:27,920
>> Du vet vad vi kan göra?

306
00:15:27,920 --> 00:15:30,160
Det ser ut som vi har en
bekvämlighet blocket här.

307
00:15:30,160 --> 00:15:32,987
Om jag zooma in, se
något som vi vill här?

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
abstraktion inbyggd här.

310
00:15:40,020 --> 00:15:45,440
Detta block verkar vara likvärdiga
till vilka andra block, plural?

311
00:15:45,440 --> 00:15:49,510
>> Detta ett kvarter verkar vara likvärdiga
att hela denna trio av block

312
00:15:49,510 --> 00:15:50,880
att vi har här.

313
00:15:50,880 --> 00:15:54,670
Så visar det sig jag kan förenkla mitt
program genom att bli av med allt detta

314
00:15:54,670 --> 00:15:58,270
och bara sätta detta här.

315
00:15:58,270 --> 00:16:01,620
Och nu är han fortfarande en liten
buggy, och det är bra för nu.

316
00:16:01,620 --> 00:16:03,370
Vi lämnar det vara.

317
00:16:03,370 --> 00:16:06,000
Men mitt program är även
enklare, och även detta

318
00:16:06,000 --> 00:16:09,060
skulle vara representativa
av ett mål i programming--

319
00:16:09,060 --> 00:16:13,430
är att helst göra din kod som
enkel, så kompakt som möjligt,

320
00:16:13,430 --> 00:16:15,650
medan det fortfarande är så
läsbar som möjligt.

321
00:16:15,650 --> 00:16:20,310
Du vill inte göra det så kortfattad
att det är svårt att förstå.

322
00:16:20,310 --> 00:16:22,826
>> Men märker jag har ersatt
tre block med ett,

323
00:16:22,826 --> 00:16:24,200
och det är utan tvekan en bra sak.

324
00:16:24,200 --> 00:16:27,280
Jag har abstraherat bort begreppet
kontrollera om du är

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

326
00:16:29,120 --> 00:16:31,520
Nu kan vi ha kul med detta, faktiskt.

327
00:16:31,520 --> 00:16:35,790
Detta lägger inte så mycket
intellektuell värde men lekfull värde.

328
00:16:35,790 --> 00:16:39,730
Jag kommer att gå vidare
och ta detta ljud här.

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

330
00:16:42,900 --> 00:16:46,420
Så låt mig gå vidare, och låt mig
stoppa programmet för ett ögonblick.

331
00:16:46,420 --> 00:16:52,070
Jag kommer att spela in följande,
ger tillgång till min mikrofon.

332
00:16:52,070 --> 00:16:53,181
>> Nu kör vi.

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

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

335
00:16:58,710 --> 00:17:01,140
Låt oss prova det här igen.

336
00:17:01,140 --> 00:17:02,279
Nu kör vi.

337
00:17:02,279 --> 00:17:03,570
OK, inspelad jag fel.

338
00:17:03,570 --> 00:17:04,580
Nu kör vi.

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

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

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

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

343
00:17:09,300 --> 00:17:10,791
Nu behöver jag att bli av med det.

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

345
00:17:11,290 --> 00:17:13,950
>> Så nu har jag en
inspelning av bara "aj".

346
00:17:13,950 --> 00:17:18,040
Så nu ska jag gå
framåt och kallar detta "aj".

347
00:17:18,040 --> 00:17:20,270
Jag kommer att gå tillbaka
till mina manus, och nu

348
00:17:20,270 --> 00:17:25,460
meddelande finns det block som kallas
spela upp ljud "mjau" eller spela upp ljud "AJ."

349
00:17:25,460 --> 00:17:28,920
Jag kommer att dra detta, och där
ska jag sätta detta för komisk effekt?

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

351
00:17:31,740 --> 00:17:37,860
Ja, så nu är det slags
buggy, eftersom nu detta block--

352
00:17:37,860 --> 00:17:42,050
Lägg märke till hur detta "om på kanten,
bounce "är typ av fristående.

353
00:17:42,050 --> 00:17:43,704
Så jag behöver för att fixa detta.

354
00:17:43,704 --> 00:17:44,870
Låt mig gå vidare och göra det.

355
00:17:44,870 --> 00:17:48,630
Låt mig bli av med detta och gå tillbaka
till vår ursprungliga, mer medvetet

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

357
00:17:49,870 --> 00:18:01,080
Så "om att röra kant, då" Jag vill
att vända, som Victoria föreslog

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

359
00:18:02,480 --> 00:18:05,497
Och jag vill spela
ljudet "aj" där?

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

361
00:18:11,800 --> 00:18:15,580
>> Ja, märker att den finns utanför
det gula blocket.

362
00:18:15,580 --> 00:18:17,680
Så här skulle också vara en
bugg, men jag har märkt det.

363
00:18:17,680 --> 00:18:21,290
Så jag kommer att dra upp här,
och meddelande nu är det inne i "om".

364
00:18:21,290 --> 00:18:24,250
Så "om" är denna typ
av liknande armliknande blot

365
00:18:24,250 --> 00:18:26,260
Det är bara att gå till
göra det som är inne i det.

366
00:18:26,260 --> 00:18:30,216
Så nu om jag zoomar ut på
risken för annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> DATOR: Aj, aj, aj.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: Och det
kommer bara fortsätta för evigt.

370
00:18:39,910 --> 00:18:44,160
Nu är det bara att påskynda saker
här, låt mig gå vidare och öppna upp,

371
00:18:44,160 --> 00:18:50,460
låt oss säga-- låta mig gå till några
av mina egna grejer från klass.

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

373
00:18:53,000 --> 00:19:00,220
Och låt mig öppna upp, låt oss säga, detta
som gjorts av en av våra undervisningsassistenter

374
00:19:00,220 --> 00:19:01,500
för några år sedan.

375
00:19:01,500 --> 00:19:04,732
Så några av er kanske kommer ihåg
det här spelet från förr,

376
00:19:04,732 --> 00:19:05,940
och det är faktiskt anmärkningsvärt.

377
00:19:05,940 --> 00:19:08,190
Även om vi har gjort
enklaste program just nu,

378
00:19:08,190 --> 00:19:09,980
låt oss betrakta vad detta
faktiskt ser ut.

379
00:19:09,980 --> 00:19:10,650
Låt mig slå play.

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

381
00:19:14,210 --> 00:19:18,980
>> Så i det här spelet, vi har en
groda, och med hjälp av pilen keys--

382
00:19:18,980 --> 00:19:23,340
han tar större steg än jag remember--
Jag har kontroll över denna groda.

383
00:19:23,340 --> 00:19:29,630
Och målet är att komma över upptagen
väg utan att köra in i bilar.

384
00:19:29,630 --> 00:19:34,735
Och låt oss see-- om jag går upp här, jag
måste vänta på en stock för att rulla förbi.

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

386
00:19:38,130 --> 00:19:39,274
Detta känns som en bugg.

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

388
00:19:42,240 --> 00:19:43,495
Detta är lite av en bugg.

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

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

391
00:19:46,480 --> 00:19:51,550
Jag är på det här,
det, och sedan hålla

392
00:19:51,550 --> 00:19:54,100
tills du får alla
grodorna till lily pads.

393
00:19:54,100 --> 00:19:55,920
Nu kan se
desto mer komplexa,

394
00:19:55,920 --> 00:19:57,840
men låt oss försöka bryta
detta ned mentalt

395
00:19:57,840 --> 00:20:00,040
och verbalt i sina komponentblock.

396
00:20:00,040 --> 00:20:03,910
Så det är förmodligen ett pussel
pjäs som vi inte har sett ännu

397
00:20:03,910 --> 00:20:07,440
men som svarar på tangenttryckningar,
till saker som jag träffade på tangentbordet.

398
00:20:07,440 --> 00:20:11,660
>> Så det är förmodligen något slags
block som säger, om nyckel är lika med upp,

399
00:20:11,660 --> 00:20:15,965
sedan göra något med Scratch--
kanske flyttar den 10 steg på detta sätt.

400
00:20:15,965 --> 00:20:20,240
Om ned tangenten trycks, flytta 10 steg
detta sätt, eller vänsterknappen, flyttar 10 steg

401
00:20:20,240 --> 00:20:21,710
detta sätt, 10 steg det.

402
00:20:21,710 --> 00:20:23,644
Jag har klart vände katten till en groda.

403
00:20:23,644 --> 00:20:26,060
Så det är just där
dräkt, som Scratch samtal det-- vi

404
00:20:26,060 --> 00:20:28,440
bara importerat en bild av grodan.

405
00:20:28,440 --> 00:20:29,570
>> Men vad händer?

406
00:20:29,570 --> 00:20:32,794
Vilka andra rader kod,
vad andra pusselbitar

407
00:20:32,794 --> 00:20:35,460
gjorde Blake, vår undervisning karl,
användning i det här programmet, tydligen?

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

409
00:20:38,320 --> 00:20:42,730
Vad gör allt move--
vad programmering konstruera?

410
00:20:42,730 --> 00:20:44,950
>> Rörelse, sure-- så
flytta block för säker.

411
00:20:44,950 --> 00:20:49,330
Och vad är det drag blocket
insida, mest troligt?

412
00:20:49,330 --> 00:20:52,850
Ja, någon form av slingan, kanske en
evigt blockera kanske en upprepning block--

413
00:20:52,850 --> 00:20:54,070
Upprepa tills blocket.

414
00:20:54,070 --> 00:20:57,330
Och det är vad som gör stockarna och
lily pads och allt annat drag

415
00:20:57,330 --> 00:20:57,990
fram och tillbaka.

416
00:20:57,990 --> 00:21:00,270
Det är bara händer i all oändlighet.

417
00:21:00,270 --> 00:21:03,180
>> Varför är några av bilarna
rör sig snabbare än de andra?

418
00:21:03,180 --> 00:21:06,607
Vad är annorlunda om dessa program?

419
00:21:06,607 --> 00:21:09,690
Ja, förmodligen några av dem tar
flera steg på en gång och en del av dem

420
00:21:09,690 --> 00:21:10,690
färre steg på en gång.

421
00:21:10,690 --> 00:21:14,670
Och den visuella effekten
är snabb jämfört med långsam.

422
00:21:14,670 --> 00:21:16,030
>> Vad tror du hände?

423
00:21:16,030 --> 00:21:19,700
När jag fick min groda hela vägen
tvärs över gatan och floden

424
00:21:19,700 --> 00:21:23,560
på näckrosblad, något
anmärkningsvärd hände.

425
00:21:23,560 --> 00:21:26,540
Vad hände så fort jag gjorde det?

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

427
00:21:27,210 --> 00:21:29,680
Det groda stoppas, och
Jag fick en andra groda.

428
00:21:29,680 --> 00:21:33,155
Så vad konstruktion måste vara
används där, vad funktionen?

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

430
00:21:36,020 --> 00:21:38,660
>> Ja, så det finns någon form av
"Om" skick upp där också.

431
00:21:38,660 --> 00:21:41,909
Och det visar out-- vi inte se this--
men det finns andra block i det att

432
00:21:41,909 --> 00:21:45,300
kan säga, om du vidrör
en annan sak på skärmen,

433
00:21:45,300 --> 00:21:47,720
Om du vidrör lily pad "och sedan".

434
00:21:47,720 --> 00:21:50,810
Och då det är då vi
göra andra grodan visas.

435
00:21:50,810 --> 00:21:54,969
Så även om det här spelet är verkligen
mycket daterat, även om det vid första anblicken

436
00:21:54,969 --> 00:21:58,010
Det finns så mycket att gå on-- och Blake
inte piska upp detta i två minuter,

437
00:21:58,010 --> 00:22:00,390
det förmodligen tog honom flera
timmar för att skapa detta spel

438
00:22:00,390 --> 00:22:03,850
baserat på hans minne eller video
från förr version av det.

439
00:22:03,850 --> 00:22:07,940
Men alla dessa små saker
gå på skärmen i isolering

440
00:22:07,940 --> 00:22:11,550
koka ner till dessa mycket enkel
constructs-- rörelser eller uttalanden

441
00:22:11,550 --> 00:22:15,519
som vi har diskuterat, loopar och
förhållanden, och det är om detta.

442
00:22:15,519 --> 00:22:17,060
Det finns några andra finare funktioner.

443
00:22:17,060 --> 00:22:19,130
Några av dem är rent
estetiska eller akustisk,

444
00:22:19,130 --> 00:22:20,964
som ljudet Jag spelade just med.

445
00:22:20,964 --> 00:22:23,380
Men för det mesta, du
har på detta språk, Scratch,

446
00:22:23,380 --> 00:22:25,350
alla av den fundamentala
byggstenar 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
och ett antal andra språk.

449
00:22:32,960 --> 00:22:36,720
Eventuella frågor om Scratch?

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

451
00:22:37,220 --> 00:22:40,303
Så vi kommer inte att dyka djupare till Scratch,
om du är välkommen här helgen,

452
00:22:40,303 --> 00:22:42,860
särskilt om du har barn eller
syskonbarn och sådant,

453
00:22:42,860 --> 00:22:44,220
att introducera dem till noll.

454
00:22:44,220 --> 00:22:47,960
Det är faktiskt en underbart lekfull
miljö med, som författarna säger,

455
00:22:47,960 --> 00:22:49,120
mycket högt i tak.

456
00:22:49,120 --> 00:22:51,670
Även om vi började med
mycket låg nivå detaljer,

457
00:22:51,670 --> 00:22:54,890
du verkligen kan göra en hel del
med det är och detta kanske

458
00:22:54,890 --> 00:22:57,360
en demonstration av just detta.

459
00:22:57,360 --> 00:23:02,920
>> Men låt oss nu övergå till några mer
sofistikerade problem, om man så vill,

460
00:23:02,920 --> 00:23:05,870
känd som "söker" och
"Sortering" mer generellt.

461
00:23:05,870 --> 00:23:09,500
Vi hade den här telefonboken earlier-- här är
en annan bara för discussion--

462
00:23:09,500 --> 00:23:13,460
att vi kunde söka
mer effektivt eftersom

463
00:23:13,460 --> 00:23:15,270
av en betydande antagande.

464
00:23:15,270 --> 00:23:17,655
Och bara för att vara tydlig, vad
antagande var jag göra

465
00:23:17,655 --> 00:23:19,280
när du söker igenom denna telefonbok?

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

467
00:23:23,342 --> 00:23:25,300
Att Mike Smith var i
telefonboken, även om jag

468
00:23:25,300 --> 00:23:27,410
skulle kunna hantera
scenariot utan honom

469
00:23:27,410 --> 00:23:30,720
det om jag bara slutade i förtid.

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

471
00:23:31,806 --> 00:23:33,930
Och det är en mycket generös
antagande, eftersom det

472
00:23:33,930 --> 00:23:36,580
innebär someone-- Jag är typ
att skära ett hörn,

473
00:23:36,580 --> 00:23:40,580
som jag är snabbare eftersom någon
annars gjorde en hel del hårt arbete för mig.

474
00:23:40,580 --> 00:23:43,120
>> Men vad händer om telefonen
boken var osorterade?

475
00:23:43,120 --> 00:23:47,050
Kanske Verizon fick lata, bara kastade
allas namn och nummer i det

476
00:23:47,050 --> 00:23:50,120
kanske i den ordning i vilken de
registrerat dig för telefon.

477
00:23:50,120 --> 00:23:54,570
Och hur mycket tid tar det mig
att hitta någon som Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 sida telefon book-- hur många
sidor måste jag titta igenom?

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

480
00:23:58,905 --> 00:24:00,030
Du sorts av lycka.

481
00:24:00,030 --> 00:24:03,420
Du har bokstavligen att titta på varje
sida om telefonboken är bara

482
00:24:03,420 --> 00:24:04,450
slumpvis sortering.

483
00:24:04,450 --> 00:24:06,910
Du kan ha tur och hitta Mike
på första sidan, eftersom han

484
00:24:06,910 --> 00:24:08,826
var den första kunden
beställa telefon.

485
00:24:08,826 --> 00:24:10,760
Men han kan ha varit den sista också.

486
00:24:10,760 --> 00:24:12,500
>> Så slumpmässig ordning är inte bra.

487
00:24:12,500 --> 00:24:16,750
Så antar att vi måste sortera
telefonboken eller i allmänhet sorteringsuppgifter

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

489
00:24:18,520 --> 00:24:19,440
Hur kan vi göra det?

490
00:24:19,440 --> 00:24:21,360
>> Nåväl, låt mig bara försöka
ett enkelt exempel här.

491
00:24:21,360 --> 00:24:24,290
Låt mig gå vidare och kasta en
några siffror på tavlan.

492
00:24:24,290 --> 00:24:35,480
Antag siffrorna vi har är,
låt oss säga, fyra, två, ett och tre.

493
00:24:35,480 --> 00:24:38,390
Och Ben, sortera dessa siffror för oss.

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

495
00:24:39,017 --> 00:24:39,850
Hur gjorde du det där?

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

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

498
00:24:43,230 --> 00:24:44,710
Så börja med den minsta
och det högsta,

499
00:24:44,710 --> 00:24:46,084
och det är riktigt bra intuition.

500
00:24:46,084 --> 00:24:48,080
Och inse att vi
människor är faktiskt ganska

501
00:24:48,080 --> 00:24:49,913
bra på att lösa problem
så här, åtminstone

502
00:24:49,913 --> 00:24:51,810
när data är relativt liten.

503
00:24:51,810 --> 00:24:54,860
Så snart du börjar få hundratals
siffror, tusentals siffror,

504
00:24:54,860 --> 00:24:58,440
miljontals siffror, Ben förmodligen
kunde inte göra det riktigt så snabbt,

505
00:24:58,440 --> 00:25:00,620
om man antar att det fanns
luckor i siffrorna.

506
00:25:00,620 --> 00:25:03,450
Ganska lätt att räkna till en miljon
annars, bara tidskrävande.

507
00:25:03,450 --> 00:25:07,150
>> Så algoritmen det låter
som Ben används just nu

508
00:25:07,150 --> 00:25:08,930
var sökandet efter det minsta antalet.

509
00:25:08,930 --> 00:25:12,900
Så även om vi människor kan ta
i en hel del information visuellt,

510
00:25:12,900 --> 00:25:14,830
en dator är faktiskt
lite mer begränsad.

511
00:25:14,830 --> 00:25:17,560
Datorn kan bara
titta på en byte i taget

512
00:25:17,560 --> 00:25:20,770
eller kanske fyra byte på en time--
dessa dagar kanske 8 byte på en time--

513
00:25:20,770 --> 00:25:24,450
men ett mycket litet antal
bitgrupper vid en given tidpunkt.

514
00:25:24,450 --> 00:25:28,480
>> Så med tanke på att vi verkligen har
fyra separata värden här--

515
00:25:28,480 --> 00:25:32,440
och du kan tänka på Ben ha
skygglappar på om han var en dator så

516
00:25:32,440 --> 00:25:36,450
att han inte kan se något annat
än en siffra i time--

517
00:25:36,450 --> 00:25:39,720
så vi kommer i allmänhet att anta, som i
Engelska, vi ska läsas från höger till vänster.

518
00:25:39,720 --> 00:25:42,870
Så det första numret Ben förmodligen såg
på var fyra och sedan mycket snabbt

519
00:25:42,870 --> 00:25:44,770
insett att det är en ganska stor
number-- låt mig hålla ute.

520
00:25:44,770 --> 00:25:45,357
>> Det finns två.

521
00:25:45,357 --> 00:25:45,940
Vänta en minut.

522
00:25:45,940 --> 00:25:47,070
Två är mindre än fyra.

523
00:25:47,070 --> 00:25:47,986
Jag kommer att minnas.

524
00:25:47,986 --> 00:25:49,070
Två är nu det minsta.

525
00:25:49,070 --> 00:25:50,417
Nu en-- det är ännu bättre.

526
00:25:50,417 --> 00:25:51,250
Det är ännu mindre.

527
00:25:51,250 --> 00:25:54,000
Jag kommer att glömma två
och kom ihåg en nu.

528
00:25:54,000 --> 00:25:56,550
>> Och han kunde sluta titta?

529
00:25:56,550 --> 00:25:58,360
Jo, han kunde baserad
på denna information,

530
00:25:58,360 --> 00:26:00,477
men han är bäst sökning
resten av listan.

531
00:26:00,477 --> 00:26:02,060
För vad om noll var i listan?

532
00:26:02,060 --> 00:26:03,643
Vad händer om negativ var i listan?

533
00:26:03,643 --> 00:26:07,720
Han vet bara att hans svar
är korrekt om han är uttömmande

534
00:26:07,720 --> 00:26:08,729
kontrolleras hela listan.

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

536
00:26:10,020 --> 00:26:11,394
Three-- det var ett slöseri med tid.

537
00:26:11,394 --> 00:26:13,540
Fick otur, men jag var
fortfarande rätt att göra det.

538
00:26:13,540 --> 00:26:17,857
Och så nu är han förmodligen
valt det minsta antalet

539
00:26:17,857 --> 00:26:20,440
och bara lägga den i början
av listan, som jag gör här.

540
00:26:20,440 --> 00:26:23,480
Nu vad gjorde du nästa, även om
du inte tycker om det nästan

541
00:26:23,480 --> 00:26:25,962
i denna omfattning?

542
00:26:25,962 --> 00:26:27,670
Upprepa processen,
så någon typ av loop.

543
00:26:27,670 --> 00:26:28,920
Det finns en välbekant idé.

544
00:26:28,920 --> 00:26:30,860
Så här är fyra.

545
00:26:30,860 --> 00:26:32,110
Det är för närvarande den minsta.

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

547
00:26:33,220 --> 00:26:33,900
Inte längre.

548
00:26:33,900 --> 00:26:34,770
Nu har jag sett två.

549
00:26:34,770 --> 00:26:36,630
Det är den näst minsta elementet.

550
00:26:36,630 --> 00:26:40,800
Three-- det är inte mindre, så
nu Ben kan plocka ut de två.

551
00:26:40,800 --> 00:26:44,510
>> Och nu har vi upprepa processen, och
naturligtvis tre får dras ut nästa.

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

553
00:26:45,420 --> 00:26:46,990
Fyra blir utdragen.

554
00:26:46,990 --> 00:26:50,140
Och nu är vi av tal,
så listan måste sorteras.

555
00:26:50,140 --> 00:26:51,960
>> Och faktiskt, är detta en formell algoritm.

556
00:26:51,960 --> 00:26:56,610
En datavetare skulle
kallar detta "val Sortera"

557
00:26:56,610 --> 00:27:00,880
Tanken är sortera en
lista iteratively-- igen

558
00:27:00,880 --> 00:27:03,807
och om och om igen att välja
det minsta antalet.

559
00:27:03,807 --> 00:27:06,140
Och vad är trevligt om det är
det är bara så jäkla intuitiv.

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

561
00:27:07,470 --> 00:27:11,100
Och du kan upprepa samma
drift och om igen.

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

563
00:27:12,150 --> 00:27:17,170
>> I detta fall den var snabb, men
Hur lång tid tar det faktiskt ta?

564
00:27:17,170 --> 00:27:19,880
Låt oss göra det verkar och
känner sig lite mer omständlig.

565
00:27:19,880 --> 00:27:24,150
Så en, två, tre, fyra, fem sex,
sju, åtta, nio, tio, elva, tolv, tretton, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- godtyckligt antal.

567
00:27:26,160 --> 00:27:28,780
Jag ville bara mer här
tid än bara fyra.

568
00:27:28,780 --> 00:27:30,780
Så om jag har en hel
massa siffror now-- det

569
00:27:30,780 --> 00:27:32,420
inte ens någon roll
vad de är-- låt oss

570
00:27:32,420 --> 00:27:34,380
tänka på vad detta
algoritm är verkligen gillar.

571
00:27:34,380 --> 00:27:35,857
>> Antag att det är tal där.

572
00:27:35,857 --> 00:27:38,190
Återigen, ingen roll vad
de är, men de är slumpmässigt.

573
00:27:38,190 --> 00:27:39,679
Jag ansöker Ben algoritm.

574
00:27:39,679 --> 00:27:41,220
Jag måste välja det minsta antalet.

575
00:27:41,220 --> 00:27:41,761
Vad gör jag?

576
00:27:41,761 --> 00:27:44,240
Och jag kommer att fysiskt
gör den här gången att agera ut.

577
00:27:44,240 --> 00:27:46,099
Titta, titta,
titta, titta, titta.

578
00:27:46,099 --> 00:27:48,140
Endast när jag kommer till
i slutet av listan kan

579
00:27:48,140 --> 00:27:51,230
Jag inser minsta
Antalet var två den här gången.

580
00:27:51,230 --> 00:27:52,720
Man är inte i listan.

581
00:27:52,720 --> 00:27:54,400
Så jag lägger ner två.

582
00:27:54,400 --> 00:27:55,590
>> Vad ska jag göra nu?

583
00:27:55,590 --> 00:27:58,600
Titta, titta, titta, titta.

584
00:27:58,600 --> 00:28:02,250
Nu hittade jag nummer sju, eftersom
det finns luckor i dessa numbers--

585
00:28:02,250 --> 00:28:03,300
men bara godtyckligt.

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

587
00:28:03,800 --> 00:28:06,030
Så nu kan jag lägga ner sju.

588
00:28:06,030 --> 00:28:08,860
Söker titta, titta.

589
00:28:08,860 --> 00:28:11,030
>> Nu jag antar, av
naturligtvis att Ben inte

590
00:28:11,030 --> 00:28:14,780
har extra RAM, extra
minne, därför att, naturligtvis,

591
00:28:14,780 --> 00:28:16,080
Jag tittar på samma nummer.

592
00:28:16,080 --> 00:28:18,246
Visst kunde jag ha kommit ihåg
alla av dessa siffror,

593
00:28:18,246 --> 00:28:19,930
och det är helt sant.

594
00:28:19,930 --> 00:28:22,610
Men om Ben minns alla
av numren han sett,

595
00:28:22,610 --> 00:28:24,430
han har verkligen inte gjort
grundläggande framsteg

596
00:28:24,430 --> 00:28:26,170
eftersom han redan har
möjligheten att söka

597
00:28:26,170 --> 00:28:27,540
igenom numren på tavlan.

598
00:28:27,540 --> 00:28:29,373
Komma ihåg alla de
siffror inte hjälper,

599
00:28:29,373 --> 00:28:32,490
eftersom han kan fortfarande som en dator
bara titta på, vi har sagt, ett antal

600
00:28:32,490 --> 00:28:33,080
vid en tid.

601
00:28:33,080 --> 00:28:35,760
Så det finns ingen typ av fusk
det att du kan utnyttja.

602
00:28:35,760 --> 00:28:39,170
>> Så i verkligheten, som jag
fortsätta söka listan,

603
00:28:39,170 --> 00:28:44,200
Jag har bokstavligen bara fortsätta
fram och tillbaka genom det, plockning ut

604
00:28:44,200 --> 00:28:45,710
nästa minsta antalet.

605
00:28:45,710 --> 00:28:48,810
Och eftersom du kan sorts sluta
från min dumma rörelser,

606
00:28:48,810 --> 00:28:50,860
detta bara blir mycket
tråkiga mycket snabbt,

607
00:28:50,860 --> 00:28:54,850
och jag verkar vara att gå tillbaka och
fram och tillbaka ganska lite.

608
00:28:54,850 --> 00:29:03,220
Nu för att vara rättvis, jag har inte gå
riktigt lika, ja, låt oss see-- att vara rättvis,

609
00:29:03,220 --> 00:29:06,310
Jag behöver inte gå helt
så många steg varje gång.

610
00:29:06,310 --> 00:29:09,200
Jo, naturligtvis, som jag
välja nummer från listan,

611
00:29:09,200 --> 00:29:11,860
den återstående listan blir kortare.

612
00:29:11,860 --> 00:29:14,240
>> Och så låt oss tänka på
hur många steg jag faktiskt

613
00:29:14,240 --> 00:29:16,010
traipsing genom varje gång.

614
00:29:16,010 --> 00:29:18,950
I den allra första läget
Vi hade 16 nummer,

615
00:29:18,950 --> 00:29:22,210
och så maximally-- låt oss bara
gör detta för en discussion--

616
00:29:22,210 --> 00:29:25,640
Jag var tvungen att titta igenom 16
tal för att hitta den minsta.

617
00:29:25,640 --> 00:29:28,420
Men när jag plockade ut
det minsta antalet, hur

618
00:29:28,420 --> 00:29:30,590
länge var den återstående listan, naturligtvis?

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

620
00:29:31,420 --> 00:29:34,670
Så hur många nummer gjorde Ben eller jag har
att titta igenom den andra gången?

621
00:29:34,670 --> 00:29:36,832
15, bara för att gå och hitta den minsta.

622
00:29:36,832 --> 00:29:39,540
Men nu, naturligtvis, är listan,
Också mindre än det var innan.

623
00:29:39,540 --> 00:29:42,540
Så hur många steg gjorde jag
måste ta nästa gång?

624
00:29:42,540 --> 00:29:49,970
14 och sedan 13 och sedan 12, plus punkt,
prick, pricka, tills jag kvar med bara en.

625
00:29:49,970 --> 00:29:53,146
Så nu datavetare skulle
fråga, ja, vad gör att alla är lika?

626
00:29:53,146 --> 00:29:55,770
Det motsvarar faktiskt en del konkreta
nummer som vi kunde säkert

627
00:29:55,770 --> 00:30:00,490
göra aritmetiskt, men vi vill prata
om effektiviteten av algoritmer

628
00:30:00,490 --> 00:30:04,940
lite mer formulaically,
oberoende av hur länge listan är.

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

630
00:30:06,240 --> 00:30:09,860
Detta är 16, men som jag sade tidigare,
Låt oss bara ringa storleken på problemet

631
00:30:09,860 --> 00:30:10,970
n, där n är något tal.

632
00:30:10,970 --> 00:30:13,220
Kanske är det 16, kanske det är
tre, det är kanske en miljon.

633
00:30:13,220 --> 00:30:13,761
jag vet inte.

634
00:30:13,761 --> 00:30:14,390
Jag bryr mig inte.

635
00:30:14,390 --> 00:30:16,520
Vad jag verkligen vill är
en formel som jag kan

636
00:30:16,520 --> 00:30:19,420
använda för att jämföra denna algoritm
mot andra algoritmer

637
00:30:19,420 --> 00:30:22,350
att någon skulle kunna hävda
är bättre eller sämre.

638
00:30:22,350 --> 00:30:25,430
>> Så visar det sig, och bara jag
vet detta från skolan,

639
00:30:25,430 --> 00:30:34,790
att det faktiskt fungerar på samma
sak som n över n plus en över två.

640
00:30:34,790 --> 00:30:40,020
Och det händer att lika, av
Naturligtvis n kvadrat plus n över två.

641
00:30:40,020 --> 00:30:43,250
Så om jag ville ha en formel
för hur många steg

642
00:30:43,250 --> 00:30:46,330
var inblandade i att titta på alla
av dessa siffror och om igen

643
00:30:46,330 --> 00:30:52,681
och om och om igen, skulle jag säga
det n kvadrat plus n över två.

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

645
00:30:53,430 --> 00:30:54,500
Detta ser bara rörigt.

646
00:30:54,500 --> 00:30:56,470
Jag verkligen vill ha en
allmän känsla av saker.

647
00:30:56,470 --> 00:30:58,810
Och du kanske kommer ihåg från
high school att det

648
00:30:58,810 --> 00:31:00,660
är begreppet högsta ordningens term.

649
00:31:00,660 --> 00:31:05,300
Vilket av dessa termer, n
kvadrat, n, eller halv,

650
00:31:05,300 --> 00:31:07,550
har störst effekt över tid?

651
00:31:07,550 --> 00:31:11,920
Ju större n blir, som
av dessa frågor mest?

652
00:31:11,920 --> 00:31:15,560
>> Med andra ord, om jag kopplar
i en miljon, n kvadrat

653
00:31:15,560 --> 00:31:17,900
kommer att vara mest sannolikt
den dominerande faktorn,

654
00:31:17,900 --> 00:31:21,670
eftersom en miljon gånger
själv är en mycket större

655
00:31:21,670 --> 00:31:23,682
än plus en extra miljon.

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

657
00:31:24,390 --> 00:31:27,305
Detta är en sådan jäkla stor
nummer om du torget ett nummer.

658
00:31:27,305 --> 00:31:28,430
Detta spelar egentligen ingen roll.

659
00:31:28,430 --> 00:31:30,596
Vi ska bara korset som
ut och glömma det.

660
00:31:30,596 --> 00:31:34,250
Och så en datavetare skulle säga
att effektiviteten hos denna algoritm

661
00:31:34,250 --> 00:31:37,850
är i storleksordningen av n squared--
Jag menar verkligen en approximation.

662
00:31:37,850 --> 00:31:40,810
Det är typ av grovt n kvadrat.

663
00:31:40,810 --> 00:31:44,130
Över tiden, desto större
och större n blir detta

664
00:31:44,130 --> 00:31:47,610
är en bra uppskattning för vad
effektivitet eller brist på effektivitet

665
00:31:47,610 --> 00:31:49,400
av denna algoritm i själva verket är.

666
00:31:49,400 --> 00:31:52,040
Och jag härleda att, naturligtvis,
från att faktiskt göra matten.

667
00:31:52,040 --> 00:31:54,040
Men nu är jag bara vinka
mina händer, eftersom jag bara

668
00:31:54,040 --> 00:31:55,790
vill ha en allmän känsla av denna algoritm.

669
00:31:55,790 --> 00:31:58,850
>> Så använder samma logik, under tiden,
låt oss betrakta en annan algoritm

670
00:31:58,850 --> 00:32:01,162
vi redan tittat at-- linjär sökning.

671
00:32:01,162 --> 00:32:02,870
När jag sökte
för telefonen book--

672
00:32:02,870 --> 00:32:05,980
inte sortering, sökning
genom telefon book--

673
00:32:05,980 --> 00:32:09,197
Vi fortsatte att säga att det var
1000 steg, eller 500 steg.

674
00:32:09,197 --> 00:32:10,280
Men låt oss generalisera det.

675
00:32:10,280 --> 00:32:12,860
Om det finns n sidor
telefonboken, vad är

676
00:32:12,860 --> 00:32:17,250
gångtid eller
effektivitet linjär sökning?

677
00:32:17,250 --> 00:32:19,750
Det är i storleksordningen
hur många steg för att hitta

678
00:32:19,750 --> 00:32:24,210
Mike Smith med linjär sökning, desto
första algoritmen, eller till och med den andra?

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

680
00:32:27,240 --> 00:32:31,710
>> I värsta fall, Mike
är i slutet av boken.

681
00:32:31,710 --> 00:32:35,590
Så om telefonboken har 1000 sidor,
vi sade förra gången, i värsta fall,

682
00:32:35,590 --> 00:32:38,380
det kan ta ungefär hur
många sidor för att hitta Mike?

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

684
00:32:38,990 --> 00:32:39,830
Det är en övre gräns.

685
00:32:39,830 --> 00:32:41,790
Det är en värsta tänkbara situation.

686
00:32:41,790 --> 00:32:44,410
Men återigen, vi flyttar bort
från siffror som 1000 nu.

687
00:32:44,410 --> 00:32:45,730
Det är bara n.

688
00:32:45,730 --> 00:32:47,470
>> Så vad är den logiska slutsatsen?

689
00:32:47,470 --> 00:32:50,210
Att hitta Mike i en telefon
bok som har n sidor

690
00:32:50,210 --> 00:32:55,280
kan ta i allra värsta fall,
hur många steg av storleksordningen n?

691
00:32:55,280 --> 00:32:58,110
Och faktiskt en dator
forskare skulle säga

692
00:32:58,110 --> 00:33:02,340
att gångtiden, eller
prestanda eller effektiviteten

693
00:33:02,340 --> 00:33:07,470
eller ineffektivitet, av en algoritm som
en linjär sökning är av storleksordningen n.

694
00:33:07,470 --> 00:33:10,010
Och vi kan tillämpa samma
logik passerar något

695
00:33:10,010 --> 00:33:13,170
som jag gjorde bara det andra
algoritm hade vi med telefonboken,

696
00:33:13,170 --> 00:33:16,040
där vi gick två sidor åt gången.

697
00:33:16,040 --> 00:33:20,120
>> Så 1000 sida telefonboken kanske
ta oss 500 sidvändningar, plus en

698
00:33:20,120 --> 00:33:21,910
Om vi ​​dubbelt tillbaka lite.

699
00:33:21,910 --> 00:33:26,590
Så om en telefonbok har n sidor, men
vi gör två sidor åt gången,

700
00:33:26,590 --> 00:33:28,900
det är ungefär vad?

701
00:33:28,900 --> 00:33:33,190
N över två, så det är som n över två.

702
00:33:33,190 --> 00:33:38,490
Men jag gjorde anspråk en
nyss att n över two--

703
00:33:38,490 --> 00:33:41,060
det är typ av samma som just n.

704
00:33:41,060 --> 00:33:44,050
Det är bara en konstant faktor,
datavetare skulle säga.

705
00:33:44,050 --> 00:33:45,970
Låt oss bara fokusera på
variablerna, really--

706
00:33:45,970 --> 00:33:47,780
de största variablerna i ekvationen.

707
00:33:47,780 --> 00:33:52,530
>> Så linjär sökning, oavsett gjort en
sida åt gången eller två sidor åt gången,

708
00:33:52,530 --> 00:33:54,810
är typ av i grunden densamma.

709
00:33:54,810 --> 00:33:56,880
Det är fortfarande i storleksordningen n.

710
00:33:56,880 --> 00:34:01,930
Men jag hävdade med min bild tidigare
att den tredje algoritmen var inte

711
00:34:01,930 --> 00:34:02,480
linjär.

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

713
00:34:03,605 --> 00:34:08,659
Det var som böjd linje, och
algebraiska formel fanns vad?

714
00:34:08,659 --> 00:34:11,812
Logg över n-- så log bas två n.

715
00:34:11,812 --> 00:34:14,520
Och vi behöver inte gå in alltför
mycket detaljer på logaritmer idag,

716
00:34:14,520 --> 00:34:17,394
men de flesta datavetare skulle inte
även berätta vad basen är.

717
00:34:17,394 --> 00:34:20,639
Eftersom det är allt bara
konstant faktorer, så att säga,

718
00:34:20,639 --> 00:34:22,659
bara små numeriska skillnader.

719
00:34:22,659 --> 00:34:31,179
Och så detta skulle vara ett mycket vanligt
sätt för särskilt formell dator

720
00:34:31,179 --> 00:34:33,949
forskare vid en styrelse eller
programmerare på en whiteboard

721
00:34:33,949 --> 00:34:36,889
faktiskt argumenterar vilka
algoritm de skulle använda

722
00:34:36,889 --> 00:34:39,500
eller vad effektiviteten
av deras algoritm är.

723
00:34:39,500 --> 00:34:42,960
>> Och det är inte nödvändigtvis något
du diskutera någon större detalj,

724
00:34:42,960 --> 00:34:47,889
men en bra programmerare är någon
som har en fast, formell bakgrund.

725
00:34:47,889 --> 00:34:50,120
Han kan tala med
du i denna typ av väg

726
00:34:50,120 --> 00:34:53,350
och faktiskt göra
kvalitativa argument som

727
00:34:53,350 --> 00:34:56,870
till varför en algoritm eller
en mjukvara

728
00:34:56,870 --> 00:35:00,165
är överlägsen på något sätt till en annan.

729
00:35:00,165 --> 00:35:02,540
Eftersom du kan säkert
bara köra en persons program

730
00:35:02,540 --> 00:35:04,980
och räkna antalet sekunder
det tar att sortera några siffror,

731
00:35:04,980 --> 00:35:06,710
och du kan köra några
andra personens program

732
00:35:06,710 --> 00:35:08,418
och räkna antalet
sekunder det tar.

733
00:35:08,418 --> 00:35:12,840
Men detta är ett mer generellt sätt att
du kan använda för att analysera algoritmer,

734
00:35:12,840 --> 00:35:15,520
om du vill, bara på
papper eller bara verbalt.

735
00:35:15,520 --> 00:35:18,430
Utan att ens köra den, utan
ens försöka provingångar,

736
00:35:18,430 --> 00:35:20,180
du kan bara resonera igenom det.

737
00:35:20,180 --> 00:35:24,670
Och så med att anställa en utvecklare eller om
ha honom eller henne slags argumentera för dig

738
00:35:24,670 --> 00:35:28,460
varför deras algoritm, deras hemlighet
sås för att söka miljarder

739
00:35:28,460 --> 00:35:30,580
av webbsidor för din
Företaget är bättre, dessa

740
00:35:30,580 --> 00:35:33,302
är den typ av argument som de
bör helst kunna göra.

741
00:35:33,302 --> 00:35:35,010
Eller åtminstone dessa är
den typen av saker

742
00:35:35,010 --> 00:35:40,211
som skulle komma upp i diskussionen, vid
stone i en mycket formell diskussion.

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

744
00:35:40,710 --> 00:35:44,400
Så Ben föreslagna något
kallas val slag.

745
00:35:44,400 --> 00:35:48,200
Men jag kommer att föreslå att det finns
andra sätt att göra detta också.

746
00:35:48,200 --> 00:35:50,400
Vad jag inte riktigt gillar
om Ben algoritm

747
00:35:50,400 --> 00:35:54,400
är att han fortsatte att gå, eller
ha mig gå fram och tillbaka

748
00:35:54,400 --> 00:35:56,930
och fram och tillbaka och fram och tillbaka.

749
00:35:56,930 --> 00:36:04,130
Vad händer om jag istället skulle göra
något som dessa siffror här

750
00:36:04,130 --> 00:36:08,200
och jag skulle bara ta itu med varje
nummer i sin tur som jag gett det?

751
00:36:08,200 --> 00:36:10,780
>> Med andra ord, här är
min nummerlistan.

752
00:36:10,780 --> 00:36:12,944
Fyra, en, tre, två.

753
00:36:12,944 --> 00:36:14,360
Och jag kommer att göra följande.

754
00:36:14,360 --> 00:36:17,230
Jag ska in numren
där de hör hemma i stället

755
00:36:17,230 --> 00:36:18,980
än att välja dem en i taget.

756
00:36:18,980 --> 00:36:20,820
Med andra ord, här är nummer fyra.

757
00:36:20,820 --> 00:36:22,430
>> Här är min ursprungliga listan.

758
00:36:22,430 --> 00:36:25,290
Och jag kommer att upprätthålla
i huvudsak en ny lista här.

759
00:36:25,290 --> 00:36:26,710
Så detta är den gamla listan.

760
00:36:26,710 --> 00:36:28,560
Detta är den nya listan.

761
00:36:28,560 --> 00:36:30,220
Jag ser nummer fyra första.

762
00:36:30,220 --> 00:36:34,500
Min nya listan är initialt tom,
så det är trivialt fallet

763
00:36:34,500 --> 00:36:36,410
att fyra nu diverse listan.

764
00:36:36,410 --> 00:36:39,560
Jag tar numret jag får,
och jag sätter det i min nya listan.

765
00:36:39,560 --> 00:36:41,460
>> Är detta nya listan sorteras?

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

767
00:36:41,990 --> 00:36:45,090
Det är dumt eftersom det finns bara en
element, men det är absolut sortering.

768
00:36:45,090 --> 00:36:46,390
Det finns inget på sin plats.

769
00:36:46,390 --> 00:36:49,290
Det är mer intressant, denna algoritm,
när jag flyttar till nästa steg.

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

771
00:36:50,550 --> 00:36:55,430
Så en, naturligtvis, tillhör vid
början eller i slutet av denna nya lista?

772
00:36:55,430 --> 00:36:56,360
Början.

773
00:36:56,360 --> 00:36:58,530
Så jag måste göra en del arbete nu.

774
00:36:58,530 --> 00:37:01,410
Jag har tagit del
friheter med min markör

775
00:37:01,410 --> 00:37:03,120
genom att bara dra saker
där jag vill ha dem,

776
00:37:03,120 --> 00:37:05,320
men det är inte riktigt
exakt i en dator.

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

778
00:37:08,530 --> 00:37:12,411
och det är ett byte och
en annan byte och en annan byte.

779
00:37:12,411 --> 00:37:14,910
Och om du har en gigabyte
RAM, har du en miljard byte,

780
00:37:14,910 --> 00:37:16,680
men de är fysiskt på ett ställe.

781
00:37:16,680 --> 00:37:19,540
Du kan inte bara flytta runt saker
genom att dra den på bordet

782
00:37:19,540 --> 00:37:20,750
var du vill.

783
00:37:20,750 --> 00:37:24,090
Så om min nya lista har
fyra platser i minnet,

784
00:37:24,090 --> 00:37:27,480
tyvärr fyra är
redan på fel ställe.

785
00:37:27,480 --> 00:37:30,410
>> Så för att sätta nummer ett
Jag kan inte bara dra det här.

786
00:37:30,410 --> 00:37:31,901
Denna minnesplats finns inte.

787
00:37:31,901 --> 00:37:35,150
Det skulle vara fusk, och jag har varit
fusk bildmässigt i några minuter

788
00:37:35,150 --> 00:37:35,800
här.

789
00:37:35,800 --> 00:37:40,950
Så egentligen, om jag vill sätta en här,
Jag måste tillfälligt kopiera fyra

790
00:37:40,950 --> 00:37:43,030
och sedan lägga en där.

791
00:37:43,030 --> 00:37:45,500
>> Det är bra, det är korrekt,
det är tekniskt möjligt,

792
00:37:45,500 --> 00:37:48,410
men inser att det är extra arbete.

793
00:37:48,410 --> 00:37:50,460
Jag inte bara uppskattar antalet på plats.

794
00:37:50,460 --> 00:37:53,026
Jag först var tvungen att flytta en
nummer, sedan lägga den på plats,

795
00:37:53,026 --> 00:37:54,650
så jag slags fördubblat min arbetsinsats.

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

797
00:37:55,660 --> 00:37:57,120
>> Men jag nu gjort med detta element.

798
00:37:57,120 --> 00:37:59,056
Nu vill jag ta nummer tre.

799
00:37:59,056 --> 00:38:00,430
Där naturligtvis, hör det?

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

801
00:38:01,480 --> 00:38:03,650
Jag kan inte fuska längre
och bara lägga den där,

802
00:38:03,650 --> 00:38:06,770
eftersom, återigen, detta minne
är i fysiska platser.

803
00:38:06,770 --> 00:38:10,900
Så jag måste kopiera fyra
och satte tre hit.

804
00:38:10,900 --> 00:38:11,550
Inte en stor sak.

805
00:38:11,550 --> 00:38:14,610
Det är bara ett extra steg
igen-- känns mycket billigt.

806
00:38:14,610 --> 00:38:16,445
>> Men nu jag gå vidare till två.

807
00:38:16,445 --> 00:38:17,820
De två, naturligtvis, hör hemma här.

808
00:38:17,820 --> 00:38:20,990
Nu du börjar se hur
arbetet kan stapla upp.

809
00:38:20,990 --> 00:38:23,520
Nu vad jag har att göra?

810
00:38:23,520 --> 00:38:28,570
Ja, jag måste flytta fyra,
Jag har sedan kopiera de tre,

811
00:38:28,570 --> 00:38:31,200
och nu kan jag sätta in två.

812
00:38:31,200 --> 00:38:34,460
Och fångsten med detta
algoritm, intressant nog,

813
00:38:34,460 --> 00:38:41,050
är att anta att vi har en mer extrem
fall där det är låt oss säga åtta, sju,

814
00:38:41,050 --> 00:38:45,150
sex, fem, fyra, tre, två, ett.

815
00:38:45,150 --> 00:38:49,450
Detta är, i många sammanhang,
det värsta scenariot,

816
00:38:49,450 --> 00:38:51,570
eftersom darn sak
är bokstavligen baklänges.

817
00:38:51,570 --> 00:38:53,670
>> Det spelar egentligen ingen
påverka Ben algoritm,

818
00:38:53,670 --> 00:38:55,940
eftersom Ben urval
sort han kommer att hålla

819
00:38:55,940 --> 00:38:58,359
gå fram och tillbaka i listan.

820
00:38:58,359 --> 00:39:01,150
Och eftersom han alltid ser
genom hela den återstående listan,

821
00:39:01,150 --> 00:39:02,858
det spelar ingen roll
där elementen är.

822
00:39:02,858 --> 00:39:05,630
Men i det här fallet med min insättning
approach-- låt oss prova detta.

823
00:39:05,630 --> 00:39:08,616
>> Så en, två, tre, fyra,
fem, sex, sju, åtta.

824
00:39:08,616 --> 00:39:11,630
Ett två tre Fyra,
fem, sex, sju, åtta.

825
00:39:11,630 --> 00:39:14,320
Jag kommer att ta åtta,
och där lägger jag det?

826
00:39:14,320 --> 00:39:17,260
Jo, i början av min lista,
eftersom denna nya lista sorteras.

827
00:39:17,260 --> 00:39:18,760
Och jag passera den ut.

828
00:39:18,760 --> 00:39:20,551
>> Var ska jag placera sju?

829
00:39:20,551 --> 00:39:21,050
Attans.

830
00:39:21,050 --> 00:39:23,174
Det måste åka dit, så
Jag måste göra en del kopiering.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Och nu sju går här.

833
00:39:28,480 --> 00:39:29,860
Nu ska jag gå vidare till sex.

834
00:39:29,860 --> 00:39:30,980
Nu är det ännu mer arbete.

835
00:39:30,980 --> 00:39:32,570
>> Åtta måste gå hit.

836
00:39:32,570 --> 00:39:33,920
Sju måste gå hit.

837
00:39:33,920 --> 00:39:35,450
Nu sex kan gå hit.

838
00:39:35,450 --> 00:39:37,950
Nu greppa jag fem.

839
00:39:37,950 --> 00:39:40,560
Nu åtta måste gå
här, sju har att gå här,

840
00:39:40,560 --> 00:39:43,650
sex måste gå här, och
nu fem och upprepa.

841
00:39:43,650 --> 00:39:46,610
Och jag är ganska mycket
flytta den ständigt.

842
00:39:46,610 --> 00:39:52,950
>> Så i slutet, detta algorithm-- vi ska
kalla det inför sort-- faktiskt

843
00:39:52,950 --> 00:39:55,020
har en hel del arbete, också.

844
00:39:55,020 --> 00:39:56,970
Det är bara annorlunda
typ av arbete än Ben.

845
00:39:56,970 --> 00:40:00,090
Ben arbete fick mig att gå
fram och tillbaka hela tiden,

846
00:40:00,090 --> 00:40:03,510
välja nästa mindre
elementet och om igen.

847
00:40:03,510 --> 00:40:06,660
Så det var detta mycket visuell typ av arbete.

848
00:40:06,660 --> 00:40:10,600
>> Denna andra algoritm, som fortfarande
correct-- det kommer att få jobbet done--

849
00:40:10,600 --> 00:40:12,800
bara ändrar mängden arbete.

850
00:40:12,800 --> 00:40:15,420
Det ser ut som du ursprungligen är
spara, eftersom du bara

851
00:40:15,420 --> 00:40:19,190
behandlar varje element
up front utan att gå alla

852
00:40:19,190 --> 00:40:20,930
vägen genom listan som Ben var.

853
00:40:20,930 --> 00:40:25,300
Men problemet är, i synnerhet i dessa
galna fall där det är allt bakåt,

854
00:40:25,300 --> 00:40:27,830
du är bara typ av
skjuta det hårda arbete

855
00:40:27,830 --> 00:40:30,360
tills du måste fixa dina misstag.

856
00:40:30,360 --> 00:40:33,919
>> Och så om du kan tänka dig här
åtta och sju och sex och fem

857
00:40:33,919 --> 00:40:36,710
och senare fyra och tre och två
flyttar sig igenom listan,

858
00:40:36,710 --> 00:40:39,060
Vi har just ändrat
typ av arbete vi gör.

859
00:40:39,060 --> 00:40:42,340
Istället för att göra det på
början av min iteration,

860
00:40:42,340 --> 00:40:45,250
Jag bara gör det på
slutet av varje iteration.

861
00:40:45,250 --> 00:40:50,550
Så visar det sig att denna algoritm,
Även i allmänhet kallas insättningssortering,

862
00:40:50,550 --> 00:40:52,190
är också i storleksordningen n kvadrat.

863
00:40:52,190 --> 00:40:56,480
Det är faktiskt inte bättre,
inget bättre alls.

864
00:40:56,480 --> 00:41:00,810
>> Men det finns en tredje metod
Jag skulle vilja uppmuntra oss att fundera över,

865
00:41:00,810 --> 00:41:02,970
som är det.

866
00:41:02,970 --> 00:41:07,850
Så antar att min lista, för enkelhets skull
igen, är fyra, en, tre,

867
00:41:07,850 --> 00:41:11,080
two-- bara fyra siffror.

868
00:41:11,080 --> 00:41:13,300
Ben hade bra intuition,
god människa intuition

869
00:41:13,300 --> 00:41:16,340
innan, genom vilken vi fast hela
lista eventually-- insättningssortering.

870
00:41:16,340 --> 00:41:18,020
Jag smickrade oss tillsammans.

871
00:41:18,020 --> 00:41:22,530
Men låt oss betrakta
enklaste sättet att åtgärda denna lista.

872
00:41:22,530 --> 00:41:24,110
>> Denna lista är inte sortering.

873
00:41:24,110 --> 00:41:26,130
Varför?

874
00:41:26,130 --> 00:41:31,920
På engelska förklara varför
det är faktiskt inte sortering.

875
00:41:31,920 --> 00:41:33,400
Vad betyder det inte ska sorteras?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: Det är inte sekventiella.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Inte sekventiella.

878
00:41:34,990 --> 00:41:35,822
Ge mig ett exempel.

879
00:41:35,822 --> 00:41:37,180
>> STUDENTEN sätta dem i ordning.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Ge mig ett mer specifikt exempel.

882
00:41:38,790 --> 00:41:39,832
>> STUDENTEN stigande ordning.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Ej stigande ordning.

884
00:41:41,206 --> 00:41:42,100
Vara mer exakt.

885
00:41:42,100 --> 00:41:45,190
Jag vet inte vad du menar med stigande.

886
00:41:45,190 --> 00:41:47,150
Vad är fel?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: Den minsta av
siffror inte är i det första utrymmet.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: Minsta antal s
inte är i det första utrymmet.

889
00:41:51,140 --> 00:41:52,120
Var mer specifik.

890
00:41:52,120 --> 00:41:55,000
Jag börjar komma på.

891
00:41:55,000 --> 00:41:59,470
Vi räknar, men
Vad är i ordning här?

892
00:41:59,470 --> 00:42:00,707
>> STUDENTEN nummerföljd.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: Numerisk sekvens.

894
00:42:02,040 --> 00:42:04,248
Allas slags hålla
det här-- mycket hög nivå.

895
00:42:04,248 --> 00:42:07,450
Bara bokstavligen berätta vad är
fel som en fem-årig styrka.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: Plus en.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Vad är det?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: Plus en.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Vad menar du plus ett?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Ge mig en annan fem år gammal.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Vad som är fel, mamma?

904
00:42:18,330 --> 00:42:19,940
Vad som är fel, pappa?

905
00:42:19,940 --> 00:42:22,808
Vad menar du detta inte sorteras?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: Det är inte rätt plats.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Vad är
inte på rätt plats?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Fyra.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, bra.

910
00:42:27,090 --> 00:42:29,110
Så fyra är inte där det ska vara.

911
00:42:29,110 --> 00:42:30,590
Framför allt är detta rätt?

912
00:42:30,590 --> 00:42:33,000
Fyra och en, den första
två siffror jag ser.

913
00:42:33,000 --> 00:42:34,930
Är det här rätt?

914
00:42:34,930 --> 00:42:36,427
Nej, de är i ordning, eller hur?

915
00:42:36,427 --> 00:42:38,135
I själva verket tror nu
om en dator också.

916
00:42:38,135 --> 00:42:40,824
Det kan bara titta på kanske en,
kanske två saker på once--

917
00:42:40,824 --> 00:42:43,240
och egentligen bara en sak
vid en tidpunkt, men den kan åtminstone

918
00:42:43,240 --> 00:42:45,790
titta på en sak sedan
Nästa sak bredvid den.

919
00:42:45,790 --> 00:42:47,380
>> Så är dessa för?

920
00:42:47,380 --> 00:42:48,032
Självklart inte.

921
00:42:48,032 --> 00:42:48,740
Så du vet vad?

922
00:42:48,740 --> 00:42:51,020
Varför tar vi inte barnet
steg åtgärdar felet

923
00:42:51,020 --> 00:42:53,410
istället för att göra dessa infall
algoritmer som Ben, där

924
00:42:53,410 --> 00:42:56,440
han slags fastställa det genom
looping igenom listan

925
00:42:56,440 --> 00:42:59,670
istället för att göra vad jag gjorde, där
Jag bara typ av fast det när vi går?

926
00:42:59,670 --> 00:43:03,650
Låt oss bara bokstavligen bryta ned
begreppet order-- nummerordning,

927
00:43:03,650 --> 00:43:06,990
kalla det vad du want--
in i dessa parvisa jämförelser.

928
00:43:06,990 --> 00:43:07,590
>> Fyra och en.

929
00:43:07,590 --> 00:43:09,970
Är detta rätt ordning?

930
00:43:09,970 --> 00:43:11,310
Så låt oss fixa det.

931
00:43:11,310 --> 00:43:14,700
En och fyra, och sedan
Vi ska bara kopiera den.

932
00:43:14,700 --> 00:43:15,560
Okej, bra.

933
00:43:15,560 --> 00:43:17,022
Jag fixade en och fyra.

934
00:43:17,022 --> 00:43:18,320
Tre och två?

935
00:43:18,320 --> 00:43:18,820
Nej.

936
00:43:18,820 --> 00:43:21,690
Låt mina ord matcha mina fingrar.

937
00:43:21,690 --> 00:43:23,695
Fyra och tre?

938
00:43:23,695 --> 00:43:27,930
>> Det är inte i ordning, så jag kommer
att göra en, tre, fyra, två.

939
00:43:27,930 --> 00:43:28,680
Okej bra.

940
00:43:28,680 --> 00:43:32,310
Nu fyra och två?

941
00:43:32,310 --> 00:43:33,370
Vi måste fixa det här också.

942
00:43:33,370 --> 00:43:36,700
Så en, tre, två, fyra.

943
00:43:36,700 --> 00:43:39,820
Så är det sorteras?

944
00:43:39,820 --> 00:43:43,170
Nej, men det närmare redas?

945
00:43:43,170 --> 00:43:48,930
>> Det är därför vi fast detta
misstag, fast vi detta misstag,

946
00:43:48,930 --> 00:43:50,370
och vi fast detta misstag.

947
00:43:50,370 --> 00:43:52,420
Så vi fast tre misstag utan tvekan.

948
00:43:52,420 --> 00:43:58,100
Fortfarande inte riktigt ser sorteras, men
det är objektivt närmare redas

949
00:43:58,100 --> 00:44:00,080
eftersom vi fast några av dessa misstag.

950
00:44:00,080 --> 00:44:02,047
>> Nu vad gör jag nu?

951
00:44:02,047 --> 00:44:03,630
Jag slags nått slutet av listan.

952
00:44:03,630 --> 00:44:05,680
Jag tycktes ha fast
alla misstag, men nej.

953
00:44:05,680 --> 00:44:08,510
Eftersom i detta fall, några siffror
kan ha bubblade upp närmare

954
00:44:08,510 --> 00:44:10,410
till ett annat nummer som
är fortfarande i ordning.

955
00:44:10,410 --> 00:44:12,951
Så låt oss göra det igen, och jag ska
bara göra det på plats den här gången.

956
00:44:12,951 --> 00:44:14,170
En och tre?

957
00:44:14,170 --> 00:44:14,720
Det är okej.

958
00:44:14,720 --> 00:44:16,070
Tre och två?

959
00:44:16,070 --> 00:44:17,560
Naturligtvis ingen, så låt oss ändra på det.

960
00:44:17,560 --> 00:44:19,160
Så två, tre.

961
00:44:19,160 --> 00:44:21,340
Tre och fyra?

962
00:44:21,340 --> 00:44:24,370
Och nu låt oss bara vara
särskilt pedantisk här.

963
00:44:24,370 --> 00:44:26,350
Är det sorteras?

964
00:44:26,350 --> 00:44:29,280
Du människor vet att det är för sortering.

965
00:44:29,280 --> 00:44:30,400
>> Jag ska försöka igen.

966
00:44:30,400 --> 00:44:31,900
Så Olivia föreslår jag försöker igen.

967
00:44:31,900 --> 00:44:32,530
Varför?

968
00:44:32,530 --> 00:44:35,810
Eftersom en dator inte har
lyxen av våra mänskliga ögon

969
00:44:35,810 --> 00:44:38,080
för att bara kasta en blick back-- OK, jag är klar.

970
00:44:38,080 --> 00:44:41,610
Hur datorn bestämma
att listan nu sorteras?

971
00:44:41,610 --> 00:44:44,590
Mekaniskt.

972
00:44:44,590 --> 00:44:47,650
>> Jag ska gå igenom
ännu en gång, och bara om jag

973
00:44:47,650 --> 00:44:51,190
inte göra / hitta några misstag kan jag
sedan sluta sig datorn Japp,

974
00:44:51,190 --> 00:44:51,980
vi är bra att gå.

975
00:44:51,980 --> 00:44:54,850
Så ett och två, två och
tre, tre och fyra.

976
00:44:54,850 --> 00:44:58,030
Nu kan jag definitivt säga att detta är
sorteras, eftersom jag inte gjort några ändringar.

977
00:44:58,030 --> 00:45:01,940
Nu skulle det vara ett fel och bara
dum om jag, datorn,

978
00:45:01,940 --> 00:45:05,640
frågade samma frågor igen
förväntar sig olika svar.

979
00:45:05,640 --> 00:45:07,110
Borde inte hända.

980
00:45:07,110 --> 00:45:08,600
>> Och så nu listan sorteras.

981
00:45:08,600 --> 00:45:12,630
Tyvärr, gångtid
denna algoritm är också n kvadrat.

982
00:45:12,630 --> 00:45:13,130
Varför?

983
00:45:13,130 --> 00:45:19,520
Eftersom du har n siffror, och i
värsta fall måste du flytta n nummer

984
00:45:19,520 --> 00:45:23,637
n gånger eftersom du måste fortsätta
tillbaka för att kontrollera och eventuellt korrigera

985
00:45:23,637 --> 00:45:24,220
dessa nummer.

986
00:45:24,220 --> 00:45:26,280
Och vi kan göra en mer
formell analys också.

987
00:45:26,280 --> 00:45:29,530
>> Så detta är allt för att säga att vi har tagit
tre olika metoder, en

988
00:45:29,530 --> 00:45:32,210
av dem omedelbart intuitivt
utanför bat från Ben

989
00:45:32,210 --> 00:45:35,170
till min föreslagna införandet
sort till denna

990
00:45:35,170 --> 00:45:38,540
där du typ av glömma
skogen för alla träd initialt.

991
00:45:38,540 --> 00:45:41,760
Men om du tar ett steg tillbaka,
voila, har vi fast sorterings begreppet.

992
00:45:41,760 --> 00:45:43,824
Så det här är, vågar säga,
en lägre nivå kanske

993
00:45:43,824 --> 00:45:45,740
än vissa av dessa andra
algoritmer, men låt oss

994
00:45:45,740 --> 00:45:48,550
se om vi inte kan visualisera
dessa med hjälp av detta.

995
00:45:48,550 --> 00:45:51,450
>> Så det här är några fina
mjukvara som någon

996
00:45:51,450 --> 00:45:56,110
skrev att använda färgrika barer som finns i
kommer att göra följande för oss.

997
00:45:56,110 --> 00:45:57,736
Var och en av dessa stänger representerar ett tal.

998
00:45:57,736 --> 00:46:00,026
Taller stapel, desto större
numret mindre bar,

999
00:46:00,026 --> 00:46:00,990
desto mindre antal.

1000
00:46:00,990 --> 00:46:05,880
Så helst vi vill ha en trevlig pyramid
där det börjar litet och blir stor,

1001
00:46:05,880 --> 00:46:08,330
och det skulle innebära att
dessa stänger sorteras.

1002
00:46:08,330 --> 00:46:11,200
Så jag kommer att gå vidare och välja,
till exempel Bens algoritm

1003
00:46:11,200 --> 00:46:13,990
first-- val slag.

1004
00:46:13,990 --> 00:46:16,220
>> Och märker vad den gör.

1005
00:46:16,220 --> 00:46:18,670
Det sätt som de har valt att
visualisera denna algoritm

1006
00:46:18,670 --> 00:46:22,090
är att, precis som jag var
promenader genom min lista,

1007
00:46:22,090 --> 00:46:24,710
Detta program är gång
genom sin nummerlistan,

1008
00:46:24,710 --> 00:46:28,160
belysa i rosa varje
nummer som det ser på.

1009
00:46:28,160 --> 00:46:32,360
Och vad är på väg att hända nu?

1010
00:46:32,360 --> 00:46:35,154
>> Det minsta antalet som
I eller Ben plötsligt fann

1011
00:46:35,154 --> 00:46:36,820
får flyttas till början av listan.

1012
00:46:36,820 --> 00:46:40,037
Och märker de gjorde vräka
det nummer som var där,

1013
00:46:40,037 --> 00:46:41,120
och det är väl bra.

1014
00:46:41,120 --> 00:46:42,600
Jag fick inte in i den detaljnivå.

1015
00:46:42,600 --> 00:46:44,308
Men vi måste lägga
det numret någonstans,

1016
00:46:44,308 --> 00:46:47,775
så vi just flyttat det till
öppen plats som skapades.

1017
00:46:47,775 --> 00:46:49,900
Så jag kommer att påskynda detta
upp, eftersom det annars

1018
00:46:49,900 --> 00:46:51,871
blir mycket omständlig snabbt.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animation Byggd det vi går.

1021
00:46:58,600 --> 00:47:01,850
Så nu samma princip
Jag tillämpade, men du

1022
00:47:01,850 --> 00:47:06,540
kan börja känna algoritmen, om du
kommer, eller se det lite tydligare.

1023
00:47:06,540 --> 00:47:13,190
Och denna algoritm har effekten att
välja nästa minsta elementet,

1024
00:47:13,190 --> 00:47:16,422
så du kommer att börja
se det ramp upp till vänster.

1025
00:47:16,422 --> 00:47:19,130
Och på varje iteration, som jag
föreslås gör det lite mindre arbete.

1026
00:47:19,130 --> 00:47:21,921
Det behöver inte gå hela vägen
tillbaka till den vänstra änden av listan,

1027
00:47:21,921 --> 00:47:23,900
eftersom det redan
vet de sorteras.

1028
00:47:23,900 --> 00:47:28,129
Så det slags känns som det är
accelererar, även om varje steg är

1029
00:47:28,129 --> 00:47:29,420
tar lika lång tid.

1030
00:47:29,420 --> 00:47:31,600
Det är bara färre steg kvar.

1031
00:47:31,600 --> 00:47:35,240
Och nu kan du slags känner
algoritm städa upp i slutet av det,

1032
00:47:35,240 --> 00:47:37,040
och faktiskt nu är det sorteras.

1033
00:47:37,040 --> 00:47:41,620
>> Så insättningssortering är klar.

1034
00:47:41,620 --> 00:47:43,600
Jag behöver nytt slumpmässigt matrisen.

1035
00:47:43,600 --> 00:47:45,940
Och märker jag kan bara
hålla randomisera det,

1036
00:47:45,940 --> 00:47:50,630
och vi kommer att få en uppskattning av
samma tillvägagångssätt, insättningssortering.

1037
00:47:50,630 --> 00:47:55,050
Låt mig sakta ner till här.

1038
00:47:55,050 --> 00:47:56,915
Låt oss börja att över.

1039
00:47:56,915 --> 00:47:57,414
Sluta.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Låt oss hoppa över fyra.

1042
00:48:02,410 --> 00:48:03,200
Det går vi.

1043
00:48:03,200 --> 00:48:04,190
Randomisera de array.

1044
00:48:04,190 --> 00:48:05,555
Och här go-- vi insättningssortering.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Spela.

1047
00:48:12,800 --> 00:48:17,280
Lägg märke till att det handlar om varje
elementet den stöter på en gång,

1048
00:48:17,280 --> 00:48:20,282
men om det hör hemma i
fel ställe meddelande

1049
00:48:20,282 --> 00:48:21,740
allt arbete som måste ske.

1050
00:48:21,740 --> 00:48:24,700
Vi måste hålla flytta mer
och flera element för att göra plats

1051
00:48:24,700 --> 00:48:27,340
för vi vill sätta på plats.

1052
00:48:27,340 --> 00:48:30,740
>> Så vi fokuserar på
vänstra änden av endast listan.

1053
00:48:30,740 --> 00:48:34,460
Märker vi inte ens har tittat at-- vi
har inte markerat i rosa något

1054
00:48:34,460 --> 00:48:35,610
till höger.

1055
00:48:35,610 --> 00:48:38,180
Vi är bara att göra med
problemen som vi går,

1056
00:48:38,180 --> 00:48:40,430
men vi skapar en hel del
arbeta för oss fortfarande.

1057
00:48:40,430 --> 00:48:44,410
Och så om vi påskynda denna
nu för att gå till fullbordan,

1058
00:48:44,410 --> 00:48:46,210
den har en annorlunda känsla att det faktiskt.

1059
00:48:46,210 --> 00:48:50,150
Det är bara att fokusera på den vänstra änden, men
göra lite mer arbete som needed--

1060
00:48:50,150 --> 00:48:53,230
slags utjämning saker
över, fastställande saker,

1061
00:48:53,230 --> 00:48:58,350
men handlar i slutändan med
varje element en i taget

1062
00:48:58,350 --> 00:49:07,740
tills vi får the-- bra, vi
alla vet hur det kommer att sluta,

1063
00:49:07,740 --> 00:49:09,700
så det är lite underwhelming kanske.

1064
00:49:09,700 --> 00:49:12,830
>> Men listan i end--
spoiler-- kommer att sorteras.

1065
00:49:12,830 --> 00:49:15,300
Så låt oss titta på en sista.

1066
00:49:15,300 --> 00:49:16,840
Vi kan inte bara hoppa nu.

1067
00:49:16,840 --> 00:49:18,000
Vi är nästan där.

1068
00:49:18,000 --> 00:49:19,980
Två att gå, en att gå.

1069
00:49:19,980 --> 00:49:22,680
Och voila.

1070
00:49:22,680 --> 00:49:23,450
Excellent.

1071
00:49:23,450 --> 00:49:27,220
>> Så nu ska vi göra ett sista,
åter randomisera med bubbelsortering.

1072
00:49:27,220 --> 00:49:31,690
Och lägg märke till här, speciellt om jag sakta
ner, betyder detta att hålla swooping igenom.

1073
00:49:31,690 --> 00:49:36,830
Men märker det bara gör parvis
comparisons-- slags lokala lösningar.

1074
00:49:36,830 --> 00:49:39,050
Men så fort vi får
I slutet av listan i rosa,

1075
00:49:39,050 --> 00:49:40,690
vad som kommer att behöva hända igen?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ja, det kommer att behöva
börja om, eftersom den endast

1078
00:49:46,830 --> 00:49:49,870
fasta parvisa sökord.

1079
00:49:49,870 --> 00:49:53,120
Och som kan ha avslöjat ytterligare andra.

1080
00:49:53,120 --> 00:49:58,950
Och så om du påskynda detta kommer du
se att mycket som namnet antyder,

1081
00:49:58,950 --> 00:50:01,870
den mindre elements-- eller snarare,
de större elements-- börjar

1082
00:50:01,870 --> 00:50:03,740
att bubbla upp till toppen, om man så vill.

1083
00:50:03,740 --> 00:50:07,380
Och de mindre elementen
börjar att bubbla ned till vänster.

1084
00:50:07,380 --> 00:50:10,780
Och faktiskt, det är den typen av
den visuella effekten också.

1085
00:50:10,780 --> 00:50:17,150
Och så detta kommer att hamna efterbehandling
på ett mycket liknande sätt, också.

1086
00:50:17,150 --> 00:50:19,160
>> Vi behöver inte uppehålla
på just detta.

1087
00:50:19,160 --> 00:50:21,010
Låt mig att öppna detta nu också.

1088
00:50:21,010 --> 00:50:24,040
Det finns några andra sorteringsalgoritmer
i världen, varav några

1089
00:50:24,040 --> 00:50:25,580
fångas här.

1090
00:50:25,580 --> 00:50:29,960
Och särskilt för elever som inte är
nödvändigtvis visuella eller matematiskt,

1091
00:50:29,960 --> 00:50:31,930
som vi gjorde innan vi kan
även göra detta audially

1092
00:50:31,930 --> 00:50:34,210
Om vi ​​associera ett ljud med detta.

1093
00:50:34,210 --> 00:50:36,990
Och bara för skojs skull, här är en
några olika algoritmer,

1094
00:50:36,990 --> 00:50:40,950
och en av dem i synnerhet du
kommer att märka kallas "merge sort."

1095
00:50:40,950 --> 00:50:43,250
>> Det är faktiskt en fundamentalt
bättre algoritm,

1096
00:50:43,250 --> 00:50:45,860
sådan att merge sort, en av
de du är på väg att se,

1097
00:50:45,860 --> 00:50:49,170
inte är storleksordningen n i kvadrat.

1098
00:50:49,170 --> 00:50:57,280
Det är i storleksordningen n gånger loggar av
n, som faktiskt är mindre och därmed

1099
00:50:57,280 --> 00:50:58,940
snabbare än de andra tre.

1100
00:50:58,940 --> 00:51:00,670
Och det finns en annan par
fåniga de som vi får se.

1101
00:51:00,670 --> 00:51:01,933
>> Så här går vi med vissa ljud.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Detta är insättningssortering, så igen
det är bara att göra med elementen

1104
00:51:10,490 --> 00:51:13,420
när de kommer.

1105
00:51:13,420 --> 00:51:17,180
Detta är bubbelsortering, så det är
betrakta dem par åt gången.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Och återigen, de största delarna
bubblar upp till toppen.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Nästa upp val slag.

1110
00:51:41,710 --> 00:51:45,420
Det här är Ben algoritm, där
igen han välja iterativt

1111
00:51:45,420 --> 00:51:46,843
nästa minsta elementet.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Och återigen, nu kan du verkligen höra det
det påskynda men endast i den mån

1114
00:51:53,900 --> 00:51:58,230
eftersom det gör mindre och mindre
arbeta på varje iteration.

1115
00:51:58,230 --> 00:52:04,170
Detta är den snabbare en, merge sort,
som sortering kluster av siffror

1116
00:52:04,170 --> 00:52:05,971
tillsammans och sedan kombinera dem.

1117
00:52:05,971 --> 00:52:07,720
Så look-- vänster
hälften redan sortering.

1118
00:52:07,720 --> 00:52:14,165
>> Nu är det sortera den högra halvan, och
nu det kommer att kombinera dem till en.

1119
00:52:14,165 --> 00:52:19,160
Detta är något som kallas "Gnome sort."

1120
00:52:19,160 --> 00:52:23,460
Och du kan typ av se att
det kommer fram och tillbaka,

1121
00:52:23,460 --> 00:52:27,950
fastställande av arbete lite här och
där innan den fortsätter till nya arbeten.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Och det är allt.

1124
00:52:33,692 --> 00:52:36,400
Det finns en annan sorts, som är
egentligen bara för akademiska ändamål,

1125
00:52:36,400 --> 00:52:40,980
kallas "dum sortera,", som tar
dina data, sorterar det slumpmässigt,

1126
00:52:40,980 --> 00:52:43,350
och sedan kontrollerar om den sorteras.

1127
00:52:43,350 --> 00:52:47,880
Och om det inte är, åter sorterar det det
slumpmässigt, kontrollerar om det sorteras,

1128
00:52:47,880 --> 00:52:49,440
och om inte upprepas.

1129
00:52:49,440 --> 00:52:52,660
Och i teorin, probabilistiskt
detta kommer att slutföra,

1130
00:52:52,660 --> 00:52:54,140
men efter en hel del tid.

1131
00:52:54,140 --> 00:52:56,930
Det är inte den mest
effektiva av algoritmer.

1132
00:52:56,930 --> 00:53:02,550
Så några frågor om de
särskilda algoritmer eller något

1133
00:53:02,550 --> 00:53:04,720
relaterade där också?

1134
00:53:04,720 --> 00:53:09,430
>> Nåväl, låt oss nu retas isär vad alla
dessa linjer är att jag har dragit

1135
00:53:09,430 --> 00:53:15,090
och vad jag antar datorn
kan göra under huven.

1136
00:53:15,090 --> 00:53:18,650
Jag skulle vilja påstå att alla dessa siffror
Jag håller drawing-- de behöver för att få

1137
00:53:18,650 --> 00:53:21,330
lagras någonstans i minnet.

1138
00:53:21,330 --> 00:53:24,130
Vi kommer att bli av med den här killen nu också.

1139
00:53:24,130 --> 00:53:30,110
>> Så en bit av minne i en
computer-- så RAM DIMM är

1140
00:53:30,110 --> 00:53:35,480
vad vi sökte i går, dubbel
inline memory module-- ser ut så här.

1141
00:53:35,480 --> 00:53:39,370
Och var och en av dessa små svarta chips
finns viss antal byte, typiskt.

1142
00:53:39,370 --> 00:53:44,380
Och sedan guld stift är som
ledningar som ansluter den till datorn,

1143
00:53:44,380 --> 00:53:47,521
och den gröna kisel kortet är bara
vad håller allting tillsammans.

1144
00:53:47,521 --> 00:53:48,770
Så vad betyder det egentligen?

1145
00:53:48,770 --> 00:53:53,180
Om jag sorts dra samma bild,
Låt oss anta att för enkelhetens skull

1146
00:53:53,180 --> 00:53:55,280
att detta DIMM, dubbel
inline minnesmodul

1147
00:53:55,280 --> 00:54:00,530
är en gigabyte RAM-minne, en gigabyte
minne, vilket är hur många byte totalt?

1148
00:54:00,530 --> 00:54:02,100
En gigabyte är hur många byte?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Mer än det.

1151
00:54:06,030 --> 00:54:09,960
1124 är kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega är miljoner.

1153
00:54:11,730 --> 00:54:14,570
Giga är en miljard.

1154
00:54:14,570 --> 00:54:15,070
>> Jag ljuger?

1155
00:54:15,070 --> 00:54:16,670
Kan vi även läsa etiketten?

1156
00:54:16,670 --> 00:54:19,920
Detta är faktiskt 128
gigabyte, det är så mycket mer.

1157
00:54:19,920 --> 00:54:22,130
Men vi ska låtsas detta
är bara en gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Så det innebär att det finns en miljard
byte minne tillgängliga för mig

1159
00:54:25,640 --> 00:54:29,770
eller 8 miljarder bitar, men vi kommer
att tala i termer av byte nu,

1160
00:54:29,770 --> 00:54:30,750
går vidare.

1161
00:54:30,750 --> 00:54:36,330
>> Så vad det betyder är att detta är
en bitgrupp, är detta ytterligare ett byte,

1162
00:54:36,330 --> 00:54:38,680
detta är ett annat byte,
och om vi verkligen ville

1163
00:54:38,680 --> 00:54:43,280
att vara specifik vi skulle behöva
rita en miljard små fyrkanter.

1164
00:54:43,280 --> 00:54:44,320
Men vad betyder det?

1165
00:54:44,320 --> 00:54:46,420
Nåväl, låt mig bara zooma
på den här bilden.

1166
00:54:46,420 --> 00:54:50,900
Om jag har något som ser
så här nu, det är fyra byte.

1167
00:54:50,900 --> 00:54:53,710
>> Och så jag kunde sätta fyra siffror här.

1168
00:54:53,710 --> 00:54:54,990
Ett två tre Fyra.

1169
00:54:54,990 --> 00:55:00,170
Eller jag kunde sätta fyra bokstäver eller symboler.

1170
00:55:00,170 --> 00:55:02,620
"Hallå!" kunde gå där,
eftersom var och en av bokstäverna,

1171
00:55:02,620 --> 00:55:04,370
vi diskuterat tidigare,
kan representeras

1172
00:55:04,370 --> 00:55:06,650
med åtta bitar eller ASCII eller en byte.

1173
00:55:06,650 --> 00:55:09,370
Så med andra ord, kan du
sätta 8 miljarder saker inuti

1174
00:55:09,370 --> 00:55:11,137
av detta en pinne av minne.

1175
00:55:11,137 --> 00:55:14,345
Nu vad betyder det att ställa saker och ting tillbaka
att rygg mot rygg i minnet så här?

1176
00:55:14,345 --> 00:55:17,330
Detta är vad en programmerare
skulle kalla en "array".

1177
00:55:17,330 --> 00:55:21,250
I ett datorprogram, tror du inte
om den underliggande hårdvaran, per se.

1178
00:55:21,250 --> 00:55:24,427
Du tror bara på dig själv som har
tillgång till en miljard byte totalt,

1179
00:55:24,427 --> 00:55:26,010
och du kan vad du vill med det.

1180
00:55:26,010 --> 00:55:27,880
Men för enkelhetens skull
Det är allmänt användbar

1181
00:55:27,880 --> 00:55:31,202
att hålla ditt minne höger
bredvid varandra som här.

1182
00:55:31,202 --> 00:55:33,660
Så om jag zoomar in på this--
eftersom vi verkligen inte gå

1183
00:55:33,660 --> 00:55:39,310
att dra en miljard små squares--
Låt oss anta att detta forum representerar

1184
00:55:39,310 --> 00:55:40,610
att pinne av minne nu.

1185
00:55:40,610 --> 00:55:43,800
Och jag ska bara dra så många som min
markör hamnar ger mig här.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Så nu har vi en pinne
minne på kortet

1188
00:55:52,300 --> 00:55:56,400
som har fått en, två, tre, fyra, fem,
sex, ett, två, tre, fyra, fem, sex,

1189
00:55:56,400 --> 00:56:01,130
seven-- så 42 bytes av
minne på den totala skärmen.

1190
00:56:01,130 --> 00:56:01,630
Tack.

1191
00:56:01,630 --> 00:56:02,838
Ja, det gjorde min aritmetik rätt.

1192
00:56:02,838 --> 00:56:05,120
Så 42 byte minne här.

1193
00:56:05,120 --> 00:56:06,660
Så vad betyder detta egentligen?

1194
00:56:06,660 --> 00:56:09,830
Tja, en programmerare
skulle faktiskt i allmänhet

1195
00:56:09,830 --> 00:56:12,450
tänka på detta minne som adresserbara.

1196
00:56:12,450 --> 00:56:16,630
Med andra ord, var och en av dessa
platser i minnet, i hårdvara,

1197
00:56:16,630 --> 00:56:18,030
har en unik adress.

1198
00:56:18,030 --> 00:56:22,020
>> Det är inte så komplicerat som en Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Istället är det bara en siffra.

1200
00:56:23,830 --> 00:56:27,930
Detta är bytenummer noll, är detta
en, det är två, det är tre,

1201
00:56:27,930 --> 00:56:30,327
och detta är 41.

1202
00:56:30,327 --> 00:56:30,910
Vänta en minut.

1203
00:56:30,910 --> 00:56:32,510
Jag trodde jag sa 42 för en stund sedan.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Jag började räkna på noll,
så det är faktiskt rätt.

1206
00:56:37,772 --> 00:56:40,980
Nu har vi inte att faktiskt dra det
som ett rutnät, och om du ritar det som ett rutnät

1207
00:56:40,980 --> 00:56:43,520
Jag tror saker faktiskt
få lite missvisande.

1208
00:56:43,520 --> 00:56:46,650
Vad en programmerare skulle,
i sitt eget sinne,

1209
00:56:46,650 --> 00:56:50,310
i allmänhet tänker på detta
minne som är precis som ett band,

1210
00:56:50,310 --> 00:56:53,340
som en bit maskeringstejp
som bara går på och för evigt

1211
00:56:53,340 --> 00:56:54,980
eller tills du får slut på minne.

1212
00:56:54,980 --> 00:56:59,200
Så ett allt vanligare sätt att dra
och bara tänka på minnet

1213
00:56:59,200 --> 00:57:03,710
skulle vara att detta är byte noll, en,
två, tre, och sedan dot, punkt, punkt.

1214
00:57:03,710 --> 00:57:07,650
Och du har 42 sådana byte totalt, även
men fysiskt Det kan faktiskt

1215
00:57:07,650 --> 00:57:09,480
vara något mer om detta.

1216
00:57:09,480 --> 00:57:12,850
>> Så om du nu tänker på din
minne som detta, precis som ett band,

1217
00:57:12,850 --> 00:57:17,640
Detta är vad en programmerare igen
skulle kalla en rad minne.

1218
00:57:17,640 --> 00:57:20,660
Och när du vill faktiskt lagra
något i en dators minne,

1219
00:57:20,660 --> 00:57:23,290
du vanligtvis gör lagra saker
back-to-back till back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Så vi har pratat om siffror.

1221
00:57:25,010 --> 00:57:30,880
Och när jag ville lösa problem
som fyra, en, tre, två,

1222
00:57:30,880 --> 00:57:33,820
även om jag var bara att dra
bara fyra siffror, en, tre,

1223
00:57:33,820 --> 00:57:39,490
två på bordet, datorn skulle
verkligen har denna inställning i minnet.

1224
00:57:39,490 --> 00:57:43,347
>> Och vad skulle vara bredvid
två i datorns minne?

1225
00:57:43,347 --> 00:57:44,680
Tja, det finns inget svar på det.

1226
00:57:44,680 --> 00:57:45,770
Vi vet inte riktigt.

1227
00:57:45,770 --> 00:57:48,200
Och så länge som
Datorn behöver inte det,

1228
00:57:48,200 --> 00:57:51,440
Det behöver inte bry sig om vad är nästa
till siffrorna det bryr sig om.

1229
00:57:51,440 --> 00:57:55,130
Och när jag sade tidigare att en dator
kan bara titta på en adress i taget,

1230
00:57:55,130 --> 00:57:56,170
Detta är typ av varför.

1231
00:57:56,170 --> 00:57:59,490
>> Inte olikt en post
spelare och ett läshuvud

1232
00:57:59,490 --> 00:58:03,030
bara att kunna titta på en viss
spår i en fysisk old-school rekord

1233
00:58:03,030 --> 00:58:06,500
åt gången, på liknande sätt
kan en dator tack

1234
00:58:06,500 --> 00:58:09,810
till sin CPU och dess
Intel instruktionsuppsättning,

1235
00:58:09,810 --> 00:58:12,480
bland vars instruktion
läses från minnet

1236
00:58:12,480 --> 00:58:15,590
eller spara till memory-- en
Datorn kan bara se

1237
00:58:15,590 --> 00:58:19,210
på en plats åt time--
ibland en kombination av dem,

1238
00:58:19,210 --> 00:58:21,770
men egentligen bara en plats åt gången.

1239
00:58:21,770 --> 00:58:24,770
Så när vi gjorde
dessa olika algoritmer,

1240
00:58:24,770 --> 00:58:28,110
Jag är inte bara skriver i en
vacuum-- fyra, en, tre, två.

1241
00:58:28,110 --> 00:58:30,849
Dessa siffror faktiskt tillhör
någonstans fysiskt i minnet.

1242
00:58:30,849 --> 00:58:32,890
Så det finns lilla
transistorer eller någon form

1243
00:58:32,890 --> 00:58:35,840
av elektronik på undersidan av
huv lagra dessa värden.

1244
00:58:35,840 --> 00:58:40,460
>> Och totalt, hur många bitar
involverade just nu, bara för att vara klart?

1245
00:58:40,460 --> 00:58:45,580
Så det här är fyra byte, eller
nu är det 32 ​​bitar totalt.

1246
00:58:45,580 --> 00:58:49,280
Så det finns faktiskt 32 nollor och
som ingår i dessa fyra saker.

1247
00:58:49,280 --> 00:58:52,070
Det finns ännu mer här, men
igen vi inte bryr sig om det.

1248
00:58:52,070 --> 00:58:55,120
>> Så nu ska vi be en annan
fråga med hjälp av minne,

1249
00:58:55,120 --> 00:58:57,519
eftersom det i slutet
av dagen är i varians.

1250
00:58:57,519 --> 00:59:00,310
Oavsett vad vi kan göra med
datorn, i slutet av dagen

1251
00:59:00,310 --> 00:59:02,560
hårdvaran är fortfarande den
samma under huven.

1252
00:59:02,560 --> 00:59:04,670
Hur skulle jag lagra ett ord här?

1253
00:59:04,670 --> 00:59:09,710
Tja, ett ord i en dator som
"Hallå!" skulle lagras precis som denna.

1254
00:59:09,710 --> 00:59:12,300
Och om du ville ha en längre
ord, kan du helt enkelt

1255
00:59:12,300 --> 00:59:19,120
skriva det och säga något
som "hej" och butik som här.

1256
00:59:19,120 --> 00:59:23,930
>> Och så här också, denna contiguousness
är faktiskt en fördel,

1257
00:59:23,930 --> 00:59:26,530
eftersom en dator kan bara
läses från höger till vänster.

1258
00:59:26,530 --> 00:59:28,680
Men här är en fråga.

1259
00:59:28,680 --> 00:59:33,480
Inom ramen för detta ord,
h-e-l-l-o, utropstecken,

1260
00:59:33,480 --> 00:59:38,740
hur kan datorn vet var
ord börjar och där ordet slutar?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
I samband med siffror,
Hur fungerar datorn

1263
00:59:43,800 --> 00:59:48,396
veta hur länge den sekvens av
nummer är eller där det börjar?

1264
00:59:48,396 --> 00:59:50,270
Tja, visar det out--
och vi kommer inte gå alltför mycket

1265
00:59:50,270 --> 00:59:54,970
in i denna nivå av detail--
datorer flytta runt saker i minnet

1266
00:59:54,970 --> 00:59:57,800
bokstavligen med hjälp av dessa adresser.

1267
00:59:57,800 --> 01:00:02,080
Så i en dator, om du är
skriva kod för att lagra saker

1268
01:00:02,080 --> 01:00:05,800
som ord, vad du är
verkligen göra är att skriva

1269
01:00:05,800 --> 01:00:11,320
uttryck som minns var i
datorns minne dessa ord är.

1270
01:00:11,320 --> 01:00:14,370
Så låt mig göra en mycket,
mycket enkelt exempel.

1271
01:00:14,370 --> 01:00:18,260
>> Jag kommer att gå vidare och
öppna upp en enkel textprogram,

1272
01:00:18,260 --> 01:00:20,330
och jag kommer att skapa
en fil som heter hej.c.

1273
01:00:20,330 --> 01:00:22,849
Det mesta av denna information vi
kommer inte att gå in i detalj,

1274
01:00:22,849 --> 01:00:25,140
men jag kommer att skriva en
program i samma språk,

1275
01:00:25,140 --> 01:00:31,140
C. Detta är långt mer skrämmande,
Jag skulle vilja hävda, än Scratch,

1276
01:00:31,140 --> 01:00:32,490
men det är mycket i samma anda.

1277
01:00:32,490 --> 01:00:34,364
Faktum är att dessa lockigt
braces-- du kan sorts

1278
01:00:34,364 --> 01:00:37,820
tänka på vad jag gjorde precis som denna.

1279
01:00:37,820 --> 01:00:39,240
>> Låt oss göra detta, faktiskt.

1280
01:00:39,240 --> 01:00:45,100
När gröna flaggan klickade,
gör följande.

1281
01:00:45,100 --> 01:00:50,210
Jag vill skriva ut "Hej."

1282
01:00:50,210 --> 01:00:51,500
Så det här är nu pseudokod.

1283
01:00:51,500 --> 01:00:53,000
Jag slags sudda ut gränserna.

1284
01:00:53,000 --> 01:00:56,750
I C, detta språk jag talar
om denna linje tryck hello

1285
01:00:56,750 --> 01:01:01,940
faktiskt blir "printf" med
några parenteser och ett semikolon.

1286
01:01:01,940 --> 01:01:03,480
>> Men det är exakt samma idé.

1287
01:01:03,480 --> 01:01:06,730
Och det är mycket användarvänlig
"När grön flagg klickade" blir

1288
01:01:06,730 --> 01:01:10,182
mycket mer svårbegripliga "int main tomrum."

1289
01:01:10,182 --> 01:01:12,890
Och detta har verkligen ingen kartläggning,
så jag ska bara ignorera det.

1290
01:01:12,890 --> 01:01:17,210
Men klammerparenteserna är som
krökta pusselbitar som denna.

1291
01:01:17,210 --> 01:01:18,700
>> Så du kan slags gissa.

1292
01:01:18,700 --> 01:01:22,357
Även om du har aldrig programmerat förut,
vad det här programmet förmodligen göra?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Förmodligen skriver hello
med ett utropstecken.

1295
01:01:28,000 --> 01:01:29,150
>> Så låt oss prova det.

1296
01:01:29,150 --> 01:01:30,800
Jag kommer att spara det.

1297
01:01:30,800 --> 01:01:34,000
Och detta är, återigen, en mycket
gamla skolmiljön.

1298
01:01:34,000 --> 01:01:35,420
Jag kan inte klicka, jag kan inte dra.

1299
01:01:35,420 --> 01:01:36,910
Jag måste skriva kommandon.

1300
01:01:36,910 --> 01:01:41,320
Så jag vill köra mitt program, så
Jag kan göra detta, som hej.c.

1301
01:01:41,320 --> 01:01:42,292
Det är filen jag sprang.

1302
01:01:42,292 --> 01:01:43,500
Men vänta, jag saknar ett steg.

1303
01:01:43,500 --> 01:01:46,470
Vad gjorde vi säga är en nödvändig
steg för ett språk som C?

1304
01:01:46,470 --> 01:01:49,470
Jag har just skrivit källa
kod, men vad behöver jag?

1305
01:01:49,470 --> 01:01:50,670
Ja, jag behöver en kompilator.

1306
01:01:50,670 --> 01:01:57,670
Så på min Mac här, har jag en
program som kallas GCC, GNU C-kompilator,

1307
01:01:57,670 --> 01:02:03,990
vilket gör att jag kan göra this-- tur
min källkod i, vi kallar det,

1308
01:02:03,990 --> 01:02:04,930
maskinkod.

1309
01:02:04,930 --> 01:02:10,180
>> Och jag kan se att,
återigen, enligt följande, dessa

1310
01:02:10,180 --> 01:02:14,090
är nollor och ettor I bara
skapas från min källkod,

1311
01:02:14,090 --> 01:02:15,730
alla nollor och ettor.

1312
01:02:15,730 --> 01:02:17,770
Och om jag vill köra
min program-- det händer

1313
01:02:17,770 --> 01:02:23,010
att kallas a.out för
historisk reasons-- "hej."

1314
01:02:23,010 --> 01:02:24,070
Jag kan köra den igen.

1315
01:02:24,070 --> 01:02:25,690
Hallå Hallå Hallå.

1316
01:02:25,690 --> 01:02:27,430
Och det verkar fungera.

1317
01:02:27,430 --> 01:02:31,000
>> Men det betyder någonstans i mitt
datorns minne är orden

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, utropstecken.

1319
01:02:35,279 --> 01:02:38,070
Och det visar sig, precis som en sidoreplik,
vad en dator skulle typiskt

1320
01:02:38,070 --> 01:02:40,550
göra så att det vet var
saker och ting börjar och end-- det är

1321
01:02:40,550 --> 01:02:42,460
kommer att sätta en speciell symbol här.

1322
01:02:42,460 --> 01:02:46,064
Och konventionen är att sätta
nummer noll i slutet av ett ord

1323
01:02:46,064 --> 01:02:48,230
så att du vet om det
faktiskt slutar, så att du

1324
01:02:48,230 --> 01:02:52,750
inte hålla skriva ut mer och mer
tecken än du tänker faktiskt.

1325
01:02:52,750 --> 01:02:55,400
>> Men takeaway här, även
även om detta är ganska svårbegripliga,

1326
01:02:55,400 --> 01:02:58,140
är att det är i slutändan
relativt enkel.

1327
01:02:58,140 --> 01:03:04,550
Du fick en slags band, en tom
utrymme där du kan skriva brev.

1328
01:03:04,550 --> 01:03:07,150
Du måste helt enkelt ha en
speciell symbol, som godtyckligt

1329
01:03:07,150 --> 01:03:10,316
siffran noll, att sätta i slutet av
dina ord så att datorn vet,

1330
01:03:10,316 --> 01:03:13,410
åh, jag ska sluta skriva ut efter
Jag ser utropstecken.

1331
01:03:13,410 --> 01:03:16,090
Eftersom nästa sak där
är en ASCII-värde på noll,

1332
01:03:16,090 --> 01:03:19,125
eller null-tecknet som
någon skulle kalla det.

1333
01:03:19,125 --> 01:03:21,500
Men det är lite av ett problem
här, och låt oss återgå

1334
01:03:21,500 --> 01:03:23,320
till nummer för en stund.

1335
01:03:23,320 --> 01:03:28,720
Antag att jag gör, i själva verket,
har en matris av nummer,

1336
01:03:28,720 --> 01:03:30,730
och antag att den
program jag skriver är

1337
01:03:30,730 --> 01:03:34,680
som en klass bok för lärare
och en lärare klassrum.

1338
01:03:34,680 --> 01:03:38,720
Och detta program tillåter honom eller henne
att skriva in elevernas poäng

1339
01:03:38,720 --> 01:03:39,960
på frågesporter.

1340
01:03:39,960 --> 01:03:43,750
Och anta att studenten får
100 på deras första quiz, kanske

1341
01:03:43,750 --> 01:03:49,920
som en 80 på nästa en, sedan en
75, sedan en 90 på fjärde testet.

1342
01:03:49,920 --> 01:03:54,150
>> Så vid denna tidpunkt i historien,
matrisen är av storlek fyra.

1343
01:03:54,150 --> 01:03:58,470
Det finns absolut mer minne i
dator, men arrayen, så att säga,

1344
01:03:58,470 --> 01:04:00,350
är storlek fyra.

1345
01:04:00,350 --> 01:04:06,060
Antag nu att läraren vill
att tilldela en femtedel frågesport för klassen.

1346
01:04:06,060 --> 01:04:08,510
Jo, en av de saker han
eller hon kommer att behöva göra

1347
01:04:08,510 --> 01:04:10,650
är nu lagra ett extra värde här.

1348
01:04:10,650 --> 01:04:15,490
Men om gruppen läraren har
skapad i detta program är av storlek för,

1349
01:04:15,490 --> 01:04:22,440
ett av problemet med en array är att
du kan inte bara fortsätta att lägga på minnet.

1350
01:04:22,440 --> 01:04:26,470
Eftersom det om en annan del av
Programmet har ordet "hej" just där?

1351
01:04:26,470 --> 01:04:29,650
>> Med andra ord kan mitt minne vara
användas för något i ett program.

1352
01:04:29,650 --> 01:04:33,250
Och om i förväg jag skrev i, hej,
Jag vill mata in fyra frågesport poäng,

1353
01:04:33,250 --> 01:04:34,784
de kan gå här och här.

1354
01:04:34,784 --> 01:04:37,700
Och om du plötsligt ändrar dig
senare och säga att jag vill en femtedel frågesport

1355
01:04:37,700 --> 01:04:40,872
poäng, kan du inte bara
lägga den var du vill,

1356
01:04:40,872 --> 01:04:42,580
eftersom det om det
minne som används

1357
01:04:42,580 --> 01:04:45,990
för något else-- något annat program
eller något annat inslag i programmet

1358
01:04:45,990 --> 01:04:46,910
att du kör?

1359
01:04:46,910 --> 01:04:50,650
Så du måste tänka i förväg
hur du vill lagra data,

1360
01:04:50,650 --> 01:04:54,480
eftersom du nu har målat
själv till en digital hörn.

1361
01:04:54,480 --> 01:04:57,280
>> Så en lärare kanske i stället
säger när du skriver ett program

1362
01:04:57,280 --> 01:04:59,360
att lagra sin
kvaliteter, vet du vad?

1363
01:04:59,360 --> 01:05:04,180
Jag kommer att begära,
när du skriver mitt program,

1364
01:05:04,180 --> 01:05:12,070
att jag vill noll, ett, två, tre,
fyra, fem, sex, åtta grader totalt.

1365
01:05:12,070 --> 01:05:15,320
Så en, två, tre, fyra,
fem, sex, sju, åtta.

1366
01:05:15,320 --> 01:05:18,612
Läraren kan bara över fördela
minne när du skriver hans eller hennes program

1367
01:05:18,612 --> 01:05:19,570
och säga, vet du vad?

1368
01:05:19,570 --> 01:05:22,236
Jag kommer aldrig att tilldela mer
än åtta frågesporter i en termin.

1369
01:05:22,236 --> 01:05:23,130
Det är bara galen.

1370
01:05:23,130 --> 01:05:24,470
Jag kommer aldrig att fördela det.

1371
01:05:24,470 --> 01:05:28,270
Så att detta sätt han eller hon har
flexibilitet att lagra elevresultat,

1372
01:05:28,270 --> 01:05:33,010
som 75, 90, och kanske en extra där
eleven fick extra kredit, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Men om läraren aldrig
använder dessa tre platser,

1374
01:05:36,130 --> 01:05:38,860
det finns en intuitiv takeaway här.

1375
01:05:38,860 --> 01:05:41,410
Han eller hon är bara slöseri med utrymme.

1376
01:05:41,410 --> 01:05:44,790
Så med andra ord, det är det här
gemensam kompromiss i programmering

1377
01:05:44,790 --> 01:05:48,241
där du antingen kan fördela
exakt så mycket minne som du vill,

1378
01:05:48,241 --> 01:05:51,490
Fördelen med det är att du är super
efficient-- du inte vara slösaktig

1379
01:05:51,490 --> 01:05:54,640
på all-- men nackdelen som
är vad händer om du ändrar dig när

1380
01:05:54,640 --> 01:05:58,780
med hjälp av program som du vill spara
mer data än du tänkt.

1381
01:05:58,780 --> 01:06:03,030
>> Så kanske lösningen är, då,
skriva dina program på ett sådant sätt

1382
01:06:03,030 --> 01:06:05,605
att de använder mer minne
än de faktiskt behöver.

1383
01:06:05,605 --> 01:06:07,730
Detta sätt du inte kommer
att köra in det problemet,

1384
01:06:07,730 --> 01:06:09,730
men du vara slösaktig.

1385
01:06:09,730 --> 01:06:12,960
Och ju mer minne programmet använder,
som vi diskuterade i går, desto mindre

1386
01:06:12,960 --> 01:06:15,410
minne som är tillgängligt
för andra program,

1387
01:06:15,410 --> 01:06:18,790
desto snabbare datorn kan bromsa
ner på grund av virtuellt minne.

1388
01:06:18,790 --> 01:06:22,670
Och så den idealiska lösningen skulle vara vad?

1389
01:06:22,670 --> 01:06:24,610
>> Under-fördelning verkar dålig.

1390
01:06:24,610 --> 01:06:27,030
Över fördelning verkar dålig.

1391
01:06:27,030 --> 01:06:31,120
Så vad kan vara en bättre lösning?

1392
01:06:31,120 --> 01:06:32,390
Omfördela.

1393
01:06:32,390 --> 01:06:33,590
Vara mer dynamisk.

1394
01:06:33,590 --> 01:06:37,520
Inte tvinga dig själv att välja en
priori i början, vad du vill.

1395
01:06:37,520 --> 01:06:41,370
Och absolut inte överdelar,
så att du inte vara slösaktig.

1396
01:06:41,370 --> 01:06:45,770
>> Och på så sätt uppnå detta mål, vi
måste kasta denna datastruktur,

1397
01:06:45,770 --> 01:06:48,100
så att säga, bort.

1398
01:06:48,100 --> 01:06:51,080
Och så vad en programmerare
kommer typiskt att använda

1399
01:06:51,080 --> 01:06:55,940
är något som kallas inte en
array utan en länkad lista.

1400
01:06:55,940 --> 01:07:00,860
Med andra ord, han eller hon kommer att
börja tänka på deras minne

1401
01:07:00,860 --> 01:07:05,280
såsom varande typ av en form, att de
kan rita på följande sätt.

1402
01:07:05,280 --> 01:07:08,520
Om jag vill lagra ett nummer i
en program-- så det är September,

1403
01:07:08,520 --> 01:07:12,600
Jag har gett mina elever en frågesport; jag vill
att lagra elevernas första frågesport,

1404
01:07:12,600 --> 01:07:16,220
och de fick en 100 på det-- I
tänker be min dator,

1405
01:07:16,220 --> 01:07:19,540
med hjälp av programmet har jag
skriven för en bit av minnet.

1406
01:07:19,540 --> 01:07:22,570
Och jag kommer att lagra
nummer 100 i det, och det är det.

1407
01:07:22,570 --> 01:07:24,820
>> Sedan ett par veckor senare
när jag får mitt andra frågesport,

1408
01:07:24,820 --> 01:07:27,890
och det är dags att skriva
i att 90% kommer jag

1409
01:07:27,890 --> 01:07:32,129
att be datorn, hej, dator,
kan jag har en annan bit av minne?

1410
01:07:32,129 --> 01:07:34,170
Det kommer att ge mig detta
tom bit av minnet.

1411
01:07:34,170 --> 01:07:39,370
Jag kommer att sätta i antalet 90,
men i mitt program på något sätt eller other--

1412
01:07:39,370 --> 01:07:42,100
och vi kommer inte att oroa sig
syntaxen för this-- jag behöver

1413
01:07:42,100 --> 01:07:44,430
att på något sätt kedja dessa saker tillsammans.

1414
01:07:44,430 --> 01:07:47,430
Och jag ska kedja ihop dem med
vad som ser ut som en pil här.

1415
01:07:47,430 --> 01:07:50,050
>> Den tredje quiz som kommer upp,
Jag kommer att säga, hej, dator,

1416
01:07:50,050 --> 01:07:51,680
ge mig en bit av minnet.

1417
01:07:51,680 --> 01:07:54,660
Och jag kommer att lägga ner
vad det var, liksom 75,

1418
01:07:54,660 --> 01:07:56,920
och jag måste kedja detta
tillsammans nu på något sätt.

1419
01:07:56,920 --> 01:08:00,290
Fjärde frågesport kommer tillsammans, och kanske
det är mot slutet av terminen.

1420
01:08:00,290 --> 01:08:03,140
Och vid den tidpunkten mitt program
kanske använder minne

1421
01:08:03,140 --> 01:08:05,540
överallt, hela fysiskt.

1422
01:08:05,540 --> 01:08:08,170
Och så bara för sparkar, jag
kommer att dra denna fjärde

1423
01:08:08,170 --> 01:08:11,260
quiz-- jag har glömt vad det var; jag
tror kanske en 80 eller something--

1424
01:08:11,260 --> 01:08:12,500
vägen hit.

1425
01:08:12,500 --> 01:08:15,920
>> Men det är bra, eftersom bildmässigt
Jag kommer att dra denna linje.

1426
01:08:15,920 --> 01:08:19,063
Med andra ord, i verkligheten,
i datorns hårdvara,

1427
01:08:19,063 --> 01:08:20,979
den första poängen kanske
hamna här eftersom det är

1428
01:08:20,979 --> 01:08:22,529
precis i början av terminen.

1429
01:08:22,529 --> 01:08:25,810
Nästa man kan hamna här
eftersom lite tid har gått

1430
01:08:25,810 --> 01:08:27,210
och programmet fortsätter att gå.

1431
01:08:27,210 --> 01:08:30,060
Nästa poäng, vilket var
75, kan vara här.

1432
01:08:30,060 --> 01:08:33,420
Och den sista poängen kan vara
80, som är här.

1433
01:08:33,420 --> 01:08:38,729
>> Så i verkligheten, fysiskt, detta kan vara
vad datorns minne ser ut.

1434
01:08:38,729 --> 01:08:41,569
Men detta är inte en bra mental
paradigm för en programmerare.

1435
01:08:41,569 --> 01:08:44,649
Varför ska du bry dig där
heck dina data hamnar?

1436
01:08:44,649 --> 01:08:46,200
Du vill bara att lagra data.

1437
01:08:46,200 --> 01:08:49,390
>> Detta är ungefär som vår diskussion
tidigare att dra kuben.

1438
01:08:49,390 --> 01:08:52,200
Varför bryr du dig vad
vinkeln är av kuben

1439
01:08:52,200 --> 01:08:53,740
och hur man måste vända sig till dra det?

1440
01:08:53,740 --> 01:08:54,950
Du vill bara en kub.

1441
01:08:54,950 --> 01:08:57,359
På samma sätt här,
bara vill klass bok.

1442
01:08:57,359 --> 01:08:59,559
Du vill bara att tänka på
detta som en lista med tal.

1443
01:08:59,559 --> 01:09:01,350
Vem bryr sig om hur det är
implementeras i hårdvara?

1444
01:09:01,350 --> 01:09:05,180
>> Så abstraktion nu
är bilden här.

1445
01:09:05,180 --> 01:09:07,580
Detta är en länkad lista, som
en programmerare skulle kalla det,

1446
01:09:07,580 --> 01:09:10,640
mån du har en
listan, uppenbarligen av siffror.

1447
01:09:10,640 --> 01:09:14,990
Men det är kopplat bildmässigt
med hjälp av dessa pilar,

1448
01:09:14,990 --> 01:09:18,510
och alla dessa pilar är-- under
huven, om du är nyfiken,

1449
01:09:18,510 --> 01:09:23,210
påminna om att vår fysiska hårdvara har
adresser noll, ett, två, tre, fyra.

1450
01:09:23,210 --> 01:09:28,465
Alla dessa pilar är är som en karta
eller riktningar, där om 90 är-- nu

1451
01:09:28,465 --> 01:09:29,090
Jag fick räkna.

1452
01:09:29,090 --> 01:09:31,750
>> Noll, ett, två, tre,
fyra, fem, sex, sju.

1453
01:09:31,750 --> 01:09:35,640
Det ser ut som 90 är på
minnesadress nummer sju.

1454
01:09:35,640 --> 01:09:38,460
Alla dessa pilar är är
som en liten papperslapp

1455
01:09:38,460 --> 01:09:42,439
som är att ge anvisningar till
program som säger att följa denna karta

1456
01:09:42,439 --> 01:09:43,880
att få på plats sju.

1457
01:09:43,880 --> 01:09:46,680
Och det du hittar
elevens andra frågesport poäng.

1458
01:09:46,680 --> 01:09:52,100
Samtidigt 75-- om jag fortsätter här,
detta är sju, åtta, nio, tio, elva, tolv,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Denna andra pilen representerar bara
en karta minnesplats 15.

1461
01:09:59,080 --> 01:10:02,550
Men återigen, programmeraren gör i allmänhet
inte bryr sig om denna detaljnivå.

1462
01:10:02,550 --> 01:10:05,530
Och i de flesta varje programmering
språk i dag, programmeraren

1463
01:10:05,530 --> 01:10:10,490
kommer inte ens vet var i minnet
dessa siffror egentligen är.

1464
01:10:10,490 --> 01:10:14,830
Allt han eller hon måste ta hand om är
att de på något sätt sammanlänkade

1465
01:10:14,830 --> 01:10:18,390
i en datastruktur som denna.

1466
01:10:18,390 --> 01:10:21,580
>> Men det visar sig inte
att få alltför tekniskt.

1467
01:10:21,580 --> 01:10:27,430
Men bara för att vi kan kanske
råd att ha denna diskussion här,

1468
01:10:27,430 --> 01:10:33,630
Anta att vi återkomma
denna fråga här av en matris.

1469
01:10:33,630 --> 01:10:35,780
Låt oss se om vi beklagar kommer hit.

1470
01:10:35,780 --> 01:10:42,950
Detta är 100, 90, 75, och 80.

1471
01:10:42,950 --> 01:10:44,980
>> Låt mig kort göra detta påstående.

1472
01:10:44,980 --> 01:10:48,980
Detta är en array, och igen,
framträdande egenskap hos en matris

1473
01:10:48,980 --> 01:10:52,400
är att alla dina data är tillbaka till
rygg mot rygg i memory-- bokstavligen

1474
01:10:52,400 --> 01:10:56,830
en byte eller kanske fyra byte,
några fast antal bitgrupper bort.

1475
01:10:56,830 --> 01:11:00,710
I en länkad lista, som vi kan dra
så här, under huven som

1476
01:11:00,710 --> 01:11:02,000
vet var det där är?

1477
01:11:02,000 --> 01:11:03,630
Det behöver inte ens att flyta så här.

1478
01:11:03,630 --> 01:11:06,050
Vissa uppgifter kan vara
tillbaka till vänster uppe.

1479
01:11:06,050 --> 01:11:07,530
Du vet inte ens.

1480
01:11:07,530 --> 01:11:15,430
>> Och så med en array, har du
funktion som kallas Random Access.

1481
01:11:15,430 --> 01:11:20,570
Och vad random accessmedel är
att datorn kan hoppa direkt

1482
01:11:20,570 --> 01:11:22,730
till valfri plats i en matris.

1483
01:11:22,730 --> 01:11:23,580
Varför?

1484
01:11:23,580 --> 01:11:26,000
Eftersom datorn känner
att den första platsen är

1485
01:11:26,000 --> 01:11:29,540
noll, en, två och tre.

1486
01:11:29,540 --> 01:11:33,890
>> Och så om du vill gå från
detta element till nästa element,

1487
01:11:33,890 --> 01:11:36,099
du bokstavligen, i
datorns sinne, bara lägga en.

1488
01:11:36,099 --> 01:11:39,140
Om du vill gå till det tredje elementet,
bara lägga en-- nästa element, bara

1489
01:11:39,140 --> 01:11:40,290
lägga till en.

1490
01:11:40,290 --> 01:11:42,980
Men i denna version
av historien, antar

1491
01:11:42,980 --> 01:11:46,080
datorn bläddrar
på eller ta itu med nummer 100.

1492
01:11:46,080 --> 01:11:49,770
Hur får man till nästa
grad i betygsboken?

1493
01:11:49,770 --> 01:11:52,560
>> Du måste ta sju
steg, som är godtyckligt.

1494
01:11:52,560 --> 01:11:58,120
För att komma till nästa, måste du
ta ytterligare åtta steg för att komma till 15.

1495
01:11:58,120 --> 01:12:02,250
Med andra ord, det är inte en
konstant spalt mellan siffrorna,

1496
01:12:02,250 --> 01:12:04,857
och det bara tar
datorn mer tid är poängen.

1497
01:12:04,857 --> 01:12:06,940
Datorn måste söka
genom minne för

1498
01:12:06,940 --> 01:12:08,990
att hitta det du letar efter.

1499
01:12:08,990 --> 01:12:14,260
>> Så medan en matris tenderar att vara en
snabb data structure-- eftersom du

1500
01:12:14,260 --> 01:12:17,610
kan bokstavligen bara göra enkel aritmetik
och komma dit du vill genom att lägga till en,

1501
01:12:17,610 --> 01:12:21,300
för instance-- en länkad lista,
du offra den funktionen.

1502
01:12:21,300 --> 01:12:24,020
Du kan inte bara gå från första
till andra till tredje till fjärde.

1503
01:12:24,020 --> 01:12:25,240
Du måste följa kartan.

1504
01:12:25,240 --> 01:12:28,160
Du måste ta fler steg
för att komma till de värden som

1505
01:12:28,160 --> 01:12:30,230
verkar vara att lägga till en kostnad.

1506
01:12:30,230 --> 01:12:35,910
Så vi betalar ett pris, men vad var
funktionen att Dan sökte här?

1507
01:12:35,910 --> 01:12:38,110
Vad gör en länkad lista
tydligen tillåter oss att göra,

1508
01:12:38,110 --> 01:12:40,240
som var ursprunget till
denna berättelse?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Exakt.

1511
01:12:43,830 --> 01:12:46,220
En dynamisk storlek på den.

1512
01:12:46,220 --> 01:12:48,040
Vi kan lägga till denna lista.

1513
01:12:48,040 --> 01:12:51,430
Vi kan även krympa listan, så
att vi bara använder så mycket minne

1514
01:12:51,430 --> 01:12:55,560
som vi verkligen vill och så
Vi är aldrig över fördelning.

1515
01:12:55,560 --> 01:12:58,470
>> Nu är det bara att vara riktigt nit-picky,
Det finns en dold kostnad.

1516
01:12:58,470 --> 01:13:01,980
Så du bör inte bara låta mig övertyga
att detta är en övertygande kompromiss.

1517
01:13:01,980 --> 01:13:04,190
Det finns en annan dold kostnad här.

1518
01:13:04,190 --> 01:13:06,550
Fördelen att vara tydlig,
är att vi får dynamik.

1519
01:13:06,550 --> 01:13:10,359
Om jag vill ha en annan del, jag kan bara
dra den och placera ett antal där.

1520
01:13:10,359 --> 01:13:12,150
Och då kan jag länka den
med en bild här,

1521
01:13:12,150 --> 01:13:14,970
medan över här, igen, om jag har
målat mig i ett hörn,

1522
01:13:14,970 --> 01:13:19,410
om något annat redan använder
minnet här, jag är ute på tur.

1523
01:13:19,410 --> 01:13:21,700
Jag har målat mig in i hörnet.

1524
01:13:21,700 --> 01:13:24,390
>> Men vad är det dolda
kosta i den här bilden?

1525
01:13:24,390 --> 01:13:27,690
Det är inte bara mängden
av tiden som det tar

1526
01:13:27,690 --> 01:13:29,870
att gå härifrån till här,
vilket är sju steg, sedan

1527
01:13:29,870 --> 01:13:32,820
åtta steg, vilket är mer än en.

1528
01:13:32,820 --> 01:13:34,830
Vad är en annan dold kostnad?

1529
01:13:34,830 --> 01:13:35,440
Inte bara tid.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Ytterligare information
nödvändigt för att uppnå denna bild.

1532
01:13:49,940 --> 01:13:53,210
>> Ja, den kartan, dessa små rester av
papper, som jag håller beskriver dem som.

1533
01:13:53,210 --> 01:13:55,650
Dessa arrows-- de är inte gratis.

1534
01:13:55,650 --> 01:13:57,660
En computer-- du känner
vad en dator har.

1535
01:13:57,660 --> 01:13:58,790
Det har nollor och ettor.

1536
01:13:58,790 --> 01:14:03,170
Om du vill representera en pil eller en
karta eller ett nummer, du behöver lite minne.

1537
01:14:03,170 --> 01:14:05,950
Så den andra pris du
betala för en länkad lista,

1538
01:14:05,950 --> 01:14:09,070
en gemensam datavetenskap
resurs, är också utrymme.

1539
01:14:09,070 --> 01:14:11,710
>> Och faktiskt så, så vanligt,
bland de kompromisser

1540
01:14:11,710 --> 01:14:15,580
i utformningen av programvaruteknik
system är tid och space--

1541
01:14:15,580 --> 01:14:18,596
är två av dina ingredienser, två
av dina mest kostsamma ingredienser.

1542
01:14:18,596 --> 01:14:21,220
Detta kostar mig mer tid
eftersom jag måste följa den här kartan,

1543
01:14:21,220 --> 01:14:25,730
men det är också kostar mig mer utrymme
eftersom jag måste hålla denna karta runt.

1544
01:14:25,730 --> 01:14:28,730
Så hoppet, eftersom vi har typ av
diskuterade över igår och idag,

1545
01:14:28,730 --> 01:14:31,720
är att fördelarna
uppväger kostnaderna.

1546
01:14:31,720 --> 01:14:33,870
>> Men det finns ingen självklar lösning här.

1547
01:14:33,870 --> 01:14:35,870
Kanske är det better--
a la snabb och smutsig,

1548
01:14:35,870 --> 01:14:38,660
som Kareem föreslagna earlier--
att kasta minnet vid problemet.

1549
01:14:38,660 --> 01:14:42,520
Bara köpa mer minne, tror mindre
hårt om att lösa problemet,

1550
01:14:42,520 --> 01:14:44,595
och lösa det på ett enklare sätt.

1551
01:14:44,595 --> 01:14:46,720
Och faktiskt tidigare, när
Vi talade om kompromisser,

1552
01:14:46,720 --> 01:14:49,190
det var inte utrymme i
datorn och tid.

1553
01:14:49,190 --> 01:14:51,810
Det var utvecklare tid, vilket
är ännu en annan resurs.

1554
01:14:51,810 --> 01:14:54,829
>> Så återigen, det är detta balansakt
försöker bestämma vilken av dessa saker

1555
01:14:54,829 --> 01:14:55,870
är du villig att spendera?

1556
01:14:55,870 --> 01:14:57,380
Som är det billigaste?

1557
01:14:57,380 --> 01:15:01,040
Vilket ger bättre resultat?

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

1561
01:15:12,580 --> 01:15:15,970
I detta fall, om du är
representerar siffror i maps--

1562
01:15:15,970 --> 01:15:18,820
dessa kallas på många språk
"pekare" eller "adresser" -

1563
01:15:18,820 --> 01:15:20,390
Det är dubbelt så mycket utrymme.

1564
01:15:20,390 --> 01:15:24,390
Det behöver inte vara så illa som dubbel om
just nu vi bara lagra nummer.

1565
01:15:24,390 --> 01:15:27,410
Antag att vi lagrar
patientjournaler i en hospital--

1566
01:15:27,410 --> 01:15:30,870
så Pierson s namn, telefonnummer,
personnummer, läkare

1567
01:15:30,870 --> 01:15:31,540
historia.

1568
01:15:31,540 --> 01:15:34,160
Denna box kan vara mycket,
mycket större, i vilket fall

1569
01:15:34,160 --> 01:15:38,000
en liten liten pekare, adress
nästa element-- det är inte en stor sak.

1570
01:15:38,000 --> 01:15:40,620
Det är en sådan frans
kostar det spelar ingen roll.

1571
01:15:40,620 --> 01:15:43,210
Men i det här fallet, ja, det är en fördubbling.

1572
01:15:43,210 --> 01:15:45,290
Bra fråga.

1573
01:15:45,290 --> 01:15:47,900
>> Låt oss tala om gång en
lite mer konkret.

1574
01:15:47,900 --> 01:15:50,380
Vad är gångtid
att söka den här listan?

1575
01:15:50,380 --> 01:15:53,640
Anta att jag ville söka
genom alla elevernas betyg,

1576
01:15:53,640 --> 01:15:55,980
och det finns n kvaliteter
i denna datastruktur.

1577
01:15:55,980 --> 01:15:58,830
Även här kan vi låna
vokabulär tidigare.

1578
01:15:58,830 --> 01:16:00,890
Detta är en linjär datastruktur.

1579
01:16:00,890 --> 01:16:04,570
>> Big O n är vad som krävs för att få
till slutet av denna datastruktur,

1580
01:16:04,570 --> 01:16:08,410
whereas-- och vi har inte sett
detta before-- en array ger dig

1581
01:16:08,410 --> 01:16:13,555
vad som kallas konstant tid, vilket innebär att
ett steg eller två steg eller 10 steps--

1582
01:16:13,555 --> 01:16:14,180
spelar ingen roll.

1583
01:16:14,180 --> 01:16:15,440
Det är ett fast antal.

1584
01:16:15,440 --> 01:16:17,440
Det har ingenting att göra med
storleken på arrayen.

1585
01:16:17,440 --> 01:16:20,130
Och anledningen till att
igen, är slumpmässig åtkomst.

1586
01:16:20,130 --> 01:16:23,180
Datorn kan bara omedelbart
hoppa till en annan plats,

1587
01:16:23,180 --> 01:16:27,770
eftersom de är alla samma
avstånd från allt annat.

1588
01:16:27,770 --> 01:16:29,112
Det finns ingen tänkande inblandade.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Okej.

1591
01:16:32,400 --> 01:16:39,230
Så om jag kan, låt mig försöka
måla två slutliga bilder.

1592
01:16:39,230 --> 01:16:42,830
En mycket vanlig en känd som en hashtabell.

1593
01:16:42,830 --> 01:16:51,120
Så för att motivera denna diskussion,
Låt mig tänka på hur man gör detta.

1594
01:16:51,120 --> 01:16:52,610
>> Så vad sägs om detta?

1595
01:16:52,610 --> 01:16:55,160
Antag att problemet
Vi vill lösa nu

1596
01:16:55,160 --> 01:16:58,360
genomför i en dictionary--
så en hel del engelska ord

1597
01:16:58,360 --> 01:16:59,330
eller vad som helst.

1598
01:16:59,330 --> 01:17:02,724
Och målet är att kunna svara
frågor av formen är detta ett ord?

1599
01:17:02,724 --> 01:17:04,640
Så du vill genomföra
en stavningskontroll, bara

1600
01:17:04,640 --> 01:17:07,220
som en fysisk lexikon
att du kan slå upp saker i.

1601
01:17:07,220 --> 01:17:10,490
Anta att jag skulle göra detta med en matris.

1602
01:17:10,490 --> 01:17:12,590
Jag kunde göra detta.

1603
01:17:12,590 --> 01:17:20,756
>> Och antar att orden är äpple
och banan och cantaloupemelon.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Och jag kan inte tänka på frukt
som börjar med d, så vi är bara

1606
01:17:26,465 --> 01:17:27,590
kommer att ha tre frukter.

1607
01:17:27,590 --> 01:17:31,510
Så detta är en array, och vi är
lagra alla dessa ord

1608
01:17:31,510 --> 01:17:34,200
i denna ordbok som en array.

1609
01:17:34,200 --> 01:17:39,350
Frågan är då hur annars
kan du spara den här informationen?

1610
01:17:39,350 --> 01:17:43,160
>> Tja, jag typ av fusk här, eftersom
var och en av dessa bokstäver i ord

1611
01:17:43,160 --> 01:17:44,490
är verkligen en enskild bitgrupp.

1612
01:17:44,490 --> 01:17:46,740
Så om jag ville verkligen vara
nit-picky, jag borde verkligen

1613
01:17:46,740 --> 01:17:49,600
att dela upp detta i mycket
mindre bitar av minne,

1614
01:17:49,600 --> 01:17:51,289
och vi kunde göra just detta.

1615
01:17:51,289 --> 01:17:53,580
Men vi kommer att stöta på
samma problem som tidigare.

1616
01:17:53,580 --> 01:17:56,674
Tänk om, som Merriam Webster eller Oxford
gör varje year-- de lägga till ord

1617
01:17:56,674 --> 01:17:59,340
till dictionary-- vi inte
nödvändigtvis vill måla oss

1618
01:17:59,340 --> 01:18:00,780
i ett hörn med en array?

1619
01:18:00,780 --> 01:18:05,710
>> Så i stället, kanske en smartare strategi
är att sätta Apple i sin egen nod eller låda,

1620
01:18:05,710 --> 01:18:11,190
som vi skulle säga, banan, och
så här har vi cantaloupemelon.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Och vi sträng dessa saker tillsammans.

1623
01:18:16,790 --> 01:18:19,980
Så detta är arrayen, och
detta är den länkade listan.

1624
01:18:19,980 --> 01:18:23,300
Om du inte riktigt kan se, det bara
säger "array", och detta säger "lista."

1625
01:18:23,300 --> 01:18:25,780
>> Så vi har samma
exakta frågor som tidigare,

1626
01:18:25,780 --> 01:18:28,600
där vi nu har
dynamik i vårt länkad lista.

1627
01:18:28,600 --> 01:18:31,090
Men vi har en ganska långsam ordboken.

1628
01:18:31,090 --> 01:18:32,870
Anta att jag vill slå upp ett ord.

1629
01:18:32,870 --> 01:18:35,430
Det kan ta mig stora O n
steg, eftersom ordet kanske

1630
01:18:35,430 --> 01:18:37,840
vara hela vägen vid slutet av
listan, som cantaloupmelon.

1631
01:18:37,840 --> 01:18:40,600
Och det visar sig att
i programmering, sortera

1632
01:18:40,600 --> 01:18:42,700
av den heliga graal av data
strukturer, är något

1633
01:18:42,700 --> 01:18:46,620
som ger dig konstant
tid som en matris

1634
01:18:46,620 --> 01:18:50,870
men som fortfarande ger dig dynamik.

1635
01:18:50,870 --> 01:18:52,940
>> Så kan vi ha det bästa av två världar?

1636
01:18:52,940 --> 01:18:55,570
Och faktiskt, det finns något
kallad hash-tabellen

1637
01:18:55,570 --> 01:18:59,320
som tillåter dig att göra exakt
att, om än ungefär.

1638
01:18:59,320 --> 01:19:03,140
En hash-tabell är en snyggare
datastruktur som vi

1639
01:19:03,140 --> 01:19:06,340
kan tänka på som
kombination av en array--

1640
01:19:06,340 --> 01:19:12,390
och jag kommer att dra det
som this-- och länkade listor

1641
01:19:12,390 --> 01:19:17,310
att jag ska göra så här hit.

1642
01:19:17,310 --> 01:19:19,760
>> Och hur denna sak
verk är som följer.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Om detta now-- hash table--
är min tredje datastruktur,

1645
01:19:29,540 --> 01:19:32,590
och jag vill spara
ord i detta, det gör jag inte

1646
01:19:32,590 --> 01:19:35,440
vill bara lagra alla av
ord rygg mot rygg mot rygg mot rygg.

1647
01:19:35,440 --> 01:19:37,430
Jag vill utnyttja vissa
bit information

1648
01:19:37,430 --> 01:19:40,330
om de ord som låter
mig att få den där den är snabbare.

1649
01:19:40,330 --> 01:19:43,666
>> Så med tanke på orden apple
och banan och cantaloupemelon,

1650
01:19:43,666 --> 01:19:45,040
Jag medvetet valde dessa ord.

1651
01:19:45,040 --> 01:19:45,340
Varför?

1652
01:19:45,340 --> 01:19:47,631
Vad blir liksom grunden
annorlunda om tre?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Vad är det uppenbara?

1655
01:19:51,484 --> 01:19:52,900
De börjar med olika bokstäver.

1656
01:19:52,900 --> 01:19:53,900
>> Så du vet vad?

1657
01:19:53,900 --> 01:19:57,120
I stället för att lägga alla mina ord i
samma hink, så att säga,

1658
01:19:57,120 --> 01:20:00,390
som i en stor lista, varför inte
Jag åtminstone prova en optimering

1659
01:20:00,390 --> 01:20:04,180
och göra mina listor 1/26 så länge.

1660
01:20:04,180 --> 01:20:07,440
En övertygande optimering
kanske varför inte

1661
01:20:07,440 --> 01:20:10,650
Jag-- när du sätter ett ord
in i denna datastruktur,

1662
01:20:10,650 --> 01:20:14,300
i datorns minne, varför
jag inte lägga alla punkt a ord här,

1663
01:20:14,300 --> 01:20:17,270
alla "B" ord här,
och alla C-ord här?

1664
01:20:17,270 --> 01:20:24,610
Så här slutar att sätta ett äpple
här, banan här, cantaloupmelon här,

1665
01:20:24,610 --> 01:20:25,730
och så vidare.

1666
01:20:25,730 --> 01:20:31,700
>> Och om jag har en extra
Ordet like-- vad är en annan?

1667
01:20:31,700 --> 01:20:36,640
Äpple, banan, päron.

1668
01:20:36,640 --> 01:20:39,370
Någon tänker på en frukt
som börjar 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 att hamna här.

1671
01:20:43,990 --> 01:20:47,530
Och så verkar vi ha en
marginellt bättre lösning,

1672
01:20:47,530 --> 01:20:50,820
för nu om jag vill
för att söka efter äpple, jag

1673
01:20:50,820 --> 01:20:53,200
first-- jag inte bara dyka
i min datastruktur.

1674
01:20:53,200 --> 01:20:54,850
Jag dyka inte i datorns minne.

1675
01:20:54,850 --> 01:20:56,530
Jag ser först på den första bokstaven.

1676
01:20:56,530 --> 01:20:58,610
>> Och detta är vad en dator
vetenskapsman skulle säga.

1677
01:20:58,610 --> 01:21:00,760
Du hash i din datastruktur.

1678
01:21:00,760 --> 01:21:04,100
Du tar din ingång, vilket i
detta fall är ett ord som äpple.

1679
01:21:04,100 --> 01:21:07,150
Du analyserar det, titta på
den första bokstaven i det här fallet,

1680
01:21:07,150 --> 01:21:08,340
därigenom hashing det.

1681
01:21:08,340 --> 01:21:10,950
Hashning är en allmän term som innebär
du ta något som indata

1682
01:21:10,950 --> 01:21:12,116
och du producerar några utgång.

1683
01:21:12,116 --> 01:21:15,090
Och utgången i det
fall är platsen

1684
01:21:15,090 --> 01:21:18,150
du vill söka, den första
plats, andra plats, tredje.

1685
01:21:18,150 --> 01:21:22,160
Så ingången är äpple,
utgången är först.

1686
01:21:22,160 --> 01:21:25,054
Ingången är banan, den
utgång ska vara sekund.

1687
01:21:25,054 --> 01:21:27,220
Ingången är cantaloupemelon,
utgången bör vara tredje.

1688
01:21:27,220 --> 01:21:30,320
Ingången är blåbär, den
utgång bör återigen vara sekund.

1689
01:21:30,320 --> 01:21:34,010
Och det är vad hjälper dig att ta
genvägar genom ditt minne

1690
01:21:34,010 --> 01:21:39,050
För att komma till ord
eller data mer effektivt.

1691
01:21:39,050 --> 01:21:43,330
>> Nu minskar vår tid potentiellt
med så mycket som en av 26,

1692
01:21:43,330 --> 01:21:45,850
eftersom om man antar att du
ha så många "a" ord som "z"

1693
01:21:45,850 --> 01:21:48,080
ord som "q" ord, som
är egentligen inte realistic--

1694
01:21:48,080 --> 01:21:50,830
du kommer att ha skev över
vissa bokstäver i alphabet--

1695
01:21:50,830 --> 01:21:53,204
men detta skulle vara en inkrementell
tillvägagångssätt som inte tillåter

1696
01:21:53,204 --> 01:21:55,930
du att få ord mycket snabbare.

1697
01:21:55,930 --> 01:21:59,660
Och i verkligheten, en sofistikerad
program, googles av världen,

1698
01:21:59,660 --> 01:22:02,180
den Facebooks av world--
de skulle använda en hash-tabell

1699
01:22:02,180 --> 01:22:03,740
för många olika ändamål.

1700
01:22:03,740 --> 01:22:06,590
Men de skulle inte vara så naiva
att bara titta på den första bokstaven

1701
01:22:06,590 --> 01:22:09,700
i äpple eller banan eller
päron eller cantaloupemelon,

1702
01:22:09,700 --> 01:22:13,420
eftersom du kan se dessa
listor kan fortfarande få långa.

1703
01:22:13,420 --> 01:22:17,130
>> Och så detta kan fortfarande vara sort
av linear-- så sorts långsam,

1704
01:22:17,130 --> 01:22:19,980
liksom med den stora O i n
som vi diskuterade tidigare.

1705
01:22:19,980 --> 01:22:25,290
Så vad en riktigt bra hash tabellen
do-- det kommer att ha en mycket större matris.

1706
01:22:25,290 --> 01:22:28,574
Och det kommer att använda en mycket mer
sofistikerad hashningsfunktion,

1707
01:22:28,574 --> 01:22:30,240
så att det inte bara titta på "a."

1708
01:22:30,240 --> 01:22:35,480
Kanske tittar på "a-p-p-l-e" och
på något sätt omvandlar dessa fem bokstäver

1709
01:22:35,480 --> 01:22:38,400
in den plats där
Apple ska lagras.

1710
01:22:38,400 --> 01:22:42,660
Vi är bara naivt att använda bokstaven "a"
ensam, eftersom det är trevlig och enkel.

1711
01:22:42,660 --> 01:22:44,600
>> Men en hashtabell, i
Till slut kan du tror

1712
01:22:44,600 --> 01:22:47,270
av som en kombination av
en array, som var och en

1713
01:22:47,270 --> 01:22:51,700
har en länkad lista som är idealiskt
bör vara så kort som möjligt.

1714
01:22:51,700 --> 01:22:54,364
Och detta är inte en självklar lösning.

1715
01:22:54,364 --> 01:22:57,280
I själva verket är mycket av den finjustering
som pågår under huven när

1716
01:22:57,280 --> 01:22:59,654
genomförandet av dessa typer av
avancerade datastrukturer

1717
01:22:59,654 --> 01:23:01,640
är vad som är rätt
längden på arrayen?

1718
01:23:01,640 --> 01:23:03,250
Vad är rätt hashfunktionen?

1719
01:23:03,250 --> 01:23:04,830
How do you lagra saker i minnet?

1720
01:23:04,830 --> 01:23:07,249
>> Men inser hur snabbt
denna typ av diskussion

1721
01:23:07,249 --> 01:23:10,540
eskalerade, antingen så långt att det är typ
av över huvudet på denna punkt, vilket

1722
01:23:10,540 --> 01:23:11,360
är bra.

1723
01:23:11,360 --> 01:23:18,820
Men vi började, minns, med verkligt
något låg nivå och elektronisk.

1724
01:23:18,820 --> 01:23:20,819
Och så detta är igen
tema av abstraktion,

1725
01:23:20,819 --> 01:23:23,610
där när du börjar ta för
beviljas, OK, jag har det-- det finns

1726
01:23:23,610 --> 01:23:26,680
fysiskt minne, OK, fick det, varje
fysisk plats har en adress,

1727
01:23:26,680 --> 01:23:29,910
OK, jag fick det, kan jag företräder
dessa adresser som arrows--

1728
01:23:29,910 --> 01:23:34,650
du kan mycket snabbt börjar få
mer sofistikerade samtal som

1729
01:23:34,650 --> 01:23:38,360
i slutändan verkar vara att låta oss
att lösa problem som söker

1730
01:23:38,360 --> 01:23:41,620
och sortering mer effektivt.

1731
01:23:41,620 --> 01:23:44,190
Och vara säker på, too--
eftersom jag tror att detta

1732
01:23:44,190 --> 01:23:48,700
är den djupaste vi har gått in i något
Dessa CS ämnen proper-- vi ve

1733
01:23:48,700 --> 01:23:51,880
gjort i en och en halv dag på detta
pekar vad du kanske normalt göra över

1734
01:23:51,880 --> 01:23:55,520
Under åtta veckor i en termin.

1735
01:23:55,520 --> 01:23:59,670
>> Eventuella frågor om dessa?

1736
01:23:59,670 --> 01:24:01,100
Nej?

1737
01:24:01,100 --> 01:24:01,940
Okej.

1738
01:24:01,940 --> 01:24:05,610
Tja, varför inte vi stannar där,
starta lunch några minuter tidigare,

1739
01:24:05,610 --> 01:24:07,052
återupptas i nästan en timme?

1740
01:24:07,052 --> 01:24:08,760
Och jag ska dröja
lite med frågor.

1741
01:24:08,760 --> 01:24:11,343
Då kommer jag att behöva gå
ta ett par samtal om det är OK.

1742
01:24:11,343 --> 01:24:15,000
Jag ska sätta på lite musik under tiden,
men lunch bör vara runt hörnet.

1743
01:24:15,000 --> 01:24:17,862