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

2
00:00:00,030 --> 00:00:00,460
>> DAVID Humala: Hea küll.

3
00:00:00,460 --> 00:00:01,094
Me oleme tagasi.

4
00:00:01,094 --> 00:00:04,260
Nii et selles segmendis programmeerimine mida
Ma arvasin, et me tahaks teha on segu asju.

5
00:00:04,260 --> 00:00:06,340
Üks, teha natuke
midagi praktilist,

6
00:00:06,340 --> 00:00:08,690
kuigi kasutades rohkem mänguline
programmeerimine environment--

7
00:00:08,690 --> 00:00:11,620
üks, mis on demonstratiivne kohta
täpselt liiki ideed

8
00:00:11,620 --> 00:00:14,220
oleme rääkinud,
kuid veidi rohkem formaalselt.

9
00:00:14,220 --> 00:00:18,200
Kaks, mõningaid
rohkem tehniliste viise

10
00:00:18,200 --> 00:00:21,520
et programmeerija tegelikult lahendada
probleeme nagu otsides probleem

11
00:00:21,520 --> 00:00:24,530
et me vaatasime enne ja
Samuti põhilisemalt

12
00:00:24,530 --> 00:00:26,020
huvitav probleem sorteerimine.

13
00:00:26,020 --> 00:00:28,840
>> Me lihtsalt eeldada saanud minna
et see telefoniraamat oli järjestatud,

14
00:00:28,840 --> 00:00:31,980
kuid üksi on tegelikult omamoodi
raske probleem paljudel erinevatel viisidel

15
00:00:31,980 --> 00:00:32,479
seda lahendada.

16
00:00:32,479 --> 00:00:34,366
Nii me kasutame neid kui
klassi probleeme

17
00:00:34,366 --> 00:00:36,740
esindaja asju, mis
võiks lahendada üldiselt.

18
00:00:36,740 --> 00:00:38,980
Ja siis me räägime
umbes üsna üksikasjalikult, mida

19
00:00:38,980 --> 00:00:42,360
nimetatakse andmete structures--
Kasvataja viisil nagu ahelloendid

20
00:00:42,360 --> 00:00:46,290
ja hash tabelid ja puud, mis
Programmeerija tegelikult

21
00:00:46,290 --> 00:00:48,890
kasutada ja üldiselt kasutada
tahvlile joonistada

22
00:00:48,890 --> 00:00:51,840
pildi, mida ta
piltlikult ette kujutada rakendamise

23
00:00:51,840 --> 00:00:52,980
mõned tükk tarkvara.

24
00:00:52,980 --> 00:00:55,130
>> Nii teeme käed-osa esimene.

25
00:00:55,130 --> 00:01:00,090
Nii lihtsalt saada oma käed määrdunud koos
keskkonda nimetatakse scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
See on vahend, mida me kasutame
Meie bakalaureuse klassi.

27
00:01:02,636 --> 00:01:04,510
Kuigi see on mõeldud
vanuses 12 ja üles,

28
00:01:04,510 --> 00:01:07,570
Me kasutame seda üles
osa, et üsna vähe

29
00:01:07,570 --> 00:01:10,020
kuna see on kena, lõbus
graafiline viis õppimiseks

30
00:01:10,020 --> 00:01:12,160
natuke midagi programmeerimisest.

31
00:01:12,160 --> 00:01:17,600
Nii pea, et URL, kus te
peaks näha lehe päris niimoodi,

32
00:01:17,600 --> 00:01:23,330
ja minna ja kliki
Liitu Scratch ülevalt paremalt

33
00:01:23,330 --> 00:01:28,300
ja valida kasutajanimi ja
parooli ning lõpuks saan ise

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

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

36
00:01:32,165 --> 00:01:34,665
Ma mõtlesin, et ma kasutada seda kui
võimalust esimesena näidata.

37
00:01:34,665 --> 00:01:39,120
Küsimus tulid Vaheajal
mida koodi tegelikult välja näeb.

38
00:01:39,120 --> 00:01:41,315
Ja rääkisime
Vaheajal umbes C,

39
00:01:41,315 --> 00:01:45,060
aastal particular-- iseäranis
madalamal tasemel vanem keel.

40
00:01:45,060 --> 00:01:47,750
Ja ma lihtsalt tegin kiire
Google'i otsing leida C koodi

41
00:01:47,750 --> 00:01:51,574
kahe- otsingu algoritmi, et me
kasutatakse otsida, et telefoniraamatus varem.

42
00:01:51,574 --> 00:01:54,240
See konkreetne näide muidugi
ei otsi telefoniraamatust.

43
00:01:54,240 --> 00:01:57,840
See lihtsalt otsib terve hulk
numbrite arvuti mällu.

44
00:01:57,840 --> 00:02:01,000
Aga kui te soovite lihtsalt saada visuaalne
tunnet, mida tegelik programmeerimine

45
00:02:01,000 --> 00:02:05,370
keele välja näeb, tundub
natuke midagi sellist.

46
00:02:05,370 --> 00:02:09,759
Nii et see on umbes 20-pluss,
30 või nii rida koodi,

47
00:02:09,759 --> 00:02:12,640
kuid vestlus me
olid võttes üle break

48
00:02:12,640 --> 00:02:16,000
oli, kuidas see tegelikult
saab aga välja ühtede ja nullide

49
00:02:16,000 --> 00:02:19,200
ja kui sa ei saa lihtsalt tagasi, et
töödelda ja lähevad ühtede ja nullide

50
00:02:19,200 --> 00:02:20,210
tagasi üles koodi.

51
00:02:20,210 --> 00:02:22,620
>> Kahjuks protsessi
on nii teosed

52
00:02:22,620 --> 00:02:24,890
et see on palju lihtsam öelda kui teha.

53
00:02:24,890 --> 00:02:29,400
Ma läksin edasi ja tegelikult välja
et programm, Binary Search,

54
00:02:29,400 --> 00:02:32,700
arvesse ühtede ja nullide teel
programm nimega kompilaator, et ma

55
00:02:32,700 --> 00:02:34,400
juhtumisi on siin just minu Mac.

56
00:02:34,400 --> 00:02:37,850
Ja kui te vaatate ekraani
siin, keskendudes eelkõige

57
00:02:37,850 --> 00:02:43,520
Nende keskel sammastele ainult
näete ainult ühtede ja nullide.

58
00:02:43,520 --> 00:02:48,290
Ja need on ühtede ja nullide et
kirjutada täpselt, et otsimise programmi.

59
00:02:48,290 --> 00:02:53,720
>> Ja nii iga tüki viis bitti,
Iga bait ühtede ja nullide siin

60
00:02:53,720 --> 00:02:57,310
moodustavad umbes juhendamine
tüüpiliselt sees arvutis.

61
00:02:57,310 --> 00:03:00,730
Ja tegelikult, kui olete kuulnud
marketing hüüdlause "Intel inside" -, et

62
00:03:00,730 --> 00:03:04,610
Loomulikult tähendab lihtsalt teil on
Intel CPU või aju sees arvutit.

63
00:03:04,610 --> 00:03:08,000
Ja mida see tähendab olla CPU on
et teil on käsustik

64
00:03:08,000 --> 00:03:08,840
niiöelda.

65
00:03:08,840 --> 00:03:11,620
>> Iga protsessori maailmas, paljud
neist valmistatud Intel nendel päevadel,

66
00:03:11,620 --> 00:03:13,690
mõistab piiratud
arvu juhiseid.

67
00:03:13,690 --> 00:03:18,690
Ja need juhised on nii madalal tasemel
kui lisada need kaks numbrit kokku

68
00:03:18,690 --> 00:03:22,560
korrutab need kaks numbrit kokku
seda malendit liigutada andmeid siit

69
00:03:22,560 --> 00:03:27,340
Siia mällu salvestada see
info siit siiani mälus,

70
00:03:27,340 --> 00:03:32,200
ja nii forth-- nii väga
madala peaaegu elektroonilise üksikasju.

71
00:03:32,200 --> 00:03:34,780
Aga nende matemaatiliste
toimingud on ühendatud

72
00:03:34,780 --> 00:03:37,410
mida me varem käsitletud,
esindatus andmeid

73
00:03:37,410 --> 00:03:40,450
kui ühtede ja nullide, saab
sa luua kõike

74
00:03:40,450 --> 00:03:44,180
et arvuti saab teha täna, kas
see on tekstiline, graafiline, muusika-,

75
00:03:44,180 --> 00:03:45,580
või muidu.

76
00:03:45,580 --> 00:03:49,450
>> Nii et see on väga lihtne saada
kadunud umbrohi kiiresti.

77
00:03:49,450 --> 00:03:52,150
Ja seal on palju
süntaktiline väljakutseid

78
00:03:52,150 --> 00:03:56,630
kusjuures, kui sa teed kõige lihtsam,
stupidest kirjavigu ükski programm

79
00:03:56,630 --> 00:03:57,860
töötab üldse.

80
00:03:57,860 --> 00:04:00,366
Ja nii selle asemel
keeles nagu C täna hommikul

81
00:04:00,366 --> 00:04:02,240
Ma arvasin, et see oleks
lõbusam tegelikult teha

82
00:04:02,240 --> 00:04:04,840
midagi visuaalset, mis
samas mõeldud lastele

83
00:04:04,840 --> 00:04:08,079
on tegelikult ideaalne ilming
tegeliku programmeerimine

84
00:04:08,079 --> 00:04:10,370
language-- lihtsalt juhtub
Piltide kasutamine teksti asemel

85
00:04:10,370 --> 00:04:11,710
esindada neid ideid.

86
00:04:11,710 --> 00:04:15,470
>> Nii et kui sa tõepoolest olla
konto scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
nupu Loo
ülevalt vasakult kohas.

88
00:04:21,070 --> 00:04:24,620
Ja sa peaksid nägema keskkonnas nagu
mida ma olen umbes et näha minu ekraanil

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

90
00:04:26,310 --> 00:04:29,350
Ja me kulutada vaid veidi
natuke aega mänginud siin.

91
00:04:29,350 --> 00:04:34,080
Vaatame, kas me ei suuda kõiki lahendada mõned
probleemid koos järgmisel viisil.

92
00:04:34,080 --> 00:04:39,420
>> Nii et mida te näete selles
environment-- ja tegelikult lihtsalt lasta

93
00:04:39,420 --> 00:04:40,050
mind mõtlema.

94
00:04:40,050 --> 00:04:42,680
Kas keegi ei ole siin?

95
00:04:42,680 --> 00:04:45,070
Mitte siin?

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

97
00:04:45,800 --> 00:04:49,030
Nii et lubage mul rõhutada paari
omadusi selles keskkonnas.

98
00:04:49,030 --> 00:04:55,024
>> Nii ülaosas vasakul ekraani, me
on Scratch etappi, nii rääkida.

99
00:04:55,024 --> 00:04:57,440
Kraabi ei ole ainult nimi
Selle programmeerimiskeele;

100
00:04:57,440 --> 00:05:00,356
see on ka nimi kass, et
näed vaikimisi seal oranž.

101
00:05:00,356 --> 00:05:02,160
Ta on laval, nii
palju nagu ma kirjeldasin

102
00:05:02,160 --> 00:05:05,770
kilpkonn varem olles
ristkülikukujuline valge tahvel keskkond.

103
00:05:05,770 --> 00:05:09,800
See kassi maailma piirdub täielikult
Selle ristküliku kuni ülemise seal.

104
00:05:09,800 --> 00:05:12,210
>> Vahepeal, paremal
pool siin, see on

105
00:05:12,210 --> 00:05:15,610
vaid skripte alal,
puhtalt lehelt, kui soovite.

106
00:05:15,610 --> 00:05:18,590
See on koht, kus me ei kavatse kirjutada
Meie programmid hetk.

107
00:05:18,590 --> 00:05:22,935
Ja ehituskivid, et me
kasuta kirjutada selle program-- puzzle

108
00:05:22,935 --> 00:05:25,310
tükki, kui te will-- on
need siin keset,

109
00:05:25,310 --> 00:05:27,500
ja nad liigitada
funktsiooni järgi.

110
00:05:27,500 --> 00:05:31,000
Nii näiteks, et ma lähen edasi minna
ja annavad vähemalt üks neist.

111
00:05:31,000 --> 00:05:33,690
Ma lähen edasi minna ja kliki
Control kategooria kuni top.

112
00:05:33,690 --> 00:05:35,720
>> Nii et need on kategooriad, kuni top.

113
00:05:35,720 --> 00:05:39,410
Ma lähen käsku Control kategooriasse.

114
00:05:39,410 --> 00:05:44,020
Pigem ma lähen klõpsake sündmused
kategooria, kõige esimene kuni top.

115
00:05:44,020 --> 00:05:47,790
Ja kui soovite jälgida mööda isegi
nagu me seda teha, sa oled üsna teretulnud.

116
00:05:47,790 --> 00:05:52,180
Ma lähen klõpsa ja lohista see
Esimene, "kui roheline lipp klõpsatud."

117
00:05:52,180 --> 00:05:58,410
Ja siis ma lähen tilk seda lihtsalt
umbes ülaosas minu tühi tahvlid.

118
00:05:58,410 --> 00:06:01,450
>> Ja mis tore Scratch
on see, et see pusletükk, kui

119
00:06:01,450 --> 00:06:04,560
blokeerituks teiste puzzle
tükki, kavatseb teha sõna otseses mõttes

120
00:06:04,560 --> 00:06:06,460
millised need puzzle tükid öelda seda teha.

121
00:06:06,460 --> 00:06:09,710
Nii näiteks Scratch on õige
nüüd keset oma maailma.

122
00:06:09,710 --> 00:06:14,660
Ma lähen edasi minna ja valida
Nüüd oletame, Motion kategoorias

123
00:06:14,660 --> 00:06:18,000
Kui soovite teha
same-- Resolutsiooni kategooriasse.

124
00:06:18,000 --> 00:06:20,430
Ja nüüd märgata Mul on terve
kamp puzzle tükki siin

125
00:06:20,430 --> 00:06:23,370
veel kord, et sellist teha, mida nad ütlevad.

126
00:06:23,370 --> 00:06:28,110
Ja ma lähen edasi minna ja tõmmata ja
tilk liikuda blokeerida õigus siin.

127
00:06:28,110 --> 00:06:31,860
>> Ja märgata, et niipea, kui saad
põhja lähedal "rohelise lipu

128
00:06:31,860 --> 00:06:34,580
klõpsatud "nuppu, teate
kuidas valge joon tundub,

129
00:06:34,580 --> 00:06:36,950
nagu ta on peaaegu
magnet, ta tahab sinna minna.

130
00:06:36,950 --> 00:06:43,070
Lihtsalt lase minna, ja ta haarab
koos ja kuju sobib.

131
00:06:43,070 --> 00:06:46,620
Ja nüüd saab ehk peaaegu
arvan, et kui me läheme seda.

132
00:06:46,620 --> 00:06:51,570
>> Kui te vaatate Scratch etapi
siin ja vaadata selle peale,

133
00:06:51,570 --> 00:06:55,142
näete punane valgus,
stop märk ja roheline lipp.

134
00:06:55,142 --> 00:06:57,100
Ja ma lähen edasi minna
ja vaadata minu screen--

135
00:06:57,100 --> 00:06:58,460
hetkeks, kui saaksid.

136
00:06:58,460 --> 00:07:01,960
Ma lähen klõpsa
roheline lipp kohe,

137
00:07:01,960 --> 00:07:07,850
ja ta kolis mis tundub olevat 10 sammu
või 10 pikslit, 10 punkti, ekraanile.

138
00:07:07,850 --> 00:07:13,390
>> Ja nii ei ole, et põnev,
kuid lubage mul pakkuda

139
00:07:13,390 --> 00:07:17,440
isegi õpetades seda, lihtsalt
abil ise oma intuition-- let

140
00:07:17,440 --> 00:07:22,560
mulle ettepaneku, et te saate aru saada, kuidas
teha Scratch Kõnnid laval.

141
00:07:22,560 --> 00:07:28,700
Kas ta teha ruumi paremal pool
ekraani, kõik viis õigus.

142
00:07:28,700 --> 00:07:32,200
Annan hetk
või nii maadelda, et.

143
00:07:32,200 --> 00:07:37,681
Võiksid vaatleme
teiste kategooriate plokid.

144
00:07:37,681 --> 00:07:38,180
Hästi.

145
00:07:38,180 --> 00:07:41,290
Nii lihtsalt sulgege, kui meil on
roheline lipp klõpsatud siin

146
00:07:41,290 --> 00:07:44,850
ja liikuda 10 sammu on
ainult juhendamise, iga kord, kui ma

147
00:07:44,850 --> 00:07:46,720
nuppu roheline lipp, mis toimub?

148
00:07:46,720 --> 00:07:50,070
Noh, see töötab minu programm.

149
00:07:50,070 --> 00:07:52,450
Nii et ma võiks seda teha
võibolla 10 korda käsitsi

150
00:07:52,450 --> 00:07:55,130
aga see tundub natuke
natuke hackish, nii-öelda

151
00:07:55,130 --> 00:07:57,480
kusjuures ma ei ole tõesti
probleemi lahendamisele.

152
00:07:57,480 --> 00:08:00,530
Ma lihtsalt üritan uuesti ja
uuesti ja uuesti ja uuesti

153
00:08:00,530 --> 00:08:03,180
kuni ma justkui kogemata
saavutada direktiivi

154
00:08:03,180 --> 00:08:05,560
et ma sätestatud, et saavutada varem.

155
00:08:05,560 --> 00:08:08,200
>> Aga me teame, meie
pseudokoodi varem, et seal on

156
00:08:08,200 --> 00:08:11,870
seda mõistet programmeerimine kordaminelooping,
midagi ikka ja jälle.

157
00:08:11,870 --> 00:08:14,888
Ja nii ma nägin, et kamp teile
jõudnud, mida pusletükk?

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

159
00:08:17,870 --> 00:08:18,730
Korda kuni.

160
00:08:18,730 --> 00:08:21,400
Nii et me võiks teha midagi
nagu korrata seni, kuni.

161
00:08:21,400 --> 00:08:23,760
Ja mida sa korrata, kuni täpselt?

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

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

164
00:08:28,540 --> 00:08:31,974
Ja lase mul minna ühega, mis on
mõnevõrra lihtsam hetkeks.

165
00:08:31,974 --> 00:08:33,140
Lubage mul minna ja seda teha.

166
00:08:33,140 --> 00:08:35,559
Pange tähele, et teil võib olla
avastas kontrolli all,

167
00:08:35,559 --> 00:08:38,409
on see korduvus plokk, mis
ei tundu see nii suur.

168
00:08:38,409 --> 00:08:41,039
Seal ei ole palju ruumi
Nende kahe kollane jooned.

169
00:08:41,039 --> 00:08:43,539
Aga nagu mõned teist võib-olla
märganud, kui te lohistada,

170
00:08:43,539 --> 00:08:45,150
märgata, kuidas ta kasvab, et täita kuju.

171
00:08:45,150 --> 00:08:46,274
>> Ja võite isegi tuupima rohkem.

172
00:08:46,274 --> 00:08:48,670
See muudkui kasvab, kui
lohistamise ja viid selle üle.

173
00:08:48,670 --> 00:08:51,110
Ja ma ei tea, mis on
Parim siin, nii et let

174
00:08:51,110 --> 00:08:54,760
mulle vähemalt korrata viis korda, sest
Näiteks ja siis tagasi minna lavale

175
00:08:54,760 --> 00:08:56,720
ja nuppu roheline lipp.

176
00:08:56,720 --> 00:08:59,110
Ja nüüd märkate see ei ole päris seal.

177
00:08:59,110 --> 00:09:02,400
>> Nüüd mõned teist kavandataval
Victoria lihtsalt ei korrata 10 korda.

178
00:09:02,400 --> 00:09:05,140
Ja et üldiselt ei
saada teda kogu tee,

179
00:09:05,140 --> 00:09:10,510
kuid siis ei tekiks tugevam
viis kui meelevaldselt figuring

180
00:09:10,510 --> 00:09:12,640
kui palju liigub teha?

181
00:09:12,640 --> 00:09:17,680
Mis võiks olla parem plokk
kordavad 10 korda olla?

182
00:09:17,680 --> 00:09:20,380
>> Jah, miks mitte teha midagi igavesti?

183
00:09:20,380 --> 00:09:24,390
Ja nüüd lubage mul liikuda selles puzzle tükk
sees olemas ja vabaneda seda.

184
00:09:24,390 --> 00:09:28,300
Nüüd märkate ükskõik kus Scratch
algab, läheb ta serva.

185
00:09:28,300 --> 00:09:30,700
Ja õnneks MIT,
kes teeb Scratch, lihtsalt

186
00:09:30,700 --> 00:09:33,190
tagab, et ta ei ole kunagi
kaob täielikult.

187
00:09:33,190 --> 00:09:35,360
Teil on alati võimalik haarata oma saba.

188
00:09:35,360 --> 00:09:37,680
>> Ja just intuitiivselt,
miks ta edasi liikuma?

189
00:09:37,680 --> 00:09:38,892
Mis siin toimub?

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

191
00:09:41,440 --> 00:09:43,824
Ta tundub olevat peatunud, kuid
siis kui ma kiirenemist ja lohista

192
00:09:43,824 --> 00:09:45,240
ta hoiab, kes tahavad minna sinna.

193
00:09:45,240 --> 00:09:46,123
Miks nii?

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

195
00:09:51,610 --> 00:09:54,360
Tõesti, arvuti on sõna otseses mõttes
kavatseb teha, mida sa öelda tahad.

196
00:09:54,360 --> 00:09:58,380
Nii et kui sa ütlesid seda varem teha
järgmised asi igavesti liikuma 10 sammu,

197
00:09:58,380 --> 00:10:01,860
see läheb edasi minema ja läheb
kuni ma tabanud punane stop märk

198
00:10:01,860 --> 00:10:04,620
ja lõpetada programmi kokku.

199
00:10:04,620 --> 00:10:06,610
>> Nii et isegi kui sa ei ole
Selleks, kuidas ma

200
00:10:06,610 --> 00:10:09,510
teha Scratch liikuda kiiremini
üle ekraani?

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

202
00:10:12,060 --> 00:10:13,280
Rohkem samme, eks?

203
00:10:13,280 --> 00:10:15,710
Nii et selle asemel tee 10
korraga, miks me ei

204
00:10:15,710 --> 00:10:20,100
minna ja muuta see mina--
mida sa propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Nüüd ma lähen nuppu roheline
lipp ja tõepoolest, ta läheb väga kiiresti.

206
00:10:24,410 --> 00:10:27,180
>> Ja see muidugi on lihtsalt
ilming animatsiooni.

207
00:10:27,180 --> 00:10:28,060
Mis on animatsioon?

208
00:10:28,060 --> 00:10:33,090
See lihtsalt näitab teile Inimese
terve hunnik pilte tõesti,

209
00:10:33,090 --> 00:10:34,160
tõesti, tõesti kiire.

