[RIPRODUZIONE DI BRANI MUSICALI] DAVID MALAN: Questo è CS50. E questo è sia l'inizio e la end-- come literally-- quasi alla fine di sei settimane. 

Ho pensato di condividere un po 'di un fatto divertente. Ho tirato su questo da un impostare i dati del semestre passato. Forse ricorderete che vi chiediamo in ogni forma set p se hai guardato on-line o se avete partecipato di persona. Ed ecco i dati. Quindi oggi era molto prevedibile. Ma volevamo passare un po ' di tempo con voi comunque. Qualcuno vuole ipotizzare il motivo per cui questo grafico è così frastagliato, su giù, su giù, così costantemente? Cosa fare ciascuno dei picchi e depressioni rappresentano? 

PUBBLICO: [incomprensibile] DAVID MALAN: In effetti. E più in modo divertente, Dio non voglia, teniamo una lezione di Venerdì all'inizio del semestre, questo è quello che accadesse. Così oggi, noi partecipiamo in un po ' di più su strutture di dati. E per dare più di un solido modello mentale per problemi alle cinque, che è ora fuori. Errori di ortografia, in cui, faremo si a mano un file di testo circa 100.000 più le parole inglesi, e si sta andando ad avere per capire come caricarli abilmente nella memoria, in RAM, utilizzando alcuni dati struttura della vostra scelta. 

Ora, una tale struttura di dati potrebbe essere, ma probabilmente non dovrebbe essere, la lista collegata piuttosto semplicistica, che abbiamo introdotto l'ultima volta. E una lista collegata avuto almeno un vantaggio su un array. Qual è uno dei vantaggi di una lista collegata forse? 

PUBBLICO: inserimento. 

DAVID MALAN: inserimento. Cosa vuoi dire con questo? 

PUBBLICO: Ovunque lungo l'elenco [incomprensibile]. 

DAVID MALAN: Good. Quindi, è possibile inserire un elemento ovunque si desidera nel bel mezzo della lista senza dover mescolare nulla, che abbiamo concluso, nel nostro ordinamento discussioni, non è necessariamente una buona cosa, perché ci vuole tempo per muoversi in realtà tutti quegli umani a sinistra oa destra. E così con una lista collegata, è possibile solo allocare con malloc, un nuovo nodo, e quindi aggiornare un paio di pointers-- due, tre operazioni max-- e siamo in grado di scanalare qualcuno in qualsiasi punto in un elenco. 

Che altro è stato vantaggioso su una lista collegata? Sì? 

PUBBLICO: [incomprensibile] DAVID MALAN: Perfect. Perfetto. E 'davvero dinamico. E che non si sta commettendo, in anticipo, in una certa dimensione fissa pezzo di memoria, come si avrebbe a con un array, il lato positivo di cui è che è possibile allocare i nodi solo su domanda usando così solo la quantità di spazio come hai veramente bisogno. Al contrario di una serie, si potrebbe accidentalmente allocare troppo poco. E poi è solo andare per essere un dolore al collo di riassegnare un nuovo array più grande, copiare tutto sopra, libera la vecchia matrice, e quindi spostare sulla tua attività. O peggio, si potrebbe allocare modo più memoria del necessario, e così si sta andando ad avere un matrice scarsamente popolate, per così dire. 

Quindi, una lista collegata ti da questi vantaggi di dinamismo e flessibilità con inserimenti ed eliminazioni. Ma sicuramente ci deve essere un prezzo pagato. In effetti, uno dei temi esplorato su quiz a zero è stato un paio di trade-off che abbiamo visto finora. Così che cosa è un prezzo pagato o di un L'unico inconveniente di una lista concatenata? Sì. 

PUBBLICO: Nessun accesso casuale. 

DAVID MALAN: Nessun accesso casuale. Ma chi se ne frega? Accesso casuale non suona convincente. 

PUBBLICO: [incomprensibile] DAVID MALAN: Esattamente. Se si desidera avere un certo algorithm-- e fammi realtà propongo ricerca binaria in particolare, che è quello che abbiamo usato un bel bit-- se non si dispone di accesso casuale, Non si può fare così semplice aritmetica di trovare come l'elemento centrale e saltare diritto. Devi invece iniziare al primo elemento lineare e la ricerca da sinistra a destra se si vuole trovare la metà o qualsiasi altro elemento. 

PUBBLICO: Ci vuole probabilmente più memoria. 

DAVID MALAN: prende più memoria. Dove è che ulteriore costo che viene dalle in memoria? 

PUBBLICO: [incomprensibile] DAVID MALAN: Esattamente. In questo caso qui, abbiamo avuto una lista concatenata per i numeri interi, ma stiamo raddoppiando la quantità di memoria abbiamo bisogno memorizzando anche questi puntatori. Ora, a meno di un grosso problema come i tuoi struct si fanno più grandi e il gioco è la memorizzazione non è un numero, ma forse uno studente o un qualche altro oggetto. Ma il punto rimane certamente. E così una serie di operazioni su liste concatenate sono stati chiamati erano grandi o di lineari n--. Cose come l'inserimento o la ricerca o cancellazione in caso di un elemento è capitato di essere alla fine del l'elenco se è stato o meno ordinato. 

A volte si potrebbe ottenere fortunati e in limiti così bassi su queste operazioni potrebbe anche essere la costante di tempo se siete sempre guardando il primo elemento, per esempio. Ma alla fine, abbiamo promesso per ottenere il Santo Graal di strutture di dati, o un po 'della stessa approssimazione, a titolo di costante di tempo. Possiamo trovare elementi o aggiungere elementi o rimuovere elementi da un elenco? Vedremo molto presto. E si scopre che uno dei meccanismi di cui siamo intenzione di iniziare ad usare oggi, utilizzo annuale in p set di cinque, è in realtà piuttosto familiare. Ad esempio, se questo è un mazzo di libri esame, ciascuna delle quali ha uno studente di prima nome e cognome su di esso, e li prendo da al termine di un esame, e sono tutti abbastanza tanto in un ordine casuale, e vogliamo andare sull'ordinamento questi esami in modo che, una volta classificati è solo molto più facile e più veloce a portata di mano di nuovo fuori agli studenti in ordine alfabetico. Che cosa il vostro istinto essere per un mucchio di esami come questo? 

