DAVID MALAN: Okej. Vi är tillbaka. Så i detta segment på programmering vad Jag trodde vi skulle göra är en blandning av saker. En gör lite något hands-on, om än med hjälp av en mer lekfull programmering environment-- en som är demonstrativa av exakt vilka typer av idéer vi har talat om, men lite mer formellt. Två, titta på några av de mer tekniska sätt att en programmerare faktiskt skulle lösa problem som den söker problem att vi tittat på tidigare och också en mer fundamentalt intressant problem att sortera. 

Vi har just antagit från get gå att denna telefonbok sorterades, men att ensam är faktiskt typ av en hård problem med många olika sätt att lösa det. Så vi kommer att använda dessa som en klass av problem representativ för saker som kan lösas i allmänhet. Och då kommer vi att tala om i detalj vad kallas uppgifter structures-- finare sätt som länkade listor och hashtabeller och träd som en programmerare skulle faktiskt använda och allmänt använda på en whiteboard för att måla en bild av vad han eller hon föreställer sig för att genomföra någon mjukvara. 

Så låt oss göra hands-on del först. Så bara få händerna smutsiga med en miljö kallas scratch.mit.edu. Detta är ett verktyg som vi använder i vårt grundklass. Även om den är utformad för åldrarna 12 och uppåt, Vi använder det för upp en del av detta ganska lite eftersom det är en trevlig, rolig grafiskt sätt att lära lite om programmering. Så bege dig till webbadressen där du bör se en sida ganska så här, och gå vidare och klicka Gå med Scratch uppe till höger och välja ett användarnamn och ett lösenord och i slutändan få dig en account-- scratch.mit.edu. Jag trodde jag skulle använda detta som en tillfälle först att visa detta. En fråga kom upp i pausen om vilken kod som faktiskt ser ut. Och vi talade pausen om C, i particular-- speciellt en lägre nivå i en äldre språk. Och jag gjorde bara en snabb Google-sökning för att hitta C-kod för binär sökning, den algoritm som vi används för att söka att telefonboken tidigare. Detta speciella exempel, naturligtvis, inte söka en telefonbok. Den söker bara en massa nummer i datorns minne. Men om du vill bara få en visuell känsla av vad en verklig programmering språket ser ut, ser det en liten sak som denna. Så det handlar om 20-plus, 30-tal rader kod, men samtalet vi hade över paus handlade om hur detta faktiskt blir förvandlats till nollor och ettor och om du inte bara kan återställa det bearbeta och gå från nollor och ettor tillbaka till koden. 

Tyvärr, processen är så omvandlande att det är mycket lättare sagt än gjort. Jag gick vidare och faktiskt visade det programmet, Binary Search, i nollor och ettor i form av en program som kallas kompilatorn som jag råkar ha här rätt på min Mac. Och om man tittar på skärmen här, med särskild inriktning på dessa mitten sex kolumner endast du ser bara nollor och ettor. Och de är nollor och ettor som komponera exakt som söker programmet. 

Och så varje bit av fem bitar, varje byte av nollor och ettor här, representerar några instruktion typiskt insidan av en dator. Och i själva verket, om du har hört marknadsföring slogan "Intel inside" - det, Naturligtvis betyder bara att du har en Intel CPU eller hjärnan inuti datorn. Och vad det betyder att vara en CPU är att du har en instruktionsuppsättning, så att säga. 

Varje CPU i världen, många av dem gjordes av Intel dessa dagar, förstår en ändlig antal instruktioner. Och dessa instruktioner är så låg nivå som lägga till dessa två siffror tillsammans, multiplicera dessa två siffror tillsammans, flytta denna bit data härifrån hit i minnet, spara Information härifrån till här i minnet, och så forth-- så mycket, mycket låg nivå, nästan elektroniska detaljer. Men med de matematiska operationer kopplade med vad vi diskuterat tidigare, representation av data som nollor och ettor, kan du bygger upp allt att en dator kan göra idag, om det är text, grafisk, musikal, eller annars. 

Så detta är mycket lätt att få vilse i ogräs snabbt. Och det finns en hel del syntaktiska utmaningar där om du gör det enklaste, stupidest stavfel ingen av programmet kommer att fungera alls. Och så istället för att använda en språk som C i morse, Jag trodde det skulle vara roligare att faktiskt göra något mer visuella, som medan avsedd för barn är faktiskt en perfekt manifestation med en verklig programmering language-- bara råkar använda bilder istället för text att representera dessa idéer. 

Så när du verkligen har en konto på scratch.mit.edu, klicka på knappen Skapa överst till vänster på webbplatsen. Och du bör se en miljö som den jag är på väg att se på min skärm här. Och vi kommer att tillbringa bara lite lite tid att spela här. Låt oss se om vi inte alla kan lösa några problem tillsammans på följande sätt. 

Så vad du ser i detta environment-- och faktiskt bara låta mig paus. Är det någon som inte här? Inte här? OK. Så låt mig påpeka några egenskaperna hos denna miljö. 

Så längst upp till vänster på skärmen, vi har Scratch scen, så att säga. Scratch är inte bara namnet av denna programmeringsspråk; Det är också namnet på katten som du ser som standard där i orange. Han är på en scen, så mycket som jag beskrev sköldpaddan tidigare som i en rektangulär whiteboard miljö. Denna katt värld begränsas helt som rektangel uppe där. 

Samtidigt, på höger sidan här är det bara ett skript område, en oskrivet blad om du vill. Det är där vi kommer att skriva våra program på bara ett ögonblick. Och de byggstenar som vi skall använder för att skriva detta program-- pusslet bitar, om du will-- är de här i mitten, och de är kategoriserade av funktionalitet. Så, till exempel, kommer jag att gå vidare och visa åtminstone en av dessa. Jag kommer att gå vidare och klicka kontroll kategorin där uppe. 

Så dessa är de kategorier där uppe. Jag kommer att klicka på kategoristyrning. Snarare kommer jag att klicka på Händelser kategori, den allra första en där uppe. Och om du vill följa med som vi gör detta, är du mycket välkommen till. Jag kommer att klicka och dra detta första ", när grön flagg klickade." Och då kommer jag att släppa det bara ungefär på toppen av min tomma skiffer. 

Och vad är trevligt om Scratch är att denna pusselbit när sammankopplad med andra pussel bitar, kommer att göra bokstavligen vad dessa pusselbitar säger att göra. Så, till exempel, är Scratch rätt nu i mitten av hans värld. Jag kommer att gå vidare och välja nu, låt oss säga, Motion kategori, Om du vill göra same-- Motion kategori. Och nu märker jag har en hel massa pusselbitar här att, återigen, typ av gör vad de säger. Och jag kommer att gå vidare och dra och släppa flytta blocket här borta. 

Och märker att så fort du får nära botten av de "gröna flaggan klickade "-knappen, meddelande hur en vit linje visas, som om det är nästan magnetisk, vill att det ska gå dit. Bara släppa taget, och det kommer att gå tillsammans och formerna kommer att matcha. Och nu kan du kanske nästan gissa om vi är på väg med detta. 

Om man tittar på Scratch stadiet hit och se till toppen av det, du ser ett rött ljus, en stoppskylt, och en grön flagga. Och jag kommer att gå vidare och titta på mina Screen-- för ett ögonblick, om du kunde. Jag kommer att klicka på gröna flaggan just nu, och han flyttade vad som verkar vara 10 steg eller 10 pixlar, 10 prickar, på skärmen. 

Och så inte så spännande, men låt mig föreslå utan att ens lära detta, bara med hjälp av egen din egen intuition-- låt mig föreslår att du räkna ut hur man göra Scratch gå precis utanför scenen. Har honom ge plats åt den högra sidan av skärmen, hela vägen till höger. Låt mig ge dig en stund eller så att brottas med. Du kanske vill ta en titt vid andra typer av block. Okej. Så bara för att sammanfatta, när vi har den gröna flaggan klickade här och flytta 10 steg är bara instruktion, varje gång jag klicka på den gröna flaggan, vad som händer? Tja, som körs mitt program. Så jag kunde göra detta kanske 10 gånger manuellt, men det känns lite bitars hackish, så att säga, där jag är inte riktigt att lösa problemet. Jag försöker bara igen och igen och igen och igen tills jag slags misstag uppnå direktivet att jag föresatt sig att uppnå tidigare. 

Men vi vet från vår pseudokod tidigare att det finns detta begrepp i programmering av looping, gör något om och om igen. Och så såg jag att ett gäng du sträckte sig efter vad pusselbit? Upprepa tills. Så vi kunde göra något som upprepas tills. Och vad gjorde du upprepa tills exakt? 

OK. Och låt mig gå med en som är något enklare för ett ögonblick. Låt mig gå vidare och göra det. Lägg märke till att du kan ha upptäckt under kontroll, det är denna upprepning block, vilket ser inte ut som det är så stor. Det finns inte mycket utrymme i mellan dessa två gula linjer. Men som en del av er kanske har märkt, om du dra och släppa, märker hur det växer för att fylla formen. 

Och du kan även klämma mer. Det ska bara fortsätta växa om du drar och sväva över den. Och jag vet inte vad som är bäst här, så låt mig åtminstone upprepa fem gånger, för Exempelvis och sedan gå tillbaka till scenen och klicka på den gröna flaggan. Och nu märker det inte riktigt där. 

Nu några av er föreslås som Victoria just gjorde, upprepa 10 gånger. Och som i allmänhet gör få honom hela vägen, men skulle det inte finnas en mer robust sätt än godtyckligt räkna ut hur många drag att göra? Vad kan vara en bättre kvarter än upprepa 10 gånger vara? 

Ja, så varför inte göra något för evigt? Och nu vill jag flytta pusselbit därinne och bli av med detta. Nu märker oavsett var Scratch startar, går han till kanten. Och tack och lov MIT, som gör Scratch, bara ser till att han aldrig försvinner helt. Du kan alltid ta svansen. 

Och bara intuitivt, varför han hålla sig i rörelse? Vad händer här? Han verkar ha stannat, men sedan om jag plocka upp och dra han håller vilja gå dit. Varför är det så? Sannerligen, är en dator bokstavligen kommer att göra det du ber den att göra. Så om du berättade det tidigare göra Följande sak för evigt, flytta 10 steg, det kommer att hålla på och gå tills jag slog den röda stoppskylt och stoppa programmet helt och hållet. 

