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

2
00:00:00,030 --> 00:00:00,460
>> DAVID Malan: Allt í lagi.

3
00:00:00,460 --> 00:00:01,094
Við erum aftur.

4
00:00:01,094 --> 00:00:04,260
Svo í þessum flokki á forritun hvað
Ég hélt að við myndum gera er að blanda af hlutum.

5
00:00:04,260 --> 00:00:06,340
Einn, gera smá
eitthvað snertið ekki-á,

6
00:00:06,340 --> 00:00:08,690
að vísu með meira fjörugur
forritun environment--

7
00:00:08,690 --> 00:00:11,620
einn sem er sýnileg á
nákvæmlega konar hugmyndir

8
00:00:11,620 --> 00:00:14,220
við höfum verið að tala um,
en lítið meira formlega.

9
00:00:14,220 --> 00:00:18,200
Tveir, líta á sumir af
meira tæknilega leiðir

10
00:00:18,200 --> 00:00:21,520
að forritari myndi reyndar leysa
vandamál eins og að leita vandans

11
00:00:21,520 --> 00:00:24,530
að við skoðuðum áður og
einnig meira grundvallaratriðum

12
00:00:24,530 --> 00:00:26,020
áhugavert vandamál að flokka.

13
00:00:26,020 --> 00:00:28,840
>> Við ráð bara frá the fá að fara
að það símaskrá var raðað,

14
00:00:28,840 --> 00:00:31,980
en það eitt er í raun eins konar
erfitt vandamál með mörgum mismunandi vegu

15
00:00:31,980 --> 00:00:32,479
til að leysa það.

16
00:00:32,479 --> 00:00:34,366
Þannig að við munum nota þessar sem
flokkur vandamálum

17
00:00:34,366 --> 00:00:36,740
fulltrúi hlutum sem
gæti verið leyst almennt.

18
00:00:36,740 --> 00:00:38,980
Og þá munum við tala
um í sumum smáatriðum hvað

19
00:00:38,980 --> 00:00:42,360
eru kallaðir gögn structures--
áhugamaður leiðir eins tengd listum

20
00:00:42,360 --> 00:00:46,290
og kjötkássa matskeið og tré sem
forritari væri í raun

21
00:00:46,290 --> 00:00:48,890
notkun og almennt nota
á whiteboard að mála

22
00:00:48,890 --> 00:00:51,840
mynd af því sem hann eða hún
ímynda fyrir framkvæmd

23
00:00:51,840 --> 00:00:52,980
sumir stykki af hugbúnaður.

24
00:00:52,980 --> 00:00:55,130
>> Svo skulum gera snertið ekki-á hluta fyrst.

25
00:00:55,130 --> 00:01:00,090
Svo bara fá þinn snertið ekki óhrein með að
umhverfi kallast scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Þetta er tæki sem við notum
í grunnnámi bekknum okkar.

27
00:01:02,636 --> 00:01:04,510
Jafnvel þó að það er hannað
fyrir 12 ára og upp,

28
00:01:04,510 --> 00:01:07,570
við notum það fyrir þig
hluti af þeim töluvert

29
00:01:07,570 --> 00:01:10,020
þar sem það er gott, gaman
Grafísku leið til að læra

30
00:01:10,020 --> 00:01:12,160
lítið eitthvað um forritun.

31
00:01:12,160 --> 00:01:17,600
Svo höfuð til þessa vefslóð, þar sem þú
ætti að sjá síðu alveg eins og þetta,

32
00:01:17,600 --> 00:01:23,330
og fara á undan og smelltu
Join Scratch efst til hægri

33
00:01:23,330 --> 00:01:28,300
og velja notandanafn og
lykilorð og að lokum fá þig

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

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

36
00:01:32,165 --> 00:01:34,665
Ég hélt ég myndi nota þetta sem
tækifæri fyrst að sýna þetta.

37
00:01:34,665 --> 00:01:39,120
Spurning kom upp á í hálfleik
um hvað númer raunverulega lítur út.

38
00:01:39,120 --> 00:01:41,315
Og við vorum að tala
á í hálfleik um C,

39
00:01:41,315 --> 00:01:45,060
í particular-- sérstaklega a
lægri í eldri tungumáli.

40
00:01:45,060 --> 00:01:47,750
Og ég gerði bara fljótur
Google leit til að finna C kóða

41
00:01:47,750 --> 00:01:51,574
fyrir tvöfaldur leit, reiknirit sem við
notuð til að leita að símaskránni fyrr.

42
00:01:51,574 --> 00:01:54,240
Þetta tiltekna dæmi, að sjálfsögðu,
ekki leita símaskrá.

43
00:01:54,240 --> 00:01:57,840
Það leitar bara a heild búnt af
Tölurnar í minni tölvu.

44
00:01:57,840 --> 00:02:01,000
En ef þú vilt bara fá sjón
tilfinningu fyrir því hvað raunveruleg forritun

45
00:02:01,000 --> 00:02:05,370
Tungumál lítur út eins og, það lítur
a lítill eitthvað eins og þetta.

46
00:02:05,370 --> 00:02:09,759
Svo það er um 20-plús,
30 eða svo línur af kóða,

47
00:02:09,759 --> 00:02:12,640
en samtal við
voru með yfir hlé

48
00:02:12,640 --> 00:02:16,000
var um hvernig þetta í raun og veru
fær morphed í núllum og sjálfur

49
00:02:16,000 --> 00:02:19,200
og ef þú getur ekki bara snúa að
vinna og fara frá núll og sjálfur

50
00:02:19,200 --> 00:02:20,210
baka til að kóða.

51
00:02:20,210 --> 00:02:22,620
>> Því miður, the aðferð
er svo transformative

52
00:02:22,620 --> 00:02:24,890
að það er mun auðveldara sagt en gert.

53
00:02:24,890 --> 00:02:29,400
Ég fór á undan og í raun snúið
það program, Binary Search,

54
00:02:29,400 --> 00:02:32,700
í núll og sjálfur með því að
forrit sem heitir The þýðanda sem ég

55
00:02:32,700 --> 00:02:34,400
átt hér rétt á Mac minn.

56
00:02:34,400 --> 00:02:37,850
Og ef þú horfir á skjáinn
hér, með áherslu sérstaklega

57
00:02:37,850 --> 00:02:43,520
á þessum miðja sex dálka aðeins,
þú munt sjá aðeins núll og sjálfur.

58
00:02:43,520 --> 00:02:48,290
Og þeir eru núll og sjálfur að
semja einmitt að leit program.

59
00:02:48,290 --> 00:02:53,720
>> Og svo hver klumpur af fimm bitum,
hver bæti núllum og sjálfur hér,

60
00:02:53,720 --> 00:02:57,310
tákna sumir kennsla
yfirleitt inni í tölvunni.

61
00:02:57,310 --> 00:03:00,730
Og í raun, ef þú hefur heyrt
markaðssetning slagorð "Intel inni" - sem,

62
00:03:00,730 --> 00:03:04,610
auðvitað, þýðir að þú ert með
Intel CPU eða heila inni í tölvunni.

63
00:03:04,610 --> 00:03:08,000
Og hvað það þýðir að vera CPU er
að þú sért með kennsla setja,

64
00:03:08,000 --> 00:03:08,840
svo að segja.

65
00:03:08,840 --> 00:03:11,620
>> Sérhver CPU í heiminum, margir af
þá gerð af Intel þessa dagana,

66
00:03:11,620 --> 00:03:13,690
skilur endanlegt
Fjöldi leiðbeiningar.

67
00:03:13,690 --> 00:03:18,690
Og þessir leiðbeiningar eru svo lágt
sem bæta þessa tvo tölur saman,

68
00:03:18,690 --> 00:03:22,560
margfalda þessar tvær tölur saman,
færa þetta stykki af gögn héðan

69
00:03:22,560 --> 00:03:27,340
að hér í minni, spara þetta
Upplýsingar frá hér að hér í minni,

70
00:03:27,340 --> 00:03:32,200
og svo forth-- svo mjög, mjög
lágmark-láréttur flötur, nánast rafræn upplýsingar.

71
00:03:32,200 --> 00:03:34,780
En með þeim stærðfræði
rekstur par

72
00:03:34,780 --> 00:03:37,410
við það sem við ræddum áðan,
framsetning gagna

73
00:03:37,410 --> 00:03:40,450
eins núllum og sjálfur, getur
þú byggja upp allt

74
00:03:40,450 --> 00:03:44,180
sem tölvan getur gert í dag, hvort sem
það er texta, myndræna, tónlistar,

75
00:03:44,180 --> 00:03:45,580
eða á annan hátt.

76
00:03:45,580 --> 00:03:49,450
>> Svo er þetta mjög auðvelt að fá
glataður í illgresið á fljótt.

77
00:03:49,450 --> 00:03:52,150
Og það er mikið af
syntactical áskoranir

78
00:03:52,150 --> 00:03:56,630
þar ef þú gerir einfaldasta,
heimskasta af innsláttarvillur ekkert áætlunarinnar

79
00:03:56,630 --> 00:03:57,860
mun vinna af neinu tagi.

80
00:03:57,860 --> 00:04:00,366
Og svo í stað þess að nota a
Tungumál eins og C í morgun,

81
00:04:00,366 --> 00:04:02,240
Ég hélt að það væri
meira gaman að raunverulega gera

82
00:04:02,240 --> 00:04:04,840
eitthvað meira sjón, sem
en hannað fyrir krakka

83
00:04:04,840 --> 00:04:08,079
er í raun fullkomið birtingarmynd
af raunverulegum forritun

84
00:04:08,079 --> 00:04:10,370
Language-- bara gerist
nota myndir í stað texta

85
00:04:10,370 --> 00:04:11,710
til að tákna þær hugmyndir.

86
00:04:11,710 --> 00:04:15,470
>> Svo þegar þú ert örugglega
reikningur á scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
smelltu á Búa til hnapp
efst til vinstri af the staður.

88
00:04:21,070 --> 00:04:24,620
Og þú ættir að sjá umhverfi eins
sá sem ég er að fara að sjá á skjánum mínum

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

90
00:04:26,310 --> 00:04:29,350
Og við munum eyða bara smá
smá tíma í að spila hér.

91
00:04:29,350 --> 00:04:34,080
Við skulum sjá hvort við getum ekki öll leyst sum
vandamál saman á eftirfarandi hátt.

92
00:04:34,080 --> 00:04:39,420
>> Svo það sem þú munt sjá í þessari
environment-- og í raun bara láta

93
00:04:39,420 --> 00:04:40,050
mér hlé.

94
00:04:40,050 --> 00:04:42,680
Er einhver ekki hér?

95
00:04:42,680 --> 00:04:45,070
Ekki hér?

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

97
00:04:45,800 --> 00:04:49,030
Svo láta mig benda á nokkrar
einkenni þessarar umhverfi.

98
00:04:49,030 --> 00:04:55,024
>> Svo á efst til vinstri á skjánum, við
hafa stigi Scratch er, svo að segja.

99
00:04:55,024 --> 00:04:57,440
Scratch er ekki aðeins nafn
þessarar forritunarmál;

100
00:04:57,440 --> 00:05:00,356
það er einnig nafn á kött sem
þú sérð sjálfgefið þar í appelsína.

101
00:05:00,356 --> 00:05:02,160
Hann er á sviðinu, svo
mikið eins og ég lýsti

102
00:05:02,160 --> 00:05:05,770
skjaldbaka fyrr eins og að vera í
rétthyrnd hvítt borð umhverfi.

103
00:05:05,770 --> 00:05:09,800
Heimurinn Þessi köttur er bundin alveg
að því rétthyrningur upp efst þar.

104
00:05:09,800 --> 00:05:12,210
>> Á sama tíma, á hægri
hönd hlið hér, það er

105
00:05:12,210 --> 00:05:15,610
bara forskriftir svæði,
autt ef þú vilt.

106
00:05:15,610 --> 00:05:18,590
Þetta er þar sem við erum að fara að skrifa
áætlanir okkar í bara smá stund.

107
00:05:18,590 --> 00:05:22,935
Og byggingareiningar sem við munum
nota til að skrifa þetta program-- þraut

108
00:05:22,935 --> 00:05:25,310
stykki, ef þú ert will--
þá hérna í miðjunni,

109
00:05:25,310 --> 00:05:27,500
og þeir eru flokkaðir
með virkni.

110
00:05:27,500 --> 00:05:31,000
Svo, til dæmis, ég ætla að fara á undan
og sýna fram á að minnsta kosti einn af þessum.

111
00:05:31,000 --> 00:05:33,690
Ég ætla að fara á undan og smelltu
eftirlitsnefnd flokki upp efst.

112
00:05:33,690 --> 00:05:35,720
>> Svo þetta eru flokkar upp efst.

113
00:05:35,720 --> 00:05:39,410
Ég ætla að smella Control flokk.

114
00:05:39,410 --> 00:05:44,020
Frekar, ég ætla að smella á atburðum
flokkur, the mjög fyrstur einn upp topp.

115
00:05:44,020 --> 00:05:47,790
Og ef þú vilt að fylgja eftir jafnvel
eins og við gerum þetta, þú ert alveg velkomið að.

116
00:05:47,790 --> 00:05:52,180
Ég ætla að smella og draga þetta
fyrsta, "þegar grænn fáni smellt."

117
00:05:52,180 --> 00:05:58,410
Og þá ætla ég að sleppa því bara
u.þ.b. efst á auða Spjöld mínum.

118
00:05:58,410 --> 00:06:01,450
>> Og hvað er gott um grunni
er að þessi þraut stykki, þegar

119
00:06:01,450 --> 00:06:04,560
kveikja á öðrum þraut
stykki, er að fara að gera bókstaflega

120
00:06:04,560 --> 00:06:06,460
hvað þessir púsluspil stykki segja að gera.

121
00:06:06,460 --> 00:06:09,710
Svo, til dæmis, Scratch er rétt
nú í miðri heiminum.

122
00:06:09,710 --> 00:06:14,660
Ég ætla að fara á undan og velja
nú, við skulum segja, Motion flokki,

123
00:06:14,660 --> 00:06:18,000
ef þú vilt gera
same-- Motion flokk.

124
00:06:18,000 --> 00:06:20,430
Og nú eftir að ég hafa a heild
fullt af stykki púsluspil hér

125
00:06:20,430 --> 00:06:23,370
sem, aftur, eins konar að gera það sem þeir segja.

126
00:06:23,370 --> 00:06:28,110
Og ég ætla að fara á undan og draga og
falla færa blokk hérna.

127
00:06:28,110 --> 00:06:31,860
>> Og eftir að um leið og þú færð
nálægt the botn af the "græna fána

128
00:06:31,860 --> 00:06:34,580
smellti "hnappinn, tilkynning
hvernig hvítt lína birtist,

129
00:06:34,580 --> 00:06:36,950
eins og það er nánast
segulmagnaðir, vill það til að fara þangað.

130
00:06:36,950 --> 00:06:43,070
Bara láta fara, og það mun smella
saman og form mun passa.

131
00:06:43,070 --> 00:06:46,620
Og nú þú getur kannski næstum
giska á hvar við erum að fara með þetta.

132
00:06:46,620 --> 00:06:51,570
>> Ef þú líta á grunni sviðinu
hérna og líta til the toppur af það,

133
00:06:51,570 --> 00:06:55,142
þú munt sjá rautt ljós, a
stöðva merki og græna fána.

134
00:06:55,142 --> 00:06:57,100
Og ég ætla að fara á undan
og horfa screen-- mín

135
00:06:57,100 --> 00:06:58,460
fyrir réttlátur a augnablik, ef þú gætir.

136
00:06:58,460 --> 00:07:01,960
Ég ætla að smella á
Grænfánann núna,

137
00:07:01,960 --> 00:07:07,850
og hann flutti það virðist vera 10 skref
eða 10 punktar, 10 punktar, á skjánum.

138
00:07:07,850 --> 00:07:13,390
>> Og svo ekki spennandi,
en láta mig leggja

139
00:07:13,390 --> 00:07:17,440
án þess þó að kenna þetta, bara
nota eigin eigin intuition-- Let

140
00:07:17,440 --> 00:07:22,560
mér að leggja til að þú reikna út hvernig á að
gera Scratch ganga strax sviðinu.

141
00:07:22,560 --> 00:07:28,700
Hafa hann að gera brautina fyrir hægri hlið
skjár, alla leið til hægri.

142
00:07:28,700 --> 00:07:32,200
Leyfðu mér að gefa þér augnablik
eða svo að glíma við það.

143
00:07:32,200 --> 00:07:37,681
Þú vilt kannski að kíkja
á aðra flokka blokkum.

144
00:07:37,681 --> 00:07:38,180
Allt í lagi.

145
00:07:38,180 --> 00:07:41,290
Svo bara að ágrip, þegar við höfum
grænn fáni smellt hér

146
00:07:41,290 --> 00:07:44,850
og færa 10 skref er
Aðeins kennsla, í hvert sinn sem ég

147
00:07:44,850 --> 00:07:46,720
smelltu á græna fána, hvað er að gerast?

148
00:07:46,720 --> 00:07:50,070
Jæja, það er í gangi forritið mitt.

149
00:07:50,070 --> 00:07:52,450
Svo ég gæti gert þetta
kannski 10 sinnum handvirkt,

150
00:07:52,450 --> 00:07:55,130
en þetta líður svolítið
bita hackish, svo að segja,

151
00:07:55,130 --> 00:07:57,480
þar sem ég er í raun ekki
að leysa vandann.

152
00:07:57,480 --> 00:08:00,530
Ég er bara að reyna aftur og
aftur og aftur og aftur

153
00:08:00,530 --> 00:08:03,180
þangað til ég svona óvart
ná tilskipunina

154
00:08:03,180 --> 00:08:05,560
að ég ákvað að ná fyrr.

155
00:08:05,560 --> 00:08:08,200
>> En við vitum af okkar
sauðakóðanum fyrr að það er

156
00:08:08,200 --> 00:08:11,870
Þessi hugmynd í forritun lykkja,
gera eitthvað aftur og aftur.

157
00:08:11,870 --> 00:08:14,888
Og svo sá ég að fullt af þér
náð fyrir hvað ráðgáta stykki?

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

159
00:08:17,870 --> 00:08:18,730
Endurtakið þar.

160
00:08:18,730 --> 00:08:21,400
Þannig að við gætum gert eitthvað
eins endurtaka þangað.

161
00:08:21,400 --> 00:08:23,760
Og hvað gerðir þú endurtaka þar nákvæmlega?

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

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

164
00:08:28,540 --> 00:08:31,974
Og láta mig fara með einn sem er
nokkuð einfaldara fyrir réttlátur a augnablik.

165
00:08:31,974 --> 00:08:33,140
Leyfðu mér að fara á undan og gera þetta.

166
00:08:33,140 --> 00:08:35,559
Takið eftir því, sem þú kannt að hafa
komst undir stjórn,

167
00:08:35,559 --> 00:08:38,409
það er þetta endurtaka blokk, sem
lítur ekki eins og það sé það stór.

168
00:08:38,409 --> 00:08:41,039
Það er ekki mikið pláss í
milli þessara tveggja gulum línum.

169
00:08:41,039 --> 00:08:43,539
En eins og sumir af þú might hafa
tekið, ef þú draga og sleppa,

170
00:08:43,539 --> 00:08:45,150
eftir því hvernig það vex að fylla lögun.

171
00:08:45,150 --> 00:08:46,274
>> Og þú getur jafnvel troða meira.

172
00:08:46,274 --> 00:08:48,670
Það verður bara að halda áfram að stækka ef
þú draga og sveima yfir það.

173
00:08:48,670 --> 00:08:51,110
Og ég veit ekki hvað er
best hér, þannig að við skulum

174
00:08:51,110 --> 00:08:54,760
mér að minnsta kosti endurtaka fimm sinnum, fyrir
dæmi, og þá fara aftur á svið

175
00:08:54,760 --> 00:08:56,720
og smella á græna fána.

176
00:08:56,720 --> 00:08:59,110
Og nú eftir að það er ekki alveg það.

177
00:08:59,110 --> 00:09:02,400
>> Nú sumir af þú lagt, eins og
Victoria bara gerði, endurtaka 10 sinnum.

178
00:09:02,400 --> 00:09:05,140
Og það yfirleitt gerir
fá hann alla leið,

179
00:09:05,140 --> 00:09:10,510
en myndi ekki það að vera öflugri
leið en geðþótta vangaveltur út

180
00:09:10,510 --> 00:09:12,640
hversu margir færist á að gera?

181
00:09:12,640 --> 00:09:17,680
Hvað gæti verið betra blokk
en endurtaka 10 sinnum verið?

182
00:09:17,680 --> 00:09:20,380
>> Já, svo hvers vegna ekki að gera eitthvað eilífu?

183
00:09:20,380 --> 00:09:24,390
Og nú langar mig að færa þessa þraut stykki
þarna inni og losna við þessa einn.

184
00:09:24,390 --> 00:09:28,300
Nú taka Sama hvar Scratch
byrjar, fer hann að brún.

185
00:09:28,300 --> 00:09:30,700
Og sem betur fer MIT,
sem gerir Scratch, bara

186
00:09:30,700 --> 00:09:33,190
gerir viss um að hann hefur aldrei
hverfur alveg.

187
00:09:33,190 --> 00:09:35,360
Þú getur alltaf grípa skottið.

188
00:09:35,360 --> 00:09:37,680
>> Og bara innsæi,
hvers vegna er hann að halda að flytja?

189
00:09:37,680 --> 00:09:38,892
Hvað er að gerast hér?

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

191
00:09:41,440 --> 00:09:43,824
Hann virðist hafa hætt, en
þá ef ég tekið upp og draga

192
00:09:43,824 --> 00:09:45,240
Hann heldur langaði til að fara yfir það.

193
00:09:45,240 --> 00:09:46,123
Afhverju er það?

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

195
00:09:51,610 --> 00:09:54,360
Sannlega, tölvan er bókstaflega
að fara að gera það sem þú segir það að gera.

196
00:09:54,360 --> 00:09:58,380
Svo ef þú sagt það áðan að gera það
Eftirfarandi hlutur eilífu, færa 10 skref,

197
00:09:58,380 --> 00:10:01,860
það er að fara að halda áfram og fara
þangað til ég lenti á rauða stöðva merki

198
00:10:01,860 --> 00:10:04,620
og stöðva the program öllu leyti.

199
00:10:04,620 --> 00:10:06,610
>> Svo jafnvel ef þú did ekki
að gera þetta, hvernig gat ég

200
00:10:06,610 --> 00:10:09,510
gera Scratch fara hraðar
yfir skjáinn?

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

202
00:10:12,060 --> 00:10:13,280
Fleiri skref, ekki satt?

203
00:10:13,280 --> 00:10:15,710
Svo í stað þess að gera 10
í einu, hví ekki við

204
00:10:15,710 --> 00:10:20,100
fara á undan og breyta því to--
hvað myndir þú propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Svo nú er ég að fara að smella á græna
merkja, og reyndar fer hann mjög hratt.

206
00:10:24,410 --> 00:10:27,180
>> Og þetta, að sjálfsögðu, er bara
birtingarmynd fjör.

207
00:10:27,180 --> 00:10:28,060
Hvað er fjör?

208
00:10:28,060 --> 00:10:33,090
Það er bara að sýna þér manna a
heild búnt af kyrrmyndir í raun,

209
00:10:33,090 --> 00:10:34,160
virkilega, virkilega hratt.

210
00:10:34,160 --> 00:10:36,500
Og svo ef við erum bara að segja
honum að fara fleiri skref,

