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

2
00:00:10,900 --> 00:00:15,860
>> ALTAVOZ 1: Muy bien, así que esto es
CS50 Este es el final de la quinta semana.

3
00:00:15,860 --> 00:00:19,220
Y recordar que la última vez que
empezado a buscar en los datos más elegante

4
00:00:19,220 --> 00:00:22,310
estructuras que comenzaron a resolver
problemas, que comenzaron a introducir

5
00:00:22,310 --> 00:00:25,640
nuevos problemas, pero la clave de este
Era el tipo de roscado que

6
00:00:25,640 --> 00:00:27,940
empezado a hacer desde un nodo a otro.

7
00:00:27,940 --> 00:00:30,085
Así que este supuesto es
una lista simplemente enlazada.

8
00:00:30,085 --> 00:00:31,960
Y por separado vinculados,
Quiero decir que hay una sola

9
00:00:31,960 --> 00:00:33,380
hilo entre cada uno de esos nodos.

10
00:00:33,380 --> 00:00:35,890
Resulta que usted puede hacer más elegante
cosas como listas doblemente enlazadas

11
00:00:35,890 --> 00:00:38,470
por el que usted tiene una flecha
va en ambas direcciones, lo cual

12
00:00:38,470 --> 00:00:40,320
puede ayudar con ciertas eficiencias.

13
00:00:40,320 --> 00:00:42,000
Pero esto soluciona el problema?

14
00:00:42,000 --> 00:00:43,500
¿Qué problema se resuelve esto?

15
00:00:43,500 --> 00:00:46,620
¿Por qué nos importa el lunes?

16
00:00:46,620 --> 00:00:49,820
¿Por qué, en teoría, nos cuidamos el lunes?

17
00:00:49,820 --> 00:00:50,630
¿Qué hace?

18
00:00:50,630 --> 00:00:51,950
>> AUDIENCIA: dinámicamente Podemos cambiar su tamaño.

19
00:00:51,950 --> 00:00:53,740
>> ALTAVOZ 1: OK, por lo que podemos
dinámicamente cambiar su tamaño.

20
00:00:53,740 --> 00:00:54,710
Bien hecho ambos.

21
00:00:54,710 --> 00:00:57,560
Así que usted puede cambiar el tamaño de forma dinámica este
estructura de datos, mientras que una matriz,

22
00:00:57,560 --> 00:01:00,760
recuerdo, usted tiene que saber un
priori la cantidad de espacio que desea

23
00:01:00,760 --> 00:01:03,870
y si usted necesita un poco más
espacio, eres la clase de suerte.

24
00:01:03,870 --> 00:01:05,560
Tienes que crear una nueva matriz entera.

25
00:01:05,560 --> 00:01:07,893
Tienes que mover todo su
datos de uno a otro,

26
00:01:07,893 --> 00:01:10,600
finalmente liberar la matriz de edad
si se puede, y luego proceder.

27
00:01:10,600 --> 00:01:13,891
Lo cual se siente muy costoso y muy
ineficientes, y de hecho puede ser.

28
00:01:13,891 --> 00:01:14,890
Pero esto no es todo lo bueno.

29
00:01:14,890 --> 00:01:18,180
Nosotros pagamos un precio, lo que fue uno
de los precios más obvias

30
00:01:18,180 --> 00:01:20,550
pagar mediante el uso de una lista enlazada?

31
00:01:20,550 --> 00:01:22,825
>> AUDIENCIA: Tenemos que usar
doble espacio para cada uno.

32
00:01:22,825 --> 00:01:25,200
ALTAVOZ 1: Sí, por lo que necesitamos
al menos el doble de espacio.

33
00:01:25,200 --> 00:01:27,700
De hecho, me di cuenta de esta imagen
incluso un poco engañoso,

34
00:01:27,700 --> 00:01:32,200
porque el IDE CS50 en muchos moderna
computadoras, un puntero o una dirección

35
00:01:32,200 --> 00:01:33,700
no es, de hecho, cuatro bytes.

36
00:01:33,700 --> 00:01:36,090
Es muy a menudo éstos
días ocho bytes, que

37
00:01:36,090 --> 00:01:38,530
significa la parte inferior más
rectángulos hay en la realidad

38
00:01:38,530 --> 00:01:40,900
son una especie de doble de
grande como lo que he dibujado,

39
00:01:40,900 --> 00:01:44,409
lo que significa que está utilizando tres veces más
espacio que podríamos tener de otra manera.

40
00:01:44,409 --> 00:01:46,700
Ahora, al mismo tiempo, estamos
sin dejar de hablar bytes, ¿verdad?

41
00:01:46,700 --> 00:01:49,140
No estamos hablando necesariamente
megabytes o gigabytes,

42
00:01:49,140 --> 00:01:51,000
a menos que estas estructuras de datos se hacen grandes.

43
00:01:51,000 --> 00:01:54,510
>> Y por eso hoy empezamos a considerar
cómo podríamos explorar los datos

44
00:01:54,510 --> 00:01:57,310
más eficientemente si en
hecho de que los datos se hace más grande.

45
00:01:57,310 --> 00:02:00,360
Pero vamos a tratar de canonicalize
las operaciones de la primera

46
00:02:00,360 --> 00:02:02,460
que se puede hacer en estos
tipos de estructuras de datos.

47
00:02:02,460 --> 00:02:04,790
Así que algo como un ligada
lista general apoya

48
00:02:04,790 --> 00:02:07,514
operaciones como borrar,
insertar y buscar.

49
00:02:07,514 --> 00:02:08,639
Y lo que quiero decir con eso?

50
00:02:08,639 --> 00:02:11,222
Eso sólo significa que por lo general,
si la gente está utilizando lista enlazada,

51
00:02:11,222 --> 00:02:14,287
ellos o alguien más ha implementado
funciones como borrar, insertar,

52
00:02:14,287 --> 00:02:16,120
y la búsqueda, por lo que puede
realmente hacer algo

53
00:02:16,120 --> 00:02:18,030
útil con la estructura de datos.

54
00:02:18,030 --> 00:02:20,760
Así que vamos a echar un vistazo rápido
en cómo podríamos aplicar

55
00:02:20,760 --> 00:02:24,530
algo de código para una lista enlazada de la siguiente manera.

56
00:02:24,530 --> 00:02:27,885
>> Así que esto es sólo algo de código C,
ni siquiera un programa completo

57
00:02:27,885 --> 00:02:29,260
que realmente me azotaron rápidamente.

58
00:02:29,260 --> 00:02:32,300
No es en línea en la distribución
código, porque no va a funcionar realmente.

59
00:02:32,300 --> 00:02:33,790
Pero noto que tengo justo
con un comentario dijo,

60
00:02:33,790 --> 00:02:36,130
punto punto punto, hay algo
allí, dot dot dot, algo allí.

61
00:02:36,130 --> 00:02:38,410
Y vamos a mirar
¿cuáles son las partes jugosas.

62
00:02:38,410 --> 00:02:40,790
Así que en la línea tres,
recordemos que esto es ahora

63
00:02:40,790 --> 00:02:45,960
nos propusimos declarar un nodo última
tiempo, uno de esos objetos rectangulares.

64
00:02:45,960 --> 00:02:48,790
Tiene un int que llamaremos N,
pero podríamos llamarlo nada,

65
00:02:48,790 --> 00:02:51,920
y luego una estrella struct nodo llamado siguiente.

66
00:02:51,920 --> 00:02:55,520
Y sólo para que quede claro, que segundos
línea, en la línea seis, ¿qué es eso?

67
00:02:55,520 --> 00:02:57,930
¿Qué está haciendo para nosotros?

68
00:02:57,930 --> 00:03:01,044
Porque sin duda se ve más
críptica que nuestras variables habituales.

69
00:03:01,044 --> 00:03:02,740
>> AUDIENCIA: Se hace que se mueva más de una.

70
00:03:02,740 --> 00:03:04,650
>> ALTAVOZ 1: Se hace que se mueva más de una.

71
00:03:04,650 --> 00:03:08,580
Y para ser más precisos,
almacenará la dirección

72
00:03:08,580 --> 00:03:11,582
del nodo que está destinado a ser
semánticamente al lado de él, ¿verdad?

73
00:03:11,582 --> 00:03:13,540
Por lo tanto, no va a
mover necesariamente nada.

74
00:03:13,540 --> 00:03:15,290
Es sólo va a
almacenar un valor, que es

75
00:03:15,290 --> 00:03:17,170
va a ser la dirección
de algún otro nodo,

76
00:03:17,170 --> 00:03:20,810
y es por eso que hemos dicho struct
estrella de nodo, que denota la estrella

77
00:03:20,810 --> 00:03:22,370
un puntero o una dirección.

78
00:03:22,370 --> 00:03:26,390
OK, así que ahora si asumir que tenemos
esta N disponible para nosotros, y vamos a

79
00:03:26,390 --> 00:03:29,490
asumir que alguien más tiene
insertado un montón de números enteros

80
00:03:29,490 --> 00:03:30,400
en una lista enlazada.

81
00:03:30,400 --> 00:03:35,640
Y esa lista enlazada es
apuntada por algún momento

82
00:03:35,640 --> 00:03:39,040
una llamada lista de variables que es
aprobada en aquí como un parámetro,

83
00:03:39,040 --> 00:03:43,120
cómo hago para línea
14 implementación de búsqueda?

84
00:03:43,120 --> 00:03:45,990
En otras palabras, si me estoy poniendo en práctica
función cuyo propósito en la vida

85
00:03:45,990 --> 00:03:48,889
es tomar un int y luego el
a partir de una lista enlazada,

86
00:03:48,889 --> 00:03:50,430
que es un puntero a la lista enlazada.

87
00:03:50,430 --> 00:03:52,992
Como primera, que creo que David
era nuestra voluntaria el lunes

88
00:03:52,992 --> 00:03:54,700
él estaba señalando
todo vinculado la lista,

89
00:03:54,700 --> 00:03:57,820
es como si estamos pasando
David como nuestra discusión aquí.

90
00:03:57,820 --> 00:03:59,990
¿Cómo hacemos para atravesar esta lista?

91
00:03:59,990 --> 00:04:04,640
Bueno, resulta que a pesar de que
punteros son relativamente nuevo ahora a nosotros,

92
00:04:04,640 --> 00:04:07,010
podemos hacer esto relativamente
sin rodeos.

93
00:04:07,010 --> 00:04:09,500
>> Voy a seguir adelante y
declarar una variable temporal que

94
00:04:09,500 --> 00:04:12,364
por convención es sólo ir
para ser llamado puntero o PTR,

95
00:04:12,364 --> 00:04:14,030
pero se le puede llamar lo que quieras.

96
00:04:14,030 --> 00:04:16,470
Y yo voy a inicializar
al comienzo de la lista.

97
00:04:16,470 --> 00:04:20,050
Así que usted puede clase de pensar en esto
como yo la maestra, el otro día,

98
00:04:20,050 --> 00:04:23,580
tipo de apuntando a alguien
entre nuestros seres humanos como voluntarios.

99
00:04:23,580 --> 00:04:26,470
Así que soy una variable temporal que es
simplemente apuntando a lo mismo

100
00:04:26,470 --> 00:04:31,390
que nuestro coincidentemente nombrado
voluntario David también estaba señalando.

101
00:04:31,390 --> 00:04:35,440
Ahora bien, aunque es puntero
no es nulo, porque recuerdo

102
00:04:35,440 --> 00:04:40,350
que nulo es un valor especial centinela
la demarca el final de la lista,

103
00:04:40,350 --> 00:04:44,280
así que mientras yo no estoy apuntando a la
suelo como nuestra última voluntario

104
00:04:44,280 --> 00:04:47,190
fue, vamos a seguir adelante
y haga lo siguiente.

105
00:04:47,190 --> 00:04:51,820
Si pointer-- y ahora que tipo de deseo
a hacer lo que hicimos con el estudiante

106
00:04:51,820 --> 00:04:57,410
structure-- si dot puntero próximo
equals-- más bien, si dot puntero N es igual

107
00:04:57,410 --> 00:05:02,290
es igual a la variable N, la
argumento que ha sido aprobada en,

108
00:05:02,290 --> 00:05:05,370
entonces quiero seguir adelante
y decir volver realidad.

109
00:05:05,370 --> 00:05:11,020
He encontrado el número N interior
uno de los nodos de mi lista enlazada.

110
00:05:11,020 --> 00:05:13,500
Pero el punto ya no
funciona en este contexto,

111
00:05:13,500 --> 00:05:17,260
porque puntero, PTR, es
de hecho un puntero, una dirección,

112
00:05:17,260 --> 00:05:20,632
que en realidad puede maravillosamente
utilizar finalmente una pieza de sintaxis

113
00:05:20,632 --> 00:05:22,590
ese tipo de marcas
sentido intuitivo y realidad

114
00:05:22,590 --> 00:05:27,870
utilizar una flecha aquí, lo que significa pasar de
esa dirección al entero más allá en.

115
00:05:27,870 --> 00:05:30,160
Así que es muy similar en
espíritu para el operador punto,

116
00:05:30,160 --> 00:05:33,860
sino porque puntero no es un puntero
y no una propia estructura real,

117
00:05:33,860 --> 00:05:35,380
sólo tiene que utilizar la flecha.

118
00:05:35,380 --> 00:05:40,620
>> Así que si el nodo actual que yo, el
variable temporal, estoy apuntando a

119
00:05:40,620 --> 00:05:43,060
¿no es N, ¿qué es lo que quiero hacer?

120
00:05:43,060 --> 00:05:45,910
Pues bien, con mis voluntarios humanos
que tuvimos aquí el otro día,

121
00:05:45,910 --> 00:05:49,710
si mi primer ser humano no es el que yo
quiere, y tal vez el segundo humano no es

122
00:05:49,710 --> 00:05:52,660
el que yo quiero, y el tercero, que
que mantener físicamente en movimiento.

123
00:05:52,660 --> 00:05:54,690
Al igual que ¿cómo me paso a través de una lista?

124
00:05:54,690 --> 00:05:57,470
Cuando tuvimos una matriz,
acaba de hacer como si plus plus.

125
00:05:57,470 --> 00:06:03,660
Pero en este caso, basta con
hacer puntero, consigue, puntero, al lado.

126
00:06:03,660 --> 00:06:07,580
En otras palabras, el campo siguiente
es como todas las manos izquierdas

127
00:06:07,580 --> 00:06:10,880
que nuestros voluntarios humanos el lunes
estaban usando para señalar en algún otro nodo.

128
00:06:10,880 --> 00:06:12,890
Esas fueron sus siguientes vecinos.

129
00:06:12,890 --> 00:06:17,060
>> Así que si quiero dar un paso a través de esta lista,
No puedo hacer yo plus plus más,

130
00:06:17,060 --> 00:06:20,120
Yo en cambio tengo que decir
Yo, puntero, va

131
00:06:20,120 --> 00:06:24,650
para igualar cualquiera que sea el siguiente campo es,
el siguiente campo es, el siguiente campo es,

132
00:06:24,650 --> 00:06:28,350
tras todas esas manos izquierdas
que teníamos en el escenario que señala

133
00:06:28,350 --> 00:06:30,000
para algunos valores posteriores.

134
00:06:30,000 --> 00:06:32,590
Y si me pongo a través
toda esa iteración,

135
00:06:32,590 --> 00:06:39,330
y, finalmente, me golpeó nula no tener
Encontré N sin embargo, acabo de regresar falsa.

136
00:06:39,330 --> 00:06:44,100
Así que de nuevo, todo lo que estamos haciendo aquí,
según la imagen hace un momento,

137
00:06:44,100 --> 00:06:47,840
está empezando señalando en el
a partir de la lista de suponer.

138
00:06:47,840 --> 00:06:50,970
Y entonces puedo comprobar, es el valor
Busco igual a nueve?

139
00:06:50,970 --> 00:06:52,650
Si es así, vuelvo verdadera y he terminado.

140
00:06:52,650 --> 00:06:56,450
Si no, puedo actualizar mi mano,
También conocido como puntero, al punto

