1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Do en CS50, ni kovris
multaj diversaj datumstrukturoj,

3
00:00:08,300 --> 00:00:09,180
dekstra?

4
00:00:09,180 --> 00:00:11,420
Ni vidis arrays, kaj ligitaj
listoj, kaj hash tabloj,

5
00:00:11,420 --> 00:00:15,210
kaj klopodoj, stakoj kaj atendovicoj.

6
00:00:15,210 --> 00:00:17,579
Ni ankaŭ lerni iom
pri arboj kaj amasoj,

7
00:00:17,579 --> 00:00:20,120
sed vere ili ĉiuj ĵus fini
estante variadoj sur temo.

8
00:00:20,120 --> 00:00:22,840
Tie vere estas jenaj
speco de kvar bazaj ideoj

9
00:00:22,840 --> 00:00:25,190
ke io alia povas bolas malsupren al.

10
00:00:25,190 --> 00:00:28,150
Arrays, ligitaj listoj,
hash tabloj, kaj provoj.

11
00:00:28,150 --> 00:00:30,720
Kaj kiel mi diris,
estas varioj sur ili,

12
00:00:30,720 --> 00:00:32,720
sed tio estas bela
multe tuj resumos

13
00:00:32,720 --> 00:00:38,140
ĉio ni tuj paroli
proksimume en ĉi tiu klaso en terminoj de C.

14
00:00:38,140 --> 00:00:40,140
>> Sed kiel faras cxi cxiuj mezuron supren, dekstra?

15
00:00:40,140 --> 00:00:44,265
Ni jam parolis pri la avantaĝoj kaj contras
de ĉiu en apartajn videojn sur ili,

16
00:00:44,265 --> 00:00:46,390
sed ekzistas multe de nombroj
Akiranta ĵetita ĉirkaŭ.

17
00:00:46,390 --> 00:00:48,723
Ekzistas multe de ĝenerala
pensoj akiranta ĵetita ĉirkaŭ.

18
00:00:48,723 --> 00:00:51,950
Ni provu kaj solidigi
ĝin nur unu loko.

19
00:00:51,950 --> 00:00:55,507
Ni pezi la pros kontraŭ
la contras, kaj konsideri

20
00:00:55,507 --> 00:00:57,340
kiu datumstrukturo
eble estos la dekstra datumoj

21
00:00:57,340 --> 00:01:01,440
strukturo por via aparta situacio,
ajn speco de datumo vi stokante.

22
00:01:01,440 --> 00:01:06,625
Vi ne nepre ĉiam bezonas
uzi la super rapida inserción, forigoj,

23
00:01:06,625 --> 00:01:10,761
kaj lookup de trie se vi vere
ne zorgas pri enmeto kaj viŝante

24
00:01:10,761 --> 00:01:11,260
tro.

25
00:01:11,260 --> 00:01:13,968
Se vi bezonas nur rapide hazarda
aliro, eble tabelo estas pli bone.

26
00:01:13,968 --> 00:01:15,340
Do ni distili tio.

27
00:01:15,340 --> 00:01:18,530
Ni parolu pri ĉiu el la kvar
gravaj specoj de datumstrukturoj

28
00:01:18,530 --> 00:01:21,720
ke ni parolis pri, kaj
nur vidas kiam povus esti bona,

29
00:01:21,720 --> 00:01:23,340
kaj kiam ili ne povus esti tiel bona.

30
00:01:23,340 --> 00:01:24,610
Do ni komencu per tabeloj.

31
00:01:24,610 --> 00:01:27,300
Do inserción, jen speco de malbona.

32
00:01:27,300 --> 00:01:31,350
>> Inserción fine de tabelo estas OK,
se ni konstruas tabelo kiel ni iru.

33
00:01:31,350 --> 00:01:33,570
Sed se ni bezonas enmeti
elementoj en la mezo,

34
00:01:33,570 --> 00:01:35,550
pensas reen al inserción
speco, ekzistas multe