Beh, se siete come me, si potrebbe vedere che questo è m, così ho intenzione di mettere questo tipo di in, se questo è il mio tavolo o il mio piano dove Sto diffondendo le cose fuori-- o la mia matrice really-- Potrei mettere tutta la signora in là. Oh. Ecco un A. Quindi potrei Come mettere i qui. Oh. Ecco un altro A. Vado mettere che qui. Ecco una Z. Ecco un altro M. E così Potrei iniziare a fare i mucchi come questo. E poi magari mi piacerebbe andare a più tardi e una sorta di molto nitpicky-ly sorta i singoli pali. Ma il punto è che vorrei guardare in ingresso che sono mano e vorrei fare qualche calcolato decisione sulla base di tale ingresso. Se inizia con A, messo lì. Se inizia con Z, lo mise sopra lì, e tutto il resto. 

Quindi questa è una tecnica che è generalmente noto come hashing-- H-A-S-H-- che generalmente significa prendere come input e usando quell'ingresso per calcolare un valore, generalmente un numero, e che numero è l'indice in una memorizzazione contenitore, come un array. Quindi, in altre parole, potrei avere un funzione di hash, come faccio io nella mia testa, che se vedo qualcuno è nome che inizia con A, Ho intenzione di mappa che a zero nella mia testa. E se vedo qualcuno con Z, io sono andando a mappare che a 25 nella mia testa e poi metterlo in l'ultima più mucchio. 

Ora, se ci pensate non il mio cervello ma un programma C, quali numeri potrebbero ci si affida per ottenere lo stesso risultato? In altre parole, se si aveva il carattere ASCII A, come si fa a determinare cosa secchio per mettere in? Probabilmente non si vuole metterlo nel secchio 65, che sarebbe come laggiù per nessuna buona ragione. Dove vuoi mettere un in termini di valore ASCII? Dove vuoi fare per la sua ASCII Valore a venire con un secchio intelligente per dirla in? 

PUBBLICO: Minus A. 

DAVID MALAN: Sì. Quindi meno A o meno in particolare 65 se si tratta di la A maiuscola o 98 se si tratta di un minuscolo a. E in modo che sarebbe ci permettono di, molto in modo semplice e molto aritmeticamente, mettere qualcosa in un secchio del genere. Così si scopre che in realtà facciamo anche questo anche con i quiz. 

Così si potrebbe ricordare che si cerchiata la tua Nome insegnamento del compagno sulla copertina. E nomi del TF sono state organizzate in queste colonne in ordine alfabetico, beh, che ci crediate o no, quando tutto 80, più di noi si sono riuniti l'altra sera al grado, l'ultimo passo del nostro processo di classificazione è quello di eseguire l'hashing dei quiz in un grande lo spazio di pavimento al [incomprensibile] nonché di definire i quiz di tutti i esattamente l'ordine delle loro TF di nomi sulla copertina, in quanto allora è molto più facile per noi per la ricerca in che l'utilizzo di lineare ricerca o qualche tipo di intelligenza per un TF a trovare la sua o quiz dei suoi studenti. 

Quindi questa idea di hashing che vedrete è abbastanza potente è in realtà piuttosto banale e molto intuitivo, molto simile forse dividere e conquista era in settimana pari a zero. I fast forward al hackathon un paio di anni fa. Questo era Zamyla e un paio di altri studenti di auguri personale come sono venuti in. E abbiamo avuto un sacco di piegatura tavoli lì con etichette nome. E avevamo i cartellini organizzata con come le Come laggiù e la Zs laggiù. E così uno dei TF molto abilmente ha scritto questo come le istruzioni per la giornata. E nella settimana 12 del semestre tale tutto aveva un senso perfetto e tutti sapeva che cosa fare. Ma ogni volta che hai coda nello stesso modo, sei l'attuazione del stessa nozione di un hash. Quindi cerchiamo di formalizzare un po '. Qui è un array. E 'disegnato per essere un po' ampia solo di rappresentare, visivamente, che potremmo mettere stringhe in qualcosa di simile a questo. E questo array è chiaramente di dimensione 26 in totale. E la cosa si chiama tavolo arbitrariamente. Ma questo è solo resa di un artista di quello che potrebbe essere una tabella hash. 

Quindi una tabella hash ora sta per una struttura di dati di livello superiore. Alla fine della giornata stiamo per vedere che si in grado di implementare una tabella hash, che è molto simile alla linea del check-in ad un hackathon molto simile a questo tavolo utilizzato per l'ordinamento di libri d'esame. Ma una tabella hash è specie di questo elevato livello concetto che potrebbe utilizzare un array sotto la cappa per la sua attuazione, o potrebbe utilizzare un elenco di lunghezza, o addirittura forse alcune altre strutture di dati. Ed ora che è la presa theme-- alcuni di questi ingredienti fondamentali come un array e questo edificio bloccare ora di una lista di lunghezza e vedere che cosa possiamo costruire in cima a quelli, come ingredienti in una ricetta, rendendo più risultati finali interessanti e utili. 

Quindi, con la tabella di hash potremmo attuarlo in memoria pittoricamente come questo, ma come potrebbe essere in realtà codificato up? Beh, forse nel modo più semplice è questo. Se la capacità in tutte le protezioni, è solo alcuni constant-- per esempio 26, per le 26 lettere dell'alfabeto alphabet-- Potrei chiamare la mia tabella delle variabili, e potrei affermare che ho intenzione di mettere stelle char in là, o una stringa. Quindi è semplice come questo se si desidera implementare una tabella hash. Eppure, questo è in realtà solo un array. Ma ancora una volta, un hash tabella è ora che cosa faremo chiamare un tipo di dato astratto che è solo sorta di stratificazione concettuale in cima di qualcosa di più banale ora come un array. 

