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

2
00:00:00,030 --> 00:00:00,460
>> DAVID Malan: V redu.

3
00:00:00,460 --> 00:00:01,094
Mi smo nazaj.

4
00:00:01,094 --> 00:00:04,260
Torej, v tem segmentu o programiranju, kaj
Mislil sem, da bi naredil je mešanica stvari.

5
00:00:04,260 --> 00:00:06,340
Ena, narediti malo
nečesa hands-on,

6
00:00:06,340 --> 00:00:08,690
čeprav z uporabo bolj igriv
programiranje environment--

7
00:00:08,690 --> 00:00:11,620
tisti, ki je demonstrativen od
natanko vrste idej

8
00:00:11,620 --> 00:00:14,220
smo se pogovarjali o tem,
ampak malo bolj formalno.

9
00:00:14,220 --> 00:00:18,200
Dva, pogled na nekatere
bolj tehnične načine

10
00:00:18,200 --> 00:00:21,520
da bi programer dejansko rešiti
težave, kot so, ki išče težave

11
00:00:21,520 --> 00:00:24,530
da smo pogledal, preden
tudi bolj temeljito

12
00:00:24,530 --> 00:00:26,020
zanimiv problem razvrščanja.

13
00:00:26,020 --> 00:00:28,840
>> Pravkar smo prevzela od zaslužiti iti
da je bila ta imenik razporejene,

14
00:00:28,840 --> 00:00:31,980
ampak da sam je pravzaprav nekakšen
Težko problem z veliko različnih načinov

15
00:00:31,980 --> 00:00:32,479
za njegovo rešitev.

16
00:00:32,479 --> 00:00:34,366
Tako bomo uporabili kot ti
razred težav

17
00:00:34,366 --> 00:00:36,740
Predstavnik stvari,
lahko rešili na splošno.

18
00:00:36,740 --> 00:00:38,980
In potem bomo govorili
pa v nekaterih podrobnostih, kaj

19
00:00:38,980 --> 00:00:42,360
so ti podatki structures--
luksuznih načinov kot povezanih seznamov

20
00:00:42,360 --> 00:00:46,290
in hash tabele in drevesa, ki
programer bi dejansko

21
00:00:46,290 --> 00:00:48,890
uporabo in splošno uporabo
na tabli slikati

22
00:00:48,890 --> 00:00:51,840
sliko o tem, kaj on ali ona
predvideva za izvajanje

23
00:00:51,840 --> 00:00:52,980
nekatere kos programske opreme.

24
00:00:52,980 --> 00:00:55,130
>> Torej, kaj je naredil roke-na delu prvi.

25
00:00:55,130 --> 00:01:00,090
Torej le dobili svoje roke umazane s
okolju imenovane scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
To je orodje, ki ga uporabljamo
V naši dodiplomski razredu.

27
00:01:02,636 --> 00:01:04,510
Čeprav je bilo načrtovano
za otroke, stare 12 let in več,

28
00:01:04,510 --> 00:01:07,570
smo ga uporabili za up
del tega zelo malo

29
00:01:07,570 --> 00:01:10,020
saj je lepo, zabavno
grafični način učenja

30
00:01:10,020 --> 00:01:12,160
nekaj malega o programiranju.

31
00:01:12,160 --> 00:01:17,600
Torej glavo na tem URL-ju, kjer vas
bi morali videti stran, prav takšen,

32
00:01:17,600 --> 00:01:23,330
in gredo naprej in kliknite
Pridružite praske na zgornjem desnem kotu

33
00:01:23,330 --> 00:01:28,300
in izberite uporabniško ime in
geslo in na koncu dobili 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
Mislil sem, da bi to uporabili kot
priložnost najprej pokazati to.

37
00:01:34,665 --> 00:01:39,120
Vprašanje je prišel med odmorom
o tem, kaj koda dejansko izgleda.

38
00:01:39,120 --> 00:01:41,315
In sva se pogovarjala
med odmorom o C,

39
00:01:41,315 --> 00:01:45,060
v particular-- še zlasti
nižja stopnja v starejšem jeziku.

40
00:01:45,060 --> 00:01:47,750
In sem naredil na hitro
Google iskanje, da bi našli številko C

41
00:01:47,750 --> 00:01:51,574
za binarno iskanje, algoritem, ki smo
uporablja za iskanje, da je telefonski imenik prej.

42
00:01:51,574 --> 00:01:54,240
To še posebej primer, seveda,
ne išče telefonski imenik.

43
00:01:54,240 --> 00:01:57,840
Samo išče cel kup
Številke v spominu računalnika.

44
00:01:57,840 --> 00:02:01,000
Ampak, če bi rad samo dobil vizualno
občutek za kaj dejansko programiranje

45
00:02:01,000 --> 00:02:05,370
jezik Izgleda, da izgleda
malo kaj takega.

46
00:02:05,370 --> 00:02:09,759
Torej, to je približno 20-plus,
30 ali tako vrstic kode,

47
00:02:09,759 --> 00:02:12,640
ampak pogovor smo
so ob več kot premoru

48
00:02:12,640 --> 00:02:16,000
je o tem, kako to dejansko
dobi morphed v ničel in enic

49
00:02:16,000 --> 00:02:19,200
in če ne moreš vrniti, da
obdelavo in gredo iz ničel in enic

50
00:02:19,200 --> 00:02:20,210
nazaj na kodo.

51
00:02:20,210 --> 00:02:22,620
>> Žal, proces
je tako transformativno

52
00:02:22,620 --> 00:02:24,890
da je veliko lažje reči kot narediti.

53
00:02:24,890 --> 00:02:29,400
Šel sem naprej in dejansko obrnil
ta program, Binary Search,

54
00:02:29,400 --> 00:02:32,700
v ničel in enic s sprejetjem
program, imenovan prevajalnik, da sem

55
00:02:32,700 --> 00:02:34,400
zgodi, da so tukaj prav na mojem Mac.

56
00:02:34,400 --> 00:02:37,850
In če pogledaš na zaslon
tukaj, se posebej osredotoča

57
00:02:37,850 --> 00:02:43,520
na teh srednjih šest stolpcev le,
boste videli samo ničle in narave.

58
00:02:43,520 --> 00:02:48,290
In to so ničle in tiste, ki
sestaviti točno to iščejo program.

59
00:02:48,290 --> 00:02:53,720
>> In tako je vsak kos pet bitov,
vsak bajt ničel in enic tukaj,

60
00:02:53,720 --> 00:02:57,310
predstavljajo nekaj navodil
tipično znotraj računalnika.

61
00:02:57,310 --> 00:03:00,730
In v resnici, če ste slišali
marketing slogan "Intel znotraj" - da,

62
00:03:00,730 --> 00:03:04,610
seveda, samo pomeni, da imate
Intel CPU ali možganov notranjosti računalnika.

63
00:03:04,610 --> 00:03:08,000
In kaj to pomeni, da je CPU je
da imate nabor ukazov,

64
00:03:08,000 --> 00:03:08,840
tako rekoč.

65
00:03:08,840 --> 00:03:11,620
>> Vsak CPU na svetu, veliko
jih je Intel v teh dneh,

66
00:03:11,620 --> 00:03:13,690
razume končna
Število navodil.

67
00:03:13,690 --> 00:03:18,690
In ta navodila so tako nizki ravni
kot dodatek teh dveh številk skupaj,

68
00:03:18,690 --> 00:03:22,560
množijo teh dveh številk skupaj,
premakniti ta podatek od tukaj

69
00:03:22,560 --> 00:03:27,340
tukaj v spomin, razen tega
informacije tukaj, da tukaj v spomin,

70
00:03:27,340 --> 00:03:32,200
in tako forth-- tako zelo, zelo
nizko raven, skoraj elektronske podrobnosti.

71
00:03:32,200 --> 00:03:34,780
Ampak s tistimi, matematična
operacije skupaj

72
00:03:34,780 --> 00:03:37,410
s tem, kar smo razpravljali prej,
upodobitev podatkov

73
00:03:37,410 --> 00:03:40,450
kot ničel in enic, lahko
ste zgraditi vse

74
00:03:40,450 --> 00:03:44,180
da lahko računalnik storiti danes, ali
je tekstovni, grafični, glasbene,

75
00:03:44,180 --> 00:03:45,580
ali kako drugače.

76
00:03:45,580 --> 00:03:49,450
>> Torej, to je zelo enostavno priti
izgubil v plevela hitro.

77
00:03:49,450 --> 00:03:52,150
In tam je veliko
sintaktične izzivi

78
00:03:52,150 --> 00:03:56,630
pri čemer, če bi najenostavnejši,
neumna tipkarskih napak nič programa

79
00:03:56,630 --> 00:03:57,860
bo delo sploh.

80
00:03:57,860 --> 00:04:00,366
In tako namesto z uporabo
jezik kot C zjutraj,

81
00:04:00,366 --> 00:04:02,240
Mislil sem, da bi bilo
bolj zabavno dejansko ne

82
00:04:02,240 --> 00:04:04,840
nekaj bolj vizualna, ki
medtem ko je namenjen za otroke

83
00:04:04,840 --> 00:04:08,079
je pravzaprav popolna manifestacija
z dejansko programiranja

84
00:04:08,079 --> 00:04:10,370
language-- slučajno
uporaba slik namesto besedila

85
00:04:10,370 --> 00:04:11,710
da predstavljajo te ideje.

86
00:04:11,710 --> 00:04:15,470
>> Torej, ko si res imeti
račun na scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
kliknite gumb Ustvari
na vrhu levi strani.

88
00:04:21,070 --> 00:04:24,620
In bi morali videti okolje, kot
tisti sem, da vidijo na mojem zaslonu

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

90
00:04:26,310 --> 00:04:29,350
In bomo porabili le malo
malo časa igrajo tukaj.

91
00:04:29,350 --> 00:04:34,080
Poglejmo, če ne moremo vsi rešiti nekatere
Težave skupaj na naslednji način.

92
00:04:34,080 --> 00:04:39,420
>> Torej, kaj boste videli v tem
environment-- in dejansko pusti

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

94
00:04:40,050 --> 00:04:42,680
Ali kdo ni tukaj?

95
00:04:42,680 --> 00:04:45,070
Ne tukaj?

96
00:04:45,070 --> 00:04:45,800
V REDU.

97
00:04:45,800 --> 00:04:49,030
Torej, naj omenim nekaj
Značilnosti tega okolja.

98
00:04:49,030 --> 00:04:55,024
>> Torej v zgornjem levem kotu zaslona, ​​smo
imajo stopnjo na praske, tako rekoč.

99
00:04:55,024 --> 00:04:57,440
Scratch ni le ime
tega programskega jezika;

100
00:04:57,440 --> 00:05:00,356
to je tudi ime mačke, ki
vidite privzeto tam v oranžni barvi.

101
00:05:00,356 --> 00:05:02,160
Je na odru, zato
podobno kot sem opisal

102
00:05:02,160 --> 00:05:05,770
želva prej kot je z
pravokotne bele okolje krovu.

103
00:05:05,770 --> 00:05:09,800
Ta mačke svet je omejena v celoti
v ta pravokotnik do vrha tam.

104
00:05:09,800 --> 00:05:12,210
>> Medtem, na desni
hand side tukaj, to je

105
00:05:12,210 --> 00:05:15,610
samo skripte prostora,
nepopisan list, če bo.

106
00:05:15,610 --> 00:05:18,590
To je, če bomo napisali
naši programi v samo trenutek.

107
00:05:18,590 --> 00:05:22,935
In gradnikov, ki jih mora
uporabite za pisanje tega program-- sestavljanko

108
00:05:22,935 --> 00:05:25,310
kosov, če will-- so
tistih, ki tukaj v sredini,

109
00:05:25,310 --> 00:05:27,500
in oni so razvrščeni
s funkcionalnostjo.

110
00:05:27,500 --> 00:05:31,000
Tako, na primer, bom šel naprej
in pokazati vsaj enega od njih.

111
00:05:31,000 --> 00:05:33,690
Bom, da gredo naprej in kliknite
Nadzor kategorija do vrha.

112
00:05:33,690 --> 00:05:35,720
>> Torej, to so kategorije do vrha.

113
00:05:35,720 --> 00:05:39,410
Bom kliknite kategorijo upravljanje.

114
00:05:39,410 --> 00:05:44,020
Namesto tega bom kliknite Dogodki
kategorija, zelo prvi up top.

115
00:05:44,020 --> 00:05:47,790
In, če bi želeli slediti skupaj tudi
kot smo to naredili, ste zelo dobrodošli.

116
00:05:47,790 --> 00:05:52,180
Bom kliknite in povlecite to
Prvi je, "ko je zelena zastava kliknili."

117
00:05:52,180 --> 00:05:58,410
In potem bom spusti samo
približno na vrhu mojih praznih tablice.

118
00:05:58,410 --> 00:06:01,450
>> In kaj je lepo o Scratch
je, da je to puzzle kos, ko

119
00:06:01,450 --> 00:06:04,560
prepletena z drugimi sestavljanke
kosov, bo naredil dobesedno

120
00:06:04,560 --> 00:06:06,460
kaj ti kosov sestavljanke pravijo storiti.

121
00:06:06,460 --> 00:06:09,710
Tako, na primer, Scratch je prav
Sedaj sredi njegovega sveta.

122
00:06:09,710 --> 00:06:14,660
Bom, da gredo naprej in izberite
Zdaj, recimo, kategorija Predlog,

123
00:06:14,660 --> 00:06:18,000
Če želite, da storijo
nam je isti Motion kategorijo.

124
00:06:18,000 --> 00:06:20,430
In zdaj opazili imam celoto
kup koščke tukaj

125
00:06:20,430 --> 00:06:23,370
da, še enkrat, nekako to, kar pravijo.

126
00:06:23,370 --> 00:06:28,110
In bom, da gredo naprej in povlecite in
spusti premikanje blok prav tukaj.

127
00:06:28,110 --> 00:06:31,860
>> In opazili, da se takoj, ko dobiš
blizu dna "zeleno zastavo

128
00:06:31,860 --> 00:06:34,580
kliknili "gumb, obvestilo
kako se pojavi bela črta,

129
00:06:34,580 --> 00:06:36,950
kot da je skoraj
magnetna, želi iti tja.

130
00:06:36,950 --> 00:06:43,070
Samo izpustil in bo snap
skupaj in bodo oblike ujemajo.

131
00:06:43,070 --> 00:06:46,620
In zdaj si lahko morda kmalu
Verjetno kam gremo s tem.

132
00:06:46,620 --> 00:06:51,570
>> Če pogledaš v fazi Scratch
sem in poglej na vrhu je,

133
00:06:51,570 --> 00:06:55,142
boste videli rdečo luč,
stop znak in zeleno zastavo.

134
00:06:55,142 --> 00:06:57,100
In bom, da gredo naprej
in gledal moje screen--

135
00:06:57,100 --> 00:06:58,460
za trenutek, če bi lahko.

136
00:06:58,460 --> 00:07:01,960
Bom kliknite
zeleno zastavo zdaj,

137
00:07:01,960 --> 00:07:07,850
in se je preselil, kar se zdi, da je 10 korakov
ali 10 točk, 10 pik, na zaslonu.

138
00:07:07,850 --> 00:07:13,390
>> In zato ni to zanimivo,
vendar naj predlaga

139
00:07:13,390 --> 00:07:17,440
ne da bi to poučevanje, samo
uporabo lastnih svoje intuition-- Let

140
00:07:17,440 --> 00:07:22,560
jaz predlagam, da ugotovimo, kako
da blok za sprehod pravico off fazi.

141
00:07:22,560 --> 00:07:28,700
So mu naredili prostor za desno stran
zaslon, vse tja v desno.

142
00:07:28,700 --> 00:07:32,200
Naj vam trenutek
ali tako boriti s tem.

143
00:07:32,200 --> 00:07:37,681
Morda boste želeli, da pogled
na druge kategorije blokov.

144
00:07:37,681 --> 00:07:38,180
V redu.

145
00:07:38,180 --> 00:07:41,290
Torej, samo da povzamem, ko imamo
zelena zastava kliknete tukaj

146
00:07:41,290 --> 00:07:44,850
in premikanje 10 korakov je
samo navodila, vsakič, ko sem

147
00:07:44,850 --> 00:07:46,720
kliknite zeleno zastavo, kaj se dogaja?

148
00:07:46,720 --> 00:07:50,070
No, to je tekmovanje v teku svoj program.

149
00:07:50,070 --> 00:07:52,450
Tako sem lahko to naredil
morda 10-krat ročno,

150
00:07:52,450 --> 00:07:55,130
vendar to meni malo
bit hekerske, tako rekoč,

151
00:07:55,130 --> 00:07:57,480
pri čemer Nisem
reševanju problema.

152
00:07:57,480 --> 00:08:00,530
Jaz sem samo enkrat poskušam in
znova in znova in znova

153
00:08:00,530 --> 00:08:03,180
dokler sem nekako po naključju
dosegli direktive

154
00:08:03,180 --> 00:08:05,560
da sem določeno, da se doseže prej.

155
00:08:05,560 --> 00:08:08,200
>> Vendar vemo iz naše
psevdokoda prej, da obstaja

156
00:08:08,200 --> 00:08:11,870
ta pojem v programiranju petlji,
tem znova in znova nekaj.

157
00:08:11,870 --> 00:08:14,888
In tako sem videl, da je kup vas
dosegla za kaj puzzle kos?

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

159
00:08:17,870 --> 00:08:18,730
Ponavljajte, dokler.

160
00:08:18,730 --> 00:08:21,400
Tako smo lahko nekaj storiti
kot ponavljati, dokler.

161
00:08:21,400 --> 00:08:23,760
In kaj si ponoviti, dokler točno?

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

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

164
00:08:28,540 --> 00:08:31,974
In mi gredo z eno, ki je
nekoliko enostavnejši za trenutek.

165
00:08:31,974 --> 00:08:33,140
Naj gredo naprej in to.

166
00:08:33,140 --> 00:08:35,559
Upoštevajte, da se boste morda morali
odkrili pod nadzor,

167
00:08:35,559 --> 00:08:38,409
je to ponavljanje blok, ki
ni videti, kot da je to velik.

168
00:08:38,409 --> 00:08:41,039
Tam ni veliko prostora v
med tema dvema rumenimi črtami.

169
00:08:41,039 --> 00:08:43,539
Toda, kot nekateri od vas morda
opazili, če ste povleci in spusti,

170
00:08:43,539 --> 00:08:45,150
opazili, kako raste zapolniti obliko.

171
00:08:45,150 --> 00:08:46,274
>> In lahko celo strpati več.

172
00:08:46,274 --> 00:08:48,670
To bo samo še naraščal, če
povlečete in lebdijo nad njim.

173
00:08:48,670 --> 00:08:51,110
In ne vem, kaj je
Najboljši tukaj, zato naj

174
00:08:51,110 --> 00:08:54,760
me vsaj ponovi petkrat, za
primer, nato pa pojdite nazaj na oder

175
00:08:54,760 --> 00:08:56,720
in kliknite na zeleno zastavo.

176
00:08:56,720 --> 00:08:59,110
In sedaj opazili, da to ni čisto tam.

177
00:08:59,110 --> 00:09:02,400
>> Zdaj ste nekateri predlagani,
Victoria ravno ni, ponovite 10-krat.

178
00:09:02,400 --> 00:09:05,140
In ki na splošno ne
spraviti vso pot,

179
00:09:05,140 --> 00:09:10,510
vendar ne bi bilo treba bolj robusten
Tako kot samovoljno ugotoviti

180
00:09:10,510 --> 00:09:12,640
koliko se premika narediti?

181
00:09:12,640 --> 00:09:17,680
Kaj bi lahko bil boljši blok
kot ponovitev 10-krat?

182
00:09:17,680 --> 00:09:20,380
>> Ja, zakaj ne stori vedno kaj?

183
00:09:20,380 --> 00:09:24,390
In zdaj naj mi premakniti ta kos sestavljanke
notri in se znebite tega.

184
00:09:24,390 --> 00:09:28,300
Zdaj opazili, ne glede na to kje Scratch
začne, gre do roba.

185
00:09:28,300 --> 00:09:30,700
In na srečo MIT,
ki naredi nič, samo

186
00:09:30,700 --> 00:09:33,190
poskrbi, da on nikoli
popolnoma izgine.

187
00:09:33,190 --> 00:09:35,360
Vedno lahko zgrabi svoj rep.

188
00:09:35,360 --> 00:09:37,680
>> In samo intuitivno,
zakaj je premikati?

189
00:09:37,680 --> 00:09:38,892
Kaj se dogaja tukaj?

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

191
00:09:41,440 --> 00:09:43,824
Zdi se, da so se ustavili, vendar
potem, če sem se poberem in povlecite

192
00:09:43,824 --> 00:09:45,240
ga še naprej želijo, da gredo tja.

193
00:09:45,240 --> 00:09:46,123
Zakaj je tako?

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

195
00:09:51,610 --> 00:09:54,360
Resnično, računalnik je dobesedno
bo to, kar je povedal, da storiti.

196
00:09:54,360 --> 00:09:58,380
Torej, če ste to povedali prej storijo
naslednja stvar za vedno, gremo 10 korakov,

197
00:09:58,380 --> 00:10:01,860
to se dogaja, da se dogaja in bo
dokler ne zadeti rdečo stop znak

198
00:10:01,860 --> 00:10:04,620
in zaustavitev programa v celoti.

199
00:10:04,620 --> 00:10:06,610
>> Torej, tudi če ni
To naredite tako, da bi lahko, kako sem

200
00:10:06,610 --> 00:10:09,510
da Scratch potezo hitreje
po zaslonu?

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

202
00:10:12,060 --> 00:10:13,280
Več korakov, kajne?

203
00:10:13,280 --> 00:10:15,710
Torej, namesto da delaš 10
v času, zakaj ne bi

204
00:10:15,710 --> 00:10:20,100
iti naprej in ga spremeniti to--
kaj bi propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Torej, zdaj bom kliknite zeleno
zastavo, in res, gre zelo hitro.

206
00:10:24,410 --> 00:10:27,180
>> In to je seveda samo
manifestacija animacije.

207
00:10:27,180 --> 00:10:28,060
Kaj je animacija?

208
00:10:28,060 --> 00:10:33,090
To je samo prikazuje človeško a
cel kup fotografij, res,

209
00:10:33,090 --> 00:10:34,160
zelo, zelo hitro.

210
00:10:34,160 --> 00:10:36,500
In zato, če smo pravkar povedali
ga premakniti več korakov,