35
00:01:35,550 --> 00:01:37,510
el sxangxigxantaj konveni ero en tie.

36
00:01:37,510 --> 00:01:41,170
Kaj do se ni iras por enmeti
ie sed la fino de tabelo,

37
00:01:41,170 --> 00:01:43,590
ke estas probable ne tiom granda.

38
00:01:43,590 --> 00:01:46,710
>> Simile, forigoj, krom se ni estas
forviŝo de la fino de tabelo,

39
00:01:46,710 --> 00:01:49,810
Estas probable ankaŭ ne tiom granda se
ni ne volas lasi malplenaj interspacoj,

40
00:01:49,810 --> 00:01:50,790
Kiu kutime ni ne faras.

41
00:01:50,790 --> 00:01:54,700
Ni volas forigi elementon, kaj
tiam ia fari ĝin komforta denove.

42
00:01:54,700 --> 00:01:57,670
Kaj tiel viŝante elementojn de
tabelo, ankaŭ ne tiom granda.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, tamen, estas granda.

44
00:01:58,820 --> 00:02:00,920
Ni havas aliro aleatorio,
konstanta tempo lookup.

45
00:02:00,920 --> 00:02:03,800
Ni simple diru sep, kaj ni iru
al tabelo delokadoj sep.

46
00:02:03,800 --> 00:02:05,907
Ni diru 20, kun go al
tabelo delokadoj 20.

47
00:02:05,907 --> 00:02:07,240
Ni ne devas persisti trans.

48
00:02:07,240 --> 00:02:08,630
Tio estas sufiĉe bona.

49
00:02:08,630 --> 00:02:11,020
>> Arrays ankaŭ relative facile ordigi.

50
00:02:11,020 --> 00:02:14,040
Ĉiufoje ni parolis pri ordigado
algoritmo, kiel selektado speco,

51
00:02:14,040 --> 00:02:18,820
inserción varo, bobelo varo, kunfandi
varon, ni ĉiam uzis arrays fari ĝin,

52
00:02:18,820 --> 00:02:21,860
ĉar tabeloj estas sufiĉe facila por
varon, relativa al la datumstrukturoj

53
00:02:21,860 --> 00:02:22,970
ni vidis ĝis nun.

54
00:02:22,970 --> 00:02:24,320
>> Ili estas ankaŭ relative malgranda.

55
00:02:24,320 --> 00:02:25,695
Ekzistas ne multe da ekstra spaco.

56
00:02:25,695 --> 00:02:29,210
Vi nur flankenmetis ĝuste tiel
kiel vi devas teni vian datumon,

57
00:02:29,210 --> 00:02:30,320
kaj tio estas sufiĉe multe ĝin.

58
00:02:30,320 --> 00:02:33,180
Do ili estas belaj malgrandaj
kaj efikaj en tiu vojo.

59
00:02:33,180 --> 00:02:36,000
Sed alia malavantaĝo, kvankam,
estas ke ili estas fiksitaj en grandeco.

60
00:02:36,000 --> 00:02:38,630
Ni devas deklari precize kiel
big ni volas nian tabelo por esti,

61
00:02:38,630 --> 00:02:39,940
kaj ni nur akiras unu ŝancon al ĝi.

62
00:02:39,940 --> 00:02:41,280
Ni ne povas kreski kaj ŝrumpi ĝin.

63
00:02:41,280 --> 00:02:44,582
>> Se ni bezonas kreski aŭ ŝrumpi ĝin, ni
bezonas deklari tute nova tabelo,

64
00:02:44,582 --> 00:02:47,750
kopii ĉiujn la elementoj de la
unua tabelo en la dua tabelo.

65
00:02:47,750 --> 00:02:51,410
Kaj se ni miskalkulis ke
tempo, ni devas fari ĝin denove.

66
00:02:51,410 --> 00:02:52,760
Ne tiel granda.

