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

2
00:00:00,030 --> 00:00:00,460
>> DAVID Malan: Està bé.

3
00:00:00,460 --> 00:00:01,094
Hem tornat.

4
00:00:01,094 --> 00:00:04,260
Així que en aquest segment de la programació el
Vaig pensar que ens agradaria fer és una barreja de coses.

5
00:00:04,260 --> 00:00:06,340
Un d'ells, fer una mica
d'alguna cosa pràctic,

6
00:00:06,340 --> 00:00:08,690
encara que utilitzant una més lúdica
ambient- programació

7
00:00:08,690 --> 00:00:11,620
un que és demostratiu de
exactament el tipus d'idees

8
00:00:11,620 --> 00:00:14,220
hem estat parlant,
però una mica més formal.

9
00:00:14,220 --> 00:00:18,200
Dos, un cop d'ull a algunes de les
les formes més tècnics

10
00:00:18,200 --> 00:00:21,520
que un programador en realitat resoldre
problemes com el problema de la recerca

11
00:00:21,520 --> 00:00:24,530
que mirem abans i
També una manera més fonamental

12
00:00:24,530 --> 00:00:26,020
interessant problema de la classificació.

13
00:00:26,020 --> 00:00:28,840
>> Nosaltres assumim des del principi
que aquest llibre de telèfon es va solucionar,

14
00:00:28,840 --> 00:00:31,980
però que per si sola és en realitat una espècie de
problema difícil amb moltes formes diferents

15
00:00:31,980 --> 00:00:32,479
per resoldre-ho.

16
00:00:32,479 --> 00:00:34,366
Així que utilitzarem aquests com
una classe de problemes

17
00:00:34,366 --> 00:00:36,740
representant de les coses que
podria resoldre en general.

18
00:00:36,740 --> 00:00:38,980
I llavors parlarem
sobre amb cert detall el

19
00:00:38,980 --> 00:00:42,360
es diuen les dades structures--
maneres més elegants com llistes enllaçades

20
00:00:42,360 --> 00:00:46,290
i taules hash i arbres que
un programador en realitat

21
00:00:46,290 --> 00:00:48,890
usar i generalment utilitzar
en una pissarra per pintar

22
00:00:48,890 --> 00:00:51,840
una imatge del que ell o ella
preveu per a la implementació

23
00:00:51,840 --> 00:00:52,980
alguna peça de programari.

24
00:00:52,980 --> 00:00:55,130
>> Així que farem les mans a la primera part.

25
00:00:55,130 --> 00:01:00,090
Pel que només embrutar-se les mans amb una
scratch.mit.edu entorn trucada.

26
00:01:00,090 --> 00:01:02,636
Aquesta és una eina que utilitzem
a la nostra classe de grau.

27
00:01:02,636 --> 00:01:04,510
Tot i que està dissenyat
per a majors de 12 anys,

28
00:01:04,510 --> 00:01:07,570
el fem servir cap amunt
part d'això una mica

29
00:01:07,570 --> 00:01:10,020
ja que és un agradable, divertit
manera gràfica d'aprenentatge

30
00:01:10,020 --> 00:01:12,160
una mica d'alguna cosa sobre la programació.

31
00:01:12,160 --> 00:01:17,600
Així que el cap a aquesta URL, on
Hauria de veure una pàgina com aquest,

32
00:01:17,600 --> 00:01:23,330
i seguir endavant i feu clic
Unir-se a les ratllades a la part superior dreta

33
00:01:23,330 --> 00:01:28,300
i triar un nom d'usuari i una
contrasenya i, finalment, s'aconsegueix

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

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

36
00:01:32,165 --> 00:01:34,665
Vaig pensar que faria ús d'això com una
oportunitat de primera per mostrar això.

37
00:01:34,665 --> 00:01:39,120
Una pregunta va sorgir durant el descans
sobre el que en realitat sembla codi.

38
00:01:39,120 --> 00:01:41,315
I estàvem parlant
durant el descans sobre C,

39
00:01:41,315 --> 00:01:45,060
en particular: en particular, una
nivell més baix en una llengua més antiga.

40
00:01:45,060 --> 00:01:47,750
I acabo de fer una ràpida
Google buscar per trobar el codi C

41
00:01:47,750 --> 00:01:51,574
per a la recerca binària, l'algoritme que ens
utilitzat per buscar aquest llibre de telèfon anterior.

42
00:01:51,574 --> 00:01:54,240
Aquest exemple en particular, per descomptat,
no busca una guia telefònica.

43
00:01:54,240 --> 00:01:57,840
Simplement busca en un munt de
números a la memòria de l'ordinador.

44
00:01:57,840 --> 00:02:01,000
Però per obtenir només una representació visual
sentit del que és una programació real

45
00:02:01,000 --> 00:02:05,370
el llenguatge s'assembla, es veu
una mica d'alguna cosa com això.

46
00:02:05,370 --> 00:02:09,759
Per tant es tracta de més de 20,
30 o més línies de codi,

47
00:02:09,759 --> 00:02:12,640
però la conversa que
estaven tenint durant les vacances

48
00:02:12,640 --> 00:02:16,000
va ser sobre com aquest fet
obté transformat en zeros i uns

49
00:02:16,000 --> 00:02:19,200
i si un no pot revertir aquest
processar i anar de zeros i uns

50
00:02:19,200 --> 00:02:20,210
tornar al codi.

51
00:02:20,210 --> 00:02:22,620
>> Desafortunadament, el procés de
és tan transformadora

52
00:02:22,620 --> 00:02:24,890
que és molt més fàcil dir que fer-ho.

53
00:02:24,890 --> 00:02:29,400
Vaig seguir endavant i en realitat va resultar
aquest programa, recerca binària,

54
00:02:29,400 --> 00:02:32,700
en zeros i uns a manera d'una
El programa anomenat compilador que jo

55
00:02:32,700 --> 00:02:34,400
passa que té aquí a la dreta en el meu Mac.

56
00:02:34,400 --> 00:02:37,850
I si ens fixem en la pantalla
aquí, centrant-se específicament

57
00:02:37,850 --> 00:02:43,520
sobre aquestes mitjanes sis columnes només,
veurà només zeros i uns.

58
00:02:43,520 --> 00:02:48,290
I aquests són els zeros i uns que
compondre exactament aquest programa de cerca.

59
00:02:48,290 --> 00:02:53,720
>> I així, cada tros de cinc bits,
cada byte de zeros i uns aquí,

60
00:02:53,720 --> 00:02:57,310
representar alguna instrucció
normalment dins d'un ordinador.

61
00:02:57,310 --> 00:03:00,730
I de fet, si vostè ha sentit el
lema publicitari "Intel inside" - que,

62
00:03:00,730 --> 00:03:04,610
per descomptat, simplement vol dir que té una
CPU Intel o el cervell a l'interior de l'equip.

63
00:03:04,610 --> 00:03:08,000
I el que significa ser un CPU és
que té un conjunt d'instruccions,

64
00:03:08,000 --> 00:03:08,840
per dir-ho així.

65
00:03:08,840 --> 00:03:11,620
>> Cada CPU en el món, molts
ells fabricats per Intel en aquests dies,

66
00:03:11,620 --> 00:03:13,690
comprèn un nombre finit
nombre d'instruccions.

67
00:03:13,690 --> 00:03:18,690
I aquestes instruccions són tan baix nivell
com afegir aquests dos nombres,

68
00:03:18,690 --> 00:03:22,560
multiplicar aquests dos nombres,
moure aquesta peça d'informació d'aquí

69
00:03:22,560 --> 00:03:27,340
d'aquí en memòria, guardar aquest
la informació d'aquí fins aquí a la memòria,

70
00:03:27,340 --> 00:03:32,200
i així forth-- molt, molt
De baix nivell, gairebé detalls electrònics.

71
00:03:32,200 --> 00:03:34,780
Però amb els matemàtica
operacions acoblada

72
00:03:34,780 --> 00:03:37,410
amb el que hem comentat anteriorment,
la representació de dades

73
00:03:37,410 --> 00:03:40,450
com zeros i uns, pot
tot el que s'acumulen

74
00:03:40,450 --> 00:03:44,180
que un ordinador pot fer avui, si
és textual, gràfica, musical,

75
00:03:44,180 --> 00:03:45,580
o d'una altra manera.

76
00:03:45,580 --> 00:03:49,450
>> Així que això és molt fàcil d'aconseguir
perdut entre la mala herba de forma ràpida.

77
00:03:49,450 --> 00:03:52,150
I hi ha una gran quantitat de
reptes sintàctics

78
00:03:52,150 --> 00:03:56,630
pel que si es fa el més simple,
més estúpida d'errors tipogràfics cap dels programes

79
00:03:56,630 --> 00:03:57,860
funcionarà en absolut.

80
00:03:57,860 --> 00:04:00,366
I així, en lloc d'utilitzar una
llenguatge com C aquest matí,

81
00:04:00,366 --> 00:04:02,240
Vaig pensar que seria
més divertit per fer realitat

82
00:04:02,240 --> 00:04:04,840
alguna cosa més visual, que
mentre dissenyat per a nens

83
00:04:04,840 --> 00:04:08,079
és en realitat una manifestació perfecta
d'una programació real

84
00:04:08,079 --> 00:04:10,370
language-- només passa a
utilitzar imatges en lloc de text

85
00:04:10,370 --> 00:04:11,710
per a representar aquestes idees.

86
00:04:11,710 --> 00:04:15,470
>> Així que una vegada que de fet té una
compte en scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
feu clic al botó Crear
a la part superior esquerra de la pàgina.

88
00:04:21,070 --> 00:04:24,620
I cal veure un entorn com
el que estic a punt de veure en la meva pantalla

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

90
00:04:26,310 --> 00:04:29,350
I anem a passar només una mica
poc de temps jugant aquí.

91
00:04:29,350 --> 00:04:34,080
Vegem si no tots podem resoldre alguns
problemes junts de la manera següent.

92
00:04:34,080 --> 00:04:39,420
>> Així que el que veurà dins d'aquest
ambient- i de fet acaba de deixar

93
00:04:39,420 --> 00:04:40,050
M'aturo.

94
00:04:40,050 --> 00:04:42,680
Hi ha algú que no és aquí?

95
00:04:42,680 --> 00:04:45,070
Aquí no?

96
00:04:45,070 --> 00:04:45,800
D'ACORD.

97
00:04:45,800 --> 00:04:49,030
Així que permetin-me assenyalar alguns
característiques d'aquest entorn.

98
00:04:49,030 --> 00:04:55,024
>> Així que a la part superior esquerra de la pantalla, ens
L'etapa de tenir ratllades, per dir-ho.

99
00:04:55,024 --> 00:04:57,440
Scratch és no només el nom
d'aquest llenguatge de programació;

100
00:04:57,440 --> 00:05:00,356
que és també el nom del gat que es
veus per defecte no en taronja.

101
00:05:00,356 --> 00:05:02,160
Ell està en una etapa, per la qual
de la mateixa manera que vaig descriure

102
00:05:02,160 --> 00:05:05,770
la tortuga anteriorment com a membres d'un
rectangular entorn de la targeta blanca.

103
00:05:05,770 --> 00:05:09,800
El món d'aquest gat està confinat en la seva totalitat
a aquest rectangle sobre de la tapa allà.

104
00:05:09,800 --> 00:05:12,210
>> Mentrestant, a la dreta
costat aquí, és

105
00:05:12,210 --> 00:05:15,610
només una àrea de seqüència, un
pissarra en blanc si es vol.

106
00:05:15,610 --> 00:05:18,590
Aquí és on anem a escriure
els nostres programes en un moment.

107
00:05:18,590 --> 00:05:22,935
I els blocs de construcció que hauran
utilitzar per escriure aquest program-- el trencaclosques

108
00:05:22,935 --> 00:05:25,310
peces, si vostè està voluntat--
els que estan aquí al mig,

109
00:05:25,310 --> 00:05:27,500
i estan categoritzats
per funcionalitat.

110
00:05:27,500 --> 00:05:31,000
Així, per exemple, seguiré endavant
i demostrar almenys un d'aquests.

111
00:05:31,000 --> 00:05:33,690
Vaig a seguir endavant i feu clic
la Categoria de control fins a la part superior.

112
00:05:33,690 --> 00:05:35,720
>> Així que aquestes són les categories sobre de la tapa.

113
00:05:35,720 --> 00:05:39,410
Vaig a clic a la categoria de control.

114
00:05:39,410 --> 00:05:44,020
Més aviat, vaig a feu clic als Esdeveniments
categoria, el primer de tots en la superior.

115
00:05:44,020 --> 00:05:47,790
I si desitja seguir endavant, fins i tot
en fer això, vostè és molt benvingut a.

116
00:05:47,790 --> 00:05:52,180
Vaig a fer clic i arrossegar aquest
primer, "quan es fa clic a bandera verda."

117
00:05:52,180 --> 00:05:58,410
I després vaig a deixar que només
més o menys en la part superior de les meves pissarres en blanc.

118
00:05:58,410 --> 00:06:01,450
>> I el que és bo de les ratllades
és que aquesta peça del trencaclosques, quan

119
00:06:01,450 --> 00:06:04,560
enclavada amb un altre trencaclosques
peces, es van a fer, literalment,

120
00:06:04,560 --> 00:06:06,460
el que aquestes peces del trencaclosques diuen que fer.

121
00:06:06,460 --> 00:06:09,710
Així, per exemple, Scratch és correcta
ara al centre del seu món.

122
00:06:09,710 --> 00:06:14,660
Vaig a seguir endavant i triar
Ara, anem a dir, la categoria de moviment,

123
00:06:14,660 --> 00:06:18,000
Si desitja fer ho
same-- categoria de moviment.

124
00:06:18,000 --> 00:06:20,430
I ara noto que tinc en el seu conjunt
munt de peces d'un trencaclosques aquí

125
00:06:20,430 --> 00:06:23,370
que, de nou, una mena de fer el que diuen.

126
00:06:23,370 --> 00:06:28,110
I vaig a seguir endavant i arrossegar i
deixar caure el bloc de moviment per aquí.

127
00:06:28,110 --> 00:06:31,860
>> I noti que tan aviat com s'obté
prop de la part inferior de la "bandera verda

128
00:06:31,860 --> 00:06:34,580
fet clic a "botó, l'avís
com apareix una línia blanca,

129
00:06:34,580 --> 00:06:36,950
com si fos gairebé
magnètica, que vol anar-hi.

130
00:06:36,950 --> 00:06:43,070
Simplement deixa anar, i s'encaixarà
junts i les formes coincidiran.

131
00:06:43,070 --> 00:06:46,620
potser i ara gairebé es pot
endevinar cap a on anem amb això.

132
00:06:46,620 --> 00:06:51,570
>> Si ens fixem en l'etapa de Scratch
per aquí i mirar a la part superior de la mateixa,

133
00:06:51,570 --> 00:06:55,142
veurà una llum vermella, una
senyal de stop, i una bandera verda.

134
00:06:55,142 --> 00:06:57,100
I seguiré endavant
i veure les meves screen--

135
00:06:57,100 --> 00:06:58,460
per un moment, si pogués.

136
00:06:58,460 --> 00:07:01,960
Vaig a fer clic al
bandera verda en aquest moment,

137
00:07:01,960 --> 00:07:07,850
i es va traslladar el que sembla ser 10 passos
o 10 píxels, 10 punts, a la pantalla.

138
00:07:07,850 --> 00:07:13,390
>> I el que no és tan emocionant,
però permetin-me proposar

139
00:07:13,390 --> 00:07:17,440
sense ni tan sols l'ensenyament d'això, només
utilitzant l'amo del seu propi let intuition--

140
00:07:17,440 --> 00:07:22,560
Em proposo a esbrinar com
fer peu dret esgarrapades fora de l'escenari.

141
00:07:22,560 --> 00:07:28,700
Faci que donar pas a la dreta
la pantalla, tot el camí a la dreta.

142
00:07:28,700 --> 00:07:32,200
Deixeu-me donar-li un moment
o pel que lluitar amb això.

143
00:07:32,200 --> 00:07:37,681
És possible que vulgueu fer una ullada
en altres categories de blocs.

144
00:07:37,681 --> 00:07:38,180
Tot bé.

145
00:07:38,180 --> 00:07:41,290
Així que per recapitular, quan tenim
la bandera verda clic aquí

146
00:07:41,290 --> 00:07:44,850
i moure 10 passos és la
única instrucció, cada vegada que

147
00:07:44,850 --> 00:07:46,720
feu clic a la bandera verda, el que està passant?

148
00:07:46,720 --> 00:07:50,070
Bé, això és córrer el meu programa.

149
00:07:50,070 --> 00:07:52,450
Pel que podia fer això
potser 10 vegades de forma manual,

150
00:07:52,450 --> 00:07:55,130
però això se sent una mica
hackish poc, per així dir-ho,

151
00:07:55,130 --> 00:07:57,480
pel que no estic realment
la solució del problema.

152
00:07:57,480 --> 00:08:00,530
Només intent una vegada i una
una i altra vegada i una altra

153
00:08:00,530 --> 00:08:03,180
fins que tipus d'accident
aconseguir la directiva

154
00:08:03,180 --> 00:08:05,560
que es va proposar aconseguir abans.

155
00:08:05,560 --> 00:08:08,200
>> Però sabem per la nostra
pseudocodi anterior que hi ha

156
00:08:08,200 --> 00:08:11,870
aquesta noció en la programació de bucles,
fer alguna cosa una i altra vegada.

157
00:08:11,870 --> 00:08:14,888
I així vaig veure que un munt de vostès
assolit per la peça de trencaclosques el que?

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

159
00:08:17,870 --> 00:08:18,730
Repetiu fins.

160
00:08:18,730 --> 00:08:21,400
Així que podríem fer alguna cosa
de la mateixa manera que repetir fins.

161
00:08:21,400 --> 00:08:23,760
¿I què es repeteix fins que exactament?

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

163
00:08:27,720 --> 00:08:28,540
>> D'ACORD.

164
00:08:28,540 --> 00:08:31,974
I me n'aniré amb un que és
una mica més senzill només per un moment.

165
00:08:31,974 --> 00:08:33,140
Déjame seguir endavant i fer això.

166
00:08:33,140 --> 00:08:35,559
Recordeu que, ja que pot tenir
descobert sota control,

167
00:08:35,559 --> 00:08:38,409
hi ha aquest bloc de repetició, la qual cosa
no es veu com si fos tan gran.

168
00:08:38,409 --> 00:08:41,039
No hi ha molt ambient a
entre aquestes dues línies grogues.

169
00:08:41,039 --> 00:08:43,539
No obstant això, com alguns de vostès podrien tenir
notat, si arrossega i deixar anar,

170
00:08:43,539 --> 00:08:45,150
observi com creix per omplir la forma.

171
00:08:45,150 --> 00:08:46,274
>> I fins i tot es pot ficar més.

172
00:08:46,274 --> 00:08:48,670
Simplement seguirà creixent si
s'arrossega i es passa a sobre.

173
00:08:48,670 --> 00:08:51,110
I no sé el que és
millor aquí, així que anem

174
00:08:51,110 --> 00:08:54,760
Em repeteixo almenys cinc vegades, per
instància i, a continuació, tornar a l'etapa

175
00:08:54,760 --> 00:08:56,720
i feu clic a la bandera verda.

176
00:08:56,720 --> 00:08:59,110
I ara es va adonar que no és molt allà.

177
00:08:59,110 --> 00:09:02,400
>> Ara alguns de vostès proposen, com
Victòria acaba de fer, repetir 10 vegades.

178
00:09:02,400 --> 00:09:05,140
I que fa en general
portar-lo fins al final,

179
00:09:05,140 --> 00:09:10,510
però ¿no hi hauria un més robust
de manera arbitrària esbrinar

180
00:09:10,510 --> 00:09:12,640
quants moviments per fer?

181
00:09:12,640 --> 00:09:17,680
Quin podria ser un bloc millor
de repetir 10 vegades?

182
00:09:17,680 --> 00:09:20,380
>> Sí, per què no fer alguna cosa per sempre?

183
00:09:20,380 --> 00:09:24,390
I ara anem a moure aquest tros del trencaclosques
A l'interior hi ha i desfer d'aquest.

184
00:09:24,390 --> 00:09:28,300
Ara noti, sense importar on les ratllades
obertures, que va fins la vora.

185
00:09:28,300 --> 00:09:30,700
I afortunadament el MIT,
que fa Scratch, simplement

186
00:09:30,700 --> 00:09:33,190
s'assegura que mai
desapareix per complet.

187
00:09:33,190 --> 00:09:35,360
Sempre es pot agafar la seva cua.

188
00:09:35,360 --> 00:09:37,680
>> I de la mateixa manera intuïtiva,
¿Per què segueix en moviment?

189
00:09:37,680 --> 00:09:38,892
Què està passant aquí?

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

191
00:09:41,440 --> 00:09:43,824
Ell sembla haver-se aturat, però
llavors, si recullo i arrossegament

192
00:09:43,824 --> 00:09:45,240
ell segueix volent anar per allà.

193
00:09:45,240 --> 00:09:46,123
Perquè és això?

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

195
00:09:51,610 --> 00:09:54,360
En veritat, un ordinador és, literalment,
va a fer el que li indica que fer.

196
00:09:54,360 --> 00:09:58,380
Així que si vostè li va dir que faci com més aviat
El següent per sempre, moure 10 passos,

197
00:09:58,380 --> 00:10:01,860
que seguirà i seguir
fins que vaig arribar al senyal de stop vermell

198
00:10:01,860 --> 00:10:04,620
i aturar el programa complet.

199
00:10:04,620 --> 00:10:06,610
>> Així que encara que no ho va fer
fer això, com podria fer-ho

200
00:10:06,610 --> 00:10:09,510
fer que les ratllades es mouen més ràpid
a través de la pantalla?

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

202
00:10:12,060 --> 00:10:13,280
Més passos, oi?

203
00:10:13,280 --> 00:10:15,710
Així que en lloc de fer 10
alhora, per què no

204
00:10:15,710 --> 00:10:20,100
seguir endavant i canviar-A--
¿Què li propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Així que ara vaig a fer clic al verd
bandera, i, de fet, va molt ràpid.

206
00:10:24,410 --> 00:10:27,180
>> I això, per descomptat, és només
una manifestació de l'animació.

