1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[Glazbom]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID Malan: Ovo je CS50.

5
00:00:14,010 --> 00:00:18,090
A to je i početak i
end-- kao literally-- gotovo do kraja

6
00:00:18,090 --> 00:00:18,825
u tjednu šest.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> Mislio sam da bih podijeliti
Malo zabavna činjenica.

9
00:00:22,640 --> 00:00:25,370
Ja sam izvukao ovaj gore iz
Podaci prošli semestar je postavljen.

10
00:00:25,370 --> 00:00:29,710
Možda se sjećate da smo vas pitati na svakom
p set oblik, ako ste gledali na internetu

11
00:00:29,710 --> 00:00:31,580
ili ako ste sudjelovali u osobi.

12
00:00:31,580 --> 00:00:33,020
I ovdje je podataka.

13
00:00:33,020 --> 00:00:34,710
Tako je danas bio vrlo predvidljiv.

14
00:00:34,710 --> 00:00:37,126
No, željeli smo provesti malo
vremena s vama svejedno.

15
00:00:37,126 --> 00:00:40,599
Bi li itko želio nagađati zašto je to
graf je tako JAGGY, gore dolje, gore dolje,

16
00:00:40,599 --> 00:00:41,265
tako dosljedno?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
Što svaki od vrhova
i korita predstavljaju?

19
00:00:45,130 --> 00:00:46,005
>> PUBLIKA: [nečujan]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID Malan: Doista.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
I više zabavno, ne daj Bože,
držimo jedno predavanje u petak

24
00:00:55,480 --> 00:00:58,960
na početku semestra,
to je ono što mi se dogodi.

25
00:00:58,960 --> 00:01:03,430
Tako je danas, možemo sudjelovati u malo
Više o strukturama podataka.

26
00:01:03,430 --> 00:01:06,660
I da vam više čvrste
mentalni model za probleme u pet,

27
00:01:06,660 --> 00:01:07,450
koji je sada van.

28
00:01:07,450 --> 00:01:10,817
Pravopisne pogreške, pri čemu, mi ćemo
uručiti vam tekstualnu datoteku oko 100.000

29
00:01:10,817 --> 00:01:12,650
plus engleski riječi i
idete imati

30
00:01:12,650 --> 00:01:17,770
shvatiti kako se pametno ih učitati
u memoriju, u RAM-a, koristeći neke podatke

31
00:01:17,770 --> 00:01:19,330
Struktura vašem izboru.

32
00:01:19,330 --> 00:01:22,470
>> Sada jedna takva struktura podataka mogla
biti, ali vjerojatno ne bi trebalo biti,

33
00:01:22,470 --> 00:01:25,630
prilično jednostavna povezani popis,
koje smo uveli posljednji put.

34
00:01:25,630 --> 00:01:29,220
A popis vezan je imao najmanje
prednost u nizu.

35
00:01:29,220 --> 00:01:32,096
Što je jedna od prednosti
Popis povezani vjerojatno?

36
00:01:32,096 --> 00:01:32,950
>> PUBLIKA: umetanje.

37
00:01:32,950 --> 00:01:33,908
>> DAVID Malan: umetanje.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
Što misliš pod tim?

40
00:01:35,196 --> 00:01:37,872
>> PUBLIKA: Svugdje zajedno
Lista [nečujan].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Malan: Dobro.

42
00:01:38,770 --> 00:01:42,090
Dakle, možete umetnuti element gdje god
Želite u sredini popisa

43
00:01:42,090 --> 00:01:45,490
bez dvoličnost ništa,
što smo zaključili, u našem sortiranje

44
00:01:45,490 --> 00:01:47,630
rasprava, nije
nužno dobra stvar,

45
00:01:47,630 --> 00:01:51,200
jer treba vremena da se zapravo premjestiti
sve te ljude lijevo ili desno.

46
00:01:51,200 --> 00:01:55,540
I tako s popisa povezan, možete
Samo izdvojiti s malloc, novi čvor,

47
00:01:55,540 --> 00:01:58,385
a zatim ažurirati par
pointers-- dva, tri operacije max--

48
00:01:58,385 --> 00:02:01,480
a mi smo u stanju utor nekoga
u bilo gdje u popisu.

49
00:02:01,480 --> 00:02:03,550
>> Što drugo je prednost
o popisu povezane?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
Da?

52
00:02:05,659 --> 00:02:06,534
>> PUBLIKA: [nečujan]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID Malan: Savršeno.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
Savršeno.

57
00:02:11,090 --> 00:02:12,070
To je stvarno dinamična.

58
00:02:12,070 --> 00:02:15,100
A da niste počinili,
unaprijed, do neke fiksne veličine

59
00:02:15,100 --> 00:02:18,750
komad memorije, kao što bi
da s nizom, naopako od kojih

60
00:02:18,750 --> 00:02:22,455
je da možete izdvojiti čvorova samo na
Potražnja čime korištenjem samo što više prostora

61
00:02:22,455 --> 00:02:23,330
kao što je zapravo potrebno.

62
00:02:23,330 --> 00:02:26,830
Za razliku od niza, možda
slučajno izdvojiti premalo.

63
00:02:26,830 --> 00:02:28,871
I onda to samo ide
da se bol u vratu

64
00:02:28,871 --> 00:02:32,440
preraspodijeliti novi veći niz, kopirati
sve više, osloboditi starog niz,

65
00:02:32,440 --> 00:02:33,990
a zatim premjestiti o svom poslovanju.

66
00:02:33,990 --> 00:02:37,479
Ili još gore, možda izdvojiti način
više memorije nego što je zapravo potrebno,

67
00:02:37,479 --> 00:02:40,520
pa ti ćeš imati vrlo
slabo naseljenom niz, da se tako izrazim.

68
00:02:40,520 --> 00:02:44,350
>> Dakle, popis povezani daje to
Prednosti dinamičnosti i fleksibilnosti

69
00:02:44,350 --> 00:02:46,080
s umetanja i brisanja.

70
00:02:46,080 --> 00:02:48,000
Ali sigurno mora postojati cijena koja se plaća.

71
00:02:48,000 --> 00:02:50,000
U stvari, jedna od tema
istražiti kviz nula

72
00:02:50,000 --> 00:02:52,430
bio par od ustupaka
smo do sada vidjeli.

73
00:02:52,430 --> 00:02:56,161
Dakle, što je cijena koja se plaća ili
negativni popisa povezane?

74
00:02:56,161 --> 00:02:56,660
Da.

75
00:02:56,660 --> 00:02:57,560
>> PUBLIKA: Nema izravnim pristupom.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Malan: Nema izravnim pristupom.

77
00:02:58,809 --> 00:02:59,540
Ali koga briga?

78
00:02:59,540 --> 00:03:01,546
Izravnim pristupom ne zvuči primamljivo.

79
00:03:01,546 --> 00:03:02,421
>> PUBLIKA: [nečujan]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID Malan: Točno.

82
00:03:05,740 --> 00:03:07,580
Ako želite imati
Sigurno algorithm--

83
00:03:07,580 --> 00:03:10,170
i neka mi zapravo predlaže
binarno pretraživanje osobito, što

84
00:03:10,170 --> 00:03:12,600
jedna smo koristi dosta bit--
Ako nemate slučajni pristup,

85
00:03:12,600 --> 00:03:15,516
ne možete učiniti tako jednostavno aritmetiku
pronalaženja poput srednjeg elementa

86
00:03:15,516 --> 00:03:16,530
i skakanje pravo na njega.

87
00:03:16,530 --> 00:03:20,239
Umjesto toga moramo početi na prvi
element i linearno traži od lijeva

88
00:03:20,239 --> 00:03:22,780
na desno, ako želite pronaći
srednji ili bilo koji drugi element.

89
00:03:22,780 --> 00:03:24,410
>> PUBLIKA: Vjerojatno traje više memorije.

90
00:03:24,410 --> 00:03:25,040
>> DAVID Malan: Uzeti više memorije.

91
00:03:25,040 --> 00:03:27,464
Gdje je dodatna
trošak dolaze iz memorije?

92
00:03:27,464 --> 00:03:28,339
>> PUBLIKA: [nečujan]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID Malan: Točno.

95
00:03:33,440 --> 00:03:35,679
U ovom slučaju ovdje, imali smo
povezani popis za cijelih brojeva,

96
00:03:35,679 --> 00:03:37,470
a ipak smo udvostručenje
količina memorije

97
00:03:37,470 --> 00:03:39,680
trebamo tako i spremanje tih savjeta.

98
00:03:39,680 --> 00:03:42,090
Sada manje velika stvar kao što je
Vaši konstrukt dobiti veći

99
00:03:42,090 --> 00:03:45,320
a ti spremanje nije broj, ali
možda student ili neki drugi objekt.

100
00:03:45,320 --> 00:03:46,880
No, stvar sigurno ostaje.

101
00:03:46,880 --> 00:03:49,421
I tako broj operacija
na povezanim listama su pozvani

102
00:03:49,421 --> 00:03:50,570
bili su veliki O je n- linearno.

103
00:03:50,570 --> 00:03:54,730
Stvari poput umetanja ili traženja
ili brisanja u slučaju elementa

104
00:03:54,730 --> 00:03:57,720
dogodilo se na samom kraju
Popis li to razvrstani ili ne.

105
00:03:57,720 --> 00:04:01,167
>> Ponekad možda ćete dobiti sretan i
pa niže granica na tim poslovima

106
00:04:01,167 --> 00:04:04,250
Također bi moglo biti konstantna vrijeme, ako ste
Uvijek gleda na prvom elementu,

107
00:04:04,250 --> 00:04:05,070
na primjer.

108
00:04:05,070 --> 00:04:09,360
No, u konačnici, obećali smo
kako bi se postigla sveti gral

109
00:04:09,360 --> 00:04:12,630
struktura podataka, ili
neke njihove aproksimacija,

110
00:04:12,630 --> 00:04:14,290
putem stalne vremena.

111
00:04:14,290 --> 00:04:17,579
Možemo pronaći elemente ili dodati elemente
ili ukloniti elemente iz popisa?

112
00:04:17,579 --> 00:04:19,059
Vidjet ćemo uskoro.

113
00:04:19,059 --> 00:04:21,100
I ispada da je jedan
mehanizama smo mi

114
00:04:21,100 --> 00:04:23,464
će se početi koristiti danas,
godišnja potrebna u p postaviti pet,

115
00:04:23,464 --> 00:04:24,630
je zapravo prilično poznato.

116
00:04:24,630 --> 00:04:27,430
Na primjer, ako je to hrpa
ispitnih knjiga, od kojih je svaki

117
00:04:27,430 --> 00:04:29,660
ima student prvi
ime i prezime na njemu,

118
00:04:29,660 --> 00:04:31,820
i ja ih pokupiti iz
Na kraju ispita,

119
00:04:31,820 --> 00:04:33,746
i oni su svi prilično
koliko u slučajnim redoslijedom,

120
00:04:33,746 --> 00:04:36,370
a mi želimo ići oko sortiranja
ovi ispiti, tako da, kada ocjenjuju

121
00:04:36,370 --> 00:04:38,661
to je samo puno lakše i
brže ih predati natrag

122
00:04:38,661 --> 00:04:40,030
za studente po abecedi.