67
00:02:52,760 --> 00:02:58,750
Do arrays ne donas al ni la fleksebleco
havi variablo nombroj de elementoj.

68
00:02:58,750 --> 00:03:01,320
>> Kun ligillisto,
inserción estas sufiĉe facila.

69
00:03:01,320 --> 00:03:03,290
Ni nur najlu sur la fronto.

70
00:03:03,290 --> 00:03:04,892
Forigo estas ankaŭ sufiĉe facila.

71
00:03:04,892 --> 00:03:06,100
Ni devas trovi la elementojn.

72
00:03:06,100 --> 00:03:07,270
Kiuj implikas iun serĉadon.

73
00:03:07,270 --> 00:03:10,270
>> Sed unufoje vi jam trovis la elementon
vi estas serĉanta, ĉiuj vi bezonas fari

74
00:03:10,270 --> 00:03:12,830
estas ŝanĝi puntero,
eble du se vi havas

75
00:03:12,830 --> 00:03:15,151
kunligita list-- duoble
ligillisto, rather--

76
00:03:15,151 --> 00:03:16,650
kaj tiam vi povas simple liberigi la nodo.

77
00:03:16,650 --> 00:03:18,399
Vi ne devas ŝanĝi
ĉio ĉirkaŭe.

78
00:03:18,399 --> 00:03:22,090
Vi nur ŝanĝi du punteros,
tiel ke estas sufiĉe rapida.

79
00:03:22,090 --> 00:03:23,470
>> Lookup estas malbona kvankam, dekstra?

80
00:03:23,470 --> 00:03:26,280
En ordo por ni trovi
elemento en ligillisto,

81
00:03:26,280 --> 00:03:29,154
ĉu unuope aŭ duoble ligitaj,
ni havos linear serĉu ĝin.

82
00:03:29,154 --> 00:03:32,320
Ni devas komenci je la komenco kaj
movi la fino, aŭ komenci fine movo

83
00:03:32,320 --> 00:03:33,860
al la komenco.

84
00:03:33,860 --> 00:03:35,474
Ni ne havas hazarda aliro anymore.

85
00:03:35,474 --> 00:03:37,265
Do se ni faras
Multa traserĉado, eble

86
00:03:37,265 --> 00:03:39,830
ligillisto ne
tre tiel bona por ni.

87
00:03:39,830 --> 00:03:43,750
>> Ili estas ankaŭ vere
malfacile ordigi, ĉu ne?

88
00:03:43,750 --> 00:03:45,666
La sola maniero vi povas
vere ordigi ligillisto

89
00:03:45,666 --> 00:03:47,870
estas ordigi ĝin kiel vi konstrui ĝin.

90
00:03:47,870 --> 00:03:50,497
Sed se vi ordigi ĝin kiel vi
konstrui ĝin, vi ne plu

91
00:03:50,497 --> 00:03:51,830
farante rapidajn inserciones anymore.

92
00:03:51,830 --> 00:03:53,746
Vi ne nur tacking
aferojn sur la fronto.

93
00:03:53,746 --> 00:03:55,710
Vi devas trovi la
dekstra loko por meti ĝin,

94
00:03:55,710 --> 00:03:57,820
kaj tiam via inserción
iĝas proksimume tiel malbona

95
00:03:57,820 --> 00:03:59,390
kiel enmeto en tabelo.

96
00:03:59,390 --> 00:04:03,130
Do ligitaj listoj ne estas
tiel granda por ordigado de datumoj.

97
00:04:03,130 --> 00:04:05,830
>> Ili estas ankaŭ belaj malgrandaj, grandeco-saĝa.

98
00:04:05,830 --> 00:04:08,496
Duoble ligita listo iomete
granda ol unuope ligitaj listoj,

99
00:04:08,496 --> 00:04:10,620
kiuj estas iomete pli granda
ol arrays, sed ĝi ne estas

100
00:04:10,620 --> 00:04:13,330
grandega kvanto de malŝparis spaco.

