[REPRODUCCIÓ DE MÚSICA] DAVID Malan: Aquest és CS50. I això és alhora el principi i el end-- com literally-- gairebé el final de la setmana 6. 

Jo vaig pensar en compartir un mica d'un fet divertit. He tirat això des d'un conjunt de dades del semestre passat. Vostè pot recordar que li demanem a cada forma conjunt p si has vist en línia o si vostè ha assistit a persona. I aquí hi ha les dades. Així que estava molt predictible avui. Però nosaltres volíem passar una mica de temps amb vostè, però. Algú vol conjecturar per què això gràfic és tan jaggy, dalt a baix, dalt a baix, tan consistentment? Què fer cada un dels pics i depressions representen? 

AUDIÈNCIA: [inaudible] DAVID Malan: En efecte. I més divertida, Déu no ho vulgui, tenim una conferència en un divendres l'inici del semestre, això és el que succeeixi. Així que avui, participem en una mica Més informació sobre les estructures de dades. I per donar-li més d'un sòlid model mental dels problemes a les cinc, que ara està fora. Errors d'ortografia, en el qual, anem a de lliurar un arxiu de text uns 100.000 a més de les paraules en anglès, i vostè va a tenir per trobar la manera de carregar ells intel·ligentment en la memòria, a la memòria RAM, l'ús d'algunes dades estructura de la seva elecció. 

Ara bé, una estructura d'aquest tipus de dades podria ser, però probablement no hauria de ser, la llista enllaçada bastant simplista, que es va introduir l'última vegada. I una llista enllaçada tenia almenys un avantatge sobre una matriu. Quin és un dels avantatges de una llista enllaçada discutible? 

AUDIÈNCIA: Inserció. 

DAVID Malan: Inserció. Què vols dir amb això? 

AUDIÈNCIA: En qualsevol lloc al llarg de la llista de [inaudible]. 

DAVID Malan: Good. Així que vostè pot inserir un element sempre que sigui que vols a la meitat de la llista sense haver de barrejar res, que vam arribar a la conclusió, en la nostra classificació discussions, no és necessàriament una bona cosa, perquè es necessita temps per navegar realitat tots aquests éssers humans cap a l'esquerra o dreta. I així, amb una llista enllaçada, pot simplement assignar amb malloc, un nou node, i després actualitzar un parell de pointers-- dos, tres operacions max-- i som capaços de ranura algú en qualsevol lloc en una llista. 

¿Quina altra cosa era avantatjós sobre una llista enllaçada? Sí? 

AUDIÈNCIA: [inaudible] DAVID Malan: Perfecte. Perfecte. És molt dinàmic. I això que no estàs cometent, per endavant, fins a cert grandària fixa tros de memòria, de la mateixa manera que vostè hauria a amb una matriu, l'alça dels quals és que es pot assignar nodes només en la demanda d'aquesta manera utilitzant només la quantitat d'espai com que realment necessita. A diferència d'una matriu, que et poden assignar accidentalment massa poc. I llavors només va a ser un dolor al coll reassignar una nova matriu més gran, copiar a tot estirar, alliberar la matriu d'edat, i després passar sobre el seu negoci. O pitjor encara, és possible assignar de manera més memòria de la que realment es necessita, i pel que tindrem un molt matriu escassament poblades, per així dir-ho. 

Així que una llista enllaçada que dóna a aquests avantatges de dinamisme i flexibilitat amb insercions i delecions. Però sens dubte que ha d'haver un preu que es paga. De fet, un dels temes explorat en concurs zero era un parell de les compensacions que hem vist fins al moment. Així que el que és un preu pagat o per un la baixa d'una llista enllaçada? Sí. 

AUDIÈNCIA: No hi ha accés aleatori. 

DAVID Malan: No hi ha accés aleatori. Però a qui li importa? Accés aleatori no sona convincent. 

AUDIÈNCIA: [inaudible] DAVID Malan: Exactament. Si vostè vol tenir una certa algorithm-- i que em faci realitat proposo recerca binària, en particular, que és un que hem utilitzat bastant bit-- si vostè no té accés a l'atzar, no es pot fer així de simple aritmètica de trobar com l'element mitjà i saltar a la dreta a la mateixa. En el seu lloc, ha de començar pel primer element i linealment buscar des de l'esquerra a dreta si vols trobar el mitjà o qualsevol altre element. 

AUDIÈNCIA: Probablement té més memòria. 

DAVID Malan: Presa més memòria. On és aquest addicional cost que ve de la memòria? 

AUDIÈNCIA: [inaudible] DAVID Malan: Exactament. En aquest cas aquí, vam tenir una llista enllaçada per a enters, i no obstant això, estem duplicant la quantitat de memòria necessitem també per l'emmagatzematge d'aquestes punters. Ara menys d'un gran problema ja les seves estructures es fan més grans i vostè està emmagatzemant no és un nombre, però potser un estudiant o algun altre objecte. Però el punt segueix sent dubte. I pel que un nombre de les operacions en llistes enllaçades van ser cridats eren grans O de N-- lineal. Coses com la inserció o recerca o eliminació en cas d'un element va passar a ser al final de la llista si està ordenada o no. 