210
00:10:34,160 --> 00:10:36,500
Ja kui me lihtsalt ütlen
teda liigutada rohkem samme,

211
00:10:36,500 --> 00:10:39,750
me lihtsalt võttes mõju olema
muutus, kus ta on ekraanil

212
00:10:39,750 --> 00:10:42,900
kõik kiiremini ajaühikus.

213
00:10:42,900 --> 00:10:46,454
>> Nüüd järgmine väljakutse, et ma pakutud
pidi ta põrgatama off serval.

214
00:10:46,454 --> 00:10:49,120
Ja teadmata, mida puzzle
tükki exist--, sest see on hea

215
00:10:49,120 --> 00:10:53,030
kui te ei saada
etapi challenge-- mida

216
00:10:53,030 --> 00:10:54,280
sa tahad teha intuitiivselt?

217
00:10:54,280 --> 00:10:58,030
Kuidas me teda põrge tagasi ja
edasi, vahel vasakule ja paremale?

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

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

220
00:11:03,810 --> 00:11:05,680
Seega on meil vaja mingisugust
seisundis, ja me

221
00:11:05,680 --> 00:11:09,710
tundub, et on conditionals, nii et
rääkida, kontrolli all kategooriasse.

222
00:11:09,710 --> 00:11:14,110
Milline neist plokid
me ilmselt tahavad?

223
00:11:14,110 --> 00:11:15,200
Jah, võib-olla ", kui siis."

224
00:11:15,200 --> 00:11:18,780
Nii märgata, et üks kollane plokid
meil siin on see "kui"

225
00:11:18,780 --> 00:11:23,920
või seda ", kui muidu" plokk, mis
võimaldab meil teha otsus seda teha

226
00:11:23,920 --> 00:11:25,000
või seda teha.

227
00:11:25,000 --> 00:11:27,380
Ja võite isegi istutada
teha mitu asja.

228
00:11:27,380 --> 00:11:34,910
Või kui olete ei läinud siin veel,
minna kuni Sensing kategooria

229
00:11:34,910 --> 00:11:39,612
Ja-- vaatame, kas see on siin.

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

231
00:11:43,050 --> 00:11:52,050
>> Mida plokk võib olla kasulik siin
avastada, kui ta on laval?

232
00:11:52,050 --> 00:11:56,740
Jah, märkate, et mõned neist plokid
saab parametriseerisin, nii rääkida.

233
00:11:56,740 --> 00:12:00,706
Neid saab omamoodi kohandatud, ei
Erinevalt HTML eile atribuute,

234
00:12:00,706 --> 00:12:03,330
kus need atribuudid liiki
kohandada käitumist silt.

235
00:12:03,330 --> 00:12:08,880
Samamoodi siin, ma saan rüütama see liigutav
blokeerida ja muutmine ning küsida,

236
00:12:08,880 --> 00:12:11,500
sa puudutamata hiir
osuti nagu kursor

237
00:12:11,500 --> 00:12:13,250
või on teil puudutamata serva?

238
00:12:13,250 --> 00:12:15,210
>> Nii et lubage mul minna ja seda teha.

239
00:12:15,210 --> 00:12:18,130
Ma lähen välja suumida hetkeks.

240
00:12:18,130 --> 00:12:21,320
Lubage mul rüütama see pusletükk
siin see pusletükk seda,

241
00:12:21,320 --> 00:12:24,570
ja ma lähen pudi-padi
neid hetkeks.

242
00:12:24,570 --> 00:12:27,620
Ma lähen liikuda selles,
muuta see liigutav serva,

243
00:12:27,620 --> 00:12:38,590
ja ma lähen algatusel seda teha.

244
00:12:38,590 --> 00:12:40,490
Nii et siin on mõned koostisosad.

245
00:12:40,490 --> 00:12:42,570
Ma arvan, et mul on kõik, mida ma tahan.

246
00:12:42,570 --> 00:12:47,710
>> Kas keegi tahaks pakkuda, kuidas ma
saab ühendada neid võibolla ülevalt alla

247
00:12:47,710 --> 00:12:52,020
et lahendada probleemi, millel
Scratch liikuda paremalt vasakule paremale

248
00:12:52,020 --> 00:12:57,020
vasakult paremale vasakule, iga
aega lihtsalt kopsakas seina?

249
00:12:57,020 --> 00:12:58,050
Mida ma tahan teha?

250
00:12:58,050 --> 00:13:01,097
Mis blokeerivad ma peaksin ühendada
"Kui roheline lipp klõpsatud esimene"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, nii et alustame koos "igavesti."

253
00:13:06,200 --> 00:13:07,170
Mis läheb sees edasi?

254
00:13:07,170 --> 00:13:10,290
Keegi teine.

255
00:13:10,290 --> 00:13:11,850
OK, liikuda samme.

256
00:13:11,850 --> 00:13:12,350
Hästi.

257
00:13:12,350 --> 00:13:14,470
Siis mida?

258
00:13:14,470 --> 00:13:15,120
Nii siis, kui.

259
00:13:15,120 --> 00:13:17,720
Ja märgata, kuigi see näeb
kihi tihedalt kokku,

260
00:13:17,720 --> 00:13:19,500
see lihtsalt kasvab täita.

261
00:13:19,500 --> 00:13:21,500
See lihtsalt hüpata, kui ma tahan seda.

262
00:13:21,500 --> 00:13:25,920
>> Ja mida ma panen vahel
IF ja siis?

263
00:13:25,920 --> 00:13:27,180
Ilmselt ", kui liigutav serva."

264
00:13:27,180 --> 00:13:31,800
Ja teate, jälle, see on liiga suur
seda, kuid see kasvab täita.

265
00:13:31,800 --> 00:13:35,002
Ja siis keera 15 kraadi?

266
00:13:35,002 --> 00:13:35,710
Mitu kraadi?

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

268
00:13:38,800 --> 00:13:41,196
Jah, nii et 180 on spin
mul kõik vastupidi.

269
00:13:41,196 --> 00:13:42,570
Vaatame, kas ma sain selle õige.

270
00:13:42,570 --> 00:13:43,930
Lubage mul suumimiseks.

271
00:13:43,930 --> 00:13:45,130
>> Lubage mul lohistada Scratch üles.

272
00:13:45,130 --> 00:13:50,030
Nii ta on natuke moonutatud
nüüd, kuid see on hea.

273
00:13:50,030 --> 00:13:52,231
Kuidas nullida teda lihtsalt?

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

275
00:13:59,879 --> 00:14:01,045
Ma lähen petta kergelt.

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

277
00:14:04,074 --> 00:14:05,990
Nii et ma olen lisades teise
plokk, vaid peab olema selge.

278
00:14:05,990 --> 00:14:08,424
Ma tahan, et ta punktist 90 kraadi
paremale vaikimisi

279
00:14:08,424 --> 00:14:10,840
nii et ma lihtsalt lähen talle öelda
mida teha, et programmiliselt.

280
00:14:10,840 --> 00:14:11,632
Ja siin me läheme.

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

282
00:14:14,740 --> 00:14:15,740
Tundub, et me oleme seda teinud.

283
00:14:15,740 --> 00:14:19,980
See on natuke imelik, sest
ta kõnnib tagurpidi.

284
00:14:19,980 --> 00:14:21,250
Kutsume mis viga.

285
00:14:21,250 --> 00:14:22,120
See on viga.

286
00:14:22,120 --> 00:14:27,320
Viga on viga programmi, ilmub
loogikaviga, et mina, inimene, tehtud.

287
00:14:27,320 --> 00:14:28,985
Miks ta läheb tagurpidi?

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

289
00:14:33,560 --> 00:14:35,250
Kas MIT kruvi üles või tegi olen?

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

291
00:14:38,840 --> 00:14:42,550
>> Jah, ma mõtlen, et see ei ole MIT
süü. Nad andsid mulle pusletükk

292
00:14:42,550 --> 00:14:44,970
mis ütleb omakorda mõned arvu kraadi.

293
00:14:44,970 --> 00:14:47,672
Ja Victoria ettepanekut,
Ma keeran 180 kraadi,

294
00:14:47,672 --> 00:14:48,880
mis on õige intuitsiooni.

295
00:14:48,880 --> 00:14:53,700
Aga keerates 180 kraadi sõna otseses mõttes
tähendab keerates 180 kraadi,

296
00:14:53,700 --> 00:14:55,860
ja see ei ole tõesti
mida ma tahan, ilmselt.

297
00:14:55,860 --> 00:14:58,026
Sest vähemalt ta on
See kahemõõtmeline maailm,

298
00:14:58,026 --> 00:15:00,740
nii pöördepunkt tegelikult toimub
klapp teda tagurpidi.

299
00:15:00,740 --> 00:15:04,030
>> Ma ilmselt soovite kasutada milline plokk
selle asemel, selle põhjal, mida te näete siin?

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

301
00:15:11,890 --> 00:15:14,790
Kuidas võiks me seda parandada?

302
00:15:14,790 --> 00:15:18,380
Jah, nii et me võiks juhtida
vastupidises suunas.

303
00:15:18,380 --> 00:15:22,300
Ja tegelikult isegi see
ei kavatse olla piisavalt,

304
00:15:22,300 --> 00:15:26,410
sest saame ainult kõva koodi
juhtides vasakule või paremale.

305
00:15:26,410 --> 00:15:27,920
>> Sa tead, mida me võiksime teha?

306
00:15:27,920 --> 00:15:30,160
Tundub, et meil on
Mugavuse plokk siin.

307
00:15:30,160 --> 00:15:32,987
Kui ma suumida, vaata
midagi meile meeldib siin?

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

309
00:15:36,120 --> 00:15:40,020
Seega tundub, MIT on
võtmiseks ehitatud siin.

310
00:15:40,020 --> 00:15:45,440
See plokk tundub olevat samaväärne
millele teised plokid, mitmuses?

311
00:15:45,440 --> 00:15:49,510
>> See üks plokk tundub olevat samaväärne
et kogu see kolmik plokid

312
00:15:49,510 --> 00:15:50,880
et meil on siin.

313
00:15:50,880 --> 00:15:54,670
Nii selgub võin lihtsustada minu
Programm vabanemiseks kõik, et

314
00:15:54,670 --> 00:15:58,270
ja lihtsalt panna see siia.

315
00:15:58,270 --> 00:16:01,620
Ja nüüd on ta ikka natuke
lollakas, ja see on hea nüüd.

316
00:16:01,620 --> 00:16:03,370
Me jätan selle olla.

317
00:16:03,370 --> 00:16:06,000
Aga minu programm on isegi
lihtsamad ning ka see

318
00:16:06,000 --> 00:16:09,060
Oleks esindaja
on eesmärk programming--

319
00:16:09,060 --> 00:16:13,430
on ideaalis teha oma koodi
lihtne, võimalikult kompaktne,

320
00:16:13,430 --> 00:16:15,650
ja samal ajal kui
loetav kui võimalik.

321
00:16:15,650 --> 00:16:20,310
Sa ei taha, et see nii sisutihedat
et see on raske aru saada.

322
00:16:20,310 --> 00:16:22,826
>> Aga märgata Olen asendatakse
kolme ploki ühe,

323
00:16:22,826 --> 00:16:24,200
ja see on vaieldamatult hea.

324
00:16:24,200 --> 00:16:27,280
Olen ammutatud minema ettekujutuse
kontrollida, kas sa oled

325
00:16:27,280 --> 00:16:29,120
äärel vaid ühe ploki.

326
00:16:29,120 --> 00:16:31,520
Nüüd saame nautige seda tegelikult.

327
00:16:31,520 --> 00:16:35,790
See ei lisa nii palju
intellektuaalne väärtus, kuid mänguline väärtus.

328
00:16:35,790 --> 00:16:39,730
Ma lähen edasi minna
ja haarata seda heli siin.

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

330
00:16:42,900 --> 00:16:46,420
Nii et lubage mul minna ja las ma
stop programm hetkeks.

331
00:16:46,420 --> 00:16:52,070
Ma lähen salvestama,
võimaldades juurdepääsu oma mikrofoni.

332
00:16:52,070 --> 00:16:53,181
>> Siin me läheme.

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

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

335
00:16:58,710 --> 00:17:01,140
Proovime uuesti.

336
00:17:01,140 --> 00:17:02,279
Siin me läheme.

337
00:17:02,279 --> 00:17:03,570
OK, ma salvestatud vale asi.

338
00:17:03,570 --> 00:17:04,580
Siin me läheme.

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

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

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

342
00:17:08,800 --> 00:17:09,300
Hästi.

343
00:17:09,300 --> 00:17:10,791
Nüüd on mul vaja vabaneda sellest.

344
00:17:10,791 --> 00:17:11,290
Hästi.

345
00:17:11,290 --> 00:17:13,950
>> Nüüd on mul
salvestamine lihtsalt "Ai".

346
00:17:13,950 --> 00:17:18,040
Nüüd ma lähen
käia ja nimetame seda "Ai".

347
00:17:18,040 --> 00:17:20,270
Ma lähen tagasi
minu skripte ja nüüd

348
00:17:20,270 --> 00:17:25,460
teate seal on see plokk, mis nimetatakse
mängida heli "mjäu" või mängida heli "Ai".

349
00:17:25,460 --> 00:17:28,920
Ma lähen lohista see, ja kus
ma peaksin seda koomilise efekti?

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

351
00:17:31,740 --> 00:17:37,860
Jah, nii et nüüd on selline
lollakas, sest nüüd on see block--

352
00:17:37,860 --> 00:17:42,050
märgata, kuidas see "kui serv,
põrge "on selline iseseisev.

353
00:17:42,050 --> 00:17:43,704
Nii et ma pean seda parandada.

354
00:17:43,704 --> 00:17:44,870
Lubage mul minna ja seda teha.

355
00:17:44,870 --> 00:17:48,630
Lubage mul vabaneda sellest ja mine tagasi
meie originaal, tahtlik

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

357
00:17:49,870 --> 00:18:01,080
Nii "kui liigutav serva, siis" Ma tahan
pöörduda, kui Victoria ettepaneku,

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

359
00:18:02,480 --> 00:18:05,497
Ja ma tahan mängida
heli "Ai" on?

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

361
00:18:11,800 --> 00:18:15,580
>> Jah, märgata on väljaspool
et kollane plokk.

362
00:18:15,580 --> 00:18:17,680
Nii ka see oleks
viga, aga ma olen märganud seda.

363
00:18:17,680 --> 00:18:21,290
Nii et ma lähen lohista see siia üles
ja teate nüüd on see sees "kui".

364
00:18:21,290 --> 00:18:24,250
Nii et "kui" on selline
samasuguse käe-like blot

365
00:18:24,250 --> 00:18:26,260
See on ainult kavatse
seda, mida on sees on.

366
00:18:26,260 --> 00:18:30,216
Nüüd, kui ma välja suumida juures
riski annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> Arvuti: Ai, Ai, Ai.

369
00:18:36,470 --> 00:18:39,910
>> DAVID Humala: Ja
lihtsalt kesta igavesti.

370
00:18:39,910 --> 00:18:44,160
Nüüd lihtsalt kiirendada asju
siin, las ma minna ja avada,

371
00:18:44,160 --> 00:18:50,460
olgem say-- lase mul minna mõnele
minu enda kraami klassi.

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

373
00:18:53,000 --> 00:19:00,220
Ja las ma avada, oletame, et see
üks tehtud üks meie õpetamise stipendiaatide

374
00:19:00,220 --> 00:19:01,500
paar aastat tagasi.

375
00:19:01,500 --> 00:19:04,732
Nii et mõned teist võib meenutada
Selle mängu Läinud,

376
00:19:04,732 --> 00:19:05,940
ja see on tegelikult märkimisväärne.

377
00:19:05,940 --> 00:19:08,190
Kuigi me oleme teinud
Lihtsaim programmide kohe,

378
00:19:08,190 --> 00:19:09,980
Vaatleme, mida see
tegelikult välja näeb.

379
00:19:09,980 --> 00:19:10,650
Las ma tabanud mängida.

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

381
00:19:14,210 --> 00:19:18,980
>> Nii et selles mängus on meil
konn ja noole abil keys--

382
00:19:18,980 --> 00:19:23,340
Ta võtab suuremaid samme, kui ma mäletada
Mul on kontroll selle konn.

383
00:19:23,340 --> 00:19:29,630
Ja eesmärk on saada kogu hõivatud
tee ilma ulatuvad autod.

384
00:19:29,630 --> 00:19:34,735
Ja olgem see-- kui ma lähen siin, ma
pea ootama logi kerida.

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

386
00:19:38,130 --> 00:19:39,274
See tunne on viga.

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

388
00:19:42,240 --> 00:19:43,495
See on selline viga.

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

390
00:19:45,980 --> 00:19:46,480
Hästi.

391
00:19:46,480 --> 00:19:51,550
Ma olen seda siin,
seal, ja siis hoida

392
00:19:51,550 --> 00:19:54,100
läheb kuni sa saad kõik
konnad lily padjad.

393
00:19:54,100 --> 00:19:55,920
Nüüd see võib tunduda
kõik keerulisemas

394
00:19:55,920 --> 00:19:57,840
aga proovime murda
Selle alla vaimselt

395
00:19:57,840 --> 00:20:00,040
verbaalselt koostisosadeks plokid.

396
00:20:00,040 --> 00:20:03,910
Nii et ilmselt puzzle
tükk, et me ei ole näinud veel

397
00:20:03,910 --> 00:20:07,440
kuid see on vastates klahvivajutusi
asju ma tabanud klaviatuuril.

398
00:20:07,440 --> 00:20:11,660
>> Nii et ilmselt mingi
plokk, mis ütleb, kui võti on võrdne üles

399
00:20:11,660 --> 00:20:15,965
tehke midagi Scratch--
võibolla liigutada 10 sammu sel viisil.

400
00:20:15,965 --> 00:20:20,240
Kui alla vajutatakse, liikuda 10 sammu
Nii või vasakule võti, liikuda 10 sammu

401
00:20:20,240 --> 00:20:21,710
Sel moel 10 sammu, et.

402
00:20:21,710 --> 00:20:23,644
Olen selgelt välja, et kass konn.

403
00:20:23,644 --> 00:20:26,060
Nii et just seal, kus
kostüüm, nagu Scratch kõned see-- me

404
00:20:26,060 --> 00:20:28,440
lihtsalt imporditud pilt konn.

405
00:20:28,440 --> 00:20:29,570
>> Aga mida muud toimub?

406
00:20:29,570 --> 00:20:32,794
Mis muu rida koodi,
mida teised puzzle tükki

407
00:20:32,794 --> 00:20:35,460
tegid Blake, meie õpetamise mehe,
kasutada seda programmi, ilmselt?

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

409
00:20:38,320 --> 00:20:42,730
Mida tehes kõike move--
Mis programmeerimise ehitada?

410
00:20:42,730 --> 00:20:44,950
>> Motion, sure-- nii
liikuda plokk, kindlasti.

411
00:20:44,950 --> 00:20:49,330
Ja mis see on liikuda plokkide
sees, kõige tõenäolisemalt?

412
00:20:49,330 --> 00:20:52,850
Jah, mingi loop, võibolla
igavesti blokeerida, võibolla korrata block--

413
00:20:52,850 --> 00:20:54,070
korrata, kuni plokk.

414
00:20:54,070 --> 00:20:57,330
Ja see on, mis teeb palke ja
liilia padjad ja kõike muud liikuda

415
00:20:57,330 --> 00:20:57,990
edasi-tagasi.

416
00:20:57,990 --> 00:21:00,270
See on lihtsalt juhtub lõputult.

417
00:21:00,270 --> 00:21:03,180
>> Miks on mõned autod
liigub kiiremini kui teised?

418
00:21:03,180 --> 00:21:06,607
Erinevus seisneb selles need programmid?

419
00:21:06,607 --> 00:21:09,690
Jah, ilmselt mõned neist võtavad
rohkem sammu korraga ja mõned neist

420
00:21:09,690 --> 00:21:10,690
vähem etappe korraga.

421
00:21:10,690 --> 00:21:14,670
Ja visuaalne efekt
on kiire vs aeglane.

422
00:21:14,670 --> 00:21:16,030
>> Mis te arvate juhtus?

423
00:21:16,030 --> 00:21:19,700
Kui sain konn kõik viis
üle tänava ja jõe

424
00:21:19,700 --> 00:21:23,560
peale liilia pad, midagi
Tähelepanuväärne juhtus.

425
00:21:23,560 --> 00:21:26,540
Mis juhtus, niipea kui ma tegin seda?

426
00:21:26,540 --> 00:21:27,210
See peatunud.

427
00:21:27,210 --> 00:21:29,680
See konn peatunud ja
Ma sain teise konn.

428
00:21:29,680 --> 00:21:33,155
Nii et mida ehitada tuleb
kasutatakse seal, mida funktsioon?

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

430
00:21:36,020 --> 00:21:38,660
>> Jah, nii et seal on mingi
"Kui" tingimus seal ka.

431
00:21:38,660 --> 00:21:41,909
Ja selgub out-- me ei näe see--
kuid seal on teised plokid olemas, et

432
00:21:41,909 --> 00:21:45,300
Võib öelda, kui teil on liigutav
teine ​​asi ekraanil

433
00:21:45,300 --> 00:21:47,720
kui sa puudutamata liilia pad ", siis."

434
00:21:47,720 --> 00:21:50,810
Ja siis see, kui me
teha teine ​​konn ilmuda.

435
00:21:50,810 --> 00:21:54,969
Nii et kuigi see mäng on kindlasti
väga kuupäevaga, kuigi esmapilgul

436
00:21:54,969 --> 00:21:58,010
seal on nii palju läheb nüüd-- ja Blake
ei piitsutama selle üles kahe minuti jooksul,

437
00:21:58,010 --> 00:22:00,390
see ilmselt võttis ta mitu
tundi, et luua seda mängu

438
00:22:00,390 --> 00:22:03,850
põhineb tema mälu või videod
Läinud versioon sellest.

439
00:22:03,850 --> 00:22:07,940
Aga kõik need väikesed asjad
läheb ekraanil eraldi

440
00:22:07,940 --> 00:22:11,550
Keeta neid väga lihtne
constructs-- liikumise või avaldused

441
00:22:11,550 --> 00:22:15,519
nagu me oleme arutanud, silmad ja
tingimused ja see ongi kõik.

442
00:22:15,519 --> 00:22:17,060
Seal on mõned muud Kasvataja funktsioone.

443
00:22:17,060 --> 00:22:19,130
Mõned neist on puhtalt
esteetiline või akustiliste,

444
00:22:19,130 --> 00:22:20,964
nagu kõlab Ma lihtsalt mängitakse.

445
00:22:20,964 --> 00:22:23,380
Aga enamasti, siis
on selles keeles, Scratch,

446
00:22:23,380 --> 00:22:25,350
kõik põhiõiguste
ehitusplokke, et sa

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

448
00:22:29,280 --> 00:22:32,960
ja mis tahes mitmeid teisi keeli.

449
00:22:32,960 --> 00:22:36,720
Küsimusi Scratch?

