1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Bine, deci acest lucru este
CS50 Acesta este sfârșitul săptămânii cinci.

3
00:00:15,860 --> 00:00:19,220
Și reamintească faptul că ultima dată am
a inceput sa caute la datele crescator

4
00:00:19,220 --> 00:00:22,310
structuri care au început să rezolve
probleme, care au început să introducă

5
00:00:22,310 --> 00:00:25,640
noi probleme, dar cheia pentru acest
era genul de filetare pe care le

6
00:00:25,640 --> 00:00:27,940
a început să facă de la nod la nod.

7
00:00:27,940 --> 00:00:30,085
Deci, aceasta este, desigur,
o listă individual legat.

8
00:00:30,085 --> 00:00:31,960
Și de individual legate,
Adică nu e doar o

9
00:00:31,960 --> 00:00:33,380
fir între fiecare dintre aceste noduri.

10
00:00:33,380 --> 00:00:35,890
Se pare că poți să faci crescator
lucruri cum ar fi liste de două ori legate

11
00:00:35,890 --> 00:00:38,470
prin care aveți o săgeată
merge în ambele direcții, care

12
00:00:38,470 --> 00:00:40,320
poate ajuta cu anumite eficiență.

13
00:00:40,320 --> 00:00:42,000
Dar acest lucru a rezolvat problema?

14
00:00:42,000 --> 00:00:43,500
Ce problemă a rezolva acest lucru?

15
00:00:43,500 --> 00:00:46,620
De ce a ne pasa de luni?

16
00:00:46,620 --> 00:00:49,820
De ce, în teorie, am grijă de luni?

17
00:00:49,820 --> 00:00:50,630
Ce face?

18
00:00:50,630 --> 00:00:51,950
>> Audiența: putem redimensiona dinamic.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, astfel încât să putem
dinamic al redimensiona.

20
00:00:53,740 --> 00:00:54,710
Bine făcut amândoi.

21
00:00:54,710 --> 00:00:57,560
Astfel încât să puteți redimensiona dinamic această
structură de date, în timp ce o matrice,

22
00:00:57,560 --> 00:01:00,760
Reamintim, trebuie să știi un
priori cât de mult spațiu pe care doriți

23
00:01:00,760 --> 00:01:03,870
Și dacă ai nevoie de un pic mai mult
spațiu, ești un fel de noroc.

24
00:01:03,870 --> 00:01:05,560
Trebuie să creați o gamă cu totul nou.

25
00:01:05,560 --> 00:01:07,893
Trebuie să muta toate dvs.
date de la unul la altul,

26
00:01:07,893 --> 00:01:10,600
în cele din urmă a elibera matrice vechi
dacă poți, și apoi continua.

27
00:01:10,600 --> 00:01:13,891
Care tocmai se simte foarte costisitoare și foarte
ineficiente, și într-adevăr poate fi.

28
00:01:13,891 --> 00:01:14,890
Dar aceasta nu este totul bine.

29
00:01:14,890 --> 00:01:18,180
Plătim un preț, ceea ce a fost un
prețurilor mai evidente ne

30
00:01:18,180 --> 00:01:20,550
plata prin utilizarea unei liste legat?

31
00:01:20,550 --> 00:01:22,825
>> Audiența: Trebuie să utilizați
spațiu dublu pentru fiecare dintre ele.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Da, asa ca avem nevoie
cel puțin de două ori mai mult spațiu.

33
00:01:25,200 --> 00:01:27,700
De fapt, am realizat această imagine a lui
chiar un pic înșelătoare,

34
00:01:27,700 --> 00:01:32,200
deoarece pe IDE CS50 într-o mulțime de moderne
computere, un pointer sau o adresă

35
00:01:32,200 --> 00:01:33,700
nu este de fapt patru octeți.

36
00:01:33,700 --> 00:01:36,090
Este foarte des acestea
zile opt bytes, care

37
00:01:36,090 --> 00:01:38,530
înseamnă partea de jos mai
dreptunghiuri acolo în realitate

38
00:01:38,530 --> 00:01:40,900
sunt un fel de două ori mai
de mare ca ceea ce am desenat,

39
00:01:40,900 --> 00:01:44,409
ceea ce înseamnă că utilizați de trei ori mai
mult spatiu ca am putea fi altfel.

40
00:01:44,409 --> 00:01:46,700
Acum, în același timp, suntem
încă mai vorbesc bytes, nu?

41
00:01:46,700 --> 00:01:49,140
Noi nu neapărat vorbesc
megabytes sau gigabytes,

42
00:01:49,140 --> 00:01:51,000
cu excepția cazului în aceste structuri de date ajunge mare.

43
00:01:51,000 --> 00:01:54,510
>> Și așa astăzi vom începe să ia în considerare
cum am putea explora date

44
00:01:54,510 --> 00:01:57,310
mai eficient dacă în
De fapt, datele devine mai mare.

45
00:01:57,310 --> 00:02:00,360
Dar să încercăm să canonic
operațiunile primele

46
00:02:00,360 --> 00:02:02,460
pe care le puteți face pe acestea
tipuri de structuri de date.

47
00:02:02,460 --> 00:02:04,790
Deci, ceva ca o legătură
Lista sprijină, în general,

48
00:02:04,790 --> 00:02:07,514
operațiuni place ștergeți,
insera, si cauta.

49
00:02:07,514 --> 00:02:08,639
Și ce vreau să spun cu asta?

50
00:02:08,639 --> 00:02:11,222
Asta înseamnă doar că, de obicei,,
dacă oamenii sunt utilizați lista legate,

51
00:02:11,222 --> 00:02:14,287
ei sau altcineva a pus în aplicare
funcții cum ar fi Ștergere, Inserare,

52
00:02:14,287 --> 00:02:16,120
și de căutare, astfel încât să puteți
face de fapt ceva

53
00:02:16,120 --> 00:02:18,030
utile cu structura de date.

54
00:02:18,030 --> 00:02:20,760
Deci, haideți să aruncăm o privire rapidă
la cum am putea pune în aplicare

55
00:02:20,760 --> 00:02:24,530
unele cod pentru o listă legată, după cum urmează.

56
00:02:24,530 --> 00:02:27,885
>> Deci, aceasta este doar un cod C,
nici măcar un program complet

57
00:02:27,885 --> 00:02:29,260
că eu chiar repede incitat.

58
00:02:29,260 --> 00:02:32,300
Nu e online în distribuția
cod, pentru că nu va rula de fapt.

59
00:02:32,300 --> 00:02:33,790
Dar observați Am doar
cu un comentariu a spus,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, e ceva
acolo, dot dot dot, ceva acolo.

61
00:02:36,130 --> 00:02:38,410
Și să uita doar la
ce piesele suculente sunt.

62
00:02:38,410 --> 00:02:40,790
Deci, pe linia trei,
reamintească faptul că acest lucru este acum

63
00:02:40,790 --> 00:02:45,960
Am propus declararea un nod trecut
timp, una dintre aceste obiecte dreptunghiulare.

64
00:02:45,960 --> 00:02:48,790
Acesta are o int care vom suna N,
dar am putea numi orice,

65
00:02:48,790 --> 00:02:51,920
și apoi o stea nod struct numit următor.

66
00:02:51,920 --> 00:02:55,520
Și doar pentru a fi clar, că de-al doilea
linie, pe linia șase, ce e asta?

67
00:02:55,520 --> 00:02:57,930
Ce o face pentru noi?

68
00:02:57,930 --> 00:03:01,044
Pentru că cu siguranță pare mai
criptic decât variabilele noastre obișnuite.

69
00:03:01,044 --> 00:03:02,740
>> Audiența: Se face muta peste o.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Se face muta peste o.

71
00:03:04,650 --> 00:03:08,580
Și pentru a fi mai precis,
se va stoca adresa

72
00:03:08,580 --> 00:03:11,582
de nodul care este menit să fie
semantic lângă el, nu?

73
00:03:11,582 --> 00:03:13,540
Deci, nu va
muta neapărat ceva.

74
00:03:13,540 --> 00:03:15,290
E doar de gând să
stoca o valoare, care este

75
00:03:15,290 --> 00:03:17,170
O să fie adresa
de un alt nod,

76
00:03:17,170 --> 00:03:20,810
și de aceea am spus struct
stele nod, steaua denotă

77
00:03:20,810 --> 00:03:22,370
un pointer sau o adresă.

78
00:03:22,370 --> 00:03:26,390
OK, deci acum, dacă presupunem că avem
acest N disponibile pentru noi, și să

79
00:03:26,390 --> 00:03:29,490
presupunem că cineva are altcineva
introdus o grămadă de numere întregi

80
00:03:29,490 --> 00:03:30,400
într-o listă legată.

81
00:03:30,400 --> 00:03:35,640
Și această listă este legată
indicat de un punct

82
00:03:35,640 --> 00:03:39,040
o variabilă numită listă care este
a trecut pe aici ca un parametru,

83
00:03:39,040 --> 00:03:43,120
cum pot face despre line
14 de punere în aplicare de căutare?

84
00:03:43,120 --> 00:03:45,990
Cu alte cuvinte, dacă am de punere în aplicare
Funcția a cărui scop în viață

85
00:03:45,990 --> 00:03:48,889
este de a lua un întreg și apoi
începutul unei liste legate,

86
00:03:48,889 --> 00:03:50,430
că este un pointer la lista legat.

87
00:03:50,430 --> 00:03:52,992
Ca și în primul rând, care a cred David
a fost voluntar la data de Monday,

88
00:03:52,992 --> 00:03:54,700
el a fost îndreptat la
tot legat listă,

89
00:03:54,700 --> 00:03:57,820
e ca și cum ne trece
David în ca argument aici.

90
00:03:57,820 --> 00:03:59,990
Cum vom merge despre care traversează această listă?

91
00:03:59,990 --> 00:04:04,640
Ei bine, se pare că, deși
indicii sunt relativ noi acum pentru noi,

92
00:04:04,640 --> 00:04:07,010
putem face acest lucru relativ
direct.

93
00:04:07,010 --> 00:04:09,500
>> Am de gând să merg mai departe și
declara o variabilă temporară care

94
00:04:09,500 --> 00:04:12,364
prin convenție este doar de gând
să fie numit pointer, sau PTR,

95
00:04:12,364 --> 00:04:14,030
dar ai putea numi tot ce vrei.

96
00:04:14,030 --> 00:04:16,470
Și am de gând pentru a inițializa
l la începutul listei.

97
00:04:16,470 --> 00:04:20,050
Astfel încât să puteți fel de a gândi această
ca si mine profesorul de altă zi,

98
00:04:20,050 --> 00:04:23,580
un fel de îndreptat pe cineva
printre oameni noastre ca voluntari.

99
00:04:23,580 --> 00:04:26,470
Deci, eu sunt o variabilă temporară care este
doar arătând spre același lucru

100
00:04:26,470 --> 00:04:31,390
că nostru numit coincidență
voluntar David a fost, de asemenea, subliniind.

101
00:04:31,390 --> 00:04:35,440
Acum în timp ce indicatorul este
nu null, deoarece rechemare

102
00:04:35,440 --> 00:04:40,350
că nulă este o anumită valoare deosebită Sentinel
delimitează sfârșitul listei,

103
00:04:40,350 --> 00:04:44,280
Deci, în timp nu am îndreptat la
teren ca ultimul nostru voluntar

104
00:04:44,280 --> 00:04:47,190
a fost, să mergem mai departe
și de a face următoarele.

105
00:04:47,190 --> 00:04:51,820
Dacă pointer-- și acum am un fel de vreau
să facem ceea ce am făcut cu elevul

106
00:04:51,820 --> 00:04:57,410
structure-- dacă pointer punct viitoare
equals-- mai degrabă, dacă indicatorul punct N este egal cu

107
00:04:57,410 --> 00:05:02,290
este egal cu variabila N, The
argument care a fost adoptată în,

108
00:05:02,290 --> 00:05:05,370
apoi vreau să merg mai departe
și spune return true.

109
00:05:05,370 --> 00:05:11,020
Am găsit numărul N interiorul
unul dintre nodurile lista mea legate.

110
00:05:11,020 --> 00:05:13,500
Dar punctul nu mai
lucrează în acest context,

111
00:05:13,500 --> 00:05:17,260
pentru că pointer, PTR, este
într-adevăr un pointer, o adresă,

112
00:05:17,260 --> 00:05:20,632
am de fapt, poate minunat
utiliza în cele din urmă o bucată de sintaxă

113
00:05:20,632 --> 00:05:22,590
acest tip de mărci
simț intuitiv și de fapt

114
00:05:22,590 --> 00:05:27,870
utilizați o săgeată aici, ceea ce înseamnă merge de la
acea adresă la întreg acolo în.

115
00:05:27,870 --> 00:05:30,160
Deci, este foarte similară în
spirit operatorului dot,

116
00:05:30,160 --> 00:05:33,860
dar pentru că nu pointer este un pointer
și nu o struct în sine,

117
00:05:33,860 --> 00:05:35,380
vom folosi doar săgeata.

118
00:05:35,380 --> 00:05:40,620
>> Deci, în cazul în care nodul curent că Eu,
variabilă temporară, am arătând spre

119
00:05:40,620 --> 00:05:43,060
nu este N, ceea ce vreau să fac?

120
00:05:43,060 --> 00:05:45,910
Ei bine, cu voluntari umani mele
că am avut aici de altă zi,

121
00:05:45,910 --> 00:05:49,710
dacă prima mea umană nu este cea pe care am
doresc, și poate al doilea om nu este

122
00:05:49,710 --> 00:05:52,660
cel vreau, iar al treilea, am
nevoie pentru a menține în mișcare fizic.

123
00:05:52,660 --> 00:05:54,690
Ca și cum pot parcurge o listă?

124
00:05:54,690 --> 00:05:57,470
Când am avut o serie de tine,
la fel a făcut cum am, plus, plus.

125
00:05:57,470 --> 00:06:03,660
Dar în acest caz, este suficient să se
face pointer, devine, pointer, alături.

126
00:06:03,660 --> 00:06:07,580
Cu alte cuvinte, următorul câmp
este ca toate mâinile stânga

127
00:06:07,580 --> 00:06:10,880
că voluntarii noastre umane luni
au fost utilizați pentru a indica la un alt nod.

128
00:06:10,880 --> 00:06:12,890
Acestea au fost următoarele vecinii lor.

129
00:06:12,890 --> 00:06:17,060
>> Deci, dacă vreau să-și intensifice prin această listă,
Nu pot să fac eu, plus, plus mai,

130
00:06:17,060 --> 00:06:20,120
Trebuie în schimb să spun
I, pointer, se va

131
00:06:20,120 --> 00:06:24,650
la egal indiferent de domeniul următor este,
următorul câmp este, următorul câmp este,

132
00:06:24,650 --> 00:06:28,350
în urma toate aceste mâini stânga
că am avut pe scena de indicare

133
00:06:28,350 --> 00:06:30,000
unor valori ulterioare.

134
00:06:30,000 --> 00:06:32,590
Și dacă mă prin
că întreaga repetare,

135
00:06:32,590 --> 00:06:39,330
și în cele din urmă, l-am lovit nul nu au
găsit N totuși, doar mă întorc false.

136
00:06:39,330 --> 00:06:44,100
Deci, din nou, tot ce facem aici,
ca pe imaginea urmă cu o clipă,

137
00:06:44,100 --> 00:06:47,840
este incepand de îndreptat de la
începutul listei probabil.

138
00:06:47,840 --> 00:06:50,970
Și apoi m-am verifica, este valoarea
Caut egal la nouă?

139
00:06:50,970 --> 00:06:52,650
Dacă este așa, mă întorc adevărat și am terminat.

140
00:06:52,650 --> 00:06:56,450
Dacă nu, actualizați mâna mea,
AKA pointer, la punctul

141
00:06:56,450 --> 00:06:59,540
la locația pe săgeata de lângă, iar
apoi locație pe săgeata de lângă, a

142
00:06:59,540 --> 00:07:00,480
și următorul.

143
00:07:00,480 --> 00:07:03,770
Sunt pur și simplu de mers pe jos am prin această matrice.

144
00:07:03,770 --> 00:07:06,010
>> Deci, din nou, cui îi pasă?

145
00:07:06,010 --> 00:07:07,861
Ca ceea ce este acest ingredient pentru?