211
00:10:36,500 --> 00:10:39,750
við erum bara að hafa áhrif að vera að
breyting þar sem hann er á skjánum

212
00:10:39,750 --> 00:10:42,900
allt hraðar á tímaeiningu.

213
00:10:42,900 --> 00:10:46,454
>> Nú er næsta verkefni sem ég lagði
var að hafa hann hopp burt brún.

214
00:10:46,454 --> 00:10:49,120
Og án þess að vita hvað ráðgáta
stykki exist-- því það er fínt

215
00:10:49,120 --> 00:10:53,030
ef þú færð ekki til
stigi challenge-- hvað

216
00:10:53,030 --> 00:10:54,280
viltu gera innsæi?

217
00:10:54,280 --> 00:10:58,030
Hvernig myndum við hafa hann hopp til baka og
fram, milli vinstri og hægri?

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

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

220
00:11:03,810 --> 00:11:05,680
Þannig að við þurfum einhvers konar
á ástandi og við

221
00:11:05,680 --> 00:11:09,710
virðast hafa conditionals, svo að
tala, undir stjórn flokki.

222
00:11:09,710 --> 00:11:14,110
Hver af þessum blokkum
við viljum líklega?

223
00:11:14,110 --> 00:11:15,200
Já, kannski "ef, þá."

224
00:11:15,200 --> 00:11:18,780
Svo eftir að meðal gulu blokkir
við höfum hér, það er þetta "ef"

225
00:11:18,780 --> 00:11:23,920
eða þetta "ef annað" blokk sem vilja
leyfa okkur að taka ákvörðun um að gera þetta

226
00:11:23,920 --> 00:11:25,000
eða til að gera það.

227
00:11:25,000 --> 00:11:27,380
Og þú getur jafnvel hreiður þá
að gera marga hluti.

228
00:11:27,380 --> 00:11:34,910
Eða ef þú hefur ekki farið hér enn,
fara á undan til Sensing flokki

229
00:11:34,910 --> 00:11:39,612
and-- skulum sjá hvort það er hér.

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

231
00:11:43,050 --> 00:11:52,050
>> Svo það blokk gæti verið gagnlegt hér
til greina ef hann er af sviðinu?

232
00:11:52,050 --> 00:11:56,740
Já, eftir að sumir af þessum blokkum
Hægt er að parametrized, svo að segja.

233
00:11:56,740 --> 00:12:00,706
Þeir geta verið eins konar aðlaga, ekki
ólíkt HTML gær með eiginleika,

234
00:12:00,706 --> 00:12:03,330
ef þessir eiginleikar konar
sérsníða hegðun merkinu.

235
00:12:03,330 --> 00:12:08,880
Á sama hátt hér, get ég grípa þetta lauslega
blokk og breyta og spyrja,

236
00:12:08,880 --> 00:12:11,500
ertu að snerta músina
bendi eins bendilinn

237
00:12:11,500 --> 00:12:13,250
eða ertu að snerta brún?

238
00:12:13,250 --> 00:12:15,210
>> Svo láta mig fara á og gera þetta.

239
00:12:15,210 --> 00:12:18,130
Ég ætla að þysja út um stund.

240
00:12:18,130 --> 00:12:21,320
Leyfðu mér að grípa þessa þraut stykki
hér, þetta ráðgáta stykki þetta,

241
00:12:21,320 --> 00:12:24,570
og ég ætla að jumble
þá upp fyrir réttlátur a augnablik.

242
00:12:24,570 --> 00:12:27,620
Ég ætla að færa þetta,
að breyta þessu til að snerta brún,

243
00:12:27,620 --> 00:12:38,590
og ég ætla að hreyfingu gera þetta.

244
00:12:38,590 --> 00:12:40,490
Svo hér eru nokkrar innihaldsefni.

245
00:12:40,490 --> 00:12:42,570
Ég held að ég hef fengið allt sem ég vil.

246
00:12:42,570 --> 00:12:47,710
>> Myndi einhver vilja leggja því hvernig ég
Hægt er að tengja þessar kannski efst til botn

247
00:12:47,710 --> 00:12:52,020
í því skyni að leysa vandamál af því að hafa
Scratch hreyfa hægri til vinstri til hægri til að

248
00:12:52,020 --> 00:12:57,020
vinstri til hægri til vinstri, hvert
tími skoppar bara að slökkva á veggnum?

249
00:12:57,020 --> 00:12:58,050
Hvað vil ég gera?

250
00:12:58,050 --> 00:13:01,097
Hvaða blokk ætti ég að tengja við
"Þegar grænn fáni smellt fyrst"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, þannig að við skulum byrja með "að eilífu."

253
00:13:06,200 --> 00:13:07,170
Hvað fer inn næst?

254
00:13:07,170 --> 00:13:10,290
Einhver annar.

255
00:13:10,290 --> 00:13:11,850
OK, færa skrefum.

256
00:13:11,850 --> 00:13:12,350
Allt í lagi.

257
00:13:12,350 --> 00:13:14,470
Hvað svo?

258
00:13:14,470 --> 00:13:15,120
Svo þá ef.

259
00:13:15,120 --> 00:13:17,720
Og eftir, jafnvel þótt það lítur
samloka saman þétt,

260
00:13:17,720 --> 00:13:19,500
það verður bara að vaxa til að fylla.

261
00:13:19,500 --> 00:13:21,500
Það verður bara að hoppa í þar sem ég vil það.

262
00:13:21,500 --> 00:13:25,920
>> Og hvað á ég að setja á milli
if og þá?

263
00:13:25,920 --> 00:13:27,180
Sennilega "ef snerta brún."

264
00:13:27,180 --> 00:13:31,800
Og takið eftir, aftur, það er of stór
fyrir það, en það mun vaxa að fylla.

265
00:13:31,800 --> 00:13:35,002
Og þá snúa 15 gráður?

266
00:13:35,002 --> 00:13:35,710
Hversu margar gráður?

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

268
00:13:38,800 --> 00:13:41,196
Já, svo 180 mun snúast
mér alla leið kring.

269
00:13:41,196 --> 00:13:42,570
Svo skulum sjá hvort ég fékk þetta rétt.

270
00:13:42,570 --> 00:13:43,930
Leyfðu mér að súmma út.

271
00:13:43,930 --> 00:13:45,130
>> Leyfðu mér að draga Scratch upp.

272
00:13:45,130 --> 00:13:50,030
Svo hann er svolítið aum
nú, en það er allt í lagi.

273
00:13:50,030 --> 00:13:52,231
Hvernig get ég endurstilla hann auðveldlega?

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

275
00:13:59,879 --> 00:14:01,045
Ég ætla að svindla örlítið.

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

277
00:14:04,074 --> 00:14:05,990
Þannig að ég ætla að bæta öðru
blokk, bara til að vera skýr.

278
00:14:05,990 --> 00:14:08,424
Ég vil að hann benda 90 gráður
til hægri sjálfgefið,

279
00:14:08,424 --> 00:14:10,840
þannig að ég ætla bara að fara að segja honum
að gera það kerfisbundið.

280
00:14:10,840 --> 00:14:11,632
Og hér við fara.

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

282
00:14:14,740 --> 00:14:15,740
Við virðumst hafa gert það.

283
00:14:15,740 --> 00:14:19,980
Það er svolítið skrítið, því
hann er að ganga á hvolfi.

284
00:14:19,980 --> 00:14:21,250
Við skulum kalla það galla.

285
00:14:21,250 --> 00:14:22,120
Það er rangt.

286
00:14:22,120 --> 00:14:27,320
A padda er mistök í a program, a
rökrétt villa sem ég, manna, gerði.

287
00:14:27,320 --> 00:14:28,985
Hvers vegna er hann að fara á hvolf?

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

289
00:14:33,560 --> 00:14:35,250
Vissir MIT skrúfa upp eða gerði ég?

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

291
00:14:38,840 --> 00:14:42,550
>> Já, ég meina, það er ekki MIT er
kenna. Þeir gáfu mér ráðgáta stykki

292
00:14:42,550 --> 00:14:44,970
sem segir að snúa einhvern fjölda gráður.

293
00:14:44,970 --> 00:14:47,672
Og á tillögu Victoriu,
Ég ætla að snúa 180 gráður,

294
00:14:47,672 --> 00:14:48,880
sem er rétt innsæi.

295
00:14:48,880 --> 00:14:53,700
En beygja 180 gráður bókstaflega
þýðir að snúa 180 gráður,

296
00:14:53,700 --> 00:14:55,860
og það er í raun ekki
það sem ég vil, greinilega.

297
00:14:55,860 --> 00:14:58,026
Því að minnsta kosti er hann í
þetta tvívíð heimi,

298
00:14:58,026 --> 00:15:00,740
svo beygja er virkilega að fara
til að fletta honum á hvolfi.

299
00:15:00,740 --> 00:15:04,030
>> Ég vil líklega nota hvaða blokk
í staðinn, miðað við það sem þú sérð hér?

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

301
00:15:11,890 --> 00:15:14,790
Hvernig getum við lagað þetta?

302
00:15:14,790 --> 00:15:18,380
Já, svo við gætum benda
í gagnstæða átt.

303
00:15:18,380 --> 00:15:22,300
Og reyndar er jafnvel að
ekki að fara að vera nóg,

304
00:15:22,300 --> 00:15:26,410
vegna þess að við getum aðeins erfitt númer
að benda vinstri eða hægri.

305
00:15:26,410 --> 00:15:27,920
>> Þú veist hvað við gætum gert?

306
00:15:27,920 --> 00:15:30,160
Það lítur út eins og við höfum
þægindi blokk hér.

307
00:15:30,160 --> 00:15:32,987
Ef ég stækka, sjá
eitthvað sem við eins og hér?

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

309
00:15:36,120 --> 00:15:40,020
Svo það lítur út eins og MIT hefur
abstrakt byggð hér.

310
00:15:40,020 --> 00:15:45,440
Þessi blokk virðist vera jafngildar
sem aðrir blokkir, plural?

311
00:15:45,440 --> 00:15:49,510
>> Þetta ein húsaröð virðist vera jafngildar
að allri þessari þremur blokkum

312
00:15:49,510 --> 00:15:50,880
sem við höfum hér.

313
00:15:50,880 --> 00:15:54,670
Svo kemur í ljós að ég get einfalda minn
Forritið með því að fá losa af öllum sem

314
00:15:54,670 --> 00:15:58,270
og bara setja þetta hérna.

315
00:15:58,270 --> 00:16:01,620
Og nú er hann enn smá
þrjótur, og það er allt í lagi núna.

316
00:16:01,620 --> 00:16:03,370
Við munum fara að vera.

317
00:16:03,370 --> 00:16:06,000
En forritið mitt er jafnvel
einfaldara, og þetta líka,

318
00:16:06,000 --> 00:16:09,060
væri fulltrúi
um markmið í programming--

319
00:16:09,060 --> 00:16:13,430
er að helst að gera kóðann þinn eins
einfalt, eins samningur og mögulegt er,

320
00:16:13,430 --> 00:16:15,650
en samt vera eins
læsileg og hægt er.

321
00:16:15,650 --> 00:16:20,310
Þú vilt ekki að gera það svo gagnorðar
að það er erfitt að skilja.

322
00:16:20,310 --> 00:16:22,826
>> En eftir að ég hef skipt
þrjár blokkir með einn,

323
00:16:22,826 --> 00:16:24,200
og það er að öllum líkindum gott.

324
00:16:24,200 --> 00:16:27,280
Ég hef horfir burtu hugmynd
um að athuga hvort þú ert

325
00:16:27,280 --> 00:16:29,120
á brún með réttlátur einn blokk.

326
00:16:29,120 --> 00:16:31,520
Nú getum við haft gaman með þetta, í raun.

327
00:16:31,520 --> 00:16:35,790
Þetta þýðir ekki að bæta svo mikið
vitsmunalegum gildi en fjörugur gildi.

328
00:16:35,790 --> 00:16:39,730
Ég ætla að fara á undan
og grípa þetta hljóð hér.

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

330
00:16:42,900 --> 00:16:46,420
Svo láta mig fara á undan, og láta mig
stöðva forritið um stund.

331
00:16:46,420 --> 00:16:52,070
Ég ætla að taka eftirfarandi,
leyfa aðgang að hljóðnemanum mínum.

332
00:16:52,070 --> 00:16:53,181
>> Hér við fara.

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

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

335
00:16:58,710 --> 00:17:01,140
Við skulum reyna þetta aftur.

336
00:17:01,140 --> 00:17:02,279
Hér við fara.

337
00:17:02,279 --> 00:17:03,570
OK, ég skráð rangt hlutur.

338
00:17:03,570 --> 00:17:04,580
Hér við fara.

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

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

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

342
00:17:08,800 --> 00:17:09,300
Allt í lagi.

343
00:17:09,300 --> 00:17:10,791
Nú þarf ég að losna við það.

344
00:17:10,791 --> 00:17:11,290
Allt í lagi.

345
00:17:11,290 --> 00:17:13,950
>> Svo nú hef ég a
Upptakan af réttlátur "Ouch."

346
00:17:13,950 --> 00:17:18,040
Svo nú ætla ég að fara
á undan og kalla þetta "ouch."

347
00:17:18,040 --> 00:17:20,270
Ég ætla að fara aftur
til skrifta mínum, og nú

348
00:17:20,270 --> 00:17:25,460
tilkynning það er þetta blokk sem heitir
spila hljóð "meow" eða spila hljóð "ouch".

349
00:17:25,460 --> 00:17:28,920
Ég ætla að draga þetta, og þar sem
ætti ég að setja þetta fyrir fyndinn áhrif?

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

351
00:17:31,740 --> 00:17:37,860
Já, svo nú er það eins konar
þrjótur, því nú block-- þetta

352
00:17:37,860 --> 00:17:42,050
eftir því hvernig þetta "ef á brún,
hopp "er eins konar sjálf-gámur.

353
00:17:42,050 --> 00:17:43,704
Þannig að ég þarf að laga þetta.

354
00:17:43,704 --> 00:17:44,870
Leyfðu mér að fara á undan og gera þetta.

355
00:17:44,870 --> 00:17:48,630
Leyfðu mér að losna við þetta og fara aftur
að upprunalega okkar, meira vísvitandi

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

357
00:17:49,870 --> 00:18:01,080
Svo "ef snerta brún, þá" ég vil
að snúa, eins og Victoria lagt,

358
00:18:01,080 --> 00:18:02,480
180 gráður.

359
00:18:02,480 --> 00:18:05,497
Og ég vil að spila
hljóðið "ouch" það?

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

361
00:18:11,800 --> 00:18:15,580
>> Já, eftir það er úti
að gult blokk.

362
00:18:15,580 --> 00:18:17,680
Svo þetta líka, væri
galla, en ég hef tekið eftir því.

363
00:18:17,680 --> 00:18:21,290
Þannig að ég ætla að draga það upp hér,
og tilkynning nú er það inni í "ef".

364
00:18:21,290 --> 00:18:24,250
Svo "ef" er þetta tegund
af eins handlegg eins afmá

365
00:18:24,250 --> 00:18:26,260
það er bara að fara að
hvað er inni í henni.

366
00:18:26,260 --> 00:18:30,216
Svo nú ef ég súmma út á
hætta á annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Ouch, ouch, ouch.

369
00:18:36,470 --> 00:18:39,910
>> DAVID Malan: Og það
verður bara að fara að eilífu.

370
00:18:39,910 --> 00:18:44,160
Nú bara að flýta hlutina
hér, láta mig fara á undan og opna upp,

371
00:18:44,160 --> 00:18:50,460
skulum say-- láta mig fara að sumir
eigin dótinu mínu frá bekknum.

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

373
00:18:53,000 --> 00:19:00,220
Og láta mig opna, við skulum segja, þetta
einn gert með því að einn af félögum kennslu okkar

374
00:19:00,220 --> 00:19:01,500
a par af ár síðan.

375
00:19:01,500 --> 00:19:04,732
Svo sumir af þú might muna
þessi leikur frá fyrra,

376
00:19:04,732 --> 00:19:05,940
og það er í raun merkilegt.

377
00:19:05,940 --> 00:19:08,190
Jafnvel þó að við höfum gert það
Einfaldasta forrit núna,

378
00:19:08,190 --> 00:19:09,980
við skulum íhuga hvað þetta
reyndar lítur út.

379
00:19:09,980 --> 00:19:10,650
Leyfðu mér að ýta leika.

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

381
00:19:14,210 --> 00:19:18,980
>> Svo í þessum leik, höfum við
froskur og nota örina keys--

382
00:19:18,980 --> 00:19:23,340
Hann tekur stærri skref en ég remember--
Ég hef stjórn á þessu froskur.

383
00:19:23,340 --> 00:19:29,630
Og markmiðið er að komast yfir upptekinn
Vegurinn án þess að keyra inn í bíla.

384
00:19:29,630 --> 00:19:34,735
Og við skulum see-- ef ég fer upp hér, ég
verða að bíða fyrir log til að fletta af.

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

386
00:19:38,130 --> 00:19:39,274
Þetta er eins og galla.

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

388
00:19:42,240 --> 00:19:43,495
Þetta er góður af galla.

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

390
00:19:45,980 --> 00:19:46,480
Allt í lagi.

391
00:19:46,480 --> 00:19:51,550
Ég er á þetta hér,
þar, og þá halda

392
00:19:51,550 --> 00:19:54,100
áfram þangað til þú færð allar
froskarnir til Lily pads.

393
00:19:54,100 --> 00:19:55,920
Nú gæti þetta litið
allt flóknari,

394
00:19:55,920 --> 00:19:57,840
en við skulum reyna að brjóta
þetta niður andlega

395
00:19:57,840 --> 00:20:00,040
og munnlega í upprunalegu blokkir sína.

396
00:20:00,040 --> 00:20:03,910
Svo er það líklega ráðgáta
Verkið sem við höfum ekki séð ennþá

397
00:20:03,910 --> 00:20:07,440
en það er að bregðast við mínútum,
að það sem ég lenti á lyklaborðinu.

398
00:20:07,440 --> 00:20:11,660
>> Svo er það líklega einhvers konar
blokk sem segir, ef lykill jafngildir upp,

399
00:20:11,660 --> 00:20:15,965
þá gera eitthvað með Scratch--
kannski færa það 10 skref með þessum hætti.

400
00:20:15,965 --> 00:20:20,240
Ef ekki er ýtt niður takkann, fara 10 skref
This vegur, eða vinstri takkann, fara 10 skref

401
00:20:20,240 --> 00:20:21,710
This vegur, 10 skref sem.

402
00:20:21,710 --> 00:20:23,644
Ég hef greinilega sneri köttinn í frosk.

403
00:20:23,644 --> 00:20:26,060
Svo er það bara þar sem
búningur, eins Scratch símtöl it-- vér

404
00:20:26,060 --> 00:20:28,440
bara flutt mynd af froskinn.

405
00:20:28,440 --> 00:20:29,570
>> En hvað er að gerast?

406
00:20:29,570 --> 00:20:32,794
Hvaða önnur línur af kóða,
hvað aðrir stykki púsluspil

407
00:20:32,794 --> 00:20:35,460
gerði Blake, kennsla náungi okkar,
nota í þessu forriti, virðist?

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

409
00:20:38,320 --> 00:20:42,730
Hvað er að gera allt move--
hvað forritun reisa?

410
00:20:42,730 --> 00:20:44,950
>> Hreyfing, sure-- svo
færa blokk, fyrir viss.

411
00:20:44,950 --> 00:20:49,330
Og hvað er það að færa blokk
inni, líklega?

412
00:20:49,330 --> 00:20:52,850
Já, einhvers konar lykkju, kannski
eilífu loka, kannski endurtaka block--

413
00:20:52,850 --> 00:20:54,070
endurtaka þar til blokk.

414
00:20:54,070 --> 00:20:57,330
Og það er það sem er að gera logs og
The Lily pads og allt annað færa

415
00:20:57,330 --> 00:20:57,990
fram og til baka.

416
00:20:57,990 --> 00:21:00,270
Það er bara að gerast endalaust.

417
00:21:00,270 --> 00:21:03,180
>> Hvers vegna eru nokkrar af þeim bílum
áhrifamikill hraðar en aðrir?

418
00:21:03,180 --> 00:21:06,607
Hvað er öðruvísi um þá forrit?

419
00:21:06,607 --> 00:21:09,690
Já, sennilega sumir af þeim eru notuð
fleiri skref í einu og sumir af þeim

420
00:21:09,690 --> 00:21:10,690
færri skref í einu.

421
00:21:10,690 --> 00:21:14,670
Og sjónræn áhrif
er fljótur móti hægt.

422
00:21:14,670 --> 00:21:16,030
>> Hvað finnst þér gerðist?

423
00:21:16,030 --> 00:21:19,700
Þegar ég fékk frosk minn alla leið
yfir götuna og árinnar

424
00:21:19,700 --> 00:21:23,560
inn á Lily púði, eitthvað
athyglisvert gerðist.

425
00:21:23,560 --> 00:21:26,540
Hvað gerðist um leið og ég gerði það?

426
00:21:26,540 --> 00:21:27,210
Það hætt.

427
00:21:27,210 --> 00:21:29,680
Það froskur hætt, og
Ég fékk annað froskur.

428
00:21:29,680 --> 00:21:33,155
Svo það reisa verður
nota það, hvað eiginleiki?

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

430
00:21:36,020 --> 00:21:38,660
>> Já, svo er það einhvers konar
"Ef" ástand þarna líka.

431
00:21:38,660 --> 00:21:41,909
Og það kemur out-- við ekki sjá this--
en það er önnur blokkir þarna sem

432
00:21:41,909 --> 00:21:45,300
má segja, ef þú ert að snerta
annar hlutur á skjánum,

433
00:21:45,300 --> 00:21:47,720
ef þú ert að snerta Lily púði, "þá."

434
00:21:47,720 --> 00:21:50,810
Og þá er það þegar við
gera annað froskur birtast.

435
00:21:50,810 --> 00:21:54,969
Svo jafnvel þótt þessi leikur er vissulega
mjög dagsett, jafnvel þótt við fyrstu sýn

436
00:21:54,969 --> 00:21:58,010
það er svo mikið að fara skráin og Blake
ekki svipa þetta upp í tvær mínútur,

437
00:21:58,010 --> 00:22:00,390
það tók sennilega honum nokkrir
klukkustundir að búa til þennan leik

438
00:22:00,390 --> 00:22:03,850
byggt á minni hans eða myndskeið
af útgáfu fyrra er af henni.

439
00:22:03,850 --> 00:22:07,940
En allar þessar litlu hluti
fara á skjánum í einangrun

440
00:22:07,940 --> 00:22:11,550
sjóða niður í þessar mjög einfalt
constructs-- hreyfingar eða yfirlýsingar

441
00:22:11,550 --> 00:22:15,519
eins og við höfum rætt, lykkjur og
skilyrði, og það er um það.

442
00:22:15,519 --> 00:22:17,060
Það er nokkrar aðrar áhugamaður lögun.

443
00:22:17,060 --> 00:22:19,130
Sumir þeirra eru eingöngu
fagurfræði eða hljóðeinangrun,

444
00:22:19,130 --> 00:22:20,964
eins hljóðum sem ég spilaði bara með.

445
00:22:20,964 --> 00:22:23,380
En að mestu leyti, að
hafa í þessu tungumáli, klóra,

446
00:22:23,380 --> 00:22:25,350
allt grundvallaratriði
kubbar sem þú

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

