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

2
00:00:05,259 --> 00:00:08,300
Doug LLOYD: Tātad CS50, mēs esam uz
daudz dažādu datu struktūras,

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

4
00:00:09,180 --> 00:00:11,420
Mēs esam redzējuši bloki, un saistīta
saraksti, un hash tabulas,

5
00:00:11,420 --> 00:00:15,210
un cenšas, skursteņi un rindas.

6
00:00:15,210 --> 00:00:17,579
Mēs arī uzzināt nedaudz
par kokiem un kaudzes,

7
00:00:17,579 --> 00:00:20,120
bet tiešām tie visi tikai beigās
galā ir variācijas par tēmu.

8
00:00:20,120 --> 00:00:22,840
Tur tiešām ir šie
veida četrām pamatidejām

9
00:00:22,840 --> 00:00:25,190
ka viss pārējais var vārīties uz leju, lai.

10
00:00:25,190 --> 00:00:28,150
Bloki, kas saistīti saraksti,
hash tabulas, un mēģina.

11
00:00:28,150 --> 00:00:30,720
Un kā jau teicu, tur
ir variācijas par tiem,

12
00:00:30,720 --> 00:00:32,720
bet tas ir diezgan
daudz kas notiek apkopot

13
00:00:32,720 --> 00:00:38,140
viss, ko mēs ejam, lai runātu
par šajā klasē ziņā C.

14
00:00:38,140 --> 00:00:40,140
>> Bet kā tie visi pasākums up, labi?

15
00:00:40,140 --> 00:00:44,265
Mēs esam runājuši par plusi un mīnusi
Katras atsevišķās video par to,

16
00:00:44,265 --> 00:00:46,390
bet tur ir daudz skaitļu
kļūst izmet apkārt.

17
00:00:46,390 --> 00:00:48,723
Tur ir daudz vispārējs
domas kļūst izmet apkārt.

18
00:00:48,723 --> 00:00:51,950
Pamēģināsim un konsolidēt
to tikai vienā vietā.

19
00:00:51,950 --> 00:00:55,507
Pieņemsim nosver plusi pret
mīnusi, un apsvērt

20
00:00:55,507 --> 00:00:57,340
kas datu struktūra
varētu būt pareizā dati

21
00:00:57,340 --> 00:01:01,440
struktūra jūsu konkrēto situāciju,
jebkāda veida datu jūs glabāšanai.

22
00:01:01,440 --> 00:01:06,625
Jums nav obligāti vienmēr vajag
izmantot super ātru ievietošanas, dzēšanu,

23
00:01:06,625 --> 00:01:10,761
un lookup par TRIE ja jums tiešām
nerūp ievietošanas un dzēšana

24
00:01:10,761 --> 00:01:11,260
pārāk daudz.

25
00:01:11,260 --> 00:01:13,968
Ja jums ir nepieciešams tikai ātri izlases
Pieeja, varbūt masīvs ir labāka.

26
00:01:13,968 --> 00:01:15,340
Tātad, pieņemsim, ka dedzināt.

27
00:01:15,340 --> 00:01:18,530
Parunāsim par katru no četriem
galvenie veidi datu struktūras

28
00:01:18,530 --> 00:01:21,720
ka mēs esam runājuši par, un
tikai redzēt, kad tie varētu būt labs,

29
00:01:21,720 --> 00:01:23,340
un kad tie varētu nebūt tik labi.

30
00:01:23,340 --> 00:01:24,610
Tāpēc sāksim ar masīviem.

31
00:01:24,610 --> 00:01:27,300
Tātad ievietošanas, tas ir sava veida slikti.

32
00:01:27,300 --> 00:01:31,350
>> Ievietošana beigās masīva ir OK,
ja mēs ēkā masīvs, kā mums iet.

33
00:01:31,350 --> 00:01:33,570
Bet, ja mums ir nepieciešams, lai ievietotu
elementi uz centru,

34
00:01:33,570 --> 00:01:35,550
domāju, ka atpakaļ uz ievietošanas
kārtot, tur ir daudz