211
00:10:36,500 --> 00:10:39,750
smo le imajo učinek je, da
Sprememba kje je na zaslonu

212
00:10:39,750 --> 00:10:42,900
vse hitreje na enota časa.

213
00:10:42,900 --> 00:10:46,454
>> Zdaj naslednji izziv, ki sem ga predlagal
je, da so mu premetavati čez rob.

214
00:10:46,454 --> 00:10:49,120
In ne da bi vedel, kaj puzzle
kosov exist-- ker je v redu

215
00:10:49,120 --> 00:10:53,030
Če ne boste dobili na
faza challenge-- kaj

216
00:10:53,030 --> 00:10:54,280
hočeš narediti intuitivno?

217
00:10:54,280 --> 00:10:58,030
Kako bi morali ga Odklonijo nazaj in
tja med levo in desno?

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

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

220
00:11:03,810 --> 00:11:05,680
Torej potrebujemo nekakšen
stanja, in

221
00:11:05,680 --> 00:11:09,710
Zdi se, da imajo Pogojniki, tako
rekoč, pod kategorijo nadzor.

222
00:11:09,710 --> 00:11:14,110
Kateri od teh blokov
bomo verjetno želeli?

223
00:11:14,110 --> 00:11:15,200
Ja, mogoče ", če je, potem."

224
00:11:15,200 --> 00:11:18,780
Tako opazili, da med rumenih blokov
imamo tukaj, je ta "če"

225
00:11:18,780 --> 00:11:23,920
ali to ", če še" blok, ki bo
nam omogočajo, da bi odločitev, da to storijo

226
00:11:23,920 --> 00:11:25,000
ali za to.

227
00:11:25,000 --> 00:11:27,380
celo in lahko gnezdo
narediti več stvari.

228
00:11:27,380 --> 00:11:34,910
Ali pa, če še niste šli tukaj,
pojdi na kategorijo Sensing

229
00:11:34,910 --> 00:11:39,612
in-- da vidimo, če je tukaj.

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

231
00:11:43,050 --> 00:11:52,050
>> Torej, kaj blok bi bil lahko koristen tukaj
odkriti, če je to z odra?

232
00:11:52,050 --> 00:11:56,740
Ja, opazili, da nekatere od teh blokov
lahko parametriziramo, tako rekoč.

233
00:11:56,740 --> 00:12:00,706
Jih lahko nekako meri ne
za razliko od HTML včeraj z atributi,

234
00:12:00,706 --> 00:12:03,330
kadar ti atributi vrste
prilagodite obnašanje oznako.

235
00:12:03,330 --> 00:12:08,880
Prav tukaj, lahko zgrabi to dotikanje
blok in spremembe in vprašati,

236
00:12:08,880 --> 00:12:11,500
ste dotika z miško
Kazalec kot kazalca

237
00:12:11,500 --> 00:12:13,250
ali ste dotika rob?

238
00:12:13,250 --> 00:12:15,210
>> Torej me noter in to.

239
00:12:15,210 --> 00:12:18,130
Bom pomanjšati za trenutek.

240
00:12:18,130 --> 00:12:21,320
Naj zgrabi ta kos sestavljanke
tukaj je to puzzle kos tem,

241
00:12:21,320 --> 00:12:24,570
in bom packarije
jih za nekaj trenutkov.

242
00:12:24,570 --> 00:12:27,620
Bom premakniti to,
spremeni to dotika roba,

243
00:12:27,620 --> 00:12:38,590
in bom gibanja to.

244
00:12:38,590 --> 00:12:40,490
Torej, tukaj je nekaj sestavin.

245
00:12:40,490 --> 00:12:42,570
Mislim, da imam vse, kar hočem.

246
00:12:42,570 --> 00:12:47,710
>> Bi kdo rad predlagal, kako
mogoče povezati ti morda vrha do dna

247
00:12:47,710 --> 00:12:52,020
da bi rešili problem z
Scratch premik od desne proti levi, da pravica do

248
00:12:52,020 --> 00:12:57,020
leve proti desne na levo, vsak
Čas samo odbijajo steno?

249
00:12:57,020 --> 00:12:58,050
Kaj želite narediti?

250
00:12:58,050 --> 00:13:01,097
Kateri blok naj priključite na
"Ko je zelena zastava kliknil prvi"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, začnimo z "večno".

253
00:13:06,200 --> 00:13:07,170
Kaj se dogaja v notranjosti sledi?

254
00:13:07,170 --> 00:13:10,290
Nekdo drug.

255
00:13:10,290 --> 00:13:11,850
OK, gremo korake.

256
00:13:11,850 --> 00:13:12,350
V redu.

257
00:13:12,350 --> 00:13:14,470
In kaj potem?

258
00:13:14,470 --> 00:13:15,120
Torej if.

259
00:13:15,120 --> 00:13:17,720
In opazil, čeprav je videti
stisnjena skupaj tesno,

260
00:13:17,720 --> 00:13:19,500
to bo samo rasla izpolniti.

261
00:13:19,500 --> 00:13:21,500
To bo samo skoči, kje sem ga želim.

262
00:13:21,500 --> 00:13:25,920
>> In kaj sem dal med
if in potem?

263
00:13:25,920 --> 00:13:27,180
Verjetno ", če se dotika roba."

264
00:13:27,180 --> 00:13:31,800
In obvestilo, še enkrat, to je prevelika
za njo, vendar se bo hkrati izpolniti.

265
00:13:31,800 --> 00:13:35,002
Nato pa 15 stopinj?

266
00:13:35,002 --> 00:13:35,710
Koliko stopinj?

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

268
00:13:38,800 --> 00:13:41,196
Ja, 180 se vrti
me vse ravno obratno.

269
00:13:41,196 --> 00:13:42,570
Torej, da vidimo, če imam to pravico.

270
00:13:42,570 --> 00:13:43,930
Naj pomanjšavo.

271
00:13:43,930 --> 00:13:45,130
>> Naj povlecite blok za ukrepanje.

272
00:13:45,130 --> 00:13:50,030
Tako je malo popačena
zdaj, ampak to je v redu.

273
00:13:50,030 --> 00:13:52,231
Kako naj ga ponastaviti enostavno?

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

275
00:13:59,879 --> 00:14:01,045
Bom malo goljufati.

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

277
00:14:04,074 --> 00:14:05,990
Tako da sem dodal še eno
blok, samo da bo jasno.

278
00:14:05,990 --> 00:14:08,424
Hočem, da točka 90 stopinj
na desni privzeto,

279
00:14:08,424 --> 00:14:10,840
tako da sem le, da bo mu povedati
za to programsko.

280
00:14:10,840 --> 00:14:11,632
In gremo.

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

282
00:14:14,740 --> 00:14:15,740
Zdi se, da smo to naredili.

283
00:14:15,740 --> 00:14:19,980
To je malo čudno, ker
on hodi z glavo navzdol.

284
00:14:19,980 --> 00:14:21,250
Recimo, da je hrošč.

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

286
00:14:22,120 --> 00:14:27,320
Bug je napaka v programu, a
logične napake, da sem človek, ki.

287
00:14:27,320 --> 00:14:28,985
Zakaj se dogaja narobe?

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

289
00:14:33,560 --> 00:14:35,250
Ali MIT zajebal, ali sem?

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

291
00:14:38,840 --> 00:14:42,550
>> Ja, mislim, da ni MIT je
napake. Dali so mi kos sestavljanke

292
00:14:42,550 --> 00:14:44,970
ki pravi, da zavrtite nekaj stopinj.

293
00:14:44,970 --> 00:14:47,672
In na predlog Victoria,
Jaz obrača za 180 stopinj,

294
00:14:47,672 --> 00:14:48,880
ki je prav intuicija.

295
00:14:48,880 --> 00:14:53,700
Toda obrača za 180 stopinj dobesedno
pomeni obrača za 180 stopinj,

296
00:14:53,700 --> 00:14:55,860
in to ni res
kaj hočem, očitno.

297
00:14:55,860 --> 00:14:58,026
Ker vsaj, da je v
Ta dvodimenzionalni svet,

298
00:14:58,026 --> 00:15:00,740
tako struženje se v resnici dogaja
da ga flip na glavo.

299
00:15:00,740 --> 00:15:04,030
>> Verjetno želite uporabiti kakšen blok
namesto tega, glede na to, kar vidite tu?

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

301
00:15:11,890 --> 00:15:14,790
Kako bi lahko to popravimo?

302
00:15:14,790 --> 00:15:18,380
Ja, tako da bi lahko kazal
v obratni smeri.

303
00:15:18,380 --> 00:15:22,300
In pravzaprav tudi, da je
ne bo dovolj,

304
00:15:22,300 --> 00:15:26,410
saj lahko le težko koda
da kaže levo ali desno.

305
00:15:26,410 --> 00:15:27,920
>> Veš, kaj lahko naredimo?

306
00:15:27,920 --> 00:15:30,160
Izgleda, da imamo
udobje blok tukaj.

307
00:15:30,160 --> 00:15:32,987
Če bi povečavo, glej
nekaj, kar je všeč tukaj?

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

309
00:15:36,120 --> 00:15:40,020
Torej izgleda, da ima MIT
abstrakcija zgradili tukaj.

310
00:15:40,020 --> 00:15:45,440
Zdi se, da je enakovredna Ta blok
na kateri drugi bloki, množina?

311
00:15:45,440 --> 00:15:49,510
>> Zdi se, da je enakovredna tale blok
s tem celotno trio blokov

312
00:15:49,510 --> 00:15:50,880
da imamo tukaj.

313
00:15:50,880 --> 00:15:54,670
Tako se izkaže, da sem lahko poenostavi moje
Program, ki ga znebi vseh, ki

314
00:15:54,670 --> 00:15:58,270
in samo da to tukaj.

315
00:15:58,270 --> 00:16:01,620
In zdaj je še vedno malo
Otroški voziček, in to je v redu za zdaj.

316
00:16:01,620 --> 00:16:03,370
Bomo pustimo, da se.

317
00:16:03,370 --> 00:16:06,000
Ampak moj program je celo
enostavnejši in tudi to,

318
00:16:06,000 --> 00:16:09,060
bi bil predstavnik
za zadetek v programming--

319
00:16:09,060 --> 00:16:13,430
je idealno, da kodo kot
preprost, kot kompaktna kot je mogoče,

320
00:16:13,430 --> 00:16:15,650
pri čemer pa so, kot je
berljivi kot je mogoče.

321
00:16:15,650 --> 00:16:20,310
Vi ne želite, da bi bilo tako jedrnat
da je težko razumeti.

322
00:16:20,310 --> 00:16:22,826
>> Ampak opazil sem zamenjati
tri bloke z enim,

323
00:16:22,826 --> 00:16:24,200
in to je verjetno dobra stvar.

324
00:16:24,200 --> 00:16:27,280
Sem odvzete stran pojem
preverjanja, ali ste

325
00:16:27,280 --> 00:16:29,120
na robu z enim blokom.

326
00:16:29,120 --> 00:16:31,520
Zdaj pa se lahko zabavajo s tem, v resnici.

327
00:16:31,520 --> 00:16:35,790
To ne doda toliko
intelektualno vrednost, vendar igriv vrednost.

328
00:16:35,790 --> 00:16:39,730
Bom, da gredo naprej
in zgrabi ta zvok tukaj.

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

330
00:16:42,900 --> 00:16:46,420
Torej naj grem naprej, in naj me
zaustavitev programa za trenutek.

331
00:16:46,420 --> 00:16:52,070
Bom za snemanje naslednje,
omogoča dostop do mojega mikrofona.

332
00:16:52,070 --> 00:16:53,181
>> Gremo.

333
00:16:53,181 --> 00:16:53,680
Auč.

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

335
00:16:58,710 --> 00:17:01,140
Pa poskusimo znova.

336
00:17:01,140 --> 00:17:02,279
Gremo.

337
00:17:02,279 --> 00:17:03,570
OK, sem posnel napačno stvar.

338
00:17:03,570 --> 00:17:04,580
Gremo.

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

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

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

342
00:17:08,800 --> 00:17:09,300
V redu.

343
00:17:09,300 --> 00:17:10,791
Zdaj se moram znebiti tega.

344
00:17:10,791 --> 00:17:11,290
V redu.

345
00:17:11,290 --> 00:17:13,950
>> Zdaj imam
Snemanje samo "Ouch."

346
00:17:13,950 --> 00:17:18,040
Torej, zdaj bom šel
naprej in pravijo temu "av".

347
00:17:18,040 --> 00:17:20,270
Bom šel nazaj
za moje skripte, in zdaj

348
00:17:20,270 --> 00:17:25,460
Obvestilo pa je to blok, ki se imenuje
predvajanje zvoka "mijav" ali predvajanje zvoka "av".

349
00:17:25,460 --> 00:17:28,920
Bom vleči to, in kje
naj dajo to za komični učinek?

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

351
00:17:31,740 --> 00:17:37,860
Ja, zdaj je vrsta
Otroški voziček, ker zdaj to block--

352
00:17:37,860 --> 00:17:42,050
opaziti, kako to ", če na robu,
bounce "je nekako samostojen.

353
00:17:42,050 --> 00:17:43,704
Torej moram popraviti to.

354
00:17:43,704 --> 00:17:44,870
Naj gredo naprej in to.

355
00:17:44,870 --> 00:17:48,630
Naj se znebite tega in nazaj
za naše izvirniku, bolj premišljeno

356
00:17:48,630 --> 00:17:49,870
funkcionalnost.

357
00:17:49,870 --> 00:18:01,080
Torej, "če se dotika roba, nato pa" hočem
vrteti, kot je predlagano Victoria,

358
00:18:01,080 --> 00:18:02,480
180 stopinj.

359
00:18:02,480 --> 00:18:05,497
In ne želim igrati
zvok "au" tam?

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

361
00:18:11,800 --> 00:18:15,580
>> Ja, opazili, da je zunaj
da rumena blok.

362
00:18:15,580 --> 00:18:17,680
Torej tudi to bi bilo
napako, vendar sem jo opazil.

363
00:18:17,680 --> 00:18:21,290
Tako bom, da ga povlečete tukaj,
in obvestilo zdaj je znotraj "če".

364
00:18:21,290 --> 00:18:24,250
Torej "če" je to neke
iz podobnega roke podobnih blot

365
00:18:24,250 --> 00:18:26,260
da bo le
to, kar je znotraj njega.

366
00:18:26,260 --> 00:18:30,216
Torej, zdaj, če sem pomanjšati na
tveganje 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: In
bo le večno.

370
00:18:39,910 --> 00:18:44,160
Zdaj pa samo, da pospeši stvari
sem, naj gredo naprej in odprli,

371
00:18:44,160 --> 00:18:50,460
kaj je say-- Naj gre za nekaj
moje stvari iz razreda.

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

373
00:18:53,000 --> 00:19:00,220
In mi odprla, recimo, to
ena je eden od naših učnih štipendistov

374
00:19:00,220 --> 00:19:01,500
nekaj let nazaj.

375
00:19:01,500 --> 00:19:04,732
Torej, nekateri od vas morda odpoklic
ta igra iz minulih dni,

376
00:19:04,732 --> 00:19:05,940
in to je dejansko izjemen.

377
00:19:05,940 --> 00:19:08,190
Čeprav smo storili
Najenostavnejši programov sedaj,

378
00:19:08,190 --> 00:19:09,980
kaj je razmisliti, kaj je to
dejansko izgleda.

379
00:19:09,980 --> 00:19:10,650
Naj hit igro.

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

381
00:19:14,210 --> 00:19:18,980
>> Torej, v tej igri, imamo
žaba, in z uporabo puščico keys--

382
00:19:18,980 --> 00:19:23,340
je potrebno večje korake, kot sem remember--
Imam nadzor nad tem žaba.

383
00:19:23,340 --> 00:19:29,630
In cilj je priti čez zaseden
cesta ne teče v avtomobile.

384
00:19:29,630 --> 00:19:34,735
In kaj je see-- če grem tukaj sem
morali počakati log, da se premaknete s.

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

386
00:19:38,130 --> 00:19:39,274
To počuti kot hrošč.

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

388
00:19:42,240 --> 00:19:43,495
To je neke vrste hrošča.

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

390
00:19:45,980 --> 00:19:46,480
V redu.

391
00:19:46,480 --> 00:19:51,550
Jaz sem na to tukaj,
tam, potem pa naprej

392
00:19:51,550 --> 00:19:54,100
bo, dokler ne dobiš vse
žabe na lilije blazinice.

393
00:19:54,100 --> 00:19:55,920
Zdaj to lahko videti
vse bolj zapletena,

394
00:19:55,920 --> 00:19:57,840
ampak poskusimo prodreti
to dol duševno

395
00:19:57,840 --> 00:20:00,040
in ustno v svojih blokih.

396
00:20:00,040 --> 00:20:03,910
Torej je verjetno puzzle
kos, ki ga še nismo videli

397
00:20:03,910 --> 00:20:07,440
ampak to je odziv na pritiske tipk,
za stvari, ki sem udaril po tipkovnici.

398
00:20:07,440 --> 00:20:11,660
>> Torej je verjetno nekakšna
blok, ki pravi, če ključ enaka navzgor,

399
00:20:11,660 --> 00:20:15,965
naredite nekaj z Scratch--
Mogoče je premakniti 10 korakov na ta način.

400
00:20:15,965 --> 00:20:20,240
Če je pritisnjena tipka, premaknite 10 korakov
na ta način, ali levo tipko, premakne 10 korakov

401
00:20:20,240 --> 00:20:21,710
na ta način, 10 korakov, ki.

402
00:20:21,710 --> 00:20:23,644
Sem jasno obrnil mačka v žabo.

403
00:20:23,644 --> 00:20:26,060
Torej, to je samo, če
kostum, kot Scratch klici it-- smo

404
00:20:26,060 --> 00:20:28,440
samo uvozili sliko žabe.

405
00:20:28,440 --> 00:20:29,570
>> Toda, kaj se dogaja?

406
00:20:29,570 --> 00:20:32,794
Katera druga vrstic kode,
kaj drugi kosov sestavljanke

407
00:20:32,794 --> 00:20:35,460
storil Blake, naše poučevanje kolegi,
uporabo v tem programu, očitno?

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

409
00:20:38,320 --> 00:20:42,730
Kaj je tako vse move--
kaj programiranje konstrukt?

410
00:20:42,730 --> 00:20:44,950
>> Predlog, sure-- tako
premakniti blok, zagotovo.

411
00:20:44,950 --> 00:20:49,330
In kaj je to poteza blok
notranjosti, najverjetneje?

412
00:20:49,330 --> 00:20:52,850
Ja, neke vrste zanke, morda
vedno blokira, morda ponovitev block--

413
00:20:52,850 --> 00:20:54,070
ponovite do bloka.

414
00:20:54,070 --> 00:20:57,330
In to je tisto, kar bi dnevnike in
lilija blazinice in vse ostalo poteza

415
00:20:57,330 --> 00:20:57,990
naprej in nazaj.

416
00:20:57,990 --> 00:21:00,270
To je samo dogaja v nedogled.

417
00:21:00,270 --> 00:21:03,180
>> Zakaj so nekateri avtomobili
gibljejo hitreje od drugih?

418
00:21:03,180 --> 00:21:06,607
Kaj je drugačnega teh programov?

419
00:21:06,607 --> 00:21:09,690
Ja, verjetno nekateri od njih so ob
več korakov naenkrat in nekateri od njih

420
00:21:09,690 --> 00:21:10,690
manj korakov naenkrat.

421
00:21:10,690 --> 00:21:14,670
In vizualni učinek
hitro v primerjavi s počasno.

422
00:21:14,670 --> 00:21:16,030
>> Kaj misliš, da se je zgodilo?

423
00:21:16,030 --> 00:21:19,700
Ko sem dobil žabo vso pot
čez cesto in reko

424
00:21:19,700 --> 00:21:23,560
na lilija pad, nekaj
Omembe vredno je zgodilo.

425
00:21:23,560 --> 00:21:26,540
Kaj se je zgodilo takoj, ko sem to naredil?

426
00:21:26,540 --> 00:21:27,210
Ustavil se je.

427
00:21:27,210 --> 00:21:29,680
Da žaba prekiniti in
Imam drugo žabo.

428
00:21:29,680 --> 00:21:33,155
Kaj konstrukt mora biti
tam uporabljajo, kaj funkcija?

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

430
00:21:36,020 --> 00:21:38,660
>> Ja, tako da je nekakšna
"Če" pogojujejo tam, preveč.

431
00:21:38,660 --> 00:21:41,909
In se izkaže out-- nismo videli this--
vendar pa druge bloke v tam, da

432
00:21:41,909 --> 00:21:45,300
Lahko rečem, če ste dotika
še ena stvar, na zaslonu,

433
00:21:45,300 --> 00:21:47,720
če ste se dotikajo lilija pad, "potem".

434
00:21:47,720 --> 00:21:50,810
In potem, da je, ko smo
da se bodo drugi žaba.

435
00:21:50,810 --> 00:21:54,969
Torej, čeprav je ta igra zagotovo
zelo dne, čeprav je na prvi pogled

436
00:21:54,969 --> 00:21:58,010
tam je tudi veliko dogaja on-- in Blake
ni bič to v dveh minutah

437
00:21:58,010 --> 00:22:00,390
verjetno je on več
ur ustvariti to igro

438
00:22:00,390 --> 00:22:03,850
temelji na njegovem spominu ali video posnetkov
različice minulih dni je od tega.

439
00:22:03,850 --> 00:22:07,940
Toda vse te malenkosti
bo na zaslonu v izolaciji

440
00:22:07,940 --> 00:22:11,550
omejijo na te zelo preprosta
constructs-- gibi ali izjave

441
00:22:11,550 --> 00:22:15,519
kot smo razpravljali, zank in
pogoji, in to je približno to.

442
00:22:15,519 --> 00:22:17,060
Obstaja še nekaj drugih luksuznih funkcij.

443
00:22:17,060 --> 00:22:19,130
Nekateri od njih so povsem
estetsko ali akustično,

444
00:22:19,130 --> 00:22:20,964
kot zvokov sem igral z.

445
00:22:20,964 --> 00:22:23,380
Toda za večino del, ki jih
imajo v tem jeziku, Scratch,

446
00:22:23,380 --> 00:22:25,350
vsi temeljni
gradnikov, ki vas

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

448
00:22:29,280 --> 00:22:32,960
in poljubno število drugih jezikov.

449
00:22:32,960 --> 00:22:36,720
Vsa vprašanja o nič?

450
00:22:36,720 --> 00:22:37,220
V redu.

