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

2
00:00:10,900 --> 00:00:15,860
>> Reproduktor 1: Dobře, takže to je
CS50 To je konec týdne pět.

3
00:00:15,860 --> 00:00:19,220
A připomenout, že minule jsme
začal hledat na chovatele dat

4
00:00:19,220 --> 00:00:22,310
struktury, které začaly řešit
problémy, které začaly zavádět

5
00:00:22,310 --> 00:00:25,640
nové problémy, ale, kterého by mělo
byl druh závitem, které jsme

6
00:00:25,640 --> 00:00:27,940
začal dělat z uzlu do uzlu.

7
00:00:27,940 --> 00:00:30,085
Takže to je samozřejmě
singly provázaný seznam.

8
00:00:30,085 --> 00:00:31,960
A jednotlivě propojeny,
Myslím, že je jen jeden

9
00:00:31,960 --> 00:00:33,380
závit mezi každý z těchto uzlů.

10
00:00:33,380 --> 00:00:35,890
Ukázalo se, že můžete dělat milovník
věci, jako je dvojnásobně spojových seznamů

11
00:00:35,890 --> 00:00:38,470
kdy máte šipku
se v obou směrech, což

12
00:00:38,470 --> 00:00:40,320
může pomoci s některými účinností.

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

14
00:00:42,000 --> 00:00:43,500
Jaký problém se to vyřešit?

15
00:00:43,500 --> 00:00:46,620
Proč se staráme v pondělí?

16
00:00:46,620 --> 00:00:49,820
Proč, teoreticky, se staráme v pondělí?

17
00:00:49,820 --> 00:00:50,630
Co to dělá?

18
00:00:50,630 --> 00:00:51,950
>> Diváků: Můžeme dynamicky změnit jeho velikost.

19
00:00:51,950 --> 00:00:53,740
>> Reproduktor 1: OK, tak můžeme
dynamicky změnit jeho velikost.

20
00:00:53,740 --> 00:00:54,710
Výborně vás oba.

21
00:00:54,710 --> 00:00:57,560
Takže můžete dynamicky měnit velikost této
struktura dat, zatímco pole,

22
00:00:57,560 --> 00:01:00,760
Připomeňme, musíte vědět
priori, kolik místa chcete

23
00:01:00,760 --> 00:01:03,870
a pokud budete potřebovat trochu více
prostor, jste trochu smůlu.

24
00:01:03,870 --> 00:01:05,560
Musíte vytvořit zcela nové pole.

25
00:01:05,560 --> 00:01:07,893
Musíte přesunout všechny vaše
data z jednoho na druhého,

26
00:01:07,893 --> 00:01:10,600
nakonec osvobodil starý pole
pokud je to možné, a pak pokračujte.

27
00:01:10,600 --> 00:01:13,891
Která se právě cítí velmi nákladné a velmi
neefektivní, a ve skutečnosti, že může být.

28
00:01:13,891 --> 00:01:14,890
Ale to není všechno dobré.

29
00:01:14,890 --> 00:01:18,180
Platíme cenu, co byl jeden
z více zjevné ceny my

30
00:01:18,180 --> 00:01:20,550
zaplatit pomocí propojeného seznamu?

31
00:01:20,550 --> 00:01:22,825
>> Diváků: Musíme použít
dvojitý prostor pro každou z nich.

32
00:01:22,825 --> 00:01:25,200
Reproduktor 1: Jo, takže potřebujeme
nejméně dvakrát tolik prostoru.

33
00:01:25,200 --> 00:01:27,700
Ve skutečnosti, jsem si uvědomil, tento obrázek je
dokonce i trochu zavádějící,

34
00:01:27,700 --> 00:01:32,200
protože na CS50 IDE v mnoha moderních
počítače, ukazatel nebo adresa

35
00:01:32,200 --> 00:01:33,700
není ve skutečnosti čtyři bajty.

36
00:01:33,700 --> 00:01:36,090
Je to velmi často tito
dny osm bajtů, které

37
00:01:36,090 --> 00:01:38,530
znamená, že spodní část nejvíce
obdélníky tam ve skutečnosti

38
00:01:38,530 --> 00:01:40,900
jsou trochu dvakrát
velký jako to, co jsem se vyvodit,

39
00:01:40,900 --> 00:01:44,409
což znamená, že používáte třikrát jako
velký prostor, jak bychom mít jinak.

40
00:01:44,409 --> 00:01:46,700
Nyní ve stejné době, my jsme
stále mluvil bytů, ne?

41
00:01:46,700 --> 00:01:49,140
My ne nutně mluvit
megabyty nebo gigabyty,

42
00:01:49,140 --> 00:01:51,000
není-li těchto údajů struktury dostat velký.

43
00:01:51,000 --> 00:01:54,510
>> A tak dnes začneme uvažovat
jak bychom mohli prozkoumat údaje

44
00:01:54,510 --> 00:01:57,310
efektivněji, pokud v
Skutečnost, data dostane větší.

45
00:01:57,310 --> 00:02:00,360
Ale pojďme se pokusit se získat kanonická
operace první

46
00:02:00,360 --> 00:02:02,460
že si můžete dělat na tyto
druhy datových struktur.

47
00:02:02,460 --> 00:02:04,790
Takže něco jako připojený
Seznam obecně podporuje

48
00:02:04,790 --> 00:02:07,514
operace, jako smazat,
vložit a vyhledávání.

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

50
00:02:08,639 --> 00:02:11,222
To prostě znamená, že obvykle,
pokud lidé používáte spojový seznam,

51
00:02:11,222 --> 00:02:14,287
oni nebo někdo jiný zavedla
funkce jako mazat, vkládat,

52
00:02:14,287 --> 00:02:16,120
a vyhledávání, takže můžete
skutečně něco dělat

53
00:02:16,120 --> 00:02:18,030
užitečné se strukturou dat.

54
00:02:18,030 --> 00:02:20,760
Takže pojďme se rychle podívat
na to, jak bychom mohli realizovat

55
00:02:20,760 --> 00:02:24,530
nějaký kód pro propojeném seznamu takto.

56
00:02:24,530 --> 00:02:27,885
>> Tak to je jen některé C kód,
Ani kompletní program

57
00:02:27,885 --> 00:02:29,260
že jsem opravdu rychle rozdmýchala.

58
00:02:29,260 --> 00:02:32,300
Není to on-line v distribuci
kód, protože to nebude ve skutečnosti spustit.

59
00:02:32,300 --> 00:02:33,790
Nevšimnout jsem jen
s komentář řekl,

60
00:02:33,790 --> 00:02:36,130
dot dot tečka, je tu něco,
tam, dot dot dot, něco, co tam.

61
00:02:36,130 --> 00:02:38,410
A ať to jen podívat na
jaké jsou šťavnaté díly.

62
00:02:38,410 --> 00:02:40,790
Takže na lince tři,
Připomínáme, že toto je nyní

63
00:02:40,790 --> 00:02:45,960
jsme navrhli deklarovat uzel poslední
čas, jeden z těchto obdélníkových objektů.

64
00:02:45,960 --> 00:02:48,790
Má int, že budeme volat N,
ale my jsme to mohli nazvat cokoliv,

65
00:02:48,790 --> 00:02:51,920
a pak struct uzel hvězdu zvanou další.

66
00:02:51,920 --> 00:02:55,520
A jen aby bylo jasno, že druhým
linka, na lince šest, co to je?

67
00:02:55,520 --> 00:02:57,930
Co to dělá pro nás?

68
00:02:57,930 --> 00:03:01,044
Vzhledem k tomu, to určitě vypadá více
mystický než naše obvyklé proměnné.

69
00:03:01,044 --> 00:03:02,740
>> Diváků: To dělá to pohybovat po jednom.

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

71
00:03:04,650 --> 00:03:08,580
A abych byl přesnější,
to bude ukládat adresu

72
00:03:08,580 --> 00:03:11,582
uzlu, který je určen k
sémanticky vedle ní, že jo?

73
00:03:11,582 --> 00:03:13,540
Takže to nebude
nutně přesunout nic.

74
00:03:13,540 --> 00:03:15,290
Je to jen bude
uložení hodnoty, což je

75
00:03:15,290 --> 00:03:17,170
bude adresa
nějakého jiného uzlu,

76
00:03:17,170 --> 00:03:20,810
a to je důvod, proč jsme řekli struct
uzel hvězda, hvězda označující

77
00:03:20,810 --> 00:03:22,370
ukazatel nebo adresa.

78
00:03:22,370 --> 00:03:26,390
OK, tak teď, pokud předpokládáme, že máme
tento N které máme k dispozici, a pojďme

79
00:03:26,390 --> 00:03:29,490
Předpokládejme, že někdo jiný má
vloženo spoustu celých čísel

80
00:03:29,490 --> 00:03:30,400
do propojeného seznamu.

81
00:03:30,400 --> 00:03:35,640
A to spojový seznam je
ukázal na nějakým bodem

82
00:03:35,640 --> 00:03:39,040
proměnná s názvem seznam, který je
prošel v zde jako parametr,

83
00:03:39,040 --> 00:03:43,120
jak mám jít o linky
14, kterým se provádí vyhledávání?

84
00:03:43,120 --> 00:03:45,990
Jinými slovy, když jsem se provádí
funkce, jejíž účel života

85
00:03:45,990 --> 00:03:48,889
je vzít int a pak se
začátek propojeného seznamu,

86
00:03:48,889 --> 00:03:50,430
že je ukazatel na spojový seznam.

87
00:03:50,430 --> 00:03:52,992
Jako první, kdo se myslím, že David
Byl to náš dobrovolník v pondělí,

88
00:03:52,992 --> 00:03:54,700
ukazoval na
celý spojový seznam,

89
00:03:54,700 --> 00:03:57,820
je to, jako bychom předáváte
David se jako naši argumentaci zde.

90
00:03:57,820 --> 00:03:59,990
Jak můžeme jít o pojížděním tento seznam?

91
00:03:59,990 --> 00:04:04,640
No, to ukáže, že i přesto,
ukazatele jsou relativně nové nyní na nás,

92
00:04:04,640 --> 00:04:07,010
to, co můžeme udělat relativně
přímočaře.

93
00:04:07,010 --> 00:04:09,500
>> Chystám se jít dopředu a
deklarovat dočasnou proměnnou, která

94
00:04:09,500 --> 00:04:12,364
konvencí se jen tak
být nazýván ukazatel, nebo PTR,

95
00:04:12,364 --> 00:04:14,030
ale jste to mohli nazvat, co chcete.

96
00:04:14,030 --> 00:04:16,470
A já jdu na inicializovat
že na začátek seznamu.

97
00:04:16,470 --> 00:04:20,050
Takže se můžete trochu myslet na to
jak se mě učitel na druhý den,

98
00:04:20,050 --> 00:04:23,580
druh ukázal na někoho
mezi našimi lidmi jako dobrovolníci.

99
00:04:23,580 --> 00:04:26,470
Takže jsem dočasné proměnné, které je
jen ukazuje na stejnou věc

100
00:04:26,470 --> 00:04:31,390
že naše shodou okolností s názvem
dobrovolník David byl také poukázat.

101
00:04:31,390 --> 00:04:35,440
Nyní, když je ukazatel
Není null, protože odvolání

102
00:04:35,440 --> 00:04:40,350
že null je nějaký speciální hlídka hodnota
vymezuje konec seznamu,

103
00:04:40,350 --> 00:04:44,280
takže zatímco já nejsem ukazuje na
zem jako náš poslední dobrovolníka

104
00:04:44,280 --> 00:04:47,190
byl, pojďme do toho
a proveďte následující.

105
00:04:47,190 --> 00:04:51,820
Pokud pointer-- a teď jsem trochu chci
dělat to, co jsme dělali se studentem

106
00:04:51,820 --> 00:04:57,410
structure-- pokud ukazatel tečka další
equals-- spíše, je-li ukazatel dot N se rovná

107
00:04:57,410 --> 00:05:02,290
se rovná proměnná N se
Argument, že to už prošel v,

108
00:05:02,290 --> 00:05:05,370
pak chci jít dopředu
a říkají, vrátí hodnotu true.

109
00:05:05,370 --> 00:05:11,020
Zjistil jsem, že číslo N vnitřek
jeden z uzlů mého spojového seznamu.

110
00:05:11,020 --> 00:05:13,500
Ale tečka již
pracuje v této souvislosti,

111
00:05:13,500 --> 00:05:17,260
protože ukazatel, PTR, je
skutečně ukazatel, adresu,

112
00:05:17,260 --> 00:05:20,632
jsme vlastně možné nádherně
použijte konečně kus syntaxe

113
00:05:20,632 --> 00:05:22,590
že druh značek
intuitivní smysl a vlastně

114
00:05:22,590 --> 00:05:27,870
použít šipky tady, což znamená, že jít od
že adresa na celé číslo tam v.

115
00:05:27,870 --> 00:05:30,160
Takže je to velmi podobné
duch operátorem tečky,

116
00:05:30,160 --> 00:05:33,860
ale proto, že ukazatel není ukazatel
a ne skutečný struct sám o sobě,

117
00:05:33,860 --> 00:05:35,380
jsme právě pomocí šipky.

118
00:05:35,380 --> 00:05:40,620
>> Takže v případě, že aktuální uzel, že I je
dočasná proměnná, jsem ukázal na

119
00:05:40,620 --> 00:05:43,060
není N, co chci dělat?

120
00:05:43,060 --> 00:05:45,910
No, s mými lidských dobrovolnících
že jsme zde měli na druhý den,

121
00:05:45,910 --> 00:05:49,710
když je moje první člověk není ten, který jsem
chtějí, a možná druhý člověk není

122
00:05:49,710 --> 00:05:52,660
jediná, kterou chci, a třetí, jsem
je třeba, aby fyzicky v pohybu.

123
00:05:52,660 --> 00:05:54,690
Jako jak mohu procházet seznamem?

124
00:05:54,690 --> 00:05:57,470
Když jsme měli celou řadu ti,
právě udělal jako já a navíc plus.

125
00:05:57,470 --> 00:06:03,660
Ale v tomto případě, stačí
dělat ukazovátko, dostane, ukazatel, další.

126
00:06:03,660 --> 00:06:07,580
Jinými slovy, další pole
je stejně jako všechny levých rukou

127
00:06:07,580 --> 00:06:10,880
že naše lidská dobrovolníci v pondělí
byly pomocí poukázat na nějakém jiném uzlu.

128
00:06:10,880 --> 00:06:12,890
Ti, kteří byli jejich další sousedé.

129
00:06:12,890 --> 00:06:17,060
>> Takže pokud chci krokovat tohoto seznamu,
Nemůžu prostě já a navíc už,

130
00:06:17,060 --> 00:06:20,120
Místo toho musím říci,
Já, ukazatel, se děje

131
00:06:20,120 --> 00:06:24,650
rovnat bez ohledu na další pole,
Další pole je, další pole,

132
00:06:24,650 --> 00:06:28,350
po všech těch levé ruce
že jsme měli na jevišti polohovací

133
00:06:28,350 --> 00:06:30,000
některých dalších hodnot.

134
00:06:30,000 --> 00:06:32,590
A když jsem si přes
že celá iterace,

135
00:06:32,590 --> 00:06:39,330
a konečně, jsem narazila null nemít
nalezeno N přesto, jen jsem return false.