35
00:01:35,550 --> 00:01:37,510
no novirzot lai ietilptu elements tur.

36
00:01:37,510 --> 00:01:41,170
Un tāpēc, ja mēs ejam, lai ievietotu
jebkur bet gala no masīva,

37
00:01:41,170 --> 00:01:43,590
tas ir iespējams, nav tik liels.

38
00:01:43,590 --> 00:01:46,710
>> Tāpat, dzēšanu, ja vien mēs esam
svītrot no beigām masīva,

39
00:01:46,710 --> 00:01:49,810
Ir iespējams arī nav tik liels, ja
mēs negribam atstāt tukšus nepilnības,

40
00:01:49,810 --> 00:01:50,790
kas parasti mums nav.

41
00:01:50,790 --> 00:01:54,700
Mēs vēlamies, lai noņemtu elementu, un
tad veida padara akurāti vēlreiz.

42
00:01:54,700 --> 00:01:57,670
Un tā dzēšot elementus no
masīvs, arī ne tik liels.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, tomēr ir liels.

44
00:01:58,820 --> 00:02:00,920
Mums ir izlases piekļūt,
konstante laiks lookup.

45
00:02:00,920 --> 00:02:03,800
Mēs vienkārši sakām septiņiem, un mēs ejam
ar masīvu pārvietošanu septiņiem.

46
00:02:03,800 --> 00:02:05,907
Mēs sakām 20, ar iet uz
masīvs pārvietošana 20.

47
00:02:05,907 --> 00:02:07,240
Mums nav atkārtot pāri.

48
00:02:07,240 --> 00:02:08,630
Tas ir diezgan labs.

49
00:02:08,630 --> 00:02:11,020
>> Masīvi ir arī salīdzinoši viegli sakārtot.

50
00:02:11,020 --> 00:02:14,040
Katru reizi, kad mēs runājām par šķirošanu
algoritmu, piemēram, atlases veida,

51
00:02:14,040 --> 00:02:18,820
ievietošanas kārtot, burbulis kārtot, apvienot
kārtot, mēs vienmēr izmanto blokus, lai to izdarītu,

52
00:02:18,820 --> 00:02:21,860
jo masīvi ir diezgan viegli
kārtot, salīdzinot ar datu struktūru

53
00:02:21,860 --> 00:02:22,970
mēs esam redzējuši līdz šim.

54
00:02:22,970 --> 00:02:24,320
>> Viņi arī salīdzinoši neliels.

55
00:02:24,320 --> 00:02:25,695
Tur nav daudz papildu telpas.

56
00:02:25,695 --> 00:02:29,210
Jūs vienkārši atcelt tieši tik daudz,
kā jums ir nepieciešams, lai noturētu savus datus,

57
00:02:29,210 --> 00:02:30,320
un tas ir diezgan daudz to.

58
00:02:30,320 --> 00:02:33,180
Tātad viņi diezgan mazs
un efektīvu šādā veidā.

59
00:02:33,180 --> 00:02:36,000
Bet vēl viens negatīvie, lai gan,
ir tā, ka tie ir noteikti lieluma.

60
00:02:36,000 --> 00:02:38,630
Mums ir jādeklarē, kā tieši
big mēs vēlamies, lai mūsu masīvs būt,

61
00:02:38,630 --> 00:02:39,940
un mēs tikai iegūt vienu shot pie tā.

62
00:02:39,940 --> 00:02:41,280
Mēs nevaram augt un sarauties to.

63
00:02:41,280 --> 00:02:44,582
>> Ja mums ir nepieciešams, lai augt vai sarukt, mēs
nepieciešams deklarēt pilnīgi jaunu masīvu,

64
00:02:44,582 --> 00:02:47,750
kopēt visu elementu
pirmais masīvs uz otro masīvs.

65
00:02:47,750 --> 00:02:51,410
Un, ja mēs nepareizi, ka
laiks, mums ir nepieciešams to darīt atkal.

66
00:02:51,410 --> 00:02:52,760
Ne tik liels.

