DAVID MALAN: Okay. Vi er tilbage. Så i dette segment om programmering, hvad Jeg troede, vi ville gøre, er en blanding af ting. One, gøre en lille smule af noget hands-on, omend bruge en mere legende programmering environment-- en, der er demonstrative af præcis den slags ideer Vi har talt om, men lidt mere formelt. To, ser på nogle af de mere tekniske måder at en programmør faktisk ville løse problemer som den søgende problem at vi kiggede på før og også en mere grundlæggende interessant problem sortering. 

Vi har lige antaget fra Hent gå at der telefonbog blev sorteret, men det alene er faktisk slags en hård problem med mange forskellige måder at løse det. Så vi vil bruge disse som en klasse af problemer repræsentant for ting, kan løses generelt. Og så vil vi tale om i nogle detaljer, hvad kaldes data structures-- amatør måder som hægtede lister og hash tabeller og træer, en programmør ville faktisk bruge og generelt bruge på en tavle til at male et billede af, hvad han eller hun forestiller sig for at gennemføre nogle stykke software. 

Så lad os gøre det hands-on del først. Så bare få dine hænder beskidte med en miljø kaldet scratch.mit.edu. Dette er et værktøj, vi bruger i vores bachelor klasse. Selvom det er designet for aldre 12 og op, vi bruge det til op del af denne ganske lidt da det er en dejlig, sjov grafisk måde at lære på lidt noget om programmering. Så hovedet til denne webadresse, hvor du bør se en side helt som denne, og gå videre og klik Deltag Scratch øverst til højre og vælge et brugernavn og en adgangskode og i sidste ende få dig en account-- scratch.mit.edu. Jeg troede, jeg ville bruge dette som en mulighed første til at vise dette. Et spørgsmål kom op i pausen om, hvad koden ser faktisk gerne. Og vi talte i pausen om C, i particular-- især en lavere niveau i en ældre sprog. Og jeg gjorde bare en hurtig Google-søgning for at finde C-kode for binær søgning, den algoritme, vi bruges til at søge at telefonbogen tidligere. Denne særlige eksempel, selvfølgelig, søger ikke en telefonbog. Det bare søger en hel masse numre i computerens hukommelse. Men hvis du gerne vil bare få en visuel fornemmelse af, hvad en egentlig programmering sprog ligner, det ser lidt noget som dette. Så det er omkring 20-plus, 30 eller deromkring linjer kode, men samtalen vi havde løbet pause handlede om, hvordan det rent faktisk bliver forvandlet til nuller og ettaller og hvis du ikke bare kan vende det behandle og gå fra nuller og ettaller tilbage til kode. 

Desværre er processen er så transformative at det er meget lettere sagt end gjort. Jeg gik videre og faktisk viste dette program, binær søgning, ind nuller og ettaller i form af en program kaldet The Compiler, at jeg tilfældigvis har her lige på min Mac. Og hvis man ser på skærmen her, der fokuserer specifikt på disse midterste seks kolonner kun, vil du kun se nuller og ettaller. Og det er de nuller og ettaller, der komponere præcis det søgende program. 

Og så hver bid af fem bit, hver byte af nuller og ettaller her, repræsenterer nogle instruktion typisk indersiden af ​​en computer. Og i virkeligheden, hvis du har hørt markedsføring slogan "Intel inside" - det, selvfølgelig betyder bare du har en Intel CPU eller hjerne inde i computeren. Og hvad det betyder at være en CPU er at du har en instruktionssæt, så at sige. 

Hver CPU i verden, mange af dem lavet af Intel i disse dage, forstår et endeligt antal instruktioner. Og disse instrukser er så lavt niveau som tilføje disse to tal sammen, formere disse to tal sammen, flytte dette stykke data herfra til her i hukommelsen, gem denne information herfra til her i hukommelsen, og så forth-- så meget, meget lavt niveau, næsten elektroniske detaljer. Men med de matematiske operationer koblede med det, vi diskuterede tidligere, repræsentationen af ​​data som nuller og ettaller, kan du opbygger alt at en computer kan gøre i dag, hvad enten det tekstuelle, grafisk, musical, for ellers. 

Så det er meget let at komme tabt i ukrudt af hurtigt. Og der er en masse syntaktiske udfordringer hvorved hvis du laver den enkleste, dummeste af stavefejl ingen af ​​programmet vil arbejde for eksklusionen. Og så i stedet for at bruge en sprog som C i morges, Jeg troede det ville være sjovere at rent faktisk at gøre noget mere visuel, hvilket mens designet til børn er faktisk en perfekt manifestation af en egentlig programmering language-- bare sker for at bruge billeder i stedet for tekst at repræsentere disse idéer. 

Så når du rent faktisk har en konto på scratch.mit.edu, Klik på knappen Opret øverst til venstre på sitet. Og du skal se et miljø som den jeg er ved at se på min skærm her. Og vi vil bruge bare en lille smule lidt tid at spille her. Lad os se, om vi ikke alle kan løse nogle problemer sammen på følgende måde. 

Så hvad du vil se i denne environment-- og faktisk bare lade mig pause. Er der nogen der ikke her? Ikke her? OKAY. Så lad mig påpege et par karakteristika dette miljø. 

Så øverst til venstre på skærmen, vi har Scratch etape, så at sige. Scratch er ikke kun navnet af dette programmeringssprog; det er også navnet på den kat, der du ser som standard der i orange. Han er på en scene, så meget gerne jeg beskrev skildpadden tidligere som værende i en rektangulære whiteboard miljø. Denne kattens verden er begrænset udelukkende til dette rektangel op toppen er der. 

I mellemtiden, til højre side her, det er bare et scripts område, en blank tavle, hvis du vil. Det er her, vi kommer til at skrive vores programmer på blot et øjeblik. Og de byggesten, at vi bruge til at skrive dette program-- puslespillet stykker, hvis du will-- er dem lige her i midten, og de er kategoriseret via funktion. Så, for eksempel, vil jeg gå videre og demonstrere mindst en af ​​disse. Jeg har tænkt mig at gå videre og klik Kontrol kategori op øverst. 

Så det er disse kategorier op toppen. Jeg har tænkt mig at klikke Control kategori. Snarere, jeg har tænkt mig at klikke på Begivenheder kategorien allerførste op øverst. Og hvis du gerne vil følge med selv som vi gør dette, er du helt velkommen til. Jeg har tænkt mig at klikke og trække dette første, ", når grønne flag klikkes." Og så jeg har tænkt mig at slippe det bare nogenlunde på toppen af ​​mine tomme tavler. 

Og hvad er rart om Scratch er, at denne brik, når sammenlåst med andre puslespil stykker, kommer til at gøre bogstaveligt hvad disse puslespilsbrikker sige at gøre. Så, for eksempel, Scratch er ret nu i midten af ​​hans verden. Jeg har tænkt mig at gå videre og vælge nu, lad os sige, Motion kategori, hvis du gerne vil gøre det same-- Motion kategori. Og nu opdager jeg har en hel bundt af puslespilsbrikker her at, igen, slags gør, hvad de siger. Og jeg har tænkt mig at gå videre og trække og drop farten blokken lige herovre. 

Og se, at så snart du får tæt på bunden af ​​den "grønne flag klikkede "knappen, varsel hvordan en hvid streg, som om det er næsten magnetisk, det ønsker at gå der. Bare lad gå, og det vil snap sammen og formerne vil matche. Og nu kan du måske næsten gætte, hvor vi skal hen med dette. 

Hvis man ser på Scratch stadium herover og se til toppen af ​​det, vil du se et rødt lys, en stoppe tegn, og et grønt flag. Og jeg har tænkt mig at gå videre og se mine screen-- for et øjeblik, hvis du kunne. Jeg har tænkt mig at klikke på grønt flag lige nu, og han flyttede, hvad der synes at være 10 trin eller 10 pixels, 10 prikker, på skærmen. 

Og så ikke så spændende, men lad mig foreslå uden selv at undervise dette, blot ved hjælp af egen din egen intuition-- lad mig foreslå, at du finde ud af at gøre Scratch gåtur lige ned fra scenen. Har ham gøre plads til den højre side af skærmen, hele vejen til højre. Lad mig give dig et øjeblik eller så at kæmpe med det. Du vil måske tage et kig på andre kategorier af blokke. Okay. Så bare for at opsummere, når vi har det grønne flag klikkede her og flytte 10 trin er kun instruktion, hver gang jeg klikke på den grønne flag, hvad sker der? Nå, der kører mit program. Så jeg kunne gøre dette måske 10 gange manuelt, men det føles lidt bit hackish, så at sige, hvorved jeg er ikke rigtig løse problemet. Jeg prøver bare igen og igen og igen og igen indtil jeg slags uheld opnå direktivet at jeg satte sig for at opnå tidligere. 

Men vi ved fra vores pseudokode tidligere, at der er dette begreb i programmering af looping, gør noget igen og igen. Og så jeg så, at en flok af jer nået for, hvad puslespilsbrik? Gentag indtil. Så vi kunne gøre noget ligesom gentag indtil. Og hvad gjorde du gentager indtil præcis? 

OKAY. Og lad mig gå med en, der er noget enklere for blot et øjeblik. Lad mig gå videre og gøre dette. Bemærk, at, som du kan have opdaget under kontrol, der er denne gentagelse blok, som ligner ikke det er så store. Der er ikke meget plads i mellem disse to gule linjer. Men som nogle af jer måske har bemærket, hvis du trækker og slipper, mærke til, hvordan den vokser til at fylde formen. 

Og du kan endda proppe mere. Det vil bare holde voksende, hvis du trækker og svæve over det. Og jeg ved ikke, hvad der er bedste her, så lad mig mindst gentages fem gange, for eksempel og derefter gå tilbage til scenen og klik på den grønne flag. Og nu mærke til det er ikke helt der. 

Nu nogle af jer foreslog, som Victoria vidste bare, gentag 10 gange. Og der generelt gør få ham hele vejen, men ville der ikke være en mere robust måde end vilkårligt regne ud hvor mange initiativer til at gøre? Hvad kan være en bedre blok end gentag 10 gange være? 

Ja, så hvorfor ikke gøre noget for evigt? Og lad mig flytte denne brik inde der og slippe af med denne ene. Bemærk nu, uanset hvor Scratch starter, han går til kanten. Og heldigvis MIT, der gør Scratch, bare sørger for, at han aldrig forsvinder helt. Du kan altid få fat i halen. 

Og bare intuitivt, hvorfor han holde bevægelse? Hvad sker der her? Han synes at være stoppet, men så hvis jeg afhente og træk han holder ønsker at gå derovre. Hvorfor det? Sandelig, en computer er bogstaveligt talt kommer til at gøre, hvad du fortæller det til at gøre. Så hvis du fortalte det tidligere gøre Følgende ting for evigt, flytte 10 trin, det kommer til at holde i gang og gå indtil jeg ramte den røde stopskilt og stoppe programmet helt. 

Så selvom du ikke gjorde gøre dette, hvordan kunne jeg gøre Scratch flytte hurtigere over skærmen? Flere trin, right? Så i stedet for at gøre 10 ad gangen, hvorfor vi ikke gå videre og ændre det at-- hvad ville du propose-- 50? Så nu vil jeg til at klikke på den grønne flag, og ja, han går rigtig hurtigt. 

