1
00:00:00,000 --> 00:00:03,423
>> [MUZIKO Ludante]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Bonvenon semajno 6 de sekcio.

4
00:00:08,210 --> 00:00:11,620
Ni deviis de nia normo
sekcio tempo de mardo

5
00:00:11,620 --> 00:00:14,130
posttagmezo al tiu bela dimanĉa mateno.

6
00:00:14,130 --> 00:00:17,330
Dankon por ĉiuj kiuj
aliĝis al mi hodiaŭ, sed serioze,

7
00:00:17,330 --> 00:00:18,170
ĉirkaŭvojon de aplaŭdoj.

8
00:00:18,170 --> 00:00:20,600
>> Tio estas sufiĉe granda peno.

9
00:00:20,600 --> 00:00:23,600
Mi preskaŭ ne eĉ fari
en tempo, sed estis okej.

10
00:00:23,600 --> 00:00:27,520
Do mi scias ke vi ĉiuj
ĵus faris ĝin al la kvizo.

11
00:00:27,520 --> 00:00:30,370
Unue, bonvenon al
la flip flanko de tio.

12
00:00:30,370 --> 00:00:32,917
>> Due, ni parolos pri tio.

13
00:00:32,917 --> 00:00:34,000
Ni parolos pri la kvizo.

14
00:00:34,000 --> 00:00:35,700
Ni parolos pri kiom
vi faras en la klaso.

15
00:00:35,700 --> 00:00:36,550
Vi estos bone.

16
00:00:36,550 --> 00:00:39,080
Mi havas viajn kvizojn por
vi fine de tie,

17
00:00:39,080 --> 00:00:42,120
do se vi infanoj volas preni
oni rigardas ĝin, tute bone.

18
00:00:42,120 --> 00:00:46,590
>> Tiel rapide ol ni komencos, la
tagordo por hodiaŭ estas kiel sekvas.

19
00:00:46,590 --> 00:00:48,430
Kiel vi povas vidi, ni estas
esence rapidan pafon

20
00:00:48,430 --> 00:00:52,120
tra tuta fasko de datumstrukturoj
vere, vere, vere rapide.

21
00:00:52,120 --> 00:00:54,380
Do kiel tia, ĝi ne estos
súper interaga hodiaŭ.

22
00:00:54,380 --> 00:00:59,620
Ĝi devos simple esti mi specon de bruo
aferojn vi, kaj se mi konfuzas vin,

23
00:00:59,620 --> 00:01:02,680
se mi iras tro rapide, sciigu min.

24
00:01:02,680 --> 00:01:05,200
Ili estas nur diversaj datumoj
strukturoj, kaj kiel parto

25
00:01:05,200 --> 00:01:07,070
de via pset por tiu
venonta semajno, vi

26
00:01:07,070 --> 00:01:10,340
esti demandita apliki unu el ili,
eble du el them-- ambaux

27
00:01:10,340 --> 00:01:12,319
en via pset.

28
00:01:12,319 --> 00:01:14,610
Bone, do mi simple tuj
starti kun iuj anoncoj.

29
00:01:14,610 --> 00:01:19,070
Ni transiru stakoj kaj atendovicoj pli en
profundo ol kion ni faris antaŭe la kvizo.

30
00:01:19,070 --> 00:01:20,990
Ni transiru ligitaj
listo denove, refoje,

31
00:01:20,990 --> 00:01:23,899
pli ĝisfunde ol kio
ni havis antaŭ la kvizo.

32
00:01:23,899 --> 00:01:26,440
Kaj tiam ni parolos pri hash
tabloj, arboj kaj provas, kion

33
00:01:26,440 --> 00:01:28,890
estas ĉiuj belaj necesa por via pset.

34
00:01:28,890 --> 00:01:32,925
Kaj tiam ni iros super kelkaj
helpema konsiloj por pset5.

35
00:01:32,925 --> 00:01:37,360
>> Bone, do kvizo 0.

36
00:01:37,360 --> 00:01:41,090
La mezumo estis de 58%.

37
00:01:41,090 --> 00:01:45,370
Ĝi estis tre malalta, kaj tiel vi infanoj ĉiuj
faris tre, tre bone en konsento

38
00:01:45,370 --> 00:01:46,510
kun tio.

39
00:01:46,510 --> 00:01:49,970
>> Pli malpli, regulo de thumb estas se vi estas
ene norma devio de la meznombro

40
00:01:49,970 --> 00:01:52,990
Precipe pro ni estas en malpli
comfy sekcio, vi tute bone.

41
00:01:52,990 --> 00:01:54,120
Vi estas sur trako.

42
00:01:54,120 --> 00:01:55,190
Vivo estas bona.

43
00:01:55,190 --> 00:01:58,952
>> Mi scias ke estas timiga pensi ke
Mi akiris kiel 40% sur tiu kvizo.

44
00:01:58,952 --> 00:02:00,160
Mi tuj malsukcesos tiu klaso.

45
00:02:00,160 --> 00:02:02,243
Mi promesas al vi, ke vi ne estas
tuj malsukcesos la klaso.

46
00:02:02,243 --> 00:02:03,680
Vi tute bone.

47
00:02:03,680 --> 00:02:06,850
>> Por tiuj de vi kiu superis
Dume, impresa, impona,

48
00:02:06,850 --> 00:02:08,780
kiel, serioze bone farita.

49
00:02:08,780 --> 00:02:09,689
Mi havas ilin kun mi.

50
00:02:09,689 --> 00:02:11,730
Bonvolu veni akiri ilin
fine de sekcio.

51
00:02:11,730 --> 00:02:14,520
Lasu min scii se vi havas ajnan
demandoj, demandojn kun ili.

52
00:02:14,520 --> 00:02:17,204
Se ni aldonas vian poentaron
erara, sciigu nin.

53
00:02:17,204 --> 00:02:21,240
>> Bone, do pset5, tiu estas vere
weird semajno por Yale en la senco

54
00:02:21,240 --> 00:02:24,240
ke nia pset estas pro
Merkredo tagmeze inkluzive

55
00:02:24,240 --> 00:02:27,317
Fine tago, do ĝi estas reale
teorie pro mardo tagmeze.

56
00:02:27,317 --> 00:02:29,150
Probable neniu finis
ĉe mardo tagmeze.

57
00:02:29,150 --> 00:02:30,830
Tio estas tute bone.

58
00:02:30,830 --> 00:02:33,700
Ni tuj devas oficejo horoj
ĉinokte krom lundo nokte.

59
00:02:33,700 --> 00:02:36,810
Kaj ĉiuj de la sekcioj tiu semajno
reale esti igitaj metiejoj,

60
00:02:36,810 --> 00:02:38,800
do bonvolu aperigi en
ajna sekcio vi volas,

61
00:02:38,800 --> 00:02:42,810
kaj ili estos speco de mini-pset
laborejoj por helpo pri tio.

62
00:02:42,810 --> 00:02:45,620
Do kiel tia, tio estas la nura sekcio
kie ni instrumaterialo.

63
00:02:45,620 --> 00:02:49,220
Ĉiuj aliaj sekcioj estos koncentranta
ekskluzive en helpo por la pset.

64
00:02:49,220 --> 00:02:50,146
Yeah?

65
00:02:50,146 --> 00:02:52,000
>> Spektantaro: Kie oficejo horoj?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Oficejo horoj
tonight-- ho, bona demando.

67
00:02:56,120 --> 00:03:00,580
Mi pensas oficejo horoj ĉinokte
estas en Teal aŭ ĉe Komunejo.

68
00:03:00,580 --> 00:03:02,984
Se vi kontrolu rete CS50
kaj vi iros al oficejo horoj,

69
00:03:02,984 --> 00:03:05,650
tie devus esti horaro kiu
diras vin kie ĉiuj ili estas.

70
00:03:05,650 --> 00:03:07,954
>> Mi scias ĉu ĉi-nokte
aŭ morgaŭ estas Teal,

71
00:03:07,954 --> 00:03:10,120
kaj mi pensas ke ni povas havi
commons por kelkaj noktoj.

72
00:03:10,120 --> 00:03:11,020
Mi ne certas.

73
00:03:11,020 --> 00:03:11,700
Bona demando.

74
00:03:11,700 --> 00:03:14,430
Kontrolu sur CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, demandojn pri la
horaro por la venonta kiel tri tagoj?

76
00:03:18,780 --> 00:03:21,690
Mi promesas vin uloj kiel Davido
diris, ĉi tiu estas la supro de la monteto.

77
00:03:21,690 --> 00:03:23,050
Vi uloj estas preskaŭ tie.

78
00:03:23,050 --> 00:03:24,644
Nur tri tagojn.

79
00:03:24,644 --> 00:03:26,310
Akiri tie, kaj poste ni ĉiuj venos.

80
00:03:26,310 --> 00:03:28,114
Ni havos belan CS-libera paŭzo.

81
00:03:28,114 --> 00:03:28,780
Ni revenos.

82
00:03:28,780 --> 00:03:30,779
Ni plonĝi en retejo
programado kaj disvolviĝo,

83
00:03:30,779 --> 00:03:35,150
aferojn, kiuj estas tre amuza kompari
al iuj el la aliaj psets.

84
00:03:35,150 --> 00:03:37,974
Kaj ĝi estos malvarma, kaj
ni havos multa amuza.

85
00:03:37,974 --> 00:03:38,890
Ni devos pli dolĉa.

86
00:03:38,890 --> 00:03:39,730
Pardonu pro dolĉaĵoj.

87
00:03:39,730 --> 00:03:40,945
Mi forgesis dolĉaĵoj.

88
00:03:40,945 --> 00:03:43,310
Estis malglata mateno.

89
00:03:43,310 --> 00:03:46,340
Do vi infanoj estas preskaŭ tie,
kaj mi estas vere fiera pri vi uloj.

90
00:03:46,340 --> 00:03:49,570
>> Bone, do stakigas.

91
00:03:49,570 --> 00:03:53,331
Kiu amis la demando pri Jack
kaj liaj vestoj sur la kvizo?

92
00:03:53,331 --> 00:03:53,830
Neniu?

93
00:03:53,830 --> 00:03:56,500
Okej, tio estas bone.

94
00:03:56,500 --> 00:04:00,200
>> Do esence kiel vi povas
bildo Joĉjo, ĉi ulo ĉi tie,

95
00:04:00,200 --> 00:04:03,350
amas preni la vesto
el la supro de la pilo,

96
00:04:03,350 --> 00:04:05,750
kaj li metas ĝin reen sur
la pilo post li faris.

97
00:04:05,750 --> 00:04:07,600
Do en tiu maniero, li neniam
ŝajnas esti akiranta

98
00:04:07,600 --> 00:04:10,090
al la fundo de la
pilo en sia vesto.

99
00:04:10,090 --> 00:04:12,600
Do tiu tipo de Priskribas
la baza datumstrukturo

100
00:04:12,600 --> 00:04:16,610
de kiel stako estas efektivigita.

101
00:04:16,610 --> 00:04:20,060
>> Esence, elpensi
pilo kiel ajna stako de objektoj

102
00:04:20,060 --> 00:04:24,900
kie meti aferojn sur la supro, kaj
tiam vi pop ilin de la supro.

103
00:04:24,900 --> 00:04:28,600
Do LIFO estas mallongigo ni ŝatas
al use-- Lasta En, Unua Out.

104
00:04:28,600 --> 00:04:32,480
Kaj tiel daŭris en la supron de la
pilo estas la unua kiu eliras.

105
00:04:32,480 --> 00:04:34,260
Kaj do la du terminoj
ni ŝatas asocii

106
00:04:34,260 --> 00:04:36,190
kun tiel nomataj puŝo kaj popo.

107
00:04:36,190 --> 00:04:39,790
Kiam vi puŝi ion sur la
pilo, kaj vi pop ĝin reen supren.

108
00:04:39,790 --> 00:04:43,422
>> Kaj do versxajne tiu estas speco de
abstrakta koncepto por tiuj de vi

109
00:04:43,422 --> 00:04:45,630
kiuj volas vidi kiel
fakta efektivigo de tiu

110
00:04:45,630 --> 00:04:46,740
en la reala mondo.

111
00:04:46,740 --> 00:04:50,170
Kiel multaj el vi skribis eseon
eble kiel horo antaŭ ĝi ŝuldiĝis,

112
00:04:50,170 --> 00:04:54,510
kaj vi hazarde forigita grandega
eron de ĝi, kiel hazarde?

113
00:04:54,510 --> 00:04:58,560
Kaj tiam kion fari kontrolo
ni uzas por meti ĝin reen?

114
00:04:58,560 --> 00:05:00,030
Kontrolo-Z, Yeah?

115
00:05:00,030 --> 00:05:03,640
Kontrolo-Z, do la kvanton de tempoj
ke Kontrolo-Z savis mian vivon,

116
00:05:03,640 --> 00:05:08,820
savis mian pugon, ĉiufoje
ke estas implementado tra pilo.

117
00:05:08,820 --> 00:05:13,020
>> Esence ĉiu informo
jen sur via Word dokumento,

118
00:05:13,020 --> 00:05:15,080
gets puŝis kaj krevita laŭvole.

119
00:05:15,080 --> 00:05:19,460
Kaj tiel esence kiam ajn vi
forigi ion, vi pop ĝin reen supren.

120
00:05:19,460 --> 00:05:22,820
Kaj tiam se vi bezonas ĝin reen sur, vi
puŝi ĝin, kiu estas kion Kontrolo-C faras.

121
00:05:22,820 --> 00:05:26,770
Kaj tiel reala mondo funkcio
de kiel simpla datumstrukturo

122
00:05:26,770 --> 00:05:28,690
povas helpi kun via ĉiutaga vivo.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Do struct estas la vojo
ni fakte krei pilo.

125
00:05:40,150 --> 00:05:44,720
Ni tajpu difini struct, kaj tiam
ni nomas ĝin stakigi funde.

126
00:05:44,720 --> 00:05:47,440
Kaj ene de la stako,
ni havos du parametroj

127
00:05:47,440 --> 00:05:51,580
ke ni povas esence manipuli,
do ni havos char stelo kordoj kapablo.

128
00:05:51,580 --> 00:05:55,150
>> Ĉiuj ke ĝi faras
kreas tabelon

129
00:05:55,150 --> 00:05:58,835
ke ni povas stoki ajn vi volas
kion ni povas determini lian kapablon.

130
00:05:58,835 --> 00:06:01,990
Kapablo estas nur la max kvanto de
erojn ni povas meti en tiun tabelo.

131
00:06:01,990 --> 00:06:05,660
int grandeco estas la vendotablo kiu tenas
trako de kiom da eroj estas aktuale

132
00:06:05,660 --> 00:06:07,850
en la stako.

133
00:06:07,850 --> 00:06:11,860
Tial do ni povu kontroli, A,
ambaŭ kiom granda la fakta pilo estas,

134
00:06:11,860 --> 00:06:14,850
kaj, B, kiom de tiu pilo
ni plenigis ĉar ni ne volas

135
00:06:14,850 --> 00:06:18,800
superflui super kio nia kapablo estas.

136
00:06:18,800 --> 00:06:24,340
>> Do ekzemple, ĉi amindaj
demando estis en via kvizo.

137
00:06:24,340 --> 00:06:28,160
Esence kio faras nin puŝi
sur la supro de stako.

138
00:06:28,160 --> 00:06:28,830
Sufiĉe simpla.

139
00:06:28,830 --> 00:06:30,621
Se vi rigardas ĝin,
ni trairu ĉi.

140
00:06:30,621 --> 00:06:32,640
Se [inaudible] size--
memoras, kiam ajn vi

141
00:06:32,640 --> 00:06:35,300
deziras aliri ajnan
parametro ene struct,

142
00:06:35,300 --> 00:06:40,320
vi faru la nomon de la struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> En tiu kazo, s estas
la nomo de nia stako.

144
00:06:42,720 --> 00:06:46,230
Ni volas aliri la grandeco
de ĝi, do ni faru s.size.

145
00:06:46,230 --> 00:06:50,280
Do tiel longe kiel la grandeco ne estas
egala al kapacito aŭ kiel longe

146
00:06:50,280 --> 00:06:52,940
kiel ĝi estas malpli ol kapablo,
ĉu laborus tie.

147
00:06:52,940 --> 00:06:57,180
>> Vi volas aliri interne
de via pilo, do s.strings,

148
00:06:57,180 --> 00:07:00,790
kaj vi tuj metis tiun novan numeron
ke vi volas enmeti en tie.

149
00:07:00,790 --> 00:07:05,030
Ni nur diras ni volas
enmeti int n sur la pilo,

150
00:07:05,030 --> 00:07:08,905
ni povus fari s.strings,
krampoj, s.size egalas n.

151
00:07:08,905 --> 00:07:11,030
Pro grandeco estas kie ni
nuntempe estas en la stako

152
00:07:11,030 --> 00:07:14,590
se ni tuj puŝi
ĝin, ni simple aliri

153
00:07:14,590 --> 00:07:17,370
kie ajn la grandeco estas, la
nuna pleneco de la pilo,

154
00:07:17,370 --> 00:07:21,729
kaj ni puŝi la int n sur ĝi.

155
00:07:21,729 --> 00:07:24,770
Kaj poste ni volas certigi ke
ni ankaŭ pliigante grandecon de la n,

156
00:07:24,770 --> 00:07:27,436
tiel ni povas sekvigi ni havas
aldonis ekstran aferon al la stako.

157
00:07:27,436 --> 00:07:29,660
Nun ni havas pli grandan grandecon.

158
00:07:29,660 --> 00:07:33,196
Ĉu ĉi tie sencon
ĉiuj, kiel logike funkcias?