Så även om du inte gör det, hur kunde jag göra Scratch flytta snabbare över skärmen? Fler steg, eller hur? Så istället för att göra 10 vid en tid, varför inte vi gå vidare och ändra det att-- vad skulle du propose-- 50? Så nu ska jag klicka på den gröna flagga, och faktiskt, går han riktigt snabbt. 

Och detta är naturligtvis bara en manifestation av animation. Vad är animation? Det är bara visar dig människa en massa stillbilder verkligen, riktigt, riktigt snabbt. Och så om vi bara berättar honom att flytta flera steg, vi bara har effekten vara att förändring där han är på skärmen allt snabbare per tidsenhet. 

Nu nästa utmaning som jag föreslog var att ha honom studsa kanten. Och utan att veta vad pussel bitar exist-- eftersom det är bra om du inte får till skede av challenge-- vad vill du göra intuitivt? Hur skulle vi ha honom studsa tillbaka och framåt, mellan vänster och höger? 

Ja. Så vi behöver någon form av tillstånd, och vi verkar ha villkorssatser, så att tala, under kategorin Control. Vilken av dessa block vi förmodligen vill? Ja, kanske "om, då." Så märker att bland de gula blocken vi har här, det är detta "om" eller detta "om, annars" block som kommer tillåter oss att fatta ett beslut att göra detta eller att göra det. Och du kan även bo dem att göra flera saker. Eller om du inte har gått här ännu, gå vidare till Sensing kategori och-- låt oss se om det är här. 

Så vad blocket kan vara till hjälp här att upptäcka om han är utanför scenen? Ja, märker att vissa av dessa block kan parametrized, så att säga. De kan slags anpassas, inte Till skillnad från HTML igår med attribut, där dessa attribut typ av skräddarsy beteendet hos en tagg. På samma sätt här, kan jag ta tag i detta gripande blocket och förändring och ställa frågan, du röra musen pekare som markören eller är du vidrör kanten? 

Så låt mig gå in och göra detta. Jag kommer att zooma ut för ett ögonblick. Låt mig ta denna pusselbit här, denna pusselbit detta, och jag kommer att virrvarr dem för ett ögonblick. Jag kommer att flytta, ändra detta till beröring kant, och jag ska rörelse göra detta. Så här är några ingredienser. Jag tror att jag har allt jag vill ha. 

Skulle någon vilja föreslå hur jag kan ansluta dessa kanske toppen till botten i syfte att lösa problemet med att ha Scratch flytta från höger till vänster till höger för att vänster till höger till vänster, varvid varje tid bara studsade väggen? Vad vill jag göra? Vilket block ska jag ansluta till "När grön flagg klickade först"? 

OK, så låt oss börja med "evigt." Vad går in nästa? Någon annan. OK, flytta steg. Okej. Sen då? Så då om. Och lägg märke till, även om det ser inklämt tillsammans tätt, Det kommer bara att växa för att fylla. Det kommer bara att hoppa i där jag vill ha det. 

Och vad lägger jag mellan if och då? Förmodligen "om att röra kanten." Och meddelande, återigen, det är för stor för det, men det kommer att växa för att fylla. Och sedan vända 15 grader? Hur många grader? Ja, så 180 kommer att snurra mig hela vägen runt. Så låt oss se om jag fick denna rätt. Låt mig zooma ut. 

Låt mig dra Scratch upp. Så han är lite förvrängd nu, men det är bra. Hur kan jag återställa honom lätt? Jag kommer att fuska lite. Så jag lägga till en annan kvarter, bara för att vara tydlig. Jag vill att han ska peka 90 grader till höger som standard, så jag ska bara tala om för honom att göra det programmatiskt. Och nu kör vi. Vi verkar ha gjort det. Det är lite konstigt, eftersom han går upp och ned. Låt oss kalla det en bugg. Det är ett misstag. En bugg är ett misstag i ett program, en logiskt fel som jag, människan, gjort. Varför han går upp och ner? Har MIT skruva upp eller gjorde jag? 

Ja, jag menar, det är inte MIT: s fel. De gav mig en pusselbit som säger vända ett visst antal grader. Och på Victoria förslag, Jag vänder 180 grader, vilket är den rätta intuition. Men att vända 180 grader bokstavligen innebär att vrida 180 grader, och det är inte riktigt vad jag vill, tydligen. Eftersom åtminstone är han i Detta tvådimensionella värld, så vänd verkligen kommer att vända honom upp och ned. 

Jag vill nog att använda det blocket istället, baserat på vad du ser här? Hur kan vi åtgärda detta? Ja, så vi kunde peka i den motsatta riktningen. Och faktiskt även det är kommer inte att vara tillräckligt, eftersom vi bara kan hårdkoda att peka åt vänster eller höger. 

Du vet vad vi kan göra? Det ser ut som vi har en bekvämlighet blocket här. Om jag zooma in, se något som vi vill här? Så det ser ut som MIT har en abstraktion inbyggd här. Detta block verkar vara likvärdiga till vilka andra block, plural? 

Detta ett kvarter verkar vara likvärdiga att hela denna trio av block att vi har här. Så visar det sig jag kan förenkla mitt program genom att bli av med allt detta och bara sätta detta här. Och nu är han fortfarande en liten buggy, och det är bra för nu. Vi lämnar det vara. Men mitt program är även enklare, och även detta skulle vara representativa av ett mål i programming-- är att helst göra din kod som enkel, så kompakt som möjligt, medan det fortfarande är så läsbar som möjligt. Du vill inte göra det så kortfattad att det är svårt att förstå. 

Men märker jag har ersatt tre block med ett, och det är utan tvekan en bra sak. Jag har abstraherat bort begreppet kontrollera om du är på kanten med bara ett kvarter. Nu kan vi ha kul med detta, faktiskt. Detta lägger inte så mycket intellektuell värde men lekfull värde. Jag kommer att gå vidare och ta detta ljud här. Så låt mig gå vidare, och låt mig stoppa programmet för ett ögonblick. Jag kommer att spela in följande, ger tillgång till min mikrofon. 

Nu kör vi. Aj. Låt oss prova det här igen. Nu kör vi. OK, inspelad jag fel. Nu kör vi. Aj. Aj. Okej. Nu behöver jag att bli av med det. Okej. 

Så nu har jag en inspelning av bara "aj". Så nu ska jag gå framåt och kallar detta "aj". Jag kommer att gå tillbaka till mina manus, och nu meddelande finns det block som kallas spela upp ljud "mjau" eller spela upp ljud "AJ." Jag kommer att dra detta, och där ska jag sätta detta för komisk effekt? Ja, så nu är det slags buggy, eftersom nu detta block-- Lägg märke till hur detta "om på kanten, bounce "är typ av fristående. Så jag behöver för att fixa detta. Låt mig gå vidare och göra det. Låt mig bli av med detta och gå tillbaka till vår ursprungliga, mer medvetet funktionalitet. Så "om att röra kant, då" Jag vill att vända, som Victoria föreslog 180 grader. Och jag vill spela ljudet "aj" där? 

Ja, märker att den finns utanför det gula blocket. Så här skulle också vara en bugg, men jag har märkt det. Så jag kommer att dra upp här, och meddelande nu är det inne i "om". Så "om" är denna typ av liknande armliknande blot Det är bara att gå till göra det som är inne i det. Så nu om jag zoomar ut på risken för annoying-- 

DATOR: Aj, aj, aj. 

DAVID MALAN: Och det kommer bara fortsätta för evigt. Nu är det bara att påskynda saker här, låt mig gå vidare och öppna upp, låt oss säga-- låta mig gå till några av mina egna grejer från klass. Och låt mig öppna upp, låt oss säga, detta som gjorts av en av våra undervisningsassistenter för några år sedan. Så några av er kanske kommer ihåg det här spelet från förr, och det är faktiskt anmärkningsvärt. Även om vi har gjort enklaste program just nu, låt oss betrakta vad detta faktiskt ser ut. Låt mig slå play. 

Så i det här spelet, vi har en groda, och med hjälp av pilen keys-- han tar större steg än jag remember-- Jag har kontroll över denna groda. Och målet är att komma över upptagen väg utan att köra in i bilar. Och låt oss see-- om jag går upp här, jag måste vänta på en stock för att rulla förbi. Detta känns som en bugg. Detta är lite av en bugg. Okej. Jag är på det här, det, och sedan hålla tills du får alla grodorna till lily pads. Nu kan se desto mer komplexa, men låt oss försöka bryta detta ned mentalt och verbalt i sina komponentblock. Så det är förmodligen ett pussel pjäs som vi inte har sett ännu men som svarar på tangenttryckningar, till saker som jag träffade på tangentbordet. 

Så det är förmodligen något slags block som säger, om nyckel är lika med upp, sedan göra något med Scratch-- kanske flyttar den 10 steg på detta sätt. Om ned tangenten trycks, flytta 10 steg detta sätt, eller vänsterknappen, flyttar 10 steg detta sätt, 10 steg det. Jag har klart vände katten till en groda. Så det är just där dräkt, som Scratch samtal det-- vi bara importerat en bild av grodan. 

Men vad händer? Vilka andra rader kod, vad andra pusselbitar gjorde Blake, vår undervisning karl, användning i det här programmet, tydligen? Vad gör allt move-- vad programmering konstruera? 

Rörelse, sure-- så flytta block för säker. Och vad är det drag blocket insida, mest troligt? Ja, någon form av slingan, kanske en evigt blockera kanske en upprepning block-- Upprepa tills blocket. Och det är vad som gör stockarna och lily pads och allt annat drag fram och tillbaka. Det är bara händer i all oändlighet. 

Varför är några av bilarna rör sig snabbare än de andra? Vad är annorlunda om dessa program? Ja, förmodligen några av dem tar flera steg på en gång och en del av dem färre steg på en gång. Och den visuella effekten är snabb jämfört med långsam. 

Vad tror du hände? När jag fick min groda hela vägen tvärs över gatan och floden på näckrosblad, något anmärkningsvärd hände. Vad hände så fort jag gjorde det? Det slutade. Det groda stoppas, och Jag fick en andra groda. Så vad konstruktion måste vara används där, vad funktionen? 

