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

2
00:00:10,900 --> 00:00:15,860
>> ALTAVEU 1: Molt bé, així que això és
CS50 Aquest és el final de la cinquena setmana.

3
00:00:15,860 --> 00:00:19,220
I recordar que l'última vegada que
començat a buscar en les dades més elegant

4
00:00:19,220 --> 00:00:22,310
estructures que van començar a resoldre
problemes, que van començar a introduir

5
00:00:22,310 --> 00:00:25,640
nous problemes, però la clau d'aquest
Era el tipus de roscat que

6
00:00:25,640 --> 00:00:27,940
començat a fer des d'un node a un altre.

7
00:00:27,940 --> 00:00:30,085
Així que aquest supòsit és
una llista simplement enllaçada.

8
00:00:30,085 --> 00:00:31,960
I per separat vinculats,
Vull dir que hi ha una sola

9
00:00:31,960 --> 00:00:33,380
fil entre cada un d'aquests nodes.

10
00:00:33,380 --> 00:00:35,890
Resulta que vostè pot fer més elegant
coses com llistes doblement enllaçades

11
00:00:35,890 --> 00:00:38,470
pel que vostè té una fletxa
va en dues direccions, la qual cosa

12
00:00:38,470 --> 00:00:40,320
pot ajudar amb certes eficiències.

13
00:00:40,320 --> 00:00:42,000
Però això soluciona el problema?

14
00:00:42,000 --> 00:00:43,500
Quin problema es resol això?

15
00:00:43,500 --> 00:00:46,620
Per què ens importa el dilluns?

16
00:00:46,620 --> 00:00:49,820
Per què, en teoria, ens cuidem el dilluns?

17
00:00:49,820 --> 00:00:50,630
Què fa això?

18
00:00:50,630 --> 00:00:51,950
>> AUDIÈNCIA: dinàmicament Podem canviar la seva mida.

19
00:00:51,950 --> 00:00:53,740
>> ALTAVEU 1: OK, per la qual cosa podem
dinàmicament canvieu la mida.

20
00:00:53,740 --> 00:00:54,710
Ben fet tots dos.

21
00:00:54,710 --> 00:00:57,560
Així que vostè pot canviar la mida de forma dinàmica aquest
estructura de dades, mentre que una matriu,

22
00:00:57,560 --> 00:01:00,760
record, vostè ha de saber una
priori la quantitat d'espai que voleu

23
00:01:00,760 --> 00:01:03,870
i si vostè necessita una mica més
espai, ets la classe de sort.

24
00:01:03,870 --> 00:01:05,560
Has de crear una nova matriu sencera.

25
00:01:05,560 --> 00:01:07,893
Has de moure tot el seu
dades d'un a un altre,

26
00:01:07,893 --> 00:01:10,600
finalment alliberar la matriu d'edat
si es pot, i després procedir.

27
00:01:10,600 --> 00:01:13,891
La qual cosa se sent molt costós i molt
ineficients, i de fet pot ser.

28
00:01:13,891 --> 00:01:14,890
Però això no és tot el bo.

29
00:01:14,890 --> 00:01:18,180
Nosaltres paguem un preu, el que va ser un
dels preus més òbvies

30
00:01:18,180 --> 00:01:20,550
pagar mitjançant l'ús d'una llista enllaçada?

31
00:01:20,550 --> 00:01:22,825
>> AUDIÈNCIA: Hem de fer servir
doble espai per a cada un.

32
00:01:22,825 --> 00:01:25,200
ALTAVEU 1: Sí, pel que necessitem
almenys el doble d'espai.

33
00:01:25,200 --> 00:01:27,700
De fet, em vaig adonar d'aquesta imatge
fins i tot una mica enganyós,

34
00:01:27,700 --> 00:01:32,200
perquè l'IDE CS50 en molts moderna
ordinadors, un punter o una adreça

35
00:01:32,200 --> 00:01:33,700
no és, de fet, quatre bytes.

36
00:01:33,700 --> 00:01:36,090
És molt sovint aquests
dies 8 bytes, que

37
00:01:36,090 --> 00:01:38,530
significa la part inferior més
rectangles hi ha en la realitat

38
00:01:38,530 --> 00:01:40,900
són una mena de doble de
gran com el que he dibuixat,

39
00:01:40,900 --> 00:01:44,409
el que significa que està utilitzant tres vegades més
espai que podríem tenir d'una altra manera.

40
00:01:44,409 --> 00:01:46,700
Ara, al mateix temps, estem
sense deixar de parlar bytes, oi?

41
00:01:46,700 --> 00:01:49,140
No estem parlant necessàriament
megabytes o gigabytes,

42
00:01:49,140 --> 00:01:51,000
llevat que aquestes estructures de dades es fan grans.

43
00:01:51,000 --> 00:01:54,510
>> I per això avui comencem a considerar
com podríem explorar les dades

44
00:01:54,510 --> 00:01:57,310
més eficientment si en
fet que les dades es fa més gran.

45
00:01:57,310 --> 00:02:00,360
Però anem a tractar de canonicalize
les operacions de la primera

46
00:02:00,360 --> 00:02:02,460
que es pot fer en aquests
tipus d'estructures de dades.

47
00:02:02,460 --> 00:02:04,790
Així que alguna cosa com un lligada
llista general dóna suport

48
00:02:04,790 --> 00:02:07,514
operacions com esborrar,
inserir i cercar.

49
00:02:07,514 --> 00:02:08,639
I el que vull dir amb això?

50
00:02:08,639 --> 00:02:11,222
Això només vol dir que en general,
si la gent està utilitzant llista enllaçada,

51
00:02:11,222 --> 00:02:14,287
ells o algú més ha implementat
funcions com esborrar, inserir,

52
00:02:14,287 --> 00:02:16,120
i la recerca, de manera que pot
realment fer alguna cosa

53
00:02:16,120 --> 00:02:18,030
útil amb l'estructura de dades.

54
00:02:18,030 --> 00:02:20,760
Així que anem a fer una ullada ràpida
en com podríem aplicar

55
00:02:20,760 --> 00:02:24,530
una mica de codi per a una llista enllaçada de la següent manera.

56
00:02:24,530 --> 00:02:27,885
>> Així que això és només una mica de codi C,
ni tan sols un programa complet

57
00:02:27,885 --> 00:02:29,260
que realment em van assotar ràpidament.

58
00:02:29,260 --> 00:02:32,300
No és en línia en la distribució
codi, perquè no funcionarà realment.

59
00:02:32,300 --> 00:02:33,790
Però noto que tinc just
amb un comentari dir,

60
00:02:33,790 --> 00:02:36,130
punt punt punt, hi ha alguna cosa
allà, dot dot dot, alguna cosa allà.

61
00:02:36,130 --> 00:02:38,410
I anem a mirar
¿Quines són les parts sucoses.

62
00:02:38,410 --> 00:02:40,790
Així que en la línia 3,
recordem que això és ara

63
00:02:40,790 --> 00:02:45,960
ens vam proposar declarar un node última
temps, un d'aquests objectes rectangulars.

64
00:02:45,960 --> 00:02:48,790
Té un int que anomenarem N,
però podríem anomenar res,

65
00:02:48,790 --> 00:02:51,920
i després una estrella struct node anomenat següent.

66
00:02:51,920 --> 00:02:55,520
I només perquè quedi clar, que segons
línia, en la línia 6, què és això?

67
00:02:55,520 --> 00:02:57,930
Què està fent per nosaltres?

68
00:02:57,930 --> 00:03:01,044
Perquè sens dubte es veu més
críptica que les nostres variables habituals.

69
00:03:01,044 --> 00:03:02,740
>> AUDIÈNCIA: Es fa que es mogui més d'una.

70
00:03:02,740 --> 00:03:04,650
>> ALTAVEU 1: Es fa que es mogui més d'una.

71
00:03:04,650 --> 00:03:08,580
I per ser més precisos,
emmagatzemarà la direcció

72
00:03:08,580 --> 00:03:11,582
del node que està destinat a ser
semànticament al costat d'ell, oi?

73
00:03:11,582 --> 00:03:13,540
Per tant, no va a
moure necessàriament res.

74
00:03:13,540 --> 00:03:15,290
És només va a
emmagatzemar un valor, que és

75
00:03:15,290 --> 00:03:17,170
serà la direcció
d'algun altre node,

76
00:03:17,170 --> 00:03:20,810
i és per això que hem dit struct
estrella de node, que denota l'estrella

77
00:03:20,810 --> 00:03:22,370
un punter o una adreça.

78
00:03:22,370 --> 00:03:26,390
OK, així que ara si assumir que tenim
aquesta N disponible per a nosaltres, i anem a

79
00:03:26,390 --> 00:03:29,490
assumir que algú més té
inserit un munt de nombres enters

80
00:03:29,490 --> 00:03:30,400
en una llista enllaçada.

81
00:03:30,400 --> 00:03:35,640
I aquesta llista enllaçada és
apuntada per algun moment

82
00:03:35,640 --> 00:03:39,040
una trucada llista de variables que és
aprovada en aquí com un paràmetre,

83
00:03:39,040 --> 00:03:43,120
com faig per línia
14 implementació de cerca?

84
00:03:43,120 --> 00:03:45,990
En altres paraules, si m'estic posant en pràctica
funció el propòsit en la vida

85
00:03:45,990 --> 00:03:48,889
és prendre un int i després el
a partir d'una llista enllaçada,

86
00:03:48,889 --> 00:03:50,430
que és un punter a la llista enllaçada.

87
00:03:50,430 --> 00:03:52,992
Com a primera, que crec que David
era la nostra voluntària dilluns

88
00:03:52,992 --> 00:03:54,700
ell estava assenyalant
tot vinculat la llista,

89
00:03:54,700 --> 00:03:57,820
és com si estem passant
David com la nostra discussió aquí.

90
00:03:57,820 --> 00:03:59,990
Com fem per travessar aquesta llista?

91
00:03:59,990 --> 00:04:04,640
Bé, resulta que tot i que
punters són relativament nou ara a nosaltres,

92
00:04:04,640 --> 00:04:07,010
podem fer això relativament
sense embuts.

93
00:04:07,010 --> 00:04:09,500
>> Vaig a seguir endavant i
declarar una variable temporal que

94
00:04:09,500 --> 00:04:12,364
per convenció és només anar
per a ser anomenat punter o PTR,

95
00:04:12,364 --> 00:04:14,030
però se li pot dir el que vulguis.

96
00:04:14,030 --> 00:04:16,470
I jo vaig a inicialitzar
al començament de la llista.

97
00:04:16,470 --> 00:04:20,050
Així que vostè pot classe de pensar en això
com jo la mestra, l'altre dia,

98
00:04:20,050 --> 00:04:23,580
tipus de apuntant a algú
entre els nostres éssers humans com a voluntaris.

99
00:04:23,580 --> 00:04:26,470
Així que sóc una variable temporal que és
simplement apuntant-se al mateix

100
00:04:26,470 --> 00:04:31,390
que el nostre coincidentment nomenat
voluntari David també estava assenyalant.

101
00:04:31,390 --> 00:04:35,440
Ara bé, tot i que és punter
no és nul, perquè recordo

102
00:04:35,440 --> 00:04:40,350
que nul és un valor especial sentinella
la demarcació del final de la llista,

103
00:04:40,350 --> 00:04:44,280
així que mentre jo no estic apuntant a la
sòl com la nostra última voluntari

104
00:04:44,280 --> 00:04:47,190
va ser, seguirem endavant
i faci el següent.

105
00:04:47,190 --> 00:04:51,820
Si pointer-- i ara que tipus de desig
a fer el que vam fer amb l'estudiant

106
00:04:51,820 --> 00:04:57,410
structure-- si dot punter proper
equals-- més bé, si dot punter N és igual

107
00:04:57,410 --> 00:05:02,290
és igual a la variable N, la
argument que ha estat aprovada en,

108
00:05:02,290 --> 00:05:05,370
llavors vull seguir endavant
i dir tornar realitat.

109
00:05:05,370 --> 00:05:11,020
He trobat el nombre N interior
un dels nodes de la cistella enllaçada.

110
00:05:11,020 --> 00:05:13,500
Però el punt ja no
funciona en aquest context,

111
00:05:13,500 --> 00:05:17,260
perquè punter, PTR, és
de fet un punter, una adreça,

112
00:05:17,260 --> 00:05:20,632
que en realitat pot meravellosament
utilitzar finalment una peça de sintaxi

113
00:05:20,632 --> 00:05:22,590
aquest tipus de marques
sentit intuïtiu i realitat

114
00:05:22,590 --> 00:05:27,870
utilitzar una fletxa aquí, el que significa passar de
aquesta direcció al sencer més enllà en.

115
00:05:27,870 --> 00:05:30,160
Així que és molt similar a
esperit per a l'operador punt,

116
00:05:30,160 --> 00:05:33,860
sinó perquè punter no és un punter
i no una pròpia estructura real,

117
00:05:33,860 --> 00:05:35,380
només ha d'utilitzar la fletxa.

118
00:05:35,380 --> 00:05:40,620
>> Així que si el node actual que jo, el
variable temporal, estic apuntant a

119
00:05:40,620 --> 00:05:43,060
¿No és N, què és el que vull fer?

120
00:05:43,060 --> 00:05:45,910
Doncs bé, amb els meus voluntaris humans
que vam tenir aquí l'altre dia,

121
00:05:45,910 --> 00:05:49,710
si el meu primer ésser humà no és el que jo
vol, i potser el segon humà no és

122
00:05:49,710 --> 00:05:52,660
el que jo vull, i el tercer, que
de mantenir físicament en moviment.

123
00:05:52,660 --> 00:05:54,690
Igual que com em va passar a través d'una llista?

124
00:05:54,690 --> 00:05:57,470
Quan vam tenir una matriu,
acaba de fer com si plus plus.

125
00:05:57,470 --> 00:06:03,660
Però en aquest cas, només cal
fer punter, aconsegueix, punter, al costat.

126
00:06:03,660 --> 00:06:07,580
En altres paraules, el camp següent
és com totes les mans esquerres

127
00:06:07,580 --> 00:06:10,880
que els nostres voluntaris humans dilluns
estaven usant per assenyalar en algun altre node.

128
00:06:10,880 --> 00:06:12,890
Aquestes van ser les seves següents veïns.

129
00:06:12,890 --> 00:06:17,060
>> Així que si vull fer un pas a través d'aquesta llista,
No puc fer jo plus plus més,

130
00:06:17,060 --> 00:06:20,120
Jo en canvi he de dir
Jo, punter, va

131
00:06:20,120 --> 00:06:24,650
per igualar qualsevol que sigui el següent camp és,
el següent camp és, el següent camp és,

132
00:06:24,650 --> 00:06:28,350
després totes aquestes mans esquerres
que teníem en l'escenari que assenyala

133
00:06:28,350 --> 00:06:30,000
per a alguns valors posteriors.

134
00:06:30,000 --> 00:06:32,590
I si em poso a través
tota aquesta iteració,

135
00:06:32,590 --> 00:06:39,330
i, finalment, em va colpejar nul·la no tenir
Vaig trobar N però, acabo de tornar falsa.

136
00:06:39,330 --> 00:06:44,100
Així que de nou, tot el que estem fent aquí,
segons la imatge fa un moment,

137
00:06:44,100 --> 00:06:47,840
està començant assenyalant al
a partir de la llista de suposar.

138
00:06:47,840 --> 00:06:50,970
I llavors puc comprovar, és el valor
Busco igual a nou?

139
00:06:50,970 --> 00:06:52,650
Si és així, torno veritable i he acabat.

140
00:06:52,650 --> 00:06:56,450
Si no, puc actualitzar la meva mà,
També conegut com punter, al punt

141
00:06:56,450 --> 00:06:59,540
en el lloc de la propera fletxa i
a continuació, la ubicació de la propera fletxa,