67
00:02:52,760 --> 00:02:58,750
Tātad bloki nedod mums elastību
ir mainīgas skaitu elementu.

68
00:02:58,750 --> 00:03:01,320
>> Ar saistītajā sarakstā,
ievietošana ir diezgan viegli.

69
00:03:01,320 --> 00:03:03,290
Mēs tikko sadiegšana uz priekšu.

70
00:03:03,290 --> 00:03:04,892
Dzēšana ir arī diezgan viegli.

71
00:03:04,892 --> 00:03:06,100
Mums ir jāatrod elementus.

72
00:03:06,100 --> 00:03:07,270
Tas ietver daži meklē.

73
00:03:07,270 --> 00:03:10,270
>> Bet tad, kad jūs esat atradis elements
jūs meklējat, viss, kas jums jādara,

74
00:03:10,270 --> 00:03:12,830
ir mainīt rādītāju,
iespējami divi, ja Jums ir

75
00:03:12,830 --> 00:03:15,151
saistītais list-- divkārt
saistīts saraksts, rather--

76
00:03:15,151 --> 00:03:16,650
un tad jūs varat vienkārši atbrīvot mezglā.

77
00:03:16,650 --> 00:03:18,399
Jums nav novirzīt
viss apkārt.

78
00:03:18,399 --> 00:03:22,090
Jūs vienkārši mainīt divas norādes,
tā ka ir diezgan ātri.

79
00:03:22,090 --> 00:03:23,470
>> Lookup ir slikti, lai gan, vai ne?

80
00:03:23,470 --> 00:03:26,280
Lai mēs varētu atrast
elements saistītajā sarakstā,

81
00:03:26,280 --> 00:03:29,154
vai atsevišķi vai divkārt saistīti,
mums ir lineāra meklēt to.

82
00:03:29,154 --> 00:03:32,320
Mums ir jāsāk sākumā un
pārvietot beigas, vai sākt gada beigās kustībā

83
00:03:32,320 --> 00:03:33,860
uz sākumu.

84
00:03:33,860 --> 00:03:35,474
Mums nav brīvpieejas vairs.

85
00:03:35,474 --> 00:03:37,265
Tātad, ja mēs darām
no meklēšanu daudz, varbūt

86
00:03:37,265 --> 00:03:39,830
saistītais saraksts nav
gluži tik labu mums.

87
00:03:39,830 --> 00:03:43,750
>> Viņi arī patiešām
grūti atrisināt, vai ne?

88
00:03:43,750 --> 00:03:45,666
Vienīgais veids, kā jūs varat
tiešām kārtot saistīts sarakstu

89
00:03:45,666 --> 00:03:47,870
ir, lai sakārtotu to, kā jūs būvēt to.

90
00:03:47,870 --> 00:03:50,497
Bet, ja jūs sakārtotu to, kā jūs
būvēt to, jūs vairs

91
00:03:50,497 --> 00:03:51,830
padarot ātri ievietošanas vairs.

92
00:03:51,830 --> 00:03:53,746
Jūs esat ne tikai lokalizācijas
lietas uz priekšu.

93
00:03:53,746 --> 00:03:55,710
Jums ir atrast
tiesības uz vietas, lai to,

94
00:03:55,710 --> 00:03:57,820
un tad jūsu ievietošanas
kļūst tikai par tik slikti

95
00:03:57,820 --> 00:03:59,390
kā ievietojot masīva.

96
00:03:59,390 --> 00:04:03,130
Tātad saistīti saraksti nav
tik liels, lai šķirošanas datus.

97
00:04:03,130 --> 00:04:05,830
>> Viņi arī ir diezgan maza, izmēra ziņā.

98
00:04:05,830 --> 00:04:08,496
Divkārt saistīts sarakstu nedaudz
lielāks nekā atsevišķi saistītas sarakstus,

99
00:04:08,496 --> 00:04:10,620
kas ir nedaudz lielāks
nekā blokiem, bet tas nav

100
00:04:10,620 --> 00:04:13,330
milzīgs daudzums izšķērdēta kosmosa.