Og det er selvfølgelig bare en manifestation af animation. Hvad er animation? Det er bare at vise dig den menneskelige en hel masse stillbilleder virkelig, virkelig, virkelig hurtig. Og så hvis vi bare at fortælle ham til at flytte flere trin, vi bare have den virkning, være at forandring, hvor han er på skærmen desto hurtigere per tidsenhed. 

Nu er den næste udfordring, som jeg foreslog var at have ham hoppe ud over kanten. Og uden at vide hvad puslespil stykker exist-- fordi det er fint hvis du ikke komme til etape af challenge-- hvad vil du gøre intuitivt? Hvordan ville vi have ham hoppe tilbage og frem, mellem venstre og højre? 

Ja. Så vi har brug for en eller anden form af tilstand, og vi synes at have betingede, så at tale, under Control kategori. Hvilke af disse blokke vi sikkert gerne? Ja, måske "hvis, da." Så bemærke, at blandt de gule blokke vi har her, er der denne "hvis" eller denne "hvis ellers" blok, der vil tillade os at træffe en beslutning til at gøre dette eller at gøre det. Og du kan endda reden dem at gøre flere ting. Eller hvis du ikke har gået her endnu, gå videre til Sensing kategori og-- lad os se om det er her. 

Så hvad blok kan være nyttige her at opdage, hvis han er fra scenen? Ja, se, at nogle af disse blokke kan parametriseret, så at sige. De kan slags tilpasset, ikke modsætning HTML i går med attributter, hvor disse attributter slags indstille opførslen af ​​et tag. Ligeledes her, kan jeg få fat i denne rørende blok og forandring og stille spørgsmålet, er du rører musen pointer som markøren eller er du rører kanten? 

Så lad mig gå ind og gøre det. Jeg har tænkt mig at zoome ud et øjeblik. Lad mig gribe denne brik her, denne brik dette, og jeg har tænkt mig at virvar dem op for et øjeblik. Jeg har tænkt mig at flytte denne, ændre dette til rørende kant, og jeg har tænkt mig at bevægelse gøre dette. Så her er nogle ingredienser. Jeg tror, ​​jeg har fået alt, hvad jeg ønsker. 

Vil nogen gerne foreslå, hvordan jeg kan forbinde disse måske top til bund for at løse problemet med Scratch flytte højre til venstre til højre til venstre til højre til venstre, hver tid bare hoppe ned fra væggen? Hvad ønsker jeg at gøre? Hvilken blok skal jeg oprette forbindelse til "Når grønne flag klikkede først"? 

OK, så lad os starte med "evigt." Hvad går inde næste? En anden. OK, flytte trin. Okay. Hvad så? Så så hvis. Og mærke, selvom det ser klemt sammen stramt, det vil bare vokse at udfylde. Det vil bare hoppe i, hvor jeg vil have det. 

Og hvad jeg sætte imellem if og derefter? Sandsynligvis ", hvis røre kant." Og varsel, igen, det er for stort for det, men det vil vokse til at udfylde. Og derefter dreje 15 grader? Hvor mange grader? Ja, så 180 vil spin mig hele vejen rundt. Så lad os se om jeg fik denne ret. Lad mig zoome ud. 

Lad mig trække Scratch op. Så han er lidt forvrænget nu, men det er fint. Hvordan kan jeg nulstille ham let? Jeg har tænkt mig at snyde lidt. Så jeg tilføje en anden blok, bare for at være klar. Jeg vil have ham til punkt 90 grader til højre som standard, så jeg bare at fortælle ham at gøre det programmeringsmæssigt. Og her går vi. Vi synes at have gjort det. Det er lidt underligt, fordi han gå op og ned. Lad os kalde det en fejl. Det er en fejl. En fejl er en fejl i et program, en logisk fejl, at jeg, menneskelige, lavet. Hvorfor skal han på hovedet? Vidste MIT skrue op eller gjorde jeg? 

Ja, jeg mener, det er ikke MIT fejl. De gav mig et puslespil brik der siger vende nogle antallet af grader. Og på Victoria forslag, Jeg vender 180 grader, der er den rigtige intuition. Men dreje 180 grader bogstaveligt betyder at dreje 180 grader, og det er ikke rigtig hvad jeg vil, tilsyneladende. Fordi han i det mindste er i dette todimensionale verden, så drejning der egentlig foregår at vende ham på hovedet. 

Jeg vil sandsynligvis at bruge, hvad blok stedet, baseret på, hvad du ser her? Hvordan kan vi løse dette? Ja, så vi kunne pege i den modsatte retning. Og faktisk selv det er ikke vil være nok, fordi vi kan kun hårdt kode at pege til venstre eller højre. 

Du ved, hvad vi kunne gøre? Det ser ud til vi har en bekvemmelighed blok her. Hvis jeg zoomer ind, se noget vi kan lide her? Så det ser ud som MIT har en abstraktion bygget i her. Denne blok synes at være ækvivalente som andre blokke, pluralis? 

Denne ene blok synes at være ækvivalente til hele denne trio af blokke at vi har her. Så det viser sig, kan jeg forenkle mit program ved at slippe af alt dette og bare sætte dette i her. Og nu er han stadig lidt buggy, og det er fint for nu. Vi vil overlade være. Men mit program er endnu enklere, og også dette ville være repræsentativ af et mål i programming-- er at ideelt set gøre din kode som enkel, så kompakt som muligt, mens den stadig er som læsbare som muligt. Du ønsker ikke at gøre det så kortfattet at det er svært at forstå. 

Men bemærk jeg har erstattet tre blokke med en, og det er velsagtens en god ting. Jeg har indvindes væk begrebet kontrollere, om du er på kanten med kun en blok. Nu kan vi have det sjovt med dette, faktisk. Dette tilføjer ikke så meget intellektuel værdi, men legende værdi. Jeg har tænkt mig at gå videre og få fat i denne lyd her. Så lad mig gå videre, og lad mig stoppe programmet et øjeblik. Jeg har tænkt mig at optage det følgende, giver adgang til min mikrofon. 

Nu sker det. Av. Lad os prøve det igen. Nu sker det. OK, indspillede jeg den forkerte ting. Nu sker det. Av. Av. Okay. Nu behøver jeg at slippe af med den. Okay. 

Så nu har jeg en registrering af blot "Av." Så nu vil jeg gå videre og kalder det "Ouch." Jeg har tænkt mig at gå tilbage til mine scripts, og nu varsel er der denne blok, der hedder spille lyd "meow" eller afspille lyd "Ouch." Jeg har tænkt mig at trække det, og hvor skal jeg sætte det for komisk effekt? Ja, så nu er det sådan buggy, for nu dette block-- mærke til, hvordan denne "hvis på kanten, bounce "er en slags selvstændig. Så jeg har brug for at løse dette. Lad mig gå videre og gøre dette. Lad mig slippe af med denne og gå tilbage til vores oprindelige, mere bevidst funktionalitet. Så "Hvis røre kant, derefter" jeg vil at vende, da Victoria foreslog, 180 grader. Og jeg ønsker at spille lyden "av" der? 

Ja, mærke det er uden den gule blok. Så også dette ville være en bug, men jeg har bemærket det. Så jeg har tænkt mig at trække det op her, og bekendtgørelse nu er det inde i "hvis". Så "hvis" er den slags ligesom arm-lignende-blot der er kun kommer til at gøre, hvad der er inde i den. Så nu, hvis jeg zoome ud på risikoen for annoying-- 

COMPUTER: Av, av, av. 

DAVID MALAN: Og det vil bare blive ved for evigt. Nu bare for at fremskynde tingene her, lad mig gå videre og åbne op, lad os say-- lade mig gå til nogle af mine egne ting fra klassen. Og lad mig åbne op, lad os sige, dette en lavet af en af ​​vores undervisning stipendiater et par år siden. Så nogle af jer måske husker dette spil fra gårsdagens, og det er faktisk bemærkelsesværdigt. Selvom vi har gjort det enkleste af programmer lige nu, Lad os overveje, hvad dette faktisk ser ud. Lad mig hit spil. 

Så i dette spil, har vi en frø, og ved hjælp af pilen keys-- han tager større skridt end jeg remember-- Jeg har kontrol over denne frø. Og målet er at komme over den travle vej uden at løbe ind i biler. Og lad os see-- hvis jeg går op her, jeg nødt til at vente på en log for at rulle med. Dette føles som en fejl. Dette er lidt af en bug. Okay. Jeg er på dette her, der, og så skal du holde ud, indtil du får alle Frøerne til lilje puder. Nu ser måske desto mere kompleks, men lad os prøve at bryde dette ned mentalt og verbalt i sine blokke. Så der er nok et puslespil stykke, som vi ikke har set endnu men der er reagerer på tastetryk, til ting, jeg ramt på tastaturet. 

Så der er nok en slags blok, der siger, hvis nøglen er lig op, så gøre noget med Scratch-- måske flytte det 10 trin på denne måde. Hvis der trykkes på ned-tasten, flytte 10 trin denne måde, eller venstre tast, flytte 10 trin denne måde, 10 trin det. Jeg har klart slået katten til en frø. Så det er lige hvor den kostume, som Scratch opkald det-- vi bare importeret et billede af frøen. 

Men hvad sker der? Hvilke andre linjer kode, hvad andre puslespilsbrikker gjorde Blake, vores undervisning fyr, brug i dette program, tilsyneladende? Hvad gør alting move-- hvad programmering konstruere? 

Motion, sure-- så flytte blok, for sikker. Og hvad er det flytte blok inderside, mest sandsynligt? Ja, en slags loop, måske en evigt blokere, måske en gentagelse block-- gentag indtil blok. Og det er hvad der gør de logfiler og de lilje puder og alt andet træk frem og tilbage. Det er bare sker uendelige. 

Hvorfor er nogle af bilerne bevæger sig hurtigere end de andre? Hvad er anderledes ved disse programmer? Ja, sandsynligvis nogle af dem tager flere trin omgående, og nogle af dem færre trin på én gang. Og den visuelle virkning er hurtig versus langsom. 

Hvad tror du der skete? Da jeg fik min frog hele vejen på tværs af gaden og floden på lilje pad, noget bemærkelsesværdigt skete. Hvad skete så snart jeg gjorde det? Det stoppede. Det frøen stoppet, og Jeg fik en anden frø. Så hvad konstrukt skal være bruges der, hvad funktion? 

