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

2
00:00:10,900 --> 00:00:15,860
>> Reproduktor 1: Dobre, takže to je
CS50 To je koniec týždňa päť.

3
00:00:15,860 --> 00:00:19,220
A pripomenúť, že minule sme
začal hľadať na chovateľa dát

4
00:00:19,220 --> 00:00:22,310
štruktúry, ktoré začali riešiť
problémy, ktoré začali zavádzať

5
00:00:22,310 --> 00:00:25,640
nové problémy, ale, ktorého by malo
bol druh závitom, ktoré sme

6
00:00:25,640 --> 00:00:27,940
začal robiť z uzla do uzla.

7
00:00:27,940 --> 00:00:30,085
Takže to je samozrejme
single previazaný zoznam.

8
00:00:30,085 --> 00:00:31,960
A jednotlivo prepojené,
Myslím, že je len jeden

9
00:00:31,960 --> 00:00:33,380
závit medzi každý z týchto uzlov.

10
00:00:33,380 --> 00:00:35,890
Ukázalo sa, že môžete robiť milovník
veci, ako je dvojnásobne spojových zoznamov

11
00:00:35,890 --> 00:00:38,470
kedy máte šípku
sa v oboch smeroch, čo

12
00:00:38,470 --> 00:00:40,320
môže pomôcť s niektorými účinnosťou.

13
00:00:40,320 --> 00:00:42,000
Ale tento problém vyriešil?

14
00:00:42,000 --> 00:00:43,500
Aký problém sa to vyriešiť?

15
00:00:43,500 --> 00:00:46,620
Prečo sa staráme v pondelok?

16
00:00:46,620 --> 00:00:49,820
Prečo, teoreticky, sa staráme v pondelok?

17
00:00:49,820 --> 00:00:50,630
Čo to robí?

18
00:00:50,630 --> 00:00:51,950
>> Divákov: Môžeme dynamicky zmeniť jeho veľkosť.

19
00:00:51,950 --> 00:00:53,740
>> Reproduktor 1: OK, tak môžeme
dynamicky zmeniť jeho veľkosť.

20
00:00:53,740 --> 00:00:54,710
Výborne vás oboch.

21
00:00:54,710 --> 00:00:57,560
Takže môžete dynamicky meniť veľkosť tejto
štruktúra dát, zatiaľ čo pole,

22
00:00:57,560 --> 00:01:00,760
Pripomeňme, musíte vedieť
priori, koľko miesta chcete

23
00:01:00,760 --> 00:01:03,870
a ak budete potrebovať trochu viac
priestor, ste trochu smolu.

24
00:01:03,870 --> 00:01:05,560
Musíte vytvoriť úplne nové pole.

25
00:01:05,560 --> 00:01:07,893
Musíte presunúť všetky vaše
dáta z jedného na druhého,

26
00:01:07,893 --> 00:01:10,600
nakoniec oslobodil starý poľa
ak je to možné, a potom pokračujte.

27
00:01:10,600 --> 00:01:13,891
Ktorá sa práve cíti veľmi nákladné a veľmi
neefektívne, a v skutočnosti, že môže byť.

28
00:01:13,891 --> 00:01:14,890
Ale to nie je všetko dobré.

29
00:01:14,890 --> 00:01:18,180
Platíme cenu, čo bol jeden
z viac zjavné ceny my

30
00:01:18,180 --> 00:01:20,550
zaplatiť pomocou prepojeného zoznamu?

31
00:01:20,550 --> 00:01:22,825
>> Divákov: Musíme použiť
dvojitý priestor pre každú z nich.

32
00:01:22,825 --> 00:01:25,200
Reproduktor 1: Jo, takže potrebujeme
najmenej dvakrát toľko priestoru.

33
00:01:25,200 --> 00:01:27,700
V skutočnosti, som si uvedomil, tento obrázok je
dokonca aj trochu zavádzajúce,

34
00:01:27,700 --> 00:01:32,200
pretože na CS50 IDE v mnohých moderných
počítače, ukazovateľ alebo adresa

35
00:01:32,200 --> 00:01:33,700
nie je v skutočnosti štyri bajty.

36
00:01:33,700 --> 00:01:36,090
Je to veľmi často títo
dni osem bajtov, ktoré

37
00:01:36,090 --> 00:01:38,530
znamená, že spodná časť najviac
obdĺžniky tam v skutočnosti

38
00:01:38,530 --> 00:01:40,900
sú trochu dvakrát
veľký ako to, čo som sa vyvodiť,

39
00:01:40,900 --> 00:01:44,409
čo znamená, že používate trikrát ako
veľký priestor, ako by sme mať inak.

40
00:01:44,409 --> 00:01:46,700
Teraz v rovnakej dobe, my sme
stále hovoril bytov, nie?

41
00:01:46,700 --> 00:01:49,140
My nie nutne hovoriť
megabajty alebo gigabajty,

42
00:01:49,140 --> 00:01:51,000
ak niet týchto údajov štruktúry dostať veľký.

43
00:01:51,000 --> 00:01:54,510
>> A tak dnes začneme uvažovať
ako by sme mohli preskúmať údaje

44
00:01:54,510 --> 00:01:57,310
efektívnejšie, ak v
Skutočnosť, dáta dostane väčší.

45
00:01:57,310 --> 00:02:00,360
Ale poďme sa pokúsiť sa získať kanonické
operácia prvý

46
00:02:00,360 --> 00:02:02,460
že si môžete robiť na tieto
druhy dátových štruktúr.

47
00:02:02,460 --> 00:02:04,790
Takže niečo ako pripojený
Zoznam všeobecne podporuje

48
00:02:04,790 --> 00:02:07,514
operácie, ako zmazať,
vložiť a vyhľadávanie.

49
00:02:07,514 --> 00:02:08,639
A čo mám na mysli, že?

50
00:02:08,639 --> 00:02:11,222
To jednoducho znamená, že obvykle,
ak ľudia používate spájať zoznam,

51
00:02:11,222 --> 00:02:14,287
oni alebo niekto iný zaviedla
funkcie ako mazať, vkladať,

52
00:02:14,287 --> 00:02:16,120
a vyhľadávania, takže môžete
skutočne niečo robiť

53
00:02:16,120 --> 00:02:18,030
užitočné so štruktúrou dát.

54
00:02:18,030 --> 00:02:20,760
Takže poďme sa rýchlo pozrieť
na to, ako by sme mohli realizovať

55
00:02:20,760 --> 00:02:24,530
nejaký kód pre prepojenom zoznamu takto.

56
00:02:24,530 --> 00:02:27,885
>> Tak to je len niektoré C kód,
Ani kompletný program

57
00:02:27,885 --> 00:02:29,260
že som naozaj rýchlo rozdúchala.

58
00:02:29,260 --> 00:02:32,300
Nie je to on-line v distribúcii
kód, pretože to nebude v skutočnosti spustiť.

59
00:02:32,300 --> 00:02:33,790
Nevšimnúť som len
s komentár povedal,

60
00:02:33,790 --> 00:02:36,130
dot dot bodka, je tu niečo,
tam, dot dot dot, niečo, čo tam.

61
00:02:36,130 --> 00:02:38,410
A nech to len pozrieť na
aké sú šťavnaté diely.

62
00:02:38,410 --> 00:02:40,790
Takže na linke tri,
Pripomíname, že toto je teraz

63
00:02:40,790 --> 00:02:45,960
sme navrhli deklarovať uzol posledný
čas, jeden z týchto obdĺžnikových objektov.

64
00:02:45,960 --> 00:02:48,790
Má int, že budeme volať N,
ale my sme to mohli nazvať čokoľvek,

65
00:02:48,790 --> 00:02:51,920
a potom struct uzol hviezdu zvanú ďalšie.

66
00:02:51,920 --> 00:02:55,520
A len aby bolo jasno, že druhým
linka, na linke šesť, čo to je?

67
00:02:55,520 --> 00:02:57,930
Čo to robí pre nás?

68
00:02:57,930 --> 00:03:01,044
Vzhľadom k tomu, to určite vyzerá viac
mystický než naše obvyklé premenné.

69
00:03:01,044 --> 00:03:02,740
>> Divákov: To robí to pohybovať po jednom.

70
00:03:02,740 --> 00:03:04,650
>> Reproduktor 1: Tak to je pohybovať po jednom.

71
00:03:04,650 --> 00:03:08,580
A aby som bol presnejší,
to bude ukladať adresu

72
00:03:08,580 --> 00:03:11,582
uzla, ktorý je určený na
sémanticky vedľa nej, že jo?

73
00:03:11,582 --> 00:03:13,540
Takže to nebude
nutne presunúť nič.

74
00:03:13,540 --> 00:03:15,290
Je to len bude
uloženie hodnoty, čo je

75
00:03:15,290 --> 00:03:17,170
bude adresa
nejakého iného uzla,

76
00:03:17,170 --> 00:03:20,810
a to je dôvod, prečo sme povedali struct
uzol hviezda, hviezda označujúca

77
00:03:20,810 --> 00:03:22,370
ukazovateľ alebo adresa.

78
00:03:22,370 --> 00:03:26,390
OK, tak teraz, ak predpokladáme, že máme
tento N ktoré máme k dispozícii, a poďme

79
00:03:26,390 --> 00:03:29,490
Predpokladajme, že niekto iný má
vložené veľa celých čísel

80
00:03:29,490 --> 00:03:30,400
do prepojeného zoznamu.

81
00:03:30,400 --> 00:03:35,640
A to spájať zoznam je
ukázal na nejakým bodom

82
00:03:35,640 --> 00:03:39,040
premenná s názvom zoznam, ktorý je
prešiel v tu ako parameter,

83
00:03:39,040 --> 00:03:43,120
ako mám ísť o linky
14, ktorým sa vykonáva vyhľadávanie?

84
00:03:43,120 --> 00:03:45,990
Inými slovami, keď som sa vykonáva
funkcie, ktorej účel života

85
00:03:45,990 --> 00:03:48,889
je vziať int a potom sa
začiatok prepojeného zoznamu,

86
00:03:48,889 --> 00:03:50,430
že je ukazovateľ na spájať zoznam.

87
00:03:50,430 --> 00:03:52,992
Ako prvý, kto sa myslím, že David
Bol to náš dobrovoľník v pondelok,

88
00:03:52,992 --> 00:03:54,700
ukazoval na
celý spájať zoznam,

89
00:03:54,700 --> 00:03:57,820
je to, ako by sme odovzdávate
David sa ako naši argumentáciu tu.

90
00:03:57,820 --> 00:03:59,990
Ako môžeme ísť o rolovaním tento zoznam?

91
00:03:59,990 --> 00:04:04,640
No, to ukáže, že aj napriek tomu,
ukazovatele sú relatívne nové teraz na nás,

92
00:04:04,640 --> 00:04:07,010
to, čo môžeme urobiť relatívne
priamočiaro.

93
00:04:07,010 --> 00:04:09,500
>> Chystám sa ísť dopredu a
deklarovať dočasnú premennú, ktorá

94
00:04:09,500 --> 00:04:12,364
konvencií sa len tak
byť nazývaný ukazovateľ, alebo PTR,

95
00:04:12,364 --> 00:04:14,030
ale ste to mohli nazvať, čo chcete.

96
00:04:14,030 --> 00:04:16,470
A ja idem na inicializovať
že na začiatok zoznamu.

97
00:04:16,470 --> 00:04:20,050
Takže sa môžete trochu myslieť na to
ako sa ma učiteľ na druhý deň,

98
00:04:20,050 --> 00:04:23,580
druh ukázal na niekoho
medzi našimi ľuďmi ako dobrovoľníci.

99
00:04:23,580 --> 00:04:26,470
Takže som dočasné premenné, ktoré je
len ukazuje na rovnakú vec

100
00:04:26,470 --> 00:04:31,390
že naše zhodou okolností s názvom
dobrovoľník David bol tiež poukázať.

101
00:04:31,390 --> 00:04:35,440
Teraz, keď je ukazovateľ
Nie je null, pretože odvolanie

102
00:04:35,440 --> 00:04:40,350
že null je nejaký špeciálny hliadka hodnota
vymedzuje koniec zoznamu,

103
00:04:40,350 --> 00:04:44,280
takže zatiaľ čo ja nie som ukazuje na
zem ako náš posledný dobrovoľníka

104
00:04:44,280 --> 00:04:47,190
bol, poďme do toho
a vykonajte nasledujúce.

105
00:04:47,190 --> 00:04:51,820
Ak pointer-- a teraz som trochu chcem
robiť to, čo sme robili so študentom

106
00:04:51,820 --> 00:04:57,410
structure-- ak ukazovateľ bodka ďalšie
equals-- skôr, ak je ukazovateľ dot N sa rovná

107
00:04:57,410 --> 00:05:02,290
sa rovná premenná N sa
Argument, že to už prešiel v,

108
00:05:02,290 --> 00:05:05,370
potom chcem ísť dopredu
a hovoria, vráti hodnotu true.

109
00:05:05,370 --> 00:05:11,020
Zistil som, že číslo N vnútro
jeden z uzlov môjho spojovaceho zoznamu.

110
00:05:11,020 --> 00:05:13,500
Ale bodka už
pracuje v tejto súvislosti,

111
00:05:13,500 --> 00:05:17,260
pretože ukazovateľ, PTR, je
skutočne ukazovateľ, adresu,

112
00:05:17,260 --> 00:05:20,632
sme vlastne možné nádherne
použite konečne kus syntaxe

113
00:05:20,632 --> 00:05:22,590
že druh značiek
intuitívne zmysel a vlastne

114
00:05:22,590 --> 00:05:27,870
použiť šípky tu, čo znamená, že ísť od
že adresa na celé číslo tam v.

115
00:05:27,870 --> 00:05:30,160
Takže je to veľmi podobné
duch operátorom bodky,

116
00:05:30,160 --> 00:05:33,860
ale preto, že ukazovateľ nie je ukazovateľ
a nie skutočný struct sám o sebe,

117
00:05:33,860 --> 00:05:35,380
sme práve pomocou šípky.

118
00:05:35,380 --> 00:05:40,620
>> Takže v prípade, že aktuálne uzol, že I je
dočasná premenná, som ukázal na

119
00:05:40,620 --> 00:05:43,060
nie je N, čo chcem robiť?

120
00:05:43,060 --> 00:05:45,910
No, s mojimi ľudských dobrovoľníkoch
že sme tu mali na druhý deň,

121
00:05:45,910 --> 00:05:49,710
keď je moja prvá človek nie je ten, ktorý som
chcú, a možno druhý človek nie je

122
00:05:49,710 --> 00:05:52,660
jediná, ktorú chcem, a tretí, som
je potrebné, aby fyzicky v pohybe.

123
00:05:52,660 --> 00:05:54,690
Ako ako môžem prechádzať zoznamom?

124
00:05:54,690 --> 00:05:57,470
Keď sme mali celý rad tí,
práve urobil ako ja a navyše plus.

125
00:05:57,470 --> 00:06:03,660
Ale v tomto prípade, stačí
robiť ukazovátko, dostane, ukazovateľ, ďalšie.

126
00:06:03,660 --> 00:06:07,580
Inými slovami, ďalšie pole
je rovnako ako všetky ľavých rúk

127
00:06:07,580 --> 00:06:10,880
že naša ľudská dobrovoľníci v pondelok
boli pomocou poukázať na nejakom inom uzla.

128
00:06:10,880 --> 00:06:12,890
Tí, ktorí boli ich ďalší susedia.

129
00:06:12,890 --> 00:06:17,060
>> Takže ak chcem krokovať tohto zoznamu,
Nemôžem jednoducho ja a navyše už,

130
00:06:17,060 --> 00:06:20,120
Namiesto toho musím povedať,
Ja, ukazovateľ, sa deje

131
00:06:20,120 --> 00:06:24,650
rovnať bez ohľadu na ďalšie pole,
Ďalšie pole je, ďalšie pole,

132
00:06:24,650 --> 00:06:28,350
po všetkých tých ľavej ruke
že sme mali na javisku polohovacie

133
00:06:28,350 --> 00:06:30,000
niektorých ďalších hodnôt.

134
00:06:30,000 --> 00:06:32,590
A keď som si cez
že celá iterácie,

135
00:06:32,590 --> 00:06:39,330
a napokon, som narazila null nemať
nájdených N napriek tomu, len som return false.

136
00:06:39,330 --> 00:06:44,100
Takže znova, všetko, čo tu robíme,
podľa obrázku pred chvíľou,

137
00:06:44,100 --> 00:06:47,840
začína poukazom na rokovaní
začiatok zoznamu pravdepodobne.

138
00:06:47,840 --> 00:06:50,970
A potom som skontrolovať, je hodnota
Hľadám rovná deväť?