Ora, come possiamo fare di risolvere i problemi? Beh, in precedenza ho avuto il lusso di avere abbastanza spazio tabella qui in modo da poter mettere il quiz ovunque volevo. Così come potrebbe andare qui. Zs potrebbero andare qui. La signora potrebbe andare qui. E poi ho avuto un po 'di spazio in più. Ma questo è un po 'di un diritto imbroglio ora perché questa tabella, se davvero pensato come una matrice, è solo andando essere di qualche dimensione fissa. 

Tecnicamente, quindi, se tiro up quiz di un altro studente e vedere, oh, questa persona di nome inizia con una A troppo, I tipi di voglia di metterlo lì. Ma non appena ho messo lì, se Questa tabella rappresenta infatti una matrice, Ho intenzione di essere priorità assoluta o sovrascrivere chi quiz di questo studente è. Giusto? Se questo è un array, solo una cosa può andare in ciascuna di queste cellule o elementi. E così ho sorta di ho di scegliere. 

Ora prima che tipo di truffato e ha fatto questo o io solo tipo di impilati li sopra l'altra. Ma che non sta andando a volare nel codice. Allora, dove posso mettere la secondo studente il cui nome è A se tutto quello che avevo è questo disponibile spazio di tabella? E io ho usato tre slot ed è sembra che ci sia solo un pochi altri. Che cosa si potrebbe fare? PUBBLICO: [incomprensibile] DAVID MALAN: Sì. Forse facciamo solo mantenere le cose semplici. Giusto? Non si adatta dove voglio metterlo. Quindi ho intenzione di metterlo tecnicamente in cui un B sarebbe andato. Ora, naturalmente, sto iniziando a dipingere me stesso in un angolo. Se arrivare a uno studente il cui nome è in realtà B, Ora B sta per essere spostato leggermente in avanti, come potrebbe accadere, sì, se questo è un B, ora deve andare qui. 

E così questo molto rapidamente potrebbe diventare problematico, ma è una tecnica che effettivamente viene indicato come scansione lineare, per cui è sufficiente prendere in considerazione il vostro array per essere lungo la linea. E tu solo tipo di sonda o ispezionare ogni elemento disponibile alla ricerca di un posto disponibile. E non appena si trova uno, viene rilasciato in là. 

Ora, il prezzo viene pagato ora per questa soluzione è quello? Abbiamo un array di dimensione fissa, e quando inserisco i nomi in esso, almeno inizialmente, ciò che è il tempo di esecuzione di insertion per mettere gli studenti quiz nei secchi giusto? Big O di che cosa? 

PUBBLICO: n. DAVID MALAN: Ho sentito grande O di n. Non è vero. Ma ci prendono in giro a parte perché in un attimo. Che altro potrebbe essere? 

PUBBLICO: [incomprensibile] DAVID MALAN: E lasciate fare a me visivamente. Quindi supponiamo che questa è la lettera S. 

PUBBLICO: E 'una. DAVID MALAN: E 'uno. Giusto? Questo è un array che significa che abbiamo accesso casuale. E se pensiamo a questo come zero e questo come 25, e ci rendiamo conto che, oh, ecco il mio ingresso S, Posso certamente convertire S, un carattere ASCII, di altrettante tra zero e 25 e poi subito metterlo in cui essa appartiene. 

Ma, naturalmente, non appena arrivo al seconda persona il cui nome è A o B o C alla fine, se ho usato il scansione lineare come la mia soluzione, il tempo di esecuzione di inserimento nel caso peggiore è in realtà andando a devolvere in che cosa? E ho sentito qui correttamente nella fase iniziale. PUBBLICO: [incomprensibile] DAVID MALAN: Così è in effetti una volta n si dispone di un numero sufficientemente ampio insieme di dati. Così, da un lato, se la matrice è abbastanza grande ei dati sono abbastanza scarsa, è ottenere questo bel tempo costante. Ma non appena si inizia a sempre più elementi, e solo statisticamente si ottiene più persone con la lettera A come il loro nome o la lettera B, si potrebbe potenzialmente devolvere in qualcosa di più lineare. Quindi, non del tutto perfetto. Così abbiamo potuto fare di meglio? 

Beh, quello che era il nostro soluzione prima quando abbiamo vogliono avere più dinamismo di qualcosa di simile a un array permesso? PUBBLICO: [incomprensibile] DAVID MALAN: Cosa abbiamo presentiamo? Sì. Quindi, una lista collegata. Bene, vediamo cosa un legato elenco potrebbe fare per noi, invece. Bene, lasciate che propongo di disegnare l'immagine come segue. Ora questo è un diverso un'immagine da un esempio da un testo diverso, in realtà, che è in realtà utilizzando un array di dimensione 31. E questo autore semplicemente deciso di hash stringhe non basata sui nomi della persona, ma in base alle loro date di nascita. Indipendentemente mese, hanno pensato se sei nato il primo di un mese o il 31 del mese, l'autore si hash sulla base di tale valore, al fine di diffondere i nomi un po ' più di 26 punti potrebbero permettere. E forse è un po 'più uniforme che andare con le lettere alfabetiche, perché naturalmente c'è probabilmente maggior numero di persone nel mondo con nomi che iniziano con un certo rispetto alcune altre lettere dell'alfabeto. Quindi forse questo è un po ' più uniforme, assumendo una distribuzione uniforme dei neonati attraverso un mese. 

Ma, naturalmente, questo è ancora imperfetta. Giusto? Stiamo avendo collisioni. Più persone in questo struttura dei dati sono ancora aventi la stessa data di nascita almeno sei a prescindere dal mese. Ma che cosa ha fatto l'autore? Beh, sembra che abbiamo un array sul lato sinistro disegnata verticalmente, ma questo è solo resa di un artista. Non importa quale direzione si disegnare un array, è ancora un array. Che cosa è questa una serie di apparenza? 