141
00:06:56,450 --> 00:06:59,540
en el lugar de la próxima flecha y
a continuación, la ubicación de la próxima flecha,

142
00:06:59,540 --> 00:07:00,480
y el siguiente.

143
00:07:00,480 --> 00:07:03,770
Simplemente estoy caminando a través de esta matriz.

144
00:07:03,770 --> 00:07:06,010
>> Así que de nuevo, a quién le importa?

145
00:07:06,010 --> 00:07:07,861
Al igual que lo es este ingrediente para?

146
00:07:07,861 --> 00:07:10,360
Bueno, recordemos que introdujimos
la noción de una pila, que

147
00:07:10,360 --> 00:07:15,400
es un tipo abstracto de datos en la medida en que es
no es una cosa C, no es una cosa CS50,

148
00:07:15,400 --> 00:07:19,430
es una idea abstracta, esta idea de
apilar cosas en la parte superior de unos a otros

149
00:07:19,430 --> 00:07:21,820
que se pueden implementar en
racimos de diferentes maneras.

150
00:07:21,820 --> 00:07:25,600
Y una manera que propusimos fue con
una matriz o con una lista enlazada.

151
00:07:25,600 --> 00:07:29,570
Y resulta que canónicamente, un
pila compatible con al menos dos operaciones.

152
00:07:29,570 --> 00:07:32,320
Y las palabras de moda son de empuje, a
empujar algo en la pila,

153
00:07:32,320 --> 00:07:34,770
como una nueva bandeja en el
comedor, o el pop,

154
00:07:34,770 --> 00:07:39,000
lo que significa para eliminar el más elevado
bandeja de la pila en el comedor

155
00:07:39,000 --> 00:07:41,500
pasillo, y luego tal vez algunos
otras operaciones también.

156
00:07:41,500 --> 00:07:45,770
Entonces, ¿cómo podríamos definir la estructura
que ahora estamos llamando a una pila?

157
00:07:45,770 --> 00:07:50,020
>> Bueno, tenemos todo lo necesario
sintaxis a nuestra disposición en C. digo,

158
00:07:50,020 --> 00:07:53,830
darme una definición de tipo de
una estructura interior de una pila,

159
00:07:53,830 --> 00:07:58,030
Yo voy a decir es una matriz, de un
toda montón de números y luego el tamaño.

160
00:07:58,030 --> 00:08:00,930
En otras palabras, si quiero
para implementar esta en el código,

161
00:08:00,930 --> 00:08:03,830
déjame ir y sólo un poco
dibujar lo que esto está diciendo.

162
00:08:03,830 --> 00:08:06,317
Así que esto está diciendo, dame un
estructura que tiene una matriz,

163
00:08:06,317 --> 00:08:09,400
y yo no sé lo que es la capacidad,
al parecer es una constante que tengo

164
00:08:09,400 --> 00:08:10,858
definidos en otro lugar, y eso está bien.

165
00:08:10,858 --> 00:08:15,260
Pero supongo que es sólo uno,
dos, tres, cuatro, cinco.

166
00:08:15,260 --> 00:08:16,700
Así capacidad es de 5.

167
00:08:16,700 --> 00:08:21,730
Este elemento interior de mi
estructura se llamará números.

168
00:08:21,730 --> 00:08:24,020
Y entonces yo necesito uno
otra variable aparentemente

169
00:08:24,020 --> 00:08:27,814
llamada tamaño que en un principio me voy
estipular se inicializa a cero.

170
00:08:27,814 --> 00:08:29,730
Si no hay nada en
la pila, el tamaño es cero,

171
00:08:29,730 --> 00:08:31,420
y es los valores de basura en números.

172
00:08:31,420 --> 00:08:33,450
No tengo idea de lo que hay allí por el momento.

173
00:08:33,450 --> 00:08:36,059
>> Así que si quiero empujar
algo en la pila,

174
00:08:36,059 --> 00:08:40,780
Supongo que yo llamo la función de empuje, y
Digo empujar 50, como el número 50,

175
00:08:40,780 --> 00:08:44,090
donde propondría
Señalo que en esta serie?

176
00:08:44,090 --> 00:08:47,124
Hay cinco posibles respuestas diferentes.

177
00:08:47,124 --> 00:08:48,790
¿Dónde quiere empujar el número 50?

178
00:08:48,790 --> 00:08:51,899
Si el objetivo aquí, de nuevo, llamar al
la función de empuje, pasar en una discusión

179
00:08:51,899 --> 00:08:52,940
de 50, ¿dónde lo pongo?

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

181
00:08:55,680 --> 00:08:59,052
Cinco posible-- 20% de probabilidad
de adivinar correctamente.

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

183
00:08:59,896 --> 00:09:00,740
>> AUDIENCIA: Extremo derecho.

184
00:09:00,740 --> 00:09:01,990
>> ALTAVOZ 1: Extremo derecho.

185
00:09:01,990 --> 00:09:08,359
En la actualidad existe una probabilidad del 25%
de adivinar correctamente.

186
00:09:08,359 --> 00:09:09,650
Así que eso sería realmente bien.

187
00:09:09,650 --> 00:09:12,770
Por convención, lo diré con una matriz,
estaríamos en general comenzará a la izquierda,

188
00:09:12,770 --> 00:09:14,519
Pero podríamos sin duda
comenzará a las de la derecha.

189
00:09:14,519 --> 00:09:17,478
Así que el alerón aquí sería que soy
probablemente va a sacar, a la izquierda,

190
00:09:17,478 --> 00:09:20,060
al igual que en una matriz normal donde
Empiezo a ir a la izquierda a la derecha.

191
00:09:20,060 --> 00:09:21,780
Pero si se puede dar la vuelta
la aritmética, bien.

192
00:09:21,780 --> 00:09:23,060
Es que no es convencional.

193
00:09:23,060 --> 00:09:24,880
OK, tengo que hacer una
más cambio embargo.

194
00:09:24,880 --> 00:09:27,710
Ahora que lo he empujado algo
en la pila, ¿qué sigue?

195
00:09:27,710 --> 00:09:29,400
>> Muy bien, tengo que incrementar el tamaño.

196
00:09:29,400 --> 00:09:32,600
Así que déjame ir por delante y justo
actualizar esta, que era cero.

197
00:09:32,600 --> 00:09:35,950
Y en lugar ahora, me voy
poner en valor uno.

198
00:09:35,950 --> 00:09:39,460
Y ahora supongo empujo otra
número en la pila, al igual que 51.

199
00:09:39,460 --> 00:09:42,680
Bueno, tengo que hacer una más
el cambio, que es hasta el tamaño dos.

200
00:09:42,680 --> 00:09:46,100
Y luego supongo empujo una más
número en la pila como 61,

201
00:09:46,100 --> 00:09:52,530
ahora tengo que actualizar el tamaño de una más
tiempo, y obtener el valor 3 como el tamaño.

202
00:09:52,530 --> 00:09:54,690
Y ahora supongo que yo llamo pop.

203
00:09:54,690 --> 00:09:57,250
Ahora pop, por convención,
no tiene un argumento.

204
00:09:57,250 --> 00:10:00,430
Con una pila, la totalidad
punto de la metáfora de la bandeja

205
00:10:00,430 --> 00:10:03,450
es que usted no tiene la discreción
para ir a buscar esa bandeja, todo lo que puede hacer

206
00:10:03,450 --> 00:10:06,330
se abrirá el de más arriba de
la pila, porque sí.

207
00:10:06,330 --> 00:10:08,010
Eso es lo que hace esta estructura de datos.

208
00:10:08,010 --> 00:10:12,250
>> Así que por esa lógica si
dicen pop, lo que sale?

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

210
00:10:13,080 --> 00:10:15,402
Así que lo que realmente es el ordenador
va a hacer en la memoria?

211
00:10:15,402 --> 00:10:16,610
¿Qué hace mi código tiene que hacer?

212
00:10:16,610 --> 00:10:20,330
¿Qué propondría usted
cambiamos en la pantalla?

213
00:10:20,330 --> 00:10:23,410
¿Qué debe cambiar?

214
00:10:23,410 --> 00:10:24,960
¿Apenado?

215
00:10:24,960 --> 00:10:26,334
Así que nos deshacemos de 61.

216
00:10:26,334 --> 00:10:27,500
Así que definitivamente puedo hacer eso.

217
00:10:27,500 --> 00:10:28,640
Y puedo deshacerme de 61.

218
00:10:28,640 --> 00:10:30,980
Y entonces, ¿qué otra
el cambio tiene que suceder?

219
00:10:30,980 --> 00:10:33,160
Tamaño probablemente tiene que volver a dos.

220
00:10:33,160 --> 00:10:34,210
Y así está bien.

221
00:10:34,210 --> 00:10:36,690
Pero espere un minuto, tamaño
Hace un momento tenía tres años.

222
00:10:36,690 --> 00:10:38,240
Vamos a hacer una comprobación de validez rápido.

223
00:10:38,240 --> 00:10:41,810
¿Cómo sabemos que estamos
quería deshacerse del 61?

224
00:10:41,810 --> 00:10:42,760
Debido a que estamos haciendo estallar.

225
00:10:42,760 --> 00:10:46,450
Y así tengo este segundo tamaño de la propiedad.

226
00:10:46,450 --> 00:10:48,470
>> Espera un minuto, estoy
pensando en volver a la segunda semana

227
00:10:48,470 --> 00:10:51,660
cuando empezamos a hablar de
arrays, donde esto era lugar de cero,

228
00:10:51,660 --> 00:10:55,920
esta era la ubicación uno, esta era la ubicación
dos, esto es la ubicación tres, cuatro,

229
00:10:55,920 --> 00:10:58,460
parece que el
relación entre el tamaño

230
00:10:58,460 --> 00:11:02,780
y el elemento que quiero quitar
de la matriz parece ser lo que?

231
00:11:02,780 --> 00:11:05,120
Tamaño menos uno.

232
00:11:05,120 --> 00:11:07,786
Y así es como los humanos
sabemos 61 que ocurra primero.

233
00:11:07,786 --> 00:11:09,160
¿Cómo está el equipo va a saber?

234
00:11:09,160 --> 00:11:11,701
Cuando su código, en el que, probablemente,
quiere hacer tamaño de menos uno,

235
00:11:11,701 --> 00:11:14,950
por lo menos uno de tres es de dos, y que
significa que queremos deshacernos de 61.

236
00:11:14,950 --> 00:11:18,000
Y entonces podemos efectivamente actualizar
el tamaño de modo que el tamaño ahora

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

238
00:11:20,300 --> 00:11:24,520
Y sólo para ser pedante, voy
proponer que he terminado, ¿no?

239
00:11:24,520 --> 00:11:27,660
Usted propuso intuitivamente
correctamente Debo deshacerme de 61.

240
00:11:27,660 --> 00:11:30,700
Pero no tienen que tipo de
tipo de deshecho de 61?

241
00:11:30,700 --> 00:11:33,790
Me he olvidado de manera efectiva
que en realidad existe.

242
00:11:33,790 --> 00:11:37,680
Y pensar en volver a PSET4, si has leído
el artículo sobre medicina forense, el PDF

243
00:11:37,680 --> 00:11:40,780
que teníamos que ustedes leer, o
leerá esta semana para PSET4.

244
00:11:40,780 --> 00:11:44,300
Recordemos que esto es en realidad afín a
toda la idea de la informática forense.

245
00:11:44,300 --> 00:11:47,820
Lo que un equipo generalmente hace es
simplemente se olvida dónde está algo,

246
00:11:47,820 --> 00:11:51,300
pero no entra y al igual que
tratar de arañar hacia fuera o anulación

247
00:11:51,300 --> 00:11:54,560
esos bits con ceros y unos
o algún otro patrón aleatorio

248
00:11:54,560 --> 00:11:56,690
a menos que usted mismo lo hacen deliberadamente.

249
00:11:56,690 --> 00:11:58,930
Por lo que su intuición era
Muy bien, vamos a deshacernos de 61.

250
00:11:58,930 --> 00:12:00,650
Pero en realidad, no tenemos que preocuparse.

251
00:12:00,650 --> 00:12:04,040
Sólo tenemos que olvidar que
que está ahí cambiando nuestro tamaño.

252
00:12:04,040 --> 00:12:05,662
>> Ahora hay un problema con esta pila.

253
00:12:05,662 --> 00:12:07,620
Si sigo empujando cosas
en la pila, lo que es

254
00:12:07,620 --> 00:12:11,167
Obviamente va a pasar
en tan sólo unos pocos momentos de tiempo?

255
00:12:11,167 --> 00:12:12,500
Vamos a quedarse sin espacio.

256
00:12:12,500 --> 00:12:13,580
¿Y qué hacemos?

257
00:12:13,580 --> 00:12:14,680
Estamos tipo de jodidos.

258
00:12:14,680 --> 00:12:19,000
Esta aplicación no permite
nos redimensionar la matriz, porque el uso de

259
00:12:19,000 --> 00:12:21,240
esta sintaxis, si
pensar de nuevo a la segunda semana,

260
00:12:21,240 --> 00:12:23,520
una vez que se ha declarado
el tamaño de un array,

261
00:12:23,520 --> 00:12:26,780
no hemos visto un mecanismo aún cuando
usted puede cambiar el tamaño de la matriz.

262
00:12:26,780 --> 00:12:29,020
Y de hecho C no tiene esa característica.

263
00:12:29,020 --> 00:12:32,524
Si dices dame cinco
NTHS, los llaman números,

264
00:12:32,524 --> 00:12:33,940
eso es todo lo que vas a conseguirlo.

265
00:12:33,940 --> 00:12:38,790
Así que vamos a hacer ahora a partir del lunes, tenemos
la capacidad de expresar una solución

266
00:12:38,790 --> 00:12:42,480
sin embargo, sólo tenemos que ajustar
la definición de nuestra pila

267
00:12:42,480 --> 00:12:46,840
de no haber algún conjunto modificable,
pero sólo para almacenar una dirección.

268
00:12:46,840 --> 00:12:47,890
>> Ahora ¿por qué es esto?

269
00:12:47,890 --> 00:12:51,690
Ahora sólo tenemos que estar cómodo con
el hecho de que cuando mi programa se ejecuta,

270
00:12:51,690 --> 00:12:53,730
Estoy presumiblemente va a
tiene que pedir a la humana,

271
00:12:53,730 --> 00:12:55,110
la cantidad de números es lo que quieres para almacenar?

272
00:12:55,110 --> 00:12:56,776
Así que la entrada tiene que venir de alguna parte.

273
00:12:56,776 --> 00:12:59,140
Pero una vez que sé que
número, entonces yo puedo solo

274
00:12:59,140 --> 00:13:02,470
utilizar lo que funciona para dar
mí una parte de la memoria?

275
00:13:02,470 --> 00:13:03,580
Puedo usar malloc.

276
00:13:03,580 --> 00:13:06,710
Y puedo decir cualquier número de
bytes quiero volver por estos NTHS.

277
00:13:06,710 --> 00:13:10,910
Y todo lo que tengo para almacenar en los números
variable de aquí dentro de esta estructura

278
00:13:10,910 --> 00:13:13,480
debería ser qué?

279
00:13:13,480 --> 00:13:18,440
Lo que en realidad sucede en el
números en este escenario?

280
00:13:18,440 --> 00:13:21,300
Sí, un puntero a la primera
byte de ese trozo de memoria,

281
00:13:21,300 --> 00:13:24,940
o más específicamente, la dirección de
del primero de esos bytes.

282
00:13:24,940 --> 00:13:27,300
No importa si es uno
byte o mil millones de bytes,

283
00:13:27,300 --> 00:13:28,890
Sólo tengo que preocuparse por el primero.

284
00:13:28,890 --> 00:13:31,530
Porque ¿qué garantías malloc y
mis garantías del sistema operativo,

285
00:13:31,530 --> 00:13:34,170
es que la parte de la memoria de E
conseguir, que va a ser contiguos.

286
00:13:34,170 --> 00:13:35,378
No va a haber lagunas.

287
00:13:35,378 --> 00:13:38,576
Así que si yo he pedido 50
bytes o 1.000 bytes,

