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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Beraz CS50, Nik estaltzen dugu
Datu-egitura desberdinak asko,

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

4
00:00:09,180 --> 00:00:11,420
Arrayak ikusi dugu, eta lotuta
zerrendak eta hash taulak,

5
00:00:11,420 --> 00:00:15,210
eta saiatzen da, pilak eta ilarak.

6
00:00:15,210 --> 00:00:17,579
Ere, apur bat ikasi dugu
zuhaitz eta metak buruz,

7
00:00:17,579 --> 00:00:20,120
baina benetan horiek guztiak, besterik gabe amaituko
up gai bat aldaketa izanik.

8
00:00:20,120 --> 00:00:22,840
Horiek Benetan,
oinarrizko lau ideia mota

9
00:00:22,840 --> 00:00:25,190
Dena dela, beste irakiten daiteke behera.

10
00:00:25,190 --> 00:00:28,150
Arrayak, lotuta zerrendak,
hash taulak, eta saiatzen da.

11
00:00:28,150 --> 00:00:30,720
Eta antzera, esan nion ez
horien gainean aldakuntzak daude,

12
00:00:30,720 --> 00:00:32,720
baina hori nahiko
Askoz laburbiltzeko joan

13
00:00:32,720 --> 00:00:38,140
Dena ari gara hitz joan
C. dagokionez class honi buruz

14
00:00:38,140 --> 00:00:40,140
>> Baina nola egin horiek neurri guztiak eman, ezta?

15
00:00:40,140 --> 00:00:44,265
Aldekoak eta kontrakoak buruz hitz egin dugu
horien gainean bideoak bereiziak bakoitzeko,

16
00:00:44,265 --> 00:00:46,390
baina ez zenbakiak asko da
ohitu inguruan bota.

17
00:00:46,390 --> 00:00:48,723
Ez dago general asko da
pentsamenduak ohitu inguruan bota.

18
00:00:48,723 --> 00:00:51,950
Dezagun saiatu eta sendotzeko
leku bakar bat sartu da.

19
00:00:51,950 --> 00:00:55,507
Dezagun pisatzen pros aurka
txarrez, eta kontuan hartu

20
00:00:55,507 --> 00:00:57,340
zein datu-egitura
Eskuineko datuak izan liteke

21
00:00:57,340 --> 00:01:01,440
zure egoera bereziki egitura,
edozein motatako datuen gordetzeko zaren.

22
00:01:01,440 --> 00:01:06,625
Zuk ez dute zertan beti behar den
super azkar txertatzeko, ezabatzeko erabili,

23
00:01:06,625 --> 00:01:10,761
eta trie bat bilatu nahi izanez gero, benetan
ez txertatu eta ezabatu zaintzeko

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

25
00:01:11,260 --> 00:01:13,968
Besterik azkar ausazko behar baduzu
sarbidea, agian array bat hobea da.

26
00:01:13,968 --> 00:01:15,340
Hargatik destila hori.

27
00:01:15,340 --> 00:01:18,530
Hitz egin lau bakoitzari buruz
Datu-egitura mota nagusien

28
00:01:18,530 --> 00:01:21,720
Horri buruz hitz egin dugu, eta
besterik ikusten denean ona izan dute agian,

29
00:01:21,720 --> 00:01:23,340
Noiz eta agian ez dute hain ona.

30
00:01:23,340 --> 00:01:24,610
Hargatik hilarak en.

31
00:01:24,610 --> 00:01:27,300
Beraz txertatzeko, hori da mota txarra.

32
00:01:27,300 --> 00:01:31,350
>> Array baten amaieran-sartzeak ondo dago;
dugu array bat eraikitzen ari bada joan gara.

33
00:01:31,350 --> 00:01:33,570
Baina txertatu behar badugu
erdian sartu elementuak,

34
00:01:33,570 --> 00:01:35,550
uste back-sartzeak den
ordenatu, han asko da

