DAVID MALAN: Oké. We zijn terug. Dus in dit segment op de programmering wat Ik dacht dat we zouden doen, is een mix van de dingen. One, doe een beetje iets hands-on, zij het met behulp van een meer speelse programmering environment-- een die demonstratief van precies het soort ideeën we hebben het over, maar een beetje meer formeel. Twee, kijken naar enkele van de meer technische mogelijkheden dat een programmeur eigenlijk zou oplossen problemen, zoals het zoeken probleem dat hebben we gekeken naar voor en ook een meer fundamenteel interessant probleem van het sorteren. 

We zijn net uitgegaan van het begin te gaan dat het telefoonboek werd opgelost, maar dat alleen is eigenlijk een soort van een harde probleem met veel verschillende manieren op te lossen. Dus we zullen deze te gebruiken als een categorie problemen vertegenwoordiger van de dingen die kunnen worden opgelost in het algemeen. En dan zullen we praten over in detail welke heten data structures-- liefhebber manieren, zoals gelinkte lijsten en hash tables en bomen die een programmeur zou eigenlijk Gebruik en algemeen gebruik op een whiteboard te schilderen een beeld van wat hij of zij voorziet voor de uitvoering van een stukje software. 

Dus laten we de hands-on gedeelte eerste. Dus gewoon je handen vuil met een milieu genoemd scratch.mit.edu. Dit is een tool die we gebruiken in onze undergraduate klasse. Hoewel het is ontworpen voor kinderen van 12 jaar en ouder, we gebruiken voor het up een deel van dat nogal wat want het is een mooie, leuke grafische manier van leren een beetje iets over programmeren. Dus ga naar die URL, waar u moet een pagina te zien heel graag dit, en ga je gang en klik op Word lid van Scratch rechtsboven en kies een gebruikersnaam en een wachtwoord en uiteindelijk krijg je een account-- scratch.mit.edu. Ik dacht dat ik dit als een gelegenheid eerste om dit aan te tonen. Een vraag kwam ter sprake tijdens de pauze over wat code ziet er eigenlijk uitziet. En we spraken tijdens de pauze over C, in het bijzonder een particular-- lager niveau in een oudere taal. En ik heb gewoon een snelle Google zoeken naar C-code te vinden voor binary search, het algoritme dat we gebruikt om eerder te zoeken die telefoonboek. Dit specifieke voorbeeld, natuurlijk niet een telefoonboek te zoeken. Het zoekt gewoon een hele hoop nummers in het geheugen van de computer. Maar als je wilt gewoon een visuele gevoel van wat een echte programmering taal eruit ziet, het lijkt een beetje iets als dit. Dus het is ongeveer 20-plus, 30 of zo regels code, maar het gesprek dat we hadden meer dan break was over hoe dit werkelijk wordt veranderd in nullen en enen en als je kunt niet zomaar terugkeren dat verwerken en gaan van nullen en enen terug naar code. 

Helaas is het proces is zo transformatieve dat het een stuk makkelijker gezegd dan gedaan. Ik ging verder en eigenlijk draaide dat programma, Binary Search, in nullen en enen in de vorm van een programma genaamd de compiler die ik toevallig hier recht op mijn Mac. En als je kijkt naar het scherm hier, met de nadruk in het bijzonder Op deze middelste zes kolommen alleen, je zult alleen nullen en enen te zien. En dat zijn de nullen en enen die componeren precies dat zoeken programma. 

En dus elke brok van vijf bits, elke byte van nullen en enen hier, vertegenwoordigen wat instructie typisch in een computer. En in feite, als je hebt gehoord van de marketing slogan 'Intel inside' - dat, Uiteraard betekent gewoon dat je een Intel CPU of de hersenen in de computer. En wat dat betekent om een ​​CPU is dat u een instructie set, bij wijze van spreken. 

Elke CPU in de wereld, vele hen gemaakt door Intel deze dagen, begrijpt een eindige aantal instructies. En die instructies zijn zo laag niveau als add deze twee getallen bij elkaar, vermenigvuldigen deze twee getallen elkaar, bewegen dit stuk van de gegevens van hier hier in het geheugen, dan deze Informatie van hier naar hier in het geheugen, en zo forth-- zo heel erg low-level, bijna elektronische details. Maar met de wiskundige operaties gekoppeld met wat we eerder hebben besproken, de representatie van data als nullen en enen, kan bouw je alles dat een computer vandaag de dag kan doen, of het is tekstueel, grafisch, muzikaal, of anders. 

Dus dit is heel makkelijk te krijgen verloren in het onkruid van snel. En er is een heleboel syntactische uitdagingen waarbij als je de eenvoudigste te maken, domste van typefouten geen van de programma zal ook werken. Etc. in plaats van een taal als C vanmorgen, Ik dacht dat het zou zijn leuker om daadwerkelijk te doen iets meer visuele, die terwijl ontworpen voor kinderen is eigenlijk een perfecte manifestatie van een daadwerkelijke programmering language-- toevallig gebruik maken van foto's in plaats van tekst om die ideeën vertegenwoordigen. 

Dus zodra je inderdaad een -account op scratch.mit.edu, klikt u op de knop Create linksboven van de site. En je moet een omgeving als te zien degene die ik sta op het punt om te zien op mijn scherm hier. En we zullen gewoon een beetje door te brengen beetje tijd hier te spelen. Laten we eens kijken of we kunnen niet alles wat op te lossen problemen samen als volgt. 

Dus wat je ziet binnen deze environment-- en eigenlijk gewoon laten me pauze. Is er iemand niet hier? Niet hier? OK. Dus laat me wijzen op een paar kenmerken van deze omgeving. 

Dus in de linkerbovenhoek van het scherm, we hebben stadium Scratch's, om zo te zeggen. Scratch is niet alleen de naam van deze programmeertaal; Het is ook de naam van de kat die zie je standaard daar in oranje. Hij is op een podium, zodat net als ik beschreef de schildpad eerder als zijnde in een rechthoekige witte boord omgeving. werelds Deze kat is volledig afgesloten dat rechthoek up top daar. 

Ondertussen, aan de rechterkant kant hier, het is slechts een scripts, een schone lei als je wil. Dit is waar we heen gaan om te schrijven onze programma's in slechts een moment. En de bouwstenen die we zullen gebruiken om te schrijven dit program-- de puzzel stukken, als je will-- bent die hier in het midden, en ze zijn gecategoriseerd door functionaliteit. Dus, bijvoorbeeld, ik ga om verder te gaan en toont ten minste een van deze. Ik ga om te gaan en klik op de categorie Besturing boven. 

Dus dit zijn de categorieën boven. Ik ga naar klik op de categorie controle. Integendeel, ik ga naar de gebeurtenissen op categorie, de allereerste boven. En als je wilt volgen langs zelfs als we dit doen, je bent zeer welkom is. Ik ga om te klikken en slepen deze eerste, "als groene vlag geklikt." En dan ga ik het gewoon laten vallen ongeveer op de top van mijn lege leien. 

En wat is er leuk is aan Scratch is dat dit stukje van de puzzel, wanneer vergrendeld met andere puzzel stukken, gaat letterlijk doen wat die puzzelstukjes zeggen te doen. Dus, bijvoorbeeld, Scratch heeft gelijk Nu in het midden van zijn wereld. Ik ga om te gaan en te kiezen Nu, laten we zeggen, de categorie Motion, als je wilt naar het doen same-- Motion categorie. En nu zie ik heb een hele stelletje puzzelstukjes hier dat, wederom, een soort van doen wat ze zeggen. En ik ga om verder te gaan en te slepen en laat de beweging blok rechts over hier. 

En merk op dat zodra je krijgt dicht bij de bodem van de "groene vlag geklikt "-knop, bericht hoe een witte lijn verschijnt, alsof het is bijna magnetisch, het wil er naartoe te gaan. Gewoon laten gaan, en het zal breken elkaar en de vormen overeenkomen. En nu kunt u misschien bijna raden waar we gaan met dit. 

Als je kijkt naar de Scratch stadium hier en kijk naar de top van het, je een rood licht te zien, een stopbord en een groene vlag. En ik ga om verder te gaan en let op mijn Screen-- voor slechts een moment, als je kon. Ik ga naar de klik groene vlag op dit moment, en hij bewoog wat lijkt op 10 stappen worden of 10 pixels, 10 punten op het scherm. 

En dus niet zo spannend, maar laat me voorstellen zonder dat dit zelfs het onderwijs, net het gebruik van de eigen eigen intuition-- let ik stel voor dat u erachter te komen hoe om te maken Scratch lopen rechts van het podium af. Laat hem maken voor de rechterzijde van het scherm helemaal naar rechts. Ik geef je een moment of zo te worstelen met dat. Wilt u misschien een kijkje te nemen bij andere categorieën van de blokken. Okee. Dus gewoon samen te vatten, als we de groene vlag geklikt hier en beweeg 10 stappen wordt het alleen instructie, elke keer als ik klik op de groene vlag, wat gebeurt er? Nou, dat is het uitvoeren van mijn programma. Dus kon ik dit doen misschien 10 keer met de hand, maar dit voelt een beetje bit hackish, om zo te zeggen, waarbij ik ben niet echt oplossen van het probleem. Ik ben gewoon opnieuw te proberen en opnieuw en opnieuw en opnieuw totdat ik een soort van ongeluk het bereiken van de richtlijn dat ik uiteengezet om eerder te bereiken. 

Maar we weten uit onze pseudocode eerder dat er dit begrip in de programmering van de looping, iets te doen opnieuw en opnieuw. En dus ik zag dat een heleboel van jullie bereikt voor wat puzzelstukje? Herhaal dit totdat. Dus konden we iets doen achtige herhalen totdat. En wat heb je herhalen totdat precies? 

OK. En laat me gaan met een dat is wat eenvoudiger voor slechts een moment. Laat me gaan en dit te doen. Merk op dat, als je kan hebben onder controle ontdekt, Er is deze herhaling blok, dat ziet er niet uit alsof het zo groot. Er is niet veel ruimte in tussen deze twee gele lijnen. Maar zoals sommigen van u zou kunnen hebben opgevallen, als je slepen en neerzetten, merken hoe het groeit om de vorm te vullen. 

En je kunt nog meer proppen. Het zal alleen maar blijven groeien als u sleept en zweven over het. En ik weet niet wat er is best hier, dus laat mij tenminste herhaal vijf keer, voor Zo, en ga dan terug naar het podium en klik op de groene vlag. En nu merken dat het helemaal er niet. 

Nu een aantal van jullie voorgesteld, zoals Victoria wist alleen, herhaal 10 keer. En dat in het algemeen doet hem de hele weg, maar zou er niet een meer robuuste zijn manier dan willekeurig uitzoeken hoeveel moves te maken? Wat zou een betere blok dan herhaal 10 keer zijn? 

Ja, dus waarom niet iets dat altijd doen? En nu laat ik verplaats deze puzzelstukje binnen is er en zich te ontdoen van deze. Let nu op, ongeacht waar Scratch begint, gaat hij naar de rand. En gelukkig MIT, die maakt Scratch, net zorgt ervoor dat hij nooit verdwijnt volledig. U kunt altijd pak zijn staart. 

En net intuïtief, waarom doet hij in beweging blijven? Wat is hier aan de hand? Hij lijkt te hebben stilgestaan, maar dan als ik pick-up en sleep hij blijft te willen gaan daar. Waarom is dat? Waarlijk, een computer is letterlijk gaan doen wat je hem vertelt wat te doen. Dus als je het verteld eerder doen het volgende ding altijd, bewegen 10 stappen, het gaat om door te gaan en gaan totdat ik raakte de rode stopbord en stoppen met het programma helemaal. 