101
00:04:13,330 --> 00:04:18,730
Tātad, ja telpa ir piemaksa, bet
nav īsti intensīva piemaksa,

102
00:04:18,730 --> 00:04:22,180
tas varētu būt pareizais ceļš.

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

104
00:04:23,330 --> 00:04:25,850
Ievietošanai hash tabulu
ir diezgan vienkārši.

105
00:04:25,850 --> 00:04:26,980
Tas ir divpakāpju process.

106
00:04:26,980 --> 00:04:30,700
Vispirms mums ir nepieciešams, lai palaistu mūsu datus, izmantojot
hash funkciju, lai iegūtu hash kodu,

107
00:04:30,700 --> 00:04:37,550
un tad mēs ievietojiet elementu Into
hash tabulu šajā hash kodu vietas.

108
00:04:37,550 --> 00:04:40,879
>> Dzēšana, līdzīgi saistīta sarakstā,
ir viegli, kad jūs atrast elementu.

109
00:04:40,879 --> 00:04:43,170
Jums ir jāatrod tā pirmo reizi,
bet tad, kad jūs to izdzēst,

110
00:04:43,170 --> 00:04:45,128
Jums vienkārši nepieciešams, lai apmainītos
pāris norādes,

111
00:04:45,128 --> 00:04:47,250
ja jūs izmantojat atsevišķu ķēžu rādītāju.

112
00:04:47,250 --> 00:04:49,942
Ja jūs izmantojat zondēšana,
vai, ja jūs neesat

113
00:04:49,942 --> 00:04:51,650
izmantojot Ķēžu vispār
Jūsu hash tabulu,

114
00:04:51,650 --> 00:04:53,040
dzēšana ir tiešām ļoti viegli.

115
00:04:53,040 --> 00:04:57,134
Viss, kas jums jādara, ir hash
dati, un tad doties uz šo vietu.

116
00:04:57,134 --> 00:04:58,925
Un pieņemot, ka jums nav
ir kādas sadursmes,

117
00:04:58,925 --> 00:05:01,650
jūs varēsiet dzēst ļoti ātri.

118
00:05:01,650 --> 00:05:04,930
>> Tagad, lookup ir, ja lietas
saņemt nedaudz sarežģītāka.

119
00:05:04,930 --> 00:05:06,910
Tas ir vidēji labāk
nekā saistītas sarakstus.

120
00:05:06,910 --> 00:05:09,560
Ja jūs izmantojat Ķēžu,
jums vēl joprojām ir saistīts sarakstu,

121
00:05:09,560 --> 00:05:13,170
kas nozīmē, ka jūs vēl joprojām ir
meklēšana kaitējot ir saistīts sarakstu.

122
00:05:13,170 --> 00:05:18,390
Bet tāpēc, ka jūs lietojat savu saistīta
saraksts un sadalot to pa 100 vai 1000

123
00:05:18,390 --> 00:05:25,380
vai n elementi jūsu hash tabulu, jūs esat
saistītie saraksti ir viss viens n lielumu.

124
00:05:25,380 --> 00:05:27,650
Viņi visi ir ievērojami mazāka.

125
00:05:27,650 --> 00:05:32,080
Jūs esat n saistīts sarakstus vietā
Vienas saistīta saraksta lieluma n.

126
00:05:32,080 --> 00:05:34,960
>> Un tā tas reālās pasaules konstante
faktors, kas Parasti mēs

127
00:05:34,960 --> 00:05:39,730
nerunā par savlaicīgas sarežģītību, to
tas tiešām kaut ko mainīt šeit.

128
00:05:39,730 --> 00:05:43,020
Tātad lookup joprojām ir lineārs
meklēt, ja jūs izmantojat Ķēžu,

129
00:05:43,020 --> 00:05:46,780
bet garums saraksta
jūs meklējat, izmantojot

130
00:05:46,780 --> 00:05:50,080
ir ļoti, ļoti īss, salīdzinot.

131
00:05:50,080 --> 00:05:52,995
Atkal, ja šķirošana ir jūsu
mērķis šeit, hash tabulas