Ja, så det finns någon form av "Om" skick upp där också. Och det visar out-- vi inte se this-- men det finns andra block i det att kan säga, om du vidrör en annan sak på skärmen, Om du vidrör lily pad "och sedan". Och då det är då vi göra andra grodan visas. Så även om det här spelet är verkligen mycket daterat, även om det vid första anblicken Det finns så mycket att gå on-- och Blake inte piska upp detta i två minuter, det förmodligen tog honom flera timmar för att skapa detta spel baserat på hans minne eller video från förr version av det. Men alla dessa små saker gå på skärmen i isolering koka ner till dessa mycket enkel constructs-- rörelser eller uttalanden som vi har diskuterat, loopar och förhållanden, och det är om detta. Det finns några andra finare funktioner. Några av dem är rent estetiska eller akustisk, som ljudet Jag spelade just med. Men för det mesta, du har på detta språk, Scratch, alla av den fundamentala byggstenar som du har i C, Java, JavaScript, PHP, Ruby, Python, och ett antal andra språk. Eventuella frågor om Scratch? Okej. Så vi kommer inte att dyka djupare till Scratch, om du är välkommen här helgen, särskilt om du har barn eller syskonbarn och sådant, att introducera dem till noll. Det är faktiskt en underbart lekfull miljö med, som författarna säger, mycket högt i tak. Även om vi började med mycket låg nivå detaljer, du verkligen kan göra en hel del med det är och detta kanske en demonstration av just detta. 

Men låt oss nu övergå till några mer sofistikerade problem, om man så vill, känd som "söker" och "Sortering" mer generellt. Vi hade den här telefonboken earlier-- här är en annan bara för discussion-- att vi kunde söka mer effektivt eftersom av en betydande antagande. Och bara för att vara tydlig, vad antagande var jag göra när du söker igenom denna telefonbok? Att Mike Smith var i telefonboken, även om jag skulle kunna hantera scenariot utan honom det om jag bara slutade i förtid. Boken är alfabetisk. Och det är en mycket generös antagande, eftersom det innebär someone-- Jag är typ att skära ett hörn, som jag är snabbare eftersom någon annars gjorde en hel del hårt arbete för mig. 

Men vad händer om telefonen boken var osorterade? Kanske Verizon fick lata, bara kastade allas namn och nummer i det kanske i den ordning i vilken de registrerat dig för telefon. Och hur mycket tid tar det mig att hitta någon som Mike Smith? 1000 sida telefon book-- hur många sidor måste jag titta igenom? 

Allihopa. Du sorts av lycka. Du har bokstavligen att titta på varje sida om telefonboken är bara slumpvis sortering. Du kan ha tur och hitta Mike på första sidan, eftersom han var den första kunden beställa telefon. Men han kan ha varit den sista också. 

Så slumpmässig ordning är inte bra. Så antar att vi måste sortera telefonboken eller i allmänhet sorteringsuppgifter att vi har fått. Hur kan vi göra det? 

Nåväl, låt mig bara försöka ett enkelt exempel här. Låt mig gå vidare och kasta en några siffror på tavlan. Antag siffrorna vi har är, låt oss säga, fyra, två, ett och tre. Och Ben, sortera dessa siffror för oss. 

Okej bra. Hur gjorde du det där? Okej. Så börja med den minsta och det högsta, och det är riktigt bra intuition. Och inse att vi människor är faktiskt ganska bra på att lösa problem så här, åtminstone när data är relativt liten. Så snart du börjar få hundratals siffror, tusentals siffror, miljontals siffror, Ben förmodligen kunde inte göra det riktigt så snabbt, om man antar att det fanns luckor i siffrorna. Ganska lätt att räkna till en miljon annars, bara tidskrävande. 

Så algoritmen det låter som Ben används just nu var sökandet efter det minsta antalet. Så även om vi människor kan ta i en hel del information visuellt, en dator är faktiskt lite mer begränsad. Datorn kan bara titta på en byte i taget eller kanske fyra byte på en time-- dessa dagar kanske 8 byte på en time-- men ett mycket litet antal bitgrupper vid en given tidpunkt. 

Så med tanke på att vi verkligen har fyra separata värden här-- och du kan tänka på Ben ha skygglappar på om han var en dator så att han inte kan se något annat än en siffra i time-- så vi kommer i allmänhet att anta, som i Engelska, vi ska läsas från höger till vänster. Så det första numret Ben förmodligen såg på var fyra och sedan mycket snabbt insett att det är en ganska stor number-- låt mig hålla ute. 

Det finns två. Vänta en minut. Två är mindre än fyra. Jag kommer att minnas. Två är nu det minsta. Nu en-- det är ännu bättre. Det är ännu mindre. Jag kommer att glömma två och kom ihåg en nu. 

Och han kunde sluta titta? Jo, han kunde baserad på denna information, men han är bäst sökning resten av listan. För vad om noll var i listan? Vad händer om negativ var i listan? Han vet bara att hans svar är korrekt om han är uttömmande kontrolleras hela listan. Så vi ser på resten av detta. Three-- det var ett slöseri med tid. Fick otur, men jag var fortfarande rätt att göra det. Och så nu är han förmodligen valt det minsta antalet och bara lägga den i början av listan, som jag gör här. Nu vad gjorde du nästa, även om du inte tycker om det nästan i denna omfattning? Upprepa processen, så någon typ av loop. Det finns en välbekant idé. Så här är fyra. Det är för närvarande den minsta. Det är en kandidat. Inte längre. Nu har jag sett två. Det är den näst minsta elementet. Three-- det är inte mindre, så nu Ben kan plocka ut de två. 

Och nu har vi upprepa processen, och naturligtvis tre får dras ut nästa. Upprepa processen. Fyra blir utdragen. Och nu är vi av tal, så listan måste sorteras. 

Och faktiskt, är detta en formell algoritm. En datavetare skulle kallar detta "val Sortera" Tanken är sortera en lista iteratively-- igen och om och om igen att välja det minsta antalet. Och vad är trevligt om det är det är bara så jäkla intuitiv. Det är så enkelt. Och du kan upprepa samma drift och om igen. Det är enkelt. 

I detta fall den var snabb, men Hur lång tid tar det faktiskt ta? Låt oss göra det verkar och känner sig lite mer omständlig. Så en, två, tre, fyra, fem sex, sju, åtta, nio, tio, elva, tolv, tretton, 14, 15, 16-- godtyckligt antal. Jag ville bara mer här tid än bara fyra. Så om jag har en hel massa siffror now-- det inte ens någon roll vad de är-- låt oss tänka på vad detta algoritm är verkligen gillar. 

Antag att det är tal där. Återigen, ingen roll vad de är, men de är slumpmässigt. Jag ansöker Ben algoritm. Jag måste välja det minsta antalet. Vad gör jag? Och jag kommer att fysiskt gör den här gången att agera ut. Titta, titta, titta, titta, titta. Endast när jag kommer till i slutet av listan kan Jag inser minsta Antalet var två den här gången. Man är inte i listan. Så jag lägger ner två. 

Vad ska jag göra nu? Titta, titta, titta, titta. Nu hittade jag nummer sju, eftersom det finns luckor i dessa numbers-- men bara godtyckligt. Okej. Så nu kan jag lägga ner sju. Söker titta, titta. 

Nu jag antar, av naturligtvis att Ben inte har extra RAM, extra minne, därför att, naturligtvis, Jag tittar på samma nummer. Visst kunde jag ha kommit ihåg alla av dessa siffror, och det är helt sant. Men om Ben minns alla av numren han sett, han har verkligen inte gjort grundläggande framsteg eftersom han redan har möjligheten att söka igenom numren på tavlan. Komma ihåg alla de siffror inte hjälper, eftersom han kan fortfarande som en dator bara titta på, vi har sagt, ett antal vid en tid. Så det finns ingen typ av fusk det att du kan utnyttja. 

Så i verkligheten, som jag fortsätta söka listan, Jag har bokstavligen bara fortsätta fram och tillbaka genom det, plockning ut nästa minsta antalet. Och eftersom du kan sorts sluta från min dumma rörelser, detta bara blir mycket tråkiga mycket snabbt, och jag verkar vara att gå tillbaka och fram och tillbaka ganska lite. Nu för att vara rättvis, jag har inte gå riktigt lika, ja, låt oss see-- att vara rättvis, Jag behöver inte gå helt så många steg varje gång. Jo, naturligtvis, som jag välja nummer från listan, den återstående listan blir kortare. 

Och så låt oss tänka på hur många steg jag faktiskt traipsing genom varje gång. I den allra första läget Vi hade 16 nummer, och så maximally-- låt oss bara gör detta för en discussion-- Jag var tvungen att titta igenom 16 tal för att hitta den minsta. Men när jag plockade ut det minsta antalet, hur länge var den återstående listan, naturligtvis? Bara 15. Så hur många nummer gjorde Ben eller jag har att titta igenom den andra gången? 15, bara för att gå och hitta den minsta. Men nu, naturligtvis, är listan, Också mindre än det var innan. Så hur många steg gjorde jag måste ta nästa gång? 14 och sedan 13 och sedan 12, plus punkt, prick, pricka, tills jag kvar med bara en. Så nu datavetare skulle fråga, ja, vad gör att alla är lika? Det motsvarar faktiskt en del konkreta nummer som vi kunde säkert göra aritmetiskt, men vi vill prata om effektiviteten av algoritmer lite mer formulaically, oberoende av hur länge listan är. 

Och så vet du vad? Detta är 16, men som jag sade tidigare, Låt oss bara ringa storleken på problemet n, där n är något tal. Kanske är det 16, kanske det är tre, det är kanske en miljon. jag vet inte. Jag bryr mig inte. Vad jag verkligen vill är en formel som jag kan använda för att jämföra denna algoritm mot andra algoritmer att någon skulle kunna hävda är bättre eller sämre. 

Så visar det sig, och bara jag vet detta från skolan, att det faktiskt fungerar på samma sak som n över n plus en över två. Och det händer att lika, av Naturligtvis n kvadrat plus n över två. Så om jag ville ha en formel för hur många steg var inblandade i att titta på alla av dessa siffror och om igen och om och om igen, skulle jag säga det n kvadrat plus n över två. Men vet du vad? Detta ser bara rörigt. Jag verkligen vill ha en allmän känsla av saker. Och du kanske kommer ihåg från high school att det är begreppet högsta ordningens term. Vilket av dessa termer, n kvadrat, n, eller halv, har störst effekt över tid? Ju större n blir, som av dessa frågor mest? 

