DAVID MALAN: Greit. Vi er tilbake. Så i dette segmentet på programmering hva Jeg trodde vi ville gjøre er en blanding av ting. One, gjøre litt noe hands-on, riktignok ved hjelp av en mer leken programmering environment-- en som er demonstrative av nøyaktig hva slags ideer vi har snakket om, men litt mer formelt. To, se på noen av de mer tekniske måter at en programmerer faktisk ville løse problemer som søker problem som vi så på før og også en mer fundamentalt interessant problem for sortering. Vi antok bare fra får gå som at telefonboken ble sortert, men det alene er faktisk slags en vanskelig problem med mange forskjellige måter å løse det. Så vi vil bruke disse som en klasse av problemer representant for ting som kan løses generelt. Og så får vi snakke om i noen detalj hva kalles data structures-- avansert måter som lenkede lister og hash tabeller og trær som en programmerer ville faktisk bruke og bruker vanligvis på en tavle til å male et bilde av hva han eller hun ser for seg for å implementere noen stykke programvare. Så la oss gjøre hands-on delen først. Så bare få hendene skitne med en miljø kalt scratch.mit.edu. Dette er et verktøy som vi bruker i vår lavere klasse. Selv om det er utformet for alderen 12 og oppover, vi bruker det for opp del av det ganske mye siden det er en fin, morsom grafisk måte å lære på litt noe om programmering. Så hodet til denne URLen, der du bør se en side som dette, og gå videre og klikk Bli med Scratch øverst til høyre og velge et brukernavn og et passord og til slutt få deg en account-- scratch.mit.edu. Jeg tenkte jeg skulle bruke dette som en mulighet første til å vise dette. Et spørsmål kom opp i pausen om hva koden faktisk ser ut. Og vi snakket i pausen om C, i particular-- spesielt en lavere nivå i en eldre språk. Og jeg bare gjorde en rask Google-søk for å finne C-kode for binære søk, algoritmen som vi brukes til å søke som telefonboken tidligere. Denne spesielle eksempel er selvfølgelig søker ikke en telefonkatalog. Den søker bare en hel haug med Tallene i datamaskinens minne. Men hvis du ønsker å bare få en visuell følelse av hva en faktisk programmering språket ser ut, det ser ut litt noe sånt som dette. Så det handler om 20-plus, 30 eller så linjer med kode, men samtalen vi hadde i løpet av pausen var om hvordan dette faktisk blir forvandlet til nuller og enere og hvis du ikke kan bare gå tilbake som behandle og gå fra nuller og enere tilbake til koden. Dessverre, prosessen er så transformative at det er mye lettere sagt enn gjort. Jeg gikk videre og faktisk slått det programmet, Binary Search, til nuller og enere i form av en program kalt The Compiler at jeg tilfeldigvis har her rett på min Mac. Og hvis du ser på skjermen her, med fokus spesielt på disse middel seks kolonner bare, ser du bare nuller og enere. Og de er de nuller og enere som komponere akkurat det søker programmet. Og slik at hver del av fem biter, hver byte av nuller og enere her, representere noen instruksjon typisk inne i en datamaskin. Og faktisk, hvis du har hørt markedsføring slagord "Intel inside" - det vil si, selvfølgelig, betyr bare at du har en Intel CPU eller hjerne inni datamaskinen. Og hva det betyr å være en CPU er at du har en instruksjonssett, så å si. Hver CPU i verden, mange av dem laget av Intel i disse dager, forstår et endelig antall instruksjoner. Og disse instruksjonene er så lavt nivå som legger disse to tallene sammen, multiplisere disse to tallene sammen, flytte denne stykke data herfra til her i minnet, lagre denne informasjon fra her til her i minnet, og så forth-- så veldig, veldig lavt nivå, nesten elektroniske detaljer. Men med de matematiske operasjoner kombinert med hva vi snakket om tidligere, representasjon av dataene som nuller og enere, kan du bygger opp alt at en datamaskin kan gjøre i dag, enten det er tekstlig, grafisk, musikalsk, hvis ikke. Så dette er veldig lett å få tapt i ugress av raskt. Og det er mye av syntaktisk utfordringer der hvis du gjør det enkleste, dummeste av skrivefeil ingen av programmet vil fungere overhodet. Og så i stedet for å bruke en språk som C i morges, Jeg trodde det ville være mer moro å faktisk gjøre noe mer visuell, som mens beregnet for barn er faktisk en perfekt manifestasjon av en faktisk programmering language-- bare skjer for å bruke bilder i stedet for tekst å representere disse ideene. Så når du faktisk har en kontoen på scratch.mit.edu, Klikk på Opprett-knappen øverst til venstre på siden. Og du burde se et miljø som den jeg er i ferd med å se på skjermen min her. Og vi vil bruke bare litt litt tid på å spille her. La oss se om vi ikke kan alle løse noen problemer sammen på følgende måte. Så hva du vil se i denne environment-- og faktisk bare la meg pause. Er noen ikke her? Ikke her? OK. Så la meg påpeke noen egenskapene til dette miljøet. Så øverst til venstre på skjermen, vi har Scratch etappe, så å si. Scratch er ikke bare navnet av denne programmeringsspråk; det er også navnet på katten som du ser som standard der i oransje. Han er på en scene, så mye som jeg beskrev skilpadden tidligere som å være i en rektangulær hvit bord miljø. Denne katten verden er begrenset helt til at rektangelet opp toppen der. I mellomtiden, på høyre siden her, er det bare et skript, en blankt hvis du vil. Det er der vi kommer til å skrive våre programmer i bare et øyeblikk. Og byggesteinene som vi skal bruke til å skrive denne program-- puslespillet stykker, hvis du will-- er de rett her i midten, og de er kategorisert av funksjonalitet. Så, for eksempel, kommer jeg til å gå videre og viser i det minste en av disse. Jeg kommer til å gå videre og klikk Kontroll kategorien opp toppen. Så dette er kategoriene opp toppen. Jeg kommer til å klikke kontroll kategorien. Snarere, jeg kommer til å klikke Hendelser kategori, den aller første opp toppen. Og hvis du ønsker å følge med selv som vi gjør dette, er du veldig velkommen til. Jeg kommer til å klikke og dra første, "når grønt flagg klikket." Og så kommer jeg til å droppe det bare omtrent på toppen av min blanke ark. Og hva er fint om Scratch er at dette puslespillet stykke, når forriglet med andre pusle stykker, kommer til å gjøre bokstavelig hva disse brikkene si å gjøre. Så, for eksempel, er Scratch riktig nå i midten av sin verden. Jeg kommer til å gå videre og velge nå, la oss si, kategori Motion, Hvis du ønsker å gjøre det same-- Motion kategori. Og nå merker jeg har en hel haug av brikkene her som, igjen, på en måte gjøre hva de sier. Og jeg kommer til å gå foran og dra og slippe farten blokken rett over her. Og legg merke til at så snart du får nær bunnen av "grønne flagget klikket "-knappen, varsel hvordan en hvit strek, som om det er nesten magnetisk, ønsker den å gå dit. Bare la gå, og det vil knipse sammen og figurene vil matche. Og nå kan du kanskje nesten Gjett hvor vi skal med dette. Hvis du ser på Scratch scenen over her og ser opp til toppen av det, vil du se et rødt lys, en stoppskilt, og et grønt flagg. Og jeg kommer til å gå videre og se mine screen-- for bare et øyeblikk, hvis du kunne. Jeg kommer til å klikke på grønt flagg akkurat nå, og han flyttet det som synes å være 10 trinn eller 10 piksler, 10 prikker, på skjermen. Og så ikke så spennende, men la meg foreslå uten selv å lære dette, bare ved hjelp av egen din egen intuition-- utleid meg foreslå at du finne ut hvordan du gjøre Scratch gå rett av scenen. Har ham gjøre vei for høyre side av skjermen, hele veien mot høyre. La meg gi deg et øyeblikk eller så for å kjempe med det. Du ønsker kanskje å ta en titt på andre kategorier av blokker. Greit. Så bare for å oppsummere, når vi har det grønne flagget klikket her og flytte 10 trinn er bare instruksjon, hver gang jeg Klikk på den grønne flagg, hva skjer? Vel, som kjører programmet mitt. Så jeg kunne gjøre dette kanskje 10 ganger manuelt, men dette føles litt bit hackish, så å si, der jeg er egentlig ikke å løse problemet. Jeg prøver bare igjen og igjen og igjen og igjen før jeg slags uhell oppnå direktivet at jeg ønsket å oppnå tidligere. Men vi vet fra vår pseudo tidligere at det er dette begrepet i programmering av looping, gjør noe igjen og igjen. Og så så jeg at en haug med deg nådd for hva puslespill brikke? Gjenta til. Slik at vi kunne gjøre noe som gjenta til. Og hva gjorde du gjenta til nøyaktig? OK. Og la meg gå med en som er noe enklere for bare et øyeblikk. La meg gå videre og gjøre dette. Legg merke til at, som du kan ha oppdaget under kontroll, det er denne gjenta blokken, hvilken ser ikke ut som det er så stor. Det er ikke mye plass i mellom disse to gule linjer. Men som noen av dere kanskje har lagt merke til, hvis du dra og slipp, Legg merke til hvordan det vokser til å fylle formen. Og du kan selv pugge mer. Det vil bare fortsette å vokse hvis du drar og sveve over det. Og jeg vet ikke hva som er beste her, så la meg minst gjenta fem ganger, for eksempel, og deretter gå tilbake til scenen og klikk på den grønne flagget. Og nå legger merke til det er ikke helt der. Nå er noen av dere foreslått, som Victoria nettopp gjorde, gjenta 10 ganger. Og som regel gjør få ham hele veien, men ville ikke det være en mer robust måte enn vilkårlig finne ut hvor mange trekk å gjøre? Hva kan være en bedre blokk enn gjenta 10 ganger være? Ja, så hvorfor ikke gjøre noe for alltid? Og nå la meg flytte dette puslespill brikke inni der og bli kvitt denne. Legg merke til nå uansett hvor Scratch starter, går han til kanten. Og heldigvis MIT, som gjør Scratch, bare sørger for at han aldri forsvinner helt. Du kan alltid ta halen. Og akkurat intuitivt, hvorfor han holder koken? Hva skjer her? Han synes å ha stoppet, men så hvis jeg plukker opp og dra han holder ønsker å gå dit. Hvorfor det? Sannelig, er en datamaskin bokstavelig talt kommer til å gjøre det du ber den om. Så hvis du fortalte det tidligere gjøre følgende ting alltid, flytte 10 trinn, det kommer til å fortsette og fortsette før jeg traff den røde stoppskiltet og stoppe programmet helt. Så selv om du ikke gjorde det gjør dette, hvordan kunne jeg gjøre Scratch flytte raskere over skjermen? Flere trinn, ikke sant? Så i stedet for å gjøre 10 om gangen, hvorfor gjør ikke vi gå videre og endre det to-- hva ville du propose-- 50? Så nå kommer jeg til å klikke på den grønne flagg, og ja, han går veldig fort. Og dette, selvfølgelig, er bare en manifestasjon av animasjon. Hva er animasjon? Det er bare å vise deg det menneskelige en hel haug med stillbilder egentlig, veldig, veldig fort. Og så hvis vi bare fortelle ham til å bevege seg flere trinn, vi bare ha effekten være å endring der han er på skjermen alle de hurtigere per tidsenhet. Nå er neste utfordring som jeg foreslo var å ha ham sprette utenfor kanten. Og uten å vite hva puslespill stykker exist-- fordi det er greit hvis du ikke får til stadium av challenge-- hva ønsker du å gjøre intuitivt? Hvordan ville vi ha ham sprette tilbake og videre, mellom venstre og høyre? Yeah. Så vi trenger noen form tilstand, og vi ser ut til å ha conditionals, så å snakke, under kategorien Control. Hvilke av disse blokkene vi sannsynligvis vil? Ja, kanskje "hvis, da." Så legger merke til at blant de gule blokkene vi har her, det er denne "hvis" eller denne "if, else" blokk som vil tillate oss å gjøre en beslutning om å gjøre dette eller å gjøre det. Og du kan til og med hekker dem å gjøre flere ting. Eller hvis du ikke har gått her ennå, gå videre til Sensing kategori og-- la oss se om det er her. Så hva blokk kan være nyttig her å oppdage hvis han er av scenen? Ja, merker at noen av disse blokkene kan parametrized, så å si. De kan liksom tilpasset, ikke i motsetning til HTML i går med attributter, hvor disse attributtene type tilpasse atferden til en tag. Tilsvar her, kan jeg ta denne rørende blokk og endring og stiller spørsmålet, er du berøre musen pekeren som markøren eller er du berører kanten? Så la meg gå inn og gjøre dette. Jeg kommer til å zoome ut for et øyeblikk. La meg ta dette puslespill brikke her, dette puslespillet stykke dette, og jeg kommer til å virvar dem opp for bare et øyeblikk. Jeg kommer til å flytte denne, endre dette til rørende kant, og jeg kommer til å bevegelse gjøre dette. Så her er noen ingredienser. Jeg tror jeg har fått alt jeg vil. Vil noen liker å foreslå hvordan jeg kan koble disse kanskje topp til bunn for å løse problemet med å måtte Scratch flytte høyre til venstre til høyre for å venstre til høyre til venstre, hvert tid bare sprette av veggen? Hva ønsker jeg å gjøre? Hvilken blokk skal jeg koble til "Når grønne flagget klikket først"? OK, så la oss starte med "evig". Hva går inne neste? Noen andre. OK, flytte trinn. Greit. Hva så? Så da hvis. Og legg merke til, selv om det ser ut klemt tett sammen, det vil bare vokse å fylle. Det vil bare hoppe i der jeg vil ha det. Og hva gjør jeg satt mellom IF og da? Sannsynligvis "hvis berøre kanten." Og legg merke til, igjen, det er for stort for det, men det vil vokse til å fylle. Og så slår 15 grader? Hvor mange grader? Ja, så 180 vil spinne meg hele veien rundt. Så la oss se om jeg fikk denne retten. La meg zoome ut. La meg dra Scratch opp. Så han er litt forvrengt nå, men det er fint. Hvordan kan jeg tilbakestille ham lett? Jeg kommer til å jukse litt. Så jeg legger en annen blokk, bare for å være klar. Jeg vil at han skal peke 90 grader til høyre som standard, så jeg skal bare fortelle ham å gjøre det programmatisk. Og her går vi. Vi ser ut til å ha gjort det. Det er litt rart, fordi han går opp ned. La oss kalle det en bug. Det er en feil. En bug er en feil i et program, en logiske feil som jeg, mennesket, gjort. Hvorfor er han går opp ned? Har MIT skru opp eller gjorde jeg? Ja, jeg mener, det er ikke MITs feil. De ga meg en puslespillbrikke som sier slå noen antall grader. Og på Victoria forslag, Jeg snu 180 grader, som er riktig intuisjon. Men å snu 180 grader bokstavelig betyr å dreie 180 grader og det er egentlig ikke hva jeg vil, tilsynelatende. Fordi minst han er i Dette to-dimensjonal verden, så vende som egentlig skjer å vende ham opp ned. Jeg vil trolig bruke hva blokk i stedet, basert på det du ser her? Hvordan kan vi fikse dette? Ja, så vi kunne peke i motsatt retning. Og faktisk selv det er ikke kommer til å være nok, fordi vi kan bare hardt kode å peke venstre eller høyre. Du vet hva vi kan gjøre? Det ser ut som vi har en bekvemmelighet blokk her. Hvis jeg zoomer inn, kan du se noe vi liker her? Så det ser ut som MIT har en abstraksjon bygget i her. Denne blokken synes å være ekvivalent til hvilken andre blokker, flertall? Denne blokk synes å være ekvivalent til hele denne trioen av blokker som vi har her. Så det viser seg kan jeg forenkle min program ved å bli kvitt alt dette og bare sette dette inn her. Og nå er han fortsatt litt buggy, og det er greit for nå. Vi skal la det være. Men mitt program er enda enklere, og også dette ville være representativ av et mål i programming-- er ideelt sett gjøre koden som enkel, så kompakt som mulig, samtidig som den er så leselig som mulig. Du ønsker ikke å gjøre det så fyndig at det er vanskelig å forstå. Men merker jeg har erstattet tre blokker med en, og det er uten tvil en god ting. Jeg har abstrahert bort forestillingen for å sjekke om du er på kanten med bare ett kvartal. Nå kan vi ha det gøy med dette, faktisk. Dette legger ikke så mye intellektuell verdi, men leken verdi. Jeg kommer til å gå videre og ta denne lyden her. Så la meg gå videre, og la meg stoppe programmet for et øyeblikk. Jeg kommer til å ta opp følgende, gir tilgang til mikrofonen min. Her går vi. Au. La oss prøve dette igjen. Her går vi. OK, jeg spilte feil ting. Her går vi. Au. Au. Greit. Nå må jeg bli kvitt det. Greit. Så nå har jeg en innspilling av bare "au". Så nå kommer jeg til å gå videre og kaller dette "au". Jeg kommer til å gå tilbake til mine skript, og nå innkalling det er denne blokken som heter spille av lyd "meow" eller spille av lyd "au". Jeg kommer til å dra dette, og hvor skal jeg sette dette for komisk effekt? Ja, så nå er det slags buggy, fordi nå dette block-- Legg merke til hvordan denne "hvis på kanten, bounce "er slags selvstendig. Så jeg trenger å fikse dette. La meg gå videre og gjøre dette. La meg bli kvitt dette og gå tilbake til vår opprinnelige, mer bevisst funksjonalitet. Så "hvis berøre kanten, deretter" Jeg vil ha å svinge, som Victoria foreslått, 180 grader. Og ønsker jeg å spille lyden "au" der? Ja, merker det er utenfor den gule blokken. Så dette også ville være en bug, men jeg har lagt merke til det. Så jeg kommer til å dra den opp her, og innkalling nå er det inne i "hvis". Så "hvis" er denne typen av som arm-lignende blot det er bare kommer til å gjøre det som er på innsiden av det. Så nå hvis jeg zoomer ut på risikoen for annoying-- COMPUTER: Au, au, au. DAVID MALAN: Og det vil bare fortsette i det uendelige. Nå bare å akselerere ting her, la meg gå videre og åpne opp, la oss say-- la meg gå til noen av mine egne ting fra klassen. Og la meg åpne opp, la oss si, dette en laget av en av våre undervisnings fellows et par år siden. Så noen av dere kanskje husker dette spillet fra en svunnen tid, og det er faktisk bemerkelsesverdig. Selv om vi har gjort enkleste av programmer akkurat nå, la oss vurdere hva dette faktisk ser ut. La meg trykke play. Så i dette spillet, har vi en frosk, og bruke pil keys-- han tar større skritt enn jeg remember-- Jeg har kontroll over denne frosken. Og målet er å komme over den travle veien uten å kjøre inn i biler. Og la oss see-- hvis jeg går opp her, jeg må vente på en logg for å bla forbi. Dette føles som en bug. Dette er en type insekt. Greit. Jeg er på dette her, der, og deretter holde til du får alle Froskene til lily pads. Nå kan dette se alle de mer komplekse, men la oss prøve å bryte dette ned mentalt og verbalt i sine enkeltkomponenter blokker. Så det er nok et puslespill brikke som vi ikke har sett ennå men det er å svare på tastetrykk, til ting jeg traff på tastaturet. Så det er nok en slags blokk som sier, hvis nøkkelen er lik opp, deretter gjøre noe med Scratch-- kanskje flytte den 10 meter på denne måten. Hvis ned-tasten trykkes inn, flytte 10 trinn denne måten, eller venstre tast, flytte 10 trinn denne måten, 10 trinn som. Jeg har klart slått katten til en frosk. Så det er bare der kostyme, som skrape samtaler it-- vi bare importert et bilde av frosken. Men hva annet som skjer? Hvilke andre linjer med kode, hva andre brikkene gjorde Blake, vår undervisning stipendiat, bruker i dette programmet, tilsynelatende? Hva gjør alt move-- hva programmering konstruere? Motion, sure-- så flytte blokken, sikkert. Og hva er det trekk blokk innside, mest sannsynlig? Ja, en slags loop, kanskje en alltid blokkere, kanskje en gjentakelse block-- gjenta til blokken. Og det er det som gjør loggene og lily pads og alt annet trekk frem og tilbake. Det er bare skjer uendelige. Hvorfor er noen av bilene beveger seg raskere enn de andre? Hva er annerledes med disse programmene? Ja, sannsynligvis noen av dem tar flere trinn på en gang, og noen av dem færre trinn på en gang. Og den visuelle effekten er rask versus treg. Hva tror du skjedde? Da jeg fikk min frosk hele veien over gaten og elven på lilje pad, noe bemerkelsesverdig skjedde. Hva skjedde så snart jeg gjorde det? Det stoppet. Det frosk stoppet, og Jeg fikk en andre frosk. Så hva konstruksjonen må være brukes der, hva funksjonen? Ja, så det er en slags "Hvis" tilstand der oppe også. Og det viser out-- vi ikke se dette-- men det er andre blokker i det som kan si, hvis du er rørende en annen ting på skjermen, hvis du berører den lilje pad ", da." Og så det er når vi gjøre andre frosken vises. Så selv om dette spillet er absolutt svært datert, selv om ved første øyekast det er så mye som skjer on-- og Blake ikke piske dette opp i to minutter, det sannsynligvis tok ham flere timer å lage dette spillet basert på hans minne eller videoer av en svunnen versjon av den. Men alle disse små tingene kommer på skjermen i isolasjon koke ned til disse svært enkle constructs-- bevegelser eller uttalelser som vi har diskutert, sløyfer og forhold, og det er omtrent det. Det er et par andre mer avansert funksjoner. Noen av dem er utelukkende estetisk eller akustisk, som lydene jeg bare spilt med. Men for det meste, du har i dette språket, Scratch, alle de fundamentale byggeklosser som du har i C, Java, Javascript, PHP, Ruby, Python, og en rekke andre språk. Eventuelle spørsmål om scratch? Greit. Så vi vil ikke dykke i dypere til Scratch, om du er velkommen denne helgen, spesielt hvis du har barn eller nieser og nevøer og slikt, å introdusere dem til å klø. Det er faktisk en fantastisk leken miljø med, som sine forfattere sier, svært høye tak. Selv om vi startet med svært lavt nivå detaljer, du virkelig kan gjøre ganske mye med det, og dette er kanskje en demonstrasjon av nettopp det. Men la oss nå gå over til litt mer sofistikerte problemer, om du vil, kjent som "søker" og "Sortering", mer generelt. Vi hadde denne telefonboken earlier-- her er en annen bare for discussion-- at vi var i stand til å søke mer effektivt fordi av en betydelig forutsetning. Og bare for å være klar, hva forutsetningen var jeg gjør når du søker gjennom denne telefonboken? At Mike Smith var i telefonboken, selv om jeg ville være i stand til å håndtere scenariet uten ham der hvis jeg bare stoppet for tidlig. Boken er alfabetisk. Og det er en veldig sjenerøs antagelse, fordi det betyr someone-- Jeg er litt for å kutte et hjørne, som jeg er raskere fordi noen andre gjorde mye hardt arbeid for meg. Men hva hvis telefonen Boken ble usortert? Kanskje Verizon fikk lat, bare kastet alles navn og numre i det kanskje i den rekkefølgen de meldt seg på telefonen. Og hvor lang tid tar det meg å finne noen som Mike Smith? 1000 side telefon book-- hvor mange sidene må jeg se gjennom? Alle sammen. Du er liksom ute av lykken. Du har bokstavelig talt å se på hver siden hvis telefonboken er bare tilfeldig sortert. Du kan ha flaks og finne Mike på den aller første siden, fordi han var den første kunden å bestille telefonen tjenesten. Men han kan ha vært den siste, også. Så tilfeldig rekkefølge er ikke bra. Så antar at vi må sortere telefonboken eller generelt slags data at vi har fått. Hvordan kan vi gjøre det? Vel, la meg bare prøve et enkelt eksempel her. La meg gå videre og kaste en få tall på bordet. Anta at tallene vi har er, la oss si, fire, to, en, og tre. Og Ben, sortere disse tallene for oss. Ok bra. Hvordan gjorde du det? Greit. Så starte med den minste verdi og den høyeste, og det er virkelig god intuisjon. Og innse at vi mennesker er faktisk ganske flink til å løse problemer som dette, i det minste når dataene er relativt liten. Så snart du begynner å ha hundrevis av tall, tusenvis av tall, millioner av tall, Ben sannsynligvis kunne ikke gjøre det ganske så fort, når det ses hull i tallene. Ganske enkelt å telle til en million ellers bare tidkrevende. Så algoritmen det høres som Ben brukes akkurat nå var jakten på det minste tallet. Så selv om vi mennesker kan ta i mye informasjon visuelt, en datamaskin er faktisk en litt mer begrenset. Den kan datamaskinen bare se på en byte om gangen eller kanskje fire byte på en tid-- disse dager kanskje 8 byte på en tid-- men et meget lite antall av bytes på et gitt tidspunkt. Så gitt at vi virkelig har fire separate verdier her-- og du kan tenke på Ben som å ha skylapper på om han var en datamaskin slik at han ikke kan se noe annet enn ett nummer om tid-- så vi vanligvis vil anta, som i Engelsk, vil vi lese fra høyre mot venstre. Så det første nummeret Ben sannsynligvis sett på var fire og deretter svært raskt innsett at det er en ganske stor number-- la meg holde utkikk. Det er to. Vent litt. To er mindre enn fire. Jeg kommer til å huske. To er nå den minste. Nå one-- som er enda bedre. Det er enda mindre. Jeg kommer til å glemme to og bare husk en nå. Og kan han slutte å se? Vel, han kunne basert på denne informasjonen, men han hadde bedre søk resten av listen. Fordi hva om null var på listen? Hva om negativt var på listen? Han vet bare at hans svar er riktig hvis han er uttømmende sjekket hele listen. Så vi ser på resten av dette. Three-- det var bortkastet tid. Fikk uheldig, men jeg var fortsatt er riktig å gjøre det. Og så nå er han antagelig valgt minste tallet og bare sette den i begynnelsen av listen, som jeg skal gjøre her. Nå hva gjorde du gjøre videre, selv om du ikke tenke på det nesten i denne grad? Gjenta prosessen, så en slags loop. Det er en kjent idé. Så her er fire. Det er for tiden den minste. Det er en kandidat. Ikke nå lenger. Nå har jeg sett to. Det er den nest minste element. Three-- det er ikke mindre, så nå Ben kan plukke ut de to. Og nå gjentar vi prosessen, og selvfølgelig tre blir trukket ut neste. Gjenta prosessen. Fire blir trukket ut. Og nå er vi ute av tall, så listen skal sorteres. Og ja, dette er en formell algoritme. En datamaskin vitenskapsmann ville kaller dette "valget sort," ideen er liksom en liste iteratively-- igjen og igjen og igjen velge det minste tallet. Og hva er fint om det er det er bare så utrolig intuitiv. Det er så enkelt. Og du kan gjenta det samme drift igjen og igjen. Det er enkelt. I dette tilfellet var det raskt, men hvor lang tid det faktisk tar? La oss gjøre det virke og føler meg litt mer kjedelig. Så en, to, tre, fire, fem seks, syv, åtte, ni, ti, elleve, tolv, tretten, fjorten, 15, 16-- vilkårlig antall. Jeg ville bare mer dette tid enn bare de fire. Så hvis jeg har en hel haug av tall now-- det ikke engang saken hva de are-- la oss tenke på hva dette algoritmen egentlig er. Anta at det er tall der. Igjen, spiller ingen rolle hva de er, men de er tilfeldige. Jeg søker Ben algoritme. Jeg må velge det minste tallet. Hva gjør jeg? Og jeg kommer til fysisk gjøre det denne gangen til å handle det ut. Ser, ser, ser, ser, ser. Bare av den tiden jeg får til enden av listen kan Jeg skjønner de minste tallet var to denne gangen. Man er ikke i listen. Så jeg satte ned to. Hva gjør jeg nå? Ser, ser, ser, ser. Nå fant jeg nummer syv, fordi det er hull i disse numbers-- men bare tilfeldig. Greit. Så nå kan jeg legge ned syv. Ser ser, ser. Nå er jeg forutsatt, Selvfølgelig, at Ben ikke har ekstra RAM, ekstra hukommelse, fordi naturligvis Jeg ser på det samme nummeret. Sikkert jeg kunne ha husket alle disse tall, og det er helt sant. Men hvis Ben husker alle av tallene han har sett, Han har egentlig ikke gjort fundamental fremgang fordi han allerede har muligheten til å søke gjennom tallene på brettet. Huske alle tallene ikke hjelper, fordi han kan stille som en datamaskin bare se på, vi har sagt, ett tall på en gang. Så det er ingen form for cheat Det at du kan utnytte. Så i virkeligheten, som jeg fortsette å søke i listen, Jeg har bokstavelig talt å bare holde det gående frem og tilbake gjennom det, plukker ut neste minste tallet. Og som du kan slags antyde fra mine dumme bevegelser, dette blir bare veldig kjedelige veldig raskt, og jeg synes å være å gå tilbake og frem, frem og tilbake ganske mye. Nå for å være rettferdig, jeg må gå ganske så, vel, la oss see-- å være rettferdig, Jeg trenger ikke å gå helt så mange skritt hver gang. Fordi, selvfølgelig, som jeg numre fra listen, de resterende listen blir kortere. Og så la oss tenke på hvor mange skritt jeg faktisk traipsing gjennom hver gang. I den aller første situasjonen vi hadde 16 tall, og så maximally-- la oss bare gjør dette for en discussion-- Jeg måtte se gjennom 16 tall for å finne den minste. Men når jeg plukket ut det minste tallet, hvor lenge var de resterende liste, selvfølgelig? Bare 15. Så hvor mange tall gjorde Ben eller jeg har å se gjennom den andre gangen? 15, bare for å gå og finne den minste. Men nå, selvfølgelig, er på listen, også, er mindre enn det var før. Så hvor mange skritt gjorde jeg nødt til å ta det neste gang? 14 og deretter 13 og så 12, pluss dot, prikk, prikk, før jeg sitter igjen med kun én. Så nå en datamaskin vitenskapsmann ville spør, vel, hva gjør det alle like? Det faktisk er lik noen konkrete nummer som vi kunne sikkert gjøre arithmetically, men vi ønsker å snakke om effektiviteten av algoritmer litt mer formulaically, uavhengig av hvor lang listen er. Og så vet du hva? Dette er 16, men som jeg sa før, la oss bare kalle størrelsen på problemet n, hvor n er et antall. Kanskje det er 16, kanskje det er tre, kanskje det er en million. Jeg vet ikke. Jeg bryr meg ikke. Det jeg egentlig ønsker er en formel som jeg kan bruke til å sammenligne denne algoritmen mot andre algoritmer at noen kan hevde er bedre eller verre. Så det viser seg, og jeg bare vet dette fra grunnskolen, at dette faktisk funker til det samme ting som n på n pluss en over to. Og dette skjer til lik, av Selvfølgelig n kvadrat pluss n over to. Så hvis jeg ønsket en formel for hvor mange skritt var involvert i å se i det hele tatt av disse tallene igjen og igjen og igjen og igjen, vil jeg si det er n kvadrat pluss n over to. Men vet du hva? Dette ser bare rotete. Jeg bare virkelig ønsker en generell følelse av ting. Og du kanskje husker fra videregående skole at det er oppfatningen av høyeste orden sikt. Hvilke av disse vilkårene, n kvadrat, n, eller den halve, har størst innvirkning over tid? Jo større n blir, som av disse teller mest? Med andre ord, hvis jeg kobler i en million, n squared kommer til å være mest sannsynlig den dominerende faktor, en million fordi ganger i seg selv er mye større enn pluss en ekstra million. Så vet du hva? Dette er en så darn stor nummer hvis du kvadrere et tall. Dette spiller ingen rolle. Vi kommer bare til korset som ut og glemme det. Og så en datamaskin vitenskapsmann vil si at virkningsgraden av denne algoritmen er i størrelsesorden n squared-- Jeg mener virkelig en tilnærming. Det er liksom omtrent n squared. Over tid, jo større og større n blir, dette er et godt anslag for hva effektivitet eller mangel på effektivitet av denne algoritmen faktisk er. Og jeg utlede det, selvfølgelig, fra faktisk gjør regnestykket. Men nå er jeg bare vinke hendene mine, fordi jeg bare ønsker en generell følelse av denne algoritmen. Så bruker den samme logikken, i mellomtiden, la oss vurdere en annen algoritme vi allerede sett at-- lineær søk. Når jeg søker for telefonen book-- ikke sortere det, søking gjennom telefonen book-- Vi fortsatte å si at det var 1000 trinn, eller 500 trinn. Men la oss generalisere det. Hvis det er n sider telefonboken, hva er kjøretiden eller effektiviteten av lineær søk? Det er i størrelsesorden hvor mange skritt for å finne Mike Smith ved hjelp av lineær søk, jo første algoritme, eller til og med den andre? I verste fall, Mike er ved slutten av boken. Så hvis telefonboken har 1000 sider, vi sa sist gang, i verste fall, det kan ta omtrent hvor mange sider for å finne Mike? Som 1000. Det er en øvre grense. Det er en verst tenkelige situasjon. Men igjen, vi beveger seg bort fra tall som 1000 nå. Det er bare n. Så hva er den logiske konklusjonen? Finne Mike i en telefon bok som har n sider kan ta, i det aller verste fall hvor mange trinn i størrelsesorden av n? Og faktisk en datamaskin vitenskapsmann vil si at kjøretiden, eller ytelse eller effektivitet eller ineffektivitet, av en algoritme som en lineær søk er i størrelsesorden n. Og vi kan bruke den samme Logikken i krysset noe ut som jeg nettopp gjorde med den andre algoritme vi hadde med telefonboken, hvor vi gikk to sider om gangen. Så tusen side telefonbok kanskje ta oss 500 side svinger, pluss en hvis vi dobbelt tilbake litt. Så hvis en telefon bok har n sider, men vi gjør to sider om gangen, det er omtrent hva? N over to, så det er som n over to. Men jeg gjorde krav en øyeblikk siden at n løpet two-- det er slags det samme som bare n. Det er bare en konstant faktor, IT-forskere vil si. La oss bare fokusere på variablene, really-- de største variable i ligningen. Så lineær søk, enten gjort en side om gangen eller to sider om gangen, er liksom fundamentalt det samme. Det er fortsatt i størrelsesorden n. Men jeg hevdet med mitt bilde tidligere at den tredje algoritme var ikke lineær. Det var ikke en rett linje. Det var den buede linje, og den algebraisk formel det var det? Logg av N- så log base to av n. Og vi trenger ikke å gå inn i for mye detaljer på logaritmer i dag, men de fleste dataforskere ville ikke også fortelle deg hva basen er. Fordi det er bare konstante faktorer, så å si, bare små numeriske forskjeller. Og så dette ville være en svært vanlig måte for spesielt formell datamaskin forskere ved et bord eller programmerere på et hvitt bord faktisk krangler som algoritme de ville bruke eller hva virkningsgraden av sin algoritme er. Og dette er ikke nødvendigvis noe du diskutere i noen stor detalj, men en god programmerer er noen som har en solid, formell bakgrunn. Han er i stand til å snakke med deg i denne slags måte og faktisk gjøre kvalitative argumenter som hvorfor en algoritme eller ett stykke programvare er overlegen på noen måte til en annen. Fordi du kan sikkert bare kjøre en persons program og telle antall sekunder det tar å sortere noen tall, og du kan kjøre noen andre personens program og telle antall sekunder det tar. Men dette er en mer generell måte at du kan bruke til å analysere algoritmer, om du vil, bare på papir eller bare verbalt. Uten engang å kjøre det, uten selv prøver prøve innganger, du kan bare resonnere gjennom den. Og så med å ansette en utvikler eller hvis å ha ham eller henne liksom argumentere for deg hvorfor deres algoritme, deres hemmelighet saus for å søke milliarder av websider for din Selskapet er bedre, disse er den slags argumenter de bør ideelt sett være i stand til å gjøre. Eller i det minste disse er den slags ting som ville komme opp i diskusjonen, ved det minste i en meget formell diskusjon. Greit. Så Ben foreslått noe kalt utvalg slag. Men jeg kommer til å foreslå at det er andre måter å gjøre dette, også. Hva jeg ikke liker om Ben algoritme er at han fortsatte å gå, eller ha meg til å gå frem og tilbake og frem og tilbake og frem og tilbake. Hva om i stedet jeg skulle gjøre noe sånt som disse tallene her og jeg skulle bare forholde seg til hverandre Tallet i sving som jeg får det? Med andre ord, her min liste med tall. Four, en, tre, to. Og jeg kommer til å gjøre følgende. Jeg kommer til å sette inn tallene der de hører heller Bortsett fra å velge dem en om gangen. Med andre ord, her er nummer fire. Her er mitt opprinnelige listen. Og jeg kommer til å opprettholde hovedsak en ny liste her. Så dette er den gamle listen. Dette er den nye liste. Jeg ser nummer fire første. Min nye listen er i utgangspunktet tom, slik det er trivielt tilfellet at fire er nå assortert listen. Jeg er bare å ta antall jeg får, og jeg setter det i min nye liste. Er dette nye listen sortert? Yeah. Det er dumt, fordi det er bare en element, men det er absolutt sortert. Det er ikke noe malplassert. Det er mer interessant, denne algoritmen, når jeg flytter til neste trinn. Nå har jeg en. Så en, selvfølgelig, hører i begynnelse eller slutten av denne nye listen? Begynnelsen. Så jeg må gjøre noe arbeid nå. Jeg har tatt noen friheter med markør min ved bare å tegne ting der jeg vil ha dem, men det er egentlig ikke nøyaktig i en datamaskin. En datamaskin, som vi vet, har RAM eller Random Access Memory, og det er en byte og en annen byte og en annen byte. Og hvis du har en gigabyte RAM, har du en milliard bytes, men de er fysisk på ett sted. Du kan ikke bare flytte ting rundt ved å tegne det på tavlen når du vil. Så hvis min nye listen har fire steder i minnet, dessverre fire er allerede på feil sted. Så for å sette inn nummer én Jeg kan ikke bare trekke den her. Denne minneområde finnes ikke. Det ville være juks, og jeg har vært juks billedlig i noen minutter her. Så egentlig, hvis jeg ønsker å sette en her, Jeg må midlertidig kopiere fire og deretter sette den der. Det er greit, det er riktig, det er teknisk mulig, men skjønner det er ekstra arbeid. Jeg hadde ikke bare sette tall på plass. Jeg først måtte flytte en nummer, og deretter sette den på plass, så jeg slags doblet mengden arbeid. Så hold det i tankene. Men jeg er nå ferdig med dette elementet. Nå ønsker jeg å ta tak i nummer tre. Der er selvfølgelig hører det? Imellom. Jeg kan ikke jukse lenger og bare sette den der, fordi, igjen, denne hukommelse er i fysiske lokasjoner. Så jeg må kopiere fire og sette tre over her. Ikke noe viktig. Det er bare ett ekstra trinn igjen-- føles veldig billig. Men nå går jeg videre til de to. De to selvfølgelig hører her. Nå kan du begynne å se hvordan arbeidet kan hope seg opp. Nå hva må jeg gjøre? Ja, jeg må flytte de fire, Jeg må da kopiere de tre, og nå kan jeg sette inn to. Og fangsten med denne algoritme, interessant nok, er at anta at vi har en mer ekstrem tilfelle der det er la oss si åtte, sju, seks, fem, fire, tre, to, en. Dette er i mange sammenhenger, worst case scenario, fordi det darn tingen er bokstavelig talt bakover. Det gjør egentlig ikke påvirke Ben algoritme, fordi i Bens utvalg liksom han kommer til å holde går frem og tilbake gjennom listen. Og fordi han var alltid på utkikk gjennom hele resten av listen, det spiller ingen rolle hvor elementene er. Men i dette tilfellet med min innsetting approach-- la oss prøve dette. Så en, to, tre, fire, fem, seks, sju, åtte. En to tre fire, fem, seks, sju, åtte. Jeg kommer til å ta åtte, og hvor finner jeg si det? Vel, i begynnelsen av listen min, fordi denne nye listen er sortert. Og jeg krysser den ut. Hvor plasserer jeg de sju? Filler'n. Det er behov for å gå dit, så Jeg må gjøre noen kopiering. Og nå syv går her. Nå går jeg videre til seks. Nå er det enda mer arbeid. Åtte har å gå her. Seven har å gå her. Nå seks kan gå her. Nå ta jeg de fem. Nå åtte må gå her, har syv å gå her, seks har å gå her, og nå fem og gjenta. Og jeg er ganske mye flytte det hele tiden. Så på slutten, dette algorithm-- vi vil kalle det innsetting sort-- faktisk har mye arbeid, også. Det er bare annerledes slags arbeid enn Ben. Ben arbeid hadde meg gående frem og tilbake hele tiden, velge den nest minste element igjen og igjen. Så det var dette veldig visuell type arbeid. Denne andre algoritme, som fremdeles correct-- det vil få jobben done-- bare endrer mengden av arbeid. Det ser ut som i utgangspunktet du er besparende, fordi du er bare arbeider med hvert element opp foran uten å gå hele veien gjennom listen som Ben var. Men problemet er, spesielt i disse gale tilfeller der det er alt bakover, du er bare slags utsette det harde arbeidet før du må fikse dine feil. Og så hvis du kan forestille deg dette åtte og sju og seks og fem og senere fire og tre og to beveger seg gjennom listen, Vi har nettopp endret type arbeid vi gjør. I stedet for å gjøre det på begynnelsen av min iterasjon, Jeg bare gjør det på slutten av hver iterasjon. Så det viser seg at denne algoritmen, også, vanligvis kalt innsetting sortere, er også i størrelsesorden n squared. Det er faktisk ikke noe bedre, ikke noe bedre i det hele tatt. Men det er en tredje tilnærming Jeg vil oppfordre oss til å vurdere, som er denne. Så antar at min liste, for enkelhet igjen, er fire, én, tre, two-- bare fire tall. Ben hadde god intuisjon, god menneskelig intuisjon før, som vi festet hele liste eventually-- innsetting slag. Jeg siktet oss sammen. Men la oss vurdere enkleste måten å løse denne listen. Denne listen er ikke sortert. Hvorfor? På engelsk, forklare hvorfor det er faktisk ikke sortert. Hva betyr det ikke skal sorteres? STUDENT: Det er ikke i rekkefølge. DAVID MALAN: Ikke sekvensiell. Gi meg et eksempel. STUDENT: Sett dem i rekkefølge. DAVID MALAN: OK. Gi meg et mer konkret eksempel. STUDENT: stigende rekkefølge. DAVID MALAN: Ikke stigende rekkefølge. Være mer presis. Jeg vet ikke hva du mener med stigende. Hva er galt? STUDENT: Den minste av tall er ikke i den første plass. DAVID MALAN: Minste antall er ikke i den første plass. Være mer spesifikk. Jeg begynner å ta på. Vi teller, men hva som er i ustand her? STUDENT: Numerisk rekkefølge. DAVID MALAN: Numerisk rekkefølge. Alles slags regnskap det her-- svært høyt nivå. Bare bokstavelig fortelle meg hva som er feil som en fem-åring makt. STUDENT: Pluss én. DAVID MALAN: Hva er det? STUDENT: Pluss én. DAVID MALAN: Hva mener du pluss en? Gi meg en annen fem år gammel. Hva er galt, mamma? Hva er galt, pappa? Hva mener du dette er ikke sortert? STUDENT: Det er ikke rett sted. DAVID MALAN: Hva er ikke på rett sted? STUDENT: Four. DAVID MALAN: OK, bra. Så fire er ikke der den skal være. Spesielt er dette sant? Fire og en, den første to tallene jeg ser. Er dette riktig? Nei, de er ute av drift, ikke sant? Faktisk tror nå om en datamaskin, også. Det kan bare se på kanskje en, kanskje to ting på once-- og faktisk bare én ting på en gang, men det kan i det minste ser på en ting da neste ting rett ved siden av den. Så er disse i orden? Selvfølgelig ikke. Så vet du hva? Hvorfor kan ikke vi ta babyen trinn fikse dette problemet stedet for å gjøre disse fancy algoritmer som Ben, der han er liksom fikse det ved looping gjennom listen i stedet for å gjøre det jeg gjorde, hvor Jeg bare slags fast det som vi går? La oss bare bokstavelig talt bryte ned oppfatningen av order-- numerisk rekkefølge, kalle det hva du want-- inn i disse parvise sammenligninger. Fire og en. Er dette riktig rekkefølge? Så la oss fikse det. Ett og fire, og deretter vi vil bare kopiere det. Greit, bra. Jeg fikset en og fire. Tre og to? Nei. La mine ord matche mine fingre. Fire og tre? Det er ikke i orden, så jeg kommer å gjøre en, tre, fire, to. Ok bra. Nå fire og to? Vi trenger å fikse dette, også. Så en, tre, to, fire. Så er det sortert? Nei, men er det nærmere sortert? Det er fordi vi løst dette feil, fikset vi denne feilen, og vi fikset denne feilen. Så vi fikset tre feil uten tvil. Fortsatt ikke egentlig ser sorterte, men det er objektivt nærmere sorterte fordi vi fikset noen av disse feilene. Nå hva gjør jeg nå? I slags nådd enden av listen. Jeg syntes å ha løst alle feilene, men nei. Fordi i dette tilfellet, noe nummer kanskje har boblet opp nærmere til andre tall som er fortsatt ute av drift. Så la oss gjøre det igjen, og jeg skal bare gjøre det på plass denne gangen. Ett og tre? Det er i orden. Tre og to? Selvfølgelig ikke, så la oss endre det. Så to, tre. Tre og fire? Og nå la oss bare være spesielt pedantisk her. Er det sortert? Du mennesker vet at det sortert. Jeg skal prøve igjen. Så Olivia foreslår jeg prøve igjen. Hvorfor? Fordi en datamaskin ikke har luksusen av våre menneskelige øyne av bare skotter back-- OK, er jeg ferdig. Hvordan datamaskinen bestemme at listen er nå sortert? Mekanisk. Jeg skal gå gjennom en gang, og bare hvis jeg ikke gjør / finne noen feil kan jeg deretter konkludere som datamaskinen, Jepp, vi er flink til å gå. Så en og to, to og tre, tre og fire. Nå kan jeg definitivt si at dette er sortert, fordi jeg har gjort noen endringer. Nå ville det være en feil og bare tåpelig hvis jeg, datamaskinen spurte de samme spørsmålene igjen venter forskjellige svar. Bør ikke skje. Og så nå listen er sortert. Dessverre, kjøretiden til denne algoritmen er også N kvadrat. Hvorfor? Fordi du har n antall, og i verste fall må du flytte n antall n ganger fordi du må holde det gående tilbake for å sjekke og eventuelt fastsette disse tallene. Og vi kan gjøre en mer formell analyse, også. Så dette er alt å si at vi har tatt tre ulike tilnærminger, en av dem umiddelbart intuitivt av baksten fra Ben til min foreslåtte innsetting sort til dette hvor du slags miste av syne skogen for bare trær utgangspunktet. Men så hvis du tar et skritt tilbake, voila, vi har løst sorterings forestillingen. Så dette blir, tør si, et lavere nivå kanskje enn noen av de andre algoritmer, men la oss se om vi ikke kan visualisere disse ved hjelp av denne. Så dette er noe hyggelig programvare som noen skrev ved hjelp av fargerike barer som er kommer til å gjøre følgende for oss. Hver av disse linjene representerer et tall. Taller baren, jo større nummeret, mindre tverr det mindre tall. Så ideelt sett ønsker vi en hyggelig pyramide hvor den starter i det små, og blir stor, og det ville bety at disse barene er sortert. Så jeg kommer til å gå videre og velge, for eksempel, Ben algoritme first-- utvalg slag. Og legg merke til hva det gjør. Måten de har valgt å visualisere denne algoritmen er det, akkurat som jeg var gå gjennom listen min, dette programmet er å vandre gjennom sin liste med tall, fremhever i rosa hver nummer som det er å se på. Og hva er i ferd med å skje nå? Den minste tall som Jeg eller Ben plutselig funnet blir flyttet til begynnelsen av listen. Og legg merke til de gjorde kaste ut nummeret som var der, og det er helt greit. Jeg fikk ikke komme inn i den detaljnivå. Men vi trenger å sette det tallet et sted, så vi flyttet den til åpen plass som ble opprettet. Så jeg kommer til å fremskynde denne opp, fordi ellers blir veldig kjedelig raskt. Animasjon speed-- der vi går. Så nå samme prinsipp Jeg søkte, men du kan begynne å føle algoritmen, hvis du vil, eller se det litt mer tydelig. Og denne algoritmen har den virkning å velge den neste minste element, så du kommer til å begynne å ser det rampen opp til venstre. Og på hver iterasjon, som jeg foreslått, gjør det litt mindre arbeid. Det trenger ikke å gå hele veien tilbake til den venstre ende av listen fordi det allerede vet de er sortert. Så det slags føles som om det er akselererende, selv om hvert trinn er tar like mye tid. Det er bare færre trinn gjenstår. Og nå kan du på en måte føler algoritme rydde opp i slutten av det, og faktisk nå er det ordnet. Så innsetting typen er ferdig. Jeg trenger å re-randomisere array. Og legg merke til jeg kan bare holde randomisering det, og vi får en tilnærming til samme tilnærming, innsetting slag. La meg sakte ned til her. La oss starte som over. Stoppe. La oss hoppe over fire. Det vi går. Tilfeldig de array. Og her Vær så god vi innsetting slag. Spille. Legg merke til at det er arbeider med hver element den støter på en gang, men hvis det hører til i feil sted varsel alt arbeidet som må skje. Vi må holde skiftende mer og flere elementer for å gjøre plass for en ønsker vi å få på plass. Så vi fokuserer på venstre ende av listen bare. Legg merke til at vi ikke har selv sett at-- vi har ikke markert i rosa noe til høyre. Vi er bare å gjøre med problemene som vi går, men vi skaper mye arbeide for oss selv fortsatt. Og så hvis vi fremskynde dette opp nå å gå til ferdigstillelse, den har en annen føler for det faktisk. Det er bare å fokusere på venstre slutten, men gjøre litt mer arbeid som needed-- slags glatte ting over, fikse ting, men arbeider til slutt med hvert element en om gangen før vi kommer til folk flest i vel, vi alle vet hvordan dette kommer til å ende, så det er litt uimponerende kanskje. Men listen i end-- spoiler-- kommer til å bli sortert. Så la oss se på en siste. Vi kan ikke bare hoppe over dette nå. Vi er nesten der. To til å gå, en å gå. Og voila. Utmerket. Så nå la oss gjøre en siste, re-randomisering med boblesortering. Og legg merke til her, spesielt hvis jeg roe det ned, betyr dette holde swooping gjennom. Men legg merke til det bare gjør parvise comparisons-- slags lokale løsninger. Men så snart vi får enden av listen i rosa, hva som kommer til å skje igjen? Ja, det er nødt til å begynne på nytt, fordi det bare faste parvise feil. Og som kanskje har avslørt ennå andre. Og så hvis du fart opp dette, vil du se at mye som navnet tilsier, den mindre elements-- eller rettere sagt, de større elements-- starter å boble opp til toppen, hvis du vil. Og de mindre elementene begynner å boble ned til venstre. Og ja, det er slags den visuelle effekten også. Og så dette vil ende opp slutt i en svært lik måte, også. Vi trenger ikke å dvele på denne ene. La meg åpne dette nå, også. Det er et par andre sortering algoritmer i verden, noen av dem fanges her. Og spesielt for elever som ikke er nødvendigvis visuelt eller matematisk, som vi gjorde før, kan vi også gjøre dette audially hvis vi knytte en lyd med dette. Og bare for moro skyld, her er en noen forskjellige algoritmer, og en av dem spesielt du er kommer til å merke kalles "merge sort." Det er faktisk en fundamentalt bedre algoritme, slik at flettesortering, en av de du er i ferd med å se, er ikke orden n squared. Det er i størrelsesorden n ganger logg av n, som faktisk er mindre og dermed raskere enn de andre tre. Og det er et annet par dumme de som vi får se. Så her går vi med litt lyd. Dette er innsetting sort, så igjen det er bare å gjøre med elementene som de kommer. Dette er boblesortering, så det er vurderer dem parvis på en gang. Og igjen, de største elementene er bobler opp til toppen. Neste opp valg slag. Dette er Ben algoritme, hvor igjen han velge iterativt den nest minste element. Og igjen, nå kan du virkelig høre at det er påskynde, men bare i den utstrekning som det gjør mindre og mindre jobbe med hver iterasjon. Dette er raskere en, flettesortering, som sortering klynger av tall sammen og deretter kombinere dem. Så look-- venstre halvparten er allerede sortert. Nå er det sortering høyre halvdel, og Nå kommer det til å kombinere dem til én. Dette er noe som kalles "Gnome slag." Og du kan slags se at det går frem og tilbake, fikse arbeidet litt her og der før den fortsetter til nytt arbeid. Og det er det. Det er en annen form, som er egentlig bare for akademiske formål, kalt "dum liksom", som tar dataene, sorterer det tilfeldig, og deretter sjekker om det er sortert. Og hvis det ikke er, det re-sorterer tilfeldig, sjekker om det er sortert, og hvis ikke gjentar seg. Og i teorien, basert på sannsynlighets Dette vil fullføre, men etter litt av en bit av tid. Det er ikke den mest effektive av algoritmer. Så noen spørsmål om de spesielle algoritmer eller noe relatert der også? Vel, la oss nå erte hverandre hva alle disse linjene er at jeg har vært tegning og hva jeg antar datamaskinen kan gjøre under panseret. Jeg vil hevde at alle disse tallene Jeg holder drawing-- de trenger å få lagret et sted i minnet. Vi vil bli kvitt denne fyren nå, også. Så en del av minnet i en computer-- så RAM DIMM er hva vi søkte etter i går, dual Inline Memory module-- ser slik ut. Og hver av disse små svarte brikker er et antall av bytes, typisk. Og så gullpinnene er som ledningene som kobler den til datamaskinen, og den grønne silisium styret er bare det som holder alt sammen. Så hva betyr dette egentlig? Hvis jeg slags tegne dette samme bildet, La oss anta at for enkelhet at dette DIMM, dual Inline Memory Module, er en gigabyte RAM, en gigabyte minne, som er hvor mange byte totalt? En gigabyte er hvor mange byte? Mer enn det. 1124 er kilo, 1000. Mega er millioner. Giga er en milliard. Er jeg lyver? Kan vi selv lese etiketten? Dette er faktisk 128 gigabyte, det er så mye mer. Men vi skal late som dette er bare én gigabyte. Så det betyr at det er en milliard byte minne tilgjengelig for meg eller 8 milliarder biter, men vi skal å snakke i form av bytes nå, går videre. Så hva det betyr er at dette er en byte, er dette en annen byte, Dette er en annen byte, og hvis vi virkelig ønsket å være konkret vil vi måtte tegne en milliard små firkanter. Men hva betyr det? Vel, la meg bare zoome i på dette bildet. Hvis jeg har noe som ser som dette nå, det er fire byte. Og så jeg kunne sette fire tall her. En to tre fire. Eller jeg kunne sette fire bokstaver eller symboler. "Hei!" kunne gå rett der, fordi hver av bokstavene, vi diskutert tidligere, kan være representert med åtte biter eller ASCII eller en byte. Så med andre ord, kan du sette 8 milliarder ting inni av dette en stokk med minne. Nå hva betyr det å sette ting tilbake til rygg mot rygg i minnet som dette? Dette er hva en programmerer vil kalle en "array". I et dataprogram, ikke du tror om det underliggende metall, per se. Du bare tenke på deg selv som har tilgang til en milliard byte totalt, og du kan alt du vil med den. Men for enkelhets skyld det er generelt nyttig å holde minnet retten ved siden av hverandre som dette. Så hvis jeg zoome inn på dette-- fordi vi er sikkert ikke kommer å trekke en milliard små squares-- la oss anta at dette forumet representerer som stick minne nå. Og jeg vil bare trekke så mange som min markør ender opp med å gi meg her. Så nå har vi en pinne minne på brettet som har fått en, to, tre, fire, fem, seks, en, to, tre, fire, fem, seks, seven-- så 42 byte minne på skjermen total. Takk skal du ha. Ja, det gjorde min regning rett. Så 42 byte minne her. Så hva betyr dette egentlig? Vel, en dataprogrammerer ville faktisk generelt tenk på dette minnet som adresserbare. Med andre ord, hver og en av disse steder i minnet, i maskinvare, har en unik adresse. Det er ikke så komplisert som en Brattle Square, Cambridge, Mass., 02138. I stedet, det er bare et tall. Dette er byte nummer null, er denne en, dette er to, dette er tre, og dette er 41. Vent litt. Jeg trodde jeg sa 42 for et øyeblikk siden. Jeg begynte å telle på null, så det er faktisk riktig. Nå har vi ikke trenger å faktisk trekke det som et rutenett, og hvis du tegner det som et rutenett Jeg tror ting faktisk få litt misvisende. Hva en programmerer ville, i hans eller hennes eget sinn, vanligvis tenker på dette minne som er akkurat som en tape, som et stykke maskeringstape som bare fortsetter og fortsetter for alltid eller til du går tom for minne. Slik at en mer vanlig måte å trekke og bare tenke på minne ville være at dette er byte null, en, to, tre, og deretter dot, dot, dot. Og du har 42 slike bytes totalt, selv om fysisk det kan faktisk være noe mer som dette. Så hvis du nå tenker på minne som dette, akkurat som en tape, Dette er hva en programmerer på nytt vil kalle en rekke minne. Og når du ønsker å faktisk lagre noe i datamaskinens minne, du vanligvis gjør store ting back-to-back to back-to-back. Så vi har snakket om tall. Og når jeg ønsket å løse problemer som fire, én, tre, to, selv om jeg var bare tegning bare tall fire, én, tre, to på bordet, ville datamaskinen virkelig har dette oppsettet i minnet. Og hva ville være ved siden av to i datamaskinens minne? Vel, det er ikke noe svar på det. Vi vet egentlig ikke. Og så lenge Maskinen virker ikke trenger det, det trenger ikke å bry seg hva som er neste til tallene den gjør seg om. Og da jeg sa tidligere at en datamaskin kan bare se på én adresse om gangen, dette er slags hvorfor. Ikke ulikt en rekord spiller og et lesehode bare å kunne se på en viss groove i en fysisk gamle skolen rekord om gangen, tilsvar kan en datamaskin takket til sin CPU og dens Intel instruksjonssett, blant hvis instruksjon blir lest fra minnet eller lagre til memory-- en Datamaskinen kan bare se på ett sted i en tid-- noen ganger en kombinasjon av dem, men egentlig bare ett sted om gangen. Så når vi gjorde disse ulike algoritmer, Jeg er ikke bare å skrive i en vacuum-- fire, én, tre, to. Disse tallene faktisk tilhører et eller annet sted fysisk minne. Så det er bitte liten transistorer eller annen form av elektronikk under den hette lagre disse verdiene. Og totalt, hvor mange biter er involvert akkurat nå, bare for å være klar? Så dette er fire byte, eller nå er det 32 ​​biter totalt. Så det er faktisk 32 nuller og de komponere disse fire tingene. Det er enda mer over her, men igjen vi ikke bryr seg om det. Så nå la oss be en annen spørsmålet ved hjelp av minne, fordi at på slutten i dag er i varians. Uansett hva vi kan gjøre med maskinen, på slutten av dagen maskinvaren er fremdeles samme under panseret. Hvordan skulle jeg lagre et ord her inne? Vel, et ord i en datamaskin som "Hei!" ville bli lagret akkurat som dette. Og hvis du ønsket en lengre ord, kan du bare skrive det og si noe som "Hei" og butikk som her. Og så her også, dette contiguousness er faktisk en fordel, fordi en datamaskin kan bare leses fra høyre mot venstre. Men her er et spørsmål. I sammenheng med dette ordet, h-e-l-l-o, utropstegn, hvordan kan datamaskinen vet hvor ord begynner og hvor ordet slutter? I sammenheng med tall, hvordan gjør datamaskinen vet hvor lang sekvens av tallene er eller hvor den starter? Vel, det viser out-- og vi vil ikke gå for mye inn i dette nivået av detail-- datamaskiner flytte ting rundt i minne bokstavelig ved hjelp av disse adressene. Så i en datamaskin, hvis du er skrive kode for å lagre ting som ord, hva du er egentlig gjør er å skrive uttrykk som husker hvor i datamaskinens minne disse ordene er. Så la meg gjøre en veldig, veldig enkelt eksempel. Jeg kommer til å gå videre og åpne opp en enkel tekstprogram, og jeg kommer til å skape en fil som heter hello.c. Mesteparten av denne informasjonen vi vil ikke gå inn i stor detalj, men jeg kommer til å skrive et program i den samme språk, C. Dette er langt mer skremmende, Jeg vil hevde, enn Scratch, men det er svært like i ånden. Faktisk er dette krøllete braces-- du kan slags tenke på hva jeg nettopp gjorde som dette. La oss gjøre dette, faktisk. Når grønne flagget klikket, gjør følgende. Jeg ønsker å skrive ut "hei." Så dette er nå pseudokode. Jeg er litt uskarphet linjene. I C, dette språket jeg snakker om, denne linjen print hallo faktisk blir "printf" med noen parenteser og et semikolon. Men det er nøyaktig samme idé. Og dette svært brukervennlig "Når grønne flagget klikket" blir den mye mer uforståelige "int main ugyldig." Og dette har virkelig ingen kartlegging, så jeg skal bare ignorere det. Men klammeparentes er som buede brikkene som dette. Så du kan slags gjette. Selv om du aldri har programmert før, hva betyr dette programmet sannsynligvis gjøre? Trolig skriver hallo med et utropstegn. Så la oss prøve det. Jeg kommer til å redde den. Og dette er, igjen, en veldig old school miljø. Jeg kan ikke klikke, jeg kan ikke dra. Jeg må skrive kommandoer. Så jeg ønsker å kjøre mitt program, så Jeg kan gjøre dette, som hello.c. Det er filen jeg kjørte. Men vent, jeg mangler et trinn. Hva gjorde vi si er en nødvendig trinn for et språk som C? Jeg har nettopp skrevet kilde kode, men hva trenger jeg? Ja, jeg trenger en kompilator. Så på min Mac her, jeg har en Programmet heter GCC, GNU C-kompilator, som tillater meg å gjøre dette-- turn min kildekoden til, vil vi kaller det, maskinkode. Og jeg kan se det, igjen, som følger, disse er nuller og enere jeg bare laget fra min kildekoden, alle de nuller og enere. Og hvis jeg vil kjøre min program-- det skjer å bli kalt a.out for historiske reasons-- "hei." Jeg kan kjøre den på nytt. Hallo hallo hallo. Og det ser ut til å virke. Men det betyr at et sted i min maskinens minne er ordene h-e-l-l-o, utropstegn. Og det viser seg, akkurat som en side, hva en datamaskin ville vanligvis gjøre slik at den vet der ting begynner og end-- det er kommer til å sette et spesielt symbol her. Og konvensjonen er å sette nummeret null ved slutten av et ord slik at du vet hvor det faktisk ender, slik at du ikke holde å skrive ut mer og mer tegn enn du faktisk har tenkt. Men takeaway her, selv selv om dette er ganske uforståelige, er at det er slutt forholdsvis enkel. Du fikk liksom en tape, en blank plass hvor du kan skrive brev. Du bare må ha en spesielt symbol, som vilkårlig tallet null, for å sette på slutten av dine ord slik at datamaskinen vet, åh, jeg skal slutte å skrive ut etter Jeg ser utropstegnet. Fordi den neste tingen der er en ASCII-verdi på null, eller nulltegnet så noen vil kalle det. Men det er litt av et problem her, og la oss gå tilbake til tall for et øyeblikk. Anta at jeg gjør det, faktisk, har en rekke tall, og anta at Programmet jeg skriver er som en karakterboken for en lærer og lærere i klasserommet. Og dette programmet gjør ham eller henne å skrive i elevenes score på spørrekonkurranser. Og anta at studenten får 100 på deres første quiz, kanskje som en 80 på den neste, deretter en 75, deretter en 90 på den fjerde prøven. Så på dette punktet i historien, matrisen er av størrelse fire. Det er absolutt mer minne i datamaskin, men matrisen, så å si, er av størrelse fire. Anta nå at læreren ønsker å tildele en femte quiz til klassen. Vel, en av de tingene han eller hun blir nødt til å gjøre er nå lagre en ekstra verdi her. Men hvis matrisen læreren har laget i dette programmet er av størrelse for, en av problemet med en matrise som er du kan ikke bare fortsette å legge til minne. For hva hvis en annen del av Programmet har ordet "hei" rett der? Med andre ord, kan min hukommelse være brukes til noe i et program. Og hvis på forhånd jeg skrev inn, hei, Jeg ønsker å legge inn fire quiz score, de kan gå her og her. Og hvis du plutselig ombestemmer deg senere og si at jeg vil ha en femte quiz poengsum, kan du ikke bare sette den hvor du vil, fordi hva om dette hukommelse blir brukt for noe else-- noen andre program eller en annen funksjon i programmet at du kjører? Så du må tenke på forhånd hvordan du ønsker å lagre dine data, fordi nå har du malt selv inn i en digital hjørne. Så en lærer kan i stedet si når du skriver et program å lagre hans eller hennes karakterer, vet du hva? Jeg kommer til å be om, når du skriver mitt program, at jeg vil ha null, en, to, tre, fire, fem, seks, åtte karakterer totalt. Så en, to, tre, fire, fem, seks, sju, åtte. Læreren kan bare over bevilge minne når du skriver hans eller hennes program og si, vet du hva? Jeg kommer aldri til å tildele mer enn åtte quizer i et semester. Det er bare tull. Jeg vil aldri fordele det. Slik at denne måten han eller hun har fleksibilitet til å lagre student score, som 75, 90, og kanskje en ekstra der studenten fikk ekstra kreditt, 105. Men hvis læreren aldri bruker disse tre områder, det er en intuitiv takeaway her. Han eller hun er bare sløse plass. Så med andre ord, det er denne felles kompromisset i programmering der du enten kan tildele akkurat så mye minne som du vil, oppsiden av dem er at du er super efficient-- du ikke er bortkastet på alle-- men ulempen som er hva hvis du ombestemmer deg når bruke programmet som du ønsker å lagre mer data enn du opprinnelig hadde tenkt. Så kanskje løsningen er, da, skrive programmene dine på en slik måte at de bruker mer minne enn de faktisk trenger. På denne måten kommer du ikke å kjøre inn det problemet, men du blir sløsing. Og jo mer minne programmet bruker, som vi diskuterte i går, jo mindre minne som er tilgjengelig for andre programmer, jo raskere datamaskinen kan bremse ned på grunn av virtuelt minne. Og så den ideelle løsningen kan være det? Under-allokering virker dårlig. Over-allokering virker dårlig. Så hva kan være en bedre løsning? Reallocating. Være mer dynamisk. Ikke tving deg selv til å velge en priori, i begynnelsen, hva du ønsker. Og absolutt ikke over-tildele, så dere ikke være bortkastet. Og så for å oppnå dette målet, vi må kaste denne datastrukturen, så å si, bort. Og så hva en programmerer vil vanligvis bruke er noe som kalles ikke en matrise men en lenket liste. Med andre ord, vil han eller hun vil begynner å tenke på deres minne som en slags form som de kan trekke på følgende måte. Hvis jeg ønsker å lagre ett nummer i en program-- så det er september Jeg har gitt mine studenter en quiz; Jeg ønsker å lagre studentenes første quiz, og de fikk en 100 på det-- jeg kommer til å spørre min datamaskin, ved hjelp av det programmet jeg har skrevet, for en del av minnet. Og jeg kommer til å lagre nummer 100 i den, og det er det. Så noen uker senere når jeg får mitt andre quiz, og det er på tide å skrive i at 90%, jeg kommer å spørre datamaskinen, hei, datamaskin, kan jeg ha en annen del av minne? Det kommer til å gi meg denne tom mengde minne. Jeg kommer til å sette i nummer 90, men i mitt program eller annen måte eller other-- og vi vil ikke bekymre syntaksen for dette-- jeg trenger å liksom kjeden disse tingene sammen. Og jeg vil kjede dem sammen med det ser ut som en pil her. Den tredje quiz som kommer opp, Jeg kommer til å si hei, datamaskin, gi meg en annen del av minnet. Og jeg kommer til å legge ned uansett hva det var, i likhet med 75, og jeg må kjede dette sammen nå liksom. Fjerde quiz kommer sammen, og kanskje det er mot slutten av semesteret. Og ved det punktet mitt program kan være å bruke minne over alt, over fysisk. Og så bare for morro skyld, jeg er kommer til å trekke dette fram quiz-- jeg glemmer hva det var; jeg tror kanskje en 80 eller something-- måte over her. Men det er greit, fordi billedlig Jeg kommer til å trekke denne linjen. Med andre ord, i virkeligheten, i datamaskinens maskinvare, det første resultatet kanskje ende opp her fordi det er helt i starten av semesteret. Den neste kan ende opp her fordi en bit av tid har gått og programmet fortsetter å kjøre. Den neste score, som var 75, kan være over her. Og det siste resultatet kan være 80, som er over her. Så i virkeligheten, fysisk, dette kan være hva datamaskinens minne ser ut. Men dette er ikke en nyttig mental paradigme for en dataprogrammerer. Hvorfor skulle du bry deg der pokker dataene er å ende opp? Du ønsker bare å lagre data. Dette er typen som vår diskusjon tidligere for å trekke kuben. Hvorfor bryr du deg hva vinkelen er av kuben og hvordan du må slå for å tegne det? Du vil bare ha en kube. På samme måte her, du bare ønsker å karakterboken. Du ønsker bare å tenke på dette som en liste med tall. Hvem bryr seg hvordan det er implementert i maskinvare? Så abstraksjon nå er dette bildet her. Dette er en lenket liste, som en programmerer vil kalle det, i den grad du har en listen, åpenbart med tall. Men det er knyttet billedlig ved hjelp av pilene, og alle disse pilene are-- under panseret, hvis du er nysgjerrig, minne om at vår fysiske maskinvaren har adresser null, en, to, tre, fire. Alle disse pilene er er som et kart eller retninger, der hvis 90 er-- nå Jeg fikk til å telle. Zero, en, to, tre, fire, fem, seks, syv. Det ser ut som 90 er på minneadresse nummer syv. Alle disse pilene er er som en liten papirlapp som gir anvisninger til program som sier følger dette kartet å komme til stedet sju. Og der vil du finne studentens andre quiz poengsum. I mellomtiden 75-- hvis jeg fortsetter dette, Dette er syv, åtte, ni, ti, elleve, tolv, 13, 14, 15. Denne andre pilen bare representerer et kart til minneområde 15. Men igjen, programmerer vanligvis gjør ikke bryr seg om dette detaljnivået. Og i de fleste hver programmering språket i dag, programmerer vil ikke engang vet hvor i minnet Disse tallene faktisk er. Alt han eller hun har å bry seg om er at de er en eller annen måte forbundet med hverandre i en datastruktur som dette. Men det viser seg ikke å bli for teknisk. Men bare fordi vi kan kanskje råd til å ha denne diskusjonen her, anta at vi besøker dette problemet her av en matrise. La oss se om vi angrer kommer her. Dette er 100, 90, 75, og 80. La meg kort hevde dette. Dette er en matrise, og igjen, fremtredende karakteristikk av en matrise er at alle dataene er tilbake til rygg mot rygg i memory-- bokstavelig én byte eller kanskje fire bytes, noen fast antall bytes bort. I en lenket liste, som vi kan trekke som dette, under panseret som vet hvor de greiene er? Det trenger ikke engang trenger å flyte som dette. Noen data kan være Tilbake til venstre opp der. Du vet ikke engang. Og så med en rekke, har du en funksjon som kalles tilfeldig tilgang. Og hva random access midler er at datamaskinen kan hoppe umiddelbart til hvilket som helst sted i en matrise. Hvorfor? Fordi datamaskinen vet at den første plasseringen er null, en, to og tre. Og så hvis du ønsker å gå fra dette element til det neste element, du bokstavelig talt, i datamaskin sinn, bare legge en. Hvis du vil gå til det tredje elementet, bare legge one-- neste element, bare legge en. Men i denne versjon av historien, antar datamaskinen er for tiden på jakt ved eller arbeider med nummer 100. Hvordan får du til neste karakter i karakterboken? Du må ta syv trinn, noe som er vilkårlig. For å komme til den neste, må du ta ytterligere åtte trinn for å komme til 15. Med andre ord, det er ikke en konstant gap mellom tallene, og slik at det bare tar datamaskinen mer tid er poenget. Datamaskinen må lete gjennom minnet for for å finne det du leter etter. Så mens en matrise har en tendens til å være en rask data structure-- fordi du kan bokstavelig talt bare gjøre enkel aritmetikk og komme dit du vil ved å legge til en, for instance-- en lenket liste, du ofre den funksjonen. Du kan ikke bare gå fra første til andre til tredje til fjerde plass. Du må følge kartet. Du må ta flere skritt for å komme til de verdier som ville synes å være å tilsette en kostnad. Så vi betaler en pris, men det som var funksjonen som Dan var søker her? Hva gjør en lenket liste tilsynelatende tillate oss å gjøre, som var opprinnelsen til denne historien? Nøyaktig. En dynamisk størrelse til det. Vi kan legge til denne listen. Vi kan også krympe på listen, så at vi bare bruker så mye minne som vi faktisk vil og så vi er aldri over-allokering. Nå bare å være virkelig nit-kresen, det er en skjult kostnad. Så du bør ikke bare la meg overbevise du at dette er en overbevisende kompromisset. Det er en annen skjulte kostnader her. Den fordel, for å være klar, er at vi får dynamikk. Hvis jeg vil ha et annet element, kan jeg bare tegne det og sette et tall på det. Og så kan jeg koble den med et bilde her, mens over her, igjen, hvis jeg har malt meg selv inn i et hjørne, hvis noe annet er allerede bruker minnet her, jeg er ute av lykken. Jeg har malt meg inn i hjørnet. Men hva er den skjulte koste i dette bildet? Det er ikke bare mengden av tiden det tar å gå herfra til her, som er sju trinn, deretter åtte trinn, som er mer enn en. Hva er en annen skjulte kostnader? Ikke bare tid. Ytterligere informasjon er nødvendig for å oppnå dette bildet. Ja, det kartet, de små utklipp av papir, som jeg holder beskriver dem som. Disse arrows-- de er ikke gratis. En computer-- du vite hva en datamaskin har. Den har nuller og enere. Hvis du ønsker å representere en pil eller et kart eller et tall, trenger du noe minne. Så den andre prisen du betale for en lenket liste, en felles informatikk ressurs, er også plass. Og faktisk så, så ofte, blant de avveininger i utformingen av software engineering systemer er tid og space-- er to av ingrediensene, to av de mest kostbare ingredienser. Dette koster meg mer tid fordi jeg må følge dette kartet, men det er også koster meg mer plass fordi jeg må holde dette kartet rundt. Så det håp, som vi har på en måte diskutert i løpet av i går og i dag, er at fordelene vil oppveie kostnadene. Men det er ingen åpenbare løsningen her. Kanskje det er better-- a la rask og skitne, som Kareem slått earlier-- å kaste minne på problemet. Bare kjøpe mer minne, tror mindre hardt om å løse problemet, og løse det på en enklere måte. Og faktisk tidligere, da vi snakket om avveininger, Det var ikke plass i maskinen og tid. Det var utvikler tid, noe er enda en annen ressurs. Så igjen, det er denne balansegangen prøver å bestemme hvilke av disse tingene er du villig til å bruke? Som er den minst kostbare? Som gir bedre resultater? Ja? Faktisk. I dette tilfellet, hvis du er representerer tallene i maps-- disse kalles på mange språk "pekere" eller "adresser" - det er dobbelt plass. Det trenger ikke være så ille som dobbel om akkurat nå er vi bare lagring av numre. Anta at vi lagret pasientjournaler i en hospital-- så Pierson navn, telefonnumre, personnummer, lege historie. Denne boksen kan være mye, mye større, i hvilket tilfelle en bitte liten peker, adressen neste element-- det er ikke en stor avtale. Det er slik en utkant koster det spiller ingen rolle. Men i dette tilfellet, ja, det er en dobling. Godt spørsmål. La oss snakke om tid en Litt mer konkret. Hva er kjøretiden for å søke denne listen? Anta at jeg ønsket å søke gjennom alle elevenes karakterer, og det er n karakterer i dette datastruktur. Også her kan vi låne vokabular av tidligere. Dette er en lineær datastruktur. Big O n er hva som kreves for å få til enden av denne datastruktur, whereas-- og vi har ikke sett dette before-- en rekke gir deg det som kalles konstant tid, noe som betyr at ett trinn eller to trinn, eller 10 steps-- spiller ingen rolle. Det er et fast antall. Det har ingenting å gjøre med størrelsen av matrisen. Og grunnen til det, igjen, er tilfeldig tilgang. Datamaskinen kan bare umiddelbart hopp til et annet sted, fordi de er alle like avstand fra alt annet. Det er ingen tenkning involvert. Greit. Så hvis jeg kan, la meg prøve å male to siste bildene. En veldig vanlig en kjent som en hash table. Så for å motivere denne diskusjonen, la meg tenke på hvordan du gjør dette. Så hva med denne? Anta at problemet vi ønsker å løse nå gjennomfører i et dictionary-- så en hel haug med engelske ord eller hva. Og målet er å være i stand til å svare spørsmål i skjemaet er dette et ord? Så du ønsker å implementere en stavekontroll, bare som en fysisk ordbok som du kan se ting opp i. Anta at jeg skulle gjøre dette med en matrise. Jeg kunne gjøre dette. Og antar at ordene er eple og banan og honningmelon. Og jeg kan ikke tenke på frukt som begynner med d, så vi er bare kommer til å ha tre frukter. Så dette er en matrise, og vi er lagring av alle disse ordene i denne ordboken som en matrise. Spørsmålet er da hvordan ellers kan du lagre denne informasjonen? Vel, jeg slags juks her, fordi hver av disse bokstavene i ordet er virkelig en person byte. Så hvis jeg virkelig ønsket å være nit-kresen, skal jeg virkelig være å dele dette opp i mye mindre biter av minne, og vi kunne gjøre akkurat det. Men vi kommer til å kjøre inn det samme problemet som før. Hva om, som Merriam Webster eller Oxford gjør hver year-- de legger ord til dictionary-- gjør vi ikke nødvendigvis ønsker å male oss selv inn i et hjørne med en rekke? Så i stedet, kanskje en smartere tilnærming er å sette eple i en egen node eller boks, som vi ville si, banan, og så her har vi honningmelon. Og vi streng disse tingene sammen. Så dette er tabellen, og Dette er lenket liste. Hvis du ikke helt kan se, er det bare sier "array", og dette sier "-liste." Så vi har det samme eksakte spørsmål som før, hvor vi har nå dynamikk i vår lenket liste. Men vi har en ganske treg ordbok. Anta at jeg ønsker å slå opp et ord. Det kan ta meg stor O av n trinn, fordi ordet makt være plassert helt ved enden av listen, som honningmelon. Og det viser seg at i programmering, sortere den hellige gral av data strukturer, er noe som gir deg konstant tid som en matrise men som likevel gir deg dynamikk. Så kan vi ha det beste fra begge verdener? Og ja, det er noe kalt hash table som lar deg gjøre akkurat det, om enn ca. En hash table er en mer avansert datastruktur som vi kan tenke på som Kombinasjonen av en array-- og jeg kommer til å trekke det som dette-- og lenkede lister at jeg skal tegne som dette over her. Og måten denne saken verkene er som følger. Hvis dette now-- hasj table-- er mitt tredje datastrukturen, og jeg ønsker å lagre ord i dette, gjør jeg ikke ønsker å bare lagre alle ord rygg mot rygg mot rygg mot rygg. Jeg ønsker å utnytte noen opplysning om ordene som vil la meg å få det der det er raskere. Så gitt ord eple og banan og honningmelon, Jeg valgte bevisst disse ordene. Hvorfor? Hva er liksom fundamentalt annerledes om de tre? Hva er det åpenbare? De starter med forskjellige bokstaver. Så vet du hva? I stedet for å sette alle mine ord i det samme bøtte, så å si, som i en stor liste, hvorfor ikke Jeg i det minste prøve en optimalisering og gjøre mine lister 1/26 så lenge. En overbevisende optimalisering kan være grunnen ikke I-- når du setter inn et ord inn i denne datastrukturen, inn i datamaskinens minne, hvorfor jeg ikke sette alle 'A' ord her, alle de "b" ord her, og alle 'c' ord her? Så dette ender opp med å sette et eple her, banan her, cantaloupe her, og så videre. Og hvis jeg har en ekstra Ordet like-- hva som er en annen? Apple, banan, pære. Alle som tenker på en frukt som starter med a, b eller c? Blueberry-- perfekt. Det kommer til å ende opp her. Og så vi synes å ha en marginalt bedre løsning, fordi nå hvis jeg vil for å søke etter eple, jeg first-- jeg ikke bare dykke inn i mitt datastruktur. Jeg vet ikke dykke inn i datamaskinens minne. Første gang jeg ser på den første bokstaven. Og dette er hva en datamaskin vitenskapsmann ville si. Du hasj inn i datastrukturen. Du tar dine innspill, som i dette tilfellet er et ord som eple. Du analysere den, ser på den første bokstav i dette tilfellet dermed hashing det. Hashing er et generelt begrep der du tar noe som input og du produserer noen utgang. Og utgang i at Saken er plasseringen du vil søke etter, den første beliggenhet, andre plassering, tredje. Så inngangen er eple, utgangen er først. Inngangen er banan, den Utgangen skal være andre. Inngangen er cantaloupe, utdataene skal være tredje. Inngangen er blåbær, den utgang bør igjen være andre. Og det er det som hjelper deg å ta snarveier gjennom hukommelsen For å få til ord eller data på en mer effektiv måte. Nå kutter ned vår tid potensielt med så mye som én av 26, fordi hvis du anta at du har så mange "en" ord som "z" ord som "Q" ord, som er egentlig ikke realistic-- du kommer til å ha skew tvers enkelte bokstavene i alphabet-- men dette ville være en inkrementell tilnærming som tillater du komme til ord mye raskere. Og i virkeligheten, en sofistikert program, Googles av verden, den Facebooks av world-- de ville bruke en hash table for en rekke forskjellige formål. Men de ville ikke være så naiv som å bare se på den første bokstaven i eple eller banan eller pære eller honningmelon, fordi som du kan se disse lister kan fortsatt få lang. Og så dette kan fortsatt være sort av linear-- så slags langsom, som med stor O av n som vi diskuterte tidligere. Så hva en virkelig god hash table vil do-- det vil ha en mye større utvalg. Og det vil bruke en mye mer sofistikert hashing funksjon, slik at det ikke bare se på "a". Kanskje den ser på "a-p-p-l-e" og liksom konverterer disse fem bokstaver i stedet der Apple bør lagres. Vi er bare naivt å bruke bokstaven 'a' alene, det er fordi fin og enkel. Men en hash table, i Til slutt kan du tror som en kombinasjon av en matrise, hver av hvilke har en lenket liste som ideelt sett bør være så kort som mulig. Og dette er ikke en åpenbar løsning. Faktisk mye av den fine tuning som går på under panseret når implementere slike sofistikerte datastrukturer er hva som er riktig Lengden av matrisen? Hva er riktig hash-funksjon? Hvordan du lagre ting i minnet? Men skjønner hvor raskt denne typen diskusjon eskalerte, enten så langt at det er slag av over hodet på dette punktet, hvilken er greit. Men vi startet, husker, med virkelig noe lav-nivå og elektronisk. Og så dette igjen er dette Temaet for abstraksjon, der en gang du begynner å ta for innvilget, OK, jeg har it-- det er fysisk minne, OK, fikk den, hver fysisk plassering har en adresse, OK, jeg fikk den, kan jeg representere disse adressene som arrows-- kan du raskt begynne å ha mer sofistikerte samtaler som til slutt ser ut til å bli slik at vi å løse problemer som søker og sortering mer effektivt. Og vær trygg, også-- fordi jeg tror dette er den dypeste vi har gått inn i noen av disse CS temaene proper-- vi har gjort på en og en halv dag på dette peke på hva du kan vanligvis gjøre over I løpet av åtte uker i et semester. Eventuelle spørsmål om disse? Nei? Greit. Vel, hvorfor ikke vi stoppe der, starte lunsj et par minutter for tidlig, fortsette i omtrent en time? Og jeg skal dvele for litt med spørsmål. Så jeg kommer til å gå ta et par samtaler hvis det er OK. Jeg skal skru på litt musikk i mellomtiden, men lunsj bør være rundt hjørnet.