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

2
00:00:05,259 --> 00:00:08,300
Doug LLOYD: Tako je u CS50 smo pokriveni
puno različitih struktura podataka,

3
00:00:08,300 --> 00:00:09,180
zar ne?

4
00:00:09,180 --> 00:00:11,420
Vidjeli smo polja i povezane
liste, i hash tablice,

5
00:00:11,420 --> 00:00:15,210
i napad, masa i redova.

6
00:00:15,210 --> 00:00:17,579
Također ćemo naučiti nešto
o drveću i hrpe,

7
00:00:17,579 --> 00:00:20,120
ali stvarno to sve samo kraj
gore bitak varijacije na temu.

8
00:00:20,120 --> 00:00:22,840
Tu stvarno su ovi
vrsta četiri osnovna ideja

9
00:00:22,840 --> 00:00:25,190
da je sve ostalo može svesti na.

10
00:00:25,190 --> 00:00:28,150
Polja, povezani popisi,
hash tablice, i napad.

11
00:00:28,150 --> 00:00:30,720
I kao što sam rekao, ne postoji
su varijacije na njih,

12
00:00:30,720 --> 00:00:32,720
ali to je prilično
koliko će sažeti

13
00:00:32,720 --> 00:00:38,140
sve ćemo razgovarati
o tome u ovom razredu u odnosu na C.

14
00:00:38,140 --> 00:00:40,140
>> Ali kako to oni sve mjere gore, zar ne?

15
00:00:40,140 --> 00:00:44,265
Razgovarali smo o pro i kontra
svakog u zasebne videa na njih,

16
00:00:44,265 --> 00:00:46,390
ali ima puno brojeva
dobivanje bačena okolo.

17
00:00:46,390 --> 00:00:48,723
Postoji mnogo općenito
misli dobivanje bačena okolo.

18
00:00:48,723 --> 00:00:51,950
Pokušajmo i učvrstiti
je na jednom mjestu.

19
00:00:51,950 --> 00:00:55,507
Idemo vagati prednosti protiv
kontra, i uzeti u obzir

20
00:00:55,507 --> 00:00:57,340
koja struktura podataka
bi mogao biti pravi podaci

21
00:00:57,340 --> 00:01:01,440
Struktura za Vašu situaciju,
bez obzira na vrstu podataka ste pohranu.

22
00:01:01,440 --> 00:01:06,625
Vi ne moraju uvijek treba
koristite super brzi umetanja, brisanja,

23
00:01:06,625 --> 00:01:10,761
i pretraživanja od Trie ako stvarno
ne brinuti se o umetanje i brisanje

24
00:01:10,761 --> 00:01:11,260
previše.

25
00:01:11,260 --> 00:01:13,968
Ako vam je potrebna samo brzo slučajnim
pristup, možda niz je bolje.

26
00:01:13,968 --> 00:01:15,340
Tako ćemo destilirati to.

27
00:01:15,340 --> 00:01:18,530
Razgovarajmo o svakom od četiri
glavne vrste struktura podataka

28
00:01:18,530 --> 00:01:21,720
da smo razgovarali o tome, i
samo vidjeti kad bi moglo biti dobro,

29
00:01:21,720 --> 00:01:23,340
a kad oni ne bi mogli biti tako dobri.

30
00:01:23,340 --> 00:01:24,610
Tako ćemo početi s polja.

31
00:01:24,610 --> 00:01:27,300
Dakle umetanje, to je vrsta loše.

32
00:01:27,300 --> 00:01:31,350
>> Umetanje na kraju niza je u redu,
ako gradimo niz kako idemo.

33
00:01:31,350 --> 00:01:33,570
Ali ako moramo umetnuti
elemente u sredini,

34
00:01:33,570 --> 00:01:35,550
mislim natrag na umetanje
vrsta, tu je mnogo

35
00:01:35,550 --> 00:01:37,510
prebacivanja da stane element tamo.

36
00:01:37,510 --> 00:01:41,170
I tako, ako ćemo umetnuti
nigdje, ali kraj niza,

37
00:01:41,170 --> 00:01:43,590
to vjerojatno nije tako velika.

38
00:01:43,590 --> 00:01:46,710
>> Slično tome, brisanje, osim ako smo
brisanje s kraja niza,

39
00:01:46,710 --> 00:01:49,810
vjerojatno i nije tako velik ako
ne želimo ostaviti prazne praznine,

