David Malan: Alle reg. Ons is terug. So in hierdie segment oor programmering wat Ek het gedink ons ​​wil doen, is 'n mengsel van dinge. Een, doen 'n bietjie van iets hands-on, hoewel die gebruik van 'n meer speelse programmering environment-- een wat demonstratiewe van presies die soort van idees Ons het gepraat oor, maar 'n bietjie meer formeel. Twee, kyk na 'n paar van die meer tegniese maniere wat 'n programmeerder eintlik sou los probleme soos die soek probleem dat ons kyk na voor en ook 'n meer fundamenteel interessante probleem van sortering. 

Ons het net aanvaar van die kry gaan dat telefoon boek gesorteer is maar dit alleen is eintlik soort van 'n hard probleem met baie verskillende maniere om dit op te los. So sal ons dit gebruik as 'n klas van probleme verteenwoordiger van die dinge wat kan opgelos word in die algemeen. En dan sal ons praat oor in detail wat geroep data structures-- liefhebber maniere soos geskakelde lyste en hash tabelle en bome wat 'n programmeerder sou eintlik gebruik en oor die algemeen gebruik op 'n witbord te verf 'n beeld van wat hy of sy vooruitsig vir die implementering 'n stuk van sagteware. 

So laat ons doen die praktiese gedeelte eerste. Dus net jou hande vuil met 'n omgewing genoem scratch.mit.edu. Dit is 'n instrument wat ons gebruik in ons voorgraadse klas. Selfs al is dit ontwerp vir ouderdomme 12 en ouer, Ons gebruik dit vir die up deel van daardie nogal 'n bietjie want dit is 'n lekker, pret grafiese manier van leer 'n ietsie oor programmering. So kop tot daardie URL, waar jy moet 'n bladsy te sien hou hiervan en gaan voort en klik Sluit Scratch op regs bo en kies 'n gebruikersnaam en 'n wagwoord en uiteindelik kry jouself 'n account-- scratch.mit.edu. Ek het gedink ek wil dit gebruik as 'n geleentheid eerste om dit te wys. 'N Vraag vorendag gekom tydens die pouse oor wat-kode lyk eintlik soos. En ons was in gesprek gedurende die pouse oor C, in particular-- veral 'n laer vlak in 'n ouer taal. En ek het net 'n vinnige Google soek om C-kode te vind vir binêre soek, die algoritme wat ons gebruik om vroeër soek wat telefoon boek. Hierdie spesifieke voorbeeld, natuurlik, nie 'n telefoon boek soek. Dit soek net 'n hele klomp van die getalle in die rekenaar se geheue. Maar as jy wil net 'n visuele gevoel van wat 'n werklike ontwikkeling taal lyk, lyk dit 'n bietjie iets. Dit is dus sowat 20-plus, 30 of so reëls van die kode, maar die gesprek het ons is met meer as break was oor hoe dit werklik kry Morphed in nulle en ene en as jy kan nie net terug te keer dat verwerk en gaan van nulle en ene terug na-kode. 

Ongelukkig is die proses so transformerende dat dit 'n baie makliker gesê as gedaan. Ek het voortgegaan en eintlik draai die program, binêre soek, in nulle en ene by wyse van 'n program genaamd samesteller dat ek gebeur hier reg op my Mac. En as jy kyk na die skerm hier, met die fokus spesifiek op hierdie middel ses kolomme net, jy net nulle en ene sien. En dit is die nulle en ene wat komponeer presies wat soek program. 

En so elke stuk van vyf stukkies, elke byte van nulle en ene hier, verteenwoordig 'n opdrag tipies binnekant van 'n rekenaar. En in werklikheid, as jy het gehoor die bemarking slagspreuk "Intel binne" - wat, natuurlik, beteken net jy het 'n Intel CPU of brein in die rekenaar. En wat dit beteken om 'n CPU is dat jy 'n stel instruksies, By wyse van spreke. 

Elke SVE in die wêreld, baie van hulle het deur Intel deesdae, verstaan ​​'n eindige aantal instruksies. En diegene instruksies is so laag vlak as voeg hierdie twee getalle bymekaar, vermenigvuldig die twee getalle bymekaar, beweeg hierdie stukkie data van hier af hier in die geheue, behalwe hierdie inligting van hier tot hier in die geheue, en so forth-- so baie, baie lae-vlak, amper elektroniese besonderhede. Maar met dié wiskundige bedrywighede gekoppel met wat ons vroeër bespreek, die voorstelling van data as nulle en ene, kan julle op te bou alles dat 'n rekenaar vandag kan doen, of dis tekstuele, grafiese, musikale, of andersins. 

So dit is baie maklik om te kry verlore in die onkruid van vinnig. En daar is 'n baie sintaktiese uitdagings waardeur as jy die eenvoudigste maak, domste van typos geeneen van die program sal hoegenaamd werk. En so in plaas van die gebruik van 'n taal soos C vanoggend, Ek het gedink dit sou wees meer pret om werklik te doen iets meer visuele, wat terwyl ontwerp vir kinders is eintlik 'n volmaakte openbaring van 'n werklike ontwikkeling language-- net gebeur met gebruik prente in plaas van teks om daardie idees verteenwoordig. 

So as jy inderdaad 'n rekening op scratch.mit.edu, Klik op die knoppie Skep op top links van die webwerf. En jy moet 'n omgewing soos te sien die een wat ek nou gaan kyk op my skerm hier. En ons sal net 'n bietjie te spandeer bietjie tyd hier speel. Kom ons kyk of ons kan nie al 'n paar op te los probleme saam op die volgende manier. 

So, wat jy sal sien in hierdie environment-- en eintlik net laat my breek. Is daar iemand hier? Nie hier nie? OK. So laat my daarop wys 'n paar kenmerke van hierdie omgewing. 

So op die links bo aan die skerm, ons het stadium Scratch se, so te sê. Scratch is nie net die naam van hierdie programmeertaal; dit is ook die naam van die kat wat jy sien by verstek daar in oranje. Hy is op 'n stadium, sodat baie soos ek beskryf die skilpad vroeër as in 'n vierkantige wit bord omgewing. wêreld hierdie kat se geheel en al beperk om daardie reghoek op die top van daar. 

Intussen het op die regte kant hier, dis net 'n skrifte gebied, 'n skoon lei as jy wil. Dit is hier waar ons gaan skryf ons programme in net 'n oomblik. En die boustene wat ons sal gebruik om te skryf hierdie program-- die legkaart stukke, as jy will-- is diegene reg hier in die middel, en hulle gekategoriseer deur funksionaliteit. So, byvoorbeeld, ek gaan om voort te gaan en demonstreer ten minste een van hierdie. Ek gaan om voort te gaan en klik die kategorie beheer op die top. 

So dit is die kategorieë op die top. Ek gaan op die kategorie beheer. Inteendeel, ek gaan die gebeure op kategorie, die heel eerste een op die top. En as jy wil om te volg saam selfs as ons dit doen, is jy heel welkom om. Ek gaan kliek en sleep dit eerste een, "wanneer groen vlag gebruik." En dan gaan ek dit net drop rofweg aan die bokant van my leeg leie. 

En wat is lekker oor Scratch is dat hierdie legkaart stuk, wanneer gevries met ander legkaart stukke, gaan letterlik doen wat die stukke van die legkaart te sê om te doen. So, byvoorbeeld, Scratch is reg nou in die middel van sy wêreld. Ek gaan om voort te gaan en kies nou, kom ons sê, die kategorie Beweging, As jy wil die doen same-- Motion kategorie. En nou sien ek het 'n hele n klomp van die legkaart stukke hier dat, weer, soort te doen wat hulle sê. En ek gaan om voort te gaan en sleep en drop die skuif blok reg hier. 

En agterkom dat sodra jy naby aan die onderkant van die "groen vlag gekliek "knoppie, kennisgewing hoe 'n wit streep verskyn, asof dit byna magnetiese, dit wil daarheen gaan. Net laat gaan, en dit sal snap saam en die vorms sal pas. En nou kan jy dalk amper raai waar ons gaan met hierdie. 

As jy kyk na die Scratch stadium hier en kyk na die top van dit, jy sal 'n rooi lig sien, 'n stopteken, en 'n groen vlag. En ek gaan om voort te gaan en kyk my screen-- vir net 'n oomblik, as jy kon. Ek gaan die klik groen vlag op die oomblik, en Hy het wat lyk na 10 stappe wees of 10 pixels, 10 punte, wat op die skerm. 

En so nie dat opwindende, maar laat my stel sonder dit selfs onderrig, net gebruik van die eie jou eie intuition-- laat my voorstel dat jy uitvind hoe om maak Scratch loop reg van die verhoog af. Het hom plek maak vir die regte kant van die skerm, al die pad na regs. Kom ek gee jou 'n oomblik of so stoei met dit. Jy wil dalk 'n blik te neem by ander kategorieë van blokke. Alles reg. So net om saam te vat, wanneer ons die groen vlag gekliek hier en beweeg 10 stappe is die net onderrig, elke keer as ek Klik op die groen vlag, wat gebeur? Wel, dit is die bestuur van my program. So kan ek dit doen Miskien 10 keer met die hand, maar dit voel 'n bietjie bietjie hackish, om so te praat, waardeur ek is nie regtig die oplossing van die probleem. Ek is net weer probeer en weer en weer en weer totdat ek soort van ongeluk bereik die richtlijn dat ek uiteengesit om vroeër te bereik. 

Maar ons weet van ons pseudokode vroeër gesê daar is hierdie idee in programmering van herhaling, om iets te doen oor en oor. En so het ek gesien dat 'n klomp van julle bereik vir wat legkaart stuk? Herhaal totdat. So kan ons iets doen soos herhaal totdat. En wat het jy te herhaal totdat presies? 

OK. Dat ek kan gaan met een wat ietwat eenvoudiger vir net 'n oomblik. Laat my gaan voort en doen dit. Let daarop dat, as jy kan hê onder beheer ontdek, Daar is hierdie herhaling blok, wat lyk nie soos dit is dat 'n groot. Daar is nie veel ruimte in tussen die twee geel strepe. Maar as 'n paar van wat jy mag hê opgemerk, as jy sleep, sien hoe dit groei tot die vorm in te vul. 

En jy kan selfs meer gedrang. Dit sal net aanhou groei as jy sleep en Beweeg oor dit. En ek weet nie wat is beste hier, so laat my ten minste herhaal vyf keer, vir Byvoorbeeld, en gaan dan terug na die verhoog en kliek op die groen vlag. En nou sien dis nogal daar nie. 

Nou sommige van julle voorgestel, soos Victoria het net herhaal 10 keer. En wat oor die algemeen nie kry hom al die pad, Maar sou daar nie 'n meer robuuste wees manier as arbitrêr uitzoeken hoeveel beweeg te maak? Wat kan 'n beter blok wees as herhaal 10 keer wees? 

Ja, so hoekom nie iets vir ewig doen? Laat My dan nou beweeg hierdie legkaart stuk binnekant daar en ontslae te raak van hierdie een. Let nou op maak nie saak waar Scratch begin, gaan hy na die rand. En gelukkig MIT, wat maak nuuts af, net maak seker dat hy nooit verdwyn heeltemal. Jy kan altyd gryp sy stert. 

En net intuïtief, waarom hy bly beweeg? Wat is hier aan die gang? Dit lyk of hy het gestop, maar dan as ek haal en sleep Hy hou wil daar gaan. Hoekom is dit? Voorwaar, 'n rekenaar is letterlik gaan om te doen wat jy dit vertel om te doen. So as jy dit het vroeër doen die volgende ding vir ewig, beweeg 10 stappe, dit gaan om voort te gaan en gaan totdat ek druk die rooi stopteken en stop die program geheel en al. 

