1
00:00:00,000 --> 00:00:00,030

2
00:00:00,030 --> 00:00:00,460
>> DAVID Malan: Dobře.

3
00:00:00,460 --> 00:00:01,094
Jsme zpět.

4
00:00:01,094 --> 00:00:04,260
Takže v tomto segmentu o programování, co
Myslel jsem, že bychom udělat, je mix věcí.

5
00:00:04,260 --> 00:00:06,340
Za prvé, udělat trochu
něčeho hands-on,

6
00:00:06,340 --> 00:00:08,690
byť s použitím hravější
programování environment--

7
00:00:08,690 --> 00:00:11,620
ten, který je demonstrativní
přesně ty druhy nápadů

8
00:00:11,620 --> 00:00:14,220
jsme mluvili o,
ale trochu více formálně.

9
00:00:14,220 --> 00:00:18,200
Za druhé, podívejte se na některé z
čím více technických způsobů

10
00:00:18,200 --> 00:00:21,520
že programátor by skutečně řešit
Problémy, jako je vyhledávání problému

11
00:00:21,520 --> 00:00:24,530
že jsme se zabývali dříve a
také více zásadně

12
00:00:24,530 --> 00:00:26,020
zajímavý problém třídění.

13
00:00:26,020 --> 00:00:28,840
>> Jen jsme předpokládali, od dostat jít
že telefonní seznam byl tříděn,

14
00:00:28,840 --> 00:00:31,980
ale to samo o sobě je vlastně něco jako
obtížný problém s mnoha různými způsoby

15
00:00:31,980 --> 00:00:32,479
to vyřešit.

16
00:00:32,479 --> 00:00:34,366
Takže budeme používat tyto jako
třída problémů

17
00:00:34,366 --> 00:00:36,740
Zástupce věcí, které
by mohl být vyřešen obecně.

18
00:00:36,740 --> 00:00:38,980
A pak si promluvíme
asi v nějakém detailu, co

19
00:00:38,980 --> 00:00:42,360
se nazývají dat structures--
milovník způsoby, jako spojových seznamů

20
00:00:42,360 --> 00:00:46,290
a hashovací tabulky a stromy, které
programátor by vlastně

21
00:00:46,290 --> 00:00:48,890
použití a obecně používají
Na tabuli malovat

22
00:00:48,890 --> 00:00:51,840
obrázek o tom, co on nebo ona
předpokládá pro provádění

23
00:00:51,840 --> 00:00:52,980
některé kus softwaru.

24
00:00:52,980 --> 00:00:55,130
>> Takže pojďme dělat hands-na části první.

25
00:00:55,130 --> 00:01:00,090
Takže jen dostat své špinavé ruce s
Prostředí tzv scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Jedná se o nástroj, který používáme
v naší třídě vysokoškoláka.

27
00:01:02,636 --> 00:01:04,510
I přesto, že je navržen
pro děti od 12 a nahoru,

28
00:01:04,510 --> 00:01:07,570
budeme používat jej pro nahoru
Součástí tohoto docela dost

29
00:01:07,570 --> 00:01:10,020
protože je to pěkné, zábavné
grafický způsob učení

30
00:01:10,020 --> 00:01:12,160
něco málo o programování.

31
00:01:12,160 --> 00:01:17,600
Takže zamířit do této adresy URL, kde vás
Měli byste vidět stránku přesně takhle,

32
00:01:17,600 --> 00:01:23,330
a pokračujte a klikněte
Přidejte se k poškrábání v pravém horním rohu

33
00:01:23,330 --> 00:01:28,300
a vybrat si uživatelské jméno a
heslem a nakonec si sami

34
00:01:28,300 --> 00:01:29,970
account-- scratch.mit.edu.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Myslel jsem, že použít jako
Příležitost první to ukázat.

37
00:01:34,665 --> 00:01:39,120
Otázka přišel během přestávky
o tom, co vlastně kód vypadá.

38
00:01:39,120 --> 00:01:41,315
A my jsme si povídali
během přestávky o C,

39
00:01:41,315 --> 00:01:45,060
v particular-- zvláště
Nižší úroveň ve starším jazykem.

40
00:01:45,060 --> 00:01:47,750
A já jsem právě udělal rychlý
Google hledání najít C kód

41
00:01:47,750 --> 00:01:51,574
pro binární vyhledávání, algoritmus, který jsme
použity k hledání tohoto telefonního seznamu dříve.

42
00:01:51,574 --> 00:01:54,240
Tento konkrétní příklad, samozřejmě,
nevyhledává telefonní seznam.

43
00:01:54,240 --> 00:01:57,840
Je to jen hledá spoustu
Čísla v paměti počítače.

44
00:01:57,840 --> 00:02:01,000
Ale pokud byste chtěli jen dostat vizuální
o tom, co skutečné programování

45
00:02:01,000 --> 00:02:05,370
jazyk vypadá, že vypadá
trochu něco takového.

46
00:02:05,370 --> 00:02:09,759
Takže je to asi 20-plus,
Přibližně 30 řádků kódu,

47
00:02:09,759 --> 00:02:12,640
ale rozhovor jsme
vedli přes přestávku

48
00:02:12,640 --> 00:02:16,000
Byl o tom, jak to vlastně
dostane proměnil nul a jedniček

49
00:02:16,000 --> 00:02:19,200
a můžete nejen vrátit v případě, že
zpracovávat a jít z nul a jedniček

50
00:02:19,200 --> 00:02:20,210
zpět ke kódu.

51
00:02:20,210 --> 00:02:22,620
>> Bohužel, tento proces
Je tak transformační

52
00:02:22,620 --> 00:02:24,890
že je to mnohem snadněji řekne, než udělá.

53
00:02:24,890 --> 00:02:29,400
Šel jsem dopředu a ve skutečnosti se obrátil
tento program, binární vyhledávání,

54
00:02:29,400 --> 00:02:32,700
do nul a jedniček formou
program s názvem kompilátoru, že jsem

55
00:02:32,700 --> 00:02:34,400
stalo se, že tady právě na mém počítači Mac.

56
00:02:34,400 --> 00:02:37,850
A když se podíváte na obrazovce
Zde, zejména s důrazem

57
00:02:37,850 --> 00:02:43,520
Na těchto středních šest sloupců pouze
uvidíte pouze nul a jedniček.

58
00:02:43,520 --> 00:02:48,290
A to jsou ty nuly a ty, které
skládat přesně ten vyhledávací program.

59
00:02:48,290 --> 00:02:53,720
>> A tak každý kus z pěti bitů,
každý bajt nul a jedniček tady,

60
00:02:53,720 --> 00:02:57,310
reprezentují nějakou instrukci
typicky uvnitř počítače.

61
00:02:57,310 --> 00:03:00,730
A ve skutečnosti, pokud jste slyšeli
marketing slogan "Intel inside" - to,

62
00:03:00,730 --> 00:03:04,610
Samozřejmě, prostě znamená, že máte
Intel CPU nebo mozku uvnitř počítače.

63
00:03:04,610 --> 00:03:08,000
A co to znamená být CPU
že máte instrukční sadu,

64
00:03:08,000 --> 00:03:08,840
abych tak řekl.

65
00:03:08,840 --> 00:03:11,620
>> Každý procesor na světě, mnozí
je vyrobený firmou Intel v těchto dnech,

66
00:03:11,620 --> 00:03:13,690
chápe konečný
počet instrukcí.

67
00:03:13,690 --> 00:03:18,690
A tyto pokyny jsou tak nízké úrovni
jako doplněk těchto dvou čísel dohromady,

68
00:03:18,690 --> 00:03:22,560
násobit těchto dvou čísel dohromady,
přesunout tento kousek dat odtud

69
00:03:22,560 --> 00:03:27,340
tady v paměti uložit toto
Informace odtud do zde v paměti,

70
00:03:27,340 --> 00:03:32,200
a tak forth-- tak velmi, velmi
low-level, téměř elektronické detaily.

71
00:03:32,200 --> 00:03:34,780
Ale s těmi, matematický
operace spojené

72
00:03:34,780 --> 00:03:37,410
s tím, co jsme diskutovali dříve,
reprezentace dat

73
00:03:37,410 --> 00:03:40,450
jako nul a jedniček, může
si vybudovat vše

74
00:03:40,450 --> 00:03:44,180
že počítač může udělat dnes, ať už
je to textové, grafické, hudební,

75
00:03:44,180 --> 00:03:45,580
nebo jinak.

76
00:03:45,580 --> 00:03:49,450
>> Takže je to velmi snadné se dostat
ztratil v plevele rychle.

77
00:03:49,450 --> 00:03:52,150
A je tu spousta
syntaktické výzvy

78
00:03:52,150 --> 00:03:56,630
přičemž když uděláte nejjednodušší,
nejhloupější překlepů nikdo z programu

79
00:03:56,630 --> 00:03:57,860
bude fungovat vůbec.

80
00:03:57,860 --> 00:04:00,366
A tak namísto použití
jazyk C dnes ráno,

81
00:04:00,366 --> 00:04:02,240
Myslel jsem si, že by bylo
zábavnější vlastně dělat

82
00:04:02,240 --> 00:04:04,840
něco víc vizuální, což
zatímco určen pro děti

83
00:04:04,840 --> 00:04:08,079
je vlastně ideální projev
o skutečném programování

84
00:04:08,079 --> 00:04:10,370
language-- jen se stane
použít obrázky namísto textu

85
00:04:10,370 --> 00:04:11,710
reprezentovat těchto myšlenek.

86
00:04:11,710 --> 00:04:15,470
>> Takže až budete opravdu mít
Účet na scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
klepněte na tlačítko Vytvořit
V levém horním rohu stránky.

88
00:04:21,070 --> 00:04:24,620
A měli byste vidět prostředí, jako je
ten, že jsem asi vidět na mé obrazovce

89
00:04:24,620 --> 00:04:26,310
zde.

90
00:04:26,310 --> 00:04:29,350
A budeme trávit jen trochu
Trochu času hraním zde.

91
00:04:29,350 --> 00:04:34,080
Uvidíme, jestli se nám podaří ne všichni řešit některé
Problémy spolu v následujícím způsobem.

92
00:04:34,080 --> 00:04:39,420
>> Takže to, co uvidíte v této
environment-- a vlastně jen nechat

93
00:04:39,420 --> 00:04:40,050
me pauzy.

94
00:04:40,050 --> 00:04:42,680
Je někdo ne tady?

95
00:04:42,680 --> 00:04:45,070
Tady ne?

96
00:04:45,070 --> 00:04:45,800
OK.

97
00:04:45,800 --> 00:04:49,030
Takže mi dovolte zdůraznit několik
Charakteristiky tohoto prostředí.

98
00:04:49,030 --> 00:04:55,024
>> Takže v levém horním rohu obrazovky, my
mají stádium Scratch je, abych tak řekl.

99
00:04:55,024 --> 00:04:57,440
Scratch není pouze název
tohoto programovacího jazyka;

100
00:04:57,440 --> 00:05:00,356
je to také jméno kočky, která
vidíte ve výchozím nastavení tam v oranžové barvě.

101
00:05:00,356 --> 00:05:02,160
Že je na jevišti, tak
stejně jako jsem popsal

102
00:05:02,160 --> 00:05:05,770
želva dříve jako v
obdélníková bílá tabule prostředí.

103
00:05:05,770 --> 00:05:09,800
Tato kočka svět je omezena výhradně
v tomto obdélníku do vrcholu.

104
00:05:09,800 --> 00:05:12,210
>> Mezitím se na pravé straně
straně tady, je to

105
00:05:12,210 --> 00:05:15,610
jen skripty prostor,
nepopsaný list chcete-li.

106
00:05:15,610 --> 00:05:18,590
To je místo, kde budeme psát
naše programy za chvíli.

107
00:05:18,590 --> 00:05:22,935
A stavební kameny, které budeme
použít k napsání této program-- puzzle

108
00:05:22,935 --> 00:05:25,310
kusy, pokud jste will-- jsou
ty tady ve středu,

109
00:05:25,310 --> 00:05:27,500
a oni jsou rozděleny do kategorií
funkčností.

110
00:05:27,500 --> 00:05:31,000
Tak například, budu pokračovat
a ukazují, alespoň jeden z nich.

111
00:05:31,000 --> 00:05:33,690
Chystám se jít dopředu a klikněte
kategorie Control nahoru vrcholu.

112
00:05:33,690 --> 00:05:35,720
>> Tak to jsou kategorie nahoru vrcholu.

113
00:05:35,720 --> 00:05:39,410
Jdu kliknout na kategorii řízení.

114
00:05:39,410 --> 00:05:44,020
Spíše jdu kliknout na události
kategorie, první jedno až nahoru.

115
00:05:44,020 --> 00:05:47,790
A pokud byste chtěli sledovat spolu dokonce
jak to uděláme, jste docela vítáni.

116
00:05:47,790 --> 00:05:52,180
Jdu kliknout a přetáhnout
První z nich, "když zelená vlajka klepnutí."

117
00:05:52,180 --> 00:05:58,410
A pak budu ji neupustili jen
zhruba v horní části svých prázdných břidlic.

118
00:05:58,410 --> 00:06:01,450
>> A co je hezké o Scratch
je, že tento skládačky, když

119
00:06:01,450 --> 00:06:04,560
spojen s jiným puzzle
kusů, se chystá udělat doslova

120
00:06:04,560 --> 00:06:06,460
co tyto kousky skládačky říci dělat.

121
00:06:06,460 --> 00:06:09,710
Tak například, Scratch je správné
se v polovině jeho světa.

122
00:06:09,710 --> 00:06:14,660
Chystám se jít dopředu a vybrat
Nyní, řekněme, kategorie Motion,

123
00:06:14,660 --> 00:06:18,000
pokud byste chtěli, aby učinily
same-- kategorii Motion.

124
00:06:18,000 --> 00:06:20,430
A teď si všimnout mám celek
banda skládačky zde

125
00:06:20,430 --> 00:06:23,370
že opět trochu dělat to, co říkají.

126
00:06:23,370 --> 00:06:28,110
A já jdu dál a přetáhnout
drop Přesun bloku támhle.

127
00:06:28,110 --> 00:06:31,860
>> A všimněte si, že jakmile se dostanete
v blízkosti spodní části "zelenou vlajkou

128
00:06:31,860 --> 00:06:34,580
klepnutí "tlačítko, vývěsní
jak se objeví bílá čára,

129
00:06:34,580 --> 00:06:36,950
jako kdyby to je téměř
magnetické, že tam chce jet.

130
00:06:36,950 --> 00:06:43,070
Jen ať jdou, a to bude snap
dohromady a tvary budou odpovídat.

131
00:06:43,070 --> 00:06:46,620
A teď můžete snad téměř
hádejte, kde jdeme s tím.

132
00:06:46,620 --> 00:06:51,570
>> Podíváte-li se ve fázi Scratch
sem a dívat se na vrcholu toho,

133
00:06:51,570 --> 00:06:55,142
uvidíte červené světlo, je
stopka a zelenou vlajku.

134
00:06:55,142 --> 00:06:57,100
A já jdu napřed
a sledovat mé screen--

135
00:06:57,100 --> 00:06:58,460
na chvíli, pokud byste mohli.

136
00:06:58,460 --> 00:07:01,960
Jdu kliknout na
Zelená vlajka právě teď,

137
00:07:01,960 --> 00:07:07,850
a přešel co se zdá být 10 kroků
nebo 10 obrazových bodů, 10 bodů na obrazovce.

138
00:07:07,850 --> 00:07:13,390
>> A tak není tak vzrušující,
ale dovolte mi navrhnout

139
00:07:13,390 --> 00:07:17,440
aniž by se učí to, jen
s použitím vlastní svůj vlastní intuition-- let

140
00:07:17,440 --> 00:07:22,560
já navrhuji, aby vám zjistit, jak se
aby Scratch procházku hned jeviště.

141
00:07:22,560 --> 00:07:28,700
Už ho dělat cestu pro pravou stranu
obrazovky, úplně napravo.

142
00:07:28,700 --> 00:07:32,200
Dám vám chvilku
nebo tak zápasit s tím.

143
00:07:32,200 --> 00:07:37,681
Možná budete chtít, aby se podívali
u ostatních kategorií bloků.

144
00:07:37,681 --> 00:07:38,180
Dobře.

145
00:07:38,180 --> 00:07:41,290
Takže jen shrnout, když máme
zelená vlajka sem klikl

146
00:07:41,290 --> 00:07:44,850
a přesunout 10 kroků je
pouze pokyn, pokaždé, když jsem

147
00:07:44,850 --> 00:07:46,720
klikněte na zelenou vlajku, co se děje?

148
00:07:46,720 --> 00:07:50,070
No, to běží můj program.

149
00:07:50,070 --> 00:07:52,450
Takže jsem mohl udělat
Možná 10krát ručně,

150
00:07:52,450 --> 00:07:55,130
ale to cítí trochu
bit hackish, tak říkajíc,

151
00:07:55,130 --> 00:07:57,480
přičemž Nejsem
vyřešení problému.

152
00:07:57,480 --> 00:08:00,530
Já jsem jen dalším pokusem a
Znovu a znovu a znovu

153
00:08:00,530 --> 00:08:03,180
dokud jsem tak nějak náhodou
dosáhnout směrnici

154
00:08:03,180 --> 00:08:05,560
že jsem vytyčených cílů dříve.

155
00:08:05,560 --> 00:08:08,200
>> Ale víme z našich
pseudocode dříve, že je tu

156
00:08:08,200 --> 00:08:11,870
Tento pojem v programování zacyklení,
dělat něco znovu a znovu.

157
00:08:11,870 --> 00:08:14,888
A tak jsem viděl, že banda vás
sáhl po tom, co skládačky?

158
00:08:14,888 --> 00:08:17,870

159
00:08:17,870 --> 00:08:18,730
Opakujte, dokud.

160
00:08:18,730 --> 00:08:21,400
Takže bychom mohli něco udělat
jako opakujte, dokud.

161
00:08:21,400 --> 00:08:23,760
A co jste opakujte, dokud přesně?

162
00:08:23,760 --> 00:08:27,720

163
00:08:27,720 --> 00:08:28,540
>> OK.

164
00:08:28,540 --> 00:08:31,974
A nech mě jít s jedním, který je
poněkud jednodušší jen na okamžik.

165
00:08:31,974 --> 00:08:33,140
Nech mě jít dopředu a to udělat.

166
00:08:33,140 --> 00:08:35,559
Všimněte si, že, jak můžete mít
objevil pod kontrolou,

167
00:08:35,559 --> 00:08:38,409
je toto opakování blok, který
nevypadá, že je to tak velký.

168
00:08:38,409 --> 00:08:41,039
Není toho moc pokoje v hotelu
mezi těmito dvěma žlutou čárou.

169
00:08:41,039 --> 00:08:43,539
Ale jak někteří z vás mohou mít
si všiml, pokud jste drag and drop,

170
00:08:43,539 --> 00:08:45,150
Všimněte si, jak roste k vyplnění tvaru.

171
00:08:45,150 --> 00:08:46,274
>> A dokonce můžete nacpat víc.

172
00:08:46,274 --> 00:08:48,670
Bude to jen neustále rostou, pokud
přetahování a vznášet se nad ním.

173
00:08:48,670 --> 00:08:51,110
A já nevím, co je
Zde nejlepší, tak ať

174
00:08:51,110 --> 00:08:54,760
me alespoň opakuje pětkrát, pro
instance, a pak se vrátit na jeviště

175
00:08:54,760 --> 00:08:56,720
a klikněte na zelenou vlajku.

176
00:08:56,720 --> 00:08:59,110
A teď si všimnout, že to není úplně tam.

177
00:08:59,110 --> 00:09:02,400
>> Nyní někteří z vás navrhl, as
Victoria jen to, opakujte 10 krát.

178
00:09:02,400 --> 00:09:05,140
A to obvykle dělá
dostat ho celou cestu,

179
00:09:05,140 --> 00:09:10,510
Ale nebylo tam být odolnější
způsob, než svévolně přijít na to,

180
00:09:10,510 --> 00:09:12,640
kolik tahů udělat?

181
00:09:12,640 --> 00:09:17,680
Co by mohlo být lepší blok
než opakovat 10krát být?

182
00:09:17,680 --> 00:09:20,380
>> Jo, tak proč ne něco navždy?

183
00:09:20,380 --> 00:09:24,390
A teď mi dovolte přesunout tento kousek skládačky
tam uvnitř a zbavit se této jedné.

184
00:09:24,390 --> 00:09:28,300
Nyní všimnout, bez ohledu na místo Scratch
Spustí se, chodí k okraji.

185
00:09:28,300 --> 00:09:30,700
A naštěstí MIT,
kdo dělá nuly, jen

186
00:09:30,700 --> 00:09:33,190
zajišťuje, že nikdy
zmizí úplně.

187
00:09:33,190 --> 00:09:35,360
Vždy se můžete chytit svůj ocas.

188
00:09:35,360 --> 00:09:37,680
>> A právě intuitivně,
proč se neustále v pohybu?

189
00:09:37,680 --> 00:09:38,892
Co se to tu děje?

190
00:09:38,892 --> 00:09:41,440

191
00:09:41,440 --> 00:09:43,824
Zdá se, že se zastavil, ale
Pak když jsem vyzvednout a táhněte

192
00:09:43,824 --> 00:09:45,240
Pořád chce jít tam.

193
00:09:45,240 --> 00:09:46,123
Proč tomu tak je?

194
00:09:46,123 --> 00:09:51,610

195
00:09:51,610 --> 00:09:54,360
Opravdu, je počítač doslova
dělat to, co jste to říct dělat.

196
00:09:54,360 --> 00:09:58,380
Takže pokud jste to řekl dříve dělat
Následující věc navždy, přesunout 10 kroků,

197
00:09:58,380 --> 00:10:01,860
že to bude pokračovat a bude
až jsem narazila na červenou stopku

198
00:10:01,860 --> 00:10:04,620
a zastavení programu úplně.

199
00:10:04,620 --> 00:10:06,610
>> Takže i když ne
to, jak bych mohl

200
00:10:06,610 --> 00:10:09,510
aby Scratch pohybovat rychleji
přes obrazovku?

201
00:10:09,510 --> 00:10:12,060

202
00:10:12,060 --> 00:10:13,280
Další kroky, ne?

203
00:10:13,280 --> 00:10:15,710
Takže místo toho dělal 10
v době, proč ne my

204
00:10:15,710 --> 00:10:20,100
jděte do toho a změnit jej to--
Co byste propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Takže teď jdu kliknout na zelenou
vlajka, a opravdu, jede opravdu rychle.

206
00:10:24,410 --> 00:10:27,180
>> A to, samozřejmě, je jen
projevem animace.

207
00:10:27,180 --> 00:10:28,060
Co je animace?

