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

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Bine.

3
00:00:00,460 --> 00:00:01,094
Ne-am intors.

4
00:00:01,094 --> 00:00:04,260
Deci, în acest segment de programare ce
Am crezut că vom face este un amestec de lucruri.

5
00:00:04,260 --> 00:00:06,340
Unu, face un pic
de ceva hands-on,

6
00:00:06,340 --> 00:00:08,690
deși folosind un mai jucaus
environment-- programare

7
00:00:08,690 --> 00:00:11,620
una care este demonstrativ de
exact genul de idei

8
00:00:11,620 --> 00:00:14,220
am vorbit despre,
dar un pic mai mult formal.

9
00:00:14,220 --> 00:00:18,200
Doi, uita-te la unele dintre
modalitățile mai tehnice

10
00:00:18,200 --> 00:00:21,520
că un programator ar rezolva de fapt
probleme cum ar fi problema căutarea

11
00:00:21,520 --> 00:00:24,530
pe care ne-am uitat la mai înainte și
De asemenea, o mai fundamental

12
00:00:24,530 --> 00:00:26,020
problemă interesantă de sortare.

13
00:00:26,020 --> 00:00:28,840
>> Tocmai ne-am asumat de a lua merge
că această carte de telefon a fost sortate,

14
00:00:28,840 --> 00:00:31,980
dar că singur este de fapt un fel de
problemă greu cu mai multe moduri diferite

15
00:00:31,980 --> 00:00:32,479
să-l rezolve.

16
00:00:32,479 --> 00:00:34,366
Așa că vom folosi acești
o clasă de probleme

17
00:00:34,366 --> 00:00:36,740
reprezentativ pentru lucruri care
ar putea fi rezolvată în general.

18
00:00:36,740 --> 00:00:38,980
Și apoi vom vorbi
despre în detaliu ceea ce

19
00:00:38,980 --> 00:00:42,360
sunt numite date structures--
moduri, cum ar fi liste crescator legate

20
00:00:42,360 --> 00:00:46,290
și tabele de dispersie și copaci, care
un programator ar fapt

21
00:00:46,290 --> 00:00:48,890
utilizează și în general, utilizați
pe o tablă pentru a picta

22
00:00:48,890 --> 00:00:51,840
o imagine a ceea ce el sau ea
prevede pentru punerea în aplicare a

23
00:00:51,840 --> 00:00:52,980
unele bucată de software.

24
00:00:52,980 --> 00:00:55,130
>> Așa că hai să facem mâinile-pe prima porțiune.

25
00:00:55,130 --> 00:01:00,090
Deci, a lua doar mâini murdare cu un
mediu numit scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Acesta este un instrument pe care le folosim
în clasa noastră de licență.

27
00:01:02,636 --> 00:01:04,510
Chiar dacă este proiectat
pentru vârstele de 12 și în sus,

28
00:01:04,510 --> 00:01:07,570
l-am folosi pentru sus
o parte din faptul că destul de un pic

29
00:01:07,570 --> 00:01:10,020
deoarece este un frumos, distractiv
mod grafic de învățare

30
00:01:10,020 --> 00:01:12,160
un pic ceva despre programare.

31
00:01:12,160 --> 00:01:17,600
Așa că cap la acea adresă URL, în cazul în care vă
ar trebui să vedeți o pagină destul ca acest lucru,

32
00:01:17,600 --> 00:01:23,330
și mergeți mai departe și faceți clic
Alăturați-vă zero la dreapta sus

33
00:01:23,330 --> 00:01:28,300
și alege un nume de utilizator și o
parola și în cele din urmă du-te

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

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

36
00:01:32,165 --> 00:01:34,665
Am crezut că o să folosesc acest lucru ca
oportunitate în primul rând pentru a arăta acest lucru.

37
00:01:34,665 --> 00:01:39,120
O întrebare a venit în timpul pauzei
despre ce codul de fapt arată.

38
00:01:39,120 --> 00:01:41,315
Si am vorbit
în timpul pauzei despre C,

39
00:01:41,315 --> 00:01:45,060
în particular un particular--
nivel inferior într-o limbă mai veche.

40
00:01:45,060 --> 00:01:47,750
Și tocmai am făcut-o rapid
Căutarea Google pentru a găsi codul C

41
00:01:47,750 --> 00:01:51,574
pentru căutare binară, algoritmul pe care noi
folosit pentru a căuta cartea de telefon mai devreme.

42
00:01:51,574 --> 00:01:54,240
Acest exemplu special, desigur,
nu caută o carte de telefon.

43
00:01:54,240 --> 00:01:57,840
Ea doar caută un întreg buchet de
Numerele din memoria calculatorului.

44
00:01:57,840 --> 00:02:01,000
Dar, dacă doriți să obțineți doar vizual
sentiment de o programare reală

45
00:02:01,000 --> 00:02:05,370
limba arata ca, se pare
un pic ceva de genul asta.

46
00:02:05,370 --> 00:02:09,759
Deci, este vorba despre 20-plus,
30 de linii de cod,

47
00:02:09,759 --> 00:02:12,640
dar conversația am
au fost cu peste pauza

48
00:02:12,640 --> 00:02:16,000
a fost despre modul în care acest fapt
devine transformat in zero-uri și altele

49
00:02:16,000 --> 00:02:19,200
și dacă nu se poate pur și simplu că reveni
procesa și du-te de la zero-uri și altele

50
00:02:19,200 --> 00:02:20,210
înapoi la cod.

51
00:02:20,210 --> 00:02:22,620
>> Din nefericire, procesul
este atât de transformare

52
00:02:22,620 --> 00:02:24,890
că este mult mai ușor de zis decât de făcut.

53
00:02:24,890 --> 00:02:29,400
M-am dus mai departe și sa transformat de fapt
acel program, binar de căutare,

54
00:02:29,400 --> 00:02:32,700
în zero-uri și altele prin intermediul unei
Programul numit compilatorul pe care am

55
00:02:32,700 --> 00:02:34,400
se întâmplă să aibă aici chiar pe Mac-ul meu.

56
00:02:34,400 --> 00:02:37,850
Și dacă te uiți la ecran
aici, concentrându-se în mod specific

57
00:02:37,850 --> 00:02:43,520
pe aceste șase coloane de mijloc numai,
veți vedea numai zerouri și cele.

58
00:02:43,520 --> 00:02:48,290
Iar acestea sunt zerouri și cele care
compun exact acel program de căutare.

59
00:02:48,290 --> 00:02:53,720
>> Și, astfel încât fiecare bucată de cinci biți,
fiecare octet de zero-uri și cele de aici,

60
00:02:53,720 --> 00:02:57,310
reprezintă câteva instrucțiuni
de obicei în interiorul unui computer.

61
00:02:57,310 --> 00:03:00,730
Și, de fapt, dacă ați auzit
sloganul de marketing "Intel în interiorul" - care,

62
00:03:00,730 --> 00:03:04,610
desigur, pur și simplu înseamnă că aveți un
CPU Intel sau creier în interiorul calculatorului.

63
00:03:04,610 --> 00:03:08,000
Și ceea ce înseamnă a fi un procesor este
că aveți un set de instrucțiuni,

64
00:03:08,000 --> 00:03:08,840
ca sa zicem asa.

65
00:03:08,840 --> 00:03:11,620
>> Fiecare procesor din lume, multe dintre
le-a făcut de Intel în aceste zile,

66
00:03:11,620 --> 00:03:13,690
înțelege un finit
numărul de instrucțiuni.

67
00:03:13,690 --> 00:03:18,690
Iar aceste instrucțiuni sunt la nivel atât de scăzut
așa cum se adaugă aceste două numere împreună,

68
00:03:18,690 --> 00:03:22,560
multiplica aceste două numere împreună,
mutați această bucată de date de aici

69
00:03:22,560 --> 00:03:27,340
aici în memorie, salvați această
informații de aici până aici, în memorie,

70
00:03:27,340 --> 00:03:32,200
și așa forth-- foarte, foarte
Low-level, detalii aproape electronice.

71
00:03:32,200 --> 00:03:34,780
Dar, cu cele matematice
operațiuni cuplate

72
00:03:34,780 --> 00:03:37,410
cu ceea ce am discutat mai devreme,
reprezentarea datelor

73
00:03:37,410 --> 00:03:40,450
ca zero-uri și altele, pot
vă construi totul

74
00:03:40,450 --> 00:03:44,180
că un calculator poate face astăzi, dacă
este textual, grafice, muzicale,

75
00:03:44,180 --> 00:03:45,580
sau altfel.

76
00:03:45,580 --> 00:03:49,450
>> Deci, acest lucru este foarte ușor pentru a obține
a pierdut în buruienile de repede.

77
00:03:49,450 --> 00:03:52,150
Și există o mulțime de
provocări sintactice

78
00:03:52,150 --> 00:03:56,630
prin care, dacă ai face cel mai simplu,
nici unul dintre erorile de scriere, mai stupida a programului

79
00:03:56,630 --> 00:03:57,860
va lucra nici un fel.

80
00:03:57,860 --> 00:04:00,366
Și astfel, în loc de a folosi un
cum ar fi limba C în această dimineață,

81
00:04:00,366 --> 00:04:02,240
M-am gândit că ar fi
mai distractiv de a face de fapt

82
00:04:02,240 --> 00:04:04,840
ceva mai vizual, care
în timp ce concepute pentru copii

83
00:04:04,840 --> 00:04:08,079
este de fapt o manifestare perfectă
de programare real

84
00:04:08,079 --> 00:04:10,370
language-- doar se întâmplă
utilizați imagini în loc de text

85
00:04:10,370 --> 00:04:11,710
să reprezinte aceste idei.

86
00:04:11,710 --> 00:04:15,470
>> Deci, odată ce aveți într-adevăr, o
cont pe scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
faceți clic pe butonul Creare
din partea stanga sus a site-ului.

88
00:04:21,070 --> 00:04:24,620
Și ar trebui să vedeți un mediu ca
cea Sunt pe cale să văd pe ecran

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

90
00:04:26,310 --> 00:04:29,350
Si vom cheltui doar un pic
ceva timp de joc aici.

91
00:04:29,350 --> 00:04:34,080
Să vedem dacă nu putem rezolva toate unele
problemele împreună în felul următor.

92
00:04:34,080 --> 00:04:39,420
>> Deci, ce veți vedea în acest
environment-- și de fapt, doar lasa

93
00:04:39,420 --> 00:04:40,050
mă întrerupe.

94
00:04:40,050 --> 00:04:42,680
Este cineva care nu aici?

95
00:04:42,680 --> 00:04:45,070
Nu aici?

96
00:04:45,070 --> 00:04:45,800
O.K.

97
00:04:45,800 --> 00:04:49,030
Așa că lasă-mă să subliniez câteva
caracteristicile acestui mediu.

98
00:04:49,030 --> 00:04:55,024
>> Așa că în partea din stânga sus a ecranului, noi
au scena Scratch lui, ca să spunem așa.

99
00:04:55,024 --> 00:04:57,440
Scratch este nu numai numele
a acestui limbaj de programare;

100
00:04:57,440 --> 00:05:00,356
este, de asemenea, numele de pisica care
vezi implicit acolo, în portocaliu.

101
00:05:00,356 --> 00:05:02,160
El se află pe o scenă, așa
mult ca am descris

102
00:05:02,160 --> 00:05:05,770
broasca mai devreme ca fiind într-un
mediu de bord alb dreptunghiular.

103
00:05:05,770 --> 00:05:09,800
aceasta lume pisicii este limitată în întregime
la acel dreptunghi în sus de sus acolo.

104
00:05:09,800 --> 00:05:12,210
>> În același timp, în partea dreaptă
partea de mână aici, este

105
00:05:12,210 --> 00:05:15,610
doar o zonă de script-uri, un
ardezie gol dacă va fi.

106
00:05:15,610 --> 00:05:18,590
Acest lucru este în cazul în care vom scrie
programele noastre in doar un moment.

107
00:05:18,590 --> 00:05:22,935
Și blocurile pe care le vom
utilizați pentru a scrie acest program-- puzzle

108
00:05:22,935 --> 00:05:25,310
bucăți, în cazul în care sunt will--
cei care chiar aici în mijloc,

109
00:05:25,310 --> 00:05:27,500
iar acestea sunt clasificate
prin funcționalitate.

110
00:05:27,500 --> 00:05:31,000
Așa că, de exemplu, am de gând să merg mai departe
și să demonstreze cel puțin una dintre acestea.

111
00:05:31,000 --> 00:05:33,690
Mă duc să merg mai departe și faceți clic
categoria de control în sus de sus.

112
00:05:33,690 --> 00:05:35,720
>> Deci, acestea sunt categoriile de top în sus.

113
00:05:35,720 --> 00:05:39,410
Am de gând să faceți clic pe categoria de control.

114
00:05:39,410 --> 00:05:44,020
Mai degrabă, am de gând să faceți clic pe Evenimente
categorie, prima una în sus de sus.

115
00:05:44,020 --> 00:05:47,790
Și, dacă doriți să urmați de-a lungul chiar
așa cum vom face acest lucru, tu ești destul de bun venit la.

116
00:05:47,790 --> 00:05:52,180
Am de gând să faceți clic și trageți această
Prima, "când steagul verde a făcut clic."

117
00:05:52,180 --> 00:05:58,410
Și apoi am de gând să-l doar picătură
aproximativ la partea de sus a Tăblițe mele goale.

118
00:05:58,410 --> 00:06:01,450
>> Și ce e frumos despre zero
este faptul că această piesă de puzzle, atunci când

119
00:06:01,450 --> 00:06:04,560
interblocată cu alte puzzle
piese, va face literalmente

120
00:06:04,560 --> 00:06:06,460
ce acele piese de puzzle spun să facă.

121
00:06:06,460 --> 00:06:09,710
Astfel, de exemplu, Scratch este corect
acum în mijlocul lumii sale.

122
00:06:09,710 --> 00:06:14,660
Mă duc să merg mai departe și alege
acum, să zicem, categoria Motion,

123
00:06:14,660 --> 00:06:18,000
dacă doriți pentru a face
same-- categoria Motion.

124
00:06:18,000 --> 00:06:20,430
Și acum am observat un întreg
grămadă de piese de puzzle aici

125
00:06:20,430 --> 00:06:23,370
că, din nou, un fel de a face ceea ce spun ei.

126
00:06:23,370 --> 00:06:28,110
Și mă duc să merg mai departe și glisați și
picătură bloc mutare chiar aici.

127
00:06:28,110 --> 00:06:31,860
>> Și observați că de îndată ce veți obține
aproape de partea de jos a "steagul verde

128
00:06:31,860 --> 00:06:34,580
click pe "buton, Notă
modul în care apare o linie albă,

129
00:06:34,580 --> 00:06:36,950
ca și cum este aproape
magnetice, vrea să meargă acolo.

130
00:06:36,950 --> 00:06:43,070
Lasa doar du-te, și va fixa
precum și formele se vor potrivi.

131
00:06:43,070 --> 00:06:46,620
Și acum puteți, probabil, aproape
ghici unde vom merge cu asta.

132
00:06:46,620 --> 00:06:51,570
>> Dacă te uiți la etapa Scratch
aici si uita-te la partea de sus a acesteia,

133
00:06:51,570 --> 00:06:55,142
veți vedea o lumină roșie, un
opri semn, și un steag verde.

134
00:06:55,142 --> 00:06:57,100
Si voi merge mai departe
și urmăriți-mi screen--

135
00:06:57,100 --> 00:06:58,460
pentru un moment, dacă ai putea.

136
00:06:58,460 --> 00:07:01,960
Am de gând să faceți clic pe
verde pavilion chiar acum,

137
00:07:01,960 --> 00:07:07,850
și sa mutat ceea ce pare a fi de 10 pași
sau 10 pixeli, 10 puncte, pe ecran.

138
00:07:07,850 --> 00:07:13,390
>> Și așa nu asta interesant,
dar permiteți-mi propun

139
00:07:13,390 --> 00:07:17,440
chiar fără a învăța acest lucru, pur și simplu
folosind propria dvs. Înștiințați intuition--

140
00:07:17,440 --> 00:07:22,560
mă propun ca să îți dai seama cum să
face plimbare de zero chiar de pe scenă.

141
00:07:22,560 --> 00:07:28,700
L-au pentru a face loc pe partea dreaptă a
ecran, tot drumul spre dreapta.

142
00:07:28,700 --> 00:07:32,200
Lasă-mă să-ți dau un moment
sau astfel încât să se lupte cu asta.

143
00:07:32,200 --> 00:07:37,681
S-ar putea dori să ia o privire
la alte categorii de blocuri.

144
00:07:37,681 --> 00:07:38,180
In regula.

145
00:07:38,180 --> 00:07:41,290
Deci, doar să recapitulez, atunci când avem
steagul verde dat click aici

146
00:07:41,290 --> 00:07:44,850
și pentru a muta 10 etape este cea
numai instruire, de fiecare dată când am

147
00:07:44,850 --> 00:07:46,720
faceți clic pe steagul verde, ce se întâmplă?

148
00:07:46,720 --> 00:07:50,070
Ei bine, asta rulează programul meu.

149
00:07:50,070 --> 00:07:52,450
Așa că am putut face acest lucru
poate 10 de ori manual,

150
00:07:52,450 --> 00:07:55,130
dar acest lucru se simte un pic
bit hackish, ca să spunem așa,

151
00:07:55,130 --> 00:07:57,480
prin care nu sunt cu adevărat
rezolvarea problemei.

152
00:07:57,480 --> 00:08:00,530
Eu doar încerc din nou și
din nou și din nou și din nou

153
00:08:00,530 --> 00:08:03,180
până când am un fel de accidental
atinge directiva

154
00:08:03,180 --> 00:08:05,560
că am stabilit pentru a realiza mai devreme.

155
00:08:05,560 --> 00:08:08,200
>> Dar noi știm de la nostru
pseudocod mai devreme că există

156
00:08:08,200 --> 00:08:11,870
această noțiune în programarea looping,
face ceva din nou și din nou.

157
00:08:11,870 --> 00:08:14,888
Și așa am văzut că o grămadă de tine
a ajuns pentru piesa ce puzzle?

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

159
00:08:17,870 --> 00:08:18,730
Se repetă până când.

160
00:08:18,730 --> 00:08:21,400
Așa că am putea face ceva
cum ar fi, până când se repetă.

161
00:08:21,400 --> 00:08:23,760
Și ce-ai repeta pana exact?

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

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

164
00:08:28,540 --> 00:08:31,974
Și lasă-mă să merg cu una singură
oarecum mai simplu pentru un moment.

165
00:08:31,974 --> 00:08:33,140
Lasă-mă să merg mai departe și fac acest lucru.

166
00:08:33,140 --> 00:08:35,559
Observați că, după cum s-ar putea avea
descoperit sub control,

167
00:08:35,559 --> 00:08:38,409
există acest bloc de repetare, care
nu arata ca este atât de mare.

168
00:08:38,409 --> 00:08:41,039
Nu există mult loc în
între cele două linii galbene.

169
00:08:41,039 --> 00:08:43,539
Dar, așa cum unii dintre voi s-ar putea avea
a observat, dacă trageți și plasați,

170
00:08:43,539 --> 00:08:45,150
observați cum crește pentru a umple forma.

171
00:08:45,150 --> 00:08:46,274
>> Și tu poți ghiftui chiar mai mult.

172
00:08:46,274 --> 00:08:48,670
Se va păstra doar în creștere în cazul în care
trageți și plasați cursorul peste ea.

173
00:08:48,670 --> 00:08:51,110
Si eu nu știu ce-i
cel mai bine aici, asa ca lasa

174
00:08:51,110 --> 00:08:54,760
mine cel puțin repeta de cinci ori, pentru
de exemplu, și apoi du-te înapoi la etapa

175
00:08:54,760 --> 00:08:56,720
și faceți clic pe steagul verde.

176
00:08:56,720 --> 00:08:59,110
Și acum observați că nu e chiar acolo.

177
00:08:59,110 --> 00:09:02,400
>> Acum, unii dintre voi a propus, ca
Victoria tocmai a, se repetă de 10 ori.

178
00:09:02,400 --> 00:09:05,140
Iar aceasta, în general,
să-l tot drumul,

179
00:09:05,140 --> 00:09:10,510
dar nu ar exista o mai robust
mod arbitrar decât imaginind

180
00:09:10,510 --> 00:09:12,640
cât de multe mișcări pentru a face?

181
00:09:12,640 --> 00:09:17,680
Ce ar putea fi un bloc mai bun
decât se repetă de 10 ori mai fie?

182
00:09:17,680 --> 00:09:20,380
>> Da, așa că de ce să nu fac ceva pentru totdeauna?

183
00:09:20,380 --> 00:09:24,390
Și acum să mă mute această piesă de puzzle
acolo înăuntru și a scăpa de asta.

184
00:09:24,390 --> 00:09:28,300
Acum observați în cazul în care nu contează zero
începe, el merge la margine.

185
00:09:28,300 --> 00:09:30,700
Din fericire și MIT,
care face zgârieturi, doar

186
00:09:30,700 --> 00:09:33,190
face sigur că el nu
dispare complet.

187
00:09:33,190 --> 00:09:35,360
Puteți apuca întotdeauna coada lui.

188
00:09:35,360 --> 00:09:37,680
>> Si doar intuitiv,
de ce face el menține în mișcare?

189
00:09:37,680 --> 00:09:38,892
Ce se intampla aici?

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

191
00:09:41,440 --> 00:09:43,824
El pare să se fi oprit, dar
apoi, dacă mă ridic și să trageți

192
00:09:43,824 --> 00:09:45,240
el continuă să vrea să meargă acolo.

193
00:09:45,240 --> 00:09:46,123
De ce este asta?

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

195
00:09:51,610 --> 00:09:54,360
Într-adevăr, un calculator este literalmente
O să facă ceea ce îi spun să facă.

196
00:09:54,360 --> 00:09:58,380
Așa că, dacă ai spus mai devreme este diferența dintre
următorul lucru pentru totdeauna, mutați 10 pași,

197
00:09:58,380 --> 00:10:01,860
se va menține merge și merge
până când am lovit semnul roșu de stop

198
00:10:01,860 --> 00:10:04,620
și a opri programul cu totul.

199
00:10:04,620 --> 00:10:06,610
>> Deci, chiar dacă nu-i
face acest lucru, cum aș putea

200
00:10:06,610 --> 00:10:09,510
face mișcare Scratch mai repede
pe ecran?

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

202
00:10:12,060 --> 00:10:13,280
Mai mulți pași, nu?

203
00:10:13,280 --> 00:10:15,710
Deci, în loc de a face 10
la un moment dat, de ce nu ne

204
00:10:15,710 --> 00:10:20,100
mergeți mai departe și schimbați-l sa--
ce-ai propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Așa că acum am de gând să faceți clic pe verde
pavilion, și într-adevăr, el merge foarte repede.

206
00:10:24,410 --> 00:10:27,180
>> Și acest lucru, desigur, este doar
o manifestare de animație.

207
00:10:27,180 --> 00:10:28,060
Ce este animația?

208
00:10:28,060 --> 00:10:33,090
Doar că vă arată un om
grămadă de imagini statice într-adevăr,

