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

2
00:00:00,030 --> 00:00:00,460
>> DAVID Malan: Bone.

3
00:00:00,460 --> 00:00:01,094
Ni estas reen.

4
00:00:01,094 --> 00:00:04,260
Do en ĉi tiu segmento de programado kio
Mi pensis ke ni faras estas miksaĵo de aĵoj.

5
00:00:04,260 --> 00:00:06,340
Unu, do iomete
de io manojn-sur,

6
00:00:06,340 --> 00:00:08,690
kvankam uzante pli ludema
programado environment--

7
00:00:08,690 --> 00:00:11,620
Kiu estas demonstrativo de
precize la specoj de ideoj

8
00:00:11,620 --> 00:00:14,220
ni parolis pri,
sed iom pli formale.

9
00:00:14,220 --> 00:00:18,200
Du, rigardu kelkajn el
la pli teknika manieroj

10
00:00:18,200 --> 00:00:21,520
ke programisto devus reale solvi
problemoj kiel la serĉado problemo

11
00:00:21,520 --> 00:00:24,530
ke ni rigardis antaŭe kaj
ankaŭ pli funde

12
00:00:24,530 --> 00:00:26,020
Interesa problemo de ordigado.

13
00:00:26,020 --> 00:00:28,840
>> Ni nur supozis de la akiri iri
ke tiu telefono libro ordigataj

14
00:00:28,840 --> 00:00:31,980
sed tio sole estas fakte speco de
peza problemo kun multaj malsamaj manieroj

15
00:00:31,980 --> 00:00:32,479
solvi ĝin.

16
00:00:32,479 --> 00:00:34,366
Do ni uzos tiujn kiel
klaso de problemoj

17
00:00:34,366 --> 00:00:36,740
reprezentanto de aĵoj kiuj
povus esti solvita en ĝenerala.

18
00:00:36,740 --> 00:00:38,980
Kaj poste ni parolos
pri detale kion

19
00:00:38,980 --> 00:00:42,360
nomas datumoj structures--
amatoro manieroj kiel ligitaj listoj

20
00:00:42,360 --> 00:00:46,290
kaj hash tabloj kaj arboj
programisto estus reale

21
00:00:46,290 --> 00:00:48,890
uzi kaj ĝenerale uzi
sur skribtabulo pentri

22
00:00:48,890 --> 00:00:51,840
bildon de kion li aŭ ŝi
antaŭvidas por efektivigado

23
00:00:51,840 --> 00:00:52,980
iu peco de programaro.

24
00:00:52,980 --> 00:00:55,130
>> Do ni faru la manojn-sur parto unua.

25
00:00:55,130 --> 00:01:00,090
Tiel simple akiri viajn manojn malpuraj kun
medio nomita scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Tio estas ilo kiu ni uzas
en nia studenta klaso.

27
00:01:02,636 --> 00:01:04,510
Kvankam ĝi estas desegnita
por aĝoj 12 kaj supren,

28
00:01:04,510 --> 00:01:07,570
Ni uzu ĝin por la supren
parto de tiu sufiĉe

29
00:01:07,570 --> 00:01:10,020
ĉar ĝi estas bela, amuza
grafika maniero de lernado

30
00:01:10,020 --> 00:01:12,160
iom ion pri programado.

31
00:01:12,160 --> 00:01:17,600
Tiel gvidi al tiu retadreso, kie vi
devus vidi tiun tute tiel,

32
00:01:17,600 --> 00:01:23,330
kaj iri antaŭen kaj klaku
Aliĝi Scratch ĉe supra dekstra

33
00:01:23,330 --> 00:01:28,300
kaj elekti uzantnomon kaj
Pasvorto kaj finfine akiri mem

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

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

36
00:01:32,165 --> 00:01:34,665
Mi pensis ke mi uzas tion kiel
ŝanco unue montri tion.

37
00:01:34,665 --> 00:01:39,120
Demando venis dum la paŭzo
pri kio kodo reale aspektas.

38
00:01:39,120 --> 00:01:41,315
Kaj ni parolis
dum la paŭzo pri C,

39
00:01:41,315 --> 00:01:45,060
en particular-- precipe
malalta nivelo en pli malnova lingvo.

40
00:01:45,060 --> 00:01:47,750
Kaj mi ĵus faris rapidan
Google serĉo trovi C kodo

41
00:01:47,750 --> 00:01:51,574
por duuma serĉo, la algoritmo ke ni
uzata por serĉi tiu telefono libro antaŭe.

42
00:01:51,574 --> 00:01:54,240
Tiu aparta ekzemplo, kompreneble,
ne serĉu telefono libro.

43
00:01:54,240 --> 00:01:57,840
Ĝi nur serĉas tuta fasko de
nombroj en la komputilo la memoro.

44
00:01:57,840 --> 00:02:01,000
Sed se vi ŝatus nur akiri vidan
senco de kio fakta programado

45
00:02:01,000 --> 00:02:05,370
lingvo similas, ĝi aspektas
iom io tiamaniere.

46
00:02:05,370 --> 00:02:09,759
Do ĝi estas ĉirkaŭ 20-plus,
30 aŭ tiel linioj de kodo,

47
00:02:09,759 --> 00:02:12,640
sed la konversacio ni
estis havanta pli paŭzo

48
00:02:12,640 --> 00:02:16,000
estis pri kiel tio fakte
iĝas transformis en nuloj kaj

49
00:02:16,000 --> 00:02:19,200
kaj se vi ne povas simple restarigu ke
procesi kaj pasi de nuloj kaj

50
00:02:19,200 --> 00:02:20,210
malantaŭeniri al kodo.

51
00:02:20,210 --> 00:02:22,620
>> Bedaŭrinde, la procezo
Estas tiom transforma

52
00:02:22,620 --> 00:02:24,890
ke estas multe pli facile dirite ol farite.

53
00:02:24,890 --> 00:02:29,400
Mi iris antaŭen kaj reale turnis
ke programo, Duuma Search,

54
00:02:29,400 --> 00:02:32,700
en nuloj kaj pere de
programo nomita La compilador mi

55
00:02:32,700 --> 00:02:34,400
hazarde havas tie rajton sur mia Mac.

56
00:02:34,400 --> 00:02:37,850
Kaj se vi rigardas la ekranon
tie, enfokusigante specife

57
00:02:37,850 --> 00:02:43,520
sur tiuj meza ses kolumnoj nur,
vi vidos nur nuloj kaj aĵoj.

58
00:02:43,520 --> 00:02:48,290
Kaj tiuj estas la nuloj kaj ke
formi ĝuste tiu serĉado programo.

59
00:02:48,290 --> 00:02:53,720
>> Kaj tiel ĉiu eron de kvin bitojn,
ĉiu bajto de nuloj kaj tie,

60
00:02:53,720 --> 00:02:57,310
reprezenti iun instrukcion
tipe ene de komputilo.

61
00:02:57,310 --> 00:03:00,730
Kaj fakte, se vi aŭdis la
marketing slogano "Intel ene" - kiuj,

62
00:03:00,730 --> 00:03:04,610
kompreneble, nur signifas vin havas
Intel CPU aŭ cerbo ene la komputilo.

63
00:03:04,610 --> 00:03:08,000
Kaj kion tio signifas esti CPU estas
ke vi havas aron de instrukcioj,

64
00:03:08,000 --> 00:03:08,840
por tiel diri.

65
00:03:08,840 --> 00:03:11,620
>> Ĉiu CPU en la mondo, multaj el
ili faris por Intel tiuj tagoj,

66
00:03:11,620 --> 00:03:13,690
komprenas finia
numeron de instrukcioj.

67
00:03:13,690 --> 00:03:18,690
Kaj tiuj instrukcioj estas tiel malalta nivelo
kiel aldoni tiujn du nombroj kune,

68
00:03:18,690 --> 00:03:22,560
multipliki tiuj du nombroj kune,
movi tiun pecon de datumoj de ĉi tie

69
00:03:22,560 --> 00:03:27,340
por tie en memoro, krom tiu
informojn de tie al tie en memoro,

70
00:03:27,340 --> 00:03:32,200
kaj tiel forth-- tiel tre, tre
malalta nivelo, preskaŭ elektronikajn detalojn.

71
00:03:32,200 --> 00:03:34,780
Sed kun tiuj, matematika
operacioj kuplita

72
00:03:34,780 --> 00:03:37,410
kun kion ni diskutis pli frua,
la reprezento de datumoj

73
00:03:37,410 --> 00:03:40,450
kiel nuloj kaj, povas
vi konstruas ĉion

74
00:03:40,450 --> 00:03:44,180
ke komputilo povas fari hodiaŭ, ĉu
ĝi estas teksta, grafika, muzika,

75
00:03:44,180 --> 00:03:45,580
aŭ alie.

76
00:03:45,580 --> 00:03:49,450
>> Do tiu estas tre facila akiri
perdita en la maleza de rapide.

77
00:03:49,450 --> 00:03:52,150
Kaj ekzistas multe de
sintaksaj defioj

78
00:03:52,150 --> 00:03:56,630
per kiu se vi faras la plej simpla,
stultan de tajperarojn nulo programo

79
00:03:56,630 --> 00:03:57,860
laboros ajn.

80
00:03:57,860 --> 00:04:00,366
Kaj tiel anstataŭ uzanta
lingvo kiel C ĉimatene,

81
00:04:00,366 --> 00:04:02,240
Mi pensis ke estus
pli amuze vere fari

82
00:04:02,240 --> 00:04:04,840
ion pli vida, kiu
dum desegnita por infanoj

83
00:04:04,840 --> 00:04:08,079
estas efektive perfekta manifestado
de fakta programado

84
00:04:08,079 --> 00:04:10,370
language-- nur okazas al
uzi bildojn anstataŭ teksto

85
00:04:10,370 --> 00:04:11,710
reprezenti tiujn ideojn.

86
00:04:11,710 --> 00:04:15,470
>> Do iam vi ja havas
konton en scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
klaku Krei butono
ĉe supro lasita de la paĝaro.

88
00:04:21,070 --> 00:04:24,620
Kaj vi devus vidi medion kiel
unu mi volis vidi sur mia ekrano

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

90
00:04:26,310 --> 00:04:29,350
Kaj ni elspezas nur iom
iom da tempo ludanta tie.

91
00:04:29,350 --> 00:04:34,080
Ni vidu se ni ne povas ĉiuj solvi iun
problemoj kune en la sekvanta maniero.

92
00:04:34,080 --> 00:04:39,420
>> Do kion vi vidos ene de tiu
environment-- kaj reale simple lasu

93
00:04:39,420 --> 00:04:40,050
mi paŭzi.

94
00:04:40,050 --> 00:04:42,680
Estas iu ne tie?

95
00:04:42,680 --> 00:04:45,070
Ne ĉi tie?

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

97
00:04:45,800 --> 00:04:49,030
Do mi atentigas kelkaj
karakterizaĵoj de ĉi tiu medio.

98
00:04:49,030 --> 00:04:55,024
>> Tiel supre maldekstre de la ekrano, ni
havas Scratch la scenejo, tiel diri.

99
00:04:55,024 --> 00:04:57,440
Nulo estas ne nur la nomo
de tiu programlingvo;

100
00:04:57,440 --> 00:05:00,356
ĝi estas ankaŭ la nomo de la kato kiu
vi vidos defaŭlte ekzistas en oranĝo.

101
00:05:00,356 --> 00:05:02,160
Li estas sur la scenejo, tiel
multe kiel mi priskribis

102
00:05:02,160 --> 00:05:05,770
la testudo frue kiel estante en
rektangula blanka tabulo medio.

103
00:05:05,770 --> 00:05:09,800
Tiu kato mondo estas limigita tute
por ke rektangulo ĝis pinto.

104
00:05:09,800 --> 00:05:12,210
>> Dume, sur la dekstra
flanko tie, estas

105
00:05:12,210 --> 00:05:15,610
nur skriptoj areo,
malplenan skribtabulo se vi volas.

106
00:05:15,610 --> 00:05:18,590
Tie estas kie ni tuj skribos
niaj programoj en nur momento.

107
00:05:18,590 --> 00:05:22,935
Kaj la konstruelementoj ke ni faros
uzas por skribi ĉi program-- la enigmo

108
00:05:22,935 --> 00:05:25,310
pecoj, se vi will-- estas
tiuj ĉi tie en la mezo,

109
00:05:25,310 --> 00:05:27,500
kaj ili estas kategoriigitaj
de funcionalidad.

110
00:05:27,500 --> 00:05:31,000
Do, ekzemple, mi tuj iros antaŭen
kaj pruvi almenaŭ unu el tiuj.

111
00:05:31,000 --> 00:05:33,690
Mi tuj iros antaŭen kaj klaku
la Kontrolo kategorio supren supro.

112
00:05:33,690 --> 00:05:35,720
>> Do jen estas la kategoriojn ĝis supro.

113
00:05:35,720 --> 00:05:39,410
Mi tuj klaki la Kontrolo kategorio.

114
00:05:39,410 --> 00:05:44,020
Prefere, mi tuj klaku Eventoj
kategorio, la unua unu ĝis supro.

115
00:05:44,020 --> 00:05:47,790
Kaj se vi ŝatus sekvi kune eĉ
kiel ni faras tion, vi tute bonvena.

116
00:05:47,790 --> 00:05:52,180
Mi tuj alklaki kaj treni tiun
unua, "kiam verda flago clicked."

117
00:05:52,180 --> 00:05:58,410
Kaj tiam mi tuj faligis ĝin ĝuste
malglate ĉe la supro de mia malplenan ardezoj.

118
00:05:58,410 --> 00:06:01,450
>> Kaj kio estas agrable pri Scratch
estas ke tiu enigmo pecon, kiam

119
00:06:01,450 --> 00:06:04,560
interkroĉitaj kun aliaj enigmo
pecoj, tuj faros laŭvorte

120
00:06:04,560 --> 00:06:06,460
kio tiuj puzlo pecoj diru fari.

121
00:06:06,460 --> 00:06:09,710
Do, ekzemple, Scratch pravas
Nun en la mezo de sia mondo.

122
00:06:09,710 --> 00:06:14,660
Mi tuj iros antaŭen kaj elekti
Nun, ni diru, la Motion kategorio,

123
00:06:14,660 --> 00:06:18,000
Se vi ŝatus fari la
same-- Moviĝo kategorio.

124
00:06:18,000 --> 00:06:20,430
Kaj nun rimarkas mi havas tutajn
faskon da puzlo pecoj tie

125
00:06:20,430 --> 00:06:23,370
ke, denove, ia fari kion ili diras.

126
00:06:23,370 --> 00:06:28,110
Kaj mi tuj iros antaŭen kaj treni kaj
faligi la movadon bloko rajton super tie.

127
00:06:28,110 --> 00:06:31,860
>> Kaj rimarki ke tuj kiam vi akiras
proksime al la fundo de la "verda flago

128
00:06:31,860 --> 00:06:34,580
klakis "butonon, avizo
kiel blanka linio aperas,

129
00:06:34,580 --> 00:06:36,950
kvazaŭ ĝi estas preskaŭ
magneta, ĝi volas iri tien.

130
00:06:36,950 --> 00:06:43,070
Nur lasu iri, kaj ĝi alkroĉiĝos
kune kaj la formoj kongruas.

131
00:06:43,070 --> 00:06:46,620
Kaj nun vi povas eble preskaŭ
diveni kie ni iras kun tio.

132
00:06:46,620 --> 00:06:51,570
>> Se vi rigardas la Scratch stadio
tien kaj rigardu al la supro,

133
00:06:51,570 --> 00:06:55,142
vi vidos ruĝan lumon, la
haltigi signo, kaj verda flago.

134
00:06:55,142 --> 00:06:57,100
Kaj mi tuj iros antaŭen
kaj rigardi mian screen--

135
00:06:57,100 --> 00:06:58,460
por nur momento, se vi povus.

136
00:06:58,460 --> 00:07:01,960
Mi tuj klaku
verda flago nun,

137
00:07:01,960 --> 00:07:07,850
kaj Li incitis kion ŝajnu esti 10 paŝoj
aŭ 10 rastrumeroj, 10 punktoj, sur la ekrano.

138
00:07:07,850 --> 00:07:13,390
>> Kaj tial ne ke ekscita,
sed mi proponas

139
00:07:13,390 --> 00:07:17,440
sen eĉ instrui tion, nur
uzante la propran vian propran intuition-- let

140
00:07:17,440 --> 00:07:22,560
mi proponas ke vi elkompreni kiel
fari Scratch promeno tuj la scenejo.

141
00:07:22,560 --> 00:07:28,700
Jam lin faras vojon por la dekstra flanko de
la ekrano, la tutan vojon al la dekstra.

142
00:07:28,700 --> 00:07:32,200
Mi donos al vi momenton
aŭ tiel lukti kun tiu.

143
00:07:32,200 --> 00:07:37,681
Vi eble volas preni rigardon
ĉe aliaj kategorioj de blokoj.

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

145
00:07:38,180 --> 00:07:41,290
Do nur por recap, kiam ni havas
la verda flago klakis tie

146
00:07:41,290 --> 00:07:44,850
kaj movas 10 paŝoj estas la
nur instrukcion, ĉiufoje mi

147
00:07:44,850 --> 00:07:46,720
klaku la verdan flagon, kio okazas?

148
00:07:46,720 --> 00:07:50,070
Nu, jen kurante mia programo.

149
00:07:50,070 --> 00:07:52,450
Do mi povus fari tion
eble 10 fojojn permane,

150
00:07:52,450 --> 00:07:55,130
sed ĉi sentas iom
iom hackish, por tiel diri,

151
00:07:55,130 --> 00:07:57,480
per kiu mi ne vere
solvi la problemon.

152
00:07:57,480 --> 00:08:00,530
Mi nur provas denove kaj
denove kaj denove kaj denove

153
00:08:00,530 --> 00:08:03,180
ĝis mi ian hazarde
atingi la directiva

154
00:08:03,180 --> 00:08:05,560
ke mi ekiris por atingi pli frue.

155
00:08:05,560 --> 00:08:08,200
>> Sed ni scias el niaj
_pseudocode_ frue ke ekzistas

156
00:08:08,200 --> 00:08:11,870
tiu nocio en programado de looping,
fari ion denove kaj denove.

157
00:08:11,870 --> 00:08:14,888
Kaj ankaux mi vidis, ke aro da vi
atingita por kio enigmo peco?

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

159
00:08:17,870 --> 00:08:18,730
Ripetu ĝis.

160
00:08:18,730 --> 00:08:21,400
Do ni povus fari ion
kiel ripeti ĝis.

161
00:08:21,400 --> 00:08:23,760
Kaj kion vi ripeti ĝis ĝuste?

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

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

164
00:08:28,540 --> 00:08:31,974
Kaj mi iros kun kiu estas
iom pli simpla por nur momento.

165
00:08:31,974 --> 00:08:33,140
Lasu min antaŭeniri kaj fari tion.

166
00:08:33,140 --> 00:08:35,559
Rimarku, ke kiel vi povas havi
malkovritaj sub kontrolo,

167
00:08:35,559 --> 00:08:38,409
ekzistas tiu ripeto bloko, kiu
ne aspektas kiel ĝi estas tiel granda.

168
00:08:38,409 --> 00:08:41,039
Tie ne estas multe ĉambron
inter tiuj du flavaj linioj.

169
00:08:41,039 --> 00:08:43,539
Sed kiel kelkaj el vi eble havas
rimarkis, se vi treni kaj guton,

170
00:08:43,539 --> 00:08:45,150
rimarki kiel ĝi kreskas por plenigi la formo.

171
00:08:45,150 --> 00:08:46,274
>> Kaj vi povas eĉ Cram pli.

172
00:08:46,274 --> 00:08:48,670
Ĝi gardos kreskas se
vi treni kaj ŝvebi super ĝi.

173
00:08:48,670 --> 00:08:51,110
Kaj mi ne scias kio estas
bona ĉi tie, do ni

174
00:08:51,110 --> 00:08:54,760
mi almenaŭ ripeti kvinfoje, por
Ekzemple, kaj poste reiri al la stadio

175
00:08:54,760 --> 00:08:56,720
kaj klaku la verdan flagon.

176
00:08:56,720 --> 00:08:59,110
Kaj nun rimarkas ĝi ne estas tre tie.

177
00:08:59,110 --> 00:09:02,400
>> Kelkaj el vi proponis, kiel
Victoria simple, ripeti 10 fojoj.

178
00:09:02,400 --> 00:09:05,140
Kaj ke ĝenerale faras
akiri lin la tutan vojon,

179
00:09:05,140 --> 00:09:10,510
sed ĉu ne estos pli fortika
maniero ol arbitre elŝeligi

180
00:09:10,510 --> 00:09:12,640
kiom da movojn fari?

181
00:09:12,640 --> 00:09:17,680
Kio povus esti pli bona bloko
ol ripeto 10 fojojn esti?

182
00:09:17,680 --> 00:09:20,380
>> Jes, do kial ne fari ion por ĉiam?

183
00:09:20,380 --> 00:09:24,390
Kaj nun lasu min movi tiun enigmo peco
interne tien kaj forigi ĉi tiun.

184
00:09:24,390 --> 00:09:28,300
Nun rimarkas negrave kie Scratch
komenciĝas, li iras al la rando.

185
00:09:28,300 --> 00:09:30,700
Kaj dankeme MIT,
kiu faras Scratch, ĵus

186
00:09:30,700 --> 00:09:33,190
certigas ke li neniam
malaperas tute.

187
00:09:33,190 --> 00:09:35,360
Vi povas ĉiam kapti sian voston.

188
00:09:35,360 --> 00:09:37,680
>> Kaj ĝuste intuicie,
kial li tenas movanta?

189
00:09:37,680 --> 00:09:38,892
Kio okazas ĉi tie?

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

191
00:09:41,440 --> 00:09:43,824
Li ŝajnas esti detenita, sed
tiam se mi reprenos kaj trenu

192
00:09:43,824 --> 00:09:45,240
Li tenas volante iri tien.

193
00:09:45,240 --> 00:09:46,123
Kial estas tio?

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

195
00:09:51,610 --> 00:09:54,360
Vere, komputilo estas laŭvorte
faros kion vi diros ĝin fari.

196
00:09:54,360 --> 00:09:58,380
Do se vi diris ĝin antaŭe fari la
sekva ĉiam, movi 10 paŝoj,

197
00:09:58,380 --> 00:10:01,860
ĝi tuj plu iri kaj iri
ĝis mi batis la ruĝa halto signo

198
00:10:01,860 --> 00:10:04,620
kaj ĉesigi la programon tute.

199
00:10:04,620 --> 00:10:06,610
>> Do eĉ se vi ne
fari tion, kiel mi povus tion

200
00:10:06,610 --> 00:10:09,510
fari Scratch movon rapida
trans la ekrano?

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

202
00:10:12,060 --> 00:10:13,280
Pli paŝojn, dekstra?

203
00:10:13,280 --> 00:10:15,710
Do anstataŭ fari 10
samtempe kial ne ni

204
00:10:15,710 --> 00:10:20,100
antaŭeniri kaj ŝanĝi ĝin to--
Kion vi propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Do nun mi tuj klaku la verdan
flago, kaj efektive, li iras vere rapida.

206
00:10:24,410 --> 00:10:27,180
>> Kaj tio, kompreneble, estas nur
demonstracio de kuraĝigo.

207
00:10:27,180 --> 00:10:28,060
Kio estas kuraĝigo?

208
00:10:28,060 --> 00:10:33,090
Ĝi simple montranta vin la homa a
tuta aro da ankoraŭ bildoj vere,

209
00:10:33,090 --> 00:10:34,160
vere, vere rapida.