208
00:10:28,060 --> 00:10:33,090
Je to jen vy zobrazující lidskému
celá řada statických snímků ve skutečnosti,

209
00:10:33,090 --> 00:10:34,160
opravdu, ale opravdu rychle.

210
00:10:34,160 --> 00:10:36,500
A tak jestli jsme jen říkat
ho přesunout více kroků,

211
00:10:36,500 --> 00:10:39,750
my jsme jen mít vliv mělo být
Změna kde je na obrazovce

212
00:10:39,750 --> 00:10:42,900
o to rychleji za jednotku času.

213
00:10:42,900 --> 00:10:46,454
>> Nyní další úkol, který jsem navrhl
měl mít ho odrazit přes okraj.

214
00:10:46,454 --> 00:10:49,120
A aniž by věděl, co puzzle
kusy exist--, protože to je v pořádku

215
00:10:49,120 --> 00:10:53,030
pokud nechcete dostat do
etapa challenge-- co

216
00:10:53,030 --> 00:10:54,280
chceš dělat intuitivně?

217
00:10:54,280 --> 00:10:58,030
Jak bychom museli ho odrazí zpět a
dále, mezi levou a pravou?

218
00:10:58,030 --> 00:11:02,630

219
00:11:02,630 --> 00:11:03,810
>> To jo.

220
00:11:03,810 --> 00:11:05,680
Takže potřebujeme nějaký druh
o stavu, a my

221
00:11:05,680 --> 00:11:09,710
Zdá se, že podmiňovací, tak
říkajíc, v kategorii Control.

222
00:11:09,710 --> 00:11:14,110
Který z těchto bloků
budeme chtít?

223
00:11:14,110 --> 00:11:15,200
Jo, možná "if, then."

224
00:11:15,200 --> 00:11:18,780
Takže si všimnout, že mezi žlutými bloky
tu máme, je to "kdyby"

225
00:11:18,780 --> 00:11:23,920
nebo to "if, else" blok, který bude
nám umožňují učinit rozhodnutí, jak toho dosáhnout

226
00:11:23,920 --> 00:11:25,000
nebo to udělat.

227
00:11:25,000 --> 00:11:27,380
A dokonce můžete vnořit jim
dělat více věcí.

228
00:11:27,380 --> 00:11:34,910
Nebo pokud jste dosud pryč tady,
pokračovat do kategorie snímání

229
00:11:34,910 --> 00:11:39,612
a-- uvidíme, jestli je to tady.

230
00:11:39,612 --> 00:11:43,050

231
00:11:43,050 --> 00:11:52,050
>> Takže to, co blok by mohlo být užitečné zde
zjistit, zda je to z jeviště?

232
00:11:52,050 --> 00:11:56,740
Jo, všimněte si, že některé z těchto bloků
lze parametrizovat, abych tak řekl.

233
00:11:56,740 --> 00:12:00,706
Mohou být nějak přizpůsobit, nikoli
Na rozdíl od HTML včera s atributy,

234
00:12:00,706 --> 00:12:03,330
pokud tyto atributy druh
přizpůsobit chování tagu.

235
00:12:03,330 --> 00:12:08,880
Stejně tak zde, mohu uchopit toto dojemné
blok a změny a položit otázku,

236
00:12:08,880 --> 00:12:11,500
jste dotýká myš
Ukazatel jako kurzor

237
00:12:11,500 --> 00:12:13,250
nebo jste dotýkat okraje?

238
00:12:13,250 --> 00:12:15,210
>> Tak nech mě jít dovnitř a udělat.

239
00:12:15,210 --> 00:12:18,130
Jdu pro oddálení na chvíli.

240
00:12:18,130 --> 00:12:21,320
Nech mě uchopit tento kousek skládačky
Zde tento skládačky to,

241
00:12:21,320 --> 00:12:24,570
a budu míchanice
je až na chvíli.

242
00:12:24,570 --> 00:12:27,620
Chystám se pohybovat to,
změnit na dotyku hrany,

243
00:12:27,620 --> 00:12:38,590
a já jdu do pohybu to udělat.

244
00:12:38,590 --> 00:12:40,490
Takže tady jsou některé ingredience.

245
00:12:40,490 --> 00:12:42,570
Myslím, že mám všechno, co chci.

246
00:12:42,570 --> 00:12:47,710
>> By někdo chtěl navrhnout, jak jsem
lze připojit tyto možná shora dolů

247
00:12:47,710 --> 00:12:52,020
za účelem vyřešení problému s
Scratch pohyb zprava doleva doprava na

248
00:12:52,020 --> 00:12:57,020
zleva zprava doleva, přičemž každý
pokus o najetí odráží od zdi?

249
00:12:57,020 --> 00:12:58,050
Co chci dělat?

250
00:12:58,050 --> 00:13:01,097
Které blokují bych měl připojit k internetu
"Při zelenou vlajkou klepnutí na prvním místě"?

251
00:13:01,097 --> 00:13:04,060

252
00:13:04,060 --> 00:13:06,200
>> OK, takže začněme s "navždy".

253
00:13:06,200 --> 00:13:07,170
Co se děje uvnitř dál?

254
00:13:07,170 --> 00:13:10,290
Někdo jiný.

255
00:13:10,290 --> 00:13:11,850
OK, pohybovat kroky.

256
00:13:11,850 --> 00:13:12,350
Dobře.

257
00:13:12,350 --> 00:13:14,470
A co pak?

258
00:13:14,470 --> 00:13:15,120
Takže potom, jestliže.

259
00:13:15,120 --> 00:13:17,720
A všimněte si, i když to vypadá
obložené spolu pevně,

260
00:13:17,720 --> 00:13:19,500
to bude jen růst zaplnit.

261
00:13:19,500 --> 00:13:21,500
To bude jen skočit, kde to chci.

262
00:13:21,500 --> 00:13:25,920
>> A co mám dát mezi
if a poté?

263
00:13:25,920 --> 00:13:27,180
Pravděpodobně ", pokud se dotknete hrany."

264
00:13:27,180 --> 00:13:31,800
A oznámení, opět, je to příliš velká
pro něj, ale poroste zaplnit.

265
00:13:31,800 --> 00:13:35,002
A pak zase 15 stupňů?

266
00:13:35,002 --> 00:13:35,710
Kolik stupňů?

267
00:13:35,710 --> 00:13:38,800

268
00:13:38,800 --> 00:13:41,196
Jo, takže 180 bude točit
mě celou cestu kolem.

269
00:13:41,196 --> 00:13:42,570
Tak uvidíme, jestli mám toto právo.

270
00:13:42,570 --> 00:13:43,930
Nech mě oddálit.

271
00:13:43,930 --> 00:13:45,130
>> Nech mě táhnout Scratch nahoru.

272
00:13:45,130 --> 00:13:50,030
Takže on je trochu zkreslený
teď, ale to je v pořádku.

273
00:13:50,030 --> 00:13:52,231
Jak mohu resetovat ho snadno?

274
00:13:52,231 --> 00:13:59,879

275
00:13:59,879 --> 00:14:01,045
Jdu trochu podvádět.

276
00:14:01,045 --> 00:14:04,074

277
00:14:04,074 --> 00:14:05,990
Tak jsem přidat další
blok, jen aby bylo jasno.

278
00:14:05,990 --> 00:14:08,424
Chci, aby bod o 90 stupňů
doprava ve výchozím nastavení,

279
00:14:08,424 --> 00:14:10,840
tak jsem prostě jít mu to říct
k tomu, že programově.

280
00:14:10,840 --> 00:14:11,632
A tady jdeme.

281
00:14:11,632 --> 00:14:14,740

282
00:14:14,740 --> 00:14:15,740
Zdá se, že to udělal.

283
00:14:15,740 --> 00:14:19,980
Je to trochu divné, protože
on šel vzhůru nohama.

284
00:14:19,980 --> 00:14:21,250
Říkejme, že chyby.

285
00:14:21,250 --> 00:14:22,120
To je chyba.

286
00:14:22,120 --> 00:14:27,320
Chyba je chyba v programu, A
logická chyba, že jsem člověk, udělal.

287
00:14:27,320 --> 00:14:28,985
Proč se děje vzhůru nohama?

288
00:14:28,985 --> 00:14:33,560

289
00:14:33,560 --> 00:14:35,250
Věděli MIT mhouřit nebo jsem?

290
00:14:35,250 --> 00:14:38,840

291
00:14:38,840 --> 00:14:42,550
>> Jo, myslím, že to není MIT
chyba. Dali mi kousek skládačky

292
00:14:42,550 --> 00:14:44,970
který říká, že otočit určitý počet stupňů.

293
00:14:44,970 --> 00:14:47,672
A na Victoria je návrh,
Jsem otočil o 180 stupňů,

294
00:14:47,672 --> 00:14:48,880
což je ta správná intuice.

295
00:14:48,880 --> 00:14:53,700
Ale otočení o 180 stupňů doslovně
znamená otočení o 180 stupňů,

296
00:14:53,700 --> 00:14:55,860
a to není opravdu
co chci, zřejmě.

297
00:14:55,860 --> 00:14:58,026
Vzhledem k tomu, aspoň že je v
Tento dvourozměrný svět,

298
00:14:58,026 --> 00:15:00,740
takže soustružení se opravdu děje
aby ho otočit vzhůru nohama.

299
00:15:00,740 --> 00:15:04,030
>> Asi chci použít to, co blok
Místo toho, podle toho, co vidíte tady?

300
00:15:04,030 --> 00:15:11,890

301
00:15:11,890 --> 00:15:14,790
Jak můžeme tento problém vyřešit?

302
00:15:14,790 --> 00:15:18,380
Jo, takže jsme mohli poukázat
v opačném směru.

303
00:15:18,380 --> 00:15:22,300
A vlastně i to je
nebude stačit,

304
00:15:22,300 --> 00:15:26,410
protože můžeme jen těžko kód
aby ukázal vlevo nebo vpravo.

305
00:15:26,410 --> 00:15:27,920
>> Víš, co bychom mohli dělat?

306
00:15:27,920 --> 00:15:30,160
Vypadá to, že máme
pohodlí blok zde.

307
00:15:30,160 --> 00:15:32,987
Kdybych přiblížit, viz
něco, co se nám líbí tady?

308
00:15:32,987 --> 00:15:36,120

309
00:15:36,120 --> 00:15:40,020
Takže to vypadá, že MIT má
abstrakce postavena v roce tady.

310
00:15:40,020 --> 00:15:45,440
Tento blok se zdá být ekvivalentní
na které ostatní bloky, množné číslo?

311
00:15:45,440 --> 00:15:49,510
>> Tento jeden blok se zdá být ekvivalentní
k celé této trojice bloků

312
00:15:49,510 --> 00:15:50,880
že tu máme.

313
00:15:50,880 --> 00:15:54,670
Tak to dopadá mohu zjednodušit můj
Program zbavíme to všechno

314
00:15:54,670 --> 00:15:58,270
a jen dát to tady.

315
00:15:58,270 --> 00:16:01,620
A teď je ještě trochu
buggy, a to je v pořádku pro tuto chvíli.

316
00:16:01,620 --> 00:16:03,370
Necháme to být.

317
00:16:03,370 --> 00:16:06,000
Ale můj program je dokonce
jednodušší, a to taky,

318
00:16:06,000 --> 00:16:09,060
by být reprezentativní
si za cíl v programming--

319
00:16:09,060 --> 00:16:13,430
je v ideálním případě vytvořit svůj kód jako
jednoduché, kompaktní, jak je to možné,

320
00:16:13,430 --> 00:16:15,650
a přitom stále as
čitelné jak je to možné.

321
00:16:15,650 --> 00:16:20,310
Nechcete, aby to tak pregnantní
že je těžké pochopit.

322
00:16:20,310 --> 00:16:22,826
>> Nevšimnout jsem nahradil
tři bloky s jedním,

323
00:16:22,826 --> 00:16:24,200
a to je pravděpodobně dobrá věc.

324
00:16:24,200 --> 00:16:27,280
Já jsem abstrahovat pryč pojmu
kontroly, zda jste

325
00:16:27,280 --> 00:16:29,120
na hraně jen jeden blok.

326
00:16:29,120 --> 00:16:31,520
Nyní můžeme bavit s tím, ve skutečnosti.

327
00:16:31,520 --> 00:16:35,790
To nepřidá tolik
intelektuální hodnotu, ale hravý hodnotu.

328
00:16:35,790 --> 00:16:39,730
Chystám se pokračovat
a chytit tento zvuk zde.

329
00:16:39,730 --> 00:16:42,900

330
00:16:42,900 --> 00:16:46,420
Tak nech mě jít dopředu, a dovolte mi, abych
program zastavit na chvíli.

331
00:16:46,420 --> 00:16:52,070
Chystám se zaznamenat následující,
umožňující přístup k mému mikrofonu.

332
00:16:52,070 --> 00:16:53,181
>> Jdeme na to.

333
00:16:53,181 --> 00:16:53,680
Ouch.

334
00:16:53,680 --> 00:16:58,710

335
00:16:58,710 --> 00:17:01,140
Zkusme to znovu.

336
00:17:01,140 --> 00:17:02,279
Jdeme na to.

337
00:17:02,279 --> 00:17:03,570
OK, zaznamenal jsem špatnou věc.

338
00:17:03,570 --> 00:17:04,580
Jdeme na to.

339
00:17:04,580 --> 00:17:05,080
Ouch.

340
00:17:05,080 --> 00:17:07,910

341
00:17:07,910 --> 00:17:08,800
Ouch.

342
00:17:08,800 --> 00:17:09,300
Dobře.

343
00:17:09,300 --> 00:17:10,791
Teď potřebuji se zbavit toho.

344
00:17:10,791 --> 00:17:11,290
Dobře.

345
00:17:11,290 --> 00:17:13,950
>> Takže teď mám
nahrávka jen "Au."

346
00:17:13,950 --> 00:17:18,040
Takže teď jdu
vpřed a nazývat "Au."

347
00:17:18,040 --> 00:17:20,270
Chystám se vrátit
mých skriptů, a teď

348
00:17:20,270 --> 00:17:25,460
Oznámení, že je to blok, který se nazývá
přehrát zvuk "mňau" nebo přehrát zvuk "Au."

349
00:17:25,460 --> 00:17:28,920
Chystám se přetáhnout, a kde
Měl bych dát to na komický efekt?

350
00:17:28,920 --> 00:17:31,740

351
00:17:31,740 --> 00:17:37,860
Jo, takže teď je to trochu
buggy, protože teď to block--

352
00:17:37,860 --> 00:17:42,050
Všimněte si, jak toto "-li na hraně,
odraz "je tak trochu soběstačný.

353
00:17:42,050 --> 00:17:43,704
Tak jsem třeba to napravit.

354
00:17:43,704 --> 00:17:44,870
Nech mě jít dopředu a to udělat.

355
00:17:44,870 --> 00:17:48,630
Dovolte mi, abych se zbavit tohoto a vrátit
k naší původní, více úmyslné

356
00:17:48,630 --> 00:17:49,870
funkčnost.

357
00:17:49,870 --> 00:18:01,080
Takže ", pokud se dotknete hrany, pak" Chci
otočit, jak Victoria navrženo,

358
00:18:01,080 --> 00:18:02,480
180 stupňů.

359
00:18:02,480 --> 00:18:05,497
A nechci hrát
zvuk "Au" tam?

360
00:18:05,497 --> 00:18:11,800

361
00:18:11,800 --> 00:18:15,580
>> Jo, všimněte si, že je to venku
že žlutý blok.

362
00:18:15,580 --> 00:18:17,680
Takže i to, by bylo
bug, ale všiml jsem si to.

363
00:18:17,680 --> 00:18:21,290
Takže budu přetáhněte ji tady,
a upozornění teď je to uvnitř "pokud".

364
00:18:21,290 --> 00:18:24,250
Takže "pokud" je tento druh
podobnou ramenem jako skvrna

365
00:18:24,250 --> 00:18:26,260
že to bude jen
to, co je uvnitř ní.

366
00:18:26,260 --> 00:18:30,216
Takže teď, když jsem oddálit na
riziko annoying--

367
00:18:30,216 --> 00:18:32,860

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Au, Au, Au.

369
00:18:36,470 --> 00:18:39,910
>> DAVID Malan: A
bude jen pokračovat donekonečna.

370
00:18:39,910 --> 00:18:44,160
Teď už jen stačí k urychlení věci
tady, nech mě jít dopředu a otevřít,

371
00:18:44,160 --> 00:18:50,460
pojďme say-- nech mě jít k některým
ze své vlastní věci z třídy.

372
00:18:50,460 --> 00:18:53,000

373
00:18:53,000 --> 00:19:00,220
A dovolte mi otevřít, řekněme, toto
jedna ze strany jednoho z našich výukových kolegy

374
00:19:00,220 --> 00:19:01,500
před pár lety.

375
00:19:01,500 --> 00:19:04,732
Takže někteří z vás možná pamatujete
Tato hra z dávných dob,

376
00:19:04,732 --> 00:19:05,940
a je to skutečně pozoruhodné.

377
00:19:05,940 --> 00:19:08,190
I přesto, že jsme hotová
Nejjednodušší programů právě teď,

378
00:19:08,190 --> 00:19:09,980
uvažujme, co to
ve skutečnosti vypadá.

379
00:19:09,980 --> 00:19:10,650
Nech mě zasáhla hru.

380
00:19:10,650 --> 00:19:14,210

381
00:19:14,210 --> 00:19:18,980
>> Takže v této hře, máme
žába, a pomocí šipky keys--

382
00:19:18,980 --> 00:19:23,340
bere větší kroky, než jsem remember--
Mám kontrolu nad touto žábou.

383
00:19:23,340 --> 00:19:29,630
A cílem je dostat se přes rušný
Cesta bez spuštění do auta.

384
00:19:29,630 --> 00:19:34,735
A pojďme see-- když půjdu sem, já
muset počkat na protokol k posouvat.

385
00:19:34,735 --> 00:19:38,130

386
00:19:38,130 --> 00:19:39,274
To se cítí jako brouk.

387
00:19:39,274 --> 00:19:42,240

388
00:19:42,240 --> 00:19:43,495
To je druh chyby.

389
00:19:43,495 --> 00:19:45,980

390
00:19:45,980 --> 00:19:46,480
Dobře.

391
00:19:46,480 --> 00:19:51,550
Jsem na to tady,
tam, a pak budete mít

392
00:19:51,550 --> 00:19:54,100
jít, až se dostanete vše
žáby na lilie podložky.

393
00:19:54,100 --> 00:19:55,920
Teď to může vypadat
o to složitější,

394
00:19:55,920 --> 00:19:57,840
ale pojďme zkusit zlomit
toto dole psychicky

395
00:19:57,840 --> 00:20:00,040
a slovně na jednotlivé bloky.

396
00:20:00,040 --> 00:20:03,910
Takže je to asi logická
kus, který jsme ještě neviděli

397
00:20:03,910 --> 00:20:07,440
ale to reaguje na úhozů,
k věcem jsem narazila na klávesnici.

398
00:20:07,440 --> 00:20:11,660
>> Takže je to asi nějaká
blok, který říká, je-li klíč rovná up,

399
00:20:11,660 --> 00:20:15,965
pak udělat něco s Scratch--
Možná ji přesunout 10 kroků tímto způsobem.

400
00:20:15,965 --> 00:20:20,240
Je-li stisknuté klávesy pohybovat 10 kroků
Tímto způsobem, nebo vlevo klíč, přesunout 10 kroků

401
00:20:20,240 --> 00:20:21,710
Tímto způsobem deset kroků, které.

402
00:20:21,710 --> 00:20:23,644
Já jsem jasně ukázalo kočku v žábu.

403
00:20:23,644 --> 00:20:26,060
Tak to je jen, kdy
kostým, jak Scratch hovory to-- my

404
00:20:26,060 --> 00:20:28,440
právě importovali obraz žáby.

405
00:20:28,440 --> 00:20:29,570
>> Ale co jiného se děje?

406
00:20:29,570 --> 00:20:32,794
Jaké další řádky kódu,
co skládačky

407
00:20:32,794 --> 00:20:35,460
udělal Blake, náš kolega učení,
použít v tomto programu, podle všeho?

408
00:20:35,460 --> 00:20:38,320

409
00:20:38,320 --> 00:20:42,730
Co se dělat všechno move--
co programovací postavit?

410
00:20:42,730 --> 00:20:44,950
>> Motion, takže sure--
přesunout blok, pro jistotu.

411
00:20:44,950 --> 00:20:49,330
A co je to pohyb blok
uvnitř, s největší pravděpodobností?

412
00:20:49,330 --> 00:20:52,850
Jo, nějaký druh smyčky, možná
navždy zablokovat, možná opakování block--

413
00:20:52,850 --> 00:20:54,070
opakujte, dokud bloku.

414
00:20:54,070 --> 00:20:57,330
A to je to, co dělat protokoly a
Lily podložky a všechno ostatní tah

415
00:20:57,330 --> 00:20:57,990
sem a tam.

416
00:20:57,990 --> 00:21:00,270
Je to prostě děje donekonečna.

417
00:21:00,270 --> 00:21:03,180
>> Proč jsou některé vozy
pohybující se rychleji než ostatní?

418
00:21:03,180 --> 00:21:06,607
Jaký je rozdíl o těchto programech?

419
00:21:06,607 --> 00:21:09,690
Jo, pravděpodobně některé z nich užíváte
více kroků najednou a některé z nich

420
00:21:09,690 --> 00:21:10,690
méně kroků najednou.

421
00:21:10,690 --> 00:21:14,670
A vizuální efekt
je velmi pomalý proti.

422
00:21:14,670 --> 00:21:16,030
>> Co myslíš, že se stalo?

423
00:21:16,030 --> 00:21:19,700
Když jsem dostal žábu celou cestu
přes ulici a řeku

424
00:21:19,700 --> 00:21:23,560
na lilie pad, něco
pozoruhodný stalo.

425
00:21:23,560 --> 00:21:26,540
Co se stalo, hned jak jsem to udělal?

426
00:21:26,540 --> 00:21:27,210
To se zastavil.

427
00:21:27,210 --> 00:21:29,680
Že žába se zastavil, a
Dostal jsem druhou žába.

428
00:21:29,680 --> 00:21:33,155
Takže to, co musí být konstrukt
používán tam, jaké funkce?

429
00:21:33,155 --> 00:21:36,020

430
00:21:36,020 --> 00:21:38,660
>> Jo, takže tam je nějaký druh
"Kdyby" podmiňují tam nahoře, taky.

431
00:21:38,660 --> 00:21:41,909
A ukázalo se out-- jsme neviděli tohle--
ale je tu další bloky v tam, že

432
00:21:41,909 --> 00:21:45,300
Dá se říci, pokud jste dojemné
Další věc, na obrazovce,

