DAVID MALAN: Va bene. Siamo tornati. Quindi, in questo segmento sulla programmazione quello Ho pensato di fare è un mix di cose. Uno, fare un po ' di qualcosa di hands-on, anche se con un più giocoso environment-- programmazione uno che è dimostrativo esattamente il tipo di idee abbiamo parlato, ma un po 'più formale. Due, un'occhiata ad alcune delle modi più tecnici che un programmatore potrebbe effettivamente risolvere problemi come il problema ricerca che abbiamo guardato prima e anche una più fondamentalmente interessante problema di ordinare. 

Abbiamo appena assunto da ottenere andare che tale rubrica è stato risolto, ma che da sola è in realtà una specie di problema difficile con molti modi diversi per risolverlo. Così useremo questi come una classe di problemi rappresentante di cose che potrebbe essere risolto in generale. E poi parleremo circa in dettaglio cosa sono chiamati dati structures-- modi fantasiosi come le liste collegate e tabelle hash e alberi che un programmatore sarebbe in realtà utilizzare e generalmente usare su una lavagna per dipingere una foto di quello che lui o lei prevede per l'attuazione qualche pezzo di software. 

Allora, facciamo gli hands-on parte prima. Quindi, solo mettere le mani sporche con una ambiente chiamato scratch.mit.edu. Questo è uno strumento che usiamo nella nostra classe di laurea. Anche se è stato progettato per le età 12 anni in su, lo usiamo per il up parte di quel piuttosto un po ' dal momento che è una bella, divertente modo grafico di apprendimento un po 'qualcosa sulla programmazione. Quindi testa a questo URL, dove si dovrebbe vedere una pagina abbastanza come questo, e andare avanti e fare clic Partecipa Scratch in alto a destra e scegliere un nome utente e una la password e, infine, farti un scratch.mit.edu account--. Ho pensato di usare questo come possibilità prima di mostrare questo. Una domanda si avvicinò durante la pausa su quale codice si presenta come. E parlavamo durante la pausa su C, in particolare una particular-- livello più basso in un linguaggio più vecchio. E ho appena fatto un rapido Google cerca di trovare il codice C per la ricerca binaria, l'algoritmo che utilizzato per la ricerca che rubrica in precedenza. Questo esempio particolare, naturalmente, non cercare una rubrica telefonica. E 'appena cerca un insieme di numeri nella memoria del computer. Ma se si desidera solo ottenere una visuale senso di ciò che una programmazione vera e propria il linguaggio sembra, sembra un po 'di qualcosa come questo. Quindi si tratta di 20-plus, Circa 30 righe di codice, ma la conversazione che abbiamo stavano avendo più di pausa era circa come questo in realtà viene trasformato in zero e uno e se non si può semplicemente tornare che elaborare e passare da zeri e quelli tornare al codice. 

Purtroppo, il processo è così trasformativa che è molto più facile a dirsi che a farsi. Sono andato avanti e realtà si quel programma, Binary Search, in zero e uno, sotto forma di programma chiamato al compilatore che ho capita di avere qui a destra sul mio Mac. E se si guarda lo schermo qui, concentrandosi in particolare nelle centrali sei colonne soltanto, vedrete solo zero e uno. E questi sono gli zeri e quelli che comporre esattamente questo programma di ricerca. 

E così ogni pezzo di cinque bit, ogni byte di zero e uno qui, rappresentare una certa istruzione tipicamente all'interno di un computer. E infatti, se hai sentito il commercializzazione slogan "Intel inside" - che, Naturalmente, solo significa avere un CPU Intel o il cervello all'interno del computer. E che cosa significa essere una CPU è che si dispone di un set di istruzioni, per così dire. 

Ogni CPU nel mondo, molti li ha fatti da Intel in questi giorni, comprende un finita numero di istruzioni. E tali istruzioni sono così basso livello come aggiungere questi due numeri insieme, moltiplicare questi due numeri insieme, spostare questo pezzo di dati da qui di qui nella memoria, salvare questo informazioni da qui a qui in memoria, e così forth-- quindi molto, molto di basso livello, i dettagli quasi elettroniche. Ma con quelle matematica operazioni accoppiato con quello che abbiamo discusso in precedenza, la rappresentazione dei dati come zero e uno, in grado di si costruisce tutto che un computer può fare oggi, se è testuale, grafico, musicale, o altrimenti. 

Quindi questo è molto facile da ottenere ha perso le erbacce di fretta. E ci sono un sacco di sfide sintattiche per cui se si effettua il più semplice, più stupida di errori di battitura nessuno del programma funzionerà sorta. E così invece di utilizzare un linguaggio come C questa mattina, Ho pensato che sarebbe stato più divertente da fare in realtà qualcosa più visivo, che mentre progettato per i bambini è in realtà una manifestazione perfetta di programmazione vera Language, guarda caso utilizzare le immagini al posto del testo per rappresentare quelle idee. 

Quindi, una volta che hai davvero un account su scratch.mit.edu, fare clic sul pulsante Crea in alto a sinistra del sito. E si dovrebbe vedere un ambiente come quello che sto per vedere sul mio schermo Qui. E passeremo solo un po ' po 'di tempo a giocare qui. Vediamo se non possiamo tutti risolvere alcuni problemi insieme nel modo seguente. 

Quindi, quello che vedrete in questo environment-- e in realtà solo lasciare Mi pausa. C'è qualcuno che non qui? Non qui? OK. Quindi, vorrei sottolineare un paio di caratteristiche di questo ambiente. 

Così in alto a sinistra dello schermo, abbiamo hanno fase di Scratch, per così dire. Scratch non è solo il nome di questo linguaggio di programmazione; è anche il nome del gatto che vedete di default lì in arancione. È su un palco, così proprio come ho descritto la tartaruga in precedenza come essere in un rettangolare ambiente bordo bianco. Il mondo di questo gatto è limitato interamente a quel rettangolo sulla parte superiore là. 

Nel frattempo, sulla destra lato qui, è solo una zona di script, un tabula rasa, se vuoi. Questo è dove stiamo andando a scrivere I nostri programmi in un attimo. E i mattoni che saremo utilizzare per scrivere le program-- il puzzle pezzi, se siete will-- quelli proprio qui in mezzo, e sono categorizzati per funzionalità. Così, per esempio, ho intenzione di andare avanti e dimostrare almeno uno di questi. Ho intenzione di andare avanti e fare clic la categoria di controllo sulla parte superiore. 

Quindi queste sono le categorie sulla parte superiore. Ho intenzione di fare clic sulla categoria di controllo. Piuttosto, ho intenzione di fare clic sui Events categoria, il primo uno fino all'inizio. E se si desidera seguire anche come facciamo questo, sei abbastanza benvenuto a. Ho intenzione di fare clic e trascinare questo primo, "quando la bandiera verde cliccato." E poi ho intenzione di rilasciarlo solo grosso modo nella parte superiore del mio tabula rasa. 

E ciò che è bello di Scratch è che questo pezzo di puzzle, in cui asservito Puzzle pezzi, sta per fare letteralmente ciò che questi pezzi del puzzle dicono di fare. Così, per esempio, Scratch è giusto Ora nel mezzo del suo mondo. Ho intenzione di andare avanti e scegliere ora, diciamo, la categoria di movimento, se si desidera fare il stesso-- categoria Motion. E ora ho notato un intero mucchio di pezzi del puzzle qui che, ancora una volta, tipo di fare quello che dicono. E ho intenzione di andare avanti e trascinare e far cadere il blocco mossa giusta qui. 

E notare che, non appena si ottiene vicino al fondo della "bandiera verde cliccato "button, avviso come appare una linea bianca, come se fosse quasi magnetico, si vuole andare lì. Basta lasciarsi andare, e si aggancerà insieme e le forme corrisponderanno. E ora si può forse quasi indovinare dove stiamo andando con questo. 

Se si guarda alla fase Scratch qui e guardare al di sopra di esso, si vedrà una luce rossa, un Segnale di stop, e una bandiera verde. E ho intenzione di andare avanti e guardare i miei screen-- solo per un momento, se si potesse. Ho intenzione di fare clic sul bandiera verde in questo momento, e si è trasferito quello che sembra essere 10 passi o 10 pixel, 10 punti, sullo schermo. 

E quindi non così eccitante, ma mi permetta di proporre senza nemmeno insegnare questo, basta utilizzando il proprio il proprio let intuition-- mi propongo a capire come rendere Scratch passeggiata proprio dal palco. Hanno lo far posto sul lato destro della schermo, fino a destra. Lasciate che vi dia un attimo o giù di lì a lottare con quella. Si potrebbe voler dare un'occhiata in altre categorie di blocchi. Tutto ok. Quindi, solo per ricapitolare, quando abbiamo la bandiera verde cliccato qui e spostare 10 passi è la unica istruzione, ogni volta che cliccare la bandiera verde, cosa sta succedendo? Beh, questo è il mio programma in esecuzione. Così ho potuto fare questo forse 10 volte manualmente, ma questo si sente un po ' po 'hacker, per così dire, per cui io non sono davvero risolvere il problema. Sto solo cercando di nuovo e Ancora e ancora e ancora fino a quando ho sorta di accidentalmente conseguire la direttiva che ho deciso di raggiungere in precedenza. 

Ma sappiamo dalla nostra pseudocodice in precedenza che non c'è questo concetto nella programmazione di looping, fare qualcosa di nuovo e di nuovo. E così ho visto che un po 'di te raggiunto per pezzo ciò puzzle? Ripetere l'operazione fino a quando. Così abbiamo potuto fare qualcosa come ripetere fino a quando. E che cosa si ripete fino a quando esattamente? 

OK. E mi permetta di andare con uno che è un po 'più semplice solo per un momento. Mi permetta di andare avanti e fare questo. Si noti che, come si può avere scoperto sotto controllo, c'è questo blocco di ripetizione, che non sembra che sia così grande. Non c'è molto spazio nel tra queste due linee gialle. Ma, come alcuni di voi potrebbero avere notato, se si trascina e goccia, notare come cresce per riempire la forma. 

E si può anche riempire di più. Sarà solo continuare a crescere se si trascina e si posiziona il mouse sopra di esso. E io non so che cosa è meglio qui, in modo da lasciare me almeno ripetere cinque volte, per esempio, e poi tornare alla fase e cliccare la bandiera verde. E ora notate che non è del tutto lì. 

Ora alcuni di voi proposti, come Victoria ha appena fatto, ripetere 10 volte. E che fa in genere lui ottenere tutta la strada, ma non sarebbe esserci una più robusta modo di arbitrariamente capire il numero di mosse per fare? Quale potrebbe essere un blocco di meglio che ripetere 10 volte essere? 

Sì, così perché non fare qualcosa per sempre? E ora mi permetta di spostare questo pezzo di puzzle all'interno vi e sbarazzarsi di questo. Ora notate, non importa dove Scratch inizia, va a bordo. E per fortuna MIT, che fa Scratch, basta si assicura che non ha mai scompare completamente. È sempre possibile afferrare la coda. 

E proprio in modo intuitivo, perché egli continuare a muoversi? Che cosa sta succedendo qui? Egli sembra essersi fermato, ma poi se prendo in mano e trascinare lui continua a voler andare laggiù. Perché? In verità, un computer è letteralmente andando a fare quello che gli si dice di fare. Quindi, se hai detto in precedenza fare il cosa seguente per sempre, spostare 10 passi, sta andando a andare avanti e andare fino a quando mi ha colpito il segnale di stop rosso e arrestare il programma del tutto. 

