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

2
00:00:00,500 --> 00:00:03,340
[MUSIC JOC]

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

4
00:00:11,020 --> 00:00:14,010
>> DAVID MALAN: Aceasta este CS50.

5
00:00:14,010 --> 00:00:18,090
Și acest lucru este atât de început și
end-- ca literally-- aproape de sfârșitul

6
00:00:18,090 --> 00:00:18,825
de sase saptamani.

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

8
00:00:20,030 --> 00:00:22,640
>> M-am gândit împărtășesc o
pic de un fapt distracție.

9
00:00:22,640 --> 00:00:25,370
Am scos asta de la un
Date semestru dribleze cuprinse.

10
00:00:25,370 --> 00:00:29,710
Vă amintiți că vă cerem pe fiecare
Formularul set p, dacă ați vizionat on-line

11
00:00:29,710 --> 00:00:31,580
sau dacă ați participat în persoană.

12
00:00:31,580 --> 00:00:33,020
Și aici este de date.

13
00:00:33,020 --> 00:00:34,710
Așa că astăzi a fost foarte mult previzibil.

14
00:00:34,710 --> 00:00:37,126
Dar ne-am dorit să-și petreacă un pic
de timp cu tine, totuși.

15
00:00:37,126 --> 00:00:40,599
Vrea cineva să presupunem ce acest
grafic este atât de jaggy, sus în jos, în sus în jos,

16
00:00:40,599 --> 00:00:41,265
astfel în mod constant?

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

18
00:00:42,980 --> 00:00:45,130
Ce face fiecare dintre vârfurilor
și jgheaburi reprezinta?

19
00:00:45,130 --> 00:00:46,005
>> Audiența: [inaudibil]

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

21
00:00:47,002 --> 00:00:47,835
DAVID MALAN: Într-adevăr.

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

23
00:00:50,900 --> 00:00:55,480
Și mai amuzant, Doamne ferește,
avem o prelegere pe o zi de vineri

24
00:00:55,480 --> 00:00:58,960
la începutul semestrului,
asta e ceea ce vedem întâmpla.

25
00:00:58,960 --> 00:01:03,430
Așa că astăzi, ne împărtășim într-un pic
mai multe despre structuri de date.

26
00:01:03,430 --> 00:01:06,660
Și pentru a vă oferi mai mult de un solid
model mental pentru probleme la cinci,

27
00:01:06,660 --> 00:01:07,450
care este acum afară.

28
00:01:07,450 --> 00:01:10,817
Greșeli de ortografie, care, vom
tu dai un fișier text oarecare 100.000

29
00:01:10,817 --> 00:01:12,650
plus cuvinte în limba engleză, și
ai de gând să aibă

30
00:01:12,650 --> 00:01:17,770
să dau seama cum să le încărcați inteligent
în memorie, în memoria RAM, folosind unele date

31
00:01:17,770 --> 00:01:19,330
structura de alegerea ta.

32
00:01:19,330 --> 00:01:22,470
>> Acum, o astfel de structură de date ar putea
fi, dar probabil nu ar trebui să fie,

33
00:01:22,470 --> 00:01:25,630
lista destul de simplist legate,
pe care am introdus ultima dată.

34
00:01:25,630 --> 00:01:29,220
Și o listă legat avut cel puțin
un avantaj pe o matrice.

35
00:01:29,220 --> 00:01:32,096
Ce este un avantaj al
o listă legată, fără îndoială?

36
00:01:32,096 --> 00:01:32,950
>> Audiența: de inserție.

37
00:01:32,950 --> 00:01:33,908
>> DAVID MALAN: de inserție.

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

39
00:01:34,155 --> 00:01:35,196
Ce vrei să spui cu asta?

40
00:01:35,196 --> 00:01:37,872
>> Audiența: Oriunde de-a lungul
lista [neauzit].

41
00:01:37,872 --> 00:01:38,770
>> DAVID MALAN: Bun.

42
00:01:38,770 --> 00:01:42,090
Astfel încât să puteți introduce un element de oriunde
vrei în mijlocul listei

43
00:01:42,090 --> 00:01:45,490
fără a fi nevoie să shuffle nimic,
care am ajuns la concluzia, în opțiunea de sortare nostru

44
00:01:45,490 --> 00:01:47,630
discuții, nu este
neapărat un lucru bun,

45
00:01:47,630 --> 00:01:51,200
pentru că este nevoie de timp pentru a trece de fapt
toate aceste oameni la stânga sau la dreapta.

46
00:01:51,200 --> 00:01:55,540
Și așa cu o listă legată, puteți
doar aloca cu malloc, un nou nod,

47
00:01:55,540 --> 00:01:58,385
și apoi să actualizeze un cuplu de
pointers-- două, trei operațiuni max--

48
00:01:58,385 --> 00:02:01,480
și suntem capabili să Fanta de cineva
în orice destinație într-o listă.

49
00:02:01,480 --> 00:02:03,550
>> Ce altceva era avantajos
despre o listă legat?

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
>> Audiența: [inaudibil]

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

54
00:02:07,538 --> 00:02:08,413
DAVID MALAN: Perfect.

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

56
00:02:10,590 --> 00:02:11,090
Perfect.

57
00:02:11,090 --> 00:02:12,070
E foarte dinamic.

58
00:02:12,070 --> 00:02:15,100
Și că nu ești comiterea,
în prealabil, într-o anumită dimensiune fixă

59
00:02:15,100 --> 00:02:18,750
bucată de memorie, ca tine ar trebui
a, cu o serie, în sensul creșterii de care

60
00:02:18,750 --> 00:02:22,455
este că puteți aloca noduri numai pe
Cererea astfel folosind doar cât mai mult spațiu

61
00:02:22,455 --> 00:02:23,330
cum ai de fapt nevoie.

62
00:02:23,330 --> 00:02:26,830
Prin contrast cu o serie, s-ar putea
aloca accidental prea puțin.

63
00:02:26,830 --> 00:02:28,871
Și apoi e doar de gând
a fi o durere în gât

64
00:02:28,871 --> 00:02:32,440
să realoce o nouă gamă mai mare, copiați
totul peste, desprindă matrice vechi,

65
00:02:32,440 --> 00:02:33,990
și apoi mutați despre afacerea ta.

66
00:02:33,990 --> 00:02:37,479
Sau, mai rău, s-ar putea aloca fel
mai multă memorie decât în ​​realitate nevoie,

67
00:02:37,479 --> 00:02:40,520
și astfel vei avea o foarte
matrice slab populate, ca să spunem așa.

68
00:02:40,520 --> 00:02:44,350
>> Deci, o listă legată vă oferă aceste
Avantajele de dinamism și flexibilitate

69
00:02:44,350 --> 00:02:46,080
cu inserții și deleții.

70
00:02:46,080 --> 00:02:48,000
Dar cu siguranță trebuie să existe un preț plătit.

71
00:02:48,000 --> 00:02:50,000
De fapt, una dintre temele
explorat pe test de zero

72
00:02:50,000 --> 00:02:52,430
a fost o pereche de compromisurile
am văzut până acum.

73
00:02:52,430 --> 00:02:56,161
Deci, ce este un preț plătit sau de o
Dezavantajul unei liste legat?

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

75
00:02:56,660 --> 00:02:57,560
>> Audiența: Nu există acces aleator.

76
00:02:57,560 --> 00:02:58,809
>> DAVID MALAN: Nu există acces aleator.

77
00:02:58,809 --> 00:02:59,540
Dar cui îi pasă?

78
00:02:59,540 --> 00:03:01,546
Cu acces aleator nu sună convingător.

79
00:03:01,546 --> 00:03:02,421
>> Audiența: [inaudibil]

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

81
00:03:04,865 --> 00:03:05,740
DAVID MALAN: Exact.

82
00:03:05,740 --> 00:03:07,580
Dacă doriți să aveți
un anumit algorithm--

83
00:03:07,580 --> 00:03:10,170
și lasă-mă să propună de fapt
binar de căutare în special, care

84
00:03:10,170 --> 00:03:12,600
este una am folosit destul de bit--
dacă nu aveți acces aleator,

85
00:03:12,600 --> 00:03:15,516
nu poți face asta aritmetică simplă
de a găsi, cum ar fi elementul de mijloc

86
00:03:15,516 --> 00:03:16,530
și sari dreptul la ea.

87
00:03:16,530 --> 00:03:20,239
Ai în schimb să înceapă de la prima
Element si cauta liniar de la stânga

88
00:03:20,239 --> 00:03:22,780
la dreapta, dacă doriți să găsiți
mijloc sau orice alt element.

89
00:03:22,780 --> 00:03:24,410
>> Audiența: Probabil este nevoie de mai multă memorie.

90
00:03:24,410 --> 00:03:25,040
>> DAVID MALAN: ia mai mult de memorie.

91
00:03:25,040 --> 00:03:27,464
Unde este acea suplimentar
costa provenind din memorie?

92
00:03:27,464 --> 00:03:28,339
>> Audiența: [inaudibil]

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

94
00:03:32,566 --> 00:03:33,440
DAVID MALAN: Exact.

95
00:03:33,440 --> 00:03:35,679
În acest caz aici, am avut
o listă legată de numere întregi,

96
00:03:35,679 --> 00:03:37,470
și totuși suntem dublare
cantitatea de memorie

97
00:03:37,470 --> 00:03:39,680
avem nevoie de asemenea stocarea aceste indicii.

98
00:03:39,680 --> 00:03:42,090
Acum mai puțin de o afacere de mare ca
structs dvs. să obțineți mai mare

99
00:03:42,090 --> 00:03:45,320
si tu esti stocarea nu un număr, dar
poate un student sau un alt obiect.

100
00:03:45,320 --> 00:03:46,880
Dar punctul rămâne cu siguranță.

101
00:03:46,880 --> 00:03:49,421
Și astfel un număr de operațiunile
pe liste legate au fost chemați

102
00:03:49,421 --> 00:03:50,570
au fost O mare de liniar N-.

103
00:03:50,570 --> 00:03:54,730
Lucruri, cum ar fi de introducere sau de căutare
sau ștergere în cazul în care un element

104
00:03:54,730 --> 00:03:57,720
sa întâmplat să fie la sfârșitul lui
lista dacă este sortate sau nu.

105
00:03:57,720 --> 00:04:01,167
>> Uneori s-ar putea avea noroc și în
limite așa mai mici pe aceste operațiuni

106
00:04:01,167 --> 00:04:04,250
ar putea fi, de asemenea, timp constant daca esti
mereu în căutarea la primul element,

107
00:04:04,250 --> 00:04:05,070
de exemplu.

108
00:04:05,070 --> 00:04:09,360
Dar în cele din urmă, ne-am promis
pentru a realiza Sfântul Graal

109
00:04:09,360 --> 00:04:12,630
de structuri de date, sau
unele acestora aproximare,

110
00:04:12,630 --> 00:04:14,290
cu titlu de timp constant.

111
00:04:14,290 --> 00:04:17,579
Poate găsim elemente sau adăuga elemente
sau elimina elemente dintr-o listă?

112
00:04:17,579 --> 00:04:19,059
Vom vedea destul de repede.

113
00:04:19,059 --> 00:04:21,100
Și se pare că o
mecanismelor suntem

114
00:04:21,100 --> 00:04:23,464
O să înceapă să folosească astăzi,
consumului anual în p stabilit cinci,

115
00:04:23,464 --> 00:04:24,630
este, de fapt destul de familiar.

116
00:04:24,630 --> 00:04:27,430
De exemplu, în cazul în care acest lucru este un buchet
de cărți de examen, fiecare dintre care