146
00:07:07,861 --> 00:07:10,360
Ei bine, amintim că am introdus
noțiunea de stivă, care

147
00:07:10,360 --> 00:07:15,400
este un abstract de date de tip în măsura în care este
nu este un lucru C, nu este un lucru CS50,

148
00:07:15,400 --> 00:07:19,430
este o idee abstractă, această idee de
stivuire lucruri pe partea de sus a unul pe altul

149
00:07:19,430 --> 00:07:21,820
care pot fi implementate în
buchete de moduri diferite.

150
00:07:21,820 --> 00:07:25,600
Și într-un fel ne-am propus a fost cu
o matrice, sau cu o listă legată.

151
00:07:25,600 --> 00:07:29,570
Și se pare că canonic, o
stivă susține cel puțin două operațiuni.

152
00:07:29,570 --> 00:07:32,320
Iar cuvintele Buzz sunt împinge, pentru a
împinge ceva pe stiva,

153
00:07:32,320 --> 00:07:34,770
ca un nou Tray în
sala de mese, sau pop,

154
00:07:34,770 --> 00:07:39,000
ceea ce înseamnă pentru a elimina cel mai de sus
tava din stivă în mese

155
00:07:39,000 --> 00:07:41,500
Hall, iar apoi poate că unele
alte operațiuni, de asemenea.

156
00:07:41,500 --> 00:07:45,770
Deci, cum am putea defini structura
că suntem de asteptare acum o stivă?

157
00:07:45,770 --> 00:07:50,020
>> Ei bine, avem toate necesar
sintaxă la dispoziția noastră în C. am spus,

158
00:07:50,020 --> 00:07:53,830
da-mi o definiție tip de
o struct interiorul-o stivă,

159
00:07:53,830 --> 00:07:58,030
Am de gând să spun este o matrice, de un
grămadă de numere și apoi dimensiunea.

160
00:07:58,030 --> 00:08:00,930
Deci, cu alte cuvinte, dacă vreau
să pună în aplicare acest lucru în cod,

161
00:08:00,930 --> 00:08:03,830
lasă-mă să merg și doar un fel de
remiză ce acest spune.

162
00:08:03,830 --> 00:08:06,317
Deci, acest lucru este de a spune, da-mi un
structură care are o matrice,

163
00:08:06,317 --> 00:08:09,400
și nu știu ce calitate este,
e pare ceva constant care le-am

164
00:08:09,400 --> 00:08:10,858
definit în altă parte, și asta e bine.

165
00:08:10,858 --> 00:08:15,260
Dar să presupunem că e doar unul,
doi, trei, patru, cinci.

166
00:08:15,260 --> 00:08:16,700
Deci capacitatea este de 5.

167
00:08:16,700 --> 00:08:21,730
Acest element în interiorul meu
Structura va fi numit numere.

168
00:08:21,730 --> 00:08:24,020
Și apoi am nevoie de unul
alte variabile aparent

169
00:08:24,020 --> 00:08:27,814
numit dimensiune care initial am de gând
să prevadă este inițializată la zero.

170
00:08:27,814 --> 00:08:29,730
Dacă nu e nimic în
stivă, dimensiunea este zero,

171
00:08:29,730 --> 00:08:31,420
și este valorile de gunoi într-un număr.

172
00:08:31,420 --> 00:08:33,450
Nu am nici o idee despre ce e acolo încă.

173
00:08:33,450 --> 00:08:36,059
>> Deci, dacă vreau să împingă
ceva pe stiva,

174
00:08:36,059 --> 00:08:40,780
Presupun că sun funcția împinge, și
Eu spun împinge 50, cum ar fi numărul 50,

175
00:08:40,780 --> 00:08:44,090
în cazul în care ați propune
Am trage in acest tablou?

176
00:08:44,090 --> 00:08:47,124
Există cinci răspunsuri diferite posibile.

177
00:08:47,124 --> 00:08:48,790
În cazul în care vrei să împingă numărul 50?

178
00:08:48,790 --> 00:08:51,899
În cazul în care obiectivul de aici, din nou, sunați la
functie push, trece într-un argument

179
00:08:51,899 --> 00:08:52,940
50, unde am pus?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Cinci possible-- 20% șanse
de ghicitul în mod corect.

182
00:08:59,052 --> 00:08:59,896
Da?

183
00:08:59,896 --> 00:09:00,740
>> Audiența: extrema dreaptă.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: extrema dreaptă.

185
00:09:01,990 --> 00:09:08,359
Există acum o sansa de 25%
de ghicitul în mod corect.

186
00:09:08,359 --> 00:09:09,650
Deci, care ar fi de fapt bine.

187
00:09:09,650 --> 00:09:12,770
Prin convenție, voi spune, cu o serie,
în general, ne-ar începe de la stânga,

188
00:09:12,770 --> 00:09:14,519
Dar am putea cu siguranță
încep de la dreapta.

189
00:09:14,519 --> 00:09:17,478
Deci, spoilerul aici ar fi că sunt
probabil gând să-l atragă pe stânga,

190
00:09:17,478 --> 00:09:20,060
la fel ca într-o gamă normală în cazul în care
Am începe să mergi la stânga la dreapta.

191
00:09:20,060 --> 00:09:21,780
Dar dacă puteți răsturna
aritmetica, bine.

192
00:09:21,780 --> 00:09:23,060
Nu este vorba doar convențional.

193
00:09:23,060 --> 00:09:24,880
OK, am nevoie pentru a face o
mai schimba totuși.

194
00:09:24,880 --> 00:09:27,710
Acum, că am împins ceva
pe stiva, ce urmează?

195
00:09:27,710 --> 00:09:29,400
>> Bine, am să incrementa dimensiunea.

196
00:09:29,400 --> 00:09:32,600
Așa că lasă-mă să merg mai departe și doar
actualiza acest, care a fost zero.

197
00:09:32,600 --> 00:09:35,950
Și în loc acum, am de gând
pentru a pune în valoare o.

198
00:09:35,950 --> 00:09:39,460
Și acum că aș împinge un alt
Numărul de pe stiva, cum ar fi 51.

199
00:09:39,460 --> 00:09:42,680
Ei bine, am să fac o mai
schimbare, care este de până la dimensiunea două.

200
00:09:42,680 --> 00:09:46,100
Și apoi că aș împinge unul mai
Numărul de pe stiva ca 61,

201
00:09:46,100 --> 00:09:52,530
acum am nevoie pentru a actualiza dimensiunea o mai
timp, și pentru a obține valoarea 3 ca dimensiunea.

202
00:09:52,530 --> 00:09:54,690
Și acum să presupunem că eu numesc pop.

203
00:09:54,690 --> 00:09:57,250
Acum pop, prin convenție,
nu ia un argument.

204
00:09:57,250 --> 00:10:00,430
Cu un teanc, întreg
punct de metafora tăvii

205
00:10:00,430 --> 00:10:03,450
este că nu aveți putere de apreciere
pentru a du-te că tava, tot ce se poate face

206
00:10:03,450 --> 00:10:06,330
este cel mai de sus pop cea de la
stiva, doar pentru că.

207
00:10:06,330 --> 00:10:08,010
Asta e ceea ce face această structură de date.

208
00:10:08,010 --> 00:10:12,250
>> Deci, prin această logică, dacă am
spune poziție favorabilă, ceea ce vine de pe?

209
00:10:12,250 --> 00:10:13,080
Deci 61.

210
00:10:13,080 --> 00:10:15,402
Deci, ce este cu adevărat computerul
de gând să faci în memorie?

211
00:10:15,402 --> 00:10:16,610
Ce codul meu trebuie să fac?

212
00:10:16,610 --> 00:10:20,330
Ce ați propune
vom schimba pe ecran?

213
00:10:20,330 --> 00:10:23,410
Ce ar trebui să se schimbe?

214
00:10:23,410 --> 00:10:24,960
Ne pare rău?

215
00:10:24,960 --> 00:10:26,334
Așa că am scăpa de 61.

216
00:10:26,334 --> 00:10:27,500
Deci, eu pot face cu siguranta asta.

217
00:10:27,500 --> 00:10:28,640
Și pot scăpa de 61.

218
00:10:28,640 --> 00:10:30,980
Și apoi ce alte
schimbarea trebuie să se întâmple?

219
00:10:30,980 --> 00:10:33,160
Dimensiune, probabil trebuie să se întoarcă la două.

220
00:10:33,160 --> 00:10:34,210
Și așa că e bine.

221
00:10:34,210 --> 00:10:36,690
Dar stai un minut, dimensiune
un moment în urmă a fost de trei.

222
00:10:36,690 --> 00:10:38,240
Hai să facem o verificare bun-simț rapid.

223
00:10:38,240 --> 00:10:41,810
Cum am ști că am
a vrut să scape de 61?

224
00:10:41,810 --> 00:10:42,760
Pentru ca suntem popping.

225
00:10:42,760 --> 00:10:46,450
Și așa că am această a doua dimensiune proprietate.

226
00:10:46,450 --> 00:10:48,470
>> Stai puțin, eu sunt
gândire înapoi la doua saptamani

227
00:10:48,470 --> 00:10:51,660
când am început să vorbim despre
tablouri, în cazul în care acest lucru a fost locația de zero,

228
00:10:51,660 --> 00:10:55,920
acest lucru a fost o locație, aceasta a fost locație
doua, aceasta este locația de trei, patru,

229
00:10:55,920 --> 00:10:58,460
Se pare ca
relație între dimensiunea

230
00:10:58,460 --> 00:11:02,780
și elementul care doresc să eliminați
din matrice pare să fie exact ceea ce?

231
00:11:02,780 --> 00:11:05,120
Dimensiune minus unul.

232
00:11:05,120 --> 00:11:07,786
Și așa așa ca oameni
știm 61 este pe primul loc.

233
00:11:07,786 --> 00:11:09,160
Cum computerul va ști?

234
00:11:09,160 --> 00:11:11,701
Când codul, în cazul în care probabil că
vrei sa faci dimensiunea minus unul,

235
00:11:11,701 --> 00:11:14,950
așa unul cu trei minus este doi, și că
înseamnă vrem să scăpăm de 61.

236
00:11:14,950 --> 00:11:18,000
Și atunci putem actualiza într-adevăr
dimensiunea astfel încât dimensiunea acum

237
00:11:18,000 --> 00:11:20,300
merge de la trei la doar două.

238
00:11:20,300 --> 00:11:24,520
Și doar pentru a fi pedant, am de gând
să propună am terminat, nu?

239
00:11:24,520 --> 00:11:27,660
Tu propus intuitiv
corect ar trebui să scape de 61.

240
00:11:27,660 --> 00:11:30,700
Dar nu le-am un fel de
un fel de scăpat de 61?

241
00:11:30,700 --> 00:11:33,790
Am uitat în mod eficient
că este de fapt acolo.

242
00:11:33,790 --> 00:11:37,680
Și cred că înapoi la PSET4, dacă ați citit
articolul despre criminalistica, PDF

243
00:11:37,680 --> 00:11:40,780
că am avut voi citi, sau
va citi în această săptămână pentru PSET4.

244
00:11:40,780 --> 00:11:44,300
Amintiti-va ca aceasta este de fapt germane a
ideea de calculator forensics.

245
00:11:44,300 --> 00:11:47,820
Ce calculator, în general, nu este
doar uita în cazul în care ceva este,

246
00:11:47,820 --> 00:11:51,300
dar nu merge în și ca
încercați să-l zero afară sau suprascrie

247
00:11:51,300 --> 00:11:54,560
aceste biți cu zerouri și cele
sau un alt tipar aleatoriu

248
00:11:54,560 --> 00:11:56,690
dacă nu te face acest lucru în mod deliberat.

249
00:11:56,690 --> 00:11:58,930
Deci, intuitia ta era
Bine, să scăpăm de 61.

250
00:11:58,930 --> 00:12:00,650
Dar, în realitate, noi nu trebuie să deranjez.

251
00:12:00,650 --> 00:12:04,040
Trebuie doar să uităm că
e acolo prin schimbarea dimensiunea noastră.

252
00:12:04,040 --> 00:12:05,662
>> Acum există o problemă cu acest stack.

253
00:12:05,662 --> 00:12:07,620
Dacă am păstra împingându lucruri
pe stiva, ceea ce este

254
00:12:07,620 --> 00:12:11,167
evident se va întâmpla
în doar câteva momente de timp?

255
00:12:11,167 --> 00:12:12,500
Vom alerga afară de spațiu.

256
00:12:12,500 --> 00:12:13,580
Și ce facem?

257
00:12:13,580 --> 00:12:14,680
Suntem un fel de filetat.

258
00:12:14,680 --> 00:12:19,000
Această punere în aplicare nu lasa
ne redimensiona matrice, deoarece cu ajutorul

259
00:12:19,000 --> 00:12:21,240
această sintaxă, dacă
cred că înapoi la doua saptamani,

260
00:12:21,240 --> 00:12:23,520
odată ce ați declarat
de dimensiunea unei matrice,

261
00:12:23,520 --> 00:12:26,780
nu am văzut încă în cazul în care un mecanism
aveți posibilitatea să modificați dimensiunea tabloului.

262
00:12:26,780 --> 00:12:29,020
Și într-adevăr C nu are această caracteristică.

263
00:12:29,020 --> 00:12:32,524
Dacă spui da cinci-mi
Nths, le numesc numere,

264
00:12:32,524 --> 00:12:33,940
asta e tot ce ai de gând să-l.

265
00:12:33,940 --> 00:12:38,790
Deci, ce facem acum ca de luni, au
abilitatea de a exprima o soluție

266
00:12:38,790 --> 00:12:42,480
deși, avem nevoie doar pentru a optimiza
definiția stivă noastre

267
00:12:42,480 --> 00:12:46,840
nu să fie o matrice greu codificate,
dar doar pentru a stoca o adresă.

268
00:12:46,840 --> 00:12:47,890
>> Acum, de ce este acest lucru?

269
00:12:47,890 --> 00:12:51,690
Acum trebuie doar să fie confortabil cu
faptul că atunci când programul meu se execută,

270
00:12:51,690 --> 00:12:53,730
Am probabil de gând să
trebuie să ceară umane,

271
00:12:53,730 --> 00:12:55,110
câte numere vrei să stocați?

272
00:12:55,110 --> 00:12:56,776
Deci de intrare trebuie sa vina de undeva.

273
00:12:56,776 --> 00:12:59,140
Dar, odată ce știu că
numărul, atunci eu pot doar

274
00:12:59,140 --> 00:13:02,470
folosi ceea ce funcționează pentru a da
mi o bucată de memorie?

275
00:13:02,470 --> 00:13:03,580
Eu pot folosi malloc.

276
00:13:03,580 --> 00:13:06,710
Și pot să spun orice număr de
bytes vreau înapoi pentru aceste Nths.

277
00:13:06,710 --> 00:13:10,910
Și tot ce am pentru a stoca în numerele
variabilă aici în interiorul acestui struct

278
00:13:10,910 --> 00:13:13,480
ar trebui să fie ce?

279
00:13:13,480 --> 00:13:18,440
Ce de fapt, merge în
Numerele în acest scenariu?

280
00:13:18,440 --> 00:13:21,300
Da, un pointer la primul
octet de care bucată de memorie,

281
00:13:21,300 --> 00:13:24,940
sau mai precis, adresa
de prima dintre aceste bytes.

282
00:13:24,940 --> 00:13:27,300
Nu contează dacă e un
byte sau un miliard de bytes,

283
00:13:27,300 --> 00:13:28,890
Am nevoie doar să aibă grijă de prima.

284
00:13:28,890 --> 00:13:31,530
Pentru că ceea ce garanții și malloc
garanții mele sistem de operare,

285
00:13:31,530 --> 00:13:34,170
este că bucată de memorie I
obține, va fi contigue.

286
00:13:34,170 --> 00:13:35,378
Nu va fi lacune.

287
00:13:35,378 --> 00:13:38,576
Deci, dacă am cerut pentru 50
bytes sau 1000 bytes,

288
00:13:38,576 --> 00:13:40,450
ei toți vor fi
Înapoi la spate în spate.

289
00:13:40,450 --> 00:13:44,500
Și atât timp cât îmi amintesc cât de mare, cât de
de mult am cerut, tot ce trebuie să știu