Med andra ord, om jag kopplar i en miljon, n kvadrat kommer att vara mest sannolikt den dominerande faktorn, eftersom en miljon gånger själv är en mycket större än plus en extra miljon. Så du vet vad? Detta är en sådan jäkla stor nummer om du torget ett nummer. Detta spelar egentligen ingen roll. Vi ska bara korset som ut och glömma det. Och så en datavetare skulle säga att effektiviteten hos denna algoritm är i storleksordningen av n squared-- Jag menar verkligen en approximation. Det är typ av grovt n kvadrat. Över tiden, desto större och större n blir detta är en bra uppskattning för vad effektivitet eller brist på effektivitet av denna algoritm i själva verket är. Och jag härleda att, naturligtvis, från att faktiskt göra matten. Men nu är jag bara vinka mina händer, eftersom jag bara vill ha en allmän känsla av denna algoritm. 

Så använder samma logik, under tiden, låt oss betrakta en annan algoritm vi redan tittat at-- linjär sökning. När jag sökte för telefonen book-- inte sortering, sökning genom telefon book-- Vi fortsatte att säga att det var 1000 steg, eller 500 steg. Men låt oss generalisera det. Om det finns n sidor telefonboken, vad är gångtid eller effektivitet linjär sökning? Det är i storleksordningen hur många steg för att hitta Mike Smith med linjär sökning, desto första algoritmen, eller till och med den andra? 

I värsta fall, Mike är i slutet av boken. Så om telefonboken har 1000 sidor, vi sade förra gången, i värsta fall, det kan ta ungefär hur många sidor för att hitta Mike? Liknande 1000. Det är en övre gräns. Det är en värsta tänkbara situation. Men återigen, vi flyttar bort från siffror som 1000 nu. Det är bara n. 

Så vad är den logiska slutsatsen? Att hitta Mike i en telefon bok som har n sidor kan ta i allra värsta fall, hur många steg av storleksordningen n? Och faktiskt en dator forskare skulle säga att gångtiden, eller prestanda eller effektiviteten eller ineffektivitet, av en algoritm som en linjär sökning är av storleksordningen n. Och vi kan tillämpa samma logik passerar något som jag gjorde bara det andra algoritm hade vi med telefonboken, där vi gick två sidor åt gången. 

Så 1000 sida telefonboken kanske ta oss 500 sidvändningar, plus en Om vi ​​dubbelt tillbaka lite. Så om en telefonbok har n sidor, men vi gör två sidor åt gången, det är ungefär vad? N över två, så det är som n över två. Men jag gjorde anspråk en nyss att n över two-- det är typ av samma som just n. Det är bara en konstant faktor, datavetare skulle säga. Låt oss bara fokusera på variablerna, really-- de största variablerna i ekvationen. 

Så linjär sökning, oavsett gjort en sida åt gången eller två sidor åt gången, är typ av i grunden densamma. Det är fortfarande i storleksordningen n. Men jag hävdade med min bild tidigare att den tredje algoritmen var inte linjär. Det var inte en rak linje. Det var som böjd linje, och algebraiska formel fanns vad? Logg över n-- så log bas två n. Och vi behöver inte gå in alltför mycket detaljer på logaritmer idag, men de flesta datavetare skulle inte även berätta vad basen är. Eftersom det är allt bara konstant faktorer, så att säga, bara små numeriska skillnader. Och så detta skulle vara ett mycket vanligt sätt för särskilt formell dator forskare vid en styrelse eller programmerare på en whiteboard faktiskt argumenterar vilka algoritm de skulle använda eller vad effektiviteten av deras algoritm är. 

Och det är inte nödvändigtvis något du diskutera någon större detalj, men en bra programmerare är någon som har en fast, formell bakgrund. Han kan tala med du i denna typ av väg och faktiskt göra kvalitativa argument som till varför en algoritm eller en mjukvara är överlägsen på något sätt till en annan. Eftersom du kan säkert bara köra en persons program och räkna antalet sekunder det tar att sortera några siffror, och du kan köra några andra personens program och räkna antalet sekunder det tar. Men detta är ett mer generellt sätt att du kan använda för att analysera algoritmer, om du vill, bara på papper eller bara verbalt. Utan att ens köra den, utan ens försöka provingångar, du kan bara resonera igenom det. Och så med att anställa en utvecklare eller om ha honom eller henne slags argumentera för dig varför deras algoritm, deras hemlighet sås för att söka miljarder av webbsidor för din Företaget är bättre, dessa är den typ av argument som de bör helst kunna göra. Eller åtminstone dessa är den typen av saker som skulle komma upp i diskussionen, vid stone i en mycket formell diskussion. Okej. Så Ben föreslagna något kallas val slag. Men jag kommer att föreslå att det finns andra sätt att göra detta också. Vad jag inte riktigt gillar om Ben algoritm är att han fortsatte att gå, eller ha mig gå fram och tillbaka och fram och tillbaka och fram och tillbaka. Vad händer om jag istället skulle göra något som dessa siffror här och jag skulle bara ta itu med varje nummer i sin tur som jag gett det? 

Med andra ord, här är min nummerlistan. Fyra, en, tre, två. Och jag kommer att göra följande. Jag ska in numren där de hör hemma i stället än att välja dem en i taget. Med andra ord, här är nummer fyra. 

Här är min ursprungliga listan. Och jag kommer att upprätthålla i huvudsak en ny lista här. Så detta är den gamla listan. Detta är den nya listan. Jag ser nummer fyra första. Min nya listan är initialt tom, så det är trivialt fallet att fyra nu diverse listan. Jag tar numret jag får, och jag sätter det i min nya listan. 

Är detta nya listan sorteras? Ja. Det är dumt eftersom det finns bara en element, men det är absolut sortering. Det finns inget på sin plats. Det är mer intressant, denna algoritm, när jag flyttar till nästa steg. 

Nu har jag en. Så en, naturligtvis, tillhör vid början eller i slutet av denna nya lista? Början. Så jag måste göra en del arbete nu. Jag har tagit del friheter med min markör genom att bara dra saker där jag vill ha dem, men det är inte riktigt exakt i en dator. En dator, som vi vet, har RAM eller Random Access Memory, och det är ett byte och en annan byte och en annan byte. Och om du har en gigabyte RAM, har du en miljard byte, men de är fysiskt på ett ställe. Du kan inte bara flytta runt saker genom att dra den på bordet var du vill. Så om min nya lista har fyra platser i minnet, tyvärr fyra är redan på fel ställe. 

Så för att sätta nummer ett Jag kan inte bara dra det här. Denna minnesplats finns inte. Det skulle vara fusk, och jag har varit fusk bildmässigt i några minuter här. Så egentligen, om jag vill sätta en här, Jag måste tillfälligt kopiera fyra och sedan lägga en där. 

Det är bra, det är korrekt, det är tekniskt möjligt, men inser att det är extra arbete. Jag inte bara uppskattar antalet på plats. Jag först var tvungen att flytta en nummer, sedan lägga den på plats, så jag slags fördubblat min arbetsinsats. Så ha det i åtanke. 

Men jag nu gjort med detta element. Nu vill jag ta nummer tre. Där naturligtvis, hör det? Mellan. Jag kan inte fuska längre och bara lägga den där, eftersom, återigen, detta minne är i fysiska platser. Så jag måste kopiera fyra och satte tre hit. Inte en stor sak. Det är bara ett extra steg igen-- känns mycket billigt. 

Men nu jag gå vidare till två. De två, naturligtvis, hör hemma här. Nu du börjar se hur arbetet kan stapla upp. Nu vad jag har att göra? Ja, jag måste flytta fyra, Jag har sedan kopiera de tre, och nu kan jag sätta in två. Och fångsten med detta algoritm, intressant nog, är att anta att vi har en mer extrem fall där det är låt oss säga åtta, sju, sex, fem, fyra, tre, två, ett. Detta är, i många sammanhang, det värsta scenariot, eftersom darn sak är bokstavligen baklänges. 

Det spelar egentligen ingen påverka Ben algoritm, eftersom Ben urval sort han kommer att hålla gå fram och tillbaka i listan. Och eftersom han alltid ser genom hela den återstående listan, det spelar ingen roll där elementen är. Men i det här fallet med min insättning approach-- låt oss prova detta. 

Så en, två, tre, fyra, fem, sex, sju, åtta. Ett två tre Fyra, fem, sex, sju, åtta. Jag kommer att ta åtta, och där lägger jag det? Jo, i början av min lista, eftersom denna nya lista sorteras. Och jag passera den ut. 

Var ska jag placera sju? Attans. Det måste åka dit, så Jag måste göra en del kopiering. Och nu sju går här. Nu ska jag gå vidare till sex. Nu är det ännu mer arbete. 

Åtta måste gå hit. Sju måste gå hit. Nu sex kan gå hit. Nu greppa jag fem. Nu åtta måste gå här, sju har att gå här, sex måste gå här, och nu fem och upprepa. Och jag är ganska mycket flytta den ständigt. 

Så i slutet, detta algorithm-- vi ska kalla det inför sort-- faktiskt har en hel del arbete, också. Det är bara annorlunda typ av arbete än Ben. Ben arbete fick mig att gå fram och tillbaka hela tiden, välja nästa mindre elementet och om igen. Så det var detta mycket visuell typ av arbete. 

Denna andra algoritm, som fortfarande correct-- det kommer att få jobbet done-- bara ändrar mängden arbete. Det ser ut som du ursprungligen är spara, eftersom du bara behandlar varje element up front utan att gå alla vägen genom listan som Ben var. Men problemet är, i synnerhet i dessa galna fall där det är allt bakåt, du är bara typ av skjuta det hårda arbete tills du måste fixa dina misstag. 

Och så om du kan tänka dig här åtta och sju och sex och fem och senare fyra och tre och två flyttar sig igenom listan, Vi har just ändrat typ av arbete vi gör. Istället för att göra det på början av min iteration, Jag bara gör det på slutet av varje iteration. Så visar det sig att denna algoritm, Även i allmänhet kallas insättningssortering, är också i storleksordningen n kvadrat. Det är faktiskt inte bättre, inget bättre alls. 

Men det finns en tredje metod Jag skulle vilja uppmuntra oss att fundera över, som är det. Så antar att min lista, för enkelhets skull igen, är fyra, en, tre, two-- bara fyra siffror. Ben hade bra intuition, god människa intuition innan, genom vilken vi fast hela lista eventually-- insättningssortering. Jag smickrade oss tillsammans. Men låt oss betrakta enklaste sättet att åtgärda denna lista. 

Denna lista är inte sortering. Varför? På engelska förklara varför det är faktiskt inte sortering. Vad betyder det inte ska sorteras? 

STUDENT: Det är inte sekventiella. 

DAVID MALAN: Inte sekventiella. Ge mig ett exempel. 

STUDENTEN sätta dem i ordning. 

