1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Pafwa, lè bati yon
pwogram nan, ou ta ka vle itilize yon

3
00:00:10,890 --> 00:00:13,190
estrikti done li te ye kòm yon diksyonè.

4
00:00:13,190 --> 00:00:17,960
Yon kat diksyonè kle yo, ki se
anjeneral strings, nan valè, antye,

5
00:00:17,960 --> 00:00:21,900
charaktèr, yon konsèy nan kèk objè,
tou sa nou vle.

6
00:00:21,900 --> 00:00:26,510
Li nan jis tankou diksyonè òdinè
kat jeyografik ke mo nan definisyon.

7
00:00:26,510 --> 00:00:29,440
>> Dictionaries bay nou ak nan
kapasite nan magazen enfòmasyon

8
00:00:29,440 --> 00:00:32,750
ki asosye avèk yon bagay
epi gade l 'pita.

9
00:00:32,750 --> 00:00:36,620
Se konsa, kouman nou aktyèlman aplike yon
diksyonè nan, di, C kòd ki nou kapab

10
00:00:36,620 --> 00:00:38,460
sèvi ak nan youn nan pwogram nou an?

11
00:00:38,460 --> 00:00:41,790
Oke, gen yon anpil nan fason ki
nou te ka aplike yon diksyonè.

12
00:00:41,790 --> 00:00:45,930
>> Pou youn, nou te ka sèvi ak yon etalaj ke nou
dynamique re-gwosè oswa nou te ka sèvi ak yon

13
00:00:45,930 --> 00:00:49,150
lis lye, tab hash
oswa yon pye bwa binè.

14
00:00:49,150 --> 00:00:52,250
Men, tou sa nou chwazi, nou ta dwe
dwe konsyan de efikasite yo ak

15
00:00:52,250 --> 00:00:54,300
pèfòmans nan aplikasyon an.

16
00:00:54,300 --> 00:00:57,930
Nou ta dwe reflechi sou algorithm a te itilize
insert epi gade anwo atik nan

17
00:00:57,930 --> 00:00:59,120
done nou an estrikti.

18
00:00:59,120 --> 00:01:03,060
>> Pou kounye a, se pou yo asime ke nou
vle sèvi ak strings kòm kle.

19
00:01:03,060 --> 00:01:07,290
Se pou nou pale sou yon sèl posiblite,
yon estrikti done yo te rele yon trye.

20
00:01:07,290 --> 00:01:11,210
Se konsa, isit la nan yon reprezantasyon vizyèl
nan yon trye.

21
00:01:11,210 --> 00:01:14,590
>> Kòm foto an sijere, yon trye
se yon pye bwa done estrikti ak

22
00:01:14,590 --> 00:01:16,050
nœuds lye ansanm.

23
00:01:16,050 --> 00:01:19,420
Nou wè ke gen nan byen klè yon rasin
ne ak kèk lyen yo pwolonje

24
00:01:19,420 --> 00:01:20,500
lòt ne.

25
00:01:20,500 --> 00:01:23,040
Men, sa ki chak ne konpoze de?

26
00:01:23,040 --> 00:01:26,700
Si nou asime ke nou ap estoke kle
ak sèlman karaktè alfabetik, ak

27
00:01:26,700 --> 00:01:30,150
nou pa pran swen sou lèt majiskil,
isit la nan yon definisyon yon ne ki

28
00:01:30,150 --> 00:01:31,100
ap sifi.

29
00:01:31,100 --> 00:01:34,130
>> Yon objè ki gen kalite a se konstri
ne gen de pati

30
00:01:34,130 --> 00:01:35,740
rele done ak timoun yo.

31
00:01:35,740 --> 00:01:39,200
Nou te kite pati nan done kòm yon kòmantè
yo dwe ranplase pa yon eleman

32
00:01:39,200 --> 00:01:43,190
deklarasyon lè konstri ne se
enkòpore nan yon pwogram C.