288
00:13:38,576 --> 00:13:40,450
están todos van a ser
espalda con espalda con espalda.

289
00:13:40,450 --> 00:13:44,500
Y siempre que me acuerdo de qué tan grande, ¿cómo
tanto que pedí, todo lo que necesito saber

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

291
00:13:46,230 --> 00:13:48,660
>> Así que ahora tenemos la capacidad de código.

292
00:13:48,660 --> 00:13:51,280
Aunque, va a llevarnos
más tiempo para escribir esto,

293
00:13:51,280 --> 00:13:55,900
podríamos ahora reasignar ese recuerdo por
simplemente almacenar una dirección diferente allí

294
00:13:55,900 --> 00:13:59,060
si queremos una más grande o incluso
un trozo más pequeño de la memoria.

295
00:13:59,060 --> 00:14:00,170
Así que aquí a un fuera de comercio.

296
00:14:00,170 --> 00:14:01,360
Ahora llegamos dinamismo.

297
00:14:01,360 --> 00:14:03,350
Todavía tenemos
contigüidad que estoy afirmando.

298
00:14:03,350 --> 00:14:05,881
Debido a malloc nos dará
una parte contigua de la memoria.

299
00:14:05,881 --> 00:14:08,630
Pero esto va a ser un dolor en
el cuello para nosotros, el programador,

300
00:14:08,630 --> 00:14:09,770
codificar realmente para arriba.

301
00:14:09,770 --> 00:14:10,730
Es sólo más trabajo.

302
00:14:10,730 --> 00:14:13,930
Necesitamos código similar a lo que era
golpeando a cabo hace un momento.

303
00:14:13,930 --> 00:14:16,120
Muy factible, pero añade complejidad.

304
00:14:16,120 --> 00:14:19,520
Y así que el tiempo desarrollador, programador
el tiempo es otro recurso

305
00:14:19,520 --> 00:14:22,520
que podamos necesitar para pasar
un poco de tiempo para conseguir nuevas características.

306
00:14:22,520 --> 00:14:24,020
Y luego, por supuesto, hay una cola.

307
00:14:24,020 --> 00:14:26,227
No vamos a entrar en esto
una en mucho detalle.

308
00:14:26,227 --> 00:14:27,560
Pero es muy similar en espíritu.

309
00:14:27,560 --> 00:14:31,220
Yo podría implementar una cola, y
sus operaciones correspondientes,

310
00:14:31,220 --> 00:14:35,660
enqueue o quitar de la cola, como agregar o quitar,
es sólo una forma más elegante de decirlo,

311
00:14:35,660 --> 00:14:38,100
enqueue o quitar de la cola, como sigue.

312
00:14:38,100 --> 00:14:41,170
Sólo me puedo dar una estructura
que de nuevo tiene matriz de un número,

313
00:14:41,170 --> 00:14:44,000
que de nuevo tiene un tamaño,
pero ¿por qué hago Ahora necesito

314
00:14:44,000 --> 00:14:46,940
hacer un seguimiento de la parte delantera de la cola?

315
00:14:46,940 --> 00:14:50,630
Yo no necesito saber
el frente de mi pila.

316
00:14:50,630 --> 00:14:53,570
Bueno, si yo de nuevo por un
queue-- vamos sólo difícil

317
00:14:53,570 --> 00:14:57,870
codificar como teniendo como de cinco
enteros en aquí potencialmente.

318
00:14:57,870 --> 00:15:00,940
Así que este es cero, uno, dos, tres, cuatro.

319
00:15:00,940 --> 00:15:03,430
Esto va a ser
números llamados de nuevo.

320
00:15:03,430 --> 00:15:06,940
Y esto se llamará tamaño.

321
00:15:06,940 --> 00:15:10,056
>> ¿Por qué es no suficiente
tener el tamaño justo?

322
00:15:10,056 --> 00:15:11,680
Bueno, vamos a empujar esos mismos números en.

323
00:15:11,680 --> 00:15:14,220
Así que pushed-- I en cola, o empujado.

324
00:15:14,220 --> 00:15:20,150
Ahora voy a poner en cola 50, y luego
51, y después de 61 años, y dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Así que eso es enqueue.

326
00:15:21,070 --> 00:15:23,176
Yo en cola 50, luego 51, luego 61.

327
00:15:23,176 --> 00:15:25,050
Y eso se ve idéntica
a una pila hasta el momento,

328
00:15:25,050 --> 00:15:27,190
sin que yo lo necesito para hacer un cambio.

329
00:15:27,190 --> 00:15:33,680
Necesito actualizar este tamaño, así que voy
de cero a uno a dos y cincuenta y ocho ahora.

330
00:15:33,680 --> 00:15:35,760
¿Cómo puedo quitar de la cola?

331
00:15:35,760 --> 00:15:36,890
¿Qué sucede con dequeue?

332
00:15:36,890 --> 00:15:41,950
¿Quién debe salir esta lista primero
si se trata de la línea en la tienda de Apple?

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

334
00:15:42,780 --> 00:15:44,700
Así que es un poco más difícil esta vez.

335
00:15:44,700 --> 00:15:47,880
Mientras que la última vez fue super
simplemente fácil de hacer tamaño de menos uno,

336
00:15:47,880 --> 00:15:51,440
Llego al final de mi serie efectiva
donde los números son, elimina 61.

337
00:15:51,440 --> 00:15:52,920
Pero yo no quiero quitar 61.

338
00:15:52,920 --> 00:15:55,030
Quiero aprovechar 50 años, que
estaba allí en 5:00

339
00:15:55,030 --> 00:15:56,790
a la línea para el
nuevo iPhone o lo que sea.

340
00:15:56,790 --> 00:16:01,200
Y así, para deshacerme de 50, me
no sólo puede hacer esto, ¿verdad?

341
00:16:01,200 --> 00:16:02,547
Puedo tachar 50.

342
00:16:02,547 --> 00:16:04,380
Pero acabamos de decir nos
no tienen que ser tan anal

343
00:16:04,380 --> 00:16:06,330
para ganarse u ocultar los datos.

344
00:16:06,330 --> 00:16:08,090
Sólo podemos olvidar dónde está.

345
00:16:08,090 --> 00:16:12,330
>> Pero si cambio de tamaño ahora
dos, es esta información suficiente

346
00:16:12,330 --> 00:16:15,711
saber lo que está pasando en mi cola?

347
00:16:15,711 --> 00:16:16,680
En realidad no.

348
00:16:16,680 --> 00:16:19,830
Al igual que mi tamaño es dos, pero
¿Dónde comienza la cola,

349
00:16:19,830 --> 00:16:22,980
especialmente si todavía tengo
esos mismos números en la memoria.

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

351
00:16:24,260 --> 00:16:27,090
Así que tengo que recordar
ahora en la parte delantera es.

352
00:16:27,090 --> 00:16:29,630
Y así como me propuse arriba
allí, vamos Acabamos de llamada

353
00:16:29,630 --> 00:16:33,729
Frente enésimo, cuya inicial
valor debe haber sido lo que?

354
00:16:33,729 --> 00:16:35,270
Cero, sólo el comienzo de la lista.

355
00:16:35,270 --> 00:16:40,876
Pero ahora, además de decremento
el tamaño, sólo incrementa el frente.

356
00:16:40,876 --> 00:16:42,000
Ahora aquí hay otro problema.

357
00:16:42,000 --> 00:16:43,030
Así que una vez que sigo yendo.

358
00:16:43,030 --> 00:16:47,520
Supongamos que este es el número de
como 121, 124, y luego, maldita sea,

359
00:16:47,520 --> 00:16:48,610
Estoy fuera de espacio.

360
00:16:48,610 --> 00:16:50,390
Pero espere un minuto, yo no lo soy.

361
00:16:50,390 --> 00:16:55,630
Así que en este punto de la historia,
supongamos que el tamaño es uno, dos,

362
00:16:55,630 --> 00:17:00,370
tres, cuatro, así que supongo que la
tamaño es cuatro, el frente es uno,

363
00:17:00,370 --> 00:17:01,621
por lo que es 51 en la parte delantera.

364
00:17:01,621 --> 00:17:04,329
Quiero poner otro número aquí,
pero, maldita sea, me he quedado sin espacio.

365
00:17:04,329 --> 00:17:06,710
Pero yo no soy realmente, ¿verdad?

366
00:17:06,710 --> 00:17:11,192
¿Dónde podría poner un poco
valor adicional, al igual que 171?

367
00:17:11,192 --> 00:17:13,400
Sólo Sí, pude tipo de
volver por allí, ¿verdad?

368
00:17:13,400 --> 00:17:18,161
Y luego cruzar la 50, o
simplemente sobrescribir con 171.

369
00:17:18,161 --> 00:17:20,410
Y si usted se está preguntando por qué
nuestros números llegaron tan al azar,

370
00:17:20,410 --> 00:17:24,150
éstos son comúnmente tomadas equipo
cursos de ciencias en Harvard después CS50.

371
00:17:24,150 --> 00:17:27,510
Pero eso era una buena optimización,
porque ahora no estoy perdiendo espacio.

372
00:17:27,510 --> 00:17:30,750
Todavía tengo que recordar
lo grande que es total.

373
00:17:30,750 --> 00:17:31,500
Es cinco en total.

374
00:17:31,500 --> 00:17:33,375
Porque no quiero
empezar a sobrescribir 51.

375
00:17:33,375 --> 00:17:36,260
Así que ahora estoy todavía sin espacio,
por lo que el mismo problema que antes.

376
00:17:36,260 --> 00:17:39,140
Pero se puede ver cómo ahora
en el código, es probable que

377
00:17:39,140 --> 00:17:41,910
que escribir un poco más
complejidad para hacer que eso suceda.

378
00:17:41,910 --> 00:17:44,510
Y de hecho, lo que el operador
en C, probablemente vamos a

379
00:17:44,510 --> 00:17:48,110
que mágicamente hace esto la circularidad?

380
00:17:48,110 --> 00:17:50,160
Sí, el operador de módulo,
el signo de porcentaje.

381
00:17:50,160 --> 00:17:53,160
Entonces, ¿qué es una especie de fresco sobre una cola,
a pesar de que seguimos matrices de dibujo

382
00:17:53,160 --> 00:17:56,520
ya que estas líneas rectas como, si usted
tipo de pensar en esto como curva

383
00:17:56,520 --> 00:18:00,341
alrededor como un círculo, entonces sólo
intuitivamente que tipo de trabajos mentales

384
00:18:00,341 --> 00:18:01,590
Creo que un poco más limpia.

385
00:18:01,590 --> 00:18:05,190
Usted todavía tiene que poner en práctica
ese modelo mental en código.

386
00:18:05,190 --> 00:18:07,550
Así que no es tan difícil,
en última instancia, para poner en práctica,

387
00:18:07,550 --> 00:18:12,430
pero todavía perdemos la size-- más bien, la
capacidad de cambiar el tamaño, a menos que hagamos esto.

388
00:18:12,430 --> 00:18:15,310
>> Tenemos que deshacernos de la matriz, se
reemplazarlo con un único puntero,

389
00:18:15,310 --> 00:18:20,010
y luego en algún lugar de mi código tengo
Una llamada lo que funciona para crear realidad

390
00:18:20,010 --> 00:18:23,720
la matriz de números llamados?

391
00:18:23,720 --> 00:18:26,190
Malloc, o algunos similares
función, exactamente.

392
00:18:26,190 --> 00:18:30,481
¿Tiene preguntas sobre pilas o colas.

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
Buena pregunta.

396
00:18:34,240 --> 00:18:35,830
Lo módulo usarías aquí.

397
00:18:35,830 --> 00:18:38,520
Así que en general, cuando se utiliza
mod, que lo haría

398
00:18:38,520 --> 00:18:40,620
con el tamaño de la
estructura de datos entera.

399
00:18:40,620 --> 00:18:44,120
Así que algo así como cinco o capacidad, si
es constante, es probablemente involucrados.

400
00:18:44,120 --> 00:18:47,100
Pero sólo haciendo módulo de cinco
probablemente no es suficiente,

401
00:18:47,100 --> 00:18:51,380
porque necesitamos saber qué tenemos
envolver alrededor de aquí o aquí o aquí.

402
00:18:51,380 --> 00:18:54,160
Así que usted es probablemente también
va a querer involucrar

403
00:18:54,160 --> 00:18:57,220
el tamaño de la cosa, o
la variable frente también.

404
00:18:57,220 --> 00:19:00,140
Así que es sólo por esta relativamente
expresión aritmética simple,

405
00:19:00,140 --> 00:19:02,000
pero módulo sería el ingrediente clave.

406
00:19:02,000 --> 00:19:03,330
>> Así cortometraje si se quiere.

407
00:19:03,330 --> 00:19:05,780
Una animación que algunos
gente de otra universidad

408
00:19:05,780 --> 00:19:08,060
armamos que hemos
adaptada para esta discusión.

409
00:19:08,060 --> 00:19:12,630
Se trata de Jack el aprendizaje de la
hechos acerca de las colas y estadísticas.

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

411
00:19:19,010 --> 00:19:21,890
>> PELÍCULA: Érase una vez,
había un tipo llamado Jack.

412
00:19:21,890 --> 00:19:25,330
Cuando se trataba de hacer amigos,
Jack no tiene una habilidad especial.

413
00:19:25,330 --> 00:19:28,220
Así que Jack fue a hablar con el
más chico popular que sabía.

414
00:19:28,220 --> 00:19:30,920
Fue a Lou y le preguntó: ¿Qué hago?

415
00:19:30,920 --> 00:19:33,400
Lou vio que su amigo
estaba muy angustiado.

416
00:19:33,400 --> 00:19:36,050
Bueno, él comenzó, justo
mira cómo estás vestida.

417
00:19:36,050 --> 00:19:38,680
¿No tienes nada de ropa
con una mirada diferente?

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

419
00:19:39,660 --> 00:19:40,840
Claro que si.

420
00:19:40,840 --> 00:19:43,320
Ven a mi casa y
Voy a mostrarles a ustedes.

421
00:19:43,320 --> 00:19:44,550
Así se fueron a Jack.

422
00:19:44,550 --> 00:19:47,520
Y Jack mostró el cuadro de Lou
donde guardaba todas sus camisas,

423
00:19:47,520 --> 00:19:49,260
y sus pantalones y los calcetines.

424
00:19:49,260 --> 00:19:52,290
Lou dijo: Veo que tienes
toda la ropa en una pila.

425
00:19:52,290 --> 00:19:54,870
¿Por qué no te pones un poco de
demás de vez en cuando?

426
00:19:54,870 --> 00:19:58,020
>> Jack dijo, bueno, cuando yo
quitar la ropa y calcetines,

427
00:19:58,020 --> 00:20:00,780
Yo les lavo y puse
a la basura en la caja.

428
00:20:00,780 --> 00:20:03,210
Luego viene la siguiente
mañana, y hasta me salto.

429
00:20:03,210 --> 00:20:06,380
Voy a la caja y obtengo
mi ropa de la parte superior.

430
00:20:06,380 --> 00:20:09,070
Lou se dio cuenta rápidamente
el problema con Jack.

431
00:20:09,070 --> 00:20:12,080
Mantuvo ropa, CDs,
y los libros de la pila.

432
00:20:12,080 --> 00:20:14,420
Cuando llegó a
algo para leer o llevar,

433
00:20:14,420 --> 00:20:17,100
él elegiría el libro superior o ropa interior.

434
00:20:17,100 --> 00:20:19,500
Luego, cuando terminó,
lo pondría de vuelta.

435
00:20:19,500 --> 00:20:21,970
Volver iría, en la parte superior de la pila.

436
00:20:21,970 --> 00:20:24,460
Yo sé la solución,
dijo un Loud triunfante.

437
00:20:24,460 --> 00:20:27,090
Tienes que aprender a
empiece a usar una cola.

438
00:20:27,090 --> 00:20:29,870
Lou tomó la ropa de Jack y
los colgó en el armario.

439
00:20:29,870 --> 00:20:32,710
Y cuando él había vaciado
la caja, él simplemente lo tiró.