210
00:10:34,160 --> 00:10:36,500
Kaj do se ni nur rakontanta
lin moviĝi pli paŝojn,

211
00:10:36,500 --> 00:10:39,750
ni nur havi la efikon estu
ŝanĝo kie li estas sur la ekrano

212
00:10:39,750 --> 00:10:42,900
des pli rapide por unuo de tempo.

213
00:10:42,900 --> 00:10:46,454
>> La sekva defio kiun mi proponis
estis havi lin rebotar ekstere la rando.

214
00:10:46,454 --> 00:10:49,120
Kaj sen scii kion enigmo
pecoj exist-- ĉar ĝi estas bone

215
00:10:49,120 --> 00:10:53,030
Se vi ne alvenas al la
scenejo de la challenge-- kio

216
00:10:53,030 --> 00:10:54,280
ĉu vi volas fari intuicie?

217
00:10:54,280 --> 00:10:58,030
Kiel ni havi lin rebotar dorso kaj
antaŭen, inter la maldekstra kaj dekstra?

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

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

220
00:11:03,810 --> 00:11:05,680
Do ni bezonas ian
de kondiĉo, kaj ni

221
00:11:05,680 --> 00:11:09,710
ŝajnas havi Conditionals, tiel
paroli, sub la kontrolo kategorio.

222
00:11:09,710 --> 00:11:14,110
Kiu el tiuj blokoj
ni probable volas?

223
00:11:14,110 --> 00:11:15,200
Yeah, eble "se, tiam."

224
00:11:15,200 --> 00:11:18,780
Do rimarki, ke inter la flavaj blokoj
ni havas ĉi tie, estas tiu "se"

225
00:11:18,780 --> 00:11:23,920
aŭ tiu "se, alie" bloko kiu volas
nin permesas fari decidon fari tiun

226
00:11:23,920 --> 00:11:25,000
aŭ fari tion.

227
00:11:25,000 --> 00:11:27,380
Kaj vi povas eĉ nesto ilin
fari plurajn aferojn.

228
00:11:27,380 --> 00:11:34,910
Aŭ se vi ne iris tien ankoraŭ,
antaŭeniri al la sensado kategorio

229
00:11:34,910 --> 00:11:39,612
kaj- ni vidu se ĝi estas tie.

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

231
00:11:43,050 --> 00:11:52,050
>> Do kio bloko povas esti utila tie
detekti se li estas de la scenejo?

232
00:11:52,050 --> 00:11:56,740
Yeah, rimarki ke iuj de ĉi tiuj blokoj
povas parametrigita, por tiel diri.

233
00:11:56,740 --> 00:12:00,706
Ili povas esti ia personecigita, ne
kontraste HTML hieraŭ kun atributoj,

234
00:12:00,706 --> 00:12:03,330
kie tiuj atributoj ia
agordi la konduton de etikedo.

235
00:12:03,330 --> 00:12:08,880
Simile tie, mi povas ekpreni ĉi kortuŝa
bloko kaj ŝanĝo kaj demandi la demandon,

236
00:12:08,880 --> 00:12:11,500
vi tuŝi la muso
puntero kiel la kursoro

237
00:12:11,500 --> 00:12:13,250
aŭ vi tuŝi la randon?

238
00:12:13,250 --> 00:12:15,210
>> Do lasu min iri en kaj fari tion.

239
00:12:15,210 --> 00:12:18,130
Mi tuj malzomi dum momento.

240
00:12:18,130 --> 00:12:21,320
Lasu min ekpreni tiun enigmo peco
tie, ĉi enigmo peco ĉi,

241
00:12:21,320 --> 00:12:24,570
kaj mi tuj senorda miksaĵo
ilin por nur momento.

242
00:12:24,570 --> 00:12:27,620
Mi tuj kopii ĉi,
ŝanĝi ĉi tion al kortuŝa rando,

243
00:12:27,620 --> 00:12:38,590
kaj mi tuj moviĝo fari tion.

244
00:12:38,590 --> 00:12:40,490
Do jen kelkaj ingrediencoj.

245
00:12:40,490 --> 00:12:42,570
Mi pensas mi havas ĉion kion mi deziras.

246
00:12:42,570 --> 00:12:47,710
>> Ĉu iu volas proponi kiel mi
povas konekti tiuj eble pinti al fundo

247
00:12:47,710 --> 00:12:52,020
Por solvi la problemon de devi
Nulo movo dekstre maldekstren al rajton

248
00:12:52,020 --> 00:12:57,020
maldekstre dekstren maldekstren, ĉiu
tempo simple rebotar ekstere la muro?

249
00:12:57,020 --> 00:12:58,050
Kion mi volas fari?

250
00:12:58,050 --> 00:13:01,097
Kiu bloko devus ligoj al la
"Kiam verda flago clicked unua"?

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

252
00:13:04,060 --> 00:13:06,200
>> Bone, do ni komencu kun la "ĉiam."

253
00:13:06,200 --> 00:13:07,170
Kio iras ene poste?

254
00:13:07,170 --> 00:13:10,290
Iu alia.

255
00:13:10,290 --> 00:13:11,850
OK, movi paŝojn.

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

257
00:13:12,350 --> 00:13:14,470
Tiam kio?

258
00:13:14,470 --> 00:13:15,120
Tial la se.

259
00:13:15,120 --> 00:13:17,720
Kaj rimarki, kvankam ĝi aspektas
krampitaj kune firme,

260
00:13:17,720 --> 00:13:19,500
ĝi nur kreskos plenigi.

261
00:13:19,500 --> 00:13:21,500
Ĝi simple salti en kie mi volas.

262
00:13:21,500 --> 00:13:25,920
>> Kaj kion mi metu inter
la se kaj do?

263
00:13:25,920 --> 00:13:27,180
Probable "se tuŝi randon."

264
00:13:27,180 --> 00:13:31,800
Kaj avizo, denove, ĝi estas tro granda
por ĝi, sed ĝi kreskos plenigi.

265
00:13:31,800 --> 00:13:35,002
Kaj tiam turni 15 gradoj?

266
00:13:35,002 --> 00:13:35,710
Kiom da gradoj?

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

268
00:13:38,800 --> 00:13:41,196
Jes, do 180 estos ŝpini
Min tuta vojo ĉirkaŭ.

269
00:13:41,196 --> 00:13:42,570
Do ni vidu se mi akiris tiun rajton.

270
00:13:42,570 --> 00:13:43,930
Lasu min malzomi.

271
00:13:43,930 --> 00:13:45,130
>> Lasu min treni Scratch supren.

272
00:13:45,130 --> 00:13:50,030
Do li estas iom distordita
nun, sed tio estas bone.

273
00:13:50,030 --> 00:13:52,231
Kiel mi retrovu lin facile?

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

275
00:13:59,879 --> 00:14:01,045
Mi tuj cheat iomete.

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

277
00:14:04,074 --> 00:14:05,990
Do mi aldonas alian
bloko, nur por esti klara.

278
00:14:05,990 --> 00:14:08,424
Mi volas lin atentigi 90 gradoj
dekstren defaŭlte,

279
00:14:08,424 --> 00:14:10,840
do mi simple tuj diros lin
fari tion programmatically.

280
00:14:10,840 --> 00:14:11,632
Kaj tie ni iru.

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

282
00:14:14,740 --> 00:14:15,740
Ŝajne ni faris.

283
00:14:15,740 --> 00:14:19,980
Ĝi estas iom bizara, ĉar
li promenis renversos.

284
00:14:19,980 --> 00:14:21,250
Ni nomas tion cimon.

285
00:14:21,250 --> 00:14:22,120
Ke estas eraro.

286
00:14:22,120 --> 00:14:27,320
Cimon estas eraro en programo, a
logika eraro ke mi, la homo, farita.

287
00:14:27,320 --> 00:14:28,985
Kial li iras renverse?

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

289
00:14:33,560 --> 00:14:35,250
Ĉu MIT ŝraŭbo supren aŭ ĉu mi?

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

291
00:14:38,840 --> 00:14:42,550
>> Yeah, Mi volas diri, ne MIT
kulpo. Ili donis al mi enigmo peco

292
00:14:42,550 --> 00:14:44,970
kiu diras turni iun numeron de gradoj.

293
00:14:44,970 --> 00:14:47,672
Kaj ĉe Viktoria sugesto,
Mi turnis 180 gradojn,

294
00:14:47,672 --> 00:14:48,880
kiu estas dekstre intuicio.

295
00:14:48,880 --> 00:14:53,700
Sed turnante 180 gradojn laŭvorte
signifas turnante 180 gradojn,

296
00:14:53,700 --> 00:14:55,860
kaj tio ne vere
kion mi volas, ŝajne.

297
00:14:55,860 --> 00:14:58,026
Ĉar almenaŭ li estas en
tiu dudimensia mondo,

298
00:14:58,026 --> 00:15:00,740
tiel decida estas vere iranta
por klaki lin renversos.

299
00:15:00,740 --> 00:15:04,030
>> Mi verŝajne volas uzi kion bloko
anstataŭe, bazita sur kion vi vidas tie?

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

301
00:15:11,890 --> 00:15:14,790
Kiel povus ni riparos tion?

302
00:15:14,790 --> 00:15:18,380
Jes, do ni povus atentigi
en la kontraŭa direkto.

303
00:15:18,380 --> 00:15:22,300
Kaj fakte eĉ tio
ne tuj estos sufiĉa,

304
00:15:22,300 --> 00:15:26,410
ĉar ni povas nur malfacile kodo
al markante maldekstra aŭ dekstra.

305
00:15:26,410 --> 00:15:27,920
>> Vi scias kion ni povus fari?

306
00:15:27,920 --> 00:15:30,160
Ĝi aspektas kiel ni havas
oportuneco bloko tie.

307
00:15:30,160 --> 00:15:32,987
Se mi zomi, vidu
iu ni ŝatas tie?

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

309
00:15:36,120 --> 00:15:40,020
Do ĝi aspektas kiel MIT havas
abstraktado konstruita tie.

310
00:15:40,020 --> 00:15:45,440
Tiu bloko ŝajnas esti ekvivalenta
al kiu aliaj blokoj, pluralo?

311
00:15:45,440 --> 00:15:49,510
>> Ĉi tiu bloko ŝajnas esti ekvivalenta
al tiu tuta triopo de blokoj

312
00:15:49,510 --> 00:15:50,880
ke ni havas ĉi tie.

313
00:15:50,880 --> 00:15:54,670
Do rezultas mi povas simpligi mian
programo de akiranta liverita de ĉiuj de tiu

314
00:15:54,670 --> 00:15:58,270
kaj ĵus metis ĉi tien.

315
00:15:58,270 --> 00:16:01,620
Kaj nun li ankoraŭ iom
kalesxo, kaj tio estas bone nun.

316
00:16:01,620 --> 00:16:03,370
Ni lasos tion esti.

317
00:16:03,370 --> 00:16:06,000
Sed mia programo estas ankoraŭ
simpla, kaj tio, ankaŭ,

318
00:16:06,000 --> 00:16:09,060
estus reprezentanto
de golo en programming--

319
00:16:09,060 --> 00:16:13,430
estas ideale fari vian kodo kiel
simpla, kiel kompakta kiel ebla,

320
00:16:13,430 --> 00:16:15,650
dum ankoraŭ estante kiel
legebla kiel eblas.

321
00:16:15,650 --> 00:16:20,310
Vi ne volas fari ĝin tiel konciza
ke ĝi estas malfacile komprenebla.

322
00:16:20,310 --> 00:16:22,826
>> Sed rimarkis mi anstataŭis
tri blokoj kun unu,

323
00:16:22,826 --> 00:16:24,200
kaj tio estas disputeble bona afero.

324
00:16:24,200 --> 00:16:27,280
Mi abstraída for la nocio
de kontrolanta ĉu vi estas

325
00:16:27,280 --> 00:16:29,120
rande per nur unu bloko.

326
00:16:29,120 --> 00:16:31,520
Nun ni povas amuzi kun ĉi, fakte.

327
00:16:31,520 --> 00:16:35,790
Tiu ne aldonas tiel
intelekta valoro sed ludema valoro.

328
00:16:35,790 --> 00:16:39,730
Mi tuj iros antaŭen
kaj ekpreni ĉi sono tie.

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

330
00:16:42,900 --> 00:16:46,420
Do lasu min antaŭeniri kaj lasi min
haltigi la programon dum momento.

331
00:16:46,420 --> 00:16:52,070
Mi tuj gravuros la jenan:
permesante aliro al miaj mikrofono.

332
00:16:52,070 --> 00:16:53,181
>> Tie ni iru.

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

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

335
00:16:58,710 --> 00:17:01,140
Ni provu ĉi denove.

336
00:17:01,140 --> 00:17:02,279
Tie ni iru.

337
00:17:02,279 --> 00:17:03,570
Okej, mi registris la malĝustan aferon.

338
00:17:03,570 --> 00:17:04,580
Tie ni iru.

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

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

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

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

343
00:17:09,300 --> 00:17:10,791
Nun mi devas forigi tion.

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

345
00:17:11,290 --> 00:17:13,950
>> Do nun mi havas
registrado de simple "Ouch."

346
00:17:13,950 --> 00:17:18,040
Do nun mi tuj iros
antaŭen kaj nomas tiun "Ouch."

347
00:17:18,040 --> 00:17:20,270
Mi tuj reiros
al mia skriptoj, kaj nun

348
00:17:20,270 --> 00:17:25,460
avizo ekzistas tiu bloko kiu nomiĝas
ludi sonon "meow" aŭ ludi sonon "Ouch."

349
00:17:25,460 --> 00:17:28,920
Mi tuj treni ĉi, kaj kie
mi metis tion por komika efekto?

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

351
00:17:31,740 --> 00:17:37,860
Jes, do nun ĝi estas ia
kalesxon, ĉar nun ĉi block--

352
00:17:37,860 --> 00:17:42,050
Rimarku kiel tiu "se sur randon,
resalto "estas speco de mem-enhavita.

353
00:17:42,050 --> 00:17:43,704
Do mi devas redifini tiun.

354
00:17:43,704 --> 00:17:44,870
Lasu min antaŭeniri kaj fari tion.

355
00:17:44,870 --> 00:17:48,630
Lasu min forigi tiun kaj reiru
al nia originala, pli intenca

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

357
00:17:49,870 --> 00:18:01,080
Do "se tuŝi randon, tiam" mi volas
turni, kiel Viktorio proponita,

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

359
00:18:02,480 --> 00:18:05,497
Kaj mi volas ludi
la sono "Ouch" tie?

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

361
00:18:11,800 --> 00:18:15,580
>> Yeah, rimarki ĝi estas ekster
ke flava bloko.

362
00:18:15,580 --> 00:18:17,680
Do tiu, tro, estus
cimo, sed mi rimarkis ĝin.

363
00:18:17,680 --> 00:18:21,290
Do mi tuj treni ĝin supren tien,
kaj avizo nun ĝi estas ene la "se."

364
00:18:21,290 --> 00:18:24,250
Do la "se" estas tiu speco
de kiel brako-kiel makulo

365
00:18:24,250 --> 00:18:26,260
ke estas nur tuj
do kio estas ene de ĝi.

366
00:18:26,260 --> 00:18:30,216
Tial nun, se mi malzomi ĉe
la risko de annoying--

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

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

369
00:18:36,470 --> 00:18:39,910
>> DAVID Malan: Kaj
simple daŭrigi eterne.

370
00:18:39,910 --> 00:18:44,160
Nun nur akceli aferoj
tie, lasu min antaŭeniri kaj malfermu,

371
00:18:44,160 --> 00:18:50,460
ni say-- lasu min iri al iuj
de miaj propraj aferoj de klaso.

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

373
00:18:53,000 --> 00:19:00,220
Kaj lasu min malfermi, diru, ĉi
unu farita de unu el niaj instruado uloj

374
00:19:00,220 --> 00:19:01,500
paro de jaroj.

375
00:19:01,500 --> 00:19:04,732
Do kelkaj el vi eble memoras
tiu ludo de en la pasintaj tempoj,

376
00:19:04,732 --> 00:19:05,940
kaj ĝi estas vere rimarkinda.

377
00:19:05,940 --> 00:19:08,190
Kvankam ni faris la
simplajn programojn nun,

378
00:19:08,190 --> 00:19:09,980
ni rigardu, kion ĉi
vere aspektas.

379
00:19:09,980 --> 00:19:10,650
Lasu min bati teatraĵo.

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

381
00:19:14,210 --> 00:19:18,980
>> Do en ĉi tiu ludo, ni havas
rano, kaj uzante la sago keys--

382
00:19:18,980 --> 00:19:23,340
Li prenas grandan paŝojn ol mi remember--
Mi havas kontrolon super tiu rano.

383
00:19:23,340 --> 00:19:29,630
Kaj la celo estas atingi tra la okupataj
vojo sen turni aŭtojn.

384
00:19:29,630 --> 00:19:34,735
Kaj ni see-- se mi iros tien, mi
atendi loglibra rulumi per.

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

386
00:19:38,130 --> 00:19:39,274
Tio sentas kiel cimon.

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

388
00:19:42,240 --> 00:19:43,495
Tio estas ia eraro.

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

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

391
00:19:46,480 --> 00:19:51,550
Mi estas sur ĉi tie,
tie, kaj tiam vi tenas

392
00:19:51,550 --> 00:19:54,100
iranta ĝis vi akiras ĉiuj
la ranojn al la lilio almohadillas.

393
00:19:54,100 --> 00:19:55,920
Nun eble tio aspektos
des pli kompleksa,

394
00:19:55,920 --> 00:19:57,840
sed ni provu rompi
ĉi malsupren mense

395
00:19:57,840 --> 00:20:00,040
kaj parole en ĝia komponanto blokoj.

396
00:20:00,040 --> 00:20:03,910
Do ekzistas verŝajne enigmo
peco kiun ni ne vidis ankoraŭ

397
00:20:03,910 --> 00:20:07,440
sed tio respondas al pulsbatoj,
por tio mi trafis sur la klavaro.

398
00:20:07,440 --> 00:20:11,660
>> Do ekzistas verŝajne ia
bloko kiu diras, se klavo egalas supren,

399
00:20:11,660 --> 00:20:15,965
tiam fari ion kun Scratch--
eble movi ĝin 10 ŝtupoj tiamaniere.

400
00:20:15,965 --> 00:20:20,240
Se malsupren ŝlosilo estas premita, movi 10 paŝoj
Tiel, nek maldekstren klavon, movi 10 paŝoj

401
00:20:20,240 --> 00:20:21,710
Tiel, la 10-ŝtupoj tio.

402
00:20:21,710 --> 00:20:23,644
Mi klare turnis la kato en ranon.

403
00:20:23,644 --> 00:20:26,060
Do tio estas nur kie la
kostumo, kiel Scratch alvokoj it-- ni

404
00:20:26,060 --> 00:20:28,440
nur importitaj bildon de la rano.

405
00:20:28,440 --> 00:20:29,570
>> Sed kio alia okazas?

406
00:20:29,570 --> 00:20:32,794
Kion aliaj linioj de kodo,
kio alia enigmo pecoj

407
00:20:32,794 --> 00:20:35,460
faris Blake, nia instruado ulo,
uzi en tiu programo, ŝajne?

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

409
00:20:38,320 --> 00:20:42,730
Kio faras ĉiu move--
kion programado konstrui?

410
00:20:42,730 --> 00:20:44,950
>> Moviĝo, sure-- do la
movi bloko, por certa.

411
00:20:44,950 --> 00:20:49,330
Kaj kio estas kio movigxas bloko
ene de, plej probable?

412
00:20:49,330 --> 00:20:52,850
Yeah, ia buklo, eble
ĉiam blokas, eble ripeto block--

413
00:20:52,850 --> 00:20:54,070
ripeti ĝis bloko.

414
00:20:54,070 --> 00:20:57,330
Kaj tio estas kio faras la ŝtipoj kaj
rozo kusenetoj kaj ĉion alian movon

415
00:20:57,330 --> 00:20:57,990
reen.

416
00:20:57,990 --> 00:21:00,270
Ĝi simple okazas senfine.

417
00:21:00,270 --> 00:21:03,180
>> Kial iuj de la aŭtoj
movi pli rapide ol la aliaj?

418
00:21:03,180 --> 00:21:06,607
Kio estas malsama pri tiuj programoj?

419
00:21:06,607 --> 00:21:09,690
Yeah, probable iuj de ilin prenas
pli ŝtupojn samtempe kaj iuj el ili

420
00:21:09,690 --> 00:21:10,690
malpli paŝoj tuj.

421
00:21:10,690 --> 00:21:14,670
Kaj la vida efiko
Estas rapida kontre malrapida.

422
00:21:14,670 --> 00:21:16,030
>> Kion vi pensas okazis?

423
00:21:16,030 --> 00:21:19,700
Kiam mi akiris miajn rano tuta vojo
trans la strato kaj la rivero

424
00:21:19,700 --> 00:21:23,560
sur rozo kuseneton, iom
notinda okazis.

425
00:21:23,560 --> 00:21:26,540
Kio okazis kiam mi faris tion?

426
00:21:26,540 --> 00:21:27,210
Ĝi haltis.

427
00:21:27,210 --> 00:21:29,680
Ke rano haltis, kaj
Mi akiris duan rano.

428
00:21:29,680 --> 00:21:33,155
Do kio konstrukcio devas esti
uzata tie, kio trajto?

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

430
00:21:36,020 --> 00:21:38,660
>> Jes, do ekzistas ia
"Se" kondiĉi tie supre, ankaŭ.

431
00:21:38,660 --> 00:21:41,909
Kaj ĝi rezultas fjordon ni ne vidis this--
sed ekzistas aliaj blokoj en tie

432
00:21:41,909 --> 00:21:45,300
povas diri, se vi estas kortuŝa
alia aĵo sur la ekrano,

433
00:21:45,300 --> 00:21:47,720
Se vi tuŝis la lilio kuseneto, "tiam".

434
00:21:47,720 --> 00:21:50,810
Kaj tiam tio estas kiam ni
fari la duan rano aperi.

435
00:21:50,810 --> 00:21:54,969
Do eĉ se tiu ludo estas certe
tre datita, kvankam unuavide

436
00:21:54,969 --> 00:21:58,010
Tie estas tiel iranta on-- kaj Blake
ne vipi ĉi supre en du minutoj,

437
00:21:58,010 --> 00:22:00,390
ĝi verŝajne prenis lin plurajn
horoj por krei tiun ludon

438
00:22:00,390 --> 00:22:03,850
bazita sur sia memoro aŭ filmetoj
de pasintaj tempoj versio de ĝi.

439
00:22:03,850 --> 00:22:07,940
Sed ĉiu el tiuj malgrandaj aferoj
irante sur la ekrano en izolado

440
00:22:07,940 --> 00:22:11,550
bolas malsupren al tiuj tre simplaj
constructs-- movadoj aŭ deklaroj

441
00:22:11,550 --> 00:22:15,519
kiel ni diskutis, loops kaj
kondiĉoj, kaj tio estas pri ĝi.

442
00:22:15,519 --> 00:22:17,060
Ekzistas kelkaj aliaj amatoro karakterizaĵoj.

443
00:22:17,060 --> 00:22:19,130
Iuj el ili estas pure
estetika aŭ akustiko,

444
00:22:19,130 --> 00:22:20,964
kiel la sonoj mi ĵus ludis kun.

445
00:22:20,964 --> 00:22:23,380
Sed plejparte, vi
havas en tiu lingvo, Scratch,

446
00:22:23,380 --> 00:22:25,350
ĉiujn fundamentajn
konstruelementoj ke vi

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