290
00:13:44,500 --> 00:13:46,230
este primul astfel de adresă.

291
00:13:46,230 --> 00:13:48,660
>> Deci, acum avem capacitatea de cod.

292
00:13:48,660 --> 00:13:51,280
Deși, o să ne ia
mai mult timp pentru a scrie asta,

293
00:13:51,280 --> 00:13:55,900
am putea realoca acum că memoria de
doar stocarea o adresă diferită acolo

294
00:13:55,900 --> 00:13:59,060
dacă ne dorim o mai mare sau chiar
o bucată mică de memorie.

295
00:13:59,060 --> 00:14:00,170
Deci, aici la un off comerț.

296
00:14:00,170 --> 00:14:01,360
Acum ajungem dinamism.

297
00:14:01,360 --> 00:14:03,350
Avem încă
contiguousness am pretind.

298
00:14:03,350 --> 00:14:05,881
Deoarece malloc ne va da
o bucată contiguu de memorie.

299
00:14:05,881 --> 00:14:08,630
Dar acest lucru va fi o durere în
gât pentru noi, programator,

300
00:14:08,630 --> 00:14:09,770
pentru a coda de fapt sus.

301
00:14:09,770 --> 00:14:10,730
E doar mai mult de lucru.

302
00:14:10,730 --> 00:14:13,930
Avem nevoie de cod asemanator cu ceea ce am fost
trage în urmă doar un moment.

303
00:14:13,930 --> 00:14:16,120
Foarte greu de realizat, dar se adaugă complexitate.

304
00:14:16,120 --> 00:14:19,520
Și astfel timp dezvoltator, programator
Acum este încă o altă resursă

305
00:14:19,520 --> 00:14:22,520
că s-ar putea nevoie pentru a petrece
ceva timp pentru a obține noi caracteristici.

306
00:14:22,520 --> 00:14:24,020
Și apoi, desigur, există o listă de așteptare.

307
00:14:24,020 --> 00:14:26,227
Nu vom intra în acest
o în detaliu.

308
00:14:26,227 --> 00:14:27,560
Dar e foarte similare în spirit.

309
00:14:27,560 --> 00:14:31,220
Aș putea pune în aplicare o coadă, și
operațiunile sale corespunzătoare,

310
00:14:31,220 --> 00:14:35,660
Puneți în coadă sau dequeue, cum ar fi adăugați sau eliminați,
e doar un mod de a spune crescator ea,

311
00:14:35,660 --> 00:14:38,100
Puneți în coadă sau dequeue, după cum urmează.

312
00:14:38,100 --> 00:14:41,170
M-am pot da doar un struct
are din nou un număr de serie,

313
00:14:41,170 --> 00:14:44,000
are din nou o dimensiune,
dar de ce acum am nevoie de

314
00:14:44,000 --> 00:14:46,940
pentru a urmări partea din față a unei cozi?

315
00:14:46,940 --> 00:14:50,630
N-am nevoie sa stiu
partea din față a stack meu.

316
00:14:50,630 --> 00:14:53,570
Ei bine, dacă am din nou pentru o
queue-- hai doar greu

317
00:14:53,570 --> 00:14:57,870
cod-o ca având ca cinci
întregi de aici potențial.

318
00:14:57,870 --> 00:15:00,940
Deci, aceasta este zero, unu, doi, trei, patru.

319
00:15:00,940 --> 00:15:03,430
Acest lucru va fi
numitele numere din nou.

320
00:15:03,430 --> 00:15:06,940
Iar acest lucru va fi numit dimensiune.

321
00:15:06,940 --> 00:15:10,056
>> De ce este nu suficient
de a avea doar dimensiuni?

322
00:15:10,056 --> 00:15:11,680
Ei bine, hai să împinge acele numere aceleași pe.

323
00:15:11,680 --> 00:15:14,220
Așa că am pushed-- I enqueued, sau împins.

324
00:15:14,220 --> 00:15:20,150
Acum voi Puneți în coadă 50, și apoi
51, și apoi 61, iar dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Așa că e Puneți în coadă.

326
00:15:21,070 --> 00:15:23,176
Am enqueued 50, apoi 51, apoi 61.

327
00:15:23,176 --> 00:15:25,050
Și care arată identic
Stivă până acum,

328
00:15:25,050 --> 00:15:27,190
cu excepția am nevoie pentru a face o schimbare.

329
00:15:27,190 --> 00:15:33,680
Am nevoie pentru a actualiza această dimensiune, așa că mă duc
de la zero la unu la două-trei acum.

330
00:15:33,680 --> 00:15:35,760
Cum pot dequeue?

331
00:15:35,760 --> 00:15:36,890
Ce se întâmplă cu dequeue?

332
00:15:36,890 --> 00:15:41,950
Cine ar trebui să vină de pe această listă în primul rând
dacă este linia de la Apple Store?

333
00:15:41,950 --> 00:15:42,780
Deci 50.

334
00:15:42,780 --> 00:15:44,700
Deci e un fel de complicat de aceasta data.

335
00:15:44,700 --> 00:15:47,880
Întrucât ultima dată când a fost super
ușor de a face doar dimensiunea minus unu,

336
00:15:47,880 --> 00:15:51,440
Ajung la sfârșitul matrice mea în mod eficient
în cazul în care numerele sunt, se elimină 61.

337
00:15:51,440 --> 00:15:52,920
Dar eu nu vreau să eliminați 61.

338
00:15:52,920 --> 00:15:55,030
Vreau sa iau 50, care a
a fost acolo la 05:00

339
00:15:55,030 --> 00:15:56,790
pentru a alinia pentru
noul iPhone sau fleacuri.

340
00:15:56,790 --> 00:16:01,200
Și așa mai departe pentru a scăpa de 50, am
nu se poate face doar asta, nu?

341
00:16:01,200 --> 00:16:02,547
Pot trece pe 50.

342
00:16:02,547 --> 00:16:04,380
Dar ne-am am spus
nu trebuie să fie atât de anal

343
00:16:04,380 --> 00:16:06,330
ca să zero afară sau ascunde datele.

344
00:16:06,330 --> 00:16:08,090
Putem uita doar unde este.

345
00:16:08,090 --> 00:16:12,330
>> Dar dacă aș schimba mărimea mea acum la
doi, este această informație suficientă

346
00:16:12,330 --> 00:16:15,711
să știe ce se întâmplă în coadă meu?

347
00:16:15,711 --> 00:16:16,680
Nu chiar.

348
00:16:16,680 --> 00:16:19,830
Cum ar fi dimensiunea mea este de două, dar
în cazul în care începe coada,

349
00:16:19,830 --> 00:16:22,980
mai ales daca mai am
aceste numere aceleași în memorie.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Așa că am nevoie să-și amintească
acum în cazul în care fata este.

352
00:16:27,090 --> 00:16:29,630
Și așa cum am propus la
acolo, vom avea doar numit

353
00:16:29,630 --> 00:16:33,729
Față Nth, a cărui inițială
Valoarea ar fi fost ce?

354
00:16:33,729 --> 00:16:35,270
Zero, doar începutul listei.

355
00:16:35,270 --> 00:16:40,876
Dar acum, în plus față de decrementare
dimensiunea, am incrementa doar partea din față.

356
00:16:40,876 --> 00:16:42,000
Acum, aici e altă problemă.

357
00:16:42,000 --> 00:16:43,030
Deci, odată ce am continua.

358
00:16:43,030 --> 00:16:47,520
Să presupunem acesta este numărul de
ca 121, 124, și apoi, la naiba,

359
00:16:47,520 --> 00:16:48,610
Sunt din spațiu.

360
00:16:48,610 --> 00:16:50,390
Dar stai un minut, nu sunt.

361
00:16:50,390 --> 00:16:55,630
Deci, în acest moment, în poveste,
presupunem că mărimea este unu, doi,

362
00:16:55,630 --> 00:17:00,370
trei, patru, astfel încât presupunem că
Dimensiunea este de patru, în față este unul,

363
00:17:00,370 --> 00:17:01,621
așa 51 este situat în față.

364
00:17:01,621 --> 00:17:04,329
Vreau să pun un alt număr aici,
dar, la naiba, eu sunt din spațiu.

365
00:17:04,329 --> 00:17:06,710
Dar eu nu sunt foarte, nu?

366
00:17:06,710 --> 00:17:11,192
În cazul în care aș putea pune unele
valoare suplimentară, cum ar fi 171?

367
00:17:11,192 --> 00:17:13,400
Da, aș putea fel doar de
du-te înapoi acolo, nu?

368
00:17:13,400 --> 00:17:18,161
Și apoi tăiați 50, sau
doar suprascrie cu 171.

369
00:17:18,161 --> 00:17:20,410
Și dacă vă întrebați de ce
numerele noastre a primit atât de aleatoriu,

370
00:17:20,410 --> 00:17:24,150
acestea sunt luate în mod obișnuit de calculator
Cursuri de stiinta de la Harvard după CS50.

371
00:17:24,150 --> 00:17:27,510
Dar asta a fost o optimizare bun,
pentru că acum nu mă pierde spațiu.

372
00:17:27,510 --> 00:17:30,750
Eu încă mai trebuie să vă amintiți
cât de mare acest lucru este totală.

373
00:17:30,750 --> 00:17:31,500
E cinci totală.

374
00:17:31,500 --> 00:17:33,375
Pentru ca nu vreau
începe suprascrierea 51.

375
00:17:33,375 --> 00:17:36,260
Așa că acum eu sunt încă de spațiu,
astfel încât aceeași problemă ca și înainte.

376
00:17:36,260 --> 00:17:39,140
Dar puteți vedea cum acum
în codul dvs., probabil

377
00:17:39,140 --> 00:17:41,910
Trebuie să scrie un pic mai mult
complexitate pentru a face să se întâmple asta.

378
00:17:41,910 --> 00:17:44,510
Și, de fapt, ceea ce operatorul
în C, probabil, permite

379
00:17:44,510 --> 00:17:48,110
faci magic acest circularitatea?

380
00:17:48,110 --> 00:17:50,160
Da operatorul modulo,
semnul sută.

381
00:17:50,160 --> 00:17:53,160
Deci, ce fel de misto despre o coadă,
chiar dacă păstrăm tablouri de desen

382
00:17:53,160 --> 00:17:56,520
ca aceste linii drepte, cum ar fi, dacă ai
un fel de despre această curbare ca

383
00:17:56,520 --> 00:18:00,341
în jurul ca un cerc, apoi doar
intuitiv un fel de lucrări mental

384
00:18:00,341 --> 00:18:01,590
Cred că un pic mai curat.

385
00:18:01,590 --> 00:18:05,190
Tu ar trebui să pună în aplicare în continuare
care model mental în codul.

386
00:18:05,190 --> 00:18:07,550
Deci, nu așa de greu,
în cele din urmă, să pună în aplicare,

387
00:18:07,550 --> 00:18:12,430
dar noi încă pierde size-- Mai degrabă,
capacitatea de a redimensiona, dacă nu vom face acest lucru.

388
00:18:12,430 --> 00:18:15,310
>> Trebuie să scăpăm de matrice, ne
înlocuiți-l cu un singur indicator,

389
00:18:15,310 --> 00:18:20,010
și apoi undeva în codul meu am
un apel ce funcționează pentru a crea de fapt

390
00:18:20,010 --> 00:18:23,720
matrice numita numere?

391
00:18:23,720 --> 00:18:26,190
Malloc, sau unele similare
funcția, exact.

392
00:18:26,190 --> 00:18:30,481
Orice întrebări cu privire la stive sau cozi.

393
00:18:30,481 --> 00:18:30,980
Da?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Buna intrebare.

396
00:18:34,240 --> 00:18:35,830
Ce modulo ai folosi aici.

397
00:18:35,830 --> 00:18:38,520
Deci, în general, atunci când se utilizează
mod, v-ar face

398
00:18:38,520 --> 00:18:40,620
cu dimensiunea de
structură de date întreg.

399
00:18:40,620 --> 00:18:44,120
Deci, ceva de genul cinci sau de capacitate, în cazul în care
este constant, este, probabil, implicat.

400
00:18:44,120 --> 00:18:47,100
Dar a face doar modulo cinci
Probabil nu este suficientă,

401
00:18:47,100 --> 00:18:51,380
pentru că avem nevoie să știm facem
înfășurați în jurul valorii de aici sau aici sau aici.

402
00:18:51,380 --> 00:18:54,160
Deci tu ești probabil, de asemenea
O să vrea să implice

403
00:18:54,160 --> 00:18:57,220
mărimea lucru, sau
variabila față, de asemenea.

404
00:18:57,220 --> 00:19:00,140
Deci e doar acest relativ
expresie aritmetică simplă,

405
00:19:00,140 --> 00:19:02,000
dar modulo ar fi ingredientul cheie.

406
00:19:02,000 --> 00:19:03,330
>> Deci, film de scurt metraj, dacă vrei.

407
00:19:03,330 --> 00:19:05,780
O animație care unele
Cei de la o altă universitate

408
00:19:05,780 --> 00:19:08,060
pune împreună că am
adaptate pentru această discuție.

409
00:19:08,060 --> 00:19:12,630
Aceasta implică învățarea Jack
fapte despre cozile și statistici.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: După ce la un moment dat,
era un tip pe nume Jack.

412
00:19:21,890 --> 00:19:25,330
Cand a venit la a face prieteni,
Jack nu a avut un talent.

413
00:19:25,330 --> 00:19:28,220
Deci, Jack a mers să vorbească la
mai tip popular știa.

414
00:19:28,220 --> 00:19:30,920
El sa dus la Lou și a întrebat, ce să fac?

415
00:19:30,920 --> 00:19:33,400
Lou a văzut că prietenul său
a fost foarte întristat.

416
00:19:33,400 --> 00:19:36,050
Ei bine, el a început, doar
uite cum te îmbraci.

417
00:19:36,050 --> 00:19:38,680
Nu ai haine
cu un aspect diferit?

418
00:19:38,680 --> 00:19:39,660
Da, a spus Jack.

419
00:19:39,660 --> 00:19:40,840
Eu sigur fac.

420
00:19:40,840 --> 00:19:43,320
Vino la casa mea și
O să le arăt.

421
00:19:43,320 --> 00:19:44,550
Așa că au plecat la Jack.

422
00:19:44,550 --> 00:19:47,520
Și Jack a arătat Lou caseta
unde a păstrat toate tricouri lui,

423
00:19:47,520 --> 00:19:49,260
și pantalonii lui, și șosete lui.

424
00:19:49,260 --> 00:19:52,290
Lou a spus, văd ai
toate hainele într-o grămadă.

425
00:19:52,290 --> 00:19:54,870
De ce nu te purta unele
altele din cand in cand?

426
00:19:54,870 --> 00:19:58,020
>> Jack a spus, bine, atunci când am
Scoateți îmbrăcămintea și șosete,

427
00:19:58,020 --> 00:20:00,780
Le-am spăla și a pus
le departe în caseta.

428
00:20:00,780 --> 00:20:03,210
Apoi vine următorul
dimineața, și până am hop.

429
00:20:03,210 --> 00:20:06,380
Mă duc la cutia și a obține
hainele mele pe partea de sus.

430
00:20:06,380 --> 00:20:09,070
Lou realizat repede
problema cu Jack.

431
00:20:09,070 --> 00:20:12,080
El a ținut haine, CD-uri,
și cărți în stivă.

432
00:20:12,080 --> 00:20:14,420
Când a ajuns pentru
ceva de citit sau de a purta,

433
00:20:14,420 --> 00:20:17,100
el ar alege cartea de sus sau lenjerie.

434
00:20:17,100 --> 00:20:19,500
Apoi, când a fost făcut, el
l-ar pune imediat înapoi.

435
00:20:19,500 --> 00:20:21,970
Înapoi ar merge, pe partea de sus a stivei.

436
00:20:21,970 --> 00:20:24,460
Știu soluția,
a declarat un Loud triumfător.

437
00:20:24,460 --> 00:20:27,090
Aveți nevoie pentru a învăța să
a începe să utilizați o coadă.

438
00:20:27,090 --> 00:20:29,870
Lou luat hainele lui Jack și
le spânzurat în dulap.

439
00:20:29,870 --> 00:20:32,710
Și după ce a golit
caseta, el doar aruncat.