DAVID MALAN: OK. Ge mig ett mer specifikt exempel. 

STUDENTEN stigande ordning. DAVID MALAN: Ej stigande ordning. Vara mer exakt. Jag vet inte vad du menar med stigande. Vad är fel? 

STUDENT: Den minsta av siffror inte är i det första utrymmet. 

DAVID MALAN: Minsta antal s inte är i det första utrymmet. Var mer specifik. Jag börjar komma på. Vi räknar, men Vad är i ordning här? 

STUDENTEN nummerföljd. DAVID MALAN: Numerisk sekvens. Allas slags hålla det här-- mycket hög nivå. Bara bokstavligen berätta vad är fel som en fem-årig styrka. 

STUDENT: Plus en. 

DAVID MALAN: Vad är det? 

STUDENT: Plus en. 

DAVID MALAN: Vad menar du plus ett? Ge mig en annan fem år gammal. Vad som är fel, mamma? Vad som är fel, pappa? Vad menar du detta inte sorteras? 

STUDENT: Det är inte rätt plats. 

DAVID MALAN: Vad är inte på rätt plats? 

STUDENT: Fyra. DAVID MALAN: OK, bra. Så fyra är inte där det ska vara. Framför allt är detta rätt? Fyra och en, den första två siffror jag ser. Är det här rätt? Nej, de är i ordning, eller hur? I själva verket tror nu om en dator också. Det kan bara titta på kanske en, kanske två saker på once-- och egentligen bara en sak vid en tidpunkt, men den kan åtminstone titta på en sak sedan Nästa sak bredvid den. 

Så är dessa för? Självklart inte. Så du vet vad? Varför tar vi inte barnet steg åtgärdar felet istället för att göra dessa infall algoritmer som Ben, där han slags fastställa det genom looping igenom listan istället för att göra vad jag gjorde, där Jag bara typ av fast det när vi går? Låt oss bara bokstavligen bryta ned begreppet order-- nummerordning, kalla det vad du want-- in i dessa parvisa jämförelser. 

Fyra och en. Är detta rätt ordning? Så låt oss fixa det. En och fyra, och sedan Vi ska bara kopiera den. Okej, bra. Jag fixade en och fyra. Tre och två? Nej. Låt mina ord matcha mina fingrar. Fyra och tre? 

Det är inte i ordning, så jag kommer att göra en, tre, fyra, två. Okej bra. Nu fyra och två? Vi måste fixa det här också. Så en, tre, två, fyra. Så är det sorteras? Nej, men det närmare redas? 

Det är därför vi fast detta misstag, fast vi detta misstag, och vi fast detta misstag. Så vi fast tre misstag utan tvekan. Fortfarande inte riktigt ser sorteras, men det är objektivt närmare redas eftersom vi fast några av dessa misstag. 

Nu vad gör jag nu? Jag slags nått slutet av listan. Jag tycktes ha fast alla misstag, men nej. Eftersom i detta fall, några siffror kan ha bubblade upp närmare till ett annat nummer som är fortfarande i ordning. Så låt oss göra det igen, och jag ska bara göra det på plats den här gången. En och tre? Det är okej. Tre och två? Naturligtvis ingen, så låt oss ändra på det. Så två, tre. Tre och fyra? Och nu låt oss bara vara särskilt pedantisk här. Är det sorteras? Du människor vet att det är för sortering. 

Jag ska försöka igen. Så Olivia föreslår jag försöker igen. Varför? Eftersom en dator inte har lyxen av våra mänskliga ögon för att bara kasta en blick back-- OK, jag är klar. Hur datorn bestämma att listan nu sorteras? Mekaniskt. 

Jag ska gå igenom ännu en gång, och bara om jag inte göra / hitta några misstag kan jag sedan sluta sig datorn Japp, vi är bra att gå. Så ett och två, två och tre, tre och fyra. Nu kan jag definitivt säga att detta är sorteras, eftersom jag inte gjort några ändringar. Nu skulle det vara ett fel och bara dum om jag, datorn, frågade samma frågor igen förväntar sig olika svar. Borde inte hända. 

Och så nu listan sorteras. Tyvärr, gångtid denna algoritm är också n kvadrat. Varför? Eftersom du har n siffror, och i värsta fall måste du flytta n nummer n gånger eftersom du måste fortsätta tillbaka för att kontrollera och eventuellt korrigera dessa nummer. Och vi kan göra en mer formell analys också. 

Så detta är allt för att säga att vi har tagit tre olika metoder, en av dem omedelbart intuitivt utanför bat från Ben till min föreslagna införandet sort till denna där du typ av glömma skogen för alla träd initialt. Men om du tar ett steg tillbaka, voila, har vi fast sorterings begreppet. Så det här är, vågar säga, en lägre nivå kanske än vissa av dessa andra algoritmer, men låt oss se om vi inte kan visualisera dessa med hjälp av detta. 

Så det här är några fina mjukvara som någon skrev att använda färgrika barer som finns i kommer att göra följande för oss. Var och en av dessa stänger representerar ett tal. Taller stapel, desto större numret mindre bar, desto mindre antal. Så helst vi vill ha en trevlig pyramid där det börjar litet och blir stor, och det skulle innebära att dessa stänger sorteras. Så jag kommer att gå vidare och välja, till exempel Bens algoritm first-- val slag. 

Och märker vad den gör. Det sätt som de har valt att visualisera denna algoritm är att, precis som jag var promenader genom min lista, Detta program är gång genom sin nummerlistan, belysa i rosa varje nummer som det ser på. Och vad är på väg att hända nu? 

Det minsta antalet som I eller Ben plötsligt fann får flyttas till början av listan. Och märker de gjorde vräka det nummer som var där, och det är väl bra. Jag fick inte in i den detaljnivå. Men vi måste lägga det numret någonstans, så vi just flyttat det till öppen plats som skapades. Så jag kommer att påskynda detta upp, eftersom det annars blir mycket omständlig snabbt. Animation Byggd det vi går. Så nu samma princip Jag tillämpade, men du kan börja känna algoritmen, om du kommer, eller se det lite tydligare. Och denna algoritm har effekten att välja nästa minsta elementet, så du kommer att börja se det ramp upp till vänster. Och på varje iteration, som jag föreslås gör det lite mindre arbete. Det behöver inte gå hela vägen tillbaka till den vänstra änden av listan, eftersom det redan vet de sorteras. Så det slags känns som det är accelererar, även om varje steg är tar lika lång tid. Det är bara färre steg kvar. Och nu kan du slags känner algoritm städa upp i slutet av det, och faktiskt nu är det sorteras. 

Så insättningssortering är klar. Jag behöver nytt slumpmässigt matrisen. Och märker jag kan bara hålla randomisera det, och vi kommer att få en uppskattning av samma tillvägagångssätt, insättningssortering. Låt mig sakta ner till här. Låt oss börja att över. Sluta. 

Låt oss hoppa över fyra. Det går vi. Randomisera de array. Och här go-- vi insättningssortering. Spela. Lägg märke till att det handlar om varje elementet den stöter på en gång, men om det hör hemma i fel ställe meddelande allt arbete som måste ske. Vi måste hålla flytta mer och flera element för att göra plats för vi vill sätta på plats. 

Så vi fokuserar på vänstra änden av endast listan. Märker vi inte ens har tittat at-- vi har inte markerat i rosa något till höger. Vi är bara att göra med problemen som vi går, men vi skapar en hel del arbeta för oss fortfarande. Och så om vi påskynda denna nu för att gå till fullbordan, den har en annorlunda känsla att det faktiskt. Det är bara att fokusera på den vänstra änden, men göra lite mer arbete som needed-- slags utjämning saker över, fastställande saker, men handlar i slutändan med varje element en i taget tills vi får the-- bra, vi alla vet hur det kommer att sluta, så det är lite underwhelming kanske. 

Men listan i end-- spoiler-- kommer att sorteras. Så låt oss titta på en sista. Vi kan inte bara hoppa nu. Vi är nästan där. Två att gå, en att gå. Och voila. Excellent. 

Så nu ska vi göra ett sista, åter randomisera med bubbelsortering. Och lägg märke till här, speciellt om jag sakta ner, betyder detta att hålla swooping igenom. Men märker det bara gör parvis comparisons-- slags lokala lösningar. Men så fort vi får I slutet av listan i rosa, vad som kommer att behöva hända igen? Ja, det kommer att behöva börja om, eftersom den endast fasta parvisa sökord. Och som kan ha avslöjat ytterligare andra. Och så om du påskynda detta kommer du se att mycket som namnet antyder, den mindre elements-- eller snarare, de större elements-- börjar att bubbla upp till toppen, om man så vill. Och de mindre elementen börjar att bubbla ned till vänster. Och faktiskt, det är den typen av den visuella effekten också. Och så detta kommer att hamna efterbehandling på ett mycket liknande sätt, också. 

Vi behöver inte uppehålla på just detta. Låt mig att öppna detta nu också. Det finns några andra sorteringsalgoritmer i världen, varav några fångas här. Och särskilt för elever som inte är nödvändigtvis visuella eller matematiskt, som vi gjorde innan vi kan även göra detta audially Om vi ​​associera ett ljud med detta. Och bara för skojs skull, här är en några olika algoritmer, och en av dem i synnerhet du kommer att märka kallas "merge sort." 

Det är faktiskt en fundamentalt bättre algoritm, sådan att merge sort, en av de du är på väg att se, inte är storleksordningen n i kvadrat. Det är i storleksordningen n gånger loggar av n, som faktiskt är mindre och därmed snabbare än de andra tre. Och det finns en annan par fåniga de som vi får se. 

Så här går vi med vissa ljud. Detta är insättningssortering, så igen det är bara att göra med elementen när de kommer. Detta är bubbelsortering, så det är betrakta dem par åt gången. Och återigen, de största delarna bubblar upp till toppen. 

Nästa upp val slag. Det här är Ben algoritm, där igen han välja iterativt nästa minsta elementet. Och återigen, nu kan du verkligen höra det det påskynda men endast i den mån eftersom det gör mindre och mindre arbeta på varje iteration. Detta är den snabbare en, merge sort, som sortering kluster av siffror tillsammans och sedan kombinera dem. Så look-- vänster hälften redan sortering. 

