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

2
00:00:05,259 --> 00:00:08,300
Doug LLOYD: Taigi CS50, mes, kuriems
skirtingų duomenų struktūrų daug,

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

4
00:00:09,180 --> 00:00:11,420
Mes matėme masyvus ir susiję
sąrašus, maišos lentelės,

5
00:00:11,420 --> 00:00:15,210
ir nutraukė, vamzdžiai ir eilių.

6
00:00:15,210 --> 00:00:17,579
Mes taip pat sužinoti šiek tiek
apie medžių ir krūvos,

7
00:00:17,579 --> 00:00:20,120
bet tikrai jie visi tiesiog galų
gale yra Variacijos tema.

8
00:00:20,120 --> 00:00:22,840
Ten tikrai yra šie
rūšies keturių pagrindinių idėjų

9
00:00:22,840 --> 00:00:25,190
kad viskas dar gali skliautais.

10
00:00:25,190 --> 00:00:28,150
Matricos, susijusios sąrašus,
maišos lentelės, ir nutraukė.

11
00:00:28,150 --> 00:00:30,720
Ir kaip jau sakiau,
Yra variantai ant jų,

12
00:00:30,720 --> 00:00:32,720
tačiau tai yra gana
daug vyksta apibendrinti

13
00:00:32,720 --> 00:00:38,140
viskas mes ketiname kalbėti
apie šioje klasėje, kalbant apie C

14
00:00:38,140 --> 00:00:40,140
>> Bet kaip tai padaryti visa tai priemonė aukštyn, tiesa?

15
00:00:40,140 --> 00:00:44,265
Mes kalbėjome apie privalumus ir trūkumus
vienas atskirose video apie juos,

16
00:00:44,265 --> 00:00:46,390
bet ten yra numeriais
gauti mesti aplink.

17
00:00:46,390 --> 00:00:48,723
Yra bendra aikštelė
mintys vis mesti aplink.

18
00:00:48,723 --> 00:00:51,950
Pabandykime ir įtvirtinti
jį į tik vieną vietą.

19
00:00:51,950 --> 00:00:55,507
Leiskite pasverti privalumus prieš
kad trūkumai, ir apsvarstyti

20
00:00:55,507 --> 00:00:57,340
kurios duomenų struktūra
gali būti teisingas duomenys

21
00:00:57,340 --> 00:01:01,440
struktūra jūsų konkrečioje situacijoje,
bet kokios rūšies duomenų esate saugoti.

22
00:01:01,440 --> 00:01:06,625
Jūs nebūtinai visada reikia
naudoti super greitai įterpimo, ištrynimą,

23
00:01:06,625 --> 00:01:10,761
ir peržvalgos iš TRIE jei jūs tikrai
nerūpi įterpiant ir trynimas

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

25
00:01:11,260 --> 00:01:13,968
Jei jums reikia tik greitai atsitiktinis
prieiga, gal masyvas yra geriau.

26
00:01:13,968 --> 00:01:15,340
Taigi leiskite distiliuoti, kad.

27
00:01:15,340 --> 00:01:18,530
Pakalbėkime apie kiekvieną iš keturių
Pagrindiniai rūšių duomenų struktūrų

28
00:01:18,530 --> 00:01:21,720
kad mes kalbėjome apie, ir
tik pamatyti, kai jie gali būti gera,

29
00:01:21,720 --> 00:01:23,340
ir kai jie gali būti ne taip gerai.

30
00:01:23,340 --> 00:01:24,610
Taigi pradėkime su matricomis.

31
00:01:24,610 --> 00:01:27,300
Taigi įkišimo, kad tipo blogai.

32
00:01:27,300 --> 00:01:31,350
>> Įterpimas į masyvo pabaigos yra gerai,
jei mes pastatų masyvą, kaip mes einame.

33
00:01:31,350 --> 00:01:33,570
Bet jei mums reikia įterpti
elementai į centrą,

34
00:01:33,570 --> 00:01:35,550
prisiminkite įterpimą
Rūšiuoti, yra daug