A vegades pot ser que tinguis sort i en fora de manera més baixos en aquestes operacions També podria ser la constant de temps si estàs sempre mirant al primer element, per exemple. Però en última instància, ens vam prometre per aconseguir el sant grial d'estructures de dades, o alguns dels mateixos aproximació, per mitjà de la constant de temps. Podem trobar elements o afegir elements o eliminar elements d'una llista? Ens veurem molt aviat. I resulta que un dels mecanismes que estem va a començar a utilitzar avui en dia, l'ús anual de P posat 5, en realitat és bastant familiar. Per exemple, si es tracta d'un munt de llibres d'examen, cadascun dels quals té un estudiant de primer nom i cognom a ell, i jo els recull de la al final d'un examen, i són tots bastant tant en un ordre aleatori, i volem anar sobre la classificació aquests exàmens perquè una vegada classificades és només molt més fàcil i més ràpid a lliurar-los de tornada als estudiants en ordre alfabètic. Quins serien els seus instints per a una pila d'exàmens d'aquest tipus? 

Bé, si ets com jo, podria veure que aquest és m, així que em vaig a posar això en una espècie de, si aquest és el meu taula o el meu pis on Estic estenent coses fora-- o el meu arsenal realmente-- Jo podria posar tota la Sra allà. Oh. Heus aquí una A. Així que podria Com posar els d'aquí. Oh. Aquí hi ha una altra A. Vaig posar que aquí. Aquí hi ha una Z. Hi ha un altre el Sr. I així Jo podria començar a fer munts com aquest. I llavors potser m'agradaria anar endavant i una espècie de molt primmirada-li espècie les piles individuals. Però el punt és, buscaria a l'entrada que estic sola mà i m'agradaria fer alguns calcular decisió basada en aquesta entrada. Si comença amb A, el va posar allà. Si comença per Z, el va posar sobre allà, i tota la resta. 

Així que aquesta és una tècnica que és generalment conegut com hashing-- H-A-S-H- que en general significa prendre com a d'entrada i utilitzar aquesta entrada per calcular un valor, en general, un nombre, i que nombre és l'índex en un emmagatzematge contenidor, com una matriu. Així que en altres paraules, que podria tenir una funció hash, com ho faig en el meu cap, que si veig algú és nom que comença amb A, Vaig a assignar que a zero en el meu cap. I si veig algú amb Z, estic anar al mapa que a 25 en el meu cap i després posar això en l'última pila més. 

Ara, si ho penses, no el meu cervell però un programa en C, el que els números podrien vostè confia en aconseguir el mateix resultat? En altres paraules, si tenia el caràcter ASCII A, ¿Com determinar el franc per posar en? És probable que no vol el va posar en el cub 65, que seria com d'allà sense una bona raó. On vols posar un en termes del seu valor ASCII? On vols que fer per al seu ASCII valor per a arribar a una galleda intel·ligent per a posar en? 

AUDIÈNCIA: Minus A. 

DAVID Malan: Sí. Així menys A o menys específicament 65 si és un capital d'A O 98 si es tracta d'una minúscula. I pel que ens permetria, molt simplement i molt aritmèticament, posar alguna cosa en una galleda així. Així que resulta que en realitat fem això també fins i tot amb els concursos. 

Així que vostè pot recordar que vas marcar el teu Nom de l'ensenyament del seu company a la portada. I es van organitzar noms del TF en aquestes columnes en ordre alfabètic, Bé, ho creguis o no, quan tot 80 més de nosaltres es van reunir l'altra nit a grau, l'últim pas en el nostre procés de classificació és per a discutir les proves en un gran espai de sòl en la [inaudible] i establir proves de tot el món a exactament en l'ordre dels seus de TF noms a la coberta, ja que llavors és molt més fàcil per a nosaltres per buscar a través que l'ús lineal buscar o algun tipus d'intel·ligència per a un TF per trobar el seu o proves dels seus estudiants. 

Així que aquesta idea de hash que veuràs és bastant poderós és en realitat bastant lloc comú i molt intuïtiva, de la mateixa manera que potser dividir i conquesta va ser a la setmana zero. Em avanç ràpid per al hackathon un parell d'anys enrere. Aquest va ser Zamyla i un parell de altres estudiants de felicitació personal com van entrar. I vam tenir un munt de plegat taules allà amb etiquetes de nom. I havíem organitzat les etiquetes de nom amb com l'As d'allà i la Zs allà. I així un dels TFS molt intel·ligentment va escriure això com les instruccions per al dia. I en la setmana 12 del semestre aquest tot tenia sentit perfecte i tot el món sabia què fer. Però en qualsevol moment que tens en cua de la mateixa manera, està implementant la mateixa noció d'un hash. Així que anem a formalitzar una mica. Aquí és una matriu. Es va assenyalar a ser una mica àmplia acaba de descriure, visualment, que podríem posar cadenes en alguna cosa com això. I aquesta matriu és clarament de mida 26 total. I la cosa es diu taula arbitràriament. Però això és només una representació artística del que podria ser una taula hash. 

Així que una taula hash ara va a ser una estructura de dades de nivell superior. Al final del dia estem a punt de veure que vostè pot aplicar una taula hash, que és molt similar a la línia de check-in en un hackathon molt com aquest taula utilitzada per a la classificació dels llibres d'examen. Però una taula hash és espècie d'aquest alt nivell concepte que podria utilitzar una matriu sota el capó per implementar-lo, o pot utilitzar una llista de longitud, o fins i tot potser algunes altres estructures de dades. I això sí que és la presa theme-- alguns d'aquests ingredients fonamentals com una matriu i aquest edifici bloquejar ara una llista de longitud i veure què més podem construir a la part superior dels que, com a ingredients en una recepta, el que fa més i més els resultats finals interessants i útils. 