117
00:04:27,430 --> 00:04:29,660
are un student în primul rând
si nume pe ea,

118
00:04:29,660 --> 00:04:31,820
și le-am ridica de la
la sfârșitul unui examen,

119
00:04:31,820 --> 00:04:33,746
și toate acestea sunt destul de
mai mult într-o ordine aleatorie,

120
00:04:33,746 --> 00:04:36,370
și vrem să mergem cu privire la sortarea
aceste examene, astfel că, odată clasificate

121
00:04:36,370 --> 00:04:38,661
e doar o mult mai ușor și
mai repede pentru a le înmâna înapoi

122
00:04:38,661 --> 00:04:40,030
pentru studenții alfabet.

123
00:04:40,030 --> 00:04:42,770
Care ar fi instinctele tale
pentru o gramada de examene, cum ar fi aceasta?

124
00:04:42,770 --> 00:04:45,019
>> Ei bine, daca esti ca mine,
s-ar putea vedea că aceasta este m,

125
00:04:45,019 --> 00:04:48,505
așa că am de gând să fel de a pune acest lucru în,
în cazul în care acest lucru este masa mea sau în cazul în care podeaua mea

126
00:04:48,505 --> 00:04:50,650
Sunt de raspandire lucruri
out-- sau matrice mea really--

127
00:04:50,650 --> 00:04:52,210
S-ar putea pune toate ms acolo.

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

129
00:04:52,710 --> 00:04:55,020
Iată un A. Deci, eu s-ar putea
a pus As aici.

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

131
00:04:55,520 --> 00:04:57,980
Iată un alt A. am de gând
pentru a pune asta pe aici.

132
00:04:57,980 --> 00:05:02,490
Iată un Z. Aici este un alt M. Și așa
S-ar putea începe a face grămezi de acest gen.

133
00:05:02,490 --> 00:05:06,620
Și atunci poate că m-aș duce în mai târziu
și un fel de foarte nitpicky-ly fel

134
00:05:06,620 --> 00:05:07,710
grămezi individuale.

135
00:05:07,710 --> 00:05:11,300
Dar ideea este m-aș uita
la intrare că sunt jucători

136
00:05:11,300 --> 00:05:14,016
și aș face ceva calculate
decizie bazată pe acea intrare.

137
00:05:14,016 --> 00:05:15,640
În cazul în care începe cu A, el a pus acolo.

138
00:05:15,640 --> 00:05:18,980
În cazul în care începe cu Z, pune-l peste
acolo, și totul în între.

139
00:05:18,980 --> 00:05:22,730
>> Deci, aceasta este o tehnica care este
în general, cunoscut sub numele hashing-- H-A-S--H

140
00:05:22,730 --> 00:05:26,550
ceea ce, în general, înseamnă a lua ca
de intrare și folosirea acea intrare pentru a calcula

141
00:05:26,550 --> 00:05:30,940
o valoare, în general, un număr, și că
Numărul este indicele într-o depozitare

142
00:05:30,940 --> 00:05:32,260
container, ca un tablou.

143
00:05:32,260 --> 00:05:35,490
Deci, cu alte cuvinte, am putea avea un
funcție hash, așa cum fac eu în capul meu,

144
00:05:35,490 --> 00:05:37,940
că dacă văd pe cineva e
Numele care începe cu A,

145
00:05:37,940 --> 00:05:40,190
Am de gând să hartă care
la zero în capul meu.

146
00:05:40,190 --> 00:05:44,160
Și dacă am vedea pe cineva cu Z, eu sunt
O să hartă care la 25 în capul meu

147
00:05:44,160 --> 00:05:46,220
și apoi a pus că în
ultima cel mai gramada.

148
00:05:46,220 --> 00:05:50,990
>> Acum, dacă te gândești nu creierul meu
dar un program C, ceea ce ar putea numere

149
00:05:50,990 --> 00:05:53,170
te bazezi pe pentru a obține același rezultat?

150
00:05:53,170 --> 00:05:55,594
Cu alte cuvinte, dacă
a avut ASCII de caractere A,

151
00:05:55,594 --> 00:05:57,510
Cum se determina
ceea ce găleată să-l pună în?

152
00:05:57,510 --> 00:05:59,801
Probabil că nu vreau să
pune-l în găleată 65 de ani, care

153
00:05:59,801 --> 00:06:01,840
Ar fi ca și cum acolo
pentru nici un motiv bun.

154
00:06:01,840 --> 00:06:04,320
În cazul în care vrei să pună A
în ceea ce privește valoarea ASCII?

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

156
00:06:05,600 --> 00:06:08,920
În cazul în care vrei să faci pentru a ASCII sale
Valoarea de a veni cu o găleată inteligentă

157
00:06:08,920 --> 00:06:09,480
a pus-o în?

158
00:06:09,480 --> 00:06:10,206
>> Audiența: Minus A.

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

160
00:06:10,956 --> 00:06:13,190
Deci, minus A sau minus
în mod specific 65 dacă e

161
00:06:13,190 --> 00:06:18,240
o A. de capital sau 98, dacă
este o literă mică o.

162
00:06:18,240 --> 00:06:21,300
Și așa încât ne-ar permite să, foarte
pur și simplu și foarte aritmetic,

163
00:06:21,300 --> 00:06:23,260
pune ceva într-o găleată de genul asta.

164
00:06:23,260 --> 00:06:26,010
Deci, se dovedește facem de fapt
aceasta, de asemenea, chiar cu chestionare.

165
00:06:26,010 --> 00:06:29,051
>> Deci, s-ar putea aminti tu încercuite ta
Numele colegi învățătura lui pe coperta.

166
00:06:29,051 --> 00:06:32,270
Și au fost organizate numele TF
în aceste coloane alfabetic

167
00:06:32,270 --> 00:06:34,400
bine, crezi sau nu,
atunci când toate 80 plus noi

168
00:06:34,400 --> 00:06:37,800
s-au reunit noaptea de calitate,
ultima etapă în procesul de clasificare

169
00:06:37,800 --> 00:06:41,830
este de a hash chestionare într-o mare
spațiu de podea la [inaudibil]

170
00:06:41,830 --> 00:06:45,110
și să se stabilească teste tuturor afară
în exact ordinea de lor TF

171
00:06:45,110 --> 00:06:47,700
Numele de pe capacul, deoarece
atunci este mult mai ușor pentru noi

172
00:06:47,700 --> 00:06:51,290
pentru a căuta prin faptul că utilizarea liniar
caută sau un fel de inteligență

173
00:06:51,290 --> 00:06:54,050
pentru un TF pentru a găsi sau a lui
chestionare elevilor ei.

174
00:06:54,050 --> 00:06:56,060
>> Deci, această idee de hash
pe care le veți vedea este

175
00:06:56,060 --> 00:07:00,520
destul de puternic este, de fapt destul de
obișnuit și foarte intuitiv,

176
00:07:00,520 --> 00:07:03,000
mai mult ca probabil, diviza și
cucerire a fost în săptămâna zero.

177
00:07:03,000 --> 00:07:05,250
Am nerăbdare rapid la hackathon
un cuplu de ani în urmă.

178
00:07:05,250 --> 00:07:08,040
Aceasta a fost Zamyla și un cuplu de
alți studenți salut personal

179
00:07:08,040 --> 00:07:09,030
așa cum au venit în.

180
00:07:09,030 --> 00:07:12,680
Și am avut o grămadă de pliere
Mese de acolo cu etichete de nume.

181
00:07:12,680 --> 00:07:15,380
Și ne-am etichetele de nume organizat
cu la fel ca și peste acolo

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

183
00:07:16,690 --> 00:07:20,350
Și astfel unul dintre cele TFS foarte inteligent
a scris acest lucru ca instrucțiunile

184
00:07:20,350 --> 00:07:21,030
pentru a doua zi.

185
00:07:21,030 --> 00:07:24,480
Și în săptămâna 12 a semestrului aceasta
a făcut toate sens perfect și toată lumea

186
00:07:24,480 --> 00:07:25,310
știa ce să facă.

187
00:07:25,310 --> 00:07:27,900
Dar oricând ai
coada de așteptare în același mod,

188
00:07:27,900 --> 00:07:30,272
te punerea în aplicare a
aceeași noțiune de un hash.

189
00:07:30,272 --> 00:07:31,730
Deci, haideți să-l un pic oficializa.

190
00:07:31,730 --> 00:07:32,890
Aici este un tablou.

191
00:07:32,890 --> 00:07:36,820
Este atras de a fi un pic
largă doar pentru a descrie, vizual,

192
00:07:36,820 --> 00:07:38,920
pe care le-ar putea pune siruri de caractere
în așa ceva.

193
00:07:38,920 --> 00:07:41,970
Și aceasta matrice este
în mod clar din numărul total de dimensiune 26.

194
00:07:41,970 --> 00:07:43,935
Și lucrul se numește
tabel arbitrar.

195
00:07:43,935 --> 00:07:48,930
Dar aceasta este doar de extrădare unui artist
a ceea ce ar putea fi un tabel hash.

196
00:07:48,930 --> 00:07:52,799
>> Deci, un tabel hash acum este de gând să
să fie o structură de date de nivel superior.

197
00:07:52,799 --> 00:07:54,840
La sfârșitul zilei
suntem pe cale de a vedea pe care le

198
00:07:54,840 --> 00:07:58,700
poate pune în aplicare un tabel hash, care
este de mult ca linia de check-in

199
00:07:58,700 --> 00:08:02,059
la un Hackathon mult ca aceasta
Tabelul folosit pentru sortarea cărți de examen.

200
00:08:02,059 --> 00:08:03,850
Dar un tabel hash este
un fel de acest nivel înalt

201
00:08:03,850 --> 00:08:08,250
concept care ar putea folosi o matrice
sub capota să-l pună în aplicare,

202
00:08:08,250 --> 00:08:11,890
sau ar putea folosi o listă de lungime, sau chiar
probabil, alte structuri de date.

203
00:08:11,890 --> 00:08:15,590
Și acum asta e prelevarea theme--
unele dintre aceste ingrediente fundamentale

204
00:08:15,590 --> 00:08:18,310
ca o matrice și această clădire
bloc acum de o listă de lungime

205
00:08:18,310 --> 00:08:21,740
și de a vedea ce altceva putem construi
pe partea de sus a acestora, cum ar fi ingredientele

206
00:08:21,740 --> 00:08:26,550
într-o rețetă, ce mai mult
Rezultatele finale interesante și utile.

207
00:08:26,550 --> 00:08:28,680
>> Deci, cu tabelul hash
putem să o pună în aplicare

208
00:08:28,680 --> 00:08:32,540
în memorie pictural ca aceasta, dar
cum s-ar putea să fie de fapt codificate în sus?

209
00:08:32,540 --> 00:08:33,789
Ei bine, poate ca pur si simplu este aceasta.

210
00:08:33,789 --> 00:08:38,270
În cazul în care CAPACITATE în toate capace, este doar
unele constant-- de exemplu 26,

211
00:08:38,270 --> 00:08:42,030
pentru 26 de litere ale alphabet--
Am putea numi masa mea variabil,

212
00:08:42,030 --> 00:08:45,630
și-ar putea pretinde că am de gând să
a pus stele char acolo, sau string.

213
00:08:45,630 --> 00:08:49,880
Deci, este la fel de simplu ca acest lucru dacă
doresc să pună în aplicare un tabel hash.

214
00:08:49,880 --> 00:08:51,490
Și totuși, aceasta este de fapt doar un tablou.

215
00:08:51,490 --> 00:08:53,198
Dar, din nou, un hash
tabel este acum ce vom