So selfs as jy nie dit te doen, hoe kon ek maak Scratch skuif vinniger oor die skerm? Meer stappe, of hoe? So in plaas van om 10 op 'n tyd, hoekom het ons nie gaan voort en verander dit aan- wat sou jy propose-- 50? So nou gaan ek op die groen vlag, en inderdaad, hy gaan baie vinnig. 

En dit, natuurlik, is net 'n manifestasie van animasie. Wat is animasie? Dit is net wat jy die menslike n hele klomp van nog beelde regtig, baie, baie vinnig. En so as ons net vertel hom meer stappe te beweeg, ons is maar net om die effek wees om verandering waar hy is op die skerm al die vinniger per eenheid van tyd. 

Nou is die volgende uitdaging wat ek voorgestel was om hom weerkaats die rand. En sonder om te weet wat legkaart stukke exist-- want dit is goed As jy nie aan die kom stadium van die challenge-- wat wil jy intuïtief te doen? Hoe sou ons hom terug te bons en uitgegaan tussen die links en regs? 

Ja. So ons moet 'n soort van toestand, en ons lyk conditionals het, om so te praat, onder die kategorie beheer. Watter een van hierdie blokke ons waarskynlik wil hê? Ja, miskien "As, dan." So sien dat onder die geel blokkies Ons het hier, daar is hierdie "as" of hierdie "As, anders" blok wat ons in staat stel om 'n besluit om dit te doen maak of om dit te doen. En jy kan selfs nes hulle om verskeie dinge te doen. Of as jy nie hier nog gegaan het, gaan voort om die kategorie Sensing and-- laat ons sien of dit hier. 

So, wat blok kan hier nuttig wees op te spoor as hy van die verhoog af? Ja, sien dat sommige van hierdie blokke kan parametrized, om so te praat. Hulle kan soort aangepas, nie In teenstelling met HTML gister met eienskappe, waar daardie kenmerke soort pas die gedrag van 'n tag. Net so hier, kan ek gryp hierdie roerende blok en verandering en vra die vraag, jy die muis te raak wyser soos die wyser of jy raak die rand? 

So laat my gaan in en dit te doen. Ek gaan om uit te zoomen vir 'n oomblik. Laat my gryp hierdie legkaart stuk hier, hierdie legkaart stuk hierdie, en ek gaan mengelmoes hulle vir net 'n oomblik. Ek gaan hierdie skuif, verander hierdie te raak rand, en ek gaan mosie dit te doen. So hier is 'n paar bestanddele. Ek dink ek het alles wat ek wil kry. 

Sou iemand graag voorstel hoe ek kan konnekteer hierdie dalk bo na onder ten einde die probleem van 'los Kras skuif na regs na links na regs om links na regs na links, elke tyd net weerkaats die muur? Wat wil ek doen? Watter blok moet ek toegang tot die "Toe groen vlag gekliek eerste"? 

OK, so laat ons begin met die "vir ewig." Wat gaan binne die volgende? Iemand anders. OK, beweeg stappe. Alles reg. Wat dan? So dan die as. En sien, selfs al is dit lyk saam landgebonde styf, dit sal net groei in te vul. Dit sal net spring in waar ek dit wil hê. 

En wat doen Ek sit tussen die as en die destydse? Waarskynlik "As raak rand." En kennis, weer, dit is te groot want dit, maar dit sal groei in te vul. En dan draai 15 grade? Hoeveel grade? Ja, so 180 sal draai my al die pad rond. So laat ons sien of ek dit reg. Laat my zoom uit. 

Laat my sleep Scratch up. So hy is 'n bietjie verdraai nou, maar dit is goed. Hoe kan ek maklik herstel hom? Ek gaan 'n bietjie oneerlik. Dus is ek die toevoeging van 'n ander blok, net om duidelik te wees. Ek wil hê hy moet 90 grade wys om die reg by verstek, so ek gaan net om hom te vertel om dit programmaties doen. En hier gaan ons. Ons lyk dit te doen. Dit is 'n bietjie vreemd, want hy loop onderstebo. Kom ons noem dit 'n fout. Dit is 'n fout. 'N fout is 'n fout in 'n program, 'n logiese fout wat ek, die mens, gemaak. Hoekom gaan hy onderstebo? Het MIT skroef of het ek? 

Ja, ek bedoel, dit is nie MIT se skuld. Hulle het my 'n legkaart stuk wat sê draai 'n paar aantal grade. En op voorstel Victoria se Ek draai 180 grade, wat is die regte aanvoeling. Maar draai 180 grade letterlik beteken draai 180 grade, en dit is nie regtig wat ek wil, blykbaar. Want ten minste is hy in hierdie twee-dimensionele wêreld, so draai is regtig aan die gang om hom onderstebo draai. 

Ek wil seker in watter blok gebruik In plaas daarvan, op grond van wat jy hier sien? Hoe kan ons dit regmaak? Ja, so ons kon wys in die teenoorgestelde rigting. En eintlik selfs dit is gaan nie genoeg wees, want ons kan net hard-kode om te wys links of regs. 

Jy weet wat ons kan doen? Dit lyk of ons 'n gerief blok hier. As ek in zoom, sien iets wat ons hier graag? So dit lyk soos MIT het 'n onttrekking gebou in hier. Hierdie blok lyk soortgelyk te wees waaraan ander blokke, meervoud? 

Hierdie een blok lyk soortgelyk te wees om hierdie hele trio van blokke dat ons hier. So dit blyk ek vereenvoudig my program deur om ontslae te raak van al daardie en net sit dit in hier. En nou is hy nog 'n bietjie karretjie, en dit is goed vir nou. Ons sal laat dit wees. Maar my program is selfs eenvoudiger, en dit is ook verteenwoordiger sal wees van 'n doel in programming-- is om ideaal maak jou kode as eenvoudige, so kompak as moontlik, terwyl hy nog in so leesbare as moontlik. Jy wil nie om dit so bondig maak dat dit moeilik is om te verstaan. 

Maar let op wat ek vervang drie blokke met een, en dit is waarskynlik 'n goeie ding. Ek het weg onttrek die idee van kontrole of jy nou op die rand met net een blok. Nou kan ons pret te hê met hierdie, in werklikheid. Dit beteken nie soseer voeg intellektuele waarde, maar speelse waarde. Ek gaan om voort te gaan en hier gryp hierdie klank. So laat ek gaan voort, en laat my stop die program vir 'n oomblik. Ek gaan die volgende noteer, die verlening van toegang tot my mikrofoon. 

Hier gaan ons. Eina. Kom ons probeer dit weer. Hier gaan ons. OK, aangeteken ek die verkeerde ding. Hier gaan ons. Eina. Eina. Alles reg. Nou moet ek om ontslae te raak van daardie. Alles reg. 

So nou het ek 'n opname van net "eina." So nou is ek gaan om te gaan voort en noem dit "eina." Ek gaan om terug te gaan om my skrifte, en nou kennisgewing daar hierdie blok wat genoem speel klank "miaau" of speel klank "eina." Ek gaan hierdie sleep, en waar moet ek dit vir komiese effek? Ja, so nou is dit soort karretjie, want nou hierdie block-- sien hoe hierdie "As stomp, weiering "is 'n soort van self-vervat. So ek moet dit op te los. Laat my gaan voort en doen dit. Laat my ontslae te raak van hierdie en gaan terug ons oorspronklike, meer doelbewuste funksionaliteit. So "As raak rand, dan" Ek wil om te draai, as Victoria voorgestel 180 grade. En ek wil om te speel die klank "eina" daar? 

Ja, sien dis buite dat geel blok. So dit ook sou wees 'n fout, maar ek het dit opgemerk. So ek gaan dit sleep hier, en kennis is dit nou binne-in die "as." So het die "as" is hierdie soort van soos arm-agtige klad dit is net gaan doen wat die binnekant van dit. So nou as ek zoom uit te die risiko van annoying-- 

REKENAAR: Eina, eina, eina. 

David Malan: En dit sal net vir ewig aanhou. Nou net om dinge te versnel hier, laat ek gaan voort en oop te stel, Kom ons say-- laat my gaan na 'n paar van my eie dinge van die klas. En laat my oop te stel, kom ons sê, dit een wat deur een van ons onderrig genote 'n Paar jaar gelede. So 'n paar van julle sal onthou hierdie spel van weleer, en dit is eintlik merkwaardig. Selfs al is wat ons gedoen het die eenvoudigste van programme op die oomblik, Kom ons kyk wat hierdie eintlik lyk. Laat my getref speel. 

So in hierdie wedstryd, het ons 'n kikker, en met behulp van die pyltjie keys-- Hy neem groter stappe as wat ek remember-- Ek het beheer oor hierdie kikker. En die doel is oor die besige te kry pad sonder hardloop in die motor. En laat ons see-- as ek optrek hier, ek hoef te wag vir 'n teken om deur te blaai. Dit voel soos 'n fout. Dit is 'n soort van 'n fout. Alles reg. Ek is oor hierdie hier, daar, en dan hou jy gaan totdat jy al kry die paddas na die lelie pads. Nou dit kan sien des te meer komplekse, maar laat ons probeer om te breek dit neer geestelik en mondelings in sy samestellende blokke. Daar is dus waarskynlik 'n legkaart stuk wat ons nog nie gesien het nie maar dit is te reageer op toetsaanslagen, om dinge wat ek getref op die sleutelbord. 

Daar is dus waarskynlik 'n soort van blok wat sê, as sleutel gelyk het, dan is daar iets met Scratch-- doen Miskien beweeg dit 10 stappe op hierdie manier. As down sleutel gedruk word, beweeg 10 stappe Sodoende of links sleutel, beweeg 10 stappe Sodoende 10 stappe wat. Ek het duidelik geword die kat in 'n padda. So dit is net waar die kostuum, as Scratch oproepe it-- ons net 'n foto van die padda ingevoer. 

Maar wat anders gebeur? Wat ander reëls van die kode, watter ander stukke van die legkaart het Blake, ons onderrig mede, gebruik in hierdie program, blykbaar? Wat maak alles move-- wat ontwikkeling rig? 

Beweging, sure-- so die beweeg blok, vir seker. En wat is die gewemel blok binnekant van, waarskynlik? Ja, 'n soort van loop, miskien 'n vir ewig te sluit, miskien 'n herhaling block-- herhaal totdat blok. En dit is wat maak die logs en die lelie pads en alles skuif heen en weer. Dit is net eindeloos gebeur. 

Hoekom is 'n paar van die motors beweeg vinniger as die ander? Wat is anders aan die programme? Ja, waarskynlik 'n paar van hulle neem meer stappe gelyktydig en sommige van hulle minder stappe gelyktydig. En die visuele effek is vinnig teenoor stadig. 

Wat dink jy gebeur? Toe ek my kikker al die pad oorkant die straat en die rivier op die lelie pad, iets noemenswaardige gebeur. Wat gebeur so gou as ek dit gedoen het? Dit gestop. Dit kikker gestop, en Ek het 'n tweede kikker. So, wat konstruk moet wees daar gebruik word, wat die funksie? 