448
00:22:29,280 --> 00:22:32,960
kaj kiom ajn da aliaj lingvoj.

449
00:22:32,960 --> 00:22:36,720
Demandojn pri Scratch?

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

451
00:22:37,220 --> 00:22:40,303
Do ni ne plonĝi en profundan al Scratch,
kvankam vi estas bonvena ĉi semajnfino,

452
00:22:40,303 --> 00:22:42,860
speciale se vi havas infanojn aŭ
nevinoj kaj nevoj kaj tia,

453
00:22:42,860 --> 00:22:44,220
enkonduki ilin al Scratch.

454
00:22:44,220 --> 00:22:47,960
Estas vere mirinde ludema
medio kun, kiel liaj aŭtoroj diras,

455
00:22:47,960 --> 00:22:49,120
tre altaj plafonoj.

456
00:22:49,120 --> 00:22:51,670
Kvankam ni komencis kun
tre malalta nivelo detaloj,

457
00:22:51,670 --> 00:22:54,890
vi povas vere fari sufiĉe
per ĝi, kaj tio estas eble

458
00:22:54,890 --> 00:22:57,360
manifestacio ĝuste tiun.

459
00:22:57,360 --> 00:23:02,920
>> Sed ni nun transiro al iu pli
kompleksaj problemoj, se vi volas,

460
00:23:02,920 --> 00:23:05,870
konata kiel "serĉado" kaj
"Ordigado" pli ĝenerale.

461
00:23:05,870 --> 00:23:09,500
Ni havis tiun telefonon libro earlier-- jen
alia simple por discussion--

462
00:23:09,500 --> 00:23:13,460
ke ni povis serĉi
pli efike ĉar

463
00:23:13,460 --> 00:23:15,270
de signifa supozo.

464
00:23:15,270 --> 00:23:17,655
Kaj nur por esti klara, kio
supozo mi faras

465
00:23:17,655 --> 00:23:19,280
kiam serĉanta tra tiu telefono libro?

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

467
00:23:23,342 --> 00:23:25,300
Ke Mike Smith estis en
la telefono libro, kvankam mi

468
00:23:25,300 --> 00:23:27,410
estus kapabla pritrakti
la scenaro sen li

469
00:23:27,410 --> 00:23:30,720
tie se mi nur haltis trofrue.

470
00:23:30,720 --> 00:23:31,806
La libro estas alfabeta.

471
00:23:31,806 --> 00:23:33,930
Kaj tio estas tre donacema
supozo, ĉar tiu

472
00:23:33,930 --> 00:23:36,580
signifas someone-- Mi speco
tranĉi angulo,

473
00:23:36,580 --> 00:23:40,580
kiel mi estas rapida ĉar iu
alia faris multa malfacila laboro por mi.

474
00:23:40,580 --> 00:23:43,120
>> Sed kion se la telefono
libro estis Neordigita?

475
00:23:43,120 --> 00:23:47,050
Eble Verizon havas mallaborema, ĵus ĵetis
ĉies nomojn kaj numerojn en tie

476
00:23:47,050 --> 00:23:50,120
eble en la ordo en kiu ili
subskribinta por telefono servo.

477
00:23:50,120 --> 00:23:54,570
Kaj kiom da tempo estas preni min
trovi iun kiel Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1.000 paĝo telefonon book-- kiom
paĝojn mi devas trarigardi?

479
00:23:58,160 --> 00:23:58,905
>> Ĉiuj ili.

480
00:23:58,905 --> 00:24:00,030
Vi estas ia el sorton.

481
00:24:00,030 --> 00:24:03,420
Vi laŭvorte devas rigardi ĉiun
paĝo se la telefono libro estas nur

482
00:24:03,420 --> 00:24:04,450
hazarde ordo.

483
00:24:04,450 --> 00:24:06,910
Vi eble ricevos bonŝanca kaj trovi Mike
sur la unua paĝo, ĉar li

484
00:24:06,910 --> 00:24:08,826
estis la unua kliento
ordigi telefono servo.

485
00:24:08,826 --> 00:24:10,760
Sed eble estis la lasta, ankaŭ.

486
00:24:10,760 --> 00:24:12,500
>> Tiel hazarda ordo estas ne bona.

487
00:24:12,500 --> 00:24:16,750
Do eble ni devas ordigi la
telefono libro aŭ ĝenerale speco datumoj

488
00:24:16,750 --> 00:24:18,520
ke ni estis donita.

489
00:24:18,520 --> 00:24:19,440
Kiel ni faru tion?

490
00:24:19,440 --> 00:24:21,360
>> Nu, lasu min nur provu
simpla ekzemplo tie.

491
00:24:21,360 --> 00:24:24,290
Lasu min antaŭeniri kaj rulos kiel
kelkaj nombroj sur la tabulo.

492
00:24:24,290 --> 00:24:35,480
Supozi la numerojn ni estas,
diru, kvar, du, unu, tri.

493
00:24:35,480 --> 00:24:38,390
Kaj Ben, ordigi tiujn numerojn por ni.

494
00:24:38,390 --> 00:24:39,017
>> OK bone.

495
00:24:39,017 --> 00:24:39,850
Kiel vi faris tion?

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

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

498
00:24:43,230 --> 00:24:44,710
Do komencu per la plej malgranda
valoro kaj la plej alta,

499
00:24:44,710 --> 00:24:46,084
kaj tio estas vere bona intuicio.

500
00:24:46,084 --> 00:24:48,080
Kaj rimarki ke ni
homoj estas vere bela

501
00:24:48,080 --> 00:24:49,913
bona ĉe solvi problemojn
tiel, almenaŭ

502
00:24:49,913 --> 00:24:51,810
Kiam la datumoj estas relative malgranda.

503
00:24:51,810 --> 00:24:54,860
Kiam vi komencas havi centojn
de nombroj, miloj de nombroj,

504
00:24:54,860 --> 00:24:58,440
Milionoj de nombroj, Ben probable
povis fari ĝin sufiĉe ke rapida,

505
00:24:58,440 --> 00:25:00,620
supozante ke ekzistis
breĉoj en la nombroj.

506
00:25:00,620 --> 00:25:03,450
Sufiĉe facile kalkuli en miliono
alie, nur la tempo konsumanta.

507
00:25:03,450 --> 00:25:07,150
>> Tial la algoritmo sonas
kiel Ben uzata ĝuste nun

508
00:25:07,150 --> 00:25:08,930
Estis serĉo por la plej malgranda nombro.

509
00:25:08,930 --> 00:25:12,900
Do eĉ se ni homoj povas preni
en multajn informojn vide,

510
00:25:12,900 --> 00:25:14,830
komputilo estas fakte
iom pli limigita.

511
00:25:14,830 --> 00:25:17,560
La komputilo povas nur
rigardi unu bajton je fojo

512
00:25:17,560 --> 00:25:20,770
aŭ eble kvar bajtoj je time--
tiuj tagoj eble 8 bajtoj en time--

513
00:25:20,770 --> 00:25:24,450
sed tre malgranda nombro
de bajtoj je donita tempo.

514
00:25:24,450 --> 00:25:28,480
>> Tiel donita ke ni vere havas
kvar apartaj valoroj here--

515
00:25:28,480 --> 00:25:32,440
kaj vi povas pensi de Ben kiel havado
blinders sur se li estus komputilo tia

516
00:25:32,440 --> 00:25:36,450
ke li ne povas vidi ion ajn alia
ol unu numeron ĉe time--

517
00:25:36,450 --> 00:25:39,720
do ni ĝenerale supozos, kiel en
English, ni legis de dekstra al maldekstra.

518
00:25:39,720 --> 00:25:42,870
Do la unua numero Ben probable rigardis
ĉe kvar kaj tiam tre rapide

519
00:25:42,870 --> 00:25:44,770
komprenis ke estas sufiĉe granda
number-- lasu min teni rigardanta.

520
00:25:44,770 --> 00:25:45,357
>> Ekzistas du.

521
00:25:45,357 --> 00:25:45,940
Atendu minuton.

522
00:25:45,940 --> 00:25:47,070
Du estas pli malgranda ol kvar.

523
00:25:47,070 --> 00:25:47,986
Mi tuj memoris.

524
00:25:47,986 --> 00:25:49,070
Du estas nun la plej malgranda.

525
00:25:49,070 --> 00:25:50,417
Nun one-- jen eĉ pli bona.

526
00:25:50,417 --> 00:25:51,250
Jen eĉ pli malgranda.

527
00:25:51,250 --> 00:25:54,000
Mi tuj forgesas pri du
kaj nur memoras unu nun.

528
00:25:54,000 --> 00:25:56,550
>> Kaj li povis halti rigardanta?

529
00:25:56,550 --> 00:25:58,360
Nu, li povus bazita
sur tiu informo,

530
00:25:58,360 --> 00:26:00,477
sed prefere serĉo
la resto de la listo.

531
00:26:00,477 --> 00:26:02,060
Ĉar se nulo estis en la listo?

532
00:26:02,060 --> 00:26:03,643
Kio se negativa estis en la listo?

533
00:26:03,643 --> 00:26:07,720
Li nur scias ke lia respondo
estas ĝusta, se li estas ĝisfunde

534
00:26:07,720 --> 00:26:08,729
kontrolis la tutan liston.

535
00:26:08,729 --> 00:26:10,020
Do ni rigardu la resto de ĉi tiu.

536
00:26:10,020 --> 00:26:11,394
Three-- ke estis malŝparo de tempo.

537
00:26:11,394 --> 00:26:13,540
Got malfeliĉa, sed mi
ankoraŭ ĝentile fari tion.

538
00:26:13,540 --> 00:26:17,857
Kaj do nun li supozeble
selektis la plej malgranda nombro

539
00:26:17,857 --> 00:26:20,440
kaj ĵus metis komence
de la listo, mi faros ĉi tie.

540
00:26:20,440 --> 00:26:23,480
Kion vi faris poste, kvankam
vi ne pensas pri ĝi preskaŭ

541
00:26:23,480 --> 00:26:25,962
al tiu mezuro?

542
00:26:25,962 --> 00:26:27,670
Ripetu la procezon,
tiel ia buklo.

543
00:26:27,670 --> 00:26:28,920
Estas familiara ideo.

544
00:26:28,920 --> 00:26:30,860
Do tie estas kvar.

545
00:26:30,860 --> 00:26:32,110
Jen nun la plej malgranda.

546
00:26:32,110 --> 00:26:33,220
Jen kandidato.

547
00:26:33,220 --> 00:26:33,900
Ne plu.

548
00:26:33,900 --> 00:26:34,770
Nun mi vidis du.

549
00:26:34,770 --> 00:26:36,630
Jen la sekva plej malgranda ero.

550
00:26:36,630 --> 00:26:40,800
Three-- tio ne pli malgranda, do
nun Ben povas desxiri la du.

551
00:26:40,800 --> 00:26:44,510
>> Kaj nun ni ripeti la procezon, kaj
kompreneble tri iĝas eltiris sekva.

552
00:26:44,510 --> 00:26:45,420
Ripeti la procezon.

553
00:26:45,420 --> 00:26:46,990
Kvar iĝas eltiris.

554
00:26:46,990 --> 00:26:50,140
Kaj nun ni estas ekstere de nombroj,
do la listo devas esti ordo.

555
00:26:50,140 --> 00:26:51,960
>> Kaj efektive, tio estas formala algoritmo.

556
00:26:51,960 --> 00:26:56,610
Komputila sciencisto farus
nomas tiun "selektado varon,"

557
00:26:56,610 --> 00:27:00,880
la ideo estanta speco de
listo iteratively-- denove

558
00:27:00,880 --> 00:27:03,807
kaj denove kaj denove elektante
la plej malgranda nombro.

559
00:27:03,807 --> 00:27:06,140
Kaj kio estas agrable pri ĝi
estas nur tiom Darn intuicia.

560
00:27:06,140 --> 00:27:07,470
Ĝi estas tiel simpla.

561
00:27:07,470 --> 00:27:11,100
Kaj vi povas ripeti la saman
agon denove kaj denove.

562
00:27:11,100 --> 00:27:12,150
Ĝi estas simpla.

563
00:27:12,150 --> 00:27:17,170
>> En tiu kazo ĝi estis rapida, sed
kiom longe? i vere preni?

564
00:27:17,170 --> 00:27:19,880
Ni faras ĝin ŝajni kaj
sentas iom pli teda.

565
00:27:19,880 --> 00:27:24,150
Do unu, du, tri, kvar, kvin ses,
sep, ok, naŭ, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15 16-- arbitra nombro.

567
00:27:26,160 --> 00:27:28,780
Mi nur volis pli ĉi
tempo ol nur kvar.

568
00:27:28,780 --> 00:27:30,780
Do se mi havas tutajn
faskon de nombroj now-- ĝi

569
00:27:30,780 --> 00:27:32,420
ne gravas
kion ili are-- ni

570
00:27:32,420 --> 00:27:34,380
pripensi kion tio
algoritmo vere ŝatas.

571
00:27:34,380 --> 00:27:35,857
>> Supozi ekzistas nombroj ekzistas.

572
00:27:35,857 --> 00:27:38,190
Denove, ne gravas kio
Ili estas, sed ili estas hazardaj.

573
00:27:38,190 --> 00:27:39,679
Mi aplikanta Ben algoritmo.

574
00:27:39,679 --> 00:27:41,220
Mi devas elekti la plej malgrandan numeron.

575
00:27:41,220 --> 00:27:41,761
Kion mi faras?

576
00:27:41,761 --> 00:27:44,240
Kaj mi tuj fizike
faru tiun fojon agi ĝin.

577
00:27:44,240 --> 00:27:46,099
Rigardante, rigardante,
rigardante, rigardante, rigardanta.

578
00:27:46,099 --> 00:27:48,140
Nur per la tempo mi akiras
Fine de la listo povas

579
00:27:48,140 --> 00:27:51,230
Mi konscias la plej malgranda
nombro estis du ĉi tempo.

580
00:27:51,230 --> 00:27:52,720
Oni ne estas en la listo.

581
00:27:52,720 --> 00:27:54,400
Do mi metis malsupren du.

582
00:27:54,400 --> 00:27:55,590
>> Kion mi faru?

583
00:27:55,590 --> 00:27:58,600
Rigardante, rigardante, rigardante, rigardanta.

584
00:27:58,600 --> 00:28:02,250
Nun mi trovis la nombro sep, ĉar
ekzistas mankoj en tiuj numbers--

585
00:28:02,250 --> 00:28:03,300
sed nur arbitra.

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

587
00:28:03,800 --> 00:28:06,030
Do nun mi povas meti malsupren sep.

588
00:28:06,030 --> 00:28:08,860
Rigardante rigardis, rigardis.

589
00:28:08,860 --> 00:28:11,030
>> Nun Mi supozas, de
Kompreneble, Ben ne

590
00:28:11,030 --> 00:28:14,780
havas kroman RAM, ekstra
memoro, ĉar, kompreneble,

591
00:28:14,780 --> 00:28:16,080
Mi serĉas en la sama nombro.

592
00:28:16,080 --> 00:28:18,246
Certe mi povus rememoris
ĉiuj tiuj nombroj,

593
00:28:18,246 --> 00:28:19,930
kaj tio estas absolute vera.

594
00:28:19,930 --> 00:28:22,610
Sed se Ben memoras cxiujn
de la nombroj li vidis,

595
00:28:22,610 --> 00:28:24,430
Li ne vere faris
fundamenta progreso

596
00:28:24,430 --> 00:28:26,170
ĉar li jam havas
la eblo serĉi

597
00:28:26,170 --> 00:28:27,540
tra la nombroj sur la tabulo.

598
00:28:27,540 --> 00:28:29,373
Memorante ĉiuj
nombroj ne helpas,

599
00:28:29,373 --> 00:28:32,490
ĉar li povas ankoraŭ kiel komputilo
nur rigardi, ni diris unu nombro

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

601
00:28:33,080 --> 00:28:35,760
Do ekzistas nenia trompanto
tie ke vi povas utiligi.

602
00:28:35,760 --> 00:28:39,170
>> Do fakte, kiel mi
teni serĉanta la listo,

603
00:28:39,170 --> 00:28:44,200
Mi laŭvorte devas nur plu iri
reen tra ĝi, elsxirintaj

604
00:28:44,200 --> 00:28:45,710
la sekva plej malgranda nombro.

605
00:28:45,710 --> 00:28:48,810
Kaj kiel vi povas ia konkludi
mia stulta movadoj,

606
00:28:48,810 --> 00:28:50,860
ĉi ĵus ricevas tre
teda tre rapide,

607
00:28:50,860 --> 00:28:54,850
kaj mi ŝajnas esti revenanta kaj
reen, tien kaj reen sufiĉe.

608
00:28:54,850 --> 00:29:03,220
Nun esti justa, mi ne devas iri
tiom, nu, ni see-- esti bela,

609
00:29:03,220 --> 00:29:06,310
Mi ne devas iri tre
kiel multaj paŝoj ĉiufoje.

610
00:29:06,310 --> 00:29:09,200
Ĉar, kompreneble, kiel mi
elekti numeroj de la listo,

611
00:29:09,200 --> 00:29:11,860
la ceteraj listo estas akiranta pli mallonga.

612
00:29:11,860 --> 00:29:14,240
>> Kaj do ni pensu pri
kiom da paŝoj mi reale

613
00:29:14,240 --> 00:29:16,010
traipsing tra ĉiu tempo.

614
00:29:16,010 --> 00:29:18,950
En la unua situacio
Ni havis 16 numerojn,

615
00:29:18,950 --> 00:29:22,210
kaj tiel maximally-- ni nur
fari tion dum discussion--

616
00:29:22,210 --> 00:29:25,640
Mi devis serĉi tra 16
nombroj trovi la plej malgranda.

617
00:29:25,640 --> 00:29:28,420
Sed unufoje mi elsxirintaj
la plej malgranda nombro, kiom

618
00:29:28,420 --> 00:29:30,590
longe estis la ceteraj listo, kompreneble?

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

620
00:29:31,420 --> 00:29:34,670
Tiom kiom nombroj faris Ben aŭ mi
rigardi tra la dua tempo ĉirkaŭe?

621
00:29:34,670 --> 00:29:36,832
15, nur por iri kaj trovi la plej malgranda.

622
00:29:36,832 --> 00:29:39,540
Sed nun, kompreneble, la listo estas,
Ankaŭ malgranda ol ĝi estis antaŭe.

623
00:29:39,540 --> 00:29:42,540
Do kiom da ŝtupoj faris mi
devas preni la venontan fojon?

624
00:29:42,540 --> 00:29:49,970
14 kaj tiam 13 kaj tiam 12, krom streketo
streketo dot, ĝis mi forlasis kun nur unu.

625
00:29:49,970 --> 00:29:53,146
Do nun komputila sciencisto farus
petu, nu, kio faras ke ĉiuj egalaj?

626
00:29:53,146 --> 00:29:55,770
Ĝi vere egalas iun konkretan
numero kiun ni povis certe

627
00:29:55,770 --> 00:30:00,490
fari aritmetike, sed ni volas paroli
pri la efikeco de algoritmoj

628
00:30:00,490 --> 00:30:04,940
iom pli formulaically,
sendependa de kiom longa la lerta estas.

629
00:30:04,940 --> 00:30:06,240
>> Kaj tiel vi scias kion?

630
00:30:06,240 --> 00:30:09,860
Tio estas 16, sed kiel mi diris antaŭe,
ni simple nomas la grandeco de la problemo

631
00:30:09,860 --> 00:30:10,970
n, kie n estas iu nombro.

632
00:30:10,970 --> 00:30:13,220
Eble estas 16, eble estas
tri, eble estas miliono.

633
00:30:13,220 --> 00:30:13,761
Mi ne scias.

634
00:30:13,761 --> 00:30:14,390
Mi ne zorgas.

635
00:30:14,390 --> 00:30:16,520
Kion mi vere volas estas
formulo kiu mi povas

636
00:30:16,520 --> 00:30:19,420
uzi kompari tiun algoritmon
kontraŭ aliaj algoritmoj

637
00:30:19,420 --> 00:30:22,350
ke iu povus aserti
estas bona aux malbona.

638
00:30:22,350 --> 00:30:25,430
>> Do rezultas, kaj mi nur
scias tion de lernojaro lernejo,

639
00:30:25,430 --> 00:30:34,790
ke tio efektive funkcias al la sama
aĵo kiel n super n plus unu super du.

640
00:30:34,790 --> 00:30:40,020
Kaj tio okazas egali, de
Kompreneble, n kvadratoj plus n super du.

641
00:30:40,020 --> 00:30:43,250
Do se mi volis formulon
cxar kiom da ŝtupoj

642
00:30:43,250 --> 00:30:46,330
estis implikitaj en rigardante ĉiujn
de tiuj nombroj multfoje

643
00:30:46,330 --> 00:30:52,681
kaj denove kaj denove, mi dirus
ĝi estas n kvadratoj plus n super du.

644
00:30:52,681 --> 00:30:53,430
Sed vi scias kion?

645
00:30:53,430 --> 00:30:54,500
Ĉi nur aspektas senorda.

646
00:30:54,500 --> 00:30:56,470
Mi nur vere volas
ĝenerala senco de aĵoj.

647
00:30:56,470 --> 00:30:58,810
Kaj vi eble memoras de
alta lernejo kiu ekzistas

648
00:30:58,810 --> 00:31:00,660
estas la nocio de Superaj termino.

649
00:31:00,660 --> 00:31:05,300
Kiu el tiuj terminoj, la n
kvadrato, la n, aŭ la duono,

650
00:31:05,300 --> 00:31:07,550
havas la plej trafo tempo?

651
00:31:07,550 --> 00:31:11,920
La granda n prenas, kio
pri tiaj aferoj la plej?

652
00:31:11,920 --> 00:31:15,560
>> Alivorte, se mi plug
en miliono, n kvadratoj

653
00:31:15,560 --> 00:31:17,900
tuj estos plej verŝajne
la domina faktoro,

654
00:31:17,900 --> 00:31:21,670
ĉar miliono fojojn
mem estas multe pli granda

655
00:31:21,670 --> 00:31:23,682
ol plie unu kroma miliono.

656
00:31:23,682 --> 00:31:24,390
Do vi scias kion?

657
00:31:24,390 --> 00:31:27,305
Jen tia Darn granda
numeron se vi akordas numero.

658
00:31:27,305 --> 00:31:28,430
Tio ne vere gravas.

659
00:31:28,430 --> 00:31:30,596
Ni ĵus tuj kruco kiu
eksteren kaj forgesi pri ĝi.

660
00:31:30,596 --> 00:31:34,250
Kaj tiel komputila sciencisto dirus
ke la efikeco de tiu algoritmo

661
00:31:34,250 --> 00:31:37,850
estas sur la ordo de n squared--
Mi signifas vere estas proksimuma kalkulado.

662
00:31:37,850 --> 00:31:40,810
Ĝi estas ia krude n kvadratoj.

663
00:31:40,810 --> 00:31:44,130
Dum tempo, la pli granda
kaj granda n prenas, tiu

664
00:31:44,130 --> 00:31:47,610
Estas bona takso por kio la
efikeco aŭ manko de efikeco

665
00:31:47,610 --> 00:31:49,400
de tiu algoritmo reale estas.

666
00:31:49,400 --> 00:31:52,040
Kaj mi derivi ke, kompreneble,
de reale fari la math.

667
00:31:52,040 --> 00:31:54,040
Sed nun mi simple svingante
miaj manoj, ĉar mi nur

668
00:31:54,040 --> 00:31:55,790
volas ĝenerala senco de tiu algoritmo.

669
00:31:55,790 --> 00:31:58,850
>> Tiel uzante la sama logiko, dume,
ni pripensu alian algoritmo