Així que amb la taula hash podríem implementar en la memòria pictòricament com aquest, però com podria ser en realitat codificada cap amunt? Bé, potser la forma més senzilla és aquesta. Si la capacitat en totes les tapes, és només alguns constant-- per exemple 26, per 26 lletres del alphabet-- Jo podria cridar a la meva taula de variables, i jo podria dir que em vaig a posar estrelles Char-hi, o una cadena. Així que és tan simple com això si vulgui implementar una taula hash. I, no obstant això, això és en realitat una matriu. Però, de nou, un hash taula és ara el que anem a trucar a un tipus de dades abstracte que només una mena d'estratificació conceptual a la part superior d'una mica més mundà ara com a vector. 

Ara, com fem per sobre la resolució de problemes? Bé, abans vaig tenir el luxe de tenir prou espai de taula aquí perquè jo pogués posar el concursos en qualsevol lloc que volia. De manera que es pot anar aquí. Zs poden anar aquí. Sra podria anar aquí. I després vaig tenir una mica d'espai extra. Però això és una mica d'un dret de trucs ara perquè aquesta taula, si realment pensat en això com una matriu, és just serà d'algun grandària fixa. 

Així que tècnicament, si em tiri fins a prova d'un altre estudiant i veure, oh, aquesta persona de nom comença amb una A també, Jo com que vull posar aquí. Però tan aviat com em vaig posar allà, si aquesta taula de fet representa una matriu, Jo vaig a estar anul·lant o clobbering a qualsevol concurs d'aquest estudiant és. Dreta? Si es tracta d'una matriu, només una cosa pot anar en cadascuna d'aquestes cèl·lules o elements. I així que tipus de tenir a escollir i triar. 

Ara abans que tipus de enganyat i va fer això o jo només tipus d'apilament ells un sobre l'altre. Però això no va a volar en codi. Llavors, on podria jo posar el segon estudiant el nom Una és si tot el que tenia és aquest espai de taules disponibles? I jo he fet servir tres ranures i es sembla que hi ha només uns pocs altres. Què podria fer? AUDIÈNCIA: [inaudible] DAVID Malan: Sí. Potser anem a mantenir simple. Dreta? No s'ajusta a on vull posar-ho. Així que em vaig a posar tècnicament, on un B aniria. Bé, és clar, estic començant per a pintar a mi mateix en una cantonada. Si arribo a un estudiant el nom és en realitat B, ara B serà mogut una mica cap endavant, com podria succeir, si, si això és un B, ara ha d'anar aquí. 

I pel que aquest molt ràpidament podria convertir-se en un problema, però és una tècnica que en realitat es coneix com sondeig lineal, pel que vostè només considera la seva matriu a ser al llarg de la línia. I que acaba de tipus de sonda o inspeccionar cada element disponible a la recerca d'un lloc disponible. I tan aviat com s'assabenti un, se't cau en aquest país. 

Ara, el preu que es paga ara per aquesta solució és el que? Tenim una matriu de mida fixa, i quan inserit noms -hi, almenys al principi, el que és el temps d'execució de la inserció per posar els estudiants concursos en els cubs de la dreta? Big O de què? 

AUDIÈNCIA: n. DAVID Malan: Vaig escoltar gran O de n. No és cert. Però anem a esmicolar ¿Per què en un moment. ¿Quina altra cosa podria ser? 

AUDIÈNCIA: [inaudible] DAVID Malan: I em va deixar fer visualment. Així que suposem que aquesta és la lletra S. 

AUDIÈNCIA: És un. DAVID Malan: És un. Dreta? Aquesta és una matriu, que vol dir que tenim accés aleatori. I si pensem en això com a zero i això com 25, i ens adonem que, oh, aquí està la meva entrada S, Certament puc convertir S, un caràcter ASCII, a un nombre corresponent entre zero i 25 i després immediatament posar on pertany. 

Però, és clar, tan aviat com arribi a la segona persona el nom és A o B o C finalment, si jo he fet servir el sondeig lineal com la meva solució, el temps d'execució de inserció en el pitjor dels casos que realment es va a delegar en què? I jo ho vaig escoltar aquí correctament des del principi. AUDIÈNCIA: [inaudible] DAVID Malan: Pel que és de fet un cop n vostè té un conjunt de dades prou gran. Així, d'una banda, si la seva matriu és prou gran i les seves dades són escassos suficient, aconseguir aquest bell temps constant. Però tan aviat com comenci cada vegada més i més elements, i només estadísticament s'obté més persones amb la lletra A com el seu nom o la lletra B, podria potencialment delegar en alguna cosa més lineal. Així que no és perfecte. Així que podríem fer millor? 

Bé, el que va ser la nostra solució abans quan ens volen tenir més dinamisme que alguna cosa així com una gran varietat permès? AUDIÈNCIA: [inaudible] DAVID Malan: Què hem presentem? Sí. Així que una llista enllaçada. Bé, anem a veure que és el vinculat llista podria fer per nosaltres en el seu lloc. Bé, deixa proposo que dibuixar la imatge de la següent manera. Ara bé, aquest és un diferent imatge d'un exemple a partir d'un text diferent, en realitat, que és en realitat l'ús d'una matriu de mida 31. I aquest autor simplement decidit hash de cadenes no es basa en els noms de la persona, però en funció de les seves dates de naixement. Independentment del mes, es van adonar si el que es neix en el primer d'un mes o el 31 d'un mes, l'autor es hash basat en aquest valor, a fi de difondre els noms una mica més que 26 punts podrien permetre. I potser és una mica més uniforme d'anar amb les lletres de l'alfabet, perquè, per descomptat, és probable que hi hagi més persones al món amb noms que comencen amb una que sens dubte algunes altres lletres de l'alfabet. Així que potser això és una mica més uniforme, suposant una distribució uniforme dels nadons a través d'un mes. 

