>> ALTAVOZ 1: Muy bien, así que estamos de vuelta.
Bienvenido a CS50.
Este es el final de la séptima semana.
Así que recordar que la última vez, empezamos mirando ligeramente más sofisticado
estructuras de datos.
Dado que hasta ahora, todo lo que teníamos realmente a nuestra disposición era esto, una matriz.
>> Pero antes de descartar la matriz como no todo lo que interesante, que de hecho se
realmente es, ¿cuáles son algunas de las ventajas de estos datos sencilla
estructurar hasta el momento?
¿Qué es lo bueno?
Por lo que hemos visto?
¿Qué tienes?
Nada.
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: ¿Qué es eso?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Tamaño fijo.
OK, así que ¿por qué es bueno, aunque de tamaño fijo?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: OK, así que es eficiente en la el sentido de que se puede asignar una
cantidad fija de espacio, lo cual es de esperar es precisamente tanto
espacio que quieras.
Así que podría ser absolutamente una ventaja.
>> ¿Cuál es la otra cara de una matriz?
¿Sí?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Todo el - lo siento?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Todos los cuadros en la memoria o uno junto al otro.
Y eso es útil - por qué?
Eso es muy cierto.
Pero ¿cómo podemos aprovechar esa verdad?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Exactamente, podemos mantener un registro de donde todo es sólo saber
una dirección, a saber, la dirección de la primer byte de ese trozo de memoria.
O en el caso de la cadena, la dirección de la primera
charla en esa cadena.
Y a partir de ahí, podemos encontrar el final de la cadena.
Podemos encontrar el segundo elemento, el tercer elemento, y así sucesivamente.
>> Y así, la manera elegante de describir que característica es que las matrices nos dan
de acceso aleatorio.
Sólo mediante el uso del corchete notación y un número, puede saltar a
un elemento específico de la matriz en tiempo constante, gran O
de uno, por así decirlo.
>> Pero ha habido algunos inconvenientes.
Lo que un conjunto no lo hacen con mucha facilidad?
¿Qué no hacer bien?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: ¿Qué es eso?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Ampliación de tamaño.
Así que los aspectos negativos de la matriz son precisamente lo contrario de lo que el
Upsides son.
Así que una de las desventajas es que es un tamaño fijo.
Así que realmente no se puede crecer.
Puede reasignar un pedazo más grande de la memoria y, a continuación, mover los elementos antiguos
en la nueva matriz.
Y luego liberar la matriz de edad, para los ejemplo, mediante el uso de malloc o similar
función llamada realloc, que reasigna memoria.
>> Realloc, como un aparte, intenta darle memoria que está al lado de la matriz
que ya tiene.
Pero podría mover cosas alrededor del todo.
Pero en fin, eso es caro, ¿no?
Porque si tienes un trozo de memoria de este tamaño, pero realmente quieres uno
de este tamaño, y desea conservar los elementos originales, que tienen
más o menos un proceso de copia de tiempo lineal eso tiene que suceder de
antigua matriz a la nueva.
Y la realidad está pidiendo a la operación sistema una y otra vez y
de nuevo por grandes trozos de la memoria puede comenzar que le costará algo de tiempo también.
Así que es tanto una bendición como una maldición en disfrazar, el hecho de que estas matrices
son de tamaño fijo.
Pero si introducimos en cambio algo como éste, que hemos denominado una ligado
lista, tenemos unas cuantas ventajas y algunas desventajas también aquí.
>> Así que una lista enlazada es simplemente un dato estructura compuesta de C estructuras en esta
caso, en que una estructura, el recuerdo, es sólo un contenedor para una o más específica
tipos de variables.
En este caso, lo que hacen los tipos de datos parecen estar dentro de la estructura que
última vez que se llama un nodo?
Cada uno de estos rectángulos es un nodo.
Y cada uno de los rectángulos más pequeños dentro de ella es un tipo de datos.
¿Qué tipos dijimos estaban el lunes?
¿Sí?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Una variable y un puntero, o más específicamente, un int, para n,
y un puntero en la parte inferior.
Tanto de los que pasan a ser de 32 bits, por lo menos en un equipo como éste CS50
Appliance y por lo que son dibujado por igual en tamaño.
>> Entonces, ¿qué está utilizando el puntero aunque para parecer?
¿Por qué añadir esta flecha ahora, cuando las matrices fueron tan agradable y limpio y simple?
¿Cuál es el puntero haciendo por nosotros en cada uno de estos nodos?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Exactamente.
Le está diciendo a donde el siguiente es.
Así que en cierto modo me utilizo la analogía de utilizando un hilo a una especie de
enhebrar estos nodos juntos.
Y eso es exactamente lo que estamos haciendo con punteros porque cada uno de estos
trozos de memoria pueden o no pueden ser contigua, espalda con espalda hacia atrás
dentro de la memoria RAM, ya que cada vez que llamada diciendo malloc, dame suficiente
bytes para un nuevo nodo, podría estar aquí o podría estar aquí.
Podría estar aquí.
Usted simplemente no sabe.
>> Pero el uso de punteros en las direcciones de esos nodos, puede coserlos
juntos en una manera que parece visualmente como una lista, incluso si estas cosas son
todo extendido en todo su ser o su dos o tus cuatro gigabytes de RAM
dentro de su propio equipo.
>> De modo que el lado negativo, pues, de una lista enlazada es lo que?
¿Qué es un precio que estamos al parecer, el pago?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Más espacio, ¿no?
Hemos, en este caso, duplicamos la cantidad de espacio, porque hemos ido
de 32 bits para cada nodo, para cada uno int, por lo que ahora de 64 bits, ya que tiene que
mantener en torno a un puntero también.
Usted obtiene más eficiencia si su estructura es más grande que esta cosa simple.
Si usted realmente tiene un estudiante en el interior de que es un par de cadenas de
nombre y la casa, tal vez un número de identificación, tal vez algunos otros campos en total.
>> Así que si usted tiene un gran suficiente estructura, entonces tal vez el costo del puntero es
no es una cosa muy importante.
Esto es un poco de un caso límite en que estamos almacenando una sencilla primitiva, tales
dentro de la lista enlazada.
Pero el punto es el mismo.
Definitivamente estás gastando más memoria, pero que está recibiendo
flexibilidad.
Porque ahora si quiero agregar un elemento al principio de esta lista,
Tengo que asignar un nuevo nodo.
Y tengo que acaba de actualizar los flechas de alguna manera, con sólo mover
algunos indicadores alrededor.
>> Si quiero insertar algo en el mitad de la lista, no tiene por qué
empujar a todos a un lado como lo hicimos en pasado semanas con nuestros voluntarios que
representado una matriz.
Yo sólo puedo asignar un nuevo nodo y a continuación, sólo apuntar las flechas en
diferentes direcciones, ya que no hace que permanecer en real
memoria una verdadera línea como he dibujado aquí en la pantalla.
>> Y luego, por último, si desea insertar algo al final de la lista, es
aún más fácil.
Esta es una especie de notación arbitraria, pero un triple de 34, tomar una conjetura.
¿Cuál es el valor de su indicador más probablemente dibujado algo así como un viejo
antena de escuela allí?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Probablemente es nulo.
Y de hecho es uno de los autores de representación de nulo.
Y es nula, porque a pesar de todo necesita saber dónde está el final de un vinculado
lista es, para que no se mantiene después y siguiendo y siguiendo estas flechas
a algún valor de basura.
Así nula significará que no es más nodos a la derecha del número 34,
en este caso.
>> Así que proponemos que podemos poner en práctica este nodo en el código.
Y hemos visto este tipo de sintaxis antes.
Typedef simplemente define un nuevo tipo de nosotros, nos da un sinónimo como
cadena era para char *.
En este caso, se nos va a dar notación abreviada de manera que el nodo struct
puede en su lugar sólo puede escribir como nodo, que es mucho más limpio.
Es mucho menos detallado.
>> Dentro de un nodo es aparentemente un int llamada n, y luego un nodo de estructura *
lo que significa exactamente lo que queríamos la flechas para significar, un puntero a otra
nodo del mismo tipo de datos exacta.
Y propongo que podríamos poner en práctica un función de búsqueda de este tipo, que en
primera vista podría parecer un poco compleja.
Pero vamos a verlo en su contexto.
>> Quiero pasar al aparato aquí.
Permítanme abrir un archivo llamado listar cero punto h.
Y que sólo contiene la definición que acabo de ver hace un momento para estos datos
tipo llamado un nodo.
Así que hemos puesto que en un archivo de puntos h.
>> Y en un aparte, a pesar de que esta programa que usted está a punto de ver es
no todo lo que complejo, es de hecho convenciones al escribir un programa para
poner las cosas como los tipos de datos, para sacar constantes a veces, dentro de su
archivo de cabecera y no necesariamente en el archivo de C, sobre todo cuando su
programas se hacen más grandes y más grandes, de modo que usted sabe dónde buscar, tanto para
documentación en algunos casos, o para lo básico como este, el
definición de algún tipo.
>> Si ahora abro la lista de puntos cero c, notar un par de cosas.
Incluye unos archivos de cabecera, la mayoría de los cuales hemos visto antes.
Incluye su propio archivo de cabecera.
>> Y en un aparte, ¿por qué eso es doble cita aquí, en comparación con el ángulo
soportes en la línea que He destacado allí?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Sí, así que es un archivo local.
Así que si es un archivo local de su propia aquí en la línea 15, por ejemplo, se utiliza
las comillas dobles en vez de los paréntesis angulares.
>> Ahora bien, esto es algo interesante.
Nótese que he declarado un mundial variable en este programa en la línea 18
llamó en primer lugar, la idea de esto es va a ser un puntero a la primera
nodo en mi lista enlazada, y he inicializa a null, porque he
no asignado ningún real nodos por el momento.
>> Así que esto representa, gráficamente, lo que vi hace un momento en la imagen como
ese puntero en el extremo a mano izquierda.
Así que ahora mismo, ese puntero no tiene una flecha.
En su lugar, es nulo.
Pero representa lo que será el dirección del primer real
nodo en esta lista.
Así que he implementado es un mundial porque, como se verá, todo esto
programa hace en la vida se implemento una lista enlazada para mí.
>> Ahora tengo un par de prototipos aquí.
Decidí implementar características como deleción, inserción, búsqueda y
de recorrido -
el último sólo estar a pie a través de la lista, la impresión de sus elementos.
Y ahora aquí está mi rutina principal.
Y no vamos a pasar mucho tiempo en éstas ya que esta es una especie de, ojalá
viejo sombrero por ahora.
>> Voy a hacer lo siguiente, mientras el usuario coopera.
Así que uno, voy a imprimir salir de este menú.
Y he formateado como limpiamente como pude.
Si el usuario escribe en uno, para que los medios quieren borrar algo.
Si el usuario escribe en dos, que los medios quieren insertar algo.
Y así sucesivamente.
Voy a continuación, pedirá a continuación, para un comando.
Y entonces voy a utilizar GetInt.
>> Así que este es un muy simple de menús interfaz en la que sólo tiene que escribir
una asignación de número a uno de esos comandos.
Y ahora tengo un interruptor limpio agradable declaración que va a cambiar el
cualquiera que sea el usuario escribió pulg
Y si ellos escriben uno, voy a llamar a delete y se rompa.
Si se escriben dos, voy a llamar inserción y descanso.
>> Y ahora noto que he puesto cada de estos en la misma línea.
Esto es sólo una decisión estilística.
Normalmente hemos visto algo como este.
Pero decidí, francamente, mi programa parecía más fácil de leer porque
era sólo cuatro casos a sólo lista así.
Totalmente uso legítimo de estilo.
Y yo voy a hacer esto siempre y cuando el El usuario no ha escrito cero, lo que me
decidido significará que quieren dejar de fumar.
>> Así que ahora doy cuenta de lo que soy vamos a hacer aquí.
Voy a liberar a la lista aparentemente.
Pero más sobre esto en un momento.
Primero vamos a ejecutar este programa.
Así que permítanme hacer una terminal más grande ventana, lista slash dot 0.
Voy a seguir adelante e inserte por escribir dos, un número como 50, y ahora
verás la lista es ahora 50.
Y mi texto sólo desplaza un poco.
Así que ahora cuenta la lista contiene el número 50.
>> Vamos a hacer otro inserto tomando dos.
Vamos a escribir el número como tal.
Lista es ahora uno, seguido por 50.
Así que esto es sólo una representación textual de la lista.
Y vamos a insertar un número más como el número 42, que es de esperar
va a terminar en el medio, porque este programa de clases particulares que
elementos, ya que los inserta.
Así que ahí lo tenemos.
Programa Súper simple que podría absolutamente he utilizado una matriz, pero
pasaría a estar usando una lista enlazada Sólo para que pueda dinámicamente
crecer y reducir su tamaño.
>> Así que echemos un vistazo a la búsqueda, si comando de tres carreras, quiero buscar
para, por ejemplo, el número 43.
Y nada se encontró al parecer, porque volví ninguna respuesta.
Así que vamos a hacer esto de nuevo.
Búsqueda.
Vamos a buscar el 50, o más bien buscar el 42, que tiene una bonita
poco significado sutil.
Y he encontrado el sentido de la vida allí.
Número 42, si usted no sabe la referencia, Google él.
Está bien.
Entonces, ¿qué ha hecho este programa para mí?
Simplemente me ha permitido insertar este modo a lo largo y búsqueda de elementos.
>> Vamos a avanzar rápidamente, entonces, esa función nos miró a
el lunes como un reclamo.
Así que esta función, reclamo, busca un elemento en la lista por primera
uno, preguntar al usuario y luego llamar GetInt para obtener un int real
que desea buscar.
>> Entonces note esto.
Voy a crear una variable temporal en línea 188 llama puntero -
PTR -
podrían haber llamado cualquier cosa.
Y es un puntero a un nodo porque he dicho nodo * allí.
Y estoy inicializando que sea igual a primero, para que yo efectivamente tengo mi
dedo de la mano, por así decirlo, en el mismo primer elemento de la lista.
Así que si mi mano derecha aquí es PTR estoy apuntando a lo mismo que la primera
está apuntando.
>> Así que ahora de nuevo en el código, ¿qué pasa después -
este es un paradigma común cuando se repite sobre una estructura como un
lista enlazada.
Yo voy a hacer lo siguiente mientras puntero no es igual a null Así, mientras que
mi dedo no está apuntando en algún nula valor, si el puntero de flecha n es igual a n.
Nos daremos cuenta primero que n es lo que el tecleado por el usuario GetInts llamar aquí.
>> Y puntero de flecha n significa qué?
Bueno, si nos remontamos a la imagen aquí, si tengo un dedo apuntando a
que primero nodo que contiene nueve, la flecha esencialmente significa que vaya a
nodo y agarrar el valor en la posición n, en este caso, el campo de datos llama n.
>> Como acotación al margen - y vimos esto un par de hace semanas, cuando alguien le preguntó -
esta sintaxis es nuevo, pero no es así darnos poderes que
no ya tienen.
¿Qué era esta frase equivale a utilizar notación de puntos y protagonizar un par
de hace semanas cuando nos pelamos espalda esta capa un poco antes de tiempo?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Exactamente, era la estrella, y entonces era punto estrella n, con
paréntesis aquí, lo que se ve, Francamente, creo que mucha
más críptico de leer.
Pero indicador de la estrella, como siempre, medios van allí.
¿Y una vez que estás allí, ¿qué datos qué campo desea acceder?
Pues usted utiliza la notación de puntos para el acceso un campo de datos estructuras, y yo
específicamente querer n.
>> Francamente, yo diría esto es simplemente más difícil de leer.
Es más difícil de recordar dónde salen de los paréntesis, la
estrella y todo eso.
Así que el mundo adoptó algunas sintáctica azúcar, por así decirlo.
Apenas una manera atractiva de decir, esto es equivalente, y
quizás más intuitivo.
Si el puntero es de hecho un puntero, el flecha notación significa ir allí y encontrar
el campo, en este caso llamado n.
>> Así que si lo encuentro, noto lo que hago.
Simplemente me imprimo, encontré ciento i, enchufar el valor para ese int.
Yo lo llamo el sueño durante un segundo sólo para clase de hacer una pausa en las cosas en la pantalla para
dar al usuario un segundo para absorber lo que acaba de suceder.
Y entonces me rompo.
De lo contrario, ¿qué hago?
Actualizo puntero a la igualdad de puntero flecha siguiente.
>> Así que para ser claros, esto significa ir allí, usando mi notación de la vieja escuela.
Así que esto sólo significa ir a lo que sea usted está apuntando a que, en el muy
primer caso es que estoy señalando a la estructura con nueve en el mismo.
Así que he ido allí.
Y entonces se entiende la notación de puntos, obtener el valor al siguiente.
>> Pero el valor, a pesar de que se dibuja como un estrecho, es sólo un número.
Es una dirección numérica.
Así que esta una línea de código, ya sea escrito como éste, el más críptico
manera, o así, los poco más manera intuitiva, simplemente significa mover mi mano
desde el primer nodo al siguiente, y luego el siguiente, y a continuación, la
siguiente, y así sucesivamente.
>> Así que no voy a detenerme en el otro implementaciones de insertar y eliminar
y el recorrido, los dos primeros de que son bastante implicados.
Y creo que es muy fácil de conseguir perdido al hacerlo verbalmente.
Pero lo que podemos hacer aquí es tratar de determinar cómo
la mejor manera de hacer esto visualmente.
Porque yo propondría que si desee insertar elementos en esta
lista existente, que tiene cinco elementos -
9, 17, 22, 26, y 33 -
si yo fuera a implementar esto en código, tengo que estudiar la manera de ir
haciendo esto.
>> Y yo propondría tomar pasos de bebé por lo que, en este caso me refiero, ¿cuáles son
los posibles escenarios que nos podría encontrarse en general?
En la aplicación de inserción para un ligado lista, esto sólo pasa a ser un
ejemplo concreto de tamaño cinco.
Bueno, si usted desea insertar un número, como decir el número uno, y
mantener el orden establecido, donde obviamente, hace el número uno de la necesidad de
ir en este ejemplo específico?
Al igual que al principio.
>> Pero lo interesante no es que si desea insertar una en este
lista, qué necesidades puntero especiales ser actualizado aparentemente?
En primer lugar.
Así que yo diría, este es el primer caso que lo que se quiere tener en cuenta, una
escenario que implica insertar al el principio de la lista.
>> Vamos a arrancar tal vez una tan fácil o incluso caso más fácil, relativamente hablando.
Supongamos que quiero insertar el el número 35 en el orden establecido.
Obviamente pertenece allí.
Entonces, ¿qué puntero obviamente va a tienen que actualizarse en ese escenario?
Un triple de 34 convirtiéndose no nula pero la dirección de la estructura
que contiene el número 35.
Así que ese es el caso de dos.
Así que ya, yo soy una especie de cuantificación la cantidad de trabajo que tengo que hacer aquí.
>> Y, por último, el caso medio obvio es de hecho, en el medio, si quiero
insertar algo así como decir 23, que va entre el 23 y el 26, pero
Ahora las cosas se ponen un poco más participar porque lo
punteros hay que cambiar?
Así 22 obviamente necesita ser cambiado porque no puede apuntar a 26 más.
Él tiene que apuntar al nuevo nodo que Voy a tener que destinar llamando
malloc o algún equivalente.
>> Pero también necesito que el nuevo nodo, 23 en este caso, para tener su puntero
señalando a quién?
26.
Y va a ser un orden de las operaciones aquí.
Porque si hago esto tontamente, y yo por ejemplo comenzar por el principio de
la lista, y mi objetivo es insertar 23.
Y compruebo, le pertenece aquí, cerca de las nueve?
No.
¿Pertenece aquí, junto a 17?
No.
¿Le pertenece a este lugar junto a 22?
Sí.
>> Ahora bien, si soy tonto aquí, y no pensando en esto, yo podría
asignar mi nuevo nodo para 23.
Yo podría actualizar el puntero de el nodo llamado 22, que señala
que en el nuevo nodo.
Y entonces, ¿qué tengo que actualizar puntero del nuevo nodo que se va?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Exactamente.
Señalando a 26.
Pero dammit si no tuviera ya actualizo Puntero del 22 al punto en el que este tipo, y
Ahora tengo los huérfanos, el resto de la lista, por así decirlo.
Así que el fin de las operaciones aquí va a ser importante.
>> Para ello podría robar, decir, seis voluntarios.
Y veamos si no podemos hacer esto visualmente en lugar del código se refiere.
Y tenemos un poco de estrés encantadora bolas para usted hoy.
Bien, ¿qué hay de una, dos, en el espalda - en el extremo allí.
tres, cuatro, los dos chicos en la final.
Y cinco, seis.
Claro.
Cinco y seis.
Está bien y vamos a venir con ustedes la próxima vez.
Muy bien, vamos arriba.
>> Muy bien, ya que estás aquí primero, ¿te gustaría ser el que torpemente
en Google Glass aquí?
Muy bien, entonces, OK, Glass, grabar un video.
Bueno, ya está bueno para ir.
>> Muy bien, así que si ustedes pueden venir aquí, he preparado con antelación
algunos números.
Muy bien, vamos por aquí.
¿Y por qué no te vas un poco promover de esa manera.
Y vamos a ver, ¿cómo te llamas, con el cristal de Google?
>> ESTUDIANTE: Ben.
>> ALTAVOZ 1: Ben?
Bueno, Ben, que será la primera, literalmente.
Así que vamos a enviarle al final de la etapa.
Muy bien, y tu nombre?
>> ESTUDIANTE: Jason.
>> ALTAVOZ 1: Jason, OK tendrás ser el número nueve.
Así que si quieres seguir Ben de esa manera.
>> ESTUDIANTE: Jill.
>> ALTAVOZ 1: Jill, vas a ser 17, que si yo hubiera hecho esto más
inteligente, que tendría comenzado en el otro extremo.
Usted va de esa manera.
22.
Y usted es?
>> ESTUDIANTE: María.
>> ALTAVOZ 1: María, que será 22.
Y su nombre es?
>> ESTUDIANTE: Chris.
>> ALTAVOZ 1: Chris, podrás 26.
Y a continuación, por último.
>> ESTUDIANTE: Diana.
>> ALTAVOZ 1: Diana, usted será 34.
Así que vienes por aquí.
>> Muy bien, así que perfecto ordenados ordenar ya.
Y vamos a seguir adelante y hacer esto para que podamos realmente -
Ben sólo estás buscando tipo de hacia la nada allí.
OK, así que vamos a seguir adelante y representan esta utilizando los brazos, al igual que yo, exactamente,
¿qué está pasando.
Así que adelante y dense un o dos pies entre ustedes mismos.
Y seguir adelante y punto con una mano para quienquiera que debe apuntar a
basado en esto.
Y si usted es sólo el punto nulo directamente hacia el suelo.
OK, así que bien.
>> Así que ahora tenemos una lista enlazada, y me dejó Propongo que voy a jugar el papel de
PTR, así que no me molestaré llevar esto alrededor.
Y entonces - alguien convención estúpida - usted puede llamar a esto todo lo que quieras -
puntero predecesor, puntero pred -
es sólo el apodo que dimos en nuestro código de ejemplo para la mano izquierda.
La otra parte que va a ser de mantenimiento Saber quién es quién en la
siguientes escenarios.
>> Así que supongamos que, en primer lugar, quiero arrancar ese primer ejemplo de inserción, por ejemplo
20, en la lista.
Así que voy a necesitar a alguien que encarnar el número 20 para nosotros.
Así que tengo que malloc alguien de la audiencia.
Vamos arriba.
¿Cómo te llamas?
>> ESTUDIANTE: Brian.
>> ALTAVOZ 1: Brian, de acuerdo, por lo que será el nodo que contiene 20.
Muy bien, vamos por aquí.
Y, obviamente, donde pertenece Brian?
Así, en medio de - en realidad, Espera un minuto.
Estamos haciendo esta fuera de orden.
Estamos haciendo esto mucho más difícil de lo que debe ser en un principio.
Bien, vamos a liberar a Brian y realloc Brian como cinco.
>> OK, así que ahora queremos insertar Brian como cinco.
Así que ven aquí al lado Ben sólo por un momento.
Y, presumiblemente, puede decir donde esta historia se va.
Pero vamos a pensar cuidadosamente acerca de el orden de las operaciones.
Y es precisamente esta visual eso va a alinear
con ese código de ejemplo.
Así que aquí tengo PTR apuntando inicialmente no a Ben, per se, sino en lo que sea
valor que contiene, que en este caso es - ¿cuál es tu nombre?
>> ESTUDIANTE: Jason.
>> ALTAVOZ 1: Jason, por lo tanto, Ben y yo estamos señalando a Jason en este momento.
Así que ahora tengo que determinar, donde pertenece Brian?
Así que lo único que tengo acceso a ahora es su elemento de datos n.
Así que voy a comprobar, es Brian menos de Jason?
La respuesta es verdadera.
>> ¿Y ahora qué tiene que suceder, en el orden correcto?
Necesito actualizar el número de punteros en total en esta historia?
Donde mi mano todavía está apuntando a Jason, y su mano - si usted desea
poner su mano como, más o menos, me no sé, un signo de interrogación.
Bueno, bueno.
>> Muy bien, por lo que tiene algunos candidatos.
Cualquiera de Ben, yo o Brian o Jason o cualquier otra persona, que
punteros tienen que cambiar?
¿Cuántos en total?
>> OK, así que dos.
Mi puntero en realidad no importa ya porque yo soy sólo temporal.
Así que es a estos dos chicos, supuestamente, tanto Ben y Brian.
Así que permítanme proponer que actualizamos Ben, ya que él es primero.
El primer elemento de esta lista ahora va a ser Brian.
Así que el punto Ben en Brian.
Bien, ¿y ahora qué?
>> ¿Quién se apunta a quién?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Aceptar lo que Brian tiene para apuntar a Jason.
Pero he perdido la cuenta de ese puntero?
¿Sé dónde está Jason?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: yo, como soy el puntero temporal.
Y, presumiblemente, no he cambiado para señalar en el nuevo nodo.
Así que simplemente podemos tener punto de Brian en el que estoy señalando.
Y ya hemos terminado.
Así caso de que uno, la inserción en el principio de la lista.
Había dos pasos clave.
Uno de ellos, tenemos que actualizar Ben, y luego también tenemos que actualizar Brian.
Y entonces yo no tengo que molestar penosamente a través de el resto de la
enumerar, porque ya encontramos su ubicación, porque pertenecía a la
la izquierda del primer elemento.
>> Muy bien, así que bastante sencillo.
De hecho, se siente como que estamos casi haciendo esto demasiado complicado.
Así que ahora vamos a arrancar el final de la lista, y ver dónde
la complejidad comienza.
Así que si ahora, de asignación de la audiencia.
¿Alguien quiere jugar al 55?
Muy bien, lo vi primero su mano.
Vamos arriba.
Sí.
¿Cómo te llamas?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Habata.
Bien, vamos arriba.
Usted será el número 55.
Así que, por supuesto, pertenece al final de la lista.
Así que vamos a jugar de nuevo la simulación conmigo siendo el PTR por un momento.
Así que estoy primero va a apuntar a lo que apunta a Ben.
Los dos estamos apuntando ahora a Brian.
Así que 55 no sea inferior a cinco.
Así que voy a actualizar mi mismo por apuntando a la siguiente triple de Brian, que
ahora es, por supuesto, Jason.
55 no sea inferior a nueve, por lo que Voy a actualizar PTR.
Voy a actualizar PTR Me va a actualizar PTR.
Y yo voy a - hmm, ¿qué tu nombre?
>> ESTUDIANTE: Diana.
>> ALTAVOZ 1: Diana está señalando, por supuesto, en nulo con la mano izquierda.
Así que ¿de dónde viene en realidad Habata pertenecer claramente?
A la izquierda, aquí.
Entonces, ¿cómo puedo saber que ponerla aquí Creo que he metido la pata.
Porque lo que es arte PTR este momento en el tiempo?
Null.
Así que a pesar de que, visualmente, podemos obviamente ver todos estos
chicos aquí en el escenario.
Yo no he mantenido un seguimiento de la anterior persona en la lista.
Yo no tengo un dedo señalando, en este caso, el número de nodo 34.
>> Así que vamos a empezar en realidad esta vez.
Así que ahora realmente necesito una segunda variable local.
Y esto es lo que verás en el código de ejemplo C real, en tanto que yo voy,
cuando actualizo mi mano derecha para señalar Jason, dejando detrás de Brian, me
mejor empezar a usar mi mano izquierda para Actualiza donde yo estaba, de modo que a medida que avanzo
a través de esta lista -
más torpe de lo que pretendía ahora aquí visualmente -
Voy a llegar a la final de la lista.
>> Esta mano es todavía nula, lo cual es bastante inútil, salvo para indicar
Estoy claramente al final de la lista, pero ahora por lo menos tengo esta
puntero predecesor señalando aquí, así ahora lo que las manos y lo que necesitan punteros
ser actualizado?
Cuya mano es lo que quieres reconfigurar primero?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: OK, así que Diana.
¿Dónde quieres que señalar Diana del puntero de la izquierda en?
En 55, presumiblemente, de manera que hemos insertado allí.
¿Y dónde debería ir el 55 de puntero?
Presionado, que representa un valor nulo.
Y mis manos, en este punto, no lo hacen importa porque no eran más que
variables temporales.
Así que ahora que hemos terminado.
>> Así que la complejidad adicional allí - y que no es tan difícil de implementar,
pero necesitamos una variable secundaria para hacer Asegúrese de que antes de pasar a mi derecho
lado, puedo actualizar el valor de mi izquierda mano, puntero pred en este caso, por lo
que tengo un indicador de seguimiento hacer un seguimiento de dónde estaba.
Ahora, como un aparte, si estás pensando en este a través, esto se siente como si fuera un
poco molesto tener que mantener seguimiento de esta mano izquierda.
>> ¿Qué sería de otra solución a este problema han sido?
Si has llegado a rediseñar los datos estructura que estamos hablando
a través de estos momentos?
Si sólo un poco se siente un poco molesto tener, como, dos punteros
pasando por la lista, ¿quién más podría han, en un mundo ideal, mantenido
información que necesitamos?
¿Sí?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Exactamente.
Justo lo que hay realmente una interesante germen de una idea.
Y esta idea de un puntero anterior, señalando el elemento anterior.
¿Y si sólo encarnó ese dentro de la propia lista?
Y va a ser difícil de visualizar esto sin todo el papel
cayendo al suelo.
Pero supongamos que estos chicos utilizan tanto de sus manos para tener un anterior
puntero, y un indicador de siguiente, con lo que aplicación de lo que vamos a llamar a un doble
lista enlazada.
Eso me permitiría especie de rebobinado, mucho más fácilmente sin mí, el
programador, tener que mantener seguimiento manual -
verdaderamente manualmente -
de donde había estado previamente en la lista.
Así que no vamos a hacer eso.
Vamos a mantenerlo simple, porque eso es va a tener un precio, el doble de
mucho espacio para los punteros, si quieres una segunda.
Pero eso es de hecho una común estructura de datos conocida como una
lista doblemente enlazada.
>> Vamos a hacer el último ejemplo aquí y poner estos chicos fuera de su miseria.
Así malloc 20.
Vamos desde el pasillo allí.
Muy bien, ¿cuál es tu nombre?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: ¿Cómo dice?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Demeron?
Aceptar vamos arriba.
Usted será el 20.
Usted, evidentemente, va a pertenecen entre el 17 y el 22.
Así que vamos a aprender la lección.
Voy a empezar puntero señalando a Brian.
Y yo voy a tener mi mano izquierda sólo actualizar a Brian como me mudo a
Jason, la comprobación hace 20 menos de nueve?
No.
Es 20 menos de 17?
No.
Es 20 menos de 22?
Sí.
Entonces, ¿qué consejos o las manos deben cambiar donde están apuntando ahora?
>> Así que podemos hacer 17 que apunta a los 20.
Así que eso está bien.
¿Dónde queremos señalar el puntero ahora?
A los 22 años.
Y sabemos donde 22 es, de nuevo, gracias a mi puntero temporal.
Así que estamos bien allí.
Así que debido a esto el almacenamiento temporal He mantenido un seguimiento de dónde es cada uno.
Y ahora usted puede ir visualmente en donde al que pertenece, y ahora nos necesita 1, 2, 3,
4, 5, 6, 7, 8, 9 bolas de la tensión, y una ronda de aplausos para
estos chicos, si pudiéramos.
Muy bien hecho.
>> [Aplausos]
>> ALTAVOZ 1: Muy bien.
Y es posible mantener las piezas de papel como recuerdos.
>> Muy bien, entonces, confía en mí que es mucho fácil de caminar a través de eso con
los seres humanos que es con código real.
Pero lo que encontrará en un momento ahora, es el mismo - oh, gracias.
Gracias -
es que usted encontrará que los mismos datos estructura, una lista enlazada, puede en realidad
ser utilizado como un bloque de construcción para aún más estructuras de datos sofisticadas.
>> Y se dan cuenta demasiado el tema aquí es que que absolutamente hemos introducido más
complejidad en la implementación de este algoritmo.
Inserción, y si nos fuimos a través de él, supresión y búsqueda, es un poco de
más complicado de lo que estaba con una matriz.
Pero ganamos algo de dinamismo.
Tenemos una estructura de datos de adaptación.
>> Pero, de nuevo, tenemos que pagar un precio de tener alguna complejidad adicional, tanto en
su aplicación.
Y se nos da el acceso aleatorio.
Y para ser honesto, no hay algún buen portaobjetos limpio me puede dar esa
dice aquí es por qué una lista enlazada es mejor que una matriz.
Y dejar las cosas así.
Debido a que el tema recurrente ahora, incluso más aún en las próximas semanas, es
que no es necesariamente una respuesta correcta.
>> Es por eso que tenemos el eje por separado de diseñar para los boletines de problemas.
Va a ser muy sensible al contexto si desea utilizar estos datos
estructura o que uno, y lo hará dependerá de lo que te importa en términos
de los recursos y la complejidad.
>> Pero permítanme proponer que los datos ideales estructura, el santo grial, sería
algo que es constante de tiempo, independientemente de la cantidad de cosas es
dentro de él, ¿no sería increíble si un estructura de datos devuelve respuestas en
constante de tiempo.
Sí.
Esta palabra es en su gran diccionario.
O no, esta palabra no es.
O tal problema.
Bueno vamos a ver si no podemos, al menos, dar un paso en esa dirección.
>> Permítanme proponer una nueva estructura de datos que puede ser utilizado para diferentes cosas,
en este caso se llama una tabla hash.
Y por lo que estamos realmente de nuevo a mirar en una matriz, en este caso, y
algo arbitrariamente, he dibujado esta la tabla de hash como una matriz con una especie de
matriz de dos dimensiones -
o más bien que está representado aquí como dos matriz bidimensional - pero esto es sólo
una matriz de tamaño 26, de tal manera que si nos llame a la mesa de matriz, soporte de mesa
cero es el rectángulo en la parte superior.
Tabla soporte 25 es el rectángulo en la parte inferior.
Y así es como yo podría dibujar un datos estructura en la que quiero para almacenar
nombres de las personas.
>> Así por ejemplo, y no voy a señalar a la Todo aquí en la cabeza, si me
tenido esta matriz, que ahora voy a llamar a una tabla hash, y esto es de nuevo
ubicación cero.
Esto aquí es la ubicación uno, y así sucesivamente.
Afirmo que quiero utilizar estos datos estructura, por el bien de la discusión,
para almacenar nombres de las personas, Alice y Bob y Charlie y otros nombres.
Así que pensar en esto ahora como el inicio de, por ejemplo, un diccionario
con un montón de palabras.
Ellos resultan ser nombres en nuestro ejemplo aquí.
Y esto es muy pertinente, tal vez, para la implementación de un corrector ortográfico, como hemos
fuerza para la solución seises.
>> Así que si tenemos una matriz de tamaño total de 26 de manera que esta es la ubicación 25a
en la parte inferior, y yo sostengo que Alice es la primera palabra en el diccionario de
nombres que quiero insertar en la memoria RAM, en esta estructura de datos, donde son
instintos que le dice que de Alice nombre debe ir en esta serie?
>> Tenemos 26 opciones.
Dónde queremos ponerla?
Nosotros la queremos en soporte de cero, ¿no?
Una de Alice, vamos a llamar a ese cero.
Y B será uno, y C será de dos.
Así que vamos a escribir El nombre de Alice aquí.
Si a continuación, insertamos Bob, su nombre pasará aquí.
Charlie va a ir aquí.
Y así sucesivamente a lo largo de esta estructura de datos.
>> Esta es una estructura de datos maravillosa.
¿Por qué?
Bueno, ¿qué es el tiempo de ejecución de insertar el nombre de un ser humano en este
estructura de datos en este momento?
Teniendo en cuenta que esta tabla se implementa, verdaderamente, como una matriz.
Bueno, es la constante de tiempo.
Es el fin de una.
¿Por qué?
>> Bueno, ¿cómo determinar donde pertenece Alice?
Te ves en qué letra de su nombre?
El primero.
Y se puede llegar, si se trata de una cadena, con sólo mirar cadena
soporte de cero.
Así el carácter de orden cero de la cadena.
Eso es fácil.
Hicimos eso en la criptografía Hace asignación semana.
Y luego, una vez que sabes que de Alice letra es mayúscula, podemos restar
off 65 o la propia capital de A, eso nos da cero.
Así que ahora sabemos que Alice pertenece en la posición cero.
>> Y teniendo en cuenta un puntero a estos datos estructura, de algún tipo, hace cuánto tiempo
que me lleve a encontrar la ubicación cero en una matriz?
A sólo un paso, ¿no es la constante de tiempo por la que el acceso aleatorio
propuso fue una característica de una matriz.
Así que en resumen, averiguar lo que el índice de el nombre de de Alice es, que es, en
este caso, es A, o vamos a resolver que a cero, donde B es uno y C es
dos, pensando que fuera es la constante de tiempo.
Sólo tengo que mirar en su primera carta, averiguar donde cero es un
matriz es también constante de tiempo.
Así que técnicamente eso es como dos pasos ahora.
Pero eso sigue siendo constante.
Así que llamamos a esa gran O de uno, por lo que hemos Alice inserta en esta tabla en
constante de tiempo.
>> Pero, por supuesto, estoy siendo ingenuo, ¿no?
¿Qué pasa si hay un Aarón en la clase?
O Alicia?
O cualquier otro nombre que comience con A. ¿Dónde vamos a poner
esa persona, ¿verdad?
Quiero decir, ahora mismo sólo hay tres gente en la mesa, así que tal vez
debe poner Aaron en la ubicación cero uno dos tres.
>> Bien, yo podría poner una aquí.
Pero entonces, si se quiere insertar en David esta lista, ¿a dónde va David?
Ahora nuestro sistema comienza a metabolizar abajo, derecha?
Porque ahora David termina aquí si Aaron es en realidad aquí.
Y por lo que ahora esta todo idea de tener un estructura de datos limpia que nos da
inserciones de tiempo constantes ya no es constante de tiempo, porque tengo que
comprobar, oh, maldita sea, ya hay alguien trabajando en la ubicación de Alice.
>> Permítame sondear el resto de estos datos estructura, en busca de un lugar para poner
alguien como el nombre de Aarón.
Y para que también está empezando tomar el tiempo lineal.
Por otra parte, si ahora quieres encontrar el Aaron en esta estructura de datos, y
cheque, y el nombre de Aarón no está aquí.
Lo ideal sería que usted acaba de decir de Aarón no en la estructura de datos.
Pero si usted comienza a hacer espacio para Aaron donde debería haber sido un D
o un correo, usted, peor de los casos, tiene que comprobar toda la estructura de datos, en
cuyo caso se convirtiera en algo lineal en el tamaño de la tabla.
>> Así bien, voy a arreglar esto.
El problema aquí es que tuve 26 elementos de esta matriz.
Permítanme cambiaré.
¡Vaya.
Déjame cambiar de tal manera que en lugar de ser de talla 26 en total, cuenta de la parte inferior
índice se va a cambiar a n menos 1.
Si 26 es claramente demasiado pequeño para los seres humanos " nombres, porque hay miles de
nombres del mundo, vamos a hacer en 100 o 1000 o 10000.
Vamos a asignar un espacio mucho más.
>> Bueno, eso no disminuye necesariamente la probabilidad de que no vamos a tener dos
personas con nombres que empiecen con A, y así, que iba a tratar de poner un
nombres en lugar de cero aún.
Siguen yendo a chocar, que significa que todavía necesitamos una solución para poner
Alice y Aarón y Alicia y otros nombres que empiecen con A otro lugar.
Pero, ¿cuánto de un problema es el siguiente?
¿Cuál es la probabilidad de que tener colisiones en un datos
estructura como esta?
>> Bueno, déjame - volveremos a esa pregunta aquí.
Y mira cómo podríamos resolverlo primero.
Déjame sacar esta propuesta aquí.
Lo que acabamos de describir es un algoritmo, una heurística llamada lineal
sondeo según el cual, si se trató de insertar algo aquí en estos datos
estructura, que se llama una tabla hash, y no hay lugar allí,
verdaderamente sondear la estructura de datos cheques, es este disponible?
¿Es esta disponible es esta disponible?
Es esta disposición?
Y cuando finalmente es, insertar el nombre que la intención original
en otro lugar en esa ubicación.
Pero en el peor de los casos, el único punto podría ser la parte inferior de los datos
estructura, el final de la matriz.
>> Así sondeo lineal, en el peor de los casos, recae en un algoritmo lineal en
Aaron, si él pasa a ser insertado última en esta estructura de datos, que podría
colisionar con esta primera ubicación, pero luego terminar por la mala suerte en el final.
Así que esto no es una constante santo grial tiempo para nosotros.
Este enfoque de la inserción de elementos en una estructura de datos llamada un valor hash
tabla no parece ser la constante de tiempo al menos no en el caso general.
Puede delegar en algo lineal.
>> ¿Y qué si resolvemos las colisiones algo diferente?
Así que aquí está una más sofisticada aproximación a lo que es aún
denominada tabla hash.
Y por hash, como un aparte, lo que Quiero decir es el índice que
Me he referido antes.
Para discutir algo puede ser considerado como un verbo.
>> Así que si el hash de Alice un nombre, una función hash, por así decirlo,
debe devolver un número.
En este caso es cero si pertenece a posición cero, uno si ella pertenece al
ubicación uno, y así sucesivamente.
Así que mi función hash hasta ahora ha sido super simple, sólo mirando el
primera letra del nombre de alguien.
Pero una función hash toma como entrada de alguna pieza de datos, un
cadena, un entero, lo que sea.
Y escupe típicamente un número.
Y ese número es donde los datos elemento pertenece en una estructura de datos
conocido aquí como una tabla hash.
>> Por lo que sólo intuitivamente, se trata de una un contexto ligeramente distinto.
En realidad, esto se refiere a un ejemplo involucrando los cumpleaños, donde
puede haber tantos como 31 días en el mes.
Pero lo que hizo esta persona decide hacer en caso de una colisión?
Contexto siendo ahora, no un choque de nombres, pero una colisión de los cumpleaños,
si dos personas tienen la misma fecha de nacimiento en el 2 de octubre, por ejemplo.
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Sí, así que aquí tenemos el aprovechamiento de las listas enlazadas.
Así se ve un poco diferente que dibujamos antes.
Pero parece que tenemos a un array en el lado de mano izquierda.
Eso es un índice, por ninguna en particular la razón.
Pero sigue siendo una matriz.
Es una matriz de punteros.
Y cada uno de esos elementos, cada uno de los estos círculos o rayas verticales - la raya vertical
representando nula - cada uno de estos punteros es aparentemente señalando
qué estructura de datos?
Una lista enlazada.
>> Así que ahora tenemos la capacidad de codificar directamente en nuestro programa
el tamaño de la tabla.
En este caso, sabemos que nunca hay más de 31 días en un mes.
Tan duro codificando un valor como 31 es razonable en ese contexto.
En el contexto de los nombres, de codificación duro 26 no es irrazonable, la gente de
sólo nombres comienzan con, por ejemplo, el alfabeto de la A a la participación de Z.
>> Podemos meter a todos en que los datos estructura, siempre que, cuando tenemos una
colisión, no ponemos los nombres aquí, nosotros en cambio pensamos en estas células
no como cadenas de sí mismos, sino como punteros a, por ejemplo, Alice.
Y entonces Javier puede tener otro puntero a otro nombre que comience con
A. Y Bob realidad va por aquí.
>> Y si hay otro nombre de partida con B, termina aquí.
Y así cada uno de los elementos de este mesa dos, si hemos diseñado este un
poco más inteligentemente -
vamos -
si hemos diseñado este un poco más inteligentemente, ahora se convierte en un dato de adaptación
estructura, donde no hay límite duro de la cantidad de elementos que se pueden insertar
en ella, porque si usted tiene una colisión, eso está bien.
Sólo tienes que ir adelante y añadirlo al lo que vimos hace poco era
conocida como una lista enlazada.
>> Bueno hagamos una pausa por un momento.
¿Cuál es la probabilidad de una colisión en el primer lugar?
Bien, tal vez soy más de pensar, tal vez Yo soy más de la ingeniería de este problema,
porque ¿sabes qué?
Sí, puedo llegar a arbitraria ejemplos de la parte superior de mi cabeza, como
Allison y Aarón, pero en realidad, dada una distribución uniforme de
insumos, es decir algunas inserciones aleatorias en una estructura de datos, lo que realmente es
la probabilidad de una colisión?
Pues resulta que, en realidad es super alta.
Permítanme generalizar este problema es como este.
>> Así que en una habitación de estudiantes n CS50, lo que es la probabilidad de que al menos
dos estudiantes en la sala de tener la misma fecha de nacimiento?
Así que no hay de qué. algunos Hund -
200, 300 personas aquí y varios cientos de personas en el país hoy en día.
Así que si quería que nos preguntemos cuál es la probabilidad de que dos personas
en esta sala que tiene el mismo cumpleaños, podemos resolver esto.
Y yo pretendo en realidad hay dos las personas con el mismo cumpleaños.
>> Por ejemplo, ¿alguien tiene cumpleaños hoy?
Ayer?
¿Mañana?
Muy bien, así que se siente como que voy a tener que hacer esto 363 o así más
veces a la figura en realidad a cabo si tenemos una colisión.
O podríamos hacer esto matemáticamente en lugar de tediosamente
haciendo esto.
Y proponer lo siguiente.
>> Así que propongo que podríamos modelar el probabilidad de que dos personas tengan el
mismo día que la probabilidad de 1 menos la probabilidad de que nadie que tiene
el mismo cumpleaños.
Así que para conseguir esto, y esto es sólo el forma elegante de escribir esto, para el
primera persona en la habitación, él o ella puede tener uno cualquiera de los posibles
cumpleaños asumiendo 365 días en el año, con perdón de las personas con
el cumpleaños 29 de febrero.
>> Así que la primera persona en esta habitación es gratis para tener cualquier número de cumpleaños
de las 365 posibilidades para que que vamos a hacer que 365 dividido por 365,
que es uno.
La siguiente persona en la sala, si el objetivo es para evitar una colisión, sólo puede
tener su cumpleaños sobre cómo muchos días diferentes posibles?
364.
Así que el segundo término de esta expresión es esencialmente haciendo que las matemáticas para nosotros
restando fuera de una posible día.
Y a continuación, el día siguiente, el día siguiente, la día siguiente hasta el número total
de personas en la habitación.
>> Y si consideramos a continuación, ¿qué es, entonces, la probabilidad de que no todo el mundo tener
cumpleaños únicos, pero una vez más 1 menos que, lo que tenemos es una expresión
que puede muy caprichosamente tener este aspecto.
Pero es más interesante a ver visualmente.
Este es un gráfico donde en el eje x es el número de personas en la habitación, el
número de cumpleaños.
En el eje y es la probabilidad de una colisión, dos personas
que tiene el mismo cumpleaños.
>> Y la comida para llevar de esta curva es que tan pronto como se llega a gustar 40
estudiantes, que están haciendo en un 90% de probabilidad combinatorically de dos
personas o más tienen el mismo cumpleaños.
Y una vez que llegue a gustar 58 personas es casi el 100% de una ocasión los dos
personas en la habitación se va a tener la mismo día, a pesar de que no hay
365 o 366 posibles cubetas y sólo 58 personas en la sala.
Sólo estadísticamente es muy probable que obtener las colisiones, que en definitiva
motiva esta discusión.
Que incluso si conseguimos extravagancias, y empezar a tener estas cadenas, todavía estamos
va a tener colisiones.
>> Así que plantea la pregunta, ¿cuál es la costo de hacer inserciones y deleciones
en una estructura de datos como este?
Pues permítanme proponer -
y déjame volver a la pantalla durante aquí - si tenemos n elementos en el
lista, por lo que si estamos tratando de insertar n elementos, y tenemos
cuántos cubos total de?
Digamos 31 cubos en total en el caso de los cumpleaños.
¿Cuál es la longitud máxima de un de estas cadenas potencialmente?
>> Si de nuevo hay 31 posibles cumpleaños en un mes determinado.
Y sólo estamos aglutinación todos -
En realidad eso es un ejemplo tonto.
Vamos a hacer 26 en su lugar.
Así que si realmente tienen las personas cuyos nombres Comience con una Z a través, lo que da
nos 26 posibilidades.
Y estamos utilizando una estructura de datos como el que acabamos de ver, por lo que tenemos
una matriz de punteros, cada uno de los cuales apunta a una lista enlazada donde el
primera lista están todos con el nombre de Alice.
La segunda lista es cada con el Nombre que comienza con A, a partir
con B, y así sucesivamente.
>> ¿Cuál es la duración probable de cada una de esas listas si asumimos un bonito y limpio
distribución de los nombres de la A a la Z a través de toda la estructura de datos?
Hay n personas en la estructura de datos dividido por 26, si están bien
repartidas en el conjunto estructura de datos.
Así la longitud de cada uno de estos cadenas se n divididos por 26.
Pero en notación O grande, ¿qué es eso?
¿Qué es eso en realidad?
Así que no deja de ser n, ¿verdad?
Debido a que hemos dicho en el pasado, que Ugh se divide por 26.
Sí, en realidad es más rápido.
Pero en teoría, no es fundamentalmente todo lo que más rápido.
>> Así que no parece que sea todo lo que mucho más cerca de este santo grial.
De hecho, esto es sólo el tiempo lineal.
Heck, en este punto, ¿por qué no nos sólo tiene que utilizar una lista enlazada enorme?
Por qué no nos limitamos a usar una enorme matriz para almacenar los nombres de los
todos en la sala?
Bueno, ¿hay todavía algo convincente sobre una tabla hash?
¿Hay todavía algo convincente sobre una estructura de datos
que se parece a esto?
Este.
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Correcto, y otra vez si es sólo un algoritmo de tiempo lineal, y un
estructura de datos de tiempo lineal, ¿por qué no me simplemente almacenar el nombre de todos en una gran
matriz o en una lista enlazada grande?
Y dejar de hacer CS mucho más difícil de lo que debe ser?
¿Qué es convincente acerca de esto, incluso aunque me rasqué la saca?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Inserciones no lo son?
Caro ya.
Así inserciones potencialmente podría todavía ser constante de tiempo, incluso si los datos
estructura se parece a esto, una serie de punteros, cada uno de ellos está apuntando a
potencialmente una lista enlazada.
¿Cómo puedes lograr constante tiempo de inserción de los nombres?
Se adhieren en la parte delantera, la derecha?
>> Si sacrificamos un objetivo de diseño de antes, donde nos queríamos mantener
el nombre de todos, por ejemplo, clasificar, o la totalidad de los números en el escenario ordenados,
supongamos que tenemos un lista enlazada sin clasificar.
Sólo nos cuesta uno o dos pasos, como en el caso de Ben y Brian
anteriormente, para insertar un elemento en el principio de la lista.
Así que si no nos preocupamos acerca de la ordenación de todo de los nombres que empiecen con A o la totalidad
los nombres que comienzan con B, que todavía podemos lograr la inserción de tiempo constante.
Ahora, mirando hacia arriba Alice o Bob o cualquier nombre más en general sigue siendo qué?
Es grande O de n dividido por 26, en el caso ideal, donde todo el mundo está uniformemente
distribuida, donde hay tantos doctores ya que hay Z, que es probablemente
poco realista.
Pero eso sigue siendo lineal.
>> Pero aquí volvemos al punto ser notación asintótica de
teóricamente cierto.
Pero en el mundo real, si afirmo que mi programa puede hacer algo 26 veces
más rápido que el tuyo, cuyo programa vas a preferir el uso de?
La tuya o la mía, que es 26 veces más rápido?
Siendo realistas, la persona cuyo es 26 veces más rápido, incluso si teóricamente
nuestros algoritmos se ejecutan en el mismo tiempo de ejecución asintótica.
>> Permítanme proponer un diferente solución en conjunto.
Y si esto no sopla tu mente, estamos fuera de las estructuras de datos.
Así que este es un trie -
clase de nombre estúpido.
Viene de recuperaciones, y la palabra se escribe trie, t-r-i-e, a causa de
recuperación de golf suena como trie.
Pero esa es la historia de la palabra trie.
>> Así que un trie es de hecho una especie de árbol, y también es un juego de la palabra.
Y aunque usted no puede verlo del todo con esta visualización, un trie es un
árbol estructurado, como un árbol de la familia con un antepasado en la parte superior y un montón
de nietos y bisnietos como las hojas en la parte inferior.
Pero cada nodo en un trie es una matriz.
Y está en una matriz - y deje de simplificar demasiado por un momento - es una
matriz, en este caso, de tamaño 26, en donde cada nodo de nuevo es una matriz de tamaño
26, donde el elemento de orden cero en ese matriz representa A, y el último
elemento en cada uno de tales matriz representa Z.
>> Así que propongo, entonces, que estos datos estructura, conocida como un trie, puede ser
utilizado también para almacenar palabras.
Nos vimos hace un momento cómo podríamos almacenar palabras, o en este caso, los nombres y nosotros
Vimos anteriormente cómo podemos almacenar números, pero si nos centramos en los nombres o cadenas
aquí, darse cuenta de lo interesante.
Afirmo que el nombre es Maxwell en el interior de esta estructura de datos.
¿Dónde ve usted Maxwell?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: A la izquierda.
Así que lo que es interesante con estos datos estructura es más bien que tienda la
cadena M-A-X-W-E-L-L barra invertida cero, todo contigua, lo que en su lugar lo hace
está siguiendo.
Si este es un trie como estructura de datos, cada uno de cuyos nodos es de nuevo una matriz,
y desea almacenar Maxwell, primero índice y así nodo de la raíz, por lo que
a hablar, el primer nodo, en la posición M, la derecha, por lo que
más o menos en el centro.
Y luego, desde allí, se sigue un Puntero a una nodos secundarios, por así decirlo.
Así, en el sentido árbol genealógico, sigue hacia abajo.
Y que te llevan a otro nodo A la izquierda, que es
sólo otro array.
>> Y luego, si desea almacenar Maxwell, usted encuentra el puntero que representa
A, que es este de aquí.
Después de ir al siguiente nodo.
Y note - es por eso la imagen del un poco engañoso -
este nodo mirar minúsculo estupendo.
Pero a la derecha de ésta es Y y Z. Es que el autor ha truncado la
foto, así que en realidad ver las cosas.
De lo contrario, la imagen sería enormemente amplia.
Así que ahora usted índice en la ubicación X, a continuación, W, A continuación, E, entonces L, entonces L. Entonces cuál es
esta curiosidad?
>> Bueno, si estamos utilizando este tipo de nuevo asumir la forma de almacenar una cadena en un
estructura de datos, usted todavía tiene que esencialmente marcar en los datos
estructura que una palabra termina aquí.
En otras palabras, cada uno de estos nodos de alguna manera tiene que recordar que nosotros
de hecho seguido todos estos punteros y están dejando un poco
miga de pan en la parte inferior de esta aquí estructura para indicar M-A-X-W-E-L-L es
de hecho, en esta estructura de datos.
>> Así que podríamos hacerlo de la siguiente.
Cada uno de los nodos de la imagen que acabamos de sierra tiene una, una matriz de tamaño 27.
Y es ahora de 27 años, ya que en p establecido seis, haremos realidad le damos un apóstrofe,
para que podamos tener nombres como O'Reilly y otros con apóstrofes.
Pero la misma idea.
Cada uno de esos elementos en el array apunta a una estructura
nodo, por lo que sólo un nodo.
Así que esto es muy reminiscente de nuestra lista enlazada.
>> Y luego tengo un booleano, que lo voy a hacer palabra llamada, que sólo va a ser
cierto si una palabra termina en este nodo en el árbol.
Se representa efectivamente la pequeña triángulo que vimos hace un momento.
Así que si una palabra termina en ese nodo en el árbol, ese campo palabra será verdad,
que es conceptualmente marcando o estamos dibujando este triángulo, sí hay
es una palabra aquí.
>> Así que este es un trie.
Y ahora la pregunta es, ¿qué es su tiempo de ejecución?
¿Es grande O de n?
¿Es algo más?
Bueno, si usted tiene n los nombres de estos datos estructura, Maxwell es sólo uno de
ellos, lo que es el tiempo de ejecución de la inserción o la búsqueda de Maxwell?
¿Qué es el tiempo de ejecución de la inserción de Maxwell?
Si hay n otros nombres ya en la mesa?
¿Sí?
>> ESTUDIANTE: [inaudible].
>> ALTAVOZ 1: Sí, es la longitud del nombre, ¿verdad?
Así M-a-x-w-e-l-l así que se siente como esto algoritmo es O grande de siete.
Ahora, por supuesto, el nombre variará en longitud.
Tal vez es un nombre corto.
Tal vez sea un nombre más largo.
Pero lo que es clave aquí es que es un número constante.
Y tal vez en realidad no es constante, Pero Dios, si de manera realista, en un
diccionario, es probable que haya algún límite en el número de cartas en un
nombre de la persona en un país determinado.
>> Y por lo que podemos asumir que valor es una constante.
No sé lo que es.
Es probable que sea más grande que creemos que es.
Porque siempre hay algún rincón Caso con un nombre largo loco.
Así que vamos a llamarlo k, pero sigue siendo un constante, presumiblemente, debido a que cada
nombre en el mundo, al menos en un país en particular, es que la longitud o
más corto, por lo que es constante.
Pero cuando hemos dicho algo es grande O de un valor constante, lo que hay que
realmente equivalente a?
Eso es realmente la misma cosa diciendo que la constante de tiempo.
>> Ahora estamos como hacer trampa, ¿no?
Estamos como el aprovechamiento de alguna teoría aquí para decir que así, el orden de k es
Para realmente sólo de uno, y es hora de constante.
Pero lo que realmente es.
Porque la idea clave aquí es que si tenemos n nombres ya en este
estructura de datos, y la insertamos Maxwell, es la cantidad de tiempo que nos lleva a
inserte Maxwell en absoluto afectada por la cantidad de otras personas
se encuentran en la estructura de datos?
No parece ser.
Si tuviera un billón más elementos a esta trie, y luego insertar Maxwell, es
que en absoluto afectada?
No.
Y eso es a diferencia de cualquiera de los datos de días estructuras que hemos visto hasta ahora, donde
el tiempo de funcionamiento de su algoritmo es completamente independiente de la cantidad
material es o no es ya en esa estructura de datos.
>> Y así, con esto le produce ahora es una oportunidad para p conjunto de seis, que se
nuevo implicar la implementación de su propia corrector ortográfico, la lectura en 150.000
Es decir, la mejor manera de almacenar esa no es necesariamente evidente.
Y aunque he aspirado a encontrar el santo grial, yo no
afirman que un trie es.
De hecho, una tabla hash puede muy bien llegar a ser mucho más eficiente.
Pero esos son sólo -
eso es sólo una de las decisiones de diseño usted tendrá que hacer.
>> Pero en el cierre vamos a echar 50 o así segundos para echar un vistazo a lo que las mentiras
con antelación la próxima semana y más allá de la transición que de esta línea de comandos
mundo si los programas en C para cosas web basado y lenguajes como PHP y
JavaScript y la propia Internet, protocolos como HTTP, que tienes
se da por sentado por años ahora, y escrito la mayoría de cada
día, tal vez, o visto.
Y vamos a empezar a pelar la capas de lo que es el Internet.
¿Y cuál es el código que subyace en las herramientas actuales.
Así que 50 segundos de este teaser aquí.
Te doy Guerreros de la red.
>> [REPRODUCCIÓN DE VÍDEO]
>> -Él vino con un mensaje.
Con un protocolo propio.
Él vino a un mundo de los servidores de seguridad crueles, routers indiferentes y peligros lejos
peor que la muerte.
Es rápido.
Es fuerte.
Es TCPIP.
Y tiene su dirección.
Warriors of the Net.
>> [VIDEO PLAYBACK FIN]
>> ALTAVOZ 1: Eso es cómo el Internet trabajará a partir de la próxima semana.