433
00:21:45,300 --> 00:21:47,720
pokud jste se dotýká lilie pad "a poté".

434
00:21:47,720 --> 00:21:50,810
A pak je to, když jsme
aby se druhá žába objeví.

435
00:21:50,810 --> 00:21:54,969
Takže i když tato hra je určitě
velmi starý, i když na první pohled

436
00:21:54,969 --> 00:21:58,010
tam je tolik děje on-- a Blake
ani bič to ve dvou minut,

437
00:21:58,010 --> 00:22:00,390
to asi trvalo mu několik
hodiny vytvořit tuto hru

438
00:22:00,390 --> 00:22:03,850
založený na jeho paměti nebo videa
verze dávných dob je to.

439
00:22:03,850 --> 00:22:07,940
Ale všechny tyto maličkostí
děje na obrazovce v izolaci

440
00:22:07,940 --> 00:22:11,550
redukuje na tyto velmi jednoduché
constructs-- pohyby nebo prohlášení

441
00:22:11,550 --> 00:22:15,519
jako jsme diskutovali, smyček a
podmínky, a to je o tom.

442
00:22:15,519 --> 00:22:17,060
Je tu několik dalších milovník rysy.

443
00:22:17,060 --> 00:22:19,130
Některé z nich jsou čistě
estetické nebo akustické,

444
00:22:19,130 --> 00:22:20,964
jako zvuky Jen jsem hrál.

445
00:22:20,964 --> 00:22:23,380
Ale z větší části, budete
mají v tomto jazyce, škrábání,

446
00:22:23,380 --> 00:22:25,350
všechny základní
stavební kameny, které vás

447
00:22:25,350 --> 00:22:29,280
mají v C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
a jakýkoliv počet dalších jazyků.

449
00:22:32,960 --> 00:22:36,720
Jakékoliv otázky ohledně začátku?

450
00:22:36,720 --> 00:22:37,220
Dobře.

451
00:22:37,220 --> 00:22:40,303
Takže nebudeme ponořit hlouběji do nuly,
když jste zač tento víkend,

452
00:22:40,303 --> 00:22:42,860
zvláště pokud máte děti nebo
neteře a synovci a takové,

453
00:22:42,860 --> 00:22:44,220
uvést je do nuly.

454
00:22:44,220 --> 00:22:47,960
Je to vlastně úžasně hravé
Prostředí se, jak jeho autoři říkají,

455
00:22:47,960 --> 00:22:49,120
velmi vysoké stropy.

456
00:22:49,120 --> 00:22:51,670
I když jsme začali s
právě detaily low-level,

457
00:22:51,670 --> 00:22:54,890
můžete opravdu dost
s ním, a to je možná

458
00:22:54,890 --> 00:22:57,360
ukázka přesně to.

459
00:22:57,360 --> 00:23:02,920
>> Ale pojďme teď přejít na něco víc
sofistikované problémy, chcete-li,

460
00:23:02,920 --> 00:23:05,870
známý jako "vyhledávání" a
"Třídění," obecněji.

461
00:23:05,870 --> 00:23:09,500
Měli jsme tento telefonní seznam zde earlier-- je
ještě jeden jen pro discussion--

462
00:23:09,500 --> 00:23:13,460
že jsme byli schopni vyhledávat
efektivněji, protože

463
00:23:13,460 --> 00:23:15,270
významného předpokladu.

464
00:23:15,270 --> 00:23:17,655
A jen proto, aby bylo jasno, jaké
předpoklad byl jsem dělat

465
00:23:17,655 --> 00:23:19,280
Při vyhledávání prostřednictvím tohoto telefonního seznamu?

466
00:23:19,280 --> 00:23:23,342

467
00:23:23,342 --> 00:23:25,300
Že Mike Smith byl v
telefonního seznamu, i když jsem

468
00:23:25,300 --> 00:23:27,410
by měl být schopen zvládnout
Scénář bez něj

469
00:23:27,410 --> 00:23:30,720
tam, pokud jsem se předčasně ukončena.

470
00:23:30,720 --> 00:23:31,806
Kniha je abecední.

471
00:23:31,806 --> 00:23:33,930
A to je velmi velkorysý
předpoklad, protože

472
00:23:33,930 --> 00:23:36,580
znamená someone-- Jsem typ
řezání za roh,

473
00:23:36,580 --> 00:23:40,580
jako já rychleji, protože někým
jiný udělal hodně tvrdé práce pro mě.

474
00:23:40,580 --> 00:23:43,120
>> Ale co když je telefon
Kniha byla nevytříděné?

475
00:23:43,120 --> 00:23:47,050
Možná, že Verizon dostal líný, právě hodil
Jména všech a čísla tam

476
00:23:47,050 --> 00:23:50,120
Možná v pořadí, v jakém
přihlásili k telefonní služby.

477
00:23:50,120 --> 00:23:54,570
A kolik času zabere mi
najít někoho, jako je Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 strana telefonu book-- kolik
Stránky musím prohlédnout?

479
00:23:58,160 --> 00:23:58,905
>> Všichni.

480
00:23:58,905 --> 00:24:00,030
Vy jste nějak smůlu.

481
00:24:00,030 --> 00:24:03,420
Doslova se podívat na každý
strana v případě, že telefonní seznam je jen

482
00:24:03,420 --> 00:24:04,450
náhodně třídit.

483
00:24:04,450 --> 00:24:06,910
Možná budete mít štěstí a najít Mika
na první stránce, protože on

484
00:24:06,910 --> 00:24:08,826
byl první zákazník
objednat telefonní služby.

485
00:24:08,826 --> 00:24:10,760
Ale on by mohl být poslední, taky.

486
00:24:10,760 --> 00:24:12,500
>> Takže náhodném pořadí není dobré.

487
00:24:12,500 --> 00:24:16,750
Takže předpokládám, že musíme seřadíte
telefonním seznamu nebo v souhrnném třídění dat

488
00:24:16,750 --> 00:24:18,520
že nám byla dána.

489
00:24:18,520 --> 00:24:19,440
Jak můžeme udělat?

490
00:24:19,440 --> 00:24:21,360
>> No, dovolte mi pokusit
jednoduchý příklad zde.

491
00:24:21,360 --> 00:24:24,290
Nech mě jít dopředu a hodit
Několik čísel na palubě.

492
00:24:24,290 --> 00:24:35,480
Předpokládejme, že čísla, která máme, jsou
řekněme, čtyři, dva, jedna a tři.

493
00:24:35,480 --> 00:24:38,390
A Ben, třídění těchto čísel pro nás.

494
00:24:38,390 --> 00:24:39,017
>> OK dobře.

495
00:24:39,017 --> 00:24:39,850
Jak jsi to udělal?

496
00:24:39,850 --> 00:24:42,731

497
00:24:42,731 --> 00:24:43,230
Dobře.

498
00:24:43,230 --> 00:24:44,710
Takže začít s nejmenší
hodnotou a nejvyšší,

499
00:24:44,710 --> 00:24:46,084
a to je opravdu dobrá intuice.

500
00:24:46,084 --> 00:24:48,080
A uvědomit si, že jsme
lidé jsou vlastně docela

501
00:24:48,080 --> 00:24:49,913
dobrý v řešení problémů
jako je tento, minimálně

502
00:24:49,913 --> 00:24:51,810
při data je relativně malý.

503
00:24:51,810 --> 00:24:54,860
Jakmile se začnete mít stovky
čísel, tisíce čísel,

504
00:24:54,860 --> 00:24:58,440
milióny čísel, Ben pravděpodobně
Nemohl to docela tak rychle,

505
00:24:58,440 --> 00:25:00,620
za předpokladu, že existují
mezery v číslech.

506
00:25:00,620 --> 00:25:03,450
Docela snadno spočítat na milion
V opačném případě pouze časově náročné.

507
00:25:03,450 --> 00:25:07,150
>> Takže to vypadá algoritmus
jako Ben používá právě teď

508
00:25:07,150 --> 00:25:08,930
Byl hledat pro nejmenší číslo.

509
00:25:08,930 --> 00:25:12,900
Takže i když my lidé mohou mít
v mnoha informací vizuálně,

510
00:25:12,900 --> 00:25:14,830
počítač je ve skutečnosti
trochu omezenější.

511
00:25:14,830 --> 00:25:17,560
Počítač může jen
podíváme na jeden byte v době

512
00:25:17,560 --> 00:25:20,770
nebo možná čtyři byty na první time--
v těchto dnech možná 8 bytů na jeden time--

513
00:25:20,770 --> 00:25:24,450
ale velmi malý počet
bytů v daném čase.

514
00:25:24,450 --> 00:25:28,480
>> Takže vzhledem k tomu, že skutečně máme
čtyři oddělené hodnoty here--

515
00:25:28,480 --> 00:25:32,440
a můžete si myslet, že mají Ben
klapky na kdyby byl počítač jako

516
00:25:32,440 --> 00:25:36,450
že nevidí nic jiného,
než jedno číslo při time--

517
00:25:36,450 --> 00:25:39,720
takže jsme se obecně bude předpokládat, stejně jako v
Angličtina, budeme číst zprava doleva.

518
00:25:39,720 --> 00:25:42,870
Takže první číslo Ben asi vypadal
v Byly čtyři a pak se velmi rychle

519
00:25:42,870 --> 00:25:44,770
si uvědomil, že je to dost velký
number-- nech mě hledat dál.

520
00:25:44,770 --> 00:25:45,357
>> Je tu dva.

521
00:25:45,357 --> 00:25:45,940
Počkej chvíli.

522
00:25:45,940 --> 00:25:47,070
Dva je menší než čtyři.

523
00:25:47,070 --> 00:25:47,986
Jdu si vzpomenout.

524
00:25:47,986 --> 00:25:49,070
Dva je nyní nejmenší.

525
00:25:49,070 --> 00:25:50,417
Nyní one-- je to ještě lepší.

526
00:25:50,417 --> 00:25:51,250
To je ještě menší.

527
00:25:51,250 --> 00:25:54,000
Jdu na to zapomenout dva
a stačí vzpomenout si jej.

528
00:25:54,000 --> 00:25:56,550
>> A mohl přestat hledat?

529
00:25:56,550 --> 00:25:58,360
No, mohl založený
Na základě těchto informací,

530
00:25:58,360 --> 00:26:00,477
ale už tak vyhledávání
zbytek seznamu.

531
00:26:00,477 --> 00:26:02,060
Vzhledem k tomu, co když nulu byly v seznamu?

532
00:26:02,060 --> 00:26:03,643
Co když negativní některý z nich v seznamu?

533
00:26:03,643 --> 00:26:07,720
On jen ví, že jeho odpověď
je správná, pokud je to vyčerpávajícím způsobem

534
00:26:07,720 --> 00:26:08,729
kontroluje celý seznam.

535
00:26:08,729 --> 00:26:10,020
Takže se podíváme na zbytek tohoto.

536
00:26:10,020 --> 00:26:11,394
Three-- to bylo plýtvání časem.

537
00:26:11,394 --> 00:26:13,540
Mám smůlu, ale byl jsem
Stále správné, aby tak učinily.

538
00:26:13,540 --> 00:26:17,857
A tak teď podle všeho
zvolili nejmenší počet

539
00:26:17,857 --> 00:26:20,440
a jen dát to na začátku
seznamu, jak budu dělat.

540
00:26:20,440 --> 00:26:23,480
A teď, co jsi dělal dál, přestože
jste si nemyslel, že o něm téměř

541
00:26:23,480 --> 00:26:25,962
v tomto rozsahu?

542
00:26:25,962 --> 00:26:27,670
Opakujte proces,
takže nějaký druh smyčky.

543
00:26:27,670 --> 00:26:28,920
K dispozici je známý nápad.

544
00:26:28,920 --> 00:26:30,860
Tak tady jsou čtyři.

545
00:26:30,860 --> 00:26:32,110
To je v současné době nejmenší.

546
00:26:32,110 --> 00:26:33,220
To je kandidátem.

547
00:26:33,220 --> 00:26:33,900
Už ne.

548
00:26:33,900 --> 00:26:34,770
Teď jsem viděl dva.

549
00:26:34,770 --> 00:26:36,630
To je další nejmenší prvek.

550
00:26:36,630 --> 00:26:40,800
Three-- to není menší, takže
Nyní Ben může vyklovnout dva.

551
00:26:40,800 --> 00:26:44,510
>> A teď jsme proces opakovat, a
Samozřejmě tři dostane vytáhl další.

552
00:26:44,510 --> 00:26:45,420
Tento postup opakujte.

553
00:26:45,420 --> 00:26:46,990
Čtyři dostane vytáhl.

554
00:26:46,990 --> 00:26:50,140
A teď jsme z čísel,
proto musí být seznam tříděn.

555
00:26:50,140 --> 00:26:51,960
>> A skutečně se jedná o formální algoritmus.

556
00:26:51,960 --> 00:26:56,610
Počítačový vědec by
nazývají "Volba druhu"

557
00:26:56,610 --> 00:27:00,880
bytí nápadu třídění A
znovu vypsat iteratively--

558
00:27:00,880 --> 00:27:03,807
a znovu a znovu zvolením
nejmenší číslo.

559
00:27:03,807 --> 00:27:06,140
A co je příjemné na tom je,
je to prostě tak zatraceně intuitivní.

560
00:27:06,140 --> 00:27:07,470
Je to tak jednoduché.

561
00:27:07,470 --> 00:27:11,100
A můžete opakovat stejný
znovu a znovu provoz.

562
00:27:11,100 --> 00:27:12,150
Je to jednoduché.

563
00:27:12,150 --> 00:27:17,170
>> V tomto případě se jednalo rychle, ale
jak dlouho to vlastně trvá?

564
00:27:17,170 --> 00:27:19,880
Řekněme, aby se mohlo zdát, a
cítit trochu únavné.

565
00:27:19,880 --> 00:27:24,150
Tak jeden, dva, tři, čtyři, pět šest,
sedm, osm, devět, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- libovolný počet.

567
00:27:26,160 --> 00:27:28,780
Jen jsem chtěl víc to
Doba než jen čtyři.

568
00:27:28,780 --> 00:27:30,780
Takže pokud mám jeden celek
banda čísel to now--

569
00:27:30,780 --> 00:27:32,420
ani jedno
co are-- Řekněme

570
00:27:32,420 --> 00:27:34,380
přemýšlet o tom, co to
Algoritmus je doopravdy.

571
00:27:34,380 --> 00:27:35,857
>> Předpokládejme, že existují čísla tam.

572
00:27:35,857 --> 00:27:38,190
Opět platí, že nezáleží na tom, jaké
jsou, ale jsou náhodné.

573
00:27:38,190 --> 00:27:39,679
Žádám Benův algoritmus.

574
00:27:39,679 --> 00:27:41,220
Musím vyberte nejmenší číslo.

575
00:27:41,220 --> 00:27:41,761
Co mám dělat?

576
00:27:41,761 --> 00:27:44,240
A budu fyzicky
dělat to tentokrát jednat to.

577
00:27:44,240 --> 00:27:46,099
Při pohledu, hledáte,
hledáte looking.

578
00:27:46,099 --> 00:27:48,140
Teprve v době, kdy jsem se dostat do
konec seznamu může

579
00:27:48,140 --> 00:27:51,230
Uvědomuji si nejmenší
číslo bylo dvě tentokrát.

580
00:27:51,230 --> 00:27:52,720
Jednou to není v seznamu.

581
00:27:52,720 --> 00:27:54,400
Tak jsem si položil dva.

582
00:27:54,400 --> 00:27:55,590
>> Co mám dělat dál?

583
00:27:55,590 --> 00:27:58,600
Looking looking.

584
00:27:58,600 --> 00:28:02,250
Teď jsem našel číslo sedm, protože
je tu mezery v těchto numbers--

585
00:28:02,250 --> 00:28:03,300
ale jen subjektivní.

586
00:28:03,300 --> 00:28:03,800
Dobře.

587
00:28:03,800 --> 00:28:06,030
Takže teď můžu dát dolů sedm.

588
00:28:06,030 --> 00:28:08,860
Při pohledu hledá, hledá.

589
00:28:08,860 --> 00:28:11,030
>> Teď jsem za předpokladu, ze
Samozřejmě, že Ben nemá

590
00:28:11,030 --> 00:28:14,780
extra RAM, extra
paměť, protože, samozřejmě,

591
00:28:14,780 --> 00:28:16,080
Dívám se stejným číslem.

592
00:28:16,080 --> 00:28:18,246
Určitě jsem mohl pamatoval
Ze všech těchto čísel,

593
00:28:18,246 --> 00:28:19,930
a to je naprostá pravda.

594
00:28:19,930 --> 00:28:22,610
Ale pokud Ben pamatuje všechny
z čísel, že viděl,

595
00:28:22,610 --> 00:28:24,430
on není opravdu udělal
zásadní pokrok

596
00:28:24,430 --> 00:28:26,170
protože už má
schopnost vyhledávat

597
00:28:26,170 --> 00:28:27,540
přes čísla na palubě.

598
00:28:27,540 --> 00:28:29,373
Vzpomínka na všechny
Čísla nepomůže,

599
00:28:29,373 --> 00:28:32,490
protože se může ještě jako počítač
jen se podívat na, jsme řekli, jedním číslem

600
00:28:32,490 --> 00:28:33,080
včas.

601
00:28:33,080 --> 00:28:35,760
Takže není žádný druh podvodu
tam, které můžete využít.

602
00:28:35,760 --> 00:28:39,170
>> Takže ve skutečnosti, jak jsem
pokračovat v hledání v seznamu,

603
00:28:39,170 --> 00:28:44,200
Doslova jsem si to jen dál
tam a zpět přes to, vyloupnutí

604
00:28:44,200 --> 00:28:45,710
druhý nejmenší počet.

605
00:28:45,710 --> 00:28:48,810
A jak si můžete odvodit druh
z mých hloupých pohybů,

606
00:28:48,810 --> 00:28:50,860
to prostě dostane velmi
únavné velmi rychle,

607
00:28:50,860 --> 00:28:54,850
a já se zdají být vracet a
tam, tam a zpět docela dost.

608
00:28:54,850 --> 00:29:03,220
Teď abychom byli spravedliví, nemám jít
zas až tak dobře, pojďme see-- být spravedlivý,

609
00:29:03,220 --> 00:29:06,310
Nemám chodit docela
jako řada kroků, každý čas.

610
00:29:06,310 --> 00:29:09,200
Vzhledem k tomu, samozřejmě, jak jsem
výběr čísel ze seznamu,

611
00:29:09,200 --> 00:29:11,860
zbývající seznam je čím dál kratší.

612
00:29:11,860 --> 00:29:14,240
>> A tak se pojďme přemýšlet o tom,
kolik kroků jsem vlastně

613
00:29:14,240 --> 00:29:16,010
traipsing přes každý čas.

614
00:29:16,010 --> 00:29:18,950
V úplně první situaci
jsme měli 16 čísel,

615
00:29:18,950 --> 00:29:22,210
a tak maximally-- Nechal jen
to pro discussion--

616
00:29:22,210 --> 00:29:25,640
Musel jsem se dívat až 16
Čísla najít nejmenší.

617
00:29:25,640 --> 00:29:28,420
Ale jakmile jsem vyloupíce
nejmenší číslo, jak

618
00:29:28,420 --> 00:29:30,590
dlouho byl zbývající seznam, samozřejmě?

619
00:29:30,590 --> 00:29:31,420
Jen 15.

620
00:29:31,420 --> 00:29:34,670
Takže kolik čísel dělal Ben nebo mám
prohlédnout podruhé kolem?

621
00:29:34,670 --> 00:29:36,832
15, prostě jít a najít nejmenší.

622
00:29:36,832 --> 00:29:39,540
Ale teď, samozřejmě, jejichž seznam je,
Také menší, než tomu bylo dříve.

623
00:29:39,540 --> 00:29:42,540
Tak kolik kroků udělal já
muset vzít příště?

624
00:29:42,540 --> 00:29:49,970
14 a pak 13 a poté 12 plus dot,
tečka, tečka, dokud jsem odešel jen s jedním.

625
00:29:49,970 --> 00:29:53,146
Takže teď počítačový vědec by
zeptat se, dobře, co dělá, že si všichni rovni?

626
00:29:53,146 --> 00:29:55,770
Je to vlastně rovná některými konkrétními
Číslo, které bychom mohli jistě

627
00:29:55,770 --> 00:30:00,490
dělat aritmeticky, ale chceme mluvit
o účinnosti algoritmů

628
00:30:00,490 --> 00:30:04,940
trochu víc formulaically,
nezávisle na tom, jak dlouho je seznam.

629
00:30:04,940 --> 00:30:06,240
>> A tak víte co?

630
00:30:06,240 --> 00:30:09,860
To je 16, ale jak jsem řekl dříve,
pojďme stačí zavolat na rozsah problému

631
00:30:09,860 --> 00:30:10,970
n, kde n je nějaké číslo.

632
00:30:10,970 --> 00:30:13,220
Možná je to 16, možná je to
tři, možná je to milion.

633
00:30:13,220 --> 00:30:13,761
Nevím.

634
00:30:13,761 --> 00:30:14,390
Nezajímá mě.

635
00:30:14,390 --> 00:30:16,520
Co opravdu chci, je
vzorec, který mohu

636
00:30:16,520 --> 00:30:19,420
použít k porovnání tohoto algoritmu
s jinými algoritmy

637
00:30:19,420 --> 00:30:22,350
že někdo může tvrdit,
jsou lepší nebo horší.

638
00:30:22,350 --> 00:30:25,430
>> Tak to dopadá, a to pouze já
vím, že to od základní školy,

639
00:30:25,430 --> 00:30:34,790
že to vlastně vyjde na stejné
věc jako n přes n plus jedna přes dva.

640
00:30:34,790 --> 00:30:40,020
A to se děje na rovné, z
Samozřejmě, že n a n na druhou přes dva.

641
00:30:40,020 --> 00:30:43,250
Takže když jsem chtěl vzorec
za kolik kroků

642
00:30:43,250 --> 00:30:46,330
byli zapojeni do pohledu na všechny
of znovu a znovu těmito čísly

643
00:30:46,330 --> 00:30:52,681
a znovu a znovu, řekl bych,
to n druhou a n přes dva.

644
00:30:52,681 --> 00:30:53,430
Ale víte co?

645
00:30:53,430 --> 00:30:54,500
To jen vypadá chaotický.

646
00:30:54,500 --> 00:30:56,470
Já jen opravdu chtít
obecný smysl věcí.

647
00:30:56,470 --> 00:30:58,810
A ty by mohly vyvolat z
vysoká škola, která tam

648
00:30:58,810 --> 00:31:00,660
je představa nejvyššího řádu termínu.

649
00:31:00,660 --> 00:31:05,300
Který z těchto podmínek, n
čtvercový, N, nebo polovinu,

