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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Kwa hiyo katika CS50, tumekuwa kufunikwa
mengi ya miundo tofauti data,

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

4
00:00:09,180 --> 00:00:11,420
Tumeona arrays, na wanaohusishwa
orodha, na meza hash,

5
00:00:11,420 --> 00:00:15,210
na inajaribu, mwingi na foleni.

6
00:00:15,210 --> 00:00:17,579
Tutaweza pia kujifunza kidogo
kuhusu miti na magofu,

7
00:00:17,579 --> 00:00:20,120
lakini kwa kweli haya yote tu kuishia
up kuwa tofauti juu ya mandhari.

8
00:00:20,120 --> 00:00:22,840
Kuna kweli ni haya
aina ya mawazo nne za msingi

9
00:00:22,840 --> 00:00:25,190
kwamba kila kitu kingine unaweza jipu chini kwa.

10
00:00:25,190 --> 00:00:28,150
Arrays, wanaohusishwa orodha,
meza hash, na inajaribu.

11
00:00:28,150 --> 00:00:30,720
Na kama nilivyosema, kuna
ni tofauti juu yao,

12
00:00:30,720 --> 00:00:32,720
lakini hii ni pretty
mengi kwenda muhtasari

13
00:00:32,720 --> 00:00:38,140
kila kitu sisi ni kwenda kuzungumza
kuhusu katika darasa hili katika suala la C.

14
00:00:38,140 --> 00:00:40,140
>> Lakini ni jinsi gani haya yote hatua up, sawa?

15
00:00:40,140 --> 00:00:44,265
Tumekuwa aliyesema kuhusu faida na hasara
wa kila katika video tofauti juu yao,

16
00:00:44,265 --> 00:00:46,390
lakini kuna mengi ya idadi
kupata kutupwa kuzunguka.

17
00:00:46,390 --> 00:00:48,723
Kuna mengi ya ujumla
mawazo kupata kutupwa kuzunguka.

18
00:00:48,723 --> 00:00:51,950
Hebu jaribu na kuimarisha
ni katika nafasi moja tu.

19
00:00:51,950 --> 00:00:55,507
Hebu kupima faida dhidi ya
hasara, na kufikiria

20
00:00:55,507 --> 00:00:57,340
ambayo muundo wa data
inaweza kuwa data sahihi

21
00:00:57,340 --> 00:01:01,440
muundo kwa hali yako maalum,
chochote aina ya data wewe ni hifadhi.

22
00:01:01,440 --> 00:01:06,625
Wewe si lazima daima haja ya
kutumia super haraka kuingizwa, kufutwa,

23
00:01:06,625 --> 00:01:10,761
na chaguo-ya trie kama kweli
hawajali kuingiza na kufuta

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

25
00:01:11,260 --> 00:01:13,968
Kama unahitaji haraka tu bila mpangilio
upatikanaji, labda safu ni bora zaidi.

26
00:01:13,968 --> 00:01:15,340
Basi hebu distill hiyo.

27
00:01:15,340 --> 00:01:18,530
Hebu majadiliano juu ya kila moja ya nne
aina kuu ya miundo data

28
00:01:18,530 --> 00:01:21,720
kwamba tumekuwa kuongelea, na
tu kuona wakati wao inaweza kuwa nzuri,

29
00:01:21,720 --> 00:01:23,340
na wakati wao wanaweza kuwa hivyo nzuri.

30
00:01:23,340 --> 00:01:24,610
Basi hebu kuanza na arrays.

31
00:01:24,610 --> 00:01:27,300
Hivyo kuingizwa, hiyo ni aina ya mbaya.

32
00:01:27,300 --> 00:01:31,350
>> Kuingizwa mwishoni mwa safu ni sawa,
kama sisi ni kujenga safu kama sisi kwenda.

33
00:01:31,350 --> 00:01:33,570
Lakini kama sisi haja ya kuingiza
mambo ndani ya katikati,

34
00:01:33,570 --> 00:01:35,550
kufikiri nyuma kuingizwa
aina, kuna mengi