33
00:01:43,190 --> 00:01:47,040
Pati nan done nan yon ne ta kapab yon
Boolean valè nan endike si wi ou

34
00:01:47,040 --> 00:01:51,160
pa ne a reprezante fini an
nan yon kle diksyonè oswa li ta kapab yon

35
00:01:51,160 --> 00:01:54,240
fisèl reprezante definisyon an
nan yon mo an nan diksyonè a.

36
00:01:54,240 --> 00:01:58,870
>> Nou pral sèvi ak yon figi Smiley ki endike
lè done ki prezan nan yon ne.

37
00:01:58,870 --> 00:02:02,310
Gen 26 eleman nan nou an
timoun etalaj, youn endèks

38
00:02:02,310 --> 00:02:03,690
pou chak karaktè alfabetik.

39
00:02:03,690 --> 00:02:06,570
Nou pwal wè siyifikasyon an
nan sa a byento.

40
00:02:06,570 --> 00:02:10,759
>> Se pou nou jwenn yon gade pi pre nan ne la rasin
nan dyagram nou an, ki pa gen okenn done

41
00:02:10,759 --> 00:02:14,740
ki asosye avèk li, jan sa endike nan la
absans nan fè fas a Smiley nan la

42
00:02:14,740 --> 00:02:16,110
done pòsyon.

43
00:02:16,110 --> 00:02:19,910
Flèch yo pwolonje soti nan pati pyès sa yo nan
timoun yo etalaj reprezante ki pa ne

44
00:02:19,910 --> 00:02:21,640
endikasyon nan lòt ne.

45
00:02:21,640 --> 00:02:25,500
Pou egzanp, flèch la pwolonje soti nan
eleman nan dezyèm nan timoun

46
00:02:25,500 --> 00:02:28,400
reprezante lèt la B
nan yon kle diksyonè.

47
00:02:28,400 --> 00:02:31,920
Apre sa, nan dyagram nan pi gwo
nou mete lejann sou li ak yon B.

48
00:02:31,920 --> 00:02:35,810
>> Remake byen ke nan dyagram nan pi gwo, lè nou
trase yon konsèy nan yon lòt ne, li

49
00:02:35,810 --> 00:02:39,100
pa gen pwoblèm ki kote Arrowhead la
satisfè ke lòt ne.

50
00:02:39,100 --> 00:02:43,850
Diksyonè echantiyon trye nou an gen
de mo, se sa ak rale.

51
00:02:43,850 --> 00:02:47,040
Se pou nou mache nan yon egzanp sou
leve je l 'done pou yon kle.

52
00:02:47,040 --> 00:02:50,800
>> Sipoze nou te vle gade nan
ki koresponn valè pou benyen nan kle.

53
00:02:50,800 --> 00:02:53,610
Nou pral kòmanse gade nou moute
nan ne an rasin.

54
00:02:53,610 --> 00:02:57,870
Lè sa a, nou pral pran premye lèt nan nou an
kle, B, epi jwenn ki koresponn a

55
00:02:57,870 --> 00:03:00,020
tach nan timoun nou yo etalaj.

56
00:03:00,020 --> 00:03:04,490
Avi ki di ke gen yo se egzakteman 26 tach
nan etalaj la, yonn pou chak lèt

57
00:03:04,490 --> 00:03:05,330
alfabè an.

58
00:03:05,330 --> 00:03:08,800
Epitou, n ap gen tach yo reprezante nan
lèt nan alfabè a nan lòd.

59
00:03:08,800 --> 00:03:13,960
>> Nou pral gade nan dezyèm endèks la lè sa a,
endèks, yonn pou B. An jeneral, si nou

60
00:03:13,960 --> 00:03:17,990
gen kèk alfabetik karaktè C nou
te kapab detèmine plas ki koresponn lan

61
00:03:17,990 --> 00:03:21,520
nan timoun etalaj la lè l sèvi avèk
yon kalkil tankou sa a.

62
00:03:21,520 --> 00:03:25,140
Nou te kapab te itilize yon pi gwo timoun
etalaj si nou te vle ofri gade leve nan