216
00:08:53,198 --> 00:08:57,470
apela un tip de date abstract asta e doar
un fel de stratificare conceptual pe partea de sus

217
00:08:57,470 --> 00:09:00,780
de ceva mai lumesc
ca acum o matrice.

218
00:09:00,780 --> 00:09:02,960
>> Acum, cum putem merge
despre rezolvarea problemelor?

219
00:09:02,960 --> 00:09:06,980
Ei bine, mai devreme am avut luxul
de a avea spațiu de tabelă suficient aici

220
00:09:06,980 --> 00:09:09,460
astfel încât am putut pune
teste oriunde am vrut.

221
00:09:09,460 --> 00:09:10,620
Deci, ceea ce ar putea merge aici.

222
00:09:10,620 --> 00:09:12,100
Zs ar putea merge aici.

223
00:09:12,100 --> 00:09:13,230
Dna ar putea merge aici.

224
00:09:13,230 --> 00:09:14,740
Și apoi am avut ceva spațiu suplimentar.

225
00:09:14,740 --> 00:09:18,740
Dar aceasta este un pic de un drept ieftin
acum, deoarece acest tabel, dacă am într-adevăr

226
00:09:18,740 --> 00:09:22,720
gândit la ea ca la o matrice, este doar
Va fi de o anumită dimensiune fixă.

227
00:09:22,720 --> 00:09:25,380
>> Deci, punct de vedere tehnic, dacă am trage
până quiz un alt elev

228
00:09:25,380 --> 00:09:28,490
și a se vedea, oh, această persoană
Numele începe cu un A de asemenea,

229
00:09:28,490 --> 00:09:30,980
Am facut un fel de doresc să-l pună acolo.

230
00:09:30,980 --> 00:09:34,740
Dar, de îndată ce am pus-o acolo, în cazul în care
acest tabel reprezintă într-adevăr o matrice,

231
00:09:34,740 --> 00:09:37,840
Am de gând să fie imperative sau clobbering
oricine test acest student este.

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

233
00:09:38,340 --> 00:09:41,972
Dacă aceasta este o matrice, un singur lucru poate
du-te în fiecare dintre aceste celule sau elemente.

234
00:09:41,972 --> 00:09:43,680
Și așa am cam avea
de a alege și de a alege.

235
00:09:43,680 --> 00:09:45,735
>> Acum, mai devreme am facut un fel de
înșelat și a făcut acest lucru sau I

236
00:09:45,735 --> 00:09:47,526
doar un fel de stivuite
ele deasupra celeilalte.

237
00:09:47,526 --> 00:09:49,170
Dar asta nu se va zbura în cod.

238
00:09:49,170 --> 00:09:52,260
Deci, în cazul în care aș putea să îl
al doilea elev al cărui nume

239
00:09:52,260 --> 00:09:54,964
este o dacă tot ce am avut asta
spațiu tabelă disponibil?

240
00:09:54,964 --> 00:09:57,880
Și l-am folosit trei sloturi și ea
Se pare ca exista doar cateva alții.

241
00:09:57,880 --> 00:09:58,959
Ce ai putea face?

242
00:09:58,959 --> 00:09:59,834
Audiența: [inaudibil]

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
Poate că hai să-l păstrați simplu.

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

247
00:10:02,660 --> 00:10:04,243
Ea nu se potrivește în cazul în care vreau să-l puneți.

248
00:10:04,243 --> 00:10:07,450
Așa că am de gând să-l puneți
punct de vedere tehnic în cazul în care B ar merge.

249
00:10:07,450 --> 00:10:09,932
Acum, desigur, încep
să mă picta într-un colț.

250
00:10:09,932 --> 00:10:11,890
Dacă aș ajunge la un elev
al cărui nume este, de fapt B,

251
00:10:11,890 --> 00:10:14,840
acum B va fi mutat un pic
înainte, așa cum s-ar putea întâmpla, da,

252
00:10:14,840 --> 00:10:17,530
în cazul în care acest lucru este un B, acum trebuie să meargă aici.

253
00:10:17,530 --> 00:10:20,180
>> Și astfel acest lucru foarte repede
ar putea deveni problematic,

254
00:10:20,180 --> 00:10:23,850
dar este o tehnica care de fapt
este menționată ca liniar palpare,

255
00:10:23,850 --> 00:10:26,650
prin care doar considerați dumneavoastră
matrice a fi de-a lungul liniei.

256
00:10:26,650 --> 00:10:29,680
Și tu doar un fel de sonda sau
inspecta fiecare element disponibile

257
00:10:29,680 --> 00:10:31,360
Cautati un loc disponibil.

258
00:10:31,360 --> 00:10:34,010
Și, de îndată ce veți găsi
unul, îl picătură acolo.

259
00:10:34,010 --> 00:10:38,390
>> Acum, prețul fiind plătit acum
pentru această soluție este ceea ce?

260
00:10:38,390 --> 00:10:41,300
Avem o gamă dimensiune fixă,
și atunci când am insera nume

261
00:10:41,300 --> 00:10:44,059
în ea, cel puțin la început, ceea ce este
timpul de execuție de inserție

262
00:10:44,059 --> 00:10:46,350
pentru a pune elevilor
teste în gălețile potrivite?

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

264
00:10:48,710 --> 00:10:50,002
Big O de ce?

265
00:10:50,002 --> 00:10:51,147
>> Audiența: n.

266
00:10:51,147 --> 00:10:52,480
DAVID MALAN: Am auzit O mare de n.

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

268
00:10:53,530 --> 00:10:54,300
Nu este adevărat.

269
00:10:54,300 --> 00:10:56,490
Dar vom tachineze pe langa
de ce într-o clipă.

270
00:10:56,490 --> 00:10:57,702
Ce altceva ar putea fi?

271
00:10:57,702 --> 00:10:58,755
>> Audiența: [inaudibil]

272
00:10:58,755 --> 00:11:00,380
DAVID MALAN: Și lasă-mă să o fac vizual.

273
00:11:00,380 --> 00:11:04,720
Deci, să presupunem că aceasta este litera S.

274
00:11:04,720 --> 00:11:05,604
>> Audiența: E una.

275
00:11:05,604 --> 00:11:06,520
DAVID MALAN: E una.

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

277
00:11:06,710 --> 00:11:08,950
Aceasta este o matrice, care
înseamnă că avem acces aleator.

278
00:11:08,950 --> 00:11:11,790
Și dacă ne gândim la acest lucru
ca zero și acest lucru ca 25,

279
00:11:11,790 --> 00:11:13,800
și ne dăm seama că,
oh, aici e intrarea mea S,

280
00:11:13,800 --> 00:11:16,350
Eu pot converti cu siguranță
S, un caracter ASCII,

281
00:11:16,350 --> 00:11:18,540
la un număr corespunzător
între zero și 25

282
00:11:18,540 --> 00:11:20,910
și apoi imediat
pune-l în cazul în care acesta face parte.

283
00:11:20,910 --> 00:11:26,120
>> Dar, desigur, de îndată ce ajung la
a doua persoană care e numele este A sau B sau C

284
00:11:26,120 --> 00:11:29,300
în cele din urmă, dacă l-am folosit
liniar palpare ca soluția mea,

285
00:11:29,300 --> 00:11:31,360
timpul de execuție a
inserarea în cel mai rău caz

286
00:11:31,360 --> 00:11:33,120
este, de fapt de gând să revină în ce?

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

288
00:11:34,270 --> 00:11:36,045
Și l-am auzit aici
corect de timpuriu.

289
00:11:36,045 --> 00:11:36,920
Audiența: [inaudibil]

290
00:11:36,920 --> 00:11:41,620
DAVID MALAN: Deci, este într-adevăr n dată
Ai un set suficient de mare de date.

291
00:11:41,620 --> 00:11:44,410
Deci, pe de o parte, dacă
matrice este destul de mare

292
00:11:44,410 --> 00:11:48,287
și datele dumneavoastră este destul de rare, tu
primi acest moment frumos constant.

293
00:11:48,287 --> 00:11:50,620
Dar, de îndată ce începe să
obtinerea mai multe și mai multe elemente,

294
00:11:50,620 --> 00:11:53,200
și doar statistic te
mai multe persoane cu litera

295
00:11:53,200 --> 00:11:56,030
A ca numele lor sau litera
B, ea ar putea potențial

296
00:11:56,030 --> 00:11:57,900
involua într ceva mai liniar.

297
00:11:57,900 --> 00:11:59,640
Deci, nu destul de perfect.

298
00:11:59,640 --> 00:12:00,690
Deci, am putea face mai bine?

299
00:12:00,690 --> 00:12:03,210
>> Ei bine, ce a fost nostru
soluție înainte de când ne-am

300
00:12:03,210 --> 00:12:06,820
doresc să aibă mai mult dinamism mult
permis ceva de genul un tablou?

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

302
00:12:08,085 --> 00:12:08,960
Audiența: [inaudibil]

303
00:12:08,960 --> 00:12:10,030
DAVID MALAN: Ce am introduce?

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

305
00:12:10,530 --> 00:12:11,430
Deci, o listă legat.

306
00:12:11,430 --> 00:12:14,430
Ei bine, să vedem ce legătură o
Lista ar putea face pentru noi în schimb.

307
00:12:14,430 --> 00:12:17,630
Ei bine, lasă-mă să propună noi
trage imaginea, după cum urmează.

308
00:12:17,630 --> 00:12:19,620
Acum, aceasta este un alt
imagine de la un exemplu

309
00:12:19,620 --> 00:12:24,750
dintr-un text diferit, de fapt, că
este, de fapt, folosind o serie de dimensiuni 31.

310
00:12:24,750 --> 00:12:28,220
Și acest autor pur și simplu
a decis să hash siruri de caractere

311
00:12:28,220 --> 00:12:32,430
nu se bazează pe numele persoanei,
dar bazat pe zile de naștere lor.

312
00:12:32,430 --> 00:12:35,680
Indiferent de luni, au gândit
dacă te-ai născut pe primul dintr-o lună

313
00:12:35,680 --> 00:12:39,580
sau 31 a lunii, autorul
va hash bazat pe acea valoare,

314
00:12:39,580 --> 00:12:44,154
astfel încât să se răspândească numele un pic
mai mult decât 26 de locuri s-ar putea permite.

315
00:12:44,154 --> 00:12:47,320
Și poate că e un pic mai uniformă
decât a merge cu litere alfabetice,

316
00:12:47,320 --> 00:12:50,236
pentru că, desigur, nu e probabil
mai multe persoane în lume, cu nume

317
00:12:50,236 --> 00:12:54,020
care începe cu A mare de siguranță
alte litere ale alfabetului.

318
00:12:54,020 --> 00:12:56,380
Deci, poate că acest lucru este un pic
mai uniform, presupunând

319
00:12:56,380 --> 00:12:58,640
o distribuție uniformă
de copii într-o lună.

320
00:12:58,640 --> 00:12:59,990
>> Dar, desigur, acest lucru este încă imperfect.

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

322
00:13:00,370 --> 00:13:01,370
Avem coliziuni.

323
00:13:01,370 --> 00:13:04,680
Mai multe persoane din acest
Structura de date sunt încă

324
00:13:04,680 --> 00:13:08,432
având aceeași data nașterii, cel puțin
esti indiferent de lună.

325
00:13:08,432 --> 00:13:09,640
Dar ceea ce a făcut autorul?

326
00:13:09,640 --> 00:13:13,427
Ei bine, se pare ca avem un tablou
pe partea stângă trase vertical,

327
00:13:13,427 --> 00:13:15,010
dar asta e doar extrădare unui artist.

328
00:13:15,010 --> 00:13:18,009
Nu contează ce direcție te
desena o matrice, este încă o matrice.