139
00:06:50,970 --> 00:06:52,650
Ak áno, vráťte som pravda a ja som urobil.

140
00:06:52,650 --> 00:06:56,450
Ak nie, môžem aktualizovať svoju ruku,
AKA ukazovateľ na bod

141
00:06:56,450 --> 00:06:59,540
v mieste budúcej Arrow, a
potom umiestnenie pri budúcom Arrow,

142
00:06:59,540 --> 00:07:00,480
a ďalšie.

143
00:07:00,480 --> 00:07:03,770
Ja som jednoducho prechádza tomto poli.

144
00:07:03,770 --> 00:07:06,010
>> Takže znova, koho to zaujíma?

145
00:07:06,010 --> 00:07:07,861
Rovnako ako to, čo je to zložka pre?

146
00:07:07,861 --> 00:07:10,360
No, pripomenúť, že sme zaviedli
pojem stohu, ktorý

147
00:07:10,360 --> 00:07:15,400
je abstraktné dátový typ, ak je to
nie je vec C, to nie je CS50 vec,

148
00:07:15,400 --> 00:07:19,430
je to abstraktné nápad, táto myšlienka
stohovanie veci na vrchole jedného iný

149
00:07:19,430 --> 00:07:21,820
, Ktoré môžu byť vykonávané v
zväzky rôznych spôsobov.

150
00:07:21,820 --> 00:07:25,600
A jeden spôsob, ako sme navrhovali bol s
poľa, alebo s prepojeného zoznamu.

151
00:07:25,600 --> 00:07:29,570
A ukázalo sa, že kánonicky, je
stack podporuje najmenej dve operácie.

152
00:07:29,570 --> 00:07:32,320
A buzz slová sú tlačiť, aby
tlačiť niečo do zásobníka,

153
00:07:32,320 --> 00:07:34,770
ako nový zásobník v
jedáleň, alebo pop,

154
00:07:34,770 --> 00:07:39,000
čo znamená, že za účelom odstránenia vrchnej
zásobník zo zásobníka v jedálni

155
00:07:39,000 --> 00:07:41,500
hala, a potom možno niektorí
ďalšie operácie rovnako.

156
00:07:41,500 --> 00:07:45,770
Tak ako môžeme definovať štruktúru
že sme teraz volá hromadu?

157
00:07:45,770 --> 00:07:50,020
>> No, máme všetci sú k dispozícii požadované
syntax máme k dispozícii v C. hovorím,

158
00:07:50,020 --> 00:07:53,830
Dajte mi definíciu typu pre
struct vnútri zásobníka,

159
00:07:53,830 --> 00:07:58,030
Ja som chcel povedať, je pole, na
celá rada čísel a potom veľkosť.

160
00:07:58,030 --> 00:08:00,930
Takže inými slovami, keď budem chcieť
na vykonanie tohto v kóde,

161
00:08:00,930 --> 00:08:03,830
nechaj ma ísť, a tak nejako
kresliť, čo to hovorí.

162
00:08:03,830 --> 00:08:06,317
Tak to hovorí, daj mi
štruktúra, ktorá má polia,

163
00:08:06,317 --> 00:08:09,400
a ja neviem, čo je kapacita,
Je to vraj nejaká konštanta, že som

164
00:08:09,400 --> 00:08:10,858
definovaná na inom mieste, a to je v poriadku.

165
00:08:10,858 --> 00:08:15,260
Predpokladajme však, že je to len jeden,
dva, tri, štyri, päť.

166
00:08:15,260 --> 00:08:16,700
Takže kapacita je 5.

167
00:08:16,700 --> 00:08:21,730
Tento prvok vnútri mojej
štruktúra bude volané čísla.

168
00:08:21,730 --> 00:08:24,020
A potom som potrebovať
iné premenné zrejme

169
00:08:24,020 --> 00:08:27,814
volal formát, ktorý pôvodne idem
stanoviť je inicializovaný na nulu.

170
00:08:27,814 --> 00:08:29,730
Pokiaľ nie je nič v
zásobník, veľkosť je nula,

171
00:08:29,730 --> 00:08:31,420
a to je hodnoty odpadkové v číslach.

172
00:08:31,420 --> 00:08:33,450
Nemám potuchy, čo je tam ešte nie.

173
00:08:33,450 --> 00:08:36,059
>> Takže ak chcem, aby sa zasadila
niečo do zásobníka,

174
00:08:36,059 --> 00:08:40,780
Predpokladám, že volanie funkcie Push, a
Hovorím tlačiť 50, ako číslo 50,

175
00:08:40,780 --> 00:08:44,090
kde by ste navrhli
Kreslím to v tomto poli?

176
00:08:44,090 --> 00:08:47,124
K dispozícii je päť rôznych možných odpovedí.

177
00:08:47,124 --> 00:08:48,790
Kam chcete tlačiť číslo 50?

178
00:08:48,790 --> 00:08:51,899
V prípade, že cieľom tu, opäť, zavolajte
funkcie Push, odovzdať argument

179
00:08:51,899 --> 00:08:52,940
50, kde mám dať?

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

181
00:08:55,680 --> 00:08:59,052
Päť possible-- 20% šanca
hádať správne.

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

183
00:08:59,896 --> 00:09:00,740
>> Divákov: Ďaleko vpravo.

184
00:09:00,740 --> 00:09:01,990
>> Reproduktor 1: Úplne vpravo.

185
00:09:01,990 --> 00:09:08,359
Tam je teraz 25% šanca
hádať správne.

186
00:09:08,359 --> 00:09:09,650
Tak, že by vlastne v poriadku.

187
00:09:09,650 --> 00:09:12,770
Podľa konvencie, poviem s radom,
by sme všeobecne začať na ľavej strane,

188
00:09:12,770 --> 00:09:14,519
ale mohli by sme určite
začať na pravej strane.

189
00:09:14,519 --> 00:09:17,478
Takže spojler by tu bolo, že som
pravdepodobne bude čerpať ju na ľavej strane,

190
00:09:17,478 --> 00:09:20,060
rovnako ako v normálnom poli kde
Aj začať chodiť zľava doprava.

191
00:09:20,060 --> 00:09:21,780
Ale ak môžete prevrátiť
aritmetický, v poriadku.

192
00:09:21,780 --> 00:09:23,060
Je to jednoducho nie je konvenčné.

193
00:09:23,060 --> 00:09:24,880
OK, musím urobiť jednu
ďalšia zmena hoci.

194
00:09:24,880 --> 00:09:27,710
Teraz, keď som tlačil niečo
do zásobníka, čo bude ďalej?

195
00:09:27,710 --> 00:09:29,400
>> Dobre, musím zvýšiť veľkosť.

196
00:09:29,400 --> 00:09:32,600
Tak nechaj ma ísť dopredu a len
je aktualizuje, ktorý bol nulový.

197
00:09:32,600 --> 00:09:35,950
A namiesto toho teraz, idem
aby v hodnote jedna.

198
00:09:35,950 --> 00:09:39,460
A teraz, že som tlačiť ďalšie
Číslo do zásobníka, rovnako ako 51.

199
00:09:39,460 --> 00:09:42,680
No, musím urobiť ešte jeden
zmena, ktorá je až do veľkosti dve.

200
00:09:42,680 --> 00:09:46,100
A potom, že som tlačiť ešte jeden
Číslo do zásobníka, ako je 61,

201
00:09:46,100 --> 00:09:52,530
teraz musím aktualizovať veľkosti jeden
čas, a získať hodnotu 3 ako veľkosť.

202
00:09:52,530 --> 00:09:54,690
A teraz, že som zavolať pop.

203
00:09:54,690 --> 00:09:57,250
Teraz pop, podľa konvencie,
neberie argument.

204
00:09:57,250 --> 00:10:00,430
So zásobníkom, celý
bod metafory zásobníka

205
00:10:00,430 --> 00:10:03,450
je to, že nemáte priestor na voľnú úvahu
ísť dostať, že zásobník, môžete všetko, čo urobiť

206
00:10:03,450 --> 00:10:06,330
je pop jeden z najvrchnejšiu
zásobníka, len preto, že.

207
00:10:06,330 --> 00:10:08,010
To je to, čo táto dátová štruktúra robí.

208
00:10:08,010 --> 00:10:12,250
>> Takže touto logikou, keby som
hovoriť pop, čo príde?

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

210
00:10:13,080 --> 00:10:15,402
Takže to, čo naozaj je počítač,
robiť v pamäti?

211
00:10:15,402 --> 00:10:16,610
Čo môj kód musíte urobiť?

212
00:10:16,610 --> 00:10:20,330
Čo by ste navrhli
meníme na obrazovke?

213
00:10:20,330 --> 00:10:23,410
Čo by sa malo zmeniť?

214
00:10:23,410 --> 00:10:24,960
Prosím?

215
00:10:24,960 --> 00:10:26,334
Tak sme sa zbaviť 61.

216
00:10:26,334 --> 00:10:27,500
Tak som si rozhodne urobiť.

217
00:10:27,500 --> 00:10:28,640
A môžem zbaviť 61.

218
00:10:28,640 --> 00:10:30,980
A potom to, čo ostatní
Zmena sa má stať?

219
00:10:30,980 --> 00:10:33,160
Veľkosť má pravdepodobne vrátiť sa do dvoch.

220
00:10:33,160 --> 00:10:34,210
A tak to je v poriadku.

221
00:10:34,210 --> 00:10:36,690
Ale počkajte chvíľu, veľkosť
pred chvíľou bol tri.

222
00:10:36,690 --> 00:10:38,240
Poďme sa len urobiť rýchlu kontrolu zdravý rozum.

223
00:10:38,240 --> 00:10:41,810
Ako to vieme, že sme
chcel sa zbaviť 61?

224
00:10:41,810 --> 00:10:42,760
Vzhľadom k tomu, že sme praskanie.

225
00:10:42,760 --> 00:10:46,450
A tak som túto druhú veľkosť majetku.

226
00:10:46,450 --> 00:10:48,470
>> Počkaj, ja som
spomínal na dve týždeň

227
00:10:48,470 --> 00:10:51,660
keď sme začali hovoriť o
pole, kam toto miesto nula,

228
00:10:51,660 --> 00:10:55,920
toto bolo umiestnenie jedného, ​​toto bolo umiestnenie
dve, to je umiestnenie troch, štyroch,

229
00:10:55,920 --> 00:10:58,460
to vyzerá ako
vzťah medzi veľkosťou

230
00:10:58,460 --> 00:11:02,780
a prvok, že chcem odstrániť
z poľa sa zdá byť len to, čo?

231
00:11:02,780 --> 00:11:05,120
Veľkosť mínus jedna.

232
00:11:05,120 --> 00:11:07,786
A tak to je, ako ako ľudia
vieme, že šesťdesiat jedna je na prvom mieste.

233
00:11:07,786 --> 00:11:09,160
Ako to, že počítač bude vedieť?

234
00:11:09,160 --> 00:11:11,701
Keď váš kód, kde na vás pravdepodobne
chcete urobiť veľkosť mínus jedna,

235
00:11:11,701 --> 00:11:14,950
takže tromi mínus jedna sú dve, a to
znamená, že chceme zbaviť 61.

236
00:11:14,950 --> 00:11:18,000
A potom môžeme skutočne aktualizovať
tak, aby veľkosť veľkosť teraz

237
00:11:18,000 --> 00:11:20,300
ide z troch na púhe dva.

238
00:11:20,300 --> 00:11:24,520
A len preto, aby pedantská, idem
navrhnúť, že som urobil, že jo?

239
00:11:24,520 --> 00:11:27,660
Tie navrhovanej intuitívne
správne by som mal zbaviť 61.

240
00:11:27,660 --> 00:11:30,700
Ale nemám ja druh
nejako zbavili 61?

241
00:11:30,700 --> 00:11:33,790
Ja som skutočne zabudol
že je to vlastne tam.

242
00:11:33,790 --> 00:11:37,680
A myslíte, že späť do PSET4, ak ste dočítali
Článok o forenznej, PDF

243
00:11:37,680 --> 00:11:40,780
že sme mali chlapci čítať, alebo si
bude čítať tento týždeň PSET4.

244
00:11:40,780 --> 00:11:44,300
Pripomeňme, že je to vlastne relevantné k
celá myšlienka počítačovej forenznú.

245
00:11:44,300 --> 00:11:47,820
Čo je počítač zvyčajne robí, je
to jednoducho zabudne, kde je niečo,

246
00:11:47,820 --> 00:11:51,300
ale to nie je ísť a podobne
pokúsiť sa poškriabať, alebo ovládanie

247
00:11:51,300 --> 00:11:54,560
tie kúsky s núl a jednotiek
alebo nejaký iný náhodný vzor

248
00:11:54,560 --> 00:11:56,690
ak vy sám to zámerne.

249
00:11:56,690 --> 00:11:58,930
Takže vaše intuícia bola
Dobre, poďme sa zbaviť 61.

250
00:11:58,930 --> 00:12:00,650
Ale v skutočnosti, my nemusíme obťažovať.

251
00:12:00,650 --> 00:12:04,040
Potrebujeme len zabudnúť, že
je to tam zmenou nášho veľkosť.

252
00:12:04,040 --> 00:12:05,662
>> Teraz je tu problém s zásobníka.

253
00:12:05,662 --> 00:12:07,620
Keby som neustále tlačí veci
do zásobníka, čo je

254
00:12:07,620 --> 00:12:11,167
zrejme bude diať
len v niekoľko okamihov čase?

255
00:12:11,167 --> 00:12:12,500
Budeme chýbať priestor.

256
00:12:12,500 --> 00:12:13,580
A čo budeme robiť?

257
00:12:13,580 --> 00:12:14,680
Sme trochu v háji.

258
00:12:14,680 --> 00:12:19,000
Táto implementácia neumožňuje
us zmeniť veľkosť poľa, pretože použitie

259
00:12:19,000 --> 00:12:21,240
Táto syntax, ak ste
Spomeňte si na dvoch týždňov,

260
00:12:21,240 --> 00:12:23,520
potom, čo ste vyhlásili,
veľkosť poľa,

261
00:12:23,520 --> 00:12:26,780
sme nevideli mechanizmus napriek tomu, kde
môžete zmeniť veľkosť poľa.

262
00:12:26,780 --> 00:12:29,020
A skutočne C nemá túto funkciu.

263
00:12:29,020 --> 00:12:32,524
Keď poviete, daj mi päť
NTHS, im hovoria čísla,

264
00:12:32,524 --> 00:12:33,940
to je všetko, budete si to.

265
00:12:33,940 --> 00:12:38,790
Takže teraz budeme robiť od pondelka, má
schopnosť vyjadrovať riešenie

266
00:12:38,790 --> 00:12:42,480
aj keď, len je potrebné štípnout
definícia nášho stohu

267
00:12:42,480 --> 00:12:46,840
nebyť nejaký pevne poľa,
ale len preto, aby uložiť adresy.

268
00:12:46,840 --> 00:12:47,890
>> Teraz, prečo je to?

269
00:12:47,890 --> 00:12:51,690
Teraz len musíme byť pohodlné s
skutočnosť, že keď môj program beží,

270
00:12:51,690 --> 00:12:53,730
Ja pravdepodobne bude
sa opýtať človeka,

271
00:12:53,730 --> 00:12:55,110
koľko čísel uložiť?

272
00:12:55,110 --> 00:12:56,776
Takže vstup má prísť odniekiaľ.

273
00:12:56,776 --> 00:12:59,140
Ale akonáhle ja viem, že
číslo, potom môžem len

274
00:12:59,140 --> 00:13:02,470
použiť to, čo funkciu, čím sa získa
mi kus pamäte?

275
00:13:02,470 --> 00:13:03,580
Môžem použiť malloc.

276
00:13:03,580 --> 00:13:06,710
A môžem povedať, ľubovoľný počet
bajtov Chcem späť na tieto NTHS.

277
00:13:06,710 --> 00:13:10,910
A všetko, čo mám skladovať v číslach
variabilný tu vnútri tohto struct

278
00:13:10,910 --> 00:13:13,480
by malo byť to, čo?

279
00:13:13,480 --> 00:13:18,440
Čo je to vlastne ide do
Čísla v tomto prípade?

280
00:13:18,440 --> 00:13:21,300
Jo, ukazovateľ na prvý
bajt tohto kusu pamäti,

281
00:13:21,300 --> 00:13:24,940
alebo viac špecificky, adresa
z prvej z týchto bajtov.

282
00:13:24,940 --> 00:13:27,300
Nezáleží na tom, či je to jedno
byte alebo miliarda bajtov,

283
00:13:27,300 --> 00:13:28,890
Len musím starať o prvý.

284
00:13:28,890 --> 00:13:31,530
Vzhľadom k tomu, čo malloc záruky a
môj operačný systém zaručuje,