101
00:04:13,330 --> 00:04:18,730
Do se spaco estas ĉe premium, sed
Ne vere intensa premio,

102
00:04:18,730 --> 00:04:22,180
ĉi povus esti la ĝusta vojo por iri.

103
00:04:22,180 --> 00:04:23,330
>> Hash tabloj.

104
00:04:23,330 --> 00:04:25,850
Inserción en hash tablo
estas sufiĉe simpla.

105
00:04:25,850 --> 00:04:26,980
Ĝi estas du-paŝa procezo.

106
00:04:26,980 --> 00:04:30,700
Unue ni devas kuri nia datumoj tra
hash funkcio akiri hash kodo,

107
00:04:30,700 --> 00:04:37,550
kaj tiam ni enŝovu la elemento en la
hash tablo en tiu hash kodo situon.

108
00:04:37,550 --> 00:04:40,879
>> Forigo, simila al ligillisto,
Facilas iam vi trovos la elemento.

109
00:04:40,879 --> 00:04:43,170
Vi devas trovi ĝin unue,
sed tiam, kiam vi forigas ĝin,

110
00:04:43,170 --> 00:04:45,128
vi nur bezonos interŝanĝi
kelkaj punteros,

111
00:04:45,128 --> 00:04:47,250
se vi uzas apartan sinsekvon.

112
00:04:47,250 --> 00:04:49,942
Se vi uzas sondado,
aŭ se vi ne estas

113
00:04:49,942 --> 00:04:51,650
uzante ĉenante tute
en via hash tablo,

114
00:04:51,650 --> 00:04:53,040
forigo estas efektive vere facila.

115
00:04:53,040 --> 00:04:57,134
Ĉiuj vi devas fari estas hash la
datumoj, kaj tiam iru al tiu loko.

116
00:04:57,134 --> 00:04:58,925
Kaj supozante vi faras ne
havas koliziojn,

117
00:04:58,925 --> 00:05:01,650
vi povos forviŝi tre rapide.

118
00:05:01,650 --> 00:05:04,930
>> Nun, lookup estas kie aferoj
ricevas iom pli komplika.

119
00:05:04,930 --> 00:05:06,910
Ĝi estas averaĝe pli bona
ol ligitaj listoj.

120
00:05:06,910 --> 00:05:09,560
Se vi uzas sinsekvon,
vi ankoraŭ havas ligillisto,

121
00:05:09,560 --> 00:05:13,170
kio signifas ke vi ankoraŭ havas la
serĉo malutilo ligillisto.

122
00:05:13,170 --> 00:05:18,390
Sed ĉar vi prenas vian ligitaj
lerta kaj disfendante ĝin super 100 aŭ 1,000

123
00:05:18,390 --> 00:05:25,380
aŭ n elementoj en via hash tablo, vi estas
ligitaj listoj cxiuj estas unu na la grandeco.

124
00:05:25,380 --> 00:05:27,650
Ili ĉiuj estas substance pli malgranda.

125
00:05:27,650 --> 00:05:32,080
Vi n ligitaj listoj anstataŭe
de unu ligillisto de amplekso n.

126
00:05:32,080 --> 00:05:34,960
>> Kaj tiel ĉi reala mondo konstanta
faktoro, kiun ni ĝenerale

127
00:05:34,960 --> 00:05:39,730
Ne parolu pri ĝustatempe komplekseco, ĝi
faras efektive fari diferencon cxi tie.

128
00:05:39,730 --> 00:05:43,020
Do lookup estas ankoraŭ lineara
serĉu, se vi uzas sinsekvon,

129
00:05:43,020 --> 00:05:46,780
sed la longo de la listo
vi trasercxante

130
00:05:46,780 --> 00:05:50,080
estas tre, tre mallonga por komparo.

131
00:05:50,080 --> 00:05:52,995
Denove, se ordigado estas via
celo tie, hash tablo la