209
00:10:33,090 --> 00:10:34,160
într-adevăr, foarte repede.

210
00:10:34,160 --> 00:10:36,500
Și așa, dacă ne povesteam
l să se miște mai mulți pași,

211
00:10:36,500 --> 00:10:39,750
noi suntem doar având ca efect să fie la
schimbare în cazul în care el este pe ecran

212
00:10:39,750 --> 00:10:42,900
tot mai rapid pe unitatea de timp.

213
00:10:42,900 --> 00:10:46,454
>> Acum, următoarea provocare pe care am propus
a fost să-l sări de pe margine.

214
00:10:46,454 --> 00:10:49,120
Și, fără să știe ce puzzle
piese de exist-- pentru că e în regulă

215
00:10:49,120 --> 00:10:53,030
dacă nu ajungi la
etapă a challenge-- ce

216
00:10:53,030 --> 00:10:54,280
vrei să faci intuitiv?

217
00:10:54,280 --> 00:10:58,030
Cum trebuie să-l sări înapoi și
mai departe, între stânga și dreapta?

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

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

220
00:11:03,810 --> 00:11:05,680
Așa că avem nevoie de un fel
de stare, și noi

221
00:11:05,680 --> 00:11:09,710
par să aibă condiționale, astfel încât să
vorbesc, în categoria de control.

222
00:11:09,710 --> 00:11:14,110
Care dintre aceste blocuri
face, probabil, ne dorim?

223
00:11:14,110 --> 00:11:15,200
Da, poate ", dacă, atunci."

224
00:11:15,200 --> 00:11:18,780
Așa că observați că printre blocurile galbene
avem aici, nu există acest "dacă"

225
00:11:18,780 --> 00:11:23,920
sau acest lucru ", în cazul în care, altfel", bloc care va
ne permit să ia o decizie de a face acest lucru

226
00:11:23,920 --> 00:11:25,000
sau de a face acest lucru.

227
00:11:25,000 --> 00:11:27,380
Și tu poți chiar să le cuib
pentru a face mai multe lucruri.

228
00:11:27,380 --> 00:11:34,910
Sau, dacă nu ai plecat încă aici,
merge mai departe la categoria Sensing

229
00:11:34,910 --> 00:11:39,612
si-- să vedem dacă e aici.

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

231
00:11:43,050 --> 00:11:52,050
>> Deci, ce blocul ar putea fi de ajutor aici
pentru a detecta dacă el e pe scenă?

232
00:11:52,050 --> 00:11:56,740
Da, observați că unele dintre aceste blocuri
poate fi parametrizat, ca să spunem așa.

233
00:11:56,740 --> 00:12:00,706
Ele pot fi un fel de personalizat, nu
spre deosebire de HTML ieri cu atribute,

234
00:12:00,706 --> 00:12:03,330
în cazul în care aceste atribute un fel de
personaliza comportamentul unei etichete.

235
00:12:03,330 --> 00:12:08,880
În mod similar aici, pot apuca această ating
bloc și schimbare și de a pune întrebarea,

236
00:12:08,880 --> 00:12:11,500
te atinge mouse-ul
pointer la fel ca cursorul

237
00:12:11,500 --> 00:12:13,250
sau te ating marginea?

238
00:12:13,250 --> 00:12:15,210
>> Așa că lasă-mă să intru și să facă acest lucru.

239
00:12:15,210 --> 00:12:18,130
Voi micșora pentru un moment.

240
00:12:18,130 --> 00:12:21,320
Lasă-mă apuca de această piesă de puzzle
aici, acest puzzle bucata asta,

241
00:12:21,320 --> 00:12:24,570
și mă duc la talmeș-balmeș
le doar pentru un moment.

242
00:12:24,570 --> 00:12:27,620
Am de gând să se mute acest lucru,
schimba acest lucru la margine atinge,

243
00:12:27,620 --> 00:12:38,590
și voi face asta de mișcare.

244
00:12:38,590 --> 00:12:40,490
Deci, aici sunt unele ingrediente.

245
00:12:40,490 --> 00:12:42,570
Cred că am tot ce vreau.

246
00:12:42,570 --> 00:12:47,710
>> Cineva ar dori să propună modul în care am
se poate conecta aceste poate de sus in jos

247
00:12:47,710 --> 00:12:52,020
în scopul de a rezolva problema de a avea
Zgârietură muta dreapta la stânga la dreapta la

248
00:12:52,020 --> 00:12:57,020
la stânga la dreapta la stânga, fiecare
timp doar cade de pe perete?

249
00:12:57,020 --> 00:12:58,050
Ce vreau să fac?

250
00:12:58,050 --> 00:13:01,097
Care blocul ar trebui să se conecteze la
"Pavilion verde atunci când a făcut clic mai întâi"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, așa că hai să începem cu "pentru totdeauna."

253
00:13:06,200 --> 00:13:07,170
Ce merge în interiorul următor?

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

255
00:13:10,290 --> 00:13:11,850
OK, mutați pași.

256
00:13:11,850 --> 00:13:12,350
In regula.

257
00:13:12,350 --> 00:13:14,470
Atunci ce?

258
00:13:14,470 --> 00:13:15,120
Așa că, atunci dacă este.

259
00:13:15,120 --> 00:13:17,720
Și observați, chiar dacă pare
sandwich strâns împreună,

260
00:13:17,720 --> 00:13:19,500
aceasta va crește doar pentru a umple.

261
00:13:19,500 --> 00:13:21,500
Acesta va sari doar în cazul în care l-am dorit.

262
00:13:21,500 --> 00:13:25,920
>> Și ce am pus între
IF și atunci?

263
00:13:25,920 --> 00:13:27,180
Probabil "dacă atinge margine."

264
00:13:27,180 --> 00:13:31,800
Și observați, din nou, este prea mare
pentru ea, dar va creste pentru a umple.

265
00:13:31,800 --> 00:13:35,002
Și apoi rândul său, de 15 de grade?

266
00:13:35,002 --> 00:13:35,710
Câte grade?

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

268
00:13:38,800 --> 00:13:41,196
Da, deci 180 se va roti
mă tot drumul în jurul valorii.

269
00:13:41,196 --> 00:13:42,570
Așa că hai să vedem dacă am acest drept.

270
00:13:42,570 --> 00:13:43,930
Lasă-mă micșora.

271
00:13:43,930 --> 00:13:45,130
>> Lasă-mă să trageți Scratch în sus.

272
00:13:45,130 --> 00:13:50,030
Deci, el e un pic distorsionat
acum, dar asta e bine.

273
00:13:50,030 --> 00:13:52,231
Cum pot să-l reseta cu ușurință?

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

275
00:13:59,879 --> 00:14:01,045
Am de gând să trișeze ușor.

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

277
00:14:04,074 --> 00:14:05,990
Deci, eu sunt adăugarea de un alt
bloc, trebuie doar să fie clar.

278
00:14:05,990 --> 00:14:08,424
Vreau ca el să punctul 90 de grade
la dreapta în mod implicit,

279
00:14:08,424 --> 00:14:10,840
așa că doar o să-i spun
pentru a face acest lucru în mod programatic.

280
00:14:10,840 --> 00:14:11,632
Si aici vom merge.

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

282
00:14:14,740 --> 00:14:15,740
Se pare că au făcut-o.

283
00:14:15,740 --> 00:14:19,980
E un pic ciudat, pentru că
Merge cu susul în jos.

284
00:14:19,980 --> 00:14:21,250
Hai să-i spunem că o eroare.

285
00:14:21,250 --> 00:14:22,120
Asta-i o greșeală.

286
00:14:22,120 --> 00:14:27,320
Un bug este o greșeală într-un program,
eroare logică pe care eu, omul, a făcut.

287
00:14:27,320 --> 00:14:28,985
De ce se întâmplă cu susul în jos?

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

289
00:14:33,560 --> 00:14:35,250
Au șurub MIT sau nu-i așa?

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

291
00:14:38,840 --> 00:14:42,550
>> Da, vreau să spun, nu e MIT
vina. Mi-au dat o bucată de puzzle

292
00:14:42,550 --> 00:14:44,970
care spune rândul său, unele număr de grade.

293
00:14:44,970 --> 00:14:47,672
Iar la sugestia Victoria,
Sunt de cotitură la 180 de grade,

294
00:14:47,672 --> 00:14:48,880
care este intuiția corectă.

295
00:14:48,880 --> 00:14:53,700
Dar, de cotitură 180 de grade literalmente
înseamnă cotitură 180 de grade,

296
00:14:53,700 --> 00:14:55,860
și că nu este cu adevărat
ceea ce vreau, aparent.

297
00:14:55,860 --> 00:14:58,026
Pentru că cel puțin el e în
această lume cu două dimensiuni,

298
00:14:58,026 --> 00:15:00,740
astfel încât de cotitură este într-adevăr merge
să-l răsturna cu susul în jos.

299
00:15:00,740 --> 00:15:04,030
>> Probabil că vreau să folosesc ceea ce bloc
în schimb, bazat pe ceea ce vezi aici?

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

301
00:15:11,890 --> 00:15:14,790
Cum ne-am putea rezolva această problemă?

302
00:15:14,790 --> 00:15:18,380
Da, așa că am putea arăta
în direcția opusă.

303
00:15:18,380 --> 00:15:22,300
Și, de fapt, chiar asta
nu va fi de ajuns,

304
00:15:22,300 --> 00:15:26,410
pentru că putem doar cod greu
la arătând spre stânga sau spre dreapta.

305
00:15:26,410 --> 00:15:27,920
>> Știi ce am putea face?

306
00:15:27,920 --> 00:15:30,160
Se pare că avem un
bloc de confort aici.

307
00:15:30,160 --> 00:15:32,987
În cazul în care pot mări, a se vedea
ceva ce ne place aici?

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

309
00:15:36,120 --> 00:15:40,020
Deci, se pare ca MIT are un
abstracție construită aici.

310
00:15:40,020 --> 00:15:45,440
Acest bloc pare a fi echivalent
la care alte blocuri, plural?

311
00:15:45,440 --> 00:15:49,510
>> Acesta bloc pare să fie echivalentă
pentru tot acest trio de blocuri

312
00:15:49,510 --> 00:15:50,880
pe care o avem aici.

313
00:15:50,880 --> 00:15:54,670
Deci, se pare că pot simplifica meu
Programul prin eliminarea de toate astea

314
00:15:54,670 --> 00:15:58,270
și tocmai a pus asta aici.

315
00:15:58,270 --> 00:16:01,620
Și acum el este încă un pic
buggy, și asta e bine acum.

316
00:16:01,620 --> 00:16:03,370
Vom lăsa asta să fie.

317
00:16:03,370 --> 00:16:06,000
Dar programul meu este chiar
mai simplu, și acest lucru, de asemenea,

318
00:16:06,000 --> 00:16:09,060
ar fi reprezentativ
de un gol în programming--

319
00:16:09,060 --> 00:16:13,430
este de a face în mod ideal codul ca
simplu, cât mai compactă,

320
00:16:13,430 --> 00:16:15,650
în timp ce încă ca
citibil posibil.

321
00:16:15,650 --> 00:16:20,310
Tu nu vrei să-l atât de succintă
că este greu de înțeles.

322
00:16:20,310 --> 00:16:22,826
>> Dar observați am înlocuit
trei blocuri cu unul,

323
00:16:22,826 --> 00:16:24,200
și asta e, fără îndoială, un lucru bun.

324
00:16:24,200 --> 00:16:27,280
Am captată departe noțiunea
de a verifica dacă sunteți

325
00:16:27,280 --> 00:16:29,120
pe margine, cu doar un singur bloc.

326
00:16:29,120 --> 00:16:31,520
Acum ne putem distra cu acest lucru, de fapt.

327
00:16:31,520 --> 00:16:35,790
Acest lucru nu adaugă atât de mult
valoare intelectuală, dar valoarea jucaus.

328
00:16:35,790 --> 00:16:39,730
Mă duc să merg mai departe
și apuca acest sunet aici.

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

330
00:16:42,900 --> 00:16:46,420
Așa că lasă-mă să merg mai departe, și lasă-mă
opri programul pentru un moment.

331
00:16:46,420 --> 00:16:52,070
Mă duc să înregistreze următoarele,
permițând accesul la microfonul meu.

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

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

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

335
00:16:58,710 --> 00:17:01,140
Hai să încercăm din nou.

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

337
00:17:02,279 --> 00:17:03,570
OK, am înregistrat un lucru greșit.

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

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

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

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

342
00:17:08,800 --> 00:17:09,300
In regula.

343
00:17:09,300 --> 00:17:10,791
Acum trebuie să scap de asta.

344
00:17:10,791 --> 00:17:11,290
In regula.

345
00:17:11,290 --> 00:17:13,950
>> Așa că acum am un
înregistrarea doar "Ouch."

346
00:17:13,950 --> 00:17:18,040
Așa că acum am de gând să merg
înainte și numesc acest lucru "Ouch."

347
00:17:18,040 --> 00:17:20,270
Mă duc să mă întorc
la scripturile mele, iar acum

348
00:17:20,270 --> 00:17:25,460
Notă există acest bloc care se numește
reda un sunet "miau", sau să joace un sunet "Ouch."

349
00:17:25,460 --> 00:17:28,920
Voi trage acest lucru, și în cazul în care
ar trebui să pun acest lucru pentru un efect comic?

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

351
00:17:31,740 --> 00:17:37,860
Da, așa că acum e un fel de
trăsură pentru două persoane, pentru că acum această block--

352
00:17:37,860 --> 00:17:42,050
observați cum acest lucru ", în cazul în care pe muchie,
sări "este un fel de sine stătătoare.

353
00:17:42,050 --> 00:17:43,704
Așa că am nevoie pentru a rezolva această problemă.

354
00:17:43,704 --> 00:17:44,870
Lasă-mă să merg mai departe și fac acest lucru.

355
00:17:44,870 --> 00:17:48,630
Lasă-mă să scap de asta și du-te înapoi
cu originalul nostru, în mod deliberat mai mult

356
00:17:48,630 --> 00:17:49,870
funcționalitate.

357
00:17:49,870 --> 00:18:01,080
Deci, "dacă atinge margine, atunci" Vreau
la rândul său, așa cum a propus Victoria,

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

359
00:18:02,480 --> 00:18:05,497
Si vreau sa joace
sunetul "Ouch" acolo?

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

361
00:18:11,800 --> 00:18:15,580
>> Da, observați că e afară
că blocul galben.

362
00:18:15,580 --> 00:18:17,680
Deci, acest lucru, de asemenea, ar fi
bug-ul, dar l-am observat.

363
00:18:17,680 --> 00:18:21,290
Așa că am de gând să-l trage în sus aici,
și acum este o notificare in interiorul "daca".

364
00:18:21,290 --> 00:18:24,250
Prin urmare, "dacă" este acest tip
cum ar fi de pată-braț ca

365
00:18:24,250 --> 00:18:26,260
că doar va
face ceea ce este în interiorul acestuia.

366
00:18:26,260 --> 00:18:30,216
Așa că acum, dacă am zoom out la
riscul de annoying--

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

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

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: Și
va merge doar la nesfârșit.

370
00:18:39,910 --> 00:18:44,160
Acum, pur și simplu pentru a accelera lucrurile
aici, lasă-mă să merg mai departe și să se deschidă,

371
00:18:44,160 --> 00:18:50,460
Să say-- lasă-mă să merg la unele
din lucrurile mele proprii de la clasă.

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

373
00:18:53,000 --> 00:19:00,220
Și lasă-mă să deschid în sus, să spunem, acest lucru
una făcută de unul dintre semenii noștri de predare

374
00:19:00,220 --> 00:19:01,500
acum cativa ani.

375
00:19:01,500 --> 00:19:04,732
Așa că unii dintre voi s-ar putea aminti
acest joc de odinioară,

376
00:19:04,732 --> 00:19:05,940
și este de fapt remarcabil.

377
00:19:05,940 --> 00:19:08,190
Chiar dacă ne-am făcut
mai simplu de programe chiar acum,

378
00:19:08,190 --> 00:19:09,980
să ia în considerare ce acest lucru
de fapt, arată.

379
00:19:09,980 --> 00:19:10,650
Lasă-mă să lovit joc.

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

381
00:19:14,210 --> 00:19:18,980
>> Deci, în acest joc, avem
broască, și utilizând săgeata keys--

382
00:19:18,980 --> 00:19:23,340
el ia măsuri mai mari decât mi-am amintește-ți
Am controlul asupra acestei broaște.

383
00:19:23,340 --> 00:19:29,630
Iar scopul este de a obține peste ocupat
rutier fără să fie difuzate în vagoane.

384
00:19:29,630 --> 00:19:34,735
Și să see-- dacă mă duc aici, am
trebuie să aștepte un jurnal pentru a derula.

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

386
00:19:38,130 --> 00:19:39,274
Acest lucru se simte ca un bug.

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

388
00:19:42,240 --> 00:19:43,495
Acesta este un fel de bug.

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

390
00:19:45,980 --> 00:19:46,480
In regula.

391
00:19:46,480 --> 00:19:51,550
Sunt pe asta aici,
acolo, și apoi păstrați

392
00:19:51,550 --> 00:19:54,100
merge până când obțineți toate
broaste pentru tampoane crin.

393
00:19:54,100 --> 00:19:55,920
Acum, acest lucru ar putea arata
tot mai complexe,

394
00:19:55,920 --> 00:19:57,840
dar să încercăm să rupă
acest lucru în jos mental

395
00:19:57,840 --> 00:20:00,040
verbal și în blocurile sale componente.

396
00:20:00,040 --> 00:20:03,910
Deci, există, probabil, un puzzle
piesa pe care nu le-am văzut încă

397
00:20:03,910 --> 00:20:07,440
dar care răspunde la intrarile de la tastatura,
la lucruri am lovit pe tastatură.

398
00:20:07,440 --> 00:20:11,660
>> Deci, nu există, probabil, un fel de
bloc care spune, în cazul în care cheia este egal în sus,

399
00:20:11,660 --> 00:20:15,965
apoi face ceva cu rămășițe
poate muta 10 pași în acest fel.

400
00:20:15,965 --> 00:20:20,240
Dacă se apasă tasta în jos, mutați 10 pași
în acest fel, sau tasta stânga, mutați 10 pași

401
00:20:20,240 --> 00:20:21,710
Astfel, 10 pași care.

402
00:20:21,710 --> 00:20:23,644
M-am transformat în mod clar pisica într-o broască.

403
00:20:23,644 --> 00:20:26,060
Deci asta e unde se trage
costum, ca în cazul apelurilor răzuibile it-- noi

404
00:20:26,060 --> 00:20:28,440
doar importate o imagine de broasca.

405
00:20:28,440 --> 00:20:29,570
>> Dar ce altceva se întâmplă?

406
00:20:29,570 --> 00:20:32,794
Ce alte linii de cod,
ce alte piese de puzzle

407
00:20:32,794 --> 00:20:35,460
a făcut Blake, colegul nostru de predare,
utilizați în acest program, aparent?

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

409
00:20:38,320 --> 00:20:42,730
Ce se face totul move--
Ce programare construct?

410
00:20:42,730 --> 00:20:44,950
>> Propunerea, sure-- așa
muta bloc, sigur.

411
00:20:44,950 --> 00:20:49,330
Si ce e acel bloc de mișcare
interiorul, cel mai probabil?

412
00:20:49,330 --> 00:20:52,850
Da, un fel de buclă, poate
pentru totdeauna bloca, poate o repetare block--

413
00:20:52,850 --> 00:20:54,070
se repetă până la bloc.

414
00:20:54,070 --> 00:20:57,330
Și asta e ceea ce face jurnalele și
tampoane crin și totul altceva muta

415
00:20:57,330 --> 00:20:57,990
Înainte şi înapoi.

416
00:20:57,990 --> 00:21:00,270
Se întâmplă doar la nesfârșit.

417
00:21:00,270 --> 00:21:03,180
>> De ce sunt unele dintre masini
se deplasează mai repede decât ceilalți?

418
00:21:03,180 --> 00:21:06,607
Ceea ce este diferit despre aceste programe?

419
00:21:06,607 --> 00:21:09,690
Da, probabil, unele dintre ele sunt luati
mai multe etape dintr-o dată, iar unele dintre ele

420
00:21:09,690 --> 00:21:10,690
mai puține etape dintr-o dată.

421
00:21:10,690 --> 00:21:14,670
Iar efectul vizual
este rapid versus lent.

422
00:21:14,670 --> 00:21:16,030
>> Ce crezi că sa întâmplat?

423
00:21:16,030 --> 00:21:19,700
Când m-am luat broasca mea tot drumul
peste drum și râul

424
00:21:19,700 --> 00:21:23,560
pe planșa de crin, ceva
demn de menționat sa întâmplat.

425
00:21:23,560 --> 00:21:26,540
Ce sa întâmplat imediat ce am făcut asta?

426
00:21:26,540 --> 00:21:27,210
S-a oprit.

427
00:21:27,210 --> 00:21:29,680
Că broasca sa oprit, și
Am primit oa doua broască.

428
00:21:29,680 --> 00:21:33,155
Deci, ce trebuie să fie construct
folosit acolo, ce facilitate?

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

430
00:21:36,020 --> 00:21:38,660
>> Da, deci există un fel de
"În cazul în care" condiționează acolo, de asemenea.

431
00:21:38,660 --> 00:21:41,909
Și se pare out-- nu am văzut astea--
dar există și alte blocuri acolo, care

432
00:21:41,909 --> 00:21:45,300
se poate spune, în cazul în care se ating
un alt lucru pe ecran,

433
00:21:45,300 --> 00:21:47,720
dacă vă atingeți pad crin ", apoi".

434
00:21:47,720 --> 00:21:50,810
Și apoi asta e atunci când ne
face să apară de-a doua broasca.

435
00:21:50,810 --> 00:21:54,969
Deci, chiar dacă acest joc este cu siguranță
foarte datat, chiar dacă la prima vedere

436
00:21:54,969 --> 00:21:58,010
există atât de mult merge pe Blake on-- și
nu a bici acest lucru în două minute,

437
00:21:58,010 --> 00:22:00,390
probabil a luat-l de mai multe
ore pentru a crea acest joc

438
00:22:00,390 --> 00:22:03,850
bazat pe memorie sau videoclipurile sale
din versiunea lui de odinioară ea.

439
00:22:03,850 --> 00:22:07,940
Dar toate aceste lucruri mici
merge pe ecran în mod izolat

440
00:22:07,940 --> 00:22:11,550
se fierbe în jos la aceste foarte simplu
mișcări constructs-- sau declarații

441
00:22:11,550 --> 00:22:15,519
așa cum am discutat, bucle și
condiții, și asta e despre asta.

442
00:22:15,519 --> 00:22:17,060
Există alte câteva caracteristici columbofil.

443
00:22:17,060 --> 00:22:19,130
Unele dintre ele sunt pur
estetice sau acustice,

444
00:22:19,130 --> 00:22:20,964
cum ar fi sunetele tocmai am jucat cu.

445
00:22:20,964 --> 00:22:23,380
Dar pentru cea mai mare parte, tu
au în această limbă, Scratch,

446
00:22:23,380 --> 00:22:25,350
toate fundamentale
blocuri de construcție pe care le