PUBBLICO: lista collegata. 

DAVID MALAN: Sì. Sembra come se fosse un serie di lista collegata. Quindi, di nuovo, a questo punto di genere di utilizzare queste strutture di dati ora come ingredienti di più soluzioni interessanti, si può assolutamente fare una fondamentale, come un array, e poi prendere qualcosa di più interessante come una lista concatenata e anche combinarli in un ancora struttura dati più interessante. E in effetti, anche questo sarebbe essere definito una tabella hash, per cui la matrice è davvero la tabella di hash, ma che tabella di hash ha catene, per così dire, che può crescere o diminuire in base alla numero di elementi che si desidera inserire. 

Ora, di conseguenza, che cosa è il tempo di esecuzione ora? Se voglio inserire qualcuno il cui compleanno è il 31 ottobre, da dove viene lui o lei andare? Bene. In fondo molto dove c'è scritto 31. E questo è perfetto. E 'stato costante di tempo. Ma cosa succede se troviamo qualcun altro il cui compleanno è, vediamo, Ottobre, novembre, 31 dicembre? Casi in cui è lui o lei sta per andare? Stessa cosa. Due step però. Questo è costante anche se non è vero? Bene. Al momento è. Ma nel caso generale, più la gente aggiungiamo noi, probabilisticamente, stiamo andando per ottenere sempre più collisioni. 

Ora questo è un po ' meglio perché tecnicamente ora le mie catene potrebbero essere in il caso peggiore per quanto tempo? Se inserisco n persone in questo più sofisticata struttura di dati, n persone, nel peggiore dei casi sarà n. Perché? 

PUBBLICO: Perché se tutti ha lo stesso compleanno, si sta andando ad essere una linea. DAVID MALAN: Perfect. Potrebbe essere un po 'forzato, ma veramente nel peggiore dei casi, se tutti hanno la stessa data di nascita, dato gli input che avete, si sta andando ad avere un massicciamente lunga catena. E così, si potrebbe chiamare un hash tavolo, ma in realtà è solo un enorme lista collegata con un sacco di spazio sprecato. Ma in generale, se si assume che almeno compleanni sono uniform-- e probabilmente non lo è. Sto facendo che fino. Ma se si assume, per il bene della discussione che sono, poi, in teoria, se questa è la rappresentazione verticale della matrice, beh, allora si spera che sei intenzione di ottenere catene che sono, si sa, all'incirca la stessa lunghezza in cui ciascuno di questi rappresenta un giorno del mese. 

Ora, se c'è 31 giorni in mese, questo significa che il mio tempo di esecuzione davvero è grande O di n più di 31, che si sente meglio che lineare. Ma quello che era uno dei nostri impegni un paio di settimane fa ogni volta che si è trattato di esprimere il tempo di esecuzione di un algoritmo? Basta guardare solo al termine di ordine superiore. Giusto? 31 è sicuramente utile. Ma questo è ancora un grande O di n. Ma uno dei temi del problema ha impostato cinque sta per essere a riconoscere che assolutamente, asintoticamente, in teoria questa struttura dati non è meglio di un semplice una massiccia lista collegata. E infatti, nel caso peggiore, questo tabella hash potrebbe devolvere in quello. 

Ma nel mondo reale, con noi esseri umani che proprio Mac o PC o qualsiasi altra cosa e sono in esecuzione mondo reale software su dati reali, che algoritmo hai intenzione di preferire? Quello che fa passi finali o le uno che prende n diviso per 31 passi di trovare qualche pezzo di dati o per cercare qualche informazione? Voglio dire, assolutamente le 31 marche la differenza nel mondo reale. E '31 volte più veloce. E noi esseri umani sono certamente andare a capire che. 

Quindi realizzare la dicotomia ci tra realtà parlando di cose teoricamente e asintoticamente che sicuramente ha valore come abbiamo visto, ma nel mondo reale, se ti interessa solo fare il felice umana per gli ingressi generali, si potrebbe benissimo voler accettare il fatto che, sì, questo è lineare, ma è 31 volte più veloce che lineare potrebbe essere. E meglio ancora, non ci resta che fare qualcosa di arbitrario come una data di nascita, abbiamo potuto trascorrere un po ' più tempo e intelligenza e pensare a ciò che potremmo fare, dato il nome di una persona e forse la loro data di nascita di combinare quelle ingredienti per capire qualcosa che è veramente più uniforme e meno Jaggy, per così dire di questa immagine Attualmente suggerisce che potrebbe essere. Come potremmo implementare questo in codice? Bene, lasciate che propongo di solo prendere in prestito un po 'di sintassi che abbiamo usato un paio di volte finora. E ho intenzione di definire un nodo, che di nuovo è un termine generico per solo alcuni Contenitore per qualche struttura dati. Ho intenzione di proporre che una stringa sta andando in là. Ma stiamo per iniziare a prendere quelli formazione ruote fuori ora. 

Non più biblioteca CS50 in realtà, se non si desidera da utilizzare per il vostro finale progetto, che va bene, ma ora stiamo andando a tirare indietro la tenda e dire che è solo una stella char. Così la parola non sta per essere il nome della persona in questione. E ora ho un link Qui al nodo successivo in modo che questi rappresentano ciascuno dei nodi nella catena, potenzialmente, di una lista collegata. 

