DAVID MALAN: Está bien. Estamos de vuelta. Así que en este segmento de la programación lo Pensé que nos gustaría hacer es una mezcla de cosas. Uno de ellos, hacer un poco de algo práctico, aunque utilizando una más lúdica ambiente- programación uno que es demostrativo de exactamente el tipo de ideas hemos estado hablando, pero un poco más formal. Dos, un vistazo a algunas de las las formas más técnicos que un programador en realidad resolver problemas como el problema de la búsqueda que miramos antes y También una manera más fundamental interesante problema de la clasificación. 

Nosotros asumimos desde el principio que ese libro de teléfono se solucionó, pero que por sí sola es en realidad una especie de problema difícil con muchas formas diferentes para resolverlo. Así que vamos a utilizar estos como una clase de problemas representante de las cosas que podría resolverse en general. Y entonces hablaremos sobre con cierto detalle lo se llaman los datos structures-- maneras más elegantes como listas enlazadas y tablas hash y árboles que un programador en realidad usar y generalmente utilizar en una pizarra para pintar una imagen de lo que él o ella prevé para la implementación alguna pieza de software. 

Así que vamos a hacer las manos en la primera parte. Por lo que sólo ensuciarse las manos con una scratch.mit.edu entorno llamada. Esta es una herramienta que utilizamos en nuestra clase de grado. A pesar de que está diseñado para mayores de 12 años, lo usamos para arriba parte de eso un poco ya que es un agradable, divertido manera gráfica de aprendizaje un poco de algo acerca de la programación. Así que la cabeza a esa URL, donde Debería ver una página como este, y seguir adelante y haga clic Unirse a los arañazos en la parte superior derecha y elegir un nombre de usuario y una contraseña y, finalmente, se consigue un scratch.mit.edu account--. Pensé que haría uso de esto como una oportunidad de primera para mostrar esto. Una pregunta surgió durante el descanso acerca de lo que en realidad parece código. Y estábamos hablando durante el descanso sobre C, en particular: en particular una nivel más bajo en una lengua más antigua. Y acabo de hacer una rápida Google buscar para encontrar el código C para la búsqueda binaria, el algoritmo que nos utilizado para buscar ese libro de teléfono anterior. Este ejemplo en particular, por supuesto, no busca una guía telefónica. Simplemente busca en un montón de números en la memoria del ordenador. Pero si desea obtener sólo una representación visual sentido de lo que es una programación real el lenguaje se parece, se ve un poco de algo como esto. Por lo tanto se trata de más de 20, 30 o más líneas de código, pero la conversación que estaban teniendo durante las vacaciones fue acerca de cómo este hecho obtiene transformado en ceros y unos y si uno no puede revertir ese procesar e ir de ceros y unos volver al código. 

Desafortunadamente, el proceso de es tan transformadora que es mucho más fácil decirlo que hacerlo. Seguí adelante y en realidad resultó ese programa, búsqueda binaria, en ceros y unos a modo de una El programa llamado compilador que yo sucede que tiene aquí a la derecha en mi Mac. Y si nos fijamos en la pantalla aquí, centrándose específicamente sobre estas medias seis columnas solamente, verá sólo ceros y unos. Y esos son los ceros y unos que componer exactamente ese programa de búsqueda. 

Y así, cada trozo de cinco bits, cada byte de ceros y unos aquí, representar alguna instrucción normalmente dentro de un ordenador. Y de hecho, si usted ha oído el lema publicitario "Intel inside" - que, por supuesto, simplemente significa que tiene una CPU Intel o el cerebro en el interior del equipo. Y lo que significa ser un CPU es que tiene un conjunto de instrucciones, por así decirlo. 

Cada CPU en el mundo, muchos de ellos fabricados por Intel en estos días, comprende un número finito número de instrucciones. Y esas instrucciones son tan bajo nivel como añadir estos dos números, multiplicar estos dos números, mover esta pieza de información de aquí de aquí en memoria, guardar este la información de aquí hasta aquí en la memoria, y así forth-- muy, muy De bajo nivel, casi detalles electrónicos. Pero con los matemática operaciones acoplada con lo que hemos comentado anteriormente, la representación de datos como ceros y unos, puede todo lo que se acumulan que un ordenador puede hacer hoy, si es textual, gráfica, musical, o de otro modo. 

Así que esto es muy fácil de conseguir perdido entre la maleza de forma rápida. Y hay una gran cantidad de retos sintácticos por lo que si se hace el más simple, más estúpida de errores tipográficos ninguno de los programas funcionará en absoluto. Y así, en lugar de utilizar una lenguaje como C esta mañana, Pensé que sería más divertido para hacer realidad algo más visual, que mientras diseñado para niños es en realidad una manifestación perfecta de una programación real language-- sólo pasa a utilizar imágenes en lugar de texto para representar esas ideas. 

Así que una vez que de hecho tiene una cuenta en scratch.mit.edu, haga clic en el botón Crear en la parte superior izquierda de la página. Y hay que ver un entorno como el que estoy a punto de ver en mi pantalla aquí. Y vamos a pasar sólo un poco poco de tiempo jugando aquí. Veamos si no todos podemos resolver algunos problemas juntos de la manera siguiente. 

Así que lo que verá dentro de este ambiente- y de hecho acaba de dejar Me detengo. ¿Hay alguien que no está aquí? ¿Aqui no? DE ACUERDO. Así que permítanme señalar algunos características de este entorno. 

Así que en la parte superior izquierda de la pantalla, nos La etapa de tener arañazos, por así decirlo. Scratch es no sólo el nombre de este lenguaje de programación; que es también el nombre del gato que se ves por defecto no en naranja. Él está en una etapa, por lo al igual que describí la tortuga anteriormente como miembros de un rectangular entorno de la tarjeta blanca. El mundo de este gato está confinado en su totalidad a ese rectángulo encima de la tapa allí. 

Mientras tanto, a la derecha lado aquí, es sólo un área de secuencias de comandos, una pizarra en blanco si se quiere. Aquí es donde vamos a escribir nuestros programas en un momento. Y los bloques de construcción que deberán utilizar para escribir este program-- el rompecabezas piezas, si usted está Voluntad-- los que están aquí en el medio, y están categorizados por funcionalidad. Así, por ejemplo, voy a seguir adelante y demostrar por lo menos uno de estos. Voy a seguir adelante y haga clic la Categoría de control hasta la parte superior. 

Así que estas son las categorías encima de la tapa. Voy a clic en la categoría de control. Más bien, voy a haga clic en los Eventos categoría, el primero de todos en la superior. Y si desea seguir adelante, incluso al hacer esto, usted es muy bienvenido a. Voy a hacer clic y arrastrar este primero, "cuando se hace clic en bandera verde." Y luego voy a dejar que sólo más o menos en la parte superior de mis pizarras en blanco. 

Y lo que es bueno de los arañazos es que esta pieza del rompecabezas, cuando enclavada con otro rompecabezas piezas, se van a hacer, literalmente, lo que esas piezas del rompecabezas dicen que hacer. Así, por ejemplo, Scratch es correcta ahora en el centro de su mundo. Voy a seguir adelante y elegir Ahora, vamos a decir, la categoría de movimiento, Si desea hacer lo same-- categoría de movimiento. Y ahora noto que tengo en su conjunto montón de piezas de un rompecabezas aquí que, de nuevo, una especie de hacer lo que dicen. Y voy a seguir adelante y arrastrar y dejar caer el bloque de movimiento por aquí. 

Y note que tan pronto como se obtiene cerca de la parte inferior de la "bandera verde hecho clic en "botón, el aviso cómo aparece una línea blanca, como si fuera casi magnética, que quiere ir allí. Simplemente deja ir, y se encajará juntos y las formas coincidirán. tal vez y ahora casi se puede adivinar hacia dónde vamos con esto. 

Si nos fijamos en la etapa de Scratch por aquí y mirar a la parte superior de la misma, verá una luz roja, una señal de stop, y una bandera verde. Y voy a seguir adelante y ver mis screen-- por un momento, si pudiera. Voy a hacer clic en el bandera verde en este momento, y se trasladó lo que parece ser 10 pasos o 10 píxeles, 10 puntos, en la pantalla. 

Y lo que no es tan emocionante, pero permítanme proponer sin ni siquiera la enseñanza de esto, sólo utilizando el dueño de su propio let intuition-- Me propongo a averiguar cómo hacer pie derecho arañazos fuera del escenario. Haga que dar paso a la derecha de la pantalla, todo el camino a la derecha. Déjeme darle un momento o por lo que luchar con eso. Es posible que desee echar un vistazo en otras categorías de bloques. Todo bien. Así que para recapitular, cuando tenemos la bandera verde clic aquí y mover 10 pasos es la única instrucción, cada vez que haga clic en la bandera verde, lo que está pasando? Bueno, eso es correr mi programa. Por lo que podía hacer esto tal vez 10 veces de forma manual, pero esto se siente un poco hackish poco, por así decirlo, por lo que no estoy realmente resolviendo el problema. Sólo intento una y otra una y otra y otra vez hasta que tipo de accidente lograr la directiva que se propuso lograr antes. 

Pero sabemos por nuestra pseudocódigo anterior que hay esta noción en la programación de bucles, hacer algo una y otra vez. Y así vi que un montón de ustedes alcanzado para la pieza de puzzle lo que? Repetir hasta. Así que podríamos hacer algo al igual que repetir hasta. ¿Y qué se repite hasta que exactamente? 

DE ACUERDO. Y déjame ir con uno que es algo más sencillo sólo por un momento. Déjame seguir adelante y hacer esto. Tenga en cuenta que, ya que puede tener descubierto bajo control, hay este bloque de repetición, lo cual no se ve como si fuera tan grande. No hay mucho ambiente en entre esas dos líneas amarillas. Sin embargo, como algunos de ustedes podrían tener notado, si arrastra y soltar, observe cómo crece para rellenar la forma. 

E incluso se puede meter más. Simplemente va a seguir creciendo si se arrastra y se pasa sobre ella. Y no sé lo que es mejor aquí, así que vamos Me repito al menos cinco veces, para instancia y, a continuación, volver a la etapa y haga clic en la bandera verde. Y ahora se dio cuenta que no es muy allá. 

Ahora algunos de ustedes proponen, como Victoria acaba de hacer, repetir 10 veces. Y que hace por lo general llevarlo hasta el final, pero ¿no habría un más robusto de manera arbitraria averiguar cuántos movimientos para hacer? ¿Cuál podría ser un bloque mejor que repetir 10 veces? 

Sí, ¿por qué no hacer algo para siempre? Y ahora vamos a mover este pedazo del rompecabezas En el interior hay y deshacerse de éste. Ahora note, sin importar dónde los arañazos aperturas, que va hasta el borde. Y afortunadamente el MIT, que hace Scratch, simplemente se asegura de que nunca desaparece por completo. Siempre se puede agarrar su cola. 

Y de la misma manera intuitiva, ¿por qué sigue en movimiento? ¿Que esta pasando aqui? Él parece haberse detenido, pero entonces, si recojo y arrastre él sigue queriendo ir por allí. ¿Porqué es eso? En verdad, un ordenador es, literalmente, va a hacer lo que le indica que hacer. Así que si usted le dijo que haga lo antes Lo siguiente para siempre, mover 10 pasos, que va a seguir y seguir hasta que llegué a la señal de stop roja y detener el programa completo. 