63
00:03:25,140 --> 00:03:28,380
kle ak yon seri pi laj de karaktè yo,
tankou tout la

64
00:03:28,380 --> 00:03:29,880
N. ASCII mete.

65
00:03:29,880 --> 00:03:32,630
>> Nan ka sa a, konsèy la
nan timoun nou yo etalaj nan

66
00:03:32,630 --> 00:03:34,320
endèks se yon sèl pa nil.

67
00:03:34,320 --> 00:03:36,600
Se konsa, nou pral kontinye kap
moute benyen nan kle.

68
00:03:36,600 --> 00:03:40,130
Si nou tout tan tout tan rankontre yon konsèy nil
nan plas ki kòrèk nan timoun yo

69
00:03:40,130 --> 00:03:43,230
etalaj pandan ke nou travèse nœuds yo,
Lè sa a, nou pral oblije di ke nou

70
00:03:43,230 --> 00:03:45,630
pa t 'kapab jwenn anyen pou sa kle.

71
00:03:45,630 --> 00:03:49,370
>> Koulye a, nou ap pran lèt nan dezyèm nan
kle nou an, A a, epi kontinye sa yo

72
00:03:49,370 --> 00:03:52,400
endikasyon nan fason sa a jiskaske nou
rive nan fen an nan kle nou yo.

73
00:03:52,400 --> 00:03:56,530
Si nou rive nan fen an nan kle a san yo pa
, frape nenpòt ki fini mouri endikasyon nil,

74
00:03:56,530 --> 00:03:59,730
kòm se ka a isit la, Lè sa a, nou sèlman
gen yo tcheke yon sèl bagay plis ankò.

75
00:03:59,730 --> 00:04:02,110
Se kle sa a aktyèlman
an nan diksyonè a?

76
00:04:02,110 --> 00:04:07,660
>> Si se konsa, nou ta dwe jwenn yon valè, byen yon
Smiley icon figi nan dyagram nou an kote

77
00:04:07,660 --> 00:04:08,750
pawòl Bondye a fini.

78
00:04:08,750 --> 00:04:12,270
Si gen yon lòt bagay ki estoke ak
done yo, Lè sa a, nou ka retounen li.

79
00:04:12,270 --> 00:04:16,500
Pou egzanp, zou a kle se pa nan la
diksyonè, menm si nou te ka gen

80
00:04:16,500 --> 00:04:19,810
rive jwenn nan fen kle sa a san yo pa janm
frape nan yon konsèy nil, pandan ke nou

81
00:04:19,810 --> 00:04:21,089
repňte nan trye la.

82
00:04:21,089 --> 00:04:25,436
>> Si nou te eseye gade benyen nan kle yo, nan
dezyèm endèks etalaj dènye ne a,

83
00:04:25,436 --> 00:04:28,750
ki koresponn ak lèt ​​H la, ta
yo te ki te fèt yon konsèy nil.

84
00:04:28,750 --> 00:04:31,120
Se konsa, benyen se pa an nan diksyonè a.

85
00:04:31,120 --> 00:04:34,800
Se konsa, yon trye se inik nan ki kle yo
pa janm gen klèman ki estoke nan

86
00:04:34,800 --> 00:04:36,650
estrikti a done.

87
00:04:36,650 --> 00:04:38,810
Se konsa, ki jan nou insert yon bagay
nan yon trye?

88
00:04:38,810 --> 00:04:41,780
>> Se pou yo insert kle a
zou nan trye nou an.

89
00:04:41,780 --> 00:04:46,120
Sonje ke yon figi Smiley nan yon ne
te kapab koresponn nan kòd nan yon senp

90
00:04:46,120 --> 00:04:50,170
Boolean valè nan endike ke zou
se an nan diksyonè a oswa li te kapab

91
00:04:50,170 --> 00:04:53,710
koresponn ak plis enfòmasyon ke nou
vle asosye ak zou a kle yo,