670
00:31:58,850 --> 00:32:01,162
ni jam rigardis at-- lineara serĉo.

671
00:32:01,162 --> 00:32:02,870
Kiam mi estis serĉanta
por la telefono book--

672
00:32:02,870 --> 00:32:05,980
Ne ordigado ĝin serĉado
tra la telefono book--

673
00:32:05,980 --> 00:32:09,197
ni tenis dirante ke ĝi estis
1.000 ŝtupoj, aŭ 500 ŝtupoj.

674
00:32:09,197 --> 00:32:10,280
Sed ni ĝeneraligi tion.

675
00:32:10,280 --> 00:32:12,860
Se estas n paĝoj
la telefono libro, kio estas

676
00:32:12,860 --> 00:32:17,250
la rula tempo aŭ la
efikeco de lineara serĉo?

677
00:32:17,250 --> 00:32:19,750
Ĝi estas sur la ordo de
kiom da paŝoj trovi

678
00:32:19,750 --> 00:32:24,210
Mike Smith uzanta lineara serĉo, la
unua algoritmo, aŭ eĉ la duan?

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

680
00:32:27,240 --> 00:32:31,710
>> En la plej malbona kazo, Mike
Estas fine de la libro.

681
00:32:31,710 --> 00:32:35,590
Do se la telefono libro havas 1.000 paĝojn,
ni diris lastan fojon, en la plej malbona kazo,

682
00:32:35,590 --> 00:32:38,380
ĝi povus preni malglate kiom
multaj paĝoj por trovi Mike?

683
00:32:38,380 --> 00:32:38,990
Kiel 1,000.

684
00:32:38,990 --> 00:32:39,830
Ĝi estas supera baro.

685
00:32:39,830 --> 00:32:41,790
Ĝi estas plej malbona ebla situacio.

686
00:32:41,790 --> 00:32:44,410
Sed denove, ni malproksimigi
de nombroj kiel 1,000 nun.

687
00:32:44,410 --> 00:32:45,730
Estas nur n.

688
00:32:45,730 --> 00:32:47,470
>> Do kio estas la logika konkludo?

689
00:32:47,470 --> 00:32:50,210
Trovanta Mike en telefono
Libro kiu havas n paĝoj

690
00:32:50,210 --> 00:32:55,280
povus preni, en la plej malbona kazo,
kiom da paŝoj sur la ordo de n?

691
00:32:55,280 --> 00:32:58,110
Kaj fakte komputilo
sciencisto dirus

692
00:32:58,110 --> 00:33:02,340
ke la rula tempo, aŭ la
rendimenton aŭ la efikecon

693
00:33:02,340 --> 00:33:07,470
aŭ senefikeco, de algoritmo kiel
lineara serĉo estas sur la ordo de n.

694
00:33:07,470 --> 00:33:10,010
Kaj ni povas apliki la samajn
logiko de transirante ion

695
00:33:10,010 --> 00:33:13,170
kiel mi ĵus faris por la dua
algoritmo ni havis kun la telefono libro,

696
00:33:13,170 --> 00:33:16,040
kie ni iris du paĝojn samtempe.

697
00:33:16,040 --> 00:33:20,120
>> Do 1,000 paĝo telefono libro eble
nin 500 paĝo turnoj, plus unu

698
00:33:20,120 --> 00:33:21,910
se ni duobligi dorson iomete.

699
00:33:21,910 --> 00:33:26,590
Do se telefono libro havas n paĝoj, sed
ni faras du paĝojn samtempe,

700
00:33:26,590 --> 00:33:28,900
jen malglate kio?

701
00:33:28,900 --> 00:33:33,190
N super du, tiel ke estas kiel n super du.

702
00:33:33,190 --> 00:33:38,490
Sed mi faris la aserto de
antaŭ momento ke n super two--

703
00:33:38,490 --> 00:33:41,060
jen speco de la sama kiel ĵus n.

704
00:33:41,060 --> 00:33:44,050
Estas nur konstanta faktoro,
komputilo sciencistoj dirus.

705
00:33:44,050 --> 00:33:45,970
Ni nur enfokusigi
la variabloj, really--

706
00:33:45,970 --> 00:33:47,780
la plej granda variabloj en la ekvacio.

707
00:33:47,780 --> 00:33:52,530
>> Do lineara serĉo, ĉu faris unu
paĝo samtempe du paĝojn samtempe,

708
00:33:52,530 --> 00:33:54,810
estas ia fundamente la sama.

709
00:33:54,810 --> 00:33:56,880
Ĝi estas ankoraŭ sur la ordo de n.

710
00:33:56,880 --> 00:34:01,930
Sed mi asertis kun mia bildo pli frue
ke la tria algoritmo ne

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

712
00:34:02,480 --> 00:34:03,605
Ĝi ne estis rekta linio.

713
00:34:03,605 --> 00:34:08,659
Estis tiu kurba linio, kaj la
algebra formulo estis kio?

714
00:34:08,659 --> 00:34:11,812
Protokolo de n-- tiel ensaluti bazo du de n.

715
00:34:11,812 --> 00:34:14,520
Kaj ni ne devas iri en tro
multe detalon sur logaritmoj hodiaŭ,

716
00:34:14,520 --> 00:34:17,394
sed plej komputilo sciencistoj ne volis
eĉ al vi, kion la bazo estas.

717
00:34:17,394 --> 00:34:20,639
Ĉar ĝi estas ĉiuj nur
konstanta faktoroj, tiel diri,

718
00:34:20,639 --> 00:34:22,659
nur iometa nombraj diferencoj.

719
00:34:22,659 --> 00:34:31,179
Kaj tial ĉi estus tre komuna
maniero por aparte formala komputilo

720
00:34:31,179 --> 00:34:33,949
sciencistoj ĉe tabulo aŭ
programistoj ĉe blanka tabulo

721
00:34:33,949 --> 00:34:36,889
fakte argumentante ke
algoritmo uzus

722
00:34:36,889 --> 00:34:39,500
kia la efikecon
ilia algoritmo estas.

723
00:34:39,500 --> 00:34:42,960
>> Kaj tio ne nepre io
vi diskuti en ajna granda detalo,

724
00:34:42,960 --> 00:34:47,889
sed bona programisto estas iu
kiu havas solidan, formala fono.

725
00:34:47,889 --> 00:34:50,120
Li estas kapabla paroli al
vi en tiu speco de vojo

726
00:34:50,120 --> 00:34:53,350
kaj fakte faras
kvalita argumentoj

727
00:34:53,350 --> 00:34:56,870
kial unu algoritmo aŭ
unu peco de programaro

728
00:34:56,870 --> 00:35:00,165
estas supera iel alia.

729
00:35:00,165 --> 00:35:02,540
Ĉar vi povus certe
nur kuri unu persono programo

730
00:35:02,540 --> 00:35:04,980
kaj kalkulu la numeron de duaj
ĝi prenas ordigi iujn numerojn,

731
00:35:04,980 --> 00:35:06,710
kaj vi povas kuri iuj
alia persono programo

732
00:35:06,710 --> 00:35:08,418
kaj kalkulu la numeron
de duaj prenas.

733
00:35:08,418 --> 00:35:12,840
Sed tio estas pli ĝenerala maniero, ke
vi povas uzi analizi algoritmojn,

734
00:35:12,840 --> 00:35:15,520
Se vi volas, nur sur
papero aŭ nur parole.

735
00:35:15,520 --> 00:35:18,430
Sen eĉ kurante ĝin, sen
eĉ provas specimeno enigoj,

736
00:35:18,430 --> 00:35:20,180
vi povas simple rezoni per ĝi.

737
00:35:20,180 --> 00:35:24,670
Kaj tiel per dunganta ellaboranto aŭ se
havi lin aŭ ŝin ia argumenti al vi

738
00:35:24,670 --> 00:35:28,460
kial ilia algoritmo, iliajn sekretajn
saŭco por serĉado miliardoj

739
00:35:28,460 --> 00:35:30,580
de retpaĝoj por via
entrepreno estas bona, ĉi tiuj

740
00:35:30,580 --> 00:35:33,302
estas la specoj de argumentoj ili
devus ideale povos fari.

741
00:35:33,302 --> 00:35:35,010
Aŭ almenaŭ tiuj estas
la specoj de aferoj

742
00:35:35,010 --> 00:35:40,211
kiu venus supren en diskuto, ĉe
almenaŭ en tre formala diskuto.

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

744
00:35:40,710 --> 00:35:44,400
Kaj Ben proponis ion
nomita selektado varon.

745
00:35:44,400 --> 00:35:48,200
Sed mi tuj proponi ke ekzistas
aliaj manieroj fari tion, ankaŭ.

746
00:35:48,200 --> 00:35:50,400
Kion mi ne vere ŝatas
pri Ben algoritmo

747
00:35:50,400 --> 00:35:54,400
estas ke li tenis piediranta aŭ
esti mi marsxas tien kaj reen

748
00:35:54,400 --> 00:35:56,930
kaj reen kaj reen.

749
00:35:56,930 --> 00:36:04,130
Kio se anstataŭe mi devis fari
ion similan nombroj tie

750
00:36:04,130 --> 00:36:08,200
kaj mi devis nur trakti ĉiun
numeron laŭvice kiel mi destinis?

751
00:36:08,200 --> 00:36:10,780
>> Alivorte, jen
mian liston de nombroj.

752
00:36:10,780 --> 00:36:12,944
Kvar, unu, tri, du.

753
00:36:12,944 --> 00:36:14,360
Kaj mi tuj faru la sekvajn.

754
00:36:14,360 --> 00:36:17,230
Mi tuj enigi la numerojn
kie ili apartenas prefere

755
00:36:17,230 --> 00:36:18,980
ol elektanta ilin unuope.

756
00:36:18,980 --> 00:36:20,820
Alivorte, jen la numero kvar.

757
00:36:20,820 --> 00:36:22,430
>> Jen mia originala listo.

758
00:36:22,430 --> 00:36:25,290
Kaj mi tuj subteni
esence nova listo tie.

759
00:36:25,290 --> 00:36:26,710
Do tiu estas la malnova listo.

760
00:36:26,710 --> 00:36:28,560
Tiu estas la nova listo.

761
00:36:28,560 --> 00:36:30,220
Mi vidas la numeron kvar unuaj.

762
00:36:30,220 --> 00:36:34,500
Mia nova listo estas komence malplena,
tial estas bagatele la kazo

763
00:36:34,500 --> 00:36:36,410
ke kvar estas nun varia listo.

764
00:36:36,410 --> 00:36:39,560
Mi nur prenante la numeron mi donita,
kaj mi metis ĝin en mian novan liston.

765
00:36:39,560 --> 00:36:41,460
>> Estas ĉi tiu nova lerta ordo?

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

767
00:36:41,990 --> 00:36:45,090
Ĝi estas stulta ĉar estas nur unu
elemento, sed ĝi estas absolute ordo.

768
00:36:45,090 --> 00:36:46,390
Nenio estas maloportune.

769
00:36:46,390 --> 00:36:49,290
Ĝi estas pli interesa, ĉi tiu algoritmo,
kiam mi movas al la sekva paŝo.

770
00:36:49,290 --> 00:36:50,550
>> Nun mi havas unu.

771
00:36:50,550 --> 00:36:55,430
Tial oni kompreneble apartenas ĉe la
komencante aŭ la fino de ĉi tiu nova listo?

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

773
00:36:56,360 --> 00:36:58,530
Do mi devas fari iun laboron nun.

774
00:36:58,530 --> 00:37:01,410
Mi estis prenanta iun
liberecojn kun mia markilo

775
00:37:01,410 --> 00:37:03,120
por nur desegni aferojn
kie mi volas ilin,

776
00:37:03,120 --> 00:37:05,320
sed tio ne estas vere
precizaj en komputilo.

777
00:37:05,320 --> 00:37:08,530
Komputila, kiel ni scias, ĝi havas
RAM aŭ Hazarda Aliro Memoro,

778
00:37:08,530 --> 00:37:12,411
kaj jen unu bajto kaj
alia bajto kaj alia bajto.

779
00:37:12,411 --> 00:37:14,910
Kaj se vi havas gigabajto de
RAM, vi havas miliardoj bajtoj,

780
00:37:14,910 --> 00:37:16,680
sed ili estas fizike en unu loko.

781
00:37:16,680 --> 00:37:19,540
Vi povas ne nur movi aĵojn ĉirkaŭe
strekante ĝin sur la tabulon

782
00:37:19,540 --> 00:37:20,750
kien ajn vi volas.

783
00:37:20,750 --> 00:37:24,090
Tial se mia nova listo havas
kvar lokoj en memoro,

784
00:37:24,090 --> 00:37:27,480
bedaŭrinde la kvar estas
jam en la malĝusta loko.

785
00:37:27,480 --> 00:37:30,410
>> Do enmeti la numeron unu
Mi ne povas simple desegni ĝin tien.

786
00:37:30,410 --> 00:37:31,901
Tiu memoro loko ne ekzistas.

787
00:37:31,901 --> 00:37:35,150
Ke estus trompado, kaj mi estis
trompado bilde dum kelkaj minutoj

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

789
00:37:35,800 --> 00:37:40,950
Do vere, se mi volas meti tie,
Mi devas provizore kopiu la kvar

790
00:37:40,950 --> 00:37:43,030
kaj surmetu la tie.

791
00:37:43,030 --> 00:37:45,500
>> Tio estas bone, ke estas ĝusta,
tio teknike eblas,

792
00:37:45,500 --> 00:37:48,410
sed rimarkas ke estas ekstra laboro.

793
00:37:48,410 --> 00:37:50,460
Mi ne simple metu la nombro en loko.

794
00:37:50,460 --> 00:37:53,026
Mi unue devis movi
nombro, tiam metis ĝin en loko,

795
00:37:53,026 --> 00:37:54,650
do mi specon de duobligis mian kvanto de laboro.

796
00:37:54,650 --> 00:37:55,660
Observu do, ke en menso.

797
00:37:55,660 --> 00:37:57,120
>> Sed mi nun faris kun tiu elemento.

798
00:37:57,120 --> 00:37:59,056
Nun mi volas ekpreni la numero tri.

799
00:37:59,056 --> 00:38:00,430
Kie, kompreneble, ĝi apartenas?

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

801
00:38:01,480 --> 00:38:03,650
Mi ne povas trompi anymore
kaj nur meti ĝin tie,

802
00:38:03,650 --> 00:38:06,770
ĉar, denove, ĉi tiu memoro
estas en fizika lokoj.

803
00:38:06,770 --> 00:38:10,900
Do mi devas kopii la kvar
kaj metis la tri super tie.

804
00:38:10,900 --> 00:38:11,550
Ne granda interkonsento.

805
00:38:11,550 --> 00:38:14,610
Estas nur unu kroma paŝo
again-- sentas tre malmultekosta.

806
00:38:14,610 --> 00:38:16,445
>> Sed nun mi pluiru al la du.

807
00:38:16,445 --> 00:38:17,820
Ambaŭ kompreneble apartenas tie.

808
00:38:17,820 --> 00:38:20,990
Nun vi komencas vidi kiel
la laboro povas amasiĝas.

809
00:38:20,990 --> 00:38:23,520
Nun kion mi devas fari?

810
00:38:23,520 --> 00:38:28,570
Yeah, Mi devi movi la kvar,
Mi tiam devas kopii la tri,

811
00:38:28,570 --> 00:38:31,200
kaj nun mi povas enmeti la du.

812
00:38:31,200 --> 00:38:34,460
Kaj la kaptaĵo kun ĉi
algoritmo, interese sufiĉe,

813
00:38:34,460 --> 00:38:41,050
estas ke eble ni havas pli ekstremaj
kazo kie ĝi diru ok, sep,

814
00:38:41,050 --> 00:38:45,150
ses, kvin, kvar, tri, du, unu.

815
00:38:45,150 --> 00:38:49,450
Tio estas, en multaj kuntekstoj,
la plej malbona kazo scenaro,

816
00:38:49,450 --> 00:38:51,570
ĉar la darn afero
Estas laŭvorte malantaŭen.

817
00:38:51,570 --> 00:38:53,670
>> Fakte ne
tuŝas Ben algoritmo,

818
00:38:53,670 --> 00:38:55,940
ĉar Ben selektado
ia li tuj teni

819
00:38:55,940 --> 00:38:58,359
irante tien kaj reen tra la listo.

820
00:38:58,359 --> 00:39:01,150
Kaj ĉar li ĉiam rigardanta
tra la tutaj ceteraj lerta,

821
00:39:01,150 --> 00:39:02,858
ne gravas
kie la elementoj estas.

822
00:39:02,858 --> 00:39:05,630
Sed en ĉi tiu kazo kun mia enmeto
approach-- ni provu tion.

823
00:39:05,630 --> 00:39:08,616
>> Do unu, du, tri, kvar,
kvin, ses, sep, ok.

824
00:39:08,616 --> 00:39:11,630
Unu, du, tri, kvar,
kvin, ses, sep, ok.

825
00:39:11,630 --> 00:39:14,320
Mi tuj prenos la ok,
kaj kie mi metis ĝin?

826
00:39:14,320 --> 00:39:17,260
Nu, je la komenco de mia listo,
ĉar tiu nova listo estas ordigita.

827
00:39:17,260 --> 00:39:18,760
Kaj mi transiras ĝin.

828
00:39:18,760 --> 00:39:20,551
>> Kie mi metis la sep?

829
00:39:20,551 --> 00:39:21,050
Darn ĝin.

830
00:39:21,050 --> 00:39:23,174
Bezonas iri tien, tiel
Mi devas fari iun kopiado.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Kaj nun la sep iras tien.

833
00:39:28,480 --> 00:39:29,860
Nun mi pluiru al la ses.

834
00:39:29,860 --> 00:39:30,980
Nun ĝi estas eĉ pli laboro.

835
00:39:30,980 --> 00:39:32,570
>> Ok devas iri tien.

836
00:39:32,570 --> 00:39:33,920
Sep devas iri tien.

837
00:39:33,920 --> 00:39:35,450
Nun la ses povas iri tien.

838
00:39:35,450 --> 00:39:37,950
Nun mi havigu la kvin.

839
00:39:37,950 --> 00:39:40,560
La ok devas iri
tie sep devas iri tie,

840
00:39:40,560 --> 00:39:43,650
ses devas iri tien, kaj
nun kvin ripeto.

841
00:39:43,650 --> 00:39:46,610
Kaj mi preskaux
movante ĝin senĉese.

842
00:39:46,610 --> 00:39:52,950
>> Do fine, ĉi algorithm-- ni
nomas ĝin inserción sort-- reale

843
00:39:52,950 --> 00:39:55,020
havas multe da laboro, tro.

844
00:39:55,020 --> 00:39:56,970
Estas nur malsamaj
speco de laboro ol Ben.

845
00:39:56,970 --> 00:40:00,090
Ben laboro havis mi iras
reen la tutan tempon,

846
00:40:00,090 --> 00:40:03,510
elektante la sekvanta malgranda
elemento denove kaj denove.

847
00:40:03,510 --> 00:40:06,660
Tiel okazis tio tre vida ia laboro.

848
00:40:06,660 --> 00:40:10,600
>> Tiu alia algoritmo, kiu estas ankoraŭ
correct-- ĝi ricevos la laboron done--

849
00:40:10,600 --> 00:40:12,800
nur ŝanĝas la kvanton de laboro.

850
00:40:12,800 --> 00:40:15,420
Aspektas kiel komence vi
ŝparante, ĉar vi estas nur

851
00:40:15,420 --> 00:40:19,190
kontraktanta kun ĉiu elemento
supren fronto sen marŝante ĉiuj

852
00:40:19,190 --> 00:40:20,930
la vojo tra la listo kiel Ben estis.

853
00:40:20,930 --> 00:40:25,300
Sed la problemo estas, speciale en tiuj
freneza kazoj kie ĉio dorsdirekte

854
00:40:25,300 --> 00:40:27,830
vi estas nur ia
prokrasti la laboremo

855
00:40:27,830 --> 00:40:30,360
ĝis vi devas fiksi vian erarojn.

856
00:40:30,360 --> 00:40:33,919
>> Kaj do se vi povas imagi tiun
ok kaj sep kaj ses kaj kvin

857
00:40:33,919 --> 00:40:36,710
kaj poste kvar kaj tri kaj du
movi sin tra la listo,

858
00:40:36,710 --> 00:40:39,060
ni ĵus ŝanĝis la
tipo de laboro ni faras.

859
00:40:39,060 --> 00:40:42,340
Anstataŭ fari ĝin en la
komencante de mia ripeto,

860
00:40:42,340 --> 00:40:45,250
Mi nur faras ĝin en la
Fine de ĉiu ripeto.

861
00:40:45,250 --> 00:40:50,550
Do rezultas ke tiu algoritmo,
Ankaŭ ĝenerale nomita inserción varon,

862
00:40:50,550 --> 00:40:52,190
estas ankaŭ sur la ordo de n kvadratoj.

863
00:40:52,190 --> 00:40:56,480
Ĝi estas fakte ne pli bona,
ne bona ĉe ĉiuj.

864
00:40:56,480 --> 00:41:00,810
>> Tamen, ekzistas tria alproksimiĝo
Mi kuraĝigus ni konsideri,

865
00:41:00,810 --> 00:41:02,970
kio estas tio.

866
00:41:02,970 --> 00:41:07,850
Do supozu mia lerta, por simpleco
denove, estas kvar, unu, tri,

867
00:41:07,850 --> 00:41:11,080
two-- nur kvar numeroj.

868
00:41:11,080 --> 00:41:13,300
Ben havis bonan intuicion,
bona homa intuicio

869
00:41:13,300 --> 00:41:16,340
antaŭe, por kiuj ni fiksis la tuta
listo eventually-- inserción varo.

870
00:41:16,340 --> 00:41:18,020
Mi kaĵolis ni kune.

871
00:41:18,020 --> 00:41:22,530
Sed ni konsideru la
simpla maniero ripari tiun liston.

872
00:41:22,530 --> 00:41:24,110
>> Tiu listo ne estas ordigitaj.

873
00:41:24,110 --> 00:41:26,130
Kial?

874
00:41:26,130 --> 00:41:31,920
En la angla, klarigas kial
ĝi ne vere ordo.

875
00:41:31,920 --> 00:41:33,400
Kion tio signifas ne esti ordo?

876
00:41:33,400 --> 00:41:34,220
>> Lernanto: Tio ne secuencial.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Malan: Ne secuencial.

878
00:41:34,990 --> 00:41:35,822
Donu al mi ekzemplon.

879
00:41:35,822 --> 00:41:37,180
>> Lernanto: Metu ilin en ordo.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Malan: Bone.

881
00:41:37,440 --> 00:41:38,790
Donu al mi pli specifa ekzemplo.

882
00:41:38,790 --> 00:41:39,832
>> Lernanto: Supreniranta ordo.

883
00:41:39,832 --> 00:41:41,206
DAVID Malan: Ne suprenirante ordo.

884
00:41:41,206 --> 00:41:42,100
Esti pli preciza.

885
00:41:42,100 --> 00:41:45,190
Mi ne scias kion vi celas diri per supreniranta.

886
00:41:45,190 --> 00:41:47,150
Kio okazas?

887
00:41:47,150 --> 00:41:49,930
>> Lernanto: La plej malgranda de la
nombroj ne en la unua spaco.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Malan: La plej malgranda nombro de
Ne en la unua spaco.

889
00:41:51,140 --> 00:41:52,120
Esti pli specifaj.

890
00:41:52,120 --> 00:41:55,000
Mi komencas populariĝis.