35
00:01:35,550 --> 00:01:37,510
ya kuhama na kifafa kipengele katika huko.

36
00:01:37,510 --> 00:01:41,170
Na hivyo kama tunakwenda kuingiza
mahali popote lakini mwisho wa safu,

37
00:01:41,170 --> 00:01:43,590
kwamba pengine si kubwa sana.

38
00:01:43,590 --> 00:01:46,710
>> Vile vile, kufutwa, isipokuwa tuko
kufuta kutoka mwisho wa safu,

39
00:01:46,710 --> 00:01:49,810
pengine pia si kubwa sana kama
hatutaki kuondoka mapengo tupu,

40
00:01:49,810 --> 00:01:50,790
ambayo kwa kawaida hatuna.

41
00:01:50,790 --> 00:01:54,700
Tunataka kuondoa kipengele, na
kisha aina ya kufanya hivyo snug tena.

42
00:01:54,700 --> 00:01:57,670
Na hivyo kufuta vipengele kutoka
safu, pia si kubwa sana.

43
00:01:57,670 --> 00:01:58,820
>> Luke, ingawa, ni kubwa.

44
00:01:58,820 --> 00:02:00,920
Tuna upatikanaji random,
mara kwa mara wakati Luke.

45
00:02:00,920 --> 00:02:03,800
Sisi tu kusema saba, na sisi kwenda
kwa safu kuhamishwa saba.

46
00:02:03,800 --> 00:02:05,907
Tunasema 20, na kwenda kwa
safu kuhamishwa 20.

47
00:02:05,907 --> 00:02:07,240
Hatuna iterate hela.

48
00:02:07,240 --> 00:02:08,630
Hiyo ni nzuri sana.

49
00:02:08,630 --> 00:02:11,020
>> Arrays ni pia rahisi kutatua.

50
00:02:11,020 --> 00:02:14,040
Kila wakati sisi aliyesema kuhusu kuchagua
algorithm, kama vile uteuzi aina,

51
00:02:14,040 --> 00:02:18,820
kuingizwa aina, Bubble aina, kuunganisha
aina, sisi daima kutumika arrays ya kufanya hivyo,

52
00:02:18,820 --> 00:02:21,860
kwa sababu arrays ni rahisi sana
aina, jamaa na miundo data

53
00:02:21,860 --> 00:02:22,970
tumeona hadi sasa.

54
00:02:22,970 --> 00:02:24,320
>> Wao ni pia kiasi kidogo.

55
00:02:24,320 --> 00:02:25,695
Kuna si mengi ya nafasi ya ziada.

56
00:02:25,695 --> 00:02:29,210
Wewe tu kuweka kando hasa kama kiasi
kama unahitaji kushikilia data yako,

57
00:02:29,210 --> 00:02:30,320
na kwamba ni pretty kiasi.

58
00:02:30,320 --> 00:02:33,180
Hivyo wao ni pretty ndogo
na ufanisi katika njia hiyo.

59
00:02:33,180 --> 00:02:36,000
Lakini upande wa chini jingine, ingawa,
ni kwamba wao ni fasta katika kawaida.

60
00:02:36,000 --> 00:02:38,630
Tuna kutangaza hasa jinsi
kubwa tunataka safu yetu kuwa,

61
00:02:38,630 --> 00:02:39,940
na sisi tu kupata risasi moja katika hilo.

62
00:02:39,940 --> 00:02:41,280
Hatuwezi kukua na kuogopa hilo.

63
00:02:41,280 --> 00:02:44,582
>> Kama tunahitaji kukua au kuogopa hilo, sisi
haja ya kutangaza safu mpya kabisa,

64
00:02:44,582 --> 00:02:47,750
nakala zote za mambo ya
safu ya kwanza katika safu ya pili.

65
00:02:47,750 --> 00:02:51,410
Na kama sisi miscalculated kwamba
muda, sisi haja ya kufanya hivyo tena.