Ja, so daar is 'n soort van "As" kondisioneer daar ook. En dit blyk out-- ons nie sien this-- maar daar is ander blokke in daar dat kan sê, as jy raak is Nog 'n ding op die skerm, as jy raak die lelie pad, "dan." En dan is dit wanneer ons maak die tweede kikker verskyn. So selfs al is hierdie spel is beslis baie gedateer, selfs al met die eerste oogopslag daar is so baie gaan is-- en Blake het dit nie sweep in twee minute, Dit het waarskynlik hom 'n paar uur om hierdie spel te skep gebaseer op sy geheue of video's van weergawe daarvan weleer se. Maar al hierdie klein dingetjies gaan op die skerm in isolasie neer op hierdie baie eenvoudige constructs-- bewegings of state soos ons bespreek, lusse en voorwaardes, en dit is omtrent dit. Daar is 'n paar ander liefhebber funksies. Sommige van hulle is suiwer estetiese of akoestiese, soos die geluide wat ek net met gespeel. Maar vir die grootste deel, jy het in hierdie taal, Scratch, al die fundamentele boustene wat jy het in C, Java, JavaScript, PHP, Ruby, Python, en 'n aantal ander tale. Enige vrae oor Scratch? Alles reg. Dan sal ons nie 'n duik in dieper te krap, al is jy welkom hierdie naweek, veral as jy kinders het of niggies en neefs en so, om hulle in te voer om te krap. Dit is eintlik 'n wonderlike speelse omgewing met, as die skrywers sê, 'n baie hoë plafonne. Selfs al het ons begin met 'n baie lae-vlak details, jy kan regtig nie nogal 'n bietjie daarmee, en dit is dalk 'n demonstrasie van presies dit. 

Maar laat ons nou die oorgang na 'n paar meer gesofistikeerde probleme, as jy wil, bekend as "soek" en "Sorteer," meer algemeen. Ons het hierdie telefoon boek earlier-- hier is 'n ander een net vir discussion-- wat ons in staat was om te soek meer doeltreffend as gevolg van 'n beduidende aanname. En net om duidelik te wees, wat aanname was ek maak wanneer jy soek deur middel van hierdie telefoon boek? Dit Mike Smith was in die telefoon boek, maar ek kan hanteer sou wees die scenario sonder hom daar as ek vroeg gestop net. Die boek is alfabetiese. En dit is 'n baie vrygewige aanname, want dit beteken someone-- Ek is soort sny 'n hoek, soos ek vinniger omdat iemand anders het 'n baie harde werk vir my. 

Maar wat as die telefoon boek is Unsorted? Miskien Verizon het lui, net gooi almal se name en nommers in daar Miskien in die volgorde waarin hulle ingeskryf vir telefoon diens. En hoeveel tyd neem dit my om iemand soos Mike Smith vind? 1000 bladsy selfoon book-- hoeveel bladsye moet ek deur kyk? 

Almal van hulle. Jy is soort van geluk. Jy het letterlik op elke kyk bladsy as die telefoon boek is net lukraak gesorteer. Jy kan kry gelukkig en vind Mike op die heel eerste bladsy, omdat hy was die eerste kliënt om telefoon diens te bestel. Maar hy kan die laaste gewees, ook. 

So enige volgorde is nie goed nie. So dink ons ​​moet die sorteer telefoon boek of in die algemeen soort data wat ons gegee. Hoe kan ons dit doen? 

Wel, laat ek net probeer 'n Eenvoudige voorbeeld hier. Laat my gaan voort en gooi 'n paar getalle op die bord. Veronderstel die getalle wat ons het is, kom ons sê, vier, twee, een, en drie. En Ben, sorteer hierdie getalle vir ons. 

Goed so. Hoe het jy dit gedoen? Alles reg. So begin met die kleinste waarde en die hoogste, en dit is regtig 'n goeie intuïsie. En besef dat ons die mens is eintlik redelik goed in die oplossing van probleme soos hierdie, ten minste wanneer die data is relatief klein. Sodra jy begin om honderde het van getalle, duisende getalle, miljoene getalle, Ben waarskynlik kon dit nie heeltemal so vinnig te doen, die veronderstelling dat daar gapings in die getalle. Redelik maklik om te tel tot 'n miljoen anders, net tydrowend. 

So het die algoritme wat dit klink soos Ben gebruik nou net was op soek na die kleinste getal. So selfs al het ons mense kan neem in 'n baie inligting visueel, 'n Rekenaar is eintlik 'n bietjie meer beperk. Die rekenaar kan net kyk na een byte op 'n slag of miskien vier grepe op 'n time-- deesdae miskien 8 grepe op 'n time-- maar 'n baie klein aantal grepe op 'n gegewe tyd. 

So gegee dat ons regtig vier afsonderlike waardes here-- en jy kan dink Ben as ' Blinders op asof hy 'n rekenaar sulke dat hy nie enigiets anders kan sien as een nommer op 'n time-- sodat ons oor die algemeen sal aanvaar, soos in Engels, sal ons lees van regs na links. So het die eerste paar Ben waarskynlik gekyk by was vier en dan baie vinnig besef dit is 'n redelik groot number-- laat my bly kyk. 

Daar is twee. Wag 'n minuut. Twee kleiner as vier. Ek gaan om te onthou. Twee is nou die kleinste. Nou one-- dis nog beter. Dit is selfs kleiner. Ek gaan oor twee vergeet en net een dink tog. 

En hy kon ophou soek? Wel, hy kan op grond op hierdie inligting, maar hy moet liewer soek die res van die lys. Want wat as nul was in die lys? Wat gebeur as negatiewe een was in die lys? Hy weet net dat sy antwoord is korrek as hy uitvoerig kyk na die hele lys. So kyk ons ​​na die res van hierdie. Three-- dit was 'n vermorsing van tyd. Het jy ongelukkig, maar ek was nog korrek om dit te doen. En so nou is hy vermoedelik gekies om die kleinste getal en net sit dit aan die begin van die lys, soos ek sal hier doen. Nou wat het jy gedoen volgende, alhoewel jy het nie naastenby daaroor dink hierdie omvang? Herhaal die proses, so 'n soort van loop. Daar is 'n bekende idee. So hier is vier. Dit is tans die kleinste. Dit is 'n kandidaat. Nie meer nie. Nou het ek twee gesien. Dit is die volgende kleinste element. Three-- dis nie kleiner, sodat nou Ben kan uitpluk die twee. 

En nou is ons herhaal die proses, en natuurlik drie kry volgende uitgetrek. Herhaal die proses. Vier kry uitgetrek. En nou is ons uit getalle, sodat die lys moet gesorteer. 

En inderdaad, dit is 'n formele algoritme. 'N Rekenaar wetenskaplike sou noem dit "seleksie soort," die idee is soort 'n lys iteratively-- weer en weer en weer te kies die kleinste getal. En wat is lekker daaroor is Dit is net so darn intuïtief. Dit is so eenvoudig nie. En jy kan dieselfde herhaal werking weer en weer. Dit is eenvoudig. 

In hierdie geval was dit 'n vinnige, maar hoe lank neem dit eintlik neem? Kom ons maak dit lyk en voel 'n bietjie meer vervelige. So een, twee, drie, vier, vyf ses, sewe, agt, nege, 10, 11, 12, 13, 14, 15, 16-- arbitrêre getal. Ek wou net meer hierdie tyd as net die vier. So as ek 'n hele het n klomp van die nommers now-- dit nie eens saak nie wat hulle are-- laat dink oor wat hierdie algoritme is regtig soos. 

Veronderstel daar is getalle daar. Weereens, maak nie saak wat hulle is nie, maar hulle is lukraak. Ek toepassing Ben se algoritme. Ek nodig het om die kleinste aantal kies. Wat doen ek? En ek gaan fisiek doen dit hierdie keer om dit uit te tree. Op soek, soek, soek, soek, soek. Slegs deur die tyd wat ek kry om die einde van die lys kan Ek besef die kleinste getal was twee hierdie tyd. Een is nie in die lys. So ek sit twee. 

Wat doen ek nou? Op soek, soek, soek, soek. Nou het ek die nommer sewe, omdat daar is gapings in hierdie numbers-- maar net arbitrêr. Alles reg. So nou kan ek neersit sewe. Op soek na, soek. 

Nou ek neem aan, van Natuurlik, dat Ben nie ekstra RAM, ekstra geheue, want natuurlik Ek is op soek na dieselfde nommer. Ja, ek kon onthou al daardie getalle, en dit is absoluut waar. Maar as Ben al onthou van die liedjies wat hy gesien het, Hy het nie regtig gemaak fundamentele vordering want hy het reeds die vermoë om te soek deur die getalle op die bord. Onthou al die getalle nie help nie, want hy kan steeds as 'n rekenaar net kyk na, ons het gesê, 'n aantal op 'n slag. Daar is dus geen soort oneerlik daar wat jy kan benut. 

So in werklikheid, as ek bly soek die lys, Ek het letterlik net voort te gaan heen en weer deur dit, pluk uit die volgende kleinste getal. En as jy kan soort aflei uit my dom bewegings, hierdie kry net baie vervelige baie vinnig, en dit lyk asof ek terug gaan en weer, heen en weer nogal 'n bietjie. Nou om eerlik te wees, weet ek nie hoef te gaan heeltemal so, wel, kom ons see-- om eerlik te wees, Ek hoef nie te hou loop soveel stappe elke keer. Omdat, natuurlik, soos ek kies nommers van die lys, die oorblywende lys is korter. 

En so laat ons dink oor hoeveel stappe Ek is eintlik traipsing deur elke keer. In die heel eerste situasie Ons het 16 nommers, en so maximally-- laat ons net doen dit vir 'n discussion-- Ek het om te kyk deur 16 getalle tot die kleinste vind. Maar wanneer ek uitgegrawe die kleinste getal, hoe lank was die oorblywende lys, natuurlik? Net 15. So hoeveel nommers het Ben of ek om te kyk deur die tweede keer rond? 15, net om te gaan en vind die kleinste. Maar nou, natuurlik, die lys is, Ook kleiner as wat dit was voor. So hoeveel stappe gedoen ek moet die volgende keer neem? 14 en dan 13 en dan 12, plus dot, dot, dot, voordat ek gelaat met net een. So nou 'n rekenaar wetenskaplike sou vra, wel, wat beteken dat almal gelyk? Dit is gelyk aan eintlik 'n paar konkrete getal wat ons kon beslis doen aritmetisch, maar ons wil praat oor die doeltreffendheid van algoritmes 'n bietjie meer formulaically, onafhanklik van hoe lank die lys is. 

En so weet julle wat? Dit is 16, maar soos ek gesê het, laat ons net noem die omvang van die probleem N, waar N is 'n paar nommer. Miskien is dit 16, miskien is dit drie, miskien is dit 'n miljoen. Ek weet nie. Ek gee nie om. Wat ek regtig wil hê, is 'n formule wat ek kan gebruik om hierdie algoritme vergelyk teen ander algoritmes dat iemand dalk eis is beter of slegter. 

So dit blyk, en net ek weet dit van graad skool, dat dit werk eintlik uit om dieselfde iets soos n oor n plus een meer as twee. En dit gebeur, moet gelyk, van Natuurlik N kwadraat plus N meer as twee. So as ek wou 'n formule vir hoeveel stappe was betrokke by kyk na al van daardie getalle weer en weer en weer en weer, sou ek sê dit N kwadraat plus N meer as twee. Maar jy weet wat? Dit lyk net slordig. Ek het net regtig wil 'n algemene gevoel van dinge. En u sal onthou uit hoërskool dat daar is die idee van die hoogste orde termyn. Watter een van hierdie terme, die N kwadraat, die N, of die helfte, het die meeste impak met verloop van tyd? Hoe groter N kry, wat van hierdie sake die meeste? 

Met ander woorde, as ek prop in 'n miljoen, N kwadraat gaan waarskynlik wees die oorheersende faktor, omdat 'n miljoen keer self is 'n baie groter as plus een bykomende miljoen. So jy weet wat? Dit is so 'n darn groot indien jy vierkant 'n nommer. Dit maak nie regtig saak nie. Ons is net gaan kruis wat uit en vergeet het. En so 'n rekenaarwetenskaplike sou sê dat die doeltreffendheid van hierdie algoritme is op die einde van N squared-- Ek bedoel regtig 'n benadering. Dit is 'n soort van sowat N vierkant. Met verloop van tyd, hoe groter en groter N kry, dit is 'n goeie skatting vir wat die doeltreffendheid of 'n gebrek aan doeltreffendheid van hierdie algoritme eintlik is. En ek aflei dat, natuurlik, vanaf eintlik die wiskunde. Maar nou is ek net waai my hande, want ek het net wil 'n algemene gevoel van hierdie algoritme. 