207
00:10:27,180 --> 00:10:28,060
Quina és l'animació?

208
00:10:28,060 --> 00:10:33,090
És només que mostra l'ésser humà
manat sencer d'imatges fixes en realitat,

209
00:10:33,090 --> 00:10:34,160
molt, molt ràpid.

210
00:10:34,160 --> 00:10:36,500
I així, si només estem dient
que es mogui més passos,

211
00:10:36,500 --> 00:10:39,750
només estem tenint l'efecte sigui
on el canvi és a la pantalla

212
00:10:39,750 --> 00:10:42,900
tant més ràpidament per unitat de temps.

213
00:10:42,900 --> 00:10:46,454
>> Ara, el següent repte que vaig proposar
anava a haver de rebot fora de la vora.

214
00:10:46,454 --> 00:10:49,120
I sense saber què trencaclosques
la qual existeixen peces, ja que està ben

215
00:10:49,120 --> 00:10:53,030
si no s'arriba a la
etapa del challenge-- el

216
00:10:53,030 --> 00:10:54,280
Què vol fer intuïtivament?

217
00:10:54,280 --> 00:10:58,030
Com hauríem de rebot cap enrere i
etc., entre l'esquerra i la dreta?

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

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

220
00:11:03,810 --> 00:11:05,680
Així que necessitem algun tipus
de la condició, i

221
00:11:05,680 --> 00:11:09,710
semblen tenir condicionals, de manera que
parlar, en la categoria de control.

222
00:11:09,710 --> 00:11:14,110
Quin d'aquests blocs
és el que probablement volem?

223
00:11:14,110 --> 00:11:15,200
Sí, potser "si, llavors".

224
00:11:15,200 --> 00:11:18,780
Així notar que entre els blocs grocs
tenim aquí, no és aquest "si"

225
00:11:18,780 --> 00:11:23,920
o aquest "si, en cas contrari" bloc que
ens permeten fer una decisió per fer això

226
00:11:23,920 --> 00:11:25,000
o per fer això.

227
00:11:25,000 --> 00:11:27,380
I fins i tot es pot niar
fer diverses coses.

228
00:11:27,380 --> 00:11:34,910
O si no has anat aquí encara,
seguir endavant amb la categoria de detecció

229
00:11:34,910 --> 00:11:39,612
i- veurem si és aquí.

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

231
00:11:43,050 --> 00:11:52,050
>> Llavors, què bloc podria ser útil aquí
per detectar si està fora de l'escenari?

232
00:11:52,050 --> 00:11:56,740
Sí, adonar-se que alguns d'aquests blocs
pot ser parametritzada, per dir-ho.

233
00:11:56,740 --> 00:12:00,706
Poden ser una mena de personalitzar-se, no
a diferència d'HTML ahir amb atributs,

234
00:12:00,706 --> 00:12:03,330
on aquests atributs tipus de
personalitzar el comportament d'una variable.

235
00:12:03,330 --> 00:12:08,880
De la mateixa manera aquí, puc agafar aquesta commovedora
bloc i el canvi i fer la pregunta,

236
00:12:08,880 --> 00:12:11,500
estàs tocant el ratolí
punter de la mateixa manera que el cursor

237
00:12:11,500 --> 00:12:13,250
o està tocant la vora?

238
00:12:13,250 --> 00:12:15,210
>> Així que permetin-me anar i fer això.

239
00:12:15,210 --> 00:12:18,130
Vaig a allunyar per un moment.

240
00:12:18,130 --> 00:12:21,320
Permetin-me aprofitar aquesta peça del trencaclosques
aquí, aquesta peça del trencaclosques d'això,

241
00:12:21,320 --> 00:12:24,570
i vaig a Jumble
cap amunt per un moment.

242
00:12:24,570 --> 00:12:27,620
Vaig a moure això,
canviar això a tocar la vora,

243
00:12:27,620 --> 00:12:38,590
i vaig a fer això de moviment.

244
00:12:38,590 --> 00:12:40,490
Així que aquí estan alguns dels ingredients.

245
00:12:40,490 --> 00:12:42,570
Crec que tinc tot el que vull.

246
00:12:42,570 --> 00:12:47,710
>> Algú vol proposar com
es pot connectar aquests potser de dalt a baix

247
00:12:47,710 --> 00:12:52,020
per tal de resoldre el problema de tenir
Scratch dreta a esquerra a dreta per moure

248
00:12:52,020 --> 00:12:57,020
d'esquerra a dreta a esquerra, cadascuna
temps només rebotant a la paret?

249
00:12:57,020 --> 00:12:58,050
Què vull fer?

250
00:12:58,050 --> 00:13:01,097
Què bloc s'ha de connectar a la
"Bandera verda quan es fa clic en primer lloc"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, així que començarem amb el "per sempre".

253
00:13:06,200 --> 00:13:07,170
El que va dins de la propera?

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

255
00:13:10,290 --> 00:13:11,850
OK, moure els passos.

256
00:13:11,850 --> 00:13:12,350
Tot bé.

257
00:13:12,350 --> 00:13:14,470
Llavors què?

258
00:13:14,470 --> 00:13:15,120
Amb això, el cas.

259
00:13:15,120 --> 00:13:17,720
I noti, tot i que sembla
intercalat juntes fermament,

260
00:13:17,720 --> 00:13:19,500
només creixerà per omplir.

261
00:13:19,500 --> 00:13:21,500
S'acaba d'entrar en on el vull.

262
00:13:21,500 --> 00:13:25,920
>> I què és el que va posar entre
el si i el llavors?

263
00:13:25,920 --> 00:13:27,180
Probablement "si tocar la vora."

264
00:13:27,180 --> 00:13:31,800
I avís, de nou, és massa gran
per a això, però que creixerà per omplir.

265
00:13:31,800 --> 00:13:35,002
I després girar 15 graus?

266
00:13:35,002 --> 00:13:35,710
Quants graus?

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

268
00:13:38,800 --> 00:13:41,196
Sí, per la qual cosa 180 girarà
amb mi tot el camí al voltant.

269
00:13:41,196 --> 00:13:42,570
Així que anem a veure si tinc aquest dret.

270
00:13:42,570 --> 00:13:43,930
Permetin-me Allunyar.

271
00:13:43,930 --> 00:13:45,130
>> Permetin-me arrossego fins esgarrinxada.

272
00:13:45,130 --> 00:13:50,030
Així que és una mica distorsionada
ara, però que està bé.

273
00:13:50,030 --> 00:13:52,231
Com li puc restablir fàcilment?

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

275
00:13:59,879 --> 00:14:01,045
Jo us vaig a enganyar una mica.

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

277
00:14:04,074 --> 00:14:05,990
Així que estic afegint una altra
bloc, per ser clars.

278
00:14:05,990 --> 00:14:08,424
Vull que el punt 90 graus
a la dreta per defecte,

279
00:14:08,424 --> 00:14:10,840
així que només vaig a dir-li
de fer-ho mitjançant programació.

280
00:14:10,840 --> 00:14:11,632
I aquí anem.

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

282
00:14:14,740 --> 00:14:15,740
Sembla que hem fet.

283
00:14:15,740 --> 00:14:19,980
És una mica estrany, perquè
ell està caminant a l'inrevés.

284
00:14:19,980 --> 00:14:21,250
Anem a trucar a que un error.

285
00:14:21,250 --> 00:14:22,120
Això és un error.

286
00:14:22,120 --> 00:14:27,320
Un error és un error en un programa, una
error lògic que jo, l'ésser humà, vaig fer.

287
00:14:27,320 --> 00:14:28,985
Per què es va a l'inrevés?

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

289
00:14:33,560 --> 00:14:35,250
¿Es cargol MIT dalt o feia jo?

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

291
00:14:38,840 --> 00:14:42,550
>> Sí, vull dir, no és de MIT
criticar. Em van donar una peça del trencaclosques

292
00:14:42,550 --> 00:14:44,970
diu que al seu torn certa quantitat de graus.

293
00:14:44,970 --> 00:14:47,672
I per suggeriment de Victòria,
Estic girant 180 graus,

294
00:14:47,672 --> 00:14:48,880
que és la intuïció correcta.

295
00:14:48,880 --> 00:14:53,700
Però convertir 180 graus literalment
significa girar 180 graus,

296
00:14:53,700 --> 00:14:55,860
i això no és veritat
el que jo vull, pel que sembla.

297
00:14:55,860 --> 00:14:58,026
A causa de que almenys està en
aquest món de dues dimensions,

298
00:14:58,026 --> 00:15:00,740
de manera decisiva és realment va
a ell voltejar l'inrevés.

299
00:15:00,740 --> 00:15:04,030
>> Probablement vull usar el que el bloc
en canvi, en base al que es veu aquí?

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

301
00:15:11,890 --> 00:15:14,790
Com podem fer això?

302
00:15:14,790 --> 00:15:18,380
Sí, pel que podríem assenyalar
en la direcció oposada.

303
00:15:18,380 --> 00:15:22,300
I, de fet, fins i tot això és
no serà suficient,

304
00:15:22,300 --> 00:15:26,410
perquè només podem codificar
que apunta cap a l'esquerra o cap a la dreta.

305
00:15:26,410 --> 00:15:27,920
>> Ja saps el que podríem fer?

306
00:15:27,920 --> 00:15:30,160
Sembla que tenim una
bloc de conveniència aquí.

307
00:15:30,160 --> 00:15:32,987
Si faig zoom, consulteu
una cosa que ens agrada aquí?

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

309
00:15:36,120 --> 00:15:40,020
Així que sembla que el MIT té una
abstracció construïda aquí.

310
00:15:40,020 --> 00:15:45,440
Aquest bloc sembla ser equivalent
a la qual altres blocs, plural?

311
00:15:45,440 --> 00:15:49,510
>> Aquesta a una quadra sembla ser equivalent
a tot aquest trio de blocs

312
00:15:49,510 --> 00:15:50,880
que tenim aquí.

313
00:15:50,880 --> 00:15:54,670
Així que resulta que puc simplificar la meva
programa per desfer-se de tot això

314
00:15:54,670 --> 00:15:58,270
i només cal posar això aquí.

315
00:15:58,270 --> 00:16:01,620
I ara està encara una mica
amb errors, i això està bé per ara.

316
00:16:01,620 --> 00:16:03,370
Anem a deixar que sigui.

317
00:16:03,370 --> 00:16:06,000
Però el meu programa és encara
més simple, i això, també,

318
00:16:06,000 --> 00:16:09,060
seria representativa
d'un objectiu en programming--

319
00:16:09,060 --> 00:16:13,430
és fer idealment com el seu codi
simple, el més compacte possible,

320
00:16:13,430 --> 00:16:15,650
sense deixar de ser tan
llegibles com sigui possible.

321
00:16:15,650 --> 00:16:20,310
No vol fer-ho de manera succinta
que és difícil d'entendre.

322
00:16:20,310 --> 00:16:22,826
>> Però cal notar que he substituït
tres blocs amb un,

323
00:16:22,826 --> 00:16:24,200
i això és sens dubte una bona cosa.

324
00:16:24,200 --> 00:16:27,280
He abstreu la noció
de comprovar si estàs

325
00:16:27,280 --> 00:16:29,120
a la vora amb un sol bloc.

326
00:16:29,120 --> 00:16:31,520
Ara podem tenir diversió amb això, de fet.

327
00:16:31,520 --> 00:16:35,790
Això no afegeix tant
valor intel·lectual però el valor lúdic.

328
00:16:35,790 --> 00:16:39,730
Vaig a seguir endavant
i apoderar-se de aquest so aquí.

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

330
00:16:42,900 --> 00:16:46,420
Així que permetin-me anar per davant, i em va deixar
aturar el programa per un moment.

331
00:16:46,420 --> 00:16:52,070
Vaig a gravar el següent,
permetent l'accés al micròfon.

332
00:16:52,070 --> 00:16:53,181
>> Aquí anem.

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

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

335
00:16:58,710 --> 00:17:01,140
Anem a intentar-ho de nou.

336
00:17:01,140 --> 00:17:02,279
Aquí anem.

337
00:17:02,279 --> 00:17:03,570
OK, he gravat el que no devia.

338
00:17:03,570 --> 00:17:04,580
Aquí anem.

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

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

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

342
00:17:08,800 --> 00:17:09,300
Tot bé.

343
00:17:09,300 --> 00:17:10,791
Ara necessito per desfer-això.

344
00:17:10,791 --> 00:17:11,290
Tot bé.

345
00:17:11,290 --> 00:17:13,950
>> Així que ara tinc una
gravació de només "ouch".

346
00:17:13,950 --> 00:17:18,040
Així que ara vaig a anar
endavant i cridar a aquest "ai".

347
00:17:18,040 --> 00:17:20,270
Vaig a tornar
als meus guions, i ara

348
00:17:20,270 --> 00:17:25,460
notificació no aquest bloc que es diu
jugar "miol" so o reproduir so "ai".

349
00:17:25,460 --> 00:17:28,920
Vaig a arrossegar aquest, i on
hauria de posar això per l'efecte còmic?

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

351
00:17:31,740 --> 00:17:37,860
Sí, de manera que ara és una espècie de
amb errors, perquè ara aquesta block--

352
00:17:37,860 --> 00:17:42,050
notar com aquest "si a la vora,
rebot "és una espècie d'auto-contingut.

353
00:17:42,050 --> 00:17:43,704
Així que he de arreglar això.

354
00:17:43,704 --> 00:17:44,870
Déjame seguir endavant i fer això.

355
00:17:44,870 --> 00:17:48,630
Permetin-me desfer-se d'aquest i tornar
al nostre original, més deliberat

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

357
00:17:49,870 --> 00:18:01,080
Pel que "si toca la vora, a continuació," Vull
al seu torn, com es va proposar Victòria,

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

359
00:18:02,480 --> 00:18:05,497
I és el que vull per jugar
el so "ai" hi ha?

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

361
00:18:11,800 --> 00:18:15,580
>> Sí, observi que està fora
aquest bloc groc.

362
00:18:15,580 --> 00:18:17,680
Així que això també seria una
insecte, però m'he adonat d'això.

363
00:18:17,680 --> 00:18:21,290
Així que vaig a arrossegar-la fins aquí,
i l'avís que ara està dins de la "si".

364
00:18:21,290 --> 00:18:24,250
Pel que el "si" és aquesta classe
com de transferència en forma de braç

365
00:18:24,250 --> 00:18:26,260
que només va a
fer el que hi ha dins d'ella.

366
00:18:26,260 --> 00:18:30,216
Així que ara si Allunyar a
el risc de annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> ORDINADOR: Ai, ai, ai.

369
00:18:36,470 --> 00:18:39,910
>> DAVID Malan: I
només durarà per sempre.

370
00:18:39,910 --> 00:18:44,160
Ara només per accelerar les coses
aquí, deixa anar per davant i obrir,

371
00:18:44,160 --> 00:18:50,460
anem a dir-- m'ho dius a mi anar a alguna
del meu propi material de la classe.

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

373
00:18:53,000 --> 00:19:00,220
I m'ho dius a mi obrir fins, diguem, aquest
1 feta per un dels nostres companys d'ensenyament

374
00:19:00,220 --> 00:19:01,500
Fa un parell d'anys.

375
00:19:01,500 --> 00:19:04,732
Pel que alguns de vostès poden recordar
aquest joc d'antany,

376
00:19:04,732 --> 00:19:05,940
i de fet és notable.

377
00:19:05,940 --> 00:19:08,190
Tot i que hem fet el
més simple dels programes en aquest moment,

378
00:19:08,190 --> 00:19:09,980
anem a considerar el que aquest
que en realitat sembla.

379
00:19:09,980 --> 00:19:10,650
Em Hit joc.

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

381
00:19:14,210 --> 00:19:18,980
>> Així que en aquest joc, tenim una
granota, i l'ús de la fletxa keys--

382
00:19:18,980 --> 00:19:23,340
presa passos més grans del que remember--
Tinc control sobre aquesta granota.

383
00:19:23,340 --> 00:19:29,630
I l'objectiu és aconseguir a través de l'ocupada
camí sense caure en els cotxes.

384
00:19:29,630 --> 00:19:34,735
I anem a veure-- si vaig fins aquí,
haver d'esperar que un registre per desplaçar-se per.

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

386
00:19:38,130 --> 00:19:39,274
Això se sent com un insecte.

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

388
00:19:42,240 --> 00:19:43,495
Aquesta és una espècie d'insecte.

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

390
00:19:45,980 --> 00:19:46,480
Tot bé.

391
00:19:46,480 --> 00:19:51,550
Estic en això aquí,
allà, i després es manté

392
00:19:51,550 --> 00:19:54,100
avançant fins a arribar tot
les granotes a les fulles de nenúfar.

393
00:19:54,100 --> 00:19:55,920
Ara bé, això pot tenir un aspecte
tot el més complex,

394
00:19:55,920 --> 00:19:57,840
però tractarem de trencar
això baix mentalment

395
00:19:57,840 --> 00:20:00,040
i verbalment en els seus blocs de components.

396
00:20:00,040 --> 00:20:03,910
Així que és probable que hi hagi un trencaclosques
peça que no hem vist encara

397
00:20:03,910 --> 00:20:07,440
però això és respondre a les pulsacions de teclat,
a les coses em va colpejar en el teclat.

398
00:20:07,440 --> 00:20:11,660
>> Així que és probable que hi hagi algun tipus de
bloc que diu, que la clau és igual a,

399
00:20:11,660 --> 00:20:15,965
a continuació, fer alguna cosa amb Scratch--
potser moure-10 passos d'aquesta manera.

400
00:20:15,965 --> 00:20:20,240
Si es prem la tecla cap avall, moure 10 passos
d'aquesta manera, o la tecla esquerra, es mouen 10 passos

401
00:20:20,240 --> 00:20:21,710
D'aquesta manera, els passos que 10.

402
00:20:21,710 --> 00:20:23,644
M'he convertit clarament el gat en una granota.

403
00:20:23,644 --> 00:20:26,060
Així que això és just on el
vestit, com trucades de Scratch que it--

404
00:20:26,060 --> 00:20:28,440
acaba d'importar una imatge de la granota.

405
00:20:28,440 --> 00:20:29,570
>> Però el que més està succeint?

406
00:20:29,570 --> 00:20:32,794
Quines altres línies de codi,
la resta peces del trencaclosques

407
00:20:32,794 --> 00:20:35,460
Blake va fer, els nostres companys de l'ensenyament,
utilitzar en aquest programa, pel que es veu?

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

409
00:20:38,320 --> 00:20:42,730
El que està fent tot el move--
el que la programació de la construcció?

410
00:20:42,730 --> 00:20:44,950
>> Moviment, per la qual cosa el sure--
moure el bloc, segur.

411
00:20:44,950 --> 00:20:49,330
I el que és aquest bloc de moviment
A dins, més probable?

412
00:20:49,330 --> 00:20:52,850
Sí, algun tipus de bucle, potser una
sempre bloquejar, potser una repetició block--

413
00:20:52,850 --> 00:20:54,070
repetir fins que el bloc.

414
00:20:54,070 --> 00:20:57,330
I això és el que està fent els registres i
les fulles de nenúfar i tota la resta jugada

415
00:20:57,330 --> 00:20:57,990
d'aquí cap allà.

416
00:20:57,990 --> 00:21:00,270
És només succeint sense fi.

417
00:21:00,270 --> 00:21:03,180
>> Per què són alguns dels cotxes
mou més ràpid que els altres?

418
00:21:03,180 --> 00:21:06,607
El que és diferent sobre aquests programes?

419
00:21:06,607 --> 00:21:09,690
Sí, probablement alguns d'ells estan prenent
més passos alhora i algunes d'elles

420
00:21:09,690 --> 00:21:10,690
un menor nombre de passos alhora.

421
00:21:10,690 --> 00:21:14,670
I l'efecte visual
és ràpid front lent.

422
00:21:14,670 --> 00:21:16,030
>> Què creus que va passar?

423
00:21:16,030 --> 00:21:19,700
Quan vaig arribar al meu granota de tot el camí
creuar el carrer i el riu

424
00:21:19,700 --> 00:21:23,560
en el coixinet de lliri, alguna cosa
digne de menció va passar.

425
00:21:23,560 --> 00:21:26,540
Què va passar tan aviat com ho vaig fer?

426
00:21:26,540 --> 00:21:27,210
Es va aturar.

427
00:21:27,210 --> 00:21:29,680
Que la granota es va aturar, i
Tinc una segona granota.

428
00:21:29,680 --> 00:21:33,155
Llavors, quin ha de ser constructe
utilitzat allà, quina funció?

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

430
00:21:36,020 --> 00:21:38,660
>> Sí, per la qual cosa hi ha algun tipus de
"Si" condició fins allà, també.

431
00:21:38,660 --> 00:21:41,909
I resulta out-- no vam veure això-
però hi ha altres blocs en què hi ha

432
00:21:41,909 --> 00:21:45,300
es pot dir, si vostè està tocant
una altra cosa a la pantalla,

433
00:21:45,300 --> 00:21:47,720
si vostè està tocant el full de lliri, "llavors".

434
00:21:47,720 --> 00:21:50,810
I llavors és quan ens
fer aparèixer la segona granota.

435
00:21:50,810 --> 00:21:54,969
Així que tot i que aquest joc és sens dubte
molt antiquat, tot i que a primera vista

436
00:21:54,969 --> 00:21:58,010
hi ha tantes coses que passen i Blake en--
no assotar això en dos minuts,

437
00:21:58,010 --> 00:22:00,390
és probable que l'hi va portar a diversos
hores per crear aquest joc

438
00:22:00,390 --> 00:22:03,850
basat en la seva memòria o vídeos
de la versió d'antany de la mateixa.

439
00:22:03,850 --> 00:22:07,940
Però totes aquestes petites coses
va a la pantalla en forma aïllada

440
00:22:07,940 --> 00:22:11,550
es redueixen a aquests molt simple
constructs-- moviments o estats

441
00:22:11,550 --> 00:22:15,519
com hem comentat, els bucles i
condicions, i això és tot.

442
00:22:15,519 --> 00:22:17,060
Hi ha algunes altres característiques més elegants.

443
00:22:17,060 --> 00:22:19,130
Alguns d'ells són purament
estètica o acústica,

444
00:22:19,130 --> 00:22:20,964
com els sons que jo en el amb.