66
00:02:51,410 --> 00:02:52,760
Si kubwa sana.

67
00:02:52,760 --> 00:02:58,750
Hivyo arrays si kutupa kubadilika
kuwa na idadi kutofautiana wa mambo.

68
00:02:58,750 --> 00:03:01,320
>> Kwa orodha wanaohusishwa,
kuingizwa ni rahisi sana.

69
00:03:01,320 --> 00:03:03,290
Sisi tu upepo kwenye mbele.

70
00:03:03,290 --> 00:03:04,892
Kufutwa pia ni rahisi sana.

71
00:03:04,892 --> 00:03:06,100
Tuna kupata vipengele.

72
00:03:06,100 --> 00:03:07,270
Ambazo zinahusisha baadhi kutafuta.

73
00:03:07,270 --> 00:03:10,270
>> Lakini mara Nimepata kipengele
wewe kutafuta, wote unahitaji kufanya

74
00:03:10,270 --> 00:03:12,830
ni mabadiliko pointer,
uwezekano mbili kama una

75
00:03:12,830 --> 00:03:15,151
wanaohusishwa list-- mara mbili
orodha wanaohusishwa, rather--

76
00:03:15,151 --> 00:03:16,650
na kisha unaweza tu bure nodi.

77
00:03:16,650 --> 00:03:18,399
Huna kuhama
kila kitu karibu.

78
00:03:18,399 --> 00:03:22,090
Wewe tu mabadiliko kuyatumia mbili,
hivyo hiyo ni pretty haraka.

79
00:03:22,090 --> 00:03:23,470
>> Luke ni mbaya ingawa, sawa?

80
00:03:23,470 --> 00:03:26,280
Ili na sisi kupata
kipengele katika orodha wanaohusishwa,

81
00:03:26,280 --> 00:03:29,154
kama moja moja au mara mbili wanaohusishwa,
tuna linear tafuta yake.

82
00:03:29,154 --> 00:03:32,320
Tuna kuanza mwanzoni na
hoja ya mwisho, au kuanza mwishoni mwa hoja

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

84
00:03:33,860 --> 00:03:35,474
Hatuna random kupata tena.

85
00:03:35,474 --> 00:03:37,265
Hivyo kama sisi ni kufanya
mengi ya kutafuta, labda

86
00:03:37,265 --> 00:03:39,830
orodha wanaohusishwa sio
kabisa hivyo nzuri kwetu.

87
00:03:39,830 --> 00:03:43,750
>> Wao ni pia kweli
vigumu kutatua, sawa?

88
00:03:43,750 --> 00:03:45,666
Njia pekee unaweza
kweli aina orodha wanaohusishwa

89
00:03:45,666 --> 00:03:47,870
ni ya aina hiyo kama wewe kujenga yake.

90
00:03:47,870 --> 00:03:50,497
Lakini kama wewe aina yake kama wewe
kujenga ni, wewe ni tena

91
00:03:50,497 --> 00:03:51,830
kufanya insertions haraka tena.

92
00:03:51,830 --> 00:03:53,746
Wewe si tu tacking
mambo kwenye mbele.

93
00:03:53,746 --> 00:03:55,710
Una kupata
doa haki na kuiweka,

94
00:03:55,710 --> 00:03:57,820
na kisha kuingizwa yako
inakuwa tu kuhusu kama mbaya

95
00:03:57,820 --> 00:03:59,390
kama kuingiza ndani ya safu.

96
00:03:59,390 --> 00:04:03,130
Hivyo orodha wanaohusishwa si
kubwa sana kwa ajili ya kuchagua data.

97
00:04:03,130 --> 00:04:05,830
>> Wao ni pia pretty ndogo, ukubwa-busara.

98
00:04:05,830 --> 00:04:08,496
Doubly wanaohusishwa orodha kidogo
kubwa kuliko orodha moja moja wanaohusishwa,

99
00:04:08,496 --> 00:04:10,620
ambayo ni kubwa kidogo
kuliko arrays, lakini siyo