Dus zelfs als je niet dit te doen, hoe kon ik maken Scratch move sneller over het scherm? Meer stappen, toch? Dus in plaats van het doen van 10 op een moment, waarom doen we niet ga je gang en verander het to-- wat zou je propose-- 50? Dus nu ga ik klik op de groene vlag, en inderdaad, hij gaat echt snel. 

En dit, natuurlijk, is gewoon een manifestatie van animatie. Wat is animatie? Het is gewoon tonen u de mens een hele hoop foto's echt, echt, echt snel. En dus als we gewoon vertellen hem om meer stappen te bewegen, we gewoon het effect te verandering waar hij op het scherm des te sneller per tijdseenheid. 

Nu is de volgende uitdaging die ik voorgesteld was om hem stuiteren de rand. En zonder te weten wat de puzzel stukken exist-- want het is fijn als je niet naar het krijgen fase van de challenge-- wat wil je intuïtief doen? Hoe zouden we hem terug te stuiteren en weer, tussen de linker en rechter? 

Ja. Dus we moeten een soort conditie, en we lijken te conditionals hebben, om zo te spreken, onder de categorie controle. Welke van deze blokken we waarschijnlijk willen? Ja, misschien 'als, dan. " Zo merken dat onder de gele blokken we hier hebben, is er deze "if" of deze "if, else" blok dat zal stellen ons in staat om een ​​beslissing om dit te doen of om dat te doen. En je kunt zelfs nesten om meerdere dingen te doen. Of als je er nog niet bent gegaan, ga je gang naar de categorie Sensing en-- laten we eens kijken of het hier. 

Dus wat blok zou hier nuttig zijn op te sporen als hij van het podium? Ja, merken dat sommige van deze blokken kunnen worden geparametriseerd, om zo te zeggen. Ze kunnen een soort van worden aangepast, niet In tegenstelling tot HTML gisteren met attributen, waar die attributen soort aanpassen van het gedrag van een tag. Op dezelfde manier hier, kan ik grijp deze ontroerende blok en verandering en de vraag stellen: Bent u de muis aan te raken pointer als de cursor of bent u het aanraken van de rand? 

Dus laat me gaan en dit te doen. Ik ga om uit te zoomen voor een moment. Laat ik grijp deze puzzelstukje Hier, dit puzzelstukje dit, en ik ga wirwar ze voor slechts een moment. Ik ga dit te verplaatsen, verandert dit ontroerende rand, en ik ga om beweging te doen. Dus hier zijn enkele ingrediënten. Ik denk dat ik alles wat ik wil hebben. 

Iemand zou willen voorstellen hoe ik kan verbinden deze misschien van boven naar beneden om het probleem van oplossen Scratch beweging rechts naar links naar rechts te links naar rechts naar links, elk tijd alleen maar stuiteren van de muur? Wat wil ik doen? Welk blok moet ik aansluiten op de "Wanneer groene vlag geklikt eerste"? 

OK, dus laten we beginnen met de "voor altijd." Wat gaat er in de volgende stap? Iemand anders. OK, ga stappen. Okee. Dan wat? Dus dan is het zo. En merk, ook al ziet het er samen ingeklemd strak, het zal alleen maar groeien in te vullen. Het zal gewoon springen in waar ik wil. 

En wat moet ik tussen de if en de toenmalige? Waarschijnlijk "als het aanraken van de rand." En let op, nogmaals, het is te groot voor, maar het zal groeien te vullen. En vervolgens 15 graden? Hoeveel graden? Ja, dus 180 zal draaien me helemaal rond. Dus laten we eens kijken als ik dit recht. Laat me uitzoomen. 

Laat me slepen Scratch up. Dus hij is een beetje vervormd nu, maar dat is prima. Hoe kan ik gemakkelijk resetten hem? Ik ga een beetje vals te spelen. Dus ik ben het toevoegen van een ander blok, alleen maar om duidelijk te zijn. Ik wil dat hij 90 graden punt om de juiste standaard, dus ik ben gewoon gaan om hem te vertellen dat programmatisch doen. En hier gaan we. We lijken te hebben gedaan. Het is een beetje raar, want Hij loopt op zijn kop. Laten we noemen dat een bug. Dat is een vergissing. Een bug is een fout in een programma, een logische fout dat ik, de mens, maakte. Waarom gaat hij op zijn kop? Heeft MIT verknallen of heb ik? 

Ja, ik bedoel, het is niet het MIT fout. Ze gaf me een stukje van de puzzel dat zegt draaien sommige aantal graden. En op voorstel van Victoria's, Ik ben het draaien van 180 graden, welke de juiste intuïtie. Maar het draaien van 180 graden letterlijk betekent dat het draaien van 180 graden, en dat is niet echt wat ik wil, blijkbaar. Omdat in ieder geval is hij in Dit tweedimensionale wereld, dus draaien gaat werkelijk om hem ondersteboven spiegelen. 

Ik wil waarschijnlijk wat blok gebruiken in plaats daarvan, op basis van wat u hier ziet? Hoe kunnen we dit oplossen? Ja, dus we konden wijzen in de tegengestelde richting. En eigenlijk zelfs dat is zal niet genoeg zijn, want we kunnen alleen vaste code te wijzen links of rechts. 

Weet je wat we kunnen doen? Het lijkt erop dat we een gemak blok hier. Als ik in te zoomen, zie iets wat we hier van? Dus het lijkt erop dat MIT heeft een abstractie gebouwd in hier. Dit blok lijkt gelijk te zijn waaraan andere blokken, meervoud? 

Dat een blok lijkt gelijk te zijn dit hele trio blokken dat we hier hebben. Dus het blijkt dat ik kan vereenvoudigen mijn programma door zich te ontdoen van al die en zet deze in hier. En nu is hij nog steeds een beetje buggy, en dat is prima voor nu. We laten dat. Maar mijn programma is zelfs eenvoudiger en ook dit representatief zou van een doelpunt in programming-- is ideaal om uw code eenvoudig, zo compact mogelijk, terwijl het nog steeds als leesbaar mogelijk. Je wilt niet om het zo beknopt te maken dat het moeilijk is om te begrijpen. 

Maar let op, ik heb vervangen drie blokken met één, en dat is misschien wel een goede zaak. Ik heb weg geabstraheerd het begrip te controleren of u bent Aan de rand met slechts één blok. Nu kunnen we veel plezier met deze, in feite. Dit betekent niet zozeer toe te voegen intellectuele waarde, maar speelse waarde. Ik ga om verder te gaan en hier grijp deze sound. Dus laat me ga je gang, en laat me stoppen met het programma voor een moment. Ik ga naar het volgende op te nemen, waardoor toegang tot mijn microfoon. 

Daar gaan we. Ouch. Laten we proberen dit opnieuw. Daar gaan we. OK, nam ik de verkeerde dingen. Daar gaan we. Ouch. Ouch. Okee. Nu moet ik om zich te ontdoen van. Okee. 

Dus nu heb ik een opname van enkel "ouch." Dus nu ga ik om te gaan vooruit en noemen dit "ouch." Ik ga om terug te gaan mijn scripts en nu Opmerking Er is dit blok dat heet spelen geluid 'miauw' of speel het geluid "ouch." Ik ga dit te slepen, en waar de moet ik dit voor het komische effect? Ja, dus nu is het soort buggy, want nu deze block-- merk op hoe dit "als aan de rand, bounce "is een soort van self-contained. Dus ik nodig om dit te bevestigen. Laat me gaan en dit te doen. Laat me te ontdoen van deze en ga terug naar onze oorspronkelijke, meer weloverwogen functionaliteit. Dus "als het aanraken van de rand, dan" Ik wil te draaien, zoals voorgesteld Victoria, 180 graden. En ik wil spelen het geluid "ouch" daar? 

Ja, ziet het buiten die gele blok. Dus ook dit zou een bug, maar ik heb het gezien. Dus ik ga het slepen hier, en merk nu is het in de "als." Dus de "als" is dit soort van soortgelijke arm-achtige vlek dat wordt alleen maar doen wat binnen van het. Dus nu als ik uitzoomen op het risico van annoying-- 

COMPUTER: Auw, auw, auw. 

DAVID MALAN: En het zal gewoon eeuwig doorgaan. Nu alleen om dingen te versnellen Hier, laat me ga je gang en open te stellen, laten we say-- laat me gaan om een ​​aantal van mijn eigen spullen uit de klas. En laat me open te stellen, laten we zeggen, dit één gemaakt door een van ons onderwijs fellows een paar jaar geleden. Dus sommigen van jullie misschien herinneren dit spel van weleer, en het is eigenlijk opmerkelijk. Hoewel we hebben gedaan de eenvoudigste programma's op dit moment, laten we eens kijken wat dit daadwerkelijk uitziet. Laat me hit te spelen. 

Dus in dit spel, we hebben een kikker, en het gebruik van de pijl keys-- Hij neemt grotere stappen dan ik remember-- Ik heb controle over deze kikker. En het doel is over het aan de slag weg zonder in de auto's. En laten we see-- als ik ga hier, ik moeten wachten op een logboek om door te bladeren. Dit voelt als een bug. Dit is een soort van een bug. Okee. Ik ben op dit hier, daar, en dan houdt u doorgaan tot je alles de kikkers naar de waterlelies. Nu is dit zou kunnen kijken des te complexer, maar laten we proberen in te breken dit neer mentaal en verbaal in zijn samenstellende blokken. Dus er is waarschijnlijk een puzzel stuk dat we nog niet hebben gezien maar dat is het reageren op toetsaanslagen, om dingen die ik hit op het toetsenbord. 

Dus er is waarschijnlijk een soort van blok dat zegt, als sleutel gelijk op, dan is er iets met Scratch-- doen misschien verplaatsen 10 stappen op deze manier. Als omlaag toets wordt ingedrukt, bewegen 10 stappen op deze manier, of links-toets, beweeg 10 stappen op deze manier, 10 stappen. Ik heb duidelijk draaide de kat in een kikker. Dus dat is precies waar de kostuum, zoals Scratch oproepen het-- we gewoon een foto van de kikker geïmporteerd. 

Maar wat gebeurt er? Welke andere regels code, wat andere puzzelstukjes deed Blake, ons onderwijs collega, Gebruik in dit programma, blijkbaar? Wat is het maken van alles move-- Wat de programmering te bouwen? 

Motion, sure-- zodat de Verplaats blok, zeker. En wat is dat beweging blok Binnenin, waarschijnlijk? Ja, een soort lus, misschien een voor altijd te blokkeren, misschien een herhaling block-- herhaal tot blok. En dat is wat het maken van de logs en de waterlelies en al het andere verplaatsen heen en weer. Het is gewoon eindeloos gebeurt. 

Waarom zijn sommige van de auto's bewegen sneller dan de anderen? Wat is er anders aan deze programma's? Ja, waarschijnlijk een aantal van hen nemen meer stappen tegelijk en sommige minder stappen tegelijk. En het visuele effect is snel versus langzaam. 

Wat denk je dat er gebeurd is? Toen ik mijn kikker helemaal overkant van de straat en de rivier op het lelieblad, iets Opmerkelijk is gebeurd. Wat is er gebeurd zodra ik dat deed? Het is gestopt. Dat kikker gestopt, en Ik kreeg een tweede kikker. Dus wat construct moet zijn er gebruikt, welke functie? 