Ja, så der er en form for "Hvis" betingelse deroppe, også. Og det viser out-- vi ikke se denne-- men der er andre blokke i der, at kan sige, hvis du er rørende en anden ting på skærmen, Hvis du rører lilje pad "og derefter". Og så er, når vi gøre den anden frog vises. Så selv om dette spil er helt sikkert meget dateret, selvom ved første øjekast der er så meget at gå on-- og Blake ikke piske det op i to minutter, det sandsynligvis tog ham flere timer til at skabe dette spil baseret på hans hukommelse eller videoer Gårsdagens udgave af det. Men alle disse små ting foregår på skærmen isoleret koges ned til disse meget simpelt constructs-- bevægelser eller udsagn ligesom vi har diskuteret, loops og betingelser, og det er om det. Der er et par andre mere avanceret funktioner. Nogle af dem er rent æstetisk eller akustisk, ligesom de lyde, Jeg har lige spillet med. Men for det meste, du har i dette sprog, Scratch, alle de grundlæggende byggesten, som du har i C, Java, JavaScript, PHP, Ruby, Python, og et antal andre sprog. Eventuelle spørgsmål om Scratch? Okay. Så vi vil ikke dykke dybere til Scratch, selvom du er velkommen denne weekend, især hvis du har børn eller niecer og nevøer og sådan, at introducere dem til Scratch. Det er faktisk en dejlig legesyg miljø med, som dens forfattere siger, meget højt til loftet. Selvom vi startede med meget lavt niveau detaljer, du virkelig kan gøre en hel del med det, og det er måske en demonstration af netop dette. 

Men lad os nu overgangen til nogle mere sofistikerede problemer, hvis du vil, kendt som "søgning" og "Sortering", mere generelt. Vi havde denne telefonbog earlier-- her en anden bare for discussion-- at vi var i stand til at søge mere effektivt, fordi af en væsentlig forudsætning. Og bare for at være klar, hvad antagelse var jeg gør når du søger gennem denne telefonbog? At Mike Smith var i telefonbogen, selvom jeg ville kunne håndtere scenariet uden ham der, hvis jeg bare stoppet for tidligt. Bogen er alfabetisk. Og det er en meget generøs antagelse, fordi det betyder someone-- Jeg er lidt skære et hjørne, ligesom jeg hurtigere, fordi nogen andre gjorde en masse hårdt arbejde for mig. 

Men hvad hvis telefonen Bogen blev usorterede? Måske Verizon fik doven, bare kastede alles navne og numre derinde måske i rækkefølge, som de tilmeldt telefon tjenesten. Og hvor meget tid tager det mig at finde en som Mike Smith? 1000 side telefon book-- hvor mange sider skal jeg kigge igennem? 

Allesammen. Du er slags ude af lykke. Du bogstaveligt talt nødt til at se på alle side, hvis telefonbogen er bare sorteres tilfældigt. Du kan få heldige og finde Mike på den allerførste side, fordi han var den første kunde at bestille telefon tjenesten. Men han kunne have været den sidste, også. 

Så tilfældig rækkefølge er ikke god. Så formoder, at vi er nødt til at sortere telefonbogen eller generelt sortere data at vi har fået. Hvordan kan vi gøre det? 

Nå, lad mig bare prøve et simpelt eksempel her. Lad mig gå videre og kaste en par numre på tavlen. Antag numrene vi har, er, lad os sige, fire, to, en, og tre. Og, Ben, sortere disse numre for os. 

Ok godt. Hvordan gjorde du det? Okay. Så start med den mindste og den højeste, og det er virkelig god intuition. Og indse, at vi mennesker er faktisk temmelig god til at løse problemer som dette, i det mindste når dataene er relativt lille. Så snart du begynder at have hundredvis af numre, tusindvis af numre, millioner af numre, Ben sandsynligvis kunne ikke gøre det helt så hurtigt, under forudsætning af, at der var huller i tallene. Temmelig let at tælle til en million ellers blot tidskrævende. 

Så den algoritme det lyder ligesom Ben bruges lige nu var søgen efter det mindste tal. Så selv om vi mennesker kan tage i en masse oplysninger visuelt, en computer er faktisk lidt mere begrænset. Computeren kan kun se på en byte ad gangen eller måske fire bytes på en time-- disse dage måske 8 bytes på en time-- men et meget lille antal bytes på et givet tidspunkt. 

Så da vi virkelig har fire separate værdier her-- og du kan tænke på Ben som havende skyklapper på, hvis han var en computer, at han ikke kan se noget andet end et nummer på en time-- så vi generelt vil antage, ligesom i Engelsk, vi vil læse fra højre mod venstre. Så det første nummer Ben sandsynligvis set på var fire og derefter meget hurtigt indså, at er en temmelig stor number-- lad mig holde udkig. 

Der er to. Vent et øjeblik. To er mindre end fire. Jeg har tænkt mig at huske. To er nu den mindste. Nu en-- det er endnu bedre. Det er endnu mindre. Jeg har tænkt mig at glemme alt om to og bare huske én nu. 

Og han kunne holde op med at kigge? Nå, kunne han baserede på disse oplysninger, men han hellere søgning resten af ​​listen. For hvad hvis nul var på listen? Hvad hvis negativ var på listen? Han ved kun, at hans svar er korrekt, hvis han er udtømmende kontrolleres hele listen. Så vi ser på resten af ​​denne. Three-- det var spild af tid. Fik uheldige, men jeg var stadig er korrekt at gøre det. Og så nu er han formentlig valgt det mindste tal og bare sætte det i begyndelsen på listen, som jeg vil gøre her. Nu hvad gjorde du gøre næste, selvom du ikke synes om det næsten i dette omfang? Gentage processen, så en slags sløjfe. Der er en velkendt idé. Så her er fire. Det er i øjeblikket den mindste. Det er en kandidat. Ikke længere. Nu har jeg set to. Det er den næstmindste element. Three-- det er ikke mindre, så nu Ben kan plukke ud de to. 

Og nu er vi gentage processen og selvfølgelig tre bliver trukket ud næste. Gentage processen. Fire bliver trukket ud. Og nu er vi ude af tal, så listen skal sorteres. 

Og ja, det er en formel algoritme. En datalog ville kalder dette "valg slags," ideen er slags en liste iteratively-- igen og igen og igen at vælge det mindste tal. Og hvad er nice om det er det er bare så pokkers intuitivt. Det er så simpelt. Og du kan gentage den samme drift igen og igen. Det er simpelt. 

I dette tilfælde var det hurtigt, men hvor lang tid tager det faktisk tage? Lad os gøre det synes og føle sig lidt mere kedelig. Så en, to, tre, fire, fem seks, syv, otte, ni, 10, 11, 12, 13, 14, 15, 16-- vilkårligt antal. Jeg ville bare mere denne tid end blot fire. Så hvis jeg har en hel bundt af tal nu-- det ikke engang noget hvad de are-- lad os tænke over, hvad dette algoritme virkelig er. 

Antag at der er tal der. Igen, er ligegyldigt, hvad de er, men de er tilfældige. Jeg søger Ben algoritme. Jeg har brug for at vælge det mindste tal. Hvad skal jeg gøre? Og jeg har tænkt mig at fysisk gør det denne gang til at handle det ud. Ser, ser, kigge, kigge, kigge. Kun ved den tid, jeg kommer til enden af ​​listen kan Jeg er klar over den mindste nummer var to denne gang. Man er ikke i listen. Så jeg satte to. 

Hvad gør jeg nu? Ser, ser, ser, ser. Nu fandt jeg nummer syv, fordi Der er huller i disse numbers-- men blot vilkårlig. Okay. Så nu kan jeg lægge syv. Ser kigge, kigge. 

Nu er jeg antager, af selvfølgelig, at Ben ikke har ekstra RAM, ekstra hukommelse, fordi, selvfølgelig, Jeg kigger på det samme nummer. Sikkert jeg kunne have husket alle disse numre, og det er helt rigtigt. Men hvis Ben husker alle af numrene han har set, han har ikke rigtig gjort grundlæggende fremskridt fordi han allerede har evnen til at søge gennem numrene på tavlen. Huske alle de numre hjælper ikke, fordi han kan stadig som en computer kun se på, vi har sagt, et nummer på et tidspunkt. Så der er ingen form for cheat der, at du kan udnytte. 

Så i virkeligheden, da jeg fortsætte med at søge på listen, Jeg bogstaveligt talt nødt til bare at holde ud frem og tilbage gennem det, plukning ud den næstmindste antal. Og som du kan slags udlede fra mine dumme bevægelser, dette bliver bare meget kedelige meget hurtigt, og jeg synes at gå tilbage og tilbage, frem og tilbage ganske lidt. Nu for at være fair, jeg ikke behøver at gå ganske som, ja, lad os see-- at være fair, Jeg behøver ikke at gå helt så mange skridt hver gang. Fordi, selvfølgelig, som jeg vælge numre fra listen, den resterende liste bliver kortere. 

Og så lad os tænke over hvor mange skridt jeg er faktisk traipsing gennem hver gang. I den allerførste situation, vi havde 16 numre, og så maximally-- lad os bare gøre dette for en discussion-- Jeg var nødt til at se gennem 16 tallene for at finde den mindste. Men når jeg plukket ud det mindste tal, hvordan længe var den resterende liste, selvfølgelig? Blot 15. Så hvor mange numre gjorde Ben eller jeg har til at se gennem anden gang rundt? 15, bare at gå og finde den mindste. Men nu, selvfølgelig, listen er, Også mindre, end det var før. Så hvordan mange skridt gjorde jeg nødt til at tage det næste gang? 14 og derefter 13 og derefter 12, plus prik, prik, prik, indtil jeg tilbage med kun én. Så nu en datalog ville spørge, godt, hvad betyder, at alle er lige? Det faktisk er lig med nogle konkrete nummer, som vi kunne helt sikkert gøre matematisk, men vi ønsker at tale om effektiviteten af ​​algoritmer lidt mere formulaically, uafhængig af hvor lang listen er. 

Og så ved du hvad? Dette er 16, men som jeg sagde før, lad os bare kalde størrelsen af ​​problemet n, hvor n er et tal. Måske er det 16, måske er det tre, måske er det en million. Jeg ved ikke. Jeg er ligeglad. Hvad jeg virkelig ønsker, er en formel, jeg kan bruge til at sammenligne denne algoritme mod andre algoritmer at nogen måske hævde er bedre eller værre. 

Så det viser sig, og kun jeg kender det fra folkeskolen, at dette rent faktisk virker ud til den samme ting som n løbet n plus en over to. Og det sker til lige, af Selvfølgelig n kvadreret plus n over to. Så hvis jeg ønskede en formel for hvor mange skridt var involveret i at kigge på alle af disse numre igen og igen og igen og igen, vil jeg sige det er n kvadreret plus n over to. Men ved du hvad? Det ser bare rodet. Jeg bare virkelig ønsker en generel følelse af ting. Og du måske husker fra gymnasiet, at der er begrebet højeste orden sigt. Hvilke af disse vilkår, n kvadreret, n, eller den halve, har størst virkning over tid? Jo større n bliver, som af disse spørgsmål mest? 

Med andre ord, hvis jeg sætte i en million, n kvadreret vil være mest sandsynligt den dominerende faktor, fordi en million gange selv er en meget større end plus én ekstra million. Så ved du hvad? Dette er sådan en pokkers stor nummer, hvis du firkantet et nummer. Dette betyder ikke rigtig noget. Vi bare kryds, der ud og glemme alt om det. Og så en datalog vil sige at effektiviteten af ​​denne algoritme er af størrelsesordenen n squared-- Jeg mener virkelig en tilnærmelse. Det er slags groft n potens. Over tid, jo større og større n bliver dette er en god vurdering for, hvad effektivitet eller mangel på effektivitet af denne algoritme faktisk er. Og jeg udlede, at selvfølgelig, fra faktisk gør det math. Men nu er jeg bare vinke mine hænder, fordi jeg bare ønsker en generel følelse af denne algoritme. 