891
00:41:55,000 --> 00:41:59,470
Ni rakonti, sed
kio estas el ordo tie?

892
00:41:59,470 --> 00:42:00,707
>> Lernanto: Nombraj sekvenco.

893
00:42:00,707 --> 00:42:02,040
DAVID Malan: Nombraj sekvenco.

894
00:42:02,040 --> 00:42:04,248
Ĉies ia plenumado
ĝi here-- tre alta nivelo.

895
00:42:04,248 --> 00:42:07,450
Nur laŭvorte diri min kio estas
erara kiel kvin-jaraĝa forto.

896
00:42:07,450 --> 00:42:08,310
>> Lernanto: Plus unu.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Malan: Kio estas tio?

898
00:42:08,750 --> 00:42:09,610
>> Lernanto: Plus unu.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Malan: Kion signifas plus unu?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Donu malsama kvin-jaraĝa.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Kio okazas, panjo?

904
00:42:18,330 --> 00:42:19,940
Kio okazas, paĉjo?

905
00:42:19,940 --> 00:42:22,808
Kion signifas ĉi tio ne ordo?

906
00:42:22,808 --> 00:42:24,370
>> Lernanto: Ĝi ne estas la gxusta loko.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Malan: Kio estas
ne en la ĝusta loko?

908
00:42:25,580 --> 00:42:26,174
>> Lernanto: Kvar.

909
00:42:26,174 --> 00:42:27,090
DAVID Malan: Bone, bone.

910
00:42:27,090 --> 00:42:29,110
Do kvar ne kie ĝi devus esti.

911
00:42:29,110 --> 00:42:30,590
Aparte, estas tiu rajto?

912
00:42:30,590 --> 00:42:33,000
Dudek unu, la unua
du nombroj mi vidas.

913
00:42:33,000 --> 00:42:34,930
Estas ĉi tiu rajto?

914
00:42:34,930 --> 00:42:36,427
Ne, ili estas el ordo, ĉu ne?

915
00:42:36,427 --> 00:42:38,135
Fakte, pensas nun
pri komputilo, ankaŭ.

916
00:42:38,135 --> 00:42:40,824
Ĝi povas nur rigardi eble unu,
eble du aferojn ĉe once--

917
00:42:40,824 --> 00:42:43,240
kaj fakte nur unu afero
samtempe, sed povas almenaŭ

918
00:42:43,240 --> 00:42:45,790
rigardi unu afero tiam la
sekva afero tuj apud ĝi.

919
00:42:45,790 --> 00:42:47,380
>> Tiaj estas tiuj en ordo?

920
00:42:47,380 --> 00:42:48,032
Kompreneble ne.

921
00:42:48,032 --> 00:42:48,740
Do vi scias kion?

922
00:42:48,740 --> 00:42:51,020
Kial ni ne prenos bebo
paŝoj fiksi tiun problemon

923
00:42:51,020 --> 00:42:53,410
anstataŭ fari tiujn fancy
algoritmoj kiel Ben, kie

924
00:42:53,410 --> 00:42:56,440
li ia fiksi ĝin
looping tra la listo

925
00:42:56,440 --> 00:42:59,670
anstataŭ fari kion mi faris, kie
Mi nur ia fiksita kiel ni iros?

926
00:42:59,670 --> 00:43:03,650
Ni nur laŭvorte detruu la
nocio de order-- nombra ordo,

927
00:43:03,650 --> 00:43:06,990
nomas ĝin kion ajn vi want--
en tiuj paroj komparoj.

928
00:43:06,990 --> 00:43:07,590
>> Kvar kaj unu.

929
00:43:07,590 --> 00:43:09,970
Estas ĉi la ĝusta ordo?

930
00:43:09,970 --> 00:43:11,310
Do ni ripari tiun.

931
00:43:11,310 --> 00:43:14,700
Unu kaj kvar, kaj poste
ni simple kopiu tion.

932
00:43:14,700 --> 00:43:15,560
Bone, bone.

933
00:43:15,560 --> 00:43:17,022
Mi riparis unu kaj kvar.

934
00:43:17,022 --> 00:43:18,320
Tri kaj du?

935
00:43:18,320 --> 00:43:18,820
Ne

936
00:43:18,820 --> 00:43:21,690
Lasu miajn vortojn kongrui miajn fingrojn.

937
00:43:21,690 --> 00:43:23,695
Dudek tri?

938
00:43:23,695 --> 00:43:27,930
>> Ĝi estas ne en ordo, do mi tuj
fari unu, tri, kvar, du.

939
00:43:27,930 --> 00:43:28,680
OK bone.

940
00:43:28,680 --> 00:43:32,310
Nun dudek du?

941
00:43:32,310 --> 00:43:33,370
Ni devas redifini tiun ankaŭ.

942
00:43:33,370 --> 00:43:36,700
Do unu, tri, du, kvar.

943
00:43:36,700 --> 00:43:39,820
Tiel estas ĝi ordo?

944
00:43:39,820 --> 00:43:43,170
Ne, sed ĉu ĝi pli proksima al ordo?

945
00:43:43,170 --> 00:43:48,930
>> Estas, ĉar ni fiksis ĉi
eraro, ni fiksis la miskompreno,

946
00:43:48,930 --> 00:43:50,370
kaj ni fiksis ĉi eraras.

947
00:43:50,370 --> 00:43:52,420
Do ni fiksis tri erarojn disputeble.

948
00:43:52,420 --> 00:43:58,100
Ankoraŭ ne vere aspektas ordo, sed
ĝi estas objektive pli proksima al ordo

949
00:43:58,100 --> 00:44:00,080
ĉar ni fiksis kelkaj el tiuj eraroj.

950
00:44:00,080 --> 00:44:02,047
>> Nun kion mi faru?

951
00:44:02,047 --> 00:44:03,630
Mi ia atingis la finon de la listo.

952
00:44:03,630 --> 00:44:05,680
Mi ŝajnis esti fiksita
ĉiuj eraroj, sed ne.

953
00:44:05,680 --> 00:44:08,510
Ĉar tiukaze, iuj nombroj
eble bobelis proksimaj

954
00:44:08,510 --> 00:44:10,410
aliaj nombroj ke
ankoraŭ el ordo.

955
00:44:10,410 --> 00:44:12,951
Do ni faru ĝin denove, kaj Mi instruos vin
simple fari ĝin en loko ĉi tempo.

956
00:44:12,951 --> 00:44:14,170
Unu kaj tri?

957
00:44:14,170 --> 00:44:14,720
Estas bone.

958
00:44:14,720 --> 00:44:16,070
Tri kaj du?

959
00:44:16,070 --> 00:44:17,560
Kompreneble ne, do ni ŝanĝu tion.

960
00:44:17,560 --> 00:44:19,160
Tial du, tri.

961
00:44:19,160 --> 00:44:21,340
Tri kaj kvar?

962
00:44:21,340 --> 00:44:24,370
Kaj nun ni nur esti
aparte pedanta tie.

963
00:44:24,370 --> 00:44:26,350
Ĉu ordo?

964
00:44:26,350 --> 00:44:29,280
Vi homoj scias ĝi estas ordo.

965
00:44:29,280 --> 00:44:30,400
>> Mi devas provi denove.

966
00:44:30,400 --> 00:44:31,900
Tiel Olivia proponas mi reprovu.

967
00:44:31,900 --> 00:44:32,530
Kial?

968
00:44:32,530 --> 00:44:35,810
Ĉar komputilo ne havas
la lukso de niaj homaj okuloj

969
00:44:35,810 --> 00:44:38,080
de nur rigardante back-- OK, mi faris.

970
00:44:38,080 --> 00:44:41,610
Kiel la komputilo determinas
ke la listo estas jam ordo?

971
00:44:41,610 --> 00:44:44,590
Mekanike.

972
00:44:44,590 --> 00:44:47,650
>> Mi devus iri tra
refoje, kaj nur se mi

973
00:44:47,650 --> 00:44:51,190
ne fari / trovos erarojn mi
tiam konkludi kiel la komputilo, Yep,

974
00:44:51,190 --> 00:44:51,980
Ni estas bone iri.

975
00:44:51,980 --> 00:44:54,850
Do unu kaj du po
tri, tri kaj kvar.

976
00:44:54,850 --> 00:44:58,030
Nun mi povas definitive diri ĉi estas
ordo, ĉar mi nenion ŝanĝas.

977
00:44:58,030 --> 00:45:01,940
GXi estus nun cimon kaj ĵus
malsaĝa se mi, la komputilo,

978
00:45:01,940 --> 00:45:05,640
demandis tiujn samajn demandojn denove
atendante malsamajn respondojn.

979
00:45:05,640 --> 00:45:07,110
Ne devus okazi.

980
00:45:07,110 --> 00:45:08,600
>> Kaj do nun la listo estas ordigita.

981
00:45:08,600 --> 00:45:12,630
Bedaŭrinde, veturtempo de
tiu algoritmo estas ankaŭ n kvadratoj.

982
00:45:12,630 --> 00:45:13,130
Kial?

983
00:45:13,130 --> 00:45:19,520
Ĉar vi havas n nombroj, kaj en la
plej malbona kazo vi devas movi n nombroj

984
00:45:19,520 --> 00:45:23,637
n fojoj ĉar vi devos teni iranta
reen por kontroli kaj potenciale ripari

985
00:45:23,637 --> 00:45:24,220
tiuj nombroj.

986
00:45:24,220 --> 00:45:26,280
Kaj ni povas fari pli
formalan analizon, tro.

987
00:45:26,280 --> 00:45:29,530
>> Do tiu estas la tuta diri ni prenis
tri malsamaj aliroj, oni

988
00:45:29,530 --> 00:45:32,210
ili tuj intuicia
la batilon de Ben

989
00:45:32,210 --> 00:45:35,170
al mia proponita inserción
speco al ĉi tiu

990
00:45:35,170 --> 00:45:38,540
kie ia forgesu
la arbaro por la arboj komence.

991
00:45:38,540 --> 00:45:41,760
Sed poste se vi preni retropaŝon,
voilà, ni fiksis la ordigado nocio.

992
00:45:41,760 --> 00:45:43,824
Do tiu estas, kuraĝas diri,
suba nivelo eble

993
00:45:43,824 --> 00:45:45,740
ol iuj el tiuj aliaj
algoritmoj, sed ni

994
00:45:45,740 --> 00:45:48,550
vidu se ni ne povas visualizar
tiuj tra ĉi.

995
00:45:48,550 --> 00:45:51,450
>> Do tiu estas iu bela
programaro kiu iu

996
00:45:51,450 --> 00:45:56,110
skribis uzante bunta stangoj kiuj estas
tuj fari la sekvan por ni.

997
00:45:56,110 --> 00:45:57,736
Ĉiu de ĉi tiuj stangoj reprezentas nombron.

998
00:45:57,736 --> 00:46:00,026
Taller la trinkejo, la pli granda
la nombro, pli malgranda la trinkejo,

999
00:46:00,026 --> 00:46:00,990
la pli malgranda la nombro.

1000
00:46:00,990 --> 00:46:05,880
Do ideale ni volas belan piramido
kie komenciĝas malgrandaj kaj ricevas grandan,

1001
00:46:05,880 --> 00:46:08,330
kaj tio signifus ke
tiuj stangoj estas ordo.

1002
00:46:08,330 --> 00:46:11,200
Do mi tuj iros antaŭen kaj elekti,
ekzemple Ben algoritmo

1003
00:46:11,200 --> 00:46:13,990
first-- selektado varon.

1004
00:46:13,990 --> 00:46:16,220
>> Kaj rimarki kio ĝi estas faranta.

1005
00:46:16,220 --> 00:46:18,670
La vojo ili elektis al
bildigi tiun algoritmon

1006
00:46:18,670 --> 00:46:22,090
estas ke, same kiel mi estis
promenante tra mia lerta,

1007
00:46:22,090 --> 00:46:24,710
tiu programo estas piediranta
tra lia lerta de numeroj,

1008
00:46:24,710 --> 00:46:28,160
elstarante en rozkolora ĉiu
numeron ke ĝi rigardas.

1009
00:46:28,160 --> 00:46:32,360
Kaj kio estas ronde okazi ĝuste nun?

1010
00:46:32,360 --> 00:46:35,154
>> La plej malgranda nombro kiu
Mi nek Ben trovis subite

1011
00:46:35,154 --> 00:46:36,820
iĝas proponita al la komenco de la listo.

1012
00:46:36,820 --> 00:46:40,037
Kaj rimarki oni faris elhejmigi
la nombro kiu estis tie,

1013
00:46:40,037 --> 00:46:41,120
kaj tio estas perfekte bone.

1014
00:46:41,120 --> 00:46:42,600
Mi ne eniros en tiu nivelo de detalo.

1015
00:46:42,600 --> 00:46:44,308
Sed ni devas meti
ke nombro ie,

1016
00:46:44,308 --> 00:46:47,775
Do ni simple kopiis ĝin al la
malfermita loko kiu estis kreita.

1017
00:46:47,775 --> 00:46:49,900
Do mi tuj rapidi ĉi
supren, ĉar alie ĝi

1018
00:46:49,900 --> 00:46:51,871
iĝas tre teda rapide.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Kuraĝigo speed-- tie ni iru.

1021
00:46:58,600 --> 00:47:01,850
Tial nun sama principo
Mi aplikis, sed vi

1022
00:47:01,850 --> 00:47:06,540
povas komenci senti la algoritmo, se vi
volo, aŭ vidi ĝin iom pli klare.

1023
00:47:06,540 --> 00:47:13,190
Kaj tiu algoritmo havas la efikon de
elektante la sekva plej malgranda elemento,

1024
00:47:13,190 --> 00:47:16,422
tiel vi tuj komencos
vidu deklivirejo supre maldekstre.

1025
00:47:16,422 --> 00:47:19,130
Kaj sur ĉiu ripeto, kiel mi
proponis, ĝi faras iom malpli laboro.

1026
00:47:19,130 --> 00:47:21,921
Ĝi ne devas iri la tutan vojon
reen al la maldekstra fino de la listo,

1027
00:47:21,921 --> 00:47:23,900
ĉar ĝi jam
konas tiujn estas ordo.

1028
00:47:23,900 --> 00:47:28,129
Do speco de sentas estas
akceli, kvankam ĉiu paŝo estas

1029
00:47:28,129 --> 00:47:29,420
prenante la sama kvanto de tempo.

1030
00:47:29,420 --> 00:47:31,600
Ekzistas nur malmultaj paŝoj ceteraj.

1031
00:47:31,600 --> 00:47:35,240
Kaj nun vi povas ia sentas la
algoritmo purigi la fino de ĝi,

1032
00:47:35,240 --> 00:47:37,040
kaj ja nun ĝi estas ordo.

1033
00:47:37,040 --> 00:47:41,620
>> Tiel inserción varo estas ĉiuj farita.

1034
00:47:41,620 --> 00:47:43,600
Mi bezonas re-randomize la tabelo.

1035
00:47:43,600 --> 00:47:45,940
Kaj rimarkos mi povas nur
teni randomizing ŝin,

1036
00:47:45,940 --> 00:47:50,630
kaj ni akiros proksimuma kalkulado de
la sama alproksimiĝo, inserción varo.

1037
00:47:50,630 --> 00:47:55,050
Lasu min malrapidigi ĝin malsupren ĉi tien.

1038
00:47:55,050 --> 00:47:56,915
Komencu ke super.

1039
00:47:56,915 --> 00:47:57,414
Halti.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Ni salti kvar.

1042
00:48:02,410 --> 00:48:03,200
Tie ni iru.

1043
00:48:03,200 --> 00:48:04,190
Randomize ili tabelo.

1044
00:48:04,190 --> 00:48:05,555
Kaj tie ni go-- inserción varo.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Ludi.

1047
00:48:12,800 --> 00:48:17,280
Rimarki ke ĝi estas kontraktanta kun ĉiu
elementon i renkontas tuj,

1048
00:48:17,280 --> 00:48:20,282
sed se ĝi apartenas en
la malĝusta loko avizo

1049
00:48:20,282 --> 00:48:21,740
ĉiuj de la laboro kiu devas okazi.

1050
00:48:21,740 --> 00:48:24,700
Ni devas konservi sxangxigxantaj pli
kaj pli elementoj por fari lokon

1051
00:48:24,700 --> 00:48:27,340
por la unu ni volas meti en lokon.

1052
00:48:27,340 --> 00:48:30,740
>> Do ni koncentranta sur la
maldekstra fino de la listo nur.

1053
00:48:30,740 --> 00:48:34,460
Rimarku ni eĉ ne rigardis at-- ni
ne elstarigita en rozkolora ion

1054
00:48:34,460 --> 00:48:35,610
dekstre.

1055
00:48:35,610 --> 00:48:38,180
Ni nur pritraktas
la problemoj ni iros,

1056
00:48:38,180 --> 00:48:40,430
sed ni kreas multajn
labori por ni mem ankoraŭ.

1057
00:48:40,430 --> 00:48:44,410
Kaj do se ni akceli ĉi supren
nun iri al kompletiĝo,

1058
00:48:44,410 --> 00:48:46,210
ĝi havas malsaman senton al ĝi efektive.

1059
00:48:46,210 --> 00:48:50,150
Ĝi simple koncentranta sur la maldekstra fino sed
faras iom pli da laboro kiel needed--

1060
00:48:50,150 --> 00:48:53,230
ia glatigante aferoj
super, fiksi aferojn,

1061
00:48:53,230 --> 00:48:58,350
sed kontraktanta finfine kun
ĉiu elemento unuope

1062
00:48:58,350 --> 00:49:07,740
ĝis ni atingos estas- bone, ni
ĉiuj scias ke tiu tuj finos,

1063
00:49:07,740 --> 00:49:09,700
do ĝi estas iom underwhelming eble.

1064
00:49:09,700 --> 00:49:12,830
>> Sed la lerta en la end--
spoiler-- tuj estos ordo.

1065
00:49:12,830 --> 00:49:15,300
Do ni rigardu tiun lasta.

1066
00:49:15,300 --> 00:49:16,840
Ni ne povas simple salti nun.

1067
00:49:16,840 --> 00:49:18,000
Ni estas preskaŭ tie.

1068
00:49:18,000 --> 00:49:19,980
Du iri, oni iros.

1069
00:49:19,980 --> 00:49:22,680
Kaj voilà.

1070
00:49:22,680 --> 00:49:23,450
Bonega.

1071
00:49:23,450 --> 00:49:27,220
>> Do nun ni faru unu lasta,
re-randomizing kun bobelo varo.

1072
00:49:27,220 --> 00:49:31,690
Kaj rimarki tie, precipe se mi malrapidigos ĝin
malsupren, ĉi tio konservi rapidas tra.

1073
00:49:31,690 --> 00:49:36,830
Sed rimarki ĝin nur faras duope
comparisons-- ia lokaj solvoj.

1074
00:49:36,830 --> 00:49:39,050
Sed tuj kiam ni atingos
Fine de la listo en rozkolora,

1075
00:49:39,050 --> 00:49:40,690
kion tuj devos okazi denove?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Yeah, ĝi tuj devas
rekomencos, ĉar nur

1078
00:49:46,830 --> 00:49:49,870
fiksa duope erarojn.

1079
00:49:49,870 --> 00:49:53,120
Kaj ke eble malkaŝis ankoraŭ aliaj.

1080
00:49:53,120 --> 00:49:58,950
Kaj do se vi akceli ĉi supren, vi
vidu, kiom la nomo implicas,

1081
00:49:58,950 --> 00:50:01,870
la malgrandaj elements-- aŭ pli ĝuste,
la grandaj elements-- komencas

1082
00:50:01,870 --> 00:50:03,740
al bobelo ĝis la supro, se vi volas.

1083
00:50:03,740 --> 00:50:07,380
Kaj la pli malgrandaj elementoj estas
komencantaj bobelo malsupren maldekstren.

1084
00:50:07,380 --> 00:50:10,780
Kaj efektive, jen speco de
la vida efekto ankaŭ.

1085
00:50:10,780 --> 00:50:17,150
Kaj tiel tiu finos finante
en tre simila maniero, ankaŭ.

1086
00:50:17,150 --> 00:50:19,160
>> Ni ne devas logxi
sur tiu aparta.

1087
00:50:19,160 --> 00:50:21,010
Lasu min malfermi ĉi nun, tro.

1088
00:50:21,010 --> 00:50:24,040
Ekzistas kelkaj aliaj ordigado algoritmoj
en la mondo, kelkaj el kiuj

1089
00:50:24,040 --> 00:50:25,580
estas kaptitaj tie.

1090
00:50:25,580 --> 00:50:29,960
Kaj speciale por lernantoj kiuj ne
nepre vida aŭ matematika,

1091
00:50:29,960 --> 00:50:31,930
kiel ni faris antaŭe, ni povas
Ankaŭ tion audially

1092
00:50:31,930 --> 00:50:34,210
se ni asocias sono kun tiu.

1093
00:50:34,210 --> 00:50:36,990
Kaj simple por amuzo, jen
kelkaj malsamaj algoritmoj,

1094
00:50:36,990 --> 00:50:40,950
kaj unu el ili precipe vi
tuj rimarkos nomiĝas "merge varon."

1095
00:50:40,950 --> 00:50:43,250
>> Ĝi estas fakte principe
bona algoritmo,

1096
00:50:43,250 --> 00:50:45,860
tia ke kunfandi varon, unu el
tiujn vi estas estonta vidi,

1097
00:50:45,860 --> 00:50:49,170
ne ordo de n kvadratoj.

1098
00:50:49,170 --> 00:50:57,280
Ĝi estas sur la ordo de n fojoj logo de
n, kiu estas vere malgranda kaj tiel

1099
00:50:57,280 --> 00:50:58,940
rapide ol tiuj aliaj tri.

1100
00:50:58,940 --> 00:51:00,670
Kaj ekzistas kelkaj aliaj
malsaĝa kiuj vidos.

1101
00:51:00,670 --> 00:51:01,933
>> Do jen ni iras kun iuj sono.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Jen inserción varo, do denove
ĝi estas nur pritraktas la elementoj

1104
00:51:10,490 --> 00:51:13,420
kiel ili venis.

1105
00:51:13,420 --> 00:51:17,180
Tio estas bobelo varo, do estas
konsiderante ilin paroj samtempe.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Kaj denove, la plej grandaj elementoj
estas bobelis ĝis la supro.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Poste supre selektado varon.

1110
00:51:41,710 --> 00:51:45,420
Tio Ben algoritmo, kie
denove li elektanta ripete

1111
00:51:45,420 --> 00:51:46,843
la sekva plej malgranda ero.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Kaj denove, nun vi povas vere aŭdi tion
ĝi estas rapidigo sed nur tiom

1114
00:51:53,900 --> 00:51:58,230
kiel ĝi estas fari malpli kaj malpli
labori sur ĉiu ripeto.

1115
00:51:58,230 --> 00:52:04,170
Tiu estas la pli rapida unu, kunfandi varon,
kiu ordigado kukojn nombroj

1116
00:52:04,170 --> 00:52:05,971
kune kaj tiam kombini ilin.

1117
00:52:05,971 --> 00:52:07,720
Tiel look-- maldekstren
duono estas jam ordo.

1118
00:52:07,720 --> 00:52:14,165
>> Nun ĝi estas ordigado la dekstra duono, kaj
nun ĝi tuj kombini ilin en unu.

1119
00:52:14,165 --> 00:52:19,160
Tio estas iu nomita "Gnome varo."

1120
00:52:19,160 --> 00:52:23,460
Kaj vi povas ia vidi ke
ĝi tuj reen,

1121
00:52:23,460 --> 00:52:27,950
fiksinte laboro iomete tie kaj
tie antaŭ ĝi procedas al nova laboro.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Kaj tio estas ĝi.