Quindi, anche se non si è fare questo, come potrei rendere Scratch si muovono più velocemente attraverso lo schermo? Ulteriori passi, giusto? Così, invece di fare 10 in un momento, perché non andare avanti e cambiare a-- cosa vorresti propose-- 50? Così ora ho intenzione di fare clic sul verde bandiera, e anzi, se ne va veramente veloce. 

E questo, naturalmente, è solo una manifestazione di animazione. Che cosa è l'animazione? E 'solo che vi mostra l'un essere umano intero gruppo di immagini fisse in realtà, molto, molto veloce. E così, se stiamo solo dicendo di muoversi più passaggi, stiamo solo avendo l'effetto sia di il cambiamento dove si trova sullo schermo tanto più rapidamente per unità di tempo. 

Ora la prossima sfida che ho proposto era quello di avere lui rimbalzare fuori dal bordo. E senza sapere che cosa di puzzle pezzi exist-- perché va bene se non si arriva alla fase del challenge-- cosa cosa vuoi fare in modo intuitivo? Come avremmo lo rimbalzare e via, tra la sinistra e la destra? 

Sì. Quindi abbiamo bisogno di un qualche tipo di condizioni, e sembrano avere condizionali, per così parlare, sotto la categoria di controllo. Quale di questi blocchi Non probabilmente vogliamo? Sì, forse "se, allora." Quindi notare che tra i blocchi gialli abbiamo qui, c'è questo "se" o questo "se, altrimenti" blocco che sarà ci permettono di prendere una decisione di fare questo o per farlo. E si può anche nidificarli di fare più cose. Oppure, se non sei ancora andato qui, andare avanti alla categoria Sensing e- vediamo se è qui. 

Allora, cosa blocco potrebbe essere utile qui per rilevare se è dal palco? Sì, notare che alcuni di questi blocchi possono essere parametrizzate, per così dire. Essi possono essere una sorta di personalizzati, non a differenza di HTML ieri con gli attributi, dove questi attributi tipo di personalizzare il comportamento di un tag. Allo stesso modo qui, posso afferrare questa toccante blocco e il cambiamento e porre la domanda, stai toccando il mouse puntatore come il cursore o stai toccando il bordo? 

Quindi, mi permetta di andare e fare questo. Ho intenzione di diminuire per un istante. Mi permetta di afferrare questo pezzo di puzzle qui, questo pezzo di puzzle questo, e ho intenzione di jumble li solo per un momento. Ho intenzione di spostare questo, cambiare questo a bordo toccante, e ho intenzione di fare questo movimento. Quindi, ecco alcuni ingredienti. Credo di aver avuto tutto quello che voglio. 

Qualcuno vuole proporre come mi può collegare questi forse dall'alto verso il basso al fine di risolvere il problema di avere Scratch mossa da destra a sinistra a destra per da sinistra a destra a sinistra, ciascun tempo solo rimbalzare il muro? Cosa voglio fare? Quale blocco dovrei connettersi al "Flag quando verde cliccato prima"? 

Ok, cominciamo con il "per sempre". Ciò che va dentro dopo? Qualcun altro. OK, spostare passi. Tutto ok. Allora che cosa? Allora il caso. E si noti, anche se sembra intramezzato insieme ermeticamente, sarà solo crescere fino a riempire. Sarà solo saltare in cui lo voglio. 

E che cosa ho messo tra il caso e l'allora? Probabilmente "se toccando bordo." E notate, ancora una volta, è troppo grande per questo, ma che crescerà da riempire. E poi girare di 15 gradi? Quanti gradi? Sì, così 180 girerà mi tutto intorno. Così vediamo se ho ottenuto questo diritto. Mi permetta di diminuire. 

Mi permetta di trascinare Scratch up. Quindi è un po 'distorta ora, ma va bene. Come l'ho ripristinare facilmente? Ho intenzione di barare un po '. Così sto aggiungendo un altro blocco, tanto per essere chiari. Voglio che al punto 90 gradi a destra per impostazione predefinita, quindi sto solo andando a dirglielo per fare questo livello di programmazione. E qui andiamo. Sembra che abbiamo fatto. E 'un po' strano, perché sta camminando a testa in giù. Chiamiamolo un bug. Questo è un errore. Un bug è un errore in un programma, un errore logico che io, l'umano, fatto. Perché sta andando a testa in giù? Ha MIT vite o fatto io? 

Sì, voglio dire, non è il MIT di colpa. Mi hanno dato un pezzo di puzzle che dice girare qualche numero di gradi. E su suggerimento di Victoria, Sto girando di 180 gradi, che è l'intuizione giusta. Ma girando di 180 gradi letteralmente mezzi rotazione di 180 gradi, e che non è proprio quello che voglio, a quanto pare. Perché almeno lui è in questo mondo bidimensionale, quindi svolta sta realmente accadendo di capovolgere lo testa in giù. 

Probabilmente voglio usare quello blocco invece, in base a ciò che si vede qui? Come possiamo risolvere questo problema? Sì, così abbiamo potuto puntare nella direzione opposta. E in realtà, anche questo è Non sarà sufficiente, perché possiamo solo codificare di puntamento di sinistra o di destra. 

Sai cosa potremmo fare? Sembra che abbiamo un blocco convenienza qui. Se io zoom avanti, vedi qualcosa che ci piace qui? Così sembra che il MIT ha una astrazione costruito qui. Questo blocco sembra essere equivalente in cui altri blocchi, plurale? 

Questo blocco sembra essere equivalente a tutto questo trio di blocchi che abbiamo qui. Così si scopre che posso semplificare la mia Programma per sbarazzarsi di tutto questo e appena messo questo qui. E ora è ancora un po ' buggy, e va bene per ora. Lasceremo che si tratti. Ma il mio programma è anche semplice, e anche questo, sarebbe rappresentativo di un obiettivo in programming-- è quello di rendere idealmente il codice come semplice, più compatto possibile, pur essendo come leggibili possibile. Non si vuole fare in modo succinto che è difficile da capire. 

Ma accorgo Ho sostituito tre blocchi con uno, e questo è senza dubbio una buona cosa. Ho astratte via la nozione di verificare se si è sul bordo con un solo isolato. Ora siamo in grado di divertirsi con questo, in effetti. Questo non aggiunge tanto valore intellettuale, ma il valore ludico. Ho intenzione di andare avanti e afferrare questo suono qui. Quindi, mi permetta di andare avanti, e mi lascio arrestare il programma per un momento. Ho intenzione di registrare il seguito, permettendo l'accesso al mio microfono. 

Eccoci qui. Ahia. Proviamo di nuovo. Eccoci qui. OK, ho registrato la cosa sbagliata. Eccoci qui. Ahia. Ahia. Tutto ok. Ora ho bisogno di sbarazzarsi di quella. Tutto ok. 

Così ora ho un la registrazione di soli "ahi". Così ora ho intenzione di andare avanti e chiamare questo "ahi". Ho intenzione di tornare indietro ai miei script, e ora avviso c'è questo blocco che si chiama riprodurre l'audio "meow" o riprodurre il suono "ahi". Ho intenzione di trascinare questo, e dove dovrei mettere questo per effetto comico? Sì, così ora è una specie di buggy, perché ora questo block-- notare come questo "se sul bordo, rimbalzo "è una specie di self-contained. Quindi ho bisogno di risolvere questo problema. Mi permetta di andare avanti e fare questo. Mi permetta di liberarsi di questo e torno al nostro originale, più deliberata funzionalità. Quindi, "se toccando bordo, poi" Voglio a girare, come Victoria proposto, 180 gradi. E voglio giocare il suono "ahi" lì? 

Sì, si noti che è al di fuori quel blocco giallo. Quindi anche questo sarebbe un bug, ma ho notato. Quindi ho intenzione di trascinarla fino qui, e l'avviso ora è all'interno del "se". Quindi, il "se" è questo tipo di come macchia braccio-like che è solo andare a fare ciò che è all'interno di esso. Così ora se io diminuire a il rischio di annoying-- 

COMPUTER: Ahi, ahi, ahi. 

DAVID MALAN: E sarà solo andare avanti per sempre. Ora basta per accelerare le cose qui, mi permetta di andare avanti e di aprire, cerchiamo di say-- mi permetta di andare in qualche della mia roba dalla classe. E mi permetta di aprire, diciamo, questo quella fatta da uno dei nostri compagni di insegnamento un paio d'anni fa. Così alcuni di voi potrebbe ricordare questo gioco da altri tempi, e in realtà è notevole. Anche se abbiamo fatto la più semplice dei programmi in questo momento, prendiamo in considerazione ciò che questo si presenta come. Mi ha colpito il gioco. 

Quindi, in questo gioco, abbiamo un rana, e utilizzando la freccia keys-- prende grandi passi di me remember-- Ho il controllo su questa rana. E l'obiettivo è quello di ottenere attraverso il occupato strada senza incorrere in auto. E cerchiamo di see-- se vado qui, mi aspettare per un registro a scorrimento da. Questo si sente come un insetto. Questa è una specie di insetto. Tutto ok. Sono su questo qui, lì, e poi si mantiene andare fino ad arrivare tutti le rane alle ninfee. Ora questo potrebbe sembrare tanto più complessa, ma proviamo a rompere questo in giù mentalmente e verbalmente nei suoi blocchi che lo compongono. Quindi c'è probabilmente un puzzle pezzo che non abbiamo ancora visto ma questo è rispondere alle combinazioni di tasti, a cose mi ha colpito sulla tastiera. 

Quindi c'è probabilmente un qualche tipo di blocco che dice, se la chiave è uguale up, poi fare qualcosa con Scratch-- forse spostarlo 10 passi in questo modo. Se si preme il tasto premuto, spostare 10 passi in questo modo, o il tasto sinistro, spostare 10 passi in questo modo, 10 passi che. Ho chiaramente trasformato il gatto in una rana. Ecco, questo è proprio dove il costume, come le chiamate Scratch it-- noi appena importato una foto della rana. 

Ma che altro sta accadendo? Quali altre linee di codice, ciò che gli altri pezzi del puzzle ha fatto Blake, il nostro insegnamento collega, usare in questo programma, a quanto pare? Cosa sta facendo tutto move-- Che tipo di programmazione costruire? 

Movimento, in modo che il sure-- muoversi blocco, di sicuro. E che cosa è quel blocco mossa interno, più probabile? Sì, una specie di loop, forse un sempre bloccare, forse una ripetizione block-- ripetere fino a blocco. Ed è quello che sta facendo i tronchi e le ninfee e tutto il resto mossa avanti e indietro. E 'solo accadendo all'infinito. 

Perché alcune delle vetture muoversi più velocemente rispetto agli altri? Qual è la differenza quei programmi? Sì, probabilmente alcuni di loro stanno prendendo più passi contemporaneamente e alcuni di essi minor numero di passaggi in una sola volta. E l'effetto visivo è veloce contro lento. 

Cosa ne pensi successo? Quando ho ottenuto il mio rana tutta la strada dall'altra parte della strada e il fiume sulla ninfea, qualcosa degno di nota è accaduto. Che cosa è successo, non appena l'ho fatto? Si fermò. Quella rana fermato, e Ho avuto un secondo rana. Allora, cosa costrutto deve essere ci utilizzato, quale funzione? 