Så bruger den samme logik, i mellemtiden, Lad os overveje en anden algoritme vi allerede kigget at-- lineær søgning. Da jeg søgte til telefonen book-- ikke sortering af den, søgning via telefonen book-- Vi holdt siger, at det var 1.000 trin eller 500 trin. Men lad os generalisere det. Hvis der er n sider i telefonbogen, hvad er køretiden eller effektiviteten af ​​lineær søgning? Det er på rækkefølgen af hvor mange skridt til at finde Mike Smith ved lineær søgning, den første algoritme, eller endda den anden? 

I værste fald, Mike er i slutningen af ​​bogen. Så hvis telefonbogen har 1.000 sider, vi sagde sidste gang, i værste fald, det kan tage nogenlunde hvordan mange sider for at finde Mike? Ligesom 1000. Det er en øvre grænse. Det er en værst mulige situation. Men igen, vi flytter væk fra numre som 1000 nu. Det er bare n. 

Så hvad er den logiske konklusion? Finde Mike i en telefon bog, der har n-sider kan tage, i værste fald, hvor mange trin i størrelsesordenen n? Og faktisk en computer videnskabsmand ville sige at køretiden, eller ydelse eller effektivitet eller ineffektivitet, af en algoritme som en lineær søgning er af størrelsesordenen n. Og vi kan anvende den samme logik krydse noget ud som jeg lige gjorde til den anden algoritme, vi havde med telefonbogen, hvor vi gik to sider ad gangen. 

Så 1000 side telefonbog måske tage os 500 sider sving, plus en hvis vi fordoble en smule tilbage. Så hvis en telefonbog har n-sider, men vi laver to sider ad gangen, det er hvad groft? N over to, så det er ligesom n over to. Men jeg gjorde kravet en øjeblik siden, at n løbet to-- der er slags det samme som bare n. Det er bare en konstant faktor, dataloger ville sige. Lad os kun fokusere på variablerne, really-- de største variabler i ligningen. 

Så lineær søgning, uanset om gøres en side ad gangen eller to sider ad gangen, er slags grundlæggende de samme. Det er stadig på rækkefølgen af ​​n. Men jeg hævdede med mit billede tidligere at den tredje algoritme var ikke lineær. Det var ikke en lige linje. Det var denne krumme linie, og algebraisk formel der var hvad? Log af n- så logge basis to af n. Og vi behøver ikke at gå ind for mange detaljer om logaritmer i dag, men de fleste dataloger ville ikke endda fortælle dig, hvad basen er. Fordi det hele er bare konstante faktorer, så at sige, kun små numeriske forskelle. Og så det ville være en meget almindelig måde for særligt formelle computer forskere ved et bord eller programmører på en hvid bord faktisk argumenterer som algoritme de ville bruge eller hvad effektiviteten af deres algoritme er. 

Og det er ikke nødvendigvis noget du diskutere i nogen stor detalje, men en god programmør er nogen der har en solid, formel baggrund. Han er i stand til at tale med dig i denne slags måde og faktisk gøre kvalitative argumenter som hvorfor en algoritme eller ét stykke software er overlegen i nogle måde til en anden. Fordi du kunne sikkert bare køre én persons program og tælle antallet af sekunder det tager at sortere nogle tal, og du kan køre nogle anden persons program og tælle antallet sekunder det tager. Men det er en mere generel måde, du kan bruge til at analysere algoritmer, hvis du vil, bare på papir eller bare verbalt. Uden selv kører det uden selv forsøger prøve indgange, du kan bare ræsonnere igennem den. Og så med at ansætte en udvikler, eller hvis have ham eller hende slags argumentere for dig hvorfor deres algoritme, deres hemmelighed sauce til at søge milliarder af websider til din Virksomheden er bedre, disse er den slags argumenter, de bør ideelt set være i stand til at gøre. Eller i det mindste disse er den slags ting der ville komme op i debat på mindst i en meget formelle diskussion. Okay. Så Ben foreslog noget kaldet udvælgelse slags. Men jeg har tænkt mig at foreslå, at der er andre måder at gøre dette, også. Hvad jeg ikke kan virkelig godt lide om Ben algoritme er, at han holdt walking, eller have mig gå frem og tilbage og frem og tilbage og frem og tilbage. Hvad hvis i stedet jeg skulle gøre noget som disse numre her og jeg skulle bare beskæftige sig med hver nummer igen, som jeg givet det? 

Med andre ord, her er min liste over numre. Fire, en, tre, to. Og jeg har tænkt mig at gøre følgende. Jeg har tænkt mig at indsætte numrene hvor de hører snarere end at vælge dem én ad gangen. Med andre ord, her er nummer fire. 

Her er min oprindelige liste. Og jeg har tænkt mig at opretholde hovedsageligt en ny liste her. Så dette er den gamle liste. Dette er den nye liste. Jeg ser nummer fire første. Min nye liste er oprindeligt tom, så det er trivielt tilfældet at fire er nu assorteret liste. Jeg er bare tage antallet jeg givet, og jeg sætte det i min nye liste. 

Er denne nye liste sorteret? Ja. Det er dumt, fordi der er bare én element, men det er absolut sorteres. Der er ikke noget ud af sted. Det er mere interessant, denne algoritme, når jeg flytter til næste trin. 

Nu har jeg en. Så en selvfølgelig tilhører på det begyndelsen eller slutningen af ​​denne nye liste? Begyndelsen. Så jeg er nødt til at gøre noget arbejde nu. Jeg har taget nogle friheder med min markør ved blot at trække ting hvor jeg vil have dem, men det er ikke rigtig præcise i en computer. En computer, som vi ved, har RAM eller Random Access Memory, og det er en byte og anden byte og en anden byte. Og hvis du har en gigabyte RAM, har du en milliard bytes, men de er fysisk på ét sted. Du kan ikke bare flytte ting rundt ved at trække det på tavlen hvorend du vil. Så hvis min nye liste har fire steder i hukommelsen, Desværre fire er allerede på det forkerte sted. 

Så for at indsætte nummer et Jeg kan ikke bare trække det her. Denne hukommelse placering findes ikke. Det ville være snyd, og jeg har været snyd billedligt i et par minutter her. Så virkelig, hvis jeg ønsker at sætte en her, Jeg er nødt til midlertidigt at kopiere fire og derefter sætte den ene der. 

Det er fint, det er korrekt, det er teknisk muligt, men indse det er ekstra arbejde. Jeg har ikke bare sætter antallet på plads. Jeg først måtte flytte en nummer, og derefter sætte det på plads, så jeg slags fordoblet mit mængde arbejde. Så hold det i tankerne. 

Men jeg er nu færdig med dette element. Nu vil jeg få fat i nummer tre. Hvor naturligvis hører det? Ind imellem. Jeg kan ikke snyde længere og bare sætte det der, fordi igen, denne hukommelse er i fysiske lokaliteter. Så jeg er nødt til at kopiere fire og sætte tre herovre. Ikke noget særligt. Det er bare et ekstra skridt igen-- føles meget billig. 

Men nu jeg gå videre til de to. De to naturligvis hører her. Nu begynder du at se, hvordan arbejdet kan hobe sig op. Nu, hvad skal jeg gøre? Ja, jeg er nødt til at flytte de fire, Jeg så nødt til at kopiere de tre, og nu kan jeg indsætte de to. Og fangsten med dette algoritme, interessant nok, er der formoder, at vi har en mere ekstrem tilfælde, hvor det er lad os sige otte, syv, seks, fem, fire, tre, to, en. Dette er, i mange sammenhænge, det værst tænkelige scenarie, fordi darn ting er bogstaveligt talt bagud. 

Det gør ikke rigtig påvirke Ben algoritme, fordi i Ben udvælgelse sortere han vil holde gå frem og tilbage gennem listen. Og fordi han altid var på udkig gennem hele resterende liste, det gør ikke noget hvor elementerne er. Men i dette tilfælde med min indsættelse approach-- lad os prøve dette. 

Så en, to, tre, fire, fem, seks, syv, otte. En to tre fire, fem, seks, syv, otte. Jeg har tænkt mig at tage otte, og hvor kan jeg sætte det? Nå, i begyndelsen af ​​min liste, fordi denne nye liste sorteres. Og jeg krydse den ud. 

Hvor skal jeg placere syv? Pokkers. Det skal gå der, så Jeg er nødt til at gøre nogle kopiering. Og nu syv går her. Nu jeg gå videre til seks. Nu er det endnu mere arbejde. 

Otte har at gå her. Syv har at gå her. Nu seks kan gå her. Nu jeg fat i fem. Nu otte skal gå her, syv har at gå her, seks har at gå her, og nu fem og gentag. Og jeg er temmelig meget flytte den hele tiden. 

Så i slutningen, denne algorithm-- vi får kalder det indsættelse sort-- faktisk har en masse arbejde, også. Det er bare anderledes slags arbejde end Ben. Ben arbejde havde mig gå frem og tilbage hele tiden, vælge den næstmindste element igen og igen. Så det var denne meget visuelle form for arbejde. 

Denne anden algoritme, som stadig correct-- det vil få jobbet done-- bare ændrer mængden af ​​arbejde. Det ligner oprindeligt er du besparelse, fordi du er bare beskæftiger sig med hvert element op foran uden at gå alt vejen gennem listen ligesom Ben var. Men problemet er, især i disse skøre sager, hvor det hele er bagud, du er bare sådan udskyde det hårde arbejde indtil du nødt til at ordne dine fejl. 

Og så hvis du kan forestille dig dette otte og syv og seks og fem og senere fire og tre og to flytter deres vej gennem listen, Vi har netop ændret type arbejde, vi laver. Stedet for at gøre det på begyndelsen af ​​min iteration, Jeg er bare at gøre det på slutningen af ​​hver iteration. Så det viser sig, at denne algoritme, Også generelt kaldes indsættelsessortering, er også af størrelsesordenen n potens. Det er faktisk ikke bedre, ikke bedre overhovedet. 

Men der er en tredje tilgang Jeg vil opfordre os til at overveje, som er dette. Så formoder min liste, for enkelhed igen, er fire, en, tre, to-- blot fire numre. Ben havde god intuition, godt menneske intuition før, hvorved fast vi hele liste eventually-- indsættelsessortering. Jeg lokkede os sammen. Men lad os betragte enkleste måde at løse denne liste. 

Denne liste er ikke sorteres. Hvorfor? PÃ¥ engelsk, forklare, hvorfor Det er faktisk ikke sorteres. Hvad betyder det ikke skal sorteres? 

STUDENT: Det er ikke sekventiel. 

DAVID MALAN: Ikke sekventiel. Giv mig et eksempel. 

STUDENT: Sæt dem i rækkefølge. 

DAVID MALAN: OK. Giv mig et mere konkret eksempel. 