451
00:22:37,220 --> 00:22:40,303
Torej ne bomo potopite globlje praske,
čeprav ste dobrodošli, ta vikend,

452
00:22:40,303 --> 00:22:42,860
še posebej, če imate otroke ali
nečakinje in nečaki in podobno,

453
00:22:42,860 --> 00:22:44,220
jih seznaniti z Scratch.

454
00:22:44,220 --> 00:22:47,960
To je pravzaprav čudovito igriv
okolje z, kot pravijo njegovi avtorji,

455
00:22:47,960 --> 00:22:49,120
zelo visokim stropom.

456
00:22:49,120 --> 00:22:51,670
Čeprav smo začeli z
zelo podrobnosti nizko stopnjo,

457
00:22:51,670 --> 00:22:54,890
lahko res zelo malo
z njo, in to je morda

458
00:22:54,890 --> 00:22:57,360
dokaz točno to.

459
00:22:57,360 --> 00:23:02,920
>> Ampak kaj je zdaj prehod v nekaj več
sofisticirane težave, če hočete,

460
00:23:02,920 --> 00:23:05,870
poznan kot "iskanje" in
"Razvrščanje", bolj na splošno.

461
00:23:05,870 --> 00:23:09,500
Imeli smo ta imenik earlier-- tukaj
še ena samo za discussion--

462
00:23:09,500 --> 00:23:13,460
da smo lahko iskanje
učinkoviteje ker

463
00:23:13,460 --> 00:23:15,270
znatnega predpostavke.

464
00:23:15,270 --> 00:23:17,655
In samo zato, da bo jasno, kaj
predpostavka, sem bil kar

465
00:23:17,655 --> 00:23:19,280
Pri iskanju po tem imeniku?

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

467
00:23:23,342 --> 00:23:25,300
To je bil Mike Smith v
telefonski imenik, čeprav I

468
00:23:25,300 --> 00:23:27,410
bi bila sposobna izpeljati
scenarij brez njega

469
00:23:27,410 --> 00:23:30,720
tam, če sem ustavil predčasno.

470
00:23:30,720 --> 00:23:31,806
Knjiga je po abecedi.

471
00:23:31,806 --> 00:23:33,930
In to je zelo radodaren
predpostavka, ker je

472
00:23:33,930 --> 00:23:36,580
pomeni someone-- sem nekako
rezanja kotiček,

473
00:23:36,580 --> 00:23:40,580
kot da sem hitrejši, ker nekdo
drug naredil veliko trdega dela za mene.

474
00:23:40,580 --> 00:23:43,120
>> Kaj pa, če je telefon
knjige so bile Nerazvrščene?

475
00:23:43,120 --> 00:23:47,050
Mogoče Verizon dobil leni, samo vrgel
imen in številk vsakogar tam

476
00:23:47,050 --> 00:23:50,120
morda v vrstnem redu, v katerem so
prijavili za telefonske storitve.

477
00:23:50,120 --> 00:23:54,570
In koliko časa traja, me
da bi našli nekoga, kot je Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1.000 strani telefona book-- koliko
Strani moram gledati skozi?

479
00:23:58,160 --> 00:23:58,905
>> Vse.

480
00:23:58,905 --> 00:24:00,030
Ti si nekako od sreče.

481
00:24:00,030 --> 00:24:03,420
Vi dobesedno gledati vsak
Stran če imenik je samo

482
00:24:03,420 --> 00:24:04,450
naključno razporejene.

483
00:24:04,450 --> 00:24:06,910
Morda boste imeli srečo in našli Mike
na zelo prvi strani, ker on

484
00:24:06,910 --> 00:24:08,826
je bil prvi naročnik
naročiti telefonsko storitev.

485
00:24:08,826 --> 00:24:10,760
Vendar bi lahko bil zadnji, preveč.

486
00:24:10,760 --> 00:24:12,500
>> Torej naključno da ni dobro.

487
00:24:12,500 --> 00:24:16,750
Torej, da imamo za razvrstite
imenik ali v splošnih podatkov sort

488
00:24:16,750 --> 00:24:18,520
ki ste nam bili dana.

489
00:24:18,520 --> 00:24:19,440
Kako lahko to storimo?

490
00:24:19,440 --> 00:24:21,360
>> No, naj le poskusite
enostaven primer tukaj.

491
00:24:21,360 --> 00:24:24,290
Naj gredo naprej in kretnjo
Nekaj ​​številke na krovu.

492
00:24:24,290 --> 00:24:35,480
Recimo, da številke, ki jih imamo, so
recimo, štiri, dva, ena in tri.

493
00:24:35,480 --> 00:24:38,390
In, Ben, rešiti te številke za nas.

494
00:24:38,390 --> 00:24:39,017
>> OK, dobro.

495
00:24:39,017 --> 00:24:39,850
Kako si to naredil?

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

497
00:24:42,731 --> 00:24:43,230
V redu.

498
00:24:43,230 --> 00:24:44,710
Torej začnite z najmanjšim
vrednost in najvišjo,

499
00:24:44,710 --> 00:24:46,084
in to je res dobro intuicijo.

500
00:24:46,084 --> 00:24:48,080
In zavedati, da smo
ljudje so dejansko precej

501
00:24:48,080 --> 00:24:49,913
dobri v reševanju problemov
kot je ta, vsaj

502
00:24:49,913 --> 00:24:51,810
ko je podatkovna relativno majhna.

503
00:24:51,810 --> 00:24:54,860
Takoj, ko začnete na stotine
številk, na tisoče številk,

504
00:24:54,860 --> 00:24:58,440
milijone številk, Ben verjetno
to ne bi mogel storiti prav tako hitro,

505
00:24:58,440 --> 00:25:00,620
ob predpostavki, da je bilo
razlike v številu.

506
00:25:00,620 --> 00:25:03,450
Zelo enostavno, da računajo na milijon
sicer pa porabijo le čas.

507
00:25:03,450 --> 00:25:07,150
>> Torej algoritem se sliši
kot Ben uporablja šele zdaj

508
00:25:07,150 --> 00:25:08,930
je iskanje najmanjšim številom.

509
00:25:08,930 --> 00:25:12,900
Torej, čeprav mi lahko ljudje sprejmejo
V veliko informacij vizualno,

510
00:25:12,900 --> 00:25:14,830
računalnik dejansko
malo bolj omejen.

511
00:25:14,830 --> 00:25:17,560
Računalnik lahko samo
poglej enega bita naenkrat

512
00:25:17,560 --> 00:25:20,770
ali morda štiri bajte na time--
v teh dneh morda 8 bajtov na time--

513
00:25:20,770 --> 00:25:24,450
vendar zelo majhno število
bajtov v določenem času.

514
00:25:24,450 --> 00:25:28,480
>> Torej, glede na to, moramo res
štirje ločeni vrednosti here--

515
00:25:28,480 --> 00:25:32,440
in lahko si misliš, Ben, da ima
senčila za, če bi bil računalnik kot

516
00:25:32,440 --> 00:25:36,450
da ne vidim ničesar drugega
kot eno številko pri time--

517
00:25:36,450 --> 00:25:39,720
zato smo na splošno bo prevzel, kot v
Angleščina, bomo prebrali od desne proti levi.

518
00:25:39,720 --> 00:25:42,870
Torej prva številka Ben verjetno pogledal
je bil štiri in nato zelo hitro

519
00:25:42,870 --> 00:25:44,770
spoznal, da je precej velik
number-- mi iščite naprej.

520
00:25:44,770 --> 00:25:45,357
>> Tam je dva.

521
00:25:45,357 --> 00:25:45,940
Počakaj minuto.

522
00:25:45,940 --> 00:25:47,070
Dva manjša od štiri.

523
00:25:47,070 --> 00:25:47,986
Grem, da se spomnimo.

524
00:25:47,986 --> 00:25:49,070
Dva je sedaj najmanjši.

525
00:25:49,070 --> 00:25:50,417
Zdaj one--, da je še boljši.

526
00:25:50,417 --> 00:25:51,250
To je še manjši.

527
00:25:51,250 --> 00:25:54,000
Bom pozabil približno dva
in zapomni si zdaj.

528
00:25:54,000 --> 00:25:56,550
>> In bi lahko nehali iskati?

529
00:25:56,550 --> 00:25:58,360
No, vendar je bil na podlagi
na te informacije,

530
00:25:58,360 --> 00:26:00,477
vendar je bolje, iskanje
preostanek seznama.

531
00:26:00,477 --> 00:26:02,060
Ker kaj če nič je bilo na seznamu?

532
00:26:02,060 --> 00:26:03,643
Kaj pa, če so bili negativni ena na seznamu?

533
00:26:03,643 --> 00:26:07,720
On ve, da je njegov odgovor
je pravilna, če je to izčrpno

534
00:26:07,720 --> 00:26:08,729
preverili celoten seznam.

535
00:26:08,729 --> 00:26:10,020
Tako gledamo na preostanek tega.

536
00:26:10,020 --> 00:26:11,394
Three--, da je izguba časa.

537
00:26:11,394 --> 00:26:13,540
Dobil sreče, vendar sem bil
Še vedno pravi, da to storijo.

538
00:26:13,540 --> 00:26:17,857
In zdaj je verjetno
izbrali najmanjše število

539
00:26:17,857 --> 00:26:20,440
in samo da na začetku
seznama, ker bom naredil tukaj.

540
00:26:20,440 --> 00:26:23,480
Zdaj, kaj si naredil zraven, čeprav
si ne mislim o tem skoraj

541
00:26:23,480 --> 00:26:25,962
do te mere?

542
00:26:25,962 --> 00:26:27,670
Ponovite postopek,
tako neke vrste zanke.

543
00:26:27,670 --> 00:26:28,920
Tam je znana ideja.

544
00:26:28,920 --> 00:26:30,860
Torej, tukaj je štiri.

545
00:26:30,860 --> 00:26:32,110
To je trenutno najmanjša.

546
00:26:32,110 --> 00:26:33,220
To je kandidat.

547
00:26:33,220 --> 00:26:33,900
Ne več.

548
00:26:33,900 --> 00:26:34,770
Zdaj sem videl dva.

549
00:26:34,770 --> 00:26:36,630
To je naslednji najmanjši element.

550
00:26:36,630 --> 00:26:40,800
Three-- ki ni manjši, tako
Zdaj Ben lahko izderi dva.

551
00:26:40,800 --> 00:26:44,510
>> In zdaj smo ponovite postopek, in
Seveda treh gets potegnil naprej.

552
00:26:44,510 --> 00:26:45,420
Ponovite postopek.

553
00:26:45,420 --> 00:26:46,990
Štiri gets potegnil ven.

554
00:26:46,990 --> 00:26:50,140
In zdaj smo iz številk,
tako da je seznam mora biti urejeno.

555
00:26:50,140 --> 00:26:51,960
>> In res, to je formalno algoritem.

556
00:26:51,960 --> 00:26:56,610
Računalniški znanstvenik bi
Takšno "izbiro vrste,"

557
00:26:56,610 --> 00:27:00,880
ideja pa neke
Seznam iteratively-- znova

558
00:27:00,880 --> 00:27:03,807
in spet izbiro
najmanjše število.

559
00:27:03,807 --> 00:27:06,140
In kaj je lepo, pa je
to je samo tako darn intuitivno.

560
00:27:06,140 --> 00:27:07,470
To je tako enostavno.

561
00:27:07,470 --> 00:27:11,100
In lahko ponovite isti
spet in spet operacija.

562
00:27:11,100 --> 00:27:12,150
To je enostavno.

563
00:27:12,150 --> 00:27:17,170
>> V tem primeru je bilo hitro, vendar
kako dolgo je pravzaprav trajalo?

564
00:27:17,170 --> 00:27:19,880
Recimo, da se zdi, in
počutim malo bolj dolgočasno.

565
00:27:19,880 --> 00:27:24,150
Torej ena, dva, tri, štiri, pet šest,
sedem, osem, devet, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- poljubna številka.

567
00:27:26,160 --> 00:27:28,780
Hotela sem več to
Čas kot le štiri.

568
00:27:28,780 --> 00:27:30,780
Torej, če imam celoto
kup številk je now--

569
00:27:30,780 --> 00:27:32,420
sploh ni pomembno
kaj are-- Oglejmo

570
00:27:32,420 --> 00:27:34,380
razmišljati o tem, kaj je to
Algoritem je res všeč.

571
00:27:34,380 --> 00:27:35,857
>> Recimo, da so številke tam.

572
00:27:35,857 --> 00:27:38,190
Še enkrat, ni pomembno, kaj
so, ampak oni so naključno.

573
00:27:38,190 --> 00:27:39,679
Prijavljam Ben je algoritem.

574
00:27:39,679 --> 00:27:41,220
Moram izbrati najmanjše število.

575
00:27:41,220 --> 00:27:41,761
Kaj naj naredim?

576
00:27:41,761 --> 00:27:44,240
In bom fizično
storiti je to čas, da to deluje ven.

577
00:27:44,240 --> 00:27:46,099
Če pogledamo, je videti,
išče, išče, išče.

578
00:27:46,099 --> 00:27:48,140
Šele ko sem dobil, da
Konec seznama lahko

579
00:27:48,140 --> 00:27:51,230
Zavedam se, najmanjši
Številka je dva tokrat.

580
00:27:51,230 --> 00:27:52,720
One ni na seznamu.

581
00:27:52,720 --> 00:27:54,400
Zato sem odložil dva.

582
00:27:54,400 --> 00:27:55,590
>> Kaj naj storim zdaj?

583
00:27:55,590 --> 00:27:58,600
Če pogledamo, je videti, videti, videti.

584
00:27:58,600 --> 00:28:02,250
Sedaj sem našel številko sedem, saj
tam je razlike v teh numbers--

585
00:28:02,250 --> 00:28:03,300
ampak samo arbitrarno.

586
00:28:03,300 --> 00:28:03,800
V redu.

587
00:28:03,800 --> 00:28:06,030
Sedaj sem lahko odložil sedem.

588
00:28:06,030 --> 00:28:08,860
Če pogledamo v prihodnost, je videti.

589
00:28:08,860 --> 00:28:11,030
>> Zdaj sem ob predpostavki, od
Seveda, da Ben ne

590
00:28:11,030 --> 00:28:14,780
imajo dodaten RAM, extra
pomnilnika, saj seveda

591
00:28:14,780 --> 00:28:16,080
Gledam isto številko.

592
00:28:16,080 --> 00:28:18,246
Gotovo bi lahko sem se spomnil
vse te številke,

593
00:28:18,246 --> 00:28:19,930
in to je popolnoma res.

594
00:28:19,930 --> 00:28:22,610
Ampak, če Ben spomni vse
številk je videl,

595
00:28:22,610 --> 00:28:24,430
on je res ni postavil
temeljni napredek

596
00:28:24,430 --> 00:28:26,170
ker je že
sposobnost za iskanje

597
00:28:26,170 --> 00:28:27,540
s številkami na krovu.

598
00:28:27,540 --> 00:28:29,373
Spomin na vse
Številke ne pomaga,

599
00:28:29,373 --> 00:28:32,490
ker je lahko še vedno kot računalnik
samo poglej, da smo omenjeno, eno številko

600
00:28:32,490 --> 00:28:33,080
ob času.

601
00:28:33,080 --> 00:28:35,760
Tako da ni neke vrste goljufija
tam, da lahko izkoristite.

602
00:28:35,760 --> 00:28:39,170
>> Torej v resnici, kot sem
naprej iskati seznam,

603
00:28:39,170 --> 00:28:44,200
Sem dobesedno samo nadaljuj
naprej in nazaj skozi njo, skubljenje ven

604
00:28:44,200 --> 00:28:45,710
naslednjo manjšo številko.

605
00:28:45,710 --> 00:28:48,810
In kot lahko nekako sklepati
iz mojih neumnih gibanja,

606
00:28:48,810 --> 00:28:50,860
to samo postane zelo
zamudno zelo hitro,

607
00:28:50,860 --> 00:28:54,850
in mi zdi, da se vrača in
naprej, naprej in nazaj zelo malo.

608
00:28:54,850 --> 00:29:03,220
Zdaj bi bilo pošteno, da ne bi bilo treba iti
čisto tako, no, see-- biti pošten,

609
00:29:03,220 --> 00:29:06,310
Nimam dokaj hoditi
toliko korakov vsak čas.

610
00:29:06,310 --> 00:29:09,200
Ker je seveda, ko sem
izberite številke iz seznama,

611
00:29:09,200 --> 00:29:11,860
preostali seznam je vedno krajši.

612
00:29:11,860 --> 00:29:14,240
>> In tako da je razmišljati o
koliko korakov sem dejansko

613
00:29:14,240 --> 00:29:16,010
traipsing skozi vsak čas.

614
00:29:16,010 --> 00:29:18,950
V prvem položaju
smo imeli 16 številk,

615
00:29:18,950 --> 00:29:22,210
in tako maximally-- jev naj samo
To storite za discussion--

616
00:29:22,210 --> 00:29:25,640
Sem moral pogledati skozi 16
številke, da bi našli najmanjši.

617
00:29:25,640 --> 00:29:28,420
Ampak, ko sem potegnil
najmanjše število, kako

618
00:29:28,420 --> 00:29:30,590
dolgo je preostalo seznam, seveda?

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

620
00:29:31,420 --> 00:29:34,670
Torej, koliko številke storil Ben, ali imam
odmisliti drugič naokoli?

621
00:29:34,670 --> 00:29:36,832
15, samo, da gredo in najti najmanjši.

622
00:29:36,832 --> 00:29:39,540
Toda zdaj, seveda, seznam,
Tudi manjše, kot je bilo prej.

623
00:29:39,540 --> 00:29:42,540
Torej, koliko korakov sem
morali naslednjič?

624
00:29:42,540 --> 00:29:49,970
14 in 13, nato pa 12 plus pika,
dot, dot, dokler ne bom ostal samo eden.

625
00:29:49,970 --> 00:29:53,146
Zdaj bi računalniški znanstvenik
vprašati, dobro, kaj počne, da so vsi enaki?

626
00:29:53,146 --> 00:29:55,770
To dejansko enaka nekaj konkretnega
število, ki smo lahko zagotovo

627
00:29:55,770 --> 00:30:00,490
narediti računsko, vendar želimo govoriti
o učinkovitosti algoritmov

628
00:30:00,490 --> 00:30:04,940
malo bolj formulaically,
neodvisna, kako dolgo je seznam.

629
00:30:04,940 --> 00:30:06,240
>> In tako da boste vedeli, kaj?

630
00:30:06,240 --> 00:30:09,860
To je 16, ampak kot sem rekel prej,
kaj je samo pokličite na velikost problema

631
00:30:09,860 --> 00:30:10,970
n, kjer je n nekaj številka.

632
00:30:10,970 --> 00:30:13,220
Mogoče je 16, morda je
tri, morda je milijon.

633
00:30:13,220 --> 00:30:13,761
Nevem.

634
00:30:13,761 --> 00:30:14,390
Me ne zanima.

635
00:30:14,390 --> 00:30:16,520
Kaj si res želim, je
formula, da sem lahko

636
00:30:16,520 --> 00:30:19,420
uporabljajo za primerjavo ta algoritem
v primerjavi z drugimi algoritmi

637
00:30:19,420 --> 00:30:22,350
da bi nekdo trdijo
bolje ali slabše.

638
00:30:22,350 --> 00:30:25,430
>> Tako se je izkazalo, in sem samo
vem, to je osnovni šoli,

639
00:30:25,430 --> 00:30:34,790
da to dejansko deluje ven enaka
stvar kot n nad n plus ena več kot dve.

640
00:30:34,790 --> 00:30:40,020
In to se zgodi, da bo enak, od
Seveda, n kvadrat plus n več kot dva.

641
00:30:40,020 --> 00:30:43,250
Torej, če sem hotel formulo
za koliko korakov

642
00:30:43,250 --> 00:30:46,330
so sodelovali pri iskanju sploh
od znova in znova te številke

643
00:30:46,330 --> 00:30:52,681
in znova in znova, bi rekel
to je n na kvadrat plus n več kot dva.

644
00:30:52,681 --> 00:30:53,430
Ampak veš kaj?

645
00:30:53,430 --> 00:30:54,500
To samo izgleda grdo.

646
00:30:54,500 --> 00:30:56,470
Pravkar sem res želijo
splošni občutek stvari.

647
00:30:56,470 --> 00:30:58,810
In morda spomnite iz
visoka šola, ki je

648
00:30:58,810 --> 00:31:00,660
je pojem najvišjega izraza naročila.

649
00:31:00,660 --> 00:31:05,300
Kateri od teh pogojev, n
kvadrat, N, ali polovico,

650
00:31:05,300 --> 00:31:07,550
ima največji vpliv skozi čas?

651
00:31:07,550 --> 00:31:11,920
Večji n bolnikih, ki
teh zadev je najbolj?

652
00:31:11,920 --> 00:31:15,560
>> Z drugimi besedami, če priključim
na milijon, n kvadrat

653
00:31:15,560 --> 00:31:17,900
se bo najverjetneje
prevladujoči faktor,

654
00:31:17,900 --> 00:31:21,670
ker je milijon krat
Sama je veliko večja

655
00:31:21,670 --> 00:31:23,682
kot plus eno dodatno milijonov.

656
00:31:23,682 --> 00:31:24,390
Torej, veste kaj?

657
00:31:24,390 --> 00:31:27,305
To je tako darn velik
številko, če kvadratni številko.

658
00:31:27,305 --> 00:31:28,430
To sploh ni pomembno.

659
00:31:28,430 --> 00:31:30,596
Mi smo le, da bo predložek, ki
ven in pozabi.

660
00:31:30,596 --> 00:31:34,250
In tako bi bil računalniški znanstvenik reči
da je za učinkovitost tega algoritma

661
00:31:34,250 --> 00:31:37,850
je reda n squared--
Mislim resnično približevanje.

662
00:31:37,850 --> 00:31:40,810
To je neke vrste grobo n kvadrat.

663
00:31:40,810 --> 00:31:44,130
Sčasoma, večji
in večji n postane ta

664
00:31:44,130 --> 00:31:47,610
je dobra ocena za kaj
učinkovitost ali pomanjkanje učinkovitosti

665
00:31:47,610 --> 00:31:49,400
tega algoritma v resnici.

666
00:31:49,400 --> 00:31:52,040
In sem izhaja, da seveda
od dejansko delaš math.

667
00:31:52,040 --> 00:31:54,040
Ampak zdaj sem samo mahal
moje roke, ker sem pravkar

668
00:31:54,040 --> 00:31:55,790
želijo splošni smisel tega algoritma.