35
00:01:35,550 --> 00:01:37,510
perkelia kad tilptų elementas ten.

36
00:01:37,510 --> 00:01:41,170
Ir todėl, jei mes ketiname įrašyti
kur bet masyvo pabaigos,

37
00:01:41,170 --> 00:01:43,590
tai tikriausiai ne toks didelis.

38
00:01:43,590 --> 00:01:46,710
>> Be to, išbraukta, jei mes
išbraukiant iš masyvo pabaigos,

39
00:01:46,710 --> 00:01:49,810
tikriausiai taip pat nėra toks didelis, jei
mes nenorime palikti tuščių tarpų,

40
00:01:49,810 --> 00:01:50,790
kuris paprastai darome ne.

41
00:01:50,790 --> 00:01:54,700
Mes norime, kad pašalinti elementą,
tada rūšiuoti, kad jis aptemptas dar kartą.

42
00:01:54,700 --> 00:01:57,670
Ir taip išbraukiant elementus iš
masyvas, taip pat nėra toks didelis.

43
00:01:57,670 --> 00:01:58,820
>> Ieškoti, nors yra didelis.

44
00:01:58,820 --> 00:02:00,920
Mes turime laisvą prieigą,
pastovus laikas peržvalgos.

45
00:02:00,920 --> 00:02:03,800
Mes tiesiog pasakyti septyni, ir mes einame
masyvo perkėlimo septyni.

46
00:02:03,800 --> 00:02:05,907
Mes sakome, 20, su eikite į
masyvo perkėlimas 20.

47
00:02:05,907 --> 00:02:07,240
Mes neturime kartoti visoje.

48
00:02:07,240 --> 00:02:08,630
Tai gana gerai.

49
00:02:08,630 --> 00:02:11,020
>> Masyvai taip pat yra gana lengva rūšiuoti.

50
00:02:11,020 --> 00:02:14,040
Kiekvieną kartą, kai mes kalbėjome apie rūšiavimą
algoritmas, kaip antai atrankos rūšiuoti,

51
00:02:14,040 --> 00:02:18,820
įterpimo rūšiuoti, burbulas rūšiuoti, sujungti
Rūšiuoti mes visada naudojamas matricas tai padaryti,

52
00:02:18,820 --> 00:02:21,860
nes matricos yra gana lengva
rūšiuoti, santykinis į duomenų struktūrų

53
00:02:21,860 --> 00:02:22,970
mes matėme iki šiol.

54
00:02:22,970 --> 00:02:24,320
>> Jie taip pat yra santykinai mažas.

55
00:02:24,320 --> 00:02:25,695
Yra ne daug papildomos vietos daug.

56
00:02:25,695 --> 00:02:29,210
Jūs tiesiog atidėta tiksliai taip, kaip daug
kaip jums reikia turėti savo duomenis,

57
00:02:29,210 --> 00:02:30,320
ir tai gana daug.

58
00:02:30,320 --> 00:02:33,180
Taigi jie gana mažas
ir efektyvus, kad tokiu būdu.

59
00:02:33,180 --> 00:02:36,000
Bet kita vertus, nors,
yra tai, kad jie yra fiksuotas dydžio.

60
00:02:36,000 --> 00:02:38,630
Turime pripažinti, kaip tiksliai
didelis, mes norime, kad mūsų masyvas turi būti,

61
00:02:38,630 --> 00:02:39,940
ir mes tik gauti vieną kadrą į jį.

62
00:02:39,940 --> 00:02:41,280
Mes negalime augti ir trauktis.

63
00:02:41,280 --> 00:02:44,582
>> Jei mes turime augti arba mažėti, mes
reikia pripažinti visiškai naują masyvą,

64
00:02:44,582 --> 00:02:47,750
nukopijuoti visus iš elementų
pirmasis masyvo į antrąjį masyvo.

65
00:02:47,750 --> 00:02:51,410
Ir jei mes apsiskaičiavo, kad
laikas, mes turime padaryti jį dar kartą.

66
00:02:51,410 --> 00:02:52,760
Ne toks didelis.