136
00:06:39,330 --> 00:06:44,100
Takže znovu, všechno, co tu děláme,
dle obrázku před chvílí,

137
00:06:44,100 --> 00:06:47,840
začíná poukazem na jednání
začátek seznamu pravděpodobně.

138
00:06:47,840 --> 00:06:50,970
A pak jsem zkontrolovat, je hodnota
Hledám rovná devět?

139
00:06:50,970 --> 00:06:52,650
Pokud ano, vraťte jsem pravda a já jsem udělal.

140
00:06:52,650 --> 00:06:56,450
Pokud ne, mohu aktualizovat svou ruku,
AKA ukazatel na bod

141
00:06:56,450 --> 00:06:59,540
v místě příští Arrow, a
pak umístění při příštím Arrow,

142
00:06:59,540 --> 00:07:00,480
a další.

143
00:07:00,480 --> 00:07:03,770
Já jsem prostě prochází tomto poli.

144
00:07:03,770 --> 00:07:06,010
>> Takže znovu, koho to zajímá?

145
00:07:06,010 --> 00:07:07,861
Stejně jako to, co je to složka pro?

146
00:07:07,861 --> 00:07:10,360
No, připomenout, že jsme zavedli
pojem stohu, který

147
00:07:10,360 --> 00:07:15,400
je abstraktní datový typ, pokud je to
není věc C, to není CS50 věc,

148
00:07:15,400 --> 00:07:19,430
je to abstraktní nápad, tato myšlenka
stohování věci na vrcholu jednoho jiný

149
00:07:19,430 --> 00:07:21,820
, které mohou být prováděny v
svazky různých způsobů.

150
00:07:21,820 --> 00:07:25,600
A jeden způsob, jak jsme navrhovali byl s
pole, nebo s propojeného seznamu.

151
00:07:25,600 --> 00:07:29,570
A ukázalo se, že kanonicky, je
stack podporuje nejméně dvě operace.

152
00:07:29,570 --> 00:07:32,320
A buzz slova jsou tlačit, aby
tlačit něco do zásobníku,

153
00:07:32,320 --> 00:07:34,770
jako nový zásobník v
jídelna, nebo pop,

154
00:07:34,770 --> 00:07:39,000
což znamená, že za účelem odstranění vrchní
zásobník ze zásobníku v jídelně

155
00:07:39,000 --> 00:07:41,500
hala, a pak možná někteří
další operace stejně.

156
00:07:41,500 --> 00:07:45,770
Tak jak můžeme definovat strukturu
že jsme nyní volá hromadu?

157
00:07:45,770 --> 00:07:50,020
>> No, máme všichni jsou k dispozici požadované
syntax máme k dispozici v C. říkám,

158
00:07:50,020 --> 00:07:53,830
Dejte mi definici typu pro
struct uvnitř zásobníku,

159
00:07:53,830 --> 00:07:58,030
Já jsem chtěl říct, je pole, na
celá řada čísel a potom velikost.

160
00:07:58,030 --> 00:08:00,930
Takže jinými slovy, když budu chtít
k provedení tohoto v kódu,

161
00:08:00,930 --> 00:08:03,830
nech mě jít, a tak nějak
kreslit, co to říká.

162
00:08:03,830 --> 00:08:06,317
Tak to říká, dej mi
struktura, která má pole,

163
00:08:06,317 --> 00:08:09,400
a já nevím, co je kapacita,
Je to prý nějaká konstanta, že jsem

164
00:08:09,400 --> 00:08:10,858
definována na jiném místě, a to je v pořádku.

165
00:08:10,858 --> 00:08:15,260
Předpokládejme však, že je to jen jeden,
dva, tři, čtyři, pět.

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

167
00:08:16,700 --> 00:08:21,730
Tento prvek uvnitř mé
struktura bude volaná čísla.

168
00:08:21,730 --> 00:08:24,020
A pak jsem potřebovat
jiné proměnné zřejmě

169
00:08:24,020 --> 00:08:27,814
volal formát, který původně jdu
stanovit je inicializován na nulu.

170
00:08:27,814 --> 00:08:29,730
Pokud není nic v
zásobník, velikost je nula,

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

172
00:08:31,420 --> 00:08:33,450
Nemám ponětí, co je tam ještě ne.

173
00:08:33,450 --> 00:08:36,059
>> Takže pokud chci, aby se zasadila
něco do zásobníku,

174
00:08:36,059 --> 00:08:40,780
Předpokládám, že volání funkce Push, a
Říkám tlačit 50, jako číslo 50,

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

176
00:08:44,090 --> 00:08:47,124
K dispozici je pět různých možných odpovědí.

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

178
00:08:48,790 --> 00:08:51,899
V případě, že cílem zde, opět, zavolejte
funkce Push, předat argument

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

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

181
00:08:55,680 --> 00:08:59,052
Pět possible-- 20% šance
hádat správně.

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

183
00:08:59,896 --> 00:09:00,740
>> Diváků: Daleko vpravo.

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

185
00:09:01,990 --> 00:09:08,359
Tam je nyní 25% šance
hádat správně.

186
00:09:08,359 --> 00:09:09,650
Tak, že by vlastně v pořádku.

187
00:09:09,650 --> 00:09:12,770
Podle konvence, řeknu s řadou,
bychom obecně začít na levé straně,

188
00:09:12,770 --> 00:09:14,519
ale mohli bychom určitě
začít na pravé straně.

189
00:09:14,519 --> 00:09:17,478
Takže spoiler by zde bylo, že jsem
pravděpodobně bude čerpat ji na levé straně,

190
00:09:17,478 --> 00:09:20,060
stejně jako v normálním poli kde
I začít chodit zleva doprava.

191
00:09:20,060 --> 00:09:21,780
Ale pokud můžete převrátit
aritmetický, v pořádku.

192
00:09:21,780 --> 00:09:23,060
Je to prostě není konvenční.

193
00:09:23,060 --> 00:09:24,880
OK, musím udělat jednu
další změna ačkoli.

194
00:09:24,880 --> 00:09:27,710
Teď, když jsem tlačil něco
do zásobníku, co bude dál?

195
00:09:27,710 --> 00:09:29,400
>> Dobře, musím zvýšit velikost.

196
00:09:29,400 --> 00:09:32,600
Tak nech mě jít dopředu a jen
je aktualizuje, který byl nulový.

197
00:09:32,600 --> 00:09:35,950
A místo toho teď, jdu
aby v hodnotě jedna.

198
00:09:35,950 --> 00:09:39,460
A teď, že jsem tlačit další
Číslo do zásobníku, stejně jako 51.

199
00:09:39,460 --> 00:09:42,680
No, musím udělat ještě jeden
změna, která je až do velikosti dvě.

200
00:09:42,680 --> 00:09:46,100
A pak, že jsem tlačit ještě jeden
Číslo do zásobníku, jako je 61,

201
00:09:46,100 --> 00:09:52,530
teď musím aktualizovat velikosti jeden
čas, a získat hodnotu 3 jako velikost.

202
00:09:52,530 --> 00:09:54,690
A teď, že jsem zavolat pop.

203
00:09:54,690 --> 00:09:57,250
Nyní pop, podle konvence,
nebere argument.

204
00:09:57,250 --> 00:10:00,430
Se zásobníkem, celý
bod metafory zásobníku

205
00:10:00,430 --> 00:10:03,450
je to, že nemáte prostor pro uvážení
jít dostat, že zásobník, můžete vše, co udělat

206
00:10:03,450 --> 00:10:06,330
je pop jeden z nejvrchnější
zásobníku, jen proto, že.

207
00:10:06,330 --> 00:10:08,010
To je to, co tato datová struktura dělá.

208
00:10:08,010 --> 00:10:12,250
>> Takže touto logikou, kdybych
říkat pop, co přijde?

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

210
00:10:13,080 --> 00:10:15,402
Takže to, co opravdu je počítač,
dělat v paměti?

211
00:10:15,402 --> 00:10:16,610
Co můj kód musíte udělat?

212
00:10:16,610 --> 00:10:20,330
Co byste navrhli
měníme na obrazovce?

213
00:10:20,330 --> 00:10:23,410
Co by se mělo změnit?

214
00:10:23,410 --> 00:10:24,960
Litovat?

215
00:10:24,960 --> 00:10:26,334
Tak jsme se zbavit 61.

216
00:10:26,334 --> 00:10:27,500
Tak jsem si rozhodně udělat.

217
00:10:27,500 --> 00:10:28,640
A mohu zbavit 61.

218
00:10:28,640 --> 00:10:30,980
A pak to, co ostatní
Změna se má stát?

219
00:10:30,980 --> 00:10:33,160
Velikost má pravděpodobně vrátit se do dva.

220
00:10:33,160 --> 00:10:34,210
A tak to je v pořádku.

221
00:10:34,210 --> 00:10:36,690
Ale počkejte chvíli, velikost
před chvílí byl tři.

222
00:10:36,690 --> 00:10:38,240
Pojďme se jen udělat rychlou kontrolu zdravý rozum.

223
00:10:38,240 --> 00:10:41,810
Jak to víme, že jsme
chtěl se zbavit 61?

224
00:10:41,810 --> 00:10:42,760
Vzhledem k tomu, že jsme praskání.

225
00:10:42,760 --> 00:10:46,450
A tak jsem tuto druhou velikost majetku.

226
00:10:46,450 --> 00:10:48,470
>> Počkej, já jsem
vzpomínal na dvě týden

227
00:10:48,470 --> 00:10:51,660
když jsme začali mluvit o
pole, kam tohle místo nula,

228
00:10:51,660 --> 00:10:55,920
toto bylo umístění jednoho, toto bylo umístění
dvě, to je umístění tří, čtyř,

229
00:10:55,920 --> 00:10:58,460
to vypadá jako
vztah mezi velikostí

230
00:10:58,460 --> 00:11:02,780
a prvek, že chci odstranit
z pole se zdá být jen to, co?

231
00:11:02,780 --> 00:11:05,120
Velikost minus jedna.

232
00:11:05,120 --> 00:11:07,786
A tak to je, jak jako lidé
víme, že šedesát jedna je na prvním místě.

233
00:11:07,786 --> 00:11:09,160
Jak to, že počítač bude vědět?

234
00:11:09,160 --> 00:11:11,701
Když váš kód, kde na vás pravděpodobně
chcete udělat velikost minus jedna,

235
00:11:11,701 --> 00:11:14,950
takže třemi minus jedna jsou dvě, a to
znamená, že chceme zbavit 61.

236
00:11:14,950 --> 00:11:18,000
A pak můžeme skutečně aktualizovat
tak, aby velikost velikost nyní

237
00:11:18,000 --> 00:11:20,300
jde ze tří na pouhé dva.

238
00:11:20,300 --> 00:11:24,520
A jen proto, aby pedantský, jdu
navrhnout, že jsem udělal, že jo?

239
00:11:24,520 --> 00:11:27,660
Ty navrhované intuitivně
správně bych měl zbavit 61.

240
00:11:27,660 --> 00:11:30,700
Ale nemám já druh
nějak zbavili 61?

241
00:11:30,700 --> 00:11:33,790
Já jsem skutečně zapomněl
že je to vlastně tam.

242
00:11:33,790 --> 00:11:37,680
A myslíte, že zpět do PSET4, pokud jste dočetli
Článek o forenzní, PDF

243
00:11:37,680 --> 00:11:40,780
že jsme měli kluci číst, nebo si
bude číst tento týden PSET4.

244
00:11:40,780 --> 00:11:44,300
Připomeňme, že je to vlastně relevantní k
celá myšlenka počítačové forenzní.

245
00:11:44,300 --> 00:11:47,820
Co je počítač obvykle dělá, je
to prostě zapomene, kde je něco,

246
00:11:47,820 --> 00:11:51,300
ale to není jít a podobně
pokusit se poškrábat, nebo ovládání

247
00:11:51,300 --> 00:11:54,560
ty kousky s nul a jedniček
nebo nějaký jiný náhodný vzor

248
00:11:54,560 --> 00:11:56,690
pokud vy sám to záměrně.

249
00:11:56,690 --> 00:11:58,930
Takže vaše intuice byla
Dobře, pojďme se zbavit 61.

250
00:11:58,930 --> 00:12:00,650
Ale ve skutečnosti, my nemusíme obtěžovat.

251
00:12:00,650 --> 00:12:04,040
Potřebujeme jen zapomenout, že
je to tam změnou našeho velikost.

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

253
00:12:05,662 --> 00:12:07,620
Kdybych neustále tlačí věci
do zásobníku, co je

254
00:12:07,620 --> 00:12:11,167
zřejmě bude dít
jen v několik okamžiků čase?

255
00:12:11,167 --> 00:12:12,500
Budeme chybět prostor.

256
00:12:12,500 --> 00:12:13,580
A co budeme dělat?

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

258
00:12:14,680 --> 00:12:19,000
Tato implementace neumožňuje
us změnit velikost pole, protože použití

259
00:12:19,000 --> 00:12:21,240
Tato syntaxe, pokud jste
Vzpomeňte si na dvou týdnů,

260
00:12:21,240 --> 00:12:23,520
poté, co jste prohlásil,
velikost pole,

261
00:12:23,520 --> 00:12:26,780
jsme neviděli mechanismus přesto, kde
můžete změnit velikost pole.

262
00:12:26,780 --> 00:12:29,020
A skutečně C nemá tuto funkci.

263
00:12:29,020 --> 00:12:32,524
Když řeknete, dej mi pět
NTHS, jim říkají čísla,

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

265
00:12:33,940 --> 00:12:38,790
Takže teď budeme dělat od pondělí, má
schopnost vyjadřovat řešení

266
00:12:38,790 --> 00:12:42,480
i když, jen je třeba štípnout
definice našeho stohu

267
00:12:42,480 --> 00:12:46,840
nebýt nějaký pevně pole,
ale jen proto, aby uložit adresy.

268
00:12:46,840 --> 00:12:47,890
>> Nyní, proč je to?

269
00:12:47,890 --> 00:12:51,690
Teď jen musíme být pohodlné s
skutečnost, že když můj program běží,

270
00:12:51,690 --> 00:12:53,730
Já pravděpodobně bude
se zeptat člověka,

271
00:12:53,730 --> 00:12:55,110
kolik čísel chcete uložit?

272
00:12:55,110 --> 00:12:56,776
Takže vstup má přijít odněkud.

273
00:12:56,776 --> 00:12:59,140
Ale jakmile já vím, že
číslo, pak mohu jen

274
00:12:59,140 --> 00:13:02,470
použít to, co funkci, čímž se získá
mi kus paměti?

275
00:13:02,470 --> 00:13:03,580
Mohu použít malloc.

276
00:13:03,580 --> 00:13:06,710
A můžu říct, libovolný počet
bajtů Chci zpátky na tyto NTHS.

277
00:13:06,710 --> 00:13:10,910
A vše, co mám skladovat v číslech
variabilní tady uvnitř tohoto struct

278
00:13:10,910 --> 00:13:13,480
by mělo být to, co?

279
00:13:13,480 --> 00:13:18,440
Co je to vlastně jde do
Čísla v tomto případě?

280
00:13:18,440 --> 00:13:21,300
Jo, ukazatel na první
byte tohoto kusu paměti,