285
00:13:31,530 --> 00:13:34,170
je to, že kus pamäte I
si, že to bude byť súvislé.

286
00:13:34,170 --> 00:13:35,378
Je tu nebude medzery.

287
00:13:35,378 --> 00:13:38,576
Takže ak som požiadal o 50
bajtov alebo 1000 bajtov,

288
00:13:38,576 --> 00:13:40,450
oni sú všetci bude
chrbtom k sebe k sebe.

289
00:13:40,450 --> 00:13:44,500
A tak dlho, ako si spomínam, ako veľký, ako
moc som požiadal o, všetko, čo potrebujem vedieť

290
00:13:44,500 --> 00:13:46,230
Je to prvá takáto adresa.

291
00:13:46,230 --> 00:13:48,660
>> Takže teraz máme možnosť v kóde.

292
00:13:48,660 --> 00:13:51,280
Hoci, že to bude trvať nás
viac času písať toto hore,

293
00:13:51,280 --> 00:13:55,900
sme teraz mohli prerozdeliť, že pamäť
Len uloženie inú adresu tu

294
00:13:55,900 --> 00:13:59,060
Ak chceme väčší, alebo dokonca
menšie kus pamäte.

295
00:13:59,060 --> 00:14:00,170
Takže tu na kompromis.

296
00:14:00,170 --> 00:14:01,360
Teraz sme si dynamiku.

297
00:14:01,360 --> 00:14:03,350
Stále máme
contiguousness som tvrdil.

298
00:14:03,350 --> 00:14:05,881
Vzhľadom k tomu, malloc bude nám
susediace kus pamäte.

299
00:14:05,881 --> 00:14:08,630
Ale toto je bude bolesť v
krk pre nás, programátor,

300
00:14:08,630 --> 00:14:09,770
skutočne kód hore.

301
00:14:09,770 --> 00:14:10,730
Je to jednoducho viac práce.

302
00:14:10,730 --> 00:14:13,930
Potrebujeme kód podobný tomu, čo som bol
búchanie sa pred chvíľou.

303
00:14:13,930 --> 00:14:16,120
Veľmi realizovateľné, ale pridáva zložitosť.

304
00:14:16,120 --> 00:14:19,520
A tak developer čas, programátor
Doba je ďalším zdrojom

305
00:14:19,520 --> 00:14:22,520
že by sme mohli musieť stráviť
nejaký čas, aby sa nové funkcie.

306
00:14:22,520 --> 00:14:24,020
A potom samozrejme je tu front.

307
00:14:24,020 --> 00:14:26,227
Nebudeme ísť do toho
človek v veľa detaile.

308
00:14:26,227 --> 00:14:27,560
Ale je to veľmi podobné duchu.

309
00:14:27,560 --> 00:14:31,220
Mohol by som implementovať frontu, a
jej zodpovedajúce operácie,

310
00:14:31,220 --> 00:14:35,660
Pridať do zoznamu alebo dequeue, ako je pridať alebo odstrániť,
je to len milovník spôsob, ako povedať to,

311
00:14:35,660 --> 00:14:38,100
Pridať do zoznamu alebo dequeue takto.

312
00:14:38,100 --> 00:14:41,170
Môžem len dať sám struct
má celý rad celú radu, že opäť,

313
00:14:41,170 --> 00:14:44,000
má to znova veľkosť,
ale prečo teraz potrebujem

314
00:14:44,000 --> 00:14:46,940
sledovať predné fronty?

315
00:14:46,940 --> 00:14:50,630
Nepotreboval som vedieť
predné môjho stacku.

316
00:14:50,630 --> 00:14:53,570
No, keď som znovu pre
queue-- Poďme sa len ťažko

317
00:14:53,570 --> 00:14:57,870
kódovať to ako mať ako päť
celé čísla v potenciálne tu.

318
00:14:57,870 --> 00:15:00,940
Takže to je nula, jedna, dva, tri, štyri.

319
00:15:00,940 --> 00:15:03,430
To bude
znovu zavolal čísla.

320
00:15:03,430 --> 00:15:06,940
A to sa bude nazývať veľkosť.

321
00:15:06,940 --> 00:15:10,056
>> Prečo nie je dostačujúce
mať len veľkosť?

322
00:15:10,056 --> 00:15:11,680
Dobre, poďme stlačte tie isté čísla na.

323
00:15:11,680 --> 00:15:14,220
Tak som pushed-- I enqueued, alebo tlačil.

324
00:15:14,220 --> 00:15:20,150
Teraz budem Zaradí 50, a potom
51, a potom 61, a dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Tak to je Enqueue.

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

327
00:15:23,176 --> 00:15:25,050
A to vyzerá totožne
do komína tak ďaleko,

328
00:15:25,050 --> 00:15:27,190
okrem Ja potrebné, aby sa jednu zmenu.

329
00:15:27,190 --> 00:15:33,680
Musím aktualizovať tejto veľkosti, takže idem
od nuly do jedného na dva až tri teraz.

330
00:15:33,680 --> 00:15:35,760
Ako môžem dequeue?

331
00:15:35,760 --> 00:15:36,890
Čo sa stane s dequeue?

332
00:15:36,890 --> 00:15:41,950
Kto by mal prísť z tohto zoznamu ako prvý
ak je to linka na Apple Store?

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

334
00:15:42,780 --> 00:15:44,700
Takže je to trochu zložitejšie tentoraz.

335
00:15:44,700 --> 00:15:47,880
Vzhľadom k tomu, naposledy to bol výborný
ľahké proste veľkosť mínus jedna,

336
00:15:47,880 --> 00:15:51,440
Aj dostať na konci svojho poľa účinne
kde čísla sú, odoberie 61.

337
00:15:51,440 --> 00:15:52,920
Ale ja nechcem, aby odstrániť 61.

338
00:15:52,920 --> 00:15:55,030
Chcem sa 50, ktorý
Bol tam v 5:00 hodín

339
00:15:55,030 --> 00:15:56,790
na line up pre
Nový iPhone alebo ktovie čo ešte.

340
00:15:56,790 --> 00:16:01,200
A tak, ako sa zbaviť 50, I
Nemôžete jednoducho to urobiť, nie?

341
00:16:01,200 --> 00:16:02,547
Môžem vyškrtnúť 50.

342
00:16:02,547 --> 00:16:04,380
Ale my sme povedali len
nemusí byť tak análny

343
00:16:04,380 --> 00:16:06,330
ako na zelenej lúke, alebo skryť dáta.

344
00:16:06,330 --> 00:16:08,090
Môžeme len zabudol, kde to je.

345
00:16:08,090 --> 00:16:12,330
>> Ale keď zmením veľkosť teraz
dva, je to dostatočné informácie

346
00:16:12,330 --> 00:16:15,711
vedieť, čo sa deje v mojom fronte?

347
00:16:15,711 --> 00:16:16,680
Ani nie.

348
00:16:16,680 --> 00:16:19,830
Rovnako ako moja veľkosť je dva, ale
kde sa front začína,

349
00:16:19,830 --> 00:16:22,980
najmä pokiaľ Stále mám
tá rovnaké čísla v pamäti.

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

351
00:16:24,260 --> 00:16:27,090
Tak som treba mať na pamäti,
Teraz, keď je predné.

352
00:16:27,090 --> 00:16:29,630
A tak, ako som navrhla hore
tam budeme práve volal

353
00:16:29,630 --> 00:16:33,729
Nth predné, ktorých pôvodná
hodnota by mala byť čo?

354
00:16:33,729 --> 00:16:35,270
Zero, len začiatok zoznamu.

355
00:16:35,270 --> 00:16:40,876
Ale teraz okrem dekrementování
veľkosť, práve sme zvýšiť predné.

356
00:16:40,876 --> 00:16:42,000
A teraz je tu ďalší problém.

357
00:16:42,000 --> 00:16:43,030
Takže akonáhle som sa ísť ďalej.

358
00:16:43,030 --> 00:16:47,520
Predpokladajme, že sa jedná o počet
ako je 121, 124, a potom sa, sakra,

359
00:16:47,520 --> 00:16:48,610
Som z vesmíru.

360
00:16:48,610 --> 00:16:50,390
Ale počkajte, ja nie som.

361
00:16:50,390 --> 00:16:55,630
Takže v tomto bode príbehu,
Predpokladajme, že veľkosť je jeden, dva,

362
00:16:55,630 --> 00:17:00,370
tri, štyri, tak predpokladať, že
veľkosť je štyri, predné je jedna,

363
00:17:00,370 --> 00:17:01,621
takže 51 je na prednej strane.

364
00:17:01,621 --> 00:17:04,329
Chcem dať iné číslo tu,
ale, sakra, ja som z vesmíru.

365
00:17:04,329 --> 00:17:06,710
Ale ja nie som, že jo?

366
00:17:06,710 --> 00:17:11,192
Tam, kde som mohol dať nejaké
ďalšie hodnoty, ako je 171?

367
00:17:11,192 --> 00:17:13,400
Jo, mohol by som len tak
vrátiť sa tam, že jo?

368
00:17:13,400 --> 00:17:18,161
A potom vyškrtnúť na 50, alebo
jednoducho ho prepísať s 171.

369
00:17:18,161 --> 00:17:20,410
A ak ste premýšľal, prečo
náš počet sa dostal tak náhodný,

370
00:17:20,410 --> 00:17:24,150
Títo sú obyčajne prijatá počítač
prírodovedné predmety na Harvarde po CS50.

371
00:17:24,150 --> 00:17:27,510
Ale to bol dobrý optimalizácie,
pretože teraz som to plytvanie miestom.

372
00:17:27,510 --> 00:17:30,750
Stále mám na pamäti,
ako veľká tá vec je totálna.

373
00:17:30,750 --> 00:17:31,500
Je to celkom piatich.

374
00:17:31,500 --> 00:17:33,375
Pretože nechcem, aby
začať prepisovanie 51.

375
00:17:33,375 --> 00:17:36,260
Takže teraz som ešte z vesmíru,
takže rovnaký problém ako predtým.

376
00:17:36,260 --> 00:17:39,140
Ale môžete vidieť, ako teraz
v kóde, budete pravdepodobne

377
00:17:39,140 --> 00:17:41,910
musieť trochu písať viac
zložitosť, aby sa to stalo.

378
00:17:41,910 --> 00:17:44,510
A v skutočnosti to, čo operátor
v C pravdepodobne umožňuje

379
00:17:44,510 --> 00:17:48,110
budete magicky urobiť kruhovitosť?

380
00:17:48,110 --> 00:17:50,160
Jo, operátor modulo,
znak percenta.

381
00:17:50,160 --> 00:17:53,160
Takže to, čo je paráda asi frontu,
aj keď sme udržať kreslenie poľa

382
00:17:53,160 --> 00:17:56,520
ako tieto, ako rovných čiar, ak ste
trochu premýšľať o tom, ako zakrivenie

383
00:17:56,520 --> 00:18:00,341
okolo ako kruh, potom stačí
intuitívne to trochu funguje mentálne

384
00:18:00,341 --> 00:18:01,590
Myslím si, že trochu viac čisto.

385
00:18:01,590 --> 00:18:05,190
Tie by sa ešte musí zaviesť
že mentálne model v kóde.

386
00:18:05,190 --> 00:18:07,550
Takže nie je tak ťažké,
nakoniec, implementovať,

387
00:18:07,550 --> 00:18:12,430
ale stále stratiť size-- trochu,
schopnosť zmeniť veľkosť, ak to urobíme.

388
00:18:12,430 --> 00:18:15,310
>> Musíme sa zbaviť poľa, my
ho nahradiť jediným ukazovateľom,

389
00:18:15,310 --> 00:18:20,010
a potom sa niekde v mojom kóde mám
Príjem volania, akú funkciu skutočne vytvoriť

390
00:18:20,010 --> 00:18:23,720
pole volaných čísel?

391
00:18:23,720 --> 00:18:26,190
Malloc, alebo nejaký podobný
funkcie, presne tak.

392
00:18:26,190 --> 00:18:30,481
Akékoľvek otázky týkajúce komínov alebo frontoch.

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

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

395
00:18:33,657 --> 00:18:34,240
Dobrá otázka.

396
00:18:34,240 --> 00:18:35,830
Čo modulo by ste použili tu.

397
00:18:35,830 --> 00:18:38,520
Takže všeobecne, pri použití
mod, mali by ste to urobiť

398
00:18:38,520 --> 00:18:40,620
s veľkosťou
Celá štruktúra dát.

399
00:18:40,620 --> 00:18:44,120
Takže niečo ako päť alebo kapacity, ak je
to je konštantná, je pravdepodobne zapojený.

400
00:18:44,120 --> 00:18:47,100
Ale len to, modulo päť
asi nie je dostačujúce,

401
00:18:47,100 --> 00:18:51,380
pretože musíme vedieť my
zábal okolo tu alebo tu alebo tu.

402
00:18:51,380 --> 00:18:54,160
Takže vy ste pravdepodobne tiež
bude chcieť zapojiť

403
00:18:54,160 --> 00:18:57,220
veľkosť veci, alebo
predné premenné rovnako.

404
00:18:57,220 --> 00:19:00,140
Takže je to práve tento pomerne
prostý aritmetický výraz,

405
00:19:00,140 --> 00:19:02,000
ale modulo bude kľúčovou zložkou.

406
00:19:02,000 --> 00:19:03,330
>> Tak krátky film ak chcete.

407
00:19:03,330 --> 00:19:05,780
Animácie, že niektoré
ľudia na inej vysokej škole

408
00:19:05,780 --> 00:19:08,060
dal dohromady, že máme
prispôsobené pre túto diskusiu.

409
00:19:08,060 --> 00:19:12,630
To zahŕňa Jack Učenie
fakty o frontoch a štatistiky.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Kedysi dávno,
tam bol chlapík menom Jack.

412
00:19:21,890 --> 00:19:25,330
Keď došlo k tomu, že priatelia,
Jack nemal talent.

413
00:19:25,330 --> 00:19:28,220
Takže Jack šiel hovoriť s
najpopulárnejšie chlapec vedel.

414
00:19:28,220 --> 00:19:30,920
On išiel do Lou a spýtal sa, čo mám robiť?

415
00:19:30,920 --> 00:19:33,400
Lou videl, že jeho priateľ
bol naozaj zúfalý.

416
00:19:33,400 --> 00:19:36,050
No, on začal, len
pozrite sa, ako ste oblečený.

417
00:19:36,050 --> 00:19:38,680
Nemáte žiadne šaty
s iným pohľadom?

418
00:19:38,680 --> 00:19:39,660
Áno, povedal Jack.

419
00:19:39,660 --> 00:19:40,840
Som si istý, áno.

420
00:19:40,840 --> 00:19:43,320
Poď do môjho domu a
Ukážem vám ich.

421
00:19:43,320 --> 00:19:44,550
A tak išli preč, aby Jack.

422
00:19:44,550 --> 00:19:47,520
A Jack ukázal na políčko lou
kde on držal všetky svoje košele,

423
00:19:47,520 --> 00:19:49,260
a jeho nohavice, a jeho ponožky.

424
00:19:49,260 --> 00:19:52,290
Povedal Lou, vidím, že máte
Všetky vaše oblečenie v hromadu.

425
00:19:52,290 --> 00:19:54,870
Prečo ste nosiť nejaké
iní raz za čas?

426
00:19:54,870 --> 00:19:58,020
>> Povedal Jack, dobre, keď som
odstrániť oblečenie a ponožky,

427
00:19:58,020 --> 00:20:00,780
Aj umyť je a dal
je preč v krabici.

428
00:20:00,780 --> 00:20:03,210
Potom príde budúci
ráno, a ja si hop.

429
00:20:03,210 --> 00:20:06,380
Chodím do boxu a získať
moje oblečenie z vrcholu.

430
00:20:06,380 --> 00:20:09,070
Lou rýchlo si uvedomil,
problém s Jackom.

431
00:20:09,070 --> 00:20:12,080
Stále oblečenie, CD,
a knihy v zásobníku.

432
00:20:12,080 --> 00:20:14,420
Keď sa dostal na
niečo na čítanie alebo opotrebenia,

433
00:20:14,420 --> 00:20:17,100
že by si vybrať horný knihu alebo spodná bielizeň.

434
00:20:17,100 --> 00:20:19,500
Potom, keď bol hotový,
by dal to späť.

435
00:20:19,500 --> 00:20:21,970
Back to pôjde, na vrchole zásobníka.

436
00:20:21,970 --> 00:20:24,460
Viem, že riešenie,
povedal víťazný Loud.

437
00:20:24,460 --> 00:20:27,090
Musíte sa naučiť
začať používať front.

438
00:20:27,090 --> 00:20:29,870
Lou vzal Jackovej šaty a
zavesil ich do skrine.