40
00:01:49,810 --> 00:01:50,790
što obično nemamo.

41
00:01:50,790 --> 00:01:54,700
Želimo ukloniti element i
onda nekako bi ga opet lagodan.

42
00:01:54,700 --> 00:01:57,670
I tako brisanje elemenata iz
niz, također nije tako velika.

43
00:01:57,670 --> 00:01:58,820
>> Potraži, iako je super.

44
00:01:58,820 --> 00:02:00,920
Imamo slučajni pristup,
vremenska konstanta pretraživanja.

45
00:02:00,920 --> 00:02:03,800
Mi samo reći sedam, a idemo
na polja preseljenja sedam.

46
00:02:03,800 --> 00:02:05,907
Kažemo 20, s pokretu na
Niz preseljenje 20.

47
00:02:05,907 --> 00:02:07,240
Mi ne moramo ponoviti preko.

48
00:02:07,240 --> 00:02:08,630
To je vrlo dobro.

49
00:02:08,630 --> 00:02:11,020
>> Nizovi su također relativno lako riješiti.

50
00:02:11,020 --> 00:02:14,040
Svaki put kad smo razgovarali o sortiranjem
algoritam, kao što su odabir vrste,

51
00:02:14,040 --> 00:02:18,820
umetanje vrsta, mjehurić sortirati, spajanje
vrsta, uvijek koristiti nizove to učiniti,

52
00:02:18,820 --> 00:02:21,860
jer polja su prilično lako
vrsta, u odnosu na strukture podataka

53
00:02:21,860 --> 00:02:22,970
smo do sada vidjeli.

54
00:02:22,970 --> 00:02:24,320
>> Oni su također relativno mali.

55
00:02:24,320 --> 00:02:25,695
Nema puno dodatnog prostora.

56
00:02:25,695 --> 00:02:29,210
Vi samo staviti na stranu točno koliko
što vam je potrebno da držite svoje podatke,

57
00:02:29,210 --> 00:02:30,320
i to je prilično zadovoljni.

58
00:02:30,320 --> 00:02:33,180
Dakle, oni su prilično male
i učinkovito na taj način.

59
00:02:33,180 --> 00:02:36,000
Ali još jedna mana, ipak,
da su fiksne veličine.

60
00:02:36,000 --> 00:02:38,630
Moramo proglasiti točno kako
Veliki želimo da naša niz biti,

61
00:02:38,630 --> 00:02:39,940
a mi samo dobiti jedan metak u njega.

62
00:02:39,940 --> 00:02:41,280
Ne možemo rasti i smanjiti.

63
00:02:41,280 --> 00:02:44,582
>> Ako trebamo rasti ili ga smanjiti, mi
morati proglasiti posve novi niz,

64
00:02:44,582 --> 00:02:47,750
kopirati sve elemente
Prvi niz u drugi niz.

65
00:02:47,750 --> 00:02:51,410
A ako smo pogrešno da
vrijeme, moramo to učiniti opet.

66
00:02:51,410 --> 00:02:52,760
Ne tako velika.

67
00:02:52,760 --> 00:02:58,750
Dakle polja ne daju nam fleksibilnost
da ima varijabilnu broj elemenata.

68
00:02:58,750 --> 00:03:01,320
>> S popisa povezani,
umetanje je prilično jednostavan.

69
00:03:01,320 --> 00:03:03,290
Upravo smo sklepati na pročelju.

70
00:03:03,290 --> 00:03:04,892
Brisanje je prilično jednostavan.

71
00:03:04,892 --> 00:03:06,100
Moramo pronaći elemente.

72
00:03:06,100 --> 00:03:07,270
To uključuje neki koji traži.

73
00:03:07,270 --> 00:03:10,270
>> No, nakon što ste pronašli element
tražiš, sve što trebate učiniti

74
00:03:10,270 --> 00:03:12,830
je promijeniti pokazivač,
eventualno dva ako imate

75
00:03:12,830 --> 00:03:15,151
je povezani list-- dvostrano
povezana lista, rather--

76
00:03:15,151 --> 00:03:16,650
a onda možete samo osloboditi čvor.

77
00:03:16,650 --> 00:03:18,399
Ne morate da pomak
sve oko.

78
00:03:18,399 --> 00:03:22,090
Vi samo promijeniti dva pokazivača,
tako da je prilično brzo.

79
00:03:22,090 --> 00:03:23,470
>> Potraži je loše ipak, zar ne?