123
00:04:40,030 --> 00:04:42,770
Što bi vaši instinkti se
za hrpu ispita kao što je ovaj?

124
00:04:42,770 --> 00:04:45,019
>> Pa, ako ste poput mene,
Možda vidim da je ovo m,

125
00:04:45,019 --> 00:04:48,505
pa ću se nekako staviti ovo u,
ako je to moj stol ili moj kat gdje

126
00:04:48,505 --> 00:04:50,650
Ja sam širenja stvari
out-- ili moj niz really--

127
00:04:50,650 --> 00:04:52,210
Možda ću staviti sve Ms tamo.

128
00:04:52,210 --> 00:04:52,710
Oh.

129
00:04:52,710 --> 00:04:55,020
Evo A. Dakle, mogao bih
staviti As ovamo.

130
00:04:55,020 --> 00:04:55,520
Oh.

131
00:04:55,520 --> 00:04:57,980
Evo još jedan A. idem
staviti da je ovdje.

132
00:04:57,980 --> 00:05:02,490
Evo Z. Ovdje je još M. I tako
Mogao bih početi zarađivati ​​hrpe kao što je ovaj.

133
00:05:02,490 --> 00:05:06,620
A onda možda bih ići kasnije
i vrsta vrlo nitpicky-ly sortiranje

134
00:05:06,620 --> 00:05:07,710
pojedinačni piloti.

135
00:05:07,710 --> 00:05:11,300
No, poanta je da će izgledati
na ulazu da sam ruku

136
00:05:11,300 --> 00:05:14,016
i ja bi neki izračunata
Odluka se temelji na tom ulazu.

137
00:05:14,016 --> 00:05:15,640
Ako se polazi, stavi ga tamo.

138
00:05:15,640 --> 00:05:18,980
Ako se počne sa Z, stavi ga na
tamo, i sve između.

139
00:05:18,980 --> 00:05:22,730
>> Dakle, ovo je tehnika koja je
općenito poznat kao hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
što obično znači da kao
ulaz i koristiti taj ulaz izračunati

141
00:05:26,550 --> 00:05:30,940
vrijednost, općenito broj, i to
broj je indeks u pohranu

142
00:05:30,940 --> 00:05:32,260
Spremnik, kao i niz.

143
00:05:32,260 --> 00:05:35,490
Dakle, drugim riječima, možda sam
hash funkcija, kao što sam to u mojoj glavi,

144
00:05:35,490 --> 00:05:37,940
da ako vidim da netko je
Naziv koji počinje sa A,

145
00:05:37,940 --> 00:05:40,190
Idem na kartu da je
na nulu u mojoj glavi.

146
00:05:40,190 --> 00:05:44,160
A ako vidim nekoga sa Z, ja sam
ide na kartu da je 25 u mojoj glavi

147
00:05:44,160 --> 00:05:46,220
a onda staviti da u
Posljednji najviše gomila.

148
00:05:46,220 --> 00:05:50,990
>> Sada, ako mislite o tome nije moj mozak
ali programske C, što su brojevi mogli

149
00:05:50,990 --> 00:05:53,170
se oslanjaju na postići taj isti rezultat?

150
00:05:53,170 --> 00:05:55,594
Drugim riječima, ako vas
imao ASCII znakova A,

151
00:05:55,594 --> 00:05:57,510
kako ste utvrdili
ono kanta da ga stavite u?

152
00:05:57,510 --> 00:05:59,801
Vi vjerojatno ne želite
stavite ga u kantu 65, koji je

153
00:05:59,801 --> 00:06:01,840
bi bilo kao tamo
bez dobrog razloga.

154
00:06:01,840 --> 00:06:04,320
Gdje želiš staviti
u smislu njegovog ASCII vrijednosti?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
Gdje želiš učiniti svoje ASCII
Vrijednost smisliti pametniji kantu

157
00:06:08,920 --> 00:06:09,480
da ga stavite u?

158
00:06:09,480 --> 00:06:10,206
>> PUBLIKA: Minus A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID Malan: Da.

160
00:06:10,956 --> 00:06:13,190
Dakle, minus ili minus
posebno 65, ako je to

161
00:06:13,190 --> 00:06:18,240
kapital A. Ili, ako 98
to je mala.

162
00:06:18,240 --> 00:06:21,300
I tako da bi nam omogućiti da, vrlo
jednostavno i vrlo aritmetički,

163
00:06:21,300 --> 00:06:23,260
stavite nešto u kantu kao što je to.

164
00:06:23,260 --> 00:06:26,010
Tako ispada da zapravo učiniti
to kao dobro, čak i sa kvizovima.

165
00:06:26,010 --> 00:06:29,051
>> Dakle, možda ćete se sjetiti što zaokružena svoje
Ime demonstrator je na naslovnici.

166
00:06:29,051 --> 00:06:32,270
A organizirani su imena TF-a
u ovim stupcima po abecednom redu,

167
00:06:32,270 --> 00:06:34,400
dobro, vjerovali ili ne,
kada je sve 80 plus nas

168
00:06:34,400 --> 00:06:37,800
okupili neku večer u razred,
posljednji korak u našoj procesa ocjenjivanja

169
00:06:37,800 --> 00:06:41,830
je razmotrili su kvizove na veliko
prostor na katu [nečujan]

170
00:06:41,830 --> 00:06:45,110
i položiti svačije kvizova iz
upravo u cilju njihove TF-ih

171
00:06:45,110 --> 00:06:47,700
imena na naslovnici, jer je
onda je puno lakše za nas

172
00:06:47,700 --> 00:06:51,290
tražiti kroz tu pomoću linearne
pretraživanja ili neka vrsta pameti

173
00:06:51,290 --> 00:06:54,050
za TF pronaći njegov ili
kvizovi svojih studenata.

174
00:06:54,050 --> 00:06:56,060
>> Dakle, ova ideja raspršivanja
da ćete vidjeti je

175
00:06:56,060 --> 00:07:00,520
vrlo moćna je zapravo prilično
uobičajena i vrlo intuitivno,

176
00:07:00,520 --> 00:07:03,000
slično kao možda dijele i
vladaj bio u tjednu nula.

177
00:07:03,000 --> 00:07:05,250
Ja brzo naprijed na hackathon
Prije par godina.

178
00:07:05,250 --> 00:07:08,040
To je Zamyla i par
drugi studenti osoblje pozdrav

179
00:07:08,040 --> 00:07:09,030
kao što su došli u.

180
00:07:09,030 --> 00:07:12,680
I imali smo hrpu sklopivi
tablicama s oznakama naziva.

181
00:07:12,680 --> 00:07:15,380
I mi smo imali oznake s imenom organiziraju
s kao i nad postoji

182
00:07:15,380 --> 00:07:16,690
i Zs tamo.

183
00:07:16,690 --> 00:07:20,350
I tako jedan od TFS vrlo pametno
napisao je ovo kao upute

184
00:07:20,350 --> 00:07:21,030
za dan.

185
00:07:21,030 --> 00:07:24,480
A u 12. tjednu semestra ove
sve napravio smisla i svima

186
00:07:24,480 --> 00:07:25,310
znao što učiniti.

187
00:07:25,310 --> 00:07:27,900
Ali kad god ste
čekanju na isti način,

188
00:07:27,900 --> 00:07:30,272
ti si provedbi
Isti pojam mljeveno meso.

189
00:07:30,272 --> 00:07:31,730
Tako ćemo se malo formalizirati.

190
00:07:31,730 --> 00:07:32,890
Ovdje je niz.

191
00:07:32,890 --> 00:07:36,820
To je nacrtana biti malo
širok samo prikazati, vizualno,

192
00:07:36,820 --> 00:07:38,920
da bismo mogli staviti žice
u nešto poput ovoga.

193
00:07:38,920 --> 00:07:41,970
A ovo polje je
Jasno je veličine 26 ukupno.

194
00:07:41,970 --> 00:07:43,935
A što se zove
Tablica proizvoljno.

195
00:07:43,935 --> 00:07:48,930
No, to je samo umjetnički izvedba
onoga što hash tablicu može biti.

196
00:07:48,930 --> 00:07:52,799
>> Tako hash tablicu sada će
biti viša razina struktura podataka.

197
00:07:52,799 --> 00:07:54,840
Na kraju dana
smo o tome da se vidi da vas

198
00:07:54,840 --> 00:07:58,700
može provesti hash tablicu, koja
je mnogo kao i prijave u skladu

199
00:07:58,700 --> 00:08:02,059
na hackathon mnogo kao što je ovaj
Tablica koristi za sortiranje ispit knjige.

200
00:08:02,059 --> 00:08:03,850
No hash tablicu je
oblik tog visokoj razini

201
00:08:03,850 --> 00:08:08,250
Koncept koji bi mogao iskoristiti niz
ispod napa da ga provede,

202
00:08:08,250 --> 00:08:11,890
ili je mogao koristiti popis dužine, ili čak
možda i neke druge strukture podataka.

203
00:08:11,890 --> 00:08:15,590
I sad kad je theme-- uzimanje
neke od tih temeljnih sastojaka

204
00:08:15,590 --> 00:08:18,310
kao i niz ove zgrade
blokirati sada popisa duljine

205
00:08:18,310 --> 00:08:21,740
i vidjeti što još možemo graditi
na vrhu onih koji, poput sastojaka

206
00:08:21,740 --> 00:08:26,550
u receptu, što više i više
zanimljive i korisne konačni rezultati.

207
00:08:26,550 --> 00:08:28,680
>> Dakle, s hash tablicu
možemo ga provesti

208
00:08:28,680 --> 00:08:32,540
u spomen slikovito ovako, ali
Kako bi mogli to zapravo biti kodirani gore?

209
00:08:32,540 --> 00:08:33,789
Pa, možda je jednostavno to.

210
00:08:33,789 --> 00:08:38,270
Ako KAPACITET u svim kape, samo je
neki constant-- primjerice 26,

211
00:08:38,270 --> 00:08:42,030
26 slova alphabet--
Možda ću nazvati svoju promjenjivu stol,

212
00:08:42,030 --> 00:08:45,630
i ja mogao tvrditi da ću
staviti char zvijezde tamo, ili niza.

213
00:08:45,630 --> 00:08:49,880
Dakle, to je kao jednostavan kao ovaj ako
žele provesti hash tablicu.

214
00:08:49,880 --> 00:08:51,490
Pa ipak, to je zapravo samo niz.

215
00:08:51,490 --> 00:08:53,198
Ali opet, mljeveno meso
Tablica je sada ono što ćemo

216
00:08:53,198 --> 00:08:57,470
nazvati apstraktni tip podataka koji je upravo
vrsta konceptualnog raslojavanje na vrhu

217
00:08:57,470 --> 00:09:00,780
nešto više mondene
Sada se sviđa niz.

218
00:09:00,780 --> 00:09:02,960
>> Sada, kako ćemo ići
o rješavanju problema?

219
00:09:02,960 --> 00:09:06,980
Pa, prije sam imao luksuz
da ima dovoljno prostora tablice ovdje

220
00:09:06,980 --> 00:09:09,460
tako da sam mogao staviti
kvizovi gdje sam htjela.

221
00:09:09,460 --> 00:09:10,620
Tako Kao što se moglo ići ovdje.

222
00:09:10,620 --> 00:09:12,100
Zs moglo ići ovdje.