669
00:31:55,790 --> 00:31:58,850
>> Torej, z uporabo iste logike, medtem,
kaj menijo drugi algoritem

670
00:31:58,850 --> 00:32:01,162
smo že pogledal at-- linearno iskanje.

671
00:32:01,162 --> 00:32:02,870
Ko sem iskal
za telefonsko book--

672
00:32:02,870 --> 00:32:05,980
ne razvrščanje, iskanje
prek telefonske book--

673
00:32:05,980 --> 00:32:09,197
smo ohranili pravi, da je bilo
1.000 korakov ali 500 korakov.

674
00:32:09,197 --> 00:32:10,280
Ampak kaj je posploševati, da je.

675
00:32:10,280 --> 00:32:12,860
Če je n strani v
telefonski imenik, kar je

676
00:32:12,860 --> 00:32:17,250
čas teče ali
Učinkovitost linearne iskanju?

677
00:32:17,250 --> 00:32:19,750
Je o vrstnem redu
koliko korakov, da bi našli

678
00:32:19,750 --> 00:32:24,210
Mike Smith z linearno iskanja,
Prvi algoritem, niti drugega?

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

680
00:32:27,240 --> 00:32:31,710
>> V najslabšem primeru, Mike
na koncu knjige.

681
00:32:31,710 --> 00:32:35,590
Torej, če je imenik 1.000 strani,
smo rekli zadnjič, v najslabšem primeru,

682
00:32:35,590 --> 00:32:38,380
to lahko traja približno kako
veliko strani, da bi našli Mike?

683
00:32:38,380 --> 00:32:38,990
Like 1.000.

684
00:32:38,990 --> 00:32:39,830
To je zgornja meja.

685
00:32:39,830 --> 00:32:41,790
To je najslabši možni položaj.

686
00:32:41,790 --> 00:32:44,410
Ampak še enkrat, smo se oddaljuje
od številk kot 1.000 zdaj.

687
00:32:44,410 --> 00:32:45,730
To je samo n.

688
00:32:45,730 --> 00:32:47,470
>> Torej, kaj je logičen zaključek?

689
00:32:47,470 --> 00:32:50,210
Iskanje Mike v telefonu
knjiga, ki ima n strani

690
00:32:50,210 --> 00:32:55,280
lahko traja, v zelo najslabšem primeru,
koliko korakov na reda n?

691
00:32:55,280 --> 00:32:58,110
In seveda računalnik
znanstvenik bi rekel

692
00:32:58,110 --> 00:33:02,340
da je čas, ki teče, ali
uspešnosti ali učinkovitosti

693
00:33:02,340 --> 00:33:07,470
ali neučinkovitost, z algoritmom, kot je
linearna iskanje je reda n.

694
00:33:07,470 --> 00:33:10,010
In lahko uporablja isti
Logika prehodu nekaj iz

695
00:33:10,010 --> 00:33:13,170
kot sem naredil drugo
Algoritem smo imeli z imenika,

696
00:33:13,170 --> 00:33:16,040
kjer smo šli dve strani naenkrat.

697
00:33:16,040 --> 00:33:20,120
>> Torej 1000 stran imenika morda
da nas 500 stran obrne, plus ena

698
00:33:20,120 --> 00:33:21,910
če bomo podvojili malo nazaj.

699
00:33:21,910 --> 00:33:26,590
Torej, če ima telefonski imenik n strani, vendar
delamo dve strani naenkrat,

700
00:33:26,590 --> 00:33:28,900
to je približno kaj?

701
00:33:28,900 --> 00:33:33,190
N čez dva, tako da je kot n več kot dva.

702
00:33:33,190 --> 00:33:38,490
Ampak sem zahtevka a
Trenutek nazaj, da n nad dvo

703
00:33:38,490 --> 00:33:41,060
To je nekako isto kot le n.

704
00:33:41,060 --> 00:33:44,050
To je samo konstanten faktor,
računalniški znanstveniki, bi rekli.

705
00:33:44,050 --> 00:33:45,970
Osredotočimo se le na
spremenljivke, really--

706
00:33:45,970 --> 00:33:47,780
največji spremenljivke v enačbi.

707
00:33:47,780 --> 00:33:52,530
>> Torej linearno iskanje, ali narediti eno
Stran naenkrat ali dve strani naenkrat,

708
00:33:52,530 --> 00:33:54,810
je nekako v osnovi enaka.

709
00:33:54,810 --> 00:33:56,880
To je še vedno v redu n.

710
00:33:56,880 --> 00:34:01,930
Ampak sem trdil, z mojo sliko prej
da tretja algoritem ni bilo

711
00:34:01,930 --> 00:34:02,480
linearna.

712
00:34:02,480 --> 00:34:03,605
To ni bil ravno črto.

713
00:34:03,605 --> 00:34:08,659
To je bil, da je ukrivljena linija, in
algebraična enačba je bilo kaj?

714
00:34:08,659 --> 00:34:11,812
Dnevnik N- tako logaritem dva n.

715
00:34:11,812 --> 00:34:14,520
In mi ne bi bilo treba iti v preveč
veliko podrobnosti o logaritmov danes

716
00:34:14,520 --> 00:34:17,394
vendar je večina računalniški znanstveniki ne bi
tudi povedal, kaj je baza.

717
00:34:17,394 --> 00:34:20,639
Ker je vse samo
stalnih dejavnikov, tako rekoč,

718
00:34:20,639 --> 00:34:22,659
le manjše numerične razlike.

719
00:34:22,659 --> 00:34:31,179
In tako bi bilo to zelo pogost
način, zlasti formalno računalnik

720
00:34:31,179 --> 00:34:33,949
znanstveniki na desko ali
programerji na belo ploščo

721
00:34:33,949 --> 00:34:36,889
dejansko trdi, ki
algoritem, ki bi jih uporabili

722
00:34:36,889 --> 00:34:39,500
ali kaj učinkovitost
za njihov algoritem.

723
00:34:39,500 --> 00:34:42,960
>> In to ni nujno nekaj
ste razpravljali v vsakem zelo podrobno,

724
00:34:42,960 --> 00:34:47,889
ampak dober programer je nekdo
ki ima trdno, formalno ozadje.

725
00:34:47,889 --> 00:34:50,120
On je sposoben govoriti z
vi v tovrstni način

726
00:34:50,120 --> 00:34:53,350
in dejansko narediti
kvalitativne argumente

727
00:34:53,350 --> 00:34:56,870
zakaj en algoritem ali
en kos programske opreme

728
00:34:56,870 --> 00:35:00,165
je boljše, na nek način v drugo.

729
00:35:00,165 --> 00:35:02,540
Ker si lahko zagotovo
samo izvajanje programa za ene osebe

730
00:35:02,540 --> 00:35:04,980
in štetje števila sekund
je potrebno rešiti nekaj številk,

731
00:35:04,980 --> 00:35:06,710
in lahko teče nekaj
Program druge osebe

732
00:35:06,710 --> 00:35:08,418
in štetje števila
sekund je potrebno.

733
00:35:08,418 --> 00:35:12,840
Ampak to je bolj splošen način, da
lahko uporabite za analizo algoritmov,

734
00:35:12,840 --> 00:35:15,520
če hočete, samo na
papir ali samo verbalno.

735
00:35:15,520 --> 00:35:18,430
Brez celo vožnjo, ne da bi
celo poskuša vzorčne vložkov,

736
00:35:18,430 --> 00:35:20,180
lahko samo razum skozi to.

737
00:35:20,180 --> 00:35:24,670
In tako z najemom razvijalec ali če
ob mu ali ji nekako trdijo, da vas

738
00:35:24,670 --> 00:35:28,460
zakaj njihova algoritem, njihova skrivnost
omaka za iskanje milijarde

739
00:35:28,460 --> 00:35:30,580
spletnih strani za vaše
Družba je bolje, ti

740
00:35:30,580 --> 00:35:33,302
so vrste argumente, ki jih
naj bodo sposobni narediti.

741
00:35:33,302 --> 00:35:35,010
Ali vsaj gre
vrste stvari,

742
00:35:35,010 --> 00:35:40,211
da bi prišel v razpravo, na
vsaj v zelo formalno razpravo.

743
00:35:40,211 --> 00:35:40,710
V redu.

744
00:35:40,710 --> 00:35:44,400
Torej Ben predlagala nekaj
imenuje izbor vrste.

745
00:35:44,400 --> 00:35:48,200
Ampak bom predlagala, da obstaja
drugih načinov za to, preveč.

746
00:35:48,200 --> 00:35:50,400
Kaj mi ni res všeč
o Benova algoritem

747
00:35:50,400 --> 00:35:54,400
je, da je ohranil hojo, ali
ko sem hodil, sem in tja

748
00:35:54,400 --> 00:35:56,930
ter naprej in nazaj in naprej in nazaj.

749
00:35:56,930 --> 00:36:04,130
Kaj če bi namesto da bi naredil
nekaj podobnega te številke tukaj

750
00:36:04,130 --> 00:36:08,200
in jaz bi samo ukvarjati z vsako
številka pa, kot sem jo dal?

751
00:36:08,200 --> 00:36:10,780
>> Z drugimi besedami, tukaj je
moj seznam številk.

752
00:36:10,780 --> 00:36:12,944
Štiri ena, tri, dva.

753
00:36:12,944 --> 00:36:14,360
In bom naredil naslednje.

754
00:36:14,360 --> 00:36:17,230
Bom vstaviti številke
kamor sodijo precej

755
00:36:17,230 --> 00:36:18,980
kot jih izbiro enega naenkrat.

756
00:36:18,980 --> 00:36:20,820
Z drugimi besedami, tu je številka štiri.

757
00:36:20,820 --> 00:36:22,430
>> Tukaj je moj prvotni seznam.

758
00:36:22,430 --> 00:36:25,290
In bom, da se ohrani
v bistvu nov seznam tukaj.

759
00:36:25,290 --> 00:36:26,710
To je torej stara seznam.

760
00:36:26,710 --> 00:36:28,560
To je novi seznam.

761
00:36:28,560 --> 00:36:30,220
Vidim, da se je število štiri prva.

762
00:36:30,220 --> 00:36:34,500
Moja Nov seznam je na začetku prazna,
zato je trivially drži

763
00:36:34,500 --> 00:36:36,410
da se štirje zdaj urejene seznam.

764
00:36:36,410 --> 00:36:39,560
Jaz sem samo pokazal številko sem dano,
in sem ga je dala v mojem novem seznamu.

765
00:36:39,560 --> 00:36:41,460
>> Je to nov seznam razporejene?

766
00:36:41,460 --> 00:36:41,990
Ja.

767
00:36:41,990 --> 00:36:45,090
To je neumno, ker tam je samo ena
element, vendar je popolnoma urejeno.

768
00:36:45,090 --> 00:36:46,390
Nič ni na pravem mestu.

769
00:36:46,390 --> 00:36:49,290
To je bolj zanimivo, ta algoritem,
ko sem se premaknete na naslednji korak.

770
00:36:49,290 --> 00:36:50,550
>> Zdaj imam enega.

771
00:36:50,550 --> 00:36:55,430
Torej on, seveda, spada v
začetek ali konec tega novega seznama?

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

773
00:36:56,360 --> 00:36:58,530
Tako da sem moral narediti nekaj dela zdaj.

774
00:36:58,530 --> 00:37:01,410
Sem bil ob nekaj
svoboščine z mojim označevalec

775
00:37:01,410 --> 00:37:03,120
s samo pripravo stvari
kjer jih hočem,

776
00:37:03,120 --> 00:37:05,320
vendar to ni res
točna v računalniku.

777
00:37:05,320 --> 00:37:08,530
Računalnik, kot vemo, je
RAM ali Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
in to je en bajt in
en bajt in en bajt.

779
00:37:12,411 --> 00:37:14,910
In če imate GB
RAM, imate milijardo bajtov,

780
00:37:14,910 --> 00:37:16,680
ampak oni so fizično na enem mestu.

781
00:37:16,680 --> 00:37:19,540
Ne moreš premikati stvari okoli
tako, da ga pripravi na krovu

782
00:37:19,540 --> 00:37:20,750
kjerkoli hočeš.

783
00:37:20,750 --> 00:37:24,090
Torej, če ima moj nov seznam
štiri lokacije v pomnilniku,

784
00:37:24,090 --> 00:37:27,480
žal štirih je
že na napačnem mestu.

785
00:37:27,480 --> 00:37:30,410
>> Torej, da vstavite številko ena
Ne morem ga pripraviti tukaj.

786
00:37:30,410 --> 00:37:31,901
Ta pomnilnik ne obstaja.

787
00:37:31,901 --> 00:37:35,150
To bi bilo goljufanje, in sem bil
varanje slikovno nekaj minut

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

789
00:37:35,800 --> 00:37:40,950
Torej res, če želim postaviti enega tukaj,
Moram začasno kopirati štiri

790
00:37:40,950 --> 00:37:43,030
in potem dal eno tam.

791
00:37:43,030 --> 00:37:45,500
>> To je v redu, da je pravilna,
da je to tehnično izvedljivo,

792
00:37:45,500 --> 00:37:48,410
vendar spoznali, da je dodatno delo.

793
00:37:48,410 --> 00:37:50,460
Nisem samo to število v mestu.

794
00:37:50,460 --> 00:37:53,026
Sem moral najprej premaknete
številko, nato pa ga na mestu,

795
00:37:53,026 --> 00:37:54,650
zato sem nekako podvojila svoj obseg dela.

796
00:37:54,650 --> 00:37:55,660
Tako da se vodijo v mislih.

797
00:37:55,660 --> 00:37:57,120
>> Ampak jaz sem zdaj naredil s tem elementom.

798
00:37:57,120 --> 00:37:59,056
Zdaj hočem, da zgrabite številko tri.

799
00:37:59,056 --> 00:38:00,430
Kjer seveda ne pripada?

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

801
00:38:01,480 --> 00:38:03,650
Ne morem goljufija več
in to samo da tam,

802
00:38:03,650 --> 00:38:06,770
ker, spet, ta spomin
je v fizičnih lokacijah.

803
00:38:06,770 --> 00:38:10,900
Tako da sem moral kopirati štiri
in dal tri tukaj.

804
00:38:10,900 --> 00:38:11,550
Ni nič takega.

805
00:38:11,550 --> 00:38:14,610
To je samo en dodaten korak
again-- se počuti zelo poceni.

806
00:38:14,610 --> 00:38:16,445
>> Sedaj pa pojdite na obeh.

807
00:38:16,445 --> 00:38:17,820
Sta seveda pripada tukaj.

808
00:38:17,820 --> 00:38:20,990
Zdaj boste videli, kako
Delo lahko kopičijo.

809
00:38:20,990 --> 00:38:23,520
Zdaj, kaj moram storiti?

810
00:38:23,520 --> 00:38:28,570
Ja, moram premakniti štiri,
potem moram kopirati tri,

811
00:38:28,570 --> 00:38:31,200
in zdaj sem lahko vstavite dva.

812
00:38:31,200 --> 00:38:34,460
In ulov s tem
algoritem, dovolj zanimivo,

813
00:38:34,460 --> 00:38:41,050
je to da imamo bolj ekstremni
primer, kjer je recimo osem, sedem,

814
00:38:41,050 --> 00:38:45,150
šest, pet, štiri, tri, dve, ena.

815
00:38:45,150 --> 00:38:49,450
To je v številnih kontekstih,
najslabšem primeru,

816
00:38:49,450 --> 00:38:51,570
ker je darn stvar
je dobesedno nazaj.

817
00:38:51,570 --> 00:38:53,670
>> To pa ni res
vplivajo Ben je algoritem,

818
00:38:53,670 --> 00:38:55,940
ker pri izbiri Benova
vrsta se dogaja, da

819
00:38:55,940 --> 00:38:58,359
gre naprej in nazaj po seznamu.

820
00:38:58,359 --> 00:39:01,150
In ker je bil vedno iščejo
preko celotnega preostalega seznama

821
00:39:01,150 --> 00:39:02,858
ni pomembno
kjer so elementi.

822
00:39:02,858 --> 00:39:05,630
Toda v tem primeru z mojim vstavljanje
approach-- poskusimo to.

823
00:39:05,630 --> 00:39:08,616
>> Torej ena, dva, tri, štiri,
pet, šest, sedem, osem.

824
00:39:08,616 --> 00:39:11,630
Ena dve tri Štiri,
pet, šest, sedem, osem.

825
00:39:11,630 --> 00:39:14,320
Bom vzeti osem,
in kje sem ga dal?

826
00:39:14,320 --> 00:39:17,260
No, na začetku mojega seznama,
ker ta novi Seznam je razvrščen.

827
00:39:17,260 --> 00:39:18,760
In sem prečkati to.

828
00:39:18,760 --> 00:39:20,551
>> Kam je sedem?

829
00:39:20,551 --> 00:39:21,050
Presneto.

830
00:39:21,050 --> 00:39:23,174
To mora iti tja, tako
Moram narediti nekaj kopiranje.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
In sedaj sedem gre tukaj.

833
00:39:28,480 --> 00:39:29,860
Zdaj pa pojdite na šest.

834
00:39:29,860 --> 00:39:30,980
Zdaj je še več dela.

835
00:39:30,980 --> 00:39:32,570
>> Osem mora iti tukaj.

836
00:39:32,570 --> 00:39:33,920
Sedem mora iti tukaj.

837
00:39:33,920 --> 00:39:35,450
Zdaj šest more iti tukaj.

838
00:39:35,450 --> 00:39:37,950
Zdaj pa zgrabi pet.

839
00:39:37,950 --> 00:39:40,560
Zdaj osem mora iti
tukaj, sedem mora iti tu,

840
00:39:40,560 --> 00:39:43,650
šest mora iti tu in
zdaj pet in ponovite.

841
00:39:43,650 --> 00:39:46,610
In sem precej
premikanjem ves čas.

842
00:39:46,610 --> 00:39:52,950
>> Torej, na koncu pa je to algorithm-- bomo
pravijo vstavljanje sort-- dejansko

843
00:39:52,950 --> 00:39:55,020
Ima veliko dela, preveč.

844
00:39:55,020 --> 00:39:56,970
To je samo drugačen
način dela kot Ben-jev.

845
00:39:56,970 --> 00:40:00,090
Delo Benova imel me bo
in nazaj ves čas,

846
00:40:00,090 --> 00:40:03,510
izberete naslednjo manjšo
znova in znova element.

847
00:40:03,510 --> 00:40:06,660
Tako da je bilo to zelo vizualni način dela.

848
00:40:06,660 --> 00:40:10,600
>> Ta drugi algoritem, ki je še vedno
correct-- bo dobil delo done--

849
00:40:10,600 --> 00:40:12,800
Samo spremeni količino dela.

850
00:40:12,800 --> 00:40:15,420
Videti je, da na začetku, da si
prihranek, saj si samo

851
00:40:15,420 --> 00:40:19,190
ki se ukvarjajo z vsakim elementom
spredaj brez hojo vse

852
00:40:19,190 --> 00:40:20,930
pot po seznamu, kot so Ben je bil.

853
00:40:20,930 --> 00:40:25,300
Ampak problem je, še posebej v teh
nori primeri, v katerih je vse nazaj,

854
00:40:25,300 --> 00:40:27,830
ste le nekako
preložitev trdo delo

855
00:40:27,830 --> 00:40:30,360
dokler ne boste morali popraviti svoje napake.

856
00:40:30,360 --> 00:40:33,919
>> In tako, če si lahko to predstavljate
osem in sedem in šest in pet

857
00:40:33,919 --> 00:40:36,710
kasneje pa štiri in tri in dva
premika svojo pot po seznamu,

858
00:40:36,710 --> 00:40:39,060
smo pravkar spremenila
vrsta dela delamo.

859
00:40:39,060 --> 00:40:42,340
Namesto, da delaš na
začetek mojega ponovitev,

860
00:40:42,340 --> 00:40:45,250
Jaz samo delam Na
konec vsake iteracije.

861
00:40:45,250 --> 00:40:50,550
Tako se izkaže, da ta algoritem,
Tudi na splošno se imenuje vstavljanje razvrščanje,

862
00:40:50,550 --> 00:40:52,190
je tudi na vrstni red n razčetverjen.

863
00:40:52,190 --> 00:40:56,480
To je pravzaprav nič boljši,
Ni boljšega sploh.

864
00:40:56,480 --> 00:41:00,810
>> Vendar pa je tretji pristop
Rad bi nas spodbujajo, da razmisli,

865
00:41:00,810 --> 00:41:02,970
ki je to.

866
00:41:02,970 --> 00:41:07,850
Torej predvidevam svoj seznam, zaradi enostavnosti
Ponovno je štiri, ena, tri,

867
00:41:07,850 --> 00:41:11,080
dvo le štiri številke.

868
00:41:11,080 --> 00:41:13,300
Ben je imel dobro intuicijo,
dobra človeška intuicija

869
00:41:13,300 --> 00:41:16,340
Prej, s katerim smo določena celotna
Seznam eventually-- vstavljanje vrste.

870
00:41:16,340 --> 00:41:18,020
coaxed sem naju skupaj.

871
00:41:18,020 --> 00:41:22,530
Ampak kaj je menijo, da je
Najenostavnejši način, da se določi ta seznam.

872
00:41:22,530 --> 00:41:24,110
>> Ta seznam ni razvrščen.

873
00:41:24,110 --> 00:41:26,130
Zakaj?

874
00:41:26,130 --> 00:41:31,920
V angleščini, razložiti, zakaj
to ni dejansko razporejene.

875
00:41:31,920 --> 00:41:33,400
Kaj to pomeni, ni treba sortirati?

876
00:41:33,400 --> 00:41:34,220
>> ŠTUDENT: To ni sekvenčno.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Malan: Ni sekvenčno.

878
00:41:34,990 --> 00:41:35,822
Daj mi primer.

879
00:41:35,822 --> 00:41:37,180
>> ŠTUDENT: Daj jih v zaporedju.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Malan: OK.

881
00:41:37,440 --> 00:41:38,790
Daj mi bolj poseben primer.

882
00:41:38,790 --> 00:41:39,832
>> ŠTUDENT: naraščajočem vrstnem redu.

883
00:41:39,832 --> 00:41:41,206
DAVID Malan: Ni naraščajoče vrstnem redu.

884
00:41:41,206 --> 00:41:42,100
Bodite bolj natančni.

885
00:41:42,100 --> 00:41:45,190
Ne vem, kaj misliš s naraščajoče.

886
00:41:45,190 --> 00:41:47,150
Kaj je narobe?

887
00:41:47,150 --> 00:41:49,930
>> ŠTUDENT: Najmanjši izmed
Številke ni v prvem prostoru.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Malan: Najmanjše število je
Ne v prvem prostoru.