1124
00:52:33,692 --> 00:52:36,400
Ekzistas alia speco, kiu estas
vere nur por akademiaj celoj,

1125
00:52:36,400 --> 00:52:40,980
nomita "stulta speco", kiu prenas
viajn datumojn, ordigas ŝin hazarde,

1126
00:52:40,980 --> 00:52:43,350
kaj tiam kontrolas se estas ordigitaj.

1127
00:52:43,350 --> 00:52:47,880
Kaj se ne, ĝi re-ordigas ŝin
hazarde, kontrolas se ĝi estas ordo,

1128
00:52:47,880 --> 00:52:49,440
kaj se ne ripetas.

1129
00:52:49,440 --> 00:52:52,660
Kaj en teorio, _probabilistically_
tio kompletigos,

1130
00:52:52,660 --> 00:52:54,140
sed post tre iom de tempo.

1131
00:52:54,140 --> 00:52:56,930
Ĝi ne estas la plej
eficiente de algoritmoj.

1132
00:52:56,930 --> 00:53:02,550
Tiel demandojn sur tiuj
aparta algoritmoj aŭ io

1133
00:53:02,550 --> 00:53:04,720
rilata tie ankaŭ?

1134
00:53:04,720 --> 00:53:09,430
>> Nu, ni nun turmentus aparte kion ĉiuj
tiuj linioj estas ke mi estis tiranta

1135
00:53:09,430 --> 00:53:15,090
kaj kion mi supozas la komputilo
povas fari sub la kapuĉo.

1136
00:53:15,090 --> 00:53:18,650
Mi argumentus ke ĉiuj tiuj nombroj
Mi daŭre drawing-- ili bezonos akiri

1137
00:53:18,650 --> 00:53:21,330
stokitaj ie en memoro.

1138
00:53:21,330 --> 00:53:24,130
Ni forigi ĉi ulo nun, tro.

1139
00:53:24,130 --> 00:53:30,110
>> Do pecon de memoro en
computer-- tiel RAM DIMM estas

1140
00:53:30,110 --> 00:53:35,480
kion ni serĉis hieraŭ, duala
inline memoro module-- aspektas jene.

1141
00:53:35,480 --> 00:53:39,370
Kaj ĉiu el tiuj malgrandaj nigraj pecetoj
estas iu nombro da bajtoj, tipe.

1142
00:53:39,370 --> 00:53:44,380
Kaj tiam la oro pingloj estas kiel la
dratoj kiuj konektas ĝin al la komputilo,

1143
00:53:44,380 --> 00:53:47,521
kaj la verda silicon estraro estas nur
kio tenas ĉiun ĉiuj kune.

1144
00:53:47,521 --> 00:53:48,770
Do kion signifas tio vere signifas?

1145
00:53:48,770 --> 00:53:53,180
Se mi specon de desegni ĉi tiu bildo,
ni supozu por simpleco

1146
00:53:53,180 --> 00:53:55,280
ke DIMM, duala
inline memoro modulo,

1147
00:53:55,280 --> 00:54:00,530
Estas unu gigabajto de RAM, unu gigabajto de
memoro, kiu estas kiom da bitokoj entute?

1148
00:54:00,530 --> 00:54:02,100
Unu gigabajto estas kiom da bitokoj?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Pli ol tio.

1151
00:54:06,030 --> 00:54:09,960
1,124 estas kilogramo, 1.000.

1152
00:54:09,960 --> 00:54:11,730
Mega estas miliono.

1153
00:54:11,730 --> 00:54:14,570
Giga estas miliardo.

1154
00:54:14,570 --> 00:54:15,070
>> Ĉu mi mensogis?

1155
00:54:15,070 --> 00:54:16,670
Ni povas eĉ legi la etikedon?

1156
00:54:16,670 --> 00:54:19,920
Tiu estas fakte 128
gigabajtoj, do estas pli.

1157
00:54:19,920 --> 00:54:22,130
Sed ni ŝajnigi ĉi
Estas nur unu gigabajto.

1158
00:54:22,130 --> 00:54:25,640
Do tio signifas ke estas miliardoj
bajtoj de memoro havebla al mi

1159
00:54:25,640 --> 00:54:29,770
aŭ 8 miliardoj bitoj, sed ni iras
paroli en terminoj de bajtoj nun,

1160
00:54:29,770 --> 00:54:30,750
movanta antaŭen.

1161
00:54:30,750 --> 00:54:36,330
>> Do kion tio signifas estas tio
unu bajto, ĉi tio estas alia bajto,

1162
00:54:36,330 --> 00:54:38,680
tiu estas alia bajto,
kaj se ni vere volis

1163
00:54:38,680 --> 00:54:43,280
esti specifa ni devus
desegni miliardoj iom kvadratoj.

1164
00:54:43,280 --> 00:54:44,320
Sed kion tio signifas?

1165
00:54:44,320 --> 00:54:46,420
Nu, lasu min nur zomi
en sur ĉi tiu bildo.

1166
00:54:46,420 --> 00:54:50,900
Se mi havas iun kiu aspektas
tiel nun, jen kvar bajtoj.

1167
00:54:50,900 --> 00:54:53,710
>> Kaj tiel mi povis meti kvar numerojn tie.

1168
00:54:53,710 --> 00:54:54,990
Unu, du, tri, kvar.

1169
00:54:54,990 --> 00:55:00,170
Aŭ mi povus meti kvar literojn aŭ simboloj.

1170
00:55:00,170 --> 00:55:02,620
"Hej!" povus iri rekte tie,
ĉar ĉiu de la literoj,

1171
00:55:02,620 --> 00:55:04,370
ni diskutis pli frua,
povus esti reprezentata

1172
00:55:04,370 --> 00:55:06,650
kun ok bitoj aŭ ASCII aŭ bajto.

1173
00:55:06,650 --> 00:55:09,370
Do alivorte, vi povas
metis 8 miliardoj aferojn interne

1174
00:55:09,370 --> 00:55:11,137
de ĉi tiu bastono de memoro.

1175
00:55:11,137 --> 00:55:14,345
Kion tio signifas meti aferojn reen
malantaŭeniri por malantaŭeniri en memoro tiel?

1176
00:55:14,345 --> 00:55:17,330
Jen kion programisto
nomus "tabelo".

1177
00:55:17,330 --> 00:55:21,250
En komputila programo, vi ne kredas
pri la subkuŝanta aparataro, en si mem.

1178
00:55:21,250 --> 00:55:24,427
Vi nur pensu pri vi mem kiel havado
aliro al miliardoj bajtoj Entute

1179
00:55:24,427 --> 00:55:26,010
kaj vi povas ion vi volas kun ĝi.

1180
00:55:26,010 --> 00:55:27,880
Sed pro konveneco
ĝi estas ĝenerale utila

1181
00:55:27,880 --> 00:55:31,202
teni vian memoron dekstra
apud la alia tiel.

1182
00:55:31,202 --> 00:55:33,660
Do se mi zomi en sur this--
ĉar ni ja ne iras

1183
00:55:33,660 --> 00:55:39,310
desegni miliardoj iom squares--
ni supozu ke tiu tabulo reprezentas

1184
00:55:39,310 --> 00:55:40,610
ke bastono de memoro nun.

1185
00:55:40,610 --> 00:55:43,800
Kaj mi nur tiri nekredeblaj mia
markilo finas donante min ĉi tie.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Do nun ni havas bastono
de memoro sur la tabulo

1188
00:55:52,300 --> 00:55:56,400
ke estas atingis unu, du, tri, kvar, kvin,
ses, unu, du, tri, kvar, kvin, ses,

1189
00:55:56,400 --> 00:56:01,130
seven-- do 42 bajtoj de
memoro sur la ekrano entute.

1190
00:56:01,130 --> 00:56:01,630
Dankon.

1191
00:56:01,630 --> 00:56:02,838
Jes, ĉu mia aritmetiko dekstra.

1192
00:56:02,838 --> 00:56:05,120
Do 42 bajtoj de memoro tie.

1193
00:56:05,120 --> 00:56:06,660
Do kion signifas ĉi reale signifas?

1194
00:56:06,660 --> 00:56:09,830
Nu, komputilprogramisto
ĉu vere ĝenerale

1195
00:56:09,830 --> 00:56:12,450
pensi pri tiu memoro direccionable.

1196
00:56:12,450 --> 00:56:16,630
Alivorte, ĉiu el tiuj
lokoj en memoro, en aparataro,

1197
00:56:16,630 --> 00:56:18,030
havas unikan adreson.

1198
00:56:18,030 --> 00:56:22,020
>> Ĝi ne estas tiel kompleksa kiel Unu Brattle
Kvadrata, Kembriĝo, Meso., 02138.

1199
00:56:22,020 --> 00:56:23,830
Anstataŭe, ĝi estas nur nombro.

1200
00:56:23,830 --> 00:56:27,930
Tiu estas bajto nombro nulo, ĉi tiu estas
unu, jen du, jen tri,

1201
00:56:27,930 --> 00:56:30,327
kaj tio estas 41.

1202
00:56:30,327 --> 00:56:30,910
Atendu minuton.

1203
00:56:30,910 --> 00:56:32,510
Mi pensis, ke mi diris 42 antaŭ momento.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Mi komencis rakonti al nulo,
do tio estas vere ĝentilaj.

1206
00:56:37,772 --> 00:56:40,980
Nun ni ne devas reale desegni ĝin
kiel krado, kaj se vi tiros gxin kiel krado

1207
00:56:40,980 --> 00:56:43,520
Mi pensas aferojn reale
akiri iom iluzia.

1208
00:56:43,520 --> 00:56:46,650
Kio programisto volas;
en sia propra menso,

1209
00:56:46,650 --> 00:56:50,310
ĝenerale opinias pri tio
memoro kiel estas ĝuste kiel bendo,

1210
00:56:50,310 --> 00:56:53,340
Kiel peco de maskante bendo
ke nur daŭras por ĉiam

1211
00:56:53,340 --> 00:56:54,980
aŭ ĝis vi elĉerpas de memoro.

1212
00:56:54,980 --> 00:56:59,200
Tiom pli komuna maniero tiri
kaj nur pensas pri memoro

1213
00:56:59,200 --> 00:57:03,710
estus tiu ĉi estas bajto nulo, unu,
du, tri, kaj poste pentras, punkto, ĝi pentras.

1214
00:57:03,710 --> 00:57:07,650
Kaj vi havas 42 tiajn bajtoj entute, eĉ
kvankam fizike ĝi povus reale

1215
00:57:07,650 --> 00:57:09,480
esti io pli da kiel tio.

1216
00:57:09,480 --> 00:57:12,850
>> Do se vi nun opinias pri via
memoro kiel tiu, kiel bendo,

1217
00:57:12,850 --> 00:57:17,640
jen kion programisto denove
vokus tabelo de memoro.

1218
00:57:17,640 --> 00:57:20,660
Kaj kiam vi volas reale stoki
io en komputila memoro,

1219
00:57:20,660 --> 00:57:23,290
vi ĝenerale faras vendejo aferoj
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Do ni parolis pri nombroj.

1221
00:57:25,010 --> 00:57:30,880
Kaj kiam mi volis solvi problemoj
kiel kvar, unu, tri, du,

1222
00:57:30,880 --> 00:57:33,820
kvankam mi estis nur desegnante
nur la nombroj kvar, unu, tri,

1223
00:57:33,820 --> 00:57:39,490
du sur la tabulo, la komputilo estus
vere havas ĉi aranĝo en memoro.

1224
00:57:39,490 --> 00:57:43,347
>> Kaj kio estus apud la
du en la komputilo la memoro?

1225
00:57:43,347 --> 00:57:44,680
Nu, ne estas respondo al tiu.

1226
00:57:44,680 --> 00:57:45,770
Ni ne vere scias.

1227
00:57:45,770 --> 00:57:48,200
Kaj tiel longe kiel la
komputilo ne bezonas ĝin,

1228
00:57:48,200 --> 00:57:51,440
ĝi ne devas zorgi kio estas proksima
la nombroj jes prizorgo pri.

1229
00:57:51,440 --> 00:57:55,130
Kaj kiam mi diris antaŭe ke komputilo
povas nur rigardi unu Adreso samtempe,

1230
00:57:55,130 --> 00:57:56,170
tio estas speco de kio.

1231
00:57:56,170 --> 00:57:59,490
>> Ne malsimile al rekordo
ludanto kaj legado kapo

1232
00:57:59,490 --> 00:58:03,030
nur povante rigardi certa
sulko en fizika malnova lernejo rekordo

1233
00:58:03,030 --> 00:58:06,500
samtempe, simile
povas komputilo danke

1234
00:58:06,500 --> 00:58:09,810
lia CPU kaj lia
Intel instrukciaro,

1235
00:58:09,810 --> 00:58:12,480
inter kies instrukcioj
legas de memoro

1236
00:58:12,480 --> 00:58:15,590
aŭ savi al memory-- a
komputilo povas nur rigardi

1237
00:58:15,590 --> 00:58:19,210
ĉe unu loko je time--
kelkfoje kombino de ili,

1238
00:58:19,210 --> 00:58:21,770
sed vere nur unu loko samtempe.

1239
00:58:21,770 --> 00:58:24,770
Do kiam ni faris
tiuj diversaj algoritmoj,

1240
00:58:24,770 --> 00:58:28,110
Mi ne nur skribis en
vacuum-- kvar, unu, tri, du.

1241
00:58:28,110 --> 00:58:30,849
Tiuj nombroj reale aparteni
ie fizika en memoro.

1242
00:58:30,849 --> 00:58:32,890
Do estas eta
transistoroj aŭ ian

1243
00:58:32,890 --> 00:58:35,840
de elektroniko sub la
kapuĉo stokante tiujn valorojn.

1244
00:58:35,840 --> 00:58:40,460
>> Kaj entute, kiom da bitoj estas
implikita nun, nur por esti klara?

1245
00:58:40,460 --> 00:58:45,580
Do tiu estas kvar bajtoj, aŭ
nun ĝi estas 32 bitoj entute.

1246
00:58:45,580 --> 00:58:49,280
Do estas fakte 32 nuloj kaj
tiuj formas tiujn kvar aferojn.

1247
00:58:49,280 --> 00:58:52,070
Ekzistas eĉ pli tie, sed
denove ni ne zorgas pri tio.

1248
00:58:52,070 --> 00:58:55,120
>> Do nun ni demandas alia
demandon uzanta memoro,

1249
00:58:55,120 --> 00:58:57,519
ĉar fine
de la tago estas en varianco.

1250
00:58:57,519 --> 00:59:00,310
Negrave kion ni povus fari kun
la komputilo, fine de la tago

1251
00:59:00,310 --> 00:59:02,560
la aparataro estas ankoraŭ la
sama sub la kapuĉo.

1252
00:59:02,560 --> 00:59:04,670
Kiel mi stoki vorto en tie?

1253
00:59:04,670 --> 00:59:09,710
Nu, vorto en komputilo kiel
"Hey!" estus stokitaj samkiel ĉi.

1254
00:59:09,710 --> 00:59:12,300
Kaj se vi volas pli longa
vorto, vi povas simple

1255
00:59:12,300 --> 00:59:19,120
anstataŭigi tion kaj diri ion
kiel "saluton" kaj provizoj, kiujn tie.

1256
00:59:19,120 --> 00:59:23,930
>> Kaj tiel ankaŭ ĉi tiu contiguousness
fakte avantaĝo,

1257
00:59:23,930 --> 00:59:26,530
ĉar komputilo povas nur
legi de dekstre maldekstren.

1258
00:59:26,530 --> 00:59:28,680
Sed jen demando.

1259
00:59:28,680 --> 00:59:33,480
En la kunteksto de tiu vorto,
h-kaj-l-l-o, ekkrion punkto,

1260
00:59:33,480 --> 00:59:38,740
kiel povus la komputilo scias kie
vorto komencas kaj kie la vorto finiĝas?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
En la kunteksto de nombroj,
kiel faras la komputilo

1263
00:59:43,800 --> 00:59:48,396
scias kiom longe la sekvencon de
nombroj estas aŭ kie komencas?

1264
00:59:48,396 --> 00:59:50,270
Nu, tio rezultas fjordon
kaj ni ne iru tro multe

1265
00:59:50,270 --> 00:59:54,970
en tiu nivelo de detail--
komputiloj movi aĵojn ĉirkaŭe en memoro

1266
00:59:54,970 --> 00:59:57,800
laŭvorte tra tiuj adresoj.

1267
00:59:57,800 --> 01:00:02,080
Tiel en komputilo, se vi estas
skribi kodon por stoki aferojn

1268
01:00:02,080 --> 01:00:05,800
kiel vortoj, kion vi
vere faras estas tajpanta

1269
01:00:05,800 --> 01:00:11,320
esprimoj kiuj memoras kie en
la komputilo la memoro tiuj vortoj estas.

1270
01:00:11,320 --> 01:00:14,370
Do lasu min fari tre,
tre simpla ekzemplo.

1271
01:00:14,370 --> 01:00:18,260
>> Mi tuj iros antaŭen kaj
malfermu simpla teksto programo,

1272
01:00:18,260 --> 01:00:20,330
kaj mi tuj kreos
dosiero nomata hello.c.

1273
01:00:20,330 --> 01:00:22,849
Plej el tiu informo ni
ne eniros en granda detalo,

1274
01:00:22,849 --> 01:00:25,140
sed mi tuj skribos
programo en tiu sama lingvo,

1275
01:00:25,140 --> 01:00:31,140
C. Jen nun pli timiganta,
Mi argumentas, ke Scratch,

1276
01:00:31,140 --> 01:00:32,490
sed estas tre simila en spirito.

1277
01:00:32,490 --> 01:00:34,364
Fakte, tiuj buklaj
braces-- vi povas ia

1278
01:00:34,364 --> 01:00:37,820
elpensi kion mi ĵus faris, kiel tiu.

1279
01:00:37,820 --> 01:00:39,240
>> Ni faru tion, fakte.

1280
01:00:39,240 --> 01:00:45,100
Kiam verda flago clicked,
fari la sekvan.

1281
01:00:45,100 --> 01:00:50,210
Mi volas presi "saluton."

1282
01:00:50,210 --> 01:00:51,500
Do tiu estas nun _pseudocode_.

1283
01:00:51,500 --> 01:00:53,000
Mi ia neklara la linioj.

1284
01:00:53,000 --> 01:00:56,750
En C, tiu lingvo mi parolas
pri tiu linio presita saluton

1285
01:00:56,750 --> 01:01:01,940
fakte fariĝas "printf" kun
iuj krampoj kaj semi-dupunkto.

1286
01:01:01,940 --> 01:01:03,480
>> Sed ĝi estas la ĝusta sama ideo.

1287
01:01:03,480 --> 01:01:06,730
Kaj tiu tre uzantamika
"Kiam verda flago klakis" iĝas

1288
01:01:06,730 --> 01:01:10,182
la multe pli arcano "int ĉefa malplenon."

1289
01:01:10,182 --> 01:01:12,890
Kaj tio vere havas nenian surĵeto,
do mi simple tuj ignori tion.

1290
01:01:12,890 --> 01:01:17,210
Sed la krispa krampoj estas kiel la
kurba puzlo pecoj kiel ĉi.

1291
01:01:17,210 --> 01:01:18,700
>> Do vi povas ia diveni.

1292
01:01:18,700 --> 01:01:22,357
Eĉ se vi neniam planita antaŭe,
kion tiu programo probable faros?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Probable presas saluton
kun krio punkto.

1295
01:01:28,000 --> 01:01:29,150
>> Do ni provu tion.

1296
01:01:29,150 --> 01:01:30,800
Mi tuj savos.

1297
01:01:30,800 --> 01:01:34,000
Kaj tio estas, denove, tre
malnova lernejo medio.

1298
01:01:34,000 --> 01:01:35,420
Mi ne povas klaki, mi ne povas treni.

1299
01:01:35,420 --> 01:01:36,910
Mi devas tajpi komandojn.

1300
01:01:36,910 --> 01:01:41,320
Do mi volas kuri mia programo, do
Mi povus fari tion, kiel hello.c.

1301
01:01:41,320 --> 01:01:42,292
Jen la dosieron mi kuris.

1302
01:01:42,292 --> 01:01:43,500
Sed atendu, mi mankas paŝo.

1303
01:01:43,500 --> 01:01:46,470
Kion ni diras estas necesa
paŝi por lingvo kiel C?

1304
01:01:46,470 --> 01:01:49,470
Mi ĵus skribis fonto
kodo, sed kion mi bezonas?

1305
01:01:49,470 --> 01:01:50,670
Yeah, Mi bezonas tradukilon.

1306
01:01:50,670 --> 01:01:57,670
Tiel sur mia Mac ĉi tie, mi havas
programo nomita GCC, GNU C kompililo,

1307
01:01:57,670 --> 01:02:03,990
kiu min permesas fari this-- victurno
mia fontkodon en, ni nomas ĝin,

1308
01:02:03,990 --> 01:02:04,930
maŝino kodo.

1309
01:02:04,930 --> 01:02:10,180
>> Kaj mi povas vidi ke,
denove, kiel sekvas, tiuj

1310
01:02:10,180 --> 01:02:14,090
estas la nuloj kaj mi ĵus
kreita de mia fontkodon,

1311
01:02:14,090 --> 01:02:15,730
ĉiuj nuloj kaj aĵoj.

1312
01:02:15,730 --> 01:02:17,770
Kaj se mi volas kuri
mia program-- okazas

1313
01:02:17,770 --> 01:02:23,010
esti nomata a.out por
historia reasons-- "saluton."

1314
01:02:23,010 --> 01:02:24,070
Mi povas kuri ĝin denove.

1315
01:02:24,070 --> 01:02:25,690
Saluton, saluton, saluton.

1316
01:02:25,690 --> 01:02:27,430
Kaj ŝajnas esti laborante.

1317
01:02:27,430 --> 01:02:31,000
>> Sed tio signifas ie en mia
komputilo la memoro estas la vortoj

1318
01:02:31,000 --> 01:02:35,279
h-kaj-l-l-o, ekkrion punkto.

1319
01:02:35,279 --> 01:02:38,070
Kaj ĝi rezultas, kiel flanken,
kion komputilo volus tipe

1320
01:02:38,070 --> 01:02:40,550
fari por ke ĝi scias kie
aĵoj komencas kaj end-- estas

1321
01:02:40,550 --> 01:02:42,460
tuj metos specialan simbolon tie.

1322
01:02:42,460 --> 01:02:46,064
Kaj la konvencio estas meti la
nombro nulo je la fino de vorto

1323
01:02:46,064 --> 01:02:48,230
por ke vi sciu kie
fakte finas, por ke vi

1324
01:02:48,230 --> 01:02:52,750
ne malhelpu presi el pli kaj pli
karakteroj ol vi efektive intencas.

1325
01:02:52,750 --> 01:02:55,400
>> Sed la takeaway tie, eĉ
kvankam tiu estas sufiĉe arcane,

1326
01:02:55,400 --> 01:02:58,140
estas ke ĝi estas finfine
relative simpla.

1327
01:02:58,140 --> 01:03:04,550
Vi ricevis ian bendo, malplenan
spaco sur kiu vi povas skribi leterojn.

1328
01:03:04,550 --> 01:03:07,150
Vi simple devas havi
speciala simbolo, kiel arbitre

1329
01:03:07,150 --> 01:03:10,316
la nombro nulo, meti je la fino de
viajn vortojn tiel ke la komputilo scias,

1330
01:03:10,316 --> 01:03:13,410
ho, mi devas halti impreso post
Mi vidas la ekkrio punkto.