445
00:22:20,964 --> 00:22:23,380
Però en la seva major part, es
tenen en aquest idioma, Scratch,

446
00:22:23,380 --> 00:22:25,350
tot de la fonamental
blocs de construcció que es

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

448
00:22:29,280 --> 00:22:32,960
i qualsevol nombre d'altres idiomes.

449
00:22:32,960 --> 00:22:36,720
Una pregunta sobre el principi?

450
00:22:36,720 --> 00:22:37,220
Tot bé.

451
00:22:37,220 --> 00:22:40,303
Així que no anem a bussejar més profundament a l'alçada,
encara que de res aquest cap de setmana,

452
00:22:40,303 --> 00:22:42,860
especialment si vostè té nens o
nebots i altres,

453
00:22:42,860 --> 00:22:44,220
per introduir-los a les ratllades.

454
00:22:44,220 --> 00:22:47,960
En realitat és un meravellosament lúdic
medi ambient, amb, com diuen els seus autors,

455
00:22:47,960 --> 00:22:49,120
sostres molt alts.

456
00:22:49,120 --> 00:22:51,670
Tot i que vam començar amb
mateixos detalls de baix nivell,

457
00:22:51,670 --> 00:22:54,890
realment es pot fer una mica
amb això, i això és potser

458
00:22:54,890 --> 00:22:57,360
una demostració d'exactament això.

459
00:22:57,360 --> 00:23:02,920
>> Però ara anem transició a una mica més de
problemes sofisticats, si es vol,

460
00:23:02,920 --> 00:23:05,870
coneguda com "cerca" i
"Classificació", en termes més generals.

461
00:23:05,870 --> 00:23:09,500
Hem tingut aquest llibre de telèfon abans els vaig parlar aquí està
una altra plantilla només per discussion--

462
00:23:09,500 --> 00:23:13,460
que hem estat capaços de buscar
de manera més eficient perquè

463
00:23:13,460 --> 00:23:15,270
d'un suposat significatiu.

464
00:23:15,270 --> 00:23:17,655
I només perquè quedi clar, el
Se suposava que fer

465
00:23:17,655 --> 00:23:19,280
quan es busca a través d'aquesta guia de telèfons?

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

467
00:23:23,342 --> 00:23:25,300
Que Mike Smith estava en
la guia de telèfons, encara que

468
00:23:25,300 --> 00:23:27,410
seria capaç de gestionar
l'escenari sense ell

469
00:23:27,410 --> 00:23:30,720
allà si només es va aturar prematurament.

470
00:23:30,720 --> 00:23:31,806
El llibre és alfabètic.

471
00:23:31,806 --> 00:23:33,930
I això és un molt generós
descomptat, perquè això

472
00:23:33,930 --> 00:23:36,580
significa algú-- Sóc una mena
de tallar un cantó,

473
00:23:36,580 --> 00:23:40,580
com jo sóc més ràpid perquè algú
més va fer un munt de treball dur per a mi.

474
00:23:40,580 --> 00:23:43,120
>> Però, i si el telèfon
llibre van ser sense ordenar?

475
00:23:43,120 --> 00:23:47,050
Potser Verizon va obtenir mandrós, acaba de llançar
noms i números de tot el món allà

476
00:23:47,050 --> 00:23:50,120
potser en l'ordre en què es
signat per al servei telefònic.

477
00:23:50,120 --> 00:23:54,570
I quant de temps es em porti
trobar algú com Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1.000 telefònic pàgina book-- quants
pàgines he de mirar a través de?

479
00:23:58,160 --> 00:23:58,905
>> Tots ells.

480
00:23:58,905 --> 00:24:00,030
Ets una espècie de fora de sort.

481
00:24:00,030 --> 00:24:03,420
Literalment has de mirar cada
pàgina si la guia telefònica és només

482
00:24:03,420 --> 00:24:04,450
ordenats aleatòriament.

483
00:24:04,450 --> 00:24:06,910
Podria ser necessari sort i trobi Mike
a la primera pàgina, perquè ell

484
00:24:06,910 --> 00:24:08,826
va ser el primer client
per ordenar el servei telefònic.

485
00:24:08,826 --> 00:24:10,760
Però podria haver estat l'última, també.

486
00:24:10,760 --> 00:24:12,500
>> Així ordre aleatori no és bo.

487
00:24:12,500 --> 00:24:16,750
Així que suposem que tenim per ordenar la
directori telefònic o en dades generals espècie

488
00:24:16,750 --> 00:24:18,520
que se'ns ha donat.

489
00:24:18,520 --> 00:24:19,440
Com podem fer això?

490
00:24:19,440 --> 00:24:21,360
>> Bé, deixa només tracte
aquí un exemple senzill.

491
00:24:21,360 --> 00:24:24,290
Déjame anar endavant i llançar una
uns números al tauler.

492
00:24:24,290 --> 00:24:35,480
Suposem que els números que tenim són,
diguem, quatre, dos, un-tres.

493
00:24:35,480 --> 00:24:38,390
I, Ben, ordenar aquests números per a nosaltres.

494
00:24:38,390 --> 00:24:39,017
>> D'acord.

495
00:24:39,017 --> 00:24:39,850
Com ho has fet?

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

497
00:24:42,731 --> 00:24:43,230
Tot bé.

498
00:24:43,230 --> 00:24:44,710
Així que comença amb els més petits
el valor i la més alta,

499
00:24:44,710 --> 00:24:46,084
i això és molt bona intuïció.

500
00:24:46,084 --> 00:24:48,080
I adonar-se que
els éssers humans són en realitat bastant

501
00:24:48,080 --> 00:24:49,913
bo en la solució de problemes
d'aquesta manera, almenys

502
00:24:49,913 --> 00:24:51,810
quan les dades és relativament petit.

503
00:24:51,810 --> 00:24:54,860
Tan aviat com vostè comença a tenir centenars
de nombres, milers de nombres,

504
00:24:54,860 --> 00:24:58,440
milions de números, Ben probablement
No podria fer-ho bastant ràpid que,

505
00:24:58,440 --> 00:25:00,620
suposant que no eren
llacunes en els números.

506
00:25:00,620 --> 00:25:03,450
Bastant fàcil d'explicar fins a un milió
en cas contrari, només consumeix molt de temps.

507
00:25:03,450 --> 00:25:07,150
>> Així que l'algoritme que sona
com Ben utilitza ara

508
00:25:07,150 --> 00:25:08,930
va ser buscar el nombre més petit.

509
00:25:08,930 --> 00:25:12,900
Així que tot i que els éssers humans podem tenir
en una gran quantitat d'informació visual,

510
00:25:12,900 --> 00:25:14,830
un ordinador és en realitat
una mica més limitada.

511
00:25:14,830 --> 00:25:17,560
L'equip només pot
mirar a un byte a la vegada

512
00:25:17,560 --> 00:25:20,770
o potser quatre bytes a la vegada--
en aquests dies potser 8 bytes a la vegada--

513
00:25:20,770 --> 00:25:24,450
però un nombre molt petit
de bytes en un moment donat.

514
00:25:24,450 --> 00:25:28,480
>> Per tant, atès que realment tenim
quatre valors separats aquí--

515
00:25:28,480 --> 00:25:32,440
i que es pugui imaginar Ben com tenir
bena als ulls si fos un ordinador, com

516
00:25:32,440 --> 00:25:36,450
que ell no pot veure una altra cosa
d'un nombre a un temps--

517
00:25:36,450 --> 00:25:39,720
pel que generalment s'assumeix, com en
Anglès, llegirem de dreta a esquerra.

518
00:25:39,720 --> 00:25:42,870
Així que el primer nombre Ben probablement es veia
a era quatre i després molt ràpidament

519
00:25:42,870 --> 00:25:44,770
es van adonar que és una bastant gran
number-- m'ho dius a mi seguir buscant.

520
00:25:44,770 --> 00:25:45,357
>> Hi ha dos.

521
00:25:45,357 --> 00:25:45,940
Espera un minut.

522
00:25:45,940 --> 00:25:47,070
Dos és menor que quatre.

523
00:25:47,070 --> 00:25:47,986
Vaig a recordar.

524
00:25:47,986 --> 00:25:49,070
Dos és ara el més petit.

525
00:25:49,070 --> 00:25:50,417
Ara un-- que és fins i tot millor.

526
00:25:50,417 --> 00:25:51,250
Això és encara més petit.

527
00:25:51,250 --> 00:25:54,000
Vaig a oblidar-se de dues
i només recorda una ara.

528
00:25:54,000 --> 00:25:56,550
>> I podia deixar de mirar?

529
00:25:56,550 --> 00:25:58,360
Bé, ell podria basada
en aquesta informació,

530
00:25:58,360 --> 00:26:00,477
però serà millor que la recerca
la resta de la llista.

531
00:26:00,477 --> 00:26:02,060
Perquè el que si eren zero a la llista?

532
00:26:02,060 --> 00:26:03,643
Què passa si un fos negatiu a la llista?

533
00:26:03,643 --> 00:26:07,720
Només sap que la seva resposta
és correcte si ell és exhaustiva

534
00:26:07,720 --> 00:26:08,729
verificat la llista sencera.

535
00:26:08,729 --> 00:26:10,020
Així que ens fixem en la resta d'aquest.

536
00:26:10,020 --> 00:26:11,394
Tres-- que era una pèrdua de temps.

537
00:26:11,394 --> 00:26:13,540
Tinc mala sort, però jo estava
sent correcta per fer-ho.

538
00:26:13,540 --> 00:26:17,857
I pel que ara és de suposar
seleccionat el nombre més petit

539
00:26:17,857 --> 00:26:20,440
i només cal posar al principi
de la llista, ja que vaig a fer aquí.

540
00:26:20,440 --> 00:26:23,480
Ara ho va fer després, tot i que
que no pensa en això gairebé

541
00:26:23,480 --> 00:26:25,962
en aquesta mesura?

542
00:26:25,962 --> 00:26:27,670
Repetiu el procés,
així que algun tipus de bucle.

543
00:26:27,670 --> 00:26:28,920
Hi ha una idea familiar.

544
00:26:28,920 --> 00:26:30,860
Així que aquí és quatre.

545
00:26:30,860 --> 00:26:32,110
Això és actualment el més petit.

546
00:26:32,110 --> 00:26:33,220
Això és un candidat.

547
00:26:33,220 --> 00:26:33,900
No més.

548
00:26:33,900 --> 00:26:34,770
Ara que he vist dues.

549
00:26:34,770 --> 00:26:36,630
Aquest és el següent element més petit.

550
00:26:36,630 --> 00:26:40,800
Tres-- això no és menor, per la qual
Ara Ben pot extirpar a tots dos.

551
00:26:40,800 --> 00:26:44,510
>> I ara repetim el procés, i
per descomptat, es tira a terme tres següent.

552
00:26:44,510 --> 00:26:45,420
Repetir el procés.

553
00:26:45,420 --> 00:26:46,990
Quatre es va retirar.

554
00:26:46,990 --> 00:26:50,140
I ara que estem fora dels nombres,
de manera que la llista ha de ser ordenada.

555
00:26:50,140 --> 00:26:51,960
>> I, en efecte, es tracta d'un algoritme formal.

556
00:26:51,960 --> 00:26:56,610
Un científic de la computació faria
anomenar aquesta "ordenació per selecció"

557
00:26:56,610 --> 00:27:00,880
amb la idea d'una espècie
iteratively-- enumerar de nou

558
00:27:00,880 --> 00:27:03,807
i una altra vegada i una altra seleccionant
el nombre més petit.

559
00:27:03,807 --> 00:27:06,140
I el que és agradable sobre ell és
és tan rematadament intuïtiva.

560
00:27:06,140 --> 00:27:07,470
És tan simple.

561
00:27:07,470 --> 00:27:11,100
I es pot repetir el mateix
operació una vegada i una altra.

562
00:27:11,100 --> 00:27:12,150
És molt senzill.

563
00:27:12,150 --> 00:27:17,170
>> En aquest cas va ser ràpid, però
Quant de temps es prengui realment?

564
00:27:17,170 --> 00:27:19,880
Farem que sembli i
sentir una mica més tediós.

565
00:27:19,880 --> 00:27:24,150
Així que un, dos, tres, quatre, cinc-sis,
set, vuit, nou, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- nombre arbitrari.

567
00:27:26,160 --> 00:27:28,780
Només volia més aquest
temps de què només el quatre.

568
00:27:28,780 --> 00:27:30,780
Així que si tinc un tot
munt de nombres que ara--

569
00:27:30,780 --> 00:27:32,420
Ni tan sols importa
el que es tracti: de deixar

570
00:27:32,420 --> 00:27:34,380
pensar en el que aquesta
algoritme és molt similar.

571
00:27:34,380 --> 00:27:35,857
>> Suposem que hi ha un nombre allà.

572
00:27:35,857 --> 00:27:38,190
Un cop més, no importa el
que són, però són a l'atzar.

573
00:27:38,190 --> 00:27:39,679
Estic aplicant l'algoritme de Ben.

574
00:27:39,679 --> 00:27:41,220
Necessito seleccionar el nombre més petit.

575
00:27:41,220 --> 00:27:41,761
Què faig?

576
00:27:41,761 --> 00:27:44,240
I vaig a físicament
fer que aquest moment d'actuar cap a fora.

577
00:27:44,240 --> 00:27:46,099
Buscant, buscant,
mira, mira, mira.

578
00:27:46,099 --> 00:27:48,140
Només de moment d'arribar a
Al final de la llista es pot

579
00:27:48,140 --> 00:27:51,230
Sóc conscient dels més petits
número dos va ser aquesta vegada.

580
00:27:51,230 --> 00:27:52,720
Un no està a la llista.

581
00:27:52,720 --> 00:27:54,400
Així que vaig posar a sota 2.

582
00:27:54,400 --> 00:27:55,590
>> Què faig ara?

583
00:27:55,590 --> 00:27:58,600
Mirant, mirant, mirant, mirant.

584
00:27:58,600 --> 00:28:02,250
Ara he trobat el número set, perquè
hi ha llacunes en aquests numbers--

585
00:28:02,250 --> 00:28:03,300
però només arbitrària.

586
00:28:03,300 --> 00:28:03,800
Tot bé.

587
00:28:03,800 --> 00:28:06,030
Així que ara puc posar 07:00.

588
00:28:06,030 --> 00:28:08,860
Mirant mirant, mirant.

589
00:28:08,860 --> 00:28:11,030
>> Ara estic suposant,
Per descomptat, que Ben no

590
00:28:11,030 --> 00:28:14,780
té RAM addicional, extra
memòria, perquè, per descomptat,

591
00:28:14,780 --> 00:28:16,080
Estic mirant el mateix nombre.

592
00:28:16,080 --> 00:28:18,246
Segurament que podria haver recordat
tots aquests números,

593
00:28:18,246 --> 00:28:19,930
i això és absolutament cert.

594
00:28:19,930 --> 00:28:22,610
Però si Ben recorda tot
dels números que ha vist,

595
00:28:22,610 --> 00:28:24,430
en realitat no ha fet
avenços fonamentals

596
00:28:24,430 --> 00:28:26,170
perquè ja té
la capacitat de buscar

597
00:28:26,170 --> 00:28:27,540
a través dels nombres en el tauler.

598
00:28:27,540 --> 00:28:29,373
Recordant a tots els
els números no ajuda,

599
00:28:29,373 --> 00:28:32,490
perquè ell pot encara com un ordinador
Només mira, ho hem dit, un nombre

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

601
00:28:33,080 --> 00:28:35,760
Així que no hi ha cap tipus de trucs
aquí que pot aprofitar.

602
00:28:35,760 --> 00:28:39,170
>> Així que en realitat, com ja
seguir buscant la llista,

603
00:28:39,170 --> 00:28:44,200
Jo, literalment, tinc que acaba de seguir endavant
d'anada i tornada a través d'ell, arrencant

604
00:28:44,200 --> 00:28:45,710
el nombre immediatament inferior.

605
00:28:45,710 --> 00:28:48,810
I com es pot inferir tipus de
de les meves moviments ximples,

606
00:28:48,810 --> 00:28:50,860
Això es posa molt
tediós molt ràpidament,

607
00:28:50,860 --> 00:28:54,850
i em sembla estar anant i
endavant, enrere i endavant una mica.

608
00:28:54,850 --> 00:29:03,220
Ara, per ser justos, no he d'anar
tan, bé, anem a veure-- per ser justos,

609
00:29:03,220 --> 00:29:06,310
No he de caminar força
tants passos cada vegada.

610
00:29:06,310 --> 00:29:09,200
Perquè, és clar, com jo
seleccionar els números de la llista,

611
00:29:09,200 --> 00:29:11,860
la llista restant es fa més curt.

612
00:29:11,860 --> 00:29:14,240
>> I així pensarem
la quantitat de passos que estic realment

613
00:29:14,240 --> 00:29:16,010
penosament a través de cada vegada.

614
00:29:16,010 --> 00:29:18,950
En la primera situació
teníem 16 nombres,

615
00:29:18,950 --> 00:29:22,210
i així només anem a maximally--
fer això per un discussion--

616
00:29:22,210 --> 00:29:25,640
Havia de mirar a través de 16
números per trobar la més petita.

617
00:29:25,640 --> 00:29:28,420
Però una vegada que vaig arrencar
el nombre més petit, com

618
00:29:28,420 --> 00:29:30,590
sempre va ser la llista restant, per descomptat?

619
00:29:30,590 --> 00:29:31,420
Només 15.

620
00:29:31,420 --> 00:29:34,670
Llavors, quants nombres de Ben va fer o que tenen
per mirar a través de la segona vegada?

621
00:29:34,670 --> 00:29:36,832
15, només per anar a buscar els més petits.

622
00:29:36,832 --> 00:29:39,540
Però ara, per descomptat, la llista és,
també, més petita del que era abans.

623
00:29:39,540 --> 00:29:42,540
Llavors, com ho van fer molts passos
ha de prendre la propera vegada?

624
00:29:42,540 --> 00:29:49,970
14 i després 13 i després 12, més punt,
punt, punt, fins que em quedo amb un de sol.

625
00:29:49,970 --> 00:29:53,146
Així que ara ho faria un científic de la computació
preguntar, bé, el que fa que tots iguals?

626
00:29:53,146 --> 00:29:55,770
En realitat, és igual a poc de concret
nombre que sens dubte podríem

627
00:29:55,770 --> 00:30:00,490
fem aritmèticament, però volem parlar
sobre l'eficiència dels algoritmes

628
00:30:00,490 --> 00:30:04,940
una mica més formulaically,
independent de la durada de la llista és.

629
00:30:04,940 --> 00:30:06,240
>> I perquè sàpiga què?

630
00:30:06,240 --> 00:30:09,860
Això és 16, però com he dit abans,
Anem a cridar la mida del problema

631
00:30:09,860 --> 00:30:10,970
n, on n és un nombre.

632
00:30:10,970 --> 00:30:13,220
Potser sigui 16, potser és
3, potser és un milió.

633
00:30:13,220 --> 00:30:13,761
No ho sé.

634
00:30:13,761 --> 00:30:14,390
No m'importa.

635
00:30:14,390 --> 00:30:16,520
El que realment vull és
una fórmula que pugui

636
00:30:16,520 --> 00:30:19,420
utilitzar per comparar aquest algoritme
contra altres algoritmes

637
00:30:19,420 --> 00:30:22,350
que algú podria reclamar
són millors o pitjors.

638
00:30:22,350 --> 00:30:25,430
>> Així que resulta, i només jo
saber això des de l'escola primària,

639
00:30:25,430 --> 00:30:34,790
que això realment funciona a la mateixa
cosa com n sobre núm més un més de dos.

640
00:30:34,790 --> 00:30:40,020
I això passa a ser igual, de
Per descomptat, n al quadrat més n més de dos.

641
00:30:40,020 --> 00:30:43,250
Així que si volia una fórmula
De quants passos

642
00:30:43,250 --> 00:30:46,330
van participar en l'estudi de tots
d'aquests números una i altra vegada

643
00:30:46,330 --> 00:30:52,681
i una altra vegada i una altra, jo diria
que està n al quadrat més n més de dos.

644
00:30:52,681 --> 00:30:53,430
Però saps què?

645
00:30:53,430 --> 00:30:54,500
Això només es veu desordenat.

646
00:30:54,500 --> 00:30:56,470
Jo realment vull una
sentit general de les coses.

647
00:30:56,470 --> 00:30:58,810
I es pot recordar de
l'escola secundària que hi ha

648
00:30:58,810 --> 00:31:00,660
és la noció de terme més alt ordre.

649
00:31:00,660 --> 00:31:05,300
Quin d'aquests termes, el núm
quadrat, el n, o la meitat,

650
00:31:05,300 --> 00:31:07,550
té el major impacte en el temps?

651
00:31:07,550 --> 00:31:11,920
Com més gran n aconsegueix, que
d'aquests assumptes més?

652
00:31:11,920 --> 00:31:15,560
>> En altres paraules, si el connecto
en un milió, n al quadrat

653
00:31:15,560 --> 00:31:17,900
serà més probable
el factor dominant,

654
00:31:17,900 --> 00:31:21,670
perquè un milió de vegades
en si és molt més gran

655
00:31:21,670 --> 00:31:23,682
que més un addicional milions.

656
00:31:23,682 --> 00:31:24,390
Així que ja saben què?

657
00:31:24,390 --> 00:31:27,305
Aquest és un donaran tan gran
nombre si s'eleva al quadrat un nombre.

658
00:31:27,305 --> 00:31:28,430
Això en realitat no importa.

659
00:31:28,430 --> 00:31:30,596
Només anem creu que
i oblidar-se'n.

660
00:31:30,596 --> 00:31:34,250
I pel que un científic de la computació diria
que l'eficàcia d'aquest algoritme

661
00:31:34,250 --> 00:31:37,850
és de l'ordre de n squared--
Em refereixo a realment una aproximació.

662
00:31:37,850 --> 00:31:40,810
És una espècie de més o menys n al quadrat.

663
00:31:40,810 --> 00:31:44,130
Amb el temps, com més gran
i més gran que n es fa, això

664
00:31:44,130 --> 00:31:47,610
és una bona estimació del que el
l'eficiència o la manca d'eficiència

665
00:31:47,610 --> 00:31:49,400
d'aquest algoritme és en realitat.