Así que incluso si no lo hizo hacer esto, ¿cómo podría hacerlo hacer que los arañazos se mueven más rápido a través de la pantalla? Más pasos, ¿verdad? Así que en lugar de hacer 10 a la vez, ¿por qué no seguir adelante y cambiarlo a-- ¿qué le propose-- 50? Así que ahora voy a hacer clic en el verde bandera, y, de hecho, va muy rápido. 

Y esto, por supuesto, es sólo una manifestación de la animación. ¿Cuál es la animación? Es sólo que muestra el ser humano manojo entero de imágenes fijas en realidad, muy, muy rápido. Y así, si sólo estamos diciendo que se mueva más pasos, sólo estamos teniendo el efecto sea donde el cambio es en la pantalla tanto más rápidamente por unidad de tiempo. 

Ahora, el siguiente reto que propuse iba a tener que rebote fuera del borde. Y sin saber qué rompecabezas la cual existen piezas, ya que está bien si no se llega a la etapa del challenge-- lo Qué desea hacer intuitivamente? ¿Cómo tendríamos que rebote hacia atrás y etc., entre la izquierda y la derecha? 

Sí. Así que necesitamos algún tipo de la condición, y parecen tener condicionales, por lo que hablar, en la categoría de control. ¿Cuál de estos bloques es lo que probablemente queremos? Sí, tal vez "si, entonces". Así notar que entre los bloques amarillos tenemos aquí, no es este "si" o este "si, de lo contrario" bloque que nos permiten hacer una decisión para hacer esto o para hacer eso. E incluso se puede anidar hacer varias cosas. O si no has ido aquí todavía, seguir adelante con la categoría de detección y- vamos a ver si es aquí. 

Entonces, ¿qué bloque podría ser útil aquí para detectar si está fuera del escenario? Sí, darse cuenta de que algunos de estos bloques puede ser parametrizada, por así decirlo. Pueden ser una especie de personalizarse, no a diferencia de HTML ayer con atributos, donde dichos atributos tipo de personalizar el comportamiento de una variable. Del mismo modo aquí, puedo agarrar esta conmovedora bloque y el cambio y hacer la pregunta, estás tocando el ratón puntero al igual que el cursor o está tocando el borde? 

Así que déjame ir y hacer esto. Voy a alejar por un momento. Permítanme aprovechar esta pieza del rompecabezas aquí, esta pieza del rompecabezas de esto, y voy a jumble para arriba para un momento. Voy a mover esto, cambiar esto a tocar el borde, y voy a hacer esto de movimiento. Así que aquí están algunos de los ingredientes. Creo que tengo todo lo que quiero. 

¿Alguien quiere proponer cómo se puede conectar éstos tal vez de arriba a abajo con el fin de resolver el problema de tener Scratch derecha a izquierda a derecha para mover de izquierda a derecha a izquierda, cada una tiempo sólo rebotando en la pared? ¿Qué quiero hacer? ¿Qué bloque se debe conectar a la "Bandera verde cuando se hace clic en primer lugar"? 

OK, así que vamos a empezar con el "para siempre". Lo que va dentro de la próxima? Alguien más. OK, mover los pasos. Todo bien. ¿Y que? Con esto, el caso. Y note, a pesar de lo que parece intercalado juntas firmemente, sólo crecerá para llenar. Se acaba de entrar en donde lo quiero. 

Y ¿qué es lo que puso entre el si y el entonces? Probablemente "si tocar el borde." Y aviso, de nuevo, es demasiado grande para ello, pero que crecerá para llenar. Y luego girar 15 grados? ¿Cuántos grados? Sí, por lo que 180 girará conmigo todo el camino alrededor. Así que vamos a ver si tengo ese derecho. Permítanme Alejar. 

Permítanme arrastro hasta rasguño. Así que es un poco distorsionada ahora, pero que está bien. ¿Cómo le puedo restablecer fácilmente? Yo os voy a engañar un poco. Así que estoy añadiendo otra bloque, para ser claros. Quiero que el punto 90 grados a la derecha por defecto, así que sólo voy a decirle de hacerlo mediante programación. Y aquí vamos. Parece que hemos hecho. Es un poco raro, porque él está caminando al revés. Vamos a llamar a que un error. Eso es un error. Un error es un error en un programa, una error lógico que yo, el ser humano, hice. Por qué se va al revés? ¿Se tornillo MIT arriba o hacía yo? 

Sí, quiero decir, no es de MIT culpa. Me dieron una pieza del rompecabezas dice que a su vez cierta cantidad de grados. Y por sugerencia de Victoria, Estoy girando 180 grados, que es la intuición correcta. Pero convertir 180 grados literalmente significa girar 180 grados, y eso no es verdad lo que yo quiero, al parecer. Debido a que al menos está en este mundo de dos dimensiones, de modo decisivo es realmente va a él voltear al revés. 

Probablemente quiero usar lo que el bloque en cambio, en base a lo que se ve aquí? ¿Cómo podemos solucionar este problema? Sí, por lo que podríamos señalar en la dirección opuesta. Y, de hecho, incluso eso es no va a ser suficiente, porque sólo podemos codificar que apunta hacia la izquierda o hacia la derecha. 

Ya sabes lo que podríamos hacer? Parece que tenemos una bloque de conveniencia aquí. Si hago zoom, consulte algo que nos gusta aquí? Así que parece que el MIT tiene una abstracción construida aquí. Este bloque parece ser equivalente a la que otros bloques, plural? 

Esta a una cuadra parece ser equivalente a todo este trío de bloques que tenemos aquí. Así que resulta que puedo simplificar mi programa por deshacerse de todo eso y sólo hay que poner esto aquí. Y ahora está todavía un poco con errores, y eso está bien por ahora. Vamos a dejar que sea. Pero mi programa es aún más simple, y esto, también, sería representativa de un objetivo en programming-- es hacer idealmente como su código simple, lo más compacto posible, sin dejar de ser tan legibles como sea posible. Usted no quiere hacerlo de modo sucinto que es difícil de entender. 

Pero nótese que he sustituido tres bloques con uno, y eso es sin duda una buena cosa. He abstrae la noción de comprobar si estás en el borde con un solo bloque. Ahora podemos tener diversión con esto, de hecho. Esto no agrega tanto valor intelectual pero el valor lúdico. Voy a seguir adelante y apoderarse de este sonido aquí. Así que déjame ir por delante, y me dejó detener el programa por un momento. Voy a grabar lo siguiente, permitiendo el acceso al micrófono. 

Aquí vamos. Ay. Vamos a intentarlo de nuevo. Aquí vamos. OK, he grabado lo que no debía. Aquí vamos. Ay. Ay. Todo bien. Ahora necesito para deshacerse de eso. Todo bien. 

Así que ahora tengo una grabación de sólo "ouch". Así que ahora voy a ir adelante y llamar a este "ay". Voy a volver a mis guiones, y ahora notificación no este bloque que se llama jugar "maullido" sonido o reproducir sonido "ay". Voy a arrastrar este, y donde debería poner esto para el efecto cómico? Sí, por lo que ahora es una especie de con errores, porque ahora esta block-- notar cómo este "si en el borde, rebote "es una especie de auto-contenido. Así que tengo que arreglar esto. Déjame seguir adelante y hacer esto. Permítanme deshacerse de este y volver a nuestro original, más deliberado funcionalidad. Por lo que "si toca el borde, a continuación," Quiero a su vez, como se propuso Victoria, 180 grados. Y es lo que quiero para jugar el sonido "ay" hay? 

Sí, observe que está fuera ese bloque amarillo. Así que esto también sería una insecto, pero me he dado cuenta de ello. Así que voy a arrastrarla hasta aquí, y el aviso que ahora está dentro de la "si". Por lo que el "si" ¿es esta clase como de transferencia en forma de brazo que sólo va a hacer lo que hay dentro de ella. Así que ahora si Alejar a el riesgo de annoying-- 

ORDENADOR: ¡Ay, ay, ay. 

DAVID MALAN: Y sólo va a durar para siempre. Ahora sólo para acelerar las cosas aquí, déjame ir por delante y abrir, vamos a decir-- déjame ir a alguna de mi propio material de la clase. Y déjame abrir hasta, digamos, este una hecha por uno de nuestros compañeros de enseñanza un par de años atras. Por lo que algunos de ustedes pueden recordar este juego de antaño, y de hecho es notable. A pesar de que hemos hecho el más simple de los programas en este momento, vamos a considerar lo que este que en realidad parece. Me Hit juego. 

Así que en este juego, tenemos una rana, y el uso de la flecha keys-- toma pasos más grandes de lo que remember-- Tengo control sobre esta rana. Y el objetivo es conseguir a través de la ocupada camino sin caer en los coches. Y vamos a ver-- si voy hasta aquí, tener que esperar a que un registro para desplazarse por. Esto se siente como un insecto. Esta es una especie de insecto. Todo bien. Estoy en esto aquí, allí, y luego se mantiene avanzando hasta llegar todo las ranas a las hojas de nenúfar. Ahora bien, esto puede tener un aspecto todo el más complejo, pero vamos a tratar de romper esto abajo mentalmente y verbalmente en sus bloques de componentes. Así que es probable que haya un rompecabezas pieza que no hemos visto todavía pero eso es responder a las pulsaciones de teclado, a las cosas me golpeó en el teclado. 

Así que es probable que haya algún tipo de bloque que dice, si la clave es igual a, a continuación, hacer algo con Scratch-- tal vez moverlo 10 pasos de esta manera. Si se pulsa la tecla hacia abajo, mover 10 pasos de esta manera, o la tecla izquierda, se mueven 10 pasos De esta manera, los pasos que 10. Me he convertido claramente el gato en una rana. Así que eso es justo donde el traje, como llamadas de Scratch que it-- acaba de importar una imagen de la rana. 

Pero lo que más está sucediendo? ¿Qué otras líneas de código, lo demás piezas del rompecabezas Blake hizo, nuestros compañeros de la enseñanza, utilizar en este programa, por lo visto? Lo que está haciendo todo lo move-- lo que la programación de la construcción? 

Movimiento, por lo que el sure-- mover el bloque, seguro. Y lo que es ese bloque de movimiento Dentro, más probable? Sí, algún tipo de bucle, tal vez una siempre bloquear, tal vez una repetición block-- repetir hasta que el bloque. Y eso es lo que está haciendo los registros y las hojas de nenúfar y todo lo demás jugada de ida y vuelta. Es sólo sucediendo sin fin. 

¿Por qué son algunos de los coches mueve más rápido que los demás? Lo que es diferente acerca de estos programas? Sí, probablemente algunos de ellos están tomando más pasos a la vez y algunas de ellas un menor número de pasos a la vez. Y el efecto visual es rápido frente lento. 

¿Qué crees que pasó? Cuando llegué a mi rana de todo el camino cruzar la calle y el río en la almohadilla de lirio, algo digno de mención ocurrió. ¿Qué pasó tan pronto como lo hice? Se detuvo. Que la rana se detuvo, y Tengo una segunda rana. Entonces, ¿cuál debe ser constructo utilizado allí, qué función? 