92
00:04:53,710 --> 00:04:56,860
tankou definisyon an nan la
mo oswa yon lòt bagay.

93
00:04:56,860 --> 00:05:00,350
Nan kèk fason, pwosesis la insert
yon bagay nan yon trye se menm jan ak

94
00:05:00,350 --> 00:05:02,060
leve je yon bagay nan yon trye.

95
00:05:02,060 --> 00:05:05,720
>> Nou pral kòmanse ak ne nan rasin ankò,
endikasyon yo ki koresponn a

96
00:05:05,720 --> 00:05:07,990
lèt yo nan kle nou yo.

97
00:05:07,990 --> 00:05:11,310
Chans, nou te kapab swiv endikasyon
tout wout la jouk nou rive

98
00:05:11,310 --> 00:05:12,770
nan fen kle a.

99
00:05:12,770 --> 00:05:16,480
Depi zou se yon prefiks nan pawòl Bondye a
rale, ki se yon manm nan la

100
00:05:16,480 --> 00:05:19,440
diksyonè, nou pa bezwen
asiyen nenpòt nouvo ne.

101
00:05:19,440 --> 00:05:23,140
>> Nou ka modifye ne a endike ke
chemen an nan karaktè ki mennen ale nan

102
00:05:23,140 --> 00:05:25,360
li reprezante yon kle nan diksyonè nou an.

103
00:05:25,360 --> 00:05:28,630
Koulye a, se pou yo eseye yo mete nan
BATH kle nan trye la.

104
00:05:28,630 --> 00:05:32,260
Nou pral kòmanse nan ne la rasin
epi swiv endikasyon ankò.

105
00:05:32,260 --> 00:05:35,620
Men, nan sitiyasyon sa a, nou frape yon moun mouri
fini anvan nou ap kapab pou li ale nan nan

106
00:05:35,620 --> 00:05:36,940
nan fen kle a.

107
00:05:36,940 --> 00:05:40,980
Koulye a, nou pral bezwen asiyen kèk nouvo
nœuds ap bezwen asiyen yon nouvo

108
00:05:40,980 --> 00:05:43,660
ne pou chak rete
lèt de kle nou yo.

109
00:05:43,660 --> 00:05:46,740
>> Nan ka sa a, nou jis bezwen
asiyen yon nouvo ne.

110
00:05:46,740 --> 00:05:50,590
Lè sa a, nou pral bezwen fè endèks la H
referans nouvo ne sa a.

111
00:05:50,590 --> 00:05:54,070
Yon fwa ankò, nou ka modifye ne a
endike ke chemen an nan karaktè

112
00:05:54,070 --> 00:05:57,120
ki mennen ale nan li reprezante yon
kle nan diksyonè nou an.

113
00:05:57,120 --> 00:06:00,730
Se pou yo rezone sou asenptotik la
konpleksite nan pwosedi nou an pou sa yo

114
00:06:00,730 --> 00:06:02,110
de operasyon yo.

115
00:06:02,110 --> 00:06:06,420
>> Nou remake ke nan tou de ka nimewo a
nan etap algorithm nou an te pran te

116
00:06:06,420 --> 00:06:09,470
pwopòsyonèl ak kantite
lèt nan mo kle a.

117
00:06:09,470 --> 00:06:10,220
Sa a dwat.

118
00:06:10,220 --> 00:06:13,470
Lè ou vle gade yon mo nan yon
trye ou jis bezwen repňte nan

119
00:06:13,470 --> 00:06:17,100
lèt yo youn pa youn jiskaske ou swa
rive nan fen an gen mo a oubyen

120
00:06:17,100 --> 00:06:19,060
frape yon fen mouri nan trye la.

121
00:06:19,060 --> 00:06:22,470
>> Men, lè ou vle mete yon kle
valè pè nan yon trye lè l sèvi avèk la

122
00:06:22,470 --> 00:06:26,250
pwosedi nou diskite, ka ki pi mal
pral gen ou allocation yon nouvo ne