281
00:13:21,300 --> 00:13:24,940
nebo více specificky, adresa
z první z těchto bajtů.

282
00:13:24,940 --> 00:13:27,300
Nezáleží na tom, jestli je to jedno
byte nebo miliarda bajtů,

283
00:13:27,300 --> 00:13:28,890
Jen musím starat o první.

284
00:13:28,890 --> 00:13:31,530
Vzhledem k tomu, co 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ěti I
si, že to bude být souvislé.

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

287
00:13:35,378 --> 00:13:38,576
Takže pokud jsem požádal o 50
bajtů nebo 1000 bajtů,

288
00:13:38,576 --> 00:13:40,450
oni jsou všichni bude
zády k sobě k sobě.

289
00:13:40,450 --> 00:13:44,500
A tak dlouho, jak si vzpomínám, jak velký, jak
moc jsem požádal o, všechno, co potřebuji vědět

290
00:13:44,500 --> 00:13:46,230
Je to první taková adresa.

291
00:13:46,230 --> 00:13:48,660
>> Takže teď máme možnost v kódu.

292
00:13:48,660 --> 00:13:51,280
Ačkoli, že to bude trvat nás
více času psát toto nahoru,

293
00:13:51,280 --> 00:13:55,900
jsme nyní mohli přerozdělit, že paměť
Jen uložení jinou adresu zde

294
00:13:55,900 --> 00:13:59,060
Chceme-li větší, nebo dokonce
menší kus paměti.

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

296
00:14:00,170 --> 00:14:01,360
Teď jsme si dynamiku.

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

298
00:14:03,350 --> 00:14:05,881
Vzhledem k tomu, malloc bude nám
sousedící kus paměti.

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

300
00:14:08,630 --> 00:14:09,770
skutečně kód nahoru.

301
00:14:09,770 --> 00:14:10,730
Je to prostě víc práce.

302
00:14:10,730 --> 00:14:13,930
Potřebujeme kód podobný tomu, co jsem byl
bouchání se před chvílí.

303
00:14:13,930 --> 00:14:16,120
Velmi proveditelné, ale přidává složitost.

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

305
00:14:19,520 --> 00:14:22,520
že bychom mohli muset strávit
nějaký čas, aby se nové funkce.

306
00:14:22,520 --> 00:14:24,020
A pak samozřejmě je zde fronta.

307
00:14:24,020 --> 00:14:26,227
Nebudeme jít do toho
člověk v hodně detailu.

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

309
00:14:27,560 --> 00:14:31,220
Mohl bych implementovat fronty, a
její odpovídající operace,

310
00:14:31,220 --> 00:14:35,660
Přidat do seznamu nebo dequeue, jako je přidat nebo odebrat,
je to jen milovník způsob, jak říct to,

311
00:14:35,660 --> 00:14:38,100
Přidat do seznamu nebo dequeue takto.

312
00:14:38,100 --> 00:14:41,170
Mohu jen dát sám struct
má celou řadu celou řadu, že opět,

313
00:14:41,170 --> 00:14:44,000
má to znovu velikost,
ale proč teď potřebuji

314
00:14:44,000 --> 00:14:46,940
sledovat přední fronty?

315
00:14:46,940 --> 00:14:50,630
Nepotřeboval jsem vědět
přední mého stacku.

316
00:14:50,630 --> 00:14:53,570
No, když jsem znovu pro
queue-- Pojďme se jen těžko

317
00:14:53,570 --> 00:14:57,870
kódovat to jak mít jako pět
celá čísla v potenciálně zde.

318
00:14:57,870 --> 00:15:00,940
Takže to je nula, jedna, dva, tři, čtyři.

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 se bude nazývat velikost.

321
00:15:06,940 --> 00:15:10,056
>> Proč není dostačující
mít jen velikost?

322
00:15:10,056 --> 00:15:11,680
Dobře, pojďme stiskněte tytéž čísla na.

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

324
00:15:14,220 --> 00:15:20,150
Teď budu Zařadí 50, a poté
51, a pak 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
I enqueued 50, pak 51, pak 61.

327
00:15:23,176 --> 00:15:25,050
A to vypadá totožně
do komína tak daleko,

328
00:15:25,050 --> 00:15:27,190
kromě Já třeba, aby se jednu změnu.

329
00:15:27,190 --> 00:15:33,680
Musím aktualizovat této velikosti, takže jdu
od nuly do jednoho na dva až tři nyní.

330
00:15:33,680 --> 00:15:35,760
Jak mohu dequeue?

331
00:15:35,760 --> 00:15:36,890
Co se stane s dequeue?

332
00:15:36,890 --> 00:15:41,950
Kdo by měl přijít z tohoto seznamu jako první
pokud 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 složitější tentokrát.

335
00:15:44,700 --> 00:15:47,880
Vzhledem k tomu, naposledy to byl výborný
snadné prostě velikost minus jedna,

336
00:15:47,880 --> 00:15:51,440
I dostat na konci svého pole účinně
kde čísla jsou, odebere 61.

337
00:15:51,440 --> 00:15:52,920
Ale já nechci, aby odstranit 61.

338
00:15:52,920 --> 00:15:55,030
Chci se 50, který
Byl tam v 5:00 hodin

339
00:15:55,030 --> 00:15:56,790
na line up pro
Nový iPhone nebo kdoví co ještě.

340
00:15:56,790 --> 00:16:01,200
A tak, jak se zbavit 50, I
Nemůžete prostě to udělat, ne?

341
00:16:01,200 --> 00:16:02,547
Můžu vyškrtnout 50.

342
00:16:02,547 --> 00:16:04,380
Ale my jsme řekli jen
nemusí být tak anální

343
00:16:04,380 --> 00:16:06,330
jak na zelené louce, nebo skrýt data.

344
00:16:06,330 --> 00:16:08,090
Můžeme jen zapomněl, kde to je.

345
00:16:08,090 --> 00:16:12,330
>> Ale když změním velikost nyní
dva, je to dostatečné informace

346
00:16:12,330 --> 00:16:15,711
vědět, co se děje v mém frontě?

347
00:16:15,711 --> 00:16:16,680
Opravdu ne.

348
00:16:16,680 --> 00:16:19,830
Stejně jako moje velikost je dva, ale
kde se fronta začíná,

349
00:16:19,830 --> 00:16:22,980
zejména pokud Stále mám
ta stejná čí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 jsem třeba mít na paměti,
Nyní, kdy je přední.

352
00:16:27,090 --> 00:16:29,630
A tak, jak jsem navrhla nahoru
tam budeme právě volal

353
00:16:29,630 --> 00:16:33,729
Nth přední, jejichž původní
hodnota by měla být co?

354
00:16:33,729 --> 00:16:35,270
Zero, jen začátek seznamu.

355
00:16:35,270 --> 00:16:40,876
Ale teď kromě dekrementování
velikost, právě jsme zvýšit přední.

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

357
00:16:42,000 --> 00:16:43,030
Takže jakmile jsem se jít dál.

358
00:16:43,030 --> 00:16:47,520
Předpokládejme, že se jedná o počet
jako je 121, 124, a pak se, sakra,

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

360
00:16:48,610 --> 00:16:50,390
Ale počkejte, já nejsem.

361
00:16:50,390 --> 00:16:55,630
Takže v tomto bodě příběhu,
Předpokládejme, že velikost je jeden, dva,

362
00:16:55,630 --> 00:17:00,370
tři, čtyři, tak předpokládat, že
velikost je čtyři, přední je jedna,

363
00:17:00,370 --> 00:17:01,621
takže 51 je na přední straně.

364
00:17:01,621 --> 00:17:04,329
Chci dát jiné číslo zde,
ale, sakra, já jsem z vesmíru.

365
00:17:04,329 --> 00:17:06,710
Ale já nejsem, že jo?

366
00:17:06,710 --> 00:17:11,192
Tam, kde jsem mohl dát nějaké
další hodnoty, jako je 171?

367
00:17:11,192 --> 00:17:13,400
Jo, mohl bych jen tak
vrátit se tam, že jo?

368
00:17:13,400 --> 00:17:18,161
A pak vyškrtnout na 50, nebo
prostě jej přepsat s 171.

369
00:17:18,161 --> 00:17:20,410
A pokud jste přemýšlel, proč
náš počet se dostal tak náhodný,

370
00:17:20,410 --> 00:17:24,150
Tito jsou obyčejně přijata počítač
přírodovědné předměty na Harvardu po CS50.

371
00:17:24,150 --> 00:17:27,510
Ale to byl dobrý optimalizace,
protože teď jsem to plýtvání místem.

372
00:17:27,510 --> 00:17:30,750
Stále mám na paměti,
jak velká ta věc je totální.

373
00:17:30,750 --> 00:17:31,500
Je to celkem pěti.

374
00:17:31,500 --> 00:17:33,375
Protože nechci, aby
zahájit přepisování 51.

375
00:17:33,375 --> 00:17:36,260
Takže teď jsem ještě z vesmíru,
takže stejný problém jako předtím.

376
00:17:36,260 --> 00:17:39,140
Ale můžete vidět, jak teď
v kódu, budete pravděpodobně

377
00:17:39,140 --> 00:17:41,910
muset trochu psát více
složitost, aby se to stalo.

378
00:17:41,910 --> 00:17:44,510
A ve skutečnosti to, co operátor
v C pravděpodobně umožňuje

379
00:17:44,510 --> 00:17:48,110
budete magicky udělat kruhovitost?

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

381
00:17:50,160 --> 00:17:53,160
Takže to, co je paráda asi fronty,
i když jsme udržet kreslení pole

382
00:17:53,160 --> 00:17:56,520
jak tyto, jako rovných čar, pokud jste
trochu přemýšlet o tom, jak zakřivení

383
00:17:56,520 --> 00:18:00,341
kolem jako kruh, pak stačí
intuitivně to trochu funguje mentálně

384
00:18:00,341 --> 00:18:01,590
Myslím si, že trochu víc čistě.

385
00:18:01,590 --> 00:18:05,190
Ty by se ještě musí zavést
že mentální model v kódu.

386
00:18:05,190 --> 00:18:07,550
Takže není tak těžké,
nakonec, implementovat,

387
00:18:07,550 --> 00:18:12,430
ale stále ztratit size-- poněkud,
schopnost změnit velikost, pokud to uděláme.

388
00:18:12,430 --> 00:18:15,310
>> Musíme se zbavit pole, my
jej nahradit jediným ukazatelem,

389
00:18:15,310 --> 00:18:20,010
a pak se někde v mém kódu mám
Příjem volání, jakou funkci skutečně vytvořit

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

391
00:18:23,720 --> 00:18:26,190
Malloc, nebo nějaký podobný
funkce, přesně tak.

392
00:18:26,190 --> 00:18:30,481
Jakékoliv dotazy týkající komínů nebo frontách.

393
00:18:30,481 --> 00:18:30,980
To 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
Co modulo byste použili zde.

397
00:18:35,830 --> 00:18:38,520
Takže obecně, při použití
mod, měli byste to udělat

398
00:18:38,520 --> 00:18:40,620
s velikostí
Celá struktura dat.

399
00:18:40,620 --> 00:18:44,120
Takže něco jako pět nebo kapacity, je-li
to je konstantní, je pravděpodobně zapojen.

400
00:18:44,120 --> 00:18:47,100
Ale jen to, modulo pět
asi není dostačující,

401
00:18:47,100 --> 00:18:51,380
protože musíme vědět my
zábal kolem zde nebo zde nebo zde.

402
00:18:51,380 --> 00:18:54,160
Takže vy jste pravděpodobně také
bude chtít zapojit

403
00:18:54,160 --> 00:18:57,220
velikost věci, nebo
přední proměnné stejně.

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

405
00:19:00,140 --> 00:19:02,000
ale modulo bude klíčovou složkou.

406
00:19:02,000 --> 00:19:03,330
>> Tak krátký film chcete-li.

407
00:19:03,330 --> 00:19:05,780
Animace, že některé
lidé na jiné vysoké škole

408
00:19:05,780 --> 00:19:08,060
dal dohromady, že máme
přizpůsobené pro tuto diskusi.

409
00:19:08,060 --> 00:19:12,630
To zahrnuje Jack Učení
fakta o frontách a statistiky.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Kdysi dávno,
tam byl chlápek jménem Jack.

412
00:19:21,890 --> 00:19:25,330
Když došlo k tomu, že přátelé,
Jack neměl talent.

413
00:19:25,330 --> 00:19:28,220
Takže Jack šel mluvit s
nejpopulárnější kluk věděl.

414
00:19:28,220 --> 00:19:30,920
On šel do Lou a zeptal se, co mám dělat?

415
00:19:30,920 --> 00:19:33,400
Lou viděl, že jeho přítel
byl opravdu zoufalý.

416
00:19:33,400 --> 00:19:36,050
No, on začal, jen
podívejte se, jak jste oblečen.

417
00:19:36,050 --> 00:19:38,680
Nemáte žádné šaty
s jiným pohledem?

418
00:19:38,680 --> 00:19:39,660
Ano, řekl Jack.

419
00:19:39,660 --> 00:19:40,840
Jsem si jistý, ano.

420
00:19:40,840 --> 00:19:43,320
Pojď do mého domu a
Ukážu vám je.

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

422
00:19:44,550 --> 00:19:47,520
A Jack ukázal na políčko lou
kde on držel všechny své košile,

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

424
00:19:49,260 --> 00:19:52,290
Řekl Lou, vidím, že máte
Všechny vaše oblečení v hromadu.

425
00:19:52,290 --> 00:19:54,870
Proč jste nosit nějaké
jiní jednou za čas?

426
00:19:54,870 --> 00:19:58,020
>> Řekl Jack, dobře, když jsem
odstranit oblečení a ponožky,

427
00:19:58,020 --> 00:20:00,780
I umýt je a dal
je pryč v krabici.

428
00:20:00,780 --> 00:20:03,210
Pak přijde příští
ráno, a já si hop.

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

430
00:20:06,380 --> 00:20:09,070
Lou rychle si uvědomil,
problém s Jackem.

431
00:20:09,070 --> 00:20:12,080
Pořád oblečení, CD,
a knihy v zásobníku.

432
00:20:12,080 --> 00:20:14,420
Když se dostal na
něco ke čtení nebo opotřebení,

433
00:20:14,420 --> 00:20:17,100
že by si vybrat horní knihu nebo spodní prádlo.

434
00:20:17,100 --> 00:20:19,500
Pak, když byl hotov,
by dal to zpátky.

435
00:20:19,500 --> 00:20:21,970
Back to půjde, na vrcholu zásobníku.

436
00:20:21,970 --> 00:20:24,460
Vím, že řešení,
řekl vítězný Loud.

437
00:20:24,460 --> 00:20:27,090
Musíte se naučit
začít používat frontu.

438
00:20:27,090 --> 00:20:29,870
Lou vzal Jackovy šaty a
pověsil je do skříně.

439
00:20:29,870 --> 00:20:32,710
A když vyprázdnil
krabice, prostě hodil.

440
00:20:32,710 --> 00:20:36,500
>> Pak řekl, nyní Jack, na konci roku
den, dát své oblečení na levé straně

441
00:20:36,500 --> 00:20:37,990
když dal je pryč.