Sì, così c'è qualche tipo di "Se" condizione lassù, anche. E si scopre fuori-- non abbiamo visto questo-- ma ci sono altri blocchi in là che può dire, se toccando un'altra cosa sullo schermo, se si sta toccando il pad giglio ", quindi." E poi in quel momento che abbiamo far apparire la seconda rana. Così, anche se questo gioco è certamente molto datato, anche se a prima vista c'è così tanto andare on-- e Blake non montare questo in due minuti, probabilmente ha preso lui diversi ore per creare questo gioco basato sulla sua memoria o video della versione di ieri di esso. Ma tutte queste piccole cose andare sullo schermo in isolamento riducono a questi molto semplice movimenti constructs-- o dichiarazioni come abbiamo discusso, loop e le condizioni, e che su di esso. Ci sono alcune altre caratteristiche amatore. Alcuni di loro sono puramente estetica o acustico, come i suoni Ho appena giocato con. Ma per la maggior parte, si avere in questa lingua, Scratch, tutto della fondamentale blocchi che si avere in C, Java, JavaScript, PHP, Ruby, Python, e qualsiasi numero di altre lingue. Tutte le domande circa zero? Tutto ok. Quindi non ci immergersi in profondità a Scratch, se sei il benvenuto in questo fine settimana, soprattutto se avete bambini o nipoti e così via, per far loro conoscere Scratch. In realtà è una meravigliosamente giocoso ambiente, come dicono i suoi autori, soffitti molto alti. Anche se abbiamo iniziato con molto dettagli di basso livello, si può davvero fare un bel po ' con esso, e questo è forse una dimostrazione di esattamente questo. 

Ma veniamo ora alla transizione un po ' problemi sofisticati, se si vuole, conosciuto come "ricerca" e "Smistamento", più in generale. Abbiamo avuto questa rubrica earlier-- ecco un altro solo per discussion-- che siamo stati in grado di cercare in modo più efficiente perché di un'assunzione significativa. E tanto per essere chiari, cosa ipotesi era che fare durante la ricerca attraverso questa rubrica? Che Mike Smith era in la rubrica telefonica, anche se sarebbe in grado di gestire lo scenario senza di lui lì se ho appena fermato prematuramente. Il libro è alfabetico. E questo è un molto generoso ipotesi, perché significa someone-- Sono un po ' di tagliare un angolo, come io sono più veloce perché qualcuno altro ha fatto un sacco di duro lavoro per me. 

Ma cosa succede se il telefono libro sono stati non ordinato? Forse Verizon ha pigri, appena buttato i nomi ei numeri di tutti in là forse nell'ordine in cui firmato per il servizio telefonico. E quanto tempo ci vuole me di trovare qualcuno come Mike Smith? 1.000 Pagina telefono book-- quanti pagine devo guardare attraverso? 

Tutti loro. Sei una sorta di fuori di fortuna. È letteralmente deve guardare ad ogni pagina se la rubrica è solo ordinati in modo casuale. Si potrebbe ottenere fortunati e trovare Mike sulla prima pagina, perché è stato il primo cliente di ordinare il servizio telefonico. Ma avrebbe potuto essere l'ultimo, anche. 

Quindi ordine casuale non è buona. Quindi supponiamo di avere per ordinare la rubrica o nei dati generali sorta che ci è stata data. Come possiamo farlo? 

Beh, vorrei solo provare un semplice esempio qui. Lasciami andare avanti e lanciare una alcuni numeri sul tabellone. Supponiamo che i numeri che abbiamo sono, diciamo, quattro, due, uno, e tre. E, Ben, ordinare questi numeri per noi. 

Ok bene. Come hai fatto? Tutto ok. Così inizia con il più piccolo il valore e la più alta, E questo è davvero un buon intuito. E rendersi conto che noi gli esseri umani sono in realtà piuttosto bravo a risolvere i problemi così, almeno quando i dati è relativamente piccolo. Non appena si inizia ad avere centinaia di numeri, migliaia di numeri, milioni di numeri, Ben probabilmente non poteva fare abbastanza così veloce, supponendo che c'erano lacune nei numeri. Abbastanza facile a contare fino a un milione tuttavia, solo tempo. 

Così l'algoritmo suona come Ben utilizzato solo ora era ricerca del numero più piccolo. Così, anche se noi umani possiamo prendere in molte informazioni visivamente, un computer è in realtà un po 'più limitata. Il computer può solo guardare un byte alla volta o forse quattro byte alla tempo-- in questi giorni forse 8 byte alla tempo-- ma un numero molto piccolo di byte in un determinato momento. 

Quindi, dato che abbiamo davvero quattro valori separati qui-- e si può pensare di Ben come avere paraocchi se fosse un computer, quali che non riesce a vedere niente altro di un numero alla tempo-- così abbiamo generalmente assumeremo, come in Inglese, faremo leggere da destra a sinistra. Quindi, il primo numero di Ben probabilmente guardato a quattro anni e quindi molto rapidamente sono resi conto che è una bella grande number-- mi permetta di continuare a cercare. 

Ce ne sono due. Apetta un minuto. Due è inferiore a quattro. Ho intenzione di ricordare. Due è ora il più piccolo. Ora tra-- che è ancora meglio. Questo è ancora più piccolo. Ho intenzione di dimenticare due e solo ricordare uno ora. 

E poteva smettere di guardare? Beh, poteva basato su queste informazioni, ma avrebbe fatto meglio a ricerca il resto della lista. Perché quello che se lo zero erano nella lista? Che cosa succede se uno fosse negativo nella lista? Sa solo che la sua risposta è corretto se è esaurientemente controllato l'intera lista. Quindi guardiamo il resto di questo. Sulle tre ruote che era una perdita di tempo. Got sfortunato, ma ero ancora corretta per farlo. E così ora lui presumibilmente selezionato il numero più piccolo e appena messo all'inizio della lista, come farò qui. Ora che cosa hai fatto dopo, anche se non hai pensato a questo proposito quasi in questa misura? Ripetere il processo, così una sorta di loop. C'è un'idea familiare. Così qui è quattro. Questo è attualmente il più piccolo. Questo è un candidato. Non più. Ora che ho visto due. Questo è l'elemento immediatamente inferiore. Sulle tre ruote che non è più piccolo, in modo da ora Ben può strappare i due. 

Ed ora si ripete il processo e naturalmente tre viene tirato fuori il prossimo. Ripetere il processo. Quattro viene tirato fuori. E ora siamo fuori di numeri, così la lista deve essere ordinato. 

Ed in effetti, questo è un algoritmo convenzionale. Uno scienziato computer sarebbe chiamare questa "selezione tipo," l'idea è sorta una elencare iteratively-- di nuovo e ancora e ancora selezionando il numero più piccolo. E che cosa è bella è è proprio così maledettamente intuitivo. E 'così semplice. E si può ripetere lo stesso operazione più e più volte. È semplice. 

In questo caso è stato veloce, ma Quanto tempo è effettivamente prendere? Facciamo sembrare e sentire un po 'più noioso. Quindi uno, due, tre, quattro, cinque sei, sette, otto, nove, 10, 11, 12, 13, 14, 15, 16-- numero arbitrario. Volevo solo più questo tempo che solo il quattro. Quindi, se ho un intero po 'di numeri now-- esso Non importa nemmeno quello che are-- di lasciare pensare a ciò che questo algoritmo è veramente. 

Supponiamo che ci siano i numeri là. Anche in questo caso, non importa cosa essi sono, ma sono casuali. Mi candido algoritmo di Ben. Ho bisogno di selezionare il numero più piccolo. Cosa faccio? E ho intenzione di fisicamente farlo in questo momento di agire fuori. Guardando, guardando, guardando, guardando, guardando. Solo il tempo arrivare a la fine della lista può Mi rendo conto che il più piccolo numero era di due questa volta. Uno non è nella lista. Così ho messo giù due. 

Cosa faccio adesso? Guardando, guardando, guardando, guardando. Ora ho trovato il numero sette, perché ci sono lacune in questi numbers-- ma semplicemente arbitrario. Tutto ok. Così ora posso mettere giù sette. Guardando guardando, guardando. 

Ora sto assumendo, di Naturalmente, che Ben non avere RAM in più, in più memoria, perché, ovviamente, Sto guardando lo stesso numero. Sicuramente avrei potuto ricordato tutti questi numeri, e questo è assolutamente vero. Ma se Ben si ricorda tutto dei numeri che ha visto, egli non ha fatto davvero il progresso fondamentale perché ha già la capacità di ricerca i numeri sul tabellone. Ricordando tutte le numeri non aiuta, perché egli può ancora come un computer solo guardare, abbiamo detto, un numero Al tempo. Quindi non c'è nessun tipo di frode lì che è possibile sfruttare. 

Quindi, in realtà, come ho continuare a cercare la lista, Ho letteralmente devo solo andare avanti avanti e indietro attraverso di essa, la spiumatura fuori il prossimo numero più piccolo. E come si può tipo di inferire dai miei movimenti stupidi, questo appena diventa molto noioso molto rapidamente, e mi sembra di andare indietro e indietro, avanti e indietro un bel po '. Ora, per essere onesti, non ho andare altrettanto, bene, cerchiamo di see-- ad essere onesti, Non devo camminare molto il maggior numero di passaggi ogni volta. Poiché, ovviamente, come ho selezionare i numeri dalla lista, la lista restante è sempre più breve. 

E così pensiamo quanti passi sono in realtà scarpinare attraverso ogni volta. Nella prima situazione abbiamo avuto 16 numeri, e così maximally-- facciamo solo fare questo per un discussion-- Ho dovuto guardare attraverso 16 i numeri per trovare il più piccolo. Ma una volta che ho strappato il numero più piccolo, come lungo era la lista restante, naturalmente? Solo 15. Così come molti numeri DID Ben o ho a guardare attraverso la seconda volta? 15, solo per andare a trovare il più piccolo. Ma ora, naturalmente, l'elenco è, Anche, più piccolo di quanto non fosse prima. Così come molti passi ho fatto prendere la prossima volta? 14 e poi 13 e poi 12, più punti, dot, dot, fino a quando io sono rimasto con una sola. Così ora un informatico sarebbe chiedere, beh, che cosa tutti uguali? In realtà è uguale a un po 'di cemento numero che potremmo certamente facciamo aritmeticamente, ma vogliamo parlare sull'efficienza degli algoritmi un po 'più formulaically, indipendentemente dal tempo la lista è. 

E così sai cosa? Questo è 16, ma, come ho detto prima, facciamo solo chiamare la dimensione del problema n, dove n è un numero. Forse è il 16, forse è tre, forse si tratta di un milione. Non lo so. Non mi interessa. Quello che voglio davvero è una formula che posso utilizzare per confrontare questo algoritmo contro altri algoritmi che qualcuno potrebbe affermare sono meglio o peggio. 

Così si scopre, e solo io conoscere questo dalla scuola elementare, che questo effettivamente funziona allo stesso cosa come N su n più uno più di due. E questo accade per uguagliare, di Naturalmente, n al quadrato più n più di due. Quindi, se volevo una formula per quanti passi sono stati coinvolti in guardando tutti di questi numeri ancora e ancora e ancora e ancora, direi è n al quadrato più n più di due. Ma sai una cosa? Questo sembra proprio disordinato. Ho solo voglia di un il senso generale delle cose. E si potrebbe ricordare da liceo che non ci è il concetto di massima termine di ordine. Quale di questi termini, la n quadrato, n, o la metà, ha il maggiore impatto nel corso del tempo? Più grande è n ottiene, che della maggior parte tali questioni? 