440
00:20:32,710 --> 00:20:36,500
>> Luego dijo, ahora Jack, al final de
el día, poner la ropa a la izquierda

441
00:20:36,500 --> 00:20:37,990
cuando se los pone lejos.

442
00:20:37,990 --> 00:20:41,300
Entonces mañana por la mañana cuando se
ver el sol, ponerse la ropa

443
00:20:41,300 --> 00:20:43,440
a la derecha, desde el final de la línea.

444
00:20:43,440 --> 00:20:44,880
¿No lo ves? dijo Lou.

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

446
00:20:46,370 --> 00:20:49,770
Te llevas todo una vez
antes de que te pones algo dos veces.

447
00:20:49,770 --> 00:20:52,670
Y con todo, en las colas
en su armario y estante,

448
00:20:52,670 --> 00:20:55,160
Jack empezó a sentir
muy seguro de sí mismo.

449
00:20:55,160 --> 00:20:59,720
Todo gracias a Lou y
su maravillosa cola.

450
00:20:59,720 --> 00:21:01,220
ALTAVOZ 1: Muy bien, es adorable.

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

452
00:21:05,920 --> 00:21:10,080
Así que lo que ha sido realmente va
de debajo de la campana ahora?

453
00:21:10,080 --> 00:21:12,370
Que tenemos punteros,
que tenemos malloc,

454
00:21:12,370 --> 00:21:15,680
que tenemos la capacidad de crear
trozos de memoria para nosotros mismos

455
00:21:15,680 --> 00:21:16,344
dinámicamente.

456
00:21:16,344 --> 00:21:18,510
Así que esta es una imagen que nos
vislumbrado el otro día.

457
00:21:18,510 --> 00:21:21,180
Nosotros realmente no moramos
en ella, pero esta imagen

458
00:21:21,180 --> 00:21:24,180
ha estado sucediendo por debajo
el capó desde hace semanas.

459
00:21:24,180 --> 00:21:27,050
Y por lo que esta representa, simplemente
un rectángulo que hemos dibujado,

460
00:21:27,050 --> 00:21:28,180
la memoria del equipo.

461
00:21:28,180 --> 00:21:31,850
Y tal vez su computadora, o CS50
Identificación, tiene un gigabyte de memoria o la memoria RAM

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

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

464
00:21:34,450 --> 00:21:37,240
Su sistema operativo
Windows o Mac OS o Linux,

465
00:21:37,240 --> 00:21:41,120
esencialmente le permite a su programa
a pensar que tiene acceso

466
00:21:41,120 --> 00:21:42,982
a la totalidad de
la memoria del equipo,

467
00:21:42,982 --> 00:21:45,440
a pesar de que podría estar ejecutando
varios programas a la vez.

468
00:21:45,440 --> 00:21:46,990
Así que en realidad, que no funciona muy bien.

469
00:21:46,990 --> 00:21:49,448
Pero es una especie de ilusión
dado a todos sus programas.

470
00:21:49,448 --> 00:21:53,110
Así que si usted tenía dos gigas de RAM, este
Es así como el equipo podría pensar en él.

471
00:21:53,110 --> 00:21:57,110
>> Ahora es coincidencia que uno de ellos
cosas, uno de estos segmentos de memoria,

472
00:21:57,110 --> 00:21:58,350
se llama una pila.

473
00:21:58,350 --> 00:22:01,680
Y, en efecto cualquier momento
hasta el momento en la escritura de código

474
00:22:01,680 --> 00:22:05,900
que ha llamado
función, por ejemplo principal.

475
00:22:05,900 --> 00:22:08,410
Recuerdo que cada vez que tengo
la memoria del ordenador dibujado,

476
00:22:08,410 --> 00:22:10,640
Siempre me baso tipo de
medio de un rectángulo aquí

477
00:22:10,640 --> 00:22:12,520
y no te molestes en hablar
sobre lo que está arriba.

478
00:22:12,520 --> 00:22:15,980
Porque cuando principal se llama, yo reclamo
que se obtiene de este trozo de la memoria

479
00:22:15,980 --> 00:22:16,970
que pasa por aquí.

480
00:22:16,970 --> 00:22:20,650
Y si una función principal llamado
como swap, así canje va aquí.

481
00:22:20,650 --> 00:22:23,720
Y resulta, eso es
donde está terminando.

482
00:22:23,720 --> 00:22:26,277
En algo que se llama una pila
dentro de la memoria del equipo.

483
00:22:26,277 --> 00:22:28,360
Ahora, al final del día,
esto es sólo aborda.

484
00:22:28,360 --> 00:22:30,680
Es como cero bytes,
byte uno, byte 2 mil millones.

485
00:22:30,680 --> 00:22:33,130
Pero si se piensa en ello
como este objeto rectangular,

486
00:22:33,130 --> 00:22:35,130
todo lo que estamos haciendo todos los
tiempo que llamamos una función es

487
00:22:35,130 --> 00:22:37,180
capas de un nuevo segmento de memoria.

488
00:22:37,180 --> 00:22:41,700
Estamos dando a esa función una rebanada
de su propia memoria para trabajar.

489
00:22:41,700 --> 00:22:44,490
>> Y recuerda ahora que esto es importante.

490
00:22:44,490 --> 00:22:46,400
Porque si tenemos
algo así como de intercambio

491
00:22:46,400 --> 00:22:51,610
y dos variables locales como A y B y
cambiamos los valores de uno y dos

492
00:22:51,610 --> 00:22:55,130
a dos y uno, el recuerdo
que cuando regresa de intercambio,

493
00:22:55,130 --> 00:22:58,330
es como si este pedazo
de la memoria simplemente se ha ido.

494
00:22:58,330 --> 00:23:00,080
En realidad, sigue siendo
hay forense.

495
00:23:00,080 --> 00:23:01,940
Y algo todavía está realmente allí.

496
00:23:01,940 --> 00:23:05,410
Pero conceptualmente, es como
aunque ha desaparecido por completo.

497
00:23:05,410 --> 00:23:10,910
Y así principal no sabe cualquiera de los trabajos
que se hizo en esa función de intercambio,

498
00:23:10,910 --> 00:23:14,890
a menos que en realidad pasó en los
argumentos de puntero o de referencia.

499
00:23:14,890 --> 00:23:17,790
Ahora, la solución fundamental
a ese problema de intercambio

500
00:23:17,790 --> 00:23:19,970
es pasar las cosas en su dirección.

501
00:23:19,970 --> 00:23:23,250
Pero resulta que, también, lo que es
estado pasando por encima de esa parte

502
00:23:23,250 --> 00:23:26,330
del rectángulo de todo este tiempo es
sin embargo, hay más memoria hasta allí.

503
00:23:26,330 --> 00:23:28,790
Y cuando dinámicamente
asignar memoria,

504
00:23:28,790 --> 00:23:32,020
ya sea en el interior de GetString, que
que hemos estado haciendo para usted en el CS50

505
00:23:32,020 --> 00:23:34,710
biblioteca, o si ustedes
llamar a malloc y pedir

506
00:23:34,710 --> 00:23:37,950
el sistema operativo de un trozo de
memoria, que no viene de la pila.

507
00:23:37,950 --> 00:23:40,960
Viene de otro lugar
en la memoria de su computadora

508
00:23:40,960 --> 00:23:42,220
eso se llama el montón.

509
00:23:42,220 --> 00:23:43,430
Y eso no es nada diferente.

510
00:23:43,430 --> 00:23:44,285
Es la misma memoria RAM.

511
00:23:44,285 --> 00:23:45,160
Es la misma memoria.

512
00:23:45,160 --> 00:23:49,080
Es sólo la memoria RAM que es hasta
allí en vez de aquí.

513
00:23:49,080 --> 00:23:50,750
>> Y así, ¿qué significa eso?

514
00:23:50,750 --> 00:23:53,650
Bueno, si el equipo tiene
una cantidad finita de memoria

515
00:23:53,650 --> 00:23:57,450
y la pila está creciendo, por lo que
hablar, y el montón, de acuerdo

516
00:23:57,450 --> 00:23:59,349
a esta flecha, está creciendo hacia abajo.

517
00:23:59,349 --> 00:24:01,140
En otras palabras, cada
vez que se llama a malloc,

518
00:24:01,140 --> 00:24:03,430
que está siendo dado una rebanada
de la memoria desde arriba,

519
00:24:03,430 --> 00:24:06,630
entonces tal vez un poco más bajo, luego un poco
inferior, cada vez que se llama a malloc,

520
00:24:06,630 --> 00:24:10,100
el montón, es el uso,
es una especie de crecimiento,

521
00:24:10,100 --> 00:24:11,950
creciendo más y más a lo que?

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

523
00:24:13,382 --> 00:24:14,840
Así que ¿esto parece una buena idea?

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

525
00:24:18,420 --> 00:24:22,140
Quiero decir, cuando en realidad no es clara
¿qué otra cosa se puede hacer si solamente

526
00:24:22,140 --> 00:24:23,910
tienen una cantidad finita de memoria.

527
00:24:23,910 --> 00:24:25,200
Pero esto es seguramente malo.

528
00:24:25,200 --> 00:24:27,920
Esos dos flechas están en una
Curso acelerado por el otro.

529
00:24:27,920 --> 00:24:31,930
>> Y resulta que los malos, la gente que
son particularmente bueno con la programación,

530
00:24:31,930 --> 00:24:36,140
y tratando de introducirse en los ordenadores,
puede explotar esta realidad.

531
00:24:36,140 --> 00:24:38,290
De hecho, vamos a considerar
un pequeño fragmento.

532
00:24:38,290 --> 00:24:41,350
Así que este es un ejemplo, usted puede leer
acerca con más detalle en la Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Te indicamos en el
artículo si curiosa.

534
00:24:43,100 --> 00:24:45,650
Pero hay un ataque general
conocido como desbordamiento de búfer que

535
00:24:45,650 --> 00:24:49,570
ha existido durante tanto tiempo como los humanos
han tenido la capacidad de manipular

536
00:24:49,570 --> 00:24:53,120
la memoria del ordenador, especialmente en C.
Así que este es un programa muy arbitraria,

537
00:24:53,120 --> 00:24:55,130
pero vamos a leer desde abajo hacia arriba.

538
00:24:55,130 --> 00:24:57,650
Principal en estrella ARGC carbón argv.

539
00:24:57,650 --> 00:24:59,830
Así que es un programa que toma
argumentos de la línea de comandos.

540
00:24:59,830 --> 00:25:03,620
Y todo principal no parecer es llamar
una función, lo llaman F para la simplicidad.

541
00:25:03,620 --> 00:25:04,610
Y que pasa en qué?

542
00:25:04,610 --> 00:25:05,490
Argv de uno.

543
00:25:05,490 --> 00:25:09,320
Por lo tanto, pasa a la F lo
la palabra es que el usuario escribió

544
00:25:09,320 --> 00:25:11,500
en el indicador después de la
El nombre del programa en absoluto.

545
00:25:11,500 --> 00:25:15,730
Tanto como César o Vigenére, que
se puede recordar haciendo con argv.

546
00:25:15,730 --> 00:25:16,680
>> Entonces, ¿qué es F?

547
00:25:16,680 --> 00:25:19,760
F lleva en una cadena
como único argumento,

548
00:25:19,760 --> 00:25:22,100
También conocido como una estrella char, misma
cosa, como una cadena.

549
00:25:22,100 --> 00:25:24,920
Y se llama arbitrariamente
bar en este ejemplo.

550
00:25:24,920 --> 00:25:27,710
Y luego carbón c 12,
sólo en términos sencillos,

551
00:25:27,710 --> 00:25:31,750
lo que es carbón c soporte 12 haciendo por nosotros?

552
00:25:31,750 --> 00:25:33,440
¿Qué se hace?

553
00:25:33,440 --> 00:25:36,490
La asignación de memoria, específicamente
12 bytes para 12 caracteres.

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

555
00:25:36,990 --> 00:25:40,000
Y luego la última línea, revolver y
copia, usted probablemente no se ve.

556
00:25:40,000 --> 00:25:43,360
Esta es una copia de cadena
función cuyo propósito en la vida

557
00:25:43,360 --> 00:25:48,160
es copiar su segundo argumento
en su primer argumento,

558
00:25:48,160 --> 00:25:51,190
pero sólo hasta una
cierto número de bytes.

559
00:25:51,190 --> 00:25:53,860
Así que el tercer argumento dice,
cuantos bytes debe copiar?

560
00:25:53,860 --> 00:25:56,720
La longitud de la barra,
cualquiera que sea el usuario escribió en.

561
00:25:56,720 --> 00:25:59,320
Y el contenido de
bar, esa cadena, son

562
00:25:59,320 --> 00:26:02,330
copia en la memoria apuntada en al C.

563
00:26:02,330 --> 00:26:04,060
>> Así que esto parece un poco estúpido, y lo es.

564
00:26:04,060 --> 00:26:06,300
Es un ejemplo artificial,
pero es representativa

565
00:26:06,300 --> 00:26:10,100
de una clase de vectores de ataque,
una manera de atacar a un programa.

566
00:26:10,100 --> 00:26:15,050
Todo está bien y bueno si el usuario
tipos en una palabra que es 11 caracteres

567
00:26:15,050 --> 00:26:18,040
o menos, además de la barra invertida cero.

568
00:26:18,040 --> 00:26:22,830
¿Qué pasa si el usuario escribe en más de
11 o 12 o 20 o 50 caracteres?

569
00:26:22,830 --> 00:26:25,090
¿Cuál es este programa va a hacer?

570
00:26:25,090 --> 00:26:29,360
Culpa Potencialmente seg. Está yendo
copiar ciegamente todo lo que en la barra de arriba

571
00:26:29,360 --> 00:26:31,750
a su longitud, que es
literalmente todo en el bar,

572
00:26:31,750 --> 00:26:36,307
en la dirección apuntando a C. Pero C
sólo se ha dado de manera preventiva como de 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Pero no hay ninguna comprobación adicional.

574
00:26:37,640 --> 00:26:38,700
No hay, si las condiciones.

575
00:26:38,700 --> 00:26:40,580
No hay ninguna comprobación de errores aquí.

576
00:26:40,580 --> 00:26:43,270
>> Y así lo que este programa es
vamos a hacer es a ciegas

577
00:26:43,270 --> 00:26:45,750
copiar una cosa a la otra.

578
00:26:45,750 --> 00:26:47,880
Y así, si trazamos este
como una imagen, aquí está

579
00:26:47,880 --> 00:26:49,860
Sólo una pequeña porción del espacio de memoria.

580
00:26:49,860 --> 00:26:53,470
Así que notamos en la parte inferior, que
tener la barra de variable local.

581
00:26:53,470 --> 00:26:57,330
Así que ese puntero que va a almacén--
más bien que el argumento local que es

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

583
00:26:58,672 --> 00:27:00,380
Y luego tan solo
por encima de ella en una pila,

584
00:27:00,380 --> 00:27:02,505
porque cada vez que pides
para la memoria en la pila,

585
00:27:02,505 --> 00:27:04,310
va un poco
por encima de ella ilustrado,

586
00:27:04,310 --> 00:27:06,270
aviso de que tenemos 12 bytes allí.

587
00:27:06,270 --> 00:27:10,690
El superior izquierdo es el soporte C cero y
la parte inferior derecha es C soporte de 11.

588
00:27:10,690 --> 00:27:12,870
Así es como las computadoras
va a sentar a cabo.

589
00:27:12,870 --> 00:27:18,300
Así que sólo intuitivamente, si la barra tiene más
de 12 caracteres en total, incluyendo

590
00:27:18,300 --> 00:27:25,790
la barra invertida cero, ¿dónde está el
12 o el soporte de C 12 a ir?

591
00:27:25,790 --> 00:27:28,440
O más bien ¿dónde está el día 12
carácter o el carácter 13,

592
00:27:28,440 --> 00:27:30,900
el carácter centésima ir
para terminar en la foto?

593
00:27:30,900 --> 00:27:33,400
¿Arriba o abajo?

594
00:27:33,400 --> 00:27:36,300
>> Claro, porque a pesar de que
la propia pila crece hacia arriba,