450
00:22:36,720 --> 00:22:37,220
Hästi.

451
00:22:37,220 --> 00:22:40,303
Seepärast ei hakka me sukelduda sügavamale Scratch,
kuigi sa oled teretulnud sel nädalavahetusel,

452
00:22:40,303 --> 00:22:42,860
eriti kui sul on lapsed või
õelapsed ja õe ja sellised,

453
00:22:42,860 --> 00:22:44,220
tutvustada neile Scratch.

454
00:22:44,220 --> 00:22:47,960
See on tegelikult imeliselt mänguline
keskkonda, kui selle autorid ütlevad,

455
00:22:47,960 --> 00:22:49,120
väga kõrged laed.

456
00:22:49,120 --> 00:22:51,670
Kuigi alustasime
väga madala üksikasjad,

457
00:22:51,670 --> 00:22:54,890
saab tõesti teha üsna natuke
koos, ja see on ehk

458
00:22:54,890 --> 00:22:57,360
tutvustamise just nii.

459
00:22:57,360 --> 00:23:02,920
>> Kuid olgem nüüd üleminek veidi rohkem
keerulisi probleeme, kui soovite,

460
00:23:02,920 --> 00:23:05,870
tuntud kui "otsimise" ja
"Sorteerimine" üldisemalt.

461
00:23:05,870 --> 00:23:09,500
Meil oli see telefoniraamat earlier-- siin
teine ​​lihtsalt discussion--

462
00:23:09,500 --> 00:23:13,460
et suutsime otsida
tõhusamalt sest

463
00:23:13,460 --> 00:23:15,270
olulise eelduse.

464
00:23:15,270 --> 00:23:17,655
Ja just olema selge, mida
Eeldus, ma muutes

465
00:23:17,655 --> 00:23:19,280
otsides läbi selle telefoni raamat?

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

467
00:23:23,342 --> 00:23:25,300
See Mike Smith oli
telefoniraamat, kuigi ma

468
00:23:25,300 --> 00:23:27,410
oleks suuteline käitlema
stsenaarium ilma temata

469
00:23:27,410 --> 00:23:30,720
seal, kui ma just lõpetanud enneaegselt.

470
00:23:30,720 --> 00:23:31,806
Raamatus on tähestiku.

471
00:23:31,806 --> 00:23:33,930
Ja see on väga helde
eeldusel, sest see

472
00:23:33,930 --> 00:23:36,580
tähendab someone-- ma olen selline
lõikamine nurgas,

473
00:23:36,580 --> 00:23:40,580
nagu ma olen kiirem, sest keegi
teine ​​tegi palju tööd minu jaoks.

474
00:23:40,580 --> 00:23:43,120
>> Aga mis siis, kui telefon
Raamat oli sortimata?

475
00:23:43,120 --> 00:23:47,050
Võib-olla Verizon sain laisk, lihtsalt viskas
kõik nimed ja numbrid olemas

476
00:23:47,050 --> 00:23:50,120
võibolla järjekorras, milles nad
registreerusin telefoni teenust.

477
00:23:50,120 --> 00:23:54,570
Ja kui palju aega see võtab mind
et leida keegi, nagu Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 lk telefoni book-- mitu
lehekülge pean vaatama läbi?

479
00:23:58,160 --> 00:23:58,905
>> Kõik nemad.

480
00:23:58,905 --> 00:24:00,030
Sa oled justkui läbi õnne.

481
00:24:00,030 --> 00:24:03,420
Sa sõna otseses mõttes pea otsima igal
lehele, kui telefoniraamatus on lihtsalt

482
00:24:03,420 --> 00:24:04,450
juhuslikult järjestatud.

483
00:24:04,450 --> 00:24:06,910
Te võite saada õnnelik ja leida Mike
juba esimesel lehel, sest ta

484
00:24:06,910 --> 00:24:08,826
oli esimene klient
tellida telefoni teenust.

485
00:24:08,826 --> 00:24:10,760
Aga ta oleks võinud viimase ka.

486
00:24:10,760 --> 00:24:12,500
>> Nii juhuslikus järjekorras ei ole hea.

487
00:24:12,500 --> 00:24:16,750
Nii Oletame, et meil sorteerida
telefoniraamat või üldiselt omamoodi andmeid

488
00:24:16,750 --> 00:24:18,520
et me oleme saanud.

489
00:24:18,520 --> 00:24:19,440
Kuidas me saame seda teha?

490
00:24:19,440 --> 00:24:21,360
>> Noh, lubage mul proovida
Lihtne näide siin.

491
00:24:21,360 --> 00:24:24,290
Lubage mul minna ja Toss
mõned numbrid laual.

492
00:24:24,290 --> 00:24:35,480
Oletame, et numbrid on meil on,
oletame, neli, kaks, üks, kolm.

493
00:24:35,480 --> 00:24:38,390
Ja Ben, sorteeri need numbrid meile.

494
00:24:38,390 --> 00:24:39,017
>> Hästi.

495
00:24:39,017 --> 00:24:39,850
Kuidas sa seda tegid?

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

497
00:24:42,731 --> 00:24:43,230
Hästi.

498
00:24:43,230 --> 00:24:44,710
Seega tuleb alustada väikseima
hinna ja kõrgeim,

499
00:24:44,710 --> 00:24:46,084
ja see on tõesti hea intuitsioon.

500
00:24:46,084 --> 00:24:48,080
Ja mõista, et me
Inimestel on tegelikult päris

501
00:24:48,080 --> 00:24:49,913
hea probleemide lahendamise
niimoodi, vähemalt

502
00:24:49,913 --> 00:24:51,810
kui andmed on suhteliselt väike.

503
00:24:51,810 --> 00:24:54,860
Niipea kui hakkad sadu
Numbrite tuhandeid numbrid,

504
00:24:54,860 --> 00:24:58,440
miljoneid numbrid, Ben ilmselt
ei saanud seda teha päris nii kiiresti,

505
00:24:58,440 --> 00:25:00,620
eeldades, et seal olid
lüngad numbrid.

506
00:25:00,620 --> 00:25:03,450
Päris lihtne loota miljon
Vastasel juhul lihtsalt aega.

507
00:25:03,450 --> 00:25:07,150
>> Nii algoritm see kõlab
nagu Ben kasutada just

508
00:25:07,150 --> 00:25:08,930
oli Otsi kõige vähem.

509
00:25:08,930 --> 00:25:12,900
Nii et kuigi meie, inimesed saavad
aastal palju informatsiooni visuaalselt,

510
00:25:12,900 --> 00:25:14,830
arvuti on tegelikult
veidi rohkem piiratud.

511
00:25:14,830 --> 00:25:17,560
Arvuti saab ainult
vaadata ühe baidi korraga

512
00:25:17,560 --> 00:25:20,770
või äkki nelja baiti juures AEG_
tänapäeval võibolla 8 baiti juures AEG_

513
00:25:20,770 --> 00:25:24,450
aga väga väike arv
baitide ajahetkel.

514
00:25:24,450 --> 00:25:28,480
>> Nii, arvestades, et meil on tõesti
neli erinevat väärtuste siin--

515
00:25:28,480 --> 00:25:32,440
ja sa ei mõtle Ben, millel
silmaklapid, kui ta oli arvuti nagu

516
00:25:32,440 --> 00:25:36,450
et ta ei näe midagi muud
kui üks number juures AEG_

517
00:25:36,450 --> 00:25:39,720
nii et me üldjuhul eeldada, nagu
Inglise, me lugeda paremalt vasakule.

518
00:25:39,720 --> 00:25:42,870
Nii et esimene number Ben ilmselt tundus
kell oli neli ja seejärel väga kiiresti

519
00:25:42,870 --> 00:25:44,770
aru, et on päris suur
number-- lase mul hoida otsin.

520
00:25:44,770 --> 00:25:45,357
>> Seal on kaks.

521
00:25:45,357 --> 00:25:45,940
Oota hetk.

522
00:25:45,940 --> 00:25:47,070
Kaks on väiksem kui neli.

523
00:25:47,070 --> 00:25:47,986
Ma mäletan.

524
00:25:47,986 --> 00:25:49,070
Kaks on nüüd kõige väiksem.

525
00:25:49,070 --> 00:25:50,417
Nüüd one-- see on isegi parem.

526
00:25:50,417 --> 00:25:51,250
See on veelgi väiksem.

527
00:25:51,250 --> 00:25:54,000
Ma lähen unustada kahte
ja just mäleta nüüd.

528
00:25:54,000 --> 00:25:56,550
>> Ja kas ta peatus otsin?

529
00:25:56,550 --> 00:25:58,360
Noh, ta võiks aluseks
Selle teabe

530
00:25:58,360 --> 00:26:00,477
kuid ta sõimanud otsing
Ülejäänud nimekirjas.

531
00:26:00,477 --> 00:26:02,060
Sest mis siis, kui null olid nimekirjas?

532
00:26:02,060 --> 00:26:03,643
Mida teha, kui negatiivne olid nimekirjas?

533
00:26:03,643 --> 00:26:07,720
Ta teab, et tema vastus
on õige, kui ta on ammendavalt

534
00:26:07,720 --> 00:26:08,729
kontrollida kogu nimekirja.

535
00:26:08,729 --> 00:26:10,020
Nii me vaatame ülejäänud seda.

536
00:26:10,020 --> 00:26:11,394
Three--, mis oli aja raiskamine.

537
00:26:11,394 --> 00:26:13,540
On õnnetu, aga ma olin
ikka õige seda teha.

538
00:26:13,540 --> 00:26:17,857
Ja nii nüüd ta arvatavasti
valitud väikseim arv

539
00:26:17,857 --> 00:26:20,440
ja lihtsalt pane see alguses
nimekirja, kui ma teen siin.

540
00:26:20,440 --> 00:26:23,480
Nüüd, mida sa järgmisena teha, kuigi
sa ei mõtle selle peale peaaegu

541
00:26:23,480 --> 00:26:25,962
selles osas?

542
00:26:25,962 --> 00:26:27,670
Korrake protsessi,
nii mingi loop.

543
00:26:27,670 --> 00:26:28,920
Seal on tuttav idee.

544
00:26:28,920 --> 00:26:30,860
Nii et siin on neli.

545
00:26:30,860 --> 00:26:32,110
See on praegu kõige väiksem.

546
00:26:32,110 --> 00:26:33,220
See kandidaat.

547
00:26:33,220 --> 00:26:33,900
Enam mitte.

548
00:26:33,900 --> 00:26:34,770
Nüüd ma olen näinud kahte.

549
00:26:34,770 --> 00:26:36,630
See on järgmise väikseim element.

550
00:26:36,630 --> 00:26:40,800
Three-- see pole väiksem, nii et
Nüüd Ben võib kiskuda kaks.

551
00:26:40,800 --> 00:26:44,510
>> Ja nüüd korrake protsessi ja
Loomulikult kolm saab tõmmatud kõrval.

552
00:26:44,510 --> 00:26:45,420
Korrake protsessi.

553
00:26:45,420 --> 00:26:46,990
Neli saab välja tõmmata.

554
00:26:46,990 --> 00:26:50,140
Ja nüüd oleme välja numbrid,
nii nimekirjas tuleb sorteerida.

555
00:26:50,140 --> 00:26:51,960
>> Ja tõepoolest, see on ametlik algoritm.

556
00:26:51,960 --> 00:26:56,610
Arvuti teadlane oleks
nimetame seda "Valiksortimine"

557
00:26:56,610 --> 00:27:00,880
idee on sorteerida
nimekirja iteratively-- jälle

558
00:27:00,880 --> 00:27:03,807
ja ikka ja jälle valides
Kõige vähem.

559
00:27:03,807 --> 00:27:06,140
Ja mis tore on
see on lihtsalt nii paganama arusaadavad.

560
00:27:06,140 --> 00:27:07,470
See on nii lihtne.

561
00:27:07,470 --> 00:27:11,100
Ja võid korrata sama
toimingut uuesti ja uuesti.

562
00:27:11,100 --> 00:27:12,150
See on lihtne.

563
00:27:12,150 --> 00:27:17,170
>> Sel juhul oli kiire, kuid
kui kaua see tegelikult aega võtab?

564
00:27:17,170 --> 00:27:19,880
Teeme tundub ja
tunnen veidi tüütu.

565
00:27:19,880 --> 00:27:24,150
Nii üks, kaks, kolm, neli, viis kuus,
seitse, kaheksa, üheksa, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- suvaline number.

567
00:27:26,160 --> 00:27:28,780
Tahtsin rohkem see
aega kui lihtsalt neli.

568
00:27:28,780 --> 00:27:30,780
Nii et kui mul on kogu
hunnik numbreid now-- see

569
00:27:30,780 --> 00:27:32,420
isegi ei loe
mida nad are-- olgem

570
00:27:32,420 --> 00:27:34,380
mõelda, mida see
algoritm tõesti ei meeldi.

571
00:27:34,380 --> 00:27:35,857
>> Oletatakse, et numbrid seal.

572
00:27:35,857 --> 00:27:38,190
Jällegi, ei ole oluline milliseid
nad on, kuid nad juhuslikult.

573
00:27:38,190 --> 00:27:39,679
Ma esitan Ben algoritm.

574
00:27:39,679 --> 00:27:41,220
Mul on vaja valida väiksema arvu.

575
00:27:41,220 --> 00:27:41,761
Mida teha?

576
00:27:41,761 --> 00:27:44,240
Ja ma lähen füüsiliselt
seda seekord tegutseda välja.

577
00:27:44,240 --> 00:27:46,099
Vaadates, otsin,
otsin, otsin, otsin.

578
00:27:46,099 --> 00:27:48,140
Ainult selleks ajaks saan
lõpuks saab nimekirja

579
00:27:48,140 --> 00:27:51,230
Ma saan aru, väikseim
number oli kaks seekord.

580
00:27:51,230 --> 00:27:52,720
Üks ei ole nimekirjas.

581
00:27:52,720 --> 00:27:54,400
Nii et ma panema kaks.

582
00:27:54,400 --> 00:27:55,590
>> Mida teha edasi?

583
00:27:55,590 --> 00:27:58,600
Vaadates, otsin, otsin, otsin.

584
00:27:58,600 --> 00:28:02,250
Nüüd leidsin number seitse, sest
seal on lüngad nendes numbers--

585
00:28:02,250 --> 00:28:03,300
vaid lihtsalt suvaline.

586
00:28:03,300 --> 00:28:03,800
Hästi.

587
00:28:03,800 --> 00:28:06,030
Nüüd võin panema seitse.

588
00:28:06,030 --> 00:28:08,860
Vaadates otsin, otsin.

589
00:28:08,860 --> 00:28:11,030
>> Nüüd ma olen eeldades, ning
Muidugi, et Ben ei

590
00:28:11,030 --> 00:28:14,780
on ekstra RAM, extra
mälu, sest loomulikult

591
00:28:14,780 --> 00:28:16,080
Otsin sama number.

592
00:28:16,080 --> 00:28:18,246
Kindlasti ma oleks võinud meelde
kõik need numbrid,

593
00:28:18,246 --> 00:28:19,930
ja see on täiesti tõsi.

594
00:28:19,930 --> 00:28:22,610
Aga kui Ben mäletab kõiki
Numbrite ta on näinud,

595
00:28:22,610 --> 00:28:24,430
ta ei ole tõesti tehtud
olulistest edusammudest

596
00:28:24,430 --> 00:28:26,170
sest ta on juba
võime otsida

597
00:28:26,170 --> 00:28:27,540
läbi numbrid laual.

598
00:28:27,540 --> 00:28:29,373
Meenutades kõik
numbrid ei aita,

599
00:28:29,373 --> 00:28:32,490
sest ta saab ikka nii arvuti
ainult vaadata, me oleme öelnud, üks number

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

601
00:28:33,080 --> 00:28:35,760
Nii pole mingi cheat
seal, et saate kasutada.

602
00:28:35,760 --> 00:28:39,170
>> Nii tegelikult, nagu ma
hoida otsivad nimekirja,

603
00:28:39,170 --> 00:28:44,200
Ma sõna otseses mõttes pea muudkui läheb
edasi-tagasi läbi, kitkumise välja

604
00:28:44,200 --> 00:28:45,710
Järgmise väikseim arv.

605
00:28:45,710 --> 00:28:48,810
Ja kui saad mingi järeldavad
minu rumal liigutused,

606
00:28:48,810 --> 00:28:50,860
see lihtsalt muutub väga
tüütu väga kiiresti,

607
00:28:50,860 --> 00:28:54,850
ja ma tundub, et läheb tagasi ja
edasi, edasi ja tagasi üsna vähe.

608
00:28:54,850 --> 00:29:03,220
Nüüd oleks õiglane, ma ei pea minema
päris nii hästi, olgem see-- oleks õiglane,

609
00:29:03,220 --> 00:29:06,310
Ma ei pea käima üsna
kui palju samme iga kord.

610
00:29:06,310 --> 00:29:09,200
Sest, muidugi, nagu ma
vali number loendist,

611
00:29:09,200 --> 00:29:11,860
Ülejäänud nimekirjas on üha lühemaks.

612
00:29:11,860 --> 00:29:14,240
>> Ja nii mõtleme
kui palju samme ma olen tegelikult

613
00:29:14,240 --> 00:29:16,010
traipsing läbi iga kord.

614
00:29:16,010 --> 00:29:18,950
Kõige esimene olukord
meil oli 16 numbrit,

615
00:29:18,950 --> 00:29:22,210
ja nii maximally-- olgem lihtsalt
Selleks jaoks discussion--

616
00:29:22,210 --> 00:29:25,640
Pidin otsima läbi 16
numbrid leida kõige väiksema.

617
00:29:25,640 --> 00:29:28,420
Aga kui ma välja kiskunud
väikseim arv, kuidas

618
00:29:28,420 --> 00:29:30,590
pikk oli ülejäänud nimekirja, muidugi?

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

620
00:29:31,420 --> 00:29:34,670
Nii mitu numbrit ei Ben või mul
vaadata läbi teist korda ümber?

621
00:29:34,670 --> 00:29:36,832
15, lihtsalt minna ja leida kõige väiksemad.

622
00:29:36,832 --> 00:29:39,540
Aga nüüd, muidugi, nimekiri on,
Ka väiksem kui see oli enne.

623
00:29:39,540 --> 00:29:42,540
Nii mitu sammu tegin ma
võtma järgmine kord?

624
00:29:42,540 --> 00:29:49,970
14 ja siis 13 ja siis 12 pluss dot,
dot, dot, kuni ma jäänud vaid üks.

625
00:29:49,970 --> 00:29:53,146
Nüüd arvuti teadlane oleks
küsida, noh, mida see kõik võrdsed?

626
00:29:53,146 --> 00:29:55,770
See tegelikult võrdub mõne konkreetse
number, et me võiks kindlasti

627
00:29:55,770 --> 00:30:00,490
teha aritmeetiliselt, kuid me tahame rääkida
tõhususe kohta algoritmid

628
00:30:00,490 --> 00:30:04,940
veidi rohkem formulaically,
sõltumatu, kui kaua nimekiri on.

629
00:30:04,940 --> 00:30:06,240
>> Ja nii sa tead, mida?

630
00:30:06,240 --> 00:30:09,860
See on 16, aga nagu ma ütlesin enne,
Kutsume suuruse probleem

631
00:30:09,860 --> 00:30:10,970
n, kus n on mõned number.

632
00:30:10,970 --> 00:30:13,220
Võibolla on see 16, võib-olla see on
kolm, võib-olla see miljon.

633
00:30:13,220 --> 00:30:13,761
Ma ei tea.

634
00:30:13,761 --> 00:30:14,390
Mind ei huvita.

635
00:30:14,390 --> 00:30:16,520
Mida ma tegelikult tahan on
valem, mis suudan

636
00:30:16,520 --> 00:30:19,420
kasuta võrrelda seda algoritmi
võrreldes teiste algoritmide

637
00:30:19,420 --> 00:30:22,350
et keegi võiks väita,
on parem või halvem.

638
00:30:22,350 --> 00:30:25,430
>> Nii selgub, ja ma ainult
Seda teame algkool,

639
00:30:25,430 --> 00:30:34,790
et see tegelikult toimib läbi sama
asi nagu n üle n pluss üks üle kahe.

640
00:30:34,790 --> 00:30:40,020
Ja see juhtub võrdsed, ning
Muidugi, n ruudus pluss n üle kahe.

641
00:30:40,020 --> 00:30:43,250
Nii et kui ma tahtsin valem
Kui suure sammu

642
00:30:43,250 --> 00:30:46,330
osalesid vaadates kõik
need numbrid ikka ja jälle

643
00:30:46,330 --> 00:30:52,681
ja ikka ja jälle, ma ütleks
see on n ruudus pluss n üle kahe.

644
00:30:52,681 --> 00:30:53,430
Aga tead mis?

645
00:30:53,430 --> 00:30:54,500
See lihtsalt tundub segane.

646
00:30:54,500 --> 00:30:56,470
Ma tõesti tahan
üldises mõttes asju.

647
00:30:56,470 --> 00:30:58,810
Ja võite tagasikutsumise
keskkooli, et

648
00:30:58,810 --> 00:31:00,660
on mõiste kõrgeima järjekorras perspektiivis.

649
00:31:00,660 --> 00:31:05,300
Millised need tingimused, n
ruudus, n, või pool,

650
00:31:05,300 --> 00:31:07,550
on kõige suurem mõju aja jooksul?

651
00:31:07,550 --> 00:31:11,920
Mida suurem n saab, mis
nendes küsimustes kõige rohkem?

652
00:31:11,920 --> 00:31:15,560
>> Teisisõnu, kui ma plug
miljon, n ruudus

653
00:31:15,560 --> 00:31:17,900
saab olema kõige tõenäolisem
Valdavaks tegur,

654
00:31:17,900 --> 00:31:21,670
sest miljon korda
ise on palju suurem

655
00:31:21,670 --> 00:31:23,682
kui pluss üks miljon.

656
00:31:23,682 --> 00:31:24,390
Nii et sa tead, mida?

657
00:31:24,390 --> 00:31:27,305
See on nii paganama suur
number kui te ruudu number.

658
00:31:27,305 --> 00:31:28,430
See ei ole tegelikult küsimus.

659
00:31:28,430 --> 00:31:30,596
Me elame rist, et
välja ja unusta see.

660
00:31:30,596 --> 00:31:34,250
Ja nii arvuti teadlane ütleks
et tõhususe seda algoritmi

661
00:31:34,250 --> 00:31:37,850
on järjekorras n ruudus
Ma mõtlen tõesti ligikaudne.

662
00:31:37,850 --> 00:31:40,810
See on omamoodi umbes n ruudus.

663
00:31:40,810 --> 00:31:44,130
Aja jooksul suurem
ja suurem n saab, seda

664
00:31:44,130 --> 00:31:47,610
on hea prognoosida, mida
tõhususe või ebatõhus

665
00:31:47,610 --> 00:31:49,400
Selle algoritmi tegelikult on.

666
00:31:49,400 --> 00:31:52,040
Ja ma tuletada, et loomulikult,
alates tegelikult seda matemaatikat.