650
00:31:05,300 --> 00:31:07,550
má největší dopad v průběhu času?

651
00:31:07,550 --> 00:31:11,920
Čím větší n dostane, což
z těchto záležitostí nejvíce?

652
00:31:11,920 --> 00:31:15,560
>> Jinými slovy, pokud se připojíte
z milionu, n čtvercový

653
00:31:15,560 --> 00:31:17,900
bude s největší pravděpodobností
dominantním faktorem,

654
00:31:17,900 --> 00:31:21,670
Vzhledem k tomu, miliónkrát
sama o sobě je mnohem větší

655
00:31:21,670 --> 00:31:23,682
než plus jeden další milion.

656
00:31:23,682 --> 00:31:24,390
Tak víte co?

657
00:31:24,390 --> 00:31:27,305
Je to tak velký zašít
číslo, pokud náměstí číslo.

658
00:31:27,305 --> 00:31:28,430
To opravdu nezáleží.

659
00:31:28,430 --> 00:31:30,596
Budeme jen kříž, který
out a zapomenout na to.

660
00:31:30,596 --> 00:31:34,250
A tak počítačový vědec by se říci,
že účinnost tohoto algoritmu

661
00:31:34,250 --> 00:31:37,850
je v řádu n squared--
Mám na mysli skutečně přiblížení.

662
00:31:37,850 --> 00:31:40,810
Je to jakýsi zhruba n druhou.

663
00:31:40,810 --> 00:31:44,130
V průběhu doby, tím větší
a větší n dostane toto

664
00:31:44,130 --> 00:31:47,610
Je to dobrý odhad pro to, co
efektivita nebo nedostatek účinnosti

665
00:31:47,610 --> 00:31:49,400
tohoto algoritmu ve skutečnosti je.

666
00:31:49,400 --> 00:31:52,040
A já odvodit, že, samozřejmě,
od skutečně dělá matematiku.

667
00:31:52,040 --> 00:31:54,040
Ale teď jsem jen mávání
mé ruce, protože jsem zrovna

668
00:31:54,040 --> 00:31:55,790
Chcete obecný smysl tohoto algoritmu.

669
00:31:55,790 --> 00:31:58,850
>> Takže za použití stejné logiky, zatím,
uvažujme jiný algoritmus

670
00:31:58,850 --> 00:32:01,162
už vypadal at-- lineární hledání.

671
00:32:01,162 --> 00:32:02,870
Když jsem hledal
pro telefonní book--

672
00:32:02,870 --> 00:32:05,980
Není jejich třídění, vyhledávání
přes telefonní book--

673
00:32:05,980 --> 00:32:09,197
jsme pořád říkala, že to bylo
1000 kroky, nebo 500 kroků.

674
00:32:09,197 --> 00:32:10,280
Ale pojďme generalizovat to.

675
00:32:10,280 --> 00:32:12,860
Pokud existuje n stránek v
telefonní seznam, co je

676
00:32:12,860 --> 00:32:17,250
doba chodu nebo
Účinnost lineární hledání?

677
00:32:17,250 --> 00:32:19,750
Je to v řádu
kolik kroků k nalezení

678
00:32:19,750 --> 00:32:24,210
Mike Smith pomocí lineární vyhledávání,
První algoritmus, nebo i druhý?

679
00:32:24,210 --> 00:32:27,240

680
00:32:27,240 --> 00:32:31,710
>> V nejhorším případě, Mike
je na konci knihy.

681
00:32:31,710 --> 00:32:35,590
Takže v případě, že telefonní seznam má 1000 stránek,
jsme si řekli minule, v nejhorším případě,

682
00:32:35,590 --> 00:32:38,380
to může trvat zhruba jak
mnoho stránek najít Miku?

683
00:32:38,380 --> 00:32:38,990
Stejně jako 1,000.

684
00:32:38,990 --> 00:32:39,830
Je to horní mez.

685
00:32:39,830 --> 00:32:41,790
Je to nejhorší možné situaci.

686
00:32:41,790 --> 00:32:44,410
Ale opět, jdeme pryč
z čísel, jako je nyní 1000.

687
00:32:44,410 --> 00:32:45,730
Je to jen n.

688
00:32:45,730 --> 00:32:47,470
>> Tak jaký je logický závěr?

689
00:32:47,470 --> 00:32:50,210
Nalezení Mika v telefonu
Kniha, která má n stran

690
00:32:50,210 --> 00:32:55,280
může trvat, v nejhorším případě,
kolik kroků v řádu n?

691
00:32:55,280 --> 00:32:58,110
A opravdu počítačový
vědec by se říci,

692
00:32:58,110 --> 00:33:02,340
že běží čas nebo se
výkonnost nebo účinnost

693
00:33:02,340 --> 00:33:07,470
nebo neúčinnost, algoritmu, jako je
lineární vyhledávání v řádu n.

694
00:33:07,470 --> 00:33:10,010
A můžeme aplikovat stejný
Logika křížení něco

695
00:33:10,010 --> 00:33:13,170
jak jsem právě udělal do druhého
Algoritmus jsme měli s telefonním seznamu,

696
00:33:13,170 --> 00:33:16,040
kde jsme udělali dvě stránky najednou.

697
00:33:16,040 --> 00:33:20,120
>> Takže 1000 strana telefonní seznam by mohl
nás zavede 500 otočených stran, plus jedna

698
00:33:20,120 --> 00:33:21,910
pokud bychom zdvojnásobit zpět trochu.

699
00:33:21,910 --> 00:33:26,590
Takže pokud telefonní seznam má n stran, ale
děláme dvě stránky najednou,

700
00:33:26,590 --> 00:33:28,900
To je zhruba to, co?

701
00:33:28,900 --> 00:33:33,190
N přes dva, takže to jako n přes dva.

702
00:33:33,190 --> 00:33:38,490
Ale já jsem udělal nárokovat
Před okamžikem, že n přes two--

703
00:33:38,490 --> 00:33:41,060
to je druh stejné jako právě n.

704
00:33:41,060 --> 00:33:44,050
Je to jen konstantní faktor,
počítačoví odborníci by se říci.

705
00:33:44,050 --> 00:33:45,970
Pojďme se zaměřit pouze na
proměnné, really--

706
00:33:45,970 --> 00:33:47,780
největší proměnné v rovnici.

707
00:33:47,780 --> 00:33:52,530
>> Takže lineární vyhledávání, zda udělal jednu
Strana najednou nebo dvě stránky najednou,

708
00:33:52,530 --> 00:33:54,810
je něco v podstatě stejné.

709
00:33:54,810 --> 00:33:56,880
Je to stále v řádu n.

710
00:33:56,880 --> 00:34:01,930
Ale já tvrdil s mým obrázku dříve
že třetí algoritmus nebyl

711
00:34:01,930 --> 00:34:02,480
lineární.

712
00:34:02,480 --> 00:34:03,605
Bylo to není přímka.

713
00:34:03,605 --> 00:34:08,659
Bylo to, že křivka, a
algebraické rovnice nebylo co?

714
00:34:08,659 --> 00:34:11,812
Log n- takže log základnu dva n.

715
00:34:11,812 --> 00:34:14,520
A nemusíme jít do příliš
mnoho detailů na logaritmy dnes,

716
00:34:14,520 --> 00:34:17,394
ale většina počítačoví odborníci nechtěli
i ti, co je základna.

717
00:34:17,394 --> 00:34:20,639
Vzhledem k tomu, že je to všechno jen
konstantní faktory, tak říkajíc,

718
00:34:20,639 --> 00:34:22,659
Jen drobné číselné rozdíly.

719
00:34:22,659 --> 00:34:31,179
A tak by to bylo velmi časté
způsob, zejména formální počítače

720
00:34:31,179 --> 00:34:33,949
Vědci na palubě nebo
programátoři na bílou tabuli

721
00:34:33,949 --> 00:34:36,889
ve skutečnosti tvrdí, které
Algoritmus by se používat

722
00:34:36,889 --> 00:34:39,500
nebo to, co je účinnost
z jejich algoritmus.

723
00:34:39,500 --> 00:34:42,960
>> A to není nutně něco
diskutujete v každém detailu,

724
00:34:42,960 --> 00:34:47,889
ale dobrý programátor je ten,
který má pevnou, formální pozadí.

725
00:34:47,889 --> 00:34:50,120
On je schopen mluvit
vám v tomto druhu cesty

726
00:34:50,120 --> 00:34:53,350
a vlastně dělat
kvalitativní argumenty jako

727
00:34:53,350 --> 00:34:56,870
proč jeden algoritmus nebo
jeden kus softwaru

728
00:34:56,870 --> 00:35:00,165
je lepší než nějakým způsobem do druhého.

729
00:35:00,165 --> 00:35:02,540
Protože ty by jistě
stačí spustit program, jednoho člověka

730
00:35:02,540 --> 00:35:04,980
a spočítat počet sekund
trvá třídit nějaká čísla,

731
00:35:04,980 --> 00:35:06,710
a můžete spustit některé
Program jiné osoby

732
00:35:06,710 --> 00:35:08,418
a počítání
sekund trvá.

733
00:35:08,418 --> 00:35:12,840
Ale to je obecnější způsob,
můžete použít k analýze algoritmů,

734
00:35:12,840 --> 00:35:15,520
chcete-li, jen na
papíru nebo jen slovně.

735
00:35:15,520 --> 00:35:18,430
Aniž by si běží to, aniž
dokonce se snaží vzorové vstupy,

736
00:35:18,430 --> 00:35:20,180
můžete jen rozum přes něj.

737
00:35:20,180 --> 00:35:24,670
A tak s pronájmem vývojáře, nebo pokud
mít ho nebo ji nějak argumentovat pro vás

738
00:35:24,670 --> 00:35:28,460
proč jejich algoritmus, jejich tajemství
omáčka pro vyhledávání miliardy

739
00:35:28,460 --> 00:35:30,580
webových stránek pro vaše
Firma je lepší, tito

740
00:35:30,580 --> 00:35:33,302
jsou druhy argumentů, že
by v ideálním případě být schopen provést.

741
00:35:33,302 --> 00:35:35,010
Nebo alespoň to jsou
druhy věcí

742
00:35:35,010 --> 00:35:40,211
které by přijít v diskuzi, při
alespoň ve velmi formální diskuse.

743
00:35:40,211 --> 00:35:40,710
Dobře.

744
00:35:40,710 --> 00:35:44,400
Takže Ben navrhované něco
volal výběr třídit.

745
00:35:44,400 --> 00:35:48,200
Ale budu navrhovat, že je tu
jiné způsoby, jak to udělat taky.

746
00:35:48,200 --> 00:35:50,400
To, co jsem neměl opravdu rád
o Benově algoritmu

747
00:35:50,400 --> 00:35:54,400
je to, že šel dál, nebo
co mě chodit sem a tam

748
00:35:54,400 --> 00:35:56,930
a sem a tam a sem a tam.

749
00:35:56,930 --> 00:36:04,130
Co když místo toho jsem měl dělat
něco podobného těchto čísel zde

750
00:36:04,130 --> 00:36:08,200
a já jsme byli jen jednat s každým
číslo v pořadí, jak jsem vzhledem k tomu, že?

751
00:36:08,200 --> 00:36:10,780
>> Jinými slovy, je zde
můj seznam čísel.

752
00:36:10,780 --> 00:36:12,944
Čtyři, jedna, tři, dva.

753
00:36:12,944 --> 00:36:14,360
A já budu dělat následující.

754
00:36:14,360 --> 00:36:17,230
Jdu vložit čísla
kam patří spíše

755
00:36:17,230 --> 00:36:18,980
Kromě výběru jim jeden po druhém.

756
00:36:18,980 --> 00:36:20,820
Jinými slovy, tady je číslo čtyři.

757
00:36:20,820 --> 00:36:22,430
>> Tady je můj původní seznam.

758
00:36:22,430 --> 00:36:25,290
A budu zachovávat
v podstatě nový seznam zde.

759
00:36:25,290 --> 00:36:26,710
Tak tohle je starý seznam.

760
00:36:26,710 --> 00:36:28,560
Jedná se o nový seznam.

761
00:36:28,560 --> 00:36:30,220
Vidím, že číslo čtyři první.

762
00:36:30,220 --> 00:36:34,500
Můj nový seznam je zpočátku prázdný,
tak je tomu v případě triviálně

763
00:36:34,500 --> 00:36:36,410
že čtyři je nyní roztříděný seznam.

764
00:36:36,410 --> 00:36:39,560
Já beru jen to číslo jsem dal,
a já ho uvedení ve svém novém seznamu.

765
00:36:39,560 --> 00:36:41,460
>> Je seřazen tento nový seznam?

766
00:36:41,460 --> 00:36:41,990
To jo.

767
00:36:41,990 --> 00:36:45,090
Je to hloupé, protože tam je jen jeden
prvek, ale je to naprosto třídit.

768
00:36:45,090 --> 00:36:46,390
Není nic na svém místě.

769
00:36:46,390 --> 00:36:49,290
Je to mnohem zajímavější, tento algoritmus,
když jsem se přesunout k dalšímu kroku.

770
00:36:49,290 --> 00:36:50,550
>> Teď mám jeden.

771
00:36:50,550 --> 00:36:55,430
Tak jeden, samozřejmě, patří u
začátek nebo konec tohoto nového seznamu?

772
00:36:55,430 --> 00:36:56,360
Začátek.

773
00:36:56,360 --> 00:36:58,530
Takže musím udělat nějakou práci hned.

774
00:36:58,530 --> 00:37:01,410
Bral jsem některé
svobody s mou značku

775
00:37:01,410 --> 00:37:03,120
pouhým kreslení věci
kde chci jim,

776
00:37:03,120 --> 00:37:05,320
ale ve skutečnosti to není
přesný v počítači.

777
00:37:05,320 --> 00:37:08,530
Počítač, jak víme, má
RAM, nebo Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
a to je jeden bajt a
další byte a další byte.

779
00:37:12,411 --> 00:37:14,910
A pokud máte gigabajt
RAM, máte miliardě bajtů

780
00:37:14,910 --> 00:37:16,680
ale jsou fyzicky na jednom místě.

781
00:37:16,680 --> 00:37:19,540
Nemůžete jen přesunout věci kolem
tím, že ho na tabuli

782
00:37:19,540 --> 00:37:20,750
kamkoliv chceš.

783
00:37:20,750 --> 00:37:24,090
Takže pokud můj nový seznam musí
Čtyři místa v paměti,

784
00:37:24,090 --> 00:37:27,480
Bohužel čtyři je
Již na špatném místě.

785
00:37:27,480 --> 00:37:30,410
>> Takže vložit číslo jedna
Nemůžu jen tak kreslit jej sem.

786
00:37:30,410 --> 00:37:31,901
Toto místo v paměti neexistuje.

787
00:37:31,901 --> 00:37:35,150
To by bylo podvádění, a byl jsem
podvádění obrazově po dobu několika minut

788
00:37:35,150 --> 00:37:35,800
zde.

789
00:37:35,800 --> 00:37:40,950
Takže opravdu, když chci dát jeden tady,
Musím se dočasně zkopírovat čtyři

790
00:37:40,950 --> 00:37:43,030
a pak dal ten tam.

791
00:37:43,030 --> 00:37:45,500
>> To je v pořádku, to je v pořádku,
je to technicky možné,

792
00:37:45,500 --> 00:37:48,410
ale uvědomit, že je to práce navíc.

793
00:37:48,410 --> 00:37:50,460
Nechtěl jsem jen dát číslo na svém místě.

794
00:37:50,460 --> 00:37:53,026
Nejdřív jsem musel přesunout
číslo, pak ji na místě,

795
00:37:53,026 --> 00:37:54,650
tak nějak jsem zdvojnásobil svůj objem práce.

796
00:37:54,650 --> 00:37:55,660
Takže mějte na paměti, že.

797
00:37:55,660 --> 00:37:57,120
>> Ale já jsem teď udělal s tímto prvkem.

798
00:37:57,120 --> 00:37:59,056
Teď chci chytit číslo tři.

799
00:37:59,056 --> 00:38:00,430
V případě, samozřejmě, to patří?

800
00:38:00,430 --> 00:38:01,480
Mezi.

801
00:38:01,480 --> 00:38:03,650
Nemůžu podvádět už
a prostě to tam dal,

802
00:38:03,650 --> 00:38:06,770
protože, znovu, této paměti
je ve fyzických místech.

803
00:38:06,770 --> 00:38:10,900
Takže mám zkopírovat čtyři
a dal tři sem.

804
00:38:10,900 --> 00:38:11,550
Není velký problém.

805
00:38:11,550 --> 00:38:14,610
Je to jen jeden krok navíc
again-- cítí velmi levná.

806
00:38:14,610 --> 00:38:16,445
>> Ale teď jsem se přesunout na dva.

807
00:38:16,445 --> 00:38:17,820
Dva, samozřejmě, patří sem.

808
00:38:17,820 --> 00:38:20,990
Nyní můžete začít sledovat, jak
Práce může nahromadit.

809
00:38:20,990 --> 00:38:23,520
A teď, co mám dělat?

810
00:38:23,520 --> 00:38:28,570
Jo, mám přesunout čtyři,
pak musím zkopírovat tři,

811
00:38:28,570 --> 00:38:31,200
a teď můžu vložit dva.

812
00:38:31,200 --> 00:38:34,460
A úlovek s tímto
algoritmus, je dost zajímavé,

813
00:38:34,460 --> 00:38:41,050
je, že předpokládám, že máme více extrémní
případ, kdy je to řekněme, osm, sedm,

814
00:38:41,050 --> 00:38:45,150
šest, pět, čtyři, tři, dva, jedna.

815
00:38:45,150 --> 00:38:49,450
To je, v mnoha kontextech,
nejhorší možný scénář,

816
00:38:49,450 --> 00:38:51,570
protože zatracenou věc
je doslova pozpátku.

817
00:38:51,570 --> 00:38:53,670
>> To není opravdu
ovlivní Benův algoritmus,

818
00:38:53,670 --> 00:38:55,940
protože v Benově výběru
sort že to bude držet

819
00:38:55,940 --> 00:38:58,359
tam a zpět přes seznam.

820
00:38:58,359 --> 00:39:01,150
A protože byl stále hledá
po celou zbývající seznamu

821
00:39:01,150 --> 00:39:02,858
to nevadí
kde jsou prvky.

822
00:39:02,858 --> 00:39:05,630
Ale v tomto případě se svým vkládání
approach-- zkusme to.

823
00:39:05,630 --> 00:39:08,616
>> Tak jeden, dva, tři, čtyři,
pět, šest, sedm, osm.

824
00:39:08,616 --> 00:39:11,630
Jedna dva tři čtyři,
pět, šest, sedm, osm.

825
00:39:11,630 --> 00:39:14,320
Chystám se vzít osm,
a kde mám dát?

826
00:39:14,320 --> 00:39:17,260
No, na začátku mého seznamu
protože tento nový seznam je seřazen.

827
00:39:17,260 --> 00:39:18,760
A já ji přejíždějí ven.

828
00:39:18,760 --> 00:39:20,551
>> Kam mám dát sedm?

829
00:39:20,551 --> 00:39:21,050
Sakra.

830
00:39:21,050 --> 00:39:23,174
Je třeba jít tam, tak
Musím udělat nějaké kopírování.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
A teď sedm chodí sem.

833
00:39:28,480 --> 00:39:29,860
Teď jsem se přesunout na šest.

834
00:39:29,860 --> 00:39:30,980
Teď je to ještě víc práce.

835
00:39:30,980 --> 00:39:32,570
>> Osm musí jít sem.

836
00:39:32,570 --> 00:39:33,920
Sedm musí jít sem.

837
00:39:33,920 --> 00:39:35,450
Nyní je šest může jít sem.

838
00:39:35,450 --> 00:39:37,950
Teď jsem chytit pět.

839
00:39:37,950 --> 00:39:40,560
Nyní osm musí jít
tady, sedm musí jít sem,

840
00:39:40,560 --> 00:39:43,650
šest musí jít sem, a
nyní pět a opakovat.

841
00:39:43,650 --> 00:39:46,610
A jsem docela hodně
pohybující se to neustále.

842
00:39:46,610 --> 00:39:52,950
>> Takže na konci, to algorithm-- zmíníme
říkat vložení sort-- vlastně

843
00:39:52,950 --> 00:39:55,020
Má hodně práce, taky.

844
00:39:55,020 --> 00:39:56,970
Je to prostě jiný
druh práce, než Bena.

845
00:39:56,970 --> 00:40:00,090
Benův práce měla mě děje
sem a tam po celou dobu,

846
00:40:00,090 --> 00:40:03,510
zvolení příští nejmenší
znovu a znovu element.

847
00:40:03,510 --> 00:40:06,660
Tak to bylo to velmi vizuální druh práce.

848
00:40:06,660 --> 00:40:10,600
>> Tento jiný algoritmus, který je ještě
correct-- to dostane práci done--

849
00:40:10,600 --> 00:40:12,800
Jen změní množství práce.

850
00:40:12,800 --> 00:40:15,420
Vypadá to, že zpočátku budete
úsporu, protože jsi zrovna

851
00:40:15,420 --> 00:40:19,190
jednání s každým prvkem
vepředu, aniž by šel all

852
00:40:19,190 --> 00:40:20,930
cesta přes seznamu jako Ben byl.

853
00:40:20,930 --> 00:40:25,300
Ale problém je, a to zejména v těch
bláznivé případy, kdy je to všechno obráceně,

854
00:40:25,300 --> 00:40:27,830
jsi jen trochu
odkládá těžkou práci

855
00:40:27,830 --> 00:40:30,360
dokud nebudete mít na opravu chyby.

856
00:40:30,360 --> 00:40:33,919
>> A tak pokud můžete si to představit
osm a sedm a šest a pět

857
00:40:33,919 --> 00:40:36,710
a později čtyři a tři a dva
pohybující se jejich cestu přes seznamu

858
00:40:36,710 --> 00:40:39,060
jsme právě změněn
druh práce děláme.

859
00:40:39,060 --> 00:40:42,340
Namísto toho, jak to dělá u
počátek mé iteraci

860
00:40:42,340 --> 00:40:45,250
Dělám jen to u
Konec každé iteraci.

861
00:40:45,250 --> 00:40:50,550
Tak to dopadá, že tento algoritmus,
Také obecně nazývané insertion sort,

862
00:40:50,550 --> 00:40:52,190
je také na objednávku n čtvercový.

863
00:40:52,190 --> 00:40:56,480
Je to vlastně o nic lepší,
o nic lepší vůbec.

864
00:40:56,480 --> 00:41:00,810
>> Nicméně, tam je třetina přístup
Byl bych nás povzbudit, aby zvážila,

865
00:41:00,810 --> 00:41:02,970
který je to.

866
00:41:02,970 --> 00:41:07,850
Takže předpokládám, že můj seznam, pro jednoduchost
znovu, je čtyři, jedna, tři,