Ja, dus er is een soort van "If" conditioneren daar ook. En het blijkt out-- we niet zien dit-- maar er zijn andere blokken in dat er kan zeggen, als je aanraakt een ander ding op het scherm, als je het aanraken van het lelieblad, "dan." En dan is dat wanneer we maken de tweede kikker verschijnen. Dus ook al is dit spel zeker zeer gedateerd, hoewel op het eerste gezicht Er is zoveel gaande on-- en Blake heeft dit niet zweep in twee minuten, het kostte hem waarschijnlijk meerdere uren om dit spel te maken op basis van zijn geheugen of video's van versie ervan weleer. Maar al deze kleine dingen gaande scherm afzonderlijk neer deze zeer eenvoudige constructs-- bewegingen of verklaringen zoals we hebben besproken, loops en omstandigheden, en dat is het zo'n beetje. Er is een paar andere liefhebber functies. Sommige zijn zuiver esthetisch of akoestische, net als de geluiden die ik alleen met gespeeld. Maar voor het grootste deel, je hebben in deze taal, Scratch, alle fundamentele bouwstenen die u hebben in C, Java, JavaScript, PHP, Ruby, Python, en een aantal andere talen. Heeft u vragen over Scratch? Okee. Dus zullen we niet duiken in dieper naar Scratch, al ben je van harte welkom dit weekend, vooral als je kinderen hebt of nichten en neven en dergelijke, om hen kennis te laten Scratch. Het is eigenlijk een heerlijk speelse omgeving met, zoals de auteurs zeggen, zeer hoge plafonds. Hoewel we begonnen met zeer low-level details kan je echt doen nogal een beetje mee, en dit is wellicht een demonstratie van precies dat. 

Maar laten we nu overgaan naar wat meer verfijnde problemen, als je wil, bekend als "zoeken" en "Sorteren" algemeen. We hadden deze telefoon boek earlier-- hier een andere enkel voor discussion-- dat we in staat waren om te zoeken efficiënter omdat een belangrijke aanname. En alleen maar om duidelijk te zijn, wat veronderstelling was ik het maken van bij het zoeken door middel van deze telefoon boeken? Dat Mike Smith was in het telefoonboek, hoewel ik kunnen verwerken zou zijn het scenario zonder hem er als ik voortijdig gestopt gewoon. Het boek is alfabetisch. En dat is een zeer royale veronderstelling, want dat betekent someone-- Ik ben een beetje van het snijden van een hoek, zoals ik ben sneller omdat iemand anders deed veel hard werk voor mij. 

Maar wat als de telefoon boek werden ongesorteerd? Misschien Verizon kreeg lui, gooiden iedereen de namen en nummers in daar misschien in de volgorde waarin ze aangemeld voor telefoon service. En hoeveel tijd kost het me iemand als Mike Smith vinden? 1000 pagina telefoon book-- hoeveel pagina's moet ik om door te kijken? 

Allemaal. Je bent een soort van pech. Je moet letterlijk bij elke look pagina als het telefoonboek is gewoon willekeurig gesorteerd. Je zou je geluk en vind Mike op de eerste pagina, omdat hij was de eerste klant naar de telefoon dienst bestelt. Maar hij zou de laatste zijn geweest, ook. 

Dus willekeurige volgorde is niet goed. Dus stel dat we moeten het sorteren telefoonboek of in het algemeen soort data die we hebben gekregen. Hoe kunnen we dat doen? 

Nou, laat me gewoon proberen een eenvoudig voorbeeld hier. Laat me ga je gang en gooi een paar nummers op het bord. Stel de nummers we zijn, laten we zeggen, vier, twee, één en drie. En, Ben, sorteren van deze nummers voor ons. 

OK goed. Hoe heb je dat gedaan? Okee. Dus beginnen met de kleinste waarde en de hoogste, en dat is echt een goede intuïtie. En beseffen dat we mensen zijn eigenlijk vrij goed in het oplossen van problemen als dit, op zijn minst wanneer de data is relatief klein. Zodra je begint te honderden hebben getallen duizenden getallen, miljoenen nummers, waarschijnlijk Ben kon het niet helemaal zo snel doen, ervan uitgaande dat er gaten in de getallen. Vrij gemakkelijk te tellen tot een miljoen anders alleen tijdrovend. 

Dus het algoritme het klinkt zoals Ben gebruikt net nu was zoeken naar het kleinste getal. Dus hoewel wij mensen kunnen nemen in veel informatie visueel, een computer is eigenlijk wat beperkter. De computer kan alleen kijken naar een byte in een tijd of misschien vier bytes op een tijd-- deze dagen misschien 8 bytes bij een tijd-- maar een zeer klein aantal van bytes op een gegeven moment. 

Dus gezien het feit dat we echt vier afzonderlijke waarden hier-- en je kunt bedenken Ben als hebbende oogkleppen op als hij een computer, dat hij niet anders kan zien dan één nummer bij een tijd-- dus we zullen in de regel aannemen, zoals in Engels, zullen we lezen van rechts naar links. Dus het eerste nummer Ben waarschijnlijk leek bij was vier en dan heel snel besefte dat is een vrij grote number-- laat me blijven zoeken. 

Er zijn twee. Wacht even. Twee kleiner is dan vier. Ik ga om te onthouden. Twee is nu de kleinste. Nu een-- dat is nog beter. Dat is nog kleiner. Ik ga over twee vergeten en slechts een herinneren nu. 

En kon hij stoppen met zoeken? Wel, hij kon op basis van van deze informatie, maar hij zou beter zoeken de rest van de lijst. Want wat als nul waren in de lijst? Wat als negatief waren in de lijst? Hij weet alleen dat zijn antwoord klopt als hij uitputtend controleerde de hele lijst. Dus kijken we naar de rest van dit. Drie: dat was een verspilling van tijd. Pech, maar ik was nog juist te doen. En nu hij vermoedelijk selecteerde de kleinste getal en zet ze gewoon aan het begin van de lijst, zoals ik hier doe. Nu, wat heb je nu doen, ook al je hebt lang niet over nadenken In zoverre? Herhaal het proces, dus een soort lus. Er is een bekend idee. Dus hier is vier. Dat is op dit moment de kleinste. Dat is een kandidaat. Niet meer. Nu heb ik twee gezien. Dat is de volgende kleinste element. Drie: dat is niet kleiner, dus Ben nu kunnen rukken uit de twee. 

En nu zijn we herhalen het proces, en Uiteraard krijgt drie volgende uitgetrokken. Herhaal dit proces. Vier wordt uitgetrokken. En nu zijn we uit van de nummers, dus de lijst moeten worden gesorteerd. 

Inderdaad is dit een formele algoritme. Een computer wetenschapper zou doen noemen dit "selectie sorteren," het idee is een soort lijst iteratively-- weer en weer selecteren het kleinste nummer. En wat is leuk over het is het is gewoon zo darn intuïtief. Het is zo simpel. En u kunt hetzelfde herhalen bewerking opnieuw en opnieuw. Het is makkelijk. 

In dit geval was het snel, maar hoe lang duurt het eigenlijk doen? Laten we het erop en voel me een beetje vervelend. Dus één, twee, drie, vier, vijf zes, zeven, acht, negen, 10, 11, 12, 13, 14, 15, 16-- willekeurig aantal. Ik wilde alleen maar meer dit tijd dan alleen de vier. Dus als ik een hele heb stelletje getallen now-- te zelfs niet uit wat ze zijn-- laten na te denken over wat dit algoritme is echt leuk. 

Stel dat er nummers zijn. Nogmaals, maakt niet uit wat ze zijn, maar ze zijn willekeurig. Ik ben het aanbrengen van Ben's algoritme. Ik moet het kleinste getal te selecteren. Wat zal ik doen? En ik ga fysiek doe het dit keer om het uit te treden. Kijken, kijken, kijken, kijken, kijken. Alleen tegen de tijd dat ik bij het einde van de lijst kan Ik besef dat de kleinste nummer twee was dit keer. Men is niet in de lijst. Dus ik zette twee. 

Wat moet ik nu doen? Kijken, kijken, kijken, kijken. Nu vond ik het getal zeven, want er hiaten in deze numbers-- maar gewoon willekeurig. Okee. Dus nu kan ik neer te zetten zeven. Op zoek naar kijken, kijken. 

Nu ben ik ervan uit, van Natuurlijk, dat Ben niet extra RAM, extra geheugen, omdat, natuurlijk, Ik ben op zoek naar hetzelfde nummer. Voorwaar, ik zou hebben gedacht al deze getallen, en dat is absoluut waar. Maar als Ben al onthoudt van de nummers die hij heeft gezien, Hij heeft niet echt gemaakt fundamentele vooruitgang want hij heeft al een zoekfunctie door de nummers op het bord. Remembering alle van de getallen niet helpt, want hij kan nog steeds als een computer alleen kijken naar, we hebben gezegd, één nummer tegelijk. Dus er is geen soort van cheat er zijn die u kunt benutten. 

Dus in werkelijkheid, zoals ik blijven zoeken in de lijst, Ik heb letterlijk om gewoon door te gaan heen en weer door het, plukken uit de volgende kleinste getal. En zoals je kunt soort afleiden uit mijn domme bewegingen, dit wordt gewoon heel vervelend heel snel, en ik lijken om terug te gaan en weer, heen en weer nogal wat. Nu om eerlijk te zijn, heb ik niet te gaan zo, nou ja, laten we see-- om eerlijk te zijn, Ik heb niet heel lopen zoveel stappen elke keer. Want natuurlijk ik Selecteer nummers uit de lijst, de rest van de lijst wordt steeds korter. 

En dus laten we nadenken over hoeveel stappen Ik ben eigenlijk gesjouw door elke keer. In de eerste situatie hadden we 16 nummers, en zo maximally-- laten we gewoon doe dit voor een discussion-- Ik moest om te kijken tot en met 16 nummers aan de kleinste vinden. Maar zodra ik uitgerukt het kleinste getal, hoe lang was de resterende lijst, natuurlijk? Slechts 15. Dus hoeveel nummers deed Ben of ik heb om te kijken door de tweede keer? 15, gewoon om te gaan en vind de kleinste. Maar nu natuurlijk, de lijst is, Ook kleiner dan voorheen. Dus hoeveel stappen heb ik moet u de volgende keer? 14 en daarna 13 en vervolgens 12, plus punt, dot, dot, totdat ik ben links met slechts één. Dus nu een computer wetenschapper zou doen vragen, nou ja, wat doet dat allemaal gelijk? Het is gelijk aan eigenlijk een aantal betonnen getal dat we konden zeker doen rekenkundig, maar we willen praten de efficiëntie van algoritmen een beetje meer formulaically, ongeacht hoe lang de lijst. 

En dus weet je wat? Dit is 16, maar zoals ik al eerder zei, laten we gewoon bellen met de omvang van het probleem n, waarbij n een getal. Misschien is het 16, misschien is het drie, misschien is het een miljoen. Ik weet het niet. Kan me niet schelen. Wat ik echt wil is een formule die ik kan om dit algoritme vergelijken tegen andere algoritmen dat iemand zou kunnen claimen zijn beter of slechter. 

Dus het blijkt, en alleen ik weten dit uit de lagere school, dat dit werkt eigenlijk naar hetzelfde zoiets als n meer dan n plus één meer dan twee. En dit gebeurt evenaren, of Natuurlijk, n kwadraat plus n meer dan twee. Dus als ik wilde een formule voor hoeveel stappen waren betrokken bij naar alle van die nummers weer en opnieuw en opnieuw, zou ik zeggen het is n kwadraat plus n meer dan twee. Maar weet je wat? Dit ziet er gewoon rommelig. Ik heb echt een algemeen gevoel van dingen. En je zou kunnen herinneren uit middelbare school dat er is de notie van de hoogste orde termijn. Welke van deze voorwaarden, de n kwadraat, de n, of de helft, heeft de meeste invloed in de tijd? Hoe groter krijgt n, waarin van deze zaken het meest? 