223
00:09:12,100 --> 00:09:13,230
Gospođa može ići ovdje.

224
00:09:13,230 --> 00:09:14,740
A onda sam imao neki dodatni prostor.

225
00:09:14,740 --> 00:09:18,740
No, to je malo varati prava
sada, jer ove tablice, ako sam stvarno

226
00:09:18,740 --> 00:09:22,720
razmišljao o njemu kao polje, samo je
će biti od neke fiksne veličine.

227
00:09:22,720 --> 00:09:25,380
>> Dakle, tehnički, ako sam povući
do drugog studenta kviz

228
00:09:25,380 --> 00:09:28,490
i vidjeti, oh, ta osoba je
ime počinje sa A također,

229
00:09:28,490 --> 00:09:30,980
Nekako sam htio da ga tamo.

230
00:09:30,980 --> 00:09:34,740
No, čim sam ga stavio tamo, ako je
ova tablica doista predstavlja niz,

231
00:09:34,740 --> 00:09:37,840
Ja ću biti preskakanja ili clobbering
Tko ovu učenika kviz je.

232
00:09:37,840 --> 00:09:38,340
Pravo?

233
00:09:38,340 --> 00:09:41,972
Ako je ovo polje, samo jedna stvar može
idu u svakoj od tih stanica ili elemente.

234
00:09:41,972 --> 00:09:43,680
I tako sam vrsta ima
izabrati.

235
00:09:43,680 --> 00:09:45,735
>> Sada sam ranije vrsta
varao i učinio ovo ili ja

236
00:09:45,735 --> 00:09:47,526
samo vrsta stog
im jedan iznad drugog.

237
00:09:47,526 --> 00:09:49,170
No, to se neće letjeti u kodu.

238
00:09:49,170 --> 00:09:52,260
Pa gdje sam mogao staviti
Drugi učenik čije ime

239
00:09:52,260 --> 00:09:54,964
je li sve što sam imala je to
dostupni prostora tablice?

240
00:09:54,964 --> 00:09:57,880
I ja sam se tri utora i to
Izgleda da postoji samo nekoliko drugih.

241
00:09:57,880 --> 00:09:58,959
Što možete učiniti?

242
00:09:58,959 --> 00:09:59,834
PUBLIKA: [nečujan]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID Malan: Da.

245
00:10:01,315 --> 00:10:02,370
Možda neka je samo ga zadržati jednostavan.

246
00:10:02,370 --> 00:10:02,660
Pravo?

247
00:10:02,660 --> 00:10:04,243
To se ne uklapa u kojoj želim da ga stavite.

248
00:10:04,243 --> 00:10:07,450
Tako ću ga staviti
tehnički gdje B će ići.

249
00:10:07,450 --> 00:10:09,932
Sada, naravno, Počinjem
kako bih se slikati u kut.

250
00:10:09,932 --> 00:10:11,890
Ako sam se studentu
čije ime je zapravo B,

251
00:10:11,890 --> 00:10:14,840
Sada B će biti premještena malo
prema naprijed, kao što bi se moglo dogoditi, yep,

252
00:10:14,840 --> 00:10:17,530
ako je to B, sada mora ići ovdje.

253
00:10:17,530 --> 00:10:20,180
>> I tako je to vrlo brzo
mogla bi postati problematično,

254
00:10:20,180 --> 00:10:23,850
ali to je tehnika koja zapravo
se naziva linearni sondiranja,

255
00:10:23,850 --> 00:10:26,650
gdje si samo uzeti u obzir svoje
Niz se duž linije.

256
00:10:26,650 --> 00:10:29,680
A ti samo vrsta probe ili
pregledati svaku dostupnu elementa

257
00:10:29,680 --> 00:10:31,360
u potrazi za dostupnom mjestu.

258
00:10:31,360 --> 00:10:34,010
I čim se nađete
jedan, što ga ispustiti tamo.

259
00:10:34,010 --> 00:10:38,390
>> Sada, cijena se plaća sada
za ovo rješenje je što?

260
00:10:38,390 --> 00:10:41,300
Imamo fiksnu veličinu niz,
a kad sam umetnuti imena

261
00:10:41,300 --> 00:10:44,059
u njega, barem u početku, što je
Vrijeme rada umetanja

262
00:10:44,059 --> 00:10:46,350
za stavljanje studente '
kvizovi na pravim kante?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Big O što?

265
00:10:50,002 --> 00:10:51,147
>> PUBLIKA: n.

266
00:10:51,147 --> 00:10:52,480
DAVID Malan: Čuo sam veliki O n.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
Nije istina.

269
00:10:54,300 --> 00:10:56,490
Ali mi ćemo zafrkavati, osim
Zato u samo trenutak.

270
00:10:56,490 --> 00:10:57,702
Što bi drugo moglo biti?

271
00:10:57,702 --> 00:10:58,755
>> PUBLIKA: [nečujan]

272
00:10:58,755 --> 00:11:00,380
DAVID Malan: I neka mi to učiniti vizualno.

273
00:11:00,380 --> 00:11:04,720
Dakle, pretpostavimo da je to pismo S.

274
00:11:04,720 --> 00:11:05,604
>> PUBLIKA: To je jedno.

275
00:11:05,604 --> 00:11:06,520
DAVID Malan: To je jedno.

276
00:11:06,520 --> 00:11:06,710
Pravo?

277
00:11:06,710 --> 00:11:08,950
To je niz, koji je
znači imamo slučajni pristup.

278
00:11:08,950 --> 00:11:11,790
A ako mislimo o tome
kao nula i to kao 25.,

279
00:11:11,790 --> 00:11:13,800
a mi shvatili da,
oh, ovdje je moj ulaz S,

280
00:11:13,800 --> 00:11:16,350
Ja sigurno mogu pretvoriti
S ASCII karakter,

281
00:11:16,350 --> 00:11:18,540
u odgovarajućem broju
između nule i 25

282
00:11:18,540 --> 00:11:20,910
a zatim odmah
stavi ga gdje mu je i mjesto.

283
00:11:20,910 --> 00:11:26,120
>> Ali, naravno, čim sam doći do
Druga osoba koja je ime je ili B ili C

284
00:11:26,120 --> 00:11:29,300
na kraju, ako sam koristiti
Linearni sondiranja kao moj rješenje,

285
00:11:29,300 --> 00:11:31,360
Vrijeme rada
umetanja u najgorem slučaju

286
00:11:31,360 --> 00:11:33,120
zapravo će prenijeti na što?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
I doista sam ga čuo ovdje
pravilno rano.

289
00:11:36,045 --> 00:11:36,920
PUBLIKA: [nečujan]

290
00:11:36,920 --> 00:11:41,620
DAVID Malan: Pa to je doista nakon nje
Imate li dovoljno veliki skup podataka.

291
00:11:41,620 --> 00:11:44,410
Tako je, s jedne strane, ako
Vaš Niz je dovoljno velika

292
00:11:44,410 --> 00:11:48,287
a vaši podaci oskudni dovoljno,
dobili ovu lijepu stalnu vrijeme.

293
00:11:48,287 --> 00:11:50,620
No, čim počnete
sve više i više elemenata,

294
00:11:50,620 --> 00:11:53,200
i samo statistički dobivate
više ljudi sa slovom

295
00:11:53,200 --> 00:11:56,030
Njihovo ime ili pismo
B, to bi potencijalno

296
00:11:56,030 --> 00:11:57,900
spadaju u nešto više ravnih.

297
00:11:57,900 --> 00:11:59,640
Dakle, nije baš idealno.

298
00:11:59,640 --> 00:12:00,690
Tako smo mogli učiniti bolje?

299
00:12:00,690 --> 00:12:03,210
>> Pa, što je naš
Rješenje prije kad smo

300
00:12:03,210 --> 00:12:06,820
Želite imati veću dinamiku od
nešto poput niz dopušteno?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
PUBLIKA: [nečujan]

303
00:12:08,960 --> 00:12:10,030
DAVID Malan: Što ćemo predstaviti?

304
00:12:10,030 --> 00:12:10,530
Da.

305
00:12:10,530 --> 00:12:11,430
Dakle, popis povezani.

306
00:12:11,430 --> 00:12:14,430
Pa, da vidimo što je povezano
Popis bi mogao učiniti za nas, umjesto.

307
00:12:14,430 --> 00:12:17,630
Pa, neka mi predlažemo da smo
nacrtati sliku kako slijedi.

308
00:12:17,630 --> 00:12:19,620
Sada je to drugačije
Slika iz primjera

309
00:12:19,620 --> 00:12:24,750
iz drugog teksta, zapravo, da
je zapravo koriste niz veličine 31.

310
00:12:24,750 --> 00:12:28,220
I ovaj autor jednostavno
odlučio hash žice

311
00:12:28,220 --> 00:12:32,430
ne na temelju imena te osobe,
ali na temelju njihovih birthdates.

312
00:12:32,430 --> 00:12:35,680
Bez obzira na mjesec, oni shvatili
Ako ste rođeni na prvi mjesec dana

313
00:12:35,680 --> 00:12:39,580
ili 31. u mjesecu, autor
hash će na temelju te vrijednosti,

314
00:12:39,580 --> 00:12:44,154
kako bi se proširila imena iz malo
više od 26 točaka mogao dopustiti.

315
00:12:44,154 --> 00:12:47,320
A možda je to malo više ujednačena
nego ide s znakovi abecede,

316
00:12:47,320 --> 00:12:50,236
jer naravno tu je vjerojatno
više ljudi u svijetu s imenima

317
00:12:50,236 --> 00:12:54,020
da je početak s nego sigurno
neka druga slova abecede.

318
00:12:54,020 --> 00:12:56,380
Dakle, možda je to malo
više uniformu, uz pretpostavku

319
00:12:56,380 --> 00:12:58,640
ravnomjerniji
beba preko mjesec dana.

320
00:12:58,640 --> 00:12:59,990
>> Ali, naravno, to je još uvijek nesavršena.

321
00:12:59,990 --> 00:13:00,370
Pravo?

322
00:13:00,370 --> 00:13:01,370
Imamo sudara.

323
00:13:01,370 --> 00:13:04,680
Više ljudi u to
struktura podataka i dalje

324
00:13:04,680 --> 00:13:08,432
imaju istu rođenja barem
ti si bez obzira na mjesec.

325
00:13:08,432 --> 00:13:09,640
No, ono što je autor učinio?

326
00:13:09,640 --> 00:13:13,427
Pa, izgleda da imamo niz
Na lijevoj strani nacrtan vertikalno,

327
00:13:13,427 --> 00:13:15,010
ali to je samo umjetnički izvedba.

328
00:13:15,010 --> 00:13:18,009
Nije bitno u kojem smjeru ti
nacrtati niz, to je još uvijek niz.

329
00:13:18,009 --> 00:13:20,225
Što je to niz naizgled?

330
00:13:20,225 --> 00:13:21,500
>> PUBLIKA: Vezana lista.

331
00:13:21,500 --> 00:13:21,650
>> DAVID Malan: Da.

332
00:13:21,650 --> 00:13:23,490
Izgleda kao da je
niz povezanih popisa.

333
00:13:23,490 --> 00:13:26,490
Pa opet, u ovom trenutku od vrste
korištenja ove strukture podataka sada