667
00:31:52,040 --> 00:31:54,040
Aga nüüd ma lihtsalt viipab
käed, sest ma lihtsalt

668
00:31:54,040 --> 00:31:55,790
taha üldises mõttes seda algoritmi.

669
00:31:55,790 --> 00:31:58,850
>> Nii kasutades sama loogikat, vahepeal
Vaatleme teise algoritmi

670
00:31:58,850 --> 00:32:01,162
me juba tundus at-- lineaarne otsing.

671
00:32:01,162 --> 00:32:02,870
Kui ma otsisin
telefoni book--

672
00:32:02,870 --> 00:32:05,980
ei sorteerimine, otsides
läbi telefoni book--

673
00:32:05,980 --> 00:32:09,197
me muudkui rääkisid, et see oli
1000 samme, või 500 sammu.

674
00:32:09,197 --> 00:32:10,280
Kuid olgem üldistada, et.

675
00:32:10,280 --> 00:32:12,860
Kui seal on n lehekülge
telefoniraamatus, mis on

676
00:32:12,860 --> 00:32:17,250
Tööaja või
tõhusust lineaarne otsing?

677
00:32:17,250 --> 00:32:19,750
See on järjekorras
kui palju samme, et leida

678
00:32:19,750 --> 00:32:24,210
Mike Smith, kasutades lineaarset otsida,
Esimene algoritmi või isegi teine?

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

680
00:32:27,240 --> 00:32:31,710
>> Halvimal juhul, Mike
on lõpus raamat.

681
00:32:31,710 --> 00:32:35,590
Nii et kui telefoniraamatus on 1000 lehekülge,
ütlesime viimane kord, halvimal juhul,

682
00:32:35,590 --> 00:32:38,380
see võib võtta umbes kuidas
mitu lehekülge leida Mike?

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

684
00:32:38,990 --> 00:32:39,830
See on ülemine piir.

685
00:32:39,830 --> 00:32:41,790
See on halvim võimalik olukord.

686
00:32:41,790 --> 00:32:44,410
Aga jälle, me liigume eemale
alates numbrid nagu 1000 praegu.

687
00:32:44,410 --> 00:32:45,730
See on lihtsalt n.

688
00:32:45,730 --> 00:32:47,470
>> Mis siis loogiline järeldus?

689
00:32:47,470 --> 00:32:50,210
Leida Mike telefon
raamat, mis on n lehekülge

690
00:32:50,210 --> 00:32:55,280
võib võtta, et väga halvimal juhul
kui palju samme selleks, n?

691
00:32:55,280 --> 00:32:58,110
Ja tõepoolest arvuti
teadlane ütleks

692
00:32:58,110 --> 00:33:02,340
et sõiduaega või
täitmise või efektiivsuse

693
00:33:02,340 --> 00:33:07,470
või ebaefektiivsus, algoritmi nagu
lineaarne otsing on järjekorras n.

694
00:33:07,470 --> 00:33:10,010
Ja me saame rakendada sama
loogika ületamisel midagi välja

695
00:33:10,010 --> 00:33:13,170
nagu ma just tegin teise
algoritm oli meil telefoniraamatust

696
00:33:13,170 --> 00:33:16,040
kus me käisime kaks lehekülge korraga.

697
00:33:16,040 --> 00:33:20,120
>> Nii 1000 lehekülge telefoniraamat võiks
meid 500 lk pöördeid, pluss üks

698
00:33:20,120 --> 00:33:21,910
kui me topelt tagasi natuke.

699
00:33:21,910 --> 00:33:26,590
Nii et kui telefoniraamatus on n lehekülge, kuid
me teeme kaks lehekülge korraga,

700
00:33:26,590 --> 00:33:28,900
see on umbes siis?

701
00:33:28,900 --> 00:33:33,190
N üle kahe, nii et on nagu n üle kahe.

702
00:33:33,190 --> 00:33:38,490
Aga ma tegin Nõude
hetk tagasi, et n üle two--

703
00:33:38,490 --> 00:33:41,060
see on omamoodi sama lihtsalt n.

704
00:33:41,060 --> 00:33:44,050
See on lihtsalt konstandiks,
arvuti teadlased öelda.

705
00:33:44,050 --> 00:33:45,970
Olgem keskenduda vaid
muutujad, really--

706
00:33:45,970 --> 00:33:47,780
suurim muutujate võrrand.

707
00:33:47,780 --> 00:33:52,530
>> Nii lineaarne otsing, kas teha üks
lehte korraga või kaks lehekülge korraga,

708
00:33:52,530 --> 00:33:54,810
on omamoodi põhimõtteliselt sama.

709
00:33:54,810 --> 00:33:56,880
See on ikka tellimusel n.

710
00:33:56,880 --> 00:34:01,930
Aga ma väita minu pilt varem
et kolmas algoritm ei olnud

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

712
00:34:02,480 --> 00:34:03,605
See ei olnud sirge.

713
00:34:03,605 --> 00:34:08,659
See oli see, et tõusva joone ja
algebralist valemit oli siis?

714
00:34:08,659 --> 00:34:11,812
Logi n-- nii sisse baasi kaks n.

715
00:34:11,812 --> 00:34:14,520
Ja me ei pea minema liiga
palju detaile logaritmide täna

716
00:34:14,520 --> 00:34:17,394
kuid enamik arvuti teadlased ei teeks
isegi öelda, mida alus on.

717
00:34:17,394 --> 00:34:20,639
Sest see kõik on lihtsalt
pidev tegurid, nii et rääkida,

718
00:34:20,639 --> 00:34:22,659
lihtsalt väike numbriline erinevusi.

719
00:34:22,659 --> 00:34:31,179
Ja nii see oleks väga sage
teed eriti formaalse arvutis

720
00:34:31,179 --> 00:34:33,949
teadlased juhatuse või
programmeerijad Wideboard

721
00:34:33,949 --> 00:34:36,889
tegelikult väites, mis
algoritm nad kasutavad

722
00:34:36,889 --> 00:34:39,500
või mida tõhusust
oma algoritmi.

723
00:34:39,500 --> 00:34:42,960
>> Ja see ei pruugi midagi
sa arutada mingil väga täpselt,

724
00:34:42,960 --> 00:34:47,889
aga hea programmeerija on keegi
kes on tugev, ametliku taustal.

725
00:34:47,889 --> 00:34:50,120
Ta on võimeline rääkima
sa sellist teed

726
00:34:50,120 --> 00:34:53,350
ja tegelikult teha
kvalitatiivne argumente

727
00:34:53,350 --> 00:34:56,870
miks üks algoritmi või
üks tükk tarkvara

728
00:34:56,870 --> 00:35:00,165
on parem kuidagi teise.

729
00:35:00,165 --> 00:35:02,540
Sest sa võiks kindlasti
lihtsalt joosta ühe inimese programmi

730
00:35:02,540 --> 00:35:04,980
ja loendada sekundit
kulub sorteerida mõned numbrid,

731
00:35:04,980 --> 00:35:06,710
ja saate käivitada mõned
teise inimese programmi

732
00:35:06,710 --> 00:35:08,418
ja loendada
sekundit kulub.

733
00:35:08,418 --> 00:35:12,840
Aga see on üldisem nii, et
mida saab kasutada, et analüüsida algoritme,

734
00:35:12,840 --> 00:35:15,520
kui soovite, lihtsalt
paberist või lihtsalt verbaalselt.

735
00:35:15,520 --> 00:35:18,430
Ilma isegi töötab see ilma
isegi üritab proovi sisendid,

736
00:35:18,430 --> 00:35:20,180
saab põhjuseta läbi.

737
00:35:20,180 --> 00:35:24,670
Ja nii rentides arendaja või kui
võttes teda justkui väita, et sa

738
00:35:24,670 --> 00:35:28,460
miks nende algoritm, oma saladus
kaste otsima miljardeid

739
00:35:28,460 --> 00:35:30,580
veebilehti oma
Ettevõte on parem, neid

740
00:35:30,580 --> 00:35:33,302
on erinevaid väiteid, mida nad
peaks ideaalis olema võimeline tegema.

741
00:35:33,302 --> 00:35:35,010
Või vähemalt need
asju, mida

742
00:35:35,010 --> 00:35:40,211
et oleks tulla aruteluga juures
vähemalt väga formaalne diskussioon.

743
00:35:40,211 --> 00:35:40,710
Hästi.

744
00:35:40,710 --> 00:35:44,400
Nii Ben pakutud midagi
nimetatakse Valiksortimine.

745
00:35:44,400 --> 00:35:48,200
Aga ma lähen ettepaneku, et seal on
teiste viise, liiga.

746
00:35:48,200 --> 00:35:50,400
Mida ma tegelikult ei meeldi
umbes Ben algoritm

747
00:35:50,400 --> 00:35:54,400
on see, et ta pidas jalgsi või
olles mul kõndida, edasi-tagasi

748
00:35:54,400 --> 00:35:56,930
ja edasi-tagasi ja edasi ja tagasi.

749
00:35:56,930 --> 00:36:04,130
Mis siis, kui selle asemel ma tegema
midagi need numbrid siin

750
00:36:04,130 --> 00:36:08,200
ja ma lihtsalt suhtleb iga
number omakorda nagu ma olen andnud talle?

751
00:36:08,200 --> 00:36:10,780
>> Teisisõnu, siin
minu nimekirja numbrid.

752
00:36:10,780 --> 00:36:12,944
Neli, üks, kolm, kaks.

753
00:36:12,944 --> 00:36:14,360
Ja ma lähen tegema järgmist.

754
00:36:14,360 --> 00:36:17,230
Ma lähen sisestada numbrid
kuhu nad kuuluvad pigem

755
00:36:17,230 --> 00:36:18,980
kui neid valides ühe korraga.

756
00:36:18,980 --> 00:36:20,820
Teisisõnu, siin on number neli.

757
00:36:20,820 --> 00:36:22,430
>> Siin on minu esialgses nimekirjas.

758
00:36:22,430 --> 00:36:25,290
Ja ma lähen hoida
sisuliselt uue nimekirja siin.

759
00:36:25,290 --> 00:36:26,710
Nii et see on vana nimekirjast.

760
00:36:26,710 --> 00:36:28,560
See on uue nimekirja.

761
00:36:28,560 --> 00:36:30,220
Näen number neli esimest.

762
00:36:30,220 --> 00:36:34,500
Minu uus nimekiri on esialgu tühjad,
nii et see on triviaalselt puhul

763
00:36:34,500 --> 00:36:36,410
et neli on nüüd assortii nimekirja.

764
00:36:36,410 --> 00:36:39,560
Ma lihtsalt tunnen arvu ma antud,
ja ma panen ta oma uues nimekirjas.

765
00:36:39,560 --> 00:36:41,460
>> Kas see uus nimekiri järjestatud?

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

767
00:36:41,990 --> 00:36:45,090
Tobe, sest seal on ainult üks
element, kuid see on absoluutselt järjestatud.

768
00:36:45,090 --> 00:36:46,390
Ei ole midagi kohatu.

769
00:36:46,390 --> 00:36:49,290
See on huvitav, see algoritm,
kui ma liikuda järgmisse etappi.

770
00:36:49,290 --> 00:36:50,550
>> Nüüd on mul üks.

771
00:36:50,550 --> 00:36:55,430
Nii üks muidugi kuulub hetkel
alguses või lõpus uue nimekirja?

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

773
00:36:56,360 --> 00:36:58,530
Nii et ma pean tegema mõned tööd nüüd.

774
00:36:58,530 --> 00:37:01,410
Olen võtnud mõned
vabadusi minu marker

775
00:37:01,410 --> 00:37:03,120
lihtsalt joonistus asju
kus ma tahan neid,

776
00:37:03,120 --> 00:37:05,320
kuid see ei ole tõesti
täpne arvutis.

777
00:37:05,320 --> 00:37:08,530
Arvuti, nagu me teame, on
RAM või Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
ja see on üks bait ja
teine ​​bait ja teise baidi.

779
00:37:12,411 --> 00:37:14,910
Ja kui sul on GB
RAM, teil on miljard baiti,

780
00:37:14,910 --> 00:37:16,680
kuid nad füüsiliselt ühes kohas.

781
00:37:16,680 --> 00:37:19,540
Sa ei saa lihtsalt liikuda kraami ümber
juhtides seda laual

782
00:37:19,540 --> 00:37:20,750
kus iganes soovite.

783
00:37:20,750 --> 00:37:24,090
Nii et kui minu uue nimekirja
neljas kohas mälus

784
00:37:24,090 --> 00:37:27,480
Kahjuks neli on
juba vales kohas.

785
00:37:27,480 --> 00:37:30,410
>> Nii et sisestada number üks
Ma ei saa lihtsalt teha siit.

786
00:37:30,410 --> 00:37:31,901
See mälu asukohta ei eksisteeri.

787
00:37:31,901 --> 00:37:35,150
See oleks petmine, ja ma olen olnud
petmine piltlikult mõne minuti

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

789
00:37:35,800 --> 00:37:40,950
Nii et tõesti, kui ma tahan panna ühte siin,
Mul on ajutiselt kopeerida neli

790
00:37:40,950 --> 00:37:43,030
ja siis pane kedagi.

791
00:37:43,030 --> 00:37:45,500
>> See on hea, see on õige,
see on tehniliselt võimalik,

792
00:37:45,500 --> 00:37:48,410
aga aru, et see lisatööd.

793
00:37:48,410 --> 00:37:50,460
Ma ei ole lihtsalt pane number kohas.

794
00:37:50,460 --> 00:37:53,026
Ma esimest pidi liikuma
number, siis pane see koht,

795
00:37:53,026 --> 00:37:54,650
nii et ma mingi kahekordistunud minu töö hulka.

796
00:37:54,650 --> 00:37:55,660
Nii et hoidke seda silmas pidades.

797
00:37:55,660 --> 00:37:57,120
>> Aga ma olen nüüd teinud selle elemendi.

798
00:37:57,120 --> 00:37:59,056
Nüüd ma tahan haarata number kolm.

799
00:37:59,056 --> 00:38:00,430
Kui muidugi see kuulub?

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

801
00:38:01,480 --> 00:38:03,650
Ma ei saa petta enam
ja lihtsalt panna sinna,

802
00:38:03,650 --> 00:38:06,770
sest jällegi seda mälu
on füüsilist asukohta.

803
00:38:06,770 --> 00:38:10,900
Nii et ma pean kopeerima neli
ja pane kolme siin.

804
00:38:10,900 --> 00:38:11,550
Ei ole suur asi.

805
00:38:11,550 --> 00:38:14,610
See on lihtsalt üks lisatööd
again-- tundub väga odav.

806
00:38:14,610 --> 00:38:16,445
>> Aga nüüd ma liikuda kaks.

807
00:38:16,445 --> 00:38:17,820
Kaks muidugi kuulub siia.

808
00:38:17,820 --> 00:38:20,990
Nüüd hakkate näha, kuidas
töö saab kuhjuma.

809
00:38:20,990 --> 00:38:23,520
Mida ma nüüd tegema pean?

810
00:38:23,520 --> 00:38:28,570
Jah, mul on liikuda neli,
Siis on kopeerida kolm,

811
00:38:28,570 --> 00:38:31,200
ja nüüd ma ei sisesta kaks.

812
00:38:31,200 --> 00:38:34,460
Ja saagi seda
algoritm, huvitaval kombel

813
00:38:34,460 --> 00:38:41,050
on, et oletame, et meil on rohkem äärmuslikke
Juhul, kui see on oletame kaheksa, seitse,

814
00:38:41,050 --> 00:38:45,150
kuue, viie, nelja, kolm, kaks, üks.

815
00:38:45,150 --> 00:38:49,450
See on paljudel kontekstides
Halvimal juhul,

816
00:38:49,450 --> 00:38:51,570
sest paganama asi
on sõna otseses mõttes tagurpidi.

817
00:38:51,570 --> 00:38:53,670
>> See ei ole tegelikult
mõjutada Ben algoritm,

818
00:38:53,670 --> 00:38:55,940
sest Ben valikut
Sorteeri ta läheb, et hoida

819
00:38:55,940 --> 00:38:58,359
läheb edasi ja tagasi läbi nimekirja.

820
00:38:58,359 --> 00:39:01,150
Ja kuna ta oli alati otsinud
läbi kogu ülejäänud nimekirja,

821
00:39:01,150 --> 00:39:02,858
see ei ole oluline
kus elemendid on.

822
00:39:02,858 --> 00:39:05,630
Aga sel juhul minu sisestamine
approach-- proovime seda.

823
00:39:05,630 --> 00:39:08,616
>> Nii üks, kaks, kolm, neli,
viis, kuus, seitse, kaheksa.

824
00:39:08,616 --> 00:39:11,630
Üks kaks kolm neli,
viis, kuus, seitse, kaheksa.

825
00:39:11,630 --> 00:39:14,320
Ma lähen võtma kaheksa,
ja kus ma pane see?

826
00:39:14,320 --> 00:39:17,260
Noh, alguses minu nimekirja,
kuna selle uue nimekirja sorteeritakse.

827
00:39:17,260 --> 00:39:18,760
Ja ma ületada seda.

828
00:39:18,760 --> 00:39:20,551
>> Kust ma panin seitse?

829
00:39:20,551 --> 00:39:21,050
Paganama ta.

830
00:39:21,050 --> 00:39:23,174
See vajab sinna minna, nii et
Mul on teha mõned kopeerimist.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Ja nüüd seitse läheb siia.

833
00:39:28,480 --> 00:39:29,860
Nüüd ma liikuda kuus.

834
00:39:29,860 --> 00:39:30,980
Nüüd on isegi rohkem tööd.

835
00:39:30,980 --> 00:39:32,570
>> Kaheksa on minna siin.

836
00:39:32,570 --> 00:39:33,920
Seitse on minna siin.

837
00:39:33,920 --> 00:39:35,450
Nüüd kuue võib minna siin.

838
00:39:35,450 --> 00:39:37,950
Nüüd ma haarata viis.

839
00:39:37,950 --> 00:39:40,560
Nüüd kaheksast peab minema
siin seitse on minna siin,

840
00:39:40,560 --> 00:39:43,650
kuus on minna siin, ja
nüüd viie ja korrata.

841
00:39:43,650 --> 00:39:46,610
Ja ma olen päris palju
liigutades seda pidevalt.

842
00:39:46,610 --> 00:39:52,950
>> Nii lõpus, see algorithm-- jagame
nimetame seda sisestamise sort-- tegelikult

843
00:39:52,950 --> 00:39:55,020
on palju tööd ka.

844
00:39:55,020 --> 00:39:56,970
See on lihtsalt erinevad
sellist tööd, kui Ben.

845
00:39:56,970 --> 00:40:00,090
Ben töö oli mulle läheb
edasi-tagasi kogu aeg,

846
00:40:00,090 --> 00:40:03,510
valides järgmise väikseim
element ja jälle.

847
00:40:03,510 --> 00:40:06,660
Nii et see oli see väga visuaalne töö.

848
00:40:06,660 --> 00:40:10,600
>> See teine ​​algoritm, mis on endiselt
correct-- ta saab selle töökoha done--

849
00:40:10,600 --> 00:40:12,800
lihtsalt muudab töö mahtu.

850
00:40:12,800 --> 00:40:15,420
Tundub, et esialgu sa oled
kokkuhoid, sest sa oled lihtsalt

851
00:40:15,420 --> 00:40:19,190
tegelevad iga element
kuni ees ilma kõndides kõik

852
00:40:19,190 --> 00:40:20,930
Muide nimekiri läbi nagu Ben oli.

853
00:40:20,930 --> 00:40:25,300
Probleem on aga selles, eriti nendes
hull juhul, kui see on kõik tagurpidi

854
00:40:25,300 --> 00:40:27,830
sa oled lihtsalt selline
edasilükkamine tööd

855
00:40:27,830 --> 00:40:30,360
kuni teil määrata oma vigu.

856
00:40:30,360 --> 00:40:33,919
>> Ja kui te võite ette kujutada seda
kaheksa ja seitse ja kuus ja viis

857
00:40:33,919 --> 00:40:36,710
ja hiljem neli ja kolm ja kaks
liigub oma teed läbi nimekirja,

858
00:40:36,710 --> 00:40:39,060
oleme lihtsalt muutnud
töö liik me teeme.

859
00:40:39,060 --> 00:40:42,340
Selle asemel, et seda teevad juures
alguses minu korduse

860
00:40:42,340 --> 00:40:45,250
Ma lihtsalt teen seda kell
lõpus iga iteratsiooni.

861
00:40:45,250 --> 00:40:50,550
Nii selgub, et see algoritm,
Ka üldiselt nimetatakse sisestamise sorteerida,

862
00:40:50,550 --> 00:40:52,190
Samuti on suurusjärgus n ruudus.

863
00:40:52,190 --> 00:40:56,480
See on tegelikult midagi paremat,
no parem üldse.

864
00:40:56,480 --> 00:41:00,810
>> Kuid seal on kolmas lähenemisviis
Tahaksin julgustada meid kaaluma,

865
00:41:00,810 --> 00:41:02,970
mis on see.

866
00:41:02,970 --> 00:41:07,850
Nii oletame minu nimekirja, lihtsuse
jällegi neli, üks, kolm,

867
00:41:07,850 --> 00:41:11,080
two-- vaid neli numbrit.

868
00:41:11,080 --> 00:41:13,300
Ben oli hea intuitsioon,
hea inimese intuitsioon

869
00:41:13,300 --> 00:41:16,340
enne, mille me fikseeritud kogu
nimekirja eventually-- sisestamise omamoodi.

870
00:41:16,340 --> 00:41:18,020
Ma coaxed meist mööda.

871
00:41:18,020 --> 00:41:22,530
Aga Vaatleme
Lihtsaim viis probleemi nimekirja.

872
00:41:22,530 --> 00:41:24,110
>> See loetelu ei ole järjestatud.

873
00:41:24,110 --> 00:41:26,130
Miks?

874
00:41:26,130 --> 00:41:31,920
Inglise keeles, miks
see ei ole tegelikult järjestatud.

875
00:41:31,920 --> 00:41:33,400
Mis see tähendab mitte sorteerida?

876
00:41:33,400 --> 00:41:34,220
>> Üliõpilane: See ei ole järjestikune.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Humala: Mitte järjestikune.

878
00:41:34,990 --> 00:41:35,822
Anna mulle üks näide.

879
00:41:35,822 --> 00:41:37,180
>> Üliõpilane: Pane järjekorras.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Humala: OK.

881
00:41:37,440 --> 00:41:38,790
Anna mulle rohkem konkreetse näite.

882
00:41:38,790 --> 00:41:39,832
>> Üliõpilane: Kasvav järjekord.

883
00:41:39,832 --> 00:41:41,206
DAVID Humala: Mitte tõusvas järjekorras.

884
00:41:41,206 --> 00:41:42,100
Ole täpsem.

885
00:41:42,100 --> 00:41:45,190
Ma ei tea, mida te mõtlete kasvavalt.