In altre parole, se collego su un milione, n quadrato sta per essere più probabile il fattore dominante, perché un milione di volte è di per sé molto più grande di più un ulteriore milione. Allora sai cosa? Questo è un grande maledettamente numero se si piazza un numero. Questo non ha molta importanza. Stiamo solo andando croce che fuori e non pensarci più. E così un informatico direbbe che l'efficienza di questo algoritmo è dell'ordine di n squared-- Voglio dire veramente una approssimazione. E 'una sorta di circa n al quadrato. Nel corso del tempo, il più grande e più grande n ottiene, questo è una buona stima per quello che la efficienza o mancanza di efficienza di questo algoritmo è in realtà. E derivo che, naturalmente, dalla realtà facendo due conti. Ma ora sto solo agitando le mie mani, perché ho appena vuole un senso generale di questo algoritmo. 

Quindi, utilizzando la stessa logica, nel frattempo, prendiamo in considerazione un altro algoritmo abbiamo già guardato at-- ricerca lineare. Quando ero alla ricerca per il telefono book-- Non smistamento, ricerca attraverso il telefono book-- abbiamo mantenuto dicendo che era 1.000 passi, o 500 passi. Ma cerchiamo di generalizzare questo. Se c'è n pagine l'elenco telefonico, che cosa è il tempo di esecuzione o efficienza della ricerca lineare? È nell'ordine di quanti passi per trovare Mike Smith utilizzando ricerca lineare, la primo algoritmo, o anche la seconda? 

Nel caso peggiore, Mike è alla fine del libro. Quindi, se il libro telefono è dotato di 1.000 pagine, abbiamo detto l'ultima volta, nel caso peggiore, potrebbe richiedere più o meno come molte pagine per trovare Mike? Come 1.000. Si tratta di un limite superiore. E 'una situazione peggiore possibile. Ma ancora una volta, ci stiamo allontanando da numeri come 1.000 ora. E 'solo n. 

Quindi qual è la conclusione logica? Trovare Mike in un telefono libro che ha pagine n potrebbe prendere, nel caso peggiore, quanti passi dell'ordine di n? E in effetti un computer scienziato direbbe che il tempo di esecuzione, o le prestazioni o l'efficienza o inefficienza, di un algoritmo simile una ricerca lineare è dell'ordine di n. E siamo in grado di applicare la stessa la logica di attraversare qualcosa come ho appena fatto al secondo algoritmo che abbiamo avuto con la rubrica telefonica, dove siamo andati due pagine alla volta. 

Così 1.000 Pagina rubrica telefonica potrebbe portarci 500 Page turno, più uno se raddoppiamo un po 'indietro. Quindi, se un libro telefono è dotato di n pagine, ma stiamo facendo due pagine alla volta, questo è più o meno quello che? N più di due, in modo che è come n più di due. Ma ho fatto la richiesta di un momento fa che n sopra two-- questo è il tipo dello stesso come proprio n. E 'solo un fattore costante, gli informatici direbbero. Concentriamoci solo sul le variabili, really-- maggiori variabili nell'equazione. 

ricerca in modo lineare, sia fatta una pagina alla volta o due pagine alla volta, è una sorta di fondamentalmente lo stesso. È ancora dell'ordine di n. Ma ho sostenuto con la mia immagine precedente che il terzo algoritmo non era lineare. Non era una linea retta. Era quella linea curva, e la formula algebrica c'era quello che? Log di n-- così logaritmo in base due di n. E noi non dobbiamo andare in troppo più dettagli su logaritmi oggi, ma la maggior parte degli scienziati informatici no anche dirvi ciò che la base è. Perché è tutto solo fattori costanti, per così dire, solo lievi differenze numeriche. E quindi questo sarebbe molto comune modo per il calcolatore particolarmente formale gli scienziati ad una scheda o programmatori di un bordo bianco in realtà sostenendo che algoritmo userebbero o che l'efficienza del loro algoritmo è. 

E questo non è necessariamente qualcosa si discute in qualsiasi grande dettaglio, ma un buon programmatore è qualcuno che ha un solido, sfondo formale. E 'in grado di parlare di in questo tipo di strada e effettivamente fare argomenti qualitativi come il motivo per cui un algoritmo o un pezzo di software è superiore in un modo all'altro. Perché si potrebbe certamente basta eseguire il programma di una persona e contare il numero di secondi che serve per ordinare alcuni numeri, e si può eseguire alcuni Il programma di altra persona e contare il numero di secondi necessari. Ma questo è un modo più generale che è possibile utilizzare per analizzare gli algoritmi, se si vuole, basta su carta o solo verbalmente. Senza nemmeno in esecuzione, senza anche cercando ingressi di esempio, si può solo ragionare attraverso di essa. E così con l'assunzione di uno sviluppatore o se avere lui o lei sorta di discutere a voi perché il loro algoritmo, il loro segreto salsa per la ricerca miliardi di pagine web per la tua azienda è meglio, questi sono i tipi di argomenti che dovrebbe idealmente in grado di fare. O almeno queste sono il tipo di cose che sarebbe venuto in discussione, a almeno in una discussione molto formale. Tutto ok. Così Ben proposto qualcosa chiamato selection sort. Ma ho intenzione di proporre che non c'è altri modi per farlo, troppo. Quello che non mi piace molto su algoritmo di Ben è che egli continuò a camminare, o avermi camminare, avanti e indietro e avanti e indietro e avanti e indietro. E se invece dovessi fare qualcosa di simile a questi numeri qui ed io eravamo a che fare solo con ogni il numero, a sua volta, come sto dato che? 

In altre parole, ecco la mia lista di numeri. Quattro, uno, tre, due. E ho intenzione di fare quanto segue. Ho intenzione di inserire i numeri a cui appartengono piuttosto che selezionando uno alla volta. In altre parole, qui è il numero quattro. 

Ecco la mia lista originale. E ho intenzione di mantenere in sostanza un nuovo elenco qui. Quindi questa è la vecchia lista. Questa è la nuova lista. Vedo il numero quattro prima. La mia nuova lista è inizialmente vuota, quindi è banalmente caso che quattro è ora lista assortiti. Sto solo prendendo il numero che sto dato, e sto mettendo nella mia nuova lista. 

E 'questa nuova lista ordinata? Sì. È stupido, perché c'è solo una elemento, ma è assolutamente allineati. Non c'è nulla fuori posto. È più interessante, questo algoritmo, quando mi muovo alla fase successiva. 

Ora ne ho uno. Quindi, naturalmente, appartiene alla inizio o la fine di questa nuova lista? L'inizio. Quindi devo fare qualche lavoro ora. Ho preso un po ' libertà con il mio marcatore semplicemente disegnando cose dove li voglio, ma questo non è proprio accurata in un computer. Un computer, come sappiamo, ha RAM o Random Access Memory, e questo è un byte e un altro byte e un altro byte. E se si dispone di un gigabyte di RAM, si dispone di un miliardo di byte, ma sono fisicamente in un unico luogo. Non si può semplicemente spostare roba in giro disegnando sulla lavagna dove vuoi. Quindi, se la mia nuova lista ha quattro posizioni di memoria, purtroppo il quattro è già nel posto sbagliato. 

Quindi, per inserire il numero uno Non posso solo disegnare qui. Questa posizione di memoria non esiste. Sarebbe barare, e mi sono stati barare pittoricamente per pochi minuti Qui. Quindi, in realtà, se voglio mettere uno qui, Devo copiare temporaneamente il quattro e poi mettere quello lì. 

Va bene, questo è corretto, che è tecnicamente possibile, ma si rendono conto che è un lavoro extra. Non ho appena messo il numero di posto. Ho dovuto spostare un numero, quindi metterlo in atto, così ho tipo di raddoppiato il mio carico di lavoro. Modo da tenere a mente. 

Ma ora sto fatto con questo elemento. Ora voglio afferrare il numero tre. Dove, naturalmente, appartiene? Nel mezzo. Non posso imbrogliare più e appena messo lì, perché, di nuovo, questa memoria è in luoghi fisici. Quindi devo copiare i quattro e mettere i tre qui. Non un grande affare. E 'solo un passo in più again-- si sente molto poco costoso. 

Ma ora passo a due. I due, ovviamente, appartiene qui. Ora si inizia a vedere come il lavoro può accumularsi. Ora cosa devo fare? Sì, devo spostare il quattro, Poi ho dovuto copiare i tre, e ora posso inserire i due. E il fermo con questo algoritmo, abbastanza interessante, è che supponiamo di avere un più estremo caso in cui è diciamo otto, sette, sei, cinque, quattro, tre, due, uno. Questo è, in molti contesti, la peggiore delle ipotesi, perché l'aggeggio è letteralmente all'indietro. 

E 'davvero non influenzare l'algoritmo di Ben, perché nella scelta di Ben Ordina ha intenzione di mantenere andando avanti e indietro attraverso la lista. E perché era sempre alla ricerca tutta la lista restante, non importa dove gli elementi sono. Ma in questo caso con il mio inserimento approach-- proviamo questo. 

Quindi uno, due, tre, quattro, cinque, sei, sette, otto. Uno due tre quattro, cinque, sei, sette, otto. Vado a prendere otto, e dove lo metto? Beh, all'inizio della mia lista, perché questo nuovo elenco è ordinato. E varco fuori. 

Dove metto il sette? Accidenti. Si deve andare lì, così Devo fare un po 'la copia. E ora i sette va qui. Ora mi muovo al sei. Ora è ancora più lavoro. 

Otto deve andare qui. Sette deve andare qui. Ora i sei può andare qui. Ora prendo il cinque. Ora gli otto deve andare qui, sette deve andare qui, sei deve andare qui, e Ora i cinque e ripetere. E sono praticamente spostandola continuamente. 

Così, alla fine, questo algorithm-- faremo chiamare inserimento sort-- realtà ha un sacco di lavoro, anche. E 'solo diverso tipo di lavoro di Ben. Il lavoro di Ben mi ha fatto andare avanti e indietro tutto il tempo, la selezione del prossimo più piccolo elemento nuovo e di nuovo. Così è stato questo tipo molto visivo di lavoro. 

Questo altro algoritmo, che è ancora correct-- si otterrà il lavoro done-- cambia solo la quantità di lavoro. Sembra che inizialmente sei risparmio, perché sei solo trattare ogni elemento in attacco senza camminare tutto il percorso attraverso la lista come Ben era. Ma il problema è, soprattutto in questi casi folli in cui è tutto al contrario, sei solo tipo di rimandando il duro lavoro fino ad avere per correggere i tuoi errori. 

E quindi se si può immaginare questo otto e sette e sei e cinque e poi quattro e tre e due spostando la loro strada attraverso la lista, abbiamo appena cambiato il tipo di lavoro che stiamo facendo. Invece di farlo al All'inizio del mio iterazione, Sto solo facendo al fine di ogni iterazione. Così si scopre che questo algoritmo, Anche, generalmente chiamato insertion sort, è anche dell'ordine di n quadrato. In realtà non è migliore, migliore affatto. 

Tuttavia, c'è un terzo approccio Mi noi vorremmo suggerire considerare, che è questo. Quindi supponiamo che la mia lista, per semplicità ancora una volta, è di quattro, uno, tre, two-- soli quattro numeri. Ben aveva buona intuizione, buona intuizione umana prima, con la quale abbiamo fissato l'intera elencare eventually-- insertion sort. Contattaci persuasi lungo. Ma prendiamo in considerazione il modo più semplice per risolvere questa lista. 

Questo elenco non è ordinato. Perché? In inglese, spiegare perché In realtà non è ordinato. Che cosa significa non essere ordinati? 