440
00:20:32,710 --> 00:20:36,500
>> Apoi a spus el, acum Jack, la sfârșitul
a doua zi, a pus hainele pe stânga

441
00:20:36,500 --> 00:20:37,990
atunci când le-a pus deoparte.

442
00:20:37,990 --> 00:20:41,300
Apoi mâine dimineață, atunci când
vezi soarele, pentru a primi hainele tale

443
00:20:41,300 --> 00:20:43,440
pe dreapta, de la capătul liniei.

444
00:20:43,440 --> 00:20:44,880
Nu vezi? a spus Lou.

445
00:20:44,880 --> 00:20:46,370
Acesta va fi atât de frumos.

446
00:20:46,370 --> 00:20:49,770
Vei purta tot o dată
înainte de a purta ceva de două ori.

447
00:20:49,770 --> 00:20:52,670
Și cu totul în cozi
în dulap și raft lui,

448
00:20:52,670 --> 00:20:55,160
Jack a început să se simtă
destul de sigur de el.

449
00:20:55,160 --> 00:20:59,720
Toate datorită Lou și
coada lui minunat.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Bine, e adorabil.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Deci, ceea ce a fost întâmplă cu adevărat
pe sub capota acum?

453
00:21:10,080 --> 00:21:12,370
Pe care o avem indicii,
pe care le avem malloc,

454
00:21:12,370 --> 00:21:15,680
că avem capacitatea de a crea
bucăți de memorie pentru noi înșine

455
00:21:15,680 --> 00:21:16,344
dinamic.

456
00:21:16,344 --> 00:21:18,510
Deci, aceasta este o imagine ne
zări doar de altă zi.

457
00:21:18,510 --> 00:21:21,180
Nu am locui într-adevăr
pe ea, dar această imagine

458
00:21:21,180 --> 00:21:24,180
a fost întâmplă sub
capota pentru săptămâna acum.

459
00:21:24,180 --> 00:21:27,050
Și astfel acest lucru reprezintă, doar
un dreptunghi pe care le-am elaborat,

460
00:21:27,050 --> 00:21:28,180
memoria computerului.

461
00:21:28,180 --> 00:21:31,850
Și poate computerul, sau CS50
ID, are o gigabyte de memorie RAM sau

462
00:21:31,850 --> 00:21:33,050
sau doi gigabytes sau patru.

463
00:21:33,050 --> 00:21:34,450
Nu contează.

464
00:21:34,450 --> 00:21:37,240
Sistemul de operare
Windows sau Mac OS sau Linux,

465
00:21:37,240 --> 00:21:41,120
permite, în esență, programul
să cred că are acces

466
00:21:41,120 --> 00:21:42,982
la totalitatea
memoria computerului,

467
00:21:42,982 --> 00:21:45,440
chiar dacă s-ar putea fi difuzate
mai multe programe în același timp.

468
00:21:45,440 --> 00:21:46,990
Deci, în realitate, că nu prea funcționează.

469
00:21:46,990 --> 00:21:49,448
Dar este un fel de o iluzie
dat toate programele.

470
00:21:49,448 --> 00:21:53,110
Deci, dacă ați avut două concerte de RAM, acest
este modul în care computerul ar putea crede ea.

471
00:21:53,110 --> 00:21:57,110
>> Acum coincidenta, unul dintre acestea
lucruri, unul dintre aceste segmente de memorie,

472
00:21:57,110 --> 00:21:58,350
se numește o stivă.

473
00:21:58,350 --> 00:22:01,680
Și într-adevăr orice moment
până acum în codul scris

474
00:22:01,680 --> 00:22:05,900
pe care le-au numit un
Funcția, de exemplu principal.

475
00:22:05,900 --> 00:22:08,410
Amintiți-vă că în orice moment Am
memoria calculatorului trase lui,

476
00:22:08,410 --> 00:22:10,640
Intotdeauna mi-am trage un fel de
o jumatate de dreptunghi aici

477
00:22:10,640 --> 00:22:12,520
și nu deranjez vorbesc
despre ce e mai sus.

478
00:22:12,520 --> 00:22:15,980
Pentru că atunci când principal este numit, eu pretind
că veți obține acest țeapă de memorie

479
00:22:15,980 --> 00:22:16,970
care merge aici.

480
00:22:16,970 --> 00:22:20,650
Și dacă principal numit în funcție
ca de swap, și de swap merge aici.

481
00:22:20,650 --> 00:22:23,720
Și se pare, că e
în cazul în care se încheie până.

482
00:22:23,720 --> 00:22:26,277
Pe ceva numit un teanc
în interiorul memoria computerului.

483
00:22:26,277 --> 00:22:28,360
Acum, la sfârșitul zilei,
aceasta este doar se adresează.

484
00:22:28,360 --> 00:22:30,680
E ca și cum octet de zero,
octet unul, octet 2 miliarde.

485
00:22:30,680 --> 00:22:33,130
Dar dacă te gândești la asta
ca acest obiect dreptunghiular,

486
00:22:33,130 --> 00:22:35,130
Tot ce facem în fiecare
timp ce numim o funcție este

487
00:22:35,130 --> 00:22:37,180
stratificarea o nouă felie de memorie.

488
00:22:37,180 --> 00:22:41,700
Ne dăm că funcția o felie
de memorie proprie pentru a lucra cu.

489
00:22:41,700 --> 00:22:44,490
>> Și amintesc acum că acest lucru este important.

490
00:22:44,490 --> 00:22:46,400
Pentru că dacă ne-am
ceva de genul de swap

491
00:22:46,400 --> 00:22:51,610
și două variabile locale ca A și B și
vom schimba aceste valori de la una și două

492
00:22:51,610 --> 00:22:55,130
la două și un, amintesc
că, atunci când se întoarce de swap,

493
00:22:55,130 --> 00:22:58,330
e ca și cum aceasta felie
de memorie este doar dus.

494
00:22:58,330 --> 00:23:00,080
În realitate, este încă
acolo forensically.

495
00:23:00,080 --> 00:23:01,940
Și ceva e încă de fapt acolo.

496
00:23:01,940 --> 00:23:05,410
Dar conceptual, este ca
deși este complet dispărut.

497
00:23:05,410 --> 00:23:10,910
Și așa principal nu cunosc nici a operei
care a fost făcut în această funcție de swap,

498
00:23:10,910 --> 00:23:14,890
cu excepția cazului în de fapt a trecut în cele
argumente de pointer sau referință.

499
00:23:14,890 --> 00:23:17,790
Acum, soluția fundamentală
pentru că problema cu schimb

500
00:23:17,790 --> 00:23:19,970
trece lucrurile în prin adresa.

501
00:23:19,970 --> 00:23:23,250
Dar se pare, de asemenea, ceea ce este
fost întâmplă de mai sus că o parte

502
00:23:23,250 --> 00:23:26,330
dreptunghiului tot acest timp este
dar nu e mai mult de memorie acolo.

503
00:23:26,330 --> 00:23:28,790
Iar atunci când dinamic
aloca memorie,

504
00:23:28,790 --> 00:23:32,020
fie că este vorba în interiorul getString, care
am făcut pentru tine în CS50

505
00:23:32,020 --> 00:23:34,710
bibliotecă, sau dacă voi
apel malloc și întrebați

506
00:23:34,710 --> 00:23:37,950
sistemul de operare pentru o bucată de
memorie, aceasta nu vine din stivă.

507
00:23:37,950 --> 00:23:40,960
Ea vine de la un alt loc
în memoria computerului

508
00:23:40,960 --> 00:23:42,220
că se numește grămadă.

509
00:23:42,220 --> 00:23:43,430
Și asta nu e diferit.

510
00:23:43,430 --> 00:23:44,285
E același RAM.

511
00:23:44,285 --> 00:23:45,160
Este aceeași memorie.

512
00:23:45,160 --> 00:23:49,080
E doar RAM care este de până
acolo în loc de aici.

513
00:23:49,080 --> 00:23:50,750
>> Și ce înseamnă asta?

514
00:23:50,750 --> 00:23:53,650
Ei bine, în cazul în care computerul are
o cantitate finită de memorie

515
00:23:53,650 --> 00:23:57,450
și stiva este în creștere în sus, astfel încât
de a vorbi, și grămada, conform

516
00:23:57,450 --> 00:23:59,349
la această săgeată, este în creștere în jos.

517
00:23:59,349 --> 00:24:01,140
Cu alte cuvinte, fiecare
timp te sun malloc,

518
00:24:01,140 --> 00:24:03,430
Ești dat o felie
de memorie de mai sus,

519
00:24:03,430 --> 00:24:06,630
atunci poate un pic mai mic, apoi un pic
mai mici, de fiecare dată când suni malloc,

520
00:24:06,630 --> 00:24:10,100
heap, e de utilizare,
este un fel de creștere,

521
00:24:10,100 --> 00:24:11,950
în creștere tot mai aproape de ce?

522
00:24:11,950 --> 00:24:13,382
Stiva.

523
00:24:13,382 --> 00:24:14,840
Deci, se pare ca acest lucru o idee bună?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Adică, în cazul în care nu este foarte clar
Ce altceva poți face dacă ai doar

526
00:24:22,140 --> 00:24:23,910
au o cantitate finită de memorie.

527
00:24:23,910 --> 00:24:25,200
Dar acest lucru este cu siguranță rău.

528
00:24:25,200 --> 00:24:27,920
Aceste două săgeți sunt pe o
Crash Course unul pentru altul.

529
00:24:27,920 --> 00:24:31,930
>> Și se pare că tipul rău, oameni care
sunt deosebit de bune, cu programare,

530
00:24:31,930 --> 00:24:36,140
și încercarea de a hack în computere,
poate exploata această realitate.

531
00:24:36,140 --> 00:24:38,290
De fapt, să luăm în considerare
un pic fragment.

532
00:24:38,290 --> 00:24:41,350
Astfel încât acesta este un exemplu puteți citi
despre mai în detaliu pe Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Vă vom indica la
Articolul dacă curios.

534
00:24:43,100 --> 00:24:45,650
Dar există un atac, în general,
cunoscut sub numele de buffer overflow care

535
00:24:45,650 --> 00:24:49,570
a existat atâta timp cât oamenii
au avut capacitatea de a manipula

536
00:24:49,570 --> 00:24:53,120
memoria calculatorului, în special în C.
Deci, acesta este un program foarte arbitrar,

537
00:24:53,120 --> 00:24:55,130
dar să-l citesc de jos în sus.

538
00:24:55,130 --> 00:24:57,650
Principal în stele argc char argv.

539
00:24:57,650 --> 00:24:59,830
Deci, este un program care ia
argumente în linia de comandă.

540
00:24:59,830 --> 00:25:03,620
Și tot principal se pare că este de apel
o funcție, o numesc F pentru simplitate.

541
00:25:03,620 --> 00:25:04,610
Și trece în ce?

542
00:25:04,610 --> 00:25:05,490
Argv de unul.

543
00:25:05,490 --> 00:25:09,320
Deci, trece in F indiferent
cuvântul este faptul că utilizatorul tastat

544
00:25:09,320 --> 00:25:11,500
la prompt după
Numele programului, la toate.

545
00:25:11,500 --> 00:25:15,730
Atât de mult ca Caesar sau Vigenere, care
s-ar putea aminti faci cu argv.

546
00:25:15,730 --> 00:25:16,680
>> Deci, ce este F?

547
00:25:16,680 --> 00:25:19,760
F ia într-un șir
ca argument unic,

548
00:25:19,760 --> 00:25:22,100
AKA o stea char, același
lucru, ca un șir.

549
00:25:22,100 --> 00:25:24,920
Și se numește în mod arbitrar
bar în acest exemplu.

550
00:25:24,920 --> 00:25:27,710
Și apoi char c 12,
doar în termeni de nespecialist,

551
00:25:27,710 --> 00:25:31,750
ceea ce este char c suport 12 face pentru noi?

552
00:25:31,750 --> 00:25:33,440
Ce se face?

553
00:25:33,440 --> 00:25:36,490
Alocarea de memorie, în special
12 bytes pentru 12 caractere.

554
00:25:36,490 --> 00:25:36,990
Exact.

555
00:25:36,990 --> 00:25:40,000
Și apoi ultima linie, se amestecă și
copie, nu ați văzut, probabil,.

556
00:25:40,000 --> 00:25:43,360
Aceasta este o copie șir
Funcția a cărui scop în viață

557
00:25:43,360 --> 00:25:48,160
este de a copia al doilea argument
în primul său argument,

558
00:25:48,160 --> 00:25:51,190
dar numai până la un
anumit număr de octeți.

559
00:25:51,190 --> 00:25:53,860
Deci al treilea argument spune,
cât de multe bytes ar trebui să vă copiați?

560
00:25:53,860 --> 00:25:56,720
Lungimea bar,
indiferent de utilizatorul tastat.

561
00:25:56,720 --> 00:25:59,320
Și conținutul
bar, că șir, sunt

562
00:25:59,320 --> 00:26:02,330
copiat în memoria arătat la la C.

563
00:26:02,330 --> 00:26:04,060
>> Deci, acest lucru pare un fel de stupid, și este.

564
00:26:04,060 --> 00:26:06,300
Este un exemplu contrived,
dar este reprezentant

565
00:26:06,300 --> 00:26:10,100
de o clasă de vectori de atac,
un mod de a ataca un program.

566
00:26:10,100 --> 00:26:15,050
Totul este în regulă și de bună dacă utilizatorul
Tipuri într-un cuvânt care este de 11 de caractere

567
00:26:15,050 --> 00:26:18,040
sau mai puține, plus backslash zero.

568
00:26:18,040 --> 00:26:22,830
Ce se întâmplă dacă de utilizator tipuri în mai mult de
11 sau 12 sau 20 sau 50 de caractere?

569
00:26:22,830 --> 00:26:25,090
Ce e acest program de gând să faci?

570
00:26:25,090 --> 00:26:29,360
Vina potențial seg. Merge
pentru a copia orbește tot în bar până

571
00:26:29,360 --> 00:26:31,750
a lungimii sale, care este
literalmente totul în bar,

572
00:26:31,750 --> 00:26:36,307
în adresa a subliniat, la C. Dar C
a dat preventiv doar ca 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Dar nu e nici o verificare suplimentară.

574
00:26:37,640 --> 00:26:38,700
Nu e nici cazul în care condițiile.

575
00:26:38,700 --> 00:26:40,580
Nu e nici o eroare verifica aici.

576
00:26:40,580 --> 00:26:43,270
>> Și așa mai departe ceea ce acest program este
de gând să faci este doar orbește

577
00:26:43,270 --> 00:26:45,750
copia un lucru la altul.

578
00:26:45,750 --> 00:26:47,880
Și așa că, dacă vom trage această
ca o imagine, aici e

579
00:26:47,880 --> 00:26:49,860
doar o așchie de spațiul de memorie.

580
00:26:49,860 --> 00:26:53,470
Deci observați în partea de jos, am
au bara variabilă locale.

581
00:26:53,470 --> 00:26:57,330
Astfel încât indicatorul care va store--
mai degrabă că argument local, care este

582
00:26:57,330 --> 00:26:58,672
merge pentru a stoca bara șir.

583
00:26:58,672 --> 00:27:00,380
Și apoi observați doar
de mai sus, într-o stivă,

584
00:27:00,380 --> 00:27:02,505
pentru că de fiecare dată când cere
pentru memorie pe stivă,

585
00:27:02,505 --> 00:27:04,310
merge un pic
deasupra ei pictural,

586
00:27:04,310 --> 00:27:06,270
Notă că avem 12 bytes acolo.

587
00:27:06,270 --> 00:27:10,690
Cel din stânga sus este C suport zero și
cel din dreapta jos este C suport 11.

588
00:27:10,690 --> 00:27:12,870
Asta e doar modul în care calculatoarele
gând să-l expune.

589
00:27:12,870 --> 00:27:18,300
Deci doar intuitiv, dacă bar are mai
mult de 12 de caractere în total, inclusiv

590
00:27:18,300 --> 00:27:25,790
backslash la zero, în cazul în care este
12 sau suportul C 12 merge?

591
00:27:25,790 --> 00:27:28,440
Sau, mai degrabă în cazul în care este 12
caracter sau caracterul 13-lea,

592
00:27:28,440 --> 00:27:30,900
caracterul suta merge
să se încheie până în imagine?