159
00:07:33,196 --> 00:07:34,160
Estis speco de rapida.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
Spektantaro: Ĉu vi povas iri super
la s.stringss.strings [s.size] denove?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Certe, do kion faras
s.size nuntempe al ni?

163
00:07:45,808 --> 00:07:47,440
Spektantaro: Ĝi estas la aktuala grandeco.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Ekzakte, do la
nuna indekso ke nia grandeco estas je,

165
00:07:50,890 --> 00:07:57,780
kaj do ni volas meti la nova entjero
ke ni volas enmeti en s.size.

166
00:07:57,780 --> 00:07:58,760
Ĉu tio havas sencon?

167
00:07:58,760 --> 00:08:01,110
Ĉar s.strings, cxiuj
estas estas la nomo de la tabelo.

168
00:08:01,110 --> 00:08:03,510
Ĉiuj estas estas aliranta la
tabelo ene nia struct,

169
00:08:03,510 --> 00:08:06,030
kaj do se ni volas
meti n en tiun indekson,

170
00:08:06,030 --> 00:08:09,651
ni povas simple aliri ĝin
uzante krampoj s.size.

171
00:08:09,651 --> 00:08:10,150
Malvarmeta.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Bone, popo, mi _Pseudocode_ ĝin
cxar vi uloj, sed simila koncepto.

174
00:08:18,916 --> 00:08:19,790
Ĉu tio havas sencon?

175
00:08:19,790 --> 00:08:22,310
Se la grandeco estas pli granda
ol nulo, tiam vi

176
00:08:22,310 --> 00:08:25,350
scias ke vi volas preni ion
ĉar se la grandeco ne estas

177
00:08:25,350 --> 00:08:27,620
pli granda ol nulo, tiam vi
havas nenion en la stako.

178
00:08:27,620 --> 00:08:29,840
>> Do vi nur volas ekzekuti
tiun kodon, ĝi povas nur

179
00:08:29,840 --> 00:08:32,320
pop se estas iu krevi.

180
00:08:32,320 --> 00:08:35,830
Do se la grandeco estas pli granda
ol 0, ni minus la grandeco.

181
00:08:35,830 --> 00:08:40,020
Ni dekremento la grandeco kaj tiam reveni
kiom estas ene de ĝi pro

182
00:08:40,020 --> 00:08:42,710
per krevanta, ni volas
aliro ajn estas stokita

183
00:08:42,710 --> 00:08:45,694
en la indekso de la supro de la stako.

184
00:08:45,694 --> 00:08:46,610
Ĉio estas ebla solvo?

185
00:08:46,610 --> 00:08:49,693
Se mi vin uloj skribi ĉi ekstere,
volus vin uloj povos skribi gxin?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, vi infanoj povas ludi kun ĝi.

188
00:08:53,570 --> 00:08:55,252
Neniu ĉagrenoj se vi ne ricevas ĝin.

189
00:08:55,252 --> 00:08:57,460
Ni ne havas tempon por programi
ĝin hodiaŭ ĉar ni jam

190
00:08:57,460 --> 00:08:59,959
akiris multan tiuj strukturoj
iri tra, sed esence

191
00:08:59,959 --> 00:09:02,214
_pseudocode_, tre, tre simila al peli.

192
00:09:02,214 --> 00:09:03,380
Nur sekvi laŭ la logiko.

193
00:09:03,380 --> 00:09:06,092
Certiĝu vi konsentas ĉiuj
ĉefaĵoj de via struct korekte.

194
00:09:06,092 --> 00:09:06,574
Yeah?

195
00:09:06,574 --> 00:09:09,282
>> Publiko: Will tiuj diapozitivoj kaj
tiu tuta afero esti ĝis hodiaŭ-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Ĉiam, Yep.

197
00:09:11,586 --> 00:09:13,710
Mi tuj provos meti
ĉi supre kiel horo post.

198
00:09:13,710 --> 00:09:16,626
Mi retmesaĝi David David provos
meti ĝin supre kiel horo post tio.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> Bone, do tiam ni moviĝas en tiu alia
amindaj datumstrukturo nomata vosto.

201
00:09:25,470 --> 00:09:30,140
Kiel vi uloj povas vidi ĉi tie,
atendovico, por la britoj inter ni,

202
00:09:30,140 --> 00:09:32,010
ĉiuj estas estas linio.

203
00:09:32,010 --> 00:09:34,680
Do male al kio
vi pensas pilo estas,

204
00:09:34,680 --> 00:09:37,750
atendovico estas ekzakte kion
logike vi pensas ĝin estas.

205
00:09:37,750 --> 00:09:41,914
Ĝi estas tenita fare de la reguloj de FIFO,
kiu estas la unua en, Unua Out.

206
00:09:41,914 --> 00:09:43,705
Se vi estas la unua
unu en la vico, vi estas

207
00:09:43,705 --> 00:09:46,230
la unua kiu
venas el la linio.

208
00:09:46,230 --> 00:09:49,680
>> Do kion ni ŝatas nomi tiun
estas dequeueing kaj enqueueing.

209
00:09:49,680 --> 00:09:52,380
Se ni volas aldoni ion
al nia vosto, ni enqueue.

210
00:09:52,380 --> 00:09:55,690
Se ni volas dequeue, aŭ preni
io for, ni dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Do sama senco ke ni estas speco de
kreanta fiksa grandeco elementoj kiujn ni

212
00:10:03,350 --> 00:10:06,500
povas stoki iujn
aferoj, sed ni ankaŭ povas

213
00:10:06,500 --> 00:10:10,100
ŝanĝi kie ni metante
parametroj ene de ili

214
00:10:10,100 --> 00:10:13,140
bazita sur kio tipo de
funcionalidad ni volas.

215
00:10:13,140 --> 00:10:16,700
Do stakoj, ni volis la lasta
unu, N al esti la unua unu eksteren.

216
00:10:16,700 --> 00:10:19,800
Atendovico estas ni volas la unua aĵo
en esti la unua afero ekstere.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Do la struct-tipo
difini, kiel vi povas vidi,

219
00:10:26,710 --> 00:10:29,470
ĝi estas iomete malsama
el kio la stako estis

220
00:10:29,470 --> 00:10:33,120
ĉar ne nur ni devas teni
trako de kie la grandeco aktuale estas,

221
00:10:33,120 --> 00:10:37,420
ni ankaŭ volas konservi trako de la kapo
krom kie ni nune estas.

222
00:10:37,420 --> 00:10:39,580
Do mi pensas, ke estas pli facile
se mi tiros ĉi supre.

223
00:10:39,580 --> 00:10:53,270
Do imagu ni hvas atendovico,
tiel diru la estro estas ĉi tie.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
La kapo de la linio, ni
nur diru ke estas aktuale tie,

226
00:10:58,310 --> 00:11:01,809
kaj ni volas enmeti
io en la vico.

227
00:11:01,809 --> 00:11:04,350
Mi tuj vokos grandeco esence
Estas la sama afero kiel vosto,

228
00:11:04,350 --> 00:11:06,314
Fine de kien viaj atendovico estas.

229
00:11:06,314 --> 00:11:07,730
Ni nur diras grandeco pravas tie.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Do kiel faras unu feasibly
enmeti ion en atendovico?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Kio indekso ni volas meti
kie ni volas enmeti en.

234
00:11:24,130 --> 00:11:29,320
Se ĉi tiu estas la komenco de via
vosto kaj ĉi tiu estas la fino de ĝi

235
00:11:29,320 --> 00:11:31,860
aŭ la grandeco de ĝi, kie ni
volas aldoni la sekvantan objekton?

236
00:11:31,860 --> 00:11:32,920
>> Spektantaro: [inaudible]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Precize, vi volas aldoni
ĝi depende vi skribis ĝin.

238
00:11:35,920 --> 00:11:37,840
Ĉu tiu estas blanka aux blanka.

239
00:11:37,840 --> 00:11:42,630
Do vi volas aldoni ŝin probable
tie ĉar se la grandeco is--

240
00:11:42,630 --> 00:11:50,540
se tiuj estas tute plena, vi volas
aldoni ĝin ĉi tie, ĉu ne?

241
00:11:50,540 --> 00:11:57,150
>> Kaj tiel tio estas, dum tre, tre
simpla, tute ne ĉiam ĝusta

242
00:11:57,150 --> 00:12:00,690
ĉar la ĉefa diferenco
inter vosto kaj pilo

243
00:12:00,690 --> 00:12:04,350
estas ke la vosto povas
reale manipulitaj

244
00:12:04,350 --> 00:12:06,980
tiel ke la kapo ŝanĝoj
depende kie vi volas

245
00:12:06,980 --> 00:12:08,650
la komenco de via cue komenci.

246
00:12:08,650 --> 00:12:11,900
Kaj kiel rezulto, via vosto
Ankaŭ tuj ŝanĝos.

247
00:12:11,900 --> 00:12:14,770
Kaj do rigardu
tiu kodo nun.

248
00:12:14,770 --> 00:12:18,620
Kiel vi uloj ankaŭ demandis al
skribi sur la kvizo, enqueue.

249
00:12:18,620 --> 00:12:22,580
Eble ni parolos tra kial
la respondo estis kio estis.

250
00:12:22,580 --> 00:12:26,790
>> Mi ne tute konvenas ĉi linion sur unu,
sed esence tio koderon

251
00:12:26,790 --> 00:12:29,030
devus esti sur unu linio.

252
00:12:29,030 --> 00:12:30,140
Elspezi kiel 30 sekundoj.

253
00:12:30,140 --> 00:12:33,000
Rigardu kaj vidu kial
tiu estas la vojo kiu estas.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Tre, tre simila struct, tre, tre
similan strukturon kiel la antaŭa

256
00:12:55,420 --> 00:12:58,090
pilo krom eble
unu linio de kodo.

257
00:12:58,090 --> 00:13:01,190
Kaj ke unu linio de kodo
determinas la funcionalidad.

258
00:13:01,190 --> 00:13:03,900
Kaj vere diferencas
atendovico de pilo.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Ĉiu volas preni ponardopiko
ĉe klarigante kial vi havas

261
00:13:22,010 --> 00:13:24,980
akiris ĉi komplika afero tie ĉi?

262
00:13:24,980 --> 00:13:27,845
Ni vidas la revenon de nia
mirinda amiko modulo.

263
00:13:27,845 --> 00:13:31,020
Kiel vi uloj Baldaŭ venos
rekoni en programado,

264
00:13:31,020 --> 00:13:34,910
preskaŭ anytime vi bezonas ion
volvi ĉirkaŭ io,

265
00:13:34,910 --> 00:13:36,850
modulon tuj estos la maniero fari ĝin.

266
00:13:36,850 --> 00:13:40,510
Do sciante ke, ĉu iu volas
provi klarigi tiun linion de kodo?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Jes, ĉiuj respondoj estas
akceptita kaj bonvenon.

269
00:13:47,507 --> 00:13:48,840
Spektantaro: Ĉu vi parolas al mi?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Yeah.

271
00:13:49,506 --> 00:13:56,200
Publiko: Ho, ne bedaŭras.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: Bone, do ni
marŝi tra tiu kodo.

273
00:14:00,250 --> 00:14:03,642
Do kiam vi provas
aldoni ion sur atendovico,

274
00:14:03,642 --> 00:14:08,510
en la bela kazo ke la kapo okazas
esti tie, ĝi estas tre facila por ni

275
00:14:08,510 --> 00:14:10,960
nur iri al la fino
enmeti ion, ĉu ne?

276
00:14:10,960 --> 00:14:14,690
Sed la tuta punkto de atendovico estas
ke la kapo povas fakte dinamike

277
00:14:14,690 --> 00:14:17,280
ŝanĝi dependanta sur kie ni
volas la komenco de nia q esti,

278
00:14:17,280 --> 00:14:19,880
kaj kiel tia, la vosto
Ankaŭ tuj ŝanĝos.

279
00:14:19,880 --> 00:14:31,100
>> Kaj do imagi ke tiu ne estis la
atendovico, sed prefere tiu estis la vico.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Diru la estro estas ĉi tie.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Diru nia queue similis tion.

284
00:14:56,980 --> 00:15:00,190
Se ni volis movi kie
la komenco de la linio estas,

285
00:15:00,190 --> 00:15:03,400
diru ni ŝanĝis kapo
unuflanken kaj grandecoj tie.

286
00:15:03,400 --> 00:15:07,100
>> Nun ni volas aldoni ion al
tiu vosto, sed kiel vi uloj povas vidi,

287
00:15:07,100 --> 00:15:11,150
ĝi ne estas tiel simpla kiel simple
aldonu kiom estas post la grandeco

288
00:15:11,150 --> 00:15:13,630
ĉar tiam ni kuras el
limojn de nia fakta tabelo.

289
00:15:13,630 --> 00:15:16,190
Kie ni volas vere aldonas estas tie.

290
00:15:16,190 --> 00:15:18,610
Jen la beleco de atendovico
koncernas nin, vide ĝi

291
00:15:18,610 --> 00:15:22,380
aspektas kiel la linio iras tiel,
sed kiam stokitaj en datumstrukturo,

292
00:15:22,380 --> 00:15:29,370
ili doni ĝin kiel kiel ciklo.

293
00:15:29,370 --> 00:15:32,360
Ĉio envolvas ĉirkaŭ
al la fronto la sama maniero

294
00:15:32,360 --> 00:15:34,780
ke linio povas ankaŭ ĉirkaŭfermi
ĉirkaŭ depende kie vi

295
00:15:34,780 --> 00:15:36,279
volas komenco de la linio esti.

296
00:15:36,279 --> 00:15:38,630
Kaj do se ni prenas
rigardi malsupren tie, ni

297
00:15:38,630 --> 00:15:40,880
diru ni volis krei
funkcio nomita enqueue.

298
00:15:40,880 --> 00:15:43,980
Ni volis aldoni int n enen ke q.

299
00:15:43,980 --> 00:15:49,250
Se q.size q-- ni vokos ke niaj datumoj
structure-- se nia queue.size ne

300
00:15:49,250 --> 00:15:52,520
egala al kapacito aŭ se
ĝi estas malpli ol kapablo,

301
00:15:52,520 --> 00:15:55,120
q.strings estas la tabelo ene nia q.

302
00:15:55,120 --> 00:15:58,380
Ni tuj starigis
ke egalas q.heads,

303
00:15:58,380 --> 00:16:02,730
kiu estas dekstre tie, plus q.size
modulon per la kapablo, kiun

304
00:16:02,730 --> 00:16:04,290
ĉirkaŭfermi nin reen ĉirkaŭ tie.

305
00:16:04,290 --> 00:16:08,040
>> Do en tiu ekzemplo, indekso
de kapo estas 1, ĉu ne?

306
00:16:08,040 --> 00:16:11,480
La indekso de grandeco estas 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Do ni povas fari 1 plus 4 modulo
per nia kapablo kiu estas 5.

308
00:16:19,500 --> 00:16:20,920
Kion tio al ni?

309
00:16:20,920 --> 00:16:23,270
Kio estas la indico kiu
venas el tio?

310
00:16:23,270 --> 00:16:24,080
>> Publiko: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, kiu
hazarde estas ĉi tie,

312
00:16:27,870 --> 00:16:30,640
kaj tiel ni volas povi
enmeti en ĝuste ĉi tie.

313
00:16:30,640 --> 00:16:34,730
Kaj do ĉi tie ekvacio speco
de nur funkcias kun ajna nombroj

314
00:16:34,730 --> 00:16:36,750
depende kie via
kapo kaj via grandeco estas.

315
00:16:36,750 --> 00:16:38,541
Se vi scias kion tiuj
aferoj, vi scias

316
00:16:38,541 --> 00:16:43,170
ĝuste kie vi volas enigi
kiom estas post via vico.

317
00:16:43,170 --> 00:16:44,640
Ĉu tio havas sencon por ĉiuj?

318
00:16:44,640 --> 00:16:48,560
>> Mi konas ia cerba
teaser Precipe pro tio

319
00:16:48,560 --> 00:16:50,512
venis en la sekvo de via kvizo.

320
00:16:50,512 --> 00:16:52,220
Sed espereble ĉiuj
nun povas kompreni

321
00:16:52,220 --> 00:16:57,800
kial tiu solvo aŭ tiun
funkcio estas la maniero ke ĝi estas.

322
00:16:57,800 --> 00:16:59,840
Ĉiu iom neklara sur tio?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
BONE.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Kaj tial nun, se vi
volis dequeue, ĉi

327
00:17:09,970 --> 00:17:15,240
estas kie nia kapo estus sxangxigxantaj
ĉar se ni devis dequeue,

328
00:17:15,240 --> 00:17:17,030
ni ne demetas la fino de la q.

329
00:17:17,030 --> 00:17:19,130
Ni volas demeti la kapon, ĉu ne?

330
00:17:19,130 --> 00:17:24,260
Do rezulte, kapo tuj ŝanĝos,
kaj tial kiam vi enqueue,

331
00:17:24,260 --> 00:17:26,800
vi devas sekvigi
kie via kapo kaj via grandeco

332
00:17:26,800 --> 00:17:29,450
estas povi enŝovi
en la ĝusta pozicio.

333
00:17:29,450 --> 00:17:32,740
>> Do kiam vi dequeue,
Mi ankaŭ _Pseudocode_ ĝin.

334
00:17:32,740 --> 00:17:35,480
Bonvolu se vi deziras
provu kodigo ĉi ekstere.

335
00:17:35,480 --> 00:17:36,980
Vi volas movi la kapon, ĉu ne?

336
00:17:36,980 --> 00:17:39,320
Se mi volis dequeue, mi
movus la kapon super.

337
00:17:39,320 --> 00:17:40,800
Ĉi tiu estus la kapo.