Sí, por lo que hay algún tipo de "Si" condición hasta allí, también. Y resulta out-- no vimos esto- pero hay otros bloques en que hay se puede decir, si usted está tocando otra cosa en la pantalla, si usted está tocando la hoja de lirio, "entonces". Y entonces es cuando nos hacer aparecer la segunda rana. Así que a pesar de que este juego es sin duda muy anticuado, a pesar de que a primera vista hay tantas cosas que pasan y Blake en-- no azotar esto en dos minutos, es probable que se lo llevó a varios horas para crear este juego basado en su memoria o vídeos de la versión de antaño de la misma. Pero todas estas pequeñas cosas va en la pantalla en forma aislada se reducen a éstos muy simple constructs-- movimientos o estados como hemos comentado, los bucles y condiciones, y eso es todo. Hay algunas otras características más elegantes. Algunos de ellos son puramente estética o acústica, como los sonidos que yo en el con. Pero en su mayor parte, se tienen en este idioma, Scratch, todo de la fundamental bloques de construcción que se tener en C, Java, JavaScript, PHP, Ruby, Python, y cualquier número de otros idiomas. Una pregunta sobre el principio? Todo bien. Así que no vamos a bucear más profundamente a la altura, aunque de nada este fin de semana, especialmente si usted tiene niños o sobrinos y demás, para introducirlos a los arañazos. En realidad es un maravillosamente lúdico medio ambiente, con, como dicen sus autores, techos muy altos. A pesar de que empezamos con mismos detalles de bajo nivel, realmente se puede hacer un poco con ello, y esto es quizás una demostración de exactamente eso. 

Pero ahora vamos transición a un poco más de problemas sofisticados, si se quiere, conocida como "búsqueda" y "Clasificación", en términos más generales. Hemos tenido este libro de teléfono antes les hablé aquí está otra plantilla sólo para discussion-- que hemos sido capaces de buscar de manera más eficiente porque de un supuesto significativo. Y sólo para que quede claro, lo Se suponía que hacer cuando se busca a través de esta guía de teléfonos? Que Mike Smith estaba en la guía de teléfonos, aunque sería capaz de manejar el escenario sin él allí si sólo se detuvo prematuramente. El libro es alfabético. Y eso es un muy generoso supuesto, porque eso significa alguien-- Soy una especie de cortar una esquina, como yo soy más rápido porque alguien más hizo un montón de trabajo duro para mí. 

Pero ¿y si el teléfono libro fueron sin ordenar? Tal vez Verizon obtuvo perezoso, acaba de lanzar nombres y números de todo el mundo allí tal vez en el orden en que se firmado para el servicio telefónico. Y cuánto tiempo se me lleve encontrar a alguien como Mike Smith? 1.000 telefónico página book-- cuántos páginas tengo que mirar a través de? 

Todos ellos. Eres una especie de fuera de suerte. Literalmente tienes que mirar cada página si la guía telefónica es sólo ordenados aleatoriamente. Puede que tenga suerte y encuentre Mike en la primera página, porque él fue el primer cliente para ordenar el servicio telefónico. Pero podría haber sido la última, también. 

Así orden aleatorio no es bueno. Así que supongamos que tenemos para ordenar la directorio telefónico o en datos generales especie que se nos ha dado. ¿Cómo podemos hacer eso? 

Bueno, déjame sólo trato aquí un ejemplo sencillo. Déjame ir adelante y lanzar una unos números en el tablero. Supongamos que los números que tenemos son, digamos, cuatro, dos, uno y tres. Y, Ben, ordenar estos números para nosotros. 

Bien. ¿Cómo hiciste eso? Todo bien. Así que empieza con los más pequeños el valor y la más alta, y eso es muy buena intuición. Y darse cuenta de que los seres humanos son en realidad bastante bueno en la solución de problemas de esta manera, al menos cuando los datos es relativamente pequeño. Tan pronto como usted comienza a tener cientos de números, miles de números, millones de números, Ben probablemente No podría hacerlo bastante rápido que, suponiendo que no eran lagunas en los números. Bastante fácil de contar hasta un millón de lo contrario, solo consume mucho tiempo. 

Así que el algoritmo que suena como Ben utiliza ahora fue buscar el número más pequeño. Así que a pesar de que los seres humanos podemos tener en una gran cantidad de información visual, un ordenador es en realidad un poco más limitada. El equipo sólo puede mirar a un byte a la vez o tal vez cuatro bytes a la vez-- en estos días quizás 8 bytes a la vez-- pero un número muy pequeño de bytes en un momento dado. 

Por lo tanto, dado que realmente tenemos cuatro valores separados aquí-- y que se pueda imaginar Ben como tener venda en los ojos si fuera un ordenador, tales que él no puede ver otra cosa de un número a un tiempo-- por lo que generalmente se asume, como en Inglés, vamos a leer de derecha a izquierda. Así que el primer número Ben probablemente se veía a era cuatro y luego muy rápidamente se dieron cuenta de que es una bastante grande number-- déjame seguir buscando. 

Hay dos. Espera un minuto. Dos es menor que cuatro. Voy a recordar. Dos es ahora el más pequeño. Ahora uno-- que es incluso mejor. Eso es aún más pequeño. Voy a olvidarse de dos y sólo recuerda una ahora. 

Y podía dejar de mirar? Bueno, él podría basada en esta información, pero será mejor que la búsqueda el resto de la lista. Porque lo que si eran cero en la lista? ¿Qué pasa si uno fuera negativo en la lista? Sólo sabe que su respuesta es correcto si él es exhaustiva verificado la lista entera. Así que nos fijamos en el resto de este. Tres-- que era una pérdida de tiempo. Tengo mala suerte, pero yo estaba siendo correcta para hacerlo. Y por lo que ahora es de suponer seleccionado el número más pequeño y sólo hay que poner al principio de la lista, ya que voy a hacer aquí. Ahora lo hizo después, a pesar de que que no piensa en ello casi ¿en esta medida? Repita el proceso, así que algún tipo de bucle. Hay una idea familiar. Así que aquí es cuatro. Eso es actualmente el más pequeño. Eso es un candidato. Ya no. Ahora que he visto dos. Ese es el siguiente elemento más pequeño. Tres-- eso no es menor, por lo Ahora Ben puede extirpar a los dos. 

Y ahora repetimos el proceso, y por supuesto, se tira a cabo tres siguiente. Repetir el proceso. Cuatro se retiró. Y ahora que estamos fuera de los números, por lo que la lista debe ser ordenada. 

Y, en efecto, se trata de un algoritmo formal. Un científico de la computación haría llamar a esta "ordenación por selección" con la idea de una especie iteratively-- enumerar de nuevo y otra vez y otra vez seleccionando el número más pequeño. Y lo que es agradable sobre él es es tan rematadamente intuitiva. Es tan simple. Y se puede repetir el mismo operación una y otra vez. Es sencillo. 

En este caso fue rápido, pero ¿Cuánto tiempo se tome realmente? Vamos a hacer que parezca y sentir un poco más tedioso. Así que uno, dos, tres, cuatro, cinco y seis, siete, ocho, nueve, 10, 11, 12, 13, 14, 15, 16-- número arbitrario. Sólo quería más este tiempo del que sólo el cuatro. Así que si tengo un todo montón de números que ahora-- Ni siquiera importa lo que se trate: de dejar pensar en lo que esta algoritmo es muy similar. 

Supongamos que hay un número allí. Una vez más, no importa lo que son, pero son al azar. Estoy aplicando el algoritmo de Ben. Necesito seleccionar el número más pequeño. ¿Qué debo hacer? Y voy a físicamente hacer que este momento de actuar hacia fuera. Buscando, buscando, mira, mira, mira. Sólo por el momento de llegar a Al final de la lista se puede Soy consciente de los más pequeños número dos fue esta vez. Uno no está en la lista. Así que puse abajo dos. 

¿Que hago después? Mirando, mirando, mirando, mirando. Ahora he encontrado el número siete, porque hay lagunas en estos numbers-- pero sólo arbitraria. Todo bien. Así que ahora puedo poner siete. Mirando mirando, mirando. 

Ahora estoy suponiendo, Por supuesto, que Ben no tiene RAM adicional, extra memoria, porque, por supuesto, Estoy mirando el mismo número. Seguramente que podría haber recordado todos esos números, y eso es absolutamente cierto. Pero si Ben recuerda todo de los números que ha visto, en realidad no ha hecho avances fundamentales porque ya tiene la capacidad de buscar a través de los números en el tablero. Recordando a todos los los números no ayuda, porque él puede todavía como un ordenador Sólo mira, lo hemos dicho, un número a la vez. Así que no hay ningún tipo de trucos ahí que puede aprovechar. 

Así que en realidad, como ya seguir buscando la lista, Yo, literalmente, tengo que acaba de seguir adelante de ida y vuelta a través de él, arrancando el número inmediatamente inferior. Y como se puede inferir tipo de de mis movimientos tontos, Esto se pone muy tedioso muy rápidamente, y me parece estar yendo y adelante, atrás y adelante un poco. Ahora, para ser justos, no tengo que ir tan, bueno, vamos a ver-- para ser justos, No tengo que caminar bastante tantos pasos cada vez. Porque, por supuesto, como yo seleccionar los números de la lista, la lista restante se hace más corto. 

Y así vamos a pensar la cantidad de pasos que estoy realmente penosamente a través de cada vez. En la primera situación teníamos 16 números, y así sólo vamos a maximally-- hacer esto por un discussion-- Tenía que mirar a través de 16 números para encontrar la más pequeña. Pero una vez que arranqué el número más pequeño, cómo siempre fue la lista restante, por supuesto? Sólo 15. Entonces, ¿cuántos números de Ben hizo o que tienen para mirar a través de la segunda vez? 15, sólo para ir a buscar a los más pequeños. Pero ahora, por supuesto, la lista es, también, más pequeña de lo que era antes. Entonces, ¿cómo lo hicieron muchos pasos tiene que tomar la próxima vez? 14 y luego 13 y luego 12, más punto, punto, punto, hasta que me quedo con uno solo. Así que ahora lo haría un científico de la computación preguntar, bueno, lo que hace que todos iguales? En realidad, es igual a poco de concreto número que sin duda podríamos hacemos aritméticamente, pero queremos hablar acerca de la eficiencia de los algoritmos un poco más formulaically, independiente de la duración de la lista es. 

Y para que sepa qué? Esto es 16, pero como he dicho antes, Vamos a llamar el tamaño del problema n, donde n es un número. Tal vez sea 16, tal vez es tres, tal vez es un millón. No lo sé. No me importa. Lo que realmente quiero es una fórmula que pueda utilizar para comparar este algoritmo contra otros algoritmos que alguien podría reclamar son mejores o peores. 

Así que resulta, y sólo yo saber esto desde la escuela primaria, que esto realmente funciona a la misma cosa como n sobre n más uno más de dos. Y esto pasa a ser igual, de Por supuesto, n al cuadrado más n más de dos. Así que si quería una fórmula ¿De cuántos pasos participaron en el estudio de todos de esos números una y otra vez y otra vez y otra vez, yo diría que está n al cuadrado más n más de dos. ¿Pero sabes que? Esto sólo se ve desordenado. Yo realmente quiero una sentido general de las cosas. Y se puede recordar de la escuela secundaria que hay es la noción de término más alto orden. ¿Cuál de estos términos, el n cuadrado, el n, o la mitad, tiene el mayor impacto en el tiempo? Cuanto más grande n consigue, que de estos asuntos más? 