442
00:20:37,990 --> 00:20:41,300
Pak se zítra ráno, když vás
vidět slunce, dostat své šaty

443
00:20:41,300 --> 00:20:43,440
Na pravé straně, od konce řádku.

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

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

446
00:20:46,370 --> 00:20:49,770
Budete nosit všechno jednou
Než budete nosit něco dvakrát.

447
00:20:49,770 --> 00:20:52,670
A se vším v frontách
v jeho skříni a policí,

448
00:20:52,670 --> 00:20:55,160
Jack začal cítit
docela jistý sám sebou.

449
00:20:55,160 --> 00:20:59,720
Všechny díky Lou a
Jeho úžasné fronta.

450
00:20:59,720 --> 00:21:01,220
Reproduktor 1: Dobře, 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, co se ve skutečnosti děje
Na pod pokličku teď?

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

454
00:21:12,370 --> 00:21:15,680
že máme schopnost vytvářet
kusy paměti pro sebe

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

456
00:21:16,344 --> 00:21:18,510
Takže tohle je obrázek jsme
zahlédl jen druhý den.

457
00:21:18,510 --> 00:21:21,180
My jsme opravdu přebývat
na to, ale tento obrázek

458
00:21:21,180 --> 00:21:24,180
má se děje pod
odsavač několik týdnů.

459
00:21:24,180 --> 00:21:27,050
A tak to znamená, jen
obdélník, který jsme vyvodit,

460
00:21:27,050 --> 00:21:28,180
paměti počítače.

461
00:21:28,180 --> 00:21:31,850
A možná váš počítač, nebo CS50
ID, má gigabajt paměti nebo RAM

462
00:21:31,850 --> 00:21:33,050
nebo dva gigabajty nebo čtyři.

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

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

465
00:21:37,240 --> 00:21:41,120
v podstatě umožňuje program
myslet si, že má přístup

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

467
00:21:42,982 --> 00:21:45,440
i když byste mohli být spuštěn
více programů najednou.

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

469
00:21:46,990 --> 00:21:49,448
Ale je to trochu iluze
věnovat všechny své programy.

470
00:21:49,448 --> 00:21:53,110
Takže pokud jste měli dva koncerty RAM, toto
je, jak se počítač může myslet na to.

471
00:21:53,110 --> 00:21:57,110
>> Nyní náhodně, jeden z nich
věci, jeden z těchto segmentů paměti,

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

473
00:21:58,350 --> 00:22:01,680
A skutečně kdykoliv
tak daleko v psaní kódu

474
00:22:01,680 --> 00:22:05,900
že jste volal
funkce, například main.

475
00:22:05,900 --> 00:22:08,410
Připomeňme si, že kdykoli jsem
Paměť Drawn počítače,

476
00:22:08,410 --> 00:22:10,640
Vždycky jsem tomu nějak
polovina z obdélníku zde

477
00:22:10,640 --> 00:22:12,520
a neobtěžují mluvit
o tom, co je výše.

478
00:22:12,520 --> 00:22:15,980
Protože když je hlavní volal, tvrdím,
že jste si to plátek paměti

479
00:22:15,980 --> 00:22:16,970
že jde sem dolů.

480
00:22:16,970 --> 00:22:20,650
A pokud hlavní volal funkce
jako odkládací prostor, dobře odkládací jde zde.

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

482
00:22:23,720 --> 00:22:26,277
Na takzvaný stoh
vnitřní paměti vašeho počítače.

483
00:22:26,277 --> 00:22:28,360
Nyní se na konci dne,
to je jen adresy.

484
00:22:28,360 --> 00:22:30,680
Je to jako bajt nula,
byte jednoho, byte 2000000000.

485
00:22:30,680 --> 00:22:33,130
Ale jestli si myslíte, že o tom
jako je obdélníkový objekt,

486
00:22:33,130 --> 00:22:35,130
všechno děláme každý
Doba říkáme funkce

487
00:22:35,130 --> 00:22:37,180
vrstvení nový řez paměti.

488
00:22:37,180 --> 00:22:41,700
Dáváme tuto funkci plátek
ze své vlastní paměti pro práci s.

489
00:22:41,700 --> 00:22:44,490
>> A teď připomínají, že je to důležité.

490
00:22:44,490 --> 00:22:46,400
Vzhledem k tomu, kdybychom se
něco jako odkládací prostor

491
00:22:46,400 --> 00:22:51,610
a dvě lokální proměnné, jako je A a B a
změníme tyto hodnoty z jedné a dvou

492
00:22:51,610 --> 00:22:55,130
na dva a jeden, odvolání
že když se vrátí swapu,

493
00:22:55,130 --> 00:22:58,330
je to, jako by tento plátek
paměti je prostě pryč.

494
00:22:58,330 --> 00:23:00,080
Ve skutečnosti, je to stále
tam forenzně.

495
00:23:00,080 --> 00:23:01,940
A něco je ještě ve skutečnosti tam.

496
00:23:01,940 --> 00:23:05,410
Ale koncepčně, je to, jako
i když je to úplně pryč.

497
00:23:05,410 --> 00:23:10,910
A tak hlavní nezná žádnou z prací
která byla provedena v této funkci odkládacího

498
00:23:10,910 --> 00:23:14,890
pokud je to vlastně prošel v těch
Argumenty ukazatelem nebo odkazem.

499
00:23:14,890 --> 00:23:17,790
Nyní, základní řešení
k tomuto problému s swapu

500
00:23:17,790 --> 00:23:19,970
je kolem věci podle adresy.

501
00:23:19,970 --> 00:23:23,250
Ale ukazuje se, taky, co je
se děje nad tuto část

502
00:23:23,250 --> 00:23:26,330
obdélníku celou dobu je
Ještě je tu více paměti tam nahoře.

503
00:23:26,330 --> 00:23:28,790
A když dynamicky
alokovat paměť,

504
00:23:28,790 --> 00:23:32,020
ať už je to uvnitř getString, který
jsme dělali pro vás v CS50

505
00:23:32,020 --> 00:23:34,710
knihovna, nebo jestli vy
zavolat a zeptat se malloc

506
00:23:34,710 --> 00:23:37,950
operační systém pro kus
paměť, nepochází ze zásobníku.

507
00:23:37,950 --> 00:23:40,960
To pochází z jiného místa
v paměti počítače

508
00:23:40,960 --> 00:23:42,220
Tomu se říká haldy.

509
00:23:42,220 --> 00:23:43,430
A to není nic jiného.

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

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

512
00:23:45,160 --> 00:23:49,080
Je to jen RAM, který se děje
tam místo tady dole.

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

514
00:23:50,750 --> 00:23:53,650
No, pokud má počítač
konečné množství paměti

515
00:23:53,650 --> 00:23:57,450
a zásobník se vyrůstal, takže
mluvit, a haldy, podle

516
00:23:57,450 --> 00:23:59,349
k této šipky, roste dolů.

517
00:23:59,349 --> 00:24:01,140
Jinými slovy, každý
Čas volání malloc,

518
00:24:01,140 --> 00:24:03,430
jste dána plátek
paměti shora,

519
00:24:03,430 --> 00:24:06,630
pak možná o něco nižší, a pak trochu
nižší, pokaždé, když budete volat malloc,

520
00:24:06,630 --> 00:24:10,100
haldy, je to použití,
je druh roste,

521
00:24:10,100 --> 00:24:11,950
roste blíž a blíž k čemu?

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

523
00:24:13,382 --> 00:24:14,840
Takže to zdá jako 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, pokud to není opravdu jasné,
co jiného můžete dělat, když jen

526
00:24:22,140 --> 00:24:23,910
mají omezené množství paměti.

527
00:24:23,910 --> 00:24:25,200
Ale to je určitě špatné.

528
00:24:25,200 --> 00:24:27,920
Tyto dva šípy jsou na
Rychlokurz jeden o druhého.

529
00:24:27,920 --> 00:24:31,930
>> A ukázalo se, že špatný člověk, lidí, kteří
jsou velmi dobré s programováním,

530
00:24:31,930 --> 00:24:36,140
a snaží se proniknout do počítačů,
můžete využít tuto skutečnost.

531
00:24:36,140 --> 00:24:38,290
Ve skutečnosti, uvažujme
trochu úryvek.

532
00:24:38,290 --> 00:24:41,350
Takže toto je příklad si můžete přečíst
o podrobněji na Wikipedii.

533
00:24:41,350 --> 00:24:43,100
Budeme bod, který u
článku, pokud zvědavý.

534
00:24:43,100 --> 00:24:45,650
Ale je tu útok obecně
známý jako přetečení vyrovnávací paměti, že

535
00:24:45,650 --> 00:24:49,570
existuje tak dlouho, jak u lidí
měli schopnost manipulovat

536
00:24:49,570 --> 00:24:53,120
paměť počítače, a to zejména v C.
Tak to je velmi libovolný program

537
00:24:53,120 --> 00:24:55,130
ale pojďme ji přečíst zdola nahoru.

538
00:24:55,130 --> 00:24:57,650
Hlavní do argc char hvězdy argv.

539
00:24:57,650 --> 00:24:59,830
Takže je to program, který bere
argumenty příkazového řádku.

540
00:24:59,830 --> 00:25:03,620
A všechny hlavní dělá zřejmě je výzva
funkce, říkají F pro jednoduchost.

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

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

543
00:25:05,490 --> 00:25:09,320
Tak to přechází do F cokoliv
slovo je, že uživatel zadaný

544
00:25:09,320 --> 00:25:11,500
do příkazového řádku po vyrobení
Název programu vůbec.

545
00:25:11,500 --> 00:25:15,730
Takže stejně jako Caesar nebo Vigenère, který
můžete připomenout děláte s argv.

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

547
00:25:16,680 --> 00:25:19,760
F se v řetězci
jako jeho jediný argument

548
00:25:19,760 --> 00:25:22,100
AKA char hvězda, stejná
věc, jako řetězec.

549
00:25:22,100 --> 00:25:24,920
A je to jen svévolně
bar v tomto příkladu.

550
00:25:24,920 --> 00:25:27,710
A pak char c 12,
jen v Laicky řečeno,

551
00:25:27,710 --> 00:25:31,750
co je char c držák 12 dělá pro nás?

552
00:25:31,750 --> 00:25:33,440
Co to dělá?

553
00:25:33,440 --> 00:25:36,490
Přidělování paměti, konkrétně
12 bytů pro 12 znaků.

554
00:25:36,490 --> 00:25:36,990
Přesně tak.

555
00:25:36,990 --> 00:25:40,000
A pak poslední řádek, zamíchat a
kopírování, pravděpodobně jste ještě neviděli.

556
00:25:40,000 --> 00:25:43,360
To je řetězec kopie
funkce, jejíž účel života

557
00:25:43,360 --> 00:25:48,160
je zkopírovat svůj druhý argument
do první argument,

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

559
00:25:51,190 --> 00:25:53,860
Takže třetí argument říká,
kolik bajtů byste měli kopírovat?

560
00:25:53,860 --> 00:25:56,720
Délka tyče,
bez ohledu na uživatel zadal.

561
00:25:56,720 --> 00:25:59,320
A obsahu
bar, tento řetězec, jsou

562
00:25:59,320 --> 00:26:02,330
zkopírovány do paměti ukázal na při ° C

563
00:26:02,330 --> 00:26:04,060
>> Takže to vypadá trochu hloupé, a to je.

564
00:26:04,060 --> 00:26:06,300
Je to nepřirozený příklad,
ale je to zástupce

565
00:26:06,300 --> 00:26:10,100
třídy vektorů útoku,
způsob, jak útočit program.

566
00:26:10,100 --> 00:26:15,050
Všechno je v pořádku a dobré, pokud uživatel
Typy ve slovech, která je 11 znaků

567
00:26:15,050 --> 00:26:18,040
nebo méně, plus zpětné lomítko nula.

568
00:26:18,040 --> 00:26:22,830
Co když uživatel zadá ve více než
11 nebo 12 nebo 20 nebo 50 znaků?

569
00:26:22,830 --> 00:26:25,090
Co je tento program bude dělat?

570
00:26:25,090 --> 00:26:29,360
Potenciálně seg chyba. Jde to
slepě kopírovat vše, co v baru nahoru

571
00:26:29,360 --> 00:26:31,750
k jeho délce, což je
doslova všechno, co v baru,

572
00:26:31,750 --> 00:26:36,307
do adresního ukázal na C. Ale ° C
má jen preventivně uveden jako 12 bajtů.

573
00:26:36,307 --> 00:26:37,640
Ale není další kontrolu.

574
00:26:37,640 --> 00:26:38,700
Není-li podmínkách.

575
00:26:38,700 --> 00:26:40,580
Neexistuje kontrola tady žádná chyba.

576
00:26:40,580 --> 00:26:43,270
>> A tak to, co je tento program
chystá udělat, je jen slepě

577
00:26:43,270 --> 00:26:45,750
kopírovat jednu věc na druhou.

578
00:26:45,750 --> 00:26:47,880
A tak, když čerpáme to
jako obrázek, tady je

579
00:26:47,880 --> 00:26:49,860
jen tříska paměťového prostoru.

580
00:26:49,860 --> 00:26:53,470
Tak si všimnout na dně, jsme
mají lokální proměnné bar.

581
00:26:53,470 --> 00:26:57,330
Tak, aby ukazatel, který to bude store--
spíše to, že místní argumentu, který je

582
00:26:57,330 --> 00:26:58,672
bude ukládat řetězec bar.

583
00:26:58,672 --> 00:27:00,380
A pak si všimnout jen
nad ní ve stohu,

584
00:27:00,380 --> 00:27:02,505
protože pokaždé, když se ptáte
pro paměť na zásobníku,

585
00:27:02,505 --> 00:27:04,310
to jde trochu
nad ní obrazově,

586
00:27:04,310 --> 00:27:06,270
Všimněte si, že máme 12 bajtů tam.

587
00:27:06,270 --> 00:27:10,690
V levém horním z nich je C držák nula a
vpravo dole nich je C držák 11.

588
00:27:10,690 --> 00:27:12,870
To je jen, jak se počítače
chystá položit ji ven.

589
00:27:12,870 --> 00:27:18,300
Takže jen intuitivně, pokud bar má více
než 12 znaků celkem, včetně

590
00:27:18,300 --> 00:27:25,790
zpětné lomítko nula, kde je
12 nebo C držák 12 jít?

591
00:27:25,790 --> 00:27:28,440
Nebo spíš, kde je 12.
znak nebo 13. znak,

592
00:27:28,440 --> 00:27:30,900
sté postava jít
skončit na obrázku?

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

594
00:27:33,400 --> 00:27:36,300
>> Správně, protože i když
stoh sám roste vzhůru,

595
00:27:36,300 --> 00:27:39,590
jakmile jste dal věci do
to, že z konstrukčních důvodů,

596
00:27:39,590 --> 00:27:41,294
klade paměť od shora dolů.

597
00:27:41,294 --> 00:27:44,460
Takže pokud máte více než 12 bajtů,
budete začít přepsat bar.

598
00:27:44,460 --> 00:27:47,280
Tak to je chyba, ale je to
není opravdu velký problém.

599
00:27:47,280 --> 00:27:51,130
Ale je to velký problém, protože tam je
více věcí se děje v paměti.