334
00:13:26,490 --> 00:13:28,550
kao sastojci u više
zanimljivih rješenja,

335
00:13:28,550 --> 00:13:30,862
vi apsolutno može potrajati
temeljno, kao niz,

336
00:13:30,862 --> 00:13:33,320
i onda se nešto više
Zanimljivo poput popisa povezan

337
00:13:33,320 --> 00:13:36,660
pa čak ih kombinirati u čak
zanimljivija struktura podataka.

338
00:13:36,660 --> 00:13:39,630
I doista, to također bi
se zove hash tablicu,

339
00:13:39,630 --> 00:13:42,610
pri čemu je niz
stvarno hash tablicu,

340
00:13:42,610 --> 00:13:45,600
ali to hash tablica ima
lanci, da se tako izrazim,

341
00:13:45,600 --> 00:13:50,220
koja može rasti ili smanjiti na temelju
broj elemenata koje želite umetnuti.

342
00:13:50,220 --> 00:13:52,990
>> Sada, u skladu s tim, što je
trčanje vrijeme sada?

343
00:13:52,990 --> 00:13:58,030
Ako želim ubaciti nekoga
čiji je rođendan je 31. listopada

344
00:13:58,030 --> 00:13:59,040
gdje se on ili ona ide?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
U redu.

347
00:14:01,030 --> 00:14:02,819
Na samom dnu gdje piše 31.

348
00:14:02,819 --> 00:14:03,610
I to je savršeno.

349
00:14:03,610 --> 00:14:05,060
To je konstanta vrijeme.

350
00:14:05,060 --> 00:14:08,760
Ali što ako nađemo nekog drugog
čiji je rođendan, da vidimo,

351
00:14:08,760 --> 00:14:10,950
Listopad, studeni, 31. prosinca?

352
00:14:10,950 --> 00:14:12,790
Kada se on ili ona će otići?

353
00:14:12,790 --> 00:14:13,290
Ista stvar.

354
00:14:13,290 --> 00:14:13,970
Dva koraka ipak.

355
00:14:13,970 --> 00:14:15,303
To je konstanta, iako je ne?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
U redu.

358
00:14:16,860 --> 00:14:17,840
U ovom trenutku je to.

359
00:14:17,840 --> 00:14:20,570
No, u općem slučaju,
više ljudi možemo dodati,

360
00:14:20,570 --> 00:14:23,790
probabilistically, idemo
da se sve više i više sudara.

361
00:14:23,790 --> 00:14:26,820
>> Sada je to malo
bolje, jer tehnički

362
00:14:26,820 --> 00:14:34,580
Sada moji lanci mogao biti u
najgorem slučaju koliko dugo?

363
00:14:34,580 --> 00:14:38,890
Ako sam umetnuti n ljudi u ovom više
sofisticirana struktura podataka, n ljudi,

364
00:14:38,890 --> 00:14:41,080
U najgorem slučaju to će biti n.

365
00:14:41,080 --> 00:14:41,815
Zašto?

366
00:14:41,815 --> 00:14:43,332
>> PUBLIKA: Jer ako svatko
ima isti rođendan,

367
00:14:43,332 --> 00:14:44,545
oni će biti jedan redak.

368
00:14:44,545 --> 00:14:45,420
DAVID Malan: Savršeno.

369
00:14:45,420 --> 00:14:47,480
To bi moglo biti malo neprirodan,
ali doista u najgorem slučaju,

370
00:14:47,480 --> 00:14:50,117
ako svatko ima isti rođendan,
s obzirom na ulaza imate,

371
00:14:50,117 --> 00:14:51,950
ti ćeš imati
masivno dugolančane.

372
00:14:51,950 --> 00:14:54,241
I tako, možete ga se nazvati
hash tablicu, ali stvarno je

373
00:14:54,241 --> 00:14:56,810
Samo masivni povezani popis s
Cijela puno izgubiti prostora.

374
00:14:56,810 --> 00:15:00,460
No, u cjelini, ako pretpostavimo da
barem rođendana su uniform--

375
00:15:00,460 --> 00:15:01,750
i to vjerojatno nije.

376
00:15:01,750 --> 00:15:02,587
Ja sam što to gore.

377
00:15:02,587 --> 00:15:04,420
Ali ako pretpostavimo, za
Radi rasprave

378
00:15:04,420 --> 00:15:07,717
da su, potom u teoriji, ako je
To je vertikalna zastupanje

379
00:15:07,717 --> 00:15:11,050
od polja, i onda se nadam da ste
će dobiti lanaca koji su, znate,

380
00:15:11,050 --> 00:15:15,880
otprilike iste duljine, gdje je svaki od
to predstavlja dan u mjesecu.

381
00:15:15,880 --> 00:15:19,930
>> Sada, ako postoji 31 ​​dana u mjesecu,
to znači da moje vrijeme trčanja jako

382
00:15:19,930 --> 00:15:25,230
je velik O n preko 31, koji je
osjeća bolje nego linearno.

383
00:15:25,230 --> 00:15:27,950
No, ono što je bio jedan od naših
Obveze par tjedana

384
00:15:27,950 --> 00:15:31,145
Prije, kad god je došao na izražavanje
Vrijeme rada algoritma?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
Dovoljno je samo pogledati u visokoj narudžbe roku.

387
00:15:35,190 --> 00:15:35,690
Pravo?

388
00:15:35,690 --> 00:15:37,400
31 je svakako korisno.

389
00:15:37,400 --> 00:15:39,610
No, to je još uvijek velika O n.

390
00:15:39,610 --> 00:15:41,730
No, jedna od tema
Problem je postaviti pet

391
00:15:41,730 --> 00:15:43,950
će biti
priznati da apsolutno,

392
00:15:43,950 --> 00:15:47,320
asimptotski, teoretski
ova struktura podataka

393
00:15:47,320 --> 00:15:50,470
nije bolje nego samo
jedan masivan povezani popis.

394
00:15:50,470 --> 00:15:53,550
I doista, u najgorem slučaju, to
hash tablicu mogli prenijeti u to.

395
00:15:53,550 --> 00:15:57,620
>> No, u stvarnom svijetu, s nama ljudima
da vlastitim Macove ili računala ili bilo

396
00:15:57,620 --> 00:16:01,240
i prikazuju stvarni svijet
softver na stvarnom svijetu podacima,

397
00:16:01,240 --> 00:16:03,260
algoritam koji ćete radije?

398
00:16:03,260 --> 00:16:09,180
Onaj koji vodi završne korake ili
onaj koji traje n podijeljena 31 koraka

399
00:16:09,180 --> 00:16:12,900
pronaći neki komad podataka ili
potražiti neke informacije?

400
00:16:12,900 --> 00:16:16,580
Mislim, apsolutno je 31 izvrši
Razlika u stvarnom svijetu.

401
00:16:16,580 --> 00:16:18,540
To je 31 puta brže.

402
00:16:18,540 --> 00:16:20,880
A mi ljudi svakako
će cijeniti to.

403
00:16:20,880 --> 00:16:23,004
>> Dakle, shvatili dihotomiju
postoji između zapravo

404
00:16:23,004 --> 00:16:25,920
govori o stvarima teoretski
i asimptotski što svakako

405
00:16:25,920 --> 00:16:28,760
ima vrijednost kao što smo vidjeli,
ali u stvarnom svijetu,

406
00:16:28,760 --> 00:16:32,930
Ako vam je stalo samo što
Ljudsko sretna za opće inputa,

407
00:16:32,930 --> 00:16:36,010
možda vrlo dobro žele prihvatiti
Činjenica da, da, ovo je linearna,

408
00:16:36,010 --> 00:16:38,360
ali to je 31 puta brže
nego linearno moglo biti.

409
00:16:38,360 --> 00:16:41,610
I još bolje, ne samo da
učinite nešto proizvoljnog poput datuma rođenja,

410
00:16:41,610 --> 00:16:44,030
bismo mogli provesti malo
više vremena i pameću

411
00:16:44,030 --> 00:16:47,140
i razmišljati o tome što bismo mogli učiniti,
ime i možda neke osobe

412
00:16:47,140 --> 00:16:50,130
njihov datum rođenja kombinirati onima
Sastojci shvatiti nešto

413
00:16:50,130 --> 00:16:52,720
to je doista više
uniformu i manje JAGGY,

414
00:16:52,720 --> 00:16:56,250
takoreći od ove slike
Trenutno sugerira da bi moglo biti.

415
00:16:56,250 --> 00:16:57,750
Kako bismo mogli provesti to u kodu?

416
00:16:57,750 --> 00:17:00,280
Pa, neka mi predlažemo da smo
Samo posuditi neki sintaksu smo

417
00:17:00,280 --> 00:17:01,799
koristiti nekoliko puta do sada.

418
00:17:01,799 --> 00:17:03,590
A ja ću definirati
čvor, što opet

419
00:17:03,590 --> 00:17:06,812
je generički naziv za samo neke
Posuda za neke strukture podataka.

420
00:17:06,812 --> 00:17:09,020
Ja ću predložiti da
niz ide tamo.

421
00:17:09,020 --> 00:17:11,369
Ali ćemo početi uzimati
onima trening kotačima off sada.

422
00:17:11,369 --> 00:17:13,230
>> Nema više CS50 knjižnica
stvarno, osim ako ne želite

423
00:17:13,230 --> 00:17:15,230
ga koristiti za svoje finale
Projekt, koji je u redu,

424
00:17:15,230 --> 00:17:18,569
ali sada ćemo povući
zavjese i reći to je samo char zvijezda.

425
00:17:18,569 --> 00:17:22,069
Dakle, riječ tamo će biti
na ime osobe u pitanju.

426
00:17:22,069 --> 00:17:25,079
A sada imam vezu
Ovdje na sljedeći čvor

427
00:17:25,079 --> 00:17:28,170
tako da to predstavlja
svaki od čvorova

428
00:17:28,170 --> 00:17:30,950
u lancu, potencijalno,
popisa povezane.

429
00:17:30,950 --> 00:17:34,090
>> I sad kako mogu proglasiti
hash sama stol?

430
00:17:34,090 --> 00:17:36,660
Kako Izjavljujem cijelu ovu strukturu?

431
00:17:36,660 --> 00:17:40,960
Pa, zapravo, baš kao i sam se pokazivač
samo na prvi element popisa

432
00:17:40,960 --> 00:17:44,510
Prije, slično mogu samo reći
Samo mi treba hrpa pokazivača

433
00:17:44,510 --> 00:17:46,270
provesti cijeli ovaj hash tablicu.

434
00:17:46,270 --> 00:17:49,484
Ja ću imati niz
pozvao stol za hash tablicu.

435
00:17:49,484 --> 00:17:50,900
To će biti od veličine kapaciteta.

436
00:17:50,900 --> 00:17:52,525
Tako su mnogi elementi mogu stati u nju.

437
00:17:52,525 --> 00:17:56,180
I svaki od tih elemenata u ovo
Niz će biti čvor zvijezda.

438
00:17:56,180 --> 00:17:56,810
Zašto?

439
00:17:56,810 --> 00:18:00,160
Pa, po ovoj slici, ono što sam
provedbi hash tablicu kao

440
00:18:00,160 --> 00:18:04,330
učinkovito je samo početak
ovaj niz koji smo nacrtana okomito,