329
00:13:18,009 --> 00:13:20,225
Ce este aceasta o serie de aparent?

330
00:13:20,225 --> 00:13:21,500
>> Audiența: Lista de legat.

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

332
00:13:21,650 --> 00:13:23,490
Se pare că e un
serie de liste legate.

333
00:13:23,490 --> 00:13:26,490
Deci, din nou, la acest punct de gen
de utilizare a acestor structuri de date acum

334
00:13:26,490 --> 00:13:28,550
ca ingrediente pentru mai multe
soluții interesante,

335
00:13:28,550 --> 00:13:30,862
puteți lua absolut o
fundamental, ca o matrice,

336
00:13:30,862 --> 00:13:33,320
și apoi să ia ceva mai mult
interesant ca o listă legată

337
00:13:33,320 --> 00:13:36,660
și chiar să le combine într-o mai
structură de date mai interesant.

338
00:13:36,660 --> 00:13:39,630
Și într-adevăr, acest lucru prea ar fi
fi numit un tabel hash,

339
00:13:39,630 --> 00:13:42,610
prin matrice este
într-adevăr tabel hash,

340
00:13:42,610 --> 00:13:45,600
dar că tabelă de dispersie a
lanțuri, ca să spunem așa,

341
00:13:45,600 --> 00:13:50,220
care poate crește sau micșora în funcție, pe de
Numărul de elemente pe care doriți să inserați.

342
00:13:50,220 --> 00:13:52,990
>> Acum, în consecință, ceea ce este
Timpul de funcționare acum?

343
00:13:52,990 --> 00:13:58,030
Dacă vreau să inserați cineva
a cărui zi de naștere este 31 octombrie,

344
00:13:58,030 --> 00:13:59,040
unde are el sau ea merge?

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

346
00:14:00,530 --> 00:14:01,030
Bine.

347
00:14:01,030 --> 00:14:02,819
În partea de jos, unde se spune 31.

348
00:14:02,819 --> 00:14:03,610
Și asta e perfect.

349
00:14:03,610 --> 00:14:05,060
Asta a fost timp constant.

350
00:14:05,060 --> 00:14:08,760
Dar ce se întâmplă dacă vom găsi pe altcineva
a cărui zi de naștere este, să vedem,

351
00:14:08,760 --> 00:14:10,950
Octombrie, noiembrie, 31 Decembrie?

352
00:14:10,950 --> 00:14:12,790
În cazul în care el sau ea este de gând să meargă?

353
00:14:12,790 --> 00:14:13,290
Același lucru.

354
00:14:13,290 --> 00:14:13,970
În două etape, totuși.

355
00:14:13,970 --> 00:14:15,303
Asta e constant, deși nu-i așa?

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

357
00:14:16,360 --> 00:14:16,860
Bine.

358
00:14:16,860 --> 00:14:17,840
În momentul de față este.

359
00:14:17,840 --> 00:14:20,570
Dar, în cazul general,
mai multe persoane pe care le adăugăm,

360
00:14:20,570 --> 00:14:23,790
probabilistic, mergem
pentru a obține mai multe și mai multe coliziuni.

361
00:14:23,790 --> 00:14:26,820
>> Acum, acest lucru este un pic
mai bine pentru că tehnic

362
00:14:26,820 --> 00:14:34,580
acum lanțurile mele ar putea fi în
cel mai rău caz cât timp?

363
00:14:34,580 --> 00:14:38,890
Dacă aș insera n oameni în acest mai mult
structură de date sofisticat, n oameni,

364
00:14:38,890 --> 00:14:41,080
în cel mai rău caz o să fie n.

365
00:14:41,080 --> 00:14:41,815
De ce?

366
00:14:41,815 --> 00:14:43,332
>> Audiența: Pentru că dacă toată lumea
are aceeași zi de naștere,

367
00:14:43,332 --> 00:14:44,545
ei vor fi o singură linie.

368
00:14:44,545 --> 00:14:45,420
DAVID MALAN: Perfect.

369
00:14:45,420 --> 00:14:47,480
Ar putea fi un pic contrived,
dar cu adevărat în cel mai rău caz,

370
00:14:47,480 --> 00:14:50,117
dacă toată lumea are aceeași zi de naștere,
ținând cont de inputuri care le ai,

371
00:14:50,117 --> 00:14:51,950
ai de gând să aibă o
lanț masiv lung.

372
00:14:51,950 --> 00:14:54,241
Și așa, ai putea apela un
hash masă, dar de fapt e

373
00:14:54,241 --> 00:14:56,810
doar o listă masiv în legătură cu
o mulțime de spațiu irosit.

374
00:14:56,810 --> 00:15:00,460
Dar, în general, dacă presupunem că
cel puțin aniversari sunt uniform--

375
00:15:00,460 --> 00:15:01,750
și, probabil, nu este.

376
00:15:01,750 --> 00:15:02,587
Fac asta.

377
00:15:02,587 --> 00:15:04,420
Dar dacă presupunem, pentru
dragul discuției

378
00:15:04,420 --> 00:15:07,717
că ele sunt, apoi, în teorie, dacă
aceasta este reprezentarea verticală

379
00:15:07,717 --> 00:15:11,050
de matrice, și atunci sperăm că ești
mergi la a lua lanțuri, care sunt, știți,

380
00:15:11,050 --> 00:15:15,880
aproximativ aceeași lungime în care fiecare dintre
acestea reprezintă o zi a lunii.

381
00:15:15,880 --> 00:15:19,930
>> Acum, dacă e 31 zile din luna,
ceea ce înseamnă că timpul meu de rulare într-adevăr

382
00:15:19,930 --> 00:15:25,230
este O mare de n peste 31, care
se simte mai bine decât liniar.

383
00:15:25,230 --> 00:15:27,950
Dar ceea ce a fost unul dintre noastre
angajamente câteva săptămâni

384
00:15:27,950 --> 00:15:31,145
acum ori de câte ori a venit la exprimarea
timpul de execuție a unui algoritm?

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

386
00:15:33,450 --> 00:15:35,190
Uită-te numai la termenul ridicat comanda.

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

388
00:15:35,690 --> 00:15:37,400
31 este cu siguranta de ajutor.

389
00:15:37,400 --> 00:15:39,610
Dar aceasta este încă O mare de n.

390
00:15:39,610 --> 00:15:41,730
Dar una dintre temele
problemei stabilit cinci

391
00:15:41,730 --> 00:15:43,950
va fi de
recunosc că absolut,

392
00:15:43,950 --> 00:15:47,320
asimptotic, teoretic
această structură de date

393
00:15:47,320 --> 00:15:50,470
nu este mai bună decât
o listă legată masiv.

394
00:15:50,470 --> 00:15:53,550
Și într-adevăr, în cel mai rău caz, acest
tabelă de dispersie s-ar putea să revină în asta.

395
00:15:53,550 --> 00:15:57,620
>> Dar în lumea reală, cu noi oamenii
că Mac-urile sau PC-uri proprii sau orice

396
00:15:57,620 --> 00:16:01,240
și se execută din lumea reală
software-ul pe date din lumea reală,

397
00:16:01,240 --> 00:16:03,260
care algoritm ai de gând să preferi?

398
00:16:03,260 --> 00:16:09,180
Cel care ia măsuri finali sau
una care ia n împărțit la 31 de pași

399
00:16:09,180 --> 00:16:12,900
pentru a găsi unele bucată de date sau
pentru a căuta unele informații?

400
00:16:12,900 --> 00:16:16,580
Adică, absolut cele 31 de mărci
o diferență în lumea reală.

401
00:16:16,580 --> 00:16:18,540
Acesta este de 31 ori mai rapid.

402
00:16:18,540 --> 00:16:20,880
Și noi, oamenii sunt cu siguranță
O să apreciez asta.

403
00:16:20,880 --> 00:16:23,004
>> Deci, dau seama de dihotomia
acolo între realitate

404
00:16:23,004 --> 00:16:25,920
vorbind despre lucruri teoretic
și asimptotic care cu siguranta

405
00:16:25,920 --> 00:16:28,760
are valoare cum am văzut,
dar în lumea reală,

406
00:16:28,760 --> 00:16:32,930
dacă îți pasă doar punerea
fericit om de intrări generale,

407
00:16:32,930 --> 00:16:36,010
ați putea dori foarte bine să accepte
faptul că, da, aceasta este liniar,

408
00:16:36,010 --> 00:16:38,360
dar e de 31 de ori mai rapid
decât liniar ar putea fi.

409
00:16:38,360 --> 00:16:41,610
Și mai bine, noi nu trebuie doar să
face ceva arbitrar ca o zi de naștere,

410
00:16:41,610 --> 00:16:44,030
am putea petrece un pic
mai mult timp și inteligență

411
00:16:44,030 --> 00:16:47,140
și cred despre ceea ce am putea face,
dat numele unei persoane și, poate,

412
00:16:47,140 --> 00:16:50,130
Data nașterii lor de a combina cele
ingrediente pentru a descoperi ceva

413
00:16:50,130 --> 00:16:52,720
care este cu adevărat mai mult
uniform și mai puțin jaggy,

414
00:16:52,720 --> 00:16:56,250
ca să spunem așa decât această imagine
în prezent sugerează că ar putea fi.

415
00:16:56,250 --> 00:16:57,750
Cum am putea pune în aplicare acest lucru în cod?

416
00:16:57,750 --> 00:17:00,280
Ei bine, lasă-mă să propună noi
doar împrumuta unele sintaxă ne-am

417
00:17:00,280 --> 00:17:01,799
folosit de câteva ori până acum.

418
00:17:01,799 --> 00:17:03,590
Și am de gând să definească
un nod, care din nou

419
00:17:03,590 --> 00:17:06,812
este un termen generic pentru doar câteva
container pentru unele structuri de date.

420
00:17:06,812 --> 00:17:09,020
Am de gând să propună
un șir se întâmplă acolo.

421
00:17:09,020 --> 00:17:11,369
Dar vom începe să luați
cele de formare roți de pe acum.

422
00:17:11,369 --> 00:17:13,230
>> Nu mai bibliotecă CS50
într-adevăr, cu excepția cazului în care doriți

423
00:17:13,230 --> 00:17:15,230
să-l utilizați pentru finală dvs.
proiect, ceea ce este bine,

424
00:17:15,230 --> 00:17:18,569
dar acum vom trage înapoi
cortina și spun că este doar o stea char.

425
00:17:18,569 --> 00:17:22,069
Deci, cuvântul acolo va fi
numele persoanei în cauză.

426
00:17:22,069 --> 00:17:25,079
Și acum am un link
aici la nodul următor

427
00:17:25,079 --> 00:17:28,170
astfel încât acestea să reprezinte
fiecare dintre nodurile

428
00:17:28,170 --> 00:17:30,950
în lanț, potențial,
de o listă legată.

429
00:17:30,950 --> 00:17:34,090
>> Și acum cum fac eu declar
tabelul hash în sine?

430
00:17:34,090 --> 00:17:36,660
Cum pot declara tot această structură?

431
00:17:36,660 --> 00:17:40,960
Ei bine, într-adevăr, la fel ca am folosit un pointer
la doar primul element al unei liste

432
00:17:40,960 --> 00:17:44,510
înainte, în mod similar, pot să spun doar
Am nevoie doar de o grămadă de indicii

433
00:17:44,510 --> 00:17:46,270
să pună în aplicare acest tabel hash întreg.

434
00:17:46,270 --> 00:17:49,484
Am de gând să aibă o matrice
numita masă pentru tabelă de dispersie.

435
00:17:49,484 --> 00:17:50,900
O să aibă o capacitate dimensiune.

