>> DAVID Malan: Labi.
Mēs esam atpakaļ.
Tātad šajā segmentā par programmu, kas Es domāju, mēs gribētu darīt, ir sajaukums lietas.
Viens, darīt mazliet kaut hands-on,
lai gan, izmantojot vairāk rotaļīgu programmēšana environment--
viens, kas ir uzskatāms par tieši veidiems ideju
mēs esam runājuši par, bet nedaudz vairāk formāli.
Divi, apskatīt dažus no jo vairāk tehniskie veidi
ka programmētājs faktiski atrisināt problēmas, piemēram, meklētājas problēmu
ka mēs paskatījās pirms un arī plašākā skatījumā
interesanta problēma šķirošanu.
>> Mēs tikko pieņemts no get iet ka tālruņu grāmata tika sakārtoti,
bet tas vien ir faktiski sava veida grūti problēma ar daudz dažādos veidos
atrisināt to.
Tāpēc mēs izmantot tos kā klases problēmas
pārstāvis lietām, kas varētu atrisināt vispār.
Un tad mēs runājam par samērā detalizēti, ko
sauc datu structures-- mīļotājs veidos, piemēram, saistītas saraksti
un jaucējtabula un koki, kas programmētājs faktiski
izmantot un parasti izmanto uz tāfeles gleznot
priekšstatu par to, ko viņš vai viņa iedomājas īstenošanas
daži gabals programmatūru.
>> Tātad, pieņemsim do roku-on daļu pirmās.
Tik vienkārši saņemt rokas netīras ar vide sauc scratch.mit.edu.
Tas ir instruments, kas mēs izmantojam mūsu bakalaura klasē.
Pat ja tas ir paredzēts par vecumu 12 un uz augšu,
mēs to izmantot, lai uz augšu daļa no šīs diezgan daudz
jo tas ir jauki, jautri grafiskā veidā mācīšanās
nedaudz kaut ko par programmēšanu.
Tāpēc dodies uz šo URL, kur jums vajadzētu redzēt lapu gluži kā šis,
un iet uz priekšu un noklikšķiniet Pievienojies Scratch pie augšējā labajā stūrī
un izvēlēties lietotājvārdu un parole un galu galā iegūt sev
account-- scratch.mit.edu.
Es domāju, es gribētu izmantot šo kā iespēja pirmo reizi parādīt to.
Jautājums nāca klajā pārtraukumā par to, ko kods tiešām izskatās.
Un mēs runājām Pārtraukumā par C laikā,
in particular-- īpaši zemāks līmenis vecāku valodā.
Un es tikko bija ātri Google meklēšanu, lai atrastu C kodu
bināro meklēšanu, algoritmu, kas mums izmanto, lai meklētu šo telefona grāmatu agrāk.
Šis konkrētais piemērs, protams, nav meklēt tālruņa grāmatu.
Tas tikai meklē visu ķekars numurus datora atmiņā.
Bet, ja vēlaties, lai tikai iegūt vizuāli sajūtu, ko faktisko plānošanu
valoda izskatās, tas izskatās mazliet kaut kas līdzīgs šim.
Tātad, tas ir par 20-plus, 30 vai tik koda rindiņas,
bet saruna mums bija, kam pāri pārtraukuma
bija par to, kā tas patiesībā izpaužas morphed nullēm un uzņēmumiem
un, ja jūs varat ne tikai atgriezties ka apstrādāt un aiziet no nullēm un uzņēmumiem
atpakaļ uz kodu.
>> Diemžēl šis process ir tik pārveidojoša
ka tas ir daudz vieglāk pateikt, nekā izdarīt.
Es devos uz priekšu un faktiski pagriezās ka programma, Binary Search,
uz nullēm un tiem Izdarot programmu, ko sauc kompilators, ka es
gadīties, ka šeit tieši par manu Mac.
Un, ja paskatās uz ekrāna šeit, jo īpaši koncentrējoties
uz šīm vidējām sešām kolonnām tikai, jūs redzēsiet tikai nullēm un uzņēmumiem.
Un tie ir nullēm un tiem, kas sacerēt tieši ka meklēšana programmu.
>> Un tā katru rieciens pieciem biti, katrs baits nullēm un tiem šeit,
pārstāv kādu instrukcija parasti iekšpusē no datora.
Un patiesībā, ja jūs esat dzirdējis mārketinga sauklis "Intel inside" - tas,
protams, tikai nozīmē, jums ir Intel CPU vai smadzeņu iekšā datoru.
Un ko tas nozīmē būt par CPU ir ka jums ir instrukciju kopums,
tā sakot.
>> Katram CPU pasaulē, daudzi no tos, ko Intel šajās dienās,
saprot ierobežots skaits norādījumiem.
Un šie norādījumi ir tik zems līmenis kā pievienot šos divus skaitļus kopā,
pavairot šos divus skaitļus kopā, pārvietot šo gabals datus no šejienes
šeit atmiņā, saglabājiet šo Informācija no šeit, lai šeit atmiņā,
un tā forth-- tik ļoti, ļoti zema līmeņa, gandrīz elektroniskās detaļas.
Bet ar tiem, matemātiskās operācijas kopā
ar to, ko mēs runājām iepriekš, attēlojumu datu
kā nullēm un uzņēmumiem, var jums veidot visu
ka dators var darīt šodien, vai tas ir teksta, grafiskā, mūzikas,
vai citādi.
>> Tātad tas ir ļoti viegli nokļūt zaudētas nezālēm ir ātri.
Un tur ir daudz sintaktiskās izaicinājumi
saskaņā ar kuru, ja jūs veicat vienkāršākais, stupidest no drukas kļūdām neviens no programmas
darbosies whatsoever.
Un tā vietā, izmantojot valoda, piemēram, C šorīt,
Es domāju, ka būtu vairāk jautrības, lai faktiski darīt
kaut kas vairāk vizuāli, kas savukārt paredzētas bērniem
ir faktiski ideāls izpausme Ar faktisko plānošanu
language-- vienkārši notiek, izmantot attēlus, nevis teksta
pārstāvēt šo ideju.
>> Tātad, kad jūs patiešām ir konts scratch.mit.edu,
noklikšķiniet uz pogas Izveidot augšā pa kreisi no vietas.
Un jums vajadzētu redzēt vidi, piemēram, viens es esmu par to, lai redzētu uz mana ekrāna
šeit.
Un mēs tērēt tikai nedaudz mazliet laika spēlējot šeit.
Let 's redzēt, ja mēs nevaram visu atrisināt dažas problēmas kopā šādā veidā.
>> Tātad, ko jūs redzēsiet laikā šis environment-- un faktiski tikai ļaujiet
man pauze.
Vai kāds nav šeit?
Ne šeit?
LABI.
Tāpēc ļaujiet man norādīt dažus raksturojums šajā vidē.
>> Tāpēc augšējā kreisajā stūrī, mēs ir Scratch stadiju, lai runāt.
Scratch ir ne tikai nosaukums Šī programmēšanas valodas;
tas ir arī nosaukums, kaķi, kas redzat pēc noklusējuma tur oranžā krāsā.
Viņš ir uz skatuves, tāpēc daudz, piemēram, es aprakstīju
bruņurupucis agrāk kā atrašanos taisnstūra baltā tāfele vide.
Šī kaķa pasaule ir tikai pilnībā ar šo taisnstūra up top tur.
>> Tajā pašā laikā, pa labi labajā pusē šeit, tas ir
tikai skripti zona, tukša šīfera ja Jums gribas.
Tas ir, ja mēs ejam, lai rakstītu Mūsu programmas tikai brīdi.
Un celtniecības bloki, ka mēs izmantot, lai rakstītu šo program-- puzzle
gabali, ja jums will-- ir tiem, tepat pa vidu,
un viņi kategorijās ar funkcionalitāti.
Tā, piemēram, es esmu gatavojas iet uz priekšu un apliecina vismaz vienu no šiem.
Es iešu uz priekšu un noklikšķiniet Kontroles kategorija augšu augšas.
>> Tātad tie ir kategorijas, līdz top.
Es esmu gatavojas noklikšķiniet uz Control kategoriju.
Drīzāk, es esmu gatavojas noklikšķiniet uz Notikumi kategorija, pats pirmais vadībā top.
Un, ja jūs vēlaties, lai sekot līdzi pat kā mēs to izdarītu, jūs esat diezgan laipni aicināti.
Es esmu gatavojas noklikšķiniet un velciet to Pirmais, "zaļus karogs uzklikšķināt."
Un tad es esmu gatavojas piliens to tikai aptuveni augšpusē manu tukšo šīferis.
>> Un, kas ir jauka par nulles ir tas, ka šī puzzle gabals, kad
savstarpēji saistīti ar citām puzzle gabalus, gatavojas darīt burtiski
kādi ir šie puzzle gabalus saku darīt.
Tā, piemēram, Scratch ir taisnība tagad vidū viņa pasaulē.
Es iešu uz priekšu un izvēlēties Tagad, teiksim, Motion kategorija,
ja vēlaties darīt same-- Motion kategoriju.
Un tagad paziņojums man ir viss ķekars puzzle gabalus šeit
ka, atkal, veida darīt to, ko viņi saka.
Un es iešu uz priekšu un velciet un piliens Pārvietot bloku tiesības pār šeit.
>> Un paziņo, ka, tiklīdz jūs saņemsiet tuvu apakšā "zaļo karogu
uzklikšķināt "pogu, paziņojums kā parādīts baltās līnijas,
it kā tas ir gandrīz magnētiskā, tā vēlas iet uz turieni.
Just let iet, un tas būs snap kopā un formas tiks atrasti.
Un tagad jūs varat varbūt gandrīz uzminēt, kur mēs ejam ar to.
>> Ja paskatās Scratch posmā nekā šeit un skatīties uz augšu no tā,
jūs redzēsiet sarkanu gaismu A stop zīmi un zaļo karogu.
Un es iešu uz priekšu un skatīties manu screen--
tikai brīdi, ja jūs varētu.
Es esmu gatavojas noklikšķiniet uz zaļā karoga tieši tagad,
un viņš pārcēlās ko, šķiet, ir 10 soļi vai 10 pikseļi, 10 punkti, uz ekrāna.
>> Un tā nav, ka aizraujoši, bet ļaujiet man ieteikt
pat bez mācīšanas, vienkārši izmantojot pašu savu intuition-- pieņemsim
es iesaku jums saprast, kā padarīt Scratch pastaigāties pa labi pie skatuves.
Vai viņam veikt ceļu labajā pusē ekrāns, visu ceļu pa labi.
Ļaujiet man sniegt jums brīdi vai arī tā cīnīties ar to.
Jūs varētu vēlēties, lai apskatīt citās kategorijās blokiem.
Viss kārtībā.
Tik vienkārši, lai Atgādinājums, kad mums ir zaļais karogs uzklikšķināt šeit
un pārvietot 10 soļi ir tikai norādījums, katru reizi, kad es
noklikšķiniet uz zaļo karogu, kas notiek?
Nu, kas ir darbojas savu programmu.
Lai es varētu darīt varbūt 10 reizes manuāli,
bet tas jūtas mazliet bit hackish, tā sakot,
kuru es neesmu īsti problēmu risināšanā.
Es esmu tikai mēģina atkal un atkal un atkal un atkal
kamēr es veida nejauši sasniegt direktīvu
ka es noteikti, lai sasniegtu iepriekš.
>> Bet mēs zinām no mūsu pseudocode agrāk, ka tur ir
šis jēdziens plānošanas looping, darot kaut ko atkal un atkal.
Un tā es redzēju, ka ķekars jums sasniegts ko puzzles gabalu?
Atkārtojiet, līdz.
Lai mēs varētu kaut ko darīt tāpat atkārto, līdz.
Un ko tu atkārto, līdz tieši?
>> LABI.
Un ļaujiet man iet ar vienu, kas ir nedaudz vienkāršāku tikai brīdi.
Ļaujiet man iet uz priekšu un darīt to.
Ievērojiet, ka, jo Jums var būt atklāja zem Control,
ir šī atkārtojums bloks, kas neizskatās kā tas ir, ka liels.
Tur nav daudz istabu starp šīm divām dzeltenām līnijām.
Bet, tā kā daži no jums varētu būt pamanīju, ja jums vilkt un nomest,
paziņojums, kā tas aug, lai aizpildītu formu.
>> Un jūs pat varat piestūķēt vairāk.
Tas būs tikai turpinās pieaugt, ja velkat un lidināties pār to.
Un es nezinu, kas ir labākais šeit, tāpēc ļaujiet
man vismaz atkārtot piecas reizes, lai instance, un tad doties atpakaļ uz skatuves
un noklikšķiniet uz zaļo karogu.
Un tagad paziņojums tas nav gluži tur.
>> Tagad daži no jums ierosināja, kā Victoria vienkārši nav, atkārto 10 reizes.
Un tas parasti dara saņemt viņam visu ceļu,
bet nebūtu tur būt straujāka veids, kā patvaļīgi norādītas
cik daudz kustas padarīt?
Kas varētu būt labāks bloks nekā atkārtot 10 reizes būt?
>> Jā, tad kāpēc ne darīt kaut ko uz visiem laikiem?
Un tagad ļaujiet man pāriet šo puzzle gabals iekšā tur un atbrīvoties no šo vienu.
Tagad paziņojums vienalga, kur Scratch sākas, viņš dodas pie malas.
Un par laimi MIT, kurš Scratch, tikko
pārliecinās, ka viņš nekad pilnībā izzūd.
Jūs vienmēr varat paķert savu asti.
>> Un tikai intuitīvi, kāpēc viņš saglabāt pārvietojas?
Kas šeit notiek?
Viņš, šķiet, ir pārtraukta, bet tad ja es uzņemt un velciet
viņš tur vēlas doties tur.
Kāpēc ir tā, ka?
Patiesi, dators ir burtiski gatavojas darīt to, kas jums pateikt to darīt.
Tātad, ja jūs teicis to agrāk darīt pēc lieta uz visiem laikiem, pārvietot 10 soļi,
tas notiek, lai saglabātu turpinās un iet kamēr es hit sarkano stop zīmi
un vispār pārtrauktu programmu.
>> Tātad, pat ja Jums nav izdarīt, kā es varēju
padarīt Scratch pārvietot ātrāk pa ekrānu?
Vairāk soļi, labi?
Tā vietā, lai dara 10 laikā, kāpēc ne mēs
iet uz priekšu un mainīt kuri paredzēti, ko tu propose-- 50?
Tāpēc tagad es esmu gatavojas noklikšķiniet uz zaļo karogu, un, protams, viņš iet ļoti ātri.
>> Un tas, protams, ir tikai izpausme animāciju.
Kas ir animācija?
Tas tikai parāda jums cilvēka A viss ķekars Fotogrāfiju tiešām,
ļoti, ļoti ātri.
Un tāpēc, ja mēs esam tikai spēcīgi viņam pārcelties papildu pasākumus,
mēs esam tikai kam efekts būt izmaiņas, kur viņš ir uz ekrāna
vēl straujāk laika vienībā.
>> Tagad nākamais izaicinājums, es ierosināju bija, ir viņam piepeši pie malas.
Un nezinot, kas puzzle gabali exist-- jo tas ir naudas sods
ja Jums nav iegūt ar posms challenge-- ko
jūs vēlaties darīt intuitīvi?
Kā mums ir viņam piepeši atpakaļ un tālāk, starp kreisi un pa labi?
>> Jā.
Tāpēc mums ir zināma veida no stāvokļa, un mēs
šķiet, ir conditionals, tāpēc, lai runā, zem Control kategorijā.
Kurš no šiem blokiem mēs, iespējams, vēlas?
Jā, varbūt, "ja, tad."
Tāpēc paziņojums, ka starp dzeltenajiem blokiem Mēs esam šeit, ir šis "ja"
vai šis "ja, cits" bloks, kas būs ļauj mums pieņemt lēmumu, lai to paveiktu
vai to darīt.
Un jūs pat varat nest tos darīt vairākas lietas.
Vai, ja jūs esat nav šeit aizgājuši vēl, iet uz priekšu uz uztveres kategoriju
and-- pieņemsim redzēt, ja tas ir šeit.
>> Tātad, ko bloks varētu būt noderīga lai noteiktu, vai viņš ir pie skatuves?
Jā, ievērosiet, ka daži no šiem blokiem var parametrized, lai runāt.
Tās var kārtot pielāgot, ne atšķirībā no HTML vakar ar atribūtiem,
ja šie atribūti veida pielāgot uzvedību tag.
Tāpat šeit, es varu paķert šo pieskaroties bloku un pārmaiņas un uzdot jautājumu,
Jūs pieskaras peles rādītāju, piemēram, kursora
vai jūs pieskaras malai?
>> Tāpēc ļaujiet man iet un darīt.
Es esmu gatavojas tālinātu uz brīdi.
Ļaujiet man paķert šo puzzle gabals šeit, tas puzzle gabals tas,
un es esmu gatavojas sajukt tos tikai brīdi.
Es esmu gatavojas pārvietot to, mainīt uz aizkustinošs malai,
un es esmu gatavojas kustības izdarīt.
Tātad, šeit ir dažas sastāvdaļas.
Es domāju, ka es esam ieguvuši visu, ko es gribu.
>> Vai kāds gribētu ierosināt, kā es var savienot šos varbūt augšas uz leju
Lai atrisinātu problēmu, kam Scratch pārvietoties pa labi pa kreisi, pa labi, lai
kreisās uz labās uz kreiso, katrs laiku tikai veselīgs pie sienas?
Ko es gribu darīt?
Kuru bloķēt man vajadzētu savienot ar "Zaļus karogs uzklikšķināt pirmais"?
>> Labi, tāpēc sāksim ar "uz visiem laikiem."
Kas iet iekšā nākamais?
Kāds cits.
OK, pārvietot darbības.
Viss kārtībā.
Tad kas?
Tātad tad, ja.
Un paziņojums, lai gan tas izskatās iestiprināta kopā cieši,
tas būs tikai pieaugs aizpildīt.
Tas būs tikai ielēkt kur es gribu to.
>> Un ko es varu ievietot starp IF un tad?
Iespējams, "ja pieskaras malai."
Un paziņojums, atkal, tas ir pārāk liels par to, bet tas pieaugs aizpildīt.
Un tad savukārt 15 grādiem?
Cik grādiem?
Jā, tāpēc 180 būs spin mani visu ceļu apkārt.
Tātad, pieņemsim redzēt, ja es saņēmu šīs tiesības.
Ļaujiet man attālinātu.
>> Ļaujiet man velciet Scratch augšu.
Tāpēc viņš ir nedaudz izkropļota tagad, bet tas ir jauki.
Kā es varu reset viņu viegli?
Es esmu gatavojas nedaudz apkrāptu.
Tāpēc es esmu pievienojot vēl bloks, tikai, lai būtu skaidrs.
Es gribu, lai viņš norāda 90 grādiem pa labi pēc noklusējuma,
tāpēc es esmu tikai gatavojas pateikt viņam to darīt programmiski.
Un šeit mēs ejam.
Mēs, šķiet, esam darījuši.
Tas ir nedaudz dīvaini, jo viņš pastaigājas otrādi.
Sauksim ka bug.
Tas ir kļūda.
Bug ir kļūda kādā programmai, loģiska kļūda, ka es, cilvēka, kas izgatavoti.
Kāpēc viņš iet kājām gaisā?
Vai MIT skrūvējamu augšu vai bija man?
>> Jā, es domāju, tas nav MIT s vaina. Viņi man iedeva puzzles gabaliņam
ka saka savukārt dažas grādiem.
Un Viktorijas ierosinājumu, Es esmu pagrieziena 180 grādiem,
kas ir pareizais intuīcija.
Bet pagriežot par 180 grādiem burtiski nozīmē pagrieziena 180 grādiem,
un tas nav īsti ko es gribu, acīmredzot.
Tāpēc, ka vismaz viņš ir Šī divdimensiju pasaulē,
tāpēc pagrieziena īsti notiek uzsist viņam otrādi.
>> Es, iespējams, vēlas izmantot to, ko bloķēt vietā, pamatojoties uz to, ko jūs redzat šeit?
Kā mēs varētu noteikt šo?
Jā, lai mēs varētu norādīt pretējā virzienā.
Un patiesībā pat tas nebūs pietiekami,
tāpēc, ka mēs varam tikai grūti kods līdz norādot pa kreisi vai pa labi.
>> Jūs zināt, ko mēs varētu darīt?
Izskatās, mums ir ērtības bloks šeit.
Ja es tuvinātu, skatiet kaut kas mums patīk šeit?
Tā izskatās MIT ir abstrakcija uzcelta šeit.
Šis bloks, šķiet, ir līdzvērtīga uz kuru citi bloki, daudzskaitlis?
>> Tas viens bloks, šķiet, ir līdzvērtīga uz šo visu trio blokiem
ka mēs esam šeit.
Tātad izrādās, es varētu vienkāršot manu programma, atbrīvojoties no visa, kas
un vienkārši ielieciet to šeit.
Un tagad viņš ir vēl mazliet buggy, un tas ir labi tagad.
Mēs ņemšu atvaļinājumu, ka būs.
Bet mana programma ir pat vienkāršāk, un arī tas,
būtu reprezentatīvi no mērķis programming--
ir ideāli padarīt savu kodu, kā vienkārši, kā kompakts vien iespējams,
kamēr vēl ir kā lasāma kā iespējams.
Jūs nevēlaties, lai padarītu to tik kodolīga ka tas ir grūti saprast.
>> Bet paziņojums es esmu aizstāj trīs bloki ar vienu,
un tas varbūt ir laba lieta.
Esmu nošķirts prom jēdzienu pārbaudīt, vai jūs esat
no malas ar tikai vienu bloku.
Tagad mēs varam būt jautri ar šo, patiesībā.
Tas nav pievienot tik daudz intelektuālā vērtība, bet jautrs vērtība.
Es iešu uz priekšu un paķert šo skaņu šeit.
Tāpēc ļaujiet man iet uz priekšu, un ļaujiet man apturēt programmu uz brīdi.
Es esmu gatavojas ierakstīt šādu, ļauj piekļūt manam mikrofonam.
>> Te nu mēs esam.
Sakta.
Mēģināsim to atkal.
Te nu mēs esam.
Labi, es ierakstīts nepareizi lieta.
Te nu mēs esam.
Sakta.
Viss kārtībā.
Tagad man ir nepieciešams, lai atbrīvotos no tā.
Viss kārtībā.
>> Tāpēc tagad man ir ierakstīšana tikai "Sakta".
Tāpēc tagad es iešu priekšu un saucam "sakta".
Es esmu gatavojas doties atpakaļ uz manu skriptu, un tagad
paziņojums tur ir šis bloks, kas sauc atskaņot skaņu "Ņau" vai atskaņot skaņu "sakta".
Es esmu gatavojas vilkt to, un, ja Es būtu jāliek šis komiski efektu?
Jā, tāpēc tagad tas ir sava veida buggy, jo tagad tas block--
paziņo, cik šis "ja uz malu, Bounce "ir sava veida pašpietiekams.
Tāpēc man ir nepieciešams noteikt šo.
Ļaujiet man iet uz priekšu un darīt to.
Ļaujiet man atbrīvoties no šo un doties atpakaļ mūsu oriģinālam, vairāk apzināta
funkcionalitāti.
So ", ja pieskaras malai, tad" es gribu griezties, kā ierosināts Victoria,
180 grādi.
Un vēlos spēlēt skaņa "sakta" tur?
>> Jā, pamanāt, ka tas ir ārpus ka dzeltenā bloks.
Tātad tas arī būtu bug, bet es esmu ievērojis to.
Tāpēc es esmu gatavojas velciet to šeit, un paziņojums tagad tas ir iekšā ", ja."
Tātad ", ja" tas ir sava veida Līdzīga rokas līdzīgi Blot
kas ir tikai gatavojas darīt to, kas ir iekšpusē no tā.
Tāpēc tagad, ja es attālinātu at risks annoying--
>> Dators: Sakta, sakta, sakta.
>> DAVID Malan: Un tas būs tikai iet uz visiem laikiem.
Tagad tikai, lai paātrinātu lietas šeit, ļaujiet man iet uz priekšu un atvērt,
pieņemsim say-- ļaujiet man iet uz kādu manas sīkumi no klases.
Un ļaujiet man atvērt, teiksim, šis viens, viens no mūsu mācību stipendiātiem
pāris gadus atpakaļ.
Tāpēc daži no jums varētu atgādināt šī spēle no vakardienas,
un tas ir tiešām ievērojams.
Pat ja mēs esam darīts Vienkāršākais programmu tieši tagad,
pieņemsim apsvērt, ko tas tiešām izskatās.
Ļaujiet man hit spēli.
>> Tātad šajā spēlē, mums ir varde, un izmantojot bultiņas keys--
viņš ņem lielākus pasākumus, nekā es remember-- Man ir kontrole pār šo varde.
Un mērķis ir iegūt pāri aizņemts ceļš bez nokļūšanu automašīnām.
Un pieņemsim see-- ja es iet uz augšu šeit, es jāgaida log lai ritinātu līdz.
Tas jūtas kā bug.
Tas ir sava veida bug.
Viss kārtībā.
Es esmu par to šeit, tur, un tad jūs turēt
iet, kamēr jums visiem vardes uz lilija spilventiņi.
Tagad tas varētu izskatīties vēl sarežģītāka,
bet pieņemsim mēģināt lauzt Tas noteikti garīgi
un mutiski uz tās sastāvdaļu blokiem.
Tātad ir iespējams, puzzle gabals, kas mēs neesam redzējuši vēl
bet tas ir reaģēt uz keystrokes, uz lietām, ko es hit uz klaviatūras.
>> Tātad tur ir iespējams, sava veida bloks, kas saka, ja atslēga vienāds augšu,
tad kaut ko darīt ar Scratch-- varbūt pārvietot to 10 soļus šajā virzienā.
Ja uz leju taustiņš ir nospiests, pārvietot 10 soļi šādā veidā, vai kreiso taustiņu, pārvietojiet 10 soļi
šādā veidā, 10 soļus, kas.
Es esmu skaidri pagriezās kaķi par varde.
Tātad tas ir tikai tad, ja kostīms, kā Scratch zvani it-- mēs
tikai imports priekšstatu par varde.
>> Bet ko vēl notiek?
Kādi citi koda rindiņas, ko citi puzzle gabalus
darīja Blake, mūsu mācību kolēģi, izmanto šajā programmā, acīmredzot?
Kas padara visu move-- kāda programmēšanas būvēt?
>> Kustības, sure-- tāpēc pārvietot bloku, for sure.
Un, kas ir tas gājiens bloks iekšpusē, visticamāk?
Jā, sava veida cilpas, varbūt mūžīgi bloķēt, varbūt atkārtot block--
atkārto, līdz bloku.
Un tas, ko ir padarot žurnālus un lilija spilventiņi un viss pārējais pārvietot
uz priekšu un atpakaļ.
Tas ir vienkārši notiek bezgalīgi.
>> Kāpēc daži no automašīnām pārvietojas ātrāk nekā citi?
Kas ir atšķirīgs par šo programmu?
Jā, iespējams, daži no tiem ir veikt vairāk soļi uzreiz un daži no tiem
mazāk soļi uzreiz.
Un vizuālo efektu ir ātra pret lēns.
>> Ko jūs domājat noticis?
Kad es saņēmu savu varde visu ceļu pāri ielai un upi
uz lilija pad, kaut ievērības cienīgs noticis.
Kas notika, tiklīdz es to izdarīju?
Tas apstājās.
Ka varde apstājās, un Man otro varde.
Tātad, ko būvēt, jābūt izmantoti tur, kāda funkcija?
>> Jā, tāpēc tur ir sava veida "Ja" stāvoklī tur, too.
Un izrādās out-- mēs neredzēju this-- bet tur ir citi bloki tur, ka
var teikt, ja jums ir aizkustinošs cita lieta, uz ekrāna,
ja jūs pieskaras lilija spilventiņu ", tad."
Un tad tas ir tad, kad mēs padarīt otrais varde parādās.
Tātad, pat ja šī spēle ir noteikti ļoti datēta, lai gan pēc pirmā acu uzmetiena
tur ir tik daudz kas notiek on-- un Blake nebija pātagu šo augšu divās minūtēs,
tas, iespējams, veica viņam vairākas stundas, lai radītu šo spēli
pamatojoties uz viņa atmiņā vai video vakardienas versiju par to.
Bet visiem šiem sīkumiem notiek uz ekrāna izolēti
vārīties uz leju, lai tie ļoti vienkārši constructs-- kustības vai paziņojumi
kā mēs esam apspriests, cilpas un nosacījumi, un tas ir par to.
Ir daži citi mīļotājs iezīmes.
Dažas no tām ir tīri estētiska vai akustisko,
tāpat skaņām es tikko spēlēja ar.
Bet lielākā daļa, jūs ir šajā valodu, nulles,
visas pamata celtniecības bloki, kas jums
ir C, Java, JavaScript, PHP, Ruby, Python,
un jebkādu skaitu citās valodās.
Visus jautājumus par nulles?
Viss kārtībā.
Tāpēc mēs ne dziļāk nirt līdz nulles, ja jūs esat laipni šīs nedēļas nogalē,
it īpaši, ja jums ir bērni vai nieces un brāļa un tādi,
iepazīstināt viņus ar nulles.
Tas ir tiešām lieliski jautrs vide ar, jo tā autori saka,
ļoti augstie griesti.
Pat ja mēs sākām ar ļoti zema līmeņa detaļas,
jūs tiešām var izdarīt diezgan daudz ar to, un tas, iespējams,
demonstrēšana tieši tā.
>> Bet pieņemsim tagad pāriet uz kādu vairāk sarežģītas problēmas, ja jūs,
pazīstams kā "meklēšana" un "Šķirošanas," kopumā.
Mums bija šis tālrunis grāmata earlier-- šeit vēl viena tikai discussion--
ka mēs varējām meklēt efektīvāk, jo
par būtisku pieņēmumu.
Un tikai, lai būtu skaidrs, ko pieņēmums bija I padarot
ja meklē, izmantojot šo tālruņa grāmatu?
Tas Mike Smith bija tālrunis grāmatu, lai gan I
varētu rīkoties scenārijs bez viņa
tur, ja es vienkārši apstājās priekšlaicīgi.
Grāmata ir alfabēta.
Un tas ir ļoti dāsna pieņēmums, jo tas
nozīmē someone-- es esmu veida griešanas stūri,
piemēram, es esmu ātrāk, jo kādam cits darīja daudz smaga darba par mani.
>> Bet ko tad, ja tālrunis Grāmata tika Nesašķirotas?
Varbūt Verizon got slinks, vienkārši izmeta ikviena vārdi un numuri, kas tur
varbūt tādā secībā, kādā tie pierakstījies tālruņa pakalpojums.
Un cik daudz laika tas mani atrast kādu, piemēram, Mike Smith?
1,000 lapa tālrunis book-- cik lapas man ir skatīties cauri?
>> Visus.
Jūs esat veida no luck.
Jūs burtiski ir jāskatās uz katru lapa, ja tālrunis grāmata ir tikai
nejauši sakārtoti.
Jūs varētu saņemt laimīgs un atrast Mike par pašu pirmo lapu, jo viņš
bija pirmais klients pasūtīt tālruņa pakalpojums.
Bet viņš varētu būt pēdējais, too.
>> Tātad izlases rīkojums nav labs.
Tātad pieņemsim, ka mums ir sakārtot tālruņu grāmatu vai vispār kārtošanas datiem
ka mēs esam dota.
Kā mēs varam darīt?
>> Nu, ļaujiet man tikai mēģināt vienkāršs piemērs šeit.
Ļaujiet man iet uz priekšu un mētāt daži skaitļi uz kuģa.
Pieņemsim, ciparus mums ir, ir, teiksim, četri, divi, viens, un trīs.
Un, Ben, kārtot šos skaitļus par mums.
>> Labi.
Kā tu to izdarīji?
Viss kārtībā.
Tātad, sākt ar mazāko vērtība un augstākais,
un tas ir patiešām labs intuīcija.
Un saprast, ka mēs cilvēki ir faktiski diezgan
labi problēmu risināšana piemēram, tas, vismaz
kad dati ir salīdzinoši neliels.
Tiklīdz jūs sākat ir simtiem skaitļu, tūkstošiem numuru,
miljoniem numuru, Ben iespējams nevar darīt to gluži tik ātri,
pieņemot, ka tur bija nepilnības numuriem.
Diezgan viegli saskaitīt uz miljonu pretējā gadījumā, tikai laikietilpīga.
>> Tātad algoritms izklausās tāpat Ben izmanto tikai tagad
bija meklēt mazāko numuru.
Tātad, pat ja mēs cilvēkiem varam veikt ir daudz informācijas vizuāli,
dators ir faktiski nedaudz vairāk ierobežota.
Dators var tikai apskatīt vienu baits laikā
vai varbūt četri baiti at a LAIKU_ šajās dienās varbūt 8 baiti at a LAIKU_
bet ļoti neliels skaits baitu noteiktā laikā.
>> Tāpēc, ka mums tiešām ir četras atsevišķas vērtības here--
un jūs varat iedomāties Ben kā ar acu aizsegi uz ja viņš būtu dators, piemēram
ka viņš nevar redzēt neko citu nekā vienu numuru pie LAIKU_
tāpēc mēs parasti pieņemam, tāpat kā Angļu, mēs lasīt no labās uz kreiso.
Tātad pirmais numurs Ben iespējams izskatījās at bija četri, un tad ļoti ātri
sapratu, ka ir diezgan liels number-- ļaujiet man glabāt meklējat.
>> Tur ir divi.
Uzgaidi minūti.
Divi ir mazāks nekā četri.
Es esmu gatavojas atcerēties.
Divi šobrīd ir mazākais.
Tagad one-- tas ir pat labāk.
Tas ir vēl mazāka.
Es esmu gatavojas aizmirst par divām un tikai atcerieties vienu tagad.
>> Un viņš varēja apstāties meklē?
Nu, viņš varēja balstīta uz šo informāciju,
bet viņš labāk meklēšanu pārējā saraksta.
Jo ko tad, ja nulles bija sarakstā?
Ko darīt, ja negatīvs viens bija sarakstā?
Viņš tikai zina, ka viņa atbildi ir pareiza, ja viņš ir izsmeļoši
pārbauda visu sarakstu.
Tātad mēs skatāmies uz pārējo šo.
Three-- tas bija laika izšķiešana.
Got nelaimīgs, bet es biju vēl pareizi to darīt.
Un tāpēc tagad viņš, iespējams, izvēlēts mazākais skaits
un vienkārši ielieciet to sākumā no saraksta, jo es darīšu šeit.
Tagad to, ko jūs darīt tālāk, lai gan Jums nav jādomā par to gandrīz
tādā mērā?
Atkārtojiet šo procesu, tāpēc daži veida cilpu.
Tur ir pazīstams ideja.
Tātad, šeit ir četri.
Pašlaik tas ir mazākais.
Tas ir kandidāts.
Vairs nē.
Tagad es esmu redzējis divus.
Tas ir nākamais mazākais elements.
Three-- tas nav mazāks, tāpēc Tagad Ben var raut ārā divas.
>> Un tagad mēs atkārtojiet procesu, un protams trīs izpaužas izvilka nākamo.
Atkārtojiet procesu.
Četri izpaužas velk ārā.
Un tagad mēs esam ārā no skaitļiem, tādēļ saraksts ir sakārtots.
>> Un tiešām, tas ir formāls algoritms.
Dators zinātnieks būtu aicinu šo "atlases veida,"
ideja ir sava uzskaitīt iteratively-- atkal
un atkal un atkal izvēloties mazākais skaits.
Un, kas ir jauki, par to ir tas ir tikai tik darn intuitīvs.
Tas ir tik vienkārši.
Un jūs varat atkārtot to pašu darbība atkal un atkal.
Tas ir vienkārši.
>> Šajā gadījumā tā bija ātri, bet cik ilgi tas tiešām ņemt?
Padarīsim to, šķiet, un justies mazliet vairāk garlaicīgs.
Tātad, viens, divi, trīs, četri, pieci seši, septiņi, astoņi, deviņi, 10, 11, 12, 13, 14,
15, 16-- jebkuram skaitam.
Es tikai gribēju vēl šo laiks nekā tikai četri.
Tātad, ja es esam ieguvuši visu ķekars numuriem now-- to
nav pat svarīgi ko viņi are-- pieņemsim
domāju par to, ko tas algoritms tiešām ir līdzīgi.
>> Pieņemsim, ka skaitļi tur.
Atkal, nav svarīgi, ko viņi ir, bet viņi nejauši.
Es esmu piemērojot Ben algoritmu.
Man vajag, lai izvēlētos mazāko numuru.
Ko man darīt?
Un es esmu gatavojas fiziski darīt to šoreiz rīkoties to ārā.
Looking, looking, looking, looking, looking.
Tikai ar laiku es nokļūt beigām, sarakstu var
Es saprotu, mazākais skaits bija divi šoreiz.
Viens nav sarakstā.
Tāpēc es nolikt divi.
>> Ko man darīt tālāk?
Looking, looking, looking, looking.
Tagad es atradu numurs septiņi, jo tur ir nepilnības šajās numbers--
bet tikai patvaļīgi.
Viss kārtībā.
Tāpēc tagad es varu nolikt septiņi.
Raugoties meklē, meklē.
>> Tagad es esmu pieņemot, no Protams, ka Ben nav
ir papildus RAM, extra atmiņa, jo, protams,
Es skatos uz to pašu numuru.
Protams, es varētu būt atcerējos visiem šiem numuriem,
un tas ir absolūti patiess.
Bet, ja Ben atceras visu no numuriem, viņš ir redzējis,
viņš nav īsti veikts būtisks progress
jo viņš jau ir spēja, lai meklētu
cauri numuriem uz kuģa.
Atceroties visi numuri nepalīdz,
jo viņš vēl var kā dators tikai apskatīt, mēs esam teica, viens numurs
laikā.
Tāpēc nav sava veida apkrāptu tur, ka jūs varat sviras.
>> Tātad patiesībā, jo es turpināt meklēšanu sarakstu,
Es burtiski ir tikai glabāt iet un atpakaļ caur to, noplūkšanas out
nākamais mazākais skaits.
Un, kā jūs varat veida secināt no manas dumjš kustības,
tas tikai kļūst ļoti garlaicīgs ļoti ātri,
un man šķiet, iet atpakaļ un tālāk, un atpakaļ pavisam nedaudz.
Tagad, lai būtu godīgi, man nav jāiet gluži kā, labi, pieņemsim see-- tā būtu godīga,
Man nav staigāt diezgan jo daudzi soļi katru reizi.
Jo, protams, kā es izvēlēties numurus no saraksta,
atlikušais saraksts kļūst īsāks.
>> Un tāpēc pieņemsim domāt par cik soļus es esmu patiešām
traipsing caur katru reizi.
Pašā pirmajā situācijā mums bija 16 numuri,
un tā maximally-- pieņemsim tikai izdarīt par discussion--
Man nācās meklēt caur 16 numurus, lai atrastu vismazāko.
Bet tad, kad es noplūktas out mazākais skaits, kā
sen bija atlikušo sarakstu, protams?
Tikai 15.
Tik, cik skaitļu darīja Ben vai man ir meklēt, izmantojot otro reizi apkārt?
15, vienkārši iet un atrast mazāko.
Bet tagad, protams, saraksts, Arī, mazāks nekā tas bija agrāk.
Tik cik soļus darīja I ir jāņem nākamreiz?
14 un pēc tam 13 un pēc tam 12, plus dot, dot, dot, kamēr es esmu palicis tikai ar vienu.
Tāpēc tagad dators zinātnieks būtu jautāt, labi, ko dara, ka visi vienlīdzīgi?
Tas faktiski ir vienāds ar kādu konkrētu numurs, kas mēs varētu noteikti
do aritmētiski, bet mēs gribam runāt par efektivitāti algoritmu
vairāk formulaically maz, neatkarīgi no cik ilgi saraksts ir.
>> Un, lai jūs zināt, ko?
Tas ir 16, bet, piemēram, es teicu iepriekš, pieņemsim tikai zvanīt izmēru problēmas
n, kur n ir daži numurs.
Varbūt tas ir 16, varbūt tā ir trīs, varbūt tas ir miljons.
Es nezinu.
Man vienalga.
Ko es tiešām gribu ir formula, kas es varu
izmantot, lai salīdzinātu šo algoritmu pret citiem algoritmiem
ka kāds varētu apgalvot ir labāk vai sliktāk.
>> Tātad izrādās, un tikai es zinām no pakāpē skolā,
ka tas faktiski darbojas, lai pats lieta kā n pār n plus viens pa diviem.
Un tas notiek ar vienāds, no Protams, n brusas plus n pa diviem.
Tātad, ja es gribēju formulu uz cik soļiem
tika iesaistīti meklē vispār no šiem numuriem atkal un atkal
un atkal un atkal, es teiktu tas n brusas plus n pa diviem.
Bet jūs zināt, ko?
Tas tikai izskatās netīrs.
Es tikai tiešām gribu vispārējā sajūta lietām.
Un jūs varētu atgādināt no vidusskola, ka
ir jēdziens augstāko pasūtījuma termiņā.
Kurš no šiem noteikumiem, tad n brusas, N, vai pusi,
ir vislielākā ietekme laika gaitā?
Jo lielāks n izpaužas, kas no šiem jautājumiem visvairāk?
>> Citiem vārdiem sakot, ja es plug no miljona, n kvadrātā
būs, visticamāk, dominējošais faktors,
jo miljons reižu pati par sevi ir daudz lielāks
nekā plus vienu papildu miljoni.
Tātad, jūs zināt, ko?
Tas ir tik darn liels numurs, ja jūs kvadrātveida numuru.
Tas nav īsti jautājums.
Mēs esam tikai gatavojas šķērsot ārā un aizmirst par to.
Un tā dators zinātnieks teiktu ka efektivitāte šajā algoritma
ir par kārtību n squared-- Es domāju patiesi tuvināšanu.
Tā ir sava veida rupji n brusas.
Laika gaitā, jo lielāka un lielāka n izpaužas, šis
ir labs novērtējums par to, ko efektivitāte vai trūkums efektivitātes
Šī algoritma patiesībā ir.
Un es iegūtu, ka, protams, no faktiski dara math.
Bet tagad es esmu tikai vicināšanu manas rokas, jo es tikko
vēlas vispārēju sajūtu šo algoritmu.
>> Tātad, izmantojot to pašu loģiku, tikmēr, pieņemsim apsvērt citu algoritmu
mēs jau izskatījās at-- lineāru meklēšanu.
Kad man bija meklējot par tālruni book--
ne šķirošanu to, meklējot pa tālruni book--
mēs tur saka, ka tas bija 1000 pakāpieni, vai 500 pakāpieni.
Bet pieņemsim vispārināt to.
Ja tur ir n lapas tālrunis grāmatu, kas ir
darbības laiks vai efektivitāte lineāro meklēt?
Tas ir par kārtību cik soļus, lai atrastu
Mike Smith izmantojot lineāro meklēšanu, tad Pirmais algoritms, vai pat otrais?
>> Sliktākajā gadījumā, Mike ir beigās grāmatas.
Tātad, ja tālrunis grāmata ir 1000 lappuses, mēs teicām pēdējo reizi, sliktākajā gadījumā,
tas var aizņemt aptuveni cik daudzas lapas, lai atrastu Mike?
Tāpat 1000.
Tas augšējo robežu.
Tas ir iespējams, vissliktākā situācija.
Bet atkal, mēs esam pārvietojas prom no skaitļiem, piemēram, 1000 tagad.
Tas ir tikai n.
>> Tātad, kas ir loģisks secinājums?
Meklējot Mike ar tālruni Grāmata, kas ir n lapas
varētu veikt, jo ļoti sliktākajā gadījumā, cik soļus par kārtību n?
Un tiešām dators zinātnieks teiktu
ka braukšanas laikā, vai sniegumu vai efektivitāte
vai neefektivitāti, par algoritmu, piemēram, lineāra meklēšanu ir kārtībā no n.
Un mēs varam piemērot vienādi loģika šķērsojot kaut ko
kā es tikko darīju uz otro algoritms mums bija ar tālruņa grāmatu,
kur mēs devāmies divas lapas vienlaikus.
>> Tātad 1000 lapa tālruņu grāmata varētu mūs 500 lapa pagriezienus, plus viens
ja mēs dubultā atpakaļ mazliet.
Tātad, ja tālrunis grāmata ir n lapas, bet mēs darām divas lapas vienlaicīgi,
tas ir aptuveni, ko?
N virs diviem, tā ka ir kā n pār diviem.
Bet es sniedza pieprasīt pirms brīža ka n pār two--
tas ir sava veida tāds pats kā tikai n.
Tas ir tikai nemainīgs faktors, datorzinātnieku teiktu.
Pieņemsim tikai koncentrēties uz mainīgie lielumi, really--
lielākais mainīgie vienādojumu.
>> Tātad lineārā meklēt, vai izdarīt vienu lapu laikā, vai divas lappuses tādā laikā,
ir sava veida būtībā ir tas pats.
Tas joprojām ir par kārtību n.
Bet es pieprasīja ar manu attēlu agrāk ka trešais algoritms nebija
lineārs.
Tas nebija taisna līnija.
Tas bija, ka izliekta līnija, kā arī algebriskā formula tur bija tas, ko?
Log N- tā log n bāzi divi.
Un mums nav iedziļināties pārāk daudz sīkāk par logaritmu šodien,
bet lielākā daļa datoru zinātnieki nebūtu pat pateikt, kāda bāze ir.
Jo tas viss ir tikai konstante faktori, tā sakot,
tikai nelielas ciparu atšķirības.
Un tā tas būtu ļoti bieži veids, īpaši formālās datoru
zinātnieki kuģa vai programmētāji pie baltā tāfele
faktiski apgalvojot kas algoritms viņi varētu izmantot
vai kāds efektivitāte par to algoritms ir.
>> Un tas ne vienmēr ir kaut kas jūs apspriest jebkurā detalizēti,
bet labs programmētājs ir kāds, kas ir ciets, oficiālu fona.
Viņš ir spējīgs runāt Jums šāda veida veidā
un faktiski padara kvalitatīvi argumenti par
kāpēc viens algoritms vai viens gabals programmatūru
ir pārāka kaut kādā veidā uz citu.
Tāpēc, ka jūs varētu noteikti ieskriet viena cilvēka programmu
un saskaitīt sekundes kas nepieciešams, lai kārtotu dažus numurus,
un jūs varat palaist kādu otras personas programma
un saskaitīt Sekunžu tas aizņem.
Bet tas ir vispārīgāks tā, ka Jūs varat izmantot, lai analizētu algoritmus,
ja jūs, vienkārši uz papīra vai tikai mutiski.
Bez pat rādīt to, bez pat mēģina izlases ieejas,
Jūs varat vienkārši iemesls caur to.
Un tā ar nomu attīstītājs vai ja kam viņam vai viņai veida apgalvo, lai jums
kāpēc to algoritmu, viņu noslēpums mērce meklēšanai miljardiem
web lapas savam Uzņēmums ir labāk, šie
ir par argumentu veidus tie ideāli būtu iespēja izdarīt.
Vai vismaz tie ir veidu lietas
kas nāks klajā diskusijā, at Vismaz ļoti formālu diskusiju.
Viss kārtībā.
Tātad Ben ierosināja kaut ko sauc izvēle kārtošanas.
Bet es esmu gatavojas ierosināt, ka tur ir citi veidi, kā to izdarīt, too.
Ko man nav tiešām patīk par Bena algoritmu
ir tas, ka viņš tur kājām, vai kam man iet, un atpakaļ
un uz priekšu un atpakaļ un uz priekšu un atpakaļ.
Ko darīt, ja tā vietā, es būtu darīt kaut kas līdzīgs šiem skaitļiem šeit
un man bija tikai nodarbojas ar katru skaits, savukārt, kā es esmu izdarījusi?
>> Citiem vārdiem sakot, šeit ir mans saraksts numuru.
Četri, viens, trīs, divi.
Un es esmu gatavojas darīt turpmāk.
Es esmu gatavojas ievietot numurus kur tie pieder drīzāk
nekā izvēloties tos pa vienam.
Citiem vārdiem sakot, šeit ir numurs četri.
>> Te ir mana sākotnējā sarakstā.
Un es esmu gatavojas, lai saglabātu būtībā jaunu sarakstu šeit.
Tātad tas ir vecais saraksts.
Tas ir jauns saraksts.
Es redzu skaits četri pirmās.
Mans jaunais saraksts ir sākotnēji tukšs, tāpēc tas ir trivially gadījums
ka četri tagad asorti sarakstu.
Es esmu tikai ņemot skaitu es esmu dota, un es varēšu to manā jaunajā sarakstā.
>> Vai šis jaunais saraksts sakārtots?
Jā.
Tas ir muļķīgi, jo tur ir tikai viens elements, bet tas ir absolūti sakārtoti.
Nav nekas nevietā.
Tas ir daudz interesantāk, šis algoritms, kad es pāriet uz nākamo soli.
>> Tagad man ir viens.
Tātad viena, protams, pieder pie sākumā vai beigās šī jaunā saraksta?
Sākums.
Tāpēc man ir darīt kādu darbu tagad.
Esmu bijis ņemot daži brīvību ar manu marķieri
, tikai zīmēšanas lietas kur es gribu viņus,
bet tas nav īsti precīzs datorā.
Dators, kā mēs zinām, ir RAM vai Random Access Memory,
un tas ir viens baits un citu baitu un citu baitu.
Un, ja jums ir gigabaita RAM, jums ir miljards baitu,
bet viņi fiziski vienā vietā.
Jūs varat ne tikai pārvietot sīkumi apkārt vēršot to uz kuģa
kur vien tu vēlies.
Tātad, ja mans jaunais saraksts ir četras vietas atmiņā,
diemžēl četri ir jau nepareizā vietā.
>> Tātad, lai ievietotu numuru viens Es nevaru vienkārši izdarīt to šeit.
Šī vieta atmiņā neeksistē.
Tas būtu krāpšanos, un man ir bijis krāpšanos gleznieciski uz dažām minūtēm
šeit.
Tik tiešām, ja es gribu, lai vienu šeit, Man ir uz laiku kopēt četri
un tad ielieciet vienu tur.
>> Tas ir jauki, ka ir pareizi, tas ir tehniski iespējams,
bet saprotu, ka ir papildu darbs.
Es neesmu vienkārši ielieciet numuru vietā.
Es pirmo reizi nācās pārcelties numurs, tad ielieciet to vietā,
tāpēc es veida dubultojies manu darba apjomu.
Lai saglabātu, ka prātā.
>> Bet es esmu tagad darīts ar šo elementu.
Tagad es gribu, lai greifers numuru trīs.
Kur, protams, tas pieder?
Starp.
Es nevaru pievilt vairs un vienkārši ielieciet to tur,
jo, atkal, šī atmiņa ir fiziskās atrašanās vietas.
Tāpēc man ir kopēt četriem un nodot trīs vairāk nekā šeit.
Nav liels darījumu.
Tas ir tikai viens papildu solis again-- jūtas ļoti lēti.
>> Bet tagad es pāriet uz diviem.
Abi, protams, pieder šeit.
Tagad jūs sākat redzēt, kā darbu var uzkrāt.
Tagad to, kas man ir jādara?
Jā, man ir, lai pārvietotu četri, Man tad ir kopēt trīs,
un tagad es varu ievietot divas.
Un loms ar šo algoritms, interesanti ir tas,
ir tas, ka pieņemsim, mums ir vairāk ekstrēms gadījums, kad tas ir teiksim astoņi, septiņi,
seši, pieci, četri, trīs, divi, viens.
Tas ir, daudzos kontekstos, sliktākajā gadījumā,
jo darn lieta ir burtiski atpakaļ.
>> Tas nav īsti ietekmēt Ben algoritmu,
jo Bena atlasē Kārtot viņš gatavojas glabāt
iet uz priekšu un atpakaļ pa sarakstu.
Un tāpēc, ka viņš vienmēr meklē cauri visai atlikušo sarakstā,
tas nav svarīgi kur elementi ir.
Bet šajā gadījumā ar manu ievietojot approach-- pamēģināsim šo.
>> Tātad, viens, divi, trīs, četri, pieci, seši, septiņi, astoņi.
Viens divi trīs četri, pieci, seši, septiņi, astoņi.
Es esmu gatavojas pieņemt astoņiem, un kur es varu likt to?
Nu, sākumā manu sarakstu, jo šis jaunais saraksts ir sakārtots.
Un es šķērsot to ārā.
>> Kur es varu nodot septiņi?
Darn to.
Tas nepieciešams, lai iet tur, tāpēc Man ir darīt kādu kopēšanu.
Un tagad septiņi iet šeit.
Tagad es pāriet uz sešiem.
Tagad tas ir vēl vairāk darba.
>> Astoņi ir iet šeit.
Seven ir iet šeit.
Tagad seši varētu iet šeit.
Tagad es greifers pieci.
Tagad astoņi ir jāiet šeit, septiņi ir iet šeit,
seši ir iet šeit, un tagad pieci un atkārtot.
Un es esmu diezgan daudz pārvietojot to pastāvīgi.
>> Tātad beigās, šis algorithm-- mēs ņemšu sauc to ievietošanas sort-- faktiski
ir daudz darba, too.
Tas ir tikai atšķirīgs veida darbu nekā Ben s.
Bena darbs bija man iet uz priekšu un atpakaļ visu laiku,
Izvēloties nākamais mazākais elements atkal un atkal.
Tātad tas bija šī ļoti vizuāla veida darbu.
>> Šī otra algoritmu, kas ir joprojām correct-- tas iegūs darbu done--
vienkārši maina darba apjomu.
Izskatās, sākotnēji tu esi ietaupot, jo tu esi tikai
nodarbojas ar katra elementa uzreiz bez kājām visu
ceļu cauri sarakstam kā Ben bija.
Bet problēma ir, it īpaši tās traki gadījumi, kad tas viss ir atpakaļ,
Jūs esat tikko veida atliekot smago darbu
kamēr jums ir noteikt savas kļūdas.
>> Un tāpēc, ja jūs varat iedomāties šo astoņi un septiņi un seši un pieci
un vēlāk četras un trīs un divi pārvietojas savu ceļu cauri sarakstam,
mēs esam tikai mainījusies darba veids mēs darām.
Tā vietā, darot to pie sākumā mana atkārtojuma,
Es esmu tikai darot to pie beigām katra atkārtojuma.
Tātad izrādās, ka šo algoritmu, Arī parasti sauc ievietošanas kārtošanas,
ir arī par kārtību n brusas.
Tas tiešām nav labāka, nav labāka vispār.
>> Tomēr, tur ir trešā pieeja Es aicinu mūs apsvērt,
kas ir šī.
Tātad pieņemsim, ka manu sarakstu, vienkāršības labad atkal, ir četri, viens, trīs,
two-- tikai četri numuri.
Ben bija laba intuīcija, labs cilvēks intuīcija
pirms, ar kuru mēs fiksētu visa uzskaitīt eventually-- ievietošanas veida.
Es coaxed mums līdzi.
Bet pieņemsim apsvērt Vienkāršākais veids, kā noteikt šo sarakstu.
>> Šis saraksts nav sakārtots.
Kāpēc?
Angļu, paskaidrojiet, kāpēc tas nav reāli sakārtoti.
Ko nozīmē nav sakārtoti?
>> STUDENT: Tas nav secīgi.
>> DAVID Malan: Nav secīgi.
Dodiet man piemēru.
>> STUDENT: Put tos kārtībā.
>> DAVID Malan: OK.
Dodiet man vairāk konkrētu piemēru.
>> STUDENT: augošā secībā.
DAVID Malan: Nav augošā secībā.
Precīzāk.
Es nezinu, ko tu domā ar augošā.
Kas noticis?
>> STUDENT: mazākais no skaitļi ir ne pirmajā telpā.
>> DAVID Malan: Vismazāk s ne pirmajā telpā.
Būt konkrētāks.
Es esmu sāk aizķert.
Mēs paļaujamies, bet kāda ir no rīkojuma šeit?
>> STUDENT: ciparu secību.
DAVID Malan: ciparu secību.
Ikviena veida turēšanai tas here-- ļoti augstā līmenī.
Vienkārši burtiski man pateikt, kas ir nepareizi, piemēram, piecus gadus vecs varenību.
>> STUDENT: Plus viens.
>> DAVID Malan: Kas tas ir?
>> STUDENT: Plus viens.
>> DAVID Malan: Ko tu ar to domā plus viens?
Dodiet man cits piecus gadus vecs.
Kas ir nepareizi, mamma?
Kas ir nepareizi, tētis?
Ko nozīmē tas nav sakārtots?
>> STUDENT: Tā nav īstā vieta.
>> DAVID Malan: Kas nav īstajā vietā?
>> STUDENT: Four.
DAVID Malan: Labi, labi.
Tātad četri nav kur tam vajadzētu būt.
Jo īpaši, tas ir labi?
Četri un viens, pirmais divi skaitļi I See.
Vai tas ir labi?
Nē, viņi no rīkojuma, vai ne?
Patiesībā, domāju, ka tagad par datoru, too.
To var apskatīt varbūt tikai vienā, varbūt divas lietas once--
un patiesībā ir tikai viena lieta laikā, bet tas var vismaz
apskatīt viena lieta, tad Nākamā lieta, blakus tai.
>> Tātad tie ir kārtībā?
Protams ka nē.
Tātad, jūs zināt, ko?
Kāpēc mēs mazuli soļi noteikt šo problēmu
nevis uz šiem iedomātā algoritmi, piemēram, Ben, kur
viņš veida nosaka to, looping cauri sarakstam
tā vietā, lai darīt to, ko es darīju, kur Es tikko veida noteikti to, kā mēs ejam?
Pieņemsim tikai burtiski nojauktu jēdziens order-- skaitliskā secībā,
sauc to ko jūs want-- šajās pairwise salīdzinājumus.
>> Četri un viens.
Vai šis ir pareizais pasūtījumu?
Tātad, pieņemsim noteikt, ka.
Viens un četri, un pēc tam mēs vienkārši kopēt to.
Labi, labi.
Es noteikti viens un četri.
Trīs un divi?
Nē.
Ļaujiet mani vārdi atbilstu manu pirkstiem.
Četri un trīs?
>> Tas nav kārtībā, tāpēc es esmu gatavojas darīt vienu, trīs, četri, divi.
Labi.
Tagad četri un divi?
Mums ir nepieciešams, lai to labotu, too.
Tātad, viens, trīs, divi, četri.
Tātad tas ir sakārtoti?
Nē, bet tas ir tuvāk sakārtoti?
>> Tas ir, jo mēs fiksēts šis kļūda, mēs fiksēto šo kļūdu,
un mēs fiksēto šo kļūdu.
Tāpēc mēs fiksēto trīs kļūdas apstrīdami.
Joprojām nav īsti izskatās sakārtots, bet tas ir objektīvi tuvāk sakārtoti
jo mēs fiksēto daži no šīm kļūdām.
>> Tagad to, ko man darīt tālāk?
Es veida sasnieguši sarakstā.
Man šķiet, ir noteikta visas kļūdas, bet ne.
Jo šajā gadījumā, daži skaitļi varētu būt burbuļojot up tuvāk
uz citiem numuriem, joprojām ir bojātas.
Tātad, pieņemsim to darīt atkal, un es ņemšu vienkārši darīt to vietā šoreiz.
Viena un trīs?
Ir labi.
Trīs un divi?
Protams nē, tāpēc pieņemsim mainīt.
Tātad divi, trīs.
Trīs un četru?
Un tagad pieņemsim tikai būt īpaši pedantiska šeit.
Vai tas ir sakārtoti?
Jūs cilvēki zina, tas ir sakārtoti.
>> Man vajadzētu mēģināt vēlreiz.
Tātad Olivia ierosina es mēģinātu vēlreiz.
Kāpēc?
Jo dators nav luksusa mūsu cilvēka acīm
no tikai glancing back-- Labi, es esmu darīts.
Kā dators noteikt ka saraksts tagad sakārtoti?
Mehāniski.
>> Man vajadzētu iet cauri vēlreiz, un tikai tad, ja es
nepadara / atrast nekādas kļūdas es varu tad secināt kā datoru, yep,
mēs esam labi iet.
Tik viens un divi, divi un trīs, trīs un četri.
Tagad es varu pilnīgi teikt, tas ir sakārtoti, jo es nekādas izmaiņas.
Tagad tas būtu kļūda, un tikai muļķīgi, ja es, dators,
lūdza šos pašus jautājumus atkal gaida dažādas atbildes.
Nedrīkst notikt.
>> Un tāpēc tagad saraksts ir sakārtots.
Diemžēl, darba laiks šis algoritms ir arī n brusas.
Kāpēc?
Tāpēc, ka jums ir n skaitļi, un tad, sliktākajā gadījumā jums ir pārvietot n numuriem
n reizes, jo jums ir, lai saglabātu turpinās atpakaļ, lai pārbaudītu un potenciāli noteikt
šie skaitļi.
Un mēs varam darīt vairāk formāla analīze, too.
>> Tātad tas ir viss, ko teikt, mēs esam veikuši trīs dažādas pieejas, kas ir viens
no viņiem uzreiz intuitīvi pie sikspārņu no Ben
uz manu ierosinājumu iekļaut Kārtot uz šo vienu
kur jūs veida aizmirst meža par kokiem sākotnēji.
Bet tad, ja jūs veikt soli atpakaļ, voila, mēs esam noteica šķirošanas jēdzienu.
Tātad tas ir, uzdrošinās teikt, zemāks līmenis varbūt
kā daži no tiem citu algoritmi, bet pieņemsim
redzēt, ja mēs nevaram iztēloties šie veidā šo.
>> Tātad šis ir daži jauki programmatūra, ka kāds
rakstīja izmantojot krāsains bāri, kas ir gatavojas darīt šādi mums.
Katrs no šiem bāriem apzīmē skaitli.
Taller stabiņš, jo lielāks skaits, mazāks ir bārs,
jo mazāks skaits.
Tik ideāli mēs gribam skaistu piramīdu kur tā sākas mazs un kļūst liels,
un tas nozīmētu, ka šie stieņi ir sakārtoti.
Tāpēc es esmu gatavojas iet uz priekšu un izvēlēties, piemēram, Bena algoritms
first-- izvēle kārtošanas.
>> Un paziņojums, ko tas dara.
Veids, kā tie esam izvēlējušies iztēloties šo algoritmu
ir tas, ka, tāpat kā es biju ejot caur manu sarakstu,
šī programma ir iešana izmantojot savu numuru sarakstā,
uzsverot rozā katrā numurs, kas tas meklē.
Un, kas ir aptuveni notikt tieši tagad?
>> Mazākais skaits, kas I vai Ben atklāju pēkšņi
izpaužas pārvietots uz saraksta sākumā.
Un paziņojums viņi darīja izlikt numuru, kas bija tur,
un tas ir perfekti labi.
Man nav iekļuvuši šajā detalizācijas pakāpi.
Bet mums ir nepieciešams, lai ka numurs kaut kur,
tāpēc mēs vienkārši pārcēla to uz open vietas, kas tika izveidots.
Tāpēc es esmu gatavojas, lai paātrinātu šo augšu, jo pretējā gadījumā tas
kļūst ļoti garlaicīgs ātri.
Animācija speed-- tur mēs ejam.
Tāpēc tagad pats princips Man bija piemērojot, bet tu
var sākt justies algoritmu, ja jūs būs, vai redzēt to mazliet skaidrāk.
Un šis algoritms ir sekas Izvēloties nākamo mazāko elementu,
tāpēc jūs gatavojas sākt redzēt to rampas līdz kreisajā pusē.
Un katrā atkārtojumā, kā es ierosināja, tas nedaudz mazāk darba.
Tas nav iet visu ceļu atpakaļ uz kreiso saraksta beigām,
jo tas jau zina, tie ir sakārtoti.
Tātad tas veids uzskata, tāpat kā tas ir paātrinot, kaut arī katrs solis ir
ņemot tādu pašu laiku.
Tur atlikušie tikai mazāk soļus.
Un tagad jūs varat veida sajust algoritms tīrīšanas galu uz augšu tā,
un tiešām tagad tas ir sakārtoti.
>> Tātad ievietošanas kārtošanas ir viss darīts.
Man nepieciešams atkārtoti randomize masīvs.
Un paziņojums Es varu tikai paturēt randomizing to,
un mēs saņemsiet tuvināšanu Tāda pati pieeja, ievietošanas kārtošanas.
Ļaujiet man lēni to šeit.
Sāksim, ka vairāk nekā.
Apstāties.
>> Pieņemsim izlaist četri.
Tur mēs ejam.
Randomize tie masīvs.
Un šeit mēs go-- ievietošanas veida.
Play.
Ievērojiet, ka tas nodarbojas ar katru elements tai rodas uzreiz,
bet, ja tas pieder nepareizā vietā paziņojums
visu darbu, kas ir noticis.
Mums ir saglabāt novirzot vairāk un vairāki elementi, lai padarītu telpu
par kādu mēs vēlamies ieviest.
>> Tātad mēs esam koncentrējoties uz atstāja beigas tikai saraksta.
Paziņojums mēs neesam pat izskatījās at-- mēs nav iezīmēts rozā neko
pa labi.
Mēs esam tikai nodarbojas ar problēmas, kā mums iet,
bet mēs esam radot daudz strādāt par sevi vēl.
Un tāpēc, ja mēs paātrinātu šo augšu tagad iet līdz galam,
tas ir atšķirīgs justies uz to patiešām.
Tas ir tikai koncentrēties uz kreisās beigām, bet darot nedaudz vairāk darba kā needed--
veida nogludināšanas lietām vairāk, nosakot lietas,
bet nodarbojas galu galā ar katrs elements vienam
kamēr mēs nokļūt the-- labi, mēs visi zinām, cik tas beigsies,
tāpēc tas ir mazliet underwhelming varbūt.
>> Bet saraksts end-- spoiler-- tiks sakārtoti.
Tātad aplūkosim vienu pēdējais.
Mēs nevaram vienkārši izlaist.
Mēs esam gandrīz tur.
Divi iet, viens iet.
Un voila.
Excellent.
>> Tāpēc tagad pieņemsim darīt vienu pēdējais, atkārtoti randomizing ar burbulis šķirot.
Un paziņojums šeit, it īpaši, ja es lēni to uz leju, tas saglabā swooping cauri.
Bet paziņojums tas tikai padara pairwise comparisons-- veida vietējiem risinājumiem.
Bet, tiklīdz mēs nokļūt beigām saraksta rozā,
kas notiek, lai būtu neatkārtotos?
Jā, tas nāksies sākt no jauna, jo tas tikai
nefiksētu pairwise kļūdas.
Un kas varētu būt atklāts vēl citus.
Un tādēļ, ja jums paātrināt šo augšu, jūs redzēt, ka, tāpat kā norāda nosaukums,
mazāks elements-- vai drīzāk, lielākās elements-- sāk
burbulis augšu uz augšu, ja jūs.
Un mazāki elementi ir sāk burbulis uz leju pa kreisi.
Un tiešām, tas ir sava veida vizuālo efektu, kā arī.
Un tā tas galu galā apdares ļoti līdzīgā veidā, too.
>> Mums nav kavēties par šo konkrēto vienu.
Ļaujiet man atvērt šo tagad, too.
Ir dažas citas šķirošanas algoritmi visā pasaulē, no kuriem daži
tiek notverti šeit.
Un jo īpaši izglītojamajiem, kuri nav obligāti vizuālā vai matemātiskā,
kā mēs to darījām iepriekš, mēs varam arī izdarīt audially
ja mēs saistīt skaņu ar šo.
Un tikai par jautru, šeit ir daži atšķirīgi algoritmi,
un viens no tiem, jo ​​īpaši jūs esat gatavojas paziņojums sauc par "apvienot kārtošanas."
>> Tas ir tiešām fundamentāli labāks algoritms,
tāds, kas apvienojas veida, kas ir viens no tie, jūs gatavojaties redzēt,
nav kārtībā n brusas.
Tas ir par kārtību n reizes žurnālu n, kas ir pat nedaudz mazāks, un tādējādi
ātrāk nekā šajās citās trim.
Un tur ir pāris citu dumjš tie, kas mēs redzēsim.
>> Tātad, šeit mēs iet ar kādu skaņu.
Tas ir ievietošanas kārtot, lai atkal tas ir tikai nodarbojas ar elementiem
kā viņi nāk.
Tas ir burbulis kārtot, tāpēc tas ir uzskatot tos pārus vienlaikus.
Un atkal, lielākais elementi tiek burbuļošana uz augšu uz augšu.
>> Nākamā atlase kārtošanas.
Tas ir Bena algoritms, kur atkal viņš izvēloties iteratīvi
nākamais mazākais elements.
Un atkal, tagad jūs tiešām var dzirdēt, ka tas ir paātrināt, bet tikai tad, ja
jo tas dara mazāk un mazāk strādāt par katru atkārtojuma.
Šis ir viens ātrāk, apvienot kārtot, kas šķirošanas kopas numuru
kopā un tad apvienojot tos.
Tātad look-- kreiso puse jau ir sakārtoti.
>> Tagad tas ir šķirošana pareizo pusi, un tagad tas notiek, lai tos apvienot vienā.
Tas ir kaut kas ko sauc par "Rūķītis kārtošanas."
Un jūs varat veida redzēt, ka tas notiek uz priekšu un atpakaļ,
Nosakot darbu mazliet šeit un tur pirms tā ieņēmumus, lai jaunu darbu.
Un tas arī viss.
Tur ir cita veida, kas ir tiešām tikai akadēmiskiem mērķiem,
sauc par "stulba veida", kas notiek jūsu dati, sakārto to nejauši,
un pēc tam pārbauda, ​​vai tā ir sakārtots.
Un, ja tas tā nav, tas atkal sakārto to nejauši, pārbauda, ​​vai tas ir sakārtoti,
un, ja nav atkārto.
Un teorētiski, probabilistically tas tiks pabeigta,
bet pēc diezgan daudz laika.
Tas nav pats efektīvu algoritmu.
Tātad kādi jautājumi par tiem īpaši algoritmus vai neko
tur saistīti, too?
>> Nu, pieņemsim tagad kaitināt intervālu, ko visi šīs līnijas ir, ka es esmu zīmēšanas
un to, ko es esmu pieņemot datoru var darīt zem motora pārsega.
Es gribētu apgalvot, ka visi no šiem numuriem Es turpinu drawing-- viņiem ir nepieciešams, lai saņemtu
glabāti kaut kur atmiņā.
Mēs atbrīvoties no šīs puisis tagad, too.
>> Tātad gabals atmiņas A computer-- tāpēc RAM DIMM ir
ko mēs meklēja vakar, dual inline atmiņas module-- izskatās šādi.
Un katrs no šiem maz melnā mikroshēmas ir daži baitu skaitu, parasti.
Un tad zelta tapas ir tāpat kā vadi, kas savieno to ar datoru,
un zaļš silīcija padome ir tikai ko tur viss kopā.
Tātad, ko tas īsti nozīmē?
Ja es veida izdarīt šo pašu attēlu, pieņemsim vienkāršību
ka šis DIMM, dual inline atmiņas modulis,
ir viena gigabaita RAM, viena gigabaita atmiņa, kas ir, cik daudz baitu kopējais?
Viens gigabaitu ir, cik daudz baiti?
Vairāk nekā tas.
1124 ir kilo, 1000.
Mega ir miljoni.
Giga ir miljards.
>> Es guļus?
Vai mēs varam pat lasīt etiķeti?
Tas ir tiešām 128 gigabaitiem, tāpēc tas ir vairāk.
Bet mēs izlikties šis ir tikai viena gigabaita.
Tātad tas nozīmē, ka ir miljards baiti atmiņas pieejami mani
vai 8 miljardi biti, bet mēs ejam runāt ziņā baitu tagad,
kustēties uz priekšu.
>> Tātad, ko tas nozīmē, tas ir viens baits, tas ir vēl viens baits,
Tas ir vēl viens baits, un, ja mēs patiešām vēlējās
par īpašu mums būtu izdarīt miljardu maz kvadrātu.
Bet ko tas nozīmē?
Nu, ļaujiet man tikai tuvinātu kas par šo attēlu.
Ja man kaut ko, kas izskatās piemēram, tas tagad, tas ir četri baiti.
>> Un tā es varētu likt četrus ciparus šeit.
Viens divi trīs četri.
Vai es varētu likt četri burti vai simboli.
"Hei!" varētu iet labi tur, jo katrs no burtiem,
mēs runājām iepriekš, varētu pārstāvēt
ar astoņiem bitiem vai ASCII vai baitu.
Tātad citiem vārdiem sakot, jūs varat likts 8 miljardi lietas iekšā
Šī viena stick atmiņas.
Tagad ko tas nozīmē nodot lietas atpakaļ atpakaļ atpakaļ atmiņā kā šī?
Tas ir tas, ko programmētājs sauktu par "masīvs."
In datorprogrammu, jūs nedomāju par pamatā esošo aparatūru, per se.
Tu tikai domā par sevi kā ar piekļuve miljards baitu kopā,
un jūs varat kaut ko vēlaties ar to.
Bet ērtības labad tas parasti noderīgi
lai saglabātu atmiņas tiesības blakus viens otram, piemēram, šis.
Tātad, ja es tuvinātu this-- jo mēs noteikti nebrauksim
izdarīt miljardu maz squares-- pieņemsim, ka šī padome ir
ka stick atmiņas tagad.
Un es ņemšu tikai izdarīt tik daudz, cik mans marķieris nonāks sniedzot mani šeit.
Tāpēc tagad mums ir stick atmiņas uz kuģa
kas ieguva vienu, divas, trīs, četri, pieci, seši, viens, divi, trīs, četri, pieciem, sešiem,
seven-- tik 42 baiti atmiņas uz ekrāna kopā.
Paldies.
Jā, bija mans aritmētika labi.
Tātad 42 baiti atmiņas šeit.
Tātad, ko tas patiesībā nozīmē?
Nu, dators programmētājs tiešām parasti
domā par šo atmiņā kā Adrešu.
Citiem vārdiem sakot, katrs no šiem vietas atmiņā, aparatūras,
ir unikāla adrese.
>> Tas nav tik sarežģīti kā One BRATTLE Square, Cambridge, Mass., 02138.
Tā vietā, tas ir tikai skaitlis.
Tas ir baitu skaitlis nulle, tas ir viens, tas ir divi, tas ir trīs,
un tas ir 41.
Uzgaidi minūti.
Es domāju, ka es pirms brīža teica 42.
Es sāku skaitīšanas nulles līmenī, tā ka ir faktiski pareiza.
Tagad mums nav reāli izdarīt to kā režģi, un, ja jūs izdarīt to kā režģi
Es domāju, ka lietas tiešām iegūt mazliet maldinošs.
Kāds programmētājs būtu, viņa vai viņas prātā,
parasti domā par šo atmiņa kā ir tāpat kā lentes,
kā gabals maskēšanas lentu ka tikai tālāk un tālāk uz visiem laikiem
vai līdz brīdim, kad jūs darbināt no atmiņas.
Tātad biežāk veids, kā pievērst un tikai domā par atmiņu
varētu būt, ka tas ir baits nulle, viens, divi, trīs, un tad dot, dot, dot.
Un jums ir 42 šādas baiti Kopumā pat gan fiziski tas varētu reāli
būt kaut kas vairāk, kā šis.
>> Tātad, ja jūs tagad domājat par jūsu atmiņa, jo tas, tāpat kā lentes,
tas ir tas, ko programmētājs atkal sauktu masīvu atmiņas.
Un, ja jūs vēlaties, lai faktiski uzglabāt kaut kas datora atmiņā,
jūs parasti darīt veikalu lietas back-to-back to back-to-back.
Tāpēc mēs esam runājuši par skaitļiem.
Un, kad es gribēju, lai atrisinātu problēmas piemēram, četri, viens, trīs, divi,
kaut gan man bija tikai zīmēšanas tikai skaitļi četri, viens, trīs,
divi uz klāja, dators būtu tiešām ir šo iestatījumu atmiņā.
>> Un kāds būtu blakus divi datora atmiņā?
Nu, tur ir ar to nav atbildes.
Mēs īsti nezinām.
Un tik ilgi, kamēr dators nav nepieciešams to,
tas nav vienalga, kas ir nākamais ar skaitļiem tas rūp.
Un, kad es teicu iepriekš, ka ar datoru var tikai aplūkot vienā adresē vienlaicīgi,
Tas ir sava veida kāpēc.
>> Nav atšķirībā ieraksts atskaņotājs un lasīšanas galvu
tikai to var apskatīt noteiktu groove tādā fiziskā vecās skolas ierakstu
laikā, līdzīgi var dators pateicība
tās CPU un tās Intel instrukciju komplekts,
starp kuras instrukciju nolasa no atmiņas
vai saglabāt memory-- dators var tikai apskatīt
vienā vietā pie LAIKU_ dažreiz kombinācija no tiem,
bet tiešām tikai viena vieta laikā.
Tātad, kad mēs darām šie dažādie algoritmi,
Es esmu ne tikai rakstiskā formā vacuum-- četri, viens, trīs, divi.
Šie skaitļi faktiski pieder kaut kur fiziskā atmiņā.
Tātad ir niecīga maz tranzistori vai kāda veida
elektronikas zem pārsegs uzglabāšanai šīs vērtības.
>> Un kopumā, cik bitus iesaistīts tieši tagad, tikai, lai būtu skaidrs?
Tātad šis ir četri baiti, vai tagad tas ir 32 bitu kopā.
Tātad faktiski ir 32 nullēm un tie, kas veido šīs četras lietas.
Tur pat vēl vairāk nekā šeit, bet atkal mēs vienalga par to.
>> Tāpēc tagad pieņemsim lūgt citu Jautājums, izmantojot atmiņu,
jo ka beigās Dienas ir pretrunā.
Nav svarīgi, ko mēs varētu darīt ar dators, beigās, dienā
aparatūras joprojām pats zem motora pārsega.
Kā es uzglabāt vārdu šeit?
Nu, vārdu datorā, piemēram, "Hey!" būtu jāglabā tāpat kā šo.
Un, ja jūs vēlētos ilgāku vārds, jūs varat vienkārši
pārrakstīt kas un teikt kaut ko piemēram, "hello" un veikals, kas šeit.
>> Un tā arī šeit, šajā contiguousness faktiski priekšrocība,
jo dators var vienkārši lasa no labās uz kreiso.
Bet šeit ir jautājums.
Saistībā ar šo vārdu, h-e-l-l-o, izsaukuma zīme,
kā varētu dators zina, kur vārds sākas un kur vārds beidzas?
Saistībā ar skaitļiem, kā tas dators
zināt, cik ilgi secība numuri ir vai ja tas sākas?
Nu, izrādās out-- un mēs neko pārāk daudz
šajā līmenī detail-- datori pārvietoties sīkumi apkārt atmiņā
burtiski veidā šīm adresēm.
Tātad datoru, ja jūs esat rakstot kodu, lai uzglabātu lietas
piemēram, vārdiem, ko tu esi patiešām dara, ir rakstīt
izteicienus, ka atcerēties, kur atrodas datora atmiņa šie vārdi ir.
Tāpēc ļaujiet man darīt ļoti, ļoti vienkāršs piemērs.
>> Es iešu uz priekšu un atvērt vienkāršu teksta programmu,
un es esmu gatavojas, lai radītu fails sauc hello.c.
Lielākā daļa no šīs informācijas mēs neiešu ļoti detalizēti,
bet es esmu gatavojas rakstīt programma tajā pašā valodā,
C. Tas ir daudz biedējoša, Es teiktu, nekā nulles,
bet tas ir ļoti līdzīgs garā.
Patiesībā, šie cirtaini braces-- varat veida
domā par to, ko es tikko darīju, jo tas.
>> Darīsim to, faktiski.
Kad zaļais karogs uzklikšķināt, rīkoties šādi.
Es gribu izdrukāt "sveiki".
Tāpēc tagad tas ir pseudocode.
Es esmu veida nojauc līnijas.
C, šī valoda es runāju par, šī līnija print sveiki
faktiski kļūst "printf" ar dažas iekavas un semikolu.
>> Bet tas ir tieši tā pati ideja.
Un šis draudzīga ļoti "Zaļus karogs uzklikšķināt" kļūst
tik ļoti vairāk arcane "int galvenais spēkā neesošu."
Un tas tiešām nav kartēšanu, tāpēc es esmu tikai gatavojas ignorēt to.
Bet cirtaini bikšturi ir tāpat kā izliektās puzzle gabalus, kā šis.
>> Tātad jūs varat veida uzminēt.
Pat ja jūs nekad neesmu ieprogrammēts agrāk, Kāda šī programma iespējams darīt?
Iespējams drukā sveiki ar izsaukuma zīmi.
>> Tātad, pieņemsim mēģināt to.
Es esmu gatavojas, lai saglabātu to.
Un tas ir, atkal, ļoti vecās skolas vide.
Es nevaru klikšķi, es nevaru vilkt.
Man ir rakstīt komandas.
Tāpēc es gribu palaist savu programmu, lai Es varētu darīt, piemēram hello.c.
Tas ir fails I ilga.
Bet pagaidiet, es esmu trūkst soli.
Ko mēs sakām, ir nepieciešams solis uz valodu, piemēram, C?
Esmu tikko uzrakstījis avotu kods, bet ko man vajag?
Jā, man ir nepieciešams kompilatoru.
Tātad par manu Mac šeit, man ir programmu, ko sauc GCC, GNU C kompilatoru,
kas ļauj man darīt this-- pagriezienu mans source kodu, mēs to saucam,
mašīnu kodu.
>> Un es redzu, ka, atkal, jo šādi, tie
ir nullēm un tie, es tikko izveidots no mana pirmkodu,
visi nullēm un uzņēmumiem.
Un, ja es gribu palaist mans program-- tas notiek
saukt a.out par vēsturiskā reasons-- "sveiki".
Es varu palaist vēlreiz.
Sveiks, sveiks, sveiks.
Un tas, šķiet, darbojas.
>> Bet tas nozīmē, ka kaut kur manā Datora atmiņa ir vārdi
h-e-l-l-o, izsaukuma zīme.
Un izrādās, tāpat kā malā, ko dators būtu tipiski
darīt, ka tā zina, kur lietas sāk un end-- tas ir
gatavojas likt īpašu simbolu šeit.
Un konvencija ir likt skaitlis nulle beigās vārda
lai jūs zināt, kur tas faktiski beidzas, lai jūs
neturiet izdrukāšanu vairāk un vairāk zīmes, nekā jūs faktiski paredzējis.
>> Bet takeaway šeit, pat lai gan tas ir diezgan mistiskā,
ir tas, ka tas galu galā samērā vienkāršs.
Jums tika dota veida lentes, tukšu telpa, kurā jūs varat rakstīt vēstules.
Jums vienkārši ir, lai būtu īpašs simbols, piemēram, patvaļīgi
skaits nulle, lai beigās jūsu vārdi lai dators zina,
oh, man vajadzētu pārtraukt drukāšanu pēc Es redzu izsaukuma zīmi.
Jo nākamais lieta tur ir ASCII vērtība ir nulle,
vai null raksturs kā kāds varētu to sauc.
Bet tur ir sava veida problēmu šeit, un pieņemsim atgriezties
uz numuriem brīdi.
Pieņemsim, ka man, patiesībā, ir masīvs numuru,
un pieņemsim, ka Programma es esmu rakstiski ir
kā grade grāmata par skolotāju un skolotāji klasē.
Un šī programma ļauj viņam vai viņai rakstīt savu skolēnu rezultātus
uz viktorīnas.
Un pieņemsim, ka students saņem 100 par savu pirmo viktorīnu, varbūt
piemēram, 80 uz nākamo, tad 75, tad 90 uz ceturto viktorīnā.
>> Tātad šajā brīdī stāsts, masīvs ir izmēru četri.
Ir absolūti vairāk atmiņu dators, bet masīvs, tā sakot,
ir izmēra četri.
Pieņemsim tagad, ka skolotājs vēlas piešķirt piekto viktorīna uz klasi.
Nu, viena no lietām, ko viņš vai viņai nāksies darīt
tagad uzglabāt papildu vērtību šeit.
Bet, ja masīva skolotājs ir izveidots šajā programmā ir izmērs,
viens no problēmas ar masīva, ka Jūs varat ne tikai saglabāt pievienojot atmiņā.
Jo ko tad, ja otra daļa no Programma ir vārds "hey" labi tur?
>> Citiem vārdiem sakot, mana atmiņa var būt izmantot kaut kādā programmā.
Un, ja iepriekš es drukāti, hey, Es gribu ievadi četriem viktorīnu rādītājus,
viņi varētu iet šeit un šeit.
Un, ja jūs pēkšņi mainīt savas domas vēlāk, un teikt, es gribu piekto viktorīna
rezultāts, jūs varat ne tikai ielieciet to, kur jūs vēlaties,
jo ko tad, ja tas atmiņa tiek izmantota
kaut else-- kādu citu programmu vai kāda cita iezīme programmas
ka jūs strādājat?
Tātad jums ir jādomā iepriekš kā jūs vēlaties, lai saglabātu savus datus,
jo tagad jūs esat krāsotas sevi par digitālo stūrī.
>> Tātad skolotājs varētu vietā teikt, rakstot programmu
uzglabāt viņa vai viņas pakāpes, jūs zināt, ko?
Es esmu gatavojas lūgt, rakstot savu programmu,
ka es gribu nulle, viens, divi, trīs, četri, pieci, seši, astoņi pakāpes kopā.
Tātad, viens, divi, trīs, četri, pieci, seši, septiņi, astoņi.
Skolotājs var tikai nedaudz vairāk, piešķirt atmiņas, rakstot savu programmu
un teikt, jūs zināt, ko?
Es nekad gatavojas piešķirt vairāk kā astoņus viktorīnas šajā semestrī.
Tas ir vienkārši traks.
Es nekad piešķirt to.
Tā, ka šādā veidā viņš vai viņa ir tāda elastība, lai uzglabātu studentu rādītājus,
piemēram, 75, 90, un varbūt kādu papildu kur students ieguva papildu kredītu, 105.
>> Bet, ja skolotājs nekad izmanto šos trīs telpas,
tur ir intuitīvs takeaway šeit.
Viņš vai viņa ir tikai izšķērdēt vietu.
Tātad citiem vārdiem sakot, tur ir šis bieži tradeoff programmēšanā
kur var vai nu piešķirt tieši tā, kā daudz atmiņas, kā jūs vēlaties,
otrādi, kura ir tā, ka tu esi super efficient-- jūs neesat to izšķērdīgs
at all-- bet negatīvie kuru ir tas, kas, ja jūs maināt jūsu prātā, kad
izmantojot programmu, kuru vēlaties saglabāt vairāk datu, nekā jūs sākotnēji paredzēts.
>> Tātad, varbūt risinājums ir, tad, rakstīt savu programmu tādā veidā,
ka viņi izmanto vairāk atmiņas nekā viņi tiešām ir nepieciešams.
Tādā veidā jūs nebrauksim uzskriet šo problēmu,
bet jūs ir izšķērdīgs.
Un jo vairāk atmiņas jūsu programma izmanto, kā mēs apspriedām vakar, jo mazāk
atmiņu, kas ir pieejams uz citām programmām,
jo ātrāk jūsu dators varētu palēnināt uz leju, jo virtuālo atmiņu.
Un tā ideāls risinājums varētu būt tas, ko?
>> Nepietiekami izlietošanai šķiet slikti.
Over-piešķirot šķiet slikti.
Tātad, kādi varētu būt labāks risinājums?
Pārdalīt.
Esiet dinamiskāku.
Nespiediet sevi izvēlēties priori, sākumā, ko jūs vēlaties.
Un, protams, nav pārāk piešķirt, lai jums būtu izšķērdīgs.
>> Un tā, lai sasniegtu šo mērķi, mēs nepieciešams, lai mest šo datu struktūru,
tā sakot, prom.
Un tā, ko programmētājs parasti izmanto
ir kaut kas sauc nav masīvs bet saistīts saraksts.
Citiem vārdiem sakot, viņš vai viņa būs sāk domāt par savu atmiņu
jo pagaidām veida formas, ka viņi var izdarīt šādā veidā.
Ja es gribu, lai saglabātu vienu numuru program-- tāpēc tas ir septembrī
Es esmu devis mani skolēni viktorīna; Es gribu uzglabāt studentu pirmo testu,
un viņi ieguva 100 par it-- I esmu gatavojas lūgt manu datoru,
veidā programmas es esmu rakstīts, vienam rieciens atmiņas.
Un es esmu gatavojas glabāt numurs 100 tajā, un tas arī viss.
>> Tad dažas nedēļas vēlāk kad es varu saņemt savu otro testu,
un ir pienācis laiks, lai rakstītu šajā 90%, es dodos
lūgt datoru, hey, dators, es varu būt vēl rieciens atmiņas?
Tas notiek, lai dotu man šo tukšs rieciens atmiņas.
Es esmu gatavojas īstenot numuru 90, bet manā programmā kaut vai other--
un mums nebūs jāuztraucas par sintakse par this-- man vajag
kaut kā ķēde šīs lietas kopā.
Un es ķēdi kopā ar kas izskatās kā bulta šeit.
>> Trešā spēle kas nāk uz augšu, Es esmu gatavojas teikt, hey, dators,
dod man vēl vienu gabalu no atmiņas.
Un es esmu gatavojas, lai apspiestu kāds tas bija, piemēram, 75,
un man ir ķēdes šim kopā tagad kaut kā.
Ceturtkārt viktorīna nāk kopā, un varbūt kas ir pret semestra noslēgumā.
Un šajā brīdī mana programma varētu būt, izmantojot atmiņu
visas vietas, visā fiziski.
Un tā tikai sākas, es esmu gatavojas izdarīt šo tālāk
quiz-- es aizmirst to, ko tā bija; es domāju, ka varbūt 80 vai something--
kā nekā šeit.
>> Bet tas ir labi, jo gleznieciski Es esmu gatavojas izdarīt šo līniju.
Citiem vārdiem sakot, patiesībā, jūsu datora aparatūru,
pirmais rezultāts varētu galu galā šeit, jo tas ir
labi sākumā semestra.
Nākamais varētu nonākt šeit jo mazliet laika ir pagājis
un programma turpina darboties.
Nākamais rezultāts, kas bija 75, varētu būt vairāk nekā šeit.
Un pēdējais rezultāts varētu būt 80, kas ir vairāk nekā šeit.
>> Tātad patiesībā, fiziski, tas varētu būt kāda datora atmiņā izskatās.
Bet tas nav noderīgs garīgās paradigmu datoru programmētājs.
Kāpēc jums vajadzētu aprūpi, kur heck jūsu dati ir beidzot?
Jūs vienkārši vēlaties, lai uzglabātu datus.
>> Tas ir veida, piemēram, mūsu diskusijas agrāk zīmēšanas kubu.
Kāpēc tu vienalga, ko leņķis ir no kuba
un kā jums ir pārvērst to izdarīt to?
Jūs vienkārši vēlaties kubu.
Tāpat šeit, jums vienkārši vēlaties pakāpē grāmatu.
Jūs vienkārši vēlaties, lai padomātu par to kā numuru sarakstā.
Who cares, kā tas ir īstenoti aparatūru?
>> Tātad abstrakcija tagad ir šo attēlu šeit.
Tas ir saistīts sarakstu, kā programmētājs to sauktu,
ciktāl jums ir sarakstu, protams skaitļu.
Bet tas ir saistīts gleznieciski Ņemot vērā šos bultas,
un visas šīs bultas are-- zem kapuci, ja jūs esat ieinteresēti,
atgādināt, ka mūsu fiziskā aparatūras ir adreses nulle, viens, divi, trīs, četri.
Visas šīs bultas ir ir kā karti vai norādes, kur, ja 90 is-- tagad
Man skaitīt.
>> Nulle, viens, divi, trīs, četriem, pieciem, sešiem, septiņiem.
Izskatās, ka 90 ir atmiņas adrese numurs septiņi.
Visas šīs bultas ir ir kā maza lūžņi papīra
ka dodot rīkojumus programma, kas saka sekot šo karti
nokļūt uz vietu septiņi.
Un tur jūs atradīsiet studenta otrais viktorīna rezultāts.
Tikmēr 75-- ja es turpinu to, tas ir septiņi, astoņi, deviņi, 10, 11, 12,
13, 14, 15.
>> Tas cita arrow tikai atspoguļo karti, lai atmiņas vietā 15.
Bet atkal, programmētājs parasti dara vienalga par šo detalizācijas pakāpi.
Un vairumā katrā programmēšanas valoda šodien, programmētājs
nav pat zināt, kur atmiņā šie skaitļi patiesībā ir.
Viss, ko viņš vai viņa ir rūpēties par ir ka tie ir kaut kas saistīti kopā
tādā datu struktūra, kā šis.
>> Bet izrādās, nav iegūt pārāk tehnisks.
Bet tikai tāpēc, ka mēs varam, iespējams, atļauties šo diskusiju šeit,
pieņemsim, ka mēs vēlreiz šis jautājums šeit no masīva.
Let 's redzēt, ja mēs nožēlojam iet šeit.
Tas ir 100, 90, 75, un 80.
>> Ļaujiet man īsi padara šo apgalvojumu.
Tas ir masīvs, un atkal, spilgta raksturīga masīva
ir tas, ka visas jūsu datu atpakaļ atpakaļ atpakaļ in memory-- burtiski
vienu baitu vai varbūt četri baiti, daži noteikts skaits baitu prom.
In saistīta sarakstā, ko mēs varētu izdarīt kā šis, zem motora pārsega, kas
zina, kur tas sīkumi ir?
Tas nav pat nepieciešams, lai plūst kā šis.
Daži dati var būt atpakaļ pa kreisi tur.
Jums nav pat zināt.
>> Un tā ar masīvu, jums ir iezīme pazīstams kā izlases piekļuvi.
Un ko brīvpiekļuves līdzekļi ir ka dators var lēkt uzreiz
uz jebkuru vietu masīvā.
Kāpēc?
Jo dators zina ka pirmā vieta ir
nulle, viens, divi, un trīs.
>> Un tādēļ, ja jūs vēlaties, lai iet no šis elements uz nākamo elementu,
Jūs burtiski, jo datora prāts, vienkārši pievienot vienu.
Ja jūs vēlaties doties uz trešo elementu, vienkārši pievienojiet one-- nākamo elementu, tikko
pievienot vienu.
Tomēr, šajā versijā stāsts, pieņemsim
dators pašlaik meklē at vai nodarbojas ar numuru 100.
Kā jūs nokļūt uz nākamo pakāpē pakāpei grāmatā?
>> Jums ir jāņem septiņi pakāpieni, kas ir patvaļīga.
Lai nokļūtu uz nākamo, jums ir veikt vēl astoņi soļi, lai saņemtu 15.
Citiem vārdiem sakot, tas nav pastāvīga plaisa starp skaitļiem,
un tāpēc tas tikai ņem dators vairāk laika ir punkts.
Dators ir meklēt caur atmiņu, lai
atrast to, ko jūs meklējat.
>> Tātad, tā kā masīvs mēdz būt ātru datu structure-- jo jums
var burtiski vienkārši darīt vienkāršu aritmētisko un saņemtu, kur jūs vēlaties, pievienojot vienu,
par instance-- saistītu sarakstu, jūs upurēt šo funkciju.
Jūs varat ne tikai iet no pirmā uz otro trešo uz ceturto.
Jums ir jāievēro karti.
Jums ir veikt papildu pasākumus, nokļūt uz tām vērtībām, kas
Šķiet, ka pievienojot izmaksas.
Tātad mēs esam maksājot cenu, bet to, kas bija līdzeklis, kas Dan tika meklē šeit?
Kāda saistītu sarakstu acīmredzot ļauj mums darīt,
kas bija izcelsmes šis konkrētais stāsts?
>> Tieši tā.
Dinamiska lielums uz to.
Mēs varam pievienot šim sarakstam.
Mēs pat varam sarukt sarakstu, lai ka mēs esam tikai izmantojot tik daudz atmiņu
kā mēs tiešām gribam, un tā mēs nekad pārāk izlietošanai.
>> Tagad tikai, lai būtu patiesi gnīda-picky, tur ir slēptās izmaksas.
Tātad jums vajadzētu ne tikai let me pārliecināt Jums, ka tas ir pārliecinošs tradeoff.
Ir vēl viens slēptās izmaksas šeit.
Pabalsts, lai būtu skaidrs, ir tas, ka mēs dinamismu.
Ja es gribu vēl vienu elementu, es varu tikai izdarīt to un nodot numuru tur.
Un tad es varu saistīt ar attēlu šeit,
tā kā vairāk nekā šeit, atkal, ja es esmu krāsotas sevi kaktā,
ja kaut kas cits jau izmanto atmiņas šeit, es esmu no luck.
Esmu gleznojis sevi stūrī.
>> Bet kas ir slēptā izmaksāt šo attēlu?
Tas ir ne tikai daudzums laiks, kas nepieciešams,
aiziet no šejienes uz šeit, kas ir septiņi soļi, tad
astoņi posmi, kas ir vairāk nekā viens.
Kas ir vēl viens slēptās izmaksas?
Ne tikai laiks.
Papildu informācija vajadzīgi, lai sasniegtu šo attēlu.
>> Yeah, ka karte, šie maz lūžņi papīrs, kā es glabāt apraksta tos kā.
Tie arrows-- tie nav bezmaksas.
Computer-- jūs zināt ko dators ir.
Tā ir nullēm un uzņēmumiem.
Ja jūs vēlaties, lai pārstāvētu bultu vai saistīto karti vai vairāki, jums ir nepieciešams dažas atmiņas.
Tātad otrā cenu, jūs maksāt par saistītā sarakstā
kopīga datorzinātnes resurss, ir arī telpa.
>> Un tiešām tā, tik bieži, starp kompromisus
projektēšanas programmatūras inženierijas sistēmas ir laiks un space--
ir divi no jūsu sastāvdaļām, divi Sava visdārgākajām sastāvdaļām.
Tas maksā man vairāk laika jo man ir sekot šo karti,
bet tas arī maksā man vairāk vietas jo man ir, lai saglabātu šo karti apkārt.
Tātad cerība, jo mēs esam sava veida apsprieda vairāk nekā vakar un šodien,
ir tas, ka ieguvumi atsvērs izmaksas.
>> Bet tur nav acīmredzams risinājums šeit.
Varbūt tas ir better-- a la ātri un netīrs,
kā Kareem ierosināts earlier-- mest atmiņu problēmu.
Vienkārši nopirkt vairāk atmiņas, domāju mazāk grūti par atrisinātu problēmu,
un atrisināt to vieglāk veidā.
Un tiešām agrāk, kad mēs runājām par kompromisus,
tas nebija telpu dators un laiks.
Tas bija attīstītājs laiks, kas ir vēl viens resurss.
>> Tātad vēlreiz, tas ir šis balansēšanas akts cenšoties izlemt, kuru no šīm lietām
jūs esat gatavi tērēt?
Kurš ir vislētākais?
Kas dod labākus rezultātus?
Yeah?
>> Patiešām.
Tādā gadījumā, ja Jūs esat pārstāvot numurus ar maps--
tos sauc daudzās valodās "norādes" vai "adreses" -
tas ir divreiz telpu.
Tas nav jābūt tik slikti, kā dubultā, ja tagad mēs esam tikai glabāšanai numurus.
Pieņemsim, ka mums bija glabāšanai pacientu ierakstus hospital--
tāpēc Pierson s vārdus, tālruņu numurus, sociālās apdrošināšanas numuri, ārsts
vēsture.
Šajā ailē var būt daudz, daudz lielāka, un tādā gadījumā
niecīga maz rādītājs, adrese nākamais element-- tas nav liels darījumu.
Tas ir tik bārkstis maksā tas nav svarīgi.
Bet šajā gadījumā, jā, tas ir divkāršojies.
Labs jautājums.
>> Parunāsim par reize mazliet konkrētāk.
Kas ir darba laiks meklējot šo sarakstu?
Pieņemsim, ka es gribēju, lai meklētu cauri visiem studentu pakāpes,
un tur ir n atzīmes Šajā datu struktūra.
Arī šeit mēs varam aizņemties vārdu krājums no agrāk.
Tas ir lineāra datu struktūra.
>> Big O n ir to, kas nepieciešams, lai saņemtu līdz beigām šo datu struktūra,
whereas-- un mēs neesam redzējuši Tas before-- masīvs dod jums
ko sauc nemainīgs laiks, kas nozīmē, vienu soli vai divus soļus vai 10 steps--
nav nozīmes.
Tas ir fiksēts skaitlis.
Tam nav nekāda sakara ar lielums masīva.
Un iemesls tam, atkal, ir brīvpiekļuves.
Dators var vienkārši uzreiz pārietu uz citu vietu,
jo viņi visi vienādi attālums no viss pārējais.
Nav domāšana iesaistīti.
Viss kārtībā.
Tātad, ja es varētu, ļaujiet man mēģināt gleznot pēdējie divi attēli.
Ļoti bieži viens pazīstams kā hash tabulu.
Tātad, lai motivētu šo diskusiju, ļaujiet man domāt par to, kā to izdarīt.
>> Tā kā par šo?
Pieņemsim, ka problēma mēs vēlamies atrisināt tagad
īsteno ar dictionary-- tāpēc viss ķekars angļu vārdiem
vai neatkarīgi.
Un mērķis ir, lai varētu atbildēt jautājumi veidlapas ir tas vārds?
Tātad jūs vēlaties, lai īstenotu pareizrakstības pārbaudītājs, tikko
kā fiziska vārdnīcu ka jūs varat meklēt lietas pat.
Pieņemsim, ka es būtu to darīt ar masīvu.
Es varētu darīt.
>> Un domāju, ka vārdi ir ābolu un banānu un cantaloupe.
Un es nevaru iedomāties augļiem kas sākas ar D, tāpēc mēs esam tikai
nāksies trīs augļus.
Tātad šī ir masīvs, un mēs esam uzglabātu visus šos vārdus
šajā vārdnīcā kā masīva.
Jautājums, tad ir, kā cits jūs varētu uzglabāt šo informāciju?
>> Nu, es esmu veida krāpšanos šeit, jo katrs no šiem burtiem vārdu
ir patiešām individuāls baitu.
Tātad, ja es patiešām gribēju būt gnīda-picky, es tiešām
būt sadalot to augšup daudz mazākos gabalos atmiņas,
un mēs varētu darīt tieši tā.
Bet mēs ejam uzskriet pati problēma kā iepriekš.
Ko darīt, ja, kā Merriam Webster vai Oxford Vai katrs year-- viņi pievienot vārdus
uz dictionary-- mums nav vienmēr vēlas gleznot sevi
kaktā ar masīvu?
>> Tā vietā, varbūt gudrāki pieeja ir likt ābolu savā mezglā vai kastē,
kā mēs teiktu, banānu, un tad šeit mums ir kantalupe.
Un mēs string šīs lietas kopā.
Tātad tas ir masīvs, un tas ir saistīts saraksts.
Ja jūs nevar gluži redzēt, tas tikai saka "masīvs", un tas saka "sarakstu."
>> Tāpēc mums ir tāds pats Precīzi jautājumi kā agrāk,
ar ko mums tagad ir dinamika mūsu saistīta sarakstā.
Bet mums ir diezgan lēns vārdnīcu.
Pieņemsim, ka es gribu, lai sameklētu vārdu.
Tas var aizņemt man Big O n soļi, jo vārds varētu
būt visu ceļu beigās saraksts, piemēram, melones.
Un izrādās, ka plānošanā, kārtot
no Svētais Grāls datu struktūras, ir kaut kas
kas dod jums konstante laiks, piemēram, masīvs
bet kas joprojām sniedz jums dinamismu.
>> Lai mēs varētu būt labākais no abām pasaulēm?
Un tiešām, tur ir kaut kas sauc hash tabulu
kas ļauj jums darīt tieši ka, lai gan apmēram.
Hash tabula ir mīļotājs datu struktūra, kas mums
var iedomāties kā kombinācija no array--
un es esmu gatavojas izdarīt to tāpat this-- un saistīti saraksti
ka es izdarīt kā šis vairāk nekā šeit.
>> Un kā šī lieta darbi ir šāds.
Ja šis now-- hash table-- ir mans trešais datu struktūra,
un es gribu, lai saglabātu vārdi tas, man nav
vēlēties, lai tikai saglabātu visu iepriekš vārdus atpakaļ atpakaļ atpakaļ atpakaļ.
Es gribu, lai piesaistītu kādu informācijas vienību
par vārdiem, kas ļaus me get to, ja tas ir ātrāk.
>> Tātad, ņemot vērā vārdus ābolu un banānu un cantaloupe,
Es apzināti izvēlējos šos vārdus.
Kāpēc?
Kas veida fundamentāli atšķirīgs par trīs?
Kas ir skaidrs?
Viņi sāk ar dažādiem burtiem.
>> Tātad, jūs zināt, ko?
Nevis likt visus Savus vārdus pats spainis, tā sakot,
tāpat vienā lielā sarakstā, kāpēc ne Es vismaz mēģināt optimizāciju
un lai manas saraksti 26/01 tik ilgi.
Pārliecinoši optimizācija varētu būt, kāpēc nav
I-- Ievietojot vārdu šajā datu struktūru,
uz datora atmiņā, kāpēc nav man visu "A" vārdus šeit,
visi "b" vārdi šeit, un visi "c" vārdi šeit?
Tātad tas beidzas līdz liekot ābolu šeit, banānu šeit, kantalupe šeit,
un tā tālāk.
>> Un, ja man ir papildu Vārds like-- kas ir vēl viens?
Apple, banānu, bumbieru.
Ikviens domā par augļu kas sākas ar A, B, vai C?
Blueberry-- perfekta.
Kas notiek, lai galu galā šeit.
Un tā mēs, šķiet, ir nedaudz labāks risinājums,
jo tagad, ja es gribu meklēt ābolu, es
first-- man nav tikai nirt manā datu struktūras.
Man nav nodoties sava datora atmiņā.
Es vispirms apskatīt pirmo burtu.
>> Un tas ir tas, ko dators zinātnieks teiktu.
Jūs hash jūsu datu struktūras.
Jūs veikt savu ieguldījumu, kas šī lieta ir vārds, piemēram, ābolu.
Analizēt to, aplūkojot pirmais burts šajā gadījumā,
tādējādi sajaukšanai to.
Sajaukšanai ir vispārējs termins, ar kuru Jūs lietojat kaut kā priekšnodokli
un jūs ražot kādu produkciju.
Un izejas, jo lieta ir vieta
jūs vēlaties meklēt, pirmais vietu, otrais vietu, trešais.
Tātad ieguldījums ir ābolu, produkcija ir pirmais.
Ieguldījums ir banānu, tad produkcija būtu otrais.
Ieguldījums ir cantaloupe, produkcija būtu trešais.
Ieguldījums ir melleņu, tad produkcija būtu atkal būs otrais.
Un tas ir tas, kas palīdz jums veikt īsceļus caur savu atmiņu
Lai saņemtu vārdiem vai datu efektīvāk.
>> Tagad tas saīsina savu laiku potenciāli ar tik daudz kā viens no 26,
jo, ja jūs pieņemt, ka jums ir tik daudz "A" vārdus kā "z"
vārdi kā "Q" vārdus, kas nav īsti realistic--
Jums nāksies šķībs pāri daži burti alphabet--
bet tas būtu papildu pieeja tas ļauj
jums nokļūt vārdiem daudz ātrāk.
Un patiesībā, sarežģītu programmu, Googles no pasaules,
Facebooks no world-- viņi varētu izmantot hash tabulu
par daudz dažādiem mērķiem.
Bet tie nebūtu tik naivi, tikai apskatīt pirmo burtu
ābolu vai banānu vai bumbieru vai cantaloupe,
jo, kā jūs varat redzēt šos sarakstus joprojām varētu saņemt ilgi.
>> Un tā tas tomēr varētu būt sava veida no linear-- tik veida lēns,
kā ar lielo O n ka mēs apspriests agrāk.
Tātad, ko reālu labs hash tabulu būs do-- tas būs daudz lielāks masīvs.
Un tā izmantos daudz vairāk sarežģīta sajaukšanai funkcija,
tāpēc, ka tas nav tikai apskatīt "a."
Varbūt tas aplūko "a-p-p-l-e" un kaut kā pārvērš šīs piecas vēstules
uz vietu, kur ābolu jāuzglabā.
Mēs vienkārši naivi, izmantojot burtu "a" viens pats, jo tas ir jauki un vienkārši.
>> Bet hash tabulu, kas beigām, jūs varat domāt
no kā kombinācija masīvs, katrs no kuriem
ir saistīts saraksts, kas ideāli jābūt pēc iespējas īsākam.
Un tas nav acīmredzams risinājums.
Patiesībā, daudz smalkas tuning kas iet uz zem motora pārsega, kad
Īstenojot šos veidus sarežģītas datu struktūras
ir tas, kas ir pareizā garums masīva?
Kāda ir pareizā hash funkcija?
Kā jūs uzglabāt lietas atmiņā?
>> Bet saproti, cik ātri šāda veida diskusijas
saasinājās, nu tik tālu, ka tas ir sava veida no virs galvas šajā brīdī, kas
ir labi.
Bet mēs sākām, atgādināt, ar patiesi kaut zema līmeņa un elektroniski.
Un tā tas atkal ir šis tēma abstrakcijas,
kur reiz sākat lietot, lai piešķirts, OK, es esam ieguvuši it-- tur
fiziskā atmiņa, Labi, sapratu, ik fiziskā atrašanās vieta ir piegādes adrese,
Labi, es saņēmu to, es varu pārstāvēt šie adreses kā arrows--
Jūs varat ļoti ātri sākt būt sarežģītākus sarunas, kas
beigās, šķiet, ir ļaut mums lai risinātu problēmas, piemēram, meklējot
un šķirošanas efektīvāk.
Un esiet droši, too-- jo es domāju, ka tas
ir dziļākais mēs esam aizgājuši par dažām Šo CS tēmām proper--, esam
darīts dienā un pusi pie šī norādīt, ko jūs varētu parasti darīt pāri
kurss astoņas nedēļas semestrī.
>> Visus jautājumus par šo?
Nē?
Viss kārtībā.
Nu, kāpēc nav mēs pauze tur, sākt pusdienas dažas minūtes sākumā,
atsākt tikai par stundu?
Un es kavēties mazliet ar jautājumiem.
Tad es esmu nāksies iet veikt pāris zvanus, ja tas ir OK.
Es ieslēgt kādu mūziku pa to laiku, bet pusdienas būtu ap stūri.