1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> Parolanto 1: Bone, do ĉi estas
CS50 Jen la fino de semajno kvin.

3
00:00:15,860 --> 00:00:19,220
Kaj memoras ke lastfoje ni
komenciĝis rigardante la amatoro datumoj

4
00:00:19,220 --> 00:00:22,310
strukturoj kiuj komencis solvi
problemoj, kiuj komencis enkonduki

5
00:00:22,310 --> 00:00:25,640
novaj problemoj, sed la ŝlosilo al tiu
estis la speco de threading ke ni

6
00:00:25,640 --> 00:00:27,940
komencis fari de nodo al nodo.

7
00:00:27,940 --> 00:00:30,085
Do tiu kompreneble estas
oni unuope ligita listo.

8
00:00:30,085 --> 00:00:31,960
Kaj per unuope ligitaj,
Mi signifas restas nur unu

9
00:00:31,960 --> 00:00:33,380
fadeno inter ĉiu el tiuj nodoj.

10
00:00:33,380 --> 00:00:35,890
Rezultas vi povas fari amatoro
aĵoj kiel duoble ligitaj listoj

11
00:00:35,890 --> 00:00:38,470
whereby vi havas sagon
irante en ambaŭ direktoj, kiuj

12
00:00:38,470 --> 00:00:40,320
povas helpi kun iuj efikecojn.

13
00:00:40,320 --> 00:00:42,000
Sed tiu solvis la problemon?

14
00:00:42,000 --> 00:00:43,500
Kio problemo ja ĉi solvi?

15
00:00:43,500 --> 00:00:46,620
Kial ni zorgas lunde?

16
00:00:46,620 --> 00:00:49,820
Kial, en teorio, ni zorgas lunde?

17
00:00:49,820 --> 00:00:50,630
Kion ĝi faras?

18
00:00:50,630 --> 00:00:51,950
>> Publiko: Ni povas dinamike regrandigi ĝin.

19
00:00:51,950 --> 00:00:53,740
>> Parolanto 1: Bone, do ni povas
dinamike regrandigi ĝin.

20
00:00:53,740 --> 00:00:54,710
Bonege vi ambaŭ.

21
00:00:54,710 --> 00:00:57,560
Do vi povas dinamike regrandigi ĉi
datumstrukturo, dum tabelo,

22
00:00:57,560 --> 00:01:00,760
revokon, vi devas scii
priori kiom spaco vi volas

23
00:01:00,760 --> 00:01:03,870
kaj se vi bezonas iom pli
spaco, vi estas speco de el sorton.

24
00:01:03,870 --> 00:01:05,560
Vi devas krei tutan novan tabelo.

25
00:01:05,560 --> 00:01:07,893
Vi devas movi ĉiuj viaj
datumoj de unu al la alia,

26
00:01:07,893 --> 00:01:10,600
eventuale liberigi la malnova tabelo
se vi povas, kaj poste plu.

27
00:01:10,600 --> 00:01:13,891
Kiuj nur sentas tre multekosta kaj tre
malkompetenta, kaj ja povas esti.

28
00:01:13,891 --> 00:01:14,890
Sed tio ne estas tute bona.

29
00:01:14,890 --> 00:01:18,180
Ni pagas prezon, kio estis unu
de la pli evidentaj prezoj ni

30
00:01:18,180 --> 00:01:20,550
pagi uzante ligitaj listo?

31
00:01:20,550 --> 00:01:22,825
>> Publiko: Ni devas uzi
duobla spaco por ĉiu.

32
00:01:22,825 --> 00:01:25,200
Parolanto 1: Jes, do ni bezonas
almenaŭ duoble da spaco.

33
00:01:25,200 --> 00:01:27,700
Fakte, mi rimarkis tiun foton la
eĉ iom misgvida,

34
00:01:27,700 --> 00:01:32,200
ĉar sur CS50 IDE en multaj modernaj
komputiloj, montrilo aŭ adreson

35
00:01:32,200 --> 00:01:33,700
ne estas fakte kvar bajtoj.

36
00:01:33,700 --> 00:01:36,090
Ĝi estas tre ofte tiuj
tagoj ok bajtoj, kiuj

37
00:01:36,090 --> 00:01:38,530
signifas la fundo plej
rektangulojn tie en realo

38
00:01:38,530 --> 00:01:40,900
estas ia duoble
granda kiel kion mi desegnis,

39
00:01:40,900 --> 00:01:44,409
kio signifas vi uzas trioble
da spaco kiel ni havu alie.

40
00:01:44,409 --> 00:01:46,700
Nun samtempe, ni estas
ankoraŭ parolas bitokoj, ĉu ne?

41
00:01:46,700 --> 00:01:49,140
Ni ne nepre parolanta
megabajtoj aŭ gigabajtoj,

42
00:01:49,140 --> 00:01:51,000
krom se tiuj datumstrukturoj akiri grandan.

43
00:01:51,000 --> 00:01:54,510
>> Kaj do hodiaŭ ni komencas konsideri
kiel ni povus esplori datumoj

44
00:01:54,510 --> 00:01:57,310
pli efike se en
Fakte la datumoj akiras pli grandan.

45
00:01:57,310 --> 00:02:00,360
Sed ni provu canonicalize
la operacioj unua

46
00:02:00,360 --> 00:02:02,460
ke vi povas fari en ĉi tiuj
specojn de datumstrukturoj.

47
00:02:02,460 --> 00:02:04,790
Do iu kiel ligitaj
lerta ĝenerale subtenas

48
00:02:04,790 --> 00:02:07,514
operacioj ŝatas forigi,
enmeti kaj serĉu.

49
00:02:07,514 --> 00:02:08,639
Kaj kion mi volas diri per tio?

50
00:02:08,639 --> 00:02:11,222
Tio simple signifas ke kutime,
se personoj uzas ligillisto,

51
00:02:11,222 --> 00:02:14,287
ili aŭ iu alia estas implementado
funkcioj kiel delete, insert,

52
00:02:14,287 --> 00:02:16,120
kaj serĉo, tiel vi povas
efektive fari ion

53
00:02:16,120 --> 00:02:18,030
utila kun la datumstrukturo.

54
00:02:18,030 --> 00:02:20,760
Do ni prenu rapidan rigardon
kiel ni povus efektivigi

55
00:02:20,760 --> 00:02:24,530
iu kodo por ligillisto jene.

56
00:02:24,530 --> 00:02:27,885
>> Do tiu estas nur iuj C kodo,
eĉ kompletan programon

57
00:02:27,885 --> 00:02:29,260
ke mi vere rapide ekfrapis.

58
00:02:29,260 --> 00:02:32,300
Ĝi ne estas linio en la dissendo
kodo, ĉar ĝi ne reale kuri.

59
00:02:32,300 --> 00:02:33,790
Sed rimarki Mi havas precize
kun komenton diris,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, ekzistas io
tie, dot dot dot, ion tie.

61
00:02:36,130 --> 00:02:38,410
Kaj ni simple rigardi
kion la sukaj partoj estas.

62
00:02:38,410 --> 00:02:40,790
Do sur linio tri,
memoras ke tiu estas nun

63
00:02:40,790 --> 00:02:45,960
Ni proponis deklari nodo lasta
tempo, unu el tiuj rektangulaj objektoj.

64
00:02:45,960 --> 00:02:48,790
Ĝi havas int ke ni vokos N,
sed ni povus nomi ion,

65
00:02:48,790 --> 00:02:51,920
kaj tiam struct nodo stelo nomas proksima.

66
00:02:51,920 --> 00:02:55,520
Kaj nur por esti klara, ke dua
linio, sur linio ses, kio estas tio?

67
00:02:55,520 --> 00:02:57,930
Kio ĝi faras por ni?

68
00:02:57,930 --> 00:03:01,044
Ĉar ĝi certe aspektas pli
kamufla ol nia kutima variabloj.

69
00:03:01,044 --> 00:03:02,740
>> Spektantaro: Ĝi igas ĝin moviĝi super unu.

70
00:03:02,740 --> 00:03:04,650
>> Parolanto 1: Ĝi igas ĝin moviĝi super unu.

71
00:03:04,650 --> 00:03:08,580
Kaj por esti pli preciza,
ĝi stokos la adreson

72
00:03:08,580 --> 00:03:11,582
de la nodo kiu signifis esti
semantike apud ĝi, ĉu ne?

73
00:03:11,582 --> 00:03:13,540
Do ne tuj
nepre movi ion.

74
00:03:13,540 --> 00:03:15,290
Ĝi simple tuj
stoki valoron, kiu estas

75
00:03:15,290 --> 00:03:17,170
tuj estos la adreso
de iu alia nodo,

76
00:03:17,170 --> 00:03:20,810
kaj tial ni diris struct
nodo stelo, la stelo signifanta

77
00:03:20,810 --> 00:03:22,370
montrilo aŭ adreson.

78
00:03:22,370 --> 00:03:26,390
Bone, do nun se vi supozas ke ni devos
tiu N havebla al ni, kaj ni

79
00:03:26,390 --> 00:03:29,490
supozas ke iu alia havas
insertita tutan faskon de entjeroj

80
00:03:29,490 --> 00:03:30,400
en ligillisto.

81
00:03:30,400 --> 00:03:35,640
Kaj ke ligillisto estas
almontras iu punkto

82
00:03:35,640 --> 00:03:39,040
ŝanĝiĝema nomita listo jen
pasis en tie kiel parametro,

83
00:03:39,040 --> 00:03:43,120
kiel mi iros sur linio
14 efektivigado serĉo?

84
00:03:43,120 --> 00:03:45,990
En aliaj vortoj, se mi efektivigado
funkcio kies celo en la vivo

85
00:03:45,990 --> 00:03:48,889
estas preni int kaj poste la
komencante de ligillisto,

86
00:03:48,889 --> 00:03:50,430
ke estas puntero al la ligillisto.

87
00:03:50,430 --> 00:03:52,992
Kiel unua, kiu mi pensas Davido
Estis nia volontulo lunde,

88
00:03:52,992 --> 00:03:54,700
li indik
la tutan ligillisto,

89
00:03:54,700 --> 00:03:57,820
ĝi estas kvazaŭ ni pasante
David en kiel nia argumento tie.

90
00:03:57,820 --> 00:03:59,990
Kiel ni iras pri petolanta tiu listo?

91
00:03:59,990 --> 00:04:04,640
Nu, Ĝi rezultas ke kvankam
punteros estas relative nova nun por ni,

92
00:04:04,640 --> 00:04:07,010
Ni povas fari ĉi relative
rekte?.

93
00:04:07,010 --> 00:04:09,500
>> Mi tuj iros antaŭen kaj
deklari portempa variablo kiu

94
00:04:09,500 --> 00:04:12,364
per konvencio estas ĝuste tuj
esti nomata montrilo, aŭ PTR,

95
00:04:12,364 --> 00:04:14,030
sed vi povus voki ĝi ajn vi volas.

96
00:04:14,030 --> 00:04:16,470
Kaj mi tuj pravalorizi
ĝin al la komenco de la listo.

97
00:04:16,470 --> 00:04:20,050
Do vi povas ia pensas pri ĉi
kiel mi la majstro la alia tago,

98
00:04:20,050 --> 00:04:23,580
ia montrante iun
inter niaj homoj kiel volontuloj.

99
00:04:23,580 --> 00:04:26,470
Do mi estas portempa variablo tio
nur montrante la saman aferon

100
00:04:26,470 --> 00:04:31,390
ke nia hazarde nomis
volontulo David ankaŭ atentiganta.

101
00:04:31,390 --> 00:04:35,440
Nun dum puntero estas
ne nula, ĉar revoko

102
00:04:35,440 --> 00:04:40,350
ke nula estas iuj specialaj sentinelo valoro
la demarca la fino de la listo,

103
00:04:40,350 --> 00:04:44,280
do dum mi ne montrante la
tero kiel nia lasta volontulo

104
00:04:44,280 --> 00:04:47,190
estis, ni iru antaŭen
kaj fari la sekvan.

105
00:04:47,190 --> 00:04:51,820
Se pointer-- kaj nun mi specon de volas
fari kion ni faris kun la studento

106
00:04:51,820 --> 00:04:57,410
structure-- se puntero punkto apud
equals-- prefere, se puntero punkto N egalas

107
00:04:57,410 --> 00:05:02,290
egalas la variablo n, la
argumento ke tio estis pasita en,

108
00:05:02,290 --> 00:05:05,370
tiam mi volas antaŭeniri
kaj diri reveni vera.

109
00:05:05,370 --> 00:05:11,020
Mi trovis la nombro N ene de
unu el la nodoj de mia ligillisto.

110
00:05:11,020 --> 00:05:13,500
Sed la punkto ne plu
laboras en tiu kunteksto,

111
00:05:13,500 --> 00:05:17,260
ĉar montrilo, PTR, estas
ja puntero, adreson,

112
00:05:17,260 --> 00:05:20,632
ni efektive povas mirinde
uzi fine peco de sintakso

113
00:05:20,632 --> 00:05:22,590
tian fabrikas
intuicia senco kaj reale

114
00:05:22,590 --> 00:05:27,870
uzi sago tie, kio signifas iri de
tiu adreso al la entjera tie.

115
00:05:27,870 --> 00:05:30,160
Do estas tre similaj en
spiriton al la skalara operatoro,

116
00:05:30,160 --> 00:05:33,860
sed ĉar montrilon ne montrilo
kaj ne reala struct mem,

117
00:05:33,860 --> 00:05:35,380
Ni simple uzu la sago.

118
00:05:35,380 --> 00:05:40,620
>> Do se la nuna nodo ke Mi, la
provizora variablo, am indik

119
00:05:40,620 --> 00:05:43,060
ne N, kion mi volas fari?

120
00:05:43,060 --> 00:05:45,910
Nu, kun mia homaj volontuloj
ke ni havis tie la alia tago,

121
00:05:45,910 --> 00:05:49,710
se mia unua homa ne estas la unu mi
volas, kaj eble la dua homa estas ne

122
00:05:49,710 --> 00:05:52,660
la unu mi volas, kaj la tria, mi
bezonas konservi fizike movante.

123
00:05:52,660 --> 00:05:54,690
Kiel kiel mi paŝi tra listo?

124
00:05:54,690 --> 00:05:57,470
Kiam ni havis tabelo, vi
nur faris kiel mi plie kaj plie.

125
00:05:57,470 --> 00:06:03,660
Sed en ĉi tiu kazo, sufiĉas
fari puntero, Akiras, montrilo, sekva.

126
00:06:03,660 --> 00:06:07,580
En aliaj vortoj, la sekvanta kampo
estas kiel ĉiuj de la maldekstra mano

127
00:06:07,580 --> 00:06:10,880
ke nia homa volontuloj lunde
estis uzante noti al iu alia nodo.

128
00:06:10,880 --> 00:06:12,890
Tiuj estas iliaj proksimaj najbaroj.

129
00:06:12,890 --> 00:06:17,060
>> Do se mi volas paŝi tra tiu listo,
Mi ne povas simple fari mi plie plus plu,

130
00:06:17,060 --> 00:06:20,120
Mi anstataŭe devas diri
Mi, montrilo, tuj

131
00:06:20,120 --> 00:06:24,650
egali ajn la sekva kampo estas,
la sekva kampo, la sekva kampo estas,

132
00:06:24,650 --> 00:06:28,350
sekvante ĉiuj tiuj postlasitaj manoj
ke ni havis sur scenejo indikanta

133
00:06:28,350 --> 00:06:30,000
al iuj sekvaj valoroj.

134
00:06:30,000 --> 00:06:32,590
Kaj se mi akiras tra
ke tutaj ripeto,

135
00:06:32,590 --> 00:06:39,330
kaj fine, mi batis nula ne havanta
trovis N tamen, mi simple reveni falsaj.

136
00:06:39,330 --> 00:06:44,100
Do denove, cxiuj ni faras ĉi tie,
kiel por la bildo antaŭ momento,

137
00:06:44,100 --> 00:06:47,840
komencas per fingromontrante la
komencante de la listo supozeble.

138
00:06:47,840 --> 00:06:50,970
Kaj tiam mi kontrolu, estas la valoro
Mi serĉas egalas naŭ?

139
00:06:50,970 --> 00:06:52,650
Se jes, mi revenas vera kaj mi estas farita.

140
00:06:52,650 --> 00:06:56,450
Se ne, mi ĝisdatigos mian manon,
AKA montrilo, atentigi

141
00:06:56,450 --> 00:06:59,540
ĉe la venonta sago situo, kaj
tiam la sekva sago situo,

142
00:06:59,540 --> 00:07:00,480
kaj la sekva.

143
00:07:00,480 --> 00:07:03,770
Mi simple piediranta tra ĉi tabelo.

144
00:07:03,770 --> 00:07:06,010
>> Do denove, al kiu gravas?

145
00:07:06,010 --> 00:07:07,861
Kiel kio estas tiu ingredienco por?

146
00:07:07,861 --> 00:07:10,360
Nu, memoru ke ni enkondukis
la nocio de pilo, kiu