142
00:06:59,540 --> 00:07:00,480
i el següent.

143
00:07:00,480 --> 00:07:03,770
Simplement estic caminant a través d'aquesta matriu.

144
00:07:03,770 --> 00:07:06,010
>> Així que de nou, a qui li importa?

145
00:07:06,010 --> 00:07:07,861
Igual que ho és aquest ingredient per?

146
00:07:07,861 --> 00:07:10,360
Bé, recordem que vam introduir
la noció d'una pila, que

147
00:07:10,360 --> 00:07:15,400
és un tipus abstracte de dades en la mesura que és
no és una cosa C, no és una cosa CS50,

148
00:07:15,400 --> 00:07:19,430
és una idea abstracta, aquesta idea de
apilar coses a la part superior dels uns als altres

149
00:07:19,430 --> 00:07:21,820
que es poden implementar en
raïms de diferents maneres.

150
00:07:21,820 --> 00:07:25,600
I una manera que vam proposar va ser amb
una matriu o amb una llista enllaçada.

151
00:07:25,600 --> 00:07:29,570
I resulta que canònicament, 1
pila compatible amb almenys dues operacions.

152
00:07:29,570 --> 00:07:32,320
I les paraules de moda són d'empenta, a
empènyer alguna cosa a la pila,

153
00:07:32,320 --> 00:07:34,770
com una nova safata al
menjador, o el pop,

154
00:07:34,770 --> 00:07:39,000
el que significa per eliminar el més elevat
safata de la pila al menjador

155
00:07:39,000 --> 00:07:41,500
passadís, i després potser alguns
altres operacions també.

156
00:07:41,500 --> 00:07:45,770
Llavors, ¿com podríem definir l'estructura
que ara estem cridant a una pila?

157
00:07:45,770 --> 00:07:50,020
>> Bé, tenim tot el necessari
sintaxi a la nostra disposició en C. dic,

158
00:07:50,020 --> 00:07:53,830
donar-me una definició de tipus de
una estructura interior d'una pila,

159
00:07:53,830 --> 00:07:58,030
Jo vaig a dir és una matriu, d'un
tota munt de números i després la mida.

160
00:07:58,030 --> 00:08:00,930
En altres paraules, si vull
per implementar aquesta en el codi,

161
00:08:00,930 --> 00:08:03,830
me n'aniré i només una mica
dibuixar el que això està dient.

162
00:08:03,830 --> 00:08:06,317
Així que això està dient, dóna'm un
estructura que té una matriu,

163
00:08:06,317 --> 00:08:09,400
i jo no sé el que és la capacitat,
pel que sembla és una constant que tinc

164
00:08:09,400 --> 00:08:10,858
definits en un altre lloc, i això està bé.

165
00:08:10,858 --> 00:08:15,260
Però suposo que és només un,
dos, tres, quatre, cinc.

166
00:08:15,260 --> 00:08:16,700
Així capacitat és de 5.

167
00:08:16,700 --> 00:08:21,730
Aquest element interior del meu
estructura es dirà nombres.

168
00:08:21,730 --> 00:08:24,020
I llavors jo necessito un
una altra variable aparentment

169
00:08:24,020 --> 00:08:27,814
crida mida que al principi em vaig
estipular s'inicialitza a zero.

170
00:08:27,814 --> 00:08:29,730
Si no hi ha res en
la pila, la mida és zero,

171
00:08:29,730 --> 00:08:31,420
i és els valors d'escombraries en nombres.

172
00:08:31,420 --> 00:08:33,450
No tinc idea del que hi ha allà de moment.

173
00:08:33,450 --> 00:08:36,059
>> Així que si vull empènyer
alguna cosa a la pila,

174
00:08:36,059 --> 00:08:40,780
Suposo que jo anomeno la funció d'empenta, i
Dic empènyer 50, com el nombre 50,

175
00:08:40,780 --> 00:08:44,090
on proposaria
Assenyalo que en aquesta sèrie?

176
00:08:44,090 --> 00:08:47,124
Hi ha cinc possibles respostes diferents.

177
00:08:47,124 --> 00:08:48,790
On vol empènyer el nombre 50?

178
00:08:48,790 --> 00:08:51,899
Si l'objectiu aquí, de nou, trucar al
la funció d'empenta, passar en una discussió

179
00:08:51,899 --> 00:08:52,940
de 50, on ho poso?

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

181
00:08:55,680 --> 00:08:59,052
Cinc possible- 20% de probabilitat
d'endevinar correctament.

182
00:08:59,052 --> 00:08:59,896
Sí?

183
00:08:59,896 --> 00:09:00,740
>> AUDIÈNCIA: Extrem dret.

184
00:09:00,740 --> 00:09:01,990
>> ALTAVEU 1: Extrem dret.

185
00:09:01,990 --> 00:09:08,359
En l'actualitat existeix una probabilitat del 25%
d'endevinar correctament.

186
00:09:08,359 --> 00:09:09,650
Així que això seria realment bé.

187
00:09:09,650 --> 00:09:12,770
Per convenció, ho diré amb una matriu,
estaríem en general començarà a l'esquerra,

188
00:09:12,770 --> 00:09:14,519
Però podríem sens dubte
començarà a les de la dreta.

189
00:09:14,519 --> 00:09:17,478
Així que l'aleró aquí seria que sóc
probablement va a treure, a l'esquerra,

190
00:09:17,478 --> 00:09:20,060
de la mateixa manera que en una matriu normal on
Començo a anar a l'esquerra a la dreta.

191
00:09:20,060 --> 00:09:21,780
Però si es pot donar la volta
l'aritmètica, bé.

192
00:09:21,780 --> 00:09:23,060
És que no és convencional.

193
00:09:23,060 --> 00:09:24,880
OK, he de fer una
més canvi però.

194
00:09:24,880 --> 00:09:27,710
Ara que l'he empès una mica
a la pila, què segueix?

195
00:09:27,710 --> 00:09:29,400
>> Molt bé, he de incrementar la grandària.

196
00:09:29,400 --> 00:09:32,600
Així que permetin-me anar per davant i just
actualitzar aquesta, que era zero.

197
00:09:32,600 --> 00:09:35,950
I en lloc ara, em vaig
posar en valor un.

198
00:09:35,950 --> 00:09:39,460
I ara suposo empenyo altra
número a la pila, igual que 51.

199
00:09:39,460 --> 00:09:42,680
Bé, he de fer una més
el canvi, que és fins a la mida 02:00.

200
00:09:42,680 --> 00:09:46,100
I després suposo empenyo una més
número a la pila com 61,

201
00:09:46,100 --> 00:09:52,530
ara he de actualitzar la mida d'una més
temps, i obtenir el valor 3 com la mida.

202
00:09:52,530 --> 00:09:54,690
I ara suposo que jo anomeno pop.

203
00:09:54,690 --> 00:09:57,250
Ara pop, per convenció,
no té un argument.

204
00:09:57,250 --> 00:10:00,430
Amb una pica, la totalitat
punt de la metàfora de la safata

205
00:10:00,430 --> 00:10:03,450
és que vostè no té la discreció
per anar a buscar aquesta safata, tot el que pot fer

206
00:10:03,450 --> 00:10:06,330
s'obrirà el de més amunt de
la pila, perquè sí.

207
00:10:06,330 --> 00:10:08,010
Això és el que fa aquesta estructura de dades.

208
00:10:08,010 --> 00:10:12,250
>> Així que per aquesta lògica si
diuen pop, el que surt?

209
00:10:12,250 --> 00:10:13,080
Així que 61.

210
00:10:13,080 --> 00:10:15,402
Així que el que realment és l'ordinador
va a fer en la memòria?

211
00:10:15,402 --> 00:10:16,610
Què fa el meu codi ha de fer?

212
00:10:16,610 --> 00:10:20,330
Què proposaria vostè
canviem a la pantalla?

213
00:10:20,330 --> 00:10:23,410
Què ha de canviar?

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

215
00:10:24,960 --> 00:10:26,334
Així que ens desfem de 61.

216
00:10:26,334 --> 00:10:27,500
Així que definitivament puc fer això.

217
00:10:27,500 --> 00:10:28,640
I puc desfer-me d'61.

218
00:10:28,640 --> 00:10:30,980
I llavors, ¿quina altra
el canvi ha de succeir?

219
00:10:30,980 --> 00:10:33,160
Mida probablement ha de tornar a dos.

220
00:10:33,160 --> 00:10:34,210
I així està bé.

221
00:10:34,210 --> 00:10:36,690
Però esperi un minut, mida
Fa un moment tenia tres anys.

222
00:10:36,690 --> 00:10:38,240
Anem a fer una comprovació de validesa ràpid.

223
00:10:38,240 --> 00:10:41,810
Com sabem que estem
volia desfer-se del 61?

224
00:10:41,810 --> 00:10:42,760
A causa de que estem fent esclatar.

225
00:10:42,760 --> 00:10:46,450
I així tinc aquest segon mida de la propietat.

226
00:10:46,450 --> 00:10:48,470
>> Espera un minut, estic
pensant en tornar a la segona setmana

227
00:10:48,470 --> 00:10:51,660
quan vam començar a parlar de
arrays, on això era lloc de zero,

228
00:10:51,660 --> 00:10:55,920
aquesta era la ubicació un, aquesta era la ubicació
dos, això és la ubicació tres, quatre,

229
00:10:55,920 --> 00:10:58,460
sembla que el
relació entre la mida

230
00:10:58,460 --> 00:11:02,780
i l'element que vull treure
de la matriu sembla ser el que?

231
00:11:02,780 --> 00:11:05,120
Mida menys un.

232
00:11:05,120 --> 00:11:07,786
I així és com els humans
sabem 61 que passi primer.

233
00:11:07,786 --> 00:11:09,160
Com està l'equip va a saber?

234
00:11:09,160 --> 00:11:11,701
Quan el seu codi, en el qual, probablement,
vol fer mida de menys un,

235
00:11:11,701 --> 00:11:14,950
almenys un de tres és de dos, i que
vol dir que volem desfer-nos d'61.

236
00:11:14,950 --> 00:11:18,000
I llavors podem efectivament actualitzar
la mida de manera que la mida ara

237
00:11:18,000 --> 00:11:20,300
va de tres a dos.

238
00:11:20,300 --> 00:11:24,520
I només per ser pedant, vaig
proposar que he acabat, no?

239
00:11:24,520 --> 00:11:27,660
Vostè va proposar intuïtivament
correctament He desfer-me d'61.

240
00:11:27,660 --> 00:11:30,700
Però no han de tipus de
tipus de rebuig de 61?

241
00:11:30,700 --> 00:11:33,790
M'he oblidat de manera efectiva
que en realitat existeix.

242
00:11:33,790 --> 00:11:37,680
I pensar en tornar a PSET4, si has llegit
l'article sobre medicina forense, el PDF

243
00:11:37,680 --> 00:11:40,780
que havíem de vostès llegir, o
llegirà aquesta setmana per PSET4.

244
00:11:40,780 --> 00:11:44,300
Recordem que això és en realitat afí a
tota la idea de la informàtica forense.

245
00:11:44,300 --> 00:11:47,820
El que un equip generalment fa és
simplement s'oblida on és alguna cosa,

246
00:11:47,820 --> 00:11:51,300
però no entra i igual que
tractar d'arrapar cap a fora o anul·lació

247
00:11:51,300 --> 00:11:54,560
aquests bits amb zeros i uns
o algun altre patró aleatori

248
00:11:54,560 --> 00:11:56,690
llevat que vostè mateix ho fan deliberadament.

249
00:11:56,690 --> 00:11:58,930
Pel que la seva intuïció era
Molt bé, anem a desfer-nos de 61.

250
00:11:58,930 --> 00:12:00,650
Però en realitat, no hem de preocupar-se.

251
00:12:00,650 --> 00:12:04,040
Només hem d'oblidar que
que hi és canviant el nostre mida.

252
00:12:04,040 --> 00:12:05,662
>> Ara hi ha un problema amb aquesta pila.

253
00:12:05,662 --> 00:12:07,620
Si segueixo empenyent coses
a la pila, el que és

254
00:12:07,620 --> 00:12:11,167
Òbviament passarà
en tan sols uns pocs moments de temps?

255
00:12:11,167 --> 00:12:12,500
Anem a quedar-se sense espai.

256
00:12:12,500 --> 00:12:13,580
I, què fem?

257
00:12:13,580 --> 00:12:14,680
Estem tipus de fotuts.

258
00:12:14,680 --> 00:12:19,000
Aquesta aplicació no permet
ens redimensionar la matriu, perquè l'ús de

259
00:12:19,000 --> 00:12:21,240
aquesta sintaxi, si
pensar de nou a la segona setmana,

260
00:12:21,240 --> 00:12:23,520
una vegada que s'ha declarat
la mida d'un array,

261
00:12:23,520 --> 00:12:26,780
no hem vist un mecanisme encara quan
vostè pot canviar la mida de la matriu.

262
00:12:26,780 --> 00:12:29,020
I de fet C no té aquesta característica.

263
00:12:29,020 --> 00:12:32,524
Si dius dóna'm 5
NTHS, els diuen nombres,

264
00:12:32,524 --> 00:12:33,940
això és tot el que vas a aconseguir-ho.

265
00:12:33,940 --> 00:12:38,790
Així que anem a fer ara a partir de dilluns, tenim
la capacitat d'expressar una solució

266
00:12:38,790 --> 00:12:42,480
però, només hem d'ajustar
la definició de la nostra pila

267
00:12:42,480 --> 00:12:46,840
de no haver algun conjunt modificable,
però només per emmagatzemar una adreça.

268
00:12:46,840 --> 00:12:47,890
>> Ara per què és això?

269
00:12:47,890 --> 00:12:51,690
Ara només hem d'estar còmode amb
el fet que quan la meva programa s'executa,

270
00:12:51,690 --> 00:12:53,730
Estic presumiblement va
ha de demanar a la humana,

271
00:12:53,730 --> 00:12:55,110
la quantitat de nombres és el que vols per emmagatzemar?

272
00:12:55,110 --> 00:12:56,776
Així que l'entrada ha de venir d'algun lloc.

273
00:12:56,776 --> 00:12:59,140
Però una vegada que sé que
nombre, llavors jo puc només

274
00:12:59,140 --> 00:13:02,470
utilitzar el que funciona per donar
mi una part de la memòria?

275
00:13:02,470 --> 00:13:03,580
Puc utilitzar malloc.

276
00:13:03,580 --> 00:13:06,710
I puc dir qualsevol nombre de
bytes vull tornar per aquests NTHS.

277
00:13:06,710 --> 00:13:10,910
I tot el que tinc per emmagatzemar en els números
variable d'aquí dins d'aquesta estructura

278
00:13:10,910 --> 00:13:13,480
hauria de ser què?

279
00:13:13,480 --> 00:13:18,440
El que en realitat succeeix en el
nombres en aquest escenari?

280
00:13:18,440 --> 00:13:21,300
Sí, un punter a la primera
byte d'aquest tros de memòria,

281
00:13:21,300 --> 00:13:24,940
o més específicament, la direcció de
del primer d'aquests bytes.

282
00:13:24,940 --> 00:13:27,300
No importa si és un
byte o mil milions de bytes,

283
00:13:27,300 --> 00:13:28,890
Només he de preocupar-se pel primer.

284
00:13:28,890 --> 00:13:31,530
Perquè ¿quines garanties malloc i
meus garanties del sistema operatiu,

285
00:13:31,530 --> 00:13:34,170
és que la part de la memòria d'E
aconseguir, que serà contigus.

286
00:13:34,170 --> 00:13:35,378
No va a haver-hi llacunes.

287
00:13:35,378 --> 00:13:38,576
Així que si jo he demanat 50
bytes o 1.000 bytes,

288
00:13:38,576 --> 00:13:40,450
estan tots van a ser
esquena amb esquena amb esquena.