So met behulp van dieselfde logika, intussen, Kom ons kyk na 'n ander algoritme Ons het reeds at-- lineêre soek. Toe ek was op soek vir die telefoon book-- nie sorteer dit, soek deur die telefoon book-- Ons het gesê dat dit ' 1000 stappe, of 500 stappe. Maar laat ons veralgemeen nie. As daar 'n bladsye in die telefoon boek, wat die loop van die tyd of die doeltreffendheid van lineêre soek? Dit is op die einde van hoeveel stappe om uit te vind Mike Smith met behulp van lineêre soek, die eerste algoritme, of selfs die tweede? 

In die ergste geval, Mike is aan die einde van die boek. So as die telefoon boek het 1000 bladsye, Ons het die vorige keer, in die ergste geval, dit kon neem ongeveer hoe baie bladsye Mike vind? Soos 1000. Dit is 'n bogrens. Dit is 'n ergste moontlike situasie. Maar weereens, ons wegbeweeg van getalle soos 1000 nou. Dis net n. 

So, wat is die logiese gevolgtrekking? Dit vind van Mike in 'n selfoon boek wat N bladsye het aan te gryp, in die heel ergste geval, hoeveel stappe op die einde van n? En inderdaad 'n rekenaar wetenskaplike sou sê dat die loop van tyd, of die prestasie of die doeltreffendheid of ondoeltreffendheid, van 'n algoritme soos 'n lineêre soek is op die einde van n. En ons kan dieselfde van toepassing logika van iets uit die kruising as ek nou net gedoen het om die tweede algoritme wat ons gehad het met die telefoon boek, waar ons het twee bladsye op 'n slag. 

So 1000 bladsy telefoon boek mag neem ons 500 bladsy draaie, plus een As ons dubbel terug 'n bietjie. So as 'n telefoon boek het N bladsye, maar ons doen twee bladsye op 'n tyd, dit is min of meer wat? N meer as twee, sodat dit is soos n meer as twee. Maar ek het die eis 'n oomblik gelede dat N oor two-- dit is soort van die dieselfde as net n. Dis net 'n konstante faktor, rekenaar wetenskaplikes sou sê. Kom ons net fokus op die veranderlikes, really-- die grootste veranderlikes in die vergelyking. 

So lineêre soek, of gedoen een bladsy op 'n slag of twee bladsye op 'n tyd, is 'n soort van fundamenteel dieselfde. Dit is nog steeds op die einde van n. Maar ek beweer met my prentjie vroeër dat die derde algoritme was nie lineêre. Dit was nie 'n reguit lyn. Dit was wat geboë lyn, en die algebraïese formule daar was wat? Meld van n-- so teken basis twee van N. En ons het nie in te gaan veel detail oor logaritmes vandag, maar die meeste rekenaar wetenskaplikes sou nie selfs vir jou sê wat die basis is. Want dit gaan alles net konstante faktore, om so te praat, net effense numeriese verskille. En so sou dit 'n baie algemene wees manier vir veral formele rekenaar wetenskaplikes by 'n raad of programmeerders op 'n wit bord eintlik argument wat algoritme hulle sou gebruik of wat die doeltreffendheid van hul algoritme is. 

En dit is nie noodwendig iets jy bespreek in enige detail, maar 'n goeie programmeerder is iemand wat 'n soliede, formele agtergrond. Hy is in staat om te praat jy in hierdie soort van manier en eintlik maak kwalitatiewe argumente waarom een ​​algoritme of een stuk sagteware is beter in een of ander manier na 'n ander. Omdat jy beslis kon net hardloop program een ​​persoon se en tel die aantal sekondes wat dit neem om 'n paar nommers te sorteer, en jy kan 'n paar uit te voer program ander persoon se en die getal sekondes wat dit neem. Maar dit is 'n meer algemene manier waarop jy kan gebruik om algoritmes te ontleed, as jy wil, net op papier of net mondelings. Sonder om eers om dit te draai, sonder selfs probeer monster insette, jy kan net redeneer daardeur. En so met die huur van 'n ontwikkelaar of indien met hom of haar soort argumenteer vir jou hoekom hul algoritme, hul geheime sous vir die soek miljarde van webblaaie vir jou maatskappy is beter, hierdie is hierdie soort argumente wat hulle moet verkieslik in staat wees om te maak. Of ten minste dit is die soort dinge wat sou kom in gesprek, by minste in 'n baie formele bespreking. Alles reg. So Ben voorgestelde iets genoem seleksie soort. Maar ek gaan voor te stel dat daar ' ander maniere om dit te doen, ook. Wat ek het nie regtig wil oor Ben se algoritme is dat hy aangehou loop, of nadat my loop, heen en weer en heen en weer en heen en weer. Wat gebeur as plaas ek was om te doen iets soos hierdie getalle hier en ek was net te gaan met elke getal op sy beurt as ek dit gegee? 

Met ander woorde, hier is my lys van getalle. Vier, een, drie, twee. En ek gaan die volgende te doen. Ek gaan die getalle te voeg waar hulle hoort eerder as hulle een kies op 'n slag. Met ander woorde, hier is die nommer vier. 

Hier is my oorspronklike lys. En ek gaan in stand te hou in wese 'n nuwe lys hier. So, dit is die ou lys. Dit is die nuwe lys. Ek sien die nommer vier eerste. My nuwe lys is aanvanklik leeg, so dit is trivially die geval wat vier is nou verskillende soorte lys. Ek is net om die aantal ek gegee het, en ek sit dit in my nuwe lys. 

Is hierdie nuwe lys gesorteer? Ja. Dit is dom, want daar is net een element, maar dit is absoluut gesorteer. Daar is niks uit plek. Dit is meer interessant, hierdie algoritme toe ek gaan na die volgende stap. 

Nou het ek een. So een, natuurlik, behoort aan die begin of die einde van hierdie nuwe lys? Die begin. So ek het 'n paar werk nou doen. Ek het al met 'n paar vryhede met my merker deur net teken dinge waar ek wil hulle maar dit is nie regtig akkuraat in 'n rekenaar. 'N Rekenaar, soos ons dit ken, het RAM, of Random Access Memory, en dit is een byte en 'n ander byte en ander byte. En as jy 'n GB RAM, jy het 'n miljard grepe, maar hulle is fisies in een plek. Jy kan nie net rond te beweeg dinge deur dit op die bord waar jy wil. So as my nuwe lys het vier plekke in die geheue, Ongelukkig is die vier is reeds op die verkeerde plek. 

So om die getal voeg een Ek kan nie net hier te trek nie. Dit geheue plek bestaan ​​nie. Dit sou wees kullery, en ek was verneuk picturaal vir 'n paar minute hier. So regtig, as ek wil een hier sit, Ek het na die vier tydelik kopieer en dan sit die een daar. 

Dis goed dat die inligting korrek is, dit is tegnies moontlik, maar besef dis ekstra werk. Ek het nie net die getal in die plek. Ek moes eers 'n skuif nommer, sit dit dan in die plek, so ek soort verdubbel my hoeveelheid werk. So hou dit in gedagte. 

Maar ek nou gedoen met hierdie element. Nou wil ek die nommer drie te gryp. Waar, natuurlik, beteken dit hoort? Tussenin. Ek kan nie oneerlik nie en net sit dit daar, omdat, weer, hierdie geheue is in fisiese plekke. So ek moet die vier kopieer en sit die drie hier. Nie 'n groot probleem nie. Dis net 'n ekstra stap again-- voel baie goedkoop. 

Maar nou het ek skuif op na die twee. Die twee, natuurlik, behoort hier. Nou begin jy sien hoe die werk kan ophoop. Nou wat moet ek doen? Ja, ek het na die vier beweeg, Ek moet dan die drie kopieer, en nou kan ek die twee in te voeg. En die vangs met hierdie algoritme, interessant genoeg, is dat veronderstel ons 'n meer ekstreme geval waar dit kom ons sê agt, sewe, ses, vyf, vier, drie, twee, een. Dit is, in baie kontekste, die ergste geval scenario, omdat die darn ding is letterlik agteruit. 

Dit maak nie regtig invloed op Ben se algoritme, want in Ben se keuse sorteer hy gaan hou gaan heen en weer deur die lys. En omdat hy altyd op soek deur die hele oorblywende lys, dit maak nie saak waar die elemente is. Maar in hierdie geval met my invoeging approach-- kom ons probeer dit. 

So een, twee, drie, vier, vyf, ses, sewe, agt. Een twee drie vier, vyf, ses, sewe, agt. Ek gaan die agt neem, en waar kan ek dit? Wel, aan die begin van my lys, want hierdie nuwe lys is gesorteer. En ek steek dit uit. 

Waar plaas ek die sewe? Darn dit. Dit moet daarheen gaan, sodat Ek het 'n paar kopiëring doen. En nou het die sewe gaan hier. Nou beweeg ek na die ses. Nou is dit nog meer werk. 

Agt moet hier gaan. Sewe moet hier gaan. Nou is die ses kan hier gaan. Nou gryp ek die vyf. Nou is die agt het om te gaan hier, sewe het om hier te gaan, ses het om hier te gaan, en nou die vyf en herhaal. En ek is pretty much voortdurend in beweging is. 

So aan die einde, hierdie algorithm-- ons sal noem dit voeg sort-- eintlik het 'n baie werk ook. Dis net verskillende soort werk as Ben se. werk Ben se het my aan die gang heen en weer al die tyd, kies die volgende kleinste element weer en weer. So was dit juis visuele soort werk. 

Dit ander algoritme, wat steeds correct-- dit sal die werk te kry done-- net verander die hoeveelheid werk. Dit lyk soos aanvanklik jy spaar, omdat jy net is die hantering van elke element voorlangs sonder loop al die pad deur die lys soos Ben was. Maar die probleem is, veral in hierdie Crazy gevalle waar dit gaan alles agteruit, jy is net soort uitstel van die harde werk totdat jy jou foute reg te stel. 

En so as jy kan hierdie voorstel agt en sewe en ses en vyf en later vier en drie en twee beweeg hulle weg deur die lys, Ons het net verander die tipe werk wat ons doen. In plaas van om dit te doen op die begin van my iterasie, Ek is net om dit te doen op die einde van elke iterasie. So dit blyk dat hierdie algoritme, Ook algemeen bekend as invoeging soort, is ook op die einde van N vierkant. Dit is eintlik nie 'n beter, geen beter nie. 

Daar is egter 'n derde benadering Ek sou ons aanmoedig om te oorweeg, wat is dit. So dink my lys, vir eenvoud weer, is vier, een, drie, two-- net vier getalle. Ben het 'n goeie aanvoeling, goeie menslike intuïsie voor, waardeur ons vaste die hele lys eventually-- invoeging soort. Ek mislei ons saam. Maar laat ons kyk na die eenvoudigste manier om hierdie lys te los. 

Hierdie lys is nie gesorteer. Hoekom? In Engels, verduidelik waarom dit is nie eintlik gesorteer. Wat beteken dit om nie gesorteer? 

STUDENT: Dit is nie opeenvolgende. 

David Malan: Nie opeenvolgende. Gee my 'n voorbeeld. 

STUDENT: Sit hulle in orde is. 

David Malan: OK. Gee my 'n meer spesifieke voorbeeld. 