447
00:22:25,350 --> 00:22:29,280
au în C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
precum și orice număr de alte limbi.

449
00:22:32,960 --> 00:22:36,720
Întrebări cu privire la zero?

450
00:22:36,720 --> 00:22:37,220
In regula.

451
00:22:37,220 --> 00:22:40,303
Așa că nu ne vom scufunda mai adânc la zero,
deși sunteți binevenit acest week-end,

452
00:22:40,303 --> 00:22:42,860
mai ales dacă aveți copii sau
nepoții și nepoatele și astfel,

453
00:22:42,860 --> 00:22:44,220
pentru a le introduce la zero.

454
00:22:44,220 --> 00:22:47,960
Este de fapt un minunat jucaus
mediu cu, după cum spun autorii săi,

455
00:22:47,960 --> 00:22:49,120
tavane foarte înalte.

456
00:22:49,120 --> 00:22:51,670
Chiar dacă am început cu
foarte multe detalii de nivel scăzut,

457
00:22:51,670 --> 00:22:54,890
puteți face într-adevăr destul de un pic
cu ea, iar acest lucru este probabil

458
00:22:54,890 --> 00:22:57,360
o demonstrație de exact asta.

459
00:22:57,360 --> 00:23:02,920
>> Dar, hai acum trecerea la unele mai multe
probleme sofisticate, dacă va fi,

460
00:23:02,920 --> 00:23:05,870
cunoscut sub numele de "căutarea" și
"Sortare", mai general.

461
00:23:05,870 --> 00:23:09,500
Am avut această carte de telefon e aici earlier--
un altul doar pentru discussion--

462
00:23:09,500 --> 00:23:13,460
că am fost capabili să caute
mai eficient deoarece

463
00:23:13,460 --> 00:23:15,270
a unei ipoteze semnificative.

464
00:23:15,270 --> 00:23:17,655
Și ca să fie clar, ceea ce
ipoteză am fost de luare

465
00:23:17,655 --> 00:23:19,280
atunci când se caută prin această carte de telefon?

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

467
00:23:23,342 --> 00:23:25,300
Mike Smith a fost în
cartea de telefon, deși am

468
00:23:25,300 --> 00:23:27,410
s-ar putea să se ocupe
scenariul fără el

469
00:23:27,410 --> 00:23:30,720
acolo dacă pur și simplu m-am oprit prematur.

470
00:23:30,720 --> 00:23:31,806
Cartea e în ordine alfabetică.

471
00:23:31,806 --> 00:23:33,930
Si asta e un foarte generos
ipoteză, pentru că

472
00:23:33,930 --> 00:23:36,580
înseamnă someone-- Sunt un fel
de tăiere a unui colt,

473
00:23:36,580 --> 00:23:40,580
ca eu sunt mai repede pentru că cineva
altcineva a făcut o mulțime de muncă grea pentru mine.

474
00:23:40,580 --> 00:23:43,120
>> Dar, ce se întâmplă dacă telefonul
carte au fost nesortate?

475
00:23:43,120 --> 00:23:47,050
Poate că Verizon a primit leneș, tocmai a aruncat
numele și numerele fiecăruia acolo

476
00:23:47,050 --> 00:23:50,120
poate, în ordinea în care acestea
semnat pentru serviciul telefonic.

477
00:23:50,120 --> 00:23:54,570
Și cât de mult timp nu-l ia-mi
pentru a găsi pe cineva ca Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1.000 pagina de telefon book-- câte
Paginile trebuie să mă uit prin ea?

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

480
00:23:58,905 --> 00:24:00,030
Tu ești un fel de noroc.

481
00:24:00,030 --> 00:24:03,420
Ai literalmente să se uite la fiecare
pagina în cazul în care cartea de telefon este doar

482
00:24:03,420 --> 00:24:04,450
sortate aleatoriu.

483
00:24:04,450 --> 00:24:06,910
S-ar putea avea noroc și să găsească Mike
pe prima pagină, pentru că el

484
00:24:06,910 --> 00:24:08,826
a fost primul client
pentru a comanda un serviciu telefonic.

485
00:24:08,826 --> 00:24:10,760
Dar el ar fi fost ultimul, de asemenea.

486
00:24:10,760 --> 00:24:12,500
>> Astfel încât ordine aleatorie nu este bun.

487
00:24:12,500 --> 00:24:16,750
Așa că să presupunem că trebuie să Sortafli
agenda telefonica sau date generale de sortare

488
00:24:16,750 --> 00:24:18,520
pe care le-am dat.

489
00:24:18,520 --> 00:24:19,440
Cum putem face asta?

490
00:24:19,440 --> 00:24:21,360
>> Ei bine, lasă-mă să încerc
un exemplu simplu aici.

491
00:24:21,360 --> 00:24:24,290
Lasă-mă să merg mai departe și să arunci o
câteva numere de pe bord.

492
00:24:24,290 --> 00:24:35,480
Să presupunem că numerele pe care le avem sunt,
să zicem, patru, doi, unu și trei.

493
00:24:35,480 --> 00:24:38,390
Si, Ben, a sorta aceste numere pentru noi.

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

495
00:24:39,017 --> 00:24:39,850
Cum ai făcut asta?

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

497
00:24:42,731 --> 00:24:43,230
In regula.

498
00:24:43,230 --> 00:24:44,710
Deci, începe cu cea mai mică
valoare și cea mai mare,

499
00:24:44,710 --> 00:24:46,084
și asta e foarte bună intuiție.

500
00:24:46,084 --> 00:24:48,080
Și ne dăm seama că
oamenii sunt de fapt destul

501
00:24:48,080 --> 00:24:49,913
bun la rezolvarea problemelor
ca aceasta, cel puțin

502
00:24:49,913 --> 00:24:51,810
în cazul în care datele sunt relativ mici.

503
00:24:51,810 --> 00:24:54,860
De îndată ce începe să aibă sute
numerelor, mii de numere,

504
00:24:54,860 --> 00:24:58,440
milioane de numere, Ben, probabil,
nu s-ar putea face destul de rapid,

505
00:24:58,440 --> 00:25:00,620
presupunând că au existat
decalaje în numere.

506
00:25:00,620 --> 00:25:03,450
Destul de ușor să numere până la un milion
în caz contrar, doar consumatoare de timp.

507
00:25:03,450 --> 00:25:07,150
>> Asa ca algoritmul suna
cum ar fi Ben folosit doar acum

508
00:25:07,150 --> 00:25:08,930
a fost căutarea pentru cel mai mic număr.

509
00:25:08,930 --> 00:25:12,900
Deci, chiar dacă noi, oamenii pot lua
într-o mulțime de informații vizuale,

510
00:25:12,900 --> 00:25:14,830
un calculator este de fapt
un pic mai limitat.

511
00:25:14,830 --> 00:25:17,560
Computerul poate doar
uita-te la un octet la un moment dat

512
00:25:17,560 --> 00:25:20,770
sau poate patru octeți de la un time--
în aceste zile, poate, 8 octeți de la un time--

513
00:25:20,770 --> 00:25:24,450
dar un număr foarte mic
de octeți la un moment dat.

514
00:25:24,450 --> 00:25:28,480
>> Așa că având în vedere că avem cu adevărat
patru valori distincte aici--

515
00:25:28,480 --> 00:25:32,440
și vă puteți gândi la Ben ca având
ochelari de cal, dacă ar fi fost un astfel de calculator

516
00:25:32,440 --> 00:25:36,450
că el nu poate vedea nimic altceva
peste un număr de la un time--

517
00:25:36,450 --> 00:25:39,720
așa că, în general, va presupune, la fel ca în
Engleză, vom citi de la dreapta la stânga.

518
00:25:39,720 --> 00:25:42,870
Deci, primul număr Ben, probabil, sa uitat
la patru a fost apoi foarte repede

519
00:25:42,870 --> 00:25:44,770
a dat seama că e destul de mare
number-- lasă-mă să continui să cauți.

520
00:25:44,770 --> 00:25:45,357
>> Sunt doi.

521
00:25:45,357 --> 00:25:45,940
Așteptaţi un minut.

522
00:25:45,940 --> 00:25:47,070
Două este mai mică decât patru.

523
00:25:47,070 --> 00:25:47,986
Mă duc să-mi amintesc.

524
00:25:47,986 --> 00:25:49,070
Doi este cel mai mic.

525
00:25:49,070 --> 00:25:50,417
Acum, asta e chiar Unu mai bine.

526
00:25:50,417 --> 00:25:51,250
Asta e chiar mai mic.

527
00:25:51,250 --> 00:25:54,000
Am de gând să uit de două
și amintiți-vă doar unul acum.

528
00:25:54,000 --> 00:25:56,550
>> Și ar putea să nu se mai uite?

529
00:25:56,550 --> 00:25:58,360
Ei bine, el ar putea bazat
aceste informații,

530
00:25:58,360 --> 00:26:00,477
dar el mai bine-ar căutare
restul listei.

531
00:26:00,477 --> 00:26:02,060
Pentru că ce se întâmplă dacă zero ar fi fost în listă?

532
00:26:02,060 --> 00:26:03,643
Ce se întâmplă dacă unul negativ au fost în listă?

533
00:26:03,643 --> 00:26:07,720
El știe doar că răspunsul lui
este corect dacă el este în mod exhaustiv

534
00:26:07,720 --> 00:26:08,729
verificat întreaga listă.

535
00:26:08,729 --> 00:26:10,020
Așa că ne uităm la restul.

536
00:26:10,020 --> 00:26:11,394
Three-- că a fost o pierdere de timp.

537
00:26:11,394 --> 00:26:13,540
Avut ghinion, dar am fost
încă corect de a face acest lucru.

538
00:26:13,540 --> 00:26:17,857
Și așa acum el probabil
selectat cel mai mic număr

539
00:26:17,857 --> 00:26:20,440
și pune-l doar la început
din listă, așa cum voi face aici.

540
00:26:20,440 --> 00:26:23,480
Acum, ce-ai făcut în continuare, chiar dacă
te-ai gândit la asta aproape

541
00:26:23,480 --> 00:26:25,962
în această măsură?

542
00:26:25,962 --> 00:26:27,670
Se repetă procesul,
astfel încât un fel de buclă.

543
00:26:27,670 --> 00:26:28,920
E o idee familiară.

544
00:26:28,920 --> 00:26:30,860
Deci, aici este de patru.

545
00:26:30,860 --> 00:26:32,110
Asta e în prezent, cele mai mici.

546
00:26:32,110 --> 00:26:33,220
Asta e un candidat.

547
00:26:33,220 --> 00:26:33,900
Nu mai.

548
00:26:33,900 --> 00:26:34,770
Acum am văzut două.

549
00:26:34,770 --> 00:26:36,630
Asta e urmatorul cel mai mic element.

550
00:26:36,630 --> 00:26:40,800
Three-- că nu este mai mică, așa
acum Ben poate scoate cele două.

551
00:26:40,800 --> 00:26:44,510
>> Și acum vom repeta procesul și
desigur, trei devine tras afară următor.

552
00:26:44,510 --> 00:26:45,420
Se repetă procedeul.

553
00:26:45,420 --> 00:26:46,990
Patru devine tras afară.

554
00:26:46,990 --> 00:26:50,140
Și acum nu mai avem numere,
astfel încât lista trebuie să fie sortate.

555
00:26:50,140 --> 00:26:51,960
>> Și într-adevăr, acest lucru este un algoritm formal.

556
00:26:51,960 --> 00:26:56,610
Un om de știință de calculator ar
numesc acest lucru "selecție sortare"

557
00:26:56,610 --> 00:27:00,880
ideea fiind un fel de
lista iteratively-- din nou

558
00:27:00,880 --> 00:27:03,807
și selectând din nou și din nou
cel mai mic număr.

559
00:27:03,807 --> 00:27:06,140
Și ce e frumos despre el este
este doar naibii de intuitiv.

560
00:27:06,140 --> 00:27:07,470
Este atât de simplu.

561
00:27:07,470 --> 00:27:11,100
Și tu poți repeta același lucru
operațiune din nou și din nou.

562
00:27:11,100 --> 00:27:12,150
E simplu.

563
00:27:12,150 --> 00:27:17,170
>> În acest caz, a fost rapid, dar
cât timp durează de fapt?

564
00:27:17,170 --> 00:27:19,880
Hai să facem să pară și
simt un pic mai plictisitor.

565
00:27:19,880 --> 00:27:24,150
Deci unul, doi, trei, patru, cinci și șase,
șapte, opt, nouă, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- număr arbitrar.

567
00:27:26,160 --> 00:27:28,780
Am vrut doar mai mult acest lucru
timp decât doar patru.

568
00:27:28,780 --> 00:27:30,780
Așa că, dacă am un întreg
grămadă de numere l now--

569
00:27:30,780 --> 00:27:32,420
chiar nu contează
ceea ce ei are-- lui lasa

570
00:27:32,420 --> 00:27:34,380
gândiți-vă ce acest lucru
Algoritmul este într-adevăr ca.

571
00:27:34,380 --> 00:27:35,857
>> Să presupunem că există un număr de acolo.

572
00:27:35,857 --> 00:27:38,190
Din nou, nu contează ce
ele sunt, dar sunt aleatorii.

573
00:27:38,190 --> 00:27:39,679
Sunt aplicarea algoritmului lui Ben.

574
00:27:39,679 --> 00:27:41,220
Am nevoie pentru a selecta cel mai mic număr.

575
00:27:41,220 --> 00:27:41,761
Ce fac?

576
00:27:41,761 --> 00:27:44,240
Și mă duc la punct de vedere fizic
fă-o de data aceasta să-l interpreteze.

577
00:27:44,240 --> 00:27:46,099
Cautam, cherestea,
Cautam, cautati, cautati.

578
00:27:46,099 --> 00:27:48,140
Numai când am ajunge la
la sfârșitul listei poate

579
00:27:48,140 --> 00:27:51,230
Îmi dau seama cel mai mic
numarul doi a fost de data asta.

580
00:27:51,230 --> 00:27:52,720
Nu mai e în listă.

581
00:27:52,720 --> 00:27:54,400
Așa că am pus jos două.

582
00:27:54,400 --> 00:27:55,590
>> Ce trebuie să fac în continuare?

583
00:27:55,590 --> 00:27:58,600
Cautam, Cautam, cherestea, cautati.

584
00:27:58,600 --> 00:28:02,250
Acum am găsit numărul șapte, deoarece
există lacune în aceste Numere

585
00:28:02,250 --> 00:28:03,300
ci pur și simplu arbitrar.

586
00:28:03,300 --> 00:28:03,800
In regula.

587
00:28:03,800 --> 00:28:06,030
Așa că acum pot pune în jos șapte.

588
00:28:06,030 --> 00:28:08,860
Looking Cautam, caut.

589
00:28:08,860 --> 00:28:11,030
>> Acum, eu sunt presupunând,
Desigur, că Ben nu

590
00:28:11,030 --> 00:28:14,780
au memorie RAM suplimentar, suplimentar
memorie, pentru că, desigur,

591
00:28:14,780 --> 00:28:16,080
Mă uit la același număr.

592
00:28:16,080 --> 00:28:18,246
Cu siguranță aș fi putut aminti
toate aceste numere,

593
00:28:18,246 --> 00:28:19,930
și asta e absolut adevărat.

594
00:28:19,930 --> 00:28:22,610
Dar, dacă Ben își aduce aminte toate
a numerelor a văzut,

595
00:28:22,610 --> 00:28:24,430
el nu și-a făcut într-adevăr
un progres fundamental

596
00:28:24,430 --> 00:28:26,170
pentru că el are deja
capacitatea de a căuta

597
00:28:26,170 --> 00:28:27,540
prin numerele de pe bord.

598
00:28:27,540 --> 00:28:29,373
Amintindu cele de mai
Numerele nu ajută,

599
00:28:29,373 --> 00:28:32,490
pentru că el încă se poate ca un computer
uita-te doar, ne-am spus, un singur număr

600
00:28:32,490 --> 00:28:33,080
la un moment dat.

601
00:28:33,080 --> 00:28:35,760
Deci, nu există nici un fel de ieftin
acolo pe care le puteți pârghie.

602
00:28:35,760 --> 00:28:39,170
>> Așa că, în realitate, așa cum am
continuați căutarea lista,

603
00:28:39,170 --> 00:28:44,200
Eu pur și simplu trebuie să păstreze doar merge
înainte și înapoi prin ea, jumulire afară

604
00:28:44,200 --> 00:28:45,710
următorul număr mai mic.

605
00:28:45,710 --> 00:28:48,810
Și, după cum se poate deduce un fel de
din mișcările mele stupide,

606
00:28:48,810 --> 00:28:50,860
acest lucru devine doar foarte
plictisitor foarte repede,

607
00:28:50,860 --> 00:28:54,850
și mi se pare să fie merge înapoi și
mai departe, înainte și înapoi destul de un pic.

608
00:28:54,850 --> 00:29:03,220
Acum, pentru a fi corect, nu trebuie să merg
destul ca, de asemenea, să see-- să fie echitabil,

609
00:29:03,220 --> 00:29:06,310
Nu trebuie să meargă destul de
cât mai multe etape de fiecare dată.

610
00:29:06,310 --> 00:29:09,200
Pentru că, desigur, așa cum am
selectați numerele din listă,

611
00:29:09,200 --> 00:29:11,860
lista rămasă se scurtează.

612
00:29:11,860 --> 00:29:14,240
>> Și așa să ne gândim la
câți pași sunt de fapt eu

613
00:29:14,240 --> 00:29:16,010
traipsing prin fiecare dată.

614
00:29:16,010 --> 00:29:18,950
În prima situație
am avut 16 numere,

615
00:29:18,950 --> 00:29:22,210
și așa mai maximally-- lui lasa doar
face acest lucru pentru o discussion--

616
00:29:22,210 --> 00:29:25,640
A trebuit să se uite prin 16
Numerele pentru a găsi cele mai mici.

617
00:29:25,640 --> 00:29:28,420
Dar, odată ce am smuls
cel mai mic număr, cum

618
00:29:28,420 --> 00:29:30,590
lung a fost lista rămasă, desigur?

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

620
00:29:31,420 --> 00:29:34,670
Deci, cât de multe numere de făcut Ben sau am
să se uite prin a doua oară în jurul valorii de?

621
00:29:34,670 --> 00:29:36,832
15, doar pentru a merge și de a găsi cele mai mici.

622
00:29:36,832 --> 00:29:39,540
Dar acum, desigur, lista este,
de asemenea, mai mică decât era înainte.

623
00:29:39,540 --> 00:29:42,540
Deci, cum mulți pași a făcut eu
trebuie să ia data viitoare?

624
00:29:42,540 --> 00:29:49,970
14 și apoi 13 și apoi 12, plus punct,
punct, punct, până când am rămas doar cu unul.

625
00:29:49,970 --> 00:29:53,146
Deci, acum, un om de știință de calculator ar
întreba, bine, ce înseamnă că toți egali?

626
00:29:53,146 --> 00:29:55,770
Ea este egală cu de fapt, unele din beton
număr pe care am putea cu siguranță

627
00:29:55,770 --> 00:30:00,490
do aritmetic, dar vrem să vorbim
despre eficiența algoritmilor

628
00:30:00,490 --> 00:30:04,940
un pic mai mult formulaically,
independent de cât timp este lista.

629
00:30:04,940 --> 00:30:06,240
>> Și așa, știi ce?

630
00:30:06,240 --> 00:30:09,860
Acest lucru este de 16, dar cum am spus mai înainte,
Să numim doar dimensiunea problemei

631
00:30:09,860 --> 00:30:10,970
n, unde n este un număr.

632
00:30:10,970 --> 00:30:13,220
Poate că e 16, poate că e
trei, poate e un milion.

633
00:30:13,220 --> 00:30:13,761
Nu știu.

634
00:30:13,761 --> 00:30:14,390
Nu-mi pasă.

635
00:30:14,390 --> 00:30:16,520
Ceea ce eu doresc cu adevărat este
o formulă pe care eu pot

636
00:30:16,520 --> 00:30:19,420
utilizați pentru a compara acest algoritm
împotriva altor algoritmi

637
00:30:19,420 --> 00:30:22,350
că cineva ar putea pretinde
sunt mai bune sau mai rele.

638
00:30:22,350 --> 00:30:25,430
>> Deci, se pare, și numai eu
știu acest lucru de la școală grad,

639
00:30:25,430 --> 00:30:34,790
că acest fapt funcționează la fel
lucru ca n peste n plus unu peste doi.

640
00:30:34,790 --> 00:30:40,020
Și acest lucru se întâmplă să fie egal, de
Desigur, n plus la pătrat n peste două.

641
00:30:40,020 --> 00:30:43,250
Deci, dacă am vrut o formulă
pentru cât de multe etape

642
00:30:43,250 --> 00:30:46,330
au fost implicați în căutarea la toate
din aceste numere din nou și din nou

643
00:30:46,330 --> 00:30:52,681
și din nou și din nou, aș spune
este n plus la pătrat n peste două.

644
00:30:52,681 --> 00:30:53,430
Dar știi ce?

645
00:30:53,430 --> 00:30:54,500
Acest lucru pur și simplu arată murdar.

646
00:30:54,500 --> 00:30:56,470
Vreau doar într-adevăr o
sens general al lucrurilor.

647
00:30:56,470 --> 00:30:58,810
Si s-ar putea aminti de
liceu că acolo

648
00:30:58,810 --> 00:31:00,660
este noțiunea de cea mai înaltă pe termen ordine.

649
00:31:00,660 --> 00:31:05,300
Care dintre acești termeni, n
patrat, n, sau jumătate,

650
00:31:05,300 --> 00:31:07,550
are cel mai mare impact asupra timpului?

651
00:31:07,550 --> 00:31:11,920
Cu cat mai mare n devine, care
din aceste chestiuni cel mai mult?

652
00:31:11,920 --> 00:31:15,560
>> Cu alte cuvinte, dacă am conectați
într-un milion, n-patrat

653
00:31:15,560 --> 00:31:17,900
va fi cel mai probabil
factorul dominant,

654
00:31:17,900 --> 00:31:21,670
pentru că un milion de ori
în sine este mult mai mare

655
00:31:21,670 --> 00:31:23,682
decât plus un milion suplimentar.

656
00:31:23,682 --> 00:31:24,390
Deci, tu ce știi?

657
00:31:24,390 --> 00:31:27,305
Aceasta este o astfel de darn mare
număr, dacă aveți un număr pătrat.

658
00:31:27,305 --> 00:31:28,430
Acest lucru nu contează cu adevărat.

659
00:31:28,430 --> 00:31:30,596
Vom merge doar cruce care
afară și uită de asta.

660
00:31:30,596 --> 00:31:34,250
Și astfel, un om de știință calculator ar spune
că eficiența acestui algoritm

661
00:31:34,250 --> 00:31:37,850
este de ordinul n squared--
Vreau să spun cu adevărat o aproximare.

662
00:31:37,850 --> 00:31:40,810
Este un fel de aproximativ n la pătrat.

663
00:31:40,810 --> 00:31:44,130
De-a lungul timpului, cu atat mai mare
și mai mare n devine, acest lucru

664
00:31:44,130 --> 00:31:47,610
este o estimare bună pentru ceea ce
eficiența sau lipsa de eficiență