67
00:02:52,760 --> 00:02:58,750
Taigi matricas nesuteikia mums lanksčiai
turėti kintamas skaičių elementų.

68
00:02:58,750 --> 00:03:01,320
>> Su susietą sąrašą
įterpimas yra gana lengva.

69
00:03:01,320 --> 00:03:03,290
Mes tiesiog smeigtuko ant priekio.

70
00:03:03,290 --> 00:03:04,892
Išbraukus taip pat yra gana lengva.

71
00:03:04,892 --> 00:03:06,100
Turime rasti elementus.

72
00:03:06,100 --> 00:03:07,270
Tai apima tam tikrą paiešką.

73
00:03:07,270 --> 00:03:10,270
>> Bet kai jūs radote elementą
jūs ieškote, viskas, ką jums reikia padaryti,

74
00:03:10,270 --> 00:03:12,830
yra pakeisti žymiklį,
galbūt dvi, jei turite

75
00:03:12,830 --> 00:03:15,151
susijusiantrosios list-- dvigubai
susiję sąrašas rather--

76
00:03:15,151 --> 00:03:16,650
ir tada galite tiesiog nemokamai mazgas.

77
00:03:16,650 --> 00:03:18,399
Jūs neturite pereiti
viskas aplink.

78
00:03:18,399 --> 00:03:22,090
Jūs tiesiog pakeisti dvi rodykles,
taip, kad gana greitai.

79
00:03:22,090 --> 00:03:23,470
>> Lookup yra blogai, nors, tiesa?

80
00:03:23,470 --> 00:03:26,280
Kad galėtume rasti
elementas, susietą sąrašą

81
00:03:26,280 --> 00:03:29,154
atskirai arba dvigubai susiję,
turime linijinis ieškoti ją.

82
00:03:29,154 --> 00:03:32,320
Mes turime pradėti pradžioje ir
pereiti prie pabaigos, arba pradėti pabaigoje manevrų

83
00:03:32,320 --> 00:03:33,860
į pradžią.

84
00:03:33,860 --> 00:03:35,474
Neturime laisvą prieigą nebėra.

85
00:03:35,474 --> 00:03:37,265
Taigi, jei mes darome
daug ieškojimų, gal

86
00:03:37,265 --> 00:03:39,830
susijusiantrosios sąrašas nėra
visai taip gerai mums.

87
00:03:39,830 --> 00:03:43,750
>> Jie taip pat labai
sunku rūšiuoti, tiesa?

88
00:03:43,750 --> 00:03:45,666
Vienintelis būdas galite
tikrai rūšiuoti susietą sąrašą

89
00:03:45,666 --> 00:03:47,870
yra rūšiuoti ją, kaip jūs statyti ją.

90
00:03:47,870 --> 00:03:50,497
Bet jei jūs rūšiuoti ją kaip jus
statyti ją, jūs nebėra

91
00:03:50,497 --> 00:03:51,830
priėmimo greitai intarpais nebėra.

92
00:03:51,830 --> 00:03:53,746
Jūs neprisijungęs tik sujungdamas
viskas ant priekio.

93
00:03:53,746 --> 00:03:55,710
Turite rasti
reikiamoje vietoje įdėti ją,

94
00:03:55,710 --> 00:03:57,820
ir tada jūsų įterpimo
tampa tik apie taip blogai

95
00:03:57,820 --> 00:03:59,390
kaip įterpti į masyvą.

96
00:03:59,390 --> 00:04:03,130
Taigi, susijusios sąrašai nėra
toks didelis, rūšiavimo duomenis.

97
00:04:03,130 --> 00:04:05,830
>> Jie taip pat yra gana mažas, dydis-protingas.

98
00:04:05,830 --> 00:04:08,496
Dvigubai susiję sąrašą šiek tiek
didesnis nei pavieniui, susijusių sąrašus,

99
00:04:08,496 --> 00:04:10,620
kuris yra šiek tiek didesnis
nei masyvus, tačiau tai nėra

100
00:04:10,620 --> 00:04:13,330
didžiulis iššvaistytos erdvėje.