En otras palabras, si lo conecto en un millón, n al cuadrado va a ser más probable el factor dominante, porque un millón de veces en sí es mucho más grande que más uno adicional millones. Así que ya saben qué? Este es un darn tan grande número si se eleva al cuadrado un número. Esto en realidad no importa. Sólo vamos cruz que y olvidarse de él. Y por lo que un científico de la computación diría que la eficacia de este algoritmo es del orden de n squared-- Me refiero a realmente una aproximación. Es una especie de más o menos n al cuadrado. Con el tiempo, cuanto más grande y más grande que n se hace, esto es una buena estimación de lo que el la eficiencia o la falta de eficiencia de este algoritmo es en realidad. Y derivo que, por supuesto, en cuanto a realizar los cálculos. Pero ahora sólo estoy agitando mis manos, porque acabo desear un sentido general de este algoritmo. 

Así, utilizando la misma lógica, por su parte, vamos a considerar otro algoritmo ya encontramos at-- búsqueda lineal. Cuando yo estaba buscando para la book-- teléfono No arreglármelo, buscando a través de la book-- teléfono mantuvimos diciendo que era 1.000 pasos, o 500 pasos. Pero vamos a generalizar eso. Si hay n páginas en la guía de teléfonos, lo que es el tiempo de ejecución o la eficiencia de búsqueda lineal? Es del orden de la cantidad de pasos para encontrar Mike Smith mediante la búsqueda lineal, la primer algoritmo, o incluso el segundo? 

En el peor de los casos, Mike está en el extremo del libro. Así que si el directorio tiene 1.000 páginas, dijimos la última vez, en el peor de los casos, que podría tomar la forma más o menos muchas páginas para encontrar Mike? Al igual que 1,000. Es un límite superior. Es una peor situación posible. Pero, de nuevo, nos estamos alejando de 1.000 números como ahora. Es sólo n. 

¿Cuál es la conclusión lógica? Encontrar Mike en un teléfono libro que tiene n páginas podría llevar, en el peor de los casos, el número de pasos en el orden de los n? Y de hecho un ordenador científico diría que el tiempo de ejecución, o la rendimiento o la eficiencia o ineficiencia, de un algoritmo como una búsqueda lineal es del orden de n. Y podemos aplicar el mismo lógica de cruzar algo fuera como acabo de hacer a la segunda algoritmo que tuvimos con la guía telefónica, donde fuimos dos páginas a la vez. 

Así 1,000 página de la guía telefónica podría llevarnos a 500 vueltas de página, más uno si doblamos un poco hacia atrás. Así que si un directorio tiene n páginas, pero que estamos haciendo dos páginas a la vez, que es más o menos qué? N más de dos, por lo que es como n más de dos. Pero hice el reclamo de una Hace momento en que n sobre dos-- eso es un poco lo mismo que acaba de n. Es sólo un factor constante, los informáticos dirían. Vamos sólo se centran en las variables, realmente-- los mayores variables en la ecuación. 

búsqueda de modo lineal, ya se haga una página a la vez o dos páginas a la vez, es una especie de fundamentalmente los mismos. Todavía es del orden de n. Pero yo decía con mi cuadro anterior que la tercera algoritmo no era lineal. No era una línea recta. Fue esa línea curva, y la fórmula algebraica no había qué? Registro de n- tan logaritmo en base dos de n. Y no tenemos que entrar en demasiado muchos detalles sobre los logaritmos de hoy, pero la mayoría de los informáticos no lo haría incluso le dirá lo que es la base. Debido a que todo es sólo factores constantes, por así decirlo, sólo ligeras diferencias numéricas. Y así, esta sería una muy comunes camino para ordenador particular formales los científicos en una junta o programadores en un tablero blanco En realidad el argumento de los cuales algoritmo que usarían o lo que la eficiencia de su algoritmo es. 

Y esto no es necesariamente algo se discute en gran detalle, pero un buen programador es alguien que tiene un fondo sólido y formal. Él es capaz de hablar con que en este tipo de camino y hacer de argumentos cualitativos como de por qué un algoritmo o una pieza de software es superior en alguna forma a otra. Debido a que ciertamente se podría basta con ejecutar el programa de una persona y contar el número de segundos que se necesita para solucionar algunos números, y se puede ejecutar algunos El programa de otra persona y contar el número de de segundos que tarda. Pero esta es una manera más general que se puede utilizar para analizar los algoritmos, si se quiere, sólo en papel o sólo verbalmente. Sin ni siquiera ejecutarlo, sin incluso tratando de entradas de muestra, sólo puede razonar a través de él. Y así, con la contratación de un desarrollador o si que él o ella una especie de discutir con usted Por eso su algoritmo, su secreto salsa para buscar miles de millones de páginas web para su empresa es mejor, estos son los tipos de argumentos que idealmente debería ser capaz de hacer. O, al menos, estos son el tipo de cosas que habría surgido en la discusión, en menos en una discusión muy formal. Todo bien. Así Ben propuso algo llamada ordenación por selección. Pero voy a proponer que hay otras maneras de hacer esto, también. Lo que no me gusta mucho sobre el algoritmo de Ben es que él siguió caminando, o habiendo a caminar, de ida y vuelta y de ida y vuelta y de ida y vuelta. ¿Y si en vez tuviera que hacer algo así como estos números aquí y tuviera que lidiar solo con cada uno número a su vez que a mí se da? 

En otras palabras, aquí está mi lista de números. Cuatro, uno, tres, dos. Y voy a hacer lo siguiente. Voy a insertar los números a la que pertenecen más bien que seleccionándolas una a la vez. En otras palabras, este es el número cuatro. 

Aquí está mi lista original. Y voy a mantener esencialmente una nueva lista aquí. Así que esta es la lista de edad. Esta es la lista nueva. Veo el número cuatro en primer lugar. Mi nueva lista está vacía inicialmente, por lo que es trivial el caso que cuatro está ahora lista variados. Sólo estoy tomando el número que me dan, y lo estoy poniendo en mi nueva lista. 

Se ordena esta nueva lista? Sí. Es estúpido porque sólo hay una elemento, pero es absolutamente ordenada. No hay nada fuera de lugar. Es más interesante, este algoritmo, cuando muevo a la siguiente etapa. 

Ahora tengo uno. Así que, por supuesto, pertenece a la principio o al final de esta nueva lista? El principio. Así que tengo que hacer un trabajo ahora. He estado tomando algunos libertades con mi marcador con sólo dibujar cosas donde los quiero, pero eso no es realmente exacta en un ordenador. Un equipo que, como se sabe, tiene RAM, o memoria de acceso aleatorio, y eso es un byte y otro byte y otro byte. Y si tiene un gigabyte de RAM, que tiene mil millones de bytes, pero están físicamente en un solo lugar. No se puede simplemente mover cosas de un lado dibujando en la pizarra donde quieras. Así que si mi nueva lista tiene cuatro ubicaciones en la memoria, por desgracia, el cuatro es Ya en el lugar equivocado. 

Así que para insertar el número uno No puedo dibujar aquí. Esta posición de memoria no existe. Eso sería hacer trampa, y han sido trampa pictóricamente durante unos minutos aquí. Así que en realidad, si yo quiero poner uno aquí, Tengo que copiar temporalmente los cuatro y luego poner el uno allí. 

Eso está bien, eso es correcto, eso es técnicamente posible, pero se dan cuenta de que es un trabajo extra. Yo no sólo hay que poner el número en su lugar. La primera vez que tuve que mover una número, a continuación, poner en su lugar, así que tipo de doblé mi cantidad de trabajo. Así que tenlo en mente. 

Pero ahora estoy hecho con este elemento. Ahora quiero agarrar el número tres. Donde, por supuesto, pertenece? Entre. No puedo engañar más y sólo hay que poner allí, porque, de nuevo, esta memoria está en ubicaciones físicas. Así que tengo que copiar los cuatro y poner el tres por aquí. No es un gran trato. Es sólo un paso adicional nuevo-- se siente muy barato. 

Pero ahora de pasar a los dos. Los dos, por supuesto, pertenece aquí. Ahora se empieza a ver cómo el trabajo puede acumularse. Ahora, ¿qué tengo que hacer? Sí, tengo que mover los cuatro, entonces tengo que copiar los tres, y ahora puedo insertar los dos. Y la captura con este algoritmo, curiosamente, es que supongamos que tenemos una manera más extrema caso en el que es digamos ocho, siete, seis, cinco, cuatro, tres, dos, uno. Esto es, en muchos contextos, el peor de los casos, porque la maldita cosa es literalmente hacia atrás. 

En realidad no afectará algoritmo de Ben, porque en la selección de Ben especie que va a mantener ir arriba y abajo por la lista. Y debido a que estaba siempre en busca a través de toda la lista restante, No importa donde los elementos son. Pero en este caso con mi inserción approach-- vamos a probar esto. 

Así que uno, dos, tres, cuatro, cinco seis SIETE OCHO. Uno dos tres CUATRO, cinco seis SIETE OCHO. Voy a tomar el ocho, y dónde lo pongo? Bueno, al principio de la lista, ya que esta nueva lista está ordenada. Y cruzo hacia fuera. 

¿Dónde pongo los siete? Maldita sea. Tiene que ir allí, por lo Tengo que hacer algunas copias. Y ahora los siete va aquí. Ahora de pasar a los seis. Ahora es aún más trabajo. 

La octava tiene que ir aquí. Siete tiene que ir aquí. Ahora el seis pueden ir aquí. Ahora me agarra el cinco. Ahora los ocho tiene que ir aquí, siete tiene que ir aquí, seis tiene que ir aquí, y Ahora los cinco y repetir. Y estoy más o menos moviendo constantemente. 

Así que al final, esto vamos a algorithm-- llamarlo inserción sort-- realidad tiene un montón de trabajo, también. Es simplemente diferente tipo de trabajo que Ben. El trabajo de Ben me había vuelvo de ida y vuelta todo el tiempo, la selección de la siguiente más pequeña elemento y otra vez. Por lo que era este tipo muy visual de la obra. 

Este otro algoritmo, que todavía está correct-- que conseguirá el trabajo done-- Sólo cambia la cantidad de trabajo. Parece que inicialmente eres el ahorro, porque estás solo tratar con cada elemento por adelantado sin tener que caminar todo el camino a través de la lista como Ben era. Pero el problema es, sobre todo en estos locas casos en los que es todo al revés, eres sólo un poco posponer el trabajo duro hasta que tenga que corregir sus errores. 

Y por lo que si se puede imaginar esto ocho y siete y seis y cinco y más tarde de cuatro y tres y dos mover su camino a través de la lista, que acaba de cambiar el tipo de trabajo que estamos haciendo. En lugar de hacerlo en el a partir de mi iteración, Sólo estoy haciendo en el final de cada iteración. Así que resulta que este algoritmo, también, generalmente se llama ordenación por inserción, También está en el orden de n al cuadrado. En realidad no es mejor, no son mejores para todos. 

Sin embargo, hay un tercer enfoque Yo nos animaría a considerar, que es esto. Así que supongo que mi lista, por simplicidad de nuevo, es de cuatro, uno, tres, dos-- sólo cuatro números. Ben tenía buena intuición, buena intuición humana antes, por el cual se fijó la totalidad eventually-- lista de ordenación por inserción. Yo nos engatusé lo largo. Pero vamos a considerar la forma más sencilla de solucionar esta lista. 

Esta lista no está ordenada. ¿Por qué? En Inglés, explicar por qué En realidad no es ordenada. ¿Qué quiere decir que ser resuelto? 

ESTUDIANTE: No es secuencial. 

DAVID MALAN: no secuencial. Dame un ejemplo. 

ESTUDIANTE: Poner en orden. 

DAVID MALAN: OK. Dame un ejemplo más específico. 