665
00:31:47,610 --> 00:31:49,400
din acest algoritm este de fapt.

666
00:31:49,400 --> 00:31:52,040
Iar eu derivă că, desigur,
de la a face de fapt matematica.

667
00:31:52,040 --> 00:31:54,040
Dar acum eu sunt doar fluturand
mâinile mele, pentru că eu doar

668
00:31:54,040 --> 00:31:55,790
doresc un sens general al acestui algoritm.

669
00:31:55,790 --> 00:31:58,850
>> Așa că, folosind aceeași logică, între timp,
Să considerăm un alt algoritm

670
00:31:58,850 --> 00:32:01,162
am uitat deja at-- căutare liniară.

671
00:32:01,162 --> 00:32:02,870
Când am fost în căutarea
pentru book-- telefonului

672
00:32:02,870 --> 00:32:05,980
nu-l sortarea, căutarea
prin intermediul telefonului book--

673
00:32:05,980 --> 00:32:09,197
am continuat spunând că acesta a fost
1000 trepte, sau 500 de pași.

674
00:32:09,197 --> 00:32:10,280
Dar, să generalizăm asta.

675
00:32:10,280 --> 00:32:12,860
În cazul în care există n pagini în
cartea de telefon, ceea ce este

676
00:32:12,860 --> 00:32:17,250
timpul de rulare sau
eficiența de căutare liniară?

677
00:32:17,250 --> 00:32:19,750
Este pe ordinea
cât de mulți pași pentru a găsi

678
00:32:19,750 --> 00:32:24,210
Mike Smith, folosind căutarea liniară, The
primul algoritm, sau chiar a doua?

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

680
00:32:27,240 --> 00:32:31,710
>> În cel mai rău caz, Mike
se află la sfârșitul cărții.

681
00:32:31,710 --> 00:32:35,590
Așa că în cazul în care cartea de telefon are 1.000 de pagini,
am spus ultima oară, în cel mai rău caz,

682
00:32:35,590 --> 00:32:38,380
ar putea dura aproximativ cât
mai multe pagini pentru a găsi Mike?

683
00:32:38,380 --> 00:32:38,990
Ca 1000.

684
00:32:38,990 --> 00:32:39,830
Este o limită superioară.

685
00:32:39,830 --> 00:32:41,790
Este o situație cel mai rău posibil.

686
00:32:41,790 --> 00:32:44,410
Dar, din nou, ne mișcăm departe
de la numere ca 1000 acum.

687
00:32:44,410 --> 00:32:45,730
Este pur și simplu n.

688
00:32:45,730 --> 00:32:47,470
>> Deci, ce este concluzia logică?

689
00:32:47,470 --> 00:32:50,210
Găsirea Mike într-un telefon
carte care are n pagini

690
00:32:50,210 --> 00:32:55,280
s-ar putea lua, în cel mai rău caz,
câți pași pe ordinea de n?

691
00:32:55,280 --> 00:32:58,110
Și, într-adevăr, un calculator
om de știință ar spune

692
00:32:58,110 --> 00:33:02,340
că timpul de funcționare, sau
performanța sau eficiența

693
00:33:02,340 --> 00:33:07,470
sau ineficiența, a unui algoritm similar
o căutare liniară este de ordinul n.

694
00:33:07,470 --> 00:33:10,010
Si putem aplica la fel
Logica de trecere ceva

695
00:33:10,010 --> 00:33:13,170
așa cum tocmai am făcut-o la a doua
algoritm am avut-o cu cartea de telefon,

696
00:33:13,170 --> 00:33:16,040
în cazul în care ne-am dus două pagini la un moment dat.

697
00:33:16,040 --> 00:33:20,120
>> Așa că 1.000 de pagini de carte de telefon s-ar putea
să ne ia 500 de pagini se transformă, plus unu

698
00:33:20,120 --> 00:33:21,910
dacă ne replia un pic.

699
00:33:21,910 --> 00:33:26,590
Așa că, dacă o carte de telefon are n pagini, dar
facem două pagini la un moment dat,

700
00:33:26,590 --> 00:33:28,900
asta e cam ce?

701
00:33:28,900 --> 00:33:33,190
N peste două, astfel încât e ca n peste doi.

702
00:33:33,190 --> 00:33:38,490
Dar am făcut revendica un
momentul în urmă că N pe parcursul two--

703
00:33:38,490 --> 00:33:41,060
asta e cam la fel ca și pur și simplu n.

704
00:33:41,060 --> 00:33:44,050
Este doar un factor constant,
oamenii de știință de calculator ar spune.

705
00:33:44,050 --> 00:33:45,970
Să ne concentrăm numai asupra
variabilele, really--

706
00:33:45,970 --> 00:33:47,780
cele mai mari variabile în ecuație.

707
00:33:47,780 --> 00:33:52,530
>> căutare atât de liniar, dacă unul făcut
pagină la un moment dat sau două pagini la un moment dat,

708
00:33:52,530 --> 00:33:54,810
este un fel de fundamental același.

709
00:33:54,810 --> 00:33:56,880
Este încă pe ordinea de n.

710
00:33:56,880 --> 00:34:01,930
Dar am susținut cu poza mea anterioară
că al treilea algoritm nu a fost

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

712
00:34:02,480 --> 00:34:03,605
Nu a fost o linie dreaptă.

713
00:34:03,605 --> 00:34:08,659
Era acea linie curbă, iar
algebrică cu formula acolo ce era?

714
00:34:08,659 --> 00:34:11,812
Jurnal de bază log, astfel N- doi n.

715
00:34:11,812 --> 00:34:14,520
Si noi nu trebuie să intru în prea
multe detalii despre logaritmi astăzi,

716
00:34:14,520 --> 00:34:17,394
dar cei mai mulți oameni de știință de calculator nu ar
chiar îți spun ce baza este.

717
00:34:17,394 --> 00:34:20,639
Pentru că e totul doar
factori constant, ca să spunem așa,

718
00:34:20,639 --> 00:34:22,659
doar diferențe numerice ușoare.

719
00:34:22,659 --> 00:34:31,179
Și, astfel încât acest lucru ar fi un foarte frecvente
mod de calculator deosebit formale

720
00:34:31,179 --> 00:34:33,949
oamenii de știință de la un consiliu sau
programatori de la o tablă albă

721
00:34:33,949 --> 00:34:36,889
de fapt, argumentând care
Algoritmul le-ar folosi

722
00:34:36,889 --> 00:34:39,500
sau ce eficiența
a algoritmului lor este.

723
00:34:39,500 --> 00:34:42,960
>> Și acest lucru nu este neapărat ceva
discuți în orice detaliu,

724
00:34:42,960 --> 00:34:47,889
dar un programator bun este cineva
care are un background solid, formal.

725
00:34:47,889 --> 00:34:50,120
El este capabil să vorbească
vă în acest fel de mod

726
00:34:50,120 --> 00:34:53,350
și de fapt, face
argumente calitative ca

727
00:34:53,350 --> 00:34:56,870
de ce un singur algoritm sau
o singură bucată de software

728
00:34:56,870 --> 00:35:00,165
este superior într-un fel la altul.

729
00:35:00,165 --> 00:35:02,540
Pentru că ai putea cu siguranță
doar rulați programul unei singure persoane

730
00:35:02,540 --> 00:35:04,980
și numără numărul de secunde
este nevoie pentru a sorta unele numere,

731
00:35:04,980 --> 00:35:06,710
și puteți rula unele
Programul altei persoane

732
00:35:06,710 --> 00:35:08,418
și conta numărul
secunde este nevoie.

733
00:35:08,418 --> 00:35:12,840
Dar acesta este un mod mai general, că
puteți utiliza pentru a analiza algoritmi,

734
00:35:12,840 --> 00:35:15,520
dacă va fi, pur și simplu pe
hârtie sau pur și simplu verbal.

735
00:35:15,520 --> 00:35:18,430
Chiar fără să fie difuzate, fără
chiar încercarea de intrări de probă,

736
00:35:18,430 --> 00:35:20,180
te poți înțelege pur și simplu prin ea.

737
00:35:20,180 --> 00:35:24,670
Și așa mai departe cu angajarea unui dezvoltator sau dacă
având în el sau ea un fel de tine pentru a argumenta

738
00:35:24,670 --> 00:35:28,460
de ce algoritmul lor, secretul lor
sos pentru căutarea miliarde

739
00:35:28,460 --> 00:35:30,580
de pagini web pentru dumneavoastra
companie este mai bine, acestea

740
00:35:30,580 --> 00:35:33,302
sunt tipurile de argumentele pe care le
ar trebui să fie în mod ideal, capabil să facă.

741
00:35:33,302 --> 00:35:35,010
Sau cel puțin acestea sunt
tipurile de lucruri

742
00:35:35,010 --> 00:35:40,211
care ar veni în discuție, la
cel puțin într-o discuție foarte formală.

743
00:35:40,211 --> 00:35:40,710
In regula.

744
00:35:40,710 --> 00:35:44,400
Așa că Ben a propus ceva
numita selecție de sortare.

745
00:35:44,400 --> 00:35:48,200
Dar voi propune ca acolo
alte moduri de a face acest lucru, de asemenea.

746
00:35:48,200 --> 00:35:50,400
Ceea ce nu am place foarte mult
despre algoritmul lui Ben

747
00:35:50,400 --> 00:35:54,400
este că el a continuat mersul pe jos, sau
după ce mă mers pe jos, înainte și înapoi

748
00:35:54,400 --> 00:35:56,930
și înainte și înapoi și înainte și înapoi.

749
00:35:56,930 --> 00:36:04,130
Ce se întâmplă dacă în schimb ar fi să fac
ceva de genul aceste numere de aici

750
00:36:04,130 --> 00:36:08,200
și am fost să se ocupe doar cu fiecare
număr la rândul său, așa cum am dat-o?

751
00:36:08,200 --> 00:36:10,780
>> Cu alte cuvinte, aici e
lista mea de numere.

752
00:36:10,780 --> 00:36:12,944
Patru, una, trei, doi.

753
00:36:12,944 --> 00:36:14,360
Si eu voi face următoarele.

754
00:36:14,360 --> 00:36:17,230
Voi insera numerele
în cazul în care acestea aparțin mai degrabă

755
00:36:17,230 --> 00:36:18,980
decât selectarea lor unul la un moment dat.

756
00:36:18,980 --> 00:36:20,820
Cu alte cuvinte, aici e numărul patru.

757
00:36:20,820 --> 00:36:22,430
>> Aici e lista mea originală.

758
00:36:22,430 --> 00:36:25,290
Și voi menține
în esență, o nouă listă aici.

759
00:36:25,290 --> 00:36:26,710
Deci, aceasta este lista veche.

760
00:36:26,710 --> 00:36:28,560
Aceasta este noua listă.

761
00:36:28,560 --> 00:36:30,220
Eu văd numărul patru întâi.

762
00:36:30,220 --> 00:36:34,500
Noua mea Lista este inițial goală,
așa că este trivial cazul

763
00:36:34,500 --> 00:36:36,410
că patru este acum lista de asortat.

764
00:36:36,410 --> 00:36:39,560
Eu doar iau numărul I-am dat,
si eu o pune în noua mea listă.

765
00:36:39,560 --> 00:36:41,460
>> Este sortata această nouă listă?

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

767
00:36:41,990 --> 00:36:45,090
E o prostie pentru că există doar un singur
Element, dar este absolut sortate.

768
00:36:45,090 --> 00:36:46,390
Nu e nimic din loc.

769
00:36:46,390 --> 00:36:49,290
Este mai interesant, acest algoritm,
când am trece la pasul următor.

770
00:36:49,290 --> 00:36:50,550
>> Acum am unul.

771
00:36:50,550 --> 00:36:55,430
Așa că unul, desigur, aparține la cele mai
începutul sau la sfârșitul acestei noi liste?

772
00:36:55,430 --> 00:36:56,360
Inceputul.

773
00:36:56,360 --> 00:36:58,530
Așa că trebuie să fac ceva de lucru acum.

774
00:36:58,530 --> 00:37:01,410
Am luat niște
libertăți cu markerul

775
00:37:01,410 --> 00:37:03,120
prin tragere la doar lucruri
în cazul în care le-am dorit,

776
00:37:03,120 --> 00:37:05,320
dar asta nu e cu adevărat
exacte într-un calculator.

777
00:37:05,320 --> 00:37:08,530
Un calculator, după cum știm, are
RAM sau Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
și asta e un octet și
un alt octet și un alt octet.

779
00:37:12,411 --> 00:37:14,910
Și, dacă aveți un gigabyte de
RAM, ai un miliard de bytes,

780
00:37:14,910 --> 00:37:16,680
dar sunt fizic într-o singură locație.

781
00:37:16,680 --> 00:37:19,540
Nu te poți mișca doar lucruri în jurul valorii de
prin tragere-l pe placa

782
00:37:19,540 --> 00:37:20,750
oriunde vrei.

783
00:37:20,750 --> 00:37:24,090
Așa că, dacă noua mea listă are
patru locații în memorie,

784
00:37:24,090 --> 00:37:27,480
din păcate, cele patru este
deja în locul greșit.

785
00:37:27,480 --> 00:37:30,410
>> Deci, pentru a se introduce numărul unu
Nu pot desena aici.

786
00:37:30,410 --> 00:37:31,901
Această locație de memorie nu există.

787
00:37:31,901 --> 00:37:35,150
Asta ar fi inselat, și am fost
inseala pictural pentru câteva minute

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

789
00:37:35,800 --> 00:37:40,950
Așa că într-adevăr, dacă vreau să pun unul aici,
Trebuie să copiați temporar cele patru

790
00:37:40,950 --> 00:37:43,030
și a pus apoi pe cel de acolo.

791
00:37:43,030 --> 00:37:45,500
>> E în regulă, asta e corect,
că este posibil punct de vedere tehnic,

792
00:37:45,500 --> 00:37:48,410
dar dau seama că e muncă suplimentară.

793
00:37:48,410 --> 00:37:50,460
Nu am pus doar numărul în loc.

794
00:37:50,460 --> 00:37:53,026
Am avut mai întâi să se miște un
număr, apoi pus în aplicare,

795
00:37:53,026 --> 00:37:54,650
așa că am cam dublat suma mea de muncă.

796
00:37:54,650 --> 00:37:55,660
Astfel încât să păstreze în minte.

797
00:37:55,660 --> 00:37:57,120
>> Dar eu sunt acum terminat cu acest element.

798
00:37:57,120 --> 00:37:59,056
Acum vreau să apuca numărul trei.

799
00:37:59,056 --> 00:38:00,430
În cazul în care, desigur, nu-i aparține?

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

801
00:38:01,480 --> 00:38:03,650
Nu mai pot înșela
și pune-l doar acolo,

802
00:38:03,650 --> 00:38:06,770
pentru că, din nou, această memorie
se află în locații fizice.

803
00:38:06,770 --> 00:38:10,900
Așa că trebuie să copiați cele patru
și a pus trei aici.

804
00:38:10,900 --> 00:38:11,550
Nu e mare lucru.

805
00:38:11,550 --> 00:38:14,610
Este doar un pas suplimentar
again-- se simte foarte ieftin.

806
00:38:14,610 --> 00:38:16,445
>> Dar acum mă mut la cei doi.

807
00:38:16,445 --> 00:38:17,820
Cei doi, desigur, aparține aici.

808
00:38:17,820 --> 00:38:20,990
Acum începe să vedeți cum
munca poate aduna.

809
00:38:20,990 --> 00:38:23,520
Acum, ce trebuie să fac?

810
00:38:23,520 --> 00:38:28,570
Da, trebuie să se mute cele patru,
atunci am să copiați trei,

811
00:38:28,570 --> 00:38:31,200
iar acum pot insera cele două.

812
00:38:31,200 --> 00:38:34,460
Și captura cu această
algoritm, destul de interesant,

813
00:38:34,460 --> 00:38:41,050
este că să presupunem că avem mai extreme
cazul în care este să zicem opt, șapte,

814
00:38:41,050 --> 00:38:45,150
șase, cinci, patru, trei, doi, unu.

815
00:38:45,150 --> 00:38:49,450
Acest lucru este, în multe contexte,
cel mai rău scenariu,

816
00:38:49,450 --> 00:38:51,570
pentru că darn lucru
este literalmente înapoi.

817
00:38:51,570 --> 00:38:53,670
>> Ea nu prea
afectează algoritmul lui Ben,

818
00:38:53,670 --> 00:38:55,940
pentru că în selecția lui Ben
sortare el va păstra

819
00:38:55,940 --> 00:38:58,359
merge înainte și înapoi prin listă.

820
00:38:58,359 --> 00:39:01,150
Și, pentru că el a fost mereu în căutarea
prin toata lista rămasă,

821
00:39:01,150 --> 00:39:02,858
nu contează
în cazul în care elementele sunt.

822
00:39:02,858 --> 00:39:05,630
Dar, în acest caz, cu inserarea mea
approach-- să încercăm.

823
00:39:05,630 --> 00:39:08,616
>> Deci unul, doi, trei, patru,
cinci, șase, șapte, opt.

824
00:39:08,616 --> 00:39:11,630
Unu doi trei patru,
cinci, șase, șapte, opt.

825
00:39:11,630 --> 00:39:14,320
Mă duc să iau cele opt,
și unde am pus-o?

826
00:39:14,320 --> 00:39:17,260
Ei bine, la începutul listei mele,
deoarece această nouă listă este sortată.

827
00:39:17,260 --> 00:39:18,760
Si eu l trec afară.

828
00:39:18,760 --> 00:39:20,551
>> Unde am pus șapte?

829
00:39:20,551 --> 00:39:21,050
La naiba.

830
00:39:21,050 --> 00:39:23,174
Este nevoie să meargă acolo, așa
Trebuie să fac niște copiere.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Și acum cei șapte merge aici.

833
00:39:28,480 --> 00:39:29,860
Acum am trece la șase.

834
00:39:29,860 --> 00:39:30,980
Acum este și mai mult de lucru.

835
00:39:30,980 --> 00:39:32,570
>> Opt trebuie să meargă aici.

836
00:39:32,570 --> 00:39:33,920
Șapte trebuie să meargă aici.

837
00:39:33,920 --> 00:39:35,450
Acum, cei șase pot merge aici.

838
00:39:35,450 --> 00:39:37,950
Acum am apuca cinci.

839
00:39:37,950 --> 00:39:40,560
Acum opt trebuie să meargă
aici, șapte trebuie să meargă aici,

840
00:39:40,560 --> 00:39:43,650
șase trebuie să meargă aici, și
acum cinci și se repetă.

841
00:39:43,650 --> 00:39:46,610
Și eu sunt destul de mult
se deplasează în mod constant.

842
00:39:46,610 --> 00:39:52,950
>> Deci, la final, această algorithm-- ne vom
numesc inserție de fapt sort--

843
00:39:52,950 --> 00:39:55,020
are o mulțime de muncă, de asemenea.

844
00:39:55,020 --> 00:39:56,970
E doar diferit
un fel de muncă decât cea a lui Ben.

845
00:39:56,970 --> 00:40:00,090
munca lui Ben a avut-mi merge
înainte și înapoi, tot timpul,

846
00:40:00,090 --> 00:40:03,510
selectarea următoarea cea mai mică
Element din nou și din nou.

847
00:40:03,510 --> 00:40:06,660
Deci, a fost acest tip foarte vizual de muncă.

848
00:40:06,660 --> 00:40:10,600
>> Celălalt algoritm, care este încă
correct-- va primi slujba done--

849
00:40:10,600 --> 00:40:12,800
schimba doar cantitatea de muncă.

850
00:40:12,800 --> 00:40:15,420
Se pare că inițial ești
de economisire, pentru că tu ești doar

851
00:40:15,420 --> 00:40:19,190
care se ocupă cu fiecare element
în față, fără a mers pe jos toate

852
00:40:19,190 --> 00:40:20,930
drum prin listă ca Ben a fost.

853
00:40:20,930 --> 00:40:25,300
Dar problema este, mai ales în aceste
cazuri nebune unde e totul în spate,

854
00:40:25,300 --> 00:40:27,830
tu esti doar un fel de
amânarea munca grea

855
00:40:27,830 --> 00:40:30,360
până când trebuie să repare greșelile.

856
00:40:30,360 --> 00:40:33,919
>> Și astfel, dacă vă puteți imagina acest lucru
opt și șapte și șase și cinci

857
00:40:33,919 --> 00:40:36,710
și mai târziu, patru și trei și doi
se deplasează prin modul lor listă,

858
00:40:36,710 --> 00:40:39,060
tocmai am schimbat
tipul de muncă ce facem.

859
00:40:39,060 --> 00:40:42,340
În loc de a face-o la
începând din iterație mea,

860
00:40:42,340 --> 00:40:45,250
Eu doar o fac la cele mai
sfârșitul termenului de fiecare iterație.

861
00:40:45,250 --> 00:40:50,550
Deci, se pare că acest algoritm,
de asemenea, în general, numit inserare de sortare,

862
00:40:50,550 --> 00:40:52,190
este, de asemenea, pe ordinea de n pătrat.

863
00:40:52,190 --> 00:40:56,480
Este de fapt nu mai bine,
nu mai bine deloc.

864
00:40:56,480 --> 00:41:00,810
>> Cu toate acestea, există oa treia abordare
Eu ne-ar încuraja să ia în considerare,

865
00:41:00,810 --> 00:41:02,970
care este aceasta.

866
00:41:02,970 --> 00:41:07,850
Așa că să presupunem că lista mea, pentru simplitate
din nou, este de patru, unul, trei,

867
00:41:07,850 --> 00:41:11,080
two-- doar patru numere.

868
00:41:11,080 --> 00:41:13,300
Ben a avut intuiție bună,
intuiție umană bună

869
00:41:13,300 --> 00:41:16,340
mai înainte, prin care ne-am fixat întreg
lista eventually-- sortare inserare.

870
00:41:16,340 --> 00:41:18,020
Eu ne-au convins de-a lungul.

871
00:41:18,020 --> 00:41:22,530
Dar haideți să considerăm
modalitate simplă de a rezolva această listă.

872
00:41:22,530 --> 00:41:24,110
>> Această listă nu este sortat.

873
00:41:24,110 --> 00:41:26,130
De ce?

874
00:41:26,130 --> 00:41:31,920
În limba engleză, explica de ce
nu este de fapt sortate.

875
00:41:31,920 --> 00:41:33,400
Ce înseamnă să nu fie sortate?

876
00:41:33,400 --> 00:41:34,220
>> ELEVUL: Nu este secvențială.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Nu secvențială.

878
00:41:34,990 --> 00:41:35,822
Dă-mi un exemplu.

879
00:41:35,822 --> 00:41:37,180
>> ELEVUL: Pune-le în ordine.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Da-mi un exemplu mai specific.

882
00:41:38,790 --> 00:41:39,832
>> ELEVUL: ordine crescătoare.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Nu sunt ordine crescătoare.

884
00:41:41,206 --> 00:41:42,100
Mai precis.

885
00:41:42,100 --> 00:41:45,190
Nu știu ce vrei să spui ascendent.

886
00:41:45,190 --> 00:41:47,150
Ce s-a întâmplat?