289
00:13:40,450 --> 00:13:44,500
I sempre que em acord de què tan gran, com
tant que vaig demanar, tot el que necessito saber

290
00:13:44,500 --> 00:13:46,230
és la primera direcció.

291
00:13:46,230 --> 00:13:48,660
>> Així que ara tenim la capacitat de codi.

292
00:13:48,660 --> 00:13:51,280
Encara que, va portar-nos
més temps per escriure això,

293
00:13:51,280 --> 00:13:55,900
podríem ara reassignar aquest record per
simplement emmagatzemar una adreça diferent allà

294
00:13:55,900 --> 00:13:59,060
si volem una més gran o fins i tot
un tros més petit de la memòria.

295
00:13:59,060 --> 00:14:00,170
Així que aquí a un fora de comerç.

296
00:14:00,170 --> 00:14:01,360
Ara arribem dinamisme.

297
00:14:01,360 --> 00:14:03,350
Encara tenim
contigüitat que estic afirmant.

298
00:14:03,350 --> 00:14:05,881
A causa de malloc ens donarà
una part contigua de la memòria.

299
00:14:05,881 --> 00:14:08,630
Però això serà un dolor a
el coll per a nosaltres, el programador,

300
00:14:08,630 --> 00:14:09,770
codificar realment cap amunt.

301
00:14:09,770 --> 00:14:10,730
És només més feina.

302
00:14:10,730 --> 00:14:13,930
Necessitem codi similar al que era
colpejant a terme fa un moment.

303
00:14:13,930 --> 00:14:16,120
Molt factible, però afegeix complexitat.

304
00:14:16,120 --> 00:14:19,520
I així que el temps desenvolupador, programador
el temps és un altre recurs

305
00:14:19,520 --> 00:14:22,520
que puguem necessitar per passar
una mica de temps per aconseguir noves característiques.

306
00:14:22,520 --> 00:14:24,020
I després, per descomptat, hi ha una cua.

307
00:14:24,020 --> 00:14:26,227
No entrarem en això
una a molt detall.

308
00:14:26,227 --> 00:14:27,560
Però és molt similar en esperit.

309
00:14:27,560 --> 00:14:31,220
Jo podria implementar una cua, i
les seves operacions corresponents,

310
00:14:31,220 --> 00:14:35,660
enqueue o treure de la cua, com afegir o treure,
és només una forma més elegant de dir-ho,

311
00:14:35,660 --> 00:14:38,100
enqueue o treure de la cua, com segueix.

312
00:14:38,100 --> 00:14:41,170
Només em puc donar una estructura
que de nou té matriu d'un nombre,

313
00:14:41,170 --> 00:14:44,000
que de nou té una mida,
però per què faig Ara necessito

314
00:14:44,000 --> 00:14:46,940
fer un seguiment de la part davantera de la cua?

315
00:14:46,940 --> 00:14:50,630
Jo no necessito saber
el front de la meva pila.

316
00:14:50,630 --> 00:14:53,570
Bé, si jo de nou per un
queue-- anem només difícil

317
00:14:53,570 --> 00:14:57,870
codificar com tenint com de cinc
sencers en aquí potencialment.

318
00:14:57,870 --> 00:15:00,940
Així que aquest és zero, un, dos, tres, quatre.

319
00:15:00,940 --> 00:15:03,430
Això serà
números cridats de nou.

320
00:15:03,430 --> 00:15:06,940
I això es dirà mida.

321
00:15:06,940 --> 00:15:10,056
>> Per què és no suficient
tenir la mida just?

322
00:15:10,056 --> 00:15:11,680
Bé, anem a empènyer aquests mateixos números en.

323
00:15:11,680 --> 00:15:14,220
Així que pushed-- I en cua, o empès.

324
00:15:14,220 --> 00:15:20,150
Ara vaig a posar en cua 50, i després
51, i després de 61 anys, i dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Així que això és enqueue.

326
00:15:21,070 --> 00:15:23,176
Jo en cua 50, després 51, després 61.

327
00:15:23,176 --> 00:15:25,050
I això es veu idèntica
a una pila fins al moment,

328
00:15:25,050 --> 00:15:27,190
sense que jo ho necessito per fer un canvi.

329
00:15:27,190 --> 00:15:33,680
Necessito actualitzar aquesta mida, així que vaig
de zero a 1:00-02:58 ara.

330
00:15:33,680 --> 00:15:35,760
Com puc treure de la cua?

331
00:15:35,760 --> 00:15:36,890
Què passa amb dequeue?

332
00:15:36,890 --> 00:15:41,950
Qui ha de sortir aquesta llista primer
si es tracta de la línia a la botiga d'Apple?

333
00:15:41,950 --> 00:15:42,780
Així que 50.

334
00:15:42,780 --> 00:15:44,700
Així que és una mica més difícil aquesta vegada.

335
00:15:44,700 --> 00:15:47,880
Mentre que l'última vegada va ser super
simplement fàcil de fer mida de menys un,

336
00:15:47,880 --> 00:15:51,440
Arribo al final de la meva sèrie efectiva
on els nombres són, elimina 61.

337
00:15:51,440 --> 00:15:52,920
Però jo no vull treure 61.

338
00:15:52,920 --> 00:15:55,030
Vull aprofitar 50 anys, que
hi era en 05:00

339
00:15:55,030 --> 00:15:56,790
a la línia per al
nou iPhone o el que sigui.

340
00:15:56,790 --> 00:16:01,200
I així, per desfer-me d'50, em
no només pot fer això, oi?

341
00:16:01,200 --> 00:16:02,547
Puc ratllar 50.

342
00:16:02,547 --> 00:16:04,380
Però acabem de dir ens
no han de ser tan anal

343
00:16:04,380 --> 00:16:06,330
per guanyar-se o ocultar les dades.

344
00:16:06,330 --> 00:16:08,090
Només podem oblidar on és.

345
00:16:08,090 --> 00:16:12,330
>> Però si canvi de mida ara
2, és aquesta informació suficient

346
00:16:12,330 --> 00:16:15,711
saber el que està passant en la meva cua?

347
00:16:15,711 --> 00:16:16,680
No realment.

348
00:16:16,680 --> 00:16:19,830
Igual que la meva mida és dues, però
On comença la cua,

349
00:16:19,830 --> 00:16:22,980
especialment si encara tinc
aquests mateixos números a la memòria.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Així que he de recordar
ara a la part davantera és.

352
00:16:27,090 --> 00:16:29,630
I així com em vaig proposar dalt
allà, anem Acabem de trucada

353
00:16:29,630 --> 00:16:33,729
Front enèsim, la inicial
valor ha d'haver estat el que?

354
00:16:33,729 --> 00:16:35,270
Zero, només el començament de la llista.

355
00:16:35,270 --> 00:16:40,876
Però ara, a més de decrement
la mida, només incrementa el front.

356
00:16:40,876 --> 00:16:42,000
Ara aquí hi ha un altre problema.

357
00:16:42,000 --> 00:16:43,030
Així que una vegada que segueixo anant.

358
00:16:43,030 --> 00:16:47,520
Suposem que aquest és el nombre de
com 121, 124, i després, maleïda sigui,

359
00:16:47,520 --> 00:16:48,610
Estic fora d'espai.

360
00:16:48,610 --> 00:16:50,390
Però esperi un minut, jo no ho sóc.

361
00:16:50,390 --> 00:16:55,630
Així que en aquest punt de la història,
suposem que la mida és un, dos,

362
00:16:55,630 --> 00:17:00,370
tres, quatre, així que suposo que la
mida és quatre, el front és un,

363
00:17:00,370 --> 00:17:01,621
pel que és 51 a la part davantera.

364
00:17:01,621 --> 00:17:04,329
Vull posar un altre nombre aquí,
però, maleïda sigui, m'he quedat sense espai.

365
00:17:04,329 --> 00:17:06,710
Però jo no sóc realment, oi?

366
00:17:06,710 --> 00:17:11,192
On podria posar una mica
valor addicional, igual que 171?

367
00:17:11,192 --> 00:17:13,400
Només Sí, vaig poder tipus de
tornar per allà, oi?

368
00:17:13,400 --> 00:17:18,161
I després creuar la 50, o
simplement sobreescriure amb 171.

369
00:17:18,161 --> 00:17:20,410
I si vostè s'està preguntant per què
els nostres números van arribar tan a l'atzar,

370
00:17:20,410 --> 00:17:24,150
aquests són comunament preses equip
cursos de ciències a Harvard després CS50.

371
00:17:24,150 --> 00:17:27,510
Però això era una bona optimització,
perquè ara no estic perdent espai.

372
00:17:27,510 --> 00:17:30,750
Encara he de recordar
el gran que és total.

373
00:17:30,750 --> 00:17:31,500
És cinc en total.

374
00:17:31,500 --> 00:17:33,375
Perquè jo no vull
començar a sobreescriure 51.

375
00:17:33,375 --> 00:17:36,260
Així que ara estic encara sense espai,
per la qual cosa el mateix problema que abans.

376
00:17:36,260 --> 00:17:39,140
Però es pot veure com ara
en el codi, és probable que

377
00:17:39,140 --> 00:17:41,910
d'escriure una mica més
complexitat per fer que això passi.

378
00:17:41,910 --> 00:17:44,510
I de fet, el que l'operador
en C, probablement anem a

379
00:17:44,510 --> 00:17:48,110
que màgicament fa això la circularitat?

380
00:17:48,110 --> 00:17:50,160
Sí, l'operador de mòdul,
el signe de percentatge.

381
00:17:50,160 --> 00:17:53,160
Llavors, ¿què és una mena de fresc sobre una cua,
tot i que seguim matrius de dibuix

382
00:17:53,160 --> 00:17:56,520
ja que aquestes línies rectes com, si vostè
tipus de pensar en això com a corba

383
00:17:56,520 --> 00:18:00,341
voltant com un cercle, llavors només
intuïtivament quin tipus de treballs mentals

384
00:18:00,341 --> 00:18:01,590
Crec que una mica més neta.

385
00:18:01,590 --> 00:18:05,190
Vostè encara ha de posar en pràctica
aquest model mental en codi.

386
00:18:05,190 --> 00:18:07,550
Així que no és tan difícil,
en última instància, per a posar en pràctica,

387
00:18:07,550 --> 00:18:12,430
però encara perdem la size-- més aviat, la
capacitat de canviar la mida, tret que fem això.

388
00:18:12,430 --> 00:18:15,310
>> Hem de desfer-nos de la matriu, es
reemplaçar amb un únic punter,

389
00:18:15,310 --> 00:18:20,010
i després en algun lloc del meu codi tinc
Una crida el que funciona per a crear realitat

390
00:18:20,010 --> 00:18:23,720
la matriu de nombres anomenats?

391
00:18:23,720 --> 00:18:26,190
Malloc, o alguns similars
funció, exactament.

392
00:18:26,190 --> 00:18:30,481
Teniu alguna pregunta respecte piles o cues.

393
00:18:30,481 --> 00:18:30,980
Sí?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Bona pregunta.

396
00:18:34,240 --> 00:18:35,830
El mòdul usaries aquí.

397
00:18:35,830 --> 00:18:38,520
Així que en general, quan s'utilitza
mod, que ho faria

398
00:18:38,520 --> 00:18:40,620
amb la mida de la
estructura de dades sencera.

399
00:18:40,620 --> 00:18:44,120
Així que una cosa així com cinc o capacitat, si
és constant, és probablement involucrats.

400
00:18:44,120 --> 00:18:47,100
Però només fent mòdul de cinc
probablement no és suficient,

401
00:18:47,100 --> 00:18:51,380
perquè necessitem saber què hem
embolicar al voltant d'aquí o aquí o aquí.

402
00:18:51,380 --> 00:18:54,160
Així que vostè és probablement també
voldrà involucrar

403
00:18:54,160 --> 00:18:57,220
la mida de la cosa, o
la variable front també.

404
00:18:57,220 --> 00:19:00,140
Així que és només per aquesta relativament
expressió aritmètica simple,

405
00:19:00,140 --> 00:19:02,000
però mòdul seria l'ingredient clau.

406
00:19:02,000 --> 00:19:03,330
>> Així curtmetratge si es vol.

407
00:19:03,330 --> 00:19:05,780
Una animació que alguns
gent d'una altra universitat

408
00:19:05,780 --> 00:19:08,060
armem que hem
adaptada per a aquesta discussió.

409
00:19:08,060 --> 00:19:12,630
Es tracta de Jack l'aprenentatge de la
fets sobre les cues i estadístiques.

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

411
00:19:19,010 --> 00:19:21,890
>> PEL·LÍCULA: Hi havia una vegada,
hi havia un tipus anomenat Jack.

412
00:19:21,890 --> 00:19:25,330
Quan es tractava de fer amics,
Jack no té una habilitat especial.

413
00:19:25,330 --> 00:19:28,220
Així que Jack va anar a parlar amb el
més noi popular que sabia.

414
00:19:28,220 --> 00:19:30,920
Va ser a Lou i li va preguntar: Què faig?

415
00:19:30,920 --> 00:19:33,400
Lou va veure que el seu amic
estava molt angoixat.

416
00:19:33,400 --> 00:19:36,050
Bé, ell va començar, just
mira com estàs vestida.

417
00:19:36,050 --> 00:19:38,680
No tens res de roba
amb una mirada diferent?

418
00:19:38,680 --> 00:19:39,660
Sí, va dir Jack.

419
00:19:39,660 --> 00:19:40,840
És clar que sí.

420
00:19:40,840 --> 00:19:43,320
Vine a casa meva i
Vaig a mostrar a vostès.

421
00:19:43,320 --> 00:19:44,550
Així es van anar a Jack.

422
00:19:44,550 --> 00:19:47,520
I Jack va mostrar el quadre de Lou
on guardava totes les seves camises,

423
00:19:47,520 --> 00:19:49,260
i els seus pantalons i els mitjons.

424
00:19:49,260 --> 00:19:52,290
Lou va dir: Veig que tens
tota la roba en una pila.

425
00:19:52,290 --> 00:19:54,870
Per què no et poses una mica de
altres de tant en tant?

426
00:19:54,870 --> 00:19:58,020
>> Jack va dir, bé, quan jo
treure la roba i mitjons,

427
00:19:58,020 --> 00:20:00,780
Jo els rento i vaig posar
a les escombraries a la caixa.

428
00:20:00,780 --> 00:20:03,210
Després ve la següent
matí, i fins i tot em salt.

429
00:20:03,210 --> 00:20:06,380
Vaig a la caixa i obtinc
la meva roba de la part superior.

430
00:20:06,380 --> 00:20:09,070
Lou es va adonar ràpidament
el problema amb Jack.

431
00:20:09,070 --> 00:20:12,080
Va mantenir roba, CD,
i els llibres de la pila.

432
00:20:12,080 --> 00:20:14,420
Quan va arribar a
alguna cosa per llegir o portar,

433
00:20:14,420 --> 00:20:17,100
ell triaria el llibre superior o roba interior.

434
00:20:17,100 --> 00:20:19,500
Després, quan va acabar,
el posaria de tornada.

435
00:20:19,500 --> 00:20:21,970
Tornar aniria, a la part superior de la pila.

436
00:20:21,970 --> 00:20:24,460
Jo sé la solució,
va dir un Loud triomfant.

437
00:20:24,460 --> 00:20:27,090
Has d'aprendre a
comenci a utilitzar una cua.

438
00:20:27,090 --> 00:20:29,870
Lou va prendre la roba de Jack i
els va penjar a l'armari.

439
00:20:29,870 --> 00:20:32,710
I quan ell havia buidat
la caixa, ell simplement el va tirar.

440
00:20:32,710 --> 00:20:36,500
>> Després va dir, ara Jack, al final de
el dia, posar la roba a l'esquerra

441
00:20:36,500 --> 00:20:37,990
quan se'ls posa lluny.