595
00:27:36,300 --> 00:27:39,590
una vez que haya puesto cosas en
ello, por razones de diseño,

596
00:27:39,590 --> 00:27:41,294
pone la memoria de arriba a abajo.

597
00:27:41,294 --> 00:27:44,460
Así que si usted tiene más de 12 bytes,
usted va a empezar a sobrescribir bar.

598
00:27:44,460 --> 00:27:47,280
Eso sí que es un error, pero es
no realmente un gran acuerdo.

599
00:27:47,280 --> 00:27:51,130
Pero es una gran cosa, porque no hay
más cosas que están pasando en la memoria.

600
00:27:51,130 --> 00:27:53,074
Así que aquí está cómo podríamos
poner hola, para ser claros.

601
00:27:53,074 --> 00:27:54,490
Si he escrito en hola en el indicador.

602
00:27:54,490 --> 00:27:59,330
Barra invertida cero H-E-L-L-O, termina dentro
esos 12 bytes, y estamos super seguro.

603
00:27:59,330 --> 00:28:00,330
Todo está bien.

604
00:28:00,330 --> 00:28:03,020
Pero si escribo algo
más largo, que es potencialmente

605
00:28:03,020 --> 00:28:05,860
va a arrastrarse en el espacio bar.

606
00:28:05,860 --> 00:28:08,405
Pero peor aún, resulta
fuera de todo este tiempo,

607
00:28:08,405 --> 00:28:11,530
a pesar de que nunca hemos hablado de
ella, la pila se utiliza para otras cosas.

608
00:28:11,530 --> 00:28:13,560
No son sólo las variables locales.

609
00:28:13,560 --> 00:28:15,100
>> C es un lenguaje de nivel muy bajo.

610
00:28:15,100 --> 00:28:17,810
Y es una especie de secreto
usa la pila también

611
00:28:17,810 --> 00:28:21,260
recordar cuando un
función se llama, lo que

612
00:28:21,260 --> 00:28:26,040
la dirección es de la función anterior,
por lo que puede saltar de nuevo a esa función.

613
00:28:26,040 --> 00:28:29,980
Así que cuando las llamadas principales intercambian, entre
las cosas insertan en la pila

614
00:28:29,980 --> 00:28:34,380
no son sólo intercambia variables locales,
o sus argumentos, también empujaron en secreto

615
00:28:34,380 --> 00:28:37,510
en la pila tal como se representa
por la rebanada rojo aquí,

616
00:28:37,510 --> 00:28:40,520
es la dirección del principal físicamente
en la memoria de su computadora,

617
00:28:40,520 --> 00:28:44,180
de modo que cuando se hace de intercambio, el ordenador
sabe que tengo que volver a la principal

618
00:28:44,180 --> 00:28:46,760
y terminar la ejecución de la función principal.

619
00:28:46,760 --> 00:28:51,960
Así que esto es peligroso ahora, porque si
el usuario escribe así más de hola,

620
00:28:51,960 --> 00:28:57,030
de tal manera que clobbers la entrada del usuario
o sobrescribe esa sección roja,

621
00:28:57,030 --> 00:28:59,820
lógicamente si del ordenador
sólo va a asumir ciegamente

622
00:28:59,820 --> 00:29:03,830
que los bytes en esa rebanada rojo son
la dirección a la que debe devolver,

623
00:29:03,830 --> 00:29:09,020
¿y si el adversario es lo suficientemente inteligente o
la suerte de poner una secuencia de bytes

624
00:29:09,020 --> 00:29:13,450
hay que se parece a una dirección,
pero es la dirección de código

625
00:29:13,450 --> 00:29:18,730
que él o ella quiere que el equipo
para ejecutar en lugar de principal?

626
00:29:18,730 --> 00:29:21,670
>> En otras palabras, si lo que el
usuario está escribiendo en el indicador,

627
00:29:21,670 --> 00:29:23,850
no es sólo algo
como inocua hola,

628
00:29:23,850 --> 00:29:28,210
pero en realidad es un código que es equivalente
eliminar todos los archivos de este usuario?

629
00:29:28,210 --> 00:29:30,060
O enviar por correo electrónico su contraseña a mí?

630
00:29:30,060 --> 00:29:31,940
O iniciar el registro de su
pulsaciones de teclado, ¿verdad?

631
00:29:31,940 --> 00:29:34,920
Hay un camino, vamos a estipulan hoy,
que podían escribir no solo hola

632
00:29:34,920 --> 00:29:36,711
mundial o su nombre,
que podían esencialmente

633
00:29:36,711 --> 00:29:39,570
Aconteció en código, ceros y
queridos, que el ordenador

634
00:29:39,570 --> 00:29:43,450
errores tanto de código y una dirección.

635
00:29:43,450 --> 00:29:48,950
Así que aunque algo abstracto, si el
usuario escribe lo suficientemente código acusatorio

636
00:29:48,950 --> 00:29:52,330
que vamos a generalizar aquí
A. A es ataque o adversarios.

637
00:29:52,330 --> 00:29:53,140
Así las cosas simplemente malo.

638
00:29:53,140 --> 00:29:55,306
No importa el
números o los ceros o unos

639
00:29:55,306 --> 00:29:59,470
hoy en día, de modo que usted termina
sobrescribir esa sección roja,

640
00:29:59,470 --> 00:30:01,580
notar que secuencia de bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C cero ocho cero.

642
00:30:05,020 --> 00:30:08,960
Y ahora como artículo de Wikipedia aquí
ha propuesto, si ahora de empezar

643
00:30:08,960 --> 00:30:12,460
etiquetado de los bytes en su equipo de
la memoria, lo que el artículo de Wikipedia es

644
00:30:12,460 --> 00:30:19,060
proponiendo es que, ¿qué pasa si la dirección
de ese byte superior izquierda es 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> En otras palabras, si el malo de la película es
lo suficientemente inteligente con su código

646
00:30:22,200 --> 00:30:26,650
para poner en realidad un número aquí que
corresponde a la dirección del código

647
00:30:26,650 --> 00:30:29,180
él o ella inyecta
en el equipo,

648
00:30:29,180 --> 00:30:31,050
puede engañar a la computadora
a hacer cualquier cosa.

649
00:30:31,050 --> 00:30:34,140
La eliminación de archivos, correo electrónico
cosas, olfateando su tráfico,

650
00:30:34,140 --> 00:30:36,710
literalmente, cualquier cosa podría ser
inyectada en el ordenador.

651
00:30:36,710 --> 00:30:39,220
Y así un desbordamiento de búfer
ataque en su núcleo

652
00:30:39,220 --> 00:30:43,530
es sólo un estúpido, estúpido
primordial de una matriz que

653
00:30:43,530 --> 00:30:45,840
no tienen sus límites comprobados.

654
00:30:45,840 --> 00:30:48,850
Y esto es lo que es super peligroso
ya la vez súper poderoso

655
00:30:48,850 --> 00:30:52,560
en C es que nosotros tenemos de hecho
acceso a cualquier lugar de la memoria.

656
00:30:52,560 --> 00:30:55,320
Todo depende de nosotros, los programadores,
que escriben el código original

657
00:30:55,320 --> 00:30:59,330
para comprobar la longitud de cualquier maldito
matrices que estamos manipulando.

658
00:30:59,330 --> 00:31:00,750
Así que para que quede claro, ¿cuál es la solución?

659
00:31:00,750 --> 00:31:03,190
Si rodamos de nuevo a este
código, no sólo debe

660
00:31:03,190 --> 00:31:08,000
cambiar la longitud de la barra, lo que
más debo revisaré?

661
00:31:08,000 --> 00:31:10,620
¿Qué más debo hacer para
prevenir este ataque por completo?

662
00:31:10,620 --> 00:31:14,110
No quiero decir simplemente ciegamente
que copie tantos bytes

663
00:31:14,110 --> 00:31:16,140
como es la longitud de la barra.

664
00:31:16,140 --> 00:31:18,910
Quiero decir, copiar como
muchos bytes como están en la barra

665
00:31:18,910 --> 00:31:24,090
hasta el asignado
memoria, o 12 como máximo.

666
00:31:24,090 --> 00:31:27,450
Así que necesito algún tipo de condición if
que hace comprobar la longitud de la barra,

667
00:31:27,450 --> 00:31:32,800
pero si es superior a 12, sólo dura código
12 como la distancia máxima posible.

668
00:31:32,800 --> 00:31:35,910
De lo contrario, el tampón de llamada
ataque de desbordamiento puede suceder.

669
00:31:35,910 --> 00:31:38,451
En la parte inferior de las diapositivas,
si tienes curiosidad para leer más

670
00:31:38,451 --> 00:31:41,200
es el artículo original real
si quieres echar un vistazo.

671
00:31:41,200 --> 00:31:44,550
>> Pero ahora, entre los precios
pagados aquí fue ineficiencias.

672
00:31:44,550 --> 00:31:46,680
Así que fue una rápida
bajo nivel vistazo a lo que

673
00:31:46,680 --> 00:31:49,709
pueden surgir problemas ahora que
tener acceso a la memoria del ordenador.

674
00:31:49,709 --> 00:31:51,750
Pero otro problema que
ya tropezado el lunes

675
00:31:51,750 --> 00:31:53,800
era sólo la ineficacia
de una lista enlazada.

676
00:31:53,800 --> 00:31:56,019
Estamos de vuelta a tiempo lineal.

677
00:31:56,019 --> 00:31:57,560
Ya no tenemos una matriz contigua.

678
00:31:57,560 --> 00:31:58,980
No tenemos acceso aleatorio.

679
00:31:58,980 --> 00:32:00,710
No podemos usar la notación de corchetes.

680
00:32:00,710 --> 00:32:04,590
Literalmente, hay que utilizar un bucle while
como la que yo escribí hace un momento.

681
00:32:04,590 --> 00:32:09,740
Pero el lunes, reclamamos que podemos
colarse de nuevo en el ámbito de la eficiencia

682
00:32:09,740 --> 00:32:13,040
lograr algo que es
logarítmica, tal vez, o mejor aún,

683
00:32:13,040 --> 00:32:16,120
tal vez incluso algo que es
la llamada constante de tiempo.

684
00:32:16,120 --> 00:32:19,840
Entonces, ¿cómo podemos hacer que al utilizar estos nuevos
herramientas, estas direcciones, estos indicadores,

685
00:32:19,840 --> 00:32:22,210
y roscado cosas de nosotros mismos?

686
00:32:22,210 --> 00:32:23,960
Bueno, supongamos que
aquí, se trata de un grupo

687
00:32:23,960 --> 00:32:27,170
de los números que queremos almacenar en un
estructura de datos y búsqueda eficiente.

688
00:32:27,170 --> 00:32:30,960
Sin duda nos podemos retroceder a la semana
dos, tirar estos en una matriz,

689
00:32:30,960 --> 00:32:33,150
y la búsqueda de ellos mediante la búsqueda binaria.

690
00:32:33,150 --> 00:32:34,040
Divide y conquistarás.

691
00:32:34,040 --> 00:32:37,720
Y, de hecho, que escribió
búsqueda binaria en PSET3,

692
00:32:37,720 --> 00:32:40,100
donde se implementó el programa de búsqueda.

693
00:32:40,100 --> 00:32:40,890
Pero sabes que.

694
00:32:40,890 --> 00:32:45,060
Hay una especie de más
forma inteligente de hacerlo.

695
00:32:45,060 --> 00:32:47,390
Es un poco más
sofisticado y tal vez

696
00:32:47,390 --> 00:32:50,830
nos permite ver qué binaria
búsqueda es mucho más rápido.

697
00:32:50,830 --> 00:32:52,980
En primer lugar, vamos a introducir
la noción de un árbol.

698
00:32:52,980 --> 00:32:54,730
Que a pesar de que en
árboles realidad tipo de

699
00:32:54,730 --> 00:32:57,730
creciendo así, en el mundo de la informática
la ciencia que tipo de crecer hacia abajo

700
00:32:57,730 --> 00:33:00,830
como un árbol de familia, donde usted tiene
sus abuelos o bisabuelos

701
00:33:00,830 --> 00:33:04,580
o lo que sea en la parte superior, el patriarca y
la matriarca de la familia, sólo uno

702
00:33:04,580 --> 00:33:07,930
denominada raíz, nodo, por debajo
cuales son sus hijos,

703
00:33:07,930 --> 00:33:11,442
por debajo del cual son sus hijos, o
sus descendientes en general.

704
00:33:11,442 --> 00:33:13,400
Y cualquiera colgando
la parte inferior de la familia

705
00:33:13,400 --> 00:33:16,070
árbol, además de ser el
más joven de la familia,

706
00:33:16,070 --> 00:33:19,520
también puede ser sólo genéricamente
llamado las hojas del árbol.

707
00:33:19,520 --> 00:33:21,800
>> Así que esto es sólo un montón
de palabras y definiciones

708
00:33:21,800 --> 00:33:25,790
de algo que se llama un árbol en equipo
la ciencia, como un árbol genealógico.

709
00:33:25,790 --> 00:33:28,770
Pero hay encarnaciones más elegantes
de árboles, uno de los cuales

710
00:33:28,770 --> 00:33:30,780
se llama un árbol de búsqueda binario.

711
00:33:30,780 --> 00:33:34,380
Y usted puede clase de tomadura de pelo
aparte lo que hace esta cosa.

712
00:33:34,380 --> 00:33:37,180
Bueno, es binario en qué sentido?

713
00:33:37,180 --> 00:33:41,455
¿De dónde viene el binario viene de aquí?

714
00:33:41,455 --> 00:33:41,955
¿Apenado?

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

716
00:33:45,961 --> 00:33:47,210
No es tanto un bien o.

717
00:33:47,210 --> 00:33:52,000
Es más que cada uno de los nodos no tiene
más de dos hijos, como vemos aquí.

718
00:33:52,000 --> 00:33:54,990
En general, un tree-- y
sus padres y abuelos

719
00:33:54,990 --> 00:33:57,640
puede tener tantos hijos o
nietos, ya que realmente quieren,

720
00:33:57,640 --> 00:34:00,820
y así, por ejemplo, no tenemos tres
los niños fuera de ese nodo mano derecha,

721
00:34:00,820 --> 00:34:05,480
pero en un árbol binario, un nodo tiene
cero, uno o dos hijos como máximo.

722
00:34:05,480 --> 00:34:08,496
Y eso es una buena propiedad,
porque si está coronada por dos,

723
00:34:08,496 --> 00:34:10,620
vamos a ser capaces de
obtener un poco de base de registro de dos

724
00:34:10,620 --> 00:34:11,975
acción pasando aquí en última instancia.

725
00:34:11,975 --> 00:34:13,350
Así que tenemos algo logarítmica.

726
00:34:13,350 --> 00:34:14,558
Pero más sobre esto en un momento.

727
00:34:14,558 --> 00:34:19,810
Búsqueda árbol significa que los números son
dispuesto de tal manera que el hijo izquierdo de

728
00:34:19,810 --> 00:34:22,429
valor es mayor que la raíz.

729
00:34:22,429 --> 00:34:26,010
Y su hijo derecho es
más grande que la raíz.

730
00:34:26,010 --> 00:34:29,290
En otras palabras, si usted toma alguno de los
linfáticos, los círculos en esta imagen,

731
00:34:29,290 --> 00:34:31,840
y mira a su izquierda
niño y su hijo derecho,

732
00:34:31,840 --> 00:34:34,739
el primero debe ser inferior a,
la segunda debe ser mayor que.

733
00:34:34,739 --> 00:34:36,159
Así cordura comprobar 55.

734
00:34:36,159 --> 00:34:37,780
Se niño dejado es 33.

735
00:34:37,780 --> 00:34:38,620
Es menos.

736
00:34:38,620 --> 00:34:40,929
55, su hijo derecho es 77.

737
00:34:40,929 --> 00:34:41,783
Es mayor que.

738
00:34:41,783 --> 00:34:43,199
Y eso es una definición recursiva.

739
00:34:43,199 --> 00:34:46,480
Podríamos revisar cada uno de los
nodos y el mismo patrón obstaculicen.