886
00:41:45,190 --> 00:41:47,150
Mis viga?

887
00:41:47,150 --> 00:41:49,930
>> Üliõpilane: Väikseim
numbrid ei ole esimeses ruumis.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Humala Väikseim number on
mitte esimesest ruumi.

889
00:41:51,140 --> 00:41:52,120
Olla täpsem.

890
00:41:52,120 --> 00:41:55,000
Ma olen hakanud saaki.

891
00:41:55,000 --> 00:41:59,470
Me arvestame, kuid
Mis rikkis siin?

892
00:41:59,470 --> 00:42:00,707
>> Üliõpilane: numbriline jada.

893
00:42:00,707 --> 00:42:02,040
DAVID Humala: numbriline jada.

894
00:42:02,040 --> 00:42:04,248
Igaühe selline pidamine
see siin-- väga kõrgel tasemel.

895
00:42:04,248 --> 00:42:07,450
Lihtsalt sõna otseses mõttes mulle öelda, mis on
vale nagu viie-aastane võiks.

896
00:42:07,450 --> 00:42:08,310
>> Üliõpilane: pluss üks.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Humala: Mis see on?

898
00:42:08,750 --> 00:42:09,610
>> Üliõpilane: pluss üks.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Humala: Mida sa mõtled pluss üks?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Anna mulle erinevas viie-aastane.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Mis viga, ema?

904
00:42:18,330 --> 00:42:19,940
Mis viga, isa?

905
00:42:19,940 --> 00:42:22,808
Mida sa mõtled seda ei järjestatud?

906
00:42:22,808 --> 00:42:24,370
>> Üliõpilane: See ei ole õige koht.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Humala: Mis
ei õiges kohas?

908
00:42:25,580 --> 00:42:26,174
>> Üliõpilane: Neli.

909
00:42:26,174 --> 00:42:27,090
DAVID Humala: OK, hea.

910
00:42:27,090 --> 00:42:29,110
Nii neli ei ole, kus see peaks olema.

911
00:42:29,110 --> 00:42:30,590
Eelkõige on see õige?

912
00:42:30,590 --> 00:42:33,000
Neli ja üks esimene
kaks numbrit näen.

913
00:42:33,000 --> 00:42:34,930
See õigus?

914
00:42:34,930 --> 00:42:36,427
Ei, nad on rikkis, eks?

915
00:42:36,427 --> 00:42:38,135
Tegelikult arvan, et nüüd
umbes arvuti ka.

916
00:42:38,135 --> 00:42:40,824
Seda saab vaadata ainult võibolla üks,
võibolla kahte asja once--

917
00:42:40,824 --> 00:42:43,240
ja tegelikult ainult üks asi
korraga, kuid see võib vähemalt

918
00:42:43,240 --> 00:42:45,790
vaata üks asi siis
Järgmine asi õige kõrval.

919
00:42:45,790 --> 00:42:47,380
>> Nii on need, et?

920
00:42:47,380 --> 00:42:48,032
Muidugi mitte.

921
00:42:48,032 --> 00:42:48,740
Nii et sa tead, mida?

922
00:42:48,740 --> 00:42:51,020
Miks me ei võta laps
samme selle probleemi lahendamisega

923
00:42:51,020 --> 00:42:53,410
selle asemel, et teeme need väljamõeldud
algoritme nagu Ben, kus

924
00:42:53,410 --> 00:42:56,440
Ta on omamoodi millega see
silmukoiminen läbi nimekirja

925
00:42:56,440 --> 00:42:59,670
selle asemel, et seda, mida ma tegin, kus
Ma lihtsalt mingi fikseeritud see, kui me minna?

926
00:42:59,670 --> 00:43:03,650
Ütleme nii sõna otseses mõttes murda
mõiste order-- numbrilises järjekorras

927
00:43:03,650 --> 00:43:06,990
nimetame seda mida iganes sa want--
neisse paarikaupa võrdlusi.

928
00:43:06,990 --> 00:43:07,590
>> Neli ja üks.

929
00:43:07,590 --> 00:43:09,970
Kas see on õige, et?

930
00:43:09,970 --> 00:43:11,310
Nii saab määrata, et.

931
00:43:11,310 --> 00:43:14,700
Üks neli, ja seejärel
me lihtsalt kopeerida seda.

932
00:43:14,700 --> 00:43:15,560
Olgu, hea.

933
00:43:15,560 --> 00:43:17,022
I fikseeritud üks kuni neli.

934
00:43:17,022 --> 00:43:18,320
Kolm ja kaks?

935
00:43:18,320 --> 00:43:18,820
Ei.

936
00:43:18,820 --> 00:43:21,690
Lase mu sõnad sobivad minu sõrmed.

937
00:43:21,690 --> 00:43:23,695
Neli ja kolm?

938
00:43:23,695 --> 00:43:27,930
>> See ei ole, et, nii et ma lähen
teha ühte, kolm, neli, kaks.

939
00:43:27,930 --> 00:43:28,680
Hästi.

940
00:43:28,680 --> 00:43:32,310
Nüüd neli ja kaks?

941
00:43:32,310 --> 00:43:33,370
Meil on vaja kindlaks määrata ka see.

942
00:43:33,370 --> 00:43:36,700
Nii üks, kolm, kaks, neli.

943
00:43:36,700 --> 00:43:39,820
Nii on see järjestatud?

944
00:43:39,820 --> 00:43:43,170
Ei, aga see on lähemal järjestatud?

945
00:43:43,170 --> 00:43:48,930
>> On, sest me fikseeritud käesoleva
viga, me fikseeritud see viga,

946
00:43:48,930 --> 00:43:50,370
ja me fikseeritud see viga.

947
00:43:50,370 --> 00:43:52,420
Nii et me fikseeritud kolm vigu väidetavalt.

948
00:43:52,420 --> 00:43:58,100
Ikka ei ole tegelikult otsima sorteeritud, kuid
see on objektiivselt lähemale sorteeritud

949
00:43:58,100 --> 00:44:00,080
sest meil fikseeritud mõned neist vigu.

950
00:44:00,080 --> 00:44:02,047
>> Mida ma nüüd edasi tegema?

951
00:44:02,047 --> 00:44:03,630
I tüüpi jõudnud lõpuks nimekiri.

952
00:44:03,630 --> 00:44:05,680
Ma tundus, et on fikseeritud
kõik vead, aga ei.

953
00:44:05,680 --> 00:44:08,510
Kuna antud juhul mõned numbrid
võis mullidena lähemale

954
00:44:08,510 --> 00:44:10,410
teiste numbreid
veel rikkis.

955
00:44:10,410 --> 00:44:12,951
Nii teeme seda uuesti, ja ma
just seda paika seekord.

956
00:44:12,951 --> 00:44:14,170
Üks ja kolm?

957
00:44:14,170 --> 00:44:14,720
Kõik on korras.

958
00:44:14,720 --> 00:44:16,070
Kolm ja kaks?

959
00:44:16,070 --> 00:44:17,560
Muidugi ei ole, nii et vaatame seda muuta.

960
00:44:17,560 --> 00:44:19,160
Nii kaks, kolm.

961
00:44:19,160 --> 00:44:21,340
Kolm ja neli?

962
00:44:21,340 --> 00:44:24,370
Ja nüüd lähme lihtsalt
eriti pedantne siin.

963
00:44:24,370 --> 00:44:26,350
Kas see on järjestatud?

964
00:44:26,350 --> 00:44:29,280
Sa inimestel tean, et see järjestatud.

965
00:44:29,280 --> 00:44:30,400
>> Uuesti proovida.

966
00:44:30,400 --> 00:44:31,900
Nii Olivia ettepaneku ma proovige uuesti.

967
00:44:31,900 --> 00:44:32,530
Miks?

968
00:44:32,530 --> 00:44:35,810
Kuna arvuti ei ole
luksus meie inimeste silmad

969
00:44:35,810 --> 00:44:38,080
lihtsalt riivav back-- OK, ma olen teinud.

970
00:44:38,080 --> 00:44:41,610
Kuidas arvuti kindlaks
et nimekiri on nüüd järjestatud?

971
00:44:41,610 --> 00:44:44,590
Mehaaniliselt.

972
00:44:44,590 --> 00:44:47,650
>> Ma peaks läbi minema
veelkord ja ainult siis I

973
00:44:47,650 --> 00:44:51,190
ei tee / leida vigu ma saan
siis järeldada, nagu arvuti, eks,

974
00:44:51,190 --> 00:44:51,980
Me oled hea minna.

975
00:44:51,980 --> 00:44:54,850
Nii et üks ja kaks, kaks ja
kolm, kolme ja nelja.

976
00:44:54,850 --> 00:44:58,030
Nüüd ma saan lõplikult öelda, see on
sorteeritud, sest ma ei teinud muutusi.

977
00:44:58,030 --> 00:45:01,940
Nüüd oleks viga ja lihtsalt
rumal kui ma arvuti,

978
00:45:01,940 --> 00:45:05,640
küsis samu küsimusi uuesti
ootab erinevaid vastuseid.

979
00:45:05,640 --> 00:45:07,110
Ei tohiks juhtuda.

980
00:45:07,110 --> 00:45:08,600
>> Ja nii nüüd nimekirja sorteeritakse.

981
00:45:08,600 --> 00:45:12,630
Kahjuks sõiduaega
See algoritm on ka n ruudus.

982
00:45:12,630 --> 00:45:13,130
Miks?

983
00:45:13,130 --> 00:45:19,520
Kuna teil on n numbrid, ja
Halvimal juhul sa pead liikuma n numbrid

984
00:45:19,520 --> 00:45:23,637
n korda, sest sa pead edasi minema
tagasi vaadata ja potentsiaalselt määrata

985
00:45:23,637 --> 00:45:24,220
Neid numbreid.

986
00:45:24,220 --> 00:45:26,280
Ja me saame teha rohkem
ametliku analüüsi ka.

987
00:45:26,280 --> 00:45:29,530
>> Nii et see on kõik öelda, et me oleme võtnud
kolm erinevat lähenemist, üks

988
00:45:29,530 --> 00:45:32,210
neist kohe intuitiivne
Kohe Ben

989
00:45:32,210 --> 00:45:35,170
minu pakutud sisestamise
Sorteeri selle ühe

990
00:45:35,170 --> 00:45:38,540
kus sa sellist unustada
metsa puid esialgu.

991
00:45:38,540 --> 00:45:41,760
Aga siis, kui te võtate samm tagasi,
voila, oleme probleemi sorteerimine mõiste.

992
00:45:41,760 --> 00:45:43,824
Nii et see on, julgen öelda,
madalamal tasemel ehk

993
00:45:43,824 --> 00:45:45,740
kui mõned nende muude
algoritme, kuid olgem

994
00:45:45,740 --> 00:45:48,550
näha, kui me ei saa visualiseerida
Nende teel seda.

995
00:45:48,550 --> 00:45:51,450
>> Nii et see on mõne kena
tarkvara, et keegi

996
00:45:51,450 --> 00:45:56,110
kirjutas kasutades värvilisi baarid, mis on
kavatsevad teha järgmise meile.

997
00:45:56,110 --> 00:45:57,736
Igaüks neist baarid tähistab number.

998
00:45:57,736 --> 00:46:00,026
Pikem riba, seda suurem
arvu, väiksema baari,

999
00:46:00,026 --> 00:46:00,990
väiksem arv.

1000
00:46:00,990 --> 00:46:05,880
Nii ideaalis soovime kena püramiid
kus see algab väike ja saab suur,

1001
00:46:05,880 --> 00:46:08,330
ja see tähendaks, et
Nende baarid on järjestatud.

1002
00:46:08,330 --> 00:46:11,200
Nii et ma lähen edasi minna ja valida,
Näiteks Ben algoritm

1003
00:46:11,200 --> 00:46:13,990
first-- Valiksortimine.

1004
00:46:13,990 --> 00:46:16,220
>> Ja pane tähele, mis ta teeb.

1005
00:46:16,220 --> 00:46:18,670
See, kuidas nad on otsustanud
visualiseerida seda algoritmi

1006
00:46:18,670 --> 00:46:22,090
on see, et, nagu ma olin
jalgsi läbi minu nimekirja,

1007
00:46:22,090 --> 00:46:24,710
Selle programmi kõnnib
läbi selle jadaga,

1008
00:46:24,710 --> 00:46:28,160
rõhutades roosa igas
number, et ta vaatab.

1009
00:46:28,160 --> 00:46:32,360
Ja mis hakkab juhtuma just nüüd?

1010
00:46:32,360 --> 00:46:35,154
>> Väikseim number, mis
I või Ben leitud äkki

1011
00:46:35,154 --> 00:46:36,820
saab liigutada loendi alguses.

1012
00:46:36,820 --> 00:46:40,037
Ja teate, nad tegid Evict
arvu, mis oli seal,

1013
00:46:40,037 --> 00:46:41,120
ja see on täiesti korras.

1014
00:46:41,120 --> 00:46:42,600
Ma ei hakka sellesse detailsus.

1015
00:46:42,600 --> 00:46:44,308
Aga me peame
et number kusagil

1016
00:46:44,308 --> 00:46:47,775
nii me lihtsalt liikus see
avatud koha, mis oli loodud.

1017
00:46:47,775 --> 00:46:49,900
Nii et ma lähen kiirendada selle
üles, sest vastasel juhul

1018
00:46:49,900 --> 00:46:51,871
muutub väga tüütu kiiresti.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animatsioon speed-- seal me läheme.

1021
00:46:58,600 --> 00:47:01,850
Nüüd sama põhimõte
Olin kohaldades, aga sa

1022
00:47:01,850 --> 00:47:06,540
saab hakata end algoritmi, kui te
hakkab, ega näe seda veidi selgemalt.

1023
00:47:06,540 --> 00:47:13,190
Ja see algoritm mõjub
valides järgmise väikseim element,

1024
00:47:13,190 --> 00:47:16,422
nii et sa lähed alustada
vaata see ramp üles vasakule.

1025
00:47:16,422 --> 00:47:19,130
Ja iga iteratsiooni, kui ma
pakutud, see natuke vähem tööd.

1026
00:47:19,130 --> 00:47:21,921
See ei pea minema nii
tagasi vasakule nimekirja lõppu,

1027
00:47:21,921 --> 00:47:23,900
sest see on juba
tunneb neid on järjestatud.

1028
00:47:23,900 --> 00:47:28,129
Seega selline tunne see on
kiireneb, kuigi iga samm on

1029
00:47:28,129 --> 00:47:29,420
võttes samal aja jooksul.

1030
00:47:29,420 --> 00:47:31,600
Seal on lihtsalt vähem etappe jäänud.

1031
00:47:31,600 --> 00:47:35,240
Ja nüüd saab selline tunne
algoritm puhastamiseks lõpuks see,

1032
00:47:35,240 --> 00:47:37,040
ja tõepoolest nüüd on järjestatud.

1033
00:47:37,040 --> 00:47:41,620
>> Nii sisestamise sorteerida on kõik tehtud.

1034
00:47:41,620 --> 00:47:43,600
Mul on vaja uuesti juhuslikult massiivi.

1035
00:47:43,600 --> 00:47:45,940
Ja teate ma lihtsalt
hoida juhuvaliku see,

1036
00:47:45,940 --> 00:47:50,630
Võtame ühtlustamise
Sama lähenemist sisestamise omamoodi.

1037
00:47:50,630 --> 00:47:55,050
Lubage mul seda aeglustada siin.

1038
00:47:55,050 --> 00:47:56,915
Alustame et üle.

1039
00:47:56,915 --> 00:47:57,414
Stopp.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Olgem vahele neli.

1042
00:48:02,410 --> 00:48:03,200
Seal me läheme.

1043
00:48:03,200 --> 00:48:04,190
Randomize nad massiivi.

1044
00:48:04,190 --> 00:48:05,555
Ja siin me go-- sisestamise omamoodi.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Esita.

1047
00:48:12,800 --> 00:48:17,280
Pange tähele, et see tegeleb iga
element tal tekib kohe,

1048
00:48:17,280 --> 00:48:20,282
aga kui see kuulub
vales kohas teate

1049
00:48:20,282 --> 00:48:21,740
kõik tööd, mis peab juhtuma.

1050
00:48:21,740 --> 00:48:24,700
Me peame nihkub rohkem
ja mitu elementi, et teha ruumi

1051
00:48:24,700 --> 00:48:27,340
üks, me tahame paika panna.

1052
00:48:27,340 --> 00:48:30,740
>> Nii et me keskendudes
vasakule nimekirja lõppu ainult.

1053
00:48:30,740 --> 00:48:34,460
Märgata ei ole me isegi tundus at-- me
ei ole esile toodud roosad midagi

1054
00:48:34,460 --> 00:48:35,610
paremale.

1055
00:48:35,610 --> 00:48:38,180
Me lihtsalt tegelevad
probleeme, kui me minna,

1056
00:48:38,180 --> 00:48:40,430
kuid me luua palju
töötada ennast ikka.

1057
00:48:40,430 --> 00:48:44,410
Ja kui me seda kiirendada
nüüd kulgeda lõpuni,

1058
00:48:44,410 --> 00:48:46,210
sellel on teistsugune tunne, et see tõepoolest.

1059
00:48:46,210 --> 00:48:50,150
See on lihtsalt keskendudes vasakul lõpuni, kuid
teed natuke rohkem tööd needed--

1060
00:48:50,150 --> 00:48:53,230
Selline silumiseks asju
üle, millega asju,

1061
00:48:53,230 --> 00:48:58,350
kuid tegelevad lõpuks koos
iga element ühe korraga

1062
00:48:58,350 --> 00:49:07,740
kuni saame the-- hästi, me
kõik teame, kuidas see lõppeb,

1063
00:49:07,740 --> 00:49:09,700
nii et see on natuke underwhelming ehk.

1064
00:49:09,700 --> 00:49:12,830
>> Aga nimekiri väljatöötamiseni
spoiler-- läheb välja sorteerida.

1065
00:49:12,830 --> 00:49:15,300
Nii vaatame ühte viimane.

1066
00:49:15,300 --> 00:49:16,840
Me ei saa lihtsalt praegu vahele.

1067
00:49:16,840 --> 00:49:18,000
Me oleme peaaegu kohal.

1068
00:49:18,000 --> 00:49:19,980
Kaks minna, üks minna.

1069
00:49:19,980 --> 00:49:22,680
Ja voila.

1070
00:49:22,680 --> 00:49:23,450
Suurepärane.

1071
00:49:23,450 --> 00:49:27,220
>> Nüüd teeme ühe viimane,
uuesti juhuvaliku koos Mullsortimine.

1072
00:49:27,220 --> 00:49:31,690
Ja märkate siin, eriti kui ma aeglane see
maha, see hoiab swooping läbi.

1073
00:49:31,690 --> 00:49:36,830
Aga pane seda lihtsalt teeb paarikaupa
comparisons-- omamoodi kohalikke lahendusi.

1074
00:49:36,830 --> 00:49:39,050
Aga niipea, kui saame
lõpuks nimekiri roosa,

1075
00:49:39,050 --> 00:49:40,690
Mis läheb on korduda?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Jah, see läheb pea
alustada otsast peale, sest see ainult

1078
00:49:46,830 --> 00:49:49,870
fikseeritud paarikaupa vigu.

1079
00:49:49,870 --> 00:49:53,120
Ja mis võisid veel avaldunud teised.

1080
00:49:53,120 --> 00:49:58,950
Ja kui sa seda kiirendada, saate
näha, et palju nagu nimigi ütleb,

1081
00:49:58,950 --> 00:50:01,870
väiksem elements-- või pigem
suurem elements-- hakkavad

1082
00:50:01,870 --> 00:50:03,740
mulksuma üles, kui soovite.

1083
00:50:03,740 --> 00:50:07,380
Ja väiksemad elemendid on
hakanud mull alla vasakul.

1084
00:50:07,380 --> 00:50:10,780
Ja tõepoolest, see on omamoodi
visuaalne efekt samuti.

1085
00:50:10,780 --> 00:50:17,150
Ja nii see lõpuks viimistlus
väga sarnaselt ka.

1086
00:50:17,150 --> 00:50:19,160
>> Me ei pea elama
selle konkreetse ühe.

1087
00:50:19,160 --> 00:50:21,010
Lubage mul avada see nüüd ka.

1088
00:50:21,010 --> 00:50:24,040
Seal on mõned muud Sortimisalgoritm
maailmas, millest vähesed

1089
00:50:24,040 --> 00:50:25,580
on püütud siin.

1090
00:50:25,580 --> 00:50:29,960
Ja eriti õppijatele, kes ei ole
tingimata visuaalset või matemaatilise,

1091
00:50:29,960 --> 00:50:31,930
nagu tegime enne, saame
seda teha ka audially

1092
00:50:31,930 --> 00:50:34,210
Kui me seostame heli seda.

1093
00:50:34,210 --> 00:50:36,990
Ja lihtsalt lõbu, siin on
vähe erinevaid algoritme,

1094
00:50:36,990 --> 00:50:40,950
ja üks neist eriti sa oled
läheb teade nimetatakse "Mestimissortimine."

1095
00:50:40,950 --> 00:50:43,250
>> See on tegelikult täiesti
parem algoritm,

1096
00:50:43,250 --> 00:50:45,860
nii et Mestimissortimine, üks
need, mida sa parasjagu näha,

1097
00:50:45,860 --> 00:50:49,170
ei ole järjekorras n ruudus.

1098
00:50:49,170 --> 00:50:57,280
See on suurusjärgus n korda samamoodi
n, mis on tegelikult väiksem ja seega

1099
00:50:57,280 --> 00:50:58,940
kiiremini kui need teised kolm.

1100
00:50:58,940 --> 00:51:00,670
Ja seal on paar teiste
rumal need, mis me näeme.

1101
00:51:00,670 --> 00:51:01,933
>> Nii et siin me läheme mõne heli.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
See on sisestamise sorteerida, nii et jälle
see on lihtsalt tegemist elemendid

1104
00:51:10,490 --> 00:51:13,420
kui nad tulevad.

1105
00:51:13,420 --> 00:51:17,180
See on mull sorteerida, nii et see on
pidades neid paari korraga.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Ja jälle, suurim elemendid
on vahustamine kuni tippu.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Järgmisena Valiksortimine.

1110
00:51:41,710 --> 00:51:45,420
See on Ben algoritm, kus
jälle ta valides korduvalt

1111
00:51:45,420 --> 00:51:46,843
Järgmise väikseim element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Ja jälle, nüüd saab tõesti kuulda, et
see on kiirendades kuid ainult niivõrd,

1114
00:51:53,900 --> 00:51:58,230
sest see teeb vähem
töötada iga iteratsiooni.

1115
00:51:58,230 --> 00:52:04,170
See on kiirem üks, Mestimissortimine,
mis sorteerimine klastrite numbrid

1116
00:52:04,170 --> 00:52:05,971
kokku ja siis ühendab neid.

1117
00:52:05,971 --> 00:52:07,720
Nii look-- vasakul
pool on juba järjestatud.