666
00:31:49,400 --> 00:31:52,040
I va derivar que, per descomptat,
pel que fa a realitzar els càlculs.

667
00:31:52,040 --> 00:31:54,040
Però ara només estic agitant
les meves mans, perquè acabo

668
00:31:54,040 --> 00:31:55,790
desitjar un sentit general d'aquest algoritme.

669
00:31:55,790 --> 00:31:58,850
>> Així, utilitzant la mateixa lògica, per la seva banda,
considerarem un altre algoritme

670
00:31:58,850 --> 00:32:01,162
ja trobem at-- cerca lineal.

671
00:32:01,162 --> 00:32:02,870
Quan jo estava buscant
per a la book-- telèfon

672
00:32:02,870 --> 00:32:05,980
No arreglármelo, buscant
a través de la book-- telèfon

673
00:32:05,980 --> 00:32:09,197
vam mantenir dient que era
1.000 passos, o 500 passos.

674
00:32:09,197 --> 00:32:10,280
Però anem a generalitzar això.

675
00:32:10,280 --> 00:32:12,860
Si hi ha n pàgines en
la guia de telèfons, el que és

676
00:32:12,860 --> 00:32:17,250
el temps d'execució o la
eficiència de cerca lineal?

677
00:32:17,250 --> 00:32:19,750
És de l'ordre de
la quantitat de passos per trobar

678
00:32:19,750 --> 00:32:24,210
Mike Smith mitjançant la recerca lineal, la
primer algoritme, o fins i tot el segon?

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

680
00:32:27,240 --> 00:32:31,710
>> En el pitjor dels casos, Mike
està a l'extrem del llibre.

681
00:32:31,710 --> 00:32:35,590
Així que si el directori té 1.000 pàgines,
vam dir l'última vegada, en el pitjor dels casos,

682
00:32:35,590 --> 00:32:38,380
que podria prendre la forma més o menys
moltes pàgines per trobar Mike?

683
00:32:38,380 --> 00:32:38,990
Igual que 1,000.

684
00:32:38,990 --> 00:32:39,830
És un límit superior.

685
00:32:39,830 --> 00:32:41,790
És una pitjor situació possible.

686
00:32:41,790 --> 00:32:44,410
Però, de nou, ens estem allunyant
de 1.000 números com ara.

687
00:32:44,410 --> 00:32:45,730
És només n.

688
00:32:45,730 --> 00:32:47,470
>> Quina és la conclusió lògica?

689
00:32:47,470 --> 00:32:50,210
Trobar Mike en un telèfon
llibre que té n pàgines

690
00:32:50,210 --> 00:32:55,280
podria portar, en el pitjor dels casos,
el nombre de passos en l'ordre dels n?

691
00:32:55,280 --> 00:32:58,110
I de fet un ordinador
científic diria

692
00:32:58,110 --> 00:33:02,340
que el temps d'execució, o la
rendiment o l'eficiència

693
00:33:02,340 --> 00:33:07,470
o ineficiència, d'un algoritme com
una recerca lineal és de l'ordre de n.

694
00:33:07,470 --> 00:33:10,010
I podem aplicar el mateix
lògica de creuar alguna cosa fora

695
00:33:10,010 --> 00:33:13,170
com acabo de fer a la segona
algoritme que vam tenir amb la guia telefònica,

696
00:33:13,170 --> 00:33:16,040
on vam ser dues pàgines alhora.

697
00:33:16,040 --> 00:33:20,120
>> Així 1,000 pàgina de la guia telefònica podria
portar-nos a 500 voltes de pàgina, més un

698
00:33:20,120 --> 00:33:21,910
si doblem una mica cap enrere.

699
00:33:21,910 --> 00:33:26,590
Així que si un directori té n pàgines, però
que estem fent dues pàgines alhora,

700
00:33:26,590 --> 00:33:28,900
que és més o menys què?

701
00:33:28,900 --> 00:33:33,190
N més de dos, pel que és com n més de dos.

702
00:33:33,190 --> 00:33:38,490
Però vaig fer el reclam d'una
Fa moment en què n sobre dos--

703
00:33:38,490 --> 00:33:41,060
això és una mica el mateix que acaba de n.

704
00:33:41,060 --> 00:33:44,050
És només un factor constant,
els informàtics dirien.

705
00:33:44,050 --> 00:33:45,970
Anem només se centren en
les variables, realmente--

706
00:33:45,970 --> 00:33:47,780
els majors variables en l'equació.

707
00:33:47,780 --> 00:33:52,530
>> recerca de manera lineal, ja es faci una
pàgina alhora o dues pàgines alhora,

708
00:33:52,530 --> 00:33:54,810
és una espècie de fonamentalment els mateixos.

709
00:33:54,810 --> 00:33:56,880
Encara és de l'ordre de n.

710
00:33:56,880 --> 00:34:01,930
Però jo deia amb el meu quadre anterior
que la tercera algorisme no era

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

712
00:34:02,480 --> 00:34:03,605
No era una línia recta.

713
00:34:03,605 --> 00:34:08,659
Va ser aquesta línia corba, i la
fórmula algebraica no hi havia què?

714
00:34:08,659 --> 00:34:11,812
Registre de n- tan logaritme en base dues de n.

715
00:34:11,812 --> 00:34:14,520
I no hem d'entrar en massa
molts detalls sobre els logaritmes d'avui,

716
00:34:14,520 --> 00:34:17,394
però la majoria dels informàtics no ho faria
fins i tot li dirà el que és la base.

717
00:34:17,394 --> 00:34:20,639
A causa de que tot és només
factors constants, per així dir-ho,

718
00:34:20,639 --> 00:34:22,659
només lleugeres diferències numèriques.

719
00:34:22,659 --> 00:34:31,179
I així, aquesta seria una molt comuns
camí per ordinador particular formals

720
00:34:31,179 --> 00:34:33,949
els científics en una junta o
programadors en un tauler blanc

721
00:34:33,949 --> 00:34:36,889
En realitat l'argument dels quals
algoritme que usarien

722
00:34:36,889 --> 00:34:39,500
o el que l'eficiència
de la seva algoritme és.

723
00:34:39,500 --> 00:34:42,960
>> I això no és necessàriament una cosa
es discuteix en gran detall,

724
00:34:42,960 --> 00:34:47,889
però un bon programador és algú
que té un fons sòlid i formal.

725
00:34:47,889 --> 00:34:50,120
Ell és capaç de parlar amb
que en aquest tipus de camí

726
00:34:50,120 --> 00:34:53,350
i fer de
arguments qualitatius com

727
00:34:53,350 --> 00:34:56,870
de per què un algoritme o
una peça de programari

728
00:34:56,870 --> 00:35:00,165
és superior en alguna forma a una altra.

729
00:35:00,165 --> 00:35:02,540
A causa de que certament es podria
n'hi ha prou amb executar el programa d'una persona

730
00:35:02,540 --> 00:35:04,980
i comptar el nombre de segons
que es necessita per solucionar alguns nombres,

731
00:35:04,980 --> 00:35:06,710
i es pot executar alguns
El programa d'una altra persona

732
00:35:06,710 --> 00:35:08,418
i comptar el nombre de
de segons que triga.

733
00:35:08,418 --> 00:35:12,840
Però aquesta és una manera més general que
es pot utilitzar per analitzar els algoritmes,

734
00:35:12,840 --> 00:35:15,520
si es vol, només en
paper o només verbalment.

735
00:35:15,520 --> 00:35:18,430
Sense ni tan sols executar-lo, sense
fins i tot tractant d'entrades de mostra,

736
00:35:18,430 --> 00:35:20,180
només pot raonar a través d'ell.

737
00:35:20,180 --> 00:35:24,670
I així, amb la contractació d'un desenvolupador o si
que ell o ella una mena de discutir amb vostè

738
00:35:24,670 --> 00:35:28,460
Per això el seu algoritme, el seu secret
salsa per buscar milers de milions

739
00:35:28,460 --> 00:35:30,580
de pàgines web per al seu
empresa és millor, aquests

740
00:35:30,580 --> 00:35:33,302
són els tipus d'arguments que
idealment hauria de ser capaç de fer.

741
00:35:33,302 --> 00:35:35,010
O, almenys, aquests són
el tipus de coses

742
00:35:35,010 --> 00:35:40,211
que hauria sorgit en la discussió, en
menys en una discussió molt formal.

743
00:35:40,211 --> 00:35:40,710
Tot bé.

744
00:35:40,710 --> 00:35:44,400
Així Ben proposar alguna cosa
anomenada ordenació per selecció.

745
00:35:44,400 --> 00:35:48,200
Però vaig a proposar que hi ha
altres maneres de fer això, també.

746
00:35:48,200 --> 00:35:50,400
El que no m'agrada molt
sobre l'algoritme de Ben

747
00:35:50,400 --> 00:35:54,400
és que ell va seguir caminant, o
havent a caminar, d'anada i tornada

748
00:35:54,400 --> 00:35:56,930
i d'anada i tornada i d'anada i tornada.

749
00:35:56,930 --> 00:36:04,130
¿I si en comptes hagués de fer
alguna cosa així com aquests números aquí

750
00:36:04,130 --> 00:36:08,200
i hagués de bregar només amb cadascun
nombre al seu torn que a mi es dóna?

751
00:36:08,200 --> 00:36:10,780
>> En altres paraules, aquí està
la meva llista de nombres.

752
00:36:10,780 --> 00:36:12,944
Quatre, un, tres, dos.

753
00:36:12,944 --> 00:36:14,360
I vaig a fer el següent.

754
00:36:14,360 --> 00:36:17,230
Vaig a inserir els números
a la qual pertanyen més aviat

755
00:36:17,230 --> 00:36:18,980
que seleccionant-les una a la vegada.

756
00:36:18,980 --> 00:36:20,820
En altres paraules, aquest és el número quatre.

757
00:36:20,820 --> 00:36:22,430
>> Aquí està la meva llista original.

758
00:36:22,430 --> 00:36:25,290
I vaig a mantenir
essencialment una nova llista aquí.

759
00:36:25,290 --> 00:36:26,710
Així que aquesta és la llista d'edat.

760
00:36:26,710 --> 00:36:28,560
Aquesta és la llista nova.

761
00:36:28,560 --> 00:36:30,220
Veig el número quatre en primer lloc.

762
00:36:30,220 --> 00:36:34,500
La meva nova llista està buida inicialment,
pel que és trivial el cas

763
00:36:34,500 --> 00:36:36,410
què quatre està ara llista variats.

764
00:36:36,410 --> 00:36:39,560
Només estic prenent el número que em donen,
i ho estic posant en la meva nova llista.

765
00:36:39,560 --> 00:36:41,460
>> S'ordena aquesta nova llista?

766
00:36:41,460 --> 00:36:41,990
Sí.

767
00:36:41,990 --> 00:36:45,090
És estúpid perquè només hi ha una
element, però és absolutament ordenada.

768
00:36:45,090 --> 00:36:46,390
No hi ha res fora de lloc.

769
00:36:46,390 --> 00:36:49,290
És més interessant, aquest algoritme,
quan moc a la següent etapa.

770
00:36:49,290 --> 00:36:50,550
>> Ara tinc un.

771
00:36:50,550 --> 00:36:55,430
Així que, per descomptat, pertany a la
principi o al final d'aquesta nova llista?

772
00:36:55,430 --> 00:36:56,360
El començament.

773
00:36:56,360 --> 00:36:58,530
Així que he de fer un treball ara.

774
00:36:58,530 --> 00:37:01,410
He estat prenent alguns
llibertats amb el meu marcador

775
00:37:01,410 --> 00:37:03,120
amb només dibuixar coses
on els vull,

776
00:37:03,120 --> 00:37:05,320
però això no és realment
exacta en un ordinador.

777
00:37:05,320 --> 00:37:08,530
Un equip que, com se sap, té
RAM, o memòria d'accés aleatori,

778
00:37:08,530 --> 00:37:12,411
i això és un byte i
un altre byte i un altre byte.

779
00:37:12,411 --> 00:37:14,910
I si té un gigabyte de
RAM, que té mil milions de bytes,

780
00:37:14,910 --> 00:37:16,680
però estan físicament en un sol lloc.

781
00:37:16,680 --> 00:37:19,540
No es pot simplement moure coses d'una banda
dibuixant a la pissarra

782
00:37:19,540 --> 00:37:20,750
on vulguis.

783
00:37:20,750 --> 00:37:24,090
Així que si la meva nova llista té
quatre ubicacions a la memòria,

784
00:37:24,090 --> 00:37:27,480
per desgràcia, el quatre és
Ja en el lloc equivocat.

785
00:37:27,480 --> 00:37:30,410
>> Així que per inserir el número u
No puc dibuixar aquí.

786
00:37:30,410 --> 00:37:31,901
Aquesta posició de memòria no existeix.

787
00:37:31,901 --> 00:37:35,150
Això seria fer trampa, i han estat
trampa pictòricament durant uns minuts

788
00:37:35,150 --> 00:37:35,800
aquí.

789
00:37:35,800 --> 00:37:40,950
Així que en realitat, si jo vull posar un aquí,
He de copiar temporalment els quatre

790
00:37:40,950 --> 00:37:43,030
i després posar l'un allà.

791
00:37:43,030 --> 00:37:45,500
>> Això està bé, això és correcte,
això és tècnicament possible,

792
00:37:45,500 --> 00:37:48,410
però s'adonen que és una feina extra.

793
00:37:48,410 --> 00:37:50,460
Jo no només cal posar el nombre al seu lloc.

794
00:37:50,460 --> 00:37:53,026
La primera vegada que vaig haver de moure una
nombre, a continuació, posar al seu lloc,

795
00:37:53,026 --> 00:37:54,650
així que tipus de vaig doblegar el meu quantitat de treball.

796
00:37:54,650 --> 00:37:55,660
Així que vés amb això en compte.

797
00:37:55,660 --> 00:37:57,120
>> Però ara estic fet amb aquest element.

798
00:37:57,120 --> 00:37:59,056
Ara vull agafar el número tres.

799
00:37:59,056 --> 00:38:00,430
On, per descomptat, pertany?

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

801
00:38:01,480 --> 00:38:03,650
No puc enganyar més
i només cal posar-hi,

802
00:38:03,650 --> 00:38:06,770
perquè, de nou, aquesta memòria
està en ubicacions físiques.

803
00:38:06,770 --> 00:38:10,900
Així que he de copiar els quatre
i posar el tres per aquí.

804
00:38:10,900 --> 00:38:11,550
No és gran cosa.

805
00:38:11,550 --> 00:38:14,610
És només un pas addicional
nou-- se sent molt barat.

806
00:38:14,610 --> 00:38:16,445
>> Però ara de passar a tots dos.

807
00:38:16,445 --> 00:38:17,820
Els dos, per descomptat, pertany aquí.

808
00:38:17,820 --> 00:38:20,990
Ara es comença a veure com
el treball pot acumular-se.

809
00:38:20,990 --> 00:38:23,520
Ara, què he de fer?

810
00:38:23,520 --> 00:38:28,570
Sí, he de moure els quatre,
llavors he de copiar els tres,

811
00:38:28,570 --> 00:38:31,200
i ara puc portar en ambdues.

812
00:38:31,200 --> 00:38:34,460
I la captura amb aquest
algoritme, curiosament,

813
00:38:34,460 --> 00:38:41,050
és que suposem que tenim una manera més extrema
cas en el qual és diguem vuit, set,

814
00:38:41,050 --> 00:38:45,150
sis, cinc, quatre, tres, dos, un.

815
00:38:45,150 --> 00:38:49,450
Això és, en molts contextos,
el pitjor dels casos,

816
00:38:49,450 --> 00:38:51,570
perquè la maleïda cosa
és literalment cap enrere.

817
00:38:51,570 --> 00:38:53,670
>> En realitat no
afectarà algoritme de Ben,

818
00:38:53,670 --> 00:38:55,940
perquè en la selecció de Ben
espècie que va a mantenir

819
00:38:55,940 --> 00:38:58,359
anar amunt i avall per la llista.

820
00:38:58,359 --> 00:39:01,150
I pel fet que estava sempre a la recerca
a través de tota la llista restant,

821
00:39:01,150 --> 00:39:02,858
no importa
on els elements són.

822
00:39:02,858 --> 00:39:05,630
Però en aquest cas amb la meva inserció
approach-- anem a provar això.

823
00:39:05,630 --> 00:39:08,616
>> Així que un, dos, tres, quatre,
cinc, sis, set, vuit.

824
00:39:08,616 --> 00:39:11,630
Un dos tres quatre,
cinc, sis, set, vuit.

825
00:39:11,630 --> 00:39:14,320
Vaig a prendre el vuit,
i on ho poso?

826
00:39:14,320 --> 00:39:17,260
Bé, al principi de la llista,
ja que aquesta nova llista està ordenada.

827
00:39:17,260 --> 00:39:18,760
I creuo cap a fora.

828
00:39:18,760 --> 00:39:20,551
>> On poso els set?

829
00:39:20,551 --> 00:39:21,050
Maleïda sigui.

830
00:39:21,050 --> 00:39:23,174
Ha d'anar-hi, per la qual
He de fer algunes còpies.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
I ara els set va aquí.

833
00:39:28,480 --> 00:39:29,860
Ara de passar als sis.

834
00:39:29,860 --> 00:39:30,980
Ara és encara més feina.

835
00:39:30,980 --> 00:39:32,570
>> La vuitena ha d'anar aquí.

836
00:39:32,570 --> 00:39:33,920
Set ha d'anar aquí.

837
00:39:33,920 --> 00:39:35,450
Ara el 6 poden anar aquí.

838
00:39:35,450 --> 00:39:37,950
Ara m'agafa el cinc.

839
00:39:37,950 --> 00:39:40,560
Ara els vuit ha d'anar
aquí, set ha d'anar aquí,

840
00:39:40,560 --> 00:39:43,650
6 ha d'anar aquí, i
Ara els cinc i repetir.

841
00:39:43,650 --> 00:39:46,610
I estic més o menys
movent constantment.

842
00:39:46,610 --> 00:39:52,950
>> Així que al final, això anem a algorithm--
cridar inserció sort-- realitat

843
00:39:52,950 --> 00:39:55,020
té un munt de treball, també.

844
00:39:55,020 --> 00:39:56,970
És simplement diferent
tipus de treball que Ben.

845
00:39:56,970 --> 00:40:00,090
El treball de Ben m'havia torno
d'anada i tornada tot el temps,

846
00:40:00,090 --> 00:40:03,510
la selecció de la següent més petita
element i una altra.

847
00:40:03,510 --> 00:40:06,660
Pel que era aquest tipus molt visual de l'obra.

848
00:40:06,660 --> 00:40:10,600
>> Aquest altre algoritme, que encara està
correct-- que aconseguirà la feina done--

849
00:40:10,600 --> 00:40:12,800
Només canvia la quantitat de treball.

850
00:40:12,800 --> 00:40:15,420
Sembla que inicialment ets
l'estalvi, perquè estàs sol

851
00:40:15,420 --> 00:40:19,190
tractar amb cada element
a la bestreta sense haver de caminar tot

852
00:40:19,190 --> 00:40:20,930
el camí a través de la llista com Ben era.

853
00:40:20,930 --> 00:40:25,300
Però el problema és, sobretot en aquests
boges casos en què és tot a l'inrevés,

854
00:40:25,300 --> 00:40:27,830
ets només una mica
posposar el treball dur

855
00:40:27,830 --> 00:40:30,360
fins que hagi de corregir els seus errors.

856
00:40:30,360 --> 00:40:33,919
>> I pel que si es pot imaginar això
08:07-sis i cinc

857
00:40:33,919 --> 00:40:36,710
i més tard de quatre i 03:02
moure el seu camí a través de la llista,

858
00:40:36,710 --> 00:40:39,060
que acaba de canviar el
tipus de treball que estem fent.

859
00:40:39,060 --> 00:40:42,340
En lloc de fer-ho al
a partir del meu iteració,

860
00:40:42,340 --> 00:40:45,250
Només estic fent en el
final de cada iteració.

861
00:40:45,250 --> 00:40:50,550
Així que resulta que aquest algorisme,
també, generalment es diu ordenació per inserció,

862
00:40:50,550 --> 00:40:52,190
També està en l'ordre de n al quadrat.

863
00:40:52,190 --> 00:40:56,480
En realitat no és millor,
no són millors per a tothom.

864
00:40:56,480 --> 00:41:00,810
>> No obstant això, hi ha un tercer enfocament
Jo ens animaria a considerar,

865
00:41:00,810 --> 00:41:02,970
que és això.

866
00:41:02,970 --> 00:41:07,850
Així que suposo que la meva llista, per simplicitat
de nou, és de quatre, un, tres,

867
00:41:07,850 --> 00:41:11,080
dos-- només quatre números.

868
00:41:11,080 --> 00:41:13,300
Ben tenia bona intuïció,
bona intuïció humana

869
00:41:13,300 --> 00:41:16,340
abans, pel qual es va fixar la totalitat
eventually-- llista d'ordenació per inserció.

870
00:41:16,340 --> 00:41:18,020
Jo ens engatusé llarg.

871
00:41:18,020 --> 00:41:22,530
Però considerarem la
forma més senzilla de solucionar aquesta llista.

872
00:41:22,530 --> 00:41:24,110
>> Aquesta llista no està ordenada.

873
00:41:24,110 --> 00:41:26,130
Per què?

874
00:41:26,130 --> 00:41:31,920
En Anglès, explicar per què
En realitat no és ordenada.

875
00:41:31,920 --> 00:41:33,400
Què vol dir que ser resolt?

876
00:41:33,400 --> 00:41:34,220
>> ESTUDIANT: No és seqüencial.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Malan: no seqüencial.

878
00:41:34,990 --> 00:41:35,822
Dóna'm un exemple.

879
00:41:35,822 --> 00:41:37,180
>> ESTUDIANT: Posar en ordre.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Malan: OK.

881
00:41:37,440 --> 00:41:38,790
Dóna'm un exemple més específic.

882
00:41:38,790 --> 00:41:39,832
>> ESTUDIANT: ordre ascendent.

883
00:41:39,832 --> 00:41:41,206
DAVID Malan: fi de no ascendir.

884
00:41:41,206 --> 00:41:42,100
Ser més precisos.

885
00:41:42,100 --> 00:41:45,190
No sé què vol dir amb ascendent.