ESTUDIANTE: orden ascendente. DAVID MALAN: fin de no ascender. Ser más precisos. No sé qué quiere decir con ascendente. ¿Qué ocurre? 

ESTUDIANTE: El más pequeño de la números no es en el primer espacio. 

DAVID MALAN: número más pequeño de no en el primer espacio. Sé más específico. Estoy empezando a hacerse popular. Estamos contando, pero lo que está fuera de aquí? 

ESTUDIANTE: secuencia numérica. DAVID MALAN: secuencia numérica. tipo de mantenimiento de todo el mundo que aquí-- nivel muy alto. Sólo literalmente, dime lo que es mal como lo haría una y cinco años de edad. 

ESTUDIANTE: más uno. 

DAVID MALAN: ¿Qué es eso? 

ESTUDIANTE: más uno. 

DAVID MALAN: ¿Qué quiere decir que uno más? Dame una diferente de cinco años de edad. ¿Qué pasa, mamá? ¿Qué pasa, papá? ¿Qué quiere decir esto no está ordenada? 

ESTUDIANTE: No es el lugar correcto. 

DAVID MALAN: ¿Cuál es no en el lugar correcto? 

ESTUDIANTE: Cuatro. DAVID MALAN: OK, bueno. Así que cuatro no es donde tiene que estar. En particular, ¿es esto correcto? Cuatro y uno, el primero dos números que veo. ¿Es esto correcto? No, están fuera de orden, ¿verdad? De hecho, piensa ahora acerca de un equipo, también. Sólo puede mirar en tal vez uno, tal vez dos cosas a la vez-- y en realidad sólo una cosa a la vez, pero al menos puede mirar a una cosa, entonces el Lo siguiente que justo al lado de ella. 

Así son estos con el fin? Por supuesto no. Así que ya saben qué? ¿Por qué no tomamos bebé etapas de fijación de este problema en lugar de hacer estos de lujo algoritmos como Ben, donde Es una especie de fijación por bucle a través de la lista en vez de hacer lo que hice, donde Yo sólo tipo de fijo que a medida que avanzamos? Vamos a romper, literalmente, por la noción de orden numérico order--, Llámalo como quieras-- en estas comparaciones por pares. 

Cuatro y uno. Es este el orden correcto? Así que vamos a arreglar eso. Uno y cuatro, y luego sólo tendremos que copiamos. Muy bien, muy bien. Me fijo uno y cuatro. Tres y dos? No. Que mis palabras coincidan con los dedos. Cuatro y tres? 

No es el fin, así que voy hacer uno, tres, cuatro, dos. Bien. Ahora cuatro y dos? Tenemos que arreglar esto, también. Así que uno, tres, dos, cuatro. Así se lo arregló? No, pero es lo más cerca ordenados? 

Es, pues hemos arreglado este error, hemos arreglado este error, y hemos arreglado este error. Así que podría decirse que lo arreglaron tres errores. Aún en realidad no mirar ordenada, pero es objetivamente más cerca ordenada porque hemos arreglado algunos de esos errores. 

Ahora, ¿qué hago ahora? Yo como que llegó al final de la lista. Me parecía haber fijado todos los errores, pero no. Porque en este caso, algunos números podría haber burbujeaba más cerca a otros números que todavía están fuera de servicio. Así que vamos a hacerlo de nuevo, y voy a sólo lo hacen en su lugar esta vez. Uno y tres? Está bien. Tres y dos? Por supuesto que no, así que vamos a cambiar. Así que dos, tres. Tres y cuatro? Y ahora vamos a ser particularmente pedante aquí. Se lo arregló? Usted sabe que es el ser humano ordenadas. 

Debería intentarlo de nuevo. Así que Olivia está proponiendo lo intento de nuevo. ¿Por qué? Debido a que un equipo no tiene el lujo de los ojos humanos de simplemente echando un vistazo espaldas; OK, he terminado. ¿Cómo determina el equipo que la lista está ordenada ahora? Mecánicamente. 

Debería ir a través una vez más, y sólo si No hacer / algún comentario sobre errores puedo entonces la conclusión de que el equipo, sip, somos buenos para ir. Así uno y dos, dos y tres, tres y cuatro. Ahora definitivamente puedo decir que es ordenados, porque he hecho ningún cambio. Ahora bien, sería un error y justo tonto si yo, el equipo, hecho estas mismas preguntas una esperando respuestas diferentes. no debería suceder. 

Y por lo que ahora se ordena la lista. Desafortunadamente, el tiempo de funcionamiento de este algoritmo es n al cuadrado. ¿Por qué? Debido a que tiene un número n, y en el peor de los casos se tiene que mover un número n n veces porque hay que seguir adelante volver a comprobar y corregir potencialmente estos números. Y podemos hacer un mayor análisis formal, también. 

Así que esto es todo lo que decir que hemos tomado tres enfoques diferentes, uno de ellos inmediatamente intuitiva del palo de Ben a mi se ha sugerido, ordenar a ésta donde tipo de pierde de vista el bosque por los árboles inicialmente. Pero entonces, si usted toma un paso atrás, voilá, hemos fijado la noción de clasificación. Así que esto es, se atreve a decir, un nivel más bajo quizá que algunos de los otros algoritmos, pero vamos a ver si no podemos visualizar estos por medio de esto. 

Así que esto es una buena software que alguien escribió usando barras de colores que de vamos a hacer lo siguiente para nosotros. Cada una de estas barras representa un número. Taller de la barra, mayor el número, más pequeña es la barra, cuanto menor sea el número. Por lo que idealmente queremos un buen pirámide donde empieza pequeño y se llena grande, y eso significaría que estas barras están ordenados. Así que voy a seguir adelante y elegir, por ejemplo, el algoritmo de Ben la selección primero-- tipo. 

Y observe lo que está haciendo. La forma en que han elegido visualizar este algoritmo es que, al igual que yo caminando a través de mi lista, este programa está caminando a través de su lista de números, destacando en rosa cada número que se está mirando. Y lo que va a ocurrir ahora? 

El número más pequeño que Me encontré de repente o Ben obtiene movido al principio de la lista. Y el aviso que hicieron evict el número que estaba allí, y que está perfectamente bien. No me meto en ese nivel de detalle. Pero tenemos que poner ese número en alguna parte, por lo que acabamos de mudar a la lugar abierto que fue creado. Así que voy a acelerar este , porque de lo contrario, se vuelve muy tedioso rápidamente. Animación speed-- haya que ir. Así que ahora mismo principio Yo estaba aplicando, pero puede comenzar a sentir el algoritmo, si voluntad, ni se ve un poco más claramente. Y este algoritmo tiene el efecto de seleccionar el siguiente elemento más pequeño, por lo que vamos a empezar a ver que la rampa encima de la izquierda. Y en cada iteración, como yo propuesto, se hace un poco menos de trabajo. No tiene que ir todo el camino de nuevo al extremo izquierdo de la lista, porque ya conoce a los se ordenan. Así que tipo de se siente como si fuera acelerando, a pesar de que cada paso es teniendo la misma cantidad de tiempo. Sólo hay un menor número de pasos restantes. Y ahora se puede sentir el tipo de algoritmo de limpieza al final de ella, y de hecho ahora se ha solucionado. 

Así ordenación por inserción se hace todo. Tengo que volver a cambiar aleatoriamente la matriz. Y note que sólo puede mantener la aleatorización de ella, y nos pondremos una aproximación de el mismo enfoque, la ordenación por inserción. Permítanme retardarlo hasta aquí. Vamos a empezar que más. Detener. 

Vamos a saltar cuatro. Aquí vamos. Selección aleatoria de ellos matriz. Y aquí vaya-- ordenación por inserción. Jugar. Tenga en cuenta que se trata de cada uno elemento que encuentra de forma inmediata, pero si pertenece en el lugar equivocado aviso todo el trabajo que tiene que suceder. Tenemos que seguir desplazándose más y más elementos para hacer espacio para el que queremos poner en su lugar. 

Así que nos estamos enfocando en el extremo izquierdo de la lista única. Aviso ni siquiera hemos visto que at-- no han puesto de relieve en rosa nada a la derecha. Estamos frente a los problemas a medida que avanzamos, pero estamos creando una gran cantidad de trabajar para nosotros mismos todavía. Y por lo que si acelerar esto ahora ir hasta su finalización, tiene una sensación diferente a él de hecho. Es sólo centrándose en el extremo izquierdo, pero haciendo un poco más de trabajo como needed-- tipo de cosas suavizado encima, arreglar cosas, pero en última instancia se trata con cada elemento de una en una hasta llegar a el-- bueno, Todos sabemos cómo va a terminar, así que es un poco decepcionante, tal vez. 

Pero la lista en el end-- spoiler-- va a ser resuelto. Así que vamos a ver una última uno. No podemos simplemente saltar ahora. Casi estámos allí. Quedan dos, uno para ir. Y listo. Excelente. 

Así que ahora vamos a hacer una última, volver a la aleatorización con la ordenación de burbuja. Y noto aquí, especialmente si retardarlo abajo, esto deslizándose por mantener. Pero nótese que sólo tiene dos a dos comparisons-- tipo de soluciones locales. Pero tan pronto como se llega a Al final de la lista en rosa, lo que va a tener que pasar de nuevo? Sí, va a tener que empezar de nuevo, ya que sólo errores fijos por pares. Y que podría haber revelado aún otros. Y por lo que si acelerar este proceso, se le ver que, tanto como el nombre implica, la más pequeña elements-- o más bien, elements-- los más grandes están comenzando que suben a la parte superior, si se quiere. Y los elementos más pequeños son empezando a burbuja hacia abajo a la izquierda. Y, en efecto, que es una especie de el efecto visual. Y así, esto va a terminar el acabado de una manera muy similar, también. 

No tenemos habitar en este caso en particular. Permítanme abrir esto ahora, también. Hay algunos otros algoritmos de ordenación en el mundo, algunos de los cuales son capturados aquí. Y especialmente para los estudiantes que no están necesariamente visual o matemática, como lo hicimos antes, podemos También hacer esto audially si asociar un sonido a esto. Y sólo por diversión, he aquí una unos algoritmos diferentes, y uno de ellos, en particular, que está va a notar que se llama "fusión especie." 

En realidad, es una forma fundamentalmente mejor algoritmo, de tal manera que se funden especie, una de los que están a punto de ver, No es el fin de n al cuadrado. Es del orden de n veces de registro n, que es en realidad más pequeño y por lo tanto más rápido que los otros tres. Y hay un par de otro los tontos que ya veremos. 

Así que aquí vamos con un poco de sonido. Esta es la ordenación por inserción, así que de nuevo es sólo tratar con los elementos como vienen. Se trata de una especie de burbuja, por lo que es teniendo en cuenta los pares a la vez. Y de nuevo, los elementos más importantes están burbujeando hasta la parte superior. 

Selección El siguiente tipo. Este es el algoritmo de Ben, donde De nuevo se ha de seleccionar de forma iterativa el elemento inmediatamente inferior. Y de nuevo, ahora se puede escuchar que realmente está acelerando, pero sólo en la medida en como lo está haciendo cada vez menos trabajar en cada iteración. Este es el más rápido, combinar especie, que se clasificar grupos de números combinando juntos y luego ellos. Así look-- la izquierda la mitad ya está ordenada. 