439
00:20:29,870 --> 00:20:32,710
A keď vyprázdnil
krabice, proste hodil.

440
00:20:32,710 --> 00:20:36,500
>> Potom povedal, teraz Jack, na konci roka
deň, dať svoje oblečenie na ľavej strane

441
00:20:36,500 --> 00:20:37,990
keď dal je preč.

442
00:20:37,990 --> 00:20:41,300
Potom sa zajtra ráno, keď vás
vidieť slnko, dostať svoje šaty

443
00:20:41,300 --> 00:20:43,440
Na pravej strane, od konca riadku.

444
00:20:43,440 --> 00:20:44,880
Copak nevidíš? povedal Lou.

445
00:20:44,880 --> 00:20:46,370
Bude to tak pekné.

446
00:20:46,370 --> 00:20:49,770
Budete nosiť všetko raz
Než budete nosiť niečo dvakrát.

447
00:20:49,770 --> 00:20:52,670
A so všetkým v frontoch
v jeho skrini a policou,

448
00:20:52,670 --> 00:20:55,160
Jack začal cítiť
celkom istý sám sebou.

449
00:20:55,160 --> 00:20:59,720
Všetky vďaka Lou a
Jeho úžasné front.

450
00:20:59,720 --> 00:21:01,220
Reproduktor 1: Dobre, to je rozkošný.

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

452
00:21:05,920 --> 00:21:10,080
Takže to, čo sa v skutočnosti deje
Na pod pokrievku teraz?

453
00:21:10,080 --> 00:21:12,370
Že máme ukazovatele,
že máme malloc,

454
00:21:12,370 --> 00:21:15,680
že máme schopnosť vytvárať
kusy pamäte pre seba

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

456
00:21:16,344 --> 00:21:18,510
Takže toto je obrázok sme
zazrel len druhý deň.

457
00:21:18,510 --> 00:21:21,180
My sme naozaj prebývať
na to, ale tento obrázok

458
00:21:21,180 --> 00:21:24,180
má sa deje pod
odsávač niekoľko týždňov.

459
00:21:24,180 --> 00:21:27,050
A tak to znamená, len
obdĺžnik, ktorý sme vyvodiť,

460
00:21:27,050 --> 00:21:28,180
pamäte počítača.

461
00:21:28,180 --> 00:21:31,850
A možno váš počítač, alebo CS50
ID, má gigabajt pamäte alebo RAM

462
00:21:31,850 --> 00:21:33,050
alebo dva gigabajty alebo štyri.

463
00:21:33,050 --> 00:21:34,450
Je to naozaj nezáleží.

464
00:21:34,450 --> 00:21:37,240
Váš operačný systém
Windows alebo Mac OS či Linux,

465
00:21:37,240 --> 00:21:41,120
v podstate umožňuje program
myslieť si, že má prístup

466
00:21:41,120 --> 00:21:42,982
na celý rozsah
pamäť počítača,

467
00:21:42,982 --> 00:21:45,440
aj keď by ste mohli byť spustený
viac programov naraz.

468
00:21:45,440 --> 00:21:46,990
Takže v skutočnosti, že v skutočnosti nefunguje.

469
00:21:46,990 --> 00:21:49,448
Ale je to trochu ilúzia
venovať všetky svoje programy.

470
00:21:49,448 --> 00:21:53,110
Takže ak ste mali dva koncerty RAM, toto
je, ako sa počítač môže myslieť na to.

471
00:21:53,110 --> 00:21:57,110
>> Teraz náhodne, jeden z nich
veci, jeden z týchto segmentov pamäti,

472
00:21:57,110 --> 00:21:58,350
sa nazýva zásobník.

473
00:21:58,350 --> 00:22:01,680
A skutočne kedykoľvek
tak ďaleko v písaní kódu

474
00:22:01,680 --> 00:22:05,900
že ste volal
funkcie, napríklad main.

475
00:22:05,900 --> 00:22:08,410
Pripomeňme si, že kedykoľvek som
Pamäť Drawn počítače,

476
00:22:08,410 --> 00:22:10,640
Vždy som tomu nejako
polovica z obdĺžnika tu

477
00:22:10,640 --> 00:22:12,520
a neobťažujú hovoriť
o tom, čo je vyššie.

478
00:22:12,520 --> 00:22:15,980
Pretože keď je hlavná volal, tvrdím,
že ste si to plátok pamäti

479
00:22:15,980 --> 00:22:16,970
že ide sem dole.

480
00:22:16,970 --> 00:22:20,650
A ak hlavná volal funkcie
ako odkladací priestor, dobre odkladacie ide tu.

481
00:22:20,650 --> 00:22:23,720
A ukázalo sa, že je to
kde je to končí.

482
00:22:23,720 --> 00:22:26,277
Na takzvaný stoh
vnútornej pamäte vášho počítača.

483
00:22:26,277 --> 00:22:28,360
Teraz sa na konci dňa,
to je len adresy.

484
00:22:28,360 --> 00:22:30,680
Je to ako bajt nula,
Byte jedného, ​​byte 2000000000.

485
00:22:30,680 --> 00:22:33,130
Ale či si myslíte, že o tom
ako je obdĺžnikový objekt,

486
00:22:33,130 --> 00:22:35,130
všetko robíme každý
Doba hovoríme funkcie

487
00:22:35,130 --> 00:22:37,180
vrstvenie nový rez pamäte.

488
00:22:37,180 --> 00:22:41,700
Dávame túto funkciu plátok
zo svojej vlastnej pamäte pre prácu s.

489
00:22:41,700 --> 00:22:44,490
>> A teraz pripomínajú, že je to dôležité.

490
00:22:44,490 --> 00:22:46,400
Vzhľadom k tomu, keby sme sa
niečo ako odkladací priestor

491
00:22:46,400 --> 00:22:51,610
a dve lokálne premenné, ako je A a B a
zmeníme tieto hodnoty z jednej a dvoch

492
00:22:51,610 --> 00:22:55,130
na dva a jeden, odvolanie
že keď sa vráti swapu,

493
00:22:55,130 --> 00:22:58,330
je to, ako by tento plátok
pamäte je jednoducho preč.

494
00:22:58,330 --> 00:23:00,080
V skutočnosti, je to stále
tam forenzných.

495
00:23:00,080 --> 00:23:01,940
A niečo je ešte v skutočnosti tam.

496
00:23:01,940 --> 00:23:05,410
Ale koncepčne, je to, ako
aj keď je to úplne preč.

497
00:23:05,410 --> 00:23:10,910
A tak hlavné nepozná žiadnu z prác
ktorá bola vykonaná v tejto funkcii odkladacieho

498
00:23:10,910 --> 00:23:14,890
ak je to vlastne prešiel v tých
Argumenty ukazovateľom alebo odkazom.

499
00:23:14,890 --> 00:23:17,790
Teraz, základné riešenie
k tomuto problému s swapu

500
00:23:17,790 --> 00:23:19,970
je okolo veci podľa adresy.

501
00:23:19,970 --> 00:23:23,250
Ale ukazuje sa, taky, čo je
sa deje nad túto časť

502
00:23:23,250 --> 00:23:26,330
obdĺžnika celú dobu je
Ešte je tu viac pamäte tam hore.

503
00:23:26,330 --> 00:23:28,790
A keď dynamicky
alokovať pamäť,

504
00:23:28,790 --> 00:23:32,020
či už je to vo vnútri getString, ktorý
sme robili pre vás v CS50

505
00:23:32,020 --> 00:23:34,710
knižnica, alebo či vy
zavolať a opýtať sa malloc

506
00:23:34,710 --> 00:23:37,950
operačný systém pre kus
pamäť, nepochádza zo zásobníka.

507
00:23:37,950 --> 00:23:40,960
To pochádza z iného miesta
v pamäti počítača

508
00:23:40,960 --> 00:23:42,220
Tomu sa hovorí haldy.

509
00:23:42,220 --> 00:23:43,430
A to nie je nič iné.

510
00:23:43,430 --> 00:23:44,285
Je to rovnaké RAM.

511
00:23:44,285 --> 00:23:45,160
Je to rovnaká pamäť.

512
00:23:45,160 --> 00:23:49,080
Je to len RAM, ktorý sa deje
tam miesto tu dole.

513
00:23:49,080 --> 00:23:50,750
>> A tak čo to znamená?

514
00:23:50,750 --> 00:23:53,650
No, ak má počítač
konečné množstvo pamäte

515
00:23:53,650 --> 00:23:57,450
a zásobník sa vyrastal, takže
hovoriť, a haldy, podľa

516
00:23:57,450 --> 00:23:59,349
k tejto šípky, rastie nadol.

517
00:23:59,349 --> 00:24:01,140
Inými slovami, každý
Čas hovoru malloc,

518
00:24:01,140 --> 00:24:03,430
ste daná plátok
pamäte zhora,

519
00:24:03,430 --> 00:24:06,630
potom možno o niečo nižšia, a potom trochu
nižšia, zakaždým, keď budete volať malloc,

520
00:24:06,630 --> 00:24:10,100
haldy, je to použitie,
je druh rastie,

521
00:24:10,100 --> 00:24:11,950
rastie bližšie a bližšie k čomu?

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

523
00:24:13,382 --> 00:24:14,840
Takže to zdá ako dobrý nápad?

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

525
00:24:18,420 --> 00:24:22,140
Mám na mysli, ak to nie je naozaj jasné,
čo iného môžete robiť, keď len

526
00:24:22,140 --> 00:24:23,910
majú obmedzené množstvo pamäte.

527
00:24:23,910 --> 00:24:25,200
Ale to je určite zlé.

528
00:24:25,200 --> 00:24:27,920
Tieto dva šípy sú na
Rýchlokurz jeden o druhého.

529
00:24:27,920 --> 00:24:31,930
>> A ukázalo sa, že zlý človek, ľudí, ktorí
sú veľmi dobré s programovaním,

530
00:24:31,930 --> 00:24:36,140
a snaží sa preniknúť do počítačov,
môžete využiť túto skutočnosť.

531
00:24:36,140 --> 00:24:38,290
V skutočnosti, uvažujme
trochu úryvok.

532
00:24:38,290 --> 00:24:41,350
Takže toto je príklad si môžete prečítať
o podrobnejšie na Wikipédii.

533
00:24:41,350 --> 00:24:43,100
Budeme bod, ktorý u
článku, ak zvedavý.

534
00:24:43,100 --> 00:24:45,650
Ale je tu útok všeobecne
známy ako pretečeniu vyrovnávacej pamäti, že

535
00:24:45,650 --> 00:24:49,570
existuje tak dlho, ako u ľudí
mali schopnosť manipulovať

536
00:24:49,570 --> 00:24:53,120
pamäť počítača, a to najmä v C.
Tak to je veľmi ľubovoľný program

537
00:24:53,120 --> 00:24:55,130
ale poďme ju prečítať zdola nahor.

538
00:24:55,130 --> 00:24:57,650
Hlavná do argc char hviezdy argv.

539
00:24:57,650 --> 00:24:59,830
Takže je to program, ktorý berie
argumenty príkazového riadku.

540
00:24:59,830 --> 00:25:03,620
A všetky hlavné robí zrejme je výzva
funkcie, hovoria F pre jednoduchosť.

541
00:25:03,620 --> 00:25:04,610
A to prejde v čom?

542
00:25:04,610 --> 00:25:05,490
Argv jedného.

543
00:25:05,490 --> 00:25:09,320
Tak to prechádza do F čokoľvek
slovo je, že používateľ zadaný

544
00:25:09,320 --> 00:25:11,500
do príkazového riadku po vyrobení
Názov programu vôbec.

545
00:25:11,500 --> 00:25:15,730
Takže rovnako ako Caesar alebo Vigener, ktorý
môžete pripomenúť robíte s argv.

546
00:25:15,730 --> 00:25:16,680
>> Takže to, čo je F?

547
00:25:16,680 --> 00:25:19,760
F sa v reťazci
ako jeho jediný argument

548
00:25:19,760 --> 00:25:22,100
AKA char hviezda, rovnaká
vec, ako reťazec.

549
00:25:22,100 --> 00:25:24,920
A je to len svojvoľne
bar v tomto príklade.

550
00:25:24,920 --> 00:25:27,710
A potom char c 12,
len v Laicky povedané,

551
00:25:27,710 --> 00:25:31,750
čo je char c držiak 12 robí pre nás?

552
00:25:31,750 --> 00:25:33,440
Čo to robí?

553
00:25:33,440 --> 00:25:36,490
Prideľovanie pamäte, konkrétne
12 bytov pre 12 znakov.

554
00:25:36,490 --> 00:25:36,990
Presne tak.

555
00:25:36,990 --> 00:25:40,000
A potom posledný riadok, zamiešať a
kopírovanie, pravdepodobne ste ešte nevideli.

556
00:25:40,000 --> 00:25:43,360
To je reťazec kópia
funkcie, ktorej účel života

557
00:25:43,360 --> 00:25:48,160
je skopírovať svoj druhý argument
do prvý argument,

558
00:25:48,160 --> 00:25:51,190
ale iba do
určitý počet bajtov.

559
00:25:51,190 --> 00:25:53,860
Takže tretí argument hovorí,
koľko bajtov by ste mali kopírovať?

560
00:25:53,860 --> 00:25:56,720
Dĺžka tyče,
bez ohľadu na užívateľ zadal.

561
00:25:56,720 --> 00:25:59,320
A obsahu
bar, tento reťazec, sú

562
00:25:59,320 --> 00:26:02,330
skopírované do pamäte ukázal na pri ° C

563
00:26:02,330 --> 00:26:04,060
>> Takže to vyzerá trochu hlúpe, a to je.

564
00:26:04,060 --> 00:26:06,300
Je to neprirodzený príklad,
ale je to zástupca

565
00:26:06,300 --> 00:26:10,100
triedy vektorov útoku,
spôsob, ako útočiť program.

566
00:26:10,100 --> 00:26:15,050
Všetko je v poriadku a dobré, ak užívateľ
Typy v slovách, ktorá je 11 znakov

567
00:26:15,050 --> 00:26:18,040
alebo menej, plus spätné lomítko nula.

568
00:26:18,040 --> 00:26:22,830
Čo keď používateľ zadá vo viac ako
11 alebo 12 alebo 20 alebo 50 znakov?

569
00:26:22,830 --> 00:26:25,090
Čo je tento program bude robiť?

570
00:26:25,090 --> 00:26:29,360
Potenciálne seg chyba. Ide to
slepo kopírovať všetko, čo v bare hore

571
00:26:29,360 --> 00:26:31,750
k jeho dĺžke, čo je
doslova všetko, čo v bare,

572
00:26:31,750 --> 00:26:36,307
do adresného ukázal na C. Ale ° C
má len preventívne uvedený ako 12 bajtov.

573
00:26:36,307 --> 00:26:37,640
Ale nie je ďalšiu kontrolu.

574
00:26:37,640 --> 00:26:38,700
Ak nie je podmienkach.

575
00:26:38,700 --> 00:26:40,580
Neexistuje kontrola tu žiadna chyba.

576
00:26:40,580 --> 00:26:43,270
>> A tak to, čo je tento program
chystá urobiť, je len slepo

577
00:26:43,270 --> 00:26:45,750
kopírovať jednu vec na druhú.

578
00:26:45,750 --> 00:26:47,880
A tak, keď čerpáme to
ako obrázok, tu je

579
00:26:47,880 --> 00:26:49,860
len trieska pamäťového priestoru.

580
00:26:49,860 --> 00:26:53,470
Tak si všimnúť na dne, sme
majú lokálne premenné bar.

581
00:26:53,470 --> 00:26:57,330
Tak, aby ukazovateľ, ktorý to bude store--
skôr to, že miestne argumentu, ktorý je

582
00:26:57,330 --> 00:26:58,672
bude ukladať reťazec bar.

583
00:26:58,672 --> 00:27:00,380
A potom si všimnúť len
nad ňou v stohu,

584
00:27:00,380 --> 00:27:02,505
pretože zakaždým, keď sa pýtate
pre pamäť na zásobníku,

585
00:27:02,505 --> 00:27:04,310
to ide trochu
nad ňou obrazovo,

586
00:27:04,310 --> 00:27:06,270
Všimnite si, že máme 12 bajtov tam.

587
00:27:06,270 --> 00:27:10,690
V ľavom hornom z nich je C držiak nula a
vpravo dole nich je C držiak 11.

588
00:27:10,690 --> 00:27:12,870
To je len, ako sa počítače
chystá položiť ju von.

589
00:27:12,870 --> 00:27:18,300
Takže len intuitívne, pokiaľ bar má viac
ako 12 znakov celkom, vrátane