Met andere woorden, als ik stop op een miljoen, n kwadraat zal hoogstwaarschijnlijk de dominerende factor, omdat een miljoen keer zelf is een stuk groter dan plus een extra miljoen. Dus weet je wat? Dit is zo'n groot darn nummer als u vierkant een nummer. Dit maakt eigenlijk niet uit. We gaan gewoon kruis dat out en vergeet het. En dus een computer wetenschapper zou zeggen dat de efficiëntie van dit algoritme in de orde van n squared-- Ik bedoel echt een benadering. Het is een soort van ongeveer n kwadraat. Na verloop van tijd, hoe groter en n groter wordt, dit is een goede schatting voor wat efficiency of gebrek aan efficiëntie van dit algoritme eigenlijk. En ik afleiden dat, uiteraard, van daadwerkelijk doen van de wiskunde. Maar nu ben ik gewoon zwaaien mijn handen, omdat ik net wil een algemeen gevoel van dit algoritme. 

Dus met behulp van dezelfde logica, ondertussen, laten we eens kijken naar een ander algoritme we keken al at-- lineair zoeken. Toen ik op zoek was de telefoon book-- niet sorteren het, zoeken via de telefoon book-- we bleef maar zeggen dat het was 1000 stappen, of 500 stappen. Maar laten we generaliseren dat. Als er n pagina's in het telefoonboek, wat is de rijtijden of de efficiëntie van lineair zoeken? Het is aan de orde van hoeveel stappen vinden Mike Smith met behulp van lineaire zoeken, de eerste algoritme, of zelfs de tweede? 

In het ergste geval, Mike is aan het eind van het boek. Dus als het telefoonboek heeft 1.000 pagina's, we zei vorige keer, in het ergste geval, Het zou kunnen nemen ongeveer hoe vele pagina's om Mike te vinden? Net als 1000. Het is een bovengrens. Het is een slechtst denkbare situatie. Maar nogmaals, we zijn afgestapt van nummers zoals 1000 nu. Het is gewoon n. 

Dus wat is de logische conclusie? Het vinden van Mike in een telefoon boek dat n pagina's heeft zou kunnen nemen, in het ergste geval, hoeveel stappen in de orde van n? En inderdaad een computer wetenschapper zou zeggen dat de looptijd, of prestaties of de efficiëntie of inefficiëntie, van een algoritme zoals een lineair zoeken is in de orde van n. En we kunnen hetzelfde van toepassing logica van iets uit het oversteken zoals ik net deed naar de tweede algoritme we hadden met de telefoon boek, waar we gingen twee pagina's tegelijk. 

Dus 1.000 pagina telefoonboek zou neem ons 500 pagina bochten, plus één als we het dubbele van een stukje terug. Dus als een telefoonboek heeft n pagina's, maar we doen twee pagina's tegelijk, Dat is ongeveer wat? N over twee, dus dat is net als n meer dan twee. Maar ik maakte de vordering een ogenblik geleden dat n meer dan two-- dat is een beetje hetzelfde als gewoon n. Het is gewoon een constante factor, informatici zou zeggen. Laten we alleen richten op de variabelen, really-- de belangrijkste variabelen in de vergelijking. 

Dus lineair zoeken, of gedaan één pagina per keer of twee pagina's tegelijk, is een soort van wezen hetzelfde. Het is nog steeds aan de orde van n. Maar ik had met mijn foto eerdere dat de derde algoritme niet lineair. Het was niet een rechte lijn. Het was dat de gebogen lijn, en de algebraïsche formule er was wat? Log van N-- dus meld basis twee van n. En we hoeven niet in te gaan veel detail op logaritmes vandaag, maar de meeste computer wetenschappers zou niet zelfs je vertellen wat de basis is. Want het is allemaal constanten, zo te zeggen, slechts kleine numerieke verschillen. En dus dit zou een zeer gemeenschappelijk zijn manier voor met name formele computer wetenschappers op een bord of programmeurs op een wit bord eigenlijk ruzie die algorithme zouden gebruiken of wat de efficiëntie hun algoritme is. 

En dit is niet per se iets u bespreken in elk detail, maar een goede programmeur is iemand die heeft een stevige, formele achtergrond. Hij is in staat om te spreken je in dit soort manier en eigenlijk maken kwalitatieve argumenten waarom een ​​algoritme of een stukje software superieur in zekere zin naar de andere. Omdat je zeker kon alleen nog maar programma van één persoon en tel het aantal seconden het duurt om een ​​aantal nummers te sorteren, en je kunt een aantal draaien programma andere persoon en tel het aantal seconden duurt. Maar dit is een meer algemene zin dat u kunt gebruiken om algoritmen te analyseren, als je wil, net aan papier of gewoon verbaal. Zonder zelfs het runnen van het, zonder zelfs maar te proberen sample-ingangen, je kunt gewoon redeneren doorheen. En dus met het inhuren van een ontwikkelaar of indien met hem of haar soort pleiten voor u waarom hun algoritme, hun geheime saus voor het zoeken miljarden van webpagina's voor uw bedrijf is beter, deze zijn de soorten argumenten die zij Idealiter kunnen maken. Of in ieder geval deze zijn het soort dingen die zou komen in de discussie, op althans in een zeer formele discussie. Okee. Dus Ben voorgestelde iets genaamd selectie sorteren. Maar ik ga voor te stellen dat er andere manieren om dit te doen, ook. Wat ik niet echt leuk over Ben's algoritme is dat hij liep, of hebben me lopen, heen en weer en heen en weer en heen en weer. Wat als in plaats ik moest doen zoiets als deze nummers hier en ik waren gewoon met elkaar omgaan nummer op zijn beurt als ik het gezien? 

Met andere woorden, hier mijn lijst van nummers. Vier, een, drie, twee. En ik ga het volgende doen. Ik ga naar de nummers in te lassen waar ze horen in plaats dan ze een voor een hebt geselecteerd. Met andere woorden, hier is de nummer vier. 

Hier is mijn originele lijst. En ik ga behouden in wezen een nieuwe lijst hier. Dus dit is de oude lijst. Dit is de nieuwe lijst. Ik zie de nummer vier eerste. Mijn nieuwe lijst is aanvankelijk leeg, dus is triviaal het geval dat vier is nu assorti lijst. Ik ben gewoon het nemen van de nummer Ik ben gegeven, en Ik zet het in mijn nieuwe lijst. 

Is dit nieuwe lijst gesorteerd? Ja. Het is dom, want er is slechts één element, maar het is absoluut gesorteerd. Er is niets op zijn plaats. Het is meer interessant, dit algoritme, toen ik naar de volgende stap. 

Nu heb ik een. Dus een natuurlijk behoort bij de begin of het einde van deze nieuwe lijst? Het begin. Dus ik moet wat werk nu te doen. Ik heb het nemen van een aantal vrijheden met mijn marker door gewoon te tekenen dingen waar ik wil dat ze, maar dat is niet echt nauwkeurig in een computer. Een computer, zoals we weten, heeft RAM of Random Access Memory, en dat is een byte en een byte en een byte. En als je een gigabyte aan RAM, heb je een miljard bytes, maar ze zijn fysiek op één locatie. Je kunt niet zomaar verplaatsen stuff door het tekenen op het bord waar je maar wilt. Dus als mijn nieuwe lijst heeft vier locaties in het geheugen, helaas is de vier is al op de verkeerde plaats. 

Dus om het nummer in te voegen één Ik kan niet zomaar hier tekenen. Deze geheugenplaats bestaat niet. Dat zou bedriegen, en ik ben geweest vreemdgaan pictorially voor een paar minuten hier. Dus echt, als ik wil er hier te zetten, Ik moet de vier tijdelijk kopiëren en zet dan de één daar. 

Dat is prima, dat klopt, Dat is technisch mogelijk, maar beseffen dat is extra werk. Ik heb niet gewoon het nummer op zijn plaats. Ik moest eerst een te verplaatsen nummer, zet het dan op zijn plaats, dus ik soort verdubbelde mijn hoeveelheid werk. Dus hou dat in gedachten. 

Maar ik ben nu klaar met dit element. Nu wil ik de nummer drie te grijpen. Waar, natuurlijk, behoort het? Tussenin. Ik kan niet bedriegen meer en zet ze gewoon daar, want, nogmaals, dit geheugen in fysieke locaties. Dus ik moet de vier kopiëren en zet de drie hier. Niet een groot probleem. Het is gewoon een extra stap again-- voelt erg goedkoop. 

Maar nu moet ik gaan naar de twee. De twee natuurlijk hoort hier. Nu begin je te zien hoe het werk kan opstapelen. Nu, wat moet ik doen? Ja, ik heb de vier te bewegen, Ik moet dan de drie kopiëren, en nu kan ik de twee plaatsen. En de vangst met deze algoritme, interessant genoeg, is dat veronderstellen we hebben een meer extreme geval waar het laten we zeggen acht, zeven, zes, vijf, vier, drie, twee, één. Dit is in veel contexten het ergste geval, omdat de darn ding letterlijk achteruit. 

Het maakt eigenlijk niet invloed op Ben's algoritme, omdat in Ben's selectie sort hij gaat houden ga heen en weer door de lijst. En omdat hij was altijd op zoek door de hele resterende lijst, het maakt niet uit waarbij de elementen. Maar in dit geval met mijn invoegen approach-- laten we proberen dit. 

Dus één, twee, drie, vier, vijf, zes, zeven, acht. Een twee drie vier, vijf, zes, zeven, acht. Ik ga naar de acht te nemen, en waar moet ik het zeggen? Nou, aan het begin van mijn lijst, omdat deze nieuwe lijst wordt gesorteerd. En ik steek het uit. 

Waar vind ik de zeven? Verdomme. Het moet er naartoe te gaan, dus Ik moet wat doen kopiëren. En nu de zeven gaat hier. Nu gaan I op de zes. Nu is het nog meer werk. 

Acht heeft om hier te gaan. Seven heeft om hier te gaan. Nu de zes kunt hier terecht. Nu pak ik de vijf. Nu de acht moet gaan hier, zeven heeft hier te gaan, zes heeft hier te gaan, en nu de vijf en herhaal. En ik ben er vrij veel voortdurend in beweging is. 

Dus aan het eind, dit algorithm-- we zullen noem het inbrengen sort-- eigenlijk heeft een hoop werk, ook. Het is gewoon anders soort werk dan Ben's. het werk van Ben had me op de been heen en weer de hele tijd, het selecteren van de kleinste element opnieuw en opnieuw. Dus het was dit heel visuele soort werk. 

Deze andere algoritme, dat nog correct-- zal de baan te krijgen done-- net verandert de hoeveelheid werk. Het lijkt erop dat in eerste instantie ben je besparing, omdat je gewoon bent behandeling van elk element up front zonder te lopen alle de weg door de lijst zoals Ben was. Maar het probleem is, zeker in deze gek gevallen waarin het allemaal achteruit, je bent gewoon een soort van uitstellen van het harde werk totdat je je fouten te repareren. 

En dus als je kunt deze voorstellen acht en zeven en zes en vijf en later vier en drie en twee bewegen hun weg door de lijst, we hebben net veranderde de soort werk dat we doen. In plaats van het doen van het op de begin van mijn iteratie, Ik ben gewoon te doen aan de einde van elke iteratie. Zo blijkt dat dit algoritme Ook het algemeen genoemd insertion sort, Ook in de orde van n kwadraat. Het is eigenlijk niet beter, niet beter helemaal. 

Echter, er is een derde benadering Ik zou ons aanmoedigen om te overwegen, wat dit. Dus stel mijn lijst, voor de eenvoud opnieuw, vier, één, drie, two-- slechts vier nummers. Ben had een goede intuïtie, goede menselijke intuïtie voor, waardoor we vast heel lijst eventually-- insertion sort. Ik overgehaald ons mee. Maar laten we eens kijken naar de eenvoudigste manier om deze lijst te bevestigen. 

Deze lijst is niet gesorteerd. Waarom? In het Engels, uitleggen waarom het is niet echt opgelost. Wat betekent het niet te sorteren? 