1118
00:52:07,720 --> 00:52:14,165
>> Nüüd on sorteerimine paremal pool, ja
Nüüd siis läheb neid kombineerida ühte.

1119
00:52:14,165 --> 00:52:19,160
See on midagi, mida nimetatakse "Gnome omamoodi."

1120
00:52:19,160 --> 00:52:23,460
Ja saab sellist näha, et
see läheb edasi ja tagasi,

1121
00:52:23,460 --> 00:52:27,950
millega tööd natuke siin ja
seal enne, kui see toimub, siis uus töö.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Ja see ongi kõik.

1124
00:52:33,692 --> 00:52:36,400
On veel üks sort, mis on
tõesti ainult akadeemilistel eesmärkidel,

1125
00:52:36,400 --> 00:52:40,980
nn "loll omamoodi", mis võtab
Oma andmete sorteerib ta juhuslikult,

1126
00:52:40,980 --> 00:52:43,350
ja siis kontrollib, kui see on järjestatud.

1127
00:52:43,350 --> 00:52:47,880
Ja kui see ei ole, see uuesti sorteerib see
juhuslikult, kontrollib, kas see on järjestatud,

1128
00:52:47,880 --> 00:52:49,440
ja kui ei kordub.

1129
00:52:49,440 --> 00:52:52,660
Ja teoreetiliselt tõenäosuslikult
Selle ülesande täidetud

1130
00:52:52,660 --> 00:52:54,140
kuid pärast üsna natuke aega.

1131
00:52:54,140 --> 00:52:56,930
See ei ole kõige
tõhus algoritme.

1132
00:52:56,930 --> 00:53:02,550
Nii tekib küsimusi nende
Eelkõige algoritme või midagi

1133
00:53:02,550 --> 00:53:04,720
seotud ka seal?

1134
00:53:04,720 --> 00:53:09,430
>> Noh, nüüd kiusa peale mida kõik
need read on, et ma olen joonistus

1135
00:53:09,430 --> 00:53:15,090
ja mida ma olen eeldades arvuti
saab teha all kapuuts.

1136
00:53:15,090 --> 00:53:18,650
Ma väidan, et kõik need numbrid
Hoian drawing-- nad vajavad, et saada

1137
00:53:18,650 --> 00:53:21,330
salvestatud kusagil mälu.

1138
00:53:21,330 --> 00:53:24,130
Me saame sellest mehest lahti nüüd ka.

1139
00:53:24,130 --> 00:53:30,110
>> Nii tükk mälu on
computer-- nii RAM DIMM on

1140
00:53:30,110 --> 00:53:35,480
mida otsisime eile, dual
inline mälu module-- näeb välja selline.

1141
00:53:35,480 --> 00:53:39,370
Ja kõik need vähe must laastud
on mõned baitide arvu, tavaliselt.

1142
00:53:39,370 --> 00:53:44,380
Ja siis kulla sõrmed on nagu
juhtmed, et ühendada see arvuti,

1143
00:53:44,380 --> 00:53:47,521
ja roheline räni pardal on lihtsalt
mis hoiab kõike koos.

1144
00:53:47,521 --> 00:53:48,770
Mida see tegelikult tähendab?

1145
00:53:48,770 --> 00:53:53,180
Kui ma sellist teha seda sama pilt,
oletame lihtsuse

1146
00:53:53,180 --> 00:53:55,280
et see DIMM, Dual
mälumoodul,

1147
00:53:55,280 --> 00:54:00,530
on üks gigabait mälu, gigabaidi
mälu, mis on mitu baiti kokku?

1148
00:54:00,530 --> 00:54:02,100
Üks gigabait on mitu baiti?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Enamat.

1151
00:54:06,030 --> 00:54:09,960
1124 on kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega on miljon.

1153
00:54:11,730 --> 00:54:14,570
Giga miljardit.

1154
00:54:14,570 --> 00:54:15,070
>> Kas ma pikali?

1155
00:54:15,070 --> 00:54:16,670
Kas me isegi lugeda etikett?

1156
00:54:16,670 --> 00:54:19,920
See on tegelikult 128
gigabaiti, nii et see on rohkem.

1157
00:54:19,920 --> 00:54:22,130
Aga me teeselda, et see
on vaid üks gigabait.

1158
00:54:22,130 --> 00:54:25,640
Nii et see tähendab seal miljardit
baiti mälu minule

1159
00:54:25,640 --> 00:54:29,770
või 8 miljardit bitti, kuid me ei kavatse
rääkida nii baiti nüüd,

1160
00:54:29,770 --> 00:54:30,750
edasi liikuma.

1161
00:54:30,750 --> 00:54:36,330
>> Mida see tähendab, et see on
Ühebaidiline see järjekordne bait,

1162
00:54:36,330 --> 00:54:38,680
See on veel üks bait,
ja kui me tõesti tahtsid

1163
00:54:38,680 --> 00:54:43,280
olema konkreetsed oleks meil
joonistada miljardit ruudukesed.

1164
00:54:43,280 --> 00:54:44,320
Aga mida see tähendab?

1165
00:54:44,320 --> 00:54:46,420
Noh, las ma suurendamiseks
aastal selle pildi kohta.

1166
00:54:46,420 --> 00:54:50,900
Kui mul on midagi, mis tundub
niimoodi nüüd, et on neli baiti.

1167
00:54:50,900 --> 00:54:53,710
>> Ja nii ma võiks panna neli numbrit siin.

1168
00:54:53,710 --> 00:54:54,990
Üks kaks kolm neli.

1169
00:54:54,990 --> 00:55:00,170
Või ma võiks panna neli tähte või sümbolit.

1170
00:55:00,170 --> 00:55:02,620
"Hei!" võiks minna seal,
sest iga tähed,

1171
00:55:02,620 --> 00:55:04,370
Arutasime varem
võiks olla esindatud

1172
00:55:04,370 --> 00:55:06,650
Kaheksa bitti või ASCII või bait.

1173
00:55:06,650 --> 00:55:09,370
Nii teisisõnu, saate
panna 8 miljardit asjad sees

1174
00:55:09,370 --> 00:55:11,137
Selle üks pulk mälu.

1175
00:55:11,137 --> 00:55:14,345
Nüüd, mida see tähendab, et panna asju tagasi
et seljad mälu niimoodi?

1176
00:55:14,345 --> 00:55:17,330
See on see, mida programmeerija
nimetaksime "massiivi."

1177
00:55:17,330 --> 00:55:21,250
Arvutiprogrammi, siis ei usu
selle aluseks oleva riistvara, per se.

1178
00:55:21,250 --> 00:55:24,427
Sa mõtle ise, kellel
juurdepääs miljard baiti kokku

1179
00:55:24,427 --> 00:55:26,010
ja te saate midagi tahad sellega.

1180
00:55:26,010 --> 00:55:27,880
Aga mugavamaks
see on üldiselt kasulik

1181
00:55:27,880 --> 00:55:31,202
hoida oma mälu õigus
üksteise kõrval niimoodi.

1182
00:55:31,202 --> 00:55:33,660
Nii et kui ma suumida see--
sest me kindlasti ei lähe

1183
00:55:33,660 --> 00:55:39,310
tõmmata miljardit vähe squares--
oletame, et see esindab amet

1184
00:55:39,310 --> 00:55:40,610
et pulk mälu nüüd.

1185
00:55:40,610 --> 00:55:43,800
Ja ma lihtsalt teha nii palju kui minu
marker jõuab andis mulle siin.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Nüüd on meil kinni
mälu laual

1188
00:55:52,300 --> 00:55:56,400
et ju üks, kaks, kolm, neli, viis,
kuue, üks, kaks, kolm, neli, viis, kuus,

1189
00:55:56,400 --> 00:56:01,130
seven-- nii 42 baiti
mälu ekraanil kokku.

1190
00:56:01,130 --> 00:56:01,630
Aitäh.

1191
00:56:01,630 --> 00:56:02,838
Jah, tegin aritmeetiline õigus.

1192
00:56:02,838 --> 00:56:05,120
Nii 42 baiti mälu siin.

1193
00:56:05,120 --> 00:56:06,660
Mida see tegelikult tähendab?

1194
00:56:06,660 --> 00:56:09,830
Noh, programmeerija
tegelikult üldiselt

1195
00:56:09,830 --> 00:56:12,450
mõtle seda mälu adresseeritav.

1196
00:56:12,450 --> 00:56:16,630
Teisisõnu, igaüks neist
kohtades mälu, riistvara,

1197
00:56:16,630 --> 00:56:18,030
on unikaalne aadress.

1198
00:56:18,030 --> 00:56:22,020
>> See ei ole nii keeruline kui üks Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Selle asemel, et see on lihtsalt number.

1200
00:56:23,830 --> 00:56:27,930
See on bait number null, on see
üks on see kaks, see on kolm,

1201
00:56:27,930 --> 00:56:30,327
ja see on 41.

1202
00:56:30,327 --> 00:56:30,910
Oota hetk.

1203
00:56:30,910 --> 00:56:32,510
Ma arvasin, et ma ütlesin 42 hetk tagasi.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Hakkasin nullist,
nii see on tegelikult õige.

1206
00:56:37,772 --> 00:56:40,980
Nüüd ei pea tegelikult joonistada
ruudustik, ja kui te joonistada ruudustik

1207
00:56:40,980 --> 00:56:43,520
Ma arvan, et asjad tegelikult
natuke eksitav.

1208
00:56:43,520 --> 00:56:46,650
Mis Programmeerija,
tema enda meeles,

1209
00:56:46,650 --> 00:56:50,310
üldiselt arvan sellest
mälu on nagu lint,

1210
00:56:50,310 --> 00:56:53,340
nagu tükk maalriteip
et lihtsalt läheb ja igavesti

1211
00:56:53,340 --> 00:56:54,980
või kuni sa otsa mälu.

1212
00:56:54,980 --> 00:56:59,200
Nii palju levinum viis juhtida
ja mõelge mälu

1213
00:56:59,200 --> 00:57:03,710
Oleks, et see on bait null, üks,
kaks, kolm, ja siis dot, dot, dot.

1214
00:57:03,710 --> 00:57:07,650
Ja sul on 42 sellised baiti kokku, isegi
Kuigi füüsiliselt võib see tegelikult

1215
00:57:07,650 --> 00:57:09,480
olla midagi enamat niimoodi.

1216
00:57:09,480 --> 00:57:12,850
>> Nii et kui te nüüd arvate teie
mälu, kuna see, nagu lindi,

1217
00:57:12,850 --> 00:57:17,640
See on see, mida programmeerija uuesti
kutsuks hulga mälu.

1218
00:57:17,640 --> 00:57:20,660
Ja kui sa tahad tegelikult salvestada
midagi arvuti mälus,

1219
00:57:20,660 --> 00:57:23,290
sa tavaliselt teha poest asju
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Nii oleme rääkinud numbrid.

1221
00:57:25,010 --> 00:57:30,880
Ja kui ma tahtsin, et lahendada probleeme
nagu neli, üks, kolm, kaks,

1222
00:57:30,880 --> 00:57:33,820
kuigi ma just joonistus
ainult numbrid neli, üks, kolm,

1223
00:57:33,820 --> 00:57:39,490
kaks laual, arvuti oleks
tõesti on see setup mälu.

1224
00:57:39,490 --> 00:57:43,347
>> Ja mis oleks kõrval
kaks arvuti mällu?

1225
00:57:43,347 --> 00:57:44,680
Noh, ei ole vastust.

1226
00:57:44,680 --> 00:57:45,770
Me tõesti ei tea.

1227
00:57:45,770 --> 00:57:48,200
Ja nii kaua, kui
arvuti ei vaja seda,

1228
00:57:48,200 --> 00:57:51,440
see ei pea hooli, mis on järgmine
numbritele see hoolivad.

1229
00:57:51,440 --> 00:57:55,130
Ja kui ma ütlesin, et arvuti
saab vaadata ainult ühel aadressil korraga

1230
00:57:55,130 --> 00:57:56,170
See on selline, miks.

1231
00:57:56,170 --> 00:57:59,490
>> Mitte erinevalt rekord
mängija ja lugemispea

1232
00:57:59,490 --> 00:58:03,030
ainult suuda vaadata teatud
soon füüsilise vana kooli rekord

1233
00:58:03,030 --> 00:58:06,500
korraga, sarnaselt
Kas arvuti tänu

1234
00:58:06,500 --> 00:58:09,810
oma CPU ja selle
Intel käsustik

1235
00:58:09,810 --> 00:58:12,480
hulgast, kelle juhendamise
loetakse mälust

1236
00:58:12,480 --> 00:58:15,590
või salvestada memory--
arvuti saab vaadata ainult

1237
00:58:15,590 --> 00:58:19,210
ühes kohas kell AEG_
mõnikord nende kombinatsiooni,

1238
00:58:19,210 --> 00:58:21,770
aga tõesti ainult ühes kohas korraga.

1239
00:58:21,770 --> 00:58:24,770
Nii et kui me teeme
Nende erinevate algoritmide

1240
00:58:24,770 --> 00:58:28,110
Ma ei ole lihtsalt kirjalikult oma
vacuum-- neli, üks, kolm, kaks.

1241
00:58:28,110 --> 00:58:30,849
Need numbrid tegelikult kuuluvad
kusagil füüsilist mälu.

1242
00:58:30,849 --> 00:58:32,890
Seega on tilluke
transistorid või mingi

1243
00:58:32,890 --> 00:58:35,840
elektroonika all
kapuutsi ladustamiseks neid väärtusi.

1244
00:58:35,840 --> 00:58:40,460
>> Ja kokku, kui palju bitid
seotud just nüüd, just olema selge?

1245
00:58:40,460 --> 00:58:45,580
Nii et see on neli baiti, või
nüüd on 32 bitti kokku.

1246
00:58:45,580 --> 00:58:49,280
Nii on tegelikult 32 nullid ja
need moodustavad need neli asja.

1247
00:58:49,280 --> 00:58:52,070
Seal on isegi rohkem siin, kuid
jälle me ei hooli sellest.

1248
00:58:52,070 --> 00:58:55,120
>> Vaatame nüüd küsida teise
küsimus mälust,

1249
00:58:55,120 --> 00:58:57,519
sest et lõpus
päeval on vastuolus.

1250
00:58:57,519 --> 00:59:00,310
Ükskõik, mida me võiksime teha
arvuti, lõpus päeval

1251
00:59:00,310 --> 00:59:02,560
riistvara on ikka
Sama all kapuuts.

1252
00:59:02,560 --> 00:59:04,670
Kuidas ma Hoida sõna siin?

1253
00:59:04,670 --> 00:59:09,710
Noh, sõna arvuti nagu
"Hei!" oleks salvestatud lihtsalt niimoodi.

1254
00:59:09,710 --> 00:59:12,300
Ja kui sa tahad pikemat
Ühesõnaga, saate lihtsalt

1255
00:59:12,300 --> 00:59:19,120
kirjutatakse seda ja öelda midagi
nagu "tere" ja pood siin.

1256
00:59:19,120 --> 00:59:23,930
>> Ja nii ka siin see contiguousness
on tegelikult ära,

1257
00:59:23,930 --> 00:59:26,530
sest arvuti saab lihtsalt
lugeda paremalt vasakule.

1258
00:59:26,530 --> 00:59:28,680
Aga siin on küsimus.

1259
00:59:28,680 --> 00:59:33,480
Seoses selle sõna
h-e-L-l-o, hüüumärk,

1260
00:59:33,480 --> 00:59:38,740
kuidas võiks arvuti tea, kus
Sõna algab ja kus sõna lõpeb?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Seoses numbrid,
Kuidas arvuti

1263
00:59:43,800 --> 00:59:48,396
tea, kui kaua jada
numbrid on või kus see algab?

1264
00:59:48,396 --> 00:59:50,270
Noh, selgub out--
ja me ei lähe liiga palju

1265
00:59:50,270 --> 00:59:54,970
sellesse tase detail--
arvutid liikuda kraami ringi mälu

1266
00:59:54,970 --> 00:59:57,800
sõna otseses mõttes teel need aadressid.

1267
00:59:57,800 --> 01:00:02,080
Nii arvuti, kui sa oled
kirjalikult koodi salvestada asju

1268
01:00:02,080 --> 01:00:05,800
nagu sõnad, mida sa
tõesti teevad kirjutab

1269
01:00:05,800 --> 01:00:11,320
väljendeid mäletavad, kus on
arvuti mällu need sõnad on.

1270
01:00:11,320 --> 01:00:14,370
Nii et lubage mul teha väga,
väga lihtsa näite.

1271
01:00:14,370 --> 01:00:18,260
>> Ma lähen edasi minna ja
avada lihtsa teksti programmi

1272
01:00:18,260 --> 01:00:20,330
ja ma lähen, et luua
fail nimega hello.c.

1273
01:00:20,330 --> 01:00:22,849
Suurem osa sellest informatsioonist, mida me
ei hakka väga täpselt,

1274
01:00:22,849 --> 01:00:25,140
aga ma lähen kirjutada
Programm samas keeles,

1275
01:00:25,140 --> 01:00:31,140
C. See on palju rohkem hirmutav,
Ma väidan, kui Scratch,

1276
01:00:31,140 --> 01:00:32,490
aga see on väga sarnase sisuga.

1277
01:00:32,490 --> 01:00:34,364
Tegelikult need lokkis
braces-- saate liiki

1278
01:00:34,364 --> 01:00:37,820
mõelda, mida ma tegin, sest see.

1279
01:00:37,820 --> 01:00:39,240
>> Teeme seda tegelikult.

1280
01:00:39,240 --> 01:00:45,100
Kui roheline lipp klõpsates
teha järgmist.

1281
01:00:45,100 --> 01:00:50,210
Ma tahan välja printida "tere."

1282
01:00:50,210 --> 01:00:51,500
Nii et see on nüüd pseudokoodi.

1283
01:00:51,500 --> 01:00:53,000
Ma olen selline hägustumas jooned.

1284
01:00:53,000 --> 01:00:56,750
In C, selles keeles Ma räägin
umbes, see rida print tere

1285
01:00:56,750 --> 01:01:01,940
tegelikult muutub "printf" koos
mõned sulud ja semikooloniga.

1286
01:01:01,940 --> 01:01:03,480
>> Aga see on täpselt sama mõte.

1287
01:01:03,480 --> 01:01:06,730
Ja seda väga kasutajasõbralik
"Kui roheline lipp klõpsatud" muutub

1288
01:01:06,730 --> 01:01:10,182
märksa kauge "int main void."

1289
01:01:10,182 --> 01:01:12,890
Ja see on tõesti ei ole kaardistamine,
nii et ma lihtsalt lähen ignoreerida seda.

1290
01:01:12,890 --> 01:01:17,210
Aga looksulg on nagu
kaardus puzzle tükki niimoodi.

1291
01:01:17,210 --> 01:01:18,700
>> Nii saab mingi arvata.

1292
01:01:18,700 --> 01:01:22,357
Isegi kui sa pole kunagi programmeeritud enne,
Mida see programm ilmselt teha?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Tõenäoliselt prindib tere
hüüumärk.

1295
01:01:28,000 --> 01:01:29,150
>> Nii proovime seda.

1296
01:01:29,150 --> 01:01:30,800
Ma lähen seda salvestada.

1297
01:01:30,800 --> 01:01:34,000
Ja see on jällegi väga
vana kooli keskkonnas.

1298
01:01:34,000 --> 01:01:35,420
Ma ei saa klõpsata, ma ei saa tõmmata.

1299
01:01:35,420 --> 01:01:36,910
Ma pean käske.

1300
01:01:36,910 --> 01:01:41,320
Ma tahan joosta minu programmi, nii et
Ma võiks seda teha, nagu hello.c.

1301
01:01:41,320 --> 01:01:42,292
See fail jooksin.

1302
01:01:42,292 --> 01:01:43,500
Aga oota, ma puudu samm.

1303
01:01:43,500 --> 01:01:46,470
Mida me ütleme, on vaja
samm keeles nagu C?

1304
01:01:46,470 --> 01:01:49,470
Ma olen lihtsalt kirjutatud allikas
koodi, aga mida ma vajan?

1305
01:01:49,470 --> 01:01:50,670
Jah, mul on vaja koostaja.

1306
01:01:50,670 --> 01:01:57,670
Nii minu Mac siin, mul on
programmi nimega GCC GNU C kompilaator,

1307
01:01:57,670 --> 01:02:03,990
mis võimaldab mul teha see-- omakorda
minu lähtekoodi, me nimetame seda,

1308
01:02:03,990 --> 01:02:04,930
masinkoodi.

1309
01:02:04,930 --> 01:02:10,180
>> Ja ma näen, et
jälle järgmiselt need

1310
01:02:10,180 --> 01:02:14,090
on ühtede ja nullide ma lihtsalt
loodud minu lähtekoodi

1311
01:02:14,090 --> 01:02:15,730
kõik ühtede ja nullide.

1312
01:02:15,730 --> 01:02:17,770
Ja kui ma jooksen
minu program-- see juhtub

1313
01:02:17,770 --> 01:02:23,010
mida nimetatakse a.out eest
ajalooline reasons-- "tere."

1314
01:02:23,010 --> 01:02:24,070
Ma saan käivitada uuesti.

1315
01:02:24,070 --> 01:02:25,690
Tere, tere, tere.

1316
01:02:25,690 --> 01:02:27,430
Ja tundub toimivat.

1317
01:02:27,430 --> 01:02:31,000
>> Aga see tähendab, et kuskil minu
Arvuti mälu on sõnad

1318
01:02:31,000 --> 01:02:35,279
h-e-L-l-o, hüüumärk.

1319
01:02:35,279 --> 01:02:38,070
Ja selgub, niisama kõrvale,
Mis arvuti on tavaliselt

1320
01:02:38,070 --> 01:02:40,550
seda, et ta teab, kus
asjad hakkavad ja väljatöötamiseni see

1321
01:02:40,550 --> 01:02:42,460
panen eriline sümbol siin.

1322
01:02:42,460 --> 01:02:46,064
Ja konventsiooni eesmärk on panna
number null lõpus sõna

1323
01:02:46,064 --> 01:02:48,230
nii et sa tead, kus see
tegelikult lõpeb, nii et sa

1324
01:02:48,230 --> 01:02:52,750
ei hoia väljatrükk rohkem
tegelased kui sa tegelikult kavatsevad.

1325
01:02:52,750 --> 01:02:55,400
>> Aga Buffee siin, isegi
kuigi see on üsna kauge,

1326
01:02:55,400 --> 01:02:58,140
on, et see lõpuks
suhteliselt lihtne.

1327
01:02:58,140 --> 01:03:04,550
Sa said omamoodi lint, tühja
ruumi, kus saab kirjutada kirju.

1328
01:03:04,550 --> 01:03:07,150
Sa lihtsalt pead olema
erisümboliga nagu suvaliselt

1329
01:03:07,150 --> 01:03:10,316
number null, panna lõpus
oma sõnu nii, et arvuti teab,

1330
01:03:10,316 --> 01:03:13,410
oh, ma peaksin lõpetama printimist pärast
Näen hüüumärk.