442
00:20:37,990 --> 00:20:41,300
Llavors demà al matí quan es
veure el sol, posar-se la roba

443
00:20:41,300 --> 00:20:43,440
a la dreta, des del final de la línia.

444
00:20:43,440 --> 00:20:44,880
No ho veus? va dir Lou.

445
00:20:44,880 --> 00:20:46,370
Serà tan agradable.

446
00:20:46,370 --> 00:20:49,770
Et portes tot un cop
abans que et poses alguna cosa dues vegades.

447
00:20:49,770 --> 00:20:52,670
I amb tot, a les cues
en el seu armari i prestatge,

448
00:20:52,670 --> 00:20:55,160
Jack va començar a sentir
molt segur de si mateix.

449
00:20:55,160 --> 00:20:59,720
Tot gràcies a Lou i
seva meravellosa cua.

450
00:20:59,720 --> 00:21:01,220
ALTAVEU 1: Molt bé, és adorable.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Així que el que ha estat realment va
de sota la campana ara?

453
00:21:10,080 --> 00:21:12,370
Que tenim punters,
que tenim malloc,

454
00:21:12,370 --> 00:21:15,680
que tenim la capacitat de crear
trossos de memòria per a nosaltres mateixos

455
00:21:15,680 --> 00:21:16,344
dinàmicament.

456
00:21:16,344 --> 00:21:18,510
Així que aquesta és una imatge que ens
albirat l'altre dia.

457
00:21:18,510 --> 00:21:21,180
Nosaltres realment no habitem
en ella, però aquesta imatge

458
00:21:21,180 --> 00:21:24,180
ha estat succeint per sota
el capó des de fa setmanes.

459
00:21:24,180 --> 00:21:27,050
I pel que aquesta representa, simplement
un rectangle que hem dibuixat,

460
00:21:27,050 --> 00:21:28,180
la memòria de l'equip.

461
00:21:28,180 --> 00:21:31,850
I potser el seu ordinador, o CS50
Identificació, té un gigabyte de memòria o la memòria RAM

462
00:21:31,850 --> 00:21:33,050
o dos gigabytes o quatre.

463
00:21:33,050 --> 00:21:34,450
En realitat no importa.

464
00:21:34,450 --> 00:21:37,240
El seu sistema operatiu
Windows o Mac OS o Linux,

465
00:21:37,240 --> 00:21:41,120
essencialment li permet al seu programa
a pensar que té accés

466
00:21:41,120 --> 00:21:42,982
a la totalitat de
la memòria de l'equip,

467
00:21:42,982 --> 00:21:45,440
tot i que podria estar executant
diversos programes alhora.

468
00:21:45,440 --> 00:21:46,990
Així que en realitat, que no funciona molt bé.

469
00:21:46,990 --> 00:21:49,448
Però és una espècie d'il·lusió
donat a tots els seus programes.

470
00:21:49,448 --> 00:21:53,110
Així que si vostè tenia dos gigues de RAM, aquest
És així com l'equip podria pensar en ell.

471
00:21:53,110 --> 00:21:57,110
>> Ara és coincidència que un d'ells
coses, un d'aquests segments de memòria,

472
00:21:57,110 --> 00:21:58,350
es diu una pila.

473
00:21:58,350 --> 00:22:01,680
I, en efecte qualsevol moment
fins al moment en l'escriptura de codi

474
00:22:01,680 --> 00:22:05,900
que ha cridat
funció, per exemple principal.

475
00:22:05,900 --> 00:22:08,410
Recordo que cada vegada que tinc
la memòria de l'ordinador dibuixat,

476
00:22:08,410 --> 00:22:10,640
Sempre em baso tipus de
mitjà d'un rectangle aquí

477
00:22:10,640 --> 00:22:12,520
i no et molestis a parlar
sobre el que està a dalt.

478
00:22:12,520 --> 00:22:15,980
Perquè quan principal es diu, jo reclamo
que s'obté d'aquest tros de la memòria

479
00:22:15,980 --> 00:22:16,970
que passa per aquí.

480
00:22:16,970 --> 00:22:20,650
I si una funció principal anomenat
com swap, així bescanvi va aquí.

481
00:22:20,650 --> 00:22:23,720
I resulta, això és
on està acabant.

482
00:22:23,720 --> 00:22:26,277
En alguna cosa que es diu una pila
dins de la memòria de l'equip.

483
00:22:26,277 --> 00:22:28,360
Ara, al final del dia,
això és només aborda.

484
00:22:28,360 --> 00:22:30,680
És com zero bytes,
byte un, byte 2000000000.

485
00:22:30,680 --> 00:22:33,130
Però si es pensa en això
com aquest objecte rectangular,

486
00:22:33,130 --> 00:22:35,130
tot el que estem fent tots els
temps que anomenem una funció és

487
00:22:35,130 --> 00:22:37,180
capes d'un nou segment de memòria.

488
00:22:37,180 --> 00:22:41,700
Estem donant a aquesta funció una llesca
de la seva pròpia memòria per treballar.

489
00:22:41,700 --> 00:22:44,490
>> I recorda ara que això és important.

490
00:22:44,490 --> 00:22:46,400
Perquè si tenim
una mena d'intercanvi

491
00:22:46,400 --> 00:22:51,610
i dues variables locals com A i B i
canviem els valors d'un i dos

492
00:22:51,610 --> 00:22:55,130
a dos i un, el record
que quan torna d'intercanvi,

493
00:22:55,130 --> 00:22:58,330
és com si aquest tros
de la memòria simplement s'ha anat.

494
00:22:58,330 --> 00:23:00,080
En realitat, segueix sent
hi ha forense.

495
00:23:00,080 --> 00:23:01,940
I alguna cosa encara està realment allà.

496
00:23:01,940 --> 00:23:05,410
Però conceptualment, és com
encara que ha desaparegut del tot.

497
00:23:05,410 --> 00:23:10,910
I així principal no sap qualsevol dels treballs
que es va fer en aquesta funció d'intercanvi,

498
00:23:10,910 --> 00:23:14,890
llevat que en realitat va passar en els
arguments de punter o de referència.

499
00:23:14,890 --> 00:23:17,790
Ara, la solució fonamental
a aquest problema d'intercanvi

500
00:23:17,790 --> 00:23:19,970
és passar les coses en la seva direcció.

501
00:23:19,970 --> 00:23:23,250
Però resulta que, també, el que és
estat passant per sobre d'aquesta part

502
00:23:23,250 --> 00:23:26,330
del rectangle de tot aquest temps és
però, hi ha més memòria fins allà.

503
00:23:26,330 --> 00:23:28,790
I quan dinàmicament
assignar memòria,

504
00:23:28,790 --> 00:23:32,020
ja sigui a l'interior de GetString, que
que hem estat fent per a vostè en el CS50

505
00:23:32,020 --> 00:23:34,710
biblioteca, o si vostès
trucar a malloc i demanar

506
00:23:34,710 --> 00:23:37,950
el sistema operatiu d'un tros de
memòria, que no ve de la pila.

507
00:23:37,950 --> 00:23:40,960
Ve d'un altre lloc
en la memòria del seu ordinador

508
00:23:40,960 --> 00:23:42,220
això es diu el munt.

509
00:23:42,220 --> 00:23:43,430
I això no és res diferent.

510
00:23:43,430 --> 00:23:44,285
És la mateixa memòria RAM.

511
00:23:44,285 --> 00:23:45,160
És la mateixa memòria.

512
00:23:45,160 --> 00:23:49,080
És només la memòria RAM que és fins
allà en comptes d'aquí.

513
00:23:49,080 --> 00:23:50,750
>> I així, què vol dir això?

514
00:23:50,750 --> 00:23:53,650
Bé, si l'equip té
una quantitat finita de memòria

515
00:23:53,650 --> 00:23:57,450
i la pila està creixent, de manera que
parlar, i el munt, d'acord

516
00:23:57,450 --> 00:23:59,349
a aquesta fletxa, està creixent cap avall.

517
00:23:59,349 --> 00:24:01,140
En altres paraules, cada
vegada que es diu a malloc,

518
00:24:01,140 --> 00:24:03,430
que està sent donat una llesca
de la memòria des de dalt,

519
00:24:03,430 --> 00:24:06,630
llavors potser una mica més baix, després una mica
inferior, cada vegada que es diu a malloc,

520
00:24:06,630 --> 00:24:10,100
el munt, és l'ús,
és una espècie de creixement,

521
00:24:10,100 --> 00:24:11,950
creixent més i més al que?

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

523
00:24:13,382 --> 00:24:14,840
Així que això sembla una bona idea?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Vull dir, quan en realitat no és clara
Què més es pot fer si només

526
00:24:22,140 --> 00:24:23,910
tenen una quantitat finita de memòria.

527
00:24:23,910 --> 00:24:25,200
Però això és segurament dolent.

528
00:24:25,200 --> 00:24:27,920
Aquests dos fletxes estan en una
Curs accelerat per l'altre.

529
00:24:27,920 --> 00:24:31,930
>> I resulta que els dolents, la gent que
són particularment bo amb la programació,

530
00:24:31,930 --> 00:24:36,140
i tractant d'introduir en els ordinadors,
pot explotar aquesta realitat.

531
00:24:36,140 --> 00:24:38,290
De fet, considerarem
un petit fragment.

532
00:24:38,290 --> 00:24:41,350
Així que aquest és un exemple, vostè pot llegir
sobre amb més detall a la Viquipèdia.

533
00:24:41,350 --> 00:24:43,100
T'indiquem en el
article si curiosa.

534
00:24:43,100 --> 00:24:45,650
Però hi ha un atac general
conegut com desbordament de memòria intermèdia que

535
00:24:45,650 --> 00:24:49,570
ha existit durant tant de temps com els humans
han tingut la capacitat de manipular

536
00:24:49,570 --> 00:24:53,120
la memòria de l'ordinador, especialment en C.
Així que aquest és un programa molt arbitrària,

537
00:24:53,120 --> 00:24:55,130
però llegirem de baix a dalt.

538
00:24:55,130 --> 00:24:57,650
Principal a estrella argc carbó argv.

539
00:24:57,650 --> 00:24:59,830
Així que és un programa que usa
arguments de la línia d'ordres.

540
00:24:59,830 --> 00:25:03,620
I tot principal no sembla és cridar
una funció, en diuen F per la simplicitat.

541
00:25:03,620 --> 00:25:04,610
I que passa en què?

542
00:25:04,610 --> 00:25:05,490
Argv d'un.

543
00:25:05,490 --> 00:25:09,320
Per tant, passa a la F el
la paraula és que l'usuari va escriure

544
00:25:09,320 --> 00:25:11,500
en l'indicador després de la
El nom del programa en absolut.

545
00:25:11,500 --> 00:25:15,730
Tant com Cèsar o Vigenère, que
es pot recordar fent amb argv.

546
00:25:15,730 --> 00:25:16,680
>> Llavors, què és F?

547
00:25:16,680 --> 00:25:19,760
F porta en una cadena
com a únic argument,

548
00:25:19,760 --> 00:25:22,100
També conegut com un estel char, mateixa
cosa, com una cadena.

549
00:25:22,100 --> 00:25:24,920
I es diu arbitràriament
bar a aquest exemple.

550
00:25:24,920 --> 00:25:27,710
I després carbó c 12,
només en termes senzills,

551
00:25:27,710 --> 00:25:31,750
el que és carbó c suporti 12 fent per nosaltres?

552
00:25:31,750 --> 00:25:33,440
Què es fa?

553
00:25:33,440 --> 00:25:36,490
L'assignació de memòria, específicament
12 bytes per a 12 caràcters.

554
00:25:36,490 --> 00:25:36,990
Exactament.

555
00:25:36,990 --> 00:25:40,000
I després l'última línia, remenar i
còpia, vostè probablement no es veu.

556
00:25:40,000 --> 00:25:43,360
Aquesta és una còpia de cadena
funció el propòsit en la vida

557
00:25:43,360 --> 00:25:48,160
és copiar el seu segon argument
en el seu primer argument,

558
00:25:48,160 --> 00:25:51,190
però només fins a una
cert nombre de bytes.

559
00:25:51,190 --> 00:25:53,860
Així que el tercer argument diu,
quants bytes de copiar?

560
00:25:53,860 --> 00:25:56,720
La longitud de la barra,
qualsevol que sigui l'usuari va escriure en.

561
00:25:56,720 --> 00:25:59,320
I el contingut de
bar, aquesta cadena, són

562
00:25:59,320 --> 00:26:02,330
còpia en la memòria apuntada en l'C.

563
00:26:02,330 --> 00:26:04,060
>> Així que això sembla una mica estúpid, i ho és.

564
00:26:04,060 --> 00:26:06,300
És un exemple artificial,
però és representativa

565
00:26:06,300 --> 00:26:10,100
d'una classe de vectors d'atac,
una manera d'atacar un programa.

566
00:26:10,100 --> 00:26:15,050
Tot està bé i bo si l'usuari
tipus en una paraula que és 11 caràcters

567
00:26:15,050 --> 00:26:18,040
o menys, a més de la barra invertida zero.

568
00:26:18,040 --> 00:26:22,830
Què passa si l'usuari escriu en més de
11 o 12 o 20 o 50 caràcters?

569
00:26:22,830 --> 00:26:25,090
Quin és aquest programa va a fer?

570
00:26:25,090 --> 00:26:29,360
Culpa Potencialment seg. Va
copiar cegament tot el que a la barra de dalt

571
00:26:29,360 --> 00:26:31,750
a la seva longitud, que és
literalment tot al bar,

572
00:26:31,750 --> 00:26:36,307
en la direcció apuntant a C. Però C
només s'ha donat de manera preventiva com de 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Però no hi ha cap comprovació addicional.

574
00:26:37,640 --> 00:26:38,700
No hi ha, si les condicions.

575
00:26:38,700 --> 00:26:40,580
No hi ha cap comprovació d'errors aquí.

576
00:26:40,580 --> 00:26:43,270
>> I així el que aquest programa és
farem és a cegues

577
00:26:43,270 --> 00:26:45,750
copiar una cosa a l'altra.

578
00:26:45,750 --> 00:26:47,880
I així, si tracem aquest
com una imatge, aquí està

579
00:26:47,880 --> 00:26:49,860
Només una petita porció de l'espai de memòria.

580
00:26:49,860 --> 00:26:53,470
Així que notem a la part inferior, que
tenir la barra de variable local.

581
00:26:53,470 --> 00:26:57,330
Així que aquest punter que va a almacén--
més aviat que l'argument local que és

582
00:26:57,330 --> 00:26:58,672
va a emmagatzemar la barra de cadena.

583
00:26:58,672 --> 00:27:00,380
I després tan sols
per sobre d'ella en una pila,

584
00:27:00,380 --> 00:27:02,505
perquè cada vegada que demanes
per a la memòria a la pila,

585
00:27:02,505 --> 00:27:04,310
va una mica
per sobre d'ella il·lustrat,

586
00:27:04,310 --> 00:27:06,270
avís que tenim 12 bytes allà.

587
00:27:06,270 --> 00:27:10,690
El superior esquerre és el suport C zero i
la part inferior dreta és C suport d'11.

588
00:27:10,690 --> 00:27:12,870
Així és com els ordinadors
va a asseure a terme.

589
00:27:12,870 --> 00:27:18,300
Així que només intuïtivament, si la barra té més
de 12 caràcters en total, incloent

590
00:27:18,300 --> 00:27:25,790
la barra invertida zero, ¿on és el
12 o el suport de C 12 a anar?

591
00:27:25,790 --> 00:27:28,440
O més aviat ¿on és el dia 12
caràcter o el caràcter 13,

592
00:27:28,440 --> 00:27:30,900
el caràcter centèsima anar
per acabar a la foto?

593
00:27:30,900 --> 00:27:33,400
Per sobre o per sota?