867
00:41:07,850 --> 00:41:11,080
two-- jen čtyři čísla.

868
00:41:11,080 --> 00:41:13,300
Ben měl dobrou intuici,
dobrý člověk intuice

869
00:41:13,300 --> 00:41:16,340
Před tím, kterou pevné celý
Seznam eventually-- insertion sort.

870
00:41:16,340 --> 00:41:18,020
nám vyprosil jsem dál.

871
00:41:18,020 --> 00:41:22,530
Ale pojďme zvážit
Nejjednodušší způsob, jak opravit tento seznam.

872
00:41:22,530 --> 00:41:24,110
>> Tento seznam není seřazena.

873
00:41:24,110 --> 00:41:26,130
Proč?

874
00:41:26,130 --> 00:41:31,920
V angličtině, vysvětlit, proč
to není ve skutečnosti třídit.

875
00:41:31,920 --> 00:41:33,400
Co to znamená nebýt řazeny?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: To není sekvenční.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Malan: Není sekvenční.

878
00:41:34,990 --> 00:41:35,822
Dejte mi příklad.

879
00:41:35,822 --> 00:41:37,180
>> STUDENT: Dejte je v pořádku.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Malan: OK.

881
00:41:37,440 --> 00:41:38,790
Dej mi víc konkrétní příklad.

882
00:41:38,790 --> 00:41:39,832
>> STUDENT: vzestupném pořadí.

883
00:41:39,832 --> 00:41:41,206
DAVID Malan: Není vzestupně.

884
00:41:41,206 --> 00:41:42,100
Být přesnější.

885
00:41:42,100 --> 00:41:45,190
Nevím, co myslíš tím vzestupně.

886
00:41:45,190 --> 00:41:47,150
Co je špatně?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: Nejmenší z
Čísla není v prvním prostoru.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Malan: Nejmenší číslo je
není v prvním prostoru.

889
00:41:51,140 --> 00:41:52,120
Být konkrétnější.

890
00:41:52,120 --> 00:41:55,000
Začínám pochopit.

891
00:41:55,000 --> 00:41:59,470
Počítáme, ale
co je mimo provoz tady?

892
00:41:59,470 --> 00:42:00,707
>> STUDENT: číselné posloupnosti.

893
00:42:00,707 --> 00:42:02,040
DAVID Malan: číselné posloupnosti.

894
00:42:02,040 --> 00:42:04,248
druh věcí každého z chovu
to here-- velmi vysokou úroveň.

895
00:42:04,248 --> 00:42:07,450
Jen mi doslova říct, co je
špatně jako pět let staré síle.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: Plus jeden.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Malan: Co je to?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: Plus jeden.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Malan: Co tím myslíš plus jedna?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Dej mi jiný pět-letý.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Co se děje, mami?

904
00:42:18,330 --> 00:42:19,940
Co se děje, tati?

905
00:42:19,940 --> 00:42:22,808
Co tím myslíš, to není řazeny?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: To není to správné místo.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Malan: Co je
není na správném místě?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Čtyři.

909
00:42:26,174 --> 00:42:27,090
DAVID Malan: OK, dobře.

910
00:42:27,090 --> 00:42:29,110
Takže čtyři není tam, kde by měla být.

911
00:42:29,110 --> 00:42:30,590
Zejména, je to pravda?

912
00:42:30,590 --> 00:42:33,000
Čtyři a jeden, první
dvě čísla Aha.

913
00:42:33,000 --> 00:42:34,930
Je to správně?

914
00:42:34,930 --> 00:42:36,427
Ne, oni jsou mimo provoz, ne?

915
00:42:36,427 --> 00:42:38,135
Ve skutečnosti, že teď
o počítači, taky.

916
00:42:38,135 --> 00:42:40,824
Může se pouze na možná jeden,
možná dvě věci once--

917
00:42:40,824 --> 00:42:43,240
a vlastně jen jedna věc
v době, ale může alespoň

918
00:42:43,240 --> 00:42:45,790
podívat se na jednu věc, pak
Další věc, kterou hned vedle něj.

919
00:42:45,790 --> 00:42:47,380
>> Takže jsou tyto v pořádku?

920
00:42:47,380 --> 00:42:48,032
Samozřejmě, že ne.

921
00:42:48,032 --> 00:42:48,740
Tak víte co?

922
00:42:48,740 --> 00:42:51,020
Proč ne vezmeme dítě
Kroky upevňovací tento problém

923
00:42:51,020 --> 00:42:53,410
namísto toho, aby tyto fantazie
algoritmy jako Ben, kde

924
00:42:53,410 --> 00:42:56,440
Je to vlastně trochu upevnění ji
smyčky v seznamu

925
00:42:56,440 --> 00:42:59,670
místo toho dělat to, co jsem udělal, kde
I tak nějak připevnil ji, jak jsme jít?

926
00:42:59,670 --> 00:43:03,650
Řekněme doslova rozebrat
Pojem order-- číselném pořadí,

927
00:43:03,650 --> 00:43:06,990
říkat cokoliv want--
Do těchto párová srovnání.

928
00:43:06,990 --> 00:43:07,590
>> Čtyři a.

929
00:43:07,590 --> 00:43:09,970
Je to správné pořadí?

930
00:43:09,970 --> 00:43:11,310
Takže pojďme napravit.

931
00:43:11,310 --> 00:43:14,700
Jeden a čtyři, a poté
budeme jen zkopírovat to.

932
00:43:14,700 --> 00:43:15,560
Dobře, dobře.

933
00:43:15,560 --> 00:43:17,022
Opravil jsem jeden a čtyři.

934
00:43:17,022 --> 00:43:18,320
Tři a dvě?

935
00:43:18,320 --> 00:43:18,820
Ne.

936
00:43:18,820 --> 00:43:21,690
Nechť moje slova odpovídala prsty.

937
00:43:21,690 --> 00:43:23,695
Čtyři a tři?

938
00:43:23,695 --> 00:43:27,930
>> Není to v pořádku, takže jdu
dělat jeden, tři, čtyři, dva.

939
00:43:27,930 --> 00:43:28,680
OK dobře.

940
00:43:28,680 --> 00:43:32,310
Nyní čtyři a dvě?

941
00:43:32,310 --> 00:43:33,370
Musíme to opravit taky.

942
00:43:33,370 --> 00:43:36,700
Tak jeden, tři, dva, čtyři.

943
00:43:36,700 --> 00:43:39,820
Takže je to řazeny?

944
00:43:39,820 --> 00:43:43,170
Ne, ale je to blíž do tříděného?

945
00:43:43,170 --> 00:43:48,930
>> Je to proto, že jsme opravil toto
chyba, jsme opravili tuto chybu,

946
00:43:48,930 --> 00:43:50,370
a my pevně tuto chybu.

947
00:43:50,370 --> 00:43:52,420
Takže jsme opravili tři chyby pravděpodobně.

948
00:43:52,420 --> 00:43:58,100
Stále není opravdu vypadají tříděny, ale
je objektivně blíže do tříděného

949
00:43:58,100 --> 00:44:00,080
protože jsme pevně některé z těchto chyb.

950
00:44:00,080 --> 00:44:02,047
>> A teď, co mám dělat dál?

951
00:44:02,047 --> 00:44:03,630
Tak nějak jsem došel na konec seznamu.

952
00:44:03,630 --> 00:44:05,680
Zdálo se, že jsem fixní
všechny chyby, ale ne.

953
00:44:05,680 --> 00:44:08,510
Vzhledem k tomu v tomto případě, některé čísla
mohl bublal blíž

954
00:44:08,510 --> 00:44:10,410
do jiných čísel, která
jsou stále mimo provoz.

955
00:44:10,410 --> 00:44:12,951
Takže pojďme udělat to znovu, a budu
Jen to v místě tentokrát.

956
00:44:12,951 --> 00:44:14,170
Jeden a tři?

957
00:44:14,170 --> 00:44:14,720
To je v pořádku.

958
00:44:14,720 --> 00:44:16,070
Tři a dvě?

959
00:44:16,070 --> 00:44:17,560
Samozřejmě že ne, tak se pojďme změnit.

960
00:44:17,560 --> 00:44:19,160
Tak dva, tři.

961
00:44:19,160 --> 00:44:21,340
Tři a čtyři?

962
00:44:21,340 --> 00:44:24,370
A teď pojďme být jen
Zvláště tady pedantský.

963
00:44:24,370 --> 00:44:26,350
Je to řazeny?

964
00:44:26,350 --> 00:44:29,280
Vy lidé vím, že to třídit.

965
00:44:29,280 --> 00:44:30,400
>> Měl bych zkusit znovu.

966
00:44:30,400 --> 00:44:31,900
Takže Olivia navrhuje I zkuste to znovu.

967
00:44:31,900 --> 00:44:32,530
Proč?

968
00:44:32,530 --> 00:44:35,810
Protože počítač nemá
luxus našich lidských očí

969
00:44:35,810 --> 00:44:38,080
pouhého podíval back-- OK, jsem udělal.

970
00:44:38,080 --> 00:44:41,610
Jak se počítač určí
že seznam je nyní řazeny?

971
00:44:41,610 --> 00:44:44,590
Mechanicky.

972
00:44:44,590 --> 00:44:47,650
>> Měl bych projít
ještě jednou, a to pouze v případě, I

973
00:44:47,650 --> 00:44:51,190
nedělají / najít žádnou chybu mohu
pak uzavře jako počítač, jo,

974
00:44:51,190 --> 00:44:51,980
jsme dobří jít.

975
00:44:51,980 --> 00:44:54,850
Aby jedna a dvě, dvě a
tři, tři a čtyři.

976
00:44:54,850 --> 00:44:58,030
Teď můžu konečně říct, že je
tříděny, protože jsem nedělal žádné změny.

977
00:44:58,030 --> 00:45:01,940
Teď to bude chyba a jen
Pokud bych hloupý, počítač,

978
00:45:01,940 --> 00:45:05,640
zeptal se ty stejné otázky znovu
očekával různé odpovědi.

979
00:45:05,640 --> 00:45:07,110
By se nemělo stát.

980
00:45:07,110 --> 00:45:08,600
>> A tak teď je seřazen seznam.

981
00:45:08,600 --> 00:45:12,630
Bohužel, doba běhu
Tento algoritmus je také N druhou.

982
00:45:12,630 --> 00:45:13,130
Proč?

983
00:45:13,130 --> 00:45:19,520
Protože máte n čísel, a ve
nejhorším případě budete muset přesunout n čísel

984
00:45:19,520 --> 00:45:23,637
n časy, protože musíte jít dál
zpět zkontrolovat a případně opravit

985
00:45:23,637 --> 00:45:24,220
tato čísla.

986
00:45:24,220 --> 00:45:26,280
A můžeme udělat víc
formální analýza, taky.

987
00:45:26,280 --> 00:45:29,530
>> Tak to je vše, říci, že jsme si vzít
tři různé přístupy, jeden

988
00:45:29,530 --> 00:45:32,210
z nich okamžitě intuitivní
off netopýra z Ben

989
00:45:32,210 --> 00:45:35,170
mé navrhované vložení
řadit k tomuhle

990
00:45:35,170 --> 00:45:38,540
kde jste druh ztrácet ze zřetele
les pro stromy zpočátku.

991
00:45:38,540 --> 00:45:41,760
Ale pak, když jdete o krok zpět,
voila, máme fixní třídění představu.

992
00:45:41,760 --> 00:45:43,824
Takže tohle je, troufám tvrdit,
nižší úroveň snad

993
00:45:43,824 --> 00:45:45,740
než někteří z těch, ostatní
algoritmy, ale pojďme

994
00:45:45,740 --> 00:45:48,550
uvidíme, jestli nemůžeme představit
Tyto prostřednictvím tohoto.

995
00:45:48,550 --> 00:45:51,450
>> Takže to je nějaký pěkný
software, který někdo

996
00:45:51,450 --> 00:45:56,110
napsal pomocí barevné pruhy, aby to
dělat následující pro nás.

997
00:45:56,110 --> 00:45:57,736
Každý z těchto tyčí představuje číslo.

998
00:45:57,736 --> 00:46:00,026
Vyšší je sloupec, tím větší
číslo, menší bar,

999
00:46:00,026 --> 00:46:00,990
čím menší je počet.

1000
00:46:00,990 --> 00:46:05,880
Takže v ideálním případě chceme krásný pyramidu
kde začíná malý a dostane velký,

1001
00:46:05,880 --> 00:46:08,330
a to by znamenalo, že
Tyto tyče jsou řazeny.

1002
00:46:08,330 --> 00:46:11,200
Takže já jdu dopředu a zvolit,
Například, Benův algoritmus

1003
00:46:11,200 --> 00:46:13,990
first-- výběr třídit.

1004
00:46:13,990 --> 00:46:16,220
>> A všimněte si, co dělá.

1005
00:46:16,220 --> 00:46:18,670
Způsob, jakým jste se rozhodli
vizualizovat tento algoritmus

1006
00:46:18,670 --> 00:46:22,090
je, že stejně jako já
procházel mém seznamu,

1007
00:46:22,090 --> 00:46:24,710
Tento program je chůze
prostřednictvím svého seznamu čísel,

1008
00:46:24,710 --> 00:46:28,160
zvýraznění v růžové každého
Číslo že to dívá.

1009
00:46:28,160 --> 00:46:32,360
A co se stane teď?

1010
00:46:32,360 --> 00:46:35,154
>> Nejmenší číslo, které
I nebo Ben našel náhle

1011
00:46:35,154 --> 00:46:36,820
se přesune na začátek seznamu.

1012
00:46:36,820 --> 00:46:40,037
A všimněte si udělali vypudit
číslo, které tam byl,

1013
00:46:40,037 --> 00:46:41,120
a to je naprosto v pořádku.

1014
00:46:41,120 --> 00:46:42,600
Nedostal jsem se do této úrovni detailu.

1015
00:46:42,600 --> 00:46:44,308
Ale musíme dát
toto číslo někde,

1016
00:46:44,308 --> 00:46:47,775
tak jsme ho přestěhovali do
otevřené místo, které bylo vytvořeno.

1017
00:46:47,775 --> 00:46:49,900
Tak jdu k urychlení tohoto
up, protože jinak

1018
00:46:49,900 --> 00:46:51,871
se stává velmi únavné rychle.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animace speed-- tam jdeme.

1021
00:46:58,600 --> 00:47:01,850
Takže teď Stejný princip
Byl jsem uplatňují, ale vy

1022
00:47:01,850 --> 00:47:06,540
může začít cítit algoritmus, pokud se
vůle, nebo to vidět trochu jasněji.

1023
00:47:06,540 --> 00:47:13,190
A tento algoritmus má za následek
výběru dalšího nejmenší prvek,

1024
00:47:13,190 --> 00:47:16,422
takže budete začít
vidět to rozjet na levé straně.

1025
00:47:16,422 --> 00:47:19,130
A na každé iteraci, jak jsem
navrhováno, to dělá trochu méně práce.

1026
00:47:19,130 --> 00:47:21,921
Nemusí jít celou cestu
zpět na levý konec seznamu,

1027
00:47:21,921 --> 00:47:23,900
protože již
zná ty jsou řazeny.

1028
00:47:23,900 --> 00:47:28,129
Takže to trochu pocit, jako by to
zrychluje, i když každý krok je

1029
00:47:28,129 --> 00:47:29,420
přičemž stejné množství času.

1030
00:47:29,420 --> 00:47:31,600
Je tu jen méně kroků zbývající.

1031
00:47:31,600 --> 00:47:35,240
A teď se můžete trochu cítit
Algoritmus vyčištění její konec,

1032
00:47:35,240 --> 00:47:37,040
a opravdu teď je to třídit.

1033
00:47:37,040 --> 00:47:41,620
>> Takže insertion sort je vše hotovo.

1034
00:47:41,620 --> 00:47:43,600
Musím znovu náhodně pole.

1035
00:47:43,600 --> 00:47:45,940
A všimněte si mohu jen
udržovat randomizing to,

1036
00:47:45,940 --> 00:47:50,630
a dostaneme aproximaci
stejný přístup, vložení sort.

1037
00:47:50,630 --> 00:47:55,050
Nech mě to zpomalit až sem.

1038
00:47:55,050 --> 00:47:56,915
Začněme že v průběhu.

1039
00:47:56,915 --> 00:47:57,414
Stop.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Pojďme přeskočit čtyři.

1042
00:48:02,410 --> 00:48:03,200
Tam jedeme.

1043
00:48:03,200 --> 00:48:04,190
Náhodně oni pole.

1044
00:48:04,190 --> 00:48:05,555
A tady jsme go-- insertion sort.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Hrát.

1047
00:48:12,800 --> 00:48:17,280
Všimněte si, že to zacházení s jednotlivým
prvek narazí hned,

1048
00:48:17,280 --> 00:48:20,282
ale v případě, že patří do
špatné oznámení místa

1049
00:48:20,282 --> 00:48:21,740
všechny práce, která má dít.

1050
00:48:21,740 --> 00:48:24,700
Musíme se držet přesouvá více
a další prvky, aby se vytvořil prostor

1051
00:48:24,700 --> 00:48:27,340
Pro jednoho chceme zavést.

1052
00:48:27,340 --> 00:48:30,740
>> Takže jsme se zaměřením na
levý konec jediného seznamu.

1053
00:48:30,740 --> 00:48:34,460
Všimněte si, jsme ani my vypadal at--
ještě zvýrazněny v růžové cokoliv

1054
00:48:34,460 --> 00:48:35,610
doprava.

1055
00:48:35,610 --> 00:48:38,180
Právě jsme se zabývají
problémy, jak jsme jít,

1056
00:48:38,180 --> 00:48:40,430
ale my jsme vytvořit hodně
pracovat pro sebe pořád.

1057
00:48:40,430 --> 00:48:44,410
A tak pokud bychom toto urychlit
Nyní jít do dokončení,

1058
00:48:44,410 --> 00:48:46,210
má jiný pocit na to opravdu.

1059
00:48:46,210 --> 00:48:50,150
Je to jen se zaměřením na levém konci, ale
dělá trochu více práce jako needed--

1060
00:48:50,150 --> 00:48:53,230
druh vyhlazování věcí
přes, napravuješ,

1061
00:48:53,230 --> 00:48:58,350
ale nakonec zabývající se
každý prvek jeden po druhém

1062
00:48:58,350 --> 00:49:07,740
až se dostaneme do dobře the--, my
Všichni víme, jak to skončí,

1063
00:49:07,740 --> 00:49:09,700
takže je to trochu nezaujatý možná.

1064
00:49:09,700 --> 00:49:12,830
>> Ale Seznam v end--
spoiler-- se bude třídit.

1065
00:49:12,830 --> 00:49:15,300
Takže pojďme se podívat na jeden poslední.

1066
00:49:15,300 --> 00:49:16,840
Nemůžeme jen tak přeskočit teď.

1067
00:49:16,840 --> 00:49:18,000
Už tam skoro jsme.

1068
00:49:18,000 --> 00:49:19,980
Dva jít, kdo jít.

1069
00:49:19,980 --> 00:49:22,680
A voila.

1070
00:49:22,680 --> 00:49:23,450
Vynikající.

1071
00:49:23,450 --> 00:49:27,220
>> Takže teď pojďme udělat jednu poslední,
re-randomizing s bublinou druhu.

1072
00:49:27,220 --> 00:49:31,690
A všimněte si tady, zvlášť když jsem ho zpomalit
dolů, to se udržet snášet projít.

1073
00:49:31,690 --> 00:49:36,830
Nevšimnout to prostě dělá po dvojicích
comparisons-- druh místních řešení.

1074
00:49:36,830 --> 00:49:39,050
Ale jakmile se dostaneme do
konec seznamu v růžové,

1075
00:49:39,050 --> 00:49:40,690
co se muselo stát znovu?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Jo, to bude muset
začít znovu, protože to jen

1078
00:49:46,830 --> 00:49:49,870
Pevné párové chyby.

1079
00:49:49,870 --> 00:49:53,120
A to by mohl odhalit ještě další.

1080
00:49:53,120 --> 00:49:58,950
A tak když se toto urychlit, budete
vidět, že, stejně jako název napovídá,

1081
00:49:58,950 --> 00:50:01,870
menší elements-- nebo spíše,
větší elements-- začínají

1082
00:50:01,870 --> 00:50:03,740
bublat až na vrchol, chcete-li.

1083
00:50:03,740 --> 00:50:07,380
A menší prvky jsou
začíná bublat dolů doleva.

1084
00:50:07,380 --> 00:50:10,780
A vskutku, to je druh
Vizuální efekt stejně.

1085
00:50:10,780 --> 00:50:17,150
A tak to bude skončit dokončovací práce
ve velmi podobným způsobem, taky.

1086
00:50:17,150 --> 00:50:19,160
>> Nemáme k bydlení
na tento konkrétní jeden.

1087
00:50:19,160 --> 00:50:21,010
Dovol mi otevřít to teď taky.

1088
00:50:21,010 --> 00:50:24,040
Je tu několik dalších třídící algoritmy
ve světě, málo z nich

1089
00:50:24,040 --> 00:50:25,580
Zde jsou zachyceny.

1090
00:50:25,580 --> 00:50:29,960
A to zejména pro studenty, kteří nejsou
nutně vizuální nebo matematické,

1091
00:50:29,960 --> 00:50:31,930
jak tomu bylo dříve, můžeme
Také to audially

1092
00:50:31,930 --> 00:50:34,210
pokud budeme spojovat zvuk s tím.

1093
00:50:34,210 --> 00:50:36,990
A jen tak pro zábavu, tady je
Několik různých algoritmů,

1094
00:50:36,990 --> 00:50:40,950
a jeden z nich, zejména jste
bude všimnout, se nazývá "merge sort."

1095
00:50:40,950 --> 00:50:43,250
>> Je to vlastně zásadně
lepší algoritmus,

1096
00:50:43,250 --> 00:50:45,860
tak, aby sloučit druh, jedním z
ty se chystáte vidět,

1097
00:50:45,860 --> 00:50:49,170
Není řád n druhou.

1098
00:50:49,170 --> 00:50:57,280
Je to v řádu n-krát logaritmu
n, což je ve skutečnosti menší, a tudíž

1099
00:50:57,280 --> 00:50:58,940
rychleji než ostatní tři.

1100
00:50:58,940 --> 00:51:00,670
A je tu další pár
ty hloupé, že uvidíme.

1101
00:51:00,670 --> 00:51:01,933
>> Tak jdeme na to s nějakým zvukem.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
To je insertion sort, takže opět
je to jen do činění s prvky

1104
00:51:10,490 --> 00:51:13,420
jak přijdou.

1105
00:51:13,420 --> 00:51:17,180
To je bublina třídit, takže je to
s ohledem jim párů najednou.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
A opět největšími elementy
vyvěrá až na vrchol.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Další na řadě výběr třídit.