593
00:27:30,900 --> 00:27:33,400
Peste sau sub?

594
00:27:33,400 --> 00:27:36,300
>> Drept, deoarece, chiar dacă
stiva în sine crește în sus,

595
00:27:36,300 --> 00:27:39,590
odată ce ați pus lucruri în
ea, din motive de design,

596
00:27:39,590 --> 00:27:41,294
pune memoria de sus în jos.

597
00:27:41,294 --> 00:27:44,460
Deci, dacă ai mai mult de 12 bytes,
ai de gând să înceapă să suprascrie bar.

598
00:27:44,460 --> 00:27:47,280
Acum, că e un bug, dar e
nu într-adevăr o afacere mare.

599
00:27:47,280 --> 00:27:51,130
Dar este o afacere mare, pentru că există
mai multe lucruri se întâmplă în memorie.

600
00:27:51,130 --> 00:27:53,074
Deci, iată cum am putea
pune salut, să fie clar.

601
00:27:53,074 --> 00:27:54,490
Dacă am scris în salut la prompt.

602
00:27:54,490 --> 00:27:59,330
Backslash zero, H-E-L-L-O, se încheie în termen de
aceste 12 bytes, și suntem foarte în siguranță.

603
00:27:59,330 --> 00:28:00,330
Totul este bine.

604
00:28:00,330 --> 00:28:03,020
Dar dacă am ceva de tip
mai mult, cu potential de e

605
00:28:03,020 --> 00:28:05,860
O să se strecoare în bara de spațiu.

606
00:28:05,860 --> 00:28:08,405
Dar, mai rău încă, se pare
în tot acest timp,

607
00:28:08,405 --> 00:28:11,530
chiar dacă nu am vorbit despre
ea, stiva este folosit pentru alte lucruri.

608
00:28:11,530 --> 00:28:13,560
Nu este vorba doar variabile locale.

609
00:28:13,560 --> 00:28:15,100
>> C este un limbaj de nivel foarte scăzut.

610
00:28:15,100 --> 00:28:17,810
Și ea un fel de secret
folosește stiva, de asemenea,

611
00:28:17,810 --> 00:28:21,260
să-și amintească atunci când un
Funcția este numit, ceea ce

612
00:28:21,260 --> 00:28:26,040
adresa este a funcției anterioare,
astfel încât să poată sări înapoi la această funcție.

613
00:28:26,040 --> 00:28:29,980
Deci, atunci când solicită principale swap, printre
lucrurile împins pe stiva

614
00:28:29,980 --> 00:28:34,380
nu sunt swap-uri doar variabile locale,
sau argumentele sale, de asemenea, împins în secret

615
00:28:34,380 --> 00:28:37,510
pe stiva așa cum este reprezentat
de felie roșu aici,

616
00:28:37,510 --> 00:28:40,520
este adresa de principal punct de vedere fizic
în memoria computerului,

617
00:28:40,520 --> 00:28:44,180
astfel încât atunci când se face schimb, calculatorul
știe că trebuie să ne întoarcem la principal

618
00:28:44,180 --> 00:28:46,760
și să termin de executare funcția principală.

619
00:28:46,760 --> 00:28:51,960
Deci acest lucru este periculos acum, deoarece în cazul în care
utilizator tipuri în bine mai mult de salut,

620
00:28:51,960 --> 00:28:57,030
astfel încât de intrare utilizatorului clobbers
sau suprascrie această secțiune roșu,

621
00:28:57,030 --> 00:28:59,820
logic cazul în care computerul este
doar de gând să-și asume orbește

622
00:28:59,820 --> 00:29:03,830
că octeții din care felie roșu sunt
adresa la care aceasta ar trebui să se întoarcă,

623
00:29:03,830 --> 00:29:09,020
Ce se întâmplă dacă un adversar este destul de inteligent sau
suficient de norocos pentru a pune o secvență de octeți

624
00:29:09,020 --> 00:29:13,450
acolo care arata ca o adresă,
dar este adresa de cod

625
00:29:13,450 --> 00:29:18,730
că el sau ea vrea computerul
să execute în loc de principal?

626
00:29:18,730 --> 00:29:21,670
>> Cu alte cuvinte, dacă Ce
utilizator este tastarea la prompt,

627
00:29:21,670 --> 00:29:23,850
nu este doar ceva
ca inofensive salut,

628
00:29:23,850 --> 00:29:28,210
dar este de fapt un cod care este echivalent
pentru a șterge toate fișierele acestui utilizator?

629
00:29:28,210 --> 00:29:30,060
Sau e-mail parola pentru mine?

630
00:29:30,060 --> 00:29:31,940
Sau de a începe de logare lor
intrarile de la tastatura, nu?

631
00:29:31,940 --> 00:29:34,920
Există o cale, să prevadă astăzi,
că acestea ar putea tip în nu doar salut

632
00:29:34,920 --> 00:29:36,711
lumea sau numele lor,
acestea ar putea, în esență,

633
00:29:36,711 --> 00:29:39,570
trece în cod, zerouri și
cele, care calculatorul

634
00:29:39,570 --> 00:29:43,450
greșeli atât pentru cod și o adresă.

635
00:29:43,450 --> 00:29:48,950
Deci, deși oarecum abstract, în cazul în care
utilizator tipuri în codul contradictorie suficient

636
00:29:48,950 --> 00:29:52,330
că vom generaliza aici ca
A. A este atac sau adversari.

637
00:29:52,330 --> 00:29:53,140
Lucrurile așa de rău doar.

638
00:29:53,140 --> 00:29:55,306
Nu ne pasă de
numere sau zerouri sau cele

639
00:29:55,306 --> 00:29:59,470
astăzi, astfel să ajungi în
suprascrierea secțiunea roșu,

640
00:29:59,470 --> 00:30:01,580
observați că secvența de octeți.

641
00:30:01,580 --> 00:30:05,020
O 835 C la zero la opt la zero.

642
00:30:05,020 --> 00:30:08,960
Și acum, ca articol Wikipedia aici
a propus, dacă acum, de fapt începe

643
00:30:08,960 --> 00:30:12,460
etichetarea bytes din a computerului
memorie, ceea ce articol Wikipedia este

644
00:30:12,460 --> 00:30:19,060
propunerea este că, ceea ce în cazul în care adresa
de care byte stânga sus este de 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Cu alte cuvinte, în cazul în care personajul negativ este
destul de inteligent cu codul său

646
00:30:22,200 --> 00:30:26,650
pentru a pune de fapt, un număr de aici care
corespunde cu adresa codului

647
00:30:26,650 --> 00:30:29,180
el sau ea injectat
în computer, ai

648
00:30:29,180 --> 00:30:31,050
poate pacali calculatorul
în a face ceva.

649
00:30:31,050 --> 00:30:34,140
Scoaterea fișiere, email-uri
lucruri, sniffing trafic,

650
00:30:34,140 --> 00:30:36,710
literalmente ceva ar putea fi
injectat în calculator.

651
00:30:36,710 --> 00:30:39,220
Și așa un buffer overflow
atac în centrul său

652
00:30:39,220 --> 00:30:43,530
este doar un prost, prost
major al unui tablou care

653
00:30:43,530 --> 00:30:45,840
nu avea limitele sale verificate.

654
00:30:45,840 --> 00:30:48,850
Și aceasta este ceea ce este super periculos
și în același timp foarte puternic

655
00:30:48,850 --> 00:30:52,560
în C este că avem într-adevăr
accesul la oriunde în memorie.

656
00:30:52,560 --> 00:30:55,320
Depinde de noi, programatori,
care scrie codul original

657
00:30:55,320 --> 00:30:59,330
pentru a verifica durata darn orice
matrice care suntem manipularea.

658
00:30:59,330 --> 00:31:00,750
Deci, să fie clar, care e fix?

659
00:31:00,750 --> 00:31:03,190
Dacă ne reveniți la acest
cod, eu nu ar trebui doar

660
00:31:03,190 --> 00:31:08,000
schimba lungimea bar, ceea ce
altceva ar trebui să mă verificarea?

661
00:31:08,000 --> 00:31:10,620
Ce altceva ar trebui să fac pentru a fi
preveni acest atac în întregime?

662
00:31:10,620 --> 00:31:14,110
Nu vreau să spun doar orbește
că ar trebui să copiați cât mai multe bytes

663
00:31:14,110 --> 00:31:16,140
cum este lungimea de bare.

664
00:31:16,140 --> 00:31:18,910
Vreau să spun, copie ca
multe bytes ca sunt in bar

665
00:31:18,910 --> 00:31:24,090
până la alocat
memorie, sau 12 maxim.

666
00:31:24,090 --> 00:31:27,450
Așa că am nevoie de un fel de stare, dacă
care face verifica durata de bar,

667
00:31:27,450 --> 00:31:32,800
dar dacă depășește 12, am cod doar greu
12 ca distanța maximă posibilă.

668
00:31:32,800 --> 00:31:35,910
În caz contrar, așa-numitul tamponul
atac preaplin se poate întâmpla.

669
00:31:35,910 --> 00:31:38,451
În partea de jos a acestor diapozitive,
Daca esti curios pentru a citi mai mult

670
00:31:38,451 --> 00:31:41,200
este articolul original real
dacă doriți să aruncăm o privire.

671
00:31:41,200 --> 00:31:44,550
>> Dar acum, între prețurile
plătit aici a fost ineficiențe.

672
00:31:44,550 --> 00:31:46,680
Astfel că a fost o rapid
nivel scăzut privire la ceea ce

673
00:31:46,680 --> 00:31:49,709
Probleme pot apărea acum că ne
să aibă acces la memoria calculatorului.

674
00:31:49,709 --> 00:31:51,750
Dar am o altă problemă
deja dat pe luni

675
00:31:51,750 --> 00:31:53,800
a fost doar ineficiența
de o listă de legate.

676
00:31:53,800 --> 00:31:56,019
Ne-am întors în timp liniar.

677
00:31:56,019 --> 00:31:57,560
Noi nu mai avem o gamă contiguă.

678
00:31:57,560 --> 00:31:58,980
Nu avem acces aleator.

679
00:31:58,980 --> 00:32:00,710
Nu putem folosi notația suport pătrat.

680
00:32:00,710 --> 00:32:04,590
Noi pur și simplu trebuie să utilizeze o buclă în timp ce
ca cea pe care am scris acum un moment.

681
00:32:04,590 --> 00:32:09,740
Dar, luni, ne-am afirmat că putem
strecoare înapoi în domeniul eficienței

682
00:32:09,740 --> 00:32:13,040
realizarea ceva care este
logaritmică poate, sau cel mai bun încă,

683
00:32:13,040 --> 00:32:16,120
poate chiar ceva care este
așa-numita constantă de timp.

684
00:32:16,120 --> 00:32:19,840
Deci, cum putem face acest lucru prin utilizarea acestor noi
instrumente, aceste adrese, aceste indicii,

685
00:32:19,840 --> 00:32:22,210
și filetare lucrurile noastre proprii?

686
00:32:22,210 --> 00:32:23,960
Ei bine, să presupunem că
aici, acestea sunt o grămadă

687
00:32:23,960 --> 00:32:27,170
de numere pe care le doresc pentru a stoca într-un
structură de date și de căutare eficient.

688
00:32:27,170 --> 00:32:30,960
Putem derula absolut la săptămână
două, arunca aceste într-o matrice,

689
00:32:30,960 --> 00:32:33,150
și le căuta folosind căutare binară.

690
00:32:33,150 --> 00:32:34,040
Diviza și cuceri.

691
00:32:34,040 --> 00:32:37,720
Și, de fapt ai scris
căutare binară în PSET3,

692
00:32:37,720 --> 00:32:40,100
în cazul în care a implementat programul găsi.

693
00:32:40,100 --> 00:32:40,890
Dar știi ce.

694
00:32:40,890 --> 00:32:45,060
Există un fel de mai
mod inteligent de a face acest lucru.

695
00:32:45,060 --> 00:32:47,390
E un pic mai mult
sofisticat și, probabil,

696
00:32:47,390 --> 00:32:50,830
ne permite să vedem de ce binar
căutare este atât de mult mai repede.

697
00:32:50,830 --> 00:32:52,980
În primul rând, haideți să introducă
noțiunea de copac.

698
00:32:52,980 --> 00:32:54,730
Care chiar dacă în
copaci realitate un fel de

699
00:32:54,730 --> 00:32:57,730
cresc ca aceasta, în lumea de calculator
știință au un fel de jos cresc

700
00:32:57,730 --> 00:33:00,830
ca un arbore genealogic, în cazul în care aveți
bunicii tăi sau bunicii mari

701
00:33:00,830 --> 00:33:04,580
sau fleacuri în partea de sus, patriarhul și
matriarhatului familiei, cel doar

702
00:33:04,580 --> 00:33:07,930
așa-numita rădăcină, nod, mai jos
care sunt copiii ei,

703
00:33:07,930 --> 00:33:11,442
sub care sunt copiii săi, sau
descendenții săi în general.

704
00:33:11,442 --> 00:33:13,400
Și oricine agățat
partea de jos a familiei

705
00:33:13,400 --> 00:33:16,070
copac, pe lângă faptul că
cel mai tanar din familie,

706
00:33:16,070 --> 00:33:19,520
de asemenea, doar poate fi generic
numit frunzele pomului.

707
00:33:19,520 --> 00:33:21,800
>> Deci, aceasta este doar o adunatura
de cuvinte și definiții

708
00:33:21,800 --> 00:33:25,790
pentru ceva numit un copac în calculator
știință, la fel ca un arbore genealogic.

709
00:33:25,790 --> 00:33:28,770
Dar nu e încarnări crescator
de arbori, dintre care unul

710
00:33:28,770 --> 00:33:30,780
este numit un arbore binar de căutare.

711
00:33:30,780 --> 00:33:34,380
Și vă puteți fel de tease
în afară ceea ce face acest lucru.

712
00:33:34,380 --> 00:33:37,180
Ei bine, e binar in ce sens?

713
00:33:37,180 --> 00:33:41,455
În cazul în care nu provin de la binar aici?

714
00:33:41,455 --> 00:33:41,955
Ne pare rău?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Nu este atât de mult un fie sau.

717
00:33:47,210 --> 00:33:52,000
Este mai mult decât fiecare dintre nodurile are nici
mai mult de doi copii, așa cum vom vedea aici.

718
00:33:52,000 --> 00:33:54,990
În general, un tree-- și
părinții și bunicii voștri

719
00:33:54,990 --> 00:33:57,640
poate avea cât mai multe copii sau
nepoții ca doresc de fapt,

720
00:33:57,640 --> 00:34:00,820
și așa, de exemplu, acolo avem trei
copii la nodul dreapta,

721
00:34:00,820 --> 00:34:05,480
dar într-un arbore binar, un nod are
Zero, una, sau doi copii. maxim

722
00:34:05,480 --> 00:34:08,496
Și că este o proprietate frumos,
pentru că dacă este limitat de doi,

723
00:34:08,496 --> 00:34:10,620
vom fi în măsură să
obține o bază de jurnal pic doi

724
00:34:10,620 --> 00:34:11,975
acțiune se întâmplă aici în cele din urmă.

725
00:34:11,975 --> 00:34:13,350
Deci, avem ceva logaritmică.

726
00:34:13,350 --> 00:34:14,558
Dar mai mult pe faptul că într-un moment.

727
00:34:14,558 --> 00:34:19,810
Copac de căutare înseamnă că numerele sunt
dispuse astfel încât copilul stânga lui

728
00:34:19,810 --> 00:34:22,429
Valoarea este mai mare decât rădăcina.

729
00:34:22,429 --> 00:34:26,010
Și copilul său chiar este
mai mare decât rădăcina.

730
00:34:26,010 --> 00:34:29,290
Cu alte cuvinte, dacă lua oricare dintre
noduri, cercurile în această imagine,

731
00:34:29,290 --> 00:34:31,840
și se uită la stânga sa
copil și copilul ei bine,

732
00:34:31,840 --> 00:34:34,739
primul trebuie să fie mai mică de,
A doua ar trebui să fie mai mare decât.

733
00:34:34,739 --> 00:34:36,159
Deci, bun-simț verifica 55.

734
00:34:36,159 --> 00:34:37,780
E plecat copil este de 33.

735
00:34:37,780 --> 00:34:38,620
E mai puțin de.