132
00:05:52,995 --> 00:05:54,370
probable ne la ĝusta vojo por iri.

133
00:05:54,370 --> 00:05:56,830
Simple uzu tabelo se ordiga
estas vere grava por vi.

134
00:05:56,830 --> 00:05:58,590
>> Kaj ili povas kuri la gamut de grandeco.

135
00:05:58,590 --> 00:06:01,640
Estas malfacile diri, ĉu
hash tablo estas malgranda aŭ granda,

136
00:06:01,640 --> 00:06:04,110
ĉar vere dependas
kiom granda viajn hash tablo estas.

137
00:06:04,110 --> 00:06:07,340
Se vi nur tuj estos stokante
kvin elementoj en via hash tablo,

138
00:06:07,340 --> 00:06:10,620
kaj vi havas hash tablo
kun 10.000 elementoj en ĝi,

139
00:06:10,620 --> 00:06:12,614
vi probable malŝparas multe da spaco.

140
00:06:12,614 --> 00:06:15,030
Kontrasto esti vi povas ankaŭ
havas tre kompakta hash tabloj,

141
00:06:15,030 --> 00:06:18,720
sed la malgrandaj viajn hash tablo ricevas,
la longaj ĉiu de tiuj ligitaj lertaj

142
00:06:18,720 --> 00:06:19,220
ricevas.

143
00:06:19,220 --> 00:06:22,607
Kaj tiel ekzistas vere neniu maniero por difini
ĝuste la grandeco de hash tablo,

144
00:06:22,607 --> 00:06:24,440
sed ĝi estas probable sekura
diri ke estas ĝenerale

145
00:06:24,440 --> 00:06:27,990
tuj estos granda ol kunligita
listo stokante la samaj datumoj,

146
00:06:27,990 --> 00:06:30,400
sed pli malgranda ol trie.

147
00:06:30,400 --> 00:06:32,720
>> Kaj klopodoj estas la kvara
de tiuj strukturoj

148
00:06:32,720 --> 00:06:34,070
ke ni parolis pri.

149
00:06:34,070 --> 00:06:36,450
Enmeto en trie estas kompleksa.

150
00:06:36,450 --> 00:06:38,400
Ekzistas multe de dinamika
memoro atribuo,

151
00:06:38,400 --> 00:06:40,780
speciale komence,
kiel vi komencas konstrui.

152
00:06:40,780 --> 00:06:43,700
Sed estas konstanta tempo.

153
00:06:43,700 --> 00:06:47,690
Ĝi estas nur la homa elemento
tie kiu faras ĝin malfacila.

154
00:06:47,690 --> 00:06:53,250
Devante renkontas nula puntero, malloc
spaco, iri tien, eble malloc spaco

155
00:06:53,250 --> 00:06:54,490
de tie denove.

156
00:06:54,490 --> 00:06:58,880
La varo de timigado faktoro de
punteros en dinamika memoro atribuo

157
00:06:58,880 --> 00:07:00,130
estas la hurdo malbari.

158
00:07:00,130 --> 00:07:04,550
Sed iam vi malbaris ĝin, inserción
fakte venas tute simpla,

159
00:07:04,550 --> 00:07:06,810
kaj gxi certe estas konstanta tempo.

160
00:07:06,810 --> 00:07:07,680
>> Forigo estas facila.

161
00:07:07,680 --> 00:07:11,330
Ĉiuj vi devas fari estas navigi malsupren
kelkaj montriloj kaj libera la nodo,

162
00:07:11,330 --> 00:07:12,420
tiel ke estas sufiĉe bonaj.

163
00:07:12,420 --> 00:07:13,930
Lookup estas ankaŭ sufiĉe rapida.

164
00:07:13,930 --> 00:07:16,780
Ĝi estas nur bazita sur la
longo de viaj datumoj.

165
00:07:16,780 --> 00:07:19,924
Do se ĉiuj viaj datumoj estas
kvin karaktero ŝnuroj,