448
00:22:29,280 --> 00:22:32,960
og fjölda annarra tungumála.

449
00:22:32,960 --> 00:22:36,720
Einhverjar spurningar um grunni?

450
00:22:36,720 --> 00:22:37,220
Allt í lagi.

451
00:22:37,220 --> 00:22:40,303
Þannig að við munum ekki kafa dýpra til grunni,
þó þú ert velkominn um helgina,

452
00:22:40,303 --> 00:22:42,860
sérstaklega ef þú ert með krakka eða
dætur og nephews og svo,

453
00:22:42,860 --> 00:22:44,220
að kynna þeim grunni.

454
00:22:44,220 --> 00:22:47,960
Það er í raun frábærlega fjörugur
umhverfi með, eins og höfundar hennar segja,

455
00:22:47,960 --> 00:22:49,120
mjög há loft.

456
00:22:49,120 --> 00:22:51,670
Jafnvel þó að við byrjuðum með
mjög lágmark-láréttur flötur upplýsingar,

457
00:22:51,670 --> 00:22:54,890
þú getur raunverulega gert töluvert
með það, og þetta er kannski

458
00:22:54,890 --> 00:22:57,360
sýning á einmitt það.

459
00:22:57,360 --> 00:23:02,920
>> En við skulum nú yfir í meira
háþróuð vandamál, ef þú vilt,

460
00:23:02,920 --> 00:23:05,870
þekktur sem "leita" og
"Flokkun" almennt.

461
00:23:05,870 --> 00:23:09,500
Við höfðum þetta símaskrá earlier-- hér er
annað bara fyrir discussion--

462
00:23:09,500 --> 00:23:13,460
sem við gátum til að leita
á skilvirkari hátt vegna þess að

463
00:23:13,460 --> 00:23:15,270
verulegs forsendu.

464
00:23:15,270 --> 00:23:17,655
Og bara til að vera skýr, hvað
forsenda var ég að gera

465
00:23:17,655 --> 00:23:19,280
þegar að leita í gegnum þetta símaskránni?

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

467
00:23:23,342 --> 00:23:25,300
Það Mike Smith var árið
símaskrá, þótt ég

468
00:23:25,300 --> 00:23:27,410
vildi vera fær um að takast
atburðarás án hans

469
00:23:27,410 --> 00:23:30,720
það ef ég hætti bara snemma.

470
00:23:30,720 --> 00:23:31,806
Bókin er stafrófsröð.

471
00:23:31,806 --> 00:23:33,930
Og það er mjög örlátur
forsenda, því að

472
00:23:33,930 --> 00:23:36,580
þýðir someone-- ég er svona
klippa horn,

473
00:23:36,580 --> 00:23:40,580
eins og ég er hraðari vegna einhvers
annars gerði mikið af vinnu fyrir mig.

474
00:23:40,580 --> 00:23:43,120
>> En hvað ef síminn
Bókin var óflokkuðu?

475
00:23:43,120 --> 00:23:47,050
Kannski Regin fékk latur, bara kastaði
nöfn allra og tölur þar

476
00:23:47,050 --> 00:23:50,120
kannski í þeirri röð sem þau
skráði sig fyrir símaþjónustu.

477
00:23:50,120 --> 00:23:54,570
Og hversu miklum tíma tekur það mig
að finna einhvern eins og Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1.000 síðu sími book-- hversu margir
síður þarf ég að horfa í gegnum?

479
00:23:58,160 --> 00:23:58,905
>> Öllum þeim.

480
00:23:58,905 --> 00:24:00,030
Þú ert svona út af heppni.

481
00:24:00,030 --> 00:24:03,420
Þú þarft bókstaflega að líta á hvert
síðu ef síminn bókin er bara

482
00:24:03,420 --> 00:24:04,450
handahófi flokkað.

483
00:24:04,450 --> 00:24:06,910
Þú might fá heppinn og finna Mike
á fyrstu síðu, vegna þess að hann

484
00:24:06,910 --> 00:24:08,826
var fyrsti viðskiptavinurinn
að panta símaþjónustu.

485
00:24:08,826 --> 00:24:10,760
En hann gæti hafa verið síðasta líka.

486
00:24:10,760 --> 00:24:12,500
>> Svo er af handahófi röð ekki gott.

487
00:24:12,500 --> 00:24:16,750
Svo býst við að raða í
símaskrá eða á almennum raða gögnum

488
00:24:16,750 --> 00:24:18,520
sem við höfum verið gefið.

489
00:24:18,520 --> 00:24:19,440
Hvernig getum við gert það?

490
00:24:19,440 --> 00:24:21,360
>> Jæja, láttu mig reyna bara
einfalt dæmi hér.

491
00:24:21,360 --> 00:24:24,290
Leyfðu mér að fara á undan og henda a
Nokkrar tölur um borð.

492
00:24:24,290 --> 00:24:35,480
Segjum tölur sem við höfum eru,
við skulum segja, fjórir, tveir, einn, og þrjú.

493
00:24:35,480 --> 00:24:38,390
Og Ben, raða þessar tölur fyrir okkur.

494
00:24:38,390 --> 00:24:39,017
>> Allt í lagi gott.

495
00:24:39,017 --> 00:24:39,850
Hvernig gerðir þú þetta?

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

497
00:24:42,731 --> 00:24:43,230
Allt í lagi.

498
00:24:43,230 --> 00:24:44,710
Svo byrja með minnstu
gildi og hæsta,

499
00:24:44,710 --> 00:24:46,084
og það er mjög gott innsæi.

500
00:24:46,084 --> 00:24:48,080
Og ljóst að við
menn eru í raun frekar

501
00:24:48,080 --> 00:24:49,913
gott að leysa vandamál
eins og þetta, að minnsta kosti

502
00:24:49,913 --> 00:24:51,810
þegar gögnum er tiltölulega lítill.

503
00:24:51,810 --> 00:24:54,860
Um leið og þú byrjar að hafa hundruð
af tölum, þúsundir tölum,

504
00:24:54,860 --> 00:24:58,440
milljónir tölur, Ben sennilega
gat ekki gert það alveg að hratt,

505
00:24:58,440 --> 00:25:00,620
að því gefnu að það væri
eyður í tölurnar.

506
00:25:00,620 --> 00:25:03,450
Nokkuð auðvelt að telja upp að milljón
annars, bara tímafrekt.

507
00:25:03,450 --> 00:25:07,150
>> Svo reiknirit það hljómar
eins Ben notað bara núna

508
00:25:07,150 --> 00:25:08,930
var að leita fyrir minnstu númer.

509
00:25:08,930 --> 00:25:12,900
Svo jafnvel þó að við mennirnir getum tekið
í fullt af upplýsingum sjónrænt,

510
00:25:12,900 --> 00:25:14,830
tölvan er í raun
svolítið meira takmarkaður.

511
00:25:14,830 --> 00:25:17,560
Tölvan getur aðeins
líta á eitt bæti í einu

512
00:25:17,560 --> 00:25:20,770
eða kannski fjögur bæti á a time--
þessa dagana kannski 8 bytes á a time--

513
00:25:20,770 --> 00:25:24,450
en mjög lítill fjöldi
bytes á hverjum tíma.

514
00:25:24,450 --> 00:25:28,480
>> Svo í ljósi þess að við höfum í raun
fjögur aðskilin gildi here--

515
00:25:28,480 --> 00:25:32,440
og hægt er að hugsa um Ben sem hafa
augnskjól ef hann væri tölvan slík

516
00:25:32,440 --> 00:25:36,450
að hann getur ekki séð neitt annað
en eitt númer í time--

517
00:25:36,450 --> 00:25:39,720
svo við almennt mun gera ráð fyrir, eins og í
English, munum við lesa frá hægri til vinstri.

518
00:25:39,720 --> 00:25:42,870
Svo fyrsta númerið Ben sennilega litið
á var fjögurra og þá mjög fljótt

519
00:25:42,870 --> 00:25:44,770
komust að því er ansi stór
number-- láta mig halda að leita.

520
00:25:44,770 --> 00:25:45,357
>> Það er tveggja.

521
00:25:45,357 --> 00:25:45,940
Bíddu aðeins.

522
00:25:45,940 --> 00:25:47,070
Tveggja er minni en fjórir.

523
00:25:47,070 --> 00:25:47,986
Ég ætla að muna.

524
00:25:47,986 --> 00:25:49,070
Tvö er nú minnsti.

525
00:25:49,070 --> 00:25:50,417
Nú er one-- jafnvel betra.

526
00:25:50,417 --> 00:25:51,250
Það er jafnvel minni.

527
00:25:51,250 --> 00:25:54,000
Ég ætla að gleyma um tvo
og bara muna eitt núna.

528
00:25:54,000 --> 00:25:56,550
>> Og gæti hann hætt að leita?

529
00:25:56,550 --> 00:25:58,360
Jæja, gat hann byggt
á þessum upplýsingum,

530
00:25:58,360 --> 00:26:00,477
en hann myndi betri leit
restin af listanum.

531
00:26:00,477 --> 00:26:02,060
Vegna þess hvað ef núll voru á listanum?

532
00:26:02,060 --> 00:26:03,643
Hvað ef neikvætt einn voru á listanum?

533
00:26:03,643 --> 00:26:07,720
Hann veit bara að svar hans
er rétt ef hann er tæmandi

534
00:26:07,720 --> 00:26:08,729
skoðaði alla lista.

535
00:26:08,729 --> 00:26:10,020
Þannig að við líta á the hvíla af þessu.

536
00:26:10,020 --> 00:26:11,394
Three-- sem var tímasóun.

537
00:26:11,394 --> 00:26:13,540
Fékk óheppinn, en ég var
enn rétt til að gera það.

538
00:26:13,540 --> 00:26:17,857
Og svo nú er hann væntanlega
valinn minnsti fjöldi

539
00:26:17,857 --> 00:26:20,440
og bara setja það í upphafi
á listanum, eins og ég geri hér.

540
00:26:20,440 --> 00:26:23,480
Nú hvað gerðirðu næst, jafnvel þótt
þú ekki að hugsa um það næstum

541
00:26:23,480 --> 00:26:25,962
að þessu leyti?

542
00:26:25,962 --> 00:26:27,670
Endurtaka ferlið,
svo einhvers konar lykkju.

543
00:26:27,670 --> 00:26:28,920
Það er kunnuglegt hugmynd.

544
00:26:28,920 --> 00:26:30,860
Svo hér er fjórir.

545
00:26:30,860 --> 00:26:32,110
Það er nú minnsti.

546
00:26:32,110 --> 00:26:33,220
Það er frambjóðandi.

547
00:26:33,220 --> 00:26:33,900
Ekki lengur.

548
00:26:33,900 --> 00:26:34,770
Nú hef ég séð tvö.

549
00:26:34,770 --> 00:26:36,630
Það er næsta minnsti þátturinn.

550
00:26:36,630 --> 00:26:40,800
Three-- það er ekki minni, svo
Nú Ben getur slíta út tvö.

551
00:26:40,800 --> 00:26:44,510
>> Og nú erum við að endurtaka ferlið og
auðvitað þremur fær dreginn út næst.

552
00:26:44,510 --> 00:26:45,420
Endurtaka ferlið.

553
00:26:45,420 --> 00:26:46,990
Four fær dreginn út.

554
00:26:46,990 --> 00:26:50,140
Og nú erum við út af tölum,
svo listinn verður flokkaður.

555
00:26:50,140 --> 00:26:51,960
>> Og reyndar, þetta er formleg reiknirit.

556
00:26:51,960 --> 00:26:56,610
A tölva vísindamaður myndi
kalla þetta "val tagi,"

557
00:26:56,610 --> 00:27:00,880
hugmyndin er að raða a
lista iteratively-- aftur

558
00:27:00,880 --> 00:27:03,807
og aftur og aftur velja
minnsti fjöldi.

559
00:27:03,807 --> 00:27:06,140
Og hvað er gott um það er
það er bara svo fjári innsæi.

560
00:27:06,140 --> 00:27:07,470
Það er svo einfalt.

561
00:27:07,470 --> 00:27:11,100
Og er hægt að endurtaka sama
rekstur aftur og aftur.

562
00:27:11,100 --> 00:27:12,150
Það er einfalt.

563
00:27:12,150 --> 00:27:17,170
>> Í þessu tilviki var það hratt, en
hversu langan tíma tekur það í raun og veru?

564
00:27:17,170 --> 00:27:19,880
Við skulum gera það virðast og
feel a lítill fleiri leiðinlegur.

565
00:27:19,880 --> 00:27:24,150
Svo einn, tveir, þrír, fjórir, fimm sex,
sjö, átta, níu, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- handahófskennt númer.

567
00:27:26,160 --> 00:27:28,780
Ég vildi bara meira á þessu
tími en bara fjórum.

568
00:27:28,780 --> 00:27:30,780
Svo ef ég hef fengið heild
fullt af tölum now-- það

569
00:27:30,780 --> 00:27:32,420
skiptir ekki einu sinni máli
hvað þeir are-- skulum

570
00:27:32,420 --> 00:27:34,380
hugsa um hvað þetta
reiknirit er í raun eins.

571
00:27:34,380 --> 00:27:35,857
>> Segjum að það eru tölur þar.

572
00:27:35,857 --> 00:27:38,190
Aftur, skiptir ekki máli hvað
þeir eru, en þeir eru af handahófi.

573
00:27:38,190 --> 00:27:39,679
Ég sæki reiknirit Ben er.

574
00:27:39,679 --> 00:27:41,220
Ég þarf að velja minnstu númer.

575
00:27:41,220 --> 00:27:41,761
Hvað geri ég?

576
00:27:41,761 --> 00:27:44,240
Og ég ætla að líkamlega
gera það í þetta sinn til að bregðast hana út.

577
00:27:44,240 --> 00:27:46,099
Horft, útlit,
leita, leita, leita.

578
00:27:46,099 --> 00:27:48,140
Aðeins með þeim tíma sem ég fá að
í lok listanum getur

579
00:27:48,140 --> 00:27:51,230
Ég geri mér grein minnsti
Fjöldi var tveggja þetta sinn.

580
00:27:51,230 --> 00:27:52,720
Einn er ekki á listanum.

581
00:27:52,720 --> 00:27:54,400
Svo ég setti niður tvö.

582
00:27:54,400 --> 00:27:55,590
>> Hvað á ég að gera næst?

583
00:27:55,590 --> 00:27:58,600
Horft, útlit, útlit, útlit.

584
00:27:58,600 --> 00:28:02,250
Nú er ég fann númerið sjö, því
það er eyður í þessum Numbers

585
00:28:02,250 --> 00:28:03,300
en bara handahófskennt.

586
00:28:03,300 --> 00:28:03,800
Allt í lagi.

587
00:28:03,800 --> 00:28:06,030
Svo nú get ég sett niður sjö.

588
00:28:06,030 --> 00:28:08,860
Leita að, leita.

589
00:28:08,860 --> 00:28:11,030
>> Nú er ég hrokafullur, af
Auðvitað, að Ben ekki

590
00:28:11,030 --> 00:28:14,780
hafa auka RAM, auka
minni, vegna þess, að sjálfsögðu,

591
00:28:14,780 --> 00:28:16,080
Ég er að horfa á sama númer.

592
00:28:16,080 --> 00:28:18,246
Víst hefði ég mundi
allar þær tölur,

593
00:28:18,246 --> 00:28:19,930
og það er alveg satt.

594
00:28:19,930 --> 00:28:22,610
En ef Ben man alla
númera hann séð,

595
00:28:22,610 --> 00:28:24,430
Hann hefur í raun ekki gert
grundvallaratriði framfarir

596
00:28:24,430 --> 00:28:26,170
vegna þess að hann hefur nú þegar
getu til að leita

597
00:28:26,170 --> 00:28:27,540
í gegnum tölurnar á borðinu.

598
00:28:27,540 --> 00:28:29,373
Muna allt í
Tölurnar hjálpar ekki,

599
00:28:29,373 --> 00:28:32,490
vegna þess að hann getur enn sem tölvu
aðeins að líta á, að við höfum sagt, eitt númer

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

601
00:28:33,080 --> 00:28:35,760
Þannig að það er engin svoleiðis svindl
þar sem hægt er að nýta.

602
00:28:35,760 --> 00:28:39,170
>> Svo í raun, eins og ég
halda áfram að leita á listanum,

603
00:28:39,170 --> 00:28:44,200
Ég hef bókstaflega bara að halda áfram
fram og til baka í gegnum það, plokkun út

604
00:28:44,200 --> 00:28:45,710
næsta minnsti fjöldi.

605
00:28:45,710 --> 00:28:48,810
Og eins og þú getur konar álykta
frá kjánalegt hreyfingum mínum,

606
00:28:48,810 --> 00:28:50,860
þetta verður bara mjög
leiðinlegur mjög fljótt,

607
00:28:50,860 --> 00:28:54,850
og ég virðist vera að fara til baka og
fram, fram og til baka töluvert.

608
00:28:54,850 --> 00:29:03,220
Nú til að vera sanngjarn, ég er ekki að fara
alveg eins vel, við skulum see-- að vera sanngjarn,

609
00:29:03,220 --> 00:29:06,310
Ég þarf ekki að ganga alveg
sem margir stíga hvert skipti.

610
00:29:06,310 --> 00:29:09,200
Vegna þess, að sjálfsögðu, eins og ég
velja númer af listanum,

611
00:29:09,200 --> 00:29:11,860
sem eftir listi er að fá styttri.

612
00:29:11,860 --> 00:29:14,240
>> Og svo skulum hugsa um
hversu mörg skref ég er reyndar

613
00:29:14,240 --> 00:29:16,010
traipsing gegnum hvert skipti.

614
00:29:16,010 --> 00:29:18,950
Í fyrstu stöðu
við höfðum 16 tölur,

615
00:29:18,950 --> 00:29:22,210
og svo maximally-- skulum bara
gera þetta fyrir discussion--

616
00:29:22,210 --> 00:29:25,640
Ég þurfti að horfa í gegnum 16
tölur til að finna minnstu.

617
00:29:25,640 --> 00:29:28,420
En þegar ég kippti út
minnsti fjöldi, hvernig

618
00:29:28,420 --> 00:29:30,590
lengi var eftirstandandi lista, auðvitað?

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

620
00:29:31,420 --> 00:29:34,670
Svo hversu margar tölur gerðu Ben eða ég hef
að líta í gegnum annað sinn í kring?

621
00:29:34,670 --> 00:29:36,832
15, bara að fara og finna minnstu.

622
00:29:36,832 --> 00:29:39,540
En nú, auðvitað, listinn er,
of, minni en hún var áður.

623
00:29:39,540 --> 00:29:42,540
Svo hversu mörg skref gerði ég
þarft að taka næst?

624
00:29:42,540 --> 00:29:49,970
14 og síðan 13 og svo 12, plús punktur,
punktur, punktur, þar til ég er vinstri með bara einn.

625
00:29:49,970 --> 00:29:53,146
Svo nú tölvunarfræðingur myndi
spyrja, vel, hvað þýðir að allir jafnir?

626
00:29:53,146 --> 00:29:55,770
Það jafngildir í raun smá steypu
tala sem við gátum vissulega

627
00:29:55,770 --> 00:30:00,490
gera arithmetically, en við viljum að tala
um skilvirkni reiknirit

628
00:30:00,490 --> 00:30:04,940
smá meira formulaically,
óháð hversu lengi listinn er.

629
00:30:04,940 --> 00:30:06,240
>> Og svo þú veist hvað?

630
00:30:06,240 --> 00:30:09,860
Þetta er 16, en eins og ég sagði áður,
við skulum bara kalla stærð vandans

631
00:30:09,860 --> 00:30:10,970
n, þar sem n er einhver númer.

632
00:30:10,970 --> 00:30:13,220
Kannski er það 16, kannski er það
þrír, kannski er það milljón.

633
00:30:13,220 --> 00:30:13,761
Ég veit ekki.

634
00:30:13,761 --> 00:30:14,390
Mér er alveg sama.

635
00:30:14,390 --> 00:30:16,520
Það sem ég vil virkilega er
uppskrift sem ég get

636
00:30:16,520 --> 00:30:19,420
nota til að bera saman þessa reiknirit
gegn öðrum reiknirit

637
00:30:19,420 --> 00:30:22,350
að einhver gæti krafa
eru betri eða verri.

638
00:30:22,350 --> 00:30:25,430
>> Svo kemur í ljós, og ég bara
veit þetta af grunnskóla,

639
00:30:25,430 --> 00:30:34,790
að þetta virkar í raun út á það sama
hlutur sem n yfir n plús einn yfir tvö.

640
00:30:34,790 --> 00:30:40,020
Og þetta gerist til að jafna, af
Auðvitað n veldi plús n yfir tvö.

641
00:30:40,020 --> 00:30:43,250
Þannig að ef ég vildi formúlu
fyrir hversu mörg skref

642
00:30:43,250 --> 00:30:46,330
tóku þátt í að horfa á alla
þær tölur aftur og aftur

643
00:30:46,330 --> 00:30:52,681
og aftur og aftur, myndi ég segja
það er n veldi plús n yfir tvö.

644
00:30:52,681 --> 00:30:53,430
En þú veist hvað?

645
00:30:53,430 --> 00:30:54,500
Þetta lítur bara sóðalegur.

646
00:30:54,500 --> 00:30:56,470
Ég bara virkilega a
almennum skilningi hlutanna.

647
00:30:56,470 --> 00:30:58,810
Og þú gætir muna frá
menntaskóla að það

648
00:30:58,810 --> 00:31:00,660
er hugmyndin um hæsta röð tíma.

649
00:31:00,660 --> 00:31:05,300
Hver af þessum skilmálum, n
í öðru veldi, N, eða helmingur,

650
00:31:05,300 --> 00:31:07,550
hefur mest áhrif með tímanum?

651
00:31:07,550 --> 00:31:11,920
The allstór n fær, sem
af þessum málum sem mest?

652
00:31:11,920 --> 00:31:15,560
>> Með öðrum orðum, ef ég stinga
í milljón, n veldi

653
00:31:15,560 --> 00:31:17,900
er að fara að vera líklegur
ríkjandi þáttur,

654
00:31:17,900 --> 00:31:21,670
því milljón sinnum
sjálft er mikið stærri

655
00:31:21,670 --> 00:31:23,682
en auk einn til viðbótar milljón.

656
00:31:23,682 --> 00:31:24,390
Svo þú veist hvað?

657
00:31:24,390 --> 00:31:27,305
Þetta er svo fjári stór
númer ef þú ferningur númer.

658
00:31:27,305 --> 00:31:28,430
Þetta skiptir ekki máli.

659
00:31:28,430 --> 00:31:30,596
Við erum bara að fara kross sem
út og gleyma óður í það.

660
00:31:30,596 --> 00:31:34,250
Og svo tölvunarfræðingur myndi segja
að skilvirkni þessarar reiknirit

661
00:31:34,250 --> 00:31:37,850
er á röð n squared--
Ég meina sannarlega nálgun.

662
00:31:37,850 --> 00:31:40,810
Það er tegund af gróflega n veldi.

663
00:31:40,810 --> 00:31:44,130
Með tímanum, stærri
og stærri n fær þetta

664
00:31:44,130 --> 00:31:47,610
er gott mat á hvað
skilvirkni eða skortur á skilvirkni

665
00:31:47,610 --> 00:31:49,400
þessarar reiknirit í raun er.

666
00:31:49,400 --> 00:31:52,040
Og ég reikna að sjálfsögðu,
frá raun að gera stærðfræði.