Nu är det sortera den högra halvan, och nu det kommer att kombinera dem till en. Detta är något som kallas "Gnome sort." Och du kan typ av se att det kommer fram och tillbaka, fastställande av arbete lite här och där innan den fortsätter till nya arbeten. Och det är allt. Det finns en annan sorts, som är egentligen bara för akademiska ändamål, kallas "dum sortera,", som tar dina data, sorterar det slumpmässigt, och sedan kontrollerar om den sorteras. Och om det inte är, åter sorterar det det slumpmässigt, kontrollerar om det sorteras, och om inte upprepas. Och i teorin, probabilistiskt detta kommer att slutföra, men efter en hel del tid. Det är inte den mest effektiva av algoritmer. Så några frågor om de särskilda algoritmer eller något relaterade där också? 

Nåväl, låt oss nu retas isär vad alla dessa linjer är att jag har dragit och vad jag antar datorn kan göra under huven. Jag skulle vilja påstå att alla dessa siffror Jag håller drawing-- de behöver för att få lagras någonstans i minnet. Vi kommer att bli av med den här killen nu också. 

Så en bit av minne i en computer-- så RAM DIMM är vad vi sökte i går, dubbel inline memory module-- ser ut så här. Och var och en av dessa små svarta chips finns viss antal byte, typiskt. Och sedan guld stift är som ledningar som ansluter den till datorn, och den gröna kisel kortet är bara vad håller allting tillsammans. Så vad betyder det egentligen? Om jag sorts dra samma bild, Låt oss anta att för enkelhetens skull att detta DIMM, dubbel inline minnesmodul är en gigabyte RAM-minne, en gigabyte minne, vilket är hur många byte totalt? En gigabyte är hur många byte? Mer än det. 1124 är kilo, 1000. Mega är miljoner. Giga är en miljard. 

Jag ljuger? Kan vi även läsa etiketten? Detta är faktiskt 128 gigabyte, det är så mycket mer. Men vi ska låtsas detta är bara en gigabyte. Så det innebär att det finns en miljard byte minne tillgängliga för mig eller 8 miljarder bitar, men vi kommer att tala i termer av byte nu, går vidare. 

Så vad det betyder är att detta är en bitgrupp, är detta ytterligare ett byte, detta är ett annat byte, och om vi verkligen ville att vara specifik vi skulle behöva rita en miljard små fyrkanter. Men vad betyder det? Nåväl, låt mig bara zooma på den här bilden. Om jag har något som ser så här nu, det är fyra byte. 

Och så jag kunde sätta fyra siffror här. Ett två tre Fyra. Eller jag kunde sätta fyra bokstäver eller symboler. "Hallå!" kunde gå där, eftersom var och en av bokstäverna, vi diskuterat tidigare, kan representeras med åtta bitar eller ASCII eller en byte. Så med andra ord, kan du sätta 8 miljarder saker inuti av detta en pinne av minne. Nu vad betyder det att ställa saker och ting tillbaka att rygg mot rygg i minnet så här? Detta är vad en programmerare skulle kalla en "array". I ett datorprogram, tror du inte om den underliggande hårdvaran, per se. Du tror bara på dig själv som har tillgång till en miljard byte totalt, och du kan vad du vill med det. Men för enkelhetens skull Det är allmänt användbar att hålla ditt minne höger bredvid varandra som här. Så om jag zoomar in på this-- eftersom vi verkligen inte gå att dra en miljard små squares-- Låt oss anta att detta forum representerar att pinne av minne nu. Och jag ska bara dra så många som min markör hamnar ger mig här. Så nu har vi en pinne minne på kortet som har fått en, två, tre, fyra, fem, sex, ett, två, tre, fyra, fem, sex, seven-- så 42 bytes av minne på den totala skärmen. Tack. Ja, det gjorde min aritmetik rätt. Så 42 byte minne här. Så vad betyder detta egentligen? Tja, en programmerare skulle faktiskt i allmänhet tänka på detta minne som adresserbara. Med andra ord, var och en av dessa platser i minnet, i hårdvara, har en unik adress. 

Det är inte så komplicerat som en Brattle Square, Cambridge, Mass., 02138. Istället är det bara en siffra. Detta är bytenummer noll, är detta en, det är två, det är tre, och detta är 41. Vänta en minut. Jag trodde jag sa 42 för en stund sedan. Jag började räkna på noll, så det är faktiskt rätt. Nu har vi inte att faktiskt dra det som ett rutnät, och om du ritar det som ett rutnät Jag tror saker faktiskt få lite missvisande. Vad en programmerare skulle, i sitt eget sinne, i allmänhet tänker på detta minne som är precis som ett band, som en bit maskeringstejp som bara går på och för evigt eller tills du får slut på minne. Så ett allt vanligare sätt att dra och bara tänka på minnet skulle vara att detta är byte noll, en, två, tre, och sedan dot, punkt, punkt. Och du har 42 sådana byte totalt, även men fysiskt Det kan faktiskt vara något mer om detta. 

Så om du nu tänker på din minne som detta, precis som ett band, Detta är vad en programmerare igen skulle kalla en rad minne. Och när du vill faktiskt lagra något i en dators minne, du vanligtvis gör lagra saker back-to-back till back-to-back. Så vi har pratat om siffror. Och när jag ville lösa problem som fyra, en, tre, två, även om jag var bara att dra bara fyra siffror, en, tre, två på bordet, datorn skulle verkligen har denna inställning i minnet. 

Och vad skulle vara bredvid två i datorns minne? Tja, det finns inget svar på det. Vi vet inte riktigt. Och så länge som Datorn behöver inte det, Det behöver inte bry sig om vad är nästa till siffrorna det bryr sig om. Och när jag sade tidigare att en dator kan bara titta på en adress i taget, Detta är typ av varför. 

Inte olikt en post spelare och ett läshuvud bara att kunna titta på en viss spår i en fysisk old-school rekord åt gången, på liknande sätt kan en dator tack till sin CPU och dess Intel instruktionsuppsättning, bland vars instruktion läses från minnet eller spara till memory-- en Datorn kan bara se på en plats åt time-- ibland en kombination av dem, men egentligen bara en plats åt gången. Så när vi gjorde dessa olika algoritmer, Jag är inte bara skriver i en vacuum-- fyra, en, tre, två. Dessa siffror faktiskt tillhör någonstans fysiskt i minnet. Så det finns lilla transistorer eller någon form av elektronik på undersidan av huv lagra dessa värden. 

Och totalt, hur många bitar involverade just nu, bara för att vara klart? Så det här är fyra byte, eller nu är det 32 ​​bitar totalt. Så det finns faktiskt 32 nollor och som ingår i dessa fyra saker. Det finns ännu mer här, men igen vi inte bryr sig om det. 

Så nu ska vi be en annan fråga med hjälp av minne, eftersom det i slutet av dagen är i varians. Oavsett vad vi kan göra med datorn, i slutet av dagen hårdvaran är fortfarande den samma under huven. Hur skulle jag lagra ett ord här? Tja, ett ord i en dator som "Hallå!" skulle lagras precis som denna. Och om du ville ha en längre ord, kan du helt enkelt skriva det och säga något som "hej" och butik som här. 

Och så här också, denna contiguousness är faktiskt en fördel, eftersom en dator kan bara läses från höger till vänster. Men här är en fråga. Inom ramen för detta ord, h-e-l-l-o, utropstecken, hur kan datorn vet var ord börjar och där ordet slutar? I samband med siffror, Hur fungerar datorn veta hur länge den sekvens av nummer är eller där det börjar? Tja, visar det out-- och vi kommer inte gå alltför mycket in i denna nivå av detail-- datorer flytta runt saker i minnet bokstavligen med hjälp av dessa adresser. Så i en dator, om du är skriva kod för att lagra saker som ord, vad du är verkligen göra är att skriva uttryck som minns var i datorns minne dessa ord är. Så låt mig göra en mycket, mycket enkelt exempel. 

Jag kommer att gå vidare och öppna upp en enkel textprogram, och jag kommer att skapa en fil som heter hej.c. Det mesta av denna information vi kommer inte att gå in i detalj, men jag kommer att skriva en program i samma språk, C. Detta är långt mer skrämmande, Jag skulle vilja hävda, än Scratch, men det är mycket i samma anda. Faktum är att dessa lockigt braces-- du kan sorts tänka på vad jag gjorde precis som denna. 

Låt oss göra detta, faktiskt. När gröna flaggan klickade, gör följande. Jag vill skriva ut "Hej." Så det här är nu pseudokod. Jag slags sudda ut gränserna. I C, detta språk jag talar om denna linje tryck hello faktiskt blir "printf" med några parenteser och ett semikolon. 

Men det är exakt samma idé. Och det är mycket användarvänlig "När grön flagg klickade" blir mycket mer svårbegripliga "int main tomrum." Och detta har verkligen ingen kartläggning, så jag ska bara ignorera det. Men klammerparenteserna är som krökta pusselbitar som denna. 

Så du kan slags gissa. Även om du har aldrig programmerat förut, vad det här programmet förmodligen göra? Förmodligen skriver hello med ett utropstecken. 

Så låt oss prova det. Jag kommer att spara det. Och detta är, återigen, en mycket gamla skolmiljön. Jag kan inte klicka, jag kan inte dra. Jag måste skriva kommandon. Så jag vill köra mitt program, så Jag kan göra detta, som hej.c. Det är filen jag sprang. Men vänta, jag saknar ett steg. Vad gjorde vi säga är en nödvändig steg för ett språk som C? Jag har just skrivit källa kod, men vad behöver jag? Ja, jag behöver en kompilator. Så på min Mac här, har jag en program som kallas GCC, GNU C-kompilator, vilket gör att jag kan göra this-- tur min källkod i, vi kallar det, maskinkod. 

Och jag kan se att, återigen, enligt följande, dessa är nollor och ettor I bara skapas från min källkod, alla nollor och ettor. Och om jag vill köra min program-- det händer att kallas a.out för historisk reasons-- "hej." Jag kan köra den igen. Hallå Hallå Hallå. Och det verkar fungera. 

Men det betyder någonstans i mitt datorns minne är orden h-e-l-l-o, utropstecken. Och det visar sig, precis som en sidoreplik, vad en dator skulle typiskt göra så att det vet var saker och ting börjar och end-- det är kommer att sätta en speciell symbol här. Och konventionen är att sätta nummer noll i slutet av ett ord så att du vet om det faktiskt slutar, så att du inte hålla skriva ut mer och mer tecken än du tänker faktiskt. 