35
00:01:35,550 --> 00:01:37,510
elementu bat egokitzeko hor ikusita.

36
00:01:37,510 --> 00:01:41,170
Eta ari gara txertatu hala bada joan
edonon baina array baten amaiera,

37
00:01:41,170 --> 00:01:43,590
Hori ez da, seguruenik, hain handia.

38
00:01:43,590 --> 00:01:46,710
>> Era berean, ezabatzeko, ari gara salbu
array baten amaiera ezabatu,

39
00:01:46,710 --> 00:01:49,810
Era berean, seguruenik ez da hain handia bada
ez dugu hutsuneak hutsik utzi nahi,

40
00:01:49,810 --> 00:01:50,790
hau da, normalean ez dugu.

41
00:01:50,790 --> 00:01:54,700
Elementu bat kendu nahi dugu, eta
Orduz Sort egin berriro snug da.

42
00:01:54,700 --> 00:01:57,670
Eta orain elementuak ezabatzen
sorta bat, gainera, ez da hain handia.

43
00:01:57,670 --> 00:01:58,820
>> Bilaketa, ordea, handia da.

44
00:01:58,820 --> 00:02:00,920
Ausazko sarbidea izan dugu,
denbora etengabe bilatu.

45
00:02:00,920 --> 00:02:03,800
Esango dugu besterik zazpi, eta joan ginen
array lekualdaketa zazpi.

46
00:02:03,800 --> 00:02:05,907
Esango dugu, 20, joan
array lekualdaketa 20.

47
00:02:05,907 --> 00:02:07,240
Guk ez dugu izan zeharkatuz batetik bestera joateko.

48
00:02:07,240 --> 00:02:08,630
Hori nahiko ona.

49
00:02:08,630 --> 00:02:11,020
>> Arrayak ordenatzeko nahiko erraza.

50
00:02:11,020 --> 00:02:14,040
Aldi bakoitzean hitz egin dugu ordenazio buruz
bildu, hala nola aukeraketa sort bezala,

51
00:02:14,040 --> 00:02:18,820
txertatzeko ordenatu, burbuila ordenatu, batu
ordenatu, beti da egiten baikenuen arrayak,

52
00:02:18,820 --> 00:02:21,860
array nahiko erraza delako
ordenatu, datuen egitura erlatiboa

53
00:02:21,860 --> 00:02:22,970
Orain arte ikusi dugu.

54
00:02:22,970 --> 00:02:24,320
>> Halaber, txiki samarra ari dira.

55
00:02:24,320 --> 00:02:25,695
Ez zeukan beste tarte asko.

56
00:02:25,695 --> 00:02:29,210
Ezarri besterik ez alde batera utzita, zehazki bezainbeste
Zure datuak eduki behar duzun bezala,

57
00:02:29,210 --> 00:02:30,320
eta hori nahiko askoz da.

58
00:02:30,320 --> 00:02:33,180
Beraz, nahiko txikiak ari dira
eta horrela eraginkorra.

59
00:02:33,180 --> 00:02:36,000
Baina arazotxo bat, nahiz eta,
da tamaina dutela finkoak dira.

60
00:02:36,000 --> 00:02:38,630
Zehazki deklaratzeko nola egin behar dugu
big gure array izan nahi dugu,

61
00:02:38,630 --> 00:02:39,940
eta jaurtiketa bat bakarrik lortuko ditugula.

62
00:02:39,940 --> 00:02:41,280
Ezin dugu hazten eta txikitu.

63
00:02:41,280 --> 00:02:44,582
>> Hazten edo txikitu behar badugu,
array erabat berria aldarrikatu behar,

64
00:02:44,582 --> 00:02:47,750
kopiatu elementu guztien
bigarren array sartu lehen array.

65
00:02:47,750 --> 00:02:51,410
Eta kalkulu okerrak dugu badu
denbora, berriro egin behar dugu.

66
00:02:51,410 --> 00:02:52,760
Ez da hain handia.