1110
00:51:41,710 --> 00:51:45,420
To je Benův algoritmus, kde
Znovu on výběrem iterativně

1111
00:51:45,420 --> 00:51:46,843
druhý nejmenší prvek.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
A opět, nyní si můžete skutečně slyšet, že
to urychlit, ale jen do té míry,

1114
00:51:53,900 --> 00:51:58,230
jak to dělá méně a méně
práce na každém opakování.

1115
00:51:58,230 --> 00:52:04,170
To je rychlejší jedno, merge sort,
který je třídění shluky čísel

1116
00:52:04,170 --> 00:52:05,971
dohromady a pak je kombinovat.

1117
00:52:05,971 --> 00:52:07,720
Takže look-- levý
polovina je již řazeno.

1118
00:52:07,720 --> 00:52:14,165
>> Teď je to třídění pravou polovinu, a
Nyní to bude zkombinovat do jednoho.

1119
00:52:14,165 --> 00:52:19,160
To je něco, co nazývá "Gnome sort."

1120
00:52:19,160 --> 00:52:23,460
A můžete trochu vidět, že
to tam a zpět,

1121
00:52:23,460 --> 00:52:27,950
kterým se práce trochu tady a
že před tím, než pokračuje do nové práce.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
A to je vše.

1124
00:52:33,692 --> 00:52:36,400
Je tu jiný druh, který je
opravdu jen pro akademické účely,

1125
00:52:36,400 --> 00:52:40,980
volal "hloupý druh", který bere
vaše data, třídí to náhodně,

1126
00:52:40,980 --> 00:52:43,350
a zkontroluje, je-li seřazeny.

1127
00:52:43,350 --> 00:52:47,880
A pokud tomu tak není, to re-třídí jej
náhodně, zkontroluje, zda je to tříděny,

1128
00:52:47,880 --> 00:52:49,440
a pokud ne, opakuje.

1129
00:52:49,440 --> 00:52:52,660
A teoreticky, pravděpodobnostně
Tím se dokončí,

1130
00:52:52,660 --> 00:52:54,140
ale po docela dost času.

1131
00:52:54,140 --> 00:52:56,930
Není to nejvíce
účinné algoritmů.

1132
00:52:56,930 --> 00:53:02,550
Takže jakékoliv otázky týkající se těch,
Konkrétní algoritmy nebo cokoliv

1133
00:53:02,550 --> 00:53:04,720
vztahující se tam taky?

1134
00:53:04,720 --> 00:53:09,430
>> Dobře, pojďme teď šprýmaři odděleně co všechno
Tyto linky jsou, že jsem byl kreslení

1135
00:53:09,430 --> 00:53:15,090
a to, co jsem za předpokladu, že počítač
může dělat pod kapotou.

1136
00:53:15,090 --> 00:53:18,650
Řekl bych, že všechny z těchto čísel
Pořád drawing-- oni potřebují dostat

1137
00:53:18,650 --> 00:53:21,330
uložené někde v paměti.

1138
00:53:21,330 --> 00:53:24,130
Budeme se zbavit toho chlapa teď taky.

1139
00:53:24,130 --> 00:53:30,110
>> Takže kus v paměti
computer-- takže RAM DIMM je

1140
00:53:30,110 --> 00:53:35,480
to, co jsme hledali včera, dual
inline memory module-- vypadá takto.

1141
00:53:35,480 --> 00:53:39,370
A každý z těchto malých černých čipů
je nějaký počet bajtů, typicky.

1142
00:53:39,370 --> 00:53:44,380
A pak zlaté kolíky jsou stejně jako
dráty, které ji připojit k počítači,

1143
00:53:44,380 --> 00:53:47,521
a zelený křemík deska je prostě
co drží všechno pohromadě.

1144
00:53:47,521 --> 00:53:48,770
Takže co to vlastně znamená?

1145
00:53:48,770 --> 00:53:53,180
Kdybych druh nakreslit stejný obrázek,
Předpokládejme pro jednoduchost

1146
00:53:53,180 --> 00:53:55,280
že tento DIMM, dual
inline paměťový modul,

1147
00:53:55,280 --> 00:54:00,530
Je jedno GB paměti RAM, jeden gigabajt
paměť, která je, kolik bytů celkem?

1148
00:54:00,530 --> 00:54:02,100
Jeden gigabajt je to, kolik bytů?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Víc než to.

1151
00:54:06,030 --> 00:54:09,960
1124 je kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega je milion.

1153
00:54:11,730 --> 00:54:14,570
Giga je miliarda.

1154
00:54:14,570 --> 00:54:15,070
>> Lžu?

1155
00:54:15,070 --> 00:54:16,670
Můžeme dokonce číst etiketu?

1156
00:54:16,670 --> 00:54:19,920
To je vlastně 128
GB, takže je to víc.

1157
00:54:19,920 --> 00:54:22,130
Ale budeme předstírat, že toto
Je jen jeden gigabajt.

1158
00:54:22,130 --> 00:54:25,640
Takže to znamená, že je o miliardu
bajtů paměti k dispozici pro mě

1159
00:54:25,640 --> 00:54:29,770
nebo 8 miliard bitů, ale jdeme
mluvit, pokud jde o bytech nyní,

1160
00:54:29,770 --> 00:54:30,750
kupředu.

1161
00:54:30,750 --> 00:54:36,330
>> Takže to, co to znamená, že je to
jeden byte, je to další bajt,

1162
00:54:36,330 --> 00:54:38,680
Jedná se o další bajt,
a kdybychom opravdu chtěli

1163
00:54:38,680 --> 00:54:43,280
být konkrétní budeme muset
čerpat miliardu malé čtverce.

1164
00:54:43,280 --> 00:54:44,320
Ale co to znamená?

1165
00:54:44,320 --> 00:54:46,420
No, dovolte mi zoom
na tomto obrázku.

1166
00:54:46,420 --> 00:54:50,900
Pokud mám něco, co vypadá
jako je to teď, to je čtyři bajty.

1167
00:54:50,900 --> 00:54:53,710
>> A tak jsem mohl dát čtyři čísla zde.

1168
00:54:53,710 --> 00:54:54,990
Jedna dva tři čtyři.

1169
00:54:54,990 --> 00:55:00,170
Nebo bych mohl dát čtyři písmena nebo symboly.

1170
00:55:00,170 --> 00:55:02,620
"Ahoj!" může jít přímo tam,
protože každý z dopisů,

1171
00:55:02,620 --> 00:55:04,370
jsme diskutovali dříve,
by mohl být zastoupen

1172
00:55:04,370 --> 00:55:06,650
s osmi bitů nebo ASCII nebo byte.

1173
00:55:06,650 --> 00:55:09,370
Takže jinými slovy, můžete
dát 8 miliard věci uvnitř

1174
00:55:09,370 --> 00:55:11,137
tato jedna hůl paměti.

1175
00:55:11,137 --> 00:55:14,345
A teď co to znamená dát věci zpět
se zády v paměti takhle?

1176
00:55:14,345 --> 00:55:17,330
To je to, co programátor
by se nazvat "pole."

1177
00:55:17,330 --> 00:55:21,250
V počítačovém programu, si nemyslím, že
o hardwarem, samy o sobě.

1178
00:55:21,250 --> 00:55:24,427
Ty prostě myslet na sebe jako vlastnění
Přístup k celkově o miliardě bajtů

1179
00:55:24,427 --> 00:55:26,010
a můžete co chcete s ním.

1180
00:55:26,010 --> 00:55:27,880
Ale pro pohodlí
je obecně užitečné

1181
00:55:27,880 --> 00:55:31,202
aby se vaše paměť právo
vedle sebe, jako to.

1182
00:55:31,202 --> 00:55:33,660
Takže když jsem se přiblížit na tohle--
protože my rozhodně nebudeme

1183
00:55:33,660 --> 00:55:39,310
čerpat miliardy trochu squares--
Dejme tomu, že tato deska představuje

1184
00:55:39,310 --> 00:55:40,610
že hůl paměti hned.

1185
00:55:40,610 --> 00:55:43,800
A já budu jen čerpat tolik jako my
Značka skončí mi dává sem.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Takže teď máme hůl
paměti na desce

1188
00:55:52,300 --> 00:55:56,400
který má jeden, dva, tři, čtyři, pět,
šest, jeden, dva, tři, čtyři, pět, šest,

1189
00:55:56,400 --> 00:56:01,130
sedmé takže 42 bajtů
paměť na celkovou obrazovky.

1190
00:56:01,130 --> 00:56:01,630
Děkuji.

1191
00:56:01,630 --> 00:56:02,838
Ano, udělal můj aritmetický pravdu.

1192
00:56:02,838 --> 00:56:05,120
tady tak 42 bajtů paměti.

1193
00:56:05,120 --> 00:56:06,660
Takže co to vlastně znamená?

1194
00:56:06,660 --> 00:56:09,830
No, počítačový programátor
by ve skutečnosti obecně

1195
00:56:09,830 --> 00:56:12,450
myslíte o této paměti jako adresovat.

1196
00:56:12,450 --> 00:56:16,630
Jinými slovy, každý z nich
místa v paměti, v hardwaru,

1197
00:56:16,630 --> 00:56:18,030
má jedinečnou adresu.

1198
00:56:18,030 --> 00:56:22,020
>> Není to tak složité, jako jeden Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Místo toho, je to jen číslo.

1200
00:56:23,830 --> 00:56:27,930
To je byte číslo nula, to je
jeden, to je dvě, to je tři,

1201
00:56:27,930 --> 00:56:30,327
a to je 41.

1202
00:56:30,327 --> 00:56:30,910
Počkej chvíli.

1203
00:56:30,910 --> 00:56:32,510
Myslel jsem, že jsem řekl 42 před chvílí.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Začal jsem počítat od nuly,
takže je vlastně správné.

1206
00:56:37,772 --> 00:56:40,980
Teď nemáme na to skutečně čerpat
jako mřížka, a pokud ji nakreslit jako mřížka

1207
00:56:40,980 --> 00:56:43,520
Myslím, že se věci ve skutečnosti
dostat trochu zavádějící.

1208
00:56:43,520 --> 00:56:46,650
Co programátor by,
v jeho vlastní mysli,

1209
00:56:46,650 --> 00:56:50,310
obecně myslet na to
Paměť jako je stejně jako páska,

1210
00:56:50,310 --> 00:56:53,340
jako kus krycí páskou
že prostě pokračuje dál a dál navždy

1211
00:56:53,340 --> 00:56:54,980
nebo dokud vám dojdou paměti.

1212
00:56:54,980 --> 00:56:59,200
Takže častější způsob, jak čerpat
a jen přemýšlet o paměti

1213
00:56:59,200 --> 00:57:03,710
by se, že je to byte nula, jedna,
dva, tři, a pak tečka, tečka, tečka.

1214
00:57:03,710 --> 00:57:07,650
A máš celkem 42 takových bytů, a to i
i když fyzicky mohlo by to ve skutečnosti

1215
00:57:07,650 --> 00:57:09,480
být něco víc takhle.

1216
00:57:09,480 --> 00:57:12,850
>> Takže pokud si nyní myslí vašich
paměť, protože to, stejně jako páska,

1217
00:57:12,850 --> 00:57:17,640
to je to, co programátor znovu
by vyžadovalo řadu paměti.

1218
00:57:17,640 --> 00:57:20,660
A když chcete skutečně uložit
něco v paměti počítače,

1219
00:57:20,660 --> 00:57:23,290
budete obecně dělat uložení věcí
back-to-back back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Takže jsme mluvili o číslech.

1221
00:57:25,010 --> 00:57:30,880
A když jsem chtěl řešit problémy
stejně jako čtyři, jedna, tři, dva,

1222
00:57:30,880 --> 00:57:33,820
i když jen jsem byl kreslení
pouze čísla čtyři, jedna, tři,

1223
00:57:33,820 --> 00:57:39,490
dva na palubě, by počítač
Opravdu mají toto nastavení do paměti.

1224
00:57:39,490 --> 00:57:43,347
>> A co by bylo vedle
dva v paměti počítače?

1225
00:57:43,347 --> 00:57:44,680
No, není odpověď na tuto otázku.

1226
00:57:44,680 --> 00:57:45,770
My opravdu nevím.

1227
00:57:45,770 --> 00:57:48,200
A tak dlouho, dokud
Počítač nepotřebuje,

1228
00:57:48,200 --> 00:57:51,440
to nemusí starat, co je další
s čísly, že se zajímá o.

1229
00:57:51,440 --> 00:57:55,130
A když jsem dříve řekl, že v počítači
může se pouze na jedné adrese v době,

1230
00:57:55,130 --> 00:57:56,170
To je druh proč.

1231
00:57:56,170 --> 00:57:59,490
>> Ne na rozdíl od záznamu
přehrávačem a čtecí hlava

1232
00:57:59,490 --> 00:58:03,030
budou moci prohlédnout určitá jen
Drážka ve fyzickém záznamu old-school

1233
00:58:03,030 --> 00:58:06,500
v době, obdobně
může počítač díky

1234
00:58:06,500 --> 00:58:09,810
k jeho CPU a jeho
Intel instrukční sada,

1235
00:58:09,810 --> 00:58:12,480
mezi jehož pokyn
se čte z paměti

1236
00:58:12,480 --> 00:58:15,590
nebo uložit do memory--
Počítač může jen dívat

1237
00:58:15,590 --> 00:58:19,210
na jednom místě při time--
někdy i jejich kombinace,

1238
00:58:19,210 --> 00:58:21,770
ale opravdu jen jedno místo najednou.

1239
00:58:21,770 --> 00:58:24,770
Takže když jsme dělali
tyto různé algoritmy,

1240
00:58:24,770 --> 00:58:28,110
Nejsem jen psaní v
vacuum-- čtyři, jedna, tři, dva.

1241
00:58:28,110 --> 00:58:30,849
Tato čísla skutečně patřit
někde fyzické paměti.

1242
00:58:30,849 --> 00:58:32,890
Takže tam jsou malinké
tranzistory nebo nějaký druh

1243
00:58:32,890 --> 00:58:35,840
elektroniky pod
kapuce ukládání těchto hodnot.

1244
00:58:35,840 --> 00:58:40,460
>> A celkem, kolik bitů
podílejí právě teď, jen aby bylo jasno?

1245
00:58:40,460 --> 00:58:45,580
Tak tohle je čtyři byty, nebo
Nyní je to 32 bitů celkem.

1246
00:58:45,580 --> 00:58:49,280
Takže tam jsou vlastně 32 nuly a
Ti tvořící tyto čtyři věci.

1247
00:58:49,280 --> 00:58:52,070
Tam je ještě tady, ale
Znovu jsme se nestarají o to.

1248
00:58:52,070 --> 00:58:55,120
>> Takže teď pojďme položit další
Otázkou pomocí paměti,

1249
00:58:55,120 --> 00:58:57,519
proto, že na konci
dne je v rozporu.

1250
00:58:57,519 --> 00:59:00,310
Bez ohledu na to, co bychom mohli dělat s
počítač, na konci dne

1251
00:59:00,310 --> 00:59:02,560
hardware je stále
Stejný pod kapotou.

1252
00:59:02,560 --> 00:59:04,670
Jak bych ukládat slovo tady?

1253
00:59:04,670 --> 00:59:09,710
No, slovo v počítači, jako
"Ahoj!" by byly uloženy, stejně jako to.

1254
00:59:09,710 --> 00:59:12,300
A pokud byste chtěli delší
Slovo, můžete jednoduše

1255
00:59:12,300 --> 00:59:19,120
přepsat, že i něco říct
jako "ahoj" a obchod, který zde.

1256
00:59:19,120 --> 00:59:23,930
>> A tak i zde to contiguousness
je ve skutečnosti výhodou,

1257
00:59:23,930 --> 00:59:26,530
protože počítač může jen
číst zprava doleva.

1258
00:59:26,530 --> 00:59:28,680
Ale tady je otázka.

1259
00:59:28,680 --> 00:59:33,480
V souvislosti s tímto slovem,
h-e-l-l-o, vykřičník,

1260
00:59:33,480 --> 00:59:38,740
jak by počítač vědět, kde je
Slovo začíná a kde slovo končí?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
V souvislosti s čísly,
jak dělá počítač

1263
00:59:43,800 --> 00:59:48,396
vědět, jak dlouho sled
Čísla je nebo tam, kde to začíná?

1264
00:59:48,396 --> 00:59:50,270
No, to ukáže out--
a nepůjdeme příliš mnoho

1265
00:59:50,270 --> 00:59:54,970
do této úrovně detail--
Počítače pohybovat věci kolem v paměti

1266
00:59:54,970 --> 00:59:57,800
doslova prostřednictvím těchto adres.

1267
00:59:57,800 --> 01:00:02,080
Takže v počítači, pokud jste
psaní kódu k uložení věcí

1268
01:00:02,080 --> 01:00:05,800
jako slova, co jste
opravdu dělají, je psaní

1269
01:00:05,800 --> 01:00:11,320
výrazy, které si vzpomenout, kde v
Paměť počítače jsou tato slova.

1270
01:00:11,320 --> 01:00:14,370
Tak mě nech dělat velmi,
velmi jednoduchý příklad.

1271
01:00:14,370 --> 01:00:18,260
>> Chystám se jít dopředu a
otevírají jednoduchého textového programu,

1272
01:00:18,260 --> 01:00:20,330
a jdu k vytvoření
soubor s názvem hello.c.

1273
01:00:20,330 --> 01:00:22,849
Většina těchto informací jsme
nepůjde do velmi podrobně,

1274
01:00:22,849 --> 01:00:25,140
ale budu psát
Program v tomto jazyce,

1275
01:00:25,140 --> 01:00:31,140
C. To je mnohem víc zastrašující,
Tvrdím, než Scratch,

1276
01:00:31,140 --> 01:00:32,490
ale je to velmi podobné v duchu.

1277
01:00:32,490 --> 01:00:34,364
Ve skutečnosti tyto vlnité
braces-- můžete druh

1278
01:00:34,364 --> 01:00:37,820
myslet na to, co jsem právě udělal, protože to.

1279
01:00:37,820 --> 01:00:39,240
>> Jdeme na to, ve skutečnosti.

1280
01:00:39,240 --> 01:00:45,100
Když zelená vlajka kliknutí
proveďte následující.

1281
01:00:45,100 --> 01:00:50,210
Chci vytisknout "Dobrý den."

1282
01:00:50,210 --> 01:00:51,500
Takže toto je nyní pseudocode.

1283
01:00:51,500 --> 01:00:53,000
Jsem typ rozmazání linky.

1284
01:00:53,000 --> 01:00:56,750
V jazyce C, tento jazyk mluvím
o tento řádek print ahoj

1285
01:00:56,750 --> 01:01:01,940
ve skutečnosti se stává "printf" s
Některé závorky a středník.

1286
01:01:01,940 --> 01:01:03,480
>> Ale je to přesně stejný nápad.

1287
01:01:03,480 --> 01:01:06,730
A to velmi uživatelsky příjemný
"Při zelenou vlajkou klepnutí" se stává

1288
01:01:06,730 --> 01:01:10,182
mnohem více tajemný "int main neplatné."

1289
01:01:10,182 --> 01:01:12,890
A to opravdu nemá mapování,
tak jsem jen tak ignorovat.

1290
01:01:12,890 --> 01:01:17,210
Ale složené závorky jsou stejně jako
zakřivené dílky takhle.

1291
01:01:17,210 --> 01:01:18,700
>> Takže si můžete trochu hádat.

1292
01:01:18,700 --> 01:01:22,357
Dokonce i když jste nikdy předtím naprogramován,
Co tento program pravděpodobně dělat?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Pravděpodobně vytiskne ahoj
s vykřičníkem.

1295
01:01:28,000 --> 01:01:29,150
>> Takže pojďme to zkusit.

1296
01:01:29,150 --> 01:01:30,800
Chystám se ho zachránit.

1297
01:01:30,800 --> 01:01:34,000
A to je opět velmi
old school prostředí.

1298
01:01:34,000 --> 01:01:35,420
Nemohu na tlačítko, nemohu přetáhnout.

1299
01:01:35,420 --> 01:01:36,910
Musím psát příkazy.

1300
01:01:36,910 --> 01:01:41,320
Takže chci spustit svůj program, takže
Mohl jsem to udělat, stejně jako hello.c.

1301
01:01:41,320 --> 01:01:42,292
To je ten soubor jsem běžel.

1302
01:01:42,292 --> 01:01:43,500
Ale počkejte, já jsem chybí krok.

1303
01:01:43,500 --> 01:01:46,470
Co udělal říkáme, je nezbytným
krokem pro jazyk C?

1304
01:01:46,470 --> 01:01:49,470
Právě jsem napsal zdroj
kód, ale co k tomu potřebuji?

1305
01:01:49,470 --> 01:01:50,670
Jo, musím kompilátoru.

1306
01:01:50,670 --> 01:01:57,670
Takže na mém počítači Mac tady, mám
program s názvem GCC, GNU C kompilátor,

1307
01:01:57,670 --> 01:02:03,990
který mi umožňuje dělat tohle-- zatáčku
můj zdrojový kód do, budeme říkat,

1308
01:02:03,990 --> 01:02:04,930
strojový kód.

1309
01:02:04,930 --> 01:02:10,180
>> A vidím, že
opět následujícím způsobem, tyto

1310
01:02:10,180 --> 01:02:14,090
jsou nuly a ty, které jsem právě
vytvořený ze svého zdrojového kódu,

1311
01:02:14,090 --> 01:02:15,730
všechny nul a jedniček.

1312
01:02:15,730 --> 01:02:17,770
A když chci spustit
my program-- se to stane

1313
01:02:17,770 --> 01:02:23,010
být nazýván a.out pro
historická reasons-- "Dobrý den."

1314
01:02:23,010 --> 01:02:24,070
I to může běžet znovu.

1315
01:02:24,070 --> 01:02:25,690
Ahoj ahoj ahoj.

1316
01:02:25,690 --> 01:02:27,430
A zdá se, že pracuje.

1317
01:02:27,430 --> 01:02:31,000
>> Ale to znamená, že někde v mém
Paměť počítače jsou slova

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, vykřičník.

1319
01:02:35,279 --> 01:02:38,070
A ukázalo se, stejně jako stranou,
co je to počítač by typicky

1320
01:02:38,070 --> 01:02:40,550
tomu, že ví, kde
věci začnou a end-- je to

1321
01:02:40,550 --> 01:02:42,460
bude klást zvláštní symbol tady.

1322
01:02:42,460 --> 01:02:46,064
A konvence je umístit
číslo nula na konci slova

1323
01:02:46,064 --> 01:02:48,230
takže víte, kde to
skutečně končí, takže

