1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [REPRODUCCIÓN DE MÚSICA] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID MALAN: Este es CS50. 5 00:00:14,010 --> 00:00:18,090 Y esto es a la vez el principio y el end-- como literally-- casi el final 6 00:00:18,090 --> 00:00:18,825 de la semana seis. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Yo pensé en compartir un poco de un hecho divertido. 9 00:00:22,640 --> 00:00:25,370 He tirado esto desde un conjunto de datos del semestre pasado. 10 00:00:25,370 --> 00:00:29,710 Usted puede recordar que le pedimos en cada forma conjunto p si has visto en línea 11 00:00:29,710 --> 00:00:31,580 o si usted ha asistido en persona. 12 00:00:31,580 --> 00:00:33,020 Y aquí están los datos. 13 00:00:33,020 --> 00:00:34,710 Así que estaba muy predecible hoy. 14 00:00:34,710 --> 00:00:37,126 Pero nosotros queríamos pasar un poco de tiempo con usted, no obstante. 15 00:00:37,126 --> 00:00:40,599 ¿Alguien quiere conjeturar por qué esto gráfico es tan jaggy, arriba abajo, arriba abajo, 16 00:00:40,599 --> 00:00:41,265 tan consistentemente? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Qué hacer cada uno de los picos y depresiones representan? 19 00:00:45,130 --> 00:00:46,005 >> AUDIENCIA: [inaudible] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: En efecto. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Y más divertida, Dios no lo quiera, tenemos una conferencia en un viernes 24 00:00:55,480 --> 00:00:58,960 al inicio del semestre, eso es lo que suceda. 25 00:00:58,960 --> 00:01:03,430 Así que hoy, participamos en un poco Más información sobre las estructuras de datos. 26 00:01:03,430 --> 00:01:06,660 Y para darle más de un sólido modelo mental de los problemas a las cinco, 27 00:01:06,660 --> 00:01:07,450 que ahora está fuera. 28 00:01:07,450 --> 00:01:10,817 Errores de ortografía, en el que, vamos a que entregar un archivo de texto unos 100.000 29 00:01:10,817 --> 00:01:12,650 además de las palabras en inglés, y usted va a tener 30 00:01:12,650 --> 00:01:17,770 para encontrar la manera de cargar ellos inteligentemente en la memoria, en la memoria RAM, el uso de algunos datos 31 00:01:17,770 --> 00:01:19,330 estructura de su elección. 32 00:01:19,330 --> 00:01:22,470 >> Ahora bien, una estructura de este tipo de datos podría ser, pero probablemente no debería ser, 33 00:01:22,470 --> 00:01:25,630 la lista enlazada bastante simplista, que se introdujo la última vez. 34 00:01:25,630 --> 00:01:29,220 Y una lista enlazada tenía por lo menos una ventaja sobre una matriz. 35 00:01:29,220 --> 00:01:32,096 ¿Cuál es una de las ventajas de una lista enlazada discutible? 36 00:01:32,096 --> 00:01:32,950 >> AUDIENCIA: Inserción. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: Inserción. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 ¿Qué quieres decir con eso? 40 00:01:35,196 --> 00:01:37,872 >> AUDIENCIA: En cualquier lugar a lo largo de la lista de [inaudible]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: Good. 42 00:01:38,770 --> 00:01:42,090 Así que usted puede insertar un elemento siempre que sea que quieres en la mitad de la lista 43 00:01:42,090 --> 00:01:45,490 sin tener que mezclar nada, que llegamos a la conclusión, en nuestra clasificación 44 00:01:45,490 --> 00:01:47,630 discusiones, no es necesariamente una buena cosa, 45 00:01:47,630 --> 00:01:51,200 porque se necesita tiempo para moverse en realidad todos esos seres humanos hacia la izquierda o derecha. 46 00:01:51,200 --> 00:01:55,540 Y así, con una lista enlazada, puede simplemente asignar con malloc, un nuevo nodo, 47 00:01:55,540 --> 00:01:58,385 y luego actualizar un par de pointers-- dos, tres operaciones max-- 48 00:01:58,385 --> 00:02:01,480 y somos capaces de ranura alguien en cualquier lugar en una lista. 49 00:02:01,480 --> 00:02:03,550 >> ¿Qué otra cosa era ventajoso acerca de una lista enlazada? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 ¿Sí? 52 00:02:05,659 --> 00:02:06,534 >> AUDIENCIA: [inaudible] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID MALAN: Perfecto. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfect. 57 00:02:11,090 --> 00:02:12,070 Es muy dinámico. 58 00:02:12,070 --> 00:02:15,100 Y eso que no estás cometiendo, de antemano, hasta cierto tamaño fijo 59 00:02:15,100 --> 00:02:18,750 trozo de memoria, al igual que usted tendría a con una matriz, el alza de los cuales 60 00:02:18,750 --> 00:02:22,455 es que se puede asignar nodos sólo en la demanda de este modo utilizando sólo la cantidad de espacio 61 00:02:22,455 --> 00:02:23,330 como que realmente necesita. 62 00:02:23,330 --> 00:02:26,830 A diferencia de una matriz, que te pueden asignar accidentalmente demasiado poco. 63 00:02:26,830 --> 00:02:28,871 Y entonces sólo va a ser un dolor en el cuello 64 00:02:28,871 --> 00:02:32,440 reasignar una nueva matriz más grande, copiar todo lo más, liberar la matriz de edad, 65 00:02:32,440 --> 00:02:33,990 y luego pasar sobre su negocio. 66 00:02:33,990 --> 00:02:37,479 O peor aún, es posible asignar de manera más memoria de la que realmente se necesita, 67 00:02:37,479 --> 00:02:40,520 y por lo que vamos a tener un muy matriz escasamente pobladas, por así decirlo. 68 00:02:40,520 --> 00:02:44,350 >> Así que una lista enlazada que da a estos ventajas de dinamismo y flexibilidad 69 00:02:44,350 --> 00:02:46,080 con inserciones y deleciones. 70 00:02:46,080 --> 00:02:48,000 Pero sin duda que debe haber un precio que se paga. 71 00:02:48,000 --> 00:02:50,000 De hecho, uno de los temas explorado en concurso cero 72 00:02:50,000 --> 00:02:52,430 era un par de las compensaciones que hemos visto hasta el momento. 73 00:02:52,430 --> 00:02:56,161 Así que lo que es un precio pagado o por un la baja de una lista enlazada? 74 00:02:56,161 --> 00:02:56,660 Sí. 75 00:02:56,660 --> 00:02:57,560 >> AUDIENCIA: No hay acceso aleatorio. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: No hay acceso aleatorio. 77 00:02:58,809 --> 00:02:59,540 Pero a quién le importa? 78 00:02:59,540 --> 00:03:01,546 Acceso aleatorio no suena convincente. 79 00:03:01,546 --> 00:03:02,421 >> AUDIENCIA: [inaudible] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Exactamente. 82 00:03:05,740 --> 00:03:07,580 Si usted quiere tener un cierto algorithm-- 83 00:03:07,580 --> 00:03:10,170 y que me haga realidad propongo búsqueda binaria, en particular, que 84 00:03:10,170 --> 00:03:12,600 es uno que hemos utilizado bastante bit-- si usted no tiene acceso al azar, 85 00:03:12,600 --> 00:03:15,516 no se puede hacer así de simple aritmética de encontrar como el elemento medio 86 00:03:15,516 --> 00:03:16,530 y saltar a la derecha a la misma. 87 00:03:16,530 --> 00:03:20,239 En su lugar, tiene que empezar por el primero elemento y linealmente buscar desde la izquierda 88 00:03:20,239 --> 00:03:22,780 a derecha si quieres encontrar el medio o cualquier otro elemento. 89 00:03:22,780 --> 00:03:24,410 >> AUDIENCIA: Probablemente tiene más memoria. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: Toma más memoria. 91 00:03:25,040 --> 00:03:27,464 ¿Dónde está ese adicional coste que viene de en la memoria? 92 00:03:27,464 --> 00:03:28,339 >> AUDIENCIA: [inaudible] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Exactamente. 95 00:03:33,440 --> 00:03:35,679 En este caso aquí, tuvimos una lista enlazada para enteros, 96 00:03:35,679 --> 00:03:37,470 y sin embargo, estamos duplicando la cantidad de memoria 97 00:03:37,470 --> 00:03:39,680 necesitamos también por el almacenamiento de estos punteros. 98 00:03:39,680 --> 00:03:42,090 Ahora menos de un gran problema ya sus estructuras se hacen más grandes 99 00:03:42,090 --> 00:03:45,320 y usted está almacenando no es un número, pero tal vez un estudiante o algún otro objeto. 100 00:03:45,320 --> 00:03:46,880 Pero el punto sigue siendo duda. 101 00:03:46,880 --> 00:03:49,421 Y por lo que un número de las operaciones en listas enlazadas fueron llamados 102 00:03:49,421 --> 00:03:50,570 eran grandes O de n-- lineal. 103 00:03:50,570 --> 00:03:54,730 Cosas como la inserción o búsqueda o eliminación en caso de un elemento 104 00:03:54,730 --> 00:03:57,720 pasó a ser al final de la lista si está ordenada o no. 105 00:03:57,720 --> 00:04:01,167 >> A veces puede que tengas suerte y en fuera de modo más bajos en estas operaciones 106 00:04:01,167 --> 00:04:04,250 También podría ser la constante de tiempo si estás siempre mirando al primer elemento, 107 00:04:04,250 --> 00:04:05,070 por ejemplo. 108 00:04:05,070 --> 00:04:09,360 Pero en última instancia, nos prometimos para lograr el santo grial 109 00:04:09,360 --> 00:04:12,630 de estructuras de datos, o algunos de los mismos aproximación, 110 00:04:12,630 --> 00:04:14,290 por medio de la constante de tiempo. 111 00:04:14,290 --> 00:04:17,579 ¿Podemos encontrar elementos o añadir elementos o eliminar elementos de una lista? 112 00:04:17,579 --> 00:04:19,059 Nos veremos muy pronto. 113 00:04:19,059 --> 00:04:21,100 Y resulta que uno de los mecanismos que estamos 114 00:04:21,100 --> 00:04:23,464 va a empezar a utilizar hoy en día, el uso anual de P puesto cinco, 115 00:04:23,464 --> 00:04:24,630 en realidad es bastante familiar. 116 00:04:24,630 --> 00:04:27,430 Por ejemplo, si se trata de un montón de libros de examen, cada uno de los cuales 117 00:04:27,430 --> 00:04:29,660 tiene un estudiante de primero nombre y apellido en él, 118 00:04:29,660 --> 00:04:31,820 y yo los recojo de la al final de un examen, 119 00:04:31,820 --> 00:04:33,746 y son todos bastante tanto en un orden aleatorio, 120 00:04:33,746 --> 00:04:36,370 y queremos ir sobre la clasificación estos exámenes para que una vez clasificadas 121 00:04:36,370 --> 00:04:38,661 es sólo mucho más fácil y más rápido a entregarlos de vuelta 122 00:04:38,661 --> 00:04:40,030 a los estudiantes en orden alfabético. 123 00:04:40,030 --> 00:04:42,770 ¿Cuáles serían sus instintos para una pila de exámenes de este tipo? 124 00:04:42,770 --> 00:04:45,019 >> Bueno, si eres como yo, podría ver que este es m, 125 00:04:45,019 --> 00:04:48,505 así que me voy a poner esto en una especie de, si este es mi mesa o mi piso donde 126 00:04:48,505 --> 00:04:50,650 Estoy extendiendo cosas fuera-- o mi arsenal realmente-- 127 00:04:50,650 --> 00:04:52,210 Yo podría poner toda la Sra allí. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 He aquí una A. Así que podría Como poner los de aquí. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Aquí hay otra A. Voy poner que aquí. 132 00:04:57,980 --> 00:05:02,490 Aquí hay una Z. Aquí hay otro M. Y así Yo podría empezar a hacer montones como este. 133 00:05:02,490 --> 00:05:06,620 Y entonces tal vez me gustaría ir en adelante y una especie de muy quisquillosa-ly especie 134 00:05:06,620 --> 00:05:07,710 las pilas individuales. 135 00:05:07,710 --> 00:05:11,300 Pero el punto es, buscaría en la entrada que estoy sola mano 136 00:05:11,300 --> 00:05:14,016 y me gustaría hacer algunos calculé decisión basada en esa entrada. 137 00:05:14,016 --> 00:05:15,640 Si comienza con A, lo puso allí. 138 00:05:15,640 --> 00:05:18,980 Si empieza por Z, lo puso sobre allí, y todo lo demás. 139 00:05:18,980 --> 00:05:22,730 >> Así que esta es una técnica que es generalmente conocido como hashing-- H-A-S-H- 140 00:05:22,730 --> 00:05:26,550 que por lo general significa tomar como de entrada y utilizar esa entrada para calcular 141 00:05:26,550 --> 00:05:30,940 un valor, en general, un número, y que número es el índice en un almacenamiento 142 00:05:30,940 --> 00:05:32,260 contenedor, como una matriz. 143 00:05:32,260 --> 00:05:35,490 Así que en otras palabras, que podría tener una función hash, como lo hago en mi cabeza, 144 00:05:35,490 --> 00:05:37,940 que si veo a alguien es nombre que comienza con A, 145 00:05:37,940 --> 00:05:40,190 Voy a asignar que a cero en mi cabeza. 146 00:05:40,190 --> 00:05:44,160 Y si veo a alguien con Z, estoy ir al mapa que a 25 en mi cabeza 147 00:05:44,160 --> 00:05:46,220 y luego poner esto en la última pila más. 148 00:05:46,220 --> 00:05:50,990 >> Ahora, si lo piensas, no mi cerebro pero un programa en C, lo que los números podrían 149 00:05:50,990 --> 00:05:53,170 usted confía en lograr el mismo resultado? 150 00:05:53,170 --> 00:05:55,594 En otras palabras, si tenía el carácter ASCII A, 151 00:05:55,594 --> 00:05:57,510 ¿cómo determinar lo balde para poner en? 152 00:05:57,510 --> 00:05:59,801 Es probable que no quiere lo puso en el cubo 65, que 153 00:05:59,801 --> 00:06:01,840 sería como de allá sin una buena razón. 154 00:06:01,840 --> 00:06:04,320 ¿Dónde quieres poner un en términos de su valor ASCII? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 ¿Dónde quieres que hacer para su ASCII valor para llegar a un cubo inteligente 157 00:06:08,920 --> 00:06:09,480 para poner en? 158 00:06:09,480 --> 00:06:10,206 >> AUDIENCIA: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Sí. 160 00:06:10,956 --> 00:06:13,190 Así menos A o menos específicamente 65 si es 161 00:06:13,190 --> 00:06:18,240 un capital de A. O 98 si se trata de una minúscula. 162 00:06:18,240 --> 00:06:21,300 Y por lo que nos permitiría, muy simplemente y muy aritméticamente, 163 00:06:21,300 --> 00:06:23,260 poner algo en un cubo así. 164 00:06:23,260 --> 00:06:26,010 Así que resulta que en realidad hacemos esto también incluso con los concursos. 165 00:06:26,010 --> 00:06:29,051 >> Así que usted puede recordar que marcaste tu Nombre de la enseñanza de su compañero en la portada. 166 00:06:29,051 --> 00:06:32,270 Y se organizaron nombres del TF en estas columnas en orden alfabético, 167 00:06:32,270 --> 00:06:34,400 Bueno, lo creas o no, cuando todo 80 más de nosotros 168 00:06:34,400 --> 00:06:37,800 se reunieron la otra noche a grado, el último paso en nuestro proceso de clasificación 169 00:06:37,800 --> 00:06:41,830 es para discutir las pruebas en un gran espacio de suelo en la [inaudible] 170 00:06:41,830 --> 00:06:45,110 y sentar pruebas de todo el mundo a exactamente en el orden de sus de TF 171 00:06:45,110 --> 00:06:47,700 nombres en la cubierta, ya que entonces es mucho más fácil para nosotros 172 00:06:47,700 --> 00:06:51,290 para buscar a través de que el uso lineal buscar o algún tipo de inteligencia 173 00:06:51,290 --> 00:06:54,050 para un TF para encontrar su o pruebas de sus estudiantes. 174 00:06:54,050 --> 00:06:56,060 >> Así que esta idea de hash que verás es 175 00:06:56,060 --> 00:07:00,520 bastante poderoso es en realidad bastante lugar común y muy intuitiva, 176 00:07:00,520 --> 00:07:03,000 al igual que quizás dividir y conquista fue en la semana cero. 177 00:07:03,000 --> 00:07:05,250 Me avance rápido para el hackathon un par de años atrás. 178 00:07:05,250 --> 00:07:08,040 Este fue Zamyla y un par de otros estudiantes de felicitación personal 179 00:07:08,040 --> 00:07:09,030 como entraron. 180 00:07:09,030 --> 00:07:12,680 Y tuvimos un montón de plegado mesas allí con etiquetas de nombre. 181 00:07:12,680 --> 00:07:15,380 Y habíamos organizado las etiquetas de nombre con como el As de allá 182 00:07:15,380 --> 00:07:16,690 y la Zs allá. 183 00:07:16,690 --> 00:07:20,350 Y así uno de los TFS muy inteligentemente escribió esto como las instrucciones 184 00:07:20,350 --> 00:07:21,030 para el día. 185 00:07:21,030 --> 00:07:24,480 Y en la semana 12 del semestre este todo tenía sentido perfecto y todo el mundo 186 00:07:24,480 --> 00:07:25,310 sabía qué hacer. 187 00:07:25,310 --> 00:07:27,900 Pero en cualquier momento que tienes en cola de la misma manera, 188 00:07:27,900 --> 00:07:30,272 está implementando la misma noción de un hash. 189 00:07:30,272 --> 00:07:31,730 Así que vamos a formalizar un poco. 190 00:07:31,730 --> 00:07:32,890 Aquí es una matriz. 191 00:07:32,890 --> 00:07:36,820 Se señaló a ser un poco amplia acaba de describir, visualmente, 192 00:07:36,820 --> 00:07:38,920 que podríamos poner cadenas en algo como esto. 193 00:07:38,920 --> 00:07:41,970 Y esta matriz es claramente de tamaño 26 total. 194 00:07:41,970 --> 00:07:43,935 Y la cosa se llama mesa arbitrariamente. 195 00:07:43,935 --> 00:07:48,930 Pero esto es sólo una representación artística de lo que podría ser una tabla hash. 196 00:07:48,930 --> 00:07:52,799 >> Así que una tabla hash ahora va a ser una estructura de datos de nivel superior. 197 00:07:52,799 --> 00:07:54,840 Al final del día estamos a punto de ver que usted 198 00:07:54,840 --> 00:07:58,700 puede aplicar una tabla hash, que es muy similar a la línea de check-in 199 00:07:58,700 --> 00:08:02,059 en un hackathon mucho como este tabla utilizada para la clasificación de los libros de examen. 200 00:08:02,059 --> 00:08:03,850 Pero una tabla hash es especie de este alto nivel 201 00:08:03,850 --> 00:08:08,250 concepto que podría utilizar una matriz debajo del capó para implementarlo, 202 00:08:08,250 --> 00:08:11,890 o puede utilizar una lista de longitud, o incluso tal vez algunas otras estructuras de datos. 203 00:08:11,890 --> 00:08:15,590 Y eso sí que es la toma theme-- algunos de estos ingredientes fundamentales 204 00:08:15,590 --> 00:08:18,310 como una matriz y este edificio bloquear ahora una lista de longitud 205 00:08:18,310 --> 00:08:21,740 y ver qué más podemos construir en la parte superior de los que, como ingredientes 206 00:08:21,740 --> 00:08:26,550 en una receta, lo que hace más y más los resultados finales interesantes y útiles. 207 00:08:26,550 --> 00:08:28,680 >> Así que con la tabla hash podríamos implementarlo 208 00:08:28,680 --> 00:08:32,540 en la memoria pictóricamente como este, pero cómo podría en realidad ser codificada para arriba? 209 00:08:32,540 --> 00:08:33,789 Bueno, tal vez la forma más sencilla es esta. 210 00:08:33,789 --> 00:08:38,270 Si la capacidad en todas las tapas, es sólo algunos constant-- por ejemplo 26, 211 00:08:38,270 --> 00:08:42,030 para 26 letras del alphabet-- Yo podría llamar a mi tabla de variables, 212 00:08:42,030 --> 00:08:45,630 y yo podría decir que me voy a poner estrellas Char allí, o una cadena. 213 00:08:45,630 --> 00:08:49,880 Así que es tan simple como esto si desee implementar una tabla hash. 214 00:08:49,880 --> 00:08:51,490 Y, sin embargo, esto es en realidad una matriz. 215 00:08:51,490 --> 00:08:53,198 Pero, de nuevo, un hash tabla es ahora lo que vamos a 216 00:08:53,198 --> 00:08:57,470 llamar a un tipo de datos abstracto que sólo una especie de estratificación conceptual en la parte superior 217 00:08:57,470 --> 00:09:00,780 de algo más mundano ahora como un array. 218 00:09:00,780 --> 00:09:02,960 >> Ahora, ¿cómo hacemos para sobre la resolución de problemas? 219 00:09:02,960 --> 00:09:06,980 Bueno, antes tuve el lujo de tener suficiente espacio de tabla aquí 220 00:09:06,980 --> 00:09:09,460 para que yo pudiera poner el concursos en cualquier lugar que quería. 221 00:09:09,460 --> 00:09:10,620 De manera que se puede ir aquí. 222 00:09:10,620 --> 00:09:12,100 Zs pueden ir aquí. 223 00:09:12,100 --> 00:09:13,230 Sra podría ir aquí. 224 00:09:13,230 --> 00:09:14,740 Y luego tuve un poco de espacio extra. 225 00:09:14,740 --> 00:09:18,740 Pero esto es un poco de un derecho de trucos ahora porque esta tabla, si realmente 226 00:09:18,740 --> 00:09:22,720 pensado en ello como una matriz, es justo va a ser de algún tamaño fijo. 227 00:09:22,720 --> 00:09:25,380 >> Así que técnicamente, si me tire hasta prueba de otro estudiante 228 00:09:25,380 --> 00:09:28,490 y ver, oh, esta persona de nombre comienza con una A también, 229 00:09:28,490 --> 00:09:30,980 Yo como que quiero poner ahí. 230 00:09:30,980 --> 00:09:34,740 Pero tan pronto como me puse allí, si esta tabla de hecho representa una matriz, 231 00:09:34,740 --> 00:09:37,840 Yo voy a estar anulando o clobbering quienquiera concurso de este estudiante es. 232 00:09:37,840 --> 00:09:38,340 Derecha? 233 00:09:38,340 --> 00:09:41,972 Si se trata de una matriz, sólo una cosa puede ir en cada una de estas células o elementos. 234 00:09:41,972 --> 00:09:43,680 Y así que tipo de tener a escoger y elegir. 235 00:09:43,680 --> 00:09:45,735 >> Ahora antes que tipo de engañado e hizo esto o yo 236 00:09:45,735 --> 00:09:47,526 sólo tipo de apilado ellos uno encima del otro. 237 00:09:47,526 --> 00:09:49,170 Pero eso no va a volar en código. 238 00:09:49,170 --> 00:09:52,260 Entonces, ¿dónde podría yo poner el segundo estudiante cuyo nombre 239 00:09:52,260 --> 00:09:54,964 Una es si todo lo que tenía es este espacio de tablas disponibles? 240 00:09:54,964 --> 00:09:57,880 Y yo he usado tres ranuras y se parece que hay sólo unos pocos otros. 241 00:09:57,880 --> 00:09:58,959 ¿Qué podría hacer? 242 00:09:58,959 --> 00:09:59,834 AUDIENCIA: [inaudible] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID MALAN: Sí. 245 00:10:01,315 --> 00:10:02,370 Tal vez vamos a mantenerlo simple. 246 00:10:02,370 --> 00:10:02,660 Derecha? 247 00:10:02,660 --> 00:10:04,243 No se ajusta a donde quiero ponerlo. 248 00:10:04,243 --> 00:10:07,450 Así que me voy a poner técnicamente, donde un B iría. 249 00:10:07,450 --> 00:10:09,932 Ahora, por supuesto, estoy empezando para pintar a mí mismo en una esquina. 250 00:10:09,932 --> 00:10:11,890 Si llego a un estudiante cuyo nombre es en realidad B, 251 00:10:11,890 --> 00:10:14,840 ahora B va a ser movido un poco hacia adelante, como podría suceder, sí, 252 00:10:14,840 --> 00:10:17,530 si esto es un B, ahora tiene que ir aquí. 253 00:10:17,530 --> 00:10:20,180 >> Y por lo que este muy rápidamente podría convertirse en un problema, 254 00:10:20,180 --> 00:10:23,850 pero es una técnica que en realidad se conoce como sondeo lineal, 255 00:10:23,850 --> 00:10:26,650 por el que usted sólo considera su matriz a ser a lo largo de la línea. 256 00:10:26,650 --> 00:10:29,680 Y que acaba de tipo de sonda o inspeccionar cada elemento disponible 257 00:10:29,680 --> 00:10:31,360 en busca de un lugar disponible. 258 00:10:31,360 --> 00:10:34,010 Y tan pronto como se entere uno, se te cae en ese país. 259 00:10:34,010 --> 00:10:38,390 >> Ahora, el precio que se paga ahora para esta solución es lo que? 260 00:10:38,390 --> 00:10:41,300 Tenemos una matriz de tamaño fijo, y cuando inserto nombres 261 00:10:41,300 --> 00:10:44,059 en ella, al menos al principio, lo que es el tiempo de ejecución de la inserción 262 00:10:44,059 --> 00:10:46,350 para poner a los estudiantes concursos en los cubos de la derecha? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O de qué? 265 00:10:50,002 --> 00:10:51,147 >> AUDIENCIA: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Escuché gran O de n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 No es cierto. 269 00:10:54,300 --> 00:10:56,490 Pero vamos a desmenuzar ¿por qué en un momento. 270 00:10:56,490 --> 00:10:57,702 ¿Qué otra cosa podría ser? 271 00:10:57,702 --> 00:10:58,755 >> AUDIENCIA: [inaudible] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN: Y me dejó hacer visualmente. 273 00:11:00,380 --> 00:11:04,720 Así que supongamos que esta es la letra S. 274 00:11:04,720 --> 00:11:05,604 >> AUDIENCIA: Es uno. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Es uno. 276 00:11:06,520 --> 00:11:06,710 Derecha? 277 00:11:06,710 --> 00:11:08,950 Esta es una matriz, que significa que tenemos acceso aleatorio. 278 00:11:08,950 --> 00:11:11,790 Y si pensamos en esto como cero y esto como 25, 279 00:11:11,790 --> 00:11:13,800 y nos damos cuenta de que, oh, aquí está mi entrada S, 280 00:11:13,800 --> 00:11:16,350 Ciertamente puedo convertir S, un carácter ASCII, 281 00:11:16,350 --> 00:11:18,540 a un número correspondiente entre cero y 25 282 00:11:18,540 --> 00:11:20,910 y luego inmediatamente puso donde pertenece. 283 00:11:20,910 --> 00:11:26,120 >> Pero, por supuesto, tan pronto como llegue a la segunda persona cuyo nombre es A o B o C 284 00:11:26,120 --> 00:11:29,300 finalmente, si yo he usado el sondeo lineal como mi solución, 285 00:11:29,300 --> 00:11:31,360 el tiempo de ejecución de inserción en el peor de los casos 286 00:11:31,360 --> 00:11:33,120 que realmente se va a delegar en qué? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Y yo lo escuché aquí correctamente desde el principio. 289 00:11:36,045 --> 00:11:36,920 AUDIENCIA: [inaudible] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: Por lo que es de hecho una vez n usted tiene un conjunto de datos suficientemente grande. 291 00:11:41,620 --> 00:11:44,410 Así, por un lado, si su matriz es suficientemente grande 292 00:11:44,410 --> 00:11:48,287 y sus datos son escasos suficiente, conseguir este hermoso tiempo constante. 293 00:11:48,287 --> 00:11:50,620 Pero tan pronto como empiece cada vez más y más elementos, 294 00:11:50,620 --> 00:11:53,200 y sólo estadísticamente se obtiene más personas con la letra 295 00:11:53,200 --> 00:11:56,030 A como su nombre o la letra B, podría potencialmente 296 00:11:56,030 --> 00:11:57,900 delegar en algo más lineal. 297 00:11:57,900 --> 00:11:59,640 Así que no es perfecto. 298 00:11:59,640 --> 00:12:00,690 Así que podríamos hacer mejor? 299 00:12:00,690 --> 00:12:03,210 >> Bueno, lo que fue nuestra solución antes cuando nos 300 00:12:03,210 --> 00:12:06,820 quieren tener más dinamismo que algo así como una gran variedad permitido? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 AUDIENCIA: [inaudible] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: ¿Qué hemos presentamos? 304 00:12:10,030 --> 00:12:10,530 Sí. 305 00:12:10,530 --> 00:12:11,430 Así que una lista enlazada. 306 00:12:11,430 --> 00:12:14,430 Bueno, vamos a ver que es lo vinculado lista podría hacer por nosotros en su lugar. 307 00:12:14,430 --> 00:12:17,630 Bueno, déjame propongo que dibujar la imagen de la siguiente manera. 308 00:12:17,630 --> 00:12:19,620 Ahora bien, este es un diferente imagen de un ejemplo 309 00:12:19,620 --> 00:12:24,750 a partir de un texto diferente, en realidad, que es en realidad el uso de una matriz de tamaño 31. 310 00:12:24,750 --> 00:12:28,220 Y este autor simplemente decidido hash de cadenas 311 00:12:28,220 --> 00:12:32,430 no se basa en los nombres de la persona, pero en función de sus fechas de nacimiento. 312 00:12:32,430 --> 00:12:35,680 Independientemente del mes, se dieron cuenta si lo que se nace en el primero de un mes 313 00:12:35,680 --> 00:12:39,580 o el 31 de un mes, el autor se hash basado en ese valor, 314 00:12:39,580 --> 00:12:44,154 a fin de difundir los nombres un poco más que 26 puntos podrían permitir. 315 00:12:44,154 --> 00:12:47,320 Y tal vez es un poco más uniforme que ir con las letras del alfabeto, 316 00:12:47,320 --> 00:12:50,236 porque, por supuesto, es probable que haya más personas en el mundo con nombres 317 00:12:50,236 --> 00:12:54,020 que comienzan con una que sin duda algunas otras letras del alfabeto. 318 00:12:54,020 --> 00:12:56,380 Así que tal vez esto es un poco más uniforme, suponiendo 319 00:12:56,380 --> 00:12:58,640 una distribución uniforme de los bebés a través de un mes. 320 00:12:58,640 --> 00:12:59,990 >> Pero, por supuesto, esto es todavía imperfecto. 321 00:12:59,990 --> 00:13:00,370 Derecha? 322 00:13:00,370 --> 00:13:01,370 Vamos a tener colisiones. 323 00:13:01,370 --> 00:13:04,680 Varias personas en este estructura de datos son todavía 324 00:13:04,680 --> 00:13:08,432 que tiene la misma fecha de nacimiento, al menos, eres independientemente de mes. 325 00:13:08,432 --> 00:13:09,640 Pero lo que ha hecho el autor? 326 00:13:09,640 --> 00:13:13,427 Bueno, parece que tenemos una matriz en el lado izquierdo dibujado verticalmente, 327 00:13:13,427 --> 00:13:15,010 pero eso es sólo una representación artística. 328 00:13:15,010 --> 00:13:18,009 No importa qué dirección dibujar una matriz, que sigue siendo una matriz. 329 00:13:18,009 --> 00:13:20,225 ¿Qué es este un arreglo de parecer? 330 00:13:20,225 --> 00:13:21,500 >> AUDIENCIA: lista Vinculado. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Sí. 332 00:13:21,650 --> 00:13:23,490 Parece que se trata de una gama de lista enlazada. 333 00:13:23,490 --> 00:13:26,490 Así que de nuevo, a este punto de la clase de la utilización de estas estructuras de datos ahora 334 00:13:26,490 --> 00:13:28,550 como ingredientes a más soluciones interesantes, 335 00:13:28,550 --> 00:13:30,862 usted puede tomar absolutamente un fundamental, como una matriz, 336 00:13:30,862 --> 00:13:33,320 y luego tomar algo más interesante como una lista enlazada 337 00:13:33,320 --> 00:13:36,660 e incluso combinar en una aún más interesante estructura de datos. 338 00:13:36,660 --> 00:13:39,630 Y, de hecho, esto también haría ser llamado una tabla hash, 339 00:13:39,630 --> 00:13:42,610 por lo que la matriz es realmente la tabla hash, 340 00:13:42,610 --> 00:13:45,600 pero que la tabla hash tiene cadenas, por así decirlo, 341 00:13:45,600 --> 00:13:50,220 que puede crecer o disminuir en base a la número de elementos que desea insertar. 342 00:13:50,220 --> 00:13:52,990 >> Ahora, en consecuencia, lo que hay el tiempo de ejecución ahora? 343 00:13:52,990 --> 00:13:58,030 Si quiero insertar alguien cuyo cumpleaños es el 31 de octubre 344 00:13:58,030 --> 00:13:59,040 ¿de dónde viene él o ella? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Bien. 347 00:14:01,030 --> 00:14:02,819 En la parte inferior, donde dice 31. 348 00:14:02,819 --> 00:14:03,610 Y eso es perfecto. 349 00:14:03,610 --> 00:14:05,060 Esa fue la constante de tiempo. 350 00:14:05,060 --> 00:14:08,760 Pero, ¿y si nos encontramos con alguien más cuyo cumpleaños es, vamos a ver, 351 00:14:08,760 --> 00:14:10,950 Octubre, Noviembre, 31 de Diciembre? 352 00:14:10,950 --> 00:14:12,790 ¿Dónde está él o ella va a ir? 353 00:14:12,790 --> 00:14:13,290 La misma cosa. 354 00:14:13,290 --> 00:14:13,970 Dos paso sin embargo. 355 00:14:13,970 --> 00:14:15,303 Eso es constante, aunque no es así? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Bien. 358 00:14:16,860 --> 00:14:17,840 En el momento que es. 359 00:14:17,840 --> 00:14:20,570 Pero en el caso general, más la gente que añadimos, 360 00:14:20,570 --> 00:14:23,790 probabilísticamente, vamos para conseguir más y más colisiones. 361 00:14:23,790 --> 00:14:26,820 >> Ahora bien, esto es un poco mejor porque técnicamente 362 00:14:26,820 --> 00:14:34,580 ahora mis cadenas podrían estar en el peor de los casos ¿hasta cuándo? 363 00:14:34,580 --> 00:14:38,890 Si introduzco n personas en este más estructura de datos sofisticado, n personas, 364 00:14:38,890 --> 00:14:41,080 en el peor de los casos va a ser n. 365 00:14:41,080 --> 00:14:41,815 ¿Por qué? 366 00:14:41,815 --> 00:14:43,332 >> AUDIENCIA: Porque si todo el mundo tiene el mismo cumpleaños, 367 00:14:43,332 --> 00:14:44,545 que van a ser una línea. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Perfecto. 369 00:14:45,420 --> 00:14:47,480 Puede ser que sea un poco artificiosa, pero realmente en el peor de los casos, 370 00:14:47,480 --> 00:14:50,117 si todo el mundo tiene el mismo cumpleaños, teniendo en cuenta las entradas que tiene, 371 00:14:50,117 --> 00:14:51,950 usted va a tener un cadena masivamente largo. 372 00:14:51,950 --> 00:14:54,241 Y así, se podría llamar un la tabla de hash, pero en realidad es 373 00:14:54,241 --> 00:14:56,810 sólo una lista masiva vinculada con una gran cantidad de espacio desperdiciado. 374 00:14:56,810 --> 00:15:00,460 Pero en general, si suponemos que al menos los cumpleaños son uniform-- 375 00:15:00,460 --> 00:15:01,750 y probablemente no lo es. 376 00:15:01,750 --> 00:15:02,587 Estoy haciendo eso. 377 00:15:02,587 --> 00:15:04,420 Pero si asumimos, para aras de la discusión 378 00:15:04,420 --> 00:15:07,717 que son, a continuación, en teoría, si Esta es la representación vertical, 379 00:15:07,717 --> 00:15:11,050 de la matriz, bueno, entonces espero que estés va a poner las cadenas que son, ya sabes, 380 00:15:11,050 --> 00:15:15,880 más o menos la misma longitud que cada uno de éstos representa un día del mes. 381 00:15:15,880 --> 00:15:19,930 >> Ahora bien, si hay 31 días en el mes, eso significa que mi tiempo de funcionamiento realmente 382 00:15:19,930 --> 00:15:25,230 es gran O de n más de 31, que se siente mejor que lineal. 383 00:15:25,230 --> 00:15:27,950 Pero lo que era uno de los nuestros compromisos de un par de semanas 384 00:15:27,950 --> 00:15:31,145 hace cada vez que se trataba de expresar el tiempo de ejecución de un algoritmo? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Así que busque sólo en el término de orden superior. 387 00:15:35,190 --> 00:15:35,690 Derecha? 388 00:15:35,690 --> 00:15:37,400 31 es definitivamente útil. 389 00:15:37,400 --> 00:15:39,610 Pero esto sigue siendo gran O de n. 390 00:15:39,610 --> 00:15:41,730 Pero uno de los temas del problema establece cinco 391 00:15:41,730 --> 00:15:43,950 va a ser de reconocer que absolutamente, 392 00:15:43,950 --> 00:15:47,320 asintóticamente, teóricamente esta estructura de datos 393 00:15:47,320 --> 00:15:50,470 no es mejor que sólo una enorme lista enlazada. 394 00:15:50,470 --> 00:15:53,550 Y, en efecto, en el peor de los casos, este tabla hash podría recaer en eso. 395 00:15:53,550 --> 00:15:57,620 >> Pero en el mundo real, con nosotros los seres humanos que los propios Macs o PCs o lo que sea 396 00:15:57,620 --> 00:16:01,240 y se están ejecutando mundo real software en los datos del mundo real, 397 00:16:01,240 --> 00:16:03,260 qué algoritmo se va a preferir? 398 00:16:03,260 --> 00:16:09,180 El que toma las medidas finales o la uno que toma n dividido por 31 pasos 399 00:16:09,180 --> 00:16:12,900 encontrar algún dato o para buscar un poco de información? 400 00:16:12,900 --> 00:16:16,580 Quiero decir, absolutamente las 31 marcas una diferencia en el mundo real. 401 00:16:16,580 --> 00:16:18,540 Es 31 veces más rápido. 402 00:16:18,540 --> 00:16:20,880 Y nosotros, los humanos son sin duda va a apreciar eso. 403 00:16:20,880 --> 00:16:23,004 >> Así que darse cuenta de la dicotomía allí entre realidad 404 00:16:23,004 --> 00:16:25,920 hablando de cosas teóricamente y asintóticamente que definitivamente 405 00:16:25,920 --> 00:16:28,760 tiene valor como hemos visto, pero en el mundo real, 406 00:16:28,760 --> 00:16:32,930 si usted se preocupa sólo hacer la feliz humano para las entradas generales, 407 00:16:32,930 --> 00:16:36,010 usted puede muy bien querer aceptar el hecho de que, sí, esta es lineal, 408 00:16:36,010 --> 00:16:38,360 pero es 31 veces más rápido que puede ser lineal. 409 00:16:38,360 --> 00:16:41,610 Y mejor aún, nosotros no sólo tenemos que hacer algo arbitrario como una fecha de nacimiento, 410 00:16:41,610 --> 00:16:44,030 podríamos pasar un poco más tiempo y la inteligencia 411 00:16:44,030 --> 00:16:47,140 y pensar en lo que podríamos hacer, dado el nombre de una persona y tal vez 412 00:16:47,140 --> 00:16:50,130 su fecha de nacimiento para combinar los ingredientes para averiguar algo 413 00:16:50,130 --> 00:16:52,720 que es verdaderamente más uniforme y menos jaggy, 414 00:16:52,720 --> 00:16:56,250 por decirlo de esta imagen Actualmente sugiere que podría ser. 415 00:16:56,250 --> 00:16:57,750 ¿Cómo podríamos aplicar esto en código? 416 00:16:57,750 --> 00:17:00,280 Bueno, déjame propongo que simplemente pedir prestado algo de sintaxis que hemos 417 00:17:00,280 --> 00:17:01,799 utilizado un par de veces hasta ahora. 418 00:17:01,799 --> 00:17:03,590 Y yo voy a definir un nodo, que de nuevo 419 00:17:03,590 --> 00:17:06,812 es un término genérico para sólo algunas recipiente para algún tipo de estructura de datos. 420 00:17:06,812 --> 00:17:09,020 Voy a proponer que una cadena va allí. 421 00:17:09,020 --> 00:17:11,369 Pero vamos a empezar a tomar las ruedas de entrenamiento de hoy. 422 00:17:11,369 --> 00:17:13,230 >> No más biblioteca CS50 realmente, a menos que quiera 423 00:17:13,230 --> 00:17:15,230 para utilizarlo para su definitiva proyecto, que está bien, 424 00:17:15,230 --> 00:17:18,569 pero ahora vamos a tirar de la cortina y dicen que es sólo una estrella de carbón. 425 00:17:18,569 --> 00:17:22,069 Así que la palabra no va a ser nombre de la persona en cuestión. 426 00:17:22,069 --> 00:17:25,079 Y ahora tengo un vínculo aquí para el siguiente nodo 427 00:17:25,079 --> 00:17:28,170 de modo que éstos representan cada uno de los nodos 428 00:17:28,170 --> 00:17:30,950 en la cadena, potencialmente, de una lista enlazada. 429 00:17:30,950 --> 00:17:34,090 >> Y ahora qué hago Declaro la tabla hash en sí? 430 00:17:34,090 --> 00:17:36,660 ¿Cómo declaro toda esta estructura? 431 00:17:36,660 --> 00:17:40,960 Bueno, en realidad, al igual que yo usé un puntero a sólo el primer elemento de una lista 432 00:17:40,960 --> 00:17:44,510 antes, de manera similar puedo decir simplemente Sólo necesito un montón de punteros 433 00:17:44,510 --> 00:17:46,270 para implementar esta tabla hash entero. 434 00:17:46,270 --> 00:17:49,484 Voy a tener una matriz llamada tabla para la tabla hash. 435 00:17:49,484 --> 00:17:50,900 Va a tener la capacidad de tamaño. 436 00:17:50,900 --> 00:17:52,525 Esa es la cantidad de elementos puede caber en ella. 437 00:17:52,525 --> 00:17:56,180 Y cada uno de esos elementos en este matriz va a ser una estrella de nodo. 438 00:17:56,180 --> 00:17:56,810 ¿Por qué? 439 00:17:56,810 --> 00:18:00,160 Bueno, por esta imagen, de lo que soy la aplicación de la tabla hash como 440 00:18:00,160 --> 00:18:04,330 eficazmente en el principio es sólo esta matriz que hemos dibujado verticalmente, 441 00:18:04,330 --> 00:18:06,820 cada uno de cuyos cuadrados representa un puntero. 442 00:18:06,820 --> 00:18:09,170 Que los que tienen barras a través de ellos son simplemente nulo. 443 00:18:09,170 --> 00:18:11,410 Y los que tienen flechas que van hacia la derecha 444 00:18:11,410 --> 00:18:16,140 son punteros a nodos reales reales, ergo el comienzo de una lista enlazada. 445 00:18:16,140 --> 00:18:19,050 >> Así que aquí, entonces, es cómo podemos implementar una tabla hash que 446 00:18:19,050 --> 00:18:21,580 implementa encadenamiento separado. 447 00:18:21,580 --> 00:18:22,840 Ahora podemos hacer mejor? 448 00:18:22,840 --> 00:18:25,632 Muy bien me prometió la última vez que podríamos alcanzar constante de tiempo. 449 00:18:25,632 --> 00:18:27,381 Y Yo como que te di constante de tiempo aquí, 450 00:18:27,381 --> 00:18:29,850 pero entonces no dicho realmente constante de tiempo porque todavía 451 00:18:29,850 --> 00:18:31,890 dependiente sobre el total número de elementos 452 00:18:31,890 --> 00:18:34,500 que está introduciendo en la estructura de datos. 453 00:18:34,500 --> 00:18:35,980 Pero supongamos que hicimos esto. 454 00:18:35,980 --> 00:18:39,550 Permítanme volver a la pantalla por aquí. 455 00:18:39,550 --> 00:18:44,520 Permítanme también este proyecto aquí, claro la pantalla, y supongamos que hice esto. 456 00:18:44,520 --> 00:18:49,300 Supongamos que yo quería para insertar el nombre Daven en en mi estructura de datos. 457 00:18:49,300 --> 00:18:52,100 >> Así que quiero insertar una cadena Daven en la estructura de datos. 458 00:18:52,100 --> 00:18:54,370 ¿Qué pasa si yo no uso un la tabla de hash, pero yo uso 459 00:18:54,370 --> 00:18:56,980 algo que es más árbol-como como un árbol de la familia, donde 460 00:18:56,980 --> 00:18:59,670 usted tiene alguna raíz en el superior y luego nodos y hojas 461 00:18:59,670 --> 00:19:01,440 que van hacia abajo y hacia afuera. 462 00:19:01,440 --> 00:19:04,450 Supongamos entonces, que yo que desee insertar Daven de 463 00:19:04,450 --> 00:19:06,430 en lo que es actualmente una lista vacía. 464 00:19:06,430 --> 00:19:09,780 Yo voy a hacer lo siguiente: yo soy va a crear un nodo en esta familia 465 00:19:09,780 --> 00:19:15,170 estructura de datos como árbol que se parece un poco como esta, cada uno de los cuales 466 00:19:15,170 --> 00:19:19,640 rectángulos ha, digamos, por el momento 26 elementos en los mismos. 467 00:19:19,640 --> 00:19:21,650 Y cada una de las células en esta matriz que está pasando 468 00:19:21,650 --> 00:19:23,470 para representar la letra de un alfabeto. 469 00:19:23,470 --> 00:19:28,190 >> En concreto, voy a tratar este es A, luego B, luego C, luego D, 470 00:19:28,190 --> 00:19:29,310 este de aquí. 471 00:19:29,310 --> 00:19:32,940 Así que esto va a con eficacia representar la letra D. 472 00:19:32,940 --> 00:19:36,040 Pero para insertar todos Daven de nombro tengo que hacer un poco más. 473 00:19:36,040 --> 00:19:37,840 Así que estoy en primer lugar va a hachís, por así decirlo. 474 00:19:37,840 --> 00:19:41,049 Voy a mirar a la primera letra en Daven de que es, obviamente, un D, 475 00:19:41,049 --> 00:19:42,840 y yo voy a asignar un nodo que mira 476 00:19:42,840 --> 00:19:45,570 así- un gran rectángulo grande suficiente para adaptarse a todo el alfabeto. 477 00:19:45,570 --> 00:19:47,140 >> Ahora D se realiza. 478 00:19:47,140 --> 00:19:49,720 Ahora A. D-A-V-E-N es la meta. 479 00:19:49,720 --> 00:19:51,220 Así que ahora lo que voy a hacer es esto. 480 00:19:51,220 --> 00:19:54,027 Tan pronto como empecé aviso D no hay puntero allí. 481 00:19:54,027 --> 00:19:56,860 Es valores de basura en el momento, o podría inicializarlo a null. 482 00:19:56,860 --> 00:19:59,630 Pero déjame seguir adelante con esta idea de construir un árbol. 483 00:19:59,630 --> 00:20:04,260 Permítanme asigno otro de estos nodos que cuenta con 26 elementos en los mismos. 484 00:20:04,260 --> 00:20:05,150 >> ¿Y sabes qué? 485 00:20:05,150 --> 00:20:09,130 Si esto es sólo un nodo en la memoria que He creado con malloc, utilizando una estructura 486 00:20:09,130 --> 00:20:11,240 como pronto veremos, Yo voy a hacer esto-- 487 00:20:11,240 --> 00:20:14,450 Voy a dibujar una flecha de lo que representó D abajo 488 00:20:14,450 --> 00:20:15,860 a este nuevo nodo. 489 00:20:15,860 --> 00:20:19,240 Y ahora, primero la siguiente carta en nombre de Daven, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- voy a seguir adelante y dibujar otro nodo de este tipo, 491 00:20:24,150 --> 00:20:30,150 mediante el cual, los elementos de V, que aquí vamos a sortear gritos instance--. 492 00:20:30,150 --> 00:20:31,020 No vamos a dibujar allí. 493 00:20:31,020 --> 00:20:31,936 Se va a ir aquí. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> A continuación, vamos a considera que se trata de V. 496 00:20:35,712 --> 00:20:44,920 Y entonces aquí vamos a índice por debajo de V en lo que vamos a considerar E. 497 00:20:44,920 --> 00:20:50,100 Y a continuación, a partir de aquí vamos a ir tener uno de estos nodos aquí. 498 00:20:50,100 --> 00:20:52,930 Y ahora tenemos una pregunta para contestar. 499 00:20:52,930 --> 00:20:57,840 Necesito alguna manera indicar que estamos en el final de la cadena Daven. 500 00:20:57,840 --> 00:20:59,490 Así que podría dejarlo nulo. 501 00:20:59,490 --> 00:21:02,670 >> Pero lo que si tenemos Daven de nombre completo también, que 502 00:21:02,670 --> 00:21:04,280 es, como hemos dicho, Davenport? 503 00:21:04,280 --> 00:21:06,970 ¿Y qué si es Daven en realidad una subcadena, 504 00:21:06,970 --> 00:21:08,960 un prefijo de una cadena mucho más tiempo? 505 00:21:08,960 --> 00:21:11,450 No podemos permanentemente decir nada va 506 00:21:11,450 --> 00:21:14,410 ir allí, porque podíamos Nunca inserte una palabra como Davenport 507 00:21:14,410 --> 00:21:15,840 en esta estructura de datos 508 00:21:15,840 --> 00:21:19,560 >> Entonces, ¿qué podríamos hacer en su lugar es tratar cada uno de estos elementos 509 00:21:19,560 --> 00:21:22,170 como tal vez tener dos elementos dentro de ellos. 510 00:21:22,170 --> 00:21:24,810 Uno de ellos es un puntero, de hecho, como que he estado haciendo. 511 00:21:24,810 --> 00:21:27,100 Así que cada una de estas cajas No es sólo una célula. 512 00:21:27,100 --> 00:21:29,855 Pero ¿y si la parte superior uno-- de la parte inferior 513 00:21:29,855 --> 00:21:32,230 va a ser nulo, porque no hay Davenport por el momento. 514 00:21:32,230 --> 00:21:34,197 ¿Qué pasa si el de arriba es algún valor especial? 515 00:21:34,197 --> 00:21:36,530 Y va a ser un poco difícil de dibujar este tamaño. 516 00:21:36,530 --> 00:21:38,130 Pero supongo que es sólo una marca de verificación. 517 00:21:38,130 --> 00:21:38,920 Compruebe. 518 00:21:38,920 --> 00:21:44,230 D-A-E-V-N es una cadena en esta estructura de datos. 519 00:21:44,230 --> 00:21:48,350 >> Mientras tanto, si tuviera más espacio aquí, lo que podía hacer P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 y yo podría poner cheque en el nodo que tiene la letra T al final. 521 00:21:52,650 --> 00:21:55,460 Así que esta es una forma masiva complejo de aspecto de estructura de datos. 522 00:21:55,460 --> 00:21:57,210 Y mi puño y letra ciertamente no ayuda. 523 00:21:57,210 --> 00:22:00,043 Pero si quería insertar algo más, consideramos lo que haríamos. 524 00:22:00,043 --> 00:22:03,370 Si quisiéramos poner en David, nos gustaría seguir la misma lógica, D-A-V, 525 00:22:03,370 --> 00:22:08,802 pero ahora me gustaría señalar en la próxima elemento no desde E, pero de I a D. 526 00:22:08,802 --> 00:22:10,760 Así que va a ser más nodos de este árbol. 527 00:22:10,760 --> 00:22:12,325 Vamos a tener la llamada malloc más. 528 00:22:12,325 --> 00:22:14,700 Pero yo no quiero hacer una completo desastre de esta imagen. 529 00:22:14,700 --> 00:22:17,710 Así que vamos a ver un lugar que ha sido pre-formulado 530 00:22:17,710 --> 00:22:21,810 como este con no punto, punto, puntos, pero sólo arrays abreviada. 531 00:22:21,810 --> 00:22:23,950 Pero cada uno de los nodos en este árbol aquí 532 00:22:23,950 --> 00:22:26,700 representa la misma cosa-- una matriz Rayo de tamaño 26. 533 00:22:26,700 --> 00:22:28,860 >> O si queremos ser ahora realmente adecuada, lo que 534 00:22:28,860 --> 00:22:30,790 si el nombre de alguien como un apóstrofe, vamos a 535 00:22:30,790 --> 00:22:35,560 asumir que cada nodo tiene en realidad como 27 índices en ella, no sólo 26. 536 00:22:35,560 --> 00:22:42,020 Así que esto ahora va a ser un dato estructura llamada trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 Un trie, que es supuestamente históricamente un nombre inteligente para un árbol 538 00:22:46,120 --> 00:22:49,040 que se optimiza para recuperación, que por supuesto, 539 00:22:49,040 --> 00:22:50,870 se escribe con un I-E por lo que es trie. 540 00:22:50,870 --> 00:22:52,710 Pero esa es la historia de la trie. 541 00:22:52,710 --> 00:22:55,860 >> Así que un trie es estos datos en forma de árbol estructura como un árbol genealógico 542 00:22:55,860 --> 00:22:57,510 que en última instancia se comporta de esa manera. 543 00:22:57,510 --> 00:23:00,890 Y aquí es sólo otro ejemplo de un toda montón de nombres de otras personas. 544 00:23:00,890 --> 00:23:03,540 Pero la pregunta ahora a la mano es lo que tiene 545 00:23:03,540 --> 00:23:08,070 hemos ganado introduciendo posiblemente una más complicada estructura de datos, y uno, 546 00:23:08,070 --> 00:23:09,870 francamente, que utiliza una gran cantidad de memoria. 547 00:23:09,870 --> 00:23:11,703 >> Porque a pesar de que, en este momento, estoy solo 548 00:23:11,703 --> 00:23:15,050 usando D's puntero y A y V y Es y Ns, 549 00:23:15,050 --> 00:23:16,700 Me estoy perdiendo una diablos de gran cantidad de memoria. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Pero donde paso un recurso, Tiendo a no recuperar otro. 552 00:23:22,660 --> 00:23:26,020 Así que si estoy gastando más espacio, lo que es probablemente la esperanza? 553 00:23:26,020 --> 00:23:27,407 Que estoy gastando menos qué? 554 00:23:27,407 --> 00:23:28,240 AUDIENCIA: Menos tiempo. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Tiempo. 556 00:23:28,990 --> 00:23:30,320 Ahora ¿por qué podría ser? 557 00:23:30,320 --> 00:23:33,880 Bueno, ¿cuál es la inserción tiempo, en términos de gran O ahora, 558 00:23:33,880 --> 00:23:37,660 de un nombre como Daven o Davenport o David? 559 00:23:37,660 --> 00:23:39,340 Bueno, Daven era cinco pasos. 560 00:23:39,340 --> 00:23:42,350 Davenport sería nueve pasos, por lo que sería un poco más pasos. 561 00:23:42,350 --> 00:23:44,250 David sería cinco pasos también. 562 00:23:44,250 --> 00:23:47,230 Así que estos son de hormigón números, pero seguro que hay 563 00:23:47,230 --> 00:23:49,550 un límite superior en el longitud del nombre de alguien. 564 00:23:49,550 --> 00:23:52,240 Y, en efecto, en el problema grupos de cinco especificación, 565 00:23:52,240 --> 00:23:54,050 vamos a proponer que es algo 566 00:23:54,050 --> 00:23:55,470 eso es 40 caracteres y tantos. 567 00:23:55,470 --> 00:23:58,180 >> Siendo realistas, nadie tiene un nombre infinitamente largo, 568 00:23:58,180 --> 00:24:01,542 que es decir que la longitud de una nombre o la longitud de una cadena que pueden 569 00:24:01,542 --> 00:24:03,750 tener cierta el estado de estructura es discutible qué? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Es constante. 572 00:24:06,250 --> 00:24:06,430 Derecha? 573 00:24:06,430 --> 00:24:09,310 Puede ser que sea una gran constante como 40 y tantos años, pero es constante. 574 00:24:09,310 --> 00:24:13,752 Y no tiene dependencia de la cantidad de otros nombres pertenecen a esta estructura de datos. 575 00:24:13,752 --> 00:24:15,460 En otras palabras, si querido insertar ahora 576 00:24:15,460 --> 00:24:20,540 Colton o Gabriel o Rob o Zamyla o Alison o Belinda o cualquier otro nombre 577 00:24:20,540 --> 00:24:23,940 desde el personal en estos datos estructura, es el tiempo de ejecución 578 00:24:23,940 --> 00:24:26,750 de insertar otros nombres va a ser en absoluto afectado 579 00:24:26,750 --> 00:24:30,220 por la forma en muchos otros elementos son en la estructura de datos ya? 580 00:24:30,220 --> 00:24:31,040 Que no es. 581 00:24:31,040 --> 00:24:31,540 Derecha? 582 00:24:31,540 --> 00:24:36,150 Debido a que estamos usando de manera efectiva esta tabla hash multi-capa. 583 00:24:36,150 --> 00:24:38,280 Y el tiempo de ejecución de cualquiera de estas operaciones 584 00:24:38,280 --> 00:24:41,510 depende no del número de elementos que están en la estructura de datos 585 00:24:41,510 --> 00:24:43,090 o que se va con el tiempo para estar en la estructura de datos, 586 00:24:43,090 --> 00:24:44,714 pero en la longitud de lo que específicamente? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> La cadena ser insertado, lo que lo hace hacer 589 00:24:49,200 --> 00:24:52,580 este asintóticamente constante gran O tiempo-- de uno. 590 00:24:52,580 --> 00:24:54,720 Y, francamente, sólo en el mundo real, este 591 00:24:54,720 --> 00:24:58,380 significa insertar el nombre de Daven toma como cinco pasos, o Davenport nueve 592 00:24:58,380 --> 00:25:00,100 David pasos, o cinco pasos. 593 00:25:00,100 --> 00:25:03,071 Eso es bastante maldito pequeños tiempos de funcionamiento. 594 00:25:03,071 --> 00:25:05,320 Y, de hecho, esa es una muy buena cosa, especialmente cuando 595 00:25:05,320 --> 00:25:08,126 no es dependiente sobre el total número de elementos de allí. 596 00:25:08,126 --> 00:25:10,500 Entonces, ¿cómo podríamos aplicar esta tipo de estructura en el código? 597 00:25:10,500 --> 00:25:12,900 Es un poco más complejo, pero aún así es 598 00:25:12,900 --> 00:25:15,050 sólo una aplicación de bloques de construcción básicos. 599 00:25:15,050 --> 00:25:17,830 Voy a redefinir nos nodo como sigue: 600 00:25:17,830 --> 00:25:21,100 bool llamada palabra-- y esto que podría llamarse cualquier cosa. 601 00:25:21,100 --> 00:25:23,970 Pero el bool representa lo dibujé como una marca de verificación. 602 00:25:23,970 --> 00:25:24,490 Sí. 603 00:25:24,490 --> 00:25:26,720 Este es el final de una cadena en esta estructura de datos. 604 00:25:26,720 --> 00:25:30,702 >> Y, por supuesto, la estrella nodo no se está refiriendo a los niños. 605 00:25:30,702 --> 00:25:32,410 Y, de hecho, al igual que un árbol de la familia, usted 606 00:25:32,410 --> 00:25:34,370 consideraría los nodos que están colgando de 607 00:25:34,370 --> 00:25:36,920 de la parte inferior de algunos de los padres elemento para ser niños. 608 00:25:36,920 --> 00:25:40,510 Y para que los niños se van a ser una matriz de 27, el 27 de 609 00:25:40,510 --> 00:25:41,680 sólo estar para apóstrofe. 610 00:25:41,680 --> 00:25:43,390 Vamos a clasificar de caso especial que. 611 00:25:43,390 --> 00:25:45,400 Así que usted puede tener cierta nombres con apóstrofes. 612 00:25:45,400 --> 00:25:47,399 Tal vez incluso debería guión ir allí, pero usted 613 00:25:47,399 --> 00:25:50,330 ver en pág conjunto 5 que sólo la atención sobre las letras y apóstrofes. 614 00:25:50,330 --> 00:25:52,990 >> Y entonces, ¿cómo hace usted representa la propia estructura de datos? 615 00:25:52,990 --> 00:25:56,454 ¿Cómo se representa a la raíz de este trie, por así decirlo? 616 00:25:56,454 --> 00:25:59,620 Bueno, al igual que con una lista enlazada, que necesitará un puntero al primer elemento. 617 00:25:59,620 --> 00:26:04,270 Con un trie sólo tiene uno puntero a la raíz de este trie. 618 00:26:04,270 --> 00:26:07,290 Y a partir de allí se puede hash de su camino hacia abajo más y más profundo 619 00:26:07,290 --> 00:26:10,460 a todos los demás nodos en la estructura. 620 00:26:10,460 --> 00:26:13,440 Así que simplemente con esta lata representamos que estructura. 621 00:26:13,440 --> 00:26:15,877 >> Ahora Meanwhile-- Oh, pregunta. 622 00:26:15,877 --> 00:26:17,220 >> AUDIENCIA: ¿Cuál es la palabra bool? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: palabra Bool es sólo esta encarnación C 624 00:26:20,490 --> 00:26:22,920 de lo que he descrito en este cuadro de aquí, cuando 625 00:26:22,920 --> 00:26:26,000 Empecé a dividir cada uno de los elementos del array en dos piezas. 626 00:26:26,000 --> 00:26:27,600 Uno es un puntero al siguiente nodo. 627 00:26:27,600 --> 00:26:30,280 La otra tiene que haber algo así como una casilla de verificación 628 00:26:30,280 --> 00:26:33,770 a decir que sí, que hay una Daven palabra que termina aquí, 629 00:26:33,770 --> 00:26:35,610 porque no queremos, por el momento, Dave. 630 00:26:35,610 --> 00:26:39,320 >> A pesar de que a Dave va a ser una palabra legítima, que no está en el trie 631 00:26:39,320 --> 00:26:39,830 todavía. 632 00:26:39,830 --> 00:26:40,950 Y D no es una palabra. 633 00:26:40,950 --> 00:26:42,770 Y D-A no es una palabra o un nombre. 634 00:26:42,770 --> 00:26:45,020 Así que la marca de verificación indica sólo una vez que 635 00:26:45,020 --> 00:26:48,190 golpeó este nodo es el trayectoria anterior de caracteres 636 00:26:48,190 --> 00:26:50,700 en realidad una cadena que ha insertado. 637 00:26:50,700 --> 00:26:53,660 Así que eso es todo el bool no está haciendo por nosotros. 638 00:26:53,660 --> 00:26:55,500 >> ¿Alguna otra pregunta sobre intentos? 639 00:26:55,500 --> 00:26:56,215 Sí. 640 00:26:56,215 --> 00:26:58,035 >> AUDIENCIA: ¿Cuál es la coincidencia? 641 00:26:58,035 --> 00:26:59,945 ¿Qué pasa si usted tiene un Dave y un Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Perfecto. 643 00:27:00,820 --> 00:27:02,580 ¿Qué pasa si usted tiene un Dave y un Daven? 644 00:27:02,580 --> 00:27:06,240 Así que si insertamos, decir un apodo, para David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Esto es realmente muy simple. 647 00:27:08,700 --> 00:27:10,325 Así que sólo vamos a tener cuatro pasos. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Y ¿qué es lo que tengo que hacer una vez que llegué a cuarto nodo? 650 00:27:15,847 --> 00:27:16,680 Sólo va a comprobar. 651 00:27:16,680 --> 00:27:18,000 Ya está bueno para ir. 652 00:27:18,000 --> 00:27:18,840 Hecho. 653 00:27:18,840 --> 00:27:19,750 Cuatro pasos. 654 00:27:19,750 --> 00:27:21,590 Tiempo constante asintótica. 655 00:27:21,590 --> 00:27:26,300 Y ahora hemos indicado que tanto de Dave y Daven son cadenas en la estructura. 656 00:27:26,300 --> 00:27:27,710 Así que no es un problema. 657 00:27:27,710 --> 00:27:30,200 Y note cómo la presencia de Daven no hacerlo 658 00:27:30,200 --> 00:27:34,750 tomar cualquier tiempo más o menos tiempo para Dave y viceversa. 659 00:27:34,750 --> 00:27:36,000 >> Entonces, ¿qué otra cosa podemos hacer ahora? 660 00:27:36,000 --> 00:27:40,680 Hemos utilizado esta metáfora antes de bandejas que representa algo. 661 00:27:40,680 --> 00:27:43,380 Pero resulta que un pila de bandejas es en realidad 662 00:27:43,380 --> 00:27:47,187 demostrativo de otro abstracto de datos type-- una estructura de datos de nivel superior 663 00:27:47,187 --> 00:27:49,770 que al final del día es sólo como una matriz o una lista enlazada 664 00:27:49,770 --> 00:27:50,970 o algo más mundano. 665 00:27:50,970 --> 00:27:53,270 Pero es una más interesante concepto conceptual. 666 00:27:53,270 --> 00:27:56,440 Una pila, como estos bandejas aquí en Mather, 667 00:27:56,440 --> 00:27:58,750 generalmente se llaman sólo que-- una pila. 668 00:27:58,750 --> 00:28:02,540 >> Y en este tipo de estructura de datos usted tiene dos operations-- 669 00:28:02,540 --> 00:28:05,880 usted tiene una llamada empuje para añadiendo algo a la pila, 670 00:28:05,880 --> 00:28:08,320 como poner otra bandeja la parte posterior en la parte superior de la pila. 671 00:28:08,320 --> 00:28:11,350 Y a continuación, el pop, el que significa tomar la más alta fuera de la bandeja. 672 00:28:11,350 --> 00:28:16,210 Pero lo que es clave sobre una pila es que que tiene esta característica curiosa. 673 00:28:16,210 --> 00:28:19,560 A medida que el personal del comedor son la reordenación de las bandejas para la próxima comida, 674 00:28:19,560 --> 00:28:21,380 lo que va a ser cierto acerca de cómo los estudiantes 675 00:28:21,380 --> 00:28:22,856 interactuar con esta estructura de datos? 676 00:28:22,856 --> 00:28:24,480 AUDIENCIA: Van a estallar uno fuera. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: Van a pop uno fuera, esperemos que la parte superior. 678 00:28:26,550 --> 00:28:28,910 De lo contrario, es sólo un poco estúpido que ir todo el camino hasta el fondo. 679 00:28:28,910 --> 00:28:29,070 Derecha? 680 00:28:29,070 --> 00:28:31,620 La estructura de datos en realidad no permite a agarrar la bandeja inferior, al menos, 681 00:28:31,620 --> 00:28:32,520 fácilmente. 682 00:28:32,520 --> 00:28:35,040 Así que hay esta curiosa propiedad de una pila 683 00:28:35,040 --> 00:28:39,730 que el último elemento es va a ser el primero en salir. 684 00:28:39,730 --> 00:28:43,400 Y los informáticos llaman LIFO-- este último en entrar, primero en salir. 685 00:28:43,400 --> 00:28:45,540 Y lo que realmente tiene aplicaciones interesantes. 686 00:28:45,540 --> 00:28:50,090 No es necesariamente tan obvio como algunos otros, pero pueden, de hecho, ser útil, 687 00:28:50,090 --> 00:28:54,040 y puede, de hecho, ser implementada en un par de maneras diferentes. 688 00:28:54,040 --> 00:28:58,550 >> Así que uno, y de hecho, dejar que a mí, no a sumergirse en eso. 689 00:28:58,550 --> 00:28:59,860 Vamos a hacer esto en su lugar. 690 00:28:59,860 --> 00:29:03,700 Echemos un vistazo a uno que es casi la misma idea, pero es un poco más justo. 691 00:29:03,700 --> 00:29:04,200 Derecha? 692 00:29:04,200 --> 00:29:07,560 Si usted es uno de esos chicos ventilador o chicas que realmente le gusta los productos de Apple 693 00:29:07,560 --> 00:29:10,130 y se despertó a las 3:00 am a alinearse en algún almacén 694 00:29:10,130 --> 00:29:14,150 para obtener la más reciente iPhone, podría haber cola para arriba como esto. 695 00:29:14,150 --> 00:29:15,800 >> Ahora una cola es nombrado muy deliberadamente. 696 00:29:15,800 --> 00:29:18,190 Es una línea porque no hay algunos justos con él. 697 00:29:18,190 --> 00:29:18,690 Derecha? 698 00:29:18,690 --> 00:29:21,690 Sería tipo de aspirado si tienes llegó primero a la tienda de Apple 699 00:29:21,690 --> 00:29:25,700 pero usted es efectivamente la más inferior bandeja debido a que los empleados de Apple luego 700 00:29:25,700 --> 00:29:28,189 pop de la última persona que en realidad se puso en línea. 701 00:29:28,189 --> 00:29:31,230 Así pilas y colas, a pesar de funcionalmente son tipo de la same-- 702 00:29:31,230 --> 00:29:33,105 es sólo esta colección de los recursos que es 703 00:29:33,105 --> 00:29:36,210 va a crecer y shrink-- hay este aspecto ser justos con él, 704 00:29:36,210 --> 00:29:39,634 al menos en el mundo real, donde las operaciones que ejercen 705 00:29:39,634 --> 00:29:40,800 son fundamentalmente diferentes. 706 00:29:40,800 --> 00:29:43,360 A stack-- una cola rather-- se dice que tiene 707 00:29:43,360 --> 00:29:45,320 dos operaciones: n de colas y colas d. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 O usted puede llamar a ellos cualquier número de cosas. 710 00:29:48,090 --> 00:29:50,770 Pero lo que desea es capturar la noción de que uno es la adición de 711 00:29:50,770 --> 00:29:53,230 y uno está en última instancia restar. 712 00:29:53,230 --> 00:29:58,840 >> Ahora bajo el capó, tanto la pila y una cola podría ser implementado, ¿cómo? 713 00:29:58,840 --> 00:30:01,390 No vamos a entrar en el código de porque el nivel más alto 714 00:30:01,390 --> 00:30:03,387 es una especie de idea más obvia. 715 00:30:03,387 --> 00:30:04,470 Quiero decir, ¿qué hacen los seres humanos? 716 00:30:04,470 --> 00:30:07,030 Si yo soy la primera persona en el Apple Guardar y esta es la puerta de entrada, 717 00:30:07,030 --> 00:30:08,130 usted sabe, yo voy a estar aquí. 718 00:30:08,130 --> 00:30:09,750 Y de la siguiente persona va a estar aquí. 719 00:30:09,750 --> 00:30:11,500 Y de la siguiente persona va a estar aquí. 720 00:30:11,500 --> 00:30:13,792 Entonces, ¿qué estructura de datos se presta a una cola? 721 00:30:13,792 --> 00:30:14,542 >> AUDIENCIA: Una cola. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Bueno, una cola. 723 00:30:15,667 --> 00:30:16,390 Claro. 724 00:30:16,390 --> 00:30:16,920 Qué otra cosa? 725 00:30:16,920 --> 00:30:17,600 >> AUDIENCIA: Una lista enlazada. 726 00:30:17,600 --> 00:30:18,990 >> DAVID MALAN: Una vinculado lista que podría implementar. 727 00:30:18,990 --> 00:30:22,500 Y una lista enlazada es agradable porque entonces que puede crecer arbitrariamente larga en oposición 728 00:30:22,500 --> 00:30:24,880 a tener un número fijo de la gente en la tienda. 729 00:30:24,880 --> 00:30:27,030 Pero tal vez un número fijo de lugares es legítimo. 730 00:30:27,030 --> 00:30:30,350 Porque si sólo tienen como 20 iPhones en el primer día, tal vez 731 00:30:30,350 --> 00:30:33,930 que sólo necesitan una matriz de tamaño 20 para representar a esa cola, que 732 00:30:33,930 --> 00:30:37,070 es sólo para decir ahora, una vez que empezamos a hablar sobre estos problemas de más alto nivel, 733 00:30:37,070 --> 00:30:38,890 usted puede ponerlo en práctica en cualquier número de maneras. 734 00:30:38,890 --> 00:30:42,030 Y hay probablemente sólo va a ser una solución de compromiso en el espacio y el tiempo 735 00:30:42,030 --> 00:30:43,950 o simplemente en su propia complejidad del código. 736 00:30:43,950 --> 00:30:45,380 >> ¿Qué pasa con una pila? 737 00:30:45,380 --> 00:30:48,190 Bien, una pila, hemos visto también podría ser sólo estas bandejas. 738 00:30:48,190 --> 00:30:50,007 Y se podría implementar esta una matriz. 739 00:30:50,007 --> 00:30:53,090 Pero en algún momento si se utiliza una matriz, lo que va a pasar con las bandejas 740 00:30:53,090 --> 00:30:54,173 usted está tratando de poner en el suelo? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Bien. 743 00:30:55,670 --> 00:30:57,490 Usted sólo va a ser capaz de ir tan alto. 744 00:30:57,490 --> 00:31:00,156 Y creo que en Mather son realmente empotrada en esa abertura. 745 00:31:00,156 --> 00:31:01,950 Así que de hecho, es casi como Mather está utilizando 746 00:31:01,950 --> 00:31:03,783 una matriz de tamaño fijo, porque sólo se puede 747 00:31:03,783 --> 00:31:08,302 encajar tantas bandejas en que la apertura en la pared por debajo de las rodillas de la gente. 748 00:31:08,302 --> 00:31:10,010 Y lo que podría ser dice que es una matriz, 749 00:31:10,010 --> 00:31:14,300 pero sin duda podríamos poner en práctica que más en general con una lista enlazada. 750 00:31:14,300 --> 00:31:16,390 >> Bueno, ¿qué pasa con otra estructura de datos? 751 00:31:16,390 --> 00:31:18,760 Permítanme levanto otra visual aquí. 752 00:31:18,760 --> 00:31:24,710 Algo así como ¿qué tal este de aquí? 753 00:31:24,710 --> 00:31:28,920 ¿Por qué podría ser útil para no tener algo tan elegante como un trie, que 754 00:31:28,920 --> 00:31:32,370 vimos tenía estos muy amplios nodos, cada uno de los cuales está en una matriz? 755 00:31:32,370 --> 00:31:35,740 Pero ¿y si hacemos algo más simplemente, como un árbol de familia de la escuela vieja, 756 00:31:35,740 --> 00:31:38,110 cada uno de cuyos nodos aquí se acaba de almacenar un número. 757 00:31:38,110 --> 00:31:42,180 En lugar de un nombre o un descendiente se acaba de almacenar un número como este. 758 00:31:42,180 --> 00:31:45,250 >> Bueno, la jerga que utilizamos en estructuras de datos es ambos paí- 759 00:31:45,250 --> 00:31:49,510 y árboles, donde un trie, de nuevo, es sólo uno cuyos nodos son matrices, 760 00:31:49,510 --> 00:31:51,680 sigue siendo lo que te pueden utilizar desde la escuela primaria 761 00:31:51,680 --> 00:31:53,860 cuando hizo una familia hojas y la raíz tree-- 762 00:31:53,860 --> 00:31:57,250 del árbol y los niños de la los padres y hermanos de los mismos. 763 00:31:57,250 --> 00:32:03,670 Y podríamos poner en práctica un árbol, por ejemplo, como simplemente como esto. 764 00:32:03,670 --> 00:32:07,420 Un árbol, si como un nodo, una de estos círculos que tiene un número, 765 00:32:07,420 --> 00:32:09,947 no va a tener un puntero, sino dos. 766 00:32:09,947 --> 00:32:11,780 Y tan pronto como usted agrega un segundo puntero, 767 00:32:11,780 --> 00:32:13,905 en realidad puede ahora hacer una especie de los datos de dos dimensiones 768 00:32:13,905 --> 00:32:14,780 estructuras en la memoria. 769 00:32:14,780 --> 00:32:16,660 Al igual que una de dos dimensiones matriz, puede 770 00:32:16,660 --> 00:32:18,904 tener clase de dos dimensiones listas enlazadas, pero los 771 00:32:18,904 --> 00:32:20,820 que siguen un patrón donde no hay ciclos. 772 00:32:20,820 --> 00:32:24,487 Es realmente un árbol con una manera abuelo hasta aquí y luego 773 00:32:24,487 --> 00:32:27,320 algunos padres y los niños y nietos y bisnietos. 774 00:32:27,320 --> 00:32:28,370 y así sucesivamente. 775 00:32:28,370 --> 00:32:32,390 >> Pero lo que es realmente bueno de esto también, sólo para bromear con un poco de código, 776 00:32:32,390 --> 00:32:35,370 el recuerdo de la recursividad un tiempo atrás, por lo que 777 00:32:35,370 --> 00:32:38,220 se escribe una función que llama a sí mismo. 778 00:32:38,220 --> 00:32:41,140 Esta es una hermosa oportunidad implementar algo 779 00:32:41,140 --> 00:32:42,920 como la recursividad, porque consideran que este. 780 00:32:42,920 --> 00:32:43,860 >> Este es un árbol. 781 00:32:43,860 --> 00:32:48,040 Y yo he sido un poco anal con cómo Puse los números enteros en la calle. 782 00:32:48,040 --> 00:32:51,020 Tanto es así que tiene una especial nombre-- un árbol de búsqueda binaria. 783 00:32:51,020 --> 00:32:53,460 Ahora que hemos escuchado de binario buscar, pero puede usted 784 00:32:53,460 --> 00:32:55,180 trabajar hacia atrás desde el nombre de esta cosa? 785 00:32:55,180 --> 00:32:59,280 ¿Cuál es el patrón de la forma en que insertado los números enteros a este árbol? 786 00:32:59,280 --> 00:33:00,696 No es arbitrario. 787 00:33:00,696 --> 00:33:01,570 Hay algún patrón. 788 00:33:01,570 --> 00:33:02,090 Sí. 789 00:33:02,090 --> 00:33:03,370 >> AUDIENCIA: Los más pequeños de la izquierda. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Sí. 791 00:33:03,690 --> 00:33:05,062 Los más pequeños están a la izquierda. 792 00:33:05,062 --> 00:33:06,270 Otros más grandes están a la derecha. 793 00:33:06,270 --> 00:33:12,940 De tal manera que un enunciado verdadero es un padre es mayor que su hijo izquierdo, 794 00:33:12,940 --> 00:33:14,850 pero menor que su hijo derecho. 795 00:33:14,850 --> 00:33:17,750 Y eso solo es aún una definición verbal recursiva 796 00:33:17,750 --> 00:33:20,500 porque se puede aplicar ese misma lógica a cada nodo 797 00:33:20,500 --> 00:33:23,080 Y sólo fondos cabo, un caso base si 798 00:33:23,080 --> 00:33:25,740 lo hará, cuando golpeó una de las hojas, por así decirlo, 799 00:33:25,740 --> 00:33:28,580 donde una licencia no tiene hijos más. 800 00:33:28,580 --> 00:33:30,614 >> Ahora, ¿cómo puede usted encontrar el número 44? 801 00:33:30,614 --> 00:33:32,280 Se podría empezar en la raíz y decir, hm. 802 00:33:32,280 --> 00:33:35,690 55 no es 44 así que quiero ir derecho o quiero ir a la izquierda? 803 00:33:35,690 --> 00:33:37,190 Bueno, obviamente quiere ir izquierda. 804 00:33:37,190 --> 00:33:40,060 Y así es como el teléfono ejemplo del libro en la búsqueda binaria 805 00:33:40,060 --> 00:33:41,099 de manera más general. 806 00:33:41,099 --> 00:33:43,390 Pero estamos implementarlo ahora un poco más de forma dinámica 807 00:33:43,390 --> 00:33:45,339 de una matriz podría permitir. 808 00:33:45,339 --> 00:33:48,130 Y de hecho, si quieres buscar en el código, a primera vista seguro. 809 00:33:48,130 --> 00:33:49,671 Se parece a un montón de líneas. 810 00:33:49,671 --> 00:33:51,220 Pero es maravillosamente simple. 811 00:33:51,220 --> 00:33:54,490 Si desea implementar una función llamada de búsqueda cuyo propósito en la vida 812 00:33:54,490 --> 00:33:57,290 es la búsqueda de un valor como n, un entero, 813 00:33:57,290 --> 00:34:01,756 y ya está aprobada en una pointer-- un puntero al nodo de las raíces, 814 00:34:01,756 --> 00:34:04,380 más bien, de ese árbol desde el cual se puede acceder a todo lo demás, 815 00:34:04,380 --> 00:34:08,850 notar cómo rodeos usted puede aplicar la lógica. 816 00:34:08,850 --> 00:34:10,880 Si el árbol es nulo, obviamente, no está allí. 817 00:34:10,880 --> 00:34:11,880 Vamos a volver falsa. 818 00:34:11,880 --> 00:34:12,000 Derecha? 819 00:34:12,000 --> 00:34:14,040 Si te mano que nada, no hay nada allí. 820 00:34:14,040 --> 00:34:17,900 >> Else, si n es menor que árbol flecha n-- ahora flecha n, 821 00:34:17,900 --> 00:34:20,670 Recordamos introdujimos súper brevemente el otro día, 822 00:34:20,670 --> 00:34:25,100 y eso sólo significa de-referencia el puntero y mirar el campo denominado n. 823 00:34:25,100 --> 00:34:27,690 Por lo tanto, significa ir allí y mirar el campo denominado n. 824 00:34:27,690 --> 00:34:33,810 Así que si n, el valor que te dan, es menos que el valor en el número entero árboles, 825 00:34:33,810 --> 00:34:35,449 ¿dónde quieres ir? 826 00:34:35,449 --> 00:34:36,389 A la izquierda. 827 00:34:36,389 --> 00:34:37,780 >> Así notar la recursividad. 828 00:34:37,780 --> 00:34:39,860 Estoy returning-- no es cierto. 829 00:34:39,860 --> 00:34:40,989 No es falso. 830 00:34:40,989 --> 00:34:45,670 Estoy volviendo cualquiera que sea la respuesta es a partir de una llamada a mi mismo, que pasa 831 00:34:45,670 --> 00:34:50,100 un n de nuevo, que es redundante, pero lo que es un poco diferente ahora? 832 00:34:50,100 --> 00:34:51,989 ¿Cómo estoy haciendo el problema más pequeño? 833 00:34:51,989 --> 00:34:54,920 Estoy pasando como segundo argumento, no la raíz del árbol, 834 00:34:54,920 --> 00:34:59,616 pero el hijo izquierdo en este caso. 835 00:34:59,616 --> 00:35:00,990 Así que estoy pasando en el hijo izquierdo. 836 00:35:00,990 --> 00:35:04,720 >> Mientras tanto, si n es mayor que el nodo que actualmente estoy mirando, 837 00:35:04,720 --> 00:35:06,690 Yo busco el lado derecho. 838 00:35:06,690 --> 00:35:10,880 De lo contrario, si el árbol no es nulo, y si el elemento no está a la izquierda 839 00:35:10,880 --> 00:35:13,240 y no es a la derecha, lo que es maravillosamente el caso? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 En realidad nos hemos encontrado en el nodo pregunta, y así volvemos cierto. 842 00:35:18,440 --> 00:35:21,490 >> Así que acabamos de arañado la superficie ahora algunas de estas estructuras de datos. 843 00:35:21,490 --> 00:35:24,370 En el problema fijó cinco podrás explorar estos aún más lejos, 844 00:35:24,370 --> 00:35:27,250 y se le dará su diseño elección de cómo ir sobre esto. 845 00:35:27,250 --> 00:35:30,250 Lo que me gustaría llegar a la conclusión de es sólo un segundo teaser de 30 846 00:35:30,250 --> 00:35:32,080 de lo que espera a la semana que viene y más allá. 847 00:35:32,080 --> 00:35:35,390 >> A medida que begin-- afortunadamente te pueden think-- nuestra transición lentamente 848 00:35:35,390 --> 00:35:38,680 del mundo de la C y la más baja detalles de implementación de nivel, 849 00:35:38,680 --> 00:35:42,090 a un mundo en el que podemos tomar para sentado que alguien tiene por fin 850 00:35:42,090 --> 00:35:44,010 implementado estos datos estructuras para nosotros, 851 00:35:44,010 --> 00:35:47,570 y vamos a empezar a entender el significa el mundo real de la implementación 852 00:35:47,570 --> 00:35:50,560 programas basados ​​en la web y sitios web de forma más general 853 00:35:50,560 --> 00:35:52,910 y también la propia seguridad implicaciones que hemos sólo 854 00:35:52,910 --> 00:35:54,850 empezado a rascar la superficie de. 855 00:35:54,850 --> 00:35:57,320 Esto es lo que nos espera en los días por venir. 856 00:35:57,320 --> 00:36:00,480 >> [REPRODUCCIÓN DE VÍDEO] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Él Vino con un mensaje, con un protocolo de todas las suyas. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Él vino a un mundo de cruel firewalls, routers indiferentes, 861 00:36:30,894 --> 00:36:33,368 y peligros mucho peores que la muerte. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Es rápido. 864 00:36:36,236 --> 00:36:37,980 Es fuerte. 865 00:36:37,980 --> 00:36:42,830 Él es TCP / IP, y que tiene su dirección. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Guerreros de la red." 868 00:36:48,074 --> 00:36:49,660 [FIN REPRODUCCIÓN DE VÍDEO] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: Si viene la próxima semana. 870 00:36:50,910 --> 00:36:51,880 Nos vemos entonces. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [REPRODUCCIÓN DE VÍDEO] 873 00:36:56,060 --> 00:36:59,240 -Y Ahora, "Pensamientos profundos" por Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Comienza siempre conferencias con: "Muy bien." 876 00:37:05,820 --> 00:37:08,750 ¿Por qué no, "Aquí está la solución al conjunto de problemas de esta semana " 877 00:37:08,750 --> 00:37:12,180 o "Estamos dando a todos ustedes una A?" 878 00:37:12,180 --> 00:37:13,380 [Risas] 879 00:37:13,380 --> 00:37:15,530 [FIN REPRODUCCIÓN DE VÍDEO]