887
00:41:47,150 --> 00:41:49,930
>> Elev: Cel mai mic dintre
Numerele nu este în primul spațiu.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: Cel mai mic număr de
Nu în primul spațiu.

889
00:41:51,140 --> 00:41:52,120
Fii mai clar.

890
00:41:52,120 --> 00:41:55,000
Încep să mă prindă.

891
00:41:55,000 --> 00:41:59,470
Contăm, dar
ce e de ordine aici?

892
00:41:59,470 --> 00:42:00,707
>> ELEVUL: secvență numerică.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: secvență numerică.

894
00:42:02,040 --> 00:42:04,248
un fel tuturor de păstrare
l aici-- nivel foarte ridicat.

895
00:42:04,248 --> 00:42:07,450
Doar literalmente spune-mi ce-i
greșit ca o putere de cinci ani.

896
00:42:07,450 --> 00:42:08,310
>> ELEVUL: Plus unul.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Ce-i asta?

898
00:42:08,750 --> 00:42:09,610
>> ELEVUL: Plus unul.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Ce vrei să spui, plus unul?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Dă-mi un alt copil de cinci ani.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Ce sa întâmplat, mamă?

904
00:42:18,330 --> 00:42:19,940
Ce sa întâmplat, tată?

905
00:42:19,940 --> 00:42:22,808
Ce vrei sa spui acest lucru nu este sortat?

906
00:42:22,808 --> 00:42:24,370
>> ELEVUL: Nu e locul potrivit.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Ce este
nu în locul potrivit?

908
00:42:25,580 --> 00:42:26,174
>> ELEVUL: Patru.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, bine.

910
00:42:27,090 --> 00:42:29,110
Așa că patru nu este în cazul în care ar trebui să fie.

911
00:42:29,110 --> 00:42:30,590
În special, este acest drept?

912
00:42:30,590 --> 00:42:33,000
Patru și unul, primele
două numere pe care le văd.

913
00:42:33,000 --> 00:42:34,930
Este corect?

914
00:42:34,930 --> 00:42:36,427
Nu, sunt de ordine, nu?

915
00:42:36,427 --> 00:42:38,135
De fapt, cred că acum
despre un computer, de asemenea.

916
00:42:38,135 --> 00:42:40,824
Ea se poate uita doar la unul, poate,
poate două lucruri la once--

917
00:42:40,824 --> 00:42:43,240
și de fapt, doar un singur lucru
la un moment dat, dar poate cel puțin

918
00:42:43,240 --> 00:42:45,790
uita-te la un singur lucru interceptează
Următorul lucru chiar lângă el.

919
00:42:45,790 --> 00:42:47,380
>> Sunt acestea în ordine?

920
00:42:47,380 --> 00:42:48,032
Desigur că nu.

921
00:42:48,032 --> 00:42:48,740
Deci, tu ce știi?

922
00:42:48,740 --> 00:42:51,020
De ce nu luăm copilul
pași de fixare această problemă

923
00:42:51,020 --> 00:42:53,410
în loc de a face aceste fantezie
algoritmi cum ar fi Ben, unde

924
00:42:53,410 --> 00:42:56,440
el e un fel de ea de fixare
looping prin lista

925
00:42:56,440 --> 00:42:59,670
în loc de a face ceea ce am făcut, în cazul în care
Am doar un fel de reparat așa cum vom merge?

926
00:42:59,670 --> 00:43:03,650
Să ne rupe doar literalmente în jos
Noțiunea de ordine numerică order--,

927
00:43:03,650 --> 00:43:06,990
numesc orice ai o doresti
în aceste comparații perechi.

928
00:43:06,990 --> 00:43:07,590
>> Patru și unu.

929
00:43:07,590 --> 00:43:09,970
Este aceasta ordinea corectă?

930
00:43:09,970 --> 00:43:11,310
Așa că hai să repare asta.

931
00:43:11,310 --> 00:43:14,700
Unu și patru, și apoi
vom copia doar asta.

932
00:43:14,700 --> 00:43:15,560
Bine, bine.

933
00:43:15,560 --> 00:43:17,022
Am fixat unul și patru.

934
00:43:17,022 --> 00:43:18,320
Trei și doi?

935
00:43:18,320 --> 00:43:18,820
Nu.

936
00:43:18,820 --> 00:43:21,690
Cuvintele mele se potrivesc degetele mele.

937
00:43:21,690 --> 00:43:23,695
Patru și trei?

938
00:43:23,695 --> 00:43:27,930
>> Nu e în ordine, așa că voi
pentru a face una, trei, patru, doi.

939
00:43:27,930 --> 00:43:28,680
OK bine.

940
00:43:28,680 --> 00:43:32,310
Acum patru și doi?

941
00:43:32,310 --> 00:43:33,370
Avem nevoie pentru a remedia acest lucru, de asemenea.

942
00:43:33,370 --> 00:43:36,700
Deci una, trei, doi, patru.

943
00:43:36,700 --> 00:43:39,820
Deci este sortat?

944
00:43:39,820 --> 00:43:43,170
Nu, dar este mai aproape de sortate?

945
00:43:43,170 --> 00:43:48,930
>> Este, pentru că am stabilit acest lucru
greșeală, am remediat această greșeală,

946
00:43:48,930 --> 00:43:50,370
și am stabilit această greșeală.

947
00:43:50,370 --> 00:43:52,420
Așa că ne-am fixat trei greșeli, fără îndoială.

948
00:43:52,420 --> 00:43:58,100
Nu arată cu adevărat sortat, dar
aceasta este în mod obiectiv mai aproape de sortat

949
00:43:58,100 --> 00:44:00,080
pentru că ne-am fixat unele dintre aceste greșeli.

950
00:44:00,080 --> 00:44:02,047
>> Acum, ce să fac în continuare?

951
00:44:02,047 --> 00:44:03,630
Am cam ajuns la sfârșitul listei.

952
00:44:03,630 --> 00:44:05,680
Mi se părea că am fixat
toate greșelile, dar nu.

953
00:44:05,680 --> 00:44:08,510
Pentru că în acest caz, unele numere
ar fi barbotat în sus mai aproape

954
00:44:08,510 --> 00:44:10,410
la alte numere care
sunt încă în ordine.

955
00:44:10,410 --> 00:44:12,951
Așa că hai să o facem din nou, și eu voi
doar face acest lucru în loc de data asta.

956
00:44:12,951 --> 00:44:14,170
Unul și trei?

957
00:44:14,170 --> 00:44:14,720
Este bine.

958
00:44:14,720 --> 00:44:16,070
Trei și doi?

959
00:44:16,070 --> 00:44:17,560
Bineînțeles că nu, așa că hai să schimbăm asta.

960
00:44:17,560 --> 00:44:19,160
Deci doi, trei.

961
00:44:19,160 --> 00:44:21,340
Trei și patru?

962
00:44:21,340 --> 00:44:24,370
Si acum sa fie doar
în special pedant aici.

963
00:44:24,370 --> 00:44:26,350
Este sortate?

964
00:44:26,350 --> 00:44:29,280
Voi, oamenii știu că e sortate.

965
00:44:29,280 --> 00:44:30,400
>> Ar trebui să încerc din nou.

966
00:44:30,400 --> 00:44:31,900
Așa că Olivia își propune să încerc din nou.

967
00:44:31,900 --> 00:44:32,530
De ce?

968
00:44:32,530 --> 00:44:35,810
Pentru că un calculator nu are
luxul de ochii noștri umani

969
00:44:35,810 --> 00:44:38,080
de doar uitându-se back-- OK, am terminat.

970
00:44:38,080 --> 00:44:41,610
Cum determină computerul
că lista este acum sortate?

971
00:44:41,610 --> 00:44:44,590
Mechanically.

972
00:44:44,590 --> 00:44:47,650
>> Ar trebui să treacă prin
încă o dată, și numai dacă

973
00:44:47,650 --> 00:44:51,190
nu fac / găsi orice greșeli pot
apoi încheie ca calculator, Yep,

974
00:44:51,190 --> 00:44:51,980
suntem bine să mergem.

975
00:44:51,980 --> 00:44:54,850
Deci, unu și doi, doi
trei, trei și patru.

976
00:44:54,850 --> 00:44:58,030
Acum pot spune definitiv acest lucru este
sortate, pentru că am făcut nici o schimbare.

977
00:44:58,030 --> 00:45:01,940
Acum ar fi un bug și doar
prostie dacă eu, computerul,

978
00:45:01,940 --> 00:45:05,640
a cerut din nou aceste întrebări aceleași
așteptând răspunsuri diferite.

979
00:45:05,640 --> 00:45:07,110
Nu ar trebui să se întâmple.

980
00:45:07,110 --> 00:45:08,600
>> Și așa acum lista este sortată.

981
00:45:08,600 --> 00:45:12,630
Din păcate, timpul de funcționare
acest algoritm este, de asemenea, n la pătrat.

982
00:45:12,630 --> 00:45:13,130
De ce?

983
00:45:13,130 --> 00:45:19,520
Pentru că aveți n numere, și în
cel mai rău caz, trebuie să se mute n numere

984
00:45:19,520 --> 00:45:23,637
n ori mai mult pentru că trebuie să continui
înapoi pentru a verifica și repara potențial

985
00:45:23,637 --> 00:45:24,220
aceste numere.

986
00:45:24,220 --> 00:45:26,280
Si putem face o mai mult
analiză formală, de asemenea.

987
00:45:26,280 --> 00:45:29,530
>> Deci, acest lucru este tot să spunem că ne-am luat
trei abordări diferite, una

988
00:45:29,530 --> 00:45:32,210
dintre ele imediat intuitiv
off BAT de la Ben

989
00:45:32,210 --> 00:45:35,170
la inserare mi-au sugerat
un fel la aceasta

990
00:45:35,170 --> 00:45:38,540
în cazul în care te cam pierde din vedere
pădurea de copaci inițial.

991
00:45:38,540 --> 00:45:41,760
Dar, apoi, dacă luați un pas înapoi,
voila, ne-am stabilit notiunea de sortare.

992
00:45:41,760 --> 00:45:43,824
Deci, aceasta este, îndrăznesc să spun,
un nivel mai scăzut, probabil,

993
00:45:43,824 --> 00:45:45,740
decât unele dintre aceste alte
algoritmi, dar să

994
00:45:45,740 --> 00:45:48,550
a se vedea dacă nu putem vizualiza
acestea prin intermediul acestui.

995
00:45:48,550 --> 00:45:51,450
>> Deci, acest lucru este un frumos
software-ul pe care cineva

996
00:45:51,450 --> 00:45:56,110
a scris folosind bare colorate, care e
O să facă următoarele pentru noi.

997
00:45:56,110 --> 00:45:57,736
Fiecare dintre aceste bare reprezintă un număr.

998
00:45:57,736 --> 00:46:00,026
Bara de mai înalți, cu atât mai mare
numărul, mai mic bar,

999
00:46:00,026 --> 00:46:00,990
este mai mic numărul.

1000
00:46:00,990 --> 00:46:05,880
Așa că în mod ideal, ne dorim o piramidă frumos
în cazul în care începe mici și devine mare,

1001
00:46:05,880 --> 00:46:08,330
și asta ar însemna că
aceste bare sunt sortate.

1002
00:46:08,330 --> 00:46:11,200
Așa că am de gând să merg mai departe și să aleagă,
de exemplu, algoritmul lui Ben

1003
00:46:11,200 --> 00:46:13,990
selecție sortare first--.

1004
00:46:13,990 --> 00:46:16,220
>> Și observați ce face.

1005
00:46:16,220 --> 00:46:18,670
Modul în care au ales să
vizualizează acest algoritm

1006
00:46:18,670 --> 00:46:22,090
este că, la fel ca și cum am fost
mersul pe jos prin lista mea,

1007
00:46:22,090 --> 00:46:24,710
acest program este mersul pe jos
prin lista de numere,

1008
00:46:24,710 --> 00:46:28,160
subliniind în roz fiecare
număr care se uită la.

1009
00:46:28,160 --> 00:46:32,360
Și ce e pe cale să se întâmple chiar acum?

1010
00:46:32,360 --> 00:46:35,154
>> Cel mai mic număr care
I sau Ben găsit pe neașteptate

1011
00:46:35,154 --> 00:46:36,820
devine mutat la începutul listei.

1012
00:46:36,820 --> 00:46:40,037
Și remarcați cu ei a făcut evacua
numărul care a fost acolo,

1013
00:46:40,037 --> 00:46:41,120
și asta e foarte bine.

1014
00:46:41,120 --> 00:46:42,600
N-am intrat în acel nivel de detaliu.

1015
00:46:42,600 --> 00:46:44,308
Dar avem nevoie pentru a pune
acest număr undeva,

1016
00:46:44,308 --> 00:46:47,775
așa că tocmai a fost mutat în
în loc deschis, care a fost creat.

1017
00:46:47,775 --> 00:46:49,900
Așa că voi grăbi
în sus, pentru că în caz contrar

1018
00:46:49,900 --> 00:46:51,871
devine foarte plictisitor repede.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animație speed-- acolo vom merge.

1021
00:46:58,600 --> 00:47:01,850
Deci, acum același principiu
Am fost aplicarea, dar tu

1022
00:47:01,850 --> 00:47:06,540
poate începe să se simtă algoritmul, în cazul în care
va, sau pentru a vedea un pic mai clar.

1023
00:47:06,540 --> 00:47:13,190
Și acest algoritm are ca efect
selectarea elementului următor cel mai mic,

1024
00:47:13,190 --> 00:47:16,422
astfel încât vei începe să
vedea rampa din stânga.

1025
00:47:16,422 --> 00:47:19,130
Și în fiecare iterație, după cum am
a propus, face un pic mai puțin de lucru.

1026
00:47:19,130 --> 00:47:21,921
Aceasta nu trebuie să meargă tot drumul
înapoi la capătul din stânga al listei,

1027
00:47:21,921 --> 00:47:23,900
deoarece deja
îi cunoaște pe cei sunt sortate.

1028
00:47:23,900 --> 00:47:28,129
Deci, este un fel de simt ca este
accelerare, chiar dacă fiecare pas este

1029
00:47:28,129 --> 00:47:29,420
luând aceeași cantitate de timp.

1030
00:47:29,420 --> 00:47:31,600
Există doar mai puțini pași rămași.

1031
00:47:31,600 --> 00:47:35,240
Și acum poți fel de Simt
Algoritmul de curățare până la sfârșitul anului acesta,

1032
00:47:35,240 --> 00:47:37,040
și într-adevăr, acum este sortat.

1033
00:47:37,040 --> 00:47:41,620
>> Așa că inserare de sortare este terminat.

1034
00:47:41,620 --> 00:47:43,600
Trebuie să re-randomiza matrice.

1035
00:47:43,600 --> 00:47:45,940
Si eu pot observa doar
păstrați randomizing-l,

1036
00:47:45,940 --> 00:47:50,630
și vom obține o aproximare a
aceeași abordare, inserare de sortare.

1037
00:47:50,630 --> 00:47:55,050
Lasă-mă să-l încetinească aici.

1038
00:47:55,050 --> 00:47:56,915
Să începem că peste.

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
>> Hai să sari peste patru.

1042
00:48:02,410 --> 00:48:03,200
Acolo mergem.

1043
00:48:03,200 --> 00:48:04,190
Randomiza ei matrice.

1044
00:48:04,190 --> 00:48:05,555
Si aici ne go-- de inserare sortare.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Joaca.

1047
00:48:12,800 --> 00:48:17,280
Observați că se ocupă cu fiecare
elementul întâmpină imediat,

1048
00:48:17,280 --> 00:48:20,282
dar, în cazul în care aparține
anunțul loc greșit

1049
00:48:20,282 --> 00:48:21,740
toată munca pe care trebuie să se întâmple.

1050
00:48:21,740 --> 00:48:24,700
Trebuie să continuăm să redirecționează
și mai multe elemente pentru a face loc

1051
00:48:24,700 --> 00:48:27,340
pentru cel care vrem să pună în aplicare.

1052
00:48:27,340 --> 00:48:30,740
>> Deci, suntem concentrându-se pe
capătul din stânga, numai lista.

1053
00:48:30,740 --> 00:48:34,460
Observati nu ne-am uitat chiar at-- noi
nu s-au evidențiat în nimic roz

1054
00:48:34,460 --> 00:48:35,610
la dreapta.

1055
00:48:35,610 --> 00:48:38,180
Noi doar de-a face cu
problemele pe măsură ce mergem,

1056
00:48:38,180 --> 00:48:40,430
dar vom crea o mulțime de
lucra pentru noi încă.

1057
00:48:40,430 --> 00:48:44,410
Și, așa că, dacă vom grăbi
acum pentru a merge la finalizare,

1058
00:48:44,410 --> 00:48:46,210
ea are un simt diferit de ea, într-adevăr.

1059
00:48:46,210 --> 00:48:50,150
Este doar concentrandu-se pe capătul din stânga, dar
face un pic de lucru mai mult ca needed--

1060
00:48:50,150 --> 00:48:53,230
un fel de lucruri de netezire
peste, lucruri de fixare,

1061
00:48:53,230 --> 00:48:58,350
dar în cele din urmă se ocupă cu
fiecare element de unul la un moment dat

1062
00:48:58,350 --> 00:49:07,740
până când vom ajunge la the-- bine, noi
toate știu cum acest lucru se va termina,

1063
00:49:07,740 --> 00:49:09,700
așa că e un pic SCENARIUL, probabil.

1064
00:49:09,700 --> 00:49:12,830
>> Dar lista din end--
spoiler-- va fi sortate.

1065
00:49:12,830 --> 00:49:15,300
Deci, să ne uităm la o ultimă unul.

1066
00:49:15,300 --> 00:49:16,840
Noi nu putem sări peste acum.

1067
00:49:16,840 --> 00:49:18,000
Suntem aproape acolo.

1068
00:49:18,000 --> 00:49:19,980
Două pentru a merge, unul pentru a merge.

1069
00:49:19,980 --> 00:49:22,680
Și voila.

1070
00:49:22,680 --> 00:49:23,450
Excelent.

1071
00:49:23,450 --> 00:49:27,220
>> Așa că acum hai să facem o ultima,
re-randomizare cu sortare cu bule.

1072
00:49:27,220 --> 00:49:31,690
Și observați aici, mai ales dacă am lent
în jos, acest lucru nu ține picaj prin.

1073
00:49:31,690 --> 00:49:36,830
Dar observați face doar pairwise
un fel de comparisons-- soluții locale.

1074
00:49:36,830 --> 00:49:39,050
Dar, de îndată ce vom ajunge la
la sfârșitul listei în roz,

1075
00:49:39,050 --> 00:49:40,690
ce se va trebui să se întâmple din nou?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Da, va trebui să
începe peste, deoarece numai

1078
00:49:46,830 --> 00:49:49,870
greșeli fixe. pereche

1079
00:49:49,870 --> 00:49:53,120
Si care ar fi dezvăluit încă altele.

1080
00:49:53,120 --> 00:49:58,950
Și, așa că, dacă viteza asta, tu vei
a se vedea că, la fel cum sugerează și numele,

1081
00:49:58,950 --> 00:50:01,870
mai mici elements-- sau, mai degrabă,
cele mai mari sunt elements-- de pornire

1082
00:50:01,870 --> 00:50:03,740
să bule până la partea de sus, dacă vreți.

1083
00:50:03,740 --> 00:50:07,380
Și elementele sunt mai mici
încep să bule în jos spre stânga.

1084
00:50:07,380 --> 00:50:10,780
Și într-adevăr, asta e un fel de
efectul vizual, de asemenea.

1085
00:50:10,780 --> 00:50:17,150
Și, astfel încât aceasta va încheia finisare
într-un mod foarte asemănător, de asemenea.

1086
00:50:17,150 --> 00:50:19,160
>> Noi nu trebuie să locuiască
pe aceasta anume.

1087
00:50:19,160 --> 00:50:21,010
Lasă-mă să deschid acest lucru acum, de asemenea.

1088
00:50:21,010 --> 00:50:24,040
Există o sortare alți câțiva algorithms
în lume, unele dintre ele

1089
00:50:24,040 --> 00:50:25,580
sunt capturate aici.

1090
00:50:25,580 --> 00:50:29,960
Și, mai ales pentru cei care învață, care nu sunt
în mod necesar vizual sau matematic,

1091
00:50:29,960 --> 00:50:31,930
așa cum am făcut-o mai înainte, putem
De asemenea, face acest lucru audially

1092
00:50:31,930 --> 00:50:34,210
dacă vom asocia un sunet cu asta.

1093
00:50:34,210 --> 00:50:36,990
Și doar pentru distracție, aici este o
câțiva algoritmi diferiți,

1094
00:50:36,990 --> 00:50:40,950
și unul dintre ei, în special, sunteți
O să observați se numește "îmbinare sortare."

1095
00:50:40,950 --> 00:50:43,250
>> Este de fapt un mod fundamental
mai bine algoritm,

1096
00:50:43,250 --> 00:50:45,860
astfel încât îmbinare un fel, unul dintre
cele pe care le vei vedea,

1097
00:50:45,860 --> 00:50:49,170
nu este ordinea de n la pătrat.

1098
00:50:49,170 --> 00:50:57,280
Este pe ordinea de n ori log de
n, care este de fapt mai mică și, prin urmare,

1099
00:50:57,280 --> 00:50:58,940
mai repede decât cele trei alte.

1100
00:50:58,940 --> 00:51:00,670
Și există un alt cuplu
cele stupide pe care le vom vedea.

1101
00:51:00,670 --> 00:51:01,933
>> Deci, aici vom merge cu un sunet.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Acesta este un fel de inserție, deci din nou
este doar de-a face cu elementele

1104
00:51:10,490 --> 00:51:13,420
așa cum au venit.

1105
00:51:13,420 --> 00:51:17,180
Acesta este un fel cu bule, deci este
considerându-le perechi la un moment dat.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Și din nou, cele mai mari elemente
sunt barbotare până la partea de sus.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Următorul selecție sortare.

1110
00:51:41,710 --> 00:51:45,420
Acesta este algoritmul lui Ben, unde
din nou, el selectând iterativ

1111
00:51:45,420 --> 00:51:46,843
următorul mai mic element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Și din nou, acum poți auzi cu adevărat că
este accelerarea, dar numai în măsura în care

1114
00:51:53,900 --> 00:51:58,230
deoarece face mai puțin și mai puțin
lucrează la fiecare iterație.

1115
00:51:58,230 --> 00:52:04,170
Acesta este cel mai rapid unul, îmbinare sortare,
care este sortarea grupuri de numere

1116
00:52:04,170 --> 00:52:05,971
împreună și apoi combinarea lor.

1117
00:52:05,971 --> 00:52:07,720
Așa că look-- la stânga
jumătate este deja sortat.

1118
00:52:07,720 --> 00:52:14,165
>> Acum este sortarea jumătatea din dreapta, și
acum o să le combine într-una singură.

1119
00:52:14,165 --> 00:52:19,160
Acest lucru este ceva numit "Gnom un fel."

1120
00:52:19,160 --> 00:52:23,460
Și tu poți fel de a vedea că
se merge înainte și înapoi,

1121
00:52:23,460 --> 00:52:27,950
de stabilire de muncă un pic aici și
acolo înainte de a trece la noua lucrare.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Si asta e.