736
00:34:38,620 --> 00:34:40,929
55, dreptul său copil este de 77.

737
00:34:40,929 --> 00:34:41,783
E mai mare decât.

738
00:34:41,783 --> 00:34:43,199
Și că este o definiție recursivă.

739
00:34:43,199 --> 00:34:46,480
Am putea verifica fiecare dintre aceste
noduri și același model va organiza.

740
00:34:46,480 --> 00:34:49,389
>> Deci, ce e frumos într-o
arbore binar de căutare, este

741
00:34:49,389 --> 00:34:52,204
că unul, putem pune în aplicare
cu o struct, la fel ca aceasta.

742
00:34:52,204 --> 00:34:54,620
Și chiar dacă suntem aruncat
o mulțime de structuri de la dumneavoastră,

743
00:34:54,620 --> 00:34:56,560
sunt oarecum
intuitiv acum sperăm.

744
00:34:56,560 --> 00:35:00,570
Sintaxa este încă arcane sigur,
dar conținutul unui nod în acest

745
00:35:00,570 --> 00:35:02,786
context-- și păstrăm
folosind nodul cuvânt,

746
00:35:02,786 --> 00:35:04,910
indiferent dacă este un dreptunghi
pe ecran sau un cerc,

747
00:35:04,910 --> 00:35:08,970
e doar o container generic,
în acest caz de un copac, cum ar fi cea

748
00:35:08,970 --> 00:35:11,780
am văzut, avem nevoie de un număr întreg
în fiecare dintre nodurile

749
00:35:11,780 --> 00:35:15,460
și apoi am nevoie de două indicii de indicare
pentru copil stânga și copilul bine,

750
00:35:15,460 --> 00:35:16,590
respectiv.

751
00:35:16,590 --> 00:35:20,730
Deci, asta e modul în care s-ar putea
punerea în aplicare a că într-o struct.

752
00:35:20,730 --> 00:35:22,315
Și cum ar putea să o pună în aplicare în codul?

753
00:35:22,315 --> 00:35:26,730
Ei bine, haideți să aruncăm o rapid
uita-te la acest exemplu mic.

754
00:35:26,730 --> 00:35:29,820
Nu este funcțională, dar am
copiat și inserat ca structura.

755
00:35:29,820 --> 00:35:33,510
Și dacă funcția mea pentru un binar
arbore de căutare este numit de căutare,

756
00:35:33,510 --> 00:35:36,980
și acest lucru ia două argumente,
un număr întreg N și un pointer

757
00:35:36,980 --> 00:35:41,400
la un nod, astfel încât un pointer la arborele
sau un pointer la rădăcina unui copac,

758
00:35:41,400 --> 00:35:43,482
cum pot face despre căutarea pentru N?

759
00:35:43,482 --> 00:35:45,440
Ei bine, în primul rând, pentru că eu sunt
care se ocupă cu indicii,

760
00:35:45,440 --> 00:35:46,750
Am de gând să fac o verificare bun-simț.

761
00:35:46,750 --> 00:35:54,279
Dacă egali copac este egal nul, este N
în acest copac sau nu in acest copac?

762
00:35:54,279 --> 00:35:55,070
Ea nu poate fi, nu?

763
00:35:55,070 --> 00:35:56,870
Dacă eu sunt trecut nul,
nu e nimic acolo.

764
00:35:56,870 --> 00:35:59,230
Am putea la fel de bine doar
spune orbește return false.

765
00:35:59,230 --> 00:36:04,050
Dacă-mi dai nimic, eu cu siguranță nu pot
găsi orice număr N. Deci, ce altceva ar putea să

766
00:36:04,050 --> 00:36:04,750
verifica acum?

767
00:36:04,750 --> 00:36:12,830
Am de gând să spun și altceva, dacă N este
mai puțin de ceea ce este la nodul arborelui

768
00:36:12,830 --> 00:36:16,300
că am fost dat valoare N.

769
00:36:16,300 --> 00:36:20,270
Cu alte cuvinte, în cazul în care numărul eu sunt
cauta, N, este mai mică decât nodul

770
00:36:20,270 --> 00:36:21,340
că mă uit la.

771
00:36:21,340 --> 00:36:23,190
Și nodul caut
la este numit copac,

772
00:36:23,190 --> 00:36:26,370
și amintesc de exemplul anterior
pentru a ajunge la valoarea într-un pointer,

773
00:36:26,370 --> 00:36:28,310
Eu folosesc notația săgeată.

774
00:36:28,310 --> 00:36:35,960
Deci, dacă N este mai mică decât săgeata copac
N, eu vreau să merg conceptual stanga.

775
00:36:35,960 --> 00:36:38,590
Cum îmi exprim în căutarea plecat?

776
00:36:38,590 --> 00:36:41,560
Pentru a fi clar, dacă acest lucru este
imaginea în cauză,

777
00:36:41,560 --> 00:36:44,612
și am fost trecut ca cel mai de sus
săgeată care este îndreptat în jos.

778
00:36:44,612 --> 00:36:45,570
Asta e pointer meu copac.

779
00:36:45,570 --> 00:36:48,060
Mă arătând la rădăcina copacului.

780
00:36:48,060 --> 00:36:52,100
Și caut să zicem, pentru
numărul 44, în mod arbitrar.

781
00:36:52,100 --> 00:36:55,300
Este mai puțin de 44 sau
mai mare decât 55, evident?

782
00:36:55,300 --> 00:36:56,360
Deci, este mai mică de.

783
00:36:56,360 --> 00:36:58,760
Și așa mai departe acest lucru, dacă se aplică condiție.

784
00:36:58,760 --> 00:37:03,981
Deci conceptual, ceea ce vreau să
Căutare următor dacă caut 44?

785
00:37:03,981 --> 00:37:04,480
Da?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Exact, vreau să
căutare copilul din stânga,

788
00:37:11,100 --> 00:37:12,789
sau sub-arborele din stânga al această imagine.

789
00:37:12,789 --> 00:37:14,830
Și, de fapt, să-mi prin
imaginea aici

790
00:37:14,830 --> 00:37:17,770
pentru o clipă, deoarece
Nu pot zgâria asta.

791
00:37:17,770 --> 00:37:21,150
Dacă aș începe aici, la 55, și
Știu că valoarea 44

792
00:37:21,150 --> 00:37:23,180
Caut este de a
stânga, e un fel

793
00:37:23,180 --> 00:37:26,010
de rupere ca cartea de telefon în
jumătate sau ruperea arborelui în jumătate.

794
00:37:26,010 --> 00:37:29,660
Nu mai am să-i pese
acest întreg jumătate de copac.

795
00:37:29,660 --> 00:37:33,270
Și totuși, curios în ceea ce privește
structură, acest lucru aici că

796
00:37:33,270 --> 00:37:36,682
începe cu 33, care se
este un arbore binar de căutare.

797
00:37:36,682 --> 00:37:39,890
I-am spus cuvântul recursiv înainte, din cauza
într-adevăr, aceasta este o structură de date care

798
00:37:39,890 --> 00:37:41,707
prin definiție este recursivă.

799
00:37:41,707 --> 00:37:44,540
S-ar putea avea un copac care este această
mare, dar fiecare dintre copii săi

800
00:37:44,540 --> 00:37:46,870
reprezintă un copac doar un pic mai mic.

801
00:37:46,870 --> 00:37:50,910
În loc de a fi bunicului ea
sau bunica, acum e doar mama

802
00:37:50,910 --> 00:37:54,300
sau-- Nu pot nu say-- mama
sau tata, care ar fi ciudat.

803
00:37:54,300 --> 00:37:59,000
În schimb, doi copii de acolo
ar fi ca frate și frate.

804
00:37:59,000 --> 00:38:01,120
O nouă generație a arborelui genealogic.

805
00:38:01,120 --> 00:38:02,900
Dar structural, e aceeași idee.

806
00:38:02,900 --> 00:38:06,790
Și se pare că am o funcție
cu care am pot căuta o căutare binară

807
00:38:06,790 --> 00:38:07,290
copac.

808
00:38:07,290 --> 00:38:08,680
Este numit de căutare.

809
00:38:08,680 --> 00:38:17,870
Caut N în copac săgeată stânga
altfel daca N este mai mare decât valoarea

810
00:38:17,870 --> 00:38:18,870
că sunt în prezent la.

811
00:38:18,870 --> 00:38:20,800
55 în povestea în urmă cu o clipă.

812
00:38:20,800 --> 00:38:23,780
Am o funcție numită
căutare care pot doar

813
00:38:23,780 --> 00:38:29,660
trece N acest lucru și caută recursiv
sub-copac și doar revenirea

814
00:38:29,660 --> 00:38:30,620
indiferent de răspunsul.

815
00:38:30,620 --> 00:38:33,530
Mai am unele cazuri de bază finală aici.

816
00:38:33,530 --> 00:38:35,310
>> Care este situația finală?

817
00:38:35,310 --> 00:38:36,570
Copac este fie nul.

818
00:38:36,570 --> 00:38:39,980
Valoarea Mă fie căutați este
mai puțin decât sau mai mare decât cea

819
00:38:39,980 --> 00:38:42,610
sau egală cu aceasta.

820
00:38:42,610 --> 00:38:44,750
Și am putea spune egal
egal, dar în mod logic e

821
00:38:44,750 --> 00:38:46,500
echivalent cu a spune altceva aici doar.

822
00:38:46,500 --> 00:38:49,150
Atât de adevărat este cum mi se pare ceva.

823
00:38:49,150 --> 00:38:51,710
Deci sperăm că acest lucru este un
chiar mai convingătoare exemplu

824
00:38:51,710 --> 00:38:54,900
decât funcția sigma prost
am facut cateva cursuri spate,

825
00:38:54,900 --> 00:38:58,360
în cazul în care a fost la fel de usor de utilizat o buclă
să numere Toate numerele de la un

826
00:38:58,360 --> 00:39:02,390
să N. Aici cu o structură de date
că în sine este recursiv

827
00:39:02,390 --> 00:39:07,050
definite și recursiv trase, acum ne-am
au capacitatea de a ne exprima

828
00:39:07,050 --> 00:39:09,780
în cod care în sine este recursiv.

829
00:39:09,780 --> 00:39:12,580
Deci, acesta este același cod exact aici.

830
00:39:12,580 --> 00:39:14,400
>> Deci, ce alte probleme putem rezolva?

831
00:39:14,400 --> 00:39:18,160
Deci, un pas rapid departe de
copaci pentru doar un moment.

832
00:39:18,160 --> 00:39:20,130
Aici este, spun, pavilion german.

833
00:39:20,130 --> 00:39:22,020
Și există în mod clar o
model de acest flag.

834
00:39:22,020 --> 00:39:23,811
Și există o mulțime de
steaguri din lume care

835
00:39:23,811 --> 00:39:27,560
sunt la fel de simplu ca acest lucru din punct de vedere
de culori și modele lor.

836
00:39:27,560 --> 00:39:31,930
Dar să presupunem că acest lucru este stocat ca un
.GIF, Sau un JPEG, sau bitmap, sau un ping,

837
00:39:31,930 --> 00:39:34,240
orice format de fișier grafic
cu care esti familiarizat,

838
00:39:34,240 --> 00:39:36,460
dintre care unele suntem
joc cu în PSET4.

839
00:39:36,460 --> 00:39:41,550
Acest lucru nu pare util pentru a stoca
pixel negru, pixel negru, pixel negru,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, o grămadă de
pixeli negri pentru prima scanline,

841
00:39:44,790 --> 00:39:47,430
sau rând, apoi o grămadă de
același, apoi o grămadă

842
00:39:47,430 --> 00:39:49,530
de același, și apoi o
grămadă de pixeli roșii,

843
00:39:49,530 --> 00:39:53,020
pixeli roșu, roșu pixeli, apoi un întreg
grămadă de pixeli galbene, galben, nu?

844
00:39:53,020 --> 00:39:55,050
>> Nu e astfel de ineficiență aici.

845
00:39:55,050 --> 00:39:59,040
Cum ați intuitiv
comprima pavilion german

846
00:39:59,040 --> 00:40:01,320
dacă o pune în aplicare ca o imagine?

847
00:40:01,320 --> 00:40:04,940
Ca ceea ce informații nu putem
deranja stocarea pe disc în ordine

848
00:40:04,940 --> 00:40:08,040
pentru a reduce dimensiunea fișierului de la noastră ca
un megabyte la un kilobyte, ceva

849
00:40:08,040 --> 00:40:09,430
mai mic?

850
00:40:09,430 --> 00:40:13,130
În care se află concediere
aici pentru a fi clar?

851
00:40:13,130 --> 00:40:13,880
Ce ai putea face?

852
00:40:13,880 --> 00:40:14,380
Da?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Exact.

855
00:40:21,970 --> 00:40:24,550
De ce nu, mai degrabă decât amintesc
culoarea fiecare pixel al naibii de

856
00:40:24,550 --> 00:40:28,200
la fel ca faci in PSET4
cu formatul de fișier bitmap,

857
00:40:28,200 --> 00:40:32,060
de ce nu te reprezinta
coloana din stânga de pixeli, de exemplu

858
00:40:32,060 --> 00:40:35,370
o grămadă de pixeli negri, un buchet
de culoare roșie, și o grămadă de galben,

859
00:40:35,370 --> 00:40:39,210
și apoi doar codifica cumva
Ideea de a repeta acest 100 de ori

860
00:40:39,210 --> 00:40:41,020
sau repeta acest 1000 de ori?

861
00:40:41,020 --> 00:40:43,430
În cazul în care 100 sau 1000 este
doar un număr întreg, astfel încât să

862
00:40:43,430 --> 00:40:47,290
poate ajunge departe cu doar un singur număr
în loc de sute sau mii

863
00:40:47,290 --> 00:40:48,270
pixeli de suplimentare.

864
00:40:48,270 --> 00:40:50,990
Și într-adevăr, asta e modul în care
ar putea comprima pavilion german.

865
00:40:50,990 --> 00:40:51,490
Și

866
00:40:51,490 --> 00:40:53,470
Acum, ce putem spune despre drapelul francez?

867
00:40:53,470 --> 00:40:58,930
Și un pic de un fel de
exercitiu mental, care de pavilion

868
00:40:58,930 --> 00:41:01,040
pot fi comprimate mai mult pe disc?

869
00:41:01,040 --> 00:41:05,720
Pavilion german sau francez
pavilion, dacă luăm această abordare?

870
00:41:05,720 --> 00:41:08,490
Pavilion german, pentru că există
mai redundanță orizontală.

871
00:41:08,490 --> 00:41:12,190
Și de proiectare, mulți fișier grafic
formate funcționează într-adevăr linii de scanare ca

872
00:41:12,190 --> 00:41:12,830
orizontal.

873
00:41:12,830 --> 00:41:14,674
Ei ar putea lucra
vertical, umanitatea doar

874
00:41:14,674 --> 00:41:17,090
cu ani în urmă a decis că vom
în general, cred că de lucruri rând

875
00:41:17,090 --> 00:41:18,880
de rând în loc de coloană cu coloană.

876
00:41:18,880 --> 00:41:20,820
Deci, într-adevăr, dacă ai fi fost
să se uite la fișierul

877
00:41:20,820 --> 00:41:24,670
mărimea unui pavilion german și francez
pavilion, atât timp cât rezoluția este

878
00:41:24,670 --> 00:41:27,530
același, aceeași lățime
și înălțimea, aceasta

879
00:41:27,530 --> 00:41:31,580
aici va fi mai mare, pentru că
Trebuie să vă repetați de trei ori.

880
00:41:31,580 --> 00:41:35,570
Trebuie să specificați albastru, repetați
le alb, repeta le roșu,

881
00:41:35,570 --> 00:41:36,740
repeta-te.

882
00:41:36,740 --> 00:41:39,000
Nu poți să mergi tot
drumul spre dreapta.

883
00:41:39,000 --> 00:41:41,200
Și, ca o paranteza, de a face
clar de compresie

884
00:41:41,200 --> 00:41:43,910
este peste tot, în cazul în care acestea sunt
patru cadre de la un video-- te

885
00:41:43,910 --> 00:41:45,890
s-ar putea aminti că un film
sau video este, în general

886
00:41:45,890 --> 00:41:47,286
cum ar fi 29 sau 30 de cadre pe secundă.