667
00:31:52,040 --> 00:31:54,040
En núna er ég bara að veifa
hendur mínar, því ég bara

668
00:31:54,040 --> 00:31:55,790
langar almenna tilfinningu þessarar reiknirit.

669
00:31:55,790 --> 00:31:58,850
>> Svo nota sömu rökfræði, á meðan,
skulum íhuga annað reiknirit

670
00:31:58,850 --> 00:32:01,162
við skoðuðum þegar at-- línulega leit.

671
00:32:01,162 --> 00:32:02,870
Þegar ég var að leita
fyrir síma book--

672
00:32:02,870 --> 00:32:05,980
Ekki flokkun og leita
gegnum síma book--

673
00:32:05,980 --> 00:32:09,197
við haldið segja að það væri
1.000 skrefum, eða 500 skref.

674
00:32:09,197 --> 00:32:10,280
En við skulum alhæfa það.

675
00:32:10,280 --> 00:32:12,860
Ef það er n síður í
símaskrá, hvað er

676
00:32:12,860 --> 00:32:17,250
gangi sinn eða
skilvirkni línuleg leit?

677
00:32:17,250 --> 00:32:19,750
Það er á röð
hversu mörg skref til að finna

678
00:32:19,750 --> 00:32:24,210
Mike Smith nota línulega leit er
Fyrsta reiknirit, eða jafnvel annað?

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

680
00:32:27,240 --> 00:32:31,710
>> Í versta tilfelli, Mike
er í lok bókarinnar.

681
00:32:31,710 --> 00:32:35,590
Svo ef síminn bókin hefur 1.000 síður,
sagði að við síðasta skipti, í versta tilfelli,

682
00:32:35,590 --> 00:32:38,380
það gæti tekið u.þ.b. hversu
margar síður til að finna Mike?

683
00:32:38,380 --> 00:32:38,990
Eins 1.000.

684
00:32:38,990 --> 00:32:39,830
Það er efri.

685
00:32:39,830 --> 00:32:41,790
Það er versta mögulega ástand.

686
00:32:41,790 --> 00:32:44,410
En aftur, við erum að flytja í burtu
frá tölum eins 1.000 núna.

687
00:32:44,410 --> 00:32:45,730
Það er bara n.

688
00:32:45,730 --> 00:32:47,470
>> Svo er það rökrétt niðurstaða?

689
00:32:47,470 --> 00:32:50,210
Finndu Mike í símann
bók sem hefur n síður

690
00:32:50,210 --> 00:32:55,280
gæti tekið, í mjög versta tilfelli,
hversu mörg skref á röð n?

691
00:32:55,280 --> 00:32:58,110
Og raunar tölvu
vísindamaður myndi segja

692
00:32:58,110 --> 00:33:02,340
sem gangi tíma, eða á
árangur eða skilvirkni

693
00:33:02,340 --> 00:33:07,470
eða óhagkvæmni, af reiknirit eins
línulegt leit er á röð á n.

694
00:33:07,470 --> 00:33:10,010
Og við getum beita sömu
Röksemdafærsla yfir eitthvað út

695
00:33:10,010 --> 00:33:13,170
eins og ég gerði bara til seinni
reiknirit sem við höfðum með símaskrá,

696
00:33:13,170 --> 00:33:16,040
þar sem við fórum tvær síður í einu.

697
00:33:16,040 --> 00:33:20,120
>> Svo 1.000 síðu símaskrá gætu
taka okkur 500 page beygjur, plús einn

698
00:33:20,120 --> 00:33:21,910
ef við tvöfalda baka svolítið.

699
00:33:21,910 --> 00:33:26,590
Svo ef símaskrá hefur n síður, en
við erum að gera tvær síður í einu,

700
00:33:26,590 --> 00:33:28,900
það er u.þ.b. hvað?

701
00:33:28,900 --> 00:33:33,190
N á tveimur, þannig að það er eins og n yfir tveimur.

702
00:33:33,190 --> 00:33:38,490
En ég gerði kröfu
stund síðan að n yfir two--

703
00:33:38,490 --> 00:33:41,060
það er góður af the sami eins og bara n.

704
00:33:41,060 --> 00:33:44,050
Það er bara stöðug þáttur,
tölva vísindamenn myndi segja.

705
00:33:44,050 --> 00:33:45,970
Við skulum bara einblína á
breytur, really--

706
00:33:45,970 --> 00:33:47,780
stærsta breytur í jöfnunni.

707
00:33:47,780 --> 00:33:52,530
>> Svo línuleg leit, hvort sem gert einn
síðu í einu eða tvær síður í einu,

708
00:33:52,530 --> 00:33:54,810
er tegund af grundvallaratriðum sú sama.

709
00:33:54,810 --> 00:33:56,880
Það er samt á röð n.

710
00:33:56,880 --> 00:34:01,930
En ég hélt með myndina mína áðan
að þriðja algrím var ekki

711
00:34:01,930 --> 00:34:02,480
línuleg.

712
00:34:02,480 --> 00:34:03,605
Það var ekki beina línu.

713
00:34:03,605 --> 00:34:08,659
Það var það sveigð lína, og
algebrulegt uppskrift var það?

714
00:34:08,659 --> 00:34:11,812
Log um n- svo log stöð tvö af n.

715
00:34:11,812 --> 00:34:14,520
Og við þurfum ekki að fara út í of
mikið smáatriði á logra dag,

716
00:34:14,520 --> 00:34:17,394
en flestir tölva vísindamenn myndu ekki
jafnvel segja þér hvað stöð er.

717
00:34:17,394 --> 00:34:20,639
Vegna þess að það er allt bara
stöðug þættir, svo að segja,

718
00:34:20,639 --> 00:34:22,659
bara hirða tölugildi munur.

719
00:34:22,659 --> 00:34:31,179
Og svo þetta væri mjög algeng
leið fyrir sérstaklega formlegrar tölvuna

720
00:34:31,179 --> 00:34:33,949
Vísindamenn á borð eða
forritari á hvítt borð

721
00:34:33,949 --> 00:34:36,889
reyndar með þeim rökum sem
algrím þeir myndu nota

722
00:34:36,889 --> 00:34:39,500
eða hvað skilvirkni
af reiknirit þeirra er.

723
00:34:39,500 --> 00:34:42,960
>> Og þetta er ekki endilega eitthvað
þú ræða í hvaða smáatriðum,

724
00:34:42,960 --> 00:34:47,889
en góður forritari er einhver
sem hefur traustan, formlega bakgrunni.

725
00:34:47,889 --> 00:34:50,120
Hann er fær um að tala við
þú í svona hátt

726
00:34:50,120 --> 00:34:53,350
og í raun gera
eigindlegar rök sem

727
00:34:53,350 --> 00:34:56,870
að hvers vegna einn reiknirit eða
eitt stykki af hugbúnaður

728
00:34:56,870 --> 00:35:00,165
er betri á einhvern hátt til annars.

729
00:35:00,165 --> 00:35:02,540
Þar sem þú gætir örugglega
bara keyra forritið ein manneskja er

730
00:35:02,540 --> 00:35:04,980
og telja fjölda sekúndur
það tekur að raða nokkrar tölur,

731
00:35:04,980 --> 00:35:06,710
og þú getur keyrt sum
Forritið hins aðilans

732
00:35:06,710 --> 00:35:08,418
og telja fjölda
um sekúndur sem það tekur.

733
00:35:08,418 --> 00:35:12,840
En þetta er meira almenn leið að
þú getur notað til að greina reiknirit,

734
00:35:12,840 --> 00:35:15,520
ef þú vilt, bara á
pappír eða bara munnlega.

735
00:35:15,520 --> 00:35:18,430
Án þess þó að keyra það, án þess að
jafnvel að reyna sýni inntak,

736
00:35:18,430 --> 00:35:20,180
þú getur bara rökrætt gegnum það.

737
00:35:20,180 --> 00:35:24,670
Og svo með að ráða verktaki eða ef
að hafa hann eða hana svoleiðis að halda því fram við þig

738
00:35:24,670 --> 00:35:28,460
hvers vegna reiknirit þeirra, leyndarmál þeirra
sósa til að leita milljörðum

739
00:35:28,460 --> 00:35:30,580
vefsíðum fyrir þinn
Félagið er betra, þessir

740
00:35:30,580 --> 00:35:33,302
eru konar rök sem þeir
ætti helst að vera fær um að gera.

741
00:35:33,302 --> 00:35:35,010
Eða að minnsta kosti að þetta eru
hvers konar hluti

742
00:35:35,010 --> 00:35:40,211
sem myndi koma upp í umræðu á
amk í mjög formlegum umræðum.

743
00:35:40,211 --> 00:35:40,710
Allt í lagi.

744
00:35:40,710 --> 00:35:44,400
Svo Ben lagt eitthvað
kallaði val tegund.

745
00:35:44,400 --> 00:35:48,200
En ég ætla að leggja til að það er
aðrar leiðir til að gera þetta líka.

746
00:35:48,200 --> 00:35:50,400
Það sem ég gerði í raun ekki eins
um reiknirit Ben er

747
00:35:50,400 --> 00:35:54,400
er að hann hélt gangandi eða
hafa mig ganga, fram og til baka

748
00:35:54,400 --> 00:35:56,930
og fram og til baka og fram og til baka.

749
00:35:56,930 --> 00:36:04,130
Hvað ef í stað ég væri að gera
eitthvað eins og þessar tölur hér

750
00:36:04,130 --> 00:36:08,200
og ég var bara að takast á við hvert
Fjöldi á móti eins og ég gefið henni?

751
00:36:08,200 --> 00:36:10,780
>> Með öðrum orðum, hér er
minn listi af tölum.

752
00:36:10,780 --> 00:36:12,944
Four, einn, þrír, tveir.

753
00:36:12,944 --> 00:36:14,360
Og ég ætla að gera eftirfarandi.

754
00:36:14,360 --> 00:36:17,230
Ég ætla að setja inn tölurnar
þar sem þeir tilheyra frekar

755
00:36:17,230 --> 00:36:18,980
en að velja þá einn í einu.

756
00:36:18,980 --> 00:36:20,820
Með öðrum orðum, hér er númer fjögur.

757
00:36:20,820 --> 00:36:22,430
>> Hér er upprunalega lista minn.

758
00:36:22,430 --> 00:36:25,290
Og ég ætla að halda
í raun nýjan lista hér.

759
00:36:25,290 --> 00:36:26,710
Svo er þetta gamla lista.

760
00:36:26,710 --> 00:36:28,560
Þetta er nýja lista.

761
00:36:28,560 --> 00:36:30,220
Ég sé númer fjögur fyrst.

762
00:36:30,220 --> 00:36:34,500
Ný minn listi er upphaflega tóm,
svo það er trivially raunin

763
00:36:34,500 --> 00:36:36,410
sem fjögur er nú blandað lista.

764
00:36:36,410 --> 00:36:39,560
Ég ætla bara að taka fjölda ég gefið,
og ég ætla að setja það í nýjan listanum mínum.

765
00:36:39,560 --> 00:36:41,460
>> Er þetta nýr listi flokkuð?

766
00:36:41,460 --> 00:36:41,990
Já.

767
00:36:41,990 --> 00:36:45,090
Það er heimskulegt vegna þess að það er bara ein
þáttur, en það er algerlega flokkað.

768
00:36:45,090 --> 00:36:46,390
Það er ekkert af stað.

769
00:36:46,390 --> 00:36:49,290
Það er meira áhugavert, þetta reiknirit,
þegar ég flyt í næsta skref.

770
00:36:49,290 --> 00:36:50,550
>> Nú hef ég einn.

771
00:36:50,550 --> 00:36:55,430
Svo einn, auðvitað, tilheyrir í síðasta
upphafi eða við lok þessarar nýju listanum?

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

773
00:36:56,360 --> 00:36:58,530
Svo ég verð að gera sumir vinna núna.

774
00:36:58,530 --> 00:37:01,410
Ég hef verið að taka nokkrar
frelsi með prjónamerki mitt

775
00:37:01,410 --> 00:37:03,120
bara með því að teikna hluti
þar sem ég vil þá,

776
00:37:03,120 --> 00:37:05,320
en það er í raun ekki
nákvæmur í tölvu.

777
00:37:05,320 --> 00:37:08,530
A tölva, eins og við vitum, hefur
RAM, eða Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
og það er eitt bæti og
annar bæti og annar bæti.

779
00:37:12,411 --> 00:37:14,910
Og ef þú ert með gígabæti af
RAM, hefur þú milljarð bytes,

780
00:37:14,910 --> 00:37:16,680
en þeir eru líkamlega á einum stað.

781
00:37:16,680 --> 00:37:19,540
Þú getur ekki bara að færa efni kring
með því að teikna hana á borð

782
00:37:19,540 --> 00:37:20,750
hvar sem þú vilt.

783
00:37:20,750 --> 00:37:24,090
Svo ef nýr listi mitt hefur
fjórum stöðum í minni,

784
00:37:24,090 --> 00:37:27,480
Því miður er fjögur er
þegar á röngum stað.

785
00:37:27,480 --> 00:37:30,410
>> Svo að setja númer eitt
Ég get ekki bara draga það hér.

786
00:37:30,410 --> 00:37:31,901
Þetta minni staðsetningu er ekki til.

787
00:37:31,901 --> 00:37:35,150
Það væri að svindla, og ég hef verið
svindla á myndrænan í nokkrar mínútur

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

789
00:37:35,800 --> 00:37:40,950
Svo í raun, ef ég vil setja einn hér,
Ég verð að tímabundið afrita fjórum

790
00:37:40,950 --> 00:37:43,030
og þá setja einn þar.

791
00:37:43,030 --> 00:37:45,500
>> Það er allt í lagi, það er rétt,
það er tæknilega mögulegt,

792
00:37:45,500 --> 00:37:48,410
en ljóst að er auka vinna.

793
00:37:48,410 --> 00:37:50,460
Ég vissi ekki bara að setja númerið í stað.

794
00:37:50,460 --> 00:37:53,026
Ég þurfti fyrst að fara á
tala, þá setja það í stað,

795
00:37:53,026 --> 00:37:54,650
svo ég tvöfaldast konar magn mínu starfi.

796
00:37:54,650 --> 00:37:55,660
Svo halda að í huga.

797
00:37:55,660 --> 00:37:57,120
>> En ég er nú búin með þennan þátt.

798
00:37:57,120 --> 00:37:59,056
Nú vil ég að grípa númer þrjú.

799
00:37:59,056 --> 00:38:00,430
Þar sem, að sjálfsögðu, er það tilheyra?

800
00:38:00,430 --> 00:38:01,480
Þar á milli.

801
00:38:01,480 --> 00:38:03,650
Ég get ekki svindla lengur
og bara setja það þar,

802
00:38:03,650 --> 00:38:06,770
vegna þess, aftur, þetta minni
er í líkamlegum stöðum.

803
00:38:06,770 --> 00:38:10,900
Svo ég verð að afrita fjórum
og setja þrjá hérna.

804
00:38:10,900 --> 00:38:11,550
Ekki mikið mál.

805
00:38:11,550 --> 00:38:14,610
Það er bara eitt auka skref
again-- finnst mjög ódýrt.

806
00:38:14,610 --> 00:38:16,445
>> En núna er ég að fara á tveimur.

807
00:38:16,445 --> 00:38:17,820
Tveir, að sjálfsögðu, tilheyrir hér.

808
00:38:17,820 --> 00:38:20,990
Nú getur þú byrjað að sjá hvernig
vinna getur hrannast upp.

809
00:38:20,990 --> 00:38:23,520
Nú hvað þarf ég að gera?

810
00:38:23,520 --> 00:38:28,570
Já, ég verð að færa fjórir,
Ég hef þá að afrita þrjú,

811
00:38:28,570 --> 00:38:31,200
og nú get ég sett tvö.

812
00:38:31,200 --> 00:38:34,460
Og aflinn við þetta
reiknirit, Athyglisvert nóg,

813
00:38:34,460 --> 00:38:41,050
er að gera ráð fyrir að við höfum fleiri Extreme
Málið þar sem það er skulum segja átta, sjö,

814
00:38:41,050 --> 00:38:45,150
sex, fimm, fjórir, þrír, tveir, einn.

815
00:38:45,150 --> 00:38:49,450
Þetta er, í mörgum samhengi,
versta falli,

816
00:38:49,450 --> 00:38:51,570
vegna þess að fjári hlutur
er bókstaflega aftur á bak.

817
00:38:51,570 --> 00:38:53,670
>> Það skiptir í raun ekki
áhrif reiknirit Ben er,

818
00:38:53,670 --> 00:38:55,940
vegna þess að í Ben er val
tegund hann er að fara að halda

819
00:38:55,940 --> 00:38:58,359
fara fram og til baka í gegnum listann.

820
00:38:58,359 --> 00:39:01,150
Og vegna þess að hann var alltaf að leita
í gegnum allt eftir listanum,

821
00:39:01,150 --> 00:39:02,858
það skiptir ekki máli
þar sem þættir eru.

822
00:39:02,858 --> 00:39:05,630
En í þessu tilfelli með því að setja mína
approach-- skulum reyna þetta.

823
00:39:05,630 --> 00:39:08,616
>> Svo einn, tveir, þrír, fjórir,
fimm, sex, sjö, átta.

824
00:39:08,616 --> 00:39:11,630
Einn tveir þrír fjórir,
fimm, sex, sjö, átta.

825
00:39:11,630 --> 00:39:14,320
Ég ætla að taka átta,
og hvar á ég að setja það?

826
00:39:14,320 --> 00:39:17,260
Jæja, í upphafi listanum mínum,
vegna þess að þetta nýja lista er raðað.

827
00:39:17,260 --> 00:39:18,760
Og ég yfir það út.

828
00:39:18,760 --> 00:39:20,551
>> Hvar set ég sjö?

829
00:39:20,551 --> 00:39:21,050
Fjári það.

830
00:39:21,050 --> 00:39:23,174
Það þarf að fara þangað, svo
Ég verð að gera sumir afritun.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Og nú sjö fer hér.

833
00:39:28,480 --> 00:39:29,860
Nú er ég að fara á sex.

834
00:39:29,860 --> 00:39:30,980
Nú er það jafnvel meiri vinna.

835
00:39:30,980 --> 00:39:32,570
>> Átta þarf að fara hér.

836
00:39:32,570 --> 00:39:33,920
Seven þarf að fara hér.

837
00:39:33,920 --> 00:39:35,450
Nú sex hægt að fara hér.

838
00:39:35,450 --> 00:39:37,950
Nú er ég grípa fimm.

839
00:39:37,950 --> 00:39:40,560
Nú hefur átta til að fara
hér sjö þarf að fara hér,

840
00:39:40,560 --> 00:39:43,650
sex þarf að fara hér, og
nú fimm og endurtaka.

841
00:39:43,650 --> 00:39:46,610
Og ég er ansi mikið
færa það stöðugt.

842
00:39:46,610 --> 00:39:52,950
>> Svo í lok, þetta algorithm-- við munum
kalla það innsetning sort-- raun

843
00:39:52,950 --> 00:39:55,020
hefur mikið af vinnu líka.

844
00:39:55,020 --> 00:39:56,970
Það er bara öðruvísi
konar vinnu en Ben er.

845
00:39:56,970 --> 00:40:00,090
verk Bens lét mig fara
fram og til baka allan tímann,

846
00:40:00,090 --> 00:40:03,510
að velja næsta minnstu
frumefni aftur og aftur.

847
00:40:03,510 --> 00:40:06,660
Svo það var þetta mjög sjónræn tagi vinna.

848
00:40:06,660 --> 00:40:10,600
>> Þessi annar reiknirit, sem er enn
correct-- það vilja fá the starf done--

849
00:40:10,600 --> 00:40:12,800
bara breytir magn af vinna.

850
00:40:12,800 --> 00:40:15,420
Það lítur út eins fyrst þú ert
sparnaður, vegna þess að þú ert bara

851
00:40:15,420 --> 00:40:19,190
takast á við hvert frumefni
upp að framan án þess að ganga alla

852
00:40:19,190 --> 00:40:20,930
leið í gegnum listann eins Ben var.

853
00:40:20,930 --> 00:40:25,300
En vandamálið er, sérstaklega í þessum
brjálaður tilfelli þar sem það er allt aftur á bak,

854
00:40:25,300 --> 00:40:27,830
þú ert bara svona
fresta vinnusemi

855
00:40:27,830 --> 00:40:30,360
þangað til þú þarft að festa mistök.

856
00:40:30,360 --> 00:40:33,919
>> Og svo ef þú getur ímyndað þetta
átta og sjö og sex og fimm

857
00:40:33,919 --> 00:40:36,710
og síðar fjórir og þrír og tveir
flytja leið sína í gegnum listann,

858
00:40:36,710 --> 00:40:39,060
við höfum bara breytt
tegund vinnu sem við erum að gera.

859
00:40:39,060 --> 00:40:42,340
Í stað þess að gera það á
upphaf endurtekning minn,

860
00:40:42,340 --> 00:40:45,250
Ég ætla bara að gera það á sem
enda hverjum endurtekning.

861
00:40:45,250 --> 00:40:50,550
Svo kemur í ljós að þetta reiknirit,
of, yfirleitt kölluð innsetning flokka,

862
00:40:50,550 --> 00:40:52,190
er einnig á röð af n veldi.

863
00:40:52,190 --> 00:40:56,480
Það er í raun engin betri,
ekkert betra á öllum.

864
00:40:56,480 --> 00:41:00,810
>> Hins vegar er þriðja nálgun
Ég myndi hvetja okkur til að íhuga,

865
00:41:00,810 --> 00:41:02,970
sem er þetta.

866
00:41:02,970 --> 00:41:07,850
Svo býst listanum mínum, fyrir einfaldleika
aftur, er fjórir, einn, þrír,

867
00:41:07,850 --> 00:41:11,080
two-- bara fjórar tölur.

868
00:41:11,080 --> 00:41:13,300
Ben hafði gott innsæi,
gott mannlegt innsæi

869
00:41:13,300 --> 00:41:16,340
áður, sem við fast allt
listi eventually-- innsetningu konar.

870
00:41:16,340 --> 00:41:18,020
Ég coaxed okkur eftir.

871
00:41:18,020 --> 00:41:22,530
En við skulum íhuga
Einfaldasta leiðin til að laga þennan lista.

872
00:41:22,530 --> 00:41:24,110
>> Þessi listi er ekki raðað.

873
00:41:24,110 --> 00:41:26,130
Hvers vegna?

874
00:41:26,130 --> 00:41:31,920
Á ensku, útskýra hvers vegna
það er í raun ekki raðað.

875
00:41:31,920 --> 00:41:33,400
Hvað þýðir það ekki að vera flokkaður?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: Það er ekki kaflaskipt.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Malan: Ekki myndaröð.

878
00:41:34,990 --> 00:41:35,822
Gefðu mér dæmi.

879
00:41:35,822 --> 00:41:37,180
>> STUDENT: Setjið þá í röð.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Malan: Allt í lagi.

881
00:41:37,440 --> 00:41:38,790
Gefðu mér meira ákveðna dæmi.

882
00:41:38,790 --> 00:41:39,832
>> STUDENT: Hækkandi röð.

883
00:41:39,832 --> 00:41:41,206
DAVID Malan: Ekki hækkandi röð.

884
00:41:41,206 --> 00:41:42,100
Vera nákvæmari.

885
00:41:42,100 --> 00:41:45,190
Ég veit ekki hvað þú átt við með hækkandi.