Però, és clar, això és encara imperfecte. Dreta? Tindrem col·lisions. Diverses persones en aquest estructura de dades són encara que té la mateixa data de naixement, com a mínim, ets independentment de mes. Però el que ha fet l'autor? Bé, sembla que tenim una matriu a la banda esquerra dibuixat verticalment, però això és només una representació artística. No importa quina direcció dibuixar una matriu, que segueix sent una matriu. Què és aquest un arranjament de semblar? 

AUDIÈNCIA: llista enllaçat. 

DAVID Malan: Sí. Sembla que es tracta d'una gamma de llista enllaçada. Així que de nou, a aquest punt de la classe de la utilització d'aquestes estructures de dades ara com a ingredients a més solucions interessants, vostè pot prendre absolutament 01:00 fonamental, com una matriu, i després prendre una mica més interessant com una llista enllaçada i fins i tot combinar en una encara més interessant estructura de dades. I, de fet, això també faria ser anomenat una taula hash, de manera que la matriu és realment la taula hash, però que la taula hash té cadenes, per dir-ho, que pot créixer o disminuir en la base de la nombre d'elements que voleu inserir. 

Ara, en conseqüència, el que hi ha el temps d'execució ara? Si vull inserir algú el aniversari és el 31 d'octubre ¿D'on ve ell o ella? Bé. A la part inferior, on diu 31. I això és perfecte. Aquesta va ser la constant de temps. Però, ¿i si ens trobem amb algú més el aniversari és, anem a veure, Octubre, novembre, 31 de desembre? On és ell o ella va a anar? La mateixa cosa. Dues pas però. Això és constant, encara que no és així? Bé. En el moment que és. Però en el cas general, més la gent que afegim, probabilísticament, anem per aconseguir més i més col·lisions. 

Ara bé, això és una mica millor perquè tècnicament ara les cadenes podrien estar en el pitjor dels casos fins quan? Si introdueixo n persones en aquest més estructura de dades sofisticat, n persones, en el pitjor dels casos serà n. Per què? 

AUDIÈNCIA: Perquè si tothom té el mateix aniversari, que seran una línia. DAVID Malan: Perfecte. Pot ser que sigui una mica artificiosa, però realment en el pitjor dels casos, si tothom té el mateix aniversari, tenint en compte les entrades que té, vostè va a tenir un cadena massivament llarg. I així, es podria anomenar un la taula de hash, però en realitat és només una llista massiva vinculada amb una gran quantitat d'espai desaprofitat. Però en general, si suposem que almenys els aniversaris són uniform-- i probablement no ho és. Estic fent això. Però si assumim, per nom de la discussió que són, a continuació, en teoria, si Aquesta és la representació vertical, de la matriu, bé, llavors espero que estiguis posarà les cadenes que són, ja saps, més o menys la mateixa longitud que cada un aquests representa un dia del mes. 

Ara bé, si hi ha 31 dies al mes, això vol dir que el meu temps de funcionament realment és gran O de n més de 31, que se sent millor que lineal. Però el que era un dels nostres compromisos d'un parell de setmanes fa cada vegada que es tractava d'expressar el temps d'execució d'un algorisme? Així que únicament busqui en el terme d'ordre superior. Dreta? 31 és definitivament útil. Però això segueix sent gran O de n. Però un dels temes del problema estableix cinc serà de reconèixer que absolutament, asimptòticament, teòricament aquesta estructura de dades no és millor que només una enorme llista enllaçada. I, en efecte, en el pitjor dels casos, aquest taula hash podria recaure en això. 

Però en el món real, amb nosaltres els éssers humans que els propis Mac o PC o el que sigui i s'estan executant món real programari en les dades del món real, quin algoritme es preferirà? El que pren les mesures finals o la un que pren n dividit per 31 passos trobar alguna dada o per buscar una mica d'informació? Vull dir, absolutament les 31 marques una diferència en el món real. És 31 vegades més ràpid. I nosaltres, els humans són sens dubte va a apreciar això. 

Així que adonar-se de la dicotomia allà entre realitat parlant de coses teòricament i asimptòticament que definitivament té valor com hem vist, però en el món real, si vostè es preocupa només fer la feliç humà per a les entrades generals, vostè pot molt bé voler acceptar el fet que, sí, aquesta és lineal, però és 31 vegades més ràpid que pot ser lineal. I millor encara, nosaltres no només hem de fer alguna cosa arbitrari com una data de naixement, podríem passar una mica més temps i la intel·ligència i pensar en el que podríem fer, donat el nom d'una persona i potser la seva data de naixement per combinar els ingredients per esbrinar alguna cosa que és veritablement més uniforme i menys jaggy, per dir-ho d'aquesta imatge Actualment suggereix que podria ser. Com podríem aplicar això en codi? Bé, deixa proposo que simplement demanar prestat una mica de sintaxi que hem utilitzat un parell de vegades fins ara. I jo vaig a definir un node, que de nou és un terme genèric per només algunes recipient per a algun tipus d'estructura de dades. Vaig a proposar que una cadena va allà. Però anem a començar a prendre les rodes d'entrenament d'avui. 

No més biblioteca CS50 realment, a menys que vulgui per utilitzar-lo per a la seva definitiva projecte, que està bé, però ara anem a tirar de la cortina i diuen que és només una estrella de carbó. Així que la paraula no serà nom de la persona en qüestió. I ara tinc un vincle aquí per al següent node de manera que aquests representen cadascun dels nodes a la cadena, potencialment, d'una llista enllaçada. 