E adesso come faccio dichiaro la tabella hash in sé? Come dichiaro tutta questa struttura? Beh, in realtà, proprio come ho usato un puntatore a solo il primo elemento di una lista prima, allo stesso modo posso solo dire Ho solo bisogno di un po 'di puntatori per attuare questa tabella intero hash. Ho intenzione di avere un array chiamato tavolo per tabella hash. Sta andando essere di capacità dimensioni. Questo è il numero di elementi può andare bene in esso. E ciascuno di questi elementi in questo serie sta per essere una stella nodo. Perché? Ebbene, a questa immagine, quello che sto l'attuazione della tabella di hash come efficacemente in principio è solo questo array che abbiamo disegnato in senso verticale, ciascuno dei quali piazze rappresenta un puntatore. Che quelli che hanno barre attraverso di loro sono proprio nulla. E quelli che hanno frecce che vanno a destra sono puntatori effettivi nodi effettivi, ergo l'inizio di una lista collegata. 

Ecco, allora, è il modo in cui potrebbe implementare una tabella hash che implementa concatenazioni separate. Ora siamo in grado di fare di meglio? Va bene ho promesso l'ultima volta che potremmo realizzare costante di tempo. E mi avete dato tipo di costante di tempo qui, ma poi non è detto veramente costante di tempo perché è ancora dipendente dal totale numero di elementi si sta inserendo in la struttura dei dati. Ma supponiamo che abbiamo fatto questo. Lasciatemi tornare alla schermata qui. Vorrei anche proietto questo qui, chiaro lo schermo, e supponiamo che ho fatto questo. Supponiamo che io volevo inserire il nome Daven in nella mia struttura dati. 

Quindi voglio inserire una stringa Daven nella struttura dati. Cosa succede se non uso un hash tavolo, ma io uso qualcosa che è più ad albero come un albero genealogico, in cui avete qualche radice in superiore e poi i nodi e foglie che vanno verso il basso e verso l'esterno. Supponiamo allora, che desidera inserire Daven di in quello che è attualmente un elenco vuoto. Ho intenzione di fare quanto segue: io sono andando a creare un nodo in questa famiglia albero-come struttura di dati che guarda un po 'come questo, ciascuno dei quali rettangoli ha, diciamo, per ora 26 elementi in esso. E ciascuna delle cellule in questo array sta andando per rappresentare la lettera di un alfabeto. 

In particolare, ho intenzione di trattare questo è A, poi B, poi C, poi D, questa qui. Quindi questo sta andando in modo efficace rappresentare la lettera D. Ma per inserire tutti Daven di nome che ho bisogno di fare un po 'di più. Così sto prima intenzione di hash, per così dire. Io vado a guardare la prima lettera in Daven di che è ovviamente una D, e ho intenzione di allocare un nodo che sembra Questa poi come un grande rettangolo grande abbastanza da contenere l'intero alfabeto. 

Ora D è fatto. Ora A. D-A-V-E-N è l'obiettivo. Così ora che cosa ho intenzione di fare è questo. Non appena ho iniziato preavviso D non c'è puntatore lì. Si tratta di valori di immondizia in questo momento, o potrei inizializzarla a null. Ma mi permetta di andare avanti con questa idea di costruire un albero. Mi permetta di allocare un altro uno di questi nodi che ha 26 elementi in esso. 

E sai una cosa? Se questo è solo un nodo nella memoria Ho creato con malloc, utilizzando una struct come vedremo tra poco, Ho intenzione di fare questo-- Ho intenzione di disegnare una freccia da la cosa che rappresentava D verso il basso a questo nuovo nodo. E ora, in primo luogo il prossimo lettera a nome di Daven, V-- D-A-V-- ho intenzione di andare avanti e disegnare un altro nodo come questo, per cui, gli elementi di V qui, che disegneremo per whoops instance--. Non disegnare lì. E 'intenzione di andare qui. 

Poi andremo a ritiene che ciò sia V. E poi qui stiamo andando all'indice giù da V in ciò che noi considereremo E. E poi da qui andremo a andare avere uno di questi nodi qui. E ora abbiamo una domanda a cui rispondere. Ho bisogno di qualche modo indicare che siamo alla fine della stringa Daven. Così ho potuto semplicemente lasciare nulla. 

Ma cosa succede se abbiamo Daven di nome e cognome anche, che è, come abbiamo detto, Davenport? Che importa se è Daven in realtà una sottostringa, un prefisso di una stringa molto più a lungo? Non possiamo solo in modo permanente dire niente sta andando di andare lì, perché abbiamo potuto non inserire mai una parola come Davenport in questa struttura dati 

Quindi quello che abbiamo potuto fare invece è trattare ciascuno di questi elementi come forse avere due elementi all'interno di essi. Uno è un puntatore, infatti, come ho fatto. Così ognuno di queste caselle non è solo una cellula. Ma cosa succede se la parte superiore tra-- del quello inferiore sta per essere nullo, perché c'è solo ancora Davenport. Che cosa succede se quella superiore è un valore speciale? E sta andando ad essere un po ' difficile da elaborare in questo formato. Ma supponiamo che è solo un segno di spunta. Controllare. D-A-V-E-N è una stringa in questa struttura dati. 

Nel frattempo, se avessi più spazio qui, ho potuto fare P-O-R-T, e ho potuto mettere il check-in nel nodo che ha la lettera T alla fine. Quindi questo è un massicciamente complesso guardando struttura dati. E la mia scrittura a mano di certo non aiuta. Ma se avessi voluto inserire qualcosa altra cosa, consideriamo cosa avremmo fatto. Se volessimo mettere in David, ci piacerebbe seguire la stessa logica, D-A-V, ma ora vorrei puntare nel prossimo Elemento non da E, ma da I a D. Quindi ci sara ' più nodi in questo albero. Stiamo andando ad avere chiamata malloc più. Ma io non voglio fare una completo disordine dell'immagine. Quindi diamo invece un'occhiata a uno che è stato pre-formulato così con non dot, dot, punti, ma gli array appena abbreviati. Ma ciascuno dei nodi in questo albero qui rappresenta la stessa cosa-- una serie Ray di dimensioni 26. 