886
00:41:45,190 --> 00:41:47,150
Hvað er að?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: minnsti
númer er ekki í fyrsta pláss.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Malan: Minnsta númer er
ekki í fyrsta pláss.

889
00:41:51,140 --> 00:41:52,120
Vera nákvæmari.

890
00:41:52,120 --> 00:41:55,000
Ég er farin að veiða á.

891
00:41:55,000 --> 00:41:59,470
Við erum að telja, en
hvað er út af röð hér?

892
00:41:59,470 --> 00:42:00,707
>> STUDENT: Tölulegar röð.

893
00:42:00,707 --> 00:42:02,040
DAVID Malan: Töluleg röð.

894
00:42:02,040 --> 00:42:04,248
Allra konar gæsla
það here-- mjög háu stigi.

895
00:42:04,248 --> 00:42:07,450
Bara bókstaflega segja mér hvað er
rangt eins og fimm ára gamall mætti.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: Plús einn.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Malan: Hvað er það?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: Plús einn.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Malan: Hvað meinarðu plús einn?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Gefðu mér annan fimm ára.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Hvað er rangt, mamma?

904
00:42:18,330 --> 00:42:19,940
Hvað er rangt, pabbi?

905
00:42:19,940 --> 00:42:22,808
Hvað meinarðu þetta er ekki raðað?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: Það er ekki rétti staðurinn.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Malan: Hvað er
ekki á réttum stað?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Four.

909
00:42:26,174 --> 00:42:27,090
DAVID Malan: Allt í lagi, gott.

910
00:42:27,090 --> 00:42:29,110
Svo fjögur er ekki þar sem það ætti að vera.

911
00:42:29,110 --> 00:42:30,590
Einkum er þetta rétt?

912
00:42:30,590 --> 00:42:33,000
Four og einn, fyrstu
tvær tölur sem ég sé.

913
00:42:33,000 --> 00:42:34,930
Er þetta rétt?

914
00:42:34,930 --> 00:42:36,427
Nei, þeir eru út af röð, ekki satt?

915
00:42:36,427 --> 00:42:38,135
Í raun held nú
um tölvu líka.

916
00:42:38,135 --> 00:42:40,824
Það getur aðeins að líta á kannski einn,
kannski tvennt á once--

917
00:42:40,824 --> 00:42:43,240
og í raun aðeins eitt
í einu, en það getur að minnsta kosti

918
00:42:43,240 --> 00:42:45,790
líta á eitt þá
Næsta hlutur við hliðina á henni.

919
00:42:45,790 --> 00:42:47,380
>> Svo eru þessir í röð?

920
00:42:47,380 --> 00:42:48,032
Auðvitað ekki.

921
00:42:48,032 --> 00:42:48,740
Svo þú veist hvað?

922
00:42:48,740 --> 00:42:51,020
Hvers vegna eigum við ekki að taka barnið
skref ákveða þetta vandamál

923
00:42:51,020 --> 00:42:53,410
í stað þess að gera þessar ímynda
reiknirit eins Ben, þar

924
00:42:53,410 --> 00:42:56,440
hann er svona að ákveða það með
lykkja í gegnum listann

925
00:42:56,440 --> 00:42:59,670
í stað þess að gera það sem ég gerði, þar sem
Ég fastur bara svona það sem við förum?

926
00:42:59,670 --> 00:43:03,650
Við skulum bara bókstaflega brjóta niður
Hugtakið order-- töluröð,

927
00:43:03,650 --> 00:43:06,990
kalla það hvað sem þú want--
í þessum parasamanburður.

928
00:43:06,990 --> 00:43:07,590
>> Four og einn.

929
00:43:07,590 --> 00:43:09,970
Er þetta rétt röð?

930
00:43:09,970 --> 00:43:11,310
Svo skulum laga það.

931
00:43:11,310 --> 00:43:14,700
Einn og fjórir, og þá
við verðum bara að afrita það.

932
00:43:14,700 --> 00:43:15,560
Allt í lagi, gott.

933
00:43:15,560 --> 00:43:17,022
Ég fastur einn og fjórir.

934
00:43:17,022 --> 00:43:18,320
Þrír og tveir?

935
00:43:18,320 --> 00:43:18,820
Nei

936
00:43:18,820 --> 00:43:21,690
Látum orð mín passa fingur mína.

937
00:43:21,690 --> 00:43:23,695
Four og þremur?

938
00:43:23,695 --> 00:43:27,930
>> Það er ekki í röð, þannig að ég ætla
að gera eitt, þrír, fjórir, tveir.

939
00:43:27,930 --> 00:43:28,680
Allt í lagi gott.

940
00:43:28,680 --> 00:43:32,310
Nú fjórum og tveimur?

941
00:43:32,310 --> 00:43:33,370
Við þurfum að laga þetta líka.

942
00:43:33,370 --> 00:43:36,700
Svo einn, þrír, tveir, fjórir.

943
00:43:36,700 --> 00:43:39,820
Svo er það flokkað?

944
00:43:39,820 --> 00:43:43,170
Nei, en það er nær flokkað?

945
00:43:43,170 --> 00:43:48,930
>> Það er, vegna þess að við fastur þetta
mistök, fast við þetta mistök,

946
00:43:48,930 --> 00:43:50,370
og við fast þetta mistök.

947
00:43:50,370 --> 00:43:52,420
Þannig að við fast þrjár mistök að öllum líkindum.

948
00:43:52,420 --> 00:43:58,100
Enn er í raun ekki líta raðað, en
það er hlutlægt nær að raðað

949
00:43:58,100 --> 00:44:00,080
vegna þess að við fast sum þessara mistökum.

950
00:44:00,080 --> 00:44:02,047
>> Nú hvað á ég að gera næst?

951
00:44:02,047 --> 00:44:03,630
Ég náði konar enda á listanum.

952
00:44:03,630 --> 00:44:05,680
Ég virtist hafa fasta
allir mistök, en nei.

953
00:44:05,680 --> 00:44:08,510
Vegna þess að í þessu tilfelli, nokkrar tölur
gæti hafa loftbólum í upp nær

954
00:44:08,510 --> 00:44:10,410
að aðrar tölur sem
eru enn út af röð.

955
00:44:10,410 --> 00:44:12,951
Svo skulum gera það aftur, og ég ætla
bara gera það í stað að þessu sinni.

956
00:44:12,951 --> 00:44:14,170
Einn og þremur?

957
00:44:14,170 --> 00:44:14,720
Það er fínt.

958
00:44:14,720 --> 00:44:16,070
Þrír og tveir?

959
00:44:16,070 --> 00:44:17,560
Auðvitað ekki, þannig að við skulum breyta því.

960
00:44:17,560 --> 00:44:19,160
Svo tveir, þrír.

961
00:44:19,160 --> 00:44:21,340
Þrír og fjórir?

962
00:44:21,340 --> 00:44:24,370
Og nú skulum bara vera
sérstaklega smámunasamur hér.

963
00:44:24,370 --> 00:44:26,350
Er það flokkað?

964
00:44:26,350 --> 00:44:29,280
Þú menn vita að það er flokkað.

965
00:44:29,280 --> 00:44:30,400
>> Ég ætti að reyna aftur.

966
00:44:30,400 --> 00:44:31,900
Svo Olivia er að leggja ég að reyna aftur.

967
00:44:31,900 --> 00:44:32,530
Hvers vegna?

968
00:44:32,530 --> 00:44:35,810
Vegna þess að tölvan er ekki með
lúxus manna augum okkar

969
00:44:35,810 --> 00:44:38,080
á bara glancing back-- lagi, ég er búin.

970
00:44:38,080 --> 00:44:41,610
Hvernig virkar tölvan ákveða
að listinn er nú flokkaður?

971
00:44:41,610 --> 00:44:44,590
Vélrænt.

972
00:44:44,590 --> 00:44:47,650
>> Ég ætti að fara í gegnum
einu sinni enn, og aðeins ef ég

973
00:44:47,650 --> 00:44:51,190
ekki gera / finna einhver mistök get ég
þá gera eins og the tölva, jebb,

974
00:44:51,190 --> 00:44:51,980
við erum gott að fara.

975
00:44:51,980 --> 00:44:54,850
Svo einn og tveir, tveir og
þrír, þrír og fjórir.

976
00:44:54,850 --> 00:44:58,030
Nú get ég endanlega segja að þetta er
flokkað, því ég gerði engar breytingar.

977
00:44:58,030 --> 00:45:01,940
Nú það væri padda og bara
heimska ef ég, tölvan,

978
00:45:01,940 --> 00:45:05,640
spurði sömu spurninga aftur
búast við mismunandi svör.

979
00:45:05,640 --> 00:45:07,110
Ætti ekki að gerast.

980
00:45:07,110 --> 00:45:08,600
>> Og svo nú listinn er raðað.

981
00:45:08,600 --> 00:45:12,630
Því miður, hlaupandi tími
þetta reiknirit er einnig n veldi.

982
00:45:12,630 --> 00:45:13,130
Hvers vegna?

983
00:45:13,130 --> 00:45:19,520
Þar sem þú hefur n tölur, og í
versta tilfelli þú þarft að færa n tölur

984
00:45:19,520 --> 00:45:23,637
n sinnum vegna þess að þú þarft að halda áfram
baka til að athuga og hugsanlega festa

985
00:45:23,637 --> 00:45:24,220
þessar tölur.

986
00:45:24,220 --> 00:45:26,280
Og við getum gert meira
formleg greining líka.

987
00:45:26,280 --> 00:45:29,530
>> Svo er þetta allt að segja að við höfum tekið
þrjár mismunandi aðferðir, einn

988
00:45:29,530 --> 00:45:32,210
þeirra strax innsæi
the kylfa frá Ben

989
00:45:32,210 --> 00:45:35,170
að leiðbeinandi innsetningu minn
tegund í þessu einn

990
00:45:35,170 --> 00:45:38,540
þar sem þú missir konar sjónar á
skógurinn fyrir trjánum í upphafi.

991
00:45:38,540 --> 00:45:41,760
En svo ef þú tekur skref til baka,
Voila, höfum við fast í flokkun hugmynd.

992
00:45:41,760 --> 00:45:43,824
Þannig að þetta er, þora að segja,
lægra verði kannski

993
00:45:43,824 --> 00:45:45,740
en sumir af þeim annað
reiknirit, en við skulum

994
00:45:45,740 --> 00:45:48,550
sjá hvort við getum ekki sjón
þetta með því að þetta.

995
00:45:48,550 --> 00:45:51,450
>> Svo er þetta sumir ágætur
Hugbúnaðurinn sem einhver

996
00:45:51,450 --> 00:45:56,110
skrifaði nota litrík bars sem er
fara að gera eftirfarandi fyrir okkur.

997
00:45:56,110 --> 00:45:57,736
Hver af þessum börum táknar fjölda.

998
00:45:57,736 --> 00:46:00,026
Hærri bar, stærri
fjöldi, minni bar,

999
00:46:00,026 --> 00:46:00,990
minni númer.

1000
00:46:00,990 --> 00:46:05,880
Svo fullkomlega við viljum gott pýramída
þar sem það byrjar lítill og fær stór,

1001
00:46:05,880 --> 00:46:08,330
og sem myndi þýða að
þessi barir eru flokkuð.

1002
00:46:08,330 --> 00:46:11,200
Þannig að ég ætla að fara á undan og velja,
til dæmis, reiknirit Bens

1003
00:46:11,200 --> 00:46:13,990
first-- val tegund.

1004
00:46:13,990 --> 00:46:16,220
>> Og taka eftir hvað það er að gera.

1005
00:46:16,220 --> 00:46:18,670
Leiðin sem þeir hafa kosið að
sjón þessa reiknirit

1006
00:46:18,670 --> 00:46:22,090
er það bara eins og ég var
að ganga í gegnum listann minn,

1007
00:46:22,090 --> 00:46:24,710
þetta forrit er að ganga
gegnum lista með tölum,

1008
00:46:24,710 --> 00:46:28,160
undirstrika í bleiku hverju
tala sem það er að horfa á.

1009
00:46:28,160 --> 00:46:32,360
Og hvað er að gerast núna?

1010
00:46:32,360 --> 00:46:35,154
>> Minnsti fjöldi sem
Ég eða Ben fann skyndilega

1011
00:46:35,154 --> 00:46:36,820
fær flutt til the byrjun af listanum.

1012
00:46:36,820 --> 00:46:40,037
Og eftir að þeir gerðu evict
fjöldi sem var þarna,

1013
00:46:40,037 --> 00:46:41,120
og það er fullkomlega í lagi.

1014
00:46:41,120 --> 00:46:42,600
Ég vissi ekki að fá inn í þessi stigi smáatriðum.

1015
00:46:42,600 --> 00:46:44,308
En við þurfum að setja
að tala einhvers staðar,

1016
00:46:44,308 --> 00:46:47,775
þannig að við fluttum bara það til
opinn blettur sem var búin til.

1017
00:46:47,775 --> 00:46:49,900
Þannig að ég ætla að flýta þessu
upp, því annars

1018
00:46:49,900 --> 00:46:51,871
verður mjög leiðinlegur fljótt.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Fjör speed-- þar sem við förum.

1021
00:46:58,600 --> 00:47:01,850
Svo nú sama lögmál
Ég var að sækja um, en þú

1022
00:47:01,850 --> 00:47:06,540
getur byrjað að líða reiknirit, ef þú
mun, eða sjá það svolítið betur.

1023
00:47:06,540 --> 00:47:13,190
Og þetta reiknirit hefur þau áhrif að
velja næsta minnstu frumefni,

1024
00:47:13,190 --> 00:47:16,422
svo þú ert að fara að byrja að
sjá það pallinum upp á vinstri.

1025
00:47:16,422 --> 00:47:19,130
Og á hverjum endurtekning, eins og ég
lagt, er það smá minni vinna.

1026
00:47:19,130 --> 00:47:21,921
Það þarf ekki að fara alla leið
aftur til vinstri lok lista,

1027
00:47:21,921 --> 00:47:23,900
vegna þess að það sem þegar
þekkir þá eru flokkuð.

1028
00:47:23,900 --> 00:47:28,129
Svo mér finnst svona eins og það er
hraða, jafnvel þótt hvert skref er

1029
00:47:28,129 --> 00:47:29,420
taka sama magn af tíma.

1030
00:47:29,420 --> 00:47:31,600
Það er bara færri skrefum eftir.

1031
00:47:31,600 --> 00:47:35,240
Og nú þú getur konar finnst
reiknirit þrífa upp endann á henni,

1032
00:47:35,240 --> 00:47:37,040
og reyndar nú er flokkað.

1033
00:47:37,040 --> 00:47:41,620
>> Svo er allt gert innsetning tegund.

1034
00:47:41,620 --> 00:47:43,600
Ég þarf að koma aftur randomize fylkisins.

1035
00:47:43,600 --> 00:47:45,940
Og eftir ég get bara
halda Randomizing henni,

1036
00:47:45,940 --> 00:47:50,630
og við munum fá nálgun á
sama aðferð, innsetning flokka.

1037
00:47:50,630 --> 00:47:55,050
Leyfðu mér að hægja hann niður til hér.

1038
00:47:55,050 --> 00:47:56,915
Við skulum byrja að yfir.

1039
00:47:56,915 --> 00:47:57,414
Hætta.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Við skulum sleppa fjórir.

1042
00:48:02,410 --> 00:48:03,200
Þar sem við förum.

1043
00:48:03,200 --> 00:48:04,190
Randomize array þeir.

1044
00:48:04,190 --> 00:48:05,555
Og hér erum við go-- innsetningu konar.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Spila.

1047
00:48:12,800 --> 00:48:17,280
Takið eftir að það er að fást við hverju
þáttur það kynni strax,

1048
00:48:17,280 --> 00:48:20,282
en ef það tilheyrir
rangur staður tilkynningu

1049
00:48:20,282 --> 00:48:21,740
alla vinnu sem þarf að gerast.

1050
00:48:21,740 --> 00:48:24,700
Við verðum að halda breytast meira
og fleiri þætti til að búa til pláss

1051
00:48:24,700 --> 00:48:27,340
fyrir einn við viljum setja í stað.

1052
00:48:27,340 --> 00:48:30,740
>> Þannig að við erum með áherslu á
vinstri enda aðeins listanum.

1053
00:48:30,740 --> 00:48:34,460
Taka við höfum ekki einu sinni litið at-- vér
hafa ekki lögð áhersla á bleiku neinu

1054
00:48:34,460 --> 00:48:35,610
til hægri.

1055
00:48:35,610 --> 00:48:38,180
Við erum bara að fást við
vandamálin sem við förum,

1056
00:48:38,180 --> 00:48:40,430
en við erum að búa til mikið af
vinna fyrir okkur enn.

1057
00:48:40,430 --> 00:48:44,410
Og svo ef við flýta þessu upp
nú að fara að ljúka,

1058
00:48:44,410 --> 00:48:46,210
það hefur mismunandi feel til það örugglega.

1059
00:48:46,210 --> 00:48:50,150
Það er bara að einblína á vinstri enda en
gera smá meiri vinnu sem needed--

1060
00:48:50,150 --> 00:48:53,230
konar refur hlutum
yfir, ákveða hlutina,

1061
00:48:53,230 --> 00:48:58,350
en fást að lokum með
hver þáttur einn í einu

1062
00:48:58,350 --> 00:49:07,740
þar til við fáum að the-- vel, við
Allir vita hvernig þetta er að fara að enda,

1063
00:49:07,740 --> 00:49:09,700
svo það er lítið underwhelming kannski.

1064
00:49:09,700 --> 00:49:12,830
>> En listinn í end--
spoiler-- er að fara að vera flokkaður.

1065
00:49:12,830 --> 00:49:15,300
Svo skulum líta á eitt síðasta.

1066
00:49:15,300 --> 00:49:16,840
Við getum ekki bara sleppa því núna.

1067
00:49:16,840 --> 00:49:18,000
Við erum næstum þarna.

1068
00:49:18,000 --> 00:49:19,980
Tveir til að fara, einn að fara.

1069
00:49:19,980 --> 00:49:22,680
Og voila.

1070
00:49:22,680 --> 00:49:23,450
Excellent.

1071
00:49:23,450 --> 00:49:27,220
>> Svo nú skulum gera eitt síðasta einn,
aftur Randomizing með kúla tagi.

1072
00:49:27,220 --> 00:49:31,690
Og eftir hér, sérstaklega ef ég hægja hana
niður, þetta er að halda swooping gegnum.

1073
00:49:31,690 --> 00:49:36,830
En eftir það gerir bara pöruðum
comparisons-- konar staðbundnar lausnir.

1074
00:49:36,830 --> 00:49:39,050
En um leið og við komum til
í lok listanum í bleikur,

1075
00:49:39,050 --> 00:49:40,690
hvað er að fara að þurfa að gerast aftur?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Já, það er að fara að þurfa að
start over, vegna þess að það bara

1078
00:49:46,830 --> 00:49:49,870
fastur parasamanburður mistök.

1079
00:49:49,870 --> 00:49:53,120
Og það gæti hafa leitt í ljós enn aðra.

1080
00:49:53,120 --> 00:49:58,950
Og svo ef þú flýta þessu upp, þú munt
sjá að mikið eins og nafnið gefur til kynna,

1081
00:49:58,950 --> 00:50:01,870
minni elements-- eða öllu heldur,
stærri elements-- eru farin

1082
00:50:01,870 --> 00:50:03,740
að kúla upp til the toppur, ef þú vilt.

1083
00:50:03,740 --> 00:50:07,380
Og smærri þættir eru
byrja að kúla niður til vinstri.

1084
00:50:07,380 --> 00:50:10,780
Og reyndar, það er góður af
sjónræn áhrif eins og heilbrigður.

1085
00:50:10,780 --> 00:50:17,150
Og svo þetta mun enda upp klára
á mjög svipaðan hátt líka.

1086
00:50:17,150 --> 00:50:19,160
>> Við þurfum ekki að búa
á þessu tiltekna einn.

1087
00:50:19,160 --> 00:50:21,010
Leyfðu mér að opna þetta núna líka.

1088
00:50:21,010 --> 00:50:24,040
Það er nokkrar aðrar flokkun reiknirit
í heiminum, nokkrar sem

1089
00:50:24,040 --> 00:50:25,580
eru teknar hér.

1090
00:50:25,580 --> 00:50:29,960
Og sérstaklega fyrir nemendur sem eru ekki
endilega sjón eða stærðfræði,

1091
00:50:29,960 --> 00:50:31,930
eins og við gerðum áður, við getum
einnig að gera þetta audially

1092
00:50:31,930 --> 00:50:34,210
Ef við tengjum hljóð með þetta.

1093
00:50:34,210 --> 00:50:36,990
Og bara til gamans, hér er
nokkrar mismunandi reiknirit,

1094
00:50:36,990 --> 00:50:40,950
og einn af þeim í lagi að þú ert
fara til tilkynningar er kallað "Mergesort."

1095
00:50:40,950 --> 00:50:43,250
>> Það er í raun í grundvallaratriðum
betri reiknirit,

1096
00:50:43,250 --> 00:50:45,860
þannig að Mergesort, einn af
þær sem þú ert að fara að sjá,

1097
00:50:45,860 --> 00:50:49,170
er ekki röð n veldi.

1098
00:50:49,170 --> 00:50:57,280
Það er á röð af n sinnum lóg af
n, sem er í raun minni og svona

1099
00:50:57,280 --> 00:50:58,940
hraðar en þeim hinum þremur.

1100
00:50:58,940 --> 00:51:00,670
Og það er a par annar
kjánalegt þau sem við munum sjá.

1101
00:51:00,670 --> 00:51:01,933
>> Svo hér við fara með einhverjum hljóð.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Þetta er innsetning tegund, svo aftur
það er bara að takast á við þá þætti

1104
00:51:10,490 --> 00:51:13,420
eins og þeir koma.

1105
00:51:13,420 --> 00:51:17,180
Þetta er kúla tegund, þannig að það er
miðað við þá pör í einu.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Og aftur, stærsta þættir
eru freyðandi upp á toppinn.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Næst val tagi.

1110
00:51:41,710 --> 00:51:45,420
Þetta er reiknirit Bens, þar
aftur hann er að velja iteratively

1111
00:51:45,420 --> 00:51:46,843
næsta minnstu þáttur.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Og aftur, nú þú geta raunverulega heyra að
það er hraðakstur upp en aðeins að því marki

1114
00:51:53,900 --> 00:51:58,230
eins og það er að gera minna og minna
vinna á hverri ítrun.

1115
00:51:58,230 --> 00:52:04,170
Þetta er hraðari einn, Mergesort,
sem er flokkun klasa af tölum

1116
00:52:04,170 --> 00:52:05,971
saman og þá sameina þá.

1117
00:52:05,971 --> 00:52:07,720
Svo look-- vinstri
helmingur er þegar raðað.

1118
00:52:07,720 --> 00:52:14,165
>> Nú það er að flokka rétt helminginn, og
nú það er að fara að sameina þær í eina.

1119
00:52:14,165 --> 00:52:19,160
Þetta er eitthvað sem kallast "Gnome tegund."

1120
00:52:19,160 --> 00:52:23,460
Og þú getur konar séð það
það er að fara fram og til baka,

1121
00:52:23,460 --> 00:52:27,950
ákveða að vinna svolítið hér og
það áður en það gengur til nýja vinnu.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Og það er það.

1124
00:52:33,692 --> 00:52:36,400
Það er annar tegund, sem er
í raun bara fyrir fræðilegum tilgangi,