STUDENT: Stigende rækkefølge. DAVID MALAN: Ikke stigende rækkefølge. Være mere præcis. Jeg ved ikke, hvad du mener med stigende. Hvad er der galt? 

STUDENT: Den mindste af de numre er ikke i det første rum. 

DAVID MALAN: Mindste antal er ikke i det første rum. Vær mere specifik. Jeg begynder at fange den. Vi regner, men hvad der er ude af drift her? 

STUDENT: Numerisk sekvens. DAVID MALAN: Numerisk sekvens. Alles slags holde det her-- meget højt niveau. Bare bogstaveligt fortælle mig, hvad der er forkert som en fem-årig magt. 

STUDENT: Plus en. 

DAVID MALAN: Hvad er det? 

STUDENT: Plus en. 

DAVID MALAN: Hvad mener du plus en? Giv mig en anden fem-Ã¥rig. Hvad er der galt, mor? Hvad er der galt, far? Hvad mener du dette er ikke sorteres? 

STUDENT: Det er ikke det rigtige sted. 

DAVID MALAN: Hvad er ikke på det rigtige sted? 

STUDENT: Fire. DAVID MALAN: OK, godt. Så fire er ikke hvor det skal være. Især er denne ret? Fire og en, den første to tal, jeg ser. Er det her rigtigt? Nej, de er ude af drift, ikke? Faktisk tror nu om en computer, også. Det kan kun se på måske en, måske to ting på once-- og faktisk kun én ting på et tidspunkt, men det kan i det mindste se på en ting derefter næste ting lige ved siden af ​​den. 

Så er disse i orden? Selvfølgelig ikke. Så ved du hvad? Hvorfor vi ikke tage barnet trin fastsættelse dette problem stedet for at gøre disse fancy algoritmer som Ben, hvor han slags fastsættelse det ved looping gennem listen stedet for at gøre, hvad jeg gjorde, hvor Jeg lige slags fast det, som vi går? Lad os bare bogstaveligt nedbryde begrebet order-- nummerorden, kalde det hvad du want-- ind i disse parvise sammenligninger. 

Fire og én. Er det den rigtige rækkefølge? Så lad os ordne det. One og fire, og derefter vi bare kopiere det. Okay, godt. Jeg fast én og fire. Tre og to? Ingen. Lad mine ord matcher mine fingre. Fire og tre? 

Det er ikke i orden, så jeg har tænkt mig at gøre én, tre, fire, to. Ok godt. Nu fire og to? Vi er nødt til at løse dette, også. Så en, tre, to, fire. Så er det sorteret? Nej, men er det tættere på sorteres? 

Det er, fordi vi fast dette fejl, vi fast denne fejl, og vi fast denne fejl. Så vi fast tre fejltagelser velsagtens. Stadig ikke rigtig ser sorterede, men det objektivt tættere på sorterede fordi vi fast nogle af disse fejl. 

Nu hvad gør jeg nu? Jeg slags nået enden af ​​listen. Jeg syntes at have fast alle de fejl, men nej. Fordi i denne sag, nogle numre kunne have boblet op tættere til andre numre, er stadig ude af drift. Så lad os gøre det igen, og jeg vil bare gøre det på plads denne gang. One og tre? Det er fint. Tre og to? Selvfølgelig nej, så lad os ændre det. Så to, tre. Tre og fire? Og lad os nu bare være især pedantisk her. Er det sorteret? Du mennesker ved, at det sorteres. 

Jeg skal prøve igen. Så Olivia foreslår jeg prøve igen. Hvorfor? Fordi en computer ikke har den luksus af vores menneskelige øjne af bare forbigående tilbage-- OK, jeg færdig. Hvordan computeren bestemme at listen nu sorteres? Mekanisk. 

Jeg skal gå igennem en gang mere, og kun hvis jeg ikke gør / finde nogen fejl kan jeg derefter konkludere som computeren, jep, vi er gode til at gå. Så en og to, to og tre, tre og fire. Nu kan jeg endeligt sige dette er sorteres, fordi jeg ikke foretages ændringer. Nu ville det være en fejl, og bare dum hvis jeg, computeren stillede de samme spørgsmål igen forventer forskellige svar. Bør ikke ske. 

Og så nu listen er sorteret. Desværre driftstid denne algoritme er også N potens. Hvorfor? Fordi du har n tal, og i værste tilfælde du nødt til at flytte n tal n gange, fordi du er nødt til at holde ud tilbage til at kontrollere og potentielt fastsætte disse numre. Og vi kan gøre en mere formel analyse, også. 

Så dette er alle at sige, vi har taget tre forskellige tilgange, en af dem straks intuitiv off bat fra Ben til min foreslåede indsættelse slags til denne ene hvor du slags glemme skoven for bare træer oprindeligt. Men så hvis du tager et skridt tilbage, voila, vi har rettet sortering begreb. Så dette er, tør sige, et lavere niveau måske end nogle af de andre algoritmer, men lad os se, om vi ikke kan visualisere disse ved hjælp af dette. 

Så dette er nogle nice software, at nogen skrev hjælp farverige barer, der er kommer til at gøre følgende for os. Hver af disse stænger repræsenterer et tal. Taller baren, jo større nummeret, mindre bar, jo færre. Så ideelt set ønsker vi en dejlig pyramide hvor det begynder lille og får store, og det ville betyde, at disse stænger er sorteret. Så jeg har tænkt mig at gå videre og vælge, for eksempel, Ben algoritme first-- udvælgelse slags. 

Og mærke til, hvad det gør. Den måde, de har valgt at visualisere denne algoritme er, at, ligesom jeg var gå gennem min liste, dette program er at gå gennem sin liste over numre, fremhæver i pink hver nummer, som det er at se på. Og hvad er ved at ske lige nu? 

Det mindste tal, der I eller Ben fandt pludselig bliver flyttet til begyndelsen af ​​listen. Og varsel, de gjorde evict det nummer, der var der, og det er helt fint. Jeg fik ikke ind i denne detaljeringsgrad. Men vi har brug for at sætte dette nummer eller andet sted, så vi lige flyttet det til åben plet, der blev oprettet. Så jeg har tænkt mig at fremskynde denne op, fordi det ellers bliver meget trættende hurtigt. Animation fart- der vi gå. Så nu samme princip Jeg anvender, men du kan begynde at føle den algoritme, hvis du vil, eller se det lidt mere klart. Og denne algoritme har den virkning, vælge den næste mindste element, så du vil begynde at se det rampe op til venstre. Og på hver iteration, da jeg foreslået, det gør lidt mindre arbejde. Det behøver ikke at gå hele vejen tilbage til den venstre ende af listen, fordi den allerede kender dem sorteres. Så den slags føles ligesom det er accelererende, selv om hvert trin er idet den samme mængde tid. Der er bare færre trin tilbage. Og nu kan du slags føler algoritme oprydning i slutningen af ​​det, og faktisk nu er det ordnet. 

Så indsættelsessortering er alle gjort. Jeg har brug for at re-randomisere array. Og opdager jeg kan bare holde randomisering det, og vi får en tilnærmelse af den samme fremgangsmåde, indsættelsessortering. Lad mig bremse den ned til her. Lad os starte at over. Stop. 

Lad os springe fire. Sådan der. Randomisere de array. Og her go-- vi indsættelsessortering. Spil. Bemærk at det er behandling af hver enkelt element det støder det samme, men hvis det tilhører i det forkerte sted varsel alt det arbejde, der skal ske. Vi er nødt til at holde skiftende mere og flere elementer for at gøre plads for den, vi ønsker at sætte på plads. 

Så vi fokuserer på venstre ende af kun listen. Bemærker vi har ikke engang kigget at-- vi har ikke fremhævet i lyserødt noget til højre. Vi er bare beskæftiger sig med de problemer, som vi går, men vi er ved at oprette en masse arbejde for os selv endnu. Og så hvis vi fremskynde dette op nu at løbe til ende, det har en anden føler for det faktisk. Det er bare at fokusere på den venstre ende, men gøre lidt mere arbejde som needed-- slags udjævning tingene overstået, fastsættelse ting, men beskæftiger sig i sidste ende med hvert element en ad gangen indtil vi får til-- godt, vi ved alle, hvordan det vil ende, så det er lidt underwhelming måske. 

Men listen i end-- spoiler-- vil blive sorteret. Så lad os se på en sidste. Vi kan ikke bare springe nu. Vi er der næsten. To til at gå, en til at gå. Og voila. Fremragende. 

Så lad os nu gøre et sidste, re-randomisering med boblesortering. Og bemærke her, især hvis jeg langsomt det ned, betyder det holde swooping igennem. Men bemærk det bare gør parvis comparisons-- slags lokale løsninger. Men så snart vi kommer til enden af ​​listen i pink, hvad der kommer til at ske igen? Ja, det kommer til at have til starte forfra, fordi den kun faste parvise fejltagelser. Og som kunne have afsløret endnu andre. Og så hvis du fremskynde det op, vil du se, meget som navnet antyder, den mindre elements-- eller rettere, de større elements-- er begyndt at boble op til toppen, hvis du vil. Og de mindre elementer er begynder at boble ned til venstre. Og ja, der er slags den visuelle effekt samt. Og så dette vil ende med efterbehandling i en meget lignende måde, også. 

Vi behøver ikke at bo på denne særlige én. Lad mig åbne det nu, også. Der er et par andre sortering algoritmer i verden, hvoraf nogle få fanges her. Og især for elever, der ikke er nødvendigvis visuel eller matematisk, som vi gjorde før, kan vi også gøre dette audially hvis vi knytte en lyd med dette. Og bare for sjov, her er en par forskellige algoritmer, og en af ​​dem i særdeleshed du er kommer til at lægge mærke til, kaldes "merge slags." 

Det er faktisk en fundamentalt bedre algoritme, således at mergesort, en af dem, du er ved at se, er ikke rækkefølgen af ​​n potens. Det er på rækkefølgen af ​​n gange logge af n, som er faktisk mindre og dermed hurtigere end de andre tre. Og der er en anden par fjollet dem, vi vil se. 

Så her går vi med nogle lyd. Dette er indsættelsessortering, så igen det er bare beskæftiger sig med elementerne som de kommer. Dette er boblesortering, så det er overvejer dem parvis ad gangen. Og igen, de største elementer er gennemstrømning op til toppen. 

Næste op udvælgelse slags. Dette er Ben algoritme, hvor igen han vælge iterativt den næstmindste element. Og igen, nu kan du virkelig høre, at det er hurtigere, men kun i det omfang som det gør mindre og mindre arbejde på hver iteration. Dette er den hurtigere en, mergesort, som er sortering klynger af numre sammen og derefter kombinere dem. Så look-- venstre halvdelen er allerede sorteret. 