147
00:07:10,360 --> 00:07:15,400
estas abstrakta datumtipo mezuro estas
ne C afero, ĝi ne estas CS50 afero,

148
00:07:15,400 --> 00:07:19,430
ĝi estas abstrakta ideo, tiu ideo de
stakiganta aferoj unu sur alian

149
00:07:19,430 --> 00:07:21,820
kiuj povas esti efektivigitaj en
gxibo de malsamaj manieroj.

150
00:07:21,820 --> 00:07:25,600
Kaj unu vojo ni proponis estis kun
tabelo, aŭ kun ligillisto.

151
00:07:25,600 --> 00:07:29,570
Kaj ĝi rezultas ke kanone, a
pilo subtenas almenaŭ du operacioj.

152
00:07:29,570 --> 00:07:32,320
Kaj la zumado vortoj estas puŝo, por
puŝi ion sur la pilo,

153
00:07:32,320 --> 00:07:34,770
kiel nova pleto en la
manĝejo, aŭ popo,

154
00:07:34,770 --> 00:07:39,000
kio signifas forigi la plejsupra
pleto de la stako en la manĝ

155
00:07:39,000 --> 00:07:41,500
halon, kaj tiam eble iuj
aliaj operacioj ankaŭ.

156
00:07:41,500 --> 00:07:45,770
Do kiel povus ni difini la strukturon
ke ni nun nomante pilo?

157
00:07:45,770 --> 00:07:50,020
>> Nu, ni havas ĉiujn la kondiĉo
sintakso ĉe nia dispono en C. Mi diras,

158
00:07:50,020 --> 00:07:53,830
Donu al mi tipon de difino
struct ene de pilo,

159
00:07:53,830 --> 00:07:58,030
Mi tuj diros estas tabelo, de
tuta aro da nombroj kaj tiam grandeco.

160
00:07:58,030 --> 00:08:00,930
Do alivorte, se mi volas
implementar ĉi en kodo,

161
00:08:00,930 --> 00:08:03,830
permesu al mi iri kaj nur speco de
desegni kion tiu diras.

162
00:08:03,830 --> 00:08:06,317
Do tiu diras, donu al mi
strukturo kiu estas alvenis tabelo,

163
00:08:06,317 --> 00:08:09,400
kaj mi ne scias kion kapablo estas,
ĝi estas ŝajne iu konstanto ke mi havas

164
00:08:09,400 --> 00:08:10,858
difinitaj aliloke, kaj tio estas bone.

165
00:08:10,858 --> 00:08:15,260
Sed certe nun nur unu,
du, tri, kvar, kvin.

166
00:08:15,260 --> 00:08:16,700
Do kapablo estas 5.

167
00:08:16,700 --> 00:08:21,730
Tiu elemento ene de mia
strukturo estos nomitaj nombroj.

168
00:08:21,730 --> 00:08:24,020
Kaj tiam mi bezonas unu
alia variablo ŝajne

169
00:08:24,020 --> 00:08:27,814
nomata grandeco kiu komence Mi tuj
al kondiĉas inicializa al nulo.

170
00:08:27,814 --> 00:08:29,730
Se nenio estas en
la pilo, esas nulo,

171
00:08:29,730 --> 00:08:31,420
kaj ĝi estas rubo valorojn en nombroj.

172
00:08:31,420 --> 00:08:33,450
Mi havas neniun ideon kio estas tie interne ĵus ankoraŭ.

173
00:08:33,450 --> 00:08:36,059
>> Do se mi volas puŝi
ion sur la pilo,

174
00:08:36,059 --> 00:08:40,780
supozas ke mi nomas la funkcion puŝo, kaj
Mi diras puŝi 50, kiel la numero 50,

175
00:08:40,780 --> 00:08:44,090
kie vi proponas
Mi tiros lin en tiu tabelo?

176
00:08:44,090 --> 00:08:47,124
Ekzistas kvin malsamaj eblaj respondoj.

177
00:08:47,124 --> 00:08:48,790
Kie vi volas puŝi la numero 50?

178
00:08:48,790 --> 00:08:51,899
Se la celo tie, denove, invitu
funkcio puŝo, pasas en argumento

179
00:08:51,899 --> 00:08:52,940
de 50, kie mi metis ĝin?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Kvin possible-- 20% ŝanco
de konjektanta korekte.

182
00:08:59,052 --> 00:08:59,896
Jes?

183
00:08:59,896 --> 00:09:00,740
>> Publiko: ekstremdekstro.

184
00:09:00,740 --> 00:09:01,990
>> Parolanto 1: ekstremdekstro.

185
00:09:01,990 --> 00:09:08,359
Estas nun 25% ŝanco
de konjektanta korekte.

186
00:09:08,359 --> 00:09:09,650
Por ke estus vere bone.

187
00:09:09,650 --> 00:09:12,770
Por konvencio, mi diru kun tabelo,
ni ĝenerale komenci ĉe la maldekstra,

188
00:09:12,770 --> 00:09:14,519
sed ni certe povus
komencu ĉe la dekstra.

189
00:09:14,519 --> 00:09:17,478
Do ruiniganto tie estus mi
probable tuj tiros gxin maldekstre,

190
00:09:17,478 --> 00:09:20,060
Ĝuste kiel en normala tabelo kie
Mi komencas irita maldekstre dekstren.

191
00:09:20,060 --> 00:09:21,780
Sed se vi povas flip
la aritmetiko, fajna.

192
00:09:21,780 --> 00:09:23,060
Ĝi estas nur ne convencionales.

193
00:09:23,060 --> 00:09:24,880
OK, mi bezonas fari unu
pli ŝanĝo tamen.

194
00:09:24,880 --> 00:09:27,710
Nun ke mi puŝis ion
sur la pilo, kio estas poste?

195
00:09:27,710 --> 00:09:29,400
>> Bone, mi devas pliigo la grandeco.

196
00:09:29,400 --> 00:09:32,600
Do lasu min antaŭeniri kaj justa
ĝisdatigu tiun, kiu estis nulo.

197
00:09:32,600 --> 00:09:35,950
Kaj anstataŭe nun, mi tuj
meti en la valoro unu.

198
00:09:35,950 --> 00:09:39,460
Kaj nun supozu mi puŝas alian
numeron sur la pilo, kiel 51.

199
00:09:39,460 --> 00:09:42,680
Nu, mi devas fari unu pli
ŝanĝo, kiu estas ĝis la grando du.

200
00:09:42,680 --> 00:09:46,100
Kaj tiam mi supozas puŝi pli
numeron sur la pilo kiel 61,

201
00:09:46,100 --> 00:09:52,530
nun mi bezonas ĝisdatigi la grandeco pli
tempo, kaj akiri la valoron 3 kiel la grandeco.

202
00:09:52,530 --> 00:09:54,690
Kaj nun supozu mi nomas popo.

203
00:09:54,690 --> 00:09:57,250
Nun pop, per konvencio,
ne prenas argumenton.

204
00:09:57,250 --> 00:10:00,430
Kun pilo, la tuta
punkto de la pleto metaforo

205
00:10:00,430 --> 00:10:03,450
estas ke vi ne havas bontrovo
iri atingi tiun pleton, Ĉiuj vi povas fari

206
00:10:03,450 --> 00:10:06,330
estas pop la plejsupra unu el
la stako, nur ĉar.

207
00:10:06,330 --> 00:10:08,010
Tion ĉi datumstrukturo faras.

208
00:10:08,010 --> 00:10:12,250
>> Do per tiu logiko se mi
diru popmuziko, kion elspezas?

209
00:10:12,250 --> 00:10:13,080
Do 61.

210
00:10:13,080 --> 00:10:15,402
Do kio vere estas la komputilo
faros en memoro?

211
00:10:15,402 --> 00:10:16,610
Kion mia kodo devas fari?

212
00:10:16,610 --> 00:10:20,330
Kion vi proponas
ni ŝanĝas sur la ekrano?

213
00:10:20,330 --> 00:10:23,410
Kio devus ŝanĝi?

214
00:10:23,410 --> 00:10:24,960
Pardonon?

215
00:10:24,960 --> 00:10:26,334
Do ni forigi 61.

216
00:10:26,334 --> 00:10:27,500
Do mi sendube povas tion fari.

217
00:10:27,500 --> 00:10:28,640
Kaj mi povas forigi 61.

218
00:10:28,640 --> 00:10:30,980
Kaj tiam kion aliaj
ŝanĝo bezonas okazi?

219
00:10:30,980 --> 00:10:33,160
Grandeco probable devas reiri al du.

220
00:10:33,160 --> 00:10:34,210
Kaj do tio estas bone.

221
00:10:34,210 --> 00:10:36,690
Sed atendu momenton, grandeco
antaŭ momento estis tri.

222
00:10:36,690 --> 00:10:38,240
Ni nur faru rapidan prudento ĉeko.

223
00:10:38,240 --> 00:10:41,810
Kiel ni scias ke ni
volis forigi 61?

224
00:10:41,810 --> 00:10:42,760
Ĉar ni krevanta.

225
00:10:42,760 --> 00:10:46,450
Kaj tial mi havas tiun duan propraĵo grandeco.

226
00:10:46,450 --> 00:10:48,470
>> Atendu minuton, mi estas
pensante reen al semajno du

227
00:10:48,470 --> 00:10:51,660
kiam ni komencis paroli pri
arrays, kie tiu estis loko nulo,

228
00:10:51,660 --> 00:10:55,920
tiu estis loko unu, tiu estis loko
du, tio estas loko tri, kvar,

229
00:10:55,920 --> 00:10:58,460
ĝi aspektas kiel la
interrilato inter grandeco

230
00:10:58,460 --> 00:11:02,780
kaj la elemento kiu mi volas forigi
el la tabelo aperas nur esti kio?

231
00:11:02,780 --> 00:11:05,120
Grandeco minus unu.

232
00:11:05,120 --> 00:11:07,786
Kaj do tiel estas kiel kiel homoj
ni scias 61 venas unue.

233
00:11:07,786 --> 00:11:09,160
Kiel fartas la komputilo tuj scias?

234
00:11:09,160 --> 00:11:11,701
Kiam via kodo, kie vi probable
volas fari grandeco minus unu,

235
00:11:11,701 --> 00:11:14,950
tial tri minus unu estas du, kaj ke
Do oni volas forigi 61.

236
00:11:14,950 --> 00:11:18,000
Kaj tiam ni povas ja ĝisdatigi
la grandeco por ke grandeco nun

237
00:11:18,000 --> 00:11:20,300
iras de tri al nur du.

238
00:11:20,300 --> 00:11:24,520
Kaj ĝuste por esti pedanta, mi tuj
proponi ke mi faris, ĉu ne?

239
00:11:24,520 --> 00:11:27,660
Vi proponis intuicie
ĝuste mi devus forigi 61.

240
00:11:27,660 --> 00:11:30,700
Sed ne mi specon de
ia liveris de 61?

241
00:11:30,700 --> 00:11:33,790
Mi efektive forgesis
ke fakte ekzistas.

242
00:11:33,790 --> 00:11:37,680
Kaj pensas reen al PSET4, se vi legis
la artikolo pri jura, la PDF

243
00:11:37,680 --> 00:11:40,780
ke ni devis vin uloj legi, aŭ vi
legos tiun semajnon por PSET4.

244
00:11:40,780 --> 00:11:44,300
Memoru ke ĉi tiu estas reale germane al
la tuta ideo de komputilo jura.

245
00:11:44,300 --> 00:11:47,820
Kio komputilo ĝenerale faras estas
ĝi simple forgesas kie io estas,

246
00:11:47,820 --> 00:11:51,300
sed ne eniros kaj kiel
provu skrapi ĝin aŭ override

247
00:11:51,300 --> 00:11:54,560
tiuj bitoj kun nuloj kaj
aŭ alian hazarda padrono

248
00:11:54,560 --> 00:11:56,690
krom se vi mem faras tiel intence.

249
00:11:56,690 --> 00:11:58,930
Do via intuicio estis
Bone, ni forigi 61.

250
00:11:58,930 --> 00:12:00,650
Sed en realo, ni ne devas tedi.

251
00:12:00,650 --> 00:12:04,040
Ni nur bezonas forgesu ke
ĝi estas tie ŝanĝante nia grandeco.

252
00:12:04,040 --> 00:12:05,662
>> Nun estas problemo kun tiu pilo.

253
00:12:05,662 --> 00:12:07,620
Se mi tenas puŝante aferoj
sur la pilo, kio estas

254
00:12:07,620 --> 00:12:11,167
evidente okazos
en nur kelkaj momentoj tempo?

255
00:12:11,167 --> 00:12:12,500
Ni tuj kuri el spaco.

256
00:12:12,500 --> 00:12:13,580
Kaj kion ni faru?

257
00:12:13,580 --> 00:12:14,680
Ni speco de ŝraŭbita.

258
00:12:14,680 --> 00:12:19,000
Tiu efektivigo ne lasas
ni regrandigi la tabelo, ĉar uzante

259
00:12:19,000 --> 00:12:21,240
tiu sintakso, se vi
pensas reen al semajno du,

260
00:12:21,240 --> 00:12:23,520
iam vi deklaris
la grandeco de tabelo,

261
00:12:23,520 --> 00:12:26,780
ni ne vidis mekanismo ankoraŭ kie
vi povas ŝanĝi la grandecon de la tabelo.

262
00:12:26,780 --> 00:12:29,020
Kaj efektive C ne havas tiun karakterizaĵon.

263
00:12:29,020 --> 00:12:32,524
Se vi diras al mi kvin
Nths, nomu ilin nombroj,

264
00:12:32,524 --> 00:12:33,940
jen ĉio vi tuj ricevos.

265
00:12:33,940 --> 00:12:38,790
Do ni faru nun kiel de lundo, havas
la kapablo esprimi solvon

266
00:12:38,790 --> 00:12:42,480
tamen, ni devas nur tweak
la difino de nia stako

267
00:12:42,480 --> 00:12:46,840
por ne esti iu malmola-kodita tabelo,
sed nur por stoki adreson.

268
00:12:46,840 --> 00:12:47,890
>> Nun kial estas tio?

269
00:12:47,890 --> 00:12:51,690
Nun ni nur devas esti komforta kun
la fakto ke kiam mia programo kuras,

270
00:12:51,690 --> 00:12:53,730
Mi supozeble tuj
devas demandi la homaj,

271
00:12:53,730 --> 00:12:55,110
kiom da ciferoj vi volas konservi?

272
00:12:55,110 --> 00:12:56,776
Do la enigo devas veni de ie.

273
00:12:56,776 --> 00:12:59,140
Sed iam mi scias ke
nombro, tiam mi povas nur

274
00:12:59,140 --> 00:13:02,470
uzu kio funkcii doni
mi eron de memoro?

275
00:13:02,470 --> 00:13:03,580
Mi povas uzi malloc.

276
00:13:03,580 --> 00:13:06,710
Kaj mi povas diri ajnan numeron de
bajtoj mi volas reveni por tiuj Nths.

277
00:13:06,710 --> 00:13:10,910
Kaj ĉiuj mi devi stoki en la nombroj
ŝanĝiĝema tie ene de ĉi struct

278
00:13:10,910 --> 00:13:13,480
devus esti kio?

279
00:13:13,480 --> 00:13:18,440
Kio reale iras en la
nombroj en tiu scenaro?

280
00:13:18,440 --> 00:13:21,300
Yeah, montrilo al la unua
bitoko de tiu bloko de memoro,

281
00:13:21,300 --> 00:13:24,940
aŭ pli specife, la adreso
de la unua el tiuj bajtoj.

282
00:13:24,940 --> 00:13:27,300
Ne gravas se ĝi estas unu
bajto aŭ miliardoj bajtoj,

283
00:13:27,300 --> 00:13:28,890
Mi nur devas zorgi pri la unua.

284
00:13:28,890 --> 00:13:31,530
Pro kio malloc garantiojn kaj
mia mastruma sistemo garantiojn,

285
00:13:31,530 --> 00:13:34,170
estas ke la eron de memoro
akiri, ĝi tuj estu apudaj.

286
00:13:34,170 --> 00:13:35,378
Tie ne iras esti breĉoj.

287
00:13:35,378 --> 00:13:38,576
Do se mi petis 50
bitokoj aŭ 1000 bitokoj,

288
00:13:38,576 --> 00:13:40,450
ili cxiuj iras al esti
malantaŭo al malantaŭo al dorso.

289
00:13:40,450 --> 00:13:44,500
Kaj tiel longe kiel mi memoras kiom granda, kiom
multe mi petis, mi nur bezonas scii

290
00:13:44,500 --> 00:13:46,230
Estas la unua tia adreso.

291
00:13:46,230 --> 00:13:48,660
>> Do nun ni havas la kapablecon en kodo.

292
00:13:48,660 --> 00:13:51,280
Kvankam, ĝi estas tuj prenos nin
pli tempon skribi ĉi supre,

293
00:13:51,280 --> 00:13:55,900
ni nun povis reallocate ke memoron per
nur stokante malsaman adreson tie

294
00:13:55,900 --> 00:13:59,060
se ni volas pli grandan aŭ eĉ
pli malgrandan eron de memoro.