594
00:27:33,400 --> 00:27:36,300
>> És clar, perquè tot i que
la pròpia pila creix cap amunt,

595
00:27:36,300 --> 00:27:39,590
una vegada que hagi posat coses en
això, per raons de disseny,

596
00:27:39,590 --> 00:27:41,294
posa la memòria de dalt a baix.

597
00:27:41,294 --> 00:27:44,460
Així que si vostè té més de 12 bytes,
vostè va a començar a sobreescriure bar.

598
00:27:44,460 --> 00:27:47,280
Això sí que és un error, però és
no és realment un gran problema.

599
00:27:47,280 --> 00:27:51,130
Però és una gran cosa, perquè no hi ha
més coses que estan passant a la memòria.

600
00:27:51,130 --> 00:27:53,074
Així que aquí està com podríem
posar hola, per ser clars.

601
00:27:53,074 --> 00:27:54,490
Si he escrit en hola en l'indicador.

602
00:27:54,490 --> 00:27:59,330
Barra invertida zero H-E-L-L-O, acaba dins
aquests 12 bytes, i estem super segur.

603
00:27:59,330 --> 00:28:00,330
Tot està bé.

604
00:28:00,330 --> 00:28:03,020
Però si escric alguna cosa
més llarg, que és potencialment

605
00:28:03,020 --> 00:28:05,860
va arrossegar-se en l'espai bar.

606
00:28:05,860 --> 00:28:08,405
Però pitjor encara, resulta
fora de tot aquest temps,

607
00:28:08,405 --> 00:28:11,530
tot i que mai hem parlat de
ella, la pila s'utilitza per a altres coses.

608
00:28:11,530 --> 00:28:13,560
No són només les variables locals.

609
00:28:13,560 --> 00:28:15,100
>> C és un llenguatge de nivell molt baix.

610
00:28:15,100 --> 00:28:17,810
I és una espècie de secret
fa servir la pila també

611
00:28:17,810 --> 00:28:21,260
recordar quan un
funció es diu, el que

612
00:28:21,260 --> 00:28:26,040
la direcció és de la funció anterior,
pel que pot saltar de nou a aquesta funció.

613
00:28:26,040 --> 00:28:29,980
Així que quan les trucades principals intercanvien, entre
les coses s'insereixen en la pila

614
00:28:29,980 --> 00:28:34,380
no són només intercanvia variables locals,
o els seus arguments, també van empènyer en secret

615
00:28:34,380 --> 00:28:37,510
a la pila tal com es representa
per la llesca vermell aquí,

616
00:28:37,510 --> 00:28:40,520
és l'adreça del principal físicament
en la memòria del seu ordinador,

617
00:28:40,520 --> 00:28:44,180
de manera que quan es fa d'intercanvi, l'ordinador
sap que he de tornar a la principal

618
00:28:44,180 --> 00:28:46,760
i acabar l'execució de la funció principal.

619
00:28:46,760 --> 00:28:51,960
Així que això és perillós ara, perquè si
l'usuari escriu així més de hola,

620
00:28:51,960 --> 00:28:57,030
de tal manera que clobbers l'entrada de l'usuari
o sobreescriu aquesta secció vermella,

621
00:28:57,030 --> 00:28:59,820
lògicament si l'ordinador
només va a assumir cegament

622
00:28:59,820 --> 00:29:03,830
que els bytes en aquesta llesca vermell són
la direcció a la que ha de tornar,

623
00:29:03,830 --> 00:29:09,020
¿I si l'adversari és prou intel·ligent o
la sort de posar una seqüència de bytes

624
00:29:09,020 --> 00:29:13,450
cal s'assembla a una adreça,
però és la direcció de codi

625
00:29:13,450 --> 00:29:18,730
que ell o ella vol que l'equip
per executar en lloc de principal?

626
00:29:18,730 --> 00:29:21,670
>> En altres paraules, si el que el
usuari està escrivint en l'indicador,

627
00:29:21,670 --> 00:29:23,850
no és només una cosa
com innòcua hola,

628
00:29:23,850 --> 00:29:28,210
però en realitat és un codi que és equivalent
eliminar tots els arxius d'aquest usuari?

629
00:29:28,210 --> 00:29:30,060
O un correu electrònic la contrasenya a mi?

630
00:29:30,060 --> 00:29:31,940
O iniciar el registre de la seva
pulsacions de teclat, oi?

631
00:29:31,940 --> 00:29:34,920
Hi ha un camí, anem a estipulen avui,
que podien escriure no només hola

632
00:29:34,920 --> 00:29:36,711
mundial o el seu nom,
que podien essencialment

633
00:29:36,711 --> 00:29:39,570
Va esdevenir en codi, zeros i
estimats, que l'ordinador

634
00:29:39,570 --> 00:29:43,450
errors tant de codi i una adreça.

635
00:29:43,450 --> 00:29:48,950
Així que encara que una mica abstracte, si el
usuari escriu prou codi acusatori

636
00:29:48,950 --> 00:29:52,330
que anem a generalitzar aquí
A. A és atac o adversaris.

637
00:29:52,330 --> 00:29:53,140
Així les coses simplement dolent.

638
00:29:53,140 --> 00:29:55,306
No importa el
números o els zeros o uns

639
00:29:55,306 --> 00:29:59,470
avui en dia, de manera que vostè acaba
sobreescriure aquesta secció vermella,

640
00:29:59,470 --> 00:30:01,580
notar que seqüència de bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C zero vuit zero.

642
00:30:05,020 --> 00:30:08,960
I ara com article de Wikipedia aquí
ha proposat, si ara de començar

643
00:30:08,960 --> 00:30:12,460
etiquetatge dels bytes en el seu equip de
la memòria, el que l'article de Wikipedia és

644
00:30:12,460 --> 00:30:19,060
proposant és que, què passa si la direcció
d'aquest byte superior esquerra és 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> En altres paraules, si el dolent de la pel·lícula és
prou intel·ligent amb el seu codi

646
00:30:22,200 --> 00:30:26,650
per posar en realitat un nombre aquí que
correspon a la direcció del codi

647
00:30:26,650 --> 00:30:29,180
ell o ella injecta
en l'equip,

648
00:30:29,180 --> 00:30:31,050
pot enganyar l'ordinador
a fer qualsevol cosa.

649
00:30:31,050 --> 00:30:34,140
L'eliminació d'arxius, correu electrònic
coses, ensumant el seu trànsit,

650
00:30:34,140 --> 00:30:36,710
literalment, qualsevol cosa podria ser
injectada a l'ordinador.

651
00:30:36,710 --> 00:30:39,220
I així un desbordament de memòria intermèdia
atac en el seu nucli

652
00:30:39,220 --> 00:30:43,530
és només un estúpid, estúpid
primordial d'una matriu que

653
00:30:43,530 --> 00:30:45,840
no tenen els seus límits comprovats.

654
00:30:45,840 --> 00:30:48,850
I això és el que és super perillós
i alhora súper poderós

655
00:30:48,850 --> 00:30:52,560
en C és que nosaltres tenim de fet
accés a qualsevol lloc de la memòria.

656
00:30:52,560 --> 00:30:55,320
Tot depèn de nosaltres, els programadors,
que escriuen el codi original

657
00:30:55,320 --> 00:30:59,330
per comprovar la longitud de qualsevol maleït
matrius que estem manipulant.

658
00:30:59,330 --> 00:31:00,750
Així que perquè quedi clar, quina és la solució?

659
00:31:00,750 --> 00:31:03,190
Si rodem de nou a aquest
codi, no només ha de

660
00:31:03,190 --> 00:31:08,000
canviar la longitud de la barra, el que
més he revisaré?

661
00:31:08,000 --> 00:31:10,620
Què més he de fer per
prevenir aquest atac del tot?

662
00:31:10,620 --> 00:31:14,110
No vull dir simplement cegament
que copiï tants bytes

663
00:31:14,110 --> 00:31:16,140
com és la longitud de la barra.

664
00:31:16,140 --> 00:31:18,910
Vull dir, copiar com
molts bytes com estan a la barra

665
00:31:18,910 --> 00:31:24,090
fins l'assignat
memòria, o 12 com a màxim.

666
00:31:24,090 --> 00:31:27,450
Així que necessito algun tipus de condició if
que fa comprovar la longitud de la barra,

667
00:31:27,450 --> 00:31:32,800
però si és superior a 12, només dura codi
12 com a la distància màxima possible.

668
00:31:32,800 --> 00:31:35,910
Altrament, el tampó de trucada
atac de desbordament pot succeir.

669
00:31:35,910 --> 00:31:38,451
A la part inferior de les diapositives,
si tens curiositat per llegir més

670
00:31:38,451 --> 00:31:41,200
és l'article original real
si vols fer una ullada.

671
00:31:41,200 --> 00:31:44,550
>> Però ara, entre els preus
pagats aquí va ser ineficiències.

672
00:31:44,550 --> 00:31:46,680
Així que va ser una ràpida
baix nivell ullada al que

673
00:31:46,680 --> 00:31:49,709
poden sorgir problemes ara que
tenir accés a la memòria de l'ordinador.

674
00:31:49,709 --> 00:31:51,750
Però un altre problema que
ja ensopegat dilluns

675
00:31:51,750 --> 00:31:53,800
era només la ineficàcia
d'una llista enllaçada.

676
00:31:53,800 --> 00:31:56,019
Estem de tornada a temps lineal.

677
00:31:56,019 --> 00:31:57,560
Ja no tenim una matriu contigua.

678
00:31:57,560 --> 00:31:58,980
No tenim accés aleatori.

679
00:31:58,980 --> 00:32:00,710
No podem usar la notació de claudàtors.

680
00:32:00,710 --> 00:32:04,590
Literalment, cal utilitzar un bucle while
com la que jo vaig escriure fa un moment.

681
00:32:04,590 --> 00:32:09,740
Però el dilluns, reclamem que podem
colar-se de nou en l'àmbit de l'eficiència

682
00:32:09,740 --> 00:32:13,040
aconseguir alguna cosa que és
logarítmica, potser, o millor encara,

683
00:32:13,040 --> 00:32:16,120
potser fins i tot una cosa que és
l'anomenada constant de temps.

684
00:32:16,120 --> 00:32:19,840
Llavors, com podem fer que en utilitzar aquests nous
eines, aquestes direccions, aquests indicadors,

685
00:32:19,840 --> 00:32:22,210
i roscat coses de nosaltres mateixos?

686
00:32:22,210 --> 00:32:23,960
Bé, suposem que
aquí, es tracta d'un grup

687
00:32:23,960 --> 00:32:27,170
dels números que volem emmagatzemar en un
estructura de dades i recerca eficient.

688
00:32:27,170 --> 00:32:30,960
Sens dubte ens podem retrocedir a la setmana
2, llençar aquests en una matriu,

689
00:32:30,960 --> 00:32:33,150
i la recerca d'ells mitjançant la recerca binària.

690
00:32:33,150 --> 00:32:34,040
Divideix i venceràs.

691
00:32:34,040 --> 00:32:37,720
I, de fet, que va escriure
recerca binària en PSET3,

692
00:32:37,720 --> 00:32:40,100
on es va implementar el programa de cerca.

693
00:32:40,100 --> 00:32:40,890
Però saps què.

694
00:32:40,890 --> 00:32:45,060
Hi ha una espècie de més
forma intel·ligent de fer-ho.

695
00:32:45,060 --> 00:32:47,390
És una mica més
sofisticat i potser

696
00:32:47,390 --> 00:32:50,830
ens permet veure què binària
recerca és molt més ràpid.

697
00:32:50,830 --> 00:32:52,980
En primer lloc, anem a introduir
la noció d'un arbre.

698
00:32:52,980 --> 00:32:54,730
Que tot i que en
arbres realitat tipus de

699
00:32:54,730 --> 00:32:57,730
creixent així, en el món de la informàtica
la ciència que tipus de créixer cap avall

700
00:32:57,730 --> 00:33:00,830
com un arbre de família, on vostè ha
seus avis o besavis

701
00:33:00,830 --> 00:33:04,580
o el que sigui en la part superior, el patriarca i
la matriarca de la família, només un

702
00:33:04,580 --> 00:33:07,930
anomenada arrel, node, per sota
quals són els seus fills,

703
00:33:07,930 --> 00:33:11,442
per sota del qual són els seus fills, o
seus descendents en general.

704
00:33:11,442 --> 00:33:13,400
I qualsevol penjant
la part inferior de la família

705
00:33:13,400 --> 00:33:16,070
arbre, a més de ser el
més jove de la família,

706
00:33:16,070 --> 00:33:19,520
també pot ser només genèricament
anomenat les fulles de l'arbre.

707
00:33:19,520 --> 00:33:21,800
>> Així que això és només un munt
de paraules i definicions

708
00:33:21,800 --> 00:33:25,790
d'una cosa que es diu un arbre en equip
la ciència, com un arbre genealògic.

709
00:33:25,790 --> 00:33:28,770
Però hi ha encarnacions més elegants
d'arbres, un dels quals

710
00:33:28,770 --> 00:33:30,780
es diu un arbre de cerca binari.

711
00:33:30,780 --> 00:33:34,380
I vostè pot classe de presa de pèl
a part el que fa aquesta cosa.

712
00:33:34,380 --> 00:33:37,180
Bé, és binari en quin sentit?

713
00:33:37,180 --> 00:33:41,455
D'on ve el binari ve d'aquí?

714
00:33:41,455 --> 00:33:41,955
Ho sentim?

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

716
00:33:45,961 --> 00:33:47,210
No és tant un bé o.

717
00:33:47,210 --> 00:33:52,000
És més que cada un dels nodes no té
més de dos fills, com veiem aquí.

718
00:33:52,000 --> 00:33:54,990
En general, un tree-- i
seus pares i avis

719
00:33:54,990 --> 00:33:57,640
pot tenir tants fills o
néts, ja que realment volen,

720
00:33:57,640 --> 00:34:00,820
i així, per exemple, no tenim tres
els nens fora d'aquest node mà dreta,

721
00:34:00,820 --> 00:34:05,480
però en un arbre binari, un node té
zero, un o dos fills com a màxim.

722
00:34:05,480 --> 00:34:08,496
I això és una bona propietat,
perquè si està coronada per dos,

723
00:34:08,496 --> 00:34:10,620
serem capaços de
obtenir una mica de base de registre de dos

724
00:34:10,620 --> 00:34:11,975
acció passant aquí en última instància.

725
00:34:11,975 --> 00:34:13,350
Així que tenim alguna cosa logarítmica.

726
00:34:13,350 --> 00:34:14,558
Però més sobre això en un moment.

727
00:34:14,558 --> 00:34:19,810
Cerca arbre vol dir que els números són
disposat de tal manera que el fill esquerre de

728
00:34:19,810 --> 00:34:22,429
valor és més gran que l'arrel.

729
00:34:22,429 --> 00:34:26,010
I el seu fill dret és
més gran que l'arrel.

730
00:34:26,010 --> 00:34:29,290
En altres paraules, si vostè pren algun dels
limfàtics, els cercles en aquesta imatge,

731
00:34:29,290 --> 00:34:31,840
i mira a la seva esquerra
nen i el seu fill dret,

732
00:34:31,840 --> 00:34:34,739
el primer ha de ser inferior a,
la segona ha de ser més gran que.

733
00:34:34,739 --> 00:34:36,159
Així seny comprovar 55.

734
00:34:36,159 --> 00:34:37,780
Es nen deixat és 33.

735
00:34:37,780 --> 00:34:38,620
És menys.

736
00:34:38,620 --> 00:34:40,929
55, el seu fill dret és 77.

737
00:34:40,929 --> 00:34:41,783
És més gran que.

738
00:34:41,783 --> 00:34:43,199
I això és una definició recursiva.

739
00:34:43,199 --> 00:34:46,480
Podríem revisar cada un dels
nodes i el mateix patró obstaculitzin.