100
00:04:10,620 --> 00:04:13,330
kiasi kikubwa cha kupita nafasi.

101
00:04:13,330 --> 00:04:18,730
Hivyo kama nafasi ni katika premium, lakini
si malipo kweli makali,

102
00:04:18,730 --> 00:04:22,180
hii inaweza kuwa njia sahihi ya kwenda.

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

104
00:04:23,330 --> 00:04:25,850
Kuingizwa katika meza hash
ni haki moja kwa moja.

105
00:04:25,850 --> 00:04:26,980
Ni mchakato wa hatua mbili.

106
00:04:26,980 --> 00:04:30,700
Kwanza tunahitaji kukimbia takwimu zetu kupitia
heshi kupata hash kificho,

107
00:04:30,700 --> 00:04:37,550
na kisha sisi kuingiza kipengele katika
hash meza wakati huo hash kificho eneo.

108
00:04:37,550 --> 00:04:40,879
>> Kufutwa, sawa na orodha wanaohusishwa,
Ni rahisi mara moja kupata kipengele.

109
00:04:40,879 --> 00:04:43,170
Una kupata hiyo kwanza,
lakini kisha wakati wewe kufuta,

110
00:04:43,170 --> 00:04:45,128
wewe tu haja ya kubadilishana
michache ya kuyatumia,

111
00:04:45,128 --> 00:04:47,250
kama unatumia tofauti chaining.

112
00:04:47,250 --> 00:04:49,942
Kama unatumia uchunguzi,
au kama huna

113
00:04:49,942 --> 00:04:51,650
kutumia chaining wakati wote
katika hash meza yako,

114
00:04:51,650 --> 00:04:53,040
kufutwa ni kweli kweli ni rahisi.

115
00:04:53,040 --> 00:04:57,134
Wote unahitaji kufanya ni hash
data, na kisha kwenda eneo hilo.

116
00:04:57,134 --> 00:04:58,925
Na kuchukua huna
na migongano yoyote,

117
00:04:58,925 --> 00:05:01,650
wewe utakuwa na uwezo wa kufuta haraka sana.

118
00:05:01,650 --> 00:05:04,930
>> Sasa, chaguo-ndipo mambo
kupata ngumu zaidi kidogo.

119
00:05:04,930 --> 00:05:06,910
Ni kwa wastani bora
kuliko orodha wanaohusishwa.

120
00:05:06,910 --> 00:05:09,560
Kama unatumia chaining,
bado una orodha wanaohusishwa,

121
00:05:09,560 --> 00:05:13,170
ambayo ina maana bado una
search hasara orodha wanaohusishwa.

122
00:05:13,170 --> 00:05:18,390
Lakini kwa sababu wewe ni kuchukua wanaohusishwa yako
orodha na kuigawanya zaidi ya 100 au 1000

123
00:05:18,390 --> 00:05:25,380
au n vipengele katika hash meza yako, wewe ni
orodha wanaohusishwa wote ni kitu kimoja nth ukubwa.

124
00:05:25,380 --> 00:05:27,650
Wao ni wote kikubwa ndogo.

125
00:05:27,650 --> 00:05:32,080
Una n wanaohusishwa orodha badala
ya moja wanaohusishwa orodha ya ukubwa n.

126
00:05:32,080 --> 00:05:34,960
>> Na hivyo halisi ya dunia hii mara kwa mara
sababu, ambayo sisi ujumla

127
00:05:34,960 --> 00:05:39,730
wala majadiliano kuhusu muda utata, ni
haina kweli kufanya tofauti hapa.

128
00:05:39,730 --> 00:05:43,020
Hivyo chaguo-bado linear
kutafuta kama unatumia chaining,

129
00:05:43,020 --> 00:05:46,780
lakini urefu wa orodha
wewe ni kutafuta njia ya

130
00:05:46,780 --> 00:05:50,080
ni sana, muda mfupi sana kwa kulinganisha.

131
00:05:50,080 --> 00:05:52,995
Tena, kama kuchagua ni yako
lengo hapa, hash meza ya