590
00:27:18,300 --> 00:27:25,790
spätné lomítko nula, kde je
12 alebo C držiak 12 ísť?

591
00:27:25,790 --> 00:27:28,440
Alebo skôr, kde je 12.
znak alebo 13. znak,

592
00:27:28,440 --> 00:27:30,900
sté postava ísť
skončiť na obrázku?

593
00:27:30,900 --> 00:27:33,400
Nad alebo pod?

594
00:27:33,400 --> 00:27:36,300
>> Správne, pretože aj keď
stoh sám rastie nahor,

595
00:27:36,300 --> 00:27:39,590
akonáhle ste dal veci do
to, že z konštrukčných dôvodov,

596
00:27:39,590 --> 00:27:41,294
kladie pamäť od zhora nadol.

597
00:27:41,294 --> 00:27:44,460
Takže ak máte viac ako 12 bajtov,
budete začať prepísať bar.

598
00:27:44,460 --> 00:27:47,280
Tak to je chyba, ale je to
nie je naozaj veľký problém.

599
00:27:47,280 --> 00:27:51,130
Ale je to veľký problém, pretože tam je
viac vecí sa deje v pamäti.

600
00:27:51,130 --> 00:27:53,074
Takže tu je návod, ako by sme mohli
dal ahoj, aby bolo jasné.

601
00:27:53,074 --> 00:27:54,490
Ak som napísal v ahoj na príkazovom riadku.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash nula, končí v rámci
tieto 12 bajtov, a my sme výborný bezpečia.

603
00:27:59,330 --> 00:28:00,330
Všetko je v poriadku.

604
00:28:00,330 --> 00:28:03,020
Ale ak píšem niečo
dlhšie, prípadne je to

605
00:28:03,020 --> 00:28:05,860
chystá vplížit do baru priestoru.

606
00:28:05,860 --> 00:28:08,405
Ale ešte horšie, to dopadá
out celú tú dobu,

607
00:28:08,405 --> 00:28:11,530
aj keď sme sa nikdy nehovoril o
to, zásobník sa používa pre iné veci.

608
00:28:11,530 --> 00:28:13,560
Nie je to len lokálne premenné.

609
00:28:13,560 --> 00:28:15,100
>> C je veľmi nízka úroveň jazyka.

610
00:28:15,100 --> 00:28:17,810
A to tak nejako tajne
používa zásobník tiež

611
00:28:17,810 --> 00:28:21,260
mať na pamäti, keď sa
Funkcia je volaná, čo

612
00:28:21,260 --> 00:28:26,040
je adresa z predchádzajúcej funkcie,
tak to môže skočiť späť na túto funkciu.

613
00:28:26,040 --> 00:28:29,980
Takže keď hlavné výzvy výmene, medzi
veci tlačil do fronty

614
00:28:29,980 --> 00:28:34,380
nie sú len swapy lokálne premenné,
alebo jej argumenty, tiež tajne tlačil

615
00:28:34,380 --> 00:28:37,510
do zásobníka, ako je znázornené
červeným rezu tu,

616
00:28:37,510 --> 00:28:40,520
je adresa hlavného fyzicky
v pamäti počítača,

617
00:28:40,520 --> 00:28:44,180
tak, že keď je odkladacia vykonáva, počítač
vie, že je potrebné sa vrátiť k hlavnému

618
00:28:44,180 --> 00:28:46,760
a dokončiť prevedenia hlavnú funkciu.

619
00:28:46,760 --> 00:28:51,960
Takže toto je teraz nebezpečné, pretože ak
užívateľ zadá v dobre viac ako ahoj,

620
00:28:51,960 --> 00:28:57,030
taká, že vstup užívateľa clobbers
alebo prepíše že červené úsek,

621
00:28:57,030 --> 00:28:59,820
logicky v prípade, že počítač je
jednoducho ísť slepo predpokladať,

622
00:28:59,820 --> 00:29:03,830
že byty v tomto červenom plátok sú
adresa, na ktorú by mal vrátiť,

623
00:29:03,830 --> 00:29:09,020
čo v prípade, že protivník je dosť šikovný, alebo
šťastie dať postupnosť bytov

624
00:29:09,020 --> 00:29:13,450
tam, že vyzerá ako adresa,
ale je to adresa kódu

625
00:29:13,450 --> 00:29:18,730
že on alebo ona chce počítač
vykonávať miesto main?

626
00:29:18,730 --> 00:29:21,670
>> Inými slovami, či to, čo sa
Užívateľ je písanie na výzvy,

627
00:29:21,670 --> 00:29:23,850
Nie je to len niečo,
neškodný ako Dobrý deň,

628
00:29:23,850 --> 00:29:28,210
ale je to vlastne kód, ktorý je rovnocenný
vymazať všetky súbory tohto užívateľa?

629
00:29:28,210 --> 00:29:30,060
Alebo e-mailom svoje heslo ku mne?

630
00:29:30,060 --> 00:29:31,940
Alebo začať protokolovanie ich
kláves, že jo?

631
00:29:31,940 --> 00:29:34,920
Existuje spôsob, poďme stanoviť dnes,
že by mohli zadajte nie je len ahoj

632
00:29:34,920 --> 00:29:36,711
world alebo ich meno,
mohli v podstate

633
00:29:36,711 --> 00:29:39,570
odovzdať kódov, nuly a
ty, že je počítač

634
00:29:39,570 --> 00:29:43,450
chyby ako pre kód a adresu.

635
00:29:43,450 --> 00:29:48,950
Takže aj keď trochu abstraktne, v prípade, že
užívateľ zadá v dostatočnom sporného kóde

636
00:29:48,950 --> 00:29:52,330
že budeme zovšeobecniť tu
A. A je útok alebo protivníci.

637
00:29:52,330 --> 00:29:53,140
Takže len zlé veci.

638
00:29:53,140 --> 00:29:55,306
My sa nestarajú o
čísla alebo nuly, alebo tie,

639
00:29:55,306 --> 00:29:59,470
dnes, takže môžete skončiť
prepisovanie, že červená časť,

640
00:29:59,470 --> 00:30:01,580
Všimnite si, že poradie bajtov.

641
00:30:01,580 --> 00:30:05,020
O 835 C nula ôsmich nula.

642
00:30:05,020 --> 00:30:08,960
A teraz, keď na Wikipédii článok tu
navrhla, ak si teraz skutočne začať

643
00:30:08,960 --> 00:30:12,460
označovanie bajtov v počítača
pamäť, čo článok Wikipédie

644
00:30:12,460 --> 00:30:19,060
navrhujúci je, že to, čo v prípade, že adresa
tohto ľavom hornom bytu je 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Inými slovami, ak je zlý chlap je
dosť chytrý s jeho alebo jej kód

646
00:30:22,200 --> 00:30:26,650
skutočne vložiť číslo, ktoré tu
odpovedá na adresu kódu

647
00:30:26,650 --> 00:30:29,180
on alebo ona injekčne
do počítača,

648
00:30:29,180 --> 00:30:31,050
ktorá dokáže oklamať počítač
do niečo robiť.

649
00:30:31,050 --> 00:30:34,140
Odstránenie súborov, posielanie e-mailov
veci, ňuchania svoju prevádzku,

650
00:30:34,140 --> 00:30:36,710
doslova niečo mohlo byť
vstrekuje do počítača.

651
00:30:36,710 --> 00:30:39,220
A tak pretečeniu vyrovnávacej pamäte
útok vo svojom jadre

652
00:30:39,220 --> 00:30:43,530
je len hlúpa, hlúpa
Prvoradým z poľa, ktorý

653
00:30:43,530 --> 00:30:45,840
nemal kontrolovať jeho hranice.

654
00:30:45,840 --> 00:30:48,850
A to je to, čo je super nebezpečný
a zároveň veľmi výkonný

655
00:30:48,850 --> 00:30:52,560
v C je, že sme skutočne majú
prístup k kdekoľvek v pamäti.

656
00:30:52,560 --> 00:30:55,320
Je to na nás, programátori,
ktorí píšu pôvodný kód

657
00:30:55,320 --> 00:30:59,330
skontrolovať dĺžku zašiť niektorého
polí, že sme manipulovali.

658
00:30:59,330 --> 00:31:00,750
Tak, aby bolo jasné, čo je to oprava?

659
00:31:00,750 --> 00:31:03,190
Ak by sme sa vrátiť k tomu
kód, mal by som to nielen

660
00:31:03,190 --> 00:31:08,000
zmeniť dĺžku tyče, čo
inak by som mal skontrolovať?

661
00:31:08,000 --> 00:31:10,620
Čo iné by som mal robiť, aby
zabrániť úplne tento útok?

662
00:31:10,620 --> 00:31:14,110
Nechcem, aby len slepo povedať
že by ste mali skopírovať toľko bajtov

663
00:31:14,110 --> 00:31:16,140
ako je dĺžka tyče.

664
00:31:16,140 --> 00:31:18,910
Chcem povedať, kopírovanie as
veľa bajtov ako sú v baroch

665
00:31:18,910 --> 00:31:24,090
až do pridelenej
pamäť, alebo 12 maximálne.

666
00:31:24,090 --> 00:31:27,450
Tak som potrebovať nejaký, ak stav
ktorá robí skontrolujte dĺžku tyče,

667
00:31:27,450 --> 00:31:32,800
ale ak prekročí 12, len sme pevný kód
12 ako maximálnej možnej vzdialenosti.

668
00:31:32,800 --> 00:31:35,910
V opačnom prípade takzvaný vyrovnávacej pamäte
overflow útoku sa môže stať.

669
00:31:35,910 --> 00:31:38,451
V dolnej časti týchto snímok,
ak ste zvedaví čítať viac

670
00:31:38,451 --> 00:31:41,200
je skutočný pôvodný článok
ak by ste chceli, aby sa pozrieť.

671
00:31:41,200 --> 00:31:44,550
>> Ale teraz, medzi cenami
Tu zaplatil bol neefektívny.

672
00:31:44,550 --> 00:31:46,680
Takže to bola rýchla
nízka úroveň pohľad na to, čo

673
00:31:46,680 --> 00:31:49,709
Problémy môžu vznikať teraz, že sme
majú prístup do pamäte počítača.

674
00:31:49,709 --> 00:31:51,750
Ale ďalší problém, ktorý sme
Už narazil v pondelok

675
00:31:51,750 --> 00:31:53,800
bol len neefektívnosť
prepojeného zoznamu.

676
00:31:53,800 --> 00:31:56,019
Sme späť do lineárneho času.

677
00:31:56,019 --> 00:31:57,560
Máme už nemajú súvislý rad.

678
00:31:57,560 --> 00:31:58,980
Nemáme náhodný prístup.

679
00:31:58,980 --> 00:32:00,710
Nemôžeme použiť hranatú zátvorku notácie.

680
00:32:00,710 --> 00:32:04,590
Máme doslova musieť použiť while
ako ten, ktorý som napísal pred chvíľou.

681
00:32:04,590 --> 00:32:09,740
Ale v pondelok, sme tvrdili, že môžeme
vplížit späť do ríše účinnosti

682
00:32:09,740 --> 00:32:13,040
dosiahnutie niečo, čo je
logaritmický možná, alebo najlepšie napriek tomu,

683
00:32:13,040 --> 00:32:16,120
možno aj niečo, čo je
tzv časová konštanta.

684
00:32:16,120 --> 00:32:19,840
Tak ako môžeme urobiť, že pri použití tieto nové
nástroje, tieto adresy, týchto ukazovateľov,

685
00:32:19,840 --> 00:32:22,210
a rezanie závitov veci vlastné?

686
00:32:22,210 --> 00:32:23,960
No, predpokladám, že
tu, to sú banda

687
00:32:23,960 --> 00:32:27,170
čísel, ktoré chceme uložiť v
štruktúra a vyhľadávanie dát efektívne.

688
00:32:27,170 --> 00:32:30,960
Môžeme úplne pretočiť do týždňa
dva, hodiť ich do poľa,

689
00:32:30,960 --> 00:32:33,150
a vyhľadávanie je pomocou binárneho vyhľadávania.

690
00:32:33,150 --> 00:32:34,040
Rozdeľ a panuj.

691
00:32:34,040 --> 00:32:37,720
A v skutočnosti ste napísal
binárne vyhľadávanie v PSET3,

692
00:32:37,720 --> 00:32:40,100
kde ste zaviedli program find.

693
00:32:40,100 --> 00:32:40,890
Ale viete čo.

694
00:32:40,890 --> 00:32:45,060
Tam je trochu viac
šikovný spôsob, ako to dosiahnuť.

695
00:32:45,060 --> 00:32:47,390
Je to trochu viac
sofistikované a to možno

696
00:32:47,390 --> 00:32:50,830
nám umožňuje vidieť, prečo binárne
Vyhľadávanie je tak oveľa rýchlejšie.

697
00:32:50,830 --> 00:32:52,980
Po prvé, poďme predstaviť
pojem stromu.

698
00:32:52,980 --> 00:32:54,730
Ktoré, aj keď v
reality stromy druh

699
00:32:54,730 --> 00:32:57,730
rastú ako to, vo svete počítačov
veda, že druh rastú smerom nadol

700
00:32:57,730 --> 00:33:00,830
ako rodinný strom, kde máte
vašu prarodičia alebo prarodičia

701
00:33:00,830 --> 00:33:04,580
alebo ktovie čo ešte na vrchole, patriarcha a
matriarchát rodiny, len jeden

702
00:33:04,580 --> 00:33:07,930
tzv koreň, uzol, nižšie
ktoré sú jeho deti,

703
00:33:07,930 --> 00:33:11,442
pod ktorou sú jeho deti, alebo
jeho potomkovia všeobecnejšie.

704
00:33:11,442 --> 00:33:13,400
A niekto visí
spodný rodiny

705
00:33:13,400 --> 00:33:16,070
tree, vedľa byť
najmladší v rodine,

706
00:33:16,070 --> 00:33:19,520
môže byť tiež všeobecne
volal listy stromu.

707
00:33:19,520 --> 00:33:21,800
>> Tak to je len banda
slov a definícií

708
00:33:21,800 --> 00:33:25,790
pre niečo, čo sa nazýva strom v počítači
veda, podobne ako rodokmeni.

709
00:33:25,790 --> 00:33:28,770
Ale je tu milovník inkarnácií
stromov, z ktorých jedna

710
00:33:28,770 --> 00:33:30,780
sa nazýva binárny vyhľadávací strom.

711
00:33:30,780 --> 00:33:34,380
A môžete druh vtipálek
okrem toho, čo táto vec robí.

712
00:33:34,380 --> 00:33:37,180
No, je to binárny v akom zmysle?

713
00:33:37,180 --> 00:33:41,455
Odkiaľ binárne pochádza tu?

714
00:33:41,455 --> 00:33:41,955
Prosím?

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

716
00:33:45,961 --> 00:33:47,210
To nie je ani tak alebo.

717
00:33:47,210 --> 00:33:52,000
Je to skôr, že každý z uzlov nemá
viac ako dve deti, pretože tu vidíme.

718
00:33:52,000 --> 00:33:54,990
Všeobecne platí, že tree-- a
vaši rodičia a prarodičia

719
00:33:54,990 --> 00:33:57,640
môže mať toľko detí, alebo
vnúčatá, ako sa v skutočnosti chcú,

720
00:33:57,640 --> 00:34:00,820
a tak napríklad tam máme tri
deti z toho pravého uzla,

721
00:34:00,820 --> 00:34:05,480
ale v binárnom stromu, uzol má
nula, jedna alebo dve deti maximálne.

722
00:34:05,480 --> 00:34:08,496
A to je pekná vlastnosť,
pretože ak je limitovaný dvoma,

723
00:34:08,496 --> 00:34:10,620
budeme môcť
si trochu log základňu dvoch

724
00:34:10,620 --> 00:34:11,975
akcie deje nakoniec.

725
00:34:11,975 --> 00:34:13,350
Takže máme niečo logaritmickej.

726
00:34:13,350 --> 00:34:14,558
Ale o tom viac za chvíľu.

727
00:34:14,558 --> 00:34:19,810
Vyhľadávací strom znamená, že čísla sú
usporiadané tak, že ľavá dieťaťa

728
00:34:19,810 --> 00:34:22,429
hodnota je väčšia než koreňa.

729
00:34:22,429 --> 00:34:26,010
A jeho právo dieťa
väčší než koreňa.

730
00:34:26,010 --> 00:34:29,290
Inými slovami, ak budete mať niektorý z
uzly, kruhy v tomto obrázku,

731
00:34:29,290 --> 00:34:31,840
a pozerá sa na jej ľavej strane
Dieťa a jeho právo dieťaťa,

732
00:34:31,840 --> 00:34:34,739
Prvá by mala byť nižšia ako,
druhá by mala byť väčšia ako.