80
00:03:23,470 --> 00:03:26,280
Da bi nam je pronaći
element u popisu povezane,

81
00:03:26,280 --> 00:03:29,154
bilo pojedinačno ili dvostruko povezani,
moramo linearno ga traži.

82
00:03:29,154 --> 00:03:32,320
Moramo početi na početku i
premjestiti kraj ili početak na kraju pokretu

83
00:03:32,320 --> 00:03:33,860
na početak.

84
00:03:33,860 --> 00:03:35,474
Nemamo slučajni pristup više.

85
00:03:35,474 --> 00:03:37,265
Dakle, ako mi radite
puno traženja, možda

86
00:03:37,265 --> 00:03:39,830
popis povezana nije
toliko dobro za nas.

87
00:03:39,830 --> 00:03:43,750
>> Oni su također jako
teško sortiranje, zar ne?

88
00:03:43,750 --> 00:03:45,666
Jedini način možete
stvarno sortirati popis povezan

89
00:03:45,666 --> 00:03:47,870
je to riješiti onako kako ga izgraditi.

90
00:03:47,870 --> 00:03:50,497
Ali ako to riješiti kao ti
izgraditi ga, ti si više ne

91
00:03:50,497 --> 00:03:51,830
izradu brzih umetanja više.

92
00:03:51,830 --> 00:03:53,746
Vi ne samo letanja
stvari na prednji.

93
00:03:53,746 --> 00:03:55,710
Morate pronaći
Pravo mjesto za staviti,

94
00:03:55,710 --> 00:03:57,820
a zatim vaš umetanje
postaje samo o loše

95
00:03:57,820 --> 00:03:59,390
kao umetanja u nizu.

96
00:03:59,390 --> 00:04:03,130
Tako povezani popisi nisu
pa super za sortiranje podataka.

97
00:04:03,130 --> 00:04:05,830
>> Oni su također prilično male, veličina mudar.

98
00:04:05,830 --> 00:04:08,496
Dvostruko povezane liste malo
veći od pojedinačno povezanim popisima,

99
00:04:08,496 --> 00:04:10,620
koji su nešto veći
od polja, ali to nije

100
00:04:10,620 --> 00:04:13,330
ogromna količina izgubljenog prostora.

101
00:04:13,330 --> 00:04:18,730
Dakle, ako je prostor na premiju, ali
ne stvarno intenzivno premija,

102
00:04:18,730 --> 00:04:22,180
to može biti pravi način da ide.

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

104
00:04:23,330 --> 00:04:25,850
Ubacivanje u hash tablici
je prilično jednostavan.

105
00:04:25,850 --> 00:04:26,980
To je proces u dva koraka.

106
00:04:26,980 --> 00:04:30,700
Prvo moramo pokrenuti naše podatke preko
hash funkcija dobiti hash kod,

107
00:04:30,700 --> 00:04:37,550
a onda smo umetnuti element u
hash tablicu na toj lokaciji hash code.

108
00:04:37,550 --> 00:04:40,879
>> Brisanje, slično povezane liste,
je jednostavno jednom kad pronađete element.

109
00:04:40,879 --> 00:04:43,170
Morate pronaći prvi,
ali onda kada ga izbrisati,

110
00:04:43,170 --> 00:04:45,128
vi samo trebate zamijeniti
par pokazivača,

111
00:04:45,128 --> 00:04:47,250
ako koristite zasebnu ulančavanje.

112
00:04:47,250 --> 00:04:49,942
Ako koristite sondiranja,
ili ako niste

113
00:04:49,942 --> 00:04:51,650
pomoću ulančavanje na sve
u svom hash tablici,

114
00:04:51,650 --> 00:04:53,040
brisanje je zapravo jako jednostavno.

115
00:04:53,040 --> 00:04:57,134
Sve što trebate učiniti je hash
podataka, a zatim idite na tom mjestu.

116
00:04:57,134 --> 00:04:58,925
I uz pretpostavku da ne
imati bilo sudara,

117
00:04:58,925 --> 00:05:01,650
ćete biti u mogućnosti to izbrisati vrlo brzo.

118
00:05:01,650 --> 00:05:04,930
>> Sada, pretraživanje je mjesto gdje stvari
dobiti malo više komplicirano.

119
00:05:04,930 --> 00:05:06,910
To je u prosjeku bolje
od povezanih liste.