67
00:02:52,760 --> 00:02:58,750
Beraz, multzo ez eman malgutasuna
elementuen zenbakiak aldakorra dute.

68
00:02:58,750 --> 00:03:01,320
>> Zerrenda bat lotuta,
Txertatze nahiko erraza da.

69
00:03:01,320 --> 00:03:03,290
Aurrean kalera Tack besterik ez dugu.

70
00:03:03,290 --> 00:03:04,892
Ezabaketa ere nahiko erraza da.

71
00:03:04,892 --> 00:03:06,100
Elementu aurkitu behar dugu.

72
00:03:06,100 --> 00:03:07,270
Hori bilatzeko batzuk inplikatzeko.

73
00:03:07,270 --> 00:03:10,270
>> Baina behin elementua aurkitu duzu
duzu, egin behar duzun guztia zabiltzala

74
00:03:10,270 --> 00:03:12,830
da erakuslea aldatu,
seguru bi baldin baduzu

75
00:03:12,830 --> 00:03:15,151
bi aldiz bat list-- lotuta
Zerrenda lotuta, rather--

76
00:03:15,151 --> 00:03:16,650
eta, ondoren, besterik libre dezakezu nodoa.

77
00:03:16,650 --> 00:03:18,399
Ez daukazu filmea
dena inguruan.

78
00:03:18,399 --> 00:03:22,090
Bi erakusleak aldatu besterik ez duzu,
beraz, nahiko azkarra da.

79
00:03:22,090 --> 00:03:23,470
>> Bilaketa txarra bada ere, ezta?

80
00:03:23,470 --> 00:03:26,280
Bat aurkitu guretzat ordenan
lotuta zerrenda batean elementu,

81
00:03:26,280 --> 00:03:29,154
ala banaka edo bi aldiz lotuta,
bilatu lineala behar dugu.

82
00:03:29,154 --> 00:03:32,320
To hasieran hasiko ditugu, eta
mugitu amaieran, bai bukaerako mugimendua hasten

83
00:03:32,320 --> 00:03:33,860
hasieran.

84
00:03:33,860 --> 00:03:35,474
Guk ez dugu izan ausazko sarbidea jada.

85
00:03:35,474 --> 00:03:37,265
Beraz, bat egiten ari gara,
Bilatzen asko, agian,

86
00:03:37,265 --> 00:03:39,830
lotutako zerrenda bat, ez da
hain ona da guretzat.

87
00:03:39,830 --> 00:03:43,750
>> Oraindik ere oso
ordenatzeko zaila da, ezta?

88
00:03:43,750 --> 00:03:45,666
Ahal duzun Modu bakarra
lotutako zerrenda bat benetan ordenatzeko

89
00:03:45,666 --> 00:03:47,870
dela ordenatzeko Eraikitzeko duzun bezala.

90
00:03:47,870 --> 00:03:50,497
Baina egiten duzun bezala ordenatzen badituzu
eraikitzen da, Oraindik ez dago jada

91
00:03:50,497 --> 00:03:51,830
sarrerak azkar jada egiteko.

92
00:03:51,830 --> 00:03:53,746
Oraindik ez duzu besterik tacking
Gauzak aurrean kalera.

93
00:03:53,746 --> 00:03:55,710
Aurkitu behar duzu
eskuineko spot jarri,

94
00:03:55,710 --> 00:03:57,820
eta, ondoren, zure txertatze-
bihurtzen besterik buruz bezain txarra

95
00:03:57,820 --> 00:03:59,390
array batean txertatzeak bezala.

96
00:03:59,390 --> 00:04:03,130
Beraz, zerrendak lotuta ez dauden
hain handia datuak ordenatzeko.

97
00:04:03,130 --> 00:04:05,830
>> Oraindik ere nahiko txikiak, tamaina-wise.

98
00:04:05,830 --> 00:04:08,496
Bi aldiz lotuta zerrenda zertxobait
banaka lotuta zerrendak baino handiagoak,