1331
01:03:13,410 --> 01:03:16,090
Ĉar la sekva afero tie
Estas ASCII valoro de nulo,

1332
01:03:16,090 --> 01:03:19,125
aŭ la nula karaktero
iu nomus ĝin.

1333
01:03:19,125 --> 01:03:21,500
Sed estas ia problemo
tie, kaj ni restarigu reen

1334
01:03:21,500 --> 01:03:23,320
al nombroj momente.

1335
01:03:23,320 --> 01:03:28,720
Supozi ke mi faras, fakte,
havas tabelo de nombroj,

1336
01:03:28,720 --> 01:03:30,730
kaj supozu ke la
programo mi skribas estas

1337
01:03:30,730 --> 01:03:34,680
kiel grado libro por instruisto
kaj instruistojn klasĉambro.

1338
01:03:34,680 --> 01:03:38,720
Kaj ĉi programo ebligas al li aŭ ŝi
tajpi en siaj studentaj partituroj

1339
01:03:38,720 --> 01:03:39,960
sur kvizojn.

1340
01:03:39,960 --> 01:03:43,750
Kaj supozu ke la studento ricevas
100 en lia unua kvizo, eble

1341
01:03:43,750 --> 01:03:49,920
kiel 80 sur la sekvanta unu, tiam
75, tiam 90 sur la kvara kvizo.

1342
01:03:49,920 --> 01:03:54,150
>> Do je ĉi tiu punkto en la rakonto,
la tabelo estas de amplekso kvar.

1343
01:03:54,150 --> 01:03:58,470
Ekzistas absolute pli memoro en la
komputilo, sed la tabelo, por tiel diri,

1344
01:03:58,470 --> 01:04:00,350
Estas de grandeco kvar.

1345
01:04:00,350 --> 01:04:06,060
Supozu nun ke la instruisto volas
atribui kvina kvizo al la klaso.

1346
01:04:06,060 --> 01:04:08,510
Nu, unu el la aĵoj li
aŭ ŝi tuj devas fari

1347
01:04:08,510 --> 01:04:10,650
nun stoki kroman valoron tie.

1348
01:04:10,650 --> 01:04:15,490
Sed se la tabelo la instruisto havas
kreitaj en tiu programo estas de grandeco por,

1349
01:04:15,490 --> 01:04:22,440
unu el la problemo kun tabelo estas ke
Vi ne povas simple observu aldonante al memoro.

1350
01:04:22,440 --> 01:04:26,470
Ĉar se alia parto de la
programo havas la vorton "hey" Dekstre?

1351
01:04:26,470 --> 01:04:29,650
>> Alivorte, mian memoron povas esti
uzata por io en programo.

1352
01:04:29,650 --> 01:04:33,250
Kaj se anticipe mi tajpita en, hej,
Mi volas enigi kvar kvizo partituroj,

1353
01:04:33,250 --> 01:04:34,784
ili povus iri tien kaj tien.

1354
01:04:34,784 --> 01:04:37,700
Kaj se vi subite ŝanĝas vian menson
poste kaj diru mi volas kvinan kvizo

1355
01:04:37,700 --> 01:04:40,872
partituro, vi ne povas simple
metis ĝin kie ajn vi volas,

1356
01:04:40,872 --> 01:04:42,580
ĉar se ĉi
memoro estas uzata

1357
01:04:42,580 --> 01:04:45,990
ion else-- alian programon
aŭ alian karakterizaĵon de la programo

1358
01:04:45,990 --> 01:04:46,910
ke vi uzas?

1359
01:04:46,910 --> 01:04:50,650
Do vi devas pensi anticipe
kiom vi volas konservi viajn datumojn,

1360
01:04:50,650 --> 01:04:54,480
ĉar nun vi pentris
vin en cifereca angulo.

1361
01:04:54,480 --> 01:04:57,280
>> Do instruisto povus anstataŭe
diru kiam skribanta programon

1362
01:04:57,280 --> 01:04:59,360
stoki siajn
gradoj, vi scias kion?

1363
01:04:59,360 --> 01:05:04,180
Mi intencas peti,
kiam skribanta mian programon,

1364
01:05:04,180 --> 01:05:12,070
ke mi volas nulo, unu, du, tri,
kvar, kvin, ses, ok gradoj entute.

1365
01:05:12,070 --> 01:05:15,320
Do unu, du, tri, kvar,
kvin, ses, sep, ok.

1366
01:05:15,320 --> 01:05:18,612
La instruisto povas nur tro asigni
memoro verkante sian programon

1367
01:05:18,612 --> 01:05:19,570
kaj diri, vi scias kion?

1368
01:05:19,570 --> 01:05:22,236
Mi neniam tuj asigni pli
ol ok kvizojn en sesmonato.

1369
01:05:22,236 --> 01:05:23,130
Tio estas nur freneza.

1370
01:05:23,130 --> 01:05:24,470
Mi neniam rezervu tion.

1371
01:05:24,470 --> 01:05:28,270
Por ke tiel li aŭ ŝi havas la
fleksebleco vendejo studento partituroj,

1372
01:05:28,270 --> 01:05:33,010
kiel 75, 90, kaj eble unu ekstra kie
la studento akiris kroman krediton, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Sed se la instruisto neniam
uzas tiujn tri spacoj,

1374
01:05:36,130 --> 01:05:38,860
ekzistas intuicia takeaway tie.

1375
01:05:38,860 --> 01:05:41,410
Li aŭ ŝi estas nur malŝparanta spaco.

1376
01:05:41,410 --> 01:05:44,790
Do alivorte, ne estas tio
komuna tradeoff en programado

1377
01:05:44,790 --> 01:05:48,241
kie vi povas aŭ asigni
ĝuste tiel memoro kiel vi volas,

1378
01:05:48,241 --> 01:05:51,490
la supra parto de kiu estas ke vi estas súper
efficient-- vi ne malŝparema

1379
01:05:51,490 --> 01:05:54,640
ĉe all-- sed la malavantaĝo de kiu
Estas kio se vi ŝanĝas vian menson kiam

1380
01:05:54,640 --> 01:05:58,780
uzante la programo ke vi volas konservi
pli datumoj ol vi originale celis.

1381
01:05:58,780 --> 01:06:03,030
>> Do eble la solvo estas, ĉar,
skribi viajn programojn en tia vojo

1382
01:06:03,030 --> 01:06:05,605
ke ili uzas pli da memoro
ol ili vere bezonas.

1383
01:06:05,605 --> 01:06:07,730
Tiel vi ne tuj
kolizii tiu problemo,

1384
01:06:07,730 --> 01:06:09,730
sed vi estis malŝparema.

1385
01:06:09,730 --> 01:06:12,960
Kaj la pli memoro via programo uzas,
kiel ni diskutis hieraŭ, la malpli

1386
01:06:12,960 --> 01:06:15,410
memoro kiu estas disponeblaj
por aliaj programoj,

1387
01:06:15,410 --> 01:06:18,790
ju pli baldaŭ via komputilo povus malrapidigi
malsupren pro virtuala memoro.

1388
01:06:18,790 --> 01:06:22,670
Kaj tiel la ideala solvo povus esti kio?

1389
01:06:22,670 --> 01:06:24,610
>> Sub-atribuo ŝajnas malbona.

1390
01:06:24,610 --> 01:06:27,030
Super-atribuo ŝajnas malbona.

1391
01:06:27,030 --> 01:06:31,120
Do kio povus esti pli bona solvo?

1392
01:06:31,120 --> 01:06:32,390
Reallocating.

1393
01:06:32,390 --> 01:06:33,590
Esti pli dinamika.

1394
01:06:33,590 --> 01:06:37,520
Ne perfortu vin al elekti
priori, komence, kion vi volas.

1395
01:06:37,520 --> 01:06:41,370
Kaj certe ne tro atribui,
ke vi estu malŝparema.

1396
01:06:41,370 --> 01:06:45,770
>> Kaj tiel atingi tiun celon, ni
bezonas ĵeti ĉi datumstrukturo,

1397
01:06:45,770 --> 01:06:48,100
tiel diri, sin.

1398
01:06:48,100 --> 01:06:51,080
Kaj tiel kion programisto
tipe uzas

1399
01:06:51,080 --> 01:06:55,940
Estas io nomata ne
tabelo sed ligillisto.

1400
01:06:55,940 --> 01:07:00,860
Alivorte, li aŭ ŝi volas
komenci pensi pri ilia memoro

1401
01:07:00,860 --> 01:07:05,280
kiel esti speco de formo ke ili
povas desegni en la sekvanta maniero.

1402
01:07:05,280 --> 01:07:08,520
Se mi volas konservi unu numeron en
oni program-- do estas septembro,

1403
01:07:08,520 --> 01:07:12,600
Mi donis mian studentoj kvizon; mi volas
stoki la studentaj unua kvizo

1404
01:07:12,600 --> 01:07:16,220
kaj ili ricevis 100 sur it-- mi
iras por peti mian komputilon,

1405
01:07:16,220 --> 01:07:19,540
tra la programo mi havas
skribita, unu eron de memoro.

1406
01:07:19,540 --> 01:07:22,570
Kaj mi tuj stoki la
numero 100 en ĝi, kaj tio estas ĝi.

1407
01:07:22,570 --> 01:07:24,820
>> Tiam kelkajn semajnojn poste
kiam mi akiras miajn dua kvizo,

1408
01:07:24,820 --> 01:07:27,890
kaj ĝi estas tempo por tajpi
en tiu 90%, mi iras

1409
01:07:27,890 --> 01:07:32,129
demandi la komputilo, hej, Komputilo,
mi havas alian eron de memoro?

1410
01:07:32,129 --> 01:07:34,170
Ĝi tuj donu al mi tiun
malplena eron de memoro.

1411
01:07:34,170 --> 01:07:39,370
Mi tuj metis en la numero 90,
sed en mian programon iel aŭ alia lando

1412
01:07:39,370 --> 01:07:42,100
kaj ni ne zorgu pri
la sintakso por this-- mi bezonas

1413
01:07:42,100 --> 01:07:44,430
iel ĉenas tion kune.

1414
01:07:44,430 --> 01:07:47,430
Kaj mi ĉenas ilin kune kun
kio aspektas kiel sago tie.

1415
01:07:47,430 --> 01:07:50,050
>> La tria kvizo venintan,
Mi tuj diru, hej, Komputilo,

1416
01:07:50,050 --> 01:07:51,680
donu al mi alian eron de memoro.

1417
01:07:51,680 --> 01:07:54,660
Kaj mi tuj metis malsupren
kio ajn ĝi estis, kiel 75,

1418
01:07:54,660 --> 01:07:56,920
kaj mi havas ĉeni tiun
kune nun iel.

1419
01:07:56,920 --> 01:08:00,290
Kvara kvizo venas kune, kaj eble
jen al la fino de la semestro.

1420
01:08:00,290 --> 01:08:03,140
Kaj de tiu punkto mia programo
povus esti uzante memoro

1421
01:08:03,140 --> 01:08:05,540
ĉie, ĉie fizike.

1422
01:08:05,540 --> 01:08:08,170
Kaj tiel nur por piedbatoj, mi estas
tuj tiri tiun antaŭen

1423
01:08:08,170 --> 01:08:11,260
quiz-- Mi forgesas, kio gxi; mi
pensas eble 80 aŭ something--

1424
01:08:11,260 --> 01:08:12,500
vojo ĉi tien.

1425
01:08:12,500 --> 01:08:15,920
>> Sed tio estas bone, ĉar bilde
Mi tuj tiri tiun linion.

1426
01:08:15,920 --> 01:08:19,063
Alivorte, en realo,
en via komputilo aparataro,

1427
01:08:19,063 --> 01:08:20,979
la unua partituro povus
finas tie ĉar ĝi estas

1428
01:08:20,979 --> 01:08:22,529
ĝuste en la komenco de la semestro.

1429
01:08:22,529 --> 01:08:25,810
La venonta unu povus fini tie
ĉar iom da tempo pasis

1430
01:08:25,810 --> 01:08:27,210
kaj la programo subtenas kurante.

1431
01:08:27,210 --> 01:08:30,060
La sekva poentaro, kiu estis
75, povus esti ĉi tie.

1432
01:08:30,060 --> 01:08:33,420
Kaj la lasta partituro povus esti
80, kiu estas tie.

1433
01:08:33,420 --> 01:08:38,729
>> Do fakte, fizike, tiu povus esti
kion via komputilo la memoro aspektas.

1434
01:08:38,729 --> 01:08:41,569
Sed tio ne estas utila mensa
paradigmo por komputila programisto.

1435
01:08:41,569 --> 01:08:44,649
Kial vi zorgas kie la
heck viajn datumojn estas fini?

1436
01:08:44,649 --> 01:08:46,200
Vi nur volas konservi datumoj.

1437
01:08:46,200 --> 01:08:49,390
>> Tiu estas speco de kiel nia diskuto
fruaj tiri la kubo.

1438
01:08:49,390 --> 01:08:52,200
Kial vi zorgas kia
la angulo estas de la kubo

1439
01:08:52,200 --> 01:08:53,740
kaj kiel vi devas turni al desegni ĝin?

1440
01:08:53,740 --> 01:08:54,950
Vi nur volas kubo.

1441
01:08:54,950 --> 01:08:57,359
Simile tie, vi
Nur volas lernojaro libron.

1442
01:08:57,359 --> 01:08:59,559
Vi nur volas pensi
tiu kiel listo de nombroj.

1443
01:08:59,559 --> 01:09:01,350
Kiu zorgas kiom ĝi estas
implementado en aparataro?

1444
01:09:01,350 --> 01:09:05,180
>> Tiel la abstracción nun
estas ĉi tiu bildo ĉi tie.

1445
01:09:05,180 --> 01:09:07,580
Tio estas ligillisto, kiel
programisto nomus ĝin,

1446
01:09:07,580 --> 01:09:10,640
mezuro vi havas
listo, evidente de nombroj.

1447
01:09:10,640 --> 01:09:14,990
Sed ĝi estas ligitaj bilde
tra tiuj sagoj,

1448
01:09:14,990 --> 01:09:18,510
kaj ĉiuj tiuj sagoj are-- sub
la kapuĉo, se vi estas scivola,

1449
01:09:18,510 --> 01:09:23,210
memoras ke nia fizika aparataro havas
adresoj nulo, unu, du, tri, kvar.

1450
01:09:23,210 --> 01:09:28,465
Ĉiuj tiuj sagoj estas estas kiel mapo
aŭ direktoj, kie se 90 is-- nun

1451
01:09:28,465 --> 01:09:29,090
Mi alvenis al havi.

1452
01:09:29,090 --> 01:09:31,750
>> Nulo, unu, du, tri,
kvar, kvin, ses, sep.

1453
01:09:31,750 --> 01:09:35,640
Ĝi aspektas kiel la 90 estas ĉe
memoro Adreso numero sep.

1454
01:09:35,640 --> 01:09:38,460
Ĉiuj tiuj sagoj estas estas
kiel malgranda peceto de papero

1455
01:09:38,460 --> 01:09:42,439
kiu estas donante direktoj al la
programo kiu diras sekvi tiun mapo

1456
01:09:42,439 --> 01:09:43,880
atingi lokon sep.

1457
01:09:43,880 --> 01:09:46,680
Kaj tie vi trovos la
studento dua kvizo partituro.

1458
01:09:46,680 --> 01:09:52,100
Dume, la 75-- se mi daŭrigos ĉi,
tio estas sep, ok, naŭ, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Tiu alia sago ĵus reprezentas
mapon por memoro loko 15.

1461
01:09:59,080 --> 01:10:02,550
Sed denove, la programisto ĝenerale faras
Ne gravas pri ĉi tiu nivelo de detalo.

1462
01:10:02,550 --> 01:10:05,530
Kaj en plej ĉiu programado
lingvo hodiaŭ, la programisto

1463
01:10:05,530 --> 01:10:10,490
ne eĉ scias kie en memoro
tiuj nombroj reale estas.

1464
01:10:10,490 --> 01:10:14,830
Ĉiuj li aŭ ŝi devas zorgi pri estas
ke ili estas iel kunligitaj

1465
01:10:14,830 --> 01:10:18,390
en datumstrukturo kiel ĉi.

1466
01:10:18,390 --> 01:10:21,580
>> Sed rezultas ne
akiri tro teknika.

1467
01:10:21,580 --> 01:10:27,430
Sed nur ĉar ni povas eble
permesi havi tiun diskuton ĉi tie,

1468
01:10:27,430 --> 01:10:33,630
supozu ke ni reviziti
tiu temo ĉi tie de tabelo.

1469
01:10:33,630 --> 01:10:35,780
Ni vidu se ni bedaŭras iras tien.

1470
01:10:35,780 --> 01:10:42,950
Tio estas 100, 90, 75, kaj 80.

1471
01:10:42,950 --> 01:10:44,980
>> Lasu min mallonge klarigu aserto.

1472
01:10:44,980 --> 01:10:48,980
Jen tabelo, kaj denove, la
elstaraĵo karakteriza de tabelo

1473
01:10:48,980 --> 01:10:52,400
Estas ke ĉiuj viaj datumoj estas al
reen malantaŭeniri en memory-- laŭvorte

1474
01:10:52,400 --> 01:10:56,830
unu bajto aŭ eble kvar bajtoj,
iu fiksita nombro de bajtoj for.

1475
01:10:56,830 --> 01:11:00,710
En ligillisto, kiun ni povus tiri
tiel, sub la kapuĉo, kiu

1476
01:11:00,710 --> 01:11:02,000
scias kie tiu materialo estas?

1477
01:11:02,000 --> 01:11:03,630
Ĝi eĉ ne devas flui kiel tiu.

1478
01:11:03,630 --> 01:11:06,050
Iuj de la datumoj povus esti
reen al la maldekstra supre.

1479
01:11:06,050 --> 01:11:07,530
Vi eĉ ne scias.

1480
01:11:07,530 --> 01:11:15,430
>> Kaj tiel kun tabelo, vi havas
trajto konata kiel hazarda aliro.

1481
01:11:15,430 --> 01:11:20,570
Kaj kion hazarda aliro rimedoj estas
ke la komputilo povas salti senprokraste

1482
01:11:20,570 --> 01:11:22,730
al ajna loko en tabelo.

1483
01:11:22,730 --> 01:11:23,580
Kial?

1484
01:11:23,580 --> 01:11:26,000
Ĉar la komputilo scias
ke la unua loko estas

1485
01:11:26,000 --> 01:11:29,540
nulo, unu, du, tri.

1486
01:11:29,540 --> 01:11:33,890
>> Do se vi volas iri de
tiu elemento al la sekva elemento,

1487
01:11:33,890 --> 01:11:36,099
vi laŭvorte, en la
komputilo menso, nur aldoni unu.

1488
01:11:36,099 --> 01:11:39,140
Se vi volas iri al la tria ero,
nur aldoni one-- sekva elemento, ĝuste

1489
01:11:39,140 --> 01:11:40,290
aldoni unu.

1490
01:11:40,290 --> 01:11:42,980
Tamen, en tiu versio
de la rakonto, supozu

1491
01:11:42,980 --> 01:11:46,080
la komputilo estas nun rigardanta
ĉe aŭ pritraktas la numeron 100.

1492
01:11:46,080 --> 01:11:49,770
Kiel vi akiras la sekva
grado en la lernojaro libron?

1493
01:11:49,770 --> 01:11:52,560
>> Vi devi preni sep
ŝtupoj, kiuj estas arbitra.

1494
01:11:52,560 --> 01:11:58,120
Akiri al la sekvanta unu, Vi devi
prenu alian ok ŝtupoj por atingi 15.

1495
01:11:58,120 --> 01:12:02,250
Alivorte, ĝi ne estas
konstanta interspaco inter la numerojn,

1496
01:12:02,250 --> 01:12:04,857
kaj tiel ĝi nur prenas la
komputilo pli tempo estas la punkto.

1497
01:12:04,857 --> 01:12:06,940
La komputilo devas serĉi
tra memoro por

1498
01:12:06,940 --> 01:12:08,990
trovi kion vi estas serĉanta.

1499
01:12:08,990 --> 01:12:14,260
>> Do dum tabelo emas esti
rapida datumoj structure-- ĉar vi

1500
01:12:14,260 --> 01:12:17,610
povas laŭvorte nur fari simplan aritmetikan
kaj akiri kie vi volas aldonante unu,

1501
01:12:17,610 --> 01:12:21,300
por instance-- ligillisto,
vi oferas ke trajto.

1502
01:12:21,300 --> 01:12:24,020
Vi ne povas simple foriri de unua
por dua al tria al kvara.

1503
01:12:24,020 --> 01:12:25,240
Vi devas sekvi la mapo.

1504
01:12:25,240 --> 01:12:28,160
Vi devas preni pli paŝoj
por atingi tiujn valorojn, kiuj

1505
01:12:28,160 --> 01:12:30,230
ŝajnus esti aldonanta kosto.

1506
01:12:30,230 --> 01:12:35,910
Do ni pagas prezon, sed kio
la trajto kiu Dan sercxis tie?

1507
01:12:35,910 --> 01:12:38,110
Kion faras ligillisto
ŝajne permesas nin fari,

1508
01:12:38,110 --> 01:12:40,240
kiu estis la origino de
tiun apartan historion?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Ĝuste.

1511
01:12:43,830 --> 01:12:46,220
Dinamika grandeco al ĝi.

1512
01:12:46,220 --> 01:12:48,040
Ni povas aldoni al tiu listo.

1513
01:12:48,040 --> 01:12:51,430
Ni povas eĉ ŝrumpi la listo, do
ke ni nur uzas tiel memoro

1514
01:12:51,430 --> 01:12:55,560
kiel ni efektive volas do
ni neniam super-atribuo.

1515
01:12:55,560 --> 01:12:58,470
>> Nun nur esti vere nit-elektema,
Tie estas kaŝita kosto.

1516
01:12:58,470 --> 01:13:01,980
Do vi ne donos al mi konvinki
vi, ke tio estas konvinka tradeoff.

1517
01:13:01,980 --> 01:13:04,190
Ekzistas alia kaŝita kosto tie.

1518
01:13:04,190 --> 01:13:06,550
Profito, esti klara,
estas ke ni akiras dinamismo.

1519
01:13:06,550 --> 01:13:10,359
Se mi volas alia elemento, mi povas nur
tiros gxin kaj metis kelkajn tie.

1520
01:13:10,359 --> 01:13:12,150
Kaj tiam mi povas ligi ĝin
kun foto tie,

1521
01:13:12,150 --> 01:13:14,970
dum ĉi tie, denove, se mi havas
pentris mem en angulon,

1522
01:13:14,970 --> 01:13:19,410
se io alia estas jam uzanta
la memoro tie, mi estas el sorton.

1523
01:13:19,410 --> 01:13:21,700
Mi pentris mem en angulon.

1524
01:13:21,700 --> 01:13:24,390
>> Sed kio estas la kaŝita
kostis en tiu bildo?

1525
01:13:24,390 --> 01:13:27,690
Ĝi estas ne nur la kvanto
de tempo ke ĝi prenas

1526
01:13:27,690 --> 01:13:29,870
iri de ĉi tie al tie,
kiu estas sep ŝtupoj, ĉar

1527
01:13:29,870 --> 01:13:32,820
ok ŝtupoj, kiuj estas pli ol unu.

1528
01:13:32,820 --> 01:13:34,830
Kio alia kaŝita kosto?

1529
01:13:34,830 --> 01:13:35,440
Ne nur la tempo.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Aldona informo
necesa por atingi tiun bildon.

1532
01:13:49,940 --> 01:13:53,210
>> Yeah, ke mapo, tiuj malgrandaj pecetoj de
papero, kiel mi gardas priskribante ilin kiel.

