[Powered by Google Translate] [Uke 7] [David J. Malan - Harvard University] [Dette er CS50. - CS50.TV] All høyre. Velkommen tilbake. Dette er CS50, og dette er begynnelsen av uke 7. Et par små kunngjøringer: Pset5 er nå i gang, eller snart skal være, og la meg si, helt ærlig, dette har en tendens til å være blant de mer utfordrende av kursets oppgavesett, så la meg nevne dette nå slik at denne uken mer enn noen gang du ikke vente til, si, onsdag kveld eller torsdag kveld for å dykke i. Dette er definitivt en interessant pset. Vi synes det er gøy. Hvis du faktisk få det helt riktig, og kan deretter utfordre den såkalte Big Board, har du en mulighet til å matche vettet med noen av kursets ansatte og noen av klassekameratene dine. What The Big Board er er når du har din spell-checker arbeid, vil du være i stand til å gå til cs50.net etter å ha kjørt en kommando, rent melde deg på, og deretter hvor mye tid og hvor mye RAM og mer at du har brukt i gjennomføringen vil bli utstilt her på kurset hjemmeside. Du vil merke at en hel haug av disse folkene her er oppført som ansatte siden over helgen, trodde ansatte det ville være morsomt å prøve å overgå hverandre. Så innser at målet her er ikke å overgå de ansatte. Selv er jeg bare her på nummer 13. Rent velge i, men det er en mulighet til å se hvor lite RAM og hvor få CPU sekunder kan du bruke vis-a-vis noen av dine klassekamerater. Og jeg skal innrømme at Kevin Michael Schmid, tiden i nummer 1 posisjon som en av de TFS, Dette er en implementering som vi kaller ikke mulig gitt at han bruker nesten 0 RAM og nesten 0 sekunder for lasting. Så vi vil ta vare på Kevin offline. [Latter] Det er visse ferdigheter som Kevin er å sette på prøve her. En av de tingene vi trodde vi ville gjøre er også nå CS50x er en uke i gang, og dere er like mye en del av dette eksperimentet som de studentene er. Vi har spurt dem som en del av pset0 deres, som var på samme måte for å sende inn en Scratch prosjekt av interesse for dem - et spill, en interaktiv kunstverk, en animasjon eller lignende - en 1 - til 2-minutters video, hvis de ønsker, sier hei til verden og hvem de egentlig er. Jeg tenkte jeg skulle dele med dere bare et par av videoene som har blitt sendt så langt fordi for oss, på de ansatte minst, det virkelig har vært spennende og inspirerende å se disse folkene fra hele verden - land over hele verden - tuning i, av alle ting, til en datamaskin science kurs på internett, enten det er fordi de ønsker å fortsette sine egne studier, de ønsker å ta sine karrierer i en ny retning, de ønsker å fylle hullene i sin egen kunnskap, så noen av de samme grunnene som dere kanskje har vært her. Så jeg gir deg en slik student her. Du kan øke volumet bare litt. Her er en av våre studentens en liten innleveringer. Hei, verden. Jeg er en student av industri her i Malaga, Spania. Jeg er begeistret for dette online kurset fordi jeg elsker informatikk, det gjør jeg virkelig, og jeg virkelig setter pris på at jeg kommer til å utforske den. Og det faktum at jeg kan lære det samme alle dere gjør men i stedet for å være i Harvard Jeg er i Malaga, hvor fantastisk er det? Vel, jeg er Fernando, og dette er CS50. Se dere. [Latter] En annen klipp vi liker spesielt godt, vil du finne at denne herren engelsk er ikke så sterk. Det ser ut som han hadde det maskin oversatt, så oversettelsene selv er litt mangelfull, men dette var en av våre favoritter så langt så vel. [♪ ♪] Hei, verden. [Snakker i japansk] [Jeg må hilse på japansk fordi min engelsk er svært upålitelige.] [Jeg har levert meldingen til deg fra byen Gifu, Japan.] [Jeg kan være en student for første gang på 20 år, som kan sees.] [Jeg er veldig takknemlig til Harvard University som ga meg denne muligheten, og EDX.] [Golf er en gitar og min favoritt ting i gang.] [Latter] [♪ ♪] [Hvorfor tror du jeg prøvde å delta på en cs50x.] [Harvard University, er det min lengsel.] [Spesielt hvis jeg er langt tilstedeværelse bodde i Japan.] [Jeg ønsket å prøve en gang klar over eksistensen av en slik EDX når.] [Tror du ikke så trenger du ikke relatert til alder av læring I.] [CS50 er min lengsel. Mitt navn er Kazu, og dette er CS50.] [♪ ♪] [applaus og jubel] En annen favoritt av våre var dette brevet her fra noen. [♪ ♪] [Malan] Google det hvis du ikke er kjent med denne meme. Og så til slutt, et par andre som fikk lagt det kanskje vinne den bedårende prisen. [Studenter] Aww! >> [Malan] Vi må lytte. Dette er kort, så hør nøye. [Kvinnelige speaker] Hva heter du? >> Louie. [Kvinnelige speaker] Hva er dette? >> [Giggles] CS50. [Latter] [Malan] Han gjorde to tar, skjønt. Here we go, den siste. Mitt navn er Louie, og dette er CS50. [Latter] Dette er da CS50x. Takk til alle de av dere mens du følger langs hjemme som har vært partaking så langt. I dag, konkluderer vi vår diskusjon av datastrukturer, det minste noen av de mest fundamentale, og vi fortsetter vår samtale om HTML og web-programmering. Faktisk har vi brukt de siste noen syv uker ser på det grunnleggende av programmering - algoritmer, datastrukturer og lignende - og C, som du kanskje har opplevd så langt, er ikke nødvendigvis den mest tilgjengelige av språk som å gjennomføre noen av disse ideene. Og så starter denne uken og neste uke, og deretter følgende, Vi vil til slutt være i stand til å overgangen fra C, som er allment kjent som en ganske lavt nivå språk, til ting høyere nivå, blant dem PHP, JavaScript, og lignende, som vi vil se trekke på de samme erfaringene som vi har lært i løpet av de siste ukene, men du vil finne at erklære ting som matriser og hash tabeller og søking og sortering blitt så mye enklere fordi språkene selv vi begynne å bruke vil bli kraftigere. Men først, en applikasjon av trær. Det er svært vanlig i disse dager til å trenge å komprimere informasjon. I hvilken sammenheng du ønsker å komprimere en slags digital informasjon? Ja. >> [Student] Når du trenger å sende den over Internett. Ja, når du ønsker å sende noe over nettet. Hvis du ønsker å laste ned en stor fil, er det ideelt hvis noen i den andre enden har komprimert filen ved hjelp av en zip-format eller noe sånt slik at du sender færre bits enn ellers kunne overføres. Så hvordan komprimere du informasjon? Det hele koker ned til å bruke færre biter enn det som er påkrevd. Men dette er en slags merkelig ting fordi tenker tilbake til uke 0 og 1 når vi snakket om ASCII og binær og vi snakket om ASCII spesielt som bruker 8 bits til å representere bokstaver i alfabetet slik at bokstaven A er representert ved 65, små bokstaver a er nummeret 97, og hvordan du representerer 65 eller 97, bruker du 7 eller 8 bits. Men fangsten er at det er noen bokstaver i det engelske alfabetet som ikke er like populær som andre. Z er ikke alle som populær, Q er ikke alle som populær, men A og E er super populære. Og likevel for alle disse brevene, som standard i verden bruker samme antall biter, bare 8. Så ville ikke det ha vært smartere hvis stedet for å bruke 8 biter for hver bokstav, selv de mest sjelden brukt som Q og Z, hva om vi brukte færre bits for A og E og S og de mest populære bokstaver og brukt flere biter for de mindre populære bokstaver, ideen er la oss optimalisere for vanlig sak, som er et tema i informatikk for å prøve å optimalisere hva som kommer til å skje mest og tilbringe litt mer tid, litt mer plass på de tingene som, ja, kan skje men ikke nødvendigvis som ofte. Så la oss ta et eksempel. Anta at vi ønsker å kryptere informasjon ganske effektivt. Du har kanskje vokst opp å vite noe om morse, og oddsen er du ikke kjenner den faktiske koden, men du husker kanskje at det er minst denne serien av prikker og streker. Dette er en ganske effektiv koding, og merker at den mest populære brev - for eksempel E - bruker den korteste av piper. Morse handler om pip-pip-pip-pip-pip-pip og holde toner enten for korte perioder eller lange perioder. E, som vist ved punktum, er en super kort pip, bare pip, og det ville representere E. I motsetning vil T være en lengre pip, som pip [forlenger lyd], og det ville representere T. Men det er fortsatt ganske kort fordi derimot hvis du ser på Z, å uttrykke Z du ville gå pip, pip [lengre lyd], pip, pip [kortere lyd]. Så det er lenger fordi det er mindre vanlig. Men fikser her er at morse er litt feil i at det er ikke umiddelbart dekodes. For eksempel anta at du hører på noen enden av ledningen pip [kort], pip [lang]. Hvilket budskap har jeg bare motta? En prikk og en strek. Hva representerer det? [Student] A. >> [Malan] Kanskje. Det kan også være E etterfulgt av T. Med andre ord, morse, selv om det benytter dette prinsippet optimalisere hjørnet tilfellet det ikke egner seg til umiddelbar decodability. Det vil si at mennesket som er å høre eller motta disse prikker og streker må liksom finne ut hvor pausene er mellom bokstaver, fordi hvis du ikke vet hvor disse pausene er, kan du forvirre A for ET eller vice versa. Så hva kan du gjøre? I morse kan du bare ta en pause mellom hver av bokstavene. Men pause er slags motsetning til hele poenget med å påskynde ting opp. Så hva om stedet vi kom opp med en kode der det ikke var så ille situasjonen hvor E er et prefiks for eksempel A - med andre ord, hvis vi kunne sørge for at oppskriftene er fortsatt kort for de populære bokstaver lang for de mindre populære bokstaver, men det er ikke mulig forvirring? En mann ved navn Huffman år siden oppfant denne ordningen kalles Huffman koding som utnytter faktisk en av de datastrukturer vi har brukt litt tid på å snakke om denne siste uken, som av trær, binære trær spesielt - et binært tre som betyr at den ikke har mer enn 2 barn. Det har kanskje en venstre barn, kanskje en høyre barn, og det er det. Så antar bare for moro skyld diskusjonen at noen ønsker å sende en melding som ser slik ut. Det er fullstendig meningsløst, men det er sammensatt av As, B, Cs, Ds, og Es. Og hvis du faktisk telle opp alle As, B, Cs, Ds, og Es og deretter dele på totalt antall brev, denne lille diagrammet her sier at 45% av bokstavene er Es, 20% er As, 10% B, og så videre. Så med andre ord, antar at den oppgitte strengen der er bare noen melding om at du ønsker å sende. Det skjer for å være tull, så vi kan bruke så få bokstaver som mulig, men det er faktisk tilfelle at E er fortsatt det mest populære, og B og C er den minst populære, minst av disse 5 bokstavene i alfabetet. Så hvordan kan vi gå om å komme opp med en koding, en binær koding, et mønster av 0'er og 1'ere for hver av disse brevene på en slik måte at E er en kort mønster og kanskje B og C er litt lengre mønstre, igjen, ideen er at vi ønsker å bruke færre bits mesteparten av tiden og flere biter bare en gang på en stund. Ifølge Huffman koding, kan du opprette en skog av trær. Det er liksom en historie linje her som involverer trær og også prosessen med å bygge dem opp. La oss begynne. Jeg foreslår at du starter med denne skogen, så å si, av 5 trær, som hver er en ganske dum treet. Treet er sammensatt av kun en enkelt node, representert her ved en sirkel. Slik at hver av disse tingene kan være en C struct og innsiden av C struct kan være en flottør som representerer frekvens teller og så kanskje en røye som representerer bokstaven. Så tenk på disse nodene som bare noen gamle C struct, men for nå, høyere nivå. Dette er en skog av 5 trær, hver av som bare har én node. Hva Huffman foreslått er at vi begynner å kombinere disse trærne som har de minste frekvens teller inn litt større trær ved å koble dem med en ny rotnoden. Slik blant bokstavene her, merker at for enkelhets har jeg sortert dem fra venstre mot høyre, selv om det er strengt tatt ikke nødvendig, og merker at de minste noder er for tiden 10% og 10%. Så Huffman foreslått at vi flette disse to minste noder i et nytt tre ved å innføre en ny forelder node og deretter gi den forelderen en venstre barn og høyre barn hvor B er vilkårlig venstre og C er vilkårlig høyre. Og så Huffman videre foreslått at la oss nå bare tenke på den venstre barnet i ett av disse trær alltid som blir representert ved 0 og rett barnet alltid som blir representert ved tallet 1. Det spiller ingen rolle om du snur dem så lenge du er konsekvent. Så nå har vi fire trær i denne skogen. Og jeg sier fire fordi nå treet til venstre - og det er ikke så mye et tre i den forstand at det vokser på denne måten, det er mer som en familie tre der nå 0,2 er liksom den overordnede av de to barna - merke til at i det overordnede har vi trukket 0,2. Vi har lagt til frekvenstellinger av de to barna og gitt den nye noden den totale summen. Så nå er vi bare gjenta denne prosessen. Finn de to minste noder og deretter bli med dem inn i et nytt tre og deretter gjenta prosessen videre. Akkurat nå har vi noen kandidater, 20%, 15%, og en annen 20%. I dette tilfellet har vi å bryte båndet. Vi kan gjøre det vilkårlig. Vi bør bare gjøre det konsekvent. I dette tilfellet vil jeg vilkårlig gå med den på venstre, og jeg nå slå sammen de 20% og 15% for å gi meg en ny forelder kalt 35%, hvis venstre barnet er 0, som rett barnet er 1, og nå har vi bare tre trær i skogen. Du kan kanskje se hvor dette går. Hvis vi gjentar dette et par ganger, vi kommer til å ha bare ett større tre, alle som kanter er merket med 0'er og 1'ere. La oss gjøre det igjen. 35% er det treet rot. 20% og 45%, så vi kommer til å flette 35% og 20%. Nå har vi dette treet her. Vi legger dem sammen, har vi 55%. Nå er det bare to trær i skogen. Vi gjør dette en siste gang, og forhåpentligvis matematisk alle frekvenser legge opp fordi de skal siden vi beregnet dem fra get-go å legge opp til 100%. Og nå har vi ett tre. Så dette er en Huffman koding treet. Den slags tok en stund å komme dit verbalt, men realiteten er en for loop eller med en rekursiv funksjon, kan du bygge denne tingen opp ganske fort. Så nå har vi en ny node, og alle disse indre nodene er malloc'd, antagelig, underveis. Så nå på toppen av dette treet vi har 100%, men nå legger vi merke har en bane fra denne nye tipp-tipp-tipp oldefar til alle de tipp-oldebarn helt på bunnen, til alle bladene. Hva vi skal gjøre nå er å foreslå at for å representere bokstaven E, Vi vil bare bruke tallet 1. Hvorfor? Fordi hvis vi traversere dette treet fra den endelige roten ned til blad kjent som E, vi følger bare én kant, høyre kant, og som er merket selvfølgelig øverst til høyre en. Så konsekvensen her for Huffman var at E koding i binær skal bare være en. Og det er ganske forbanna effektiv. Kan egentlig ikke få noe mindre enn det. Derimot, er til å være representert, hvis du følger logikken, av hva mønster av biter i stedet? 01. Så for å komme til A, starter vi ved roten, og vi går til venstre og deretter går vi rett, som betyr at vi fulgt en 0 og deretter en 1. Så vi skal representere bokstaven A med mønsteret 0 og 1. Og nå ser vi allerede har en eiendom umiddelbar decodability at vi ikke har i morse. Selv om begge disse mønstrene er ganske kort - E er en bit, er en 2 biter - merke til at de ikke kan forveksles ene eller den andre, fordi hvis du ser en en det må være en E, hvis du ser en 0 deretter en 1 er det åpenbart må være en A. Tilsvarende, hva er D? 001. Hva er C? 0001. Og hva er B? 0000. Og igjen, fordi alle bokstavene vi bryr oss om er på bladene og ingen av dem er slags mellommenn i banen fra rot til blad, det er ingen fare for conflating 2 bokstaver 'forskjellige kodinger fordi alle disse bit mønster er deterministisk. 0000 vil alltid være B. Det er ingen node et sted i mellom at du kan forvirre en bokstav for den andre. Så hva er konsekvensen her? Den mest populære brev - i dette tilfellet E - har fått den korteste koding, A har fått den nest korteste koding, og B og C, som vi allerede visste fra get-go var slags den minst populære ved 10% frekvens hver, har de fått lengst koding. Og så hva dette betyr nå er at hvis du ønsker å sende en melding som er komprimert over Internett eller i en e-post eller lignende, heller enn å bruke standard ASCII, kan du sende en Huffman kodet melding der hvis du ønsker å sende brevet E, sender du bare en enkelt bit. Hvis du ønsker å sende en A, sende deg to biter, 01, i stedet for å sende 8 bits etterfulgt av en annen 8 bits etterfulgt av en annen 8 biter og så videre. Men det er en fikser her. Det er ikke tilstrekkelig å bare bygge dette treet og deretter begynne å sende fra Alice til Bob kortere bit mønster, streng fra ASCII, fordi Alice har også å informere Bob av hva hvis Bob kommer til å være i stand til å lese hennes komprimert budskap? [Uhørlig student respons] >> Hva er det? [Uhørlig student respons] >> av hva treet er. Eller enda mer spesifikt, hva disse kodinger er, spesielt siden i løpet av denne historien gjorde vi en vurderingssak på ett punkt. Husk at vi måtte plukke vilkårlig mellom de to ulike 20% noder? Så det er ikke slik at Bob, mottaker, kan bare rekonstruere tre på sin egen fordi kanskje han vil skape treet aldri så litt annerledes fra Alice. Videre betyr Bob ikke engang vet hva den opprinnelige meldingen er fordi det eneste Alice sender ham, selvfølgelig, er den komprimerte meldingen. Så fangsten med kompresjon som dette er at, ja, kan Alice spare en hel masse biter ved å sende en til E og 01 for A og så videre, men hun har også å informere Bob hva kartleggingen er mellom bokstaver og biter fordi de ikke kan tydelig stole på bare ASCII lenger hvis vi ikke bruker ASCII. Slik at hun kan enten sende ham treet eller annen måte - skrive det ned, lagre det som binære data eller noe sånt - eller bare sende ham en liten jukselapp, en Excel-fil, som viser tilordningene. Så effekten av komprimering forutsetter egentlig at meldingene som du sender er ganske stor, minst mellomstore, fordi hvis du sender en super kort melding, Hvis du bare ønsker å sende meldingen BAD, som skjer for å være et ord vi kan stave her, B-A-D, er du sannsynligvis kommer til å bruke færre biter, men fangsten er hvis du må også informere Bob hva treet er eller hva disse kodinger er, du kommer til å sannsynligvis oppveie alle de besparelser av å ha komprimerte ting til å begynne med. Så det kan faktisk være slik at hvis du prøver å komprimere selv med noe som zip eller filformater kan du bli kjent med - ganske små filer, selv tomme filer - noen ganger disse filene kan bli større og ikke mindre. Men realistisk, det skjer bare for små filstørrelser, så det ikke kommer til å gjøre en gigabyte fil være 2 gigabyte; vi egentlig snakker byte eller bare et par kilobyte. Noen programmer som zip er smart nok til å innse at "Du kommer til å tilbringe flere biter komprimere dette." "La meg ikke bry komprimere det for deg i det hele tatt." Så dette er bare én måte så å komprimere tekstformat. Vi kunne gjennomføre noe sånt i C. For eksempel, her er hvordan vi kan representere en node i dette treet hvor vi har en char for symbolet, en flytende verdi for frekvensen, og som vi har sett med våre andre datastrukturer, 2 pekere, 1 til venstre barnet, 1 til høyre, som begge kan være NULL, men hvis ikke, refererer det til en venstre barn og høyre barn. Så dette er da Huffman koding, og det er en måte at du kan gå om å komprimere informasjon, og det er absolutt en av de mest lett å implementere i sammenheng med, sier forrige ukes datastrukturer, men enda mer avanserte algoritmer eksisterer som kan gjøre enda mer sofistikerte mutasjoner av dine data. Eventuelle spørsmål deretter på trær, binære trær, eller komprimering av tekst? [Student] Er det noen tvetydighet, som om [hørbar] delt inn i 01, deretter 011 ville være tvetydige, ikke sant? [Uhørlig] >> Godt spørsmål. Tvetydighet. La meg oppsummere ved å henvise til dette bildet her. Fordi tegnene du komprimere, representasjoner av, per definisjon av denne algoritmen alltid forbli bladene, du aldri uhell bruke samme mønster av biter for prefikset av flere bokstaver. Så med andre ord, er du bekymret, det høres ut som, en tvetydighet som oppstår der 001 kan være starten på B eller begynnelsen av C eller noe sånt. Men det kan ikke være tilfelle fordi varsel om at alle bokstavene i alfabetet vi koding er på bladene. Tvetydigheten kan bare oppstå, som i tilfelle av morse, hvis du for eksempel var C sted langs stien fra roten til B. [Student] Høyre. Så i så fall, si A har 2 blader. >> Say A har - Si det igjen. [Student] Say A har 2 blader, F og G, og deretter G - >> OK. Men det kan ikke. En selv kunne ikke ha bladene F og G fordi disse bokstavene F og G selv ville være forlater sted til venstre for B eller høyre av E. Så per definisjon, må de være blader. Ellers er du helt riktig, har vi ikke løst problemet med at morse ansikter. Godt spørsmål. Andre spørsmål? All høyre. Denne oppfatningen av biter, viser det seg at vi har hatt makten hele tiden at vi ikke har faktisk brukt når det kom til å manipulere disse 0'er og 1'ere. Vi spurte om dette på en av de tidligste oppgavesett: nemlig, hvordan du går om å konvertere store til små bokstaver eller omvendt? Eller, mer konkret, spurte en av de første psets hvor mange biter trenger du faktisk nødt til å vende for å endre A til små bokstaver a eller vice versa? Her er en rask påminnelse om hva 65 og 97 ser ut i binær. Og selv om det spørsmålet har liksom bleknet i minnet, du kan se igjen her at hvor mange biter må venda å endre kapital A til små bokstaver a? Bare ett. Den eneste forskjellen på ett sted, den tredje biten fra venstre. Mens A har en 010, litt a har en 011. Så noe må vi bare være i stand til å snu det litt, og vi kan da utnytte eller små bokstaver. Vi har gjort dette i det siste ved å bruke nettopp dersom forholdene og sjekke om bokstaven er mellom kapital A og kapital Z, deretter utganger som A - a + 26 eller noe sånt. Du gjorde en aritmetisk endring bokstavene i alfabetet. Men hva om vi kunne bare snu det eneste bit? Hvordan kunne du gå om å ta en byte er verdt av biter, så 8 bits som 01000001 og 01100001? Hvis du hadde disse punktmønstre, hvordan kan vi gå om endring bare en av dem? Hva om vi innfører i gult her denne andre mønster av biter? Hvis jeg gjør hele gule streng 0s bortsett fra for en bit som jeg ønsker å endre og da jeg introdusere en ny operatør kjent som en bitvis operator - bitvis i den forstand at den opererer på individuelle biter, ikke på en hel byte eller fire byte alle samtidig. Denne vertikale linjen der i gult tyder på at hva om vi tar representasjon av kapital A og bitvis OR det med den gule sekvens av biter? Med andre ord, tenke tilbake til vår diskusjon av boolske uttrykk i Scratch og deretter i C. Gjør en boolsk eller betyr at for å være sant, enten det første har til å være sant eller andre ting er å være sant, eller de begge har til å være sant, og deretter den resulterende utgang er selve sant. I dette tilfellet her, hva vi får hvis vi tar 0 "eller" ed med 0? Falsk eller usant? Det er fortsatt falsk, så små en fortsatt som forventet. Hva om vi i stedet gjør 1 eller 0? Dette gjenstår nå 1, men merker hva som er i ferd med å skje her. Hvis vi starter med kapital A og vi fortsetter å "eller" de enkelte biter som vi gjør her, 0 eller den gule gir oss det her nede? Dette gir oss en. Faktisk antar vi visste ikke hva det store versjonen av liten en egentlig var. La oss gå gjøre dette. La meg flytte dette tilbake over her. La oss gjøre dette igjen. 0 eller 0 gir meg 0. 1 eller 0 gir meg en. 0 eller 1 gir meg 1. 0 eller 0 gir meg 0. Den neste er 0, den neste er 0, er den neste 0. 1 eller 0 gir meg en. Og så selv om vi ikke vet på forhånd hva små bokstaver en var, ganske enkelt ved å "eller" ing A med dette mønsteret av biter som vi har presentert her i gult, du kan små bokstaver en kapital A ved å bla det litt. Vi brukte dette uttrykket uker siden: bla litt. Hvordan kan du faktisk gjøre det programmatisk? Du bruker det som vanligvis kalles en maske, en sekvens av biter, at i dette tilfellet bare så skjer for å se ut som dette nummeret her, og du "eller" det sammen med denne nye C operatør, ikke | |, bruker du et enkelt | og du vil faktisk få dette svaret her fordi hvorfor? Dette er det 1s sted, 2s sted, 4S, 8S, 16S, 32s. Så det viser seg at hvis du tar en stor bokstav A og bitvis OR den med heltall 32, fordi heltall 32, når du ser på det som biter, ser slik ut, som betyr at du kan snu litt på at du faktisk ønsker. Og tilsvarende - og vi skal se på koden i løpet av et øyeblikk - anta vi ønsker å gå den andre retningen. Hvordan du går fra små en til kapital A? Hvilken bit må endres? Det er den samme. Vi ønsker å endre det tredje bit fra en 1 til 0. Og hvordan kan vi gå om du gjør dette? Hvordan slår vi av litt? Med hva mønster av biter kan vi slå av litt? Hva om vi liksom snu masken? Mens før, gjorde vi hele gule masken 0s med unntak av én bit ønsket vi å slå på, hva om denne gangen, gjør vi hele masken 1s bortsett litt at vi ønsker å slå av og deretter bruke det operatør? Hva om vi "og" ting? La oss ta en titt. Hvis vi nå snu til dette, antar at jeg igjen lage en maske som er alt 1s med unntak av én bit som jeg ønsker å slå av og deretter heller enn "eller" de hvite tallene opp toppen med de gule tall her nede, hva om jeg i stedet "og" dem sammen? Det kalles en bitvis og. Logisk, er det det samme som en boolsk og. Dette gir meg 0 og 1 er 0. Så falsk og ekte er falsk. Sant og ekte er sant. Og her er det magiske: sant og usant er nå falsk, så vi har slått av at bit. Og nå resten av historien er noe enkel. Fordi resten av masken er 1s, spiller det ingen rolle hva tallene er i hvitt. Når du "og" noe med sann, er du ikke kommer til å endre verdien. Hvis det er sant, vil det forbli sant. Hvis det var falsk, vil den forbli falsk. Men den magiske skjer når du tar noe som var sant og du deretter "og" det med falsk. Dette har effekten av å slå av at litt. Så en liten kryptisk der. La oss faktisk ser på noen kode, som kan faktisk se enda mer kryptisk, men la oss ta en titt her på tolower. Hvis jeg ser på tolower, kommer fra hovedstaden A til små bokstaver a, la oss se hvordan vi kan implementere dette programmet. Her er viktigste, og det er ikke å ta noen kommandolinjeargumenter. Jeg erklærer en karakter c for brevet som brukeren kommer til å skrive i. Jeg deretter bruke en kjent do mens loop å bare sørge for at brukeren definitivt gir meg en kapital A eller B eller C. .. Z, slik at de gir meg noe mellom A og Z. Og nå hva gjør jeg her? Jeg er "eller" ing dette med 0x20, men det er faktisk det samme som - og vi vil komme tilbake til dette i et øyeblikk - 32. Så igjen, er 32 dette mønsteret biter her. Hvorfor vet vi dette? Bare tenk tilbake til uke 0. Dette er det 1s sted, 2s sted, 4s, 8S, 16S, 32s sted. Så dette gule tall skjer for å være 32. Da kan jeg ta med et brev som røye her, bitvis "eller" det med bokstavelig talt nummer 32, og hva får jeg tilbake? Små bokstaver versjon av røye. For et øyeblikk siden, men uttrykte jeg dette i en annen base notasjon. Hva gjorde dette representerer? >> [Student] Heksadesimal. [Malan] Dette skjer for å representere heksadesimal. Vi har ikke snakket om heksadesimal alle så mye, men det er faktisk praktisk i tilfeller som dette. Selv om det ser mer komplisert og selv om det ser ut som 20 og ikke 32, det viser seg at heksadesimal er faktisk super praktisk notasjon fordi i heksadesimal hvert siffer etter 0x - og dette betyr ingenting; dette er bare menneskelig konvensjonen som sier her kommer et heksadesimalt tall - hver av disse sifre er de to og deretter 0, kan selv være representert med nøyaktig 4 biter. Så hvis vi gjør dette, la meg åpne opp en tekst editor her - merkelig autofullfør - hvis vi gjør en liten tekst editor her, betyr at antall 0x20 her er 4 biter, her er en annen 4 biter. La oss gjøre den høyre 4 biter først. 0 når representert med 4 biter er hva? Super lett. Bare alle 0s. Så 4 biter som 0s. Hvordan representerer du 2? Det har gått en stund siden vi gjorde dette, men det er 0100. Så dette er 1s sted, er dette 2s sted, og da er det ingen rolle hva de andre stedene er. Med andre ord, i heksadesimal kan du si 0x20, men hvis du da tenker på hva som er de 2 og hvordan er de representert i binær, hva er 0 og hvordan er de representert i binær, svarene på disse spørsmålene er dette og dette, henholdsvis. Så 0x20 skjer for å representere dette mønsteret av 8 bits, som er nettopp masken som vi ønsket. Så dette er for øyeblikket bare en intellektuell øvelse, men realiteten er i koden er det vanligvis mer vanlig å skrive konstanter som dette i heksadesimalt fordi da programmerer kan relativt enkelt, selv om det krever litt papir og blyant, finne ut hva som mønster av biter er fordi du kan ikke bare uttrykke 0'er og 1'ere typisk i koden. Du kan ikke gå 00010 og så videre. Du må velge desimal eller heksadesimal eller oktal eller andre merknader. De fleste mennesker har en tendens til å plukke heksadesimale bare slik at hvert siffer representerer fire biter og du kan gjøre dette raskt matematikk. Og jeg vil vinke min hånd på toupper, som er nesten det samme, det ser nesten identiske. Toupper skjer bruker ikke eller operatør, men heller denne fyren og df. Hva representerer df? df? Anyone? >> [Student] 255. 255? Ikke 255. Det ville være ff. Vi vil forlate dette som en liten øvelse. Men hvis du går fra 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, og deretter hva som kommer etter 9? Vi er slags ut av desimaler, men i heksadesimalt hva som kommer etter 9? [Student] en. >> Så a, b, c, d. Du kan finne ut fra det hva mønster av biter d faktisk representerer. Og hvis vi gjør regnestykket, vil vi se at masken du ender opp med å få tilbake er identisk med denne. Dette er f, alt 1s, og dette er d. Så df representerer den masken. All høyre. Og til slutt, for ikke å gjøre ting høres super, super teknisk, men antar vi ønsket å skrive et program som gjør dette. La meg gå videre og gjøre binære, som er et program i en fil kalt binary.c. Og nå la meg kjøre binære og gi meg et ikke-negativt heltall. La oss starte enkelt og skriv inn 0. Dette er nå et program som skriver ut et heltall i den binære representasjon. Så hvis jeg spiller dette spillet igjen og skrive bare 1, skal jeg få en 32-bit representasjon av en. Hvis jeg gjør dette igjen med 2, bør jeg få det. Hvis jeg gjør 7, skal jeg få noen 1s på slutten og så videre. Det viser seg at jeg nevner dette fordi med bitvis operasjoner du faktisk kan gjøre en annen ting også. Du kan opprette disse maskene dynamisk. Ta en titt på denne siste eksempel involverer bitvis operasjoner. Her er første del av koden, spør brukeren om et tall, og det insisterer på at du gir meg et ikke-negativt heltall. Så det er liksom gamle skole ting. Men her er noe som er ganske interessant. Hvordan går jeg om å skrive ut et nummer i binære? Jeg først iterate fra hva til hva? Hva er størrelsen på en int typisk, i hvert fall i oppvaskmaskinen? >> [Student] 4. Det er fire. Så 4 * 8 er 32 - 1 er 31. Så hvis jeg begynner å telle fra 31, representerer det, det viser seg, bare konseptuelt, den 31. bit eller høyeste orden bit, som er denne fyren over her, mens dette kommer til å være litt 0. Så dette er litt 01 ... bit 31. Så hva er denne koden gjør? Merke dette for loop, selv om det ser kryptisk, er bare gjentar fra 31 ned til 0. Det var det. Så den interessante delen nå må være i disse 5 linjer her. Legg merke til at i denne linjen jeg erklære en variabel kalt maske å være i samsvar med vår historie av disse gule tall. Og hva er dette med? Dette er en annen bitvis operatør vi ikke har sett før, mest sannsynlig. Det er den venstre skifte operatør. Denne operatøren gjør dette. Her er nummer 1, og hvis du gjør jeg forlot skift, venstre shift, hva tror du som har effekten av å gjøre til den enkelte 1? Bokstavelig skiftende det over. Så hvis nummer 1 er det du har på venstre og du begynner ved å initialisere jeg til 31, hva kommer det til å gjøre? Det kommer til å ta dette nummer 1 og skift den 31 steder over her. Og fordi det er det tydeligvis ingen andre siffer bak det, de vil som standard bli erstattet med 0s. Så du vil starte med tallet 1, som selvfølgelig ser slik ut - og la meg trekke den over her i sentrum. Og deretter som du flytter ting til venstre, går denne fyren egentlig denne måten. Men så snart du gjør det, blir en 0 fylt i. Hvis du flytter den en gang til, går det på denne måten, og en annen 0 blir fylt i. Du skifte den igjen og deretter en annen 0 blir fylt i. Så hvis du gjør dette av en << I 31 steder, ender du opp med å få en maske som er 32 tegn, lengst til venstre en av disse er en 1, alle, hvorav resten er en 0. Og det viser seg, som en side, skiftende et nummer til venstre som dette også tilfeldig, og noen ganger praktisk, har effekten av å gjøre det til det nummeret? >> [Student] Dobling det. Dobling det fordi hver av kolonnene - det 1s sted, 2s sted, 4s sted, 8s sted, 16s sted - de er alle dobling som du går til venstre. Eller rettere sagt, når du flytter 1s du kommer til å ende opp med doble verdien av nummeret. Du kan ende opp med å gjøre interessante transformasjoner av sifre av skiftende alt over på denne måten ved potenser av 2. Så hvordan fungerer dette? Dette gir da meg en maske som er alt 0s bortsett fra en en i nøyaktig sted jeg ønsker det, og deretter dette uttrykket, som er stjålet fra toupper.c, er bare å si ta nummeret n at brukeren har skrevet inn, "Og" det med at masken, og hva skal du bli? Du kommer til å få en 1 hvis det er en 1 i den maskerte beliggenhet, eller du kommer til å få en 0 hvis det ikke. Og så alt dette programmet gjør er effektivt det har en loop, og det skaper en maske med en 1 over her, så en 1 over her, så en 1 over her, og den bruker denne bitvis AND trikset å si er det en 1 bit i brukerens input her? Er det en 1 bit i brukerens input her? Og hvis så, bokstavelig talt ut en, ellers ut 0. Vi gjør dette med ints bare fordi det er derfor vi gjør 32 bits i stedet for 8, men hva vi har introdusert så er dette bitvis AND, dette bitvis OR, og denne venstre skifte operatør, som er ikke ofte veldig nyttig, men det viser seg at de kan være. Faktisk, hvis du skulle representere noe som en rekke boolske bare for å representere sant eller usant, antar du ønsket å holde styr på hvorvidt et rom fullt av 300 studenter er til stede, du kunne erklære en rekke størrelse 300 av typen bool slik at du får 300 bools, og du kan sette hver til true hvis noen er her og falsk ellers. Hvorfor er det representasjon i at data struktur ineffektiv? Hva er dårlig om utformingen av den datastrukturen, en rekke 300 bools? Hva er en bool, faktisk, under panseret? Også dette er noe som kanskje ikke er kjent. Det viser seg at det ikke er noen bool. Husk vi liksom skapt at med cs50.h fil, som selv har standard bool. C er slags dum, men når det kommer til bool. Den bruker 8 bits for å representere hver bool, som er helt bortkastet fordi åpenbart, hvor mange biter du trenger å representere en bool? Bare 1. Så det viser seg at hvis du har nå muligheten med bitvis operatører å manipulere individuelle biter selv i en char, selv i en enkelt byte, det viser seg at du kan redusere minnet som kreves for å representere noe dumt sånn frammøte stylet datastruktur med en faktor på 8. I stedet for å bruke åtte biter til å representere sant eller usant, kan du bokstavelig talt bruke en ved hjelp av en enkelt byte for hver åttende studenter i klassen og veksling 0-1 individuelle biter ved hjelp av disse typer lavt nivå triks. Som virkelig satt en stopper for energi. Er det noen spørsmål om bitvis operasjoner? Ja. >> [Student] Er det en eksklusiv eller operatør? Ja. Det er en eksklusiv eller operatør som ser slik ut, ^, gulrot symbol, som betyr at bare den første eller den andre ting kan være en 1 for utgangen til være en 1. Det er også en ikke ~, som vil tillate deg å invertere en 0 til en 1 eller vice versa, så vel. Og det er også en høyre shift operatør, >>, som er det motsatte av det vi så. All høyre. La oss ta ting nå til et høyere nivå. Vi begynte med å snakke om tekst og deretter komprimere den og representerer teksten med færre antall biter; Vi snakket litt om hvordan vi kan nå begynne å manipulere ting på en bitvis nivå. La oss nå zoome opp 10.000 fot til representasjon av mer komplekse ting som grafikk. Her har vi et flagg i Tyskland, her har vi en av Frankrike. Disse kan være representert i filformater du kanskje kjenner - GIF, for eksempel. Hvis du noensinne har sett et bilde på nettet som slutter på. Gif, Dette er en Graphics Interchange Format. Disse to flagg her slags egner seg til komprimering for hva kanskje åpenbar grunn? >> [Uhørlig student respons] Det er mye repetisjon, ikke sant? For å sende Tysklands flagg, tenk på dette som et bilde på skjermen tilbake i Scratch dager. Du husker kanskje at det er individuelle piksler eller punkter som komponerer et bilde. Det er en hel rad av svarte prikker og en annen hele rad av svarte prikker. Det er en haug med rader av sorte prikker som vi kunne se om vi virkelig har zoomet inn, mye som når vi zoomet inn på Rob ansikt i Photoshop. Så snart vi kom dypere og dypere og dypere inn i bildet, du begynte å se pikselering, alle rutene som komponerte øyet i dette tilfellet. Samme avtale her. Hvis vi zoomet inn ganske mye, ville du se individuelle prikker. Vel, dette er en slags avfall av biter. Hvis en tredjedel av flagget er svart og en tredjedel av flagget er gult og så videre, hvorfor kan ikke vi noe komprimere dette flagget? Og selv det franske flagget kan bli komprimert selv om mønsteret er litt annerledes. Det viser seg at GIF filformatet er en tapsfri komprimering format, som betyr at du kan ta et bilde som det tyske flagget her, du kan kaste bort mye av sine biter uten å ofre kvaliteten. Dette er i motsetning til noe som JPEG, som de fleste av oss er nok mer kjent. Facebook bilder og Flickr-bilder og lignende er nesten alltid lagres som JPEG når de er lastet opp, men JPEG er et lossy - lossy - format der du kaster bort biter men du også kaste bort kvalitet. Og så hvis du komprimere bilder med Photoshop eller laste dem opp til Facebook eller ta dem på en virkelig crappy telefon, du vet at bildet begynner å bli veldig flekkete og pixelated, og det er fordi det blir komprimert av datamaskinen eller telefonen ved bokstavelig talt å kaste informasjon unna. Men GIF er fantastisk i at det kan bruke færre bits enn det kanskje som standard uten å miste noe informasjon. Og det i hovedsak gjør så som følger. Snarere enn butikk i en fil som en BMP ville en RGB trippel for svart, svart, svart, svart, svart, svart, svart, svart, svart, svart, svart, svart og så videre, snarere er det GIF-format kommer til å si, "Black" og da, "Gjenta dette 100 ganger," eller noe sånt. "Black, gjenta dette 100 ganger, svart, gjenta dette 100 ganger ..." "Gul, gjenta dette 100 ganger." Og så det husker, i hovedsak, den lengst til venstre pixel og koder deretter noe oppfatningen av å gjenta at pixel igjen og igjen. Så GIF kan deretter komprimere seg uten å miste noe informasjon. Men hvis du skulle gjette, hvis det er algoritmen som GIF-filer bruk, hvilke av disse flaggene, selv om de ser identiske i størrelse, kommer til å bli mindre når de lagres på disken som en GIF? >> [Student] Tyskland. Tyskland kommer til å bli mindre? Hvorfor? [Student] Fordi du gjentar den mange, mange ganger horisontalt og deretter gjenta en annen gang. >> Nettopp. Fordi folk som oppfant GIF bare slags vilkårlig besluttet at repetisjon skal utnyttes horisontalt og ikke sidelengs. Det er mye mer repetisjon sideveis her i det tyske flagget enn i det franske flagget. Så hvis vi faktisk åpne opp en mappe på harddisken min som har disse GIFs, du kan faktisk se at det tyske flagget her er to kilobyte og den franske er 4 kilobyte. Det skjer for å være en tilfeldighet at man er dobbelt den andre, men det er faktisk slik at det franske flagget er mye større. Selv om vi snakker her om grafikk, kan de samme ideene gjelder ikke ting som flagg, men bilder som er litt mer komplisert. Hvis du tar et bilde av et eple, sikkert det er mye dobbeltarbeid der, slik at vi kunne liksom huske at standard bakgrunnen er blå , og ikke som den høyre bilde antyder, må huske fargen på hver eneste piksel i dette bildet. Så vi kan kaste biter unna det uten å miste informasjon. Eplet ser fortsatt akkurat det samme. I dette eksempelet her, kan du se hva som skjer i en film. Disse representerer old-school filmruller der i toppen bildet der du har en RV kjøring forbi et hus og et tre. Og som det van kjører forbi fra venstre til høyre, hva åpenbart ikke endring? Huset er ikke noe sted, og treet er ikke noe sted. Det eneste som beveger seg er van i dette tilfellet. Så som bakgrunn Uendret antyder, hva du kan gjøre i filmer er tilsvarende bare kaste bort informasjon som ikke endres i mellom rammer. Dette er vanligvis kjent som interframe komprimering der hvis denne rammen ser nesten identisk til denne, la oss ikke bry lagre på disk noen av identisk informasjon på disse mellomliggende frames, la oss bare bruke nøkkelbilder gang på en stund som faktisk lagrer denne informasjonen redundant bare som en liten mental helse sjekk. Som kontrast, er en annen tilnærming til komprimere videoen i denne andre og lavere eksempel her, der heller enn butikk 30 bilder, hva med å bare lagre 15 bilder per sekund i stedet? Snarere enn filmen slags flyter vakkert, perfekt, det kan se ut som det er hakkete litt, litt old school, men nettoeffekten vil være å bruke langt færre bits enn ellers ville være nødvendig. Så hvor kommer dette så la oss? Det var litt av en side på hvor ellers kan du gå med komprimering. For mer om dette, ta en klasse som CS175 her. Her er et annet eksempel innen video. Hvis bee er den eneste bevegelse, du virkelig kan kaste bort informasjon i disse midterste rammer fordi blomst og himmelen og blader ikke er i endring. Men la oss nå vurdere en siste ting. I de neste 5 minuttene la vi C bak evig i forelesningen? Ja. Ikke i psets, skjønt. Siste historien om C og så får vi til svært sexy ting involverer HTML og web-og woo-hoo. All høyre. Here we go. Det er motivasjon. Det viser seg hele tiden når vi har vært å skrive programmene vi kjører Clang. Og Clang, vi har sagt siden den første uken ganske mye, tar kildekoden og konverterer den til objektkode. Det tar C og konverterer den til 0'er og 1'ere. Jeg har slags ligget til deg for noen uker fordi det er ikke fullt så enkelt som det. Det er mye mer som skjer under panseret når du kjører et program som Clang. Faktisk kan prosessen med å sette sammen et program virkelig bli oppsummert, som du kanskje husker fra Rob video på kompilatorer, inn i disse fire trinnene: pre-prosessering, kompilering selv, montering, og linking. Men vi i klassen og de fleste mennesker i verden typisk oppsummere alle disse trinnene som bare "kompilering". Men hvis vi starter med kildekoden som dette, husker dette er kanskje den enkleste C program vi har skrevet så langt, husker at når kompilert det ender opp som ser slik ut. Men det er faktisk et mellomliggende trinn, og disse trinnene er som følger. Først er det denne tingen på toppen av dette, og de fleste av våre programmer, # Include Hva omfatter # gjøre for oss? Det ganske mye kopierer og limer innholdet i stdio.h inn filen min, slik at hvorfor? Hvorfor bryr jeg meg om innholdet i stdio.h? Hva er der av interesse? Printf erklæring, sin prototype, slik at kompilatoren så vet du hva jeg mener når jeg nevner denne funksjonen printf. Så trinn 1 i kompilering er pre-prosessering, der et program som Clang eller noen helper program som Clang kommer med leser koden topp til bunn, venstre til høyre, og hver gang den ser en # symbol etterfulgt av et søkeord som omfatter, den utfører den operasjonen, kopiere og lime inn i dette tilfellet stdio.h inn i filen. Det er trinn 1. Da har du en mye større C-fil på grunn av den enorme kopiere, lime inn jobb som bare skjedde. Trinn 2 nå er kompilering. Men det viser seg kompilere tar kildekoden som ser slik ut og gjør den til noe som ser ut som dette, som for de som er kjent heter? >> [Student] Assembly. >> Assembly språk. Dette er faktisk noe hvis du tar CS61 du vil dykke inn i mer detalj. Dette er omtrent så nær som du kan komme til å skrive 0'er og 1'ere selv men skriver ting på en slik måte som fortsatt gjør minst en liten bit av fornuftig. Dette er maskininstruksjonene, og hvis vi blar ned til den viktigste funksjonen her, merke til at det er dette push instruksjon, flytte undervisning, trekke instruksjon, call instruksjon, og så videre. Når du hører at datamaskinen har Intel inside, du har en Intel CPU i din Mac eller PC, hva betyr det? En CPU kommer innebygd med selskaper som Intel forstå visse instruksjoner. De har ingen anelse om hvilke funksjoner som swap er eller hovedsak er per se, men de vet hva svært lavt nivå instruksjoner som legge til, trekke fra, presse, flytte, ringe, og så videre er. Så når du kompilere C-kode i forsamlingen språk, din svært brukervennlig utseende kode er konvertert til noe som ser ut som dette, som beveger bokstavelig byte eller 4 byte rundt i slike små enheter i og ut av CPU. Men til slutt, når Clang er klar til å ta denne representasjonen av programmet inn 0'er og 1'ere, deretter trinnet kalles montering skjer, og dette igjen alle skjer i løpet av et øyeblikk når du kjører Clang. Vi starter her, utganger det en fil som dette, og da er det konverterer den til disse 0'er og 1'ere. Og hvis du ønsker å gå tilbake på et tidspunkt og faktisk se dette i praksis, hvis jeg går inn hello1.c--dette er en av de aller første programmene vi har sett på - normalt ville vi kompilere dette med Clang hello1.c og dette ville gi oss a.out. Hvis derimot du i stedet gi den-S flagget, hva du får er hello1.s og du vil faktisk se assembly. Jeg gjør dette for en svært kort program, men hvis du går tilbake til Scramble eller Gjenopprett eller hvilket som helst program du har skrevet og bare ut av nysgjerrighet ønsker å se hva det egentlig ser ut, hva som faktisk blir matet inn i CPU, kan du bruke den-S flagg med Clang. Men så til slutt, det er fortsatt en fikser. Her er de 0'er og 1'ere som representerer min gjennomføring av hallo, verden. Men jeg brukt en annens funksjon i programmet mitt. Så selv om prosessen har vært jeg ta hallo.c, det blir samlet i forsamlingen koden, og deretter den blir satt sammen til 0'er og 1'ere, den eneste 0'er og 1'ere som er outputted på dette tidspunkt er de som kommer fra min kode. Men personen som skrev printf, samlet de seg koden for 20 år siden og det er nå installert sted på apparatet, så vi noe å fusjonere sine 0'er og 1'ere med min 0'er og 1'ere, og det bringer oss til den fjerde og siste trinnet kompilering, kjent som linking. Så på venstre side har vi nøyaktig samme bilde som før: hallo.c blir assemblykode blir 0'er og 1'ere. Men husker at jeg brukte standard I / O-bibliotek i koden min, og det betyr et sted på datamaskinen er det en fil som heter stdio.c eller minst kompilert versjon derav fordi noen noen år siden kompilert stdio.c inn assembly-kode og deretter en hel haug med 0'er og 1'ere. Dette er det som kalles en statisk eller dynamisk bibliotek. Det er noen fil sitter et sted i apparatet. Men til slutt, må jeg ta min 0'er og 1'ere og vedkommende har 0'er og 1'ere og noe knytte dem sammen, bokstavelig talt kombinere de 0'er og 1'ere i en enkelt fil som heter a.out eller hello1 eller hva jeg ringte min program slik at sluttresultatet har all 1s og 0s som bør komponere mitt program. Så alt denne gangen dette semesteret når du har brukt Clang og enda mer nylig kjørte gjøre for å kjøre Clang, alle disse trinnene har skjedd slags umiddelbart, men svært bevisst. Og så hvis du fortsetter på i informatikk, nemlig CS61, Dette er laget som du vil fortsette å skrelle tilbake av det snakker om effektivitet, sikkerhetsimplikasjonene, og lignende av disse lavere nivå detaljene. Men med det, er vi i ferd med å forlate C bak. La oss gå videre og ta vår 5-minutters pause nå, og når vi kommer tilbake: Internett. All høyre. Vi er tilbake. Nå begynner vi ser ikke bare på HTML fordi, som du vil se, HTML selv er faktisk ganske enkelt men virkelig på web-programmering mer generelt, nettverk mer generelt, og hvordan alle disse teknologiene kommer sammen å tillate oss å lage mye mer avanserte programmer oppå Internett enn hittil har vi vært i stand til å i disse sorte og hvite vinduer. Faktisk, på dette punktet i semesteret, selv om vi vil bruke relativt mindre tid på PHP, HTML, CSS, JavaScript, SQL og mer, de fleste studenter ender opp med å gjøre endelige prosjekter som er web-basert fordi som du ser, den bakgrunnen du har nå i C er veldig mye som gjelder for disse høyere nivå språk. Og når du begynner å tenke på det endelige prosjektet, som, mye som Problem Set 0, der du ble oppfordret å gjøre det meste noe av interesse for deg i Scratch, den endelige prosjektet er din mulighet til å ta ny kunnskap og kunnskapsrike med C eller PHP eller JavaScript eller lignende for en snurr og lage din helt egen stykke programvare for verden å se. Og til frøet du med ideer, vet at du kan hodet her, projects.cs50.net. Hvert år, oppfordre vi ideer fra lærere og ansatte og student grupper på campus bare å sende inn sine ideer for interessante ting som kan løses ved hjelp av datamaskiner, bruker nettsteder, ved hjelp av programvare. Så hvis du sliter med å komme opp med en idé av dine egne, for all del bla gjennom ideer der fra i år og siste. Det er helt greit å takle et prosjekt som har blitt håndtert før. Vi har sett mange apps for å se status for vaskeri på campus, mange apps for å navigere i matsalen menyen, mange apps for å navigere i kurskatalogen og lignende. Og ja, i en fremtidig foredrag og i fremtidige seminarer, Vi vil introdusere deg til noen offentlig tilgjengelig APIer, både kommersielt tilgjengelig så vel som her er tilgjengelig fra CS50 på campus, slik at du har tilgang til data og kan deretter gjøre interessante ting med det. Så mer om endelige prosjekter i noen dager når vi slipper spesifikasjonen, men for nå, vet at du kan arbeide alene eller med en eller to venner på de fleste ethvert prosjekt av interesse for deg. Internett. Går du videre og trekke ut den bærbare datamaskinen, går du til facebook.com for første gang, ikke at du har logget inn nylig, og trykk Enter. Hva skjer egentlig? Når du trykker på Enter på datamaskinen, en hel haug med trinn starter slags magisk skjer. Så du her til venstre, web server som Facebook er her på høyre side, og noe du bruker dette språket kalles HTTP, Hypertext Transfer Protocol. HTTP er ikke et programmeringsspråk. Det er mer av en protokoll. Det er et sett av konvensjoner som nettlesere og webservere bruker når intercommunicating. Og hva dette betyr er som følger. Mye som i den virkelige verden, har vi disse konvensjonene der hvis du møter noen mennesker for første gang, hvis du ikke tankene humoring meg her, Jeg kan komme opp til deg og sier: "Hei, mitt navn er David." >> Hei, David. Mitt navn er Sammy. "Hei, David. Mitt navn er Sammy." Så nå har vi bare engasjert i denne typen dum menneskelig protokoll hvor jeg har startet protokollen, har Sammy svarte, vi har håndhilst, og transaksjonen er fullført. HTTP er veldig lik i ånden. Når nettleseren forespørsler www.facebook.com, hva din nettleser er virkelig gjør er å utvide sin hånd, så å si, til serveren, og det er å sende den en melding. Og at meldingen er vanligvis noe som får - hva vil du bli? - få meg på hjemmesiden, som er typisk merket med en enkel slash på slutten av en nettadresse. Og bare så du vet hvilket språk jeg snakker, jeg leseren kommer til å fortelle deg at jeg snakker HTTP versjon 1.1, Og også for godt mål, skal jeg fortelle deg at verten som jeg vil at hjemmesiden er facebook.com. Vanligvis, en nettleser, ukjent for deg, menneske, sender denne meldingen på Internett når du bare skrive www.facebook.com, Enter, inn i nettleseren din. Og hva svarer Facebook med? Den reagerer med noen lignende utseende kryptiske detaljer, men også mye mer. La meg gå videre til Facebook hjemmeside her. Dette er skjermen som de fleste av oss sannsynligvis aldri se om du fremdeles er logget inn hele tiden, men dette er faktisk deres hjemmeside. Hvis vi gjør dette i Chrome merke til at du kan trekke opp disse små hurtigmenyer. Bruker Chrome, enten på Mac OS, Windows, Linux, eller lignende, Hvis du har kontroll klikk eller venstre klikk, kan du vanligvis trekke opp en meny som ser slik ut, hvor noen alternativer venter, er en av dem Vis sidekilde. Du kan også vanligvis få til disse tingene ved å gå til Vis-menyen og poking rundt. For eksempel, her under visning, er Developer det samme. Jeg kommer til å gå videre og se på Vis sidekilde. Hva du vil se er HTML som Mark har skrevet for å representere facebook.com. Det er et komplett rot her, men vi får se at dette gjør litt mer fornuftig før lenge. Men det er noen mønstre her. La meg bla ned til ting som dette. Dette er vanskelig for et menneske å lese, men merker at det er dette mønsteret av festemateriell med søkeord som alternativ, søkeord som verdi, noen siterte strenger. Det er der, da du registrerte deg for aller første gang, spesifisert hva fødselsår er. At drop-down menyen for medfødte år er liksom kodet her i dette språket kalles HTML, HyperText Markup Language. Med andre ord, når nettleseren ber en nettside, det taler denne konvensjonen heter HTTP. Men hva svarer facebook.com til at forespørselen med? Den reagerer med noen av disse kryptiske meldinger, som vi skal se om et øyeblikk. Men mest av sitt svar er i form av HTML, HyperText Markup Language. Det er selve språket som en nettside er skrevet. Og hva en nettleser virkelig er da, ved mottak av noe som ser ut som dette, leser det topp til bunn, fra venstre til høyre, og hver gang den ser en av disse festemateriell etterfulgt av et søkeord som alternativ, viser det at markup language på en forsvarlig måte. I dette tilfellet ville det vise en drop-down menyen år. Men igjen, dette er et komplett rot å se på. Dette er ikke fordi Facebook utviklere manifest 0 for 5 for stil, for eksempel. Dette er fordi de fleste av koden som de skriver er faktisk skrevet vakkert, godt kommentert, pent innrykket, og lignende, men selvfølgelig, datamaskiner, nettlesere egentlig ikke gi en jævla om koden er godt stylet. Og faktisk, det er helt bortkastet å treffe tabulatortasten alle de gangene og å sette kommentarer gjennom hele koden din og velge virkelig beskrivende variabelnavn fordi hvis nettleseren ikke bryr seg, er alt du gjør på slutten av dagen sløse bytes. Så det viser seg hva de fleste nettsteder gjør er, selv om kildekoden for facebook.com, for cs50.net og alle disse andre nettstedene på Internett er vanligvis godt skrevet og godt kommentert og pent innrykket og lignende, vanligvis før nettsiden er satt på internett, er koden minified, der HTML og CSS - noe annet vil vi snart se - JavaScript-koden vil vi snart se er komprimert, hvorved lange variabelnavn blir X og Y og Z, og alle som blanktegn som gjør alt ser så lesbar er alle kastet bort, fordi hvis du tenker på det på denne måten, får Facebook en milliard sidevisninger per dag - noe sprøtt sånn - så hva hvis en programmerer bare for å være anal traff space bar en ekstra gang bare for å rykke litt kodelinje aldri så mye mer? Hva er konsekvensen hvis Facebook bevarer at whitespace i alle byte sender de tilbake til folk på Internett? Treffer plassen bar gir når du en ekstra byte i filen. Og hvis en milliard mennesker så fortsette å laste ned hjemmesiden den dagen, hvor mye mer data du har overført over Internett? En gigabyte for ingen god grunn. Og gitt, for en rekke nettsteder dette er ikke en så skalerbar problem, men for Facebook, for Google, for noen av de mest populære nettsteder det er stor oppmuntring økonomisk gjøre koden ser ut som et rot slik at du bruker så få bytes som mulig i tillegg til da komprimere den bruke noe sånt som zip, kalles en algoritme gzip, at nettleseren gjør for deg automatisk. Men dette er forferdelig. Vi vil aldri lære noe om andre menneskers nettsteder og hvordan å designe web sider hvis vi må se på det som dette. Så heldigvis, nettlesere som Chrome og IE og Firefox i disse dager vanligvis kommer med innebygd utviklerverktøy. Faktisk, hvis jeg går ned hit for å Inspiser Element eller hvis jeg går til Vis, Developer og gå til Utviklerverktøy eksplisitt, dette vinduet nederst på skjermen min vises nå. Det er litt skremmende i begynnelsen, fordi det er mye av ukjente faner her, men hvis jeg klikker på elementer hele veien nederst til venstre, Chrome er åpenbart ganske smart. Det vet hvordan man skal tolke alt dette koden. Og så hva Chrome gjør er det renser opp alle Facebooks HTML. Selv om det ikke er mellomrom der, det er ikke innrykk der, nå merke til at jeg kan begynne å navigere denne nettsiden desto mer hierarkisk. Det viser seg at hver nettside skrevet i et språk som kalles HTML5 bør starte med dette, Dette DOCTYPE erklæringen, så å si: Det er slags lys og grå der, men det er den aller første kodelinje i denne filen, og det forteller bare nettleseren, "Hey, her kommer noen HTML5. Her kommer en nettside." Den første åpne braketten utover det skjer for å være denne tingen, en åpen brakett HTML-kode, og hvis jeg dykke i dypere - disse pilene er helt meningsløst; de er bare for presentasjon skyld, de er faktisk ikke i filen - merke til at innsiden av Facebooks HTML-kode, noe som starter med et åpent brakett og da har et ord kalles en kode. Så inne i HTML-koden er tilsynelatende et hode-kode og en body-koden. Innsiden av hodet koden er nå en hel rot for Facebook fordi de har mye av metadata og andre ting for markedsføring og reklame. Men hvis vi bla ned, ned, ned, ned, la oss se hvor det er. Her er det. Dette er i det minste noe kjent. Tittelen på Facebook hjemmeside, hvis du noen gang ser i fanen i tittellinjen, er Velkommen til Facebook - logg inn, registrer deg eller lære mer. Det er hva du ville se i Chrome tittellinje, og det er hvordan det er representert i koden. Hvis vi ser bort alt annet i hodet, de fleste av guts av en nettside er i kroppen, og det viser seg at Facebooks kode kommer til å se mer komplekse enn de fleste ting vil vi skrive utgangspunktet bare fordi det er blitt bygget opp gjennom årene, men det er en hel masse skriptkodene, JavaScript-kode, som gjør nettstedet svært interaktive: se statusoppdateringer umiddelbart med språk som JavaScript. Det er noe som kalles en div, som er en divisjon av en side. Men før vi kommer til det detalj, la oss prøve å zoome ut og se på en enklere versjon av Facebook 1.0, så å si. Her er hallo, verden av websider. Det har den DOCTYPE deklarasjon på toppen som er litt forskjellig fra alt annet. Ingenting annet vi skriver i en nettside kommer til å starte med for fet. Igjen er historien den samme: Hallo, komma, begynne å gjøre denne dristige, da verden blir trykket i fet skrift, og dette betyr stoppe utskriften dette i fet skrift. La meg gå videre og lagre filen min, gå tilbake til Chrome, vil jeg zoome inn så vi kan se det bedre, og legg, og du vil se at verden er nå i fet skrift. Web handler om hyperkoblinger, så la oss gå videre og gjøre dette: min favoritt nettside er, la oss si, youtube.com. Lagre, laste. Okay. Det er et par problemer nå foruten den skrekkelige nettstedet. 1, er jeg ganske sikker på at jeg traff inn her. Og jeg gjorde. Jeg ikke bare trykke Enter, jeg også rykket, praktisere det vi har forkynt om stil, men min er rett ved siden av verden. Så hvorfor er dette? Nettlesere bare gjøre det du ber dem om å gjøre. Jeg har ikke fortalt leseren, "Break linjer her. Sett ledd pause her." Så leseren, spiller det ingen rolle om jeg traff Return 30 ganger, det er fortsatt kommer til å sette min rett ved siden av verden. Hva jeg virkelig har å gjøre her er å si noe sånt som
, sette inn et linjeskift. Og faktisk er et linjeskift slags merkelig ting fordi du ikke kan virkelig begynne å flytte til en annen linje, så gjør noe, og deretter stoppe å flytte til en ny linje. Det er slags en atom operasjon. Du enten gjøre det eller gjør du ikke. Du trykker på Enter eller ikke. Så br er en liten bit av en annen kode, og så jeg trenger å sortere både åpne og lukke den alt på en gang. Syntaksen for det er dette. Teknisk, kan du gjøre noe som dette i noen versjoner av HTML, men dette er bare dumt fordi det er ingen grunn til å starte og stoppe noe hvis du kan i stedet gjøre alt på en gang. Innse at HTML5 ikke strengt nødvendig denne skråstrek, så du vil se lærebøker og elektroniske ressurser som ikke har det, men for godt mål la oss øve på symmetri som vi har sett så langt. Dette betyr at brikken er både åpnes og lukkes. Så nå la meg lagre filen min, gå tilbake hit. Ok, så det begynner å se bedre ut, bortsett fra nettet jeg vet er slags klikkbare, og likevel youtube her ikke synes å føre til noe. Det er fordi selv om det ser ut som en link, ikke nettleseren ikke vet at per se, så jeg må fortelle leseren at dette er en kobling. Måten å gjøre dette på er å bruke et anker tag: og la meg flytte denne til en ny linje bare så det er litt mer lesbar, og jeg vil krympe skriftstørrelsen. Jeg er ferdig ennå? Nei Det kommer til å bli denne motsetningen. Denne taggen, ankerkoden, tar faktisk et attributt, som modifiserer sin atferd, og verdien av attributtet er tilsynelatende YouTube URL. Men legg merke motsetningen er at bare fordi det er nettadressen du skal, det betyr ikke at må være ordet som du understreking og gjør en link. Snarere kan det være noe sånt som dette. Så jeg må si slutte å gjøre dette ordet en hyperkobling ved hjelp av tett ankerkoden. Legg merke til jeg ikke gjør dette. 1, vil dette bare være en sløsing med alles tid, og det er ikke nødvendig. For å lukke en tag, du bare nevner navnet på koden på nytt. Du trenger ikke nevne noen av attributtene. Så la oss lagre det, gå tilbake. Ok, voila, nå er det blå og hyperkoblet. Hvis jeg klikker på den, jeg faktisk gjør gå til YouTube. Så selv om min nettside er ikke på internett, er det minst HTML, og hvis vi la Internett fange opp, ville vi faktisk ende opp her på youtube.com. Og jeg kan gå tilbake og her er min nettside. Men legg merke dette. Hvis du noen gang har fått spam eller phishing-angrep, nå har du muligheten etter bare fem minutter å gjøre det samme. Vi kan gå her og gjøre noe som www.badguy.com eller hva den sketchy nettstedet er, og da kan du si bekrefte din PayPal-konto. [Latter] Og nå dette kommer til å gå til badguy.com, som jeg ikke kommer til å klikke på fordi jeg har ingen anelse om hvor det fører. [Latter] Men vi har nå muligheten til å faktisk ende opp der. Så vi egentlig bare begynt å skrape i overflaten. Vi er ikke programmering per se, vi skriver kodespråk. Men så snart vi avrunder vår vokabular i HTML, vi vil introdusere PHP, en faktisk programmeringsspråk som vil tillate oss å generere HTML automatisk, generere CSS automatisk, slik at vi kan begynne på onsdag for å gjennomføre, sier vår egen søkemotor og mer. Men mer om det i et par dager. Vi vil se deg da. [CS50.TV]