295
00:13:59,060 --> 00:14:00,170
Do jen al komerco ekstere.

296
00:14:00,170 --> 00:14:01,360
Nun ni akiras dinamismo.

297
00:14:01,360 --> 00:14:03,350
Ni ankoraŭ havas
contiguousness Mi asertante.

298
00:14:03,350 --> 00:14:05,881
Ĉar malloc donos nin
apudan eron de memoro.

299
00:14:05,881 --> 00:14:08,630
Sed ĉi tiu tuj estos doloro en
la kolo por ni, la programisto,

300
00:14:08,630 --> 00:14:09,770
efektive programi supren.

301
00:14:09,770 --> 00:14:10,730
Estas nur pli laboro.

302
00:14:10,730 --> 00:14:13,930
Ni bezonas kodo parenca al kio mi estis
batante eksteren nur antaŭ momento.

303
00:14:13,930 --> 00:14:16,120
Tre doable, sed aldonas kompleksecon.

304
00:14:16,120 --> 00:14:19,520
Kaj tiel ellaboranto tempo, programisto
tempo estas alia rimedo

305
00:14:19,520 --> 00:14:22,520
ke ni eble bezonas por elspezi
iun tempon akiri novajn funkciojn.

306
00:14:22,520 --> 00:14:24,020
Kaj tiam kompreneble estas atendovico.

307
00:14:24,020 --> 00:14:26,227
Ni ne iros en tiun
en multe da detalo.

308
00:14:26,227 --> 00:14:27,560
Sed ĝi estas tre simila en spirito.

309
00:14:27,560 --> 00:14:31,220
Mi povus praktikigi atendovico, kaj
lia responda operacioj,

310
00:14:31,220 --> 00:14:35,660
enqueue aŭ dequeue, kiel aldoni aŭ forigi,
ĝi estas nur amatoro maniero diri ĝin,

311
00:14:35,660 --> 00:14:38,100
enqueue aŭ dequeue, jene.

312
00:14:38,100 --> 00:14:41,170
Mi povas nur doni min struct
ke denove havas nombro de tabelo,

313
00:14:41,170 --> 00:14:44,000
ke denove havas grandecon,
sed kial mi nun bezonas

314
00:14:44,000 --> 00:14:46,940
konservi trako de la fronto de atendovico?

315
00:14:46,940 --> 00:14:50,630
Mi ne bezonas scii
la fronto de mia stako.

316
00:14:50,630 --> 00:14:53,570
Nu, se mi denove por
queue-- ni nur malfacile

317
00:14:53,570 --> 00:14:57,870
programi ĝin havante kiel kvin
entjeroj tien potenciale.

318
00:14:57,870 --> 00:15:00,940
Do tiu estas nulo, unu, du, tri, kvar.

319
00:15:00,940 --> 00:15:03,430
Ĉi tuj estos
nomitaj nombroj denove.

320
00:15:03,430 --> 00:15:06,940
Kaj tiu estos nomata grandeco.

321
00:15:06,940 --> 00:15:10,056
>> Kial estas ne sufiĉa
havi nur grandecon?

322
00:15:10,056 --> 00:15:11,680
Nu, ni puŝi tiujn samajn numerojn sur.

323
00:15:11,680 --> 00:15:14,220
Do mi pushed-- mi enqueued, aŭ puŝis.

324
00:15:14,220 --> 00:15:20,150
Nun mi enqueue 50, kaj poste
51, kaj tiam 61, kaj dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Do jen enqueue.

326
00:15:21,070 --> 00:15:23,176
Mi enqueued 50, tiam 51, do 61.

327
00:15:23,176 --> 00:15:25,050
Kaj kiu aspektas identa
al pilo tiel longe,

328
00:15:25,050 --> 00:15:27,190
krom mi bezonas fari unu ŝanĝo.

329
00:15:27,190 --> 00:15:33,680
Mi bezonas ĝisdatigi ĉi tiu grandeco, do mi iros
de nulo al unu al du al tri nun.

330
00:15:33,680 --> 00:15:35,760
Kiel mi dequeue?

331
00:15:35,760 --> 00:15:36,890
Kio okazas kun dequeue?

332
00:15:36,890 --> 00:15:41,950
Kiu devus elspezi tiun liston unua
se ĝi estas la linio je la Apple Store?

333
00:15:41,950 --> 00:15:42,780
Do 50.

334
00:15:42,780 --> 00:15:44,700
Do ĝi estas speco de trickier tiu tempo.

335
00:15:44,700 --> 00:15:47,880
Dum lasta tempo ĝi estis ekstra
facile simple fari grandeco minus unu,

336
00:15:47,880 --> 00:15:51,440
Mi alvenas al la finon de mia tabelo efike
kie la numeroj estas, ĝi eltiras 61.

337
00:15:51,440 --> 00:15:52,920
Sed mi ne volas forigi 61.

338
00:15:52,920 --> 00:15:55,030
Mi volas preni 50, kiu
estis tie je 5:00 atm

339
00:15:55,030 --> 00:15:56,790
laŭliniigi por la
nova iPhone aŭ whatnot.

340
00:15:56,790 --> 00:16:01,200
Kaj tiel seniĝi de 50, mi
povas ne nur faru tion, ĉu ne?

341
00:16:01,200 --> 00:16:02,547
Mi povas transiri el 50.

342
00:16:02,547 --> 00:16:04,380
Sed ni ĵus diris nin
ne devas esti tiel anal

343
00:16:04,380 --> 00:16:06,330
kiel skrapi eksteren aŭ kaŝi la datumojn.

344
00:16:06,330 --> 00:16:08,090
Ni povas simple forgesos kie ĝi estas.

345
00:16:08,090 --> 00:16:12,330
>> Sed se mi ŝanĝas mian grandecon nun al
du, estas tiu sufiĉa informo

346
00:16:12,330 --> 00:16:15,711
scii kio okazas en mia vosto?

347
00:16:15,711 --> 00:16:16,680
Ne vere.

348
00:16:16,680 --> 00:16:19,830
Kiel mia esas du, sed
tio rilatas al la atendovico komenci,

349
00:16:19,830 --> 00:16:22,980
precipe se mi ankoraŭ havas
tiujn samajn numerojn en memoro.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Do mi devas memori
nun kie la fronto estas.

352
00:16:27,090 --> 00:16:29,630
Kaj tiel kiel mi proponis supren
tie, ni ĵus nomis

353
00:16:29,630 --> 00:16:33,729
Na fronto, kies komencaj
valoro devus esti kio?

354
00:16:33,729 --> 00:16:35,270
Nulo, nur la komenco de la listo.

355
00:16:35,270 --> 00:16:40,876
Sed nun krom decrementing
la grandeco, ni ĵus pliigo la fronto.

356
00:16:40,876 --> 00:16:42,000
Nun jen alia problemo.

357
00:16:42,000 --> 00:16:43,030
Do iam mi plu iri.

358
00:16:43,030 --> 00:16:47,520
Supozi ĉi estas la nombro de
kiel 121, 124, kaj tiam, Dammit,

359
00:16:47,520 --> 00:16:48,610
Mi estas el spaco.

360
00:16:48,610 --> 00:16:50,390
Sed atendu momenton, mi ne estas.

361
00:16:50,390 --> 00:16:55,630
Do je ĉi tiu punkto en la rakonto,
supozas ke la grandeco estas unu, du,

362
00:16:55,630 --> 00:17:00,370
tri, kvar, do supozu ke la
grandeco estas kvar, la fronto estas unu,

363
00:17:00,370 --> 00:17:01,621
do 51 estas ĉe la fronto.

364
00:17:01,621 --> 00:17:04,329
Mi volas meti alian numeron tie,
sed, Dammit, mi estos for de spaco.

365
00:17:04,329 --> 00:17:06,710
Sed mi ne vere, rajto?

366
00:17:06,710 --> 00:17:11,192
Kie mi povus meti iun
aldona valoro, kiel 171?

367
00:17:11,192 --> 00:17:13,400
Jes, mi povis nur speco de
reiri tien, ĉu ne?

368
00:17:13,400 --> 00:17:18,161
Kaj tiam transiri el la 50, aŭ
simple anstataŭigi ĝin per 171.

369
00:17:18,161 --> 00:17:20,410
Kaj se vi scivolas kial
niaj nombroj akiris tiom hazarda,

370
00:17:20,410 --> 00:17:24,150
tiuj estas kutime prenita komputilo
scienco kursojn en Harvard post CS50.

371
00:17:24,150 --> 00:17:27,510
Sed tio estis bona optimumigo,
ĉar nun mi ne malŝparas spacon.

372
00:17:27,510 --> 00:17:30,750
Mi ankoraŭ devas memori
kiom granda afero estas entute.

373
00:17:30,750 --> 00:17:31,500
Estas kvin entute.

374
00:17:31,500 --> 00:17:33,375
Ĉar mi ne volas
komenci superskribi 51.

375
00:17:33,375 --> 00:17:36,260
Do nun mi restas ekstere de spaco,
do la saman problemon antaŭe.

376
00:17:36,260 --> 00:17:39,140
Sed vi povas vidi kiel nun
en via kodo, vi probable

377
00:17:39,140 --> 00:17:41,910
devas skribi iom pli
komplekseco fari ke okazas.

378
00:17:41,910 --> 00:17:44,510
Kaj fakte, kion operatoro
en C probable lasas

379
00:17:44,510 --> 00:17:48,110
vi magie fari ĉi la circularidad?

380
00:17:48,110 --> 00:17:50,160
Yeah la module operatoro,
la procentoj signo.

381
00:17:50,160 --> 00:17:53,160
Do kio estas speco de cool pri atendovico,
eĉ se ni plenumas desegnante tabeloj

382
00:17:53,160 --> 00:17:56,520
kiel tiuj kiel rektoj, se vi
ia pensas pri tio kiel kurbigante

383
00:17:56,520 --> 00:18:00,341
ĉirkaŭe kiel cirklo, tiam nur
intuicie gxi ia laboras mense

384
00:18:00,341 --> 00:18:01,590
Mi pensas iom pli pure.

385
00:18:01,590 --> 00:18:05,190
Vi ankoraŭ devas apliki
ke mensa modelo en kodo.

386
00:18:05,190 --> 00:18:07,550
Do ne estas tiel malfacila,
finfine, al implementar,

387
00:18:07,550 --> 00:18:12,430
sed ni ankoraŭ perdi la size-- prefere, la
kapablo regrandigi, krom se ni faras tion.

388
00:18:12,430 --> 00:18:15,310
>> Ni devas forigi la tabelo, ni
anstataŭigi ĝin per sola puntero,

389
00:18:15,310 --> 00:18:20,010
kaj tiam ie en mia kodo mi devas
alvokon kio funkcii por fakte krei

390
00:18:20,010 --> 00:18:23,720
la tabelo nomita nombroj?

391
00:18:23,720 --> 00:18:26,190
Malloc, aŭ iu simila
funkcio, ĝuste.

392
00:18:26,190 --> 00:18:30,481
Demandojn sur stakoj aŭ vostoj.

393
00:18:30,481 --> 00:18:30,980
Yeah?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Bona demando.

396
00:18:34,240 --> 00:18:35,830
Kio module estus vi uzas ĉi tie.

397
00:18:35,830 --> 00:18:38,520
Do ĝenerale, kiam oni uzas
mod, vi farus

398
00:18:38,520 --> 00:18:40,620
kun la grandeco de la
tutaj datumstrukturo.

399
00:18:40,620 --> 00:18:44,120
Do ion kiel kvin aŭ kapablo, se
ĝi estas konstanta, probable implikitaj.

400
00:18:44,120 --> 00:18:47,100
Sed ĝuste faras module kvin
probable ne suficxus,

401
00:18:47,100 --> 00:18:51,380
ĉar ni bezonas scii ĉu ni
envolver ĉirkaŭe ĉi tie aŭ ĉi tie aŭ tie.

402
00:18:51,380 --> 00:18:54,160
Do vi probable ankaŭ
tuj volas engaĝi

403
00:18:54,160 --> 00:18:57,220
la grandeco de la afero, aŭ
la fronto variablo tiel.

404
00:18:57,220 --> 00:19:00,140
Do estas nur tiu relative
simpla aritmetiko esprimo,

405
00:19:00,140 --> 00:19:02,000
sed module estus la ŝlosilo ingredienco.

406
00:19:02,000 --> 00:19:03,330
>> Tiel mallonga filmo se vi volas.

407
00:19:03,330 --> 00:19:05,780
Kuraĝigo kiu iuj
uloj de alia universitato

408
00:19:05,780 --> 00:19:08,060
kunmetis ke ni
adaptitaj por ĉi tiu diskuto.

409
00:19:08,060 --> 00:19:12,630
Ĝi implikas Jack lernas la
faktoj pri atendovicoj kaj statistikojn.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILMO: Iam,
ekzistis ulo kiu nomiĝas Jack.

412
00:19:21,890 --> 00:19:25,330
Kiam ĝi venis al amikiĝi,
Jack ne havas povoscion.

413
00:19:25,330 --> 00:19:28,220
Do Joĉjo iris paroli kun la
plej populara ulo li sciis.

414
00:19:28,220 --> 00:19:30,920
Li iris al Lou kaj demandis: Kion mi faru?

415
00:19:30,920 --> 00:19:33,400
Lou vidis ke lia amiko
Estis vere premata.

416
00:19:33,400 --> 00:19:36,050
Nu, li komencis, ĵus
rigardu, kiel vi estas vestita.

417
00:19:36,050 --> 00:19:38,680
Ĉu vi ne havas ajnan vestoj
kun malsama rigardo?

418
00:19:38,680 --> 00:19:39,660
Jes, diris Joĉjo.

419
00:19:39,660 --> 00:19:40,840
Mi certas fari.

420
00:19:40,840 --> 00:19:43,320
Venu al mia domo kaj
Mi montros ilin al vi.

421
00:19:43,320 --> 00:19:44,550
Do ili iris al Jack.

422
00:19:44,550 --> 00:19:47,520
Kaj Jack montris Lou la skatolo
kie li observis cxiujn liajn ĉemizojn,

423
00:19:47,520 --> 00:19:49,260
kaj lia pantalono, kaj lia ŝtrumpetoj.

424
00:19:49,260 --> 00:19:52,290
Lou diris, mi vidas ke vi havas
ĉiujn viajn vestojn en amaso.

425
00:19:52,290 --> 00:19:54,870
Kial ne vi portas iuj
aliaj unufoje en kelktempe?

426
00:19:54,870 --> 00:19:58,020
>> Joĉjo diris, bone, kiam mi
forigi vestojn kaj ŝtrumpetoj,

427
00:19:58,020 --> 00:20:00,780
Mi lavos ilin kaj metis
ilin en la skatolon.

428
00:20:00,780 --> 00:20:03,210
Tiam venas la sekva
mateno, kaj supre mi hop.

429
00:20:03,210 --> 00:20:06,380
Mi iras al la skatolo kaj akiri
miaj vestoj de la supro.

430
00:20:06,380 --> 00:20:09,070
Lou rapide komprenis
la problemo kun Jack.

431
00:20:09,070 --> 00:20:12,080
Li tenis vestojn, KD-a,
kaj libroj en la stako.

432
00:20:12,080 --> 00:20:14,420
Kiam li atingis por
io por legi aŭ surhavi,

433
00:20:14,420 --> 00:20:17,100
li elektus la supro libro aŭ subvestoj.

434
00:20:17,100 --> 00:20:19,500
Kiam do li faris, li
metus lin rekte reen.

435
00:20:19,500 --> 00:20:21,970
Reen ĝi irus, sur supro de la stako.

436
00:20:21,970 --> 00:20:24,460
Mi konas la solvon,
diris triumfa Loud.

437
00:20:24,460 --> 00:20:27,090
Vi devas lerni
ekuzi atendovico.

438
00:20:27,090 --> 00:20:29,870
Lou prenis Jack vestojn kaj
pendigis ilin en la ŝranko.

439
00:20:29,870 --> 00:20:32,710
Kaj kiam li malplenigis
la skatolon, li simple forĵetis ĝin.

440
00:20:32,710 --> 00:20:36,500
>> Tiam li diris, nun Joĉjo, fine de
la tago, meti viajn vestojn en la maldekstra

441
00:20:36,500 --> 00:20:37,990
kiam vi metis ilin.

442
00:20:37,990 --> 00:20:41,300
Tiam morgaŭ matene kiam vi
vidi la sunlumon atingi viajn vestojn

443
00:20:41,300 --> 00:20:43,440
dekstre, de la fino de la linio.

444
00:20:43,440 --> 00:20:44,880
Ĉu vi ne vidas? diris Lou.

445
00:20:44,880 --> 00:20:46,370
Estos tiel bela.

446
00:20:46,370 --> 00:20:49,770
Vi surhavas ĉiu iam
antaŭ vi surhavas ion dufoje.

447
00:20:49,770 --> 00:20:52,670
Kaj kun ĉio en atendovicoj
en sia ŝranko kaj breto,