740
00:34:46,480 --> 00:34:49,389
>> Así que lo que es bueno en un
árbol binario de búsqueda, es

741
00:34:49,389 --> 00:34:52,204
que uno, podemos ponerlo en práctica
con una estructura, al igual que este.

742
00:34:52,204 --> 00:34:54,620
Y a pesar de que estamos lanzando
un montón de estructuras en su,

743
00:34:54,620 --> 00:34:56,560
son un tanto
intuitiva ahora con suerte.

744
00:34:56,560 --> 00:35:00,570
La sintaxis es aún arcana a ciencia cierta,
pero el contenido de un nodo en este

745
00:35:00,570 --> 00:35:02,786
context-- y guardamos
usando el nodo palabra,

746
00:35:02,786 --> 00:35:04,910
si se trata de un rectángulo
en la pantalla o un círculo,

747
00:35:04,910 --> 00:35:08,970
que es sólo un poco de contenedor genérico,
en este caso de un árbol, como el que se

748
00:35:08,970 --> 00:35:11,780
vimos, necesitamos un número entero
en cada uno de los nodos

749
00:35:11,780 --> 00:35:15,460
y entonces necesito dos punteros apuntando
al hijo izquierdo y el hijo derecho,

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

751
00:35:16,590 --> 00:35:20,730
Así que esa es la forma en que podría
implementar que en una estructura.

752
00:35:20,730 --> 00:35:22,315
¿Y cómo podría yo poner en práctica en el código?

753
00:35:22,315 --> 00:35:26,730
Bueno, vamos a echar un rápido
mirar a este pequeño ejemplo.

754
00:35:26,730 --> 00:35:29,820
No es funcional, pero he
copiado y pegado esa estructura.

755
00:35:29,820 --> 00:35:33,510
Y si mi función para un binario
árbol de búsqueda se llama búsqueda,

756
00:35:33,510 --> 00:35:36,980
y esto tiene dos argumentos,
un N entero y un puntero

757
00:35:36,980 --> 00:35:41,400
a un nodo, por lo que un puntero al árbol
o un puntero a la raíz de un árbol,

758
00:35:41,400 --> 00:35:43,482
cómo hago para la búsqueda de N?

759
00:35:43,482 --> 00:35:45,440
Bueno, en primer lugar, porque soy
tratar con punteros,

760
00:35:45,440 --> 00:35:46,750
Yo voy a hacer una comprobación de validez.

761
00:35:46,750 --> 00:35:54,279
Si es igual a los iguales árbol nulo, es N
en este árbol o no en este árbol?

762
00:35:54,279 --> 00:35:55,070
No puede ser, ¿verdad?

763
00:35:55,070 --> 00:35:56,870
Si estoy pasado nulo,
no hay nada allí.

764
00:35:56,870 --> 00:35:59,230
Puede ser que también acaba de
ciegamente decir return false.

765
00:35:59,230 --> 00:36:04,050
Si me das nada, seguramente no puede
encontrar cualquier número N. Entonces, ¿qué más podría yo

766
00:36:04,050 --> 00:36:04,750
¿revisalo ahora?

767
00:36:04,750 --> 00:36:12,830
Yo voy a decir así más si N es
menos de lo que está en el nodo del árbol

768
00:36:12,830 --> 00:36:16,300
que he estado entregué valor N.

769
00:36:16,300 --> 00:36:20,270
En otras palabras, si el número estoy
buscando, N, es menor que el nodo

770
00:36:20,270 --> 00:36:21,340
que estoy mirando.

771
00:36:21,340 --> 00:36:23,190
Y el nodo estoy buscando
por lo que se llama árbol,

772
00:36:23,190 --> 00:36:26,370
y recordar del ejemplo anterior
para obtener el valor de un puntero,

773
00:36:26,370 --> 00:36:28,310
Utilizo la notación flecha.

774
00:36:28,310 --> 00:36:35,960
Así que si n es menor que el árbol flecha
N, quiero ir conceptualmente izquierda.

775
00:36:35,960 --> 00:36:38,590
¿Cómo puedo expresar searching fui?

776
00:36:38,590 --> 00:36:41,560
Para que quede claro, si esto es
la imagen en cuestión,

777
00:36:41,560 --> 00:36:44,612
y me han pasado esa superior
arrow eso está apuntando hacia abajo.

778
00:36:44,612 --> 00:36:45,570
Esa es mi puntero del árbol.

779
00:36:45,570 --> 00:36:48,060
Estoy apuntando a la raíz del árbol.

780
00:36:48,060 --> 00:36:52,100
Y estoy buscando por ejemplo, para
el número 44, de manera arbitraria.

781
00:36:52,100 --> 00:36:55,300
Es 44 menor o
mayor que 55 obviamente?

782
00:36:55,300 --> 00:36:56,360
Así que es menos.

783
00:36:56,360 --> 00:36:58,760
Y por lo que esta condición se aplica si.

784
00:36:58,760 --> 00:37:03,981
Así conceptualmente, lo que es lo que quiero
buscar siguiente si estoy buscando 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
>> Exactamente, quiero
buscar el hijo izquierdo,

788
00:37:11,100 --> 00:37:12,789
o el sub-árbol de la izquierda de esta imagen.

789
00:37:12,789 --> 00:37:14,830
Y, de hecho, me dejó a través
la imagen aquí abajo

790
00:37:14,830 --> 00:37:17,770
por un momento, ya que
No puedo arañar esto.

791
00:37:17,770 --> 00:37:21,150
Si empiezo aquí a 55, y
Sé que el valor 44

792
00:37:21,150 --> 00:37:23,180
Yo estoy buscando es a
la izquierda, es una especie

793
00:37:23,180 --> 00:37:26,010
de como arrancar la guía telefónica en
medio o desgarrar el árbol por la mitad.

794
00:37:26,010 --> 00:37:29,660
Yo ya no tengo que preocuparse
todo este medio del árbol.

795
00:37:29,660 --> 00:37:33,270
Y, sin embargo, curiosamente, en términos de la
estructura, esta cosa aquí que

796
00:37:33,270 --> 00:37:36,682
comienza con 33, que la propia
es un árbol de búsqueda binaria.

797
00:37:36,682 --> 00:37:39,890
Dije la palabra recurrente antes porque
de hecho esta es una estructura de datos que

798
00:37:39,890 --> 00:37:41,707
por definición es recursiva.

799
00:37:41,707 --> 00:37:44,540
Es posible que tenga un árbol que es esto
grande, pero cada uno de sus hijos

800
00:37:44,540 --> 00:37:46,870
representa un árbol un poco más pequeño.

801
00:37:46,870 --> 00:37:50,910
En lugar de que sea el abuelo
o la abuela, ahora es sólo madre

802
00:37:50,910 --> 00:37:54,300
o-- No puedo no decir-- mamá
o papá, eso sería raro.

803
00:37:54,300 --> 00:37:59,000
En lugar de los dos niños allí
sería como hermano y hermana.

804
00:37:59,000 --> 00:38:01,120
Una nueva generación del árbol genealógico.

805
00:38:01,120 --> 00:38:02,900
Pero estructuralmente, es la misma idea.

806
00:38:02,900 --> 00:38:06,790
Y resulta que tengo una función
con el que puedo buscar una búsqueda binaria

807
00:38:06,790 --> 00:38:07,290
árbol.

808
00:38:07,290 --> 00:38:08,680
Se llama búsqueda.

809
00:38:08,680 --> 00:38:17,870
Busco N en árbol de flecha izquierda
else if N es mayor que el valor

810
00:38:17,870 --> 00:38:18,870
que soy actualmente.

811
00:38:18,870 --> 00:38:20,800
55 en la historia hace un momento.

812
00:38:20,800 --> 00:38:23,780
Tengo una función llamada
búsqueda que puedo simplemente

813
00:38:23,780 --> 00:38:29,660
N pasar esto y buscar de forma recursiva
el sub-árbol y acaba de retorno

814
00:38:29,660 --> 00:38:30,620
sea ​​cual sea la respuesta.

815
00:38:30,620 --> 00:38:33,530
Else Tengo un poco de caso base final aquí.

816
00:38:33,530 --> 00:38:35,310
>> ¿Cuál es el último caso?

817
00:38:35,310 --> 00:38:36,570
Árbol es o bien nulo.

818
00:38:36,570 --> 00:38:39,980
El valor o yo estoy buscando es
menos de lo que o mayor que la

819
00:38:39,980 --> 00:38:42,610
o igual a ella.

820
00:38:42,610 --> 00:38:44,750
Y yo podría decir igual
iguales, pero lógicamente es

821
00:38:44,750 --> 00:38:46,500
equivalente a sólo decir más aquí.

822
00:38:46,500 --> 00:38:49,150
Tan cierto es lo que encuentro algo.

823
00:38:49,150 --> 00:38:51,710
Así que espero que este es un
Incluso ejemplo más convincente

824
00:38:51,710 --> 00:38:54,900
que la función sigma estúpido
hicimos un par de conferencias espalda,

825
00:38:54,900 --> 00:38:58,360
donde era tan fácil de usar un bucle
para contar todos los números de un

826
00:38:58,360 --> 00:39:02,390
a N. Aquí, con una estructura de datos
que en sí es de forma recursiva

827
00:39:02,390 --> 00:39:07,050
Definimos y recursiva atraídos, ahora
tener la capacidad de expresarnos

828
00:39:07,050 --> 00:39:09,780
en el código que sí es recursivo.

829
00:39:09,780 --> 00:39:12,580
Así que este es el mismo código exacto aquí.

830
00:39:12,580 --> 00:39:14,400
>> Entonces, ¿qué otros problemas podemos resolver?

831
00:39:14,400 --> 00:39:18,160
Así que un rápido paso de distancia de
árboles para un momento.

832
00:39:18,160 --> 00:39:20,130
Aquí es, digamos, la bandera alemana.

833
00:39:20,130 --> 00:39:22,020
Y hay claramente una
patrón para este indicador.

834
00:39:22,020 --> 00:39:23,811
Y hay un montón de
banderas del mundo que

835
00:39:23,811 --> 00:39:27,560
son tan simple como esto en términos
de sus colores y patrones.

836
00:39:27,560 --> 00:39:31,930
Pero supongamos que este se almacena como una
GIF o JPEG, o mapa de bits o un ping,

837
00:39:31,930 --> 00:39:34,240
cualquier formato de archivo gráfico
con el que está familiarizado,

838
00:39:34,240 --> 00:39:36,460
algunos de los cuales estamos
jugando con en PSET4.

839
00:39:36,460 --> 00:39:41,550
Esto no parece que vale la pena para almacenar
pixel negro, pixel negro, pixel negro,

840
00:39:41,550 --> 00:39:44,790
punto, punto, punto, un montón de
píxeles negros para la primera línea de exploración,

841
00:39:44,790 --> 00:39:47,430
o fila, a continuación, en su conjunto montón de
la misma, entonces un manojo entero

842
00:39:47,430 --> 00:39:49,530
de la misma, y ​​luego una
toda montón de píxeles rojos,

843
00:39:49,530 --> 00:39:53,020
píxeles rojos, píxeles rojos, a continuación, en su conjunto
montón de píxeles de color amarillo, amarillo, ¿verdad?

844
00:39:53,020 --> 00:39:55,050
>> Hay tal ineficiencia aquí.

845
00:39:55,050 --> 00:39:59,040
¿Cómo haría usted intuitivamente
comprimir la bandera alemana

846
00:39:59,040 --> 00:40:01,320
si su aplicación como un archivo?

847
00:40:01,320 --> 00:40:04,940
Al igual que lo que la información no podemos nosotros
molestarse almacenar en el disco con el fin

848
00:40:04,940 --> 00:40:08,040
para disminuir el tamaño de nuestro archivo de como
un megabyte a un kilobyte, algo

849
00:40:08,040 --> 00:40:09,430
más pequeño?

850
00:40:09,430 --> 00:40:13,130
En donde se encuentra la redundancia
aquí para ser claro?

851
00:40:13,130 --> 00:40:13,880
¿Qué podrías hacer?

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
Exactamente.

855
00:40:21,970 --> 00:40:24,550
¿Por qué no en lugar de recordar
el color de cada píxel darn

856
00:40:24,550 --> 00:40:28,200
al igual que lo está haciendo en PSET4
con el formato de archivo de mapa de bits,

857
00:40:28,200 --> 00:40:32,060
¿por qué no acaba de Representas a la
columna de la izquierda de píxeles, por ejemplo

858
00:40:32,060 --> 00:40:35,370
un montón de píxeles negros, un grupo
de color rojo, y un montón de amarillo,

859
00:40:35,370 --> 00:40:39,210
y luego simplemente alguna manera codificar el
idea de la repetición de este 100 veces

860
00:40:39,210 --> 00:40:41,020
o repetir esto 1.000 veces?

861
00:40:41,020 --> 00:40:43,430
Donde 100 o 1000 es
sólo un número entero, por lo que

862
00:40:43,430 --> 00:40:47,290
puede conseguir lejos con apenas un solo número
en lugar de cientos o miles

863
00:40:47,290 --> 00:40:48,270
píxeles de adicionales.

864
00:40:48,270 --> 00:40:50,990
Y de hecho, así es como nos
podría comprimir la bandera alemana.

865
00:40:50,990 --> 00:40:51,490
Y

866
00:40:51,490 --> 00:40:53,470
Ahora ¿qué pasa con la bandera francesa?

867
00:40:53,470 --> 00:40:58,930
Y un poco de algún tipo de
ejercicio mental, que la bandera

868
00:40:58,930 --> 00:41:01,040
se puede comprimir más en el disco?

869
00:41:01,040 --> 00:41:05,720
La bandera alemana o los franceses
bandera, si tomamos este enfoque?

870
00:41:05,720 --> 00:41:08,490
La bandera alemana, porque hay
redundancia más horizontal.

871
00:41:08,490 --> 00:41:12,190
Y por diseño, muchos archivos gráfico
formatos de hecho funcionan como líneas de escaneo

872
00:41:12,190 --> 00:41:12,830
horizontalmente.

873
00:41:12,830 --> 00:41:14,674
Podrían trabajar
verticalmente, justo la humanidad

874
00:41:14,674 --> 00:41:17,090
Hace años decidido que vamos a
en general, pensar en fila cosas

875
00:41:17,090 --> 00:41:18,880
por fila en lugar de la columna por columna.

876
00:41:18,880 --> 00:41:20,820
Así que de hecho si fueras
para mirar el archivo

877
00:41:20,820 --> 00:41:24,670
tamaño de una bandera alemana y francesa
bandera, siempre que la resolución es

878
00:41:24,670 --> 00:41:27,530
el mismo, el mismo ancho
y la altura, éste

879
00:41:27,530 --> 00:41:31,580
aquí va a ser más grande, porque usted
tener que repetir tres veces.

880
00:41:31,580 --> 00:41:35,570
Tiene que especificar azul, repita
a ti mismo, blanco, repita usted mismo, rojo,

881
00:41:35,570 --> 00:41:36,740
te repitas.

882
00:41:36,740 --> 00:41:39,000
No se puede ir todo
el camino a la derecha.

883
00:41:39,000 --> 00:41:41,200
Y como un aparte, para hacer
borrar la compresión

884
00:41:41,200 --> 00:41:43,910
está en todas partes, si éstas son
cuatro cuadros de un video-- usted

885
00:41:43,910 --> 00:41:45,890
podría recordar que una película
o vídeo es generalmente

886
00:41:45,890 --> 00:41:47,286
como 29 o 30 fotogramas por segundo.

887
00:41:47,286 --> 00:41:50,410
Es como un pequeño libro de tapa donde
simplemente ver la imagen, imagen, imagen, imagen,

888
00:41:50,410 --> 00:41:54,410
imagen acaba muy rápido por lo que parece
los actores de la pantalla están moviendo.

889
00:41:54,410 --> 00:41:57,130
Aquí está un abejorro en
la parte superior de un ramo de flores.

890
00:41:57,130 --> 00:41:59,790
Y a pesar de que podría ser una especie de
difícil de ver a simple vista,

891
00:41:59,790 --> 00:42:04,020
lo único que se mueve en
esta película es la abeja.