Oppure, se vogliamo essere davvero corretto ora, cosa se il nome di qualcuno come un apostrofo, cerchiamo di supporre che ciascun nodo ha effettivamente come 27 indici in esso, non solo 26. Quindi questo ora sta per essere un dato struttura chiamata trie-- T-R-I-E. Un trie, che si suppone sia storicamente un nome intelligente per un albero che è ottimizzato per recupero, che naturalmente, è scritto con un I-E quindi è trie. Ma questa è la storia del trie. 

Quindi un trie è questi dati ad albero struttura come un albero genealogico che si comporta in ultima analisi, come quella. E qui è solo un altro esempio di un sacco di nomi di altre persone. Ma la questione ora a portata di mano è quello che ha abbiamo ottenuto introducendo senza dubbio un più struttura dati complessa, e uno, francamente, che utilizza molta memoria. 

Perché anche se, in questo momento, io sono solo con puntatore D's e A e V e Es e Ns, Sto sprecando un diavolo di molta memoria. Ma dove trascorro una risorsa, Tendo a non ottenere indietro un altro. Quindi, se io sto spendendo più spazio, ciò che è probabilmente la speranza? Che sto spendendo meno che cosa? PUBBLICO: Meno tempo. DAVID MALAN: Tempo. Ora, perché potrebbe essere? Ebbene, che cosa è l'inserimento tempo, in termini di grande O ora, di un nome come Daven o Davenport o David? Beh, Daven era cinque passi. Davenport sarebbe nove passi, quindi sarebbe un altro paio di passi. David sarebbe cinque passi pure. Quindi questi sono di cemento numeri, ma sicuramente non c'è un limite superiore sulla lunghezza del nome di qualcuno. E infatti, nel problema set di cinque specifiche, che andremo a proporre che si tratta di qualcosa di questo è caratteri 40-qualche-dispari. 

Realisticamente, nessuno ha un nome infinitamente lungo, vale a dire che la lunghezza di un il nome o la lunghezza di una stringa potremmo hanno determinato lo stato di la struttura è senza dubbio quello che? E 'costante. Giusto? Potrebbe essere un grande costante come 40-qualcosa, ma è costante. E non ha alcuna dipendenza da quanti altri nomi sono in questa struttura dati. In altre parole, se voluto inserire ora Colton o Gabriel o Rob o Zamyla o Alison o Belinda o qualsiasi altro nome dal personale in questi dati struttura, è il tempo di esecuzione di inserimento di altri nomi andando affatto impatto da come molti altri elementi sono nella struttura dati già? Non è. Giusto? Perché stiamo utilizzando in modo efficace questa tabella hash multistrato. E il tempo di esecuzione di una di queste operazioni non dipende dal numero di elementi che sono nella struttura dati o che siano eventualmente andando sia nella struttura dati, ma la lunghezza di quello specifico? 

La stringa essendo inserito, che fa fare questo asintoticamente costante tempo-- grande O di uno. E, francamente, proprio in mondo reale, questo significa inserire il nome di Daven prende come cinque passi, o Davenport nove passi, o David cinque passi. Questo è maledettamente piccoli tempi di esecuzione. E, in effetti, questo è un molto buona cosa, soprattutto quando non è dipendente dal totale numero di elementi in là. Così come si potrebbe implementare questa tipo di struttura in codice? E 'un po' di più complessa, ma comunque è semplice applicazione degli elementi di base. Ho intenzione di ridefinire nodo di noi nel modo seguente: bool chiamato word-- e questo potrebbe essere chiamato nulla. Ma il bool rappresenta quello che ho disegnato come un segno di spunta. Sì. Questa è la fine di una stringa in questa struttura dati. 

E, naturalmente, la stella nodo si fa riferimento ad i bambini. E, in effetti, proprio come un albero genealogico, si prenderebbe in considerazione i nodi che vengono appesi fuori del fondo di qualche genitore Elemento di essere bambini. E così i bambini sta per essere un array di 27, quella 27 solo di essere per apostrofo. Stiamo andando a ordinare di caso speciale che. Così si può avere certo nomi con apostrofi. Forse anche trattino dovrebbe andare in là, ma avrete vedi in p set 5 abbiamo solo la cura su lettere e apostrofi. 

E allora come si fa a rappresentare la struttura dati stessi? Come si fa a rappresentare la radice questo trie, per così dire? Beh, proprio come con una lista collegata, è serve un puntatore al primo elemento. Con un trie è sufficiente uno puntatore alla radice di questo trie. E da lì si può hash il vostro senso giù sempre più in profondità ad ogni altro nodo nella struttura. Quindi, semplicemente con questo can noi rappresentiamo che struct. 

Ora Meanwhile-- Oh, domanda. 

PUBBLICO: Che cosa è la parola bool? 

DAVID MALAN: parola di Bool è proprio questa incarnazione C di quello che ho descritto in questa casella qui, quando Ho iniziato dividere ciascuno degli elementi di array in due pezzi. Uno è un puntatore al nodo successivo. L'altro deve essere qualcosa di simile a una casella di controllo a dire di sì, c'è un parola Daven che finisce qui, perché non vogliamo, Al momento, Dave. 

Anche se Dave sta per essere un legittimo parola, che non è nel trie ancora. E D non è una parola. E D-A non è una parola o un nome. Così il segno di spunta indica solo una volta che si ha colpito questo nodo è il precedente percorso di personaggi in realtà una stringa che hai inserito. Ecco, questo è tutto il bool si sta facendo per noi. 

Tutte le altre domande sui tentativi? Sì. 

PUBBLICO: Qual è la sovrapposizione? Che cosa succede se si dispone di un Dave e un Daven? DAVID MALAN: Perfect. Che cosa succede se si dispone di un Dave e un Daven? Quindi, se inseriamo, dire un soprannome, per David-- Dave-- D-A-V-E? Questo in realtà è super semplice. Quindi stiamo solo andando a prendere quattro passi. D-A-V-E. E che cosa devo fare una volta mi ha colpito che il quarto nodo? Basta andare a controllare. Siamo già a posto. Fatto. Quattro passi. Costante di tempo asintoticamente. E ora abbiamo indicato che sia Dave e Daven sono stringhe nella struttura. Quindi non è un problema. E notare come la presenza di Daven non ha fatto che prendere altro tempo o meno tempo per Dave e viceversa. 