1124
00:52:33,692 --> 00:52:36,400
Există un alt soi, care este
într-adevăr doar pentru scopuri academice,

1125
00:52:36,400 --> 00:52:40,980
numit "un fel de prost", care ia
datele, sortează la întâmplare,

1126
00:52:40,980 --> 00:52:43,350
și apoi verifică dacă este sortat.

1127
00:52:43,350 --> 00:52:47,880
Și dacă nu este, se re-sorteaza-l
la întâmplare, verifică dacă este sortat,

1128
00:52:47,880 --> 00:52:49,440
și în cazul în care nu se repetă.

1129
00:52:49,440 --> 00:52:52,660
Și, în teorie, probabilist
acest lucru se va finaliza,

1130
00:52:52,660 --> 00:52:54,140
dar după destul de un pic de timp.

1131
00:52:54,140 --> 00:52:56,930
Nu e cel mai mult
eficientă a algoritmilor.

1132
00:52:56,930 --> 00:53:02,550
Astfel încât orice întrebări cu privire la acele
algoritmi speciale sau orice

1133
00:53:02,550 --> 00:53:04,720
legate de acolo, de asemenea?

1134
00:53:04,720 --> 00:53:09,430
>> Ei bine, hai acum tachineze in afara ce toate
aceste linii sunt că am fost de desen

1135
00:53:09,430 --> 00:53:15,090
și ceea ce eu sunt presupunând computerul
se poate face sub capota.

1136
00:53:15,090 --> 00:53:18,650
Aș argumenta că toate aceste numere
Am păstra drawing-- care au nevoie pentru a obține

1137
00:53:18,650 --> 00:53:21,330
stocat undeva în memorie.

1138
00:53:21,330 --> 00:53:24,130
O să scăpăm de tipul ăsta acum, de asemenea.

1139
00:53:24,130 --> 00:53:30,110
>> Deci, o bucată de memorie într-un
computer-- astfel încât RAM DIMM este

1140
00:53:30,110 --> 00:53:35,480
ceea ce am căutat ieri, cu dublă
inline memory module-- arata ca acest lucru.

1141
00:53:35,480 --> 00:53:39,370
Și fiecare dintre aceste chip-uri mici negre
este un număr de octeți, în mod tipic.

1142
00:53:39,370 --> 00:53:44,380
Și apoi pinii de aur sunt ca
fire care se conectează la calculator,

1143
00:53:44,380 --> 00:53:47,521
iar placa de siliciu verde este doar
ceea ce ține totul împreună.

1144
00:53:47,521 --> 00:53:48,770
Deci, ce înseamnă cu adevărat?

1145
00:53:48,770 --> 00:53:53,180
Dacă aș fi un fel de remiză aceeași imagine,
Să presupunem, pentru simplitate

1146
00:53:53,180 --> 00:53:55,280
că acest DIMM, dublă
modul de memorie în linie,

1147
00:53:55,280 --> 00:54:00,530
este un gigabyte de memorie RAM, o gigabyte de
de memorie, care este cât de mulți octeți totală?

1148
00:54:00,530 --> 00:54:02,100
Gigaoctet este cât de mulți octeți?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Mai mult decat atat.

1151
00:54:06,030 --> 00:54:09,960
1124 este kilogram, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega este milioane.

1153
00:54:11,730 --> 00:54:14,570
Giga este un miliard.

1154
00:54:14,570 --> 00:54:15,070
>> Sunt eu mint?

1155
00:54:15,070 --> 00:54:16,670
Putem citi chiar eticheta?

1156
00:54:16,670 --> 00:54:19,920
Aceasta este de fapt 128
gigaocteți, deci este mai mult.

1157
00:54:19,920 --> 00:54:22,130
Dar ne vom prefacem că
este doar un gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Deci asta înseamnă că există un miliard
octeți de memorie disponibile pentru mine

1159
00:54:25,640 --> 00:54:29,770
sau 8 miliarde de biți, dar vom
pentru a vorbi în termeni de octeți acum,

1160
00:54:29,770 --> 00:54:30,750
a merge inainte.

1161
00:54:30,750 --> 00:54:36,330
>> Deci, ceea ce înseamnă că este acest lucru este
un octet, acesta este un alt octet,

1162
00:54:36,330 --> 00:54:38,680
acesta este un alt octet,
și dacă ne-am dorit cu adevărat

1163
00:54:38,680 --> 00:54:43,280
să fie specifice ne-ar trebui să
trage un miliard de mici pătrate.

1164
00:54:43,280 --> 00:54:44,320
Dar ce înseamnă asta?

1165
00:54:44,320 --> 00:54:46,420
Ei bine, lasă-mă doar zoom
în? Pe aceasta imagine.

1166
00:54:46,420 --> 00:54:50,900
Dacă am ceva care arată
ca acest lucru acum, asta e patru octeți.

1167
00:54:50,900 --> 00:54:53,710
>> Și așa am putut pune patru numere aici.

1168
00:54:53,710 --> 00:54:54,990
Unu doi trei patru.

1169
00:54:54,990 --> 00:55:00,170
Sau aș putea pune patru litere sau simboluri.

1170
00:55:00,170 --> 00:55:02,620
"Hei!" ar putea merge chiar acolo,
pentru că fiecare dintre litere,

1171
00:55:02,620 --> 00:55:04,370
am discutat mai devreme,
poate fi reprezentat

1172
00:55:04,370 --> 00:55:06,650
cu opt biți sau ASCII sau de un octet.

1173
00:55:06,650 --> 00:55:09,370
Deci, cu alte cuvinte, poți
a pus 8 miliarde de lucruri în interiorul

1174
00:55:09,370 --> 00:55:11,137
din aceasta stick de memorie.

1175
00:55:11,137 --> 00:55:14,345
Acum, ce înseamnă a pune lucrurile înapoi
to back to back în memorie ca asta?

1176
00:55:14,345 --> 00:55:17,330
Aceasta este ceea ce un programator
ar numi o "matrice".

1177
00:55:17,330 --> 00:55:21,250
Într-un program de calculator, nu crezi
despre hardware-ul de bază, per se.

1178
00:55:21,250 --> 00:55:24,427
Tocmai ai gândi la tine ca având
acces la un total de miliard de bytes,

1179
00:55:24,427 --> 00:55:26,010
și poți tot ce vrei cu ea.

1180
00:55:26,010 --> 00:55:27,880
Dar, pentru comoditate
este în general util

1181
00:55:27,880 --> 00:55:31,202
pentru a păstra dreptul de memorie
unul lângă altul ca asta.

1182
00:55:31,202 --> 00:55:33,660
Deci, dacă am zoom pe astea--
pentru că cu siguranță nu vom

1183
00:55:33,660 --> 00:55:39,310
să atragă un miliard de mici squares--
Să presupunem că acest consiliu reprezintă

1184
00:55:39,310 --> 00:55:40,610
care se lipesc de memorie acum.

1185
00:55:40,610 --> 00:55:43,800
Și eu voi trage la fel de multe ca meu
marcator sfârșește prin a da-mi aici.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Așa că acum avem un băț
de memorie de pe placa

1188
00:55:52,300 --> 00:55:56,400
că are unul, doi, trei, patru, cinci,
șase, unu, doi, trei, patru, cinci, șase,

1189
00:55:56,400 --> 00:56:01,130
seven-- astfel încât 42 octeți
memorie pe total ecran.

1190
00:56:01,130 --> 00:56:01,630
Mulțumesc.

1191
00:56:01,630 --> 00:56:02,838
Da, a făcut aritmetica mea dreapta.

1192
00:56:02,838 --> 00:56:05,120
Deci 42 bytes de memorie.

1193
00:56:05,120 --> 00:56:06,660
Deci, ce înseamnă de fapt?

1194
00:56:06,660 --> 00:56:09,830
Ei bine, un programator de calculator
ar fi, de fapt, în general,

1195
00:56:09,830 --> 00:56:12,450
cred că de această memorie ca adresabile.

1196
00:56:12,450 --> 00:56:16,630
Cu alte cuvinte, fiecare dintre acestea
locații în memorie, în hardware,

1197
00:56:16,630 --> 00:56:18,030
are o adresă unică.

1198
00:56:18,030 --> 00:56:22,020
>> Nu este la fel de complex ca un Brattle
Pătrat, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
În schimb, este doar un număr.

1200
00:56:23,830 --> 00:56:27,930
Acesta este numărul de octeți zero, acest lucru este
unul, aceasta este de două, acest lucru este de trei,

1201
00:56:27,930 --> 00:56:30,327
iar acest lucru este de 41.

1202
00:56:30,327 --> 00:56:30,910
Așteptaţi un minut.

1203
00:56:30,910 --> 00:56:32,510
Am crezut că am spus 42 un moment în urmă.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Am început de numărare la zero,
astfel încât este de fapt corect.

1206
00:56:37,772 --> 00:56:40,980
Acum, noi nu trebuie să-l atragă de fapt
ca o grilă, iar dacă îl trage ca grilă

1207
00:56:40,980 --> 00:56:43,520
Cred că de fapt lucrurile
obține un pic înșelătoare.

1208
00:56:43,520 --> 00:56:46,650
Ce un programator ar fi,
în propria mintea lui sau ei,

1209
00:56:46,650 --> 00:56:50,310
în general, cred că de acest lucru
memorie este la fel ca o bandă,

1210
00:56:50,310 --> 00:56:53,340
ca o bucată de bandă de mascare
că doar merge mai departe și pentru totdeauna

1211
00:56:53,340 --> 00:56:54,980
sau până când a alerga afară de memorie.

1212
00:56:54,980 --> 00:56:59,200
Deci, un mod mai comun de a desena
Gândiți-vă doar despre memorie

1213
00:56:59,200 --> 00:57:03,710
ar fi că acest lucru este octet zero, unu,
doi, trei, și apoi punct, punct, punct.

1214
00:57:03,710 --> 00:57:07,650
Și tu ai 42 de astfel de bytes totală, chiar
deși fizic s-ar putea de fapt

1215
00:57:07,650 --> 00:57:09,480
să fie ceva mai mult ca acest lucru.

1216
00:57:09,480 --> 00:57:12,850
>> Așa că, dacă te gândești acum al tău
memorie ca acest lucru, la fel ca și o bandă,

1217
00:57:12,850 --> 00:57:17,640
aceasta este ceea ce un programator din nou
ar numi o serie de memorie.

1218
00:57:17,640 --> 00:57:20,660
Iar atunci când doriți să stocați de fapt,
ceva în memoria unui calculator,

1219
00:57:20,660 --> 00:57:23,290
ai face, în general, magazin lucruri
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Așa că am vorbit despre numere.

1221
00:57:25,010 --> 00:57:30,880
Iar când am vrut să rezolve problemele
cum ar fi patru, unul, trei, doi,

1222
00:57:30,880 --> 00:57:33,820
chiar dacă am fost doar desen
numai patru numere, una, trei,

1223
00:57:33,820 --> 00:57:39,490
două pe bord, computerul ar
au într-adevăr această configurare în memorie.

1224
00:57:39,490 --> 00:57:43,347
>> Și ce ar fi lângă opțiunea
două în memoria calculatorului?

1225
00:57:43,347 --> 00:57:44,680
Ei bine, nu există nici un răspuns la asta.

1226
00:57:44,680 --> 00:57:45,770
Noi nu știm cu adevărat.

1227
00:57:45,770 --> 00:57:48,200
Și, atâta vreme cât
computerul nu are nevoie de ea,

1228
00:57:48,200 --> 00:57:51,440
nu trebuie să aibă grijă de ceea ce este urmatorul
la numerele de face pasa.

1229
00:57:51,440 --> 00:57:55,130
Iar când am spus mai devreme că un calculator
se pot uita doar la o singură adresă la un moment dat,

1230
00:57:55,130 --> 00:57:56,170
acest lucru este un fel de ce.

1231
00:57:56,170 --> 00:57:59,490
>> Nu spre deosebire de un record
player și un cap de citire

1232
00:57:59,490 --> 00:58:03,030
doar să fii capabil să se uite la un anumit
canelură într-un record de școală veche fizică

1233
00:58:03,030 --> 00:58:06,500
la un moment dat, în mod similar
poate un calculator multumesc

1234
00:58:06,500 --> 00:58:09,810
CPU și ei
set de instrucțiuni Intel,

1235
00:58:09,810 --> 00:58:12,480
printre ale căror instruire
se citește din memorie

1236
00:58:12,480 --> 00:58:15,590
sau pentru a salva o memory--
computer poate privi doar

1237
00:58:15,590 --> 00:58:19,210
la o locație la time--
uneori o combinație a acestora,

1238
00:58:19,210 --> 00:58:21,770
dar într-adevăr doar o singură locație la un moment dat.

1239
00:58:21,770 --> 00:58:24,770
Așa că, atunci când făceam
acești diverși algoritmi,

1240
00:58:24,770 --> 00:58:28,110
Nu am scris doar într-un
vacuum-- patru, unul, trei, doi.

1241
00:58:28,110 --> 00:58:30,849
Aceste numere aparțin de fapt
undeva fizic în memorie.

1242
00:58:30,849 --> 00:58:32,890
Prin urmare, există minuscul
tranzistori sau un fel

1243
00:58:32,890 --> 00:58:35,840
de electronice de sub
hota stocarea acestor valori.

1244
00:58:35,840 --> 00:58:40,460
>> Și, în total, câți biți sunt
implicat chiar acum, trebuie doar să fie clar?

1245
00:58:40,460 --> 00:58:45,580
Deci, acest lucru este de patru octeți, sau
acum este de 32 de biți totală.

1246
00:58:45,580 --> 00:58:49,280
Prin urmare, există de fapt 32 de zerouri,
cei care compun aceste patru lucruri.

1247
00:58:49,280 --> 00:58:52,070
Există chiar și mai mult aici, dar
din nou, nu ne pasă de asta.

1248
00:58:52,070 --> 00:58:55,120
>> Așa că acum să ceară un alt
întrebare folosind memorie,

1249
00:58:55,120 --> 00:58:57,519
pentru că la sfârșitul anului
a zilei este în dezacord.

1250
00:58:57,519 --> 00:59:00,310
Nu contează ce am putea face cu
computerul, la sfârșitul zilei

1251
00:59:00,310 --> 00:59:02,560
hardware-ul este încă
aceeași sub capota.

1252
00:59:02,560 --> 00:59:04,670
Cum aș păstra un cuvânt aici?

1253
00:59:04,670 --> 00:59:09,710
Ei bine, un cuvânt într-un calculator cum ar fi
"Hei!" ar fi stocate la fel ca asta.

1254
00:59:09,710 --> 00:59:12,300
Și, dacă ai vrut o mai
cuvânt, puteți pur și simplu

1255
00:59:12,300 --> 00:59:19,120
suprascrie acest lucru și spune ceva
cum ar fi "Bună ziua" și magazin care aici.

1256
00:59:19,120 --> 00:59:23,930
>> Și așa aici, de asemenea, această contiguousness
este de fapt un avantaj,

1257
00:59:23,930 --> 00:59:26,530
pentru că un calculator poate doar
citit de la dreapta la stânga.

1258
00:59:26,530 --> 00:59:28,680
Dar iată o întrebare.

1259
00:59:28,680 --> 00:59:33,480
În contextul acestui cuvânt,
h-e-l-l-O, punctul de exclamare,

1260
00:59:33,480 --> 00:59:38,740
cum s-ar putea computerul știe unde
cuvânt începe și unde se termină cuvântul?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
În cadrul numerelor,
cum face computerul

1263
00:59:43,800 --> 00:59:48,396
știu cât timp secvența
Numerele este sau în cazul în care acesta începe?

1264
00:59:48,396 --> 00:59:50,270
Ei bine, se pare out--
și nu vom merge prea mult

1265
00:59:50,270 --> 00:59:54,970
în acest nivel de detail--
computerele muta lucrurile în jurul valorii în memorie

1266
00:59:54,970 --> 00:59:57,800
literalmente prin intermediul acestor adrese.

1267
00:59:57,800 --> 01:00:02,080
Deci, într-un calculator, dacă sunteți
scrierea de cod pentru a stoca lucruri

1268
01:00:02,080 --> 01:00:05,800
cum ar fi cuvinte, ceea ce ești
într-adevăr faci este tastarea

1269
01:00:05,800 --> 01:00:11,320
expresii care amintesc în cazul în care, în
memoria calculatorului aceste cuvinte sunt.

1270
01:00:11,320 --> 01:00:14,370
Așa că lasă-mă să fac un foarte,
exemplu foarte simplu.

1271
01:00:14,370 --> 01:00:18,260
>> Mă duc să merg mai departe și
deschide un program de text simplu,

1272
01:00:18,260 --> 01:00:20,330
și voi crea
un fișier numit hello.c.

1273
01:00:20,330 --> 01:00:22,849
Cele mai multe dintre aceste informații noi
nu va intra în în detaliu,

1274
01:00:22,849 --> 01:00:25,140
dar am de gând să scrie
program, în aceeași limbă,

1275
01:00:25,140 --> 01:00:31,140
C. Acest lucru este mult mai intimidant,
Aș argumenta, decât zero,

1276
01:00:31,140 --> 01:00:32,490
dar este foarte similar în spirit.

1277
01:00:32,490 --> 01:00:34,364
De fapt, aceste creț
braces-- poți fel de

1278
01:00:34,364 --> 01:00:37,820
cred că de ce am făcut ca acest lucru.

1279
01:00:37,820 --> 01:00:39,240
>> Hai să facem asta, de fapt.

1280
01:00:39,240 --> 01:00:45,100
Atunci când steagul verde face clic,
procedați în felul următor.

1281
01:00:45,100 --> 01:00:50,210
Vreau să imprime "salut".

1282
01:00:50,210 --> 01:00:51,500
Deci, acest lucru este acum pseudocode.

1283
01:00:51,500 --> 01:00:53,000
Sunt un fel de estomparea liniilor.

1284
01:00:53,000 --> 01:00:56,750
În C, această limbă vorbesc
despre, această linie de imprimare salut

1285
01:00:56,750 --> 01:01:01,940
devine de fapt "printf" cu
unele paranteze și un semi-colon.

1286
01:01:01,940 --> 01:01:03,480
>> Dar e aceeași idee exactă.

1287
01:01:03,480 --> 01:01:06,730
Și acest lucru foarte user-friendly
"Când steagul verde a făcut clic" devine

1288
01:01:06,730 --> 01:01:10,182
mult mai arcana "void main int."

1289
01:01:10,182 --> 01:01:12,890
Și acest lucru are într-adevăr nici o mapare,
așa că doar o să ignore asta.

1290
01:01:12,890 --> 01:01:17,210
Dar, acolade sunt ca
piese de puzzle curbate, cum ar fi acest lucru.

1291
01:01:17,210 --> 01:01:18,700
>> Așa că poți fel de ghici.

1292
01:01:18,700 --> 01:01:22,357
Chiar dacă nu ați programat mai înainte,
ce face acest program, probabil, nu?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Probabil tipărește salut
cu un punct de exclamare.

1295
01:01:28,000 --> 01:01:29,150
>> Așa că hai să încercăm.

1296
01:01:29,150 --> 01:01:30,800
Mă duc să-l salvez.

1297
01:01:30,800 --> 01:01:34,000
Și acest lucru este, din nou, o foarte
mediul școlar vechi.

1298
01:01:34,000 --> 01:01:35,420
Nu pot să faceți clic, nu pot trage.

1299
01:01:35,420 --> 01:01:36,910
Trebuie să tastați comenzi.

1300
01:01:36,910 --> 01:01:41,320
Așa că vreau să rulați programul meu, asa
S-ar putea face acest lucru, cum ar fi hello.c.

1301
01:01:41,320 --> 01:01:42,292
Asta e fișierul am fugit.

1302
01:01:42,292 --> 01:01:43,500
Dar stai, îmi lipsește un pas.

1303
01:01:43,500 --> 01:01:46,470
Ce am spus este o condiție necesară
pas pentru o limbă ca C?

1304
01:01:46,470 --> 01:01:49,470
Tocmai am scris sursa
cod, dar ce am nevoie?

1305
01:01:49,470 --> 01:01:50,670
Da, am nevoie de un compilator.

1306
01:01:50,670 --> 01:01:57,670
Deci, pe Mac-ul meu aici, am o
program numit CCG, GNU C compilator,

1307
01:01:57,670 --> 01:02:03,990
ceea ce-mi permite să fac asta-- rândul său,
codul meu sursă în, îl vom numi,

1308
01:02:03,990 --> 01:02:04,930
cod mașină.

1309
01:02:04,930 --> 01:02:10,180
>> Și eu pot vedea că,
din nou, după cum urmează, acestea

1310
01:02:10,180 --> 01:02:14,090
sunt zerouri și cele am doar
create din codul meu sursă,

1311
01:02:14,090 --> 01:02:15,730
toate zerouri și cele.

1312
01:02:15,730 --> 01:02:17,770
Și, dacă vreau să curgă
meu program-- se întâmplă

1313
01:02:17,770 --> 01:02:23,010
să fie numit a.out pentru
reasons-- istoric "salut".

1314
01:02:23,010 --> 01:02:24,070
Pot să-l rula din nou.

1315
01:02:24,070 --> 01:02:25,690
Salut salut salut.

1316
01:02:25,690 --> 01:02:27,430
Și se pare a fi de lucru.

1317
01:02:27,430 --> 01:02:31,000
>> Dar asta înseamnă undeva în meu
memoriei calculatorului sunt cuvintele

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-O, punctul de exclamare.

1319
01:02:35,279 --> 01:02:38,070
Și se pare că, la fel ca și o parte,
ce un calculator ar fi în mod tipic

1320
01:02:38,070 --> 01:02:40,550
face astfel încât să știe unde
lucrurile vor începe și end-- este

1321
01:02:40,550 --> 01:02:42,460
va pune un simbol special aici.

1322
01:02:42,460 --> 01:02:46,064
Iar convenția este de a pune
numărul zero la sfârșitul unui cuvânt

1323
01:02:46,064 --> 01:02:48,230
astfel încât să știi unde
de fapt, se termină, astfel încât să

1324
01:02:48,230 --> 01:02:52,750
nu păstrați imprimarea mai mult
caractere decât cele pe care de fapt intenționați.

1325
01:02:52,750 --> 01:02:55,400
>> Dar aici takeaway, chiar
deși acest lucru este destul de obscură,

1326
01:02:55,400 --> 01:02:58,140
este că este în cele din urmă
relativ simplu.

1327
01:02:58,140 --> 01:03:04,550
Ai fost dat un fel de bandă, un gol
spațiu pe care le puteți scrie scrisori.

1328
01:03:04,550 --> 01:03:07,150
Pur și simplu trebuie să aibă un
simbol special, cum ar fi în mod arbitrar

1329
01:03:07,150 --> 01:03:10,316
numărul de zero, pentru a pune la sfârșitul anului
cuvintele tale, astfel încât computerul să știe,

1330
01:03:10,316 --> 01:03:13,410
oh, ar trebui să se oprească după imprimare
Eu văd punctul de exclamare.

1331
01:03:13,410 --> 01:03:16,090
Pentru că următorul lucru pe acolo
este o valoare ASCII de la zero,