1125
00:52:36,400 --> 00:52:40,980
kallað "heimskur tegund", sem tekur
gögn, raðar því af handahófi,

1126
00:52:40,980 --> 00:52:43,350
og þá athugar hvort það er flokkað.

1127
00:52:43,350 --> 00:52:47,880
Og ef það er ekki, aftur skiptir það það
handahófi, tékka ef það er raðað,

1128
00:52:47,880 --> 00:52:49,440
og ef ekki endurtekur.

1129
00:52:49,440 --> 00:52:52,660
Og í orði, probabilistically
þetta mun ljúka,

1130
00:52:52,660 --> 00:52:54,140
en eftir töluvert af tíma.

1131
00:52:54,140 --> 00:52:56,930
Það er ekki mest
duglegur reiknirit.

1132
00:52:56,930 --> 00:53:02,550
Svo einhverjar spurningar um þá
sérstaklega reiknirit eða eitthvað

1133
00:53:02,550 --> 00:53:04,720
tengist það líka?

1134
00:53:04,720 --> 00:53:09,430
>> Jæja, við skulum nú stríða sundur hvað allt
þessar línur eru sem ég hef verið að teikna

1135
00:53:09,430 --> 00:53:15,090
og það sem ég er hrokafullur tölvuna
getur gert undir hetta.

1136
00:53:15,090 --> 00:53:18,650
Ég myndi halda því fram að allar þessar tölur
Ég að halda samningu þeir þurfa að fá

1137
00:53:18,650 --> 00:53:21,330
geymdar einhvers staðar í minni.

1138
00:53:21,330 --> 00:53:24,130
Við munum losna við þennan gaur núna, líka.

1139
00:53:24,130 --> 00:53:30,110
>> Svo a stykki af minni í
computer-- svo RAM DIMM er

1140
00:53:30,110 --> 00:53:35,480
hvað við leitað gær, tvískiptur
inline minni module-- lítur svona út.

1141
00:53:35,480 --> 00:53:39,370
Og hver af þessum litlu svörtu flögum
er einhver fjöldi bytes, yfirleitt.

1142
00:53:39,370 --> 00:53:44,380
Og þá gull prjónar eru eins og
vír sem tengja það við tölvuna,

1143
00:53:44,380 --> 00:53:47,521
og græna sílikon borð er bara
hvað heldur allt allt saman.

1144
00:53:47,521 --> 00:53:48,770
Svo hvað þýðir þetta í raun?

1145
00:53:48,770 --> 00:53:53,180
Ef ég teikna svona þetta sama mynd,
við skulum gera ráð fyrir einfaldleika

1146
00:53:53,180 --> 00:53:55,280
að þetta DIMM, tvískiptur
inline minni mát,

1147
00:53:55,280 --> 00:54:00,530
er einn gígabæti af RAM, einn gígabæti af
minni, sem er hversu margir bæti alls?

1148
00:54:00,530 --> 00:54:02,100
Einn gígabæti er hversu margir bæti?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Meira en það.

1151
00:54:06,030 --> 00:54:09,960
1124 er kíló, 1.000.

1152
00:54:09,960 --> 00:54:11,730
Mega er ein milljón.

1153
00:54:11,730 --> 00:54:14,570
Giga er milljarð.

1154
00:54:14,570 --> 00:54:15,070
>> Er ég að ljúga?

1155
00:54:15,070 --> 00:54:16,670
Getum við lesið jafnvel merkið?

1156
00:54:16,670 --> 00:54:19,920
Þetta er í raun 128
gígabæta, svo það er meira.

1157
00:54:19,920 --> 00:54:22,130
En við munum láta þetta
er bara einn gígabæti.

1158
00:54:22,130 --> 00:54:25,640
Svo það þýðir að það er milljarður
bæti af minni í boði fyrir mig

1159
00:54:25,640 --> 00:54:29,770
eða 8 milljarðar bitar, en við erum að fara
að tala í skilmálar af bæti nú,

1160
00:54:29,770 --> 00:54:30,750
halda áfram.

1161
00:54:30,750 --> 00:54:36,330
>> Svo hvað það þýðir er að þetta er
eitt bæti, þetta er annar bæti,

1162
00:54:36,330 --> 00:54:38,680
þetta er annar bæti,
og ef við vildum virkilega

1163
00:54:38,680 --> 00:54:43,280
til að vera nákvæm við yrðum að
draga milljarð litla ferninga.

1164
00:54:43,280 --> 00:54:44,320
En hvað þýðir það?

1165
00:54:44,320 --> 00:54:46,420
Jæja, láttu mig súmma bara
í á þessari mynd.

1166
00:54:46,420 --> 00:54:50,900
Ef ég hef eitthvað sem lítur
svona nú, það er fjögur bæti.

1167
00:54:50,900 --> 00:54:53,710
>> Og svo ég gæti sett fjórar tölur hér.

1168
00:54:53,710 --> 00:54:54,990
Einn tveir þrír fjórir.

1169
00:54:54,990 --> 00:55:00,170
Eða ég gæti sett fjögur bréf eða tákn.

1170
00:55:00,170 --> 00:55:02,620
"Hey!" gæti farið þarna,
því að hver af bréfum,

1171
00:55:02,620 --> 00:55:04,370
við ræddum áðan,
mætti ​​fulltrúa

1172
00:55:04,370 --> 00:55:06,650
með átta bitum eða ASCII eða bæti.

1173
00:55:06,650 --> 00:55:09,370
Svo í öðrum orðum, getur þú
setja 8 milljarða hlutina inni

1174
00:55:09,370 --> 00:55:11,137
af þessum eina staf minni.

1175
00:55:11,137 --> 00:55:14,345
Nú hvað þýðir það að setja hlutina aftur
til baka til baka í minni svona?

1176
00:55:14,345 --> 00:55:17,330
Þetta er það sem forritari
myndi kalla "fylki".

1177
00:55:17,330 --> 00:55:21,250
Í tölvuforriti, finnst þér ekki
um undirliggjandi vélbúnaður, í sjálfu sér.

1178
00:55:21,250 --> 00:55:24,427
Þú heldur bara um sjálfan þig og að hafa
aðgangur að milljarð bytes samtals,

1179
00:55:24,427 --> 00:55:26,010
og þú getur allt sem þú vilt með það.

1180
00:55:26,010 --> 00:55:27,880
En fyrir þægindi
það er yfirleitt gagnlegt

1181
00:55:27,880 --> 00:55:31,202
að halda minni þitt rétt
við hliðina á hvort öðru eins og þetta.

1182
00:55:31,202 --> 00:55:33,660
Þannig að ef ég súmma inn á this--
vegna þess að við erum vissulega ekki að fara

1183
00:55:33,660 --> 00:55:39,310
að draga milljarð smá squares--
skulum gera ráð fyrir að þetta borð táknar

1184
00:55:39,310 --> 00:55:40,610
að standa af minni núna.

1185
00:55:40,610 --> 00:55:43,800
Og ég ætla bara að teikna eins og margir eins minn
merki endar gefa mig hér.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Svo nú höfum spýtu
minni á borð

1188
00:55:52,300 --> 00:55:56,400
sem fékk einn, tveir, þrír, fjórir, fimm,
sex, einn, tveir, þrír, fjórir, fimm, sex,

1189
00:55:56,400 --> 00:56:01,130
seven-- svo 42 bæti af
minni á samtals skjánum.

1190
00:56:01,130 --> 00:56:01,630
Þakka þér.

1191
00:56:01,630 --> 00:56:02,838
Já, gerði tölur minn rétt.

1192
00:56:02,838 --> 00:56:05,120
Svo 42 bæti af minni hér.

1193
00:56:05,120 --> 00:56:06,660
Svo hvað þýðir þetta í raun þýtt?

1194
00:56:06,660 --> 00:56:09,830
Jæja, tölva forritari
myndi reyndar almennt

1195
00:56:09,830 --> 00:56:12,450
hugsa um þetta minni sem addressable.

1196
00:56:12,450 --> 00:56:16,630
Með öðrum orðum, hver og einn af þessum
stöðum í minni, í vélbúnaði,

1197
00:56:16,630 --> 00:56:18,030
hefur einstakt tölu.

1198
00:56:18,030 --> 00:56:22,020
>> Það er ekki eins flókið eins og eitt BRATTLE
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Þess í stað, það er bara tala.

1200
00:56:23,830 --> 00:56:27,930
Þetta er bæti númer núll, þetta er
einn, þetta er tveir, þetta er þrír,

1201
00:56:27,930 --> 00:56:30,327
og þetta er 41.

1202
00:56:30,327 --> 00:56:30,910
Bíddu aðeins.

1203
00:56:30,910 --> 00:56:32,510
Ég hélt að ég sagði 42 í smá stund síðan.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Ég byrjaði að telja á núlli,
svo það er í raun rétt.

1206
00:56:37,772 --> 00:56:40,980
Nú erum við ekki að í raun draga það
sem rist, og ef þú draga það sem rist

1207
00:56:40,980 --> 00:56:43,520
Ég held að það í raun og veru
fá dálítið villandi.

1208
00:56:43,520 --> 00:56:46,650
Hvað forritari myndi,
í hans eða hennar eigin huga,

1209
00:56:46,650 --> 00:56:50,310
almennt hugsa um þetta
minni sem er bara eins og borði,

1210
00:56:50,310 --> 00:56:53,340
eins og a stykki af gríma borði
sem bara fer á og á eilífu

1211
00:56:53,340 --> 00:56:54,980
eða þar til þú keyrir út af minni.

1212
00:56:54,980 --> 00:56:59,200
Svo algengari leið til að vekja
og hugsa bara um minni

1213
00:56:59,200 --> 00:57:03,710
væri verið að þetta sé bæti núll, einn,
tveir, þrír, og þá punktur, punktur, punktur.

1214
00:57:03,710 --> 00:57:07,650
Og þú ert 42 slíkar bytes alls, jafnvel
þó líkamlega það gæti í raun og veru

1215
00:57:07,650 --> 00:57:09,480
vera eitthvað meira svona.

1216
00:57:09,480 --> 00:57:12,850
>> Svo ef þú heldur nú af þinn
minni eins og þetta, rétt eins og borði,

1217
00:57:12,850 --> 00:57:17,640
þetta er það sem forritari aftur
myndi kalla á fjölbreytta minni.

1218
00:57:17,640 --> 00:57:20,660
Og þegar þú vilt í raun og veru að geyma
eitthvað í minni tölvu,

1219
00:57:20,660 --> 00:57:23,290
þú gerir venjulega geyma hluti
bak-til-bak við bak-til-bak.

1220
00:57:23,290 --> 00:57:25,010
Þannig að við höfum verið að tala um tölur.

1221
00:57:25,010 --> 00:57:30,880
Og þegar ég vildi til að leysa vandamál
eins og fjögurra, einn, þrír, tveir,

1222
00:57:30,880 --> 00:57:33,820
jafnvel þótt ég var bara að teikna
aðeins tölurnar fjögur, einn, þrír,

1223
00:57:33,820 --> 00:57:39,490
tveir á borð, tölvan myndi
í raun hafa þetta skipulag í minni.

1224
00:57:39,490 --> 00:57:43,347
>> Og hvað væri við hliðina á
tvær í minni tölvunnar?

1225
00:57:43,347 --> 00:57:44,680
Jæja, það er ekkert svar við því.

1226
00:57:44,680 --> 00:57:45,770
Við í raun ekki vita.

1227
00:57:45,770 --> 00:57:48,200
Og svo lengi sem
tölva hjartarskinn ekki þurfa það,

1228
00:57:48,200 --> 00:57:51,440
það þarf ekki að hugsa hvað er næst
að tölurnar það gerir sama um.

1229
00:57:51,440 --> 00:57:55,130
Og þegar ég sagði áðan að tölvu
getur aðeins líta á eitt netfang í einu,

1230
00:57:55,130 --> 00:57:56,170
þetta er góður af hverju.

1231
00:57:56,170 --> 00:57:59,490
>> Ekki ólíkt met
leikmaður og lestur höfuð

1232
00:57:59,490 --> 00:58:03,030
aðeins að vera fær um að líta á ákveðin
gróp í líkamlegu gamla skólann met

1233
00:58:03,030 --> 00:58:06,500
í einu, álíka
getur tölvan takk

1234
00:58:06,500 --> 00:58:09,810
CPU hennar og þess
Intel kennsla setja,

1235
00:58:09,810 --> 00:58:12,480
meðal hverra kennsla
er að lesa úr minni

1236
00:58:12,480 --> 00:58:15,590
eða spara til memory-- a
tölva getur aðeins líta

1237
00:58:15,590 --> 00:58:19,210
á einum stað í time--
stundum a samsetning af þeim,

1238
00:58:19,210 --> 00:58:21,770
en í raun bara einn stað í einu.

1239
00:58:21,770 --> 00:58:24,770
Svo þegar við vorum að gera
þessi mismunandi reiknirit,

1240
00:58:24,770 --> 00:58:28,110
Ég er ekki bara að skrifa í
vacuum-- fjórir, einn, þrír, tveir.

1241
00:58:28,110 --> 00:58:30,849
Þær tölur tilheyra í raun
einhvers staðar líkamlega í minni.

1242
00:58:30,849 --> 00:58:32,890
Þannig að það eru pínulítill lítill
smári eða einhvers konar

1243
00:58:32,890 --> 00:58:35,840
rafeindatækni undir
hetta geyma þessi gildi.

1244
00:58:35,840 --> 00:58:40,460
>> Og í heild, eru hvernig margir bitar
þátt núna, bara að vera skýr?

1245
00:58:40,460 --> 00:58:45,580
Svo er þetta fjögur bæti, eða
nú er það 32 bita alls.

1246
00:58:45,580 --> 00:58:49,280
Þannig að það eru í raun 32 núll og
Þeir semja þessum fjórum hlutum.

1247
00:58:49,280 --> 00:58:52,070
Það er jafnvel meira hérna, en
aftur við ekki sama um það.

1248
00:58:52,070 --> 00:58:55,120
>> Svo nú skulum spyrja annan
spurning með minni,

1249
00:58:55,120 --> 00:58:57,519
vegna þess að að í lok
dagsins er í dreifni.

1250
00:58:57,519 --> 00:59:00,310
Sama hvað við gætum gert með
tölva, í lok dags

1251
00:59:00,310 --> 00:59:02,560
vélbúnaður er enn
Sama undir hetta.

1252
00:59:02,560 --> 00:59:04,670
Hvernig myndi ég geyma orð hér?

1253
00:59:04,670 --> 00:59:09,710
Jæja, orð í tölvu eins og
"Hey!" væri hægt að geyma bara svona.

1254
00:59:09,710 --> 00:59:12,300
Og ef þú vildir vera lengur
orð, þú getur einfaldlega

1255
00:59:12,300 --> 00:59:19,120
skrifa það og segja eitthvað
eins og "halló" og geyma það hér.

1256
00:59:19,120 --> 00:59:23,930
>> Og svo hér líka, þetta contiguousness
er í raun kostur,

1257
00:59:23,930 --> 00:59:26,530
vegna þess að tölva getur bara
lesa frá hægri til vinstri.

1258
00:59:26,530 --> 00:59:28,680
En hér er spurning.

1259
00:59:28,680 --> 00:59:33,480
Í tengslum við þetta orð,
H-e-L-L-o, upphrópunarmerki,

1260
00:59:33,480 --> 00:59:38,740
hvernig gæti tölvan vita hvar
Bæta hefst og þar sem orðið endar?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Í tengslum við tölum,
hvernig virkar tölvan

1263
00:59:43,800 --> 00:59:48,396
vita hversu lengi runa
númer er eða hvar það byrjar?

1264
00:59:48,396 --> 00:59:50,270
Jæja, það kemur out--
og við munum ekki fara of mikið

1265
00:59:50,270 --> 00:59:54,970
í þessu stigi detail--
tölvur færa efni í kring í minni

1266
00:59:54,970 --> 00:59:57,800
bókstaflega með því að þessi vefföng.

1267
00:59:57,800 --> 01:00:02,080
Svo í tölvu, ef þú ert
skrifa kóða til að geyma hluti

1268
01:00:02,080 --> 01:00:05,800
eins orðum, hvað þú ert
í raun að gera er að skrifa

1269
01:00:05,800 --> 01:00:11,320
orðasambönd sem muna hvar í
minni í tölvunni þessi orð eru.

1270
01:00:11,320 --> 01:00:14,370
Svo láta mig gera mjög,
mjög einfalt dæmi.

1271
01:00:14,370 --> 01:00:18,260
>> Ég ætla að fara á undan og
opna einfaldan texta program,

1272
01:00:18,260 --> 01:00:20,330
og ég ætla að búa til
skrá sem heitir hello.c.

1273
01:00:20,330 --> 01:00:22,849
Flest af þessum upplýsingum við
mun ekki fara í í smáatriðum,

1274
01:00:22,849 --> 01:00:25,140
en ég ætla að skrifa
Dagskráin í sama tungumáli,

1275
01:00:25,140 --> 01:00:31,140
C. Þetta er miklu meira ógnandi,
Ég myndi halda því fram, en grunni,

1276
01:00:31,140 --> 01:00:32,490
en það er mjög svipað í anda.

1277
01:00:32,490 --> 01:00:34,364
Í staðreynd, þessir hrokkið
braces-- þú getur konar

1278
01:00:34,364 --> 01:00:37,820
hugsa um hvað ég gerði bara eins og þetta.

1279
01:00:37,820 --> 01:00:39,240
>> Við skulum gera þetta, í raun og veru.

1280
01:00:39,240 --> 01:00:45,100
Þegar grænn fáni smellt
gera eftirfarandi.

1281
01:00:45,100 --> 01:00:50,210
Ég vil að prenta út "halló."

1282
01:00:50,210 --> 01:00:51,500
Svo er þetta nú sauðakóðanum.

1283
01:00:51,500 --> 01:00:53,000
Ég er svona blurring línurnar.

1284
01:00:53,000 --> 01:00:56,750
Í C, þetta tungumál ég er að tala
um þetta lína prenta halló

1285
01:00:56,750 --> 01:01:01,940
reyndar verður "printf" með
sumir svigum og hálf-hreinsun.

1286
01:01:01,940 --> 01:01:03,480
>> En það er nákvæmlega sama hugmynd.

1287
01:01:03,480 --> 01:01:06,730
Og þetta mjög notandi-vingjarnlegur
"Þegar grænn fáni smellt" verður

1288
01:01:06,730 --> 01:01:10,182
miklu meira Bogagöng "int helstu ógilt."

1289
01:01:10,182 --> 01:01:12,890
Og þetta hefur í raun enga kortlagning,
þannig að ég ætla bara að fara að hunsa það.

1290
01:01:12,890 --> 01:01:17,210
En hrokkið axlabönd eru eins og
boginn stykki púsluspil eins og þetta.

1291
01:01:17,210 --> 01:01:18,700
>> Svo þú getur konar giska á.

1292
01:01:18,700 --> 01:01:22,357
Jafnvel ef þú hefur aldrei forritað áður,
hvað þýðir þetta forrit sennilega gera?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Sennilega prentar halló
með upphrópunarmerki.

1295
01:01:28,000 --> 01:01:29,150
>> Svo skulum reyna það.

1296
01:01:29,150 --> 01:01:30,800
Ég ætla að spara hana.

1297
01:01:30,800 --> 01:01:34,000
Og þetta er, aftur, mjög
gamla skólanum umhverfi.

1298
01:01:34,000 --> 01:01:35,420
Ég get ekki smellt, ég get ekki dregið.

1299
01:01:35,420 --> 01:01:36,910
Ég verð að slá skipanir.

1300
01:01:36,910 --> 01:01:41,320
Svo ég vil að hlaupa program minn, svo
Ég gæti gert þetta, eins hello.c.

1301
01:01:41,320 --> 01:01:42,292
Það er skrá sem ég hljóp.

1302
01:01:42,292 --> 01:01:43,500
En bíddu, ég er vantar skref.

1303
01:01:43,500 --> 01:01:46,470
Hvað gerði við segjum er nauðsynlegt
skref fyrir tungumál eins og C?

1304
01:01:46,470 --> 01:01:49,470
Ég hef bara skrifað uppspretta
númer, en hvað þarf ég?

1305
01:01:49,470 --> 01:01:50,670
Já, ég þarf þýðanda.

1306
01:01:50,670 --> 01:01:57,670
Svo á Mac minn hér, ég er með
forrit sem heitir GCC, GNU C þýðanda,

1307
01:01:57,670 --> 01:02:03,990
sem leyfir mér að gera this-- beygju
Kóðinn minn í, munum við kalla það,

1308
01:02:03,990 --> 01:02:04,930
vél númer.

1309
01:02:04,930 --> 01:02:10,180
>> Og ég get séð það,
aftur, eins og hér segir, þessir

1310
01:02:10,180 --> 01:02:14,090
eru núll og sjálfur ég bara
búin til úr uppspretta minn kóða,

1311
01:02:14,090 --> 01:02:15,730
allar núllum og sjálfur.

1312
01:02:15,730 --> 01:02:17,770
Og ef ég vil keyra
minn program-- það gerist

1313
01:02:17,770 --> 01:02:23,010
að vera kölluð a.out fyrir
sögulegu reasons-- "halló."

1314
01:02:23,010 --> 01:02:24,070
Ég get keyrt það aftur.

1315
01:02:24,070 --> 01:02:25,690
Halló, halló, halló.

1316
01:02:25,690 --> 01:02:27,430
Og það virðist vera að virka.

1317
01:02:27,430 --> 01:02:31,000
>> En það þýðir einhvers staðar í minn
minni tölvunnar eru orðin

1318
01:02:31,000 --> 01:02:35,279
H-e-L-L-o, upphrópunarmerki.

1319
01:02:35,279 --> 01:02:38,070
Og það kemur í ljós, eins og innskot,
hvað tölva myndi venjulega

1320
01:02:38,070 --> 01:02:40,550
gera þannig að það veit hvar
hlutir byrja og end-- það er

1321
01:02:40,550 --> 01:02:42,460
fara að setja sérstaka tákn hér.

1322
01:02:42,460 --> 01:02:46,064
Og venju er að setja
númer núll í lok orði

1323
01:02:46,064 --> 01:02:48,230
þannig að þú veist hvar það
reyndar endar, þannig að þú

1324
01:02:48,230 --> 01:02:52,750
halda ekki að prenta út fleiri og fleiri
stafir en þú í raun og veru ætla.

1325
01:02:52,750 --> 01:02:55,400
>> En takeaway hér, jafnvel
þó að þetta er nokkuð yfirnáttúrulegt,

1326
01:02:55,400 --> 01:02:58,140
er að það er á endanum
tiltölulega einfalt.

1327
01:02:58,140 --> 01:03:04,550
Þú varst að gefa einhverskonar borði, autt
pláss sem þú getur skrifað bréf.

1328
01:03:04,550 --> 01:03:07,150
Þú þarft einfaldlega að hafa
sérstakt tákn, eins og geðþótta

1329
01:03:07,150 --> 01:03:10,316
fjöldi núll, að setja í lok
orð þín svo að tölvan veit,

1330
01:03:10,316 --> 01:03:13,410
ó, ætti ég að hætta prentun á eftir
Ég sé upphrópunarmerki.

1331
01:03:13,410 --> 01:03:16,090
Vegna þess að næsta sem þar
er ASCII gildi núll,

1332
01:03:16,090 --> 01:03:19,125
eða null karakter sem
einhver myndi kalla það.

1333
01:03:19,125 --> 01:03:21,500
En það er góður af vandamál
hér, og við skulum snúa aftur