886
00:41:45,190 --> 00:41:47,150
Que passa?

887
00:41:47,150 --> 00:41:49,930
>> ESTUDIANT: El més petit de la
números no és en el primer espai.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Malan: nombre més petit de
no en el primer espai.

889
00:41:51,140 --> 00:41:52,120
Ser més específic.

890
00:41:52,120 --> 00:41:55,000
Estic començant a fer-se popular.

891
00:41:55,000 --> 00:41:59,470
Estem comptant, però
el que està fora d'aquí?

892
00:41:59,470 --> 00:42:00,707
>> ESTUDIANT: seqüència numèrica.

893
00:42:00,707 --> 00:42:02,040
DAVID Malan: seqüència numèrica.

894
00:42:02,040 --> 00:42:04,248
tipus de manteniment de tot el món
que aquí-- nivell molt alt.

895
00:42:04,248 --> 00:42:07,450
Només literalment, digues-me el que és
malament com ho faria una-cinc anys d'edat.

896
00:42:07,450 --> 00:42:08,310
>> ESTUDIANT: més un.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Malan: Què és això?

898
00:42:08,750 --> 00:42:09,610
>> ESTUDIANT: més un.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Malan: Què vol dir que un més?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Dóna'm una diferent de cinc anys d'edat.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Què passa, mama?

904
00:42:18,330 --> 00:42:19,940
Què passa, pare?

905
00:42:19,940 --> 00:42:22,808
Què vol dir això no està ordenada?

906
00:42:22,808 --> 00:42:24,370
>> ESTUDIANT: No és el lloc correcte.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Malan: Quin és
no en el lloc correcte?

908
00:42:25,580 --> 00:42:26,174
>> ESTUDIANT: Quatre.

909
00:42:26,174 --> 00:42:27,090
DAVID Malan: OK, bo.

910
00:42:27,090 --> 00:42:29,110
Així que 4 no és on ha d'estar.

911
00:42:29,110 --> 00:42:30,590
En particular, és això correcte?

912
00:42:30,590 --> 00:42:33,000
Quatre i un, el primer
dos nombres que veig.

913
00:42:33,000 --> 00:42:34,930
¿Això és correcte?

914
00:42:34,930 --> 00:42:36,427
No, estan fora d'ordre, oi?

915
00:42:36,427 --> 00:42:38,135
De fet, pensa ara
sobre un equip, també.

916
00:42:38,135 --> 00:42:40,824
Només pot mirar potser un,
potser dues coses a la vegada--

917
00:42:40,824 --> 00:42:43,240
i en realitat només una cosa
alhora, però almenys pot

918
00:42:43,240 --> 00:42:45,790
mirar a una cosa, llavors el
El següent que just al costat d'ella.

919
00:42:45,790 --> 00:42:47,380
>> Així són aquests per tal?

920
00:42:47,380 --> 00:42:48,032
Esclar que no.

921
00:42:48,032 --> 00:42:48,740
Així que ja saben què?

922
00:42:48,740 --> 00:42:51,020
Per què no prenem nadó
etapes de fixació d'aquest problema

923
00:42:51,020 --> 00:42:53,410
en lloc de fer aquests de luxe
algoritmes com Ben, on

924
00:42:53,410 --> 00:42:56,440
És una espècie de fixació per
bucle a través de la llista

925
00:42:56,440 --> 00:42:59,670
en comptes de fer el que vaig fer, on
Jo només tipus de fix que a mesura que avancem?

926
00:42:59,670 --> 00:43:03,650
Anem a trencar, literalment, per la
noció d'ordre numèric order--,

927
00:43:03,650 --> 00:43:06,990
cridar el que want--
en aquestes comparacions per parells.

928
00:43:06,990 --> 00:43:07,590
>> Quatre i un.

929
00:43:07,590 --> 00:43:09,970
És aquest l'ordre correcte?

930
00:43:09,970 --> 00:43:11,310
Així que arreglarem això.

931
00:43:11,310 --> 00:43:14,700
Un i quatre, i després
només haurem de copiem.

932
00:43:14,700 --> 00:43:15,560
Molt bé, molt bé.

933
00:43:15,560 --> 00:43:17,022
Em fixo 01:04.

934
00:43:17,022 --> 00:43:18,320
Tres i dos?

935
00:43:18,320 --> 00:43:18,820
No.

936
00:43:18,820 --> 00:43:21,690
Que les meves paraules coincideixin amb els dits.

937
00:43:21,690 --> 00:43:23,695
Quatre i tres?

938
00:43:23,695 --> 00:43:27,930
>> No és la fi, així que vaig
fer un, tres, quatre, dos.

939
00:43:27,930 --> 00:43:28,680
D'acord.

940
00:43:28,680 --> 00:43:32,310
Ara 04:02?

941
00:43:32,310 --> 00:43:33,370
Hem d'arreglar això, també.

942
00:43:33,370 --> 00:43:36,700
Així que un, tres, dos, quatre.

943
00:43:36,700 --> 00:43:39,820
Així li ho va arreglar?

944
00:43:39,820 --> 00:43:43,170
No, però és el més a prop ordenats?

945
00:43:43,170 --> 00:43:48,930
>> És, doncs hem arreglat aquest
error, hem arreglat aquest error,

946
00:43:48,930 --> 00:43:50,370
i hem arreglat aquest error.

947
00:43:50,370 --> 00:43:52,420
Així que podria dir-se que ho van arreglar tres errors.

948
00:43:52,420 --> 00:43:58,100
Encara en realitat no mirar ordenada, però
és objectivament més a prop ordenada

949
00:43:58,100 --> 00:44:00,080
perquè hem arreglat alguns d'aquests errors.

950
00:44:00,080 --> 00:44:02,047
>> Ara, què faig ara?

951
00:44:02,047 --> 00:44:03,630
Jo com que va arribar al final de la llista.

952
00:44:03,630 --> 00:44:05,680
Em semblava haver fixat
tots els errors, però no.

953
00:44:05,680 --> 00:44:08,510
Perquè en aquest cas, alguns números
podria haver bombollejava més a prop

954
00:44:08,510 --> 00:44:10,410
a altres nombres que
encara estan fora de servei.

955
00:44:10,410 --> 00:44:12,951
Així que anem a fer-ho de nou, i vaig a
només ho fan en el seu lloc aquesta vegada.

956
00:44:12,951 --> 00:44:14,170
Un i tres?

957
00:44:14,170 --> 00:44:14,720
Està bé.

958
00:44:14,720 --> 00:44:16,070
Tres i dos?

959
00:44:16,070 --> 00:44:17,560
Per descomptat que no, així que anem a canviar.

960
00:44:17,560 --> 00:44:19,160
Així que dos, tres.

961
00:44:19,160 --> 00:44:21,340
Tres i quatre?

962
00:44:21,340 --> 00:44:24,370
I ara serem
particularment pedant aquí.

963
00:44:24,370 --> 00:44:26,350
L'hi va arreglar?

964
00:44:26,350 --> 00:44:29,280
Vostè sap que és l'ésser humà ordenades.

965
00:44:29,280 --> 00:44:30,400
>> Hauria intentar-ho de nou.

966
00:44:30,400 --> 00:44:31,900
Així que Olivia està proposant ho intento de nou.

967
00:44:31,900 --> 00:44:32,530
Per què?

968
00:44:32,530 --> 00:44:35,810
A causa de que un equip no té
el luxe dels ulls humans

969
00:44:35,810 --> 00:44:38,080
de simplement fent una ullada esquena; OK, he acabat.

970
00:44:38,080 --> 00:44:41,610
Com determina l'equip
que la llista està ordenada ara?

971
00:44:41,610 --> 00:44:44,590
Mecànicament.

972
00:44:44,590 --> 00:44:47,650
>> Hauria d'anar a través
una vegada més, i només si

973
00:44:47,650 --> 00:44:51,190
No fer / algun comentari sobre errors puc
llavors la conclusió que l'equip, sip,

974
00:44:51,190 --> 00:44:51,980
som bons per anar.

975
00:44:51,980 --> 00:44:54,850
Així ui dos, dos i
3, tres i quatre.

976
00:44:54,850 --> 00:44:58,030
Ara definitivament puc dir que és
ordenats, perquè he fet cap canvi.

977
00:44:58,030 --> 00:45:01,940
Ara bé, seria un error i just
ximple si jo, l'equip,

978
00:45:01,940 --> 00:45:05,640
fet aquestes mateixes preguntes 1
esperant respostes diferents.

979
00:45:05,640 --> 00:45:07,110
no hauria de succeir.

980
00:45:07,110 --> 00:45:08,600
>> I pel que ara s'ordena la llista.

981
00:45:08,600 --> 00:45:12,630
Desafortunadament, el temps de funcionament de
aquest algoritme és n al quadrat.

982
00:45:12,630 --> 00:45:13,130
Per què?

983
00:45:13,130 --> 00:45:19,520
A causa que té un nombre n, i al
pitjor dels casos s'ha de moure un nombre n

984
00:45:19,520 --> 00:45:23,637
n vegades perquè cal seguir endavant
tornar a comprovar i corregir potencialment

985
00:45:23,637 --> 00:45:24,220
aquests nombres.

986
00:45:24,220 --> 00:45:26,280
I podem fer un major
anàlisi formal, també.

987
00:45:26,280 --> 00:45:29,530
>> Així que això és tot el que dir que hem pres
3 enfocaments diferents, un

988
00:45:29,530 --> 00:45:32,210
d'ells immediatament intuïtiva
del pal de Ben

989
00:45:32,210 --> 00:45:35,170
al meu s'ha suggerit,
ordenar a aquesta

990
00:45:35,170 --> 00:45:38,540
on tipus d'perd de vista
el bosc pels arbres inicialment.

991
00:45:38,540 --> 00:45:41,760
Però llavors, si vostè pren un pas enrere,
voilà, hem fixat la noció de classificació.

992
00:45:41,760 --> 00:45:43,824
Així que això és, s'atreveix a dir,
un nivell més baix potser

993
00:45:43,824 --> 00:45:45,740
que alguns dels altres
algoritmes, però anem a

994
00:45:45,740 --> 00:45:48,550
veure si no podem visualitzar
aquests per mitjà d'això.

995
00:45:48,550 --> 00:45:51,450
>> Així que això és una bona
programari que algú

996
00:45:51,450 --> 00:45:56,110
va escriure usant barres de colors que de
anem a fer el següent per a nosaltres.

997
00:45:56,110 --> 00:45:57,736
Cadascuna d'aquestes barres representa un nombre.

998
00:45:57,736 --> 00:46:00,026
Taller de la barra, més
el nombre, més petita és la barra,

999
00:46:00,026 --> 00:46:00,990
com menor sigui el nombre.

1000
00:46:00,990 --> 00:46:05,880
Pel que idealment volem un bon piràmide
on comença petit i s'omple gran,

1001
00:46:05,880 --> 00:46:08,330
i això significaria que
aquestes barres estan ordenats.

1002
00:46:08,330 --> 00:46:11,200
Així que vaig a seguir endavant i triar,
per exemple, l'algorisme de Ben

1003
00:46:11,200 --> 00:46:13,990
la selecció primer-- tipus.

1004
00:46:13,990 --> 00:46:16,220
>> I observi el que està fent.

1005
00:46:16,220 --> 00:46:18,670
La forma en que han triat
visualitzar aquest algoritme

1006
00:46:18,670 --> 00:46:22,090
és que, igual que jo
caminant a través de la cistella,

1007
00:46:22,090 --> 00:46:24,710
aquest programa està caminant
a través de la seva llista de nombres,

1008
00:46:24,710 --> 00:46:28,160
destacant en rosa cada
nombre que s'està mirant.

1009
00:46:28,160 --> 00:46:32,360
I el que va a ocórrer ara?

1010
00:46:32,360 --> 00:46:35,154
>> El nombre més petit que
Em vaig trobar de sobte o Ben

1011
00:46:35,154 --> 00:46:36,820
obté mogut al principi de la llista.

1012
00:46:36,820 --> 00:46:40,037
I l'avís que van fer evict
el número que hi era,

1013
00:46:40,037 --> 00:46:41,120
i que està perfectament bé.

1014
00:46:41,120 --> 00:46:42,600
No em fico en aquest nivell de detall.

1015
00:46:42,600 --> 00:46:44,308
Però hem de posar
aquest nombre en algun lloc,

1016
00:46:44,308 --> 00:46:47,775
pel que acabem de mudar a la
lloc obert que va ser creat.

1017
00:46:47,775 --> 00:46:49,900
Així que vaig a accelerar aquest
, Perquè en cas contrari,

1018
00:46:49,900 --> 00:46:51,871
es torna molt tediós ràpidament.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animació speed-- hagi d'anar.

1021
00:46:58,600 --> 00:47:01,850
Així que ara mateix principi
Jo estava aplicant, però

1022
00:47:01,850 --> 00:47:06,540
pot començar a sentir l'algoritme, si
voluntat, ni es veu una mica més clarament.

1023
00:47:06,540 --> 00:47:13,190
I aquest algoritme té l'efecte de
seleccionar el següent element més petit,

1024
00:47:13,190 --> 00:47:16,422
pel que començarem a
veure que la rampa sobre de l'esquerra.

1025
00:47:16,422 --> 00:47:19,130
I en cada iteració, com jo
proposat, es fa una mica menys de treball.

1026
00:47:19,130 --> 00:47:21,921
No ha d'anar tot el camí
de nou a l'extrem esquerre de la llista,

1027
00:47:21,921 --> 00:47:23,900
perquè ja
coneix als s'ordenen.

1028
00:47:23,900 --> 00:47:28,129
Així que tipus de se sent com si fos
accelerant, tot i que cada pas és

1029
00:47:28,129 --> 00:47:29,420
tenint la mateixa quantitat de temps.

1030
00:47:29,420 --> 00:47:31,600
Només hi ha un menor nombre de passos restants.

1031
00:47:31,600 --> 00:47:35,240
I ara es pot sentir el tipus de
algoritme de neteja al final d'ella,

1032
00:47:35,240 --> 00:47:37,040
i de fet ara s'ha solucionat.

1033
00:47:37,040 --> 00:47:41,620
>> Així ordenació per inserció es fa tot.

1034
00:47:41,620 --> 00:47:43,600
He de tornar a canviar aleatòriament la matriu.

1035
00:47:43,600 --> 00:47:45,940
I noti que només pot
mantenir l'aleatorització d'ella,

1036
00:47:45,940 --> 00:47:50,630
i ens posarem una aproximació de
el mateix enfocament, l'ordenació per inserció.

1037
00:47:50,630 --> 00:47:55,050
Permetin-me retardar fins aquí.

1038
00:47:55,050 --> 00:47:56,915
Anem a començar que més.

1039
00:47:56,915 --> 00:47:57,414
Atura.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Anem a saltar 04:00.

1042
00:48:02,410 --> 00:48:03,200
Allà anem.

1043
00:48:03,200 --> 00:48:04,190
Selecció aleatòria d'ells matriu.

1044
00:48:04,190 --> 00:48:05,555
I aquí vaya-- ordenació per inserció.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Jugar.

1047
00:48:12,800 --> 00:48:17,280
Recordeu que es tracta de cadascun
element que troba de forma immediata,

1048
00:48:17,280 --> 00:48:20,282
però si pertany a
el lloc equivocat avís

1049
00:48:20,282 --> 00:48:21,740
tota la feina que ha de succeir.

1050
00:48:21,740 --> 00:48:24,700
Hem de seguir desplaçant més
i més elements per a fer lloc

1051
00:48:24,700 --> 00:48:27,340
per al qual volem posar al seu lloc.

1052
00:48:27,340 --> 00:48:30,740
>> Així que ens estem centrant en el
extrem esquerre de la llista única.

1053
00:48:30,740 --> 00:48:34,460
Avís ni tan sols hem vist que at--
no han posat en relleu en rosa res

1054
00:48:34,460 --> 00:48:35,610
a la dreta.

1055
00:48:35,610 --> 00:48:38,180
Estem davant
els problemes a mesura que avancem,

1056
00:48:38,180 --> 00:48:40,430
però estem creant una gran quantitat de
treballar per a nosaltres mateixos encara.

1057
00:48:40,430 --> 00:48:44,410
I pel que si accelerar això
ara anar fins a la seva finalització,

1058
00:48:44,410 --> 00:48:46,210
té una sensació diferent a ell de fet.

1059
00:48:46,210 --> 00:48:50,150
És només centrant-se en l'extrem esquerre, però
fent una mica més de treball com needed--

1060
00:48:50,150 --> 00:48:53,230
tipus de coses suavitzat
sobre, arreglar coses,

1061
00:48:53,230 --> 00:48:58,350
però en última instància es tracta amb
cada element d'una en una

1062
00:48:58,350 --> 00:49:07,740
fins a arribar a ell-- bo,
Tots sabem com va a acabar,

1063
00:49:07,740 --> 00:49:09,700
així que és una mica decebedor, potser.

1064
00:49:09,700 --> 00:49:12,830
>> Però la llista en el end--
spoiler-- va a ser resolt.

1065
00:49:12,830 --> 00:49:15,300
Així que anem a veure una última un.

1066
00:49:15,300 --> 00:49:16,840
No podem simplement saltar ara.

1067
00:49:16,840 --> 00:49:18,000
Ja gairebé hem arribat.

1068
00:49:18,000 --> 00:49:19,980
Queden dos, un per anar.

1069
00:49:19,980 --> 00:49:22,680
I llest.

1070
00:49:22,680 --> 00:49:23,450
Excel · lent.

1071
00:49:23,450 --> 00:49:27,220
>> Així que ara anem a fer una última,
tornar a l'aleatorització amb l'ordenació de bombolla.

1072
00:49:27,220 --> 00:49:31,690
I noto aquí, especialment si retardar
baix, això lliscant per mantenir.

1073
00:49:31,690 --> 00:49:36,830
Però cal notar que només té 2-2
comparisons-- tipus de solucions locals.

1074
00:49:36,830 --> 00:49:39,050
Però tan aviat com s'arriba a
Al final de la llista en rosa,

1075
00:49:39,050 --> 00:49:40,690
el que va a haver de passar de nou?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Sí, va a haver de
començar de nou, ja que només

1078
00:49:46,830 --> 00:49:49,870
errors fixos per parells.

1079
00:49:49,870 --> 00:49:53,120
I que podria haver revelat encara altres.

1080
00:49:53,120 --> 00:49:58,950
I pel que si accelerar aquest procés, se li
veure que, tant com el nom implica,

1081
00:49:58,950 --> 00:50:01,870
la més petita elements-- o més aviat,
elements-- els més grans estan començant

1082
00:50:01,870 --> 00:50:03,740
que pugen a la part superior, si es vol.

1083
00:50:03,740 --> 00:50:07,380
I els elements més petits són
començant a bombolla cap a baix a l'esquerra.

1084
00:50:07,380 --> 00:50:10,780
I, en efecte, que és una mena de
l'efecte visual.

1085
00:50:10,780 --> 00:50:17,150
I així, això va a acabar l'acabat
d'una manera molt similar, també.

1086
00:50:17,150 --> 00:50:19,160
>> No tenim habitar
en aquest cas en particular.

1087
00:50:19,160 --> 00:50:21,010
Permetin-me obrir això ara, també.

1088
00:50:21,010 --> 00:50:24,040
Hi ha alguns altres algoritmes d'ordenació
en el món, alguns dels quals

1089
00:50:24,040 --> 00:50:25,580
són capturats aquí.

1090
00:50:25,580 --> 00:50:29,960
I especialment per als estudiants que no estan
necessàriament visual o matemàtica,

1091
00:50:29,960 --> 00:50:31,930
com ho vam fer abans, podem
També fer això audially

1092
00:50:31,930 --> 00:50:34,210
si associar un so a això.

1093
00:50:34,210 --> 00:50:36,990
I només per diversió, he aquí una
uns algoritmes diferents,

1094
00:50:36,990 --> 00:50:40,950
i un d'ells, en particular, que està
notarà que es diu "fusió espècie."

1095
00:50:40,950 --> 00:50:43,250
>> En realitat, és una forma fonamentalment
millor algoritme,

1096
00:50:43,250 --> 00:50:45,860
de tal manera que es fonen espècie, una de
els que estan a punt de veure,

1097
00:50:45,860 --> 00:50:49,170
No és la fi de n al quadrat.

1098
00:50:49,170 --> 00:50:57,280
És de l'ordre de n vegades de registre
n, que és en realitat més petit i per tant

1099
00:50:57,280 --> 00:50:58,940
més ràpid que els altres tres.

1100
00:50:58,940 --> 00:51:00,670
I hi ha un parell d'un altre
els ximples que ja veurem.

1101
00:51:00,670 --> 00:51:01,933
>> Així que aquí anem amb una mica de so.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Aquesta és l'ordenació per inserció, així que de nou
és només tractar amb els elements

1104
00:51:10,490 --> 00:51:13,420
com vénen.

1105
00:51:13,420 --> 00:51:17,180
Es tracta d'una espècie de bombolla, pel que és
tenint en compte els parells alhora.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
I de nou, els elements més importants
estan bombollejant fins a la part superior.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Selecció El següent tipus.

1110
00:51:41,710 --> 00:51:45,420
Aquest és l'algoritme de Ben, on
De nou s'ha de seleccionar de forma iterativa

1111
00:51:45,420 --> 00:51:46,843
l'element immediatament inferior.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
I de nou, ara es pot escoltar que realment
està accelerant, però només en la mesura

1114
00:51:53,900 --> 00:51:58,230
com ho està fent cada vegada menys
treballar en cada iteració.

1115
00:51:58,230 --> 00:52:04,170
Aquest és el més ràpid, combinar espècie,
que es classificar grups de nombres

1116
00:52:04,170 --> 00:52:05,971
combinant junts i després ells.

1117
00:52:05,971 --> 00:52:07,720
Així look-- l'esquerra
la meitat ja està ordenada.

1118
00:52:07,720 --> 00:52:14,165
>> Ara està la classificació de la meitat dreta, i
Ara es va a combinar en una sola.

1119
00:52:14,165 --> 00:52:19,160
Això és una cosa que es diu "Gnome tipus."

1120
00:52:19,160 --> 00:52:23,460
I es pot veure que tipus de
que va d'anada i tornada,