1324
01:02:48,230 --> 01:02:52,750
nevedou vytisknout víc a víc
znaky, než si ve skutečnosti v úmyslu.

1325
01:02:52,750 --> 01:02:55,400
>> Ale stánek s jídlem tady, a to i
ačkoli to je docela tajemný,

1326
01:02:55,400 --> 01:02:58,140
je, že to nakonec
relativně jednoduché.

1327
01:02:58,140 --> 01:03:04,550
Jste dostali jakousi pásku, prázdné
Prostor na které můžete psát dopisy.

1328
01:03:04,550 --> 01:03:07,150
Vy prostě musíte mít
Speciální symbol, jako je libovolně

1329
01:03:07,150 --> 01:03:10,316
číslo nula, aby na konci
vaše slova tak, aby počítač ví,

1330
01:03:10,316 --> 01:03:13,410
oh, měl bych přestat tisku po
Vidím vykřičník.

1331
01:03:13,410 --> 01:03:16,090
Vzhledem k tomu, další věc, kterou zde
je ASCII hodnota nula,

1332
01:03:16,090 --> 01:03:19,125
nebo null charakter as
někdo by se to nazvat.

1333
01:03:19,125 --> 01:03:21,500
Ale je tu trochu problém
tady a pojďme vrátit

1334
01:03:21,500 --> 01:03:23,320
čísel na chvíli.

1335
01:03:23,320 --> 01:03:28,720
Předpokládejme, že mám ve skutečnosti,
mají celou řadu čísel,

1336
01:03:28,720 --> 01:03:30,730
a předpokládejme, že
Program píšu je

1337
01:03:30,730 --> 01:03:34,680
jako stupeň knihy pro učitele
a učitelů ve třídě.

1338
01:03:34,680 --> 01:03:38,720
A tento program mu umožňuje
zadat skóre svých žáků

1339
01:03:38,720 --> 01:03:39,960
Na vyslýchá.

1340
01:03:39,960 --> 01:03:43,750
A předpokládám, že student dostane
100 na svém prvním testu, možná

1341
01:03:43,750 --> 01:03:49,920
jako 80 na ten příští, pak
75, pak 90 na čtvrtém testu.

1342
01:03:49,920 --> 01:03:54,150
>> Takže v tomto bodě příběhu,
pole je velikosti čtyři.

1343
01:03:54,150 --> 01:03:58,470
Tam je absolutně větší množství paměti v
počítač, ale pole, abych tak řekl,

1344
01:03:58,470 --> 01:04:00,350
je o velikosti čtyři.

1345
01:04:00,350 --> 01:04:06,060
Předpokládejme nyní, že učitel chce
přiřadit pátý kvíz na třídu.

1346
01:04:06,060 --> 01:04:08,510
No, jedna z věcí,
nebo ona bude muset dělat

1347
01:04:08,510 --> 01:04:10,650
Nyní je uložit dodatečnou hodnotu zde.

1348
01:04:10,650 --> 01:04:15,490
Ale pokud pole má učitel
vytvořené v tomto programu je velikosti pro,

1349
01:04:15,490 --> 01:04:22,440
jeden z problému s polem je, že
můžete nejen držet přidání do paměti.

1350
01:04:22,440 --> 01:04:26,470
Vzhledem k tomu, co když jiné části
Program má slovo "hej" právě tam?

1351
01:04:26,470 --> 01:04:29,650
>> Jinými slovy, má paměť může být
použít na cokoliv v programu.

1352
01:04:29,650 --> 01:04:33,250
A pokud se předem jsem zadal, hej,
Chci vstup čtyř kvíz skóre,

1353
01:04:33,250 --> 01:04:34,784
Mohou jít zde a zde.

1354
01:04:34,784 --> 01:04:37,700
A pokud se náhle změní svůj názor
později a že chci pátý kvíz

1355
01:04:37,700 --> 01:04:40,872
skóre, můžete nejen
dát kamkoli budete chtít,

1356
01:04:40,872 --> 01:04:42,580
protože co kdyby to
Paměť je používán

1357
01:04:42,580 --> 01:04:45,990
o něco else-- nějaký jiný program
nebo jiné funkce programu

1358
01:04:45,990 --> 01:04:46,910
že vedete?

1359
01:04:46,910 --> 01:04:50,650
Takže musíte myslet dopředu
Jak chcete uložit svá data,

1360
01:04:50,650 --> 01:04:54,480
protože teď jsi namaloval
yourself do digitálního rohu.

1361
01:04:54,480 --> 01:04:57,280
>> Takže učitel by mohl místo
říci, kdy psaní programu

1362
01:04:57,280 --> 01:04:59,360
pro uložení jeho nebo její
stupně, víte co?

1363
01:04:59,360 --> 01:05:04,180
Budu požadovat,
Při psaní můj program,

1364
01:05:04,180 --> 01:05:12,070
že chci nula, jedna, dva, tři,
čtyři, pět, šest, osm stupňů celkem.

1365
01:05:12,070 --> 01:05:15,320
Tak jeden, dva, tři, čtyři,
pět, šest, sedm, osm.

1366
01:05:15,320 --> 01:05:18,612
Učitel může jen něco málo přes přidělit
paměti při psaní jeho nebo její program,

1367
01:05:18,612 --> 01:05:19,570
a říkat, víte co?

1368
01:05:19,570 --> 01:05:22,236
Nikdy nebudu přiřadit více
než osm vyslýchá v semestru.

1369
01:05:22,236 --> 01:05:23,130
To je prostě šílené.

1370
01:05:23,130 --> 01:05:24,470
Už nikdy přidělit to.

1371
01:05:24,470 --> 01:05:28,270
Tak, že tento způsob on nebo ona má
Flexibilita pro ukládání studentské skóre,

1372
01:05:28,270 --> 01:05:33,010
stejně jako 75, 90, a možná jeden navíc, pokud
student dostal kreditu navíc, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Ale v případě, že učitel nikdy
používá tyto tři mezery,

1374
01:05:36,130 --> 01:05:38,860
je tu intuitivní stánek s jídlem zde.

1375
01:05:38,860 --> 01:05:41,410
On nebo ona je jen plýtvání místem.

1376
01:05:41,410 --> 01:05:44,790
Takže jinými slovy, tam je to
Společný kompromis při programování

1377
01:05:44,790 --> 01:05:48,241
kde si můžete buď přidělit
přesně tolik, kolik paměti, jak chcete,

1378
01:05:48,241 --> 01:05:51,490
Vzhůru z nich je, že jsi výborný
efficient-- nejste být nehospodárné

1379
01:05:51,490 --> 01:05:54,640
na all-- ale nevýhoda, z nichž
Je co když si to rozmyslíte, kdy

1380
01:05:54,640 --> 01:05:58,780
pomocí programu, který chcete uložit
více dat, než jste původně zamýšleli.

1381
01:05:58,780 --> 01:06:03,030
>> Možná řešení je, tedy,
napsat své programy tak,

1382
01:06:03,030 --> 01:06:05,605
že používají více paměti
než ve skutečnosti potřebují.

1383
01:06:05,605 --> 01:06:07,730
Tímto způsobem si nejdeš
narazit na tento problém,

1384
01:06:07,730 --> 01:06:09,730
ale ty jsou nehospodárné.

1385
01:06:09,730 --> 01:06:12,960
A čím více paměti váš program používá,
jak jsme diskutovali včera, tím méně

1386
01:06:12,960 --> 01:06:15,410
paměť, která je k dispozici
pro jiné programy,

1387
01:06:15,410 --> 01:06:18,790
tím dříve může být váš počítač zpomalit
dolů, protože virtuální paměti.

1388
01:06:18,790 --> 01:06:22,670
A tak ideálním řešením by mohlo být to, co?

1389
01:06:22,670 --> 01:06:24,610
>> Under-přidělování zdá špatné.

1390
01:06:24,610 --> 01:06:27,030
Over-Přidělení zdá špatné.

1391
01:06:27,030 --> 01:06:31,120
Takže to, co by mohlo být lepším řešením?

1392
01:06:31,120 --> 01:06:32,390
Přerozdělení.

1393
01:06:32,390 --> 01:06:33,590
Být dynamičtější.

1394
01:06:33,590 --> 01:06:37,520
Nenuťte si vybrat
priori, na začátku, co chcete.

1395
01:06:37,520 --> 01:06:41,370
A už vůbec ne více než přidělit,
abyste nebyli nehospodárné.

1396
01:06:41,370 --> 01:06:45,770
>> A tak k dosažení tohoto cíle jsme
muset hodit tuto datovou strukturu,

1397
01:06:45,770 --> 01:06:48,100
tak říkajíc, pryč.

1398
01:06:48,100 --> 01:06:51,080
A tak to, co programátor
se obvykle používají

1399
01:06:51,080 --> 01:06:55,940
Je něco, co nazývá není
array ale provázaný seznam.

1400
01:06:55,940 --> 01:07:00,860
Jinými slovy, on nebo ona bude
začít přemýšlet o jejich paměť

1401
01:07:00,860 --> 01:07:05,280
jako bytí druh tvaru, který jim
lze čerpat v následujícím způsobem.

1402
01:07:05,280 --> 01:07:08,520
Pokud chci uložit jedno číslo
program-- takže je to září,

1403
01:07:08,520 --> 01:07:12,600
Dal jsem moji studenti kvíz; Chci
ukládat první kvíz studentů,

1404
01:07:12,600 --> 01:07:16,220
a dostali 100 na to-- I
Chystám se zeptat můj počítač,

1405
01:07:16,220 --> 01:07:19,540
prostřednictvím tohoto programu jsem
napsáno, pro jeden kus paměti.

1406
01:07:19,540 --> 01:07:22,570
A budu ukládat
Číslo 100 v něm, a to je vše.

1407
01:07:22,570 --> 01:07:24,820
>> Pak několik týdnů později
když jsem si svůj druhý kvíz,

1408
01:07:24,820 --> 01:07:27,890
a je čas psát
V tomto 90%, jdu

1409
01:07:27,890 --> 01:07:32,129
požádat počítač, hej, počítač,
mohu mít jiný kus paměti?

1410
01:07:32,129 --> 01:07:34,170
Bude to, aby mi to
prázdný kus paměti.

1411
01:07:34,170 --> 01:07:39,370
Chystám se dát do čísla 90,
ale v mém programu nějakým způsobem other--

1412
01:07:39,370 --> 01:07:42,100
a nebudeme bát
syntaxe pro tohle-- potřebuji

1413
01:07:42,100 --> 01:07:44,430
nějak řetěz tyto věci dohromady.

1414
01:07:44,430 --> 01:07:47,430
A já jim to řetěz spolu s
co vypadá jako šíp zde.

1415
01:07:47,430 --> 01:07:50,050
>> Třetí kvíz, který přijde,
Chystám se říct, hej, počítač,

1416
01:07:50,050 --> 01:07:51,680
dej mi ještě kus paměti.

1417
01:07:51,680 --> 01:07:54,660
A já jdu dát dolů
co to bylo, jako 75,

1418
01:07:54,660 --> 01:07:56,920
a musím řetězci této
teď spolu nějak.

1419
01:07:56,920 --> 01:08:00,290
Čtvrtý kvíz přijde, a možná
to je ke konci semestru.

1420
01:08:00,290 --> 01:08:03,140
A tím bodem mého programu
může být použití paměti

1421
01:08:03,140 --> 01:08:05,540
všude, po celém fyzicky.

1422
01:08:05,540 --> 01:08:08,170
A tak jen pro zábavu, jsem
bude kreslit to tam

1423
01:08:08,170 --> 01:08:11,260
quiz-- jsem zapomněl, jaké to bylo; já
že možná 80 nebo something--

1424
01:08:11,260 --> 01:08:12,500
cesta sem.

1425
01:08:12,500 --> 01:08:15,920
>> Ale to je v pořádku, protože obrazově
Budu čerpat tento řádek.

1426
01:08:15,920 --> 01:08:19,063
Jinými slovy, ve skutečnosti,
v hardwaru počítače,

1427
01:08:19,063 --> 01:08:20,979
První skóre mohlo
skončit tady, protože je to

1428
01:08:20,979 --> 01:08:22,529
hned na začátku semestru.

1429
01:08:22,529 --> 01:08:25,810
Příští jeden by mohl skončit tady
protože trochu času uplynulo

1430
01:08:25,810 --> 01:08:27,210
a program stále běží.

1431
01:08:27,210 --> 01:08:30,060
Dalším skóre, která byla
75, by mohl být tady.

1432
01:08:30,060 --> 01:08:33,420
A poslední skóre mohlo být
80, což je tady.

1433
01:08:33,420 --> 01:08:38,729
>> Takže ve skutečnosti fyzicky, by to mohlo být
co paměti počítače vypadá.

1434
01:08:38,729 --> 01:08:41,569
Ale to není užitečný mentální
paradigma pro počítačový programátor.

1435
01:08:41,569 --> 01:08:44,649
Proč by vám záleží, kde je
Heck vaše data skončí?

1436
01:08:44,649 --> 01:08:46,200
Chcete jen pro ukládání dat.

1437
01:08:46,200 --> 01:08:49,390
>> To je něco jako naši diskusi
dřívější čerpání krychle.

1438
01:08:49,390 --> 01:08:52,200
Proč se staráš, co
úhel je krychle

1439
01:08:52,200 --> 01:08:53,740
a jak budete muset obrátit ji nakreslit?

1440
01:08:53,740 --> 01:08:54,950
Chcete jen krychle.

1441
01:08:54,950 --> 01:08:57,359
Stejně tak zde vás
prostě chtějí stupně knize.

1442
01:08:57,359 --> 01:08:59,559
Jen chcete myslet
toto jako seznam čísel.

1443
01:08:59,559 --> 01:09:01,350
Koho zajímá, jak je to
realizovány v hardwaru?

1444
01:09:01,350 --> 01:09:05,180
>> Takže teď abstrakce
Je to obrázek zde.

1445
01:09:05,180 --> 01:09:07,580
Jedná se o seznam spojena, as
programátor by to nazval,

1446
01:09:07,580 --> 01:09:10,640
pokud máte
Seznam samozřejmě čísel.

1447
01:09:10,640 --> 01:09:14,990
Ale je to spojeno obrazově
pomocí těchto šipek,

1448
01:09:14,990 --> 01:09:18,510
a všechny tyto šípy are-- vespod
digestoř, pokud jste zvědaví,

1449
01:09:18,510 --> 01:09:23,210
Připomínáme, že náš fyzický hardware má
adresy nula, jedna, dva, tři, čtyři.

1450
01:09:23,210 --> 01:09:28,465
Všechny tyto šípy jsou jako mapu
nebo nasměrování, kde v případě 90 je-- nyní

1451
01:09:28,465 --> 01:09:29,090
Musím počítat.

1452
01:09:29,090 --> 01:09:31,750
>> Nula, jedna, dva, tři,
čtyři, pět, šest, sedm.

1453
01:09:31,750 --> 01:09:35,640
Vypadá to, že 90 je
adresa paměti číslo sedm.

1454
01:09:35,640 --> 01:09:38,460
Všechny tyto střely se
jako malý kousek papíru

1455
01:09:38,460 --> 01:09:42,439
že to dává pokyny k
Program, který říká, že řídit tuto mapu

1456
01:09:42,439 --> 01:09:43,880
se dostat na místo sedmé.

1457
01:09:43,880 --> 01:09:46,680
A tam najdou
Druhý kvíz skóre studenta.

1458
01:09:46,680 --> 01:09:52,100
Mezitím, 75-- když jsem v tom pokračovat,
To je sedm, osm, devět, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Tento druhý šíp právě představuje
mapy na paměťové místo 15.

1461
01:09:59,080 --> 01:10:02,550
Ale opět, programátor obvykle dělá
nestará o této úrovni detailu.

1462
01:10:02,550 --> 01:10:05,530
A ve většině každém programování
jazyka dnes, programátor

1463
01:10:05,530 --> 01:10:10,490
ani nebude vědět, kde v paměti
tato čísla ve skutečnosti jsou.

1464
01:10:10,490 --> 01:10:14,830
Jediné, co nebo ona má se starat o je
které jsou nějakým způsobem spojeny dohromady

1465
01:10:14,830 --> 01:10:18,390
V datové struktury, jako je tato.

1466
01:10:18,390 --> 01:10:21,580
>> Ale ukazuje se, není
se dostat příliš technické.

1467
01:10:21,580 --> 01:10:27,430
Ale jen proto, že můžeme snad
dovolit mít tuto diskusi,

1468
01:10:27,430 --> 01:10:33,630
Domníváme se, že jsme znovu
Tento problém tady z pole.

1469
01:10:33,630 --> 01:10:35,780
Uvidíme, jestli budeme litovat jít sem.

1470
01:10:35,780 --> 01:10:42,950
To je 100, 90, 75, a 80.

1471
01:10:42,950 --> 01:10:44,980
>> Dovolte mi, abych stručně, aby toto tvrzení.

1472
01:10:44,980 --> 01:10:48,980
Toto je pole, a znovu,
charakteristickým rysem matici

1473
01:10:48,980 --> 01:10:52,400
je to, že všechna vaše data je zpět, aby
zády k sobě v memory-- doslovně

1474
01:10:52,400 --> 01:10:56,830
jeden byte nebo možná čtyři bajty,
některé fixní počet bajtů pryč.

1475
01:10:56,830 --> 01:11:00,710
V propojeném seznamu, který bychom mohli čerpat
takhle, pod kapotou, který

1476
01:11:00,710 --> 01:11:02,000
ví, kde ta věc je?

1477
01:11:02,000 --> 01:11:03,630
To ani nemusí proudit takhle.

1478
01:11:03,630 --> 01:11:06,050
Některé z těchto údajů může být
zpět vlevo nahoře.

1479
01:11:06,050 --> 01:11:07,530
Nemusíte ani vědět.

1480
01:11:07,530 --> 01:11:15,430
>> A tak s řadou, máte
Funkce známý jako náhodný přístup.

1481
01:11:15,430 --> 01:11:20,570
A co s libovolným přístupem znamená,
že počítač může skočit okamžitě

1482
01:11:20,570 --> 01:11:22,730
na libovolné místo v poli.

1483
01:11:22,730 --> 01:11:23,580
Proč?

1484
01:11:23,580 --> 01:11:26,000
Vzhledem k tomu, že počítač ví
že první poloha je

1485
01:11:26,000 --> 01:11:29,540
nula, jedna, dvě, tři.

1486
01:11:29,540 --> 01:11:33,890
>> A tak pokud chcete přejít z
tento prvek k dalšímu prvku,

1487
01:11:33,890 --> 01:11:36,099
doslova, v
počítače mysl, stačí přidat jeden.

1488
01:11:36,099 --> 01:11:39,140
Chcete-li jít do třetího prvku,
stačí přidat one-- další prvek, jen

1489
01:11:39,140 --> 01:11:40,290
přidat jeden.

1490
01:11:40,290 --> 01:11:42,980
Nicméně, v této verzi
příběhu, předpokládám

1491
01:11:42,980 --> 01:11:46,080
počítač je v současné době hledá
na nebo do činění s číslem 100.

1492
01:11:46,080 --> 01:11:49,770
Jak se dostanete k dalšímu
stupně v platové třídě knize?

1493
01:11:49,770 --> 01:11:52,560
>> Musíte vzít sedm
Kroky, které je libovolná.

1494
01:11:52,560 --> 01:11:58,120
Chcete-li získat na ten příští, budete muset
trvat dalších osm kroků se dostat do 15 let.

1495
01:11:58,120 --> 01:12:02,250
Jinými slovy, to není
konstantní mezeru mezi čísly,

1496
01:12:02,250 --> 01:12:04,857
a tak to prostě bere
Počítač více času je bod.

1497
01:12:04,857 --> 01:12:06,940
Počítač má k hledání
prostřednictvím paměti v pořadí

1498
01:12:06,940 --> 01:12:08,990
najít to, co hledáte.

1499
01:12:08,990 --> 01:12:14,260
>> Tak vzhledem k tomu, pole má tendenci být
rychlá údaje structure-- kvůli tobě

1500
01:12:14,260 --> 01:12:17,610
může doslova dělat jednoduchou aritmetiku
a dostat tam, kam chcete, přidáním jednoho,

1501
01:12:17,610 --> 01:12:21,300
Pro instance-- spojový seznam,
obětujete tuto funkci.

1502
01:12:21,300 --> 01:12:24,020
Nemůžete prostě jít od první
na druhé až třetího na čtvrté místo.

1503
01:12:24,020 --> 01:12:25,240
Budete muset následovat mapy.

1504
01:12:25,240 --> 01:12:28,160
Budete muset vzít další kroky
se dostat k těm hodnotám, které

1505
01:12:28,160 --> 01:12:30,230
Zdá se, že přidání náklady.

1506
01:12:30,230 --> 01:12:35,910
Takže budeme platit cenu, ale to, co bylo
funkce, která Dan hledal tady?

1507
01:12:35,910 --> 01:12:38,110
Co spojový seznam
zřejmě nám umožňují dělat,

1508
01:12:38,110 --> 01:12:40,240
který byl původ
tento konkrétní příběh?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Přesně.

1511
01:12:43,830 --> 01:12:46,220
Dynamická velikost na to.

1512
01:12:46,220 --> 01:12:48,040
Můžeme přidat do tohoto seznamu.

1513
01:12:48,040 --> 01:12:51,430
Můžeme dokonce zmenšit seznamu, takže
že jsme pouze pomocí tolik paměti

1514
01:12:51,430 --> 01:12:55,560
jak vlastně chceme a tak
nikdy nejsme over-přidělování.

1515
01:12:55,560 --> 01:12:58,470
>> Teď už jen stačí být opravdu nit-vybíravý,
tam je skrytá náklady.

1516
01:12:58,470 --> 01:13:01,980
Takže byste neměli nechat mě přesvědčit
jste, že je to přesvědčivý kompromis.

1517
01:13:01,980 --> 01:13:04,190
Je tu další skryté náklady zde.

1518
01:13:04,190 --> 01:13:06,550
Výhoda, aby bylo jasné,
je to, že dostaneme dynamiku.

1519
01:13:06,550 --> 01:13:10,359
Pokud chci další prvek, mohu jen
nakreslit a vložit číslo tam.

1520
01:13:10,359 --> 01:13:12,150
A pak jsem jej propojit
s obrázkem tady,

1521
01:13:12,150 --> 01:13:14,970
zatímco tady opět, jestli jsem
maloval sám sebe do kouta,

1522
01:13:14,970 --> 01:13:19,410
-li něco jiného již používá
paměť tady, jsem smůlu.

1523
01:13:19,410 --> 01:13:21,700
Já jsem namaloval sám sebe do kouta.

1524
01:13:21,700 --> 01:13:24,390
>> Ale to, co je skryto
stálo na tomto obrázku?