STUDENT: stygende volgorde. David Malan: Nie stygende volgorde. Meer akkurate. Ek weet nie wat jy bedoel met stygende. Wat is fout? 

STUDENT: Die kleinste van die getalle is nie in die eerste plek. 

David Malan: Kleinste se nommer nie in die eerste plek. Wees meer spesifiek. Ek is besig om te vang op. Ons tel nie, maar wat buite werking is hier? 

STUDENT: numeriese volgorde. David Malan: numeriese volgorde. Almal se soort bewaring dit here-- baie hoë vlak. Net letterlik vir my sê wat is verkeerd soos 'n vyf-jaar-oue krag. 

STUDENT: plus een. 

David Malan: Wat is dit? 

STUDENT: plus een. 

David Malan: Wat bedoel jy plus een? Gee my 'n ander vyf-jaar-oue. Wat is fout, ma? Wat is fout, pa? Wat bedoel jy dit nie gesorteer? 

STUDENT: Dit is nie die regte plek. 

David Malan: Wat is nie op die regte plek? 

STUDENT: Vier. David Malan: OK, goed. So vier is nie waar dit moet wees. In die besonder, is dit reg? Vier en een, die eerste twee getalle Ek sien. Is dit reg? Nee, hulle is buite orde, reg? Trouens, dink nou oor 'n rekenaar, ook. Dit kan net kyk na miskien een, Miskien twee dinge by once-- en eintlik net een ding op 'n tyd, maar dit kan ten minste kyk na een ding dan die volgende ding reg langs dit. 

So is dit in orde? Natuurlik nie. So jy weet wat? Hoekom het ons nie neem baba stappe van hierdie probleem in plaas van om hierdie fancy algoritmes soos Ben, waar hy soort van die vasstelling dit deur herhaling deur die lys in plaas van om te doen wat ek gedoen het, waar Ek het net soort van vaste dit as ons gaan? Kom ons letterlik breek die idee van order-- numeriese volgorde, Noem dit wat jy want-- in hierdie paarsgewyse vergelykings. 

Vier en een. Is dit die korrekte volgorde? So laat ons los dit. Een en vier, en dan ons sal net kopieer dit. Goed, goed. Ek vaste een en vier. Drie en twee? Geen. Laat my woorde pas my vingers. Vier en drie? 

Dit is nie in orde is, so ek gaan een, drie, vier, twee doen. Goed so. Nou vier en twee? Ons moet dit op te los, te. So een, drie, twee, vier. So is dit gesorteer? Nee, maar is dit nader aan gesorteer? 

Dit is omdat ons hierdie vaste fout, vaste ons hierdie fout, en ons vaste die fout. So vaste ons drie foute waarskynlik. Nog nie regtig kyk gesorteer maar dit is objektief nader aan gesorteerde omdat ons vaste 'n paar van daardie foute. 

Nou wat moet ek doen? Ek hou nogal van die einde van die lys. Ek skynbaar vaste al die foute, maar nee. Want in hierdie geval, 'n paar nommers dalk geborrel het nader om ander getalle wat nog buite werking. So laat ons dit weer doen, en ek sal doen dit net in plek hierdie tyd. Een en drie? Dit is fyn. Drie en twee? Natuurlik nie, so laat ons dit verander. So twee, drie. Drie en vier? En nou, laat ons net veral pedanties hier. Is dit gesorteer? Julle mense weet dit gesorteer. 

Ek moet weer probeer. So Olivia stel ek probeer weer. Hoekom? Omdat 'n rekenaar het nie die luukse van ons menslike oë van net skrams back-- OK, ek gedoen. Hoe werk die rekenaar te bepaal dat die lys is nou gesorteer? Meganies. 

Ek moet deurgaan een maal, wys en net as ek maak nie / vind foute kan ek dan aflei as die rekenaar, yep, ons is goed om te gaan. So een en twee, twee en drie, drie en vier. Nou kan ek beslis sê dit is gesorteer, want ek geen veranderinge gemaak. Nou sou dit 'n fout wees en net dwase as ek, die rekenaar, gevra daardie selfde vrae weer verwag verskillende antwoorde. Indien nie gebeur nie. 

En so nou is die lys is gesorteer. Ongelukkig loop tyd van hierdie algoritme word ook N vierkant. Hoekom? Omdat jy N getalle, en in die ergste geval moet jy n getalle beweeg N keer, want jy het om aan te hou terug te kyk en potensieel los hierdie getalle. En ons kan 'n meer doen formele analise ook. 

So dit is al te sê ons het geneem drie verskillende benaderings, een van hulle onmiddellik intuïtief uit die kolf van Ben om my voorgestelde invoeging sorteer om hierdie een waar jy soort van uit die oog verloor die bos vir die bome aanvanklik. Maar dan as jy 'n stap terug te neem, voila, ons het die sortering idee vasgestel. So dit is, waag om te sê, 'n laer vlak miskien as 'n paar van die ander algoritmes, maar laat ons kyk of ons nie kan visualiseer hierdie by wyse van hierdie. 

So dit is 'n paar mooi sagteware wat iemand geskryf met behulp van kleurvolle bars dis gaan die volgende te doen vir ons. Elkeen van hierdie bars verteenwoordig 'n aantal. Langer die bar, hoe groter die getal, kleiner die bar, hoe kleiner die nommer. Ideaal gesproke wil ons 'n lekker piramide waar dit begin klein en kry 'n groot, en dit sou beteken dat hierdie bars gesorteer. So ek gaan om voort te gaan en te kies, byvoorbeeld, Ben se algoritme first-- seleksie soort. 

En sien wat dit doen. Die manier waarop hulle gekies het om visualiseer hierdie algoritme is dat, net soos ek was loop deur my lys, hierdie program is loop deur middel van sy lys van getalle, beklemtoon in pienk elke getal wat dit na. En wat is die punt om nou gebeur? 

Die kleinste getal wat Ek of Ben gevind skielik kry verskuif na die begin van die lys. En let op wat hulle gedoen het uitjaag die getal wat daar was, en dit is heeltemal fyn. Ek het nie in daardie vlak van detail. Maar ons moet sit dat die getal iewers, sodat ons net verskuif dit na die oop kol wat geskep is. So ek gaan hierdie bespoedig up, want anders is dit word vinnig baie geduld. Animasie speed-- daar gaan ons. So nou dieselfde beginsel Ek is die toepassing, maar jy kan begin om die algoritme voel, as jy wil nie, of sien dit 'n bietjie meer duidelik. En hierdie algoritme het die effek van kies die volgende kleinste element, so jy gaan begin om sien dit oprit aan die linkerkant. En op elke iterasie, soos ek voorgestelde, is dit nie 'n bietjie minder werk. Dit hoef nie al die pad om te gaan terug na die linkerkant van die lys, omdat dit reeds weet dit is gesorteer. Daarom is dit soort van voel soos dit is versnel, selfs al is elke stap is neem dieselfde hoeveelheid tyd. Daar is net minder stappe wat oorbly. En nou kan jy soort van voel die algoritme skoonmaak van die einde van dit, en inderdaad is dit nou uitgesorteer. 

So voeg soort is al gedoen. Ek nodig het om weer dit enige van die skikking. En sien wat ek kan net hou randomizing dit, en ons sal 'n aanpassing van die kry dieselfde benadering, voeg soort. Laat my stadig dit af hier. Kom ons begin wat verby is. Stop. 

Kom ons slaan vier. Daar gaan ons. Dit enige hulle skikking. En hier go-- ons voeg soort. Speel. Let daarop dat dit die hantering van elke element dit ontmoetings dadelik, maar as dit hoort in die verkeerde plek kennisgewing al die werk wat moet gebeur. Ons moet aanhou verskuiwing meer en nog baie meer elemente om plek te maak vir die een wil ons in plek te stel. 

Ons is dus fokus op die linkerkant van slegs die lys. Sien ons het nie eens gekyk at-- ons het nie uitgelig in pienk enigiets aan die regterkant. Ons is net die hantering van die probleme as ons gaan, maar ons skep 'n baie werk vir onsself steeds. En so as ons bespoedig hierdie up nou om te gaan na voltooiing, dit het 'n ander gevoel om dit inderdaad. Dit is net te fokus op die linker kant, maar doen 'n bietjie meer werk as needed-- soort glad dinge oor, vas dinge, maar die hantering uiteindelik met elke element een op 'n slag totdat ons om goed te the--, ons almal weet hoe dit gaan eindig, so dit is 'n bietjie underwhelming miskien. 

Maar die lys in die end-- spoiler-- gaan word gesorteer. So kom ons kyk na 'n laaste een. Ons kan nie net slaan nou. Ons is amper daar. Twee gaan, een om te gaan. En voila. Uitstekende. 

So nou kom ons doen 'n laaste een, weer randomizing met borrelsortering. En sien hier, veral as ek stadig dit af, beteken dit hou neerskiet deur. Maar let op dit maak net paarsgewyse comparisons-- soort plaaslike oplossings. Maar so gou as wat ons kry om die einde van die lys in pienk, wat gaan hê om weer te gebeur? Ja, dit gaan om te hê begin oor, omdat dit slegs vaste paarsgewyse foute. En dit kan nog ander het aan die lig gebring. En dus as jy hierdie bespoedig, sal jy sien dat soveel as die naam impliseer, die kleiner elements-- of liewer, die groter elements-- begin borrel op die top, as jy wil. En die kleiner elemente begin borrel tot by die linkerkant. En inderdaad, dit is soort van die visuele effek sowel. En so sal dit uiteindelik afwerking in 'n baie soortgelyke wyse ook. 

Ons hoef nie te woon op hierdie spesifieke een. Laat my nou oop, ook. Daar is 'n paar ander sorteringsalgoritmes in die wêreld, 'n paar van wat Hier vasgevang. En veral vir leerders wat nie noodwendig visuele of wiskundige, Soos ons vantevore gedoen het, kan ons dit te doen ook audially As ons assosieer 'n geluid met hierdie. En net vir die pret, hier is 'n paar verskillende algoritmes, en een van hulle in die besonder is jy gaan Kennisgewing heet "merge soort." 

Dit is eintlik 'n fundamenteel beter algoritme, sodanig dat soort saamsmelt, een van die mense wat jy oor om te sien, is nie orde van N vierkant. Dit is op die einde van N keer inteken van N, wat eintlik kleiner en dus vinniger as die ander drie. En daar is 'n ander paartjie dom mense wat ons sal sien. 

So hier gaan ons met 'n paar goeie. Dit is invoeging soort, so weer dit is net die hantering van die elemente soos hulle kom. Dit is borrelsortering, so dit is oorweeg dit pare op 'n slag. En weer, die grootste elemente is borrelende tot die top. 

Volgende aan die beurt seleksie soort. Dit is Ben se algoritme, waar weer hy kies iteratief die volgende kleinste element. En weer, nou kan jy regtig hoor wat dit bespoediging maar slegs in soverre as dit doen al hoe minder werk op elke iterasie. Dit is die vinniger een, saamsmelt soort, wat sorteer trosse van getalle saam en dan hulle te kombineer. So look-- links helfte is reeds gesorteer. 

Nou is dit te sorteer die regte helfte, en nou dit gaan om hulle te kombineer in een. Dit is iets genaamd "Gnome soort." En jy kan soort sien dat dit heen en weer gaan, vaststelling werk 'n bietjie hier en daar voor dit verder gaan om nuwe werk. En dit is dit. Daar is 'n ander soort, wat eintlik net vir akademiese doeleindes, genoem "dom sorteer," wat neem jou data, sorteer dit lukraak, en dan kontroleer of dit gesorteer is. En as dit is nie, is dit weer sorteer dit lukraak, tjeks as dit gesorteer, en as dit nie herhaal. En in teorie, probabilistically dit sal voltooi, maar na nogal 'n bietjie van die tyd. Dit is nie die mees doeltreffende algoritmes. So enige vrae oor die spesifieke algoritmes of enigiets Daar verwante ook? 