I ara què faig Declaro la taula hash en si? Com declaro tota aquesta estructura? Bé, en realitat, de la mateixa manera que jo vaig usar un punter a només el primer element d'una llista abans, de manera similar puc dir simplement Només necessito un munt de punters per implementar aquesta taula hash sencer. Vaig a tenir una matriu crida taula per a la taula hash. Va a tenir la capacitat de mida. Aquesta és la quantitat d'elements pot cabre-hi. I cada un d'aquests elements en aquest matriu serà una estrella de node. Per què? Bé, per aquesta imatge, del que sóc l'aplicació de la taula hash com eficaçment en el principi és només aquesta matriu que hem dibuixat verticalment, cada un dels quadrats representa un punter. Que els que tenen barres a través d'ells són simplement nul. I els que tenen fletxes que van cap a la dreta són punters a nodes reals reals, ergo el començament d'una llista enllaçada. 

Així que aquí, llavors, és com podem implementar una taula hash que implementa encadenament separat. Ara podem fer millor? Molt bé em va prometre l'última vegada que podríem arribar constant de temps. I Jo com que et vaig donar constant de temps aquí, però llavors no dit realment constant de temps perquè encara dependent sobre el total nombre d'elements que està introduint en l'estructura de dades. Però suposem que vam fer això. Permetin-me tornar a la pantalla per aquí. Permetin-me també aquest projecte aquí, clar la pantalla, i suposem que vaig fer això. Suposem que jo volia per inserir el nom Daven en en el meu estructura de dades. 

Així que vull inserir una cadena Daven en l'estructura de dades. Què passa si jo no faig servir un la taula de hash, però jo faig servir cosa que és més arbre-com com un arbre de la família, on vostè té alguna arrel en el superior i després nodes i fulles que van cap a baix i cap a fora. Suposem doncs, que jo que voleu inserir Daven de en el que és actualment una llista buida. Jo vaig a fer el següent: jo sóc crearà un node en aquesta família estructura de dades com arbre que s'assembla una mica com aquesta, cadascun dels quals rectangles ha, diguem, de moment 26 elements en els mateixos. I cadascuna de les cèl·lules en aquesta matriu que està passant per representar la lletra d'un alfabet. 

En concret, vaig a tractar aquest és A, després B, després C, després D, aquest d'aquí. Així que això va a amb eficàcia representar la lletra D. Però per inserir tots Daven de nomeno he de fer una mica més. Així que estic en primer lloc va a haixix, per així dir-ho. Vaig a mirar la primera lletra en Daven que és, òbviament, un D, i jo vaig a assignar un node que mira així- un gran rectangle gran suficient per adaptar-se a tot l'alfabet. 

Ara D es realitza. Ara A. D-A-V-I-N és la meta. Així que ara el que faré és això. Tan aviat com vaig començar avís D no hi ha punter allà. És valors d'escombraries en el moment, o podria inicialitzar a null. Però m'ho dius a mi seguir endavant amb aquesta idea de construir un arbre. Permetin-me assigno un altre d'aquests nodes que compta amb 26 elements en els mateixos. 

I saps què? Si això és només un node en la memòria que He creat amb malloc, utilitzant una estructura com aviat veurem, Jo faré esto-- Vaig a dibuixar una fletxa de el que va representar D baix a aquest nou node. I ara, primer la següent carta en nom de Daven, V-- D-A-V-- vaig a seguir endavant i dibuixar un altre node d'aquest tipus, mitjançant el qual, els elements de V, que aquí anem a sortejar crits instance--. No anem a dibuixar-hi. Es va a anar aquí. 

A continuació, anem a considera que es tracta de V. I llavors aquí anem a índex per sota de V en el que considerarem I. I a continuació, a partir d'aquí anem a anar tenir un d'aquests nodes aquí. I ara tenim una pregunta per contestar. Necessito alguna manera indicar que estem en el final de la cadena Daven. Així que podria deixar nul. 

Però el que si tenim Daven de nom complet també, que és, com hem dit, Davenport? I què si és Daven en realitat una subcadena, un prefix d'una cadena molt més temps? No podem permanentment dir res va anar-hi, perquè podíem Mai inseriu una paraula com Davenport en aquesta estructura de dades 

Llavors, ¿què podríem fer en el seu lloc és tractar cada un d'aquests elements com potser tenir dos elements dins d'ells. Un d'ells és un punter, de fet, com que he estat fent. Així que cadascuna d'aquestes caixes No és només una cèl·lula. Però, i si la part superior un-- de la part inferior serà nul, perquè no hi ha Davenport de moment. Què passa si el de dalt és algun valor especial? I serà una mica difícil de dibuixar aquesta mida. Però suposo que és només una marca de verificació. Comprovi. D-A-E-V-N és una cadena en aquesta estructura de dades. 

Mentrestant, si tingués més espai aquí, el que podia fer P-O-R-T, i jo podria posar xec en el node que té la lletra T al final. Així que aquesta és una forma massiva complex d'aspecte d'estructura de dades. I la meva pròpia mà certament no ajuda. Però si volia inserir alguna cosa més, considerem el que faríem. Si volguéssim posar en David, ens agradaria seguir la mateixa lògica, D-A-V, però ara m'agradaria assenyalar a la propera element no des d'E, però de R a D. Així que serà més nodes d'aquest arbre. Tindrem l'anomenada malloc més. Però jo no vull fer una complet desastre d'aquesta imatge. Així que anem a veure un lloc que ha estat pre-formulat com aquest amb no punt, punt, punts, però només arrays abreujada. Però cada un dels nodes en aquest arbre aquí representa la mateixa cosa-- una matriu Raig de mida 26. 

O si volem ser ara realment adequada, el que si el nom d'algú com un apòstrof, anem a assumir que cada node té en realitat com 27 índexs en ella, no només 26. Així que això ara serà una dada estructura anomenada trie-- T-R-I-I. Un trie, que és suposadament històricament un nom intel·ligent per a un arbre que s'optimitza per recuperació, que per descomptat, s'escriu amb un I-I pel que és trie. Però aquesta és la història de la trie. 