740
00:34:46,480 --> 00:34:49,389
>> Així que el que és bo en un
arbre binari de recerca, és

741
00:34:49,389 --> 00:34:52,204
que un, podem posar-lo en pràctica
amb una estructura, igual que aquest.

742
00:34:52,204 --> 00:34:54,620
I tot i que estem llançant
un munt d'estructures en la seva,

743
00:34:54,620 --> 00:34:56,560
són un tant
intuïtiva ara amb sort.

744
00:34:56,560 --> 00:35:00,570
La sintaxi és encara arcana amb certesa,
però el contingut d'un node en aquest

745
00:35:00,570 --> 00:35:02,786
context-- i guardem
usant el node paraula,

746
00:35:02,786 --> 00:35:04,910
si es tracta d'un rectangle
a la pantalla o un cercle,

747
00:35:04,910 --> 00:35:08,970
que és només una mica de contenidor genèric,
en aquest cas d'un arbre, com el que es

748
00:35:08,970 --> 00:35:11,780
vam veure, necessitem un nombre enter
en cada un dels nodes

749
00:35:11,780 --> 00:35:15,460
i llavors necessito dos punters apuntant
al fill esquerre i el fill dret,

750
00:35:15,460 --> 00:35:16,590
respectivament.

751
00:35:16,590 --> 00:35:20,730
Així que aquesta és la forma en què podria
implementar que en una estructura.

752
00:35:20,730 --> 00:35:22,315
I com podria jo posar en pràctica en el codi?

753
00:35:22,315 --> 00:35:26,730
Bé, anem a fer un ràpid
mirar a aquest petit exemple.

754
00:35:26,730 --> 00:35:29,820
No és funcional, però he
copiat i enganxat aquesta estructura.

755
00:35:29,820 --> 00:35:33,510
I si la meva funció per a un binari
arbre de cerca es diu recerca,

756
00:35:33,510 --> 00:35:36,980
i això té dos arguments,
1 N sencer i un punter

757
00:35:36,980 --> 00:35:41,400
a un node, de manera que un punter a l'arbre
o un punter a l'arrel d'un arbre,

758
00:35:41,400 --> 00:35:43,482
com faig per a la recerca de N?

759
00:35:43,482 --> 00:35:45,440
Bé, en primer lloc, perquè sóc
tractar amb punters,

760
00:35:45,440 --> 00:35:46,750
Jo vaig a fer una comprovació de validesa.

761
00:35:46,750 --> 00:35:54,279
Si és igual als iguals arbre nul, és N
en aquest arbre o no en aquest arbre?

762
00:35:54,279 --> 00:35:55,070
No pot ser, oi?

763
00:35:55,070 --> 00:35:56,870
Si estic passat nul,
no hi ha res allà.

764
00:35:56,870 --> 00:35:59,230
Pot ser que també acaba de
cegament dir return false.

765
00:35:59,230 --> 00:36:04,050
Si em dones res, segurament no pot
trobar qualsevol nombre N. Llavors, què més podria jo

766
00:36:04,050 --> 00:36:04,750
comprovi ara?

767
00:36:04,750 --> 00:36:12,830
Jo vaig a dir així més si N és
menys del que està en el node de l'arbre

768
00:36:12,830 --> 00:36:16,300
que he estat lliurar valor N.

769
00:36:16,300 --> 00:36:20,270
En altres paraules, si el nombre estic
buscant, N, és menor que el node

770
00:36:20,270 --> 00:36:21,340
que estic mirant.

771
00:36:21,340 --> 00:36:23,190
I el node estic buscant
per la qual cosa es diu arbre,

772
00:36:23,190 --> 00:36:26,370
i recordar l'exemple anterior
per obtenir el valor d'un punter,

773
00:36:26,370 --> 00:36:28,310
Utilitzo la notació fletxa.

774
00:36:28,310 --> 00:36:35,960
Així que si n és menor que l'arbre fletxa
N, vull anar conceptualment esquerra.

775
00:36:35,960 --> 00:36:38,590
Com puc expressar searching vaig ser?

776
00:36:38,590 --> 00:36:41,560
Perquè quedi clar, si això és
la imatge en qüestió,

777
00:36:41,560 --> 00:36:44,612
i m'han passat aquesta superior
arrow això està apuntant cap avall.

778
00:36:44,612 --> 00:36:45,570
Aquesta és la meva punter del arbre.

779
00:36:45,570 --> 00:36:48,060
Estic apuntant a l'arrel de l'arbre.

780
00:36:48,060 --> 00:36:52,100
I estic buscant per exemple, per
el número 44, de manera arbitrària.

781
00:36:52,100 --> 00:36:55,300
És 44 menor o
més gran que 55 òbviament?

782
00:36:55,300 --> 00:36:56,360
Així que és menys.

783
00:36:56,360 --> 00:36:58,760
I pel que aquesta condició s'aplica si.

784
00:36:58,760 --> 00:37:03,981
Així conceptualment, el que és el que vull
buscar següent si estic buscant 44?

785
00:37:03,981 --> 00:37:04,480
Sí?

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

787
00:37:08,310 --> 00:37:11,100
>> Exactament, vull
buscar el fill esquerre,

788
00:37:11,100 --> 00:37:12,789
o el sub-arbre de l'esquerra d'aquesta imatge.

789
00:37:12,789 --> 00:37:14,830
I, de fet, em va deixar a través
la imatge aquí sota

790
00:37:14,830 --> 00:37:17,770
per un moment, ja que
No puc esgarrapar això.

791
00:37:17,770 --> 00:37:21,150
Si començo aquí a 55, i
Sé que el valor 44

792
00:37:21,150 --> 00:37:23,180
Jo estic buscant és a
l'esquerra, és una espècie

793
00:37:23,180 --> 00:37:26,010
de com arrencar la guia telefònica en
mitjà o esquinçar l'arbre per la meitat.

794
00:37:26,010 --> 00:37:29,660
Jo ja no he de preocupar
tot aquest mitjà de l'arbre.

795
00:37:29,660 --> 00:37:33,270
I, no obstant això, curiosament, en termes de la
estructura, aquesta cosa aquí que

796
00:37:33,270 --> 00:37:36,682
comença amb 33, que la mateixa
és un arbre de cerca binària.

797
00:37:36,682 --> 00:37:39,890
Vaig dir la paraula recurrent abans perquè
de fet aquesta és una estructura de dades que

798
00:37:39,890 --> 00:37:41,707
per definició és recursiva.

799
00:37:41,707 --> 00:37:44,540
És possible que tingui un arbre que és això
gran, però cada un dels seus fills

800
00:37:44,540 --> 00:37:46,870
representa un arbre una mica més petit.

801
00:37:46,870 --> 00:37:50,910
En lloc de que sigui l'avi
o l'àvia, ara és només mare

802
00:37:50,910 --> 00:37:54,300
o-- No puc no dir-- mare
o pare, això seria estrany.

803
00:37:54,300 --> 00:37:59,000
En lloc dels dos nens allà
seria com germà i germana.

804
00:37:59,000 --> 00:38:01,120
Una nova generació de l'arbre genealògic.

805
00:38:01,120 --> 00:38:02,900
Però estructuralment, és la mateixa idea.

806
00:38:02,900 --> 00:38:06,790
I resulta que tinc una funció
amb el qual puc buscar una recerca binària

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

808
00:38:07,290 --> 00:38:08,680
Es diu cerca.

809
00:38:08,680 --> 00:38:17,870
Busco N en arbre de fletxa esquerra
else if N és més gran que el valor

810
00:38:17,870 --> 00:38:18,870
que sóc actualment.

811
00:38:18,870 --> 00:38:20,800
55 en la història fa un moment.

812
00:38:20,800 --> 00:38:23,780
Tinc una funció anomenada
recerca que puc simplement

813
00:38:23,780 --> 00:38:29,660
N passar això i buscar de forma recursiva
el sub-arbre i acaba de retorn

814
00:38:29,660 --> 00:38:30,620
sigui quina sigui la resposta.

815
00:38:30,620 --> 00:38:33,530
Else Tinc una mica de cas base final aquí.

816
00:38:33,530 --> 00:38:35,310
>> Quin és l'últim cas?

817
00:38:35,310 --> 00:38:36,570
Arbre és o bé nul.

818
00:38:36,570 --> 00:38:39,980
El valor o jo estic buscant és
menys del que o més gran que la

819
00:38:39,980 --> 00:38:42,610
o igual a ella.

820
00:38:42,610 --> 00:38:44,750
I jo podria dir igual
iguals, però lògicament és

821
00:38:44,750 --> 00:38:46,500
equivalent a només dir més aquí.

822
00:38:46,500 --> 00:38:49,150
Tan cert és el que trobo alguna cosa.

823
00:38:49,150 --> 00:38:51,710
Així que espero que aquest és un
Fins i tot exemple més convincent

824
00:38:51,710 --> 00:38:54,900
que la funció sigma estúpid
vam fer un parell de conferències esquena,

825
00:38:54,900 --> 00:38:58,360
on era tan fàcil d'usar un bucle
per explicar tots els números d'un

826
00:38:58,360 --> 00:39:02,390
a N. Aquí, amb una estructura de dades
que en si és de forma recursiva

827
00:39:02,390 --> 00:39:07,050
Definim i recursiva atrets, ara
tenir la capacitat d'expressar-nos

828
00:39:07,050 --> 00:39:09,780
en el codi que sí és recursiu.

829
00:39:09,780 --> 00:39:12,580
Així que aquest és el mateix codi exacte aquí.

830
00:39:12,580 --> 00:39:14,400
>> Llavors, quins altres problemes podem resoldre?

831
00:39:14,400 --> 00:39:18,160
Així que un ràpid pas de distància de
arbres per un moment.

832
00:39:18,160 --> 00:39:20,130
Aquí és, diguem, la bandera alemanya.

833
00:39:20,130 --> 00:39:22,020
I hi ha clarament una
patró per a aquest indicador.

834
00:39:22,020 --> 00:39:23,811
I hi ha un munt de
banderes del món que

835
00:39:23,811 --> 00:39:27,560
són tan simple com això en termes
dels seus colors i patrons.

836
00:39:27,560 --> 00:39:31,930
Però suposem que aquest s'emmagatzema com una
GIF o JPEG, o mapa de bits o un ping,

837
00:39:31,930 --> 00:39:34,240
qualsevol format d'arxiu gràfic
amb el qual està familiaritzat,

838
00:39:34,240 --> 00:39:36,460
alguns dels quals estem
jugant amb en PSET4.

839
00:39:36,460 --> 00:39:41,550
Això no sembla que val la pena per emmagatzemar
píxel negre, píxel negre, píxel negre,

840
00:39:41,550 --> 00:39:44,790
punt, punt, punt, un munt de
píxels negres per a la primera línia d'exploració,

841
00:39:44,790 --> 00:39:47,430
o fila, a continuació, en el seu conjunt munt de
la mateixa, llavors un grapat sencer

842
00:39:47,430 --> 00:39:49,530
de la mateixa, i després una
tota munt de píxels vermells,

843
00:39:49,530 --> 00:39:53,020
píxels vermells, píxels vermells, a continuació, en el seu conjunt
munt de píxels de color groc, groc, oi?

844
00:39:53,020 --> 00:39:55,050
>> Hi ha tal ineficiència aquí.

845
00:39:55,050 --> 00:39:59,040
Com faria vostè intuïtivament
comprimir la bandera alemanya

846
00:39:59,040 --> 00:40:01,320
si la seva aplicació com un arxiu?

847
00:40:01,320 --> 00:40:04,940
Igual que el que la informació no podem nosaltres
molestar emmagatzemar en el disc per tal

848
00:40:04,940 --> 00:40:08,040
per disminuir la mida del nostre arxiu de com
un megabyte a un kilobyte, alguna cosa

849
00:40:08,040 --> 00:40:09,430
més petit?

850
00:40:09,430 --> 00:40:13,130
On es troba la redundància
aquí per ser clar?

851
00:40:13,130 --> 00:40:13,880
Què podria fer?

852
00:40:13,880 --> 00:40:14,380
Sí?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Exactament.

855
00:40:21,970 --> 00:40:24,550
Per què no en lloc de recordar
el color de cada píxel donaran

856
00:40:24,550 --> 00:40:28,200
de la mateixa manera que ho està fent en PSET4
amb el format d'arxiu de mapa de bits,

857
00:40:28,200 --> 00:40:32,060
¿Per què no acaba de Representes a la
columna de l'esquerra de píxels, per exemple

858
00:40:32,060 --> 00:40:35,370
un munt de píxels negres, un grup
de color vermell, i un munt de groc,

859
00:40:35,370 --> 00:40:39,210
i després simplement alguna manera codificar el
idea de la repetició d'aquest 100 vegades

860
00:40:39,210 --> 00:40:41,020
o repetir això 1.000 vegades?

861
00:40:41,020 --> 00:40:43,430
On 100 o 1000 és
només un nombre enter, de manera que

862
00:40:43,430 --> 00:40:47,290
pot aconseguir lluny amb prou feines un sol número
en lloc de centenars o milers

863
00:40:47,290 --> 00:40:48,270
píxels d'addicionals.

864
00:40:48,270 --> 00:40:50,990
I de fet, així és com ens
podria comprimir la bandera alemanya.

865
00:40:50,990 --> 00:40:51,490
I

866
00:40:51,490 --> 00:40:53,470
Ara què passa amb la bandera francesa?

867
00:40:53,470 --> 00:40:58,930
I una mica d'algun tipus de
exercici mental, que la bandera

868
00:40:58,930 --> 00:41:01,040
es pot comprimir més en el disc?

869
00:41:01,040 --> 00:41:05,720
La bandera alemanya o els francesos
bandera, si prenem aquest enfocament?

870
00:41:05,720 --> 00:41:08,490
La bandera alemanya, perquè hi ha
redundància més horitzontal.

871
00:41:08,490 --> 00:41:12,190
I per disseny, molts arxius gràfic
formats de fet funcionen com a línies d'escaneig

872
00:41:12,190 --> 00:41:12,830
horitzontalment.

873
00:41:12,830 --> 00:41:14,674
Podrien treballar
verticalment, just la humanitat

874
00:41:14,674 --> 00:41:17,090
Fa anys decidit que anem a
en general, pensar en fila coses

875
00:41:17,090 --> 00:41:18,880
per fila en lloc de la columna per columna.

876
00:41:18,880 --> 00:41:20,820
Així que de fet si fossis
per mirar l'arxiu

877
00:41:20,820 --> 00:41:24,670
mida d'una bandera alemanya i francesa
bandera, sempre que la resolució és

878
00:41:24,670 --> 00:41:27,530
el mateix, la mateixa amplada
i l'altura, aquest

879
00:41:27,530 --> 00:41:31,580
aquí serà més gran, perquè vostè
haver de repetir tres vegades.

880
00:41:31,580 --> 00:41:35,570
Ha d'especificar blau, repeteixi
a tu mateix, blanc, repeteixi vostè mateix, vermell,

881
00:41:35,570 --> 00:41:36,740
et repeteixis.

882
00:41:36,740 --> 00:41:39,000
No es pot anar tot
el camí a la dreta.

883
00:41:39,000 --> 00:41:41,200
I com un a part, per fer
esborrar la compressió

884
00:41:41,200 --> 00:41:43,910
és a tot arreu, si aquestes són
4 quadres d'un vídeo-- vostè

885
00:41:43,910 --> 00:41:45,890
podria recordar que una pel·lícula
o vídeo és generalment

886
00:41:45,890 --> 00:41:47,286
com 29 o 30 fotogrames per segon.

887
00:41:47,286 --> 00:41:50,410
És com un petit llibre de tapa on
simplement veure la imatge, imatge, imatge, imatge,

888
00:41:50,410 --> 00:41:54,410
imatge acaba molt ràpid pel que sembla
els actors de la pantalla estan movent.