1121
00:52:23,460 --> 00:52:27,950
la fixació de treball una mica aquí i
no abans de procedir al nou treball.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
I ja està.

1124
00:52:33,692 --> 00:52:36,400
Hi ha un altre tipus, que és
en realitat només amb fins acadèmics,

1125
00:52:36,400 --> 00:52:40,980
anomenada "classe estúpida", que té
les seves dades, que ordena a l'atzar,

1126
00:52:40,980 --> 00:52:43,350
i després comprova si està ordenada.

1127
00:52:43,350 --> 00:52:47,880
I si no ho és, es tornarà a ordenar que
a l'atzar, comprova si està ordenada,

1128
00:52:47,880 --> 00:52:49,440
i si no es repeteix.

1129
00:52:49,440 --> 00:52:52,660
I, en teoria, probabilísticament
Això completarà,

1130
00:52:52,660 --> 00:52:54,140
però després d'una mica de temps.

1131
00:52:54,140 --> 00:52:56,930
No és el més
eficient dels algoritmes.

1132
00:52:56,930 --> 00:53:02,550
Així que qualsevol pregunta sobre els
algoritmes o qualsevol particulars

1133
00:53:02,550 --> 00:53:04,720
relacionada amb elles, també?

1134
00:53:04,720 --> 00:53:09,430
>> Bé, ara anem a esmicolar el que tots
aquestes línies són que he estat dibuixant

1135
00:53:09,430 --> 00:53:15,090
i el que estic suposant que l'ordinador
pot fer sota de la campana.

1136
00:53:15,090 --> 00:53:18,650
Jo diria que tots aquests números
Segueixo drawing-- que necessiten per obtenir

1137
00:53:18,650 --> 00:53:21,330
emmagatzemat en algun lloc de la memòria.

1138
00:53:21,330 --> 00:53:24,130
Anem a desfer-nos d'aquest tipus ara, també.

1139
00:53:24,130 --> 00:53:30,110
>> Així que una peça de la memòria en una
computer-- pel DIMM RAM és

1140
00:53:30,110 --> 00:53:35,480
el que es van realitzar cerques d'ahir, dual
module-- de memòria en línia té aquest aspecte.

1141
00:53:35,480 --> 00:53:39,370
I cadascuna d'aquestes petites fitxes negres
és un nombre de bytes, en general.

1142
00:53:39,370 --> 00:53:44,380
I a continuació, les agulles d'or són com el
cables que es connecten a l'ordinador,

1143
00:53:44,380 --> 00:53:47,521
i la placa de silici verd és només
el que manté tot junt.

1144
00:53:47,521 --> 00:53:48,770
Llavors, què significa això realment?

1145
00:53:48,770 --> 00:53:53,180
Si aquest tipus de dibuix mateixa imatge,
Suposem per simplicitat

1146
00:53:53,180 --> 00:53:55,280
que aquest DIMM, dual
mòdul de memòria en línia,

1147
00:53:55,280 --> 00:54:00,530
és un gigabyte de memòria RAM, un giga de
memòria, que és el nombre de bytes en total?

1148
00:54:00,530 --> 00:54:02,100
Un gigabyte és el nombre de bytes?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Més que això.

1151
00:54:06,030 --> 00:54:09,960
1.124 és el quilo, 1.000.

1152
00:54:09,960 --> 00:54:11,730
Mega és milions.

1153
00:54:11,730 --> 00:54:14,570
Giga és un mil milions.

1154
00:54:14,570 --> 00:54:15,070
>> Estic mentint?

1155
00:54:15,070 --> 00:54:16,670
Podem fins i tot llegir l'etiqueta?

1156
00:54:16,670 --> 00:54:19,920
Això és en realitat 128
gigabytes, pel que és molt més.

1157
00:54:19,920 --> 00:54:22,130
Però anem a pretendre aquest
és només un gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Per la qual cosa significa que hi ha 1000000000
bytes de memòria disponibles per a mi

1159
00:54:25,640 --> 00:54:29,770
o 8 mil milions de bits, però anem
per parlar en termes de bytes ara,

1160
00:54:29,770 --> 00:54:30,750
avançant.

1161
00:54:30,750 --> 00:54:36,330
>> Així que el que això significa és que això és
un byte, això és un altre byte,

1162
00:54:36,330 --> 00:54:38,680
aquest és un altre byte,
i si realment volíem

1163
00:54:38,680 --> 00:54:43,280
per ser específics, hauríem de
dibuixar un bilió de petits quadrats.

1164
00:54:43,280 --> 00:54:44,320
Però què vol dir això?

1165
00:54:44,320 --> 00:54:46,420
Bé, permetin-me zoom
en aquesta imatge.

1166
00:54:46,420 --> 00:54:50,900
Si tinc alguna cosa que sembla
així ara, això és quatre bytes.

1167
00:54:50,900 --> 00:54:53,710
>> I pel que podria posar quatre nombres aquí.

1168
00:54:53,710 --> 00:54:54,990
Un dos tres quatre.

1169
00:54:54,990 --> 00:55:00,170
O podria posar quatre lletres o símbols.

1170
00:55:00,170 --> 00:55:02,620
"Hey!" podria anar-hi,
perquè cadascuna de les lletres,

1171
00:55:02,620 --> 00:55:04,370
hem comentat anteriorment,
podria ser representat

1172
00:55:04,370 --> 00:55:06,650
amb vuit bits o ASCII o un byte.

1173
00:55:06,650 --> 00:55:09,370
Així, en altres paraules, es pot
posar 8 mil milions de coses a l'interior

1174
00:55:09,370 --> 00:55:11,137
d'aquest un pal de memòria.

1175
00:55:11,137 --> 00:55:14,345
Ara, què significa per a posar les coses
amb esquena amb esquena a la memòria d'aquesta manera?

1176
00:55:14,345 --> 00:55:17,330
Això és el que un programador
diria una "matriu".

1177
00:55:17,330 --> 00:55:21,250
En un programa d'ordinador, que no crec
sobre el maquinari subjacent, per se.

1178
00:55:21,250 --> 00:55:24,427
Vostè només pensa en si mateix com tenint
accés a un total de mil milions de bytes,

1179
00:55:24,427 --> 00:55:26,010
i es pot el que vulgui amb ella.

1180
00:55:26,010 --> 00:55:27,880
Però per conveniència
generalment és útil

1181
00:55:27,880 --> 00:55:31,202
per mantenir el seu dret de memòria
un al costat de l'altre com aquest.

1182
00:55:31,202 --> 00:55:33,660
Així que si faig zoom sobre això-
perquè per descomptat no anem

1183
00:55:33,660 --> 00:55:39,310
per dibuixar un bilió de petits squares--
anem a suposar que aquest tauler representa

1184
00:55:39,310 --> 00:55:40,610
que pal de la memòria ara.

1185
00:55:40,610 --> 00:55:43,800
I només vaig a assenyalar a tots els que el meu
marcador acaba per donar-me aquí.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Així que ara tenim un pal
de memòria de la placa

1188
00:55:52,300 --> 00:55:56,400
això té un, dos, tres, quatre, cinc,
sis, un, dos, tres, quatre, cinc, sis,

1189
00:55:56,400 --> 00:56:01,130
seven-- així que 42 bytes de
memòria en el total de la pantalla.

1190
00:56:01,130 --> 00:56:01,630
Gràcies.

1191
00:56:01,630 --> 00:56:02,838
Sí, ho va fer el meu aritmètica dreta.

1192
00:56:02,838 --> 00:56:05,120
Pel que 42 bytes de memòria aquí.

1193
00:56:05,120 --> 00:56:06,660
Llavors, què significa això realment?

1194
00:56:06,660 --> 00:56:09,830
Bé, un programador d'ordinadors
en realitat generalment

1195
00:56:09,830 --> 00:56:12,450
pensar en aquesta memòria com direccionable.

1196
00:56:12,450 --> 00:56:16,630
En altres paraules, cada un d'aquests
ubicacions a la memòria, en maquinari,

1197
00:56:16,630 --> 00:56:18,030
té una adreça única.

1198
00:56:18,030 --> 00:56:22,020
>> No és tan complex com un Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
En canvi, és només un nombre.

1200
00:56:23,830 --> 00:56:27,930
Aquest és el nombre de bytes zero, és a dir
un, això és dues, això és tres,

1201
00:56:27,930 --> 00:56:30,327
i això és 41.

1202
00:56:30,327 --> 00:56:30,910
Espera un minut.

1203
00:56:30,910 --> 00:56:32,510
Vaig pensar que vaig dir fa un moment 42.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Vaig començar a comptar des de zero,
pel que és realment correcte.

1206
00:56:37,772 --> 00:56:40,980
Ara no hem de cridar la realitat
com una reixeta, i si ho dibuixa com una quadrícula

1207
00:56:40,980 --> 00:56:43,520
Crec que les coses realment
ser una mica enganyós.

1208
00:56:43,520 --> 00:56:46,650
Què faria un programador,
en la seva pròpia ment,

1209
00:56:46,650 --> 00:56:50,310
en general, pensar en això
la memòria com és com una cinta,

1210
00:56:50,310 --> 00:56:53,340
com un tros de cinta adhesiva
això és només una vegada i una altra per sempre

1211
00:56:53,340 --> 00:56:54,980
o fins que s'esgoti la memòria.

1212
00:56:54,980 --> 00:56:59,200
Així que d'una manera més comuna per dibuixar
i només pensar en la memòria

1213
00:56:59,200 --> 00:57:03,710
seria que això és byte zero, un,
dos, tres, i després del punt, punt, punt.

1214
00:57:03,710 --> 00:57:07,650
I vostè té 42 d'aquests bytes en total, fins i tot
encara que físicament en realitat podria

1215
00:57:07,650 --> 00:57:09,480
ser alguna cosa més semblant a això.

1216
00:57:09,480 --> 00:57:12,850
>> Així que si vostè ara pensa en el seu
la memòria, ja que, igual que una cinta,

1217
00:57:12,850 --> 00:57:17,640
això és el que un programador nou
cridaria a una matriu de memòria.

1218
00:57:17,640 --> 00:57:20,660
I quan es desitja emmagatzemar en realitat
alguna cosa a la memòria d'un ordinador,

1219
00:57:20,660 --> 00:57:23,290
en general, es deu conservar les coses
esquena amb esquena amb esquena amb esquena.

1220
00:57:23,290 --> 00:57:25,010
Així que hem estat parlant de nombres.

1221
00:57:25,010 --> 00:57:30,880
I quan jo volia per resoldre problemes
com quatre, un, tres, dos,

1222
00:57:30,880 --> 00:57:33,820
tot i que jo estava dibuixant
només el número quatre, un, tres,

1223
00:57:33,820 --> 00:57:39,490
dues de la taula, l'ordinador
realment tenen aquesta configuració en la memòria.

1224
00:57:39,490 --> 00:57:43,347
>> I el que seria al costat de la
dos a la memòria de l'ordinador?

1225
00:57:43,347 --> 00:57:44,680
Bé, no hi ha una resposta a això.

1226
00:57:44,680 --> 00:57:45,770
No se sap molt bé.

1227
00:57:45,770 --> 00:57:48,200
I sempre que la
equip no ho necessita,

1228
00:57:48,200 --> 00:57:51,440
que no ha de preocupar del que és el proper
als números que es preocupa per.

1229
00:57:51,440 --> 00:57:55,130
I quan he dit abans que un ordinador
només pot mirar en una direcció a la vegada,

1230
00:57:55,130 --> 00:57:56,170
això és una espècie de per què.

1231
00:57:56,170 --> 00:57:59,490
>> No a diferència d'un registre
jugador i un capçal de lectura

1232
00:57:59,490 --> 00:58:03,030
només ser capaç de mirar a una certa
ranura en un registre físic de la vella escola

1233
00:58:03,030 --> 00:58:06,500
a la vegada, de manera similar
pot un ordinador gràcies

1234
00:58:06,500 --> 00:58:09,810
a la seva UPC i la seva
conjunt d'instruccions Intel,

1235
00:58:09,810 --> 00:58:12,480
entre les instruccions
es llegeix de la memòria

1236
00:58:12,480 --> 00:58:15,590
o guardar en un memory--
equip només pot mirar

1237
00:58:15,590 --> 00:58:19,210
en un lloc en un temps--
de vegades una combinació d'ells,

1238
00:58:19,210 --> 00:58:21,770
però en realitat un sol lloc alhora.

1239
00:58:21,770 --> 00:58:24,770
Així que quan fèiem
aquests diversos algoritmes,

1240
00:58:24,770 --> 00:58:28,110
No només estic escrivint en una
vacuum-- quatre, un, tres, dos.

1241
00:58:28,110 --> 00:58:30,849
Aquests nombres pertanyen en realitat
en algun lloc físic en la memòria.

1242
00:58:30,849 --> 00:58:32,890
Així que hi ha diminut
transistors o algun tipus

1243
00:58:32,890 --> 00:58:35,840
de l'electrònica sota de la
campana d'emmagatzematge d'aquests valors.

1244
00:58:35,840 --> 00:58:40,460
>> I en total, el nombre de bits
involucrat en aquest moment, només per ser clars?

1245
00:58:40,460 --> 00:58:45,580
Així que això és de quatre bytes, o
ara és 32 bits en total.

1246
00:58:45,580 --> 00:58:49,280
Així que en realitat hi ha 32 zeros i
els que componen aquestes quatre coses.

1247
00:58:49,280 --> 00:58:52,070
Hi ha encara més per aquí, però
de nou, no es preocupen per això.

1248
00:58:52,070 --> 00:58:55,120
>> Així que ara anem a demanar una altra
pregunta usant la memòria,

1249
00:58:55,120 --> 00:58:57,519
perquè que al final
del dia és la variància.

1250
00:58:57,519 --> 00:59:00,310
No importa el que podríem fer amb
l'equip, al final del dia

1251
00:59:00,310 --> 00:59:02,560
el maquinari és encara el
mateixa sota de la campana.

1252
00:59:02,560 --> 00:59:04,670
Com anava a emmagatzemar una paraula en aquesta llista?

1253
00:59:04,670 --> 00:59:09,710
Doncs bé, una paraula en un equip com
"Hey!" s'emmagatzemaria com aquest.

1254
00:59:09,710 --> 00:59:12,300
I si volia una més llarga
paraula, només ha de

1255
00:59:12,300 --> 00:59:19,120
sobreescriure i que dir alguna cosa
així com "hola" i botiga que aquí.

1256
00:59:19,120 --> 00:59:23,930
>> I així, també, aquesta contigüitat
és en realitat un avantatge,

1257
00:59:23,930 --> 00:59:26,530
pel fet que un equip pot simplement
llegeix de dreta a esquerra.

1258
00:59:26,530 --> 00:59:28,680
Però vet aquí una pregunta.

1259
00:59:28,680 --> 00:59:33,480
En el context d'aquesta paraula,
h-e-l-l-o, signe d'exclamació,

1260
00:59:33,480 --> 00:59:38,740
Com podria l'equip saber on és el
paraula comença i on acaba la paraula?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
En el context dels nombres,
Com funciona l'equip

1263
00:59:43,800 --> 00:59:48,396
saber quant de temps la seqüència de
nombres és o on comença?

1264
00:59:48,396 --> 00:59:50,270
Bé, resulta out--
i no anirem massa

1265
00:59:50,270 --> 00:59:54,970
en aquest nivell de detail--
computadores mouen la matèria al voltant en la memòria

1266
00:59:54,970 --> 00:59:57,800
literalment, a través d'aquestes direccions.

1267
00:59:57,800 --> 01:00:02,080
Així que en un ordinador, si estàs
escriure codi per emmagatzemar coses

1268
01:00:02,080 --> 01:00:05,800
com les paraules, el que està
fent en realitat està escrivint

1269
01:00:05,800 --> 01:00:11,320
expressions que recorden a on
la memòria de l'ordinador aquestes paraules són.

1270
01:00:11,320 --> 01:00:14,370
Així que permetin-me fer un molt,
exemple molt senzill.

1271
01:00:14,370 --> 01:00:18,260
>> Vaig a seguir endavant i
obrir un programa de text simple,

1272
01:00:18,260 --> 01:00:20,330
i jo vaig a crear
un arxiu anomenat hola.c.

1273
01:00:20,330 --> 01:00:22,849
La major part d'aquesta informació,
No entraré en gran detall,

1274
01:00:22,849 --> 01:00:25,140
però vaig a escriure una
programa en el mateix idioma,

1275
01:00:25,140 --> 01:00:31,140
C. Això és molt més intimidatori,
Jo diria, que gratar,

1276
01:00:31,140 --> 01:00:32,490
però és molt similar en esperit.

1277
01:00:32,490 --> 01:00:34,364
De fet, aquests arrissat
braces-- puguis tipus de

1278
01:00:34,364 --> 01:00:37,820
pensar en el que he fet com aquest.

1279
01:00:37,820 --> 01:00:39,240
>> Anem a fer això, en realitat.

1280
01:00:39,240 --> 01:00:45,100
Quan fa clic a bandera verda,
fer el següent.

1281
01:00:45,100 --> 01:00:50,210
Vull imprimir "hola".

1282
01:00:50,210 --> 01:00:51,500
Així que això és ara pseudocodi.

1283
01:00:51,500 --> 01:00:53,000
Sóc una mena de desdibuixar les línies.

1284
01:00:53,000 --> 01:00:56,750
En C, aquest idioma estic parlant
aproximadament, aquesta línia d'impressió hola

1285
01:00:56,750 --> 01:01:01,940
en realitat es converteix en "printf" amb
alguns parèntesi i un punt i coma.

1286
01:01:01,940 --> 01:01:03,480
>> Però és la mateixa idea exacta.

1287
01:01:03,480 --> 01:01:06,730
I això molt fàcil d'utilitzar
"Quan es fa clic a bandera verda" es converteix

1288
01:01:06,730 --> 01:01:10,182
el més arcà "void main int."

1289
01:01:10,182 --> 01:01:12,890
I això realment sense cap assignació,
així que només vaig a ignorar això.

1290
01:01:12,890 --> 01:01:17,210
No obstant això, les claus són com el
peces del trencaclosques corbes d'aquest tipus.

1291
01:01:17,210 --> 01:01:18,700
>> Pel que pot tipus d'endevinar.

1292
01:01:18,700 --> 01:01:22,357
Fins i tot si mai has programat abans,
¿Què fa aquest programa probablement fer?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Probablement imprimeix hola
amb un signe d'exclamació.

1295
01:01:28,000 --> 01:01:29,150
>> Així que anem a tractar d'això.

1296
01:01:29,150 --> 01:01:30,800
Vaig a guardar-lo.

1297
01:01:30,800 --> 01:01:34,000
I això és, de nou, una molt
entorn de la vella escola.

1298
01:01:34,000 --> 01:01:35,420
No puc fer clic, no puc arrossegar.

1299
01:01:35,420 --> 01:01:36,910
He de escriure ordres.

1300
01:01:36,910 --> 01:01:41,320
Per això vull córrer el meu programa, per la qual
Jo podria fer això, de la mateixa manera que hola.c.

1301
01:01:41,320 --> 01:01:42,292
Aquest és l'arxiu em vaig trobar.

1302
01:01:42,292 --> 01:01:43,500
Però espera, que em falta un pas.

1303
01:01:43,500 --> 01:01:46,470
Què vam dir és una condició necessària
pas per a un llenguatge com C?

1304
01:01:46,470 --> 01:01:49,470
He font acaba d'escriure
codi, però què necessito?

1305
01:01:49,470 --> 01:01:50,670
Sí, necessito un compilador.

1306
01:01:50,670 --> 01:01:57,670
Així que en el meu Mac aquí, tinc una
programa anomenat GCC, GNU compilador de C,

1307
01:01:57,670 --> 01:02:03,990
el que em permet fer això- al seu torn
el meu codi font en, l'anomenarem,

1308
01:02:03,990 --> 01:02:04,930
codi màquina.

1309
01:02:04,930 --> 01:02:10,180
>> I puc veure que,
de nou, de la següent manera, aquests

1310
01:02:10,180 --> 01:02:14,090
són els zeros i uns I només
creat a partir de la meva codi font,

1311
01:02:14,090 --> 01:02:15,730
tots els zeros i uns.

1312
01:02:15,730 --> 01:02:17,770
I si vull córrer
el meu program-- succeeix

1313
01:02:17,770 --> 01:02:23,010
per a ser anomenat a.out per
reasons-- històrica "hola".

1314
01:02:23,010 --> 01:02:24,070
Puc córrer de nou.

1315
01:02:24,070 --> 01:02:25,690
Hola Hola hola.

1316
01:02:25,690 --> 01:02:27,430
I sembla estar funcionant.

1317
01:02:27,430 --> 01:02:31,000
>> Però això vol dir que en algun lloc de la meva
la memòria de l'ordinador són les paraules

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, signe d'exclamació.

1319
01:02:35,279 --> 01:02:38,070
I resulta que, igual que un a part,
el que un ordinador faria normalment

1320
01:02:38,070 --> 01:02:40,550
fer perquè sàpiga on
les coses comencen i és end--

1321
01:02:40,550 --> 01:02:42,460
posarà un símbol especial aquí.

1322
01:02:42,460 --> 01:02:46,064
I la convenció és posar el
número zero al final d'una paraula

1323
01:02:46,064 --> 01:02:48,230
perquè sàpiga on
en realitat acaba, per la qual cosa

1324
01:02:48,230 --> 01:02:52,750
no seguir imprimint més i més
caràcters dels que en realitat es proposen.

1325
01:02:52,750 --> 01:02:55,400
>> Però el menjar per emportar aquí, fins i tot
encara que això és bastant arcà,

1326
01:02:55,400 --> 01:02:58,140
és que és en última instància,
relativament simple.

1327
01:02:58,140 --> 01:03:04,550
Se li va donar una mena de cinta, un espai en blanc
espai en el qual pot escriure lletres.

1328
01:03:04,550 --> 01:03:07,150
Vostè simplement ha de tenir una
símbol especial, igual que de manera arbitrària

1329
01:03:07,150 --> 01:03:10,316
el número zero, per posar al final de
les seves paraules perquè l'ordinador sap,

1330
01:03:10,316 --> 01:03:13,410
Oh, hauria aturar la impressió després de
Veig el signe d'exclamació.

1331
01:03:13,410 --> 01:03:16,090
Perquè el següent que hi ha
és un valor ASCII de zero,