448
00:20:52,670 --> 00:20:55,160
Jack komencis senti
tute certa pri si.

449
00:20:55,160 --> 00:20:59,720
Ĉiu danke al Lou kaj
lia mirinda atendovico.

450
00:20:59,720 --> 00:21:01,220
Parolanto 1: Bone, estas adorable.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Do kio estis vere iranta
sur sub la kapuĉo nun?

453
00:21:10,080 --> 00:21:12,370
Ke ni havas punteros,
ke ni havas malloc,

454
00:21:12,370 --> 00:21:15,680
ke ni havas la eblon krei
pecoj de memoro por ni mem

455
00:21:15,680 --> 00:21:16,344
dinamike.

456
00:21:16,344 --> 00:21:18,510
Do tiu estas bildo ni
duonvidis ĵus la alia tago.

457
00:21:18,510 --> 00:21:21,180
Ni ne vere logxas
sur ĝi, sed tiu bildo

458
00:21:21,180 --> 00:21:24,180
estis daŭriganta sub
la kapuĉo por semajnoj nun.

459
00:21:24,180 --> 00:21:27,050
Kaj tiel tio reprezentas, nur
rektangulo kiu ni desegnas,

460
00:21:27,050 --> 00:21:28,180
via komputilo la memoro.

461
00:21:28,180 --> 00:21:31,850
Kaj eble via komputilo, aŭ CS50
ID, havas gigabajto de memoro aŭ RAM

462
00:21:31,850 --> 00:21:33,050
aŭ du gigabajtoj aŭ kvar.

463
00:21:33,050 --> 00:21:34,450
Fakte ne gravas.

464
00:21:34,450 --> 00:21:37,240
Via operaciumo
Windows aŭ Mac VIN aŭ Linukso,

465
00:21:37,240 --> 00:21:41,120
esence permesas via programo
pensi ke ĝi havas atingo

466
00:21:41,120 --> 00:21:42,982
al la tuteco de
via komputilo la memoro,

467
00:21:42,982 --> 00:21:45,440
Eĉ kvankam vi povus esti kurante
multoblaj programoj samtempe.

468
00:21:45,440 --> 00:21:46,990
Do fakte, tio ne vere funkcias.

469
00:21:46,990 --> 00:21:49,448
Sed ĝi estas speco de iluzio
donita al ĉiuj viaj programoj.

470
00:21:49,448 --> 00:21:53,110
Do se vi havus du koncertoj de RAM, ĉi
tale la komputilo povus pensi pri tio.

471
00:21:53,110 --> 00:21:57,110
>> Nun hazarde, unu el tiuj
aferoj, unu el tiuj segmentoj de memoro,

472
00:21:57,110 --> 00:21:58,350
nomata stako.

473
00:21:58,350 --> 00:22:01,680
Kaj ja neniu tempo
tiel ege skribe kodo

474
00:22:01,680 --> 00:22:05,900
ke vi nomiĝas
funkcio, ekzemple ĉefa.

475
00:22:05,900 --> 00:22:08,410
Memoru ke ajna tempo mi havas
tirita komputilo memoro,

476
00:22:08,410 --> 00:22:10,640
Mi ĉiam tiri ian
duono de rektangulo tie

477
00:22:10,640 --> 00:22:12,520
kaj ne ĝenas parolante
pri kio estas supre.

478
00:22:12,520 --> 00:22:15,980
Ĉar kiam ĉefa nomas, mi postulas
ke vi akiras ĉi Sliver de memoro

479
00:22:15,980 --> 00:22:16,970
kiu iras malsupren tie.

480
00:22:16,970 --> 00:22:20,650
Kaj se ĉefa nomas funkcio
kiel interŝanĝa, bone interŝanĝa iras tien.

481
00:22:20,650 --> 00:22:23,720
Kaj ĝi rezultas, jen
kie ĝi estas fini.

482
00:22:23,720 --> 00:22:26,277
Sur iun nomita parva
ene de via komputilo la memoro.

483
00:22:26,277 --> 00:22:28,360
Nun je la fino de la tago,
tio decas adresoj.

484
00:22:28,360 --> 00:22:30,680
Estas kiel bitoko nulo,
bajto unu, bajto 2 miliardoj.

485
00:22:30,680 --> 00:22:33,130
Sed se vi pensas pri ĝi
kiel tiu rektangula objekto,

486
00:22:33,130 --> 00:22:35,130
ĉiuj ni faras ĉiun
tempo ni nomas funkcio estas

487
00:22:35,130 --> 00:22:37,180
layering nova tranĉaĵo de memoro.

488
00:22:37,180 --> 00:22:41,700
Ni donas domadministranto tranĉaĵo
de lia propra memoro por labori kun.

489
00:22:41,700 --> 00:22:44,490
>> Kaj memoru ke nun tiu estas grava.

490
00:22:44,490 --> 00:22:46,400
Ĉar se ni havas
io kiel interŝanĝa

491
00:22:46,400 --> 00:22:51,610
kaj du lokaj variabloj kiel A kaj B kaj
ni ŝanĝas tiujn valorojn de unu kaj du

492
00:22:51,610 --> 00:22:55,130
du kaj unu, revoko
ke kiam interŝanĝa revenas,

493
00:22:55,130 --> 00:22:58,330
ĝi estas kvazaŭ ĉi tranĉaĵo
de memoro estas nur irita.

494
00:22:58,330 --> 00:23:00,080
En realeco, ĝi estas ankoraŭ
tie forensically.

495
00:23:00,080 --> 00:23:01,940
Kaj io ankoraŭ efektive tie.

496
00:23:01,940 --> 00:23:05,410
Sed koncepte, tio estas tiel
kvankam ĝi estas tute irita.

497
00:23:05,410 --> 00:23:10,910
Kaj tiel ĉefa ne konas iun el la verkon
kio okazis en tiu interŝanĝa funkcio,

498
00:23:10,910 --> 00:23:14,890
krom se ĝi estas vere pasis en tiuj
argumentojn per montrilo aŭ referenco.

499
00:23:14,890 --> 00:23:17,790
Nun, la fundamenta solvo
al tiu problemo kun swap

500
00:23:17,790 --> 00:23:19,970
preterpasas aferoj por adreso.

501
00:23:19,970 --> 00:23:23,250
Sed rezultas, tro, kio estas
daŭras jam super tiu parto

502
00:23:23,250 --> 00:23:26,330
de la rektangulo ĉiu ĉi tiu tempo estas
tamen ekzistas pli memoro tie supre.

503
00:23:26,330 --> 00:23:28,790
Kaj kiam vi dinamike
rezervi memoron,

504
00:23:28,790 --> 00:23:32,020
ĉu ĝi estas ene de GetString, kiu
ni estis farante por vi en la CS50

505
00:23:32,020 --> 00:23:34,710
biblioteko, aŭ se vi infanoj
vokas malloc kaj petu

506
00:23:34,710 --> 00:23:37,950
la operaciumo por eron de
memoro, ĝi ne venas de la stako.

507
00:23:37,950 --> 00:23:40,960
Ĝi venas de alia loko
en via komputilo la memoro

508
00:23:40,960 --> 00:23:42,220
ke nomiĝas la havaĵo.

509
00:23:42,220 --> 00:23:43,430
Kaj tio ne ajna malsama.

510
00:23:43,430 --> 00:23:44,285
Ĝi estas la sama RAM.

511
00:23:44,285 --> 00:23:45,160
Ĝi estas la sama memoro.

512
00:23:45,160 --> 00:23:49,080
Estas nur la RAM tio estas supren
tie anstataŭ malsupren tie.

513
00:23:49,080 --> 00:23:50,750
>> Kaj tiel kion tio signifas?

514
00:23:50,750 --> 00:23:53,650
Nu, se via komputilo havas
finia kvanto de memoro

515
00:23:53,650 --> 00:23:57,450
kaj la pilo kreskas supren, tiel
paroli, kaj la havaĵon, laŭ

516
00:23:57,450 --> 00:23:59,349
al ĉi sago, kreskas malsupren.

517
00:23:59,349 --> 00:24:01,140
En aliaj vortoj, ĉiu
tempo vi vokas malloc,

518
00:24:01,140 --> 00:24:03,430
vi transdonitan tranĉaĵo
de memoro de supre,

519
00:24:03,430 --> 00:24:06,630
tiam eble iom pli malalta, tiam iom
malsupra, ĉiufoje vi nomas malloc,

520
00:24:06,630 --> 00:24:10,100
la amaso, estas uzado,
estas speco de kultivado,

521
00:24:10,100 --> 00:24:11,950
kreskanta pli kaj pli proksimen al kio?

522
00:24:11,950 --> 00:24:13,382
La pilo.

523
00:24:13,382 --> 00:24:14,840
Do ĉu tio ŝajnas kiel bona ideo?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Mi volas diri, kie ĝi ne estas vere klara
kion alian vi povas fari se vi nur

526
00:24:22,140 --> 00:24:23,910
havi finia kvanto de memoro.

527
00:24:23,910 --> 00:24:25,200
Sed tio estas certe malbona.

528
00:24:25,200 --> 00:24:27,920
Tiuj du sagoj estas sur
kraŝi kurson por unu alia.

529
00:24:27,920 --> 00:24:31,930
>> Kaj ĝi rezultas ke malbona ulo, uloj kiuj
estas aparte bona pri programado,

530
00:24:31,930 --> 00:24:36,140
kaj provanta haki en komputiloj,
povas ekspluati tiun realecon.

531
00:24:36,140 --> 00:24:38,290
Fakte, ni konsideru
iom fragmento.

532
00:24:38,290 --> 00:24:41,350
Do tiu estas ekzemplo vi povas legi
pri pli detale en Vikipedio.

533
00:24:41,350 --> 00:24:43,100
Ni atentigi vin je la
artikolo se scivola.

534
00:24:43,100 --> 00:24:45,650
Sed estas atako ĝenerale
konata kiel la buffer overflow ke

535
00:24:45,650 --> 00:24:49,570
ekzistis tiel longe kiel homoj
havis la kapablon manipuli

536
00:24:49,570 --> 00:24:53,120
komputilo memoro, speciale en C.
Do temas pri tre arbitra programo,

537
00:24:53,120 --> 00:24:55,130
sed ni legis ĝin de malsupre supren.

538
00:24:55,130 --> 00:24:57,650
Ĉefa en argc char stelo argv.

539
00:24:57,650 --> 00:24:59,830
Do estas programo kiu prenas
komandliniajn argumentojn.

540
00:24:59,830 --> 00:25:03,620
Kaj ĉiuj ĉefaj does ŝajne estas alvoko
funkcio, nomas ĝin F por simpleco.

541
00:25:03,620 --> 00:25:04,610
Kaj ĝi pasas en kio?

542
00:25:04,610 --> 00:25:05,490
Argv de unu.

543
00:25:05,490 --> 00:25:09,320
Do pasas en F ajn
la vorto estas ke la uzanto tajpas

544
00:25:09,320 --> 00:25:11,500
ĉe la prompto post la
programo nomon.

545
00:25:11,500 --> 00:25:15,730
Tiel kiel Cezaro aŭ Vigenère, kiu
vi eble memoras faras kun argv.

546
00:25:15,730 --> 00:25:16,680
>> Do kio estas F?

547
00:25:16,680 --> 00:25:19,760
F prenas en ĉeno
kiel lia sola argumento,

548
00:25:19,760 --> 00:25:22,100
AKA char stelo, sama
afero, kiel ĉeno.

549
00:25:22,100 --> 00:25:24,920
Kaj ĝi nomiĝas arbitre
trinkejo en tiu ekzemplo.

550
00:25:24,920 --> 00:25:27,710
Kaj tiam char c 12,
nur en laiko La terminoj,

551
00:25:27,710 --> 00:25:31,750
kio estas char c krampo 12 faras por ni?

552
00:25:31,750 --> 00:25:33,440
Kio ĝi faras?

553
00:25:33,440 --> 00:25:36,490
Asignante memoron, specife
12 bajtoj por 12 signoj.

554
00:25:36,490 --> 00:25:36,990
Ekzakte.

555
00:25:36,990 --> 00:25:40,000
Kaj tiam la lasta linio, veku kaj
kopion, vi probable ne vidis.

556
00:25:40,000 --> 00:25:43,360
Ĉi estas ĉeno kopion
funkcio kies celo en la vivo

557
00:25:43,360 --> 00:25:48,160
estas kopii lian duan argumenton
en lia unua argumento,

558
00:25:48,160 --> 00:25:51,190
sed nur supren al
iu numero de bajtoj.

559
00:25:51,190 --> 00:25:53,860
Do la tria argumento diras,
kiom da bajtoj devus vi kopias?

560
00:25:53,860 --> 00:25:56,720
La longo de trinkejo,
kiom la uzanto tajpas en.

561
00:25:56,720 --> 00:25:59,320
Kaj la enhavo de
bari, ke kordoj, estas

562
00:25:59,320 --> 00:26:02,330
kopiis en la memoro indik ĉe C.

563
00:26:02,330 --> 00:26:04,060
>> Do tio ŝajnas ia stulta, kaj ĝi estas.

564
00:26:04,060 --> 00:26:06,300
Ĝi estas elpensita ekzemplo,
sed estas reprezentanto

565
00:26:06,300 --> 00:26:10,100
de klaso de atako vektoroj,
maniero de ataki programon.

566
00:26:10,100 --> 00:26:15,050
Ĉiuj estas belaj kaj bonaj se la uzanto
tipoj en vorton kiu estas 11 karakteroj

567
00:26:15,050 --> 00:26:18,040
aŭ malpli, plus la backslash nula.

568
00:26:18,040 --> 00:26:22,830
Kio se la uzanto tajpas en pli ol
11 aŭ 12 aŭ 20 aŭ 50 signoj?

569
00:26:22,830 --> 00:26:25,090
Kio estas tio programo faros?

570
00:26:25,090 --> 00:26:29,360
Potenciale seg kulpo. Ĝi tuj
blinde kopii ĉion en trinkejo supren

571
00:26:29,360 --> 00:26:31,750
al ĝia longo, kiu estas
laŭvorte ĉio en trinkejo,

572
00:26:31,750 --> 00:26:36,307
en la adreson notita al C. Sed C
nur preventa donita kiel 12 bajtoj.

573
00:26:36,307 --> 00:26:37,640
Sed estas neniu plia ĉeko.

574
00:26:37,640 --> 00:26:38,700
Mankas se kondiĉoj.

575
00:26:38,700 --> 00:26:40,580
Mankas eraro kontrolanta tie.

576
00:26:40,580 --> 00:26:43,270
>> Kaj tiel kion ĉi programo estas
tuj fari estas simple blinde

577
00:26:43,270 --> 00:26:45,750
kopii ion al la aliaj.

578
00:26:45,750 --> 00:26:47,880
Kaj do se ni desegni tiun
kiel bildo, jen

579
00:26:47,880 --> 00:26:49,860
nur Sliver de la memoro spaco.

580
00:26:49,860 --> 00:26:53,470
Do rimarki ĉe la fundo, ni
havi la loka variablo trinkejo.

581
00:26:53,470 --> 00:26:57,330
Por ke puntero ke tuj store--
prefere ke lokaj argumento tio

582
00:26:57,330 --> 00:26:58,672
tuj stoki la kordo trinkejo.

583
00:26:58,672 --> 00:27:00,380
Kaj tiam rimarkos nur
super ĝi en pilo,

584
00:27:00,380 --> 00:27:02,505
ĉar ĉiufoje kiam vi petos
por memoro sur la stako,

585
00:27:02,505 --> 00:27:04,310
iras iomete
super ĝi bilde,

586
00:27:04,310 --> 00:27:06,270
avizo ke ni havas 12 bajtoj tie.

587
00:27:06,270 --> 00:27:10,690
La supro maldekstra estas C krampo nulo kaj
la dekstra malsupra unu estas C krampo 11.

588
00:27:10,690 --> 00:27:12,870
Tio estas nur kiamaniere la komputiloj
tuj metos ĝin.

589
00:27:12,870 --> 00:27:18,300
Do ĝuste intuicie, se stango havas pli
ol 12 karakteroj en totala, inkluzive de

590
00:27:18,300 --> 00:27:25,790
la backslash nulo, kie estas la
12 aŭ la C krampo 12 tuj iros?

591
00:27:25,790 --> 00:27:28,440
Aŭ prefere, kie estas la 12-a
karakteron aŭ la 13a karaktero,

592
00:27:28,440 --> 00:27:30,900
la centa karaktero iranta
por fini en la bildo?

593
00:27:30,900 --> 00:27:33,400
Supre aŭ malsupre?

594
00:27:33,400 --> 00:27:36,300
>> Bone, ĉar kvankam
la pilo mem kreskas pli,

595
00:27:36,300 --> 00:27:39,590
iam vi metis aĵon en
ĝin, por dezajno kialoj,

596
00:27:39,590 --> 00:27:41,294
metas la memoro de supro al fundo.

597
00:27:41,294 --> 00:27:44,460
Do se vi havas pli ol 12 bajtoj,
vi tuj komenci anstataŭigi trinkejo.