1332
01:03:16,090 --> 01:03:19,125
sau caracterul nul ca
cineva ar suna.

1333
01:03:19,125 --> 01:03:21,500
Dar există un fel de problemă
aici, și să revină înapoi

1334
01:03:21,500 --> 01:03:23,320
la numere pentru un moment.

1335
01:03:23,320 --> 01:03:28,720
Să presupunem că eu fac, de fapt,
au o serie de numere,

1336
01:03:28,720 --> 01:03:30,730
și presupunem că
Programul am scris este

1337
01:03:30,730 --> 01:03:34,680
ca o carte de grad pentru un profesor
și o clasă.

1338
01:03:34,680 --> 01:03:38,720
Iar acest program permite el sau ea
pentru a introduce în scorurile elevilor lor

1339
01:03:38,720 --> 01:03:39,960
pe chestionare.

1340
01:03:39,960 --> 01:03:43,750
Și să presupunem că studentul devine
100, pe primul lor test, poate

1341
01:03:43,750 --> 01:03:49,920
ca un 80 pe următoarea, apoi
75, apoi 90 la al patrulea test.

1342
01:03:49,920 --> 01:03:54,150
>> Astfel încât în ​​acest moment în poveste,
matrice este de marimea patru.

1343
01:03:54,150 --> 01:03:58,470
Nu există absolut mai mult de memorie în
calculator, dar matrice, ca să spunem așa,

1344
01:03:58,470 --> 01:04:00,350
este de mărime patru.

1345
01:04:00,350 --> 01:04:06,060
Să presupunem acum că profesorul dorește
pentru a atribui un al cincilea test la clasa.

1346
01:04:06,060 --> 01:04:08,510
Ei bine, unul dintre lucrurile pe care el
sau ea va trebui să facă

1347
01:04:08,510 --> 01:04:10,650
este stoca o valoare suplimentară aici.

1348
01:04:10,650 --> 01:04:15,490
Dar, în cazul în care matrice profesorul are
creat în acest program este de dimensiune pentru,

1349
01:04:15,490 --> 01:04:22,440
una dintre problema cu o matrice este că
nu se poate păstra doar adăugarea la memorie.

1350
01:04:22,440 --> 01:04:26,470
Pentru că ce se întâmplă dacă o altă parte a
Programul are cuvântul "hei" chiar acolo?

1351
01:04:26,470 --> 01:04:29,650
>> Cu alte cuvinte, memoria mea poate fi
utilizat pentru orice într-un program.

1352
01:04:29,650 --> 01:04:33,250
Și dacă în prealabil am tastat, hei,
Vreau să introducă patru scoruri test,

1353
01:04:33,250 --> 01:04:34,784
ei s-ar putea merge aici și aici.

1354
01:04:34,784 --> 01:04:37,700
Și dacă vă schimbați brusc mintea ta
mai târziu și spun că doresc un al cincilea test

1355
01:04:37,700 --> 01:04:40,872
scor, nu poți
pune-l oriunde doriți,

1356
01:04:40,872 --> 01:04:42,580
pentru că ceea ce în cazul în care acest lucru
memorie este utilizat

1357
01:04:42,580 --> 01:04:45,990
pentru ceva else-- un alt program
sau o altă caracteristică a programului

1358
01:04:45,990 --> 01:04:46,910
că difuzați?

1359
01:04:46,910 --> 01:04:50,650
Deci, va trebui să se gândească în avans
modul în care doriți să stocați datele,

1360
01:04:50,650 --> 01:04:54,480
pentru că acum ai pictat
te într-un colț digital.

1361
01:04:54,480 --> 01:04:57,280
>> Deci, un profesor poate în schimb
spune atunci când scrieți un program de

1362
01:04:57,280 --> 01:04:59,360
pentru a stoca sale
clase, știi ce?

1363
01:04:59,360 --> 01:05:04,180
Am de gând să solicite,
atunci când scrieți programul meu,

1364
01:05:04,180 --> 01:05:12,070
că vreau zero, unu, doi, trei,
patru, cinci, șase, opt clase în total.

1365
01:05:12,070 --> 01:05:15,320
Deci unul, doi, trei, patru,
cinci, șase, șapte, opt.

1366
01:05:15,320 --> 01:05:18,612
Profesorul poate doar peste aloca
memorie atunci când scrieți programul său

1367
01:05:18,612 --> 01:05:19,570
și spune, știi ce?

1368
01:05:19,570 --> 01:05:22,236
Nu voi să alocați mai mult
mult de opt teste într-un semestru.

1369
01:05:22,236 --> 01:05:23,130
Asta e doar o nebunie.

1370
01:05:23,130 --> 01:05:24,470
Nu voi aloca asta.

1371
01:05:24,470 --> 01:05:28,270
Astfel că în acest fel el sau ea are
flexibilitate la scoruri magazin de student,

1372
01:05:28,270 --> 01:05:33,010
cum ar fi 75, 90, și poate unul suplimentar în cazul în care
studentul a primit credite în plus, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Dar, dacă profesorul nu
utilizează aceste trei spații,

1374
01:05:36,130 --> 01:05:38,860
există un takeaway intuitiv aici.

1375
01:05:38,860 --> 01:05:41,410
El sau ea este pur și simplu pierdem spațiu.

1376
01:05:41,410 --> 01:05:44,790
Deci, cu alte cuvinte, există această
tradeoff comună în programare

1377
01:05:44,790 --> 01:05:48,241
în cazul în care puteți fie aloca
exact la fel de mult de memorie așa cum doriți,

1378
01:05:48,241 --> 01:05:51,490
în sensul creșterii din care este că ești super-
efficient-- nu ești risipitor

1379
01:05:51,490 --> 01:05:54,640
la all--, dar dezavantajul care
este ce se întâmplă dacă vă schimbați mintea atunci când

1380
01:05:54,640 --> 01:05:58,780
folosind programul pe care doriți să stocați
mai multe date decât ați intenționat inițial.

1381
01:05:58,780 --> 01:06:03,030
>> Deci, poate soluția este, atunci,
scrie programe în așa fel

1382
01:06:03,030 --> 01:06:05,605
pe care le utilizează mai multă memorie
decât au de fapt nevoie.

1383
01:06:05,605 --> 01:06:07,730
In acest fel nu vei
pentru a rula în această problemă,

1384
01:06:07,730 --> 01:06:09,730
dar tu ești risipitor.

1385
01:06:09,730 --> 01:06:12,960
Și mai multă memorie de program utilizează,
așa cum am discutat ieri, cu atât mai puțin

1386
01:06:12,960 --> 01:06:15,410
memorie care este disponibil
pentru alte programe,

1387
01:06:15,410 --> 01:06:18,790
cu atât mai repede calculatorul poate încetini
jos, din cauza memoriei virtuale.

1388
01:06:18,790 --> 01:06:22,670
Și astfel, soluția ideală ar putea fi ceea ce?

1389
01:06:22,670 --> 01:06:24,610
>> Sub-pare rău Alocarea.

1390
01:06:24,610 --> 01:06:27,030
Supraevaluare pare rău.

1391
01:06:27,030 --> 01:06:31,120
Deci, ce ar putea fi o soluție mai bună?

1392
01:06:31,120 --> 01:06:32,390
Realocării.

1393
01:06:32,390 --> 01:06:33,590
Fii mai dinamic.

1394
01:06:33,590 --> 01:06:37,520
Nu te forta pentru a alege un
a priori, la început, ceea ce vrei.

1395
01:06:37,520 --> 01:06:41,370
Și, cu siguranță, nu supra-alocarea,
ca nu cumva să fie risipitor.

1396
01:06:41,370 --> 01:06:45,770
>> Și astfel, pentru a atinge acest obiectiv,
Trebuie să arunce această structură de date,

1397
01:06:45,770 --> 01:06:48,100
ca să spunem așa, departe.

1398
01:06:48,100 --> 01:06:51,080
Și ce un programator
se va folosi în mod tipic

1399
01:06:51,080 --> 01:06:55,940
nu este un numit ceva
matrice ci o listă legată.

1400
01:06:55,940 --> 01:07:00,860
Cu alte cuvinte, el sau ea va
începe să se gândească la memoria lor

1401
01:07:00,860 --> 01:07:05,280
ca fiind un fel de formă pe care le
se pot desena în felul următor.

1402
01:07:05,280 --> 01:07:08,520
Dacă vreau să stocați un singur număr în
un program-- deci este septembrie

1403
01:07:08,520 --> 01:07:12,600
I-am dat elevilor mei un test; eu vreau
pentru a stoca primul test al studenților,

1404
01:07:12,600 --> 01:07:16,220
și au primit 100 pe I it--
am de gând să ceară calculatorul meu,

1405
01:07:16,220 --> 01:07:19,540
prin intermediul programului I-am
în scris, pentru o bucată de memorie.

1406
01:07:19,540 --> 01:07:22,570
Si voi pentru a stoca
100 în el number, și asta este.

1407
01:07:22,570 --> 01:07:24,820
>> Apoi, câteva săptămâni mai târziu
când am obține al doilea test meu,

1408
01:07:24,820 --> 01:07:27,890
și este timpul să tastați
în 90%, voi

1409
01:07:27,890 --> 01:07:32,129
pentru a cere computerul, hei, calculator,
pot avea o altă bucată de memorie?

1410
01:07:32,129 --> 01:07:34,170
O să-mi dau asta
bucată goală de memorie.

1411
01:07:34,170 --> 01:07:39,370
Mă duc să pun în numărul 90,
dar în programul meu într-un fel sau other--

1412
01:07:39,370 --> 01:07:42,100
și nu vom face griji cu privire la
sintaxa pentru astea-- am nevoie

1413
01:07:42,100 --> 01:07:44,430
cumva să înlănțui aceste lucruri împreună.

1414
01:07:44,430 --> 01:07:47,430
Și eu voi le lega împreună cu
ceea ce arata ca o săgeată aici.

1415
01:07:47,430 --> 01:07:50,050
>> Al treilea test care vine în sus,
Am de gând să spun, hei, calculator,

1416
01:07:50,050 --> 01:07:51,680
da-mi o altă bucată de memorie.

1417
01:07:51,680 --> 01:07:54,660
Și voi pune în jos
orice ar fi fost, cum ar fi 75,

1418
01:07:54,660 --> 01:07:56,920
și am să lanț de această
împreună acum într-un fel.

1419
01:07:56,920 --> 01:08:00,290
În al patrulea rând test vine de-a lungul, și poate
că e spre sfârșitul semestrului.

1420
01:08:00,290 --> 01:08:03,140
Și, până la acel punct programul meu
ar putea fi utilizați de memorie

1421
01:08:03,140 --> 01:08:05,540
peste tot, peste tot fizic.

1422
01:08:05,540 --> 01:08:08,170
Și așa doar pentru lovituri, eu sunt
O să atragă acest lucru mai departe

1423
01:08:08,170 --> 01:08:11,260
quiz-- Am uitat ce era; eu
cred că poate un 80 sau something--

1424
01:08:11,260 --> 01:08:12,500
drum aici.

1425
01:08:12,500 --> 01:08:15,920
>> Dar asta e bine, pentru că pictural
Voi trage această linie.

1426
01:08:15,920 --> 01:08:19,063
Cu alte cuvinte, în realitate,
în hardware-ul computerului,

1427
01:08:19,063 --> 01:08:20,979
primul scor ar putea
sfârșesc aici pentru că e

1428
01:08:20,979 --> 01:08:22,529
chiar la începutul semestrului.

1429
01:08:22,529 --> 01:08:25,810
Următorul termen s-ar putea încheia aici
pentru că un pic de timp a trecut

1430
01:08:25,810 --> 01:08:27,210
iar programul continuă să funcționeze.

1431
01:08:27,210 --> 01:08:30,060
Urmatorul scor, care a fost
75, ar putea fi aici.

1432
01:08:30,060 --> 01:08:33,420
Iar ultimul scor ar putea fi
un 80, care este aici.

1433
01:08:33,420 --> 01:08:38,729
>> Deci, în realitate, punct de vedere fizic, acest lucru ar putea fi
ce memoria computerului arată.

1434
01:08:38,729 --> 01:08:41,569
Dar acest lucru nu este o mentală utilă
paradigmă pentru un programator de calculator.

1435
01:08:41,569 --> 01:08:44,649
De ce ar trebui să vă pese cazurilor în care
Heck datele se termină în sus?

1436
01:08:44,649 --> 01:08:46,200
Vrei doar pentru a stoca date.

1437
01:08:46,200 --> 01:08:49,390
>> Acest lucru este un fel de discuția noastră
mai devreme de desen cub.

1438
01:08:49,390 --> 01:08:52,200
De ce îți pasă ce
unghiul este cubului

1439
01:08:52,200 --> 01:08:53,740
și modul în care trebuie să activați să-l atragă?

1440
01:08:53,740 --> 01:08:54,950
Vrei doar un cub.

1441
01:08:54,950 --> 01:08:57,359
În mod similar aici,
vreau doar sa carte de grad.

1442
01:08:57,359 --> 01:08:59,559
Vrei doar să se gândească la
acest lucru ca o listă de numere.

1443
01:08:59,559 --> 01:09:01,350
Cui îi pasă cum e
implementat în hardware-ul?

1444
01:09:01,350 --> 01:09:05,180
>> Așa că abstracția acum
este această imagine aici.

1445
01:09:05,180 --> 01:09:07,580
Aceasta este o listă legată, după cum
un programator ar numi,

1446
01:09:07,580 --> 01:09:10,640
în măsura în care aveți
listă, în mod evident de numere.

1447
01:09:10,640 --> 01:09:14,990
Dar este legat pictural
prin intermediul acestor săgeți,

1448
01:09:14,990 --> 01:09:18,510
și toate aceste săgeți are-- dedesubt
capota, daca esti curios,

1449
01:09:18,510 --> 01:09:23,210
Reamintim că hardware-ul nostru fizic are
adrese zero, unu, doi, trei, patru.

1450
01:09:23,210 --> 01:09:28,465
Toate aceste săgeți sunt este ca o hartă
sau instrucțiuni de ghidare, în cazul în care în cazul în care 90 este-- acum

1451
01:09:28,465 --> 01:09:29,090
Trebuie să conta.

1452
01:09:29,090 --> 01:09:31,750
>> Zero, unu, doi, trei,
patru, cinci, șase, șapte.

1453
01:09:31,750 --> 01:09:35,640
Se pare ca 90 este la
memorie număr de șapte adrese.

1454
01:09:35,640 --> 01:09:38,460
Toate aceste săgeți sunt este
ca un pic resturi de hârtie

1455
01:09:38,460 --> 01:09:42,439
care dă indicații pentru a ajunge
program care spune urmați această hartă

1456
01:09:42,439 --> 01:09:43,880
pentru a ajunge la poziția șapte.

1457
01:09:43,880 --> 01:09:46,680
Și acolo vei gasi
al doilea scor test student.

1458
01:09:46,680 --> 01:09:52,100
Între timp, 75-- dacă voi continua acest lucru,
acest lucru este de șapte, opt, nouă, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Această altă săgeată reprezintă doar
o hartă în memoria locație 15.

1461
01:09:59,080 --> 01:10:02,550
Dar, din nou, programator face în general
Nu pasă de acest nivel de detaliu.

1462
01:10:02,550 --> 01:10:05,530
Și, în cele mai multe fiecare programare
limbă astăzi, programator

1463
01:10:05,530 --> 01:10:10,490
chiar nu va ști unde în memorie
aceste numere sunt de fapt.

1464
01:10:10,490 --> 01:10:14,830
Tot el sau ea trebuie să aibă grijă este
că acestea sunt legate între ele într-un fel

1465
01:10:14,830 --> 01:10:18,390
într-o structură de date ca aceasta.

1466
01:10:18,390 --> 01:10:21,580
>> Dar se pare că nu
pentru a obține prea tehnic.

1467
01:10:21,580 --> 01:10:27,430
Dar, tocmai pentru că putem, probabil,
permite să aibă această discuție aici,

1468
01:10:27,430 --> 01:10:33,630
să presupunem că revizuim
această problemă aici, dintr-o matrice.

1469
01:10:33,630 --> 01:10:35,780
Să vedem dacă vom regreta merge aici.

1470
01:10:35,780 --> 01:10:42,950
Acest lucru este de 100, 90, 75 și 80.

1471
01:10:42,950 --> 01:10:44,980
>> Lasă-mă să fac această afirmație pe scurt.

1472
01:10:44,980 --> 01:10:48,980
Aceasta este o matrice, și, din nou,
Caracteristica proeminentă a unei matrice

1473
01:10:48,980 --> 01:10:52,400
este faptul că toate datele sunt înapoi
spate în spate în memory-- literalmente

1474
01:10:52,400 --> 01:10:56,830
un octet sau poate patru octeți,
un numar fix de bytes departe.

1475
01:10:56,830 --> 01:11:00,710
Într-o listă legată, pe care am putea trage
ca aceasta, sub capota, care

1476
01:11:00,710 --> 01:11:02,000
știe unde chestia asta e?

1477
01:11:02,000 --> 01:11:03,630
Ea nu are nevoie chiar să curgă așa.

1478
01:11:03,630 --> 01:11:06,050
Unele dintre aceste date ar putea fi
înapoi la stânga sus acolo.

1479
01:11:06,050 --> 01:11:07,530
Nici măcar nu știu.

1480
01:11:07,530 --> 01:11:15,430
>> Și astfel, cu o matrice, aveți
caracteristică cunoscută sub numele de acces aleatoriu.

1481
01:11:15,430 --> 01:11:20,570
Și ce înseamnă acces aleator este
că computerul poate sări instantaneu

1482
01:11:20,570 --> 01:11:22,730
la orice locație într-o matrice.

1483
01:11:22,730 --> 01:11:23,580
De ce?

1484
01:11:23,580 --> 01:11:26,000
Deoarece computerul știe
că prima locație este

1485
01:11:26,000 --> 01:11:29,540
zero, unu, doi și trei.

1486
01:11:29,540 --> 01:11:33,890
>> Și, așa că, dacă vrei să mergi la
acest element la elementul următor,

1487
01:11:33,890 --> 01:11:36,099
literalmente, în
mintea lui de calculator, trebuie doar să adăugați unul.

1488
01:11:36,099 --> 01:11:39,140
Dacă doriți ca să mergi la al treilea element,
trebuie doar să adăugați elementul următor Unu, doar

1489
01:11:39,140 --> 01:11:40,290
adaugă unul.

1490
01:11:40,290 --> 01:11:42,980
Cu toate acestea, în această versiune
din poveste, să presupunem că

1491
01:11:42,980 --> 01:11:46,080
computerul este în prezent în căutarea
la sau care se ocupă cu numărul 100.

1492
01:11:46,080 --> 01:11:49,770
Cum ajungi la următorul
gradul în cartea de grad?

1493
01:11:49,770 --> 01:11:52,560
>> Trebuie să iei șapte
trepte, care este arbitrară.

1494
01:11:52,560 --> 01:11:58,120
Pentru a ajunge la următoarea, trebuie să
ia încă opt pași pentru a ajunge la 15.

1495
01:11:58,120 --> 01:12:02,250
Cu alte cuvinte, nu e
decalaj constantă între numere,

1496
01:12:02,250 --> 01:12:04,857
și așa că doar ia
calculator mai mult timp este punctul.

1497
01:12:04,857 --> 01:12:06,940
Computerul trebuie să caute
prin memorie în ordine

1498
01:12:06,940 --> 01:12:08,990
pentru a găsi ceea ce căutați.

1499
01:12:08,990 --> 01:12:14,260
>> Așadar, în timp o matrice tinde să fie un
structure-- rapid de date, deoarece vă

1500
01:12:14,260 --> 01:12:17,610
poate literalmente face doar aritmetică simplă
și pentru a obține în cazul în care doriți prin adăugarea de unul,

1501
01:12:17,610 --> 01:12:21,300
pentru instance-- o listă legată,
sacrifici acea caracteristică.

1502
01:12:21,300 --> 01:12:24,020
Nu poți merge de la prima
la două la treia la al patrulea.

1503
01:12:24,020 --> 01:12:25,240
Trebuie să urmați hartă.

1504
01:12:25,240 --> 01:12:28,160
Trebuie să iei mai mulți pași
pentru a ajunge la acele valori, care

1505
01:12:28,160 --> 01:12:30,230
S-ar părea a fi adăugarea de un cost.

1506
01:12:30,230 --> 01:12:35,910
Deci ne plătește un preț, dar ceea ce a fost
caracteristica pe care Dan căuta aici?

1507
01:12:35,910 --> 01:12:38,110
Ce face o listă legată
aparent ne permit să facem,

1508
01:12:38,110 --> 01:12:40,240
care a fost originea
această poveste specială?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Exact.

1511
01:12:43,830 --> 01:12:46,220
O dimensiune dinamică la acesta.

1512
01:12:46,220 --> 01:12:48,040
Putem adăuga la această listă.

1513
01:12:48,040 --> 01:12:51,430
Putem micsora chiar si lista, asa
că suntem folosind doar la fel de mult de memorie

1514
01:12:51,430 --> 01:12:55,560
ca de fapt ne-o dorim și așa
suntem niciodată supraevaluare.

1515
01:12:55,560 --> 01:12:58,470
>> Acum, doar pentru a fi cu adevărat niți-pretentios,
există un cost ascuns.

1516
01:12:58,470 --> 01:13:01,980
Deci, tu nu trebuie doar să mă convingă
vă că acesta este un compromis convingător.

1517
01:13:01,980 --> 01:13:04,190
Nu există un alt cost ascuns aici.

1518
01:13:04,190 --> 01:13:06,550
Beneficiul, să fie clar,
este că obținem dinamism.

1519
01:13:06,550 --> 01:13:10,359
Dacă vreau un alt element, eu pot doar
trage-l și a pus un număr acolo.

1520
01:13:10,359 --> 01:13:12,150
Și apoi eu pot lega
cu o imagine aici,

1521
01:13:12,150 --> 01:13:14,970
întrucât aici, din nou, dacă am
ma pictat într-un colț,

1522
01:13:14,970 --> 01:13:19,410
dacă ceva este deja folosind
memorie aici, am noroc.

1523
01:13:19,410 --> 01:13:21,700
M-am pictat în colț.

1524
01:13:21,700 --> 01:13:24,390
>> Dar ceea ce este ascuns
cost cu o schimbare în această imagine?

1525
01:13:24,390 --> 01:13:27,690
Nu este vorba doar suma
de timp în care este nevoie

1526
01:13:27,690 --> 01:13:29,870
pentru a merge de aici până aici,
care este de șapte trepte, atunci

1527
01:13:29,870 --> 01:13:32,820
opt trepte, care este mai mult de unul.

1528
01:13:32,820 --> 01:13:34,830
Ce este un alt cost ascuns?

1529
01:13:34,830 --> 01:13:35,440
Nu doar timp.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Informații suplimentare este
necesare pentru a realiza această imagine.

1532
01:13:49,940 --> 01:13:53,210
>> Da, acea hartă, acele resturi mici de
hârtie, așa cum am păstra le ca fiind.

1533
01:13:53,210 --> 01:13:55,650
Aceștia arrows-- cei care nu sunt liberi.