887
00:41:47,286 --> 00:41:50,410
E ca o carte de flip pic în cazul în care
vedea doar imaginea, imagine, imagine, imagine,

888
00:41:50,410 --> 00:41:54,410
imagine doar super-rapid, astfel se pare ca
actorii de pe ecran sunt în mișcare.

889
00:41:54,410 --> 00:41:57,130
Iată un bondar pe
partea de sus a un buchet de flori.

890
00:41:57,130 --> 00:41:59,790
Și, deși ar putea fi un fel de
greu pentru a vedea la prima vedere,

891
00:41:59,790 --> 00:42:04,020
singurul lucru se deplasează în
acest film este albina.

892
00:42:04,020 --> 00:42:06,880
>> Ce este prost despre stocarea
imagini video necomprimate,?

893
00:42:06,880 --> 00:42:11,420
E un fel de deșeuri pentru a stoca filme
ca patru imagini aproape identice care

894
00:42:11,420 --> 00:42:13,670
diferă numai în măsura în care albina este.

895
00:42:13,670 --> 00:42:16,280
Puteți arunca mai
de aceste informații

896
00:42:16,280 --> 00:42:20,190
și amintiți-vă doar, de exemplu,
primul cadru și ultimul cadru,

897
00:42:20,190 --> 00:42:22,180
cadre cheie dacă ați
auzit vreodată cuvântul,

898
00:42:22,180 --> 00:42:24,337
și doar magazin din
mijloc în cazul în care albina este.

899
00:42:24,337 --> 00:42:26,170
Și nu trebuie să
stoca toate roz,

900
00:42:26,170 --> 00:42:28,330
și albastru, și
Valorile verzi, de asemenea.

901
00:42:28,330 --> 00:42:31,200
Deci, acest lucru este de a spune doar că
compresie este peste tot.

902
00:42:31,200 --> 00:42:34,900
Este o tehnica de multe ori am folosi
sau de a lua de la sine aceste zile.

903
00:42:34,900 --> 00:42:38,750
>> Dar cum a face tu comprima text?

904
00:42:38,750 --> 00:42:40,450
Cum te duci despre comprimarea text?

905
00:42:40,450 --> 00:42:45,410
Ei bine, fiecare dintre personajele din
ASCII este un octet, sau opt biți.

906
00:42:45,410 --> 00:42:47,360
Și asta e un fel de prost, nu?

907
00:42:47,360 --> 00:42:51,160
Pentru că, probabil, de tip A
și E și I și O și U o mulțime

908
00:42:51,160 --> 00:42:55,270
mai des decât ca W sau Q sau Z,
în funcție de limba în care

909
00:42:55,270 --> 00:42:56,610
scrii cu siguranță.

910
00:42:56,610 --> 00:42:59,600
Și atunci de ce suntem folosind
opt biți pentru fiecare literă,

911
00:42:59,600 --> 00:43:02,040
inclusiv cel mai puțin
scrisori populare, nu?

912
00:43:02,040 --> 00:43:05,300
De ce nu folosiți mai puțini biți pentru
Super populare litere,

913
00:43:05,300 --> 00:43:07,760
cum ar fi e, lucrurile pe care le ghici
pentru prima dată în Roata Norocului,

914
00:43:07,760 --> 00:43:10,450
și de a folosi mai multe biți pentru
cele mai puțin populare literele?

915
00:43:10,450 --> 00:43:10,950
Ce?

916
00:43:10,950 --> 00:43:13,130
Pentru ca suntem doar de gând să
le folosesc mai rar.

917
00:43:13,130 --> 00:43:15,838
>> Ei bine, se pare că au
fost făcute încercări de a face acest lucru.

918
00:43:15,838 --> 00:43:18,630
Și dacă vă amintiți de la clasa
școală sau liceu, codul Morse.

919
00:43:18,630 --> 00:43:20,400
Codul Morse a puncte
și linii care poate fi

920
00:43:20,400 --> 00:43:24,270
transmise de-a lungul unui fir ca
sunete sau semnale de un fel.

921
00:43:24,270 --> 00:43:25,930
Dar codul Morse este un super curat.

922
00:43:25,930 --> 00:43:29,010
E un fel de sistem binar în
că aveți puncte sau liniuțe.

923
00:43:29,010 --> 00:43:30,977
Dar dacă vezi, de exemplu, două puncte.

924
00:43:30,977 --> 00:43:33,810
Sau, dacă credeți că înapoi la operatorul
care merge ca bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
beep, lovind un pic de declanșare
care transmite un semnal,

926
00:43:36,760 --> 00:43:40,360
dacă, destinatarul primește două
puncte, ce mesaj ați primit?

927
00:43:40,360 --> 00:43:43,490
Complet arbitrar.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Sau ce about-- sau eu?

931
00:43:47,500 --> 00:43:49,570
Poate a fost doar doi dreptate E lui?

932
00:43:49,570 --> 00:43:52,480
Deci nu e problema
de Decodării cu Morse

933
00:43:52,480 --> 00:43:54,890
Codul, cu excepția cazului în care
persoană să vă trimită un mesaj

934
00:43:54,890 --> 00:43:59,510
de fapt, o pauză, astfel încât să puteți sorta de
vedea sau auzi golurile dintre litere,

935
00:43:59,510 --> 00:44:02,990
nu este suficient doar pentru a
trimite un flux de zerouri și cele,

936
00:44:02,990 --> 00:44:05,610
sau puncte și linii,
pentru că există ambiguitate.

937
00:44:05,610 --> 00:44:08,640
E este un singur punct, așa că, dacă
vedea două puncte sau auzi două puncte,

938
00:44:08,640 --> 00:44:11,254
Poate că e de două E sau poate e un I.

939
00:44:11,254 --> 00:44:13,670
Deci, avem nevoie de un sistem care este un
puțin mai mult inteligent decât atât.

940
00:44:13,670 --> 00:44:16,851
Deci, un om pe nume Huffman ani
Acum a venit cu exact acest lucru.

941
00:44:16,851 --> 00:44:18,600
Deci, noi suntem doar de gând
să ia o privire rapidă

942
00:44:18,600 --> 00:44:20,114
la modul în care copacii sunt germane la acest lucru.

943
00:44:20,114 --> 00:44:22,530
Să presupunem că acest lucru este unele
Mesajul prost doriți să trimiteți,

944
00:44:22,530 --> 00:44:26,342
compusă din doar A, B, D C S și lui E,
dar există o mulțime de concediere aici.

945
00:44:26,342 --> 00:44:27,550
Nu este menit să fie limba engleză.

946
00:44:27,550 --> 00:44:28,341
Nu e criptat.

947
00:44:28,341 --> 00:44:30,540
E doar un mesaj prost
cu o mulțime de repetiție.

948
00:44:30,540 --> 00:44:34,010
Deci, dacă te numeri efectiv tot
A lui, E lui lui B, C lui, D, și, iată

949
00:44:34,010 --> 00:44:34,890
frecvența.

950
00:44:34,890 --> 00:44:37,800
20% dintre literele sunt
A lui, 45% din scrisorile

951
00:44:37,800 --> 00:44:39,660
sunt E lui, și alte trei frecvențe.

952
00:44:39,660 --> 00:44:41,960
Am numărat acolo manual
și doar a făcut calculele.

953
00:44:41,960 --> 00:44:44,579
>> Deci, se dovedește că
Huffman, ceva timp în urmă,

954
00:44:44,579 --> 00:44:46,620
a dat seama că, știți
ceea ce, în cazul în care încep de construcție

955
00:44:46,620 --> 00:44:51,172
un copac, sau padure de copaci, dacă vreți,
după cum urmează, pot face următoarele.

956
00:44:51,172 --> 00:44:53,880
Am de gând să dea un nod la fiecare
scrisorilor pe care le pasă

957
00:44:53,880 --> 00:44:55,530
și am de gând pentru a stoca
în interiorul acestui nod

958
00:44:55,530 --> 00:44:58,610
frecvențele ca un punct de flotant
valoare, sau ai putea folosi o N, de asemenea,

959
00:44:58,610 --> 00:45:00,210
dar vom folosi doar un float aici.

960
00:45:00,210 --> 00:45:03,100
Și algoritmul care
el a propus este că

961
00:45:03,100 --> 00:45:07,210
să ia această pădure de nod unic
copaci, copaci, astfel super-scurt,

962
00:45:07,210 --> 00:45:11,920
și de a începe să le cu conectarea
grupuri noi, noi părinții, dacă vrei.

963
00:45:11,920 --> 00:45:16,150
Și faci asta prin alegerea
două mai mici frecvențe la un moment dat.

964
00:45:16,150 --> 00:45:18,110
Așa că am luat 10% și 10%.

965
00:45:18,110 --> 00:45:19,090
Am crea un nou nod.

966
00:45:19,090 --> 00:45:20,910
Și fac apel noul nod de 20%.

967
00:45:20,910 --> 00:45:22,750
>> Care două noduri combina viitoare?

968
00:45:22,750 --> 00:45:23,810
E un pic ambiguu.

969
00:45:23,810 --> 00:45:26,643
Deci nu e unele cazuri colț
ia în considerare, dar pentru a menține lucrurile destul de,

970
00:45:26,643 --> 00:45:29,300
Am de gând să aleagă 20% -
Acum am ignora pe copii.

971
00:45:29,300 --> 00:45:33,640
Am de gând să aleagă 20% și
15% și să tragă două noi muchii.

972
00:45:33,640 --> 00:45:35,624
Și acum două noduri care
pot combina în mod logic?

973
00:45:35,624 --> 00:45:38,540
Ignorați toți copiii, toate
nepoți, doar uita-te la rădăcini

974
00:45:38,540 --> 00:45:39,070
acum.

975
00:45:39,070 --> 00:45:42,220
Care două noduri pot lega împreună?

976
00:45:42,220 --> 00:45:44,530
Punct de două și 0,35.

977
00:45:44,530 --> 00:45:45,890
Deci lasă-mă să elaboreze două noi muchii.

978
00:45:45,890 --> 00:45:47,570
Și apoi am doar un singur stângă.

979
00:45:47,570 --> 00:45:48,650
Deci, aici e un copac.

980
00:45:48,650 --> 00:45:51,160
Și a fost întocmită în mod deliberat
să se uite un fel de frumos,

981
00:45:51,160 --> 00:45:55,870
dar observați că marginile au
De asemenea, a fost etichetate zero și unu.

982
00:45:55,870 --> 00:45:59,510
Deci toate marginile rămase sunt zero
arbitrar, dar în mod constant.

983
00:45:59,510 --> 00:46:01,170
Toate marginile din dreapta sunt cele.

984
00:46:01,170 --> 00:46:05,070
>> Și așa mai departe ceea ce a propus Hoffman este,
dacă doriți să reprezinte un B,

985
00:46:05,070 --> 00:46:10,080
mai degrabă decât reprezintă numărul 66 ca
ASCII care este de opt biți întregi,

986
00:46:10,080 --> 00:46:13,360
Știi ce, doar magazin
modelul de zero, zero, zero,

987
00:46:13,360 --> 00:46:17,030
zero pentru că asta e calea
din copacul meu, domnul copac Huffman lui,

988
00:46:17,030 --> 00:46:18,600
la frunza de la rădăcină.

989
00:46:18,600 --> 00:46:20,970
Dacă doriți să stocați un
E, prin contrast, nu

990
00:46:20,970 --> 00:46:26,290
trimite opt biți care reprezintă un E.
În schimb, trimite ce model de biți?

991
00:46:26,290 --> 00:46:26,890
Unul.

992
00:46:26,890 --> 00:46:30,410
Și ce e frumos despre acest lucru este
că E este cel mai popular scrisoare,

993
00:46:30,410 --> 00:46:32,340
și utilizați
cel mai scurt codul pentru el.

994
00:46:32,340 --> 00:46:34,090
Următoarea mai populare
scrisoare pare ca

995
00:46:34,090 --> 00:46:37,380
a fost A. Și câți biți
-a propus utilizarea pentru asta?

996
00:46:37,380 --> 00:46:38,270
Zero, unul.

997
00:46:38,270 --> 00:46:41,060
>> Și pentru că este pus în aplicare
ca acest copac, de acum

998
00:46:41,060 --> 00:46:43,350
lasă-mă să prevadă există
nici o ambiguitate ca în Morse

999
00:46:43,350 --> 00:46:46,090
cod, deoarece toate
scrisori care vă interesează

1000
00:46:46,090 --> 00:46:48,780
sunt la finalul acestor margini.

1001
00:46:48,780 --> 00:46:50,580
Deci asta e doar o
aplicarea unui copac.

1002
00:46:50,580 --> 00:46:52,538
Acest este-- și voi val
mâna mea la acest modul în care

1003
00:46:52,538 --> 00:46:55,570
s-ar putea să pună în aplicare acest lucru ca pe o structură C.

1004
00:46:55,570 --> 00:46:58,260
Avem nevoie doar de a combina
un simbol, ca un char,

1005
00:46:58,260 --> 00:46:59,910
și frecvența în stânga și dreapta.

1006
00:46:59,910 --> 00:47:02,510
Dar să ne uităm la două
exemple finale pe care le vei

1007
00:47:02,510 --> 00:47:06,070
obține destul de familiarizat cu după
test zero în problema set de cinci.

1008
00:47:06,070 --> 00:47:09,210
>> Deci, nu există structura de date
cunoscut ca un tabel hash.

1009
00:47:09,210 --> 00:47:12,247
Și un tabel hash este un fel de
se răcească în care acesta are pistoane.

1010
00:47:12,247 --> 00:47:14,830
Și să presupunem că e patru găleți
aici, doar patru spații goale.

1011
00:47:14,830 --> 00:47:20,830
Iată un pachet de cărți, și aici este
club, cazma, club, diamante, club,

1012
00:47:20,830 --> 00:47:25,960
diamante, club, diamante,
astfel clubs-- aceasta este aleatorie.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts-- așa că eu sunt
bucketizing toate intrările aici.

1014
00:47:30,330 --> 00:47:32,430
Și are nevoie de masă hash
să se uite la dvs. de intrare,

1015
00:47:32,430 --> 00:47:34,850
și apoi pune-l într-o anumită
loc pe baza ceea ce vezi.

1016
00:47:34,850 --> 00:47:35,600
Este un algoritm.

1017
00:47:35,600 --> 00:47:37,980
Și am fost folosind un super
algoritm vizual simplu.

1018
00:47:37,980 --> 00:47:40,030
Cea mai grea parte a care a fost
amintindu care au fost imaginile.

1019
00:47:40,030 --> 00:47:41,590
Și apoi există patru lucruri totale.

1020
00:47:41,590 --> 00:47:45,440
>> Acum stive au fost în creștere, care
este un lucru de design deliberat aici.

1021
00:47:45,440 --> 00:47:46,540
Dar ce altceva s-ar putea să fac?

1022
00:47:46,540 --> 00:47:49,080
Deci, de fapt, aici avem o
grămadă de cărți de examen Old School.

1023
00:47:49,080 --> 00:47:51,240
Să presupunem că o grămadă de
Numele elevilor sunt pe aici.

1024
00:47:51,240 --> 00:47:52,570
Iată un tabel hash mai mare.

1025
00:47:52,570 --> 00:47:54,867
În loc de patru pistoane,
Am, să spunem 26.

1026
00:47:54,867 --> 00:47:57,950
Și nu am vrut să merg împrumute 26
lucruri din afara [? Annenberg?], Așa

1027
00:47:57,950 --> 00:48:00,289
aici e cinci, care reprezintă
Un prin Z. Și dacă

1028
00:48:00,289 --> 00:48:03,580
vezi un student al cărui nume începe cu A,
Am de gând să lui sau test pus acolo.

1029
00:48:03,580 --> 00:48:08,850
Dacă cineva începe cu C, acolo,
Un-- de fapt, nu a vrut să fac asta.

1030
00:48:08,850 --> 00:48:10,060
B merge aici.

1031
00:48:10,060 --> 00:48:13,390
Deci am A și B și C și
Acum, aici e un alt student A.

1032
00:48:13,390 --> 00:48:16,212
Dar dacă acest tabel hash este
puse în aplicare cu o matrice,

1033
00:48:16,212 --> 00:48:17,920
Sunt un fel de filetat
în acest moment, nu?

