>> DAVID Malan: Të gjithë të drejtë.
Ne jemi kthyer.
Pra, në këtë segment në programimin çfarë Mendova se ne do të bëjmë është një përzierje e gjërave.
One, të bëjë pak për diçka duart-on,
edhe pse duke përdorur një shumë të gjallë programimit environment--
ai që është i demonstrative saktësisht llojet e ideve
ne kemi qenë duke folur në lidhje me, por pak më formale.
Dy, të shikojmë disa nga mënyra më teknike
që një programues në fakt do të zgjidhte Problemet si problemin në kërkim
që ne shikuar në para dhe edhe më thelbësisht
Problemi interesante e gjykimit.
>> Ne vetëm mori nga te merrni që ky libër telefoni u renditur,
por se vetëm është në fakt një lloj i Problemi vështirë me shumë mënyra të ndryshme
për të zgjidhur atë.
Pra, ne do të përdorim këto si një klasë e problemeve
përfaqësues i gjërave që mund të zgjidhen në përgjithësi.
Dhe pastaj ne do të flasim lidhje në disa detaje se çfarë
quhen të dhënat structures-- mënyra njohës si listat e lidhura
dhe tavolina hash dhe pemë që një programues do të vërtetë
përdorur dhe në përgjithësi përdorin në një whiteboard për të pikturuar
një foto të asaj që ai ose ajo parashikon për zbatimin
disa pjesë e software.
>> Pra, le të bëjë duart-në pjesën e parë.
Pra, vetëm të marrë në duart tuaja të pista me një mjedisit quajtur scratch.mit.edu.
Ky është një mjet që ne përdorim në klasën tonë universitare.
Edhe pse është e projektuar për moshat 12 e lart,
ne e përdorin atë për deri pjesë e atij mjaft pak
pasi kjo është një e mirë, fun Mënyra grafike e të mësuarit
një diçka të vogël në lidhje me programimin.
Kështu që të shkojnë në këtë URL, ku ju duhet të shihni një faqe krejt si ky,
dhe të shkojnë përpara dhe klikoni Join Scratch në krye të drejtë
dhe të zgjidhni një username dhe a fjalekalimin dhe në fund të fundit për të marrë veten
një scratch.mit.edu account--.
Unë mendova se do të përdorin këtë si një mundësia e parë për të treguar këtë.
Një pyetje doli gjatë pushimit në lidhje me atë code fakt duket si.
Dhe ne ishim duke folur gjatë pushimit rreth C,
në particular-- veçanërisht a Niveli më i ulët në një gjuhë të vjetër.
Dhe unë vetëm e bëri një të shpejtë Google kërko për të gjetur kodin C
për kërkimin binar, algoritmi që ne përdoret për të kërkuar atë librin e telefonit më parë.
Ky shembull i veçantë, sigurisht, nuk kërkoni një libër telefoni.
Ajo vetëm kërkon një bandë e tërë e numrat në kujtesën e kompjuterit.
Por në qoftë se ju dëshironi të merrni vetëm një vizuale kuptim të asaj që një programimit aktuale
gjuha duket si, duket një diçka të vogël si kjo.
Pra, kjo është në lidhje me 20-plus, 30 apo më shumë rreshta të kodit,
por biseda ne kishin mbi pushim
ishte se si kjo në fakt merr shndërrua në zero dhe ato
dhe në qoftë se ju nuk mund të kthehet se procesit dhe të shkojnë nga zero dhe ato
mbështetur të kodit.
>> Për fat të keq, procesi i është aq transformuese
se kjo është një shumë më e lehtë tha se bëhet.
Unë shkova përpara dhe në fakt u se programi, Binary Kërko:
në zero dhe ato me anë të një Programi i quajtur Compiler se unë
ndodh që të ketë këtu të drejtë në Mac tim.
Dhe në qoftë se ju shikoni në ekran këtu, duke u fokusuar në mënyrë të veçantë
në këto të mesëm gjashtë kolona vetëm, ju do të shihni vetëm zero dhe ato.
Dhe ata janë zero dhe ato që shkruaj pikërisht atë program kërkim.
>> Dhe kështu që çdo copë e pesë copa, çdo bajt e zero dhe ato këtu,
paraqesin disa udhëzime zakonisht brenda një kompjuter.
Dhe në fakt, në qoftë se ju keni dëgjuar marketingut slogan "Intel brenda" - se,
sigurisht, thjesht do të thotë që ju keni një Intel CPU apo truri brenda kompjuterit.
Dhe çfarë do të thotë të jetë një CPU është që ju të keni një instruksioneve,
mënyrë që të flasin.
>> Çdo CPU në botë, shumë prej ata të bërë nga Intel këto ditë,
kupton një fundme numër i udhëzimeve.
Dhe ato udhëzime janë të nivelit aq të ulëta si shtesë e këtyre dy numra së bashku,
shumohen këta dy numra së bashku, lëvizur këtë pjesë të të dhënave nga këtu
për të këtu në kujtesë, për të shpëtuar këtë informacion nga këtu për të këtu në kujtesë,
dhe kështu forth-- aq shumë, shumë Nivelit të ulët, të dhënat pothuajse elektronike.
Por me ato matematikore operacionet bashku
me atë që kemi diskutuar më herët, përfaqësimi i të dhënave
si zero dhe ato, mund të ju të ndërtuar çdo gjë
që një kompjuter mund të bëjë sot, nëse kjo është tekstuale, grafike, muzikore,
ose ndryshe.
>> Pra, kjo është shumë e lehtë për të marrë humbur në barërat e këqija të shpejtë.
Dhe nuk është një shumë e sfidat sintaksore
ku në qoftë se ju bëni më të thjeshtë, budalla e tipos asnjë programit
do të punojnë whatsoever.
Dhe kështu që në vend të përdorimit të një gjuha si C këtë mëngjes,
Mendova se do të ishte më shumë argëtim për të vërtetë të bëjë
diçka më shumë vizuale, e cila duke projektuar për fëmijët
është në fakt një manifestim i përsosur e një programimin aktual
language-- ndodh vetëm për të përdorin fotografitë në vend të tekstit
për të përfaqësuar ato ide.
>> Pra, një herë ju të vërtetë kanë një llogari në scratch.mit.edu,
kliko butonin Krijo në krye majtë të faqes.
Dhe ju duhet të shihni një mjedis si ajo që unë jam gati për të parë në ekran e mia
këtu.
Dhe ne do të shpenzojnë pak pak kohë duke luajtur këtu.
Le të shohim nëse ne nuk mund të gjithë të zgjidhur disa Problemet së bashku në mënyrën e mëposhtme.
>> Kështu që ajo që ju do të shihni në këtë environment-- dhe në fakt vetëm le
me pauzë.
A është dikush nuk është këtu?
Jo ketu?
NE RREGULL.
Pra më lejoni të theksoj disa Karakteristikat e këtij mjedisi.
>> Pra, në të majtë krye të ekranit, ne kanë fazën e para, kështu që të flasin.
Scratch nuk është vetëm emri e kësaj gjuhe programimi;
është edhe emri i mace që ju shikoni nga default atje në portokalli.
Ai është në një fazë, në mënyrë ashtu si kam përshkruar
breshkë më parë si në një drejtkëndëshe mjedisi bordit të bardhë.
Bota e këtij mace kufizohet tërësisht për këtë drejtkëndësh deri të lartë atje.
>> Ndërkohë, në të djathtë nga e djathta, këtu, është e
vetëm një zonë scripts, një propozoj bosh nëse ju do.
Kjo është ajo ku ne jemi duke shkuar për të shkruar programet tona në një moment të vetëm.
Dhe blloqet ndërtuese që do të përdorin për të shkruar këtë program-- mister
copa, nëse ju jeni will-- ata të drejtë këtu në mes,
dhe ata janë të kategorizuar nga funksionaliteti.
Kështu, për shembull, unë jam duke shkuar për të shkuar përpara dhe të demonstrojnë të paktën një nga këto.
Unë jam duke shkuar për të shkuar përpara dhe klikoni kategoria Kontrollit up krye.
>> Pra, këto janë kategori deri krye.
Unë jam duke shkuar për të klikoni në kategorinë e kontrollit.
Përkundrazi, unë jam duke shkuar për të klikoni Ngjarje kategori, shumë të parë një dorë të lartë.
Dhe në qoftë se ju dëshironi për të ndjekur së bashku edhe si ne të bërë këtë, ju jeni mjaft të mirëpritur për të.
Unë jam duke shkuar për të klikoni dhe terhiq këtë para ", kur flamuri gjelbër klikuar".
Dhe atëherë unë jam duke shkuar për të hequr dorë atë vetëm afërsisht në krye të listat e mia bosh.
>> Dhe çfarë është e bukur për Scratch është se kjo pjesë mister, kur
kombinuara me mister tjetër copë, do të bëjë fjalë për fjalë
çfarë ato copa mister të thotë për të bërë.
Kështu, për shembull, Scratch është e drejtë tani në mes të botës së tij.
Unë jam duke shkuar për të shkuar përpara dhe të zgjedhin Tani, le të themi, kategoria Motion,
në qoftë se ju dëshironi të bëni të same-- kategori Motion.
Dhe tani vini re unë kam një tërësi bandë e puzzle copë këtu
që, përsëri, lloj bëjnë atë që thonë ata.
Dhe unë jam duke shkuar për të shkuar përpara dhe të drag and rënie bllok veprim të drejtë mbi këtu.
>> Dhe vini re se sa më shpejt që ju të merrni afër në fund e "flamurit gjelbër
klikuar "button, njoftimi si një vijë e bardhë duket,
sikur është pothuajse magnetike, ajo dëshiron të shkojë atje.
Vetëm le të shkojë, dhe ajo do të parakohshme së bashku dhe forma do të përputhen.
Dhe tani ju mund ndoshta pothuajse me mend se ku ne jemi duke shkuar me këtë.
>> Nëse ju shikoni në fazën Scratch mbi këtu dhe të shohim në krye të saj,
ju do të shihni një dritë të kuqe, një ndaluar shenjë, dhe një flamur të gjelbër.
Dhe unë jam duke shkuar për të shkuar përpara dhe të shikojnë screen-- mia
për vetëm një moment, nëse ju mund të.
Unë jam duke shkuar për të klikoni flamurin e gjelbër të drejtë tani,
dhe ai shkoi atë që duket të jetë 10 hapa ose 10 pixels, 10 pika, në ekran.
>> Dhe jo aq se emocionuese, por më lejoni të propozoj
edhe pa e mësuar këtë, vetëm përdorimin e vet e let tuaj intuition--
me të propozojë që të kuptoj se si për të të bëjë shëtitje Scratch drejtë off fazë.
A ai të bëjë rrugën për anën e djathtë të ekran, të gjitha mënyra për të djathtë.
Më lejoni t'ju jap një moment ose në mënyrë të luftoj me atë.
Ju mund të dëshironi të marrë një sy në kategoritë e tjera të blloqeve.
Në rregull.
Pra, vetëm për radhitje, kur kemi flamuri gjelbër klikuar këtu
dhe për të shkuar 10 hapa është vetëm udhëzim, çdo herë që unë
klikoni flamurin e gjelbër, çfarë po ndodh?
E pra, kjo është drejtimin programin tim.
Kështu që unë mund të bëjë këtë ndoshta 10 herë me dorë,
por kjo ndihet pak bit hackish, kështu që të flasin,
ku unë nuk jam me të vërtetë zgjidhjen e problemit.
Unë jam vetëm duke u përpjekur përsëri dhe përsëri dhe përsëri dhe përsëri
deri sa lloj aksidentalisht arritur direktivën
që unë e përcaktuar për të arritur më parë.
>> Por ne e dimë nga tonë pseudocode më parë se nuk ka
ky nocion në programimin e looping, duke bërë diçka përsëri dhe përsëri.
Dhe kështu unë pashë se një bandë prej jush arritur për copë atë mister?
Përsëriteni deri.
Pra, ne mund të bëjmë diçka si të përsëritur deri.
Dhe çfarë keni përsëritur deri sa saktësisht?
>> NE RREGULL.
Dhe më lejoni të shkoj me një që është disi të thjeshtë për vetëm një moment.
Më lejoni të shkojnë përpara dhe të bëjë këtë.
Vini re se, si ju mund të keni zbuluar nën kontroll,
ka ky bllok të përsëritur, e cila nuk duket si ajo është aq e madhe.
Nuk ka shumë vend në në mes të këtyre dy vijave të verdha.
Por si disa prej jush mund të ketë vënë re, në qoftë se ju drag and drop,
vini re se si ajo rritet për të mbushur formën.
>> Dhe ju mund edhe të mbushur më shumë.
Ajo do të mbajë vetëm në rritje, nëse ju drag dhe rri pezull mbi të.
Dhe unë nuk e di se çfarë është më të mirë këtu, kështu që le
më së paku të përsërisë pesë herë, për shembull, dhe pastaj të kthehemi në fazën
dhe klikoni flamurin e gjelbër.
Dhe tani vini re kjo nuk është mjaft atje.
>> Tani disa prej jush të propozuar, si Victoria vetëm ka, të përsëritur 10 herë.
Dhe se në përgjithësi nuk marrë atë të gjithë rrugën,
por nuk do të ketë një më të fuqishme Mënyra se sa në mënyrë arbitrare parafytyruar
sa lëviz për të bërë?
Çfarë mund të jetë një bllok më të mirë se të përsëritur 10 herë të jetë?
>> Yeah, kështu që pse nuk bëni diçka për gjithnjë?
Dhe tani më lejoni të lëvizë këtë pjesë mister brenda atje dhe të shpëtoj nga ky.
Tani vini re pa marrë parasysh se ku Scratch fillon, ai shkon në buzë.
Dhe fatmirësisht MIT, i cili bën Scratch, vetëm
e bën të sigurt se ai nuk zhduket plotësisht.
Ju mund gjithmonë të kap bishtin e tij.
>> Dhe vetëm intuitive, pse ai mbani lëviz?
Çfarë po ndodh këtu?
Ai duket se ka ndalur, por atëherë në qoftë se unë marr dhe terhiq
ai mban dëshirojnë të shkojnë atje.
Pse eshte ajo?
Me të vërtetë, një kompjuter është fjalë për fjalë do të bëni atë që ju them se për të bërë.
Pra, nëse ju tregoi atë më parë të bëjë të pas gjë përgjithmonë, lëvizin 10 hapa,
ajo do të mbajë dhe shkon deri sa unë goditi shenjë të kuqe të ndaluar
dhe të ndaluar programin krejt.
>> Pra, edhe në qoftë se ju nuk e keni bëni këtë, si mund unë
të bëjë lëvizje të shpejtë Scratch nëpër ekran?
Më shumë hapa, apo jo?
Pra, në vend që të bëjnë 10 në një kohë, pse nuk e bëjmë ne
të shkojnë përpara dhe për të ndryshuar atë to-- çfarë do të propose-- 50?
Kështu që tani unë jam duke shkuar për të klikoni gjelbër flamurin, dhe në të vërtetë, ai shkon të vërtetë të shpejtë.
>> Dhe kjo, sigurisht, është vetëm një manifestim i animacion.
Çfarë është animacion?
Kjo është vetëm duke ju dhënë një të njeriut tërë bandë e imazheve ende me të vërtetë,
me të vërtetë, të vërtetë të shpejtë.
Dhe kështu që në qoftë se ne jemi vetëm duke u thënë atë për të lëvizur më shumë hapa,
ne jemi vetëm duke pasur efekti të jetë për ndryshimi, ku ai është në ekran
të gjithë më shpejt për njësi të kohës.
>> Tani sfida e ardhshme që kam propozuar ishte që të ketë atë të kërcej off buzë.
Dhe pa e ditur se çfarë puzzle copë exist-- për shkak se ajo është në rregull
në qoftë se ju nuk e merrni për të Faza e challenge-- asaj
doni të bëni intuitive?
Si do ta kemi atë të kërcej prapa dhe me radhë, në mes të majtë dhe të djathtë?
>> Po.
Pra, ne kemi nevojë për një lloj e gjendjes, dhe ne
duket se kanë conditionals, në mënyrë që të flasin, nën kategorinë Kontrollit.
Cila nga këto blloqe nuk kemi ndoshta dëshironi?
Yeah, ndoshta "nëse, atëherë."
Pra, vini re se në mesin e blloqeve të verdhë ne kemi këtu, nuk është kjo "nëse"
ose kjo "nëse, tjetër" bllok që do të të na lejojë të marrë një vendim për të bërë këtë
ose për të bërë këtë.
Dhe ju mund edhe fole ato për të bërë gjëra të shumta.
Ose në qoftë se ju nuk keni shkuar këtu ende, të shkojnë përpara në kategorinë Sensing
and-- le të shohim nëse ai është këtu.
>> Pra, çfarë bllok mund të jetë e dobishme këtu për të zbuluar nëse ai është jashtë skene?
Po, vini re se disa nga këto blloqe mund të parametrized, kështu që të flasin.
Ato mund të jenë përshtatur lloj, nuk ndryshe HTML dje me atributet,
ku këto atribute lloj rregulloje sjelljen e një tag.
Në mënyrë të ngjashme këtu, mund ta kap këtë prekje bllok dhe për të ndryshuar dhe të bëni pyetje,
jeni prekur miun pointer si kursorit
ose jeni prekur buzë?
>> Pra më lejoni të shkoj në dhe të bëjë këtë.
Unë jam duke shkuar për të zoom jashtë për një moment.
Më lejoni të rrëmbyer këtë pjesë mister këtu, ky mister pjesë këtë,
dhe unë do të grumbull ata up për vetëm një moment.
Unë jam duke shkuar për të lëvizur këtë, ndryshojë këtë për buzë prekur,
dhe unë jam duke shkuar për të bërë këtë lëvizje.
Pra, këtu janë disa nga përbërësit.
Unë mendoj se kam gjithçka që dua.
>> Dikush do të doja të propozojë si unë mund të lidhë këto ndoshta krye e deri në fund
në mënyrë për të zgjidhur problemin e të pasurit Scratch veprim i drejtë për të majta në të djathtë për të
majta në të djathtë në të majtë, çdo Ora vetëm kërcim jashtë murit?
Çfarë unë dua të bëj?
Të cilat bllok duhet të lidheni me "Flamurin kur green klikuar parë"?
>> OK, kështu që le të fillojë me "përgjithmonë."
Çfarë shkon brenda e ardhshme?
Dikush tjeter.
OK, lëvizin hapa.
Në rregull.
E pastaj?
Pra, atëherë, nëse.
Dhe vini re, edhe pse duket sandwiched bashku fort,
ajo vetëm do të rritet për të mbushur.
Ajo thjesht do të hidhen në ku unë dua atë.
>> Dhe çfarë kam vënë në mes të if dhe pastaj?
Ndoshta "nëse buzë prekur."
Dhe vini re, përsëri, kjo është shumë e madhe për të, por ajo do të rritet për të mbushur.
Dhe pastaj të kthehet 15 gradë?
Sa gradë?
Yeah, kështu që 180 do të tjerr me gjithë rrugës përreth.
Pra, le të shohim nëse unë kam këtë të drejtë.
Më lejoni të zoom out.
>> Më lejoni të zvarritet Scratch up.
Pra, ai është pak e shtrembëruar tani, por kjo është në rregull.
Si mund të rivendosur atë të lehtë?
Unë do të mashtrojnë pak.
Kështu që unë jam duke shtuar një tjetër bllok, vetëm të jetë i qartë.
Unë dua që ai të vinte në 90 gradë në të djathtë by default,
kështu që unë jam vetëm duke shkuar për të treguar atë për të bërë këtë programuar.
Dhe këtu ne do të shkojmë.
Ne duket se kanë bërë atë.
Është pak e çuditshme, sepse ai është duke ecur me kokë poshtë.
Le të thërrasë atë një bug.
Kjo është një gabim.
Një bug është një gabim në një program, a gabimi logjik që unë, njeriu, bërë.
Pse është ai shkon me kokë poshtë?
A MIT vidhos deri ose nuk kam?
>> Po, Unë do të thotë, kjo nuk është e MIT-së faji. Ata më dhanë një copë mister
që thotë se të kthehet disa numrin e diplomave.
Dhe në sugjerimin e Victoria-s, Unë jam kthyer 180 gradë,
që është intuita e drejtë.
Por, duke e kthyer 180 gradë fjalë për fjalë do të thotë kthim 180 gradë,
dhe kjo nuk është e vërtetë atë që unë dua, me sa duket.
Sepse të paktën ai është në kjo botë dy-dimensionale,
kështu kthese është me të vërtetë ndodh të shfletoj atë me kokë poshtë.
>> Unë ndoshta dëshironi të përdorni çfarë bllok në vend të kësaj, në bazë të asaj që ju shihni këtu?
Si mund ta fix this?
Yeah, kështu që ne mund të tregojnë në drejtimin e kundërt.
Dhe në fakt, edhe kjo është nuk do të jetë e mjaftueshme,
sepse ne vetëm mund Kodi hard për të vënë në të majtë apo të djathtë.
>> Ti e di se çfarë ne mund të bëjmë?
Ajo duket si ne kemi një bllok komoditet këtu.
Nëse unë zmadhuar, shih diçka që ne si këtu?
Pra, duket si MIT ka një Nxjerrja e ndërtuar në këtu.
Ky bllok duket të jetë e barabartë të cilat blloqe të tjera, shumësi?
>> Kjo një bllok duket të jetë e barabartë në këtë treshe të tërë të blloqeve
që ne kemi këtu.
Pra, rezulton që unë mund të lehtësuar tim program duke u shpëtoj prej të gjithë që
dhe vetëm vënë këtë në këtu.
Dhe tani ai është ende pak buggy, dhe kjo është në rregull tani për tani.
Ne do të lënë që të jetë.
Por programi im është edhe thjeshtë, dhe kjo, gjithashtu,
do të jetë përfaqësues e një qëllimi në programming--
është ideale bëjë kodin tuaj si thjeshtë, si kompakt të jetë e mundur,
ndërsa ende po si lexueshëm të jetë e mundur.
Ju nuk doni të bëni atë në mënyrë të ngjeshur se është e vështirë për të kuptuar.
>> Por vini re unë kam zëvendësuar tre blloqe me një,
dhe kjo është ndoshta një gjë e mirë.
Unë e kam përhumbur larg nocionin të kontrolluar nëse ju jeni
në buzë me vetëm një bllok.
Tani ne mund të argëtohen me këtë, në fakt.
Kjo nuk do të shtojë aq shumë vlera intelektuale por vlera e gjallë.
Unë jam duke shkuar për të shkuar përpara dhe kap këtë tingull këtu.
Pra më lejoni të shkoj përpara, dhe le të më të ndaluar programin për një moment.
Unë jam duke shkuar për të regjistruar në vijim, duke lejuar qasje në mikrofon tim.
>> Këtu ne do të shkojmë.
Ouch.
Le të provoni këtë përsëri.
Këtu ne do të shkojmë.
OK, I regjistruar gjë e gabuar.
Këtu ne do të shkojmë.
Ouch.
Në rregull.
Tani kam nevojë për të hequr qafe këtë.
Në rregull.
>> Deri tani unë kam një regjistrimi i vetëm "uf".
Kështu që tani unë jam duke shkuar për të shkuar përpara dhe e quajnë këtë "ouch".
Unë jam duke shkuar për të shkuar mbrapa për Scripts mia, dhe tani
Njoftimi ka ky bllok që është quajtur luajnë të shëndoshë "Meow" ose luaj tingull "ouch".
Unë jam duke shkuar për të drag këtë, dhe ku duhet të vënë këtë për efekt komik?
Yeah, kështu që tani kjo është lloj i buggy, sepse tani kjo block--
vini re se si kjo ", nëse në buzë, fryrje "është lloj i vetë-përmbante.
Kështu që kam nevojë për të rregulluar këtë.
Më lejoni të shkojnë përpara dhe të bëjë këtë.
Më lejoni të shpëtoj prej kësaj dhe të kthehemi të origjinalit tonë, më shumë të qëllimshme
funksionalitetin.
Pra, "nëse prekur buzë, atëherë" unë dua për ta kthyer, siç është propozuar Victoria,
180 gradë.
Dhe nuk dua të luajë të shëndoshë "ouch" atje?
>> Po, vini re se është jashtë se bllok të verdhë.
Pra, kjo, gjithashtu, do të jetë një bug, por unë kam vënë re atë.
Kështu që unë jam duke shkuar për të zvarrit atë deri këtu, dhe njoftimi tani është brenda "nëse".
Pra, "në qoftë se" është ky lloj e si njollë krah-like
që vetëm do të bëni atë që është në brendësi të saj.
Kështu që tani, nëse unë zvogëluar në rreziku i annoying--
>> COMPUTER: Ouch, ouch, ouch.
>> DAVID Malan: Dhe thjesht do të vazhdojë përgjithmonë.
Tani vetëm për të përshpejtuar gjërat këtu, më lejoni të shkoj përpara dhe të hapur,
le say-- më lejoni të shkoj për disa të stuff tim nga klasa.
Dhe më lejoni të hapur, le të themi, kjo një të bërë nga një prej shokëve tanë mësimore
nja dy vjet më parë.
Kështu që disa prej jush mund të kujtojnë kjo lojë nga kaluar,
dhe është e vërtetë e jashtëzakonshme.
Edhe pse ne kemi bërë të thjeshtë e programeve të drejtë tani,
le të shqyrtojmë se çfarë këtë në fakt duket si.
Më lejoni të goditur të luajë.
>> Pra, në këtë lojë, ne kemi një bretkocë, dhe duke përdorur arrow keys--
ai ndërmerr hapa më të mëdha se unë remember-- Unë kam kontroll mbi këtë bretkocë.
Dhe qëllimi është për të marrë të gjithë zënë Rruga pa drejtimin në makina.
Dhe le të see-- kur të shkoj deri këtu, duhet të presë për një regjistër të lëvizni nga.
Kjo duket si një bug.
Kjo është lloj i një bug.
Në rregull.
Unë jam në këtë këtu, atje, dhe pastaj ju mbani
duke shkuar deri sa ju të merrni të gjithë bretkosat në pads zambak.
Tani kjo mund të duket edhe më komplekse,
por le të përpiqemi për të thyer këtë poshtë mendërisht
dhe me gojë në blloqe që e përbëjnë.
Pra, nuk ka ndoshta një mister pjesë që ne nuk kemi parë ende
por që është duke iu përgjigjur tasteve, për gjërat që i goditi në tastierë.
>> Pra, nuk ka ndoshta një lloj bllok që thotë se, në qoftë se çelësi është e barabartë me lart,
pastaj të bëjë diçka me Scratch-- ndoshta lëvizin atë 10 hapa në këtë mënyrë.
Nëse çelësi poshtë shtypet, lëvizin 10 hapa në këtë mënyrë, ose butonin e majtë, lëvizin 10 hapa
në këtë mënyrë, 10 hapat se.
Unë e kam kthyer në mënyrë të qartë cat në një bretkocë.
Pra, kjo është vetëm kur kostum, si thirrjet Scratch arsyetimet tuaja, ne
vetëm importuar një pamje të bretkocë.
>> Por çfarë tjetër po ndodh?
Çfarë linja të tjera të kodit, atë pjesë të tjera puzzle
bënë Blake, bashkëpunëtorit tonë të mësimdhënies, përdorur në këtë program, me sa duket?
Çfarë është duke bërë çdo gjë move-- çfarë programimi ndërtuar?
>> Motion, sure-- kështu lëvizur bllok, me siguri.
Dhe çfarë është ajo block veprim brenda, ka shumë të ngjarë?
Po, një lloj lak, ndoshta një forever bllokuar, ndoshta një përsëritje block--
të përsëritur deri në bllok.
Dhe kjo është ajo që është duke e bërë shkrimet dhe pads zambak dhe çdo gjë tjetër veprim
poshtë e lart.
Është vetëm ndodh pafund.
>> Pse janë disa nga makinat lëviz më shpejt se të tjerët?
Çfarë është e ndryshme në lidhje me këto programe?
Yeah, ndoshta disa prej tyre janë duke marrë më shumë hapa në të njëjtën kohë dhe disa prej tyre
pak hapa në të njëjtën kohë.
Dhe efekti vizual është i shpejtë kundrejt ngadalshëm.
>> Çfarë mendoni ju ka ndodhur?
Kur kam marrë bretkocë tim gjatë gjithë rrugës nëpër rrugë dhe lumit
mbi jastëk lily, diçka rëndësishëm ndodhi.
Ajo që ndodhi sa më shpejt që kam bërë këtë?
Ajo u ndal.
Kjo bretkocë ndalur, dhe Kam marrë një bretkocë të dytë.
Pra, çfarë duhet të jetë konstrukt përdoret atje, çfarë veti?
>> Yeah, kështu që nuk ka një lloj "Në qoftë se" kusht deri atje, too.
Dhe kjo rezulton out-- ne nuk e shohim this-- por ka blloqe të tjera në atë vend
mund të them, nëse ju jeni të prekur një tjetër gjë në ekran,
në qoftë se ju jeni prekur pad zambak, "pastaj".
Dhe pastaj kjo është kur ne bërë bretkocë dytë shfaqet.
Pra, edhe pse kjo lojë është sigurisht shumë datë, edhe pse në shikim të parë
nuk ka aq shumë do Blake on-- dhe nuk e nxit këtë deri në dy minuta,
ajo ndoshta mori atë të disa orë për të krijuar këtë lojë
në bazë të kujtesës ose video e tij e versionit të kaluar së saj.
Por të gjitha këto gjëra të vogla ndodh në ekran në izolim
avulloj për këto shumë e thjeshtë Lëvizjet constructs-- ose deklarata
si ne kemi diskutuar, sythe dhe kushtet, dhe kjo është në lidhje.
Ka disa karakteristika të tjera njohës.
Disa prej tyre janë thjesht estetike ose akustike,
si tingujt Unë vetëm luajtur me.
Por, për pjesën më të madhe, ju kanë në këtë gjuhë, Scratch,
të gjithë themelore blloqe ndërtimi që ju
kanë në C, Java, JavaScript, PHP, Ruby, Python,
dhe çdo numër të gjuhëve të tjera.
Çdo pyetje në lidhje me Scratch?
Në rregull.
Pra, ne nuk do të zhyten në të thellë për Scratch, edhe pse ju jeni të mirëpritur këtë fundjavë,
veçanërisht në qoftë se keni fëmijë ose mbesat dhe nipërit dhe të tilla,
për futjen e tyre në Scratch.
Kjo është në fakt një mrekullisht gjallë mjedisi me, siç thonë autorët e saj,
tavanet shumë të larta.
Edhe pse kemi filluar me shumë detaje të nivelit të ulët,
ju mund të vërtetë të bëjë mjaft me të, dhe kjo është ndoshta
një demonstrim i pikërisht këtë.
>> Por tani le të kalojnë në disa më shumë probleme të sofistikuara, në qoftë se ju do të,
i njohur si "kërkim" dhe "Sorting," në përgjithësi.
Ne kishim ky libër telefoni earlier-- këtu është një tjetër vetëm për discussion--
që ne ishim në gjendje për të kërkuar më efikase për shkak se
një supozim të rëndësishëm.
Dhe vetëm të jetë i qartë, çfarë Supozimi ishte I bërë
kur të kërkoni me anë të këtij libri të telefonit?
Kjo Mike Smith ishte në libri telefonit, edhe pse unë
do të jetë në gjendje për të trajtuar skenari pa të
ka në qoftë se unë vetëm u ndal para kohe.
Libri është alfabetik.
Dhe kjo është një shumë bujar supozim, sepse kjo
do të thotë someone-- Unë jam natyrë e prerjes një qoshe,
si unë jam më i shpejtë, sepse dikush tjetër bëri një punë shumë e vështirë për mua.
>> Por, çfarë nëse telefoni Libri u Unsorted?
Ndoshta Verizon mori dembel, vetëm hodhën emrat e të gjithëve dhe numrat në atje
ndoshta në mënyrë në të cilën ata nënshkruar për shërbimin e telefonit.
Dhe sa kohë do të marrë mua për të gjetur dikë si Mike Smith?
1000 faqe telefoni book-- sa Faqet e nuk kam për të parë përmes?
>> Të gjithë ata.
Ju jeni lloj nga fat.
Ju fjalë për fjalë duhet të shikoni në çdo faqe nëse librin e telefonit është vetëm
të renditura rastësisht.
Ju mund të merrni me fat dhe për të gjetur Mike në faqen e parë, për shkak se ai
ishte i konsumatorit të parë të urdhërojë shërbimin e telefonit.
Por ai mund të ketë qenë i fundit, too.
>> Kështu mënyrë të rastit nuk është e mirë.
Pra, mendoj që ne duhet të lloj Libri i telefonit ose në të dhënat e përgjithshme e renditjes
se ne kemi qenë të dhënë.
Si mund ta bëjmë këtë?
>> E pra, më lejoni vetëm të përpiqet një shembull i thjeshtë këtu.
Më lejoni të shkojnë përpara dhe të hedh një Disa numrat në bord.
Supozoni se numrat që kemi janë, le të themi, katër, dy, një dhe tre.
Dhe, Ben, lloj këta numra për ne.
>> OK, mirë.
Si e bëre?
Në rregull.
Pra, fillojë me më të vogël vlera dhe më të lartë,
dhe kjo është me të vërtetë intuita e mirë.
Dhe të kuptojë se ne njerëzit në të vërtetë janë mjaft të
mirë në zgjidhjen e problemeve si kjo, te pakten
kur të dhënave është relativisht i vogël.
Sa më shpejt që ju të filloni të keni qindra e numrave, mijëra të numrave,
miliona numrave, Ben ndoshta nuk mund ta bëjë atë mjaft që të shpejtë,
duke supozuar se ka pasur boshllëqet në numrat.
Shumë e lehtë për të numëruar për një milion ndryshe, vetëm konsumon kohë.
>> Pra, kjo tingëllon algorithm si Ben përdorur vetëm tani
ishte kërkimi për numrin më të vogël.
Pra, edhe pse ne njerëzit mund të marrë në një shumë të informacionit me sy,
një kompjuter është në fakt pak më të kufizuar.
Kanaçe kompjuter vetëm shikoni në një byte në një kohë
ose ndoshta katër bytes në një time-- këto ditë ndoshta 8 bytes në një time--
por një numër shumë i vogël i bytes në një kohë të dhënë.
>> Pra, duke pasur parasysh se ne me të vërtetë kemi katër vlera të veçanta here--
dhe ju mund të mendoni Ben si ka pafta në qoftë se do të ishte një kompjuter i tillë
se ai nuk mund të shohin asgjë tjetër se një numër në një time--
kështu që ne në përgjithësi do të marrë, si në English, ne do të lexohet nga e djathta në të majtë.
Pra, numri i parë Ben ndoshta shikuar të ishte katër dhe pastaj shumë shpejt
e kuptoi se është një goxha i madh number-- lejoni të mbajtur në kërkim.
>> Ka dy.
Prit një minutë.
Dy është më e vogël se katër.
Unë jam duke shkuar për të kujtuar.
Dy tani është më i vogël.
Tani one-- kjo është edhe më mirë.
Kjo është edhe më të vogla.
Unë do të harrojmë për dy dhe vetëm mos harroni një tani.
>> Dhe ai mund të ndalet në kërkim?
E pra, ai mund të bazohet në këtë informacion,
por ai do kërkimin më të mirë pjesa tjetër e listës.
Sepse ajo që në qoftë se zero ishin në listë?
Çfarë ndodh nëse negative dikush në listë?
Ai vetëm e di se përgjigjen e tij është e saktë nëse ai është shteruese
kontrolluar krejt Listen.
Kështu që ne shikojmë në pjesën tjetër të kësaj.
Trete kjo ishte një humbje kohe.
Mori pafat, por unë kam qenë ende të drejtë për ta bërë këtë.
Dhe kështu që tani ai me sa duket zgjedhur numrin më të vogël
dhe vetëm vënë atë në fillim i listës, si unë do të bëj këtu.
Tani çfarë keni bërë tjetër, edhe pse ju nuk e mendoni rreth saj gati
në këtë masë?
Përsëris procesin, kështu një lloj lak.
Nuk është një ide e njohur.
Kështu që këtu është katër.
Kjo është aktualisht më i vogël.
Kjo është një kandidat.
Jo më.
Tani unë kam parë dy.
Kjo është element tjetër më i vogël.
Trete kjo nuk është më e vogël, kështu që tani Ben mund të çrrënjos dy.
>> Dhe tani ne përsëris procesin, dhe sigurisht tre merr nxorrën jashtë ardhshëm.
Përsëris procesin.
Katër merr nxorrën jashtë.
Dhe tani ne jemi jashtë numrave, kështu që lista duhet të ndahen.
>> Dhe në të vërtetë, kjo është një algoritëm formal.
Një shkencëtar kompjuteri do e quajnë këtë "lloj përzgjedhjes"
me idenë lloj a lista iteratively-- përsëri
dhe përsëri dhe përsëri përzgjedhjen numri më i vogël.
Dhe çfarë është e bukur për këtë është kjo është vetëm në mënyrë mallkuar intuitive.
Është kaq e thjeshtë.
Dhe ju mund të përsërisë të njëjtën gjë operacion përsëri dhe përsëri.
Është e thjeshtë.
>> Në këtë rast ajo ishte e shpejtë, por sa kohë e bën atë të vërtetë të marrë?
Le të bëjnë të duket dhe të të ndjehen pak më shumë i lodhshëm.
Pra, një, dy, tre, katër, pesë gjashtë, shtatë, tetë, nëntë, 10, 11, 12, 13, 14,
15, 16-- numër arbitrar.
Unë vetëm të kërkuar më shumë këtë herë se vetëm katër.
Pra, nëse unë kam marrë një e tërë bandë e numrave now-- atë
nuk ka edhe rëndësi atë që ata are---së lejojnë
mendoni se çka kjo algorithm të vërtetë është si.
>> Supozoni se ka një numër atje.
Përsëri, nuk ka rëndësi se çfarë ata janë, por ata janë të rastit.
Unë jam duke aplikuar algorithm Ben-së.
Unë kam nevojë për të zgjedhur numrin më të vogël.
Çfarë të bëj?
Dhe unë jam duke shkuar për të fizikisht të bëjë atë në këtë kohë për të vepruar atë.
Duke kërkuar, duke kërkuar, duke kërkuar, në kërkim, në kërkim.
Vetëm nga koha që kam marrë për të fundi i listës mund të
Unë të kuptojë më i vogël Numri i dy këtë herë.
Një nuk është në listë.
Kështu që unë vënë poshtë dy.
>> Çfarë të bëj tjetër?
Duke kërkuar, duke kërkuar, duke kërkuar, duke kërkuar.
Tani kam gjetur numrin shtatë, sepse ka boshllëqe në këto numbers--
por vetëm arbitrare.
Në rregull.
Deri tani unë mund të vënë poshtë shtatë.
Kërkim në kërkim, në kërkim.
>> Tani unë jam duke supozuar, i Sigurisht, që Ben nuk
kanë RAM ekstra, ekstra kujtesës, sepse, natyrisht,
Unë jam duke kërkuar në të njëjtin numër.
Po, unë mund të ketë mend të gjitha këto numra,
dhe kjo është absolutisht e vërtetë.
Por në qoftë se Ben kujton të gjithë nga numrat që ai ka parë,
ai nuk e ka bërë me të vërtetë progresi themelore
për shkak se ai tashmë ka aftësinë për të kërkuar
me numrat në bord.
Duke kujtuar të gjithë të Numrat nuk i ndihmon,
për shkak se ai ende mund të si një kompjuter vetëm shikoni në, ne kemi thënë, një numër
ne nje kohe.
Kështu që nuk ka lloj mashtrojnë atje se ju mund të levave.
>> Pra, në të vërtetë, si unë mbajtur në kërkim të listës,
Unë fjalë për fjalë duhet të vetëm të mbajë mbrapa dhe me radhë nëpërmjet saj, të nxirrnit edhe
numri i ardhshëm më i vogël.
Dhe si ju lloj i mund të konkludoj nga lëvizjet e mia pa kuptim,
kjo vetëm merr shumë lodhshëm shumë shpejt,
dhe unë duket të jetë duke shkuar prapa dhe me radhë, mbrapa dhe me radhë mjaft pak.
Tani për të qenë të drejtë, unë nuk kam për të shkuar mjaft të, mirë, le të see-- të jetë e drejtë,
Unë nuk duhet të ecin shumë si shumë hapa çdo herë.
Sepse, sigurisht, si unë zgjidhni numrat nga lista,
lista mbetur po bëhet më e shkurtër.
>> Dhe kështu që le të mendojmë për sa hapa unë jam në të vërtetë
traipsing nëpër çdo kohë.
Në situatën e parë kemi pasur 16 numra,
dhe kështu maximally-- le të vetëm e bëjnë këtë për një discussion--
Unë kisha për të parë përmes 16 Numrat për të gjetur më të vogël.
Por një herë kam shkëputur nga numri më i vogël, se si
kohë të gjatë ishte në listën e mbetur, natyrisht?
Vetëm 15.
Pra, sa numra bëri Ben, ose unë kam për të parë përmes herë të dytë rreth?
15, vetëm për të shkuar dhe për të gjetur më të vogël.
Por tani, natyrisht, lista është, Edhe më e vogël se sa ishte më parë.
Pra, si shumë hapa nuk kam duhet të marrë herën tjetër?
14 dhe pastaj 13 dhe pastaj 12, plus dot, dot, dot, deri sa unë jam duke mbetur me vetëm një.
Deri tani një shkencëtar kompjuteri do pyesin, mirë, çfarë bën që të gjithë të barabartë?
Ajo në fakt është e barabartë me një beton Numri që ne mund të sigurisht
bëjnë arithmetically, por ne duam të flasim në lidhje me efikasitetin e algoritmeve
pak më shumë formulaically, pavarur nga sa kohë lista është.
>> Dhe kështu që ju e dini se çfarë?
Kjo është 16, por si kam thënë më parë, le të vetëm thirrje madhësinë e problemit
n, ku n është një numër i.
Ndoshta është 16, ndoshta është tre, ndoshta kjo është një milion.
Une nuk e di.
Unë nuk e kujdesit.
Ajo që unë me të vërtetë dua është një formulë që unë mund të
përdorin për të krahasuar këtë algorithm kundër algoritme të tjera
që dikush mund të pretendojnë janë më të mirë ose më keq.
>> Pra, ajo rezulton, dhe vetëm unë e di këtë nga klasën e shkollës,
se ky fakt punon jashtë për të njëjtën gjë gjë si n mbi n plus një më shumë se dy.
Dhe kjo ndodh me të barabartë, të Natyrisht, n katror plus n mbi dy.
Pra, nëse kam kërkuar një formulë për mënyrën se si shumë hapa
ishin të përfshirë në kërkim në të gjitha nga ato numra përsëri dhe përsëri
dhe përsëri dhe përsëri, unë do të thoja kjo është katror n plus n mbi dy.
Por ju e dini se çfarë?
Kjo vetëm duket çrregullt.
Unë vetëm të vërtetë dëshironi një ndjenja e përgjithshme e gjërave.
Dhe ju mund të kujtojnë nga Shkolla e lartë se
është nocioni i mandatit të lartë rendit.
Cila nga këto kushte, n katror, ​​n, ose gjysmën,
ka ndikimin më kalimin e kohës?
N më e madhe merr, e cila nga këto çështje më së shumti?
>> Me fjalë të tjera, në qoftë se unë plug në një milion, n katror
do të jetë më e mundshme faktori dominues,
një milion herë, sepse në vetvete është shumë më e madhe
se plus një shtesë milion.
Kështu që ju e dini se çfarë?
Kjo është një tmerrshëm i tillë i madh Numri nëse katror një numër.
Kjo nuk ka rëndësi.
Ne jemi vetëm duke shkuar kryqin që jashtë dhe të harrojnë për të.
Dhe kështu një shkencëtar kompjuteri do të thoshte se efikasiteti i këtij algoritmi
është në rendin e n squared-- Unë do të thotë me të vërtetë një përafrim.
Ajo është katror lloj afërsisht n.
Me kalimin e kohës, aq më i madh dhe n madhe merr, kjo
është një vlerësim i mirë për atë që efikasitetit ose mungesa e efikasitetit
i këtij algoritmi të vërtetë është.
Dhe unë nxjerrin se, sigurisht, nga të vërtetë duke bërë matematikë.
Por tani unë jam vetëm duke përshëndetur duart e mia, sepse unë vetëm
duan një ndjenjë të përgjithshme të këtij algoritmi.
>> Pra, duke përdorur të njëjtën logjikë, ndërkohë, le të konsiderojmë një algoritmi
ne tashmë dukej at-- kërkim linear.
Kur isha në kërkim për book-- telefonit
jo zgjidhja atë, në kërkim përmes telefonit book--
ne kemi mbajtur duke thënë se ajo ishte 1.000 hapa, ose 500 hapa.
Por le të përgjithësojmë atë.
Nëse ka n faqe në libri telefon, çfarë është
koha running ose Efikasiteti i kërkimit lineare?
Kjo është në mënyrë të sa hapa për të gjetur
Mike Smith duke përdorur search linear, algorithm parë, apo edhe i dyti?
>> Në rastin më të keq, Mike është në fund të libri.
Pra, nëse libri telefoni ka 1.000 faqe, kemi thënë për herë të fundit, në rastin më të keq,
ajo mund të marrë afërsisht si shumë faqe për të gjetur Mike?
Like 1,000.
Kjo është një kufi i sipërm.
Kjo është një situatë e keqe e mundshme.
Por përsëri, ne jemi duke u larguar nga numra si 1000 tani.
Është vetëm n.
>> Pra, çfarë është konkluzioni logjik?
Gjetja e Mike në një telefon libër që ka faqet n
mund të marrë, në rastin më të keq shumë, sa hapa në mënyrë që të n?
Dhe në të vërtetë një kompjuter Shkencëtari do të thoshte
që në kohën drejtimin, apo në Performanca ose efikasiteti
ose joefikasiteti, të një algoritmi si një kërkim linear është në rendin e n.
Dhe ne mund të aplikojnë të njëjtën gjë Logjika e kalimit diçka jashtë
si unë vetëm e bëri të dytë algorithm kemi pasur me librin e telefonit,
ku kemi dy faqe në një kohë.
>> Pra, 1000 faqe Libri i telefonit fuqisë na merr 500 faqe kthehet, plus një
në qoftë se ne të dyfishtë përsëri pak.
Pra, nëse një libër telefoni ka faqet n, por ne jemi duke bërë dy faqe në një kohë,
kjo është afërsisht çfarë?
N mbi dy, kështu që kjo është si n mbi dy.
Por unë e bëri pretendojnë një moment më parë se n mbi two--
kjo është lloj i njëjtë si vetëm n.
Kjo është vetëm një faktor konstant, Shkencëtarët kompjuterike do të thonë.
Le të përqëndrohet vetëm në variablat, really--
variablat më të mëdha në ekuacion.
>> Kërkimi Pra linear, nëse bëhet një faqe në një kohë ose dy faqe në një kohë,
është lloj i në thelb të njëjtën gjë.
Është ende në mënyrë të n.
Por unë pohoi me foton time më parë se algoritmi i tretë nuk ishte
linear.
Kjo nuk ishte një vijë e drejtë.
Kjo ishte se vija e lakuar, dhe algjebrike formula nuk ishte ajo?
Log n-- mënyrë hyni bazë të dy të n.
Dhe ne nuk kemi për të shkuar në shumë më shumë detaje në logarithms sot,
por shumica e shkencëtarëve të kompjuterit nuk do të edhe ju them se çfarë është baza.
Për shkak se ajo është e gjitha vetëm faktorë të vazhdueshme, kështu që të flasin,
vetëm dallime të vogla numerike.
Dhe kështu që kjo do të jetë një shumë e zakonshme Mënyra për kompjuterin veçanërisht formal
shkencëtarët në një bord ose programuesit në një bord të bardhë
në fakt duke argumentuar cilat algorithm ata do të përdorin
apo çfarë efikasiteti i algorithm e tyre është.
>> Dhe kjo nuk është domosdoshmërisht diçka ju diskutuar në çdo hollësi të madhe,
por një programues i mirë është dikush i cili ka një sfond solid, formale.
Ai është në gjendje të flasin për ju në këtë lloj mënyrë
dhe në fakt të bëjë Argumentet cilësore si
pse një algorithm ose një pjesë e software
është superiore në një farë mënyre në një tjetër.
Për shkak se ju mund të me siguri vetëm të drejtuar programin e një personi
dhe të numëruar numrin e sekondave që duhet për të zgjidhur disa numra,
dhe ju mund të kandidojë disa Programi personi tjetër
dhe të numëruar numrin sekonda ajo merr.
Por kjo është një mënyrë më të përgjithshme që ju mund të përdorni për të analizuar algoritme,
në qoftë se ju do të, vetëm në letër ose vetëm me gojë.
Edhe pa drejtimin e tij, pa edhe duke u përpjekur inputeve mostër,
ju vetëm mund të arsyetojë nëpërmjet saj.
Dhe kështu me punësimin e një zhvilluesi ose nëse të paturit e tij apo të saj lloj të argumentojnë për ju
pse algorithm e tyre, sekreti i tyre Salcë për kërkimin miliarda
i faqeve të internetit për tuaj Kompania është më e mirë, këto
janë llojet e argumenteve që ideale duhet të jetë në gjendje për të bërë.
Ose të paktën këto janë të llojet e gjërave
që do të dalë në diskutim, në paktën në një diskutim shumë formale.
Në rregull.
Kështu Ben propozuar diçka quajtur përzgjedhjes lloj.
Por unë do të propozojë që ka mënyra të tjera për ta bërë këtë, too.
Ajo që unë nuk të vërtetë si në lidhje me algorithm Ben-së
është se ai e mbajti në këmbë, ose pasi eci, mbrapa dhe me radhë
dhe mbrapa dhe me radhë dhe mbrapa dhe me radhë.
Çka nëse në vend të kësaj unë do të bëj diçka si këto numra këtu
dhe unë do të vetëm të marrë me njëri- Numri i nga ana e tij që unë jam duke i dhënë atë?
>> Me fjalë të tjera, këtu është lista ime e numrave.
Katër, një, tre, dy.
Dhe unë jam duke shkuar për të bërë në vijim.
Unë jam duke shkuar për të futur numrat ku ata i përkasin në vend
sesa përzgjedhur ato një në një kohë.
Me fjalë të tjera, këtu është numri katër.
>> Këtu është lista ime origjinale.
Dhe unë jam duke shkuar për të ruajtur në thelb një listë e re këtu.
Pra, kjo është lista e vjetër.
Kjo është lista e re.
Unë po të shoh se numri katër i parë.
Lista im i ri është fillimisht bosh, kështu që është trivially rasti
se katër tani është e ndryshme listë.
Unë jam vetëm duke marrë numrin e unë jam e dhënë, dhe unë jam vënë atë në listën time të re.
>> Është renditur kjo listë e re?
Po.
Kjo është budalla, sepse nuk është vetëm një element, por është absolutisht e renditura.
Nuk ka asgjë në vendin e vet.
Është më interesante, ky algoritëm, kur unë të lëvizin për në hapin e ardhshëm.
>> Tani unë kam një të tillë.
Pra, një, natyrisht, i takon më së duke filluar ose në fund të kësaj liste të re?
Fillimi.
Kështu që unë duhet të bëni disa punë tani.
Unë kam qenë duke marrë disa liritë me shënues tim
nga vetëm duke tërhequr gjëra ku unë dua ata,
por kjo nuk është e vërtetë saktë në një kompjuter.
Një kompjuter, siç e dimë, ka RAM, ose Random Access Memory,
dhe kjo është një bajt dhe një tjetër dhe një tjetër byte byte.
Dhe në qoftë se ju keni një Gigabyte e RAM, ju keni një miliard byte,
por ata janë fizikisht në një vend.
Ju nuk mund të lëvizë gjëra rreth duke tërhequr atë në bord
ku të duash.
Pra, nëse lista ime e re ka katër vende në kujtesë,
për fat të keq katër është tashmë në vendin e gabuar.
>> Pra, për të futur numrin një Unë nuk mund të tërheqë atë këtu.
Ky vend i kujtesës nuk ekziston.
Kjo do të mashtrimit, dhe unë kam qenë mashtrimit në pikturë për disa minuta
këtu.
Pra, me të vërtetë, në qoftë se unë dua të vënë një këtu, Unë duhet të kopje përkohësisht katër
dhe pastaj të vënë atë atje.
>> Kjo është në rregull, kjo është e saktë, kjo është teknikisht e mundur,
por të kuptojë se është punë shtesë.
Unë nuk e vetëm të vënë numrin në vend.
I pari kishte për të lëvizur një numrin, pastaj të vënë atë në vend,
kështu që unë lloj i dyfishuar sasinë e mia të punës.
Pra, mbani në mend.
>> Por unë tani jam bërë me këtë element.
Tani unë dua të kap numrin tre.
Ku, sigurisht, e bën atë të takon?
Në mes.
Unë nuk mund të mashtrojnë më dhe vetëm vënë atë atje,
sepse, përsëri, ky kujtim është në vende fizike.
Kështu që unë duhet të kopjoni katër dhe të vënë tre të gjatë këtu.
Nuk është një punë e madhe.
Kjo është vetëm një hap shtesë again-- ndihet shumë e lirë.
>> Por tani unë të lëvizin për të dy.
Të dy, natyrisht, i takon këtu.
Tani ju filloni për të parë se si puna mund të grumbullohem.
Tani çfarë duhet të bëj?
Po, unë kam për të lëvizur katër, Unë pastaj duhet të kopjoni tre,
dhe tani unë mund të futni të dy.
Dhe kapur me këtë algorithm, mjaft interesant,
është se mendoj ne kemi një më ekstreme rast ku është le të themi tetë, shtatë,
gjashtë, pesë, katër, tre, dy, një.
Kjo është, në shumë kontekste, skenari më i keq,
për shkak të gjë e mallkuar është fjalë për fjalë prapa.
>> Ajo nuk ka të vërtetë ndikojnë algorithm Ben-së,
sepse në përzgjedhjen Ben-së lloj ai do të mbajë
duke shkuar mbrapa dhe me radhë nëpër lista.
Dhe për shkak se ai ishte gjithmonë në kërkim nëpër të gjithë listën e mbetur,
kjo nuk ka rëndësi ku elementet janë.
Por në këtë rast me futur tim approach-- le të provoni këtë.
>> Pra, një, dy, tre, katër, pesë, gjashtë, shtatë, tetë.
Një dy tre katër, pesë, gjashtë, shtatë, tetë.
Unë jam duke shkuar për të marrë tetë, dhe ku mund ta vënë atë?
E pra, në fillim të listës sime, sepse kjo listë e re është e renditura.
Dhe unë e kalojnë atë.
>> Ku mund të vënë shtatë?
Mallkuar atë.
Ajo ka nevojë për të shkuar atje, kështu që Unë kam për të bërë disa kopjimi.
Dhe tani shtatë shkon këtu.
Tani unë të lëvizin për në gjashtë.
Tani kjo është edhe më shumë punë.
>> Tetë ka për të shkuar këtu.
Seven ka për të shkuar këtu.
Tani gjashtë mund të shkoni këtu.
Tani unë kap pesë.
Tani tetë ka për të shkuar këtu, shtatë ka për të shkuar këtu,
gjashtë ka për të shkuar këtu, dhe tani pesë dhe të përsëritur.
Dhe unë jam shumë e shumë lëvizur atë vazhdimisht.
>> Pra, në fund, kjo algorithm-- ne do të e quajti atë futje sort-- fakt
ka shumë punë, too.
Është vetëm ndryshe lloj pune se Ben-së.
Puna Ben kishte mua në jetë mbrapa dhe me radhë të gjithë kohës,
zgjedhjen e ardhshme të vogël element përsëri dhe përsëri.
Pra, ajo ishte kjo lloj shumë vizuale të punës.
>> Kjo algorithm tjetër, e cila është ende e correct-- ajo do të marrë punë done--
vetëm ndryshon sasinë e punës.
Ajo duket si fillimisht jeni kursimit, sepse ju jeni vetëm
që kanë të bëjnë me çdo element deri para pa këmbë gjithë
rruga nëpër lista si Ben ishte.
Por problemi është, sidomos në këto Rastet e çmendur ku ajo është e gjitha prapa,
ju jeni vetëm lloj i shtyrjen e punë e vështirë
deri sa ju duhet për të rregulluar gabimet tuaja.
>> Dhe kështu që nëse ju mund të imagjinoni këtë tetë dhe shtatë dhe gjashtë dhe pesë
dhe më vonë katër dhe tre dhe dy duke lëvizur në rrugën e tyre nëpër lista,
ne kemi vetëm ndryshuar lloji i punës që po bëjmë.
Në vend të bërë atë më së fillimi i përsëritje tim,
Unë jam vetëm duke bërë atë më së Fundi i çdo përsëritje.
Pra, rezulton se këtij algoritmi, gjithashtu, në përgjithësi të quajtur futje lloj,
është gjithashtu në mënyrë të n katërkëndësh.
Kjo është në fakt më mirë, nuk ka më të mirë në të gjitha.
>> Megjithatë, ka një qasje të tretë Unë do të na inkurajojnë të marrin në konsideratë,
e cila është kjo.
Pra, mendoj listën time, për thjeshtësi përsëri, është katër, një, tre,
two-- vetëm katër numra.
Ben kishte intuitë të mirë, intuita e mirë e njeriut
më parë, me të cilin ne e fiksuar të gjithë lista eventually-- lloj futje.
I na coaxed së bashku.
Por le të marrë në konsideratë Mënyra më e thjeshtë për të rregulluar këtë listë.
>> Kjo listë nuk është e renditura.
Pse?
Në anglisht, të shpjegojë pse kjo nuk është e renditura në fakt.
Çfarë do të do të thotë të zgjidhet?
>> STUDENT: Kjo nuk është vijues.
>> DAVID Malan: Jo vijues.
Më jepni një shembull.
>> STUDENT: Vënë ato në mënyrë.
>> DAVID Malan: OK.
Më jepni një shembull më specifike.
>> STUDENT: Në ngjitje Në rendin.
DAVID Malan: Not në ngjitje qëllim.
Qenë më të saktë.
Unë nuk e di se çfarë do të thotë duke u ngritur.
Çfarë nuk shkon?
>> STUDENT: më i vogël i numra nuk është në hapësirën e parë.
>> DAVID Malan: Numri më i vogël e jo në hapësirën e parë.
Të jetë më specifik.
Unë jam duke filluar të bie në të.
Ne jemi duke numëruar, por çfarë është jashtë rendit këtu?
>> STUDENT: rend numerik.
DAVID Malan: sekuencë numerike.
lloj gjithëve të mbajtjes ajo here-- nivel shumë të lartë.
Vetëm fjalë për fjalë më tregoni se çfarë është gabuar si një fuqisë pesë-vjeçar.
>> STUDENT: Plus një.
>> DAVID Malan: Çfarë është ajo?
>> STUDENT: Plus një.
>> DAVID Malan: Çfarë do të thotë një plus?
Më jep një tjetër pesë-vjeçar.
Çfarë është e gabuar, mom?
Çfarë është e gabuar, babi?
Çfarë do të thotë kjo nuk është e renditura?
>> STUDENT: Kjo nuk është vendi i duhur.
>> DAVID Malan: Çfarë është jo në vendin e duhur?
>> STUDENT: Katër.
DAVID Malan: OK, mirë.
Pra, katër nuk është aty ku duhet të jetë.
Në veçanti, është kjo e drejtë?
Katër dhe një, i pari dy numra shoh.
A është kjo e drejtë?
Jo, ata janë jashtë funksionit, apo jo?
Në fakt, mendoj se tani në lidhje me një kompjuter, too.
Ajo mund të shikoni vetëm ndoshta një, ndoshta dy gjëra në once--
dhe në të vërtetë vetëm një gjë në një kohë, por mund të paktën
shikoni në një gjë, atëherë Gjë tjetër të drejtë tjetër për të.
>> Pra, janë këto në mënyrë?
Sigurisht që jo.
Kështu që ju e dini se çfarë?
Pse nuk kemi marrë fëmijën Hapat e ndreqim këtë problem
në vend të bërë këto dashuroj Algoritmet si Ben, ku
ai është lloj i fiksimin e tij nga looping nëpër lista
në vend të bërë atë që kam bërë, ku Unë vetëm lloji i caktuar atë si të shkojmë?
Le të vetëm të vërtetë të thyer poshtë Nocioni i rendit order-- numerike,
e quajti atë çdo gjë që ju want-- në këto krahasime pairwise.
>> Katër dhe një.
A është kjo mënyrë e saktë?
Pra, le të rregullojmë se.
One dhe katër, dhe pastaj ne vetëm do të kopje atë.
Të gjithë të drejtë, të mirë.
I fiksuar një dhe katër.
Tre dhe dy?
Jo.
Le fjalët e mia përputhen me gishtat e mi.
Katër dhe tre?
>> Kjo nuk është në rregull, kështu që unë jam duke shkuar për të bërë një, tre, katër, dy.
OK, mirë.
Tani katër dhe dy?
Ne kemi nevojë për të rregulluar këtë, too.
Kështu një, tre, dy, katër.
Pra, është ajo zgjidhet?
Jo, por është më afër të zgjidhet?
>> Kjo është, sepse ne e fiksuar këtë gabim, ne e fiksuar këtë gabim,
dhe ne e fiksuar këtë gabim.
Pra, ne fiks tre gabime ndoshta.
Ende nuk ka të vërtetë të duken renditura, por ajo është objektivisht më afër renditura
sepse ne fiksuar disa nga këto gabime.
>> Tani çfarë të bëj tjetër?
I lloj i arritur në fund të listës.
Unë duket se kanë fiksuar të gjitha gabimet, por jo.
Sepse në këtë rast, disa numra mund të ketë bubbled deri afër
me numra të tjerë që janë ende jashtë funksionit.
Pra, le të bëjë atë përsëri, dhe unë do të vetëm të bëjë atë në vend në këtë kohë.
Një dhe tre?
Kjo është në rregull.
Tre dhe dy?
Sigurisht nuk ka, kështu që le të ndryshojë këtë.
Pra dy, tre.
Tre dhe katër?
Dhe tani le të vetëm të jetë i veçanërisht pedant këtu.
A është e renditura?
Ju njerëzit e dinë se është e renditura.
>> Unë duhet të provoni përsëri.
Pra Olivia propozon I provoni përsëri.
Pse?
Për shkak se një kompjuter nuk ka luksin e syve tanë të njeriut
i vetëm glancing back-- OK, unë jam bërë.
Si e përcakton kompjuteri se lista është renditur tani?
Mekanikisht.
>> Unë duhet të kalojnë nëpër edhe një herë, dhe vetëm në qoftë se unë
nuk bëjnë / të gjejnë gabime mund të pastaj të konkludojmë si kompjuter, yep,
ne jemi të mirë për të shkuar.
Pra, një dhe dy, dy dhe tre, tre dhe katër.
Tani unë mund të them se kjo është definitivisht të renditura, sepse kam bërë asnjë ndryshim.
Tani ajo do të jetë një bug dhe vetëm qesharake në qoftë se unë, kompjuteri,
kërkuar të njëjtat pyetje përsëri duke pritur përgjigje të ndryshme.
nuk duhet të ndodhë.
>> Dhe kështu që tani lista është renditur.
Për fat të keq, duke kohën e ky algoritëm është edhe n katror.
Pse?
Sepse ju keni numrat n, dhe në rastin më të keq ju duhet të lëvizin numrat n
herë n sepse ju keni për të mbajtur vazhdim e sipër përsëri për të kontrolluar dhe potencialisht të rregulluar
këto shifra.
Dhe ne mund të bëjmë një më të Analiza formale, too.
>> Pra, kjo është e gjitha për të thënë që ne kemi marrë tre qasjet e ndryshme, një
prej tyre menjëherë intuitive off bat nga Ben
për futjen time sugjeruar lloj të këtë një
ku ju lloj i lë në harresë pyll për të pemëve fillimisht.
Por atëherë në qoftë se ju të marrë një hap prapa, voila, ne kemi fiksuar idenë klasifikim.
Pra, kjo është, guxoj të them, një nivel më të ulët, ndoshta
se disa nga ato të tjera algoritme, por le të
të shohim nëse ne nuk mund të parashikoj këto me anë të kësaj.
>> Pra, kjo është një e bukur software që dikush
shkroi përdorur bare ngjyra që është do të bëjë të mëposhtme për ne.
Secili prej këtyre bare përfaqëson një numër.
Taller bar, më e madhe numri, më i vogël bar,
më i vogël se numri.
Pra, në mënyrë ideale ne duam një piramidë të bukur ku fillon e vogël dhe merr të mëdha,
dhe kjo do të thotë se këto bare janë të renditura.
Kështu që unë jam duke shkuar për të shkuar përpara dhe të zgjedhur, për shembull, algorithm Ben
first-- lloj përzgjedhje.
>> Dhe njoftim se çfarë është bërë.
Mënyra se si ata kanë zgjedhur për të kujtoj këtë algorithm
është se, ashtu si unë kam qenë duke ecur nëpër listën time,
ky program është duke ecur me listën e saj të numrave,
theksuar në rozë çdo numër që është e kërkuar në.
Dhe çfarë është gati të ndodhë tani?
>> Numri më i vogël se I apo Ben gjetur papritur
merr zhvendos në fillim të listës.
Dhe njoftim ata kanë nxjerrë numri që ishte atje,
dhe kjo është e përkryer gjobë.
Unë nuk e kam marrë në atë nivel të detajuar.
Por ne kemi nevojë për të vënë ky numër diku,
kështu që ne vetëm u zhvendos atë në spot hapur që ishte krijuar.
Kështu që unë jam duke shkuar për të shpejtuar këtë up, sepse përndryshe ajo
bëhet shumë e lodhshme shpejt.
Animation speed-- atje ne do të shkojmë.
Deri tani njëjti parim Unë kam qenë duke aplikuar, por ju
mund të filloni të ndjeni algorithm, në qoftë se ju do, ose të parë atë një pak më qartë.
Dhe kjo algorithm ka efektin e zgjedhur elementin tjetër më të vogël,
kështu që ju jeni do të fillojë të shohin atë luftoj deri në të majtë.
Dhe në çdo përsëritje, si unë propozuar, ajo ka një punë pak më pak.
Ajo nuk duhet të shkoni të gjithë rrugën përsëri në fund e majtë të listës,
sepse ajo tashmë e di se ata janë të renditura.
Pra, kjo lloj ndjehet si ajo është përshpejtimin, edhe pse çdo hap është
duke marrë të njëjtën sasi e kohës.
Ka vetëm hapa pak mbetura.
Dhe tani ju mund të lloj të ndjehen algorithm pastrimin në fund të tij,
dhe në të vërtetë tani është e renditura.
>> Pra, futje lloj është bërë të gjithë.
Unë kam nevojë për të ri-randomize array.
Dhe vini re unë mund vetëm mbajtur randomizing atë,
dhe ne do të merrni një përafrim të qasja e njëjtë, futje lloj.
Më lejoni të ngadalësuar atë poshtë për këtu.
Le të fillojmë se mbi.
Stop.
>> Le të kaloni katër.
Atje shkojmë.
Randomize array ata.
Dhe këtu ne go-- hyrjes lloj.
Luaj.
Vini re se kjo është që kanë të bëjnë me njëri- element ajo ballafaqohet menjëherë,
por në qoftë se ajo i takon në njoftimi gabuar vendi
të gjithë punën që ka për të ndodhë.
Ne duhet të vazhdojmë të zhvendosur më shumë më shumë elemente për të bërë dhomë
për atë që ne duam të vënë në vend.
>> Pra, ne jemi duke u fokusuar në la fund vetëm listës.
Njoftim nuk kemi shikuar edhe ne at-- nuk kanë nxjerrë në pah në çdo gjë rozë
në të djathtë.
Ne jemi vetëm kanë të bëjnë me problemet si të shkojmë,
por ne jemi duke krijuar një shumë të punojnë për veten akoma.
Dhe kështu që në qoftë se ne të shpejtuar këtë ide tani për të shkuar në përfundimin,
ajo ka një të ndjehen të ndryshme në të vërtetë.
Ajo është vetëm duke u fokusuar në fund e majtë, por duke bërë një punë pak më shumë si needed--
lloj gjëra zbutjen mbi, ndreqim gjërat,
por që kanë të bëjnë në fund të fundit me çdo element në një kohë
deri sa të kemi të the-- mirë, ne të gjithë e dimë se si kjo do të përfundojë,
kështu që është një underwhelming pak ndoshta.
>> Por lista në end-- spoiler-- do të zgjidhet.
Pra, le të shohim në një të fundit.
Ne nuk mund të kaloni tani.
Ne jemi pothuajse atje.
Dy për të shkuar, në një të shkuar.
Dhe voila.
I shkelqyer.
>> Pra, tani le të bëjë një një të fundit, ri-randomizing me lloj flluskë.
Dhe vini re këtu, veçanërisht në qoftë se unë të ngadalësuar atë poshtë, kjo ka mbajtur swooping përmes.
Por vini re ai thjesht e bën pairwise lloj comparisons-- e zgjidhjeve lokale.
Por, sa më shpejt që ne të merrni për fundi i listës në rozë,
çfarë do të duhet të ndodhë përsëri?
Po, ajo do të duhet të të fillojnë të gjatë, për shkak të vetëm
gabime fikse pairwise.
Dhe kjo mund të ketë ende zbuluar të tjerët.
Dhe kështu që nëse ju të shpejtuar këtë ide, ju do të shihni se, shumë si emri nënkupton,
të vogla elements-- ose më mirë, e elements-- më të mëdha kanë filluar
të flluskë deri në krye, nëse ju do.
Dhe elementet më të vogla janë filluar të flluskë deri në të majtë.
Dhe me të vërtetë, kjo është lloj i efekti vizual si.
Dhe kështu që kjo do të përfundojë deri duke përfunduar në një mënyrë shumë të ngjashme, too.
>> Ne nuk duhet të banojë për këtë një të veçantë.
Më lejoni të hapur këtë tani, too.
Ka disa algoritme të tjera klasifikim në botë, disa prej të cilave
janë kapur këtu.
Dhe veçanërisht për nxënësit të cilët nuk janë të domosdoshmërisht vizuale apo matematikore,
siç kemi bërë më parë, ne mund të të bëjë këtë audially
nëse shoqërojnë një zë me këtë.
Dhe vetëm për argëtim, këtu është një disa algoritme të ndryshme,
dhe një prej tyre në mënyrë të veçantë ju jeni do të vini re është quajtur "bashkojë lloj."
>> Kjo është në fakt një thelb algorithm më të mirë,
të tilla që të bashkojë lloj, një nga ato ju jeni gati për të parë,
Nuk është rendi i n katror.
Kjo është në mënyrë të n herë log i n, e cila në fakt është më i vogël dhe kështu
më shpejt se ato tre të tjerë.
Dhe ka disa të tjera ato pa kuptim që ne do të shohim.
>> Pra, këtu ne do të shkojmë me një zë.
Kjo është futje lloj, kështu që përsëri kjo është vetëm që kanë të bëjnë me elementet
si ata vijnë.
Kjo është lloj flluskë, kështu që është e duke pasur parasysh ato palë në një kohë.
Dhe përsëri, elementet më të mëdha janë bubbling deri në krye.
>> Next up lloj përzgjedhje.
Kjo është algorithm Benit, ku përsëri ai është zgjedhur iteratively
element tjetër më i vogël.
Dhe përsëri, tani ju mund të vërtetë të dëgjuar se ajo është përshpejtuar, por vetëm në masën
si ajo e bërë gjithnjë e më pak punojnë në çdo përsëritje.
Kjo është aq më shpejt ai, shkrihen lloj, cila është zgjidhja grupe të numrave
së bashku dhe pastaj i kombinuar ato.
Pra look-- majtë gjysma është renditur tashmë.
>> Tani ajo është zgjidhja gjysmën e djathtë, dhe tani ajo do të kombinohen ato në një.
Kjo është diçka që quhet "Gnome lloj."
Dhe ju mund të lloj të shihni se kjo është kthim prapa dhe me radhë,
fiksimin e punë pak këtu dhe aty para se ajo vazhdon me punën e re.
Dhe kjo eshte.
Ka një tjetër lloj, e cila është me të vërtetë vetëm për qëllime akademike,
quajtur "lloj budalla", e cila merr të dhënat tuaja, llojet atë rastësisht,
dhe pastaj kontrollon nëse ajo është e renditura.
Dhe në qoftë se ajo nuk është, ajo ri-llojet it rastësisht, kontrollon nëse është e renditura,
dhe në qoftë se nuk e përsërit.
Dhe në teori, probabilistically kjo do të përfundojë,
por pas mjaft pak kohe.
Kjo nuk është më e efikas të algoritmeve.
Kështu ndonjë pyetje në ato algoritma të veçanta apo ndonjë gjë
lidhur atje, too?
>> E pra, tani le të të vë në lojë përveç atë që të gjithë këto linja janë që unë kam qenë i tërhequr
dhe atë që unë jam duke supozuar kompjuter mund të bëjë nën kapuç.
Unë do të argumentojnë se të gjitha këto numra I mbajtur drawing-- ata kanë nevojë për të marrë
ruhet diku në kujtesë.
Ne do të të hequr qafe këtë djalë tani, too.
>> Kështu që një pjesë e kujtesës në një computer-- kështu RAM DIMM është
ajo që kemi kërkuar për dje, të dyfishtë kujtesës inline module-- duket si ky.
Dhe secili prej këtyre patate të skuqura të vogla të zeza është një numër i bytes, në mënyrë tipike.
Dhe pastaj kunjat ari janë si më telat që lidhin atë në kompjuter,
dhe bordi gjelbër silic është vetëm ajo që e mban çdo gjë të gjithë së bashku.
Pra, çfarë e bën këtë të vërtetë do të thotë?
Nëse unë lloj i nxjerrë këtë të njëjtën pamje, le të supozojmë për thjeshtësi
se kjo DIMM, të dyfishtë modul memorie inline,
është një Gigabyte RAM, një Gigabyte e kujtesës, e cila është sa bytes totale?
Një Gigabyte është se si shumë bytes?
Më shumë se aq.
1,124 është kilogram, 1000.
Mega është million.
Giga është një miliard.
>> A jam i shtrirë?
A mund ta lexoni edhe etiketën?
Kjo është në fakt 128 gigabajt, kështu që është më shumë.
Por ne do të pretendojë këtë është vetëm një Gigabyte.
Pra, kjo do të thotë se ka një miliard bytes të memories në dispozicion për mua
ose 8 miliardë bit, por ne jemi duke shkuar për të folur në drejtim të bytes tani,
Duke ecur perpara.
>> Pra, çfarë do të thotë kjo është një byte, kjo është një tjetër byte,
kjo është një tjetër byte, dhe në qoftë se ne me të vërtetë të kërkuar
të jenë të veçanta që do të duhet të të nxjerrë një miliard sheshe të vogla.
Por çfarë do të thotë?
E pra, më lejoni vetëm të zmadhuar në në këtë foto.
Nëse unë kam marrë diçka që duket si kjo tani, kjo është katër bytes.
>> Dhe kështu që unë mund të vënë katër numra këtu.
Një dy tre katër.
Ose unë mund të vënë katër letra apo simbole.
"Hey!" mund të shkojnë drejtë atje, sepse secili prej letrave,
kemi diskutuar më herët, mund të përfaqësohet
me tetë bit ose ASCII ose një bajt.
Pra, me fjalë të tjera, ju mund të vënë 8 miliardë gjëra brenda
për këtë një shkop të kujtesës.
Tani çfarë do të thotë për të vënë gjërat përsëri për të mbështetur për të mbështetur në kujtesë si kjo?
Kjo është ajo që një programues do të thërrasë një "rrjet".
Në një program kompjuterik, ju nuk mendoni se në lidhje me hardware themelor, në vetvete.
Ju vetëm mendoni për veten si ka qasje në një total miliardë bytes,
dhe ju mund të çdo gjë që ju doni me të.
Por, për lehtësi kjo është në përgjithësi e dobishme
për të mbajtur të drejtën tuaj të kujtesës pranë njëri-tjetrit si kjo.
Pra, nëse unë zoom në this-- sepse ne me siguri nuk jemi duke shkuar
për të nxjerrë një miliard squares-- pak le të supozojmë se ky bord përfaqëson
që rrinë e kujtesës tani.
Dhe unë do të vetëm të tërheqë sa më shumë tim marker përfundon duke i dhënë këtu.
Deri tani ne kemi një shkop memorie në bord
që e mori një, dy, tre, katër, pesë, gjashtë, një, dy, tre, katër, pesë, gjashtë,
seven-- kështu 42 bytes memorie ne totalin sheshtë.
Faleminderit.
Po, ka aritmetikë ime e djathtë.
Pra 42 bytes e kujtesës këtu.
Pra, çfarë do të thotë kjo?
E pra, një programues kompjuteri në fakt do të në përgjithësi
mendoni për këtë kujtesës si adresueshme.
Me fjalë të tjera, çdo njëri prej tyre vende në kujtesë, në hardware,
ka një adresë unike.
>> Kjo nuk është aq komplekse sa One Brattle Square, Cambridge, Mass., 02138.
Në vend të kësaj, kjo është vetëm një numër.
Ky është numri i byte zero, kjo është një, kjo është dy, kjo është tre,
dhe kjo është 41.
Prit një minutë.
Unë mendova se tha 42 një moment më parë.
Unë fillova duke numëruar në zero, në mënyrë që është në të vërtetë e saktë.
Tani ne nuk duhet të vërtetë të nxjerrë atë si një rrjet, dhe në qoftë se ju tërheq atë si një rrjet
Unë mendoj se gjërat në fakt merrni pak mashtruese.
Çfarë një programues do, në mendjen e tij ose të saj,
në përgjithësi mendojnë për këtë kujtesës si është vetëm si një shirit,
si një copë të kasetë maskimin që vetëm vazhdon dhe përgjithmonë
ose deri sa të dalë jashtë kujtesës.
Pra, një mënyrë më të zakonshme për të nxjerrë dhe vetëm mendojnë për kujtesën
do të ishte se kjo është byte zero, një, dy, tre, dhe pastaj dot, dot, dot.
Dhe ju keni 42 bytes tilla total, edhe edhe pse fizikisht ajo mund të vërtetë
të jetë diçka më shumë si kjo.
>> Pra, nëse ju tani mendoni për tuaj kujtesës si kjo, ashtu si një shirit,
kjo është ajo që një programues përsëri do të thërrasë një grup të kujtesës.
Dhe kur të doni të vërtetë të ruajtur diçka në kujtesën e një kompjuteri,
në përgjithësi të bëjë dyqan gjëra back-to-back për back-to-back.
Pra, ne kemi qenë duke folur në lidhje me numrat.
Dhe kur unë të kërkuar për të zgjidhur problemet si katër, një, tre, dy,
edhe pse unë isha vetëm duke tërhequr vetëm numra katër, një, tre,
dy në bord, kompjuteri do të me të vërtetë kanë këtë përbërje në kujtesë.
>> Dhe çfarë do të jetë e ardhshme të dy në kujtesën e kompjuterit?
E pra, nuk ka asnjë përgjigje për këtë.
Ne vërtetë nuk e di.
Dhe për sa kohë që kompjuteri nuk ka nevojë për të,
kjo nuk duhet të kujdesen se çfarë është e ardhshëm me numrat që të bëjë kujdes në lidhje.
Dhe kur kam thënë më parë se një kompjuter mund të shohim vetëm në një adresë në një kohë,
kjo është lloj i pse.
>> Jo ndryshe nga një rekord player dhe një kokë lexim
vetëm janë në gjendje për të parë në një farë zakon në një rekord vjetër-shkollën fizike
në një kohë, në mënyrë të ngjashme mund një kompjuter në sajë
të CPU e saj dhe e saj Intel udhëzim të vendosur,
në mesin e të cilit udhëzim lexohet nga kujtesa
apo ruani në memory-- një kompjuter vetëm mund të shikojnë
në një vend në një time-- shpesh një kombinim i tyre,
por me të vërtetë vetëm një vend në një kohë.
Pra, kur ne ishim duke bërë këto algoritme të ndryshme,
Unë nuk jam vetëm me shkrim në një vacuum-- katër, një, tre, dy.
Këto shifra në fakt i përkasin diku fizike në memorie.
Pra, ka pak të vogël transistorëve ose një lloj
i elektronikës nën hood ruajtjen e këtyre vlerave.
>> Dhe në total, sa bit janë përfshirë tani, vetëm të jetë i qartë?
Pra, kjo është katër bytes, ose tani është 32 bit total.
Pra, nuk janë në fakt 32 zero dhe ato që përbëjnë këto katër gjëra.
Ka edhe më shumë gjatë këtu, por përsëri ne nuk e kujdesit në lidhje me këtë.
>> Pra, tani le të kërkojë një tjetër Pyetja duke përdorur kujtesën,
shkak që në fund e ditës është në kundërshtim.
Pa marrë parasysh se çfarë mund të bëjmë me kompjuteri, në fund të ditës
hardware është ende njëjtë nën kapuç.
Si do të ruajtur një mesazh në këtu?
E pra, një fjalë në një kompjuter si "Hey!" do të ruhen ashtu si kjo.
Dhe në qoftë se ju të kërkuar për një më të gjatë fjalë, ju thjesht mund të
prishësh atë dhe të thonë diçka si "hello" dhe dyqan se këtu.
>> Dhe kështu që këtu, gjithashtu, kjo contiguousness në fakt është një avantazh,
për shkak se një kompjuter mund vetëm lexohet nga e djathta në të majtë.
Por këtu është një pyetje.
Në kontekstin e kësaj fjale, h-e-l-l-o, pikë thirrje,
si mund kompjuteri di se ku fjala fillon dhe ku mbaron fjala?
Në kontekstin e numrave, si e bën kompjuteri
e di se sa kohë sekuencat e numrat është apo ku fillon?
E pra, ajo rezulton out-- dhe ne nuk do të shkojnë shumë
në këtë nivel të detail-- kompjutera lëvizin gjëra rreth në kujtesë
fjalë për fjalë me anë të këtyre adresave.
Pra, në një kompjuter, nëse ju jeni të shkruar kodin për të ruajtur gjërat
si fjalë, ajo që ju jeni me të vërtetë duke bërë është e shtypur
Shprehjet që të kujtuar ku në kujtesa e kompjuterit këto fjalë janë.
Pra më lejoni të bëjë një shumë, shembull shumë i thjeshtë.
>> Unë jam duke shkuar për të shkuar përpara dhe të të hapur një program të thjeshtë teksti,
dhe unë jam duke shkuar për të krijuar një file i quajtur hello.c.
Shumica e këtij informacioni ne nuk do të shkojë në në hollësi të madhe,
por unë jam duke shkuar për të shkruar një program në të njëjtën gjuhë,
C. Kjo është shumë më frikësuese, Unë do të argumentojnë, se Scratch,
por është shumë e ngjashme në frymë.
Në fakt, këto kaçurrel braces-- ju mund të lloj
të mendojnë për atë që unë vetëm e bëri pasi kjo.
>> Le ta bëjmë këtë, në të vërtetë.
Kur flamuri gjelbër klikuar, të bëjë të mëposhtme.
Unë dua të shtypura nga "hello".
Pra, kjo është tani pseudocode.
Unë jam lloj i blurring e linjave.
Në C, kjo gjuhë po flas lidhje, kjo linjë print përshëndetje
fakt bëhet "printf" me disa kllapa dhe një gjysmë-zorrës së trashë.
>> Por është e njëjta ide e saktë.
Dhe kjo shumë miqësore "Kur flamuri gjelbër klikuar" bëhet
aq shumë të më misterioze "e pavlefshme int main."
Dhe kjo me të vërtetë nuk ka asnjë hartë, kështu që unë jam vetëm duke shkuar për të injorojë atë.
Por formatimin e teksteve kaçurrel janë si copa lakuar mister si kjo.
>> Kështu që ju mund të lloj të guess.
Edhe në qoftë se ju nuk keni programuar më parë, çfarë e bën këtë program ndoshta të bëjë?
Ndoshta shtyp përshëndetje me një pikë thirrje.
>> Pra, le të përpiqemi që.
Unë jam duke shkuar për të shpëtuar atë.
Dhe kjo është, përsëri, një shumë Mjedisi vjetër e shkollës.
Unë nuk mund të klikoni, unë nuk mund të zvarritet.
Unë duhet të tipit komandat.
Kështu që unë dua të drejtuar programin tim, kështu që Unë mund ta bëjë këtë, si hello.c.
Kjo është dosja unë u zhvillua.
Por prisni, unë jam i humbur një hap.
Çfarë bëri që themi është e nevojshme hap për një gjuhë si C?
Unë kam shkruar vetëm burim Kodi, por çfarë nuk kam nevojë?
Po, kam nevojë për një përpilues.
Pra, në Mac tim këtu, unë kam një program të quajtur GCC, GNU C përpilues,
e cila lejon mua për të bërë kthesë this-- kodi im burim në, ne do të thërrasë atë,
Kodi makinë.
>> Dhe unë mund të shoh se, përsëri, si më poshtë, këto
janë zero dhe ato I vetëm krijuar nga kodin tim burim,
të gjitha zero dhe ato.
Dhe në qoftë se unë dua të drejtuar my program-- kjo ndodh
që do të quhet a.out për reasons-- historike "hello".
Unë mund të kandidojë atë përsëri.
Ckemi ckemi ckemi.
Dhe kjo duket të jetë duke punuar.
>> Por kjo do të thotë diku në tim kujtesës kompjuterit janë fjalët
h-e-l-l-o, pikë thirrje.
Dhe kjo rezulton, ashtu si një mënjanë, atë që një kompjuter do të zakonisht
të bëjë në mënyrë që ajo e di se ku gjërat fillojnë dhe end-- është e
do të vënë një simbol të veçantë këtu.
Dhe konventa është për të vënë numër zero në fund të një fjale
në mënyrë që ju e dini ku në fakt përfundon, kështu që ju
nuk mbajnë shtypjen nga gjithnjë e më shumë Karaktere se ju në fakt ndërmend.
>> Por takeaway këtu, edhe edhe pse kjo është mjaft e errët,
është se kjo është në fund të fundit relativisht e thjeshtë.
Ju janë dhënë lloj të një kasetë, një bosh Hapësira në të cilën ju mund të shkruajnë letra.
Ju thjesht duhet të ketë një simbol të veçantë, si në mënyrë arbitrare
numri zero, të vënë në fund fjalët e tua në mënyrë që kompjuteri di,
oh, unë duhet të ndalet shtypjen pas I shoh pikë thirrje.
Sepse gjë tjetër nuk është një vlerë ASCII zero,
ose karakterin null si dikush do të thërrasë atë.
Por ka lloj e një problemi këtu, dhe le të ktheheni
në numrat për një moment.
Supozoni që bëj unë, në fakt, kanë një rrjet të numrave,
dhe mendoj se program unë jam shkrim është
si një libër të keq për një mësues dhe një klasë.
Dhe ky program lejon atë ose të saj të shkruani në rezultatet e nxënësve të tyre
në kuize.
Dhe mendoj se studenti merr 100 të quiz e parë, ndoshta
si një 80 në një tjetër, pastaj një 75, pas një 90 në quiz katërt.
>> Pra, në këtë pikë në histori, array është e madhësisë së katër.
Nuk ka absolutisht më shumë memorie në kompjuter, por array, kështu që të flasin,
është e madhësisë së katër.
Supozojmë tani se mësuesi dëshiron të caktojë një quiz pestë të klasës.
E pra, një nga gjërat që ai ose ajo do të duhet të bëni
Tani është ruajtur një vlerë shtesë këtu.
Por nëse array mësuesi ka krijuar në këtë program është e madhësisë për,
një e problemit me një grup është se ju nuk mund të mbani duke shtuar në kujtesë.
Sepse ajo që në qoftë se një pjesë e Programi ka fjalën "hey" ka të drejtë?
>> Me fjalë të tjera, kujtesa ime mund të jetë përdoret për ndonjë gjë në një program.
Dhe në qoftë se më parë i shtypur në, hey, Dua të dhëna katër rezultatet quiz,
ata mund të shkoni këtu dhe këtu.
Dhe në qoftë se ju papritmas të ndryshojë mendjen tuaj më vonë dhe të thonë se unë dua një quiz pestë
Rezultati, ju nuk mund vetëm të vënë atë kudo që ju dëshironi,
sepse ajo që në qoftë se ky memorie është duke u përdorur
për diçka else-- ndonjë program tjetër ose ndonjë veçori tjetër të programit
që ju jeni duke?
Kështu që ju duhet të mendoni më parë si ju doni të ruajtur të dhënat tuaja,
sepse tani ju keni pikturuar veten në një qoshe dixhitale.
>> Kështu një mësues fuqi në vend thonë se kur shkruani një program
për të ruajtur tij ose të saj notat, ju e dini se çfarë?
Unë jam duke shkuar për të kërkuar, kur shkruani programin tim,
që unë dua zero, një, dy, tre, katër, pesë, gjashtë, tetë notat totale.
Pra, një, dy, tre, katër, pesë, gjashtë, shtatë, tetë.
Mësuesi mund të pak më shumë, të ndajë kujtesës kur shkrim programin e tij ose të saj
dhe thonë se, ju e dini se çfarë?
Unë kurrë nuk do të caktojë më shumë se tetë kuize në një semestër.
Kjo është vetëm i çmendur.
Unë kurrë nuk do të ndajë atë.
Kështu që në këtë mënyrë ai ose ajo ka të fleksibilitet për rezultatet dyqan të studentëve,
si 75, 90, dhe ndoshta një shtesë, ku studenti marrë kredi shtesë, 105.
>> Por në qoftë se nuk mësuesi përdor këto tre hapësira,
ka një takeaway intuitive këtu.
Ai ose ajo është vetëm humbur hapësirë.
Pra, me fjalë të tjera, nuk është kjo tradeoff zakonshme në programimin
ku ju mund të ndajë pikërisht sa më shumë kujtesa sa të doni,
me kokë e të cilit është se ju jeni super efficient-- ju nuk jeni duke u kota
në all-- por downside i të cilave është ajo që në qoftë se ju të ndryshojë mendjen tuaj kur
duke përdorur programin që ju dëshironi për të ruajtur më shumë të dhëna se sa ju menduar fillimisht.
>> Pra, ndoshta zgjidhja është, atëherë, shkruajnë programet tuaja në mënyrë të tillë
që ata përdorin më shumë memorie se ata në të vërtetë kanë nevojë.
Në këtë mënyrë ju nuk do të jeni për të kandiduar në këtë problem,
por ju jeni duke u kota.
Dhe më shumë memorie programi juaj përdor, siç kemi diskutuar dje, më pak
kujtesës që është në dispozicion për programe të tjera,
aq më shpejt kompjuteri juaj mund të ngadalësojë poshtë për shkak të kujtesës virtuale.
Dhe kështu zgjidhje ideale mund të jetë ajo?
>> Nën-ndarjes duket e keqe.
Over-ndarjes duket e keqe.
Pra, çfarë mund të jetë një zgjidhje më të mirë?
Rishpërndarë.
Të jetë më dinamike.
Mos i detyroni veten për të zgjedhur një priori, në fillim, atë që ju dëshironi.
Dhe sigurisht nuk mbi-ndajë, përndryshe do të kota.
>> Dhe në mënyrë që të arritur këtë qëllim, ne nevojë për të hedhur këtë strukturë të dhënave,
mënyrë që të flasin, larg.
Dhe kështu që ajo që një programues do të përdorë në mënyrë tipike
është diçka që nuk është një i quajtur array por një listë e lidhur.
Me fjalë të tjera, ai ose ajo do fillojnë të mendojnë për kujtesën e tyre
si qenë lloj i një formë që ata mund të tërheqë në këtë mënyrë.
Nëse unë dua të ruajtur një numër në një program-- kështu që është e shtator
Unë e kam dhënë nxënësit e mi një quiz; unë dua për të ruajtur quiz e parë e studentëve,
dhe ata patën një 100 në I arsyetimet tuaja, jam duke shkuar për të kërkuar kompjuterin tim,
me anë të programit që kam shkruar, për një copë e kujtesës.
Dhe unë jam duke shkuar për të ruajtur Numri 100 në të, dhe kjo është ajo.
>> Pastaj disa javë më vonë kur unë të marrë quiz time të dytë,
dhe është koha për të tipit në atë 90%, Unë jam duke shkuar
për të kërkuar kompjuterin, hej, kompjuter, mund të ketë një copë e kujtesës?
Ajo do të më jepni këtë copë bosh e kujtesës.
Unë jam duke shkuar për të vënë në numrin 90, por në programin tim disi ose other--
dhe ne nuk do të shqetësohen për sintaksa për this-- kam nevojë për
në një farë mënyre zinxhir këto gjëra së bashku.
Dhe unë do zinxhir e tyre së bashku me atë që duket si një shigjetë këtu.
>> Kuizi i tretë që vjen, Unë jam duke shkuar për të thënë, hej, kompjuter,
më jepni një copë e kujtesës.
Dhe unë jam duke shkuar për të vënë poshtë çfarëdo qoftë ajo ishte, si 75,
dhe unë duhet të zinxhirit të këtij së bashku tani disi.
quiz katërti vjen së bashku, dhe ndoshta kjo është nga fundi i semestrit.
Dhe deri në atë pikë të programit tim mund të jetë duke përdorur kujtesën
në të gjithë vendin, të gjithë fizikisht.
Dhe kështu vetëm për shkelma, unë jam i do të nxjerrë këtë radhë
quiz-- harroj se çfarë ishte; unë mendoj se ndoshta një 80 ose something--
Mënyra këtu.
>> Por kjo është në rregull, sepse në pikturë Unë jam duke shkuar për të tërhequr këtë linjë.
Me fjalë të tjera, në të vërtetë, në hardware e kompjuterit tuaj,
i pari rezultatin e fuqisë përfundojnë këtu, sepse kjo është
të drejtë në fillim të semestrit.
Një tjetër mund të përfundojë këtu sepse pak kohe ka kaluar
dhe programi mban drejtimin.
Rezultati i ardhshëm, i cili ishte një 75, mund të jetë këtu.
Dhe rezultati i fundit mund të jetë një 80, i cili është këtu.
>> Pra, në të vërtetë, fizikisht, kjo mund të jetë ajo memorie kompjuteri juaj duket si.
Por kjo nuk është një mendore dobishme paradigmë për një programues kompjuteri.
Pse duhet të keni kujdes kur dreq dhënat tuaja është duke përfunduar?
Ju thjesht doni të ruajtur të dhënat.
>> Kjo është lloj i si diskutimit tonë më parë i tërhequr kubike.
Pse nuk ju intereson se çfarë kënd është i kubike
dhe se si ju duhet të kthehet për të nxjerrë atë?
Ju vetëm dëshironi një kubike.
Në mënyrë të ngjashme këtu, ju vetëm dua të librit të klasës.
Ju thjesht doni të mendoni për këtë si një listë të numrave.
Kush kujdeset se si është e implementuar në hardware?
>> Pra abstraksion tani është kjo foto këtu.
Kjo është një listë e lidhur, si një programues do të thërrasë atë,
për aq kohë sa ju keni një Lista, padyshim e numrave.
Por kjo është e lidhur në pikturë me anë të këtyre shigjetave,
dhe të gjitha këto shigjeta are-- poshtë individualitet, në qoftë se ju jeni kurioz,
kujtojnë se hardware tonë fizike ka Adresat zero, një, dy, tre, katër.
Të gjitha këto shigjetat janë është si një hartë ose drejtime, ku në qoftë se 90 is-- tani
I kam për të numëruar.
>> Zero, një, dy, tre, katër, pesë, gjashtë, shtatë.
Ajo duket si 90 është në Adresa e kujtesës numri shtatë.
Të gjitha këto shigjetat janë është si një copëz të vogël letre
që është duke i dhënë udhëzime të program që thotë se ndjekin këtë hartë
për të marrë në vendin e shtatë.
Dhe aty ju do të gjeni Rezultati quiz dytë nxënësit.
Ndërkohë, 75-- në qoftë se unë vazhdoj këtë, kjo është shtatë, tetë, nëntë, 10, 11, 12,
13, 14, 15.
>> Kjo shigjetë tjetër vetëm të perfaqeson një hartë të vendndodhjes së kujtesës 15.
Por përsëri, programues në përgjithësi nuk nuk e kujdesit në lidhje me këtë nivel të detajuar.
Dhe në shumicën çdo programim gjuha sot, programues
nuk do e di edhe ku në kujtesë këto numra të vërtetë janë.
Të gjitha ai ose ajo ka të intereson është që ato janë të lidhura bashkë diku
në një strukturë të dhënave si kjo.
>> Por kjo rezulton jo për të marrë shumë teknike.
Por vetëm për shkak se ne mund të ndoshta përballojë që të ketë këtë diskutim këtu,
mendoj se ne sërish kjo çështje këtu për një grup.
Le të shohim nëse ne vjen keq ndodh këtu.
Kjo është 100, 90, 75, dhe 80.
>> Më lejoni të bëj shkurtimisht këtë pohim.
Ky është një grup, dhe një herë, karakteristikë e spikatur e një grup
është se të gjitha të dhënat tuaja është kthyer në të kthyer prapa në memory-- fjalë për fjalë
një byte ose ndoshta katër bytes, disa numër të caktuar të bytes larg.
Në një listë të lidhura, të cilat ne mund të tërheqë si kjo, nën kapuç që
e di se ku stuff është?
Ajo nuk ka nevojë edhe për të rrjedhin si kjo.
Disa prej të dhënave mund të jetë përsëri në të majtë deri atje.
Ti nuk e di edhe.
>> Dhe kështu me një grup, ju keni një tipar i njohur si qasje të rastit.
Dhe çfarë do të thotë qasje të rastit është se kompjuteri mund të kërcejnë në çast
për çdo vend në një rrjet.
Pse?
Sepse kompjuteri e di se vendi i parë është
zero, një, dy, tre.
>> Dhe kështu që nëse ju doni të shkoni nga ky element me elementin tjeter,
ju fjalë për fjalë, në Mendja kompjuterit, vetëm të shtoni një të tillë.
Nëse ju doni të shkoni në elementin e tretë, vetëm të shtoni one-- element tjetër, vetëm
shtoni një të tillë.
Megjithatë, në këtë version i tregimit, mendoj
kompjuteri është aktualisht në kërkim në ose trajtimin me numrin 100.
Si mund të merrni për të ardhshëm klasën në librin e klasës?
>> Ju keni për të marrë shtatë hapa, e cila është arbitrare.
Për të marrë në një tjetër, ju duhet të marrë edhe tetë hapa për të marrë për të 15.
Me fjalë të tjera, kjo nuk është një hendeku i vazhdueshëm midis numrave,
dhe kështu ajo vetëm merr kompjuter shumë kohë është pika.
Kompjuter ka për të kërkuar nëpërmjet kujtesës në mënyrë
për të gjetur atë që ju po kërkoni.
>> Pra, ndërkohë që një grup tenton të jetë një të dhënat e shpejtë structure--, sepse ju
mund të vërtetë vetëm të bëjë aritmetikë të thjeshtë dhe për të marrë ku ju doni duke shtuar një të tillë,
për instance-- një listë e lidhur, ju sakrifikojë atë funksion.
Ju nuk mund të shkojnë nga e para të dytë të tretë për të katërt.
Ju duhet të ndjekin hartë.
Ju duhet të marrë më shumë hapa për të marrë në ato vlera, të cilat
do të duket të jetë duke shtuar një kosto.
Pra, ne jemi duke paguar një çmim, por ajo që ishte tipar që Dan po kërkon këtu?
Çfarë bën një listë të lidhur duket të na lejojë për të bërë,
e cila ishte origjina e kjo histori të veçantë?
>> Pikërisht.
Një madhësi dinamike të.
Ne mund të shtoni në këtë listë.
Ne edhe mund të tkurret listën, kështu se ne jemi vetëm duke përdorur sa më shumë memorie
si ne të vërtetë duan dhe kështu ne nuk jemi mbi-ndarjen e.
>> Tani vetëm të jetë me të vërtetë NIT-picky, ka një kosto të fshehura.
Pra, ju nuk duhet vetëm të më lejoni të bindë ju se kjo është një tradeoff bindëse.
Ka një kosto të fshehura këtu.
Përfitimi, të jetë i qartë, është që ne të merrni dinamizëm.
Nëse unë dua një element tjetër, unë mund vetëm të tërheqë atë dhe të vënë një numër në atje.
Dhe atëherë unë mund të lidhë atë me një foto këtu,
ndërsa këtu, përsëri, në qoftë se unë kam pikturuar veten në një qoshe,
në qoftë se diçka tjetër është tashmë duke përdorur kujtesës këtu, unë jam nga fat.
Unë kam pikturuar veten në qoshe.
>> Por ajo që është e fshehur kosto në këtë foto?
Kjo nuk është vetëm shuma të kohës që merr
për të shkuar nga këtu për këtu, që është shtatë hapa, atëherë
tetë hapa, që është më shumë se një.
Çfarë është një kosto të fshehura?
Jo vetëm koha.
Informata shtesë është nevojshme për të arritur këtë foto.
>> Yeah, se harta, ato scraps pak të letër, si unë mbaj duke i përshkruar ato si.
Këto arrows-- ata që nuk janë të lirë.
A computer-- ju e dini atë që një kompjuter ka.
Ajo ka zero dhe ato.
Nëse ju doni për të përfaqësuar një shigjetë ose një hartë ose një numër, ju keni nevojë për disa kujtesës.
Pra, çmimi tjetër të paguajnë për një listë të lidhura,
një shkencë të përbashkët kompjuterike burimeve, është edhe hapësira.
>> Dhe me të vërtetë kështu, në mënyrë zakonisht, në mesin e tradeoffs
në hartimin inxhinieri software sistemeve është koha dhe space--
janë dy nga përbërësit tuaj, dy e përbërësve tuaj më të kushtueshme.
Kjo kushton më shumë kohë sepse unë kam për të ndjekur këtë hartë,
por është edhe kushton më shumë hapësirë sepse unë kam për të mbajtur këtë hartë përreth.
Kështu ka shpresë, pasi ne kemi lloj biseduar për dje dhe sot,
është se përfitimet do të jenë më të mëdha shpenzimet.
>> Por nuk ka asnjë zgjidhje e qartë këtu.
Ndoshta kjo është better-- një të shpejtë dhe të pista la,
si Kareem propozuar earlier-- për të hedhur kujtesës në problem.
Vetëm për të blerë më shumë memorie, mendoni pak e vështirë për zgjidhjen e problemit,
dhe të zgjidhur atë në një mënyrë më të lehtë.
Dhe në të vërtetë më parë, kur kemi biseduar për tradeoffs,
ajo nuk ishte në hapësirë kompjuter dhe koha.
Kjo ishte koha zhvilluesi i saj, i cili është edhe një burim.
>> Pra, përsëri, është ky akt balancues duke u përpjekur për të vendosur se cilat nga ato gjëra
jeni të gatshëm për të shpenzuar?
E cila është më pak e shtrenjtë?
E cila jep rezultate më të mira?
Po?
>> Me të vërtetë.
Në këtë rast, në qoftë se ju jeni përfaqësojnë numrat në maps--
këto janë quajtur në shumë gjuhë "pointers" ose "adresa" -
është e dyfishtë hapësirë.
Kjo nuk duhet të jetë aq e keqe sa të dyfishtë nëse tani ne jemi vetëm ruajtjen numra.
Supozoni se ne kemi qenë të ruajtur të dhënat e pacientit në një hospital--
kështu që emrat Pierson së, numrat e telefonit, numrat e sigurimeve shoqërore, mjeku
histori.
Kjo kuti mund të jetë shumë, shumë më të madhe, në të cilin rast
një tregues i vogël pak, adresa e tjetër element-- kjo nuk është një punë e madhe.
Kjo është një periferi e tillë kosto kjo nuk ka rëndësi.
Por në këtë rast, po, kjo është një dyfishim.
Pyetje e mirë.
>> Le të flasim për kohë të a pak më konkretisht.
Çfarë është koha running e kërkimit në këtë listë?
Mendoj unë të kërkuar për të kërkuar nëpër të gjitha notat e nxënësve,
dhe nuk ka nota n në këtë strukturë të të dhënave.
Këtu, gjithashtu, ne mund të marrë hua fjalori i parë.
Kjo është një strukturë e të dhënave linear.
>> O i madh i n është ajo që është e nevojshme për të marrë deri në fund të kësaj strukture të dhënave,
whereas-- dhe ne nuk e kemi parë kjo më herët, një grup ju jep
atë që quhet koha e vazhdueshme, që do të thotë një hap ose dy hapa ose 10 steps--
nuk ka rëndësi.
Është një numër i caktuar.
Ajo nuk ka të bëjë me madhësia e array.
Dhe arsyeja për këtë, përsëri, është e gjallë.
Kompjuter mund vetëm menjëherë hidhen në një vend tjetër,
për shkak se ata janë të gjithë të njëjtën gjë Distanca nga çdo gjë tjetër.
Nuk ka asnjë mendim të përfshira.
Në rregull.
Pra, nëse unë mund të, më lejoni të përpiqet të pikturuar dy fotografi përfundimtare.
Një njeri shumë i zakonshëm i njohur si një tabelë hash.
Pra, për të motivuar këtë diskutim, më lejoni të mendoj se si ta bëni këtë.
>> Pra, si në lidhje me këtë?
Supozoni se problemi ne duam të zgjidhim tani
është zbatuar në një dictionary-- kështu që një bandë e tërë e fjalëve angleze
apo çfarëdo.
Dhe qëllimi është që të jetë në gjendje për t'iu përgjigjur pyetjet e formularit është kjo një fjalë?
Pra, ju doni për të zbatuar një checker magji, vetëm
si një fjalor fizike që ju mund të shikoni gjërat në.
Mendoj unë do të bëj këtë me një grup.
Unë mund ta bëjë këtë.
>> Dhe mendoj se fjalët janë apple dhe banane dhe pjepër.
Dhe unë nuk mund të mendoj e frutave që të fillojë me d, kështu që ne jemi vetëm
do të ketë tre fruta.
Kështu që kjo është një grup, dhe ne jemi magazinimin e të gjitha këto fjalë
në këtë fjalor, si një grup.
Pyetja, pra, është se si të tjerët mund ta ruajë këtë informacion?
>> E pra, unë jam lloj i mashtrimit këtu, sepse secila nga këto letra në fjalë
është me të vërtetë një bajt individual.
Pra, nëse unë me të vërtetë donte të jetë lajthi-picky, unë duhet të vërtetë
të duke e ndarë këtë ide në shumë chunks vogla e kujtesës,
dhe ne mund të bëjë pikërisht këtë.
Por, ne jemi duke shkuar për të kandiduar në të njëjtin problem si më parë.
Po në qoftë se, si Merriam Webster apo Oxford bën çdo year-- ata shtojnë fjalët
të dictionary-- ne nuk domosdoshmërisht duan të pikturoj veten
në një qoshe me një grup?
>> Pra, në vend, ndoshta një qasje të zgjuar është për të vënë mollë në nyje e vet apo kuti,
si ne do të themi, banane, dhe atëherë këtu kemi pjepër.
Dhe ne string këto gjëra së bashku.
Pra, kjo është array, dhe kjo është lista e lidhur.
Nëse ju nuk mund të mjaft të shohim, ajo vetëm thotë se "array", dhe kjo thotë se "listë."
>> Pra, ne kemi të njëjtën gjë Çështjet e saktë si më parë,
anë të të cilit tani kemi Dinamizmi në listën tonë të lidhura.
Por ne kemi një fjalor mjaft të ngadalshëm.
Mendoj unë doni të shikoni një fjalë.
Ajo mund të marrë mua O të madhe të n hapa, sepse fjala e fuqisë
të jenë të gjithë rrugën në fund lista, si pjepër.
Dhe kjo rezulton se në programimin, lloj
e Grail shenjtë e të dhënave strukturave, është diçka
që i jep të vazhdueshme kohë si një grup
por që ende ju jep dinamizëm.
>> Kështu që mund të kemi më të mirë të të dy botëve?
Dhe me të vërtetë, nuk është diçka quhet tabela hash
që ju lejon të bëni pikërisht që, edhe pse përafërsisht.
Një tabelë hash është një njohës Struktura e të dhënave që ne
mund të mendoni si Kombinimi i një array--
dhe unë jam duke shkuar për të nxjerrë atë si this-- dhe listat e lidhura
që do të marr si kjo këtu.
>> Dhe mënyra kjo gjë vepra është si më poshtë.
Nëse kjo now-- hash table-- është struktura e ime e tretë e të dhënave,
dhe unë dua për të ruajtur fjalët në këtë, unë nuk
duan të vetëm të ruajtur të gjitha të fjalë për të kthyer prapa për të mbështetur prapa.
Unë dua të levave disa pjesë e informacionit
për fjalët që do të lejojnë me të marrë atë aty ku është e shpejtë.
>> Pra, duke pasur parasysh fjalët mollë dhe banane dhe pjepër,
Unë qëllimisht zgjodhi këto fjalë.
Pse?
Çfarë është lloj krejtësisht ndryshme në lidhje me tre?
Çfarë është e qartë?
Ato fillojnë me shkronja të ndryshme.
>> Kështu që ju e dini se çfarë?
Në vend se të vënë të gjitha fjalët e mia në e njëjta kovë, kështu që të flasin,
si në një listë të madhe, pse nuk e bëjmë Unë të paktën të përpiqet një optimization
dhe të bëjë listat e mia 1/26 sa kohë.
A optimization bindëse mund të jetë pse nuk e bëjmë
I-- kur futur një fjalë në këtë strukturë të të dhënave,
në kujtesën e kompjuterit, pse nuk e kam vënë të gjitha 'një' fjalë e këtu,
të gjithë 'b' fjalë këtu, dhe të gjithë "c" fjalët e këtu?
Pra, kjo përfundon duke vënë një mollë këtu, banane këtu, pjepër këtu,
dhe kështu me radhë.
>> Dhe në qoftë se unë kam një shtesë fjala like-- çfarë është tjetër?
Apple, banane, dardhë.
Çdokush mendojnë për një fruta që fillon me a, b, ose c?
përsosur Blueberry--.
Që do të përfundojnë këtu.
Dhe kështu që ne duket se kanë një pak zgjidhje më të mirë,
sepse tani në qoftë se unë dua për të kërkuar për mollë, unë
first-- Unë nuk e vetëm pikiatë në strukturën e mia e të dhënave.
Unë nuk zhyten në kujtesën e kompjuterit tim.
I pari shikoni në letrën e parë.
>> Dhe kjo është ajo që një kompjuter Shkencëtari do të thonë.
Ju hash në strukturën tuaj të të dhënave.
Ju merrni kontributin tuaj, e cila në ky rast është një fjalë si mollë.
Ju analizuar atë, duke kërkuar në letra e parë në këtë rast,
duke hashing atë.
Hashing është një term i përgjithshëm, ku ju merrni diçka si input
dhe të prodhojë disa dalje.
Dhe prodhimi në atë Rasti është vend
ju doni të kërkoni, i pari vendndodhja, vendndodhja e dytë, të tretë.
Pra input është molla, prodhimi është i pari.
Input është banana, Prodhimi duhet të jetë të dytë.
Input është pjepër, prodhimi duhet të jetë i treti.
Input është boronice, Prodhimi përsëri duhet të jetë të dytë.
Dhe kjo është ajo që ju ndihmon të merrni shkurtesat përmes kujtesën tuaj
në mënyrë që të merrni në fjalë ose të dhëna në mënyrë më efikase.
>> Tani kjo shkurtimet e poshtë kohën tonë potencialisht nga sa më shumë që një në 26,
sepse në qoftë se ju të supozojmë se ju ketë sa më shumë "një" fjalë si "z"
Fjalët si fjalët "q", e cila nuk është me të vërtetë realistic--
ju jeni do të ketë anuar gjithë shkronja të caktuara të alphabet--
por kjo do të ishte një rritje qasje që lejon
që ju të merrni për fjalë shumë më shpejt.
Dhe në të vërtetë, një të sofistikuar programit, Googles i botës,
Facebooks e world-- ata do të përdorin një tabelë hash
për shumë qëllime të ndryshme.
Por ata nuk do të jetë aq naiv sa për të vetëm shikoni në letrën e parë
në mollë ose banane, ose dardhë apo pjepër,
sepse si ju mund të shihni këto Listat ende mund të marrë kohë të gjatë.
>> Dhe kështu kjo mund të jetë ende një lloj e linear-- kështu lloj i ngadalshëm,
si me O të madhe të n që kemi diskutuar më parë.
Pra, çfarë një tabelë të vërtetë të mirë hash do do-- ajo do të ketë një rrjet shumë më të madhe.
Dhe kjo do të përdorë një shumë më të Funksioni i sofistikuar hashing,
në mënyrë që ajo nuk ka vetëm të shikoni në "a".
Ndoshta shikon "a-p-p-l-e" dhe disi konverton ato pesë letra
në vendin ku apple duhet të ruhen.
Ne jemi vetëm naivitet duke përdorur letër 'a' vetëm, sepse ajo është e bukur dhe të thjeshtë.
>> Por një tabelë hash, në në fund, ju mund të mendoni
si një kombinim i një grup, secila prej të cilave
ka një listë të lidhur që në mënyrë ideale duhet të jetë sa më e shkurtër.
Dhe kjo nuk është një zgjidhje e qartë.
Në fakt, pjesa më e madhe akordim gjobë që shkon në nën kapuç kur është
zbatimin e këtyre llojeve të struktura të sofistikuara të dhënave
është ajo që është e drejtë gjatësia e vektorit?
Cili është funksioni i duhur hash?
Si mund të ruajtur gjërat në kujtesë?
>> Por e kuptojnë se sa shpejt ky lloj i diskutimit
shkallëzua, ose deri më tani që kjo është lloj e mbi kokën e dikujt në këtë pikë, e cila
është e mirë.
Por kemi filluar, risjell, me të vërtetë diçka e nivelit të ulët dhe elektronike.
Dhe kështu kjo përsëri është ky Tema e abstraksionit,
ku sapo ju filloni për të marrë për dhënë, OK, unë kam marrë arsyetimet tuaja, nuk ka
kujtesës fizike, OK, e mori atë, çdo vendndodhjen fizike ka një adresë,
OK, kam marrë atë, unë mund të përfaqësojë ato adresat si arrows--
ju mund shumë shpejt të fillojë të ketë Bisedat më të sofistikuara se
në fund duket të jetë na lejuar për të zgjidhur probleme si në kërkim
dhe zgjidhja më efikase.
Dhe pjesa tjetër e siguroi, too-- sepse unë mendoj se kjo
është më e thellë që kemi shkuar në disa nga këto tema CS proper-- ne kemi
bëhet në një ditë e gjysmë në këtë tregojë se çfarë ju mund të bëni në mënyrë tipike gjatë
kursi i tetë javë në një semestër.
>> Çdo pyetje mbi këto?
Nuk ka?
Në rregull.
E pra, pse nuk ndalemi atje, fillojnë drekë disa minuta në fillim,
rinisë në vetëm rreth një orë?
Dhe unë do të zgjatem për pak me pyetje.
Atëherë unë jam duke shkuar për të duhet të shkojnë të marrë një thirrje çift nëse kjo është në rregull.
Unë do të kthehet në disa muzikë në ndërkohë, por dreka duhet të jetë rreth qoshe.