[Powered by Google Translate] [Settimana 7] [David J. Malan - Harvard University] [Questo è CS50. - CS50.TV] Bene. Bentornato. Questo è CS50, e questo è l'inizio della settimana 7. Un paio di piccoli annunci: Pset5 è ora in corso, o che presto sarà, e lasciatemi dire, in tutta onestà, questo tende ad essere tra i più impegnativo di insiemi di problemi del corso, per cui vorrei parlare adesso in modo che questa settimana più che mai, non aspettare fino a quando, diciamo, Mercoledì sera o Giovedi notte per tuffarcisi dentro Questo è sicuramente un pset interessante. Pensiamo che sia divertente. Se effettivamente ottenere pienamente corretta e può quindi contestare il cosiddetto Big Board, avrete la possibilità di abbinare ingegno con alcuni dello staff del corso e alcuni dei tuoi compagni di classe. What The Big Board è una volta che avete il vostro correttore ortografico di lavoro, sarete in grado di andare a cs50.net dopo l'esecuzione di un comando, puramente opt in, e quindi la quantità di tempo e la quantità di RAM e più che avete utilizzato nel vostro implementazione saranno esposti qui nella home page del corso. Si noterà che un intero gruppo di queste persone sono qui elencati come il personale poiché durante il fine settimana, il personale pensato che sarebbe stato divertente cercare di superarsi a vicenda. Così si rendono conto che l'obiettivo non è quello di superare il personale. Anche io sono qui solo al numero 13. Puramente opt-in, ma è l'occasione per vedere quanto poca RAM e quanto pochi secondi di CPU si può utilizzare nei confronti di alcuni dei tuoi compagni di classe.
E devo ammettere che Kevin Michael Schmid, attualmente in numero 1 posizione tra i TF, questa è una implementazione che non chiamiamo possibile dato che sta usando quasi 0 RAM e circa 0 secondi per il caricamento. Quindi, noi ci occuperemo di linea Kevin. [Risate] Ci sono alcune abilità che Kevin sta mettendo alla prova qui. Una delle cose che abbiamo pensato di fare è troppo CS50x ora è una settimana in corso, e voi ragazzi sono tanto una parte di questo esperimento come gli studenti sono. Abbiamo chiesto loro come parte della loro pset0, che era simile a presentare un progetto Scratch di loro interesse - un gioco, un pezzo d'arte interattiva, un'animazione, o simili - un 1 - video 2 minuti, se vogliono, dire ciao al mondo, e che sono in realtà. Ho pensato di condividere con voi un paio di video che sono state presentate finora perché per noi, il personale, almeno, in realtà è stato emozionante e stimolante per vedere queste persone provenienti da tutto il mondo - i paesi di tutto il mondo - sintonizzazione, di tutte le cose, ad un corso di informatica su Internet, se è perché vogliono continuare i propri studi, vogliono prendere la loro carriera in una nuova direzione, vogliono colmare le lacune nella loro conoscenza, quindi alcune delle stesse ragioni che voi ragazzi forse sono stati qui.
Quindi vi do uno studente come qui. Si può aumentare il volume solo un po '. Ecco uno dei nostri studenti di 1 minuto osservazioni. Ciao, mondo. Sono uno studente di ingegneria industriale qui a Malaga, in Spagna. Sono entusiasta di questo corso on-line perché amo l'informatica, davvero, e ho davvero conto che arrivare a esplorare. E il fatto che posso imparare la stessa cosa tutti voi ragazzi fare ma invece di essere in Harvard sono a Malaga, come impressionante è quello? Beh, io sono Fernando, e questo è CS50. Ci vediamo. [Risate] Un altro clip ci piace particolarmente, vi accorgerete che questo signore inglese non è così forte. Sembra che l'aveva tradotta macchina, in modo che le stesse traduzioni sono un po 'imperfetta, ma questo era uno dei nostri preferiti finora pure. [♪ ♪] Ciao, mondo. [Parlando in giapponese] [Devo saluto in giapponese perché il mio inglese è molto inaffidabile.] [Ho consegnato il messaggio a voi dalla città di Gifu, Giappone.] [Posso essere uno studente per la prima volta in 20 anni, come si può vedere.] [Sono molto grato alla Harvard University, che mi ha dato questa opportunità e edx.] [Il golf è una chitarra e la cosa che preferisco in esecuzione.] [Risate] [♪ ♪] [Perché pensi che stavo cercando di partecipare a una cs50x.] [Harvard University, è il mio desiderio.] [Soprattutto se sono lontana presenza vissuto in Giappone.] [Ho voluto provare immediatamente a conoscenza dell'esistenza di tale EDX quando.] [Non pensate in modo da non legata all'età di apprendimento I.] [CS50 è il mio desiderio. Il mio nome è Kazu, e questo è CS50.] [♪ ♪] [applausi e applausi] Un altro favorito della nostra era questa presentazione qui da qualcuno. [♪ ♪] [Malan] Google, se non si ha familiarità con questo meme.
E poi, infine, un paio di altri che ho postato che forse vincere il premio adorabile. [Gli studenti] Aww! >> [Malan] Dobbiamo ascoltare. Questo è breve, in modo da ascoltare attentamente. [Speaker femminile] Qual è il tuo nome? Louie >>. [Speaker femminile] Di cosa si tratta? >> [Ridacchia] CS50. [Risate] [Malan] Ha fatto due ciak, però. Ci siamo, l'ultimo. Il mio nome è Louie, e questo è CS50. [Risate] Questo è quindi CS50x. Grazie a tutti quelli di voi, mentre proseguendo lungo a casa che sono stati partecipi finora. Oggi, concludiamo la nostra discussione di strutture di dati, almeno alcuni dei più fondamentale, e poi continuare la nostra conversazione di HTML e programmazione web. In effetti, abbiamo speso passato alcune sette settimane analizzando i fondamenti della programmazione - algoritmi, strutture di dati, e simili - e C, come si può avere sperimentato finora, non è necessariamente la più accessibile delle lingue con cui attuare alcune di queste idee. E così a partire da questa settimana e la prossima settimana e poi il seguente, saremo finalmente in grado di transizione da C, che è generalmente noto come un linguaggio abbastanza basso livello, alle cose più alto livello, tra cui PHP, JavaScript, e simili, che vedremo di attingere alle stesse lezioni che abbiamo imparato nel corso delle ultime settimane, ma vi accorgerete che dichiara cose come gli array e le tabelle hash e la ricerca e l'ordinamento diventato molto più facile perché le lingue stesse inizieremo con diventerà più potente. Ma prima, un'applicazione di alberi. E 'molto comune in questi giorni per necessità di comprimere le informazioni. In quale contesto si vuole comprimere un certo tipo di informazione digitale?
Gia '. >> [Studente] Quando è necessario inviare via web. Si, quando si desidera inviare qualcosa sul web. Se volete scaricare un file di grandi dimensioni, è ideale se qualcuno all'altro capo del filo ha compresso il file utilizzando un formato zip o qualcosa del genere in modo che si sta inviando meno bit che altrimenti potrebbero essere trasmessi. Quindi, come si fa a comprimere le informazioni? Il tutto si riduce a utilizzare un numero inferiore di bit necessari per impostazione predefinita. Ma questo è una specie di una cosa curiosa, perché ripenso alle settimane 0 e 1 quando abbiamo parlato di ASCII e binario e abbiamo parlato di ASCII, in particolare, come con 8 bit per rappresentare lettere dell'alfabeto così che la lettera A è rappresentato da 65, a minuscola è il numero 97, e comunque si rappresentano il 65 o 97, si sta utilizzando 7 o 8 bit. Ma il problema è che ci sono alcune lettere dell'alfabeto inglese che non sono così popolari come gli altri. Z non è poi così popolare, Q non è poi così popolare, ma A ed E sono super popolari. Eppure per tutte queste lettere, per impostazione predefinita il mondo utilizza lo stesso numero di bit, a soli 8. Quindi non sarebbe stato più intelligente, se invece di usare 8 bit per ogni lettera, anche il più di rado utilizzato come Q e Z, cosa succede se abbiamo usato meno bit per la A ed E e S e le lettere più popolari e utilizzati più bit per le lettere meno popolari, l'idea è ottimizzare andiamo per il caso comune, che è un tema in informatica di cercare di ottimizzare quello che sta per accadere il più e trascorrere un po 'di tempo, un po' più spazio sulle cose che, sì, potrebbe accadere ma non necessariamente la stessa frequenza. Quindi cerchiamo di fare un esempio.
Supponiamo di voler codificare informazioni abbastanza efficiente. Si potrebbe avere cresciuto sapendo qualcosa su codice Morse, e le probabilità sono che non conosceva il codice vero e proprio, ma si potrebbe ricordare che è almeno questa serie di punti e linee. Si tratta di una codifica abbastanza efficienti, e notare che la lettera più importante - per esempio, E - utilizza il più breve di segnali acustici. Il codice Morse è tutto bip-bip-bip-bip-bip-bip e tenendo i toni sia per brevi periodi di tempo o lunghi periodi di tempo. E, come indicato con il punto, è un segnale acustico super breve, solo un segnale acustico, e che rappresenterebbe E. Al contrario, T sarebbe un suono più lungo, come il segnale acustico [prolunga audio], e che rappresenterebbe T. Ma questo è ancora piuttosto breve, perché, al contrario, se si guarda a Z, per esprimere Z si dovrebbe andare bip, bip [più sound], bip, bip [suono più breve]. Quindi è più perché è meno comune. Ma il Gotcha è che il codice Morse è un po 'difettoso in quanto non è immediatamente decodificabili. Per esempio, supponiamo che si sente su alcune estremità del cavo segnale acustico [corto], segnale acustico [lungo]. Quale messaggio ho appena ricevuto? Un punto e un trattino. Che cosa rappresenta? [Studente] A. >> [Malan] Forse. Potrebbe anche essere seguito da E T. In altre parole, il codice Morse, sebbene sfrutta questo principio di ottimizzare il caso d'angolo, essa non si presta a decodificabilità immediata. Cioè, l'uomo che sta ascoltando o la ricezione di questi punti e linee deve capire in qualche modo in cui le pause sono tra le lettere, perché se non si sa dove le pause sono, si potrebbe confondere A per ET o viceversa.
Allora, cosa potrebbe fare? Nel codice Morse si può solo mettere in pausa tra ciascuna delle lettere. Ma la pausa è una specie di contrasto con il punto di accelerare le cose. E se invece ci si avvicinò con un codice in cui non c'era questa brutta situazione dove E è un prefisso, per esempio, di A - in altre parole, se si potesse fare in modo che i modelli sono ancora brevi per le lettere popolari lungo per le lettere meno popolari, ma non c'è possibilità di confusione? Un uomo con il nome di Huffman anni fa ha inventato questo programma chiamato codifica di Huffman che sfrutta in realtà una delle strutture dati che abbiamo trascorso un po 'di tempo a parlare la scorsa settimana, quella degli alberi, alberi binari in particolare - un significato albero binario che non ha più di due figli. Ha forse un figlio sinistro, forse un figlio destro, e questo è tutto. Supponiamo solo per il gusto della discussione che qualcuno vuole inviare un messaggio che assomiglia a questo. E 'assolutamente privi di senso, ma è composto di As, Bs, Cs, Ds, e Es. E se effettivamente contare tutte le As, B, Cs, Ds, e Es e poi dividere per il numero totale di lettere, questo grafico poco qui dice che il 45% delle lettere sono Es, il 20% sono come, 10% B, e così via. In altre parole, assumiamo che la stringa ivi citate è solo un po 'di messaggio che si desidera inviare. Capita di essere una sciocchezza solo così possiamo usare come lettere minor numero possibile, ma è vero che E rimane il più popolare, e B e C sono le meno popolari, almeno su queste 5 lettere dell'alfabeto. Quindi, come possiamo fare per venire con una codifica, una codifica binaria, un modello di 0 e 1 per ciascuna di queste lettere in modo tale che E è un modello corto e forse B e C sono modelli leggermente più lungo, di nuovo, l'idea è che si desidera utilizzare meno bit più delle volte più bit e solo una volta ogni tanto. Secondo la codifica di Huffman, è possibile creare una foresta di alberi. C'è una sorta di linea di storia qui che coinvolge gli alberi e anche il processo di costruzione in su. Cominciamo.
Propongo di iniziare con questa foresta, per così dire, di 5 alberi, ciascuno dei quali è un albero abbastanza stupido. La struttura è composta da un singolo nodo, come qui rappresentata da un cerchio. Quindi ognuna di queste cose potrebbe essere una struct C e all'interno della struct C potrebbe essere un galleggiante che rappresenta il conteggio di frequenza e poi magari un carattere che rappresenta la lettera. Quindi, pensare di questi nodi, come un qualsiasi vecchio struct C, ma, per ora, di livello superiore. Si tratta di una foresta di 5 alberi, ognuno dei che hanno solo un singolo nodo. Che Huffman proposta è che si inizia a combinare questi alberi che hanno i conti in alberi più piccoli di frequenza leggermente più grandi collegandoli con un nodo radice nuova. Così tra le lettere qui, si noti che per comodità li ho ordinati da sinistra a destra, anche se questo non è strettamente necessario, e notare che i più piccoli nodi sono attualmente 10% e 10%. Così Huffman propone di unire questi 2 piccoli nodi in un nuovo albero con l'introduzione di un nuovo nodo padre e poi dare quel genitore di un figlio sinistro e figlio destro dove B è arbitrariamente sinistra e C è arbitrariamente destra. E poi Huffman propone inoltre che andiamo ora solo pensare al figlio sinistro in uno di questi alberi sempre ad essere rappresentato da 0 e il figlio destro sempre come rappresentato dal numero 1.
Non importa se si capovolgere fino a quando sei coerente. Così ora abbiamo quattro alberi in questa foresta. E dico quattro perché ormai l'albero a sinistra - e non è tanto un albero nel senso che cresce in questo modo, è più simile a un albero di famiglia dove ora la 0.2 è una sorta di madre di due bambini - notare che in quel genitore che abbiamo disegnato 0.2. Abbiamo aggiunto i conteggi di frequenza dei due bambini e dato il nuovo nodo la somma totale. Quindi ora dobbiamo solo ripetere questo processo. Trova i due nodi più piccoli e poi unirsi a loro in un nuovo albero e poi ripetere il processo ulteriormente. In questo momento ci sono alcuni candidati, il 20%, 15%, e un altro 20%. In questo caso, dobbiamo rompere il legame. Possiamo farlo arbitrariamente. Dovremmo farlo in modo coerente. In questo caso, verrà arbitrariamente andare con quello di sinistra, e ora unire il 20% e il 15% per darmi un nuovo genitore chiamato il 35%, il cui figlio sinistro è 0, il cui diritto è di 1 bambino, e ora abbiamo solo tre alberi nella foresta. Si può forse vedere dove questo sta andando. Se ripetiamo questo un paio di volte, stiamo andando ad avere un solo albero più grande, in cui tutti gli archi sono etichettati con 0 e 1. Facciamolo di nuovo. 35% è la radice dell'albero che. 20% e 45%, in modo che andremo a unire il 35% e il 20%. Ora abbiamo questo albero qui. Aggiungiamo allo stesso tempo, abbiamo il 55%. Ora ci sono solo due alberi nella foresta. Lo facciamo un'ultima volta, e, auspicabilmente, matematicamente tutte le frequenze si sommano perché dovrebbero dato che li abbiamo calcolato dal get-go per aggiungere fino a 100%. E ora abbiamo un albero. Quindi questo è un albero codifica Huffman. E 'sorta di voluto un po' per arrivarci verbalmente, ma la realtà è con un ciclo for o con una funzione ricorsiva, si potrebbe costruire questa cosa abbastanza veloce. Così ora abbiamo un nuovo nodo, e tutti questi nodi interni sono stati malloc'd, presumibilmente, lungo la strada. Così ora in cima di questo albero abbiamo 100%, ma ora notare abbiamo un percorso da questa nuova gran-gran-gran-nonno a tutti i pro-pro-pronipoti fino in fondo, a tutte le foglie.
Quello che andremo a fare ora è proporre che, al fine di rappresentare la lettera E, ci limiteremo a usare il numero 1. Perché? Perché se attraversiamo questo albero dalla radice finale verso il basso per la foglia denominato E, seguiamo un solo bordo, il bordo destro, e con l'indicazione del corso in alto a destra 1. Quindi l'implicazione qui per Huffman è che la codifica E in binario è solo essere 1. E questo è dannatamente efficace. Non può davvero ottenere qualsiasi più piccolo di quello. Al contrario, una sta per essere rappresentato, se si segue la logica, da ciò modello di bit invece? 01. Quindi, per arrivare a A, si parte dalla radice e si va a sinistra e poi a destra, il che significa che abbiamo seguito uno 0 e quindi a 1. Così abbiamo rappresenta la lettera A, con il modello 0 e 1. E ora si noti che ci hanno già una proprietà di decodificabilità immediata che non abbiamo avuto in codice Morse. Anche se entrambi questi modelli sono piuttosto breve - E è 1 bit, 2 bit A è - notare che non possono essere confusi uno o l'altro, perché se si vede un 1 è avuto modo di essere un E, se vedete uno 0 allora un 1 è ovviamente avuto modo di essere una A. Allo stesso modo, ciò che è D? 001. Che cosa è C? 0001. E che cosa è B? 0000. E ancora, perché tutte le lettere che ci interessano sono le foglie e nessuno di loro sono un po 'intermediari nel percorso dalla radice alla foglia, non c'è rischio di fondere differenti codifiche 2 lettere ' perché tutti questi modelli di bit sono deterministiche. 0000 sarà sempre B. Non c'è una via di mezzo nodo che si potrebbe confondere una lettera per l'altro. Allora, qual è l'implicazione qui?
La lettera più popolare - in questo caso E - ha ottenuto il più breve di codifica, A ha ottenuto la codifica più breve successiva, e B e C, che abbiamo già conosciuto dal get-go genere erano di meno popolare al 10% frequenza di ciascuno, che hanno ottenuto il più lungo di codifica. E così ciò che questo significa ora è che, se si desidera inviare un messaggio che è compresso su Internet o in una e-mail o simili, piuttosto che usare ASCII standard, è possibile inviare un messaggio in codice Huffman per cui se si desidera inviare la lettera E, si invia solo un singolo bit. Se si desidera inviare una A, si inviano 2 bit, 01, invece di inviare 8 bit seguita da altri 8 bit seguito da un altro 8 bit e così via. Ma c'è un dettaglio del tuo qui. Non è sufficiente costruire solo questo albero e poi iniziare a inviare da Alice a Bob la sequenza di bit più breve, una stringa da ASCII, perché Alice deve anche informare di ciò che Bob se Bob sta per essere in grado di leggere il suo messaggio compressa? [Risposta degli studenti incomprensibile] >> Che cos'è? [Risposta incomprensibile studente] >> Di che l'albero è. O, ancora più specificamente, quali siano tali codifiche sono, tanto più che in questa storia abbiamo fatto un giudizio ad un certo punto. Ricordate che abbiamo dovuto scegliere arbitrariamente tra i 2 nodi diversi 20%? Quindi non è il caso che Bob, il destinatario, può solo ricostruire l'albero da solo perché forse egli creerà l'albero sempre in modo leggermente diverso da Alice. Inoltre, Bob non sa nemmeno cosa sia il messaggio originale perché l'unica cosa Alice lo sta inviando, naturalmente, è il messaggio compresso.
Così il fermo con la compressione come questo è che, sì, Alice può risparmiare un bel po 'di bit inviando 1 per E e 01 per A e così via, ma deve anche informare Bob ciò che il mapping è tra lettere e bit perché non possono chiaramente affidamento solo su ASCII più se non stiamo utilizzando ASCII. Così si può mandargli l'albero in qualche modo - scrivere, memorizzare come dati binari o qualcosa di simile - o solo mandargli un piccolo foglio imbroglione, un file Excel, che mostra i mapping. Quindi, l'efficacia della compressione assume davvero che i messaggi che si sta inviando sono abbastanza grandi, almeno di medie dimensioni, perché se si sta inviando un messaggio super breve, se si desidera inviare il messaggio BAD, che risulta essere una parola che può significare qui, B-A-D, probabilmente stai andando ad utilizzare meno bit, ma il problema è che se si hanno anche per informare Bob ciò che l'albero è o quali siano tali codifiche sono, si sta andando a superare, probabilmente tutti i risparmi di dover cose compressi per cominciare. Quindi, si può effettivamente essere il caso che se si tenta di comprimere anche con qualcosa come i formati zip o file che si potrebbe avere familiarità con - file molto piccoli, file anche se vuoti - a volte questi file possono ottenere più grande e non più piccola. Ma realisticamente, che avviene solo per file di piccole dimensioni, quindi non è intenzione di fare un file di gigabyte è di 2 gigabyte; stiamo davvero parlando byte o solo un paio di kilobyte.
Alcuni programmi come zip sono abbastanza intelligenti per capire che, "Hai intenzione di spendere più bit compressione questo." "Che io non fastidio compressione per voi a tutti." Quindi questo è solo un modo di comprimere poi formato testo. Si potrebbe implementare qualcosa di simile in C. Per esempio, ecco come si potrebbe rappresentare un nodo in questo albero dove abbiamo un carattere per il simbolo, un valore variabile per la frequenza, e, come abbiamo visto con le nostre strutture di altri dati, 2 puntatori, 1 al bambino sinistra, 1 a destra, ciascuno dei quali può essere NULL, ma se non si riferisce ad un figlio sinistro e figlio destro. Quindi questo è quindi la codifica di Huffman, ed è un modo che si può fare per comprimere le informazioni, ed è certamente uno dei più facili da implementare nel contesto, per esempio, le strutture di dati della scorsa settimana, anche se esistono algoritmi più sofisticati che può fare mutazioni ancora più sofisticate dei dati. Tutte le domande poi sugli alberi, alberi binari, o di compressione del testo? [Studente] C'è qualche ambiguità, come se diviso [incomprensibile] in 01, 011 allora sarebbe ambigua, giusto? [Incomprensibile] >> Buona domanda. L'ambiguità. Permettetemi di riassumere facendo riferimento a questo quadro qui. Poiché i caratteri che si sta comprimendo, le rappresentazioni del, per definizione di questo algoritmo rimangono sempre le foglie, non sarai mai accidentalmente utilizzare lo stesso modello di bit per il prefisso di più lettere. Quindi, in altre parole, si è preoccupato, sembra, un'ambiguità derivante 001 in base al quale potrebbe essere l'inizio di B o l'inizio di C o qualcosa del genere. Ma questo non può essere il caso perché si noti che tutte le lettere dell'alfabeto che stiamo codificando sono le foglie.
L'ambiguità può sorgere, come nel caso di codice Morse, se, per esempio, C era lungo il percorso dalla radice a B. [Studente] destro. Quindi, in questo caso, diciamo A ha due foglie. >> Say A ha - Dillo di nuovo. [Studente] Say A ha 2 foglie, F e G, e quindi G - >> OK. Ma non può. La stessa non può avere le foglie F e G, perché quelle lettere F e G sarebbero loro lascia posto alla sinistra di B o il diritto di E. Quindi, per definizione, devono essere foglie. In caso contrario, hai perfettamente ragione, non abbiamo risolto il problema che si affaccia codice Morse. Bella domanda. Altre domande? Bene. Questa nozione di bit, si scopre che abbiamo avuto il potere per tutto il tempo che non abbiamo effettivamente utilizzato quando si trattava di manipolare questi 0 e 1. Abbiamo chiesto informazioni su questo su uno dei primi set di problema: vale a dire, come si fa a fare la conversione maiuscolo a minuscolo o viceversa? O, più concretamente, una di quelle prime chiese pset quanti bit si fa effettivamente deve lanciare per cambiare A lettere minuscole a o viceversa? Ecco un rapido promemoria di ciò che 65 e 97 aspetto in binario. E anche se tale questione è una sorta di sbiadito nella memoria, si può vedere di nuovo qui che quanti bit devono essere capovolte per cambiare maiuscola in minuscolo un? Solo uno.
Si distinguono solo per una posizione, il terzo bit da sinistra. Considerando che A ha un 010, un po 'ha un 011. Così in qualche modo, dobbiamo essere solo in grado di capovolgere quel po ', e possiamo quindi sfruttare o le lettere minuscole. Abbiamo fatto questo in passato tramite l'uso, se le condizioni e controllando se la lettera è tra il capitale e il capitale A Z, poi uscite come A - a + 26 o qualcosa del genere. Probabilmente ha fatto una modifica aritmetica delle lettere dell'alfabeto. Ma cosa succede se solo potessimo capovolgere che solo bit? Come si fa a prendere un byte valore di bit, così come 8 bit 01000001 e 01100001? Se tu avessi quei modelli di bit, come possiamo fare per cambiare solo uno di loro? Che cosa succede se introduciamo in giallo qui questo altro modello di bit? Se faccio le 0s intero stringa giallo ad eccezione del bit quello che voglio cambiare e poi introdurre un nuovo operatore conosciuto come un operatore bit per bit - bitwise nel senso che esso opera su singoli bit, non su un intero byte o quattro byte tutti in una volta. Questa barra verticale in giallo ci suggerisce che se prendiamo la rappresentazione del capitale di una e OR bit a bit con la sequenza di bit di colore giallo? In altre parole, ripensare alla nostra discussione di espressioni booleane in Scratch e poi in C.
Facendo un booleano o significa che per essere vero, sia la prima cosa che deve essere vero o la seconda cosa deve essere vero o entrambi devono essere vere, e quindi l'uscita risultante sé è vera. In questo caso qui, cosa otteniamo se prendiamo 0 "o" ed con 0? False o falso? E 'ancora falso, per cui la minuscola rimane come previsto. E se invece facciamo 1 o 0? Questo rimane ora 1, a meno di notare quello che sta per succedere qui. Se cominciamo con maiuscola e noi continuiamo a "o" i singoli bit, come stiamo facendo, 0 o quello giallo ci dà quello qui sotto? Questo ci dà 1. Infatti, supponiamo di non sapere che cosa la versione maiuscola di un po 'di realtà. Andiamo a fare questo. Vorrei spostare questo qui. Facciamolo di nuovo. 0 o 0 mi dà 0. 1 o 0 mi dà 1. 0 o 1 mi dà 1. 0 o 0 mi dà 0. Il prossimo è 0, il successivo è 0, il prossimo è 0. 1 o 0 mi dà 1. E quindi, anche se non sapevamo in anticipo che cosa era un minuscolo, semplicemente "o" ing A con questo modello di bit che abbiamo presentato qui in giallo, è possibile la lettera minuscola a maiuscola lanciando quel po '. Abbiamo usato questa espressione settimane fa: lanciando un po '. Come si fa a darsi da fare di programmazione? Si utilizza quello che generalmente chiamato una maschera, una sequenza di bit, che in questo caso così succede a guardare come questo numero qui, e poi si "o" insieme con questo nuovo operatore C, non | |, è possibile utilizzare un unico | e si dovrebbe realmente ottenere questa risposta qui perché perché? Questo è il luogo 1s, luogo 2s, 16s 4s, 8s,, 32s. Così si scopre che se si prende una lettera maiuscola A e OR bit a bit con il numero intero 32, perché il numero intero 32, quando la si guarda come bit, simile a questo, che significa che è possibile capovolgere la parte che si desidera veramente. E allo stesso modo - e vedremo il codice in un momento - supponiamo di voler andare nella direzione opposta.
Come si fa a passare da una minuscola a maiuscola? Quali bit ha bisogno di cambiare? E 'lo stesso. Vogliamo cambiare questo terzo bit da 1 a 0. E come potremmo fare per fare questo? Come si fa a spegnere un po '? Con quale modello di bit potremmo spegnere un po '? E se ordinare di invertire la maschera? Mentre prima, abbiamo fatto la 0s intero maschera gialla tranne per il bit uno volevamo accendere, E se questa volta, facciamo il tutto 1s maschera ad eccezione del bit che si desidera disattivare e quindi utilizzare quale operatore? E se noi "e" le cose? Diamo uno sguardo. Se ora capovolgere a questo, pensare che ancora una volta a creare una maschera che è tutto 1s tranne che per il bit di quello che voglio spegnere e allora piuttosto che "o" i numeri bianchi su cima con i numeri gialli quaggiù, se io invece "e" loro insieme? Si chiama bit per bit e. Logicamente, è la stessa cosa di un valore booleano e. Questo mi dà 0 e 1 è 0. Così falso e vero è falso. Vero e vero è vero. Ed ecco la magia: vero e falso è falso, quindi abbiamo spento quel po '. E ora il resto della storia è un po 'semplice. Poiché il resto della maschera è 1s, non importa quanto i numeri sono in bianco. Quando si "e" qualcosa con vero, non avete intenzione di cambiare il suo valore. Se è vero, rimane vero. Se fosse falso, rimarrà false.
Ma la magia accade quando si prende qualcosa che era vero e quindi si "e" con false. Questo ha l'effetto di spegnere tale bit. Quindi, un po 'là criptico. Diamo un'occhiata ad alcune realtà del codice, che potrebbe effettivamente sembrare ancora più criptico, ma diamo uno sguardo qui a tolower. Se guardo tolower, passando da maiuscola a minuscola a, vediamo come si potrebbe attuare questo programma. Ecco principale, e non è di prendere qualsiasi riga di comando argomenti. Sto dichiarando un carattere c per la lettera che l'utente sta per digitare trovi Ho quindi utilizzare un fai familiare ciclo while per fare solo in modo che l'utente dà sicuramente me la A maiuscola o B o C. .. Z, così mi danno qualcosa tra A e Z. E ora che ci faccio qui? Sono "o" ing questo con 0x20, ma che in realtà è lo stesso - e torneremo a questo in un momento - 32. Quindi, di nuovo, 32 è questo modello di bit qui. Perché lo sappiamo? Basta ripensare alla settimana 0. Questo è il luogo 1s, luogo 2s, 4s, 8s, 16s, 32s posto. Quindi questo numero giallo sembra essere 32. Posso quindi prendere una lettera come il carattere qui, bit per bit "o" letteralmente con il numero 32, e quello che faccio a tornare? La versione minuscola del char. Poco fa, però, ho espresso questo concetto in una notazione di base diversa. Che cosa rappresenta questo? >> [Studente] esadecimale. [Malan] Questo accade per rappresentare esadecimale. Non abbiamo parlato di esadecimale più di tanto, ma in realtà è utile in casi come questo.
Anche se sembra più complesso e anche se sembra 20 e non 32, si scopre che in realtà è super-esadecimale notazione conveniente perché in ogni cifra esadecimale dopo la 0x - e questo non significa nulla; questo è solo convenzione umana che dice che viene qui un numero esadecimale - ciascuna di queste cifre, il 2 e quindi lo 0, si può essere rappresentato con esattamente 4 bit. Quindi, se facciamo questo, vorrei aprire un editor di testo qui - strano completamento automatico - se facciamo un piccolo editor di testo qui, il numero 0x20 significa qui è di 4 bit, ecco altri 4 bit. Facciamo i 4 bit più a destra prima. 0 se rappresentato con 4 bit è che cosa? Super facile. Proprio tutti 0. Quindi 4 bit come 0s. Come si rappresentano il 2? E 'stato un po' da quando abbiamo fatto questo, ma è 0100. Quindi, questo è il posto 1s, questo è il posto 2s, e poi non importa ciò che gli altri posti sono. In altre parole, in esadecimale si potrebbe dire 0x20, ma se poi si pensa a cosa è il 2 e come viene rappresentato in binario, ciò che è lo 0 e come viene rappresentato in binario, le risposte a queste domande sono questo e questo, rispettivamente. Quindi 0x20 accade per rappresentare questo modello di 8 bit, che è appunto la maschera che volevamo. Quindi questa è per il momento solo un esercizio intellettuale, ma la realtà è in codice è in genere più comune per scrivere costanti come questo in esadecimale perché allora il programmatore può con relativa facilità, anche se richiede un po 'di carta e matita, capire ciò che quel modello di bit è perché non si può esprimere solo 0 e 1 in genere nel codice. Non si può andare 00010 e così via.
Devi scegliere notazioni decimali o esadecimale o ottale o altro. La maggior parte delle persone tendono a scegliere esadecimale semplicemente in modo che ogni numero rappresenta 4 bit e si può fare questo rapido calcolo. E ti agitare la mia mano a toupper, che è quasi lo stesso, sembra quasi identico. ToUpper capita di non utilizzare l'operatore o ma questo ragazzo e df. Che cosa rappresenta df? df? Chiunque? >> [Studente] 255. 255? Non 255. Sarebbe ss. Lasceremo questo come un po 'di esercizio. Ma se si va da 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 e poi quello che viene dopo il 9? Siamo un po 'fuori di cifre decimali, ma in esadecimale quello che viene dopo il 9? [Studente] a. >> Quindi a, b, c, d. Si può capire da lì quale schema di bit D rappresenta in realtà. E se fate i conti, vedremo che la maschera si finisce per tornare è identica a questa. Questo è f, tutti 1, e questo è d. Così df rappresenta quella maschera. Bene. E, infine, per non rendere le cose suono super, super tecnico, ma si supponga di voler scrivere un programma che fa questo. Lasciatemi andare avanti e fare binario, che è un programma in un file chiamato binary.c. E adesso lasciatemi correre binario e mi danno un numero intero non negativo. Cominciamo facile e digitare 0. Questo è ormai un programma che stampi un numero intero nella sua rappresentazione binaria. Quindi, se io giocare a questo gioco di nuovo e digitare solo 1, dovrei avere una rappresentazione a 32 bit di 1. Se lo faccio di nuovo con 2, dovrei ottenere questo. Se lo faccio 7, dovrei avere un 1s pochi alla fine e così via. Si scopre Dico questo perché con le operazioni bit per bit si può effettivamente fare una cosa anche altri. È possibile creare queste maschere in modo dinamico. Date un'occhiata a questo esempio quella finale che coinvolge operazioni bit per bit. Ecco la prima parte del codice, richiedere all'utente un numero, e insiste sul fatto che mi dai un numero intero non negativo. Ecco, questo è roba vecchia scuola. Ma ecco qualcosa che è piuttosto interessante.
Come faccio a stampare un numero in binario? Ho scorrere da che cosa a che cosa? Qual è la dimensione di un int in genere, almeno nel apparecchio? >> [Studente] 4. Sono le 4. Quindi 4 * 8 è 32 - 1 è 31. Quindi, se sto iniziando a contare dal 31, che rappresenta, a quanto pare, solo concettualmente, il bit 31 o il bit più alto ordine, che è questo tizio qui, che tale sarà il bit 0. Quindi questo è il bit 01 ... bit 31. Così che cosa è questo codice facendo? Si noti che questo ciclo for, anche se sembra criptico, è solo l'iterazione da 31 a 0. Tutto qui. Così la parte interessante ora deve essere in queste 5 righe qui. Si noti che in questa linea mi dichiara una maschera variabile chiamata per essere coerenti con la nostra storia di questi numeri gialli. E poi che cosa è questo facendo? Questo è un altro operatore bit per bit non abbiamo visto prima, molto probabilmente. E 'l'operatore spostamento a sinistra. Questo operatore fa questo. Qui è il numero 1, e se lo fai io spostamento a sinistra, sinistra shift, cosa pensi che abbia l'effetto di fare a quello individuale 1? Letteralmente lo spostamento sopra. Quindi, se il numero 1 è quello che hai a sinistra e si inizia inizializzando i a 31, cosa è che sta per fare? E 'intenzione di prendere questo numero 1 e spostarlo 31 posti qui. E perché non c'è ovviamente nessun altre cifre dietro di essa, quelli per impostazione predefinita sostituito con 0. Quindi, si inizia con il numero 1, che ovviamente si presenta così - e mi permette di disegnare sopra qui al centro. E poi come si passa le cose a sinistra, questo ragazzo va essenzialmente in questo modo. Ma non appena hai fatto, uno 0 si riempie trovi Se si sposta una seconda volta, va in questo modo e un altro 0 si riempie trovi
Lo spostamento di nuovo e poi un altro 0 si compilati Quindi, se si fa questa cosa di 1 << i 31 posti, si finisce per ottenere una maschera che è di 32 caratteri, quella più a sinistra di cui è un 1, tutto il resto di cui sono 0. E si scopre, per inciso, lo spostamento di un numero a sinistra in questo modo anche per coincidenza, e talvolta conveniente, ha l'effetto di fare ciò che a quel numero? >> [Studente] raddoppio. Raddoppiare perché ciascuna delle colonne - il luogo 1s, 2s luogo, luogo 4s, Posto 8s, 16s posto - Stanno tutti raddoppio, come si va a sinistra. O meglio, quando si sposta l'1s si sta andando a finire per raddoppiare il valore del numero. Si può finire per fare trasformazioni interessanti di cifre spostando tutto finito in questo modo da potenze di 2. Quindi, come fa questo lavoro? Questo dà poi mi una maschera che è tutto 0s tranne un 1 in proprio il posto che lo voglio, e poi questa espressione, che è stato rubato da toupper.c, è semplicemente dire: prendi il numero n che l'utente ha digitato, "E" con quella maschera, e che cosa hai intenzione di ottenere? Hai intenzione di ottenere un 1 se c'è un 1 in quella posizione mascherato, o avete intenzione di ottenere un 0 se non c'è. E così tutto il programma si è effettivamente ha un ciclo, e crea una maschera con un 1 qui, poi un 1 qui, poi un 1 qui sopra, e utilizza questo AND bit a bit trucco per dire che c'è un po '1 input dell'utente qui?
C'è un po '1 input dell'utente qui? E se è così, letteralmente stampare 1, altrimenti la stampa 0. Stiamo facendo questo con int solo perché è per questo che stiamo facendo 32 bit invece di 8, ma quello che abbiamo introdotto è dunque costui, AND bit per bit, questo OR bit per bit, e questo di spostamento a sinistra, che non sono spesso terribilmente utile, ma si scopre che può essere. Infatti, se si dovesse rappresentare qualcosa come un array di booleani solo per rappresentare vero o falso, si supponga di voler tenere traccia di se una stanza piena di 300 studenti è presente, è possibile dichiarare un array di dimensioni 300 di tipo bool in modo da ottenere 300 Caccio, ed è possibile impostare ogni su true se qualcuno è qui e false in caso contrario. Perché è che la rappresentazione in quella struttura dati inefficiente? Cosa c'è di male al progetto di tale struttura di dati, una matrice di 300 Caccio? Ciò è un bool, infatti, sotto la cappa? Anche questo è qualcosa che potrebbe non essere a conoscenza. Sembra che vi sia bool. Ricordate che tipo di creato che con il file cs50.h, che a sua volta include la norma bool. C è una specie di muta, però, quando si tratta di bool. Utilizza 8 bit per rappresentare ogni bool, che è completamente uno spreco perché ovviamente, quanti bit hai bisogno di rappresentare un bool? Situato a solo 1. Così si scopre che, se ora avete la possibilità con gli operatori bit a bit di manipolare singoli bit anche in un char, anche in un singolo byte, si scopre che potrebbe ridurre la quantità di memoria richiesta per rappresentare qualcosa di stupido così la struttura in stile dati l'intervento di un fattore 8. Invece di usare otto bit per rappresentare vero o falso, si può letteralmente utilizzare uno utilizzando un singolo byte per ogni otto studenti in classe e commutando 0-1 singoli bit utilizzando questi tipi di basso livello trucchi. Che davvero porre fine all'energia. Ci sono domande su operazioni bit per bit?
Gia '. >> [Studente] C'è un operatore esclusivo o? Sì. C'è un operatore esclusivo o che assomiglia a questo, ^, il simbolo carota, il che significa che solo la prima cosa o la seconda cosa può essere un 1 per l'uscita di un 1. Vi è anche un non, ~, che vi permetterà di invertire un 0 a 1 o viceversa pure. E c'è anche un operatore spostamento a destra, >>, che è l'opposto di quello che abbiamo visto. Bene. Prendiamo ora le cose ad un livello superiore. Abbiamo iniziato parlando di testo e quindi comprimendo e rappresenta il testo con un numero minore di bit; abbiamo parlato un po 'su come siamo in grado di iniziare a manipolare le cose a livello di bit per bit. Vediamo ora l'immagine di backup 10.000 piedi alla rappresentazione di cose più complesse come la grafica. Qui abbiamo una bandiera della Germania, qui abbiamo uno di Francia. Questi potrebbero essere rappresentati in formati di file che potresti conoscere - GIF, per esempio. Se hai mai visto un immagine sul web che termina con. Gif, si tratta di un formato di interscambio grafico. Queste due specie di bandiere qui si prestano a compressione per quale motivo forse ovvio? >> [Risposta degli studenti incomprensibile] Ci sono un sacco di ripetizioni, giusto? Per poter inviare bandiera della Germania, pensare a questo come un immagine sullo schermo eseguire nei vostri giorni Scratch. Si potrebbe ricordare che ci sono i singoli pixel o punti che compongono l'immagine.
C'è una fila di punti neri e un'altra fila di punti neri. Ci sono un sacco di righe di puntini neri che abbiamo potuto vedere se davvero ingrandita, un po 'come quando ci zoom sul volto di Rob in Photoshop. Non appena siamo arrivati sempre più in profondità e più in profondità l'immagine, è iniziato a vedere il pixelation, tutti i quadrati che compongono il suo occhio in questo caso. Stessa cosa qui. Se si ingrandisce un bel po ', si vedrebbe singoli punti. Bene, questo è una specie di uno spreco di bit. Se un terzo della bandiera è nero e un terzo della bandiera è gialla e così via, perché non possiamo in qualche modo comprimere questa bandiera? E anche la bandiera francese potrebbe essere compresso, anche se il modello è un po 'diverso. Si scopre il formato di file GIF è un formato di compressione senza perdita di dati, che significa che è possibile scattare una foto come la bandiera tedesca qui, si può buttare via un sacco di suoi bit senza sacrificare la qualità. Questo è in contrasto con qualcosa come JPEG, con la quale la maggior parte di noi sono probabilmente più familiare. Facebook foto e le foto di Flickr e simili sono quasi sempre salvati in formato JPEG quando vengono caricati, ma è un file JPEG lossy - formato in base al quale si fa buttare via i bit - LOSSY ma anche buttare via la qualità. E così se si comprime foto con Photoshop o caricarle su Facebook o portarli su un telefono davvero pessima, si sa che l'immagine inizia a diventare molto splotchy e pixelated, e questo perché si tratta di essere compresso dal computer o dal telefono letteralmente gettando le informazioni di distanza. Ma GIF è sorprendente in quanto può utilizzare meno bit di quanto potrebbe per impostazione predefinita senza perdere alcuna informazione.
E lo fa in modo essenzialmente come segue. Invece di memorizzare in un file come un BMP farebbe una tripla RGB per il nero, nero, nero, nero, nero, nero, nero, nero, nero, nero, nero, nero e così via, piuttosto, il formato GIF sta per dire, "Nero" e poi, "Ripetere questo 100 volte", o qualcosa del genere. "Black, ripetere questo 100 volte, neri, ripetere questo 100 volte ..." "Giallo, ripetere questo 100 volte." E così lo ricorda, in sostanza, il pixel più a sinistra codifica e quindi in qualche modo l'idea di ripetere quel pixel ancora e ancora. Così GIF possono allora comprimere senza perdere alcuna informazione. Ma se dovessi tirare a indovinare, se questo è l'algoritmo che Gifs uso, quale di queste bandiere, anche se sembrano identici nelle dimensioni, sta per essere più piccolo quando viene salvato su disco in formato GIF? >> [Studente] Germania. La Germania sta per essere più piccolo? Perché? [Studenti] Dato che si ripetono molte, molte volte in senso orizzontale e poi si ripete un'altra volta. >> Esattamente. Perché le persone che hanno inventato GIF solo tipo di arbitrariamente deciso che la ripetizione andrà a leva orizzontale e non lateralmente. C'è ripetizione molto più lateralmente qui la bandiera tedesca che nel bandiera francese. Quindi, se abbiamo effettivamente aprire una cartella sul disco rigido che ha questi GIF, si può effettivamente vedere che la bandiera tedesca: ecco 2 kilobyte e quello francese è di 4 kilobyte. Capita di essere una coincidenza che uno è due volte l'altro, ma è infatti il caso che la bandiera francese è molto più grande.
Anche se stiamo parlando di grafica, le stesse idee possono applicare a non le cose come bandiere, ma le immagini che sono un po 'più complesso. Se si scatta una foto di una mela, sicuramente ci sono un sacco di duplicazione lì, in modo da poter in qualche modo ricordare che lo sfondo predefinito è blu e non, come di destra immagine suggerisce, ricordare il colore di ogni singolo pixel in figura. Così possiamo buttare via i bit lì senza perdere informazioni. La mela sembra ancora lo stesso. In questo esempio qui, si potrebbe vedere cosa succede in un film. Questi rappresentano vecchia scuola bobine di film cioè se nell'immagine superiore ci si dispone di una guida RV passato una casa e un albero. E come quel furgone guida passato da sinistra a destra, cosa ovviamente non cambia? La casa non si va da nessuna parte, e l'albero non va da nessuna parte. L'unica cosa che si muove è il furgone in questo caso. Così come sfondo Invariato suggerisce, cosa si può fare nei film è altrettanto giusto buttare via le informazioni che non cambia tra i fotogrammi. Questo è generalmente noto come compressione interframe per cui se questo telaio sembra quasi identico a questo, cerchiamo di non preoccuparsi memorizzazione su disco tutte le informazioni identiche su questi fotogrammi intermedi, cerchiamo di utilizzare solo i fotogrammi chiave di tanto in tanto che in realtà conservare tali informazioni in modo ridondante come un po 'di sanità mentale controllo.
Per contro, un altro approccio per comprimere il video è in questo secondo esempio qui e inferiore, dove invece di negozio di 30 fotogrammi, perché non solo memorizzare 15 fotogrammi al secondo, invece? Piuttosto che il tipo di film che scorre meravigliosamente, perfettamente, potrebbe apparire come se fosse la balbuzie un po ', una scuola po' vecchio, ma l'effetto netto sarà quello di utilizzare i bit molte meno potrebbero altrimenti necessari. Pertanto, qual è allora ci lascia? E 'stato un po' di parte su dove altro si può andare con la compressione. Per saperne di più su questo, prendere una classe come CS175 qui. Ecco un altro esempio all'interno del video. Se l'ape è l'unica cosa in movimento, si può davvero buttare via informazioni in quei fotogrammi intermedi perché il fiore e il cielo e le foglie non stanno cambiando. Ma andiamo ora a considerare un'ultima cosa. Nei prossimi 5 minuti ci lasciamo alle spalle per sempre C nella lezione? Sì. Non nei pset, però. Storia di Ultimo su C e poi si arriva a cose molto sexy coinvolgendo HTML e Web e woo-hoo. Bene. Ci siamo. Questa è la motivazione. E 'venuto fuori tutto questo tempo in cui siamo stati la scrittura di programmi che corriamo Clang. E Clang, abbiamo detto fin dalla prima settimana più o meno, prende il codice sorgente e lo converte in codice oggetto. Prende C e converte in 0 e 1. Ho tipo di mentito a voi per un paio di settimane, perché non è così semplice come sembra.
C'è molto di più in corso sotto la cappa quando si esegue un programma come Clang. Infatti, il processo di compilazione di un programma può realmente essere sintetizzati, come si potrebbe ricordare da un video di Rob su compilatori, in queste 4 fasi: pre-elaborazione, la compilazione stessa, montaggio e collegamento. Ma noi in classe e la maggior parte delle persone nel mondo in genere riassumere tutti questi passaggi semplicemente come "compilazione". Ma se si parte con il codice sorgente di questo tipo, ricordo questo è forse il più semplice programma C che abbiamo scritto fino ad ora, ricordare che durante la compilazione finisce per assomigliare a questa. Ma c'è effettivamente una fase intermedia, e quei passi sono i seguenti. In primo luogo c'è questa cosa al vertice di questo e la maggior parte dei nostri programmi, # Include Cosa fa # include fare per noi? E 'più o meno copie e Incolla il contenuto degli stdio.h nel mio file in modo che il motivo? Perché mi interessa circa il contenuto del stdio.h? Cosa c'e 'dentro di interesse? Printf dichiarazione, il suo prototipo, in modo che il compilatore sa quindi cosa voglio dire quando ho detto questa funzione printf. Quindi, il punto 1 della compilazione è pre-elaborazione, per cui un programma come Clang o qualche programma di supporto che viene fornito con Clang legge il codice in alto verso il basso, da sinistra a destra, e ogni volta che vede un simbolo # seguito da una parola chiave come includono, esegue questa operazione, copiare e incollare in questo caso stdio.h nel file. Ecco passo 1. Poi si ha un file molto più grande C a causa della copia grande, lavoro incolla che è appena accaduto.
2 Passo ora sta compilando. Ma si scopre la compilazione del codice sorgente si che assomiglia a questo e si trasforma in qualcosa che assomiglia a questo, che per chi ha familiarità si chiama? >> [Studente] Assemblea. Assemblea lingua >>. Questo è in realtà qualcosa che se si prende CS61 ti tuffarsi in modo più dettagliato. Questo è solo quanto di più vicino si può arrivare a scrivere 0 e 1 se stessi ma scrivere le cose in un modo che rende ancora almeno un po 'di senso. Si tratta di istruzioni macchina, e se scorrete fino alla funzione principale qui, notato che c'è questa istruzione spinta, spostare l'istruzione, sottrarre istruzione, chiamare l'istruzione, e così via. Quando si sente che il vostro computer è dotato di processore Intel all'interno, si dispone di una CPU Intel nel vostro Mac o PC, che cosa significa? Una CPU viene costruito da aziende come Intel capire determinate istruzioni. Non hanno idea di cosa funzioni come swap sono, o quanto meno sono di per sé, ma sanno cosa molto istruzioni di basso livello, come addizione, sottrazione, spingere, spostare, chiamare, e così via sono. Così, quando si compila il codice C in linguaggio assembly, molto facile da usare il tuo codice dall'aspetto viene convertito in qualcosa che assomiglia a questo, che si muove letteralmente byte o 4 byte in giro in queste piccole unità dentro e fuori della CPU. Ma alla fine, quando Clang è pronta a prendere questa rappresentazione del vostro programma in 0 e 1, allora il passo chiamato assemblaggio avviene, e questo ancora una volta tutto avviene in un batter d'occhio durante l'esecuzione Clang. Cominciamo qui, genera un file in questo modo, e poi lo converte in questi 0 e 1. E se si vuole tornare ad un certo punto e in realtà vedere in azione, se vado in hello1.c--questo è uno dei primi programmi che abbiamo esaminato - normalmente avremmo compilare questo con hello1.c Clang e questo ci darebbe a.out. Se invece voi invece dare il flag-S, quello che otterrete è hello1.s e ci troveremo a vedere il linguaggio assembly.
Lo sto facendo per un programma molto breve, ma se si va indietro per Scramble o recupero o qualsiasi altro programma che hai scritto e solo per curiosità Voglio vedere quello che si presenta come, ciò che è effettivamente immessa nella CPU, è possibile utilizzare tale-S contrassegna con Clang. Ma poi, infine, c'è ancora un dettaglio. Ecco le 0 e 1 che rappresentano la mia implementazione di ciao, mondo. Ma ho usato la funzione di qualcun altro nel mio programma. Così, anche se il processo è stato prendo hello.c, Viene compilato in codice assembly, e poi viene assemblato in 0 e 1, il solo 0 e 1 che sono emessi a questo punto nel tempo sono quelli che derivano dal mio codice. Ma la persona che ha scritto printf, hanno compilato il loro codice 20 anni fa ed è ora installato da qualche parte l'apparecchio, quindi in qualche modo necessario unire 0s suoi e 1 con la mia 0 e 1, e che ci porta al passo 4 e il finale di compilazione, noto come collegamento. Quindi, sulla sinistra abbiamo il quadro esatto stessa di prima: hello.c diventa codice assembly diventa 0 e 1. Ma ricordo che ho usato lo standard libreria I / O nel mio codice, e questo significa che da qualche parte nel computer c'è un file chiamato stdio.c o almeno la sua versione compilata perché qualcuno alcuni anni fa stdio.c compilato in codice assembly e quindi tutta una serie di 0 e 1. Questo è ciò che è noto come un statico o una libreria dinamica. E 'qualche file seduto da qualche parte in macchina.
Ma, infine, devo prendere il mio 0 e 1 e che la persona 0 e 1 e in qualche modo li collegare tra loro, letteralmente unire quelli 0 e 1 in un unico file chiamato a.out o Hello1 o qualsiasi altra cosa ho chiamato il mio programma in modo che il risultato finale ha tutti gli 1 e 0 che dovrebbe compongono mio programma. Quindi, tutto questo tempo in questo semestre in cui hai utilizzato Clang e ancor più di recente si esegue make per eseguire Clang, tutti questi passaggi sono stati accadendo sorta di istantaneamente, ma molto deliberatamente. E quindi se si continua su in informatica, vale a dire CS61, questo è il livello che si continuano a staccare fuori là parlando di efficienza, implicazioni di sicurezza, e simili di questi dati di livello inferiore. Ma con questo, siamo in procinto di lasciare C dietro. Andiamo avanti e prendere la nostra pausa di 5 minuti ora, e quando torneremo: Internet. Bene. Siamo tornati. Ora cominciamo il nostro sguardo non solo a HTML perché, come si vedrà, HTML in sé è in realtà piuttosto semplice ma in realtà in programmazione web più in generale, la messa in rete più in generale, e come tutte queste tecnologie si incontrano per permetterci di creare programmi molto più sofisticati in cima alla Internet che fino ad ora siamo stati in grado in queste finestre in bianco e nero. In effetti, a questo punto, nel semestre, anche se passeremo il tempo relativamente meno su PHP, HTML, CSS, JavaScript, SQL e di più, maggior parte degli studenti finiscono per fare progetti finali che sono web-based perché, come si vedrà, sullo sfondo, ora in C è molto applicabile a questi linguaggi di livello superiore.
E come si inizia a pensare al tuo progetto finale, che, proprio come Set problema 0, in cui si sono stati incoraggiati di fare qualsiasi cosa di vostro interesse in Scratch, il progetto finale è la vostra occasione per prendere la vostra conoscenza ritrovata e buon senso con C o PHP o JavaScript o simili fuori per un giro e creare il vostro pezzo molto personale di software per il mondo a vedere. E per seme che con le idee, sappiate che è possibile dirigersi qui, projects.cs50.net. Ogni anno, sollecitare idee da docenti e personale e gruppi di studenti nel campus solo a presentare le loro idee per le cose interessanti che potrebbero essere risolti con i computer, utilizzando siti web, utilizzando il software. Quindi, se stai lottando per venire con l'idea di tuo, con tutti i mezzi scorrere le idee ci da quest'anno e l'ultimo. E 'perfettamente bene per affrontare un progetto che è stato affrontato in precedenza. Abbiamo visto molte applicazioni per vedere lo stato della biancheria nel campus, molte applicazioni per la navigazione del menu sala da pranzo, molte applicazioni per la navigazione del catalogo dei corsi e simili. E in effetti, in una conferenza futuro e in seminari futuri, vi presentiamo alcune API a disposizione del pubblico, sia disponibile in commercio così come qui disponibile da CS50 nel campus in modo da avere accesso ai dati e può fare cose interessanti con esso. Quindi più sui progetti definitivi tra qualche giorno quando abbiamo rilasciare le specifiche, ma per ora, so che si può lavorare da solo o con uno o due amici sulla maggior parte qualsiasi progetto di vostro interesse. Internet. Si va avanti e tirare fuori il vostro computer portatile, si va a facebook.com per la prima volta, non aver effettuato il login di recente, e premere Invio. Che cosa succede esattamente?
Quando si preme Invio sul vostro computer, un sacco di passi avviare una sorta di magia accadendo. Così qui a sinistra, il server web come Facebook è qui a destra, e in qualche modo si sta utilizzando questo linguaggio chiamato HTTP Hypertext Transfer Protocol. HTTP non è un linguaggio di programmazione. E 'più di un protocollo. Si tratta di un insieme di convenzioni che i browser web e server web usano quando intercomunicante. E che cosa questo significa è il seguente. Proprio come nel mondo reale, abbiamo queste convenzioni dove se si incontra qualche essere umano per la prima volta, se non ti dispiace assecondando me qui, Io possa venire da voi, dire: "Ciao, il mio nome è David." >> Ciao, David. Il mio nome è Sammy. "Ciao, David. Mio nome è Sammy". Così ora abbiamo appena impegnati in questo tipo di sciocco protocollo umano dove ho iniziato il protocollo, Sammy ha risposto, abbiamo stretto la mano, e la transazione è completata. HTTP è molto simile nello spirito. Quando il web browser richiede www.facebook.com, che cosa il vostro browser è davvero facendo sta estendendo la sua mano, per così dire, al server e lo sta mandando un messaggio. E questo messaggio è in genere qualcosa di simile a ottenere - che cosa si vuole ottenere? - farmi la home page, che in genere è indicato da una barra singola alla fine di un URL. E solo così sai che lingua sto parlando, il browser sto per dirvi che sto parlando versione HTTP 1.1, E anche per buona misura, ho intenzione di dirvi che l'host che voglio la home page di è facebook.com. In genere, un browser web, a tua insaputa, l'umano, invia questo messaggio attraverso Internet, quando è sufficiente digitare www.facebook.com,
Inserire, nel browser. E che cosa risponde con Facebook? Risponde con alcuni dettagli criptici simili di aspetto, ma anche molto di più. Lasciami andare avanti alla home page di Facebook qui. Questa è la schermata che la maggior parte di noi probabilmente mai vedere se rimanere connesso tutto il tempo, ma questa è davvero la loro home page. Se lo facciamo in Chrome, notare che è possibile tirare su questi menu contestuali piccoli. Con Chrome, sia su Mac OS, Windows, Linux, o simili, Se controlli click o click sinistro, in genere è possibile tirare su un menu simile a questo, dove alcune opzioni attendono, uno dei quali è Visualizza sorgente pagina. È inoltre possibile ottenere in genere a queste cose andando al menu Visualizza e rovistando. Ad esempio, qui sotto Vista, gli sviluppatori è la stessa cosa. Ho intenzione di andare avanti e guardare View Page Source. Quello che vedrete è il codice HTML che Marco ha scritto per rappresentare facebook.com. E 'un casino completo qui, ma vedremo che questo ha un senso un po' più in breve tempo. Ma ci sono alcuni modelli qui. Permettetemi di scorrere verso il basso per cose come questa. Questo è difficile per un essere umano di leggere, a meno di notare che c'è questo modello di staffe angolari con parole chiave come opzione, parole chiave come valore, alcune stringhe tra virgolette. E 'qui che, quando ti sei iscritto per la prima volta, specificato che cosa il vostro anno di nascita è. Questo menu a discesa di anni di nascita è in qualche modo codificato qui in questo linguaggio chiamato HTML, HyperText Markup Language. In altre parole, quando il browser richiede una pagina web, parla questa convenzione chiamata HTTP. Ma che cosa facebook.com rispondere a tale richiesta con?
Risponde con alcuni di questi messaggi criptici, come vedremo tra un attimo. Ma la maggior parte della sua risposta è in forma di HTML, HyperText Markup Language. Questo è il linguaggio vero e proprio in cui è scritta una pagina web. E ciò che un browser web davvero è quindi, al momento del ricevimento di qualcosa che assomiglia a questo, lo legge dall'alto in basso, da sinistra a destra, e ogni volta che vede una di queste staffe angolari seguito da una parola chiave, come opzione, viene visualizzato che il linguaggio di markup in modo appropriato. In questo caso, sarebbe visualizzare un menu a discesa di anni. Ma ancora una volta, questo è un disastro completo da guardare. Questo non è perché gli sviluppatori di Facebook manifestano 0 per 5 per lo stile, per esempio. Questo è perché la maggior parte del codice che scrivere è, infatti, scritto magnificamente, ben commentata, ben rientrato, e simili, ma di macchine di corso, computer, browser in realtà non me ne frega niente se il codice è ben stile. E infatti, è del tutto uno spreco di colpire il tasto di tabulazione tutte quelle volte e di mettere tutti i commenti in tutto il codice e scegliere i nomi delle variabili molto descrittivi perché se il browser non importa, tutto quello che stai facendo, alla fine della giornata sta sprecando byte.
Così si scopre che la maggior parte siti web non è, anche se il codice sorgente per facebook.com, per cs50.net e tutti questi altri siti web su Internet sono in genere ben scritto e ben commentato e ben frastagliata e simili, di solito prima che il sito viene messo su Internet, il codice viene minified, in base al quale il codice HTML e CSS - qualcos'altro vedremo presto - il codice JavaScript vedremo presto è compresso, in base al quale a lungo i nomi delle variabili diventano X e Y e Z, e tutto questo spazio bianco che fa sembrare tutto in modo leggibile è tutto buttato via, perché se ci pensi in questo modo, Facebook ottiene un miliardo di pagina contatti al giorno - qualcosa di folle del genere - così che cosa se un programmatore solo per essere anale premere la barra spaziatrice una volta in più solo per far rientrare qualche linea di codice sempre molto di più? Qual è l'implicazione se Facebook conserva che gli spazi bianchi in tutti i byte rimandano a persone su Internet? Premendo la barra spaziatrice una volta che si dà un byte extra nel file. E se un miliardo di persone quindi procedere al download della pagina casa quel giorno, quanti più dati hai trasmesso su Internet? Un gigabyte per nessuna buona ragione. E concesso, per un sacco di siti web non si tratta di una questione scalabile, ma per Facebook, per Google, per alcuni dei siti più popolari c'è grande incentivo finanziario per rendere il codice apparire come un pasticcio in modo che si sta utilizzando come byte meno possibile in aggiunta per poi comprimere usando qualcosa come zip, un algoritmo chiamato gzip, che il browser fa per voi automaticamente. Ma questo è terribile. Non riusciremo mai a imparare qualcosa su siti web di altre persone e come progettare le pagine web se dobbiamo vedere le cose in questo modo.
Quindi, per fortuna, browser come Chrome e IE e Firefox in questi giorni in genere sono dotati di built-in strumenti di sviluppo. Infatti, se scendo qui per Inspect Element o se vado a visualizzare, Developer, e andare in Strumenti per gli sviluppatori in modo esplicito, questa finestra nella parte inferiore del mio schermo si apre ora in su. E 'un po' intimidatorio in un primo momento, perché ci sono un sacco di schede sconosciuti qui, ma se clicco su elementi tutta la strada in basso a sinistra, Chrome è ovviamente piuttosto intelligente. Si sa come interpretare tutto questo codice. E così ciò che Chrome non fa altro che pulisce tutto l'HTML di Facebook. Anche se non c'è spazio qui, non c'è indentazione lì, ora notare che posso cominciare a navigare questa pagina web ancora più gerarchicamente. Si scopre che ogni pagina web scritto in un linguaggio chiamato HTML5 dovrebbe iniziare con questo, questa dichiarazione DOCTYPE, per così dire: È un po 'di luce e di colore grigio lì, ma questa è la prima riga di codice in questo file, e che dice solo il browser, "Ehi, ecco che arriva un po 'di HTML5. Ecco una pagina web." La prima staffa aperta oltre che sembra essere questa cosa, un sistema open tag HTML staffa, e poi se mi tuffo in profondità - queste frecce sono completamente priva di senso; sono solo per amor di presentazione, essi non sono in realtà nel file - notare che all'interno del tag HTML di Facebook, tutto ciò che inizia con una parentesi aperta e poi ha una parola si chiama un tag. Quindi, all'interno del tag HTML è apparentemente un tag head e un tag body. All'interno del tag head ora è un casino per Facebook perché hanno un sacco di metadati e altre cose per il marketing e la pubblicità.
Ma se scorrere verso il basso, giù, giù, giù, vediamo dove si trova. Eccolo. Questo è almeno un po familiare. Il titolo della home page di Facebook, se mai e visualizzare la scheda nella barra del titolo, è Welcome to Facebook - Log In, Registrati o saperne di più. Questo è quello che si vede nella barra del titolo di Chrome, ed è così che è rappresentato nel codice. Se ignoriamo tutto il resto nella testa, la maggior parte delle viscere di una pagina web sono nel corpo, e si scopre che il codice di Facebook sta andando a guardare più complessa rispetto alla maggior parte le cose che scriveremo inizialmente solo perché è stato costruito nel corso degli anni, ma c'è un sacco di tag script, il codice JavaScript, che rende il sito molto interattivo: vedere gli aggiornamenti di stato istantaneamente utilizzando linguaggi come JavaScript. C'è qualcosa chiamato un div, che è una divisione di una pagina. Ma prima di arrivare a questo dettaglio, cerchiamo di diminuire e guardare una versione più semplice di Facebook 1.0, per così dire. Ecco il ciao, mondo delle pagine web. E 'che la dichiarazione DOCTYPE al vertice che è un po 'diverso da tutto il resto. Niente altro che scrivere in una pagina web sta per iniziare con per il grassetto. Anche in questo caso, la storia è la stessa: ciao, virgola, iniziare a fare questo audace, allora il mondo viene stampato in grassetto, e questo significa interrompere la stampa presente in grassetto. Lasciatemi andare avanti e salvare il mio file, tornare a Chrome, mi ingrandire solo così possiamo vedere meglio, e ricaricare, e vedrete che il mondo è ora in grassetto. Il Web è tutto su collegamenti ipertestuali, quindi cerchiamo di andare avanti e fare questo: il mio sito preferito è, diciamo, youtube.com. Salva, ricaricare. Va bene. Ci sono un paio di problemi ora, oltre alla bruttezza del sito. 1, sono abbastanza sicuro che mi ha colpito Inserire qui. E l'ho fatto. Non solo premere Invio, ho anche frastagliata, praticando quello che abbiamo predicato di stile, ma il mio è proprio accanto al mondo. Allora, perché è questo? I browser solo fare quello che dicono loro di fare. Non ho detto al browser, "linee pausa qui. Inserisci punto rompere qui." Quindi il browser, non importa se mi ha colpito di ritorno 30 volte, è ancora in corso di mettere la mia accanto al mondo. Quello che mi hanno veramente a fare qui è dire qualcosa di simile
, inserire un'interruzione di riga.
E in realtà, una interruzione di linea è una specie di una cosa strana perché non si può davvero iniziare a muoversi a un'altra linea, poi fare qualcosa, e poi si fermano per una nuova linea. È una specie di operazione atomica. O lo fai o non lo fai. Si premere Invio o non lo fai. Così br è un po 'di una variabile diversa, e quindi ho bisogno di ordinare sia aperto e chiuderlo tutto in una volta. La sintassi per questo che è. Tecnicamente, si potrebbe fare qualcosa di simile in alcune versioni di HTML, ma questo è solo stupido, perché non c'è alcun motivo per avviare e fermare qualcosa se in alternativa puoi fare tutto in una volta. Rendetevi conto che HTML5 non impongono questa barra, così potrete vedere i libri di testo e le risorse on-line che non ce l'hanno, ma per buona misura cerchiamo di praticare la simmetria che abbiamo visto finora. Ciò significa che l'etichetta sia aperto e chiuso. Così ora vorrei salvare il mio file, tornare qui. Ok, allora si comincia a guardare meglio, ad eccezione del Web so è una specie di cliccabile, eppure youtube qui non sembra portare a nulla. Questo perché, anche se sembra un collegamento, il browser non sa che di per sé, quindi devo dire al browser che si tratta di un link.
Il modo per farlo è quello di utilizzare un tag di ancoraggio: e lasciatemi passare ad una nuova riga solo così è un po 'più leggibile, e io ridurre la dimensione del carattere. Sto ancora finito? No. Non vi sarà questa dicotomia. Questo tag, il tag di ancoraggio, tiene effettivamente un attributo, che modifica il suo comportamento, e il valore di tale attributo è apparentemente l'URL di YouTube. Ma bando la dicotomia è che solo perché questo è l'indirizzo che si vuole, ciò non significa che deve essere la parola che si sta evidenziando e facendo un link. Piuttosto, che può essere una cosa del genere. Quindi devo dire smettere di fare questa parola un collegamento ipertestuale utilizzando il tag di chiusura di ancoraggio. Si noti che non sto facendo questo. 1, questo sarebbe solo uno spreco di tempo di tutti e non è necessario.
Per chiudere un tag, è sufficiente citare il nome del tag di nuovo. Lei non dice gli attributi. Quindi cerchiamo di salvare quella, tornare indietro. Ok, voilà, ora è blu e collegamenti ipertestuali. Se mi clic su di esso, ho fatto fare andare su YouTube. Così, anche se la mia pagina web non è su Internet, è almeno HTML, e se lasciamo che il Internet raggiungere, ci sarebbe in realtà finisce qui su youtube.com. E posso tornare indietro ed ecco la mia pagina web. Ma nota questo. Se hai mai ricevuto spam o un attacco di phishing, ora si ha la possibilità dopo appena cinque minuti per fare lo stesso. Si può andare qui e fare qualcosa di simile www.badguy.com o qualsiasi altra cosa il sito web è impreciso, e allora si può dire verificare il tuo conto PayPal. [Risate] E ora questo sta per andare a badguy.com, che io non ho intenzione di fare clic su perché non ho idea di dove che porta. [Risate]
Ma ora abbiamo la possibilità di finire in realtà lassù. Quindi siamo davvero iniziando a graffiare la superficie. Non stiamo programmando di per sé, stiamo scrivendo linguaggio di markup. Ma non appena si completano nostro vocabolario in HTML, si introducono i PHP, un linguaggio di programmazione vero che ci permetterà di generare automaticamente codice HTML, CSS generare automaticamente, in modo che possiamo cominciare ad attuare il Mercoledì, per esempio, il nostro motore di ricerca e altro ancora. Ma più su che in un paio di giorni. Ci vediamo allora.
[CS50.TV]