436
00:17:50,900 --> 00:17:52,525
Asta-i cât de multe elemente pot încăpea în el.

437
00:17:52,525 --> 00:17:56,180
Și fiecare dintre aceste elemente în acest
matrice va fi o stea nod.

438
00:17:56,180 --> 00:17:56,810
De ce?

439
00:17:56,810 --> 00:18:00,160
Ei bine, pe această imagine, ceea ce am
de punere în aplicare a tabelului hash ca

440
00:18:00,160 --> 00:18:04,330
în mod eficient la început este doar
această matrice pe care le-am desenat pe verticală,

441
00:18:04,330 --> 00:18:06,820
fiecare dintre căror pătrate
reprezintă un pointer.

442
00:18:06,820 --> 00:18:09,170
Ca cei care au slash-uri
prin ele sunt doar nule.

443
00:18:09,170 --> 00:18:11,410
Și cei care au
săgeți care merg la dreapta

444
00:18:11,410 --> 00:18:16,140
sunt indicii reale cu noduri reale,
ergo la începutul unei liste legate.

445
00:18:16,140 --> 00:18:19,050
>> Deci, aici, atunci, este modul în care s-ar putea
să pună în aplicare un tabel hash care

446
00:18:19,050 --> 00:18:21,580
pune în aplicare înlănțuire separat.

447
00:18:21,580 --> 00:18:22,840
Acum putem face mai bine?

448
00:18:22,840 --> 00:18:25,632
Bine am promis ultima dată că
am putea realiza timp constant.

449
00:18:25,632 --> 00:18:27,381
Și eu un fel de ți-a dat
constanta de timp aici,

450
00:18:27,381 --> 00:18:29,850
dar atunci nu a spus într-adevăr
constantă de timp, deoarece este încă

451
00:18:29,850 --> 00:18:31,890
dependentă total
număr de elemente

452
00:18:31,890 --> 00:18:34,500
te introducere în
structura de date.

453
00:18:34,500 --> 00:18:35,980
Dar să presupunem că am făcut asta.

454
00:18:35,980 --> 00:18:39,550
Lasă-mă să mă întorc la ecranul pe aici.

455
00:18:39,550 --> 00:18:44,520
Permiteți-mi să proiecteze asta aici, clar
ecran, și să presupunem că am făcut asta.

456
00:18:44,520 --> 00:18:49,300
Să presupunem că am vrut pentru a introduce numele
Daven în în structura mea de date.

457
00:18:49,300 --> 00:18:52,100
>> Așa că vreau să introduceți un șir
Daven în structura de date.

458
00:18:52,100 --> 00:18:54,370
Ce se întâmplă dacă nu folosesc un
hash masă, dar am folosi

459
00:18:54,370 --> 00:18:56,980
ceva care este mai mult copac-ca
ca un arbore genealogic, în cazul în care

460
00:18:56,980 --> 00:18:59,670
aveți unele rădăcină de la
noduri și frunze de top și apoi

461
00:18:59,670 --> 00:19:01,440
care merge în jos și spre exterior.

462
00:19:01,440 --> 00:19:04,450
Să presupunem deci, că am
vrea să introducă lui Daven

463
00:19:04,450 --> 00:19:06,430
în ceea ce-i în prezent o listă goală.

464
00:19:06,430 --> 00:19:09,780
Am de gând să fac următoarele: Sunt
va crea un nod în această familie

465
00:19:09,780 --> 00:19:15,170
copac ca structura de date care arată
un pic de acest fel, fiecare dintre acestea

466
00:19:15,170 --> 00:19:19,640
dreptunghiuri a, să zicem,
de acum 26 elemente în ea.

467
00:19:19,640 --> 00:19:21,650
Și fiecare dintre celulele
în această matrice se întâmplă

468
00:19:21,650 --> 00:19:23,470
pentru a reprezenta scrisoarea unui alfabet.

469
00:19:23,470 --> 00:19:28,190
>> Mai exact, am de gând să trateze
aceasta este A, apoi B, apoi C, apoi D,

470
00:19:28,190 --> 00:19:29,310
asta de aici.

471
00:19:29,310 --> 00:19:32,940
Deci, acest lucru se întâmplă pentru eficient
reprezintă litera D.

472
00:19:32,940 --> 00:19:36,040
Dar pentru a introduce toate lui Daven
nume am nevoie pentru a face un pic mai mult.

473
00:19:36,040 --> 00:19:37,840
Deci, eu în primul rând de gând să hash, ca să spunem așa.

474
00:19:37,840 --> 00:19:41,049
Am de gând să se uite la prima literă
în a Daven care este, evident, un D,

475
00:19:41,049 --> 00:19:42,840
și am de gând să aloce
un nod care arată

476
00:19:42,840 --> 00:19:45,570
ca asta: un dreptunghi mare mare
suficient pentru a se potrivi tot alfabetul.

477
00:19:45,570 --> 00:19:47,140
>> Acum, D se face.

478
00:19:47,140 --> 00:19:49,720
Acum A. D-A-V-E-N este gol.

479
00:19:49,720 --> 00:19:51,220
Deci, acum ce am de gând să fac asta.

480
00:19:51,220 --> 00:19:54,027
De îndată ce am început Notă D
nu exista nici pointer acolo.

481
00:19:54,027 --> 00:19:56,860
Este valori de gunoi în acest moment,
sau I s-ar putea inițializa la null.

482
00:19:56,860 --> 00:19:59,630
Dar permiteți-mi să continui cu
această idee de a construi un copac.

483
00:19:59,630 --> 00:20:04,260
Lasă-mă să aloce un alt una dintre acestea
noduri, care are 26 de elemente în ea.

484
00:20:04,260 --> 00:20:05,150
>> Și știi ce?

485
00:20:05,150 --> 00:20:09,130
În cazul în care acest lucru este doar un nod în memorie care
Am creat cu malloc, folosind un struct

486
00:20:09,130 --> 00:20:11,240
așa cum vom vedea în curând,
Am de gând să fac asta:

487
00:20:11,240 --> 00:20:14,450
Am de gând să tragă o săgeată de la
lucru care a reprezentat D jos

488
00:20:14,450 --> 00:20:15,860
la acest nou nod.

489
00:20:15,860 --> 00:20:19,240
Și acum, în primul rând în următorii
scrisoare în numele Daven lui,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- am de gând să merg mai departe
și să tragă un alt nod ca aceasta,

491
00:20:24,150 --> 00:20:30,150
prin care, elementele V aici, care
vom trage pentru Hopa instance--.

492
00:20:30,150 --> 00:20:31,020
Nu vom trage acolo.

493
00:20:31,020 --> 00:20:31,936
O să merg aici.

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

495
00:20:32,890 --> 00:20:35,712
>> Apoi, vom
consideră acest lucru ca fiind V.

496
00:20:35,712 --> 00:20:44,920
Și apoi aici vom index
jos de la V în ceea ce vom considera E.

497
00:20:44,920 --> 00:20:50,100
Și apoi de aici vom
du-te să aveți una dintre aceste noduri aici.

498
00:20:50,100 --> 00:20:52,930
Și acum avem o întrebare pentru a răspunde.

499
00:20:52,930 --> 00:20:57,840
Trebuie să indice faptul că într-un fel
suntem la sfârșitul șirului Daven.

500
00:20:57,840 --> 00:20:59,490
Așa că am putut pleca doar nul.

501
00:20:59,490 --> 00:21:02,670
>> Dar ce se întâmplă dacă avem de Daven
numele complet, de asemenea, care

502
00:21:02,670 --> 00:21:04,280
este, așa cum ne-am spus, Davenport?

503
00:21:04,280 --> 00:21:06,970
Și ce dacă Daven este
de fapt un subșir,

504
00:21:06,970 --> 00:21:08,960
un prefix de un șir mult mai lung?

505
00:21:08,960 --> 00:21:11,450
Noi nu putem doar permanent
nu spun nimic se întâmplă

506
00:21:11,450 --> 00:21:14,410
pentru a merge acolo, pentru că am putut
nu introduceți niciodată un cuvânt ca Davenport

507
00:21:14,410 --> 00:21:15,840
în această structură de date

508
00:21:15,840 --> 00:21:19,560
>> Deci, ce am putea face în schimb este
trata fiecare dintre aceste elemente

509
00:21:19,560 --> 00:21:22,170
cum poate avea două
elemente din interiorul ei.

510
00:21:22,170 --> 00:21:24,810
Una dintre ele este un pointer, într-adevăr,
așa cum am făcut.

511
00:21:24,810 --> 00:21:27,100
Deci, fiecare dintre aceste cutii
nu este doar o celulă.

512
00:21:27,100 --> 00:21:29,855
Dar dacă în partea de sus
Unu cea de jos a

513
00:21:29,855 --> 00:21:32,230
va fi nul, pentru că
nu există nici o Davenport doar încă.

514
00:21:32,230 --> 00:21:34,197
Ce se întâmplă dacă cel de sus
este o valoare specială?

515
00:21:34,197 --> 00:21:36,530
Și că va fi un pic
greu să-l această dimensiune trage.

516
00:21:36,530 --> 00:21:38,130
Dar să presupunem că e doar o bifă.

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

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N este un șir
în această structură de date.

519
00:21:44,230 --> 00:21:48,350
>> Între timp, dacă aș avea mai mult spațiu
aici, aș putea face P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
și am putut pune check-in nodul
care are litera T la sfârșitul.

521
00:21:52,650 --> 00:21:55,460
Deci, acesta este un masiv
-complex excelentă structură de date.

522
00:21:55,460 --> 00:21:57,210
Și scrisul meu
cu siguranță nu ajută.

523
00:21:57,210 --> 00:22:00,043
Dar dacă am vrut să insera ceva
altfel, ia în considerare ceea ce ne-ar face.

524
00:22:00,043 --> 00:22:03,370
Dacă am vrut să pună pe David in,
am urmeze aceeași logică, D-A-V,

525
00:22:03,370 --> 00:22:08,802
dar acum aș vrea să subliniez în următorii
Element nu de la E, dar de la I la D.

526
00:22:08,802 --> 00:22:10,760
Deci nu va fi
mai multe noduri în acest copac.

527
00:22:10,760 --> 00:22:12,325
Vom avea malloc apel mai mult.

528
00:22:12,325 --> 00:22:14,700
Dar eu nu vreau să fac o
dezastru complet de această imagine.

529
00:22:14,700 --> 00:22:17,710
Așa că haideți să în loc să se uite la un
care a fost pre-formulate

530
00:22:17,710 --> 00:22:21,810
ca acest lucru cu care nu dot, dot,
puncte, dar tablouri doar prescurtate.

531
00:22:21,810 --> 00:22:23,950
Dar fiecare dintre nodurile
în acest copac de aici în sus

532
00:22:23,950 --> 00:22:26,700
reprezintă același thing--
o serie Ray de dimensiune 26.

533
00:22:26,700 --> 00:22:28,860
>> Sau, dacă vrem să fim
într-adevăr corectă acum, ceea ce

534
00:22:28,860 --> 00:22:30,790
dacă numele cuiva ca
un apostrof, să

535
00:22:30,790 --> 00:22:35,560
presupune că fiecare nod are de fapt
ca 27 de indici în ea, nu doar 26.

536
00:22:35,560 --> 00:22:42,020
Deci, acest lucru acum va fi un de date
structura numita un trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Un trie, care se presupune
istoric un nume inteligent pentru un copac

538
00:22:46,120 --> 00:22:49,040
care este optimizat pentru
regăsire, care, desigur,

539
00:22:49,040 --> 00:22:50,870
se scrie cu un I-E deci e trie.