Wel, laat ons nou terg uitmekaar wat al hierdie lyne is dat ek het al die tekens en wat Ek neem aan die rekenaar kan doen onder die enjinkap. Ek sou argumenteer dat al hierdie getalle Ek hou drawing-- wat hulle nodig het om te kry iewers gestoor in die geheue. Ons sal ontslae te raak van hierdie man kry nou ook. 

So 'n stuk van die geheue in 'n computer-- so RAM DIMM is wat ons gesoek het gister, dubbele inline memory module-- lyk soos volg. En elkeen van hierdie klein swart skyfies is 'n paar aantal grepe, tipies. En dan die goud penne is soos die drade dat dit verbind aan die rekenaar, en die groen silikon raad is net wat hou alles bymekaar. So wat beteken dit werklik? As ek soort van dieselfde prentjie teken, Kom ons veronderstel vir eenvoud dat hierdie DIMM, dubbele inline geheue module is een GB RAM, een GB geheue, wat is hoeveel grepe totale? Een GB is hoeveel grepe? Meer as dit. 1124 is kilo, 1000. Mega is miljoen. Giga is 'n miljard. 

Ek lieg? Kan ons die etiket lees selfs? Dit is eintlik 128 GB, so dit is meer. Maar ons sal dit voorgee is net een gigagreep. So dit beteken dat daar 'n miljard grepe van die geheue beskikbaar vir my of 8000000000 stukkies, maar ons gaan om te praat in terme van grepe nou, beweeg vorentoe. 

So, wat beteken dit is dit een byte, dit is 'n ander byte, dit is 'n ander byte, en as ons regtig wou spesifieke ons sou hê om te wees trek 'n miljard bietjie blokkies. Maar wat beteken dit? Wel, laat ek net vergroot in hierdie foto. As ek iets het wat lyk soos dit nou, dit is vier grepe. 

En so kan ek vier nommers hier sit. Een twee drie vier. Of ek kon vier letters of simbole sit. "Haai!" kon net daar gaan, omdat elk van die briewe, ons vroeër bespreek, kan verteenwoordig met agt stukkies of ASCII of 'n greep. So met ander woorde, kan jy sit 8000000000 dinge binne hierdie een stuk hout van geheue. Nou wat beteken dit om dinge terug te sit om terug te back-in die geheue soos hierdie? Dit is wat 'n programmeerder sou 'n "skikking." noem In 'n rekenaarprogram, dink jy nie oor die onderliggende hardeware, per se. Jy dink net aan jouself as wat toegang tot 'n miljard grepe totale, en jy kan enigiets wat jy wil met dit. Maar vir gerief Dit is oor die algemeen nuttig om jou geheue reg te hou langs mekaar soos hierdie. So as ek zoom in op this-- omdat ons beslis nie van plan 'n miljard bietjie squares-- trek Kom ons veronderstel dat hierdie raad verteenwoordig dat stok geheue nou. En ek sal net trek soveel as my merker beland hier gee my. So nou het ons 'n stok geheue op die bord Dit is het een, twee, drie, vier, vyf, ses, een, twee, drie, vier, vyf, ses, seven-- so 42 grepe van geheue op die totale skerm. Dankie. Ja, het my rekenkundige reg. So 42 grepe van die geheue hier. So wat beteken dit eintlik? Wel, 'n rekenaarprogrammeerder sou eintlik oor die algemeen dink aan die geheue as aanspreekbaar. Met ander woorde, elkeen van hierdie plekke in die geheue, in hardeware, het 'n unieke adres. 

Dit is nie so ingewikkeld as een Brattle Square, Cambridge, Mass., 02138. In plaas daarvan, is dit net 'n paar. Dit is byte nommer nul, dit is een, dit is twee, dit is drie, en dit is 41. Wag 'n minuut. Ek het gedink ek het 42 'n oomblik gelede. Ek het begin tel op nul, so dit is eintlik korrek is. Nou het ons nie eintlik trek dit as 'n rooster, en as jy dit tog as 'n rooster Ek dink dinge eintlik kry 'n bietjie misleidend. Wat 'n programmeerder sou in sy of haar eie gedagtes, oor die algemeen dink van hierdie geheue as net soos 'n band, soos 'n stuk maskeerband wat net gaan aan en aan vir ewig of totdat jy hardloop uit die geheue. So 'n meer algemene manier om te trek en net te dink oor geheue sou wees dat dit byte nul, een, twee, drie, en dan dot, dot, dot. En jy het 42 sulke grepe totale, selfs Al is hulle fisies dit kan eintlik iets meer soos hierdie. 

So as jy nou dink aan jou geheue as dit, net soos 'n band, dit is wat 'n programmeerder weer sou 'n verskeidenheid van geheue roep. En as jy wil eintlik slaan iets in die geheue van 'n rekenaar, jy in die algemeen doen winkel dinge back-to-rug aan rug-aan-rug. So ons het gepraat oor getalle. En toe ek wou probleme op te los soos vier, een, drie, twee, selfs al het ek was net te teken net die nommers vier, een, drie, twee op die bord, die rekenaar sal regtig hierdie opstelling in die geheue. 

En wat sou langs die wees twee in die rekenaar se geheue? Wel, daar is geen antwoord op daardie. Ons weet nie regtig. En so lank as wat die rekenaar dit nie nodig nie, Dit hoef nie om wat volgende is om die getalle dit nie omgee. Toe ek vroeër gesê het dat 'n rekenaar kan net kyk na 'n adres in 'n tyd, hierdie is 'n soort van waarom. 

Nie in teenstelling met 'n rekord speler en 'n lesing kop net in staat is om te kyk na 'n sekere groef in 'n fisiese ou-skool rekord op 'n tyd, insgelyks kan 'n rekenaar te danke om sy CPU en sy Intel stel instruksies, onder wie se opdrag gelees uit die geheue of stoor na 'n memory-- rekenaar kan net kyk op een plek op 'n time-- soms 'n kombinasie van hulle, maar eintlik net een plek op 'n slag. So wanneer ons doen hierdie verskillende algoritmes, Ek is nie net skryf in 'n vacuum-- vier, een, drie, twee. Hierdie syfers eintlik hoort iewers fisiese geheue. So is daar klein bietjie transistors of 'n soort elektronika onder die kap stoor hierdie waardes. 

En in totaal, hoeveel stukkies is betrokke op die oomblik, net om duidelik te wees? Dit is dus vier grepe, of nou is dit 32 stukkies totaal. So is daar eintlik 32 nulle en kinders komponeer hierdie vier dinge. Daar is selfs meer hier nie, maar weer het ons nie omgee nie. 

So nou kom ons vra 'n ander vraag met behulp van geheue, want dit aan die einde van die dag is in stryd. Maak nie saak wat ons kan doen met die rekenaar, aan die einde van die dag die hardeware is nog steeds die dieselfde onder die enjinkap. Hoe sou ek slaan 'n woord hier? Wel, 'n woord in 'n rekenaar soos "Hey!" sou word gestoor net soos hierdie. En as jy wil 'n langer woord, kan jy net oorskryf dit en iets sê soos "hallo" en bêre dit hier. 

En so ook hier, hierdie contiguousness is eintlik 'n voordeel, omdat 'n rekenaar kan net lees van regs na links. Maar hier is 'n vraag. In die konteks van hierdie woord, h-e-l-l-o, uitroepteken, hoe kan die rekenaar weet waar die woord begin en waar die woord eindig? In die konteks van getalle, hoe werk die rekenaar weet hoe lank die volgorde van getalle is of waar dit begin? Wel, dit blyk out-- en ons sal nie te veel gaan in hierdie vlak van detail-- rekenaars te beweeg dinge rondom in die geheue letterlik deur middel van hierdie adresse. So in 'n rekenaar, as jy skryf kode om dinge te stoor soos woorde, wat jy regtig doen is tik uitdrukkings wat onthou waar in geheue van die rekenaar se hierdie woorde is. So laat ek doen 'n baie, baie eenvoudige voorbeeld. 

Ek gaan om voort te gaan en oop te stel 'n eenvoudige teks program, en ek gaan om te skep 'n lêer met die naam hello.c. Die meeste van hierdie inligting wat ons sal nie in te gaan in groot detail, maar ek gaan 'n skrywe program in wat dieselfde taal, C. Dit is veel meer intimiderend, Ek sou argumenteer, as nuuts af, maar dit is baie soortgelyk in die gees. Trouens, hierdie krullerige braces-- jy kan soort dink aan wat ek nou net gedoen soos hierdie. 

Kom ons doen dit, eintlik. Wanneer groen vlag gekliek, Doen die volgende. Ek wil uit te druk "hallo." So is dit nou pseudokode. Ek is soort van vervaag die lyne. In C, hierdie taal Ek praat oor, hierdie lyn druk hallo eintlik word "printf" met sommige hakies en 'n kommapunt. 

Maar dit is presies dieselfde idee. En dit baie gebruikers vriendelik "Toe groen vlag gekliek" word die veel meer arcane "int main leemte." En dit het regtig geen kartering, so ek gaan net te ignoreer nie. Maar die krullerige draadjies is soos die geboë legkaart stukke soos hierdie. 

Sodat jy kan soort van dink. Selfs as jy nog nooit voorheen geprogrammeer, Wat beteken hierdie program waarskynlik doen? Waarskynlik druk hallo met 'n uitroepteken. 

So kom ons probeer dit. Ek gaan om dit te verlos. En dit is, weer, 'n baie ou skoolomgewing. Ek kan nie op, ek kan nie sleep. Ek moet opdragte tik. So ek wil my program uit te voer, sodat Ek kan dit doen, soos hello.c. Dit is die lêer wat ek gehardloop. Maar wag, ek mis 'n stap. Wat het ons sê is 'n noodsaaklike stap vir 'n taal soos C? Ek het net geskrewe bron kode, maar wat moet ek doen? Ja, ek het 'n samesteller. So op my Mac hier, ek het 'n program genaamd GCC, GNU C samesteller, wat dit moontlik maak vir my om this-- beurt doen my bronkode in, sal ons dit noem, masjienkode. 

En ek kan sien dat, weer, soos volg, hierdie is die nulle en ene ek net geskep uit my bronkode, al die nulle en ene. En as ek wil uit te voer my program-- dit gebeur om a.out genoem word vir historiese reasons-- "hallo." Ek kan dit weer uit te voer. Hallo, hallo, hallo. En dit blyk te werk. 

Maar dit beteken iewers in my geheue rekenaar se is die woorde h-e-l-l-o, uitroepteken. En dit blyk, net soos 'n eenkant, wat 'n rekenaar sou tipies doen sodat dit weet waar dinge begin en end-- dis gaan 'n spesiale simbool hier sit. En die konvensie is om die plaas getal nul aan die einde van 'n woord sodat jy weet waar dit eintlik eindig, sodat jy hou nie uit te druk hoe meer karakters as wat jy werklik van plan is. 

Maar die afhaal hier, selfs al is dit redelik arcane, is dat dit uiteindelik relatief eenvoudig. Jy is gegee soort van 'n band, 'n leë ruimte waarop jy briewe kan skryf. Jy hoef net 'n moet spesiale simbool, soos arbitrêr die getal nul, om aan die einde van sit jou woorde sodat die rekenaar weet, O, ek moet druk stop nadat Ek sien die uitroepteken. Omdat die volgende ding wat daar is 'n ASCII-waarde van nul, of die nul karakter as iemand sou dit noem. Maar daar is soort van 'n probleem hier, en laat ons terugkeer om getalle vir 'n oomblik. Veronderstel dat ek, in werklikheid, 'n skikking van getalle, en veronderstel dat die program Ek skryf is soos 'n graad boek vir 'n onderwyser en 'n onderwysers klaskamer. En hierdie program verleen hom of haar om te tik in tellings hul studente se op vasvrae. En veronderstel dat die student kry 100 op hul eerste toets, miskien soos 'n 80 op die volgende een, dan 'n 75, dan 'n 90 op die vierde toets. 