Men takeaway här, även även om detta är ganska svårbegripliga, är att det är i slutändan relativt enkel. Du fick en slags band, en tom utrymme där du kan skriva brev. Du måste helt enkelt ha en speciell symbol, som godtyckligt siffran noll, att sätta i slutet av dina ord så att datorn vet, åh, jag ska sluta skriva ut efter Jag ser utropstecken. Eftersom nästa sak där är en ASCII-värde på noll, eller null-tecknet som någon skulle kalla det. Men det är lite av ett problem här, och låt oss återgå till nummer för en stund. Antag att jag gör, i själva verket, har en matris av nummer, och antag att den program jag skriver är som en klass bok för lärare och en lärare klassrum. Och detta program tillåter honom eller henne att skriva in elevernas poäng på frågesporter. Och anta att studenten får 100 på deras första quiz, kanske som en 80 på nästa en, sedan en 75, sedan en 90 på fjärde testet. 

Så vid denna tidpunkt i historien, matrisen är av storlek fyra. Det finns absolut mer minne i dator, men arrayen, så att säga, är storlek fyra. Antag nu att läraren vill att tilldela en femtedel frågesport för klassen. Jo, en av de saker han eller hon kommer att behöva göra är nu lagra ett extra värde här. Men om gruppen läraren har skapad i detta program är av storlek för, ett av problemet med en array är att du kan inte bara fortsätta att lägga på minnet. Eftersom det om en annan del av Programmet har ordet "hej" just där? 

Med andra ord kan mitt minne vara användas för något i ett program. Och om i förväg jag skrev i, hej, Jag vill mata in fyra frågesport poäng, de kan gå här och här. Och om du plötsligt ändrar dig senare och säga att jag vill en femtedel frågesport poäng, kan du inte bara lägga den var du vill, eftersom det om det minne som används för något else-- något annat program eller något annat inslag i programmet att du kör? Så du måste tänka i förväg hur du vill lagra data, eftersom du nu har målat själv till en digital hörn. 

Så en lärare kanske i stället säger när du skriver ett program att lagra sin kvaliteter, vet du vad? Jag kommer att begära, när du skriver mitt program, att jag vill noll, ett, två, tre, fyra, fem, sex, åtta grader totalt. Så en, två, tre, fyra, fem, sex, sju, åtta. Läraren kan bara över fördela minne när du skriver hans eller hennes program och säga, vet du vad? Jag kommer aldrig att tilldela mer än åtta frågesporter i en termin. Det är bara galen. Jag kommer aldrig att fördela det. Så att detta sätt han eller hon har flexibilitet att lagra elevresultat, som 75, 90, och kanske en extra där eleven fick extra kredit, 105. 

Men om läraren aldrig använder dessa tre platser, det finns en intuitiv takeaway här. Han eller hon är bara slöseri med utrymme. Så med andra ord, det är det här gemensam kompromiss i programmering där du antingen kan fördela exakt så mycket minne som du vill, Fördelen med det är att du är super efficient-- du inte vara slösaktig på all-- men nackdelen som är vad händer om du ändrar dig när med hjälp av program som du vill spara mer data än du tänkt. 

Så kanske lösningen är, då, skriva dina program på ett sådant sätt att de använder mer minne än de faktiskt behöver. Detta sätt du inte kommer att köra in det problemet, men du vara slösaktig. Och ju mer minne programmet använder, som vi diskuterade i går, desto mindre minne som är tillgängligt för andra program, desto snabbare datorn kan bromsa ner på grund av virtuellt minne. Och så den idealiska lösningen skulle vara vad? 

Under-fördelning verkar dålig. Över fördelning verkar dålig. Så vad kan vara en bättre lösning? Omfördela. Vara mer dynamisk. Inte tvinga dig själv att välja en priori i början, vad du vill. Och absolut inte överdelar, så att du inte vara slösaktig. 

Och på så sätt uppnå detta mål, vi måste kasta denna datastruktur, så att säga, bort. Och så vad en programmerare kommer typiskt att använda är något som kallas inte en array utan en länkad lista. Med andra ord, han eller hon kommer att börja tänka på deras minne såsom varande typ av en form, att de kan rita på följande sätt. Om jag vill lagra ett nummer i en program-- så det är September, Jag har gett mina elever en frågesport; jag vill att lagra elevernas första frågesport, och de fick en 100 på det-- I tänker be min dator, med hjälp av programmet har jag skriven för en bit av minnet. Och jag kommer att lagra nummer 100 i det, och det är det. 

Sedan ett par veckor senare när jag får mitt andra frågesport, och det är dags att skriva i att 90% kommer jag att be datorn, hej, dator, kan jag har en annan bit av minne? Det kommer att ge mig detta tom bit av minnet. Jag kommer att sätta i antalet 90, men i mitt program på något sätt eller other-- och vi kommer inte att oroa sig syntaxen för this-- jag behöver att på något sätt kedja dessa saker tillsammans. Och jag ska kedja ihop dem med vad som ser ut som en pil här. 

Den tredje quiz som kommer upp, Jag kommer att säga, hej, dator, ge mig en bit av minnet. Och jag kommer att lägga ner vad det var, liksom 75, och jag måste kedja detta tillsammans nu på något sätt. Fjärde frågesport kommer tillsammans, och kanske det är mot slutet av terminen. Och vid den tidpunkten mitt program kanske använder minne överallt, hela fysiskt. Och så bara för sparkar, jag kommer att dra denna fjärde quiz-- jag har glömt vad det var; jag tror kanske en 80 eller something-- vägen hit. 

Men det är bra, eftersom bildmässigt Jag kommer att dra denna linje. Med andra ord, i verkligheten, i datorns hårdvara, den första poängen kanske hamna här eftersom det är precis i början av terminen. Nästa man kan hamna här eftersom lite tid har gått och programmet fortsätter att gå. Nästa poäng, vilket var 75, kan vara här. Och den sista poängen kan vara 80, som är här. 

Så i verkligheten, fysiskt, detta kan vara vad datorns minne ser ut. Men detta är inte en bra mental paradigm för en programmerare. Varför ska du bry dig där heck dina data hamnar? Du vill bara att lagra data. 

Detta är ungefär som vår diskussion tidigare att dra kuben. Varför bryr du dig vad vinkeln är av kuben och hur man måste vända sig till dra det? Du vill bara en kub. På samma sätt här, bara vill klass bok. Du vill bara att tänka på detta som en lista med tal. Vem bryr sig om hur det är implementeras i hårdvara? 

Så abstraktion nu är bilden här. Detta är en länkad lista, som en programmerare skulle kalla det, mån du har en listan, uppenbarligen av siffror. Men det är kopplat bildmässigt med hjälp av dessa pilar, och alla dessa pilar är-- under huven, om du är nyfiken, påminna om att vår fysiska hårdvara har adresser noll, ett, två, tre, fyra. Alla dessa pilar är är som en karta eller riktningar, där om 90 är-- nu Jag fick räkna. 

Noll, ett, två, tre, fyra, fem, sex, sju. Det ser ut som 90 är på minnesadress nummer sju. Alla dessa pilar är är som en liten papperslapp som är att ge anvisningar till program som säger att följa denna karta att få på plats sju. Och det du hittar elevens andra frågesport poäng. Samtidigt 75-- om jag fortsätter här, detta är sju, åtta, nio, tio, elva, tolv, 13, 14, 15. 

Denna andra pilen representerar bara en karta minnesplats 15. Men återigen, programmeraren gör i allmänhet inte bryr sig om denna detaljnivå. Och i de flesta varje programmering språk i dag, programmeraren kommer inte ens vet var i minnet dessa siffror egentligen är. Allt han eller hon måste ta hand om är att de på något sätt sammanlänkade i en datastruktur som denna. 

Men det visar sig inte att få alltför tekniskt. Men bara för att vi kan kanske råd att ha denna diskussion här, Anta att vi återkomma denna fråga här av en matris. Låt oss se om vi beklagar kommer hit. Detta är 100, 90, 75, och 80. 

Låt mig kort göra detta påstående. Detta är en array, och igen, framträdande egenskap hos en matris är att alla dina data är tillbaka till rygg mot rygg i memory-- bokstavligen en byte eller kanske fyra byte, några fast antal bitgrupper bort. I en länkad lista, som vi kan dra så här, under huven som vet var det där är? Det behöver inte ens att flyta så här. Vissa uppgifter kan vara tillbaka till vänster uppe. Du vet inte ens. 

Och så med en array, har du funktion som kallas Random Access. Och vad random accessmedel är att datorn kan hoppa direkt till valfri plats i en matris. Varför? Eftersom datorn känner att den första platsen är noll, en, två och tre. 

Och så om du vill gå från detta element till nästa element, du bokstavligen, i datorns sinne, bara lägga en. Om du vill gå till det tredje elementet, bara lägga en-- nästa element, bara lägga till en. Men i denna version av historien, antar datorn bläddrar på eller ta itu med nummer 100. Hur får man till nästa grad i betygsboken? 

Du måste ta sju steg, som är godtyckligt. För att komma till nästa, måste du ta ytterligare åtta steg för att komma till 15. Med andra ord, det är inte en konstant spalt mellan siffrorna, och det bara tar datorn mer tid är poängen. Datorn måste söka genom minne för att hitta det du letar efter. 

Så medan en matris tenderar att vara en snabb data structure-- eftersom du kan bokstavligen bara göra enkel aritmetik och komma dit du vill genom att lägga till en, för instance-- en länkad lista, du offra den funktionen. Du kan inte bara gå från första till andra till tredje till fjärde. Du måste följa kartan. Du måste ta fler steg för att komma till de värden som verkar vara att lägga till en kostnad. Så vi betalar ett pris, men vad var funktionen att Dan sökte här? Vad gör en länkad lista tydligen tillåter oss att göra, som var ursprunget till denna berättelse? 

Exakt. En dynamisk storlek på den. Vi kan lägga till denna lista. Vi kan även krympa listan, så att vi bara använder så mycket minne som vi verkligen vill och så Vi är aldrig över fördelning. 

Nu är det bara att vara riktigt nit-picky, Det finns en dold kostnad. Så du bör inte bara låta mig övertyga att detta är en övertygande kompromiss. Det finns en annan dold kostnad här. Fördelen att vara tydlig, är att vi får dynamik. Om jag vill ha en annan del, jag kan bara dra den och placera ett antal där. Och då kan jag länka den med en bild här, medan över här, igen, om jag har målat mig i ett hörn, om något annat redan använder minnet här, jag är ute på tur. Jag har målat mig in i hörnet. 

Men vad är det dolda kosta i den här bilden? Det är inte bara mängden av tiden som det tar att gå härifrån till här, vilket är sju steg, sedan åtta steg, vilket är mer än en. Vad är en annan dold kostnad? Inte bara tid. Ytterligare information nödvändigt för att uppnå denna bild. 