441
00:18:04,330 --> 00:18:06,820
od kojih svaki kvadrata
predstavlja pokazivač.

442
00:18:06,820 --> 00:18:09,170
To one koje imaju kose crte
kroz njih su samo null.

443
00:18:09,170 --> 00:18:11,410
A oni koji imaju
Strelice idu u desno

444
00:18:11,410 --> 00:18:16,140
su stvarni upućuje na stvarnim čvorova,
ergo početka popisa povezane.

445
00:18:16,140 --> 00:18:19,050
>> Dakle, ovdje je, dakle, kako bismo mogli
implementirati hash tablicu koja

446
00:18:19,050 --> 00:18:21,580
provodi poseban ulančavanje.

447
00:18:21,580 --> 00:18:22,840
Sada možemo učiniti bolje?

448
00:18:22,840 --> 00:18:25,632
U redu sam obećao zadnji put
bismo mogli postići stalnu vrijeme.

449
00:18:25,632 --> 00:18:27,381
A ja vrsta ti dao
konstanta vrijeme ovdje,

450
00:18:27,381 --> 00:18:29,850
ali onda nije rekao stvarno
vremenska konstanta, jer to je još uvijek

451
00:18:29,850 --> 00:18:31,890
ovisno o ukupnom
broj elemenata

452
00:18:31,890 --> 00:18:34,500
ti si unosom u
struktura podataka.

453
00:18:34,500 --> 00:18:35,980
No, pretpostavimo da je to učinio.

454
00:18:35,980 --> 00:18:39,550
Pusti me da se vratim na zaslonu ovamo.

455
00:18:39,550 --> 00:18:44,520
Dopustite mi također projiciraju to ovdje, jasno
zaslon, a da bih to učinio.

456
00:18:44,520 --> 00:18:49,300
Pretpostavimo da sam htjela umetnuti ime
Daven u u moju strukturu podataka.

457
00:18:49,300 --> 00:18:52,100
>> Dakle, želim umetnuti niz
Daven u strukturu podataka.

458
00:18:52,100 --> 00:18:54,370
Što ako ne koristim
hash tablicu, ali ja koristiti

459
00:18:54,370 --> 00:18:56,980
nešto što je više stabala nalik
poput obiteljskog stabla, gdje je

460
00:18:56,980 --> 00:18:59,670
Imate li neki korijen u
vrhu, a zatim čvorovi i lišće

461
00:18:59,670 --> 00:19:01,440
da ide prema dolje i prema van.

462
00:19:01,440 --> 00:19:04,450
Pretpostavimo onda da ja
želite umetnuti Daven-a

463
00:19:04,450 --> 00:19:06,430
u ono što je trenutno prazna popis.

464
00:19:06,430 --> 00:19:09,780
Ja ću učiniti sljedeće: Ja sam
će stvoriti čvor u ovoj obitelji

465
00:19:09,780 --> 00:19:15,170
stabla kao struktura podataka koja izgleda
nešto kao što je ovaj, od kojih svaka

466
00:19:15,170 --> 00:19:19,640
pravokutnici je, recimo,
za sada 26 elemenata u njemu.

467
00:19:19,640 --> 00:19:21,650
I svaka ćelija
U tom nizu ide

468
00:19:21,650 --> 00:19:23,470
zastupati pismo jednog pisma.

469
00:19:23,470 --> 00:19:28,190
>> Naime, idem na liječenje
To je, onda B, zatim C, zatim D,

470
00:19:28,190 --> 00:19:29,310
ovaj ovdje.

471
00:19:29,310 --> 00:19:32,940
Dakle, to će učinkovito
predstavljaju slovo D.

472
00:19:32,940 --> 00:19:36,040
No, umetanje sve Daven-a
ime moram učiniti nešto više.

473
00:19:36,040 --> 00:19:37,840
Pa ja sam prvi put ide na mljeveno meso, da se tako izrazim.

474
00:19:37,840 --> 00:19:41,049
Ja ću gledati na prvo slovo
U Daven-a koji je očito D,

475
00:19:41,049 --> 00:19:42,840
a ja ću izdvojiti
čvor koji izgleda

476
00:19:42,840 --> 00:19:45,570
kao this-- veliki pravokutnik veliki
dovoljno da stane na cijelu abecedu.

477
00:19:45,570 --> 00:19:47,140
>> Sada D je učinio.

478
00:19:47,140 --> 00:19:49,720
Sada A. D--V-E-N je cilj.

479
00:19:49,720 --> 00:19:51,220
Pa sad što ću učiniti je to.

480
00:19:51,220 --> 00:19:54,027
Čim sam počeo D obavijest
nema kazaljke nema.

481
00:19:54,027 --> 00:19:56,860
To je smeće vrijednosti u ovom trenutku,
ili sam možda ga inicijalizirati na nulu.

482
00:19:56,860 --> 00:19:59,630
No, dopustite mi da ide s
ta ideja o izgradnji stablo.

483
00:19:59,630 --> 00:20:04,260
Dopustite mi izdvojiti još jedan od njih
čvorovi koji ima 26 elemenata u njoj.

484
00:20:04,260 --> 00:20:05,150
>> I znate što?

485
00:20:05,150 --> 00:20:09,130
Ako je to samo čvor u sjećanju da je
Napravio sam s malloc, pomoću struct

486
00:20:09,130 --> 00:20:11,240
kao što ćemo uskoro vidjeti,
Ja ću učiniti this--

487
00:20:11,240 --> 00:20:14,450
Ja ću nacrtati strelicu
stvar koja zastupa D prema dolje

488
00:20:14,450 --> 00:20:15,860
na ovaj novi čvor.

489
00:20:15,860 --> 00:20:19,240
I sada, prvi sljedeći
Pismo u Daven ime,

490
00:20:19,240 --> 00:20:24,150
V-- D--V-- ću ići naprijed
i privući još jedan čvor kao što je ovaj,

491
00:20:24,150 --> 00:20:30,150
pri čemu su V elementi ovdje, koji
ćemo izvući za instance-- Ups.

492
00:20:30,150 --> 00:20:31,020
Nećemo povući tamo.

493
00:20:31,020 --> 00:20:31,936
To će ići ovdje.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> Onda ćemo
smatram da je to V.

496
00:20:35,712 --> 00:20:44,920
A onda ovdje ćemo indeksa
dolje iz V u ono što ćemo razmotriti E.

497
00:20:44,920 --> 00:20:50,100
A onda odavde ćemo
nesposobnu jedan od tih čvorova ovdje.

498
00:20:50,100 --> 00:20:52,930
I sad imamo pitanje za odgovor.

499
00:20:52,930 --> 00:20:57,840
Moram nekako pokazuju da
smo na kraju niza Daven.

500
00:20:57,840 --> 00:20:59,490
Dakle, samo sam mogao vratiti ga null.

501
00:20:59,490 --> 00:21:02,670
>> Ali što ako imamo Daven a
ime i prezime i koji

502
00:21:02,670 --> 00:21:04,280
je, kao što smo rekli, Davenport?

503
00:21:04,280 --> 00:21:06,970
Pa što ako je Daven
zapravo podniz,

504
00:21:06,970 --> 00:21:08,960
prefiks mnogo duži niz?

505
00:21:08,960 --> 00:21:11,450
Ne možemo baš stalno
kažu ništa ne događa

506
00:21:11,450 --> 00:21:14,410
ići tamo, jer smo mogli
Nikada umetanje riječi poput Davenport

507
00:21:14,410 --> 00:21:15,840
u ovu strukturu podataka

508
00:21:15,840 --> 00:21:19,560
>> Pa što bismo mogli učiniti umjesto toga je
tretirati svaki od tih elemenata

509
00:21:19,560 --> 00:21:22,170
što možda ima dva
elementi unutar njih.

510
00:21:22,170 --> 00:21:24,810
Jedan od njih je pokazivač, doista,
kao što sam bio događaj.

511
00:21:24,810 --> 00:21:27,100
Dakle, svaki od tih kutija
nije samo jedna stanica.

512
00:21:27,100 --> 00:21:29,855
Ali što ako je vrh
one-- dno nečije

513
00:21:29,855 --> 00:21:32,230
će biti nula, jer
nema Davenport samo još.

514
00:21:32,230 --> 00:21:34,197
Što ako jedan vrh
je neka posebna vrijednost?

515
00:21:34,197 --> 00:21:36,530
I to će biti malo
teško je to veličina izvući.

516
00:21:36,530 --> 00:21:38,130
Ali pretpostavljam da je to samo kvačica.

517
00:21:38,130 --> 00:21:38,920
Check.

518
00:21:38,920 --> 00:21:44,230
D--V-E-N je niz
U toj strukturi podataka.

519
00:21:44,230 --> 00:21:48,350
>> U međuvremenu, ako sam imao više prostora
ovdje, što sam mogao učiniti P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
i ja mogao staviti oznaku u čvoru
koja ima slovo T na samom kraju.

521
00:21:52,650 --> 00:21:55,460
Dakle, ovo je masivno
Kompleks izgleda strukturu podataka.

522
00:21:55,460 --> 00:21:57,210
I moj rukopis
Sigurno ne pomaže.

523
00:21:57,210 --> 00:22:00,043
Ali ako sam htio ubaciti nešto
drugo, razmislite što ćemo učiniti.

524
00:22:00,043 --> 00:22:03,370
Ako smo htjeli staviti Davida u,
bismo slijediti istu logiku, D-A-V,

525
00:22:03,370 --> 00:22:08,802
ali sada bih uputiti u iduće
element ne iz E, ali od I. do D.

526
00:22:08,802 --> 00:22:10,760
Tako će biti
više čvorovi u ovom stablu.

527
00:22:10,760 --> 00:22:12,325
Mi ćemo imati poziva malloc više.

528
00:22:12,325 --> 00:22:14,700
Ali ja ne želim napraviti
potpuni nered ovu sliku.

529
00:22:14,700 --> 00:22:17,710
Tako ćemo umjesto da pogledate jedan
koji je bio unaprijed formuliran

530
00:22:17,710 --> 00:22:21,810
kao što je ovaj sa ne dot, dot,
točkice, ali samo skraćeni polja.

531
00:22:21,810 --> 00:22:23,950
No, svaki od čvorova
U ovom stabla ovdje

532
00:22:23,950 --> 00:22:26,700
predstavlja istu stvar--
Niz Ray veličine 26.

533
00:22:26,700 --> 00:22:28,860
>> Ili, ako želimo biti
stvarno pravi sad, što

534
00:22:28,860 --> 00:22:30,790
Ako nečije ime kao
apostrof, neka je

535
00:22:30,790 --> 00:22:35,560
Pretpostavljamo da svaki čvor zapravo ima
kao što je 27 indeksa u njemu, a ne samo 26.

536
00:22:35,560 --> 00:22:42,020
Dakle, ovo je sada će biti podaci
Struktura naziva trie-- T-R-I-e.

537
00:22:42,020 --> 00:22:46,120
Trie, koji je navodno
povijesno pametan ime za drvo

538
00:22:46,120 --> 00:22:49,040
koji je optimiziran za
dohvat, što je, naravno,

539
00:22:49,040 --> 00:22:50,870
napisane s I-E pa to je Trie.

540
00:22:50,870 --> 00:22:52,710
Ali to je povijest Trie.