600
00:27:51,130 --> 00:27:53,074
Takže tady je návod, jak bychom mohli
dal ahoj, aby bylo jasné.

601
00:27:53,074 --> 00:27:54,490
Pokud jsem napsal v ahoj na příkazovém řádku.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash nula, končí v rámci
tyto 12 bajtů, a my jsme výborný bezpečí.

603
00:27:59,330 --> 00:28:00,330
Vše je v pořádku.

604
00:28:00,330 --> 00:28:03,020
Ale pokud píšu něco
déle, případně je to

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

606
00:28:05,860 --> 00:28:08,405
Ale ještě horší, to dopadá
out celou tu dobu,

607
00:28:08,405 --> 00:28:11,530
i když jsme se nikdy nemluvil o
to, zásobník se používá pro jiné věci.

608
00:28:11,530 --> 00:28:13,560
Není to jen lokální proměnné.

609
00:28:13,560 --> 00:28:15,100
>> C je velmi nízká úroveň jazyka.

610
00:28:15,100 --> 00:28:17,810
A to tak nějak tajně
používá zásobník také

611
00:28:17,810 --> 00:28:21,260
mít na paměti, když se
Funkce je volána, co

612
00:28:21,260 --> 00:28:26,040
je adresa z předchozí funkce,
tak to může skočit zpět na tuto funkci.

613
00:28:26,040 --> 00:28:29,980
Takže když hlavní výzvy výměně, mezi
věci tlačil do fronty

614
00:28:29,980 --> 00:28:34,380
nejsou jen swapy lokální proměnné,
nebo její argumenty, také tajně tlačil

615
00:28:34,380 --> 00:28:37,510
do zásobníku, jak je znázorněno
červeným řezu zde,

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

617
00:28:40,520 --> 00:28:44,180
tak, že když je odkládací provádí, počítač
ví, že je třeba se vrátit k hlavnímu

618
00:28:44,180 --> 00:28:46,760
a dokončit provedení hlavní funkci.

619
00:28:46,760 --> 00:28:51,960
Takže toto je nyní nebezpečné, protože pokud
uživatel zadá v dobře více než ahoj,

620
00:28:51,960 --> 00:28:57,030
taková, že vstup uživatele clobbers
nebo přepíše že červené úsek,

621
00:28:57,030 --> 00:28:59,820
logicky v případě, že počítač je
prostě jít slepě předpokládat,

622
00:28:59,820 --> 00:29:03,830
že byty v tomto červeném plátek jsou
adresa, na kterou by měl vrátit,

623
00:29:03,830 --> 00:29:09,020
co v případě, že protivník je dost chytrý, nebo
štěstí dát posloupnost bytů

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

625
00:29:13,450 --> 00:29:18,730
že on nebo ona chce počítač
provádět místo main?

626
00:29:18,730 --> 00:29:21,670
>> Jinými slovy, jestli to, co se
Uživatel je psaní na výzvy,

627
00:29:21,670 --> 00:29:23,850
Není to jen něco,
neškodný jako Dobrý den,

628
00:29:23,850 --> 00:29:28,210
ale je to vlastně kód, který je rovnocenný
vymazat všechny soubory tohoto uživatele?

629
00:29:28,210 --> 00:29:30,060
Nebo e-mailem své heslo ke mně?

630
00:29:30,060 --> 00:29:31,940
Nebo začít protokolování jejich
kláves, že jo?

631
00:29:31,940 --> 00:29:34,920
Existuje způsob, pojďme stanovit dnes,
že by mohli zadejte není jen ahoj

632
00:29:34,920 --> 00:29:36,711
world nebo jejich jméno,
mohli v podstatě

633
00:29:36,711 --> 00:29:39,570
předat kódů, nuly a
ty, že je počítač

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

635
00:29:43,450 --> 00:29:48,950
Takže i když poněkud abstraktně, v případě, že
uživatel zadá v dostatečném sporného kódu

636
00:29:48,950 --> 00:29:52,330
že budeme zobecnit zde
A. A je útok nebo protivníci.

637
00:29:52,330 --> 00:29:53,140
Takže jen špatné věci.

638
00:29:53,140 --> 00:29:55,306
My se nestarají o
čísla nebo nuly, nebo ty,

639
00:29:55,306 --> 00:29:59,470
dnes, takže můžete skončit
přepisování, že červená část,

640
00:29:59,470 --> 00:30:01,580
Všimněte si, že pořadí bajtů.

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

642
00:30:05,020 --> 00:30:08,960
A teď, když na Wikipedii článek zde
navrhla, pokud si nyní skutečně začít

643
00:30:08,960 --> 00:30:12,460
označování bajtů v počítače
paměť, co článek Wikipedie

644
00:30:12,460 --> 00:30:19,060
navrhující je, že to, co v případě, že adresa
tohoto levém horním bytu je 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Jinými slovy, pokud je špatný chlap je
dost chytrý s jeho nebo její kód

646
00:30:22,200 --> 00:30:26,650
skutečně vložit číslo, které zde
odpovídá na adresu kódu

647
00:30:26,650 --> 00:30:29,180
on nebo ona injekčně
do počítače,

648
00:30:29,180 --> 00:30:31,050
která dokáže oklamat počítač
do něco dělat.

649
00:30:31,050 --> 00:30:34,140
Odstranění souborů, posílání e-mailů
věci, čichání svůj provoz,

650
00:30:34,140 --> 00:30:36,710
doslova něco mohlo být
vstřikuje do počítače.

651
00:30:36,710 --> 00:30:39,220
A tak přetečení vyrovnávací paměti
útok ve svém jádru

652
00:30:39,220 --> 00:30:43,530
je jen hloupá, hloupá
Prvořadým z pole, který

653
00:30:43,530 --> 00:30:45,840
neměl kontrolovat jeho hranice.

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

655
00:30:48,850 --> 00:30:52,560
v C je, že jsme skutečně mají
přístup k kdekoli v paměti.

656
00:30:52,560 --> 00:30:55,320
Je to na nás, programátoři,
kteří píší původní kód

657
00:30:55,320 --> 00:30:59,330
zkontrolovat délku zašít některého
polí, že jsme manipulovali.

658
00:30:59,330 --> 00:31:00,750
Tak, aby bylo jasné, co je to oprava?

659
00:31:00,750 --> 00:31:03,190
Pokud bychom se vrátit k tomu
kód, měl bych to nejen

660
00:31:03,190 --> 00:31:08,000
změnit délku tyče, co
jinak bych měl zkontrolovat?

661
00:31:08,000 --> 00:31:10,620
Co jiného bych měl dělat, aby
zabránit zcela tento útok?

662
00:31:10,620 --> 00:31:14,110
Nechci, aby jen slepě říct
že byste měli zkopírovat tolik bajtů

663
00:31:14,110 --> 00:31:16,140
jako je délka tyče.

664
00:31:16,140 --> 00:31:18,910
Chci říci, kopírování as
mnoho bajtů jako jsou v barech

665
00:31:18,910 --> 00:31:24,090
až do přidělené
paměť, nebo 12 maximálně.

666
00:31:24,090 --> 00:31:27,450
Tak jsem potřebovat nějaký, pokud stav
která dělá zkontrolujte délku tyče,

667
00:31:27,450 --> 00:31:32,800
ale pokud překročí 12, jen jsme pevný kód
12 jako maximální možné vzdálenosti.

668
00:31:32,800 --> 00:31:35,910
V opačném případě takzvaný vyrovnávací paměti
overflow útoku se může stát.

669
00:31:35,910 --> 00:31:38,451
V dolní části těchto snímků,
pokud jste zvědaví číst více

670
00:31:38,451 --> 00:31:41,200
je skutečný původní článek
pokud byste chtěli, aby se podívat.

671
00:31:41,200 --> 00:31:44,550
>> Ale teď, mezi cenami
Zde zaplatil byl neefektivní.

672
00:31:44,550 --> 00:31:46,680
Takže to byla rychlá
nízká úroveň pohled na to, co

673
00:31:46,680 --> 00:31:49,709
Problémy mohou vznikat nyní, že jsme
mají přístup do paměti počítače.

674
00:31:49,709 --> 00:31:51,750
Ale další problém, který jsme
Už narazil v pondělí

675
00:31:51,750 --> 00:31:53,800
byl jen neefektivnost
propojeného seznamu.

676
00:31:53,800 --> 00:31:56,019
Jsme zpátky do lineárního času.

677
00:31:56,019 --> 00:31:57,560
Máme již nemají souvislou řadu.

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

679
00:31:58,980 --> 00:32:00,710
Nemůžeme použít hranatou závorku notace.

680
00:32:00,710 --> 00:32:04,590
Máme doslova muset použít while
jako ten, který jsem napsal před chvílí.

681
00:32:04,590 --> 00:32:09,740
Ale v pondělí, jsme tvrdili, že můžeme
vplížit zpět do říše účinnosti

682
00:32:09,740 --> 00:32:13,040
dosažení něco, co je
logaritmický možná, nebo nejlepší přesto,

683
00:32:13,040 --> 00:32:16,120
možná i něco, co je
tzv časová konstanta.

684
00:32:16,120 --> 00:32:19,840
Tak jak můžeme udělat, že při použití tyto nové
nástroje, tyto adresy, těchto ukazatelů,

685
00:32:19,840 --> 00:32:22,210
a řezání závitů věci vlastní?

686
00:32:22,210 --> 00:32:23,960
No, předpokládám, že
tady, to jsou banda

687
00:32:23,960 --> 00:32:27,170
čísel, které chceme uložit v
struktura a vyhledávání dat efektivně.

688
00:32:27,170 --> 00:32:30,960
Můžeme zcela přetočit do týdne
dva, hodit je do pole,

689
00:32:30,960 --> 00:32:33,150
a vyhledávání je pomocí binárního vyhledávání.

690
00:32:33,150 --> 00:32:34,040
Rozděl a panuj.

691
00:32:34,040 --> 00:32:37,720
A ve skutečnosti jste napsal
binární vyhledávání v PSET3,

692
00:32:37,720 --> 00:32:40,100
kde jste zavedli program find.

693
00:32:40,100 --> 00:32:40,890
Ale víte co.

694
00:32:40,890 --> 00:32:45,060
Tam je trochu více
chytrý způsob, jak toho dosáhnout.

695
00:32:45,060 --> 00:32:47,390
Je to trochu víc
sofistikované a to možná

696
00:32:47,390 --> 00:32:50,830
nám umožňuje vidět, proč binární
Vyhledávání je tak mnohem rychlejší.

697
00:32:50,830 --> 00:32:52,980
Za prvé, pojďme představit
pojem stromu.

698
00:32:52,980 --> 00:32:54,730
Které, i když v
reality stromy druh

699
00:32:54,730 --> 00:32:57,730
rostou jako to, ve světě počítačů
věda, že druh rostou směrem dolů

700
00:32:57,730 --> 00:33:00,830
jako rodinný strom, kde máte
vaši prarodiče nebo prarodiče

701
00:33:00,830 --> 00:33:04,580
nebo kdoví co ještě na vrcholu, patriarcha a
matriarch rodiny, jen jeden

702
00:33:04,580 --> 00:33:07,930
tzv kořen, uzel, níže
které jsou jeho děti,

703
00:33:07,930 --> 00:33:11,442
pod kterou jsou jeho děti, nebo
jeho potomci obecněji.

704
00:33:11,442 --> 00:33:13,400
A někdo visí
spodní rodiny

705
00:33:13,400 --> 00:33:16,070
tree, vedle být
nejmladší v rodině,

706
00:33:16,070 --> 00:33:19,520
může být jen také obecně
volal listy stromu.

707
00:33:19,520 --> 00:33:21,800
>> Tak to je jen banda
slov a definic

708
00:33:21,800 --> 00:33:25,790
pro něco, co se nazývá strom v počítači
věda, podobně jako rodokmenu.

709
00:33:25,790 --> 00:33:28,770
Ale je tu milovník inkarnací
stromů, z nichž jedna

710
00:33:28,770 --> 00:33:30,780
se nazývá binární vyhledávací strom.

711
00:33:30,780 --> 00:33:34,380
A můžete druh vtipálek
kromě toho, co tahle věc dělá.

712
00:33:34,380 --> 00:33:37,180
No, je to binární v jakém smyslu?

713
00:33:37,180 --> 00:33:41,455
Odkud binární pochází tady?

714
00:33:41,455 --> 00:33:41,955
Litovat?

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

716
00:33:45,961 --> 00:33:47,210
To není ani tak nebo.

717
00:33:47,210 --> 00:33:52,000
Je to spíše, že každý z uzlů nemá
více než dvě děti, protože zde vidíme.

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

719
00:33:54,990 --> 00:33:57,640
může mít tolik dětí, nebo
vnoučata, jak se ve skutečnosti chtějí,

720
00:33:57,640 --> 00:34:00,820
a tak například tam máme tři
děti z toho pravého uzlu,

721
00:34:00,820 --> 00:34:05,480
ale v binárním stromu, uzel má
nula, jedna nebo dvě děti maximálně.

722
00:34:05,480 --> 00:34:08,496
A to je pěkná vlastnost,
protože pokud je limitován dvěma,

723
00:34:08,496 --> 00:34:10,620
budeme moci
si trochu log základnu dvou

724
00:34:10,620 --> 00:34:11,975
akce děje nakonec.

725
00:34:11,975 --> 00:34:13,350
Takže máme něco logaritmické.

726
00:34:13,350 --> 00:34:14,558
Ale o tom více za chvíli.

727
00:34:14,558 --> 00:34:19,810
Vyhledávací strom znamená, že čísla jsou
uspořádány tak, že levá dítěte

728
00:34:19,810 --> 00:34:22,429
hodnota je větší než kořene.

729
00:34:22,429 --> 00:34:26,010
A jeho právo dítě
větší než kořene.

730
00:34:26,010 --> 00:34:29,290
Jinými slovy, pokud budete mít některý z
uzly, kruhy v tomto obrázku,

731
00:34:29,290 --> 00:34:31,840
a dívá se na její levé straně
Dítě a jeho právo dítěte,

732
00:34:31,840 --> 00:34:34,739
První by měla být nižší než,
druhá by měla být větší než.

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

734
00:34:36,159 --> 00:34:37,780
Je to nechal dítě je 33.

735
00:34:37,780 --> 00:34:38,620
To je méně než.

736
00:34:38,620 --> 00:34:40,929
55, jeho právo dítě je 77.

737
00:34:40,929 --> 00:34:41,783
To je větší než.

738
00:34:41,783 --> 00:34:43,199
A to je rekurzivní definice.

739
00:34:43,199 --> 00:34:46,480
Mohli bychom zkontrolovat každý jeden z těch,
uzly a stejný vzor by se držet.

740
00:34:46,480 --> 00:34:49,389
>> Takže to, co je milé v
binární vyhledávací strom, je

741
00:34:49,389 --> 00:34:52,204
že jeden, můžeme jej realizovat
s struct, stejně jako tato.

742
00:34:52,204 --> 00:34:54,620
A i když jsme házení
spousta staveb na dosah,

743
00:34:54,620 --> 00:34:56,560
oni jsou poněkud
intuitivní teď nadějně.

744
00:34:56,560 --> 00:35:00,570
Syntaxe je stále tajemný pro jistotu,
ale obsah uzlu v této

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