STUDENT: Het is niet sequentieel. 

DAVID MALAN: niet op volgorde. Geef me een voorbeeld. 

STUDENT: Leg ze in orde. 

DAVID MALAN: OK. Geef me een meer specifiek voorbeeld. 

STUDENT: oplopende volgorde. DAVID MALAN: Niet oplopende volgorde. Wees nauwkeuriger. Ik weet niet wat je bedoelt met oplopende. Wat is er mis? 

STUDENT: De kleinste van de getallen is niet in de eerste ruimte. 

DAVID MALAN: Kleinste-nummer niet in de eerste ruimte. Wees specifieker. Ik ben beginnen aan te slaan. We rekenen, maar wat is niet in orde hier? 

STUDENT: numerieke volgorde. DAVID MALAN: Numerieke volgorde. Ieders soort boekhouding Het hier-- zeer hoog niveau. Gewoon letterlijk me vertellen wat er verkeerd als een vijf-jaar-oude macht. 

STUDENT: Plus één. 

DAVID MALAN: Wat is dat? 

STUDENT: Plus één. 

DAVID MALAN: Wat bedoel je plus één? Geef me een ander vijf jaar oud. Wat is er mis, mama? Wat is er mis, vader? Wat bedoel je dit niet gesorteerd? 

STUDENT: Het is niet de juiste plaats. 

DAVID MALAN: Wat is niet op de juiste plaats? 

STUDENT: Four. DAVID MALAN: OK, goed. Dus vier is niet waar het zou moeten zijn. In het bijzonder is dit recht? Vier en een, de eerste twee nummers die ik zie. Is dit juist? Nee, ze zijn niet in orde, toch? In feite, denk nu om een ​​computer, ook. Het kan alleen maar kijken naar misschien één, misschien twee dingen op once-- en eigenlijk maar één ding tegelijk, maar het kan ten minste kijken naar een ding dan de volgende ding ernaast. 

Dus zijn deze in orde? Natuurlijk niet. Dus weet je wat? Waarom gaan we niet nemen kindje stappen vaststelling van dit probleem in plaats van het doen van deze buitensporige algoritmen als Ben, waarbij hij is een soort van de vaststelling van het door doorlussen de lijst in plaats van te doen wat ik deed, waar de Ik gewoon een soort van vaste het als we gaan? Laten we gewoon letterlijk breken de notie van order-- numerieke volgorde, noem het wat je want-- in deze paarsgewijze vergelijkingen. 

Vier en één. Is dit de juiste volgorde? Dus laten we dat oplossen. Eén en vier, en dan we zullen gewoon kopiëren dat. Oké, goed. Ik bevestigde een en vier. Drie en twee? Nee. Laat mijn woorden niet overeen met mijn vingers. Vier en drie? 

Het is niet in orde, dus ik ga één, drie, vier, twee doen. OK goed. Nu vier en twee? We moeten dit op te lossen, ook. Dus één, drie, twee, vier. Dus wordt het opgelost? Nee, maar is het dichter bij gesorteerd? 

Het is, omdat we dit vast fout, vaste we deze fout, en we vaste deze fout. Dus vaste we drie fouten aantoonbaar. Nog steeds niet echt kijken gesorteerde, maar het objectief dichter bij gesorteerde omdat we vast een aantal van die fouten. 

Nu, wat moet ik nu doen? Ik soort van aan het einde van de lijst. Ik leek te hebben vastgesteld alle fouten, maar nee. Omdat in dit geval een aantal nummers zou hebben geborreld dichterbij andere nummers die zijn nog steeds niet in orde. Dus laten we het opnieuw doen, en ik zal doe het gewoon op zijn plaats deze tijd. Een en drie? Het is goed. Drie en twee? Natuurlijk niet, dus laten we dat veranderen. Dus twee, drie. Drie en vier? En laten we nu gewoon vooral pedant hier. Is het opgelost? U, mensen weet dat het opgelost. 

Ik zou het opnieuw te proberen. Dus Olivia stelt Ik probeer het opnieuw. Waarom? Omdat een computer niet heeft de luxe van onze menselijke ogen van slechts vluchtig back-- Oké, ik ben klaar. Hoe werkt de computer vast te stellen dat de lijst nu wordt gesorteerd? Mechanisch. 

Ik moet gaan door eens te meer, en alleen als ik niet maken / vinden geen fouten kan ik dan is de conclusie als de computer, yep, we zijn goed om te gaan. Dus een en twee, twee en drie, drie en vier. Nu kan ik definitief zeggen dat dit gesorteerd, omdat ik geen wijzigingen aangebracht. Nu zou het een bug te zijn en gewoon dwaas als ik, de computer, vroeg diezelfde vragen opnieuw verwacht verschillende antwoorden. Zou niet mogen gebeuren. 

En nu de lijst wordt gesorteerd. Helaas, speelduur van dit algoritme wordt ook N kwadraat. Waarom? Want je hebt n getallen, en in de ergste geval moet je n nummers bewegen n keer want je hebt om door te gaan terug om te controleren en eventueel op te lossen deze getallen. En we kunnen meer doen formele analyse, ook. 

Dus dit is allemaal te zeggen dat we hebben genomen drie benaderingen, een van hen onmiddellijk intuïtief van de vleermuis van Ben aan mijn voorgestelde invoeging sorteren naar deze ene waar je een soort uit het oog verliezen de bos door de bomen aanvankelijk. Maar dan als je een stap terug te nemen, voila, we hebben de sortering begrip vast. Dus dit is, durf te zeggen, een lager niveau misschien dan sommige van de andere algoritmes, maar laten we kijken of we niet kunnen visualiseren die door middel van deze. 

Dus dit is een aantal leuke software die iemand schreef het gebruik van kleurrijke bars dat is gaan naar de volgende te doen voor ons. Elk van deze staven een getal. Taller de bar, hoe groter het getal, hoe kleiner de bar, hoe kleiner het aantal. Dus idealiter willen we een mooie piramide waar het begint klein en krijgt grote, en dat zou betekenen dat deze bars worden gesorteerd. Dus ik ga om te gaan en te kiezen, Zo Ben's algoritme first-- selectie sorteren. 

En let op wat het doet. De manier waarop ze hebt ervoor gekozen om visualiseren dit algoritme is dat, net zoals ik was wandelen door mijn lijst, dit programma loopt door middel van haar lijst van nummers, markeren in roze elk getal dat het kijken naar. En wat er gaat nu gebeuren? 

Het kleinste getal dat I of Ben plotseling wordt verplaatst naar het begin van de lijst. En merkt dat ze deden verdrijven het getal dat er, en dat is prima. Ik heb niet in die mate van detail. Maar we moeten zetten dat nummer ergens, dus we net verhuisd naar de open plek die is gemaakt. Dus ik ga dit te versnellen up, omdat anders wordt al snel erg vervelend. Animatie snelheid- daar gaan we. Dus nu hetzelfde principe Ik was de toepassing, maar u kunnen beginnen met het algoritme te voelen, als je zal, of zie het een beetje duidelijker. En dit algoritme tot gevolg heeft het selecteren van de volgende kleinste element, dus je gaat om te beginnen met zie het opvoeren aan de linkerkant. En elke iteratie ik voorgesteld, het doet een beetje minder werk. Het hoeft niet de hele weg te gaan terug naar de linkerkant van de lijst, omdat het al kent hen zijn gesorteerd. Dus het soort voelt alsof het versnellen, hoewel elke stap waarbij dezelfde hoeveelheid tijd. Er is gewoon minder stappen overgebleven. En nu kunt u soort voelen de algoritme voor het opruimen van het einde ervan, en ook nu is het opgelost. 

Dus insertion sort is allemaal gedaan. Ik moet opnieuw willekeurig de array. En let op, ik kan het gewoon houden randomizing het, en we zullen een benadering van krijgen dezelfde aanpak, insertion sort. Laat me langzaam naar beneden om hier. Laten we beginnen dat voorbij. Stop. 

Laten we overslaan vier. Daar gaan we. Willekeurig ze array. En hier gaan-- we insertion sort. Spelen. Merk op dat het omgaan met elkaar element zij tegenkomt meteen, maar indien het behoort in de verkeerde plaats bericht al het werk dat moet gebeuren. We moeten blijven verschuiven meer en nog veel meer elementen om ruimte te maken voor degene die willen we in te voeren. 

Dus we focussen op de linkereinde van alleen de lijst. Merken we nog niet eens gekeken at-- we zijn niet gemarkeerd in roze iets naar rechts. We hebben alleen te maken met de problemen als we gaan, maar we zijn het creëren van een heleboel werken voor onszelf nog steeds. En dus als we versnellen dit op nu laten voltooien, het heeft een ander gevoel aan het inderdaad. Het is gewoon te focussen op de linker einde, maar het doen van een beetje meer werk als needed-- soort dingen glad te strijken over, de vaststelling van dingen, maar uiteindelijk omgaan met elk element een voor een tot we bij goed the--, we weten allemaal hoe dit gaat eindigen, dus het is een beetje underwhelming misschien. 

Maar de lijst in de end-- spoiler-- zal worden gesorteerd. Dus laten we eens kijken naar een laatste. We kunnen niet gewoon overslaan nu. We zijn er bijna. Twee om te gaan, een te gaan. En voila. Uitstekend. 

Dus nu laten we een laatste, opnieuw randomizing met bubble sort. En merk hier, vooral als ik langzaam naar naar beneden, dit betekent houden stoten door. Maar let op het maakt paarsgewijs comparisons-- soort van lokale oplossingen. Maar zodra we krijgen het einde van de lijst in roze, wat er gaat nog een keer gebeuren? Ja, het gaat om te hebben opnieuw, omdat het alleen vaste paarsgewijs fouten. En dat zou weer anderen hebben geopenbaard. En dus als je dit te versnellen, zul je zien dat, net zoals de naam impliceert, de kleinere elements-- of liever, de grotere elements-- beginnen te borrelen naar de top, als je wil. En de kleinere elementen begint te borrelen naar links. En inderdaad, dat is een soort van het visuele effect ook. En dus dit zal eindigen afwerking op soortgelijke wijze ook. 

We hoeven niet te blijven stilstaan op dit ene. Laat me dit nu te openen, ook. Er is een paar andere sorteeralgoritmen in de wereld, een paar van die Hier worden gevangen. En vooral voor leerlingen die niet noodzakelijkerwijs visuele of wiskundige, zoals we eerder deden, kunnen wij Dit doen ook audially als we associëren een geluid met deze. En gewoon voor de lol, hier is een aantal verschillende algoritmen, en een van hen in het bijzonder je bent gaan merken heet "merge sort." 

Het is eigenlijk een fundamenteel beter algoritme, zodanig dat soort fuseren, een van degene die je gaat zien, is niet orde van n kwadraat. Het is aan de orde van n keer in te loggen of n, die in feite kleiner en dus sneller dan de andere drie. En er is een ander koppel domme degenen die we zullen zien. 

Dus hier gaan we met een geluid. Dit is insertion sort, dus nogmaals het is alleen te maken met de elementen als ze komen. Dit is bubble sort, dus het is die ze als paren tegelijk. En nogmaals, de grootste elementen borrelen naar de top. 

Next up selectie sorteren. Dit is Ben's algoritme, waarbij nogmaals dat hij de selectie van iteratief de volgende kleinste element. En nogmaals, nu kun je echt horen dat het is versnellen, maar alleen voor zover want het doet steeds minder werken op elke iteratie. Dit is de snellere, samenvoegen sorteren, die sorteert clusters getallen elkaar en vervolgens te combineren. Dus look-- links de helft is al opgelost. 