598
00:27:44,460 --> 00:27:47,280
Nun tio estas cimo, sed estas
Ne vere granda interkonsento.

599
00:27:47,280 --> 00:27:51,130
Sed estas granda interkonsento, ĉar estas
pli stuff daŭriganta en memoro.

600
00:27:51,130 --> 00:27:53,074
Do jen kiel ni povus
metis saluton, esti klara.

601
00:27:53,074 --> 00:27:54,490
Se mi tajpis en saluton ĉe la prompto.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash nulo, finas ene
tiuj 12 bajtoj, kaj ni estas súper sekura.

603
00:27:59,330 --> 00:28:00,330
Ĉio bonas.

604
00:28:00,330 --> 00:28:03,020
Sed se mi tajpas ion
plu, potenciale estas

605
00:28:03,020 --> 00:28:05,860
tuj rampas en trinkejo spaco.

606
00:28:05,860 --> 00:28:08,405
Sed pli malbone ankoraŭ, rezultas
el ĉiuj ĉi tempo,

607
00:28:08,405 --> 00:28:11,530
kvankam ni neniam parolis pri
ĝi, la pilo estas uzata por aliaj aferoj.

608
00:28:11,530 --> 00:28:13,560
Ĝi estas ne nur loka variabloj.

609
00:28:13,560 --> 00:28:15,100
>> C estas tre malalta nivelo lingvo.

610
00:28:15,100 --> 00:28:17,810
Kaj ia sekrete
uzas la stako ankaŭ

611
00:28:17,810 --> 00:28:21,260
memori kiam
funkcio estas vokita, kio

612
00:28:21,260 --> 00:28:26,040
la adreso estas de la antaŭa funkcio,
do ĝi povas salti reen al tiu funkcio.

613
00:28:26,040 --> 00:28:29,980
Do kiam ĉefa alvokoj interŝanĝi, inter
tion puŝis sur la pilo

614
00:28:29,980 --> 00:28:34,380
ne nur interŝanĝas lokaj variabloj,
aŭ ĝiaj argumentoj, ankaŭ sekrete puŝis

615
00:28:34,380 --> 00:28:37,510
sur la pilo kiel reprezentitaj
per la ruĝa tranĉaĵo tie,

616
00:28:37,510 --> 00:28:40,520
estas la adreso de ĉefa fizike
en via komputilo memoro,

617
00:28:40,520 --> 00:28:44,180
tiel ke kiam interŝanĝa estas farita, la komputilo
scias min devas reiri al ĉefa

618
00:28:44,180 --> 00:28:46,760
kaj fini ekzekuti la ĉefa funkcio.

619
00:28:46,760 --> 00:28:51,960
Do tiu estas danĝera nun, ĉar se
la uzanto tajpas en bone pli ol saluton,

620
00:28:51,960 --> 00:28:57,030
tia ke la uzanto enigo clobbers
aŭ overwrites ke ruĝa sekcio,

621
00:28:57,030 --> 00:28:59,820
logike se la komputilo
nur tuj blinde supozi

622
00:28:59,820 --> 00:29:03,830
ke la bitokoj en tiu ruĝa tranĉaĵo estas
la adreso al kiu devus reveni,

623
00:29:03,830 --> 00:29:09,020
kion se la kontraŭulo estas sufiĉe lerta aŭ
bonŝancon meti sekvenco de bajtoj

624
00:29:09,020 --> 00:29:13,450
tie kiu similas adreson,
sed ĝi estas la adreso de kodo

625
00:29:13,450 --> 00:29:18,730
ke li aŭ ŝi volas la komputilon
ekzekuti anstataŭ ĉefa?

626
00:29:18,730 --> 00:29:21,670
>> En aliaj vortoj, se kio la
uzanto estas tajpi ĉe la prompto:

627
00:29:21,670 --> 00:29:23,850
ne nur io
nenoca kiel saluton,

628
00:29:23,850 --> 00:29:28,210
sed estas reale kodo kiu estas ekvivalenta
forigi ĉiujn ĉi uzanto dosierojn?

629
00:29:28,210 --> 00:29:30,060
Aŭ retpoŝtu sian pasvorton al mi?

630
00:29:30,060 --> 00:29:31,940
Aŭ komenci ensalutanta ilia
pulsbatoj, dekstra?

631
00:29:31,940 --> 00:29:34,920
Iufoje vojo, ni kondiĉas hodiaŭ,
ke ili povus entajpi ne ĝuste saluton

632
00:29:34,920 --> 00:29:36,711
mondo aŭ ilia nomo,
ili povus esence

633
00:29:36,711 --> 00:29:39,570
Iam en kodo, kaj nuloj
tiuj, kiujn la komputilo

634
00:29:39,570 --> 00:29:43,450
erarojn por ambaŭ kodo kaj adreson.

635
00:29:43,450 --> 00:29:48,950
Do kvankam iom abstrakte, se la
uzanto tajpas en sufiĉe adversarial kodo

636
00:29:48,950 --> 00:29:52,330
ke ni ĝeneraligi tie kiel
A. A estas atako aŭ kontraŭuloj.

637
00:29:52,330 --> 00:29:53,140
Do simple malbonaj aĵoj.

638
00:29:53,140 --> 00:29:55,306
Ni ne zorgas pri la
nombroj aŭ la nuloj aŭ aĵoj

639
00:29:55,306 --> 00:29:59,470
hodiaŭ, tia ke vi finos
superskribi ke ruĝa sekcio,

640
00:29:59,470 --> 00:30:01,580
rimarkos ke sekvenco de bajtoj.

641
00:30:01,580 --> 00:30:05,020
O 835 C nulo ok nul.

642
00:30:05,020 --> 00:30:08,960
Kaj nun kiel Vikipedia artikolo tie
proponis, se vi nun vere komenci

643
00:30:08,960 --> 00:30:12,460
etikedi la bajtoj en via komputilo
memoro, kion la Vikipedia artikolo estas

644
00:30:12,460 --> 00:30:19,060
proponante estas ke, se la adreso
de tiu pinta maldekstra bajto estas 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> En aliaj vortoj, se la malbona ulo estas
sufiĉe lertaj kun lia aŭ ŝia kodo

646
00:30:22,200 --> 00:30:26,650
por fakte metis kelkajn tie ke
respondas al la adreso de la kodo

647
00:30:26,650 --> 00:30:29,180
li aŭ ŝi injektis
en la komputilo, vi

648
00:30:29,180 --> 00:30:31,050
povas trompi la komputilo
en fari ion.

649
00:30:31,050 --> 00:30:34,140
Forigado dosieroj, emailing
aferojn, snufante vian trafiko,

650
00:30:34,140 --> 00:30:36,710
laŭvorte povus esti io
injektita en la komputilo.

651
00:30:36,710 --> 00:30:39,220
Kaj tiel buffer overflow
atako en sia kerno

652
00:30:39,220 --> 00:30:43,530
estas nur stulta, stulta
supera de tabelo ke

653
00:30:43,530 --> 00:30:45,840
ne havis lian limojn kontrolis.

654
00:30:45,840 --> 00:30:48,850
Kaj tiu estas kio estas super danĝera
kaj samtempe super potencaj

655
00:30:48,850 --> 00:30:52,560
en C estas ke ni ja havas
aliro al anywhere en la memoro.

656
00:30:52,560 --> 00:30:55,320
Ĝi dependas de ni, la programistoj,
kiuj skribas la originala kodo

657
00:30:55,320 --> 00:30:59,330
kontroli la Darn longo de ajna
arrays ke ni manipulas.

658
00:30:59,330 --> 00:31:00,750
Do esti klara, kio estas la embaraso?

659
00:31:00,750 --> 00:31:03,190
Se ni ruliĝi reen al tiu
kodo, mi devus ne nur

660
00:31:03,190 --> 00:31:08,000
ŝanĝi la longo de trinkejo, kio
alie mi devus esti kontrolanta?

661
00:31:08,000 --> 00:31:10,620
Kion alian mi devus esti faranta al
malebligi ĉi atako tute?

662
00:31:10,620 --> 00:31:14,110
Mi ne volas simple blinde diri
ke vi kopiu kiel multaj bitokoj

663
00:31:14,110 --> 00:31:16,140
kiel estas la longo de trinkejo.

664
00:31:16,140 --> 00:31:18,910
Mi volas diri, kopiu kiel
multaj bitokoj kiel estas en trinkejo

665
00:31:18,910 --> 00:31:24,090
ĝis la asignitaj
memoro, aŭ la 12 maksimume.

666
00:31:24,090 --> 00:31:27,450
Do mi bezonas ian se kondiĉo
kiu faras kontrolu la longo de trinkejo,

667
00:31:27,450 --> 00:31:32,800
sed se ĝi superas 12, ni nur malfacile kodo
12 kiel la maksimuma ebla distanco.

668
00:31:32,800 --> 00:31:35,910
Alie la tn bufro
overflow atako povas okazi.

669
00:31:35,910 --> 00:31:38,451
Funde de tiuj diapozitivoj,
se vi estas scivola legi pli

670
00:31:38,451 --> 00:31:41,200
estas la fakta originala artikolo
se vi ŝatus preni rigardon.

671
00:31:41,200 --> 00:31:44,550
>> Sed nun, inter la prezoj
pagis refarigxis ineficiencias.

672
00:31:44,550 --> 00:31:46,680
Do kiu estis rapida
malalta nivelo rigardi kion

673
00:31:46,680 --> 00:31:49,709
problemoj povas ekesti nun ke ni
havas aliron al komputilo la memoro.

674
00:31:49,709 --> 00:31:51,750
Sed alia problemo ni
jam stumblis lunde

675
00:31:51,750 --> 00:31:53,800
Estis ĝuste la neefikecon
de ligitaj listo.

676
00:31:53,800 --> 00:31:56,019
Ni estas reen al lineara tempo.

677
00:31:56,019 --> 00:31:57,560
Ni ne plu havas apudan tabelon.

678
00:31:57,560 --> 00:31:58,980
Ni ne havas aliro aleatorio.

679
00:31:58,980 --> 00:32:00,710
Ni ne povas uzi kvadrata krampo skribmaniero.

680
00:32:00,710 --> 00:32:04,590
Ni laŭvorte devas uzi dum buklo
kiel la unu mi skribis antaŭ momento.

681
00:32:04,590 --> 00:32:09,740
Sed lunde, ni asertis, ke ni povas
rampi reen al la regno de efikeco

682
00:32:09,740 --> 00:32:13,040
atingi ion tio
logaritma eble, aŭ bona ankoraŭ,

683
00:32:13,040 --> 00:32:16,120
eble eĉ iu kiu estas
tn konstanta tempo.

684
00:32:16,120 --> 00:32:19,840
Do kiel ni povas fari tion de uzanta ĉi tiujn novajn
iloj, tiuj adresoj, tiuj punteros,

685
00:32:19,840 --> 00:32:22,210
kaj fadenigante aferojn de nia propra?

686
00:32:22,210 --> 00:32:23,960
Nu, supozu ke
tie, ĉi tiuj estas aro

687
00:32:23,960 --> 00:32:27,170
de nombroj kiun ni volas konservi en
datumstrukturo kaj serĉo kompetente.

688
00:32:27,170 --> 00:32:30,960
Ni povas absolute malantaŭenigi al semajno
du, ĵeti tiujn en tabelo,

689
00:32:30,960 --> 00:32:33,150
kaj serĉu ilin uzante binaran serĉon.

690
00:32:33,150 --> 00:32:34,040
Dividu kaj konkeru.

691
00:32:34,040 --> 00:32:37,720
Kaj fakte vi skribis
Binara serĉo en PSET3,

692
00:32:37,720 --> 00:32:40,100
kie implementado la trovaĵo programo.

693
00:32:40,100 --> 00:32:40,890
Sed vi scias kion.

694
00:32:40,890 --> 00:32:45,060
Tie estas speco de pli
ruza maniero fari tion.

695
00:32:45,060 --> 00:32:47,390
Ĝi estas iom pli
malnaiva kaj ĝi eble

696
00:32:47,390 --> 00:32:50,830
permesas al ni vidi kial duuma
serĉo estas tiel rapida.

697
00:32:50,830 --> 00:32:52,980
Unue, ni enkonduki
la nocio de arbo.

698
00:32:52,980 --> 00:32:54,730
Kiu kvankam en
realaĵo arboj ia

699
00:32:54,730 --> 00:32:57,730
kreski kiel tiu, en la mondo de komputilo
scienco ili ia kreski malsupren

700
00:32:57,730 --> 00:33:00,830
kiel familio arbo, kie vi havas
viaj avoj aŭ grandaj geavoj

701
00:33:00,830 --> 00:33:04,580
aŭ whatnot ĉe la supro, la patriarko kaj
la matriarko de la familio, nur unu

702
00:33:04,580 --> 00:33:07,930
tn radiko, nodo, sube
kiuj estas liaj filoj,

703
00:33:07,930 --> 00:33:11,442
sub kiu estas liaj infanoj, aŭ
liaj posteuloj pli ĝenerale.

704
00:33:11,442 --> 00:33:13,400
Kaj iu pendis ekstere
la fundo de la familio

705
00:33:13,400 --> 00:33:16,070
arbo, krom esti la
plej juna en la familio,

706
00:33:16,070 --> 00:33:19,520
povas ankaŭ esti nur genéricamente
vokis la folioj de la arbo.

707
00:33:19,520 --> 00:33:21,800
>> Do tio estas nur aro
de vortoj kaj difinoj

708
00:33:21,800 --> 00:33:25,790
por iu nomita arbo en komputilo
scienco, multe kiel familio arbo.

709
00:33:25,790 --> 00:33:28,770
Sed estas amatoro enkarniĝoj
de arboj, el kiuj unu

710
00:33:28,770 --> 00:33:30,780
nomiĝas binara serĉo arbo.

711
00:33:30,780 --> 00:33:34,380
Kaj vi povas ia tease
dise kio tion faras.

712
00:33:34,380 --> 00:33:37,180
Nu, estas duuma en kiu senco?

713
00:33:37,180 --> 00:33:41,455
Kien la duuma veni de tie?

714
00:33:41,455 --> 00:33:41,955
Pardonon?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Ĝi ne estas tiel multe kiel aŭ aŭ.

717
00:33:47,210 --> 00:33:52,000
Estas pli ke ĉiu el la nodoj ne havas
pli ol du infanojn, kiel ni vidos tie.

718
00:33:52,000 --> 00:33:54,990
Ĝenerale, tree-- kaj
viaj gepatroj kaj geavoj

719
00:33:54,990 --> 00:33:57,640
povas havi tiom da infanoj aŭ
nepoj kiel ili efektive volas,

720
00:33:57,640 --> 00:34:00,820
kaj tiel ekzemple tie ni havas tri
infanoj ekstere ke dekstra mano nodo,

721
00:34:00,820 --> 00:34:05,480
sed en duuma arbo, nodo havas
nul, unu, aŭ du infanojn maksimume.

722
00:34:05,480 --> 00:34:08,496
Kaj tio estas bela propraĵo,
ĉar se ĝi estas haltigataj per du,

723
00:34:08,496 --> 00:34:10,620
ni tuj povos
akiri malgrandan log bazo du

724
00:34:10,620 --> 00:34:11,975
ago okazas tie finfine.

725
00:34:11,975 --> 00:34:13,350
Do ni havas ion logaritma.

726
00:34:13,350 --> 00:34:14,558
Sed pli en kiu tre frue.

727
00:34:14,558 --> 00:34:19,810
Serĉu arbo signifas, ke la ciferoj estas
aranĝita tia ke la maldekstra infano

728
00:34:19,810 --> 00:34:22,429
valoro estas pli granda ol la radiko.

729
00:34:22,429 --> 00:34:26,010
Kaj lia dekstra infano estas
granda ol la radiko.

730
00:34:26,010 --> 00:34:29,290
Alivorte, se vi prenos iun el la
nodoj, la cirkloj en ĉi tiu bildo,

731
00:34:29,290 --> 00:34:31,840
kaj rigardas lian maldekstran
infano kaj lia dekstra infano,

732
00:34:31,840 --> 00:34:34,739
la unua devus esti malpli ol,
la dua devus esti pli granda ol.

733
00:34:34,739 --> 00:34:36,159
Do prudento kontroli 55.

734
00:34:36,159 --> 00:34:37,780
Ĝi lasis infano estas 33.

735
00:34:37,780 --> 00:34:38,620
Ĝi estas malpli ol.

736
00:34:38,620 --> 00:34:40,929
55, lia dekstra infano estas 77.

737
00:34:40,929 --> 00:34:41,783
Ĝi estas pli granda ol.

738
00:34:41,783 --> 00:34:43,199
Kaj tio estas rekursia difino.

739
00:34:43,199 --> 00:34:46,480
Ni povis kontroli ĉiu el tiuj
nodoj kaj la sama padrono tenus.

740
00:34:46,480 --> 00:34:49,389
>> Do kio estas agrabla en
duuma serĉo arboj

741
00:34:49,389 --> 00:34:52,204
tiu, ni povas apliki ĝin
kun struct, nur ŝatas tion.