STUDENTE: Non è sequenziale. 

DAVID MALAN: non sequenziale. Fammi un esempio. 

STUDENTE: Metterli in ordine. 

DAVID MALAN: OK. Dammi un esempio più specifico. 

STUDENTE: ordine crescente. DAVID MALAN: Non ordine crescente. Essere più precisi. Non so cosa si intende per ascendente. Cosa c'è di sbagliato? 

STUDENTE: Il più piccolo del numeri non è nel primo spazio. 

DAVID MALAN: minor numero di non nel primo spazio. Sii più preciso. Sto iniziando a prendere piede. Contiamo, ma ciò che è fuori ordine qui? 

STUDENTE: sequenza numerica. DAVID MALAN: sequenza numerica. tipo di ognuno di conservazione è qui-- altissimo livello. Basta letteralmente dimmi cosa c'è male come una forza di cinque anni. 

STUDENTE: più uno. 

DAVID MALAN: Che cos'è? 

STUDENTE: più uno. 

DAVID MALAN: Cosa vuoi dire più uno? Dammi un altro di cinque anni. Cosa c'è che non va, mamma? Cosa c'è che non va, papà? Cosa vuol dire questo non è ordinato? 

STUDENTE: Non è il posto giusto. 

DAVID MALAN: Cosa c'è Non nel posto giusto? 

STUDENTE: Quattro. DAVID MALAN: OK, bene. Quindi quattro non è dove dovrebbe essere. In particolare, è questo diritto? Quattro e uno, il primo due numeri che vedo. È giusto? No, sono in ordine, giusto? In effetti, pensare ora A proposito di un computer, anche. Si può solo guardare forse uno, forse due cose a once-- e in realtà solo una cosa alla volta, ma può almeno guardare una cosa poi la prossima cosa proprio accanto ad esso. 

Quindi, sono questi in ordine? Ovviamente no. Allora sai cosa? Perché non prendere il bambino passaggi risoluzione di questo problema invece di fare questi fantasia algoritmi come Ben, dove E 'una specie di risolverlo da scorrendo la lista invece di fare quello che ho fatto, dove Ho solo tipo di riparato come andiamo? Diciamo solo letteralmente abbattere il nozione di ordine numerico order--, chiamare quello che want-- in questi confronti a coppie. 

Quattro e uno. E 'questo l'ordine corretto? Quindi cerchiamo di sistemare le cose. Uno e quattro, e poi ci limiteremo a Ricevuto. Va bene, bene. Ho sistemato uno e quattro. Tre e due? No. Lasciate che le mie parole corrispondono le dita. Quattro e tre? 

Non è in ordine, così ho intenzione fare uno, tre, quattro, due. Ok bene. Ora quattro e due? Abbiamo bisogno di risolvere questo problema, anche. Quindi uno, tre, due, quattro. Quindi è risolto? No, ma è più vicino al filtrate? 

E ', perché abbiamo fissato questo errore, abbiamo fissato questo errore, e abbiamo fissato questo errore. Così abbiamo fissato tre errori senza dubbio. Ancora in realtà non guardare ordinato, ma è oggettivamente più vicino alla ordinato perché abbiamo fissato alcuni di questi errori. 

Ora cosa faccio adesso? I tipi di raggiunto la fine della lista. Mi sembrava di aver risolto tutti gli errori, ma no. Poiché in questo caso, alcuni numeri potrebbe aver bollito su più vicino ad altri numeri che sono ancora fuori uso. Quindi cerchiamo di farlo di nuovo, e io basta farlo al suo posto questa volta. Uno e tre? Va bene. Tre e due? Naturalmente no, quindi cerchiamo di cambiare la situazione. Così due, tre. Tre e quattro? Ed ora facciamo solo essere particolarmente pedante qui. E 'allineati? È l'uomo sai che è ordinato. 

Dovrei provare di nuovo. Così Olivia propone provo di nuovo. Perché? Poiché un computer non dispone il lusso dei nostri occhi umani di un semplice sguardo back-- OK, ho finito. Come fa il computer a determinare che l'elenco è ora ordinato? Meccanicamente. 

Dovrei passare attraverso ancora una volta, e solo se Non fare / trovare eventuali errori posso poi concludere come il computer, sì, siamo a posto. Così uno e due, due e tre, tre e quattro. Ora posso definitivamente dire che questo è ordinato, perché ho fatto alcuna modifica. Ora sarebbe un errore e basta sciocca se io, il computer, ha chiesto ancora una volta quelle stesse domande in attesa di risposte diverse. Non dovrebbe accadere. 

E così ora la lista è ordinata. Purtroppo, il tempo di esecuzione questo algoritmo è anche N al quadrato. Perché? Perché hai n numeri, e nel peggiore dei casi si deve spostare n numeri N volte perché si deve andare avanti indietro per controllare e potenzialmente risolvere questi numeri. E possiamo fare di più analisi formale, troppo. 

Quindi questo è tutto dire che abbiamo preso tre diversi approcci, uno di loro immediatamente intuitivo fuori del blocco di Ben al mio inserimento suggerito sorta a questo dove tipo di perdere di vista la foresta per gli alberi inizialmente. Ma poi se si prende un passo indietro, voilà, abbiamo fissato la nozione di ordinamento. Quindi questo è, oserei dire, un livello inferiore forse di alcune di quelle altre algoritmi, ma cerchiamo di vedere se non possiamo visualizzare questi attraverso questo. 

Quindi, questo è un bel un software che qualcuno ha scritto utilizzando barre colorate che di intenzione di fare quanto segue per noi. Ciascuna di queste barre rappresenta un numero. Taller il bar, il più grande il numero, più piccolo è il bar, minore è il numero. Quindi idealmente vogliamo un bel piramide dove inizia piccolo e diventa grande, e ciò significherebbe che queste barre vengono ordinati. Quindi ho intenzione di andare avanti e scegliere, per esempio, l'algoritmo di Ben first-- selection sort. 

E notare quello che sta facendo. Il modo in cui hanno scelto di visualizzare questo algoritmo è che, proprio come me passeggiando per la mia lista, questo programma è a piedi attraverso il suo elenco di numeri, evidenziando in rosa ogni numero che si sta guardando. E quello che sta per accadere in questo momento? 

Il più piccolo numero che I o Ben trovato improvvisamente viene spostato all'inizio della lista. E notare che hanno fatto sfrattare il numero che era lì, e che è perfettamente bene. Non ho fatto in quel livello di dettaglio. Ma abbiamo bisogno di mettere quel numero da qualche parte, così abbiamo appena spostato al luogo aperto che è stato creato. Quindi ho intenzione di accelerare questo up, perché altrimenti diventa molto noioso rapidamente. Animazione speed-- ci andiamo. Così ora lo stesso principio Io ero l'applicazione, ma si può iniziare a sentire l'algoritmo, se si volontà, o di vederlo un po 'più chiaramente. E questo algoritmo ha l'effetto di selezionando l'elemento più piccolo successivo, così si sta andando a cominciare a vederlo rampa sulla sinistra. E su ogni iterazione, come ho proposto, fa un po 'meno lavoro. Essa non deve andare fino in fondo indietro verso l'estremità sinistra della lista, perché già sa chi sono allineati. Quindi che tipo di sente come se fosse accelerando, anche se ogni passo è prendendo la stessa quantità di tempo. C'è solo un minor numero di passaggi rimanenti. E ora è possibile tipo di sentire il algoritmo di ripulire la fine di esso, e in effetti ora è risolto. 

Così insertion sort è tutto fatto. Ho bisogno di ri-casuale la matrice. E notare che posso solo mantenere randomizzazione esso, e otterremo un ravvicinamento delle lo stesso approccio, insertion sort. Mi permetta di rallentarlo a qui. Cominciamo che oltre. Stop. 

Saltiamo quattro. Ecco quà. Randomize essi array. E qui si go-- insertion sort. Giocare. Si noti che si tratta di trattare con ogni elemento che incontra subito, ma se appartiene il posto avviso sbagliato tutto il lavoro che deve accadere. Dobbiamo continuare a spostare più e più elementi per fare spazio per quello che vogliamo mettere in atto. 

Quindi ci stiamo concentrando sulla estremità sinistra solo l'elenco. Si noti che non abbiamo nemmeno guardato at-- noi non hanno evidenziato in rosa nulla a destra. Stiamo solo che fare con i problemi man mano che procediamo, ma stiamo creando un sacco di lavorare per noi stessi ancora. E così, se noi accelerare l'operazione ora di andare a compimento, ha una sensazione diversa ad esso davvero. E 'solo concentrandosi sulla estremità sinistra ma facendo un po 'di lavoro come needed-- tipo di cose smoothing sopra, aggiustare le cose, ma si tratta in ultima analisi, con ciascun elemento alla volta fino ad arrivare a il-- bene, abbiamo tutti sappiamo come andrà a finire, quindi è un po 'deludente, forse. 

Ma l'elenco nella end-- spoiler-- sta per essere ordinato. Quindi diamo un'occhiata a un ultimo uno. Non possiamo ignorare ora. Ci siamo quasi. Due per andare, uno per andare. E voilà. Eccellente. 

Così ora facciamo un ultimo uno, ri-randomizzazione con bubble sort. E notate qui, soprattutto se lento giù, questo non tenere in picchiata attraverso. Ma notate rende solo a coppie sorta comparisons-- di soluzioni locali. Ma non appena si arriva a la fine della lista in rosa, quello che sta andando ad avere per accadere di nuovo? Sì, sta andando ad avere per ricominciare, perché solo errori a coppie fisse. E che potrebbe aver rivelato altri ancora. E così se accelerare questo, ti vedere che, proprio come dice il nome, minore elements-- o meglio, i più grandi stanno cominciando elements-- a bollire fino alla cima, se si vuole. E gli elementi più piccoli sono iniziando a bolla verso sinistra. E in effetti, questo è il tipo di l'effetto visivo pure. E così questo finirà per finire in un modo molto simile, anche. 

Non abbiamo soffermarsi su questo particolare. Mi permetta di aprire questo ora, anche. Ci sono un paio di altri algoritmi di ordinamento nel mondo, alcuni dei quali vengono catturati qui. E soprattutto per gli studenti che non sono necessariamente visiva o matematica, come abbiamo fatto prima, possiamo anche fare questo audially se associamo un suono con questo. E solo per divertimento, ecco un pochi diversi algoritmi, e uno di loro, in particolare, si è andando a notare che viene chiamato "merge sort." 

In realtà è un fondamentalmente meglio algoritmo, in modo tale che merge sort, uno dei quelli che state per vedere, Non è dell'ordine di n al quadrato. E 'nell'ordine di n volte log di n, che è in realtà più piccole e quindi più velocemente di quelle altre tre. E ci sono un paio altro quelle stupide che vedremo. 

Quindi qui si va con qualche suono. Questo è insertion sort, in modo nuovo è solo trattare con gli elementi come vengono. Si tratta di bubble sort, quindi è considerandoli paia alla volta. E ancora, i più grandi elementi sono gorgogliare fino alla cima. 

Next up selection sort. Questo è l'algoritmo di Ben, dove ancora una volta sta selezionando in modo iterativo l'elemento immediatamente inferiore. E ancora, ora si può veramente sentire che sta accelerando, ma solo nella misura come si sta facendo sempre meno lavorare su ogni iterazione. Questo è il più veloce uno, merge sort, che è l'ordinamento grappoli di numeri insieme e poi li unisce. Così look-- sinistra la metà è già ordinato. 