338
00:17:40,800 --> 00:17:45,617
>> Kaj nia nuna grandeco volus
subtrahi ĉar ni ne plu

339
00:17:45,617 --> 00:17:46,950
havas kvar elementoj en la tabelo.

340
00:17:46,950 --> 00:17:51,370
Ni nur havas tri, kaj poste ni volas
reveni ajn estis stokita interne

341
00:17:51,370 --> 00:17:56,260
de la kapo ĉar ni volas preni tiun
valoro el tiel tre similaj al la stako.

342
00:17:56,260 --> 00:17:58,010
Nur vi prenas
el malsama loko,

343
00:17:58,010 --> 00:18:01,770
kaj vi havas religi vian montrilon
al malsama loko kiel rezulto.

344
00:18:01,770 --> 00:18:03,890
Logike, ĉiuj sekvas?

345
00:18:03,890 --> 00:18:05,690
Granda.

346
00:18:05,690 --> 00:18:10,156
>> Bone, do ni iras por paroli iomete
pli en profundo pri ligitaj listoj

347
00:18:10,156 --> 00:18:13,280
ĉar ili estos tre, tre valora
por vi en la paso de ĉi tiu semajno

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Ligitaj listoj, kiel vi infanoj
povas memori, ili cxiuj,

350
00:18:17,130 --> 00:18:22,570
estas nodoj kiuj estas nodoj de certaj
valoroj de ambaŭ valoro kaj puntero

351
00:18:22,570 --> 00:18:26,290
ke kunligitaj
per tiujn punteros.

352
00:18:26,290 --> 00:18:29,880
Kaj tial la struct en kiel
ni krei nodon tie estas ni

353
00:18:29,880 --> 00:18:33,569
havas int n, kiu estas kio ajn
la valoron en oni tendencas aŭ ŝnuro n

354
00:18:33,569 --> 00:18:35,610
aŭ kion ajn vi volas
nomas ĝin, la char stelo n.

355
00:18:35,610 --> 00:18:41,482
Struct nodo stelo, kiu estas la montrilon
ke vi volas havi en ĉiu nodo,

356
00:18:41,482 --> 00:18:43,690
vi tuj havos tiun
puntero punkton al proksimaj.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Vi havos la kapo
de ligillisto tio

359
00:18:50,040 --> 00:18:53,140
tuj atentigi al la cetera
la valoroj tiel plu kaj tiel plu

360
00:18:53,140 --> 00:18:55,290
ĝis eventuale atingi la finon.

361
00:18:55,290 --> 00:18:58,040
Kaj ĉi lasta nodo estas nur
tuj ne havas puntero.

362
00:18:58,040 --> 00:18:59,952
Ĝi tuj celi
nula, kaj tio estas kiam

363
00:18:59,952 --> 00:19:01,910
vi scias ke vi trafis la
fino de via ligitaj listo

364
00:19:01,910 --> 00:19:04,076
estas kiam via lasta montrilon
ne notas al nenio.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Do ni tuj iru iom pli en
profundo pri kiel oni farus eble

367
00:19:10,990 --> 00:19:12,400
serĉu ligillisto.

368
00:19:12,400 --> 00:19:15,460
Memoru kion estas iuj de la
malavantaĝoj de la ligitaj listoj

369
00:19:15,460 --> 00:19:19,340
versoj tabelo pri serĉoj.

370
00:19:19,340 --> 00:19:22,565
Tabelo vi povas duuma serĉo, sed
kial ne povas vin fari tion en ligillisto?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> Publiko: Ĉar ili ĉiuj konektita,
sed vi ne scias precize kie

373
00:19:30,320 --> 00:19:31,330
[Inaudible].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Jes, ĝuste tial memoru
ke la brilo de tabelo

375
00:19:34,600 --> 00:19:37,190
estis la fakto ke ni devis
senvica atingo memoro kie

376
00:19:37,190 --> 00:19:41,580
se mi volus la valoro de indekso
ses, mi povis nur diri indekso ses,

377
00:19:41,580 --> 00:19:42,407
donu al mi tiun valoron.

378
00:19:42,407 --> 00:19:45,240
Kaj tio estas ĉar tabeloj estas ordo
en apuda spaco de memoro

379
00:19:45,240 --> 00:19:48,020
en unu loko, dum
speco de ligitaj listoj

380
00:19:48,020 --> 00:19:52,820
estas hazarde intermetita ĉie,
kaj la sola maniero vi povas trovi unu

381
00:19:52,820 --> 00:19:56,890
estas per montrilo ke informas vin
la adreso de kie tiu sekva nodo.

382
00:19:56,890 --> 00:20:00,290
>> Kaj tiel kiel rezulto, la nura maniero
serĉi tra ligillisto

383
00:20:00,290 --> 00:20:01,560
estas lineara serĉo.

384
00:20:01,560 --> 00:20:05,890
Ĉar mi ne ĝuste scias kie
la 12-a valoro en la ligillisto estas,

385
00:20:05,890 --> 00:20:08,780
Mi devas kruci la tuteco
de tiu ligillisto unu

386
00:20:08,780 --> 00:20:12,450
per unu el la kapo al la unua nodo,
al la dua vertico, al la tria vertico,

387
00:20:12,450 --> 00:20:17,690
tuta vojo malsupren ĝis mi finfine akiras
al kie tiu nodo Mi serĉas estas.

388
00:20:17,690 --> 00:20:22,110
Kaj tiel en tiu senco, serĉo
sur ligillisto estas ĉiam n.

389
00:20:22,110 --> 00:20:23,040
Ĉiam n.

390
00:20:23,040 --> 00:20:25,690
Ĉiam en lineara tempo.

391
00:20:25,690 --> 00:20:28,470
>> Kaj tial la kodo en kiu
ni efektivigu tiun, kaj tiu

392
00:20:28,470 --> 00:20:32,620
estas iom nova por vi uloj ĉar vi
infanoj ne vere parolis aŭ iam

393
00:20:32,620 --> 00:20:35,000
vidita punteros en kiel
traserĉi punteros,

394
00:20:35,000 --> 00:20:37,670
do ni trairu
ĉi tre, tre malrapide.

395
00:20:37,670 --> 00:20:40,200
Do bool serĉo, dekstra,
imagu ni volas

396
00:20:40,200 --> 00:20:42,820
krei funkcion nomita
serĉo kiu revenas vera

397
00:20:42,820 --> 00:20:46,820
se vi trovis valoron ene la ligitaj
listo, kaj False alie.

398
00:20:46,820 --> 00:20:50,030
Nodo stelo listo estas
Nuntempe nur la montrilon

399
00:20:50,030 --> 00:20:52,960
al la unua ero en via ligitaj listo.

400
00:20:52,960 --> 00:20:56,700
int n estas la valoro kiun vi estas
serĉanta en tiu listo.

401
00:20:56,700 --> 00:20:58,770
>> Do nodo stelo puntero egalas listo.

402
00:20:58,770 --> 00:21:00,970
Tio signifas ke ni opcio
kaj kreante montrilon

403
00:21:00,970 --> 00:21:03,592
al tiu unua nodo ene de la listo.

404
00:21:03,592 --> 00:21:04,300
Ĉiu kun mi?

405
00:21:04,300 --> 00:21:06,530
Do se ni devis iri
tien, mi havus

406
00:21:06,530 --> 00:21:13,850
pravalorizitaj montrilo kiu indikas al
la kapo de kio ajn tiu listo estas.

407
00:21:13,850 --> 00:21:18,600
>> Kaj tiam unufoje vi akiras ĉi tie,
dum montrilon ne egala NULL,

408
00:21:18,600 --> 00:21:22,160
tiel ke estas la buklo en kiu ni estas
tuj estos poste lauxiris

409
00:21:22,160 --> 00:21:25,940
la resto de nia listo pro kio
okazas kiam puntero egalas nula?

410
00:21:25,940 --> 00:21:27,550
Ni scias ke ni have--

411
00:21:27,550 --> 00:21:28,450
>> Spektantaro: [inaudible]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Ekzakte, do ni scias ke
ni atingis la finon de listo, ĉu ne?

413
00:21:31,491 --> 00:21:34,470
Se vi iros tien, ĉiu nodo
devus esti montrante al alia nodo

414
00:21:34,470 --> 00:21:36,550
kaj tiel plu kaj tiel plu
ĝis vi batis eventuale

415
00:21:36,550 --> 00:21:41,589
la vosto de via ligillisto,
kiu havas puntero kiu ĵus

416
00:21:41,589 --> 00:21:43,130
ne notas ie alia ol neniu.

417
00:21:43,130 --> 00:21:47,510
Kaj tial vi scias ke esence
via listo estas ankoraŭ tie supren

418
00:21:47,510 --> 00:21:50,900
ĝis montrilon ne egala
nulaj ĉar iam ĝi egalas nula,

419
00:21:50,900 --> 00:21:53,310
vi scias ke estas nenia pli aĵoj.

420
00:21:53,310 --> 00:21:56,930
>> Do kiu estas la buklo en kiu ni estas
tuj havos la fakta serĉo.

421
00:21:56,930 --> 00:22:01,690
Kaj se la pointer-- ĉu vi vidas
tian sagon funkcio ekzistas?

422
00:22:01,690 --> 00:22:06,930
Do se puntero punktoj al n, se
la montrilo ĉe n egalas egalas n,

423
00:22:06,930 --> 00:22:09,180
por ke signifas ke se
la puntero kiu vi estas

424
00:22:09,180 --> 00:22:13,420
serĉanta sur la fino de ĉiu
nodo estas fakte egala al la valoro

425
00:22:13,420 --> 00:22:15,990
vi serĉas, tiam
Vi volas reveni vera.

426
00:22:15,990 --> 00:22:19,280
Do resume, se vi estas ĉe nodo ke
havas la valoron, ke vi serĉas,

427
00:22:19,280 --> 00:22:23,550
vi scias, ke vi estis
povis sukcese serĉu.

428
00:22:23,550 --> 00:22:27,150
>> Alie, vi volas agordi
vian sagon al la sekva nodo.

429
00:22:27,150 --> 00:22:28,850
Tion tiun linion tie faras.

430
00:22:28,850 --> 00:22:31,750
Puntero egalas puntero sekva.

431
00:22:31,750 --> 00:22:33,360
Cxiu komprenas kiel tio funkcias?

432
00:22:33,360 --> 00:22:36,580
>> Kaj esence vi tuj nur
kruci la tuteco de la listo,

433
00:22:36,580 --> 00:22:41,920
rekomenciganta via puntero ĉiu tempo ĝis
vi finfine atingis la finon de la listo.

434
00:22:41,920 --> 00:22:45,030
Kaj vi scias, ke ne ekzistas
pli nodoj al traserĉi,

435
00:22:45,030 --> 00:22:47,999
kaj tiam vi povas reveni falsaj
ĉar vi scias ke, ho, nu,

436
00:22:47,999 --> 00:22:50,540
se mi povis serĉi
tra la tuteco de la listo.

437
00:22:50,540 --> 00:22:54,530
Se en ĉi tiu ekzemplo, se mi volus
serĉi la valoro de 10,

438
00:22:54,530 --> 00:22:57,250
kaj mi komencos je la kapo, kaj
Mi traserĉos la vojo malsupren,

439
00:22:57,250 --> 00:23:00,550
kaj mi fine atingis tion, kio
puntero kiu notas al nula,

440
00:23:00,550 --> 00:23:04,415
Mi scias ke, crap, mi supozas 10 Ne en
tiu listo ĉar mi ne povis trovi ĝin.

441
00:23:04,415 --> 00:23:06,520
Kaj mi estas fine de la listo.

442
00:23:06,520 --> 00:23:11,040
Kaj tiaokaze vi scias
Mi tuj revenos falsaj.

443
00:23:11,040 --> 00:23:12,900
>> Lasu ke trempi en ĉar iomete.

444
00:23:12,900 --> 00:23:17,350
Tiu estos bela
grava por via pset.

445
00:23:17,350 --> 00:23:21,140
La logiko de tio estas tre simpla, eble
sintakse ĵus efektiviganta ĝin.

446
00:23:21,140 --> 00:23:23,365
Vi infanoj deziras fari
certas ke vi komprenos.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Malvarmeta.

449
00:23:27,650 --> 00:23:32,560
>> OK, do kiel ni estus
enmeto nodoj, dekstra,

450
00:23:32,560 --> 00:23:35,380
en listo ĉar memori
kio estas la kiom da avantaĝoj

451
00:23:35,380 --> 00:23:39,230
havi ligillisto kontre
tabelo en terminoj de stokado?

452
00:23:39,230 --> 00:23:41,110
>> Spektantaro: Ĝi estas dinamika,
do ĝi estas pli facile to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Precize,
do ĝi estas dinamika, kiu

454
00:23:43,180 --> 00:23:46,880
signifas ke ĝi povas pligrandigi kaj retiri
dependanta sur la uzanto bezonoj.

455
00:23:46,880 --> 00:23:56,570
Kaj tiel, en tiu senso, ni ne bezonas
malŝpari nenecesa memoro ĉar mi

456
00:23:56,570 --> 00:24:00,850
se mi ne scias kiom da valoroj Mi volas
al vendejo, ĝi ne havas sencon por mi

457
00:24:00,850 --> 00:24:04,310
krei tabelo ĉar
se mi volas konservi 10 valoroj

458
00:24:04,310 --> 00:24:08,380
kaj mi kreos tabelo de 1.000, jen
multajn malŝparita memoro, donitan.

459
00:24:08,380 --> 00:24:11,180
Tial ni volas uzi kunligita
listo por povi dinamike

460
00:24:11,180 --> 00:24:13,860
ŝanĝi aŭ ŝrumpi nia grandeco.

461
00:24:13,860 --> 00:24:17,040
>> Kaj tial faras inserción
iom pli komplikita.

462
00:24:17,040 --> 00:24:20,810
Ĉar ni ne povas aliri hazarde elementoj
la vojo, ke ni devus de tabelo.

463
00:24:20,810 --> 00:24:24,270
Se mi volas enmeti ero
en la sepa indekso,

464
00:24:24,270 --> 00:24:26,930
Mi nur povas enmeti ĝin
en la sepa indekso.

465
00:24:26,930 --> 00:24:30,020
Sur ligillisto, ĝi ne
tute labori kiel facile,

466
00:24:30,020 --> 00:24:34,947
kaj do se ni volas enmeti
la tie en la ligillisto,

467
00:24:34,947 --> 00:24:36,280
vide, ĝi estas tre facile vidi.

468
00:24:36,280 --> 00:24:39,363
Ni nur volas enmeti ĝin ĝuste tie,
ĝuste en la komenco de la listo,

469
00:24:39,363 --> 00:24:40,840
dekstra post kapo.

470
00:24:40,840 --> 00:24:44,579
>> Sed la maniero en kiu ni havas religi
la punteros estas iom malsimpla

471
00:24:44,579 --> 00:24:47,620
aŭ, logike, ĝi havas sencon, sed
Vi volas certigi ke vi havas ĝin

472
00:24:47,620 --> 00:24:50,250
tute malsupren ĉar
la lasta afero vi volas

473
00:24:50,250 --> 00:24:52,990
estas religi puntero la
maniero ke ni faras ĉi tie.

474
00:24:52,990 --> 00:24:58,170
Se vi dereference la
montrilo de la kapo ĝis 1,

475
00:24:58,170 --> 00:25:01,086
tiam subite la
resto de via ligitaj listo

476
00:25:01,086 --> 00:25:04,680
estas perdita ĉar vi havas ne reale
kreis provizoran nenion.

477
00:25:04,680 --> 00:25:06,220
Jen montris la 2.

478
00:25:06,220 --> 00:25:10,080
Se vi preferas religi la montrilo, tiam la
resto de via listo estas tute perdita.

479
00:25:10,080 --> 00:25:13,310
Do vi deziras esti
tre, zorgoplenaj

480
00:25:13,310 --> 00:25:17,010
unue atribui la
montrilo el ajn vi

481
00:25:17,010 --> 00:25:20,150
volas enmeti en kie ajn
vi volas, kaj tiam vi

482
00:25:20,150 --> 00:25:22,710
povas dereference la resto de via listo.

483
00:25:22,710 --> 00:25:25,250
>> Do ĉi validas por kien
vi provas enmeti en.

484
00:25:25,250 --> 00:25:27,520
Se vi volas enigi ĉe la
kapo, se vi volas respondi tie,

485
00:25:27,520 --> 00:25:29,455
se vi volas enmeti en
Fine, nu, fine mi

486
00:25:29,455 --> 00:25:30,910
divenu vi simple
ne havas puntero, sed vi

487
00:25:30,910 --> 00:25:33,830
volas certigi ke vi ne
perdi la reston de via listo.

488
00:25:33,830 --> 00:25:36,640
Vi ĉiam volas certigi
via nova nodo notas

489
00:25:36,640 --> 00:25:39,330
al kio ajn vi
volas enmeti en,

490
00:25:39,330 --> 00:25:42,170
kaj tiam vi povas aldoni la ĉenante plu.

491
00:25:42,170 --> 00:25:43,330
Ĉiu klara?

492
00:25:43,330 --> 00:25:45,427
>> Ĉi tuj estos
unu el la veraj temoj.

493
00:25:45,427 --> 00:25:48,010
Unu de la plej gravaj aferoj
vi tuj havos sur via pset

494
00:25:48,010 --> 00:25:51,340
estas ke vi tuj provi krei
ligillisto kaj enigaĵo aferoj

495
00:25:51,340 --> 00:25:53,340
sed tiam simple perdi la
resto de via ligitaj listo.

496
00:25:53,340 --> 00:25:54,900
Kaj vi tuj estos kiel mi
ne scias kial tio okazas?