166
00:07:19,924 --> 00:07:22,590
ekzemple, vi stokante kvin
karaktero ŝnuroj en via trie,

167
00:07:22,590 --> 00:07:25,439
ĝi nur prenas kvin paŝoj al
trovi kion vi serĉas.

168
00:07:25,439 --> 00:07:28,480
Kvin estas nur konstanta faktoro, tiel
denove, inserción, forigo, kaj lookup

169
00:07:28,480 --> 00:07:31,670
tie ĉiuj estas konstanta tempo, efike.

170
00:07:31,670 --> 00:07:34,880
>> Alia afero estas ke via trie estas
fakte speco de jam ordo, ĉu ne?

171
00:07:34,880 --> 00:07:36,800
En virto de kiel ni estas
enmeto elementoj,

172
00:07:36,800 --> 00:07:40,060
irante letero de letero de la
klavo, aŭ cifero de cifero de la ŝlosilo,

173
00:07:40,060 --> 00:07:45,084
tipe, via trie finas esti
ia ordo kiel vi konstruos ĝin.

174
00:07:45,084 --> 00:07:47,250
Fakte ne faras
sentita pensi pri ordigado

175
00:07:47,250 --> 00:07:49,874
en la sama maniero kiel ni pensas pri
ĝi kun sensilo, aŭ ligitaj listoj,

176
00:07:49,874 --> 00:07:51,070
aŭ hash tabloj.

177
00:07:51,070 --> 00:07:54,780
Sed iusence, via
trie estas ordo kiel vi iros.

178
00:07:54,780 --> 00:07:58,630
>> La malavantaĝo, kompreneble, estas ke
trie rapide iĝas grandega.

179
00:07:58,630 --> 00:08:02,970
El ĉiu junton punkto, vi eble
have-- se via ŝlosilo konsistas de ciferoj,

180
00:08:02,970 --> 00:08:04,880
vi havos 10 aliaj
lokoj vi povas iri, kiu

181
00:08:04,880 --> 00:08:07,490
signifas ke ĉiu nodo
enhavas informon

182
00:08:07,490 --> 00:08:11,440
pri la datumojn vi volas konservi
en tiu nodo, plus 10 punteros.

183
00:08:11,440 --> 00:08:14,430
Kiu, sur CS50 IDE, estas 80 bajtoj.

184
00:08:14,430 --> 00:08:17,220
Do estas almenaŭ 80 bajtoj por
ĉiu nodo kiun vi kreas,

185
00:08:17,220 --> 00:08:19,240
kaj tio eĉ ne kalkulante datumoj.

186
00:08:19,240 --> 00:08:24,950
Kaj se via nodoj estas
literojn anstataŭ ciferoj,

187
00:08:24,950 --> 00:08:27,825
nun vi havas 26 punteros
de ĉiu loko.

188
00:08:27,825 --> 00:08:32,007
Kaj 26 fojojn 8 estas probable 200
bajtoj, aŭ io simila.

189
00:08:32,007 --> 00:08:33,840
Kaj vi havas ĉefurbo
kaj lowercase-- vi povas

190
00:08:33,840 --> 00:08:35,381
vidi kie mi iros kun tiu, ĉu ne?

191
00:08:35,381 --> 00:08:37,500
Via nodoj povas akiri vere
granda, kaj tiel la trie

192
00:08:37,500 --> 00:08:40,470
mem, entute, povas
akiri vere granda, tro.

193
00:08:40,470 --> 00:08:42,630
Do se spaco estas ĉe alta
premio en via sistemo,

194
00:08:42,630 --> 00:08:45,830
trie eble ne estas la dekstra maniero
iri, eĉ se liaj aliaj profitoj

195
00:08:45,830 --> 00:08:47,780
veni en ludon.

196
00:08:47,780 --> 00:08:48,710
Mi Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Jen CS50.

198
00:08:50,740 --> 00:08:52,316