Ahora está la clasificación de la mitad derecha, y Ahora se va a combinar en una sola. Esto es algo que se llama "Gnome tipo." Y se puede ver que tipo de que va de ida y vuelta, la fijación de trabajo un poco aquí y no antes de proceder al nuevo trabajo. Y eso es. Hay otro tipo, que es en realidad sólo con fines académicos, llamada "clase estúpida", que tiene sus datos, que ordena al azar, y luego comprueba si está ordenada. Y si no lo es, se volverá a ordenar que al azar, comprueba si está ordenada, y si no se repite. Y, en teoría, probabilísticamente Esto completará, pero después de un poco de tiempo. No es el más eficiente de los algoritmos. Así que cualquier pregunta sobre los algoritmos o cualquier particulares relacionada con ellas, también? 

Bueno, ahora vamos a desmenuzar lo que todos estas líneas son que he estado dibujando y lo que estoy suponiendo que el ordenador puede hacer debajo de la campana. Yo diría que todos estos números Sigo drawing-- que necesitan para obtener almacenado en algún lugar de la memoria. Vamos a deshacernos de este tipo ahora, también. 

Así que una pieza de la memoria en una computer-- por lo DIMM RAM es lo que se realizaron búsquedas de ayer, dual module-- de memoria en línea tiene este aspecto. Y cada una de estas pequeñas fichas negras es un número de bytes, por lo general. Y a continuación, los alfileres de oro son como el cables que se conectan a la computadora, y la placa de silicio verde es sólo lo que mantiene todo junto. Entonces, ¿qué significa esto realmente? Si este tipo de dibujo misma imagen, Supongamos por simplicidad que este DIMM, dual módulo de memoria en línea, es un gigabyte de memoria RAM, un gigabyte de memoria, que es el número de bytes en total? Un gigabyte es el número de bytes? Más que eso. 1.124 es el kilo, 1.000. Mega es millones. Giga es un mil millones. 

¿Estoy mintiendo? Podemos incluso leer la etiqueta? Esto es en realidad 128 gigabytes, por lo que es mucho más. Pero vamos a pretender este es sólo un gigabyte. Por lo que significa que hay un mil millones bytes de memoria disponibles para mí o 8 mil millones de bits, pero vamos para hablar en términos de bytes ahora, avanzar. 

Así que lo que esto significa es que esto es un byte, esto es otro byte, este es otro byte, y si realmente queríamos para ser específicos, tendríamos que dibujar un billón de pequeños cuadrados. Pero ¿qué significa eso? Bueno, permítanme zoom en esta imagen. Si tengo algo que parece así ahora, eso es cuatro bytes. 

Y por lo que podría poner cuatro números aquí. Uno dos tres CUATRO. O podría poner cuatro letras o símbolos. "¡Oye!" podría ir allí, porque cada una de las letras, hemos comentado anteriormente, podría ser representado con ocho bits o ASCII o un byte. Así, en otras palabras, se puede poner 8 mil millones de cosas en el interior de este un palo de memoria. Ahora, ¿qué significa para poner las cosas con espalda con espalda en la memoria de esta manera? Esto es lo que un programador llamaría una "matriz". En un programa de ordenador, que no creo sobre el hardware subyacente, per se. Usted sólo piensa en sí mismo como teniendo acceso a un total de mil millones de bytes, y se puede lo que quiera con ella. Pero por conveniencia generalmente es útil para mantener su derecho de memoria uno junto al otro como este. Así que si hago zoom sobre esto- porque desde luego no vamos para dibujar un billón de pequeños squares-- vamos a suponer que este tablero representa que palo de la memoria ahora. Y sólo voy a señalar a todos los que mi marcador termina por darme aquí. Así que ahora tenemos un palo de memoria de la placa eso tiene uno, dos, tres, cuatro, cinco, seis, uno, dos, tres, cuatro, cinco, seis, seven-- así que 42 bytes de memoria en el total de la pantalla. Gracias. Sí, lo hizo mi aritmética derecha. Por lo que 42 bytes de memoria aquí. Entonces, ¿qué significa esto realmente? Bueno, un programador de computadoras en realidad generalmente pensar en esta memoria como direccionable. En otras palabras, cada uno de estos ubicaciones en la memoria, en hardware, tiene una dirección única. 

No es tan complejo como un Brattle Square, Cambridge, Mass., 02138. En cambio, es sólo un número. Este es el número de bytes cero, esto es uno, esto es dos, esto es tres, y esto es 41. Espera un minuto. Pensé que dije hace un momento 42. Empecé a contar desde cero, por lo que es realmente correcto. Ahora no tenemos que llamar la realidad como una rejilla, y si lo dibuja como una cuadrícula Creo que las cosas realmente ser un poco engañoso. ¿Qué haría un programador, en su propia mente, en general, pensar en esto la memoria como es como una cinta, como un trozo de cinta adhesiva eso es sólo una y otra vez para siempre o hasta que se agote la memoria. Así que de una manera más común para dibujar y sólo pensar en la memoria sería que esto es byte cero, uno, dos, tres, y después del punto, punto, punto. Y usted tiene 42 de esos bytes en total, incluso aunque físicamente en realidad podría ser algo más parecido a esto. 

Así que si usted ahora piensa en su la memoria, ya que, al igual que una cinta, esto es lo que un programador nuevo llamaría a una matriz de memoria. Y cuando se desea almacenar en realidad algo en la memoria de un ordenador, por lo general, se debe de conservar las cosas espalda con espalda con espalda con espalda. Así que hemos estado hablando de números. Y cuando yo quería para resolver problemas como cuatro, uno, tres, dos, a pesar de que yo estaba dibujando sólo el número cuatro, uno, tres, dos de la mesa, la computadora realmente tienen esta configuración en la memoria. 

Y lo que sería al lado de la dos en la memoria del ordenador? Bueno, no hay una respuesta a eso. No se sabe muy bien. Y siempre que la equipo no lo necesita, que no tiene que preocuparse de lo que es el próximo a los números que se preocupa por. Y cuando he dicho antes que una computadora sólo puede mirar en una dirección a la vez, esto es una especie de por qué. 

No a diferencia de un registro jugador y un cabezal de lectura sólo ser capaz de mirar a una cierta ranura en un registro físico de la vieja escuela a la vez, de manera similar puede un ordenador gracias a su CPU y su conjunto de instrucciones Intel, entre cuyas instrucciones se lee de la memoria o guardar en un memory-- equipo sólo puede mirar en un lugar en un tiempo-- a veces una combinación de ellos, pero en realidad un solo lugar a la vez. Así que cuando hacíamos estos diversos algoritmos, No sólo estoy escribiendo en una vacuum-- cuatro, uno, tres, dos. Esos números pertenecen en realidad en algún lugar físico en la memoria. Así que hay diminuto transistores o algún tipo de la electrónica debajo de la campana de almacenamiento de estos valores. 

Y en total, el número de bits involucrado en este momento, sólo para ser claros? Así que esto es de cuatro bytes, o ahora es 32 bits en total. Así que en realidad hay 32 ceros y los que componen estas cuatro cosas. Hay aún más por aquí, pero de nuevo, no se preocupan por eso. 

Así que ahora vamos a pedir otra pregunta usando la memoria, porque que al final del día es la varianza. No importa lo que podríamos hacer con el equipo, al final del día el hardware es todavía el misma debajo de la campana. ¿Cómo iba a almacenar una palabra en esta lista? Pues bien, una palabra en un equipo como "¡Oye!" se almacenaría como este. Y si quería una más larga palabra, sólo tiene que sobrescribir y que decir algo así como "hola" y tienda que aquí. 

Y así, también, esta contigüidad es en realidad una ventaja, debido a que un equipo puede simplemente lee de derecha a izquierda. Pero he aquí una pregunta. En el contexto de esta palabra, h-e-l-l-o, signo de exclamación, ¿Cómo podría el equipo saber dónde está el palabra empieza y donde termina la palabra? En el contexto de los números, ¿Cómo funciona el equipo saber cuánto tiempo la secuencia de números es o dónde comienza? Bueno, resulta out-- y no vamos a ir demasiado en este nivel de detail-- computadoras mueven la materia alrededor en la memoria literalmente, a través de estas direcciones. Así que en un ordenador, si estás escribir código para almacenar cosas como las palabras, lo que está haciendo en realidad está escribiendo expresiones que recuerdan en donde la memoria del ordenador estas palabras son. Así que déjame hacer un muy, ejemplo muy sencillo. 

Voy a seguir adelante y abrir un programa de texto simple, y yo voy a crear un archivo llamado hola.c. La mayor parte de esta información, No voy a entrar en gran detalle, pero voy a escribir una programa en el mismo idioma, C. Esto es mucho más intimidante, Yo diría, que rascar, pero es muy similar en espíritu. De hecho, estos rizado braces-- puedas tipo de pensar en lo que he hecho como este. 

Vamos a hacer esto, en realidad. Cuando hace clic en bandera verde, Haz lo siguiente. Quiero imprimir "hola". Así que esto es ahora pseudocódigo. Soy una especie de desdibujar las líneas. En C, este idioma estoy hablando aproximadamente, esta línea de impresión hola en realidad se convierte en "printf" con algunos paréntesis y un punto y coma. 

Pero es la misma idea exacta. Y esto muy fácil de usar "Cuando se hace clic en bandera verde" se convierte el más arcano "void main int." Y esto realmente sin ninguna asignación, así que sólo voy a ignorar eso. Sin embargo, las llaves son como el piezas del rompecabezas curvas de este tipo. 

Por lo que puede tipo de adivinar. Incluso si nunca has programado antes, ¿qué hace este programa probablemente hacer? Probablemente imprime hola con un signo de exclamación. 

Así que vamos a tratar de eso. Voy a guardarlo. Y esto es, de nuevo, una muy entorno de la vieja escuela. No puedo hacer clic, no puedo arrastrar. Tengo que escribir comandos. Por eso quiero correr mi programa, por lo Yo podría hacer esto, al igual que hola.c. Ese es el archivo me encontré. Pero espera, que me falta un paso. ¿Qué dijimos es una condición necesaria paso para un lenguaje como C? He fuente acaba de escribir código, pero ¿qué necesito? Sí, necesito un compilador. Así que en mi Mac aquí, tengo una programa llamado GCC, GNU compilador de C, lo que me permite hacer esto- a su vez mi código fuente en, lo llamaremos, codigo de maquina. 

Y puedo ver que, de nuevo, de la siguiente manera, estos son los ceros y unos I solo creado a partir de mi código fuente, todos los ceros y unos. Y si quiero correr mi program-- sucede para ser llamado a.out para reasons-- histórica "hola". Puedo correr de nuevo. Hola hola hola. Y parece que funciona. 

Pero eso significa que en algún lugar de mi la memoria del ordenador son las palabras h-e-l-l-o, signo de exclamación. Y resulta que, al igual que un aparte, lo que un ordenador haría normalmente hacer para que sepa donde las cosas empiezan y es end-- va a poner un símbolo especial aquí. Y la convención es poner el número cero al final de una palabra para que sepa donde en realidad termina, por lo que se no seguir imprimiendo más y más caracteres de los que en realidad se proponen. 