99
00:04:08,496 --> 00:04:10,620
diren zertxobait handiagoa
array baino, baina ez da

100
00:04:10,620 --> 00:04:13,330
alferrik galtzen espazioa kopuru handi bat.

101
00:04:13,330 --> 00:04:18,730
Beraz, bada, espazio prima bat da, baina
Ez prima benetan bizia,

102
00:04:18,730 --> 00:04:22,180
hau da joan eskuineko bidea izan liteke.

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

104
00:04:23,330 --> 00:04:25,850
Hash taula bat sartzen lagunduz
nahiko erraza da.

105
00:04:25,850 --> 00:04:26,980
Bi-prozesuan urrats bat da.

106
00:04:26,980 --> 00:04:30,700
Lehen bitartez gure datuak exekutatu behar dugu
hash funtzio bat hash kodea lortzeko,

107
00:04:30,700 --> 00:04:37,550
eta, ondoren, sartu elementua txertatu dugu
Hash kodea kokapena hartan mahai hash.

108
00:04:37,550 --> 00:04:40,879
>> Deletion, lotuta zerrenda antzekoak,
erraza da behin elementu aurkituko dituzu.

109
00:04:40,879 --> 00:04:43,170
Da lehen aurkitu behar duzu,
baina, orduan, ezabatzeko duzu,

110
00:04:43,170 --> 00:04:45,128
besterik truke behar duzu
erakusleak pare bat,

111
00:04:45,128 --> 00:04:47,250
bereizi kateatzea erabiliz gero.

112
00:04:47,250 --> 00:04:49,942
Kraterrak erabiltzen ari bazara,
edo ez bazaude

113
00:04:49,942 --> 00:04:51,650
batere kateatzea erabiliz
hash taula batean,

114
00:04:51,650 --> 00:04:53,040
ezabatzeko benetan oso erraza da.

115
00:04:53,040 --> 00:04:57,134
Guztiak egin behar duzun da hash
datuak, eta, ondoren, kokapena joango dira.

116
00:04:57,134 --> 00:04:58,925
Eta suposatuz ez duzu
talkak dute,

117
00:04:58,925 --> 00:05:01,650
Oso azkar ezabatu ahal izango duzu.

118
00:05:01,650 --> 00:05:04,930
>> Orain, bilatu non gauza da
pixka bat zailagoa da.

119
00:05:04,930 --> 00:05:06,910
Batez besteko hobea on It
lotutako zerrendak baino.

120
00:05:06,910 --> 00:05:09,560
Kateatzea erabiltzen ari bazara,
oraindik lotuta zerrenda bat duzu,

121
00:05:09,560 --> 00:05:13,170
horrek esan nahi du, oraindik ere, behar duzun
bilaketa lotuta zerrenda kaltetan.

122
00:05:13,170 --> 00:05:18,390
Baina zuk hartzen ari delako zure lotuta
Zerrenda eta splitting 100 edo 1.000

123
00:05:18,390 --> 00:05:25,380
edo n zure hash taula elementu, zaren
lotuta zerrendak tamaina Ngarren bat dira.

124
00:05:25,380 --> 00:05:27,650
Guztiak nabarmenki txikiagoa Oraindik dute.

125
00:05:27,650 --> 00:05:32,080
Izan n lotuta Zerrendak ordez
lotuta tamaina n zerrenda bat.

126
00:05:32,080 --> 00:05:34,960
>> Eta beraz, real-mundu honetan konstante
faktorea, oro har, zein dugu

127
00:05:34,960 --> 00:05:39,730
ez hitz egin, denbora konplexutasuna, hura
du benetan egin diferentzia hemen.

128
00:05:39,730 --> 00:05:43,020
Beraz bilatu lineala oraindik
bilatu kateatzea erabiliz gero,

129
00:05:43,020 --> 00:05:46,780
baina zerrenda luzera
bilatzean zu