101
00:04:13,330 --> 00:04:18,730
Taigi, jei erdvė yra priemoka, bet
ne tikrai intensyvus priemokos,

102
00:04:18,730 --> 00:04:22,180
tai gali būti tinkamas būdas eiti.

103
00:04:22,180 --> 00:04:23,330
>> Hash lentelės.

104
00:04:23,330 --> 00:04:25,850
Įterpimas į maišos lentelė
yra gana paprasta.

105
00:04:25,850 --> 00:04:26,980
Tai dviejų etapų procesas.

106
00:04:26,980 --> 00:04:30,700
Pirmiausia, mes turime paleisti mūsų duomenis per
maišos funkcija gauti maišos kodą,

107
00:04:30,700 --> 00:04:37,550
ir tada mes įdėti elementą į
maišos lentelės tuo maišos kodo vietą.

108
00:04:37,550 --> 00:04:40,879
>> Ištrynimą, panašus į susijusio sąrašą
yra lengva, kai jums rasti elementą.

109
00:04:40,879 --> 00:04:43,170
Jūs turite jį rasti, pirma,
bet tada, kai jūs jį pašalinti,

110
00:04:43,170 --> 00:04:45,128
jums tiesiog reikia keistis
iš rodyklės pora,

111
00:04:45,128 --> 00:04:47,250
jei jūs naudojate atskirą Grupavimo.

112
00:04:47,250 --> 00:04:49,942
Jei naudojate zondavimo,
arba, jei nesate

113
00:04:49,942 --> 00:04:51,650
naudojant Grupavimo ne visi
Jūsų maišos lentelė,

114
00:04:51,650 --> 00:04:53,040
išbraukta iš tikrųjų labai paprasta.

115
00:04:53,040 --> 00:04:57,134
Viskas, ką jums reikia padaryti, tai maišos
duomenų, ir tada pereiti prie tos vietos.

116
00:04:57,134 --> 00:04:58,925
Ir jei jūs neturite
turite kokių nors susidūrimų,

117
00:04:58,925 --> 00:05:01,650
Galėsite labai greitai pašalinti.

118
00:05:01,650 --> 00:05:04,930
>> Dabar lookup yra, kur viskas
gauti šiek tiek sudėtingesnis.

119
00:05:04,930 --> 00:05:06,910
Tai vidutiniškai geriau
nei susijusių sąrašus.

120
00:05:06,910 --> 00:05:09,560
Jei naudojate Grupavimo,
jūs vis dar turite susietą sąrašą

121
00:05:09,560 --> 00:05:13,170
o tai reiškia, jūs vis dar turite
Paieška nenaudai susietą sąrašą.

122
00:05:13,170 --> 00:05:18,390
Bet kadangi jūs vartojate savo susietos
sąrašą ir padalijant jį per 100 ar 1000

123
00:05:18,390 --> 00:05:25,380
arba n elementų savo maišos lentelė, jūs
susiję sąrašai yra visi vienas n-tasis dydžio.

124
00:05:25,380 --> 00:05:27,650
Jie visi žymiai mažesnis.

125
00:05:27,650 --> 00:05:32,080
Jūs N susiję sąrašus vietoj
vieno susijusio sąrašą dydžio n.

126
00:05:32,080 --> 00:05:34,960
>> Ir todėl tai realaus pasaulio pastovus
faktorius, kurį mes paprastai

127
00:05:34,960 --> 00:05:39,730
nereikia kalbėti apie laiko sudėtingumą,
ar iš tikrųjų padaryti skirtumą čia.

128
00:05:39,730 --> 00:05:43,020
Taigi lookup yra dar linijinis
ieškoti jei jūs naudojate Grupavimo,

129
00:05:43,020 --> 00:05:46,780
bet sąrašo ilgis
esate ieškant per

130
00:05:46,780 --> 00:05:50,080
yra labai, labai trumpas, palyginus.

131
00:05:50,080 --> 00:05:52,995
Vėlgi, jei rūšiavimas yra jūsų
tikslas čia, maišos lentelės