497
00:25:54,900 --> 00:25:58,040
Kaj ĝi estas doloro trapasi
kaj serĉi ĉiun de viaj indikoj.

498
00:25:58,040 --> 00:26:02,100
>> Kaj mi garantias vin sur ĉi pset,
skribado kaj desegnado tiuj nodoj eksteren

499
00:26:02,100 --> 00:26:03,344
estos tre, tre helpema.

500
00:26:03,344 --> 00:26:06,010
Do vi povas tute sekvigi
de kie ĉiuj viaj indikoj estas,

501
00:26:06,010 --> 00:26:08,540
kio okazas erara,
kie ĉiuj nodoj estas via,

502
00:26:08,540 --> 00:26:12,660
kion vi bezonas fari por aliri aŭ
enmeti aŭ forigi aŭ ajna de ili.

503
00:26:12,660 --> 00:26:14,550
Ĉiu bona kun tiu?

504
00:26:14,550 --> 00:26:15,050
Malvarmeta.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Do se ni volis rigardi la kodon?

507
00:26:22,600 --> 00:26:24,470
Ho, mi ne scias se ni
povas vidi the-- Bone, do

508
00:26:24,470 --> 00:26:27,940
ĉe la supro ĉiu estas estas funkcio
nomita insert kie ni volas

509
00:26:27,940 --> 00:26:31,365
enmeti int n en la ligillisto.

510
00:26:31,365 --> 00:26:32,740
Ni tuj trairu ĉi.

511
00:26:32,740 --> 00:26:34,770
Ĝi estas multe da kodo, multan novan sintakson.

512
00:26:34,770 --> 00:26:36,220
Ni estos OK.

513
00:26:36,220 --> 00:26:39,120
>> Do supren ĉe la supro, kiam ajn
ni volas krei ion

514
00:26:39,120 --> 00:26:42,380
kion ni devas fari, Precipe se vi
deziras ĝin ne esti stokitaj sur la stako

515
00:26:42,380 --> 00:26:43,920
sed en la amaso?

516
00:26:43,920 --> 00:26:45,460
Ni iras al malloc, dekstra?

517
00:26:45,460 --> 00:26:48,240
Do ni tuj krei puntero.

518
00:26:48,240 --> 00:26:52,074
Nodo, montrilo, novaj egaluloj
malloc la grandeco de nodo

519
00:26:52,074 --> 00:26:53,740
ĉar ni volas ke nodo estu kreita.

520
00:26:53,740 --> 00:26:56,720
Ni volas la kvanto de
memoro kiu nodo dissxutas

521
00:26:56,720 --> 00:26:59,300
esti asignita por la
kreo de la nova nodo.

522
00:26:59,300 --> 00:27:02,270
>> Kaj tiam ni tuj kontrolu
ĉu nova egaluloj egalas nula.

523
00:27:02,270 --> 00:27:03,370
Memoru kion ni diris?

524
00:27:03,370 --> 00:27:06,470
Kion ajn vi malloc,
Kion vi devas ĉiam fari?

525
00:27:06,470 --> 00:27:09,490
Vi devas ĉiam kontroli por vidi
ĉu aŭ ne ke estas nula.

526
00:27:09,490 --> 00:27:13,620
>> Ekzemple, se via mastruma
sistemo estis tute plena,

527
00:27:13,620 --> 00:27:17,060
se vi jam ne havis memoron ĉe
ĉiuj kaj vi provas malloc,

528
00:27:17,060 --> 00:27:18,410
revenus nula por vi.

529
00:27:18,410 --> 00:27:21,094
Kaj do se vi provas uzi ĝin
kiam montrante al nula,

530
00:27:21,094 --> 00:27:23,260
vi ne tuj povis
aliri tiun informon.

531
00:27:23,260 --> 00:27:27,010
Do kiel tia, ni volis fari
certas ke kiam ajn vi mallocing,

532
00:27:27,010 --> 00:27:30,500
vi ĉiam kontrolas, ĉu
tiu memoro, al vi estas nula.

533
00:27:30,500 --> 00:27:33,670
Kaj se ĝi ne estas, tiam ni povas movi
sur kun la resto de nia kodo.

534
00:27:33,670 --> 00:27:36,140
>> Do ni tuj
pravalorizi la nova nodo.

535
00:27:36,140 --> 00:27:39,050
Ni tuj faros novan n egalas n.

536
00:27:39,050 --> 00:27:42,390
Kaj tiam ni tuj faros
metis novajn la montrilo sur nova

537
00:27:42,390 --> 00:27:46,900
al nula ĉar nun ni ne
volas nenion por ŝi atentigi al.

538
00:27:46,900 --> 00:27:48,755
Ni ne scias kien
ĝi tuj metos vin,

539
00:27:48,755 --> 00:27:50,630
kaj tiam se ni volas
enmeti ĝin ĉe la kapo,

540
00:27:50,630 --> 00:27:53,820
tiam ni povas reassign
la sagon al la kapo.

541
00:27:53,820 --> 00:27:58,530
Ĉu ĉiuj sekvi la logikon
de kie ke okazas?

542
00:27:58,530 --> 00:28:02,502
>> Ĉiuj ni faras estas kreante nova
nodo, fiksanta la montrilon al nula,

543
00:28:02,502 --> 00:28:04,210
kaj tiam reassigning
ĝin al la kapo se ni

544
00:28:04,210 --> 00:28:06,320
scias ni volas enmeti gxin en la kapo.

545
00:28:06,320 --> 00:28:09,420
Kaj tiam la kapo tuj
atentigi al tiu nova nodo.

546
00:28:09,420 --> 00:28:11,060
Ĉiu OK kun tiu?

547
00:28:11,060 --> 00:28:12,380
>> Do estas du-paŝa procezo.

548
00:28:12,380 --> 00:28:14,760
Vi devas atribui unua
ajn vi kreas.

549
00:28:14,760 --> 00:28:18,260
Ŝanĝu ke puntero al la
referenci kaj tiam vi

550
00:28:18,260 --> 00:28:21,400
povas ia dereference
la unua montrilo

551
00:28:21,400 --> 00:28:22,972
kaj punkto al la nova nodo.

552
00:28:22,972 --> 00:28:25,680
Kie ajn vi volas enigi ĝin,
ke logiko tuj teni vera.

553
00:28:25,680 --> 00:28:27,530
>> Estas ia kiel asignanta
temporal variablo.

554
00:28:27,530 --> 00:28:28,700
Memoru, vi havas
certigi ke vi

555
00:28:28,700 --> 00:28:30,346
ne perdas trakon de se vi interŝanĝante.

556
00:28:30,346 --> 00:28:33,470
Vi volas certigi ke vi havas
temporal variablo tian tenas

557
00:28:33,470 --> 00:28:35,620
trako de kie tiu afero
estas stokita por ke vi

558
00:28:35,620 --> 00:28:41,190
ne perdas neniun valoron en la kurso
de kiel rompado ĉirkaŭe kun ĝi.

559
00:28:41,190 --> 00:28:42,710
>> Bone, do kodo estos tie.

560
00:28:42,710 --> 00:28:45,020
Vi uloj rigardu post sekcio.

561
00:28:45,020 --> 00:28:48,060
Estos tie.

562
00:28:48,060 --> 00:28:50,280
>> Do mi supozas kiel faras
ĉi diferenciĝas se ni volis

563
00:28:50,280 --> 00:28:52,300
enmeti en la mezo aŭ la fino?

564
00:28:52,300 --> 00:28:57,892
Ĉu iu havas ideon pri kio estas la
_pseudocode_ kiel la logika referenco

565
00:28:57,892 --> 00:29:00,350
ke ni prenus se ni volis
enmeti ĝin en la mezo?

566
00:29:00,350 --> 00:29:03,391
Do se ni volis enmeti ĝin ĉe la
kapo, ĉiuj ni faras estas krei nova nodo.

567
00:29:03,391 --> 00:29:06,311
Ni starigu la montrilo de tiu
nova nodo al kiom la kapo,

568
00:29:06,311 --> 00:29:08,310
kaj poste ni almetis la kapon
al la nova nodo, ĉu ne?

569
00:29:08,310 --> 00:29:11,560
Se ni volis enmeti ĝin en la mezo
de la listo, kion ni devas fari?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Spektantaro: estus ankoraŭ
esti simila procezo

572
00:29:16,110 --> 00:29:19,114
de kiel asignanta puntero kaj
tiam asignanta ke puntero,

573
00:29:19,114 --> 00:29:20,530
sed ni devus loki tie.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Ekzakte, do precize
la sama procezo krom vi

575
00:29:23,560 --> 00:29:27,820
devas lokalizi kie ekzakte vi
volas ke novaj montrilon al internigi,

576
00:29:27,820 --> 00:29:44,790
do se mi volas enmeti en
la mezo de ligitaj list-- OK,

577
00:29:44,790 --> 00:29:46,370
diru ke estas nia ligillisto.

578
00:29:46,370 --> 00:29:49,500
Se ni volas enmeti ĝin ĉi tie,
ni iras al krei novan nodon.

579
00:29:49,500 --> 00:29:50,520
Ni tuj malloc.

580
00:29:50,520 --> 00:29:52,220
Ni tuj kreos novan nodon.

581
00:29:52,220 --> 00:29:55,940
Ni tuj asigni la
montrilo de tiu nodo tie.

582
00:29:55,940 --> 00:29:58,335
>> Sed la problemo kiu diferencas
de kie la kapo estas

583
00:29:58,335 --> 00:30:00,490
estas ke ni sciis ĝuste
kie la kapo estas.

584
00:30:00,490 --> 00:30:01,930
Estis ĝuste en la unua, ĉu ne?

585
00:30:01,930 --> 00:30:04,870
Sed tie ni devas konservi trako
de kie ni enmeto ĝin.

586
00:30:04,870 --> 00:30:07,930
Se ni enmeto nia
nodo tie, ni havas

587
00:30:07,930 --> 00:30:12,270
certigi ke la
unu antaŭa al tiu nodo

588
00:30:12,270 --> 00:30:14,172
Estas kiu reassigns la montrilo.

589
00:30:14,172 --> 00:30:16,380
Tial do vi devas ia
sekvigi du aferoj.

590
00:30:16,380 --> 00:30:19,420
Se vi konservi trako de kie tiu
nodo aktuale estas enmeto en.

591
00:30:19,420 --> 00:30:23,280
Vi ankaŭ devas konservi trako de kie
la antaŭa nodo ke vi rigardas

592
00:30:23,280 --> 00:30:24,340
estis ankaŭ tie.

593
00:30:24,340 --> 00:30:25,830
Ĉiu bona kun tiu?

594
00:30:25,830 --> 00:30:26,500
BONE.

595
00:30:26,500 --> 00:30:28,000
>> Kion pri enmeto en la fino?

596
00:30:28,000 --> 00:30:34,220
Se mi volis aldoni ĝin here-- se mi volus
aldoni novan nodon al la fino de listo,

597
00:30:34,220 --> 00:30:37,009
kiom povus mi iras pri faranta tion?

598
00:30:37,009 --> 00:30:39,300
Publiko: Do ​​nuntempe, la
lasta onies indikis nula.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Yeah.

600
00:30:40,960 --> 00:30:43,560
Precize, do ĉi tiu
aktuale estas pinta scii,

601
00:30:43,560 --> 00:30:46,720
kaj do versxajne, en tiu senco, estas
tre facile aldoni al la fino de listo.

602
00:30:46,720 --> 00:30:51,810
Ĉiuj vi devas fari estas starigis ĝin
egala al nula kaj tiam Eksplodo.

603
00:30:51,810 --> 00:30:53,070
Dekstre, tre facila.

604
00:30:53,070 --> 00:30:53,960
Tre simpla.

605
00:30:53,960 --> 00:30:56,430
>> Tre simila al la
kapo, sed logike vi

606
00:30:56,430 --> 00:30:59,690
volas certigi ke la paŝoj
vi prenas al fari ion el tiu,

607
00:30:59,690 --> 00:31:01,500
vi sekvajn kune.

608
00:31:01,500 --> 00:31:04,420
Estas tre facile, en la mezo
de via kodo, akiri kaptita supre sur,

609
00:31:04,420 --> 00:31:05,671
ho, mi havas tiom da montriloj.

610
00:31:05,671 --> 00:31:07,461
Mi ne scias kie
io estas indikante.

611
00:31:07,461 --> 00:31:09,170
Mi eĉ ne scias kiu nodo Mi estas sur.

612
00:31:09,170 --> 00:31:11,490
Kio okazas?

613
00:31:11,490 --> 00:31:13,620
>> Relax, trankviligi, prenu profunda spiro.

614
00:31:13,620 --> 00:31:15,530
Eltiru vian ligillisto.

615
00:31:15,530 --> 00:31:18,800
Se vi diras, mi scias, kie ĝuste
Mi bezonas enmeti ĉi en

616
00:31:18,800 --> 00:31:22,970
kaj mi scias precize kiel religi mian
punteros, multe, multe pli facile bildigi

617
00:31:22,970 --> 00:31:27,200
fjordon multe, multe pli facile ne
perdiĝi en la cimoj de via kodo.

618
00:31:27,200 --> 00:31:29,410
Ĉiu OK kun tiu?

619
00:31:29,410 --> 00:31:31,380
BONE.

620
00:31:31,380 --> 00:31:35,120
>> Do mi supozas estas koncepto kiun ni havas ne
vere priparolis antaŭ nun,

621
00:31:35,120 --> 00:31:38,131
kaj mi supozas ke vi probable
ne renkontas multe yet--

622
00:31:38,131 --> 00:31:40,880
ĝi estas speco de progresinta concept--
estas ke ni efektive havas datumojn

623
00:31:40,880 --> 00:31:43,900
strukturo nomiĝas duoble ligitaj listo.

624
00:31:43,900 --> 00:31:46,390
Do kiel vi uloj povas vidi,
ĉiuj ni faras estas kreante

625
00:31:46,390 --> 00:31:50,400
fakta valoro, ekstra
montrilon sur ĉiu el niaj nodoj

626
00:31:50,400 --> 00:31:52,660
kiu ankaŭ notas al la antaŭa nodo.

627
00:31:52,660 --> 00:31:58,170
Do ne nur ni havas niajn
nodoj atentigi al la venonta unu.

628
00:31:58,170 --> 00:32:01,430
Ili ankaŭ indikas la antaŭa.

629
00:32:01,430 --> 00:32:04,310
Mi tuj ignori tiujn du nun.

630
00:32:04,310 --> 00:32:06,740
>> Sekve vi cxeno
kiu povas movi ambaŭ manieroj,

631
00:32:06,740 --> 00:32:09,630
kaj tiam ĝi estas iom pli facile
al logike sekvi kune.

632
00:32:09,630 --> 00:32:11,896
Kiel tie, anstataŭ
konservanta trako de, ho, mi

633
00:32:11,896 --> 00:32:14,520
devas scii ke ĉi tiu nodo estas
kiu mi devos religi,

634
00:32:14,520 --> 00:32:17,532
Mi povas nur iri tien kaj
nur tiri la antaŭa.

635
00:32:17,532 --> 00:32:19,490
Tiam mi scias precize kie
tio estas, kaj tiam vi

636
00:32:19,490 --> 00:32:21,130
ne devas trairi la
tuteco de la ligitaj listo.

637
00:32:21,130 --> 00:32:22,180
Estas iom pli facile.

638
00:32:22,180 --> 00:32:24,960
>> Sed kiel tiaj, vi havos duoble
la kvanto de punteros,

639
00:32:24,960 --> 00:32:26,960
jen duobla la kvanto de memoro.

640
00:32:26,960 --> 00:32:28,950
Estas multaj indikoj spuri.

641
00:32:28,950 --> 00:32:32,140
Estas iom pli kompleksaj, sed estas
iom pli uzanto amika depende

642
00:32:32,140 --> 00:32:34,080
sur kion vi provas sukcesi.

643
00:32:34,080 --> 00:32:36,910
>> Do tiu tipo de datumoj
strukturo totalmente ekzistas,

644
00:32:36,910 --> 00:32:40,280
kaj la strukturon por estas tre, tre
simpla krom ĉiuj vi devi estas,

645
00:32:40,280 --> 00:32:43,850
anstataŭ simple montrilo al proksima,
vi ankaŭ havas montrilon por antaŭa.

646
00:32:43,850 --> 00:32:45,940
Jen ĉio la diferenco estis.

647
00:32:45,940 --> 00:32:47,740
Ĉiu bona kun tiu?

648
00:32:47,740 --> 00:32:48,240
Malvarmeta.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Bone, do nun mi estas
por vere elspezi probable

651
00:32:53,280 --> 00:32:56,870
kiel 15 al 20 minutoj aŭ la plejparton
de la resto de la tempo en sekcio

652
00:32:56,870 --> 00:32:58,360
parolante pri hash tabloj.

653
00:32:58,360 --> 00:33:02,590
Kiel multaj el vi infanoj
legis pset5 specifon?

654
00:33:02,590 --> 00:33:03,620
Bone, bone.

655
00:33:03,620 --> 00:33:06,160
Jen altaj ol la 50% de normale.

656
00:33:06,160 --> 00:33:07,560
Estas bone.

657
00:33:07,560 --> 00:33:10,345
>> Do kiel vi infanoj vidos,
vi estas defio en pset5

658
00:33:10,345 --> 00:33:16,790
Estos implementar vortaron
kie vi ŝarĝi super 140.000 vortoj

659
00:33:16,790 --> 00:33:20,610
ke ni donu al vi kaj literumilo
ĝin kontraŭ la tuta de la teksto.

660
00:33:20,610 --> 00:33:22,580
Ni donos al vi hazarda
pecoj de literaturo.

661
00:33:22,580 --> 00:33:23,520
Ni donos al vi La Odiseado.