1534
01:13:55,650 --> 01:13:57,660
Un computer-- știi
ce un computer are.

1535
01:13:57,660 --> 01:13:58,790
Ea are zerouri și cele.

1536
01:13:58,790 --> 01:14:03,170
Dacă doriți ca să reprezinte o săgeată sau
hartă sau un număr, aveți nevoie de memorie.

1537
01:14:03,170 --> 01:14:05,950
Așa că celălalt preț vă
să plătească pentru o listă legată,

1538
01:14:05,950 --> 01:14:09,070
o știință comună calculator
resursă, este de asemenea spațiu.

1539
01:14:09,070 --> 01:14:11,710
>> Și într-adevăr așa, atât de frecvent,
printre compromisurile

1540
01:14:11,710 --> 01:14:15,580
în proiectarea inginerie software
sisteme este timpul și space--

1541
01:14:15,580 --> 01:14:18,596
sunt două dintre ingredientele, două
dintre ingredientele cele mai costisitoare.

1542
01:14:18,596 --> 01:14:21,220
Acest lucru ma costa mai mult timp
pentru că trebuie să urmeze această hartă,

1543
01:14:21,220 --> 01:14:25,730
dar este, de asemenea, ma costa mai mult spațiu
pentru că trebuie să păstreze această hartă în jurul valorii.

1544
01:14:25,730 --> 01:14:28,730
Așa că speranța, așa cum ne-am un fel de
a discutat mai mult de ieri și de azi,

1545
01:14:28,730 --> 01:14:31,720
este că beneficiile
vor depăși costurile.

1546
01:14:31,720 --> 01:14:33,870
>> Dar nu e nici o soluție evidentă aici.

1547
01:14:33,870 --> 01:14:35,870
Poate că este better--
o rapidă și la murdar,

1548
01:14:35,870 --> 01:14:38,660
așa cum a propus Kareem earlier--
pentru a arunca memorie la problema.

1549
01:14:38,660 --> 01:14:42,520
Doar cumpăra mai multă memorie, cred că mai puțin
greu cu privire la rezolvarea problemei,

1550
01:14:42,520 --> 01:14:44,595
și rezolva într-un mod mai ușor.

1551
01:14:44,595 --> 01:14:46,720
Și, într-adevăr, mai devreme, atunci când
am vorbit despre compromisurile,

1552
01:14:46,720 --> 01:14:49,190
nu era spațiu în
computer și timpul.

1553
01:14:49,190 --> 01:14:51,810
A fost timp de dezvoltator, care
este încă o altă resursă.

1554
01:14:51,810 --> 01:14:54,829
>> Deci, din nou, este acest act de echilibrare
încercând să decidă care dintre aceste lucruri

1555
01:14:54,829 --> 01:14:55,870
ești dispus să-și petreacă?

1556
01:14:55,870 --> 01:14:57,380
Care este cel mai scump?

1557
01:14:57,380 --> 01:15:01,040
Care dă rezultate mai bune?

1558
01:15:01,040 --> 01:15:01,540
Da?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Intr-adevar.

1561
01:15:12,580 --> 01:15:15,970
În acest caz, dacă sunteți
reprezentând numere în maps--

1562
01:15:15,970 --> 01:15:18,820
acestea sunt numite în mai multe limbi
"indicii" sau "adrese" -

1563
01:15:18,820 --> 01:15:20,390
este dublu spațiu.

1564
01:15:20,390 --> 01:15:24,390
Acest lucru nu trebuie să fie la fel de rău ca dublu în cazul în care
chiar acum suntem doar numere de stocare.

1565
01:15:24,390 --> 01:15:27,410
Să presupunem că am fost stocarea
înregistrările pacienților într-un hospital--

1566
01:15:27,410 --> 01:15:30,870
așa că numele Pierson, numere de telefon,
numere de securitate socială, medicul

1567
01:15:30,870 --> 01:15:31,540
istorie.

1568
01:15:31,540 --> 01:15:34,160
Această casetă ar putea fi mult,
mult mai mare, caz în care

1569
01:15:34,160 --> 01:15:38,000
un pic pointer minuscul, adresa
în următorii element-- nu e mare lucru.

1570
01:15:38,000 --> 01:15:40,620
Este un astfel de franjuri
cost cu o schimbare nu contează.

1571
01:15:40,620 --> 01:15:43,210
Dar, în acest caz, da, este o dublare.

1572
01:15:43,210 --> 01:15:45,290
Buna intrebare.

1573
01:15:45,290 --> 01:15:47,900
>> Hai să vorbim despre timp o
puțin mai concret.

1574
01:15:47,900 --> 01:15:50,380
Care este timpul de funcționare
de a căuta această listă?

1575
01:15:50,380 --> 01:15:53,640
Să presupunem că am vrut să caute
prin toate clasele elevilor,

1576
01:15:53,640 --> 01:15:55,980
și există n clase
în această structură de date.

1577
01:15:55,980 --> 01:15:58,830
Aici, de asemenea, putem împrumuta
vocabularul anterior.

1578
01:15:58,830 --> 01:16:00,890
Aceasta este o structură de date liniară.

1579
01:16:00,890 --> 01:16:04,570
>> O mare n este ceea ce este necesar pentru a obține
la sfârșitul acestei structuri de date,

1580
01:16:04,570 --> 01:16:08,410
whereas-- și nu am văzut
acest before-- o matrice vă oferă

1581
01:16:08,410 --> 01:16:13,555
ceea ce se numește timp constant, ceea ce înseamnă
cu un pas sau doi pași sau 10 steps--

1582
01:16:13,555 --> 01:16:14,180
nu contează.

1583
01:16:14,180 --> 01:16:15,440
Este un număr fix.

1584
01:16:15,440 --> 01:16:17,440
Nu are nimic de-a face cu
dimensiunea tabloului.

1585
01:16:17,440 --> 01:16:20,130
Și motivul pentru care,
din nou, este de acces aleatoriu.

1586
01:16:20,130 --> 01:16:23,180
Computerul poate pur și simplu imediat
sări într-o altă locație,

1587
01:16:23,180 --> 01:16:27,770
pentru că acestea sunt toate la fel
distanta de la orice altceva.

1588
01:16:27,770 --> 01:16:29,112
Nu există nici o gândire implicate.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
In regula.

1591
01:16:32,400 --> 01:16:39,230
Așa că, dacă eu pot, lasă-mă să încerc să
pictează două imagini finale.

1592
01:16:39,230 --> 01:16:42,830
Un foarte comun cunoscut ca un tabel hash.

1593
01:16:42,830 --> 01:16:51,120
Deci, pentru a motiva această discuție,
Stai să mă gândesc cum să facă acest lucru.

1594
01:16:51,120 --> 01:16:52,610
>> Deci, cum zici de asta?

1595
01:16:52,610 --> 01:16:55,160
Să presupunem că problema
vrem să rezolve acum

1596
01:16:55,160 --> 01:16:58,360
implementează într-un dictionary--
astfel încât o grămadă de cuvinte în limba engleză

1597
01:16:58,360 --> 01:16:59,330
sau orice altceva.

1598
01:16:59,330 --> 01:17:02,724
Iar scopul este de a fi capabil să răspundă
întrebări din formular este acesta un cuvânt?

1599
01:17:02,724 --> 01:17:04,640
Astfel încât să doriți să pună în aplicare
un corector ortografic, doar

1600
01:17:04,640 --> 01:17:07,220
ca un dicționar fizic
că te poți uita lucrurile în.

1601
01:17:07,220 --> 01:17:10,490
Să presupunem că ar fi să fac acest lucru cu o matrice.

1602
01:17:10,490 --> 01:17:12,590
Aș putea face asta.

1603
01:17:12,590 --> 01:17:20,756
>> Și să presupunem că cuvintele sunt măr
și banane și pepene galben.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Si eu nu pot gândi la fructe
care începe cu d, așa că suntem doar

1606
01:17:26,465 --> 01:17:27,590
va avea trei fructe.

1607
01:17:27,590 --> 01:17:31,510
Deci, aceasta este o matrice, și suntem
stocarea toate aceste cuvinte

1608
01:17:31,510 --> 01:17:34,200
în acest dicționar ca o matrice.

1609
01:17:34,200 --> 01:17:39,350
Întrebarea, atunci, este cum altfel
ai putea stoca aceste informații?

1610
01:17:39,350 --> 01:17:43,160
>> Ei bine, eu sunt un fel de înșelăciune aici, pentru că
fiecare dintre aceste litere în cuvântul

1611
01:17:43,160 --> 01:17:44,490
este într-adevăr un octet individuale.

1612
01:17:44,490 --> 01:17:46,740
Așa că, dacă într-adevăr am vrut să fiu
lindină-pretentios, eu ar trebui într-adevăr

1613
01:17:46,740 --> 01:17:49,600
să fie împărțirea asta în mult
bucăți mai mici de memorie,

1614
01:17:49,600 --> 01:17:51,289
și am putea face exact acest lucru.

1615
01:17:51,289 --> 01:17:53,580
Dar noi vom rula în
aceeași problemă ca și mai înainte.

1616
01:17:53,580 --> 01:17:56,674
Ce se întâmplă dacă, după cum Merriam Webster sau Oxford
face fiecare year-- ei adăuga cuvinte

1617
01:17:56,674 --> 01:17:59,340
la dictionary-- noi nu facem
doresc neapărat să ne picteze

1618
01:17:59,340 --> 01:18:00,780
într-un colț cu o matrice?

1619
01:18:00,780 --> 01:18:05,710
>> Deci, în loc, poate o abordare mai inteligentă
este de a pune mere în propriul său nod sau cutie,

1620
01:18:05,710 --> 01:18:11,190
așa cum s-ar spune, banane, și
atunci aici avem cantalup.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Si noi șir aceste lucruri împreună.

1623
01:18:16,790 --> 01:18:19,980
Deci, acesta este matrice, și
aceasta este lista legată.

1624
01:18:19,980 --> 01:18:23,300
Dacă nu se poate vedea destul, pur și simplu
spune "matrice", iar acest lucru spune "listă."

1625
01:18:23,300 --> 01:18:25,780
>> Așa că avem aceleași
aspecte exacte ca înainte,

1626
01:18:25,780 --> 01:18:28,600
prin care avem acum
dinamism în lista noastră legată.

1627
01:18:28,600 --> 01:18:31,090
Dar avem un dicționar destul de lent.

1628
01:18:31,090 --> 01:18:32,870
Să presupunem că vreau să se uite un cuvânt.

1629
01:18:32,870 --> 01:18:35,430
s-ar putea să dureze O mare de n
pași, deoarece cuvântul ar putea

1630
01:18:35,430 --> 01:18:37,840
fie tot drumul la sfârșitul
lista, cum ar fi pepenele galben.

1631
01:18:37,840 --> 01:18:40,600
Și se pare că
în programare, sortare

1632
01:18:40,600 --> 01:18:42,700
din Sfântul Graal al datelor
structuri, este ceva

1633
01:18:42,700 --> 01:18:46,620
care vă oferă constant
timp ca o matrice

1634
01:18:46,620 --> 01:18:50,870
dar care încă vă oferă dinamism.

1635
01:18:50,870 --> 01:18:52,940
>> Deci, putem avea cel mai bun din ambele lumi?

1636
01:18:52,940 --> 01:18:55,570
Și într-adevăr, există ceva
numit tabel hash

1637
01:18:55,570 --> 01:18:59,320
care vă permite să faceți exact
că, deși aproximativ.

1638
01:18:59,320 --> 01:19:03,140
Un tabel hash este un columbofil
Structura de date pe care le

1639
01:19:03,140 --> 01:19:06,340
se poate gândi ca despre
combinație a unui array--

1640
01:19:06,340 --> 01:19:12,390
și am de gând să-l atragă
cum ar fi astea-- și liste legate

1641
01:19:12,390 --> 01:19:17,310
că voi trage ca asta aici.

1642
01:19:17,310 --> 01:19:19,760
>> Și modul în care acest lucru
lucrări este după cum urmează.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
În cazul în care acest now-- hash table--
este structura mea de date a treia,

1645
01:19:29,540 --> 01:19:32,590
și vreau să stocheze
cuvinte în această, eu nu fac

1646
01:19:32,590 --> 01:19:35,440
doriți să stocați doar cele de mai
cuvinte spate în spate la spate în spate.

1647
01:19:35,440 --> 01:19:37,430
Vreau să pârghie unele
informaţie

1648
01:19:37,430 --> 01:19:40,330
despre cuvintele care vă va permite
mi-l în cazul în care este mai rapid.

1649
01:19:40,330 --> 01:19:43,666
>> Așa că, având în vedere cuvintele mere
și banane și pepene galben,

1650
01:19:43,666 --> 01:19:45,040
Am ales în mod deliberat aceste cuvinte.

1651
01:19:45,040 --> 01:19:45,340
De ce?

1652
01:19:45,340 --> 01:19:47,631
Ce este un fel de fundamental
diferite despre cele trei?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Ce e evident?

1655
01:19:51,484 --> 01:19:52,900
Ei încep cu litere diferite.

1656
01:19:52,900 --> 01:19:53,900
>> Deci, tu ce știi?

1657
01:19:53,900 --> 01:19:57,120
Mai degrabă decât a pune toate cuvintele mele în
aceeași găleată, ca să spunem așa,

1658
01:19:57,120 --> 01:20:00,390
cum ar fi într-o listă mare, de ce nu
Eu cel puțin încerc o optimizare

1659
01:20:00,390 --> 01:20:04,180
și face listele mele 1/26, atâta timp.

1660
01:20:04,180 --> 01:20:07,440
O optimizare convingătoare
ar putea fi de ce nu

1661
01:20:07,440 --> 01:20:10,650
Eu-- la introducerea unui cuvânt
în această structură de date,

1662
01:20:10,650 --> 01:20:14,300
în memoria calculatorului, de ce
nu am pus toate cuvintele "un" aici,

1663
01:20:14,300 --> 01:20:17,270
toate "b" cuvinte aici,
și toate "c" cuvintele aici?

1664
01:20:17,270 --> 01:20:24,610
Deci, acest lucru sfârșește prin a pune un mar
aici, banana aici, cantalup aici,

1665
01:20:24,610 --> 01:20:25,730
si asa mai departe.

1666
01:20:25,730 --> 01:20:31,700
>> Și, dacă am o suplimentare
cuvânt like-- ce-o alta?

1667
01:20:31,700 --> 01:20:36,640
Mere, banane, pere.

1668
01:20:36,640 --> 01:20:39,370
Oricine se gândească la un fruct
care începe cu a, b, sau c?

1669
01:20:39,370 --> 01:20:40,570
perfectă Blueberry--.

1670
01:20:40,570 --> 01:20:43,990
Care se va încheia aici.

1671
01:20:43,990 --> 01:20:47,530
Și așa se pare că avem un
marginal soluție mai bună,

1672
01:20:47,530 --> 01:20:50,820
pentru că acum, dacă vreau
pentru a căuta mere, I

1673
01:20:50,820 --> 01:20:53,200
first-- Eu nu doar se arunca cu capul
în structura mea de date.

1674
01:20:53,200 --> 01:20:54,850
Nu se arunca cu capul în memoria computerului meu.

1675
01:20:54,850 --> 01:20:56,530
Mă uit mai întâi la prima literă.

1676
01:20:56,530 --> 01:20:58,610
>> Și acest lucru este ceea ce un calculator
om de știință s-ar spune.

1677
01:20:58,610 --> 01:21:00,760
Vă hash în structura dvs. de date.

1678
01:21:00,760 --> 01:21:04,100
Vă luați datele introduse, care în
acest caz este un cuvânt ca și mere.

1679
01:21:04,100 --> 01:21:07,150
Ai analiza, uita la
prima literă în acest caz,

1680
01:21:07,150 --> 01:21:08,340
prin aceasta hashing.

1681
01:21:08,340 --> 01:21:10,950
Hashing este un termen general prin care
să luați ceva ca intrare

1682
01:21:10,950 --> 01:21:12,116
și ai produce unele ieșire.

1683
01:21:12,116 --> 01:21:15,090
Și ieșire în
caz este locația

1684
01:21:15,090 --> 01:21:18,150
pe care doriți să căutați, primul
locație, a doua locație, a treia.

1685
01:21:18,150 --> 01:21:22,160
Așa că de intrare este de mere,
de ieșire este mai întâi.

1686
01:21:22,160 --> 01:21:25,054
De intrare este banana, The
ieșire ar trebui să fie în al doilea rând.

1687
01:21:25,054 --> 01:21:27,220
De intrare este pepenele galben,
producția ar trebui să fie al treilea.

1688
01:21:27,220 --> 01:21:30,320
De intrare este de afine, The
ieșire ar trebui să fie din nou în al doilea rând.

1689
01:21:30,320 --> 01:21:34,010
Și asta te ajută să luați
comenzile rapide prin memorie

1690
01:21:34,010 --> 01:21:39,050
în scopul de a ajunge la cuvinte
sau date mai eficient.

1691
01:21:39,050 --> 01:21:43,330
>> Acum, acest lucru taie timpul nostru potențial
de la fel de mult ca și unul din 26,

1692
01:21:43,330 --> 01:21:45,850
pentru că dacă presupunem că
au cât mai multe "o" cuvinte ca "z"

1693
01:21:45,850 --> 01:21:48,080
cuvinte ca și cuvinte "q", care
nu este într-adevăr realistic--

1694
01:21:48,080 --> 01:21:50,830
vei avea oblic peste
anumite scrisori ale alphabet--

1695
01:21:50,830 --> 01:21:53,204
dar acest lucru ar fi un incremental
abordare care permite

1696
01:21:53,204 --> 01:21:55,930
tu pentru a ajunge la cuvinte mult mai repede.

1697
01:21:55,930 --> 01:21:59,660
Și, în realitate, un sofisticat
program, Googles lumii,

1698
01:21:59,660 --> 01:22:02,180
Facebooks a world--
ei s-ar folosi un tabel hash

1699
01:22:02,180 --> 01:22:03,740
pentru o mulțime de scopuri diferite.

1700
01:22:03,740 --> 01:22:06,590
Dar ei n-ar fi atât de naiv încât
să se uite doar la prima literă

1701
01:22:06,590 --> 01:22:09,700
în mere sau banane sau
pere sau pepenele galben,

1702
01:22:09,700 --> 01:22:13,420
pentru că așa cum puteți vedea aceste
liste ar putea obține încă mult timp.

1703
01:22:13,420 --> 01:22:17,130
>> Și, astfel încât acest lucru ar putea fi încă un fel
de linear--, astfel un fel de lent,

1704
01:22:17,130 --> 01:22:19,980
cum ar fi cu mare O n
pe care am discutat mai devreme.

1705
01:22:19,980 --> 01:22:25,290
Deci, ce un adevărat tabel hash bun va
do-- va avea o matrice mult mai mare.

1706
01:22:25,290 --> 01:22:28,574
Și se va folosi o mult mai
Funcția hashing sofisticate,

1707
01:22:28,574 --> 01:22:30,240
astfel încât să nu se uita doar la "a."

1708
01:22:30,240 --> 01:22:35,480
Poate că se uită la "o-p-p-l-e" și
cumva convertește aceste cinci litere

1709
01:22:35,480 --> 01:22:38,400
în locul unde
Apple ar trebui să fie stocate.

1710
01:22:38,400 --> 01:22:42,660
Noi doar în mod naiv folosind litera "a"
singur, pentru că e frumos și simplu.

1711
01:22:42,660 --> 01:22:44,600
>> Dar un tabel hash, în
la sfârșitul anului, vă puteți gândi

1712
01:22:44,600 --> 01:22:47,270
ca o combinație de
o matrice, fiecare dintre acestea

1713
01:22:47,270 --> 01:22:51,700
are o listă legată în mod ideal, care
ar trebui să fie cât mai scurt posibil.

1714
01:22:51,700 --> 01:22:54,364
Și acest lucru nu este o soluție evidentă.

1715
01:22:54,364 --> 01:22:57,280
De fapt, o mare parte din reglajul fin
care merge pe sub capota atunci când

1716
01:22:57,280 --> 01:22:59,654
punerea în aplicare a acestor tipuri de
structuri de date sofisticate

1717
01:22:59,654 --> 01:23:01,640
este ceea ce este dreptul
Lungimea de matrice?

1718
01:23:01,640 --> 01:23:03,250
Care este funcția hash dreapta?

1719
01:23:03,250 --> 01:23:04,830
Cum vă stocați lucruri în memorie?

1720
01:23:04,830 --> 01:23:07,249
>> Dar, dau seama cât de repede
acest tip de discuție

1721
01:23:07,249 --> 01:23:10,540
a escaladat, fie atât de departe încât e un fel
de deasupra capului, în acest moment, care

1722
01:23:10,540 --> 01:23:11,360
e bine.

1723
01:23:11,360 --> 01:23:18,820
Dar, am început, amintesc, cu adevărat
ceva de nivel scăzut și electronic.

1724
01:23:18,820 --> 01:23:20,819
Și așa este din nou
Tema de abstracție,

1725
01:23:20,819 --> 01:23:23,610
în cazul în care odată ce începe să luați pentru
acordat, OK, am it-- acolo

1726
01:23:23,610 --> 01:23:26,680
memorie fizică, OK, am înțeles, fiecare
locația fizică are o adresă,

1727
01:23:26,680 --> 01:23:29,910
OK, am înțeles, eu pot reprezenta
aceste adrese ca arrows--

1728
01:23:29,910 --> 01:23:34,650
puteți începe foarte repede pentru a avea
conversații mai sofisticate

1729
01:23:34,650 --> 01:23:38,360
în cele din urmă par să fie permițându-ne
pentru a rezolva probleme cum ar fi căutarea

1730
01:23:38,360 --> 01:23:41,620
și sortarea mai eficient.

1731
01:23:41,620 --> 01:23:44,190
Și fiți siguri, too--
deoarece cred că acest lucru

1732
01:23:44,190 --> 01:23:48,700
este cea mai adâncă ne-am dus într-o anumită
din aceste subiecte CS proper-- le considerăm,

1733
01:23:48,700 --> 01:23:51,880
făcut într-o zi și jumătate de la această
punctul ceea ce s-ar putea face de obicei peste

1734
01:23:51,880 --> 01:23:55,520
parcursul a opt săptămâni într-un semestru.

1735
01:23:55,520 --> 01:23:59,670
>> Orice întrebări cu privire la acestea?

1736
01:23:59,670 --> 01:24:01,100
Nu?

1737
01:24:01,100 --> 01:24:01,940
In regula.

1738
01:24:01,940 --> 01:24:05,610
Ei bine, de ce nu ne oprim acolo,
a începe masa de prânz câteva minute mai devreme,

1739
01:24:05,610 --> 01:24:07,052
relua în doar aproximativ o oră?

1740
01:24:07,052 --> 01:24:08,760
Iar eu voi persista
un pic cu întrebări.

1741
01:24:08,760 --> 01:24:11,343
Apoi am de gând să trebuie să meargă
să ia câteva apeluri dacă e în regulă.

1742
01:24:11,343 --> 01:24:15,000
Voi activa niște muzică în același timp,
dar masa de prânz ar trebui să fie în jurul valorii de colț.

1743
01:24:15,000 --> 01:24:17,862