132
00:05:52,995 --> 00:05:54,370
tikriausiai nėra tinkamas būdas eiti.

133
00:05:54,370 --> 00:05:56,830
Tiesiog naudoti masyvą, jei rūšiavimo
yra tikrai svarbu jums.

134
00:05:56,830 --> 00:05:58,590
>> Ir jie gali paleisti dydžio gamą.

135
00:05:58,590 --> 00:06:01,640
Sunku pasakyti, ar
maišos lentelė mažas ar didelis,

136
00:06:01,640 --> 00:06:04,110
nes tai tikrai priklauso nuo
kaip didelis jūsų maišos lentelė.

137
00:06:04,110 --> 00:06:07,340
Jei tik bus saugoti
Penki elementai Jūsų maišos lentelė,

138
00:06:07,340 --> 00:06:10,620
ir jūs turite maišos lentelę
su 10.000 elementų jį,

139
00:06:10,620 --> 00:06:12,614
jūs tikriausiai eikvoti daug vietos.

140
00:06:12,614 --> 00:06:15,030
Kontrastas yra taip pat galite
labai kompaktiškas maišos lenteles,

141
00:06:15,030 --> 00:06:18,720
bet mažesnis jūsų maišos lentelės gauna,
ilgiau kiekviena iš šių susijusių sąrašą

142
00:06:18,720 --> 00:06:19,220
pasireiškia.

143
00:06:19,220 --> 00:06:22,607
Ir taip ten tikrai ne būdas apibrėžti
būtent tas maišos lentelės dydis,

144
00:06:22,607 --> 00:06:24,440
bet tai tikriausiai saugus
pasakyti, kad tai apskritai

145
00:06:24,440 --> 00:06:27,990
bus didesnis nei susijusi
Sąrašas saugoti tuos pačius duomenis,

146
00:06:27,990 --> 00:06:30,400
bet mažesnis nei TRIE.

147
00:06:30,400 --> 00:06:32,720
>> Ir nutraukė yra ketvirtas
šių struktūrų

148
00:06:32,720 --> 00:06:34,070
kad mes jau kalbame apie.

149
00:06:34,070 --> 00:06:36,450
Įdėjimas į TRIE yra sudėtinga.

150
00:06:36,450 --> 00:06:38,400
Yra daug dinamiškas daug
atminties paskirstymas,

151
00:06:38,400 --> 00:06:40,780
ypač pradžioje,
kaip jūs pradedate statyti.

152
00:06:40,780 --> 00:06:43,700
Bet tai pastovus laikas.

153
00:06:43,700 --> 00:06:47,690
Tai tik žmogiškasis faktorius
čia, kad daro tai sudėtinga.

154
00:06:47,690 --> 00:06:53,250
Atsižvelgdama susidurti null žymeklį, malloc
Erdvė, ten, galbūt malloc vietos

155
00:06:53,250 --> 00:06:54,490
iš ten vėl.

156
00:06:54,490 --> 00:06:58,880
Bauginimo veiksnį Rūšiuoti
rodykles į dinaminės atminties paskirstymo

157
00:06:58,880 --> 00:07:00,130
yra kliūtis išvalyti.

158
00:07:00,130 --> 00:07:04,550
Bet kai jūs vartų, įterpimo
faktiškai yra gana paprasta,

159
00:07:04,550 --> 00:07:06,810
ir tai tikrai yra pastovus laikas.

160
00:07:06,810 --> 00:07:07,680
>> Išbraukus yra paprasta.

161
00:07:07,680 --> 00:07:11,330
Viskas, ką jums reikia padaryti, tai eikite žemyn
pora patarimų ir nemokama mazgas,

162
00:07:11,330 --> 00:07:12,420
kad gana gera.

163
00:07:12,420 --> 00:07:13,930
Lookup yra taip pat gana greitai.

164
00:07:13,930 --> 00:07:16,780
Jis grindžiamas tik
ilgis jūsų duomenis.

165
00:07:16,780 --> 00:07:19,924
Taigi, jei visi jūsų duomenis
penki charakterio įsipareigojimų,