889
00:41:51,140 --> 00:41:52,120
Bodite bolj natančni.

890
00:41:52,120 --> 00:41:55,000
Začenjam ujeti naprej.

891
00:41:55,000 --> 00:41:59,470
Računamo, vendar
kaj je v okvari tu?

892
00:41:59,470 --> 00:42:00,707
>> ŠTUDENT: Numerična zaporedje.

893
00:42:00,707 --> 00:42:02,040
DAVID Malan: Numerična zaporedje.

894
00:42:02,040 --> 00:42:04,248
Vsakdo je vrsta vodenja
je here-- zelo visoko raven.

895
00:42:04,248 --> 00:42:07,450
Samo mi dobesedno pove, kaj je
narobe kot pet let stari moči.

896
00:42:07,450 --> 00:42:08,310
>> ŠTUDENT: plus ena.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Malan: Kaj je to?

898
00:42:08,750 --> 00:42:09,610
>> ŠTUDENT: plus ena.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Malan: Kaj misliš s plus ena?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Daj mi drugo pet-year-old.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Kaj je narobe, mama?

904
00:42:18,330 --> 00:42:19,940
Kaj je narobe, oče?

905
00:42:19,940 --> 00:42:22,808
Kaj misliš da to ni urejeno?

906
00:42:22,808 --> 00:42:24,370
>> ŠTUDENT: To ni pravi kraj.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Malan: Kaj je
ni na pravem mestu?

908
00:42:25,580 --> 00:42:26,174
>> ŠTUDENT: Štiri.

909
00:42:26,174 --> 00:42:27,090
DAVID Malan: OK, dobro.

910
00:42:27,090 --> 00:42:29,110
Torej, štiri je ni tam, kjer bi morala biti.

911
00:42:29,110 --> 00:42:30,590
Še zlasti je to prav?

912
00:42:30,590 --> 00:42:33,000
Štiri in ena prva
dve številki vidim.

913
00:42:33,000 --> 00:42:34,930
Ali je to v redu?

914
00:42:34,930 --> 00:42:36,427
Ne, oni so v okvari, kajne?

915
00:42:36,427 --> 00:42:38,135
V bistvu, mislim zdaj
o računalniku, preveč.

916
00:42:38,135 --> 00:42:40,824
To lahko ogledate le na morda eno,
morda dve stvari na once--

917
00:42:40,824 --> 00:42:43,240
in dejansko samo ena stvar
hkrati pa je lahko vsaj

918
00:42:43,240 --> 00:42:45,790
poglej eno stvar potem
Naslednja stvar, tik ob njem.

919
00:42:45,790 --> 00:42:47,380
>> Torej so to, da bi?

920
00:42:47,380 --> 00:42:48,032
Seveda ne.

921
00:42:48,032 --> 00:42:48,740
Torej, veste kaj?

922
00:42:48,740 --> 00:42:51,020
Zakaj ne vzamemo otroka
ukrepe, ki določajo te težave

923
00:42:51,020 --> 00:42:53,410
namesto da bi te fancy
algoritmi, kot so Ben, kjer

924
00:42:53,410 --> 00:42:56,440
on je nekako pritrjevanje, ki ga
zanka po seznamu

925
00:42:56,440 --> 00:42:59,670
namesto da bi to, kar sem storil, kjer
Sem ga le nekako določen, ko gremo?

926
00:42:59,670 --> 00:43:03,650
Naj samo dobesedno zlomil navzdol
Pojem order-- številčnem vrstnem redu

927
00:43:03,650 --> 00:43:06,990
rečejo karkoli want--
v teh parne primerjave.

928
00:43:06,990 --> 00:43:07,590
>> Štiri in eden.

929
00:43:07,590 --> 00:43:09,970
Je to pravi red?

930
00:43:09,970 --> 00:43:11,310
Torej, kaj je popraviti.

931
00:43:11,310 --> 00:43:14,700
Ena in štiri, nato pa
bomo samo kopirajte to.

932
00:43:14,700 --> 00:43:15,560
Dobro, dobro.

933
00:43:15,560 --> 00:43:17,022
Popravil sem eno in štiri.

934
00:43:17,022 --> 00:43:18,320
Tri, dva?

935
00:43:18,320 --> 00:43:18,820
No.

936
00:43:18,820 --> 00:43:21,690
Naj moje besede ujemajo prste.

937
00:43:21,690 --> 00:43:23,695
Štiri in tri?

938
00:43:23,695 --> 00:43:27,930
>> To ni v redu, tako da bom
narediti eno, tri, štiri, dva.

939
00:43:27,930 --> 00:43:28,680
OK, dobro.

940
00:43:28,680 --> 00:43:32,310
Sedaj štiri in dve?

941
00:43:32,310 --> 00:43:33,370
Moramo popraviti tudi to.

942
00:43:33,370 --> 00:43:36,700
Torej ena, tri, dva, štiri.

943
00:43:36,700 --> 00:43:39,820
Tako je urejeno?

944
00:43:39,820 --> 00:43:43,170
Ne, ampak je bližje razporejene?

945
00:43:43,170 --> 00:43:48,930
>> To je, ker smo to določen
napaka, smo fiksni to napako,

946
00:43:48,930 --> 00:43:50,370
in mi določena to napako.

947
00:43:50,370 --> 00:43:52,420
Tako smo v osnovna tri napake verjetno.

948
00:43:52,420 --> 00:43:58,100
Še vedno pa ni res videti sortirani, toda
je objektivno bližje sortiranega

949
00:43:58,100 --> 00:44:00,080
ker smo določen nekatere od teh napak.

950
00:44:00,080 --> 00:44:02,047
>> Zdaj, kaj naj storim zdaj?

951
00:44:02,047 --> 00:44:03,630
Nekako dosegel konec seznama.

952
00:44:03,630 --> 00:44:05,680
Zdelo sem, da so določene
vse napake, toda ne.

953
00:44:05,680 --> 00:44:08,510
Ker v tem primeru, nekatere številke
morda vrela bližje

954
00:44:08,510 --> 00:44:10,410
na druge številke, ki
so še vedno v okvari.

955
00:44:10,410 --> 00:44:12,951
Torej, dajmo še enkrat, in bom
samo to na mestu tokrat.

956
00:44:12,951 --> 00:44:14,170
Ena in tri?

957
00:44:14,170 --> 00:44:14,720
V redu je.

958
00:44:14,720 --> 00:44:16,070
Tri, dva?

959
00:44:16,070 --> 00:44:17,560
Seveda ne, tako da je spremeniti.

960
00:44:17,560 --> 00:44:19,160
Torej dva, tri.

961
00:44:19,160 --> 00:44:21,340
Tri in štiri?

962
00:44:21,340 --> 00:44:24,370
In zdaj kaj je samo biti
še posebej občutljiv tukaj.

963
00:44:24,370 --> 00:44:26,350
Je urejeno?

964
00:44:26,350 --> 00:44:29,280
Vi ljudje vedo, da je urejeno.

965
00:44:29,280 --> 00:44:30,400
>> Moral bi poskusiti znova.

966
00:44:30,400 --> 00:44:31,900
Torej Olivia predlaga, da poskusite znova.

967
00:44:31,900 --> 00:44:32,530
Zakaj?

968
00:44:32,530 --> 00:44:35,810
Ker računalnik nima
razkošje naše človeške oči

969
00:44:35,810 --> 00:44:38,080
bi samo pogledal back-- OK, bom končal.

970
00:44:38,080 --> 00:44:41,610
Kako računalnik določi
da je ta seznam zdaj urejeno?

971
00:44:41,610 --> 00:44:44,590
Mehansko.

972
00:44:44,590 --> 00:44:47,650
>> Moral bi iti skozi
še enkrat, in le če

973
00:44:47,650 --> 00:44:51,190
ne delajo / najti nobene napake lahko
nato pa ugotoviti, računalnika, ja,

974
00:44:51,190 --> 00:44:51,980
smo na dobri poti.

975
00:44:51,980 --> 00:44:54,850
Tako ena in dve, dve in
tri, tri in štiri.

976
00:44:54,850 --> 00:44:58,030
Zdaj lahko dokončno reči, da je to
razporejene, ker sem naredil nobenih sprememb.

977
00:44:58,030 --> 00:45:01,940
Zdaj bi bilo napako in samo
neumno, če I, računalnik,

978
00:45:01,940 --> 00:45:05,640
vprašal še enkrat te iste vprašanja
pričakujejo različne odgovore.

979
00:45:05,640 --> 00:45:07,110
Ne bi smelo zgoditi.

980
00:45:07,110 --> 00:45:08,600
>> In zdaj je seznam razvrščeni.

981
00:45:08,600 --> 00:45:12,630
Na žalost, teče čas
Ta algoritem je tudi N na kvadrat.

982
00:45:12,630 --> 00:45:13,130
Zakaj?

983
00:45:13,130 --> 00:45:19,520
Ker imate n številke, in v
najslabšem primeru boste morali premakniti n številk

984
00:45:19,520 --> 00:45:23,637
n-krat, ker imate nadaljuj
nazaj, da preveri in morda popraviti

985
00:45:23,637 --> 00:45:24,220
te številke.

986
00:45:24,220 --> 00:45:26,280
In lahko naredimo bolj
formalna analiza, preveč.

987
00:45:26,280 --> 00:45:29,530
>> Torej, to je vse, da bi rekli, da smo sprejeti
trije različni pristopi, ena

988
00:45:29,530 --> 00:45:32,210
od njih takoj intuitivno
off kij iz Ben

989
00:45:32,210 --> 00:45:35,170
na mojo predlagano vključitev
vrste, da je ta

990
00:45:35,170 --> 00:45:38,540
kjer si nekako pozabimo
gozd za drevesa sprva.

991
00:45:38,540 --> 00:45:41,760
Ampak potem, če naredimo korak nazaj,
voila, smo določen vrstni pojem.

992
00:45:41,760 --> 00:45:43,824
Torej, to je, upal reči,
nižja raven morda

993
00:45:43,824 --> 00:45:45,740
kot nekateri od tistih drugih
algoritmi, ampak dajmo

994
00:45:45,740 --> 00:45:48,550
vidim, če ne moremo vizualizirati
te s pomočjo tega.

995
00:45:48,550 --> 00:45:51,450
>> Torej, to je nekaj lepih
programsko opremo, da je nekdo

996
00:45:51,450 --> 00:45:56,110
napisala s pomočjo pisane palice, ki je
naredili naslednje za nas.

997
00:45:56,110 --> 00:45:57,736
Vsaka od teh palic predstavlja številko.

998
00:45:57,736 --> 00:46:00,026
Višji bar, večji
število, manjši bar,

999
00:46:00,026 --> 00:46:00,990
manjše število.

1000
00:46:00,990 --> 00:46:05,880
Torej v najboljšem primeru želimo lepo piramido
kjer se začne mala in postane velika,

1001
00:46:05,880 --> 00:46:08,330
in da bi pomenilo, da
Te palice so razporejene.

1002
00:46:08,330 --> 00:46:11,200
Tako da sem šel naprej in izbrati,
na primer, Benova algoritem

1003
00:46:11,200 --> 00:46:13,990
first-- izbor vrste.

1004
00:46:13,990 --> 00:46:16,220
>> In opazili, kaj počne.

1005
00:46:16,220 --> 00:46:18,670
Način, ki so jih izbrali na
vizualizirati ta algoritem

1006
00:46:18,670 --> 00:46:22,090
je, da sem tako kot je bilo
hoja skozi moj seznam,

1007
00:46:22,090 --> 00:46:24,710
ta program je hoja
s svojega seznama številk,

1008
00:46:24,710 --> 00:46:28,160
poudarjanje v roza vsakem
Številka, ki jo gleda.

1009
00:46:28,160 --> 00:46:32,360
In kaj se bo zgodilo zdaj?

1010
00:46:32,360 --> 00:46:35,154
>> Najmanjše število, ki
I ali ben dalo nenadoma

1011
00:46:35,154 --> 00:46:36,820
dobi premakne na začetku seznama.

1012
00:46:36,820 --> 00:46:40,037
In zaznali so naredili izselijo
številka, ki je bil tam,

1013
00:46:40,037 --> 00:46:41,120
in to je popolnoma v redu.

1014
00:46:41,120 --> 00:46:42,600
Nisem dobil v tej ravni podrobnosti.

1015
00:46:42,600 --> 00:46:44,308
Vendar moramo dati
ta številka nekje,

1016
00:46:44,308 --> 00:46:47,775
zato smo samo preselili na
odprto mesto, ki je bilo ustvarjeno.

1017
00:46:47,775 --> 00:46:49,900
Tako da bom za pospešitev tega
gor, ker v nasprotnem primeru pa

1018
00:46:49,900 --> 00:46:51,871
postane zelo dolgočasno hitro.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animacija speed-- tam gremo.

1021
00:46:58,600 --> 00:47:01,850
Torej, zdaj enako načelo
Sem se uporabljajo, vendar si

1022
00:47:01,850 --> 00:47:06,540
Lahko začnete počutiti algoritem, če
bo, ali pa malo bolj jasno.

1023
00:47:06,540 --> 00:47:13,190
In to algoritem ima za posledico
izberete naslednji najmanjši element,

1024
00:47:13,190 --> 00:47:16,422
tako da boste začeli
videli, da ploščadi na levi strani.

1025
00:47:16,422 --> 00:47:19,130
In na vsaki ponovitvi, kot sem
predlagal, je pa malo manj dela.

1026
00:47:19,130 --> 00:47:21,921
To ni nujno, da gredo do konca
nazaj na levem koncu seznama

1027
00:47:21,921 --> 00:47:23,900
zato, ker je že
ve tisti, so razporejene.

1028
00:47:23,900 --> 00:47:28,129
Torej je nekako zdi, kot da je
pospeševanje, čeprav je vsak korak je

1029
00:47:28,129 --> 00:47:29,420
pri čemer enako količino časa.

1030
00:47:29,420 --> 00:47:31,600
Tam je samo manj korakov preostale.

1031
00:47:31,600 --> 00:47:35,240
In sedaj lahko nekako čutijo
Algoritem čiščenje konec njega,

1032
00:47:35,240 --> 00:47:37,040
in tudi zdaj je to urejeno.

1033
00:47:37,040 --> 00:47:41,620
>> Torej vstavljanje vrsta je vse narejeno.

1034
00:47:41,620 --> 00:47:43,600
Moram ponovno naključen array.

1035
00:47:43,600 --> 00:47:45,940
In opazil sem lahko samo
da ga randomizing,

1036
00:47:45,940 --> 00:47:50,630
in bomo dobili približevanje
enak pristop, urejanje z navadnim vstavljanjem.

1037
00:47:50,630 --> 00:47:55,050
Naj upočasni tukaj.

1038
00:47:55,050 --> 00:47:56,915
Začnimo da več.

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
>> Poglejmo preskočiti štiri.

1042
00:48:02,410 --> 00:48:03,200
No pa gremo.

1043
00:48:03,200 --> 00:48:04,190
Naključni so niz.

1044
00:48:04,190 --> 00:48:05,555
In tukaj smo go-- vstavljanje vrste.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Igrajo.

1047
00:48:12,800 --> 00:48:17,280
Opazili, da se ukvarjajo z vsako
element naleti takoj,

1048
00:48:17,280 --> 00:48:20,282
če pa sodi v
obvestilo o napačnem mestu

1049
00:48:20,282 --> 00:48:21,740
vse delo, ki ga je zgodilo.

1050
00:48:21,740 --> 00:48:24,700
Moramo ohraniti premika več
več elementov, da bi naredili prostor

1051
00:48:24,700 --> 00:48:27,340
za tistega, želimo vzpostaviti.

1052
00:48:27,340 --> 00:48:30,740
>> Torej smo s poudarkom na
levo konec le seznama.

1053
00:48:30,740 --> 00:48:34,460
Obvestilo nismo niti pogledal at-- mi
niso poudarjeno v roza nič

1054
00:48:34,460 --> 00:48:35,610
na desno.

1055
00:48:35,610 --> 00:48:38,180
Mi samo ukvarjajo z
težave, ko gremo,

1056
00:48:38,180 --> 00:48:40,430
vendar smo ustvariti veliko
delajo za nas še vedno.

1057
00:48:40,430 --> 00:48:44,410
In zato, če bi pospešili to gor
zdaj, da gredo do konca,

1058
00:48:44,410 --> 00:48:46,210
ima drugačen občutek, da je res.

1059
00:48:46,210 --> 00:48:50,150
To je samo usmerimo levo na koncu, ampak
tem malo več dela kot needed--

1060
00:48:50,150 --> 00:48:53,230
vrsta glajenja stvari
več, pritrjevanje stvari,

1061
00:48:53,230 --> 00:48:58,350
vendar se ukvarjajo na koncu z
vsak element eden naenkrat

1062
00:48:58,350 --> 00:49:07,740
dokler ne bomo dobili dobro the-- smo
vsi vemo, kako se bo to končalo,

1063
00:49:07,740 --> 00:49:09,700
tako da je malo underwhelming morda.

1064
00:49:09,700 --> 00:49:12,830
>> Toda seznam v end--
spoiler-- se bo urejeno.

1065
00:49:12,830 --> 00:49:15,300
Tako da je pogled na eni zadnji.

1066
00:49:15,300 --> 00:49:16,840
Ne moremo preskočiti zdaj.

1067
00:49:16,840 --> 00:49:18,000
Skoraj smo že tam.

1068
00:49:18,000 --> 00:49:19,980
Še dva, eden iti.

1069
00:49:19,980 --> 00:49:22,680
In voila.

1070
00:49:22,680 --> 00:49:23,450
Odlično.

1071
00:49:23,450 --> 00:49:27,220
>> Zdaj naredimo eno zadnjo,
ponovno randomizing z mehurček vrste.

1072
00:49:27,220 --> 00:49:31,690
In opazil sem, še posebej, če ga počasi
navzdol, se ta vodi swooping skozi.

1073
00:49:31,690 --> 00:49:36,830
Toda opazili samo naredi parno
comparisons-- vrste lokalnih rešitev.

1074
00:49:36,830 --> 00:49:39,050
Toda takoj, ko smo prišli do
konec seznama v roza,

1075
00:49:39,050 --> 00:49:40,690
kaj se dogaja, da imajo spet zgodilo?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ja, to se dogaja, da imajo za
začeti znova, ker je to le

1078
00:49:46,830 --> 00:49:49,870
fiksne Parne napake.

1079
00:49:49,870 --> 00:49:53,120
In da bi lahko še pokazala druge.

1080
00:49:53,120 --> 00:49:58,950
In tako, če pospeši to gor, boste
glej, da toliko, kot pove že samo ime,

1081
00:49:58,950 --> 00:50:01,870
manjša elements-- ali ne,
večji elements-- začenjajo

1082
00:50:01,870 --> 00:50:03,740
mehurček do vrha, če hočete.

1083
00:50:03,740 --> 00:50:07,380
In manjši elementi
začenja mehurček navzdol proti levi.

1084
00:50:07,380 --> 00:50:10,780
In res, da je vrsta
vizualni učinek kot dobro.

1085
00:50:10,780 --> 00:50:17,150
In tako da bo to na koncu zaključna
na zelo podoben način, preveč.

1086
00:50:17,150 --> 00:50:19,160
>> Nimamo spuščala
o tem eno.

1087
00:50:19,160 --> 00:50:21,010
Naj odpre to zdaj, preveč.

1088
00:50:21,010 --> 00:50:24,040
Obstaja še nekaj drugih sortiranje algoritmi
V svetu, nekateri od katerih

1089
00:50:24,040 --> 00:50:25,580
Tu so zajeti.

1090
00:50:25,580 --> 00:50:29,960
In še posebej za učence, ki niso
nujno vizualni ali matematične,

1091
00:50:29,960 --> 00:50:31,930
kot smo prej, smo lahko
tudi to narediti slušnega

1092
00:50:31,930 --> 00:50:34,210
če bomo povezali zvok s tem.

1093
00:50:34,210 --> 00:50:36,990
In samo za zabavo, tukaj je
nekaj različnih algoritmov,

1094
00:50:36,990 --> 00:50:40,950
in eden od njih še posebej si
bomo opazili, se imenuje "zlivanjem."

1095
00:50:40,950 --> 00:50:43,250
>> Je dejansko bistveno
boljši algoritem,

1096
00:50:43,250 --> 00:50:45,860
tako da zlivanjem, eden izmed
tisti, s katerimi boste videli,

1097
00:50:45,860 --> 00:50:49,170
ni red n kvadrat.

1098
00:50:49,170 --> 00:50:57,280
To je o vrstnem redu za n-krat dnevnik
N, ki je pravzaprav manjše in zato

1099
00:50:57,280 --> 00:50:58,940
hitrejši od tistih ostalih treh.

1100
00:50:58,940 --> 00:51:00,670
In tam je drugi par
neumno tisti, ki bomo videli.

1101
00:51:00,670 --> 00:51:01,933
>> Torej gremo z nekaj zvokom.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
To je vstavljanje razvrščanje, tako da še enkrat
to je samo ukvarjajo z elementi

1104
00:51:10,490 --> 00:51:13,420
ko pridejo.

1105
00:51:13,420 --> 00:51:17,180
To je mehurček vrste, tako da je
upoštevamo jim parov naenkrat.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
In spet, največji elementi
so prepihavanje do vrha.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Naslednji izbor vrste.

1110
00:51:41,710 --> 00:51:45,420
To je Benova algoritem, kjer
spet on izbiro iterativno

1111
00:51:45,420 --> 00:51:46,843
naslednji najmanjši element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
In še enkrat, zdaj lahko zares slišati, da
to je pospešilo, vendar le toliko, kolikor

1114
00:51:53,900 --> 00:51:58,230
saj počne vse manj
delo na vsaki ponovitvi.

1115
00:51:58,230 --> 00:52:04,170
To je hitrejši eno, urejanje z zlivanjem,
ki je razvrščanje skupin številk

1116
00:52:04,170 --> 00:52:05,971
jih skupaj in nato združevanje.

1117
00:52:05,971 --> 00:52:07,720
Torej look-- levo
pol je že urejeno.

1118
00:52:07,720 --> 00:52:14,165
>> Zdaj je razvrščanje v desno polovico, in
Zdaj pa se dogaja, da jih združiti v eno.

1119
00:52:14,165 --> 00:52:19,160
To je nekaj, kar se imenuje "Gnome vrste."

1120
00:52:19,160 --> 00:52:23,460
In lahko nekako videli, da
to se dogaja, naprej in nazaj,