Nu er det sortering den højre halvdel, og nu det kommer til at kombinere dem i én. Dette er noget, der hedder "Gnome slags." Og du kan slags se, at det går frem og tilbage, fastsættelse arbejde en lille smule her og der, før det fortsætter til nyt arbejde. Og det er det. Der er en anden slags, som er virkelig bare til akademiske formål, kaldet "dumme slags", som tager dine data, sorterer det tilfældigt, og kontrollerer derefter, hvis det er sorteret. Og hvis det ikke er, det re-sorterer det tilfældigt, tjekker, om det er sorteret, og hvis ikke gentager. Og i teorien, probalistisk dette vil fuldføre, men efter ganske lidt tid. Det er ikke den mest effektive af algoritmer. Så spørgsmål om dem, særlige algoritmer eller noget relateret, også? 

Nå, lad os nu drille hinanden, hvad alle disse linjer er, at jeg har været tegning og hvad jeg går ud af computeren kan gøre under emhætten. Jeg vil hævde, at alle disse tal Jeg holder drawing-- de behøver for at få gemt et sted i hukommelsen. Vi vil slippe af med denne fyr nu, også. 

Så et stykke hukommelse i en computer-- så RAM DIMM er hvad vi søgte efter i går, dual Inline Memory module-- ser sådan ud. Og hver af disse små sorte chips er nogle antal byte, typisk. Og så guld ben er ligesom ledninger, der forbinder den til computeren, og den grønne silicium bord er bare hvad der holder alting sammen. Så hvad betyder det egentlig? Hvis jeg slags tegne samme billede, Lad os antage for enkelhed at denne DIMM, dual inline hukommelsesmodul, er en gigabyte RAM, en gigabyte hukommelse, hvilket er hvor mange bytes alt? En gigabyte er, hvor mange bytes? Mere end det. 1124 er kilo, 1000. Mega er millioner. Giga er en milliard. 

Er jeg lyver? Kan vi selv læse etiketten? Dette er faktisk 128 gigabyte, så det er mere. Men vi vil lade dette er blot én gigabyte. Så det betyder, at der er en milliard bytes af hukommelse til rådighed for mig eller 8 milliarder bits, men vi vil at tale i form af bytes nu, Bevæger sig fremad. 

Så hvad det betyder er det er én byte, det er en anden byte, det er en anden byte, og hvis vi virkelig ønskede at være specifik vi skulle tegne en milliard små firkanter. Men hvad betyder det? Nå, lad mig bare zoome i på dette billede. Hvis jeg har noget, der ser som dette nu, det er fire bytes. 

Og så jeg kunne sætte fire numre her. En to tre fire. Eller jeg kunne sætte fire bogstaver eller symboler. "Hej!" kunne gå lige der, fordi hver af bogstaverne, vi diskuterede tidligere, kunne være repræsenteret med otte bit eller ASCII eller en byte. Så med andre ord kan du sætte 8 milliarder ting inde af denne ene pind af hukommelse. Nu hvad betyder det at sætte tingene tilbage til tilbage til tilbage i hukommelsen som denne? Det er, hvad en programmør ville kalde en "array." I et computerprogram, tror du ikke om den underliggende hardware, per se. Du tror bare på dig selv som havende adgang til en milliard bytes alt, og du kan noget, du vil med det. Men for nemheds skyld det er generelt anvendelig at holde din hukommelse højre ved siden af ​​hinanden på denne måde. Så hvis jeg zoome ind på denne-- fordi vi bestemt ikke gå at tegne en milliard små squares-- Lad os antage, at dette board repræsenterer at pind af hukommelse nu. Og jeg vil bare trække så mange som min markør ender med at give mig her. Så nu har vi en pind hukommelse på tavlen der er har en, to, tre, fire, fem, seks, en, to, tre, fire, fem, seks, seven-- så 42 bytes af hukommelse på den totale skærmen. Tak. Ja, gjorde min aritmetiske højre. Så 42 bytes af hukommelse her. Så hvad betyder det egentlig? Tja, en computer programmør ville faktisk generelt tænke på denne hukommelse som adresserbare. Med andre ord, hver enkelt af disse steder i hukommelsen, i hardware, har en unik adresse. 

Det er ikke så kompliceret som One Brattle Square, Cambridge, Mass., 02138. I stedet er det bare et tal. Dette er byte tallet nul, er dette en, dette er to, er det tre, og dette er 41. Vent et øjeblik. Jeg troede, jeg sagde 42 for et øjeblik siden. Jeg begyndte at tælle på nul, så det er faktisk korrekt. Nu har vi ikke til rent faktisk at trække det som et gitter, og hvis du tegner det som et gitter Jeg tror tingene faktisk få en smule misvisende. Hvad en programmør ville, i hans eller hendes eget sind, generelt tænker på denne hukommelse som er ligesom et bånd, som et stykke malertape der bare bliver ved og ved for evigt eller indtil du løber tør for hukommelse. Så en mere almindelig måde at trække og bare tænke på hukommelse ville være, at det er byte nul, et, to, tre, og derefter prik, prik, prik. Og du har 42 sådanne bytes alt, selv selvom fysisk det måske faktisk være noget mere som denne. 

Så hvis du nu tænker på din hukommelse som dette, ligesom et bånd, dette er hvad en programmør igen ville kalde en vifte af hukommelse. Og når du vil rent faktisk gemme noget i en computers hukommelse, du generelt gør gemme ting back-to-back to back-to-back. Så vi har talt om tal. Og når jeg ønskede at løse problemer ligesom fire, en, tre, to, selvom jeg bare tegne kun de numre, fire, en, tre, to på bordet, computeren ville virkelig har denne opsætning i hukommelsen. 

Og hvad ville være ved siden af to i computerens hukommelse? Tja, der er ikke noget svar på det. Vi ved ikke rigtig. Og så længe den Computeren har ikke brug for det, det behøver ikke at bekymre sig, hvad der er næste til numrene det gør sig om. Og da jeg sagde tidligere, at en computer kan kun se på én adresse ad gangen, dette er lidt hvorfor. 

Ikke ulig en rekord afspiller og et læsehoved kun at kunne se på en bestemt rille i en fysisk old-school rekord på et tidspunkt, på lignende måde kan en computer tak til dens CPU og dens Intel instruktionssæt, blandt hvis instruktion læses fra hukommelsen eller gemme til memory-- en computer kan kun se på ét sted ad time-- undertiden en kombination af dem, men egentlig bare ét sted ad gangen. Så når vi lavede disse forskellige algoritmer, Jeg er ikke bare skrive i en vacuum-- fire, en, tre, to. Disse tal faktisk tilhører et sted fysisk i hukommelsen. Så der er lillebitte transistorer eller anden form af elektronik nedenunder hætte lagring disse værdier. 

Og i alt, hvor mange bit er involveret lige nu, bare for at være klar? Så dette er fire bytes, eller nu er det 32 ​​bit alt. Så der er faktisk 32 nuller og dem komponere disse fire ting. Der er endnu mere herovre, men igen vi er ligeglad om det. 

Så lad os nu spørge en anden spørgsmål ved hjælp hukommelse, fordi der ved udgangen af dagen er i varians. Ligegyldigt hvad vi kan gøre med computeren, ved slutningen af ​​dagen hardwaren er stadig den samme under emhætten. Hvordan ville jeg opbevare et ord i her? Tja, et ord i en computer som "Hej!" vil kunne lagres ligesom dette. Og hvis du ønskede en længere ord, kan du blot overskrive det og sige noget ligesom "hej" og butik, der her. 

Og så også her denne contiguousness er faktisk en fordel, fordi en computer kan bare læses fra højre mod venstre. Men her er et spørgsmål. I forbindelse med dette ord, h-e-l-l-o, udråbstegn, hvordan kan computeren ved, hvor den ord begynder og hvor ordet ender? I forbindelse med numre, hvordan gør computeren hvor længe sekvensen af tal er, eller hvor det starter? Tja, det viser out-- og vi vil ikke gå for meget i dette niveau af detail-- computere flytte ting rundt i hukommelsen bogstaveligt i form af disse adresser. Så i en computer, hvis du er skrive kode til at gemme ting ligesom ord, hvad du er virkelig gør er at skrive udtryk, der husker hvor i computerens hukommelse disse ord er. Så lad mig gøre en meget, meget simpelt eksempel. 

Jeg har tænkt mig at gå videre og åbne op for en simpel tekst-program, og jeg har tænkt mig at skabe en fil kaldet hello.c. De fleste af disse oplysninger, vi vil ikke gå ind i detaljer, men jeg har tænkt mig at skrive en program i samme sprog, C. Det er langt mere skræmmende, Jeg vil hævde, end Scratch, men det er meget ens i ånd. I virkeligheden er disse krøllet braces-- kan du slags tænke på, hvad jeg lige gjorde, som dette. 

Lad os gøre det, faktisk. Når grønt flag klikkede, gøre følgende. Jeg ønsker at udskrive "Hej." Så dette er nu pseudokode. Jeg er lidt sløring linjerne. I C, dette sprog jeg taler om, denne linje print hej faktisk bliver "printf" med nogle parenteser og et semikolon. 

Men det er nøjagtig samme idé. Og denne meget brugervenligt "Når grønne flag klikket" bliver den langt mere mystiske "int main tomrum." Og det har virkelig ingen kortlægning, så jeg bare at ignorere det. Men de krøllede parenteser er ligesom buede puslespilsbrikker som denne. 

Så du kan slags gætte. Selv hvis du aldrig har programmeret før, hvad betyder dette program sandsynligvis gøre? Sandsynligvis udskriver hej med et udråbstegn. 

Så lad os prøve det. Jeg har tænkt mig at gemme det. Og det er, igen, en meget gamle skole miljø. Jeg kan ikke klikke, jeg kan ikke trække. Jeg er nødt til at skrive kommandoer. Så jeg vil køre mit program, så Jeg kan gøre dette, ligesom hello.c. Det er den fil, jeg løb. Men vent, jeg mangler et trin. Hvad gjorde vi siger, er en nødvendig trin til et sprog som C? Jeg har lige skrevet kilde kode, men hvad skal jeg bruge? Ja, jeg har brug for en compiler. Så på min Mac her, jeg har en program kaldet GCC, GNU C compiler, som tillader mig at gøre denne-- tur min kilde kode i, vil vi kalde det, maskinkode. 

Og jeg kan se, at, igen, som følger, er disse er de nuller og ettaller I bare skabt ud fra min kildekode, alle de nuller og ettaller. Og hvis jeg vil køre min program-- det sker at blive kaldt a.out for historiske reasons-- "Hej." Jeg kan køre det igen. Hej hej hej. Og det ser ud til at virke. 

Men det betyder et eller andet sted i min computerens hukommelse er de ord h-e-l-l-o, udråbstegn. Og det viser sig, lige som en sidebemærkning, hvad en computer ville typisk gøre, så den ved, hvor tingene begynder og end-- det er vil sætte et særligt symbol her. Og konventionen er at sætte nummer nul ved slutningen af ​​et ord så du ved, hvor det faktisk afsluttes, så du ikke holde udskrive mere og mere tegn end du rent faktisk har til hensigt. 