Ja, den kartan, dessa små rester av papper, som jag håller beskriver dem som. Dessa arrows-- de är inte gratis. En computer-- du känner vad en dator har. Det har nollor och ettor. Om du vill representera en pil eller en karta eller ett nummer, du behöver lite minne. Så den andra pris du betala för en länkad lista, en gemensam datavetenskap resurs, är också utrymme. 

Och faktiskt så, så vanligt, bland de kompromisser i utformningen av programvaruteknik system är tid och space-- är två av dina ingredienser, två av dina mest kostsamma ingredienser. Detta kostar mig mer tid eftersom jag måste följa den här kartan, men det är också kostar mig mer utrymme eftersom jag måste hålla denna karta runt. Så hoppet, eftersom vi har typ av diskuterade över igår och idag, är att fördelarna uppväger kostnaderna. 

Men det finns ingen självklar lösning här. Kanske är det better-- a la snabb och smutsig, som Kareem föreslagna earlier-- att kasta minnet vid problemet. Bara köpa mer minne, tror mindre hårt om att lösa problemet, och lösa det på ett enklare sätt. Och faktiskt tidigare, när Vi talade om kompromisser, det var inte utrymme i datorn och tid. Det var utvecklare tid, vilket är ännu en annan resurs. 

Så återigen, det är detta balansakt försöker bestämma vilken av dessa saker är du villig att spendera? Som är det billigaste? Vilket ger bättre resultat? Ja? 

Verkligen. I detta fall, om du är representerar siffror i maps-- dessa kallas på många språk "pekare" eller "adresser" - Det är dubbelt så mycket utrymme. Det behöver inte vara så illa som dubbel om just nu vi bara lagra nummer. Antag att vi lagrar patientjournaler i en hospital-- så Pierson s namn, telefonnummer, personnummer, läkare historia. Denna box kan vara mycket, mycket större, i vilket fall en liten liten pekare, adress nästa element-- det är inte en stor sak. Det är en sådan frans kostar det spelar ingen roll. Men i det här fallet, ja, det är en fördubbling. Bra fråga. 

Låt oss tala om gång en lite mer konkret. Vad är gångtid att söka den här listan? Anta att jag ville söka genom alla elevernas betyg, och det finns n kvaliteter i denna datastruktur. Även här kan vi låna vokabulär tidigare. Detta är en linjär datastruktur. 

Big O n är vad som krävs för att få till slutet av denna datastruktur, whereas-- och vi har inte sett detta before-- en array ger dig vad som kallas konstant tid, vilket innebär att ett steg eller två steg eller 10 steps-- spelar ingen roll. Det är ett fast antal. Det har ingenting att göra med storleken på arrayen. Och anledningen till att igen, är slumpmässig åtkomst. Datorn kan bara omedelbart hoppa till en annan plats, eftersom de är alla samma avstånd från allt annat. Det finns ingen tänkande inblandade. Okej. Så om jag kan, låt mig försöka måla två slutliga bilder. En mycket vanlig en känd som en hashtabell. Så för att motivera denna diskussion, Låt mig tänka på hur man gör detta. 

Så vad sägs om detta? Antag att problemet Vi vill lösa nu genomför i en dictionary-- så en hel del engelska ord eller vad som helst. Och målet är att kunna svara frågor av formen är detta ett ord? Så du vill genomföra en stavningskontroll, bara som en fysisk lexikon att du kan slå upp saker i. Anta att jag skulle göra detta med en matris. Jag kunde göra detta. 

Och antar att orden är äpple och banan och cantaloupemelon. Och jag kan inte tänka på frukt som börjar med d, så vi är bara kommer att ha tre frukter. Så detta är en array, och vi är lagra alla dessa ord i denna ordbok som en array. Frågan är då hur annars kan du spara den här informationen? 

Tja, jag typ av fusk här, eftersom var och en av dessa bokstäver i ord är verkligen en enskild bitgrupp. Så om jag ville verkligen vara nit-picky, jag borde verkligen att dela upp detta i mycket mindre bitar av minne, och vi kunde göra just detta. Men vi kommer att stöta på samma problem som tidigare. Tänk om, som Merriam Webster eller Oxford gör varje year-- de lägga till ord till dictionary-- vi inte nödvändigtvis vill måla oss i ett hörn med en array? 

Så i stället, kanske en smartare strategi är att sätta Apple i sin egen nod eller låda, som vi skulle säga, banan, och så här har vi cantaloupemelon. Och vi sträng dessa saker tillsammans. Så detta är arrayen, och detta är den länkade listan. Om du inte riktigt kan se, det bara säger "array", och detta säger "lista." 

Så vi har samma exakta frågor som tidigare, där vi nu har dynamik i vårt länkad lista. Men vi har en ganska långsam ordboken. Anta att jag vill slå upp ett ord. Det kan ta mig stora O n steg, eftersom ordet kanske vara hela vägen vid slutet av listan, som cantaloupmelon. Och det visar sig att i programmering, sortera av den heliga graal av data strukturer, är något som ger dig konstant tid som en matris men som fortfarande ger dig dynamik. 

Så kan vi ha det bästa av två världar? Och faktiskt, det finns något kallad hash-tabellen som tillåter dig att göra exakt att, om än ungefär. En hash-tabell är en snyggare datastruktur som vi kan tänka på som kombination av en array-- och jag kommer att dra det som this-- och länkade listor att jag ska göra så här hit. 

Och hur denna sak verk är som följer. Om detta now-- hash table-- är min tredje datastruktur, och jag vill spara ord i detta, det gör jag inte vill bara lagra alla av ord rygg mot rygg mot rygg mot rygg. Jag vill utnyttja vissa bit information om de ord som låter mig att få den där den är snabbare. 

Så med tanke på orden apple och banan och cantaloupemelon, Jag medvetet valde dessa ord. Varför? Vad blir liksom grunden annorlunda om tre? Vad är det uppenbara? De börjar med olika bokstäver. 

Så du vet vad? I stället för att lägga alla mina ord i samma hink, så att säga, som i en stor lista, varför inte Jag åtminstone prova en optimering och göra mina listor 1/26 så länge. En övertygande optimering kanske varför inte Jag-- när du sätter ett ord in i denna datastruktur, i datorns minne, varför jag inte lägga alla punkt a ord här, alla "B" ord här, och alla C-ord här? Så här slutar att sätta ett äpple här, banan här, cantaloupmelon här, och så vidare. 

Och om jag har en extra Ordet like-- vad är en annan? Äpple, banan, päron. Någon tänker på en frukt som börjar med a, b eller c? Blueberry-- perfekt. Det kommer att hamna här. Och så verkar vi ha en marginellt bättre lösning, för nu om jag vill för att söka efter äpple, jag first-- jag inte bara dyka i min datastruktur. Jag dyka inte i datorns minne. Jag ser först på den första bokstaven. 

Och detta är vad en dator vetenskapsman skulle säga. Du hash i din datastruktur. Du tar din ingång, vilket i detta fall är ett ord som äpple. Du analyserar det, titta på den första bokstaven i det här fallet, därigenom hashing det. Hashning är en allmän term som innebär du ta något som indata och du producerar några utgång. Och utgången i det fall är platsen du vill söka, den första plats, andra plats, tredje. Så ingången är äpple, utgången är först. Ingången är banan, den utgång ska vara sekund. Ingången är cantaloupemelon, utgången bör vara tredje. Ingången är blåbär, den utgång bör återigen vara sekund. Och det är vad hjälper dig att ta genvägar genom ditt minne För att komma till ord eller data mer effektivt. 

Nu minskar vår tid potentiellt med så mycket som en av 26, eftersom om man antar att du ha så många "a" ord som "z" ord som "q" ord, som är egentligen inte realistic-- du kommer att ha skev över vissa bokstäver i alphabet-- men detta skulle vara en inkrementell tillvägagångssätt som inte tillåter du att få ord mycket snabbare. Och i verkligheten, en sofistikerad program, googles av världen, den Facebooks av world-- de skulle använda en hash-tabell för många olika ändamål. Men de skulle inte vara så naiva att bara titta på den första bokstaven i äpple eller banan eller päron eller cantaloupemelon, eftersom du kan se dessa listor kan fortfarande få långa. 

Och så detta kan fortfarande vara sort av linear-- så sorts långsam, liksom med den stora O i n som vi diskuterade tidigare. Så vad en riktigt bra hash tabellen do-- det kommer att ha en mycket större matris. Och det kommer att använda en mycket mer sofistikerad hashningsfunktion, så att det inte bara titta på "a." Kanske tittar på "a-p-p-l-e" och på något sätt omvandlar dessa fem bokstäver in den plats där Apple ska lagras. Vi är bara naivt att använda bokstaven "a" ensam, eftersom det är trevlig och enkel. 

Men en hashtabell, i Till slut kan du tror av som en kombination av en array, som var och en har en länkad lista som är idealiskt bör vara så kort som möjligt. Och detta är inte en självklar lösning. I själva verket är mycket av den finjustering som pågår under huven när genomförandet av dessa typer av avancerade datastrukturer är vad som är rätt längden på arrayen? Vad är rätt hashfunktionen? How do you lagra saker i minnet? 

Men inser hur snabbt denna typ av diskussion eskalerade, antingen så långt att det är typ av över huvudet på denna punkt, vilket är bra. Men vi började, minns, med verkligt något låg nivå och elektronisk. Och så detta är igen tema av abstraktion, där när du börjar ta för beviljas, OK, jag har det-- det finns fysiskt minne, OK, fick det, varje fysisk plats har en adress, OK, jag fick det, kan jag företräder dessa adresser som arrows-- du kan mycket snabbt börjar få mer sofistikerade samtal som i slutändan verkar vara att låta oss att lösa problem som söker och sortering mer effektivt. Och vara säker på, too-- eftersom jag tror att detta är den djupaste vi har gått in i något Dessa CS ämnen proper-- vi ve gjort i en och en halv dag på detta pekar vad du kanske normalt göra över Under åtta veckor i en termin. 

Eventuella frågor om dessa? Nej? Okej. Tja, varför inte vi stannar där, starta lunch några minuter tidigare, återupptas i nästan en timme? Och jag ska dröja lite med frågor. Då kommer jag att behöva gå ta ett par samtal om det är OK. Jag ska sätta på lite musik under tiden, men lunch bör vara runt hörnet.