120
00:05:06,910 --> 00:05:09,560
Ako koristite ulančavanje,
još uvijek imate popis povezani,

121
00:05:09,560 --> 00:05:13,170
što znači da još uvijek imaju
traži štetu popis povezane.

122
00:05:13,170 --> 00:05:18,390
Ali zato ste uzimajući vaše povezani
popis i podijelite preko 100 ili 1000

123
00:05:18,390 --> 00:05:25,380
ili n elementi u vašem hash tablici, ti si
vezane liste su svi jedno NTH veličini.

124
00:05:25,380 --> 00:05:27,650
Svi su znatno manji.

125
00:05:27,650 --> 00:05:32,080
Vi nje su povezane liste umjesto
jednog povezanog popisa veličine n.

126
00:05:32,080 --> 00:05:34,960
>> I tako konstantno to u stvarnom svijetu
faktor, koji mi općenito

127
00:05:34,960 --> 00:05:39,730
Ne govorimo o složenosti vrijeme to,
ne zapravo čine razliku ovdje.

128
00:05:39,730 --> 00:05:43,020
Tako je još uvijek linearno pretraživanje
Pretražite ako koristite ulančavanje,

129
00:05:43,020 --> 00:05:46,780
a duljina popisa
ste u potrazi kroz

130
00:05:46,780 --> 00:05:50,080
vrlo, vrlo kratko u usporedbi.

131
00:05:50,080 --> 00:05:52,995
Opet, ako je vaš sortiranje
cilj ovdje, hash tablicu a

132
00:05:52,995 --> 00:05:54,370
vjerojatno nije pravi način da ide.

133
00:05:54,370 --> 00:05:56,830
Dovoljno je koristiti niz ako sortiranje
stvarno važno za vas.

134
00:05:56,830 --> 00:05:58,590
>> I oni mogu pokrenuti skala veličine.

135
00:05:58,590 --> 00:06:01,640
Teško je reći je li
hash tablica je mala ili velika,

136
00:06:01,640 --> 00:06:04,110
jer to stvarno ovisi o
koliko je velika vaša hash tablica.

137
00:06:04,110 --> 00:06:07,340
Ako ste samo ide da se pohrane
pet elemenata u vašem hash tablici,

138
00:06:07,340 --> 00:06:10,620
i imate hash tablicu
s 10.000 elemenata u njemu,

139
00:06:10,620 --> 00:06:12,614
vjerojatno ste gubit puno prostora.

140
00:06:12,614 --> 00:06:15,030
Kontrast vam se može
imaju vrlo kompaktnih hash tablice,

141
00:06:15,030 --> 00:06:18,720
ali manji vaše hash tablicu dobiva,
duže svaki od tih povezanih popisa

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

143
00:06:19,220 --> 00:06:22,607
I tako da stvarno nema načina za definiranje
upravo veličina hash tablici,

144
00:06:22,607 --> 00:06:24,440
ali to je vjerojatno sigurno
reći da je općenito

145
00:06:24,440 --> 00:06:27,990
će biti veća nego povezani
Popis spremanje istih podataka,

146
00:06:27,990 --> 00:06:30,400
ali manji od Trie.

147
00:06:30,400 --> 00:06:32,720
>> I napad su četvrti
Navedene konstrukcije

148
00:06:32,720 --> 00:06:34,070
da smo razgovarali o tome.

149
00:06:34,070 --> 00:06:36,450
Umetanje u Trie je složen.

150
00:06:36,450 --> 00:06:38,400
Postoji mnogo dinamički
dodjela memorije,

151
00:06:38,400 --> 00:06:40,780
pogotovo na početku,
kao što ste počeli graditi.

152
00:06:40,780 --> 00:06:43,700
Ali to je konstanta vrijeme.

153
00:06:43,700 --> 00:06:47,690
To je samo ljudski element
ovdje, što ga čini zahtjevno.

154
00:06:47,690 --> 00:06:53,250
Imajući u susret null pointer, malloc
prostor, tamo, možda malloc prostor

155
00:06:53,250 --> 00:06:54,490
od tamo opet.

156
00:06:54,490 --> 00:06:58,880
Vrsta zastrašivanja faktor
upućuje na dinamičke dodjele memorije

157
00:06:58,880 --> 00:07:00,130
je zapreka za brisanje.

158
00:07:00,130 --> 00:07:04,550
No, nakon što ste ga izbrisani, umetanje
zapravo dolazi vrlo jednostavna,