1332
01:03:16,090 --> 01:03:19,125
o el caràcter nul com
algú en diria.

1333
01:03:19,125 --> 01:03:21,500
Però hi ha una espècie d'un problema
aquí, i anem a tornar de nou

1334
01:03:21,500 --> 01:03:23,320
als números per un moment.

1335
01:03:23,320 --> 01:03:28,720
Suposem que faig, de fet,
disposarà d'un conjunt de nombres,

1336
01:03:28,720 --> 01:03:30,730
i suposem que la
programa que estic escrivint és

1337
01:03:30,730 --> 01:03:34,680
com un llibre de qualificacions d'un mestre
i una aula de professors.

1338
01:03:34,680 --> 01:03:38,720
I aquest programa li permet
per escriure en les puntuacions dels estudiants

1339
01:03:38,720 --> 01:03:39,960
en les proves.

1340
01:03:39,960 --> 01:03:43,750
I suposem que l'estudiant obté
100 en el seu primer concurs, potser

1341
01:03:43,750 --> 01:03:49,920
com un 80 en la pròxima, a continuació, una
75, després a 90 en la quarta prova.

1342
01:03:49,920 --> 01:03:54,150
>> Així que en aquest punt de la història,
la matriu és d'una grandària 04:00.

1343
01:03:54,150 --> 01:03:58,470
No hi ha absolutament més memòria al
ordinador, però la matriu, per així dir-ho,

1344
01:03:58,470 --> 01:04:00,350
és de mida quatre.

1345
01:04:00,350 --> 01:04:06,060
Suposem ara que el professor vol
per assignar una cinquena prova per a la classe.

1346
01:04:06,060 --> 01:04:08,510
Bé, una de les coses que ell
o ella va a haver de fer

1347
01:04:08,510 --> 01:04:10,650
ara és emmagatzemar un valor addicional aquí.

1348
01:04:10,650 --> 01:04:15,490
Però si la matriu té el mestre
creat en aquest programa és de mida per,

1349
01:04:15,490 --> 01:04:22,440
un dels problemes amb una matriu que és
no es pot simplement seguir afegint a la memòria.

1350
01:04:22,440 --> 01:04:26,470
Perquè el que si una altra part de la
programa té la paraula "hey" just aquí?

1351
01:04:26,470 --> 01:04:29,650
>> En altres paraules, la memòria pot ser
utilitzat per a qualsevol cosa en un programa.

1352
01:04:29,650 --> 01:04:33,250
I si per endavant teclegi, hey,
Vull entrada de quatre puntuacions de les proves,

1353
01:04:33,250 --> 01:04:34,784
que podrien anar aquí i aquí.

1354
01:04:34,784 --> 01:04:37,700
I si canvia de parer ràpidament
més tard i dir que vull un cinquè concurs

1355
01:04:37,700 --> 01:04:40,872
puntuació, no es pot simplement
ja que més li convingui,

1356
01:04:40,872 --> 01:04:42,580
perquè el que si aquesta
s'utilitza la memòria

1357
01:04:42,580 --> 01:04:45,990
per alguna cosa else-- algun altre programa
o alguna altra característica del programa

1358
01:04:45,990 --> 01:04:46,910
que s'està executant?

1359
01:04:46,910 --> 01:04:50,650
Així que cal pensar per endavant
la forma en la qual desitja emmagatzemar les seves dades,

1360
01:04:50,650 --> 01:04:54,480
perquè ara s'ha pintat
a si mateix en una cantonada digital.

1361
01:04:54,480 --> 01:04:57,280
>> Pel que un professor pot en canvi
dir en escriure un programa

1362
01:04:57,280 --> 01:04:59,360
per emmagatzemar el seu
graus, saben què?

1363
01:04:59,360 --> 01:05:04,180
Vaig a sol·licitar,
en escriure el meu programa,

1364
01:05:04,180 --> 01:05:12,070
Vull que zero, un, dos, tres,
quatre, cinc, sis, vuit graus en total.

1365
01:05:12,070 --> 01:05:15,320
Així que un, dos, tres, quatre,
cinc, sis, set, vuit.

1366
01:05:15,320 --> 01:05:18,612
El professor pot simplement sobreasigne
la memòria en escriure el seu programa

1367
01:05:18,612 --> 01:05:19,570
i dir, saben què?

1368
01:05:19,570 --> 01:05:22,236
Mai vaig a assignar més
de vuit proves en un semestre.

1369
01:05:22,236 --> 01:05:23,130
Això és una bogeria.

1370
01:05:23,130 --> 01:05:24,470
Mai vaig a assignar aquest.

1371
01:05:24,470 --> 01:05:28,270
Així que d'aquesta manera ell o ella té la
flexibilitat a la puntuació de botiga dels estudiants,

1372
01:05:28,270 --> 01:05:33,010
com 75, 90, i potser un addicional on
l'estudiant té el crèdit addicional, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Però si el mestre mai
utilitza aquests tres espais,

1374
01:05:36,130 --> 01:05:38,860
hi ha una menjar per emportar intuïtiva aquí.

1375
01:05:38,860 --> 01:05:41,410
Ell o ella està perdent espai.

1376
01:05:41,410 --> 01:05:44,790
Així, en altres paraules, hi ha una
desavantatge comú en la programació

1377
01:05:44,790 --> 01:05:48,241
on pot assignar
exactament com la quantitat de memòria que desitgi,

1378
01:05:48,241 --> 01:05:51,490
l'alça dels quals és que ets molt
efficient-- no estàs sent un malbaratament

1379
01:05:51,490 --> 01:05:54,640
en sobretot-- però el desavantatge dels quals
és el que si canvia d'opinió quan

1380
01:05:54,640 --> 01:05:58,780
usant el programa que voleu emmagatzemar
més dades que els que originalment previst.

1381
01:05:58,780 --> 01:06:03,030
>> Així que potser la solució és, doncs,
escriure els seus programes de tal manera

1382
01:06:03,030 --> 01:06:05,605
que utilitzen més memòria
del que realment necessiten.

1383
01:06:05,605 --> 01:06:07,730
D'aquesta manera no vas
a executar en aquest problema,

1384
01:06:07,730 --> 01:06:09,730
però estàs sent un malbaratament.

1385
01:06:09,730 --> 01:06:12,960
I com més memòria utilitza el seu programa,
com vam dir ahir, menys

1386
01:06:12,960 --> 01:06:15,410
la memòria que està disponible
per altres programes,

1387
01:06:15,410 --> 01:06:18,790
com més aviat millor l'equip podria alentir
a causa de la memòria virtual.

1388
01:06:18,790 --> 01:06:22,670
I així, la solució ideal podria ser què?

1389
01:06:22,670 --> 01:06:24,610
>> Sota-es reparteixen sembla malament.

1390
01:06:24,610 --> 01:06:27,030
Sobre-el qual es reparteixen sembla malament.

1391
01:06:27,030 --> 01:06:31,120
Llavors, què podria ser una solució millor?

1392
01:06:31,120 --> 01:06:32,390
La reassignació.

1393
01:06:32,390 --> 01:06:33,590
Ser més dinàmic.

1394
01:06:33,590 --> 01:06:37,520
No s'obligui a escollir un
a priori, al principi, el que volen.

1395
01:06:37,520 --> 01:06:41,370
I certament no sobreasigne,
perquè no sigui un malbaratament.

1396
01:06:41,370 --> 01:06:45,770
>> I així, per aconseguir aquest objectiu,
necessitar descarregar a aquesta estructura de dades,

1397
01:06:45,770 --> 01:06:48,100
per així dir-ho, de distància.

1398
01:06:48,100 --> 01:06:51,080
I així el que un programador
normalment utilitzarà

1399
01:06:51,080 --> 01:06:55,940
és una cosa que es diu no és una
matriu, però una llista enllaçada.

1400
01:06:55,940 --> 01:07:00,860
En altres paraules, ell o ella
començar a pensar en la seva memòria

1401
01:07:00,860 --> 01:07:05,280
com una mena de manera que es
pot treure de la següent manera.

1402
01:07:05,280 --> 01:07:08,520
Si vull emmagatzemar un nombre en
1 program-- pel que és de setembre

1403
01:07:08,520 --> 01:07:12,600
M'he donat als meus estudiants un qüestionari; vull
per emmagatzemar la primera prova dels estudiants,

1404
01:07:12,600 --> 01:07:16,220
i van aconseguir un 100 a it-- I
demanaré al meu equip,

1405
01:07:16,220 --> 01:07:19,540
per mitjà del programa que he
per escrit, per un tros de memòria.

1406
01:07:19,540 --> 01:07:22,570
I vaig a emmagatzemar el
número 100 en el mateix, i això és tot.

1407
01:07:22,570 --> 01:07:24,820
>> A continuació, unes setmanes més tard
quan arribo a la meva segona prova,

1408
01:07:24,820 --> 01:07:27,890
i és el moment d'escriure
en el qual el 90%, vaig

1409
01:07:27,890 --> 01:07:32,129
preguntar a l'equip, hey, ordinador,
puc tenir un altre tros de memòria?

1410
01:07:32,129 --> 01:07:34,170
Es em va a donar a aquest
tros buit de la memòria.

1411
01:07:34,170 --> 01:07:39,370
Vaig a posar en el nombre 90,
però en el meu programa d'una manera o altre--

1412
01:07:39,370 --> 01:07:42,100
i no anem a preocupar-se per
la sintaxi per això- que necessito

1413
01:07:42,100 --> 01:07:44,430
d'alguna manera encadenar aquestes coses juntes.

1414
01:07:44,430 --> 01:07:47,430
I els vaig a encadenar amb
el que sembla una sola fletxa.

1415
01:07:47,430 --> 01:07:50,050
>> El tercer qüestionari que apareix,
Vaig a dir, escolta, ordinador,

1416
01:07:50,050 --> 01:07:51,680
dóna'm una altra part de la memòria.

1417
01:07:51,680 --> 01:07:54,660
I vaig a posar a terra
el que fos, igual que 75,

1418
01:07:54,660 --> 01:07:56,920
i he de aquesta cadena de
junts ara d'alguna manera.

1419
01:07:56,920 --> 01:08:00,290
Quarta prova ve, i potser
això és cap al final del semestre.

1420
01:08:00,290 --> 01:08:03,140
I en aquest moment el meu programa
podria ser l'ús de la memòria

1421
01:08:03,140 --> 01:08:05,540
per tot el lloc, tot físicament.

1422
01:08:05,540 --> 01:08:08,170
I així, només per diversió, jo sóc
traurà aquesta volta

1423
01:08:08,170 --> 01:08:11,260
quiz-- m'oblido del que era; jo
pensar que potser un 80 o alguna cosa--

1424
01:08:11,260 --> 01:08:12,500
fins aquí.

1425
01:08:12,500 --> 01:08:15,920
>> Però això està bé, perquè pictòricament
Vaig a traçar aquesta línia.

1426
01:08:15,920 --> 01:08:19,063
En altres paraules, en la realitat,
en el maquinari de l'ordinador,

1427
01:08:19,063 --> 01:08:20,979
la primera puntuació podria
acaben aquí perquè és

1428
01:08:20,979 --> 01:08:22,529
just al començament del semestre.

1429
01:08:22,529 --> 01:08:25,810
El proper podria acabar aquí
perquè una mica de temps ha passat

1430
01:08:25,810 --> 01:08:27,210
i el programa segueix funcionant.

1431
01:08:27,210 --> 01:08:30,060
La puntuació següent, que era
un 75, podria ser aquí.

1432
01:08:30,060 --> 01:08:33,420
I l'última puntuació podria ser
un 80, que és per aquí.

1433
01:08:33,420 --> 01:08:38,729
>> Així que, en realitat, físicament, això podria ser
el que la memòria del seu ordinador es sembla.

1434
01:08:38,729 --> 01:08:41,569
Però això no és un trastorn mental útil
paradigma per a un programador d'ordinadors.

1435
01:08:41,569 --> 01:08:44,649
Per què ha de tenir cura quan l'
diables seves dades està acabant cap amunt?

1436
01:08:44,649 --> 01:08:46,200
El que desitja és emmagatzemar dades.

1437
01:08:46,200 --> 01:08:49,390
>> Això és una cosa així com la nostra discussió
abans de treure el cub.

1438
01:08:49,390 --> 01:08:52,200
Per què t'importa el
l'angle és de la galleda

1439
01:08:52,200 --> 01:08:53,740
i com s'ha de donar volta a dibuixar?

1440
01:08:53,740 --> 01:08:54,950
El que desitja és un cub.

1441
01:08:54,950 --> 01:08:57,359
De la mateixa manera aquí,
només volen llibre de qualificacions.

1442
01:08:57,359 --> 01:08:59,559
El que vol és pensar
això com una llista de nombres.

1443
01:08:59,559 --> 01:09:01,350
A qui li importa com és
implementat en maquinari?

1444
01:09:01,350 --> 01:09:05,180
>> Així que l'abstracció ara
És aquesta imatge aquí.

1445
01:09:05,180 --> 01:09:07,580
Aquesta és una llista vinculada, com
un programador en diria,

1446
01:09:07,580 --> 01:09:10,640
en la mesura que té una
llista, òbviament, dels nombres.

1447
01:09:10,640 --> 01:09:14,990
Però està vinculat pictòricament
per mitjà d'aquestes fletxes,

1448
01:09:14,990 --> 01:09:18,510
i totes aquestes fletxes sota són--
el capó, si tens curiositat,

1449
01:09:18,510 --> 01:09:23,210
recordar que el nostre maquinari físic té
adreces zero, un, dos, tres, quatre.

1450
01:09:23,210 --> 01:09:28,465
Totes aquestes fletxes són és com un mapa
o direccions, en la qual si ara 90 és--

1451
01:09:28,465 --> 01:09:29,090
He de explicar.

1452
01:09:29,090 --> 01:09:31,750
>> Zero, un, dos, tres,
quatre, cinc, sis, set.

1453
01:09:31,750 --> 01:09:35,640
Sembla que el 90 és a
memòria de nombre de direcció de set.

1454
01:09:35,640 --> 01:09:38,460
Totes aquestes fletxes són és
com un petit tros de paper

1455
01:09:38,460 --> 01:09:42,439
que és donar instruccions a la
programa que diu segueix aquest mapa

1456
01:09:42,439 --> 01:09:43,880
per arribar al lloc de set.

1457
01:09:43,880 --> 01:09:46,680
I allà es troba el
segona puntuació de la prova de Student.

1458
01:09:46,680 --> 01:09:52,100
Mentrestant, el 75-- si continuo això,
això és set, vuit, 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
>> Aquesta altra fletxa representa només
un mapa d'ubicació de la memòria 15.

1461
01:09:59,080 --> 01:10:02,550
Però, de nou, el programador fa generalment
no es preocupen per aquest nivell de detall.

1462
01:10:02,550 --> 01:10:05,530
I en la majoria de cada programació
llenguatge d'avui, el programador

1463
01:10:05,530 --> 01:10:10,490
ni tan sols saber on en la memòria
aquests números són en realitat.

1464
01:10:10,490 --> 01:10:14,830
Tot el que ell o ella ha de tenir en compte és
que d'alguna manera estan vinculats entre si

1465
01:10:14,830 --> 01:10:18,390
en una estructura de dades com aquest.

1466
01:10:18,390 --> 01:10:21,580
>> Però resulta que no
per aconseguir massa tècnic.

1467
01:10:21,580 --> 01:10:27,430
Però el fet que potser pot
permetre el luxe de tenir aquesta discussió aquí,

1468
01:10:27,430 --> 01:10:33,630
Suposem que tornem
aquesta qüestió aquí d'una matriu.

1469
01:10:33,630 --> 01:10:35,780
Ja veurem si ens penedim anar aquí.

1470
01:10:35,780 --> 01:10:42,950
Això és 100, 90, 75, i 80.

1471
01:10:42,950 --> 01:10:44,980
>> Permetin-me breument fer aquesta afirmació.

1472
01:10:44,980 --> 01:10:48,980
Aquesta és una matriu, i de nou, la
característica destacada d'una matriu

1473
01:10:48,980 --> 01:10:52,400
és que totes les seves dades estan de nou a
esquena amb esquena a memory-- literalment

1474
01:10:52,400 --> 01:10:56,830
Un byte o potser quatre bytes,
un nombre fix de bytes de distància.

1475
01:10:56,830 --> 01:11:00,710
En una llista enllaçada, que podríem anomenar la
així, a sota de la campana que

1476
01:11:00,710 --> 01:11:02,000
sap on és això?

1477
01:11:02,000 --> 01:11:03,630
Ni tan sols es necessita per fluir com aquest.

1478
01:11:03,630 --> 01:11:06,050
Algunes de les dades podria ser
de volta a l'esquerra fins allà.

1479
01:11:06,050 --> 01:11:07,530
Ni tan sols sap.

1480
01:11:07,530 --> 01:11:15,430
>> I així, amb una matriu, que té una
característica coneguda com accés aleatori.

1481
01:11:15,430 --> 01:11:20,570
I el que els mitjans d'accés aleatori és
que l'equip pot saltar a l'instant

1482
01:11:20,570 --> 01:11:22,730
a qualsevol lloc d'una matriu.

1483
01:11:22,730 --> 01:11:23,580
Per què?

1484
01:11:23,580 --> 01:11:26,000
A causa de que l'ordinador sap
que la primera ubicació és

1485
01:11:26,000 --> 01:11:29,540
zero, un, dos, i tres.

1486
01:11:29,540 --> 01:11:33,890
>> I així que si vols anar de
aquest element al següent element,

1487
01:11:33,890 --> 01:11:36,099
que, literalment, en el
la ment de l'ordinador, només ha d'afegir un.

1488
01:11:36,099 --> 01:11:39,140
Si vols anar al tercer element,
només ha d'afegir un-- següent element, simplement

1489
01:11:39,140 --> 01:11:40,290
afegir un.

1490
01:11:40,290 --> 01:11:42,980
No obstant això, en aquesta versió
de la història, suposi

1491
01:11:42,980 --> 01:11:46,080
l'equip està buscant actualment
en o per tractar amb el número 100.

1492
01:11:46,080 --> 01:11:49,770
Com s'arriba a la següent
grau en el llibre de qualificacions?

1493
01:11:49,770 --> 01:11:52,560
>> Vostè ha de prendre 7
passos, que és arbitrari.

1494
01:11:52,560 --> 01:11:58,120
Per arribar a la següent, cal
prendre altres vuit passos per arribar a 15.

1495
01:11:58,120 --> 01:12:02,250
En altres paraules, no és una
distància constant entre els números,

1496
01:12:02,250 --> 01:12:04,857
i per tant només es necessita la
equip més temps és el punt.

1497
01:12:04,857 --> 01:12:06,940
L'equip ha de buscar
a través de la memòria amb la finalitat

1498
01:12:06,940 --> 01:12:08,990
per trobar el que estàs buscant.

1499
01:12:08,990 --> 01:12:14,260
>> Així, mentre una matriu tendeix a ser una
structure-- ràpida de dades, ja que

1500
01:12:14,260 --> 01:12:17,610
literalment, pot simplement fer aritmètica simple
i obtenir en la qual desitja mitjançant l'addició d'un,

1501
01:12:17,610 --> 01:12:21,300
instance-- d'una llista enllaçada,
se sacrifica aquesta característica.

1502
01:12:21,300 --> 01:12:24,020
No es pot simplement passar de la primera
la segona a tercera a la quarta.

1503
01:12:24,020 --> 01:12:25,240
Vostè ha de seguir el mapa.

1504
01:12:25,240 --> 01:12:28,160
Vostè ha de prendre més mesures
per arribar a aquests valors, els quals

1505
01:12:28,160 --> 01:12:30,230
semblaria ser l'addició d'un cost.

1506
01:12:30,230 --> 01:12:35,910
Així que estem pagant un preu, però el que es
la característica que Dan estava buscant aquí?

1507
01:12:35,910 --> 01:12:38,110
Com és una llista enllaçada
pel que sembla, ens permet fer,

1508
01:12:38,110 --> 01:12:40,240
que va ser l'origen de
aquesta història en particular?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Exactament.

1511
01:12:43,830 --> 01:12:46,220
Una mida de dinàmica a la mateixa.

1512
01:12:46,220 --> 01:12:48,040
Podem afegir a aquesta llista.

1513
01:12:48,040 --> 01:12:51,430
Fins i tot podem reduir la llista, per la qual
que només estem utilitzant tanta memòria

1514
01:12:51,430 --> 01:12:55,560
ja que en realitat volem i per
mai estem sobre-el qual es reparteixen.

1515
01:12:55,560 --> 01:12:58,470
>> Ara acaba de ser molt primmirats,
hi ha un cost ocult.

1516
01:12:58,470 --> 01:13:01,980
Així que no ha de deixar a convèncer
que aquest és un compromís convincent.

1517
01:13:01,980 --> 01:13:04,190
Hi ha un altre cost ocult aquí.

1518
01:13:04,190 --> 01:13:06,550
El benefici, per ser clar,
és que tenim dinamisme.

1519
01:13:06,550 --> 01:13:10,359
Si vull un altre element, només pot
elaborar i posar un nombre en aquest país.

1520
01:13:10,359 --> 01:13:12,150
I llavors puc vincular
amb una imatge aquí,

1521
01:13:12,150 --> 01:13:14,970
mentre que aquí, de nou, si tinc
mi mateix pintat en una cantonada,

1522
01:13:14,970 --> 01:13:19,410
si alguna cosa més ja està utilitzant
la memòria aquí, estic fora de sort.

1523
01:13:19,410 --> 01:13:21,700
Jo mateix he pintat a la cantonada.

1524
01:13:21,700 --> 01:13:24,390
>> Però el que és l'ocult
costaria en aquesta imatge?

1525
01:13:24,390 --> 01:13:27,690
No és només la quantitat
de temps que es triga

1526
01:13:27,690 --> 01:13:29,870
per anar des d'aquí fins aquí,
que és set passos, llavors

1527
01:13:29,870 --> 01:13:32,820
vuit passos, que és més d'un.

1528
01:13:32,820 --> 01:13:34,830
Quin és altra cost ocult?

1529
01:13:34,830 --> 01:13:35,440
No només el temps.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Informació addicional està
necessàries per aconseguir aquesta imatge.