1334
01:03:21,500 --> 01:03:23,320
til tölur um stund.

1335
01:03:23,320 --> 01:03:28,720
Segjum sem svo að ég geri, í raun,
hafa fjölbreytta tölum,

1336
01:03:28,720 --> 01:03:30,730
og ætla að
Forritið sem ég er að skrifa er

1337
01:03:30,730 --> 01:03:34,680
eins og bekk bók fyrir kennara
og kennara í kennslustofunni.

1338
01:03:34,680 --> 01:03:38,720
Og þetta forrit gerir hann eða hana
að slá í stig nemenda sinna

1339
01:03:38,720 --> 01:03:39,960
á Skyndipróf.

1340
01:03:39,960 --> 01:03:43,750
Og ætla að fær nemandinn
100 á fyrsta prófið sitt, kannski

1341
01:03:43,750 --> 01:03:49,920
eins og 80 á næsta einn, þá er
75, þá 90 á fjórða spurningakeppni.

1342
01:03:49,920 --> 01:03:54,150
>> Svo á þessum tímapunkti í sögunni,
fylki er stærð fjórum.

1343
01:03:54,150 --> 01:03:58,470
Það er algerlega meira minni í
tölva, en array, svo að segja,

1344
01:03:58,470 --> 01:04:00,350
af stærð fjórum.

1345
01:04:00,350 --> 01:04:06,060
Segjum nú að kennarinn vill
að úthluta fimmta quiz á bekknum.

1346
01:04:06,060 --> 01:04:08,510
Jæja, einn af þeim hlutum sem hann
eða hún er að fara að þurfa að gera

1347
01:04:08,510 --> 01:04:10,650
er nú geymt fleiri gildi hér.

1348
01:04:10,650 --> 01:04:15,490
En ef array kennarinn hefur
búin í þessari áætlun er stærð fyrir,

1349
01:04:15,490 --> 01:04:22,440
einn af vandamálinu með array er að
þú getur ekki bara að halda að bæta við minni.

1350
01:04:22,440 --> 01:04:26,470
Vegna þess hvað ef annar hluti af
Forritið hefur orðið "hey" þarna?

1351
01:04:26,470 --> 01:04:29,650
>> Með öðrum orðum, minni mitt er hægt að
notaður fyrir neitt í áætluninni.

1352
01:04:29,650 --> 01:04:33,250
Og ef fyrirfram ég slóst í, hey,
Ég vil inntak fjórum quiz skora,

1353
01:04:33,250 --> 01:04:34,784
þeir gætu farið hér og hér.

1354
01:04:34,784 --> 01:04:37,700
Og ef þú breytir skyndilega um skoðun
seinna og segja ég vil fimmta quiz

1355
01:04:37,700 --> 01:04:40,872
skora, þú getur ekki bara
setja það hvar sem þú vilt,

1356
01:04:40,872 --> 01:04:42,580
því hvað ef þetta
minni er verið að nota

1357
01:04:42,580 --> 01:04:45,990
fyrir eitthvað else-- annað forrit
eða einhver annar lögun af the program

1358
01:04:45,990 --> 01:04:46,910
að þú ert að keyra?

1359
01:04:46,910 --> 01:04:50,650
Svo þú verður að hugsa fyrirfram
hvernig þú vilt geyma gögn,

1360
01:04:50,650 --> 01:04:54,480
því nú þú hefur málað
sjálfur í stafrænu horn.

1361
01:04:54,480 --> 01:04:57,280
>> Svo kennari gæti í staðinn
segja þegar þú skrifar forrit

1362
01:04:57,280 --> 01:04:59,360
að geyma hans eða hennar
bekk, þú veist hvað?

1363
01:04:59,360 --> 01:05:04,180
Ég er að fara að biðja,
þegar þú skrifar forritið mitt,

1364
01:05:04,180 --> 01:05:12,070
að ég vil núll, einn, tveir, þrír,
fjögur, fimm, sex, átta einkunna samtals.

1365
01:05:12,070 --> 01:05:15,320
Svo einn, tveir, þrír, fjórir,
fimm, sex, sjö, átta.

1366
01:05:15,320 --> 01:05:18,612
Kennarinn getur bara yfir-úthluta
minni þegar þú skrifar áætlun hans eða hennar

1367
01:05:18,612 --> 01:05:19,570
og segja, þú veist hvað?

1368
01:05:19,570 --> 01:05:22,236
Ég ætla aldrei að fara að úthluta fleiri
en átta Skyndipróf í önn.

1369
01:05:22,236 --> 01:05:23,130
Það er bara brjálaður.

1370
01:05:23,130 --> 01:05:24,470
Ég mun aldrei úthluta því.

1371
01:05:24,470 --> 01:05:28,270
Þannig að þetta leiðin sem hann eða hún hefur
sveigjanleika til að skora geyma nemenda,

1372
01:05:28,270 --> 01:05:33,010
eins 75, 90, og kannski einn auka þar
nemandi fékk auka lánsfé, 105.

1373
01:05:33,010 --> 01:05:36,130
>> En ef kennarinn aldrei
notar þessi þrjú rými,

1374
01:05:36,130 --> 01:05:38,860
það er innsæi takeaway hér.

1375
01:05:38,860 --> 01:05:41,410
Hann eða hún er bara að sóa pláss.

1376
01:05:41,410 --> 01:05:44,790
Svo í öðrum orðum, það er þetta
algengt tradeoff í forritun

1377
01:05:44,790 --> 01:05:48,241
þar sem þú getur annað hvort úthluta
nákvæmlega eins mikið minni og þú vilt,

1378
01:05:48,241 --> 01:05:51,490
The kosti sem er að þú ert frábær
efficient-- þú ert ekki að vera eyðslusamur

1379
01:05:51,490 --> 01:05:54,640
á all-- en hæðir sem
er það ef þú skiptir um skoðun þegar

1380
01:05:54,640 --> 01:05:58,780
nota forritið sem þú vilt geyma
fleiri gögn en þú upphaflega ætlað.

1381
01:05:58,780 --> 01:06:03,030
>> Svo kannski er lausnin, þá,
skrifa forrit þannig

1382
01:06:03,030 --> 01:06:05,605
sem þeir nota meira minni
en þeir þurfa í raun og veru.

1383
01:06:05,605 --> 01:06:07,730
This vegur þú ert ekki að fara
að hlaupa inn í þessi vandamál,

1384
01:06:07,730 --> 01:06:09,730
en þú ert að eyðslusamur.

1385
01:06:09,730 --> 01:06:12,960
Og því meira minni program notar,
eins og við ræddum í gær, því minni

1386
01:06:12,960 --> 01:06:15,410
minni sem er í boði
fyrir önnur forrit,

1387
01:06:15,410 --> 01:06:18,790
fyrr tölvan þín gæti hægja
niður vegna raunverulegur minni.

1388
01:06:18,790 --> 01:06:22,670
Og svo tilvalin lausn gæti verið það?

1389
01:06:22,670 --> 01:06:24,610
>> Undir-úthlutun virðist slæmt.

1390
01:06:24,610 --> 01:06:27,030
Yfir-úthlutun virðist slæmt.

1391
01:06:27,030 --> 01:06:31,120
Svo það gæti verið betri lausn?

1392
01:06:31,120 --> 01:06:32,390
Endurúthluta.

1393
01:06:32,390 --> 01:06:33,590
Vera meira dynamic.

1394
01:06:33,590 --> 01:06:37,520
Ekki þvinga þig til að velja
fyrirfram, í upphafi, það sem þú vilt.

1395
01:06:37,520 --> 01:06:41,370
Og vissulega ekki yfir-úthluta,
svo að þú eyðslusamur.

1396
01:06:41,370 --> 01:06:45,770
>> Og svo til að ná því markmiði, að við
þarf að henda þessu gögn uppbygging,

1397
01:06:45,770 --> 01:06:48,100
svo að segja, í burtu.

1398
01:06:48,100 --> 01:06:51,080
Og svo hvað forritari
mun nota venjulega

1399
01:06:51,080 --> 01:06:55,940
er eitthvað sem kallast ekki
array en tengda listanum.

1400
01:06:55,940 --> 01:07:00,860
Með öðrum orðum, hann eða hún mun
byrja að hugsa um minni þeirra

1401
01:07:00,860 --> 01:07:05,280
Eins og að vera einskonar form sem þeir
getur teiknað á eftirfarandi hátt.

1402
01:07:05,280 --> 01:07:08,520
Ef ég vil að geyma eitt númer í
a program-- svo það er September,

1403
01:07:08,520 --> 01:07:12,600
Ég hef gefið nemendum mínum quiz; ég vil
að geyma nemandans fyrsta prófið,

1404
01:07:12,600 --> 01:07:16,220
og þeir fengu 100 á ég it--
er að fara að spyrja tölvuna mína,

1405
01:07:16,220 --> 01:07:19,540
með því að áætluninni sem ég hef
skrifað, fyrir einn klumpur af minni.

1406
01:07:19,540 --> 01:07:22,570
Og ég ætla að geyma það
Fjölda 100 í það, og það er það.

1407
01:07:22,570 --> 01:07:24,820
>> Þá nokkrum vikum seinna
þegar ég fæ annað quiz minn,

1408
01:07:24,820 --> 01:07:27,890
og það er kominn tími til að slá
af því að 90%, ég er að fara

1409
01:07:27,890 --> 01:07:32,129
að spyrja tölvuna, hey, tölva,
má ég hafa aðra klumpur af minni?

1410
01:07:32,129 --> 01:07:34,170
Það er að fara að gefa mér þetta
tóm klumpur af minni.

1411
01:07:34,170 --> 01:07:39,370
Ég ætla að setja á fjölda 90,
en í áætlun mína einhvern veginn eða other--

1412
01:07:39,370 --> 01:07:42,100
og við munum ekki hafa áhyggjur
setningafræði fyrir this-- ég þarf

1413
01:07:42,100 --> 01:07:44,430
að einhvern veginn keðjureykir þetta saman.

1414
01:07:44,430 --> 01:07:47,430
Og ég keðjureykir þær saman við
það lítur út eins og ör hér.

1415
01:07:47,430 --> 01:07:50,050
>> Þriðja quiz sem kemur upp,
Ég ætla að segja, hey, tölva,

1416
01:07:50,050 --> 01:07:51,680
gefa mér annað klumpur af minni.

1417
01:07:51,680 --> 01:07:54,660
Og ég ætla að setja niður
hvað sem það var, eins og 75,

1418
01:07:54,660 --> 01:07:56,920
og ég verð að keðja þetta
saman nú einhvern veginn.

1419
01:07:56,920 --> 01:08:00,290
Fjórða quiz kemur með, og kannski
það er undir lok misseris.

1420
01:08:00,290 --> 01:08:03,140
Og eftir þeim tímapunkti program minn
gæti verið að nota minni

1421
01:08:03,140 --> 01:08:05,540
um allt, allan líkamlega.

1422
01:08:05,540 --> 01:08:08,170
Og svo bara fyrir spörk, ég er
að fara að draga þetta fram

1423
01:08:08,170 --> 01:08:11,260
quiz-- ég gleymi hvað það var; ég
held kannski 80 eða something--

1424
01:08:11,260 --> 01:08:12,500
leið hérna.

1425
01:08:12,500 --> 01:08:15,920
>> En það er allt í lagi, vegna þess að á myndrænan
Ég ætla að draga þessa línu.

1426
01:08:15,920 --> 01:08:19,063
Með öðrum orðum, í raun,
í vélbúnaði tölvunnar,

1427
01:08:19,063 --> 01:08:20,979
fyrsta skora gæti
enda hér vegna þess að það er

1428
01:08:20,979 --> 01:08:22,529
strax í upphafi misseris.

1429
01:08:22,529 --> 01:08:25,810
Næsta einn gæti endað hér
vegna smá tíma hefur liðið

1430
01:08:25,810 --> 01:08:27,210
og forritið heldur gangi.

1431
01:08:27,210 --> 01:08:30,060
Næsta stig, sem var
75, gæti verið hérna.

1432
01:08:30,060 --> 01:08:33,420
Og síðasta skora gæti verið
80, sem er hérna.

1433
01:08:33,420 --> 01:08:38,729
>> Svo í raun, líkamlega, þetta gæti verið
hvað minni tölvunnar lítur út.

1434
01:08:38,729 --> 01:08:41,569
En þetta er ekki gagnlegt andlega
fyrirmynd fyrir a tölva forritari.

1435
01:08:41,569 --> 01:08:44,649
Hvers vegna ættir þú að hugsa þar sem
Heck gögn er lendi?

1436
01:08:44,649 --> 01:08:46,200
Þú vilt bara til að geyma gögn.

1437
01:08:46,200 --> 01:08:49,390
>> Þetta er góður af eins og umræðu okkar
fyrr teikna teningur.

1438
01:08:49,390 --> 01:08:52,200
Hvers vegna gera þú aðgát hvað
hornið er á teningnum

1439
01:08:52,200 --> 01:08:53,740
og hvernig þú þarft að snúa að draga það?

1440
01:08:53,740 --> 01:08:54,950
Þú vilt bara teningur.

1441
01:08:54,950 --> 01:08:57,359
Á sama hátt hér, þér
bara að bekk bók.

1442
01:08:57,359 --> 01:08:59,559
Þú vilt bara að hugsa um
þetta sem lista af tölum.

1443
01:08:59,559 --> 01:09:01,350
Hverjum er ekki sama hvernig það er
framkvæmda í vélbúnaði?

1444
01:09:01,350 --> 01:09:05,180
>> Svo abstrakt nú
er þessi mynd hér.

1445
01:09:05,180 --> 01:09:07,580
Þetta er tengdur lista, eins og
forritari myndi kalla það,

1446
01:09:07,580 --> 01:09:10,640
að því marki sem þú hefur
lista, augljóslega af tölum.

1447
01:09:10,640 --> 01:09:14,990
En það er tengt á myndrænan
með því að þessum örvum,

1448
01:09:14,990 --> 01:09:18,510
og allar þessar örvar are-- undir
hetta, ef þú ert forvitinn,

1449
01:09:18,510 --> 01:09:23,210
muna að líkamlega vélbúnaður okkar hefur
heimilisföng núll, einn, tveir, þrír, fjórir.

1450
01:09:23,210 --> 01:09:28,465
Allar þessar örvar eru er eins og kort
eða áttir, þar sem ef 90 is-- nú

1451
01:09:28,465 --> 01:09:29,090
Ég fékk að telja.

1452
01:09:29,090 --> 01:09:31,750
>> Núll, einn, tveir, þrír,
fjórir, fimm, sex, sjö.

1453
01:09:31,750 --> 01:09:35,640
Það lítur út eins og 90 er
minni heimilisfang númer sjö.

1454
01:09:35,640 --> 01:09:38,460
Allar þessar örvar eru er
eins og lítið rusl úr pappír

1455
01:09:38,460 --> 01:09:42,439
það er að gefa leiðbeiningar til að
forrit sem segir fylgja þessu korti

1456
01:09:42,439 --> 01:09:43,880
að fá að staðsetningu sjö.

1457
01:09:43,880 --> 01:09:46,680
Og þar sem þú munt finna
Annað quiz nemanda skora.

1458
01:09:46,680 --> 01:09:52,100
Á sama tíma, 75-- ef ég halda áfram á þessu,
þetta er sjö, átta, níu, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Þessi annar arrow táknar bara
kort í minni stað 15.

1461
01:09:59,080 --> 01:10:02,550
En aftur, forritari almennt gerir
ekki sama um þennan stigi smáatriðum.

1462
01:10:02,550 --> 01:10:05,530
Og í flestum hverjum forritun
Tungumál dag, forritari

1463
01:10:05,530 --> 01:10:10,490
mun ekki einu sinni vita hvar á minni
þessar tölur í raun eru.

1464
01:10:10,490 --> 01:10:14,830
Allt sem hann eða hún hefur til að hugsa um er
að þeir séu á einhvern hátt tengd saman

1465
01:10:14,830 --> 01:10:18,390
í gagnagrind eins og þetta.

1466
01:10:18,390 --> 01:10:21,580
>> En það reynist ekki
að fá of tæknilegur.

1467
01:10:21,580 --> 01:10:27,430
En bara vegna þess að við getum kannski
efni á að hafa þessa umræðu hér,

1468
01:10:27,430 --> 01:10:33,630
ráð fyrir að við endurskoðun
þetta mál hér á fylki.

1469
01:10:33,630 --> 01:10:35,780
Við skulum sjá hvort við eftirsjá fara hér.

1470
01:10:35,780 --> 01:10:42,950
Þetta er 100, 90, 75, og 80.

1471
01:10:42,950 --> 01:10:44,980
>> Leyfðu mér að gera stuttlega þessa fullyrðingu.

1472
01:10:44,980 --> 01:10:48,980
Þetta er fylki, og aftur,
mikilvæg einkenni fylki

1473
01:10:48,980 --> 01:10:52,400
er að öll gögn er aftur til
aftur til baka í memory-- bókstaflega

1474
01:10:52,400 --> 01:10:56,830
eitt bæti eða kannski fjögur bæti,
sumir fastur fjöldi bæti burtu.

1475
01:10:56,830 --> 01:11:00,710
Í tengda listanum, sem við gætum dregið
eins og þetta, undir hetta sem

1476
01:11:00,710 --> 01:11:02,000
veit hvar það efni sem er?

1477
01:11:02,000 --> 01:11:03,630
Það þarf ekki einu sinni að renna svona.

1478
01:11:03,630 --> 01:11:06,050
Sumar af eftirfarandi upplýsingum gæti verið
aftur til vinstri þar upp.

1479
01:11:06,050 --> 01:11:07,530
Þú þarft ekki einu sinni vita.

1480
01:11:07,530 --> 01:11:15,430
>> Og svo með fjölbreytta, hefur þú a
lögun þekktur sem handahófi aðgang.

1481
01:11:15,430 --> 01:11:20,570
Og hvað handahófi aðgang leið er
sem tölvan getur hoppað stað

1482
01:11:20,570 --> 01:11:22,730
á hvaða stað í fylki.

1483
01:11:22,730 --> 01:11:23,580
Hvers vegna?

1484
01:11:23,580 --> 01:11:26,000
Vegna þess að tölvan veit
að fyrsta staðsetning er

1485
01:11:26,000 --> 01:11:29,540
núll, einn, tveir, og þrír.

1486
01:11:29,540 --> 01:11:33,890
>> Og svo ef þú vilt fara úr
þessi þáttur í næsta frumefni,

1487
01:11:33,890 --> 01:11:36,099
þú bókstaflega, í
Hugur tölvunni, réttlátur bæta við einum.

1488
01:11:36,099 --> 01:11:39,140
Ef þú vilt fara í þriðja frumefni,
bara bæta one-- næsta frumefni, bara

1489
01:11:39,140 --> 01:11:40,290
bæta við einum.

1490
01:11:40,290 --> 01:11:42,980
Hins vegar, í þessari útgáfu
af sögunni, býst

1491
01:11:42,980 --> 01:11:46,080
tölvan er nú að leita
á eða takast á við fjölda 100.

1492
01:11:46,080 --> 01:11:49,770
Hvernig gera þú fá til the næstur
bekk í bekk bókinni?

1493
01:11:49,770 --> 01:11:52,560
>> Þú þarft að taka sjö
skref, sem er handahófskennt.

1494
01:11:52,560 --> 01:11:58,120
Til að fá til the næstur einn, þú þarft að
taka aðra átta þrep til að komast til 15.

1495
01:11:58,120 --> 01:12:02,250
Með öðrum orðum, það er ekki
stöðug bilið milli talnanna,

1496
01:12:02,250 --> 01:12:04,857
og svo það tekur bara
tölva meiri tími er málið.

1497
01:12:04,857 --> 01:12:06,940
Tölvan þarf að leita
með minni í röð

1498
01:12:06,940 --> 01:12:08,990
til að finna það sem þú ert að leita að.

1499
01:12:08,990 --> 01:12:14,260
>> Svo á meðan fylki tilhneigingu til að vera
fljótur gögn structure-- vegna þess að þú

1500
01:12:14,260 --> 01:12:17,610
getur bókstaflega bara gera einfalda stærðfræði
og fá þar sem þú vilt með því að bæta við einum,

1501
01:12:17,610 --> 01:12:21,300
fyrir instance-- tengdan lista,
þú fórna að lögun.

1502
01:12:21,300 --> 01:12:24,020
Þú getur ekki bara farið úr fyrsta
að öðrum til þriðja til fjórða.

1503
01:12:24,020 --> 01:12:25,240
Þú þarft að fylgja kortinu.

1504
01:12:25,240 --> 01:12:28,160
Þú þarft að taka fleiri skref
til að fá að þeim gildum sem

1505
01:12:28,160 --> 01:12:30,230
virðist vera að bæta kostnað.

1506
01:12:30,230 --> 01:12:35,910
Þannig að við erum að borga verð, en það var
eiginleiki sem Dan var að leita hér?

1507
01:12:35,910 --> 01:12:38,110
Hvað gerir tengdan lista
virðist leyfa okkur að gera,

1508
01:12:38,110 --> 01:12:40,240
sem var uppruni
þetta tiltekna saga?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Nákvæmlega.

1511
01:12:43,830 --> 01:12:46,220
A dynamic stærð við það.

1512
01:12:46,220 --> 01:12:48,040
Við getum bætt við þennan lista.

1513
01:12:48,040 --> 01:12:51,430
Við getum jafnvel skreppa lista, svo
að við erum bara að nota eins mikið minni

1514
01:12:51,430 --> 01:12:55,560
eins og við viljum í raun og veru og svo
við erum aldrei yfir-úthlutun.

1515
01:12:55,560 --> 01:12:58,470
>> Nú bara að vera mjög nit-vandlátur,
það er falinn kostnaður.

1516
01:12:58,470 --> 01:13:01,980
Svo þú ættir ekki bara að láta mig sannfæra
þú að þetta er sannfærandi tradeoff.

1517
01:13:01,980 --> 01:13:04,190
Það er annar falinn kostnaður hér.

1518
01:13:04,190 --> 01:13:06,550
Ávinningur, að vera ljóst,
er að við fáum kraft.

1519
01:13:06,550 --> 01:13:10,359
Ef ég vil annað þáttur, ég get bara
teikna það og setja númer í það.

1520
01:13:10,359 --> 01:13:12,150
Og þá get ég tengt það
með mynd hér,

1521
01:13:12,150 --> 01:13:14,970
en hérna, aftur, ef ég hef
málað mig út í horn,

1522
01:13:14,970 --> 01:13:19,410
ef eitthvað annað er nú þegar að nota
minni hér, ég er út af heppni.

1523
01:13:19,410 --> 01:13:21,700
Ég hef málað mig í horn.

1524
01:13:21,700 --> 01:13:24,390
>> En hvað er falinn
kosta á þessari mynd?

1525
01:13:24,390 --> 01:13:27,690
Það er ekki bara magn
Tíminn sem það tekur

1526
01:13:27,690 --> 01:13:29,870
að fara héðan til hér,
sem er sjö skref, þá

1527
01:13:29,870 --> 01:13:32,820
átta skrefum, sem er meira en ein.

1528
01:13:32,820 --> 01:13:34,830
Hvað er annað falinn kostnaður?

1529
01:13:34,830 --> 01:13:35,440
Ekki bara tími.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Frekari upplýsingar eru
nauðsynleg til að ná þessari mynd.

1532
01:13:49,940 --> 01:13:53,210
>> Já, það kort, þessir litlu bjórar
pappír, eins og ég að halda lýsa þeim sem.