Quindi, che cosa possiamo fare ora? Abbiamo utilizzato questa metafora prima di vassoi che rappresenta qualcosa. Ma si scopre che un pila di vassoi è effettivamente dimostrativo di un altro dato astratto type-- una struttura di dati di livello superiore che alla fine della giornata è solo come un array o una lista concatenata o qualcosa di più banale. Ma è un più interessante concetto concettuale. Una pila, come questi vassoi qui a Mather, sono generalmente chiamati solo che-- una pila. 

E in questo tipo di struttura dati si hanno due operations-- si dispone di uno chiamato spinta per aggiungendo qualcosa alla pila, come mettere un altro vassoio eseguire in cima alla pila. E poi pop, che significa prendere il più in alto cassetto off. Ma cosa c'è di chiave su una pila è che è ottenuto questa curiosa caratteristica. Mentre il personale di sala da pranzo sono riorganizzare i vassoi per il pasto successivo, cosa sarà vero circa come gli studenti Interazioni struttura dati? PUBBLICO: Stanno andando al pop una tantum. DAVID MALAN: Stanno andando a pop una tantum, si spera la parte superiore. In caso contrario, è solo un po 'stupido per andare fino al fondo. Giusto? La struttura dei dati in realtà non permette di afferrare il vassoio inferiore almeno facilmente. Quindi c'è questo curioso proprietà su una pila che l'ultimo elemento è sarà il primo ad uscire. E gli informatici chiamano questo LIFO-- last in, first out. E che ha realmente interessanti applicazioni. Non è necessariamente così evidente come alcuni altri, ma può, infatti, essere utile, e può, infatti, essere attuato in un paio di modi diversi. 

Così uno, e in realtà, lasciate me, non a tuffarsi in quella. Facciamo così, invece. Diamo un'occhiata a quello che è quasi il stessa idea, ma è un po 'più giusto. Giusto? Se siete uno di questi ragazzi fan o ragazze che ama davvero i prodotti Apple e ti sei svegliato alle 3:00 AM a schierarsi in qualche negozio per ottenere le più recenti iPhone, si avrebbe potuto in coda in questo modo. 

Ora una coda è molto deliberatamente nome. E 'una linea perché c'è un po 'di equità ad esso. Giusto? Sarebbe tipo di risucchiato se avete arrivati ​​prima presso l'Apple Store ma si sta effettivamente il più in basso cassetto perché i dipendenti Apple poi pop l'ultima persona che in realtà ha ottenuto in linea. Quindi, pile e code, ancorché funzionalmente sono tipo di stesso-- è solo questa collezione delle risorse che è andando a crescere e shrink-- c'è questo aspetto dell'equità ad esso, almeno nel mondo reale, dove le operazioni che esercitano sono fondamentalmente diversi. Un stack-- una coda rather-- si dice che abbia due operazioni: n coda e coda d. Oppure è possibile chiamare qualsiasi numero di cose. Ma vuoi solo catturare l'idea che si sta aggiungendo e si è in ultima analisi, sottraendo. 

Ora sotto la cappa, sia lo stack e una coda può essere implementato come? Non entreremo nel codice di perché il livello superiore idea è una sorta di più evidente. Voglio dire, che cosa fanno gli esseri umani? Se io sono la prima persona al di Apple Conservare e questa è la porta d'ingresso, sai, ho intenzione di stare qui. E la prossima persona andando a stare qui. E la prossima persona andando a stare qui. Quindi, quale struttura dati si presta a una coda? 

PUBBLICO: Una coda. DAVID MALAN: Beh, una coda. Certo. Cos'altro? 

PUBBLICO: Una lista concatenata. 

DAVID MALAN: una legata l'elenco che si potrebbe implementare. E una lista collegata è bello perché poi può crescere arbitrariamente lungo rispetto di avere un numero fisso di persone nel negozio. Ma forse un numero fisso di posti è legittimo. Perché se hanno solo come 20 iPhone il primo giorno, forse hanno solo bisogno di un array di dimensione 20 per rappresentare quella coda, che è solo per dire ora una volta che si comincia a parlare su questi problemi di livello superiore, è possibile implementare in qualsiasi numero di modi. E c'è probabilmente solo andando a essere un compromesso nello spazio e nel tempo o semplicemente nel proprio la complessità del codice. 

Che dire di una pila? Beh, una pila, abbiamo visto anche potrebbe essere solo questi vassoi. E si potrebbe implementare questa una matrice. Ma ad un certo punto se si utilizza una matrice, cosa succederà ai vassoi si sta cercando di mettere giù? Bene. Stai andando solo a essere in grado di andare così in alto. E penso che in Mather sono effettivamente incassata in tale apertura. Così in effetti, è quasi come Mather sta usando un array di dimensioni fisse, perché è solo possibile inserire tanti vassoi in quella apertura in il muro verso il basso sotto le ginocchia della gente. E così che potrebbe essere ha detto di essere un array, ma potremmo certamente attuare tale più in generale, con una lista collegata. 

Beh, che dire un'altra struttura dati? Permettetemi di tirare su un altro visiva qui. Qualcosa di simile che ne dici di questo qui? Perché potrebbe essere utile per non avere qualcosa di sofisticato come un trie, che abbiamo visto avuto questi molto larghi nodi, ciascuno dei quali è in un array? Ma cosa succede se facciamo qualcosa di più semplicemente, come un vecchio albero di famiglia la scuola, ciascuno di cui nodi qui è solo memorizzazione di un numero. Invece di un nome o discendente è solo la memorizzazione di un numero come questo. 