1533
01:13:53,210 --> 01:13:55,650
Tiuj arrows-- tiuj ne estas liberaj.

1534
01:13:55,650 --> 01:13:57,660
A computer-- vi scias
kion komputilo havas.

1535
01:13:57,660 --> 01:13:58,790
Ĝi havas nuloj kaj aĵoj.

1536
01:13:58,790 --> 01:14:03,170
Se vi volas reprezenti sago aŭ
mapi aŭ nombro, vi bezonas iun memoron.

1537
01:14:03,170 --> 01:14:05,950
Do la aliaj prezo
pagi ligillisto,

1538
01:14:05,950 --> 01:14:09,070
komuna komputiko
rimedo, estas ankaŭ spaco.

1539
01:14:09,070 --> 01:14:11,710
>> Kaj ja tial, tiel ofte,
inter la tradeoffs

1540
01:14:11,710 --> 01:14:15,580
en dizajnado programado
sistemoj estas tempo kaj space--

1541
01:14:15,580 --> 01:14:18,596
Estas du de viaj ingrediencoj, du
de via plej multekostajn ingrediencojn.

1542
01:14:18,596 --> 01:14:21,220
Tio kostas min pli tempo
ĉar mi devos sekvi tiun mapon,

1543
01:14:21,220 --> 01:14:25,730
sed ĝi ankaŭ kostas min pli spaco
ĉar mi devas gardi ĉi Mapo ĉirkaŭe.

1544
01:14:25,730 --> 01:14:28,730
Do la espero, kiel ni ia
diskutis pri hieraŭ kaj hodiaŭ,

1545
01:14:28,730 --> 01:14:31,720
estas ke la profitoj
estos superpezas la kostojn.

1546
01:14:31,720 --> 01:14:33,870
>> Sed estas neniu evidenta solvo tie.

1547
01:14:33,870 --> 01:14:35,870
Eble estas better--
a la rapida kaj malpura,

1548
01:14:35,870 --> 01:14:38,660
kiel Kareem proponita earlier--
ĵeti memoro ĉe la problemon.

1549
01:14:38,660 --> 01:14:42,520
Nur aĉeti pli memoro, opinias malpli
forte pri solvi la problemon,

1550
01:14:42,520 --> 01:14:44,595
kaj solvi ĝin en facila maniero.

1551
01:14:44,595 --> 01:14:46,720
Kaj ja pli frue, kiam
ni parolis pri tradeoffs,

1552
01:14:46,720 --> 01:14:49,190
ĝi ne estis spaco en
la komputilo kaj tempo.

1553
01:14:49,190 --> 01:14:51,810
Estis programisto tempo, kiun
Estas ankoraŭ alia rimedo.

1554
01:14:51,810 --> 01:14:54,829
>> Tiom pli, ĝi estas tio ekvilibriganta ago
provas decidi kiu el tiuj aferoj

1555
01:14:54,829 --> 01:14:55,870
ĉu vi pretas elspezi?

1556
01:14:55,870 --> 01:14:57,380
Kiu estas la malplej multekosta?

1557
01:14:57,380 --> 01:15:01,040
Kiu rendimenta bonajn rezultojn?

1558
01:15:01,040 --> 01:15:01,540
Yeah?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Fakte.

1561
01:15:12,580 --> 01:15:15,970
En tiu kazo, se vi estas
reprezentantaj nombrojn en la maps--

1562
01:15:15,970 --> 01:15:18,820
tiuj estas nomitaj en multaj lingvoj
"Punteros" aŭ "adresoj" -

1563
01:15:18,820 --> 01:15:20,390
ĝi estas duobla la spaco.

1564
01:15:20,390 --> 01:15:24,390
Ke ne bezonas esti tiel malbona kiel duobla se
nun ni nur stoki nombroj.

1565
01:15:24,390 --> 01:15:27,410
Supozu ke ni stokante
paciento rekordojn en hospital--

1566
01:15:27,410 --> 01:15:30,870
tiel Pierson nomoj, telefonnumerojn,
socia sekureco nombroj, kuracisto

1567
01:15:30,870 --> 01:15:31,540
historio.

1568
01:15:31,540 --> 01:15:34,160
Tiu skatolo povu multe,
multe pli granda, en kies kazo

1569
01:15:34,160 --> 01:15:38,000
eta montrilo, la adreso de
la sekva element-- ĝi ne estas granda interkonsento.

1570
01:15:38,000 --> 01:15:40,620
Ĝi estas tia franĝo
kostis ne gravas.

1571
01:15:40,620 --> 01:15:43,210
Sed en ĉi tiu kazo, jes, ĝi estas duobligo.

1572
01:15:43,210 --> 01:15:45,290
Bona demando.

1573
01:15:45,290 --> 01:15:47,900
>> Ni parolu pri tempo
iom pli konkrete.

1574
01:15:47,900 --> 01:15:50,380
Kio estas la rula tempo
esplorrigardi tiu listo?

1575
01:15:50,380 --> 01:15:53,640
Supozu mi volis serĉi
tra ĉiuj studentoj 'kvalifikojn,

1576
01:15:53,640 --> 01:15:55,980
kaj ekzistas n gradoj
en ĉi datumstrukturo.

1577
01:15:55,980 --> 01:15:58,830
Ankaŭ tie ni povas deprunti
la vortprovizo de pli fruaj.

1578
01:15:58,830 --> 01:16:00,890
Tio estas lineara datumstrukturo.

1579
01:16:00,890 --> 01:16:04,570
>> Granda a de n estas kio postulita akiri
al la fino de tiu datumstrukturo,

1580
01:16:04,570 --> 01:16:08,410
whereas-- kaj ni ne vidis
ĉi before-- tabelo donas

1581
01:16:08,410 --> 01:16:13,555
kio nomiĝas konstanta tempo, kio signifas
unu paŝo aŭ du paŝoj aŭ 10 steps--

1582
01:16:13,555 --> 01:16:14,180
Ne gravas.

1583
01:16:14,180 --> 01:16:15,440
Ĝi estas fiksa nombro.

1584
01:16:15,440 --> 01:16:17,440
Ĝi havas nenion komunan kun
la grandeco de la tabelo.

1585
01:16:17,440 --> 01:16:20,130
Kaj la kialo por tio,
denove, estas hazarda aliro.

1586
01:16:20,130 --> 01:16:23,180
La komputilo povas simple tuj
salti al alia loko,

1587
01:16:23,180 --> 01:16:27,770
ĉar ili estas tutegale
distanco de ĉiu alia.

1588
01:16:27,770 --> 01:16:29,112
Ne ekzistas pensado implikitaj.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Bone.

1591
01:16:32,400 --> 01:16:39,230
Do se mi povos, mi provos
pentri du finaj bildoj.

1592
01:16:39,230 --> 01:16:42,830
Tre komuna nomata hash tablo.

1593
01:16:42,830 --> 01:16:51,120
Tiel motivi ĉi diskuto,
mi pensas pri kiel fari tion.

1594
01:16:51,120 --> 01:16:52,610
>> Do kion pri cxi tiu?

1595
01:16:52,610 --> 01:16:55,160
Supozu ke la problemo
ni volas solvi nun

1596
01:16:55,160 --> 01:16:58,360
estas implementando en dictionary--
tiel tutan faskon da anglaj vortoj

1597
01:16:58,360 --> 01:16:59,330
aŭ kio ajn.

1598
01:16:59,330 --> 01:17:02,724
Kaj la celo estas povi respondi
demandoj de la formo estas tiu vorto?

1599
01:17:02,724 --> 01:17:04,640
Do vi volas apliki
sorĉas Kontrolilo, ĵus

1600
01:17:04,640 --> 01:17:07,220
kiel fizika vortaro
ke vi povas rigardi aĵojn en.

1601
01:17:07,220 --> 01:17:10,490
Eble mi devis fari tion kun tabelo.

1602
01:17:10,490 --> 01:17:12,590
Mi povus fari tion.

1603
01:17:12,590 --> 01:17:20,756
>> Kaj supozu la vortoj estas pomo
kaj banano kaj melono.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Kaj mi ne povas pensi pri fruktoj
kiuj komencas kun d, tial ni estas nur

1606
01:17:26,465 --> 01:17:27,590
havos tri fruktoj.

1607
01:17:27,590 --> 01:17:31,510
Do tiu estas tabelo kaj ni
stokante ĉiuj vortoj

1608
01:17:31,510 --> 01:17:34,200
en tiu vortaro kiel tabelo.

1609
01:17:34,200 --> 01:17:39,350
La demando do estas kiel alie
povus stoki tiun informon?

1610
01:17:39,350 --> 01:17:43,160
>> Nu, mi specon de trompado tie, ĉar
ĉiu el tiuj literoj en la vorto

1611
01:17:43,160 --> 01:17:44,490
estas vere individuo bajto.

1612
01:17:44,490 --> 01:17:46,740
Do se mi vere volis esti
nit-elektema, mi devus vere

1613
01:17:46,740 --> 01:17:49,600
esti dividanta ĉi supre en multa
malgrandaj pecoj de memoro,

1614
01:17:49,600 --> 01:17:51,289
kaj ni povus fari ĝuste tion.

1615
01:17:51,289 --> 01:17:53,580
Sed ni tuj kolizii
la saman problemon antaŭe.

1616
01:17:53,580 --> 01:17:56,674
Kio se, kiel Merriam Webster aŭ Oxford
faras ĉiun year-- ili aldonu vortojn

1617
01:17:56,674 --> 01:17:59,340
al la dictionary-- ni ne
nepre volas pentri mem

1618
01:17:59,340 --> 01:18:00,780
en angulon kun tabelo?

1619
01:18:00,780 --> 01:18:05,710
>> Do anstataŭe, eble pli lerta alproksimiĝo
estas meti pomon en lia propra nodo aŭ skatolo,

1620
01:18:05,710 --> 01:18:11,190
kiel ni dirus, banano, kaj
tiam tie ni havas melono.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Kaj ni ŝnuro tion kune.

1623
01:18:16,790 --> 01:18:19,980
Do tiu estas la tabelo, kaj
tio estas la ligillisto.

1624
01:18:19,980 --> 01:18:23,300
Se vi ne tute povas vidi, ĝi nur
diras "tabelo", kaj tiu diras "listo."

1625
01:18:23,300 --> 01:18:25,780
>> Do ni havas la samajn
ĝusta temoj kiel antaŭe,

1626
01:18:25,780 --> 01:18:28,600
per kiu ni jam havas
dinamismo en nia ligillisto.

1627
01:18:28,600 --> 01:18:31,090
Sed ni havas sufiĉe malrapidan vortaro.

1628
01:18:31,090 --> 01:18:32,870
Supozu mi volas serĉi ion.

1629
01:18:32,870 --> 01:18:35,430
Ĝi povus kapti min granda a de n
paŝojn, ĉar la vorto eble

1630
01:18:35,430 --> 01:18:37,840
esti tute fine de
la lerta, kiel melono.

1631
01:18:37,840 --> 01:18:40,600
Kaj ĝi rezultas ke
en programado, speco

1632
01:18:40,600 --> 01:18:42,700
de la sankta grail de datumoj
strukturoj, estas io

1633
01:18:42,700 --> 01:18:46,620
kiu donas al vi konstantan
tempo kiel tabelo

1634
01:18:46,620 --> 01:18:50,870
sed kiu ankoraŭ donas dinamismo.

1635
01:18:50,870 --> 01:18:52,940
>> Do ni povas havi la plej bonan de ambaŭ mondoj?

1636
01:18:52,940 --> 01:18:55,570
Kaj ja ekzistas io
nomata hash tablo

1637
01:18:55,570 --> 01:18:59,320
kiu permesas fari ĝuste
ke, kvankam proksimume.

1638
01:18:59,320 --> 01:19:03,140
Al hash tablo estas amatoro
datumstrukturo ke ni

1639
01:19:03,140 --> 01:19:06,340
povas pensi kiel la
kombino de tabelo

1640
01:19:06,340 --> 01:19:12,390
kaj mi tuj desegni ĝin
kiel this-- kaj ligitaj listoj

1641
01:19:12,390 --> 01:19:17,310
ke mi desegni kiel ĉi tie.

1642
01:19:17,310 --> 01:19:19,760
>> Kaj la vojon tion
verkoj estas kiel sekvas.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Se tiu now-- hash table--
Estas mia tria datumstrukturo,

1645
01:19:29,540 --> 01:19:32,590
kaj mi volas konservi
vortoj en tio, mi ne faras

1646
01:19:32,590 --> 01:19:35,440
volas nur konservi ĉiujn
vortoj malantaŭo al malantaŭo al malantaŭo al dorso.

1647
01:19:35,440 --> 01:19:37,430
Mi volas utiligi iun
peco de informo

1648
01:19:37,430 --> 01:19:40,330
pri la vortoj kiuj lasos
mi ricevas ĝin kie ĝi estas pli rapida.

1649
01:19:40,330 --> 01:19:43,666
>> Tiel donitaj la vortoj pomon
kaj banano kaj melono,

1650
01:19:43,666 --> 01:19:45,040
Mi intence elektis tiujn vortojn.

1651
01:19:45,040 --> 01:19:45,340
Kial?

1652
01:19:45,340 --> 01:19:47,631
Kio estas ia fundamente
malsama pri la tri?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Kio estas evidenta?

1655
01:19:51,484 --> 01:19:52,900
Ili komencas kun malsamaj literoj.

1656
01:19:52,900 --> 01:19:53,900
>> Do vi scias kion?

1657
01:19:53,900 --> 01:19:57,120
Anstataŭ meti ĉiujn miajn vortojn en
la sama sitelo, por tiel diri,

1658
01:19:57,120 --> 01:20:00,390
kiel en unu granda listo, kial ne
Mi almenaŭ provu optimumiga

1659
01:20:00,390 --> 01:20:04,180
Kaj purigus miajn listojn 1/26 kiel longe.

1660
01:20:04,180 --> 01:20:07,440
A konvinkaj optimumigo
povus esti kial ne

1661
01:20:07,440 --> 01:20:10,650
I-- kiam enmeto vorton
en ĉi datumstrukturo,

1662
01:20:10,650 --> 01:20:14,300
en la komputilo la memoro, kial
ne mi metis ĉiujn a vortojn tie,

1663
01:20:14,300 --> 01:20:17,270
ĉiuj b vortojn tie,
kaj ĉiuj 'c' vortoj tie?

1664
01:20:17,270 --> 01:20:24,610
Do tiu finas metante pomon
tie, banano tie, melono tie,

1665
01:20:24,610 --> 01:20:25,730
kaj tiel plu.

1666
01:20:25,730 --> 01:20:31,700
>> Kaj se mi havas kroman
vorto like-- kio estas alia?

1667
01:20:31,700 --> 01:20:36,640
Pomo, banano, piro.

1668
01:20:36,640 --> 01:20:39,370
Iu pensas de frukto
kiu komencas kun a, b, aŭ c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- perfekta.

1670
01:20:40,570 --> 01:20:43,990
Kiu tuj finos tie.

1671
01:20:43,990 --> 01:20:47,530
Kaj tiel ni ŝajnas havi
marĝene pli bona solvo,

1672
01:20:47,530 --> 01:20:50,820
ĉar nun se mi volas
serĉi pomon, mi

1673
01:20:50,820 --> 01:20:53,200
first-- mi ne nur dive
en mian datumstrukturo.

1674
01:20:53,200 --> 01:20:54,850
Mi ne plonĝi en mia komputilo memoro.

1675
01:20:54,850 --> 01:20:56,530
Mi unue rigardu la unuan literon.

1676
01:20:56,530 --> 01:20:58,610
>> Kaj tio estas kion komputilo
sciencisto dirus.

1677
01:20:58,610 --> 01:21:00,760
Vi hash en vian datumstrukturo.

1678
01:21:00,760 --> 01:21:04,100
Vi prenas vian enigon, kiu en
tiu kazo estas vorto kiel pomo.

1679
01:21:04,100 --> 01:21:07,150
Vi analizi ĝin, rigardante
la unua letero en tiu kazo,

1680
01:21:07,150 --> 01:21:08,340
tiel hashing ĝin.

1681
01:21:08,340 --> 01:21:10,950
Regionoj estas ĝenerala termino por kiu
vi prenas ion kiel enigo

1682
01:21:10,950 --> 01:21:12,116
kaj vi produkti iuj eligo.

1683
01:21:12,116 --> 01:21:15,090
Kaj la eligo en tiu
kazo estas la loko

1684
01:21:15,090 --> 01:21:18,150
vi volas serĉi, la unua
loko, dua loko, tria.

1685
01:21:18,150 --> 01:21:22,160
Do la enigo estas pomo,
la eligo estas unua.

1686
01:21:22,160 --> 01:21:25,054
La enigo estas banano, la
eligo devus esti dua.

1687
01:21:25,054 --> 01:21:27,220
La enigo estas melono,
la eligo estu tria.

1688
01:21:27,220 --> 01:21:30,320
La enigo estas Blueberry, la
eligo devus denove esti dua.

1689
01:21:30,320 --> 01:21:34,010
Kaj tio helpas vin preni
ŝparvojoj tra via memoro

1690
01:21:34,010 --> 01:21:39,050
por akiri al vortoj
aŭ datumojn pli efike.

1691
01:21:39,050 --> 01:21:43,330
>> Nun ĉi tranĉas malsupren nia tempo potenciale
per kiom unu el 26,

1692
01:21:43,330 --> 01:21:45,850
ĉar se vi supozas ke vi
havi tiom da "al" vortoj kiel "z"

1693
01:21:45,850 --> 01:21:48,080
vortoj kiel "q" vortoj, kiujn
ne vere realistic--

1694
01:21:48,080 --> 01:21:50,830
vi tuj havos esviaje trans
iuj literoj de la aboco

1695
01:21:50,830 --> 01:21:53,204
sed tio estus dumtajpa
alproksimiĝo tio permesas

1696
01:21:53,204 --> 01:21:55,930
vi atingos vortoj multe pli rapide.

1697
01:21:55,930 --> 01:21:59,660
Kaj fakte, kompleksa
programo, la Googles de la mondo,

1698
01:21:59,660 --> 01:22:02,180
la Facebooks de la world--
ili uzus hash tablo

1699
01:22:02,180 --> 01:22:03,740
por multaj malsamaj celoj.

1700
01:22:03,740 --> 01:22:06,590
Sed ili ne estus tiel naiva kiel
nur rigardu la unuan literon

1701
01:22:06,590 --> 01:22:09,700
en pomo aŭ banano aŭ
piro aŭ melono,

1702
01:22:09,700 --> 01:22:13,420
ĉar kiel vi povas vidi ĉi tiujn
listoj povus ankoraŭ atingi longa.

1703
01:22:13,420 --> 01:22:17,130
>> Kaj tiel ĉi povus ankoraŭ esti ia
de linear-- do ia malrapida,

1704
01:22:17,130 --> 01:22:19,980
kiel kun la granda a de n
ke ni diskutis antaŭe.

1705
01:22:19,980 --> 01:22:25,290
Do kion realan bonon hash tablo volo
do-- havos multe pli granda tabelo.

1706
01:22:25,290 --> 01:22:28,574
Kaj ĝi uzos multe pli
malnaiva kradanta funkcio,

1707
01:22:28,574 --> 01:22:30,240
tiel ke ĝi ne nur rigardi la "a."

1708
01:22:30,240 --> 01:22:35,480
Eble rigardas "al-p-p-l-e" kaj
iel konvertas tiujn kvin literoj

1709
01:22:35,480 --> 01:22:38,400
en la loko kie
pomo estas konservataj.

1710
01:22:38,400 --> 01:22:42,660
Ni nur naive uzante la literon 'a'
sola, ĉar ĝi estas bela kaj simpla.

1711
01:22:42,660 --> 01:22:44,600
>> Sed hash tablo, en
Fine, vi povas pensi

1712
01:22:44,600 --> 01:22:47,270
de kiel kombinaĵo de
tabelo, ĉiu el kiuj

1713
01:22:47,270 --> 01:22:51,700
havas ligillisto ke ideale
devus esti kiel mallonga kiel ebla.

1714
01:22:51,700 --> 01:22:54,364
Kaj tio ne estas evidenta solvo.

1715
01:22:54,364 --> 01:22:57,280
Fakte, granda parto de la ĝustigas fajna
okazanta sub la kapuĉo kiam

1716
01:22:57,280 --> 01:22:59,654
efektivigado tiuj specoj de
kompleksaj datumstrukturoj

1717
01:22:59,654 --> 01:23:01,640
Estas kio estas la dekstra
longo de la tabelo?

1718
01:23:01,640 --> 01:23:03,250
Kio estas la dekstra hash funkcio?

1719
01:23:03,250 --> 01:23:04,830
Kiel vi stoki aferojn en memoro?

1720
01:23:04,830 --> 01:23:07,249
>> Sed konscias kiom rapide
ĉi tia diskuto

1721
01:23:07,249 --> 01:23:10,540
eskaladis, ĉu ĝis nun ke ĝi estas speco
de super onies kapo ĉe tiu punkto, kiu

1722
01:23:10,540 --> 01:23:11,360
Estas bone.

1723
01:23:11,360 --> 01:23:18,820
Sed ni komencis, revokon, kun vere
io malalta nivelo kaj elektronika.

1724
01:23:18,820 --> 01:23:20,819
Kaj tiel ĉi denove estas ĉi
temo de abstraktado,

1725
01:23:20,819 --> 01:23:23,610
kie iam vi komencas preni por
permesite, OK, Mi havas it-- ekzistas

1726
01:23:23,610 --> 01:23:26,680
fizika memoro, OK, havas ĝin, ĉiu
fizika loko havas adreson,

1727
01:23:26,680 --> 01:23:29,910
Okej, mi havas ĝin, mi povas reprezenti
tiujn adresojn kiel arrows--

1728
01:23:29,910 --> 01:23:34,650
Vi povas tre rapide komencas havi
pli altnivela konversaciojn kiuj

1729
01:23:34,650 --> 01:23:38,360
en la fino ŝajnas esti permesante nin
solvi problemojn kiel serĉado

1730
01:23:38,360 --> 01:23:41,620
kaj ordigado pli efike.

1731
01:23:41,620 --> 01:23:44,190
Kaj estu certaj, ankaŭ kontraŭ
ĉar mi pensas ĉi

1732
01:23:44,190 --> 01:23:48,700
estas la plej profunda ni iris en iun
de tiuj CS temoj proper-- ni havas

1733
01:23:48,700 --> 01:23:51,880
farita en tago kaj duono ĉe tiu
atentigi kion vi eble tipe fari super

1734
01:23:51,880 --> 01:23:55,520
la kurso de ok semajnoj en semestro.

1735
01:23:55,520 --> 01:23:59,670
>> Demandojn pri tiuj?

1736
01:23:59,670 --> 01:24:01,100
Ne?

1737
01:24:01,100 --> 01:24:01,940
Bone.

1738
01:24:01,940 --> 01:24:05,610
Nu, kial ni ne paŭzi tie,
komenci tagmanĝo kelkajn minutojn frua,

1739
01:24:05,610 --> 01:24:07,052
rekomenci en nur ĉirkaŭ unu horon?

1740
01:24:07,052 --> 01:24:08,760
Kaj mi restadi dum
iom kun demandoj.

1741
01:24:08,760 --> 01:24:11,343
Tiam mi tuj devos iri
preni kelkajn vokojn se tio estas bone.

1742
01:24:11,343 --> 01:24:15,000
Mi turnos sur iu muziko intertempe,
sed lunĉo devus esti ĉirkaŭ la angulo.

1743
01:24:15,000 --> 01:24:17,862