>> SPEAKER 1: Labi, tāpēc tas ir CS50 Tas ir nedēļas beigām pieci.
Un atgādināt, ka pēdējo reizi, kad mēs sākās apskatot mīļotājs datiem
struktūras, kas sāka risināt problēmas, kas sāka ieviest
jaunas problēmas, bet galvenais, lai tas bija tāda veida Threading, ka mēs
sāka darīt no mezgla uz mezglu.
Tātad tas, protams, ir atsevišķi saistīts saraksts.
Un atsevišķi saistītas, Es domāju, ka ir tikai viens
diegu starp katru no šiem punktiem.
Izrādās, jūs varat darīt mīļotājs lietas, piemēram, divkārt saistītas sarakstos
saskaņā ar kuru jums ir bultiņa notiek abos virzienos, kas
var palīdzēt ar konkrētiem efektivitāti.
Bet tas atrisināja problēmu?
Kāda problēma bija šo atrisināt?
Kāpēc mēs rūpējamies pirmdien?
Kāpēc, teorētiski, vai mēs rūpējamies pirmdien?
Ko tas dara?
>> Mērķauditorija: Mēs varam dinamiski mainīt to.
>> SPEAKER 1: OK, lai mēs varētu dinamiski mainīt to.
Labi darīts jums abiem.
Tātad jūs varat dinamiski mainīt šo datu struktūra, bet masīva,
Atsaukt, jums ir jāzina priori, cik daudz vietas vēlaties
un, ja jums ir nepieciešams mazliet vairāk telpa, tu esi veida no luck.
Jums ir izveidot pilnīgi jaunu klāstu.
Jums ir pārvietot visas jūsu dati no viena uz otru,
beidzot atbrīvotu veco masīvs ja jūs varat, un tad doties.
Kas vienkārši jūtas ļoti dārgi un ļoti neefektīva, un tas patiešām var būt.
Bet tas vēl nav viss labi.
Mēs maksājam par cenu, kas bija viens no vairāk acīmredzamas cenām mums
samaksāt, izmantojot saistīts sarakstu?
>> Mērķauditorija: Mums ir jāizmanto dubultā platība katram.
SPEAKER 1: Jā, tāpēc mums ir nepieciešams vismaz divreiz tik daudz vietas.
Patiesībā, es sapratu, tas bildes pat nedaudz maldinošs,
jo par CS50 IDE ir daudz mūsdienu datori, rādītājs vai adrese
nav faktiski četri baiti.
Tas ir ļoti bieži šiem dienas astoņi baiti, kas
ir apakšā visvairāk taisnstūri tur patiesībā
ir sava veida divreiz liels, kā tas, ko es esmu sastādīts,
kas nozīmē, ka jūs izmantojat trīs reizes daudz vietas, kā mēs varētu būt citādi.
Tagad tajā pašā laikā, mēs esam joprojām runā baiti, vai ne?
Mēs ne vienmēr runā megabaiti vai gigabaiti,
ja vien šie dati struktūras iegūt lielas.
>> Un tāpēc šodien mēs sākam apsvērt kā mēs varētu izpētīt datus
efektīvāk, ja Fakts, dati kļūst lielāka.
Bet pamēģināsim canonicalize darbības pirmie
ka jūs varat darīt, par šiem veida datu struktūras.
Tātad kaut kā saistīts sarakstu kopumā atbalsta
operācijas, piemēram, dzēst, ievietot, un meklēt.
Un ko es ar to domā?
Tas tikai nozīmē, ka parasti, ja cilvēki izmanto saistītas sarakstu,
viņi vai kāds cits ir īstenojusi funkcijas, piemēram, dzēst, ievietot,
un meklēt, lai jūs varētu faktiski darīt kaut ko
noderīgs ar datu struktūru.
Tātad pieņemsim ātri apskatīt pie kā mēs varētu īstenot
daži kods saistītu sarakstu šādi.
>> Tātad tas ir tikai daži C kods, nav pat pabeigta programma
ka es tiešām ātri saputo.
Tas nav online izplatīšanā kodu, jo tas nav reāli darboties.
Bet paziņojums es tikko ar komentāru teica:
dot dot dot, tur ir kaut kas tur, dot dot dot, kaut ko tur.
Un pieņemsim tikai apskatīt kādi sulīgs daļas ir.
Tātad uz līnijas trīs, atgādina, ka tas ir tagad
mēs ierosinājām deklarējot mezglu pēdējo laiks, viens no šiem taisnstūra objektu.
Tas ir int, ka mēs saucam N, bet mēs varētu to nosaukt kaut,
un tad struct mezglā zvaigzne sauc nākamo.
Un tikai, lai būtu skaidrs, ka otrais line, on line seši, kas tas ir?
Ko tas dara mums?
Jo tas, protams, izskatās vairāk mistisks nekā mūsu parastajiem mainīgajiem.
>> Mērķauditorija: Tas padara to pāriet vienu.
>> SPEAKER 1: Tas padara to pāriet vienu.
Un precīzāk, tas būs saglabāt adresi
mezgla, kas ir domāts, lai būtu semantiski blakus tai, vai ne?
Tātad tas nav gatavojas obligāti pārcelties neko.
Tas ir tikai gatavojas saglabātu vērtību,, kas ir
būs adresi dažu citu mezglu,
un tas ir iemesls, kāpēc mēs esam teica struct mezglā zvaigzne, zvaigzne apzīmē
rādītājs vai adresi.
Labi, tāpēc tagad, ja jūs pieņemt, ka mēs esam šis N pieejams pie mums, un pieņemsim
pieņemu, ka kāds cits ir Iekļauj visu ķekars integers
uz saistīts sarakstā.
Un tas saistīts saraksts norādīja uz ko kādā brīdī
mainīgais sauc sarakstu, kas ir pagājis šeit kā parametrs,
Kā es varu iet par tiešsaistes 14. Īstenojot meklēšanu?
Citiem vārdiem sakot, ja es esmu īstenošanai funkcija, kuras mērķis dzīvē
ir veikt int un tad sākums saistīts saraksta
ka ir pointers uz saistītā sarakstā.
Tāpat kā pirmā, kas es domāju Dāvidu bija mūsu brīvprātīgais pirmdien,
viņš norādot viss saistīts saraksts,
tas ir tā, it kā mēs iet Dāvids kā mūsu arguments šeit.
Kā mēs iet par šķērso šo sarakstu?
Nu, izrādās, ka, lai gan norādes ir salīdzinoši jauns, tagad pie mums,
mēs varam izdarīt salīdzinoši vienkāršākā.
>> Es iešu uz priekšu un atzīt pagaidu mainīgo, kas
pēc vienošanās ir tikai gatavojas varētu saukt rādītājs, vai PTR,
bet jūs varētu sauc to kaut ko vēlaties.
Un es esmu gatavojas, lai sāktu tā sākuma saraksta.
Tātad jūs varat veida domā par to kā man skolotāja citu dienu,
veida norādot uz kādu starp mūsu cilvēkiem, kā brīvprātīgajiem.
Tāpēc es esmu pagaidu mainīgo, kas ir tieši norādot uz to pašu
ka mūsu nejauši nosaukts brīvprātīgais Dāvids bija arī norādot.
Tagad, kamēr rādītājs ir nav null, jo atsaukums
ka null ir dažas īpašas Sentinel vērtība norobežo galu saraksta,
Tāpēc, kamēr es neesmu norādot uz zemes tāpat kā mūsu pēdējā brīvprātīgais
bija, iesim uz priekšu un darīt šādi.
Ja pointer-- un tagad es veida gribu darīt to, ko mēs darījām ar studentu
structure-- ja rādītājs dot blakus equals-- diezgan, ja rādītājs dot N vienāds
vienāds mainīgo N, tad Arguments, ka ir bijis pieņemts,
tad es gribu iet uz priekšu un teikt atgriezties taisnība.
Atradu numuru N iekšpusē viens no mezgliem mana saistīta sarakstā.
Bet dot vairs darbojas šajā kontekstā,
jo rādītājs, PTR, ir patiešām rādītājs, adrese,
mēs faktiski var lieliski izmantot beidzot gabals sintakses
šāda veida padara intuitīva sajūta un faktiski
izmantojiet bultiņu šeit, kas nozīmē aiziet no šī adrese uz skaitlim tur in.
Tātad, tas ir ļoti līdzīgs gars ar dot operatoram,
bet tāpēc, ka rādītājs nav rādītājs un nav faktiskā struct pati,
mēs tikai izmantot bultiņu.
>> Tātad, ja pašreizējais mezglā ka es, tad pagaidu mainīgo, esmu norādot
nav N, ko es gribu darīt?
Nu, ar saviem brīvprātīgajiem ka mums bija šeit citu dienu,
ja mans pirmais cilvēks nav viens es gribu, un varbūt otrais cilvēks nav
vienu es gribu, un trešais, es ir nepieciešams, lai saglabātu fiziski pārvietojas.
Tāpat kā es varu soli pa sarakstu?
Kad mums bija masīvs, jums vienkārši darīja tāpat I plus plus.
Bet šajā gadījumā, pietiek do rādītāju, saņem, rādītāju, blakus.
Citiem vārdiem, nākamais lauks ir tāpat kā visas kreisā rokās
ka mūsu cilvēku brīvprātīgie pirmdien bija izmantojot norādīt uz kādu citu mezglu.
Tie bija viņu nākamie kaimiņi.
>> Tātad, ja es gribu, lai soli pa šo sarakstu, Es nevaru vienkārši man plus plus vairs,
Man gan jāsaka Es, rādītājs, kas notiek
uz vienāda neatkarīgi nākamais lauks ir, nākamais lauks, nākamais lauks ir,
pēc visām šīm kreisās rokas ka mums bija uz skatuves norādot
dažiem turpmākajiem vērtībām.
Un, ja man cauri ka viss atkārtojuma,
un, visbeidzot, es hit null, kam nav konstatēts N vēl, es vienkārši atgriezties viltus.
Tātad vēlreiz, viss, ko mēs darām šeit, kā vienu attēlu pirms brīža,
sāk norādot ne sākot no saraksta iespējams.
Un tad es varētu pārbaudīt, ir vērtība Es meklēju vienāds ar deviņiem?
Ja tā, tad es atgrieztos taisnība, un es esmu darīts.
Ja nē, es atjaunināt manu roku, AKA rādītājs, norādīt
nākamajā ARROW atrašanās vietu, un Tad Nākošais atrašanās vietu,
un nākamo.
Es esmu vienkārši ejot pa šo masīvu.
>> Tātad vēlreiz, kurš rūpējas?
Tāpat kā to, kas ir šī sastāvdaļa atrast?
Nu, atgādināt, ka mēs ieviesām jēdziens kaudze, kas
ir abstrakts datu tips, ciktāl tas ir nav C lieta, tas nav CS50 lieta,
tas ir abstrakts ideja, šī ideja kraušanas lietas virsū viens otram
ka var īstenot ķekarus dažādos veidos.
Un viens no veidiem, mēs ierosinājām, bija ar masīvs, vai ar saistīta sarakstu.
Un izrādās, ka kanoniski A kaudze atbalsta vismaz divas operācijas.
Un buzz vārdi ir push, lai push kaut uz kaudze,
piemēram, jaunu paplāti ēdamzāle, vai pop,
kas nozīmē noņemt augšējais paplāte no skursteņa ar ēdamistabas
halle, un tad varbūt daži citas darbības, kā arī.
Tātad, kā mēs varbūt definētu struktūru ka mēs tagad zvanot kaudze?
>> Nu, mums ir visi vajadzīgie sintakse mūsu rīcībā C. es saku,
man tipa definīciju struct iekšpusē kaudze,
Es esmu gatavojas teikt, ir masīvs, kādas viss ķekars numuriem, un pēc tam izmēra.
Tātad citiem vārdiem sakot, ja es gribu lai īstenotu šo kodu,
ļaujiet man iet un tikai veida izdarīt to, kas tas ir saprotams.
Tātad tas ir saprotams, dod man struktūra, kas ir ieguvuši masīvu,
un es nezinu, kas jauda ir, tas acīmredzot daži konstante, kas es esmu
noteikts citur, un tas ir jauki.
Bet pieņemsim, ka tas ir tikai viens, divi, trīs, četri, pieci.
Tātad jauda ir 5.
Šis elements iekšpusē manu struktūra sauks numurus.
Un tad man tas ir nepieciešams cits mainīgais acīmredzot
sauc lielums ka sākotnēji es eju noteikt, tiek inicializēts ar nulli.
Ja tur nekas kaudze, izmērs ir nulle,
un tas ir atkritumu vērtības numuriem.
Man nav ne jausmas, kas tur tikai pagaidām.
>> Tātad, ja es gribu, lai push kaut uz kaudze,
domāju, ka es aicinu funkciju push, un Es saku push 50, piemēram, numuru 50,
kur jūs ierosināt Es izdarīt to šajā masīvā?
Ir piecas dažādas iespējamās atbildes.
Ja jūs vēlaties, lai push numuru 50?
Ja mērķis šeit, atkal, zvaniet funkcija push, iet uz argumentu
50, kur es varu likt to?
Pieci possible-- 20% iespēja guessing pareizi.
Jā?
>> Mērķauditorija: Far labi.
>> SPEAKER 1: Far labi.
Tagad ir 25% iespēja guessing pareizi.
Tā, ka faktiski nebūtu labi.
Pēc vienošanās, es saku ar masīvu, mēs parasti sākas no kreisās
bet mēs, protams, var sākas labi.
Tātad spoileris šeit būtu es esmu iespējams, gatavojas izdarīt to pa kreisi,
tāpat kā parastā masīvs kur Man sāk iet no kreisās uz labo.
Bet, ja jūs varat uzsist aritmētiskais, naudas sodu.
Tas vienkārši nav parasto.
Labi, man ir nepieciešams veikt vienu vairāk maiņa though.
Tagad, ka es esmu kaut ko uzstāja uz steku, ko tālāk?
>> Labi, man ir pieauguma lielumu.
Tāpēc ļaujiet man iet uz priekšu un vienkārši atjaunināt tas, kas bija nulle.
Un tā vietā, tagad, es eju likt vērtības vienā.
Un tagad domāju, ka es push citu numurs uz steku, piemēram, 51.
Nu, man ir padarīt vēl viens izmaiņas, kas ir līdz ar izmēru diviem.
Un tad es domāju, ka push vēl viens numurs uz kā 61 kaudze,
tagad man ir nepieciešams, lai atjauninātu izmēru vēl viens laiks, un iegūt vērtību 3, lielums.
Un tagad domāju, ka es aicinu pop.
Tagad pop, pēc vienošanās, neņem argumentu.
Ar steku, viss punkts paplātes metafora
ir tas, ka jums nav rīcības brīvības iet saņemt šo paplāti, visu jūs varat darīt
ir pop augšējais vienu no kaudze, tikai tāpēc, ka.
Tas, ko šis datu struktūra dara.
>> Tātad, šī loģika, ja es saka pop, kas nāk nost?
Tātad 61.
Tātad, kas īsti ir dators darīsim atmiņā?
Kāda mans kods ir jādara?
Ko jūs varētu ieteikt mēs mainīt uz ekrāna?
Kas būtu jāmaina?
Sorry?
Tātad, mēs atbrīvoties no 61.
Tāpēc es varu noteikti darīt.
Un es varu atbrīvoties no 61.
Un tad kāds cits izmaiņas nepieciešams notikt?
Izmērs, iespējams, ir doties atpakaļ uz diviem.
Un tā tas ir jauki.
Bet pagaidiet minūti, izmērs pirms brīža bija trīs.
Pieņemsim tikai darīt ātri veselība pārbaudītu.
Kā mēs zinām, ka mēs vēlējās atbrīvoties no 61?
Jo mēs esam popping.
Un tāpēc man ir šī otrā īpašuma lielumu.
>> Pagaidiet minūti, es esmu domāšana atpakaļ uz nedēļu divām
kad mēs sākām runāt par bloki, kur tas bija vieta nulle,
tas bija vieta viens, tas bija vieta divi, tas ir vieta trīs, četri,
izskatās, ka Saistība starp izmērā
un elements, kas es gribu noņemt no masīva, šķiet, tieši tas, ko?
Size mīnus viens.
Un tā tas ir, kā par cilvēkiem mēs zinām, 61 ir pirmajā vietā.
Kā ir dators gatavojas zināt?
Kad jūsu kods, kur jūs, iespējams, gribu darīt izmērs mīnus viens,
tā trīs mīnus viens ir divi, un ka nozīmē, ka mēs gribam, lai atbrīvotos no 61.
Un tad mēs varam patiesi atjaunināt tā šī izmēra lielums tagad
iet no trim līdz tikai divi.
Un tikai, lai būtu pedantiska, es eju ierosināt, ka es esmu darījis, vai ne?
Jūs ierosināja intuitīvi pareizi man vajadzētu atbrīvoties no 61.
Bet es neesmu veida kārtot gotten atbrīvoties no 61?
Esmu aizmirsis efektīvi ka tas ir faktiski tur.
Un domāju, ka atpakaļ uz PSET4, ja esat izlasīt raksts par kriminālistikas, PDF
ka mums bija jūs guys lasīt, vai jūs lasīt šonedēļ PSET4.
Atgādināt, ka tas ir faktiski piederīgs visa ideja par datoru kriminālistikas.
Kas dators parasti dara, ir tā vienkārši aizmirst, kur kaut kas ir,
bet tas nav iet un, piemēram, mēģināt saskrāpēt to, vai ignorēt
šie gabaliņi ar nullēm un uzņēmumiem vai kādu citu izlases modelis
Ja vien jūs pats to darīt apzināti.
Tātad jūsu intuīcija bija labi, pieņemsim atbrīvoties no 61.
Bet patiesībā, mums nav apnikt.
Mums ir nepieciešams, lai aizmirst, ka tas ir tur, mainot savu izmēru.
>> Tagad tur ir problēma ar šo kaudze.
Ja es glabāt stumšanas lietas uz steku, kas ir
acīmredzot notiks tikai dažus mirkļus laikā?
Mēs ejam, lai pietrūkt vietas.
Un ko mēs darām?
Mēs esam veida ieskrūvē.
Šis īstenošana neļauj mums mainīt masīvs, jo, izmantojot
Tas sintakse, ja jums domāju, ka atpakaļ uz nedēļu divām,
kad jūs esat deklarēta lielums masīva,
mēs neesam redzējuši mehānismu vēl kur Jūs varat mainīt izmēru masīva.
Un tiešām C nav šo funkciju.
Ja jūs sakāt man pieci Nths, viņiem piezvanīt numurus,
tas ir viss, jūs gatavojas, lai saņemtu to.
Tāpēc mēs tagad darīt, jo pirmdien, ir spēja izteikt risinājumu
lai gan, mums ir nepieciešams, lai kniebiens definīcija mūsu kaudze
ne būt daži iekodēts masīvs, bet tikai, lai uzglabātu adresi.
>> Tagad, kāpēc tas ir?
Tagad mums vienkārši ir, lai būtu ērti ar tas, ka tad, kad mana programma darbojas,
Es esmu domājams gatavojas ir jālūdz cilvēkresursus,
cik skaitļi jūs vēlaties saglabāt?
Tātad ievade ir jānāk no kaut.
Bet tad, kad es zinu, ka numurs, tad es varu tikai
izmantot to, kas darbojas, lai sniegtu man rieciens atmiņas?
Es varu izmantot malloc.
Un es varu teikt jebkuru skaitu bytes Es gribu atpakaļ uz šiem Nths.
Un viss, kas man ir, lai glabāt numuriem mainīgs šeit iekšā šajā struct
vajadzētu būt, ko?
Kas patiesībā tērēta skaitļi šajā scenārijā?
Jā, pointers uz pirmo baitu šī rieciens atmiņas,
vai precīzāk, adrese no pirmo no minētajiem bytes.
Nav svarīgi, vai tas ir viens baitu vai viens miljards baitu,
Man vienkārši vajag rūpēties par pirmo.
Jo tas, ko malloc garantijas un Mani operētājsistēmas garantijas,
ir tas, ka rieciens atmiņas I iegūt, tas būs blakus.
Tur nebūs nepilnības.
Tātad, ja es esmu lūgusi 50 baiti vai 1000 baiti,
viņi visi būs atpakaļ atpakaļ atpakaļ.
Un tik ilgi, cik es atceros, cik liels, cik daudz es lūdza, visi man ir nepieciešams zināt
ir pirmais šāda adrese.
>> Tāpēc tagad mums ir iespēja kodu.
Kaut gan, tas notiek, lai mūs vairāk laika, lai rakstītu šo augšu,
Tagad mēs varētu pārdalīt šo atmiņu, vienkārši uzglabātu citu adresi tur
ja mēs gribam lielāka vai pat mazāku rieciens atmiņas.
Tātad šeit, lai tirdzniecības off.
Tagad mēs dinamismu.
Mums joprojām ir contiguousness Es esmu apgalvojot.
Jo malloc dos mums blakusesoši rieciens atmiņas.
Bet tas būs sāpes kakls mums, programmētājs,
faktiski kods up.
Tas ir tikai vairāk darba.
Mums ir nepieciešams kods līdzīgs, ko es biju banging ārā tikai pirms brīža.
Ļoti veicams, bet tas padara sarežģītāku.
Un tā attīstītājs laiks, programmētājs laiks ir vēl viens resurss
ka mums, iespējams, vajadzēs tērēt kādu laiku, lai iegūtu jaunas funkcijas.
Un tad, protams, ir rinda.
Mēs ne iedziļināties šajā viens daudz sīkāk.
Bet tas ir ļoti līdzīgs garā.
Es varētu ieviest rindā, un tās atbilst operācijas,
Enqueue vai dequeue, piemēram, pievienot vai noņemt, tas ir tikai mīļotājs veids, kā pateikt to,
Enqueue vai dequeue šādi.
Es varu tikai dot sev struct ka atkal ir vairāki ir masīvs,
kas atkal ir izmēru, bet kāpēc man tagad vajag
sekot priekšā rindā?
Man nav nepieciešams zināt priekšējo mana kaudze.
Nu, ja es atkal priekšlikums queue-- pieņemsim tikai grūti
kodēt to kā, kam, piemēram, pieci skaitļu šeit potenciāli.
Tāpēc tas ir nulle, viens, divi, trīs, četri.
Tas būs sauktie skaitļi vēlreiz.
Un tas tiks saukts izmērs.
>> Kāpēc tas nav pietiekami, lai ir tikai izmēru?
Nu, pieņemsim virzīt tos pašus numurus.
Tāpēc es pushed-- es enqueued vai stumšanai.
Tagad es ņemšu ierindod 50, un pēc tam 51, un pēc tam 61, un dot dot dot.
Tātad tas ir Enqueue.
Es enqueued 50, tad 51, tad 61.
Un tas izskatās identiski uz kaudze līdz šim,
izņemot man ir nepieciešams veikt vienu maiņu.
Man vajag, lai atjauninātu šo lielumu, tāpēc es dodos no nulles līdz vienam līdz diviem līdz trīs tagad.
Kā es varu dequeue?
Kas notiek ar dequeue?
Kam būtu jānāk pie šī saraksta pirmais ja tas ir līnija pie Apple Store?
Tātad 50.
Tātad, tas ir sava veida sarežģītāk šoreiz.
Tā kā pēdējo reizi tas bija super viegli vienkārši darīt izmērs mīnus viens,
Man uz beigām mana masīva efektīvi ja šie skaitļi ir, tas noņem 61.
Bet es negribu, lai novērstu 61.
Es gribu, lai 50, kurš bija tur at 5:00
rindā, lai Jaunais iPhone vai plauktiņš.
Un tāpēc, lai atbrīvotos no 50, es nevar vienkārši izdarīt, vai ne?
Es varu izsvītrot 50.
Bet mēs tikko teica, ka mums nav jābūt tik Anal
kā lai nesaskrāpētu ārā vai paslēptu datus.
Mēs varam vienkārši aizmirst, kur tas ir.
>> Bet, ja es varu mainīt savu izmēru tagad divi, tas ir pietiekama informācija
zināt, kas notiek manā rindā?
Ne īsti.
Tāpat kā mans izmērs ir divi, bet ja nav rinda sākas,
it īpaši, ja man vēl ir šie paši skaitļi atmiņā.
50, 51, 61.
Tāpēc man ir nepieciešams atcerēties tagad, kad priekšā ir.
Un tā kā es ierosināju up tur, mēs esam vienkārši sauc
N priekšā, kuru sākotnējais vērtība būtu bijis, ko?
Zero, tikai sākums saraksta.
Bet tagad papildus decrementing lielums, mēs vienkārši pieauguma priekšā.
Tagad šeit ir vēl viena problēma.
Tātad, kad es turpinu iet.
Domāt, tas ir skaitlis no piemēram, 121, 124, un pēc tam, Nolāpīts,
Es esmu no kosmosa.
Bet pagaidiet minūti, es neesmu.
Tātad šajā brīdī stāsts, domāt, ka izmērs ir viens, divi,
trīs, četri, tā domāt, ka izmērs ir četri, priekšējā ir viens,
tā 51 atrodas priekšpusē.
Es gribu, lai citu numuru šeit, bet, dammit, es esmu no kosmosa.
Bet es neesmu īsti, vai ne?
Kur es varētu likt kādu papildu vērtību, piemēram, 171?
Jā, es varētu tikai veida atgriezties tur, labi?
Un tad izsvītrot no 50, vai tikai pārrakstīt ar 171.
Un, ja jūs esat jautājums, kāpēc Mūsu numuri dabūja tik nejauši,
tie ir parasti ņem datoru zinātņu kursus Hārvardas pēc CS50.
Bet tas bija labs optimizācija, jo tagad es neesmu izšķērdēt telpā.
Man joprojām ir jāatceras cik liela šī lieta ir kopā.
Tas ir pieci kopā.
Jo es negribu sākt pārrakstot 51.
Tāpēc tagad es esmu vēl no vietas, tā pati problēma kā iepriekš.
Bet jūs varat redzēt, kā tagad savu kodu, jūs, iespējams,
ir uzrakstīt mazliet vairāk sarežģītība, lai tas notiktu.
Un patiesībā, ko operators C droši vien ļauj
jūs maģiski to izdarītu riņķveida?
Yeah Modulo operators, procentuālais zīme.
Tātad, kas ir sava veida atdzist apmēram rindā, pat ja mēs turpinām zīmēšanas bloki
kā šajās piemēram taisnām līnijām, ja jums veida domāt par to, kā izliecas
apkārt kā apli, tad vienkārši intuitīvi tā veida darbojas garīgi
Es domāju, ka nedaudz vairāk tīri.
Jums joprojām būs jāīsteno ka garīgā modelis kodu.
Tātad nav tik grūti, galu galā, lai īstenotu,
bet mēs joprojām zaudēt size-- drīzāk, Spēja mainīt, ja vien mēs to izdarītu.
>> Mums ir atbrīvoties no masīva, mēs aizstāt ar vienu rādītāju,
un tad kaut kur manā kodu Man zvanu, kādu funkciju, lai faktiski izveidot
masīvs sauktie skaitļi?
Malloc, vai kādu līdzīgu funkcija, tieši tā.
Visus jautājumus par skursteņi vai rindas.
Yeah?
Labs jautājums.
Ko Modulo jūs izmantojat šeit.
Tātad kopumā, ja izmanto mod, jūs varētu darīt to
ar izmēru no Visa datu struktūra.
Tātad kaut kā pieci vai jaudu, ja tas ir pastāvīgs, iespējams, ir iesaistīti.
Bet tikai darot modulo pieci iespējams, nav pietiekams,
jo mums ir jāzina darīt mēs aptīšanas šeit vai šeit vai šeit.
Tātad jūs, iespējams, arī gatavojas vēlaties, lai iesaistītu
lielums lieta, vai priekšējā mainīga, kā arī.
Tātad, tas ir tikai šo salīdzinoši vienkārša aritmētika izteiksme,
bet Modulo būs galvenā sastāvdaļa.
>> Tātad īsfilma, ja Jums gribas.
Animācijas, ka daži folks at citā augstskolā
salikt kopā, ka mēs esam pielāgotas šajā diskusijā.
Tas ietver Jack apgūstot fakti par rindām un stats.
>> FILM: Reiz, tur bija puisis vārdā Džeks.
Kad tas nāca padarīt draugiem, Jack nebija iemaņa.
Tātad Jack gāja runāt ar populārākais puisis viņš zināja.
Viņš devās uz Lū un jautāja, ko man darīt?
Lou redzēja, ka viņa draugs bija tiešām noskumuši.
Nu, viņš sāka, vienkārši skatīties, kā jūs dressed.
Vai nav jums ir kādi drēbes ar atšķirīgu izskatu?
Jā, teica Jack.
Nudien darīt.
Nāciet uz manu māju un Es jums parādīs tos jums.
Tāpēc viņi aizgāja uz Jack s.
Un Jack parādīja Lou lodziņu kur viņš tur visus savus kreklus,
un viņa bikses, un viņa zeķes.
Lū teica, es redzu, jums ir visi jūsu drēbes kaudzē.
Kāpēc jūs valkāt kādu Citi reizi awhile?
>> Džeks teica, labi, kad es noņemt drēbes un zeķes,
Es nomazgājiet tos un nodot viņus prom lodziņā.
Tad nāk nākamais no rīta, un līdz es hop.
Es eju uz kastes un saņemt manas drēbes off augšpusē.
Lou ātri saprata problēma ar Jack.
Viņš tur apģērbi, CD, un grāmatas kaudze.
Kad viņš sasniedza par kaut ko lasīt vai valkāt,
viņš gribētu izvēlēties top grāmatu vai apakšveļu.
Tad, kad viņš bija darīts, viņš varētu nodot to tiesības atpakaļ.
Back to varētu iet, virsū kaudze.
Es zinu risinājumu, teica triumfējošs Loud.
Jums ir nepieciešams, lai uzzinātu, lai sākt izmantot rindā.
Lou paņēma Jack drēbes un karājās tos skapī.
Un, kad viņš bija iztukšota kastē, viņš vienkārši iemeta to.
>> Tad viņš teica, tagad Jack, beigās diena, lai jūsu drēbes pa kreisi
kad jūs viņus prom.
Tad rīt no rīta, kad jūs redzēt sauli, saņemt savas drēbes
labajā pusē, no gala līnijas.
Vai tu neredzi? teica Lū.
Tas būs tik jauki.
Jūs valkāt visu reiz Pirms jūs valkāt kaut divreiz.
Un ar visu rindās viņa skapī un plauktu,
Jack sāku justies diezgan pārliecināts par sevi.
Visi pateicoties Lou un viņa brīnišķīgi rinda.
SPEAKER 1: Nu labi, tas ir adorable.
Tātad, kas ir īsti notiek par zem motora pārsega tagad?
Ka mums ir norādes, ka mums ir malloc,
ka mums ir iespēja veidot gabalos atmiņas par sevi
dinamiski.
Tātad tas ir attēlu mēs glimpsed tikai otro dienu.
Mums nav īsti kavēties par to, bet šo attēlu
turpinās jau zem kapuci nedēļas tagad.
Un tā tas ir, tikai taisnstūris, ka mēs esam sagatavoti,
datora atmiņā.
Un varbūt jūsu dators, vai CS50 ID, ir gigabaitu atmiņas vai RAM
vai divi gigabaiti vai četri.
Tas nav īsti jautājums.
Jūsu operētājsistēma Windows vai Mac OS vai Linux,
būtībā ļauj savu programmu domāt, ka tai ir piekļuve
uz visu datora atmiņa,
pat ja jūs varētu darboties vairākas programmas vienlaicīgi.
Tātad patiesībā, tas nav īsti strādāt.
Bet tas ir sava veida ilūziju pievērsta visas programmas.
Tātad, ja jums ir divi gigs RAM, šis ir kā dators varētu domāt par to.
>> Tagad nejauši, viens no šiem lietas, viens no šiem segmentiem atmiņas,
sauc kaudze.
Un tiešām jebkurā laikā līdz šim rakstiski kodu
ka esat sauc funkcija, piemēram maģistrāli.
Atgādināt, ka jebkurā laikā es esmu Drawn datora atmiņā,
Es vienmēr izdarīt veida puse no taisnstūra šeit
un nav apnikt runāt par to, kas iepriekš.
Jo tad, kad galvenais sauc, es apgalvot ka jums šis skaida atmiņas
kas iet uz leju šeit.
Un, ja galvenais sauc funkcija piemēram, swap, swap labi iet šeit.
Un izrādās, ka ir kur tas beidzot.
Par kaut ko sauc kaudze iekšpusē datora atmiņā.
Tagad beigās, dienā, tas ir tikai adreses.
Tas ir tāpat kā baitu nulles, baitu viens, baits 2 miljardiem.
Bet, ja jūs domājat par to kā šo taisnstūra objektu,
viss, ko mēs darām katru Šoreiz mēs saucam funkcija ir
layering jaunu šķēle atmiņas.
Mēs dodam šo funkciju šķēle savas atmiņas, lai strādātu ar.
>> Un atcerēties tagad, kad tas ir svarīgi.
Jo, ja mums ir kaut kā mijmaiņas
un divas vietējās mainīgie, piemēram, A un B un mēs mainīt šīs vērtības no viena un divu
uz divām un vienu, atsaukšanas ka tad, kad swap atgriežas,
tas ir tā, it kā šī šķēle atmiņas ir tikai aizgāja.
Patiesībā, tas joprojām ir tur forensically.
Un kaut kas vēl patiesībā tur.
Bet konceptuāli, tas ir kā ja tas ir pilnīgi pagājis.
Un tā galvenais nezina kādu no darba kas tika darīts šajā mijmaiņas funkciju,
ja vien tas ir faktiski nodots tiem argumenti kursoru vai ar atsauci.
Tagad galvenais risinājums šai problēmai ar swap
ir iet lietas pēc adreses.
Bet izrādās, pārāk, kas ir turpinās jau iepriekš, ka daļa
no taisnstūra visu šo laiku ir Pagaidām tur ir vairāk atmiņas tur augšā.
Un, kad jūs dinamiski piešķirt atmiņu,
vai tas ir iekšpusē GetString, kas mēs esam bijuši dara, lai jūs par CS50
bibliotēka, vai, ja jūs guys zvaniet malloc un jautāt
operētājsistēma rieciens atmiņa, tas nenāk no skursteņa.
Tas nāk no citas vietas Jūsu datora atmiņā
ka sauc kaudze.
Un tas vēl nav atšķirīgi.
Tas ir tas pats RAM.
Tas ir tas pats atmiņas.
Tas ir tikai RAM, kas ir atkarīgs tur, nevis uz leju šeit.
>> Un tā, ko tas nozīmē?
Nu, ja jūsu dators ir ierobežots atmiņas apjoms
un kaudze aug, tāpēc runāt, un kaudze, saskaņā
šim bultiņas, pieaug uz leju.
Citiem vārdiem sakot, katrs reizi, kad jūs zvanu malloc,
jūs ir dota šķēle atmiņas no augšas,
tad varbūt nedaudz zemāks, tad nedaudz zemāks, katru reizi, kad zvana malloc,
kaudze, tā ir izmantošana, ir sava veida pieaug,
aug tuvāk un tuvāk, ko?
Kaudze.
Tātad tas šķist laba ideja?
Es domāju, ja tas nav īsti skaidrs ko vēl jūs varat darīt, ja jums ir tikai
ir ierobežots atmiņas apjomu.
Bet tas, protams, slikti.
Šie divi bultas ir par crash kurss par vienu citu.
>> Un izrādās, ka slikts puisis, ļaudīm, kas ir īpaši labi ar plānošanu,
un mēģina uzlauzt datorus, var izmantot šo realitāti.
Patiesībā, pieņemsim apsvērt mazliet fragments.
Tātad šis ir piemērs, jūs varat izlasīt par sīkāk par Wikipedia.
Mēs punkts jums pie raksts ja ziņkārīgs.
Bet tur ir uzbrukums vispār pazīstams kā bufera pārpildes, ka
ir pastāvējusi tik ilgi, cik cilvēkiem ir bijusi iespēja manipulēt
datora atmiņa, īpaši C. Tātad šī ir ļoti patvaļīgs programma,
bet pieņemsim lasīt no apakšas uz augšu.
Galvenā vērā argC char zvaigžņu argv.
Tātad tā ir programma, kas ņem komandrindas argumentus.
Un viss galvenais tas acīmredzot ir aicinājums funkcija, to sauc F vienkāršību.
Un tas iet uz ko?
Argv viens.
Tātad tas nonāk F neatkarīgi vārds ir tas, ka lietotājs drukāti
pie uzvednē pēc tam, kad Programmas nosaukums vispār.
Tik daudz, piemēram, Cēzara vai Vigenere, kas jūs varētu atgādināt darāt ar argv.
>> Tātad, kas ir F?
F notiek virknē tās vienīgais arguments,
AKA char zvaigzne, pats lieta, kā virkni.
Un to sauc patvaļīgi bārs šajā piemērā.
Un tad char c 12, tikai lajs izteiksmē,
kāda ir char c kronšteins 12 darot mums?
Ko tas dara?
Piešķirot atmiņu, īpaši 12 baiti par 12 simboli.
Tieši tā.
Un tad pēdējā rindā, samaisa un kopija, jūs, iespējams, nav redzējuši.
Tas ir virkne kopija funkcija, kuras mērķis dzīvē
ir kopēt savu otro argumentu uz savu pirmo argumentu
bet tikai līdz noteiktu skaitu baitu.
Tātad trešais arguments saka, cik baiti jums vajadzētu kopēt?
No bāra garums, kāds lietotājs drukāti.
Un saturs bārs, ka virkne ir
kopēts atmiņā norādīja at C.
>> Tātad tas šķiet veida stulba, un tas ir.
Tas ir izdomāts piemērs, bet tas ir reprezentatīvs
no klases uzbrukuma vektori, veids, kā uzbrukt programmu.
Viss ir labi un labi, ja lietotājs veidi vārdu, kas ir 11 rakstzīmes
vai mazāk, plus slīpsvītra nulle.
Ko darīt, ja lietotājs veidi vairāk nekā 11 vai 12 vai 20 vai 50 simboli?
Kas ir šī programma gatavojas darīt?
Potenciāli SEG vaina. Tas notiek akli kopēt visu bārā augšu
uz tās garumā, kas ir burtiski viss joslā,
uz adresi norādīja C. Bet C ir tikai preemptively dota kā 12 baitu.
Bet tur nav papildu pārbaude.
Nav ja apstākļi.
Nav kļūdu pārbaude šeit.
>> Un tā, ko šī programma ir gatavojas darīt, ir tikai akli
kopēt viena lieta uz otru.
Un tāpēc, ja mēs izdarīt šo kā attēlu, šeit ir
tikai skaida no atmiņas vietas.
Tā paziņojuma apakšā, mēs ir vietējo mainīgo bar.
Tā, ka rādītāja, kas notiek, lai store-- drīzāk, ka vietējās argumentu, kas ir
gatavojas glabāt virknes bar.
Un tad pamanīt tikai Iepriekš tā kaudze,
jo katru reizi, kad jūs lūgt lai atmiņas par kaudze,
tas iet mazliet virs tā gleznieciski,
paziņojums, ka mēs esam ieguvuši 12 baiti tur.
Augšējā kreisajā viens ir C kronšteins nulle un apakšējā labajā viens ir C kronšteins 11.
Tas ir tikai kā datori gatavojas nolikt to ārā.
Tik vienkārši intuitīvi, ja josla ir vairāk nekā 12 rakstzīmes kopā, t.sk.
Reversā slīpsvītra nulles, kur ir 12 vai C kronšteins 12 gatavojas doties?
Vai drīzāk, kur ir 12 raksturs vai 13 raksturs,
Attiecīgā simtdaļa raksturs iet nonākt attēlā?
Virs vai zem?
>> Pareizi, jo, pat ja kaudze pati aug uz augšu,
kad jūs esat likts sabāzt tā, tā konstrukcijas iemeslu dēļ
liek atmiņu no augšas uz leju.
Tātad, ja jūs esat ieguvuši vairāk nekā 12 baiti, jūs gatavojas sākt pārrakstīt bar.
Tagad tas ir bug, bet tas ir nav īsti liels darījumu.
Bet tas ir īpašs, jo tur ir vairāk sīkumi notiek atmiņā.
Tātad, lūk, kā mēs varētu likts hello, lai būtu skaidrs.
Ja es drukāti sveiki pie uzvednē.
H-E-L-L-O slīpsvītru nulle, beidzas laikā šie 12 baiti, un mēs esam super droši.
Viss ir labi.
Bet, ja es tipa kaut ko ilgāk, iespējams, tas ir
gatavojas rāpot uz bāra telpas.
Bet vēl sliktāk, izrādās ārā visu šo laiku,
kaut arī mēs nekad runāja par tas, kaudze izmanto citas lietas.
Tas ir ne tikai vietējie mainīgie.
>> C ir ļoti zema līmeņa valoda.
Un tā veida slepeni izmanto kaudze arī
atcerēties, kad funkcija sauc, ko
adrese ir no iepriekšējo funkciju, lai tā varētu pāriet atpakaļ uz šo funkciju.
Tātad, kad galvenie aicina swap, starp lietas uzstāja uz skursteņa
ir ne tikai mijmaiņas vietējo mainīgie, vai tās argumenti, arī slepeni uzstāja
uz skursteņa ko pārstāv ar sarkano šķēli šeit,
ir adrese galvenais fiziski jūsu datora atmiņā,
tā, ka tad, kad swap tiek darīts, dators zina, man ir nepieciešams, lai dotos atpakaļ uz galveno
un pabeigt izpildot galveno funkciju.
Tātad tas ir bīstami tagad, jo, ja lietotājs veidi arī vairāk nekā sveiki,
tāds, ka lietotāja ievade clobbers vai pārraksta ka sarkanā sadaļu,
loģiski, ja dators ir tikai gatavojas akli pieņemt,
ka baiti šajā sarkanu šķēle ir adresi, uz kuru tas būtu atgriezties,
ko tad, ja pretinieks ir pietiekami gudrs, vai paveicies likt secība baitu
tur, ka izskatās adresi, bet tas ir adrese kodu
ka viņš vai viņa vēlas datoru izpildīt, nevis galvenais?
>> Citiem vārdiem sakot, ja tas, ko lietotājs ir rakstīt par ātru,
ir ne tikai kaut ko nekaitīgs patīk hello,
bet patiesībā tas ir kods, kas ir ekvivalents izdzēst visus šī lietotāja failus?
Vai e-pastu savu paroli uz mani?
Vai sākt piesakoties viņu keystrokes, vai ne?
Ir veids, pieņemsim paredz šodien, ka viņi varētu rakstīt ne tikai sveiki
pasaules vai savu vārdu, tie varētu būtiski
apliecību kods, nulles un dzīvotspēju, ka dators
kļūdas, kuras gan kodu un adresi.
Tātad kaut nedaudz abstrakti, ja lietotājs veidu pietiekami sacīkstes kodu
ka mēs vispārināt šeit kā A. A ir uzbrukums vai pretiniekiem.
Tik vienkārši slikti sīkumi.
Mums nav rūp numurus vai nulles vai tiem
Šodien, piemēram, ka jūs galu galā pārrakstīšanas ka sarkanā sadaļu,
paziņojums, ka baitu secība.
O 835 C nulle astoņi nulle.
Un tagad, kad Vikipēdijas raksts šeit ir ierosinājusi, ja jūs tagad faktiski sākt
marķēšanas baitu datora atmiņa, ko Wikipedia raksts ir
iesniedzēja ir tas, kas notiks, ja adrese Minētā augšējā kreisajā baits ir 80 C 0 3508.
>> Citiem vārdiem sakot, ja slikts puisis ir pietiekami gudrs, ar viņa vai viņas kodu
faktiski likt numuru šeit atbilst adresi koda
viņš vai viņa injicē datorā, jūs
var triks datoru uz darot jebko.
Noņemot failus, e-pastu lietas, sniffing savu satiksmes,
burtiski kaut kas varētu būt ievada datorā.
Un tā bufera pārpildes uzbrukums tās kodols
ir tikai stulba, stulba sevišķas no masīva, kas
nebija pārbaudījusi tās robežas.
Un tas ir tas, kas ir super bīstami un vienlaicīgi super jaudīgu
C ir tas, ka mums patiešām ir piekļuve jebkur atmiņā.
Tas ir atkarīgs no mums, programmētāji, kas raksta sākotnējo kodu
lai pārbaudītu darn garumu jebkurš masīvi, ka mēs esam manipulācijas.
Tātad, lai būtu skaidrs, kāda ir noteikt?
Ja mēs roll atpakaļ uz šo kods, es ne tikai
mainīt garumu joslas, ko cits man būtu pārbaudīt?
Kas vēl man darīt, lai novērstu šo uzbrukumu pilnībā?
Es nevēlos, lai tikai akli teikt ka jums vajadzētu kopēt tik daudz baitu
kā ir garums bar.
Es gribu teikt, kopēt kā daudzi baiti kā ir bar
līdz piešķirtais atmiņa, vai 12 maksimāli.
Tāpēc man vajag kādu, ja stāvoklis kas nav pārbaudīt garumu joslas,
bet, ja tas pārsniedz 12, mēs vienkārši grūti kodu 12 kā maksimālo iespējamo attālumu.
Pretējā gadījumā tā saukto bufera pārplūdes uzbrukums var notikt.
Apakšā šiem slaidiem, Ja jūs esat ieinteresēti, lai uzzinātu vairāk
ir faktiskais sākotnējo rakstu ja jūs vēlaties, lai to apskatīt.
>> Bet tagad, starp cenām maksā šeit bija neefektivitāte.
Tā, ka bija ātrs zems līmenis apskatīt to, ko
problēmas var rasties tagad, ka mēs piekļūt datora atmiņā.
Bet vēl viena problēma, kas mums jau paklupa pirmdien
bija tikai neefektivitāti no saistītajā sarakstā.
Mēs esam atpakaļ uz lineāro laiku.
Mums vairs nav blakusesošo masīvs.
Mums nav brīvpieejas.
Mēs nevaram izmantot kvadrātiekava notācija.
Mums burtiski ir jāizmanto kamēr cilpa kādu es uzrakstīju pirms brīža.
Bet pirmdien, mēs apgalvoja, ka mēs varam rāpot atpakaļ valstība efektivitātes
panākt kaut ko, kas ir logaritmiska varbūt, vai labākais vēl,
varbūt pat kaut kas ir tā saukto konstante laiks.
Tātad, kā mēs varam darīt, ka, izmantojot šīs jaunās instrumenti, šīs adreses, šie Pointers,
un vītņu lietas mūsu pašu?
Nu, pieņemsim, ka šeit, tie ir ķekars
skaitļu, ka mēs vēlamies, lai Uzglabāt datu struktūru un meklēt efektīvi.
Mēs varam pilnīgi attīt uz nedēļu divi, mest tos vērā masīva,
un meklēt tos, izmantojot bināro meklēšanu.
Divide un iekarot.
Un patiesībā jūs rakstījāt binārā sektorā PSET3,
kur jūs īstenoja atrašanas programmu.
Bet jūs zināt, kas.
Tur ir sava veida vairāk gudrs veids, kā to izdarīt.
Tas ir nedaudz vairāk sarežģīta un tas, iespējams,
ļauj mums redzēt, kāpēc bināro meklēšana ir tik daudz ātrāk.
Pirmkārt, pieņemsim iepazīstināt jēdziens koku.
Kurš kaut arī realitāte koki veida
augt, piemēram, tas, pasaulē datora zinātne viņi veida aug uz leju
piemēram, ģimenes koku, kur jums ir jūsu vecvecāki vai vecvecvecākus
vai plauktiņš augšpusē, patriarha un matriarch ģimenes, tikai viens
tā sauktais saknes, mezglu, zemāk kas ir tās bērni,
zem kuras ir tās bērni, vai tās pēcteči kopumā.
Un ikviens piekārtiem off apakšā ģimenes
koks, turklāt esot jaunākais ģimenē,
arī var vienkārši būt vispārēji sauc koka lapas.
>> Tātad tas ir tikai ķekars vārdiem un definīcijas
kaut ko sauc par koku datorā zinātne, līdzīgi ciltskoku.
Bet tur ir mīļotājs iemiesojumiem koku, no kuriem viens
To sauc par bināro meklēšanu koks.
Un jūs varat veida kaitināt izņemot to, ko šī lieta nav.
Nu, tas ir bināro kādā ziņā?
Kur binārais nāk no šejienes?
Sorry?
Tas nav tik daudz, vai nu vai.
Tas ir vairāk, ka katrs no mezgliem ir ne vairāk nekā divi bērni, kā mēs redzam šeit.
Vispār, tree-- un jūsu vecāki un vecvecāki
var būt tik daudz bērnus vai grandkids jo viņi patiešām vēlas,
un tāpēc, piemēram, tur mums ir trīs Bērni off, ka labajā mezglā,
bet bināro koku, mezgls ir nulle, viens vai divi bērni maksimāli.
Un tas ir jauki īpašums, jo, ja tas ir ierobežots ar divi
mēs ejam, lai varētu saņemt nedaudz log bāzi divi
darbība notiek šeit galu galā.
Tātad mums ir kaut logaritmisko.
Bet vairāk par to pēc brīža.
Meklēt koks nozīmē, ka skaitļi ir ierīkotas tā, lai pa kreisi bērna
vērtība ir lielāka nekā saknes.
Un tās tiesības bērns lielāks nekā saknes.
Citiem vārdiem sakot, ja jūs lietojat kādu no mezglus, apļi šajā attēlā,
un skatās tās pa kreisi Bērns un tā tiesības bērns,
pirmais jābūt mazākam nekā, otrais jābūt lielākam par.
Tātad vesels saprāts pārbaudīt 55.
Tas ir atstājis bērnam ir 33.
Tas ir mazāk nekā.
55, tā tiesības bērns ir 77.
Tas ir lielāks nekā.
Un tas ir rekursīvs definīcija.
Mēs varētu pārbaudīt katru no tiem mezgli un tas pats modelis varētu turēt.
>> Tātad, kas ir jauki binārā meklēšana koks, ir
ka viens, mēs varam īstenot ar struktūrai, tāpat kā šo.
Un, pat ja mēs esam throwing daudz konstrukciju JŪSU,
viņi nedaudz intuitīvi tagad cerams.
Sintakse ir joprojām Arcane pārliecināts, bet saturs mezglu šajā
context-- un mēs turpinām izmantojot vārdu mezglu,
vai tas ir taisnstūris uz ekrāna vai apli,
tas ir tikai daži vispārējs konteiners, šajā gadījumā no koka, piemēram, vienu
mēs redzējām, mums ir nepieciešams vesels skaitlis katrā no mezgliem
un tad man vajag divas norādes kas norāda uz kreiso bērnu un labo bērnu,
attiecīgi.
Tātad, tas ir, kā mēs varētu īsteno ka struct.
Un kā es varētu īstenot to kodu?
Nu, pieņemsim ātri apskatīt šo tiny piemēru.
Tas nav funkcionāls, bet es esmu nokopēt un ielīmēt šo struktūru.
Un, ja mana funkcija bināro meklēšana koku sauc meklēšanu,
un tas aizņem divus argumentus, vesels skaitlis N un rādītājs
uz mezglu, tāpēc rādītāju uz koku vai rādītāju uz saknes koku,
Kā es varu iet par meklē N?
Nu, pirmkārt, tāpēc, ka es esmu nodarbojas ar norādes,
Es esmu gatavojas darīt veselība pārbaudītu.
Ja koku vienlīdzīgi vienāds null, ir N šajā kokā vai ne šajā kokā?
Tā nevar būt, vai ne?
Ja es esmu garām null, tur nekā nav.
Es varētu arī vienkārši akli teikt atgriezties viltus.
Ja jūs varētu man nekas, es, protams, nevaru atrast nevienu numuru N. Tātad, ko vēl varētu man
pārbaudiet tagad?
Es esmu gatavojas teikt arī cits, ja N ir mazāk nekā kāds ir koku mezglā
ka es esmu nodota N vērtību.
Citiem vārdiem sakot, ja numurs es esmu meklē, N, ir mazāks nekā mezglā
ka es esmu meklē.
Un mezglu Es meklēju at sauc koku,
un atsauktu no iepriekšējā piemērā nokļūt pie vērtības rādītājs,
Es izmantoju bultiņas notācija.
Tātad, ja N ir mazāks par koku bultas N, es gribu, lai konceptuāli iet pa kreisi.
Kā es varu izteikt meklēšanas, pa kreisi?
Lai būtu skaidrs, ja tas ir aina jautājumu
un es esmu izturējis ka augšējais bultiņa, kas ir vērsta uz leju.
Tas ir mans koks rādītājs.
Es esmu norādot uz koka saknēm.
Un es esmu meklē teiksim, par skaits 44, patvaļīgi.
Ir 44 mazāk nekā vai lielāks par 55 acīmredzami?
Tātad, tas ir mazāk nekā.
Un tā tas, ja nosacījums ir piemērojams.
Tātad konceptuāli, ko vēlos meklēt tālāk, ja es esmu meklē 44?
Yeah?
>> Tieši tā, es gribu meklēt kreiso bērnu,
vai pa kreisi sub-tree par šo attēlu.
Un patiesībā, ļaujiet man cauri attēlu uz leju šeit
tikai brīdi, jo Es nevaru saskrāpēt šo out.
Ja es sāktu šeit ir 55, un Es zinu, ka vērtība 44
Es meklēju, ir kreiso, tas ir sava veida
līdzīgu plīsumi telefona grāmatu puse vai asarošana koku pusi.
Man vairs nav jārūpējas par Visa šī puse no koka.
Un tomēr, savādi ziņā no struktūru, šī lieta vairāk nekā šeit, ka
sākas ar 33, kas pats par sevi ir bināro meklēšanas koku.
Es teicu vārdu rekursīvas agrāk, jo patiešām tas ir datu struktūra, kas
pēc definīcijas ir rekursīvs.
Jums varētu būt koku, kas ir šī liels, bet katrs no saviem bērniem
apzīmē koku tikai nedaudz mazāka.
Tā vietā, lai ar to Grandpa vai vecmāmiņa, tagad tā ir tikai mamma
or-- es nevaru say-- nav mamma vai tētis, tas būtu dīvaini.
Tā vietā divi bērni tur būtu tāpat kā brālis un brālis.
Jaunās paaudzes ģimenes koku.
Bet strukturāli, tā ir tā pati ideja.
Un izrādās, man ir funkcija ar kuru es varu meklēt bināro meklēšanu
koks.
To sauc meklēšanu.
Es meklētu N koku bultiņas pa kreisi cits ja n ir lielāks par vērtību
ka es esmu pašlaik.
55. stāsts pirms brīža.
Man ir funkciju sauc search ka es varu tikai
iet N šo un rekursīvi meklēt sub-tree un vienkārši atgriešanās
neatkarīgi ka atbilde.
Else Man daži galīgo bāzes lietu šeit.
>> Kas ir pēdējais gadījums?
Tree ir vai nu nulle.
Vērtība es esmu vai nu meklē ir mazāks nekā tā, vai lielāks nekā tas
vai vienāds ar to.
Un es varētu teikt vienāds vienāds, bet loģiski tas ir
līdzvērtīgs tikai saku cits šeit.
Tātad taisnība ir, kā es varu atrast kaut ko.
Tātad cerams tas ir vēl vairāk pārliecinošu piemēru
nekā stulba sigma funkcijas mēs darījām dažas lekcijas atpakaļ,
kur tas bija tikpat viegli izmantot cilpu saskaitīt visus numurus no viena
ar N. šeit ar datu struktūru kas pats par sevi ir rekursīvi
definēts un rekursīvi sastādīts, tagad mēs ir iespēja izteikt sevi
ar kodu, kas pati par sevi ir rekursīvs.
Tātad šī ir tieši tā pati kodu šeit.
>> Tātad, ko citi problēmas mēs varam atrisināt?
Tik ātri solis prom no kokus tikai brīdi.
Te ir, teiksim, Vācijas karogu.
Un tur ir skaidri modelis, lai šo karogu.
Un tur ir daudz karogi pasaulē, kas
ir tik vienkārši, kā tas izteiksmē par to krāsas un raksti.
Bet pieņemsim, ka tas tiek saglabāts kā .GIF, Vai JPEG, vai bitmap, vai ping,
jebkurš grafisko failu formātu ar kuru jūs esat pazīstami,
daži no kuriem mēs esam spēlē ar in PSET4.
Tas nešķiet vērts saglabāt melns pixel, melns pixel, melns pixel,
dot, dot, dot, visu ķekars melni pikseļi pirmajam scanline,
vai rinda, tad viss ķekars tas pats, tad viss ķekars
no to pašu, un pēc tam viss ķekars sarkano pikseļi,
sarkans pikseļi, sarkanā pikseļi, tad viss ķekars dzeltenās pikseļi, dzeltens, vai ne?
>> Tur ir tik neefektivitāte šeit.
Kā jūs intuitīvi saspiest Vācijas karogu
ja to īsteno kā failu?
Tāpat kāda informācija mēs varam ne apnikt glabāšanai diskā, lai
lai samazinātu mūsu faila izmēru no, piemēram, megabaitu uz kilobaiti, kaut
mazākas?
Kur slēpjas atlaišanas šeit, lai būtu skaidrs?
Ko jūs varētu darīt?
Yeah?
Tieši tā.
Kāpēc ne, nevis atcerēties krāsa katru darn pikseli
tāpat kā jūs darāt ar PSET4 ar bitmap failu formātā,
kāpēc nav jūs vienkārši pārstāvēt kreisās malas kolonnā pikseļi, piemēram,
ķekars melni pikseļi, ķekars no sarkanā, un ķekars dzeltena,
un tad tikai kaut kā šifrēt ideja par Atkārtojiet to 100 reizes
vai atkārtot šo 1000 reizes?
Ja 100 vai 1000 ir tikai vesels skaitlis, lai jūs
var saņemt prom ar tikai ar vienu numuru nevis simtiem vai tūkstošiem
papildu pikseļi.
Un tiešām, tas, kā mēs varētu saspiest Vācijas karogu.
Un
Tagad to par Francijas karogu?
Un mazliet daži no veida garīgās vingrinājums, kurā karogs
var tikt saspiests vairāk uz diska?
Vācijas karogu vai franču karogs, ja mēs šo pieeju?
Vācijas karogs, jo tur ir vairāk horizontālā atlaišanu.
Un ar dizainu, daudzi grafisko failu formāti patiešām strādā kā skenēšanas līnijas
horizontāli.
Viņi varētu strādāt vertikāli, tikai cilvēce
Pirms nolēma gadiem, ka mēs parasti domā par lietām, rindas
pēc kārtas, nevis kolonnā pa kolonnas.
Tātad, patiesi, ja tu būtu apskatīt faila
lielums Vācijas karogu un franču karogs, tik ilgi, kamēr izšķirtspēja ir
tas pats, tas pats platums un augstums, tas viens
šeit būs lielāks, jo jums atkārtot sev trīs reizes.
Jums ir jānorāda zils, atkārtojiet yourself, balts, atkārtot sevi, sarkans,
atkārtot sevi.
Jūs varat ne tikai iet all veids, kā labi.
Un kā malā, lai padarītu skaidrs saspiešanas
ir visur, ja tie ir četri kadri no a video-- jūs
varētu atgādināt, ka filmu vai video parasti
piemēram, 29 vai 30 kadriem sekundē.
Tas ir kā mazs uzsist grāmatu, kur jums tikai redzēt attēlu, attēlu, attēlu, attēlu,
attēls vienkārši super ātri, lai tā izskatās aktieri uz ekrāna ir kustībā.
Lūk kameņu par top ķekars ziedu.
Un, lai gan tas varētu būt sava veida grūti redzēt pēc pirmā acu uzmetiena,
vienīgā lieta virzās šī filma ir bišu.
>> Kas ir mēms par uzglabāšanu video nesaspiesti?
Tas ir sava veida atkritumus, lai uzglabātu video kā četras gandrīz identisku attēlus, kas
atšķiras tikai tiktāl, ciktāl, ja bite ir.
Jūs varat mest prom visvairāk Šīs informācijas
un atcerēties tikai, piemēram, pirmais kadrs un pēdējais kadrs,
galvenie kadri ja esat kādreiz dzirdējis vārdu,
un tikai Uzglabāt vidus, kad bite ir.
Un jums nav uzglabāt visu rozā,
un zilā, un zaļās vērtības, kā arī.
Tātad tas ir tikai teikt, ka kompresija ir visur.
Tas ir paņēmiens, mēs bieži izmantojam vai par pašsaprotamu šajās dienās.
>> Bet kā jūs saspiest tekstu?
Kā jūs iet par saspiežot tekstu?
Nu, katrs no rakstzīmju Ascii ir viens baits, vai astoņi biti.
Un tas ir sava veida mēms, vai ne?
Tāpēc, ka jūs, iespējams, A tipa un E un I un O un U daudz
biežāk nekā, piemēram, W vai Q vai Z, atkarībā no valodas, kurā
jūs esat rakstiski noteikti.
Un tad kāpēc mēs izmantojam astoņi biti par katru vēstuli,
ieskaitot vismaz tautas vēstules, vai ne?
Kāpēc ne izmantot mazāk bitus super tautas burti,
piemēram, E, lietas jūs uzminēt pirmais Wheel of Fortune,
un izmantot vairāk bitus mazāk populāri burtiem?
Kāpēc?
Tāpēc, ka mēs esam tikai gatavojas tos izmanto retāk.
>> Nu, izrādās, ka tur ir bijuši mēģinājumi veikti, lai to paveiktu.
Un, ja jūs atceraties no pakāpes skola vai vidusskola, Morse kodu.
Morzes kods ir punkti un domuzīmes, kas var būt
pārraida pa vadiem, kā skaņas vai signāli veida.
Bet Morse kods ir super tīrs.
Tas ir sava veida bināro sistēmas ka jums ir punktiņi vai domuzīmes.
Bet, ja jūs redzat, piemēram, divus punktus.
Vai, ja jūs domājat, ka atpakaļ uz operatora kas iet kā pīkstiens, pīkstiens, pīkstiens,
pīkstiens, trāpot nedaudz sprūda kas pārraida signālu,
ja jums, saņēmējs, saņem divas punkti, ko ziņa esat saņēmis?
Pilnīgi patvaļīgi.
>> Es?
Es?
Vai kas about-- vai es?
Varbūt tas bija tikai divi E tiesības?
Tātad tur ir šī problēma no decodability ar Morse
kods, saskaņā ar kuru, ja vien Persona sūtīt jums ziņu
faktiski ietur pauzi, lai jūs varētu kārtot redzēt vai dzirdēt atšķirības starp burtiem,
tas nav pietiekams tikai, lai nosūtīt straumi no nullēm un tiem,
vai punktiņi un svītriņas, jo tur ir neskaidrība.
E ir viens dot, tādēļ, ja jums redzēt divus punktus vai dzirdēt divus punktus,
varbūt tas ir divas E ir vai varbūt tas ir viens I.
Tāpēc mums ir vajadzīga sistēma, kas ir nedaudz vairāk gudrs nekā.
Tātad cilvēks nosaukts Huffman gadi pirms nāca klajā ar tieši to.
Tātad mēs esam tikai gatavojas veikt ātrs skatiens
cik koki ir piederīgs šim.
Pieņemsim, ka tas ir daži stulba ziņa jūs vēlaties nosūtīt,
šādā sastāvā tikai A, B, C ir D's un E s, bet tur ir daudz no atlaišanas šeit.
Tas nav domāts, lai būtu angļu valoda.
Tas nav šifrēts.
Tas ir tikai stulba ziņa ar daudz atkārtošanās.
Tātad, ja jūs faktiski rēķināties visus A s, B s, C s, D's, un E ir, lūk,
biežums.
20% no burtiem ir A s, 45% no burtiem
ir E s, un trīs citas frekvences.
Mēs saskaitījām tur manuāli un tikko izdarīja math.
>> Tātad izrādās, ka Huffman, kādu laiku atpakaļ,
sapratu, ka jūs zināt ko, ja es sāktu ēkas
koks, vai meža koku, ja jūs, šādi, es varu darīt šādi.
Es esmu gatavojas sniegt mezglu uz katru no vēstulēm, kas man rūp
un es esmu gatavojas glabāt iekšpusē šī mezgla
frekvences kā peldošā punkta vērtība, vai jūs varētu izmantot to par N, pārāk,
bet mēs tikai izmantot peldēt šeit.
Un algoritms, kas Viņš ierosināja, ka jūs
šo mežu vienā mezglā koki, tāpēc super īsi koki,
un tu sāktu, kas savieno tos ar jaunas grupas, jauni vecāki, ja Jums gribas.
Un jūs to izdarītu, izvēloties divi mazākie frekvences vienlaicīgi.
Tāpēc es ņēma 10% un 10%.
Izveidot jaunu mezglu.
Un es aicinu jaunajam mezglā 20%.
>> Kuriem divi punkti es apvienot nākamais?
Tas ir nedaudz neskaidrs.
Tātad tur ir daži stūru gadījumiem apsvērt, bet, lai saglabātu lietas diezgan,
Es esmu gatavojas izvēlēties 20% - Es tagad ignorēt bērnus.
Es esmu gatavojas izvēlēties 20% un 15% un izdarīt divus jaunus malas.
Un tagad kuriem divi punkti man loģiski apvienot?
Ignorēt visus bērnus, visi mazbērni, paskatieties saknēm
tagad.
Kuriem divi punkti man tie kopā?
Divi Point un 0,35.
Tāpēc ļaujiet man izdarīt divas jaunas šķautnes.
Un tad es esmu tikai ieguva vienu pa kreisi.
Tātad, šeit ir koks.
Un tas ir bijis sagatavots apzināti izskatīties veida diezgan,
bet paziņo, ka malas ir arī tika marķēti nulli un vienu.
Tātad, visi no kreisās puses, malām ir nulle patvaļīgi, bet konsekventi.
Visas labās malas ir tie.
>> Un tā, kādi Hoffman piedāvātā, ja jūs vēlaties pārstāvēt B,
nevis pārstāv numuru 66, kā ASCII kas ir astoņas visu biti,
Jūs zināt, ko, tikai veikalu modelis nulle, nulle, nulle,
nulle, jo tas ir ceļš no mana koka, Mr Huffman koks,
uz lapas no saknes.
Ja vēlaties saglabāt E, gluži pretēji, nav
nosūtīt astoņi biti, kas pārstāv kādu E. Tā vietā, nosūtīt kāda modelis bitiem?
One.
Un, kas ir jauka par šo ir ka E ir populārākais vēstule,
un jūs izmantojat īsākais koda.
Nākamais populārākais vēstule izskatās kā tas
bija A. Un tik cik bitus viņš ierosina izmantot par to?
Nulle, viens.
>> Un tāpēc, ka tas ir īstenots kā šo koku, tagad
ļaujiet man noteikt, tur ir nē neskaidrību kā Morse
kods, jo visi burti jums rūp
ir pēc tam, kad minētie malām.
Tātad tas ir tikai viens piemērošana no koka.
Tas is-- un es ņemšu vilnis mana roka pie šī, kā jūs
varētu to īstenotu kā C struktūru.
Mums ir nepieciešams, lai apvienotu simbols, kā char,
un biežums, kas pa kreisi un pa labi.
Bet aplūkosim divus nobeiguma piemēri, kas jums
iegūt diezgan pazīstams ar pēc viktorīna nulle problēmu noteikti pieci.
>> Tātad tur ir datu struktūra pazīstams kā hash tabulu.
Un hash tabulu, ir sava veida atdzesē, ka tā ir kausi.
Un pieņemsim, ka tur ir četri kausi šeit, tikai četras tukšas vietas.
Lūk kārtis, un šeit ir klubs, lāpsta, klubs, dimanti, klubs,
dimanti, klubs, dimanti, clubs-- tāpēc tas ir nejauši.
Sirdis, hearts-- tāpēc es esmu bucketizing visas izejvielas šeit.
Un hash tabulu vajadzības paskatīties uz savu ieguldījumu,
un pēc tam nodot to zināmu vietu, pamatojoties uz to, ko jūs redzēt.
Tas ir algoritms.
Un man bija, izmantojot super vienkāršs vizuālais algoritms.
Par cieta daļa no kuriem bija atceroties kādi bildes bija.
Un tad tur ir četras kopējās lietas.
>> Tagad skursteņi tika pieaug, kas ir apzināta dizaina lieta šeit.
Bet ko vēl varētu man darīt?
Tātad patiesībā šeit mums ir ķekars vecās skolas eksāmenu grāmatas.
Pieņemsim, ka ķekars studentiem vārdi ir šeit.
Lūk lielāks hash tabulu.
Tā vietā, četri kausi, Man ir, teiksim 26.
Un mēs negribējām iet aizņemties 26 lietas no ārpuses [? Annenberg?], Tāpēc
šeit ir pieci, kas pārstāv A līdz Z. Un, ja es
redzēt students, kura vārds sākas ar A, Es esmu gatavojas īstenot savu viktorīna tur.
Ja kāds sāk ar C, tur, A-- faktiski, nevēlējās to darīt.
B iet vairāk nekā šeit.
Tāpēc es esam ieguvuši A un B un C. And Tagad šeit ir vēl viens students.
Bet, ja tas hash tabulā ir īsteno ar masīvu,
Es esmu veida ieskrūvē šajā brīdī, vai ne?
Es veida nepieciešams, lai šo kaut kur.
>> Tātad viens veids, kā es varētu atrisināt, tas ir, viss labi, ir aizņemts, B ir aizņemts, C ir aizņemts.
Es esmu gatavojas nodot viņam D. Tātad pirmkārt, man ir izlases tūlītēja piekļuve
uz katru kausu studentiem.
Bet tagad tas ir sava veida nodota uz kaut ko lineāra,
jo, ja es gribu, lai meklētu kādu kura vārds sākas ar A, es varētu pārbaudīt šeit.
Bet, ja tas nav A students Es meklēju,
Es veida ir jāsāk pārbaudīt spaiņiem, jo ​​tas, ko es darīju
bija sava veida lineāri zonde datu struktūru.
Muļķīgs veids, kā pateikt tikai izskatās par pirmo pieejamo atvēršanas,
un nodot kā plāna B, tā sakot, vai plāns D šajā gadījumā vērtība
šajā vietā vietā.
Tas ir tikai tāpēc, ka, ja jūs esat ieguva 26 vietas un neviens students
ar nosaukumu Q vai Z, vai kaut kas tamlīdzīgs ka, vismaz jūs izmantojat telpu.
>> Bet mēs jau esam redzējuši vairāk gudrs risinājumu šeit, vai ne?
Ko jūs darītu, nevis ja jums ir sadursmi?
Ja divi cilvēki ir nosaukums A, ko būtu
bijuši gudrāki vai vairāk intuitīvi risinājums nekā tikai
Liekot kur D ir vajadzēja būt?
Kāpēc es tikai iet ārpus [? Annenberg?],
piemēram malloc, citu mezglu, ielieciet to šeit, un pēc tam nodot, ka students šeit.
Tāpēc, ka man būtībā ir sava veida masīva,
vai varbūt vairāk eleganti, jo mēs esam sāk redzēt saistīts sarakstu.
>> Un tāpēc hash tabulu ir struktūra kas varētu izskatīties tāpat kā tas,
bet vairāk gudri, tu kaut ko sauc atsevišķa ķēžu rādītāju, ar kuru hash tabulu
vienkārši ir masīvs, katrs no kurā sastāvdaļas nav skaitlis,
pati ir saistīts saraksts.
Tā, ka jūs saņemsiet super ātri piekļūt izlemjot, kur hash savu vērtību.
Daudz, piemēram, ar kartēm piemēram, Es super ātri pieņemt lēmumus.
Hearts iet šeit, dimanti iet šeit.
Same Lūk, iet šeit, D iet šeit, B iet šeit.
Tik super ātri meklēt-ups, un ja tev gadās uzskriet lietu
kur jūs esat ieguvuši sadursmes, divi cilvēki ar tādu pašu nosaukumu, arī tad
jūs vienkārši sākt saistot tos kopā.
Un varbūt jūs saglabātu tos sakārtoti alfabētiskā secībā, varbūt jums nav.
Bet vismaz tagad mums ir dinamismu.
Tā, no vienas puses, mums ir super ātri pastāvīgs laiks, un veida lineārā laika
iesaistīti ja šiem saistītas sarakstiem sāk saņemt mazliet garš.
>> Tātad šāda veida dumjš, geeky joks gadus atpakaļ.
Pie CS50 kapāt-a-Thon, kad studenti pārbaudi,
daži TF vai CA katru gadu domā, ka tas ir smieklīgi, lai safasēti
pazīme, piemēram, tas, kur tā vienkārši nozīmē, ja jūsu vārds sākas ar A,
iet šo ceļu.
Ja jūsu vārds sākas ar B, iet this-- OK,
tas ir smieklīgi, varbūt vēlāk semestrī.
Bet tur ir cita veids, kā to izdarīt, too.
Nāciet atpakaļ uz to.
>> Tātad tur ir šī struktūra.
Un tas ir mūsu pēdējais struktūra šodien,
kas ir kaut kas sauc trie.
T-R-I-E, kas kaut kādu iemeslu dēļ ir īss izguves, bet to sauc trie.
Tātad trie ir vēl viens interesants amalgama daudz šīm idejām.
Tas ir koks, ko mēs esam redzējuši iepriekš.
Tas nav bināro meklēšanas koku.
Tas ir koks ar jebkuru bērnu skaitu, bet katrs no bērniem sistēmu TRIE
ir masīvs.
Masīvs izmēra, teiksim, 26 vai varbūt 27 ja jūs vēlaties, lai atbalstītu hyphenated nosaukumus
vai apostrofs cilvēku vārdiem.
>> Un tā tas ir datu struktūra.
Un, ja paskatās no augšas uz leju, piemēram, ja jūs
apskatīt augšējā mezglā tur, M, ir norādot uz galējo kreiso lieta tur,
kuru pēc tam, X, W, E, L, L. Tas ir tikai datu struktūra, kas patvaļīgi
ir uzglabātu cilvēku vārdus.
Un Maxwell glabā tikai pēc ceļš no masīva ar masīvu masīvs.
Bet kas ir pārsteidzošs apmēram trie ir ka, tā kā saistīta sarakstu un pat
masīvs, labākais, ko mēs jebkad esam gotten ir lineārais laiks vai logaritmisko laiks meklē
kāds up.
Šajā datu struktūrā TRIE, ja mans datu struktūra ir viens vārds tajā
un es esmu meklē Maxwell, es esmu gatavojas atrast viņam diezgan ātri.
Es tikai meklē M-A-X-W-E-L-L. Ja šo datu struktūra, gluži pretēji,
ja N ir miljons, ja tur ir miljons vārdi šajā datu struktūru,
Maxwell joprojām būs redzamu pēc tikko M-A-X-W-E-L-L
soļi.
Un David-- D-A-V-I-D soļus.
Citiem vārdiem sakot, veidojot datu struktūra, kas ir
got visi no šiem blokiem, kas visi paši atbalstīt brīvpieejas,
Es varu sākt meklēt up Tautas nosaukt izmantojot laiku, kas ir
proporcionāls nevis numuru no lietas datu struktūru,
kā miljons esošie nosaukumi.
Par laiku, kas nepieciešams, lai es atrastu summa M-A-X-W-E-L-L šajā datu struktūra ir
proporcionāls nevis uz izmērs no datu struktūru,
bet ar garumu nosaukuma.
Un reāli nosaukumi mēs meklējam up
nekad būs traks garš.
Varbūt kādam ir 10 raksturs nosaukt, 20 rakstzīmju nosaukumu.
Tas, protams, ierobežots, vai ne?
Ir cilvēks uz Zemes, kas ir pēc iespējas garāku vārdu,
bet šis nosaukums ir nemainīga vērtība garums, vai ne?
Tas nemainās nekādā ziņā.
Tātad šādā veidā, mēs esam sasniegusi datu struktūra
tas ir nemainīgs laika meklēt-up.
Tas veikt vairākus soļus atkarībā no tā garuma ievadi,
bet ne skaits nosaukuma datu struktūrā,.
Tātad, ja mēs dubultu skaitu nosaukumiem nākamgad no miljards līdz diviem miljardiem,
secinājums Maxwell gatavojas veikt tieši tādu pašu numuru septiņi soļi
lai atrastu viņu.
Un tā mēs, šķiet, esam sasnieguši Mūsu svēts grail darba laika.
>> Tātad pāris ātri paziņojumiem.
Viktorīna nulle nāk uz augšu.
Vairāk par ka par kursu mājas lapā nākamo pāris dienu laikā.
Pirmdiena lecture-- tas ir brīvdiena šeit Hārvardā pirmdien.
Tas nav New Haven, tāpēc mēs esam ņemot klasi
New Haven par lekciju pirmdien.
Viss tiks filmēts un noskatīties tiešraidē, kā ierasts,
bet pieņemsim beidzas šodien ar 30 sekunžu klipu
saucamie "Deep Domas" ar Daven Farnham, kas
iedvesmoja pagājušajā gadā līdz sestdienai Night Live s "Deep Domas"
Jack, ērts, kas tagad būtu jēga.
>> FILM: Un tagad, "Deep Domas "ar Daven Farnham.
Hash tabulu.
>> SPEAKER 1: Labi, tas arī tagad.
Redzēsim tevi nākamnedēļ.
>> Doug: Lai redzētu to darbībā.
Tātad, pieņemsim to apskatīt, kas tieši tagad.
Tātad šeit, mums ir nešķirotas masīvs.
>> IAN: Doug, jūs varat iet uz priekšu un restart tas tikai vienu sekundi, lūdzu.
Labi, kameras ir ritošā, tāpēc darbība, kad jūs esat gatavs, Doug, OK?
Doug: Labi, lai to, ko mēs ir šeit ir nešķirotas masīvs.
Un es esmu krāsainu visi elementi sarkans, lai norādītu, ka tas ir, faktiski,
nešķiroti.
Tik atceros, ka pirmā lieta, ko mēs darām ir mēs sakārtot kreiso pusi no masīva.
Tad mēs kārtot tiesības puse no masīva.
Un ya-da, ya-da, ya-da, mēs apvienot tos kopā.
Un mums ir pilnīgi sakārtoti masīvs.
Tātad tas, kā apvienot veida darbi.
>> IAN: Paga, paga, paga, sagriezti, sagriezti, sagriezti, sagriezti.
Doug, jūs varat ne tikai ya-da, ya-da, Ya-da, savu ceļu caur sapludināšanas kārtošanas.
>> Doug: Es tikko izdarīja.
Ir labi.
Mēs esam labi iet.
Pieņemsim tikai glabāt velmēšanas.
So anyway,
>> IAN: Jums ir, lai izskaidrotu tā pilnīgāk nekā.
Tas ir vienkārši nav pietiekami.
Doug: Ian, mums nav ir nepieciešams, lai dotos atpakaļ uz vienu.
Ir labi.
So anyway, ja mēs turpināsim ar merge-- Ian, mēs esam vidū filmēšanas.
>> IAN: Es zinu.
Un mēs varam ne tikai ya-da, ya-da, Ya-da, cauri visam procesam.
Jums ir paskaidrot, kā Abas puses saņemt apvienojās kopā.
>> Doug: Bet mēs jau esam paskaidroja, kā divi sides--
>> IAN: Jūs esat tikko parādīts viņus apvienot masīvs.
Doug: Viņi zina procesu.
Viņi labi.
Mēs esam aizgājuši pār to desmit reizes.
>> IAN: Jūs vienkārši izlaidis tiesības pār to.
Mēs ejam atpakaļ uz vienu, jums nevar tu ya-da, ya-da pār to.
Labi, atpakaļ uz vienu.
>> Doug: man ir jāiet atpakaļ cauri visiem slaidiem?
Mans Dievs.
Tas ir tāpat kā sesto reizi, Ian.
Ir labi.
>> IAN: Nu labi.
Esat gatavi?
Liels.
Darbība.