1532
01:13:49,940 --> 01:13:53,210
>> Sí, aquest mapa, aquests petits trossos de
paper, com segueixo descrivint-los com.

1533
01:13:53,210 --> 01:13:55,650
Aquests arrows-- els que no són lliures.

1534
01:13:55,650 --> 01:13:57,660
Un computer-- saps
el que té un ordinador.

1535
01:13:57,660 --> 01:13:58,790
Compta amb zeros i uns.

1536
01:13:58,790 --> 01:14:03,170
Si vol representar una fletxa o un
mapa o un nombre, es necessita una mica de memòria.

1537
01:14:03,170 --> 01:14:05,950
Així que l'altre preu que
pagar per una llista enllaçada,

1538
01:14:05,950 --> 01:14:09,070
una informàtica comuna
de recursos, és també l'espai.

1539
01:14:09,070 --> 01:14:11,710
>> I de fet és així, comunament,
entre les compensacions

1540
01:14:11,710 --> 01:14:15,580
en el disseny de l'enginyeria de programari
sistemes requereix temps i espai--

1541
01:14:15,580 --> 01:14:18,596
són dos dels seus ingredients, dues
dels seus ingredients més costosos.

1542
01:14:18,596 --> 01:14:21,220
Això m'està costant més temps
perquè tinc que segueix aquest mapa,

1543
01:14:21,220 --> 01:14:25,730
Però també em costa més espai
perquè he de mantenir aquest mapa voltant.

1544
01:14:25,730 --> 01:14:28,730
Pel que la esperança, com hem tipus de
discutit sobre l'ahir i avui,

1545
01:14:28,730 --> 01:14:31,720
és que els beneficis
seran més grans que els costos.

1546
01:14:31,720 --> 01:14:33,870
>> Però no hi ha una solució òbvia aquí.

1547
01:14:33,870 --> 01:14:35,870
Potser és millor--
a la ràpida i bruta,

1548
01:14:35,870 --> 01:14:38,660
com Kareem va proposar abans els he parlat
a tirar de memòria en el problema.

1549
01:14:38,660 --> 01:14:42,520
Acaba de comprar més memòria, pensar menys
estès sobre la solució del problema,

1550
01:14:42,520 --> 01:14:44,595
i resoldre-ho de una manera més fàcil.

1551
01:14:44,595 --> 01:14:46,720
I, de fet abans, quan
parlem sobre les compensacions,

1552
01:14:46,720 --> 01:14:49,190
no hi havia espai en
equip i l'hora.

1553
01:14:49,190 --> 01:14:51,810
Era temps de desenvolupament, la qual cosa
és un recurs més.

1554
01:14:51,810 --> 01:14:54,829
>> Així que de nou, és aquest acte d'equilibri
tractant de decidir quina d'aquestes coses

1555
01:14:54,829 --> 01:14:55,870
¿Està disposat a gastar?

1556
01:14:55,870 --> 01:14:57,380
Què és el menys costós?

1557
01:14:57,380 --> 01:15:01,040
Que produeix els millors resultats?

1558
01:15:01,040 --> 01:15:01,540
Sí?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> En efecte.

1561
01:15:12,580 --> 01:15:15,970
En aquest cas, si estàs
en representació de nombres en el maps--

1562
01:15:15,970 --> 01:15:18,820
aquests són cridats en molts idiomes
"Punters" o "direccions" -

1563
01:15:18,820 --> 01:15:20,390
que és el doble d'espai.

1564
01:15:20,390 --> 01:15:24,390
Això no té per què ser tan dolent com el doble si
en aquest moment només estem emmagatzemar nombres.

1565
01:15:24,390 --> 01:15:27,410
Suposem que s'emmagatzemaven
registres dels pacients en un hospital--

1566
01:15:27,410 --> 01:15:30,870
pel que els noms de Pierson, números de telèfon,
números de seguretat social, metge

1567
01:15:30,870 --> 01:15:31,540
història.

1568
01:15:31,540 --> 01:15:34,160
Aquest quadre pot ser molt,
molt més gran, en aquest cas

1569
01:15:34,160 --> 01:15:38,000
un diminut punter, la direcció de
la propera element-- que no és un gran problema.

1570
01:15:38,000 --> 01:15:40,620
És una franja tals
costa no importa.

1571
01:15:40,620 --> 01:15:43,210
Però en aquest cas, sí, és una duplicació.

1572
01:15:43,210 --> 01:15:45,290
Bona pregunta.

1573
01:15:45,290 --> 01:15:47,900
>> Anem a parlar d'una vegada
poc més concreta.

1574
01:15:47,900 --> 01:15:50,380
Què és el temps d'execució
de cercar aquesta llista?

1575
01:15:50,380 --> 01:15:53,640
Suposem que es vol buscar
a través de tots els graus dels estudiants,

1576
01:15:53,640 --> 01:15:55,980
i hi ha n graus
en aquesta estructura de dades.

1577
01:15:55,980 --> 01:15:58,830
Aquí, també, podem demanar prestat
el vocabulari de l'anterior.

1578
01:15:58,830 --> 01:16:00,890
Aquesta és una estructura de dades lineal.

1579
01:16:00,890 --> 01:16:04,570
>> O gran de n és el que es requereix per aconseguir
al final d'aquesta estructura de dades,

1580
01:16:04,570 --> 01:16:08,410
whereas-- i no hem vist
això abans-- una matriu que dóna

1581
01:16:08,410 --> 01:16:13,555
el que s'anomena constant de temps, el que significa
un pas o dos passos o 10 steps--

1582
01:16:13,555 --> 01:16:14,180
no importa.

1583
01:16:14,180 --> 01:16:15,440
És un nombre fix.

1584
01:16:15,440 --> 01:16:17,440
No té res a veure amb
la mida de la matriu.

1585
01:16:17,440 --> 01:16:20,130
I la raó que,
de nou, és d'accés aleatori.

1586
01:16:20,130 --> 01:16:23,180
L'ordinador pot simplement immediatament
saltar a una altra ubicació,

1587
01:16:23,180 --> 01:16:27,770
perquè són tots iguals
distància de tota la resta.

1588
01:16:27,770 --> 01:16:29,112
No hi ha pensament involucrat.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Tot bé.

1591
01:16:32,400 --> 01:16:39,230
Així que si puc, vaig a tractar
pintar dos quadres finals.

1592
01:16:39,230 --> 01:16:42,830
Un molt comú coneguda com una taula hash.

1593
01:16:42,830 --> 01:16:51,120
Així que per motivar aquesta discussió,
m'ho dius a mi pensar sobre com fer això.

1594
01:16:51,120 --> 01:16:52,610
>> Així que què tal això?

1595
01:16:52,610 --> 01:16:55,160
Suposem que el problema
volem resoldre ara

1596
01:16:55,160 --> 01:16:58,360
està duent a terme en un dictionary--
de manera que un munt de paraules en anglès

1597
01:16:58,360 --> 01:16:59,330
o el que sigui.

1598
01:16:59,330 --> 01:17:02,724
I l'objectiu és ser capaç de respondre
preguntes de la forma es tracta d'una paraula?

1599
01:17:02,724 --> 01:17:04,640
Pel que desitja aplicar
un corrector ortogràfic, just

1600
01:17:04,640 --> 01:17:07,220
com un diccionari física
que es pot mirar les coses en.

1601
01:17:07,220 --> 01:17:10,490
Suposem que jo anés a fer això amb una matriu.

1602
01:17:10,490 --> 01:17:12,590
Podria fer això.

1603
01:17:12,590 --> 01:17:20,756
>> I suposem que les paraules són la poma
i el plàtan i meló.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
I no puc pensar en les fruites
que comencen amb D., de manera que només estem

1606
01:17:26,465 --> 01:17:27,590
va a tenir tres fruites.

1607
01:17:27,590 --> 01:17:31,510
Així que aquesta és una matriu, i estem
emmagatzemar totes aquestes paraules

1608
01:17:31,510 --> 01:17:34,200
en aquest diccionari com una matriu.

1609
01:17:34,200 --> 01:17:39,350
La pregunta és, llavors, ¿de quina altra
es pot emmagatzemar aquesta informació?

1610
01:17:39,350 --> 01:17:43,160
>> Bé, estic tipus de parany aquí, perquè
cadascuna d'aquestes lletres de la paraula

1611
01:17:43,160 --> 01:17:44,490
és realment un byte individual.

1612
01:17:44,490 --> 01:17:46,740
Així que si realment volia ser
nit-exigent, que realment hauria

1613
01:17:46,740 --> 01:17:49,600
es divideix això en gran part
trossos més petits de la memòria,

1614
01:17:49,600 --> 01:17:51,289
i podríem fer exactament això.

1615
01:17:51,289 --> 01:17:53,580
Però anem a executar en
el mateix problema que abans.

1616
01:17:53,580 --> 01:17:56,674
Què passa si, com Merriam Webster o Oxford
Té cada any-- afegeixen paraules

1617
01:17:56,674 --> 01:17:59,340
a la dictionary-- no ho fem
necessàriament vol pintar-nos

1618
01:17:59,340 --> 01:18:00,780
en una cantonada amb una matriu?

1619
01:18:00,780 --> 01:18:05,710
>> Així que en comptes, potser un enfocament més intel·ligent
és posar poma en el seu propi node o caixa,

1620
01:18:05,710 --> 01:18:11,190
com diríem, plàtan, i
llavors aquí tenim meló.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
I la cadena que aquestes coses juntes.

1623
01:18:16,790 --> 01:18:19,980
Així que aquesta és la matriu, i
aquesta és la llista enllaçada.

1624
01:18:19,980 --> 01:18:23,300
Si no pot veure bé, només
diu "matriu", i això diu "llista".

1625
01:18:23,300 --> 01:18:25,780
>> Així que tenim la mateixa
qüestions exactes com abans,

1626
01:18:25,780 --> 01:18:28,600
de manera que ara tenim
dinamisme a la nostra llista enllaçada.

1627
01:18:28,600 --> 01:18:31,090
Però tenim un diccionari bastant lent.

1628
01:18:31,090 --> 01:18:32,870
Suposem que vull buscar una paraula.

1629
01:18:32,870 --> 01:18:35,430
Em podria tenir gran O de n
passos, perquè la paraula podria

1630
01:18:35,430 --> 01:18:37,840
ser tot el camí al final de
la llista, igual que el meló.

1631
01:18:37,840 --> 01:18:40,600
I resulta que
en la programació, més o menys

1632
01:18:40,600 --> 01:18:42,700
del Sant Grial de les dades
estructures, és una cosa

1633
01:18:42,700 --> 01:18:46,620
que li dóna constant
temps com una matriu

1634
01:18:46,620 --> 01:18:50,870
però que encara li dóna dinamisme.

1635
01:18:50,870 --> 01:18:52,940
>> Així podem tenir el millor d'ambdós mons?

1636
01:18:52,940 --> 01:18:55,570
I, en efecte, hi ha alguna cosa
diu la taula hash

1637
01:18:55,570 --> 01:18:59,320
que li permet fer exactament
que, encara que aproximadament.

1638
01:18:59,320 --> 01:19:03,140
Una taula hash és un columbòfil
estructura de dades que ens

1639
01:19:03,140 --> 01:19:06,340
es pot pensar en com el
combinació d'un array--

1640
01:19:06,340 --> 01:19:12,390
i vaig a treure,
així- i llistes enllaçades

1641
01:19:12,390 --> 01:19:17,310
que vaig a dibuixar com això aquí.

1642
01:19:17,310 --> 01:19:19,760
>> I la forma en què aquesta cosa
obres és com segueix.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Si això ara-- el hash table--
és la tercera estructura de dades,

1645
01:19:29,540 --> 01:19:32,590
i vull emmagatzemar
paraules d'aquest, no ho sé

1646
01:19:32,590 --> 01:19:35,440
voler simplement emmagatzemar tota la
paraules esquena amb esquena amb esquena amb esquena.

1647
01:19:35,440 --> 01:19:37,430
Vull aprofitar alguna
peça d'informació

1648
01:19:37,430 --> 01:19:40,330
sobre les paraules que li permetrà
jo entenc on és més ràpid.

1649
01:19:40,330 --> 01:19:43,666
>> Per tant, donada la poma paraules
i el plàtan i meló,

1650
01:19:43,666 --> 01:19:45,040
Vaig triar deliberadament aquestes paraules.

1651
01:19:45,040 --> 01:19:45,340
Per què?

1652
01:19:45,340 --> 01:19:47,631
El que és una espècie de, fonamentalment,
diferent en els tres?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Què és el que és obvi?

1655
01:19:51,484 --> 01:19:52,900
Comencen amb diferents lletres.

1656
01:19:52,900 --> 01:19:53,900
>> Així que ja saben què?

1657
01:19:53,900 --> 01:19:57,120
En lloc de posar totes les meves paraules
el mateix cub, per així dir-ho,

1658
01:19:57,120 --> 01:20:00,390
com en una llista molt llarga, ¿per què no fer
Jo, almenys, tracte a una optimització

1659
01:20:00,390 --> 01:20:04,180
i fer les meves llistes 1/26 sempre.

1660
01:20:04,180 --> 01:20:07,440
Una optimització convincent
podria ser per què no fer

1661
01:20:07,440 --> 01:20:10,650
Jo-- en inserir una paraula
en aquesta estructura de dades,

1662
01:20:10,650 --> 01:20:14,300
en la memòria de l'ordinador, per què
No vaig posar totes les paraules 'a' aquí,

1663
01:20:14,300 --> 01:20:17,270
totes les paraules 'b' aquí,
i totes les paraules 'c' aquí?

1664
01:20:17,270 --> 01:20:24,610
Així que això acaba posant una poma
aquí, plàtan aquí, meló aquí,

1665
01:20:24,610 --> 01:20:25,730
i així successivament.

1666
01:20:25,730 --> 01:20:31,700
>> I si tinc un addicional
paraula com- quin és l'altra?

1667
01:20:31,700 --> 01:20:36,640
Poma, plàtan, pera.

1668
01:20:36,640 --> 01:20:39,370
Algú pensa d'una fruita
que comença amb A, B, o C?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- perfecta.

1670
01:20:40,570 --> 01:20:43,990
Això va a acabar aquí.

1671
01:20:43,990 --> 01:20:47,530
I pel que sembla que tenen una
marginalment millor solució,

1672
01:20:47,530 --> 01:20:50,820
perquè ara si vull
per buscar la poma, em

1673
01:20:50,820 --> 01:20:53,200
primer-- no m'acaba de busseig
en el meu estructura de dades.

1674
01:20:53,200 --> 01:20:54,850
No em submergeixo en la memòria del meu ordinador.

1675
01:20:54,850 --> 01:20:56,530
La primera vegada que miro la primera lletra.

1676
01:20:56,530 --> 01:20:58,610
>> I això és el que un ordinador
científic diria.

1677
01:20:58,610 --> 01:21:00,760
Vostè comprovació aleatòria, l'estructura de dades.

1678
01:21:00,760 --> 01:21:04,100
Vostè pren la seva entrada, que al seu
aquest cas és una paraula com la poma.

1679
01:21:04,100 --> 01:21:07,150
Vostè ho analitza, mirant
la primera lletra en aquest cas,

1680
01:21:07,150 --> 01:21:08,340
hash d'aquesta manera.

1681
01:21:08,340 --> 01:21:10,950
Hashing mitjançant el qual és un terme general
preses alguna cosa com a entrada

1682
01:21:10,950 --> 01:21:12,116
i produir una sortida.

1683
01:21:12,116 --> 01:21:15,090
I la sortida en aquest
cas és la ubicació

1684
01:21:15,090 --> 01:21:18,150
que voleu cercar, el primer
ubicació, segona ubicació, tercer.

1685
01:21:18,150 --> 01:21:22,160
Així que l'entrada és de poma,
la sortida és primer.

1686
01:21:22,160 --> 01:21:25,054
L'entrada és plàtan, la
sortida ha de ser segon.

1687
01:21:25,054 --> 01:21:27,220
L'entrada és meló,
la sortida ha de ser tercer.

1688
01:21:27,220 --> 01:21:30,320
L'entrada és el nabiu, la
sortida ha de tornar a ser segon.

1689
01:21:30,320 --> 01:21:34,010
I això és el que l'ajuda a prendre
accessos directes a través de la memòria

1690
01:21:34,010 --> 01:21:39,050
per tal d'arribar a les paraules
o les dades de manera més eficaç.

1691
01:21:39,050 --> 01:21:43,330
>> Ara bé, això redueix el nostre temps potencialment
per tant com un de cada 26,

1692
01:21:43,330 --> 01:21:45,850
perquè si s'assumeix que vostè
tenir tants "a" paraules com "z"

1693
01:21:45,850 --> 01:21:48,080
paraules com a paraules "q", que
no és realment realistic--

1694
01:21:48,080 --> 01:21:50,830
vas a tenir biaix en tots
certes lletres del alphabet--

1695
01:21:50,830 --> 01:21:53,204
però això seria un increment
enfocament que permet

1696
01:21:53,204 --> 01:21:55,930
vostè pugui arribar a dir molt més ràpidament.

1697
01:21:55,930 --> 01:21:59,660
I en realitat, un sofisticat
programa, el Googles del món,

1698
01:21:59,660 --> 01:22:02,180
la Facebooks del món--
usarien una taula hash

1699
01:22:02,180 --> 01:22:03,740
per a una gran quantitat de propòsits diferents.

1700
01:22:03,740 --> 01:22:06,590
Però ells no serien tan ingenus com
a tan sols mirar la primera lletra

1701
01:22:06,590 --> 01:22:09,700
a la poma o un plàtan o
pera o el meló,

1702
01:22:09,700 --> 01:22:13,420
ja que com es pot veure aquests
llistes encara podien fer llarga.

1703
01:22:13,420 --> 01:22:17,130
>> I així, això encara podria ser una espècie
de manera linear-- espècie de lent,

1704
01:22:17,130 --> 01:22:19,980
de la mateixa manera que amb el gran O de n
que hem comentat anteriorment.

1705
01:22:19,980 --> 01:22:25,290
Així que el que és una veritable bona voluntat taula hash
fer-- que tindrà una gamma molt més gran.

1706
01:22:25,290 --> 01:22:28,574
I va a utilitzar una forma molt més
sofisticada funció hash,

1707
01:22:28,574 --> 01:22:30,240
de manera que no es limita a considerar la "a".

1708
01:22:30,240 --> 01:22:35,480
Potser es veu en "a-p-p-l-i" i
d'alguna manera converteix aquestes cinc lletres

1709
01:22:35,480 --> 01:22:38,400
en la ubicació on
poma ha de ser emmagatzemat.

1710
01:22:38,400 --> 01:22:42,660
Estem ingènuament utilitzant la lletra "a"
sol, perquè és agradable i senzilla.

1711
01:22:42,660 --> 01:22:44,600
>> Però una taula hash, en
Al final, es pot pensar

1712
01:22:44,600 --> 01:22:47,270
de com una combinació de
una matriu, cada un dels quals

1713
01:22:47,270 --> 01:22:51,700
té una llista enllaçada que, idealment,
ha de ser el més curt possible.

1714
01:22:51,700 --> 01:22:54,364
I això no és una solució òbvia.

1715
01:22:54,364 --> 01:22:57,280
De fet, gran part de la sintonització fina
que continua sota de la caputxa quan

1716
01:22:57,280 --> 01:22:59,654
la implementació d'aquest tipus de
estructures de dades sofisticades

1717
01:22:59,654 --> 01:23:01,640
és el que és el dret
longitud de la matriu?

1718
01:23:01,640 --> 01:23:03,250
Quina és la funció hash correcte?

1719
01:23:03,250 --> 01:23:04,830
Com es pot emmagatzemar en la memòria les coses?

1720
01:23:04,830 --> 01:23:07,249
>> Però adonar-se del ràpid
aquest tipus de discussió

1721
01:23:07,249 --> 01:23:10,540
escalada, o bé fins al moment que és una espècie
de sobre el cap d'un en aquest punt, que

1722
01:23:10,540 --> 01:23:11,360
està bé.

1723
01:23:11,360 --> 01:23:18,820
Però comencem, memòria, amb veritat
alguna cosa de baix nivell i l'electrònica.

1724
01:23:18,820 --> 01:23:20,819
I pel que aquest nou és aquest
el tema de l'abstracció,

1725
01:23:20,819 --> 01:23:23,610
on una vegada que comenci a prendre per
concedida, OK, he it-- vaig arribar allà és

1726
01:23:23,610 --> 01:23:26,680
memòria física, OK, ho va aconseguir, cada
ubicació física té una adreça,

1727
01:23:26,680 --> 01:23:29,910
OK, el tinc, puc representar
aquestes adreces com arrows--

1728
01:23:29,910 --> 01:23:34,650
pot començar molt ràpidament a tenir
converses més sofisticades que

1729
01:23:34,650 --> 01:23:38,360
al final sembla que són el que ens
per resoldre problemes com la recerca

1730
01:23:38,360 --> 01:23:41,620
i classificar de manera més eficaç.

1731
01:23:41,620 --> 01:23:44,190
I pot estar segur, també-
perquè crec que això

1732
01:23:44,190 --> 01:23:48,700
és la més profunda que hem anat en alguna
d'aquests temes CS proper-- que hem

1733
01:23:48,700 --> 01:23:51,880
fet en un dia i mig en aquest
apuntar el que normalment podria fer més de

1734
01:23:51,880 --> 01:23:55,520
el curs de vuit setmanes en un semestre.

1735
01:23:55,520 --> 01:23:59,670
>> Qualsevol pregunta sobre aquests?

1736
01:23:59,670 --> 01:24:01,100
No?

1737
01:24:01,100 --> 01:24:01,940
Tot bé.

1738
01:24:01,940 --> 01:24:05,610
Bé, per què no ens aturem allà,
començar el dinar uns minuts abans,

1739
01:24:05,610 --> 01:24:07,052
reprendre en tan sols al voltant d'una hora?

1740
01:24:07,052 --> 01:24:08,760
I vaig a romandre durant
una mica amb preguntes.

1741
01:24:08,760 --> 01:24:11,343
A continuació, vaig a haver d'anar
prendre un parell de trucades si això està bé.

1742
01:24:11,343 --> 01:24:15,000
Vaig al seu torn una mica de música en el interí,
però el dinar ha de ser la volta de la cantonada.

1743
01:24:15,000 --> 01:24:17,862