540
00:22:50,870 --> 00:22:52,710
Dar asta este istoria trie.

541
00:22:52,710 --> 00:22:55,860
>> Deci, un trie este asta arborescentă
structură ca un arbore genealogic

542
00:22:55,860 --> 00:22:57,510
care în cele din urmă se comportă ca asta.

543
00:22:57,510 --> 00:23:00,890
Și aici este doar un alt exemplu de
grămadă de nume altor oameni.

544
00:23:00,890 --> 00:23:03,540
Dar întrebarea acum
la îndemână este ceea ce avem

545
00:23:03,540 --> 00:23:08,070
am câștigat prin introducerea, fără îndoială, o mai
structură de date complicate, și unul,

546
00:23:08,070 --> 00:23:09,870
sincer, că folosește o mulțime de memorie.

547
00:23:09,870 --> 00:23:11,703
>> Deoarece, chiar dacă,
în acest moment, eu sunt doar

548
00:23:11,703 --> 00:23:15,050
folosind D pointer și
A și V și Es și NS,

549
00:23:15,050 --> 00:23:16,700
Mă pierd un heck de mult de memorie.

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

551
00:23:18,030 --> 00:23:22,660
Dar unde îmi petrec o resursă,
Am tendința de a-mi câștiga înapoi altul.

552
00:23:22,660 --> 00:23:26,020
Deci, dacă am petrece mai mult spațiu,
ceea ce este, probabil, speranța?

553
00:23:26,020 --> 00:23:27,407
Că eu îmi petrec mai puțin ce?

554
00:23:27,407 --> 00:23:28,240
Audiența: Mai puțin timp.

555
00:23:28,240 --> 00:23:28,990
DAVID MALAN: Time.

556
00:23:28,990 --> 00:23:30,320
Acum, de ce ar putea fi asta?

557
00:23:30,320 --> 00:23:33,880
Ei bine, ceea ce este inserția
timp, în termeni de mare O acum,

558
00:23:33,880 --> 00:23:37,660
de un nume ca Daven
sau Davenport sau David?

559
00:23:37,660 --> 00:23:39,340
Ei bine, Daven a fost de cinci etape.

560
00:23:39,340 --> 00:23:42,350
Davenport ar fi nouă etape,
asa ca ar fi o gamă mai mulți pași.

561
00:23:42,350 --> 00:23:44,250
David ar fi de cinci etape la fel de bine.

562
00:23:44,250 --> 00:23:47,230
Deci, acestea sunt beton
numere, dar sigur nu e

563
00:23:47,230 --> 00:23:49,550
o limită superioară
lungime de numele cuiva.

564
00:23:49,550 --> 00:23:52,240
Și într-adevăr, în problema
seturi de cinci caietul de sarcini,

565
00:23:52,240 --> 00:23:54,050
am de gând să propună
asta e ceva

566
00:23:54,050 --> 00:23:55,470
asta e de caractere de 40-unele-impar.

567
00:23:55,470 --> 00:23:58,180
>> Realist, nimeni nu are
un nume infinit lung,

568
00:23:58,180 --> 00:24:01,542
care înseamnă că lungimea unei
numele sau lungimea unui șir am putea

569
00:24:01,542 --> 00:24:03,750
au anumite starea de
structură este, fără îndoială, de ce?

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

571
00:24:05,550 --> 00:24:06,250
E constant.

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

573
00:24:06,430 --> 00:24:09,310
Ar putea fi o constantă mare ca
40-ceva, dar este constantă.

574
00:24:09,310 --> 00:24:13,752
Și nu are nici o dependență de cât de multe
alte nume se află în această structură de date.

575
00:24:13,752 --> 00:24:15,460
Cu alte cuvinte, dacă am
a vrut să insera acum

576
00:24:15,460 --> 00:24:20,540
Colton sau Gabriel sau Rob sau Zamyla sau
Alison sau Belinda sau orice alt nume

577
00:24:20,540 --> 00:24:23,940
de la personalul în aceste date
structura, este timpul de funcționare

578
00:24:23,940 --> 00:24:26,750
de a introduce alte nume
va fi deloc afectate

579
00:24:26,750 --> 00:24:30,220
de cât de multe alte elemente sunt
în structura de date deja?

580
00:24:30,220 --> 00:24:31,040
Nu e.

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

582
00:24:31,540 --> 00:24:36,150
Pentru că suntem în mod eficient folosind
acest tabel hash multi-strat.

583
00:24:36,150 --> 00:24:38,280
Și timpul de execuție a
oricare dintre aceste operațiuni

584
00:24:38,280 --> 00:24:41,510
nu depinde de numărul de
elemente care sunt în structura de date

585
00:24:41,510 --> 00:24:43,090
sau care sunt în cele din urmă de gând
a fi în structura de date,

586
00:24:43,090 --> 00:24:44,714
dar de durata ce anume?

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

588
00:24:46,500 --> 00:24:49,200
>> Șirul fiind
inserat, care nu face

589
00:24:49,200 --> 00:24:52,580
acest asimptotic constant
O mare time-- de unul.

590
00:24:52,580 --> 00:24:54,720
Și sincer, doar în
lumea reală, acest

591
00:24:54,720 --> 00:24:58,380
înseamnă introducerea numele Daven lui ia
cum ar fi cinci etape, sau Davenport nouă

592
00:24:58,380 --> 00:25:00,100
trepte, sau David cinci etape.

593
00:25:00,100 --> 00:25:03,071
Asta este al naibii de ori mici de funcționare.

594
00:25:03,071 --> 00:25:05,320
Și, într-adevăr, e un foarte
lucru bun, mai ales atunci când

595
00:25:05,320 --> 00:25:08,126
nu este dependentă de totalul
Numărul de elemente în acolo.

596
00:25:08,126 --> 00:25:10,500
Deci, cum am putea pune în aplicare această
tip de structură în codul?

597
00:25:10,500 --> 00:25:12,900
E un pic mai mult
complex, dar încă e

598
00:25:12,900 --> 00:25:15,050
doar o cerere de
blocuri de bază.

599
00:25:15,050 --> 00:25:17,830
Am de gând să redefinească
ne nod după cum urmează:

600
00:25:17,830 --> 00:25:21,100
bool numit word-- și acest
ar putea fi numit nimic.

601
00:25:21,100 --> 00:25:23,970
Dar bool reprezintă
ceea ce am desenat ca un semn de selectare.

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

603
00:25:24,490 --> 00:25:26,720
Acesta este sfârșitul unui șir
în această structură de date.

604
00:25:26,720 --> 00:25:30,702
>> Și, desigur, steaua nod
se referă la copii.

605
00:25:30,702 --> 00:25:32,410
Și, într-adevăr, la fel ca
un arbore genealogic, tu

606
00:25:32,410 --> 00:25:34,370
ar lua în considerare nodurile
care sunt agățat off

607
00:25:34,370 --> 00:25:36,920
din partea de jos a unora părinte
element de a fi copii.

608
00:25:36,920 --> 00:25:40,510
Și astfel copiii este de gând să
fie o serie de 27, cel 27

609
00:25:40,510 --> 00:25:41,680
doar fiind de apostrof.

610
00:25:41,680 --> 00:25:43,390
Mergem pentru a sorta
de caz special care.

611
00:25:43,390 --> 00:25:45,400
Astfel încât să puteți avea sigur
nume cu apostrofuri.

612
00:25:45,400 --> 00:25:47,399
Poate chiar ar trebui cratimă
du-te acolo, dar veți

613
00:25:47,399 --> 00:25:50,330
a se vedea în p set 5 doar am grijă
despre scrisori și apostrofuri.

614
00:25:50,330 --> 00:25:52,990
>> Și atunci cum Reprezentati
structura de date în sine?

615
00:25:52,990 --> 00:25:56,454
How do you reprezintă rădăcina
din acest trie, ca să spunem așa?

616
00:25:56,454 --> 00:25:59,620
Ei bine, la fel ca și cu o listă legată, tu
au nevoie de un pointer la primul element.

617
00:25:59,620 --> 00:26:04,270
Cu un trie ai nevoie doar de un singur
pointer la rădăcina acestei trie.

618
00:26:04,270 --> 00:26:07,290
Și de acolo puteți distribuire
-ți de drum în jos adânc și mai adânc

619
00:26:07,290 --> 00:26:10,460
la fiecare alt nod din structură.

620
00:26:10,460 --> 00:26:13,440
Deci, pur și simplu, cu această cutie
noi reprezentăm că struct.

621
00:26:13,440 --> 00:26:15,877
>> Acum Meanwhile-- Oh, întrebare.

622
00:26:15,877 --> 00:26:17,220
>> Audiența: Care e cuvântul bool?

623
00:26:17,220 --> 00:26:20,490
>> DAVID MALAN: cuvânt Bool este
doar aceasta incarnare C

624
00:26:20,490 --> 00:26:22,920
din ceea ce am descris
în această casetă de aici, atunci când

625
00:26:22,920 --> 00:26:26,000
Am început să împartă fiecare dintre
elemente în două bucăți array lui.

626
00:26:26,000 --> 00:26:27,600
Una este un pointer la nodul următor.

627
00:26:27,600 --> 00:26:30,280
De altă parte trebuie să fie
ceva de genul o casetă de selectare

628
00:26:30,280 --> 00:26:33,770
să spun da, există o
cuvânt Daven că se termină aici,

629
00:26:33,770 --> 00:26:35,610
pentru că nu vrem,
în acest moment, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Chiar dacă Dave va fi o
cuvânt legitim, că nu este în trie

631
00:26:39,320 --> 00:26:39,830
încă.

632
00:26:39,830 --> 00:26:40,950
Și D nu este un cuvânt.

633
00:26:40,950 --> 00:26:42,770
Și D-A nu este un cuvânt sau un nume.

634
00:26:42,770 --> 00:26:45,020
Deci, bifa
indică o singură dată tu

635
00:26:45,020 --> 00:26:48,190
a lovit acest nod este
cale precedent de caractere

636
00:26:48,190 --> 00:26:50,700
de fapt, un șir care le-ați introdus.

637
00:26:50,700 --> 00:26:53,660
Deci, asta e tot bool
acolo se face pentru noi.

638
00:26:53,660 --> 00:26:55,500
>> Orice alte întrebări cu privire la încercări?

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

640
00:26:56,215 --> 00:26:58,035
>> Audiența: Ce este suprapunerea?

641
00:26:58,035 --> 00:26:59,945
Ce se întâmplă dacă aveți un Dave și o Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID MALAN: Perfect.

643
00:27:00,820 --> 00:27:02,580
Ce se întâmplă dacă aveți un Dave și o Daven?

644
00:27:02,580 --> 00:27:06,240
Deci, dacă am introduce, spune un pseudonim,
pentru David-- Dave-- D-A-V-E?

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

646
00:27:07,370 --> 00:27:08,700
Aceasta este de fapt foarte simplu.

647
00:27:08,700 --> 00:27:10,325
Așa că doar de gând să ia patru etape.

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

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. Și ce trebuie să
face o dată am lovit că al patrulea nod?

650
00:27:15,847 --> 00:27:16,680
Doar de gând să verifice.

651
00:27:16,680 --> 00:27:18,000
Suntem deja bine să plec.

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

653
00:27:18,840 --> 00:27:19,750
Patru pași.

654
00:27:19,750 --> 00:27:21,590
Constanta de timp asimptotic.

655
00:27:21,590 --> 00:27:26,300
Și acum am arătat că atât Dave
și Daven sunt șiruri în structura.

656
00:27:26,300 --> 00:27:27,710
Deci, nu este o problemă.