159
00:07:04,550 --> 00:07:06,810
i sigurno je konstanta vrijeme.

160
00:07:06,810 --> 00:07:07,680
>> Brisanje je jednostavno.

161
00:07:07,680 --> 00:07:11,330
Sve što trebate učiniti je ploviti dolje
Nekoliko upućuje i slobodnog čvora,

162
00:07:11,330 --> 00:07:12,420
tako da je vrlo dobro.

163
00:07:12,420 --> 00:07:13,930
Potraži je također prilično brzo.

164
00:07:13,930 --> 00:07:16,780
Ona se temelji samo na
duljina podataka.

165
00:07:16,780 --> 00:07:19,924
Dakle, ako sve svoje podatke je
pet nizova znakova,

166
00:07:19,924 --> 00:07:22,590
na primjer, da ste spremanje pet
niz znakova u vašem Trie,

167
00:07:22,590 --> 00:07:25,439
to traje samo pet koraka do
pronaći ono što tražite.

168
00:07:25,439 --> 00:07:28,480
Pet je samo konstantan faktor, tako da
opet, umetanje, brisanje i pretraživanje

169
00:07:28,480 --> 00:07:31,670
ovdje su svi vremenska konstanta, učinkovito.

170
00:07:31,670 --> 00:07:34,880
>> Druga stvar je da je vaš Trie je
zapravo vrsta već razvrstani, zar ne?

171
00:07:34,880 --> 00:07:36,800
Zahvaljujući tome smo
umetanje elemenata,

172
00:07:36,800 --> 00:07:40,060
odlaskom slovo po slovo
Ključ ili znamenku po znamenku ključa,

173
00:07:40,060 --> 00:07:45,084
obično, vaš Trie završi kao
vrsta razvrstani kao što ste ga graditi.

174
00:07:45,084 --> 00:07:47,250
To zapravo ne čini
smisla razmišljati o razvrstavanju

175
00:07:47,250 --> 00:07:49,874
na isti način na koji mislimo o
to s polja, ili povezanim popisima,

176
00:07:49,874 --> 00:07:51,070
ili hash tablice.

177
00:07:51,070 --> 00:07:54,780
No, u nekom smislu, vaše
Trie je razvrstani kao i ti ići.

178
00:07:54,780 --> 00:07:58,630
>> Loša strana je, naravno, da je
Trie brzo postaje ogromna.

179
00:07:58,630 --> 00:08:02,970
Iz svakog čvorište, možda
have-- ako vaš ključ sastoji od brojki,

180
00:08:02,970 --> 00:08:04,880
imate 10 drugi
mjesta možete ići, što

181
00:08:04,880 --> 00:08:07,490
znači da je svaki čvor
sadržava podatke

182
00:08:07,490 --> 00:08:11,440
o podacima želite pohraniti
u tom čvoru, plus 10 pokazivače.

183
00:08:11,440 --> 00:08:14,430
Koji, na CS50 IDE, 80 bajtova.

184
00:08:14,430 --> 00:08:17,220
Tako da je najmanje 80 bajtova za
svaki čvor koji ste stvorili,

185
00:08:17,220 --> 00:08:19,240
i da nije ni računajući podatke.

186
00:08:19,240 --> 00:08:24,950
I ako tvoji čvorovi
slova umjesto brojki,

187
00:08:24,950 --> 00:08:27,825
Sada imate 26 pokazivače
iz svakog mjesta.

188
00:08:27,825 --> 00:08:32,007
A 26 puta 8 je vjerojatno 200
bajtova, ili nešto slično.

189
00:08:32,007 --> 00:08:33,840
A imate kapital
i ti lowercase-- može

190
00:08:33,840 --> 00:08:35,381
vidjeti gdje idem s ovim, zar ne?

191
00:08:35,381 --> 00:08:37,500
Vaša čvorovi mogu dobiti stvarno
velika, pa je Trie

192
00:08:37,500 --> 00:08:40,470
Sama, u ukupnom poretku, može
dobili stvarno velik, previše.

193
00:08:40,470 --> 00:08:42,630
Dakle, ako je prostor na visokoj
Premija na vašem sustavu,

194
00:08:42,630 --> 00:08:45,830
Trie možda nije pravi način da se
ići, iako drugih prednosti

195
00:08:45,830 --> 00:08:47,780
dolaze u igru.

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

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

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