662
00:33:23,520 --> 00:33:24,561
Ni donos al vi La Iliado.

663
00:33:24,561 --> 00:33:26,350
Ni donos al vi Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Kaj via defio
Estos por literumilo

665
00:33:28,220 --> 00:33:31,760
ĉiu unuopa vorto en ĉiu
de tiuj vortaroj

666
00:33:31,760 --> 00:33:34,960
esence kun niaj literumilo.

667
00:33:34,960 --> 00:33:38,620
Kaj tiel ekzistas kelkaj partoj
krei ĉi pset,

668
00:33:38,620 --> 00:33:41,970
unue vi volas esti
povis reale ŝarĝi

669
00:33:41,970 --> 00:33:43,970
ĉiuj vortoj en vian
vortaro, kaj tiam vi

670
00:33:43,970 --> 00:33:45,530
deziras povi
literumilo ĉiuj ili.

671
00:33:45,530 --> 00:33:48,780
Kaj tiel kiel tiaj, vi tuj postuli
datumstrukturo kiu povas fari tion rapide

672
00:33:48,780 --> 00:33:50,790
kaj kompetente kaj dinamike.

673
00:33:50,790 --> 00:33:52,900
>> Do mi supozas la plej facila
maniero fari tion, vi

674
00:33:52,900 --> 00:33:55,010
verŝajne krei tabelon, dekstra?

675
00:33:55,010 --> 00:33:58,910
La plej facila maniero de stokado estas vi
povas krei tabelon de 140.000 vortoj

676
00:33:58,910 --> 00:34:03,400
kaj simple meti ilin ĉiuj tie kaj
tiam kruci ilin per duuma serĉo

677
00:34:03,400 --> 00:34:06,780
aŭ por selektadoj aŭ not--
bedaŭras ke estas ordigado.

678
00:34:06,780 --> 00:34:10,729
Vi povas ordigi ilin kaj tiam kruci ilin
per duuma serĉo aŭ nur lineara serĉo

679
00:34:10,729 --> 00:34:13,730
kaj nur finaj vortoj, sed ke
prenas grandegan kvanton da memoro,

680
00:34:13,730 --> 00:34:15,190
kaj ĝi ne estas tre efika.

681
00:34:15,190 --> 00:34:18,350
>> Kaj tial ni tuj komencos
parolas pri manieroj de farado

682
00:34:18,350 --> 00:34:20,110
nia rultempo pli efika.

683
00:34:20,110 --> 00:34:23,190
Kaj nia celo estas atingi
konstanta tempo kie

684
00:34:23,190 --> 00:34:25,810
Estas preskaŭ kiel sensilo, kie
vi havos tujan aliron.

685
00:34:25,810 --> 00:34:28,560
Se mi volis serĉi ion,
Mi volas povi ĝuste,

686
00:34:28,560 --> 00:34:30,810
eksplodo, trovas ĝin ĝuste, kaj tiri ĝin ekstere.

687
00:34:30,810 --> 00:34:34,100
Kaj tiel strukturo en kiu
ni estos igante tre proksima

688
00:34:34,100 --> 00:34:37,569
por povi aliri konstanta
tempo, tiu sankta grail

689
00:34:37,569 --> 00:34:41,370
en programado de konstanta
tempo nomata hash tablo.

690
00:34:41,370 --> 00:34:45,370
Kaj David antaŭe menciita la
[Inaudible] iomete en prelego,

691
00:34:45,370 --> 00:34:49,100
sed ni tuj vere
plonĝo en profunda tiu semajno

692
00:34:49,100 --> 00:34:51,780
sur peco kiu estas rilate
kiom hash tablo funkcias.

693
00:34:51,780 --> 00:34:53,949
>> Do la vojo ke hash
tablo verkoj, ekzemple,

694
00:34:53,949 --> 00:35:00,230
se mi volis konservi aron da vortoj,
faskon da vortoj en la angla lingvo,

695
00:35:00,230 --> 00:35:02,940
Mi povus teorie metis
banano, pomo, kivo, tenilo, paro,

696
00:35:02,940 --> 00:35:04,980
kaj melono ĉiuj sur nur tabelo.

697
00:35:04,980 --> 00:35:07,044
Cxiuj povis havi en kaj esti trovi.

698
00:35:07,044 --> 00:35:09,210
Estus speco de doloro
serĉu tra kaj aliro,

699
00:35:09,210 --> 00:35:12,920
sed la facila maniero fari tiun estas
ke ni povas krei fakte strukturo

700
00:35:12,920 --> 00:35:15,680
nomata hash tablo kie nin hash.

701
00:35:15,680 --> 00:35:19,880
Ni kuras ĉiujn de niaj klavoj tra
hash funkcio, ekvacio,

702
00:35:19,880 --> 00:35:22,600
kiu igas ilin ĉiujn en
ia valoro

703
00:35:22,600 --> 00:35:28,740
ke poste ni povos stoki sur
esence tabelo de ligillisto.

704
00:35:28,740 --> 00:35:32,570
>> Kaj do ĉi tie, se ni volis
stoki anglaj vortoj,

705
00:35:32,570 --> 00:35:37,250
ni povis potenciale simple, mi ne faras
scias, turni ĉiujn unua literoj

706
00:35:37,250 --> 00:35:39,630
en ia nombro.

707
00:35:39,630 --> 00:35:43,140
Do, ekzemple, se mi volus
A esti sinonimo apple--

708
00:35:43,140 --> 00:35:47,460
aŭ kun la indico de 0, kaj
B esti sinonima kun 1,

709
00:35:47,460 --> 00:35:51,030
ni povas havi 26 eniroj
kiu povas nur stoki

710
00:35:51,030 --> 00:35:53,610
ĉiuj leteroj de la
alfabeto kiu ni komencos kun.

711
00:35:53,610 --> 00:35:56,130
Kaj tiam ni povas havi
pomo je la indekso de 0.

712
00:35:56,130 --> 00:35:59,160
Ni povas havi banano ĉe la indico de
1, melono ĉe la indico de 2,

713
00:35:59,160 --> 00:36:00,540
kaj tiel plu kaj tiel antaŭen.

714
00:36:00,540 --> 00:36:04,460
Kaj tiel, se mi volis serĉi
miaj hash tablo kaj aliro pomo,

715
00:36:04,460 --> 00:36:07,560
Mi scias pomon komenciĝas per
A, kaj mi scias precize

716
00:36:07,560 --> 00:36:10,860
ke ĝi devas esti kaj la hash
tablo ĉe indekso 0 ĉar

717
00:36:10,860 --> 00:36:13,620
de la funkcio antaŭe asignita.

718
00:36:13,620 --> 00:36:16,572
>> Do mi ne scias, ni
uzanto programo kie

719
00:36:16,572 --> 00:36:18,780
vi estos akuzita
arbitrarily-- ne arbitre,

720
00:36:18,780 --> 00:36:22,530
kun provanta pensoplene
elpensi bonan ekvacioj

721
00:36:22,530 --> 00:36:25,460
povi disvastigi
el ĉiuj viaj valoroj

722
00:36:25,460 --> 00:36:29,370
en maniero ili povas facile aliri
ĝin poste kun kiel ekvacio

723
00:36:29,370 --> 00:36:31,130
ke vi mem scias.

724
00:36:31,130 --> 00:36:35,210
Do en tiu senco, se mi volis iri al
mango, mi scias, ho, ĝi komenciĝas kun m.

725
00:36:35,210 --> 00:36:37,134
Devas esti ĉe la indico de 12.

726
00:36:37,134 --> 00:36:38,800
Mi ne devas traserĉi nenion.

727
00:36:38,800 --> 00:36:42,080
Mi scias exactly-- mi povus nur iri al
la indekso de 12 kaj tiri ke ekstere.

728
00:36:42,080 --> 00:36:45,520
>> Ĉiu klara pri kiel oni
hash tablo funkcio laboras?

729
00:36:45,520 --> 00:36:48,380
Estas speco de nur pli kompleksa tabelo.

730
00:36:48,380 --> 00:36:50,010
Jen ĉio estas.

731
00:36:50,010 --> 00:36:51,630
BONE.

732
00:36:51,630 --> 00:36:57,690
>> Do mi supozas ke ni renkontas
tiu demando de kio

733
00:36:57,690 --> 00:37:06,390
okazas se vi havas plurajn aferojn
kiuj donas vin la sama indico?

734
00:37:06,390 --> 00:37:10,570
Do diru nia funkcio, ĉiuj ĝi
faris estis preni tiun unuan literon

735
00:37:10,570 --> 00:37:14,490
kaj turni kiuj en
respektiva 0 tra 25 indekso.

736
00:37:14,490 --> 00:37:17,137
Tio estas tute bone se
vi nur havas unu de ĉiu.

737
00:37:17,137 --> 00:37:18,970
Sed la dua vi komencas
havante pli, vi estas

738
00:37:18,970 --> 00:37:20,910
tuj havas kio nomiĝas kolizio.

739
00:37:20,910 --> 00:37:25,580
>> Do se mi provas enmeti enterigi en hash
tablo kiu jam havas bananon sur ĝi,

740
00:37:25,580 --> 00:37:27,870
kio okazos kiam
vi provas enmeti tio?

741
00:37:27,870 --> 00:37:30,930
Malbonaj aferoj ĉar banano
jam ekzistas ene de la indekso

742
00:37:30,930 --> 00:37:33,800
ke vi volas konservi ĝin en.

743
00:37:33,800 --> 00:37:35,560
Bero ia similas, ha, kion mi faru?

744
00:37:35,560 --> 00:37:37,080
Mi ne scias kien iri.

745
00:37:37,080 --> 00:37:38,410
Kiel mi solvi ĉi?

746
00:37:38,410 --> 00:37:41,150
>> Do vi infanoj volas ia
vidu ni faros ĉi delikata afero

747
00:37:41,150 --> 00:37:44,810
Kie ni povas ia reale
krei ligillisto en niaj tabeloj.

748
00:37:44,810 --> 00:37:46,840
Kaj do la plej facila vojo
pensi pri tio,

749
00:37:46,840 --> 00:37:50,830
ĉiuj hash tablo estas
tabelo de ligitaj listoj.

750
00:37:50,830 --> 00:37:55,670
Kaj tiel, en tiu senco, vi devos
tiu bela tabelo de punteros,

751
00:37:55,670 --> 00:37:58,740
kaj tiam ĉiu montrilon en
ke valoro, en tiu indekso,

752
00:37:58,740 --> 00:38:00,740
povas fakte indiki al aliaj aferoj.

753
00:38:00,740 --> 00:38:05,720
Kaj tial vi havas ĉiujn tiujn apartajn
ĉenoj elspezi de unu granda tabelo.

754
00:38:05,720 --> 00:38:07,960
>> Kaj do ĉi tie, se mi
volis enmeti bero,

755
00:38:07,960 --> 00:38:11,220
Mi scias, OK, mi tuj enigo
ĝin tra mia hash funkcio.

756
00:38:11,220 --> 00:38:15,070
Mi tuj finos kun la indico de
1, kaj tiam mi tuj povos havi

757
00:38:15,070 --> 00:38:20,410
nur malgrandan subaron de tiu
giganto 140.000-vorto vortaro.

758
00:38:20,410 --> 00:38:24,220
Kaj tiam mi povas nur rigardi
tra 1/26 de tiu.

759
00:38:24,220 --> 00:38:27,910
>> Kaj tiel do mi povas simple enŝovi
bero aŭ antaŭ aŭ post banano

760
00:38:27,910 --> 00:38:28,820
en tiu kazo?

761
00:38:28,820 --> 00:38:29,700
Post, dekstra?

762
00:38:29,700 --> 00:38:33,920
Kaj do vi tuj volas
enmeti ĉi nodo post banano,

763
00:38:33,920 --> 00:38:36,667
kaj tiel vi tuj enmeti
ĉe la vosto de tiu ligillisto.

764
00:38:36,667 --> 00:38:38,500
Mi tuj iros reen
al tiu antaŭa glitejo,

765
00:38:38,500 --> 00:38:40,680
do vi uloj povas vidi kiel
hash funkcio laboras.

766
00:38:40,680 --> 00:38:43,980
>> Do krada funkcio estas tiu ekvacio
ke vi uzas specon de via enigo

767
00:38:43,980 --> 00:38:46,940
tra akiri ajn indekso
vi volas atribui al ĝi.

768
00:38:46,940 --> 00:38:51,130
Kaj tiel, en tiu ekzemplo, ĉiuj ni volis
fari estis preni la unua litero,

769
00:38:51,130 --> 00:38:55,890
igi tiun en indekso, tiam ni
povas stoki ke en nia hash funkcio.

770
00:38:55,890 --> 00:39:00,160
Ĉiuj ni faras ĉi tie estas ni
konvertanta la unua litero.

771
00:39:00,160 --> 00:39:04,770
Do keykey [0] estas nur la unua litero
sendistinge kordoj ni havas,

772
00:39:04,770 --> 00:39:05,720
ni pasante en.

773
00:39:05,720 --> 00:39:09,740
Ni konvertas ke al supra, kaj
ni forprenante per majuskla A,

774
00:39:09,740 --> 00:39:11,740
do ĉiuj kiuj faras
donas al ni kelkajn

775
00:39:11,740 --> 00:39:13,670
en kiu ni povas hash niajn valorojn sur.

776
00:39:13,670 --> 00:39:16,550
>> Kaj tiam ni tuj
reveni hash modulo grandeco.

777
00:39:16,550 --> 00:39:19,340
Estu tre, tre zorgema
ĉar, teorie, tie

778
00:39:19,340 --> 00:39:21,870
via hash valoro povis esti malfinio.

779
00:39:21,870 --> 00:39:23,660
Ĝi povus simple daŭrigi kaj sur kaj sur.

780
00:39:23,660 --> 00:39:26,080
Ĝi povus esti kelkaj vere,
vere granda valoro,

781
00:39:26,080 --> 00:39:29,849
sed ĉar via hash tablo ke
vi kreis nur havas 26 indeksas,

782
00:39:29,849 --> 00:39:31,890
Vi volas certigi vian
modulusing por ke vi

783
00:39:31,890 --> 00:39:33,848
ne run-- ĝi estas la sama
aĵo kiel via queue--

784
00:39:33,848 --> 00:39:36,320
por ke vi ne kuras ekstere la
fundo de via hash funkcio.

785
00:39:36,320 --> 00:39:39,210
>> Vi volas enpaki ĝin ĉirkaŭ
sammaniere en [inaudible] kiam

786
00:39:39,210 --> 00:39:41,750
vi havis kiel tre,
tre grandan leteron, vi

787
00:39:41,750 --> 00:39:43,740
ne volis ke al
nur kuri for la fino.

788
00:39:43,740 --> 00:39:46,948
Sama afero ĉi tie, vi volas certigi
ĝi ne kuras for la fino envolviendo

789
00:39:46,948 --> 00:39:48,330
ĉirkaŭ la supro de la tablo.

790
00:39:48,330 --> 00:39:50,530
Do tio estas nur tre
simpla hash funkcio.

791
00:39:50,530 --> 00:39:56,570
Ĉiuj kiuj faris estis preni la unuan
letero de whatever niaj enigo estis

792
00:39:56,570 --> 00:40:01,660
kaj turni kiuj en indico kiu
Ni povus meti en niajn hash tablo.

793
00:40:01,660 --> 00:40:05,450
>> Yeah, kaj tiel kiel mi diris antaŭe,
la vojo, ke ni solvi kolizioj

794
00:40:05,450 --> 00:40:09,330
en nia hash tabloj estas havanta,
kion ni nomas, ĉenante.

795
00:40:09,330 --> 00:40:13,860
Do se vi provas enmeti plurajn
vortoj kiuj komenciĝas kun la sama afero,

796
00:40:13,860 --> 00:40:16,145
vi tuj havos unu hash valoro.

797
00:40:16,145 --> 00:40:18,770
Aguacates kaj pomon, se vi havas
ruli ĝin per nia hash funkcio,

798
00:40:18,770 --> 00:40:21,450
tuj donos al vi la
sama nombro, la nombro de 0.

799
00:40:21,450 --> 00:40:24,550
Kaj tial la maniero kiun ni decidu, ke estas
ke ni povas efektive ia ligas ilin

800
00:40:24,550 --> 00:40:27,010
kune tra ligitaj listoj.

801
00:40:27,010 --> 00:40:29,600
>> Kaj tiel en tiu senco,
vi uloj povas vidi specon

802
00:40:29,600 --> 00:40:32,640
de kiel datumstrukturoj ke
ni estis fiksanta antaŭe

803
00:40:32,640 --> 00:40:35,870
kiel sekvinberoj ligillisto speco
de povas kunvenos.

804
00:40:35,870 --> 00:40:38,860
Kaj tiam vi povas krei multe
pli efika datumstrukturoj

805
00:40:38,860 --> 00:40:43,350
kiu povas manipuli grandajn kvantojn de
datumoj, kiuj dinamike regrandigi depende

806
00:40:43,350 --> 00:40:44,870
sur viaj bezonoj.

807
00:40:44,870 --> 00:40:45,620
Ĉiu klara?

808
00:40:45,620 --> 00:40:47,580
Ĉiu speco de klara
kio okazas ĉi tie?

809
00:40:47,580 --> 00:40:52,110
>> Se mi volis insert-- kio estas
frukto kiu komenciĝas per, mi ne scias,

810
00:40:52,110 --> 00:40:54,726
B, aliaj ol bero, banano.

811
00:40:54,726 --> 00:40:55,710
>> Publiko: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, rubuso.

813
00:40:57,910 --> 00:41:00,530
Kie rubusbero iras tien?

814
00:41:00,530 --> 00:41:04,251
Nu, ni fakte ne ordo
ĉi ankoraŭ, sed teorie