130
00:05:46,780 --> 00:05:50,080
da, oso, oso labur alderatuz.

131
00:05:50,080 --> 00:05:52,995
Berriz ere, ordenazio zure badago
Helburua hemen, hash taula

132
00:05:52,995 --> 00:05:54,370
seguruenik ez da eskuineko bidea joan.

133
00:05:54,370 --> 00:05:56,830
Just matrizea erabiliko dira ordenatzeko bada
da benetan garrantzia.

134
00:05:56,830 --> 00:05:58,590
>> Eta tamaina gamaren exekutatu ahal izango dute.

135
00:05:58,590 --> 00:06:01,640
Zaila da bat esatea
Hash taula txiki edo handi,

136
00:06:01,640 --> 00:06:04,110
Egiatan araberakoa delako
nola handi hash taula da.

137
00:06:04,110 --> 00:06:07,340
Gordetzeko bakarrik bazoaz
bost elementu hash taula batean,

138
00:06:07,340 --> 00:06:10,620
eta hash taula bat behar duzu
10.000 bertan elementuekin,

139
00:06:10,620 --> 00:06:12,614
Ziurrenik ari espazio asko alferrik galtzen duzu.

140
00:06:12,614 --> 00:06:15,030
Kontrastatu duzu ere ari daiteke
hash oso trinkoa mahaiak dute,

141
00:06:15,030 --> 00:06:18,720
baina txikiagoa hash taula lortzen,
luzeagoak loturiko zerrendak horietako bakoitza

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

143
00:06:19,220 --> 00:06:22,607
Eta, beraz, ez da benetan den definitzen du inola
zehazki hash taula baten tamaina,

144
00:06:22,607 --> 00:06:24,440
baina seguruenik seguru
esateko oro har,

145
00:06:24,440 --> 00:06:27,990
a lotuta baino handiagoa izango da
Zerrenda bera datuak gordetzeko,

146
00:06:27,990 --> 00:06:30,400
baina trie bat baino txikiagoa.

147
00:06:30,400 --> 00:06:32,720
>> Eta saiatzen laugarrena dira
Egitura horiek

148
00:06:32,720 --> 00:06:34,070
Hori egin dugu buruz hitz egiten.

149
00:06:34,070 --> 00:06:36,450
Trie bat sartu txertatzeak konplexua da.

150
00:06:36,450 --> 00:06:38,400
Ez dago dinamikoa asko da
memoria esleipena,

151
00:06:38,400 --> 00:06:40,780
batez ere, hasieran,
eraikitzeko hasten zaren bezala.

152
00:06:40,780 --> 00:06:43,700
Baina etengabeko denbora da.

153
00:06:43,700 --> 00:06:47,690
Giza elementu bakarra da,
Hemen egiten duen delikatua.

154
00:06:47,690 --> 00:06:53,250
Null erakuslea topo beharrik, malloc
espazioa, han joan, espazio seguru malloc

155
00:06:53,250 --> 00:06:54,490
hortik berriro.

156
00:06:54,490 --> 00:06:58,880
Larderia faktore moduko
memoria dinamikoa esleipena erakusleak

157
00:06:58,880 --> 00:07:00,130
oztopoa den argi dago.

158
00:07:00,130 --> 00:07:04,550
Baina behin garbitu egiten, txertatzeko
Egia esan, nahiko erraz dator,

159
00:07:04,550 --> 00:07:06,810
eta, zalantzarik gabe, etengabeko denbora da.

160
00:07:06,810 --> 00:07:07,680
>> Ezabaketa erraza da.

161
00:07:07,680 --> 00:07:11,330
Guztiak egin behar duzun da nabigatu behera
erakusleak eta doan nodoa pare,

162
00:07:11,330 --> 00:07:12,420
beraz, nahiko ona.

163
00:07:12,420 --> 00:07:13,930
Bilatu ere nahiko azkarra da.

164
00:07:13,930 --> 00:07:16,780
Honez bakarrik oinarritutako
Zure datuak luzera.