Ora è l'ordinamento la metà destra, e ora sta andando a combinarle in una sola. Questo è qualcosa che si chiama "Gnome sorta." E si può vedere che tipo di sta andando avanti e indietro, fissare il lavoro un po 'qui e lì prima di procedere a un nuovo lavoro. E questo è tutto. C'è un altro tipo, che è in realtà solo per scopi accademici, chiamato "stupido tipo", che prende i dati, lo ordina in modo casuale, e quindi controlla se è ordinato. E se non lo è, si ri-ordina esso casualmente, controlla se è ordinato, e se non si ripete. E in teoria, probabilisticamente questo completerà, ma dopo un po 'di tempo. Non è il più efficiente di algoritmi. Quindi tutte le domande su quelli particolari algoritmi o niente ci correlate, troppo? 

Bene, ora prendere in giro a parte quello che tutti queste linee sono che ho disegnando e quello che sto assumendo il computer può fare sotto la cappa. Direi che tutti questi numeri Continuo drawing-- hanno bisogno di ottenere memorizzati da qualche parte nella memoria. Ci sbarazzarsi di questo ragazzo ora, anche. 

Così un pezzo di memoria in un computer-- così RAM DIMM è quello che abbiamo cercato di ieri, doppio di memoria in linea module-- assomiglia a questo. E ciascuno di questi piccoli chip neri è un numero di byte, tipicamente. E poi le spille d'oro sono come il fili che collegano al computer, e la scheda di silicio verde è solo ciò che tiene tutto insieme. Così che cosa questo significa veramente? Se I tipi di disegnare questo stessa immagine, supponiamo per semplicità che questo DIMM, doppio Inline Memory Module, è un gigabyte di RAM, un gigabyte di la memoria, che è il numero di byte totale? Un gigabyte è quanti byte? Più di quello. 1.124 è chilo, 1.000. Mega è milioni. Giga è un miliardo. 

Sto mentendo? Possiamo anche leggere l'etichetta? Questo è in realtà 128 gigabyte, quindi è più. Ma fingiamo che è solo un gigabyte. In modo che significa che c'è un miliardo byte di memoria disponibile per me o 8 miliardi di bit, ma stiamo andando a parlare in termini di byte ora, andando avanti. 

Quindi, che cosa significa questo è un byte, questo è un altro byte, questo è un altro byte, e se volevamo per essere precisi dovremmo disegnare un miliardo di piccoli quadrati. Ma che cosa significa? Beh, vorrei solo lo zoom in su questa immagine. Se ho qualcosa che sembra come adesso, che è quattro byte. 

E così ho potuto mettere quattro numeri qui. Uno due tre quattro. Oppure potrei mettere quattro lettere o simboli. "Hey!" potrebbe andare proprio lì, perché ciascuna delle lettere, abbiamo discusso in precedenza, potrebbe essere rappresentata con otto bit o ASCII o un byte. Quindi, in altre parole, è possibile mettere 8 miliardi di cose dentro di questo uno stick di memoria. Ora che cosa significa per rimettere le cose di back to back in memoria come questo? Questo è ciò che un programmatore chiamerebbe un "allineamento". In un programma per computer, non pensi circa l'hardware sottostante, di per sé. Basta pensare a te stesso come avere accesso a un totale miliardo di byte, e si può tutto quello che vuoi con esso. Ma per convenienza è generalmente utile per mantenere la giusta memoria accanto all'altra come questo. Quindi, se ingrandire una questo-- perché non stiamo certamente andando disegnare un miliardo di piccoli squares-- supponiamo che questa scheda rappresenta quel bastone della memoria ora. E io solo disegnare come molti come il mio marcatore finisce per dare me qui. Così ora abbiamo un bastone di memoria sulla scheda che ha ottenuto uno, due, tre, quattro, cinque, sei, uno, due, tre, quattro, cinque, sei, seven-- così 42 byte di Memoria sullo schermo totale. Grazie. Sì, ha fatto la mia aritmetica destra. Così 42 byte di memoria qui. Che cosa significa questo in realtà significa? Ebbene, un programmatore di computer sarebbe in realtà in genere pensare a questa memoria come indirizzabile. In altre parole, ognuno di questi posizioni in memoria, in hardware, ha un indirizzo univoco. 

Non è così complesso come un Brattle Square, Cambridge, Mass., 02138. Invece, è solo un numero. Questo è il numero di byte pari a zero, questo è uno, questo è due, questo è tre, e questo è 41. Apetta un minuto. Pensavo di aver detto 42 un momento fa. Ho iniziato a contare da zero, in modo che in realtà è corretta. Ora non dobbiamo disegnare realtà come una griglia, e se si disegna come una griglia Penso che le cose in realtà ottenere un po 'fuorviante. Quello che un programmatore sarebbe, nella sua mente, generalmente pensare a questo la memoria, come è proprio come un nastro, come un pezzo di nastro adesivo che va solo avanti e avanti per sempre o fino a quando si esaurisce la memoria. Quindi un modo più comune per disegnare e basta pensare a memoria sarebbe che questo byte zero, uno, due, tre, e poi dot, puntini, puntini. E hai 42 tali byte totale, anche se fisicamente si potrebbe effettivamente essere qualcosa di più simile a questo. 

Quindi, se ora pensate al vostro memoria, come tale, come un nastro, questo è ciò che un programmatore nuovo chiamerebbe un array di memoria. E quando si desidera memorizzare in realtà qualcosa nella memoria di un computer, generalmente conservare le cose back-to-back to back-to-back. Così abbiamo parlato di numeri. E quando ho voluto risolvere i problemi come quattro, uno, tre, due, anche se ero appena disegnavo solo i numeri quattro, uno, tre, due sulla scheda, il computer sarebbe davvero questa configurazione nella memoria. 

E quale sarebbe vicino alla due nella memoria del computer? Beh, non c'è risposta. Noi non lo sappiamo. E finché la di computer non ne ha bisogno, non deve prendersi cura ciò che è prossimo ai numeri lo fa a cuore. E quando ho detto prima che un computer può solo guardare un indirizzo alla volta, questo è una specie di perché. 

Non diversamente da un record giocatore e una testa di lettura solo essere in grado di guardare un certo scanalatura in un record vecchia scuola fisico alla volta, analogamente può un computer grazie alla sua CPU e la sua set di istruzioni Intel, tra cui l'istruzione viene letto dalla memoria o salvare un memory-- computer può solo guardare in un unico posto per tempo-- talvolta una loro combinazione, ma in realtà solo una posizione alla volta. Così, quando stavamo facendo questi vari algoritmi, Non sto scrivendo in un vacuum-- quattro, uno, tre, due. Quei numeri in realtà appartengono qualche parte fisica nella memoria. Quindi ci sono piccolo piccolo transistor o qualche tipo dell'elettronica sotto la Cappuccio memorizzazione di questi valori. 

E in totale, la quantità di bit coinvolto in questo momento, tanto per essere chiari? Quindi questo è di quattro byte, o ora è 32 bit totale. Quindi, ci sono in realtà 32 zeri e quelli che compongono queste quattro cose. C'è ancora di più qui, ma ancora una volta non ci interessa di questo. 

Così ora cerchiamo di chiedere a un altro domanda utilizzando la memoria, perché alla fine della giornata è in varianza. Non importa ciò che potremmo fare con il computer, alla fine della giornata l'hardware è ancora la stesso sotto la cappa. Come faccio a conservare una parola qui? Ebbene, una parola in un computer come "Hey!" sarebbe stato conservato proprio come questo. E se si voleva una più lunga parola, si può semplicemente sovrascrivere questo e dire qualcosa come "ciao" e negozio che qui. 

Ed ecco, anche, questa contiguità in realtà è un vantaggio, perché un computer può solo leggere da destra a sinistra. Ma ecco una domanda. Nel contesto di questa parola, h-e-l-l-o, punto esclamativo, come potrebbe il computer sa dove il parola comincia e dove finisce la parola? Nel contesto dei numeri, come fa il computer sapere per quanto tempo la sequenza di numeri è o dove si inizia? Bene, si scopre fuori-- e non andremo troppo in questo livello di detail-- computer si muovono roba in giro in memoria letteralmente per mezzo di questi indirizzi. Quindi, in un computer, se siete la scrittura di codice per memorizzare le cose come le parole, quello che stai realmente facendo sta scrivendo espressioni che ricordano dove nel memoria del computer queste parole sono. Quindi, mi permetta di fare molto, esempio molto semplice. 

Ho intenzione di andare avanti e aprire un semplice programma di testo, e ho intenzione di creare un file chiamato hello.c. La maggior parte di queste informazioni che Non andrà in in grande dettaglio, ma ho intenzione di scrivere un programma nella stessa lingua, C. Questo è molto più intimidatorio, Direi, di Scratch, ma è molto simile nello spirito. In realtà, questi ricci braces-- è possibile tipo di pensare a quello che ho appena fatto come questo. 

Facciamo così, in realtà. Quando bandiera verde cliccato, Fare quanto segue. Voglio stampare "ciao". Quindi questo è ora pseudocodice. Sono un po 'confondendo i confini. In C, questa lingua sto parlando A proposito, questa linea di stampa ciao in realtà diventa "printf" con alcune parentesi e un punto e virgola. 

Ma è esattamente la stessa idea. E questo molto user-friendly "Quando bandiera verde cliccato" diventa il più arcano "void main int." E questo non ha davvero alcuna mappatura, quindi sto solo andando a ignorare. Ma le parentesi graffe sono come il pezzi del puzzle curvi come questo. 

Così si può tipo di indovinare. Anche se non hai mai programmato prima, che cosa fa questo programma probabilmente fare? Probabilmente stampa ciao con un punto esclamativo. 

Quindi proviamo questo. Io vado a salvarlo. E questo è, ancora, un ambiente vecchia scuola. Non posso fare clic, non riesco a trascinare. Devo digitare i comandi. Quindi voglio correre il mio programma, in modo da Potrei fare questo, come hello.c. Questo è il file mi sono imbattuto. Ma aspetta, mi manca un passo. Cosa abbiamo detto è una condizione necessaria passo per un linguaggio come il C? Ho appena scritto fonte codice, ma che cosa ho bisogno? Sì, ho bisogno di un compilatore. Quindi sul mio Mac qui, ho un programma chiamato GCC, GNU C compiler, che mi permette di fare questo-- turno il mio codice sorgente in, che chiameremo, codice macchina. 

E posso vedere che, di nuovo, come segue, questi sono gli zeri e quelli che ho appena creato dal mio codice sorgente, tutti gli zeri e uno. E se voglio correre il mio program-- succede di essere chiamato a.out per reasons-- storica "ciao". Posso correre di nuovo. Ciao ciao ciao. E sembra funzionare. 

Ma questo significa che da qualche parte nel mio la memoria del computer sono le parole h-e-l-l-o, punto esclamativo. E si scopre, tanto per fare un a parte, ciò che un computer normale procedura farlo in modo che sappia dove le cose iniziano e end-- è andando a mettere un simbolo speciale qui. E la convenzione è quello di mettere il numero zero alla fine di una parola in modo da sapere dove si in realtà finisce, in modo da non tenere la stampa fuori sempre di più caratteri di quello che effettivamente intenzione. 