Nu is het sorteren van de rechterhelft, en nu het gaat om ze te combineren tot één. Dit is iets genaamd "Gnome sort." En je kunt soort zien dat het is heen en weer, vaststelling van het werk een beetje hier en er voordat het overgaat tot nieuw werk. En dat is het. Er is een ander soort, dat is echt alleen voor academische doeleinden, genaamd "domme soort," waarbij rekening uw gegevens, sorteert het willekeurig, en controleert vervolgens of het wordt gesorteerd. En als het niet is, herordent is willekeurig, controleert of het wordt gesorteerd, en zo niet herhaalt. En in theorie, probabilistisch dit zal voltooien, maar na heel wat tijd. Het is niet de meest efficiënte algoritmen. Dus vragen op die bijzonder algoritmen of iets daar verwant zijn, ook? 

Nou, laten we nu plagen elkaar wat er allemaal deze lijnen zijn die ik heb al getekend en wat ik ervan uitgaande dat de computer kunnen doen onder de motorkap. Ik zou zeggen dat al deze nummers Ik blijf drawing-- ze moeten krijgen ergens in het geheugen opgeslagen. We zullen zich te ontdoen van deze man krijgt nu ook. 

Dus een stuk geheugen in een computer-- dus RAM DIMM is wat wij zochten naar gisteren, dual inline memory module-- ziet er als volgt uit. En elk van deze kleine zwarte chips is bepaald aantal bytes, typisch. En dan is de gouden pinnen zijn als de draden die aansluiten op de computer, en de groene silicium bord is gewoon wat houdt alles in elkaar. Dus wat betekent dit eigenlijk? Als ik soort van hetzelfde beeld te schetsen, Laten we veronderstellen voor de eenvoud dat deze DIMM, dual inline memory module, is één gigabyte RAM-geheugen, één gigabyte geheugen, dat is hoeveel bytes in totaal? Een gigabyte is hoeveel bytes? Meer dan dat. 1124 is kilo, 1000. Mega is miljoen. Giga is een miljard. 

Ben ik liegen? Kunnen we het etiket te lezen, zelfs? Dit is eigenlijk 128 gigabytes, dus het is nog veel meer. Maar wij zullen dit doen alsof is slechts één gigabyte. Dus dat betekent dat er een miljard bytes van het geheugen beschikbaar voor mij of 8 miljard bits, maar we gaan om te praten in termen van bytes nu, vooruit gaan. 

Dus wat dat betekent is dit een byte, is een byte, dit is een ander byte, en als we echt wilden specifieke we zouden moeten zijn trek je een miljard pleintjes. Maar wat betekent dat? Nou, laat me gewoon te zoomen in op deze foto. Als ik iets heb dat eruit ziet zoals dit nu, dat is vier bytes. 

En dus kon ik vier nummers hier te zetten. Een twee drie vier. Of ik kon vier letters of symbolen te zetten. "Hey!" kon daar gaan, omdat elk van de letters, we eerder hebben besproken, kan worden vertegenwoordigd met acht bits of ASCII of een byte. Dus met andere woorden, kunt u zet 8 miljard dingen binnen van deze stok van het geheugen. Nu, wat betekent het om dingen terug te zetten aan rug aan rug in het geheugen als deze? Dit is wat een programmeur zou een "array." noemen In een computerprogramma, denk je niet de onderliggende hardware, per se. Je denkt alleen maar aan jezelf als het hebben van toegang tot een miljard bytes totaal, en je kunt alles wat je wilt met haar. Maar voor het gemak het is over het algemeen nuttig om uw geheugen rechts houden naast elkaar als deze. Dus als ik inzoomen op dit-- omdat we zeker niet van plan een miljard beetje squares-- trekken Laten we veronderstellen dat deze raad vertegenwoordigt die stok van het geheugen nu. En ik zal gewoon te trekken zo veel als mijn marker eindigt hier geeft me. Dus nu hebben we een stok van het geheugen op het bord dat heeft een, twee, drie, vier, vijf, zes, een, twee, drie, vier, vijf, zes, seven-- dus 42 bytes geheugen op het totale scherm. Dank je. Ja, deed mijn rekenkunde rechts. Dus 42 bytes geheugen in. Dus wat betekent dit eigenlijk? Nou ja, een computerprogrammeur zou eigenlijk in het algemeen denk aan dit geheugen als adresseerbare. Met andere woorden, elk van deze locaties in het geheugen, in hardware, heeft een uniek adres. 

Het is niet zo complex als One Brattle Square, Cambridge, Mass., 02138. In plaats daarvan, het is gewoon een nummer. Dit is byte getal nul, is heeft weergegeven, twee, drie is, en dit is 41. Wacht even. Ik dacht dat ik zei 42 een moment geleden. Ik begon te tellen bij nul, dus dat is eigenlijk juist. Nu hoeven we niet om daadwerkelijk te tekenen als een raster, en als je het te tekenen als een raster Ik denk dat dingen eigenlijk een beetje misleidend. Wat een programmeur zou doen, in zijn of haar eigen geest, over het algemeen denken van deze geheugen is net als een tape, als een stuk afplakband dat gaat gewoon door en voor altijd of totdat u opraken van het geheugen. Dus een meer gebruikelijke manier om te tekenen en denk maar over het geheugen zou zijn dat dit byte nul, een, twee, drie, en toen puntje, puntje, puntje. En je hebt zo'n 42 bytes totaal, zelfs hoewel fysiek het misschien eigenlijk iets meer als dit. 

Dus als je nu denken van uw geheugen als deze, net als een tape, dit is wat een programmeur weer zou een reeks geheugencellen noemen. En als je wilt eigenlijk te slaan iets in een computergeheugen, je over het algemeen doen slaan dingen back-to-back to back-to-back. Dus we hebben gesproken over getallen. En toen ik wilde om problemen op te lossen zoals vier, één, drie, twee, hoewel ik was gewoon tekenen alleen de nummers vier, een, drie, twee op het bord, de computer zou echt deze opstelling in het geheugen. 

En wat zou naast het zijn twee in het geheugen van de computer? Nou, er is geen antwoord op. We weten niet echt. En zolang de computer heeft het niet nodig, het hoeft niet te schelen wat er is om de nummers doet de zorg over. En toen ik zei eerder dat een computer kan alleen maar kijken naar een adres in een tijd, dit is een soort van waarom. 

Niet in tegenstelling tot een record -speler en een leeskop alleen in staat om te kijken naar een bepaald groef in een fysieke old-school plaat tegelijkertijd, eveneens Kan een computer dankzij om de CPU en de Intel-instructieset, onder wie de instructie wordt gelezen uit het geheugen of op te slaan naar een memory-- computer kan alleen maar kijken op één locatie bij een tijd-- soms een combinatie daarvan, maar eigenlijk gewoon één plaats tegelijk. Dus toen we aan het doen waren deze verschillende algoritmes, Ik ben niet alleen schrijven in een vacuum-- vier, één, drie, twee. Die aantallen eigenlijk behoren ergens fysiek in het geheugen. Dus er zijn piepkleine transistors of een soort elektronica onder de hood opslaan van deze waarden. 

En in het totaal, hoeveel bits die betrokken zijn op dit moment, alleen maar om duidelijk te zijn? Dus dit is vier bytes, of nu is het 32 ​​bits in totaal. Er zijn dus eigenlijk 32 nullen en degenen die het samenstellen van deze vier dingen. Er is zelfs nog meer dan hier, maar weer hebben we niet schelen. 

Dus nu laten we vragen een ander vraag het gebruik van het geheugen, omdat aan het einde van de dag in variantie. Het maakt niet uit wat we zouden kunnen doen met de computer, aan het eind van de dag de hardware blijft de Hetzelfde onder de motorkap. Hoe zou ik slaan een woord hier? Nou ja, een woord in een computer, zoals "Hey!" zouden worden opgeslagen, net als dit. En als je wilde een langere Word kunt u eenvoudig overschrijven dat en iets te zeggen zoals "hallo" en winkel die hier. 

En dus ook hier deze contiguousness is juist een voordeel, want een computer kan gewoon van rechts naar links. Maar hier is een vraag. In het kader van dit woord, h-e-l-l-o, uitroepteken, hoe kan de computer laten weten waar de woord begint en waar het woord eindigt? In de context van getallen, hoe werkt de computer hoe lang de reeks getallen is of wanneer het begint? Nou, het blijkt out-- en we zullen niet te veel gaan in dit niveau van detail-- computers bewegen spullen rond in het geheugen letterlijk door middel van deze adressen. Dus in een computer, als je het schrijven van code om dingen op te slaan zoals woorden, wat je bent eigenlijk doet is aan het typen uitdrukkingen die onthouden waar in geheugen van de computer deze woorden zijn. Dus laat me een zeer, eenvoudig voorbeeld. 

Ik ga om te gaan en het openen van een eenvoudige tekst-programma, en ik ga om te creëren een bestand genaamd hello.c. De meeste van deze gegevens wordt zal niet in te gaan tot in detail, maar ik ga naar een schrijven programma in diezelfde taal, C. Dit is veel meer intimiderend, Ik zou zeggen, dan Scratch, maar het is zeer vergelijkbaar in de geest. In feite zijn deze curly braces-- je kunt soort denk aan wat ik net gedaan als dit. 

Laten we dit doen, eigenlijk. Als groene vlag geklikt, doe het volgende. Ik wil om uit te printen "hallo." Dus dit is nu pseudocode. Ik ben soort van het vervagen van de lijnen. In C, deze taal ik spreek over, deze lijn druk hello eigenlijk wordt "printf" met wat haakjes en een puntkomma. 

Maar het is precies hetzelfde idee. En deze zeer gebruiksvriendelijk "Wanneer groene vlag geklikt" wordt de veel meer mysterieuze "int main leegte." En dit heeft echt geen mapping, dus ik ga gewoon negeren dat. Maar de accolades zijn als de gebogen puzzelstukjes als deze. 

Zo kun je soort raden. Zelfs als je nog nooit hebt geprogrammeerd, wat heeft dit programma waarschijnlijk nog doen? Waarschijnlijk drukt hello met een uitroepteken. 

Dus laten we proberen dat. Ik ga om het op te slaan. Dit is, nogmaals, een zeer oude school omgeving. Ik kan het niet klikt, kan ik niet slepen. Ik moet commando's typen. Dus ik wil mijn programma uit te voeren, zodat Ik kan dit doen, zoals hello.c. Dat is het bestand dat ik liep. Maar wacht, ik mis een stap. Wat deden we zeggen is een noodzakelijke stap voor een taal als C? Ik heb net geschreven bron code, maar wat heb ik nodig? Ja, ik heb een compiler. Dus op mijn Mac hier, ik heb een programma genaamd GCC, GNU C-compiler, waardoor ik dit-- beurt doen mijn source code in, zullen we het noemen, machine code. 

En ik kan zien dat, opnieuw, als hieronder, deze zijn de nullen en enen ik gewoon gemaakt op basis van mijn broncode, alle nullen en enen. En als ik wil lopen mijn program-- het gebeurt a.out te worden uitgenodigd voor historische reasons-- "hallo." Ik kan het opnieuw uit te voeren. Hallo hallo hallo. En het lijkt te werken. 

Maar dat betekent dat ergens in mijn geheugen van de computer zijn de woorden h-e-l-l-o, uitroepteken. En het blijkt, net als een terzijde, wat een computer zouden in het algemeen doen zodat het weet wanneer dingen beginnen en end-- het is gaat naar een speciaal symbool hier zetten. En de conventie is om het te zetten cijfer nul aan het einde van een woord zodat u weet waar het daadwerkelijk eindigt, zodat u houden niet uit te printen meer en meer personages dan je eigenlijk van plan bent. 