733
00:34:34,739 --> 00:34:36,159
Takže zdravý rozum skontrolovať 55.

734
00:34:36,159 --> 00:34:37,780
Je to nechal dieťa je 33.

735
00:34:37,780 --> 00:34:38,620
To je menej ako.

736
00:34:38,620 --> 00:34:40,929
55, jeho právo dieťa je 77.

737
00:34:40,929 --> 00:34:41,783
To je väčší ako.

738
00:34:41,783 --> 00:34:43,199
A to je rekurzívne definície.

739
00:34:43,199 --> 00:34:46,480
Mohli by sme skontrolovať každý jeden z tých,
uzly a rovnaký vzor by sa držať.

740
00:34:46,480 --> 00:34:49,389
>> Takže to, čo je milé v
binárny vyhľadávací strom, je

741
00:34:49,389 --> 00:34:52,204
že jeden, môžeme ho realizovať
s struct, rovnako ako táto.

742
00:34:52,204 --> 00:34:54,620
A aj keď sme hádzanie
veľa stavieb na dosah,

743
00:34:54,620 --> 00:34:56,560
oni sú trochu
intuitívne teraz nádejne.

744
00:34:56,560 --> 00:35:00,570
Syntax je stále tajomný pre istotu,
ale obsah uzla v tejto

745
00:35:00,570 --> 00:35:02,786
context-- a držíme
pomocou uzla slovo,

746
00:35:02,786 --> 00:35:04,910
či už je to obdĺžnik
na obrazovku alebo do kruhu,

747
00:35:04,910 --> 00:35:08,970
je to len nejaký všeobecný kontajner,
V tomto prípade stromu, ako je tá

748
00:35:08,970 --> 00:35:11,780
sme videli, potrebujeme číslo
v každom z uzlov

749
00:35:11,780 --> 00:35:15,460
a potom som potrebné dva ukazovateľov ukazujúcich
do ľavého dieťa a pravé dieťa,

750
00:35:15,460 --> 00:35:16,590
v tomto poradí.

751
00:35:16,590 --> 00:35:20,730
Tak to je to, ako by sme mohli
náradie, ktoré v Struct.

752
00:35:20,730 --> 00:35:22,315
A ako by som mohol realizovať ju v kóde?

753
00:35:22,315 --> 00:35:26,730
Dobre, poďme sa rýchlo
pozrite sa na tento malý príklad.

754
00:35:26,730 --> 00:35:29,820
Nie je to funkčné, ale ja som
skopírovať a vložiť túto štruktúru.

755
00:35:29,820 --> 00:35:33,510
A keď je moja funkcia pre binárne
vyhľadávací strom sa nazýva hľadanie,

756
00:35:33,510 --> 00:35:36,980
a to trvá dva argumenty,
celé číslo N a ukazovateľ

757
00:35:36,980 --> 00:35:41,400
do uzla, takže ukazovateľ na stromu
alebo ukazovateľ ku koreňu stromu,

758
00:35:41,400 --> 00:35:43,482
Ako mám ísť o hľadanie N?

759
00:35:43,482 --> 00:35:45,440
No, v prvom, pretože som
rokovania s ukazovateľmi,

760
00:35:45,440 --> 00:35:46,750
Budem robiť kontrolu zdravý rozum.

761
00:35:46,750 --> 00:35:54,279
Ak strom rovná rovná null, je N
v tejto vetve alebo nie je v tejto vetve?

762
00:35:54,279 --> 00:35:55,070
To nemôže byť, že jo?

763
00:35:55,070 --> 00:35:56,870
Ak som v minulosti null,
tam nič nie je.

764
00:35:56,870 --> 00:35:59,230
Ja by som mohol tiež práve
slepo hovoria return false.

765
00:35:59,230 --> 00:36:04,050
Ak mi nič, rozhodne nemôžem
nájsť ľubovoľný počet N. Takže čo iného by som mohol

766
00:36:04,050 --> 00:36:04,750
skontroluj teraz?

767
00:36:04,750 --> 00:36:12,830
Chystám sa povedať aj inak, ak N je
menšie ako to, čo je v uzla stromu

768
00:36:12,830 --> 00:36:16,300
že som bola odovzdaná hodnota n.

769
00:36:16,300 --> 00:36:20,270
Inými slovami, ak je číslo nie som
hľadá, N, je menšie, než uzol

770
00:36:20,270 --> 00:36:21,340
že som pri pohľade na.

771
00:36:21,340 --> 00:36:23,190
A uzol sa pozerám
u sa nazýva strom,

772
00:36:23,190 --> 00:36:26,370
a vyvolať z predchádzajúceho príkladu
sa dostať na hodnotu v ukazovateli,

773
00:36:26,370 --> 00:36:28,310
Používam notáciu so šípkou.

774
00:36:28,310 --> 00:36:35,960
Takže ak N je menší ako stromu šípky
N, chcem koncepčne ísť doľava.

775
00:36:35,960 --> 00:36:38,590
Ako môžem express vyhľadávania odišiel?

776
00:36:38,590 --> 00:36:41,560
Aby bolo jasno, či sa jedná
obraz v otázke,

777
00:36:41,560 --> 00:36:44,612
a bol som prešiel, že najvyššie
šípka, ktorá je smerom nadol.

778
00:36:44,612 --> 00:36:45,570
To je môj strom ukazovateľ.

779
00:36:45,570 --> 00:36:48,060
Ja som ukázal na koreň stromu.

780
00:36:48,060 --> 00:36:52,100
A ja hľadám povedzme, pre
číslo 44, ľubovoľne.

781
00:36:52,100 --> 00:36:55,300
Je menšia ako 44, alebo
väčší ako 55 zrejme?

782
00:36:55,300 --> 00:36:56,360
Takže je to menej ako.

783
00:36:56,360 --> 00:36:58,760
A tak, ak podmienka platí.

784
00:36:58,760 --> 00:37:03,981
Tak koncepčne, čo chcem
hľadať ďalšie, keď som hľadal 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Presne tak, chcem
vyhľadávať ľavej dieťa,

788
00:37:11,100 --> 00:37:12,789
alebo doľava sub-strom obrázku.

789
00:37:12,789 --> 00:37:14,830
A v skutočnosti, dovoľte mi, aby som prostredníctvom
obrázok tu dole

790
00:37:14,830 --> 00:37:17,770
len na chvíľu, pretože
Nemôžem poškriabaniu to.

791
00:37:17,770 --> 00:37:21,150
Ak začnem tu na 55, a
Viem, že hodnota 44

792
00:37:21,150 --> 00:37:23,180
Ja som hľadal je
ľavá, je to druh

793
00:37:23,180 --> 00:37:26,010
ako sa trhá telefónny zoznam v
polpenzia alebo trhanie strom na polovicu.

794
00:37:26,010 --> 00:37:29,660
Ja už musieť starať o
Celá táto polovica stromu.

795
00:37:29,660 --> 00:37:33,270
A napriek tomu, zvedavo v termínoch
štruktúra, toto tu, že

796
00:37:33,270 --> 00:37:36,682
začína 33, ktoré samo o sebe
je binárny vyhľadávací strom.

797
00:37:36,682 --> 00:37:39,890
Povedal som to slovo rekurzívne skôr, pretože
v skutočnosti to je dátová štruktúra, ktorá

798
00:37:39,890 --> 00:37:41,707
podľa definície je rekurzívne.

799
00:37:41,707 --> 00:37:44,540
Možno budete mať strom, ktorý je tento
veľký, ale každý z jej detí

800
00:37:44,540 --> 00:37:46,870
predstavuje strom len trochu menší.

801
00:37:46,870 --> 00:37:50,910
Namiesto toho, že dedo
alebo babička, teraz je to len mama

802
00:37:50,910 --> 00:37:54,300
nebo-- Nemôžem say-- nie je mama
alebo otec, to by bolo divné.

803
00:37:54,300 --> 00:37:59,000
Namiesto toho tam dve deti
by bol ako brat a súrodenci.

804
00:37:59,000 --> 00:38:01,120
Nová generácia rodinného stromu.

805
00:38:01,120 --> 00:38:02,900
Ale štrukturálne, je to rovnaký nápad.

806
00:38:02,900 --> 00:38:06,790
A ukázalo sa, že mám funkciu
s ktorými môžem vyhľadávať binárne vyhľadávanie

807
00:38:06,790 --> 00:38:07,290
strom.

808
00:38:07,290 --> 00:38:08,680
Nazýva sa vyhľadávanie.

809
00:38:08,680 --> 00:38:17,870
Aj hľadať N vo stromu Šípka doľava
else if N je väčší ako hodnota

810
00:38:17,870 --> 00:38:18,870
že som v súčasnej dobe.

811
00:38:18,870 --> 00:38:20,800
55 v príbehu pred chvíľou.

812
00:38:20,800 --> 00:38:23,780
Mám funkciu nazvanú
Hľadania, ktorý môžem len

813
00:38:23,780 --> 00:38:29,660
prejsť N a to rekurzívne vyhľadávanie
sub-strom a práve návrat

814
00:38:29,660 --> 00:38:30,620
čo to odpoveď.

815
00:38:30,620 --> 00:38:33,530
Inak mám nejaké finálnej základné prípad tu.

816
00:38:33,530 --> 00:38:35,310
>> Aká je konečná prípad?

817
00:38:35,310 --> 00:38:36,570
Strom je buď nulový.

818
00:38:36,570 --> 00:38:39,980
Hodnota som buď hľadal je
menšie ako, alebo väčšia ako

819
00:38:39,980 --> 00:38:42,610
alebo rovná to.

820
00:38:42,610 --> 00:38:44,750
A mohol by som povedať, rovná
rovní, ale logicky je to

821
00:38:44,750 --> 00:38:46,500
čo zodpovedá len hovorím, že tu inde.

822
00:38:46,500 --> 00:38:49,150
Takže pravda je, ako som sa niečo nájsť.

823
00:38:49,150 --> 00:38:51,710
Tak dúfajme, že to je
ešte presvedčivejší príklad

824
00:38:51,710 --> 00:38:54,900
ako stupídny funkcie sigma
sme urobili niekoľko prednášok späť,

825
00:38:54,900 --> 00:38:58,360
kde to bolo rovnako jednoduché používanie slučku
spočítať všetky čísla od jednotky

826
00:38:58,360 --> 00:39:02,390
N. Tu s dátovú štruktúru
ktorý sám o sebe je rekurzívne

827
00:39:02,390 --> 00:39:07,050
definované a rekurzívne vyvodiť, teraz sme
majú schopnosť vyjadriť seba

828
00:39:07,050 --> 00:39:09,780
V kódu, ktorý sám o sebe je rekurzívne.

829
00:39:09,780 --> 00:39:12,580
Tak to je presne rovnaký kód tu.

830
00:39:12,580 --> 00:39:14,400
>> Takže to, čo ďalšie problémy môžeme vyriešiť?

831
00:39:14,400 --> 00:39:18,160
Tak rýchly krôčik od
stromy na chvíľku.

832
00:39:18,160 --> 00:39:20,130
Tu je, povedzme, pod nemeckou vlajkou.

833
00:39:20,130 --> 00:39:22,020
A je tu jednoznačne
vzor tohto parametra.

834
00:39:22,020 --> 00:39:23,811
A je tu veľa
Vlajky na svete, ktorý

835
00:39:23,811 --> 00:39:27,560
sú tak jednoduché, ako je to z hľadiska
ich farieb a vzorov.

836
00:39:27,560 --> 00:39:31,930
Ale predpokladajme, že tento je uložený ako
GIF, alebo JPEG, alebo bitmapové, alebo ping,

837
00:39:31,930 --> 00:39:34,240
akýkoľvek grafický formát súboru
, S ktorým ste sa zoznámili,

838
00:39:34,240 --> 00:39:36,460
z ktorých niektoré sme
hrať s v PSET4.

839
00:39:36,460 --> 00:39:41,550
To sa zdá ako veľmi užitočné pre ukladanie
Čierny pixel, čierny pixel, čierny pixel,

840
00:39:41,550 --> 00:39:44,790
bodka, bodka, bodka, celá partia
čierne pixely pre prvú scanline,

841
00:39:44,790 --> 00:39:47,430
alebo riadku, potom celá partia
rovnaké, potom sa celý zväzok

842
00:39:47,430 --> 00:39:49,530
of rovnaké, a potom
Celá banda červených pixelov,

843
00:39:49,530 --> 00:39:53,020
červené pixely, červené pixely, potom celý
banda žltých pixelov, žltá, že jo?

844
00:39:53,020 --> 00:39:55,050
>> Je tu taký neefektívnosť sem.

845
00:39:55,050 --> 00:39:59,040
Ako by ste intuitívne
stlačiť pod nemeckou vlajkou

846
00:39:59,040 --> 00:40:01,320
ak sa vykonáva ako súbor?

847
00:40:01,320 --> 00:40:04,940
Ako aké informácie nemôžeme
obťažovať ukladanie na disk v poradí

848
00:40:04,940 --> 00:40:08,040
znížiť našu veľkosť súboru z podobne
megabajt na kilobyte, niečo

849
00:40:08,040 --> 00:40:09,430
menšie?

850
00:40:09,430 --> 00:40:13,130
V čom spočíva redundancie
tu musí byť jasné?

851
00:40:13,130 --> 00:40:13,880
Čo si to mohol urobiť?

852
00:40:13,880 --> 00:40:14,380
Jo?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Presne tak.

855
00:40:21,970 --> 00:40:24,550
Prečo radšej než spomenúť
farba každého pixelu zašiť

856
00:40:24,550 --> 00:40:28,200
rovnako ako to robíte v PSET4
s formátom bitmapový obrázok,

857
00:40:28,200 --> 00:40:32,060
prečo si jednoducho predstavujú
vľavo stĺpec obrazových bodov, napríklad

858
00:40:32,060 --> 00:40:35,370
banda čiernych pixelov, partia
červenej a banda žlté,

859
00:40:35,370 --> 00:40:39,210
a potom už len nejako zakódovať
idea Opakujte tento 100 krát

860
00:40:39,210 --> 00:40:41,020
alebo zopakovať tento 1,000 časov?

861
00:40:41,020 --> 00:40:43,430
V prípade, 100 alebo 1000, je
len číslo, takže si

862
00:40:43,430 --> 00:40:47,290
môže dostať preč len s jedným číslom
namiesto stoviek alebo tisícok

863
00:40:47,290 --> 00:40:48,270
dodatočných pixelov.

864
00:40:48,270 --> 00:40:50,990
A naozaj, to je, ako sme
by mohlo stlačiť pod nemeckou vlajkou.

865
00:40:50,990 --> 00:40:51,490
A

866
00:40:51,490 --> 00:40:53,470
A teraz, čo o francúzskou vlajkou?

867
00:40:53,470 --> 00:40:58,930
A trochu akýsi
mentálne cvičenie, ktoré vlajka

868
00:40:58,930 --> 00:41:01,040
môžu byť komprimované viac na disku?

869
00:41:01,040 --> 00:41:05,720
Nemeckej vlajky alebo francúzska
vlajky, ak vezmeme tento prístup?

870
00:41:05,720 --> 00:41:08,490
Nemecká vlajka, pretože tam je
viac horizontálne redundancie.

871
00:41:08,490 --> 00:41:12,190
A podľa návrhu, mnohí grafický súbor
formáty skutočne pracovať ako rozkladovej riadky

872
00:41:12,190 --> 00:41:12,830
horizontálne.

873
00:41:12,830 --> 00:41:14,674
Mohli by fungovať
vertikálne, len ľudstvo

874
00:41:14,674 --> 00:41:17,090
Pred rokmi sa rozhodli, že budeme
všeobecne myslieť na veci, radu

875
00:41:17,090 --> 00:41:18,880
riadkom namiesto riadok po riadku.

876
00:41:18,880 --> 00:41:20,820
Takže naozaj, ak ste boli
sa pozrieť na súbor

877
00:41:20,820 --> 00:41:24,670
veľkosť nemeckou vlajkou a francúzštine
flag, tak dlho, kým je rozlíšenie

878
00:41:24,670 --> 00:41:27,530
rovnaké, rovnakú šírku
a výška, tahle

879
00:41:27,530 --> 00:41:31,580
Tu bude väčší, pretože
musieť opakovať sami trikrát.

880
00:41:31,580 --> 00:41:35,570
Musíte zadať modrá, opakovanie
sami, biela, opakovať sami, červená,

881
00:41:35,570 --> 00:41:36,740
opakovať sa.

882
00:41:36,740 --> 00:41:39,000
Nemôžete jednoducho ísť all
cesta doprava.

883
00:41:39,000 --> 00:41:41,200
A ako stranou, aby sa
zrušte kompresie

