1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [REPRODUCCIÓ DE MÚSICA] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: Aquest és CS50. 5 00:00:14,010 --> 00:00:18,090 I això és alhora el principi i el end-- com literally-- gairebé el final 6 00:00:18,090 --> 00:00:18,825 de la setmana 6. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Jo vaig pensar en compartir un mica d'un fet divertit. 9 00:00:22,640 --> 00:00:25,370 He tirat això des d'un conjunt de dades del semestre passat. 10 00:00:25,370 --> 00:00:29,710 Vostè pot recordar que li demanem a cada forma conjunt p si has vist en línia 11 00:00:29,710 --> 00:00:31,580 o si vostè ha assistit a persona. 12 00:00:31,580 --> 00:00:33,020 I aquí hi ha les dades. 13 00:00:33,020 --> 00:00:34,710 Així que estava molt predictible avui. 14 00:00:34,710 --> 00:00:37,126 Però nosaltres volíem passar una mica de temps amb vostè, però. 15 00:00:37,126 --> 00:00:40,599 Algú vol conjecturar per què això gràfic és tan jaggy, dalt a baix, dalt a baix, 16 00:00:40,599 --> 00:00:41,265 tan consistentment? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Què fer cada un dels pics i depressions representen? 19 00:00:45,130 --> 00:00:46,005 >> AUDIÈNCIA: [inaudible] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: En efecte. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 I més divertida, Déu no ho vulgui, tenim una conferència en un divendres 24 00:00:55,480 --> 00:00:58,960 l'inici del semestre, això és el que succeeixi. 25 00:00:58,960 --> 00:01:03,430 Així que avui, participem en una mica Més informació sobre les estructures de dades. 26 00:01:03,430 --> 00:01:06,660 I per donar-li més d'un sòlid model mental dels problemes a les cinc, 27 00:01:06,660 --> 00:01:07,450 que ara està fora. 28 00:01:07,450 --> 00:01:10,817 Errors d'ortografia, en el qual, anem a de lliurar un arxiu de text uns 100.000 29 00:01:10,817 --> 00:01:12,650 a més de les paraules en anglès, i vostè va a tenir 30 00:01:12,650 --> 00:01:17,770 per trobar la manera de carregar ells intel·ligentment en la memòria, a la memòria RAM, l'ús d'algunes dades 31 00:01:17,770 --> 00:01:19,330 estructura de la seva elecció. 32 00:01:19,330 --> 00:01:22,470 >> Ara bé, una estructura d'aquest tipus de dades podria ser, però probablement no hauria de ser, 33 00:01:22,470 --> 00:01:25,630 la llista enllaçada bastant simplista, que es va introduir l'última vegada. 34 00:01:25,630 --> 00:01:29,220 I una llista enllaçada tenia almenys un avantatge sobre una matriu. 35 00:01:29,220 --> 00:01:32,096 Quin és un dels avantatges de una llista enllaçada discutible? 36 00:01:32,096 --> 00:01:32,950 >> AUDIÈNCIA: Inserció. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Inserció. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Què vols dir amb això? 40 00:01:35,196 --> 00:01:37,872 >> AUDIÈNCIA: En qualsevol lloc al llarg de la llista de [inaudible]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Good. 42 00:01:38,770 --> 00:01:42,090 Així que vostè pot inserir un element sempre que sigui que vols a la meitat de la llista 43 00:01:42,090 --> 00:01:45,490 sense haver de barrejar res, que vam arribar a la conclusió, en la nostra classificació 44 00:01:45,490 --> 00:01:47,630 discussions, no és necessàriament una bona cosa, 45 00:01:47,630 --> 00:01:51,200 perquè es necessita temps per navegar realitat tots aquests éssers humans cap a l'esquerra o dreta. 46 00:01:51,200 --> 00:01:55,540 I així, amb una llista enllaçada, pot simplement assignar amb malloc, un nou node, 47 00:01:55,540 --> 00:01:58,385 i després actualitzar un parell de pointers-- dos, tres operacions max-- 48 00:01:58,385 --> 00:02:01,480 i som capaços de ranura algú en qualsevol lloc en una llista. 49 00:02:01,480 --> 00:02:03,550 >> ¿Quina altra cosa era avantatjós sobre una llista enllaçada? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Sí? 52 00:02:05,659 --> 00:02:06,534 >> AUDIÈNCIA: [inaudible] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Malan: Perfecte. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfecte. 57 00:02:11,090 --> 00:02:12,070 És molt dinàmic. 58 00:02:12,070 --> 00:02:15,100 I això que no estàs cometent, per endavant, fins a cert grandària fixa 59 00:02:15,100 --> 00:02:18,750 tros de memòria, de la mateixa manera que vostè hauria a amb una matriu, l'alça dels quals 60 00:02:18,750 --> 00:02:22,455 és que es pot assignar nodes només en la demanda d'aquesta manera utilitzant només la quantitat d'espai 61 00:02:22,455 --> 00:02:23,330 com que realment necessita. 62 00:02:23,330 --> 00:02:26,830 A diferència d'una matriu, que et poden assignar accidentalment massa poc. 63 00:02:26,830 --> 00:02:28,871 I llavors només va a ser un dolor al coll 64 00:02:28,871 --> 00:02:32,440 reassignar una nova matriu més gran, copiar a tot estirar, alliberar la matriu d'edat, 65 00:02:32,440 --> 00:02:33,990 i després passar sobre el seu negoci. 66 00:02:33,990 --> 00:02:37,479 O pitjor encara, és possible assignar de manera més memòria de la que realment es necessita, 67 00:02:37,479 --> 00:02:40,520 i pel que tindrem un molt matriu escassament poblades, per així dir-ho. 68 00:02:40,520 --> 00:02:44,350 >> Així que una llista enllaçada que dóna a aquests avantatges de dinamisme i flexibilitat 69 00:02:44,350 --> 00:02:46,080 amb insercions i delecions. 70 00:02:46,080 --> 00:02:48,000 Però sens dubte que ha d'haver un preu que es paga. 71 00:02:48,000 --> 00:02:50,000 De fet, un dels temes explorat en concurs zero 72 00:02:50,000 --> 00:02:52,430 era un parell de les compensacions que hem vist fins al moment. 73 00:02:52,430 --> 00:02:56,161 Així que el que és un preu pagat o per un la baixa d'una llista enllaçada? 74 00:02:56,161 --> 00:02:56,660 Sí. 75 00:02:56,660 --> 00:02:57,560 >> AUDIÈNCIA: No hi ha accés aleatori. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: No hi ha accés aleatori. 77 00:02:58,809 --> 00:02:59,540 Però a qui li importa? 78 00:02:59,540 --> 00:03:01,546 Accés aleatori no sona convincent. 79 00:03:01,546 --> 00:03:02,421 >> AUDIÈNCIA: [inaudible] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Exactament. 82 00:03:05,740 --> 00:03:07,580 Si vostè vol tenir una certa algorithm-- 83 00:03:07,580 --> 00:03:10,170 i que em faci realitat proposo recerca binària, en particular, que 84 00:03:10,170 --> 00:03:12,600 és un que hem utilitzat bastant bit-- si vostè no té accés a l'atzar, 85 00:03:12,600 --> 00:03:15,516 no es pot fer així de simple aritmètica de trobar com l'element mitjà 86 00:03:15,516 --> 00:03:16,530 i saltar a la dreta a la mateixa. 87 00:03:16,530 --> 00:03:20,239 En el seu lloc, ha de començar pel primer element i linealment buscar des de l'esquerra 88 00:03:20,239 --> 00:03:22,780 a dreta si vols trobar el mitjà o qualsevol altre element. 89 00:03:22,780 --> 00:03:24,410 >> AUDIÈNCIA: Probablement té més memòria. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: Presa més memòria. 91 00:03:25,040 --> 00:03:27,464 On és aquest addicional cost que ve de la memòria? 92 00:03:27,464 --> 00:03:28,339 >> AUDIÈNCIA: [inaudible] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Exactament. 95 00:03:33,440 --> 00:03:35,679 En aquest cas aquí, vam tenir una llista enllaçada per a enters, 96 00:03:35,679 --> 00:03:37,470 i no obstant això, estem duplicant la quantitat de memòria 97 00:03:37,470 --> 00:03:39,680 necessitem també per l'emmagatzematge d'aquestes punters. 98 00:03:39,680 --> 00:03:42,090 Ara menys d'un gran problema ja les seves estructures es fan més grans 99 00:03:42,090 --> 00:03:45,320 i vostè està emmagatzemant no és un nombre, però potser un estudiant o algun altre objecte. 100 00:03:45,320 --> 00:03:46,880 Però el punt segueix sent dubte. 101 00:03:46,880 --> 00:03:49,421 I pel que un nombre de les operacions en llistes enllaçades van ser cridats 102 00:03:49,421 --> 00:03:50,570 eren grans O de N-- lineal. 103 00:03:50,570 --> 00:03:54,730 Coses com la inserció o recerca o eliminació en cas d'un element 104 00:03:54,730 --> 00:03:57,720 va passar a ser al final de la llista si està ordenada o no. 105 00:03:57,720 --> 00:04:01,167 >> A vegades pot ser que tinguis sort i en fora de manera més baixos en aquestes operacions 106 00:04:01,167 --> 00:04:04,250 També podria ser la constant de temps si estàs sempre mirant al primer element, 107 00:04:04,250 --> 00:04:05,070 per exemple. 108 00:04:05,070 --> 00:04:09,360 Però en última instància, ens vam prometre per aconseguir el sant grial 109 00:04:09,360 --> 00:04:12,630 d'estructures de dades, o alguns dels mateixos aproximació, 110 00:04:12,630 --> 00:04:14,290 per mitjà de la constant de temps. 111 00:04:14,290 --> 00:04:17,579 Podem trobar elements o afegir elements o eliminar elements d'una llista? 112 00:04:17,579 --> 00:04:19,059 Ens veurem molt aviat. 113 00:04:19,059 --> 00:04:21,100 I resulta que un dels mecanismes que estem 114 00:04:21,100 --> 00:04:23,464 va a començar a utilitzar avui en dia, l'ús anual de P posat 5, 115 00:04:23,464 --> 00:04:24,630 en realitat és bastant familiar. 116 00:04:24,630 --> 00:04:27,430 Per exemple, si es tracta d'un munt de llibres d'examen, cadascun dels quals 117 00:04:27,430 --> 00:04:29,660 té un estudiant de primer nom i cognom a ell, 118 00:04:29,660 --> 00:04:31,820 i jo els recull de la al final d'un examen, 119 00:04:31,820 --> 00:04:33,746 i són tots bastant tant en un ordre aleatori, 120 00:04:33,746 --> 00:04:36,370 i volem anar sobre la classificació aquests exàmens perquè una vegada classificades 121 00:04:36,370 --> 00:04:38,661 és només molt més fàcil i més ràpid a lliurar-los de tornada 122 00:04:38,661 --> 00:04:40,030 als estudiants en ordre alfabètic. 123 00:04:40,030 --> 00:04:42,770 Quins serien els seus instints per a una pila d'exàmens d'aquest tipus? 124 00:04:42,770 --> 00:04:45,019 >> Bé, si ets com jo, podria veure que aquest és m, 125 00:04:45,019 --> 00:04:48,505 així que em vaig a posar això en una espècie de, si aquest és el meu taula o el meu pis on 126 00:04:48,505 --> 00:04:50,650 Estic estenent coses fora-- o el meu arsenal realmente-- 127 00:04:50,650 --> 00:04:52,210 Jo podria posar tota la Sra allà. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Heus aquí una A. Així que podria Com posar els d'aquí. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Aquí hi ha una altra A. Vaig posar que aquí. 132 00:04:57,980 --> 00:05:02,490 Aquí hi ha una Z. Hi ha un altre el Sr. I així Jo podria començar a fer munts com aquest. 133 00:05:02,490 --> 00:05:06,620 I llavors potser m'agradaria anar endavant i una espècie de molt primmirada-li espècie 134 00:05:06,620 --> 00:05:07,710 les piles individuals. 135 00:05:07,710 --> 00:05:11,300 Però el punt és, buscaria a l'entrada que estic sola mà 136 00:05:11,300 --> 00:05:14,016 i m'agradaria fer alguns calcular decisió basada en aquesta entrada. 137 00:05:14,016 --> 00:05:15,640 Si comença amb A, el va posar allà. 138 00:05:15,640 --> 00:05:18,980 Si comença per Z, el va posar sobre allà, i tota la resta. 139 00:05:18,980 --> 00:05:22,730 >> Així que aquesta és una tècnica que és generalment conegut com hashing-- H-A-S-H- 140 00:05:22,730 --> 00:05:26,550 que en general significa prendre com a d'entrada i utilitzar aquesta entrada per calcular 141 00:05:26,550 --> 00:05:30,940 un valor, en general, un nombre, i que nombre és l'índex en un emmagatzematge 142 00:05:30,940 --> 00:05:32,260 contenidor, com una matriu. 143 00:05:32,260 --> 00:05:35,490 Així que en altres paraules, que podria tenir una funció hash, com ho faig en el meu cap, 144 00:05:35,490 --> 00:05:37,940 que si veig algú és nom que comença amb A, 145 00:05:37,940 --> 00:05:40,190 Vaig a assignar que a zero en el meu cap. 146 00:05:40,190 --> 00:05:44,160 I si veig algú amb Z, estic anar al mapa que a 25 en el meu cap 147 00:05:44,160 --> 00:05:46,220 i després posar això en l'última pila més. 148 00:05:46,220 --> 00:05:50,990 >> Ara, si ho penses, no el meu cervell però un programa en C, el que els números podrien 149 00:05:50,990 --> 00:05:53,170 vostè confia en aconseguir el mateix resultat? 150 00:05:53,170 --> 00:05:55,594 En altres paraules, si tenia el caràcter ASCII A, 151 00:05:55,594 --> 00:05:57,510 ¿Com determinar el franc per posar en? 152 00:05:57,510 --> 00:05:59,801 És probable que no vol el va posar en el cub 65, que 153 00:05:59,801 --> 00:06:01,840 seria com d'allà sense una bona raó. 154 00:06:01,840 --> 00:06:04,320 On vols posar un en termes del seu valor ASCII? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 On vols que fer per al seu ASCII valor per a arribar a una galleda intel·ligent 157 00:06:08,920 --> 00:06:09,480 per a posar en? 158 00:06:09,480 --> 00:06:10,206 >> AUDIÈNCIA: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Sí. 160 00:06:10,956 --> 00:06:13,190 Així menys A o menys específicament 65 si és 161 00:06:13,190 --> 00:06:18,240 un capital d'A O 98 si es tracta d'una minúscula. 162 00:06:18,240 --> 00:06:21,300 I pel que ens permetria, molt simplement i molt aritmèticament, 163 00:06:21,300 --> 00:06:23,260 posar alguna cosa en una galleda així. 164 00:06:23,260 --> 00:06:26,010 Així que resulta que en realitat fem això també fins i tot amb els concursos. 165 00:06:26,010 --> 00:06:29,051 >> Així que vostè pot recordar que vas marcar el teu Nom de l'ensenyament del seu company a la portada. 166 00:06:29,051 --> 00:06:32,270 I es van organitzar noms del TF en aquestes columnes en ordre alfabètic, 167 00:06:32,270 --> 00:06:34,400 Bé, ho creguis o no, quan tot 80 més de nosaltres 168 00:06:34,400 --> 00:06:37,800 es van reunir l'altra nit a grau, l'últim pas en el nostre procés de classificació 169 00:06:37,800 --> 00:06:41,830 és per a discutir les proves en un gran espai de sòl en la [inaudible] 170 00:06:41,830 --> 00:06:45,110 i establir proves de tot el món a exactament en l'ordre dels seus de TF 171 00:06:45,110 --> 00:06:47,700 noms a la coberta, ja que llavors és molt més fàcil per a nosaltres 172 00:06:47,700 --> 00:06:51,290 per buscar a través que l'ús lineal buscar o algun tipus d'intel·ligència 173 00:06:51,290 --> 00:06:54,050 per a un TF per trobar el seu o proves dels seus estudiants. 174 00:06:54,050 --> 00:06:56,060 >> Així que aquesta idea de hash que veuràs és 175 00:06:56,060 --> 00:07:00,520 bastant poderós és en realitat bastant lloc comú i molt intuïtiva, 176 00:07:00,520 --> 00:07:03,000 de la mateixa manera que potser dividir i conquesta va ser a la setmana zero. 177 00:07:03,000 --> 00:07:05,250 Em avanç ràpid per al hackathon un parell d'anys enrere. 178 00:07:05,250 --> 00:07:08,040 Aquest va ser Zamyla i un parell de altres estudiants de felicitació personal 179 00:07:08,040 --> 00:07:09,030 com van entrar. 180 00:07:09,030 --> 00:07:12,680 I vam tenir un munt de plegat taules allà amb etiquetes de nom. 181 00:07:12,680 --> 00:07:15,380 I havíem organitzat les etiquetes de nom amb com l'As d'allà 182 00:07:15,380 --> 00:07:16,690 i la Zs allà. 183 00:07:16,690 --> 00:07:20,350 I així un dels TFS molt intel·ligentment va escriure això com les instruccions 184 00:07:20,350 --> 00:07:21,030 per al dia. 185 00:07:21,030 --> 00:07:24,480 I en la setmana 12 del semestre aquest tot tenia sentit perfecte i tot el món 186 00:07:24,480 --> 00:07:25,310 sabia què fer. 187 00:07:25,310 --> 00:07:27,900 Però en qualsevol moment que tens en cua de la mateixa manera, 188 00:07:27,900 --> 00:07:30,272 està implementant la mateixa noció d'un hash. 189 00:07:30,272 --> 00:07:31,730 Així que anem a formalitzar una mica. 190 00:07:31,730 --> 00:07:32,890 Aquí és una matriu. 191 00:07:32,890 --> 00:07:36,820 Es va assenyalar a ser una mica àmplia acaba de descriure, visualment, 192 00:07:36,820 --> 00:07:38,920 que podríem posar cadenes en alguna cosa com això. 193 00:07:38,920 --> 00:07:41,970 I aquesta matriu és clarament de mida 26 total. 194 00:07:41,970 --> 00:07:43,935 I la cosa es diu taula arbitràriament. 195 00:07:43,935 --> 00:07:48,930 Però això és només una representació artística del que podria ser una taula hash. 196 00:07:48,930 --> 00:07:52,799 >> Així que una taula hash ara va a ser una estructura de dades de nivell superior. 197 00:07:52,799 --> 00:07:54,840 Al final del dia estem a punt de veure que vostè 198 00:07:54,840 --> 00:07:58,700 pot aplicar una taula hash, que és molt similar a la línia de check-in 199 00:07:58,700 --> 00:08:02,059 en un hackathon molt com aquest taula utilitzada per a la classificació dels llibres d'examen. 200 00:08:02,059 --> 00:08:03,850 Però una taula hash és espècie d'aquest alt nivell 201 00:08:03,850 --> 00:08:08,250 concepte que podria utilitzar una matriu sota el capó per implementar-lo, 202 00:08:08,250 --> 00:08:11,890 o pot utilitzar una llista de longitud, o fins i tot potser algunes altres estructures de dades. 203 00:08:11,890 --> 00:08:15,590 I això sí que és la presa theme-- alguns d'aquests ingredients fonamentals 204 00:08:15,590 --> 00:08:18,310 com una matriu i aquest edifici bloquejar ara una llista de longitud 205 00:08:18,310 --> 00:08:21,740 i veure què més podem construir a la part superior dels que, com a ingredients 206 00:08:21,740 --> 00:08:26,550 en una recepta, el que fa més i més els resultats finals interessants i útils. 207 00:08:26,550 --> 00:08:28,680 >> Així que amb la taula hash podríem implementar 208 00:08:28,680 --> 00:08:32,540 en la memòria pictòricament com aquest, però com podria ser en realitat codificada cap amunt? 209 00:08:32,540 --> 00:08:33,789 Bé, potser la forma més senzilla és aquesta. 210 00:08:33,789 --> 00:08:38,270 Si la capacitat en totes les tapes, és només alguns constant-- per exemple 26, 211 00:08:38,270 --> 00:08:42,030 per 26 lletres del alphabet-- Jo podria cridar a la meva taula de variables, 212 00:08:42,030 --> 00:08:45,630 i jo podria dir que em vaig a posar estrelles Char-hi, o una cadena. 213 00:08:45,630 --> 00:08:49,880 Així que és tan simple com això si vulgui implementar una taula hash. 214 00:08:49,880 --> 00:08:51,490 I, no obstant això, això és en realitat una matriu. 215 00:08:51,490 --> 00:08:53,198 Però, de nou, un hash taula és ara el que anem a 216 00:08:53,198 --> 00:08:57,470 trucar a un tipus de dades abstracte que només una mena d'estratificació conceptual a la part superior 217 00:08:57,470 --> 00:09:00,780 d'una mica més mundà ara com a vector. 218 00:09:00,780 --> 00:09:02,960 >> Ara, com fem per sobre la resolució de problemes? 219 00:09:02,960 --> 00:09:06,980 Bé, abans vaig tenir el luxe de tenir prou espai de taula aquí 220 00:09:06,980 --> 00:09:09,460 perquè jo pogués posar el concursos en qualsevol lloc que volia. 221 00:09:09,460 --> 00:09:10,620 De manera que es pot anar aquí. 222 00:09:10,620 --> 00:09:12,100 Zs poden anar aquí. 223 00:09:12,100 --> 00:09:13,230 Sra podria anar aquí. 224 00:09:13,230 --> 00:09:14,740 I després vaig tenir una mica d'espai extra. 225 00:09:14,740 --> 00:09:18,740 Però això és una mica d'un dret de trucs ara perquè aquesta taula, si realment 226 00:09:18,740 --> 00:09:22,720 pensat en això com una matriu, és just serà d'algun grandària fixa. 227 00:09:22,720 --> 00:09:25,380 >> Així que tècnicament, si em tiri fins a prova d'un altre estudiant 228 00:09:25,380 --> 00:09:28,490 i veure, oh, aquesta persona de nom comença amb una A també, 229 00:09:28,490 --> 00:09:30,980 Jo com que vull posar aquí. 230 00:09:30,980 --> 00:09:34,740 Però tan aviat com em vaig posar allà, si aquesta taula de fet representa una matriu, 231 00:09:34,740 --> 00:09:37,840 Jo vaig a estar anul·lant o clobbering a qualsevol concurs d'aquest estudiant és. 232 00:09:37,840 --> 00:09:38,340 Dreta? 233 00:09:38,340 --> 00:09:41,972 Si es tracta d'una matriu, només una cosa pot anar en cadascuna d'aquestes cèl·lules o elements. 234 00:09:41,972 --> 00:09:43,680 I així que tipus de tenir a escollir i triar. 235 00:09:43,680 --> 00:09:45,735 >> Ara abans que tipus de enganyat i va fer això o jo 236 00:09:45,735 --> 00:09:47,526 només tipus d'apilament ells un sobre l'altre. 237 00:09:47,526 --> 00:09:49,170 Però això no va a volar en codi. 238 00:09:49,170 --> 00:09:52,260 Llavors, on podria jo posar el segon estudiant el nom 239 00:09:52,260 --> 00:09:54,964 Una és si tot el que tenia és aquest espai de taules disponibles? 240 00:09:54,964 --> 00:09:57,880 I jo he fet servir tres ranures i es sembla que hi ha només uns pocs altres. 241 00:09:57,880 --> 00:09:58,959 Què podria fer? 242 00:09:58,959 --> 00:09:59,834 AUDIÈNCIA: [inaudible] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Sí. 245 00:10:01,315 --> 00:10:02,370 Potser anem a mantenir simple. 246 00:10:02,370 --> 00:10:02,660 Dreta? 247 00:10:02,660 --> 00:10:04,243 No s'ajusta a on vull posar-ho. 248 00:10:04,243 --> 00:10:07,450 Així que em vaig a posar tècnicament, on un B aniria. 249 00:10:07,450 --> 00:10:09,932 Bé, és clar, estic començant per a pintar a mi mateix en una cantonada. 250 00:10:09,932 --> 00:10:11,890 Si arribo a un estudiant el nom és en realitat B, 251 00:10:11,890 --> 00:10:14,840 ara B serà mogut una mica cap endavant, com podria succeir, si, 252 00:10:14,840 --> 00:10:17,530 si això és un B, ara ha d'anar aquí. 253 00:10:17,530 --> 00:10:20,180 >> I pel que aquest molt ràpidament podria convertir-se en un problema, 254 00:10:20,180 --> 00:10:23,850 però és una tècnica que en realitat es coneix com sondeig lineal, 255 00:10:23,850 --> 00:10:26,650 pel que vostè només considera la seva matriu a ser al llarg de la línia. 256 00:10:26,650 --> 00:10:29,680 I que acaba de tipus de sonda o inspeccionar cada element disponible 257 00:10:29,680 --> 00:10:31,360 a la recerca d'un lloc disponible. 258 00:10:31,360 --> 00:10:34,010 I tan aviat com s'assabenti un, se't cau en aquest país. 259 00:10:34,010 --> 00:10:38,390 >> Ara, el preu que es paga ara per aquesta solució és el que? 260 00:10:38,390 --> 00:10:41,300 Tenim una matriu de mida fixa, i quan inserit noms 261 00:10:41,300 --> 00:10:44,059 -hi, almenys al principi, el que és el temps d'execució de la inserció 262 00:10:44,059 --> 00:10:46,350 per posar els estudiants concursos en els cubs de la dreta? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O de què? 265 00:10:50,002 --> 00:10:51,147 >> AUDIÈNCIA: n. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: Vaig escoltar gran O de n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 No és cert. 269 00:10:54,300 --> 00:10:56,490 Però anem a esmicolar ¿Per què en un moment. 270 00:10:56,490 --> 00:10:57,702 ¿Quina altra cosa podria ser? 271 00:10:57,702 --> 00:10:58,755 >> AUDIÈNCIA: [inaudible] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: I em va deixar fer visualment. 273 00:11:00,380 --> 00:11:04,720 Així que suposem que aquesta és la lletra S. 274 00:11:04,720 --> 00:11:05,604 >> AUDIÈNCIA: És un. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: És un. 276 00:11:06,520 --> 00:11:06,710 Dreta? 277 00:11:06,710 --> 00:11:08,950 Aquesta és una matriu, que vol dir que tenim accés aleatori. 278 00:11:08,950 --> 00:11:11,790 I si pensem en això com a zero i això com 25, 279 00:11:11,790 --> 00:11:13,800 i ens adonem que, oh, aquí està la meva entrada S, 280 00:11:13,800 --> 00:11:16,350 Certament puc convertir S, un caràcter ASCII, 281 00:11:16,350 --> 00:11:18,540 a un nombre corresponent entre zero i 25 282 00:11:18,540 --> 00:11:20,910 i després immediatament posar on pertany. 283 00:11:20,910 --> 00:11:26,120 >> Però, és clar, tan aviat com arribi a la segona persona el nom és A o B o C 284 00:11:26,120 --> 00:11:29,300 finalment, si jo he fet servir el sondeig lineal com la meva solució, 285 00:11:29,300 --> 00:11:31,360 el temps d'execució de inserció en el pitjor dels casos 286 00:11:31,360 --> 00:11:33,120 que realment es va a delegar en què? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 I jo ho vaig escoltar aquí correctament des del principi. 289 00:11:36,045 --> 00:11:36,920 AUDIÈNCIA: [inaudible] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Pel que és de fet un cop n vostè té un conjunt de dades prou gran. 291 00:11:41,620 --> 00:11:44,410 Així, d'una banda, si la seva matriu és prou gran 292 00:11:44,410 --> 00:11:48,287 i les seves dades són escassos suficient, aconseguir aquest bell temps constant. 293 00:11:48,287 --> 00:11:50,620 Però tan aviat com comenci cada vegada més i més elements, 294 00:11:50,620 --> 00:11:53,200 i només estadísticament s'obté més persones amb la lletra 295 00:11:53,200 --> 00:11:56,030 A com el seu nom o la lletra B, podria potencialment 296 00:11:56,030 --> 00:11:57,900 delegar en alguna cosa més lineal. 297 00:11:57,900 --> 00:11:59,640 Així que no és perfecte. 298 00:11:59,640 --> 00:12:00,690 Així que podríem fer millor? 299 00:12:00,690 --> 00:12:03,210 >> Bé, el que va ser la nostra solució abans quan ens 300 00:12:03,210 --> 00:12:06,820 volen tenir més dinamisme que alguna cosa així com una gran varietat permès? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 AUDIÈNCIA: [inaudible] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Què hem presentem? 304 00:12:10,030 --> 00:12:10,530 Sí. 305 00:12:10,530 --> 00:12:11,430 Així que una llista enllaçada. 306 00:12:11,430 --> 00:12:14,430 Bé, anem a veure que és el vinculat llista podria fer per nosaltres en el seu lloc. 307 00:12:14,430 --> 00:12:17,630 Bé, deixa proposo que dibuixar la imatge de la següent manera. 308 00:12:17,630 --> 00:12:19,620 Ara bé, aquest és un diferent imatge d'un exemple 309 00:12:19,620 --> 00:12:24,750 a partir d'un text diferent, en realitat, que és en realitat l'ús d'una matriu de mida 31. 310 00:12:24,750 --> 00:12:28,220 I aquest autor simplement decidit hash de cadenes 311 00:12:28,220 --> 00:12:32,430 no es basa en els noms de la persona, però en funció de les seves dates de naixement. 312 00:12:32,430 --> 00:12:35,680 Independentment del mes, es van adonar si el que es neix en el primer d'un mes 313 00:12:35,680 --> 00:12:39,580 o el 31 d'un mes, l'autor es hash basat en aquest valor, 314 00:12:39,580 --> 00:12:44,154 a fi de difondre els noms una mica més que 26 punts podrien permetre. 315 00:12:44,154 --> 00:12:47,320 I potser és una mica més uniforme d'anar amb les lletres de l'alfabet, 316 00:12:47,320 --> 00:12:50,236 perquè, per descomptat, és probable que hi hagi més persones al món amb noms 317 00:12:50,236 --> 00:12:54,020 que comencen amb una que sens dubte algunes altres lletres de l'alfabet. 318 00:12:54,020 --> 00:12:56,380 Així que potser això és una mica més uniforme, suposant 319 00:12:56,380 --> 00:12:58,640 una distribució uniforme dels nadons a través d'un mes. 320 00:12:58,640 --> 00:12:59,990 >> Però, és clar, això és encara imperfecte. 321 00:12:59,990 --> 00:13:00,370 Dreta? 322 00:13:00,370 --> 00:13:01,370 Tindrem col·lisions. 323 00:13:01,370 --> 00:13:04,680 Diverses persones en aquest estructura de dades són encara 324 00:13:04,680 --> 00:13:08,432 que té la mateixa data de naixement, com a mínim, ets independentment de mes. 325 00:13:08,432 --> 00:13:09,640 Però el que ha fet l'autor? 326 00:13:09,640 --> 00:13:13,427 Bé, sembla que tenim una matriu a la banda esquerra dibuixat verticalment, 327 00:13:13,427 --> 00:13:15,010 però això és només una representació artística. 328 00:13:15,010 --> 00:13:18,009 No importa quina direcció dibuixar una matriu, que segueix sent una matriu. 329 00:13:18,009 --> 00:13:20,225 Què és aquest un arranjament de semblar? 330 00:13:20,225 --> 00:13:21,500 >> AUDIÈNCIA: llista enllaçat. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Sí. 332 00:13:21,650 --> 00:13:23,490 Sembla que es tracta d'una gamma de llista enllaçada. 333 00:13:23,490 --> 00:13:26,490 Així que de nou, a aquest punt de la classe de la utilització d'aquestes estructures de dades ara 334 00:13:26,490 --> 00:13:28,550 com a ingredients a més solucions interessants, 335 00:13:28,550 --> 00:13:30,862 vostè pot prendre absolutament 01:00 fonamental, com una matriu, 336 00:13:30,862 --> 00:13:33,320 i després prendre una mica més interessant com una llista enllaçada 337 00:13:33,320 --> 00:13:36,660 i fins i tot combinar en una encara més interessant estructura de dades. 338 00:13:36,660 --> 00:13:39,630 I, de fet, això també faria ser anomenat una taula hash, 339 00:13:39,630 --> 00:13:42,610 de manera que la matriu és realment la taula hash, 340 00:13:42,610 --> 00:13:45,600 però que la taula hash té cadenes, per dir-ho, 341 00:13:45,600 --> 00:13:50,220 que pot créixer o disminuir en la base de la nombre d'elements que voleu inserir. 342 00:13:50,220 --> 00:13:52,990 >> Ara, en conseqüència, el que hi ha el temps d'execució ara? 343 00:13:52,990 --> 00:13:58,030 Si vull inserir algú el aniversari és el 31 d'octubre 344 00:13:58,030 --> 00:13:59,040 ¿D'on ve ell o ella? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Bé. 347 00:14:01,030 --> 00:14:02,819 A la part inferior, on diu 31. 348 00:14:02,819 --> 00:14:03,610 I això és perfecte. 349 00:14:03,610 --> 00:14:05,060 Aquesta va ser la constant de temps. 350 00:14:05,060 --> 00:14:08,760 Però, ¿i si ens trobem amb algú més el aniversari és, anem a veure, 351 00:14:08,760 --> 00:14:10,950 Octubre, novembre, 31 de desembre? 352 00:14:10,950 --> 00:14:12,790 On és ell o ella va a anar? 353 00:14:12,790 --> 00:14:13,290 La mateixa cosa. 354 00:14:13,290 --> 00:14:13,970 Dues pas però. 355 00:14:13,970 --> 00:14:15,303 Això és constant, encara que no és així? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Bé. 358 00:14:16,860 --> 00:14:17,840 En el moment que és. 359 00:14:17,840 --> 00:14:20,570 Però en el cas general, més la gent que afegim, 360 00:14:20,570 --> 00:14:23,790 probabilísticament, anem per aconseguir més i més col·lisions. 361 00:14:23,790 --> 00:14:26,820 >> Ara bé, això és una mica millor perquè tècnicament 362 00:14:26,820 --> 00:14:34,580 ara les cadenes podrien estar en el pitjor dels casos fins quan? 363 00:14:34,580 --> 00:14:38,890 Si introdueixo n persones en aquest més estructura de dades sofisticat, n persones, 364 00:14:38,890 --> 00:14:41,080 en el pitjor dels casos serà n. 365 00:14:41,080 --> 00:14:41,815 Per què? 366 00:14:41,815 --> 00:14:43,332 >> AUDIÈNCIA: Perquè si tothom té el mateix aniversari, 367 00:14:43,332 --> 00:14:44,545 que seran una línia. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Perfecte. 369 00:14:45,420 --> 00:14:47,480 Pot ser que sigui una mica artificiosa, però realment en el pitjor dels casos, 370 00:14:47,480 --> 00:14:50,117 si tothom té el mateix aniversari, tenint en compte les entrades que té, 371 00:14:50,117 --> 00:14:51,950 vostè va a tenir un cadena massivament llarg. 372 00:14:51,950 --> 00:14:54,241 I així, es podria anomenar un la taula de hash, però en realitat és 373 00:14:54,241 --> 00:14:56,810 només una llista massiva vinculada amb una gran quantitat d'espai desaprofitat. 374 00:14:56,810 --> 00:15:00,460 Però en general, si suposem que almenys els aniversaris són uniform-- 375 00:15:00,460 --> 00:15:01,750 i probablement no ho és. 376 00:15:01,750 --> 00:15:02,587 Estic fent això. 377 00:15:02,587 --> 00:15:04,420 Però si assumim, per nom de la discussió 378 00:15:04,420 --> 00:15:07,717 que són, a continuació, en teoria, si Aquesta és la representació vertical, 379 00:15:07,717 --> 00:15:11,050 de la matriu, bé, llavors espero que estiguis posarà les cadenes que són, ja saps, 380 00:15:11,050 --> 00:15:15,880 més o menys la mateixa longitud que cada un aquests representa un dia del mes. 381 00:15:15,880 --> 00:15:19,930 >> Ara bé, si hi ha 31 dies al mes, això vol dir que el meu temps de funcionament realment 382 00:15:19,930 --> 00:15:25,230 és gran O de n més de 31, que se sent millor que lineal. 383 00:15:25,230 --> 00:15:27,950 Però el que era un dels nostres compromisos d'un parell de setmanes 384 00:15:27,950 --> 00:15:31,145 fa cada vegada que es tractava d'expressar el temps d'execució d'un algorisme? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Així que únicament busqui en el terme d'ordre superior. 387 00:15:35,190 --> 00:15:35,690 Dreta? 388 00:15:35,690 --> 00:15:37,400 31 és definitivament útil. 389 00:15:37,400 --> 00:15:39,610 Però això segueix sent gran O de n. 390 00:15:39,610 --> 00:15:41,730 Però un dels temes del problema estableix cinc 391 00:15:41,730 --> 00:15:43,950 serà de reconèixer que absolutament, 392 00:15:43,950 --> 00:15:47,320 asimptòticament, teòricament aquesta estructura de dades 393 00:15:47,320 --> 00:15:50,470 no és millor que només una enorme llista enllaçada. 394 00:15:50,470 --> 00:15:53,550 I, en efecte, en el pitjor dels casos, aquest taula hash podria recaure en això. 395 00:15:53,550 --> 00:15:57,620 >> Però en el món real, amb nosaltres els éssers humans que els propis Mac o PC o el que sigui 396 00:15:57,620 --> 00:16:01,240 i s'estan executant món real programari en les dades del món real, 397 00:16:01,240 --> 00:16:03,260 quin algoritme es preferirà? 398 00:16:03,260 --> 00:16:09,180 El que pren les mesures finals o la un que pren n dividit per 31 passos 399 00:16:09,180 --> 00:16:12,900 trobar alguna dada o per buscar una mica d'informació? 400 00:16:12,900 --> 00:16:16,580 Vull dir, absolutament les 31 marques una diferència en el món real. 401 00:16:16,580 --> 00:16:18,540 És 31 vegades més ràpid. 402 00:16:18,540 --> 00:16:20,880 I nosaltres, els humans són sens dubte va a apreciar això. 403 00:16:20,880 --> 00:16:23,004 >> Així que adonar-se de la dicotomia allà entre realitat 404 00:16:23,004 --> 00:16:25,920 parlant de coses teòricament i asimptòticament que definitivament 405 00:16:25,920 --> 00:16:28,760 té valor com hem vist, però en el món real, 406 00:16:28,760 --> 00:16:32,930 si vostè es preocupa només fer la feliç humà per a les entrades generals, 407 00:16:32,930 --> 00:16:36,010 vostè pot molt bé voler acceptar el fet que, sí, aquesta és lineal, 408 00:16:36,010 --> 00:16:38,360 però és 31 vegades més ràpid que pot ser lineal. 409 00:16:38,360 --> 00:16:41,610 I millor encara, nosaltres no només hem de fer alguna cosa arbitrari com una data de naixement, 410 00:16:41,610 --> 00:16:44,030 podríem passar una mica més temps i la intel·ligència 411 00:16:44,030 --> 00:16:47,140 i pensar en el que podríem fer, donat el nom d'una persona i potser 412 00:16:47,140 --> 00:16:50,130 la seva data de naixement per combinar els ingredients per esbrinar alguna cosa 413 00:16:50,130 --> 00:16:52,720 que és veritablement més uniforme i menys jaggy, 414 00:16:52,720 --> 00:16:56,250 per dir-ho d'aquesta imatge Actualment suggereix que podria ser. 415 00:16:56,250 --> 00:16:57,750 Com podríem aplicar això en codi? 416 00:16:57,750 --> 00:17:00,280 Bé, deixa proposo que simplement demanar prestat una mica de sintaxi que hem 417 00:17:00,280 --> 00:17:01,799 utilitzat un parell de vegades fins ara. 418 00:17:01,799 --> 00:17:03,590 I jo vaig a definir un node, que de nou 419 00:17:03,590 --> 00:17:06,812 és un terme genèric per només algunes recipient per a algun tipus d'estructura de dades. 420 00:17:06,812 --> 00:17:09,020 Vaig a proposar que una cadena va allà. 421 00:17:09,020 --> 00:17:11,369 Però anem a començar a prendre les rodes d'entrenament d'avui. 422 00:17:11,369 --> 00:17:13,230 >> No més biblioteca CS50 realment, a menys que vulgui 423 00:17:13,230 --> 00:17:15,230 per utilitzar-lo per a la seva definitiva projecte, que està bé, 424 00:17:15,230 --> 00:17:18,569 però ara anem a tirar de la cortina i diuen que és només una estrella de carbó. 425 00:17:18,569 --> 00:17:22,069 Així que la paraula no serà nom de la persona en qüestió. 426 00:17:22,069 --> 00:17:25,079 I ara tinc un vincle aquí per al següent node 427 00:17:25,079 --> 00:17:28,170 de manera que aquests representen cadascun dels nodes 428 00:17:28,170 --> 00:17:30,950 a la cadena, potencialment, d'una llista enllaçada. 429 00:17:30,950 --> 00:17:34,090 >> I ara què faig Declaro la taula hash en si? 430 00:17:34,090 --> 00:17:36,660 Com declaro tota aquesta estructura? 431 00:17:36,660 --> 00:17:40,960 Bé, en realitat, de la mateixa manera que jo vaig usar un punter a només el primer element d'una llista 432 00:17:40,960 --> 00:17:44,510 abans, de manera similar puc dir simplement Només necessito un munt de punters 433 00:17:44,510 --> 00:17:46,270 per implementar aquesta taula hash sencer. 434 00:17:46,270 --> 00:17:49,484 Vaig a tenir una matriu crida taula per a la taula hash. 435 00:17:49,484 --> 00:17:50,900 Va a tenir la capacitat de mida. 436 00:17:50,900 --> 00:17:52,525 Aquesta és la quantitat d'elements pot cabre-hi. 437 00:17:52,525 --> 00:17:56,180 I cada un d'aquests elements en aquest matriu serà una estrella de node. 438 00:17:56,180 --> 00:17:56,810 Per què? 439 00:17:56,810 --> 00:18:00,160 Bé, per aquesta imatge, del que sóc l'aplicació de la taula hash com 440 00:18:00,160 --> 00:18:04,330 eficaçment en el principi és només aquesta matriu que hem dibuixat verticalment, 441 00:18:04,330 --> 00:18:06,820 cada un dels quadrats representa un punter. 442 00:18:06,820 --> 00:18:09,170 Que els que tenen barres a través d'ells són simplement nul. 443 00:18:09,170 --> 00:18:11,410 I els que tenen fletxes que van cap a la dreta 444 00:18:11,410 --> 00:18:16,140 són punters a nodes reals reals, ergo el començament d'una llista enllaçada. 445 00:18:16,140 --> 00:18:19,050 >> Així que aquí, llavors, és com podem implementar una taula hash que 446 00:18:19,050 --> 00:18:21,580 implementa encadenament separat. 447 00:18:21,580 --> 00:18:22,840 Ara podem fer millor? 448 00:18:22,840 --> 00:18:25,632 Molt bé em va prometre l'última vegada que podríem arribar constant de temps. 449 00:18:25,632 --> 00:18:27,381 I Jo com que et vaig donar constant de temps aquí, 450 00:18:27,381 --> 00:18:29,850 però llavors no dit realment constant de temps perquè encara 451 00:18:29,850 --> 00:18:31,890 dependent sobre el total nombre d'elements 452 00:18:31,890 --> 00:18:34,500 que està introduint en l'estructura de dades. 453 00:18:34,500 --> 00:18:35,980 Però suposem que vam fer això. 454 00:18:35,980 --> 00:18:39,550 Permetin-me tornar a la pantalla per aquí. 455 00:18:39,550 --> 00:18:44,520 Permetin-me també aquest projecte aquí, clar la pantalla, i suposem que vaig fer això. 456 00:18:44,520 --> 00:18:49,300 Suposem que jo volia per inserir el nom Daven en en el meu estructura de dades. 457 00:18:49,300 --> 00:18:52,100 >> Així que vull inserir una cadena Daven en l'estructura de dades. 458 00:18:52,100 --> 00:18:54,370 Què passa si jo no faig servir un la taula de hash, però jo faig servir 459 00:18:54,370 --> 00:18:56,980 cosa que és més arbre-com com un arbre de la família, on 460 00:18:56,980 --> 00:18:59,670 vostè té alguna arrel en el superior i després nodes i fulles 461 00:18:59,670 --> 00:19:01,440 que van cap a baix i cap a fora. 462 00:19:01,440 --> 00:19:04,450 Suposem doncs, que jo que voleu inserir Daven de 463 00:19:04,450 --> 00:19:06,430 en el que és actualment una llista buida. 464 00:19:06,430 --> 00:19:09,780 Jo vaig a fer el següent: jo sóc crearà un node en aquesta família 465 00:19:09,780 --> 00:19:15,170 estructura de dades com arbre que s'assembla una mica com aquesta, cadascun dels quals 466 00:19:15,170 --> 00:19:19,640 rectangles ha, diguem, de moment 26 elements en els mateixos. 467 00:19:19,640 --> 00:19:21,650 I cadascuna de les cèl·lules en aquesta matriu que està passant 468 00:19:21,650 --> 00:19:23,470 per representar la lletra d'un alfabet. 469 00:19:23,470 --> 00:19:28,190 >> En concret, vaig a tractar aquest és A, després B, després C, després D, 470 00:19:28,190 --> 00:19:29,310 aquest d'aquí. 471 00:19:29,310 --> 00:19:32,940 Així que això va a amb eficàcia representar la lletra D. 472 00:19:32,940 --> 00:19:36,040 Però per inserir tots Daven de nomeno he de fer una mica més. 473 00:19:36,040 --> 00:19:37,840 Així que estic en primer lloc va a haixix, per així dir-ho. 474 00:19:37,840 --> 00:19:41,049 Vaig a mirar la primera lletra en Daven que és, òbviament, un D, 475 00:19:41,049 --> 00:19:42,840 i jo vaig a assignar un node que mira 476 00:19:42,840 --> 00:19:45,570 així- un gran rectangle gran suficient per adaptar-se a tot l'alfabet. 477 00:19:45,570 --> 00:19:47,140 >> Ara D es realitza. 478 00:19:47,140 --> 00:19:49,720 Ara A. D-A-V-I-N és la meta. 479 00:19:49,720 --> 00:19:51,220 Així que ara el que faré és això. 480 00:19:51,220 --> 00:19:54,027 Tan aviat com vaig començar avís D no hi ha punter allà. 481 00:19:54,027 --> 00:19:56,860 És valors d'escombraries en el moment, o podria inicialitzar a null. 482 00:19:56,860 --> 00:19:59,630 Però m'ho dius a mi seguir endavant amb aquesta idea de construir un arbre. 483 00:19:59,630 --> 00:20:04,260 Permetin-me assigno un altre d'aquests nodes que compta amb 26 elements en els mateixos. 484 00:20:04,260 --> 00:20:05,150 >> I saps què? 485 00:20:05,150 --> 00:20:09,130 Si això és només un node en la memòria que He creat amb malloc, utilitzant una estructura 486 00:20:09,130 --> 00:20:11,240 com aviat veurem, Jo faré esto-- 487 00:20:11,240 --> 00:20:14,450 Vaig a dibuixar una fletxa de el que va representar D baix 488 00:20:14,450 --> 00:20:15,860 a aquest nou node. 489 00:20:15,860 --> 00:20:19,240 I ara, primer la següent carta en nom de Daven, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- vaig a seguir endavant i dibuixar un altre node d'aquest tipus, 491 00:20:24,150 --> 00:20:30,150 mitjançant el qual, els elements de V, que aquí anem a sortejar crits instance--. 492 00:20:30,150 --> 00:20:31,020 No anem a dibuixar-hi. 493 00:20:31,020 --> 00:20:31,936 Es va a anar aquí. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> A continuació, anem a considera que es tracta de V. 496 00:20:35,712 --> 00:20:44,920 I llavors aquí anem a índex per sota de V en el que considerarem I. 497 00:20:44,920 --> 00:20:50,100 I a continuació, a partir d'aquí anem a anar tenir un d'aquests nodes aquí. 498 00:20:50,100 --> 00:20:52,930 I ara tenim una pregunta per contestar. 499 00:20:52,930 --> 00:20:57,840 Necessito alguna manera indicar que estem en el final de la cadena Daven. 500 00:20:57,840 --> 00:20:59,490 Així que podria deixar nul. 501 00:20:59,490 --> 00:21:02,670 >> Però el que si tenim Daven de nom complet també, que 502 00:21:02,670 --> 00:21:04,280 és, com hem dit, Davenport? 503 00:21:04,280 --> 00:21:06,970 I què si és Daven en realitat una subcadena, 504 00:21:06,970 --> 00:21:08,960 un prefix d'una cadena molt més temps? 505 00:21:08,960 --> 00:21:11,450 No podem permanentment dir res va 506 00:21:11,450 --> 00:21:14,410 anar-hi, perquè podíem Mai inseriu una paraula com Davenport 507 00:21:14,410 --> 00:21:15,840 en aquesta estructura de dades 508 00:21:15,840 --> 00:21:19,560 >> Llavors, ¿què podríem fer en el seu lloc és tractar cada un d'aquests elements 509 00:21:19,560 --> 00:21:22,170 com potser tenir dos elements dins d'ells. 510 00:21:22,170 --> 00:21:24,810 Un d'ells és un punter, de fet, com que he estat fent. 511 00:21:24,810 --> 00:21:27,100 Així que cadascuna d'aquestes caixes No és només una cèl·lula. 512 00:21:27,100 --> 00:21:29,855 Però, i si la part superior un-- de la part inferior 513 00:21:29,855 --> 00:21:32,230 serà nul, perquè no hi ha Davenport de moment. 514 00:21:32,230 --> 00:21:34,197 Què passa si el de dalt és algun valor especial? 515 00:21:34,197 --> 00:21:36,530 I serà una mica difícil de dibuixar aquesta mida. 516 00:21:36,530 --> 00:21:38,130 Però suposo que és només una marca de verificació. 517 00:21:38,130 --> 00:21:38,920 Comprovi. 518 00:21:38,920 --> 00:21:44,230 D-A-E-V-N és una cadena en aquesta estructura de dades. 519 00:21:44,230 --> 00:21:48,350 >> Mentrestant, si tingués més espai aquí, el que podia fer P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 i jo podria posar xec en el node que té la lletra T al final. 521 00:21:52,650 --> 00:21:55,460 Així que aquesta és una forma massiva complex d'aspecte d'estructura de dades. 522 00:21:55,460 --> 00:21:57,210 I la meva pròpia mà certament no ajuda. 523 00:21:57,210 --> 00:22:00,043 Però si volia inserir alguna cosa més, considerem el que faríem. 524 00:22:00,043 --> 00:22:03,370 Si volguéssim posar en David, ens agradaria seguir la mateixa lògica, D-A-V, 525 00:22:03,370 --> 00:22:08,802 però ara m'agradaria assenyalar a la propera element no des d'E, però de R a D. 526 00:22:08,802 --> 00:22:10,760 Així que serà més nodes d'aquest arbre. 527 00:22:10,760 --> 00:22:12,325 Tindrem l'anomenada malloc més. 528 00:22:12,325 --> 00:22:14,700 Però jo no vull fer una complet desastre d'aquesta imatge. 529 00:22:14,700 --> 00:22:17,710 Així que anem a veure un lloc que ha estat pre-formulat 530 00:22:17,710 --> 00:22:21,810 com aquest amb no punt, punt, punts, però només arrays abreujada. 531 00:22:21,810 --> 00:22:23,950 Però cada un dels nodes en aquest arbre aquí 532 00:22:23,950 --> 00:22:26,700 representa la mateixa cosa-- una matriu Raig de mida 26. 533 00:22:26,700 --> 00:22:28,860 >> O si volem ser ara realment adequada, el que 534 00:22:28,860 --> 00:22:30,790 si el nom d'algú com un apòstrof, anem a 535 00:22:30,790 --> 00:22:35,560 assumir que cada node té en realitat com 27 índexs en ella, no només 26. 536 00:22:35,560 --> 00:22:42,020 Així que això ara serà una dada estructura anomenada trie-- T-R-I-I. 537 00:22:42,020 --> 00:22:46,120 Un trie, que és suposadament històricament un nom intel·ligent per a un arbre 538 00:22:46,120 --> 00:22:49,040 que s'optimitza per recuperació, que per descomptat, 539 00:22:49,040 --> 00:22:50,870 s'escriu amb un I-I pel que és trie. 540 00:22:50,870 --> 00:22:52,710 Però aquesta és la història de la trie. 541 00:22:52,710 --> 00:22:55,860 >> Així que un trie és aquestes dades en forma d'arbre s'estructura com un arbre genealògic 542 00:22:55,860 --> 00:22:57,510 que en última instància es comporta d'aquesta manera. 543 00:22:57,510 --> 00:23:00,890 I aquí és només un altre exemple d'un tota munt de noms d'altres persones. 544 00:23:00,890 --> 00:23:03,540 Però la pregunta ara a la mà és el que té 545 00:23:03,540 --> 00:23:08,070 hem guanyat introduint possiblement una més complicada estructura de dades, i un, 546 00:23:08,070 --> 00:23:09,870 francament, que utilitza una gran quantitat de memòria. 547 00:23:09,870 --> 00:23:11,703 >> Perquè tot i que, en aquest moment, estic sol 548 00:23:11,703 --> 00:23:15,050 usant D's punter i A i V i Es i Ns, 549 00:23:15,050 --> 00:23:16,700 M'estic perdent una diables de gran quantitat de memòria. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Però on pas un recurs, Tendeixo a no recuperar un altre. 552 00:23:22,660 --> 00:23:26,020 Així que si estic gastant més espai, el que és probablement l'esperança? 553 00:23:26,020 --> 00:23:27,407 Que estic gastant menys què? 554 00:23:27,407 --> 00:23:28,240 AUDIÈNCIA: Menys temps. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Temps. 556 00:23:28,990 --> 00:23:30,320 Ara per què podria ser? 557 00:23:30,320 --> 00:23:33,880 Bé, quina és la inserció temps, en termes de gran O ara, 558 00:23:33,880 --> 00:23:37,660 d'un nom com Daven o Davenport o David? 559 00:23:37,660 --> 00:23:39,340 Bé, Daven era cinc passos. 560 00:23:39,340 --> 00:23:42,350 Davenport seria nou passos, per la qual cosa seria una mica més passos. 561 00:23:42,350 --> 00:23:44,250 David seria cinc passos també. 562 00:23:44,250 --> 00:23:47,230 Així que aquests són de formigó números, però segur que hi ha 563 00:23:47,230 --> 00:23:49,550 un límit superior en el longitud del nom d'algú. 564 00:23:49,550 --> 00:23:52,240 I, en efecte, en el problema grups de cinc especificació, 565 00:23:52,240 --> 00:23:54,050 proposarem que és una cosa 566 00:23:54,050 --> 00:23:55,470 això és 40 caràcters i tants. 567 00:23:55,470 --> 00:23:58,180 >> Sent realistes, ningú té un nom infinitament llarg, 568 00:23:58,180 --> 00:24:01,542 que és dir que la longitud d'una nom o la longitud d'una cadena que poden 569 00:24:01,542 --> 00:24:03,750 tenir certa l'estat de estructura és discutible què? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 És constant. 572 00:24:06,250 --> 00:24:06,430 Dreta? 573 00:24:06,430 --> 00:24:09,310 Pot ser que sigui una gran constant com 40 i tants anys, però és constant. 574 00:24:09,310 --> 00:24:13,752 I no té dependència de la quantitat de altres noms pertanyen a aquesta estructura de dades. 575 00:24:13,752 --> 00:24:15,460 En altres paraules, si volgut inserir ara 576 00:24:15,460 --> 00:24:20,540 Colton o Gabriel o Rob o Zamyla o Alison o Belinda o qualsevol altre nom 577 00:24:20,540 --> 00:24:23,940 des del personal en aquestes dades estructura, és el temps d'execució 578 00:24:23,940 --> 00:24:26,750 d'inserir altres noms serà en absolut afectat 579 00:24:26,750 --> 00:24:30,220 per la forma en molts altres elements són en l'estructura de dades ja? 580 00:24:30,220 --> 00:24:31,040 Que no és. 581 00:24:31,040 --> 00:24:31,540 Dreta? 582 00:24:31,540 --> 00:24:36,150 Com que estem fent servir de manera efectiva aquesta taula hash multicapa. 583 00:24:36,150 --> 00:24:38,280 I el temps d'execució de qualsevol d'aquestes operacions 584 00:24:38,280 --> 00:24:41,510 depèn no del nombre de elements que estan en l'estructura de dades 585 00:24:41,510 --> 00:24:43,090 o que va amb el temps per estar en l'estructura de dades, 586 00:24:43,090 --> 00:24:44,714 però en la longitud del que específicament? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> La cadena ser inserit, el que ho fa fer 589 00:24:49,200 --> 00:24:52,580 aquest asimptòticament constant gran O temps-- d'un. 590 00:24:52,580 --> 00:24:54,720 I, francament, només en el món real, aquest 591 00:24:54,720 --> 00:24:58,380 significa inserir el nom de Daven presa com cinc passos, o Davenport 09:00 592 00:24:58,380 --> 00:25:00,100 David passos, o cinc passos. 593 00:25:00,100 --> 00:25:03,071 Això és bastant maleït petits temps de funcionament. 594 00:25:03,071 --> 00:25:05,320 I, de fet, aquesta és una molt bona cosa, especialment quan 595 00:25:05,320 --> 00:25:08,126 no és dependent sobre el total nombre d'elements d'allà. 596 00:25:08,126 --> 00:25:10,500 Llavors, ¿com podríem aplicar aquesta tipus d'estructura en el codi? 597 00:25:10,500 --> 00:25:12,900 És una mica més complex, però tot i així és 598 00:25:12,900 --> 00:25:15,050 només una aplicació de blocs de construcció bàsics. 599 00:25:15,050 --> 00:25:17,830 Vaig a redefinir ens node de la manera següent: 600 00:25:17,830 --> 00:25:21,100 bool anomenada paraula-- i això que podria dir qualsevol cosa. 601 00:25:21,100 --> 00:25:23,970 Però el bool representa el vaig dibuixar com una marca de verificació. 602 00:25:23,970 --> 00:25:24,490 Sí. 603 00:25:24,490 --> 00:25:26,720 Aquest és el final d'una cadena en aquesta estructura de dades. 604 00:25:26,720 --> 00:25:30,702 >> I, per descomptat, l'estrella node no s'està referint als nens. 605 00:25:30,702 --> 00:25:32,410 I, de fet, de la mateixa manera que un arbre de la família, vostè 606 00:25:32,410 --> 00:25:34,370 consideraria els nodes que estan penjant 607 00:25:34,370 --> 00:25:36,920 de la part inferior d'alguns dels pares element per a ser nens. 608 00:25:36,920 --> 00:25:40,510 I perquè els nens es van a ser una matriu de 27, el 27 de 609 00:25:40,510 --> 00:25:41,680 només estar per apòstrof. 610 00:25:41,680 --> 00:25:43,390 Anem a classificar de cas especial que. 611 00:25:43,390 --> 00:25:45,400 Així que vostè pot tenir certa noms amb apòstrofs. 612 00:25:45,400 --> 00:25:47,399 Potser fins i tot hauria guió anar-hi, però vostè 613 00:25:47,399 --> 00:25:50,330 veure a la pàg conjunt 5, que només l'atenció sobre les lletres i apòstrofs. 614 00:25:50,330 --> 00:25:52,990 >> I llavors, com fa vostè representa la pròpia estructura de dades? 615 00:25:52,990 --> 00:25:56,454 Com es representa a l'arrel d'aquest trie, per dir-ho? 616 00:25:56,454 --> 00:25:59,620 Bé, de la mateixa manera que amb una llista enllaçada, que necessitarà un punter al primer element. 617 00:25:59,620 --> 00:26:04,270 Amb un trie només en té un punter a l'arrel d'aquest trie. 618 00:26:04,270 --> 00:26:07,290 I a partir d'allí es pot hash de el seu camí cap avall més i més profund 619 00:26:07,290 --> 00:26:10,460 a tots els altres nodes en l'estructura. 620 00:26:10,460 --> 00:26:13,440 Així que simplement amb aquesta llauna representem que estructura. 621 00:26:13,440 --> 00:26:15,877 >> Ara Meanwhile-- Oh, pregunta. 622 00:26:15,877 --> 00:26:17,220 >> AUDIÈNCIA: Quina és la paraula bool? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: paraula Bool és només aquesta encarnació C 624 00:26:20,490 --> 00:26:22,920 del que he descrit en aquest quadre d'aquí, quan 625 00:26:22,920 --> 00:26:26,000 Vaig començar a dividir cada un dels elements de l'array en dues peces. 626 00:26:26,000 --> 00:26:27,600 Un és un punter al següent node. 627 00:26:27,600 --> 00:26:30,280 L'altra ha d'haver alguna cosa així com una casella de verificació 628 00:26:30,280 --> 00:26:33,770 a dir que sí, que hi ha una Daven paraula que acaba aquí, 629 00:26:33,770 --> 00:26:35,610 perquè no volem, de moment, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Tot i que a Dave serà una paraula legítima, que no està en el trie 631 00:26:39,320 --> 00:26:39,830 encara. 632 00:26:39,830 --> 00:26:40,950 I D no és una paraula. 633 00:26:40,950 --> 00:26:42,770 I D-A no és una paraula o un nom. 634 00:26:42,770 --> 00:26:45,020 Així que la marca de verificació indica només una vegada que 635 00:26:45,020 --> 00:26:48,190 colpejar aquest node és el trajectòria anterior de caràcters 636 00:26:48,190 --> 00:26:50,700 en realitat una cadena que ha inserit. 637 00:26:50,700 --> 00:26:53,660 Així que això és tot el bool no està fent per nosaltres. 638 00:26:53,660 --> 00:26:55,500 >> Alguna altra pregunta sobre intents? 639 00:26:55,500 --> 00:26:56,215 Sí. 640 00:26:56,215 --> 00:26:58,035 >> AUDIÈNCIA: Quina és la coincidència? 641 00:26:58,035 --> 00:26:59,945 Què passa si vostè té un Dave i un Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Perfecte. 643 00:27:00,820 --> 00:27:02,580 Què passa si vostè té un Dave i un Daven? 644 00:27:02,580 --> 00:27:06,240 Així que si inserim, dir un sobrenom, per David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Això és realment molt simple. 647 00:27:08,700 --> 00:27:10,325 Així que només tindrem quatre passes. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-I. I què és el que he de fer una vegada que vaig arribar a quart node? 650 00:27:15,847 --> 00:27:16,680 Només va a comprovar. 651 00:27:16,680 --> 00:27:18,000 Ja està bo per anar. 652 00:27:18,000 --> 00:27:18,840 Fet. 653 00:27:18,840 --> 00:27:19,750 Quatre passos. 654 00:27:19,750 --> 00:27:21,590 Temps constant asimptòtica. 655 00:27:21,590 --> 00:27:26,300 I ara hem indicat que tant de Dave i Daven són cadenes en l'estructura. 656 00:27:26,300 --> 00:27:27,710 Així que no és un problema. 657 00:27:27,710 --> 00:27:30,200 I noti com la presència de Daven no fer-ho 658 00:27:30,200 --> 00:27:34,750 prendre qualsevol temps més o menys temps per Dave i viceversa. 659 00:27:34,750 --> 00:27:36,000 >> Llavors, ¿què més podem fer ara? 660 00:27:36,000 --> 00:27:40,680 Hem utilitzat aquesta metàfora abans de safates que representa una mica. 661 00:27:40,680 --> 00:27:43,380 Però resulta que un pila de safates és en realitat 662 00:27:43,380 --> 00:27:47,187 demostratiu d'un altre abstracte de dades type-- una estructura de dades de nivell superior 663 00:27:47,187 --> 00:27:49,770 que al final del dia és només com una matriu o una llista enllaçada 664 00:27:49,770 --> 00:27:50,970 o alguna cosa més mundà. 665 00:27:50,970 --> 00:27:53,270 Però és una més interessant concepte conceptual. 666 00:27:53,270 --> 00:27:56,440 Una pila, com aquests safates aquí a Mather, 667 00:27:56,440 --> 00:27:58,750 es poden anomenar només que-- una pila. 668 00:27:58,750 --> 00:28:02,540 >> I en aquest tipus d'estructura de dades vostè té dues operations-- 669 00:28:02,540 --> 00:28:05,880 vostè té una trucada empenta per afegint alguna cosa a la pila, 670 00:28:05,880 --> 00:28:08,320 com posar una altra safata la part posterior a la part superior de la pila. 671 00:28:08,320 --> 00:28:11,350 I a continuació, el pop, el que significa prendre la més alta fora de la safata. 672 00:28:11,350 --> 00:28:16,210 Però el que és clau sobre una pila és que que té aquesta característica curiosa. 673 00:28:16,210 --> 00:28:19,560 A mesura que el personal del menjador són la reordenació de les safates per a la pròxima menjar, 674 00:28:19,560 --> 00:28:21,380 el que serà cert sobre com els estudiants 675 00:28:21,380 --> 00:28:22,856 interactuar amb aquesta estructura de dades? 676 00:28:22,856 --> 00:28:24,480 AUDIÈNCIA: Van a esclatar un fos. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Van a pop un fos, esperem que la part superior. 678 00:28:26,550 --> 00:28:28,910 En cas contrari, és només una mica estúpid d'anar tot el camí fins al fons. 679 00:28:28,910 --> 00:28:29,070 Dreta? 680 00:28:29,070 --> 00:28:31,620 L'estructura de dades en realitat no permet a agafar la safata inferior, almenys, 681 00:28:31,620 --> 00:28:32,520 fàcilment. 682 00:28:32,520 --> 00:28:35,040 Així que hi ha aquesta curiosa propietat d'una pila 683 00:28:35,040 --> 00:28:39,730 que l'últim element és serà el primer a sortir. 684 00:28:39,730 --> 00:28:43,400 I els informàtics anomenen LIFO-- aquest últim a entrar, primer a sortir. 685 00:28:43,400 --> 00:28:45,540 I el que realment té aplicacions interessants. 686 00:28:45,540 --> 00:28:50,090 No és necessàriament tan obvi com alguns altres, però poden, de fet, ser útil, 687 00:28:50,090 --> 00:28:54,040 i pot, de fet, ser implementada en un parell de maneres diferents. 688 00:28:54,040 --> 00:28:58,550 >> Així que un, i de fet, deixar que a mi, no a submergir-se en això. 689 00:28:58,550 --> 00:28:59,860 Anem a fer això en el seu lloc. 690 00:28:59,860 --> 00:29:03,700 Fem una ullada a un que és gairebé la mateixa idea, però és una mica més just. 691 00:29:03,700 --> 00:29:04,200 Dreta? 692 00:29:04,200 --> 00:29:07,560 Si vostè és un d'aquests nois ventilador o noies que realment li agrada els productes d'Apple 693 00:29:07,560 --> 00:29:10,130 i es va despertar a les 3:00 am a alinear-se en algun magatzem 694 00:29:10,130 --> 00:29:14,150 per obtenir la més recent iPhone, podria haver-hi cua cap amunt com això. 695 00:29:14,150 --> 00:29:15,800 >> Ara una cua és nomenat molt deliberadament. 696 00:29:15,800 --> 00:29:18,190 És una línia perquè no hi ha alguns justos amb ell. 697 00:29:18,190 --> 00:29:18,690 Dreta? 698 00:29:18,690 --> 00:29:21,690 Seria tipus de aspirat si tens va arribar primer a la botiga d'Apple 699 00:29:21,690 --> 00:29:25,700 però vostè és efectivament la més inferior safata pel fet que els empleats d'Apple després 700 00:29:25,700 --> 00:29:28,189 pop de l'última persona que en realitat es va posar en línia. 701 00:29:28,189 --> 00:29:31,230 Així piles i cues, tot i funcionalment són tipus de la same-- 702 00:29:31,230 --> 00:29:33,105 és només aquesta col·lecció dels recursos que és 703 00:29:33,105 --> 00:29:36,210 creixerà i shrink-- hi aquest aspecte ser justos amb ell, 704 00:29:36,210 --> 00:29:39,634 almenys en el món real, on les operacions que exerceixen 705 00:29:39,634 --> 00:29:40,800 són fonamentalment diferents. 706 00:29:40,800 --> 00:29:43,360 A stack-- una cua rather-- es diu que té 707 00:29:43,360 --> 00:29:45,320 dues operacions: n de cues i cues d. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 O vostè pot trucar a ells qualsevol nombre de coses. 710 00:29:48,090 --> 00:29:50,770 Però el que desitja és capturar la noció que un és l'addició de 711 00:29:50,770 --> 00:29:53,230 i un està en última instància restar. 712 00:29:53,230 --> 00:29:58,840 >> Ara sota el capó, tant la pila i una cua podria ser implementat, com? 713 00:29:58,840 --> 00:30:01,390 No entrarem en el codi de perquè el nivell més alt 714 00:30:01,390 --> 00:30:03,387 és una espècie d'idea més òbvia. 715 00:30:03,387 --> 00:30:04,470 Vull dir, ¿què fan els éssers humans? 716 00:30:04,470 --> 00:30:07,030 Si jo sóc la primera persona a l'Apple Guardar i aquesta és la porta d'entrada, 717 00:30:07,030 --> 00:30:08,130 vostè sap, jo vaig a ser aquí. 718 00:30:08,130 --> 00:30:09,750 I de la persona va a ser aquí. 719 00:30:09,750 --> 00:30:11,500 I de la persona va a ser aquí. 720 00:30:11,500 --> 00:30:13,792 Llavors, ¿quina estructura de dades es presta a una cua? 721 00:30:13,792 --> 00:30:14,542 >> AUDIÈNCIA: Una cua. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: Bé, una cua. 723 00:30:15,667 --> 00:30:16,390 És clar. 724 00:30:16,390 --> 00:30:16,920 Quina altra cosa? 725 00:30:16,920 --> 00:30:17,600 >> AUDIÈNCIA: Una llista enllaçada. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: Una vinculat llista que podria implementar. 727 00:30:18,990 --> 00:30:22,500 I una llista enllaçada és agradable perquè llavors que pot créixer arbitràriament llarga en oposició 728 00:30:22,500 --> 00:30:24,880 a tenir un nombre fix de la gent a la botiga. 729 00:30:24,880 --> 00:30:27,030 Però potser un nombre fix de llocs és legítim. 730 00:30:27,030 --> 00:30:30,350 Perquè si només tenen com a 20 iPhones en el primer dia, potser 731 00:30:30,350 --> 00:30:33,930 que només necessiten una matriu de mida 20 per representar aquesta cua, que 732 00:30:33,930 --> 00:30:37,070 és només per dir ara, una vegada que vam començar a parlar sobre aquests problemes de més alt nivell, 733 00:30:37,070 --> 00:30:38,890 vostè pot posar-lo en pràctica en qualsevol nombre de maneres. 734 00:30:38,890 --> 00:30:42,030 I hi ha probablement només va a ser una solució de compromís en l'espai i el temps 735 00:30:42,030 --> 00:30:43,950 o simplement en la seva pròpia complexitat del codi. 736 00:30:43,950 --> 00:30:45,380 >> Què passa amb una pila? 737 00:30:45,380 --> 00:30:48,190 Bé, una pica, hem vist també podria ser només aquestes safates. 738 00:30:48,190 --> 00:30:50,007 I es podria implementar aquesta una matriu. 739 00:30:50,007 --> 00:30:53,090 Però en algun moment si s'utilitza una matriu, el que va a passar amb les safates 740 00:30:53,090 --> 00:30:54,173 vostè està tractant de posar a terra? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Bé. 743 00:30:55,670 --> 00:30:57,490 Vostè només va a ser capaç d'anar tan alt. 744 00:30:57,490 --> 00:31:00,156 I crec que en Mather són realment encastada en aquesta obertura. 745 00:31:00,156 --> 00:31:01,950 Així que de fet, és gairebé com Mather està utilitzant 746 00:31:01,950 --> 00:31:03,783 una matriu de mida fixa, perquè només es pot 747 00:31:03,783 --> 00:31:08,302 encaixar tantes safates en què l'obertura a la paret per sota dels genolls de la gent. 748 00:31:08,302 --> 00:31:10,010 I el que podria ser diu que és una matriu, 749 00:31:10,010 --> 00:31:14,300 però sens dubte podríem posar en pràctica que més en general amb una llista enllaçada. 750 00:31:14,300 --> 00:31:16,390 >> Bé, què passa amb una altra estructura de dades? 751 00:31:16,390 --> 00:31:18,760 Permetin-me llevo una altra visual aquí. 752 00:31:18,760 --> 00:31:24,710 Una cosa així com què tal aquest d'aquí? 753 00:31:24,710 --> 00:31:28,920 Per què podria ser útil per no haver una cosa tan elegant com un trie, que 754 00:31:28,920 --> 00:31:32,370 vam veure tenia aquests molt amplis nodes, cadascun dels quals està en una matriu? 755 00:31:32,370 --> 00:31:35,740 Però i si fem alguna cosa més simplement, com un arbre de família de l'escola vella, 756 00:31:35,740 --> 00:31:38,110 cada un dels nodes aquí s'acaba d'emmagatzemar un nombre. 757 00:31:38,110 --> 00:31:42,180 En lloc d'un nom o un descendent s'acaba d'emmagatzemar un nombre com aquest. 758 00:31:42,180 --> 00:31:45,250 >> Bé, l'argot que fem servir a estructures de dades és dos paï- 759 00:31:45,250 --> 00:31:49,510 i arbres, on un trie, de nou, és només un els nodes són matrius, 760 00:31:49,510 --> 00:31:51,680 continua sent el que et poden utilitzar des de l'escola primària 761 00:31:51,680 --> 00:31:53,860 quan va fer una família fulles i l'arrel tree-- 762 00:31:53,860 --> 00:31:57,250 de l'arbre i els nens de la els pares i germans dels mateixos. 763 00:31:57,250 --> 00:32:03,670 I podríem posar en pràctica un arbre, per exemple, com simplement com això. 764 00:32:03,670 --> 00:32:07,420 Un arbre, si com un node, una de aquests cercles que té un nombre, 765 00:32:07,420 --> 00:32:09,947 no tindrà un punter, sinó dos. 766 00:32:09,947 --> 00:32:11,780 I tan aviat com vostè afegeix un segon punter, 767 00:32:11,780 --> 00:32:13,905 en realitat pot ara fer una espècie de les dades de dues dimensions 768 00:32:13,905 --> 00:32:14,780 estructures en la memòria. 769 00:32:14,780 --> 00:32:16,660 Igual que una de dues dimensions matriu, pot 770 00:32:16,660 --> 00:32:18,904 tenir classe de dues dimensions llistes enllaçades, però els 771 00:32:18,904 --> 00:32:20,820 que segueixen un patró on no hi ha cicles. 772 00:32:20,820 --> 00:32:24,487 És realment un arbre amb una manera avi fins aquí i després 773 00:32:24,487 --> 00:32:27,320 alguns pares i els nens i néts i besnéts. 774 00:32:27,320 --> 00:32:28,370 i així successivament. 775 00:32:28,370 --> 00:32:32,390 >> Però el que és realment bo d'això també, només per fer broma amb una mica de codi, 776 00:32:32,390 --> 00:32:35,370 el record de la recursivitat un temps enrere, per la qual cosa 777 00:32:35,370 --> 00:32:38,220 s'escriu una funció que diu a si mateix. 778 00:32:38,220 --> 00:32:41,140 Aquesta és una bella oportunitat implementar alguna cosa 779 00:32:41,140 --> 00:32:42,920 com la recursivitat, perquè consideren que aquest. 780 00:32:42,920 --> 00:32:43,860 >> Aquest és un arbre. 781 00:32:43,860 --> 00:32:48,040 I jo he estat una mica anal amb com Vaig posar els números sencers al carrer. 782 00:32:48,040 --> 00:32:51,020 Tant és així que té una especial nom-- un arbre de cerca binària. 783 00:32:51,020 --> 00:32:53,460 Ara que hem escoltat de binari cercar, però podeu 784 00:32:53,460 --> 00:32:55,180 treballar cap enrere des del nom d'aquesta cosa? 785 00:32:55,180 --> 00:32:59,280 Quin és el patró de la forma en què inserit els nombres enters a aquest arbre? 786 00:32:59,280 --> 00:33:00,696 No és arbitrari. 787 00:33:00,696 --> 00:33:01,570 Hi ha algun patró. 788 00:33:01,570 --> 00:33:02,090 Sí. 789 00:33:02,090 --> 00:33:03,370 >> AUDIÈNCIA: Els més petits de l'esquerra. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Sí. 791 00:33:03,690 --> 00:33:05,062 Els més petits estan a l'esquerra. 792 00:33:05,062 --> 00:33:06,270 Altres més grans estan a la dreta. 793 00:33:06,270 --> 00:33:12,940 De tal manera que un enunciat veritable és un pare és més gran que el seu fill esquerre, 794 00:33:12,940 --> 00:33:14,850 però menor que el seu fill dret. 795 00:33:14,850 --> 00:33:17,750 I això només és encara una definició verbal recursiva 796 00:33:17,750 --> 00:33:20,500 perquè es pot aplicar aquest mateixa lògica a cada node 797 00:33:20,500 --> 00:33:23,080 I només fons terme, un cas base si 798 00:33:23,080 --> 00:33:25,740 ho farà, quan va colpejar una de les fulles, per així dir-ho, 799 00:33:25,740 --> 00:33:28,580 on una llicència no té fills més. 800 00:33:28,580 --> 00:33:30,614 >> Ara, com pot vostè trobar al número 44? 801 00:33:30,614 --> 00:33:32,280 Es podria començar a l'arrel i dir, hm. 802 00:33:32,280 --> 00:33:35,690 55 no és 44 així que vull anar dret o vull anar a l'esquerra? 803 00:33:35,690 --> 00:33:37,190 Bé, òbviament vol anar esquerra. 804 00:33:37,190 --> 00:33:40,060 I així és com el telèfon exemple del llibre en la recerca binària 805 00:33:40,060 --> 00:33:41,099 de manera més general. 806 00:33:41,099 --> 00:33:43,390 Però estem implementar ara una mica més de forma dinàmica 807 00:33:43,390 --> 00:33:45,339 d'una matriu podria permetre. 808 00:33:45,339 --> 00:33:48,130 I de fet, si vols buscar en el codi, a primera vista segur. 809 00:33:48,130 --> 00:33:49,671 S'assembla a un munt de línies. 810 00:33:49,671 --> 00:33:51,220 Però és meravellosament simple. 811 00:33:51,220 --> 00:33:54,490 Si desitja implementar una funció crida de recerca el propòsit a la vida 812 00:33:54,490 --> 00:33:57,290 és la recerca d'un valor com n, un enter, 813 00:33:57,290 --> 00:34:01,756 i ja està aprovada en una pointer-- un punter al node de les arrels, 814 00:34:01,756 --> 00:34:04,380 més aviat, d'aquest arbre des del qual es pot accedir a tota la resta, 815 00:34:04,380 --> 00:34:08,850 notar com voltes vostè pot aplicar la lògica. 816 00:34:08,850 --> 00:34:10,880 Si l'arbre és nul, òbviament, no hi és. 817 00:34:10,880 --> 00:34:11,880 Anem a tornar falsa. 818 00:34:11,880 --> 00:34:12,000 Dreta? 819 00:34:12,000 --> 00:34:14,040 Si et mà que res, no hi ha res allà. 820 00:34:14,040 --> 00:34:17,900 >> Else, si n és menor que arbre fletxa N-- ara fletxa n, 821 00:34:17,900 --> 00:34:20,670 Recordem introduir súper breument l'altre dia, 822 00:34:20,670 --> 00:34:25,100 i això només vol dir de-referència el punter i mirar el camp denominat n. 823 00:34:25,100 --> 00:34:27,690 Per tant, vol dir anar-hi i mirar el camp denominat n. 824 00:34:27,690 --> 00:34:33,810 Així que si n, el valor que et donen, és menys que el valor en el nombre enter arbres, 825 00:34:33,810 --> 00:34:35,449 ¿On vols anar? 826 00:34:35,449 --> 00:34:36,389 A l'esquerra. 827 00:34:36,389 --> 00:34:37,780 >> Així notar la recursivitat. 828 00:34:37,780 --> 00:34:39,860 Estic returning-- no és cert. 829 00:34:39,860 --> 00:34:40,989 No és fals. 830 00:34:40,989 --> 00:34:45,670 Estic tornant sigui quina sigui la resposta és a partir d'una crida a mi mateix, que passa 831 00:34:45,670 --> 00:34:50,100 1 n de nou, que és redundant, però el que és una mica diferent ara? 832 00:34:50,100 --> 00:34:51,989 Com estic fent el problema més petit? 833 00:34:51,989 --> 00:34:54,920 Estic passant com a segon argument, no l'arrel de l'arbre, 834 00:34:54,920 --> 00:34:59,616 però el fill esquerre en aquest cas. 835 00:34:59,616 --> 00:35:00,990 Així que estic passant al fill esquerre. 836 00:35:00,990 --> 00:35:04,720 >> Mentrestant, si n és més gran que el node que actualment estic mirant, 837 00:35:04,720 --> 00:35:06,690 Jo busco el costat dret. 838 00:35:06,690 --> 00:35:10,880 En cas contrari, si l'arbre no és nul, i si l'element no està a l'esquerra 839 00:35:10,880 --> 00:35:13,240 i no és a la dreta, el que és meravellosament el cas? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 En realitat ens hem trobat en el node pregunta, i així tornem cert. 842 00:35:18,440 --> 00:35:21,490 >> Així que acabem de esgarrapat la superfície ara algunes d'aquestes estructures de dades. 843 00:35:21,490 --> 00:35:24,370 En el problema va fixar cinc podràs explorar aquests encara més lluny, 844 00:35:24,370 --> 00:35:27,250 i se li donarà el seu disseny elecció de com anar sobre això. 845 00:35:27,250 --> 00:35:30,250 El que m'agradaria arribar a la conclusió és només un segon teaser de 30 846 00:35:30,250 --> 00:35:32,080 del que espera a la setmana que ve i més enllà. 847 00:35:32,080 --> 00:35:35,390 >> A mesura que begin-- afortunadament et poden think-- la nostra transició lentament 848 00:35:35,390 --> 00:35:38,680 del món de la C i la més baixa detalls d'implementació de nivell, 849 00:35:38,680 --> 00:35:42,090 a un món en el qual podem prendre per fet que algú pretén 850 00:35:42,090 --> 00:35:44,010 implementat aquestes dades estructures per a nosaltres, 851 00:35:44,010 --> 00:35:47,570 i anem a començar a entendre el significa el món real de la implementació 852 00:35:47,570 --> 00:35:50,560 programes basats en la web i llocs web de forma més general 853 00:35:50,560 --> 00:35:52,910 i també la pròpia seguretat implicacions que hem només 854 00:35:52,910 --> 00:35:54,850 començat a gratar la superfície de. 855 00:35:54,850 --> 00:35:57,320 Això és el que ens espera en els dies per venir. 856 00:35:57,320 --> 00:36:00,480 >> [REPRODUCCIÓ DE VÍDEO] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Ell Vi amb un missatge, amb un protocol de totes les seves. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Ell va venir a un món de cruel tallafocs, routers indiferents, 861 00:36:30,894 --> 00:36:33,368 i perills molt pitjors que la mort. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 És ràpid. 864 00:36:36,236 --> 00:36:37,980 És fort. 865 00:36:37,980 --> 00:36:42,830 Ell és TCP / IP, i que té la seva adreça. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Guerrers de la xarxa." 868 00:36:48,074 --> 00:36:49,660 [FI REPRODUCCIÓ DE VÍDEO] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: Si ve la setmana que ve. 870 00:36:50,910 --> 00:36:51,880 Ens veiem llavors. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [REPRODUCCIÓ DE VÍDEO] 873 00:36:56,060 --> 00:36:59,240 -I Ara, "Pensaments profunds" per Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Comença sempre conferències amb: "Molt bé." 876 00:37:05,820 --> 00:37:08,750 Per què no, "Aquí està la solució al conjunt de problemes d'aquesta setmana " 877 00:37:08,750 --> 00:37:12,180 o "Estem donant a tots vostès una A?" 878 00:37:12,180 --> 00:37:13,380 [El] 879 00:37:13,380 --> 00:37:15,530 [FI REPRODUCCIÓ DE VÍDEO]