889
00:41:54,410 --> 00:41:57,130
Aquí està una borinot en
la part superior d'un ram de flors.

890
00:41:57,130 --> 00:41:59,790
I tot i que podria ser una mena de
difícil de veure a simple vista,

891
00:41:59,790 --> 00:42:04,020
l'únic que es mou en
aquesta pel·lícula és l'abella.

892
00:42:04,020 --> 00:42:06,880
>> Quin és mut sobre l'emmagatzematge
vídeo sense comprimir?

893
00:42:06,880 --> 00:42:11,420
És una mica una pèrdua per emmagatzemar vídeo
com quatre imatges gairebé idèntiques que

894
00:42:11,420 --> 00:42:13,670
difereixen només en la mesura que l'abella és.

895
00:42:13,670 --> 00:42:16,280
Vostè pot tirar més
d'aquesta informació

896
00:42:16,280 --> 00:42:20,190
i només recordar, per exemple,
el primer fotograma i l'última trama,

897
00:42:20,190 --> 00:42:22,180
fotogrames clau si ha
Alguna vegada has sentit la paraula,

898
00:42:22,180 --> 00:42:24,337
i acaba d'emmagatzemar en el
mig, on l'abella és.

899
00:42:24,337 --> 00:42:26,170
I vostè no ha de
emmagatzemar la totalitat de la rosa,

900
00:42:26,170 --> 00:42:28,330
i el blau, i el
valors verds també.

901
00:42:28,330 --> 00:42:31,200
Així que això és per dir només això
compressió està a tot arreu.

902
00:42:31,200 --> 00:42:34,900
És una tècnica que utilitzem sovint
o donar per fet aquests dies.

903
00:42:34,900 --> 00:42:38,750
>> Però, ¿com comprimir text?

904
00:42:38,750 --> 00:42:40,450
Com vostè va sobre la compressió de text?

905
00:42:40,450 --> 00:42:45,410
Bé, cada un dels personatges de
ASCII és un byte, o vuit bits.

906
00:42:45,410 --> 00:42:47,360
I això és una mica ximple, no?

907
00:42:47,360 --> 00:42:51,160
Com que és probable que el tipus A
i E i I i O i U molt

908
00:42:51,160 --> 00:42:55,270
més de les vegades com W o Q o Z,
depenent de l'idioma en què

909
00:42:55,270 --> 00:42:56,610
estàs escrivint, sens dubte.

910
00:42:56,610 --> 00:42:59,600
I per què estem fent servir
vuit bits per a cada lletra,

911
00:42:59,600 --> 00:43:02,040
inclosos els menys
lletres populars, oi?

912
00:43:02,040 --> 00:43:05,300
Per què no utilitzar menys bits per
les lletres súper populars

913
00:43:05,300 --> 00:43:07,760
I igual, les coses que endevinin
primer a la Roda de la Fortuna,

914
00:43:07,760 --> 00:43:10,450
i utilitzar més bits per
les lletres menys populars?

915
00:43:10,450 --> 00:43:10,950
Per què?

916
00:43:10,950 --> 00:43:13,130
A causa de que només anem a
utilitzar-los amb menys freqüència.

917
00:43:13,130 --> 00:43:15,838
>> Bé, resulta que no tenen
hagut intents de fer això.

918
00:43:15,838 --> 00:43:18,630
I si vostè recorda de grau
l'escola o l'institut, el codi Morse.

919
00:43:18,630 --> 00:43:20,400
Codi Morse té punts
i guions que poden ser

920
00:43:20,400 --> 00:43:24,270
transmesa al llarg d'un filferro com
sons o senyals d'algun tipus.

921
00:43:24,270 --> 00:43:25,930
Però el codi Morse és un super net.

922
00:43:25,930 --> 00:43:29,010
És una espècie d'un sistema binari en
que té punts o guions.

923
00:43:29,010 --> 00:43:30,977
Però si vostè veu, per exemple, dos punts.

924
00:43:30,977 --> 00:43:33,810
O si vostè pensa de nou a l'operador
qui va com bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
xiulet, colpejar una mica el gallet
que transmet un senyal,

926
00:43:36,760 --> 00:43:40,360
si, el destinatari, rep de dos
punts, quin missatge han rebut?

927
00:43:40,360 --> 00:43:43,490
Completament arbitrària.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
O el que sobre-- o jo?

931
00:43:47,500 --> 00:43:49,570
Potser va ser només dos a la dreta d'E?

932
00:43:49,570 --> 00:43:52,480
Així que hi ha aquest problema
de decodabilidad amb Morse

933
00:43:52,480 --> 00:43:54,890
codi, de manera que llevat que el
persona que envia el missatge que

934
00:43:54,890 --> 00:43:59,510
en realitat entra en pausa per a vostè pot classificar de
veure o escoltar els espais entre les lletres,

935
00:43:59,510 --> 00:44:02,990
que no és suficient només per
enviar un flux de zeros i uns,

936
00:44:02,990 --> 00:44:05,610
o punts i ratlles,
perquè no hi ha ambigüitat.

937
00:44:05,610 --> 00:44:08,640
I és un sol punt, de manera que si
veure dos punts o escoltar dos punts,

938
00:44:08,640 --> 00:44:11,254
potser és dues E d'o potser és un I.

939
00:44:11,254 --> 00:44:13,670
Així que necessitem un sistema que és un
poc més intel·ligent que això.

940
00:44:13,670 --> 00:44:16,851
Així que un home anomenat Huffman anys
Fa passar exactament això.

941
00:44:16,851 --> 00:44:18,600
Així que només anem
per prendre una ràpida mirada

942
00:44:18,600 --> 00:44:20,114
la forma en què els arbres són pertinents a aquest.

943
00:44:20,114 --> 00:44:22,530
Suposem que es tracta d'algun
estúpid missatge que voleu enviar,

944
00:44:22,530 --> 00:44:26,342
composta d'anar del punt A, B, C de D's i E de,
però hi ha una gran quantitat de redundància aquí.

945
00:44:26,342 --> 00:44:27,550
No està destinat a ser anglès.

946
00:44:27,550 --> 00:44:28,341
No està encriptada.

947
00:44:28,341 --> 00:44:30,540
És només un estúpid missatge
amb un munt de repetició.

948
00:44:30,540 --> 00:44:34,010
Així que si vostè realment explicar tota la
Atlètics, B, C de, D's, i E de, aquí està

949
00:44:34,010 --> 00:44:34,890
la freqüència.

950
00:44:34,890 --> 00:44:37,800
20% de les cartes són
A de fins a un 45% de les cartes

951
00:44:37,800 --> 00:44:39,660
són d'E, i tres freqüències.

952
00:44:39,660 --> 00:44:41,960
Comptem allà manualment
i acaba de fer els càlculs.

953
00:44:41,960 --> 00:44:44,579
>> Així resulta que
Huffman, fa algun temps,

954
00:44:44,579 --> 00:44:46,620
va adonar que, ja saps
la qual cosa, si començo edifici

955
00:44:46,620 --> 00:44:51,172
un arbre, o el bosc dels arbres, si es vol,
de la següent manera, puc fer el següent.

956
00:44:51,172 --> 00:44:53,880
Vaig a donar un node per a cada un
de les cartes que m'importen

957
00:44:53,880 --> 00:44:55,530
i jo vaig a emmagatzemar
dins d'aquest node

958
00:44:55,530 --> 00:44:58,610
les freqüències com a punt flotant
valor, o vostè podria utilitzar una N, també,

959
00:44:58,610 --> 00:45:00,210
però nosaltres només farem servir un flotador aquí.

960
00:45:00,210 --> 00:45:03,100
I l'algoritme que
proposar és que vostè

961
00:45:03,100 --> 00:45:07,210
prendre aquest bosc d'un sol node
arbres, arbres tan super curts,

962
00:45:07,210 --> 00:45:11,920
i començar a connectar amb
nous grups, nous pares, si es vol.

963
00:45:11,920 --> 00:45:16,150
I ho fa mitjançant l'elecció del
dues freqüències més petits alhora.

964
00:45:16,150 --> 00:45:18,110
Així que vaig prendre el 10% i 10%.

965
00:45:18,110 --> 00:45:19,090
Crec un nou node.

966
00:45:19,090 --> 00:45:20,910
I que jo anomeno el nou node 20%.

967
00:45:20,910 --> 00:45:22,750
>> Quins dos nodes combino després?

968
00:45:22,750 --> 00:45:23,810
És una mica ambigua.

969
00:45:23,810 --> 00:45:26,643
Així que hi ha alguns casos de cantonada a
considerar, però per mantenir les coses bastant,

970
00:45:26,643 --> 00:45:29,300
Vaig a triar 20% -
Jo ara ignoro els nens.

971
00:45:29,300 --> 00:45:33,640
Vaig a triar 20% i
15% i dibuixa dues noves arestes.

972
00:45:33,640 --> 00:45:35,624
I ara que dos nodes
Com puc lògicament combino?

973
00:45:35,624 --> 00:45:38,540
No feu cas de tots els nens, tots els
néts, només cal veure les arrels

974
00:45:38,540 --> 00:45:39,070
ara.

975
00:45:39,070 --> 00:45:42,220
¿Amb quin de dos nodes vincle junts?

976
00:45:42,220 --> 00:45:44,530
Punt dos i 0,35.

977
00:45:44,530 --> 00:45:45,890
Així que permetin-me dibuixar dues noves arestes.

978
00:45:45,890 --> 00:45:47,570
I llavors jo només en tinc un esquerre.

979
00:45:47,570 --> 00:45:48,650
Així que aquí està un arbre.

980
00:45:48,650 --> 00:45:51,160
I s'ha elaborat deliberadament
mirar espècie de bonic,

981
00:45:51,160 --> 00:45:55,870
de notar que les vores tenen
També ha etiquetat zero i un.

982
00:45:55,870 --> 00:45:59,510
Així que totes les vores esquerres són zero
arbitràriament, però consistent.

983
00:45:59,510 --> 00:46:01,170
Totes les vores drets són estimats.

984
00:46:01,170 --> 00:46:05,070
>> I així ho Hoffman proposa és,
si vostè vol representar una B,

985
00:46:05,070 --> 00:46:10,080
en lloc de representar el nombre 66 com
un arxiu ASCII que és vuit bits sencers,

986
00:46:10,080 --> 00:46:13,360
Saps què, botiga només
el patró zero, zero, zero,

987
00:46:13,360 --> 00:46:17,030
zero, perquè aquest és el camí
del meu arbre, arbre del Sr. Huffman,

988
00:46:17,030 --> 00:46:18,600
al full de l'arrel.

989
00:46:18,600 --> 00:46:20,970
Si voleu emmagatzemar un
I, per contra, no ho facis

990
00:46:20,970 --> 00:46:26,290
enviar vuit bits que representen una E.
En el seu lloc, envieu quin patró de bits?

991
00:46:26,290 --> 00:46:26,890
Un.

992
00:46:26,890 --> 00:46:30,410
I el que és bo d'això és
que E és la lletra més popular,

993
00:46:30,410 --> 00:46:32,340
i utilitzeu el
codi més curt per a això.

994
00:46:32,340 --> 00:46:34,090
El següent més popular
carta sembla que

995
00:46:34,090 --> 00:46:37,380
va ser A. I així la quantitat de bits
no es proposa utilitzar per això?

996
00:46:37,380 --> 00:46:38,270
Zero, un.

997
00:46:38,270 --> 00:46:41,060
>> I com està implementat
ja que aquest arbre, per ara

998
00:46:41,060 --> 00:46:43,350
m'ho dius a mi estipulo que hi ha
sense ambigüitat com en Morse

999
00:46:43,350 --> 00:46:46,090
codi, perquè tot el
cartes que t'importen

1000
00:46:46,090 --> 00:46:48,780
estan a l'extrem d'aquestes vores.

1001
00:46:48,780 --> 00:46:50,580
Així que això és només una
aplicació d'un arbre.

1002
00:46:50,580 --> 00:46:52,538
Aquesta és-- i vaig ona
la meva mà en aquest com

1003
00:46:52,538 --> 00:46:55,570
podria aplicar això com una estructura C.

1004
00:46:55,570 --> 00:46:58,260
Només hem de combinar
un símbol, com un char,

1005
00:46:58,260 --> 00:46:59,910
i la freqüència en l'esquerra i la dreta.

1006
00:46:59,910 --> 00:47:02,510
Però donem una ullada a les dues
exemples finals que Tu

1007
00:47:02,510 --> 00:47:06,070
arribar a ser molt familiaritzat amb després
qüestionari de zero en un problema fixar cinc.

1008
00:47:06,070 --> 00:47:09,210
>> Així que no és l'estructura de dades
coneguda com una taula hash.

1009
00:47:09,210 --> 00:47:12,247
I una taula hash és una espècie de
refredar en què té galledes.

1010
00:47:12,247 --> 00:47:14,830
I suposo que hi ha quatre cubs
aquí, només quatre espais en blanc.

1011
00:47:14,830 --> 00:47:20,830
Aquí hi ha una baralla de cartes, i aquí està
club, espasa, club, diamant, club,

1012
00:47:20,830 --> 00:47:25,960
diamants, clubs, diamants,
clubs-- pel que aquest és l'atzar.

1013
00:47:25,960 --> 00:47:30,330
Cors, Hearts-- així que estic
bucketizing totes les entrades aquí.

1014
00:47:30,330 --> 00:47:32,430
I a les necessitats de la taula de hash
mirar a la seva entrada,

1015
00:47:32,430 --> 00:47:34,850
i després posar-lo en un determinat
col·locar sobre la base del que es veu.

1016
00:47:34,850 --> 00:47:35,600
És un algoritme.

1017
00:47:35,600 --> 00:47:37,980
I jo estava fent servir un super
algoritme visual simple.

1018
00:47:37,980 --> 00:47:40,030
La part més dura de la qual era
recordant quines eren les fotos.

1019
00:47:40,030 --> 00:47:41,590
I després hi ha quatre coses totals.

1020
00:47:41,590 --> 00:47:45,440
>> Ara les piles estaven creixent, la qual cosa
és una cosa disseny deliberat aquí.

1021
00:47:45,440 --> 00:47:46,540
Però què més podia fer?

1022
00:47:46,540 --> 00:47:49,080
Així que en realitat aquí tenim una
munt de vells llibres de l'examen de l'escola.

1023
00:47:49,080 --> 00:47:51,240
Suposem que un grup de
noms dels estudiants són d'aquí.

1024
00:47:51,240 --> 00:47:52,570
Aquí hi ha una taula hash més gran.

1025
00:47:52,570 --> 00:47:54,867
En lloc de quatre cubs,
He, diguem 26.

1026
00:47:54,867 --> 00:47:57,950
I no volíem anar prestat 26
coses de fora [? Annenberg?], Pel que

1027
00:47:57,950 --> 00:48:00,289
aquí és de cinc que representen
A fins a la Z. I si jo

1028
00:48:00,289 --> 00:48:03,580
veure a un estudiant el nom del qual comença amb A,
Vaig a posar el seu qüestionari allà.

1029
00:48:03,580 --> 00:48:08,850
Si algú comença amb C, allà,
A-- realitat, no volia fer això.

1030
00:48:08,850 --> 00:48:10,060
B passa per aquí.

1031
00:48:10,060 --> 00:48:13,390
Així que tinc A i B i C. I
Ara aquí està un altre estudiant A.

1032
00:48:13,390 --> 00:48:16,212
Però si aquesta taula hash és
implementat amb una matriu,

1033
00:48:16,212 --> 00:48:17,920
Sóc una mena de fotut
en aquest punt, no?

1034
00:48:17,920 --> 00:48:19,510
Jo com que necessito posar això en algun lloc.

1035
00:48:19,510 --> 00:48:24,380
>> Així que una manera de que pugui resoldre això és, tot
dret, A està ocupada, B està ocupat, C està ocupat.