1331
01:03:13,410 --> 01:03:16,090
Kuna järgmine asi seal
on ASCII väärtus null,

1332
01:03:16,090 --> 01:03:19,125
või null iseloomu
keegi oleks seda nimetada.

1333
01:03:19,125 --> 01:03:21,500
Aga seal on mingi probleem
siin, ja olgem siis tagasi

1334
01:03:21,500 --> 01:03:23,320
Numbrite hetkeks.

1335
01:03:23,320 --> 01:03:28,720
Oletame, et ma tegelikult
on massiivi numbrid,

1336
01:03:28,720 --> 01:03:30,730
ja oletame, et
Programm Ma kirjutan on

1337
01:03:30,730 --> 01:03:34,680
nagu klass raamat õpetaja
ja õpetajad klassiruumis.

1338
01:03:34,680 --> 01:03:38,720
Ja see programm võimaldab tal
kirjuta oma õpilaste hinded

1339
01:03:38,720 --> 01:03:39,960
kohta viktoriine.

1340
01:03:39,960 --> 01:03:43,750
Ja oletame, et üliõpilane saab
100 oma esimesele viktoriin, võibolla

1341
01:03:43,750 --> 01:03:49,920
nagu 80 järgmise üks, siis
75, siis 90 neljanda viktoriini.

1342
01:03:49,920 --> 01:03:54,150
>> Nii siinkohal lugu,
massiiv on suuruse neli.

1343
01:03:54,150 --> 01:03:58,470
Seal on absoluutselt rohkem mälu
arvuti, kuid massiiv, nii et rääkida,

1344
01:03:58,470 --> 01:04:00,350
on suurus neli.

1345
01:04:00,350 --> 01:04:06,060
Oletame nüüd, et õpetaja tahab
määrata viiendiku viktoriin klassis.

1346
01:04:06,060 --> 01:04:08,510
Noh, üks asju, mida ta
või ta läheb tegema

1347
01:04:08,510 --> 01:04:10,650
Nüüd on hoida lisaväärtust siin.

1348
01:04:10,650 --> 01:04:15,490
Aga kui massiivi õpetajal on
loodud see programm on suurus,

1349
01:04:15,490 --> 01:04:22,440
üks probleem array on see, et
sa ei saa lihtsalt hoida lisades mälu.

1350
01:04:22,440 --> 01:04:26,470
Sest mis siis, kui teine ​​osa
Programm on sõna "hei" seal?

1351
01:04:26,470 --> 01:04:29,650
>> Teisisõnu, mu mälu võib olla
kasutatakse millegi programmi.

1352
01:04:29,650 --> 01:04:33,250
Ja kui enne ma kirjutada, hei,
Ma tahan, et sisestada neli viktoriini skoorid,

1353
01:04:33,250 --> 01:04:34,784
nad võivad minna siin ja siin.

1354
01:04:34,784 --> 01:04:37,700
Ja kui sa äkki meelt muuta
hiljem ja öelda, et ma tahan viiendiku viktoriin

1355
01:04:37,700 --> 01:04:40,872
skoor, sa ei saa lihtsalt
pane see kus iganes soovite,

1356
01:04:40,872 --> 01:04:42,580
sest mis siis, kui see
mälu on kasutusel

1357
01:04:42,580 --> 01:04:45,990
midagi else-- mõne muu programmi
või mõni muu element programmis

1358
01:04:45,990 --> 01:04:46,910
et sa kasutad?

1359
01:04:46,910 --> 01:04:50,650
Nii et sa pead mõtlema enne
kuidas soovite salvestada oma andmeid,

1360
01:04:50,650 --> 01:04:54,480
sest nüüd olete värvitud
ise digitaalseks nurgas.

1361
01:04:54,480 --> 01:04:57,280
>> Nii võib õpetaja asemel
öelda, kui kirjalikult programmi

1362
01:04:57,280 --> 01:04:59,360
salvestada tema
klassid, tead mis?

1363
01:04:59,360 --> 01:05:04,180
Ma küsida,
kirjutamise ajal oma programm,

1364
01:05:04,180 --> 01:05:12,070
et ma tahan null, üks, kaks, kolm,
nelja, viie, kuue, kaheksa klassid kokku.

1365
01:05:12,070 --> 01:05:15,320
Nii üks, kaks, kolm, neli,
viis, kuus, seitse, kaheksa.

1366
01:05:15,320 --> 01:05:18,612
Õpetaja võib lihtsalt üle jaotada
mälu, kui kirjalikult oma programmi

1367
01:05:18,612 --> 01:05:19,570
ja öelda, et tead, mida?

1368
01:05:19,570 --> 01:05:22,236
Ma ei kavatse määrata rohkem
kui kaheksa viktoriinid semestris.

1369
01:05:22,236 --> 01:05:23,130
See on lihtsalt hull.

1370
01:05:23,130 --> 01:05:24,470
Ma ei saa kunagi eraldada seda.

1371
01:05:24,470 --> 01:05:28,270
Nii et sel viisil ta on
paindlikkust poest õpilase hinded,

1372
01:05:28,270 --> 01:05:33,010
nagu 75, 90, ja võib-olla üks ekstra kus
õpilane sai lisapunkte, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Aga kui õpetaja kunagi
kasutab neid kolme ruumid,

1374
01:05:36,130 --> 01:05:38,860
seal on intuitiivne Buffee siin.

1375
01:05:38,860 --> 01:05:41,410
Ta on lihtsalt raiskab ruumi.

1376
01:05:41,410 --> 01:05:44,790
Nii teisisõnu, seal on see
ühise Miinuseks programmeerimine

1377
01:05:44,790 --> 01:05:48,241
kus saab kas eraldada
täpselt nii palju mälu, kui soovite,

1378
01:05:48,241 --> 01:05:51,490
tagurpidi, mis seisneb selles, et sa oled super
efficient-- et sa ei ole raiskav

1379
01:05:51,490 --> 01:05:54,640
kell all-- kuid negatiivseid millest
ongi, kui muudad oma meelt, kui

1380
01:05:54,640 --> 01:05:58,780
kasutades programmi, mida soovite salvestada
rohkem andmeid, kui sa algselt mõeldud.

1381
01:05:58,780 --> 01:06:03,030
>> Ehk lahendus on, siis
kirjuta oma programmides nii

1382
01:06:03,030 --> 01:06:05,605
et nad kasutavad rohkem mälu
kui nad tegelikult vajavad.

1383
01:06:05,605 --> 01:06:07,730
Nii sa ei kavatse
joosta, et probleem,

1384
01:06:07,730 --> 01:06:09,730
Aga Sa oled raiskav.

1385
01:06:09,730 --> 01:06:12,960
Ja mida rohkem mälu oma programm kasutab,
kui me arutasime eile, seda vähem

1386
01:06:12,960 --> 01:06:15,410
mälu, mis on saadaval
teisi programme,

1387
01:06:15,410 --> 01:06:18,790
varem arvuti võib aeglustada
alla, sest virtuaalmälu.

1388
01:06:18,790 --> 01:06:22,670
Ja nii ideaalne lahendus võiks olla see, mida?

1389
01:06:22,670 --> 01:06:24,610
>> Vastavalt jaotada tundub halb.

1390
01:06:24,610 --> 01:06:27,030
Üle jaotada tundub halb.

1391
01:06:27,030 --> 01:06:31,120
Mis võiks olla parem lahendus?

1392
01:06:31,120 --> 01:06:32,390
Ümberjaotamine.

1393
01:06:32,390 --> 01:06:33,590
Ole dünaamilisemaks.

1394
01:06:33,590 --> 01:06:37,520
Ärge suruge ennast valida
priori alguses, mida sa tahad.

1395
01:06:37,520 --> 01:06:41,370
Ja kindlasti ei üle jaotada,
muidu sa raiskamine.

1396
01:06:41,370 --> 01:06:45,770
>> Ja nii, et selle eesmärgi saavutamiseks oleme
vaja visata andmete struktuuri,

1397
01:06:45,770 --> 01:06:48,100
nii-öelda ära.

1398
01:06:48,100 --> 01:06:51,080
Ja mis siis programmeerija
tüüpiliselt kasutada

1399
01:06:51,080 --> 01:06:55,940
on midagi, mida nimetatakse mitte
massiivi kuid ahelloend.

1400
01:06:55,940 --> 01:07:00,860
Teisisõnu, ta saab
hakata mõtlema oma mälu

1401
01:07:00,860 --> 01:07:05,280
nagu oleks mingi kuju, et nad
saab juhtida järgmisel viisil.

1402
01:07:05,280 --> 01:07:08,520
Kui ma tahan salvestada ühe numbri
program-- nii et see on septembril

1403
01:07:08,520 --> 01:07:12,600
Ma olen andnud oma õpilastele viktoriin; tahan
salvestada õpilaste esimesele viktoriin,

1404
01:07:12,600 --> 01:07:16,220
ja nad said 100 see-- ma
küsin minu arvuti,

1405
01:07:16,220 --> 01:07:19,540
teel programm Olen
kirjutatud, ühe tüki mälu.

1406
01:07:19,540 --> 01:07:22,570
Ja ma lähen salvestada
number 100, ja ongi kõik.

1407
01:07:22,570 --> 01:07:24,820
>> Siis paar nädalat hiljem
kui ma saan teist viktoriin,

1408
01:07:24,820 --> 01:07:27,890
ja see on aeg, et sisestada
et 90%, ma lähen

1409
01:07:27,890 --> 01:07:32,129
küsida arvuti, hei, arvuti,
saan teise patakas mälu?

1410
01:07:32,129 --> 01:07:34,170
See läheb mulle seda
tühja patakas mälu.

1411
01:07:34,170 --> 01:07:39,370
Ma panen arvu 90,
kuid minu programmi kuidagi või other--

1412
01:07:39,370 --> 01:07:42,100
ja me ei pea muretsema
süntaks see-- vajan

1413
01:07:42,100 --> 01:07:44,430
kuidagi kett need asjad kokku.

1414
01:07:44,430 --> 01:07:47,430
Ja ma kett neile koos
mis näeb välja nagu nool siin.

1415
01:07:47,430 --> 01:07:50,050
>> Kolmas viktoriin, mis kerkib,
Ma lähen öelda, hei, arvuti,

1416
01:07:50,050 --> 01:07:51,680
anna mulle veel patakas mälu.

1417
01:07:51,680 --> 01:07:54,660
Ja ma lähen panema
mis iganes see oli, nagu 75,

1418
01:07:54,660 --> 01:07:56,920
ja ma pean kett seda
koos nüüd kuidagi.

1419
01:07:56,920 --> 01:08:00,290
Neljas viktoriin jõuab mööda, ja võib-olla
see on poole semestri lõpuks.

1420
01:08:00,290 --> 01:08:03,140
Ja selles punktis oma programmi
Võib olla kasutades mälu

1421
01:08:03,140 --> 01:08:05,540
kõikjal, üle kogu füüsiliselt.

1422
01:08:05,540 --> 01:08:08,170
Ja nii lihtsalt peksab, ma olen
läheb juhtida seda edasi

1423
01:08:08,170 --> 01:08:11,260
quiz-- ma unustan, mis see oli; mina
arvan, võibolla 80 või midagi--

1424
01:08:11,260 --> 01:08:12,500
kuidas siin.

1425
01:08:12,500 --> 01:08:15,920
>> Aga see on hea, sest piltlikult
Ma lähen juhtida seda joont.

1426
01:08:15,920 --> 01:08:19,063
Teisisõnu, et tegelikkuses
arvuti riistvara,

1427
01:08:19,063 --> 01:08:20,979
esimene tulemus võiks
lõpuks siin, sest see on

1428
01:08:20,979 --> 01:08:22,529
kohe alguses poolaastal.

1429
01:08:22,529 --> 01:08:25,810
Järgmise üks sattuda siin
sest natuke aega on möödas

1430
01:08:25,810 --> 01:08:27,210
ja programm peab näitama.

1431
01:08:27,210 --> 01:08:30,060
Järgmine tulemus, mis oli
75, võib olla siin.

1432
01:08:30,060 --> 01:08:33,420
Ja viimane tulemus võib olla
80, mis on siin.

1433
01:08:33,420 --> 01:08:38,729
>> Nii et tegelikkuses füüsiliselt, see võib olla
mida teie arvuti mälu välja näeb.

1434
01:08:38,729 --> 01:08:41,569
Kuid see ei ole kasulik vaimse
paradigma programmeerija.

1435
01:08:41,569 --> 01:08:44,649
Miks peaks sul kus
Heck oma andmed jõuavad?

1436
01:08:44,649 --> 01:08:46,200
Sa tahad salvestada andmeid.

1437
01:08:46,200 --> 01:08:49,390
>> See on selline nagu meie arutelu
varem joonistamise kuubik.

1438
01:08:49,390 --> 01:08:52,200
Miks sa huvita, mida
nurk on kuubik

1439
01:08:52,200 --> 01:08:53,740
ja kuidas teil pöörduda joonistada?

1440
01:08:53,740 --> 01:08:54,950
Sa tahad kuubik.

1441
01:08:54,950 --> 01:08:57,359
Samamoodi siin, siis
tahan hinne raamat.

1442
01:08:57,359 --> 01:08:59,559
Sa tahad mõelda
seda nimekirja numbrid.

1443
01:08:59,559 --> 01:09:01,350
Keda huvitab, kuidas see
rakendatakse riistvara?

1444
01:09:01,350 --> 01:09:05,180
>> Nii võtmiseks nüüd
on see pilt siin.

1445
01:09:05,180 --> 01:09:07,580
See on seotud nimekirja, kuna
programmeerija oleks seda nimetada,

1446
01:09:07,580 --> 01:09:10,640
kuivõrd teil on
nimekirja, ilmselt numbreid.

1447
01:09:10,640 --> 01:09:14,990
Aga see on seotud piltlikult
teel Nende nooled,

1448
01:09:14,990 --> 01:09:18,510
ja kõik need nooled are-- all
kapuutsi, kui sa oled uudishimulik,

1449
01:09:18,510 --> 01:09:23,210
Tuletame meelde, et meie füüsilise riistvara on
aadressid null, üks, kaks, kolm, neli.

1450
01:09:23,210 --> 01:09:28,465
Kõik need nooled on on nagu kaart
või suundades, kus kui 90 on-- nüüd

1451
01:09:28,465 --> 01:09:29,090
Sain loota.

1452
01:09:29,090 --> 01:09:31,750
>> Null, üks, kaks, kolm,
nelja, viie, kuue, seitsme.

1453
01:09:31,750 --> 01:09:35,640
Tundub, et 90 on
mälu aadressi number seitse.

1454
01:09:35,640 --> 01:09:38,460
Kõik need nooled on on
nagu väike paberiribad

1455
01:09:38,460 --> 01:09:42,439
mis on andes suunad
programm, mis ütleb, järgige selle kaardiga

1456
01:09:42,439 --> 01:09:43,880
saada asukohta seitse.

1457
01:09:43,880 --> 01:09:46,680
Ja seal leiad
õpilane teise viktoriini tulemus.

1458
01:09:46,680 --> 01:09:52,100
Vahepeal 75-- kui ma jätkuvalt seda,
see on seitse, kaheksa, üheksa, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> See teine ​​nool lihtsalt esindab
kaart, mäluasukoha 15.

1461
01:09:59,080 --> 01:10:02,550
Aga jälle, programmeerija üldjuhul ei
ei hooli sellest detailsus.

1462
01:10:02,550 --> 01:10:05,530
Ja kõige iga programmeerimine
keelt täna, programmeerija

1463
01:10:05,530 --> 01:10:10,490
isegi ei tea, kus mälu
need numbrid tegelikult on.

1464
01:10:10,490 --> 01:10:14,830
Kõik on tal hoolivad on
et nad on mingil viisil omavahel seotud

1465
01:10:14,830 --> 01:10:18,390
andmestruktuur niimoodi.

1466
01:10:18,390 --> 01:10:21,580
>> Selgub aga mitte
saada liiga tehniline.

1467
01:10:21,580 --> 01:10:27,430
Aga kuna me saame olla
endale lubada seda arutelu siin,

1468
01:10:27,430 --> 01:10:33,630
Oletame, et meil vaadata
Selle probleemi siin massiivi.

1469
01:10:33,630 --> 01:10:35,780
Vaatame, kas meil on kahju, läheb siin.

1470
01:10:35,780 --> 01:10:42,950
See on 100, 90, 75, ja 80.

1471
01:10:42,950 --> 01:10:44,980
>> Lubage mul lühidalt teha selle nõude.

1472
01:10:44,980 --> 01:10:48,980
See on massiiv, ja jälle
väljapaistev iseloomulik massiivi

1473
01:10:48,980 --> 01:10:52,400
on see, et kõik andmed on tagasi
seljad in memory-- sõna otseses mõttes

1474
01:10:52,400 --> 01:10:56,830
üks bait või hoopis neli baiti,
mõned fikseeritud baitide arv kaugusel.

1475
01:10:56,830 --> 01:11:00,710
Ühes seotud nimekirja, mida võiksime teha
niimoodi, all kapuuts, kes

1476
01:11:00,710 --> 01:11:02,000
teab, kus see kraam on?

1477
01:11:02,000 --> 01:11:03,630
See ei pea isegi voolu niimoodi.

1478
01:11:03,630 --> 01:11:06,050
Mõned andmed võivad olla ka
tagasi vasakule seal.

1479
01:11:06,050 --> 01:11:07,530
Sa ei tea isegi.

1480
01:11:07,530 --> 01:11:15,430
>> Ja nii array, teil on
funktsioon tuntud muutmälu.

1481
01:11:15,430 --> 01:11:20,570
Ja mis muutmälu vahendid on
et arvuti saab hüpata koheselt

1482
01:11:20,570 --> 01:11:22,730
kõikjale massiivi.

1483
01:11:22,730 --> 01:11:23,580
Miks?

1484
01:11:23,580 --> 01:11:26,000
Kuna arvuti teab
et esimene asukoht on

1485
01:11:26,000 --> 01:11:29,540
null, üks, kaks, ja kolm.

1486
01:11:29,540 --> 01:11:33,890
>> Ja kui sa tahad minna
Selle elemendi järgmisele element,

1487
01:11:33,890 --> 01:11:36,099
sa sõna otseses mõttes, et
arvuti meeles, lihtsalt lisage esimene kommentaar.

1488
01:11:36,099 --> 01:11:39,140
Kui soovite minna kolmas element,
lihtsalt lisada one-- järgmine element, vaid

1489
01:11:39,140 --> 01:11:40,290
lisage esimene kommentaar.

1490
01:11:40,290 --> 01:11:42,980
Kuid selles versioonis
lugu oletame

1491
01:11:42,980 --> 01:11:46,080
arvuti on praegu otsin
kell või tegelevad number 100.

1492
01:11:46,080 --> 01:11:49,770
Kuidas sa saad järgmisele
klassi klassi raamat?

1493
01:11:49,770 --> 01:11:52,560
>> Sa pead võtma seitse
samme, mis on meelevaldne.

1494
01:11:52,560 --> 01:11:58,120
Et saada järgmise üks, sa pead
võtab veel kaheksa sammu, et saada 15.

1495
01:11:58,120 --> 01:12:02,250
Teisisõnu, see ei ole
konstantne lõhet numbrid,

1496
01:12:02,250 --> 01:12:04,857
ja nii see lihtsalt võtab
Arvuti rohkem aega mõtet.

1497
01:12:04,857 --> 01:12:06,940
Arvutil on otsida
läbi mälu, et

1498
01:12:06,940 --> 01:12:08,990
leida, mida te otsite.

1499
01:12:08,990 --> 01:12:14,260
>> Nii arvestades massiivi kipub olema
kiire andmeside structure-- sest sa

1500
01:12:14,260 --> 01:12:17,610
võib sõna otseses mõttes lihtsalt teha lihtsa aritmeetilise
ja saada kuhu tahad, lisades ühe,

1501
01:12:17,610 --> 01:12:21,300
jaoks instance-- ahelloend,
sa ohverdama, et funktsioon.

1502
01:12:21,300 --> 01:12:24,020
Sa ei saa lihtsalt minna esimest
et teiselt kolmandale neljandale.

1503
01:12:24,020 --> 01:12:25,240
Sa pead järgima kaardil.

1504
01:12:25,240 --> 01:12:28,160
Sa pead võtma rohkem samme
saada need väärtused, mis

1505
01:12:28,160 --> 01:12:30,230
tundub olevat lisades kulu.

1506
01:12:30,230 --> 01:12:35,910
Nii et me maksab ka, aga mis oli
funktsioon, mis Dan otsis siin?

1507
01:12:35,910 --> 01:12:38,110
Mida ahelloend
ilmselt võimaldab meil teha,

1508
01:12:38,110 --> 01:12:40,240
mis oli päritolu
see konkreetne lugu?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Täpselt.

1511
01:12:43,830 --> 01:12:46,220
Dünaamiline suurus ta.

1512
01:12:46,220 --> 01:12:48,040
Me võime lisada sellesse nimekirja.

1513
01:12:48,040 --> 01:12:51,430
Me isegi kahaneb nimekirja, nii et
et me ainult kasutades nii palju mälu

1514
01:12:51,430 --> 01:12:55,560
nagu me tegelikult tahame ja nii
me kunagi üle jaotada.

1515
01:12:55,560 --> 01:12:58,470
>> Nüüd lihtsalt olla tõesti tobu valiv,
seal on varjatud kulud.

1516
01:12:58,470 --> 01:13:01,980
Nii et sa ei tohiks lihtsalt lase mul veenda
teile, et see on mõjuv Miinuseks.

1517
01:13:01,980 --> 01:13:04,190
On veel üks varjatud kulusid siin.

1518
01:13:04,190 --> 01:13:06,550
Kasu, et oleks selge,
on see, et me saame dünaamikat.

1519
01:13:06,550 --> 01:13:10,359
Kui ma tahan veel üks element, ma lihtsalt
joonistada ja pani number seal.

1520
01:13:10,359 --> 01:13:12,150
Ja siis ma saan siduda see
koos pilti siin

1521
01:13:12,150 --> 01:13:14,970
samas siin jälle, kui ma olen
värvitud ennast nurka,

1522
01:13:14,970 --> 01:13:19,410
kui midagi muud juba kasutab
mälu siin, ma olen läbi õnne.

1523
01:13:19,410 --> 01:13:21,700
Olen värvitud ennast nurka.

1524
01:13:21,700 --> 01:13:24,390
>> Aga mis on peidetud
maksab see pilt?

1525
01:13:24,390 --> 01:13:27,690
See ei ole lihtsalt summa
aega, mis kulub

1526
01:13:27,690 --> 01:13:29,870
minna siit siiani,
mis on seitse sammu, siis

1527
01:13:29,870 --> 01:13:32,820
kaheksa astet, mis on rohkem kui üks.

1528
01:13:32,820 --> 01:13:34,830
Mis on veel üks varjatud kulusid?

1529
01:13:34,830 --> 01:13:35,440
Mitte lihtsalt aega.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Lisainfot
selle eesmärgi saavutamiseks vajalik pilt.