1533
01:13:53,210 --> 01:13:55,650
Þetta arrows-- þeir eru ekki ókeypis.

1534
01:13:55,650 --> 01:13:57,660
A computer-- þú veist
hvað tölva hefur.

1535
01:13:57,660 --> 01:13:58,790
Það hefur núll og sjálfur.

1536
01:13:58,790 --> 01:14:03,170
Ef þú vilt að tákna ör eða a
kortleggja eða tala, þú þarft sumir minni.

1537
01:14:03,170 --> 01:14:05,950
Svo hinn verð sem þú
greiða fyrir tengda listanum,

1538
01:14:05,950 --> 01:14:09,070
sameiginlegt tölvunarfræði
úrræði, er líka pláss.

1539
01:14:09,070 --> 01:14:11,710
>> Og reyndar svo, svo almennt,
meðal tradeoffs

1540
01:14:11,710 --> 01:14:15,580
í að hanna hugbúnaðarverkfræði
kerfi er tími og space--

1541
01:14:15,580 --> 01:14:18,596
eru tveir af hráefni þínum, tveir
af the dýr hráefni þínum.

1542
01:14:18,596 --> 01:14:21,220
Þetta er kosta mig meiri tíma
því ég þarf að fylgja þessu korti,

1543
01:14:21,220 --> 01:14:25,730
en það er líka kosta mig meira pláss
vegna þess að ég þarf að halda þessu korti í kring.

1544
01:14:25,730 --> 01:14:28,730
Svo vonin, sem við höfum eins konar
rætt um í gær og dag,

1545
01:14:28,730 --> 01:14:31,720
er að ávinningur
mun meiri en kostnaðurinn.

1546
01:14:31,720 --> 01:14:33,870
>> En það er engin augljós lausn hér.

1547
01:14:33,870 --> 01:14:35,870
Kannski er það better--
a la fljótur og óhreinn,

1548
01:14:35,870 --> 01:14:38,660
sem Kareem lagt earlier--
að kasta minni á vandamálinu.

1549
01:14:38,660 --> 01:14:42,520
Bara kaupa meira minni, hugsa minna
erfitt um að leysa vandann,

1550
01:14:42,520 --> 01:14:44,595
og leysa það á auðveldari hátt.

1551
01:14:44,595 --> 01:14:46,720
Og reyndar fyrr, þegar
við ræddum um tradeoffs,

1552
01:14:46,720 --> 01:14:49,190
það var ekki pláss í
tölva og tíma.

1553
01:14:49,190 --> 01:14:51,810
Það var verktaki tími, sem
er enn annar auðlind.

1554
01:14:51,810 --> 01:14:54,829
>> Svo aftur, það er þetta jafnvægislist
að reyna að ákveða hvaða af þessum hlutum

1555
01:14:54,829 --> 01:14:55,870
ertu tilbúinn að eyða?

1556
01:14:55,870 --> 01:14:57,380
Sem er amk dýr?

1557
01:14:57,380 --> 01:15:01,040
Sem gefur betri árangri?

1558
01:15:01,040 --> 01:15:01,540
Já?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Einmitt.

1561
01:15:12,580 --> 01:15:15,970
Í þessu tilfelli, ef þú ert
fulltrúi tölur í maps--

1562
01:15:15,970 --> 01:15:18,820
þessir eru kallaðir á mörgum tungumálum
"ábendingum" eða "heimilisföng" -

1563
01:15:18,820 --> 01:15:20,390
það er tvöfalt rúm.

1564
01:15:20,390 --> 01:15:24,390
Það þarf ekki að vera eins slæmt eins og tvöfaldur ef
núna erum við bara að geyma tölur.

1565
01:15:24,390 --> 01:15:27,410
Segjum sem svo að við vorum að geyma
sjúkraskrám í hospital--

1566
01:15:27,410 --> 01:15:30,870
svo nöfnum Pierson er, símanúmerum,
almannatryggingar reikningur, læknir

1567
01:15:30,870 --> 01:15:31,540
sögu.

1568
01:15:31,540 --> 01:15:34,160
Þessi kassi gæti verið mikið,
miklu stærri, en í því tilviki

1569
01:15:34,160 --> 01:15:38,000
a pínulítill lítill músina, heimilisfang
næsta element-- það er ekki stór samningur.

1570
01:15:38,000 --> 01:15:40,620
Það er svo kögur
kosta það skiptir ekki máli.

1571
01:15:40,620 --> 01:15:43,210
En í þessu tilfelli, já, það er tvöföldun.

1572
01:15:43,210 --> 01:15:45,290
Góð spurning.

1573
01:15:45,290 --> 01:15:47,900
>> Við skulum tala um tíma
lítið meira concretely.

1574
01:15:47,900 --> 01:15:50,380
Hvað er í gangi tími
á að leita þennan lista?

1575
01:15:50,380 --> 01:15:53,640
Segjum að ég vildi leita
í gegnum alla nemenda bekk,

1576
01:15:53,640 --> 01:15:55,980
og það er n einkunnir
í þessum gögnum uppbyggingu.

1577
01:15:55,980 --> 01:15:58,830
Hér líka, getum við fengið lánað
orðaforða fyrr.

1578
01:15:58,830 --> 01:16:00,890
Þetta er línulegt gögn uppbygging.

1579
01:16:00,890 --> 01:16:04,570
>> Big O n er það sem er nauðsynlegt til að fá
til loka þessum gögnum uppbyggingu,

1580
01:16:04,570 --> 01:16:08,410
whereas-- og við höfum ekki séð
þetta before-- fylki gefur þér

1581
01:16:08,410 --> 01:16:13,555
hvað heitir fasti tími, sem þýðir
eitt skref eða tvö skref eða 10 steps--

1582
01:16:13,555 --> 01:16:14,180
skiptir ekki máli.

1583
01:16:14,180 --> 01:16:15,440
Það er föst tala.

1584
01:16:15,440 --> 01:16:17,440
Það hefur ekkert að gera með
stærð fylkisins.

1585
01:16:17,440 --> 01:16:20,130
Og ástæðan fyrir því,
aftur, er handahófi aðgang.

1586
01:16:20,130 --> 01:16:23,180
Tölvan getur bara strax
hoppa á annan stað,

1587
01:16:23,180 --> 01:16:27,770
vegna þess að þeir eru allir á sama
fjarlægð frá öllu öðru.

1588
01:16:27,770 --> 01:16:29,112
Það er engin hugsun að ræða.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Allt í lagi.

1591
01:16:32,400 --> 01:16:39,230
Svo ef ég get, láta mig reyna að
mála tvær endanlega myndir.

1592
01:16:39,230 --> 01:16:42,830
A mjög sameiginlegur einn þekktur sem kjötkássa töflunni.

1593
01:16:42,830 --> 01:16:51,120
Svo til að hvetja þessa umræðu,
láta mig hugsa um hvernig á að gera þetta.

1594
01:16:51,120 --> 01:16:52,610
>> Svo hvernig um þetta?

1595
01:16:52,610 --> 01:16:55,160
Gerum ráð fyrir að vandamálið
Við viljum leysa nú

1596
01:16:55,160 --> 01:16:58,360
er að innleiða í dictionary--
svo er allt fullt af enskum orðum

1597
01:16:58,360 --> 01:16:59,330
eða hvað sem er.

1598
01:16:59,330 --> 01:17:02,724
Og markmiðið er að vera fær um að svara
spurningar um form er þetta orð?

1599
01:17:02,724 --> 01:17:04,640
Svo þú vilt að framkvæma
a stafa afgreiðslumaður, bara

1600
01:17:04,640 --> 01:17:07,220
eins og líkamlega orðabókina
að þú getur litið það upp í.

1601
01:17:07,220 --> 01:17:10,490
Segjum að ég væri að gera þetta með fjölda.

1602
01:17:10,490 --> 01:17:12,590
Ég gæti gert þetta.

1603
01:17:12,590 --> 01:17:20,756
>> Og ætla orðin eru epli
og banani og cantaloupe.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Og ég get ekki hugsað um ávöxtum
að byrja með d, þannig að við erum bara

1606
01:17:26,465 --> 01:17:27,590
fara að hafa þrjú ávexti.

1607
01:17:27,590 --> 01:17:31,510
Svo er þetta fylki, og við erum
að geyma öll þessara orða

1608
01:17:31,510 --> 01:17:34,200
í þessari orðabók sem fylki.

1609
01:17:34,200 --> 01:17:39,350
Spurningin er þá hvernig annars
gætir þú geymt þessar upplýsingar?

1610
01:17:39,350 --> 01:17:43,160
>> Jæja, ég er góður af svindla hér, vegna þess að
hver af þessum bréfum í orði

1611
01:17:43,160 --> 01:17:44,490
er í raun einstaklingur bæti.

1612
01:17:44,490 --> 01:17:46,740
Þannig að ef ég vildi virkilega að vera
nit-vandlátur, ég ætti virkilega

1613
01:17:46,740 --> 01:17:49,600
að skipta þessu upp í mikið
smærri klumpur af minni,

1614
01:17:49,600 --> 01:17:51,289
og við gætum gert einmitt það.

1615
01:17:51,289 --> 01:17:53,580
En við erum að fara að keyra inn
sama vandamál og áður.

1616
01:17:53,580 --> 01:17:56,674
Hvað ef, eins og Merriam Webster eða Oxford
er sérhver year-- þeir bæta orðum

1617
01:17:56,674 --> 01:17:59,340
til dictionary-- við gerum ekki
endilega að mála okkur

1618
01:17:59,340 --> 01:18:00,780
í horn með fjölda?

1619
01:18:00,780 --> 01:18:05,710
>> Þannig að í stað, kannski betri nálgun
er að setja epli í eigin hnút þess eða kassa,

1620
01:18:05,710 --> 01:18:11,190
eins og við myndi segja, banani, og
þá hér höfum cantaloupe.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Og við string þetta saman.

1623
01:18:16,790 --> 01:18:19,980
Svo er þetta array, og
þetta er tengt með lista.

1624
01:18:19,980 --> 01:18:23,300
Ef þú getur ekki alveg séð það bara
segir "array", og þetta segir "lista."

1625
01:18:23,300 --> 01:18:25,780
>> Þannig að við höfum sama
Nákvæmlega málefni eins og áður,

1626
01:18:25,780 --> 01:18:28,600
þar sem við höfum nú
kraftur í tengda listanum okkar.

1627
01:18:28,600 --> 01:18:31,090
En við höfum nokkuð hægur orðabók.

1628
01:18:31,090 --> 01:18:32,870
Segjum að ég vil að líta upp orði.

1629
01:18:32,870 --> 01:18:35,430
Það gæti tekið mig stór O n
skref, vegna þess að orðið gæti

1630
01:18:35,430 --> 01:18:37,840
að vera alla leið í lok
listi, eins cantaloupe.

1631
01:18:37,840 --> 01:18:40,600
Og það kemur í ljós að
í forritun, flokka

1632
01:18:40,600 --> 01:18:42,700
af Gral af gögnum
mannvirki, er eitthvað

1633
01:18:42,700 --> 01:18:46,620
sem gefur þér stöðug
tími eins og fylki

1634
01:18:46,620 --> 01:18:50,870
en það samt gefur þér kraft.

1635
01:18:50,870 --> 01:18:52,940
>> Svo getum við hafa það besta af báðum heimum?

1636
01:18:52,940 --> 01:18:55,570
Og reyndar, það er eitthvað
kallað kjötkássa borð

1637
01:18:55,570 --> 01:18:59,320
sem leyfir þér að gera einmitt
að vísu um það bil.

1638
01:18:59,320 --> 01:19:03,140
A kjötkássa borð er áhugamaður
gögn uppbygging sem við

1639
01:19:03,140 --> 01:19:06,340
er að hugsa um eins og
Sambland af array--

1640
01:19:06,340 --> 01:19:12,390
og ég ætla að draga það
eins this-- og tengd listum

1641
01:19:12,390 --> 01:19:17,310
að ég teikna svona hérna.

1642
01:19:17,310 --> 01:19:19,760
>> Og hvernig þessi hlutur
verk er eins og hér segir.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Ef þetta now-- kjötkássa table--
er þriðji gögn uppbygging minn,

1645
01:19:29,540 --> 01:19:32,590
og ég vil að geyma
orð í þetta, ég er ekki

1646
01:19:32,590 --> 01:19:35,440
vil bara geyma allt í
orð aftur til baka til baka til baka.

1647
01:19:35,440 --> 01:19:37,430
Ég vil nýta sumir
stykki af upplýsingar

1648
01:19:37,430 --> 01:19:40,330
um orðum sem munu láta
mér að fá það þar sem það er hraðar.

1649
01:19:40,330 --> 01:19:43,666
>> Svo gefið orðin epli
og banani og cantaloupe,

1650
01:19:43,666 --> 01:19:45,040
Ég valdi vísvitandi þessi orð.

1651
01:19:45,040 --> 01:19:45,340
Hvers vegna?

1652
01:19:45,340 --> 01:19:47,631
Hvað er tegund af grundvallaratriðum
öðruvísi um þremur?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Hvað er augljóst?

1655
01:19:51,484 --> 01:19:52,900
Þeir byrja með mismunandi stöfum.

1656
01:19:52,900 --> 01:19:53,900
>> Svo þú veist hvað?

1657
01:19:53,900 --> 01:19:57,120
Frekar en að setja öll mín orð í
sama fötu, svo að segja,

1658
01:19:57,120 --> 01:20:00,390
eins og í eina stóra skrá, hvers vegna ekki
Ég að minnsta kosti reyna hagræðingu

1659
01:20:00,390 --> 01:20:04,180
og gera listum mínum 1/26 eins lengi.

1660
01:20:04,180 --> 01:20:07,440
A sannfærandi hagræðingu
gæti verið ástæðan ekki

1661
01:20:07,440 --> 01:20:10,650
I-- að setja í orð
í þessum gögnum uppbyggingu,

1662
01:20:10,650 --> 01:20:14,300
í minni tölvunnar, hvers vegna
ég er ekki að setja allar "A" orð hér,

1663
01:20:14,300 --> 01:20:17,270
allir 'B' orð hér,
og allir 'c' orð hér?

1664
01:20:17,270 --> 01:20:24,610
Svo endar þetta allt að koma epli
hér, banani hér, cantaloupe hér,

1665
01:20:24,610 --> 01:20:25,730
og svo framvegis.

1666
01:20:25,730 --> 01:20:31,700
>> Og ef ég hef til viðbótar
Bæta like-- hvað er annað?

1667
01:20:31,700 --> 01:20:36,640
Epli, banani, pera.

1668
01:20:36,640 --> 01:20:39,370
Einhver hugsa um ávöxtum
sem byrjar með a, b, eða c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- fullkominn.

1670
01:20:40,570 --> 01:20:43,990
Það er að fara að enda hér.

1671
01:20:43,990 --> 01:20:47,530
Og svo við virðast hafa
ívið betri lausn,

1672
01:20:47,530 --> 01:20:50,820
því nú ef ég vil
til að leita að epli, ég

1673
01:20:50,820 --> 01:20:53,200
first-- ég ekki bara kafa
í uppbyggingu gagna mína.

1674
01:20:53,200 --> 01:20:54,850
Ég kafa ekki í minni tölvunnar minnar.

1675
01:20:54,850 --> 01:20:56,530
Ég lít fyrst á fyrsta stafnum.

1676
01:20:56,530 --> 01:20:58,610
>> Og þetta er hvað tölva
vísindamaður myndi segja.

1677
01:20:58,610 --> 01:21:00,760
Þú kjötkássa í uppbyggingu gögn þína.

1678
01:21:00,760 --> 01:21:04,100
Þú tekur inntak þitt, sem í
þetta mál er orðið eins og epli.

1679
01:21:04,100 --> 01:21:07,150
Þú greina það, að horfa á
fyrsti stafurinn í þessu tilfelli,

1680
01:21:07,150 --> 01:21:08,340
þannig hass það.

1681
01:21:08,340 --> 01:21:10,950
Hökkun er almennt hugtak þar
þú tekur eitthvað sem inntak

1682
01:21:10,950 --> 01:21:12,116
og þú framleiða nokkur framleiðsla.

1683
01:21:12,116 --> 01:21:15,090
Og framleiðsla í það
Málið er staðsetningin

1684
01:21:15,090 --> 01:21:18,150
þú vilt leita, fyrsta
staðsetningu, annar staðsetning, þriðja.

1685
01:21:18,150 --> 01:21:22,160
Svo inntak er epli,
framleiðsla er fyrst.

1686
01:21:22,160 --> 01:21:25,054
The inntak er banani, sem
framleiðsla ætti að vera annað.

1687
01:21:25,054 --> 01:21:27,220
The inntak er cantaloupe,
framleiðsla ætti að vera þriðji.

1688
01:21:27,220 --> 01:21:30,320
The inntak er bláberja, sem
framleiðsla ætti aftur að vera annað.

1689
01:21:30,320 --> 01:21:34,010
Og það er það sem hjálpar þér að taka
flýtileiðir í gegnum minni þitt

1690
01:21:34,010 --> 01:21:39,050
í því skyni að fá að orðum
eða gögn á skilvirkari hátt.

1691
01:21:39,050 --> 01:21:43,330
>> Nú sker þetta niður okkar tíma hugsanlega
með eins mikið eins og einn af 26,

1692
01:21:43,330 --> 01:21:45,850
því ef þú ráð fyrir að þú
hafa eins mörg "a" orð eins og "z"

1693
01:21:45,850 --> 01:21:48,080
orð eins og "Q" orð, sem
er í raun ekki realistic--

1694
01:21:48,080 --> 01:21:50,830
þú ert að fara að hafa Skekkja yfir
ákveðin bréf í alphabet--

1695
01:21:50,830 --> 01:21:53,204
en þetta væri stigvaxandi
nálgun sem ekki leyfa

1696
01:21:53,204 --> 01:21:55,930
þú þarft að fá að orðum miklu hraðar.

1697
01:21:55,930 --> 01:21:59,660
Og í raun, háþróuð
program, Googles í heiminum,

1698
01:21:59,660 --> 01:22:02,180
sem Facebooks af world--
þeir myndu nota kjötkássa töflu

1699
01:22:02,180 --> 01:22:03,740
fyrir a einhver fjöldi af mismunandi tilgangi.

1700
01:22:03,740 --> 01:22:06,590
En þeir myndu ekki vera svo barnaleg og
bara líta á fyrsta staf

1701
01:22:06,590 --> 01:22:09,700
í epli eða banana eða
pera eða cantaloupe,

1702
01:22:09,700 --> 01:22:13,420
því eins og þú getur séð þetta
listar gæti samt fengið lengi.

1703
01:22:13,420 --> 01:22:17,130
>> Og svo þetta gæti samt verið eins konar
af linear-- svo konar hægur,

1704
01:22:17,130 --> 01:22:19,980
eins og með stór O n
sem við ræddum áðan.

1705
01:22:19,980 --> 01:22:25,290
Svo það alvöru gott kjötkássa borð vilja
do-- það mun hafa miklu stærri array.

1706
01:22:25,290 --> 01:22:28,574
Og það mun nota miklu meira
háþróuð Hökkun virka,

1707
01:22:28,574 --> 01:22:30,240
þannig að það er ekki bara að líta á "a".

1708
01:22:30,240 --> 01:22:35,480
Kannski lítur á "a-p-P-L-e" og
einhvern veginn breytir þeim fimm stafi

1709
01:22:35,480 --> 01:22:38,400
í stað þar
epli skal geyma.

1710
01:22:38,400 --> 01:22:42,660
Við erum bara naively nota stafinn 'a'
einn, því að það er gott og einfalt.

1711
01:22:42,660 --> 01:22:44,600
>> En kjötkássa borð, í
enda, getur þú hugsa

1712
01:22:44,600 --> 01:22:47,270
af eins og a blöndu af
fylki, sem hver um sig

1713
01:22:47,270 --> 01:22:51,700
hefur tengdan lista sem helst
skal vera eins stutt og mögulegt er.

1714
01:22:51,700 --> 01:22:54,364
Og þetta er ekki augljós lausn.

1715
01:22:54,364 --> 01:22:57,280
Í raun, mikið af fínstilla
sem fer á undir hetta hvenær

1716
01:22:57,280 --> 01:22:59,654
framkvæmd þessar tegundir af
háþróuð gögn uppbygging

1717
01:22:59,654 --> 01:23:01,640
er það sem er rétt
lengd fylkisins?

1718
01:23:01,640 --> 01:23:03,250
Hvað er rétt kjötkássa virka?

1719
01:23:03,250 --> 01:23:04,830
Hvernig finnst þér að geyma hluti í minni?

1720
01:23:04,830 --> 01:23:07,249
>> En átta sig hversu fljótt
Þessi tegund af umræðu

1721
01:23:07,249 --> 01:23:10,540
stigmagna, annaðhvort svo langt að það er góður
af yfir höfuð manns á þessum tímapunkti, sem

1722
01:23:10,540 --> 01:23:11,360
er fínt.

1723
01:23:11,360 --> 01:23:18,820
En við byrjuðum, muna, með sannarlega
eitthvað lágmark-láréttur flötur og rafræn.

1724
01:23:18,820 --> 01:23:20,819
Og svo þetta aftur er þetta
þema abstrakt,

1725
01:23:20,819 --> 01:23:23,610
þar þegar þú byrjar að taka til
veitt, OK, ég hef fengið it-- það er

1726
01:23:23,610 --> 01:23:26,680
líkamlegur minni, OK, fékk það, hver
líkamlegur staðsetning hefur heimilisfang,

1727
01:23:26,680 --> 01:23:29,910
OK, ég fékk það, get ég tákna
þessir heimilisföng sem arrows--

1728
01:23:29,910 --> 01:23:34,650
þú getur mjög fljótt að byrja að hafa
flóknari samtöl sem

1729
01:23:34,650 --> 01:23:38,360
á endanum virðast vera að leyfa okkur
til að leysa vandamál eins og að leita

1730
01:23:38,360 --> 01:23:41,620
og flokkun á skilvirkari hátt.

1731
01:23:41,620 --> 01:23:44,190
Og treyst, too--
vegna þess að ég held að þetta

1732
01:23:44,190 --> 01:23:48,700
er dýpsta sem við höfum farið í nokkrar
þessara CS viðfangsefnum proper-- við höfum

1733
01:23:48,700 --> 01:23:51,880
gera í dag og hálfan á þetta
benda hvað þú gætir venjulega gera yfir

1734
01:23:51,880 --> 01:23:55,520
auðvitað af átta vikur í önn.

1735
01:23:55,520 --> 01:23:59,670
>> Einhverjar spurningar um þetta?

1736
01:23:59,670 --> 01:24:01,100
Nei?

1737
01:24:01,100 --> 01:24:01,940
Allt í lagi.

1738
01:24:01,940 --> 01:24:05,610
Ja, hvers vegna eigum við ekki að staldra þar,
byrja hádegismat nokkrar mínútur snemma,

1739
01:24:05,610 --> 01:24:07,052
halda áfram í bara um klukkutíma?

1740
01:24:07,052 --> 01:24:08,760
Og ég sitja fyrir
svolítið með spurningum.

1741
01:24:08,760 --> 01:24:11,343
Þá er ég að fara að fara
taka nokkrar símtöl ef það er í lagi.

1742
01:24:11,343 --> 01:24:15,000
Ég kveiki á smá tónlist í millitíðinni,
en hádegisverður ætti að vera handan við hornið.

1743
01:24:15,000 --> 01:24:17,862