123
00:06:26,250 --> 00:06:27,550
pou chak lèt.

124
00:06:27,550 --> 00:06:31,290
Epitou, n ap sipoze alokasyon ki
se yon operasyon tan konstan.

125
00:06:31,290 --> 00:06:35,850
Se konsa, si nou sipoze ke longè a kle a se
limite pa yon konstan fiks, tou de

126
00:06:35,850 --> 00:06:39,400
ensèsyon epi gade anwo yo konstan
operasyon tan pou yon trye.

127
00:06:39,400 --> 00:06:42,930
>> Si nou pa fè sipozisyon sa a ki
se longè a kle limite pa yon fiks

128
00:06:42,930 --> 00:06:46,650
konstan, Lè sa a, ensèsyon ak gade leve,
nan ka ki pi mal la, yo lineyè nan la

129
00:06:46,650 --> 00:06:48,240
longè kle a.

130
00:06:48,240 --> 00:06:51,800
Remake ki kantite atik ki estoke
nan trye la pa afekte gade nan moute

131
00:06:51,800 --> 00:06:52,820
oswa tan ensèsyon.

132
00:06:52,820 --> 00:06:55,360
Li sèlman ntre nan pa la
longè kle a.

133
00:06:55,360 --> 00:06:59,300
>> Nan kontras, pandan l ajoute antre a, di,
yon tab hash gen tandans fè

134
00:06:59,300 --> 00:07:01,250
tan kap vini gade pi dousman.

135
00:07:01,250 --> 00:07:04,520
Pandan ke sa a pouvwa son fè apèl kont an premye,
nou ta dwe kenbe nan tèt ou ke yon

136
00:07:04,520 --> 00:07:08,740
favorab konpleksite asenptotik fè sa ki pa
vle di ke nan pratik done a

137
00:07:08,740 --> 00:07:11,410
estrikti a se nesesèman
pi lwen pase wont.

138
00:07:11,410 --> 00:07:15,860
Nou dwe konsidere ke tou nan magazen yon
mo nan yon trye nou bezwen, nan pi move a

139
00:07:15,860 --> 00:07:19,700
ka, yon nimewo nan nœuds pwopòsyonèl
longè a nan pawòl Bondye a tèt li.

140
00:07:19,700 --> 00:07:21,880
>> Ap eseye yo gen tandans sèvi ak yon anpil nan espas.

141
00:07:21,880 --> 00:07:25,620
Sa a nan kontra a yon tab hash,
kote nou sèlman bezwen yon nouvo ne

142
00:07:25,620 --> 00:07:27,940
magazen kèk valè kle pè.

143
00:07:27,940 --> 00:07:31,370
Koulye a, ankò nan teyori, gwo espas
konsomasyon pa sanble tankou yon gwo

144
00:07:31,370 --> 00:07:34,620
fè fas, espesyalman bay yo ke modèn
òdinatè gen jigokte ak

145
00:07:34,620 --> 00:07:36,180
jigokte nan memwa.

146
00:07:36,180 --> 00:07:39,200
Men, li sanble ke nou toujou gen
enkyete sou itilizasyon memwa ak

147
00:07:39,200 --> 00:07:42,540
òganizasyon pou dedomajman pou la
pèfòmans, depi òdinatè modèn

148
00:07:42,540 --> 00:07:46,960
yo gen mekanis nan plas anba a
kapo pi vit aksè memwa.

149
00:07:46,960 --> 00:07:51,180
>> Men, mekanis sa yo travay pi byen lè
aksèd memwa yo te fè nan kontra enfòmèl ant

150
00:07:51,180 --> 00:07:52,810
rejyon oswa zòn nan.

151
00:07:52,810 --> 00:07:55,910
Apre sa, nœuds yo nan yon trye te kapab abite
nenpòt kote nan ki miray.

152
00:07:55,910 --> 00:07:58,390
Men, sa yo, se komès-konpwomi
ke nou dwe konsidere.