So op hierdie punt in die verhaal, die skikking is van groot vier. Daar is absoluut meer geheue in die rekenaar, maar die skikking, so te sê, is van groot vier. Veronderstel nou dat die onderwyser wil 'n vyfde toets om die klas te wys. Wel, een van die dinge wat hy of sy gaan hê om te doen is nou 'n bykomende waarde slaan hier. Maar as die skikking moet die onderwyser geskep in hierdie program is van grootte vir, een van die probleem met 'n skikking is dat jy kan nie net aanhou toe te voeg tot die geheue. Want wat as 'n ander deel van die program het die woord "hey" net daar? 

Met ander woorde, kan my geheue wees gebruik word vir enigiets in 'n program. En as vooruit ek getik in, hey, Ek wil insette vier quiz tellings, hulle kan hier en hier gaan. En as jy skielik verander jou gedagtes later en sê ek wil 'n vyfde toets telling, kan jy nie net sit dit waar jy wil, want wat as dit geheue gebruik word vir iets else-- 'n ander program of 'n ander kenmerk van die program dat jy hardloop? So jy moet dink vooruit hoe jy jou data stoor, want nou het jy geverf jouself in 'n digitale hoek. 

So 'n onderwyser mag plaas sê wanneer die skryf van 'n program op te slaan sy of haar grade, jy weet wat? Ek gaan vra, tydens die skryf van my program, wat ek wil nul, een, twee, drie, vier, vyf, ses, agt grade totaal. So een, twee, drie, vier, vyf, ses, sewe, agt. Die onderwyser kan net meer toe te ken geheue tydens die skryf van sy of haar program en sê, jy weet wat? Ek is nooit gaan meer wys as agt vasvrae in 'n semester. Dit is net gek. Ek sal nooit wys dat. Sodat hierdie manier het hy of sy die buigsaamheid te slaan student tellings, soos 75, 90, en miskien een ekstra waar die student het ekstra krediet, 105. 

Maar as die onderwyser nooit gebruik hierdie drie ruimtes, daar is 'n intuïtiewe afhaal hier. Hy of sy is net mors spasie. So met ander woorde, daar is hierdie gemeenskaplike nadeel in programmering waar jy óf kan toeken presies soveel geheue as wat jy wil, die onderstebo waarvan is dat jy super is efficient-- jy nie verkwistende by all-- maar die nadeel van wat is wat as jy jou verstand wanneer verander die gebruik van die program wat jy wil stoor meer inligting as wat jy oorspronklik bedoel. 

So miskien is die oplossing is, dan, skryf jou programme op so 'n manier wat hulle gebruik meer geheue as wat hulle werklik nodig het. Hierdie manier waarop jy gaan nie uit te voer in die probleem, maar jy word verkwistende. En hoe meer geheue jou program maak gebruik van, soos ons gister bespreek, hoe minder geheue wat beskikbaar is op die ander kursusse, hoe gouer jou rekenaar kan vertraag af as gevolg van virtuele geheue. En so het die ideale oplossing sou wat wees? 

Onder-verdeling lyk sleg. Oor-verdeling lyk sleg. So, wat kan 'n beter oplossing wees? Herverdeling. Meer dinamies. Moenie jouself te dwing om 'n keuse priori, aan die begin, wat jy wil hê. En in elk geval nie veel toe te ken, sodat julle nie wees verkwistende. 

En so aan daardie doel te bereik, het ons nodig om hierdie datastruktuur gooi, so te sê, weg. En so what 'n programmeerder sal tipies gebruik is iets genoem nie 'n verskeidenheid, maar 'n geskakelde lys. Met ander woorde, sal hy of sy begin om te dink aan hul geheue as soort van 'n vorm dat hulle kan trek op die volgende manier. As ek wil 'n paar op te slaan in 'n program-- so dit is September, Ek het my studente 'n quiz gegee; ek wil om eerste toets die studente se stoor, en hulle het 'n 100 op it-- ek Ek gaan op my rekenaar te vra, deur middel van die program Ek het geskryf, vir een stuk van die geheue. En ek gaan na die winkel getal 100 in dit, en dit is dit. 

Toe 'n paar weke later wanneer ek my tweede toets, en dit is tyd om te tik in daardie 90%, gaan ek om die rekenaar te vra, hey, rekenaar, kan ek nog 'n stuk van die geheue? Dit gaan vir my gee hierdie leë stuk van die geheue. Ek gaan in die getal 90 te sit, maar in my program op 'n manier of other-- en ons sal nie bekommerd wees oor die sintaksis vir this-- ek nodig het om een ​​of ander manier ketting hierdie dinge saam. En Ek sal hulle saam met ketting wat lyk soos 'n pyl hier. 

Die derde toets wat opkom, Ek gaan om te sê, hey, rekenaar, Gee my 'n ander deel van die geheue. En ek gaan neersit wat dit ookal was, soos 75, en ek moet ketting hierdie saam nou een of ander manier. Vierde toets kom saam, en miskien dit is teen die einde van die semester. En deur daardie punt my program kan gebruik word om die geheue oor die hele plek, regoor fisies. En so net vir skoppe, is ek gaan dit voort te trek quiz-- ek vergeet wat dit was; Ek dink miskien 'n 80 of something-- weg oor hier. 

Maar dit is goed, want picturaal Ek gaan hierdie streep te trek. Met ander woorde, in werklikheid, in hardeware van die rekenaar, die eerste telling mag uiteindelik hier, want dit is reg aan die begin van die semester. Die volgende een kan uiteindelik hier omdat 'n bietjie van die tyd verby is en die program hou hardloop. Die volgende telling, wat was 'n 75, dalk hier. En die laaste telling dalk 'n 80, wat is hier. 

So in werklikheid, fisies, dit kan wees wat jou rekenaar se geheue lyk. Maar dit is nie 'n nuttige geestelike paradigma vir 'n rekenaarprogrammeerder. Hoekom moet jy omgee waar die klink jou data is eindig? Jy wil net om data te stoor. 

Dit is soort van soos ons bespreking vroeër van die tekens van die kubus. Hoekom dink jy omgee wat die hoek van die kubus en hoe jy moet draai om dit te trek? Jy wil net 'n kubus. Net so hier, jy wil net graad boek. Jy wil net om te dink aan dit as 'n lys van getalle. Wie gee om hoe dit is geïmplementeer in hardeware? 

So het die onttrekking nou is hierdie prentjie hier. Dit is 'n geskakelde lys, soos 'n programmeerder sou dit noem, sover as wat jy het 'n lys, natuurlik van getalle. Maar dit is picturaal gekoppel deur middel van hierdie pyle, en al hierdie pyle are-- onder die kap, as jy nuuskierig is, onthou dat ons fisiese hardeware het adresse nul, een, twee, drie, vier. Al hierdie pyle is soos 'n kaart of rigtings, waar as 90 is-- nou Ek het om te tel. 

Zero, een, twee, drie, vier, vyf, ses, sewe. Dit lyk soos die 90 is op geheue adres nommer sewe. Al hierdie pyle is soos 'n klein stukkie papier dit is die gee van aanwysings om die program wat sê volg hierdie kaart om plek sewe te kry. En daar sal julle die vind student se tweede toets telling. Intussen het die 75-- as ek voortgaan om hierdie, Dit is sewe, agt, nege, 10, 11, 12, 13, 14, 15. 

Dit ander pyl net verteenwoordig 'n kaart om geheue plek 15. Maar weereens, die programmeerder oor die algemeen nie nie omgee hierdie vlak van detail. En in die meeste elke programmering taal vandag, die programmeerder sal nie eens weet waar in die geheue hierdie getalle eintlik is. Al wat hy of sy moet omgee is dat hulle een of ander manier met mekaar verbind in 'n datastruktuur soos hierdie. 

Maar dit blyk nie te tegnies te kry. Maar net omdat ons kan dalk bekostig om hierdie bespreking hier te hê, veronderstel dat ons weer hierdie kwessie hier van 'n skikking. Kom ons kyk of ons hier spyt gaan. Dit is 100, 90, 75, en 80. 

Laat my kortliks hierdie eis te maak. Dit is 'n skikking, en weer, die belangrike eienskap van 'n verskeidenheid is dat al jou data is terug na rug aan rug in memory-- letterlik een byte of miskien vier grepe, sommige vaste aantal grepe weg. In 'n geskakelde lys, wat ons kan trek soos hierdie, onder die enjinkap wat weet waar daardie dinge is? Dit maak nie eens nodig om te vloei soos hierdie. Sommige van die data kon wees terug na die links daar. Jy hoef nie eens weet nie. 

En so 'n skikking, jy het 'n kenmerk bekend as ewetoeganklike. En wat ewetoeganklike middel is dat die rekenaar onmiddellik kan spring om enige plek in 'n skikking. Hoekom? Omdat die rekenaar weet dat die eerste plek is nul, een, twee, en drie. 

En so as jy wil gaan uit hierdie element na die volgende element, jy letterlik, in die gedagte rekenaar se, voeg net een. As jy wil om te gaan na die derde element, voeg net one-- volgende element, net voeg een. Maar in hierdie weergawe van die storie, veronderstel die rekenaar is tans op soek na op of die hantering van die getal 100. Hoe kry jy na die volgende graad in die graad boek? 

Jy moet neem sewe stappe, wat is arbitrêr. na die volgende een te kry, moet jy neem 'n ander agt stappe om 15 te kry. Met ander woorde, dit is nie 'n konstante gaping tussen die getalle, en dus is dit net neem die rekenaar meer tyd is die punt. Die rekenaar het om te soek deur geheue ten einde om uit te vind wat jy soek. 

So terwyl 'n verskeidenheid is geneig om 'n wees vinnige data structure-- omdat jy kan letterlik net eenvoudige rekenkundige en kry waar jy wil deur die toevoeging van een, vir instance-- n geskakelde lys, jy offer wat funksie. Jy kan nie net gaan van die eerste tweede tot derde tot vierde. Jy moet die kaart te volg. Jy moet meer stappe te neem om daardie waardes, te kry wat sou blyk te wees toevoeging van 'n koste. So ons betaal 'n prys, maar wat was die funksie wat Dan hier is op soek na? Wat doen 'n geskakelde lys glo ons in staat stel om dit te doen, wat was die oorsprong van hierdie spesifieke storie? 

Presies. 'N dinamiese grootte om dit te. Ons kan by hierdie lys. Ons kan selfs krimp die lys, sodat dat ons net jy gebruik soveel geheue as ons werklik wil en so ons nooit oor-verdeling. 

Nou net om werklik neet-kieskeurig, daar is 'n versteekte koste. So jy moet nie net laat my oortuig jy dat dit 'n dwingende nadeel. Daar is nog 'n versteekte koste hier. Die voordeel, om duidelik te wees, is dat ons dinamika. As ek wil 'n ander element, kan ek net teken dit en sit 'n aantal in daar. En dan kan ek dit te koppel met 'n prentjie hier, terwyl hier weer, as ek het geverf myself in 'n hoek, As iets anders is reeds met behulp van die geheue hier, ek is out of luck. Ek het myself geverf in die hoek. 

Maar wat is die verborge kos in hierdie prentjie? Dit is nie net die bedrag tyd wat dit neem om te gaan van hier af tot hier, wat is sewe stappe, dan agt trappies, wat meer as een. Wat is 'n ander verborge koste? Nie net tyd. Meer besonderhede kan wat nodig is om hierdie foto te bereik. 