Men takeaway her, selv selvom dette er temmelig mystisk, er, at det er i sidste ende relativt simpelt. Du fik en slags tape, en tom plads, hvor du kan skrive breve. Du er simpelthen nødt til at have en særligt symbol, som vilkårligt tallet nul, for at sige ved udgangen af dine ord, så computeren kender, Åh, jeg skal stoppe udskrivningen, efter Jeg ser udråbstegn. Fordi den næste ting der er en ASCII værdi på nul, eller null karakter som nogen ville kalde det. Men der er lidt af et problem her, og lad os vende tilbage til tal for et øjeblik. Antag, at jeg gør, i virkeligheden, har en matrix af tal, og antage, at program jeg skriver, er som en karakterbog for en lærer og en lærere klasseværelse. Og dette program giver ham eller hende til at skrive i deres elevers score på quizzer. Og formoder, at den studerende får 100 på deres første quiz, måske som en 80 på den næste, derefter en 75, derefter en 90 på den fjerde quiz. 

Så på dette tidspunkt i historien, arrayet er af størrelse fire. Der er absolut mere hukommelse i computer, men arrayet, så at sige, er af størrelse fire. Antag nu, at læreren ønsker at tildele en femte quiz til klassen. Tja, en af ​​de ting, han eller hun vil have at gøre er nu at gemme en ekstra værdi her. Men hvis arrayet læreren skabt i dette program er af størrelse for, en af ​​problemet med et array er, at du kan ikke bare holde tilføje til hukommelsen. For hvad hvis en anden del af Programmet har ordet "hej" lige der? 

Med andre ord, kan min hukommelse være bruges til noget i et program. Og hvis i forvejen, jeg har skrevet i, hey, Jeg vil indtaste fire quiz scores, de kunne gå her og her. Og hvis du pludselig skifter mening senere og sige, at jeg vil have en femte quiz score, kan du ikke bare sætte det hvor du vil, fordi det, hvis dette hukommelse bliver brugt for noget else-- et andet program eller nogle andre træk ved programmet at du kører? Så du er nødt til at tænke på forhånd hvordan du ønsker at gemme dine data, fordi nu har du malet dig ind i en digital hjørne. 

Så lærer måske i stedet sige, når du skriver et program at lagre hans eller hendes kvaliteter, ved du hvad? Jeg vil anmode om, når du skriver mit program, at jeg ønsker nul, en, to, tre, fire, fem, seks, otte kvaliteter alt. Så en, to, tre, fire, fem, seks, syv, otte. Læreren kan bare over-allokere hukommelse, når du skriver hans eller hendes program og sige, ved du hvad? Jeg kommer aldrig til at tildele mere end otte quizzer i et semester. Det er bare vanvittigt. Jeg vil aldrig tildele det. Så at denne måde, han eller hun har fleksibilitet til at gemme elevernes resultater, ligesom 75, 90, og måske en ekstra hvor eleven fik ekstra kredit, 105. 

Men hvis læreren aldrig bruger disse tre rum, der er en intuitiv takeaway her. Han eller hun bare spilde plads. Så med andre ord, der er denne fælles tradeoff i programmering hvor du enten kan tildele præcis så meget hukommelse som du ønsker, opadrettede af som er, at du er super efficient-- du ikke at være ødsel på all-- men bagsiden af ​​medaljen, som er, hvad hvis du ændrer mening, når ved hjælp af programmet, som du vil gemme flere data end du oprindeligt beregnet. 

Så måske er løsningen, da skrive dine programmer på en sådan måde at de bruger mere hukommelse end de faktisk har brug for. Denne måde du ikke kommer at løbe ind i det problem, men du bliver spild. Og jo mere hukommelse dit program bruger, som vi diskuterede i går, jo mindre hukommelse, der er til rådighed for andre programmer, jo før din computer kan bremse ned på grund af virtuel hukommelse. Og så den ideelle løsning kunne være, hvad? 

Under-fordeling synes dårligt. Over-fordeling synes dårligt. Så hvad kunne være en bedre løsning? Omfordeling. Være mere dynamisk. Må ikke tvinge dig selv til at vælge en priori, i begyndelsen, hvad du ønsker. Og bestemt ikke over-allokere, lest du være spild. 

Og så for at nå dette mål, vi nødt til at kaste denne datastruktur, så at sige, væk. Og så hvad en programmør vil typisk bruge er noget, der hedder ikke en matrix men en sammenkædet liste. Med andre ord, vil han eller hun begynde at tænke på deres hukommelse som værende slags en form, som de kan trække på følgende måde. Hvis jeg ønsker at gemme et nummer i en program-- så det er september Jeg har givet mine elever en quiz; jeg vil til at gemme de studerendes første quiz, og de fik en 100 på it-- I jeg vil bede min computer, ved hjælp af det program, jeg har skrevet, for én luns af hukommelse. Og jeg har tænkt mig at gemme nummer 100 i den, og det er det. 

Så et par uger senere når jeg får min anden quiz, og det er tid til at skrive i, at 90%, vil jeg at spørge computeren, hey, computer, kan jeg have en anden luns af hukommelse? Det kommer til at give mig denne tom luns af hukommelse. Jeg har tænkt mig at sætte i antallet 90, men i mit program på en eller other-- og vi vil ikke bekymre dig om syntaksen for denne-- jeg har brug for en eller anden måde kæde disse ting sammen. Og jeg vil kæde dem sammen med hvad der ligner en pil her. 

Den tredje quiz, der kommer op, Jeg har tænkt mig at sige, hey, computer, give mig en anden luns af hukommelse. Og jeg har tænkt mig at sætte ned uanset hvad det var, ligesom 75, og jeg er nødt til at kæde dette sammen nu en eller anden måde. Fjerde quiz kommer sammen, og måske det er mod slutningen af ​​semestret. Og ved dette punkt mit program kan være ved hjælp af hukommelse over det hele, hele fysisk. Og så bare for spark, jeg er vil trække denne ud quiz-- Jeg glemmer, hvad det var; jeg tror måske en 80 eller something-- vej herover. 

Men det er fint, fordi billedligt Jeg har tænkt mig at trække denne linje. Med andre ord, i virkeligheden, i computerens hardware, den første score might ender her, fordi det er lige i starten af ​​semesteret. Den næste kan ende her fordi en smule tid der er gået og programmet holder kører. Den næste score, som var en 75, måske herovre. Og den sidste score kunne være en 80, hvilket er over her. 

Så i virkeligheden, fysisk, dette kan være hvad computerens hukommelse ser ud. Men dette er ikke en nyttig mental paradigme for en computer programmør. Hvorfor skal du pleje, hvor dælen dine data er ender? Du vil bare gemme data. 

Dette er lidt ligesom vores diskussion tidligere at trække terningen. Hvorfor bekymrer du dig, hvad vinklen er af terningen og hvordan du skal slå til at trække det? Du vil bare en terning. På samme måde her, du blot ønsker at karakterbog. Du vil bare at tænke på dette som en liste af tal. Hvem bekymrer sig, hvordan det er implementeres i hardware? 

Så indvinding nu er dette billede her. Dette er en linket liste, som en programmør ville kalde det, det omfang du har en liste, naturligvis af tal. Men det er forbundet billedligt ved hjælp af disse pile, og alle disse pile are-- nedenunder hætten, hvis du er nysgerrig, minde om, at vores fysiske hardware har adresser nul, en, to, tre, fire. Alle disse pile er er ligesom et kort eller retninger, hvor hvis 90 is-- nu Jeg fik at tælle. 

Nul, en, to, tre, fire, fem, seks, syv. Det ser ud til 90 er på hukommelse adresse nummer syv. Alle disse pile er er som en lille lap papir der er at give anvisninger til program, der siger at følge dette kort at komme til placering syv. Og der vil du finde studerendes anden quiz score. I mellemtiden er den 75-- hvis jeg fortsætter dette, dette er syv, otte, ni, 10, 11, 12, 13, 14, 15. 

Denne anden pil bare repræsenterer et kort til hukommelsesplacering 15. Men igen, programmøren generelt gør ikke bekymre sig om dette niveau af detaljer. Og i de fleste hver programmering sprog i dag, programmøren vil ikke engang, hvor i hukommelsen disse tal egentlig er. Alt, hvad han eller hun har at bekymre sig om, er at de på en måde er bundet sammen i en datastruktur som denne. 

Men det viser sig ikke at få alt for teknisk. Men bare fordi vi kan måske råd til at have denne diskussion her, antage, at vi revidere dette problem her af et array. Lad os se, om vi beklager går her. Dette er 100, 90, 75, og 80. 

Lad mig kort gøre denne påstand. Dette er et array, og igen, iøjnefaldende egenskab ved et array er, at alle dine data er tilbage til ryg mod ryg i memory-- bogstaveligt én byte eller måske fire bytes, nogle fast antal bytes væk. I en sammenkædet liste, som vi kunne trække som dette, under hætten, der ved, hvor at ting er? Det behøver ikke engang at flyde som dette. Nogle af dataene kunne være tilbage til venstre op dér. Du behøver ikke engang kender. 

Og så med et array, du har en funktion kaldet random access. Og hvad random access midler er at computeren kan springe øjeblikkeligt til enhver placering i et array. Hvorfor? Fordi computeren ved at den første placering er nul, et, to, og tre. 

Og så hvis du ønsker at gå fra dette element til det næste element, du bogstaveligt talt, i computers sind, bare tilføje en. Hvis du ønsker at gå til det tredje element, blot tilføje en-- næste element, bare tilføje en. Men i denne version af historien, formoder computeren er i øjeblikket på udkig ved eller beskæftiger sig med nummer 100. Hvordan du kommer til det næste lønklasse i karakterbogen? 

Du er nødt til at tage syv trin, som er vilkårlig. For at komme til den næste, skal du tage yderligere otte trin for at komme til 15. Med andre ord, det er ikke en konstant afstand mellem tallene, og så det bare tager den computeren mere tid er det punkt. Computeren har for at søge gennem hukommelse for at finde det, du leder efter. 

Så mens et array tendens til at være en hurtige data structure-- fordi du kan bogstaveligt talt bare gøre simple aritmetiske og få, hvor du vil ved at tilføje en, til instance-- en sammenkædet liste, du ofrer denne funktion. Du kan ikke bare gå fra første til anden til tredje til fjerde. Du er nødt til at følge kortet. Du er nødt til at tage flere skridt at komme til de værdier, som synes at være at tilføje en omkostning. Så vi betaler en pris, men hvad var den funktion, Dan søgte her? Hvad betyder en linket liste tilsyneladende tillade os at gøre, som var oprindelsen til denne historie? 

Nøjagtig. En dynamisk størrelse til den. Vi kan tilføje til denne liste. Vi kan endda skrumpe listen, så at vi kun bruger så meget hukommelse som vi rent faktisk ønsker, og så vi er aldrig over-fordeling. 

Nu bare for at være virkelig nit-betyder, der er en skjult omkostning. Så du skal ikke bare lade mig overbevise dig, at dette er en overbevisende afvejning. Der er en anden skjulte omkostninger her. Fordelen, at være klar, er, at vi får dynamik. Hvis jeg vil et andet element, kan jeg bare trække det og sætte et nummer derinde. Og så kan jeg linke det med et billede her, mens herovre, igen, hvis jeg har malede mig i et hjørne, hvis noget andet er allerede bruger hukommelsen her, jeg er ude af lykke. Jeg har malet mig ind i hjørnet. 