1532
01:13:49,940 --> 01:13:53,210
>> Jah, see kaart, need väikesed sissekannet
paberi, nagu ma hoida kirjeldavad neid.

1533
01:13:53,210 --> 01:13:55,650
Need arrows-- need ei ole vabad.

1534
01:13:55,650 --> 01:13:57,660
Computer-- tead
mida arvutil on.

1535
01:13:57,660 --> 01:13:58,790
See on ühtede ja nullide.

1536
01:13:58,790 --> 01:14:03,170
Kui soovite esindavad nool või
map või mitu, teil on vaja mõned mälu.

1537
01:14:03,170 --> 01:14:05,950
Nii teine ​​hind, mida
maksma ahelloend,

1538
01:14:05,950 --> 01:14:09,070
ühine infotehnoloogia
ressurss, on ka ruumi.

1539
01:14:09,070 --> 01:14:11,710
>> Ja tõepoolest nii, nii tavaliselt,
hulgast kompromissidega

1540
01:14:11,710 --> 01:14:15,580
kavandamisel tarkvaratehnika
süsteemid on aega ja space--

1541
01:14:15,580 --> 01:14:18,596
On kaks oma koostisosade, kaks
oma kõige kallima koostisosi.

1542
01:14:18,596 --> 01:14:21,220
See maksab mulle rohkem aega
sest mul on jälgida seda kaardil

1543
01:14:21,220 --> 01:14:25,730
aga see on ka maksab mulle rohkem ruumi
sest mul on hoida selle kaardi ümber.

1544
01:14:25,730 --> 01:14:28,730
Nii et lootust, kui me oleme omamoodi
arutati üle eile ja täna

1545
01:14:28,730 --> 01:14:31,720
on see, et kasu
kaalub üles kulud.

1546
01:14:31,720 --> 01:14:33,870
>> Aga seal ei ilmne lahendus siin.

1547
01:14:33,870 --> 01:14:35,870
Võib-olla on better--
a la kiire ja määrdunud,

1548
01:14:35,870 --> 01:14:38,660
nagu Kareem pakutud earlier--
visata mälu probleem.

1549
01:14:38,660 --> 01:14:42,520
Lihtsalt osta rohkem mälu, arvan vähem
kõvasti probleemi lahendamisel,

1550
01:14:42,520 --> 01:14:44,595
ja lahendada seda lihtsam viis.

1551
01:14:44,595 --> 01:14:46,720
Ja tõepoolest varem, kui
me rääkisime kompromissidega,

1552
01:14:46,720 --> 01:14:49,190
see ei olnud ruumi
arvuti ja aega.

1553
01:14:49,190 --> 01:14:51,810
See oli arendaja aega, mis
On veel üks ressurss.

1554
01:14:51,810 --> 01:14:54,829
>> Nii jälle, see on see tasakaal
püüavad otsustada, milline neist asjadest

1555
01:14:54,829 --> 01:14:55,870
kas te olete nõus kulutama?

1556
01:14:55,870 --> 01:14:57,380
Milline on kõige kallim?

1557
01:14:57,380 --> 01:15:01,040
Mis annab paremaid tulemusi?

1558
01:15:01,040 --> 01:15:01,540
Jah?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Tõepoolest.

1561
01:15:12,580 --> 01:15:15,970
Sel juhul, kui sa oled
esindavad numbrid maps--

1562
01:15:15,970 --> 01:15:18,820
nimetatakse neid paljudes keeltes
"Osuti" või "aadressid" -

1563
01:15:18,820 --> 01:15:20,390
see on topelt ruumi.

1564
01:15:20,390 --> 01:15:24,390
See ei pea olema nii halb, kui topelt, kui
kohe me lihtsalt ladustamiseks numbrid.

1565
01:15:24,390 --> 01:15:27,410
Oletame, et me talletame
Patsient dokumendikogumid hospital--

1566
01:15:27,410 --> 01:15:30,870
nii Pierson nimed, telefoninumbrid,
sotsiaalkindlustuse numbrid, arst

1567
01:15:30,870 --> 01:15:31,540
ajaloos.

1568
01:15:31,540 --> 01:15:34,160
See kast võiks olla palju,
palju suurem, mispuhul

1569
01:15:34,160 --> 01:15:38,000
tilluke pointer, aadress
Järgmise element-- see ei ole suur asi.

1570
01:15:38,000 --> 01:15:40,620
See on nii erisoodustuse
hind ei ole oluline.

1571
01:15:40,620 --> 01:15:43,210
Aga sel juhul, jah, see on kahekordistamist.

1572
01:15:43,210 --> 01:15:45,290
Hea küsimus.

1573
01:15:45,290 --> 01:15:47,900
>> Räägime korda
vähe konkreetsemalt.

1574
01:15:47,900 --> 01:15:50,380
Mis sõiduaega
otsides seda nimekirja?

1575
01:15:50,380 --> 01:15:53,640
Oletame, tahtsin otsida
läbi kõik õpilaste klassid,

1576
01:15:53,640 --> 01:15:55,980
ja seal on n klassid
Selles andmestruktuur.

1577
01:15:55,980 --> 01:15:58,830
Siingi saame laenata
sõnavara varem.

1578
01:15:58,830 --> 01:16:00,890
See on lineaarne andmestruktuur.

1579
01:16:00,890 --> 01:16:04,570
>> Big O n on, milline on vajalik saada
lõpuni käesoleva andmestruktuur,

1580
01:16:04,570 --> 01:16:08,410
whereas-- ja me ei ole näinud
See before-- massiivi annab teile

1581
01:16:08,410 --> 01:16:13,555
mida nimetatakse konstantset aega, mis tähendab,
üks samm või kaks sammu või 10 steps--

1582
01:16:13,555 --> 01:16:14,180
Ei ole oluline.

1583
01:16:14,180 --> 01:16:15,440
See on kindel arv.

1584
01:16:15,440 --> 01:16:17,440
See on midagi pistmist
suurusest massiivist.

1585
01:16:17,440 --> 01:16:20,130
Ja põhjus, et
jälle on muutmälu.

1586
01:16:20,130 --> 01:16:23,180
Arvuti saab lihtsalt kohe
hüpata ühest kohast teise,

1587
01:16:23,180 --> 01:16:27,770
sest nad on kõik ühesugused
kaugusele kõike muud.

1588
01:16:27,770 --> 01:16:29,112
Ei ole mõtlemine seotud.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Hästi.

1591
01:16:32,400 --> 01:16:39,230
Nii et kui suudan, las ma proovida
värvida kaks viimast pilti.

1592
01:16:39,230 --> 01:16:42,830
Väga levinud üks tuntud hash tabelis.

1593
01:16:42,830 --> 01:16:51,120
Nii et motiveerida Selle arutelu
las ma mõtlen, kuidas seda teha.

1594
01:16:51,120 --> 01:16:52,610
>> Niisiis, kuidas see on?

1595
01:16:52,610 --> 01:16:55,160
Oletame, et probleem
me tahame lahendada nüüd

1596
01:16:55,160 --> 01:16:58,360
rakendab oma dictionary--
nii terve hulk inglise sõnad

1597
01:16:58,360 --> 01:16:59,330
või mis iganes.

1598
01:16:59,330 --> 01:17:02,724
Ja eesmärgiks on olla võimeline vastama
küsimuste näol on see sõna?

1599
01:17:02,724 --> 01:17:04,640
Nii et sa tahad ellu
õigekirjakontrolli, lihtsalt

1600
01:17:04,640 --> 01:17:07,220
nagu füüsilise sõnastik
et saad vaadata asju üles.

1601
01:17:07,220 --> 01:17:10,490
Oletame, ma oleks seda teha koos hulga.

1602
01:17:10,490 --> 01:17:12,590
Ma ei suutnud seda teha.

1603
01:17:12,590 --> 01:17:20,756
>> Ja oletame, et sõnad on õun
ja banaan ja melon.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Ja ma ei saa mõelda puuviljad
mis algavad d, nii et me oleme lihtsalt

1606
01:17:26,465 --> 01:17:27,590
läheb on kolm puuviljad.

1607
01:17:27,590 --> 01:17:31,510
Nii et see on maatriks, ja me oleme
säilitada kogu nende sõnade

1608
01:17:31,510 --> 01:17:34,200
Selles sõnaraamatus massiiv.

1609
01:17:34,200 --> 01:17:39,350
Küsimus on siis, kuidas muidu
sa võisid seda teavet säilitada?

1610
01:17:39,350 --> 01:17:43,160
>> Noh, ma olen selline petmine siin, sest
kõik need tähed sõna

1611
01:17:43,160 --> 01:17:44,490
on tõesti individuaalne bait.

1612
01:17:44,490 --> 01:17:46,740
Nii et kui ma tõesti tahtsin olla
ting-valiv, ma tõesti

1613
01:17:46,740 --> 01:17:49,600
olla jagades selle üles võetud palju
väikesteks tükkideks mälu

1614
01:17:49,600 --> 01:17:51,289
ja me võime teha just nii.

1615
01:17:51,289 --> 01:17:53,580
Aga me ei kavatse joosta
sama probleem nagu enne.

1616
01:17:53,580 --> 01:17:56,674
Mis siis, kui nagu Merriam Webster või Oxford
teeb iga year-- nad lisavad sõnad

1617
01:17:56,674 --> 01:17:59,340
kuni dictionary-- me ei
tingimata soovite värvi ise

1618
01:17:59,340 --> 01:18:00,780
nurka array?

1619
01:18:00,780 --> 01:18:05,710
>> Nii et selle asemel, võib-olla targem lähenemine
on panna õuna oma sõlme või kast

1620
01:18:05,710 --> 01:18:11,190
kui me ütleks, banaan, ja
siis siin on meil cantaloupe.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Ja me string need asjad kokku.

1623
01:18:16,790 --> 01:18:19,980
Nii et see on massiiv, ja
see on seotud nimekirja.

1624
01:18:19,980 --> 01:18:23,300
Kui te ei ole päris näha, see lihtsalt
ütleb "massiiv" ja see ütleb "nimekirja."

1625
01:18:23,300 --> 01:18:25,780
>> Nii et meil on sama
täpse küsimusi nagu enne,

1626
01:18:25,780 --> 01:18:28,600
kusjuures meil on nüüd
dünaamikat meie ahelloendid.

1627
01:18:28,600 --> 01:18:31,090
Aga meil on suhteliselt aeglane sõnastik.

1628
01:18:31,090 --> 01:18:32,870
Oletame, ma tahan otsida sõna.

1629
01:18:32,870 --> 01:18:35,430
See võib võtta mulle suur O n
samme, sest sõna võiks

1630
01:18:35,430 --> 01:18:37,840
olla kogu tee lõpus
nimekirjas, nagu melon.

1631
01:18:37,840 --> 01:18:40,600
Ja selgub, et
programmeerimine, omamoodi

1632
01:18:40,600 --> 01:18:42,700
Püha Graal andmeid
struktuure, on midagi

1633
01:18:42,700 --> 01:18:46,620
mis annab teile pideva
aega nagu massiivi

1634
01:18:46,620 --> 01:18:50,870
kuid see annab ikkagi dünaamikat.

1635
01:18:50,870 --> 01:18:52,940
>> Nii saame olla parim nii maailmad?

1636
01:18:52,940 --> 01:18:55,570
Ja tõepoolest, seal on midagi
nimetatakse hash tabelis

1637
01:18:55,570 --> 01:18:59,320
mis võimaldab teil teha just
et ehkki umbes.

1638
01:18:59,320 --> 01:19:03,140
Hash tabelis on Kasvataja
andmestruktuur, et me

1639
01:19:03,140 --> 01:19:06,340
ei mõtle nagu
kombinatsiooni array--

1640
01:19:06,340 --> 01:19:12,390
ja ma lähen joonistada
nagu see-- ja ahelloendid

1641
01:19:12,390 --> 01:19:17,310
et ma joonistan, nagu see siin.

1642
01:19:17,310 --> 01:19:19,760
>> Ja kuidas see asi
teoste on järgmine.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Kui see now-- hash table--
on minu kolmas andmestruktuur,

1645
01:19:29,540 --> 01:19:32,590
ja ma tahan hoida
sõnu, ma ei ole

1646
01:19:32,590 --> 01:19:35,440
tahan lihtsalt salvestada kõik
sõnad seljad et seljad.

1647
01:19:35,440 --> 01:19:37,430
Ma tahan ära mõned
tükk info

1648
01:19:37,430 --> 01:19:40,330
sõnade kohta, mis võimaldab
ma saan seda, kui see on kiirem.

1649
01:19:40,330 --> 01:19:43,666
>> Nii antakse sõna õun
ja banaan ja melon,

1650
01:19:43,666 --> 01:19:45,040
Valisin teadlikult neid sõnu.

1651
01:19:45,040 --> 01:19:45,340
Miks?

1652
01:19:45,340 --> 01:19:47,631
Mis on omamoodi fundamentaalselt
erinevates umbes kolm?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Mis on ilmne?

1655
01:19:51,484 --> 01:19:52,900
Nad hakkavad erinevate tähtedega.

1656
01:19:52,900 --> 01:19:53,900
>> Nii et sa tead, mida?

1657
01:19:53,900 --> 01:19:57,120
Selle asemel, et panna kõik oma sõnad
sama kopp, nii et rääkida,

1658
01:19:57,120 --> 01:20:00,390
nagu üks suur nimekiri, miks mitte
Ma vähemalt proovida optimeerimise

1659
01:20:00,390 --> 01:20:04,180
ja teha oma nimekirjad 1/26 nii kaua.

1660
01:20:04,180 --> 01:20:07,440
Meelitav optimeerimine
Võib olla, miks mitte

1661
01:20:07,440 --> 01:20:10,650
I-- sisestamisel sõna
sellesse andmestruktuur,

1662
01:20:10,650 --> 01:20:14,300
arvesse arvuti mällu, miks
ma ei pane kõiki "a" sõnadega siin,

1663
01:20:14,300 --> 01:20:17,270
kõiki "b" sõnadega siin,
ja kõik "c" sõnadega siin?

1664
01:20:17,270 --> 01:20:24,610
Nii et see jõuab panna õuna
siin, banaan siin, melon siin

1665
01:20:24,610 --> 01:20:25,730
ja nii edasi.

1666
01:20:25,730 --> 01:20:31,700
>> Ja kui mul on veel
Sõna like-- mida on veel?

1667
01:20:31,700 --> 01:20:36,640
Apple, banaan, pirn.

1668
01:20:36,640 --> 01:20:39,370
Igaüks mõelda puu
mis algab a, b, või c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- täiuslik.

1670
01:20:40,570 --> 01:20:43,990
See läheb lõpuks siin.

1671
01:20:43,990 --> 01:20:47,530
Ja nii me tundub, et on
natuke parem lahendus,

1672
01:20:47,530 --> 01:20:50,820
sest nüüd, kui ma tahan
otsida õun, ma

1673
01:20:50,820 --> 01:20:53,200
first-- Ma ei ole lihtsalt sukelduda
minu andmete struktuuri.

1674
01:20:53,200 --> 01:20:54,850
Ma ei sukelduda minu arvuti mällu.

1675
01:20:54,850 --> 01:20:56,530
Ma esimene pilk esimene täht.

1676
01:20:56,530 --> 01:20:58,610
>> Ja see on see, mida arvuti
teadlane ütleks.

1677
01:20:58,610 --> 01:21:00,760
Sa hash oma andmete struktuuri.

1678
01:21:00,760 --> 01:21:04,100
Sa võta oma panus, mis
Sel juhul on sõna nagu õun.

1679
01:21:04,100 --> 01:21:07,150
Sa seda analüüsida, vaadeldes
esitäht sel juhul,

1680
01:21:07,150 --> 01:21:08,340
seeläbi ülessulamise ta.

1681
01:21:08,340 --> 01:21:10,950
Tärkimine on üldine termin, millega
te võtate midagi sisendina

1682
01:21:10,950 --> 01:21:12,116
ja sa toota mõned väljund.

1683
01:21:12,116 --> 01:21:15,090
Ja väljund, mis
juhul on asukoht

1684
01:21:15,090 --> 01:21:18,150
soovite otsida, esimene
asukoht, teine ​​asukoht, kolmas.

1685
01:21:18,150 --> 01:21:22,160
Nii sisend on õun,
väljund on esimene.

1686
01:21:22,160 --> 01:21:25,054
Sisend on banaan, on
väljund peaks olema teine.

1687
01:21:25,054 --> 01:21:27,220
Sisend on melon,
väljund peaks olema kolmas.

1688
01:21:27,220 --> 01:21:30,320
Sisend on mustika on
väljund peaks jälle teine.

1689
01:21:30,320 --> 01:21:34,010
Ja see on see, mis aitab teil võtta
otseteed läbi oma mälu

1690
01:21:34,010 --> 01:21:39,050
selleks, et saada sõna
või andmete tõhusamalt.

1691
01:21:39,050 --> 01:21:43,330
>> Nüüd on see kergendab meie aja potentsiaalselt
nii palju kui üks 26st,

1692
01:21:43,330 --> 01:21:45,850
sest kui sa eeldada, et sa
on nii palju "a" sõnadega nagu "z"

1693
01:21:45,850 --> 01:21:48,080
sõnad nagu "q" sõnad, mis
ei ole tõesti realistic--

1694
01:21:48,080 --> 01:21:50,830
sa lähed on viltune üle
teatud tähed alphabet--

1695
01:21:50,830 --> 01:21:53,204
kuid see oleks lisanduvate
lähenemisviisi, mis ei võimalda

1696
01:21:53,204 --> 01:21:55,930
sa saada sõnad palju kiiremini.

1697
01:21:55,930 --> 01:21:59,660
Ja tegelikult keeruline
Programmi Googles maailma

1698
01:21:59,660 --> 01:22:02,180
Facebooks on world--
nad kasutavad hash tabelis

1699
01:22:02,180 --> 01:22:03,740
jaoks palju erinevaid eesmärke.

1700
01:22:03,740 --> 01:22:06,590
Aga nad ei oleks nii naiivne, nagu
lihtsalt vaadata algustäht

1701
01:22:06,590 --> 01:22:09,700
Apple või banaan või
pirni või melon,

1702
01:22:09,700 --> 01:22:13,420
sest nagu näete neid
nimekirju oleks ikka pikk.

1703
01:22:13,420 --> 01:22:17,130
>> Ja nii see võib siiski olla omamoodi
ning linear-- nii omamoodi aeglane,

1704
01:22:17,130 --> 01:22:19,980
nagu suurte O n
et meil arutatud ka varem.

1705
01:22:19,980 --> 01:22:25,290
Mis siis väga hea hash tabel
do-- see on palju suurem massiiv.

1706
01:22:25,290 --> 01:22:28,574
Ja ta kasutab palju
kogenud segamist funktsiooni

1707
01:22:28,574 --> 01:22:30,240
nii, et see ei ole lihtsalt vaadata "a."

1708
01:22:30,240 --> 01:22:35,480
Võib-olla see vaatleb "a-p-p-l-e" ja
kuidagi teisendab need viis tähte

1709
01:22:35,480 --> 01:22:38,400
arvesse asukohta, kus
Apple tuleb hoida.

1710
01:22:38,400 --> 01:22:42,660
Me lihtsalt naiivselt kasutades täht "a"
üksi, sest see on tore ja lihtne.

1711
01:22:42,660 --> 01:22:44,600
>> Kuid hash tabelis asendatakse
Lõpuks saab mõelda

1712
01:22:44,600 --> 01:22:47,270
AS kombinatsioon
massiivi, millest igaüks

1713
01:22:47,270 --> 01:22:51,700
on seotud nimekirja, et ideaalis
peaks olema nii lühike kui võimalik.

1714
01:22:51,700 --> 01:22:54,364
Ja see ei ole ilmne lahendus.

1715
01:22:54,364 --> 01:22:57,280
Tegelikult palju täpsustamisel
et läheb all kapuuts, kui

1716
01:22:57,280 --> 01:22:59,654
rakendatakse selliseid
kogenud andmestruktuurid

1717
01:22:59,654 --> 01:23:01,640
on see, mis on õige
pikkus array?

1718
01:23:01,640 --> 01:23:03,250
Mis on õige hash funktsiooni?

1719
01:23:03,250 --> 01:23:04,830
Kuidas sa asju hoida mälu?

1720
01:23:04,830 --> 01:23:07,249
>> Aga aru, kui kiiresti
selline arutelu

1721
01:23:07,249 --> 01:23:10,540
eskaleerunud, kas nii kaugele, et see on selline
üle ühe pea sel hetkel, mis

1722
01:23:10,540 --> 01:23:11,360
on hea.

1723
01:23:11,360 --> 01:23:18,820
Aga me alustasime, mäletate, tõeliselt
midagi madala ja elektrooniline.

1724
01:23:18,820 --> 01:23:20,819
Ja nii see jälle on see
teema võtmiseks,

1725
01:23:20,819 --> 01:23:23,610
kus kord, kui hakkate kasutama eest
antud, OK, mul see-- seal

1726
01:23:23,610 --> 01:23:26,680
füüsiline mälu, Sain aru, iga
füüsilist asukohta on aadress,

1727
01:23:26,680 --> 01:23:29,910
OK, ma sain selle, ma ei esinda
need aadressid arrows--

1728
01:23:29,910 --> 01:23:34,650
saab väga kiiresti hakkavad olema
keerukamaid vestluste

1729
01:23:34,650 --> 01:23:38,360
lõpuks tundub, et see võimaldab meil
lahendada probleeme, nagu otsides

1730
01:23:38,360 --> 01:23:41,620
ja sorteerimine tõhusamalt.

1731
01:23:41,620 --> 01:23:44,190
Ja kindel, too--
sest ma arvan, et see

1732
01:23:44,190 --> 01:23:48,700
on sügavaim oleme läinud mõned
Nende CS teemasid proper-- me oleme

1733
01:23:48,700 --> 01:23:51,880
teha päevas ja pool selles
meelde, mida sa võib tavaliselt teha üle

1734
01:23:51,880 --> 01:23:55,520
käigus kaheksa nädala jooksul semestri.

1735
01:23:55,520 --> 01:23:59,670
>> Kõik küsimused on need?

1736
01:23:59,670 --> 01:24:01,100
Ei?

1737
01:24:01,100 --> 01:24:01,940
Hästi.

1738
01:24:01,940 --> 01:24:05,610
Noh, miks me ei peatamiseks on olemas,
alustada lõunasööki minutit varem,

1739
01:24:05,610 --> 01:24:07,052
jätkata vaid umbes tund aega?

1740
01:24:07,052 --> 01:24:08,760
Ja ma jõlkuma
natuke küsimusi.

1741
01:24:08,760 --> 01:24:11,343
Siis ma lähen minema
võtta paar kõned, kui see on OK.

1742
01:24:11,343 --> 01:24:15,000
Ma lülitage muusikat vahepeal
kuid lõunasöök peaks olema ümber nurga.

1743
01:24:15,000 --> 01:24:17,862