657
00:27:27,710 --> 00:27:30,200
Și observați modul în care prezența
de Daven nu-l face

658
00:27:30,200 --> 00:27:34,750
să ia orice mai mult timp sau mai puțin
timp de Dave și vice-versa.

659
00:27:34,750 --> 00:27:36,000
>> Deci, ce altceva putem să facem acum?

660
00:27:36,000 --> 00:27:40,680
Am folosit această metaforă înainte
tăvi reprezentând ceva.

661
00:27:40,680 --> 00:27:43,380
Dar se pare că o
teanc de tăvi este de fapt

662
00:27:43,380 --> 00:27:47,187
demonstrativ de un alt datelor abstract
type-- o structură de date de nivel superior

663
00:27:47,187 --> 00:27:49,770
că, la sfârșitul zilei este doar
cum ar fi un tablou sau o listă de legat

664
00:27:49,770 --> 00:27:50,970
sau ceva mai mult lumesc.

665
00:27:50,970 --> 00:27:53,270
Dar este o mult mai interesant
Conceptul conceptual.

666
00:27:53,270 --> 00:27:56,440
Un teanc, cum ar fi acestea
tăvilor aici, în Mather,

667
00:27:56,440 --> 00:27:58,750
sunt, în general, numite
doar that-- o stivă.

668
00:27:58,750 --> 00:28:02,540
>> Și în acest tip de structură de date
aveți două operations--

669
00:28:02,540 --> 00:28:05,880
aveți unul numit apăsare pentru
adăugând ceva la stiva,

670
00:28:05,880 --> 00:28:08,320
cum ar fi punerea altă tavă
înapoi pe partea de sus a stivei.

671
00:28:08,320 --> 00:28:11,350
Și apoi pop, care înseamnă
ia cel mai de sus off tavă.

672
00:28:11,350 --> 00:28:16,210
Dar ceea ce este esențial despre o stivă este că
ea are această caracteristică curios.

673
00:28:16,210 --> 00:28:19,560
Ca personalul sala de mese sunt
rearanjarea tăvile pentru masa urmatoare,

674
00:28:19,560 --> 00:28:21,380
ce va fi
adevărat despre modul în care elevii

675
00:28:21,380 --> 00:28:22,856
interacționa cu această structură de date?

676
00:28:22,856 --> 00:28:24,480
Audiența: Au de gând să pop un off.

677
00:28:24,480 --> 00:28:26,550
DAVID MALAN: Au de gând să
pop un off, sperăm, în partea de sus.

678
00:28:26,550 --> 00:28:28,910
În caz contrar, e doar un fel de stupid
pentru a merge tot drumul la partea de jos.

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

680
00:28:29,070 --> 00:28:31,620
Structura de date nu permite într-adevăr
să vă apuca tava de jos, cel puțin

681
00:28:31,620 --> 00:28:32,520
ușurință.

682
00:28:32,520 --> 00:28:35,040
Deci, există această curios
proprietate la o stivă

683
00:28:35,040 --> 00:28:39,730
că ultimul element din este
Va fi un prim out.

684
00:28:39,730 --> 00:28:43,400
Si oamenii de stiinta de calculator apel
acest LIFO-- ultimul intrat, primul ieșit.

685
00:28:43,400 --> 00:28:45,540
Și este de fapt are
aplicatii interesante.

686
00:28:45,540 --> 00:28:50,090
Nu e neaparat la fel de evident ca unii
alții, dar poate, într-adevăr, să fie util,

687
00:28:50,090 --> 00:28:54,040
și poate, într-adevăr, să fie pus în aplicare
într-o pereche de moduri diferite.

688
00:28:54,040 --> 00:28:58,550
>> Așa că, și de fapt, să
mă să nu se scufunde în asta.

689
00:28:58,550 --> 00:28:59,860
Hai să facem acest lucru în schimb.

690
00:28:59,860 --> 00:29:03,700
Să ne uităm la unul care e aproape
aceeași idee, dar e un pic mai echitabilă.

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

692
00:29:04,200 --> 00:29:07,560
Daca esti unul dintre acesti baieti ventilator sau
fete care îi place într-adevăr produsele Apple

693
00:29:07,560 --> 00:29:10,130
și te-ai trezit la 3:00
să se alinieze la un magazin

694
00:29:10,130 --> 00:29:14,150
pentru a obține cele mai recente foarte iPhone, tu
ar fi coada de așteptare până ca aceasta.

695
00:29:14,150 --> 00:29:15,800
>> Acum, o coadă este foarte deliberat pe nume.

696
00:29:15,800 --> 00:29:18,190
E o linie pentru că există
unii echitate la ea.

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

698
00:29:18,690 --> 00:29:21,690
Ar fel de supt, dacă ai
ajuns acolo în primul rând la Apple Store

699
00:29:21,690 --> 00:29:25,700
dar esti eficient de jos
tavă pentru că angajații Apple a atunci

700
00:29:25,700 --> 00:29:28,189
pop ultima persoană care
de fapt, a intrat în linie.

701
00:29:28,189 --> 00:29:31,230
Deci, stive și cozi, chiar dacă
funcțional sunt un fel de same--

702
00:29:31,230 --> 00:29:33,105
e doar această colecție
de resurse care este

703
00:29:33,105 --> 00:29:36,210
de gând să crească și shrink-- acolo a
acest aspect corectitudine a acesteia,

704
00:29:36,210 --> 00:29:39,634
cel puțin în lumea reală, la,
în cazul în care operațiunile de efort fizic

705
00:29:39,634 --> 00:29:40,800
sunt fundamental diferite.

706
00:29:40,800 --> 00:29:43,360
Un stack-- o coadă
rather-- se spune că au

707
00:29:43,360 --> 00:29:45,320
două operațiuni de coadă: n și de cozi d.

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

709
00:29:46,341 --> 00:29:48,090
Sau le puteți apela
orice număr de lucruri.

710
00:29:48,090 --> 00:29:50,770
Dar tu vrei doar pentru a capta
ideea că unul este adăugarea

711
00:29:50,770 --> 00:29:53,230
și unul este în cele din urmă scăzând.

712
00:29:53,230 --> 00:29:58,840
>> Acum sub capota, atât stiva
și o coadă ar putea fi puse în aplicare cât?

713
00:29:58,840 --> 00:30:01,390
Nu vom merge în codul de
aceasta deoarece nivelul superior

714
00:30:01,390 --> 00:30:03,387
Ideea este un fel de mai evidentă.

715
00:30:03,387 --> 00:30:04,470
Adică, ce fac oamenii?

716
00:30:04,470 --> 00:30:07,030
Dacă eu sunt prima persoana de la Apple
Stoca și aceasta este ușa din față,

717
00:30:07,030 --> 00:30:08,130
Știi, am de gând să stau aici.

718
00:30:08,130 --> 00:30:09,750
Și următoarea persoanei
O să stau aici.

719
00:30:09,750 --> 00:30:11,500
Și următoarea persoanei
O să stau aici.

720
00:30:11,500 --> 00:30:13,792
Deci, ce structură de date
se pretează la o coadă?

721
00:30:13,792 --> 00:30:14,542
>> Audiența: O coadă.

722
00:30:14,542 --> 00:30:15,667
DAVID MALAN: Ei bine, o listă de așteptare.

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

724
00:30:16,390 --> 00:30:16,920
Ce altceva?

725
00:30:16,920 --> 00:30:17,600
>> Audiența: O listă legat.

726
00:30:17,600 --> 00:30:18,990
>> DAVID MALAN: A postat
lista pe care ar putea să pună în aplicare.

727
00:30:18,990 --> 00:30:22,500
Și o listă legat este frumos, pentru că atunci
aceasta poate crește în mod arbitrar de mult, spre deosebire de

728
00:30:22,500 --> 00:30:24,880
de a avea un numar fix
de oameni în magazin.

729
00:30:24,880 --> 00:30:27,030
Dar poate un număr fix
de locuri este legitim.

730
00:30:27,030 --> 00:30:30,350
Pentru că dacă au doar ca 20
iPhone în prima zi, poate

731
00:30:30,350 --> 00:30:33,930
au nevoie de doar o serie de dimensiuni
20 pentru a reprezenta coadă, ceea ce

732
00:30:33,930 --> 00:30:37,070
este doar să spun acum, odată ce vom începe să vorbim
despre aceste probleme de nivel superior,

733
00:30:37,070 --> 00:30:38,890
puteți să-l pună în aplicare
în orice număr de moduri.

734
00:30:38,890 --> 00:30:42,030
Și există, probabil, doar de gând să
fie un compromis în spațiu și timp

735
00:30:42,030 --> 00:30:43,950
sau pur și simplu în propria complexitate cod.

736
00:30:43,950 --> 00:30:45,380
>> Ce zici de o stivă?

737
00:30:45,380 --> 00:30:48,190
Ei bine, o stivă, am vazut prea
ar putea fi doar aceste tăvi.

738
00:30:48,190 --> 00:30:50,007
Și ați putea pune în aplicare această o matrice.

739
00:30:50,007 --> 00:30:53,090
Dar, la un moment dat, dacă utilizați o matrice,
ce se va întâmpla cu tăvile

740
00:30:53,090 --> 00:30:54,173
sunteți încercarea de a pune în jos?

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

742
00:30:55,170 --> 00:30:55,670
Bine.

743
00:30:55,670 --> 00:30:57,490
Te duci doar la
să poată să meargă atât de mare.

744
00:30:57,490 --> 00:31:00,156
Și cred că în Mather sunt
de fapt, încastrate în acea deschidere.

745
00:31:00,156 --> 00:31:01,950
Așa că, într-adevăr, e aproape
ca Mather se utilizează

746
00:31:01,950 --> 00:31:03,783
o serie de dimensiune fixă,
pentru că poți doar

747
00:31:03,783 --> 00:31:08,302
se potrivesc atât de multe tăvi în care deschiderea în
perete jos de genunchi oamenilor.

748
00:31:08,302 --> 00:31:10,010
Și astfel, care ar putea fi
a declarat a fi o matrice,

749
00:31:10,010 --> 00:31:14,300
dar am putea pune în aplicare cu siguranță că
mai mult, în general, cu o listă legat.

750
00:31:14,300 --> 00:31:16,390
>> Ei bine, ce zici de o altă structură de date?

751
00:31:16,390 --> 00:31:18,760
Lasă-mă trage în sus un alt vizual aici.

752
00:31:18,760 --> 00:31:24,710
Ceva de genul cum despre asta aici?

753
00:31:24,710 --> 00:31:28,920
De ce s-ar putea fi util pentru a nu avea
ceva la fel de fantezie ca un trie, care

754
00:31:28,920 --> 00:31:32,370
am văzut avut aceste noduri foarte largi,
fiecare dintre aceștia fiind într-o matrice?

755
00:31:32,370 --> 00:31:35,740
Dar ce se întâmplă dacă facem ceva mai mult
pur și simplu, ca un arbore genealogic de școală veche,

756
00:31:35,740 --> 00:31:38,110
fiecare din ale cărui noduri aici
doar stochează un număr.

757
00:31:38,110 --> 00:31:42,180
În loc de un nume sau un descendent
doar stochează un număr de genul asta.

758
00:31:42,180 --> 00:31:45,250
>> Ei bine, jargonul vom folosi în
structuri de date este atat încercări

759
00:31:45,250 --> 00:31:49,510
și copaci, în cazul în care un trie, din nou, este
doar unul a cărui noduri sunt tablouri,

760
00:31:49,510 --> 00:31:51,680
este încă ceea ce s-ar putea
utilizeze, începând cu școala primară