815
00:41:04,251 --> 00:41:06,250
se ni volus havi tiun
en alfabeta ordo,

816
00:41:06,250 --> 00:41:07,944
kie devus BlackBerry iras?

817
00:41:07,944 --> 00:41:09,210
>> Spektantaro: [inaudible]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Precize, post ĉi tie, ĉu ne?

819
00:41:11,100 --> 00:41:14,950
Sed ĉar ĝi estas tre malfacile
reorder-- Mi supozas lin tuŝas al vi uloj.

820
00:41:14,950 --> 00:41:17,920
Vi uloj povas tute
apliki kion vi volas.

821
00:41:17,920 --> 00:41:20,730
La pli efika maniero
fari tion eble

822
00:41:20,730 --> 00:41:24,570
estus ordigi vian ligitaj
listo en alfabeta ordo,

823
00:41:24,570 --> 00:41:26,520
kaj do kiam vi estas
enmeto aferoj, vi volas

824
00:41:26,520 --> 00:41:28,632
certi enigi ilin
en alfabeta ordo

825
00:41:28,632 --> 00:41:30,590
por ke poste kiam vi estas
provas serĉi ilin,

826
00:41:30,590 --> 00:41:32,410
vi ne devas trairi ĉiu.

827
00:41:32,410 --> 00:41:35,290
Vi scias precize kie
ĝi estas, kaj ĝi estas pli facila.

828
00:41:35,290 --> 00:41:39,100
>> Sed se vi ia havas
aferojn intermetita hazarde,

829
00:41:39,100 --> 00:41:41,420
vi ankoraŭ havos
al _traverse_ ĝi anyways.

830
00:41:41,420 --> 00:41:44,990
Kaj do se mi volis nur
enmeti rubusbero tie

831
00:41:44,990 --> 00:41:47,470
kaj mi volis serĉi
ĝi, mi scias, ho, rubusbero

832
00:41:47,470 --> 00:41:52,012
devas komenci kun la indico de 1, do mi
scias instantáneamente nur serĉu ĉe 1.

833
00:41:52,012 --> 00:41:53,970
Kaj tiam mi povas ia
kruci la ligillisto

834
00:41:53,970 --> 00:41:56,120
ĝis mi alvenas al BlackBerry,
kaj then-- yeah?

835
00:41:56,120 --> 00:41:59,550
>> Publiko: Se vi provas create--
Mi supozas kiel ĉi estas tre simpla hash

836
00:41:59,550 --> 00:42:00,050
funkcio.

837
00:42:00,050 --> 00:42:02,835
Kaj se ni volis fari
multoblaj tavoloj de tiu kiel,

838
00:42:02,835 --> 00:42:05,870
OK, ni volas apartigi en
kiel ĉiuj alfabeta literoj

839
00:42:05,870 --> 00:42:09,040
kaj tiam denove ŝati alia aro
de alfabeta literoj ene de tiu,

840
00:42:09,040 --> 00:42:11,715
ni metante kiel hash
tablo ene hash tablo,

841
00:42:11,715 --> 00:42:13,256
aŭ kiel funkcio ene funkcio?

842
00:42:13,256 --> 00:42:14,880
Aŭ estas that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Do via hash
function-- via hash tablo

844
00:42:17,510 --> 00:42:19,360
povas esti kiel granda kiel vi deziras ĝin.

845
00:42:19,360 --> 00:42:21,930
Do en tiu senco, mi pensis
gxi estas tre facila, tre

846
00:42:21,930 --> 00:42:25,320
simpla por mi nur ia bazita
sur literoj de la unua vorto.

847
00:42:25,320 --> 00:42:28,690
Do ekzistas nur 26 eblojn.

848
00:42:28,690 --> 00:42:32,650
Mi povas nur akiri 26 ebloj de
0 ĝis 25 ĉar ili povas nur

849
00:42:32,650 --> 00:42:36,510
komenci de A ĝis Z. Sed Se vi volis
aldoni, eble, pli komplekseco

850
00:42:36,510 --> 00:42:39,260
aŭ rapida kuri tempo por via
hash tablo, vi absolute

851
00:42:39,260 --> 00:42:40,760
povas fari ĉiajn aferojn.

852
00:42:40,760 --> 00:42:43,330
Vi povas fari vian propran
ekvacio kiu donas

853
00:42:43,330 --> 00:42:48,000
pli dissendo en via
vortoj, tiam kiam vi serĉi,

854
00:42:48,000 --> 00:42:49,300
ĝi tuj estos pli rapida.

855
00:42:49,300 --> 00:42:52,100
>> Ĝi estas tute ĝis vi infanoj
kiom vi volas apliki tion.

856
00:42:52,100 --> 00:42:55,140
Pensu pri ĝi kiel ĵus siteloj.

857
00:42:55,140 --> 00:42:57,376
Se mi volus havi
26 siteloj, mi tuj

858
00:42:57,376 --> 00:42:59,420
ordigi aferojn en tiuj siteloj.

859
00:42:59,420 --> 00:43:02,980
Sed mi tuj havas faskon
de aĵoj en ĉiu sitelo

860
00:43:02,980 --> 00:43:05,890
do se vi volas fari ĝin
rapida kaj pli efika,

861
00:43:05,890 --> 00:43:07,190
mi havas cent sitelojn.

862
00:43:07,190 --> 00:43:09,290
>> Sed tiam vi devas eltrovi
maniero ordigi aferojn tiel ke ili estas

863
00:43:09,290 --> 00:43:11,040
en la konvena sitelo ili devus esti en.

864
00:43:11,040 --> 00:43:13,331
Sed tiam kiam vi efektive
volas rigardi ke sitelo

865
00:43:13,331 --> 00:43:16,410
ĝi estas multe pli rapida ĉar tie estas
malpli havajxoj en ĉiu sitelo.

866
00:43:16,410 --> 00:43:20,250
Do, jes, tio estas vere
la lertaĵo por vi uloj en pset5

867
00:43:20,250 --> 00:43:22,360
estas ke vi estos
defiita simple krei

868
00:43:22,360 --> 00:43:26,170
kiom estas la plej efika
funkcio povas pensi ke

869
00:43:26,170 --> 00:43:28,520
povi stoki kaj kontroli tiujn valorojn.

870
00:43:28,520 --> 00:43:30,840
>> Tute supren al vi infanoj
tamen vi volas fari ĝin,

871
00:43:30,840 --> 00:43:32,229
sed tio estas vere bona punkto.

872
00:43:32,229 --> 00:43:34,520
Ke tia logiko vi
volas komenci pensi pri

873
00:43:34,520 --> 00:43:37,236
estas, nu, kial ne mi faras pli siteloj.

874
00:43:37,236 --> 00:43:39,527
Kaj tiam mi devos serĉi
malpli aĵoj, kaj tiam eble mi

875
00:43:39,527 --> 00:43:41,640
havas malsaman hash funkcio.

876
00:43:41,640 --> 00:43:45,500
>> Jes, ekzistas multe da manieroj fari tion
pset, iuj estas pli rapida ol aliaj.

877
00:43:45,500 --> 00:43:50,630
Mi tute tuj ĝuste vidi kiel
rapida estis la plej rapida vi infanoj estos

878
00:43:50,630 --> 00:43:55,170
povos akiri vian funkciojn labori.

879
00:43:55,170 --> 00:43:58,176
OK, ĉiuj bone sur
ĉeni kaj hash tabloj?

880
00:43:58,176 --> 00:44:00,800
Ĝi estas fakte kiel tre simpla
koncepto se vi pensas pri ĝi.

881
00:44:00,800 --> 00:44:05,160
Ĉiuj estas estas disigante ajn
viaj enigoj estas en siteloj,

882
00:44:05,160 --> 00:44:10,670
ordigado de ili, tiam serĉanta la
listas ke estas asociita kun.

883
00:44:10,670 --> 00:44:11,852
>> Malvarmeta.

884
00:44:11,852 --> 00:44:18,160
Bone, nun ni havas malsaman specon
de datuma strukturo kiu nomiĝas arbo.

885
00:44:18,160 --> 00:44:20,850
Ni plu iru kaj parolu pri tries
kiuj estas klare malsamaj,

886
00:44:20,850 --> 00:44:22,330
sed en la sama kategorio.

887
00:44:22,330 --> 00:44:29,010
Esence, ĉiu arbo estas anstataŭe
organizi datumojn en la maniero lineal

888
00:44:29,010 --> 00:44:32,560
ke hash tablo does-- vi
Sciu, ĝi estas atingis supro kaj fundo

889
00:44:32,560 --> 00:44:37,900
kaj tiam vi ia ligi ekstere de it-- a
arbo havas maksimuman kiun vi nomas la radiko,

890
00:44:37,900 --> 00:44:40,220
kaj tiam ĝi havas foliojn tute ĉirkaŭ ĝi.

891
00:44:40,220 --> 00:44:42,390
>> Kaj do ĉiuj vi havas ĉi tie
estas nur la pinta nodo

892
00:44:42,390 --> 00:44:45,980
kiu notas al aliaj nodoj, kiuj punktoj
al pli nodoj, kaj tiel plu kaj tiel antaŭen.

893
00:44:45,980 --> 00:44:48,130
Kaj tial vi nur devas forkiĝanta branĉoj.

894
00:44:48,130 --> 00:44:53,255
Estas nur alia maniero de organizado
datumoj, kaj ĉar ni nomas ĝin arbo,

895
00:44:53,255 --> 00:44:56,270
vi uloj just-- estas nur
modelita eksteren rigardi kiel arbo.

896
00:44:56,270 --> 00:44:57,670
Tial ni nomas ĝin arboj.

897
00:44:57,670 --> 00:44:59,370
>> Hash tablo aspektas kiel tablo.

898
00:44:59,370 --> 00:45:01,310
Arbo nur aspektas kiel arbo.

899
00:45:01,310 --> 00:45:03,300
Ĉiuj estas estas aparta
maniero organizi nodoj

900
00:45:03,300 --> 00:45:06,020
Dependanta sur kio viaj bezonoj estas.

901
00:45:06,020 --> 00:45:11,810
>> Do vi havas radikon kaj
tiam vi havas foliojn.

902
00:45:11,810 --> 00:45:15,380
La maniero kiun ni povas aparte
pensi pri ĝi estas duuma arbo,

903
00:45:15,380 --> 00:45:18,150
duuma arbo estas nur
specifa tipo de arbo

904
00:45:18,150 --> 00:45:22,450
kie ĉiu nodo nur punktoj
al, je maks, du aliaj nodoj.

905
00:45:22,450 --> 00:45:25,434
Kaj do jen vi havas distingan
simetrio en via arbo

906
00:45:25,434 --> 00:45:28,600
ke faciligante ia rigardu
ĉe kio aprezas vi estas ĉar tiam vi

907
00:45:28,600 --> 00:45:30,150
havas ĉiam maldekstran aŭ dekstren.

908
00:45:30,150 --> 00:45:33,150
Ekzistas neniam kiel maldekstra tria el
maldekstren aŭ kvarono de la maldekstro.

909
00:45:33,150 --> 00:45:36,358
Ĝi estas nur vi havas maldekstra kaj dekstra
kaj vi povas serĉi aŭ de tiuj du.

910
00:45:36,358 --> 00:45:38,980
Kaj do kial estas tiu utila?

911
00:45:38,980 --> 00:45:40,980
La maniero ke tiu estas
utila estas se vi serĉas

912
00:45:40,980 --> 00:45:42,890
serĉi tra valoroj, dekstra?

913
00:45:42,890 --> 00:45:45,640
Prefere ol efektivigado duuma
serĉu en eraro tabelo,

914
00:45:45,640 --> 00:45:49,260
se vi volis povi enigi nodoj
kaj forigos nodoj ĉe volo kaj ankaŭ

915
00:45:49,260 --> 00:45:52,185
konservi la serĉo
kapabloj de duuma serĉo.

916
00:45:52,185 --> 00:45:54,560
Do tiamaniere, ni estas speco de
tricking-- memoras kiam ni

917
00:45:54,560 --> 00:45:56,530
diris ligitaj listoj ne povas duuma serĉo?

918
00:45:56,530 --> 00:46:01,700
Ni ia kreante datumstrukturo
ke lertaĵoj ke en laboranta.

919
00:46:01,700 --> 00:46:05,034
>> Kaj tiel ĉar ligitaj listoj estas linearaj,
ili nur ligas unu post la alia.

920
00:46:05,034 --> 00:46:06,950
Ni povas ia havas
Alispeca punteros

921
00:46:06,950 --> 00:46:09,408
ke punkto al malsamaj nodoj
kiu povas helpi nin per serĉo.

922
00:46:09,408 --> 00:46:12,590
Kaj do ĉi tie, se mi volus
havas duuma serĉo arbo,

923
00:46:12,590 --> 00:46:14,090
Mi scias ke miaj mezo se 55.

924
00:46:14,090 --> 00:46:18,280
Mi simple tuj krei ke
kiel mia mezo, kiel mia radiko,

925
00:46:18,280 --> 00:46:20,770
kaj tiam mi iros al havi
valoroj spin off de ĝi.

926
00:46:20,770 --> 00:46:25,610
>> Do jen, se mi iros por serĉi
la valoro de 66, mi povas komenci ĉe 55.

927
00:46:25,610 --> 00:46:27,310
Estas 66 pli granda ol 55?

928
00:46:27,310 --> 00:46:30,970
Jes ĝi estas, do mi scias mi mus serĉu
I n la dekstra montrilo de tiu arbo.

929
00:46:30,970 --> 00:46:32,440
Mi iros al 77.

930
00:46:32,440 --> 00:46:35,367
OK, estas 66 malpli ol aŭ pli granda ol 77?

931
00:46:35,367 --> 00:46:37,950
Ĝi estas malpli ol, tiel vi scias, ho,
kiu devas esti la maldekstra nodo.

932
00:46:37,950 --> 00:46:41,410
>> Do jen ni estas speco de konservado
ĉiuj la grandaj aferoj pri arrays,

933
00:46:41,410 --> 00:46:44,420
tiel kiel dinamika regrandigo
de objektoj, estante

934
00:46:44,420 --> 00:46:49,530
povos enmeti kaj forigi laŭvole,
sen devi maltrankviligi la fiksa

935
00:46:49,530 --> 00:46:50,370
kvanto de spaco.

936
00:46:50,370 --> 00:46:52,820
Ni ankoraŭ konservas ĉiujn
tiujn mirindaĵojn

937
00:46:52,820 --> 00:46:57,140
dum ankaŭ povante konservi la
ensaluti kaj serĉu tempo de duuma serĉo

938
00:46:57,140 --> 00:47:00,450
ke ni nur antaŭe
kapabla akiri frazo.

939
00:47:00,450 --> 00:47:06,310
>> Cool datumstrukturo, ia
kompleksa implementar, la nodo.

940
00:47:06,310 --> 00:47:08,311
Kiel vi povas vidi, ĉiuj ĝi
estas la struct de la nodo

941
00:47:08,311 --> 00:47:10,143
estas ke vi havas maldekstre
kaj dekstra montrilo.

942
00:47:10,143 --> 00:47:11,044
Jen ĉio estas.

943
00:47:11,044 --> 00:47:12,960
Do anstataŭ nur
havanta x aŭ antaŭan.

944
00:47:12,960 --> 00:47:15,920
Vi havas maldekstra aŭ dekstra, kaj tiam
vi povas ia ligas ilin kune

945
00:47:15,920 --> 00:47:16,836
tamen vi tiel elektos.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, Ni efektive tuj
nur preni kelkajn minutojn.

948
00:47:24,270 --> 00:47:25,790
Do ni tuj iru tien.

949
00:47:25,790 --> 00:47:28,270
Kiel mi diris antaŭe,
Mi specon de klarigis

950
00:47:28,270 --> 00:47:31,520
la logiko malantaŭ kiel ni
estus traserĉi ĉi.

951
00:47:31,520 --> 00:47:33,860
Ni tuj provos
pseudocoding ĉi ekstere al vidi

952
00:47:33,860 --> 00:47:38,000
se ni povas ia apliki la
sama logiko de binara serĉo

953
00:47:38,000 --> 00:47:40,055
al malsama tipo de datumstrukturo.

954
00:47:40,055 --> 00:47:45,049
Se vi infanoj volas preni kiel paro
Minutoj ĵus pensas pri tiu.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
BONE.

957
00:48:46,925 --> 00:48:51,407
Bone, mi tuj
efektive nur donas vin the-- ne,

958
00:48:51,407 --> 00:48:52,990
ni parolos pri la _pseudocode_ unue.

959
00:48:52,990 --> 00:48:56,580
Do ĉu iu volas
doni ponardopiko ĉe kio

960
00:48:56,580 --> 00:49:02,100
la unua afero vi deziras fari kiam
vi elkomencanta serĉado estas?

961
00:49:02,100 --> 00:49:04,460
Se ni serĉas
la valoro de 66, kio estas

962
00:49:04,460 --> 00:49:07,940
ni unue volas fari se
ni volas duuma serĉo ĉi arbo?

963
00:49:07,940 --> 00:49:10,760
>> Spektantaro: Vi volas rigardi dekstra
kaj rigardu maldekstren kaj vidu [inaudible]

964
00:49:10,760 --> 00:49:11,230
pli granda nombro.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Jes, ĝuste.

966
00:49:12,271 --> 00:49:15,350
Do vi tuj rigardi vian radikon.

967
00:49:15,350 --> 00:49:18,180
Ekzistas multaj manieroj vi povas nomi
ĝin, via patro nodo homoj diras.

968
00:49:18,180 --> 00:49:21,317
Mi ŝatas diri radiko ĉar
jen kiel la radiko de la arbo.