132
00:05:52,995 --> 00:05:54,370
iespējams, nav pareizais veids, kā iet.

133
00:05:54,370 --> 00:05:56,830
Just izmantot masīvu ja šķirošanas
ir ļoti svarīgi, lai jums.

134
00:05:56,830 --> 00:05:58,590
>> Un viņi var palaist toņkārta no izmēra.

135
00:05:58,590 --> 00:06:01,640
Ir grūti pateikt, vai
hash tabulā ir mazs vai liels,

136
00:06:01,640 --> 00:06:04,110
jo tas tiešām ir atkarīgs
cik liels jūsu hash tabula ir.

137
00:06:04,110 --> 00:06:07,340
Ja jūs tikai būs uzglabāšanai
pieci elementi jūsu hash tabulu,

138
00:06:07,340 --> 00:06:10,620
un jums ir hash tabulu
ar 10000 elementiem tajā,

139
00:06:10,620 --> 00:06:12,614
jūs, iespējams, izšķērdēt daudz vietas.

140
00:06:12,614 --> 00:06:15,030
Kontrasts ir Varat arī
ir ļoti kompaktas hash tabulas,

141
00:06:15,030 --> 00:06:18,720
bet mazākais jūsu hash tabulu izpaužas,
jo ilgāk katru no šiem sarakstiem, kas saistītas

142
00:06:18,720 --> 00:06:19,220
izpaužas.

143
00:06:19,220 --> 00:06:22,607
Un tā tur tiešām nav veids, kā definēt
tieši lielums hash tabulu,

144
00:06:22,607 --> 00:06:24,440
bet tas ir iespējams, droši
teikt, tas ir vispār

145
00:06:24,440 --> 00:06:27,990
būs lielāks nekā saistīta
saraksts uzglabājot to pašu datu,

146
00:06:27,990 --> 00:06:30,400
bet mazāka nekā TRIE.

147
00:06:30,400 --> 00:06:32,720
>> Un cenšas ir ceturtais
Šo struktūru

148
00:06:32,720 --> 00:06:34,070
ka mēs esam runājuši par.

149
00:06:34,070 --> 00:06:36,450
Ievietojot uz TRIE ir sarežģīta.

150
00:06:36,450 --> 00:06:38,400
Tur ir daudz dinamisku
atmiņas sadalījumu,

151
00:06:38,400 --> 00:06:40,780
īpaši sākumā,
kā jūs sāk būvēt.

152
00:06:40,780 --> 00:06:43,700
Bet tas ir nemainīgs laiks.

153
00:06:43,700 --> 00:06:47,690
Tas ir tikai cilvēka faktors
šeit, kas padara to grūts.

154
00:06:47,690 --> 00:06:53,250
Ņemot sastapties null rādītāju, malloc
telpa, iet tur, iespējams, malloc telpa

155
00:06:53,250 --> 00:06:54,490
no turienes atkal.

156
00:06:54,490 --> 00:06:58,880
Par iebiedēšana faktora veida
Norādes dinamisku atmiņas sadalījumu

157
00:06:58,880 --> 00:07:00,130
ir šķērslis, lai notīrītu.

158
00:07:00,130 --> 00:07:04,550
Bet tad, kad jūs esat noskaidroti to, ievietošanas
faktiski ir diezgan vienkārši,

159
00:07:04,550 --> 00:07:06,810
un tas, protams, ir nemainīgs laika.

160
00:07:06,810 --> 00:07:07,680
>> Dzēšana ir viegli.

161
00:07:07,680 --> 00:07:11,330
Viss, kas jums jādara, ir orientēties uz leju
Pāris norādes un bezmaksas mezglā,

162
00:07:11,330 --> 00:07:12,420
tā ka ir diezgan laba.

163
00:07:12,420 --> 00:07:13,930
Lookup ir arī diezgan ātri.

164
00:07:13,930 --> 00:07:16,780
Tas ir balstīts tikai uz
garums jūsu datiem.