1121
00:52:23,460 --> 00:52:27,950
določitvi dela malo tukaj in
tam, preden se nadaljuje z novo delo.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
In to je to.

1124
00:52:33,692 --> 00:52:36,400
Obstaja še ena vrsta, ki je
res samo za akademske namene

1125
00:52:36,400 --> 00:52:40,980
imenovano "neumen vrste", ki traja
vaše podatke, da razvrsti naključno,

1126
00:52:40,980 --> 00:52:43,350
in nato preveri če je razvrščen.

1127
00:52:43,350 --> 00:52:47,880
In če je ni, se ponovno razvrsti ga
naključno, preveri, če je to urejeno,

1128
00:52:47,880 --> 00:52:49,440
in če ne ponavlja.

1129
00:52:49,440 --> 00:52:52,660
In v teoriji, probabilistically
To bo popolna,

1130
00:52:52,660 --> 00:52:54,140
vendar po zelo malo časa.

1131
00:52:54,140 --> 00:52:56,930
To ni najbolj
učinkovitih algoritmov.

1132
00:52:56,930 --> 00:53:02,550
Tako da kakršna koli vprašanja o tistih
posebni algoritmi ali karkoli

1133
00:53:02,550 --> 00:53:04,720
je povezana tudi?

1134
00:53:04,720 --> 00:53:09,430
>> No, kaj je zdaj draži narazen, kaj vse
te vrstice so, da sem bila risba

1135
00:53:09,430 --> 00:53:15,090
in kaj sem ob predpostavki, da računalnik
lahko storite pod pokrovom.

1136
00:53:15,090 --> 00:53:18,650
Jaz bi trditi, da so vse te številke
Držim drawing-- ki jih potrebujejo, da bi dobili

1137
00:53:18,650 --> 00:53:21,330
shranjena nekje v spominu.

1138
00:53:21,330 --> 00:53:24,130
Bomo znebili tega fanta sedaj, preveč.

1139
00:53:24,130 --> 00:53:30,110
>> Tako kos pomnilnika je z
computer-- tako RAM DIMM

1140
00:53:30,110 --> 00:53:35,480
tisto, kar smo iskali včeraj, dual
inline spomin module-- izgleda takole.

1141
00:53:35,480 --> 00:53:39,370
In vsaka od teh malih črnih žetonov
je nekaj število bajtov, običajno.

1142
00:53:39,370 --> 00:53:44,380
In potem zlato nožice so všeč
žice, ki jo povezujejo z računalnikom,

1143
00:53:44,380 --> 00:53:47,521
in zelena silicijevega plošča je le
tisto, kar ohranja vse skupaj.

1144
00:53:47,521 --> 00:53:48,770
Torej, kaj to v resnici pomeni?

1145
00:53:48,770 --> 00:53:53,180
Če bi nekako sestaviti to isto sliko,
recimo, zaradi enostavnosti

1146
00:53:53,180 --> 00:53:55,280
da ta DIMM, dvojni
inline pomnilniški modul,

1147
00:53:55,280 --> 00:54:00,530
je eden GB RAM-a, en gigabajt
spomin, ki je, koliko bajtov skupaj?

1148
00:54:00,530 --> 00:54:02,100
Eden od gigabyte je, koliko bajtov?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Več kot 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 milijon.

1153
00:54:11,730 --> 00:54:14,570
Giga je milijard.

1154
00:54:14,570 --> 00:54:15,070
>> Sem laže?

1155
00:54:15,070 --> 00:54:16,670
lahko celo beremo etiketo?

1156
00:54:16,670 --> 00:54:19,920
To je dejansko 128
GB, tako da je več.

1157
00:54:19,920 --> 00:54:22,130
Vendar bomo to pretvarjamo
je samo en gigabajt.

1158
00:54:22,130 --> 00:54:25,640
Torej to pomeni, da je milijardo
bajtov pomnilnika, ki so na voljo, da me

1159
00:54:25,640 --> 00:54:29,770
ali 8 milijard bitov, vendar bomo
govoriti v smislu bajtov zdaj,

1160
00:54:29,770 --> 00:54:30,750
premikanje naprej.

1161
00:54:30,750 --> 00:54:36,330
>> Torej, kaj to pomeni, je to
Enobajtni, to je druga bajt,

1162
00:54:36,330 --> 00:54:38,680
To je še en bajt,
in če bomo res hoteli

1163
00:54:38,680 --> 00:54:43,280
da je specifična bi se morali
pripravi milijardo malo kvadratov.

1164
00:54:43,280 --> 00:54:44,320
Toda kaj to pomeni?

1165
00:54:44,320 --> 00:54:46,420
No, naj le povečavo
v to sliko.

1166
00:54:46,420 --> 00:54:50,900
Če imam nekaj, kar izgleda
kot je to sedaj, to je štiri bajte.

1167
00:54:50,900 --> 00:54:53,710
>> In tako sem lahko dal štiri številke tukaj.

1168
00:54:53,710 --> 00:54:54,990
Ena dve tri Štiri.

1169
00:54:54,990 --> 00:55:00,170
Ali pa bi dal štiri črke ali simbole.

1170
00:55:00,170 --> 00:55:02,620
"Zdravo!" bi šel tam,
ker je vsak od črk,

1171
00:55:02,620 --> 00:55:04,370
smo razpravljali prej,
mogoče predstaviti

1172
00:55:04,370 --> 00:55:06,650
osem bitov ali ASCII ali bajt.

1173
00:55:06,650 --> 00:55:09,370
Torej, z drugimi besedami, lahko
dal 8 milijard stvari v notranjosti

1174
00:55:09,370 --> 00:55:11,137
to eno palico spomina.

1175
00:55:11,137 --> 00:55:14,345
Zdaj kaj to pomeni, da se dajo stvari nazaj
nazaj nazaj v spomin, kot je ta?

1176
00:55:14,345 --> 00:55:17,330
To je tisto, kar je programer
bi klic "nizom."

1177
00:55:17,330 --> 00:55:21,250
V računalniškem programu, ne mislite
okoli osnovnega strojne opreme, samo po sebi.

1178
00:55:21,250 --> 00:55:24,427
Pravkar si mislijo o sebi, kot da imajo
dostop do milijardo bajtov vsoto,

1179
00:55:24,427 --> 00:55:26,010
in lahko karkoli želite z njim.

1180
00:55:26,010 --> 00:55:27,880
Ampak za udobje
je na splošno koristno

1181
00:55:27,880 --> 00:55:31,202
da pomnilniško pravico
drug poleg drugega takole.

1182
00:55:31,202 --> 00:55:33,660
Torej, če sem povečate this--
ker smo gotovo ne bo

1183
00:55:33,660 --> 00:55:39,310
pripraviti milijarde malo squares--
recimo, da je ta svet zastopa

1184
00:55:39,310 --> 00:55:40,610
da palico spomina zdaj.

1185
00:55:40,610 --> 00:55:43,800
In bom sestaviti toliko kot moja
dvojno podajo konča mi daje tukaj.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Torej, zdaj imamo palico
spomina na krovu

1188
00:55:52,300 --> 00:55:56,400
da je dobil en, dva, tri, štiri, pet,
šest, ena, dva, tri, štiri, pet, šest,

1189
00:55:56,400 --> 00:56:01,130
seven-- tako 42 bajtov
spomin na skupno zaslona.

1190
00:56:01,130 --> 00:56:01,630
Hvala.

1191
00:56:01,630 --> 00:56:02,838
Da, naredil moj aritmetično desno.

1192
00:56:02,838 --> 00:56:05,120
Torej 42 bajtov pomnilnika tukaj.

1193
00:56:05,120 --> 00:56:06,660
Torej, kaj to dejansko pomeni?

1194
00:56:06,660 --> 00:56:09,830
No, računalniški programer
bi dejansko splošno

1195
00:56:09,830 --> 00:56:12,450
razmišljati o tem spominu kot Adresabilni.

1196
00:56:12,450 --> 00:56:16,630
Z drugimi besedami, vsak izmed njih
lokacije v pomnilniku, v strojni opremi,

1197
00:56:16,630 --> 00:56:18,030
ima edinstven naslov.

1198
00:56:18,030 --> 00:56:22,020
>> To ni tako zapleten, kot One Brattle
Square, Cambridge, Mass., 02.138.

1199
00:56:22,020 --> 00:56:23,830
Namesto tega je samo številka.

1200
00:56:23,830 --> 00:56:27,930
To je bajt število nič, to je
ena, to je dve, to je tri,

1201
00:56:27,930 --> 00:56:30,327
in to je 41.

1202
00:56:30,327 --> 00:56:30,910
Počakaj minuto.

1203
00:56:30,910 --> 00:56:32,510
Mislil sem, da sem rekel 42 pred nekaj trenutki.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Začel sem štetja na nič,
tako da je dejansko pravilna.

1206
00:56:37,772 --> 00:56:40,980
Zdaj nimamo, da ga dejansko pripravi
kot omrežje, in če jo pripravijo kot mreža

1207
00:56:40,980 --> 00:56:43,520
Mislim, da stvari dejansko
dobili nekoliko zavajajoča.

1208
00:56:43,520 --> 00:56:46,650
Kaj programer bi,
v svojem lastnem umu,

1209
00:56:46,650 --> 00:56:50,310
na splošno misli o tem
pomnilnik, ki je tako kot trak,

1210
00:56:50,310 --> 00:56:53,340
kot kos samolepilnim trakom
da samo nadaljuje in v nedogled

1211
00:56:53,340 --> 00:56:54,980
ali dokler ne zmanjka pomnilnika.

1212
00:56:54,980 --> 00:56:59,200
Torej bolj običajen način pripraviti
in samo pomislite spomin

1213
00:56:59,200 --> 00:57:03,710
bi bilo, da je to bajt nič, ena,
dva, tri, nato pa pika, pika, pika.

1214
00:57:03,710 --> 00:57:07,650
In imaš 42 takih bajte skupaj, čeprav
čeprav fizično da bi lahko dejansko

1215
00:57:07,650 --> 00:57:09,480
je nekaj več, kot je ta.

1216
00:57:09,480 --> 00:57:12,850
>> Torej, če zdaj pomislim na vaš
spomin kot je ta, tako kot trak,

1217
00:57:12,850 --> 00:57:17,640
To je tisto, kar programer znova
bi zahtevala vrsto pomnilnika.

1218
00:57:17,640 --> 00:57:20,660
In če želite, da dejansko shranjevanje
nekaj v spominu računalnika,

1219
00:57:20,660 --> 00:57:23,290
vam na splošno storiti shranjevanje stvari
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Tako smo že govorili o številkah.

1221
00:57:25,010 --> 00:57:30,880
In ko sem hotel rešiti probleme
kot štiri, ena, tri, dva,

1222
00:57:30,880 --> 00:57:33,820
čeprav sem bil samo risanje
samo številke štiri, ena, tri,

1223
00:57:33,820 --> 00:57:39,490
dve na krovu, bi računalnik
Res so to nastavitev v spomin.

1224
00:57:39,490 --> 00:57:43,347
>> In kaj bi bilo zraven
dva v spominu računalnika?

1225
00:57:43,347 --> 00:57:44,680
No, ni odgovor na to.

1226
00:57:44,680 --> 00:57:45,770
Mi res ne vem.

1227
00:57:45,770 --> 00:57:48,200
In tako dolgo, dokler
računalnik ne potrebuje,

1228
00:57:48,200 --> 00:57:51,440
da ni nujno, da je vseeno, kaj je naslednji
s številkami to ne briga.

1229
00:57:51,440 --> 00:57:55,130
In ko sem že povedal, da je v računalniku
lahko ogledate le na en naslov v času,

1230
00:57:55,130 --> 00:57:56,170
To je nekako, zakaj.

1231
00:57:56,170 --> 00:57:59,490
>> Ni v nasprotju z zapisom
predvajalnik in glavo branje

1232
00:57:59,490 --> 00:58:03,030
samo, da lahko pogled na določeno
groove v fizičnem stare šole zapisu

1233
00:58:03,030 --> 00:58:06,500
naenkrat, podobno
lahko računalnik hvala

1234
00:58:06,500 --> 00:58:09,810
njegove CPU in njenih
Intel nabor ukazov,

1235
00:58:09,810 --> 00:58:12,480
med katere navodili
bere iz pomnilnika

1236
00:58:12,480 --> 00:58:15,590
ali shranite v memory--
Računalnik lahko ogledate le

1237
00:58:15,590 --> 00:58:19,210
na enem mestu pri time--
včasih njihove kombinacije,

1238
00:58:19,210 --> 00:58:21,770
ampak res samo eno lokacijo naenkrat.

1239
00:58:21,770 --> 00:58:24,770
Torej, ko smo počeli
ti različni algoritmi,

1240
00:58:24,770 --> 00:58:28,110
Ne bom samo pisni obliki v
vacuum-- štiri, ena, tri, dva.

1241
00:58:28,110 --> 00:58:30,849
Te številke dejansko pripadajo
nekje fizično v spomin.

1242
00:58:30,849 --> 00:58:32,890
Tako da so mali
tranzistorji ali nekakšen

1243
00:58:32,890 --> 00:58:35,840
elektronike pod
hood shranjevanje teh vrednot.

1244
00:58:35,840 --> 00:58:40,460
>> In skupaj, koliko bitov
vpleten zdaj, samo da bo jasno?

1245
00:58:40,460 --> 00:58:45,580
Torej, to je štiri bajte, ali
zdaj je 32 bitov skupaj.

1246
00:58:45,580 --> 00:58:49,280
Tako da so dejansko 32 ničel in
tisti, ki sestavljajo te štiri stvari.

1247
00:58:49,280 --> 00:58:52,070
Še več tukaj, ampak
spet nam ni mar za to.

1248
00:58:52,070 --> 00:58:55,120
>> Sedaj pa vprašam drugo
Vprašanje uporablja pomnilnik,

1249
00:58:55,120 --> 00:58:57,519
ker to na koncu
dneva v variance.

1250
00:58:57,519 --> 00:59:00,310
Ne glede na to, kaj lahko naredimo z
računalnik, na koncu dneva

1251
00:59:00,310 --> 00:59:02,560
strojna oprema je še vedno
Enako pod pokrovom.

1252
00:59:02,560 --> 00:59:04,670
Kako bi shraniti besedo tukaj?

1253
00:59:04,670 --> 00:59:09,710
No, beseda v računalniku kot
"zdravo!" bodo shranjeni, tako kot je ta.

1254
00:59:09,710 --> 00:59:12,300
In če si hotel daljše
beseda, lahko preprosto

1255
00:59:12,300 --> 00:59:19,120
prepišejo da in nekaj reči
kot "zdravo" in trgovina, ki tu.

1256
00:59:19,120 --> 00:59:23,930
>> In tako tudi tu, to contiguousness
je pravzaprav prednost,

1257
00:59:23,930 --> 00:59:26,530
ker računalnik lahko samo
bere od desne proti levi.

1258
00:59:26,530 --> 00:59:28,680
Ampak tukaj je vprašanje.

1259
00:59:28,680 --> 00:59:33,480
V okviru te besede,
h-e-l-l-ol, klicaj,

1260
00:59:33,480 --> 00:59:38,740
kako bi računalnik ve, kje
Beseda se začne in kje se beseda konča?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
V okviru številk
kako deluje računalnik

1263
00:59:43,800 --> 00:59:48,396
vem, kako dolgo zaporedje
številke je, ali če se začne?

1264
00:59:48,396 --> 00:59:50,270
No, se izkaže out--
in ne bo šel preveč

1265
00:59:50,270 --> 00:59:54,970
na tej ravni detail--
računalniki premakniti stvari okrog v spomin

1266
00:59:54,970 --> 00:59:57,800
dobesedno s pomočjo teh naslovov.

1267
00:59:57,800 --> 01:00:02,080
Torej, v računalniku, če ste
pisanje kode za shranjevanje stvari

1268
01:00:02,080 --> 01:00:05,800
kot povedano, kaj ste
res počne je tipkanje

1269
01:00:05,800 --> 01:00:11,320
izrazi, ki se spomnite, kje v
pomnilnik računalnika te besede.

1270
01:00:11,320 --> 01:00:14,370
Torej mi naredil zelo,
zelo preprost primer.

1271
01:00:14,370 --> 01:00:18,260
>> Bom, da gredo naprej in
odpirajo preprost program besedila,

1272
01:00:18,260 --> 01:00:20,330
in bom za ustvarjanje
datoteka z imenom hello.c.

1273
01:00:20,330 --> 01:00:22,849
Večina teh informacij smo
ne bo šel v zelo podrobno,

1274
01:00:22,849 --> 01:00:25,140
ampak bom napisati
Program v istem jeziku,

1275
01:00:25,140 --> 01:00:31,140
C. To je veliko bolj zastrašujoče,
Jaz bi trditi, kot Scratch,

1276
01:00:31,140 --> 01:00:32,490
ampak to je v duhu zelo podobna.

1277
01:00:32,490 --> 01:00:34,364
V bistvu, ti Skodrana
braces-- lahko nekako

1278
01:00:34,364 --> 01:00:37,820
mislim, kaj sem storil, kot je ta.

1279
01:00:37,820 --> 01:00:39,240
>> Naredimo to, pravzaprav.

1280
01:00:39,240 --> 01:00:45,100
Ko je zelena zastava kliknili,
naredite naslednje.

1281
01:00:45,100 --> 01:00:50,210
Želim natisniti "zdravo."

1282
01:00:50,210 --> 01:00:51,500
Torej, to je zdaj psevdokoda.

1283
01:00:51,500 --> 01:00:53,000
Jaz sem nekako zabrisane linije.

1284
01:00:53,000 --> 01:00:56,750
V C, ta jezik govorim
o, ta linija print zdravo

1285
01:00:56,750 --> 01:01:01,940
dejansko postane "printf" s
nekateri oklepaje ter podpičjem.

1286
01:01:01,940 --> 01:01:03,480
>> Ampak to je točno isto idejo.

1287
01:01:03,480 --> 01:01:06,730
In to zelo uporabniku prijazen
"Ko je zelena zastava kliknili" postane

1288
01:01:06,730 --> 01:01:10,182
veliko bolj starinski "int main nična."

1289
01:01:10,182 --> 01:01:12,890
In to je res ni kartiranje,
tako da sem le, da bo prezreti, da je.

1290
01:01:12,890 --> 01:01:17,210
Toda zaviti oklepaji so všeč
ukrivljenih kosov sestavljanke je to všeč.

1291
01:01:17,210 --> 01:01:18,700
>> Tako da lahko nekako uganiti.

1292
01:01:18,700 --> 01:01:22,357
Tudi če ste nikoli programirano pred,
kaj ta program verjetno ne?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Verjetno natisne zdravo
s klicajem.

1295
01:01:28,000 --> 01:01:29,150
>> Torej, poskusimo to.

1296
01:01:29,150 --> 01:01:30,800
Bom, da ga shranite.

1297
01:01:30,800 --> 01:01:34,000
To pa je spet zelo
staro šolsko okolje.

1298
01:01:34,000 --> 01:01:35,420
Ne morem klikniti, ne morem vleči.

1299
01:01:35,420 --> 01:01:36,910
Moram vpisovati ukaze.

1300
01:01:36,910 --> 01:01:41,320
Torej, želim teči svoj program, tako
Jaz bi to naredil, kot hello.c.

1301
01:01:41,320 --> 01:01:42,292
To je datoteka sem tekel.

1302
01:01:42,292 --> 01:01:43,500
Toda počakaj, sem manjka korak.

1303
01:01:43,500 --> 01:01:46,470
Kaj smo rekli, je potrebno
korak za jezik kot C?

1304
01:01:46,470 --> 01:01:49,470
Pravkar sem napisal vir
kodo, ampak kaj potrebujem?

1305
01:01:49,470 --> 01:01:50,670
Ja, rabim prevajalnik.

1306
01:01:50,670 --> 01:01:57,670
Torej, na mojem Mac tukaj, imam
program, imenovan GCC, GNU C prevajalnik,

1307
01:01:57,670 --> 01:02:03,990
ki mi omogoča, da naredite this-- vrsti
moje izvorno kodo v, ga bomo klic,

1308
01:02:03,990 --> 01:02:04,930
strojni kodi.

1309
01:02:04,930 --> 01:02:10,180
>> In vidim, da je
Ponovno, kot sledi, to

1310
01:02:10,180 --> 01:02:14,090
so ničle in tisti I samo
ustvarjena iz moje izvorne kode,

1311
01:02:14,090 --> 01:02:15,730
vse ničel in enic.

1312
01:02:15,730 --> 01:02:17,770
In če želim teči
moj program-- se zgodi

1313
01:02:17,770 --> 01:02:23,010
da se imenuje a.out za
zgodovinski reasons-- "zdravo."

1314
01:02:23,010 --> 01:02:24,070
Sem ga lahko ponovno zagnati.

1315
01:02:24,070 --> 01:02:25,690
Živijo živijo živijo.

1316
01:02:25,690 --> 01:02:27,430
In zdi se, da se dela.

1317
01:02:27,430 --> 01:02:31,000
>> Toda to pomeni, da nekje v moji
pomnilnik računalnika so besede

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-ol, klicaj.

1319
01:02:35,279 --> 01:02:38,070
In se je izkazalo, tako kot prahi,
kakšen računalnik bi običajno

1320
01:02:38,070 --> 01:02:40,550
tako da se ne ve, kje
stvari začnejo in end-- je

1321
01:02:40,550 --> 01:02:42,460
bo dal poseben simbol tukaj.

1322
01:02:42,460 --> 01:02:46,064
In konvencija je dal
Številka ničelne konec besede

1323
01:02:46,064 --> 01:02:48,230
tako da boste vedeli, kje je
dejansko konča, tako da si

1324
01:02:48,230 --> 01:02:52,750
ne vodijo bolj tiskanje
znakov, kot bi dejansko nameravajo.

1325
01:02:52,750 --> 01:02:55,400
>> Toda takeaway tukaj, čeprav
čeprav je to dokaj Skrivnosten,

1326
01:02:55,400 --> 01:02:58,140
je, da je na koncu
relativno enostavna.

1327
01:02:58,140 --> 01:03:04,550
Dobil si neke vrste traku, prazno
Prostor, na katerem lahko pišete pisma.

1328
01:03:04,550 --> 01:03:07,150
Vi preprosto morali imeti
posebno oznako, kot samovoljno

1329
01:03:07,150 --> 01:03:10,316
število nič, da dajo na koncu
tvoje besede, tako da računalnik ve,

1330
01:03:10,316 --> 01:03:13,410
oh, naj neha tiskati po
Vidim klicaj.