969
00:49:21,317 --> 00:49:23,400
Vi tuj rigardi
via radika vertico, kaj vi estas

970
00:49:23,400 --> 00:49:26,940
tuj vidos estas 66 grandaj
ol aŭ malpli ol 55.

971
00:49:26,940 --> 00:49:30,360
Kaj se ĝi estas pli granda ol, nu, tio estas
granda ol, kie ni volas rigardi?

972
00:49:30,360 --> 00:49:32,000
Kie ni volas serĉi nun, ĉu ne?

973
00:49:32,000 --> 00:49:34,340
Ni volas serĉi
dekstra duono de tiu arbo.

974
00:49:34,340 --> 00:49:38,390
>> Do ni havas, oportune, a
puntero kiu notas al la dekstra.

975
00:49:38,390 --> 00:49:44,325
Kaj tiel do ni povas fiksi
nia nova radiko esti 77.

976
00:49:44,325 --> 00:49:46,450
Ni povas nur iri al kie ajn
la puntero estas indikante.

977
00:49:46,450 --> 00:49:49,100
Nu, ho, tie ni startanta
ĉe 77, kaj ni povas nur

978
00:49:49,100 --> 00:49:51,172
fari tion rekursie denove kaj denove.

979
00:49:51,172 --> 00:49:52,880
Tiamaniere, vi afabla
de havi funkcion.

980
00:49:52,880 --> 00:49:57,430
Vi havas vojon de serĉado ke vi
povas nur ripeti denove kaj denove kaj denove,

981
00:49:57,430 --> 00:50:02,720
Dependanta sur kie vi volas rigardi
ĝis vi fine atingos la valoro

982
00:50:02,720 --> 00:50:04,730
ke vi estas serĉanta.

983
00:50:04,730 --> 00:50:05,230
Sencon?

984
00:50:05,230 --> 00:50:07,800
>> Mi volis montri al vi la fakta
kodo, kaj ĝi estas multe da kodo.

985
00:50:07,800 --> 00:50:08,674
Ne necesas Freak Out.

986
00:50:08,674 --> 00:50:09,910
Ni parolos tra ĝi.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Efektive, ne.

989
00:50:14,020 --> 00:50:15,061
Tiu estis nur _pseudocode_.

990
00:50:15,061 --> 00:50:17,860
OK, ke estis nur la _pseudocode_,
kio estas iom kompleksa,

991
00:50:17,860 --> 00:50:19,751
sed estas tute bone.

992
00:50:19,751 --> 00:50:21,000
Ĉiu sekvanta kune tie?

993
00:50:21,000 --> 00:50:24,260
Se la radiko estas nula, reveno
falsa pro tiu rimedo

994
00:50:24,260 --> 00:50:26,850
vi eĉ ne havas tie ion.

995
00:50:26,850 --> 00:50:31,376
>> Se radiko n estas la valoro, tial se ĝi
hazarde estas la unu vi rigardas,

996
00:50:31,376 --> 00:50:34,000
tiam vi tuj reveni vera
ĉar vi scias ke vi trovis ĝin.

997
00:50:34,000 --> 00:50:36,250
Sed se la valoro estas malpli
ol radiko de n, vi estas

998
00:50:36,250 --> 00:50:38,332
tuj serĉu maldekstre
infano aŭ la maldekstra folio,

999
00:50:38,332 --> 00:50:39,540
kion ajn vi volas nomi ĝin.

1000
00:50:39,540 --> 00:50:41,750
Se la valoro estas pli granda ol radiko,
vi tuj serĉu la dekstra arbo,

1001
00:50:41,750 --> 00:50:44,610
tiam nur ruli la funkcio
tra serĉo denove.

1002
00:50:44,610 --> 00:50:48,037
>> Se radiko estas nula, ke tiu
signifas vi atingis la finon?

1003
00:50:48,037 --> 00:50:50,120
Tio signifas ke vi ne havas
pli pli folioj esplori,

1004
00:50:50,120 --> 00:50:52,230
tiam sciu, ho, mi
supozas ke ne tien

1005
00:50:52,230 --> 00:50:55,063
ĉar post mi rigardis tra
la tuta afero kaj ĝi ne estas tie ĉi,

1006
00:50:55,063 --> 00:50:56,930
ĝi simple ne povus esti ĉi tie.

1007
00:50:56,930 --> 00:50:58,350
>> Ĉu tio havas sencon por ĉiuj?

1008
00:50:58,350 --> 00:51:03,230
Do estas kiel duuma serĉo konservante
la kapabloj de ligitaj listoj.

1009
00:51:03,230 --> 00:51:09,200
Cool, kaj tiel la dua tipo
de datumstrukturo vi infanoj

1010
00:51:09,200 --> 00:51:13,180
povas provi efektiviganta vian pset,
Vi nur devas elekti unu metodo.

1011
00:51:13,180 --> 00:51:19,430
Sed eble alternativa metodo al
la hash tablo estas kion ni nomas trie.

1012
00:51:19,430 --> 00:51:24,080
>> Ĉiuj trie estas estas
specifa tipo de arbo kiun

1013
00:51:24,080 --> 00:51:28,600
havas valorojn kiuj iras al aliaj valoroj.

1014
00:51:28,600 --> 00:51:31,450
Do anstataŭ havi binaran
arbo en la senco, ke nur unu

1015
00:51:31,450 --> 00:51:35,940
afero povas celi du, vi povas havi
unu aferon punkto al multaj, multaj aĵoj.

1016
00:51:35,940 --> 00:51:39,450
Vi esence havas arrays
ene de kiu vi stoki

1017
00:51:39,450 --> 00:51:41,790
punteros ke indikas aliaj tabeloj.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Do la nodo de kiel ni
difinus trie

1020
00:51:49,460 --> 00:51:52,590
Estas ni volas havi
Buleaj, c vorto, ĉu ne?

1021
00:51:52,590 --> 00:51:54,920
Do la nodo estas Bulea
kiel vera aŭ falsa,

1022
00:51:54,920 --> 00:51:58,490
Unue ĉe la kapo de
ke tabelo estas la jena vorto?

1023
00:51:58,490 --> 00:52:03,620
Due, vi volas havi punteros
al kiom la resto de ili estas.

1024
00:52:03,620 --> 00:52:07,470
Iom komplika, iom abstrakta, sed
Mi klarigos kion tio ĉiuj rimedoj.

1025
00:52:07,470 --> 00:52:13,800
>> Do jen, supre, se vi
havas tabelo deklaris jam,

1026
00:52:13,800 --> 00:52:17,040
nodo kie vi havas Bulea
valoro stokita en la fronto

1027
00:52:17,040 --> 00:52:19,490
kiu diras vin estas tiu vorto?

1028
00:52:19,490 --> 00:52:20,520
Ĉu tio ne estas vorto?

1029
00:52:20,520 --> 00:52:23,240
Kaj tiam vi havas la
resto de via tabelo ke

1030
00:52:23,240 --> 00:52:26,040
fakte stokas ĉiujn
ebloj de kio povis esti.

1031
00:52:26,040 --> 00:52:28,660
Do, ekzemple, kiel
ĉe la supro vi havas

1032
00:52:28,660 --> 00:52:32,140
la unua kiu diras veraj aŭ
falsa, jes aŭ ne, ĉi tiu estas vorto.

1033
00:52:32,140 --> 00:52:38,130
>> Kaj tiam vi havas 0 tra 26 de
la literoj, ke vi povas stoki.

1034
00:52:38,130 --> 00:52:42,790
Se mi volis serĉi tie
por vesperto, mi iras al la supro

1035
00:52:42,790 --> 00:52:49,200
kaj mi serĉos B. mi trovas B en mia
tabelo, do mi scias, OK, estas B vorton?

1036
00:52:49,200 --> 00:52:53,010
B ne estas vorto, do tiel
Mi devas teni serĉanta.

1037
00:52:53,010 --> 00:52:56,410
Mi iras de B, kaj mi rigardas al la
montrilo ke B notas al

1038
00:52:56,410 --> 00:53:00,900
kaj mi vidas alian aron de informoj,
la sama strukturo kiun ni havis antaŭe.

1039
00:53:00,900 --> 00:53:05,240
>> Kaj here-- ho, la sekva
letero en [inaudible] estas A.

1040
00:53:05,240 --> 00:53:07,210
Do ni rigardu en tiu tabelo.

1041
00:53:07,210 --> 00:53:10,860
Ni trovas la oka valoro,
kaj tiam ni rigardu vidi, ho,

1042
00:53:10,860 --> 00:53:12,840
hey, estas ke vorto, estas B-Al unu vorton?

1043
00:53:12,840 --> 00:53:13,807
Ĝi ne estas vorto.

1044
00:53:13,807 --> 00:53:14,890
Ni devas teni rigardante.

1045
00:53:14,890 --> 00:53:17,850
>> Kaj tiel do oni konsideras kie
la montrilon de A punktoj,

1046
00:53:17,850 --> 00:53:21,130
kaj ĝi notas al alia maniero en
kion ni havas pli valoro stokita.

1047
00:53:21,130 --> 00:53:24,150
Kaj fine, ni atingos
B-Al-T, kiu estas vorto.

1048
00:53:24,150 --> 00:53:25,970
Do la sekvanta tempo
vi aspektas, vi tuj

1049
00:53:25,970 --> 00:53:30,850
havi tiun ĉeko de, jes,
ĉi Bulea funkcio estas vera.

1050
00:53:30,850 --> 00:53:35,450
Kaj tiel en la senco ni estas speco
havi arbon kun tabeloj.

1051
00:53:35,450 --> 00:53:39,890
>> Tial do vi povas ia serĉu suben.

1052
00:53:39,890 --> 00:53:43,650
Anstataŭ hashing funkcio kaj
asignanta valorojn per ligillisto,

1053
00:53:43,650 --> 00:53:49,190
Vi povas simple apliki
trie ke sercxojn downwords.

1054
00:53:49,190 --> 00:53:50,850
Vere, vere komplikitaj aĵoj.

1055
00:53:50,850 --> 00:53:54,060
Ne facilas pensi ĉar mi ŝatas
kracxi tiel multaj datumstrukturoj el

1056
00:53:54,060 --> 00:53:58,710
ĉe vi, sed faras ĉiu tipon de
kompreni kiel la logiko de tio funkcias?

1057
00:53:58,710 --> 00:54:01,920
>> Bone, mojose.

1058
00:54:01,920 --> 00:54:05,600
Do B-Al-T, kaj tiam
vi tuj serĉu.

1059
00:54:05,600 --> 00:54:07,940
La venontan fojon vi tuj
vidi, ho, hej, ĝi estas vera,

1060
00:54:07,940 --> 00:54:09,273
tiele mi konas ĉi devas esti vorto.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Sama afero por zoo.

1063
00:54:13,770 --> 00:54:17,960
Do jen la afero nun, se ni
volis serĉi bestoĝardeno, nun,

1064
00:54:17,960 --> 00:54:20,780
aktuale bestoĝardeno ne estas
vorto en nia vortaro

1065
00:54:20,780 --> 00:54:25,300
ĉar, kiel vi infanoj povas vidi, la
unua loko kiun ni havas Bulea

1066
00:54:25,300 --> 00:54:28,590
reveni vera estas fine de zoom.

1067
00:54:28,590 --> 00:54:30,430
Ni havas Z-ho-ho-M.

1068
00:54:30,430 --> 00:54:33,900
>> Kaj do ĉi tie, ni ne vere havas
la vorto, zoo, en nia vortaro

1069
00:54:33,900 --> 00:54:36,070
ĉar tiu markobutono ne estas markita.

1070
00:54:36,070 --> 00:54:39,540
Do la komputilo ne
scias ke bestoĝardeno estas vorto

1071
00:54:39,540 --> 00:54:42,430
ĉar la vojo kiun ni
stokita, nur zoom tie

1072
00:54:42,430 --> 00:54:44,920
efektive havas Bulea valoro
ke tio estis turnita vera.

1073
00:54:44,920 --> 00:54:49,380
Do se ni volas enmeti la
vorto: zoo, en nia vortaro,

1074
00:54:49,380 --> 00:54:51,770
Kiel ni iras pri faranta tion?

1075
00:54:51,770 --> 00:54:55,960
Kion ni devas fari por certigi nian
komputilo scias ke Z-ho-ho estas vorto

1076
00:54:55,960 --> 00:54:58,130
kaj ne la unua vorto estas Z-ho-ho-M?

1077
00:54:58,130 --> 00:54:59,360
>> Spektantaro: [inaudible]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Ĝuste, ni
volas certigi ke ĉi

1079
00:55:01,450 --> 00:55:07,890
tie, ke Bulea valoro estas
kontrolis ekstere ke ĝi estas vera.

1080
00:55:07,890 --> 00:55:13,297
Z-ho-ho, tiam ni tuj kontroli tion,
tial ni scias precize, hej, bestoĝardeno estas vorto.

1081
00:55:13,297 --> 00:55:15,380
Mi tuj rakontos la
komputilo ke ĝi estas vorto tiom

1082
00:55:15,380 --> 00:55:18,000
ke kiam la komputilo ĉekojn,
ĝi scias ke bestoĝardeno estas vorto.

1083
00:55:18,000 --> 00:55:21,269
>> Ĉar memori ĉiuj ĉi tiuj datumoj
strukturoj, ĝi estas tre facila por ni

1084
00:55:21,269 --> 00:55:22,310
diri, ho, vesperto estas vorto.

1085
00:55:22,310 --> 00:55:22,851
Zooparko estas vorto.

1086
00:55:22,851 --> 00:55:23,611
Zoom estas vorto.

1087
00:55:23,611 --> 00:55:25,860
Sed kiam vi konstruado ĝi,
la komputilo havas nenian ideon.

1088
00:55:25,860 --> 00:55:28,619
>> Do vi devas diri ĝin precize
en kio punkto estas tiu vorto?

1089
00:55:28,619 --> 00:55:29,910
Ĉe kiu punkto ĝi estas ne unu vorton?

1090
00:55:29,910 --> 00:55:31,784
Alian punkton mi
bezonas serĉi aferojn,

1091
00:55:31,784 --> 00:55:34,000
kaj en kio punkto mi devas nun iri?

1092
00:55:34,000 --> 00:55:37,010
Ĉiu klara de tiu?

1093
00:55:37,010 --> 00:55:39,540
Malvarmeta.

1094
00:55:39,540 --> 00:55:42,530
>> Kaj tiel do venas la
problemo de kiel estus ni

1095
00:55:42,530 --> 00:55:45,560
iri pri enmeto ion
ke fakte ne ekzistas?

1096
00:55:45,560 --> 00:55:49,090
Do ni nur diros ni volas enmeti
la vorto, bano, en nian trie.

1097
00:55:49,090 --> 00:55:53,589
Kiel vi uloj povas vidi kiel nuntempe
ĉiuj ni havas nun estas B-Al-T,

1098
00:55:53,589 --> 00:55:55,630
kaj tiu nova datumstrukturo
tie havis pint ke

1099
00:55:55,630 --> 00:55:59,740
montris nula ĉar ni supozas
ke, ho, ekzistas neniu vortoj post B-Al-T,

1100
00:55:59,740 --> 00:56:02,530
kial ni devas teni
havanta aferojn post ke T.

1101
00:56:02,530 --> 00:56:06,581
>> Sed la problemo ekestas se ni faras vin
deziras havi vorton kiu venas post

1102
00:56:06,581 --> 00:56:07,080
la T.

1103
00:56:07,080 --> 00:56:09,500
Se vi havas banon, vi estas
tuj volas H pravas.

1104
00:56:09,500 --> 00:56:13,290
Kaj tiel la vojon ni tuj faros kiu estas
ni tuj krei apartan nodon.

1105
00:56:13,290 --> 00:56:16,840
Ni ne allot ajn kvanto
de memoro por tiu nova tabelo,

1106
00:56:16,840 --> 00:56:20,720
kaj ni tuj reassign punteros.

1107
00:56:20,720 --> 00:56:22,947
>> Ni tuj asigni la
H, Unue, tiu nula,

1108
00:56:22,947 --> 00:56:24,030
ni tuj forigi.

1109
00:56:24,030 --> 00:56:26,590
Ni tuj devas
la H punkto suben.

1110
00:56:26,590 --> 00:56:30,600
Se ni vidas H, ni volas ĝin
iri al ie alia.

1111
00:56:30,600 --> 00:56:33,910
>> En tie, ni povas tiam kontroli ekstere jes.

1112
00:56:33,910 --> 00:56:38,170
Se ni batis H post la T, ho,
tiam ni scias ke tiu estas vorto.

1113
00:56:38,170 --> 00:56:41,110
La Buleaj tuj reveni vera.

1114
00:56:41,110 --> 00:56:42,950
Ĉiu klara de kiel tio okazis?

1115
00:56:42,950 --> 00:56:45,110
BONE.

1116
00:56:45,110 --> 00:56:47,214
>> Do esence, ĉiuj
tiuj datumstrukturoj

1117
00:56:47,214 --> 00:56:50,130
ke ni trapasis hodiaŭ, mi havas
trairinte ilin vere, vere rapide

1118
00:56:50,130 --> 00:56:52,192
kaj ne en multa
detalo, kaj tio estas okej.

1119
00:56:52,192 --> 00:56:53,900
Unufoje vi komencas rompado
kun ĝi, Vi estos

1120
00:56:53,900 --> 00:56:55,733
konservanta trako de kie
ĉiuj punteros estas,

1121
00:56:55,733 --> 00:56:58,060
kio okazas en via
datumstrukturoj, kaj tiel plu.

1122
00:56:58,060 --> 00:56:59,810
Ili estos tre utilaj,
kaj ĝi estas ĝis vi