746
00:35:02,786 --> 00:35:04,910
ať už je to obdélník
na obrazovku nebo do kruhu,

747
00:35:04,910 --> 00:35:08,970
je to jen nějaký obecný kontejner,
V tomto případě stromu, jako je ta

748
00:35:08,970 --> 00:35:11,780
jsme viděli, potřebujeme číslo
v každém z uzlů

749
00:35:11,780 --> 00:35:15,460
a pak jsem třeba dva ukazatelů ukazujících
do levého dítě a pravé dítě,

750
00:35:15,460 --> 00:35:16,590
v tomto pořadí.

751
00:35:16,590 --> 00:35:20,730
Tak to je to, jak bychom mohli
nářadí, které v Struct.

752
00:35:20,730 --> 00:35:22,315
A jak bych mohl realizovat ji v kódu?

753
00:35:22,315 --> 00:35:26,730
Dobře, pojďme se rychle
podívejte se na tento malý příklad.

754
00:35:26,730 --> 00:35:29,820
Není to funkční, ale já jsem
zkopírovat a vložit tuto strukturu.

755
00:35:29,820 --> 00:35:33,510
A když je moje funkce pro binární
vyhledávací strom se nazývá hledání,

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

757
00:35:36,980 --> 00:35:41,400
do uzlu, takže ukazatel na stromu
nebo ukazatel ke kořeni stromu,

758
00:35:41,400 --> 00:35:43,482
Jak mám jít o hledání N?

759
00:35:43,482 --> 00:35:45,440
No, v první, protože jsem
jednání s ukazateli,

760
00:35:45,440 --> 00:35:46,750
Budu dělat kontrolu zdravý rozum.

761
00:35:46,750 --> 00:35:54,279
Pokud strom rovná rovná null, je N
v této větvi nebo není v této větvi?

762
00:35:54,279 --> 00:35:55,070
To nemůže být, že jo?

763
00:35:55,070 --> 00:35:56,870
Jestliže jsem v minulosti null,
tam nic není.

764
00:35:56,870 --> 00:35:59,230
Já bych mohl také právě
slepě říkají return false.

765
00:35:59,230 --> 00:36:04,050
Pokud mi nic, rozhodně nemůžu
najít libovolný počet N. Takže co jiného bych mohl

766
00:36:04,050 --> 00:36:04,750
zjistit teď?

767
00:36:04,750 --> 00:36:12,830
Chystám se říct i jinak, pokud N je
menší než to, co je v uzlu stromu

768
00:36:12,830 --> 00:36:16,300
že jsem byla předána hodnota n.

769
00:36:16,300 --> 00:36:20,270
Jinými slovy, pokud je číslo nejsem
hledá, N, je menší, než uzel

770
00:36:20,270 --> 00:36:21,340
že jsem při pohledu na.

771
00:36:21,340 --> 00:36:23,190
A uzel se dívám
u se nazývá strom,

772
00:36:23,190 --> 00:36:26,370
a vyvolat z předchozího příkladu
se dostat na hodnotu v ukazateli,

773
00:36:26,370 --> 00:36:28,310
Používám notaci se šipkou.

774
00:36:28,310 --> 00:36:35,960
Takže pokud N je menší než stromu šipky
N, chci koncepčně jít doleva.

775
00:36:35,960 --> 00:36:38,590
Jak mohu express vyhledávání odešel?

776
00:36:38,590 --> 00:36:41,560
Aby bylo jasno, zda se jedná
obraz v otázce,

777
00:36:41,560 --> 00:36:44,612
a byl jsem prošel, že nejvyšší
šipka, která je směrem dolů.

778
00:36:44,612 --> 00:36:45,570
To je můj strom ukazatel.

779
00:36:45,570 --> 00:36:48,060
Já jsem ukázal na kořen stromu.

780
00:36:48,060 --> 00:36:52,100
A já hledám řekněme, pro
číslo 44, libovolně.

781
00:36:52,100 --> 00:36:55,300
Je menší než 44, nebo
větší než 55 zřejmě?

782
00:36:55,300 --> 00:36:56,360
Takže je to méně než.

783
00:36:56,360 --> 00:36:58,760
A tak, pokud podmínka platí.

784
00:36:58,760 --> 00:37:03,981
Tak koncepčně, co chci
hledat další, když jsem hledal 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Přesně tak, chci
vyhledávat levé dítě,

788
00:37:11,100 --> 00:37:12,789
nebo doleva sub-strom obrázku.

789
00:37:12,789 --> 00:37:14,830
A ve skutečnosti, dovolte mi, abych prostřednictvím
obrázek tady dole

790
00:37:14,830 --> 00:37:17,770
jen na chvíli, protože
Nemůžu poškrábání to.

791
00:37:17,770 --> 00:37:21,150
Pokud začnu tady na 55, a
Vím, že hodnota 44

792
00:37:21,150 --> 00:37:23,180
Já jsem hledal je
levá, je to druh

793
00:37:23,180 --> 00:37:26,010
jako se trhá telefonní seznam v
polopenze nebo trhání strom na polovinu.

794
00:37:26,010 --> 00:37:29,660
Já už muset starat o
Celá tato polovina stromu.

795
00:37:29,660 --> 00:37:33,270
A přesto, zvědavě v termínech
struktura, tohle tady, že

796
00:37:33,270 --> 00:37:36,682
začíná 33, které samo o sobě
je binární vyhledávací strom.

797
00:37:36,682 --> 00:37:39,890
Řekl jsem to slovo rekurzivní dříve, protože
ve skutečnosti to je datová struktura, která

798
00:37:39,890 --> 00:37:41,707
podle definice je rekurzivní.

799
00:37:41,707 --> 00:37:44,540
Možná budete mít strom, který je tento
velký, ale každý z jejích dětí

800
00:37:44,540 --> 00:37:46,870
představuje strom jen trochu menší.

801
00:37:46,870 --> 00:37:50,910
Namísto toho, že děda
nebo babička, teď je to jen máma

802
00:37:50,910 --> 00:37:54,300
nebo-- Nemůžu say-- není máma
nebo táta, to by bylo divné.

803
00:37:54,300 --> 00:37:59,000
Místo toho tam dvě děti
by byl jako bratr a sourozenci.

804
00:37:59,000 --> 00:38:01,120
Nová generace rodinného stromu.

805
00:38:01,120 --> 00:38:02,900
Ale strukturálně, je to stejný nápad.

806
00:38:02,900 --> 00:38:06,790
A ukázalo se, že mám funkci
s nimiž mohu vyhledávat binární vyhledávání

807
00:38:06,790 --> 00:38:07,290
strom.

808
00:38:07,290 --> 00:38:08,680
Nazývá se vyhledávání.

809
00:38:08,680 --> 00:38:17,870
I hledat N ve stromu Šipka doleva
else if N je větší než hodnota

810
00:38:17,870 --> 00:38:18,870
že jsem v současné době.

811
00:38:18,870 --> 00:38:20,800
55 v příběhu před chvílí.

812
00:38:20,800 --> 00:38:23,780
Mám funkci nazvanou
Hledání, který mohu jen

813
00:38:23,780 --> 00:38:29,660
projít N a to rekurzivně vyhledávání
sub-strom a právě návrat

814
00:38:29,660 --> 00:38:30,620
co to odpověď.

815
00:38:30,620 --> 00:38:33,530
Jinak mám nějaké finální základní případ tady.

816
00:38:33,530 --> 00:38:35,310
>> Jaká je konečná případ?

817
00:38:35,310 --> 00:38:36,570
Strom je buď nulový.

818
00:38:36,570 --> 00:38:39,980
Hodnota jsem buď hledal je
menší než, nebo větší než

819
00:38:39,980 --> 00:38:42,610
nebo rovna to.

820
00:38:42,610 --> 00:38:44,750
A mohl bych říct, rovná
rovni, ale logicky je to

821
00:38:44,750 --> 00:38:46,500
což odpovídá jen říkám, že tady jinde.

822
00:38:46,500 --> 00:38:49,150
Takže pravda je, jak jsem se něco najít.

823
00:38:49,150 --> 00:38:51,710
Tak doufejme, že to je
ještě přesvědčivější příklad

824
00:38:51,710 --> 00:38:54,900
než stupidní funkce sigma
jsme udělali několik přednášek zpět,

825
00:38:54,900 --> 00:38:58,360
kde to bylo stejně snadné používat smyčku
spočítat všechna čísla od jedničky

826
00:38:58,360 --> 00:39:02,390
N. Zde s datovou strukturu
který sám o sobě je rekurzivně

827
00:39:02,390 --> 00:39:07,050
definované a rekurzivně vyvodit, teď jsme
mají schopnost vyjádřit sebe

828
00:39:07,050 --> 00:39:09,780
V kódu, který sám o sobě je rekurzivní.

829
00:39:09,780 --> 00:39:12,580
Tak to je přesně stejný kód zde.

830
00:39:12,580 --> 00:39:14,400
>> Takže to, co další problémy můžeme vyřešit?

831
00:39:14,400 --> 00:39:18,160
Tak rychlý krůček od
stromy na chvilku.

832
00:39:18,160 --> 00:39:20,130
Zde je, řekněme, pod německou vlajkou.

833
00:39:20,130 --> 00:39:22,020
A je tu jednoznačně
vzor tohoto parametru.

834
00:39:22,020 --> 00:39:23,811
A je tu spousta
Vlajky na světě, který

835
00:39:23,811 --> 00:39:27,560
jsou tak jednoduché, jak je to z hlediska
jejich barev a vzorů.

836
00:39:27,560 --> 00:39:31,930
Ale předpokládejme, že tento je uložen jako
GIF, nebo JPEG, nebo bitmapové, nebo ping,

837
00:39:31,930 --> 00:39:34,240
jakýkoli grafický formát souboru
, se kterým jste se seznámili,

838
00:39:34,240 --> 00:39:36,460
z nichž některé jsme
hrát s v PSET4.

839
00:39:36,460 --> 00:39:41,550
To se zdá jako velice užitečné pro ukládání
Černý pixel, černý pixel, černý pixel,

840
00:39:41,550 --> 00:39:44,790
tečka, tečka, tečka, celá parta
černé pixely pro první scanline,

841
00:39:44,790 --> 00:39:47,430
nebo řádku, pak celá parta
stejné, pak se celý svazek

842
00:39:47,430 --> 00:39:49,530
of stejné, a pak
Celá banda červených pixelů,

843
00:39:49,530 --> 00:39:53,020
červené pixely, červené pixely, potom celý
banda žlutých pixelů, žlutá, že jo?

844
00:39:53,020 --> 00:39:55,050
>> Je tu takový neefektivnost sem.

845
00:39:55,050 --> 00:39:59,040
Jak byste intuitivně
stlačit pod německou vlajkou

846
00:39:59,040 --> 00:40:01,320
pokud se provádí jako soubor?

847
00:40:01,320 --> 00:40:04,940
Jako jaké informace nemůžeme
obtěžovat ukládání na disk v pořadí

848
00:40:04,940 --> 00:40:08,040
snížit naši velikost souboru z podobně
megabajt na kilobyte, něco

849
00:40:08,040 --> 00:40:09,430
menší?

850
00:40:09,430 --> 00:40:13,130
V čem spočívá redundance
zde musí být jasné?

851
00:40:13,130 --> 00:40:13,880
Co jsi to mohl udělat?

852
00:40:13,880 --> 00:40:14,380
To jo?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Přesně tak.

855
00:40:21,970 --> 00:40:24,550
Proč raději než vzpomenout
barva každého pixelu zašít

856
00:40:24,550 --> 00:40:28,200
stejně jako to děláte v PSET4
s formátem bitmapový obrázek,

857
00:40:28,200 --> 00:40:32,060
proč si prostě představují
vlevo sloupec obrazových bodů, například

858
00:40:32,060 --> 00:40:35,370
banda černých pixelů, parta
červené a banda žluté,

859
00:40:35,370 --> 00:40:39,210
a pak už jen nějak zakódovat
idea Opakujte tento 100 krát

860
00:40:39,210 --> 00:40:41,020
nebo zopakovat tento 1,000 časů?

861
00:40:41,020 --> 00:40:43,430
V případě, 100 nebo 1000, je
jen číslo, takže si

862
00:40:43,430 --> 00:40:47,290
může dostat pryč jen s jedním číslem
namísto stovek nebo tisíců

863
00:40:47,290 --> 00:40:48,270
dodatečných pixelů.

864
00:40:48,270 --> 00:40:50,990
A opravdu, to je, jak jsme
by mohlo stlačit pod německou vlajkou.

865
00:40:50,990 --> 00:40:51,490
A

866
00:40:51,490 --> 00:40:53,470
A teď, co o francouzskou vlajkou?

867
00:40:53,470 --> 00:40:58,930
A trochu jakýsi
mentální cvičení, které vlajka

868
00:40:58,930 --> 00:41:01,040
mohou být komprimovány více na disku?

869
00:41:01,040 --> 00:41:05,720
Německé vlajky nebo francouzská
vlajky, vezmeme-li tento přístup?

870
00:41:05,720 --> 00:41:08,490
Německá vlajka, protože tam je
více horizontální redundance.

871
00:41:08,490 --> 00:41:12,190
A podle návrhu, mnozí grafický soubor
formáty skutečně pracovat jako rozkladové řádky

872
00:41:12,190 --> 00:41:12,830
horizontálně.

873
00:41:12,830 --> 00:41:14,674
Mohly by fungovat
vertikálně, jen lidstvo

874
00:41:14,674 --> 00:41:17,090
Před lety se rozhodli, že budeme
obecně myslet na věci, řady

875
00:41:17,090 --> 00:41:18,880
řádkem namísto řádku po řádce.

876
00:41:18,880 --> 00:41:20,820
Takže opravdu, pokud jste byli
se podívat na soubor

877
00:41:20,820 --> 00:41:24,670
velikost německou vlajkou a francouzštině
flag, tak dlouho, dokud je rozlišení

878
00:41:24,670 --> 00:41:27,530
stejné, stejnou šířku
a výška, tahle

879
00:41:27,530 --> 00:41:31,580
Zde bude větší, protože
muset opakovat sami třikrát.

880
00:41:31,580 --> 00:41:35,570
Musíte zadat modrá, opakování
sami, bílá, opakovat sami, červená,

881
00:41:35,570 --> 00:41:36,740
opakovat se.

882
00:41:36,740 --> 00:41:39,000
Nemůžete prostě jít all
cesta doprava.

883
00:41:39,000 --> 00:41:41,200
A jako stranou, aby se
zrušte komprese

884
00:41:41,200 --> 00:41:43,910
je všude, pokud se jedná o
Čtyři rámy z video-- vás

885
00:41:43,910 --> 00:41:45,890
by mohl připomenout, že filmu
nebo video je obecně

886
00:41:45,890 --> 00:41:47,286
jako je 29 nebo 30 snímků za sekundu.

887
00:41:47,286 --> 00:41:50,410
Je to jako malé flip knihy, kde vás
Jen viz obrázek, obrázek, image, image,

888
00:41:50,410 --> 00:41:54,410
image prostě super rychlý, takže to vypadá,
herci na obrazovce se pohybují.

889
00:41:54,410 --> 00:41:57,130
Zde je bumble včela na
Vrchol kytice.