Pero la comida para llevar aquí, incluso aunque esto es bastante arcano, es que es en última instancia, relativamente simple. Se le dio una especie de cinta, un espacio en blanco espacio en el que puede escribir letras. Usted simplemente tiene que tener una símbolo especial, al igual que de manera arbitraria el número cero, para poner al final de sus palabras para que la computadora sabe, Oh, debería detener la impresión después de Veo el signo de exclamación. Porque lo siguiente que hay es un valor ASCII de cero, o el carácter nulo como alguien lo llamaría. Pero hay una especie de un problema aquí, y vamos a volver de nuevo a los números por un momento. Supongamos que hago, de hecho, dispondrá de un conjunto de números, y supongamos que la programa que estoy escribiendo es como un libro de calificaciones de un maestro y un aula de profesores. Y este programa le permite para escribir en las puntuaciones de los estudiantes en las pruebas. Y supongamos que el estudiante obtiene 100 en su primer concurso, tal vez como un 80 en la próxima, a continuación, una 75, luego a 90 en la cuarta prueba. 

Así que en este punto de la historia, la matriz es de un tamaño cuatro. No hay absolutamente más memoria en el ordenador, pero la matriz, por así decirlo, es de tamaño cuatro. Supongamos ahora que el profesor quiere para asignar una quinta prueba para la clase. Bueno, una de las cosas que él o ella va a tener que hacer ahora es almacenar un valor adicional aquí. Pero si la matriz tiene el maestro creado en este programa es de tamaño para, uno de los problemas con una matriz que es no se puede simplemente seguir añadiendo a la memoria. Porque lo que si otra parte de la programa tiene la palabra "hey" justo ahí? 

En otras palabras, la memoria puede ser utilizado para cualquier cosa en un programa. Y si de antemano Tecleé, hey, Quiero entrada de cuatro puntuaciones de las pruebas, que podrían ir aquí y aquí. Y si cambia de parecer rápidamente más tarde y decir que quiero un quinto concurso puntuación, no se puede simplemente puesto que más le convenga, porque lo que si esta se utiliza la memoria por algo else-- algún otro programa o alguna otra característica del programa que se está ejecutando? Así que hay que pensar de antemano la forma en la que desea almacenar sus datos, porque ahora se ha pintado a sí mismo en una esquina digital. 

Por lo que un profesor puede en cambio decir al escribir un programa para almacenar su grados, ¿saben qué? Voy a solicitar, al escribir mi programa, Quiero que cero, uno, dos, tres, cuatro, cinco, seis, ocho grados en total. Así que uno, dos, tres, cuatro, cinco seis SIETE OCHO. El profesor puede simplemente sobreasigne la memoria al escribir su programa y decir, ¿saben qué? Nunca voy a asignar más de ocho pruebas en un semestre. Eso es una locura. Nunca voy a asignar ese. Así que de esta manera él o ella tiene la flexibilidad a la puntuación de tienda de los estudiantes, como 75, 90, y tal vez uno adicional donde el estudiante tiene el crédito adicional, 105. 

Pero si el maestro nunca utiliza estos tres espacios, hay una comida para llevar intuitiva aquí. Él o ella está perdiendo espacio. Así, en otras palabras, hay una desventaja común en la programación donde puede asignar exactamente como la cantidad de memoria que desee, al alza de los cuales es que eres muy efficient-- no estás siendo un desperdicio en todo-- pero la desventaja de los cuales es lo que si cambia de opinión cuando usando el programa que desea almacenar más datos que los que originalmente previsto. 

Así que tal vez la solución es, entonces, escribir sus programas de tal manera que utilizan más memoria de lo que realmente necesitan. De esta manera no vas a ejecutar en ese problema, pero estás siendo un desperdicio. Y cuanto más memoria utiliza su programa, como dijimos ayer, menos la memoria que está disponible para otros programas, cuanto antes el equipo podría ralentizar a causa de la memoria virtual. Y así, la solución ideal podría ser qué? 

Bajo-se reparten parece mal. Sobre-el que se reparten parece mal. Entonces, ¿qué podría ser una solución mejor? La reasignación. Ser más dinámico. No se obligue a elegir un a priori, al principio, lo que quieren. Y ciertamente no sobreasigne, para que no sea un desperdicio. 

Y así, para lograr ese objetivo, necesitar descargar a esta estructura de datos, por así decirlo, de distancia. Y así lo que un programador normalmente utilizará es algo que se llama no es una matriz, pero una lista enlazada. En otras palabras, él o ella comenzar a pensar en su memoria como una especie de forma que se puede sacar de la siguiente manera. Si quiero almacenar un número en un program-- por lo que es de septiembre Me he dado a mis estudiantes un cuestionario; yo quiero para almacenar la primera prueba de los estudiantes, y consiguieron un 100 en it-- I voy a pedir a mi equipo, por medio del programa que he por escrito, por un trozo de memoria. Y voy a almacenar el número 100 en el mismo, y eso es todo. 

A continuación, unas semanas más tarde cuando llego a mi segunda prueba, y es el momento de escribir en el que el 90%, voy preguntar al equipo, hey, ordenador, puedo tener otro trozo de memoria? Se me va a dar a este trozo vacío de la memoria. Voy a poner en el número 90, pero en mi programa de una manera u otro-- y no vamos a preocuparse por la sintaxis para esto- que necesito de alguna manera encadenar estas cosas juntas. Y les voy a encadenar con lo que parece una sola flecha. 

El tercer cuestionario que aparece, Voy a decir, oye, ordenador, dame otra parte de la memoria. Y voy a poner en el suelo lo que fuera, al igual que 75, y tengo que esta cadena de juntos ahora de alguna manera. Cuarta prueba viene, y tal vez eso es hacia el final del semestre. Y en ese momento mi programa podría ser el uso de la memoria por todo el lugar, todo físicamente. Y así, sólo por diversión, yo soy va a sacar esta vuelta quiz-- me olvido de lo que era; yo pensar que tal vez un 80 o algo-- hasta aquí. 

Pero eso está bien, porque pictóricamente Voy a trazar esta línea. En otras palabras, en la realidad, en el hardware del ordenador, la primera puntuación podría terminan aquí porque es justo al comienzo del semestre. El próximo podría terminar aquí porque un poco de tiempo ha pasado y el programa sigue funcionando. La puntuación siguiente, que era un 75, podría ser aquí. Y la última puntuación podría ser un 80, que es por aquí. 

Así que, en realidad, físicamente, esto podría ser lo que la memoria de su ordenador se parece. Pero esto no es un trastorno mental útil paradigma para un programador de computadoras. ¿Por qué debe tener cuidado cuando el diablos sus datos está terminando para arriba? Lo que desea es almacenar datos. 

Esto es algo así como nuestra discusión antes de sacar el cubo. ¿Por qué te importa lo el ángulo es del cubo y cómo se tiene que dar vuelta a dibujar? Lo que desea es un cubo. Del mismo modo aquí, sólo quieren libro de calificaciones. Lo que desea es pensar esto como una lista de números. A quién le importa cómo es implementado en hardware? 

Así que la abstracción ahora Es esta imagen aquí. Esta es una lista vinculada, como un programador lo llamaría, en la medida en que tiene una lista, obviamente, de los números. Pero está vinculado pictóricamente por medio de estas flechas, y todas estas flechas debajo son-- el capó, si tienes curiosidad, recordar que nuestro hardware físico tiene direcciones cero, uno, dos, tres, cuatro. Todas estas flechas son es como un mapa o direcciones, en la que si ahora 90 es-- Tengo que contar. 

Cero, uno, dos, tres, cuatro, cinco, seis, siete. Parece que el 90 es en memoria de número de dirección de siete. Todas estas flechas son es como un pequeño trozo de papel que es dar instrucciones a la programa que dice sigue este mapa para llegar al lugar de siete. Y allí se encuentra el segunda puntuación de la prueba de Student. Mientras tanto, el 75-- si continúo esto, esto es siete, ocho, nueve, 10, 11, 12, 13, 14, 15. 

Esta otra flecha representa solo un mapa de ubicación de la memoria 15. Pero, de nuevo, el programador hace generalmente no se preocupan por este nivel de detalle. Y en la mayoría de cada programación lenguaje de hoy, el programador ni siquiera saber dónde en la memoria estos números son en realidad. Todo lo que él o ella tiene que tener en cuenta es que de alguna manera están vinculados entre sí en una estructura de datos como este. 

Pero resulta que no para conseguir demasiado técnico. Pero el hecho de que tal vez puede permitirse el lujo de tener esta discusión aquí, Suponemos que volvamos esta cuestión aquí de una matriz. Vamos a ver si nos arrepentimos ir aquí. Esto es 100, 90, 75, y 80. 

Permítanme brevemente hacer esta afirmación. Esta es una matriz, y de nuevo, la característica sobresaliente de una matriz es que todos sus datos están de nuevo a espalda con espalda en memory-- literalmente Un byte o tal vez cuatro bytes, un número fijo de bytes de distancia. En una lista enlazada, que podríamos llamar la así, debajo de la campana que sabe dónde está eso? Ni siquiera se necesita para fluir como este. Algunos de los datos podría ser de vuelta a la izquierda hasta allí. Ni siquiera sabe. 

Y así, con una matriz, que tiene una característica conocida como acceso aleatorio. Y lo que los medios de acceso aleatorio es de que el equipo puede saltar al instante a cualquier lugar de una matriz. ¿Por qué? Debido a que la computadora sabe que la primera ubicación es cero, uno, dos, y tres. 

Y así que si quieres ir de este elemento al siguiente elemento, que, literalmente, en el la mente del ordenador, sólo tiene que añadir uno. Si quieres ir al tercer elemento, sólo tiene que añadir uno-- siguiente elemento, simplemente Agrega uno. Sin embargo, en esta versión de la historia, suponga el equipo está buscando actualmente en o por tratar con el número 100. ¿Cómo se llega a la siguiente grado en el libro de calificaciones? 

Usted tiene que tomar siete pasos, que es arbitrario. Para llegar a la siguiente, hay que tomar otros ocho pasos para llegar a 15. En otras palabras, no es una distancia constante entre los números, y por lo tanto sólo se necesita la equipo más tiempo es el punto. El equipo tiene que buscar a través de la memoria con el fin para encontrar lo que estás buscando. 

Así, mientras una matriz tiende a ser una structure-- rápida de datos, ya que literalmente, puede simplemente hacer aritmética simple y obtener en la que desea mediante la adición de uno, instance-- de una lista enlazada, se sacrifica esa característica. No se puede simplemente pasar de la primera la segunda a tercera a la cuarta. Usted tiene que seguir el mapa. Usted tiene que tomar más medidas para llegar a esos valores, los cuales parecería ser la adición de un costo. Así que estamos pagando un precio, pero lo que se la característica de que Dan estaba buscando aquí? ¿Cómo es una lista enlazada al parecer, nos permite hacer, que fue el origen de esta historia en particular? 

Exactamente. Un tamaño de dinámica a la misma. Podemos añadir a esta lista. Incluso podemos reducir la lista, por lo que sólo estamos utilizando tanta memoria ya que en realidad queremos y por lo nunca estamos sobre-el que se reparten. 

Ahora acaba de ser muy puntillosos, hay un costo oculto. Así que no debe dejar a convencer que este es un compromiso convincente. Hay otro coste oculto aquí. El beneficio, para ser claro, es que tenemos dinamismo. Si quiero otro elemento, sólo puede elaborar y poner un número en ese país. Y entonces puedo vincularlo con una imagen aquí, mientras que aquí, de nuevo, si tengo mí mismo pintado en una esquina, si algo más ya está utilizando la memoria aquí, estoy fuera de suerte. Yo mismo he pintado en la esquina. 