1123
00:56:59,810 --> 00:57:03,890
guys tute elkompreni kiel
vi volas apliki aferojn.

1124
00:57:03,890 --> 00:57:07,650
>> Kaj tiel pset4, de 5-- ho, tio estas erara.

1125
00:57:07,650 --> 00:57:10,140
Pset5 estas fuŝo.

1126
00:57:10,140 --> 00:57:13,710
Kiel mi diris antaŭe, vi tuj, fojo
denove, elŝuti fontkodon de ni.

1127
00:57:13,710 --> 00:57:16,210
Tie tuj estos tri ĉefaj
aferoj vi estos elŝuto.

1128
00:57:16,210 --> 00:57:18,470
Vi elŝuti vortarojn,
KERS, kaj tekstoj.

1129
00:57:18,470 --> 00:57:21,660
>> Ĉiuj tiuj aferoj estas estas
ĉu vortarojn de vortoj

1130
00:57:21,660 --> 00:57:25,190
ke ni volas ke vi kontrolu
aŭ testo de informo

1131
00:57:25,190 --> 00:57:26,930
ke ni deziras vin literumilo.

1132
00:57:26,930 --> 00:57:29,670
Kaj tial la vortaroj
Ni donas vin iras

1133
00:57:29,670 --> 00:57:34,870
doni vin precizaj vortoj, ke ni volas
vi stoki iel en maniero kiu estas

1134
00:57:34,870 --> 00:57:36,530
pli efika ol tabelo.

1135
00:57:36,530 --> 00:57:38,470
Kaj tiam la tekstoj estas
tuj estos kio ni estas

1136
00:57:38,470 --> 00:57:43,900
demandante vin literumi kontroli por certiĝi
ĉiuj vortoj estas veraj vortoj.

1137
00:57:43,900 --> 00:57:47,970
>> Kaj tiel la tri blokoj de
programoj kiuj ni donos al vi

1138
00:57:47,970 --> 00:57:51,130
nomas dictionary.c,
dictionary.h kaj speller.c.

1139
00:57:51,130 --> 00:57:56,500
Kaj tial ĉiuj dictionary.c faras estas
kion vi demandis apliki.

1140
00:57:56,500 --> 00:57:57,880
Ĝi ŝarĝas vortoj.

1141
00:57:57,880 --> 00:58:02,000
Ĝi literumi ĉekojn ilin, kaj ĝi certigas
ke ĉio estas enigita konvene.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h estas nur biblioteko dosiero
kiu deklaras ĉiuj tiuj funkcioj.

1143
00:58:05,180 --> 00:58:07,650
Kaj speller.c, ni tuj donas vin.

1144
00:58:07,650 --> 00:58:09,290
Vi ne bezonas modifi iuj ĝi.

1145
00:58:09,290 --> 00:58:14,290
Ĉiuj speller.c faras estas preni tiun,
ŝarĝoj, kontrolas la rapidon de ĝi,

1146
00:58:14,290 --> 00:58:19,190
testas la etalono de kiel kiom
rapide vi povos fari aferojn.

1147
00:58:19,190 --> 00:58:20,410
>> Estas literumanto.

1148
00:58:20,410 --> 00:58:23,920
Nur ne salaton kun ĝi, Sed faro
certe vin komprenas kion ĝi faras.

1149
00:58:23,920 --> 00:58:28,090
Ni uzi funkcio nomita getrusage ke
testas la rendimenton de via sorĉas

1150
00:58:28,090 --> 00:58:28,590
kontrolilo.

1151
00:58:28,590 --> 00:58:32,200
Ĉiuj faras estas esence testi la
tempo de ĉio en via vortaro,

1152
00:58:32,200 --> 00:58:33,680
Tiel faro certe vi komprenas.

1153
00:58:33,680 --> 00:58:36,660
Penu ne salaton kun ĝi aŭ
alia aĵoj ne kuras konvene.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Kaj la plejparton de tiu defio estas por
you guys vere modifi dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Ni tuj donos al vi
140.000 vortojn en vortaro.

1157
00:58:48,526 --> 00:58:50,900
Ni tuj donos al vi tekston
dosieron kiu havas tiujn vortojn,

1158
00:58:50,900 --> 00:58:54,840
kaj ni volas ke vi povos organizi
ilin en hash tablo aŭ trie

1159
00:58:54,840 --> 00:58:58,140
ĉar kiam ni petas vin literumi
check-- imagi se vi estas sorĉo

1160
00:58:58,140 --> 00:59:00,690
kontrolanta kiel Homero Odiseado.

1161
00:59:00,690 --> 00:59:03,010
Estas kiel tiu grandega, grandega provo.

1162
00:59:03,010 --> 00:59:05,190
>> Imagu se ĉiu unuopa
vorto vi devis serĉi

1163
00:59:05,190 --> 00:59:08,100
tra tabelo de 140.000 valoroj.

1164
00:59:08,100 --> 00:59:10,350
Kiu portus ĉiam
por via maŝino kuri.

1165
00:59:10,350 --> 00:59:14,490
Tial ni volas organizi niajn
datumojn en pli efika datumstrukturoj

1166
00:59:14,490 --> 00:59:17,270
kiel hash tablo aŭ trie.

1167
00:59:17,270 --> 00:59:20,700
Kaj tiam vi uloj povas ia
de kiam vi serĉu aliro

1168
00:59:20,700 --> 00:59:22,570
aferojn pli facile kaj pli rapide.

1169
00:59:22,570 --> 00:59:24,934
>> Kaj do atentu solvi kolizioj.

1170
00:59:24,934 --> 00:59:27,350
Vi tuj ricevos multajn
vortoj de kiuj komenciĝas je A.

1171
00:59:27,350 --> 00:59:29,957
Vi tuj ricevos multajn vortojn
ke komenco kun B. Ĝis vi

1172
00:59:29,957 --> 00:59:31,290
uloj kiel vi volas solvi ĝin.

1173
00:59:31,290 --> 00:59:34,144
Eble ekzistas pli
efika hash funkcio

1174
00:59:34,144 --> 00:59:36,810
ol nur la unua litero de
io, kaj tiel ke estas ĝis vi

1175
00:59:36,810 --> 00:59:38,190
uloj al speco de fari kion vi volas.

1176
00:59:38,190 --> 00:59:40,148
>> Eble vi deziras aldoni
ĉiuj literoj kune.

1177
00:59:40,148 --> 00:59:43,410
Eble vi volas ŝatas fari strangajn aferojn
ĝi rakontas la nombro de literoj,

1178
00:59:43,410 --> 00:59:43,970
ajn.

1179
00:59:43,970 --> 00:59:45,386
Ĝis vi uloj kiel vi volas fari.

1180
00:59:45,386 --> 00:59:49,262
Se vi volas fari hash tablo, se vi
volas provi trie, tute dependas de vi.

1181
00:59:49,262 --> 00:59:52,470
Mi avertas vin antaŭ tempo ke la
trie estas tipe iom pli malfacila

1182
00:59:52,470 --> 00:59:54,520
nur ĉar ekzistas multe
pli punteros spuri.

1183
00:59:54,520 --> 00:59:55,645
Sed tute dependas de vi uloj.

1184
00:59:55,645 --> 00:59:58,742
Estas multe pli efika
en plej kazoj.

1185
00:59:58,742 --> 01:00:01,450
Vi volas vere esti kapabla teni
trako de ĉiuj viaj indikoj.

1186
01:00:01,450 --> 01:00:03,850
Kiel fari la saman aferon
ke mi estis faranta tie.

1187
01:00:03,850 --> 01:00:06,871
Kiam vi provas enmeti
valorojn en hash tablo aŭ forviŝi,

1188
01:00:06,871 --> 01:00:08,620
certiĝu ke vi estas
vere konservanta trako

1189
01:00:08,620 --> 01:00:11,860
de kie ĉiu estas ĉar
ĝi estas vere facila por se mi

1190
01:00:11,860 --> 01:00:14,727
provas enmeti kiel la vorto, andy.

1191
01:00:14,727 --> 01:00:16,810
Ni nur diras, ke estas
reala vorto, la vorto, andy,

1192
01:00:16,810 --> 01:00:19,640
en giganta listo de A vortojn.

1193
01:00:19,640 --> 01:00:22,450
>> Se mi nur hazarde reassign
montrilo malĝusta, oops,

1194
01:00:22,450 --> 01:00:24,940
tie iras la tuteco de
la resto de mia ligillisto.

1195
01:00:24,940 --> 01:00:26,897
Nun la nura vorto mi
havas estas andy, kaj nun

1196
01:00:26,897 --> 01:00:29,230
ĉiuj la aliaj vortoj en la
vortaro perdiĝis.

1197
01:00:29,230 --> 01:00:31,370
Kaj do vi deziras fari certe vin
sekvigi ĉiuj viaj indikoj

1198
01:00:31,370 --> 01:00:33,661
aŭ alie vi ricevos
grandegaj problemoj en via kodo.

1199
01:00:33,661 --> 01:00:35,840
Desegni aferojn zorge paŝon post paŝo.

1200
01:00:35,840 --> 01:00:37,870
Ĝi faras ĝin tre pli facila elpensi.

1201
01:00:37,870 --> 01:00:40,910
>> Kaj fine, vi volas povi
testi vian rendimenton de via programo

1202
01:00:40,910 --> 01:00:41,618
sur la granda tabulo.

1203
01:00:41,618 --> 01:00:43,710
Se vi infanoj prenas
rigardas CS50 nun,

1204
01:00:43,710 --> 01:00:45,210
ni havos kion nomas la granda tabulo.

1205
01:00:45,210 --> 01:00:50,200
Estas la partituro folio de la plej rapida
literumi kontrolanta fojojn tra ĉiuj de CS50

1206
01:00:50,200 --> 01:00:55,720
Ĝuste nun, mi kredas ke la supro kiel 10
tempoj mi pensas ok de ili estas bastono.

1207
01:00:55,720 --> 01:00:57,960
Ni vere volas vin infanoj bati nin.

1208
01:00:57,960 --> 01:01:00,870
>> Ni ĉiuj provis implementar
la plej rapidan kodon kiel ebla.

1209
01:01:00,870 --> 01:01:04,880
Ni volas vin infanoj provi defii
ni kaj efektivigi pli rapide ol ni ĉiuj

1210
01:01:04,880 --> 01:01:05,550
povas.

1211
01:01:05,550 --> 01:01:07,970
Kaj tiel tio estas vere
la unua tempo ke ni estas

1212
01:01:07,970 --> 01:01:12,680
demandante vin infanoj fari pset ke
vi povas vere fari en ajn metodo

1213
01:01:12,680 --> 01:01:13,760
vi volas.

1214
01:01:13,760 --> 01:01:17,730
>> Mi ĉiam diras, tiu estas pli parenca
al reala-vivo solvo, ĉu ne?

1215
01:01:17,730 --> 01:01:19,550
Mi diras, hey, mi bezonas vin por fari tion.

1216
01:01:19,550 --> 01:01:21,380
Konstruu programo kiu faras tion por mi.

1217
01:01:21,380 --> 01:01:22,630
Ĉu ĝi tamen vi volas.

1218
01:01:22,630 --> 01:01:24,271
Mi nur scias ke mi volas fasti.

1219
01:01:24,271 --> 01:01:25,770
Tio estas via defio por tiu semajno.

1220
01:01:25,770 --> 01:01:27,531
Vi uloj, ni tuj
doni al vi taskon.

1221
01:01:27,531 --> 01:01:29,030
Ni tuj donos al vi defion.

1222
01:01:29,030 --> 01:01:31,559
Kaj tiam ĝi estas ĝis vi infanoj
tute simple elkalkuli

1223
01:01:31,559 --> 01:01:34,100
kio estas la plej rapida kaj plej
efika maniero por efektivigi tion.

1224
01:01:34,100 --> 01:01:34,600
Yeah?

1225
01:01:34,600 --> 01:01:37,476
>> Spektantaro: Ĉu ni permesis al se
volis esplori pli rapida manieroj

1226
01:01:37,476 --> 01:01:40,821
fari hash tabloj linio, ni povas fari
ke kaj cite aliulaj kodo?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Jes, tute bone.

1228
01:01:42,070 --> 01:01:44,320
Do se vi infanoj legi la
spec, ekzistas linio

1229
01:01:44,320 --> 01:01:48,310
en la spec kiu diras vin infanoj
estas tute libera por priesplori hash

1230
01:01:48,310 --> 01:01:51,070
funkcioj sur kio estas iuj
de la rapida kradaj funkcioj

1231
01:01:51,070 --> 01:01:54,720
kuri aĵojn tra kiel
longe kiel vi citas ke kodo.

1232
01:01:54,720 --> 01:01:57,220
Do iuj personoj havas jam
eltrovis rapidaj manieroj

1233
01:01:57,220 --> 01:02:00,250
fari sorĉas kontroliloj, de rapida
manieroj de stoki informon.

1234
01:02:00,250 --> 01:02:02,750
Tute supren al vi knaboj, se vi
volas nur prenu ke, dekstra?

1235
01:02:02,750 --> 01:02:04,045
Certiĝu vi citante.

1236
01:02:04,045 --> 01:02:06,170
La defio ĉi tie vere
ke ni provas testi

1237
01:02:06,170 --> 01:02:09,750
estas certigi ke vi scias
vian vojon ĉirkaŭ punteros.

1238
01:02:09,750 --> 01:02:12,700
Koncerne vin efektivigado
la fakta hash funkcio

1239
01:02:12,700 --> 01:02:15,070
kaj venanta supre kun kiel
la math fari tion,

1240
01:02:15,070 --> 01:02:17,570
vi uloj povas priesplori ajn
metodoj rete vi uloj volas.

1241
01:02:17,570 --> 01:02:17,996
Yeah?

1242
01:02:17,996 --> 01:02:19,700
>> Spektantaro: Ĉu ni povas citi nur
uzante la [inaudible]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Yeah.

1244
01:02:20,120 --> 01:02:22,328
Vi povas simple, en via komento,
vi povas citi kiel, oh,

1245
01:02:22,328 --> 01:02:26,127
prenita de Yada, Yada,
Yada, hash funkcio.

1246
01:02:26,127 --> 01:02:27,210
Iu havas demandojn?

1247
01:02:27,210 --> 01:02:29,694
Ni efektive breezed
tra sekcio hodiaŭ.

1248
01:02:29,694 --> 01:02:31,610
Mi estos supren tie al
respondi demandojn ankaŭ.

1249
01:02:31,610 --> 01:02:36,570
>> Ankaŭ, kiel mi diris, oficejo
horoj ĉinokte kaj morgaŭ.

1250
01:02:36,570 --> 01:02:40,307
La specifo ĉi semajno estas reale
super facila kaj super mallonga legi.

1251
01:02:40,307 --> 01:02:43,140
Mi sugestus prenante rigardu, ĝuste
legi tra la tuteco de ĝi.

1252
01:02:43,140 --> 01:02:45,730
>> Kaj Zamyla reale promenas vin
tra ĉiu de la funkcioj

1253
01:02:45,730 --> 01:02:49,796
Vi devas efektivigi, kaj tiel ĝi estas
tre tre klara kiel fari ĉion.

1254
01:02:49,796 --> 01:02:51,920
Ĝuste certigi ke vi estas
konservanta trako de punteros.

1255
01:02:51,920 --> 01:02:53,650
Tio estas tre defia pset.

1256
01:02:53,650 --> 01:02:56,744
>> Ĝi ne estas defianta ĉar kiel,
ho, la konceptoj estas tiel multe pli

1257
01:02:56,744 --> 01:02:59,160
malfacila, aŭ vi devas lerni
tiel nova sintakso la vojon

1258
01:02:59,160 --> 01:03:00,650
ke vi faris por la lasta pset.

1259
01:03:00,650 --> 01:03:03,320
Ĉi pset estas malfacila ĉar
Estas tiom multaj indikoj,

1260
01:03:03,320 --> 01:03:06,980
kaj tiam ĝi estas tre, tre facile tuj
vi havas cimon en via kodo ne povos

1261
01:03:06,980 --> 01:03:08,315
trovi kie tiu cimo estas.

1262
01:03:08,315 --> 01:03:13,200
>> Kaj tiel kompleta kaj absoluta fido en vi
uloj povi bati nia [inaudible]

1263
01:03:13,200 --> 01:03:13,700
literumojn.

1264
01:03:13,700 --> 01:03:16,640
Mi efektive ne havas skribita la mia
ankoraŭ, sed mi volis skribi mian.

1265
01:03:16,640 --> 01:03:19,070
Do dum vi skribas
via, mi skribos mia.

1266
01:03:19,070 --> 01:03:21,070
Mi tuj provos fari
mia rapida ol la via.

1267
01:03:21,070 --> 01:03:23,940
Ni vidos kiu havas la plej rapida unu.

1268
01:03:23,940 --> 01:03:27,340
>> Kaj jes, mi vidos ĉiujn
vi uloj tie marde.

1269
01:03:27,340 --> 01:03:29,510
Mi kuras speco kiel pset ateliero.

1270
01:03:29,510 --> 01:03:32,640
Ĉiuj la sekcioj ĉi
semajno estas pset metiejoj,

1271
01:03:32,640 --> 01:03:36,690
tiel vi infanoj havas multajn ŝancojn
por helpo, oficejo horoj kiel ĉiam,

1272
01:03:36,690 --> 01:03:41,330
kaj mi vere atendas senpacience
leganta ĉiujn de viaj infanoj 'kodo.

1273
01:03:41,330 --> 01:03:44,160
Mi havas kvizojn ĉi tien se vi
uloj volas veni akiri tiujn.

1274
01:03:44,160 --> 01:03:45,880
Tio estas ĉio.

1275
01:03:45,880 --> 01:03:48,180