1331
01:03:13,410 --> 01:03:16,090
Ker je naslednja stvar, ki obstaja
je ASCII vrednost nič,

1332
01:03:16,090 --> 01:03:19,125
ali null značaj kot
kdo bi ga poklical.

1333
01:03:19,125 --> 01:03:21,500
Ampak tam je nekako problem
tu, in kaj je vrniti nazaj

1334
01:03:21,500 --> 01:03:23,320
številkam za trenutek.

1335
01:03:23,320 --> 01:03:28,720
Recimo, da sem naredil, v resnici,
imajo vrsto številk,

1336
01:03:28,720 --> 01:03:30,730
in domnevam, da je
Program pišem je

1337
01:03:30,730 --> 01:03:34,680
kot redovalnice za učitelja
in učiteljev v razredu.

1338
01:03:34,680 --> 01:03:38,720
In ta program mu omogoča
vnesti rezultate svojih učencev

1339
01:03:38,720 --> 01:03:39,960
na kvizov.

1340
01:03:39,960 --> 01:03:43,750
In domnevam, da študent dobi
100 na prvi kviz, morda

1341
01:03:43,750 --> 01:03:49,920
kot 80 na naslednjega, nato pa
75, nato pa 90 na četrtem kviz.

1342
01:03:49,920 --> 01:03:54,150
>> Tako da na tej točki v zgodbo,
matrika z velikostjo štiri.

1343
01:03:54,150 --> 01:03:58,470
Tam je absolutno več pomnilnika v
računalnik, vendar matrika, tako rekoč

1344
01:03:58,470 --> 01:04:00,350
z velikostjo štiri.

1345
01:04:00,350 --> 01:04:06,060
Recimo zdaj, da učitelj želi
dodeliti peti kviz v razredu.

1346
01:04:06,060 --> 01:04:08,510
No, ena od stvari, ki jih
ali ona se dogaja, da imajo opraviti

1347
01:04:08,510 --> 01:04:10,650
je zdaj trgovina dodatno vrednost tukaj.

1348
01:04:10,650 --> 01:04:15,490
Ampak, če array ima učitelj
ustvarjena v tem programu je velikosti za,

1349
01:04:15,490 --> 01:04:22,440
eden od problema z matrike je to
ne moreš kar naprej tako, da spomin.

1350
01:04:22,440 --> 01:04:26,470
Ker kaj če drugi del od
Program ima besedo "hej" tam?

1351
01:04:26,470 --> 01:04:29,650
>> Z drugimi besedami, moj spomin je
uporabljen za nič v programu.

1352
01:04:29,650 --> 01:04:33,250
In če vnaprej sem tipkal v, hej,
Želim vhod štirih rezultatov kviza,

1353
01:04:33,250 --> 01:04:34,784
morda gre tukaj in tukaj.

1354
01:04:34,784 --> 01:04:37,700
In če ste nenadoma premislite
kasneje in da hočem peti kviz

1355
01:04:37,700 --> 01:04:40,872
ocena, ne moreš samo
ga kjerkoli želite,

1356
01:04:40,872 --> 01:04:42,580
ker kaj pa če je to
pomnilnik se uporablja

1357
01:04:42,580 --> 01:04:45,990
nekaj else-- kakšen drug program,
ali kakšno drugo značilnost programa

1358
01:04:45,990 --> 01:04:46,910
da delate?

1359
01:04:46,910 --> 01:04:50,650
Tako da boste morali razmišljati vnaprej
kako želite shraniti podatke,

1360
01:04:50,650 --> 01:04:54,480
ker zdaj ste naslikal
sami v digitalno kotu.

1361
01:04:54,480 --> 01:04:57,280
>> Tako učitelj bi lahko namesto
pravijo pri pisanju programa

1362
01:04:57,280 --> 01:04:59,360
za shranjevanje njegovo ali njeno
stopnje, veš kaj?

1363
01:04:59,360 --> 01:05:04,180
Bom, da zahteva,
pri pisanju svoj program,

1364
01:05:04,180 --> 01:05:12,070
da Rad nič, ena, dva, tri,
štiri, pet, šest, osem stopenj skupaj.

1365
01:05:12,070 --> 01:05:15,320
Torej ena, dva, tri, štiri,
pet, šest, sedem, osem.

1366
01:05:15,320 --> 01:05:18,612
Učitelj lahko samo over-dodeliti
spomin pri pisanju svoj program,

1367
01:05:18,612 --> 01:05:19,570
in rekel, veste kaj?

1368
01:05:19,570 --> 01:05:22,236
Nikoli ne bom dodeliti več
kot osem kvizov v semestru.

1369
01:05:22,236 --> 01:05:23,130
To je samo nor.

1370
01:05:23,130 --> 01:05:24,470
Nikoli ne bom dodeli da.

1371
01:05:24,470 --> 01:05:28,270
Tako, da je on ali ona ima na ta način
prožnost za shranjevanje študentskih rezultate,

1372
01:05:28,270 --> 01:05:33,010
kot 75, 90, in morda eno dodatno, kadar
študent dobil dodaten kredit, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Ampak, če učitelj ne
uporablja te tri prostore,

1374
01:05:36,130 --> 01:05:38,860
tam je intuitiven takeaway tukaj.

1375
01:05:38,860 --> 01:05:41,410
On ali ona je samo zapravljaš prostor.

1376
01:05:41,410 --> 01:05:44,790
Torej, z drugimi besedami, da je to
Skupno kompromis v programiranju

1377
01:05:44,790 --> 01:05:48,241
kjer lahko dodeli
natanko toliko pomnilnika, kot želite,

1378
01:05:48,241 --> 01:05:51,490
Glavo, ki je, da ste super
efficient-- si niso potratne

1379
01:05:51,490 --> 01:05:54,640
na all-- vendar je slaba stran, ki
je kaj, če si premisliš, kadar

1380
01:05:54,640 --> 01:05:58,780
s pomočjo programa, ki ga želite shraniti
več podatkov, kot bi bilo prvotno predvideno.

1381
01:05:58,780 --> 01:06:03,030
>> Mogoče je rešitev, potem
pisati programe na tak način

1382
01:06:03,030 --> 01:06:05,605
da se porabi več pomnilnika
kot jih dejansko potrebujejo.

1383
01:06:05,605 --> 01:06:07,730
Na ta način ne boš
teči v ta problem,

1384
01:06:07,730 --> 01:06:09,730
ampak si pa potratna.

1385
01:06:09,730 --> 01:06:12,960
In več pomnilnika vaš program uporablja,
kot smo razpravljali včeraj, manj

1386
01:06:12,960 --> 01:06:15,410
pomnilnika, ki je na voljo
za druge programe,

1387
01:06:15,410 --> 01:06:18,790
prej računalnik lahko počasen
navzdol zaradi navideznega pomnilnika.

1388
01:06:18,790 --> 01:06:22,670
In zato je idealna rešitev bi lahko bila, kaj?

1389
01:06:22,670 --> 01:06:24,610
>> Pod-razdeljevanje zdi slabo.

1390
01:06:24,610 --> 01:06:27,030
Over-prirejanje zdi slabo.

1391
01:06:27,030 --> 01:06:31,120
Torej, kaj bi lahko bila boljša rešitev?

1392
01:06:31,120 --> 01:06:32,390
Prerazporeditev.

1393
01:06:32,390 --> 01:06:33,590
Bolj dinamično.

1394
01:06:33,590 --> 01:06:37,520
Ne se prisiliti, da izberejo
priori, na začetku, kaj hočeš.

1395
01:06:37,520 --> 01:06:41,370
In gotovo ne preveč dodeliti,
da ne bi ti bilo potratno.

1396
01:06:41,370 --> 01:06:45,770
>> In tako bi dosegli ta cilj, smo
treba metati to strukturo podatkov,

1397
01:06:45,770 --> 01:06:48,100
tako rekoč proč.

1398
01:06:48,100 --> 01:06:51,080
In kaj programer
se običajno uporabljajo

1399
01:06:51,080 --> 01:06:55,940
je nekaj, kar ti ni
matrika ampak povezani seznam.

1400
01:06:55,940 --> 01:07:00,860
Z drugimi besedami, on ali ona bo
začeli razmišljati o svojem spominu

1401
01:07:00,860 --> 01:07:05,280
kot čemer koli obliki, ki jih
lahko pripravi na naslednji način.

1402
01:07:05,280 --> 01:07:08,520
Če hočem shraniti eno številko v
program-- tako da je september,

1403
01:07:08,520 --> 01:07:12,600
Dal sem moji učenci kviz; hočem
za shranjevanje prve kviz učencev,

1404
01:07:12,600 --> 01:07:16,220
in so dobili 100 na it-- I
bom vprašal svoj računalnik,

1405
01:07:16,220 --> 01:07:19,540
s pomočjo programa, ki sem jih
napisan za en kos pomnilnika.

1406
01:07:19,540 --> 01:07:22,570
In bom shranili
Številka 100 v njem, in to je to.

1407
01:07:22,570 --> 01:07:24,820
>> Potem pa nekaj tednov kasneje
ko sem dobil svoj drugi kviz,

1408
01:07:24,820 --> 01:07:27,890
in je čas, da tip
V tem 90%, bom

1409
01:07:27,890 --> 01:07:32,129
vprašati računalnik, hej, računalnik,
Lahko sem še en kos pomnilnika?

1410
01:07:32,129 --> 01:07:34,170
To se dogaja, da mi to
prazen kos pomnilnika.

1411
01:07:34,170 --> 01:07:39,370
Bom dal v številko 90,
ampak v mojem programu tako ali other--

1412
01:07:39,370 --> 01:07:42,100
in ne bomo skrbeti
sintaksa za this-- rabim

1413
01:07:42,100 --> 01:07:44,430
nekako veriga te stvari skupaj.

1414
01:07:44,430 --> 01:07:47,430
In jih bom verigo skupaj z
Izgleda puščico tukaj.

1415
01:07:47,430 --> 01:07:50,050
>> Tretji kviz, ki pride gor,
Sem hotel reči, hej, računalnik,

1416
01:07:50,050 --> 01:07:51,680
daj mi še en kos pomnilnika.

1417
01:07:51,680 --> 01:07:54,660
In bom dal dol
kar je bilo, kot 75,

1418
01:07:54,660 --> 01:07:56,920
in moram verigo tem
skupaj zdaj nekako.

1419
01:07:56,920 --> 01:08:00,290
Četrta kviz pride mimo, in morda
da je proti koncu semestra.

1420
01:08:00,290 --> 01:08:03,140
In v tej točki moje programa
lahko uporablja pomnilnik

1421
01:08:03,140 --> 01:08:05,540
po vsem mestu, po vsej fizično.

1422
01:08:05,540 --> 01:08:08,170
In tako samo za brcne, da sem
dogaja, da pripravi to naprej

1423
01:08:08,170 --> 01:08:11,260
quiz-- sem pozabil, kaj je bilo; jaz
mislim, morda 80 ali something--

1424
01:08:11,260 --> 01:08:12,500
Tako tukaj.

1425
01:08:12,500 --> 01:08:15,920
>> Ampak to je v redu, ker je slikovno
Bom, da pripravi te vrstice.

1426
01:08:15,920 --> 01:08:19,063
Z drugimi besedami, v resnici,
strojne opreme računalnika,

1427
01:08:19,063 --> 01:08:20,979
Prvi rezultat morda
na koncu sem, ker je to

1428
01:08:20,979 --> 01:08:22,529
takoj na začetku semestra.

1429
01:08:22,529 --> 01:08:25,810
Naslednjič morda na koncu tukaj
ker je malo časa minilo

1430
01:08:25,810 --> 01:08:27,210
in program ohranja teče.

1431
01:08:27,210 --> 01:08:30,060
Naslednji rezultat, ki je bil
75, lahko tukaj.

1432
01:08:30,060 --> 01:08:33,420
In zadnji rezultat morda
80, ki je tukaj.

1433
01:08:33,420 --> 01:08:38,729
>> Torej, v resnici, fizično, bi to lahko bilo
kaj spomin računalnika izgleda.

1434
01:08:38,729 --> 01:08:41,569
Vendar to ni uporaben mentalna
paradigma za računalniški programer.

1435
01:08:41,569 --> 01:08:44,649
Zakaj bi morali skrbeti, če
heck vaši podatki se konča?

1436
01:08:44,649 --> 01:08:46,200
samo želite shraniti podatke.

1437
01:08:46,200 --> 01:08:49,390
>> To je nekako tako kot naši razpravi
prej črpanja kocke.

1438
01:08:49,390 --> 01:08:52,200
Zakaj ti je mar, kaj
kota je kocke

1439
01:08:52,200 --> 01:08:53,740
in kako moraš obrniti, da ga pripravi?

1440
01:08:53,740 --> 01:08:54,950
Pravkar si želijo kocko.

1441
01:08:54,950 --> 01:08:57,359
Prav tu, vas
hočejo redovalnice.

1442
01:08:57,359 --> 01:08:59,559
Pravkar si želeli, da razmišljajo o
to kot seznam številk.

1443
01:08:59,559 --> 01:09:01,350
Koga briga, kako je
izvaja v strojno opremo?

1444
01:09:01,350 --> 01:09:05,180
>> Torej abstrakcija zdaj
je ta slika tukaj.

1445
01:09:05,180 --> 01:09:07,580
To je povezano seznama, kot je
programer bi ga poklical,

1446
01:09:07,580 --> 01:09:10,640
če imate
seznam, seveda številk.

1447
01:09:10,640 --> 01:09:14,990
Vendar je to povezano slikovno
s pomočjo teh puščic,

1448
01:09:14,990 --> 01:09:18,510
in vse te puščice are-- pod
pokrov, če ste radovedni,

1449
01:09:18,510 --> 01:09:23,210
opozarjajo, da je naša fizične strojne opreme
naslovi nič, ena, dva, tri, štiri.

1450
01:09:23,210 --> 01:09:28,465
Vse te puščice so se kot zemljevid
ali smeri, kjer je po 90 is-- zdaj

1451
01:09:28,465 --> 01:09:29,090
Moram štetje.

1452
01:09:29,090 --> 01:09:31,750
>> Nič, ena, dva, tri,
štiri, pet, šest, sedem.

1453
01:09:31,750 --> 01:09:35,640
Izgleda, da 90 je na
Naslov številka spominskega sedem.

1454
01:09:35,640 --> 01:09:38,460
Vse te puščice so se
kot majhen kos papirja

1455
01:09:38,460 --> 01:09:42,439
da se daje navodila na
program, ki pravi, da sledijo temu zemljevid

1456
01:09:42,439 --> 01:09:43,880
priti do lokacije sedem.

1457
01:09:43,880 --> 01:09:46,680
In tam boste našli
študent drugega kviz ocena.

1458
01:09:46,680 --> 01:09:52,100
Medtem, 75--, če sem še to,
To je sedem, osem, devet, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Ta druga puščica pravkar predstavlja
zemljevid na pomnilniško lokacijo 15.

1461
01:09:59,080 --> 01:10:02,550
Ampak še enkrat, programer na splošno ne
Ne skrbi za to raven podrobnosti.

1462
01:10:02,550 --> 01:10:05,530
In v večini vsakem programiranju
jezik danes, programer

1463
01:10:05,530 --> 01:10:10,490
sploh ne bo vedel, kje v pomnilniku
te številke dejansko so.

1464
01:10:10,490 --> 01:10:14,830
Vse, on ali ona mora skrbeti, je
da so nekako povezane skupaj

1465
01:10:14,830 --> 01:10:18,390
v podatkovno strukturo, kot je ta.

1466
01:10:18,390 --> 01:10:21,580
>> Vendar se izkaže, da niso
da bi dobili preveč strokovno.

1467
01:10:21,580 --> 01:10:27,430
Ampak samo zato, ker smo lahko morda
privoščiti, da bi to razpravo tukaj,

1468
01:10:27,430 --> 01:10:33,630
Predpostavimo, da smo ponovno
to vprašanje tukaj za matrike.

1469
01:10:33,630 --> 01:10:35,780
Poglejmo, če smo žal dogaja tukaj.

1470
01:10:35,780 --> 01:10:42,950
To je 100, 90, 75 in 80.

1471
01:10:42,950 --> 01:10:44,980
>> Naj na kratko, da to trditev.

1472
01:10:44,980 --> 01:10:48,980
To je matrika in enkrat,
pereče značilnost array

1473
01:10:48,980 --> 01:10:52,400
je, da je vse vaše podatke nazaj
na hrbtni strani v memory-- dobesedno

1474
01:10:52,400 --> 01:10:56,830
en bajt ali morda štiri bajte,
nekateri določeno število bajtov stran.

1475
01:10:56,830 --> 01:11:00,710
V povezanem seznamu, ki lahko črpamo
kot je ta, pod pokrovom, ki

1476
01:11:00,710 --> 01:11:02,000
ve, kje je ta stvar?

1477
01:11:02,000 --> 01:11:03,630
Da sploh ne potrebujejo, da teče, kot je ta.

1478
01:11:03,630 --> 01:11:06,050
Nekateri podatki so lahko
nazaj na levo, tam.

1479
01:11:06,050 --> 01:11:07,530
Sploh ne vem.

1480
01:11:07,530 --> 01:11:15,430
>> In tako z vrsto, imate
Funkcija znan kot bralno.

1481
01:11:15,430 --> 01:11:20,570
In kaj bralno sredstvo je
da lahko računalnik skoči takoj

1482
01:11:20,570 --> 01:11:22,730
na katero koli mesto v matriki.

1483
01:11:22,730 --> 01:11:23,580
Zakaj?

1484
01:11:23,580 --> 01:11:26,000
Ker računalnik ve
da je prva lokacija

1485
01:11:26,000 --> 01:11:29,540
nič, ena, dva, tri.

1486
01:11:29,540 --> 01:11:33,890
>> In tako, če želite, da gredo iz
ta element na naslednji element,

1487
01:11:33,890 --> 01:11:36,099
dobesedno, v
um računalnika, dodajte eno.

1488
01:11:36,099 --> 01:11:39,140
Če želite iti na tretji element,
dodajte one-- naslednji element, samo

1489
01:11:39,140 --> 01:11:40,290
dodali.

1490
01:11:40,290 --> 01:11:42,980
Vendar pa v tej različici
zgodbe, domnevam

1491
01:11:42,980 --> 01:11:46,080
računalnik je trenutno iščejo
na ali se ukvarjajo s številko 100.

1492
01:11:46,080 --> 01:11:49,770
Kako priti do naslednjega
razred v redovalnice?

1493
01:11:49,770 --> 01:11:52,560
>> Moraš vzeti sedem
koraki, ki je poljubna.

1494
01:11:52,560 --> 01:11:58,120
Da bi prišli do naslednjega, morate
sprejeti še osem korakov, da bi dobili do 15.

1495
01:11:58,120 --> 01:12:02,250
Z drugimi besedami, to ni
stalna razlika med številkami,

1496
01:12:02,250 --> 01:12:04,857
in zato je prav da prevzame
Računalnik več časa, je točka.

1497
01:12:04,857 --> 01:12:06,940
Računalnik ima za iskanje
v pomnilniku, da

1498
01:12:06,940 --> 01:12:08,990
da bi našli tisto, kar iščete.

1499
01:12:08,990 --> 01:12:14,260
>> Torej, ker je matrika kaže, da je
hitro podatki structure-- ker vas

1500
01:12:14,260 --> 01:12:17,610
Lahko dobesedno pač enostavno aritmetično
in dobili, če želite, z dodajanjem enega,

1501
01:12:17,610 --> 01:12:21,300
za instance-- povezan seznam,
ste žrtvovati to funkcijo.

1502
01:12:21,300 --> 01:12:24,020
Ne moreš kar iti iz prve
na drugi do tretji do četrti.

1503
01:12:24,020 --> 01:12:25,240
Moraš slediti zemljevid.

1504
01:12:25,240 --> 01:12:28,160
Moraš sprejeti več ukrepov
priti do tistih vrednot, ki so

1505
01:12:28,160 --> 01:12:30,230
Zdi se, da dodajanje stroškov.

1506
01:12:30,230 --> 01:12:35,910
Torej smo plačuje ceno, ampak kaj je bilo
funkcija, ki je bil Dan išče tukaj?

1507
01:12:35,910 --> 01:12:38,110
Kaj povezan seznam
očitno nam omogočajo, da ne,

1508
01:12:38,110 --> 01:12:40,240
ki je bila izvor
to predvsem zgodba?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Točno tako.

1511
01:12:43,830 --> 01:12:46,220
Dinamični velikost nanjo.

1512
01:12:46,220 --> 01:12:48,040
Mi lahko dodamo na ta seznam.

1513
01:12:48,040 --> 01:12:51,430
Mi lahko tudi skrči seznam, tako
da smo le z uporabo toliko pomnilnika

1514
01:12:51,430 --> 01:12:55,560
kot dejansko želimo in tako
smo nikoli preveč razdeljevanje.

1515
01:12:55,560 --> 01:12:58,470
>> Zdaj pa samo, da je res nit-izbirčen,
tam je skrito stroškov.

1516
01:12:58,470 --> 01:13:01,980
Zato se nikoli ne pusti me prepričal
si, da je to prepričljiv kompromis.

1517
01:13:01,980 --> 01:13:04,190
Še en skriti strošek tukaj.

1518
01:13:04,190 --> 01:13:06,550
Korist, mora biti jasno,
je, da smo dobili dinamiko.

1519
01:13:06,550 --> 01:13:10,359
Če želim še en element, da lahko samo
ga pripravi in ​​dal več tam.

1520
01:13:10,359 --> 01:13:12,150
In potem sem ga lahko poveže
s sliko tod

1521
01:13:12,150 --> 01:13:14,970
ker je tukaj, še enkrat, če sem
sam naslikal v kotu,

1522
01:13:14,970 --> 01:13:19,410
če kaj drugega se že uporablja
spomin tu, sem od sreče.

1523
01:13:19,410 --> 01:13:21,700
Sem sam naslikal v kotu.

1524
01:13:21,700 --> 01:13:24,390
>> Toda tisto, kar je skrito
stalo na tej sliki?

1525
01:13:24,390 --> 01:13:27,690
To ni samo količina
Čas, ki je potreben

1526
01:13:27,690 --> 01:13:29,870
iti od tu do tu,
kar je sedem korakov, nato

1527
01:13:29,870 --> 01:13:32,820
Osem korakov, ki jih je več kot ena.

1528
01:13:32,820 --> 01:13:34,830
Kaj je še skritih stroškov?