Així que un trie és aquestes dades en forma d'arbre s'estructura com un arbre genealògic que en última instància es comporta d'aquesta manera. I aquí és només un altre exemple d'un tota munt de noms d'altres persones. Però la pregunta ara a la mà és el que té hem guanyat introduint possiblement una més complicada estructura de dades, i un, francament, que utilitza una gran quantitat de memòria. 

Perquè tot i que, en aquest moment, estic sol usant D's punter i A i V i Es i Ns, M'estic perdent una diables de gran quantitat de memòria. Però on pas un recurs, Tendeixo a no recuperar un altre. Així que si estic gastant més espai, el que és probablement l'esperança? Que estic gastant menys què? AUDIÈNCIA: Menys temps. DAVID Malan: Temps. Ara per què podria ser? Bé, quina és la inserció temps, en termes de gran O ara, d'un nom com Daven o Davenport o David? Bé, Daven era cinc passos. Davenport seria nou passos, per la qual cosa seria una mica més passos. David seria cinc passos també. Així que aquests són de formigó números, però segur que hi ha un límit superior en el longitud del nom d'algú. I, en efecte, en el problema grups de cinc especificació, proposarem que és una cosa això és 40 caràcters i tants. 

Sent realistes, ningú té un nom infinitament llarg, que és dir que la longitud d'una nom o la longitud d'una cadena que poden tenir certa l'estat de estructura és discutible què? És constant. Dreta? Pot ser que sigui una gran constant com 40 i tants anys, però és constant. I no té dependència de la quantitat de altres noms pertanyen a aquesta estructura de dades. En altres paraules, si volgut inserir ara Colton o Gabriel o Rob o Zamyla o Alison o Belinda o qualsevol altre nom des del personal en aquestes dades estructura, és el temps d'execució d'inserir altres noms serà en absolut afectat per la forma en molts altres elements són en l'estructura de dades ja? Que no és. Dreta? Com que estem fent servir de manera efectiva aquesta taula hash multicapa. I el temps d'execució de qualsevol d'aquestes operacions depèn no del nombre de elements que estan en l'estructura de dades o que va amb el temps per estar en l'estructura de dades, però en la longitud del que específicament? 

La cadena ser inserit, el que ho fa fer aquest asimptòticament constant gran O temps-- d'un. I, francament, només en el món real, aquest significa inserir el nom de Daven presa com cinc passos, o Davenport 09:00 David passos, o cinc passos. Això és bastant maleït petits temps de funcionament. I, de fet, aquesta és una molt bona cosa, especialment quan no és dependent sobre el total nombre d'elements d'allà. Llavors, ¿com podríem aplicar aquesta tipus d'estructura en el codi? És una mica més complex, però tot i així és només una aplicació de blocs de construcció bàsics. Vaig a redefinir ens node de la manera següent: bool anomenada paraula-- i això que podria dir qualsevol cosa. Però el bool representa el vaig dibuixar com una marca de verificació. Sí. Aquest és el final d'una cadena en aquesta estructura de dades. 

I, per descomptat, l'estrella node no s'està referint als nens. I, de fet, de la mateixa manera que un arbre de la família, vostè consideraria els nodes que estan penjant de la part inferior d'alguns dels pares element per a ser nens. I perquè els nens es van a ser una matriu de 27, el 27 de només estar per apòstrof. Anem a classificar de cas especial que. Així que vostè pot tenir certa noms amb apòstrofs. Potser fins i tot hauria guió anar-hi, però vostè veure a la pàg conjunt 5, que només l'atenció sobre les lletres i apòstrofs. 

I llavors, com fa vostè representa la pròpia estructura de dades? Com es representa a l'arrel d'aquest trie, per dir-ho? Bé, de la mateixa manera que amb una llista enllaçada, que necessitarà un punter al primer element. Amb un trie només en té un punter a l'arrel d'aquest trie. I a partir d'allí es pot hash de el seu camí cap avall més i més profund a tots els altres nodes en l'estructura. Així que simplement amb aquesta llauna representem que estructura. 

Ara Meanwhile-- Oh, pregunta. 

AUDIÈNCIA: Quina és la paraula bool? 

DAVID Malan: paraula Bool és només aquesta encarnació C del que he descrit en aquest quadre d'aquí, quan Vaig començar a dividir cada un dels elements de l'array en dues peces. Un és un punter al següent node. L'altra ha d'haver alguna cosa així com una casella de verificació a dir que sí, que hi ha una Daven paraula que acaba aquí, perquè no volem, de moment, Dave. 

Tot i que a Dave serà una paraula legítima, que no està en el trie encara. I D no és una paraula. I D-A no és una paraula o un nom. Així que la marca de verificació indica només una vegada que colpejar aquest node és el trajectòria anterior de caràcters en realitat una cadena que ha inserit. Així que això és tot el bool no està fent per nosaltres. 

Alguna altra pregunta sobre intents? Sí. 

AUDIÈNCIA: Quina és la coincidència? Què passa si vostè té un Dave i un Daven? DAVID Malan: Perfecte. Què passa si vostè té un Dave i un Daven? Així que si inserim, dir un sobrenom, per David-- Dave-- D-A-V-E? Això és realment molt simple. Així que només tindrem quatre passes. D-A-V-I. I què és el que he de fer una vegada que vaig arribar a quart node? Només va a comprovar. Ja està bo per anar. Fet. Quatre passos. Temps constant asimptòtica. I ara hem indicat que tant de Dave i Daven són cadenes en l'estructura. Així que no és un problema. I noti com la presència de Daven no fer-ho prendre qualsevol temps més o menys temps per Dave i viceversa. 