132
00:05:52,995 --> 00:05:54,370
pengine si njia sahihi ya kwenda.

133
00:05:54,370 --> 00:05:56,830
Tu kutumia safu kama kuchagua
ni kweli ni muhimu na wewe.

134
00:05:56,830 --> 00:05:58,590
>> Na wanaweza inataka wa kawaida.

135
00:05:58,590 --> 00:06:01,640
Ni vigumu kusema kama
hash meza ni ndogo au kubwa,

136
00:06:01,640 --> 00:06:04,110
kwa sababu ni kweli inategemea
jinsi kubwa hash meza yako ni.

137
00:06:04,110 --> 00:06:07,340
Kama wewe ni tu kwenda kuwa hifadhi
mambo matano katika hash meza yako,

138
00:06:07,340 --> 00:06:10,620
na una meza hash
na mambo 10,000 ndani yake,

139
00:06:10,620 --> 00:06:12,614
pengine wewe kupoteza nafasi kubwa mno.

140
00:06:12,614 --> 00:06:15,030
Tofauti kuwa unaweza pia
na meza hash kompakt sana,

141
00:06:15,030 --> 00:06:18,720
lakini ndogo hash meza yako anapata,
tena kila moja ya orodha wanaohusishwa wale

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

143
00:06:19,220 --> 00:06:22,607
Na hivyo kuna kweli hakuna njia kufafanua
hasa ukubwa wa meza hash,

144
00:06:22,607 --> 00:06:24,440
lakini pengine salama
kusema ni kwa ujumla

145
00:06:24,440 --> 00:06:27,990
kwenda kuwa kubwa kuliko wanaohusishwa
orodha kuhifadhi data huo huo,

146
00:06:27,990 --> 00:06:30,400
lakini ndogo kuliko trie.

147
00:06:30,400 --> 00:06:32,720
>> Na inajaribu ni ya nne
ya miundo haya

148
00:06:32,720 --> 00:06:34,070
kwamba sisi tumekuwa kuzungumza juu.

149
00:06:34,070 --> 00:06:36,450
Kuingiza katika trie ni ngumu.

150
00:06:36,450 --> 00:06:38,400
Kuna mengi ya nguvu
mgao kumbukumbu,

151
00:06:38,400 --> 00:06:40,780
hasa mwanzoni,
kama wewe ni mapya ya kujenga.

152
00:06:40,780 --> 00:06:43,700
Lakini ni wakati wa mara kwa mara.

153
00:06:43,700 --> 00:06:47,690
Ni tu kipengele binadamu
hapa kwamba inafanya gumu.

154
00:06:47,690 --> 00:06:53,250
Kuwa na kukutana na pointer null, malloc
nafasi, kwenda huko, nafasi uwezekano malloc

155
00:06:53,250 --> 00:06:54,490
kutoka huko tena.

156
00:06:54,490 --> 00:06:58,880
Aina ya vitisho sababu ya
kuyatumia katika mgao wa nguvu kumbukumbu

157
00:06:58,880 --> 00:07:00,130
ni tatizo kwa wazi.

158
00:07:00,130 --> 00:07:04,550
Lakini mara moja umefanya akalipa yake, kuingizwa
kweli ilitokana rahisi,

159
00:07:04,550 --> 00:07:06,810
na ni hakika ni wakati wa mara kwa mara.

160
00:07:06,810 --> 00:07:07,680
>> Kufutwa ni rahisi.

161
00:07:07,680 --> 00:07:11,330
Wote unahitaji kufanya ni navigate chini
michache ya kuyatumia na nodi bure,

162
00:07:11,330 --> 00:07:12,420
hivyo hiyo ni nzuri sana.

163
00:07:12,420 --> 00:07:13,930
Luke pia ni pretty kufunga.

164
00:07:13,930 --> 00:07:16,780
Ni msingi tu juu ya
urefu wa data zako.

165
00:07:16,780 --> 00:07:19,924
Hivyo kama wote wa taarifa yako ni
masharti tano tabia,