890
00:41:57,130 --> 00:41:59,790
A i když to by mohlo být trochu
těžké vidět na první pohled,

891
00:41:59,790 --> 00:42:04,020
Jediná věc, pohybující se v
tento film je včela.

892
00:42:04,020 --> 00:42:06,880
>> Co je němý o skladování
Video nekomprimované?

893
00:42:06,880 --> 00:42:11,420
Je to druh odpadu pro ukládání videa
jako čtyři téměř identické obrazy, které

894
00:42:11,420 --> 00:42:13,670
se liší pouze v případě, kdy je včela.

895
00:42:13,670 --> 00:42:16,280
Můžete zahodit většinu
těchto informací

896
00:42:16,280 --> 00:42:20,190
a pamatovat si jen, například,
první snímek a poslední snímek,

897
00:42:20,190 --> 00:42:22,180
klíčové snímky, pokud jste
někdy slyšel slovo,

898
00:42:22,180 --> 00:42:24,337
a jen uložit do
prostřední kde včela je.

899
00:42:24,337 --> 00:42:26,170
A nemusíte se
ukládat všechny růžové,

900
00:42:26,170 --> 00:42:28,330
a modré, a
zelené hodnoty stejně.

901
00:42:28,330 --> 00:42:31,200
Tak tohle je jen říct, že
komprese je všude.

902
00:42:31,200 --> 00:42:34,900
Jedná se o techniku ​​často používáme
nebo považuje za samozřejmost v těchto dnech.

903
00:42:34,900 --> 00:42:38,750
>> Ale jak si komprimovat text?

904
00:42:38,750 --> 00:42:40,450
Jak se vám jít o kompresi textu?

905
00:42:40,450 --> 00:42:45,410
No, každý ze znaků v
ASCII je jeden bajt, nebo osm bitů.

906
00:42:45,410 --> 00:42:47,360
A to je trochu hloupá, že jo?

907
00:42:47,360 --> 00:42:51,160
Vzhledem k tomu, budete pravděpodobně typu A
a E a I a O a U hodně

908
00:42:51,160 --> 00:42:55,270
častěji než jako W nebo Q nebo Z,
v závislosti na jazyk, ve kterém

909
00:42:55,270 --> 00:42:56,610
píšete určitě.

910
00:42:56,610 --> 00:42:59,600
A proč jsme s použitím
osm bitů pro každé písmeno,

911
00:42:59,600 --> 00:43:02,040
včetně nejméně
populární dopisy, že jo?

912
00:43:02,040 --> 00:43:05,300
Proč ne použít méně bitů pro
Super populární dopisy,

913
00:43:05,300 --> 00:43:07,760
jako E, věci, které hádat
nejprve v Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
a používat více bitů pro
méně populární dopisy?

915
00:43:10,450 --> 00:43:10,950
Proč?

916
00:43:10,950 --> 00:43:13,130
Protože jsme jen tak
používat méně často.

917
00:43:13,130 --> 00:43:15,838
>> No, to ukáže, že tam mají
Byl pokusy, jak toho dosáhnout.

918
00:43:15,838 --> 00:43:18,630
A pokud si vzpomínáte ze stupně
škola nebo vysoká škola, Morseova abeceda.

919
00:43:18,630 --> 00:43:20,400
Morseova abeceda má tečky
a pomlčky, které mohou být

920
00:43:20,400 --> 00:43:24,270
přenášeny po drátě as
zvuky nebo signály nějaké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árního systému
že máte tečky nebo čárky.

923
00:43:29,010 --> 00:43:30,977
Ale když vidíte, například, dvě tečky.

924
00:43:30,977 --> 00:43:33,810
Nebo pokud si myslíte, zpět na provozovatele
kteří chodí jako píp, píp, pípnutí,

925
00:43:33,810 --> 00:43:36,760
pípnutí, bít trochu spoušť
který vysílá signál,

926
00:43:36,760 --> 00:43:40,360
pokud vás, příjemce, obdrží dvě
tečky, jakou zprávu jste obdrželi?

927
00:43:40,360 --> 00:43:43,490
Zcela libovolné.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Nebo co about-- nebo já?

931
00:43:47,500 --> 00:43:49,570
Možná to bylo jen 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, přičemž pokud se
osoba zasílání zprávy

934
00:43:54,890 --> 00:43:59,510
ve skutečnosti se zastaví, takže si můžete třídit podle
vidět nebo slyšet mezery mezi písmeny,

935
00:43:59,510 --> 00:44:02,990
že to není dostačující jen
Poslat proudu nul a jedniček,

936
00:44:02,990 --> 00:44:05,610
nebo tečky a čárky,
protože tam je dvojznačnost.

937
00:44:05,610 --> 00:44:08,640
E je jediná tečka, takže pokud vás
viz dvě tečky nebo slyšet dvě tečky,

938
00:44:08,640 --> 00:44:11,254
Možná je to dva E je nebo možná je to jedna I.

939
00:44:11,254 --> 00:44:13,670
Takže potřebujeme systém, který je
málo chytřejší než to.

940
00:44:13,670 --> 00:44:16,851
Takže muž jménem Huffman let
Před přišli s přesně tohle.

941
00:44:16,851 --> 00:44:18,600
Takže jsme jen tak
vzít rychlý pohled

942
00:44:18,600 --> 00:44:20,114
na to, jak stromy jsou pro projednávanou.

943
00:44:20,114 --> 00:44:22,530
Předpokládejme, že je to nějaký
hloupý zpráva, kterou chcete odeslat,

944
00:44:22,530 --> 00:44:26,342
složený z pouhých A, B, C je D'S a E je,
ale je tu spousta redundance sem.

945
00:44:26,342 --> 00:44:27,550
Není to znamená být angličtina.

946
00:44:27,550 --> 00:44:28,341
To není šifrována.

947
00:44:28,341 --> 00:44:30,540
Je to jen hloupá zpráva
se spoustou opakování.

948
00:44:30,540 --> 00:44:34,010
Takže pokud jste opravdu počítat se všechny
A to, B je, je C, D's, a E je, tady je

949
00:44:34,010 --> 00:44:34,890
frekvence.

950
00:44:34,890 --> 00:44:37,800
20% z dopisů jsou
A je 45% z dopisů

951
00:44:37,800 --> 00:44:39,660
jsou E je, a další tři frekvence.

952
00:44:39,660 --> 00:44:41,960
Počítali jsme tam ručně
a právě udělal matematický.

953
00:44:41,960 --> 00:44:44,579
>> Tak to dopadá, že
Huffman, před nějakým časem,

954
00:44:44,579 --> 00:44:46,620
si uvědomil, že, víte,
co, když jsem začít stavět

955
00:44:46,620 --> 00:44:51,172
strom nebo les stromů, chcete-li,
takto, mohu udělat následující.

956
00:44:51,172 --> 00:44:53,880
Chystám se dát uzlu ke každému
z dopisů, které jsem záleží

957
00:44:53,880 --> 00:44:55,530
a budu ukládat
uvnitř tohoto uzlu

958
00:44:55,530 --> 00:44:58,610
frekvence jako pohyblivé řádové čárce
hodnota, nebo můžete použít N, taky,

959
00:44:58,610 --> 00:45:00,210
ale my budeme stačí použít float zde.

960
00:45:00,210 --> 00:45:03,100
A algoritmus, který
navrhl je, že jste

961
00:45:03,100 --> 00:45:07,210
tento les jednoho uzlu
stromy, takže extra krátké stromy,

962
00:45:07,210 --> 00:45:11,920
a začnete je spojují s
nové skupiny, nové rodiče, chcete-li.

963
00:45:11,920 --> 00:45:16,150
A to tím, že volbě
dvě nejmenší frekvencí najednou.

964
00:45:16,150 --> 00:45:18,110
Tak jsem vzal 10% a 10%.

965
00:45:18,110 --> 00:45:19,090
I vytvořit nový uzel.

966
00:45:19,090 --> 00:45:20,910
A já říkám nového uzlu 20%.

967
00:45:20,910 --> 00:45:22,750
>> Kteří dva uzly I kombinovat dál?

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 několik případů roh
zvážit, ale udržet věci dost,

970
00:45:26,643 --> 00:45:29,300
Budu volit 20% -
I nyní ignorovat děti.

971
00:45:29,300 --> 00:45:33,640
Budu volit 20% a
15% a kreslit dva nové hrany.

972
00:45:33,640 --> 00:45:35,624
A nyní, kdy jsou dvě uzly
mám logicky kombinovat?

973
00:45:35,624 --> 00:45:38,540
Ignorovat všechny děti, jsou všechny
vnoučata, stačí se podívat na kořeny

974
00:45:38,540 --> 00:45:39,070
teď.

975
00:45:39,070 --> 00:45:42,220
Kteří dva uzly mám svázat dohromady?

976
00:45:42,220 --> 00:45:44,530
Bod dva a 0.35.

977
00:45:44,530 --> 00:45:45,890
Dovolte mi tedy kreslit dva nové hrany.

978
00:45:45,890 --> 00:45:47,570
A pak jsem se dostal jen jeden vlevo.

979
00:45:47,570 --> 00:45:48,650
Tak tady je to strom.

980
00:45:48,650 --> 00:45:51,160
A to byl vypracován záměrně
vypadat trochu hezká,

981
00:45:51,160 --> 00:45:55,870
ale všimněte si, že hrany mají
Také byl označen nulou a jedničkou.

982
00:45:55,870 --> 00:45:59,510
Takže všechny levého okraje jsou nulové
libovolně, ale důsledně.

983
00:45:59,510 --> 00:46:01,170
Všechny hrany jsou ty správné.

984
00:46:01,170 --> 00:46:05,070
>> A tak to, co Hoffman Navrhuje se,
Chcete-li reprezentovat B,

985
00:46:05,070 --> 00:46:10,080
spíše než představují počet 66 as
ASCII, který je osm celé bitů,

986
00:46:10,080 --> 00:46:13,360
Víš co, jen obchod
vzor nula, nula, nula,

987
00:46:13,360 --> 00:46:17,030
nula, protože to je cesta
z mého stromu, pana Huffmanův strom,

988
00:46:17,030 --> 00:46:18,600
na listu z kořene.

989
00:46:18,600 --> 00:46:20,970
Pokud chcete uložit
E, naproti tomu nemají

990
00:46:20,970 --> 00:46:26,290
poslat osm bitů, které představují E.
Místo toho, co poslat vzor bitů?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
A co je příjemné na tom je,
že E je nejpopulárnější dopis,

993
00:46:30,410 --> 00:46:32,340
a používáte
Nejkratší kód pro ni.

994
00:46:32,340 --> 00:46:34,090
Příští Nejoblíbenější
dopis vypadá, že

995
00:46:34,090 --> 00:46:37,380
byl A. A tak, kolik bitů
udělal navrhují použití za to?

996
00:46:37,380 --> 00:46:38,270
Nula, jedna.

997
00:46:38,270 --> 00:46:41,060
>> A protože je implementováno
jak tohoto stromu, prozatím

998
00:46:41,060 --> 00:46:43,350
dovolte mi, abych stanoví, že je
žádná nejasnost jako v Morse

999
00:46:43,350 --> 00:46:46,090
kód, protože všechny
dopisy vám záleží

1000
00:46:46,090 --> 00:46:48,780
jsou na konci těchto hran.

1001
00:46:48,780 --> 00:46:50,580
Tak to je jen jeden
Aplikace stromu.

1002
00:46:50,580 --> 00:46:52,538
To je-- a budu mávat
moje ruka se na to, jak na Vás

1003
00:46:52,538 --> 00:46:55,570
může provádět toto jako struktura C.

1004
00:46:55,570 --> 00:46:58,260
Potřebujeme jen kombinovat
symbol, jako char,

1005
00:46:58,260 --> 00:46:59,910
a frekvence doleva a doprava.

1006
00:46:59,910 --> 00:47:02,510
Ale pojďme se podívat na dva
Konečné příklady, které budete

1007
00:47:02,510 --> 00:47:06,070
dostat docela obeznámeni s po
kvíz nula problém nastavit pět.

1008
00:47:06,070 --> 00:47:09,210
>> Takže tam je datová struktura
známý jako stolu mřížky.

1009
00:47:09,210 --> 00:47:12,247
A hash tabulka je druh
ochladí se tím, že korečky.

1010
00:47:12,247 --> 00:47:14,830
A předpokládám, že tam je čtyři kbelíky
tady, pouhé čtyři mezery.

1011
00:47:14,830 --> 00:47:20,830
Zde je balíček karet, a je zde
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 jsem
bucketizing veškeré vstupy sem.

1014
00:47:30,330 --> 00:47:32,430
A A potřebuje hash table
podívat se na váš vstup,

1015
00:47:32,430 --> 00:47:34,850
a pak ji do určité
položte na základě toho, co vidíte.

1016
00:47:34,850 --> 00:47:35,600
Je to algoritmus.

1017
00:47:35,600 --> 00:47:37,980
A já jsem byl s použitím super
jednoduché vizuální algoritmus.

1018
00:47:37,980 --> 00:47:40,030
Nejtěžší část, která byla
si vzpomněl, jaké obrázky byly.

1019
00:47:40,030 --> 00:47:41,590
A pak je tu celkem čtyři věci.

1020
00:47:41,590 --> 00:47:45,440
>> Nyní komíny rostly, což
je záměrná návrh věc tady.

1021
00:47:45,440 --> 00:47:46,540
Ale co jiného bych mohl udělat?

1022
00:47:46,540 --> 00:47:49,080
Takže vlastně tady máme
banda staré školy zkoušky knih.

1023
00:47:49,080 --> 00:47:51,240
Předpokládejme, že banda
Jména studenti jsou tady.

1024
00:47:51,240 --> 00:47:52,570
Tady to větší hash tabulky.

1025
00:47:52,570 --> 00:47:54,867
Namísto čtyř věder,
Jsem, řekněme 26.

1026
00:47:54,867 --> 00:47:57,950
A my jsme nechtěli jít půjčit 26
ze zemí mimo [? Annenberg?], Tak

1027
00:47:57,950 --> 00:48:00,289
tady je pěti které reprezentují
A až Z. A pokud já

1028
00:48:00,289 --> 00:48:03,580
viz studentem, jehož jméno začíná na A,
Chystám se dát jeho nebo její kvíz tam.

1029
00:48:03,580 --> 00:48:08,850
Pokud někdo začne s C, tam,
Je-- skutečnosti, nechtěl udělat.

1030
00:48:08,850 --> 00:48:10,060
B jede sem.

1031
00:48:10,060 --> 00:48:13,390
Tak jsem dostal A a B a C a
teď tady je další student.

1032
00:48:13,390 --> 00:48:16,212
Ale pokud to hash tabulka
implementován s matici

1033
00:48:16,212 --> 00:48:17,920
Jsem typ šroubované
v tomto bodě, že jo?

1034
00:48:17,920 --> 00:48:19,510
Tak nějak jsem potřebujete, aby to někde.

1035
00:48:19,510 --> 00:48:24,380
>> Takže jeden způsob, jak mohu řešit to, všechno
vpravo, A je zaneprázdněn, B je zaneprázdněn, C je zaneprázdněn.

1036
00:48:24,380 --> 00:48:28,880
Chystám se ho dát do D. Takže na
První, mám náhodný okamžitý přístup