Ja, wat kaart, daardie klein stukkies papier, soos ek hou beskryf dit as. Hierdie arrows-- dit is nie vry nie. A computer-- jy weet wat 'n rekenaar het. Dit het nulle en ene. As jy wil 'n pyl of 'n stel karteer of 'n nommer, jou 'n paar geheue benodig. So het die ander prys wat jy betaal vir 'n geskakelde lys, 'n gemeenskaplike rekenaarwetenskap hulpbron, is ook ruimte. 

En inderdaad so, so algemeen, onder die werkinge in die ontwerp van sagteware-ingenieurswese stelsels is tyd en space-- is twee van jou bestanddele, twee van jou mees kosbare bestanddele. Dit kos my meer tyd want ek het om die kaart te volg, Maar dit is ook kos my meer ruimte want ek het tot die kaart om te hou. So het die hoop, as ons het soort bespreek oor gister en vandag, is dat die voordele sal swaarder as die koste. 

Maar daar is geen duidelike oplossing hier. Miskien is dit better-- a la vinnige en vuil, as Kareem voorgestelde earlier-- geheue te gooi by die probleem. koop net meer geheue, dink minder hard oor die oplossing van die probleem, en los dit in 'n makliker manier. En inderdaad vroeër, toe Ons het gepraat oor werkinge, dit was nie ruimte in die rekenaar en tyd. Dit was ontwikkelaar tyd, wat is nog 'n hulpbron. 

So weer, dit is hierdie balans te vind probeer om te besluit watter een van dié dinge is jy bereid om te spandeer? Wat is die goedkoopste? Wat lewer die beter resultate? Ja? 

Inderdaad. In hierdie geval, as jy voorstelling van getalle op die maps-- hierdie is geroep in verskeie tale "Pointers" of "adresse" - dis dubbel die ruimte. Dit hoef nie so erg soos dubbel wees indien nou is ons net die stoor van getalle. Veronderstel dat ons die stoor pasiënt rekords in 'n hospital-- sodat name Pierson se telefoonnommers, sosiale sekerheid nommers, dokter geskiedenis. Hierdie boks kan baie wees, veel groter, in welke geval 'n klein bietjie wyser, die adres van die volgende element-- dit is nie 'n groot deal. Dit is so 'n byvoordele kos dit maak nie saak. Maar in hierdie geval, ja, dit is 'n verdubbeling. Goeie vraag. 

Kom ons praat oor tyd 'n bietjie meer konkreet. Wat is die bestuur van tyd van soek hierdie lys? Veronderstel ek wou soek deur alle grade die studente se en daar is N grade in hierdie datastruktuur. Ook hier kan ons leen die woordeskat van vroeër. Dit is 'n lineêre datastruktuur. 

Big O van N is wat nodig is om te kry tot aan die einde van hierdie datastruktuur, whereas-- en ons het nie gesien hierdie before-- 'n skikking gee jou wat genoem konstante tyd, wat beteken 'n stap of twee stappe of 10 steps-- maak nie saak. Dit is 'n vaste aantal. Dit het niks te doen met die grootte van die skikking. En die rede daarvoor, weer, is ewetoeganklike. Die rekenaar kan net onmiddellik spring na 'n ander plek, want hulle is almal dieselfde afstand van alles. Daar is geen denke betrokke is. Alles reg. So as ek kan, laat ek probeer om verf twee finale foto's. 'N Baie algemene een bekend as 'n hash tafel. So om hierdie bespreking te motiveer, Laat my dink oor hoe om dit te doen. 

So wat dink jy hiervan? Veronderstel dat die probleem Ons wil nou los is die uitvoering van 'n dictionary-- so 'n hele klomp van die Engelse woorde of wat ook al. En die doel is om in staat wees om te antwoord vrae van die vorm is dit 'n woord? So jy wil uit te voer 'n speltoetser, net soos 'n fisiese woordeboek dat jy kan dinge opkyk in. Veronderstel ek was om dit te doen met 'n skikking. Ek kan dit doen. 

En dink die woorde is Apple en piesang en spanspek. En ek kan nie dink aan vrugte wat begin met D, so ons is net gaan drie vrugte het. So dit is 'n skikking, en ons is stoor al hierdie woorde in hierdie woordeboek as 'n skikking. Die vraag is dus hoe anders kon jy hierdie inligting te stoor? 

Wel, ek soort bedrog hier, want elk van hierdie letters in die woord is regtig 'n individu byte. So as ek regtig wou wees neet-kieskeurig gesê: Sou ek regtig word verdeel hierdie is in die veel kleiner stukke van die geheue, en ons kon presies dit te doen. Maar ons gaan loop in dieselfde probleem as voorheen. Wat as, soos Merriam Webster of Oxford doen elke year-- hulle woorde by te voeg om die dictionary-- doen ons nie noodwendig wil onsself te verf in 'n hoek met 'n verskeidenheid? 

So in plaas, miskien 'n slimmer benadering is om die appel in sy eie node of boks, as ons sou sê, piesang, en dan hier het ons spanspek. En ons string hierdie dinge saam. Dit is dus die skikking, en dit is die geskakelde lys. As jy nie heeltemal kan sien, is dit net sê "skikking," en dit sê "lys." 

Ons het dus dieselfde presiese kwessies soos voorheen, waardeur ons nou dinamika in ons geskakelde lys. Maar ons het 'n redelik stadige woordeboek. Veronderstel ek wil om te kyk op 'n woord. Dit mag dalk vir my te neem groot O van N stappe, want die woord kan wees al die pad aan die einde van die lys, soos spanspek. En dit blyk dat in programmering, sorteer van die heilige graal van data strukture, is iets wat gee jou konstante tyd soos 'n skikking maar wat gee jou nog dinamika. 

So kan ons die beste van beide wêrelde? En inderdaad, daar is iets bekend as die hash tafel wat jou toelaat om presies te doen dat, hoewel ongeveer. 'N gemors tafel is 'n liefhebber datastruktuur dat ons kan dink as die kombinasie van 'n array-- en ek gaan om dit te trek soos this-- en geskakelde lyste dat ek sal trek soos hierdie hier. 

En die wyse waarop hierdie ding werke is soos volg. As dit now-- hash table-- is my derde datastruktuur, en ek wil stoor woorde in hierdie, ek doen nie wil net al die stoor woorde rug aan rug aan rug aan rug. Ek wil 'n paar hefboom stukkie inligting oor die woorde wat jou sal laat my kry waar dit vinniger. 

So kry die woorde appel en piesang en spanspek, Ek doelbewus gekies daardie woorde. Hoekom? Wat is soort van fundamenteel anders oor die drie? Wat is die voor die hand liggend? Hulle begin met verskillende letters. 

So jy weet wat? Eerder as om te sit al my woorde in dieselfde emmer, om so te praat, soos in 'n groot lys, waarom doen nie Ek ten minste probeer om 'n optimalisering en my lyste 26/01 solank maak. 'N dwingende optimalisering dalk hoekom doen nie I-- wanneer invoeging van 'n woord in hierdie datastruktuur, in die rekenaar se geheue, waarom weet ek nie sit al die 'n se woorde hier, al die 'B' woorde hier, en al die "c" woorde hier? So eindig dit op om 'n appel hier, piesang hier, spanspek hier, en dies meer. 

En as ek 'n bykomende woord like-- wat 'n ander? Apple, piesang, peer. Enigiemand dink aan 'n vrug wat begin met A, B, of C? Blueberry-- volmaak. Dit gaan uiteindelik hier. En so lyk ons ​​'n moet effens beter oplossing, want nou as ek wil Soek vir appel, ek first-- ek doen nie net duik in my datastruktuur. Ek het nie 'n duik in die geheue van my rekenaar se. Ek kyk eers na die eerste letter. 

En dit is wat 'n rekenaar wetenskaplike sou sê. Jy hash in jou datastruktuur. Jy neem jou insette, wat in hierdie geval is 'n woord soos appel. Jy analiseer dit, kyk na die eerste letter in hierdie geval, daardeur hashing dit. Hashing is 'n algemene term waardeur jy iets as invoer neem en jy produseer sommige uitset. En die uitset in daardie geval is die plek jy wil soek, die eerste plek, tweede plek, derde. So het die insette is appel, die produksie is die eerste. Die insette is piesang, die uitset moet tweede wees. Die insette is spanspek, die uitset moet derde wees. Die insette is ys, die uitset moet weer tweede. En dit is wat jou help om te neem kortpaaie deur jou geheue ten einde woorde te kry of data meer effektief. 

Nou sny dit af ons tyd potensieel met soveel as een uit 26, want as jy aanvaar dat jy het soveel " 'n" woorde soos "Z" woorde soos "V" woorde, wat is nie regtig realistic-- jy gaan skeef oor het sekere letters van die alphabet-- maar dit sou 'n inkrementele wees benadering wat toelaat jy veel vinniger om woorde te kry. En in werklikheid, 'n gesofistikeerde program, die Googles van die wêreld, die Facebooks van die world-- Hulle sou 'n gemors tafel gebruik vir 'n baie verskillende doeleindes. Maar hulle sal nie so naïef as wees om net te kyk na die eerste letter in appel of piesang of peer of spanspek, want as jy dit kan sien lyste kan nog steeds 'n lang. 

En so gaan dit dalk nog soort wees van linear-- so soort van stadig, soos met die groot O van N dat ons vroeër bespreek. So, wat 'n baie goeie hash tafel do-- dit sal 'n veel groter verskeidenheid het. En dit sal 'n baie meer gebruik gesofistikeerde hashing funksie, sodat dit nie net kyk na die "a." Miskien is dit kyk na " 'n p-p-l-e" en een of ander manier vat die vyf letters in die plek waar Apple moet gestoor word. Ons is net naïef met behulp van die letter 'n ' alleen, want dit is lekker en maklik. 

Maar 'n hash tafel in die ou end, kan jy dink van so 'n kombinasie van 'n skikking, wat elk 'n geskakelde lys wat ideaal moet so kort as moontlik wees. En dit is nie 'n voor die hand liggende oplossing. Trouens, baie van die fine tuning wat gaan aan onder die enjinkap toe implementering van hierdie soort gesofistikeerde datastrukture is wat die reg lengte van die skikking? Wat is die regte hash funksie? Hoe kan jy slaan dinge in die geheue? 

Maar besef hoe vinnig hierdie soort van gesprek toegeneem, óf so ver dat dit soort van meer as 'n mens se kop op hierdie punt, wat is fyn. Maar ons het, onthou, met werklik iets lae-vlak en elektroniese. En so is dit weer hierdie tema van onttrekking, waar sodra jy begin om te neem vir verleen, OK, ek het it-- het daar fisiese geheue, OK, het dit, elke fisiese plek het 'n adres, OK, ek het dit, kan ek verteenwoordig diegene adresse as arrows-- jy kan baie vinnig begin om meer gesofistikeerde gesprekke wat op die ou end lyk ons ​​te laat om probleme soos soek op te los en sorteer meer effektief. En wees verseker, too-- want ek dink dit is die diepste ons gegaan het in 'n paar van hierdie CS onderwerpe proper-- ons het gedoen in 'n dag en 'n half by hierdie wys wat jy kan gewoonlik oor doen die loop van agt weke in 'n semester. 

Enige vrae oor hierdie? Geen? Alles reg. Wel, hoekom nie ons daar breek, begin middagete 'n paar minute vroeg, hervat in net oor 'n uur? En Ek sal talm vir 'n bietjie met vrae. Toe ek gaan hê om te gaan neem 'n paar oproepe as dit is OK. Ek sal draai op musiek in die tussentyd, maar middagete moet wees om die draai.