Maar de afhaalmaaltijd hier, zelfs al is dit vrij mysterieus, is dat het uiteindelijk relatief eenvoudig. Je kreeg een soort van band, een lege ruimte waar je letters kunt schrijven. Je moet gewoon een hebben speciaal symbool, zoals willekeurig het getal nul, tot eind gezet je woorden zodat de computer weet, oh, ik moet stoppen met afdrukken na Ik zie het uitroepteken. Omdat het volgende wat er is een ASCII-waarde van nul, of het null karakter iemand zou noemen. Maar er is een soort van een probleem hier, en laten we keren terug om nummers voor een moment. Stel dat ik doe, in feite, een matrix van getallen, en veronderstellen dat de programma dat ik aan het schrijven ben is als een cijfer boek voor een leraar en leraren klaslokaal. En dit programma maakt hem of haar te typen in scores van hun leerlingen op quizzen. En stel dat de student krijgt 100 op hun eerste quiz, misschien als een 80 op de volgende, dan 75, dan is een 90 op de vierde quiz. 

Dus op dit punt in het verhaal, de array van grootte vier. Er is absoluut meer geheugen in de computer, maar de matrix, bij wijze van spreken, is de omvang van vier. Veronderstel nu dat de leraar wil een vijfde quiz aan de klasse toe te wijzen. Nou, een van de dingen die hij of zij zal moeten doen is nu een extra waarde op te slaan in. Maar als de array de leraar gemaakt in dit programma is van de grootte voor, een van de problemen met een array is dat je kunt niet zomaar blijven toevoegen aan het geheugen. Want wat als een ander deel van de programma heeft het woord "hey" daar? 

Met andere woorden, kan mijn geheugen gebruikt voor alles in een programma. En als op voorhand Ik typte in, hey, Ik wil invoeren vier quiz scores, ze misschien hier en hier te gaan. En als je opeens van gedachten verandert later en zeggen dat ik wil een vijfde quiz score, kun je niet zomaar zet het waar u maar wilt, want wat als dit geheugen wordt gebruikt iets else-- een ander programma of een ander kenmerk van het programma dat je draait? Dus je moet denken bij voorbaat hoe u wilt uw gegevens op te slaan, want nu heb geschilderd jezelf in een digitale hoek. 

Dus een leraar zou in plaats daarvan zeggen wanneer het schrijven van een programma opslaan diens rangen, weet je wat? Ik ga vragen, bij het schrijven van mijn programma, dat wil nul, één, twee, drie, vier, vijf, zes, acht graden totaal. Dus één, twee, drie, vier, vijf, zes, zeven, acht. De leerkracht kan gewoon over-toewijzen geheugen bij het schrijven van zijn of haar programma en zeggen: weet je wat? Ik ga nooit meer toe te wijzen dan acht quizzen in een semester. Dat is gewoon gek. Ik zal nooit meer toe te wijzen dat. Zodat deze manier hij of zij de flexibiliteit opslaan student scores, als 75, 90, en misschien een extra, waar de student kreeg extra krediet, 105. 

Maar als de leraar nooit gebruikt deze drie ruimten, er is een intuïtieve afhaalmaaltijd hier. Hij of zij is gewoon verspilling van ruimte. Dus met andere woorden, er is dit gemeenschappelijke afruil in de programmering waar u ook kunt toewijzen precies zoveel geheugen als je wilt, de positieve kant daarvan is dat je super bent efficient-- je bent het niet verkwistend bij all-- maar de keerzijde van die is wat als je van gedachten verandert wanneer met behulp van het programma dat u wilt opslaan meer data dan je oorspronkelijk de bedoeling was. 

Dus misschien de oplossing is, dan, schrijf uw programma zodanig die ze gebruiken meer geheugen dan ze eigenlijk nodig hebben. Op deze manier zul je niet te lopen in dit probleem, maar je wordt verspilling. En hoe meer geheugen van uw programma gebruikt, zoals we gisteren besproken, minder geheugen dat beschikbaar is voor andere programma's, hoe eerder uw computer kunnen vertragen naar beneden als gevolg van virtueel geheugen. En dus is de ideale oplossing zou wat zijn? 

Under-verdeling lijkt slecht. Over-verdeling lijkt slecht. Dus wat zou een betere oplossing zijn? Herschikking. Be dynamischer. Doe jezelf niet dwingen om te kiezen voor een priori, in het begin, wat je wilt. En zeker niet over-toewijzen, opdat u verspilling. 

En zo om dat doel te bereiken, we moeten deze datastructuur te gooien, zo te zeggen, weg. En wat een programmeur Doorgaans gebruikt is zoiets als geen -array maar een gekoppelde lijst. Met andere woorden, zal hij of zij beginnen te denken van hun geheugen als een soort van een vorm die zij kan trekken op de volgende manier. Als ik wil een nummer op te slaan in een program-- dus het is september, Ik heb mijn leerlingen een quiz gegeven; ik wil eerst quiz van de studenten op te slaan, en ze kregen een 100 op het-- I ga mijn computer te vragen, door middel van het programma dat ik heb geschreven, één stuk geheugen. En ik ga naar de winkel nummer 100 in, en dat is het. 

Dan een paar weken later als ik mijn tweede quiz, en het is tijd om te typen in dat 90%, ga ik om de computer te vragen, hey, computer, kan ik nog een brok van geheugen? Het gaat om me geven deze leeg stuk van het geheugen. Ik ga in het nummer 90 te zetten, maar in mijn programma een of andere manier of other-- en we zullen niet zorgen te maken over de syntaxis voor dit-- ik nodig een of andere manier keten deze dingen samen. En ik zal ze samen met ketting wat lijkt op een pijl hier. 

De derde quiz die omhoog komt, Ik ga zeggen, hey, computer, geef me nog een stuk van het geheugen. En ik ga neer te zetten wat het ook was, zoals 75, en ik moet deze keten nu samen een of andere manier. Vierde quiz komt langs, en misschien Dat is tegen het einde van het semester. En op dat moment mijn programma misschien met behulp van het geheugen all over the place, heel fysiek. En dus gewoon voor de lol, ik ben gaat deze voort te trekken quiz-- ik vergeten wat het was; ik denk dat een 80 of something-- hierheen. 

Maar dat is prima, want pictorially Ik ga deze lijn te trekken. Met andere woorden, in werkelijkheid, in de hardware van uw computer, de eerste score zou uiteindelijk hier, want het is meteen aan het begin van het semester. De volgende zou kunnen eindigen hier omdat er een beetje van de tijd is verstreken en het programma blijft draaien. De volgende score, die was een 75, misschien wel meer dan hier. En de laatste score zou kunnen zijn een 80, dat is meer dan hier. 

Dus in werkelijkheid, fysiek, dit zou kunnen wat geheugen van uw computer eruit ziet. Maar dit is niet een nuttig mentaal paradigma voor computerprogrammeur. Waarom zou u de zorg waar de heck uw gegevens belanden? Je wil gewoon gegevens op te slaan. 

Dit is net zoiets als onze discussie eerder van het tekenen van de kubus. Waarom heb je schelen wat de hoek van de kubus en hoe je moet draaien om het te tekenen? Je wil gewoon een kubus. Op dezelfde manier hier, je ik wil gewoon naar de rang boek. Je wilt alleen maar te denken aan dit als een lijst van nummers. Who cares hoe het geïmplementeerd in hardware? 

Dus de abstractie nu is deze foto hier. Dit is een gekoppelde lijst, zoals een programmeur zou noemen, voor zover u een lijst uiteraard getallen. Maar het is pictorially gekoppeld door middel van deze pijlen, en al deze pijlen zijn-- eronder de kap, als je nieuwsgierig bent, herinneren dat onze fysieke hardware heeft adressen nul, één, twee, drie, vier. Al deze pijlen zijn is als een kaart of richtingen, waar als 90 is-- nu Ik kreeg te tellen. 

Nul, één, twee, drie, vier, vijf, zes, zeven. Het lijkt erop dat de 90 is op geheugenadres nummer zeven. Al deze pijlen zijn is als een klein stukje papier dat is het geven van een routebeschrijving naar het programma dat zegt dat deze kaart volgen om plaats zeven te krijgen. En daar zult u de vondst student tweede quiz score. Intussen is de 75-- als ik doorga dit, Deze zeven, acht, negen, 10, 11, 12, 13, 14, 15. 

Deze andere pijl gewoon vertegenwoordigt een kaart om het geheugen locatie 15. Maar nogmaals, de programmeur het algemeen doet niet om dit niveau van detail. En in de meeste elke programmering taal van vandaag, de programmeur zal niet eens weten waar in het geheugen deze nummers eigenlijk zijn. Het enige wat hij of zij moet de zorg over is dat ze ergens elkaar verbonden in een datastructuur als deze. 

Maar het blijkt niet te technisch te worden. Maar gewoon omdat we kunnen misschien veroorloven om deze discussie hier, veronderstellen dat we terugkomen deze kwestie hier van een array. Laten we eens kijken of we hier spijt van gaan. Dit is 100, 90, 75 en 80. 

Laat me even deze claim te maken. Dit is een matrix, en opnieuw, de opvallende kenmerk van een array is dat al uw gegevens terug naar rug aan rug in memory-- letterlijk één byte of misschien vier bytes, sommige vast aantal bytes afstand. In een gelinkte lijst, die we kunnen trekken als dit, onder de motorkap, die weet waar dat spul is? Het hoeft niet eens te stromen als dit. Sommige gegevens kunnen zijn terug naar links daar. Je weet niet eens. 

En dus met een array, heb je een feature bekend als random access. En wat random access betekent is dat de computer direct kan springen op elke locatie in de matrix. Waarom? Omdat de computer weet dat de eerste locatie nul, één, twee en drie. 

En dus als je wilt gaan uit dit element naar het volgende element, je letterlijk, in de geest computer, voeg een. Als u wilt gaan naar het derde element, voeg een-- volgende element, net Voeg een toe. Echter, in deze versie van het verhaal, veronderstel de computer is momenteel op zoek op of omgaan met het nummer 100. Hoe krijg je naar het volgende rang in de rang boek? 

Je moet nemen zeven stappen, die willekeurig. naar de volgende te krijgen, moet je neem een ​​andere acht stappen om 15 te komen. Met andere woorden, het is niet een constante spleet tussen de nummers, en zo het gewoon neemt de computer meer tijd is het punt. De computer heeft om te zoeken door het geheugen in orde om te vinden wat je zoekt. 

Dus terwijl een array heeft de neiging om een ​​te zijn snelle data structure-- omdat je kan letterlijk gewoon doen eenvoudige rekenkundige en komen waar je wilt door het toevoegen van een, voor instance-- een gekoppelde lijst, U offeren die functie. Je kunt niet zomaar gaan van de eerste naar de tweede naar de derde naar de vierde. Je moet de kaart te volgen. Je moet meer stappen te ondernemen deze waarden, om welke lijkt het toevoegen van een vergoeding. Dus we betalen een prijs, maar wat was de functie die hier Dan zocht? Wat doet een gekoppelde lijst blijkbaar kunnen we doen, die de oorsprong van dit verhaal? 

Precies. Een dynamische maat aan. We kunnen aan deze lijst toevoegen. We kunnen zelfs krimpen de lijst, dus dat we alleen gebruik maakt van zoveel geheugen zoals we eigenlijk willen en zo we zijn nooit over-verdeling. 

Nu alleen maar om echt spitsvondigheid kieskeurig, er is een verborgen kosten. Dus je moet niet alleen laat me overtuigen je dat dit een dwingende afweging. Er is een andere verborgen kosten hier. Het voordeel, om duidelijk te zijn, is dat we dynamiek. Als ik wil een ander element, kan ik alleen maar tekenen en zet een aantal in. En dan kan ik het koppelen met een foto hier, overwegende dat meer dan hier, nogmaals, als ik heb geschilderd mezelf in een hoekje, als er iets anders wordt al gebruikt het geheugen hier, ben ik pech. Ik heb mezelf geschilderd in de hoek. 