166
00:07:19,924 --> 00:07:22,590
Pavyzdžiui, jūs saugoti penkis
charakterio įsipareigojimų Jūsų TRIE,

167
00:07:22,590 --> 00:07:25,439
tai trunka tik Penki žingsniai
rasti tai, ko ieškote.

168
00:07:25,439 --> 00:07:28,480
Penkios yra tik pastovus veiksnys, todėl
vėl, įterpimo, išbraukta, ir peržvalgos

169
00:07:28,480 --> 00:07:31,670
Čia yra visi pastovus laikas, efektyviai.

170
00:07:31,670 --> 00:07:34,880
>> Kitas dalykas yra tai, kad jūsų Trie yra
realiai natūra jau rūšiuojamos, tiesa?

171
00:07:34,880 --> 00:07:36,800
Pagal tai, kaip mes
įterpimą elementai,

172
00:07:36,800 --> 00:07:40,060
eidami raštą raidė
klavišą arba skaitmenį rakto,

173
00:07:40,060 --> 00:07:45,084
Paprastai, jūsų Trie baigiasi yra
rūšies rūšiuojami kaip jūs statyti.

174
00:07:45,084 --> 00:07:47,250
Jis tikrai ne daro
prasmės galvoti apie rūšiavimas

175
00:07:47,250 --> 00:07:49,874
tokiu pačiu būdu mes galvojame apie
Ji su matricos, ar susijusių sąrašus,

176
00:07:49,874 --> 00:07:51,070
arba maišos lentelės.

177
00:07:51,070 --> 00:07:54,780
Bet tam tikra prasme, jūsų
Trie yra rūšiuojami kaip jūs einate.

178
00:07:54,780 --> 00:07:58,630
>> Neigiama, žinoma, yra tai, kad
Trie greitai tampa didžiulis.

179
00:07:58,630 --> 00:08:02,970
Iš kiekvienos jungties taško, jums gali
have-- jei jūsų raktas susideda iš skaitmenų,

180
00:08:02,970 --> 00:08:04,880
jūs turite 10 kitų
vietų, kur galite eiti, kuri

181
00:08:04,880 --> 00:08:07,490
reiškia, kad kiekvienas mazgas
pateikiama informacija

182
00:08:07,490 --> 00:08:11,440
apie duomenų, kuriuos norite saugoti
tuo mazgu, plius 10 patarimų.

183
00:08:11,440 --> 00:08:14,430
Kuri, CS50 IDE, yra 80 baitų.

184
00:08:14,430 --> 00:08:17,220
Taigi, tai ne mažiau kaip 80 baitų
kiekvienas mazgas, kad jums sukurti,

185
00:08:17,220 --> 00:08:19,240
ir tai net ne skaičiuoti duomenis.

186
00:08:19,240 --> 00:08:24,950
Ir jei jūsų mazgai
raidės vietoj skaičių,

187
00:08:24,950 --> 00:08:27,825
dabar jūs turite 26 patarimų
iš kiekvienos vietos.

188
00:08:27,825 --> 00:08:32,007
Ir 26 kartų 8 turbūt 200
baitų, ar kažkas panašaus.

189
00:08:32,007 --> 00:08:33,840
Ir jūs turite kapitalą
ir lowercase-- galite

190
00:08:33,840 --> 00:08:35,381
pamatyti, kur aš einu su tuo, ar ne?

191
00:08:35,381 --> 00:08:37,500
Jūsų mazgai gali gauti tikrai
didelis, ir todėl Trie

192
00:08:37,500 --> 00:08:40,470
pati apskritai gali
gauti tikrai didelis, taip pat.

193
00:08:40,470 --> 00:08:42,630
Taigi, jei erdvė yra ne aukšto
įmoka į savo sistemą,

194
00:08:42,630 --> 00:08:45,830
Trie gali būti tinkamas būdas
eiti, nors kiti jo nauda

195
00:08:45,830 --> 00:08:47,780
ateiti į žaidimą.

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

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

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