165
00:07:16,780 --> 00:07:19,924
Beraz, zure datu guztiak badago
bost pertsonaia kateak,

166
00:07:19,924 --> 00:07:22,590
adibidez, bost gordetzeko zaren
Pertsonaia zure trie kateak,

167
00:07:22,590 --> 00:07:25,439
bost urrats bakarrik hartzen du
da zer bilatzen ari zaren aurkitzeko.

168
00:07:25,439 --> 00:07:28,480
Etengabeko faktore bat besterik Bost dago, beraz,
Berriro, txertatzeko, ezabatzeko, eta bilatu

169
00:07:28,480 --> 00:07:31,670
Hemen zaude etengabeko denbora guztian, eraginkortasunez.

170
00:07:31,670 --> 00:07:34,880
>> Beste gauza bat da zure trie dela
benetan mota dagoeneko horrela, ezta?

171
00:07:34,880 --> 00:07:36,800
Nola ari garen indarrez
elementu sartuko,

172
00:07:36,800 --> 00:07:40,060
Gutun joan letra by arabera
gakoa, edo gakoaren digituko arabera digituko,

173
00:07:40,060 --> 00:07:45,084
normalean, zure trie bukatzen ari
motatako ordenatuko eratzen duzun bezala.

174
00:07:45,084 --> 00:07:47,250
Ez du benetan egiten
Zentzu ordenatzeko pentsatzen

175
00:07:47,250 --> 00:07:49,874
modu berean pentsatzen dugu
da multzo dute, edo zerrendak lotuta,

176
00:07:49,874 --> 00:07:51,070
edo hash taulak.

177
00:07:51,070 --> 00:07:54,780
Baina nolabait, zure
trie ordenatuko da joan ahala.

178
00:07:54,780 --> 00:07:58,630
>> Arazotxo, jakina, hori da
trie bat azkar handi bihurtzen da.

179
00:07:58,630 --> 00:08:02,970
Bidegurutzera puntu guztietatik, baliteke
have-- zure gako digituak osatzen bada,

180
00:08:02,970 --> 00:08:04,880
duzu 10 bestelako
lekuak joan ahal izango duzu, eta horrek

181
00:08:04,880 --> 00:08:07,490
nodo bakoitzean esan nahi du
informazioa du

182
00:08:07,490 --> 00:08:11,440
datuei buruz gorde nahi duzu
nodo hori, plus 10 erakusle dira.

183
00:08:11,440 --> 00:08:14,430
Zein, CS50 IDE, 80 byte da.

184
00:08:14,430 --> 00:08:17,220
Beraz, gutxienez 80 byte da
zuk sortutako nodo bakoitzean,

185
00:08:17,220 --> 00:08:19,240
eta hori ez da datu are kontatuta.

186
00:08:19,240 --> 00:08:24,950
Eta zure nodo badira
letren ordez digituen,

187
00:08:24,950 --> 00:08:27,825
orain 26 erakusle duzu
kokapena guztietatik.

188
00:08:27,825 --> 00:08:32,007
Eta 26 aldiz 8 da seguruenik 200
byte, edo horrelako zerbait.

189
00:08:32,007 --> 00:08:33,840
Eta kapital duzu
eta minuskulaz dezakezu

190
00:08:33,840 --> 00:08:35,381
Begira non honekin noa, ezta?

191
00:08:35,381 --> 00:08:37,500
Zure nodo benetan lortu ahal
big, eta beraz, trie

192
00:08:37,500 --> 00:08:40,470
bera, oro har, ezin
benetan big, gehiegi.

193
00:08:40,470 --> 00:08:42,630
Beraz, bada espazio altua da
premium zure sisteman,

194
00:08:42,630 --> 00:08:45,830
trie bat agian ez du modu eskubidea izan
joan, nahiz eta bere beste prestazioak arren

195
00:08:45,830 --> 00:08:47,780
jokoan sartzen dira.

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

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

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