541
00:22:52,710 --> 00:22:55,860
>> Dakle Trie je ovo drvo poput podataka
Struktura poput obiteljskog stabla

542
00:22:55,860 --> 00:22:57,510
koji u konačnici se ponaša kao da je.

543
00:22:57,510 --> 00:23:00,890
I ovdje je samo još jedan primjer
cijela hrpa tuđih imena.

544
00:23:00,890 --> 00:23:03,540
No, pitanje je sad
pri ruci je ono što imamo

545
00:23:03,540 --> 00:23:08,070
dobili smo uvođenjem nedvojbeno više
složenoj strukturi podataka, i on,

546
00:23:08,070 --> 00:23:09,870
iskreno, koji koristi mnogo memorije.

547
00:23:09,870 --> 00:23:11,703
>> Jer iako,
u ovom trenutku, ja sam samo

548
00:23:11,703 --> 00:23:15,050
korištenjem D's pokazivač i
I V i Es i NS,

549
00:23:15,050 --> 00:23:16,700
Ja sam gubit ispitati kritički od puno memorije.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
Ali gdje sam provesti jedan resurs,
Ja obično ne dobiti natrag drugog.

552
00:23:22,660 --> 00:23:26,020
Dakle, ako sam trošiti više prostora,
što je vjerojatno nada?

553
00:23:26,020 --> 00:23:27,407
To ću trošiti manje što?

554
00:23:27,407 --> 00:23:28,240
PUBLIKA: Manje vremena.

555
00:23:28,240 --> 00:23:28,990
DAVID Malan: Vrijeme.

556
00:23:28,990 --> 00:23:30,320
Sad zašto bi to moglo biti?

557
00:23:30,320 --> 00:23:33,880
Pa, ono što je umetanje
vrijeme, u smislu velikog O sada,

558
00:23:33,880 --> 00:23:37,660
naziva kao Daven
ili Davenport ili David?

559
00:23:37,660 --> 00:23:39,340
Pa, Daven je pet koraka.

560
00:23:39,340 --> 00:23:42,350
Davenport će biti devet koraka,
tako da će biti još nekoliko koraka.

561
00:23:42,350 --> 00:23:44,250
David bi biti pet koraka kao dobro.

562
00:23:44,250 --> 00:23:47,230
Dakle, to su konkretni
brojeve, ali sigurno postoji

563
00:23:47,230 --> 00:23:49,550
gornja granica na
duljina nečijeg imena.

564
00:23:49,550 --> 00:23:52,240
I doista, u problemu
seta pet specifikacije,

565
00:23:52,240 --> 00:23:54,050
ćemo predložiti
da je to nešto

566
00:23:54,050 --> 00:23:55,470
To je 40-neke-ak znakova.

567
00:23:55,470 --> 00:23:58,180
>> Realno, nitko nema
beskonačno dugo ime,

568
00:23:58,180 --> 00:24:01,542
što će reći da je duljina
ime ili duljina niza smo mogli

569
00:24:01,542 --> 00:24:03,750
ima sigurno stanje
Struktura je nedvojbeno što?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
To je konstanta.

572
00:24:06,250 --> 00:24:06,430
Pravo?

573
00:24:06,430 --> 00:24:09,310
To bi moglo biti velika stalna poput
40-nešto, ali je konstantan.

574
00:24:09,310 --> 00:24:13,752
I to nema ovisnosti o tome koliko
ostali su imena u ovoj strukturi podataka.

575
00:24:13,752 --> 00:24:15,460
Drugim riječima, ako sam
htjela sada umetanje

576
00:24:15,460 --> 00:24:20,540
Colton ili Gabriel ili Rob ili Zamyla ili
Alison ili Belinda, ili bilo koja druga imena

577
00:24:20,540 --> 00:24:23,940
od osoblja u ovoj podataka
struktura, je trčanje vrijeme

578
00:24:23,940 --> 00:24:26,750
umetanja druga imena
će biti uopće utjecali

579
00:24:26,750 --> 00:24:30,220
koliko mnogih drugih elemenata
U strukturi podataka već?

580
00:24:30,220 --> 00:24:31,040
To nije.

581
00:24:31,040 --> 00:24:31,540
Pravo?

582
00:24:31,540 --> 00:24:36,150
Budući da smo učinkovito korištenje
ovaj višeslojni hash tablicu.

583
00:24:36,150 --> 00:24:38,280
A vrijeme rada
bilo koji od ovih operacija

584
00:24:38,280 --> 00:24:41,510
ne ovisi o broju
Elementi koji su u strukturi podataka

585
00:24:41,510 --> 00:24:43,090
ili da na kraju ide
da u strukturi podataka,

586
00:24:43,090 --> 00:24:44,714
ali na duljinu što posebno?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> Niz se
umetnuta, koji ne čine

589
00:24:49,200 --> 00:24:52,580
ovo asimptotski stalna
time-- veliki O jedne.

590
00:24:52,580 --> 00:24:54,720
I iskreno, samo u
stvarnom svijetu, to

591
00:24:54,720 --> 00:24:58,380
znači umetanje Daven ime traje
kao pet koraka, ili Davenport devet

592
00:24:58,380 --> 00:25:00,100
koraka, ili je David pet koraka.

593
00:25:00,100 --> 00:25:03,071
To je prilično prokleto malo vremena trčanje.

594
00:25:03,071 --> 00:25:05,320
I, doista, to je vrlo
dobra stvar, pogotovo kad

595
00:25:05,320 --> 00:25:08,126
to ne ovisi o ukupno
Broj elemenata u tamo.

596
00:25:08,126 --> 00:25:10,500
Pa kako bismo mogli provesti taj
vrsta strukture u kodu?

597
00:25:10,500 --> 00:25:12,900
To je malo više
kompleksna, ali još uvijek je

598
00:25:12,900 --> 00:25:15,050
Samo primjena
osnovni građevni blokovi.

599
00:25:15,050 --> 00:25:17,830
Idem redefinirati
nas čvor kako slijedi:

600
00:25:17,830 --> 00:25:21,100
bool nazvao word-- i to
bi se moglo nazvati ništa.

601
00:25:21,100 --> 00:25:23,970
No bool predstavlja
ono što sam nacrtao kao kvačicom.

602
00:25:23,970 --> 00:25:24,490
Da.

603
00:25:24,490 --> 00:25:26,720
To je kraj niza
U toj strukturi podataka.

604
00:25:26,720 --> 00:25:30,702
>> I, naravno, čvor zvijezda
tu se odnosi na djecu.

605
00:25:30,702 --> 00:25:32,410
I, doista, baš kao i
obiteljsko stablo, što

606
00:25:32,410 --> 00:25:34,370
bi razmotriti čvorova
koji su visi

607
00:25:34,370 --> 00:25:36,920
dna neke roditelja
element biti djeca.

608
00:25:36,920 --> 00:25:40,510
I tako djeca će
se niz 27, 27 jedan

609
00:25:40,510 --> 00:25:41,680
samo se za apostrof.

610
00:25:41,680 --> 00:25:43,390
Idemo sortiranje
o posebnom slučaju tog.

611
00:25:43,390 --> 00:25:45,400
Tako možete imati sigurno
Imena s apostrofe.

612
00:25:45,400 --> 00:25:47,399
Možda čak i crtica trebala
ići tamo, ali ćete

613
00:25:47,399 --> 00:25:50,330
vidjeti u p setu 5 mi samo njegu
o pismima i apostrofe.

614
00:25:50,330 --> 00:25:52,990
>> A onda kako se predstavljate
Sama struktura podataka?

615
00:25:52,990 --> 00:25:56,454
Kako se predstavlja korijen
ove Trie, da tako kažem?

616
00:25:56,454 --> 00:25:59,620
Pa, baš kao s popisa povezane, što
potreban pokazivač na prvi element.

617
00:25:59,620 --> 00:26:04,270
Uz Trie trebate samo jedan
pokazivač na korijen ove Trie.

618
00:26:04,270 --> 00:26:07,290
A od tamo možete hash
svoj put prema dolje sve dublje i dublje

619
00:26:07,290 --> 00:26:10,460
na svaki drugi čvor u strukturi.

620
00:26:10,460 --> 00:26:13,440
Tako jednostavno s ovom kantom
zastupamo tu struct.

621
00:26:13,440 --> 00:26:15,877
>> Sada Meanwhile-- Oh, pitanje.

622
00:26:15,877 --> 00:26:17,220
>> PUBLIKA: Što je bool riječ?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Malan: Bool riječ
upravo to C utjelovljenje

624
00:26:20,490 --> 00:26:22,920
onoga što sam opisao
U ovoj kutiji ovdje, kada je

625
00:26:22,920 --> 00:26:26,000
Počela sam cijepanje svaki od
niz elemenata je u dva dijela.

626
00:26:26,000 --> 00:26:27,600
Jedan je pokazivač na sljedeći čvor.

627
00:26:27,600 --> 00:26:30,280
Drugi mora biti
nešto poput potvrdni okvir

628
00:26:30,280 --> 00:26:33,770
reći da, postoji
Riječ Daven da se ovdje završava,

629
00:26:33,770 --> 00:26:35,610
zato što ne želimo,
u ovom trenutku, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Iako Dave će biti
legitimna riječ, on nije u Trie

631
00:26:39,320 --> 00:26:39,830
još.

632
00:26:39,830 --> 00:26:40,950
A D Nije riječ.

633
00:26:40,950 --> 00:26:42,770
I D-nije riječ ili naziv.

634
00:26:42,770 --> 00:26:45,020
Tako je kvačicom
ukazuje samo jednom vas

635
00:26:45,020 --> 00:26:48,190
hit ove čvor
Prethodni put znakova

636
00:26:48,190 --> 00:26:50,700
zapravo niz koji ste umetnuli.

637
00:26:50,700 --> 00:26:53,660
Tako da je sve bool
tu se radi za nas.

638
00:26:53,660 --> 00:26:55,500
>> Ima li još pitanja o pokušaja?

639
00:26:55,500 --> 00:26:56,215
Da.

640
00:26:56,215 --> 00:26:58,035
>> PUBLIKA: Što je preklapanja?

641
00:26:58,035 --> 00:26:59,945
Što ako imate Dave i Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID Malan: Savršeno.

643
00:27:00,820 --> 00:27:02,580
Što ako imate Dave i Daven?

644
00:27:02,580 --> 00:27:06,240
Dakle, ako ćemo ubaciti, kažu nadimak,
za David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
To je zapravo super jednostavna.

647
00:27:08,700 --> 00:27:10,325
Tako smo samo će potrajati četiri koraka.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-E-V-. I što moram
ne jednom sam pogodio taj četvrti čvor?

650
00:27:15,847 --> 00:27:16,680
Samo ću provjeriti.

651
00:27:16,680 --> 00:27:18,000
Već smo dobro ide.

652
00:27:18,000 --> 00:27:18,840
Gotovo.

653
00:27:18,840 --> 00:27:19,750
Četiri koraka.

654
00:27:19,750 --> 00:27:21,590
Konstantna vrijeme asimptotski.

655
00:27:21,590 --> 00:27:26,300
I sada smo pokazali da i Dave
i Daven su žice u strukturi.

656
00:27:26,300 --> 00:27:27,710
Dakle, nije problem.