742
00:34:52,204 --> 00:34:54,620
Kaj kvankam ni ĵetante
multaj strukturoj ĉe via,

743
00:34:54,620 --> 00:34:56,560
ili estas iom
intuicia nun espereble.

744
00:34:56,560 --> 00:35:00,570
La sintakso estas ankoraŭ arcano por certa,
sed la enhavon de nodo en ĉi

745
00:35:00,570 --> 00:35:02,786
context-- kaj ni plenumas
uzante la vorton nodo,

746
00:35:02,786 --> 00:35:04,910
ĉu ĝi estas rektangulo
sur la ekrano aŭ cirklo,

747
00:35:04,910 --> 00:35:08,970
ĝi estas nur kelkaj genraj ujo,
en tiu kazo de arbo, kiel la

748
00:35:08,970 --> 00:35:11,780
ni vidis, ni bezonas entjero
en ĉiu de la nodoj

749
00:35:11,780 --> 00:35:15,460
kaj tiam Mi bezonas du punteros montradon
maldekstren infano kaj la dekstra infano,

750
00:35:15,460 --> 00:35:16,590
respektive.

751
00:35:16,590 --> 00:35:20,730
Do jen kiel ni povus
apliki ke en struct.

752
00:35:20,730 --> 00:35:22,315
Kaj kiel povus mi implementarlo en kodo?

753
00:35:22,315 --> 00:35:26,730
Nu, ni prenu rapidan
rigardi tiun etan ekzemplon.

754
00:35:26,730 --> 00:35:29,820
Ĝi ne estas praktika, sed mi havas
kopiitaj kaj batitaj de tiu strukturo.

755
00:35:29,820 --> 00:35:33,510
Kaj se mia funkcio por duargumenta
serĉo arbo nomiĝas serĉo,

756
00:35:33,510 --> 00:35:36,980
kaj tio prenas du argumentojn,
entjero N kaj puntero

757
00:35:36,980 --> 00:35:41,400
al nodo, do puntero al la arbo
aŭ montrilo al la radiko de arbo,

758
00:35:41,400 --> 00:35:43,482
kiel mi iros priserĉi por N?

759
00:35:43,482 --> 00:35:45,440
Nu, unue, ĉar mi estas
pritraktas punteros,

760
00:35:45,440 --> 00:35:46,750
Mi tuj fari prudento ĉeko.

761
00:35:46,750 --> 00:35:54,279
Se arbo egaluloj egalas nula, estas N
en ĉi tiu arbo aŭ ne en ĉi tiu arbo?

762
00:35:54,279 --> 00:35:55,070
Ne povas esti, ĉu ne?

763
00:35:55,070 --> 00:35:56,870
Se mi estas pasinteco nula,
nenio estas tie.

764
00:35:56,870 --> 00:35:59,230
Mi povus tiel simple
blinde diri reveni falsaj.

765
00:35:59,230 --> 00:36:04,050
Se vi donos al mi nenion, mi certe ne povas
trovi ajnan nombron N. Do kion alian povus mi

766
00:36:04,050 --> 00:36:04,750
kontroli nun?

767
00:36:04,750 --> 00:36:12,830
Mi tuj diros bone alia se N estas
malpli ol kiom estas ĉe la arbo nodo

768
00:36:12,830 --> 00:36:16,300
ke mi estis transdonita N valoro.

769
00:36:16,300 --> 00:36:20,270
En aliaj vortoj, se la nombro mi
serĉas, N, estas pli malgranda ol la nodo

770
00:36:20,270 --> 00:36:21,340
ke mi rigardas.

771
00:36:21,340 --> 00:36:23,190
Kaj la nodo Mi serĉas
ĉe nomata arbo,

772
00:36:23,190 --> 00:36:26,370
kaj memoras de la antaŭa ekzemplo
atingi la valoron en puntero,

773
00:36:26,370 --> 00:36:28,310
Mi uzas la saga skribmaniero.

774
00:36:28,310 --> 00:36:35,960
Do se N estas malpli ol arbo sagon
No, mi volas koncepte iros maldekstren.

775
00:36:35,960 --> 00:36:38,590
Kjel mi esprimas Searching forlasis?

776
00:36:38,590 --> 00:36:41,560
Esti klara, se tio estas
la bildo en demando,

777
00:36:41,560 --> 00:36:44,612
kaj Mi estis pasita ke plejsupra
arrow ke estas indikante malsupren.

778
00:36:44,612 --> 00:36:45,570
Jen mia arbo montrilo.

779
00:36:45,570 --> 00:36:48,060
Mi fingromontrante la radiko de la arbo.

780
00:36:48,060 --> 00:36:52,100
Kaj Mi serĉas diru, por
la nombro 44, arbitre.

781
00:36:52,100 --> 00:36:55,300
Estas 44 malpli ol aŭ
pli granda ol 55 evidente?

782
00:36:55,300 --> 00:36:56,360
Do estas malpli ol.

783
00:36:56,360 --> 00:36:58,760
Kaj tiel ĉi se kondiĉo validas.

784
00:36:58,760 --> 00:37:03,981
Do koncepte, kion mi volas
serĉu apud se Mi serĉas 44?

785
00:37:03,981 --> 00:37:04,480
Yeah?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Ekzakte, mi volas
serĉu la maldekstra infano,

788
00:37:11,100 --> 00:37:12,789
aŭ maldekstre sub-arbo de tiu bildo.

789
00:37:12,789 --> 00:37:14,830
Kaj fakte, lasu min tra
la bildo malsupren tie

790
00:37:14,830 --> 00:37:17,770
por nur momento, kiam
Mi ne povas skrapi ĉi ekstere.

791
00:37:17,770 --> 00:37:21,150
Se mi komencas ĉi tie ĉe 55, kaj
Mi scias ke la valoro 44

792
00:37:21,150 --> 00:37:23,180
Mi serĉas estas
la maldekstra, ĝi estas speco

793
00:37:23,180 --> 00:37:26,010
de kiel ŝirante la telefono libro en
duono aŭ ŝirante la arbo en duono.

794
00:37:26,010 --> 00:37:29,660
Mi ne plu devos zorgi pri
tiu tuta duono de la arbo.

795
00:37:29,660 --> 00:37:33,270
Kaj tamen, scivoleme en terminoj de la
strukturo, tion super tie ke

796
00:37:33,270 --> 00:37:36,682
komenciĝas kun 33, kiu mem
estas duuma serĉo arbo.

797
00:37:36,682 --> 00:37:39,890
Mi diris la vorton rekursia antaŭ ĉar
ja tiu estas datumstrukturo ke

798
00:37:39,890 --> 00:37:41,707
laŭdifine estas rekursiaj.

799
00:37:41,707 --> 00:37:44,540
Vi povus havi arbo kiu estas tio
grandan, sed ĉiu el liaj infanoj

800
00:37:44,540 --> 00:37:46,870
reprezentas arbon nur iom pli malgranda.

801
00:37:46,870 --> 00:37:50,910
Anstataŭ ĝi estanta avo
aŭ avino, nun ĝi estas nur panjo

802
00:37:50,910 --> 00:37:54,300
or-- Mi ne povas say-- ne panjon
aŭ paĉjo, ke estus stranga.

803
00:37:54,300 --> 00:37:59,000
Anstataŭ la du infanoj tie
estus kiel frato kaj gefrato.

804
00:37:59,000 --> 00:38:01,120
Nova generacio de la familio arbo.

805
00:38:01,120 --> 00:38:02,900
Sed strukture ĝi estas la sama ideo.

806
00:38:02,900 --> 00:38:06,790
Kaj ĝi rezultas mi havas funkcion
kun kiu mi povas serĉi duuma serĉo

807
00:38:06,790 --> 00:38:07,290
arbon.

808
00:38:07,290 --> 00:38:08,680
Ĝi nomiĝas serĉo.

809
00:38:08,680 --> 00:38:17,870
Mi serĉi N en arbo sago maldekstren
alie se N estas pli granda ol la valoro

810
00:38:17,870 --> 00:38:18,870
ke mi estas nune en.

811
00:38:18,870 --> 00:38:20,800
55 en la rakonto antaŭ momento.

812
00:38:20,800 --> 00:38:23,780
Mi havas funkcion nomita
serĉo ke mi povas nur

813
00:38:23,780 --> 00:38:29,660
pasi N ĉi kaj rekursie serĉo
la sub-arbo kaj simple reveno

814
00:38:29,660 --> 00:38:30,620
kio ajn tiu respondo.

815
00:38:30,620 --> 00:38:33,530
Alie Mi havas iuj fina bazo kazo tie.

816
00:38:33,530 --> 00:38:35,310
>> Kio estas la fina kazo?

817
00:38:35,310 --> 00:38:36,570
Arbo estas aŭ nula.

818
00:38:36,570 --> 00:38:39,980
La valoron mi ĉu serĉas estas
malpli ol aŭ pli granda ol tiu

819
00:38:39,980 --> 00:38:42,610
aŭ egala al ĝi.

820
00:38:42,610 --> 00:38:44,750
Kaj mi povus diri egalaj
egalaj, sed logike ĝi estas

821
00:38:44,750 --> 00:38:46,500
ekvivalenta al nur diras alia ĉi tie.

822
00:38:46,500 --> 00:38:49,150
Tiel vera kiel mi trovas ion.

823
00:38:49,150 --> 00:38:51,710
Do espereble tiu estas
eĉ pli konvinka ekzemplo

824
00:38:51,710 --> 00:38:54,900
ol la stulta sigma funkcio
ni faris kelkajn prelegojn reen,

825
00:38:54,900 --> 00:38:58,360
kie estis egale facile uzi buklo
kalkuli ĉiujn numerojn de unu

826
00:38:58,360 --> 00:39:02,390
al N. tie kun datumstrukturo
ke mem estas rekursie

827
00:39:02,390 --> 00:39:07,050
difinita kaj rekursie desegnita, nun ni
havas la kapablon esprimi nin

828
00:39:07,050 --> 00:39:09,780
en kodo kiu mem estas rekursiaj.

829
00:39:09,780 --> 00:39:12,580
Do tiu estas la ĝusta sama kodo tie.

830
00:39:12,580 --> 00:39:14,400
>> Do kion aliaj problemoj povas ni solvi?

831
00:39:14,400 --> 00:39:18,160
Tiel rapida paŝo for de
arboj por nur momento.

832
00:39:18,160 --> 00:39:20,130
Jen, diru, la germana flago.

833
00:39:20,130 --> 00:39:22,020
Kaj estas klare
ekzemplo por tiu flago.

834
00:39:22,020 --> 00:39:23,811
Kaj estas multaj
flagoj en la mondo kiu

835
00:39:23,811 --> 00:39:27,560
estas tiel simpla kiel tiu en terminoj
de siaj koloroj kaj skemoj.

836
00:39:27,560 --> 00:39:31,930
Sed supozu, ke tiu estas stokita kiel
.gif, Aŭ JPEG aŭ bitmap aŭ ping,

837
00:39:31,930 --> 00:39:34,240
ajna grafika dosierformato
kun kiu vi konas,

838
00:39:34,240 --> 00:39:36,460
Kelkaj de kiu ni estas
ludante kun en PSET4.

839
00:39:36,460 --> 00:39:41,550
Ĉi tio ne ŝajnas inda enteni
nigra pikselo, nigra pikselo, nigra pikselo,

840
00:39:41,550 --> 00:39:44,790
dot, punkto, punkto, tuta aro de
nigraj pikseloj por la unua scanline,

841
00:39:44,790 --> 00:39:47,430
aŭ vico, tiam tuta amaso de
la sama, tiam tutan faskon

842
00:39:47,430 --> 00:39:49,530
de la sama, kaj tiam
tutan faskon de ruĝa rastrumeroj,

843
00:39:49,530 --> 00:39:53,020
ruĝa rastrumeroj, ruĝa rastrumeroj, tiam tuto
faskon da flavaj rastrumeroj, flava, dekstra?

844
00:39:53,020 --> 00:39:55,050
>> Ekzistas tiaj senefikeco tie.

845
00:39:55,050 --> 00:39:59,040
Kiel vi intue
kunpremi la germana flago

846
00:39:59,040 --> 00:40:01,320
se efektiviganta ĝin kiel dosieron?

847
00:40:01,320 --> 00:40:04,940
Kiel kion informo povas ni ne
ĝeni stokante en disko por

848
00:40:04,940 --> 00:40:08,040
malpliigi niajn grandeco de dosiero el kiel
megabajto al kilobajto, io

849
00:40:08,040 --> 00:40:09,430
malgrandaj?

850
00:40:09,430 --> 00:40:13,130
Kien kuŝas la redundo
tie esti klara?

851
00:40:13,130 --> 00:40:13,880
Kion vi povus fari?

852
00:40:13,880 --> 00:40:14,380
Yeah?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Ekzakte.

855
00:40:21,970 --> 00:40:24,550
Kial ne prefere ol memori
la koloro de ĉiu Darn rastrumero

856
00:40:24,550 --> 00:40:28,200
kiel vi faras en PSET4
kun la bitmap dosiero formato,

857
00:40:28,200 --> 00:40:32,060
kial vi ne simple reprezenti la
plej maldekstra kolumno de rastrumeroj, ekzemple

858
00:40:32,060 --> 00:40:35,370
faskon de nigra rastrumeroj, faskon
de ruĝa, kaj faskon da flavaj,

859
00:40:35,370 --> 00:40:39,210
kaj tiam simple iel kodas la
ideon de ripeti ĉi 100 fojoj

860
00:40:39,210 --> 00:40:41,020
aŭ ripeti tiun 1,000 fojoj?

861
00:40:41,020 --> 00:40:43,430
Kie 100 aŭ 1,000 estas
nur entjero, do vi

862
00:40:43,430 --> 00:40:47,290
povas foriri kun nur unu nombro
anstataŭ centoj aŭ miloj

863
00:40:47,290 --> 00:40:48,270
de pliaj rastrumeroj.

864
00:40:48,270 --> 00:40:50,990
Kaj efektive, jen kiel ni
povis kunpremi la germana flago.

865
00:40:50,990 --> 00:40:51,490
Kaj

866
00:40:51,490 --> 00:40:53,470
Nun kio pri la franca flago?

867
00:40:53,470 --> 00:40:58,930
Kaj iom ian
mensa ekzerco, kiu flagon

868
00:40:58,930 --> 00:41:01,040
povas kunpremi pli surdiske?

869
00:41:01,040 --> 00:41:05,720
La germana flago aŭ la franca
flago, se ni prenas tiun aliron?

870
00:41:05,720 --> 00:41:08,490
La germana flago, ĉar estas
pli horizontala redundo.

871
00:41:08,490 --> 00:41:12,190
Kaj projekte, multaj grafikaj dosieron
formatoj ĉu vere labori kiel skanado liniojn

872
00:41:12,190 --> 00:41:12,830
horizontale.

873
00:41:12,830 --> 00:41:14,674
Ili povis funkcii
vertikale, ĵus homaro

874
00:41:14,674 --> 00:41:17,090
decidis jaroj ke ni
ĝenerale pensas pri aferoj vico

875
00:41:17,090 --> 00:41:18,880
per vico anstataŭ kolumno por kolumno.

876
00:41:18,880 --> 00:41:20,820
Do efektive, se vi estus
por rigardi la dosieron

877
00:41:20,820 --> 00:41:24,670
grandeco de germana flago kaj franca
flago, tiel longe kiel la rezolucio estas

878
00:41:24,670 --> 00:41:27,530
la sama, la sama larĝo
kaj alteco, ĉi tiu

879
00:41:27,530 --> 00:41:31,580
tie tuj estos pli granda, ĉar vi
devos ripeti mem trifoje.

880
00:41:31,580 --> 00:41:35,570
Vi devas entajpi blua, ripeto
mem, blanka, ripeti mem, ruĝa,

881
00:41:35,570 --> 00:41:36,740
ripetas vin.

882
00:41:36,740 --> 00:41:39,000
Vi ne povas simple iru ĉiuj
la vojo dekstre.

883
00:41:39,000 --> 00:41:41,200
Kaj kiel flanken, por fari
liberigi la kunpremo

884
00:41:41,200 --> 00:41:43,910
estas ĉie, se tiuj estas
kvar kadroj de video-- vi

885
00:41:43,910 --> 00:41:45,890
eble memoras ke filmo
aŭ video estas ĝenerale

886
00:41:45,890 --> 00:41:47,286
kiel 29 aŭ 30 kadroj je sekundo.

887
00:41:47,286 --> 00:41:50,410
Estas kiel iom flip libro kie vi
nur vidu bildon, bildo, bildo, bildo,

888
00:41:50,410 --> 00:41:54,410
bildo ĵus super rapida tiel ĝi aspektas kiel
la aktoroj sur la ekrano estas movanta.

889
00:41:54,410 --> 00:41:57,130
Jen burdoj sur
supro de faskon da floroj.

890
00:41:57,130 --> 00:41:59,790
Kaj kvankam ĝi povus esti speco de
malfacile vidi unuavide,