1037
00:48:28,880 --> 00:48:31,064
ke každé z lopatek pro studenty.

1038
00:48:31,064 --> 00:48:33,230
Ale teď je to trochu přenesl
do něčeho lineární,

1039
00:48:33,230 --> 00:48:36,750
protože když chci hledat někoho,
Název jehož začíná, já podívejte se sem.

1040
00:48:36,750 --> 00:48:38,854
Ale pokud to není A
Student Hledám,

1041
00:48:38,854 --> 00:48:41,520
Tak nějak jsem musel spustit kontrolu
kbelíky, protože to, co jsem udělal

1042
00:48:41,520 --> 00:48:44,530
Bylo to trochu lineárně
zkoumat strukturu dat.

1043
00:48:44,530 --> 00:48:47,710
Hloupá způsob jak říci, stačí se podívat
za první dostupné otvoru,

1044
00:48:47,710 --> 00:48:51,850
a dal jako plán B, abych tak řekl,
nebo plán D v tomto případě je hodnota

1045
00:48:51,850 --> 00:48:53,340
V tomto místě namísto.

1046
00:48:53,340 --> 00:48:56,470
Je to jen proto, aby, pokud jste
dostal 26 míst a žádní studenti

1047
00:48:56,470 --> 00:49:00,600
s názvem Q nebo Z, nebo něco podobného
že přinejmenším používáte prostor.

1048
00:49:00,600 --> 00:49:03,140
>> Ale my jsme již viděli více
Chytrá řešení tady, že jo?

1049
00:49:03,140 --> 00:49:04,870
Co byste dělali, místo
Máte-li ke kolizi?

1050
00:49:04,870 --> 00:49:06,670
Pokud se dva lidé mají
název A, co by

1051
00:49:06,670 --> 00:49:09,160
byli chytřejší a více
intuitivní řešení než jen

1052
00:49:09,160 --> 00:49:12,840
Uvedení kde D má být?

1053
00:49:12,840 --> 00:49:14,810
Proč nemůžu prostě jít
mimo [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
jako je malloc, jiného uzlu, dát to
tady, a pak dal, že student zde.

1055
00:49:19,960 --> 00:49:22,120
Tak, že jsem v podstatě mají
nějaký pole,

1056
00:49:22,120 --> 00:49:25,590
nebo možná více elegantně, jak jsme
Začínáme vidět propojeného seznamu.

1057
00:49:25,590 --> 00:49:29,520
>> A tak hash tabulky je struktura
které by mohly vypadat přesně takhle,

1058
00:49:29,520 --> 00:49:33,900
ale chytře, jste něco jako
samostatný řetězení, přičemž hash tabulky

1059
00:49:33,900 --> 00:49:38,340
docela jednoduše je pole, každý z
jejíž prvky není číslo,

1060
00:49:38,340 --> 00:49:40,470
je sám o sobě spojen seznam.

1061
00:49:40,470 --> 00:49:45,080
Tak, že máte super rychlý přístup
rozhodování o tom, kde se vaše hash hodnotu.

1062
00:49:45,080 --> 00:49:48,059
Podobně jako u příkladu karty,
Udělal jsem mimořádně rychlé rozhodování.

1063
00:49:48,059 --> 00:49:49,600
Hearts jde tady, diamanty jde zde.

1064
00:49:49,600 --> 00:49:52,180
Já taky, A tady jde,
D jde tady, B jde zde.

1065
00:49:52,180 --> 00:49:55,740
Takže super rychlé look-ups, a pokud
jste náhodou narazit na případu

1066
00:49:55,740 --> 00:49:59,429
kde jste dostal kolize, dva
lidé se stejným názvem, no a pak

1067
00:49:59,429 --> 00:50:00,970
stačí začít spojovat dohromady.

1068
00:50:00,970 --> 00:50:03,900
A možná si udržet je seřazena
abecedně, možná ne.

1069
00:50:03,900 --> 00:50:05,900
Ale aspoň teď máme dynamiku.

1070
00:50:05,900 --> 00:50:10,250
Takže na jedné straně máme velmi rychlé
konstantní čas, a druh lineárního času

1071
00:50:10,250 --> 00:50:14,110
zapojit, pokud těchto spojových seznamů
začne být trochu dlouho.

1072
00:50:14,110 --> 00:50:16,880
>> Takže tento druh hloupý,
geeky vtip před lety.

1073
00:50:16,880 --> 00:50:19,590
Na CS50 hack-a-Thon,
Když studenti check in,

1074
00:50:19,590 --> 00:50:22,040
některé TF nebo CA každý rok
si myslí, že je to legrační, aby se

1075
00:50:22,040 --> 00:50:27,772
znamení jako je tento, kde jde jen
znamená, že pokud vaše jméno začíná s A,

1076
00:50:27,772 --> 00:50:28,870
jít touto cestou.

1077
00:50:28,870 --> 00:50:31,110
Pokud se spustí Vaše jméno
s B, jděte tohle-- OK,

1078
00:50:31,110 --> 00:50:33,290
je to legrační možná později v semestru.

1079
00:50:33,290 --> 00:50:36,420
Ale je tu další
způsob, jak toho dosáhnout, taky.

1080
00:50:36,420 --> 00:50:37,410
Vrať se k tomu.

1081
00:50:37,410 --> 00:50:38,600
>> Takže je tu tato struktura.

1082
00:50:38,600 --> 00:50:40,420
A to je náš poslední
struktura pro dnešek,

1083
00:50:40,420 --> 00:50:42,400
což je něco, co nazývá trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, která z nějakého důvodu je krátká
pro vyhledávání, ale je to jen trie.

1085
00:50:47,140 --> 00:50:51,389
Takže Trie je další zajímavá
amalgám z mnoha těchto nápadů.

1086
00:50:51,389 --> 00:50:52,930
Je to strom, který jsme viděli dříve.

1087
00:50:52,930 --> 00:50:54,180
Není to strom binárního vyhledávání.

1088
00:50:54,180 --> 00:50:58,410
Je to strom s libovolným počtem dětí,
ale každý z dětí v trie

1089
00:50:58,410 --> 00:51:00,090
je pole.

1090
00:51:00,090 --> 00:51:04,790
Pole velikosti, řekněme, 26 nebo možná 27
Chcete-li podpořit pomlčkou jména

1091
00:51:04,790 --> 00:51:06,790
nebo apostrofy v názvech lidí.

1092
00:51:06,790 --> 00:51:08,280
>> A tak to je datová struktura.

1093
00:51:08,280 --> 00:51:10,290
A když se podíváte z vrcholu
dolů, jako když

1094
00:51:10,290 --> 00:51:13,710
podívejte se na horním uzlu tam, M, je
ukazující na nejvíce vlevo věc tam,

1095
00:51:13,710 --> 00:51:17,665
který je potom A, X, W, E, L, L. To je
jen datová struktura, která libovolně

1096
00:51:17,665 --> 00:51:19,120
je ukládání jmen lidí.

1097
00:51:19,120 --> 00:51:25,720
A Maxwell je uložen právě tímto
cesta z pole na pole do pole.

1098
00:51:25,720 --> 00:51:30,050
Ale co je to úžasné asi trie je
že, vzhledem k tomu, Google seznamu a dokonce

1099
00:51:30,050 --> 00:51:34,520
pole, to nejlepší, co jsem kdy dostal, je
lineární čas nebo logaritmické čas hledáte

1100
00:51:34,520 --> 00:51:35,600
někdo up.

1101
00:51:35,600 --> 00:51:40,530
V této datové struktuře trie, pokud je to
můj datová struktura má jedno jméno v něm

1102
00:51:40,530 --> 00:51:43,720
a já jsem hledal Maxwella, já jsem
že ho docela rychle najít.

1103
00:51:43,720 --> 00:51:47,910
Já se jen podívat na M-A-X-W-E-L-L. Jestliže
Tato datová struktura, naopak

1104
00:51:47,910 --> 00:51:51,830
pokud N je milion, jestli je
milión jména v této datové struktury,

1105
00:51:51,830 --> 00:51:57,100
Maxwell se ještě bude
zjistitelný po právě 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
Jinými slovy tím, že stavební
datová struktura, která je

1109
00:52:03,400 --> 00:52:07,240
dostal přičemž všechny z těchto polí, vše
samy podporují náhodný přístup,

1110
00:52:07,240 --> 00:52:11,090
Můžu začít vzhlédl lidí'S
název pomocí množství času, který je

1111
00:52:11,090 --> 00:52:14,340
úměrný ne číslo
věcí v datové struktury,

1112
00:52:14,340 --> 00:52:16,330
jako milion existující jmen.

1113
00:52:16,330 --> 00:52:20,135
Množství času to trvá mi najít
M-A-X-W-E-L-L v této datové struktury je

1114
00:52:20,135 --> 00:52:22,260
úměrný není na
velikost datové struktury,

1115
00:52:22,260 --> 00:52:25,930
ale k délce názvu.

1116
00:52:25,930 --> 00:52:28,440
A Realisticky
Jména díváme nahoru

1117
00:52:28,440 --> 00:52:29,970
se nikdy nebude blázen dlouho.

1118
00:52:29,970 --> 00:52:32,600
Možná, že někdo má 10 znak
jméno, název 20 znaků.

1119
00:52:32,600 --> 00:52:33,900
Je to určitě konečný, že jo?

1120
00:52:33,900 --> 00:52:37,110
Tam je člověk na Zemi, který
má nejdelší název,

1121
00:52:37,110 --> 00:52:39,920
ale to jméno je konstantní
hodnota délky, ne?

1122
00:52:39,920 --> 00:52:41,980
To se nemění v žádném smyslu.

1123
00:52:41,980 --> 00:52:45,090
Takže tímto způsobem, máme
dosáhla datovou strukturu

1124
00:52:45,090 --> 00:52:47,800
že je konstantní doba look-up.

1125
00:52:47,800 --> 00:52:50,670
Je to trvat řadu kroků
v závislosti na délce vstupu,

1126
00:52:50,670 --> 00:52:54,250
ale ne množství názvu
v datové struktuře.

1127
00:52:54,250 --> 00:52:58,700
Takže pokud budeme zdvojnásobit počet jmen
v příštím roce z miliardy do dvou miliard,

1128
00:52:58,700 --> 00:53:03,720
nález Maxwell bude trvat
přesně stejný počet sedmi stupních

1129
00:53:03,720 --> 00:53:04,650
ho najít.

1130
00:53:04,650 --> 00:53:08,810
A tak se zdá k dosáhli
náš svatý grál doby chodu.

1131
00:53:08,810 --> 00:53:10,860
>> Takže pár rychlých oznámení.

1132
00:53:10,860 --> 00:53:11,850
Kvíz nula se blíží.

1133
00:53:11,850 --> 00:53:14,600
Více o tom na internetových stránkách Course
během příštích pár dní.

1134
00:53:14,600 --> 00:53:17,120
Pondělní lecture-- je to svátek
tady na Harvardu v pondělí.

1135
00:53:17,120 --> 00:53:18,850
Není to v New Haven,
takže bereme třídu

1136
00:53:18,850 --> 00:53:20,310
do New Havenu pro přednášku v pondělí.

1137
00:53:20,310 --> 00:53:22,550
Vše bude natočen
a sledovat živě jako obvykle,

1138
00:53:22,550 --> 00:53:24,900
ale pojďme skončit dnes
s 30 druhého klipu

1139
00:53:24,900 --> 00:53:26,910
zvané "hluboké myšlenky"
podle Daven Farnham, který

1140
00:53:26,910 --> 00:53:30,850
byl inspirován v loňském roce v sobotu
Night Live "hluboké myšlenky"

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, který
by nyní měla smysl.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: A teď, "Hluboké
Myšlenky "od Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tabulky.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> Reproduktor 1: Dobře, to je pro teď.

1147
00:53:47,660 --> 00:53:48,805
Uvidíme se příští týden.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Chcete-li jej vidět v akci.

1150
00:53:56,680 --> 00:53:58,304
Takže pojďme se podívat na právě teď.

1151
00:53:58,304 --> 00:53:59,890
Takže tady máme netříděného pole.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, můžete jít dopředu a restart
to jen na jednu sekundu, prosím.

1153
00:54:04,860 --> 00:54:08,562
Dobře, kamery jsou rolovací, tak
akce vždy, když budete připraveni, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Dobře, takže to, co jsme
zde je netříděný pole.

1155
00:54:11,020 --> 00:54:13,960
A já jsem barevné všech prvků
červeně, což znamená, že to je, ve skutečnosti,

1156
00:54:13,960 --> 00:54:14,460
netříděný.

1157
00:54:14,460 --> 00:54:17,960
Takže připomenout, že první věc, kterou děláme
je třídíme na levé polovině pole.

1158
00:54:17,960 --> 00:54:20,630
Pak jsme třídit právo
polovina pole.

1159
00:54:20,630 --> 00:54:22,830
A ya-da, da-ya, ya-da,
jsme je spojit dohromady.

1160
00:54:22,830 --> 00:54:24,520
A máme úplně setříděné pole.

1161
00:54:24,520 --> 00:54:25,360
Tak to je, jak sloučit nějak funguje.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, hej, hej,
střih, střih, střih, řez.

1163
00:54:27,109 --> 00:54:30,130
Doug, nemůžeš ya-da, ya-da,
ya-da, si cestu přes sloučení druhu.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Jen jsem udělal.

1165
00:54:31,970 --> 00:54:32,832
To je v pořádku.

1166
00:54:32,832 --> 00:54:33,540
Jsme dobré jít.

1167
00:54:33,540 --> 00:54:34,760
Pojďme se jen držet válcování.

1168
00:54:34,760 --> 00:54:35,380
Tak jako tak,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Musíte vysvětlit
to ve větší míře, než to.

1170
00:54:37,800 --> 00:54:39,999
To je prostě nestačí.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, my ne
je třeba se vrátit do jednoho.

1172
00:54:41,790 --> 00:54:42,350
To je v pořádku.

1173
00:54:42,350 --> 00:54:45,690
Takže tak jako tak, pokud budeme pokračovat s merge--
Ian jsme v polovině natáčení.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Já vím.

1175
00:54:46,612 --> 00:54:49,320
A my nemůžeme jen ya-da, ya-da,
ya-da, celý proces.

1176
00:54:49,320 --> 00:54:52,200
Musíte vysvětlit, jak
Obě strany si spojil.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Ale máme už
vysvětlil, jak dva sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Právě jste zobrazeny
jim merge pole.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Znají proces.

1180
00:54:56,486 --> 00:54:57,172
Jsou v pořádku.

1181
00:54:57,172 --> 00:54:58,380
Šli jsme přes to desetkrát.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Právě jsi přeskočil hned nad ním.

1183
00:55:00,330 --> 00:55:03,360
Vracíme se do jednoho, vy
nemůžeš ya-da, ya-da přes ni.

1184
00:55:03,360 --> 00:55:05,480
Dobře, zpátky do jednoho.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Musím se vrátit
přes všechny 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 jako již pošesté, Ian.

1189
00:55:13,004 --> 00:55:13,940
To je v pořádku.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Dobře.

1191
00:55:15,200 --> 00:55:16,590
Jste připraveni?

1192
00:55:16,590 --> 00:55:17,400
Skvělý.

1193
00:55:17,400 --> 00:55:18,950
Akce.