892
00:42:04,020 --> 00:42:06,880
>> ¿Cuál es mudo sobre el almacenamiento
vídeo sin comprimir?

893
00:42:06,880 --> 00:42:11,420
Es un poco una pérdida para almacenar vídeo
como cuatro imágenes casi idénticas que

894
00:42:11,420 --> 00:42:13,670
difieren sólo en la medida en que la abeja es.

895
00:42:13,670 --> 00:42:16,280
Usted puede tirar más
de esa información

896
00:42:16,280 --> 00:42:20,190
y sólo recordar, por ejemplo,
el primer fotograma y la última trama,

897
00:42:20,190 --> 00:42:22,180
fotogramas clave si ha
Alguna vez has oído la palabra,

898
00:42:22,180 --> 00:42:24,337
y acaba de almacenar en el
medio, donde la abeja es.

899
00:42:24,337 --> 00:42:26,170
Y usted no tiene que
almacenar la totalidad de la rosa,

900
00:42:26,170 --> 00:42:28,330
y el azul, y el
valores verdes también.

901
00:42:28,330 --> 00:42:31,200
Así que esto es para decir sólo eso
compresión está en todas partes.

902
00:42:31,200 --> 00:42:34,900
Es una técnica que utilizamos a menudo
o dar por hecho estos días.

903
00:42:34,900 --> 00:42:38,750
>> Pero, ¿cómo comprimir texto?

904
00:42:38,750 --> 00:42:40,450
¿Cómo usted va sobre la compresión de texto?

905
00:42:40,450 --> 00:42:45,410
Bueno, cada uno de los personajes de
ASCII es un byte, u ocho bits.

906
00:42:45,410 --> 00:42:47,360
Y eso es un poco tonto, ¿no?

907
00:42:47,360 --> 00:42:51,160
Debido a que es probable que el tipo A
y E y I y O y U mucho

908
00:42:51,160 --> 00:42:55,270
más de las veces como W o Q o Z,
dependiendo del idioma en el que

909
00:42:55,270 --> 00:42:56,610
estás escribiendo, sin duda.

910
00:42:56,610 --> 00:42:59,600
Y ¿por qué estamos usando
ocho bits para cada letra,

911
00:42:59,600 --> 00:43:02,040
incluidos los menos
letras populares, ¿verdad?

912
00:43:02,040 --> 00:43:05,300
¿Por qué no utilizar menos bits para
las letras súper populares

913
00:43:05,300 --> 00:43:07,760
E igual, las cosas que adivinen
primero en la Rueda de la Fortuna,

914
00:43:07,760 --> 00:43:10,450
y utilizar más bits para
las letras menos populares?

915
00:43:10,450 --> 00:43:10,950
¿Por qué?

916
00:43:10,950 --> 00:43:13,130
Debido a que sólo vamos a
utilizarlos con menos frecuencia.

917
00:43:13,130 --> 00:43:15,838
>> Bueno, resulta que no tienen
habido intentos de hacer esto.

918
00:43:15,838 --> 00:43:18,630
Y si usted recuerda de grado
la escuela o el instituto, el código Morse.

919
00:43:18,630 --> 00:43:20,400
Código Morse tiene puntos
y guiones que pueden ser

920
00:43:20,400 --> 00:43:24,270
transmitida a lo largo de un alambre como
sonidos o señales de algún tipo.

921
00:43:24,270 --> 00:43:25,930
Pero el código Morse es un super limpio.

922
00:43:25,930 --> 00:43:29,010
Es una especie de un sistema binario en
que tiene puntos o guiones.

923
00:43:29,010 --> 00:43:30,977
Pero si usted ve, por ejemplo, dos puntos.

924
00:43:30,977 --> 00:43:33,810
O si usted piensa de nuevo al operador
quien va como bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
pitido, golpear un poco el gatillo
que transmite una señal,

926
00:43:36,760 --> 00:43:40,360
si, el destinatario, recibe de dos
puntos, ¿qué mensaje han recibido?

927
00:43:40,360 --> 00:43:43,490
Completamente arbitraria.

928
00:43:43,490 --> 00:43:44,450
>> ¿YO?

929
00:43:44,450 --> 00:43:45,060
¿YO?

930
00:43:45,060 --> 00:43:47,500
O lo que sobre-- o yo?

931
00:43:47,500 --> 00:43:49,570
Tal vez fue sólo dos a la derecha de E?

932
00:43:49,570 --> 00:43:52,480
Así que hay este problema
de decodabilidad con Morse

933
00:43:52,480 --> 00:43:54,890
código, con lo que a menos que el
persona que envía el mensaje de que

934
00:43:54,890 --> 00:43:59,510
en realidad entra en pausa para usted puede clasificar de
ver o escuchar los espacios entre las letras,

935
00:43:59,510 --> 00:44:02,990
que no es suficiente sólo para
enviar un flujo de ceros y unos,

936
00:44:02,990 --> 00:44:05,610
o puntos y rayas,
porque no hay ambigüedad.

937
00:44:05,610 --> 00:44:08,640
E es un solo punto, por lo que si
ver dos puntos o escuchar dos puntos,

938
00:44:08,640 --> 00:44:11,254
tal vez es dos E de o tal vez es uno I.

939
00:44:11,254 --> 00:44:13,670
Así que necesitamos un sistema que es un
poco más inteligente que eso.

940
00:44:13,670 --> 00:44:16,851
Así que un hombre llamado Huffman años
Hace ocurrió exactamente esto.

941
00:44:16,851 --> 00:44:18,600
Así que sólo vamos
para tomar una rápida mirada

942
00:44:18,600 --> 00:44:20,114
la forma en que los árboles son pertinentes a este.

943
00:44:20,114 --> 00:44:22,530
Supongamos que se trata de algún
estúpido mensaje que desea enviar,

944
00:44:22,530 --> 00:44:26,342
compuesta de ir del punto A, B, C de D's y E de,
pero hay una gran cantidad de redundancia aquí.

945
00:44:26,342 --> 00:44:27,550
No está destinado a ser Inglés.

946
00:44:27,550 --> 00:44:28,341
No está encriptada.

947
00:44:28,341 --> 00:44:30,540
Es sólo un estúpido mensaje
con un montón de repetición.

948
00:44:30,540 --> 00:44:34,010
Así que si usted realmente contar toda la
Atléticos, B, C de, D's, y E de, aquí está

949
00:44:34,010 --> 00:44:34,890
la frecuencia.

950
00:44:34,890 --> 00:44:37,800
20% de las cartas son
A de hasta un 45% de las cartas

951
00:44:37,800 --> 00:44:39,660
son de E, y otros tres frecuencias.

952
00:44:39,660 --> 00:44:41,960
Contamos allí manualmente
y acaba de hacer los cálculos.

953
00:44:41,960 --> 00:44:44,579
>> Así resulta que
Huffman, hace algún tiempo,

954
00:44:44,579 --> 00:44:46,620
dio cuenta de que, ya sabes
lo que, si empiezo edificio

955
00:44:46,620 --> 00:44:51,172
un árbol, o el bosque de los árboles, si se quiere,
de la siguiente manera, puedo hacer lo siguiente.

956
00:44:51,172 --> 00:44:53,880
Voy a dar un nodo para cada uno
de las cartas que me importan

957
00:44:53,880 --> 00:44:55,530
y yo voy a almacenar
dentro de ese nodo

958
00:44:55,530 --> 00:44:58,610
las frecuencias como punto flotante
valor, o usted podría utilizar una N, también,

959
00:44:58,610 --> 00:45:00,210
pero nosotros sólo usaremos un flotador aquí.

960
00:45:00,210 --> 00:45:03,100
Y el algoritmo que
propuso es que usted

961
00:45:03,100 --> 00:45:07,210
tomar este bosque de un solo nodo
árboles, árboles tan super cortos,

962
00:45:07,210 --> 00:45:11,920
y empezar a conectar con
nuevos grupos, nuevos padres, si se quiere.

963
00:45:11,920 --> 00:45:16,150
Y lo hace mediante la elección del
dos frecuencias más pequeños a la vez.

964
00:45:16,150 --> 00:45:18,110
Así que tomé el 10% y 10%.

965
00:45:18,110 --> 00:45:19,090
Creo un nuevo nodo.

966
00:45:19,090 --> 00:45:20,910
Y que yo llamo el nuevo nodo 20%.

967
00:45:20,910 --> 00:45:22,750
>> ¿Qué dos nodos combino después?

968
00:45:22,750 --> 00:45:23,810
Es un poco ambigua.

969
00:45:23,810 --> 00:45:26,643
Así que hay algunos casos de esquina a
considerar, pero para mantener las cosas bastante,

970
00:45:26,643 --> 00:45:29,300
Voy a elegir 20% -
Yo ahora ignoro los niños.

971
00:45:29,300 --> 00:45:33,640
Voy a elegir 20% y
15% y dibuja dos nuevas aristas.

972
00:45:33,640 --> 00:45:35,624
Y ahora que dos nodos
Cómo puedo lógicamente combino?

973
00:45:35,624 --> 00:45:38,540
No haga caso de todos los niños, todos los
nietos, basta con ver las raíces

974
00:45:38,540 --> 00:45:39,070
ahora.

975
00:45:39,070 --> 00:45:42,220
¿Con cuál de dos nodos vinculo juntos?

976
00:45:42,220 --> 00:45:44,530
Punto dos y 0,35.

977
00:45:44,530 --> 00:45:45,890
Así que permítanme dibujar dos nuevas aristas.

978
00:45:45,890 --> 00:45:47,570
Y entonces yo sólo tengo uno izquierdo.

979
00:45:47,570 --> 00:45:48,650
Así que aquí está un árbol.

980
00:45:48,650 --> 00:45:51,160
Y se ha elaborado deliberadamente
mirar especie de bonito,

981
00:45:51,160 --> 00:45:55,870
de notar que los bordes tienen
También ha etiquetado cero y uno.

982
00:45:55,870 --> 00:45:59,510
Así que todos los bordes izquierdos son cero
arbitrariamente, pero consistente.

983
00:45:59,510 --> 00:46:01,170
Todos los bordes derechos son queridos.

984
00:46:01,170 --> 00:46:05,070
>> Y así lo Hoffman propone es,
si usted quiere representar una B,

985
00:46:05,070 --> 00:46:10,080
en lugar de representar el número 66 como
un archivo ASCII que es ocho bits enteros,

986
00:46:10,080 --> 00:46:13,360
¿sabes qué, tienda sólo
el patrón cero, cero, cero,

987
00:46:13,360 --> 00:46:17,030
cero, porque ese es el camino
de mi árbol, árbol del Sr. Huffman,

988
00:46:17,030 --> 00:46:18,600
a la hoja de la raíz.

989
00:46:18,600 --> 00:46:20,970
Si desea almacenar un
E, por el contrario, no lo hagas

990
00:46:20,970 --> 00:46:26,290
enviar ocho bits que representan una E.
En su lugar, envíe qué patrón de bits?

991
00:46:26,290 --> 00:46:26,890
Uno.

992
00:46:26,890 --> 00:46:30,410
Y lo que es bueno de esto es
que E es la letra más popular,

993
00:46:30,410 --> 00:46:32,340
y está utilizando el
código más corto para ello.

994
00:46:32,340 --> 00:46:34,090
El siguiente más popular
carta parece que

995
00:46:34,090 --> 00:46:37,380
fue A. Y así la cantidad de bits
no se propone utilizar para eso?

996
00:46:37,380 --> 00:46:38,270
Cero uno.

997
00:46:38,270 --> 00:46:41,060
>> Y como está implementado
ya que este árbol, por ahora

998
00:46:41,060 --> 00:46:43,350
déjame estipulo que hay
sin ambigüedad como en Morse

999
00:46:43,350 --> 00:46:46,090
código, porque todo el
cartas que te importan

1000
00:46:46,090 --> 00:46:48,780
están en el extremo de estos bordes.

1001
00:46:48,780 --> 00:46:50,580
Así que eso es sólo una
aplicación de un árbol.

1002
00:46:50,580 --> 00:46:52,538
Esta es-- y voy onda
mi mano en este cómo

1003
00:46:52,538 --> 00:46:55,570
podría aplicar esto como una estructura C.

1004
00:46:55,570 --> 00:46:58,260
Sólo tenemos que combinar
un símbolo, como un char,

1005
00:46:58,260 --> 00:46:59,910
y la frecuencia en la izquierda y la derecha.

1006
00:46:59,910 --> 00:47:02,510
Pero echemos un vistazo a las dos
ejemplos finales que Tú

1007
00:47:02,510 --> 00:47:06,070
llegar a ser muy familiarizado con después
cuestionario de cero en un problema fijó cinco.

1008
00:47:06,070 --> 00:47:09,210
>> Así que no es la estructura de datos
conocida como una tabla hash.

1009
00:47:09,210 --> 00:47:12,247
Y una tabla hash es una especie de
enfriar en que tiene cubos.

1010
00:47:12,247 --> 00:47:14,830
Y supongo que hay cuatro cubos
aquí, sólo cuatro espacios en blanco.

1011
00:47:14,830 --> 00:47:20,830
Aquí hay una baraja de cartas, y aquí está
club, espada, club, diamante, club,

1012
00:47:20,830 --> 00:47:25,960
diamantes, clubes, diamantes,
clubs-- por lo que este es el azar.

1013
00:47:25,960 --> 00:47:30,330
Corazones, Hearts-- así que estoy
bucketizing todas las entradas aquí.

1014
00:47:30,330 --> 00:47:32,430
Y a las necesidades de la tabla de hash
mirar a su entrada,

1015
00:47:32,430 --> 00:47:34,850
y luego ponerlo en un determinado
colocar sobre la base de lo que se ve.

1016
00:47:34,850 --> 00:47:35,600
Es un algoritmo.

1017
00:47:35,600 --> 00:47:37,980
Y yo estaba usando un super
algoritmo visual simple.

1018
00:47:37,980 --> 00:47:40,030
La parte más dura de la que era
recordando cuáles eran las fotos.

1019
00:47:40,030 --> 00:47:41,590
Y luego está cuatro cosas totales.

1020
00:47:41,590 --> 00:47:45,440
>> Ahora las pilas estaban creciendo, lo que
es una cosa diseño deliberado aquí.

1021
00:47:45,440 --> 00:47:46,540
Pero ¿qué otra cosa podía hacer?

1022
00:47:46,540 --> 00:47:49,080
Así que en realidad aquí tenemos una
montón de viejos libros del examen de la escuela.

1023
00:47:49,080 --> 00:47:51,240
Supongamos que un grupo de
nombres de los estudiantes son de aquí.

1024
00:47:51,240 --> 00:47:52,570
Aquí hay una tabla hash más grande.

1025
00:47:52,570 --> 00:47:54,867
En lugar de cuatro cubos,
He, digamos 26.

1026
00:47:54,867 --> 00:47:57,950
Y no queríamos ir prestado 26
cosas de fuera [? Annenberg?], Por lo que

1027
00:47:57,950 --> 00:48:00,289
aquí es de cinco que representan
A hasta la Z. Y si yo

1028
00:48:00,289 --> 00:48:03,580
ver a un estudiante cuyo nombre comienza con A,
Voy a poner su cuestionario allí.

1029
00:48:03,580 --> 00:48:08,850
Si alguien empieza con C, allá,
A-- realidad, no quería hacer eso.

1030
00:48:08,850 --> 00:48:10,060
B pasa por aquí.

1031
00:48:10,060 --> 00:48:13,390
Así que tengo A y B y C. Y
Ahora aquí está otro estudiante A.

1032
00:48:13,390 --> 00:48:16,212
Pero si esta tabla hash es
implementado con una matriz,

1033
00:48:16,212 --> 00:48:17,920
Soy una especie de jodido
en este punto, ¿no?

1034
00:48:17,920 --> 00:48:19,510
Yo como que necesito poner esto en alguna parte.

1035
00:48:19,510 --> 00:48:24,380
>> Así que una manera de que pueda resolver esto es, todo
derecho, A está ocupada, B está ocupado, C está ocupado.