891
00:41:59,790 --> 00:42:04,020
la sola afero movanta en
tiu filmo estas la abelo.

892
00:42:04,020 --> 00:42:06,880
>> Kio estas muta pri stokante
video kunpremitaj?

893
00:42:06,880 --> 00:42:11,420
Estas speco de malŝparo stoki video
kiel kvar preskaŭ identaj bildoj kiu

894
00:42:11,420 --> 00:42:13,670
diferencas nur en la mezuro kie la abelo estas.

895
00:42:13,670 --> 00:42:16,280
Vi povas forĵeti plej
de tiu informo

896
00:42:16,280 --> 00:42:20,190
kaj memori nur, ekzemple,
la unua kadro kaj la lasta kadro,

897
00:42:20,190 --> 00:42:22,180
ŝlosilo kadroj se vi havas
iam aŭdis la vorton,

898
00:42:22,180 --> 00:42:24,337
kaj simple stoki en la
mezo kie la abelo estas.

899
00:42:24,337 --> 00:42:26,170
Kaj vi ne devas
stoki ĉiujn la rozo,

900
00:42:26,170 --> 00:42:28,330
kaj bluan, kaj la
verda valoroj ankaŭ.

901
00:42:28,330 --> 00:42:31,200
Do tio estas nur por diri ke
kunpremo estas ĉie.

902
00:42:31,200 --> 00:42:34,900
Estas tekniko ni ofte uzas
aŭ preni por donita tiujn tagojn.

903
00:42:34,900 --> 00:42:38,750
>> Sed kiel vi kunpremi teksto?

904
00:42:38,750 --> 00:42:40,450
Kiel vi iras pri kunpremante teksto?

905
00:42:40,450 --> 00:42:45,410
Nu, ĉiu el la karakteroj en
Ascii estas unu bajto, aŭ ok bitoj.

906
00:42:45,410 --> 00:42:47,360
Kaj jen speco de mutaj, dekstra?

907
00:42:47,360 --> 00:42:51,160
Ĉar vi probable Speco
kaj E kaj I kaj O kaj U multe

908
00:42:51,160 --> 00:42:55,270
pli ofte ol kiel W aŭ Q aŭ Z,
depende de la lingvo en kiu

909
00:42:55,270 --> 00:42:56,610
vi skribas certe.

910
00:42:56,610 --> 00:42:59,600
Kaj do kial ni uzas
ok bitojn por ĉiu litero,

911
00:42:59,600 --> 00:43:02,040
Inkluzivanta la malplej
populara literoj, dekstra?

912
00:43:02,040 --> 00:43:05,300
Kial ne uzi pli malmultajn bitoj por
la súper populara literoj,

913
00:43:05,300 --> 00:43:07,760
kiel E, tion vi divenu
unua en Rado de Fortuno,

914
00:43:07,760 --> 00:43:10,450
kaj uzi pli bitojn por
la malpli populara literoj?

915
00:43:10,450 --> 00:43:10,950
Kial?

916
00:43:10,950 --> 00:43:13,130
Ĉar ni ĵus tuj
uzi ilin malpli ofte.

917
00:43:13,130 --> 00:43:15,838
>> Nu, Ĝi rezultas ke havas
estis provoj faritaj por fari tion.

918
00:43:15,838 --> 00:43:18,630
Kaj se vi memoras de lernojaro
lernejo aŭ mezlernejo, Morsa kodo.

919
00:43:18,630 --> 00:43:20,400
Morsa kodo havas punktojn
kaj strekoj kiuj povas esti

920
00:43:20,400 --> 00:43:24,270
transdonita kune drato kiel
sonas aŭ signaloj de iu speco.

921
00:43:24,270 --> 00:43:25,930
Sed Morsa kodo estas super pura.

922
00:43:25,930 --> 00:43:29,010
Estas speco de duuma sistemo en
ke vi havas punktoj aŭ streketoj.

923
00:43:29,010 --> 00:43:30,977
Sed se vi vidas, ekzemple, du punktoj.

924
00:43:30,977 --> 00:43:33,810
Aŭ se vi pensas reen al la operatoro
kiu iras tiel pepi, pepi, pepi,

925
00:43:33,810 --> 00:43:36,760
pepi, trafante iom ellasilon
kiu transdonas signalon,

926
00:43:36,760 --> 00:43:40,360
se vi, la ricevanto, ricevas du
dots, kion mesaĝon vi ricevis?

927
00:43:40,360 --> 00:43:43,490
Tute arbitra.

928
00:43:43,490 --> 00:43:44,450
>> Mi?

929
00:43:44,450 --> 00:43:45,060
Mi?

930
00:43:45,060 --> 00:43:47,500
Aŭ kion about-- aŭ mi?

931
00:43:47,500 --> 00:43:49,570
Eble estis nur du E pravas?

932
00:43:49,570 --> 00:43:52,480
Do ekzistas tiu problemo
de decodability kun Morso

933
00:43:52,480 --> 00:43:54,890
kodo, per kiu krom se la
persono sendas la mesaĝon

934
00:43:54,890 --> 00:43:59,510
fakte paŭzoj tiel vi povas ordigi de
vidi aŭ aŭdi la breĉoj inter literoj,

935
00:43:59,510 --> 00:44:02,990
ĝi ne estas sufiĉa nur por
sendu torenton da nuloj kaj,

936
00:44:02,990 --> 00:44:05,610
aŭ punktoj kaj strekoj,
ĉar ekzistas ambigueco.

937
00:44:05,610 --> 00:44:08,640
E estas sola punkto, do se vi
vidas du punktojn aŭ aŭdi du punktojn,

938
00:44:08,640 --> 00:44:11,254
Eble estas du E aŭ eble estas unu I.

939
00:44:11,254 --> 00:44:13,670
Do ni bezonas sistemon kiu estas
iom pli ruza ol tio.

940
00:44:13,670 --> 00:44:16,851
Do viro nomis Huffman jaroj
antaŭ venadis kun precize tiu.

941
00:44:16,851 --> 00:44:18,600
Do ni simple tuj
preni rapidan rigardon

942
00:44:18,600 --> 00:44:20,114
ĉe kiel arboj estas germane al tiu.

943
00:44:20,114 --> 00:44:22,530
Supozu ke tiu estas iuj
stulta mesaĝo vi volas sendi,

944
00:44:22,530 --> 00:44:26,342
formita de nur A, B, C la D kaj E,
sed ekzistas multe de redundo tie.

945
00:44:26,342 --> 00:44:27,550
Ĝi ne estas intencita esti angla.

946
00:44:27,550 --> 00:44:28,341
Ĝi ne estas ĉifrita.

947
00:44:28,341 --> 00:44:30,540
Estas nur stulta mesaĝon
kun multe da ripeto.

948
00:44:30,540 --> 00:44:34,010
Do se vi reale kalkuli ĉiujn
-a, B, C la, D, kaj E, jen

949
00:44:34,010 --> 00:44:34,890
la frekvenco.

950
00:44:34,890 --> 00:44:37,800
20% de la literoj estas
-a, 45% de la literoj

951
00:44:37,800 --> 00:44:39,660
estas E, kaj tri aliaj frekvencoj.

952
00:44:39,660 --> 00:44:41,960
Ni kalkulis tie supre permane
kaj ĝuste faris la math.

953
00:44:41,960 --> 00:44:44,579
>> Do rezultas ke
Huffman, antaŭ kelka tempo,

954
00:44:44,579 --> 00:44:46,620
rimarkis ke, vi scias
kio, se mi komencas konstruaĵo

955
00:44:46,620 --> 00:44:51,172
arbo aŭ arbaro de arboj, se vi volas,
jene, mi povas fari la sekvajn.

956
00:44:51,172 --> 00:44:53,880
Mi tuj donos al ĉiu nodo
de la leteroj kiujn mi zorgas pri

957
00:44:53,880 --> 00:44:55,530
kaj mi tuj stoki
ene de tiu nodo

958
00:44:55,530 --> 00:44:58,610
la frekvencoj kiel glitpunktaj
valoro, aŭ vi povus uzi ĝin N, tro,

959
00:44:58,610 --> 00:45:00,210
sed ni simple uzu kaleŝego tie.

960
00:45:00,210 --> 00:45:03,100
Kaj la algoritmo kiu
li proponita estas ke vi

961
00:45:03,100 --> 00:45:07,210
prenu ĉi arbaro de ununura nodo
arboj, tiel super mallonga arboj,

962
00:45:07,210 --> 00:45:11,920
kaj vi komencas konektante ilin kun
novaj grupoj, novaj gepatroj, se vi volas.

963
00:45:11,920 --> 00:45:16,150
Kaj vi faros tion elektante la
du pli malgrandaj frekvencoj samtempe.

964
00:45:16,150 --> 00:45:18,110
Do mi prenis 10% kaj 10%.

965
00:45:18,110 --> 00:45:19,090
Mi kreas novan nodon.

966
00:45:19,090 --> 00:45:20,910
Kaj mi alvokis la nova nodo 20%.

967
00:45:20,910 --> 00:45:22,750
>> Kiu du nodoj mi kombinas poste?

968
00:45:22,750 --> 00:45:23,810
Ĝi estas iom ambigua.

969
00:45:23,810 --> 00:45:26,643
Do ekzistas iu angulo kazoj
konsideri, sed konservi aferojn belajn,

970
00:45:26,643 --> 00:45:29,300
Mi tuj elektos 20% -
Mi nun ignori la infanoj.

971
00:45:29,300 --> 00:45:33,640
Mi tuj elektos 20% kaj
15% kaj desegni du novaj lateroj.

972
00:45:33,640 --> 00:45:35,624
Kaj nun kiu du nodoj
mi logike kombini?

973
00:45:35,624 --> 00:45:38,540
Ignori ĉiujn infanojn, ĉiuj
genepoj, nur rigardas la radikojn

974
00:45:38,540 --> 00:45:39,070
nun.

975
00:45:39,070 --> 00:45:42,220
Kiu du nodoj mi jungu kune?

976
00:45:42,220 --> 00:45:44,530
Punkto du kaj 0.35.

977
00:45:44,530 --> 00:45:45,890
Do lasu min tiri du novaj lateroj.

978
00:45:45,890 --> 00:45:47,570
Kaj tiam mi havas nur unu maldekstra.

979
00:45:47,570 --> 00:45:48,650
Do jen arbo.

980
00:45:48,650 --> 00:45:51,160
Kaj ĝi estas estita desegnita intence
rigardi ia bela,

981
00:45:51,160 --> 00:45:55,870
sed rimarki ke la lateroj havas
ankaŭ estis etikeditaj nulo kaj unu.

982
00:45:55,870 --> 00:45:59,510
Do ĉio maldekstre randoj estas nulo
arbitre, sed konstante.

983
00:45:59,510 --> 00:46:01,170
Ĉiuj rektaj randoj estas ones.

984
00:46:01,170 --> 00:46:05,070
>> Kaj tiel kion Hoffman proponitaj estas,
se vi volas reprezenti B,

985
00:46:05,070 --> 00:46:10,080
anstataŭ reprezenti la numero 66 kiel
an Ascii kiu estas ok tutan bitoj,

986
00:46:10,080 --> 00:46:13,360
Vi scias kion, simple vendejo
desegnon nulo, nulo, nulo,

987
00:46:13,360 --> 00:46:17,030
nulo, ĉar tio estas la vojo
de mia arbo, sinjoro Huffman la arbo,

988
00:46:17,030 --> 00:46:18,600
al la folio de la radiko.

989
00:46:18,600 --> 00:46:20,970
Se vi volas stoki
Kaj, kontraste, ne

990
00:46:20,970 --> 00:46:26,290
sendu ok bitoj kiuj reprezentas E.
Anstataŭe, sendu kion mastro de bitoj?

991
00:46:26,290 --> 00:46:26,890
Unu.

992
00:46:26,890 --> 00:46:30,410
Kaj kio estas agrabla pri tio estas
ke E estas la plej populara letero,

993
00:46:30,410 --> 00:46:32,340
kaj vi uzas la
mallonga kodo por ĝi.

994
00:46:32,340 --> 00:46:34,090
La venonta plej popularaj
letero aspektas kiel ĝi

995
00:46:34,090 --> 00:46:37,380
estis A. Sed do kiom da bitoj
Ĉu li proponis uzi por tio?

996
00:46:37,380 --> 00:46:38,270
Zero, unu.

997
00:46:38,270 --> 00:46:41,060
>> Kaj ĉar ĝi estas implementado
kiel tiu arbo, nun

998
00:46:41,060 --> 00:46:43,350
lasu min kondiĉas ekzistas
neniu ambigueco kiel en Morse

999
00:46:43,350 --> 00:46:46,090
kodo, ĉar ĉiuj el la
literojn vi zorgas pri

1000
00:46:46,090 --> 00:46:48,780
estas ĉe la fino de ĉi tiuj lateroj.

1001
00:46:48,780 --> 00:46:50,580
Do jen nur unu
apliko de arbo.

1002
00:46:50,580 --> 00:46:52,538
Ĉi is-- kaj mi skuos
mian manon je ĉi kiamaniere vi

1003
00:46:52,538 --> 00:46:55,570
povus efektivigi tion kiel C strukturo.

1004
00:46:55,570 --> 00:46:58,260
Ni nur bezonas kombini
simbolo, kiel char,

1005
00:46:58,260 --> 00:46:59,910
kaj la ofteco en maldekstra kaj dekstra.

1006
00:46:59,910 --> 00:47:02,510
Sed ni rigardu du
fina ekzemploj ke vi

1007
00:47:02,510 --> 00:47:06,070
akiri sufiĉe familiara kun post
kvizo nulo en problemo starigis kvin.

1008
00:47:06,070 --> 00:47:09,210
>> Do estas la datumstrukturo
konata kiel hash tablo.

1009
00:47:09,210 --> 00:47:12,247
Kaj hash tablo estas speco de
malvarmigi en tio ĝi havas siteloj.

1010
00:47:12,247 --> 00:47:14,830
Kaj supozu ke estas kvar sitelojn
tie, nur kvar malplenan spacoj.

1011
00:47:14,830 --> 00:47:20,830
Jen ludkartaro de kartoj, kaj tie estas
klubo, fosilon, klubo, diamantoj, klubo,

1012
00:47:20,830 --> 00:47:25,960
diamantoj, klubo, diamantoj,
clubs-- do ĉi tiu estas la hazardo.

1013
00:47:25,960 --> 00:47:30,330
Koroj, hearts-- do mi estas
bucketizing ĉiuj enigoj tie.

1014
00:47:30,330 --> 00:47:32,430
Kaj hash tablo bezonoj
rigardi vian enigo,

1015
00:47:32,430 --> 00:47:34,850
kaj tiam metis ĝin en certa
meti bazita sur kio vi vidas.

1016
00:47:34,850 --> 00:47:35,600
Ĝi estas algoritmo.

1017
00:47:35,600 --> 00:47:37,980
Kaj mi estis uzanta super
simpla vida algoritmo.

1018
00:47:37,980 --> 00:47:40,030
La plej malfacila parto de kiu estis
memorante kion la bildoj estis.

1019
00:47:40,030 --> 00:47:41,590
Kaj tiam tie estas kvar aferoj entute.

1020
00:47:41,590 --> 00:47:45,440
>> Nun la stakoj estis kreskantaj, kiu
Estas intenca dezajno afero tie.

1021
00:47:45,440 --> 00:47:46,540
Sed kion alian povus mi fari?

1022
00:47:46,540 --> 00:47:49,080
Do fakte tie ni havas
faskon de malnova lernejo ekzameno libroj.

1023
00:47:49,080 --> 00:47:51,240
Supozu ke faskon da
studentoj nomoj estas tie.

1024
00:47:51,240 --> 00:47:52,570
Jen pli granda hash tablo.

1025
00:47:52,570 --> 00:47:54,867
Anstataŭ kvar siteloj,
Mi, ni diru 26.

1026
00:47:54,867 --> 00:47:57,950
Kaj ni ne volas iri prunteprenos 26
aferojn de ekstere [? Annenberg?], Do

1027
00:47:57,950 --> 00:48:00,289
jen kvin kiuj reprezentas
A tra Z. Kaj se mi

1028
00:48:00,289 --> 00:48:03,580
vidu studento kies nomo komenciĝas per A,
Mi tuj metis sian kvizo tie.

1029
00:48:03,580 --> 00:48:08,850
Se iu komencas kun C, tien,
A-- reale, ne volis fari tion.

1030
00:48:08,850 --> 00:48:10,060
B iras tien.

1031
00:48:10,060 --> 00:48:13,390
Do mi havas A kaj B kaj C. Kaj
nun jen alia studento.

1032
00:48:13,390 --> 00:48:16,212
Sed se tiu hash tablo estas
implementado kun tabelo,

1033
00:48:16,212 --> 00:48:17,920
Mi estas speco de ŝraŭbita
ĉe tiu punkto, dekstra?

1034
00:48:17,920 --> 00:48:19,510
Mi ia bezonas meti tiun ie.