657
00:27:27,710 --> 00:27:30,200
I primijetiti kako prisutnost
od Daven ne čine ga

658
00:27:30,200 --> 00:27:34,750
uzeti više vremena ili manje
Vrijeme za Dave i obrnuto.

659
00:27:34,750 --> 00:27:36,000
>> Pa što još možemo sada učiniti?

660
00:27:36,000 --> 00:27:40,680
Koristili smo tu metaforu prije
od ladica predstavlja nešto.

661
00:27:40,680 --> 00:27:43,380
No, ispada da
snop ladica je zapravo

662
00:27:43,380 --> 00:27:47,187
demonstrativni drugog apstraktnog podataka
type-- višu razinu strukturu podataka

663
00:27:47,187 --> 00:27:49,770
da je na kraju dana je samo
kao polje ili popis povezan

664
00:27:49,770 --> 00:27:50,970
ili nešto više svjetovnim.

665
00:27:50,970 --> 00:27:53,270
No, to je još zanimljivije
konceptualni pojam.

666
00:27:53,270 --> 00:27:56,440
Stog, kao što je to
ladice ovdje u Mather,

667
00:27:56,440 --> 00:27:58,750
Nazivaju se
Samo that-- hrpu.

668
00:27:58,750 --> 00:28:02,540
>> I u ovoj vrsti strukture podataka
imate dva operations--

669
00:28:02,540 --> 00:28:05,880
imate jedan zove poticaj za
dodao nešto na stog,

670
00:28:05,880 --> 00:28:08,320
poput stavljanja još jednu ladicu
natrag na vrhu dimnjaka.

671
00:28:08,320 --> 00:28:11,350
I onda pop, što vam znači
uzeti vrhunski ladice off.

672
00:28:11,350 --> 00:28:16,210
No, ono što je ključno o stog je da
to je dobio ovu neobičnu karakteristiku.

673
00:28:16,210 --> 00:28:19,560
Kao blagovaonice osoblja
preraspodjela ladice za sljedeći obrok,

674
00:28:19,560 --> 00:28:21,380
što će biti
Istina o tome kako studenata

675
00:28:21,380 --> 00:28:22,856
interakciju s ove strukture podataka?

676
00:28:22,856 --> 00:28:24,480
PUBLIKA: Oni će se pojaviti jedan off.

677
00:28:24,480 --> 00:28:26,550
DAVID Malan: Oni će
pop One, nadamo se do vrha.

678
00:28:26,550 --> 00:28:28,910
Inače to je samo vrsta glupo
ići sve do dna.

679
00:28:28,910 --> 00:28:29,070
Pravo?

680
00:28:29,070 --> 00:28:31,620
Struktura podataka zapravo ne dopuštaju
da iskoristite dno ladice najmanje

681
00:28:31,620 --> 00:28:32,520
lako.

682
00:28:32,520 --> 00:28:35,040
Tako da je ovo zanima
Objekt na stog

683
00:28:35,040 --> 00:28:39,730
da je posljednja stavka u je
će biti prvi van.

684
00:28:39,730 --> 00:28:43,400
A računalni znanstvenici nazivaju
to LIFO-- trajati u, prvi van.

685
00:28:43,400 --> 00:28:45,540
I to zapravo nema
zanimljive aplikacije.

686
00:28:45,540 --> 00:28:50,090
To ne mora nužno biti tako očite kao što neki
drugi, ali se može doista biti korisno,

687
00:28:50,090 --> 00:28:54,040
i to može, doista, biti proveden
u nekoliko različitih načina.

688
00:28:54,040 --> 00:28:58,550
>> Tako je jedan, i zapravo, neka
ja ne zaroniti u to.

689
00:28:58,550 --> 00:28:59,860
Idemo to učiniti umjesto.

690
00:28:59,860 --> 00:29:03,700
Pogledajmo jedan koji je gotovo
ista ideja, ali to je malo ljepša.

691
00:29:03,700 --> 00:29:04,200
Pravo?

692
00:29:04,200 --> 00:29:07,560
Ako ste jedan od tih navijačkih dječaka ili
djevojke koja stvarno voli Apple proizvode

693
00:29:07,560 --> 00:29:10,130
a vi se probudio u 3:00
da se postroje u nekom dućanu

694
00:29:10,130 --> 00:29:14,150
dobiti najnovije iPhone,
Možda su se okupili kao što je ovaj.

695
00:29:14,150 --> 00:29:15,800
>> Sada je red vrlo namjerno zove.

696
00:29:15,800 --> 00:29:18,190
To je crta, jer postoji
neke pravičnosti na njega.

697
00:29:18,190 --> 00:29:18,690
Pravo?

698
00:29:18,690 --> 00:29:21,690
To bi vrsta sisao, ako ste
stigli prvi na Apple Store

699
00:29:21,690 --> 00:29:25,700
ali vi ste učinkovito najniži
ladicu jer Apple zaposlenicima onda

700
00:29:25,700 --> 00:29:28,189
pop posljednju osobu koja
zapravo je dobio u redu.

701
00:29:28,189 --> 00:29:31,230
Dakle, dimnjaka i redove, iako to
funkcionalno oni vrsta u same--

702
00:29:31,230 --> 00:29:33,105
to je samo ova zbirka
sredstava koji je

703
00:29:33,105 --> 00:29:36,210
će rasti i shrink-- tu je
to pravednost aspekt na njega,

704
00:29:36,210 --> 00:29:39,634
barem u stvarnom svijetu,
gdje su poslovi vježbate

705
00:29:39,634 --> 00:29:40,800
bitno razlikuju.

706
00:29:40,800 --> 00:29:43,360
Stack-- red
rather-- je rekao da su

707
00:29:43,360 --> 00:29:45,320
dvije operacije: n red i d red.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
Ili ih možete nazvati
bilo koji broj stvari.

710
00:29:48,090 --> 00:29:50,770
Ali samo želite snimiti
spoznaja da je netko dodao

711
00:29:50,770 --> 00:29:53,230
a jedan je u konačnici oduzimanjem.

712
00:29:53,230 --> 00:29:58,840
>> Sada ispod haube, i stog
i red bi mogao biti proveden kako?

713
00:29:58,840 --> 00:30:01,390
Nećemo ulaziti u kodeksu
Zato što viša razina

714
00:30:01,390 --> 00:30:03,387
Ideja je vrsta očitija.

715
00:30:03,387 --> 00:30:04,470
Mislim, što da i ljudi?

716
00:30:04,470 --> 00:30:07,030
Ako sam prva osoba na Apple
Spremite i to je ulazna vrata,

717
00:30:07,030 --> 00:30:08,130
znaš, ja ću stajati ovdje.

718
00:30:08,130 --> 00:30:09,750
I sljedeća osoba je
će stajati ovdje.

719
00:30:09,750 --> 00:30:11,500
I sljedeća osoba je
će stajati ovdje.

720
00:30:11,500 --> 00:30:13,792
Pa što struktura podataka
sama posuđuje na red?

721
00:30:13,792 --> 00:30:14,542
>> PUBLIKA: red.

722
00:30:14,542 --> 00:30:15,667
DAVID Malan: Pa, red.

723
00:30:15,667 --> 00:30:16,390
Naravno.

724
00:30:16,390 --> 00:30:16,920
Što još?

725
00:30:16,920 --> 00:30:17,600
>> PUBLIKA: Popis povezani.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Malan: povezani
popis bi mogao provesti.

727
00:30:18,990 --> 00:30:22,500
A popis vezan je lijepo, jer tada
to može rasti proizvoljno dugo razliku

728
00:30:22,500 --> 00:30:24,880
da ima neki fiksni broj
ljudi u trgovini.

729
00:30:24,880 --> 00:30:27,030
No, možda fiksni broj
mjesta je legitimna.

730
00:30:27,030 --> 00:30:30,350
Jer ako su samo kao i 20
iPhonea prvog dana, možda

731
00:30:30,350 --> 00:30:33,930
što im je potrebno samo niz veličine
20 zastupati taj red čekanja, koji

732
00:30:33,930 --> 00:30:37,070
samo je sada reći nakon što počnemo govoriti
o tim problemima višim razinama,

733
00:30:37,070 --> 00:30:38,890
možete ga provesti
na bilo koji broj načina.

734
00:30:38,890 --> 00:30:42,030
I tu je vjerojatno samo ide
biti trade off u prostoru i vremenu

735
00:30:42,030 --> 00:30:43,950
ili samo u svoj vlastiti kod složenosti.

736
00:30:43,950 --> 00:30:45,380
>> Što je stog?

737
00:30:45,380 --> 00:30:48,190
Pa, stog, vidjeli smo previše
može biti samo ove ladice.

738
00:30:48,190 --> 00:30:50,007
A ti bi mogao provesti ovaj niz.

739
00:30:50,007 --> 00:30:53,090
No, u nekom trenutku ako koristite niz,
što će se dogoditi s ladicama

740
00:30:53,090 --> 00:30:54,173
pokušavate staviti dolje?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
U redu.

743
00:30:55,670 --> 00:30:57,490
Vi ste samo ide na
moći ići tako visoko.

744
00:30:57,490 --> 00:31:00,156
I mislim da je u Mather su
zapravo uvučeni u taj otvor.

745
00:31:00,156 --> 00:31:01,950
Dakle, istina, to je gotovo
kao Mather koristi

746
00:31:01,950 --> 00:31:03,783
niz fiksne veličine,
jer možete samo

747
00:31:03,783 --> 00:31:08,302
stane toliko ladice u tom otvaranju u
Zid dolje ljudi koljena.

748
00:31:08,302 --> 00:31:10,010
I tako bi moglo biti
rekao je da se polje,

749
00:31:10,010 --> 00:31:14,300
ali smo svakako mogli provesti da
općenitije s popisa povezane.

750
00:31:14,300 --> 00:31:16,390
>> Pa, što je s drugom strukturom podataka?

751
00:31:16,390 --> 00:31:18,760
Dopustite mi podići jedan drugi vizualni ovdje.

752
00:31:18,760 --> 00:31:24,710
Nešto kao što je o tome kako je ovaj ovdje?

753
00:31:24,710 --> 00:31:28,920
Zašto bi moglo biti korisno imati ne
nešto kao fantazija kao Trie, koji

754
00:31:28,920 --> 00:31:32,370
smo vidjeli imali ove vrlo široke čvorova,
svaki od kojih je u nizu?

755
00:31:32,370 --> 00:31:35,740
Ali što ako mi se nešto više
jednostavno, kao stara škola obiteljskog stabla,

756
00:31:35,740 --> 00:31:38,110
svaki od čvorova čije ovdje
je upravo spremate broj.

757
00:31:38,110 --> 00:31:42,180
Umjesto imena ili potomak
je upravo spremate broj kao što je ovaj.

758
00:31:42,180 --> 00:31:45,250
>> Pa, žargonu koristimo u
strukture podataka je oba pokušaja

759
00:31:45,250 --> 00:31:49,510
i drveće, gdje Trie, opet,
Samo onaj čije čvorovi su nizovi,

760
00:31:49,510 --> 00:31:51,680
je još uvijek ono što bi moglo
koristiti iz osnovnoj školi

761
00:31:51,680 --> 00:31:53,860
kada se obitelj
tree-- listovi i korijen

762
00:31:53,860 --> 00:31:57,250
stabla i djecu
roditelja i njihove braće i sestara.