1529
01:13:34,830 --> 01:13:35,440
Ne samo čas.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Dodatne informacije
potrebno za dosego to sliko.

1532
01:13:49,940 --> 01:13:53,210
>> Ja, to karto, ti malo zapisov o
papir, kot sem vedno znova opisujejo kot.

1533
01:13:53,210 --> 01:13:55,650
To arrows-- to ni zastonj.

1534
01:13:55,650 --> 01:13:57,660
Computer-- veš
kar ima računalnik.

1535
01:13:57,660 --> 01:13:58,790
Ima ničle in narave.

1536
01:13:58,790 --> 01:14:03,170
Če želite predstavlja puščico ali A
map ali več, boste potrebovali nekaj pomnilnika.

1537
01:14:03,170 --> 01:14:05,950
Torej drugi ceno, ki jo
plačati za povezani seznam,

1538
01:14:05,950 --> 01:14:09,070
skupni računalništva
virov, je tudi prostor.

1539
01:14:09,070 --> 01:14:11,710
>> In res je tako, tako pogosto,
med kompromisi

1540
01:14:11,710 --> 01:14:15,580
pri oblikovanju programske opreme inženiring
Sistemi za čas in space--

1541
01:14:15,580 --> 01:14:18,596
sta dva izmed svojih sestavin, dva
vaših najdražjih sestavin.

1542
01:14:18,596 --> 01:14:21,220
To me stanejo več časa
ker moram upoštevati ta zemljevid,

1543
01:14:21,220 --> 01:14:25,730
vendar pa je že tudi mi stanejo več prostora
ker imam, da bo ta zemljevid okoli.

1544
01:14:25,730 --> 01:14:28,730
Torej upanje, kot smo jih nekako
obravnavali kot včeraj in danes,

1545
01:14:28,730 --> 01:14:31,720
je, da so koristi
bodo večje od stroškov.

1546
01:14:31,720 --> 01:14:33,870
>> Vendar ni očitna rešitev tukaj.

1547
01:14:33,870 --> 01:14:35,870
Mogoče je better--
a la hitro in umazano,

1548
01:14:35,870 --> 01:14:38,660
kot Kareem predlagano earlier--
metati spomin na problem.

1549
01:14:38,660 --> 01:14:42,520
Samo kupiti več pomnilnika, mislim manj
težko o reševanju problema,

1550
01:14:42,520 --> 01:14:44,595
in ga rešiti na lažji način.

1551
01:14:44,595 --> 01:14:46,720
In celo prej, ko
smo se pogovarjali o kompromisi,

1552
01:14:46,720 --> 01:14:49,190
ni bilo prostor
računalnik in čas.

1553
01:14:49,190 --> 01:14:51,810
To je bil čas za razvijalce, ki
še en vir.

1554
01:14:51,810 --> 01:14:54,829
>> Torej še enkrat, da je to ravnotežja
poskuša odločiti, katere od teh stvari

1555
01:14:54,829 --> 01:14:55,870
ste pripravljeni porabiti?

1556
01:14:55,870 --> 01:14:57,380
Ki je najcenejši?

1557
01:14:57,380 --> 01:15:01,040
Ki prinaša boljše rezultate?

1558
01:15:01,040 --> 01:15:01,540
Ja?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Prav zares.

1561
01:15:12,580 --> 01:15:15,970
V tem primeru, če ste
predstavljajo številke v maps--

1562
01:15:15,970 --> 01:15:18,820
to so ti v številnih jezikih
"kazalci" ali "naslovi" -

1563
01:15:18,820 --> 01:15:20,390
to je dvakrat več prostora.

1564
01:15:20,390 --> 01:15:24,390
To ne bi smelo biti tako slabo, kot dvojna, če
zdaj smo samo shranjevanje številk.

1565
01:15:24,390 --> 01:15:27,410
Denimo, da smo bili shranjevanje
zapisov bolnikov v hospital--

1566
01:15:27,410 --> 01:15:30,870
tako imena Pierson je, telefonske številke,
številke socialnega zavarovanja, zdravnik

1567
01:15:30,870 --> 01:15:31,540
Zgodovina.

1568
01:15:31,540 --> 01:15:34,160
To polje je lahko veliko,
veliko večji, pri čemer

1569
01:15:34,160 --> 01:15:38,000
majhen malo kazalec, naslov
Naslednji element-- to ni nič takega.

1570
01:15:38,000 --> 01:15:40,620
To je tako obroben
stalo ni pomembno.

1571
01:15:40,620 --> 01:15:43,210
Toda v tem primeru, ja, to je podvojitev.

1572
01:15:43,210 --> 01:15:45,290
Dobro vprašanje.

1573
01:15:45,290 --> 01:15:47,900
>> Spregovorimo o časovnem a
malo bolj konkretno.

1574
01:15:47,900 --> 01:15:50,380
Kaj je čas teče
iskanja ta seznam?

1575
01:15:50,380 --> 01:15:53,640
Recimo, da sem želel iskanje
skozi vse razrede učencev,

1576
01:15:53,640 --> 01:15:55,980
in tam je n ocene
V tej strukturi podatkov.

1577
01:15:55,980 --> 01:15:58,830
Tudi tu lahko sposodim
Besednjak prej.

1578
01:15:58,830 --> 01:16:00,890
To je linearna struktura podatkov.

1579
01:16:00,890 --> 01:16:04,570
>> Big O n je tisto, kar je potrebno, da bi dobili
na koncu te strukture podatkov,

1580
01:16:04,570 --> 01:16:08,410
whereas-- in nismo videli
To before-- matrika vam daje

1581
01:16:08,410 --> 01:16:13,555
kar se imenuje konstanta čas, kar pomeni,
en korak ali dva koraka ali 10 steps--

1582
01:16:13,555 --> 01:16:14,180
ni važno.

1583
01:16:14,180 --> 01:16:15,440
To je osnovna številka.

1584
01:16:15,440 --> 01:16:17,440
To nima nič opraviti z
velikost polja.

1585
01:16:17,440 --> 01:16:20,130
In razlog za to,
še enkrat, je bralno-pisalnega.

1586
01:16:20,130 --> 01:16:23,180
Računalnik lahko samo takoj
skok na drugo mesto,

1587
01:16:23,180 --> 01:16:27,770
ker so vsi enaki
oddaljenost od vsega drugega.

1588
01:16:27,770 --> 01:16:29,112
Ni vpleten razmišljanje.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
V redu.

1591
01:16:32,400 --> 01:16:39,230
Torej, če sem lahko, naj poskušajo
slikati dve končne slike.

1592
01:16:39,230 --> 01:16:42,830
Zelo pogost en znan kot hash tabelo.

1593
01:16:42,830 --> 01:16:51,120
Torej motivirati to razpravo,
Naj razmišljati o tem, kako to storiti.

1594
01:16:51,120 --> 01:16:52,610
>> Torej, kaj pa je to?

1595
01:16:52,610 --> 01:16:55,160
Denimo, da je problem
želimo zdaj rešiti

1596
01:16:55,160 --> 01:16:58,360
izvaja v dictionary--
tako cel kup angleških besed

1597
01:16:58,360 --> 01:16:59,330
ali karkoli.

1598
01:16:59,330 --> 01:17:02,724
In cilj je, da bi lahko odgovorili
vprašanja obliki je to beseda?

1599
01:17:02,724 --> 01:17:04,640
Torej hočeš, da izvajanje
črkovalnik, le

1600
01:17:04,640 --> 01:17:07,220
kot fizični slovar
da si lahko ogledate stvari v.

1601
01:17:07,220 --> 01:17:10,490
Recimo, da bi to naredili s paleto.

1602
01:17:10,490 --> 01:17:12,590
Jaz bi to lahko naredil.

1603
01:17:12,590 --> 01:17:20,756
>> In domnevam besede so jabolko
in banana in melona.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
In ne morem misliti sadja
ki se začnejo z d, tako da smo pravkar

1606
01:17:26,465 --> 01:17:27,590
dogaja, da imajo tri sadje.

1607
01:17:27,590 --> 01:17:31,510
Torej, to je množica, in smo
shranjevanje vseh teh besed

1608
01:17:31,510 --> 01:17:34,200
V tem slovarju kot matrike.

1609
01:17:34,200 --> 01:17:39,350
Vprašanje je torej, kako še
lahko shranite te informacije?

1610
01:17:39,350 --> 01:17:43,160
>> No, jaz sem nekako varanje tukaj, ker
vsako od teh črk v besede

1611
01:17:43,160 --> 01:17:44,490
je res posameznik bajt.

1612
01:17:44,490 --> 01:17:46,740
Torej, če sem res želela biti
nit-izbirčen, da bi moral res

1613
01:17:46,740 --> 01:17:49,600
je treba tako, da to gor v veliko
manjše kose pomnilnika,

1614
01:17:49,600 --> 01:17:51,289
in lahko storimo ravno to.

1615
01:17:51,289 --> 01:17:53,580
Ampak bomo zašli v
enak problem kot prej.

1616
01:17:53,580 --> 01:17:56,674
Kaj pa, če, kot Merriam Webster ali Oxford
počne vsak year-- dodajo besede

1617
01:17:56,674 --> 01:17:59,340
na dictionary-- ne bomo
nujno želijo slikati sebe

1618
01:17:59,340 --> 01:18:00,780
v kotu z vrsto?

1619
01:18:00,780 --> 01:18:05,710
>> Torej, namesto, morda pametnejši pristop
je dal jabolko v svojem vozlišču ali polje

1620
01:18:05,710 --> 01:18:11,190
kot bi rekli, banana, in
potem tukaj imamo melona.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
In smo niz te stvari skupaj.

1623
01:18:16,790 --> 01:18:19,980
To je torej matrika, in
to je povezani seznam.

1624
01:18:19,980 --> 01:18:23,300
Če ne more povsem videti, je samo
pravi: "Niz", in ta pravi, da "seznam".

1625
01:18:23,300 --> 01:18:25,780
>> Torej imamo enake
Natančne vprašanja, kot prej,

1626
01:18:25,780 --> 01:18:28,600
pri čemer imamo zdaj
dinamika v našem povezani seznam.

1627
01:18:28,600 --> 01:18:31,090
Vendar imamo dokaj počasno slovar.

1628
01:18:31,090 --> 01:18:32,870
Recimo, da želite poiskati besedo.

1629
01:18:32,870 --> 01:18:35,430
To mi lahko traja veliko O n
koraki, ker beseda morda

1630
01:18:35,430 --> 01:18:37,840
so vse poti na koncu
seznam, kot melone.

1631
01:18:37,840 --> 01:18:40,600
In se izkaže, da
v programiranje, razvrščanje

1632
01:18:40,600 --> 01:18:42,700
na sveti gral podatkov
strukture, je nekaj

1633
01:18:42,700 --> 01:18:46,620
ki vam omogoča stalen
Čas kot niz

1634
01:18:46,620 --> 01:18:50,870
vendar to še vedno vam daje dinamiko.

1635
01:18:50,870 --> 01:18:52,940
>> Tako lahko imamo najboljše iz obeh svetov?

1636
01:18:52,940 --> 01:18:55,570
In res, da je nekaj
imenuje hash tabela

1637
01:18:55,570 --> 01:18:59,320
ki vam omogoča, da natančno
da, čeprav približno.

1638
01:18:59,320 --> 01:19:03,140
Razpršene tabele je Ljubitelj
struktura podatkov, ki jih

1639
01:19:03,140 --> 01:19:06,340
moremo misliti kot
Kombinacija array--

1640
01:19:06,340 --> 01:19:12,390
in bom, da ga pripravi
kot this-- in povezanih seznamov

1641
01:19:12,390 --> 01:19:17,310
da bom pripravi takole tukaj.

1642
01:19:17,310 --> 01:19:19,760
>> In kako ta stvar
dela je, kot sledi.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Če now-- this hash table--
je moj tretji struktura podatkov,

1645
01:19:29,540 --> 01:19:32,590
in želim, da shranite
besede v tem, da ne

1646
01:19:32,590 --> 01:19:35,440
želi le shraniti vse
besede back to back to back to back.

1647
01:19:35,440 --> 01:19:37,430
Želim vzvoda nekaj
podatek

1648
01:19:37,430 --> 01:19:40,330
o besedah, ki bo pustil
mi ga dobili, če je hitrejši.

1649
01:19:40,330 --> 01:19:43,666
>> Torej, glede na besede jabolko
in banane in melone,

1650
01:19:43,666 --> 01:19:45,040
Namenoma sem izbrala te besede.

1651
01:19:45,040 --> 01:19:45,340
Zakaj?

1652
01:19:45,340 --> 01:19:47,631
Kaj je nekako v osnovi
razlikuje glede na tri?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Kaj je jasno?

1655
01:19:51,484 --> 01:19:52,900
Začnejo z različnimi črkami.

1656
01:19:52,900 --> 01:19:53,900
>> Torej, veste kaj?

1657
01:19:53,900 --> 01:19:57,120
Namesto da bi vse moje besede
enako vedro, tako rekoč

1658
01:19:57,120 --> 01:20:00,390
kot v enem dolgem seznamu, zakaj ne
Sem vsaj poskusiti optimizacijo

1659
01:20:00,390 --> 01:20:04,180
in da moje sezname 26/01 tako dolgo.

1660
01:20:04,180 --> 01:20:07,440
Prepričljivih optimizacija
morda, zakaj pa ne

1661
01:20:07,440 --> 01:20:10,650
Jaz-- pri vstavljanju besede
v to strukturo podatkov

1662
01:20:10,650 --> 01:20:14,300
v spominu računalnika, zakaj
ne bom dal vse "A" besede, tukaj,

1663
01:20:14,300 --> 01:20:17,270
vsi "b" besede tukaj,
in vse "c" besede so tukaj?

1664
01:20:17,270 --> 01:20:24,610
Torej, to konča dajanje jabolko
tukaj, banana tukaj, melone tukaj,

1665
01:20:24,610 --> 01:20:25,730
in tako naprej.

1666
01:20:25,730 --> 01:20:31,700
>> In če imam dodaten
Beseda like-- kaj drugega?

1667
01:20:31,700 --> 01:20:36,640
Jabolko, banana, hruška.

1668
01:20:36,640 --> 01:20:39,370
Kdo misli iz sadja
ki se začne z a, b ali c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- popolna.

1670
01:20:40,570 --> 01:20:43,990
To se bo končalo tukaj.

1671
01:20:43,990 --> 01:20:47,530
In tako se zdi, da imajo
nekoliko boljša rešitev,

1672
01:20:47,530 --> 01:20:50,820
ker zdaj, če hočem
za iskanje jabolko, sem

1673
01:20:50,820 --> 01:20:53,200
first-- jaz ne le potop
v svojo podatkovno strukturo.

1674
01:20:53,200 --> 01:20:54,850
Ne potopite v spomin mojega računalnika.

1675
01:20:54,850 --> 01:20:56,530
Sem prvi pogled na prvo črko.

1676
01:20:56,530 --> 01:20:58,610
>> In to je tisto, kar računalnik
znanstvenik bi rekel.

1677
01:20:58,610 --> 01:21:00,760
Si hash v svojo podatkovno strukturo.

1678
01:21:00,760 --> 01:21:04,100
Vzamete vhod, ki je v
V tem primeru je beseda, kot jabolko.

1679
01:21:04,100 --> 01:21:07,150
Jo proučiti
prva črka v tem primeru

1680
01:21:07,150 --> 01:21:08,340
s čimer je razpršitev.

1681
01:21:08,340 --> 01:21:10,950
Razprševanje je splošen izraz, s katerim
vzameš nekaj kot vhod

1682
01:21:10,950 --> 01:21:12,116
in jih proizvajajo nekatere izhod.

1683
01:21:12,116 --> 01:21:15,090
In izhod s tem
Primer je lokacija

1684
01:21:15,090 --> 01:21:18,150
želite iskati, prvi
lokacija, druga lokacija, tretji.

1685
01:21:18,150 --> 01:21:22,160
Torej, vhod je jabolko,
proizvodnja je prva.

1686
01:21:22,160 --> 01:21:25,054
Vhod je banana je
Izhod mora biti drugi.

1687
01:21:25,054 --> 01:21:27,220
Vhod je melone,
proizvodnja mora biti tretji.

1688
01:21:27,220 --> 01:21:30,320
Vhod je borovnica je
Izhod bi moral spet drugi.

1689
01:21:30,320 --> 01:21:34,010
In to je tisto, kar vam pomaga, da
bližnjice skozi spomin

1690
01:21:34,010 --> 01:21:39,050
da bi prišli do besede
ali podatke bolj učinkovito.

1691
01:21:39,050 --> 01:21:43,330
>> Zdaj to zmanjša našega časa potencialno
toliko, kot eden od 26,

1692
01:21:43,330 --> 01:21:45,850
ker če predpostavimo, da vas
imajo toliko "A" besede, kot so "Z"

1693
01:21:45,850 --> 01:21:48,080
besede, kot so "Q" besed, ki
ni res realistic--

1694
01:21:48,080 --> 01:21:50,830
boste imeli nagnjenost čez
nekatere črke alphabet--

1695
01:21:50,830 --> 01:21:53,204
vendar pa bi bilo to primarni
pristop, ki ne omogočajo

1696
01:21:53,204 --> 01:21:55,930
da si veliko hitreje priti do besede.

1697
01:21:55,930 --> 01:21:59,660
In v resnici, prefinjeno
Program je Googlovo sveta,

1698
01:21:59,660 --> 01:22:02,180
Facebooks od world--
bi jih uporabili razpršene tabele

1699
01:22:02,180 --> 01:22:03,740
za veliko različnih namenov.

1700
01:22:03,740 --> 01:22:06,590
Vendar pa ne bi bil tako naiven, kot je
samo poglej na prvo črko

1701
01:22:06,590 --> 01:22:09,700
v jabolko ali banana ali
hrušk ali melone,

1702
01:22:09,700 --> 01:22:13,420
saj, kot lahko vidite, to
Seznami lahko še vedno dobite dolgo.

1703
01:22:13,420 --> 01:22:17,130
>> In zato je to morda še vedno neke
od linear-- tako nekako počasi,

1704
01:22:17,130 --> 01:22:19,980
kot z velikim O n
da smo razpravljali prej.

1705
01:22:19,980 --> 01:22:25,290
Torej, kaj je resnično dober hash tabela bo
do-- bo imel veliko večji nabor.

1706
01:22:25,290 --> 01:22:28,574
In bo uporabila veliko bolj
prefinjen razprševanje funkcija,

1707
01:22:28,574 --> 01:22:30,240
tako, da se ne samo pogled na "a."

1708
01:22:30,240 --> 01:22:35,480
Morda je videti na "a-p-p-l-e" in
nekako pretvori tistih pet črk

1709
01:22:35,480 --> 01:22:38,400
v kraju, kjer
jabolko je treba shraniti.

1710
01:22:38,400 --> 01:22:42,660
Mi samo naivno z črko "a"
sam, saj je lepo in enostavno.

1711
01:22:42,660 --> 01:22:44,600
>> Toda razpršene tabele, v
konec, si lahko zamislite

1712
01:22:44,600 --> 01:22:47,270
ali kot kombinacija
niz, od katerih vsaka

1713
01:22:47,270 --> 01:22:51,700
je povezan seznam, ki v najboljšem primeru
mora biti čim krajše.

1714
01:22:51,700 --> 01:22:54,364
In to ni očitna rešitev.

1715
01:22:54,364 --> 01:22:57,280
V resnici, velik del fino nastavitev
da gre na pod pokrovom kadar

1716
01:22:57,280 --> 01:22:59,654
izvajanje tovrstnih
izpopolnjene podatkovne strukture

1717
01:22:59,654 --> 01:23:01,640
je tisto, kar je prav
dolžina polja?

1718
01:23:01,640 --> 01:23:03,250
Kaj je prava funkcija hash?

1719
01:23:03,250 --> 01:23:04,830
Kako hranite stvari v spomin?

1720
01:23:04,830 --> 01:23:07,249
>> Toda zavedamo, kako hitro
tovrstna razprava

1721
01:23:07,249 --> 01:23:10,540
stopnjevalo, in sicer tako daleč, da je vrsta
za nad glavo na tej točki, ki

1722
01:23:10,540 --> 01:23:11,360
je v redu.

1723
01:23:11,360 --> 01:23:18,820
Ampak smo začeli, odpoklic, z resnično
nekaj nizko stopnjo in elektronsko.

1724
01:23:18,820 --> 01:23:20,819
In zato je to spet je to
Tema abstrakcije,

1725
01:23:20,819 --> 01:23:23,610
kjer je nekoč začnete jemati
odobrena, OK, imam it-- obstaja

1726
01:23:23,610 --> 01:23:26,680
fizičnega pomnilnika, OK, razumem, vsak
fizično lokacijo, ki ima naslov,

1727
01:23:26,680 --> 01:23:29,910
OK, razumem, da lahko predstavljajo
ti naslovi so arrows--

1728
01:23:29,910 --> 01:23:34,650
lahko zelo hitro, da imajo
bolj zapletene pogovorov, ki

1729
01:23:34,650 --> 01:23:38,360
Na koncu se zdi, da se nam omogoči
za reševanje problemov, kot so iskanje

1730
01:23:38,360 --> 01:23:41,620
Sortiranje in bolj učinkovito.

1731
01:23:41,620 --> 01:23:44,190
In prepričani, too--
ker sem to mislim

1732
01:23:44,190 --> 01:23:48,700
je najgloblja smo šli v nekatere
od teh tem CS proper-- smo jih na

1733
01:23:48,700 --> 01:23:51,880
opravljeno v enem dnevu in pol na to
poudariti tisto, kar bi običajno stori preko

1734
01:23:51,880 --> 01:23:55,520
potek osem tednov v semestru.

1735
01:23:55,520 --> 01:23:59,670
>> Vsa vprašanja glede te teme?

1736
01:23:59,670 --> 01:24:01,100
Ne?

1737
01:24:01,100 --> 01:24:01,940
V redu.

1738
01:24:01,940 --> 01:24:05,610
Torej, zakaj ne se ustavimo tam,
začetek kosilo nekaj minut prej,

1739
01:24:05,610 --> 01:24:07,052
nadaljeval v skoraj eno uro?

1740
01:24:07,052 --> 01:24:08,760
In bom ostajal za
malo z vprašanji.

1741
01:24:08,760 --> 01:24:11,343
Potem bom moral iti
traja nekaj klicev, če je to v redu.

1742
01:24:11,343 --> 01:24:15,000
Bom vklopite glasbo v tem času,
ampak mora kosilo je za vogalom.

1743
01:24:15,000 --> 01:24:17,862