Pero lo que es lo oculto costaría en esta imagen? No es sólo la cantidad de tiempo que se tarda para ir desde aquí hasta aquí, que es siete pasos, entonces ocho pasos, que es más de uno. ¿Cuál es otra costo oculto? No sólo el tiempo. Información adicional está necesarias para lograr esta imagen. 

Sí, ese mapa, esos pequeños trozos de papel, como sigo describiéndolos como. Estos arrows-- los que no son libres. Un computer-- sabes lo que tiene un ordenador. Cuenta con ceros y unos. Si desea representar una flecha o una mapa o un número, se necesita algo de memoria. Así que el otro precio que pagar por una lista enlazada, una informática común de recursos, es también el espacio. 

Y de hecho es así, por lo común, entre las compensaciones en el diseño de la ingeniería de software sistemas requiere tiempo y espacio-- son dos de sus ingredientes, dos de sus ingredientes más costosos. Esto me está costando más tiempo porque tengo que sigue este mapa, Pero también me cuesta más espacio porque tengo que mantener este mapa alrededor. Por lo que la esperanza, como hemos tipo de discutido sobre el ayer y hoy, es que los beneficios serán mayores que los costos. 

Pero no hay una solución obvia aquí. Tal vez es mejor-- a la rápida y sucia, como Kareem propuso antes les hablé a tirar de memoria en el problema. Acaba de comprar más memoria, pensar menos tendido sobre la solución del problema, y resolverlo de una manera más fácil. Y, de hecho antes, cuando hablamos acerca de las compensaciones, no había espacio en equipo y la hora. Era tiempo de desarrollo, lo cual es un recurso más. 

Así que de nuevo, es este acto de equilibrio tratando de decidir cuál de esas cosas ¿está dispuesto a gastar? ¿Qué es el menos costoso? Que produce los mejores resultados? ¿Sí? 

En efecto. En este caso, si estás en representación de números en el maps-- estos son llamados en muchos idiomas "punteros" o "direcciones" - que es el doble de espacio. Eso no tiene por qué ser tan malo como el doble si en este momento sólo estamos almacenar números. Supóngase que se almacenaban registros de los pacientes en un hospital-- por lo que los nombres de Pierson, números de teléfono, números de seguridad social, médico historia. Este cuadro puede ser mucho, mucho más grande, en cuyo caso un diminuto puntero, la dirección de la próxima element-- que no es un gran problema. Es una franja tales cuesta no importa. Pero en este caso, sí, es una duplicación. Buena pregunta. 

Vamos a hablar de una vez poco más concreta. ¿Qué es el tiempo de ejecución de buscar esta lista? Supongamos que se quiere buscar a través de todos los grados de los estudiantes, y hay n grados en esta estructura de datos. Aquí, también, podemos pedir prestado el vocabulario de la anterior. Esta es una estructura de datos lineal. 

O grande de n es lo que se requiere para conseguir al final de esta estructura de datos, whereas-- y no hemos visto esto antes-- una matriz que da lo que se llama constante de tiempo, lo que significa un paso o dos pasos o 10 steps-- no importa. Es un número fijo. No tiene nada que ver con el tamaño de la matriz. Y la razón de que, de nuevo, es de acceso aleatorio. El ordenador puede simplemente inmediatamente saltar a otra ubicación, porque son todos iguales distancia de todo lo demás. No hay pensamiento involucrado. Todo bien. Así que si puedo, voy a tratar pintar dos cuadros finales. Uno muy común conocida como una tabla hash. Así que para motivar a esta discusión, déjame pensar acerca de cómo hacer esto. 

Así que ¿qué tal esto? Supongamos que el problema queremos resolver ahora está llevando a cabo en un dictionary-- por lo que un montón de palabras en inglés o lo que sea. Y el objetivo es ser capaz de responder preguntas de la forma se trata de una palabra? Por lo que desea aplicar un corrector ortográfico, justo como un diccionario física que se puede mirar las cosas en. Supongamos que yo fuera a hacer esto con una matriz. Yo podría hacer esto. 

Y supongamos que las palabras son la manzana y el plátano y melón. Y no puedo pensar en las frutas que empiezan con D., por lo que sólo estamos va a tener tres frutas. Así que esta es una matriz, y estamos almacenar todas estas palabras en este diccionario como una matriz. La pregunta es, entonces, ¿de qué otra se puede almacenar esta información? 

Bien, estoy tipo de trampa aquí, porque cada una de estas letras de la palabra es realmente un byte individual. Así que si realmente quería ser nit-exigente, que realmente debería se divide esto en gran parte trozos más pequeños de la memoria, y podríamos hacer exactamente eso. Pero vamos a ejecutar en el mismo problema que antes. ¿Qué pasa si, como Merriam Webster u Oxford ¿Tiene cada año-- añaden palabras a la dictionary-- no lo hacemos necesariamente quiere pintarnos en una esquina con una matriz? 

Así que en vez, tal vez un enfoque más inteligente es poner manzana en su propio nodo o caja, como diríamos, plátano, y entonces aquí tenemos melón. Y la cadena que estas cosas juntas. Así que esta es la matriz, y esta es la lista enlazada. Si no puede ver bien, sólo dice "matriz", y esto dice "lista". 

Así que tenemos la misma cuestiones exactas como antes, por lo que ahora tenemos dinamismo en nuestra lista enlazada. Pero tenemos un diccionario bastante lento. Supongamos que quiero buscar una palabra. Me podría tener gran O de n pasos, porque la palabra podría ser todo el camino al final de la lista, al igual que el melón. Y resulta que en la programación, más o menos del Santo Grial de los datos estructuras, es algo que le da constante tiempo como una matriz pero que todavía le da dinamismo. 

Así podemos tener lo mejor de ambos mundos? Y, en efecto, hay algo llama la tabla hash que le permite hacer exactamente que, aunque aproximadamente. Una tabla hash es un colombófilo estructura de datos que nos se puede pensar en como el combinación de un array-- y voy a sacar, así- y listas enlazadas que voy a dibujar como esto aquí. 

Y la forma en que esta cosa obras es como sigue. Si esto ahora-- el hash table-- es la tercera estructura de datos, y quiero almacenar palabras de este, no lo sé querer simplemente almacenar toda la palabras espalda con espalda con espalda con espalda. Quiero aprovechar alguna pieza de información acerca de las palabras que le permitirá yo entiendo donde es más rápido. 

Por lo tanto, dada la manzana palabras y el plátano y melón, Elegí deliberadamente esas palabras. ¿Por qué? Lo que es una especie de, fundamentalmente, diferente en los tres? ¿Qué es lo obvio? Comienzan con diferentes letras. 

Así que ya saben qué? En lugar de poner todas mis palabras el mismo cubo, por así decirlo, como en una enorme lista, ¿por qué no hacer Yo, al menos, trato una optimización y hacer mis listas 1/26 siempre. Una optimización convincente podría ser por qué no hacer Yo-- al insertar una palabra en esta estructura de datos, en la memoria del ordenador, ¿por qué No puse todas las palabras 'a' aquí, todas las palabras 'b' aquí, y todas las palabras 'c' aquí? Así que esto termina poniendo una manzana aquí, plátano aquí, melón aquí, Etcétera. 

Y si tengo un adicional palabra como- ¿cuál es la otra? Manzana, plátano, pera. Alguien piensa de una fruta que comienza con A, B, o C? Blueberry-- perfecta. Eso va a terminar aquí. Y por lo que parece que tienen una marginalmente mejor solución, porque ahora si quiero para buscar la manzana, me primero-- no me acaba de buceo en mi estructura de datos. No me sumerjo en la memoria de mi ordenador. La primera vez que miro a la primera letra. 

Y esto es lo que un ordenador científico diría. Usted comprobación aleatoria, la estructura de datos. Usted toma su entrada, que a su este caso es una palabra como la manzana. Usted lo analiza, mirando la primera letra en este caso, hash de ese modo. Hashing mediante el cual es un término general tomas algo como entrada y producir una salida. Y la salida en ese caso es la ubicación que desea buscar, el primer ubicación, segunda ubicación, tercero. Así que la entrada es de manzana, la salida es primero. La entrada es plátano, la salida debe ser segundo. La entrada es melón, la salida debe ser tercero. La entrada es el arándano, la salida debe volver a ser segundo. Y eso es lo que le ayuda a tomar accesos directos a través de la memoria con el fin de llegar a las palabras o los datos de manera más eficaz. 

Ahora bien, esto reduce nuestro tiempo potencialmente por tanto como uno de cada 26, porque si se asume que usted tener tantos "a" palabras como "z" palabras como palabras "q", que no es realmente realistic-- vas a tener sesgo en todos ciertas letras del alphabet-- pero esto sería un incremento enfoque que permite usted pueda llegar a decir mucho más rápidamente. Y en realidad, un sofisticado programa, el Googles del mundo, la Facebooks del mundo-- usarían una tabla hash para una gran cantidad de propósitos diferentes. Pero ellos no serían tan ingenuos como a tan sólo mirar a la primera letra en la manzana o un plátano o pera o el melón, ya que como se puede ver estos listas todavía podían hacer larga. 

Y así, esto todavía podría ser una especie de modo linear-- especie de lento, al igual que con el gran O de n que hemos comentado anteriormente. Así que lo que es una verdadera buena voluntad tabla hash hacer-- que tendrá una gama mucho más grande. Y va a utilizar una forma mucho más sofisticada función hash, de modo que no se limita a considerar la "a". Tal vez se ve en "a-p-p-l-e" y de alguna manera convierte esas cinco letras en la ubicación donde manzana debe ser almacenado. Estamos ingenuamente utilizando la letra "a" solo, porque es agradable y sencilla. 

Pero una tabla hash, en Al final, se puede pensar de como una combinación de una matriz, cada uno de los cuales tiene una lista enlazada que, idealmente, debe ser lo más corto posible. Y esto no es una solución obvia. De hecho, gran parte de la sintonización fina que continúa debajo de la capucha cuando la implementación de este tipo de estructuras de datos sofisticadas es lo que es el derecho longitud de la matriz? ¿Cuál es la función hash correcto? ¿Cómo se puede almacenar en la memoria las cosas? 

Pero darse cuenta de lo rápido este tipo de discusión escalada, o bien hasta el momento que es una especie de sobre la cabeza de uno en este punto, que está bien. Pero empezamos, memoria, con verdad algo de bajo nivel y la electrónica. Y por lo que este nuevo es este el tema de la abstracción, donde una vez que comience a tomar para concedida, OK, he it-- llegué allí es memoria física, OK, lo consiguió, cada ubicación física tiene una dirección, OK, lo tengo, puedo representar esas direcciones como arrows-- puede empezar muy rápidamente a tener conversaciones más sofisticadas que al final parecen ser lo que nos para resolver problemas como la búsqueda y clasificar de manera más eficaz. Y puede estar seguro, también-- porque creo que esto es la más profunda que hemos ido en alguna de estos temas CS proper-- que hemos hecho en un día y medio en este apuntar lo que normalmente podría hacer más de el curso de ocho semanas en un semestre. 

Cualquier pregunta sobre estos? ¿No? Todo bien. Bueno, ¿por qué no nos detenemos allí, comenzar el almuerzo unos minutos antes, reanudar en tan sólo alrededor de una hora? Y voy a permanecer durante un poco con preguntas. A continuación, voy a tener que ir tomar un par de llamadas si eso está bien. Voy a su vez algo de música en el ínterin, pero el almuerzo debe ser la vuelta de la esquina.