761
00:31:51,680 --> 00:31:53,860
atunci când a făcut-o familie
frunze tree-- și rădăcină

762
00:31:53,860 --> 00:31:57,250
de copac și copii ai
mamă și frații acestora.

763
00:31:57,250 --> 00:32:03,670
Și am putea pune în aplicare un copac,
de exemplu, la fel de simplu ca aceasta.

764
00:32:03,670 --> 00:32:07,420
Un copac, în cazul în care ca un nod, unul dintre
aceste cercuri, care are un număr,

765
00:32:07,420 --> 00:32:09,947
ea nu va avea
un pointer, dar doi.

766
00:32:09,947 --> 00:32:11,780
Și, de îndată ce vă adăugați
un al doilea indicator, tu

767
00:32:11,780 --> 00:32:13,905
poate acum de fapt, face un fel
de date bidimensional

768
00:32:13,905 --> 00:32:14,780
Structuri din memorie.

769
00:32:14,780 --> 00:32:16,660
Mai mult ca un bi-dimensional
matrice, puteți

770
00:32:16,660 --> 00:32:18,904
au un fel de două-dimensional
Lista postat, dar cele

771
00:32:18,904 --> 00:32:20,820
că urmează un model
în cazul în care nu exista nici cicluri.

772
00:32:20,820 --> 00:32:24,487
Este cu adevărat un copac cu un
mod bunic aici și apoi

773
00:32:24,487 --> 00:32:27,320
unii părinți și copii și
nepoți și strănepoți.

774
00:32:27,320 --> 00:32:28,370
și așa mai departe.

775
00:32:28,370 --> 00:32:32,390
>> Dar ceea ce este cu adevarat elegant despre asta,
doar pentru a vă tachineze cu ceva cod,

776
00:32:32,390 --> 00:32:35,370
rechemare recursivitate de la
un timp înapoi, prin care

777
00:32:35,370 --> 00:32:38,220
vă scrie o funcție care se numește.

778
00:32:38,220 --> 00:32:41,140
Aceasta este o oportunitate de frumos
să pună în aplicare ceva

779
00:32:41,140 --> 00:32:42,920
ca recursivitate, pentru că ia în considerare acest lucru.

780
00:32:42,920 --> 00:32:43,860
>> Acesta este un copac.

781
00:32:43,860 --> 00:32:48,040
Și eu am fost un pic anal cu cât
Am pus numerele întregi în stradă.

782
00:32:48,040 --> 00:32:51,020
Atât de mult, astfel că are o deosebită
name-- un arbore binar de căutare.

783
00:32:51,020 --> 00:32:53,460
Acum am auzit de binar
căutare, dar poate tu

784
00:32:53,460 --> 00:32:55,180
de lucru înapoi de la numele asta lui?

785
00:32:55,180 --> 00:32:59,280
Care este modelul de cum am
introduc numerele întregi în acest copac?

786
00:32:59,280 --> 00:33:00,696
Nu e arbitrar.

787
00:33:00,696 --> 00:33:01,570
Nu e ceva model.

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

789
00:33:02,090 --> 00:33:03,370
>> Audiența: cele mai mici de pe partea stângă.

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

791
00:33:03,690 --> 00:33:05,062
Cele mai mici sunt pe partea stângă.

792
00:33:05,062 --> 00:33:06,270
Cele mai mari sunt pe dreapta.

793
00:33:06,270 --> 00:33:12,940
Astfel încât o afirmație adevărată este o
mamă este mai mare decât copilul său stâng,

794
00:33:12,940 --> 00:33:14,850
dar mai mică de copil dreptul său.

795
00:33:14,850 --> 00:33:17,750
Și care singur este chiar un
definiție verbal recursiv

796
00:33:17,750 --> 00:33:20,500
pentru că puteți aplica asta
aceeași logică a fiecărui nod

797
00:33:20,500 --> 00:33:23,080
și ea doar fundul
out, un caz de bază, dacă

798
00:33:23,080 --> 00:33:25,740
va fi, atunci când a lovit unul dintre
frunzele, ca să spunem așa,

799
00:33:25,740 --> 00:33:28,580
în cazul în care un concediu mai are nici copii.

800
00:33:28,580 --> 00:33:30,614
>> Acum, cum ar putea să vă găsi numărul 44?

801
00:33:30,614 --> 00:33:32,280
Te-ar începe de la rădăcină și să spună, hm.

802
00:33:32,280 --> 00:33:35,690
55 nu este 44 Și eu vreau să merg
drept sau nu vreau să merg la stânga?

803
00:33:35,690 --> 00:33:37,190
Ei bine, evident, vrei să mergi stanga.

804
00:33:37,190 --> 00:33:40,060
Și așa e la fel ca la telefon
exemplu de carte în căutare binar

805
00:33:40,060 --> 00:33:41,099
mai general.

806
00:33:41,099 --> 00:33:43,390
Dar suntem o punere în aplicare
acum un pic mai dinamic

807
00:33:43,390 --> 00:33:45,339
decât o matrice-ar putea permite.

808
00:33:45,339 --> 00:33:48,130
Și, de fapt, dacă vrei să te uiți
la codul, la prima vedere sigur.

809
00:33:48,130 --> 00:33:49,671
Se pare ca o grămadă de linii.

810
00:33:49,671 --> 00:33:51,220
Dar e frumos simplu.

811
00:33:51,220 --> 00:33:54,490
Dacă doriți să pună în aplicare o funcție
numit de căutare al cărui scop în viață

812
00:33:54,490 --> 00:33:57,290
de a va cauta o valoare
ca n, un număr întreg,

813
00:33:57,290 --> 00:34:01,756
si tu esti trecut într-un pointer-- una
un pointer la nodul de rădăcini,

814
00:34:01,756 --> 00:34:04,380
mai degrabă, de acel copac din care
puteți accesa orice altceva,

815
00:34:04,380 --> 00:34:08,850
observa cât de direct
puteți pune în aplicare logica.

816
00:34:08,850 --> 00:34:10,880
Dacă copac este nul,
în mod evident, nu e acolo.

817
00:34:10,880 --> 00:34:11,880
Să se întoarcă false.

818
00:34:11,880 --> 00:34:12,000
Dreapta?

819
00:34:12,000 --> 00:34:14,040
Dacă vă predați-l nimic,
nu e nimic acolo.

820
00:34:14,040 --> 00:34:17,900
>> Altfel, dacă n este mai mic de
sageata copac N- acum săgeată n,

821
00:34:17,900 --> 00:34:20,670
amintesc am introdus super-
scurt de altă zi,

822
00:34:20,670 --> 00:34:25,100
și asta înseamnă că doar de-referința
pointer si uita-te la câmpul numit n.

823
00:34:25,100 --> 00:34:27,690
Deci, aceasta înseamnă du-te acolo și
uita-te la câmpul numit n.

824
00:34:27,690 --> 00:34:33,810
Deci, dacă n, valoarea bază dat, este mai puțin
decât valoarea din întreg copaci,

825
00:34:33,810 --> 00:34:35,449
în cazul în care vrei să mergi?

826
00:34:35,449 --> 00:34:36,389
La stânga.

827
00:34:36,389 --> 00:34:37,780
>> Deci, observați recursivitatea.

828
00:34:37,780 --> 00:34:39,860
Eu returning-- nu este adevărat.

829
00:34:39,860 --> 00:34:40,989
Nu este fals.

830
00:34:40,989 --> 00:34:45,670
Mă întorc, indiferent de răspunsul
este de la un apel la mine, care trece

831
00:34:45,670 --> 00:34:50,100
un n din nou, care este redundantă,
dar ceea ce este puțin diferit acum?

832
00:34:50,100 --> 00:34:51,989
Cum mă face problema mai mica?

833
00:34:51,989 --> 00:34:54,920
Sunt trece în drept a doua
argument, nu rădăcină de copac,

834
00:34:54,920 --> 00:34:59,616
dar copilul din stânga, în acest caz.

835
00:34:59,616 --> 00:35:00,990
Deci, eu sunt asociate de la copilul din stânga.

836
00:35:00,990 --> 00:35:04,720
>> Între timp, dacă n este mai mare decât
nodul Eu sunt în prezent în căutarea la,

837
00:35:04,720 --> 00:35:06,690
Caut de pe partea dreaptă.

838
00:35:06,690 --> 00:35:10,880
Altfel, dacă pomul nu este nulă, și
dacă elementul nu este la stânga

839
00:35:10,880 --> 00:35:13,240
și nu e de dreapta,
ceea ce este minunat în cazul?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Am descoperit, de fapt, nodul de la
întrebare, și așa ne întoarcem adevărat.

842
00:35:18,440 --> 00:35:21,490
>> Deci, tocmai am zgâriat suprafața
acum unele dintre aceste structuri de date.

843
00:35:21,490 --> 00:35:24,370
În problemă a seta cinci veți
excursiile acestea încă mai departe,

844
00:35:24,370 --> 00:35:27,250
și veți fi dat design-ul
alegere a modului de a merge cu privire la acest lucru.

845
00:35:27,250 --> 00:35:30,250
Ce aș vrea să închei pe
este doar un al doilea teaser de 30

846
00:35:30,250 --> 00:35:32,080
de ceea ce așteaptă săptămâna viitoare și dincolo.

847
00:35:32,080 --> 00:35:35,390
>> Așa cum am begin-- din fericire s-ar putea
think-- tranziție noastră încet

848
00:35:35,390 --> 00:35:38,680
din lumea C și mai mic
Detalii de implementare nivel,

849
00:35:38,680 --> 00:35:42,090
într-o lume în care putem lua pentru
a acordat că altcineva are în cele din urmă

850
00:35:42,090 --> 00:35:44,010
puse în aplicare aceste date
structuri pentru noi,

851
00:35:44,010 --> 00:35:47,570
și vom începe să înțelegem
lumea reală mijloace de punere în aplicare

852
00:35:47,570 --> 00:35:50,560
programe bazate pe web și
site-uri mai mult, în general,

853
00:35:50,560 --> 00:35:52,910
și, de asemenea, foarte securitate
implicațiile pe care le-am doar

854
00:35:52,910 --> 00:35:54,850
a început să zgârie suprafața de.

855
00:35:54,850 --> 00:35:57,320
Iată ce ne așteaptă
în zilele următoare.

856
00:35:57,320 --> 00:36:00,480
>> [VIDEO PLAYBACK]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -A Venit cu un mesaj,
cu un protocol toată proprie.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
El a venit la o lume de crudă
firewall-uri, routere nepăsătoare,

861
00:36:30,894 --> 00:36:33,368
și pericole mult mai rău decât moartea.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
El este rapid.

864
00:36:36,236 --> 00:36:37,980
E puternic.

865
00:36:37,980 --> 00:36:42,830
E TCP / IP, și el are adresa ta.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Warriors of net."

868
00:36:48,074 --> 00:36:49,660
[END VIDEO PLAYBACK]

869
00:36:49,660 --> 00:36:50,910
DAVID MALAN: primește săptămâna viitoare.

870
00:36:50,910 --> 00:36:51,880
Ne veți vedea atunci.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[VIDEO PLAYBACK]

873
00:36:56,060 --> 00:36:59,240
-Si Acum, "Gânduri profunde"
de Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Începe întotdeauna
prelegeri cu "Bine".

876
00:37:05,820 --> 00:37:08,750
De ce nu, "Aici e solutia
la set problemă din această săptămână "

877
00:37:08,750 --> 00:37:12,180
sau "Suntem oferindu voi toti o A?"

878
00:37:12,180 --> 00:37:13,380
[Rîzînd]

879
00:37:13,380 --> 00:37:15,530
[END VIDEO PLAYBACK]