1034
00:48:17,920 --> 00:48:19,510
Am facut un fel de nevoie de a pune această undeva.

1035
00:48:19,510 --> 00:48:24,380
>> Deci, într-un fel eu pot rezolva acest lucru este, toate
drept, A este ocupat, B este ocupat, C este ocupat.

1036
00:48:24,380 --> 00:48:28,880
Am de gând să-l pună în D. Deci, la
în primul rând, am acces instant aleator

1037
00:48:28,880 --> 00:48:31,064
la fiecare dintre gălețile pentru studenți.

1038
00:48:31,064 --> 00:48:33,230
Dar acum e un fel de descentralizat
în ceva liniar,

1039
00:48:33,230 --> 00:48:36,750
pentru că dacă vreau pentru a căuta pe cineva
al cărui nume începe cu A, am verifica aici.

1040
00:48:36,750 --> 00:48:38,854
Dar dacă acest lucru nu este A
Student caut,

1041
00:48:38,854 --> 00:48:41,520
Am facut un fel de trebuie să începe verificarea
gălețile, pentru că ceea ce am făcut

1042
00:48:41,520 --> 00:48:44,530
a fost un fel de liniar
sonda structura de date.

1043
00:48:44,530 --> 00:48:47,710
Un mod stupid de a spune doar uita-te
pentru prima deschidere disponibile,

1044
00:48:47,710 --> 00:48:51,850
și a pus ca un plan B, ca să spunem așa,
sau plan de dezvoltare în acest caz, valoarea

1045
00:48:51,850 --> 00:48:53,340
în acel loc în loc.

1046
00:48:53,340 --> 00:48:56,470
Acesta este doar astfel încât, dacă ați
Trebuie 26 locații și nici elevi

1047
00:48:56,470 --> 00:49:00,600
cu Q nume sau Z, sau ceva de genul
că, cel puțin pe care îl utilizați spațiul.

1048
00:49:00,600 --> 00:49:03,140
>> Dar am văzut deja mai mult
soluții inteligente de aici, nu?

1049
00:49:03,140 --> 00:49:04,870
Ce ai face loc
dacă aveți o coliziune?

1050
00:49:04,870 --> 00:49:06,670
Dacă doi oameni au
nume A, ceea ce ar fi

1051
00:49:06,670 --> 00:49:09,160
au fost mai inteligent sau
soluție intuitivă decât

1052
00:49:09,160 --> 00:49:12,840
Punerea o în cazul în care D ar trebui să fie?

1053
00:49:12,840 --> 00:49:14,810
De ce nu mă duci
în afara [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
ca malloc, un alt nod, pune-l
aici, și a pus apoi că un student aici.

1055
00:49:19,960 --> 00:49:22,120
Așa că am, în esență,
un fel de o matrice,

1056
00:49:22,120 --> 00:49:25,590
sau poate mai mult elegant ca suntem
pornire pentru a vedea o listă legată.

1057
00:49:25,590 --> 00:49:29,520
>> Și așa o masă hash este o structură
care ar putea arata exact ca aceasta,

1058
00:49:29,520 --> 00:49:33,900
dar mai inteligent, ai ceva numit
înlănțuire separat, prin care un tabel hash

1059
00:49:33,900 --> 00:49:38,340
pur și simplu este o matrice, fiecare dintre
ale cărui elemente nu este un număr,

1060
00:49:38,340 --> 00:49:40,470
este ea însăși o listă legată.

1061
00:49:40,470 --> 00:49:45,080
Astfel încât să obțineți acces super rapid
decide unde să hash valoare la.

1062
00:49:45,080 --> 00:49:48,059
La fel ca în exemplul carduri,
Am luat decizii foarte rapide.

1063
00:49:48,059 --> 00:49:49,600
Hearts merge aici, diamante merge aici.

1064
00:49:49,600 --> 00:49:52,180
La fel aici, A merge aici,
D merge aici, B merge aici.

1065
00:49:52,180 --> 00:49:55,740
Deci, super rapid uite-up-uri, și în cazul în care
se întâmplă pentru a rula într-un caz

1066
00:49:55,740 --> 00:49:59,429
coliziuni în cazul în care ați luat-o, două
persoane cu același nume, și apoi

1067
00:49:59,429 --> 00:50:00,970
doar de a începe asocierea acestora împreună.

1068
00:50:00,970 --> 00:50:03,900
Și poate vă păstrați-le sortate
în ordine alfabetică, poate că nu.

1069
00:50:03,900 --> 00:50:05,900
Dar cel puțin acum avem dinamismul.

1070
00:50:05,900 --> 00:50:10,250
Deci, pe de o parte, avem super rapid
constantă de timp, și un fel de timp liniar

1071
00:50:10,250 --> 00:50:14,110
implicat în cazul în care aceste liste legate
începe pentru a obține un pic cam lung.

1072
00:50:14,110 --> 00:50:16,880
>> Deci, acest fel de prostie,
ani în urmă. geeky glumă

1073
00:50:16,880 --> 00:50:19,590
La CS50 hack-a-Thon,
atunci când elevii check-in,

1074
00:50:19,590 --> 00:50:22,040
unele TF sau CA în fiecare an
crede că e amuzant să pună

1075
00:50:22,040 --> 00:50:27,772
un semn ca aceasta, în cazul în care doar
înseamnă că dacă numele tău începe cu un A,

1076
00:50:27,772 --> 00:50:28,870
du-te în acest fel.

1077
00:50:28,870 --> 00:50:31,110
Dacă numele tău începe
cu un B, du-te astea-- OK,

1078
00:50:31,110 --> 00:50:33,290
e amuzant Poate mai târziu în semestrul.

1079
00:50:33,290 --> 00:50:36,420
Dar există o altă
mod de a face acest lucru, de asemenea.

1080
00:50:36,420 --> 00:50:37,410
Întoarce-te la asta.

1081
00:50:37,410 --> 00:50:38,600
>> Deci, există această structură.

1082
00:50:38,600 --> 00:50:40,420
Și aceasta este ultima noastră
structură pentru ziua de azi,

1083
00:50:40,420 --> 00:50:42,400
care este ceva numit un trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, care din anumite motive este scurt
pentru recuperare, dar se numește trie.

1085
00:50:47,140 --> 00:50:51,389
Deci, un trie este un alt interesant
amalgam de o mulțime de aceste idei.

1086
00:50:51,389 --> 00:50:52,930
Este un copac, pe care le-am văzut înainte.

1087
00:50:52,930 --> 00:50:54,180
Nu este un arbore binar de căutare.

1088
00:50:54,180 --> 00:50:58,410
Este un copac cu orice număr de copii,
dar fiecare dintre copii într-o trie

1089
00:50:58,410 --> 00:51:00,090
este o matrice.

1090
00:51:00,090 --> 00:51:04,790
O serie de dimensiuni, spun, 26 sau poate 27
dacă doriți să sprijine nume despărțite

1091
00:51:04,790 --> 00:51:06,790
sau apostrofuri în numele oamenilor.

1092
00:51:06,790 --> 00:51:08,280
>> Și așa este o structură de date.

1093
00:51:08,280 --> 00:51:10,290
Și dacă te uiți de sus
în jos, cum ar fi dacă ați

1094
00:51:10,290 --> 00:51:13,710
uita-te la nodul de sus acolo, M, este
arătând spre stânga lucru acolo,

1095
00:51:13,710 --> 00:51:17,665
care este apoi A, X, W, E, L, L. Acest lucru este
doar o structură de date care în mod arbitrar

1096
00:51:17,665 --> 00:51:19,120
este stocarea numele oamenilor.

1097
00:51:19,120 --> 00:51:25,720
Și Maxwell sunt stocate de doar în urma
o cale de matrice pentru a matrice de matrice.

1098
00:51:25,720 --> 00:51:30,050
Dar ceea ce este uimitor cu privire la un trie este
că, în timp ce o listă legată și chiar

1099
00:51:30,050 --> 00:51:34,520
o matrice, cel mai bun am ajuns vreodată este
timp liniar sau de timp logaritmică căutarea

1100
00:51:34,520 --> 00:51:35,600
cineva.

1101
00:51:35,600 --> 00:51:40,530
În această structură de date a unui trie, în cazul în care
structura mea de date are un nume în ea

1102
00:51:40,530 --> 00:51:43,720
și caut Maxwell, eu sunt
O să-l găsim destul de repede.

1103
00:51:43,720 --> 00:51:47,910
Mă uit doar pentru M-A-X-W-E-L-L. Dacă
această structură de date, prin contrast,

1104
00:51:47,910 --> 00:51:51,830
dacă N este un milion, dacă există o
milioane de nume în această structură de date,

1105
00:51:51,830 --> 00:51:57,100
Maxwell este încă va fi
detectabil după doar M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
pași.

1107
00:51:58,090 --> 00:52:01,276
Și etapele David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Cu alte cuvinte, prin construirea
o structură de date care este

1109
00:52:03,400 --> 00:52:07,240
Trebuie de care toate aceste tablouri, toate
se intretine cu acces aleator,

1110
00:52:07,240 --> 00:52:11,090
Pot începe căutarea în sus lui oameni
numele folosind o cantitate de timp în care este

1111
00:52:11,090 --> 00:52:14,340
proporțional cu numărul de nu
de lucruri în structura de date,

1112
00:52:14,340 --> 00:52:16,330
ca un milioane de nume existente.

1113
00:52:16,330 --> 00:52:20,135
Durata de timp este nevoie de mine pentru a găsi
M-O-X-W-E-L-L în această structură de date este

1114
00:52:20,135 --> 00:52:22,260
proporțională nu cu
Dimensiunea de structura de date,

1115
00:52:22,260 --> 00:52:25,930
dar la lungimea numelui.

1116
00:52:25,930 --> 00:52:28,440
Și realist
Numele ne uităm în sus

1117
00:52:28,440 --> 00:52:29,970
nu sunt niciodată de gând să fie nebun lung.

1118
00:52:29,970 --> 00:52:32,600
Poate cineva are un caracter de 10
numele, 20 nume de caractere.

1119
00:52:32,600 --> 00:52:33,900
Este cu siguranță finit, nu?

1120
00:52:33,900 --> 00:52:37,110
Există un om de pe Pamant, care
are cel mai lung nume posibil,

1121
00:52:37,110 --> 00:52:39,920
dar numele este o constantă
lungime valoare, nu?

1122
00:52:39,920 --> 00:52:41,980
Nu variază în nici un sens.

1123
00:52:41,980 --> 00:52:45,090
Deci, în acest fel, am
realizat o structură de date

1124
00:52:45,090 --> 00:52:47,800
care este constantă de timp uite-up.

1125
00:52:47,800 --> 00:52:50,670
Aceasta nu ia o serie de măsuri
în funcție de lungimea de intrare,

1126
00:52:50,670 --> 00:52:54,250
dar nu numărul numelui
în structura de date.

1127
00:52:54,250 --> 00:52:58,700
Deci, dacă ne-am dubla numărul de nume
anul viitor, de la un miliard la două miliarde de euro,

1128
00:52:58,700 --> 00:53:03,720
constatare Maxwell este de gând să ia
același număr exact de șapte pași

1129
00:53:03,720 --> 00:53:04,650
să-l găsească.

1130
00:53:04,650 --> 00:53:08,810
Și așa se pare că am atins
Graal nostru sfânt de timpul de funcționare.

1131
00:53:08,810 --> 00:53:10,860
>> Deci, un cuplu de anunțuri rapid.

1132
00:53:10,860 --> 00:53:11,850
Quiz zero, se apropie.

1133
00:53:11,850 --> 00:53:14,600
Mai multe pe site-ul care pe parcursul a
în următoarele două zile.

1134
00:53:14,600 --> 00:53:17,120
De luni lecture-- Este o sărbătoare
aici, la Harvard luni.

1135
00:53:17,120 --> 00:53:18,850
Nu e în New Haven,
așa că luați clasa

1136
00:53:18,850 --> 00:53:20,310
la New Haven pentru prelegere luni.

1137
00:53:20,310 --> 00:53:22,550
Totul va fi filmat
și transmisă în direct, ca de obicei,

1138
00:53:22,550 --> 00:53:24,900
dar să se încheie astăzi
cu un al doilea clip de 30

1139
00:53:24,900 --> 00:53:26,910
numitele "Gânduri profunde"
de Daven Farnham, care

1140
00:53:26,910 --> 00:53:30,850
a fost inspirat anul trecut de sâmbătă
"Gânduri adânci" Night Live de

1141
00:53:30,850 --> 00:53:35,700
de Jack Handy, care
ar trebui să facă acum un sens.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Și acum, "Deep
Gânduri "de Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tabel hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Bine, asta e de acum.

1147
00:53:47,660 --> 00:53:48,805
Ne vedem săptămâna viitoare.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: să-l văd în acțiune.

1150
00:53:56,680 --> 00:53:58,304
Deci, haideți să aruncăm o privire la asta acum.

1151
00:53:58,304 --> 00:53:59,890
Deci, aici, avem o serie nesortate.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, pot merge mai departe și repornire
acest lucru pentru doar o secundă, vă rog.

1153
00:54:04,860 --> 00:54:08,562
Bine, camere sunt de rulare, astfel încât
acțiune ori de câte ori sunteți gata, Doug, bine?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Bine, deci ceea ce am
avem aici este o matrice nesortate.

1155
00:54:11,020 --> 00:54:13,960
Și am colorat toate elementele
roșu pentru a indica faptul că acesta este, de fapt,

1156
00:54:13,960 --> 00:54:14,460
nesortate.

1157
00:54:14,460 --> 00:54:17,960
Deci amintesc că primul lucru pe care o facem
este ne sorta jumătatea stângă a tabloului.

1158
00:54:17,960 --> 00:54:20,630
Apoi ne-am sorta dreapta
jumătate din matrice.

1159
00:54:20,630 --> 00:54:22,830
Și Ya-da, Ya-da, Ya-da,
le merge împreună.

1160
00:54:22,830 --> 00:54:24,520
Și avem o gamă complet sortat.

1161
00:54:24,520 --> 00:54:25,360
Deci așa merge sort funcționează.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Ho, ho, ho,
cut, cut, cut, tăiate.

1163
00:54:27,109 --> 00:54:30,130
Doug, nu poți doar Ya-da, Ya-da,
Ya-da, ți de drum prin îmbinare fel.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Tocmai am făcut-o.

1165
00:54:31,970 --> 00:54:32,832
Este bine.

1166
00:54:32,832 --> 00:54:33,540
Suntem bine să mergem.

1167
00:54:33,540 --> 00:54:34,760
Să păstreze rulare.

1168
00:54:34,760 --> 00:54:35,380
Deci, oricum,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Trebuie să explice
mai deplin decât atât.

1170
00:54:37,800 --> 00:54:39,999
Asta nu e suficienta.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, noi nu
Trebuie să mă întorc la o.

1172
00:54:41,790 --> 00:54:42,350
Este bine.

1173
00:54:42,350 --> 00:54:45,690
Deci, oricum, dacă vom continua cu merge--
Ian, suntem în mijlocul filmare.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Știu.

1175
00:54:46,612 --> 00:54:49,320
Și nu putem doar Ya-da, Ya-da,
Ya-da, prin întregul proces.

1176
00:54:49,320 --> 00:54:52,200
Trebuie să explice modul în care
cele două părți se fuzionat împreună.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Dar am deja
a explicat modul în care două sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Ai doar afișate
le o gamă merge.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Ei știu procesul.

1180
00:54:56,486 --> 00:54:57,172
Sunt bine.

1181
00:54:57,172 --> 00:54:58,380
Am trecut peste asta de zece ori.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Tocmai ai sărit chiar peste ea.

1183
00:55:00,330 --> 00:55:03,360
Mergem înapoi la unul,
nu poți Ya-da, da-Ya peste el.

1184
00:55:03,360 --> 00:55:05,480
Bine, înapoi la unul.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Am să mă întorc
prin toate slide-uri?

1186
00:55:07,833 --> 00:55:08,332
Dumnezeul meu.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
E ca și cum a șasea oară, Ian.

1189
00:55:13,004 --> 00:55:13,940
Este bine.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Bine.

1191
00:55:15,200 --> 00:55:16,590
Ești gata?

1192
00:55:16,590 --> 00:55:17,400
Grozav.

1193
00:55:17,400 --> 00:55:18,950
Acțiune.