1036
00:48:24,380 --> 00:48:28,880
Voy a ponerlo en D. Así que en
primero, tengo acceso instantáneo al azar

1037
00:48:28,880 --> 00:48:31,064
a cada uno de los cubos para los estudiantes.

1038
00:48:31,064 --> 00:48:33,230
Pero ahora es una especie de degeneró
en algo lineal,

1039
00:48:33,230 --> 00:48:36,750
porque si quiero buscar a alguien
cuyo nombre comienza con A, puedo comprobar aquí.

1040
00:48:36,750 --> 00:48:38,854
Pero si esto no es el A
estudiante que estoy buscando,

1041
00:48:38,854 --> 00:48:41,520
Yo como que tengo que empezar a comprobar
los cubos, porque lo que hice

1042
00:48:41,520 --> 00:48:44,530
era una especie de forma lineal
sondear la estructura de datos.

1043
00:48:44,530 --> 00:48:47,710
Una forma estúpida de decir basta con ver
para la primera abertura disponible,

1044
00:48:47,710 --> 00:48:51,850
y poner como un plan B, por así decirlo,
o plan D en este caso, el valor

1045
00:48:51,850 --> 00:48:53,340
en esa ubicación.

1046
00:48:53,340 --> 00:48:56,470
Esto es justo lo que si ha
tiene 26 ubicaciones y no hay estudiantes

1047
00:48:56,470 --> 00:49:00,600
con el nombre de Q o Z, o algo así
que, al menos que esté utilizando el espacio.

1048
00:49:00,600 --> 00:49:03,140
>> Pero ya hemos visto más
soluciones inteligentes aquí, ¿verdad?

1049
00:49:03,140 --> 00:49:04,870
¿Qué haría usted en su lugar
si usted tiene un accidente?

1050
00:49:04,870 --> 00:49:06,670
Si dos personas tienen
el nombre de A, lo que haría

1051
00:49:06,670 --> 00:49:09,160
han sido más inteligente o más
solución intuitiva que sólo

1052
00:49:09,160 --> 00:49:12,840
poner una donde se supone que D a ser?

1053
00:49:12,840 --> 00:49:14,810
¿Por qué no sólo tiene que ir
afuera [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
como malloc, otro nodo, lo puso
aquí y, a continuación, poner que un estudiante aquí.

1055
00:49:19,960 --> 00:49:22,120
Así que básicamente tengo
algún tipo de una matriz,

1056
00:49:22,120 --> 00:49:25,590
o tal vez con más elegancia que a nosotros
empezando a ver una lista enlazada.

1057
00:49:25,590 --> 00:49:29,520
>> Y así una tabla hash es una estructura
que podría tener un aspecto como este,

1058
00:49:29,520 --> 00:49:33,900
pero más inteligentemente, algo llamado
encadenamiento separado, por el que una tabla hash

1059
00:49:33,900 --> 00:49:38,340
simplemente es una matriz, cada uno de
cuyos elementos no es un número,

1060
00:49:38,340 --> 00:49:40,470
es en sí mismo una lista enlazada.

1061
00:49:40,470 --> 00:49:45,080
Así que usted obtenga acceso súper rápido
decidir dónde hash de su valor a.

1062
00:49:45,080 --> 00:49:48,059
Al igual que con el ejemplo de las tarjetas,
Hice decisiones muy rápidas.

1063
00:49:48,059 --> 00:49:49,600
Corazones va aquí, los diamantes va aquí.

1064
00:49:49,600 --> 00:49:52,180
Lo mismo digo, A va aquí,
D va aquí, B va aquí.

1065
00:49:52,180 --> 00:49:55,740
Así super rápido look-ups, y si
le sucede a ejecutar en un caso

1066
00:49:55,740 --> 00:49:59,429
colisiones en el que tienes, dos
las personas con el mismo nombre, bueno, entonces

1067
00:49:59,429 --> 00:50:00,970
que acaba de empezar que los une.

1068
00:50:00,970 --> 00:50:03,900
Y tal vez mantenerlos ordenados
por orden alfabético, tal vez usted no lo hace.

1069
00:50:03,900 --> 00:50:05,900
Pero al menos ahora tenemos el dinamismo.

1070
00:50:05,900 --> 00:50:10,250
Así, por un lado tenemos súper rápido
constante de tiempo, y el tipo de tiempo lineal

1071
00:50:10,250 --> 00:50:14,110
involucrados si estas listas enlazadas
empezar a ser un poco larga.

1072
00:50:14,110 --> 00:50:16,880
>> Así que esta clase de tonto,
Hace años broma geek.

1073
00:50:16,880 --> 00:50:19,590
Al CS50 hack-a-thon,
cuando los estudiantes del check in,

1074
00:50:19,590 --> 00:50:22,040
algunos TF o CA cada año
piensa que es gracioso que aguantar

1075
00:50:22,040 --> 00:50:27,772
una señal de este tipo, donde se acaba
significa que si su nombre comienza con A,

1076
00:50:27,772 --> 00:50:28,870
ve por este camino.

1077
00:50:28,870 --> 00:50:31,110
Si su nombre comienza
con una B, vaya esto-- OK,

1078
00:50:31,110 --> 00:50:33,290
es curioso tal vez más tarde en el semestre.

1079
00:50:33,290 --> 00:50:36,420
Pero hay otra
manera de hacer esto, también.

1080
00:50:36,420 --> 00:50:37,410
Vuelve a eso.

1081
00:50:37,410 --> 00:50:38,600
>> Así que hay esta estructura.

1082
00:50:38,600 --> 00:50:40,420
Y esta es nuestra última
estructura para hoy,

1083
00:50:40,420 --> 00:50:42,400
que es algo que se llama un trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, que por alguna razón es corta
para la recuperación, pero que se llama trie.

1085
00:50:47,140 --> 00:50:51,389
Así que un trie es otro interesante
amalgama de muchas de estas ideas.

1086
00:50:51,389 --> 00:50:52,930
Es un árbol, lo que hemos visto antes.

1087
00:50:52,930 --> 00:50:54,180
No es un árbol de búsqueda binaria.

1088
00:50:54,180 --> 00:50:58,410
Es un árbol con cualquier número de hijos,
pero cada uno de los niños en un trie

1089
00:50:58,410 --> 00:51:00,090
es una matriz.

1090
00:51:00,090 --> 00:51:04,790
Una matriz de tamaño, digamos, 26 o tal vez 27
si quieres apoyar nombres con guiones

1091
00:51:04,790 --> 00:51:06,790
o apóstrofos en los nombres de las personas.

1092
00:51:06,790 --> 00:51:08,280
>> Y lo que esta es una estructura de datos.

1093
00:51:08,280 --> 00:51:10,290
Y si se mira desde arriba
a abajo, como si

1094
00:51:10,290 --> 00:51:13,710
mirar el nodo superior allí, M, es
que apunta a lo más a la izquierda allí,

1095
00:51:13,710 --> 00:51:17,665
que luego es A, X, W, E, L, L. Esto es
sólo una estructura de datos que de forma arbitraria

1096
00:51:17,665 --> 00:51:19,120
es almacenar nombres de las personas.

1097
00:51:19,120 --> 00:51:25,720
Y Maxwell se almacena con sólo seguir
un camino de matriz a matriz a matriz.

1098
00:51:25,720 --> 00:51:30,050
Pero lo que es sorprendente de un trie es
que, mientras que una lista enlazada e incluso

1099
00:51:30,050 --> 00:51:34,520
una matriz, el mejor que hemos conseguido es
tiempo lineal o logarítmica tiempo buscando

1100
00:51:34,520 --> 00:51:35,600
a alguien.

1101
00:51:35,600 --> 00:51:40,530
En esta estructura de datos de un trie, si
mi estructura de datos tiene un nombre en ella

1102
00:51:40,530 --> 00:51:43,720
y estoy en busca de Maxwell, estoy
ir a buscarlo rápidamente.

1103
00:51:43,720 --> 00:51:47,910
Yo sólo busco M-A-X-W-E-L-L. Si
esta estructura de datos, por el contrario,

1104
00:51:47,910 --> 00:51:51,830
si N es un millón, si hay una
millón de nombres en esta estructura de datos,

1105
00:51:51,830 --> 00:51:57,100
Maxwell todavía va a ser
detectable después de sólo M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
pasos.

1107
00:51:58,090 --> 00:52:01,276
Y los pasos David-- D-A-V-me-D.

1108
00:52:01,276 --> 00:52:03,400
En otras palabras, mediante la construcción
una estructura de datos que es

1109
00:52:03,400 --> 00:52:07,240
conseguido todos estos arrays, todos los cuales
ellos apoyan de acceso aleatorio,

1110
00:52:07,240 --> 00:52:11,090
Puedo empezar a buscar de la gente
nombre usando una cantidad de tiempo que es

1111
00:52:11,090 --> 00:52:14,340
proporcional a no el número
de las cosas en la estructura de datos,

1112
00:52:14,340 --> 00:52:16,330
como un millón de nombres existentes.

1113
00:52:16,330 --> 00:52:20,135
La cantidad de tiempo que me lleva a encontrar
M-A-X-W-E-L-L en esta estructura de datos se

1114
00:52:20,135 --> 00:52:22,260
proporcional no a la
tamaño de la estructura de datos,

1115
00:52:22,260 --> 00:52:25,930
pero a la longitud del nombre.

1116
00:52:25,930 --> 00:52:28,440
Y realista el
nombres que están mirando hacia arriba

1117
00:52:28,440 --> 00:52:29,970
Nunca van a estar loco de largo.

1118
00:52:29,970 --> 00:52:32,600
Tal vez alguien tiene un carácter 10
nombre, nombre de 20 caracteres.

1119
00:52:32,600 --> 00:52:33,900
Ciertamente es finita, ¿verdad?

1120
00:52:33,900 --> 00:52:37,110
No es un ser humano en la Tierra que
tiene el nombre más largo posible,

1121
00:52:37,110 --> 00:52:39,920
pero ese nombre es una constante
longitud de valor, ¿no?

1122
00:52:39,920 --> 00:52:41,980
Es no varía en ningún sentido.

1123
00:52:41,980 --> 00:52:45,090
Así de esta manera, tenemos
logrado una estructura de datos

1124
00:52:45,090 --> 00:52:47,800
es decir constante de tiempo de consulta.

1125
00:52:47,800 --> 00:52:50,670
Sin embargo, toma una serie de medidas
dependiendo de la longitud de la entrada,

1126
00:52:50,670 --> 00:52:54,250
pero no el número del nombre
en la estructura de datos.

1127
00:52:54,250 --> 00:52:58,700
Así que si duplicamos el número de nombres
el año que viene a partir de un mil millones a dos mil millones,

1128
00:52:58,700 --> 00:53:03,720
hallazgo Maxwell va a tomar
el mismo número exacto de siete pasos

1129
00:53:03,720 --> 00:53:04,650
para encontrarlo.

1130
00:53:04,650 --> 00:53:08,810
Y así parece que hemos logrado
nuestro santo grial de tiempo de ejecución.

1131
00:53:08,810 --> 00:53:10,860
>> Así que un par de anunciar.

1132
00:53:10,860 --> 00:53:11,850
Cuestionario cero se acerca.

1133
00:53:11,850 --> 00:53:14,600
Más sobre esto en la página web del curso
durante el próximo par de días.

1134
00:53:14,600 --> 00:53:17,120
Lunes de lecture-- Es un día de fiesta
aquí en Harvard el lunes.

1135
00:53:17,120 --> 00:53:18,850
No está en New Haven,
así que estamos tomando la clase

1136
00:53:18,850 --> 00:53:20,310
a New Haven de la conferencia el lunes.

1137
00:53:20,310 --> 00:53:22,550
Todo será filmado
y transmitido en vivo como siempre,

1138
00:53:22,550 --> 00:53:24,900
pero vamos a terminar hoy
con un clip de 30 segundos

1139
00:53:24,900 --> 00:53:26,910
llamados "Pensamientos profundos"
por Daven Farnham, que

1140
00:53:26,910 --> 00:53:30,850
se inspiró el año pasado por Sábado
"Pensamientos profundos" de Night Live

1141
00:53:30,850 --> 00:53:35,700
por Jack práctico, que
Ahora debe tener sentido.

1142
00:53:35,700 --> 00:53:38,810
>> CINE: Y ahora, "Deep
Pensamientos "de Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tabla de picadillo.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> ALTAVOZ 1: Muy bien, eso es todo por ahora.

1147
00:53:47,660 --> 00:53:48,805
Nos vemos la semana que viene.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Para ver en acción.

1150
00:53:56,680 --> 00:53:58,304
Así que vamos a echar un vistazo a eso ahora mismo.

1151
00:53:58,304 --> 00:53:59,890
Así que aquí tenemos una matriz sin clasificar.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, ¿puedes seguir adelante y reinicio
esto por sólo un segundo, por favor.

1153
00:54:04,860 --> 00:54:08,562
De acuerdo, las cámaras están rodando, por lo
acción cada vez que esté listo, Doug, ¿de acuerdo?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Muy bien, así que lo que
tenemos aquí es una serie sin clasificar.

1155
00:54:11,020 --> 00:54:13,960
Y he coloreé todos los elementos
rojo para indicar que es, de hecho,

1156
00:54:13,960 --> 00:54:14,460
sin clasificar.

1157
00:54:14,460 --> 00:54:17,960
Así que recordemos que la primera cosa que hacemos
es clasificamos la mitad izquierda de la matriz.

1158
00:54:17,960 --> 00:54:20,630
Luego clasificamos la derecha
medio de la matriz.

1159
00:54:20,630 --> 00:54:22,830
Y ya-da, ya-da, ya-da,
les funden.

1160
00:54:22,830 --> 00:54:24,520
Y tenemos una gama completamente ordenado.

1161
00:54:24,520 --> 00:54:25,360
Así es como fusionar tipo de obras.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Espera, espera, espera,
cortar, cortar, cortar, cortar.

1163
00:54:27,109 --> 00:54:30,130
Doug, no puedes simplemente ya-da, ya-da,
ya-da, su camino a través de combinación de clase.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Me acaba de hacer.

1165
00:54:31,970 --> 00:54:32,832
Está bien.

1166
00:54:32,832 --> 00:54:33,540
Somos buenos para ir.

1167
00:54:33,540 --> 00:54:34,760
Sigamos la rodadura.

1168
00:54:34,760 --> 00:54:35,380
Así que de todos modos,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Usted tiene que explicar
más plenamente que eso.

1170
00:54:37,800 --> 00:54:39,999
Eso no es suficiente.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, no lo hacemos
que tenga que volver a uno.

1172
00:54:41,790 --> 00:54:42,350
Está bien.

1173
00:54:42,350 --> 00:54:45,690
Así que de todos modos, si seguimos con merge--
Ian, estamos en medio de la filmación.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Lo sé.

1175
00:54:46,612 --> 00:54:49,320
Y no podemos simplemente ya-da, ya-da,
ya-da, a través de todo el proceso.

1176
00:54:49,320 --> 00:54:52,200
Usted tiene que explicar cómo el
Ambas partes quedan fusionadas juntas.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Pero ya hemos
explicó cómo los dos sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Usted acaba mostrará
ellos una matriz de mezcla.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Ellos conocen el proceso.

1180
00:54:56,486 --> 00:54:57,172
Ellos están bien.

1181
00:54:57,172 --> 00:54:58,380
Hemos pasado más de diez veces.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Usted acaba de saltar por encima de ella.

1183
00:55:00,330 --> 00:55:03,360
Vamos a volver a uno,
¿no es así ya-da, ya-da sobre él.

1184
00:55:03,360 --> 00:55:05,480
Muy bien, de nuevo a uno.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Tengo que volver
a través de todas las diapositivas?

1186
00:55:07,833 --> 00:55:08,332
Dios mío.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Es como la sexta vez, Ian.

1189
00:55:13,004 --> 00:55:13,940
Está bien.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: De acuerdo.

1191
00:55:15,200 --> 00:55:16,590
¿Estás listo?

1192
00:55:16,590 --> 00:55:17,400
Excelente.

1193
00:55:17,400 --> 00:55:18,950
Acción.