1 00:00:00,000 --> 00:00:00,030 2 00:00:00,030 --> 00:00:00,460 >> DAVID Malan: Todo ben. 3 00:00:00,460 --> 00:00:01,094 Estamos de volta. 4 00:00:01,094 --> 00:00:04,260 Polo tanto, neste segmento sobre a programación que Penso que faría é unha mestura de cousas. 5 00:00:04,260 --> 00:00:06,340 Un, facer un pouco algo práctico, 6 00:00:06,340 --> 00:00:08,690 aínda que cunha forma máis lúdica environment-- programación 7 00:00:08,690 --> 00:00:11,620 un que é demostrativo de exactamente tipo de ideas 8 00:00:11,620 --> 00:00:14,220 vimos falando, pero un pouco máis formalmente. 9 00:00:14,220 --> 00:00:18,200 Dous, ollar para algúns dos as formas máis técnicas 10 00:00:18,200 --> 00:00:21,520 que un programador sería realmente resolver problemas como o problema busca 11 00:00:21,520 --> 00:00:24,530 que mirou antes e tamén unha máis fundamentalmente 12 00:00:24,530 --> 00:00:26,020 problema interesante de clasificación. 13 00:00:26,020 --> 00:00:28,840 >> Nós só asumiu desde o ir buscar que este libro de teléfono foi resolto, 14 00:00:28,840 --> 00:00:31,980 pero que por si só é realmente unha especie de problema difícil con moitas formas diferentes 15 00:00:31,980 --> 00:00:32,479 resolvelo. 16 00:00:32,479 --> 00:00:34,366 Entón, imos usalos como unha clase de problemas 17 00:00:34,366 --> 00:00:36,740 representante das cousas que pode ser resolto dun modo xeral. 18 00:00:36,740 --> 00:00:38,980 E entón imos falar sobre con algún detalle que 19 00:00:38,980 --> 00:00:42,360 chámanse datos structures-- formas máis extravagantes como listas ligadas 20 00:00:42,360 --> 00:00:46,290 e táboas de hash e árbores que programador sería realmente 21 00:00:46,290 --> 00:00:48,890 usar e, xeralmente, utilizar nun cadro branco para pintar 22 00:00:48,890 --> 00:00:51,840 unha imaxe do que el ou ela albisca para a implantación 23 00:00:51,840 --> 00:00:52,980 algún anaco de software. 24 00:00:52,980 --> 00:00:55,130 >> Entón imos facer o hands-on primeira parte. 25 00:00:55,130 --> 00:01:00,090 Entón, só tes que ensuciar as mans cun ambiente chamada scratch.mit.edu. 26 00:01:00,090 --> 00:01:02,636 Esta é unha ferramenta que usan na nosa clase de graduación. 27 00:01:02,636 --> 00:01:04,510 Aínda que está deseñado para as idades de 12 e por riba, 28 00:01:04,510 --> 00:01:07,570 podemos usalo para o up parte dese algo 29 00:01:07,570 --> 00:01:10,020 xa que é un bo, divertido forma gráfica da aprendizaxe 30 00:01:10,020 --> 00:01:12,160 algo sobre programación. 31 00:01:12,160 --> 00:01:17,600 Entón cabeza para que URL onde debe ver unha páxina como esta, 32 00:01:17,600 --> 00:01:23,330 e dalle clic Únete a cero na esquina superior dereita 33 00:01:23,330 --> 00:01:28,300 e escoller un nome de usuario e un contrasinal e finalmente, obter-se 34 00:01:28,300 --> 00:01:29,970 un scratch.mit.edu account--. 35 00:01:29,970 --> 00:01:32,165 36 00:01:32,165 --> 00:01:34,665 Penso en usar isto como unha primeira oportunidade para amosar isto. 37 00:01:34,665 --> 00:01:39,120 A cuestión foi levantada durante a pausa sobre o código realmente se parece. 38 00:01:39,120 --> 00:01:41,315 E nós estabamos falando durante a pausa de aproximadamente C, 39 00:01:41,315 --> 00:01:45,060 en particular un particular-- menor nivel nunha linguaxe máis antiga. 40 00:01:45,060 --> 00:01:47,750 E eu só fixen unha rápida Google busca para atopar o código C 41 00:01:47,750 --> 00:01:51,574 descriptor binaria, o algoritmo que usado para buscar o libro de teléfono máis cedo. 42 00:01:51,574 --> 00:01:54,240 Neste exemplo concreto, por suposto, non buscar un libro de teléfono. 43 00:01:54,240 --> 00:01:57,840 El só busca unha morea de números na memoria do ordenador. 44 00:01:57,840 --> 00:02:01,000 Pero se quere obter só un Visual sentido que unha programación real 45 00:02:01,000 --> 00:02:05,370 linguaxe parece, parece un pouco algo como isto. 46 00:02:05,370 --> 00:02:09,759 Polo tanto, é un 20-plus, 30 ou máis liñas de código, 47 00:02:09,759 --> 00:02:12,640 pero a conversa que estaban tendo durante as vacacións 48 00:02:12,640 --> 00:02:16,000 era sobre como realmente converteuse ceros e uns 49 00:02:16,000 --> 00:02:19,200 e se non pode simplemente reverter esta procesar e ir de ceros e uns 50 00:02:19,200 --> 00:02:20,210 volver ao código. 51 00:02:20,210 --> 00:02:22,620 >> Desafortunadamente, o proceso de é tan transformadora 52 00:02:22,620 --> 00:02:24,890 que é moito máis fácil dicir que facer. 53 00:02:24,890 --> 00:02:29,400 Fun adiante e realmente se converteu este programa, Binary Search, 54 00:02:29,400 --> 00:02:32,700 en ceros e uns por medio dun O programa chamado compilador que 55 00:02:32,700 --> 00:02:34,400 ocorrer de ter aquí ben no meu Mac. 56 00:02:34,400 --> 00:02:37,850 E se ollar para a pantalla aquí, concentrando-se especialmente 57 00:02:37,850 --> 00:02:43,520 neses seis columnas do medio só, verás só ceros e uns. 58 00:02:43,520 --> 00:02:48,290 E estes son os ceros e uns que compoñer exactamente este programa de investigación. 59 00:02:48,290 --> 00:02:53,720 >> E así cada peza de cinco bits, cada byte de ceros e uns aquí, 60 00:02:53,720 --> 00:02:57,310 representan algunhas instrucións tipicamente dentro dun ordenador. 61 00:02:57,310 --> 00:03:00,730 E, de feito, se xa escoitou o slogan de márketing "Intel Inside" - que, 62 00:03:00,730 --> 00:03:04,610 por suposto, significa só que ten un CPU Intel ou o cerebro no seu ordenador. 63 00:03:04,610 --> 00:03:08,000 E o que significa ser un CPU é que ten un conxunto de instrucións, 64 00:03:08,000 --> 00:03:08,840 por así dicir. 65 00:03:08,840 --> 00:03:11,620 >> Cada CPU no mundo, dos Los feito por Intel nos días de hoxe, 66 00:03:11,620 --> 00:03:13,690 comprende un finito número de instrucións. 67 00:03:13,690 --> 00:03:18,690 E esas instrucións son tan baixo nivel como engadir eses dous números xuntos, 68 00:03:18,690 --> 00:03:22,560 multiplicar estes dous números xuntos, mover este anaco de datos a partir de aquí 69 00:03:22,560 --> 00:03:27,340 para aquí na memoria, gardar esta información aquí ata aquí na memoria, 70 00:03:27,340 --> 00:03:32,200 e así por forth-- moito baixo nivel, detalles case electrónicos. 71 00:03:32,200 --> 00:03:34,780 Pero cos matemático operacións axustado 72 00:03:34,780 --> 00:03:37,410 co que discutir anteriormente, a representación dos datos 73 00:03:37,410 --> 00:03:40,450 como ceros e uns, pode construír todo 74 00:03:40,450 --> 00:03:44,180 que un ordenador pode facer hoxe, sexa é textual, gráfica, musical, 75 00:03:44,180 --> 00:03:45,580 ou doutra forma. 76 00:03:45,580 --> 00:03:49,450 >> Entón iso é moi fácil de obter perdido nas herbas daniñas de xeito rápido. 77 00:03:49,450 --> 00:03:52,150 E hai unha morea de retos sintáticas 78 00:03:52,150 --> 00:03:56,630 en que facer o máis sinxelo, estúpido de erros de dixitación ningún programa 79 00:03:56,630 --> 00:03:57,860 funcionará calquera. 80 00:03:57,860 --> 00:04:00,366 E así, en vez de usar un linguaxe como C, esta mañá, 81 00:04:00,366 --> 00:04:02,240 Eu penso que sería máis divertido para realmente facer 82 00:04:02,240 --> 00:04:04,840 algo máis visual, que mentres deseñado para nenos 83 00:04:04,840 --> 00:04:08,079 é, en realidade, unha manifestación perfecta dunha programación real 84 00:04:08,079 --> 00:04:10,370 language-- só pasa de usar imaxes en vez de texto 85 00:04:10,370 --> 00:04:11,710 para representar esas ideas. 86 00:04:11,710 --> 00:04:15,470 >> Entón, cando de feito ten un conta en scratch.mit.edu, 87 00:04:15,470 --> 00:04:21,070 prema no botón Crear na esquina superior esquerda da páxina. 88 00:04:21,070 --> 00:04:24,620 E ten que ver un ambiente como o que eu estou a piques de ver na miña pantalla 89 00:04:24,620 --> 00:04:26,310 aquí. 90 00:04:26,310 --> 00:04:29,350 E nós imos gastar un pouco pouco de tempo a xogar aquí. 91 00:04:29,350 --> 00:04:34,080 Imos ver se non podemos todos resolver algúns problemas xuntos do seguinte xeito. 92 00:04:34,080 --> 00:04:39,420 >> Entón, o que podes ver dentro deste environment-- e realmente só deixar 93 00:04:39,420 --> 00:04:40,050 me unha pausa. 94 00:04:40,050 --> 00:04:42,680 Será que alguén non está aquí? 95 00:04:42,680 --> 00:04:45,070 Aquí non? 96 00:04:45,070 --> 00:04:45,800 OK. 97 00:04:45,800 --> 00:04:49,030 Entón, deixe-me salientar algúns características deste medio. 98 00:04:49,030 --> 00:04:55,024 >> Entón, na parte superior esquerda da pantalla, nos ten escenario cero, por así dicir. 99 00:04:55,024 --> 00:04:57,440 Cero non é só o nome desta linguaxe de programación; 100 00:04:57,440 --> 00:05:00,356 é tamén o nome do gato que ve por defecto, non en laranxa. 101 00:05:00,356 --> 00:05:02,160 Está nun estadio, de xeito tanto como eu describe 102 00:05:02,160 --> 00:05:05,770 a tartaruga anteriormente como estar nun rectangular ambiente cadro branco. 103 00:05:05,770 --> 00:05:09,800 mundo deste gato está totalmente confinada para ese rectángulo enriba alí. 104 00:05:09,800 --> 00:05:12,210 >> Mentres tanto, do lado dereito lado aquí, é 105 00:05:12,210 --> 00:05:15,610 só unha área de guións, unha lousa en branco se quere. 106 00:05:15,610 --> 00:05:18,590 Este é o lugar onde nós estamos indo a escribir nosos programas en só un momento. 107 00:05:18,590 --> 00:05:22,935 E os bloques de construción que debe usado para gravar esa program-- o puzzle 108 00:05:22,935 --> 00:05:25,310 anacos, se will-- son aqueles aquí no medio, 109 00:05:25,310 --> 00:05:27,500 e están categorizados pola función. 110 00:05:27,500 --> 00:05:31,000 Así, por exemplo, eu estou indo a ir adiante e demostran, polo menos, un destes. 111 00:05:31,000 --> 00:05:33,690 Eu estou indo a ir adiante e prema a categoría de control encima. 112 00:05:33,690 --> 00:05:35,720 >> Polo tanto, estas son as categorías enriba. 113 00:05:35,720 --> 00:05:39,410 Vou prema na categoría de Control. 114 00:05:39,410 --> 00:05:44,020 Pola contra, eu vou facer clic nos eventos categoría, o primeiro un encima. 115 00:05:44,020 --> 00:05:47,790 E se quere seguir, mesmo como facelo, está moi benvido para. 116 00:05:47,790 --> 00:05:52,180 Eu estou indo a facer clic e arrastrar ese primeiro, "cando a bandeira verde premendo." 117 00:05:52,180 --> 00:05:58,410 E entón eu vou deixala só aproximadamente na parte superior dos meus follas en branco. 118 00:05:58,410 --> 00:06:01,450 >> E o que é agradable sobre risco é que esta parte do enigma, cando 119 00:06:01,450 --> 00:06:04,560 interligado con outro puzzle pezas, vai facer literalmente 120 00:06:04,560 --> 00:06:06,460 o que estas pezas do puzzle dicir que facer. 121 00:06:06,460 --> 00:06:09,710 Así, por exemplo, Scratch é correcto agora no medio do seu mundo. 122 00:06:09,710 --> 00:06:14,660 Eu estou indo a ir adiante e elixir Agora, imos dicir, a categoría Movemento, 123 00:06:14,660 --> 00:06:18,000 Se desexa facer o same-- categoría Motion. 124 00:06:18,000 --> 00:06:20,430 E agora noten teño un todo chea de pezas do puzzle aquí 125 00:06:20,430 --> 00:06:23,370 que, de novo, tipo de facer o que eles din. 126 00:06:23,370 --> 00:06:28,110 E eu estou indo a ir adiante e arrastrar e soltar o bloque movemento ben aquí. 127 00:06:28,110 --> 00:06:31,860 >> E teña en conta que, así que comeza preto da parte inferior da "bandeira verde 128 00:06:31,860 --> 00:06:34,580 premendo "botón, o aviso previo como unha liña branca aparece, 129 00:06:34,580 --> 00:06:36,950 como se fose case magnética, quere ir máis alá. 130 00:06:36,950 --> 00:06:43,070 Só deixe ir, e se encaixará en conxunto e as formas corresponde. 131 00:06:43,070 --> 00:06:46,620 E agora pode, talvez, case adiviñar onde estamos indo con iso. 132 00:06:46,620 --> 00:06:51,570 >> Se ollar para o estadio cero por aquí e ollar para arriba, 133 00:06:51,570 --> 00:06:55,142 verás unha luz vermella, un deixe o sinal, e unha bandeira verde. 134 00:06:55,142 --> 00:06:57,100 E eu estou indo a ir adiante e asistir os meus screen-- 135 00:06:57,100 --> 00:06:58,460 por só un momento, se puidese. 136 00:06:58,460 --> 00:07:01,960 Vou prema o bandeira verde agora, 137 00:07:01,960 --> 00:07:07,850 e moveu-se o que parece ser 10 pasos ou 10 píxeles, 10 puntos, na pantalla. 138 00:07:07,850 --> 00:07:13,390 >> E así non excitante, pero déixeme propoñer 139 00:07:13,390 --> 00:07:17,440 sen sequera ensinando iso, só tes que usando o propio o seu propio let intuition-- 140 00:07:17,440 --> 00:07:22,560 -me propoñer que descubrir como facer scratch pé para fóra do escenario. 141 00:07:22,560 --> 00:07:28,700 Telo abrir camiño para o lado dereito a pantalla, todo o camiño para a dereita. 142 00:07:28,700 --> 00:07:32,200 Deixe-me dar-lle un momento ou máis para loitar con iso. 143 00:07:32,200 --> 00:07:37,681 Pode querer dar un ollo noutras categorías de bloques. 144 00:07:37,681 --> 00:07:38,180 Todo ben. 145 00:07:38,180 --> 00:07:41,290 Entón, só para recapitular, cando temos a bandeira verde premendo aquí 146 00:07:41,290 --> 00:07:44,850 e mover 10 pasos é a única instrución, cada vez que eu 147 00:07:44,850 --> 00:07:46,720 prema na bandeira verde, o que está pasando? 148 00:07:46,720 --> 00:07:50,070 Ben, iso está executando o meu programa. 149 00:07:50,070 --> 00:07:52,450 Entón, eu podería facelo quizais 10 veces a man, 150 00:07:52,450 --> 00:07:55,130 pero este se sente un pouco pouco hackish, por así dicir, 151 00:07:55,130 --> 00:07:57,480 en que eu realmente non estou resolvendo o problema. 152 00:07:57,480 --> 00:08:00,530 Eu só estou tentando de novo e de novo e de novo e de novo 153 00:08:00,530 --> 00:08:03,180 ata eu medio que accidentalmente alcanzar a Directiva 154 00:08:03,180 --> 00:08:05,560 que se propón acadar antes. 155 00:08:05,560 --> 00:08:08,200 >> Pero sabemos da nosa pseudocódigo anterior de que hai 156 00:08:08,200 --> 00:08:11,870 esta noción en programación de looping, facendo algo novo e de novo. 157 00:08:11,870 --> 00:08:14,888 E entón vin que unha morea de ti alcanzou peza o puzzle? 158 00:08:14,888 --> 00:08:17,870 159 00:08:17,870 --> 00:08:18,730 Repita ata. 160 00:08:18,730 --> 00:08:21,400 Para que puidésemos facer algo como repetir ata. 161 00:08:21,400 --> 00:08:23,760 E o que repetir ata que exactamente? 162 00:08:23,760 --> 00:08:27,720 163 00:08:27,720 --> 00:08:28,540 >> OK. 164 00:08:28,540 --> 00:08:31,974 E déixeme ir con un que é un pouco máis simple para só un momento. 165 00:08:31,974 --> 00:08:33,140 Deixe-me ir adiante e facelo. 166 00:08:33,140 --> 00:08:35,559 Teña en conta que, como pode ter descuberto baixo control, 167 00:08:35,559 --> 00:08:38,409 existe este bloque de repetición, que Non parece que é tan grande. 168 00:08:38,409 --> 00:08:41,039 Non hai moito espazo no entre esas dúas liñas amarelas. 169 00:08:41,039 --> 00:08:43,539 Pero, como algúns de vostedes poden ter notado, se arrastrar e soltar, 170 00:08:43,539 --> 00:08:45,150 notar como medra para cubrir a forma. 171 00:08:45,150 --> 00:08:46,274 >> E aínda pode empinar máis. 172 00:08:46,274 --> 00:08:48,670 El só vai continuar a crecer, se arrastrar e pair sobre el. 173 00:08:48,670 --> 00:08:51,110 E eu non sei o que é mellor aquí, entón imos 174 00:08:51,110 --> 00:08:54,760 me, polo menos, repetir cinco veces, por exemplo, e despois volver para o escenario 175 00:08:54,760 --> 00:08:56,720 e prema na bandeira verde. 176 00:08:56,720 --> 00:08:59,110 E agora entende que non é ben alí. 177 00:08:59,110 --> 00:09:02,400 >> Agora algúns de vostedes proposto, Victoria fixo, repita 10 veces. 178 00:09:02,400 --> 00:09:05,140 E que xeralmente fai leva-lo todo o camiño, 179 00:09:05,140 --> 00:09:10,510 Pero non sería haber unha máis robusta xeito que arbitrariamente descubrir 180 00:09:10,510 --> 00:09:12,640 cantos movementos para facer? 181 00:09:12,640 --> 00:09:17,680 O que podería ser un bloque mellor que repetir 10 veces ser? 182 00:09:17,680 --> 00:09:20,380 >> Si, entón por que non facer algo para sempre? 183 00:09:20,380 --> 00:09:24,390 E agora déixeme ir esta parte do enigma dentro e librar-se dun presente. 184 00:09:24,390 --> 00:09:28,300 Agora conta, non importa onde Raspadinha comeza, que vai para o bordo. 185 00:09:28,300 --> 00:09:30,700 E por sorte MIT, que fai scratch, só 186 00:09:30,700 --> 00:09:33,190 garante que nunca desaparece por completo. 187 00:09:33,190 --> 00:09:35,360 Poderá coller súa cola. 188 00:09:35,360 --> 00:09:37,680 >> E só intuitivamente, por que segue movendo? 189 00:09:37,680 --> 00:09:38,892 O que está pasando aquí? 190 00:09:38,892 --> 00:09:41,440 191 00:09:41,440 --> 00:09:43,824 El parece parado, pero logo se eu incorporarse e arrastrar 192 00:09:43,824 --> 00:09:45,240 segue querendo ir máis alá. 193 00:09:45,240 --> 00:09:46,123 Por que é iso? 194 00:09:46,123 --> 00:09:51,610 195 00:09:51,610 --> 00:09:54,360 Verdadeiramente, un ordenador é, literalmente, vai facer o que diga a el para facer. 196 00:09:54,360 --> 00:09:58,380 Entón, se dixo que antes facer o O seguinte para sempre, mover 10 pasos, 197 00:09:58,380 --> 00:10:01,860 vai continuar e vai ata que eu bati o sinal vermello 198 00:10:01,860 --> 00:10:04,620 e deixar o programa completo. 199 00:10:04,620 --> 00:10:06,610 >> Así, mesmo se non está facelo, como eu podería 200 00:10:06,610 --> 00:10:09,510 facer mover máis rápido risco do outro lado da pantalla? 201 00:10:09,510 --> 00:10:12,060 202 00:10:12,060 --> 00:10:13,280 Máis pasos, non? 203 00:10:13,280 --> 00:10:15,710 Entón, en vez de facer 10 á vez, polo que non 204 00:10:15,710 --> 00:10:20,100 dalle cambiar isto a-- o que propose-- 50? 205 00:10:20,100 --> 00:10:24,410 Entón agora eu vou prema o verde bandeira, e, de feito, que vai moi rápido. 206 00:10:24,410 --> 00:10:27,180 >> E, por suposto, é só unha manifestación de animación. 207 00:10:27,180 --> 00:10:28,060 Que é animación? 208 00:10:28,060 --> 00:10:33,090 É só mostrándolle a un ser humano grupo enteiro de imaxes fixas, realmente, 209 00:10:33,090 --> 00:10:34,160 moi, moi rápido. 210 00:10:34,160 --> 00:10:36,500 E por iso, se nós estamos só dicindo Lo a moverse máis pasos, 211 00:10:36,500 --> 00:10:39,750 Nós só estamos tendo o efecto pode cambio onde está na pantalla 212 00:10:39,750 --> 00:10:42,900 toda a unidade máis rapidamente por tempo. 213 00:10:42,900 --> 00:10:46,454 >> Agora, o seguinte reto que propuxen era telo ir para fóra do borde. 214 00:10:46,454 --> 00:10:49,120 E sen saber o puzzle pezas exist-- porque é fina 215 00:10:49,120 --> 00:10:53,030 se non chegar ao etapa que challenge-- 216 00:10:53,030 --> 00:10:54,280 quere facer intuitivamente? 217 00:10:54,280 --> 00:10:58,030 Como poderiamos telo ir para atrás e diante, entre a esquerda e dereita? 218 00:10:58,030 --> 00:11:02,630 219 00:11:02,630 --> 00:11:03,810 >> Si. 220 00:11:03,810 --> 00:11:05,680 Entón, necesitamos algún tipo da condición, e 221 00:11:05,680 --> 00:11:09,710 parecen condicionais, por así falar, baixo a categoría de control. 222 00:11:09,710 --> 00:11:14,110 Cal destes bloques nós probablemente quere? 223 00:11:14,110 --> 00:11:15,200 Si, quizais ", entón." 224 00:11:15,200 --> 00:11:18,780 Entón, teña en conta que, entre os bloques amarelo temos aquí, non é este "se" 225 00:11:18,780 --> 00:11:23,920 ou este "if, else" bloque que nos permiten tomar unha decisión para facelo 226 00:11:23,920 --> 00:11:25,000 ou para facelo. 227 00:11:25,000 --> 00:11:27,380 E aínda pode inserir-las para facer moitas cousas. 228 00:11:27,380 --> 00:11:34,910 Ou se non fose aínda aquí, dalle á categoría Sensing 229 00:11:34,910 --> 00:11:39,612 e- imos ver se está aquí. 230 00:11:39,612 --> 00:11:43,050 231 00:11:43,050 --> 00:11:52,050 >> Entón, o bloque pode ser útil aquí para detectar se está fóra do escenario? 232 00:11:52,050 --> 00:11:56,740 Si, ter en conta que algúns destes bloques pode ser parametrizada, por así dicir. 233 00:11:56,740 --> 00:12:00,706 Poden ser tipo de personalización, non ao contrario do HTML onte con atributos, 234 00:12:00,706 --> 00:12:03,330 onde estes atributos tipo de personalizar o comportamento dunha etiqueta. 235 00:12:03,330 --> 00:12:08,880 Do mesmo xeito aquí, podo coller esta conmovedora bloque e cambio e facer a pregunta, 236 00:12:08,880 --> 00:12:11,500 está tocando o rato punteiro como o cursor 237 00:12:11,500 --> 00:12:13,250 ou está tocando a bordo? 238 00:12:13,250 --> 00:12:15,210 >> Entón deixe-me entrar e facelo. 239 00:12:15,210 --> 00:12:18,130 Eu estou indo a afastar un momento. 240 00:12:18,130 --> 00:12:21,320 Déixeme coller esta parte do enigma aquí, este enigma que, 241 00:12:21,320 --> 00:12:24,570 e eu vou Desorde Los por só un momento. 242 00:12:24,570 --> 00:12:27,620 Eu estou indo a ir este, cambiar esta a bordo tocar, 243 00:12:27,620 --> 00:12:38,590 e eu vou facelo de movemento. 244 00:12:38,590 --> 00:12:40,490 Entón, aquí están algúns ingredientes. 245 00:12:40,490 --> 00:12:42,570 Eu creo que eu teño todo o que quero. 246 00:12:42,570 --> 00:12:47,710 >> Será que alguén quere propoñer como eu pode conectar estes quizais de arriba para abaixo 247 00:12:47,710 --> 00:12:52,020 a fin de resolver o problema de ter Cero dereita a esquerda a dereita para mover 248 00:12:52,020 --> 00:12:57,020 esquerda a dereita á esquerda, cada un tempo só ir fóra da pantalla? 249 00:12:57,020 --> 00:12:58,050 O que quero facer? 250 00:12:58,050 --> 00:13:01,097 Cal bloque debe podo conectar á "Flag cando verde clic por primeira vez"? 251 00:13:01,097 --> 00:13:04,060 252 00:13:04,060 --> 00:13:06,200 >> OK, entón imos comezar co "para sempre". 253 00:13:06,200 --> 00:13:07,170 Que dentro logo? 254 00:13:07,170 --> 00:13:10,290 Alguén máis. 255 00:13:10,290 --> 00:13:11,850 OK, move etapas. 256 00:13:11,850 --> 00:13:12,350 Todo ben. 257 00:13:12,350 --> 00:13:14,470 Entón o que? 258 00:13:14,470 --> 00:13:15,120 Entón a. 259 00:13:15,120 --> 00:13:17,720 E teña en conta, aínda que pareza imprensados ​​xunto con forza, 260 00:13:17,720 --> 00:13:19,500 ela só vai medrar para cubrir. 261 00:13:19,500 --> 00:13:21,500 Vai só no salto, onde quero. 262 00:13:21,500 --> 00:13:25,920 >> E o que eu puxen entre if e entón? 263 00:13:25,920 --> 00:13:27,180 Probablemente "se tocar bordo." 264 00:13:27,180 --> 00:13:31,800 E observen, de novo, é moi grande para el, pero el vai medrar para cubrir. 265 00:13:31,800 --> 00:13:35,002 E, a continuación, Xire 15 graos? 266 00:13:35,002 --> 00:13:35,710 Cantos graos? 267 00:13:35,710 --> 00:13:38,800 268 00:13:38,800 --> 00:13:41,196 Si, entón 180 virará me a toda a volta. 269 00:13:41,196 --> 00:13:42,570 Entón imos ver se eu teño ese dereito. 270 00:13:42,570 --> 00:13:43,930 Déixeme afastar. 271 00:13:43,930 --> 00:13:45,130 >> Déixeme arrastrar cero superior. 272 00:13:45,130 --> 00:13:50,030 Entón, el é un pouco distorsionada agora, pero iso é bo. 273 00:13:50,030 --> 00:13:52,231 Como se restaurar-lo facilmente? 274 00:13:52,231 --> 00:13:59,879 275 00:13:59,879 --> 00:14:01,045 Eu estou indo a enganar un pouco. 276 00:14:01,045 --> 00:14:04,074 277 00:14:04,074 --> 00:14:05,990 Entón, eu estou engadindo outro bloque, só para quedar claro. 278 00:14:05,990 --> 00:14:08,424 Quero que apunta 90 graos á dereita por defecto, 279 00:14:08,424 --> 00:14:10,840 entón eu só vou dicir a el para facelo por medio de programación. 280 00:14:10,840 --> 00:14:11,632 E aquí imos nós. 281 00:14:11,632 --> 00:14:14,740 282 00:14:14,740 --> 00:14:15,740 Nós parecemos ter feito isto. 283 00:14:15,740 --> 00:14:19,980 É un pouco raro, porque está camiñando de cabeza para baixo. 284 00:14:19,980 --> 00:14:21,250 Imos chamar ese un erro. 285 00:14:21,250 --> 00:14:22,120 Isto é un erro. 286 00:14:22,120 --> 00:14:27,320 Un erro é un erro nun programa, un erro lóxico que, o ser humano, feito. 287 00:14:27,320 --> 00:14:28,985 Por que está indo de cabeza para abaixo? 288 00:14:28,985 --> 00:14:33,560 289 00:14:33,560 --> 00:14:35,250 Será que MIT romper ou eu? 290 00:14:35,250 --> 00:14:38,840 291 00:14:38,840 --> 00:14:42,550 >> Si, quero dicir, non é MIT fallo. Eles me deron unha parte do enigma 292 00:14:42,550 --> 00:14:44,970 que di que transformar algúns número de graos. 293 00:14:44,970 --> 00:14:47,672 E por suxestión de Victoria, Estou xirando 180 graos, 294 00:14:47,672 --> 00:14:48,880 que é a intuición correcta. 295 00:14:48,880 --> 00:14:53,700 Pero transformar 180 graos literalmente significa virar 180 graos, 296 00:14:53,700 --> 00:14:55,860 e iso non é realmente o que quero, aparentemente. 297 00:14:55,860 --> 00:14:58,026 Porque polo menos está este mundo bidimensional, 298 00:14:58,026 --> 00:15:00,740 de xeito decisivo que realmente está a suceder para virar de cabeza para baixo. 299 00:15:00,740 --> 00:15:04,030 >> I probablemente vai querer usar o bloque en vez diso, segundo o que ve aquí? 300 00:15:04,030 --> 00:15:11,890 301 00:15:11,890 --> 00:15:14,790 Como podemos solucionar isto? 302 00:15:14,790 --> 00:15:18,380 É, por tanto, podería apuntar no sentido oposto. 303 00:15:18,380 --> 00:15:22,300 E, de feito, aínda que sexa non vai ser suficiente, 304 00:15:22,300 --> 00:15:26,410 porque só pode código ríxido apuntando á esquerda ou á dereita. 305 00:15:26,410 --> 00:15:27,920 >> Vostede sabe o que poderiamos facer? 306 00:15:27,920 --> 00:15:30,160 Parece que temos un bloque de barrio aquí. 307 00:15:30,160 --> 00:15:32,987 Se eu aumentar o zoom, ver algo que nos gusta aquí? 308 00:15:32,987 --> 00:15:36,120 309 00:15:36,120 --> 00:15:40,020 Polo tanto, parece que o MIT ten unha abstracción construída aquí. 310 00:15:40,020 --> 00:15:45,440 Este bloque parece ser equivalente para que outros bloques, plural? 311 00:15:45,440 --> 00:15:49,510 >> Este bloque parece ser equivalente a todo este trío de bloques 312 00:15:49,510 --> 00:15:50,880 que temos aquí. 313 00:15:50,880 --> 00:15:54,670 Non é que podo simplificar a miña programa por se librar de todo isto 314 00:15:54,670 --> 00:15:58,270 e pode poñer iso aquí. 315 00:15:58,270 --> 00:16:01,620 E agora aínda é un pouco cesta, e iso é bo para agora. 316 00:16:01,620 --> 00:16:03,370 Imos deixar que sexa. 317 00:16:03,370 --> 00:16:06,000 Pero o meu programa é aínda máis simple, e iso, tamén, 318 00:16:06,000 --> 00:16:09,060 sería representativa dun obxectivo en programming-- 319 00:16:09,060 --> 00:16:13,430 é ideal facer o código como simple, tan compacto como sexa posible, 320 00:16:13,430 --> 00:16:15,650 mentres seguen a ser tan lexible posible. 321 00:16:15,650 --> 00:16:20,310 Non quere facelo de xeito sucinto que é difícil de entender. 322 00:16:20,310 --> 00:16:22,826 >> Pero teña en conta que eu substituído tres bloques cun, 323 00:16:22,826 --> 00:16:24,200 e iso é, sen dúbida, unha cousa boa. 324 00:16:24,200 --> 00:16:27,280 Eu abstraída a noción comprobar se está 325 00:16:27,280 --> 00:16:29,120 no bordo con só un bloque. 326 00:16:29,120 --> 00:16:31,520 Agora podemos divertirse con iso, en realidade. 327 00:16:31,520 --> 00:16:35,790 Isto non engadir moito valor intelectual, pero valor lúdico. 328 00:16:35,790 --> 00:16:39,730 Eu estou indo a ir adiante e incorporarse este son aquí. 329 00:16:39,730 --> 00:16:42,900 330 00:16:42,900 --> 00:16:46,420 Entón deixe-me ir adiante, e deixe-me deter o programa por un momento. 331 00:16:46,420 --> 00:16:52,070 Vou gardar o seguinte, permitindo o acceso ao meu micrófono. 332 00:16:52,070 --> 00:16:53,181 >> Alá imos. 333 00:16:53,181 --> 00:16:53,680 Ouch. 334 00:16:53,680 --> 00:16:58,710 335 00:16:58,710 --> 00:17:01,140 Imos tentar que de novo. 336 00:17:01,140 --> 00:17:02,279 Alá imos. 337 00:17:02,279 --> 00:17:03,570 OK, eu gravei a cousa incorrecta. 338 00:17:03,570 --> 00:17:04,580 Alá imos. 339 00:17:04,580 --> 00:17:05,080 Ouch. 340 00:17:05,080 --> 00:17:07,910 341 00:17:07,910 --> 00:17:08,800 Ouch. 342 00:17:08,800 --> 00:17:09,300 Todo ben. 343 00:17:09,300 --> 00:17:10,791 Agora eu teño para se librar desa. 344 00:17:10,791 --> 00:17:11,290 Todo ben. 345 00:17:11,290 --> 00:17:13,950 >> Entón agora eu teño un gravar só "ouch". 346 00:17:13,950 --> 00:17:18,040 Entón agora eu estou indo a ir adiante e chamar iso de "ai". 347 00:17:18,040 --> 00:17:20,270 Eu estou indo a volver para os meus guións, e agora 348 00:17:20,270 --> 00:17:25,460 aviso hai este bloque que se chama reproducir o son "Miau" ou reproducir o son "ai". 349 00:17:25,460 --> 00:17:28,920 Eu estou indo a arrastrar iso, e onde debo poñer isto para efecto cómico? 350 00:17:28,920 --> 00:17:31,740 351 00:17:31,740 --> 00:17:37,860 É, polo que agora é unha especie de cesta, porque agora este block-- 352 00:17:37,860 --> 00:17:42,050 observe como este "na beira, salto "é unha especie de auto-contido. 353 00:17:42,050 --> 00:17:43,704 Entón eu teño fixar iso. 354 00:17:43,704 --> 00:17:44,870 Deixe-me ir adiante e facelo. 355 00:17:44,870 --> 00:17:48,630 Déixeme librarse desa e volver para a nosa orixinal, máis deliberada 356 00:17:48,630 --> 00:17:49,870 funcionalidade. 357 00:17:49,870 --> 00:18:01,080 Entón, "se tocar bordo, a continuación," Eu quero a xirar, como Victoria proposto, 358 00:18:01,080 --> 00:18:02,480 180 graos. 359 00:18:02,480 --> 00:18:05,497 E quero xogar o son "ouch" alí? 360 00:18:05,497 --> 00:18:11,800 361 00:18:11,800 --> 00:18:15,580 >> Si, ter en conta que é fóra este bloque amarelo. 362 00:18:15,580 --> 00:18:17,680 Entón, iso tamén sería unha erro, pero teño notado iso. 363 00:18:17,680 --> 00:18:21,290 Entón eu vou arrastralo ata aquí, e aviso agora dentro do "si". 364 00:18:21,290 --> 00:18:24,250 Así, o "si" é ese tipo de como blot brazo-like 365 00:18:24,250 --> 00:18:26,260 que só vai facer o que está dentro dela. 366 00:18:26,260 --> 00:18:30,216 Entón agora eu reducir en o risco de annoying-- 367 00:18:30,216 --> 00:18:32,860 368 00:18:32,860 --> 00:18:36,470 >> Ordenador: Ai, ai, ai. 369 00:18:36,470 --> 00:18:39,910 >> DAVID Malan: E só vai durar para sempre. 370 00:18:39,910 --> 00:18:44,160 Agora é só para acelerar as cousas aquí, deixe-me ir adiante e abrir-se, 371 00:18:44,160 --> 00:18:50,460 imos dizer-- déixeme ir a algún do meu propio material de clase. 372 00:18:50,460 --> 00:18:53,000 373 00:18:53,000 --> 00:19:00,220 E déixeme abrir, imos dicir, este un feito por un dos nosos compañeiros de ensino 374 00:19:00,220 --> 00:19:01,500 un par de anos. 375 00:19:01,500 --> 00:19:04,732 Entón, algúns de vostedes poden lembrar este xogo doutros tempos, 376 00:19:04,732 --> 00:19:05,940 e é realmente notable. 377 00:19:05,940 --> 00:19:08,190 Aínda que nós fixemos o máis simple de programas de agora, 378 00:19:08,190 --> 00:19:09,980 imos considerar o que iso realmente parece. 379 00:19:09,980 --> 00:19:10,650 Déixeme bateu xogar. 380 00:19:10,650 --> 00:19:14,210 381 00:19:14,210 --> 00:19:18,980 >> Entón, neste xogo, temos un ra, e utilizando a frecha keys-- 382 00:19:18,980 --> 00:19:23,340 toma pasos máis grandes que eu recorde-- Teño control sobre ese sapo. 383 00:19:23,340 --> 00:19:29,630 E o obxectivo é atravesar o movemento estrada sen executar para os coches. 384 00:19:29,630 --> 00:19:34,735 E imos see-- se eu ir ata aquí, eu ten que esperar por un rexistro para rodar. 385 00:19:34,735 --> 00:19:38,130 386 00:19:38,130 --> 00:19:39,274 Isto parece un erro. 387 00:19:39,274 --> 00:19:42,240 388 00:19:42,240 --> 00:19:43,495 Este é un tipo de erro. 389 00:19:43,495 --> 00:19:45,980 390 00:19:45,980 --> 00:19:46,480 Todo ben. 391 00:19:46,480 --> 00:19:51,550 Estou neste aquí, alí, e entón segue 392 00:19:51,550 --> 00:19:54,100 indo ata obter toda as ras para os lírios. 393 00:19:54,100 --> 00:19:55,920 Agora isto pode parecer tanto máis complexa, 394 00:19:55,920 --> 00:19:57,840 pero imos tentar romper este abaixo mentalmente 395 00:19:57,840 --> 00:20:00,040 e verbalmente os seus bloques compoñentes. 396 00:20:00,040 --> 00:20:03,910 Entón, hai probablemente un puzzle peza que non vimos aínda 397 00:20:03,910 --> 00:20:07,440 pero que responde aos mandos das teclas, a cousas que eu bati o teclado. 398 00:20:07,440 --> 00:20:11,660 >> Entón, hai probablemente algún tipo de bloque que di, a clave é igual a anterior, 399 00:20:11,660 --> 00:20:15,965 a continuación, facer algo con Scratch-- quizais movelo 10 pasos desta forma. 400 00:20:15,965 --> 00:20:20,240 Se cursor abaixo é presionado, mover 10 pasos Deste xeito, ou á esquerda, mover 10 pasos 401 00:20:20,240 --> 00:20:21,710 Deste xeito, o 10 pasos que. 402 00:20:21,710 --> 00:20:23,644 Virei claramente o gato nun sapo. 403 00:20:23,644 --> 00:20:26,060 Entón, iso é só onde a traxe, como chamadas de raspadinhas ele-- nós 404 00:20:26,060 --> 00:20:28,440 acaba de importar unha imaxe do sapo. 405 00:20:28,440 --> 00:20:29,570 >> Pero o que máis está a suceder? 406 00:20:29,570 --> 00:20:32,794 Que outras liñas de código, o que as outras pezas do puzzle 407 00:20:32,794 --> 00:20:35,460 fixo Blake, o noso ensino do compañeiro, utilizar neste programa, aparentemente? 408 00:20:35,460 --> 00:20:38,320 409 00:20:38,320 --> 00:20:42,730 O que está facendo todo move-- o que de programación construír? 410 00:20:42,730 --> 00:20:44,950 >> Movemento, de xeito que o sure-- mover o bloque, con certeza. 411 00:20:44,950 --> 00:20:49,330 E que é o que o bloque movemento Dentro, máis probable? 412 00:20:49,330 --> 00:20:52,850 Si, algún tipo de loop, quizais un sempre bloquear, quizais unha repetición block-- 413 00:20:52,850 --> 00:20:54,070 repetir ata que o bloque. 414 00:20:54,070 --> 00:20:57,330 E iso é o que está a facer os rexistros e os lírios e todo máis movemento 415 00:20:57,330 --> 00:20:57,990 e cara atrás. 416 00:20:57,990 --> 00:21:00,270 É só a suceder sen parar. 417 00:21:00,270 --> 00:21:03,180 >> Por que algúns dos coches movendo máis rápido que os outros? 418 00:21:03,180 --> 00:21:06,607 Que é diferente sobre estes programas? 419 00:21:06,607 --> 00:21:09,690 Si, probablemente algúns deles están a tomar máis pasos dunha soa vez e algúns deles 420 00:21:09,690 --> 00:21:10,690 menos etapas dunha soa vez. 421 00:21:10,690 --> 00:21:14,670 E o efecto visual é rápido contra lento. 422 00:21:14,670 --> 00:21:16,030 >> ¿Que pensas que pasou? 423 00:21:16,030 --> 00:21:19,700 Cando eu teño o meu sapo todo o camiño do outro lado da rúa e do río 424 00:21:19,700 --> 00:21:23,560 na almofada de lírio, algo digno de nota pasou. 425 00:21:23,560 --> 00:21:26,540 Que pasou así que eu fixen iso? 426 00:21:26,540 --> 00:21:27,210 Deixou. 427 00:21:27,210 --> 00:21:29,680 Aquel sapo parou, e Eu teño unha segunda ra. 428 00:21:29,680 --> 00:21:33,155 Entón, o construto debe ser usado alí, o recurso? 429 00:21:33,155 --> 00:21:36,020 430 00:21:36,020 --> 00:21:38,660 >> É, por iso hai algún tipo de "Se" condicionar-se alí, tamén. 431 00:21:38,660 --> 00:21:41,909 E pasa out-- non vimos isto-- pero hai outros bloques en que hai 432 00:21:41,909 --> 00:21:45,300 pode dicir que, se está tocando algo na pantalla, 433 00:21:45,300 --> 00:21:47,720 se está tocando a almofada de lírio ", entón". 434 00:21:47,720 --> 00:21:50,810 E, a continuación, que é cando facer a segunda ra aparecer. 435 00:21:50,810 --> 00:21:54,969 Así, aínda que este xogo é certamente moi antigo, aínda que a primeira vista 436 00:21:54,969 --> 00:21:58,010 hai tanta cousa suceder Blake on-- e non chicotear isto en dous minutos, 437 00:21:58,010 --> 00:22:00,390 probablemente levou varios horas para crear este xogo 438 00:22:00,390 --> 00:22:03,850 con base na súa memoria ou vídeos da versión de pasado del. 439 00:22:03,850 --> 00:22:07,940 Pero todas estas pequenas cousas indo na pantalla de forma illada 440 00:22:07,940 --> 00:22:11,550 resumen-se a estes moi sinxelo movementos constructs-- ou declaracións 441 00:22:11,550 --> 00:22:15,519 como xa discutir, loops e condicións, e é sobre iso. 442 00:22:15,519 --> 00:22:17,060 Hai algunhas outras características extravagantes. 443 00:22:17,060 --> 00:22:19,130 Algúns deles son puramente estética ou acústico, 444 00:22:19,130 --> 00:22:20,964 como os sons Só xogou con. 445 00:22:20,964 --> 00:22:23,380 Pero para a maior parte, vostede ten nesta lingua, risco, 446 00:22:23,380 --> 00:22:25,350 todos de fundamental bloques de construción que 447 00:22:25,350 --> 00:22:29,280 teñen en C, Java, JavaScript, PHP, Ruby, Python, 448 00:22:29,280 --> 00:22:32,960 e calquera número de outras linguas. 449 00:22:32,960 --> 00:22:36,720 Calquera dúbida sobre cero? 450 00:22:36,720 --> 00:22:37,220 Todo ben. 451 00:22:37,220 --> 00:22:40,303 Polo tanto, non imos mergullar máis fondo a cero, que é benvido este fin de semana, 452 00:22:40,303 --> 00:22:42,860 especialmente se ten fillos ou sobriños e sobriñas e tal, 453 00:22:42,860 --> 00:22:44,220 presenta-los a cero. 454 00:22:44,220 --> 00:22:47,960 É realmente un marabillosas lúdica ambiente, con, como os seus autores, 455 00:22:47,960 --> 00:22:49,120 teitos moi altos. 456 00:22:49,120 --> 00:22:51,670 Aínda que comezou con moi detalles de baixo nivel, 457 00:22:51,670 --> 00:22:54,890 pode realmente facer algo con el, e este é quizais 458 00:22:54,890 --> 00:22:57,360 unha demostración de exactamente isto. 459 00:22:57,360 --> 00:23:02,920 >> Pero imos agora facer a transición cara un pouco máis problemas sofisticados, se quixeren, 460 00:23:02,920 --> 00:23:05,870 coñecida como "busca" e "Selección", de xeito máis xeral. 461 00:23:05,870 --> 00:23:09,500 Tivemos este libro de teléfono earlier-- aquí outra só para discussion-- 462 00:23:09,500 --> 00:23:13,460 que fomos capaces de busca de forma máis eficiente porque 463 00:23:13,460 --> 00:23:15,270 dun presuposto significativo. 464 00:23:15,270 --> 00:23:17,655 E só para quedar claro, o que suposición era eu facendo 465 00:23:17,655 --> 00:23:19,280 Ao buscar a través deste libro de teléfono? 466 00:23:19,280 --> 00:23:23,342 467 00:23:23,342 --> 00:23:25,300 Que Mike Smith estaba o libro de teléfono, aínda que 468 00:23:25,300 --> 00:23:27,410 sería capaz de tratar o escenario sen el 469 00:23:27,410 --> 00:23:30,720 alí se eu simplemente deixou prematuramente. 470 00:23:30,720 --> 00:23:31,806 O libro é alfabético. 471 00:23:31,806 --> 00:23:33,930 E iso é moi xeneroso suposición, porque iso 472 00:23:33,930 --> 00:23:36,580 significa someone-- Eu son do tipo de corte de esquina, 473 00:23:36,580 --> 00:23:40,580 como eu son máis rápido porque alguén outros fixeron unha chea de traballo duro para min. 474 00:23:40,580 --> 00:23:43,120 >> Pero e se o teléfono libro foron non separados? 475 00:23:43,120 --> 00:23:47,050 Quizais Verizon teño preguiza, só xogou nomes e números de todos dentro 476 00:23:47,050 --> 00:23:50,120 quizais na orde en que asinou o servizo de teléfono. 477 00:23:50,120 --> 00:23:54,570 E canto tempo leva-me para atopar alguén como Mike Smith? 478 00:23:54,570 --> 00:23:58,160 1.000 páxinas de teléfono book-- cantas páxinas que eu teño que ollar a través? 479 00:23:58,160 --> 00:23:58,905 >> Todos eles. 480 00:23:58,905 --> 00:24:00,030 Es tipo de fóra da sorte. 481 00:24:00,030 --> 00:24:03,420 Vostede literalmente ten que mirar para todos os páxina se o libro de teléfono é só 482 00:24:03,420 --> 00:24:04,450 ordenados aleatoriamente. 483 00:24:04,450 --> 00:24:06,910 Pode ter sorte e atopar Mike na primeira páxina, porque 484 00:24:06,910 --> 00:24:08,826 foi o primeiro cliente para solicitar o servizo de teléfono. 485 00:24:08,826 --> 00:24:10,760 Pero pode ser a última tamén. 486 00:24:10,760 --> 00:24:12,500 >> Entón orde aleatoria non é bo. 487 00:24:12,500 --> 00:24:16,750 Entón, supoña que temos para ordenar a libro de teléfono ou nos datos xerais tipo 488 00:24:16,750 --> 00:24:18,520 que se nos deu. 489 00:24:18,520 --> 00:24:19,440 Como podemos facer iso? 490 00:24:19,440 --> 00:24:21,360 >> Ben, deixe-me tentar un exemplo simple aquí. 491 00:24:21,360 --> 00:24:24,290 Deixe-me ir adiante e tirar unha algúns números no cadro. 492 00:24:24,290 --> 00:24:35,480 Supoña que os números que temos son, digamos, catro, dous, un e tres. 493 00:24:35,480 --> 00:24:38,390 E, Ben, clasificar estes números para nós. 494 00:24:38,390 --> 00:24:39,017 >> OK, bo. 495 00:24:39,017 --> 00:24:39,850 Como fixo iso? 496 00:24:39,850 --> 00:24:42,731 497 00:24:42,731 --> 00:24:43,230 Todo ben. 498 00:24:43,230 --> 00:24:44,710 Entón comeza coa menor valor e o máis alto, 499 00:24:44,710 --> 00:24:46,084 e iso é realmente boa intuición. 500 00:24:46,084 --> 00:24:48,080 E entender que nós os seres humanos son realmente moi 501 00:24:48,080 --> 00:24:49,913 bo en resolver problemas así, polo menos, 502 00:24:49,913 --> 00:24:51,810 cando os datos é relativamente pequena. 503 00:24:51,810 --> 00:24:54,860 Así que comeza a ter centos de números, miles de números, 504 00:24:54,860 --> 00:24:58,440 millóns de números, Ben probablemente Non podería facelo tan rápido, 505 00:24:58,440 --> 00:25:00,620 asumindo que había lagoas nos números. 506 00:25:00,620 --> 00:25:03,450 Moi fácil de contar ata un millón Se non, pode levar. 507 00:25:03,450 --> 00:25:07,150 >> Así, o algoritmo soa como Ben usado agora 508 00:25:07,150 --> 00:25:08,930 Foi busca polo menor número. 509 00:25:08,930 --> 00:25:12,900 Así, aínda que nós, humanos, pode levar en unha morea de información visuais, 510 00:25:12,900 --> 00:25:14,830 un ordenador é, en realidade algo máis limitada. 511 00:25:14,830 --> 00:25:17,560 O ordenador non pode mirar para un byte de cada vez 512 00:25:17,560 --> 00:25:20,770 ou quizais catro bytes de cada vez-- nos días de hoxe é posible 8 bytes de cada vez-- 513 00:25:20,770 --> 00:25:24,450 pero un número moi pequeno de bytes nun determinado momento. 514 00:25:24,450 --> 00:25:28,480 >> Entón, unha vez que realmente temos catro valores separados aqui-- 515 00:25:28,480 --> 00:25:32,440 e pode pensar en Ben como tendo antolhos se fose un ordenador, tales 516 00:25:32,440 --> 00:25:36,450 que non pode ver nada dun número nunha vez-- 517 00:25:36,450 --> 00:25:39,720 por iso, xeralmente pode asumir, como en Inglés, imos ler de dereita a esquerda. 518 00:25:39,720 --> 00:25:42,870 Así, o primeiro número Ben probablemente parecía logo foi de catro e moi rapidamente 519 00:25:42,870 --> 00:25:44,770 entender que é un moi grande number-- déixeme seguir buscando. 520 00:25:44,770 --> 00:25:45,357 >> Hai dous. 521 00:25:45,357 --> 00:25:45,940 Espera un minuto. 522 00:25:45,940 --> 00:25:47,070 Dous é menor que catro. 523 00:25:47,070 --> 00:25:47,986 Vou lembrar. 524 00:25:47,986 --> 00:25:49,070 Dous é agora menor. 525 00:25:49,070 --> 00:25:50,417 Agora um-- que é aínda mellor. 526 00:25:50,417 --> 00:25:51,250 Isto é aínda menor. 527 00:25:51,250 --> 00:25:54,000 Vou esquecer dous e lembra-se un momento. 528 00:25:54,000 --> 00:25:56,550 >> E podería deixar de mirar? 529 00:25:56,550 --> 00:25:58,360 Ben, podería baseadas nesta información, 530 00:25:58,360 --> 00:26:00,477 pero sería mellor busca resto da lista. 531 00:26:00,477 --> 00:26:02,060 Porque o que si é cero estaban na lista? 532 00:26:02,060 --> 00:26:03,643 E se negativo alguén fose na lista? 533 00:26:03,643 --> 00:26:07,720 El só sabe que a súa resposta é correcto se é extensa 534 00:26:07,720 --> 00:26:08,729 comproba a lista enteira. 535 00:26:08,729 --> 00:26:10,020 Entón miramos o resto deste. 536 00:26:10,020 --> 00:26:11,394 Three-- que era unha perda de tempo. 537 00:26:11,394 --> 00:26:13,540 Demos azar, pero eu estaba Aínda correcta de facelo. 538 00:26:13,540 --> 00:26:17,857 E entón agora presuntamente seleccionado o número máis pequeno 539 00:26:17,857 --> 00:26:20,440 e só colocar-lo no inicio da lista, como eu vou facer aquí. 540 00:26:20,440 --> 00:26:23,480 Agora, o que fixo despois, aínda non pensar niso case 541 00:26:23,480 --> 00:26:25,962 a este punto? 542 00:26:25,962 --> 00:26:27,670 Repita o proceso, de xeito algún tipo de loop. 543 00:26:27,670 --> 00:26:28,920 Hai unha idea familiar. 544 00:26:28,920 --> 00:26:30,860 Entón aquí é catro. 545 00:26:30,860 --> 00:26:32,110 Isto é actualmente o máis pequeno. 546 00:26:32,110 --> 00:26:33,220 Isto é un candidato. 547 00:26:33,220 --> 00:26:33,900 Non máis. 548 00:26:33,900 --> 00:26:34,770 Agora que vin dous. 549 00:26:34,770 --> 00:26:36,630 Ese é o seguinte elemento máis pequeno. 550 00:26:36,630 --> 00:26:40,800 Three-- que non é menor, entón, agora Ben pode arrincar os dous. 551 00:26:40,800 --> 00:26:44,510 >> E agora nós repita o proceso, e de curso de tres é levado para fóra a continuación. 552 00:26:44,510 --> 00:26:45,420 Repita o proceso. 553 00:26:45,420 --> 00:26:46,990 Catro é levado cara fóra. 554 00:26:46,990 --> 00:26:50,140 E agora estamos fóra dos números, así que a lista debe ser ordenada. 555 00:26:50,140 --> 00:26:51,960 >> E, de feito, este é un algoritmo formal. 556 00:26:51,960 --> 00:26:56,610 Un científico da computación sería chaman iso de "tipo de selección," 557 00:26:56,610 --> 00:27:00,880 A idea é tipo un listar iteratively-- novo 558 00:27:00,880 --> 00:27:03,807 e de novo e de novo seleccionando menor número. 559 00:27:03,807 --> 00:27:06,140 E o que é agradable sobre el é iso é tan danado intuitiva. 560 00:27:06,140 --> 00:27:07,470 É tan sinxelo. 561 00:27:07,470 --> 00:27:11,100 E pode repetir o mesmo operación de novo e de novo. 562 00:27:11,100 --> 00:27:12,150 É sinxelo. 563 00:27:12,150 --> 00:27:17,170 >> Neste caso, foi rápido, pero canto tempo fai exame realmente? 564 00:27:17,170 --> 00:27:19,880 Imos facelo parecer e sentir un pouco máis tedioso. 565 00:27:19,880 --> 00:27:24,150 Entón, un, dous, tres, catro, cinco, seis, sete, oito, nove, 10, 11, 12, 13, 14, 566 00:27:24,150 --> 00:27:26,160 15, 16-- número arbitrario. 567 00:27:26,160 --> 00:27:28,780 Eu só quería máis que tempo que a catro. 568 00:27:28,780 --> 00:27:30,780 Entón, se eu teño un todo chea de números agora --- lo 569 00:27:30,780 --> 00:27:32,420 non importa mesmo o que é-- Imos 570 00:27:32,420 --> 00:27:34,380 pensar sobre o que este algoritmo é realmente como. 571 00:27:34,380 --> 00:27:35,857 >> Supoña que hai números alí. 572 00:27:35,857 --> 00:27:38,190 Unha vez máis, non importa o que son, pero son aleatorios. 573 00:27:38,190 --> 00:27:39,679 Estou aplicando o algoritmo de Ben. 574 00:27:39,679 --> 00:27:41,220 Necesito seleccionar o menor número. 575 00:27:41,220 --> 00:27:41,761 Que fago? 576 00:27:41,761 --> 00:27:44,240 E eu vou fisicamente facelo esta vez para representalo. 577 00:27:44,240 --> 00:27:46,099 Mirando, mirando, mirando, mirando, mirando. 578 00:27:46,099 --> 00:27:48,140 Só no momento que eu chegar a o fin da lista pode 579 00:27:48,140 --> 00:27:51,230 Eu entendo a menor número era dous neste momento. 580 00:27:51,230 --> 00:27:52,720 Non está na lista. 581 00:27:52,720 --> 00:27:54,400 Entón, eu coloque dous. 582 00:27:54,400 --> 00:27:55,590 >> Que debo facer a continuación? 583 00:27:55,590 --> 00:27:58,600 Mirando, mirando, mirando, mirando. 584 00:27:58,600 --> 00:28:02,250 Agora eu atope o número sete, porque hai erros nestes números de 585 00:28:02,250 --> 00:28:03,300 pero só arbitraria. 586 00:28:03,300 --> 00:28:03,800 Todo ben. 587 00:28:03,800 --> 00:28:06,030 Entón agora podo tirar abaixo sete. 588 00:28:06,030 --> 00:28:08,860 Mirando mirando, mirando. 589 00:28:08,860 --> 00:28:11,030 >> Agora eu estou supondo, claro, que non fai Ben 590 00:28:11,030 --> 00:28:14,780 ten RAM extra, extra memoria, porque, obviamente, 591 00:28:14,780 --> 00:28:16,080 Estou mirando para o mesmo número. 592 00:28:16,080 --> 00:28:18,246 Certamente eu podería lembrar todos estes números, 593 00:28:18,246 --> 00:28:19,930 e iso é absolutamente certo. 594 00:28:19,930 --> 00:28:22,610 Pero se Ben recorda todo dos números que viu, 595 00:28:22,610 --> 00:28:24,430 el non fixo realmente progresos fundamentais 596 00:28:24,430 --> 00:28:26,170 porque xa ten a capacidade de buscar 597 00:28:26,170 --> 00:28:27,540 a través dos números na mesa. 598 00:28:27,540 --> 00:28:29,373 Lembrando todas as O número non axudan, 599 00:28:29,373 --> 00:28:32,490 porque pode aínda como un ordenador só ollar para, xa dixemos, un número 600 00:28:32,490 --> 00:28:33,080 á vez. 601 00:28:33,080 --> 00:28:35,760 Polo tanto, non hai ningún tipo de fraude alí que pode aproveitar. 602 00:28:35,760 --> 00:28:39,170 >> Entón, en realidade, como eu seguir buscando a lista, 603 00:28:39,170 --> 00:28:44,200 Eu literalmente só ten que seguir adiante e cara atrás a través del, arrincando 604 00:28:44,200 --> 00:28:45,710 a seguinte menor número. 605 00:28:45,710 --> 00:28:48,810 E como pode tipo de inferir dos meus movementos parvos, 606 00:28:48,810 --> 00:28:50,860 isto só queda moito tedioso moi rapidamente, 607 00:28:50,860 --> 00:28:54,850 e eu parecen estar indo cara atrás e adiante, para atrás e para adiante un pouco. 608 00:28:54,850 --> 00:29:03,220 Agora, para ser xusto, eu non teño que ir así como, así, imos see-- para ser xusto, 609 00:29:03,220 --> 00:29:06,310 Non teño que camiñar bastante como moitos pasos de cada vez. 610 00:29:06,310 --> 00:29:09,200 Xa que, por suposto, como I seleccionar números da lista, 611 00:29:09,200 --> 00:29:11,860 a lista restante está quedando máis curto. 612 00:29:11,860 --> 00:29:14,240 >> E así imos pensar sobre cantos pasos eu estou realmente 613 00:29:14,240 --> 00:29:16,010 traipsing través de cada vez. 614 00:29:16,010 --> 00:29:18,950 Na primeira situación tivemos 16 números, 615 00:29:18,950 --> 00:29:22,210 e así por maximally-- imos só facelo por un discussion-- 616 00:29:22,210 --> 00:29:25,640 Tiven que ollar a través de 16 números para atopar a menor. 617 00:29:25,640 --> 00:29:28,420 Pero unha vez eu arrincado menor número, como 618 00:29:28,420 --> 00:29:30,590 tempo durou a lista restante, por suposto? 619 00:29:30,590 --> 00:29:31,420 Só 15. 620 00:29:31,420 --> 00:29:34,670 Entón, cantos números fixo Ben ou eu teño ollar a través da segunda vez? 621 00:29:34,670 --> 00:29:36,832 15, só para ir e atopar o menor. 622 00:29:36,832 --> 00:29:39,540 Pero agora, por suposto, a lista é, Tamén, menor que era antes. 623 00:29:39,540 --> 00:29:42,540 Entón, como moitos pasos fixo I ten que tomar a seguinte visita? 624 00:29:42,540 --> 00:29:49,970 14 e despois 13 e despois 12, ademais de punto, punto, punto, ata que eu estou á esquerda con só un. 625 00:29:49,970 --> 00:29:53,146 Polo tanto, agora un científico da computación sería preguntar, así, o que fai que todos iguais? 626 00:29:53,146 --> 00:29:55,770 En realidade, é igual a algún formigón número que seguramente poderiamos 627 00:29:55,770 --> 00:30:00,490 facer aritmeticamente, pero queremos falar sobre a eficiencia de algoritmos 628 00:30:00,490 --> 00:30:04,940 un pouco máis como unha fórmula, independente de canto tempo a lista é. 629 00:30:04,940 --> 00:30:06,240 >> E así que sabe o que? 630 00:30:06,240 --> 00:30:09,860 Este é 16, pero como dixen antes, imos chamar o tamaño do problema 631 00:30:09,860 --> 00:30:10,970 n, onde n é un número. 632 00:30:10,970 --> 00:30:13,220 Quizais sexa 16, quizais sexa tres, quizais sexa un millón. 633 00:30:13,220 --> 00:30:13,761 Non sei. 634 00:30:13,761 --> 00:30:14,390 Eu non me importa. 635 00:30:14,390 --> 00:30:16,520 O que realmente quero é unha fórmula que poida 636 00:30:16,520 --> 00:30:19,420 usar para comparar este algoritmo contra outros algoritmos 637 00:30:19,420 --> 00:30:22,350 que alguén pode reclamar son mellores ou peores. 638 00:30:22,350 --> 00:30:25,430 >> Así, ao parecer, e só eu sei que isto de escola, 639 00:30:25,430 --> 00:30:34,790 que iso realmente funciona para o mesmo que n máis de n un sobre dous. 640 00:30:34,790 --> 00:30:40,020 E isto ocorre para igualar, de Por suposto, n ao cadrado máis n máis de dous. 641 00:30:40,020 --> 00:30:43,250 Entón, se eu quería unha fórmula por cantos pasos 642 00:30:43,250 --> 00:30:46,330 estaban implicados en ollar para todos deses números novo e de novo 643 00:30:46,330 --> 00:30:52,681 e de novo e de novo, eu diría é n ao cadrado máis n máis de dous. 644 00:30:52,681 --> 00:30:53,430 Pero vostede sabe o que? 645 00:30:53,430 --> 00:30:54,500 Isto só parece confuso. 646 00:30:54,500 --> 00:30:56,470 Realmente quero un sentido xeral das cousas. 647 00:30:56,470 --> 00:30:58,810 E pode lembrar de ensino medio que non 648 00:30:58,810 --> 00:31:00,660 é a noción de expiración maior orde. 649 00:31:00,660 --> 00:31:05,300 Cal destes termos, a n cadrado, a N, ou a media, 650 00:31:05,300 --> 00:31:07,550 ten o maior impacto no tempo? 651 00:31:07,550 --> 00:31:11,920 O maior n recibe, que destes asuntos máis? 652 00:31:11,920 --> 00:31:15,560 >> Noutras palabras, se eu conectar nun millón, n ao cadrado 653 00:31:15,560 --> 00:31:17,900 será máis probable o factor dominante, 654 00:31:17,900 --> 00:31:21,670 Unha vez que un millón de veces en si é moi grande 655 00:31:21,670 --> 00:31:23,682 que máis un adicional millóns. 656 00:31:23,682 --> 00:31:24,390 Entón vostede sabe o que? 657 00:31:24,390 --> 00:31:27,305 Este é un tal danado gran número se cadrado dun número. 658 00:31:27,305 --> 00:31:28,430 Iso realmente non importa. 659 00:31:28,430 --> 00:31:30,596 Nós só imos cruz que fóra e esquece. 660 00:31:30,596 --> 00:31:34,250 E así un científico da computación diría que a eficiencia deste algoritmo 661 00:31:34,250 --> 00:31:37,850 é da orde de n ao cadrado Quero dicir realmente unha aproximación. 662 00:31:37,850 --> 00:31:40,810 É unha especie de aproximadamente n ao cadrado. 663 00:31:40,810 --> 00:31:44,130 Co paso do tempo, a maior e maior n recibe, este 664 00:31:44,130 --> 00:31:47,610 é unha boa estimación para o que o a eficiencia ou a falta de eficiencia 665 00:31:47,610 --> 00:31:49,400 deste algoritmo é realmente. 666 00:31:49,400 --> 00:31:52,040 E eu derivar que, por suposto, de realmente facer a matemática. 667 00:31:52,040 --> 00:31:54,040 Pero agora eu só estou acenando as mans, porque eu só 668 00:31:54,040 --> 00:31:55,790 quere un sentido xeral deste algoritmo. 669 00:31:55,790 --> 00:31:58,850 >> Entón, usando a mesma lóxica, non obstante, imos considerar outro algoritmo 670 00:31:58,850 --> 00:32:01,162 xa mirou at-- busca lineal. 671 00:32:01,162 --> 00:32:02,870 Cando eu estaba a buscar ao teléfono book-- 672 00:32:02,870 --> 00:32:05,980 non clasificándose o, buscando a través do teléfono book-- 673 00:32:05,980 --> 00:32:09,197 mantivemos dicindo que era 1.000 pasos, ou 500 pasos. 674 00:32:09,197 --> 00:32:10,280 Pero imos xeneralizar iso. 675 00:32:10,280 --> 00:32:12,860 Se hai n páxinas o libro de teléfono, o que é 676 00:32:12,860 --> 00:32:17,250 o tempo de execución ou o eficiencia da busca lineal? 677 00:32:17,250 --> 00:32:19,750 E da orde de cantos pasos para atopar 678 00:32:19,750 --> 00:32:24,210 Mike Smith usando a busca lineal, a primeiro algoritmo, ou mesmo o segundo? 679 00:32:24,210 --> 00:32:27,240 680 00:32:27,240 --> 00:32:31,710 >> No peor dos casos, o Mike é ao final do libro. 681 00:32:31,710 --> 00:32:35,590 Entón, se o libro de teléfono ten 1.000 páxinas, dixemos última vez, no peor caso, 682 00:32:35,590 --> 00:32:38,380 isto pode levar máis ou menos como moitas páxinas para atopar Mike? 683 00:32:38,380 --> 00:32:38,990 Como 1000. 684 00:32:38,990 --> 00:32:39,830 É un límite superior. 685 00:32:39,830 --> 00:32:41,790 É unha peor situación posible. 686 00:32:41,790 --> 00:32:44,410 Pero, de novo, nós estamos movendo para lonxe desde números como 1.000 agora. 687 00:32:44,410 --> 00:32:45,730 É só n. 688 00:32:45,730 --> 00:32:47,470 >> Entón, cal é a conclusión lóxica? 689 00:32:47,470 --> 00:32:50,210 Buscar Mike nun teléfono libro que ten n páxinas 690 00:32:50,210 --> 00:32:55,280 pode levar, no peor caso, cantos pasos na orde de n? 691 00:32:55,280 --> 00:32:58,110 E, de feito un ordenador científico diría 692 00:32:58,110 --> 00:33:02,340 que o tempo de execución, ou o o desempeño ou a eficiencia 693 00:33:02,340 --> 00:33:07,470 ou ineficiencia, dun algoritmo como unha investigación lineal está na orde de n. 694 00:33:07,470 --> 00:33:10,010 E podemos aplicar o mesmo lóxica de atravesar algo fóra 695 00:33:10,010 --> 00:33:13,170 como eu fixen co segundo algoritmo que tivemos co libro de teléfono, 696 00:33:13,170 --> 00:33:16,040 onde fomos dúas páxinas á vez. 697 00:33:16,040 --> 00:33:20,120 >> Entón 1000 páxina do libro de teléfono pode levar 500 páxinas voltas, máis un 698 00:33:20,120 --> 00:33:21,910 dobrar un pouco para atrás. 699 00:33:21,910 --> 00:33:26,590 Polo tanto, se un libro de teléfono ten n páxinas, pero nós estamos facendo dúas páxinas por vez, 700 00:33:26,590 --> 00:33:28,900 que é aproximadamente o que? 701 00:33:28,900 --> 00:33:33,190 N ao longo de dous, de xeito que é como n máis de dous. 702 00:33:33,190 --> 00:33:38,490 Pero eu fixen a petición dun hai pouco que n ao longo dois-- 703 00:33:38,490 --> 00:33:41,060 iso é medio mesmo que n. 704 00:33:41,060 --> 00:33:44,050 É só un factor constante, científicos da computación diría. 705 00:33:44,050 --> 00:33:45,970 Nós só centrar as variables, realmente-- 706 00:33:45,970 --> 00:33:47,780 os maiores variables na ecuación. 707 00:33:47,780 --> 00:33:52,530 >> investigación de modo lineal, sexa feito un páxina de cada vez ou dúas páxinas por vez, 708 00:33:52,530 --> 00:33:54,810 é unha especie de fundamentalmente o mesmo. 709 00:33:54,810 --> 00:33:56,880 Aínda é da orde de n. 710 00:33:56,880 --> 00:34:01,930 Pero reivindicado coa miña foto anterior que a terceira algoritmo non foi 711 00:34:01,930 --> 00:34:02,480 lineal. 712 00:34:02,480 --> 00:34:03,605 Non era unha liña recta. 713 00:34:03,605 --> 00:34:08,659 Foi que liña curva, eo fórmula alxébrica había o que? 714 00:34:08,659 --> 00:34:11,812 Rexistro de n-- tan rexistro base dous n. 715 00:34:11,812 --> 00:34:14,520 E non debemos ir moi moitos detalles sobre logaritmos de hoxe, 716 00:34:14,520 --> 00:34:17,394 pero a maioría dos científicos da computación non estaba mesmo dicirlle que é a base. 717 00:34:17,394 --> 00:34:20,639 Por todo só factores constantes, por así dicir, 718 00:34:20,639 --> 00:34:22,659 só pequenas diferenzas numéricas. 719 00:34:22,659 --> 00:34:31,179 E así esta sería unha moi común camiño para ordenador particular formais 720 00:34:31,179 --> 00:34:33,949 científicos unha placa ou programadores nun cadro branco 721 00:34:33,949 --> 00:34:36,889 en realidade, argumentando que algoritmo que usarían 722 00:34:36,889 --> 00:34:39,500 ou que a eficiencia do seu algoritmo é. 723 00:34:39,500 --> 00:34:42,960 >> E iso non é necesariamente algo vostede discute en calquera gran detalle, 724 00:34:42,960 --> 00:34:47,889 pero un bo programador é alguén que ten unha base sólida, formal. 725 00:34:47,889 --> 00:34:50,120 É capaz de falar con Lo neste tipo de forma 726 00:34:50,120 --> 00:34:53,350 e realmente facer argumentos cualitativos como 727 00:34:53,350 --> 00:34:56,870 a razón pola que un algoritmo ou unha peza de software 728 00:34:56,870 --> 00:35:00,165 é superior, dalgunha forma a outra. 729 00:35:00,165 --> 00:35:02,540 Porque podería certamente basta con executar o programa dunha persoa 730 00:35:02,540 --> 00:35:04,980 e contar o número de segundos hai que para clasificar algúns números, 731 00:35:04,980 --> 00:35:06,710 e pode realizar algúns O programa de outra persoa 732 00:35:06,710 --> 00:35:08,418 e contar o número de segundos que leva. 733 00:35:08,418 --> 00:35:12,840 Pero esta é unha forma máis xeral, que pode usar para analizar algoritmos, 734 00:35:12,840 --> 00:35:15,520 se quixeren, só de papel ou só verbalmente. 735 00:35:15,520 --> 00:35:18,430 Sen mesmo executalo, sen mesmo tentando entradas de mostra, 736 00:35:18,430 --> 00:35:20,180 pode só razoar con el. 737 00:35:20,180 --> 00:35:24,670 E así, coa contratación de un creador ou téndolle especie de discutir con vostede 738 00:35:24,670 --> 00:35:28,460 porque o seu algoritmo, o seu segredo salsa para buscar millóns 739 00:35:28,460 --> 00:35:30,580 de páxinas web para o seu empresa é mellor, estes 740 00:35:30,580 --> 00:35:33,302 son os tipos de argumentos que debería idealmente ser capaz de facer. 741 00:35:33,302 --> 00:35:35,010 Ou, polo menos, estes son tipo de cousas 742 00:35:35,010 --> 00:35:40,211 que viría en discusión, na menos nunha discusión moi formal. 743 00:35:40,211 --> 00:35:40,710 Todo ben. 744 00:35:40,710 --> 00:35:44,400 Entón Ben propuxo algo chamado de selección de clasificación. 745 00:35:44,400 --> 00:35:48,200 Pero eu vou propoñer que hai outras formas de facelo, tamén. 746 00:35:48,200 --> 00:35:50,400 O que eu non me gusta moito sobre o algoritmo de Ben 747 00:35:50,400 --> 00:35:54,400 é que continuou camiñando, ou téndome andar, e cara atrás 748 00:35:54,400 --> 00:35:56,930 e de atrás e cara adiante e cara atrás e cara adiante. 749 00:35:56,930 --> 00:36:04,130 E se en vez eu fose facer algo así como eses números aquí 750 00:36:04,130 --> 00:36:08,200 e eu fose só para tratar con cada número á súa vez, como eu estou dado? 751 00:36:08,200 --> 00:36:10,780 >> Noutras palabras, é aquí A miña lista de números. 752 00:36:10,780 --> 00:36:12,944 Catro, un, tres, dous. 753 00:36:12,944 --> 00:36:14,360 E eu vou facer o seguinte. 754 00:36:14,360 --> 00:36:17,230 Eu estou indo a introducir os números onde eles pertencen, en vez 755 00:36:17,230 --> 00:36:18,980 que seleccionar os un de cada vez. 756 00:36:18,980 --> 00:36:20,820 Noutras palabras, aquí é o número catro. 757 00:36:20,820 --> 00:36:22,430 >> Aquí está a miña lista orixinal. 758 00:36:22,430 --> 00:36:25,290 E eu vou manter esencialmente unha nova lista aquí. 759 00:36:25,290 --> 00:36:26,710 Polo tanto, esta é a lista de idade. 760 00:36:26,710 --> 00:36:28,560 Esta é a nova lista. 761 00:36:28,560 --> 00:36:30,220 Eu vexo o número catro en primeiro lugar. 762 00:36:30,220 --> 00:36:34,500 Miña nova lista é inicialmente baleiro, por iso é o caso trivialmente 763 00:36:34,500 --> 00:36:36,410 que catro está a lista variada. 764 00:36:36,410 --> 00:36:39,560 Estou só tomando o número que eu son dado, e eu estou poñendo isto na miña nova lista. 765 00:36:39,560 --> 00:36:41,460 >> É esta nova lista ordenada? 766 00:36:41,460 --> 00:36:41,990 Si. 767 00:36:41,990 --> 00:36:45,090 É estúpido porque hai só un elemento, pero é absolutamente clasificadas. 768 00:36:45,090 --> 00:36:46,390 Non hai nada fóra do lugar. 769 00:36:46,390 --> 00:36:49,290 É máis interesante, este algoritmo, cando pasar á seguinte etapa. 770 00:36:49,290 --> 00:36:50,550 >> Agora eu teño un. 771 00:36:50,550 --> 00:36:55,430 Así, unha, por suposto, pertence ao inicio ou no fin desta nova lista? 772 00:36:55,430 --> 00:36:56,360 O comezo. 773 00:36:56,360 --> 00:36:58,530 Entón eu teño que facer un traballo agora. 774 00:36:58,530 --> 00:37:01,410 Fun tomar uns liberdades co meu marcador 775 00:37:01,410 --> 00:37:03,120 por só deseñar cousas onde quero que, 776 00:37:03,120 --> 00:37:05,320 pero iso non é realmente que nun ordenador. 777 00:37:05,320 --> 00:37:08,530 Un ordenador, como se sabe, ten RAM, ou memoria de acceso aleatorio, 778 00:37:08,530 --> 00:37:12,411 e iso é un byte e outro byte e outro byte. 779 00:37:12,411 --> 00:37:14,910 E se tes un gigabyte de RAM, ten mil millóns de bytes, 780 00:37:14,910 --> 00:37:16,680 pero eles están fisicamente nun único lugar. 781 00:37:16,680 --> 00:37:19,540 Non pode simplemente mover cousas arredor deseñando a no taboleiro 782 00:37:19,540 --> 00:37:20,750 onde quere. 783 00:37:20,750 --> 00:37:24,090 Entón, se a miña nova lista ten catro locais na memoria, 784 00:37:24,090 --> 00:37:27,480 Desafortunadamente a catro é xa no lugar incorrecto. 785 00:37:27,480 --> 00:37:30,410 >> Así, para introducir o número un Non podo simplemente deseña-lo aquí. 786 00:37:30,410 --> 00:37:31,901 Este lugar de memoria non existe. 787 00:37:31,901 --> 00:37:35,150 Iso sería facer trampas, e eu teño sido trampas pictoricamente por uns minutos 788 00:37:35,150 --> 00:37:35,800 aquí. 789 00:37:35,800 --> 00:37:40,950 Entón, en realidade, se eu queira poñer un aquí, Teño que copiar temporalmente os catro 790 00:37:40,950 --> 00:37:43,030 e logo poñer un alí. 791 00:37:43,030 --> 00:37:45,500 >> Isto é bo, iso é correcto, que é tecnicamente posible, 792 00:37:45,500 --> 00:37:48,410 pero entende que é un traballo adicional. 793 00:37:48,410 --> 00:37:50,460 Non só tes que poñer o número no lugar. 794 00:37:50,460 --> 00:37:53,026 A primeira vez que tivo que mover unha número, a continuación, colocar-lo no lugar, 795 00:37:53,026 --> 00:37:54,650 entón eu medio que duplicou a miña cantidade de traballo. 796 00:37:54,650 --> 00:37:55,660 Polo tanto, manter isto presente. 797 00:37:55,660 --> 00:37:57,120 >> Pero agora estou feito con este elemento. 798 00:37:57,120 --> 00:37:59,056 Agora quero incorporarse o número tres. 799 00:37:59,056 --> 00:38:00,430 Onde, por suposto, pertence? 800 00:38:00,430 --> 00:38:01,480 No medio. 801 00:38:01,480 --> 00:38:03,650 Non pode enganar máis e só poñelas alí, 802 00:38:03,650 --> 00:38:06,770 porque, de novo, esta memoria é en lugares físicos. 803 00:38:06,770 --> 00:38:10,900 Entón eu teño que copiar os catro e poñer os tres aquí. 804 00:38:10,900 --> 00:38:11,550 Non é un gran negocio. 805 00:38:11,550 --> 00:38:14,610 É só unha etapa extra novamente-- sente moi barato. 806 00:38:14,610 --> 00:38:16,445 >> Pero agora eu paso para os dous. 807 00:38:16,445 --> 00:38:17,820 Os dous, por suposto, pertence aquí. 808 00:38:17,820 --> 00:38:20,990 Agora comeza a ver como o traballo pode acumular. 809 00:38:20,990 --> 00:38:23,520 Agora o que eu teño que facer? 810 00:38:23,520 --> 00:38:28,570 Si, eu teño que ir a catro, Eu, entón, ten que copiar os tres, 811 00:38:28,570 --> 00:38:31,200 e agora podo inserir os dous. 812 00:38:31,200 --> 00:38:34,460 E a captura con este algoritmo, curiosamente, 813 00:38:34,460 --> 00:38:41,050 que supoña que temos unha forma máis extrema caso en que é, digamos oito, sete, 814 00:38:41,050 --> 00:38:45,150 seis, cinco, catro, tres, dous, un. 815 00:38:45,150 --> 00:38:49,450 Isto é, en moitos contextos, o peor escenario, 816 00:38:49,450 --> 00:38:51,570 porque o danado é, literalmente, para tras. 817 00:38:51,570 --> 00:38:53,670 >> realmente non afecta o algoritmo de Ben, 818 00:38:53,670 --> 00:38:55,940 porque na selección de Ben tipo que vai continuar 819 00:38:55,940 --> 00:38:58,359 indo e volvendo pola lista. 820 00:38:58,359 --> 00:39:01,150 E porque estaba sempre á procura a través de toda a lista restante, 821 00:39:01,150 --> 00:39:02,858 non importa en que os elementos son. 822 00:39:02,858 --> 00:39:05,630 Pero, neste caso, coa miña inserción approach-- imos tentar iso. 823 00:39:05,630 --> 00:39:08,616 >> Entón, un, dous, tres, catro, cinco, seis, sete, oito. 824 00:39:08,616 --> 00:39:11,630 Un dous tres catro, cinco, seis, sete, oito. 825 00:39:11,630 --> 00:39:14,320 Vou tomar a oito, e onde podo poñelas? 826 00:39:14,320 --> 00:39:17,260 Ben, no inicio da miña lista, porque esta nova lista é ordenada. 827 00:39:17,260 --> 00:39:18,760 E eu atravesa-la fóra. 828 00:39:18,760 --> 00:39:20,551 >> Onde debo poñer o sete? 829 00:39:20,551 --> 00:39:21,050 Danado. 830 00:39:21,050 --> 00:39:23,174 Necesita ir alí, entón Teño que facer algunha copia. 831 00:39:23,174 --> 00:39:26,820 832 00:39:26,820 --> 00:39:28,480 E agora a sete vai aquí. 833 00:39:28,480 --> 00:39:29,860 Agora eu pasar ao seis. 834 00:39:29,860 --> 00:39:30,980 Agora é aínda máis traballo. 835 00:39:30,980 --> 00:39:32,570 >> Oito ten que ir aquí. 836 00:39:32,570 --> 00:39:33,920 Sete ten que ir aquí. 837 00:39:33,920 --> 00:39:35,450 Agora, a seis pode ir aquí. 838 00:39:35,450 --> 00:39:37,950 Agora eu coller a cinco. 839 00:39:37,950 --> 00:39:40,560 Agora, a oito ten que ir aquí, sete ten que ir aquí, 840 00:39:40,560 --> 00:39:43,650 seis ten que ir aquí, e agora os cinco e repita. 841 00:39:43,650 --> 00:39:46,610 E eu estou moi ben movéndose o constantemente. 842 00:39:46,610 --> 00:39:52,950 >> Así, ao final, este algorithm-- imos chamalo de inserción sort-- realmente 843 00:39:52,950 --> 00:39:55,020 ten unha chea de traballo, tamén. 844 00:39:55,020 --> 00:39:56,970 É só diferente tipo de traballo de Ben. 845 00:39:56,970 --> 00:40:00,090 O traballo de Ben tiña-me ir e cara atrás todo o tempo, 846 00:40:00,090 --> 00:40:03,510 seleccionar o seguinte menor elemento novo e de novo. 847 00:40:03,510 --> 00:40:06,660 Por iso, foi este tipo moi visual do traballo. 848 00:40:06,660 --> 00:40:10,600 >> Este outro algoritmo que aínda é correct-- vai comezar o traballo done-- 849 00:40:10,600 --> 00:40:12,800 só cambia a cantidade de traballo. 850 00:40:12,800 --> 00:40:15,420 Parece que inicialmente está aforro, porque está só 851 00:40:15,420 --> 00:40:19,190 tratar con cada elemento diante sen andar todo 852 00:40:19,190 --> 00:40:20,930 o camiño a través da lista como Ben era. 853 00:40:20,930 --> 00:40:25,300 Pero o problema é, sobre todo nestes casos tolo onde todo está de volta, 854 00:40:25,300 --> 00:40:27,830 é só un tipo de adiando o traballo duro 855 00:40:27,830 --> 00:40:30,360 ata que ten que corrixir os seus erros. 856 00:40:30,360 --> 00:40:33,919 >> E por iso, se pode imaxinar este oito e sete anos e seis e cinco 857 00:40:33,919 --> 00:40:36,710 e despois de catro e tres e dous movendo o seu camiño a través da lista, 858 00:40:36,710 --> 00:40:39,060 temos só cambiou o tipo de traballo que estamos facendo. 859 00:40:39,060 --> 00:40:42,340 No canto de facelo no inicio da miña iteración, 860 00:40:42,340 --> 00:40:45,250 Eu estou facendo iso só na final de cada iteración. 861 00:40:45,250 --> 00:40:50,550 Así, verifícase que este algoritmo, Tamén, xeralmente chamado de ordenación por inserción, 862 00:40:50,550 --> 00:40:52,190 é tamén a orde de n ao cadrado. 863 00:40:52,190 --> 00:40:56,480 Realmente non é mellor, non é mellor en todo. 864 00:40:56,480 --> 00:41:00,810 >> Con todo, hai unha terceira visión Quere fomentar-nos a considerar, 865 00:41:00,810 --> 00:41:02,970 que é esta. 866 00:41:02,970 --> 00:41:07,850 Entón supoño miña lista, por simplicidade unha vez máis, é de catro, un, tres, 867 00:41:07,850 --> 00:41:11,080 dois-- só catro números. 868 00:41:11,080 --> 00:41:13,300 Ben tivo boa intuición, boa intuición humana 869 00:41:13,300 --> 00:41:16,340 antes, polo que se fixa o conxunto listar eventually-- tipo de inserción. 870 00:41:16,340 --> 00:41:18,020 I persuadiu connosco xunto. 871 00:41:18,020 --> 00:41:22,530 Pero imos considerar o maneira máis sinxela de resolver esta lista. 872 00:41:22,530 --> 00:41:24,110 >> A lista non está ordenada. 873 00:41:24,110 --> 00:41:26,130 Por que? 874 00:41:26,130 --> 00:41:31,920 En inglés, explicar por que En realidade non é clasificada. 875 00:41:31,920 --> 00:41:33,400 O que significa a menos ordenados? 876 00:41:33,400 --> 00:41:34,220 >> ESTUDANTE: Non é secuencial. 877 00:41:34,220 --> 00:41:34,990 >> DAVID Malan: Non secuencial. 878 00:41:34,990 --> 00:41:35,822 Dáme un exemplo. 879 00:41:35,822 --> 00:41:37,180 >> ALUMNO: Pon-as en orde. 880 00:41:37,180 --> 00:41:37,440 >> DAVID Malan: OK. 881 00:41:37,440 --> 00:41:38,790 Dáme un exemplo máis específico. 882 00:41:38,790 --> 00:41:39,832 >> ALUMNO: orde crecente. 883 00:41:39,832 --> 00:41:41,206 DAVID Malan: Orde non ascendente. 884 00:41:41,206 --> 00:41:42,100 Ser máis preciso. 885 00:41:42,100 --> 00:41:45,190 Non sei o que quere dicir con ascendente. 886 00:41:45,190 --> 00:41:47,150 O que hai de malo? 887 00:41:47,150 --> 00:41:49,930 >> ALUMNO: O menor da números non está no primeiro espazo. 888 00:41:49,930 --> 00:41:51,140 >> DAVID Malan: menor número de non no primeiro espazo. 889 00:41:51,140 --> 00:41:52,120 Sexa máis específico. 890 00:41:52,120 --> 00:41:55,000 Estou empezando a coller. 891 00:41:55,000 --> 00:41:59,470 Estamos contando, pero o que está fóra de orde aquí? 892 00:41:59,470 --> 00:42:00,707 >> ALUMNO: secuencia numérica. 893 00:42:00,707 --> 00:42:02,040 DAVID Malan: secuencia numérica. 894 00:42:02,040 --> 00:42:04,248 tipo de todos de mantemento iso aqui-- nivel moi alto. 895 00:42:04,248 --> 00:42:07,450 Só literalmente me dicir o que é mal como unha forza de cinco anos de idade. 896 00:42:07,450 --> 00:42:08,310 >> ALUMNO: Máis un. 897 00:42:08,310 --> 00:42:08,750 >> DAVID Malan: ¿Que é iso? 898 00:42:08,750 --> 00:42:09,610 >> ALUMNO: Máis un. 899 00:42:09,610 --> 00:42:11,235 >> DAVID Malan: O que quere dicir un? 900 00:42:11,235 --> 00:42:12,754 901 00:42:12,754 --> 00:42:14,170 Déame unha persoa distinta de cinco anos de idade. 902 00:42:14,170 --> 00:42:16,840 903 00:42:16,840 --> 00:42:18,330 O que hai de malo, nai? 904 00:42:18,330 --> 00:42:19,940 O que está mal, pai? 905 00:42:19,940 --> 00:42:22,808 O que quere dicir que non é ordenada? 906 00:42:22,808 --> 00:42:24,370 >> ALUMNO: Non é o lugar seguro. 907 00:42:24,370 --> 00:42:25,580 >> DAVID Malan: Cal é non no lugar seguro? 908 00:42:25,580 --> 00:42:26,174 >> ALUMNO: Four. 909 00:42:26,174 --> 00:42:27,090 DAVID Malan: OK, bo. 910 00:42:27,090 --> 00:42:29,110 Entón, catro non é onde debería estar. 911 00:42:29,110 --> 00:42:30,590 En particular, é ese dereito? 912 00:42:30,590 --> 00:42:33,000 Catro e un, o primeiro dous números que vexo. 913 00:42:33,000 --> 00:42:34,930 Isto é certo? 914 00:42:34,930 --> 00:42:36,427 Non, están fóra de orde, non? 915 00:42:36,427 --> 00:42:38,135 De feito, creo que agora sobre un ordenador, tamén. 916 00:42:38,135 --> 00:42:40,824 Pode só ollar para quizais un, quizais dúas cousas á once-- 917 00:42:40,824 --> 00:42:43,240 e, de feito, só unha cousa á vez, pero pode, polo menos 918 00:42:43,240 --> 00:42:45,790 ollar a unha cousa, entón o seguinte ben próximo a ela. 919 00:42:45,790 --> 00:42:47,380 >> Entón son estes en orde? 920 00:42:47,380 --> 00:42:48,032 Por suposto que non. 921 00:42:48,032 --> 00:42:48,740 Entón vostede sabe o que? 922 00:42:48,740 --> 00:42:51,020 Por que non tomamos bebé pasos corrixir este problema 923 00:42:51,020 --> 00:42:53,410 en vez de facer estes fantasía algoritmos, como Ben, onde 924 00:42:53,410 --> 00:42:56,440 É unha especie de resolve-lo por Looping través da lista 925 00:42:56,440 --> 00:42:59,670 en vez de facer o que eu fixen, onde Eu medio que fixa-lo como nós imos? 926 00:42:59,670 --> 00:43:03,650 Nós só literalmente romper a noción de orde numérica order--, 927 00:43:03,650 --> 00:43:06,990 chamalo de todo o que want-- para estas comparacións de pares. 928 00:43:06,990 --> 00:43:07,590 >> Catro e un. 929 00:43:07,590 --> 00:43:09,970 É esta a orde correcta? 930 00:43:09,970 --> 00:43:11,310 Entón imos solucionar isto. 931 00:43:11,310 --> 00:43:14,700 Un e catro, e logo imos só copiar isto. 932 00:43:14,700 --> 00:43:15,560 Todo ben, bo. 933 00:43:15,560 --> 00:43:17,022 Fixei un e catro. 934 00:43:17,022 --> 00:43:18,320 Tres e dous? 935 00:43:18,320 --> 00:43:18,820 Non. 936 00:43:18,820 --> 00:43:21,690 Deixe miñas palabras coincidir cos meus dedos. 937 00:43:21,690 --> 00:43:23,695 Catro e tres? 938 00:43:23,695 --> 00:43:27,930 >> Non é en orde, entón eu vou para facer un, tres, catro, dous. 939 00:43:27,930 --> 00:43:28,680 OK, bo. 940 00:43:28,680 --> 00:43:32,310 Agora, catro e dous? 941 00:43:32,310 --> 00:43:33,370 Necesitamos corrixir isto, tamén. 942 00:43:33,370 --> 00:43:36,700 Entón, un, dous, tres, catro. 943 00:43:36,700 --> 00:43:39,820 Entón, se clasifica? 944 00:43:39,820 --> 00:43:43,170 Non, pero é o máis preto de ordenar? 945 00:43:43,170 --> 00:43:48,930 >> É, xa que nós modificado este erro, nós modificado este erro, 946 00:43:48,930 --> 00:43:50,370 e nós modificado este erro. 947 00:43:50,370 --> 00:43:52,420 Por iso, fixo tres erros, sen dúbida. 948 00:43:52,420 --> 00:43:58,100 Aínda realmente non parece ordenada, pero é obxectivamente máis preto de ordenado 949 00:43:58,100 --> 00:44:00,080 porque fixa algúns deses erros. 950 00:44:00,080 --> 00:44:02,047 >> Agora o que fago agora? 951 00:44:02,047 --> 00:44:03,630 I tipo de alcanzar o fin da lista. 952 00:44:03,630 --> 00:44:05,680 Eu parecía fixado os erros, pero non. 953 00:44:05,680 --> 00:44:08,510 Porque neste caso, algúns números podería borbulhava máis preto 954 00:44:08,510 --> 00:44:10,410 para outros números aínda están fóra de orde. 955 00:44:10,410 --> 00:44:12,951 Entón, imos facelo de novo, e eu vou só facelo no lugar neste momento. 956 00:44:12,951 --> 00:44:14,170 Un e tres? 957 00:44:14,170 --> 00:44:14,720 Está ben. 958 00:44:14,720 --> 00:44:16,070 Tres e dous? 959 00:44:16,070 --> 00:44:17,560 Claro que non, entón imos cambiar isto. 960 00:44:17,560 --> 00:44:19,160 Entón, dous, tres. 961 00:44:19,160 --> 00:44:21,340 Tres e catro? 962 00:44:21,340 --> 00:44:24,370 E agora imos ser particularmente pedante aquí. 963 00:44:24,370 --> 00:44:26,350 É clasificado? 964 00:44:26,350 --> 00:44:29,280 Vostede humanos sabe que está clasificada. 965 00:44:29,280 --> 00:44:30,400 >> Eu debería tentar de novo. 966 00:44:30,400 --> 00:44:31,900 Entón, Olivia está propondo que tente de novo. 967 00:44:31,900 --> 00:44:32,530 Por que? 968 00:44:32,530 --> 00:44:35,810 Porque un ordenador non ten o luxo dos nosos ollos humanos 969 00:44:35,810 --> 00:44:38,080 de só mirando traseira-- OK, eu son feito. 970 00:44:38,080 --> 00:44:41,610 Como o ordenador determinar que a lista está clasificado? 971 00:44:41,610 --> 00:44:44,590 Mecánicamente. 972 00:44:44,590 --> 00:44:47,650 >> Eu debería pasar por unha vez máis, e só se I 973 00:44:47,650 --> 00:44:51,190 non faga / atopa algún erro pode I entón concluír que o equipo, si, 974 00:44:51,190 --> 00:44:51,980 somos bos de ir. 975 00:44:51,980 --> 00:44:54,850 Así, un e dous, dous e tres, tres e catro. 976 00:44:54,850 --> 00:44:58,030 Agora podo definitivamente dicir que este é clasificadas, porque eu non fixo cambios. 977 00:44:58,030 --> 00:45:01,940 Agora sería un erro e só tolo si, o ordenador, 978 00:45:01,940 --> 00:45:05,640 Pregunta esas mesmas preguntas novo esperando respostas diferentes. 979 00:45:05,640 --> 00:45:07,110 non debería pasar. 980 00:45:07,110 --> 00:45:08,600 >> E entón agora a lista é ordenada. 981 00:45:08,600 --> 00:45:12,630 Desafortunadamente, duración de este algoritmo tamén é n cadrado. 982 00:45:12,630 --> 00:45:13,130 Por que? 983 00:45:13,130 --> 00:45:19,520 Porque ten n números, e na peor caso ten que mover n números 984 00:45:19,520 --> 00:45:23,637 n veces, porque ten que seguir de volta para comprobar e corrixir potencialmente 985 00:45:23,637 --> 00:45:24,220 estas cifras. 986 00:45:24,220 --> 00:45:26,280 E podemos facer máis análise formal, tamén. 987 00:45:26,280 --> 00:45:29,530 >> Entón, todo isto é para dicir que tomamos tres enfoques diferentes, unha 988 00:45:29,530 --> 00:45:32,210 deles inmediatamente intuitiva fóra do pau de Ben 989 00:45:32,210 --> 00:45:35,170 á miña inserción suxerido tipo a este 990 00:45:35,170 --> 00:45:38,540 onde tipo de perder de vista o bosque para as árbores inicialmente. 991 00:45:38,540 --> 00:45:41,760 Pero, entón, se tomar un paso atrás, voila, temos fixo a noción de clasificación. 992 00:45:41,760 --> 00:45:43,824 Polo tanto, este é, atrévome a dicir, un nivel máis baixo posible 993 00:45:43,824 --> 00:45:45,740 que algúns dos outros algoritmos, pero imos 994 00:45:45,740 --> 00:45:48,550 ver se non podemos ver estes a través deste. 995 00:45:48,550 --> 00:45:51,450 >> Entón, este é un bo programa que alguén 996 00:45:51,450 --> 00:45:56,110 escribiu usando barras de cores que hai de vai facer o seguinte para nós. 997 00:45:56,110 --> 00:45:57,736 Cada unha destas barras representa un número. 998 00:45:57,736 --> 00:46:00,026 Taller barra, maior o número, menores do bar, 999 00:46:00,026 --> 00:46:00,990 Canto menor o número. 1000 00:46:00,990 --> 00:46:05,880 Así, idealmente, queremos unha boa pirámide onde comeza pequeno e recibe gran, 1001 00:46:05,880 --> 00:46:08,330 e iso significaría que estas barras son clasificadas. 1002 00:46:08,330 --> 00:46:11,200 Entón, eu estou indo a ir adiante e elixir, por exemplo, o algoritmo de Ben 1003 00:46:11,200 --> 00:46:13,990 tipo selección first--. 1004 00:46:13,990 --> 00:46:16,220 >> E teña en conta o que está facendo. 1005 00:46:16,220 --> 00:46:18,670 A forma como eles optaron por facer ver este algoritmo 1006 00:46:18,670 --> 00:46:22,090 é que, como eu era camiñando a través da miña lista, 1007 00:46:22,090 --> 00:46:24,710 este programa está camiñando a través da súa lista de números, 1008 00:46:24,710 --> 00:46:28,160 destacando en cada rosa número que está mirando. 1009 00:46:28,160 --> 00:46:32,360 E o que está a piques de pasar agora? 1010 00:46:32,360 --> 00:46:35,154 >> O menor número de que I é Ben atopou de súpeto 1011 00:46:35,154 --> 00:46:36,820 é movido para o inicio da lista. 1012 00:46:36,820 --> 00:46:40,037 E noten que fixeron evict o número que estaba alí, 1013 00:46:40,037 --> 00:46:41,120 e iso é perfectamente ben. 1014 00:46:41,120 --> 00:46:42,600 Non entrar nese nivel de detalle. 1015 00:46:42,600 --> 00:46:44,308 Pero hai que poñer este número en algún lugar, 1016 00:46:44,308 --> 00:46:47,775 por iso, só mudouse para o lugar aberto que foi creado. 1017 00:46:47,775 --> 00:46:49,900 Entón eu vou para acelerar este -Se, porque se non, 1018 00:46:49,900 --> 00:46:51,871 fai-se rapidamente moi tedioso. 1019 00:46:51,871 --> 00:46:55,800 1020 00:46:55,800 --> 00:46:58,600 Animación speed-- alí imos nós. 1021 00:46:58,600 --> 00:47:01,850 Entón, agora mesmo principio Estaba aplicando, pero 1022 00:47:01,850 --> 00:47:06,540 Pode comezar a sentir o algoritmo, se vai, ou velo un pouco máis claramente. 1023 00:47:06,540 --> 00:47:13,190 E este algoritmo ten o efecto de seleccionar o seguinte elemento máis pequeno, 1024 00:47:13,190 --> 00:47:16,422 entón vai comezar a velo rampla ata a esquerda. 1025 00:47:16,422 --> 00:47:19,130 E en cada iteración, como eu proposto, que fai algo menos de traballo. 1026 00:47:19,130 --> 00:47:21,921 Non ten que percorrer todo o camiño de volta á extrema esquerda da lista, 1027 00:47:21,921 --> 00:47:23,900 porque xa coñece os son clasificadas. 1028 00:47:23,900 --> 00:47:28,129 Entón, que tipo de parece que é acelerando, aínda que cada paso é 1029 00:47:28,129 --> 00:47:29,420 tendo a mesma cantidade de tempo. 1030 00:47:29,420 --> 00:47:31,600 Hai poucas etapas restantes. 1031 00:47:31,600 --> 00:47:35,240 E agora pode tipo de sentir a algoritmo de limpeza do final do mesmo, 1032 00:47:35,240 --> 00:47:37,040 e de feito xa está clasificada. 1033 00:47:37,040 --> 00:47:41,620 >> Entón ordenación por inserción é todo feito. 1034 00:47:41,620 --> 00:47:43,600 Eu necesidade de re-embaralhar a matriz. 1035 00:47:43,600 --> 00:47:45,940 E teña en conta Só pode manter randomização-lo, 1036 00:47:45,940 --> 00:47:50,630 e teremos un achegamento das a mesma visión, ordenación por inserción. 1037 00:47:50,630 --> 00:47:55,050 Déixeme retarda-lo para aquí. 1038 00:47:55,050 --> 00:47:56,915 Imos comezar que máis. 1039 00:47:56,915 --> 00:47:57,414 Parar. 1040 00:47:57,414 --> 00:48:00,662 1041 00:48:00,662 --> 00:48:02,410 >> Imos saltar catro. 1042 00:48:02,410 --> 00:48:03,200 Alí imos nós. 1043 00:48:03,200 --> 00:48:04,190 Randomize eles matriz. 1044 00:48:04,190 --> 00:48:05,555 E aquí vai-- tipo de inserción. 1045 00:48:05,555 --> 00:48:10,260 1046 00:48:10,260 --> 00:48:12,800 Xogar. 1047 00:48:12,800 --> 00:48:17,280 Teña en conta que está lidando con cada elemento que atopa inmediatamente, 1048 00:48:17,280 --> 00:48:20,282 pero se pertence a o aviso de lugar incorrecto 1049 00:48:20,282 --> 00:48:21,740 todo o traballo que ten que pasar. 1050 00:48:21,740 --> 00:48:24,700 Temos que seguir cambiando máis e máis elementos para abrir espazo 1051 00:48:24,700 --> 00:48:27,340 para o que queremos poñer no lugar. 1052 00:48:27,340 --> 00:48:30,740 >> Entón, nós estamos focando en extremo esquerda da lista única. 1053 00:48:30,740 --> 00:48:34,460 Lembre que non temos sequera mirou at-- nós non destacaron en calquera cousa rosa 1054 00:48:34,460 --> 00:48:35,610 cara á dereita. 1055 00:48:35,610 --> 00:48:38,180 Estamos só lidando con os problemas a medida que avanzamos, 1056 00:48:38,180 --> 00:48:40,430 pero estamos creando unha morea de traballar para nós aínda. 1057 00:48:40,430 --> 00:48:44,410 E así se acelerar este proceso agora a estar completa, 1058 00:48:44,410 --> 00:48:46,210 el ten unha sensación diferente para el, de feito. 1059 00:48:46,210 --> 00:48:50,150 É só incidir sobre o fin esquerdo, pero facendo un pouco máis de traballo como needed-- 1060 00:48:50,150 --> 00:48:53,230 tipo de cousas suavización máis, arranxar as cousas, 1061 00:48:53,230 --> 00:48:58,350 pero tratar última instancia, co cada elemento de un de cada vez 1062 00:48:58,350 --> 00:49:07,740 ata chegar ao as-- ben, nós Todos sabemos como iso vai acabar, 1063 00:49:07,740 --> 00:49:09,700 por iso é un pouco nada asombroso quizais. 1064 00:49:09,700 --> 00:49:12,830 >> Pero a lista na end-- spoiler-- será resolto. 1065 00:49:12,830 --> 00:49:15,300 Entón, imos ollar para un último. 1066 00:49:15,300 --> 00:49:16,840 Non podemos ignorar o momento. 1067 00:49:16,840 --> 00:49:18,000 Estamos case alí. 1068 00:49:18,000 --> 00:49:19,980 Dúas para ir, un para ir. 1069 00:49:19,980 --> 00:49:22,680 E listo. 1070 00:49:22,680 --> 00:49:23,450 Excelente. 1071 00:49:23,450 --> 00:49:27,220 >> Entón agora imos facer unha última, re-randomização con bubble sort. 1072 00:49:27,220 --> 00:49:31,690 E teña en conta aquí, sobre todo si retarda-lo abaixo, iso manter mergullando totalmente. 1073 00:49:31,690 --> 00:49:36,830 Pero teña en conta que só fai pairwise tipo comparisons-- de solucións locais. 1074 00:49:36,830 --> 00:49:39,050 Pero así que chegamos a o fin da lista en cor rosa, 1075 00:49:39,050 --> 00:49:40,690 o que vai ter que pasar de novo? 1076 00:49:40,690 --> 00:49:44,539 1077 00:49:44,539 --> 00:49:46,830 Si, vai ter que comezar de novo, porque só 1078 00:49:46,830 --> 00:49:49,870 erros de pares fixos. 1079 00:49:49,870 --> 00:49:53,120 E que pode revelar aínda outros. 1080 00:49:53,120 --> 00:49:58,950 E entón se acelerar este proceso, vai ver que, así como o nome indica, 1081 00:49:58,950 --> 00:50:01,870 menor elements-- ou mellor, os elements-- maiores empezan 1082 00:50:01,870 --> 00:50:03,740 a burbulla ata o cumio, se quere. 1083 00:50:03,740 --> 00:50:07,380 E os elementos son menores empezando a burbulla para abaixo á esquerda. 1084 00:50:07,380 --> 00:50:10,780 E, de feito, este é o tipo de o efecto visual ben. 1085 00:50:10,780 --> 00:50:17,150 E así que vai acabar terminando dun xeito moi semellante, tamén. 1086 00:50:17,150 --> 00:50:19,160 >> Non temos a habitar nun presente particular. 1087 00:50:19,160 --> 00:50:21,010 Déixeme abrir iso agora tamén. 1088 00:50:21,010 --> 00:50:24,040 Hai algúns outros algoritmos de ordenación en todo o mundo, algúns dos cales 1089 00:50:24,040 --> 00:50:25,580 son capturados aquí. 1090 00:50:25,580 --> 00:50:29,960 E, sobre todo, para os alumnos que non son necesariamente visual ou matemáticas, 1091 00:50:29,960 --> 00:50:31,930 como fixemos antes, podemos Tamén facelo audially 1092 00:50:31,930 --> 00:50:34,210 asociar un son con iso. 1093 00:50:34,210 --> 00:50:36,990 E só por diversión, aquí está un algúns algoritmos diferentes, 1094 00:50:36,990 --> 00:50:40,950 e un deles, en especial, está Vai notar é chamado de "merge sort". 1095 00:50:40,950 --> 00:50:43,250 >> É realmente unha fundamentalmente mellor algoritmo, 1096 00:50:43,250 --> 00:50:45,860 de tal forma que merge sort, un dos os que está a piques de ver, 1097 00:50:45,860 --> 00:50:49,170 non é orde de n ao cadrado. 1098 00:50:49,170 --> 00:50:57,280 É na orde rexistro de n veces de n, que é realmente menor e, polo tanto, 1099 00:50:57,280 --> 00:50:58,940 máis rápido que os outros tres. 1100 00:50:58,940 --> 00:51:00,670 E hai un par outra bobas que veremos. 1101 00:51:00,670 --> 00:51:01,933 >> Entón, imos con algún son. 1102 00:51:01,933 --> 00:51:06,620 1103 00:51:06,620 --> 00:51:10,490 Esta é a ordenación por inserción, polo que de novo é só xestionar os elementos 1104 00:51:10,490 --> 00:51:13,420 como eles veñen. 1105 00:51:13,420 --> 00:51:17,180 Este é bubble sort, polo que é considerándose os pares de cada vez. 1106 00:51:17,180 --> 00:51:22,030 1107 00:51:22,030 --> 00:51:24,490 E, de novo, os maiores elementos están burbullas ata o cumio. 1108 00:51:24,490 --> 00:51:38,098 1109 00:51:38,098 --> 00:51:41,710 >> Logo tipo de selección. 1110 00:51:41,710 --> 00:51:45,420 Este é o algoritmo de Ben, onde novo está seleccionando de forma iterativa 1111 00:51:45,420 --> 00:51:46,843 o seguinte elemento máis pequeno. 1112 00:51:46,843 --> 00:51:49,801 1113 00:51:49,801 --> 00:51:53,900 E unha vez máis, agora pode realmente escoitar que está acelerando, pero só na medida 1114 00:51:53,900 --> 00:51:58,230 como está facendo cada vez menos traballar en cada iteración. 1115 00:51:58,230 --> 00:52:04,170 Este é o máis rápido un, merge sort, que é clasificar grupos de números 1116 00:52:04,170 --> 00:52:05,971 xuntos e logo, combina-las. 1117 00:52:05,971 --> 00:52:07,720 Así look-- esquerda metade xa están clasificados. 1118 00:52:07,720 --> 00:52:14,165 >> Agora que está clasificando a metade dereita, e agora vai combina-los nun só. 1119 00:52:14,165 --> 00:52:19,160 Isto é algo chamado "Gnome tipo." 1120 00:52:19,160 --> 00:52:23,460 E pode tipo de ver que vai alí e para aquí, 1121 00:52:23,460 --> 00:52:27,950 que fixa o traballo un pouco aquí e antes de proceder á nova obra. 1122 00:52:27,950 --> 00:52:32,900 1123 00:52:32,900 --> 00:52:33,692 E iso. 1124 00:52:33,692 --> 00:52:36,400 Hai outro tipo, que é Realmente só para fins académicos, 1125 00:52:36,400 --> 00:52:40,980 chamado "tipo estúpido", que leva os seus datos, clasifícase o de forma aleatoria, 1126 00:52:40,980 --> 00:52:43,350 e comproba se está clasificada. 1127 00:52:43,350 --> 00:52:47,880 E se non é, re-ordena-lo azar, comproba se está clasificado, 1128 00:52:47,880 --> 00:52:49,440 e se non se repite. 1129 00:52:49,440 --> 00:52:52,660 E, en teoría, probabilisticamente isto vai rematar, 1130 00:52:52,660 --> 00:52:54,140 pero despois de un pouco de tempo. 1131 00:52:54,140 --> 00:52:56,930 Non é o máis eficiente de algoritmos. 1132 00:52:56,930 --> 00:53:02,550 Así, calquera preguntas sobre os algoritmos particulares ou nada 1133 00:53:02,550 --> 00:53:04,720 relacionados alí, tamén? 1134 00:53:04,720 --> 00:53:09,430 >> Ben, imos agora desmembrar o que todos estas liñas son que teño deseñado 1135 00:53:09,430 --> 00:53:15,090 eo que eu estou supondo que o ordenador pode facer debaixo do capó. 1136 00:53:15,090 --> 00:53:18,650 Eu diría que todos estes números Eu sigo drawing-- precisan para obter 1137 00:53:18,650 --> 00:53:21,330 almacenado nalgún lugar na memoria. 1138 00:53:21,330 --> 00:53:24,130 Imos librar dese cara agora, tamén. 1139 00:53:24,130 --> 00:53:30,110 >> Así, unha parte da memoria nunha Computador-- tan RAM DIMM é 1140 00:53:30,110 --> 00:53:35,480 o que buscou onte dobre memoria en liña module-- parécese iso. 1141 00:53:35,480 --> 00:53:39,370 E cada unha destas pequenas fichas negras é un número de bytes, normalmente. 1142 00:53:39,370 --> 00:53:44,380 E entón os pinos de ouro son como o fíos que conectan ao ordenador, 1143 00:53:44,380 --> 00:53:47,521 ea placa de silicio verde é só o que mantén todo en conxunto. 1144 00:53:47,521 --> 00:53:48,770 Entón o que iso realmente significa? 1145 00:53:48,770 --> 00:53:53,180 Se eu tipo de deseñar esta mesma imaxe, imos supor que a sinxeleza 1146 00:53:53,180 --> 00:53:55,280 que este DIMM, dobre Liña Memory Module, 1147 00:53:55,280 --> 00:54:00,530 é un gigabyte de memoria RAM, un gigabyte de memoria, que é o número de bytes en total? 1148 00:54:00,530 --> 00:54:02,100 Un gigabyte é cantos bytes? 1149 00:54:02,100 --> 00:54:04,860 1150 00:54:04,860 --> 00:54:06,030 Máis que iso. 1151 00:54:06,030 --> 00:54:09,960 1124 é kilo, 1000. 1152 00:54:09,960 --> 00:54:11,730 Mega é millóns. 1153 00:54:11,730 --> 00:54:14,570 Giga é mil millóns. 1154 00:54:14,570 --> 00:54:15,070 >> Eu estou mentindo? 1155 00:54:15,070 --> 00:54:16,670 podemos ata ler a etiqueta? 1156 00:54:16,670 --> 00:54:19,920 Isto é, en realidade, 128 gigabytes, polo que é máis. 1157 00:54:19,920 --> 00:54:22,130 Pero imos finxir que iso é só un gigabyte. 1158 00:54:22,130 --> 00:54:25,640 Entón isto significa que hai mil millóns bytes de memoria dispoñible para min 1159 00:54:25,640 --> 00:54:29,770 ou 8 millóns de bits, pero imos para falar en termos de bytes agora, 1160 00:54:29,770 --> 00:54:30,750 avanzar. 1161 00:54:30,750 --> 00:54:36,330 >> Entón, o que iso significa que o que un byte, este é un byte, 1162 00:54:36,330 --> 00:54:38,680 este é un byte, e se realmente queriamos 1163 00:54:38,680 --> 00:54:43,280 para ser máis específico, teriamos que deseñar un billón de pequenos cadrados. 1164 00:54:43,280 --> 00:54:44,320 Pero o que significa isto? 1165 00:54:44,320 --> 00:54:46,420 Ben, deixe-me só aumentar en nesta imaxe. 1166 00:54:46,420 --> 00:54:50,900 Se eu teño algo que parece así agora, iso é catro bytes. 1167 00:54:50,900 --> 00:54:53,710 >> E así eu podería poñer catro números aquí. 1168 00:54:53,710 --> 00:54:54,990 Un dous tres catro. 1169 00:54:54,990 --> 00:55:00,170 Ou eu podería poñer catro letras ou símbolos. 1170 00:55:00,170 --> 00:55:02,620 "Hey!" podería ir para a dereita alí, porque cada unha das cartas, 1171 00:55:02,620 --> 00:55:04,370 discutir anteriormente, Pode ser representado 1172 00:55:04,370 --> 00:55:06,650 con oito bits ou ASCII ou un byte. 1173 00:55:06,650 --> 00:55:09,370 Polo tanto, noutras palabras, pode poñer 8 mil millóns de cousas dentro 1174 00:55:09,370 --> 00:55:11,137 dun presente da vara da memoria. 1175 00:55:11,137 --> 00:55:14,345 Agora o que iso supón para poñer as cousas de volta a volta atrás na memoria como esta? 1176 00:55:14,345 --> 00:55:17,330 Isto é o que un programador chamaría dun "array". 1177 00:55:17,330 --> 00:55:21,250 Nun programa de ordenador, non pensa sobre o hardware subxacente, per se. 1178 00:55:21,250 --> 00:55:24,427 Só pensa en si mesmo como tendo acceso a un total mil millóns de bytes, 1179 00:55:24,427 --> 00:55:26,010 e pode que queira con el. 1180 00:55:26,010 --> 00:55:27,880 Pero por conveniencia normalmente é útil 1181 00:55:27,880 --> 00:55:31,202 para manter o seu dereito de memoria á beira do outro como este. 1182 00:55:31,202 --> 00:55:33,660 Entón, se eu aumentar o zoom en isto-- porque certamente non vai 1183 00:55:33,660 --> 00:55:39,310 deseñar un billón de pequenos squares-- imos supor que este cadro representa 1184 00:55:39,310 --> 00:55:40,610 esta vara da memoria agora. 1185 00:55:40,610 --> 00:55:43,800 E eu vou só chamar a todos cantos o meu marcador acaba me dando aquí. 1186 00:55:43,800 --> 00:55:46,420 1187 00:55:46,420 --> 00:55:52,300 Polo tanto, agora temos unha vara de memoria na tarxeta 1188 00:55:52,300 --> 00:55:56,400 que ten un, dous, tres, catro, cinco, seis, un, dous, tres, catro, cinco, seis, 1189 00:55:56,400 --> 00:56:01,130 seven-- así 42 bytes de memoria sobre o total da pantalla. 1190 00:56:01,130 --> 00:56:01,630 Grazas. 1191 00:56:01,630 --> 00:56:02,838 Si, fixen a miña aritmética dereita. 1192 00:56:02,838 --> 00:56:05,120 Así, 42 bytes de memoria aquí. 1193 00:56:05,120 --> 00:56:06,660 Entón o que iso realmente significa? 1194 00:56:06,660 --> 00:56:09,830 Ben, un programador de ordenador sería realmente xeral 1195 00:56:09,830 --> 00:56:12,450 pensa deste como memoria endereçável. 1196 00:56:12,450 --> 00:56:16,630 Noutras palabras, cada unha delas locais na memoria, en hardware, 1197 00:56:16,630 --> 00:56:18,030 ten un enderezo único. 1198 00:56:18,030 --> 00:56:22,020 >> Non é tan complexo como un Brattle Square, Cambridge, Mass., 02138. 1199 00:56:22,020 --> 00:56:23,830 Ao contrario, é só un número. 1200 00:56:23,830 --> 00:56:27,930 Este é byte número cero, é dicir un, é dicir dous, isto é tres, 1201 00:56:27,930 --> 00:56:30,327 e esta é de 41. 1202 00:56:30,327 --> 00:56:30,910 Espera un minuto. 1203 00:56:30,910 --> 00:56:32,510 Eu penso que eu dixen 42 un momento atrás. 1204 00:56:32,510 --> 00:56:35,050 1205 00:56:35,050 --> 00:56:37,772 Comecei a contar desde cero, de xeito que é realmente correcto. 1206 00:56:37,772 --> 00:56:40,980 Agora non temos realmente deséñase la como unha rede, e se deseña-lo como unha reixa 1207 00:56:40,980 --> 00:56:43,520 Creo que as cousas realmente obter un pouco erro. 1208 00:56:43,520 --> 00:56:46,650 O que un programador faría, na súa propia mente, 1209 00:56:46,650 --> 00:56:50,310 xeralmente pensan desta memoria como é como unha fita, 1210 00:56:50,310 --> 00:56:53,340 como un anaco de cinta adhesiva que só vai sobre e sobre para sempre 1211 00:56:53,340 --> 00:56:54,980 ou ata quedar sen memoria. 1212 00:56:54,980 --> 00:56:59,200 Así, un xeito máis común para debuxar e só pensar sobre a memoria 1213 00:56:59,200 --> 00:57:03,710 sería a de que esta é cero bytes, un, dous, tres, e logo, punto, punto, punto. 1214 00:57:03,710 --> 00:57:07,650 E ten 42 destes bytes total, o mesmo aínda permanece pode realmente 1215 00:57:07,650 --> 00:57:09,480 ser algo máis como este. 1216 00:57:09,480 --> 00:57:12,850 >> Entón, se vostede pensa agora do seu memoria como esta, así como unha cinta, 1217 00:57:12,850 --> 00:57:17,640 iso é o que un programador de novo chamaría dunha matriz de memoria. 1218 00:57:17,640 --> 00:57:20,660 E cando quere realmente gardar algo en memoria dun ordenador, 1219 00:57:20,660 --> 00:57:23,290 normalmente facer cousas tenda back-to-back to back-to-back. 1220 00:57:23,290 --> 00:57:25,010 Entón, estamos a falar de números. 1221 00:57:25,010 --> 00:57:30,880 E cando eu quería para resolver problemas como catro, un, tres, dous, 1222 00:57:30,880 --> 00:57:33,820 aínda que eu estaba só un debuxo só o número catro, un, tres, 1223 00:57:33,820 --> 00:57:39,490 dous no bordo, o ordenador faría Realmente ten esta configuración na memoria. 1224 00:57:39,490 --> 00:57:43,347 >> E o que sería a carón do dous na memoria do ordenador? 1225 00:57:43,347 --> 00:57:44,680 Ben, non hai ningunha resposta a iso. 1226 00:57:44,680 --> 00:57:45,770 Nós realmente non sabemos. 1227 00:57:45,770 --> 00:57:48,200 E desde que a O ordenador non precisa del, 1228 00:57:48,200 --> 00:57:51,440 non se preocupe que é o seguinte aos números que se preocupa. 1229 00:57:51,440 --> 00:57:55,130 E cando eu dixen anteriormente que un ordenador só pode ollar a un enderezo de cada vez, 1230 00:57:55,130 --> 00:57:56,170 este é o tipo de por que. 1231 00:57:56,170 --> 00:57:59,490 >> Non ao contrario dun rexistro xogador e unha cabeza de lectura 1232 00:57:59,490 --> 00:58:03,030 só ser capaz de ollar para un correcto suco nun rexistro da vella escola física 1233 00:58:03,030 --> 00:58:06,500 á vez, de xeito semellante Pode un ordenador grazas 1234 00:58:06,500 --> 00:58:09,810 a CPU ea súa conxunto de instrucións Intel, 1235 00:58:09,810 --> 00:58:12,480 entre cuxos instrución é lido a partir da memoria 1236 00:58:12,480 --> 00:58:15,590 ou gardar en memory-- un ordenador só pode ollar 1237 00:58:15,590 --> 00:58:19,210 nun lugar de cada vez-- por veces, unha combinación dos mesmos, 1238 00:58:19,210 --> 00:58:21,770 pero realmente só un lugar de cada vez. 1239 00:58:21,770 --> 00:58:24,770 Entón, cando estabamos facendo estes varios algoritmos, 1240 00:58:24,770 --> 00:58:28,110 Non só estou escribindo nun vacuum-- catro, un, tres, dous. 1241 00:58:28,110 --> 00:58:30,849 Estas cifras, en realidade, pertencen algures na memoria física. 1242 00:58:30,849 --> 00:58:32,890 Polo tanto, hai pequeno transistores ou algún tipo 1243 00:58:32,890 --> 00:58:35,840 da electrónica debaixo da Hood almacenar eses valores. 1244 00:58:35,840 --> 00:58:40,460 >> E en total, cantos bits son implicados agora, só para quedar claro? 1245 00:58:40,460 --> 00:58:45,580 Polo tanto, este é catro bytes, ou agora é 32 bits total. 1246 00:58:45,580 --> 00:58:49,280 Entón, en realidade existen 32 ceros e aqueles que compoñen estas catro cousas. 1247 00:58:49,280 --> 00:58:52,070 Hai aínda máis aquí, pero unha vez máis, non se preocupan con iso. 1248 00:58:52,070 --> 00:58:55,120 >> Entón agora imos facer outra pregunta empregando memoria, 1249 00:58:55,120 --> 00:58:57,519 pois que a finais do día está na varianza. 1250 00:58:57,519 --> 00:59:00,310 Non importa o que pode facer o ordenador, ao final do día 1251 00:59:00,310 --> 00:59:02,560 hardware aínda o é mesmo debaixo do capó. 1252 00:59:02,560 --> 00:59:04,670 Cómo podería almacenar unha palabra aquí? 1253 00:59:04,670 --> 00:59:09,710 Ben, unha palabra nun ordenador, como "Hey!" sería almacenado como esta. 1254 00:59:09,710 --> 00:59:12,300 E se quería un máis Word, pode simplemente 1255 00:59:12,300 --> 00:59:19,120 substituír este e dicir algo como "Ola" e tenda que aquí. 1256 00:59:19,120 --> 00:59:23,930 >> E aquí, tamén, este contiguidade é realmente unha vantaxe, 1257 00:59:23,930 --> 00:59:26,530 porque un ordenador pode só ler de dereita a esquerda. 1258 00:59:26,530 --> 00:59:28,680 Pero aquí está unha pregunta. 1259 00:59:28,680 --> 00:59:33,480 No contexto desta palabra, h-e-l-l-o, punto de exclamación, 1260 00:59:33,480 --> 00:59:38,740 como pode o equipo sabe onde a palabra comeza e onde a palabra remata? 1261 00:59:38,740 --> 00:59:41,690 1262 00:59:41,690 --> 00:59:43,800 No contexto de números, Como o ordenador 1263 00:59:43,800 --> 00:59:48,396 saber canto tempo a secuencia de números é ou onde comeza? 1264 00:59:48,396 --> 00:59:50,270 Ben, acontece out-- e non imos entrar moi 1265 00:59:50,270 --> 00:59:54,970 a este nivel de detail-- ordenadores mover cousas arredor da memoria 1266 00:59:54,970 --> 00:59:57,800 literalmente, por medio destes enderezos. 1267 00:59:57,800 --> 01:00:02,080 Así, nun ordenador, se está escribir código para gardar cousas 1268 01:00:02,080 --> 01:00:05,800 como palabras, o que está facendo realmente está escribindo 1269 01:00:05,800 --> 01:00:11,320 expresións que lembran onde en memoria do ordenador estas palabras son. 1270 01:00:11,320 --> 01:00:14,370 Entón deixe-me facer unha moi, exemplo moi sinxelo. 1271 01:00:14,370 --> 01:00:18,260 >> Eu estou indo a ir adiante e abrir un programa de texto simple, 1272 01:00:18,260 --> 01:00:20,330 e eu estou indo a crear un arquivo chamado hello.c. 1273 01:00:20,330 --> 01:00:22,849 A maioría desta información que Non vou entrar en en gran detalle, 1274 01:00:22,849 --> 01:00:25,140 pero eu estou indo a escribir un programa nese mesmo idioma, 1275 01:00:25,140 --> 01:00:31,140 C. Isto é moito máis intimidante, Eu diría, que cero, 1276 01:00:31,140 --> 01:00:32,490 pero é moi semellante en espírito. 1277 01:00:32,490 --> 01:00:34,364 En realidade, estes rizado braces-- Pode tipo de 1278 01:00:34,364 --> 01:00:37,820 pensar o que eu fixen como esta. 1279 01:00:37,820 --> 01:00:39,240 >> Imos facelo, en realidade. 1280 01:00:39,240 --> 01:00:45,100 Cando a bandeira verde premendo, faga o seguinte. 1281 01:00:45,100 --> 01:00:50,210 Quero imprimir "Ola". 1282 01:00:50,210 --> 01:00:51,500 Polo tanto, esta é agora pseudocódigo. 1283 01:00:51,500 --> 01:00:53,000 Eu son o tipo de borrar as liñas. 1284 01:00:53,000 --> 01:00:56,750 C, esta lingua que eu estou falando sobre, esta liña de impresión Ola 1285 01:00:56,750 --> 01:01:01,940 convértese en realidade "printf" con algúns parénteses e un punto e coma. 1286 01:01:01,940 --> 01:01:03,480 >> Pero é exactamente a mesma idea. 1287 01:01:03,480 --> 01:01:06,730 E moi amigable "Cando a bandeira verde premendo" convértese en 1288 01:01:06,730 --> 01:01:10,182 o máis arcano "void main int." 1289 01:01:10,182 --> 01:01:12,890 E iso realmente non ten cartografía, entón eu só vou ignorar isto. 1290 01:01:12,890 --> 01:01:17,210 Pero as claves son como o pezas do puzzle curvo como este. 1291 01:01:17,210 --> 01:01:18,700 >> Así, pode tipo de adiviñar. 1292 01:01:18,700 --> 01:01:22,357 Mesmo se nunca programou antes, que é o que este programa probablemente facer? 1293 01:01:22,357 --> 01:01:25,560 1294 01:01:25,560 --> 01:01:28,000 Probablemente imprime Ola cun signo de admiración. 1295 01:01:28,000 --> 01:01:29,150 >> Entón, imos tentar iso. 1296 01:01:29,150 --> 01:01:30,800 Eu estou indo para salvalo. 1297 01:01:30,800 --> 01:01:34,000 E isto é, de novo, unha moi ambiente da vella escola. 1298 01:01:34,000 --> 01:01:35,420 Non podo facer clic, non pode arrastrar. 1299 01:01:35,420 --> 01:01:36,910 Teño que escribir ordes. 1300 01:01:36,910 --> 01:01:41,320 Entón, quero facer o meu programa, de xeito Podería facelo, como hello.c. 1301 01:01:41,320 --> 01:01:42,292 Ese é o ficheiro que eu execute. 1302 01:01:42,292 --> 01:01:43,500 Pero espera, eu estou falta un paso. 1303 01:01:43,500 --> 01:01:46,470 O que dicimos é unha condición necesaria paso a unha linguaxe como C? 1304 01:01:46,470 --> 01:01:49,470 Acaba de fonte escrita código, pero o que eu teño? 1305 01:01:49,470 --> 01:01:50,670 Si, eu teño un compilador. 1306 01:01:50,670 --> 01:01:57,670 Entón, o meu Mac aquí, eu teño un programa chamado GCC, o compilador GNU C, 1307 01:01:57,670 --> 01:02:03,990 o que me permite facer isto-- vez meu código fonte en, imos chamalo, 1308 01:02:03,990 --> 01:02:04,930 código de máquina. 1309 01:02:04,930 --> 01:02:10,180 >> E podo ver que, outra vez, como segue, estes 1310 01:02:10,180 --> 01:02:14,090 son os ceros e uns EU SÓ creado a partir do meu código fonte, 1311 01:02:14,090 --> 01:02:15,730 todo ceros e uns. 1312 01:02:15,730 --> 01:02:17,770 E se eu queira executar meu program-- isto ocorre 1313 01:02:17,770 --> 01:02:23,010 a ser chamado a.out para reasons-- histórico "Ola". 1314 01:02:23,010 --> 01:02:24,070 Podo executa-lo de novo. 1315 01:02:24,070 --> 01:02:25,690 Ola, ola, ola. 1316 01:02:25,690 --> 01:02:27,430 E parece estar funcionando. 1317 01:02:27,430 --> 01:02:31,000 >> Pero iso significa que en algún lugar na miña memoria do ordenador son as palabras 1318 01:02:31,000 --> 01:02:35,279 h-e-l-l o punto de exclamación. 1319 01:02:35,279 --> 01:02:38,070 E verifícase se, como un aparte, o que un ordenador faría normalmente 1320 01:02:38,070 --> 01:02:40,550 facer para que saiba onde as cousas comezan e end-- é 1321 01:02:40,550 --> 01:02:42,460 vai poñer un símbolo especial aquí. 1322 01:02:42,460 --> 01:02:46,064 E o convenio é poñer o número cero ao final dunha palabra 1323 01:02:46,064 --> 01:02:48,230 para que vostede sabe onde realmente remata, de xeito que 1324 01:02:48,230 --> 01:02:52,750 non manter imprimir máis e máis caracteres que realmente pretende. 1325 01:02:52,750 --> 01:02:55,400 >> Pero o takeaway aquí, mesmo aínda que este é moi misterioso, 1326 01:02:55,400 --> 01:02:58,140 é que é, en definitiva relativamente simple. 1327 01:02:58,140 --> 01:03:04,550 Foille dado unha especie de cinta, un espazo en branco espazo onde pode escribir cartas. 1328 01:03:04,550 --> 01:03:07,150 Vostede simplemente ten que ter un símbolo especial, como arbitrariamente 1329 01:03:07,150 --> 01:03:10,316 o número cero, para poñer no extremo da as súas palabras para que o ordenador sabe, 1330 01:03:10,316 --> 01:03:13,410 Oh, eu debería deixar a impresión despois Eu vexo o punto de exclamación. 1331 01:03:13,410 --> 01:03:16,090 Porque a seguinte cousa alí é un valor ASCII de cero, 1332 01:03:16,090 --> 01:03:19,125 ou o carácter nulo como alguén vai chamalo. 1333 01:03:19,125 --> 01:03:21,500 Pero hai un tipo de problema aquí, e imos volver 1334 01:03:21,500 --> 01:03:23,320 a números por un momento. 1335 01:03:23,320 --> 01:03:28,720 Supoña que fago, en realidade, teñen unha serie de números, 1336 01:03:28,720 --> 01:03:30,730 e supor que o programa que eu estou escribindo é 1337 01:03:30,730 --> 01:03:34,680 como un libro de notas para un profesor e unha clase profesores. 1338 01:03:34,680 --> 01:03:38,720 E este programa permite que el ou ela para escribir as notas dos seus alumnos 1339 01:03:38,720 --> 01:03:39,960 en cuestionarios. 1340 01:03:39,960 --> 01:03:43,750 E supoña que o alumno recibe 100 no seu primeiro exame, quizais 1341 01:03:43,750 --> 01:03:49,920 como un 80 o próximo, a continuación, un 75, a continuación, un 90 no cuarto quiz. 1342 01:03:49,920 --> 01:03:54,150 >> Polo tanto, neste punto da historia, a matriz é de tamaño catro. 1343 01:03:54,150 --> 01:03:58,470 Non hai absolutamente máis memoria na ordenador, pero a matriz, por así dicir, 1344 01:03:58,470 --> 01:04:00,350 é de tamaño catro. 1345 01:04:00,350 --> 01:04:06,060 Supoñamos agora que o profesor quere para asignar un quinto exame para a clase. 1346 01:04:06,060 --> 01:04:08,510 Ben, unha das cousas que ou vai ter que facer 1347 01:04:08,510 --> 01:04:10,650 agora almacenar un valor adicional aquí. 1348 01:04:10,650 --> 01:04:15,490 Pero se a matriz o profesor ten creado neste programa é de tamaño para, 1349 01:04:15,490 --> 01:04:22,440 un dos problemas con que é unha matriz non pode simplemente seguir engadir a memoria. 1350 01:04:22,440 --> 01:04:26,470 Porque o que se outra parte do programa ten a palabra "hey" alí? 1351 01:04:26,470 --> 01:04:29,650 >> Noutras palabras, a memoria pode ser usado para calquera cousa nun programa. 1352 01:04:29,650 --> 01:04:33,250 E se antes eu escriba, hey, Quero entrada catro puntuacións do cuestionario, 1353 01:04:33,250 --> 01:04:34,784 poden ir aquí e aquí. 1354 01:04:34,784 --> 01:04:37,700 E se de súpeto cambiar a súa mente máis tarde e dicir que quero un quinto proba 1355 01:04:37,700 --> 01:04:40,872 puntuación, non pode simplemente poñelas onde quere, 1356 01:04:40,872 --> 01:04:42,580 porque o que se esta memoria está a ser usada 1357 01:04:42,580 --> 01:04:45,990 para algo else-- algún outro programa ou algunha outra característica do programa 1358 01:04:45,990 --> 01:04:46,910 que está correndo? 1359 01:04:46,910 --> 01:04:50,650 Entón tes que pensar con antelación como quere almacenar os seus datos, 1360 01:04:50,650 --> 01:04:54,480 porque agora pintou só nun recuncho dixital. 1361 01:04:54,480 --> 01:04:57,280 >> Así, un profesor pode, en vez dicir cando se escribe un programa 1362 01:04:57,280 --> 01:04:59,360 para almacenar o seu notas, vostede sabe o que? 1363 01:04:59,360 --> 01:05:04,180 Vou pedir, ao escribir o meu programa, 1364 01:05:04,180 --> 01:05:12,070 que quero cero, un, dous, tres, catro, cinco, seis, oito graos en total. 1365 01:05:12,070 --> 01:05:15,320 Entón, un, dous, tres, catro, cinco, seis, sete, oito. 1366 01:05:15,320 --> 01:05:18,612 O profesor pode só sobre-reservar memoria ao escribir o seu programa 1367 01:05:18,612 --> 01:05:19,570 e dicir, vostede sabe o que? 1368 01:05:19,570 --> 01:05:22,236 Eu nunca vou asignar máis de oito probas nun semestre. 1369 01:05:22,236 --> 01:05:23,130 Isto é unha tolemia. 1370 01:05:23,130 --> 01:05:24,470 Eu nunca vou asignar iso. 1371 01:05:24,470 --> 01:05:28,270 Así que esta forma que el ou ela ten a flexibilidade para puntuacións tenda de estudante, 1372 01:05:28,270 --> 01:05:33,010 como 75, 90, e quizais un extra, onde o alumno ten crédito extra, 105. 1373 01:05:33,010 --> 01:05:36,130 >> Pero se o profesor non utiliza estes tres espazos, 1374 01:05:36,130 --> 01:05:38,860 hai un takeaway intuitiva aquí. 1375 01:05:38,860 --> 01:05:41,410 El ou ela é só desperdicio de espazo. 1376 01:05:41,410 --> 01:05:44,790 Polo tanto, noutras palabras, non é iso tradeoff común na programación 1377 01:05:44,790 --> 01:05:48,241 onde podes reservar exactamente tanta memoria como quere, 1378 01:05:48,241 --> 01:05:51,490 a cabeza do que é o que está super efficient-- non está a ser a pérdida 1379 01:05:51,490 --> 01:05:54,640 en todos-- pero a desvantaxe dos cales é o que se cambiar a súa mente cando 1380 01:05:54,640 --> 01:05:58,780 usando o programa que quere gardar máis datos do que inicialmente previsto. 1381 01:05:58,780 --> 01:06:03,030 >> Entón, se cadra a solución é, entón, escribir os seus programas de tal forma 1382 01:06:03,030 --> 01:06:05,605 que empregan máis memoria do que realmente precisan. 1383 01:06:05,605 --> 01:06:07,730 Desta forma, non vai a executar para este problema, 1384 01:06:07,730 --> 01:06:09,730 pero está a ser un desperdicio. 1385 01:06:09,730 --> 01:06:12,960 E o máis memoria o programa usa, como discutir onte, a menos 1386 01:06:12,960 --> 01:06:15,410 memoria que está dispoñible para outros programas, 1387 01:06:15,410 --> 01:06:18,790 canto máis cedo o seu ordenador pode retardar abaixo por mor da memoria virtual. 1388 01:06:18,790 --> 01:06:22,670 E así a solución ideal pode ser o que? 1389 01:06:22,670 --> 01:06:24,610 >> Sub-reparte parece malo. 1390 01:06:24,610 --> 01:06:27,030 Over-reparte parece malo. 1391 01:06:27,030 --> 01:06:31,120 Entón, o que pode ser unha solución mellor? 1392 01:06:31,120 --> 01:06:32,390 A deslocalización. 1393 01:06:32,390 --> 01:06:33,590 Sexa máis dinámico. 1394 01:06:33,590 --> 01:06:37,520 Non force a escoller un priori, en principio, o que quere. 1395 01:06:37,520 --> 01:06:41,370 E, por suposto, non o exceso de reservar, para que non ser un desperdicio. 1396 01:06:41,370 --> 01:06:45,770 >> E así, para acadar este obxectivo, que xogar esta estrutura de datos, 1397 01:06:45,770 --> 01:06:48,100 por así dicir, lonxe. 1398 01:06:48,100 --> 01:06:51,080 E entón o que un programador tipicamente utilizará 1399 01:06:51,080 --> 01:06:55,940 é algo que non é unha chamada matriz, pero unha lista ligada. 1400 01:06:55,940 --> 01:07:00,860 Noutras palabras, el ou ela vai comezar a pensar na súa memoria 1401 01:07:00,860 --> 01:07:05,280 como un tipo de forma que eles pode aproveitar do seguinte xeito. 1402 01:07:05,280 --> 01:07:08,520 Se eu queira gardar un número na un program-- polo que é de setembro de 1403 01:07:08,520 --> 01:07:12,600 Eu dei os meus alumnos un cuestionario; quero para almacenar primeira proba dos alumnos, 1404 01:07:12,600 --> 01:07:16,220 e ten un 100 sobre ele-- I vou pedir o meu ordenador, 1405 01:07:16,220 --> 01:07:19,540 por medio do programa que eu teño escrito, por un anaco de memoria. 1406 01:07:19,540 --> 01:07:22,570 E eu estou indo para almacenar o número 100, e é iso. 1407 01:07:22,570 --> 01:07:24,820 >> Logo unhas semanas máis tarde cando chegar no meu segundo cuestionario, 1408 01:07:24,820 --> 01:07:27,890 e é o momento de escribir en que o 90%, eu vou 1409 01:07:27,890 --> 01:07:32,129 para pedir o ordenador, hey, ordenador, Podo ter outro anaco de memoria? 1410 01:07:32,129 --> 01:07:34,170 Me vai dar a este anaco branco de memoria. 1411 01:07:34,170 --> 01:07:39,370 Vou poñer o número 90, pero no meu programa de algunha maneira ou outro-- 1412 01:07:39,370 --> 01:07:42,100 e nós non vai preocuparse a sintaxe para isto-- necesito 1413 01:07:42,100 --> 01:07:44,430 dalgún xeito encadear esas cousas xuntas. 1414 01:07:44,430 --> 01:07:47,430 E eu vou acorrentá los xunto coa o que parece ser unha frecha aquí. 1415 01:07:47,430 --> 01:07:50,050 >> O terceiro cuestionario que xorde, Eu vou dicir, hey, ordenador, 1416 01:07:50,050 --> 01:07:51,680 darme outro anaco de memoria. 1417 01:07:51,680 --> 01:07:54,660 E eu vou tirar abaixo que quere que fose, como 75, 1418 01:07:54,660 --> 01:07:56,920 e teño de cadea presente xuntos agora dalgún xeito. 1419 01:07:56,920 --> 01:08:00,290 Cuarta cuestionario ven xunto, e quizais isto é para o final do semestre. 1420 01:08:00,290 --> 01:08:03,140 E por ese punto o meu programa pode estar usando memoria 1421 01:08:03,140 --> 01:08:05,540 en todo o lugar, en todo fisicamente. 1422 01:08:05,540 --> 01:08:08,170 E así, só por diversión, eu son vai sacar esa luz 1423 01:08:08,170 --> 01:08:11,260 quiz-- esquezo o que era; eu creo que quizais un 80 ou algo-- 1424 01:08:11,260 --> 01:08:12,500 camiño ata aquí. 1425 01:08:12,500 --> 01:08:15,920 >> Pero iso é bo, porque pictoricamente Eu estou indo a deseñar esta liña. 1426 01:08:15,920 --> 01:08:19,063 Noutras palabras, en realidade, no hardware do seu ordenador, 1427 01:08:19,063 --> 01:08:20,979 a primeira puntuación pode acabar aquí, porque é 1428 01:08:20,979 --> 01:08:22,529 Ao comezo do semestre. 1429 01:08:22,529 --> 01:08:25,810 O seguinte pode acabar aquí porque un pouco de tempo xa pasou 1430 01:08:25,810 --> 01:08:27,210 eo programa segue funcionando. 1431 01:08:27,210 --> 01:08:30,060 A seguinte puntuación, que foi a 75, pode ser por aquí. 1432 01:08:30,060 --> 01:08:33,420 E a última puntuación pode ser un 80, que é por aquí. 1433 01:08:33,420 --> 01:08:38,729 >> Entón, en realidade, fisicamente, que pode ser o que a memoria do seu ordenador parece. 1434 01:08:38,729 --> 01:08:41,569 Pero este non é un mentais útil paradigma para un programador informático. 1435 01:08:41,569 --> 01:08:44,649 Por que ten que se preocupar onde a Parreira seus datos están rematando? 1436 01:08:44,649 --> 01:08:46,200 Só quere almacenar datos. 1437 01:08:46,200 --> 01:08:49,390 >> Este é tipo de como a nosa discusión antes de deseñar o cubo. 1438 01:08:49,390 --> 01:08:52,200 Por que lle importa o que é o ángulo do cubo 1439 01:08:52,200 --> 01:08:53,740 e como ten que volver para deseña-lo? 1440 01:08:53,740 --> 01:08:54,950 Só quere un cubo. 1441 01:08:54,950 --> 01:08:57,359 Do mesmo xeito aquí, só quero libro de notas. 1442 01:08:57,359 --> 01:08:59,559 Só quere pensar isto como unha lista de números. 1443 01:08:59,559 --> 01:09:01,350 Quen lle importa como é aplicadas en hardware? 1444 01:09:01,350 --> 01:09:05,180 >> Así, a abstracción agora É esta foto aquí. 1445 01:09:05,180 --> 01:09:07,580 Esta é unha lista ligada, como programador estaba chamalo, 1446 01:09:07,580 --> 01:09:10,640 na medida en que ten un lista, obviamente, de números. 1447 01:09:10,640 --> 01:09:14,990 Pero está ligada pictoricamente por medio destas frechas, 1448 01:09:14,990 --> 01:09:18,510 e todas estas frechas é-- debaixo o capó, se está curioso, 1449 01:09:18,510 --> 01:09:23,210 Recordamos que o noso hardware físico ten enderezos cero, un, dous, tres, catro. 1450 01:09:23,210 --> 01:09:28,465 Todas estas frechas son é como un mapa ou instrucións, onde se 90 é-- agora 1451 01:09:28,465 --> 01:09:29,090 Teño que contar. 1452 01:09:29,090 --> 01:09:31,750 >> Cero, un, dous, tres, catro, cinco, seis, sete. 1453 01:09:31,750 --> 01:09:35,640 Parece que o 90 é o memoria do número de enderezo de sete. 1454 01:09:35,640 --> 01:09:38,460 Todas estas frechas son é como un pequeno anaco de papel 1455 01:09:38,460 --> 01:09:42,439 que está dando instrucións ao programa que di que siga este mapa 1456 01:09:42,439 --> 01:09:43,880 para chegar ao lugar de sete. 1457 01:09:43,880 --> 01:09:46,680 E alí vai atopar o segunda puntuación do cuestionario do estudante. 1458 01:09:46,680 --> 01:09:52,100 Mentres tanto, o 75-- si continuar con este, este é sete, oito, nove, 10, 11, 12, 1459 01:09:52,100 --> 01:09:54,240 13, 14, 15. 1460 01:09:54,240 --> 01:09:59,080 >> Estoutra frecha representa só nun mapa para localización de memoria 15. 1461 01:09:59,080 --> 01:10:02,550 Pero, de novo, o programador xeralmente fai non se preocupan este nivel de detalle. 1462 01:10:02,550 --> 01:10:05,530 E na maioría cada programación linguaxe de hoxe, o programador 1463 01:10:05,530 --> 01:10:10,490 nin vai saber onde na memoria estas cifras realmente son. 1464 01:10:10,490 --> 01:10:14,830 Todo o que el ou ela ten que se preocupan o que son de algunha maneira ligado xuntos 1465 01:10:14,830 --> 01:10:18,390 nunha estrutura de datos como este. 1466 01:10:18,390 --> 01:10:21,580 >> Pero resulta que non ser moi técnico. 1467 01:10:21,580 --> 01:10:27,430 Pero só porque podemos quizais dar o luxo de ter esta conversa aquí, 1468 01:10:27,430 --> 01:10:33,630 supoña que revisitar esta cuestión aquí dunha matriz. 1469 01:10:33,630 --> 01:10:35,780 Imos ver se nós lamentamos indo para alí. 1470 01:10:35,780 --> 01:10:42,950 Esta é de 100, 90, 75, e 80. 1471 01:10:42,950 --> 01:10:44,980 >> Deixe-me facer brevemente esta reivindicación. 1472 01:10:44,980 --> 01:10:48,980 Esta é unha matriz, e de novo, o característica destacada dunha matriz 1473 01:10:48,980 --> 01:10:52,400 é que os seus datos está de volta ao de volta para atrás en memory-- literalmente 1474 01:10:52,400 --> 01:10:56,830 Un byte ou quizais catro bytes, un número fixo de bytes de distancia. 1475 01:10:56,830 --> 01:11:00,710 Nunha lista ligada, o que poderiamos chamar así, debaixo do capó que 1476 01:11:00,710 --> 01:11:02,000 sabe onde o material é? 1477 01:11:02,000 --> 01:11:03,630 El nin sequera teñen que fluír como este. 1478 01:11:03,630 --> 01:11:06,050 Algúns dos datos pode ser de volta á esquerda ata alí. 1479 01:11:06,050 --> 01:11:07,530 Vostede nin sequera sabe. 1480 01:11:07,530 --> 01:11:15,430 >> E así, cunha matriz, ten un recurso coñecido como acceso aleatorio. 1481 01:11:15,430 --> 01:11:20,570 E o que os medios de acceso aleatorio é que o ordenador pode ir instantáneamente 1482 01:11:20,570 --> 01:11:22,730 para calquera lugar nunha matriz. 1483 01:11:22,730 --> 01:11:23,580 Por que? 1484 01:11:23,580 --> 01:11:26,000 Porque o equipo sabe que é o primeiro localización 1485 01:11:26,000 --> 01:11:29,540 cero, un, dous e tres. 1486 01:11:29,540 --> 01:11:33,890 >> E entón se quere ir de este elemento para o elemento seguinte, 1487 01:11:33,890 --> 01:11:36,099 vostede literalmente, na A mente de ordenador, só tes que engadir un. 1488 01:11:36,099 --> 01:11:39,140 Se quere ir ao terceiro elemento, basta engadir um-- seguinte elemento, só 1489 01:11:39,140 --> 01:11:40,290 engadir un. 1490 01:11:40,290 --> 01:11:42,980 Con todo, nesta versión da historia, supoña 1491 01:11:42,980 --> 01:11:46,080 o ordenador está a visitar ou en manexar o número 100. 1492 01:11:46,080 --> 01:11:49,770 Como chegar ao seguinte grao no libro de notas? 1493 01:11:49,770 --> 01:11:52,560 >> Ten que tomar sete etapas, que é arbitraria. 1494 01:11:52,560 --> 01:11:58,120 Para chegar ao seguinte, ten que levar oito pasos para chegar a 15. 1495 01:11:58,120 --> 01:12:02,250 Noutras palabras, non é un lagoa constante entre os números, 1496 01:12:02,250 --> 01:12:04,857 e por iso só leva o ordenador máis tempo é o punto. 1497 01:12:04,857 --> 01:12:06,940 O ordenador debe buscar a través da memoria, a fin 1498 01:12:06,940 --> 01:12:08,990 para atopar o que está a procurar. 1499 01:12:08,990 --> 01:12:14,260 >> Así, mentres que unha matriz tende a ser un structure-- rápida de datos porque 1500 01:12:14,260 --> 01:12:17,610 Pode literalmente só facer aritmética simple e chegar onde quere pola adición dun, 1501 01:12:17,610 --> 01:12:21,300 para instance-- unha lista ligada, vostede sacrifica este recurso. 1502 01:12:21,300 --> 01:12:24,020 Non pode simplemente ir de primeira para a segunda a terceira para a cuarta. 1503 01:12:24,020 --> 01:12:25,240 Ten que seguir o mapa. 1504 01:12:25,240 --> 01:12:28,160 Ten que tomar máis medidas para chegar a eses valores, que 1505 01:12:28,160 --> 01:12:30,230 parece ser a adición dun custo. 1506 01:12:30,230 --> 01:12:35,910 Entón, nós estamos pagando un prezo, pero o que era o recurso que Dan busca aquí? 1507 01:12:35,910 --> 01:12:38,110 O que fai unha lista ligada parecer nos permiten facer, 1508 01:12:38,110 --> 01:12:40,240 cal foi a orixe da esta historia en particular? 1509 01:12:40,240 --> 01:12:43,250 1510 01:12:43,250 --> 01:12:43,830 >> Exactamente. 1511 01:12:43,830 --> 01:12:46,220 Un tamaño dinámico para iso. 1512 01:12:46,220 --> 01:12:48,040 Podemos engadir a esta lista. 1513 01:12:48,040 --> 01:12:51,430 Podemos incluso máis a, para que só está a usar o máximo de memoria 1514 01:12:51,430 --> 01:12:55,560 como queremos realmente e así estamos nunca over-reparte. 1515 01:12:55,560 --> 01:12:58,470 >> Agora é só para ser realmente nit-esixente, hai un custo oculto. 1516 01:12:58,470 --> 01:13:01,980 Entón non debe deixarme convencer que este é un compromiso convincente. 1517 01:13:01,980 --> 01:13:04,190 Hai outro custo oculto aquí. 1518 01:13:04,190 --> 01:13:06,550 O beneficio, para ser claro, é que comezamos dinamismo. 1519 01:13:06,550 --> 01:13:10,359 Se eu queira outro elemento, só pode deseña-lo e poñer un número alí. 1520 01:13:10,359 --> 01:13:12,150 E entón eu podo ligala cunha imaxe aquí, 1521 01:13:12,150 --> 01:13:14,970 mentres aquí, de novo, se eu teño pintou-me en un canto, 1522 01:13:14,970 --> 01:13:19,410 se algo xa está a usar a memoria aquí, estou fóra da sorte. 1523 01:13:19,410 --> 01:13:21,700 Pintei-me para o canto. 1524 01:13:21,700 --> 01:13:24,390 >> Pero o que é o oculto custa nesta foto? 1525 01:13:24,390 --> 01:13:27,690 Non é só a cantidade de tempo que leva 1526 01:13:27,690 --> 01:13:29,870 para ir de aquí ata aquí, que é de sete pasos, logo 1527 01:13:29,870 --> 01:13:32,820 oito etapas, que é máis que un. 1528 01:13:32,820 --> 01:13:34,830 Que é outro custo oculto? 1529 01:13:34,830 --> 01:13:35,440 Non só tempo. 1530 01:13:35,440 --> 01:13:44,790 1531 01:13:44,790 --> 01:13:49,940 Información adicional están necesario para lograr este cadro. 1532 01:13:49,940 --> 01:13:53,210 >> Si, ese mapa, eses pequenos anacos de papel, como eu manter describindo os como. 1533 01:13:53,210 --> 01:13:55,650 Estes arrows-- aqueles que non son libres. 1534 01:13:55,650 --> 01:13:57,660 A Computador-- sabe o que un ordenador ten. 1535 01:13:57,660 --> 01:13:58,790 Ten ceros e uns. 1536 01:13:58,790 --> 01:14:03,170 Se desexa representar unha frecha ou un mapear ou un número, precisas algunha memoria. 1537 01:14:03,170 --> 01:14:05,950 Entón, o outro prezo que pagar por unha lista ligada, 1538 01:14:05,950 --> 01:14:09,070 a ciencia da computación común de recursos, é tamén espazo. 1539 01:14:09,070 --> 01:14:11,710 >> E de feito así, tan comunmente, Entre as compensacións 1540 01:14:11,710 --> 01:14:15,580 no deseño de enxeñaría de software sistemas é o tempo e espaço-- 1541 01:14:15,580 --> 01:14:18,596 son dous dos seus ingredientes, dous dos seus ingredientes máis caros. 1542 01:14:18,596 --> 01:14:21,220 Isto me custando máis tempo porque eu teño que siga este mapa, 1543 01:14:21,220 --> 01:14:25,730 pero tamén me custa máis espazo porque eu teño que manter este mapa arredor. 1544 01:14:25,730 --> 01:14:28,730 Así, a esperanza, como nós tipo de discutido sobre onte e hoxe, 1545 01:14:28,730 --> 01:14:31,720 é que os beneficios ha superan os custos. 1546 01:14:31,720 --> 01:14:33,870 >> Pero non hai ningunha solución obvia aquí. 1547 01:14:33,870 --> 01:14:35,870 Quizais sexa melhor-- a la rápida e sucia, 1548 01:14:35,870 --> 01:14:38,660 como Kareem proposta earlier-- para xogar memoria ao problema. 1549 01:14:38,660 --> 01:14:42,520 Só ten que mercar máis memoria, pensar menos duro sobre como resolver o problema, 1550 01:14:42,520 --> 01:14:44,595 e resolver-lo dun xeito máis sinxelo. 1551 01:14:44,595 --> 01:14:46,720 E, de feito antes, cando falamos compensacións, 1552 01:14:46,720 --> 01:14:49,190 non había espazo o ordenador e tempo. 1553 01:14:49,190 --> 01:14:51,810 Era hora creador, que é aínda outro recurso. 1554 01:14:51,810 --> 01:14:54,829 >> Entón, de novo, é este acto de equilibrio tentando decidir cal destas cousas 1555 01:14:54,829 --> 01:14:55,870 está disposto a gastar? 1556 01:14:55,870 --> 01:14:57,380 Cal é o menos caro? 1557 01:14:57,380 --> 01:15:01,040 Que produce os mellores resultados? 1558 01:15:01,040 --> 01:15:01,540 Si? 1559 01:15:01,540 --> 01:15:11,310 1560 01:15:11,310 --> 01:15:12,580 >> Por suposto. 1561 01:15:12,580 --> 01:15:15,970 Neste caso, se está representando números na maps-- 1562 01:15:15,970 --> 01:15:18,820 estes son chamados en moitas linguas "Ponteiros" ou "enderezos" - 1563 01:15:18,820 --> 01:15:20,390 que é o dobre do espazo. 1564 01:15:20,390 --> 01:15:24,390 Isto non debe ser tan malo como o dobre se agora estamos só almacenar números. 1565 01:15:24,390 --> 01:15:27,410 Supoña que estaban almacenando rexistros de pacientes nun hospital-- 1566 01:15:27,410 --> 01:15:30,870 así nomes de Pierson, números de teléfono, números de seguridade social, médico 1567 01:15:30,870 --> 01:15:31,540 historia. 1568 01:15:31,540 --> 01:15:34,160 Esta caixa pode ser moi, moito maior, en cuxo caso 1569 01:15:34,160 --> 01:15:38,000 algo punteiro minúsculo, a dirección do a seguinte element-- non é un gran negocio. 1570 01:15:38,000 --> 01:15:40,620 É un tal franxa custo, non importa. 1571 01:15:40,620 --> 01:15:43,210 Pero neste caso, si, é unha duplicación. 1572 01:15:43,210 --> 01:15:45,290 Boa pregunta. 1573 01:15:45,290 --> 01:15:47,900 >> Imos falar sobre o tempo que un pouco máis concretamente. 1574 01:15:47,900 --> 01:15:50,380 Cal é o tempo de execución de buscar esta lista? 1575 01:15:50,380 --> 01:15:53,640 Supoña que quería para buscar a través de todas as notas dos alumnos, 1576 01:15:53,640 --> 01:15:55,980 e hai n graos nesta estrutura de datos. 1577 01:15:55,980 --> 01:15:58,830 Aquí, tamén, podemos tomar prestado o vocabulario da anterior. 1578 01:15:58,830 --> 01:16:00,890 Esta é unha estrutura de datos lineal. 1579 01:16:00,890 --> 01:16:04,570 >> Big O de n é o que é necesario para obter ao final da presente estrutura de datos, 1580 01:16:04,570 --> 01:16:08,410 whereas-- e non vimos este antes-- unha matriz dálle 1581 01:16:08,410 --> 01:16:13,555 o que se chama de tempo constante, o que significa un paso ou dous pasos ou 10 steps-- 1582 01:16:13,555 --> 01:16:14,180 non importa. 1583 01:16:14,180 --> 01:16:15,440 É un número fixo. 1584 01:16:15,440 --> 01:16:17,440 Non ten nada que ver con o tamaño da matriz. 1585 01:16:17,440 --> 01:16:20,130 E a razón para iso, unha vez máis, é de acceso aleatorio. 1586 01:16:20,130 --> 01:16:23,180 O ordenador pode só inmediatamente ir a outro lugar, 1587 01:16:23,180 --> 01:16:27,770 porque son todos iguais distancia de todo o resto. 1588 01:16:27,770 --> 01:16:29,112 Non hai ningún pensamento parte. 1589 01:16:29,112 --> 01:16:31,900 1590 01:16:31,900 --> 01:16:32,400 Todo ben. 1591 01:16:32,400 --> 01:16:39,230 Entón, se eu puidera, déixeme probar pintar dous cadros finais. 1592 01:16:39,230 --> 01:16:42,830 Un moi común coñecida como unha táboa hash. 1593 01:16:42,830 --> 01:16:51,120 Entón, para motivar a discusión, déixeme pensar sobre como facelo. 1594 01:16:51,120 --> 01:16:52,610 >> Así como sobre iso? 1595 01:16:52,610 --> 01:16:55,160 Supóñase que o problema queremos resolver agora 1596 01:16:55,160 --> 01:16:58,360 está a aplicar nun dictionary-- polo que unha morea de palabras en inglés 1597 01:16:58,360 --> 01:16:59,330 ou o que quere. 1598 01:16:59,330 --> 01:17:02,724 E o obxectivo é o de poder responder preguntas do formulario esta é unha palabra? 1599 01:17:02,724 --> 01:17:04,640 Entón quere aplicar un corrector ortográfico, só 1600 01:17:04,640 --> 01:17:07,220 como un dicionario física que podes ollar as cousas en. 1601 01:17:07,220 --> 01:17:10,490 Supoña que eu fose facelo con unha matriz. 1602 01:17:10,490 --> 01:17:12,590 Podería facelo. 1603 01:17:12,590 --> 01:17:20,756 >> E supoñer que as palabras son de mazá e bananas e melón. 1604 01:17:20,756 --> 01:17:23,330 1605 01:17:23,330 --> 01:17:26,465 E eu non podo pensar de froitas que comezan con D, entón estamos só 1606 01:17:26,465 --> 01:17:27,590 terá tres froitas. 1607 01:17:27,590 --> 01:17:31,510 Polo tanto, este é un array, e estamos almacenar todas estas palabras 1608 01:17:31,510 --> 01:17:34,200 neste dicionario como unha matriz. 1609 01:17:34,200 --> 01:17:39,350 A cuestión, entón, é que outra forma pode almacenar esta información? 1610 01:17:39,350 --> 01:17:43,160 >> Ben, eu son o tipo de trampas aquí, porque cada unha destas letras da palabra 1611 01:17:43,160 --> 01:17:44,490 é realmente un byte individual. 1612 01:17:44,490 --> 01:17:46,740 Entón, se eu realmente quería ser nit-esixente, realmente debería 1613 01:17:46,740 --> 01:17:49,600 ser dividindo este en moi pequenos anacos de memoria, 1614 01:17:49,600 --> 01:17:51,289 e poderiamos facer exactamente isto. 1615 01:17:51,289 --> 01:17:53,580 Pero nós estamos indo funcionar o mesmo problema que antes. 1616 01:17:53,580 --> 01:17:56,674 E se, como Merriam Webster ou Oxford fai cada ano-- que engadir palabras 1617 01:17:56,674 --> 01:17:59,340 ao dictionary-- non necesariamente quere nos pintar 1618 01:17:59,340 --> 01:18:00,780 nunha esquina cunha matriz? 1619 01:18:00,780 --> 01:18:05,710 >> Entón, en vez, se cadra unha visión máis intelixente é poñer a mazá no seu propio nó ou caixa, 1620 01:18:05,710 --> 01:18:11,190 como diriamos, banana, e entón aquí temos melón. 1621 01:18:11,190 --> 01:18:14,990 1622 01:18:14,990 --> 01:18:16,790 E corda que estas cousas xuntas. 1623 01:18:16,790 --> 01:18:19,980 Polo tanto, esta é a matriz, e esta é a lista ligada. 1624 01:18:19,980 --> 01:18:23,300 Se non pode ver, só di "matriz", e iso di "lista". 1625 01:18:23,300 --> 01:18:25,780 >> Polo tanto, temos o mesmo cuestións exactas como antes, 1626 01:18:25,780 --> 01:18:28,600 polo cal agora temos dinamismo na nosa lista ligada. 1627 01:18:28,600 --> 01:18:31,090 Pero temos un dicionario moi lento. 1628 01:18:31,090 --> 01:18:32,870 Supoña que queira procurar unha palabra. 1629 01:18:32,870 --> 01:18:35,430 Me pode levar gran O de n pasos, porque a palabra pode 1630 01:18:35,430 --> 01:18:37,840 ser todo o camiño a finais de a lista, como melón. 1631 01:18:37,840 --> 01:18:40,600 E verifícase que na programación, sort 1632 01:18:40,600 --> 01:18:42,700 do Santo Graal dos datos estruturas, é algo 1633 01:18:42,700 --> 01:18:46,620 que lle dá constante tempo como unha matriz 1634 01:18:46,620 --> 01:18:50,870 pero que aínda lle dá dinamismo. 1635 01:18:50,870 --> 01:18:52,940 >> Así, podemos ter o mellor dos dous mundos? 1636 01:18:52,940 --> 01:18:55,570 E, de feito, hai algo chamada táboa hash 1637 01:18:55,570 --> 01:18:59,320 que permite que fai exactamente que, aínda que aproximadamente. 1638 01:18:59,320 --> 01:19:03,140 Unha táboa é un columbófilo estrutura de datos que nós 1639 01:19:03,140 --> 01:19:06,340 pode pensar en como a combinación dun array-- 1640 01:19:06,340 --> 01:19:12,390 e eu vou deseña-lo como isto-- e listas ligadas 1641 01:19:12,390 --> 01:19:17,310 que eu vou deseñar como este aquí. 1642 01:19:17,310 --> 01:19:19,760 >> E a forma como esa cousa obras é como segue. 1643 01:19:19,760 --> 01:19:23,310 1644 01:19:23,310 --> 01:19:29,540 Se este agora-- de hash mesa-- é a miña estrutura de datos de terceira, 1645 01:19:29,540 --> 01:19:32,590 e quero gardar palabras neste, eu non fago 1646 01:19:32,590 --> 01:19:35,440 quero só almacenar todas as palabras de volta para atrás a volta atrás. 1647 01:19:35,440 --> 01:19:37,430 Quero aproveitar algunhas peza de información 1648 01:19:37,430 --> 01:19:40,330 sobre as palabras que lle permitirán me obtelo onde é máis rápido. 1649 01:19:40,330 --> 01:19:43,666 >> Así, dada a mazá palabras e bananas e melón, 1650 01:19:43,666 --> 01:19:45,040 Eu deliberadamente elixiu estas palabras. 1651 01:19:45,040 --> 01:19:45,340 Por que? 1652 01:19:45,340 --> 01:19:47,631 O que é unha especie de fundamentalmente diferente sobre os tres? 1653 01:19:47,631 --> 01:19:49,950 1654 01:19:49,950 --> 01:19:51,484 Cal é o evidente? 1655 01:19:51,484 --> 01:19:52,900 Comezan con letras distintas. 1656 01:19:52,900 --> 01:19:53,900 >> Entón vostede sabe o que? 1657 01:19:53,900 --> 01:19:57,120 No canto de poñer todas as miñas palabras mesmo balde, por así dicir, 1658 01:19:57,120 --> 01:20:00,390 como nunha lista grande, por que non facer Eu, polo menos, tentar unha optimización 1659 01:20:00,390 --> 01:20:04,180 e facer as miñas listas de 1/26 do tempo. 1660 01:20:04,180 --> 01:20:07,440 A optimización convincente Pode ser por que non facer 1661 01:20:07,440 --> 01:20:10,650 Eu-- ao inserir unha palabra para esa estrutura de datos, 1662 01:20:10,650 --> 01:20:14,300 na memoria do ordenador, por iso Non coloque todas as palabras "o" aquí, 1663 01:20:14,300 --> 01:20:17,270 todo 'B' palabras aquí, e todos os "c" palabras aquí? 1664 01:20:17,270 --> 01:20:24,610 Entón iso acaba poñendo unha mazá aquí, banana aquí, melón aquí, 1665 01:20:24,610 --> 01:20:25,730 e así por diante. 1666 01:20:25,730 --> 01:20:31,700 >> E se eu tivera un adicional palabra como-- o que é outro? 1667 01:20:31,700 --> 01:20:36,640 Mazá, plátano, pera. 1668 01:20:36,640 --> 01:20:39,370 Calquera pensa dunha froita que comeza con a, b, c? 1669 01:20:39,370 --> 01:20:40,570 perfecta Blueberry--. 1670 01:20:40,570 --> 01:20:43,990 Isto vai acabar aquí. 1671 01:20:43,990 --> 01:20:47,530 E así parece que temos un marxinalidade mellor solución, 1672 01:20:47,530 --> 01:20:50,820 porque agora se eu queira para buscar mazá, I 1673 01:20:50,820 --> 01:20:53,200 first-- Non só mergullo na miña estrutura de datos. 1674 01:20:53,200 --> 01:20:54,850 Non mergullo na memoria do meu ordenador. 1675 01:20:54,850 --> 01:20:56,530 I primeiro ollar para a primeira letra. 1676 01:20:56,530 --> 01:20:58,610 >> E iso é o que un ordenador científico diría. 1677 01:20:58,610 --> 01:21:00,760 Vostede botar na súa estrutura de datos. 1678 01:21:00,760 --> 01:21:04,100 Toma a súa entrada, o que, neste caso, é unha palabra como mazá. 1679 01:21:04,100 --> 01:21:07,150 Vostede analiza-lo, buscando a primeira letra neste caso 1680 01:21:07,150 --> 01:21:08,340 hashing-o así. 1681 01:21:08,340 --> 01:21:10,950 Hashing é un termo xeral que toma algo como entrada 1682 01:21:10,950 --> 01:21:12,116 e producir algunha saída. 1683 01:21:12,116 --> 01:21:15,090 E a saída na que caso é a localización 1684 01:21:15,090 --> 01:21:18,150 quere investigar, o primeiro local, segundo lugar, a terceira. 1685 01:21:18,150 --> 01:21:22,160 Así, a entrada é de mazá, a saída é en primeiro lugar. 1686 01:21:22,160 --> 01:21:25,054 A entrada é de bananas, o saída debe ser segundo. 1687 01:21:25,054 --> 01:21:27,220 A entrada é melón, a saída debe ser o terceiro. 1688 01:21:27,220 --> 01:21:30,320 A entrada é de Arandeira, o saída debe volver a ser segundo. 1689 01:21:30,320 --> 01:21:34,010 E iso é o que axuda a sacar atallos a través da súa memoria 1690 01:21:34,010 --> 01:21:39,050 a fin de obter a palabras ou datos de forma máis eficaz. 1691 01:21:39,050 --> 01:21:43,330 >> Agora, iso reduce noso tempo potencialmente xa que logo como un de 26, 1692 01:21:43,330 --> 01:21:45,850 porque se asumir que ter tantos "a" palabras como "z" 1693 01:21:45,850 --> 01:21:48,080 palabras como palabras "q", que non é realmente realistic-- 1694 01:21:48,080 --> 01:21:50,830 terá a inclinación do outro lado certas letras do alphabet-- 1695 01:21:50,830 --> 01:21:53,204 pero iso sería un incremental visión que non permite 1696 01:21:53,204 --> 01:21:55,930 Lo a obter a palabras moito máis rápido. 1697 01:21:55,930 --> 01:21:59,660 E, en realidade, un sofisticado programa, os Googles do mundo, 1698 01:21:59,660 --> 01:22:02,180 o Facebooks do mundo-- eles usarían unha táboa hash 1699 01:22:02,180 --> 01:22:03,740 para unha serie de fins distintos. 1700 01:22:03,740 --> 01:22:06,590 Pero non sería tan inxenuo basta ollar para a primeira letra 1701 01:22:06,590 --> 01:22:09,700 na mazá ou albaricoque ou pera ou melón, 1702 01:22:09,700 --> 01:22:13,420 porque como podes ver eses listas aínda podía comezar por moito tempo. 1703 01:22:13,420 --> 01:22:17,130 >> E por iso este pode ser tipo de linear-- tan especie de lento, 1704 01:22:17,130 --> 01:22:19,980 como co gran O de n que discutir anteriormente. 1705 01:22:19,980 --> 01:22:25,290 Entón, o que un verdadeiro táboa hash boa vontade fazer-- terá unha variedade moi grande. 1706 01:22:25,290 --> 01:22:28,574 E vai usar un moito máis función de hash sofisticado, 1707 01:22:28,574 --> 01:22:30,240 de xeito que non só ollar para o "a". 1708 01:22:30,240 --> 01:22:35,480 Quizais ten en conta "a-p-p-l-e" e dalgún xeito, convértese esas cinco letras 1709 01:22:35,480 --> 01:22:38,400 no lugar onde mazá debe ser almacenado. 1710 01:22:38,400 --> 01:22:42,660 Estamos só inxenuamente usando letra 'a' só porque é agradable e sinxela. 1711 01:22:42,660 --> 01:22:44,600 >> Pero unha táboa hash, en Ao final, pode pensar 1712 01:22:44,600 --> 01:22:47,270 como unha combinación de unha matriz, cada un dos cales 1713 01:22:47,270 --> 01:22:51,700 ten unha lista vinculada que idealmente deberá ser tan curto como sexa posible. 1714 01:22:51,700 --> 01:22:54,364 E iso non é unha solución obvia. 1715 01:22:54,364 --> 01:22:57,280 De feito, gran parte da sintonização fina o que pasa debaixo do capó cando 1716 01:22:57,280 --> 01:22:59,654 aplicar estes tipos de estruturas de datos sofisticados 1717 01:22:59,654 --> 01:23:01,640 é o que é o dereito lonxitude da matriz? 1718 01:23:01,640 --> 01:23:03,250 Cal é a función hash non? 1719 01:23:03,250 --> 01:23:04,830 Como gardar cousas na memoria? 1720 01:23:04,830 --> 01:23:07,249 >> Pero entender o quão rápido este tipo de debate 1721 01:23:07,249 --> 01:23:10,540 escalada, sexa tan lonxe que é unha especie de sobre a cabeza neste momento, que 1722 01:23:10,540 --> 01:23:11,360 está ben. 1723 01:23:11,360 --> 01:23:18,820 Pero comezamos, recall, con verdadeiramente algo de baixo nivel e electrónicos. 1724 01:23:18,820 --> 01:23:20,819 E así esta nova é este tema da abstracción, 1725 01:23:20,819 --> 01:23:23,610 onde unha vez que comezar a tomar para concedido, OK, eu teño ele-- hai 1726 01:23:23,610 --> 01:23:26,680 memoria física, OK, ten, cada localización física ten un enderezo, 1727 01:23:26,680 --> 01:23:29,910 OK, I got it, I pode representar estes enderezos como arrows-- 1728 01:23:29,910 --> 01:23:34,650 pode rapidamente comezar a ter conversas máis sofisticados que 1729 01:23:34,650 --> 01:23:38,360 ao final parece estar nos permite para resolver problemas como buscar 1730 01:23:38,360 --> 01:23:41,620 e selección de forma máis eficaz. 1731 01:23:41,620 --> 01:23:44,190 E por suposto, demasiado-- porque eu creo que iso 1732 01:23:44,190 --> 01:23:48,700 é o máis profundo, fomos nalgún destes temas CS proper-- Nós 1733 01:23:48,700 --> 01:23:51,880 feito en un día e unha metade neste apuntar o que pode xeralmente facer máis 1734 01:23:51,880 --> 01:23:55,520 o curso de oito semanas nun semestre. 1735 01:23:55,520 --> 01:23:59,670 >> Calquera preguntas sobre estes? 1736 01:23:59,670 --> 01:24:01,100 Non? 1737 01:24:01,100 --> 01:24:01,940 Todo ben. 1738 01:24:01,940 --> 01:24:05,610 Ben, por que non facemos un descanso alí, iniciar o xantar uns minutos máis cedo, 1739 01:24:05,610 --> 01:24:07,052 retomar en só aproximadamente unha hora? 1740 01:24:07,052 --> 01:24:08,760 E eu vou durar algo con preguntas. 1741 01:24:08,760 --> 01:24:11,343 Entón eu vou ter que ir levar algunhas chamadas, se está todo OK. 1742 01:24:11,343 --> 01:24:15,000 Vou chamar unha música, con todo, pero o xantar debe ser á volta da esquina. 1743 01:24:15,000 --> 01:24:17,862