Llavors, ¿què més podem fer ara? Hem utilitzat aquesta metàfora abans de safates que representa una mica. Però resulta que un pila de safates és en realitat demostratiu d'un altre abstracte de dades type-- una estructura de dades de nivell superior que al final del dia és només com una matriu o una llista enllaçada o alguna cosa més mundà. Però és una més interessant concepte conceptual. Una pila, com aquests safates aquí a Mather, es poden anomenar només que-- una pila. 

I en aquest tipus d'estructura de dades vostè té dues operations-- vostè té una trucada empenta per afegint alguna cosa a la pila, com posar una altra safata la part posterior a la part superior de la pila. I a continuació, el pop, el que significa prendre la més alta fora de la safata. Però el que és clau sobre una pila és que que té aquesta característica curiosa. A mesura que el personal del menjador són la reordenació de les safates per a la pròxima menjar, el que serà cert sobre com els estudiants interactuar amb aquesta estructura de dades? AUDIÈNCIA: Van a esclatar un fos. DAVID Malan: Van a pop un fos, esperem que la part superior. En cas contrari, és només una mica estúpid d'anar tot el camí fins al fons. Dreta? L'estructura de dades en realitat no permet a agafar la safata inferior, almenys, fàcilment. Així que hi ha aquesta curiosa propietat d'una pila que l'últim element és serà el primer a sortir. I els informàtics anomenen LIFO-- aquest últim a entrar, primer a sortir. I el que realment té aplicacions interessants. No és necessàriament tan obvi com alguns altres, però poden, de fet, ser útil, i pot, de fet, ser implementada en un parell de maneres diferents. 

Així que un, i de fet, deixar que a mi, no a submergir-se en això. Anem a fer això en el seu lloc. Fem una ullada a un que és gairebé la mateixa idea, però és una mica més just. Dreta? Si vostè és un d'aquests nois ventilador o noies que realment li agrada els productes d'Apple i es va despertar a les 3:00 am a alinear-se en algun magatzem per obtenir la més recent iPhone, podria haver-hi cua cap amunt com això. 

Ara una cua és nomenat molt deliberadament. És una línia perquè no hi ha alguns justos amb ell. Dreta? Seria tipus de aspirat si tens va arribar primer a la botiga d'Apple però vostè és efectivament la més inferior safata pel fet que els empleats d'Apple després pop de l'última persona que en realitat es va posar en línia. Així piles i cues, tot i funcionalment són tipus de la same-- és només aquesta col·lecció dels recursos que és creixerà i shrink-- hi aquest aspecte ser justos amb ell, almenys en el món real, on les operacions que exerceixen són fonamentalment diferents. A stack-- una cua rather-- es diu que té dues operacions: n de cues i cues d. O vostè pot trucar a ells qualsevol nombre de coses. Però el que desitja és capturar la noció que un és l'addició de i un està en última instància restar. 

Ara sota el capó, tant la pila i una cua podria ser implementat, com? No entrarem en el codi de perquè el nivell més alt és una espècie d'idea més òbvia. Vull dir, ¿què fan els éssers humans? Si jo sóc la primera persona a l'Apple Guardar i aquesta és la porta d'entrada, vostè sap, jo vaig a ser aquí. I de la persona va a ser aquí. I de la persona va a ser aquí. Llavors, ¿quina estructura de dades es presta a una cua? 

AUDIÈNCIA: Una cua. DAVID Malan: Bé, una cua. És clar. Quina altra cosa? 

AUDIÈNCIA: Una llista enllaçada. 

DAVID Malan: Una vinculat llista que podria implementar. I una llista enllaçada és agradable perquè llavors que pot créixer arbitràriament llarga en oposició a tenir un nombre fix de la gent a la botiga. Però potser un nombre fix de llocs és legítim. Perquè si només tenen com a 20 iPhones en el primer dia, potser que només necessiten una matriu de mida 20 per representar aquesta cua, que és només per dir ara, una vegada que vam començar a parlar sobre aquests problemes de més alt nivell, vostè pot posar-lo en pràctica en qualsevol nombre de maneres. I hi ha probablement només va a ser una solució de compromís en l'espai i el temps o simplement en la seva pròpia complexitat del codi. 

Què passa amb una pila? Bé, una pica, hem vist també podria ser només aquestes safates. I es podria implementar aquesta una matriu. Però en algun moment si s'utilitza una matriu, el que va a passar amb les safates vostè està tractant de posar a terra? Bé. Vostè només va a ser capaç d'anar tan alt. I crec que en Mather són realment encastada en aquesta obertura. Així que de fet, és gairebé com Mather està utilitzant una matriu de mida fixa, perquè només es pot encaixar tantes safates en què l'obertura a la paret per sota dels genolls de la gent. I el que podria ser diu que és una matriu, però sens dubte podríem posar en pràctica que més en general amb una llista enllaçada. 

Bé, què passa amb una altra estructura de dades? Permetin-me llevo una altra visual aquí. Una cosa així com què tal aquest d'aquí? Per què podria ser útil per no haver una cosa tan elegant com un trie, que vam veure tenia aquests molt amplis nodes, cadascun dels quals està en una matriu? Però i si fem alguna cosa més simplement, com un arbre de família de l'escola vella, cada un dels nodes aquí s'acaba d'emmagatzemar un nombre. En lloc d'un nom o un descendent s'acaba d'emmagatzemar un nombre com aquest. 