Ma l'asporto qui, anche anche se questo è abbastanza arcano, è che è in ultima analisi, relativamente semplice. È stata data una sorta di un nastro, un vuoto spazio su cui è possibile scrivere lettere. È sufficiente avere un simbolo speciale, come arbitrariamente il numero zero, per mettere a fine le tue parole in modo che il computer sa, Oh, avrei dovuto interrompere la stampa dopo Vedo il punto esclamativo. Dato che la prossima cosa c'è è un valore ASCII pari a zero, o il carattere null come qualcuno lo chiamerebbe. Ma c'è una specie di problema qui, e cerchiamo di revert indietro di numeri per un attimo. Supponiamo che io faccio, infatti, hanno una serie di numeri, e supponiamo che il programma che sto scrivendo è come un libro di grado per un insegnante e un'aula insegnanti. E questo programma permette di lui o lei digitare i punteggi dei loro studenti il quiz. E supponiamo che lo studente ottiene 100 sul loro primo quiz, forse come un 80 sul successivo, poi un 75, poi a 90 sul quarto quiz. 

Quindi, a questo punto della storia, la matrice è di dimensioni quattro. Non c'è assolutamente più memoria nel computer, ma la matrice, per così dire, è di dimensioni quattro. Supponiamo ora che l'insegnante vuole assegnare un quinto quiz alla classe. Ebbene, una delle cose che ha o lei sta per avere a che fare è ora memorizzare un valore aggiunto qui. Ma se l'array l'insegnante ha creata in questo programma è di dimensioni per, Uno dei problemi con una serie è che non si può solo continuare ad aggiungere alla memoria. Perché quello che se un'altra parte del il programma ha la parola "hey" proprio lì? 

In altre parole, la memoria può essere utilizzato per nulla in un programma. E se in anticipo ho digitato in, hey, Voglio ingresso quattro punteggi quiz, si potrebbe andare qui e qui. E se si cambia improvvisamente idea più tardi e dire che voglio un quinto quiz punteggio, non si può solo metterlo dove vuoi, perché ciò che se questo memoria utilizzata per qualcosa else-- qualche altro programma o qualche altra caratteristica del programma che si sta eseguendo? Quindi devi pensare in anticipo come si desidera memorizzare i dati, perché ora hai dipinto se stessi in un angolo digitale. 

Così un insegnante potrebbe invece dire quando si scrive un programma memorizzare sua gradi, sai cosa? Ho intenzione di chiedere, quando si scrive il mio programma, che voglio zero, uno, due, tre, quattro, cinque, sei, otto gradi totali. Quindi uno, due, tre, quattro, cinque, sei, sette, otto. L'insegnante può semplicemente over-allocare la memoria quando si scrive il suo programma e dire, sai una cosa? Non sono mai intenzione di assegnare più di otto quiz in un semestre. Questo è solo pazzo. Non potrò mai destinare tale. In modo che in questo modo lui o lei ha la flessibilità per i punteggi degli studenti negozio, come 75, 90, e forse uno in più in cui lo studente ha ottenuto il credito extra, 105. 

Ma se l'insegnante non utilizza questi tre spazi, c'è un takeaway intuitivo qui. Lui o lei è solo spreco di spazio. In altre parole, c'è questa compromesso comune in programmazione dove è possibile allocare esattamente la quantità di memoria che si desidera, il rialzo dei quali è che sei Super efficient-- tu non sia uno spreco a tutto-- ma il lato negativo di cui è cosa succede se si cambia idea quando utilizzando il programma che si desidera memorizzare più dati di quanto originariamente destinati. 

Così forse la soluzione è, quindi, scrivere i programmi in modo tale che usano più memoria quanto ne abbiano bisogno. In questo modo non si sta andando di incorrere in questo problema, ma sei stato uno spreco. E la più memoria il programma utilizza, come abbiamo discusso ieri, meno la memoria che è disponibile per altri programmi, Quanto prima il computer potrebbe rallentare a causa di memoria virtuale. E così la soluzione ideale potrebbe essere quello che? 

Under, che ripartisce sembra male. Over-ripartisce sembra male. Quindi, quale potrebbe essere una soluzione migliore? Riallocazione. Essere più dinamica. Non sforzatevi di scegliere un priori, all'inizio, ciò che si vuole. E certamente non più di-allocare, per non essere uno spreco. 

E così, per raggiungere questo obiettivo, abbiamo bisogno di gettare questa struttura dati, per così dire, di distanza. E così quello che un programmatore si utilizzano in genere è qualcosa che non una chiamata serie, ma una lista collegata. In altre parole, lui o lei iniziare a pensare a loro memoria come tipo di una forma che può disegnare nel modo seguente. Se voglio memorizzare un numero in un program-- quindi è settembre Ho dato ai miei studenti un quiz; voglio per memorizzare primo quiz degli studenti, e hanno ottenuto un 100 sul it-- I Sto andando a chiedere il mio computer, a titolo del programma ho scritta, per un pezzo di memoria. E ho intenzione di archiviare il numero 100 in essa, e il gioco è fatto. 

Poi un paio di settimane più tardi quando ottengo il mio secondo quiz, ed è il momento di digitare in quel 90%, sto andando per chiedere al computer, hey, computer, posso avere un altro pezzo di memoria? Sta andando a darmi questo vuoto pezzo di memoria. Ho intenzione di mettere il numero 90, ma nel mio programma in qualche modo o other-- e non ci preoccupare La sintassi per questo-- ho bisogno in qualche modo concatenare queste cose insieme. E io li farò concatenare con quella che appare come una freccia qui. 

Il terzo quiz che viene in su, Sto per dire, hey, computer, dammi un altro pezzo di memoria. E ho intenzione di mettere giù qualunque cosa fosse, come 75, e devo catena di questo insieme ora in qualche modo. Quarto quiz arriva, e forse che è verso la fine del semestre. E a quel punto il mio programma potrebbe essere utilizzando la memoria dappertutto, tutto fisicamente. E così solo per calci, io sono andando a disegnare questa via quiz-- ho dimenticato quello che era; io che forse un 80 o something-- fin qui. 

Ma va bene, perché pittoricamente Sto andando a disegnare questa linea. In altre parole, in realtà, in hardware del computer, il primo punteggio potrebbe finiscono qui perché è proprio all'inizio del semestre. Il prossimo potrebbe finire qui perché un po 'di tempo è passato e il programma continua a funzionare. Il punteggio successivo, che era un 75, potrebbe essere qui. E l'ultimo punteggio potrebbe essere un 80, che è qui. 

Quindi, in realtà, fisicamente, questo potrebbe essere ciò che la memoria del computer assomiglia. Ma questo non è un utile mentale paradigma per un programmatore di computer. Perché si deve preoccuparsi in cui il diamine i dati è di finire? Volete solo per memorizzare i dati. 

Questo è un po 'come la nostra discussione precedente del disegno del cubo. Perché ti interessa cosa l'angolo è del cubo e come si deve girare a disegnarlo? Volete solo un cubo. Allo stesso modo qui, solo voglia di libro di grado. Hai voglia di pensare questo come un elenco di numeri. Chi se ne frega come è implementato in hardware? 

Così l'astrazione ora è questa immagine qui. Questa è una lista collegata, come un programmatore potrebbe chiamare, nella misura in cui si dispone di un lista, ovviamente, di numeri. Ma è collegata pittoricamente per mezzo di queste frecce, e tutte queste frecce are-- sotto il cofano, se siete curiosi, ricordare che il nostro hardware fisico ha indirizzi zero, uno, due, tre, quattro. Tutte queste frecce sono è come una mappa o direzioni, dove se 90 è-- ora Ho avuto modo di contare. 

Zero, uno, due, tre, quattro, cinque, sei, sette. Sembra che il 90 è a memoria del numero di indirizzo sette. Tutte queste frecce sono è come un piccolo pezzo di carta che sta dando indicazioni per il programma che dice che seguono questa mappa per arrivare alla posizione di sette. E ci si trova il secondo punteggio quiz dello studente. Nel frattempo, il 75-- se continuo questo, questo è sette, otto, nove, 10, 11, 12, 13, 14, 15. 

Quest'altra freccia rappresenta solo una mappa di locazione di memoria 15. Ma ancora una volta, il programmatore fa generalmente non si preoccupano di questo livello di dettaglio. E in più ogni programmazione il linguaggio di oggi, il programmatore Non si sa nemmeno dove in memoria questi numeri sono in realtà. Tutto lui o lei deve preoccuparsi è che sono in qualche modo collegati insieme in una struttura di dati come questo. 

Ma si scopre non per ottenere troppo tecnico. Ma proprio perché possiamo forse permettersi di avere questa discussione qui, supponiamo di rivisitare questo problema qui di un array. Vediamo se ci dispiace andare qui. Questo è 100, 90, 75, e 80. 

Permettetemi brevemente fare questa affermazione. Questo è un array, e di nuovo, la Caratteristica saliente di un array è che tutti i dati è tornato a back to back in memory-- letteralmente Un byte o forse quattro byte, un numero fisso di byte di distanza. In una lista collegata, che potremmo disegnare in questo modo, sotto il cofano che sa dove che roba è? Non ha nemmeno bisogno di scorrere come questo. Alcuni dei dati potrebbe essere verso sinistra lassù. Non si sa nemmeno. 

E così con una matrice, si dispone di un funzionalità nota come accesso casuale. E quali mezzi ad accesso casuale è che il computer può saltare immediatamente in qualsiasi posizione in un array. Perché? Poiché il computer sa che la prima posizione è zero, uno, due e tre. 

E così, se si vuole andare da questo elemento per l'elemento successivo, letteralmente, in la mente del computer, è sufficiente aggiungere uno. Se si vuole andare al terzo elemento, basta aggiungere tra-- elemento successivo, basta Aggiungi uno. Tuttavia, in questa versione della storia, supponiamo il computer è attualmente alla ricerca in o trattare con il numero 100. Come si arriva a quello successivo grade nel libro di grado? 

Bisogna prendere sette passi, che è arbitraria. Per arrivare a quello successivo, è necessario prendere un altro otto passi per arrivare a 15. In altre parole, non è un costante divario tra i numeri, e così ci vuole solo la computer più tempo è il punto. Il computer deve cercare attraverso la memoria al fine per trovare quello che stai cercando. 

Quindi considerando un array tende ad essere un dati veloce structure-- perché può letteralmente fare semplice aritmetica e arrivare dove si vuole con l'aggiunta di uno, per instance-- una lista collegata, sacrificate quella caratteristica. Non si può solo andare dalla prima al secondo al terzo al quarto posto. Bisogna seguire la mappa. Devi prendere più passi per arrivare a quei valori, che sembrerebbe essere aggiunta un costo. Quindi stiamo pagando un prezzo, ma quello che era la caratteristica che Dan stava cercando qui? Che cosa fa un elenco collegato a quanto pare ci permettono di fare, che era l'origine questa particolare storia? 

Di preciso. Una dimensione dinamica ad esso. Possiamo aggiungere a questa lista. Possiamo anche ridurre la lista, in modo che stiamo utilizzando solo la quantità di memoria come vogliamo davvero e così siamo mai troppo, che ripartisce. 

Ora basta per essere veramente pignoli esigente, c'è un costo nascosto. Quindi non si dovrebbe lasciarmi convincere che questo è un compromesso convincente. C'è un altro costo nascosto qui. Il vantaggio, per essere chiari, è che otteniamo dinamismo. Se voglio un altro elemento, posso solo disegnare e mettere un numero in là. E allora posso collegarlo con una foto qui, che è qui, ancora una volta, se ho Mi dipinto in un angolo, se qualcosa sta già usando la memoria qui, io sono fuori di fortuna. Io stesso ho dipinto in un angolo. 