1036
00:48:24,380 --> 00:48:28,880
Vaig a posar-lo en D. Així que en
primer, tinc accés instantani a l'atzar

1037
00:48:28,880 --> 00:48:31,064
a cada un dels cubs per als estudiants.

1038
00:48:31,064 --> 00:48:33,230
Però ara és una espècie de degenerar
en alguna cosa lineal,

1039
00:48:33,230 --> 00:48:36,750
perquè si vull buscar algú
el nom comença amb A, puc comprovar aquí.

1040
00:48:36,750 --> 00:48:38,854
Però si això no és l'A
estudiant que estic buscant,

1041
00:48:38,854 --> 00:48:41,520
Jo com que he de començar a comprovar
les galledes, perquè el que vaig fer

1042
00:48:41,520 --> 00:48:44,530
era una mena de forma lineal
sondejar l'estructura de dades.

1043
00:48:44,530 --> 00:48:47,710
Una forma estúpida de dir prou amb veure
per a la primera obertura disponible,

1044
00:48:47,710 --> 00:48:51,850
i posar com un pla B, per així dir-ho,
o pla D en aquest cas, el valor

1045
00:48:51,850 --> 00:48:53,340
en aquesta ubicació.

1046
00:48:53,340 --> 00:48:56,470
Això és just el que si ha
té 26 ubicacions i no hi ha estudiants

1047
00:48:56,470 --> 00:49:00,600
amb el nom de Q o Z, o alguna cosa així
que, almenys que estigui utilitzant l'espai.

1048
00:49:00,600 --> 00:49:03,140
>> Però ja hem vist més
solucions intel·ligents aquí, oi?

1049
00:49:03,140 --> 00:49:04,870
Què faria vostè en el seu lloc
si vostè té un accident?

1050
00:49:04,870 --> 00:49:06,670
Si dues persones tenen
el nom de A, el que faria

1051
00:49:06,670 --> 00:49:09,160
han estat més intel·ligent o més
solució intuïtiva que només

1052
00:49:09,160 --> 00:49:12,840
posar una on se suposa que D a ser?

1053
00:49:12,840 --> 00:49:14,810
Per què no només ha d'anar
[exterior? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
com malloc, un altre node, el va posar
aquí i, a continuació, posar que un estudiant aquí.

1055
00:49:19,960 --> 00:49:22,120
Així que bàsicament tinc
algun tipus d'una matriu,

1056
00:49:22,120 --> 00:49:25,590
o potser amb més elegància que a nosaltres
començant a veure una llista enllaçada.

1057
00:49:25,590 --> 00:49:29,520
>> I així una taula hash és una estructura
que podria tenir un aspecte com aquest,

1058
00:49:29,520 --> 00:49:33,900
però més intel·ligentment, cosa anomenada
encadenament separat, pel que una taula hash

1059
00:49:33,900 --> 00:49:38,340
simplement és una matriu, cada un
els elements no és un nombre,

1060
00:49:38,340 --> 00:49:40,470
és en si mateix una llista enllaçada.

1061
00:49:40,470 --> 00:49:45,080
Així que vostè obtingui accés súper ràpid
decidir on hash del seu valor a.

1062
00:49:45,080 --> 00:49:48,059
Igual que amb l'exemple de les targetes,
Vaig fer decisions molt ràpides.

1063
00:49:48,059 --> 00:49:49,600
Cors va aquí, els diamants va aquí.

1064
00:49:49,600 --> 00:49:52,180
El mateix dic, A va aquí,
D va aquí, B va aquí.

1065
00:49:52,180 --> 00:49:55,740
Així super ràpid look-ups, i si
li passa a executar en un cas

1066
00:49:55,740 --> 00:49:59,429
col·lisions en el qual has, dos
les persones amb el mateix nom, bé, llavors

1067
00:49:59,429 --> 00:50:00,970
que acaba de començar que els uneix.

1068
00:50:00,970 --> 00:50:03,900
I potser mantenir ordenats
per ordre alfabètic, potser vostè no ho fa.

1069
00:50:03,900 --> 00:50:05,900
Però almenys ara tenim el dinamisme.

1070
00:50:05,900 --> 00:50:10,250
Així, d'una banda tenim súper ràpid
constant de temps, i el tipus de temps lineal

1071
00:50:10,250 --> 00:50:14,110
involucrats si aquestes llistes enllaçades
començar a ser una mica llarga.

1072
00:50:14,110 --> 00:50:16,880
>> Així que aquesta classe de tonto,
Fa anys broma geek.

1073
00:50:16,880 --> 00:50:19,590
Al CS50 hack-a-thon,
quan els estudiants del check in,

1074
00:50:19,590 --> 00:50:22,040
alguns TF o CA cada any
pensa que és graciós que aguantar

1075
00:50:22,040 --> 00:50:27,772
un senyal d'aquest tipus, on s'acaba
vol dir que si el seu nom comença amb A,

1076
00:50:27,772 --> 00:50:28,870
anar per aquest camí.

1077
00:50:28,870 --> 00:50:31,110
Si el seu nom comença
amb una B, aneu esto-- OK,

1078
00:50:31,110 --> 00:50:33,290
és curiós potser més tard en el semestre.

1079
00:50:33,290 --> 00:50:36,420
Però hi ha una altra
manera de fer això, també.

1080
00:50:36,420 --> 00:50:37,410
Torna a això.

1081
00:50:37,410 --> 00:50:38,600
>> Així que hi ha aquesta estructura.

1082
00:50:38,600 --> 00:50:40,420
I aquesta és la nostra última
estructura per avui,

1083
00:50:40,420 --> 00:50:42,400
que és una cosa que es diu un trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-I, que per alguna raó és curta
per a la recuperació, però que es diu trie.

1085
00:50:47,140 --> 00:50:51,389
Així que un trie és un altre interessant
amalgama de moltes d'aquestes idees.

1086
00:50:51,389 --> 00:50:52,930
És un arbre, el que hem vist abans.

1087
00:50:52,930 --> 00:50:54,180
No és un arbre de cerca binària.

1088
00:50:54,180 --> 00:50:58,410
És un arbre amb qualsevol nombre de fills,
però cada un dels nens en un trie

1089
00:50:58,410 --> 00:51:00,090
és una matriu.

1090
00:51:00,090 --> 00:51:04,790
Una matriu de mida, diguem, 26 o potser 27
si vols donar suport noms amb guions

1091
00:51:04,790 --> 00:51:06,790
o apòstrofs en els noms de les persones.

1092
00:51:06,790 --> 00:51:08,280
>> I el que aquesta és una estructura de dades.

1093
00:51:08,280 --> 00:51:10,290
I si es mira des de dalt
a baix, com si

1094
00:51:10,290 --> 00:51:13,710
mirar el node superior allà, M, és
que apunta al més a l'esquerra allà,

1095
00:51:13,710 --> 00:51:17,665
que després és A, X, W, E, L, L. Això és
només una estructura de dades que de forma arbitrària

1096
00:51:17,665 --> 00:51:19,120
és emmagatzemar noms de les persones.

1097
00:51:19,120 --> 00:51:25,720
I Maxwell s'emmagatzema amb només seguir
un camí de matriu a matriu a matriu.

1098
00:51:25,720 --> 00:51:30,050
Però el que és sorprenent d'un trie és
que, mentre que una llista enllaçada i fins i tot

1099
00:51:30,050 --> 00:51:34,520
una matriu, el millor que hem aconseguit és
temps lineal o logarítmica temps buscant

1100
00:51:34,520 --> 00:51:35,600
a algú.

1101
00:51:35,600 --> 00:51:40,530
En aquesta estructura de dades d'un trie, si
la meva estructura de dades té un nom en ella

1102
00:51:40,530 --> 00:51:43,720
i estic a la recerca de Maxwell, estic
anar a buscar-ràpidament.

1103
00:51:43,720 --> 00:51:47,910
Jo només busco M-A-X-W-E-L-L. Si
aquesta estructura de dades, per contra,

1104
00:51:47,910 --> 00:51:51,830
si N és un milió, si hi ha una
milió de noms en aquesta estructura de dades,

1105
00:51:51,830 --> 00:51:57,100
Maxwell encara serà
detectable després de només M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
passos.

1107
00:51:58,090 --> 00:52:01,276
I els passos David-- D-A-V-me-D.

1108
00:52:01,276 --> 00:52:03,400
En altres paraules, mitjançant la construcció
una estructura de dades que és

1109
00:52:03,400 --> 00:52:07,240
aconseguit tots aquests arrays, tots els quals
ells donen suport d'accés aleatori,

1110
00:52:07,240 --> 00:52:11,090
Puc començar a buscar de la gent
nom usant una quantitat de temps que és

1111
00:52:11,090 --> 00:52:14,340
proporcional a no el nombre
de les coses en l'estructura de dades,

1112
00:52:14,340 --> 00:52:16,330
com un milió de noms existents.

1113
00:52:16,330 --> 00:52:20,135
La quantitat de temps que em porta a trobar
M-A-X-W-E-L-L en aquesta estructura de dades es

1114
00:52:20,135 --> 00:52:22,260
proporcional no a la
mida de l'estructura de dades,

1115
00:52:22,260 --> 00:52:25,930
però a la longitud del nom.

1116
00:52:25,930 --> 00:52:28,440
I realista el
noms que estan mirant cap amunt

1117
00:52:28,440 --> 00:52:29,970
Mai van a estar boig de llarg.

1118
00:52:29,970 --> 00:52:32,600
Potser algú té un caràcter 10
nom, nom de 20 caràcters.

1119
00:52:32,600 --> 00:52:33,900
Certament és finita, oi?

1120
00:52:33,900 --> 00:52:37,110
No és un ésser humà a la Terra que
té el nom més llarg possible,

1121
00:52:37,110 --> 00:52:39,920
però aquest nom és una constant
longitud de valor, no?

1122
00:52:39,920 --> 00:52:41,980
És no varia en cap sentit.

1123
00:52:41,980 --> 00:52:45,090
Així d'aquesta manera, tenim
aconseguit una estructura de dades

1124
00:52:45,090 --> 00:52:47,800
és a dir constant de temps de consulta.

1125
00:52:47,800 --> 00:52:50,670
No obstant això, pren una sèrie de mesures
depenent de la longitud de l'entrada,

1126
00:52:50,670 --> 00:52:54,250
però no el nombre del nom
en l'estructura de dades.

1127
00:52:54,250 --> 00:52:58,700
Així que si dupliquem el nombre de noms
l'any que ve a partir d'1000000000-2000000000,

1128
00:52:58,700 --> 00:53:03,720
troballa Maxwell va a prendre
el mateix nombre exacte de set passos

1129
00:53:03,720 --> 00:53:04,650
per trobar-lo.

1130
00:53:04,650 --> 00:53:08,810
I així sembla que hem aconseguit
nostre sant grial de temps d'execució.

1131
00:53:08,810 --> 00:53:10,860
>> Així que un parell d'anunciar.

1132
00:53:10,860 --> 00:53:11,850
Qüestionari zero s'acosta.

1133
00:53:11,850 --> 00:53:14,600
Més sobre això en la pàgina web del curs
durant el pròxim parell de dies.

1134
00:53:14,600 --> 00:53:17,120
Dilluns de lecture-- És un dia de festa
aquí a Harvard dilluns.

1135
00:53:17,120 --> 00:53:18,850
No està a New Haven,
així que estem prenent la classe

1136
00:53:18,850 --> 00:53:20,310
a New Haven de la conferència el dilluns.

1137
00:53:20,310 --> 00:53:22,550
Tot serà filmat
i transmès en viu com sempre,

1138
00:53:22,550 --> 00:53:24,900
però anem a acabar avui
amb un clip de 30 segons

1139
00:53:24,900 --> 00:53:26,910
anomenats "Pensaments profunds"
per Daven Farnham, que

1140
00:53:26,910 --> 00:53:30,850
es va inspirar l'any passat per dissabte
"Pensaments profunds" de Night Live

1141
00:53:30,850 --> 00:53:35,700
per Jack pràctic, que
Ara ha de tenir sentit.

1142
00:53:35,700 --> 00:53:38,810
>> CINEMA: I ara, "Deep
Pensaments "de Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Taula hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> ALTAVEU 1: Molt bé, això és tot per ara.

1147
00:53:47,660 --> 00:53:48,805
Ens veiem la setmana que ve.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Per veure en acció.

1150
00:53:56,680 --> 00:53:58,304
Així que anem a fer una ullada a això ara mateix.

1151
00:53:58,304 --> 00:53:59,890
Així que aquí tenim una matriu sense classificar.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, pots seguir endavant i reinici
això per només un segon, si us plau.

1153
00:54:04,860 --> 00:54:08,562
D'acord, les càmeres estan rodant, per la qual
acció cada vegada que estigui llest, Doug, ¿d'acord?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Molt bé, així que el que
tenim aquí és una sèrie sense classificar.

1155
00:54:11,020 --> 00:54:13,960
I he vaig acolorir tots els elements
vermell per indicar que és, de fet,

1156
00:54:13,960 --> 00:54:14,460
sense classificar.

1157
00:54:14,460 --> 00:54:17,960
Així que recordem que la primera cosa que fem
és classifiquem la meitat esquerra de la matriu.

1158
00:54:17,960 --> 00:54:20,630
Després vam classificar la dreta
mitjà de la matriu.

1159
00:54:20,630 --> 00:54:22,830
I ja-da, ja-da, ja-da,
els fonen.

1160
00:54:22,830 --> 00:54:24,520
I tenim una gamma completament ordenat.

1161
00:54:24,520 --> 00:54:25,360
Així és com fusionar tipus d'obres.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Espera, espera, espera,
tallar, tallar, tallar, tallar.

1163
00:54:27,109 --> 00:54:30,130
Doug, no pots simplement ja-da, ja-da,
ja-da, el seu camí a través de combinació de classe.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Em acaba de fer.

1165
00:54:31,970 --> 00:54:32,832
Està bé.

1166
00:54:32,832 --> 00:54:33,540
Som bons per anar.

1167
00:54:33,540 --> 00:54:34,760
Seguim la rodadura.

1168
00:54:34,760 --> 00:54:35,380
Així que de totes maneres,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Vostè ha d'explicar
més plenament que això.

1170
00:54:37,800 --> 00:54:39,999
Això no és suficient.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, no ho fem
que hagi de tornar a un.

1172
00:54:41,790 --> 00:54:42,350
Està bé.

1173
00:54:42,350 --> 00:54:45,690
Així que de totes maneres, si seguim amb merge--
Ian, estem enmig de la filmació.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Ho sé.

1175
00:54:46,612 --> 00:54:49,320
I no podem simplement ja-da, ja-da,
ja-da, a través de tot el procés.

1176
00:54:49,320 --> 00:54:52,200
Vostè ha d'explicar com el
Ambdues parts queden fusionades juntes.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Però ja hem
va explicar com els dos sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Vostè acaba mostrarà
ells una matriu de mescla.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Ells coneixen el procés.

1180
00:54:56,486 --> 00:54:57,172
Estan bé.

1181
00:54:57,172 --> 00:54:58,380
Hem passat més de deu vegades.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Vostè acaba de saltar per sobre d'ella.

1183
00:55:00,330 --> 00:55:03,360
Anem a tornar a un,
¿No és així ja-da, ja-da sobre ell.

1184
00:55:03,360 --> 00:55:05,480
Molt bé, de nou a un.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: He de tornar
a través de totes les diapositives?

1186
00:55:07,833 --> 00:55:08,332
Deu meu.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
És com la sisena vegada, Ian.

1189
00:55:13,004 --> 00:55:13,940
Està bé.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: D'acord.

1191
00:55:15,200 --> 00:55:16,590
Estàs preparat?

1192
00:55:16,590 --> 00:55:17,400
Gran.

1193
00:55:17,400 --> 00:55:18,950
Acció.