Maar wat is de verborgen kosten in dit plaatje? Het is niet alleen de hoeveelheid tijd die het duurt te gaan van hier naar hier, die zeven stappen, dan acht stappen, die meer dan één. Wat is een ander verborgen kosten? Niet alleen de tijd. Aanvullende informatie is moet deze beeldkwaliteit. 

Ja, die kaart, die kleine stukjes papier, want ik houd het beschrijven van hen. Deze arrows-- dat zijn niet gratis. Een computer-- je weet wat een computer heeft. Het heeft nullen en enen. Wilt u een pijl of een vertegenwoordigen kaart of een nummer, u wat geheugen nodig. Dus de andere prijs die u betalen voor een gelinkte lijst, een gemeenschappelijke computer science resource, is ook ruimte. 

En inderdaad zo, zo vaak, onder de afwegingen in het ontwerpen van software engineering systemen is de tijd en space-- twee van ingrediënten, twee van uw meest kostbare ingrediënten. Dit kost me meer tijd want ik heb deze kaart te volgen, maar het is ook kost me meer ruimte want ik heb deze kaart in de buurt te houden. Dus de hoop, zoals we hebben soort besproken meer dan gisteren en vandaag, is dat de voordelen zal opwegen tegen de kosten. 

Maar er is geen voor de hand liggende oplossing. Misschien is het better-- a la quick and dirty, als Kareem voorgesteld earlier-- om het geheugen te gooien naar het probleem. Gewoon kopen meer geheugen, denken minder hard over het oplossen van het probleem, en lossen het op een eenvoudiger manier. En inderdaad eerder, toen spraken we over compromissen, Het was niet ruimte de computer en de tijd. Het was ontwikkelaar tijd, die is een andere bron. 

Dus nogmaals, het is deze evenwichtsoefening proberen om te beslissen welke van die dingen bent u bereid te besteden? Wat is de minst dure? Die geeft betere resultaten? Ja? 

Inderdaad. In dit geval, als je die getallen in de maps-- deze worden genoemd in vele talen "Pointers" of "adressen" - het is het dubbele van de ruimte. Dat hoeft niet zo slecht als dubbel zo zijn op dit moment zijn we gewoon het opslaan van nummers. Stel dat we het opslaan patiëntendossiers in een hospital-- dus namen Pierson's, telefoonnummers, sofi-nummers, arts geschiedenis. Deze doos kan veel, veel groter, waarbij een klein beetje wijzer, het adres van de volgende element-- het is niet een big deal. Het is zo'n pony kost het maakt niet uit. Maar in dit geval, ja, het is een verdubbeling. Goede vraag. 

Laten we praten over een tijd beetje meer concreet. Wat is de looptijd van het zoeken in dit overzicht? Stel dat ik wilde om te zoeken door middel van alle kwaliteiten van de studenten, en er is n kwaliteiten in deze datastructuur. Ook hier kunnen we lenen de woordenschat van eerder. Dit is een lineaire datastructuur. 

Big O van n is wat er nodig is om te krijgen aan het einde van deze gegevensstructuur, whereas-- en we hebben niet gezien Dit before-- een matrix geeft je wat heet constante tijd, wat betekent dat een stap of twee stappen of 10 steps-- maakt niet uit. Het is een vast aantal. Het heeft niets te maken met de grootte van de matrix. En de reden daarvoor, opnieuw, is willekeurige toegang. De computer kan gewoon meteen springen naar een andere locatie, want ze zijn allemaal hetzelfde afstand van alles. Er is geen denken bij betrokken. Okee. Dus als ik kan, laat me proberen te verf laatste twee foto's. Een veel voorkomende een bekend als een hash tabel. Dus om deze discussie te motiveren, laat me denken over hoe dit te doen. 

Dus hoe zit dit? Stel dat het probleem we willen nu op te lossen implementeert in een dictionary-- dus een hele hoop van het Engels woorden of wat dan ook. En het doel is om te kunnen beantwoorden vragen van het formulier is dat een woord? Dus u wilt implementeren een spellingscontrole, net als een fysieke woordenboek dat je kunt dingen opzoeken in. Stel dat ik dit doen met een array. Ik zou dit te doen. 

En stel dat de woorden zijn appel en banaan en meloen. En ik kan niet denken van vruchten die beginnen met d, dus we zijn gewoon gaat drie vruchten hebben. Dus dit is een array, en we zijn opslaan van al deze woorden in dit woordenboek als een matrix. De vraag is dus hoe anders zou je deze informatie op te slaan? 

Nou, ik ben een beetje vals spelen hier, want elk van deze letters in het woord is echt een individuele byte. Dus als ik echt wilde zijn nit-kieskeurig, zou ik echt te verdelen deze op in veel kleinere delen van het geheugen, en we konden precies dat te doen. Maar we gaan tegenkomen hetzelfde probleem als voorheen. Wat als, zoals Merriam Webster of Oxford doet elke jaar-- ze woorden toevoegen de dictionary-- doen we niet per se willen onszelf te schilderen in een hoek met een serie? 

Dus in plaats daarvan, misschien een slimmere aanpak is om appel in haar eigen knoop of doos, zoals wij zouden zeggen, banaan, en dan is hier hebben we cantaloupe. En we touwtje deze dingen samen. Dus dit is de matrix en Dit is het gelinkte lijst. Als je niet helemaal kunt zien, het is gewoon zegt "array", en dit zegt "lijst." 

Dus we hebben dezelfde exact kwesties als voorheen, waardoor we nu dynamiek in onze gelinkte lijst. Maar we hebben een vrij traag woordenboek. Stel dat ik wil een woord opzoeken. Het zou me grote O n stappen, omdat het woord misschien zijn helemaal aan het eind de lijst, zoals meloen. En het blijkt dat in de programmering, sorteren van de heilige graal van data structuren, is iets dat geeft je een constante tijd als een array maar dat geeft je nog steeds dynamiek. 

Zo kunnen we het beste van beide werelden? En inderdaad, er is iets genaamd de hash table die u toelaat om precies te doen dat zij bij benadering. Een hash tabel is een liefhebber gegevensstructuur die we maar kunt bedenken als het combinatie van een array-- en ik ga om het te tekenen zoals dit-- en gelinkte lijsten dat ik zal trekken als dit hier. 

En de manier waarop deze zaak werkt als volgt. Als dit now-- hash table-- is mijn derde datastructuur, en ik wil op te slaan woorden in deze, dat doe ik niet willen gewoon allemaal van de winkel woorden rug aan rug aan rug aan rug. Ik wil een hefboomeffect wat informatie over de woorden die zal laten me get it waar het sneller. 

Dus gezien de woorden apple en banaan en meloen, Ik koos bewust voor die woorden. Waarom? Wat is een soort van fundamenteel anders over de drie? Wat is de voor de hand liggende? Ze beginnen met verschillende letters. 

Dus weet je wat? In plaats van al mijn woorden in dezelfde emmer, om zo te zeggen, net als in een grote lijst, waarom niet Ik op zijn minst proberen een optimalisatie en mijn lijsten 26/01 zo lang te maken. Een meeslepend optimalisatie misschien waarom niet Ik-- bij het plaatsen van een woord in deze gegevensstructuur, in het geheugen van de computer, waarom weet ik niet al de 'a' woorden hier, alle 'b' woorden hier en alle 'c' woorden hier? Zo eindigt deze putting een appel hier, hier banaan, meloen hier, enzovoorts. 

En als ik een extra woord like-- wat is een ander? Appel, banaan, peer. Iedereen denken van een vrucht die begint met een a, b of c? Blueberry-- perfect. Dat gaat uiteindelijk hier. En dus lijken we een hebben marginaal betere oplossing, want nu als ik wil om te zoeken naar apple, I first-- ik niet alleen duik in mijn datastructuur. Ik weet niet duik in het geheugen van mijn computer. Ik kijk eerst naar de eerste letter. 

En dit is wat een computer wetenschapper zou zeggen. Je hash in uw datastructuur. Je neemt je input, die in dit geval is een woord als appel. Je analyseert het, kijkend naar de eerste letter in casu waardoor hash is. Hashing is een algemene term waarbij je iets als input nemen en produceer je wat output. En de output van die geval is de locatie u wilt zoeken, de eerste locatie, de tweede plaats, de derde plaats. Zodat de ingang appel, de eerste uitgang. De ingang is banaan, de output moet seconde. De ingang is cantaloupe, de productie moet derde zijn. De ingang is bosbessen, de output moet weer tweede. En dat is wat helpt u mee shortcuts door je geheugen om woorden te krijgen of gegevens efficiënter te maken. 

Nu snijdt deze naar beneden onze tijd mogelijk zelfs met een op de 26, want als je ervan uitgaat dat je zo veel "a" woorden als "z" woorden als "q" woorden, die is niet echt realistic-- je gaat scheef over hebben bepaalde letters van het alphabet-- maar dit zou een incrementele aanpak die toelaat je veel sneller om woorden te krijgen. En in werkelijkheid een verfijnd programma de Googles van de wereld, de Facebooks van de wereld-- ze zouden een hash-tabel gebruiken voor veel verschillende doeleinden. Maar zij zouden niet zo naïef zijn gewoon kijken naar de eerste letter in appel of banaan of peer of meloen, want zoals u deze kunt zien lijsten kon nog steeds lang. 

En dus dit kan nog steeds soort zijn van linear-- dus een soort van trage, zoals bij de grote O n dat we eerder besproken. Dus wat een echte goede hash tafel zal doen-- het zal een veel grotere array. En het zal een veel gebruikt verfijnde hashing-functie, zodat het niet alleen kijken naar de "a." Misschien kijkt naar "a-p-p-l-e" en een of andere manier zet die vijf letters in de plaats waar appel moeten worden opgeslagen. We zijn gewoon naïef met de letter 'a' alleen, want het is leuk en eenvoudig. 

Maar een hash-tabel, in het einde, kunt u denkt of als een combinatie van een matrix, die elk heeft een gekoppelde lijst die idealiter moet zo kort mogelijk zijn. En dit is niet voor de hand. In feite, veel van de fijnafstemming dat gaat onder de kap als de uitvoering van dit soort geavanceerde data structuren is wat de juiste lengte van de array? Wat is de juiste hash-functie? Hoe doe je opslaan dingen in het geheugen? 

Maar beseffen hoe snel dit soort discussie escaleerde, ofwel zo ver dat het is een soort van boven het hoofd op dit punt, die is prima. Maar we begonnen, rappel, met werkelijk iets low-level en elektronisch. En dus dit is ook dit thema van de abstractie, waar eens je begint te nemen voor verleend, OK, ik heb het-- heb er fysiek geheugen, OK, kreeg het, elke fysieke locatie heeft een adres, OK, ik heb het, kan ik vertegenwoordig deze adressen als arrows-- kun je heel snel aan de slag te hebben verfijndere gesprekken die in het einde lijkt ons te worden zodat om problemen zoals het zoeken op te lossen en sorteren efficiënter te maken. En wees gerust, too-- omdat ik denk dat dit is de diepste we gegaan in een aantal Deze CS onderwerpen proper-- we hebben in één dag en een half in dit punt wat je zou normaal meer dan doen de loop van acht weken in een semester. 

Heeft u vragen over deze? Nee? Okee. Nou, waarom niet we daar te pauzeren, starten lunch een paar minuten te vroeg, hervatten in slechts ongeveer een uur? En ik zal blijven hangen een beetje met vragen. Dan ga ik moeten gaan neem een ​​paar oproepen als dat is OK. Ik zet wat muziek in de tussentijd, maar de lunch moet rond de hoek.