884
00:41:41,200 --> 00:41:43,910
je všade, ak sa jedná o
Štyri rámy z video-- vás

885
00:41:43,910 --> 00:41:45,890
by mohol pripomenúť, že filmu
alebo video je všeobecne

886
00:41:45,890 --> 00:41:47,286
ako je 29 alebo 30 snímok za sekundu.

887
00:41:47,286 --> 00:41:50,410
Je to ako malé flip knihy, kde vás
Len pozri obrázok, obrázok, image, image,

888
00:41:50,410 --> 00:41:54,410
image proste super rýchly, takže to vyzerá,
herci na obrazovke sa pohybujú.

889
00:41:54,410 --> 00:41:57,130
Tu je bumble včela na
Vrchol kytice.

890
00:41:57,130 --> 00:41:59,790
A aj keď to by mohlo byť trochu
ťažké vidieť na prvý pohľad,

891
00:41:59,790 --> 00:42:04,020
Jediná vec, pohybujúce sa v
tento film je včela.

892
00:42:04,020 --> 00:42:06,880
>> Čo je nemý o skladovaní
Video nekomprimované?

893
00:42:06,880 --> 00:42:11,420
Je to druh odpadu pre ukladanie videa
ako štyri takmer identické obrazy, ktoré

894
00:42:11,420 --> 00:42:13,670
sa líšia iba v prípade, keď je včela.

895
00:42:13,670 --> 00:42:16,280
Môžete zahodiť väčšinu
týchto informácií

896
00:42:16,280 --> 00:42:20,190
a pamätať si len, napríklad,
prvý záber a posledná snímka,

897
00:42:20,190 --> 00:42:22,180
kľúčové snímky, ak ste
niekedy počul slovo,

898
00:42:22,180 --> 00:42:24,337
a len uložiť do
prostredný kde včela je.

899
00:42:24,337 --> 00:42:26,170
A nemusíte sa
ukladať všetky ružové,

900
00:42:26,170 --> 00:42:28,330
a modrej, a
zelené hodnoty rovnako.

901
00:42:28,330 --> 00:42:31,200
Tak toto je len povedať, že
kompresie je všade.

902
00:42:31,200 --> 00:42:34,900
Jedná sa o techniku ​​často používame
alebo považuje za samozrejmosť v týchto dňoch.

903
00:42:34,900 --> 00:42:38,750
>> Ale ako si komprimovať text?

904
00:42:38,750 --> 00:42:40,450
Ako sa vám ísť o kompresiu textu?

905
00:42:40,450 --> 00:42:45,410
No, každý zo znakov v
ASCII je jeden bajt, alebo osem bitov.

906
00:42:45,410 --> 00:42:47,360
A to je trochu hlúpa, že jo?

907
00:42:47,360 --> 00:42:51,160
Vzhľadom k tomu, budete pravdepodobne typu A
a E a I a O a U veľa

908
00:42:51,160 --> 00:42:55,270
častejšie než ako W alebo Q alebo Z,
v závislosti na jazyk, v ktorom

909
00:42:55,270 --> 00:42:56,610
píšete určite.

910
00:42:56,610 --> 00:42:59,600
A prečo sme s použitím
osem bitov pre každé písmeno,

911
00:42:59,600 --> 00:43:02,040
vrátane najmenej
populárne listy, že jo?

912
00:43:02,040 --> 00:43:05,300
Prečo nie použiť menej bitov pre
Super populárne listy,

913
00:43:05,300 --> 00:43:07,760
ako E, veci, ktoré hádať
najprv v Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
a používať viac bitov pre
menej populárne listy?

915
00:43:10,450 --> 00:43:10,950
Prečo?

916
00:43:10,950 --> 00:43:13,130
Pretože sme len tak
používať menej často.

917
00:43:13,130 --> 00:43:15,838
>> No, to ukáže, že tam majú
Bol pokusy, ako to dosiahnuť.

918
00:43:15,838 --> 00:43:18,630
A ak si spomínate zo stupňa
škola alebo vysoká škola, Morseova abeceda.

919
00:43:18,630 --> 00:43:20,400
Morseova abeceda má bodky
a pomlčky, ktoré môžu byť

920
00:43:20,400 --> 00:43:24,270
prenášané po drôte as
zvuky alebo signály nejakého druhu.

921
00:43:24,270 --> 00:43:25,930
Ale Morseova abeceda je super čistý.

922
00:43:25,930 --> 00:43:29,010
Je to trochu binárneho systému
že máte bodky alebo čiarky.

923
00:43:29,010 --> 00:43:30,977
Ale keď vidíte, napríklad, dve bodky.

924
00:43:30,977 --> 00:43:33,810
Alebo ak si myslíte, späť na prevádzkovateľa
ktorí chodia ako píp, píp, pípnutie,

925
00:43:33,810 --> 00:43:36,760
pípnutie, biť trochu spúšť
ktorý vysiela signál,

926
00:43:36,760 --> 00:43:40,360
ak vás, príjemcu, dostane dve
bodky, akú správu ste dostali?

927
00:43:40,360 --> 00:43:43,490
Úplne ľubovoľné.

928
00:43:43,490 --> 00:43:44,450
>> Aj?

929
00:43:44,450 --> 00:43:45,060
Aj?

930
00:43:45,060 --> 00:43:47,500
Alebo čo about-- alebo ja?

931
00:43:47,500 --> 00:43:49,570
Možno to bolo len dva E má pravdu?

932
00:43:49,570 --> 00:43:52,480
Takže tam je to problém
z decodability s Morse

933
00:43:52,480 --> 00:43:54,890
kód, pričom ak sa
osoba zasielanie správy

934
00:43:54,890 --> 00:43:59,510
v skutočnosti sa zastaví, takže si môžete triediť podľa
vidieť alebo počuť medzery medzi písmenami,

935
00:43:59,510 --> 00:44:02,990
že to nie je dostačujúce len
Poslať prúdu núl a jednotiek,

936
00:44:02,990 --> 00:44:05,610
alebo bodky a čiarky,
pretože tam je dvojznačnosť.

937
00:44:05,610 --> 00:44:08,640
E je jediná bodka, takže ak vás
pozri dve bodky alebo počuť dve bodky,

938
00:44:08,640 --> 00:44:11,254
Možno je to dva E je alebo možno je to jedna I.

939
00:44:11,254 --> 00:44:13,670
Takže potrebujeme systém, ktorý je
málo múdrejší než to.

940
00:44:13,670 --> 00:44:16,851
Takže muž menom Huffman rokov
Pred prišli s presne toto.

941
00:44:16,851 --> 00:44:18,600
Takže sme len tak
vziať rýchly pohľad

942
00:44:18,600 --> 00:44:20,114
na to, ako stromy sú pre predmetnú.

943
00:44:20,114 --> 00:44:22,530
Predpokladajme, že je to nejaký
hlúpy správa, ktorú chcete odoslať,

944
00:44:22,530 --> 00:44:26,342
zložený z iba A, B, C je D'S a E je,
ale je tu veľa redundancie sem.

945
00:44:26,342 --> 00:44:27,550
Nie je to znamená byť angličtina.

946
00:44:27,550 --> 00:44:28,341
To nie je šifrovaná.

947
00:44:28,341 --> 00:44:30,540
Je to len hlúpa správa
s množstvom opakovaní.

948
00:44:30,540 --> 00:44:34,010
Takže ak ste naozaj počítať sa všetky
A to, B je, je C, D's, a E je, tu je

949
00:44:34,010 --> 00:44:34,890
frekvencie.

950
00:44:34,890 --> 00:44:37,800
20% z listov sú
A je 45% z listov

951
00:44:37,800 --> 00:44:39,660
sú E je, a ďalšie tri frekvencie.

952
00:44:39,660 --> 00:44:41,960
Počítali sme tam ručne
a práve urobil matematický.

953
00:44:41,960 --> 00:44:44,579
>> Tak to dopadá, že
Huffman, pred nejakým časom,

954
00:44:44,579 --> 00:44:46,620
si uvedomil, že, viete,
čo, keď som začať stavať

955
00:44:46,620 --> 00:44:51,172
strom alebo les stromov, ak chcete,
takto, môžem urobiť nasledovné.

956
00:44:51,172 --> 00:44:53,880
Chystám sa dať uzla ku každému
z listov, ktoré som záleží

957
00:44:53,880 --> 00:44:55,530
a budem ukladať
vnútri tohto uzla

958
00:44:55,530 --> 00:44:58,610
frekvencie ako pohyblivou rádovou čiarkou
hodnota, alebo môžete použiť N, taky,

959
00:44:58,610 --> 00:45:00,210
ale my budeme stačí použiť float tu.

960
00:45:00,210 --> 00:45:03,100
A algoritmus, ktorý
navrhol je, že ste

961
00:45:03,100 --> 00:45:07,210
tento les jedného uzla
stromy, takže extra krátke stromy,

962
00:45:07,210 --> 00:45:11,920
a začnete ich spájajú s
nové skupiny, nové rodičia, ak chcete.

963
00:45:11,920 --> 00:45:16,150
A to tým, že voľbe
dve najmenšie frekvenciou naraz.

964
00:45:16,150 --> 00:45:18,110
Tak som vzal 10% a 10%.

965
00:45:18,110 --> 00:45:19,090
Aj vytvoriť nový uzol.

966
00:45:19,090 --> 00:45:20,910
A ja hovorím nového uzla 20%.

967
00:45:20,910 --> 00:45:22,750
>> Ktorí dva uzly Aj kombinovať ďalej?

968
00:45:22,750 --> 00:45:23,810
Je to trochu nejasné.

969
00:45:23,810 --> 00:45:26,643
Takže tam je niekoľko prípadov roh
zvážiť, ale udržať veci dosť,

970
00:45:26,643 --> 00:45:29,300
Budem voliť 20% -
Aj teraz ignorovať deti.

971
00:45:29,300 --> 00:45:33,640
Budem voliť 20% a
15% a kresliť dva nové hrany.

972
00:45:33,640 --> 00:45:35,624
A teraz, keď sú dve uzly
mám logicky kombinovať?

973
00:45:35,624 --> 00:45:38,540
Ignorovať všetky deti, sú všetky
vnúčatá, stačí sa pozrieť na korene

974
00:45:38,540 --> 00:45:39,070
teraz.

975
00:45:39,070 --> 00:45:42,220
Ktorí dva uzly mám zviazať dohromady?

976
00:45:42,220 --> 00:45:44,530
Bod dva a 0.35.

977
00:45:44,530 --> 00:45:45,890
Dovoľte mi teda kresliť dva nové hrany.

978
00:45:45,890 --> 00:45:47,570
A potom som sa dostal len jeden vľavo.

979
00:45:47,570 --> 00:45:48,650
Tak tu je to strom.

980
00:45:48,650 --> 00:45:51,160
A to bol vypracovaný zámerne
vyzerať trochu pekná,

981
00:45:51,160 --> 00:45:55,870
ale všimnite si, že hrany majú
Tiež bol označený nulou a jednotkou.

982
00:45:55,870 --> 00:45:59,510
Takže všetky ľavého okraja sú nulové
ľubovoľne, ale dôsledne.

983
00:45:59,510 --> 00:46:01,170
Všetky hrany sú tie správne.

984
00:46:01,170 --> 00:46:05,070
>> A tak to, čo Hoffman Navrhuje sa,
Ak chcete reprezentovať B,

985
00:46:05,070 --> 00:46:10,080
skôr než predstavujú počet 66 as
ASCII, ktorý je osem celé bitov,

986
00:46:10,080 --> 00:46:13,360
Vieš čo, len obchod
vzor nula, nula, nula,

987
00:46:13,360 --> 00:46:17,030
nula, pretože to je cesta
z môjho stromu, pána Huffmanův strom,

988
00:46:17,030 --> 00:46:18,600
na liste z koreňa.

989
00:46:18,600 --> 00:46:20,970
Ak chcete uložiť
E, naproti tomu nemajú

990
00:46:20,970 --> 00:46:26,290
poslať osem bitov, ktoré predstavujú E.
Namiesto toho, čo poslať vzor bitov?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
A čo je príjemné na tom je,
že E je najpopulárnejší list,

993
00:46:30,410 --> 00:46:32,340
a používate
Najkratšie kód pre ňu.

994
00:46:32,340 --> 00:46:34,090
Budúci Najobľúbenejšie
list vyzerá, že

995
00:46:34,090 --> 00:46:37,380
bol A. A tak, koľko bitov
urobil navrhujú použitie za to?

996
00:46:37,380 --> 00:46:38,270
Nula, jedna.

997
00:46:38,270 --> 00:46:41,060
>> A pretože je implementované
ako tohto stromu, zatiaľ

998
00:46:41,060 --> 00:46:43,350
dovoľte mi, aby som sa stanovuje, že je
žiadna nejasnosť ako v Morse

999
00:46:43,350 --> 00:46:46,090
kód, pretože všetky
listy vám záleží

1000
00:46:46,090 --> 00:46:48,780
sú na konci týchto hrán.

1001
00:46:48,780 --> 00:46:50,580
Tak to je len jeden
Aplikácia stromu.

1002
00:46:50,580 --> 00:46:52,538
To je-- a budem mávať
moja ruka sa na to, ako na Vás

1003
00:46:52,538 --> 00:46:55,570
môže vykonávať toto ako štruktúra C.

1004
00:46:55,570 --> 00:46:58,260
Potrebujeme len kombinovať
symbol, ako char,

1005
00:46:58,260 --> 00:46:59,910
a frekvencia doľava a doprava.

1006
00:46:59,910 --> 00:47:02,510
Ale poďme sa pozrieť na dva
Konečné príklady, ktoré budete

1007
00:47:02,510 --> 00:47:06,070
dostať docela oboznámení s po
kvíz nula problém nastaviť päť.

1008
00:47:06,070 --> 00:47:09,210
>> Takže tam je dátová štruktúra
známy ako stola mriežky.

1009
00:47:09,210 --> 00:47:12,247
A hash tabuľka je druh
ochladí sa tým, že korčeky.

1010
00:47:12,247 --> 00:47:14,830
A predpokladám, že tam je štyri vedierka
tu, iba štyri medzery.

1011
00:47:14,830 --> 00:47:20,830
Tu je balíček kariet, a je tu
klubu, rýľ, klub, diamanty, klub,

1012
00:47:20,830 --> 00:47:25,960
diamanty, klub, diamanty,
clubs-- takže to je náhodné.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts-- takže som
bucketizing všetky vstupy sem.

1014
00:47:30,330 --> 00:47:32,430
A A potrebuje hash table
pozrieť sa na váš vstup,

1015
00:47:32,430 --> 00:47:34,850
a potom ju do určitej
položte na základe toho, čo vidíte.

1016
00:47:34,850 --> 00:47:35,600
Je to algoritmus.

1017
00:47:35,600 --> 00:47:37,980
A ja som bol s použitím super
jednoduché vizuálne algoritmus.

1018
00:47:37,980 --> 00:47:40,030
Najťažšia časť, ktorá bola
si spomenul, aké obrázky boli.

1019
00:47:40,030 --> 00:47:41,590
A potom je tu celkom štyri veci.

1020
00:47:41,590 --> 00:47:45,440
>> Teraz komíny rástli, čo
je zámerná návrh vec tu.

1021
00:47:45,440 --> 00:47:46,540
Ale čo iného by som mohol urobiť?

1022
00:47:46,540 --> 00:47:49,080
Takže vlastne tu máme
banda starej školy skúšky kníh.

1023
00:47:49,080 --> 00:47:51,240
Predpokladajme, že banda
Mená študenti sú tu.

1024
00:47:51,240 --> 00:47:52,570
Tu to väčšie hash tabuľky.

1025
00:47:52,570 --> 00:47:54,867
Namiesto štyroch vedier,
Som, povedzme 26.

1026
00:47:54,867 --> 00:47:57,950
A my sme nechceli ísť požičať 26
z krajín mimo [? Annenberg?], Tak

1027
00:47:57,950 --> 00:48:00,289
tu je piatich ktoré reprezentujú
A až Z. A ak ja

1028
00:48:00,289 --> 00:48:03,580
pozri študentom, ktorého meno začína na A,
Chystám sa dať jeho alebo jej kvíz tam.

1029
00:48:03,580 --> 00:48:08,850
Ak niekto začne s C, tam,
Je-- skutočnosti, nechcel urobiť.

1030
00:48:08,850 --> 00:48:10,060
B jede sem.

1031
00:48:10,060 --> 00:48:13,390
Tak som dostal A a B a C a
teraz tu je ďalší študent.

1032
00:48:13,390 --> 00:48:16,212
Ale ak to hash tabuľka
implementovaný s maticu

1033
00:48:16,212 --> 00:48:17,920
Som typ skrutkované
v tomto bode, že jo?