166
00:07:19,924 --> 00:07:22,590
Kwa mfano, wewe ni hifadhi tano
masharti tabia katika trie yako,

167
00:07:22,590 --> 00:07:25,439
tu inachukua hatua tano
kupata nini wewe kutafuta.

168
00:07:25,439 --> 00:07:28,480
Tano ni sababu mara kwa mara, hivyo
tena, kuingizwa, kufutwa, na chaguo-

169
00:07:28,480 --> 00:07:31,670
hapa ni wakati wote mara kwa mara, kwa ufanisi.

170
00:07:31,670 --> 00:07:34,880
>> Kitu kingine ni kwamba trie yako ni
kweli aina ya tayari Iliyopangwa, sawa?

171
00:07:34,880 --> 00:07:36,800
Kwa mujibu wa jinsi tuko
kuingiza vipengele,

172
00:07:36,800 --> 00:07:40,060
kwa kwenda barua na barua ya
ufunguo, au tarakimu na tarakimu la muhimu,

173
00:07:40,060 --> 00:07:45,084
kawaida, trie yako kuishia kuwa
aina ya yamepangwa kama kujenga yake.

174
00:07:45,084 --> 00:07:47,250
Haina kweli hufanya
maana kufikiri juu ya kuchagua

175
00:07:47,250 --> 00:07:49,874
katika njia hiyo sisi kufikiri juu ya
kwa arrays, au orodha wanaohusishwa,

176
00:07:49,874 --> 00:07:51,070
au meza hash.

177
00:07:51,070 --> 00:07:54,780
Lakini katika baadhi ya hisia, yako
trie ni yamepangwa kama wewe kwenda.

178
00:07:54,780 --> 00:07:58,630
>> Upande mwingine, bila shaka, ni kwamba
trie haraka inakuwa kubwa.

179
00:07:58,630 --> 00:08:02,970
Kutoka kila hatua ya makutano, waweza
have-- kama ufunguo wako lina tarakimu,

180
00:08:02,970 --> 00:08:04,880
una 10 wengine
maeneo unaweza kwenda, ambayo

181
00:08:04,880 --> 00:08:07,490
maana yake ni kwamba kila node
ina taarifa

182
00:08:07,490 --> 00:08:11,440
kuhusu data unataka kuhifadhi
wakati huo nodi, pamoja na kuyatumia 10.

183
00:08:11,440 --> 00:08:14,430
Ambayo, juu ya CS50 IDE, ni 80 ka.

184
00:08:14,430 --> 00:08:17,220
Hivyo ni angalau 80 ka kwa
kila nodi kwamba kujenga,

185
00:08:17,220 --> 00:08:19,240
na kwamba hata kuhesabu data.

186
00:08:19,240 --> 00:08:24,950
Na kama nodes yako ni
barua badala ya tarakimu,

187
00:08:24,950 --> 00:08:27,825
sasa una 26 kuyatumia
kutoka kila eneo.

188
00:08:27,825 --> 00:08:32,007
Na 26 mara 8 pengine 200
ka, au kitu kama hicho.

189
00:08:32,007 --> 00:08:33,840
Na una mtaji
na lowercase-- unaweza

190
00:08:33,840 --> 00:08:35,381
kuona ambapo mimi nina kwenda na hii, sawa?

191
00:08:35,381 --> 00:08:37,500
Nodes wako anaweza kupata kweli
kubwa, na hivyo trie

192
00:08:37,500 --> 00:08:40,470
yenyewe, kwa ujumla, unaweza
kupata kweli kubwa, pia.

193
00:08:40,470 --> 00:08:42,630
Hivyo kama nafasi ni katika mwendo wa
premium kwenye mfumo wako,

194
00:08:42,630 --> 00:08:45,830
trie wanaweza kuwa njia sahihi ya
kwenda, ingawa faida zake nyingine

195
00:08:45,830 --> 00:08:47,780
kuja kucheza.

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

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

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