Beh, il gergo usiamo in strutture di dati è entrambe le mete e alberi, dove un trie, di nuovo, è solo uno i cui nodi sono array, è ancora quello che si potrebbe utilizzare dalla scuola elementare quando hai fatto una famiglia tree-- foglie e la radice dell'albero e figli del genitori e fratelli loro. E potremmo implementare un albero, per esempio, nel modo più semplice questo. Un albero, se come un nodo, uno dei questi cerchi che ha un numero, non sta andando ad avere un puntatore, ma due. E non appena si aggiunge un secondo puntatore, è può effettivamente ora fare tipo dei dati bidimensionali strutture in memoria. Proprio come un bidimensionale array, è possibile avere tipo bidimensionale liste collegate, ma quelli che seguono un pattern dove non ci sono cicli. E 'veramente un albero con una modo nonni qui e poi alcuni genitori e figli e nipoti e pronipoti. e così via. 

Ma ciò che è veramente pulito anche su questo, solo per prendere in giro voi con un po 'di codice, richiamo ricorsione da un po 'indietro, per cui si scrive una funzione che chiama se stessa. Questa è una bella opportunità di implementare qualcosa come ricorsione, perché considerano questo. 

Questo è un albero. E io sono stato un po 'anale con il modo Ho messo i numeri interi in mezzo alla strada. Tanto che ha una speciale nome-- un albero binario di ricerca. Ora abbiamo sentito di binario la ricerca, ma anche voi lavorare a ritroso dal nome di questa cosa? Qual è il modello di come ho inserite i numeri interi in questo albero? Non è arbitrario. C'è qualche modello. Sì. 

PUBBLICO: quelli più piccoli a sinistra. 

DAVID MALAN: Sì. Quelli più piccoli sono a sinistra. Quelli più grandi sono sulla destra. Tale che un'affermazione vera è un genitore è maggiore del suo figlio sinistro, ma inferiore al suo figlio destro. E che da solo è ancora un definizione verbale ricorsiva perché si può applicare tale stessa logica ad ogni nodo e solo in battuta fuori, un caso base, se si sarà, quando si preme uno dei le foglie, per così dire, dove un congedo non ha più figli. 

Ora, come si potrebbe trovare il numero 44? Si potrebbe iniziare alla radice e dire, hm. 55 non è 44 Quindi voglio andare giusto fare o voglio andare a sinistra? Beh, ovviamente si vuole andare a sinistra. E così è proprio come il telefono libro esempio in ricerca binaria più in generale. Ma stiamo attuazione ora un po 'più dinamico di un array potrebbe consentire. E infatti, se si vuole guardare il codice, a prima vista sicuro. Si presenta come un insieme di linee. Ma è meravigliosamente semplice. Se si desidera implementare una funzione chiamata di ricerca il cui scopo nella vita è quello di cercare un valore come n, un numero intero, e il gioco è passato in uno pointer-- un puntatore al nodo delle radici, piuttosto, di detto albero da cui è possibile accedere a tutto il resto, notare come semplicemente è possibile implementare la logica. Se l'albero è nullo, ovviamente non c'è. Diciamo solo return false. Giusto? Se si passi nulla, non c'è niente lì. 

Altrimenti, se n è minore di albero freccia n-- ora freccia n, Ricordiamo abbiamo introdotto eccellente brevemente l'altro giorno, e questo significa solo de-riferimento puntatore e guardare il campo denominato n. Quindi vuol dire andare lì e guardare il campo denominato n. Quindi, se n, il valore si è dato, è meno al valore in intero alberi, dove vuoi andare? A sinistra. 

Così notare la ricorsione. Sto returning-- non è vero. Non falso. Sto tornando qualunque sia la risposta è da una chiamata a me stesso, passando nuovo un n, che è ridondante, ma ciò che è un po 'diverso ora? Come sto facendo il problema più piccolo? Sto passando come secondo argomento, non la radice dell'albero, ma il figlio sinistro in questo caso. Così sto passando il figlio sinistro. 

Nel frattempo, se n è maggiore di il nodo Attualmente sto guardando, Cerco il lato destro della strada. Altrimenti, se l'albero non è nullo, e se l'elemento non è a fianco e non è a destra, ciò che è meravigliosamente il caso? Abbiamo davvero trovato il nodo domanda, e così torniamo vero. 

Quindi, abbiamo appena scalfito la superficie Ora alcune di queste strutture di dati. Nel problema ha impostato cinque avrete esplorare questi ulteriormente, e ti verrà dato il vostro disegno scelta di come fare per questo. Quello che mi piacerebbe concludere il è solo un secondo teaser di 30 di ciò che attende la prossima settimana e oltre. 

Come abbiamo begin-- per fortuna si potrebbe think-- nostra transizione lentamente dal mondo di C e inferiori dettagli di implementazione di livello, a un mondo in cui possiamo dare per scontato che qualcun altro ha, infine, implementato questi dati strutture per noi, e inizieremo a capire la mondo reale mezzo di attuazione programmi web-based e i siti web più in generale ed anche la stessa sicurezza implicazioni che abbiamo solo cominciato a graffiare la superficie del. Ecco cosa ci aspetta nei giorni a venire. 

[RIPRODUZIONE VIDEO] 

-Ha È venuto con un messaggio, con un protocollo tutto suo. Egli è venuto per un mondo di crudele firewall, router indifferente, e pericoli di gran lunga peggiore della morte. E 'veloce. Lui è forte. E 'il protocollo TCP / IP, e lui ha il vostro indirizzo. "Guerrieri della Rete." [FINE RIPRODUZIONE VIDEO] DAVID MALAN: Settimana prossima. Vedremo allora. [RIPRODUZIONE VIDEO] -E Ora, "Pensieri profondi" da Daven Farnham. -David Inizia sempre conferenze con: "Va bene." Perché no, "Ecco la soluzione al problema di set di questa settimana " o "Stiamo dando a tutti voi un A?" [Ride] [FINE RIPRODUZIONE VIDEO]