[REPRODUCCIÓN DE MÚSICA]
>> DAVID MALAN: Este es CS50.
Y esto es a la vez el principio y el end-- como literally-- casi el final
de la semana seis.
>> Yo pensé en compartir un poco de un hecho divertido.
He tirado esto desde un conjunto de datos del semestre pasado.
Usted puede recordar que le pedimos en cada forma conjunto p si has visto en línea
o si usted ha asistido en persona.
Y aquí están los datos.
Así que estaba muy predecible hoy.
Pero nosotros queríamos pasar un poco de tiempo con usted, no obstante.
¿Alguien quiere conjeturar por qué esto gráfico es tan jaggy, arriba abajo, arriba abajo,
tan consistentemente?
Qué hacer cada uno de los picos y depresiones representan?
>> AUDIENCIA: [inaudible]
DAVID MALAN: En efecto.
Y más divertida, Dios no lo quiera, tenemos una conferencia en un viernes
al inicio del semestre, eso es lo que suceda.
Así que hoy, participamos en un poco Más información sobre las estructuras de datos.
Y para darle más de un sólido modelo mental de los problemas a las cinco,
que ahora está fuera.
Errores de ortografía, en el que, vamos a que entregar un archivo de texto unos 100.000
además de las palabras en inglés, y usted va a tener
para encontrar la manera de cargar ellos inteligentemente en la memoria, en la memoria RAM, el uso de algunos datos
estructura de su elección.
>> Ahora bien, una estructura de este tipo de datos podría ser, pero probablemente no debería ser,
la lista enlazada bastante simplista, que se introdujo la última vez.
Y una lista enlazada tenía por lo menos una ventaja sobre una matriz.
¿Cuál es una de las ventajas de una lista enlazada discutible?
>> AUDIENCIA: Inserción.
>> DAVID MALAN: Inserción.
¿Qué quieres decir con eso?
>> AUDIENCIA: En cualquier lugar a lo largo de la lista de [inaudible].
>> DAVID MALAN: Good.
Así que usted puede insertar un elemento siempre que sea que quieres en la mitad de la lista
sin tener que mezclar nada, que llegamos a la conclusión, en nuestra clasificación
discusiones, no es necesariamente una buena cosa,
porque se necesita tiempo para moverse en realidad todos esos seres humanos hacia la izquierda o derecha.
Y así, con una lista enlazada, puede simplemente asignar con malloc, un nuevo nodo,
y luego actualizar un par de pointers-- dos, tres operaciones max--
y somos capaces de ranura alguien en cualquier lugar en una lista.
>> ¿Qué otra cosa era ventajoso acerca de una lista enlazada?
¿Sí?
>> AUDIENCIA: [inaudible]
DAVID MALAN: Perfecto.
Perfect.
Es muy dinámico.
Y eso que no estás cometiendo, de antemano, hasta cierto tamaño fijo
trozo de memoria, al igual que usted tendría a con una matriz, el alza de los cuales
es que se puede asignar nodos sólo en la demanda de este modo utilizando sólo la cantidad de espacio
como que realmente necesita.
A diferencia de una matriz, que te pueden asignar accidentalmente demasiado poco.
Y entonces sólo va a ser un dolor en el cuello
reasignar una nueva matriz más grande, copiar todo lo más, liberar la matriz de edad,
y luego pasar sobre su negocio.
O peor aún, es posible asignar de manera más memoria de la que realmente se necesita,
y por lo que vamos a tener un muy matriz escasamente pobladas, por así decirlo.
>> Así que una lista enlazada que da a estos ventajas de dinamismo y flexibilidad
con inserciones y deleciones.
Pero sin duda que debe haber un precio que se paga.
De hecho, uno de los temas explorado en concurso cero
era un par de las compensaciones que hemos visto hasta el momento.
Así que lo que es un precio pagado o por un la baja de una lista enlazada?
Sí.
>> AUDIENCIA: No hay acceso aleatorio.
>> DAVID MALAN: No hay acceso aleatorio.
Pero a quién le importa?
Acceso aleatorio no suena convincente.
>> AUDIENCIA: [inaudible]
DAVID MALAN: Exactamente.
Si usted quiere tener un cierto algorithm--
y que me haga realidad propongo búsqueda binaria, en particular, que
es uno que hemos utilizado bastante bit-- si usted no tiene acceso al azar,
no se puede hacer así de simple aritmética de encontrar como el elemento medio
y saltar a la derecha a la misma.
En su lugar, tiene que empezar por el primero elemento y linealmente buscar desde la izquierda
a derecha si quieres encontrar el medio o cualquier otro elemento.
>> AUDIENCIA: Probablemente tiene más memoria.
>> DAVID MALAN: Toma más memoria.
¿Dónde está ese adicional coste que viene de en la memoria?
>> AUDIENCIA: [inaudible]
DAVID MALAN: Exactamente.
En este caso aquí, tuvimos una lista enlazada para enteros,
y sin embargo, estamos duplicando la cantidad de memoria
necesitamos también por el almacenamiento de estos punteros.
Ahora menos de un gran problema ya sus estructuras se hacen más grandes
y usted está almacenando no es un número, pero tal vez un estudiante o algún otro objeto.
Pero el punto sigue siendo duda.
Y por lo que un número de las operaciones en listas enlazadas fueron llamados
eran grandes O de n-- lineal.
Cosas como la inserción o búsqueda o eliminación en caso de un elemento
pasó a ser al final de la lista si está ordenada o no.
>> A veces puede que tengas suerte y en fuera de modo más bajos en estas operaciones
También podría ser la constante de tiempo si estás siempre mirando al primer elemento,
por ejemplo.
Pero en última instancia, nos prometimos para lograr el santo grial
de estructuras de datos, o algunos de los mismos aproximación,
por medio de la constante de tiempo.
¿Podemos encontrar elementos o añadir elementos o eliminar elementos de una lista?
Nos veremos muy pronto.
Y resulta que uno de los mecanismos que estamos
va a empezar a utilizar hoy en día, el uso anual de P puesto cinco,
en realidad es bastante familiar.
Por ejemplo, si se trata de un montón de libros de examen, cada uno de los cuales
tiene un estudiante de primero nombre y apellido en él,
y yo los recojo de la al final de un examen,
y son todos bastante tanto en un orden aleatorio,
y queremos ir sobre la clasificación estos exámenes para que una vez clasificadas
es sólo mucho más fácil y más rápido a entregarlos de vuelta
a los estudiantes en orden alfabético.
¿Cuáles serían sus instintos para una pila de exámenes de este tipo?
>> Bueno, si eres como yo, podría ver que este es m,
así que me voy a poner esto en una especie de, si este es mi mesa o mi piso donde
Estoy extendiendo cosas fuera-- o mi arsenal realmente--
Yo podría poner toda la Sra allí.
Oh.
He aquí una A. Así que podría Como poner los de aquí.
Oh.
Aquí hay otra A. Voy poner que aquí.
Aquí hay una Z. Aquí hay otro M. Y así Yo podría empezar a hacer montones como este.
Y entonces tal vez me gustaría ir en adelante y una especie de muy quisquillosa-ly especie
las pilas individuales.
Pero el punto es, buscaría en la entrada que estoy sola mano
y me gustaría hacer algunos calculé decisión basada en esa entrada.
Si comienza con A, lo puso allí.
Si empieza por Z, lo puso sobre allí, y todo lo demás.
>> Así que esta es una técnica que es generalmente conocido como hashing-- H-A-S-H-
que por lo general significa tomar como de entrada y utilizar esa entrada para calcular
un valor, en general, un número, y que número es el índice en un almacenamiento
contenedor, como una matriz.
Así que en otras palabras, que podría tener una función hash, como lo hago en mi cabeza,
que si veo a alguien es nombre que comienza con A,
Voy a asignar que a cero en mi cabeza.
Y si veo a alguien con Z, estoy ir al mapa que a 25 en mi cabeza
y luego poner esto en la última pila más.
>> Ahora, si lo piensas, no mi cerebro pero un programa en C, lo que los números podrían
usted confía en lograr el mismo resultado?
En otras palabras, si tenía el carácter ASCII A,
¿cómo determinar lo balde para poner en?
Es probable que no quiere lo puso en el cubo 65, que
sería como de allá sin una buena razón.
¿Dónde quieres poner un en términos de su valor ASCII?
¿Dónde quieres que hacer para su ASCII valor para llegar a un cubo inteligente
para poner en?
>> AUDIENCIA: Minus A.
>> DAVID MALAN: Sí.
Así menos A o menos específicamente 65 si es
un capital de A. O 98 si se trata de una minúscula.
Y por lo que nos permitiría, muy simplemente y muy aritméticamente,
poner algo en un cubo así.
Así que resulta que en realidad hacemos esto también incluso con los concursos.
>> Así que usted puede recordar que marcaste tu Nombre de la enseñanza de su compañero en la portada.
Y se organizaron nombres del TF en estas columnas en orden alfabético,
Bueno, lo creas o no, cuando todo 80 más de nosotros
se reunieron la otra noche a grado, el último paso en nuestro proceso de clasificación
es para discutir las pruebas en un gran espacio de suelo en la [inaudible]
y sentar pruebas de todo el mundo a exactamente en el orden de sus de TF
nombres en la cubierta, ya que entonces es mucho más fácil para nosotros
para buscar a través de que el uso lineal buscar o algún tipo de inteligencia
para un TF para encontrar su o pruebas de sus estudiantes.
>> Así que esta idea de hash que verás es
bastante poderoso es en realidad bastante lugar común y muy intuitiva,
al igual que quizás dividir y conquista fue en la semana cero.
Me avance rápido para el hackathon un par de años atrás.
Este fue Zamyla y un par de otros estudiantes de felicitación personal
como entraron.
Y tuvimos un montón de plegado mesas allí con etiquetas de nombre.
Y habíamos organizado las etiquetas de nombre con como el As de allá
y la Zs allá.
Y así uno de los TFS muy inteligentemente escribió esto como las instrucciones
para el día.
Y en la semana 12 del semestre este todo tenía sentido perfecto y todo el mundo
sabía qué hacer.
Pero en cualquier momento que tienes en cola de la misma manera,
está implementando la misma noción de un hash.
Así que vamos a formalizar un poco.
Aquí es una matriz.
Se señaló a ser un poco amplia acaba de describir, visualmente,
que podríamos poner cadenas en algo como esto.
Y esta matriz es claramente de tamaño 26 total.
Y la cosa se llama mesa arbitrariamente.
Pero esto es sólo una representación artística de lo que podría ser una tabla hash.
>> Así que una tabla hash ahora va a ser una estructura de datos de nivel superior.
Al final del día estamos a punto de ver que usted
puede aplicar una tabla hash, que es muy similar a la línea de check-in
en un hackathon mucho como este tabla utilizada para la clasificación de los libros de examen.
Pero una tabla hash es especie de este alto nivel
concepto que podría utilizar una matriz debajo del capó para implementarlo,
o puede utilizar una lista de longitud, o incluso tal vez algunas otras estructuras de datos.
Y eso sí que es la toma theme-- algunos de estos ingredientes fundamentales
como una matriz y este edificio bloquear ahora una lista de longitud
y ver qué más podemos construir en la parte superior de los que, como ingredientes
en una receta, lo que hace más y más los resultados finales interesantes y útiles.
>> Así que con la tabla hash podríamos implementarlo
en la memoria pictóricamente como este, pero cómo podría en realidad ser codificada para arriba?
Bueno, tal vez la forma más sencilla es esta.
Si la capacidad en todas las tapas, es sólo algunos constant-- por ejemplo 26,
para 26 letras del alphabet-- Yo podría llamar a mi tabla de variables,
y yo podría decir que me voy a poner estrellas Char allí, o una cadena.
Así que es tan simple como esto si desee implementar una tabla hash.
Y, sin embargo, esto es en realidad una matriz.
Pero, de nuevo, un hash tabla es ahora lo que vamos a
llamar a un tipo de datos abstracto que sólo una especie de estratificación conceptual en la parte superior
de algo más mundano ahora como un array.
>> Ahora, ¿cómo hacemos para sobre la resolución de problemas?
Bueno, antes tuve el lujo de tener suficiente espacio de tabla aquí
para que yo pudiera poner el concursos en cualquier lugar que quería.
De manera que se puede ir aquí.
Zs pueden ir aquí.
Sra podría ir aquí.
Y luego tuve un poco de espacio extra.
Pero esto es un poco de un derecho de trucos ahora porque esta tabla, si realmente
pensado en ello como una matriz, es justo va a ser de algún tamaño fijo.
>> Así que técnicamente, si me tire hasta prueba de otro estudiante
y ver, oh, esta persona de nombre comienza con una A también,
Yo como que quiero poner ahí.
Pero tan pronto como me puse allí, si esta tabla de hecho representa una matriz,
Yo voy a estar anulando o clobbering quienquiera concurso de este estudiante es.
Derecha?
Si se trata de una matriz, sólo una cosa puede ir en cada una de estas células o elementos.
Y así que tipo de tener a escoger y elegir.
>> Ahora antes que tipo de engañado e hizo esto o yo
sólo tipo de apilado ellos uno encima del otro.
Pero eso no va a volar en código.
Entonces, ¿dónde podría yo poner el segundo estudiante cuyo nombre
Una es si todo lo que tenía es este espacio de tablas disponibles?
Y yo he usado tres ranuras y se parece que hay sólo unos pocos otros.
¿Qué podría hacer?
AUDIENCIA: [inaudible]
DAVID MALAN: Sí.
Tal vez vamos a mantenerlo simple.
Derecha?
No se ajusta a donde quiero ponerlo.
Así que me voy a poner técnicamente, donde un B iría.
Ahora, por supuesto, estoy empezando para pintar a mí mismo en una esquina.
Si llego a un estudiante cuyo nombre es en realidad B,
ahora B va a ser movido un poco hacia adelante, como podría suceder, sí,
si esto es un B, ahora tiene que ir aquí.
>> Y por lo que este muy rápidamente podría convertirse en un problema,
pero es una técnica que en realidad se conoce como sondeo lineal,
por el que usted sólo considera su matriz a ser a lo largo de la línea.
Y que acaba de tipo de sonda o inspeccionar cada elemento disponible
en busca de un lugar disponible.
Y tan pronto como se entere uno, se te cae en ese país.
>> Ahora, el precio que se paga ahora para esta solución es lo que?
Tenemos una matriz de tamaño fijo, y cuando inserto nombres
en ella, al menos al principio, lo que es el tiempo de ejecución de la inserción
para poner a los estudiantes concursos en los cubos de la derecha?
Big O de qué?
>> AUDIENCIA: n.
DAVID MALAN: Escuché gran O de n.
No es cierto.
Pero vamos a desmenuzar ¿por qué en un momento.
¿Qué otra cosa podría ser?
>> AUDIENCIA: [inaudible]
DAVID MALAN: Y me dejó hacer visualmente.
Así que supongamos que esta es la letra S.
>> AUDIENCIA: Es uno.
DAVID MALAN: Es uno.
Derecha?
Esta es una matriz, que significa que tenemos acceso aleatorio.
Y si pensamos en esto como cero y esto como 25,
y nos damos cuenta de que, oh, aquí está mi entrada S,
Ciertamente puedo convertir S, un carácter ASCII,
a un número correspondiente entre cero y 25
y luego inmediatamente puso donde pertenece.
>> Pero, por supuesto, tan pronto como llegue a la segunda persona cuyo nombre es A o B o C
finalmente, si yo he usado el sondeo lineal como mi solución,
el tiempo de ejecución de inserción en el peor de los casos
que realmente se va a delegar en qué?
Y yo lo escuché aquí correctamente desde el principio.
AUDIENCIA: [inaudible]
DAVID MALAN: Por lo que es de hecho una vez n usted tiene un conjunto de datos suficientemente grande.
Así, por un lado, si su matriz es suficientemente grande
y sus datos son escasos suficiente, conseguir este hermoso tiempo constante.
Pero tan pronto como empiece cada vez más y más elementos,
y sólo estadísticamente se obtiene más personas con la letra
A como su nombre o la letra B, podría potencialmente
delegar en algo más lineal.
Así que no es perfecto.
Así que podríamos hacer mejor?
>> Bueno, lo que fue nuestra solución antes cuando nos
quieren tener más dinamismo que algo así como una gran variedad permitido?
AUDIENCIA: [inaudible]
DAVID MALAN: ¿Qué hemos presentamos?
Sí.
Así que una lista enlazada.
Bueno, vamos a ver que es lo vinculado lista podría hacer por nosotros en su lugar.
Bueno, déjame propongo que dibujar la imagen de la siguiente manera.
Ahora bien, este es un diferente imagen de un ejemplo
a partir de un texto diferente, en realidad, que es en realidad el uso de una matriz de tamaño 31.
Y este autor simplemente decidido hash de cadenas
no se basa en los nombres de la persona, pero en función de sus fechas de nacimiento.
Independientemente del mes, se dieron cuenta si lo que se nace en el primero de un mes
o el 31 de un mes, el autor se hash basado en ese valor,
a fin de difundir los nombres un poco más que 26 puntos podrían permitir.
Y tal vez es un poco más uniforme que ir con las letras del alfabeto,
porque, por supuesto, es probable que haya más personas en el mundo con nombres
que comienzan con una que sin duda algunas otras letras del alfabeto.
Así que tal vez esto es un poco más uniforme, suponiendo
una distribución uniforme de los bebés a través de un mes.
>> Pero, por supuesto, esto es todavía imperfecto.
Derecha?
Vamos a tener colisiones.
Varias personas en este estructura de datos son todavía
que tiene la misma fecha de nacimiento, al menos, eres independientemente de mes.
Pero lo que ha hecho el autor?
Bueno, parece que tenemos una matriz en el lado izquierdo dibujado verticalmente,
pero eso es sólo una representación artística.
No importa qué dirección dibujar una matriz, que sigue siendo una matriz.
¿Qué es este un arreglo de parecer?
>> AUDIENCIA: lista Vinculado.
>> DAVID MALAN: Sí.
Parece que se trata de una gama de lista enlazada.
Así que de nuevo, a este punto de la clase de la utilización de estas estructuras de datos ahora
como ingredientes a más soluciones interesantes,
usted puede tomar absolutamente un fundamental, como una matriz,
y luego tomar algo más interesante como una lista enlazada
e incluso combinar en una aún más interesante estructura de datos.
Y, de hecho, esto también haría ser llamado una tabla hash,
por lo que la matriz es realmente la tabla hash,
pero que la tabla hash tiene cadenas, por así decirlo,
que puede crecer o disminuir en base a la número de elementos que desea insertar.
>> Ahora, en consecuencia, lo que hay el tiempo de ejecución ahora?
Si quiero insertar alguien cuyo cumpleaños es el 31 de octubre
¿de dónde viene él o ella?
Bien.
En la parte inferior, donde dice 31.
Y eso es perfecto.
Esa fue la constante de tiempo.
Pero, ¿y si nos encontramos con alguien más cuyo cumpleaños es, vamos a ver,
Octubre, Noviembre, 31 de Diciembre?
¿Dónde está él o ella va a ir?
La misma cosa.
Dos paso sin embargo.
Eso es constante, aunque no es así?
Bien.
En el momento que es.
Pero en el caso general, más la gente que añadimos,
probabilísticamente, vamos para conseguir más y más colisiones.
>> Ahora bien, esto es un poco mejor porque técnicamente
ahora mis cadenas podrían estar en el peor de los casos ¿hasta cuándo?
Si introduzco n personas en este más estructura de datos sofisticado, n personas,
en el peor de los casos va a ser n.
¿Por qué?
>> AUDIENCIA: Porque si todo el mundo tiene el mismo cumpleaños,
que van a ser una línea.
DAVID MALAN: Perfecto.
Puede ser que sea un poco artificiosa, pero realmente en el peor de los casos,
si todo el mundo tiene el mismo cumpleaños, teniendo en cuenta las entradas que tiene,
usted va a tener un cadena masivamente largo.
Y así, se podría llamar un la tabla de hash, pero en realidad es
sólo una lista masiva vinculada con una gran cantidad de espacio desperdiciado.
Pero en general, si suponemos que al menos los cumpleaños son uniform--
y probablemente no lo es.
Estoy haciendo eso.
Pero si asumimos, para aras de la discusión
que son, a continuación, en teoría, si Esta es la representación vertical,
de la matriz, bueno, entonces espero que estés va a poner las cadenas que son, ya sabes,
más o menos la misma longitud que cada uno de éstos representa un día del mes.
>> Ahora bien, si hay 31 días en el mes, eso significa que mi tiempo de funcionamiento realmente
es gran O de n más de 31, que se siente mejor que lineal.
Pero lo que era uno de los nuestros compromisos de un par de semanas
hace cada vez que se trataba de expresar el tiempo de ejecución de un algoritmo?
Así que busque sólo en el término de orden superior.
Derecha?
31 es definitivamente útil.
Pero esto sigue siendo gran O de n.
Pero uno de los temas del problema establece cinco
va a ser de reconocer que absolutamente,
asintóticamente, teóricamente esta estructura de datos
no es mejor que sólo una enorme lista enlazada.
Y, en efecto, en el peor de los casos, este tabla hash podría recaer en eso.
>> Pero en el mundo real, con nosotros los seres humanos que los propios Macs o PCs o lo que sea
y se están ejecutando mundo real software en los datos del mundo real,
qué algoritmo se va a preferir?
El que toma las medidas finales o la uno que toma n dividido por 31 pasos
encontrar algún dato o para buscar un poco de información?
Quiero decir, absolutamente las 31 marcas una diferencia en el mundo real.
Es 31 veces más rápido.
Y nosotros, los humanos son sin duda va a apreciar eso.
>> Así que darse cuenta de la dicotomía allí entre realidad
hablando de cosas teóricamente y asintóticamente que definitivamente
tiene valor como hemos visto, pero en el mundo real,
si usted se preocupa sólo hacer la feliz humano para las entradas generales,
usted puede muy bien querer aceptar el hecho de que, sí, esta es lineal,
pero es 31 veces más rápido que puede ser lineal.
Y mejor aún, nosotros no sólo tenemos que hacer algo arbitrario como una fecha de nacimiento,
podríamos pasar un poco más tiempo y la inteligencia
y pensar en lo que podríamos hacer, dado el nombre de una persona y tal vez
su fecha de nacimiento para combinar los ingredientes para averiguar algo
que es verdaderamente más uniforme y menos jaggy,
por decirlo de esta imagen Actualmente sugiere que podría ser.
¿Cómo podríamos aplicar esto en código?
Bueno, déjame propongo que simplemente pedir prestado algo de sintaxis que hemos
utilizado un par de veces hasta ahora.
Y yo voy a definir un nodo, que de nuevo
es un término genérico para sólo algunas recipiente para algún tipo de estructura de datos.
Voy a proponer que una cadena va allí.
Pero vamos a empezar a tomar las ruedas de entrenamiento de hoy.
>> No más biblioteca CS50 realmente, a menos que quiera
para utilizarlo para su definitiva proyecto, que está bien,
pero ahora vamos a tirar de la cortina y dicen que es sólo una estrella de carbón.
Así que la palabra no va a ser nombre de la persona en cuestión.
Y ahora tengo un vínculo aquí para el siguiente nodo
de modo que éstos representan cada uno de los nodos
en la cadena, potencialmente, de una lista enlazada.
>> Y ahora qué hago Declaro la tabla hash en sí?
¿Cómo declaro toda esta estructura?
Bueno, en realidad, al igual que yo usé un puntero a sólo el primer elemento de una lista
antes, de manera similar puedo decir simplemente Sólo necesito un montón de punteros
para implementar esta tabla hash entero.
Voy a tener una matriz llamada tabla para la tabla hash.
Va a tener la capacidad de tamaño.
Esa es la cantidad de elementos puede caber en ella.
Y cada uno de esos elementos en este matriz va a ser una estrella de nodo.
¿Por qué?
Bueno, por esta imagen, de lo que soy la aplicación de la tabla hash como
eficazmente en el principio es sólo esta matriz que hemos dibujado verticalmente,
cada uno de cuyos cuadrados representa un puntero.
Que los que tienen barras a través de ellos son simplemente nulo.
Y los que tienen flechas que van hacia la derecha
son punteros a nodos reales reales, ergo el comienzo de una lista enlazada.
>> Así que aquí, entonces, es cómo podemos implementar una tabla hash que
implementa encadenamiento separado.
Ahora podemos hacer mejor?
Muy bien me prometió la última vez que podríamos alcanzar constante de tiempo.
Y Yo como que te di constante de tiempo aquí,
pero entonces no dicho realmente constante de tiempo porque todavía
dependiente sobre el total número de elementos
que está introduciendo en la estructura de datos.
Pero supongamos que hicimos esto.
Permítanme volver a la pantalla por aquí.
Permítanme también este proyecto aquí, claro la pantalla, y supongamos que hice esto.
Supongamos que yo quería para insertar el nombre Daven en en mi estructura de datos.
>> Así que quiero insertar una cadena Daven en la estructura de datos.
¿Qué pasa si yo no uso un la tabla de hash, pero yo uso
algo que es más árbol-como como un árbol de la familia, donde
usted tiene alguna raíz en el superior y luego nodos y hojas
que van hacia abajo y hacia afuera.
Supongamos entonces, que yo que desee insertar Daven de
en lo que es actualmente una lista vacía.
Yo voy a hacer lo siguiente: yo soy va a crear un nodo en esta familia
estructura de datos como árbol que se parece un poco como esta, cada uno de los cuales
rectángulos ha, digamos, por el momento 26 elementos en los mismos.
Y cada una de las células en esta matriz que está pasando
para representar la letra de un alfabeto.
>> En concreto, voy a tratar este es A, luego B, luego C, luego D,
este de aquí.
Así que esto va a con eficacia representar la letra D.
Pero para insertar todos Daven de nombro tengo que hacer un poco más.
Así que estoy en primer lugar va a hachís, por así decirlo.
Voy a mirar a la primera letra en Daven de que es, obviamente, un D,
y yo voy a asignar un nodo que mira
así- un gran rectángulo grande suficiente para adaptarse a todo el alfabeto.
>> Ahora D se realiza.
Ahora A. D-A-V-E-N es la meta.
Así que ahora lo que voy a hacer es esto.
Tan pronto como empecé aviso D no hay puntero allí.
Es valores de basura en el momento, o podría inicializarlo a null.
Pero déjame seguir adelante con esta idea de construir un árbol.
Permítanme asigno otro de estos nodos que cuenta con 26 elementos en los mismos.
>> ¿Y sabes qué?
Si esto es sólo un nodo en la memoria que He creado con malloc, utilizando una estructura
como pronto veremos, Yo voy a hacer esto--
Voy a dibujar una flecha de lo que representó D abajo
a este nuevo nodo.
Y ahora, primero la siguiente carta en nombre de Daven,
V-- D-A-V-- voy a seguir adelante y dibujar otro nodo de este tipo,
mediante el cual, los elementos de V, que aquí vamos a sortear gritos instance--.
No vamos a dibujar allí.
Se va a ir aquí.
>> A continuación, vamos a considera que se trata de V.
Y entonces aquí vamos a índice por debajo de V en lo que vamos a considerar E.
Y a continuación, a partir de aquí vamos a ir tener uno de estos nodos aquí.
Y ahora tenemos una pregunta para contestar.
Necesito alguna manera indicar que estamos en el final de la cadena Daven.
Así que podría dejarlo nulo.
>> Pero lo que si tenemos Daven de nombre completo también, que
es, como hemos dicho, Davenport?
¿Y qué si es Daven en realidad una subcadena,
un prefijo de una cadena mucho más tiempo?
No podemos permanentemente decir nada va
ir allí, porque podíamos Nunca inserte una palabra como Davenport
en esta estructura de datos
>> Entonces, ¿qué podríamos hacer en su lugar es tratar cada uno de estos elementos
como tal vez tener dos elementos dentro de ellos.
Uno de ellos es un puntero, de hecho, como que he estado haciendo.
Así que cada una de estas cajas No es sólo una célula.
Pero ¿y si la parte superior uno-- de la parte inferior
va a ser nulo, porque no hay Davenport por el momento.
¿Qué pasa si el de arriba es algún valor especial?
Y va a ser un poco difícil de dibujar este tamaño.
Pero supongo que es sólo una marca de verificación.
Compruebe.
D-A-E-V-N es una cadena en esta estructura de datos.
>> Mientras tanto, si tuviera más espacio aquí, lo que podía hacer P-O-R-T,
y yo podría poner cheque en el nodo que tiene la letra T al final.
Así que esta es una forma masiva complejo de aspecto de estructura de datos.
Y mi puño y letra ciertamente no ayuda.
Pero si quería insertar algo más, consideramos lo que haríamos.
Si quisiéramos poner en David, nos gustaría seguir la misma lógica, D-A-V,
pero ahora me gustaría señalar en la próxima elemento no desde E, pero de I a D.
Así que va a ser más nodos de este árbol.
Vamos a tener la llamada malloc más.
Pero yo no quiero hacer una completo desastre de esta imagen.
Así que vamos a ver un lugar que ha sido pre-formulado
como este con no punto, punto, puntos, pero sólo arrays abreviada.
Pero cada uno de los nodos en este árbol aquí
representa la misma cosa-- una matriz Rayo de tamaño 26.
>> O si queremos ser ahora realmente adecuada, lo que
si el nombre de alguien como un apóstrofe, vamos a
asumir que cada nodo tiene en realidad como 27 índices en ella, no sólo 26.
Así que esto ahora va a ser un dato estructura llamada trie-- T-R-I-E.
Un trie, que es supuestamente históricamente un nombre inteligente para un árbol
que se optimiza para recuperación, que por supuesto,
se escribe con un I-E por lo que es trie.
Pero esa es la historia de la trie.
>> Así que un trie es estos datos en forma de árbol estructura como un árbol genealógico
que en última instancia se comporta de esa manera.
Y aquí es sólo otro ejemplo de un toda montón de nombres de otras personas.
Pero la pregunta ahora a la mano es lo que tiene
hemos ganado introduciendo posiblemente una más complicada estructura de datos, y uno,
francamente, que utiliza una gran cantidad de memoria.
>> Porque a pesar de que, en este momento, estoy solo
usando D's puntero y A y V y Es y Ns,
Me estoy perdiendo una diablos de gran cantidad de memoria.
Pero donde paso un recurso, Tiendo a no recuperar otro.
Así que si estoy gastando más espacio, lo que es probablemente la esperanza?
Que estoy gastando menos qué?
AUDIENCIA: Menos tiempo.
DAVID MALAN: Tiempo.
Ahora ¿por qué podría ser?
Bueno, ¿cuál es la inserción tiempo, en términos de gran O ahora,
de un nombre como Daven o Davenport o David?
Bueno, Daven era cinco pasos.
Davenport sería nueve pasos, por lo que sería un poco más pasos.
David sería cinco pasos también.
Así que estos son de hormigón números, pero seguro que hay
un límite superior en el longitud del nombre de alguien.
Y, en efecto, en el problema grupos de cinco especificación,
vamos a proponer que es algo
eso es 40 caracteres y tantos.
>> Siendo realistas, nadie tiene un nombre infinitamente largo,
que es decir que la longitud de una nombre o la longitud de una cadena que pueden
tener cierta el estado de estructura es discutible qué?
Es constante.
Derecha?
Puede ser que sea una gran constante como 40 y tantos años, pero es constante.
Y no tiene dependencia de la cantidad de otros nombres pertenecen a esta estructura de datos.
En otras palabras, si querido insertar ahora
Colton o Gabriel o Rob o Zamyla o Alison o Belinda o cualquier otro nombre
desde el personal en estos datos estructura, es el tiempo de ejecución
de insertar otros nombres va a ser en absoluto afectado
por la forma en muchos otros elementos son en la estructura de datos ya?
Que no es.
Derecha?
Debido a que estamos usando de manera efectiva esta tabla hash multi-capa.
Y el tiempo de ejecución de cualquiera de estas operaciones
depende no del número de elementos que están en la estructura de datos
o que se va con el tiempo para estar en la estructura de datos,
pero en la longitud de lo que específicamente?
>> La cadena ser insertado, lo que lo hace hacer
este asintóticamente constante gran O tiempo-- de uno.
Y, francamente, sólo en el mundo real, este
significa insertar el nombre de Daven toma como cinco pasos, o Davenport nueve
David pasos, o cinco pasos.
Eso es bastante maldito pequeños tiempos de funcionamiento.
Y, de hecho, esa es una muy buena cosa, especialmente cuando
no es dependiente sobre el total número de elementos de allí.
Entonces, ¿cómo podríamos aplicar esta tipo de estructura en el código?
Es un poco más complejo, pero aún así es
sólo una aplicación de bloques de construcción básicos.
Voy a redefinir nos nodo como sigue:
bool llamada palabra-- y esto que podría llamarse cualquier cosa.
Pero el bool representa lo dibujé como una marca de verificación.
Sí.
Este es el final de una cadena en esta estructura de datos.
>> Y, por supuesto, la estrella nodo no se está refiriendo a los niños.
Y, de hecho, al igual que un árbol de la familia, usted
consideraría los nodos que están colgando de
de la parte inferior de algunos de los padres elemento para ser niños.
Y para que los niños se van a ser una matriz de 27, el 27 de
sólo estar para apóstrofe.
Vamos a clasificar de caso especial que.
Así que usted puede tener cierta nombres con apóstrofes.
Tal vez incluso debería guión ir allí, pero usted
ver en pág conjunto 5 que sólo la atención sobre las letras y apóstrofes.
>> Y entonces, ¿cómo hace usted representa la propia estructura de datos?
¿Cómo se representa a la raíz de este trie, por así decirlo?
Bueno, al igual que con una lista enlazada, que necesitará un puntero al primer elemento.
Con un trie sólo tiene uno puntero a la raíz de este trie.
Y a partir de allí se puede hash de su camino hacia abajo más y más profundo
a todos los demás nodos en la estructura.
Así que simplemente con esta lata representamos que estructura.
>> Ahora Meanwhile-- Oh, pregunta.
>> AUDIENCIA: ¿Cuál es la palabra bool?
>> DAVID MALAN: palabra Bool es sólo esta encarnación C
de lo que he descrito en este cuadro de aquí, cuando
Empecé a dividir cada uno de los elementos del array en dos piezas.
Uno es un puntero al siguiente nodo.
La otra tiene que haber algo así como una casilla de verificación
a decir que sí, que hay una Daven palabra que termina aquí,
porque no queremos, por el momento, Dave.
>> A pesar de que a Dave va a ser una palabra legítima, que no está en el trie
todavía.
Y D no es una palabra.
Y D-A no es una palabra o un nombre.
Así que la marca de verificación indica sólo una vez que
golpeó este nodo es el trayectoria anterior de caracteres
en realidad una cadena que ha insertado.
Así que eso es todo el bool no está haciendo por nosotros.
>> ¿Alguna otra pregunta sobre intentos?
Sí.
>> AUDIENCIA: ¿Cuál es la coincidencia?
¿Qué pasa si usted tiene un Dave y un Daven?
DAVID MALAN: Perfecto.
¿Qué pasa si usted tiene un Dave y un Daven?
Así que si insertamos, decir un apodo, para David-- Dave-- D-A-V-E?
Esto es realmente muy simple.
Así que sólo vamos a tener cuatro pasos.
D-A-V-E. Y ¿qué es lo que tengo que hacer una vez que llegué a cuarto nodo?
Sólo va a comprobar.
Ya está bueno para ir.
Hecho.
Cuatro pasos.
Tiempo constante asintótica.
Y ahora hemos indicado que tanto de Dave y Daven son cadenas en la estructura.
Así que no es un problema.
Y note cómo la presencia de Daven no hacerlo
tomar cualquier tiempo más o menos tiempo para Dave y viceversa.
>> Entonces, ¿qué otra cosa podemos hacer ahora?
Hemos utilizado esta metáfora antes de bandejas que representa algo.
Pero resulta que un pila de bandejas es en realidad
demostrativo de otro abstracto de datos type-- una estructura de datos de nivel superior
que al final del día es sólo como una matriz o una lista enlazada
o algo más mundano.
Pero es una más interesante concepto conceptual.
Una pila, como estos bandejas aquí en Mather,
generalmente se llaman sólo que-- una pila.
>> Y en este tipo de estructura de datos usted tiene dos operations--
usted tiene una llamada empuje para añadiendo algo a la pila,
como poner otra bandeja la parte posterior en la parte superior de la pila.
Y a continuación, el pop, el que significa tomar la más alta fuera de la bandeja.
Pero lo que es clave sobre una pila es que que tiene esta característica curiosa.
A medida que el personal del comedor son la reordenación de las bandejas para la próxima comida,
lo que va a ser cierto acerca de cómo los estudiantes
interactuar con esta estructura de datos?
AUDIENCIA: Van a estallar uno fuera.
DAVID MALAN: Van a pop uno fuera, esperemos que la parte superior.
De lo contrario, es sólo un poco estúpido que ir todo el camino hasta el fondo.
Derecha?
La estructura de datos en realidad no permite a agarrar la bandeja inferior, al menos,
fácilmente.
Así que hay esta curiosa propiedad de una pila
que el último elemento es va a ser el primero en salir.
Y los informáticos llaman LIFO-- este último en entrar, primero en salir.
Y lo que realmente tiene aplicaciones interesantes.
No es necesariamente tan obvio como algunos otros, pero pueden, de hecho, ser útil,
y puede, de hecho, ser implementada en un par de maneras diferentes.
>> Así que uno, y de hecho, dejar que a mí, no a sumergirse en eso.
Vamos a hacer esto en su lugar.
Echemos un vistazo a uno que es casi la misma idea, pero es un poco más justo.
Derecha?
Si usted es uno de esos chicos ventilador o chicas que realmente le gusta los productos de Apple
y se despertó a las 3:00 am a alinearse en algún almacén
para obtener la más reciente iPhone, podría haber cola para arriba como esto.
>> Ahora una cola es nombrado muy deliberadamente.
Es una línea porque no hay algunos justos con él.
Derecha?
Sería tipo de aspirado si tienes llegó primero a la tienda de Apple
pero usted es efectivamente la más inferior bandeja debido a que los empleados de Apple luego
pop de la última persona que en realidad se puso en línea.
Así pilas y colas, a pesar de funcionalmente son tipo de la same--
es sólo esta colección de los recursos que es
va a crecer y shrink-- hay este aspecto ser justos con él,
al menos en el mundo real, donde las operaciones que ejercen
son fundamentalmente diferentes.
A stack-- una cola rather-- se dice que tiene
dos operaciones: n de colas y colas d.
O usted puede llamar a ellos cualquier número de cosas.
Pero lo que desea es capturar la noción de que uno es la adición de
y uno está en última instancia restar.
>> Ahora bajo el capó, tanto la pila y una cola podría ser implementado, ¿cómo?
No vamos a entrar en el código de porque el nivel más alto
es una especie de idea más obvia.
Quiero decir, ¿qué hacen los seres humanos?
Si yo soy la primera persona en el Apple Guardar y esta es la puerta de entrada,
usted sabe, yo voy a estar aquí.
Y de la siguiente persona va a estar aquí.
Entonces, ¿qué estructura de datos se presta a una cola?
>> AUDIENCIA: Una cola.
DAVID MALAN: Bueno, una cola.
Claro.
Qué otra cosa?
>> AUDIENCIA: Una lista enlazada.
>> DAVID MALAN: Una vinculado lista que podría implementar.
Y una lista enlazada es agradable porque entonces que puede crecer arbitrariamente larga en oposición
a tener un número fijo de la gente en la tienda.
Pero tal vez un número fijo de lugares es legítimo.
Porque si sólo tienen como 20 iPhones en el primer día, tal vez
que sólo necesitan una matriz de tamaño 20 para representar a esa cola, que
es sólo para decir ahora, una vez que empezamos a hablar sobre estos problemas de más alto nivel,
usted puede ponerlo en práctica en cualquier número de maneras.
Y hay probablemente sólo va a ser una solución de compromiso en el espacio y el tiempo
o simplemente en su propia complejidad del código.
>> ¿Qué pasa con una pila?
Bien, una pila, hemos visto también podría ser sólo estas bandejas.
Y se podría implementar esta una matriz.
Pero en algún momento si se utiliza una matriz, lo que va a pasar con las bandejas
usted está tratando de poner en el suelo?
Bien.
Usted sólo va a ser capaz de ir tan alto.
Y creo que en Mather son realmente empotrada en esa abertura.
Así que de hecho, es casi como Mather está utilizando
una matriz de tamaño fijo, porque sólo se puede
encajar tantas bandejas en que la apertura en la pared por debajo de las rodillas de la gente.
Y lo que podría ser dice que es una matriz,
pero sin duda podríamos poner en práctica que más en general con una lista enlazada.
>> Bueno, ¿qué pasa con otra estructura de datos?
Permítanme levanto otra visual aquí.
Algo así como ¿qué tal este de aquí?
¿Por qué podría ser útil para no tener algo tan elegante como un trie, que
vimos tenía estos muy amplios nodos, cada uno de los cuales está en una matriz?
Pero ¿y si hacemos algo más simplemente, como un árbol de familia de la escuela vieja,
cada uno de cuyos nodos aquí se acaba de almacenar un número.
En lugar de un nombre o un descendiente se acaba de almacenar un número como este.
>> Bueno, la jerga que utilizamos en estructuras de datos es ambos paí-
y árboles, donde un trie, de nuevo, es sólo uno cuyos nodos son matrices,
sigue siendo lo que te pueden utilizar desde la escuela primaria
cuando hizo una familia hojas y la raíz tree--
del árbol y los niños de la los padres y hermanos de los mismos.
Y podríamos poner en práctica un árbol, por ejemplo, como simplemente como esto.
Un árbol, si como un nodo, una de estos círculos que tiene un número,
no va a tener un puntero, sino dos.
Y tan pronto como usted agrega un segundo puntero,
en realidad puede ahora hacer una especie de los datos de dos dimensiones
estructuras en la memoria.
Al igual que una de dos dimensiones matriz, puede
tener clase de dos dimensiones listas enlazadas, pero los
que siguen un patrón donde no hay ciclos.
Es realmente un árbol con una manera abuelo hasta aquí y luego
algunos padres y los niños y nietos y bisnietos.
y así sucesivamente.
>> Pero lo que es realmente bueno de esto también, sólo para bromear con un poco de código,
el recuerdo de la recursividad un tiempo atrás, por lo que
se escribe una función que llama a sí mismo.
Esta es una hermosa oportunidad implementar algo
como la recursividad, porque consideran que este.
>> Este es un árbol.
Y yo he sido un poco anal con cómo Puse los números enteros en la calle.
Tanto es así que tiene una especial nombre-- un árbol de búsqueda binaria.
Ahora que hemos escuchado de binario buscar, pero puede usted
trabajar hacia atrás desde el nombre de esta cosa?
¿Cuál es el patrón de la forma en que insertado los números enteros a este árbol?
No es arbitrario.
Hay algún patrón.
Sí.
>> AUDIENCIA: Los más pequeños de la izquierda.
>> DAVID MALAN: Sí.
Los más pequeños están a la izquierda.
Otros más grandes están a la derecha.
De tal manera que un enunciado verdadero es un padre es mayor que su hijo izquierdo,
pero menor que su hijo derecho.
Y eso solo es aún una definición verbal recursiva
porque se puede aplicar ese misma lógica a cada nodo
Y sólo fondos cabo, un caso base si
lo hará, cuando golpeó una de las hojas, por así decirlo,
donde una licencia no tiene hijos más.
>> Ahora, ¿cómo puede usted encontrar el número 44?
Se podría empezar en la raíz y decir, hm.
55 no es 44 así que quiero ir derecho o quiero ir a la izquierda?
Bueno, obviamente quiere ir izquierda.
Y así es como el teléfono ejemplo del libro en la búsqueda binaria
de manera más general.
Pero estamos implementarlo ahora un poco más de forma dinámica
de una matriz podría permitir.
Y de hecho, si quieres buscar en el código, a primera vista seguro.
Se parece a un montón de líneas.
Pero es maravillosamente simple.
Si desea implementar una función llamada de búsqueda cuyo propósito en la vida
es la búsqueda de un valor como n, un entero,
y ya está aprobada en una pointer-- un puntero al nodo de las raíces,
más bien, de ese árbol desde el cual se puede acceder a todo lo demás,
notar cómo rodeos usted puede aplicar la lógica.
Si el árbol es nulo, obviamente, no está allí.
Vamos a volver falsa.
Derecha?
Si te mano que nada, no hay nada allí.
>> Else, si n es menor que árbol flecha n-- ahora flecha n,
Recordamos introdujimos súper brevemente el otro día,
y eso sólo significa de-referencia el puntero y mirar el campo denominado n.
Por lo tanto, significa ir allí y mirar el campo denominado n.
Así que si n, el valor que te dan, es menos que el valor en el número entero árboles,
¿dónde quieres ir?
A la izquierda.
>> Así notar la recursividad.
Estoy returning-- no es cierto.
No es falso.
Estoy volviendo cualquiera que sea la respuesta es a partir de una llamada a mi mismo, que pasa
un n de nuevo, que es redundante, pero lo que es un poco diferente ahora?
¿Cómo estoy haciendo el problema más pequeño?
Estoy pasando como segundo argumento, no la raíz del árbol,
pero el hijo izquierdo en este caso.
Así que estoy pasando en el hijo izquierdo.
>> Mientras tanto, si n es mayor que el nodo que actualmente estoy mirando,
Yo busco el lado derecho.
De lo contrario, si el árbol no es nulo, y si el elemento no está a la izquierda
y no es a la derecha, lo que es maravillosamente el caso?
En realidad nos hemos encontrado en el nodo pregunta, y así volvemos cierto.
>> Así que acabamos de arañado la superficie ahora algunas de estas estructuras de datos.
En el problema fijó cinco podrás explorar estos aún más lejos,
y se le dará su diseño elección de cómo ir sobre esto.
Lo que me gustaría llegar a la conclusión de es sólo un segundo teaser de 30
de lo que espera a la semana que viene y más allá.
>> A medida que begin-- afortunadamente te pueden think-- nuestra transición lentamente
del mundo de la C y la más baja detalles de implementación de nivel,
a un mundo en el que podemos tomar para sentado que alguien tiene por fin
implementado estos datos estructuras para nosotros,
y vamos a empezar a entender el significa el mundo real de la implementación
programas basados ​​en la web y sitios web de forma más general
y también la propia seguridad implicaciones que hemos sólo
empezado a rascar la superficie de.
Esto es lo que nos espera en los días por venir.
>> [REPRODUCCIÓN DE VÍDEO]
>> -Él Vino con un mensaje, con un protocolo de todas las suyas.
Él vino a un mundo de cruel firewalls, routers indiferentes,
y peligros mucho peores que la muerte.
Es rápido.
Es fuerte.
Él es TCP / IP, y que tiene su dirección.
"Guerreros de la red."
[FIN REPRODUCCIÓN DE VÍDEO]
DAVID MALAN: Si viene la próxima semana.
Nos vemos entonces.
[REPRODUCCIÓN DE VÍDEO]
-Y Ahora, "Pensamientos profundos" por Daven Farnham.
-David Comienza siempre conferencias con: "Muy bien."
¿Por qué no, "Aquí está la solución al conjunto de problemas de esta semana "
o "Estamos dando a todos ustedes una A?"
[Risas]
[FIN REPRODUCCIÓN DE VÍDEO]