153
00:07:58,390 --> 00:08:01,440
>> Sonje ke, lè w ap chwazi yon done
estrikti pou yon travay sèten, nou

154
00:08:01,440 --> 00:08:04,420
ta dwe reflechi sou ki kalite
operasyon estrikti nan done bezwen

155
00:08:04,420 --> 00:08:07,140
sipò ak ki kantite pèfòmans nan
nan chak nan sa yo

156
00:08:07,140 --> 00:08:09,080
operasyon zafè yo ban nou.

157
00:08:09,080 --> 00:08:11,300
Operasyon sa yo ka menm
pwolonje pi lwen pase jis

158
00:08:11,300 --> 00:08:13,430
debaz gade leve, li ensèsyon.

159
00:08:13,430 --> 00:08:17,010
Sipoze nou te vle aplike yon kalite
nan oto-ranpli fonctionnalités, anpil

160
00:08:17,010 --> 00:08:18,890
tankou Google motè rechèch fè.

161
00:08:18,890 --> 00:08:22,210
Ki se, retounen tout kle yo ak
potansyèlman valè ki

162
00:08:22,210 --> 00:08:24,130
gen yon prefiks bay yo.

163
00:08:24,130 --> 00:08:27,050
>> Yon trye se inikman itil
pou operasyon sa a.

164
00:08:27,050 --> 00:08:29,890
Li nan dwat yo repňte nan
trye a pou chak karaktè nan

165
00:08:29,890 --> 00:08:30,950
prefiks la.

166
00:08:30,950 --> 00:08:33,559
Jis tankou yon gade operasyon an,
nou te ka swiv endikasyon

167
00:08:33,559 --> 00:08:35,400
N. pa karaktè.

168
00:08:35,400 --> 00:08:38,659
Lè sa a, lè nou rive nan fen an
prefiks, nou te ka repňte nan la

169
00:08:38,659 --> 00:08:42,049
rete pòsyon nan estrikti a done
depi nenpòt nan kle yo pi lwen pase

170
00:08:42,049 --> 00:08:43,980
pwen sa a gen prefiks la.

171
00:08:43,980 --> 00:08:47,670
>> Li la tou fasil jwenn lis sa a
nan alfabetik lòd depi nan

172
00:08:47,670 --> 00:08:50,970
eleman nan etalaj la timoun
yo te bay lòd avèk lèt ​​alfabè.

173
00:08:50,970 --> 00:08:54,420
Se konsa, èspere ke ou pral konsidere
bay ap eseye yon eseye.

174
00:08:54,420 --> 00:08:56,085
Mwen se Kevin Schmid, e sa se CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, sa a se nan konmansman an
nan bès la.

177
00:09:00,790 --> 00:09:01,350
Mwen regrèt.

178
00:09:01,350 --> 00:09:01,870
M regrèt.

179
00:09:01,870 --> 00:09:02,480
M regrèt.

180
00:09:02,480 --> 00:09:03,130
M regrèt.

181
00:09:03,130 --> 00:09:03,950
>> Grèv kat.

182
00:09:03,950 --> 00:09:04,360
Mwen se deyò.

183
00:09:04,360 --> 00:09:05,280
M regrèt.

184
00:09:05,280 --> 00:09:06,500
M regrèt.

185
00:09:06,500 --> 00:09:07,490
M regrèt.

186
00:09:07,490 --> 00:09:12,352
Padon pou fè moun ki te
te modifye sa a ale fou.

187
00:09:12,352 --> 00:09:13,280
>> M regrèt.

188
00:09:13,280 --> 00:09:13,880
M regrèt.

189
00:09:13,880 --> 00:09:15,080
M regrèt.

190
00:09:15,080 --> 00:09:15,680
M regrèt.

191
00:09:15,680 --> 00:09:16,280
>> Oratè 1: Bon fè.

192
00:09:16,280 --> 00:09:17,530
Sa ki te vrèman byen fè.

193
00:09:17,530 --> 00:09:18,430