1034
00:48:17,920 --> 00:48:19,510
Tak nejako som potrebujete, aby to niekde.

1035
00:48:19,510 --> 00:48:24,380
>> Takže jeden spôsob, ako môžem riešiť to, všetko
vpravo, A je zaneprázdnený, B je zaneprázdnený, C je zaneprázdnený.

1036
00:48:24,380 --> 00:48:28,880
Chystám sa ho dať do D. Takže na
Prvé, mám náhodný okamžitý prístup

1037
00:48:28,880 --> 00:48:31,064
ku každej z lopatiek pre študentov.

1038
00:48:31,064 --> 00:48:33,230
Ale teraz je to trochu preniesol
do niečoho lineárne,

1039
00:48:33,230 --> 00:48:36,750
pretože keď chcem hľadať niekoho,
Názov ktorého začína, ja pozrite sa sem.

1040
00:48:36,750 --> 00:48:38,854
Ale ak to nie je A
Student Hľadám,

1041
00:48:38,854 --> 00:48:41,520
Tak nejako som musel spustiť kontrolu
vedierka, pretože to, čo som urobil

1042
00:48:41,520 --> 00:48:44,530
Bolo to trochu lineárne
skúmať štruktúru dát.

1043
00:48:44,530 --> 00:48:47,710
Hlúpa spôsob ako povedať, stačí sa pozrieť
za prvé dostupné otvoru,

1044
00:48:47,710 --> 00:48:51,850
a dal ako plán B, aby som tak povedal,
alebo plán D v tomto prípade je hodnota

1045
00:48:51,850 --> 00:48:53,340
V tomto mieste namiesto.

1046
00:48:53,340 --> 00:48:56,470
Je to len preto, aby, ak ste
dostal 26 miest a žiadni študenti

1047
00:48:56,470 --> 00:49:00,600
s názvom Q alebo Z, alebo niečo podobné
že prinajmenšom používate priestor.

1048
00:49:00,600 --> 00:49:03,140
>> Ale my sme už videli viac
Múdra riešenie tu, že jo?

1049
00:49:03,140 --> 00:49:04,870
Čo by ste robili, miesto
Ak máte ku kolízii?

1050
00:49:04,870 --> 00:49:06,670
Ak sa dvaja ľudia majú
názov A, čo by

1051
00:49:06,670 --> 00:49:09,160
boli múdrejší a viac
intuitívne riešenie než len

1052
00:49:09,160 --> 00:49:12,840
Uvedenie kde D má byť?

1053
00:49:12,840 --> 00:49:14,810
Prečo nemôžem jednoducho ísť
mimo [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
ako je malloc, iného uzla, dať to
tu, a potom dal, že študent tu.

1055
00:49:19,960 --> 00:49:22,120
Tak, že som v podstate majú
nejaký poľa,

1056
00:49:22,120 --> 00:49:25,590
alebo možno viac elegantne, ako sme
Začíname vidieť prepojeného zoznamu.

1057
00:49:25,590 --> 00:49:29,520
>> A tak hash tabuľky je štruktúra
ktoré by mohli vyzerať presne takto,

1058
00:49:29,520 --> 00:49:33,900
ale chytro, ste niečo ako
samostatný reťazenie, pričom hash tabuľky

1059
00:49:33,900 --> 00:49:38,340
celkom jednoducho je pole, každý z
ktorej prvky nie je číslo,

1060
00:49:38,340 --> 00:49:40,470
je sám o sebe spojený zoznam.

1061
00:49:40,470 --> 00:49:45,080
Tak, že máte super rýchly prístup
rozhodovanie o tom, kde sa vaše hash hodnotu.

1062
00:49:45,080 --> 00:49:48,059
Podobne ako v príklade karty,
Urobil som mimoriadne rýchle rozhodovanie.

1063
00:49:48,059 --> 00:49:49,600
Hearts ide tu, diamanty ide tu.

1064
00:49:49,600 --> 00:49:52,180
Ja taky, A tu ide,
D ide tu, B ide tu.

1065
00:49:52,180 --> 00:49:55,740
Takže super rýchle look-ups, a pokiaľ
ste náhodou naraziť na prípade

1066
00:49:55,740 --> 00:49:59,429
kde ste dostal kolízie, dva
ľudia s rovnakým názvom, no a potom

1067
00:49:59,429 --> 00:50:00,970
stačí začať spájať dokopy.

1068
00:50:00,970 --> 00:50:03,900
A možno si udržať je zoradená
abecedne, možno nie.

1069
00:50:03,900 --> 00:50:05,900
Ale aspoň teraz máme dynamiku.

1070
00:50:05,900 --> 00:50:10,250
Takže na jednej strane máme veľmi rýchle
konštantný čas, a druh lineárneho času

1071
00:50:10,250 --> 00:50:14,110
zapojiť, ak týchto spojových zoznamov
začne byť trochu dlho.

1072
00:50:14,110 --> 00:50:16,880
>> Takže tento druh hlúpy,
geek vtip pred rokmi.

1073
00:50:16,880 --> 00:50:19,590
Na CS50 hack-a-Thon,
Keď študenti check in,

1074
00:50:19,590 --> 00:50:22,040
niektoré TF alebo CA každý rok
si myslí, že je to smiešne, aby sa

1075
00:50:22,040 --> 00:50:27,772
znamenia ako je tento, kde ide len
znamená, že ak vaše meno začína s A,

1076
00:50:27,772 --> 00:50:28,870
ísť touto cestou.

1077
00:50:28,870 --> 00:50:31,110
Ak sa spustí Vaše meno
s B, choďte tohle-- OK,

1078
00:50:31,110 --> 00:50:33,290
je to smiešne možno neskôr v semestri.

1079
00:50:33,290 --> 00:50:36,420
Ale je tu ďalší
spôsob, ako to dosiahnuť, taky.

1080
00:50:36,420 --> 00:50:37,410
Vráť sa k tomu.

1081
00:50:37,410 --> 00:50:38,600
>> Takže je tu táto štruktúra.

1082
00:50:38,600 --> 00:50:40,420
A to je náš posledný
štruktúra pre dnešok,

1083
00:50:40,420 --> 00:50:42,400
čo je niečo, čo nazýva trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, ktorá z nejakého dôvodu je krátka
pre vyhľadávanie, ale je to len trie.

1085
00:50:47,140 --> 00:50:51,389
Takže Trie je ďalšia zaujímavá
amalgám z mnohých týchto nápadov.

1086
00:50:51,389 --> 00:50:52,930
Je to strom, ktorý sme videli skôr.

1087
00:50:52,930 --> 00:50:54,180
Nie je to strom binárneho vyhľadávania.

1088
00:50:54,180 --> 00:50:58,410
Je to strom s ľubovoľným počtom detí,
ale každý z detí v trie

1089
00:50:58,410 --> 00:51:00,090
je pole.

1090
00:51:00,090 --> 00:51:04,790
Poľa veľkosti, povedzme, 26 alebo možno 27
Ak chcete podporiť pomlčkou mená

1091
00:51:04,790 --> 00:51:06,790
alebo apostrofy v názvoch ľudí.

1092
00:51:06,790 --> 00:51:08,280
>> A tak to je dátová štruktúra.

1093
00:51:08,280 --> 00:51:10,290
A keď sa pozriete z vrcholu
dole, ako keď

1094
00:51:10,290 --> 00:51:13,710
pozrite sa na hornom uzla tam, M, je
ukazujúci na najviac vľavo vec tam,

1095
00:51:13,710 --> 00:51:17,665
ktorý je potom A, X, W, E, L, L. To je
len dátová štruktúra, ktorá ľubovoľne

1096
00:51:17,665 --> 00:51:19,120
je ukladanie mien ľudí.

1097
00:51:19,120 --> 00:51:25,720
A Maxwell je uložený práve týmto
cesta z poľa na pole do poľa.

1098
00:51:25,720 --> 00:51:30,050
Ale čo je to úžasné asi trie je
že, vzhľadom k tomu, Google zoznamu a dokonca

1099
00:51:30,050 --> 00:51:34,520
pole, to najlepšie, čo som kedy dostal, je
lineárny čas alebo logaritmickej čas hľadáte

1100
00:51:34,520 --> 00:51:35,600
niekto up.

1101
00:51:35,600 --> 00:51:40,530
V tejto dátovej štruktúre trie, ak je to
môj dátová štruktúra má jedno meno v ňom

1102
00:51:40,530 --> 00:51:43,720
a ja som hľadal Maxwella, ja som
že ho celkom rýchlo nájsť.

1103
00:51:43,720 --> 00:51:47,910
Ja sa len pozrieť na M-A-X-W-E-L-L. Ak
Táto dátová štruktúra, naopak

1104
00:51:47,910 --> 00:51:51,830
ak N je milión, či je
milión mená v tejto dátovej štruktúry,

1105
00:51:51,830 --> 00:51:57,100
Maxwell sa ešte bude
zistiteľný po práve M-A-X-W-E-L-L,

1106
00:51:57,100 --> 00:51:58,090
kroky.

1107
00:51:58,090 --> 00:52:01,276
A David-- D-A-V-I-D kroky.

1108
00:52:01,276 --> 00:52:03,400
Inými slovami tým, že stavebné
dátová štruktúra, ktorá je

1109
00:52:03,400 --> 00:52:07,240
dostal pričom všetky z týchto polí, všetko
samy podporujú náhodný prístup,

1110
00:52:07,240 --> 00:52:11,090
Môžem začať vzhliadol ľudí'S
názov pomocou množstvo času, ktorý je

1111
00:52:11,090 --> 00:52:14,340
úmerný nie číslo
vecí v dátovej štruktúry,

1112
00:52:14,340 --> 00:52:16,330
ako milión existujúcu mien.

1113
00:52:16,330 --> 00:52:20,135
Množstvo času to trvá mi nájsť
M-A-X-W-E-L-L v tejto dátovej štruktúry je

1114
00:52:20,135 --> 00:52:22,260
úmerný nie je na
veľkosť dátové štruktúry,

1115
00:52:22,260 --> 00:52:25,930
ale k dĺžke názvu.

1116
00:52:25,930 --> 00:52:28,440
A Realisticky
Mená pozeráme hore

1117
00:52:28,440 --> 00:52:29,970
sa nikdy nebude blázon dlho.

1118
00:52:29,970 --> 00:52:32,600
Možno, že niekto má 10 znak
meno, názov 20 znakov.

1119
00:52:32,600 --> 00:52:33,900
Je to určite konečný, že jo?

1120
00:52:33,900 --> 00:52:37,110
Tam je človek na Zemi, ktorý
má najdlhší názov,

1121
00:52:37,110 --> 00:52:39,920
ale to meno je konštantná
hodnota dĺžky, nie?

1122
00:52:39,920 --> 00:52:41,980
To sa nemení v žiadnom zmysle.

1123
00:52:41,980 --> 00:52:45,090
Takže týmto spôsobom, máme
dosiahla dátovú štruktúru

1124
00:52:45,090 --> 00:52:47,800
že je konštantná doba look-up.

1125
00:52:47,800 --> 00:52:50,670
Je to trvať niekoľko krokov
v závislosti na dĺžke vstupe,

1126
00:52:50,670 --> 00:52:54,250
ale nie množstvo názvu
v dátovej štruktúre.

1127
00:52:54,250 --> 00:52:58,700
Takže ak budeme zdvojnásobiť počet mien
v budúcom roku z miliardy do dvoch miliárd,

1128
00:52:58,700 --> 00:53:03,720
nález Maxwell bude trvať
presne rovnaký počet siedmich stupňoch

1129
00:53:03,720 --> 00:53:04,650
ho nájsť.

1130
00:53:04,650 --> 00:53:08,810
A tak sa zdá k dosiahli
náš svätý grál doby chodu.

1131
00:53:08,810 --> 00:53:10,860
>> Takže pár rýchlych oznámenia.

1132
00:53:10,860 --> 00:53:11,850
Kvíz nula sa blíži.

1133
00:53:11,850 --> 00:53:14,600
Viac o tom na internetových stránkach Course
počas najbližších pár dní.

1134
00:53:14,600 --> 00:53:17,120
Pondelkové lecture-- je to sviatok
tu na Harvarde v pondelok.

1135
00:53:17,120 --> 00:53:18,850
Nie je to v New Haven,
takže berieme triedu

1136
00:53:18,850 --> 00:53:20,310
do New Havene pre prednášku v pondelok.

1137
00:53:20,310 --> 00:53:22,550
Všetko bude natočený
a sledovať naživo ako obvykle,

1138
00:53:22,550 --> 00:53:24,900
ale poďme skončiť dnes
s 30 druhého klipu

1139
00:53:24,900 --> 00:53:26,910
zvané "hlboké myšlienky"
podľa Daven Farnham, ktorý

1140
00:53:26,910 --> 00:53:30,850
bol inšpirovaný v minulom roku v sobotu
Night Live "hlboké myšlienky"

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, ktorý
by teraz mala zmysel.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: A teraz, "Hlboké
Myšlienky "od Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tabuľky.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> Reproduktor 1: Dobre, to je pre teraz.

1147
00:53:47,660 --> 00:53:48,805
Uvidíme sa budúci týždeň.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Ak chcete ho vidieť v akcii.

1150
00:53:56,680 --> 00:53:58,304
Takže poďme sa pozrieť na práve teraz.

1151
00:53:58,304 --> 00:53:59,890
Takže tu máme netriedeného poľa.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, môžete ísť dopredu a reštart
to len na jednu sekundu, prosím.

1153
00:54:04,860 --> 00:54:08,562
Dobre, kamery sú rolovacie, tak
akcie vždy, keď budete pripravení, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Dobre, takže to, čo sme
tu je netriedený pole.

1155
00:54:11,020 --> 00:54:13,960
A ja som farebné všetkých prvkov
červeno, čo znamená, že to je, v skutočnosti,

1156
00:54:13,960 --> 00:54:14,460
netriedený.

1157
00:54:14,460 --> 00:54:17,960
Takže pripomenúť, že prvá vec, ktorú robíme
je triedime na ľavej polovici poľa.

1158
00:54:17,960 --> 00:54:20,630
Potom sme triediť právo
polovica poľa.

1159
00:54:20,630 --> 00:54:22,830
A ya-da, da-ya, ya-da,
sme ich spojiť dohromady.

1160
00:54:22,830 --> 00:54:24,520
A máme úplne zotriedené poľa.

1161
00:54:24,520 --> 00:54:25,360
Tak to je, ako zlúčiť nejako funguje.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, hej, hej,
strih, strih, strih, rez.

1163
00:54:27,109 --> 00:54:30,130
Doug, nemôžeš ya-da, ya-da,
ya-da, si cestu cez zlúčenie druhu.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Len som urobil.

1165
00:54:31,970 --> 00:54:32,832
Je to fajn.

1166
00:54:32,832 --> 00:54:33,540
Sme dobré ísť.

1167
00:54:33,540 --> 00:54:34,760
Poďme sa len držať valcovania.

1168
00:54:34,760 --> 00:54:35,380
Tak ako tak,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Musíte vysvetliť
to vo väčšej miere, než to.

1170
00:54:37,800 --> 00:54:39,999
To je jednoducho nestačí.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, my nie
je potrebné sa vrátiť do jedného.

1172
00:54:41,790 --> 00:54:42,350
Je to fajn.

1173
00:54:42,350 --> 00:54:45,690
Takže tak ako tak, ak budeme pokračovať s merge--
Ian sme v polovici natáčania.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Ja viem.

1175
00:54:46,612 --> 00:54:49,320
A my nemôžeme len ya-da, ya-da,
ya-da, celý proces.

1176
00:54:49,320 --> 00:54:52,200
Musíte vysvetliť, ako
Obe strany si spojil.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Ale máme už
vysvetlil, ako dva sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Práve ste zobrazené
im merge poľa.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Poznajú proces.

1180
00:54:56,486 --> 00:54:57,172
Sú v poriadku.

1181
00:54:57,172 --> 00:54:58,380
Šli sme cez to desaťkrát.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Práve si preskočil hneď nad ním.

1183
00:55:00,330 --> 00:55:03,360
Vraciame sa do jedného, ​​vy
nemôžeš ya-da, ya-da cez ňu.

1184
00:55:03,360 --> 00:55:05,480
Dobre, späť do jedného.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Musím sa vrátiť
cez všetky snímky?

1186
00:55:07,833 --> 00:55:08,332
Môj Bože.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Je to ako už po šiestykrát, Ian.

1189
00:55:13,004 --> 00:55:13,940
Je to fajn.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Dobre.

1191
00:55:15,200 --> 00:55:16,590
Ste pripravení?

1192
00:55:16,590 --> 00:55:17,400
Skvelé.

1193
00:55:17,400 --> 00:55:18,950
Akcie.