Men hvad er den skjulte koste i dette billede? Det er ikke kun det beløb, tid, det tager at gå fra her til her, hvilket er syv trin, så otte trin, hvilket er mere end én. Hvad er en anden skjulte omkostninger? Ikke bare tid. Yderligere oplysninger er nødvendigt for at nå dette billede. 

Ja, det kort, de små papirlapper papir, som jeg holder beskriver dem som. Disse arrows-- de er ikke gratis. En computer-- du kender hvad en computer har. Det har nuller og ettaller. Hvis du ønsker at repræsentere en pil eller et kort eller et nummer, du har brug for noget hukommelse. Så den anden pris, du betale for en forbundet liste, en fælles computer science ressource, er også plads. 

Og faktisk så, så almindeligt, blandt kompromiser i at designe software engineering systemer er tid og space-- er to af dine ingredienser, to af dine mest kostbare ingredienser. Dette koster mig mere tid fordi jeg er nødt til at følge dette kort, men det er også koster mig mere plads fordi jeg nødt til at holde dette kort rundt. Så det håb, som vi har slags drøftede i går og i dag, er, at fordelene vil opveje omkostningerne. 

Men der er ingen oplagte løsning her. Måske er det better-- a la hurtig og beskidt, som Kareem foreslog earlier-- at kaste hukommelse på problemet. Bare købe mere hukommelse, tror mindre hårdt om at løse problemet, og løse det på en lettere måde. Og faktisk tidligere, da vi talte om kompromiser, det ikke var plads i computeren og tid. Det var udvikleren tid, som er endnu en ressource. 

Så igen, det er denne balancegang forsøger at beslutte, hvilke af disse ting er du villig til at betale? Hvilket er den billigste? Hvilket giver de bedre resultater? Ja? 

Ja. I dette tilfælde, hvis du er repræsenterer numre i maps-- disse kaldes på mange sprog "pointers" eller "adresser" - det er dobbelt plads. Det behøver ikke være så slemt som dobbelt, hvis lige nu er vi bare opbevaring numre. Antag, at vi opbevaring patientjournaler i en hospital-- så Pierson navne, telefonnumre, CPR-numre, læge historie. Denne boks kan være meget, meget større, i hvilket tilfælde en lille smule pointer, adressen på den næste element-- det er ikke en big deal. Det er sådan en marginal koster det gør ikke noget. Men i dette tilfælde, ja, det er en fordobling. Godt spørgsmål. 

Lad os tale om gang en lidt mere konkret. Hvad er køretiden søge denne liste? Antag jeg ønskede at søge gennem alle de studerendes kvaliteter, og der er n kvaliteter i denne datastruktur. Også her kan vi låne ordforråd tidligere. Dette er en lineær datastruktur. 

Big O i n er, hvad der kræves for at få til slutningen af ​​denne datastruktur, whereas-- og vi har ikke set dette before-- et array giver dig hvad der kaldes konstant tid, hvilket betyder, et trin eller to trin eller 10 steps-- betyder ikke noget. Det er et fast antal. Det har intet at gøre med størrelsen af ​​array. Og grunden til, at igen, er random access. Computeren kan bare straks hoppe til en anden placering, fordi de er alle de samme afstand fra alt andet. Der er ingen tænkning involveret. Okay. Så hvis jeg kan, så lad mig prøve at male to sidste billeder. En meget almindelig en såkaldt hash tabel. Så for at motivere denne diskussion, lad mig tænke over, hvordan du gør dette. 

Så hvad med dette? Antag, at problemet vi ønsker at løse nu gennemfører i en dictionary-- så en hel masse engelske ord eller hvad. Og målet er at være i stand til at besvare spørgsmål af formen er det et ord? Så du ønsker at gennemføre en stavekontrol, bare som en fysisk ordbog at du kan se tingene op i. Antag jeg skulle gøre dette med et array. Jeg kunne gøre dette. 

Og formoder ordene er æble og banan og cantaloupe. Og jeg kan ikke tænke på frugt som starter med d, så vi er bare vil have tre frugter. Så dette er en matrix, og vi er lagring af alle disse ord i denne ordbog som en matrix. Spørgsmålet er så, hvordan ellers kunne du gemme disse oplysninger? 

Nå, jeg slags snyd her, fordi hver af disse bogstaver i ordet er virkelig en individuel byte. Så hvis jeg virkelig ønskede at være nit-betyder, bør jeg virkelig være at opdele dette op i meget mindre bidder af hukommelse, og vi kunne gøre netop dette. Men vi kommer til at løbe ind i det samme problem som før. Hvad nu hvis, som Merriam Webster eller Oxford gør hvert year-- de tilføje ord til dictionary-- vi ikke nødvendigvis ønsker at male os selv i et hjørne med et array? 

Så i stedet, måske en smartere tilgang er at sætte æble i sin egen node eller kasse, som vi ville sige, banan, og så her har vi cantaloupe. Og vi strengen disse ting sammen. Så dette er matrixen, og dette er den linkede liste. Hvis du ikke kan helt se, det bare siger "matrix", og det siger "liste." 

Så vi har den samme præcise spørgsmål som før, hvorved vi nu har dynamik i vores linkede liste. Men vi har en temmelig langsom ordbog. Antag jeg ønsker at se et ord op. Det kan tage mig store O i n trin, fordi ordet måske være hele vejen ved udgangen af listen, ligesom cantaloupe. Og det viser sig, at i programmering, sortere af den hellige gral af data strukturer, er noget der giver dig konstant tid som et array men som stadig giver dig dynamik. 

Så kan vi få det bedste fra begge verdener? Og ja, der er noget kaldet hash tabellen der tillader dig at gøre præcis der, selv tilnærmelsesvis. En hash tabel er en mere avanceret datastruktur, vi kan tænke på som kombination af en array-- og jeg har tænkt mig at trække det ligesom denne-- og hægtede lister at jeg vil trække på denne måde herovre. 

Og den måde, denne ting værker er som følger. Hvis dette nu-- hash table-- er min tredje datastruktur, og jeg vil gemme ord i denne, det gør jeg ikke bare ønsker at gemme alle de ord tilbage til tilbage til tilbage til tilbage. Jeg ønsker at udnytte nogle stykke information om de ord, der vil lade mig med at få det, hvor det er hurtigere. 

Så givet ord æble og banan og melon, Jeg valgte bevidst disse ord. Hvorfor? Hvad er slags fundamentalt anderledes ved de tre? Hvad er det indlysende? De starter med forskellige bogstaver. 

Så ved du hvad? I stedet lægge alle mine ord i den samme spand, så at sige, ligesom i en stor liste, hvorfor ikke Jeg i det mindste prøve en optimering og gøre mine lister 1/26 så længe. En overbevisende optimering måske hvorfor ikke Jeg-- når du sætter et ord i denne datastruktur, i computerens hukommelse, hvorfor jeg ikke sætte alle a-ord her, alle de B-ord her, og alle C-ord her? Så det ender med at sætte et æble her, banan her, cantaloupe her, og så videre. 

Og hvis jeg har en ekstra ord like-- hvad er en anden? Apple, banan, pære. Nogen tænker på en frugt der starter med a, b eller c? Blueberry-- perfekt. Det kommer til at ende op her. Og så vi synes at have en marginalt bedre opløsning, fordi nu hvis jeg vil at søge efter æble, jeg first-- jeg ikke bare dykke ind i min datastruktur. Jeg kan ikke dykke ned i min computers hukommelse. Jeg først se på det første bogstav. 

Og dette er, hvad en computer videnskabsmand ville sige. Du hash ind i din datastruktur. Du tager dit input, der i dette tilfælde er et ord som æble. Du analyserer det, ser på det første bogstav i denne sag, hvorved hashing det. Hashing er en generel betegnelse, hvorved du tager noget som input og du producerer nogle output. Og outputtet ved, at tilfælde er placeringen du vil søge, den første beliggenhed, anden placering, tredje. Så indgangen er æble, produktionen er først. Inputtet er banan, den output skal være andet. Inputtet er cantaloupe, output bør være tredjedel. Inputtet er blåbær, den output skal igen være andet. Og det er, hvad hjælper du tager genveje gennem din hukommelse for at komme til ord eller data mere effektivt. 

Nu skærer ned vores tid potentielt med så meget som en ud af 26, fordi hvis du antager, at du have så mange "a" ord som "z" ord som "Q" ord, som er egentlig ikke realistic-- du kommer til at have skew tværs visse bogstaver i alphabet-- men dette ville være en trinvis tilgang, der tillader dig at komme til ord meget hurtigere. Og i virkeligheden, en sofistikeret programmet, Googles af verden, Den Facebooks af verden- de ville bruge en hash tabel for mange forskellige formål. Men de ville ikke være så naive, bare se på det første bogstav i æble eller banan eller pærer eller cantaloupe, fordi som du kan se disse lister kan stadig få lange. 

Og så dette kan stadig være sort af linear-- så slags langsom, Ligesom med den store O i n at vi diskuterede tidligere. Så hvad en rigtig god hash tabel vil do-- det vil have en meget større array. Og det vil bruge en langt mere sofistikeret hashingfunktion, så det ikke bare se på "a". Måske ser på "en-p-p-l-e" og en eller anden måde omdanner disse fem bogstaver i den placering, hvor æble skal opbevares. Vi er lige naivt at bruge bogstavet »a« alene, fordi det er rart og enkel. 

Men en hash tabel, i sidste ende, kan du tror som en kombination af et array, som hver har en sammenkædet liste, der ideelt set bør være så kort som muligt. Og dette er ikke en indlysende løsning. Faktisk er meget af finindstillingen der foregår under kølerhjelmen, når gennemførelsen af ​​disse former for sofistikerede datastrukturer er det, er den rigtige længden af ​​array? Hvad er den rigtige hash funktion? Hvordan gemme ting i hukommelsen? 

Men indse, hvor hurtigt denne form for diskussion eskalerede, enten så langt, at det er sådan af over hovedet på dette tidspunkt, som er fint. Men vi startede, husker, med virkelig noget lavt niveau og elektronisk. Og så det igen er dette temaet abstraktion, hvor når du begynder at tage for givet, OK, har jeg fået it-- der er fysisk hukommelse, OK, fik det, hver fysiske placering har en adresse, OK, jeg fik det, kan jeg repræsenterer disse adresser som arrows-- kan du meget hurtigt begynde at have mere sofistikerede samtaler, i sidste ende synes at være at lade os til at løse problemer som søger og sortering mere effektivt. Og være sikker på, too-- fordi jeg tror, ​​det er den dybeste vi har gået ind i nogle af disse CS emner proper-- vi ve gøres på en dag og en halv på dette pege hvad du måske typisk gøre løbet løbet af otte uger i et semester. 

Eventuelle spørgsmål om disse? Ingen? Okay. Tja, hvorfor vi ikke pause der, starte frokost et par minutter tidligt, genoptages i næsten en time? Og jeg vil blive hængende i lidt med spørgsmål. Så jeg har tænkt mig at have til at gå tage et par opkald, hvis det er OK. Jeg vil tænde noget musik i mellemtiden, men frokost skal være rundt om hjørnet.