763
00:31:57,250 --> 00:32:03,670
I možemo provesti stablo,
na primjer, kao što je to jednostavno.

764
00:32:03,670 --> 00:32:07,420
Stabla, ako je to kao čvor, jedan od
ti krugovi koji ima broj,

765
00:32:07,420 --> 00:32:09,947
to neće imati
jedan pointer, nego dva.

766
00:32:09,947 --> 00:32:11,780
I čim ste dodali
Drugi pokazivač, što

767
00:32:11,780 --> 00:32:13,905
zapravo može sada napraviti svojevrsni
od dvodimenzionalni podataka

768
00:32:13,905 --> 00:32:14,780
strukture u memoriji.

769
00:32:14,780 --> 00:32:16,660
Slično kao dvodimenzionalni
Niz, možete

770
00:32:16,660 --> 00:32:18,904
ima kakav dvodimenzionalne
povezani popisi, ali one

771
00:32:18,904 --> 00:32:20,820
da slijede uzorak
tamo gdje je nema ciklusa.

772
00:32:20,820 --> 00:32:24,487
To je doista stablo s jednim
djed i baka put ovdje, a zatim

773
00:32:24,487 --> 00:32:27,320
neki roditelji i djeca i
unuci i praunuci.

774
00:32:27,320 --> 00:32:28,370
i tako dalje.

775
00:32:28,370 --> 00:32:32,390
>> No, ono što je stvarno uredan o tome previše,
samo da vas zafrkavati s malo koda,

776
00:32:32,390 --> 00:32:35,370
Opoziv rekurzija od
neko vrijeme natrag, pri čemu

777
00:32:35,370 --> 00:32:38,220
što napisati funkciju koja se poziva.

778
00:32:38,220 --> 00:32:41,140
Ovo je lijepa prilika
provesti nešto

779
00:32:41,140 --> 00:32:42,920
kao što rekurzije, jer smatram to.

780
00:32:42,920 --> 00:32:43,860
>> To je stablo.

781
00:32:43,860 --> 00:32:48,040
I ja sam bio malo analni s načinom
Stavio sam se cijeli brojevi na ulicu.

782
00:32:48,040 --> 00:32:51,020
I to toliko da je posebna
name-- binarno pretraživanje stablo.

783
00:32:51,020 --> 00:32:53,460
Sada smo čuli binarna
traženje, ali može vas

784
00:32:53,460 --> 00:32:55,180
raditi unatrag od ova stvar imena?

785
00:32:55,180 --> 00:32:59,280
Što je uzorak kako sam
umetnuli prirodnih brojeva u ovom stablu?

786
00:32:59,280 --> 00:33:00,696
To nije proizvoljna.

787
00:33:00,696 --> 00:33:01,570
Postoji neki obrazac.

788
00:33:01,570 --> 00:33:02,090
Da.

789
00:33:02,090 --> 00:33:03,370
>> PUBLIKA: Manji one na lijevoj strani.

790
00:33:03,370 --> 00:33:03,690
>> DAVID Malan: Da.

791
00:33:03,690 --> 00:33:05,062
Manji one su na lijevoj strani.

792
00:33:05,062 --> 00:33:06,270
Veće one su na desnoj strani.

793
00:33:06,270 --> 00:33:12,940
Takav da je istina izjava
roditelj je veća od njegove lijeve dijete,

794
00:33:12,940 --> 00:33:14,850
ali manje od njegove desne djeteta.

795
00:33:14,850 --> 00:33:17,750
I to samo još
rekurzivna verbalnog definicija

796
00:33:17,750 --> 00:33:20,500
jer možete podnijeti zahtjev da se
Ista logika za svaki čvor

797
00:33:20,500 --> 00:33:23,080
i to samo dno
out, osnovni scenarij, ako vas

798
00:33:23,080 --> 00:33:25,740
će, kada se zabio u
lišće, da tako kažemo,

799
00:33:25,740 --> 00:33:28,580
gdje dopust nema djece i dalje.

800
00:33:28,580 --> 00:33:30,614
>> Sada kako možda ćete naći broj 44?

801
00:33:30,614 --> 00:33:32,280
Ti bi početi u korijenu i reći, hm.

802
00:33:32,280 --> 00:33:35,690
55 nije 44 I ja želim ići
pravo ili ne želim ići lijevo?

803
00:33:35,690 --> 00:33:37,190
Pa, očito želite ići lijevo.

804
00:33:37,190 --> 00:33:40,060
I to je baš kao i telefona
Knjiga je primjer u binarnom potrazi

805
00:33:40,060 --> 00:33:41,099
općenito.

806
00:33:41,099 --> 00:33:43,390
No, mi smo ga provedbi
Sada malo više dinamički

807
00:33:43,390 --> 00:33:45,339
nego niz mogao dopustiti.

808
00:33:45,339 --> 00:33:48,130
A u stvari, ako želite izgledati
u kodu, na prvi pogled sigurno.

809
00:33:48,130 --> 00:33:49,671
To izgleda kao cijela hrpa linija.

810
00:33:49,671 --> 00:33:51,220
Ali, to je lijepo jednostavna.

811
00:33:51,220 --> 00:33:54,490
Ako želite provesti funkciju
zove pretragu čija je svrha u životu

812
00:33:54,490 --> 00:33:57,290
je u potrazi za vrijednošću
kao što je n cijeli broj,

813
00:33:57,290 --> 00:34:01,756
a vi ste prošli u jednom pointer--
pokazivač na čvoru korijena,

814
00:34:01,756 --> 00:34:04,380
a, tog stabla od kojih
možete pristupiti sve ostalo,

815
00:34:04,380 --> 00:34:08,850
primijetiti kako se izravno
možete provesti logiku.

816
00:34:08,850 --> 00:34:10,880
Ako stablo je null,
očito da to ne postoji.

817
00:34:10,880 --> 00:34:11,880
Ajmo se vratiti false.

818
00:34:11,880 --> 00:34:12,000
Pravo?

819
00:34:12,000 --> 00:34:14,040
Ako ga predati ništa,
nema ničega.

820
00:34:14,040 --> 00:34:17,900
>> Inače, ako je n manji od
Stablo strelica n- sada strijela n,

821
00:34:17,900 --> 00:34:20,670
podsjetiti uveli smo super
Kratko drugi dan,

822
00:34:20,670 --> 00:34:25,100
a to samo znači de-reference na
pokazivač i pogledajte polju zvanom n.

823
00:34:25,100 --> 00:34:27,690
Dakle, to znači otići tamo i
pogledajte polju zvanom n.

824
00:34:27,690 --> 00:34:33,810
Dakle, ako n, vrijednost koju si dao, manje
od vrijednosti na cijeli broj stabala,

825
00:34:33,810 --> 00:34:35,449
gdje želiš ići?

826
00:34:35,449 --> 00:34:36,389
S lijeve strane.

827
00:34:36,389 --> 00:34:37,780
>> Dakle primijetiti rekurzija.

828
00:34:37,780 --> 00:34:39,860
Ja returning-- nije istina.

829
00:34:39,860 --> 00:34:40,989
Ne lažna.

830
00:34:40,989 --> 00:34:45,670
Ja sam se vraćaju bez obzira na odgovor
je od poziva do sebe, prolazeći

831
00:34:45,670 --> 00:34:50,100
opet nje, što je suvišno,
ali ono što je sada nešto drugačije?

832
00:34:50,100 --> 00:34:51,989
Kako sam ja problem što manja?

833
00:34:51,989 --> 00:34:54,920
Ja sam u prolazu, kao drugo
argument, a ne korijen stabla,

834
00:34:54,920 --> 00:34:59,616
ali lijeva dijete u ovom slučaju.

835
00:34:59,616 --> 00:35:00,990
Tako sam prolazeći u lijevom dijete.

836
00:35:00,990 --> 00:35:04,720
>> U međuvremenu, ako je n veći od
čvor Ja sam trenutno gledajući,

837
00:35:04,720 --> 00:35:06,690
Tražim desnoj strani.

838
00:35:06,690 --> 00:35:10,880
Inače, ako je stablo nije null, i
Ako se element ne lijevo

839
00:35:10,880 --> 00:35:13,240
i to ne na desno,
ono što je predivno slučaj?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Mi zapravo našli čvor u
pitanje, pa smo se vratili istinito.

842
00:35:18,440 --> 00:35:21,490
>> Dakle, upravo smo zagrebali površinu
Sada neki od tih struktura podataka.

843
00:35:21,490 --> 00:35:24,370
U Problem postaviti pet vi ćete
istražite to još dalje,

844
00:35:24,370 --> 00:35:27,250
a vi ćete dati svoj dizajn
izbor kako to ide o tome.

845
00:35:27,250 --> 00:35:30,250
Ono što bih želio zaključiti na
je samo drugi teaser 30

846
00:35:30,250 --> 00:35:32,080
onoga što čeka sljedeći tjedan i izvan nje.

847
00:35:32,080 --> 00:35:35,390
>> Kao što smo begin-- srećom li možda
think-- naš prijelaz polako

848
00:35:35,390 --> 00:35:38,680
iz svijeta C i niže
detalji provedbe razini,

849
00:35:38,680 --> 00:35:42,090
u svijetu u kojem možemo uzeti zdravo za
odobriti da netko drugi ima napokon

850
00:35:42,090 --> 00:35:44,010
provoditi ove podatke
strukture za nas,

851
00:35:44,010 --> 00:35:47,570
pa ćemo početi razumjeti
stvarni svijet sredstva za provedbu

852
00:35:47,570 --> 00:35:50,560
web-based programa i
web općenitije

853
00:35:50,560 --> 00:35:52,910
a također je vrlo sigurnost
implikacije da smo samo

854
00:35:52,910 --> 00:35:54,850
počeli ispočetka površinu.

855
00:35:54,850 --> 00:35:57,320
Evo što nas čeka
U danima koji dolaze.

856
00:35:57,320 --> 00:36:00,480
>> [Video reprodukcije]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -On Je došao s porukom,
s protokolom sve svoje.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Došao je na svijet okrutno
firewall, usmjerivači, nemilosrdan

861
00:36:30,894 --> 00:36:33,368
i opasnosti daleko gore od smrti.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
On je brzo.

864
00:36:36,236 --> 00:36:37,980
On je jak.

865
00:36:37,980 --> 00:36:42,830
On je TCP / IP, a on je dobio svoju adresu.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Ratnici Mreže".

868
00:36:48,074 --> 00:36:49,660
[END reprodukciju videozapisa]

869
00:36:49,660 --> 00:36:50,910
DAVID Malan: Dolazi sljedeći tjedan.

870
00:36:50,910 --> 00:36:51,880
Mi ćemo vas vidjeti onda.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[Video reprodukcije]

873
00:36:56,060 --> 00:36:59,240
-I Sada, "Deep Misli"
po Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Uvijek počinje
predavanja sa "sve u redu."

876
00:37:05,820 --> 00:37:08,750
Zašto ne, "Evo rješenje
na ovotjednom skupu problema "

877
00:37:08,750 --> 00:37:12,180
ili "dajemo sve od tebe?"

878
00:37:12,180 --> 00:37:13,380
[Laughing]

879
00:37:13,380 --> 00:37:15,530
[END reprodukciju videozapisa]