Ma qual è il nascosto costare in questa foto? Non è solo la quantità di tempo che ci vuole andare da qui a qui, che è sette passi, poi otto fasi, che è più di uno. Che cosa è un altro costo nascosto? Non appena il tempo. Ulteriori informazioni sono necessario per raggiungere questa immagine. 

Sì, quella mappa, quei piccoli frammenti di carta, come continuo a descriverli come. Questi arrows-- coloro che non sono liberi. Un computer-- sai ciò che un computer ha. Ha zero e uno. Se si vuole rappresentare una freccia o un mappa o un numero, è necessario qualche ricordo. Così l'altro prezzo che pagare per una lista collegata, una scienza informatico comune risorsa, è anche spazio. 

E infatti così, così comunemente, Tra i compromessi nella progettazione di ingegneria del software sistemi è il tempo e space-- sono due dei vostri ingredienti, due dei tuoi ingredienti più costosi. Questo mi sta costando più tempo perché devo seguire questa mappa, ma è anche mi è costato più spazio perché devo mantenere questa mappa intorno. Così la speranza, come abbiamo tipo di discusso nel corso ieri e oggi, è che i benefici saranno superiori ai costi. 

Ma non c'è soluzione ovvia qui. Forse è better-- a la rapido e sporco, come Kareem proposto earlier-- gettare memoria al problema. Basta acquistare più memoria, pensare di meno difficile di risolvere il problema, e risolvere in un modo più semplice. E infatti in precedenza, quando abbiamo parlato di compromessi, non was spazio in il computer e il tempo. Era giunto il momento di sviluppo, che è ancora un'altra risorsa. 

Quindi, di nuovo, è questo equilibrio cercando di decidere quale di queste cose siete disposti a spendere? Quale è il meno costoso? Che produce i risultati migliori? Sì? 

Infatti. In questo caso, se siete che rappresenta numeri nella maps-- questi sono chiamati in molte lingue "puntatori" o "indirizzi" - è il doppio dello spazio. Che non devono essere così male come doppio se in questo momento stiamo solo la memorizzazione dei numeri. Supponiamo che siamo stati memorizzati presso i dati dei pazienti in un hospital-- così i nomi di Pierson, numeri di telefono, numeri di previdenza sociale, medico storia. Questa casella potrebbe essere molto, molto più grande, nel qual caso un minuscolo puntatore, l'indirizzo la prossima element-- non è un grosso problema. E 'un tale frangia costo non importa. Ma in questo caso, sì, è un raddoppio. Buona domanda. 

Parliamo di un tempo poco più concretamente. Qual è il tempo di esecuzione di cercare questa lista? Supponiamo che io volevo cercare attraverso tutti i gradi degli studenti, e c'è n gradi in questa struttura dati. Anche qui, si può prendere in prestito il vocabolario della precedente. Questa è una struttura dati lineare. 

Big O di n è ciò che è necessario per ottenere alla fine di questa struttura di dati, whereas-- e non abbiamo visto questo before-- una matrice ti dà ciò che si chiama costante di tempo, il che significa un passo o due gradini o 10 steps-- non importa. Si tratta di un numero fisso. Non ha nulla a che fare con la dimensione della matrice. E la ragione di ciò, di nuovo, è ad accesso casuale. Il computer può solo immediatamente passare a un'altra posizione, perché sono tutti uguali distanza da tutto il resto. Non c'è pensiero coinvolti. Tutto ok. Quindi, se posso, vorrei provare a dipingere due immagini finali. Un uno molto comune noto come una tabella hash. Quindi, per motivare questa discussione, fammi pensare su come fare questo. 

Così come su questo? Supponiamo che il problema noi vogliamo risolvere ora sta attuando in un dictionary-- così un sacco di parole inglesi o qualsiasi altra cosa. E l'obiettivo è quello di essere in grado di rispondere domande del modulo è presente una parola? Così si desidera implementare un correttore ortografico, basta come un dizionario fisico che si può guardare le cose in. Supponiamo che io dovessi fare questo con un array. Ho potuto fare questo. 

E supponiamo che le parole sono mela e banana e melone. E non riesco a pensare di frutta che iniziano con d, quindi siamo solo andando ad avere tre frutti. Quindi questo è un array, e siamo memorizzare tutte queste parole in questo dizionario come un array. La domanda, allora, è come gli altri potrebbe memorizzare queste informazioni? 

Beh, sto tipo di barare qui, perché ciascuna di queste lettere nella parola è davvero un byte individuale. Quindi, se ho davvero voluto essere nit-schizzinosi, dovrei davvero essere dividere questo in su in tanto piccoli blocchi di memoria, e abbiamo potuto fare esattamente questo. Ma stiamo andando a correre in lo stesso problema di prima. E se, come Merriam Webster o Oxford fa ogni anno di successo aggiungono parole al dictionary-- non lo facciamo necessariamente voler dipingere noi stessi in un angolo con una serie? 

Così, invece, forse un approccio più intelligente è quello di mettere Apple nel proprio nodo o scatola, come diremmo, banana, e allora qui abbiamo melone. E noi stringa di queste cose insieme. Quindi questa è la matrice, e questa è la lista collegata. Se non riesco a vedere, è solo dice "matrice", e questo dice "lista". 

Così abbiamo la stessa questioni precise come prima, per cui ora abbiamo dinamismo nella nostra lista collegata. Ma abbiamo un dizionario piuttosto lento. Supponiamo che io voglio cercare una parola. Mi potrebbe prendere grande O di n passi, perché la parola potrebbe essere fino a fine la lista, come melone. E si scopre che in programmazione, una specie del Santo Graal dei dati strutture, è qualcosa che ti dà costante il tempo come un array ma che ti dà ancora dinamismo. 

Così possiamo avere il meglio dei due mondi? E in effetti, c'è qualcosa chiamato la tabella di hash che permette di fare esattamente che, seppur approssimativamente. Una tabella hash è un amatore struttura di dati che può pensare come il combinazione di un array-- e ho intenzione di disegnarlo come questo-- e liste collegate che io traggo come questo qui. 

E il modo in cui questa cosa opere è il seguente. Se questo now-- hash table-- è la mia struttura terzo dei dati, e voglio archiviare parole in questo, non lo faccio desidera memorizzare solo tutte le parole back to back to back to back. Voglio sfruttare qualche un'informazione circa le parole che vi permetterà Mi capito dove è più veloce. 

Quindi, dato il parole mela e banana e melone, Ho deliberatamente scelto quelle parole. Perché? Che sorta di fondamentalmente differente circa il tre? Qual è l'ovvio? Iniziano con lettere diverse. 

Allora sai cosa? Invece di mettere tutte le mie parole nella lo stesso bucket, per così dire, come in una lunga lista, perché non fare Io, almeno, provo una ottimizzazione e fare le mie liste 1/26 più a lungo. Una ottimizzazione convincente potrebbe essere perché non fare I-- quando si inserisce una parola in questa struttura dati, nella memoria del computer, perché Non ho messo tutti «A», le parole qui, tutto 'B' parole qui, e tutti i 'c' parole qui? Quindi questo finisce per mettere una mela qui, banana qui, melone qui, e così via. 

E se ho un ulteriore parola like-- cosa è un altro? Mela, banana, pera. Chiunque pensa di un frutto che inizia con a, b, o c? perfetto Blueberry--. Che sta per finire qui. E così ci sembra di avere un marginalmente migliore soluzione, perché ora se voglio per la ricerca di Apple, io first-- non lo faccio solo dive nella mia struttura dati. Non mi tuffo nella memoria del mio computer. Io prima guardo la prima lettera. 

E questo è ciò che un computer scienziato direbbe. È hash nella vostra struttura dati. Si prende l'input, che a sua questo caso è una parola come Apple. Si analizza, guardando la prima lettera in questo caso, hashing in tal modo. Hashing è un termine generale per cui si prende qualcosa come input e si produce un output. E l'uscita dal fatto che caso è la posizione si desidera cercare, la prima posizione, secondo posizione, terzo. Quindi l'ingresso è mela, l'uscita è prima. L'ingresso è di banana, il uscita dovrebbe essere secondo. L'ingresso è melone, l'uscita dovrebbe essere terzo. L'ingresso è di mirtillo, il uscita dovrebbe essere di nuovo secondo. Ed è quello che ti aiuta a prendere scorciatoie attraverso la memoria per arrivare a parole o dati in modo più efficace. 

Ora, questo riduce il nostro tempo potenzialmente da tanto quanto uno su 26, perché se si assume che si avere il maggior numero di "a" parole come "z" parole come parole "Q", che non è realmente realistic-- si sta andando ad avere skew tra alcune lettere del alphabet-- ma questo sarebbe un incrementale approccio che non consentono di arrivare a parole molto più rapidamente. E in realtà, un sofisticato programma, il Googles del mondo, la Facebooks del world-- avrebbero usato una tabella hash per molti scopi differenti. Ma non sarebbe così ingenuo da di guardare solo alla prima lettera in mela o banana o pera o melone, perché, come si può vedere questi liste potrebbero ancora arrivare a lungo. 

E così questo potrebbe ancora essere una sorta di linear-- così una sorta di lento, come con il grande O di n che abbiamo discusso in precedenza. Quindi, ciò che una vera e propria buona volontà tabella hash fare-- avrà una matrice molto più grande. E userà una molto più sofisticata funzione di hashing, in modo che non si limita a guardare la "a". Forse guarda "a-p-p-l-e" e converte in qualche modo quelle cinque lettere nella posizione in cui Apple dovrebbe essere conservato. Stiamo solo ingenuamente con la lettera 'a' da solo, perché è bello e semplice. 

Ma una tabella hash, in Alla fine, si può pensare come una combinazione di una matrice, ciascuna delle quali ha una lista collegata che idealmente deve essere il più breve possibile. E questa non è una soluzione ovvia. In realtà, gran parte della messa a punto che va avanti sotto il cofano quando l'attuazione di tali tipi di sofisticate strutture di dati è ciò che è il diritto lunghezza della matrice? Qual è la funzione hash giusto? Come si fa a memorizzare le cose in memoria? 

Ma rendersi conto di quanto rapidamente questo tipo di discussione escalation, sia così lontano che è una specie oltre la testa a questo punto, che è ok. Ma abbiamo iniziato, il richiamo, con veramente qualcosa di basso livello ed elettroniche. E così questo è ancora una volta questo tema di astrazione, dove una volta si inizia a prendere per concesso, OK, ho it-- c'è memoria fisica, OK, capito, ogni ubicazione fisica ha un indirizzo, OK, ho capito, posso rappresentare quegli indirizzi come arrows-- si può iniziare molto rapidamente ad avere conversazioni più sofisticati che alla fine sembrano essere permettendoci per risolvere i problemi come la ricerca e classificare in modo più efficace. E stare tranquilli, too-- perché credo che questo è il più profondo siamo andati in qualche di questi argomenti CS proper-- Abbiamo fatto in un giorno e mezzo in questo puntare quello che si potrebbe fare di solito sopra corso di otto settimane in un semestre. 

Tutte le domande su questi? No? Tutto ok. Beh, perché non ci fermiamo lì, iniziare a pranzo un paio di minuti di anticipo, riprendere in quasi un'ora? E io indugiare per un po 'di domande. Poi ho intenzione di andare prendere un paio di chiamate, se va bene. Io accendo po 'di musica, nel frattempo, ma il pranzo dovrebbe essere dietro l'angolo.