165
00:07:16,780 --> 00:07:19,924
Tātad, ja visi jūsu dati ir
pieci rakstzīmju virknes,

166
00:07:19,924 --> 00:07:22,590
Piemēram, jūs uzglabātu pieci
rakstzīmju virknes jūsu TRIE,

167
00:07:22,590 --> 00:07:25,439
tas aizņem tikai pieci soļi, lai
atrast to, ko jūs meklējat.

168
00:07:25,439 --> 00:07:28,480
Pieci ir tikai nemainīgs faktors, tāpēc
atkal, ievietošana, dzēšana, un lookup

169
00:07:28,480 --> 00:07:31,670
Šeit ir visi nemainīgs laiku, efektīvi.

170
00:07:31,670 --> 00:07:34,880
>> Vēl viena lieta ir, ka jūsu trie ir
faktiski veida jau sakārtots, labi?

171
00:07:34,880 --> 00:07:36,800
Pamatojoties uz to, kā mēs esam
ievietojot elementi,

172
00:07:36,800 --> 00:07:40,060
dodoties burtu pēc burta
atslēgu, vai cipars ar ciparu taustiņu,

173
00:07:40,060 --> 00:07:45,084
parasti, jūsu trie beidzas ar to,
veida sakārtoti kā jūs veidot to.

174
00:07:45,084 --> 00:07:47,250
Tas nav īsti padara
jēga domāt par šķirošanas

175
00:07:47,250 --> 00:07:49,874
tādā pašā veidā, kā mēs domājam par
tas ar masīviem, vai saistīti sarakstiem,

176
00:07:49,874 --> 00:07:51,070
vai hash tabulas.

177
00:07:51,070 --> 00:07:54,780
Bet savā ziņā, jūsu
trie ir sakārtots, kā jums iet.

178
00:07:54,780 --> 00:07:58,630
>> Negatīvie, protams, ir tas, ka
trie strauji kļūst milzīgs.

179
00:07:58,630 --> 00:08:02,970
No katra krustojuma vietā, jūs varētu
have-- ja jūsu galvenais sastāv no cipariem,

180
00:08:02,970 --> 00:08:04,880
Jums ir 10 citas
vietas, jūs varat iet, kas

181
00:08:04,880 --> 00:08:07,490
nozīmē, ka katrā mezglā
satur informāciju

182
00:08:07,490 --> 00:08:11,440
par datiem, jūs vēlaties, lai saglabātu
šajā mezglā, plus 10 norādes.

183
00:08:11,440 --> 00:08:14,430
Kas, CS50 IDE, ir 80 baiti.

184
00:08:14,430 --> 00:08:17,220
Tātad, tas ir vismaz 80 baiti uz
katrs mezgls, ka jūs izveidojat,

185
00:08:17,220 --> 00:08:19,240
un tas nav pat skaitīšanas datus.

186
00:08:19,240 --> 00:08:24,950
Un, ja jūsu mezgli ir
burti nevis cipari,

187
00:08:24,950 --> 00:08:27,825
Tagad jums ir 26 norādes
No katras vietas.

188
00:08:27,825 --> 00:08:32,007
Un 26 reizes 8, iespējams, ir 200
baiti, vai kaut kas tamlīdzīgs.

189
00:08:32,007 --> 00:08:33,840
Un jums ir kapitāls
un lowercase-- jūs varat

190
00:08:33,840 --> 00:08:35,381
redzēt, kur es esmu, kas ar šo, labi?

191
00:08:35,381 --> 00:08:37,500
Jūsu mezgli var iegūt patiešām
liels, un tā trie

192
00:08:37,500 --> 00:08:40,470
pati, kopumā var
riktīgi liels, too.

193
00:08:40,470 --> 00:08:42,630
Tātad, ja telpa ir liela
premium jūsu sistēmā,

194
00:08:42,630 --> 00:08:45,830
trie varētu nebūt pareizais veids, kā
iet, pat ja citi tās priekšrocības

195
00:08:45,830 --> 00:08:47,780
stāties spēlēt.

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

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

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