1525
01:13:24,390 --> 01:13:27,690
Nejde jen o částku
o čas potřebný

1526
01:13:27,690 --> 01:13:29,870
jít odtud až sem,
což je sedm kroků, pak

1527
01:13:29,870 --> 01:13:32,820
osm stupňů, což je více než jedna.

1528
01:13:32,820 --> 01:13:34,830
Jaký je další skryté náklady?

1529
01:13:34,830 --> 01:13:35,440
Není to jen čas.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Doplňující informace
nezbytné pro dosažení tento obrázek.

1532
01:13:49,940 --> 01:13:53,210
>> Jasně, že mapa, ty malé kousky
papíru, jak jsem držet popisovat je jako.

1533
01:13:53,210 --> 01:13:55,650
Jedná arrows-- ty nejsou zadarmo.

1534
01:13:55,650 --> 01:13:57,660
Computer-- víte
co je v počítači.

1535
01:13:57,660 --> 01:13:58,790
To má nul a jedniček.

1536
01:13:58,790 --> 01:14:03,170
Chcete-li reprezentovat šipky nebo A
map nebo číslo, budete potřebovat nějakou paměť.

1537
01:14:03,170 --> 01:14:05,950
Takže druhou cenu, kterou
platit za propojeného seznamu

1538
01:14:05,950 --> 01:14:09,070
obyčejná počítačová věda
zdroj, je také prostor.

1539
01:14:09,070 --> 01:14:11,710
>> A skutečně tak, tak často,
Mezi kompromisů

1540
01:14:11,710 --> 01:14:15,580
při navrhování softwarové inženýrství
Systémy je čas a space--

1541
01:14:15,580 --> 01:14:18,596
jsou dvě z vašich složek, dva
z vašich nejnákladnějších složek.

1542
01:14:18,596 --> 01:14:21,220
To mě stojí víc času
protože musím sledovat tuto mapu,

1543
01:14:21,220 --> 01:14:25,730
ale je to také mi stojí více prostoru
protože musím držet tuto mapu okolí.

1544
01:14:25,730 --> 01:14:28,730
Takže naděje, jak jsme druh
diskutovali více než včera a dnes

1545
01:14:28,730 --> 01:14:31,720
je, že výhody
převáží nad náklady.

1546
01:14:31,720 --> 01:14:33,870
>> Ale není jasné řešení zde.

1547
01:14:33,870 --> 01:14:35,870
Možná je to better--
a la rychlé a špinavé,

1548
01:14:35,870 --> 01:14:38,660
jako Kareem navrženo earlier--
hodit paměti na problém.

1549
01:14:38,660 --> 01:14:42,520
Stačí koupit více paměti, myslím, že méně
hard o vyřešení problému,

1550
01:14:42,520 --> 01:14:44,595
a řešit ji v jednodušším způsobem.

1551
01:14:44,595 --> 01:14:46,720
A skutečně dříve, když
jsme si povídali o kompromisy,

1552
01:14:46,720 --> 01:14:49,190
to nebylo prostor v
počítač a čas.

1553
01:14:49,190 --> 01:14:51,810
Bylo na čase developer, který
je dalším zdrojem.

1554
01:14:51,810 --> 01:14:54,829
>> Takže znovu, je to balancování
se snaží rozhodnout, která z těchto věcí

1555
01:14:54,829 --> 01:14:55,870
jste ochotni utratit?

1556
01:14:55,870 --> 01:14:57,380
Což je nejlevnější?

1557
01:14:57,380 --> 01:15:01,040
Což vede k lepším výsledkům?

1558
01:15:01,040 --> 01:15:01,540
To jo?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Vskutku.

1561
01:15:12,580 --> 01:15:15,970
V takovém případě, pokud jste
reprezentující čísla v maps--

1562
01:15:15,970 --> 01:15:18,820
tito jsou voláni v mnoha jazycích
"ukazovátka" nebo "adresa" -

1563
01:15:18,820 --> 01:15:20,390
je to dvojnásobek prostor.

1564
01:15:20,390 --> 01:15:24,390
Že nemusí být tak špatné, jak double-li
Teď jsme jen ukládání čísel.

1565
01:15:24,390 --> 01:15:27,410
Předpokládejme, že jsme byli ukládání
záznamy o pacientech v hospital--

1566
01:15:27,410 --> 01:15:30,870
takže jména Pierson to, telefonní čísla,
čísla sociálního pojištění, lékař

1567
01:15:30,870 --> 01:15:31,540
dějiny.

1568
01:15:31,540 --> 01:15:34,160
Tento box může být mnoho,
mnohem větší, v kterémžto případě

1569
01:15:34,160 --> 01:15:38,000
malinké ukazatel, adresa
další element--, že to není velký problém.

1570
01:15:38,000 --> 01:15:40,620
Je to takový třásně
stálo na tom nezáleží.

1571
01:15:40,620 --> 01:15:43,210
Ale v tomto případě, jo, je to dvojnásobek.

1572
01:15:43,210 --> 01:15:45,290
Dobrá otázka.

1573
01:15:45,290 --> 01:15:47,900
>> Pojďme se bavit o době, kdy
trochu konkrétněji.

1574
01:15:47,900 --> 01:15:50,380
Jaká je doba chodu
vyhledávání tento seznam?

1575
01:15:50,380 --> 01:15:53,640
Dejme tomu, že jsem chtěl hledat
přes všechny stupně studentů,

1576
01:15:53,640 --> 01:15:55,980
a je tu n tříd
v této datové struktury.

1577
01:15:55,980 --> 01:15:58,830
Také zde můžeme půjčit
Slovník dříve.

1578
01:15:58,830 --> 01:16:00,890
Jedná se o lineární struktura dat.

1579
01:16:00,890 --> 01:16:04,570
>> Velký O n je to, co je zapotřebí, aby si
na konci této datové struktury,

1580
01:16:04,570 --> 01:16:08,410
whereas-- a my jsme neviděli
Tento before-- pole vám dává

1581
01:16:08,410 --> 01:16:13,555
čemu se říká časová konstanta, což znamená,
jeden krok nebo dva kroky nebo 10 steps--

1582
01:16:13,555 --> 01:16:14,180
nezáleží.

1583
01:16:14,180 --> 01:16:15,440
Je to pevně stanovený počet.

1584
01:16:15,440 --> 01:16:17,440
To nemá nic společného s
velikost pole.

1585
01:16:17,440 --> 01:16:20,130
A důvod pro to,
Znovu je náhodný přístup.

1586
01:16:20,130 --> 01:16:23,180
Počítač může jen bezprostředně
skočit na jiném místě,

1587
01:16:23,180 --> 01:16:27,770
protože jsou všechny stejné
vzdálenost od všeho ostatního.

1588
01:16:27,770 --> 01:16:29,112
Neexistuje žádná myšlení zapojit.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Dobře.

1591
01:16:32,400 --> 01:16:39,230
Takže pokud mohu, dovolte mi, abych se snaží
malovat dvě poslední fotky.

1592
01:16:39,230 --> 01:16:42,830
Velmi častým jeden známý jako hash tabulky.

1593
01:16:42,830 --> 01:16:51,120
Takže motivovat tuto diskusi,
nech mě přemýšlet o tom, jak to udělat.

1594
01:16:51,120 --> 01:16:52,610
>> Tak jak o tom?

1595
01:16:52,610 --> 01:16:55,160
Předpokládejme, že problém
Chceme-li řešit nyní

1596
01:16:55,160 --> 01:16:58,360
realizuje v dictionary--
takže celá parta anglických slov

1597
01:16:58,360 --> 01:16:59,330
nebo cokoliv jiného.

1598
01:16:59,330 --> 01:17:02,724
A cílem je, aby bylo možné zodpovědět
otázky formě je to slovo?

1599
01:17:02,724 --> 01:17:04,640
Takže chcete implementovat
kontrolu pravopisu, jen

1600
01:17:04,640 --> 01:17:07,220
jako fyzická slovníku
že se můžete podívat, co se v.

1601
01:17:07,220 --> 01:17:10,490
Předpokládejme, že kdybych to s polem.

1602
01:17:10,490 --> 01:17:12,590
Nemohl jsem to udělat.

1603
01:17:12,590 --> 01:17:20,756
>> A předpokládám, že slova jsou jablka
a banán a meloun.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
A já si nemyslím, že ovoce
že začít s d, takže jsme jen

1606
01:17:26,465 --> 01:17:27,590
bude mít tři plody.

1607
01:17:27,590 --> 01:17:31,510
Takže to je pole, a my jsme
skladování všechna tato slova

1608
01:17:31,510 --> 01:17:34,200
v tomto slovníku jako pole.

1609
01:17:34,200 --> 01:17:39,350
Otázkou tedy je, jak jinak
mohl byste uložit tyto informace?

1610
01:17:39,350 --> 01:17:43,160
>> No, já jsem trochu podvádění tady, protože
každý z těchto písmen ve slově

1611
01:17:43,160 --> 01:17:44,490
je opravdu individuální byte.

1612
01:17:44,490 --> 01:17:46,740
Takže když jsem opravdu chtěl být
nit-vybíravý, měl jsem opravdu

1613
01:17:46,740 --> 01:17:49,600
Tento rozdelit do mnohem
Menší kousky paměti,

1614
01:17:49,600 --> 01:17:51,289
a my jsme mohli dělat přesně to.

1615
01:17:51,289 --> 01:17:53,580
Ale budeme narážet na
stejný problém jako předtím.

1616
01:17:53,580 --> 01:17:56,674
Co když, jak Merriam Webster nebo Oxford
dělá každý rok-- dodávají slova

1617
01:17:56,674 --> 01:17:59,340
na dictionary-- my ne
nutně chtějí malovat sami

1618
01:17:59,340 --> 01:18:00,780
do rohu s polem?

1619
01:18:00,780 --> 01:18:05,710
>> Takže místo toho, možná chytřejší přístup
je dát jablko ve vlastním uzlu nebo box

1620
01:18:05,710 --> 01:18:11,190
jak bychom říci, banán, a
Pak zde máme ananasový meloun.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
A my string tyto věci dohromady.

1623
01:18:16,790 --> 01:18:19,980
Tak tohle je pole, a
To je provázaný seznam.

1624
01:18:19,980 --> 01:18:23,300
Pokud se vám není úplně vidět, to prostě
říká: "pole", a to říká, že "seznam."

1625
01:18:23,300 --> 01:18:25,780
>> Takže máme stejný
Přesné problémy jako dříve,

1626
01:18:25,780 --> 01:18:28,600
kdy máme nyní
dynamika našeho propojeného seznamu.

1627
01:18:28,600 --> 01:18:31,090
Ale my máme poměrně pomalý slovník.

1628
01:18:31,090 --> 01:18:32,870
Dejme tomu, že chci vyhledat slovo.

1629
01:18:32,870 --> 01:18:35,430
To mi může trvat velký O n
kroky, protože slovo by mohla

1630
01:18:35,430 --> 01:18:37,840
se celou cestu na konci
seznam, stejně jako melounu.

1631
01:18:37,840 --> 01:18:40,600
A ukázalo se, že
programování, třídění

1632
01:18:40,600 --> 01:18:42,700
svatého grálu údajů
struktury, je něco,

1633
01:18:42,700 --> 01:18:46,620
že vám dává konstantní
Čas jako matici

1634
01:18:46,620 --> 01:18:50,870
ale přesto vám dává dynamiku.

1635
01:18:50,870 --> 01:18:52,940
>> Takže můžeme mít to nejlepší z obou světů?

1636
01:18:52,940 --> 01:18:55,570
A skutečně, je tu něco
volal hash tabulky

1637
01:18:55,570 --> 01:18:59,320
který vám umožní dělat přesně
že, byť jen přibližně.

1638
01:18:59,320 --> 01:19:03,140
Hash tabulka je milovník
Datová struktura, která nám

1639
01:19:03,140 --> 01:19:06,340
napadne jako
Kombinace array--

1640
01:19:06,340 --> 01:19:12,390
a budu ji čerpat
jako tohle-- a spojových seznamů

1641
01:19:12,390 --> 01:19:17,310
že budu čerpat takhle tady.

1642
01:19:17,310 --> 01:19:19,760
>> A to, jak ta věc
Práce je následující.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Pokud toto now-- hash table--
je můj třetí datová struktura,

1645
01:19:29,540 --> 01:19:32,590
A chci uložit
slov to, nemám

1646
01:19:32,590 --> 01:19:35,440
chcete jen ukládat všechny
Slova zády k sobě, aby zády k sobě.

1647
01:19:35,440 --> 01:19:37,430
Chci využít některé
kus informací

1648
01:19:37,430 --> 01:19:40,330
o slovech, která vám umožní
me dostat tam, kde je to rychlejší.

1649
01:19:40,330 --> 01:19:43,666
>> Tak daný slova jablko
a banán a meloun,

1650
01:19:43,666 --> 01:19:45,040
Záměrně jsem zvolil ta slova.

1651
01:19:45,040 --> 01:19:45,340
Proč?

1652
01:19:45,340 --> 01:19:47,631
Co je to druh zásadně
odlišný o tři?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Co je jasné?

1655
01:19:51,484 --> 01:19:52,900
Začínají s různými písmeny.

1656
01:19:52,900 --> 01:19:53,900
>> Tak víte co?

1657
01:19:53,900 --> 01:19:57,120
Spíše než dát všechny moje slova
stejný vědro, tak říkajíc,

1658
01:19:57,120 --> 01:20:00,390
stejně jako v jedné velké seznamu, proč ne
I alespoň pokusit optimalizace

1659
01:20:00,390 --> 01:20:04,180
a aby se mé seznamy 1/26 tak dlouho.

1660
01:20:04,180 --> 01:20:07,440
Přesvědčivá optimalizace
by mohl být důvod, proč ne

1661
01:20:07,440 --> 01:20:10,650
Já-- při vkládání slovo
do této datové struktury,

1662
01:20:10,650 --> 01:20:14,300
do paměti počítače, proč
Co kdybych sem dát všechny "A" slovo,

1663
01:20:14,300 --> 01:20:17,270
všechna "b" slova zde,
a všechny "C" slova tady?

1664
01:20:17,270 --> 01:20:24,610
Takže tohle skončí uvedení jablko
tady, banán tady, ananasový meloun tady,

1665
01:20:24,610 --> 01:20:25,730
a tak dále.

1666
01:20:25,730 --> 01:20:31,700
>> A pokud mám další
Slovo jako--, co je další?

1667
01:20:31,700 --> 01:20:36,640
Jablko, banán, hruška.

1668
01:20:36,640 --> 01:20:39,370
Každý, kdo myslet na ovoce
který začíná, B nebo C?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- perfektní.

1670
01:20:40,570 --> 01:20:43,990
Že se chystá skončit tady.

1671
01:20:43,990 --> 01:20:47,530
A tak se zdá, že mají
okrajově lepší řešení,

1672
01:20:47,530 --> 01:20:50,820
protože teď, když chci
hledat jablko, já

1673
01:20:50,820 --> 01:20:53,200
first-- já ne jen ponořit
do mé datové struktury.

1674
01:20:53,200 --> 01:20:54,850
Nemyslím ponořit do paměti svého počítače.

1675
01:20:54,850 --> 01:20:56,530
Poprvé jsem se podívat na první písmeno.

1676
01:20:56,530 --> 01:20:58,610
>> A to je to, co počítačový
vědec řekne.

1677
01:20:58,610 --> 01:21:00,760
Vy hash do své datové struktury.

1678
01:21:00,760 --> 01:21:04,100
Budete mít svůj vstup, který v
Tento případ je slovo, jako jablko.

1679
01:21:04,100 --> 01:21:07,150
Můžete analyzovat, při pohledu na
První písmeno v tomto případě,

1680
01:21:07,150 --> 01:21:08,340
tím ji hash.

1681
01:21:08,340 --> 01:21:10,950
Hešování je obecný termín, kdy
budete mít něco jako vstup

1682
01:21:10,950 --> 01:21:12,116
a produkovat nějaký výstup.

1683
01:21:12,116 --> 01:21:15,090
A výstup v tom, že
Případ je umístění

1684
01:21:15,090 --> 01:21:18,150
Chcete-li vyhledávat, první
lokalita, druhé místo, třetí.

1685
01:21:18,150 --> 01:21:22,160
Takže vstup je jablko,
je výstup první.

1686
01:21:22,160 --> 01:21:25,054
Vstup je banán se
Výstup by měl být druhý.

1687
01:21:25,054 --> 01:21:27,220
Vstup je ananasový meloun,
výstup by měl být třetí.

1688
01:21:27,220 --> 01:21:30,320
Vstup je borůvka se
Výstup by měl být opět druhý.

1689
01:21:30,320 --> 01:21:34,010
A to je to, co vám pomůže vzít
zkratky přes svou paměť

1690
01:21:34,010 --> 01:21:39,050
za účelem získání slovům
nebo data efektivněji.

1691
01:21:39,050 --> 01:21:43,330
>> Teď to snižuje svůj čas potenciálně
jak hodně jako jedna z 26,

1692
01:21:43,330 --> 01:21:45,850
protože pokud předpokládáme, že vás
mít tolik "A" slova jako "z"

1693
01:21:45,850 --> 01:21:48,080
Slova jako "q" slov, která
ve skutečnosti není realistic--

1694
01:21:48,080 --> 01:21:50,830
budete mít překroutit napříč
některá písmena alphabet--

1695
01:21:50,830 --> 01:21:53,204
ale to by přírůstkové
Přístup, který má umožnit

1696
01:21:53,204 --> 01:21:55,930
můžete se dostat do slov mnohem rychleji.

1697
01:21:55,930 --> 01:21:59,660
A ve skutečnosti, sofistikovaná
programu, Brýle na světě,

1698
01:21:59,660 --> 01:22:02,180
Facebooks z world--
by použít hash tabulky

1699
01:22:02,180 --> 01:22:03,740
pro mnoho různých účelů.

1700
01:22:03,740 --> 01:22:06,590
Ale oni by neměla být tak naivní,
jen podívat na první písmeno

1701
01:22:06,590 --> 01:22:09,700
V jablko nebo banán nebo
hruškovice nebo melounu,

1702
01:22:09,700 --> 01:22:13,420
protože jak můžete vidět tyto
seznamy by mohly ještě dostat dlouho.

1703
01:22:13,420 --> 01:22:17,130
>> A tak by to mohlo být ještě sort
z linear-- tak nějak pomalu,

1704
01:22:17,130 --> 01:22:19,980
stejně jako s velkým O n
které jsme diskutovali dříve.

1705
01:22:19,980 --> 01:22:25,290
Takže, co je to opravdu dobrý hash tabulka
do-- to bude mít mnohem větší pole.

1706
01:22:25,290 --> 01:22:28,574
A bude používat mnohem
sofistikované funkce zatřiďování

1707
01:22:28,574 --> 01:22:30,240
takže to není jen podívat na "A".

1708
01:22:30,240 --> 01:22:35,480
Možná to vypadá na "A-p-p-l-e" a
nějak převádí těch pět písmen

1709
01:22:35,480 --> 01:22:38,400
do místa, kde
Apple by měl být uložen.

1710
01:22:38,400 --> 01:22:42,660
My jen naivně pomocí písmeno "A"
sám, protože je to pěkný a jednoduchý.

1711
01:22:42,660 --> 01:22:44,600
>> Ale hash tabulka, ve
konec, můžete myslet

1712
01:22:44,600 --> 01:22:47,270
jako kombinace
pole, přičemž každý z nich

1713
01:22:47,270 --> 01:22:51,700
Má propojený seznam, který v ideálním případě
by měla být co nejkratší.

1714
01:22:51,700 --> 01:22:54,364
A to není samozřejmé řešení.

1715
01:22:54,364 --> 01:22:57,280
Ve skutečnosti, hodně z jemného doladění
, co se děje pod kapotou, když

1716
01:22:57,280 --> 01:22:59,654
provádění těchto druhů
sofistikované datové struktury

1717
01:22:59,654 --> 01:23:01,640
je to, co je správné
Délka pole?

1718
01:23:01,640 --> 01:23:03,250
Jaká je správná hash funkce?

1719
01:23:03,250 --> 01:23:04,830
Jak se vám uložení věcí do paměti?

1720
01:23:04,830 --> 01:23:07,249
>> Ale uvědomuji, jak rychle
tento druh diskuse

1721
01:23:07,249 --> 01:23:10,540
stupňoval, a to buď tak daleko, že je to trochu
of nad hlavou v tomto bodě, který

1722
01:23:10,540 --> 01:23:11,360
je v pořádku.

1723
01:23:11,360 --> 01:23:18,820
Ale my jsme začali, odvolání, se skutečně
něco, co low-level a elektronické.

1724
01:23:18,820 --> 01:23:20,819
A tak to zase je to
Téma abstrakce,

1725
01:23:20,819 --> 01:23:23,610
kde jakmile začnete brát za
samozřejmost, OK, mám tu to--

1726
01:23:23,610 --> 01:23:26,680
fyzické paměti, OK, to mám každý
fyzické umístění má adresu,

1727
01:23:26,680 --> 01:23:29,910
OK, já to mám, můžu reprezentovat
tyto adresy jsou arrows--

1728
01:23:29,910 --> 01:23:34,650
můžete velmi rychle začít mít
sofistikovanější konverzace, které

1729
01:23:34,650 --> 01:23:38,360
nakonec se zdá, že nám umožňuje
řešit problémy, jako je vyhledávání

1730
01:23:38,360 --> 01:23:41,620
a třídění efektivněji.

1731
01:23:41,620 --> 01:23:44,190
A buďte ujištěni, too--
protože myslím, že to

1732
01:23:44,190 --> 01:23:48,700
je nejhlubší jsme šli do některé
z těchto témat CS proper-- my jsme

1733
01:23:48,700 --> 01:23:51,880
provedeno v den a půl na to
bod, co byste mohli dělat více než obvykle

1734
01:23:51,880 --> 01:23:55,520
Průběh osm týdnů v semestru.

1735
01:23:55,520 --> 01:23:59,670
>> Jakékoli otázky týkající se tito?

1736
01:23:59,670 --> 01:24:01,100
Ne?

1737
01:24:01,100 --> 01:24:01,940
Dobře.

1738
01:24:01,940 --> 01:24:05,610
No, proč ne my pozastavit tam,
spustit oběd několik minut dříve,

1739
01:24:05,610 --> 01:24:07,052
pokračovat v jen asi hodinu?

1740
01:24:07,052 --> 01:24:08,760
A budu prodlévat pro
trochu otázkami.

1741
01:24:08,760 --> 01:24:11,343
Pak budu muset jít
trvat několik hovory pouze v případě, že je v pořádku.

1742
01:24:11,343 --> 01:24:15,000
Budu zapnout nějakou hudbu do té doby,
ale oběd by měl být za rohem.

1743
01:24:15,000 --> 01:24:17,862