Bé, l'argot que fem servir a estructures de dades és dos paï- i arbres, on un trie, de nou, és només un els nodes són matrius, continua sent el que et poden utilitzar des de l'escola primària quan va fer una família fulles i l'arrel tree-- de l'arbre i els nens de la els pares i germans dels mateixos. I podríem posar en pràctica un arbre, per exemple, com simplement com això. Un arbre, si com un node, una de aquests cercles que té un nombre, no tindrà un punter, sinó dos. I tan aviat com vostè afegeix un segon punter, en realitat pot ara fer una espècie de les dades de dues dimensions estructures en la memòria. Igual que una de dues dimensions matriu, pot tenir classe de dues dimensions llistes enllaçades, però els que segueixen un patró on no hi ha cicles. És realment un arbre amb una manera avi fins aquí i després alguns pares i els nens i néts i besnéts. i així successivament. 

Però el que és realment bo d'això també, només per fer broma amb una mica de codi, el record de la recursivitat un temps enrere, per la qual cosa s'escriu una funció que diu a si mateix. Aquesta és una bella oportunitat implementar alguna cosa com la recursivitat, perquè consideren que aquest. 

Aquest és un arbre. I jo he estat una mica anal amb com Vaig posar els números sencers al carrer. Tant és així que té una especial nom-- un arbre de cerca binària. Ara que hem escoltat de binari cercar, però podeu treballar cap enrere des del nom d'aquesta cosa? Quin és el patró de la forma en què inserit els nombres enters a aquest arbre? No és arbitrari. Hi ha algun patró. Sí. 

AUDIÈNCIA: Els més petits de l'esquerra. 

DAVID Malan: Sí. Els més petits estan a l'esquerra. Altres més grans estan a la dreta. De tal manera que un enunciat veritable és un pare és més gran que el seu fill esquerre, però menor que el seu fill dret. I això només és encara una definició verbal recursiva perquè es pot aplicar aquest mateixa lògica a cada node I només fons terme, un cas base si ho farà, quan va colpejar una de les fulles, per així dir-ho, on una llicència no té fills més. 

Ara, com pot vostè trobar al número 44? Es podria començar a l'arrel i dir, hm. 55 no és 44 així que vull anar dret o vull anar a l'esquerra? Bé, òbviament vol anar esquerra. I així és com el telèfon exemple del llibre en la recerca binària de manera més general. Però estem implementar ara una mica més de forma dinàmica d'una matriu podria permetre. I de fet, si vols buscar en el codi, a primera vista segur. S'assembla a un munt de línies. Però és meravellosament simple. Si desitja implementar una funció crida de recerca el propòsit a la vida és la recerca d'un valor com n, un enter, i ja està aprovada en una pointer-- un punter al node de les arrels, més aviat, d'aquest arbre des del qual es pot accedir a tota la resta, notar com voltes vostè pot aplicar la lògica. Si l'arbre és nul, òbviament, no hi és. Anem a tornar falsa. Dreta? Si et mà que res, no hi ha res allà. 

Else, si n és menor que arbre fletxa N-- ara fletxa n, Recordem introduir súper breument l'altre dia, i això només vol dir de-referència el punter i mirar el camp denominat n. Per tant, vol dir anar-hi i mirar el camp denominat n. Així que si n, el valor que et donen, és menys que el valor en el nombre enter arbres, ¿On vols anar? A l'esquerra. 

Així notar la recursivitat. Estic returning-- no és cert. No és fals. Estic tornant sigui quina sigui la resposta és a partir d'una crida a mi mateix, que passa 1 n de nou, que és redundant, però el que és una mica diferent ara? Com estic fent el problema més petit? Estic passant com a segon argument, no l'arrel de l'arbre, però el fill esquerre en aquest cas. Així que estic passant al fill esquerre. 

Mentrestant, si n és més gran que el node que actualment estic mirant, Jo busco el costat dret. En cas contrari, si l'arbre no és nul, i si l'element no està a l'esquerra i no és a la dreta, el que és meravellosament el cas? En realitat ens hem trobat en el node pregunta, i així tornem cert. 

Així que acabem de esgarrapat la superfície ara algunes d'aquestes estructures de dades. En el problema va fixar cinc podràs explorar aquests encara més lluny, i se li donarà el seu disseny elecció de com anar sobre això. El que m'agradaria arribar a la conclusió és només un segon teaser de 30 del que espera a la setmana que ve i més enllà. 

A mesura que begin-- afortunadament et poden think-- la nostra transició lentament del món de la C i la més baixa detalls d'implementació de nivell, a un món en el qual podem prendre per fet que algú pretén implementat aquestes dades estructures per a nosaltres, i anem a començar a entendre el significa el món real de la implementació programes basats en la web i llocs web de forma més general i també la pròpia seguretat implicacions que hem només començat a gratar la superfície de. Això és el que ens espera en els dies per venir. 

[REPRODUCCIÓ DE VÍDEO] 

-Ell Vi amb un missatge, amb un protocol de totes les seves. Ell va venir a un món de cruel tallafocs, routers indiferents, i perills molt pitjors que la mort. És ràpid. És fort. Ell és TCP / IP, i que té la seva adreça. "Guerrers de la xarxa." [FI REPRODUCCIÓ DE VÍDEO] DAVID Malan: Si ve la setmana que ve. Ens veiem llavors. [REPRODUCCIÓ DE VÍDEO] -I Ara, "Pensaments profunds" per Daven Farnham. -David Comença sempre conferències amb: "Molt bé." Per què no, "Aquí està la solució al conjunt de problemes d'aquesta setmana " o "Estem donant a tots vostès una A?" [El] [FI REPRODUCCIÓ DE VÍDEO]