1035
00:48:19,510 --> 00:48:24,380
>> Do unu maniero mi povas solvi tio, ĉiuj
Bone, A estas okupita, B estas okupata, C estas okupata.

1036
00:48:24,380 --> 00:48:28,880
Mi tuj metis lin en D. Tiel ĉe
unue, mi havas hazardaj tuja aliro

1037
00:48:28,880 --> 00:48:31,064
al ĉiu el la siteloj por la studentoj.

1038
00:48:31,064 --> 00:48:33,230
Sed nun ĝi estas speco de transdonitaj
en ion lineara,

1039
00:48:33,230 --> 00:48:36,750
ĉar se mi volas serĉi iun
kies nomo komenciĝas per A, mi kontrolu ĉi tie.

1040
00:48:36,750 --> 00:48:38,854
Sed se tio ne estas la A
Studento Mi serĉas,

1041
00:48:38,854 --> 00:48:41,520
Mi specon de devas komenci kontrolanta
la siteloj, ĉar kion mi faris

1042
00:48:41,520 --> 00:48:44,530
estis speco de lineare
sondi la datumstrukturo.

1043
00:48:44,530 --> 00:48:47,710
Stulta maniero diri simple aspektas
por la unua havebla malfermo,

1044
00:48:47,710 --> 00:48:51,850
kaj meti kiel planon B, tiel diri,
aŭ planon D en tiu kazo, la valoro

1045
00:48:51,850 --> 00:48:53,340
en tiu loko anstataŭe.

1046
00:48:53,340 --> 00:48:56,470
Tiu estas nur tiel ke se oni devas
ricevis 26 lokojn kaj ne lernantoj

1047
00:48:56,470 --> 00:49:00,600
kun la nomo Q aŭ Z, aŭ io simila
ke, almenaŭ vi uzas la spacon.

1048
00:49:00,600 --> 00:49:03,140
>> Sed ni jam vidis pli
clever solvojn ĉi tie, ĉu ne?

1049
00:49:03,140 --> 00:49:04,870
Kion vi farus anstataŭ
se vi havas kolizion?

1050
00:49:04,870 --> 00:49:06,670
Se du personoj havas
la nomo A, kion farus

1051
00:49:06,670 --> 00:49:09,160
estinti pli inteligenta aŭ pli
intuicia solvo ol nur

1052
00:49:09,160 --> 00:49:12,840
Metante kie D estas supozita esti?

1053
00:49:12,840 --> 00:49:14,810
Kial mi ne nur iri
eksteren [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
kiel malloc, alia nodo, metis ĝin
tie kaj surmetu ke studento tie.

1055
00:49:19,960 --> 00:49:22,120
Por ke mi esence havas
ia tabelo,

1056
00:49:22,120 --> 00:49:25,590
aŭ eble pli elegante kiel ni estas
ekvidas ligillisto.

1057
00:49:25,590 --> 00:49:29,520
>> Kaj tiel hash tablo estas strukturo
kiuj povis rigardi ĝuste kiel ĉi,

1058
00:49:29,520 --> 00:49:33,900
sed pli lerte, vi ion nomatan
apartan sinsekvon, per hash tablo

1059
00:49:33,900 --> 00:49:38,340
tute simple estas tabelo, ĉiu el
kies elementoj ne estas nombro,

1060
00:49:38,340 --> 00:49:40,470
estas sin ligillisto.

1061
00:49:40,470 --> 00:49:45,080
Tiel ke vi ricevas super rapida aliro
decidi kie hash via valoro.

1062
00:49:45,080 --> 00:49:48,059
Multe kiel kun la kartoj ekzemple,
Mi faris súper rapidajn decidojn.

1063
00:49:48,059 --> 00:49:49,600
Koroj iras tie, diamantoj iras tien.

1064
00:49:49,600 --> 00:49:52,180
Sama ĉi tie, A iras tie,
D iras tie, B iras tien.

1065
00:49:52,180 --> 00:49:55,740
Do super rapida rigardo-ups, kaj se
vi hazarde trafos kazo

1066
00:49:55,740 --> 00:49:59,429
kie vi havas koliziojn, du
homoj kun la sama nomo, bone tiam

1067
00:49:59,429 --> 00:50:00,970
vi simple komenci ligante ilin kune.

1068
00:50:00,970 --> 00:50:03,900
Kaj eble vi gardos ilin ordo
alfabete, eble ne.

1069
00:50:03,900 --> 00:50:05,900
Sed almenaŭ nun ni havas la dinamismo.

1070
00:50:05,900 --> 00:50:10,250
Do unuflanke ni havas súper rapida
konstanta tempo, kaj speco de lineara tempo

1071
00:50:10,250 --> 00:50:14,110
implikita se tiuj ligitaj lertaj
komencas akiri iom longa.

1072
00:50:14,110 --> 00:50:16,880
>> Do tiu speco de stulta,
geeky ŝerco jaroj.

1073
00:50:16,880 --> 00:50:19,590
Ĉe la CS50 hako-a-thon,
kiam studentoj kontroli en,

1074
00:50:19,590 --> 00:50:22,040
iuj TF aŭ CA ĉiujare
pensas ĝi estas amuza toleri

1075
00:50:22,040 --> 00:50:27,772
signo kiel tiu, kie nur
signifas se via nomo komenciĝas per A,

1076
00:50:27,772 --> 00:50:28,870
iri tiun vojon.

1077
00:50:28,870 --> 00:50:31,110
Se via nomo komenciĝas
kun B, iru this-- OK,

1078
00:50:31,110 --> 00:50:33,290
ĝi estas amuza eble poste en la semestro.

1079
00:50:33,290 --> 00:50:36,420
Sed estas alia
maniero fari tion, ankaŭ.

1080
00:50:36,420 --> 00:50:37,410
Revenu al tio.

1081
00:50:37,410 --> 00:50:38,600
>> Do ekzistas tiu strukturo.

1082
00:50:38,600 --> 00:50:40,420
Kaj tiu estas nia lasta
strukturon por hodiaŭ,

1083
00:50:40,420 --> 00:50:42,400
kiu estas iu nomita trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-Mi-E, kiu ial estas mallonga
por rehavigo, sed ĝi nomiĝas trie.

1085
00:50:47,140 --> 00:50:51,389
Do trie estas alia interesa
amalgama de multe de tiuj ideoj.

1086
00:50:51,389 --> 00:50:52,930
Ĝi estas arbo, kiun ni vidis antaŭe.

1087
00:50:52,930 --> 00:50:54,180
Ĝi ne estas duuma serĉo arbo.

1088
00:50:54,180 --> 00:50:58,410
Ĝi estas arbo kun iu ajn nombro de infanoj,
sed ĉiu el la infanoj en trie

1089
00:50:58,410 --> 00:51:00,090
estas tabelo.

1090
00:51:00,090 --> 00:51:04,790
Tabelo de grandeco, diru, 26 aŭ eble 27
se vi volas subteni skripto nomoj

1091
00:51:04,790 --> 00:51:06,790
aŭ apostrofoj en nomojn de homoj.

1092
00:51:06,790 --> 00:51:08,280
>> Kaj tiel tio estas datumstrukturo.

1093
00:51:08,280 --> 00:51:10,290
Kaj se vi rigardas el supro
sube, kiel se

1094
00:51:10,290 --> 00:51:13,710
rigardi la supro nodo tie, M, estas
indikante la plej maldekstra afero tie,

1095
00:51:13,710 --> 00:51:17,665
kiu tiam estas A, X, W, E, L, L. Jen
nur datumstrukturo ke arbitre

1096
00:51:17,665 --> 00:51:19,120
estas stokante popolaj nomoj.

1097
00:51:19,120 --> 00:51:25,720
Kaj Maxwell estas stokita per nur jenaj
vojeto tabelo tabelo al tabelo.

1098
00:51:25,720 --> 00:51:30,050
Sed kio estas mirinda pri trie estas
ke, dum ligillisto kaj eĉ

1099
00:51:30,050 --> 00:51:34,520
tabelo, la plej bona ni iam alveninta estas
lineara tempo aŭ logaritma tempo rigardanta

1100
00:51:34,520 --> 00:51:35,600
iu supren.

1101
00:51:35,600 --> 00:51:40,530
En tiu datumstrukturo de trie, se
miaj datumstrukturo havas unu nomon en ĝi

1102
00:51:40,530 --> 00:51:43,720
kaj Mi serĉas Maxwell, mi estas
tuj trovos lin bela rapide.

1103
00:51:43,720 --> 00:51:47,910
Mi nur serĉas M-Al-X-W-E-L-L. Se
tiu datumstrukturo, kontraste,

1104
00:51:47,910 --> 00:51:51,830
se N estas miliono, se ekzistas
milionoj nomoj en ĉi datumstrukturo,

1105
00:51:51,830 --> 00:51:57,100
Maxwell estas ankoraŭ tuj estos
discoverable post ĵus G-Al-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
paŝojn.

1107
00:51:58,090 --> 00:52:01,276
Kaj David-- D-Al-V-mi-D paŝoj.

1108
00:52:01,276 --> 00:52:03,400
Alivorte, per konstruado
datumstrukturo tio

1109
00:52:03,400 --> 00:52:07,240
ricevis ĉiujn tiujn arrays, ĉiuj kiuj
sin apogi hazarda aliro,

1110
00:52:07,240 --> 00:52:11,090
Mi povas komenci suprenrigardinte popola
nomi uzante kvanto de tempo kiu estas

1111
00:52:11,090 --> 00:52:14,340
proporcia al la nombro ne
de aferoj en la datumstrukturo,

1112
00:52:14,340 --> 00:52:16,330
kvazaŭ miliono ekzistantaj nomoj.

1113
00:52:16,330 --> 00:52:20,135
La kvanto de tempo ĝi prenas al mi trovi
M-Al-X-W-E-L-L en ĉi datumstrukturo estas

1114
00:52:20,135 --> 00:52:22,260
proporcia ne al la
grandeco de la datumstrukturo,

1115
00:52:22,260 --> 00:52:25,930
sed la longeco de la nomo.

1116
00:52:25,930 --> 00:52:28,440
Kaj realisme la
nomojn ni suprenrigardinte

1117
00:52:28,440 --> 00:52:29,970
estas neniam iranta esti freneza longa.

1118
00:52:29,970 --> 00:52:32,600
Eble iu havas 10 karaktero
citi, 20 karaktero nomo.

1119
00:52:32,600 --> 00:52:33,900
Estas certe finia, dekstra?

1120
00:52:33,900 --> 00:52:37,110
Estas homa sur la Tero, kiuj
havas la plej longan eblan nomon

1121
00:52:37,110 --> 00:52:39,920
sed tiu nomo estas konstanta
valoro longo, dekstra?

1122
00:52:39,920 --> 00:52:41,980
Ĝi ne varias en iu senco.

1123
00:52:41,980 --> 00:52:45,090
Do tiamaniere, ni
atingita datumstrukturo

1124
00:52:45,090 --> 00:52:47,800
ke estas konstanta tempo rigardo-supren.

1125
00:52:47,800 --> 00:52:50,670
Ĝi faras preni kelkajn paŝojn
depende de la longo de la enigo,

1126
00:52:50,670 --> 00:52:54,250
sed ne la nombron de nomo
en la datumstrukturo.

1127
00:52:54,250 --> 00:52:58,700
Do se ni duobligi la numeron de nomoj
sekva jaro de miliardo al du miliardoj,

1128
00:52:58,700 --> 00:53:03,720
trovo Maxwell tuj prenos
la ĝusta sama nombro de sep ŝtupoj

1129
00:53:03,720 --> 00:53:04,650
trovi lin.

1130
00:53:04,650 --> 00:53:08,810
Kaj tial ŝajne ni atingis
nia sankta grail de rula tempo.

1131
00:53:08,810 --> 00:53:10,860
>> Do kelkajn rapidajn anoncoj.

1132
00:53:10,860 --> 00:53:11,850
Kvizo nulo venas supren.

1133
00:53:11,850 --> 00:53:14,600
Pli sur tiu en la paso de afiŝinto
dum la venontaj kelkaj tagoj.

1134
00:53:14,600 --> 00:53:17,120
Lundo la lecture-- ĝi estas ferio
tie en Harvard lunde.

1135
00:53:17,120 --> 00:53:18,850
Ĝi ne estas en New Haven,
do ni prenas la klaso

1136
00:53:18,850 --> 00:53:20,310
al New Haven por prelego lunde.

1137
00:53:20,310 --> 00:53:22,550
Ĉio estos filmado
kaj eksudita vivas kiel kutime,

1138
00:53:22,550 --> 00:53:24,900
sed ni finos hodiaŭ
kun 30 dua tranĉeto

1139
00:53:24,900 --> 00:53:26,910
nomita "Deep Thoughts"
per Daven Farnham, kiu

1140
00:53:26,910 --> 00:53:30,850
estis inspirita lasta jaro por sabato
Night Live la "Deep Thoughts"

1141
00:53:30,850 --> 00:53:35,700
por Jack Handy, kiu
devus nun sencon.

1142
00:53:35,700 --> 00:53:38,810
>> FILMO: Kaj nun, "Deep
Pensoj "de Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tablo.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> Parolanto 1: Bone, tio estas ĝi nun.

1147
00:53:47,660 --> 00:53:48,805
Ni vidos vin proksima semajno.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Vidi ĝin en ago.

1150
00:53:56,680 --> 00:53:58,304
Do ni rigardu tion tuj.

1151
00:53:58,304 --> 00:53:59,890
Do jen, ni havas unsorted tabelo.

1152
00:53:59,890 --> 00:54:04,860
>> IAN Doug, vi povas iri antaŭen kaj rekomenco
tion por nur sekundo, bonvolu.

1153
00:54:04,860 --> 00:54:08,562
Bone, fotiloj ruliĝas, do
ago kiam ajn vi pretos, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Bone, do kion ni
havi jen unsorted tabelo.

1155
00:54:11,020 --> 00:54:13,960
Kaj mi koloraj ĉiujn la elementoj
ruĝa por indiki ke ĝi estas, fakte,

1156
00:54:13,960 --> 00:54:14,460
unsorted.

1157
00:54:14,460 --> 00:54:17,960
Do memoru, ke la unua afero ni fari
Estas ni ordigi la maldekstra duono de la tabelo.

1158
00:54:17,960 --> 00:54:20,630
Tiam ni ordigi la dekstra
duono de la tabelo.

1159
00:54:20,630 --> 00:54:22,830
Kaj ya-da, ya-da, ya-da,
ni kunfandi ilin kune.

1160
00:54:22,830 --> 00:54:24,520
Kaj ni havas tute ordo tabelo.

1161
00:54:24,520 --> 00:54:25,360
Do jen kiel kunfandi speco funkcias.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Halt, halt, halt,
tranĉo, tranĉo, tranĉo, tranĉi.

1163
00:54:27,109 --> 00:54:30,130
Doug, ne eblas simple ya-da, ya-da,
ya-donu, vian vojon tra merge varon.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: mi ĵus faris.

1165
00:54:31,970 --> 00:54:32,832
Ĝi estas bone.

1166
00:54:32,832 --> 00:54:33,540
Ni estas bone iri.

1167
00:54:33,540 --> 00:54:34,760
Ni simple teni ruliĝanta.

1168
00:54:34,760 --> 00:54:35,380
Do ĉiuokaze,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Vi devas klarigi
ĝi pli plene ol tio.

1170
00:54:37,800 --> 00:54:39,999
Tio estas nur ne sufiĉe.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, tamen ni ne
bezonas reiri al unu.

1172
00:54:41,790 --> 00:54:42,350
Ĝi estas bone.

1173
00:54:42,350 --> 00:54:45,690
Do ĉiuokaze, se ni daŭrigas kun merge--
Ian, ni estas en la mezo de la filmación.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Mi scias.

1175
00:54:46,612 --> 00:54:49,320
Kaj ni ne povas simple ya-da, ya-da,
ya-da, tra la tuta procezo.

1176
00:54:49,320 --> 00:54:52,200
Vi devas klarigi kiel la
du flankoj akiri kunfanditaj kune.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: sed ni jam
klarigis kiel la du sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Vi ĵus montrita
ili merge tabelo.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Ili konas la procezon.

1180
00:54:56,486 --> 00:54:57,172
Ili estas belaj.

1181
00:54:57,172 --> 00:54:58,380
Ni iris super ĝi dek fojojn.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Vi nur saltis rajton super ĝi.

1183
00:55:00,330 --> 00:55:03,360
Ni iras reen al unu, vi
ĉu ne ya-da, ya-da super ĝi.

1184
00:55:03,360 --> 00:55:05,480
Bone, reen al unu.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Mi devos reiri
tra ĉiuj de la diapozitivoj?

1186
00:55:07,833 --> 00:55:08,332
Mia Dio.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Estas kiel la sesa fojo, Ian.

1189
00:55:13,004 --> 00:55:13,940
Ĝi estas bone.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Bone.

1191
00:55:15,200 --> 00:55:16,590
Vi preta?

1192
00:55:16,590 --> 00:55:17,400
Granda.

1193
00:55:17,400 --> 00:55:18,950
Ago.