[Muusika mÃĊngimine]
DAVID J. Humala: Olgu.
See on CS50.
See on nÃĊdala viie jÃĊtkus ning me on hÃĊid uudiseid ja halbu uudiseid.
Nii hea uudis on see, et CS50 kÃĊivitab sel reedel.
Kui soovid meiega liituda, pea tavaline URL siia.
Veelgi parem uudis, ei loeng tuleval esmaspÃĊeval 13..
Veidi vÃĊhem parem uudis, viktoriin null on jÃĊrgmisel kolmapÃĊeval.
Rohkem infot saab leida see URL siia.
Ja jÃĊrgmise paari pÃĊeva jooksul saadame tÃĊites toorikud
seoses tuba et me oleme kaitstud.
Parem uudis on see, et saad on muidugi hÃṁlmavast
istungil tuleval EsmaspÃĊev Ãṁhtul.
JÃĊlgige kursuse veebisait asukoha ja detailid.
Sektsioonid, kuigi see on puhkus, kohtub ka samuti.
Parim uudis, loeng jÃĊrgmisel reedel.
Nii et see on traditsioon, et me on, kui Ãỳhe Ãṁppekava.
Lihtsalt-- see saab olema hÃĊmmastav.
Sa nÃĊed asju konstantse ajaga andmestruktuurid
ja hash tabeleid ja puud ja proovib.
Ja me rÃĊÃĊgime sÃỳnnipÃĊev probleeme.
Terve hunnik kraami ootab jÃĊrgmisel reedel.
OK.
Igatahes.
>> Nii et meelde tuletada, et me oleme olnud keskendub see pilt, mis on
sees meie arvuti mÃĊllu.
Nii et mÃĊlu vÃṁi muutmÃĊlu on koht, kus programmid olemas, kui sa kasutad neid.
Kui te topeltklÃṁps ikooni, et kÃĊivitada mÃṁned programmi
vÃṁi topeltklÃṁpsake ikooni, et avada mÃṁnda faili,
see on koormatud kÃṁvakettalt autot vÃṁi tahkes olekus autot
RAM, muutmÃĊlu, kus ta elab kuni toide vÃĊlja lÃỳlitub,
sÃỳlearvuti kaas sulgub, vÃṁi sa vÃĊljud rakendusest.
>> NÃỳÃỳd, kui mÃĊlu on mis siis ilmselt on
1 GB nendel pÃĊevadel, 2 gigabaiti vÃṁi isegi palju rohkem,
Ãldiselt on sÃĊtestatud antud programmi
Selles omamoodi ristkÃỳlikukujuline kontseptuaalse mudeli
kusjuures meil stack allosas ja hunnik muid asju Ãỳlaosas.
Asi tipus Me oleme nÃĊinud seda pilti
Enne aga ei rÃĊÃĊkinud on nn tekstiosa.
Tekst segment on lihtsalt fancy viis Ã¶elda nullid ja need, mis
kirjutada oma tegelik koostatud programmi.
>> Nii et kui te topeltklÃṁps Microsoft Word Mac vÃṁi PC,
vÃṁi kui sa jooksed dot kaldkriips Mario kohta Linuxi arvuti oma terminali aknas
nullid ja need, mis moodustavad Word vÃṁi Mario ladustatakse ajutiselt
Teie arvuti muutmÃĊlu nn teksti segment konkreetse programmi.
Allpool mis lÃĊheb vormindatud ja uninitialized andmed.
See on midagi sellist globaalsed muutujad, et me ei kasuta paljud,
kuid mÃṁnikord me oleme oli globaalsete muutujate
vÃṁi staatiliselt mÃĊÃĊratud stringe, mis on kÃṁva kodeeritud sÃṁnu nagu "tere"
mis ei ole tehtud kasutaja mis on kodeeritud oma programmi.
>> NÃỳÃỳd alumises otsas me on nn pinu.
Ja virna, seni oleme olnud kasutades milliseid eesmÃĊrgil?
Mis stack on kasutatud?
Jah?
>> SihtrÃỳhm: funktsioonid.
>> DAVID J. Humala: Funktsioonide?
Mis mÃṁttes funktsioonide?
>> SihtrÃỳhm: Kui te helistate funktsiooni argumendid kopeeritakse pinu.
>> DAVID J. Humala: TÃĊpselt.
Kui te helistate funktsiooni oma argumendid kopeeritakse pinu.
Nii et iga X vÃṁi Y vÃṁi A vÃṁi B et sa pÃĊÃĊsemist funktsioon
ajutiselt panna nn korstna
nagu Ãỳks Annenberg sÃ¶Ã¶gisaal plaate ja ka asjad
nagu kohalikud muutujad.
Kui teie foo funktsiooni vÃṁi oma swap funktsioon on kohalikud muutujad,
nagu temp, need kaks lÃṁpuks on virnas.
NÃỳÃỳd me ei rÃĊÃĊgi liiga palju neid, kuid need keskkonnamuutujateta
allosas nÃĊgime aega tagasi, kui Olin futzing klaviatuuri Ãỳks pÃĊev
ja hakkasin pÃĊÃĊseb asju nagu argv 100 vÃṁi argv 1000,
lihtsalt elements-- ma unustan numbers-- kuid
ei pidanud juurde mind.
Me hakkasime nÃĊgema mÃṁned funky sÃỳmbolid ekraanil.
Need olid nn keskkonnamuutujateta
nagu globaalne seadeid minu programmi vÃṁi minu arvuti, ei
mitteseotud viimastel viga, mis me arutasime,
Shellshock, mis on olnud kannatavad Ãỳsna vÃĊhe arvuteid.
>> NÃỳÃỳd lÃṁpuks, tÃĊnapÃĊeva fookus me lÃṁpuks hunnik.
See on veel Ãỳks patakas mÃĊlu.
Ja pÃṁhimÃṁtteliselt kÃṁik see mÃĊlu on sama vÃĊrk.
See on sama riistvara.
Oleme vaid omamoodi ravides erinevaid klastrite
baitide erinevatel eesmÃĊrkidel.
Hunnik on ka saab olema, kui muutujad ja mÃĊlu, et teil paluda
alates operatsioonisÃỳsteemi ajutiselt hoitakse.
>> Aga seal on mingi probleem siin, nagu pilt tÃĊhendab.
Meil on justkui kaks laevade kohta pÃṁrkuvad.
Sest kui te kasutate rohkem virna ja nagu me tÃĊna nÃĊeme
aastast, kui te kasutate rohkem ja rohkem hunnik, kindlasti halbu asju vÃṁib juhtuda.
Ja tÃṁepoolest, saame esile, et tahtlikult vÃṁi tahtmatult.
Nii et pinge viimase aega oli see programm,
mis ei teeni Ãỳhtegi funktsionaalne muul eesmÃĊrgil kui nÃĊidata
kuidas sa nii halb, vÃṁib tegelikult vÃṁtta ÃĊra vead kellegi programmi
ja Ãỳle vÃṁtta programmi vÃṁi isegi Kogu arvutisÃỳsteemi vÃṁi server.
Nii lihtsalt pilgu korraks, siis mÃĊrgata, et peamine allosas
vÃṁtab kÃĊsurea argumentide kohta argv.
Ja see on kÃṁne funktsioon f, sisuliselt nimetu funktsiooni nimetatakse
f, ja see kulgeb argv [1].
>> Nii et mis iganes sÃṁna kasutaja liigid juures kiiret pÃĊrast selle programmi nime,
ja siis see suvalise funktsiooni Ãỳles top, f, vÃṁtab string, AKA char *
sest me oleme hakanud arutama, ja see lihtsalt kutsub seda "bar".
Aga me vÃṁime seda kutsuda midagi.
Ja siis ta teatab, sees f array tÃĊhemÃĊrki
nimetatakse c-- 12 sellist mÃĊrki.
>> NÃỳÃỳd, aasta lugu ma Ãỳtlen Hetk tagasi, kui mÃĊlu
on c, vÃṁi on need 12 tÃĊhemÃĊrki lÃĊheb lÃṁpuks?
Lihtsalt olla kindel.
Jah?
>> SihtrÃỳhm: korstnat.
>> DAVID J. Humala: korstnat.
Nii on c kohaliku muutuja.
Me palume 12 tÃĊhemÃĊrki vÃṁi 12 baiti.
Need hakkavad lÃṁpuks aasta nn pinu.
NÃỳÃỳd lÃṁpuks on see teine ââfunktsioon see on tegelikult pÃĊris kasulik,
aga meil ei ole tegelikult kasutatud ta ise strncopy.
See tÃĊhendab string koopia, kuid ainult n tÃĊhed, n tÃĊhemÃĊrki.
Nii n mÃĊrgid kopeeritud baar arvesse c.
Ja kui palju?
Pikkus baari.
Nii teisisÃṁnu, et Ãỳks liin, strncopy,
lÃĊheb kopeerida tÃṁhusalt baar c.
>> NÃỳÃỳd, lihtsalt selline ennetada Moraal sellest loost,
mis on potentsiaalselt probleemne siin?
Kuigi me kontrollime pikkus baar ja kulgeb see strncopy,
Mis on su soole Ãỳtlen sulle ei ikka katki selle programmi?
Jah?
>> SihtrÃỳhm: Ei sisalda ruumi null iseloomu.
DAVID J. Humala: Ei sisalda ruumi null iseloomu.
Potentsiaalselt erinevalt varasem praktika me isegi ei
on nii palju kui pluss 1 kuni mahutada, et null iseloomu.
Aga see on veel hullem kui see.
Mida muud me ei suuda teha?
Jah?
>> SihtrÃỳhm: [kuuldamatu]
DAVID J. Humala: Perfect.
Me oleme kÃṁvasti kodeeritud 12 pÃĊris suvaliselt.
See ei ole nii palju probleem, vaid asjaolu
et me ei ole isegi kontrollida, kas pikkusega riba on vÃĊiksem kui 12,
sellisel juhul saab olema ohutu panna see mÃĊllu
nimetatakse c, et oleme eraldatud.
TÃṁepoolest, kui riba on nagu 20 tÃĊhemÃĊrki pikk,
Selle funktsiooni nÃĊib kopeerides 20 mÃĊrki baar arvesse c, mis
vÃṁttes vÃĊhemalt 8 baiti et see ei tohiks olla.
See tÃĊhendas siin.
>> LÃỳhidalt Ã¶eldes katki programmi.
Mitte nii suur asi.
Ãkki saad killustatust sÃỳÃỳ.
Me kÃṁik oleme olnud vead programmides.
Me kÃṁik vÃṁib olla vigu programmides kohe.
Aga mis on kaudselt?
Noh, siin on suumitud-in versioon et pilt minu arvuti mÃĊllu.
See on alt mu virna.
Ja tÃṁepoolest, vÃĊga pÃṁhjas on see, mis kutsus vanem rutiinne stack, fancy viis
Ã¶elda, et see on peamine.
Nii et kes nimetatakse funktsiooni f, mis me rÃĊÃĊgime.
Nii et see on pÃṁhja pinu.
Tagasi aadress on midagi uut.
See on alati olemas olnud, alati olnud, et pilt.
Me lihtsalt ei helistanud tÃĊhelepanu.
Sest selgub, kuidas c tÃ¶Ã¶tab, on et kui Ãỳks funktsioon nÃṁuab teise
mitte ainult teha argumente, mis funktsioon saada surunud peale virna,
mitte ainult ei funktsiooni kohaliku muutujad saada surunud peale virna,
midagi, mida nimetatakse saatja aadress Samuti saab panna peale virna.
TÃĊpsemalt, kui peamised kÃṁned foo, peamised on oma aadress mÃĊllu, hÃĊrg midagi,
tegelikult saab panna peale virna nii, et kui f on tehtud kÃĊivitamata
teab, kuhu hÃỳpata tagasi tekstis segment, et jÃĊtkuvalt tÃĊidetakse.
>> Nii et kui me siin oleme kontseptuaalselt aastal peamine, siis f saab nn.
Kuidas f tea, kes et kÃĊsitsi kontrolli tagasi?
Noh, see vÃĊike riivsai punaselt siin
nimetatakse saatja aadress, see lihtsalt kontrolli, mis seisneb selles, et saatja aadress?
Oh, andke mulle tagasi hÃỳpata Otse siin.
Ja see on natuke Ãỳlelihtsustatuna,
sest nulli ja need jaoks peamine on tehniliselt
siia Ãỳles tech segment.
Aga see mÃṁte. f lihtsalt peab teadma, mida
kus kontroll lÃṁpuks lÃĊheb tagasi.
>> Aga kuidas arvutid on ammu sÃĊtestatud asjad
nagu kohalikud muutujad ja argumendid on niimoodi.
Nii peal see pilt sinine on freimi jaoks f, nii et kÃṁik
ning mÃĊlu, et f konkreetselt ei kasuta.
Nii et jÃĊrelikult mÃĊrgata, et baar on siin pildil.
Baar oli tema argument.
Ja me vÃĊita, et argumendid funktsioonid vajutata peale virna.
Ja c, on muidugi see, ka seda pilti.
>> Ja just TÃĊhistused eesmÃĊrkidel, teate Ãỳlaosas vasakul nurgas
on see, mis oleks c sulg 0 ja siis veidi alla paremale
on c sulg 11.
Nii teisisÃṁnu, te vÃṁite ette kujutada et seal on ruudustik baiti
seal, esimene on Ãleval vasakul on pÃṁhjas, mis
on viimase nendest 12 baiti.
>> Aga nÃỳÃỳd proovida kiiresti edasi.
Mis hakkab juhtuma siis, kui vÃṁtame string riba, mis on enam kui c?
Ja me ei ole kontrollida, kas see on tÃṁesti enam kui 12.
Milline osa sellest pilt lÃĊheb saada kirjutatakse baiti 0, 1, 2, 3,
dot dot dot, 11 ja seejÃĊrel halb, 12, 13 kuni 19?
Mis juhtub siin, Kui te jÃĊreldada tellimine
et c sulg 0 on peal ja c sulg 11 on justkui maha
paremale?
Jah?
>> SihtrÃỳhm: Noh, see lÃĊheb kirjutada char * baar.
>> DAVID J. Humala: Jah, see nÃĊeb vÃĊlja nagu sa lÃĊhed kirjutada char * baar.
Ja mis veel hullem, kui saadate tÃṁesti pikk string, siis vÃṁib isegi kirjutada, mida?
Saatja aadress.
Mis jÃĊllegi on nagu riivsai Ã¶elda programmi, kus
tagasi minna, kui f tehakse kutsutakse.
>> Mida pahad tavaliselt teha on see, kui nad kohanud programmi
et nad on uudishimulik, kas on kasutatavust, lollakas viisil
et ta vÃṁib vÃṁtta ÃĊra, mis viga,
Ãldiselt nad ei saa Selle Ãṁiguse esmakordselt.
Nad lihtsalt saatma hakata, nÃĊiteks juhuslikult koostatud stringe oma programmi
kas klaviatuuri, vÃṁi ausalt Ã¶eldes nad ilmselt
kirjutada vÃĊike programm lihtsalt automaatselt genereerida stringid,
ja hakata peksma oma programmi saates palju erinevaid sisendeid
erineva pikkusega.
>> Niipea, kui teie programm jookseb kokku, see on hÃĊmmastav asi.
Sest see tÃĊhendab, et ta vÃṁi ta on avastanud
mis on ilmselt tÃṁepoolest viga.
Ja siis nad saavad rohkem targad ja alustada keskendudes kitsamalt
kuidas kasutada, et viga.
EelkÃṁige, milline ta vÃṁib tegema, on saata, parimal juhul, tere.
Ei midagi erilist.
See on string, mis on piisavalt lÃỳhike.
Aga mis siis, kui ta saadab, ja me Ãỳldistada seda,
rÃỳnnak code-- nii nulli ja need, kes teevad asju
nagu rm-rf, et eemaldada kÃṁik kÃṁvakettale vÃṁi saata rÃĊmpsposti
vÃṁi kuidagi rÃỳnnata masin?
>> Seega, kui kÃṁik need tÃĊhed lihtsalt on,
kontseptuaalselt, rÃỳnnak, rÃỳnnak, rÃỳnnak, rÃỳnnak, halbu kood
et keegi kirjutas, kuid kui see inimene on piisavalt tark,
mitte ainult hÃṁlmama kÃṁiki Nende rm-RFS, vaid ka
on tema viimastel baiti olla number, mis vastab
Lisa aadress tema vÃṁi tema enda rÃỳnnak kood
et ta mÃ¶Ã¶dunud aastal vaid esitades kÃỳsimuse jÃĊrel
saate tÃṁhusalt trikk arvuti arvesse mÃĊrganud, kui f on teinud tÃĊidesaatva,
Oh, see on minu jaoks aega hÃỳpata tagasi punane saatja aadress.
Aga kuna ta on kuidagi kattusid et saatja aadress
oma number, ja nad on piisavalt targad,
et on konfigureeritud, et number viidata, kui
nÃĊed super top vasakus nurgas,
tegeliku aadressi arvuti mÃĊlestuseks mÃṁned nende rÃỳnnaku kood,
paha poiss saab trikk arvuti arvesse tÃĊidesaatva enda kood.
>> Ja see kood uuesti, vÃṁib olla mis iganes.
See on tavaliselt nimetatakse shell kood, mis on lihtsalt
viis Ã¶elda, et see ei ole Ãỳldiselt midagi nii lihtne rm-rf.
See on tegelikult midagi Bash, vÃṁi tegelik programm, mis annab talle
vÃṁi tema programmilisi kontrolli teostada midagi muud, mis nad tahavad.
LÃỳhidalt Ã¶eldes, see kÃṁik tuleneb tÃṁsiasjast,
et see viga on seotud mitte kontrollida piire oma valikut.
Ja kuna teed arvutite tÃ¶Ã¶d on, et nad
kasuta virna tÃṁhusalt, kontseptuaalselt
alt Ãỳlesse, kuid siis elemendid surute peale virna kasvab Ãỳlevalt alla,
see on uskumatult problemaatiline.
NÃỳÃỳd on vÃṁimalusi tÃ¶Ã¶tada selle Ãỳmber.
Ja ausalt Ã¶eldes, on keeled kellega tÃ¶Ã¶tada selle Ãỳmber.
Java on immuunsÃỳsteemi, nÃĊiteks selles konkreetses kÃỳsimuses.
Sest nad ei anna teile vihjeid.
Nad ei anna teile otsene mÃĊlu aadressid.
Nii et see vÃĊgi, mis meil on puudutada midagi mÃĊlestuseks
soovime tuleb kÃỳll suur risk.
>> Nii et hoidke silmad lahti.
Kui aus olla, siis on kuu vÃṁi aastaid, millal
lugesid mÃṁned ÃĊrakasutamise programmi vÃṁi server,
kui sa kunagi nÃĊha vihjet midagi nagu buffer overflow rÃỳnnak,
vÃṁi stack overflow on teist tÃỳÃỳpi rÃỳnnak, sarnase sisuga,
palju inspireerib veebisaidi nimi, kui sa tead seda,
see on kÃṁik rÃĊÃĊgime lihtsalt tÃĊis suurust mÃṁned iseloomu
massiiv vÃṁi mÃṁni massiivi Ãỳldisemalt.
KÃṁik kÃỳsimused, siis selles kÃỳsimuses?
Ãrge proovige seda kodus.
>> Olgu.
Nii malloc Seni on meie uus sÃṁber, et saame eraldada mÃĊlu
et me ei pruugi teada, ette, et me tahame, et meil ei ole
kÃṁva kood meie Programmi numbrid nagu 12.
Kui kasutaja Ãỳtleb meile, kui palju Andmete ta tahab sisend,
saame malloc et palju mÃĊlu.
>> Nii malloc selgub, et mÃĊÃĊral oleme seda kasutanud,
sÃṁnaselgelt viimast korda, ja siis Te olete seda kasutanud
jaoks getString teadmatult eest mitu nÃĊdalat, kÃṁik malloc mÃĊllu
pÃĊrineb nn hunnik.
Ja see on pÃṁhjus, miks getString nÃĊiteks vÃṁib eraldada mÃĊlu dÃỳnaamiliselt
teadmata, mida sa oled lÃĊheb kirjuta ette,
kÃĊe tagasi pointer, et mÃĊlu ja et mÃĊlu on ikka sinu hoida,
isegi pÃĊrast getString tulu.
Sest tagasivÃṁtmine ju, et stack on pidevalt lÃĊheb Ãỳles ja alla,
Ãỳles ja alla.
Ja niipea, kui see lÃĊheb sÃĊtestatakse, et mis tahes mÃĊlu
seda funktsiooni kasutada tuleks ei tohi kasutada keegi teine.
See prÃỳgi vÃĊÃĊrtused nÃỳÃỳd.
>> Aga hunnik on siin.
Ja mis on tore malloc on see, et kui malloc eraldab mÃĊlu siin,
see ei mÃṁjutanud, sest pÃṁhiliselt virna.
Ja nii iga funktsiooni saab kasutada mÃĊlu, mis on malloc'd,
isegi funktsioon nagu getString, isegi pÃĊrast seda tagasi.
>> NÃỳÃỳd vastupidist malloc on tasuta.
Ja tÃṁepoolest, Ãṁigusriigi sa vaja alustada vastuvÃṁtmist
on midagi, mis tahes, iga kord, kui kasutate malloc peate ise kasutada tasuta lÃṁpuks
aasta sama pointer.
Kogu selle aja oleme olnud kirjalikult lollakas, lollakas kood, mitmel pÃṁhjusel.
Kuid Ãỳks, mis on olnud kasutades CS50 raamatukogu, mis
iseenesest on sihilikult lollakas, see lekib mÃĊlu.
Iga kord, kui sa oled kutsutud getString Viimase paari nÃĊdala jooksul
Me palume operatsioonisÃỳsteemi sÃỳsteemi, Linux, mÃĊlu.
Ja sa ei ole kunagi kunagi andnud seda tagasi.
Ja see ei ole a harjutada, hea asi.
>> Ja Valgrind Ãỳks vahendeid kasutusele pset 4,
on kÃṁike, mis aitab teil nÃỳÃỳd leida vigu niimoodi.
Aga Ãṁnneks pset 4 sa ei pea kasutada CS50 raamatukogu vÃṁi getString.
Nii tahes vigu, mis on seotud mÃĊlu on lÃṁpuks saab olema oma.
>> Nii malloc on rohkem kui lihtsalt mugav selleks.
Me ei saa tegelikult nÃỳÃỳd lahendada pÃṁhimÃṁtteliselt erinevad probleemid,
ja pÃṁhimÃṁtteliselt lahendada probleeme rohkem tÃṁhusalt nÃĊdalas null lubadust.
Senini on see seksikaim andmestruktuur oleme olnud.
Ja andmestruktuur ma tÃĊhenda ainult viis kontseptualiseerimiseks mÃĊlu
viisil, mis lÃĊheb kaugemale lihtsalt Ã¶eldes see on int, see on paalia.
Me ei saa hakata klastri asju koos.
>> Nii massiivi nÃĊgi vÃĊlja selline.
Ja mis oli vÃṁti kohta massiiv on, et see annab sulle
back-to-back tÃỳkkideks mÃĊlu, millest igaÃỳks
saab olema sama tÃỳÃỳpi, int, int, int, int vÃṁi char, char, char,
char.
Aga seal on mÃṁned varjukÃỳljed.
See on nÃĊiteks massiivi suurus kuus.
Oletame, et tÃĊita seda massiivi kuus numbrid ja siis mingil pÃṁhjusel,
Sinu kasutaja tahab anda sa seitsmes number.
Kust sa seda?
>> Mis on lahendus, kui teil on loodud massiivi korstnat
nÃĊiteks lihtsalt koos nÃĊdalal kaks mÃĊrke, et oleme kasutusele
ruudu sulgudes number sees?
Noh, sul on kuus numbrid need kastid.
Mida su instinktid olema?
Kuhu sa tahad seda?
>> SihtrÃỳhm: [kuuldamatu]
>> DAVID J. Humala: Vabandust?
>> SihtrÃỳhm: Pane see lÃṁpuni.
>> DAVID J. Humala: Pane see lÃṁpuni.
Nii lihtsalt Ãỳle paremale, vÃĊljaspool seda kasti.
Milline oleks tore, kuid see Selgub, sa ei saa seda teha.
Sest kui sa ei kÃỳsita Selle patakas mÃĊlu,
see vÃṁib olla juhus, et see kasutatakse mÃṁne muu muutuja
kokku.
MÃṁtle tagasi nÃĊdala vÃṁi nii, kui me ette vÃĊlja Zamyla ja Davin ja Gabe nimed
mÃĊllu.
Nad olid sÃṁna otseses mÃṁttes tagasi tagasi tagasi.
Nii et me ei saa alati usun, et kÃṁike, mis on
siin on olemas minu jaoks kasutada.
>> Mida veel vÃṁiks teha?
Noh, Ãỳks kord aru, sa vajame massiivi suurus seitse,
vÃṁid lihtsalt luua massiivi suurus seitse, siis kasuta
loop vÃṁi samas loop, kopeerige see uue massiivi,
ja siis kuidagi lihtsalt vabaneda Selle massiivi vÃṁi lihtsalt kasutamise lÃṁpetamiseks.
Aga see ei ole eriti tÃṁhus.
ÃhesÃṁnaga, massiivid ei lase sa dÃỳnaamiliselt suurust.
>> Nii et Ãỳhest kÃỳljest saad muutmÃĊlu, mis on hÃĊmmastav.
Sest see vÃṁimaldab meil teha asju nagu lÃṁhe ja vallutada,
binaarne otsing, mis kÃṁik me oleme rÃĊÃĊkis ekraanil siin.
Aga sa vÃĊrvi ise nurka.
Niipea kui sa tabanud lÃṁpuks oma valikut,
mida sa pead tegema vÃĊga kallis operatsioon
vÃṁi kirjutada terve hunnik koodi nÃỳÃỳd tegeleda selle probleemiga.
>> Mis siis, kui selle asemel oli meil midagi, mida nimetatakse nimekiri,
vÃṁi ahelloend eriti?
Mis siis, kui selle asemel, et ristkÃỳlikud seljad tagasi,
meil on ristkÃỳlikud, mis jÃĊtavad vÃĊhe natuke kÃṁigutama ruumi nende vahel?
Ja kuigi ma olen koostanud kÃĊesoleva pilt vÃṁi kohandatud seda pilti
Ãỳhest tekste siin tuleb tagasi seljad vÃĊga korrapÃĊrane, tegelikult,
Ãỳks neist ristkÃỳlikud vÃṁiks olla siin mÃĊlu.
Ãks neist vÃṁiks olla siin Ãỳleval.
Ãks neist vÃṁiks olla siin Ãỳleval, siin, ja nii edasi.
>> Aga mis siis, kui me joonistasin, sel juhul nooled
et kuidagi seostada neid ristkÃỳlikuid koos?
TÃṁepoolest, me oleme nÃĊinud tehniline kehastus nool.
Mida oleme kasutatud viimastel pÃĊeva, et all kapuuts,
esindaks nool?
Pointer, eks?
>> Mis siis, kui selle asemel, et lihtsalt ladustamiseks numbrid,
nagu 9, 17, 22, 26, 34, Mis siis, kui me ei salvestata mitte
ainult number, kuid osuti kÃṁrvuti sellise arvu?
Nii et palju nagu sa oleks niit nÃṁel lÃĊbi terve hunnik kangast,
kuidagi sidumine asjad koos, samamoodi ei saa
me koos suunanÃĊitajaks, kui kehastunud nooltega siin
liiki jutustama koos individuaalsete ristkÃỳlikud
tÃṁhusalt kasutades pointer kÃṁrvuti number, et
mÃĊrgib, et mÃṁned jÃĊrgmine number, et osutab omakorda mÃṁned jÃĊrgmine number?
Nii teisisÃṁnu, mida kui me tegelikult tahtsime
rakendada midagi sellist?
Noh kahjuks need ristkÃỳlikud, vÃĊhemalt Ãỳks 9, 17, 22,
ja nii edasi, need ei ole enam kena ruudud Ãỳhte numbrid.
Alt, ristkÃỳlik Allpool 9, nÃĊiteks
nÃĊitab, mida peaksid olema pointer, 32 bitti.
NÃỳÃỳd, ma ei ole veel teadlik mis tahes andmete tÃỳÃỳp C, mis annab teile mitte ainult int
kuid pointer tÃĊielikult.
>> Mis siis lahendus, kui tahame leiutada oma vastus sellele?
Jah?
>> SihtrÃỳhm: [kuuldamatu]
>> DAVID J. Humala: Mis see on?
>> SihtrÃỳhm: Uus struktuur.
>> DAVID J. Humala: Jah, miks ei me luua uus struktuur,
vÃṁi C, struct?
Me oleme nÃĊinud structs enne, kui lÃỳhidalt, kus tegelesime Ãṁpilane struktuur
nagu see, kellel oli nimi ja maja.
In pset 3 Breakout sa kasutada kogu hunnik structs-- GRect ja GOvals
et Stanford loodud klastri info koos.
Mis siis, kui me vÃṁtame selle sama idee mÃĊrksÃṁnad "typedef" ja "struct"
ja siis mÃṁned ÃỳliÃṁpilane spetsiifilised asjad, ja arenema seda arvesse jÃĊrgmised:
typedef struktuure node-- ja sÃṁlm lihtsalt vÃĊga generic arvutiteadus
perspektiivis midagi andmestruktuur, konteinerit andmestruktuur.
SÃṁlme VÃĊidan lÃĊheb on int n, tÃĊiesti arusaadav,
ja siis veidi salapÃĊraselt, see teine ââjoon, struct node * kÃṁrval.
Aga vÃĊhem tehnilisi termineid, Mis on see, et teine âârida
koodi sees looksulg?
Jah?
>> SihtrÃỳhm: [kuuldamatu]
DAVID J. Humala: kursor teise sÃṁlme.
Nii tÃṁsi, sÃỳntaks veidi segasena.
Aga kui sa loed seda sÃṁna otseses mÃṁttes, JÃĊrgmine on nime muutuja.
Mis on selle andmetÃỳÃỳbi?
See on veidi verbaalselt, seekord aga see tÃỳÃỳp struct node *.
Iga kord, kui me oleme nÃĊinud midagi star, et tÃĊhendab, et see kursor andmete tÃỳÃỳp.
Nii et jÃĊrgmine on ilmselt kursor struct node.
>> NÃỳÃỳd, mis on struct node?
Noh, teate te nÃĊete neid samad sÃṁnad Ãỳlevalt paremalt.
Ja tÃṁepoolest, te vaadake ka sÃṁna "SÃṁlm" siin all vasakul.
Ja see on tegelikult lihtsalt mugavuse.
Pange tÃĊhele, et meie Ãṁpilane mÃĊÃĊratlus seal on sÃṁna "Ãṁpilane" ainult Ãỳks kord.
Ja see on sellepÃĊrast, et ÃỳliÃṁpilane objekti ei eneseleosutavad.
Seal ei ole midagi sees Ãṁpilane mis vajab punktist teise ÃỳliÃṁpilase,
persay.
See oleks omamoodi imelik reaalses maailmas.
>> Kuid sÃṁlmega seotud nimekiri, me ei taha sÃṁlme
olema referentsiaalse sarnase objekti.
Ja nii mÃĊrkate muutusi siin ei ole lihtsalt, mis seal sees looksulg.
Aga me lisada sÃṁna "sÃṁlm" Ãỳlaosas, samuti
lisades selle alt asemel "Ãṁpilane".
Ja see on vaid tehniline detail nii et jÃĊlle oma andmestruktuur
saab eneseleosutavad, nii et sÃṁlm vÃṁib juhtida ka teise sellise sÃṁlme.
>> Nii et mis see on lÃṁppkokkuvÃṁttes lÃĊheb meie jaoks tÃĊhendab?
Noh, Ãỳks, seda kraami sees on sisu meie sÃṁlme.
See asi siin, Paremal Ãỳlal on lihtsalt nii
veel kord, et me ei viita endale.
Ja siis ÃĊÃĊrepoolseimate kraami kuigi sÃṁlm on uus mÃṁiste,
vÃṁib-olla, et see on ikka sama Ãṁpilane ja mida
oli all kapuuts SPL.
>> Nii et kui me nÃỳÃỳd tahtis alustada rakendamisel seotud nimekirja,
kuidas vÃṁiks tÃṁlkida midagi sellist koodi?
Noh, lihtsalt vaata nÃĊide programm, mis
tegelikult kasutab seotud nimekirja.
Seas tÃĊnapÃĊeva jaotus kood on programm nimega Eesti Zero.
Ja kui ma saan seda ma loodud super lihtne GUI, graafiline kasutajaliides,
aga see on tÃṁesti lihtsalt printf.
Ja nÃỳÃỳd ma olen andnud ennast mÃṁne menÃỳÃỳ options-- Kustuta, Lisa, otsing,
ja Traverse.
Ja lÃṁpetan.
Need on vaid Ãỳhised toimingud andmestruktuur tuntud lingi nimekirja.
>> NÃỳÃỳd Kustuta lÃĊheb Numbri kustutamine nimekirjast.
Sisesta lÃĊheb lisada number nimekirjas.
Otsi lÃĊheb otsima jaoks number nimekirjas.
Ja Traverse on lihtsalt fancy viis Ã¶elda, kÃṁndida lÃĊbi nimekirja
prindi see vÃĊlja, kuid see on kÃṁik.
Ãra muuda see kuidagi.
>> Nii et proovime seda.
LÃĊhme edasi ja 2. tÃỳÃỳpi.
Ja siis ma lÃĊhen sisestada, Ãỳtleme 9.
Sisesta.
Ja nÃỳÃỳd mu programm on lihtsalt programmeeritud Ã¶elda, nimekiri on nÃỳÃỳd 9.
NÃỳÃỳd, kui ma edasi minna ja ei Paigaldage uuesti, lase
mul minna ja vÃĊlja suumida ja kirjuta 17.
NÃỳÃỳd on mu nimekirjas on 9, siis 17.
Kui ma sisestada uuesti, lÃĊhme vahele Ãỳks.
Selle asemel, et 22, kui Ãỳhe pildi me oleme otsinud siin, las ma sinna hÃỳpata
ja lisada 26 jÃĊrgmine.
Nii et ma lÃĊhen kirjuta 26.
Nimekiri on mul oodata.
Aga nÃỳÃỳd, lihtsalt et nÃĊha, kas see kood saab olema paindlik, andke mulle nÃỳÃỳd
tÃỳÃỳp 22, milles vÃĊhemalt kontseptuaalselt, kui me oleme
Hoides seda sorteerida, mis on tÃṁepoolest saab veel Ãỳhe vÃĊrava kohe,
peaks minema vahemikus 17 ja 26.
Nii et ma Enter.
TÃṁepoolest, mis tÃ¶Ã¶tab.
Ja nÃỳÃỳd lubage mul lisada Viimase kohta pilt, 34.
>> Olgu.
Nii et nÃỳÃỳd las ma ette nÃĊha, et Kustuta ja Traverse ja otsing teha,
tegelikult tÃ¶Ã¶tavad.
Tegelikult, kui ma joosta Search, olgem otsida number 22, Enter.
Ta leidis 22.
Nii et on, mida see Programmi Eesti Zero teeb.
>> Aga mis tegelikult toimub kohta, mis rakendab seda?
Noh, esiteks ma vÃṁib-olla, ja tÃṁepoolest Ma ei ole, fail nimega list0.h.
Ja kusagil on see line, typedef, struct node,
siis on mul looksulg, int n, ja siis struct-- mis oli mÃṁiste?
Struct node kÃṁrval.
Seega peame star.
NÃỳÃỳd tehniliselt kui me sattuda harjumus joonistus siin.
VÃṁite nÃĊha Ãṁpikute ja Internetis viited seda seal.
See on funktsionaalselt samavÃĊÃĊrne.
Tegelikult on see natuke rohkem iseloomulik.
Aga ma tulen kooskÃṁlas sellega, mida eelmisel korral ja seda teha.
Ja siis lÃṁpuks, ma lÃĊhen seda tegema.
>> Nii pÃĊisefailist kusagil on list0.h
tÃĊna on see struct mÃĊÃĊratlus, ja vÃṁibolla mÃṁned muud kraami.
Vahepeal list0c seal kavatse olla mÃṁned asjad.
Aga me lihtsalt alustada ja ei lÃṁpeta seda.
List0.h on fail tahan lisada oma C-faili.
Ja siis mingil hetkel ma olen lÃĊheb on int, peamine, tÃỳhine.
Ja siis ma lÃĊhen mÃṁned to-do on siin.
Ma olen ka kavatse olla prototÃỳÃỳp, nagu tÃỳhine, otsing, int,
n, mille eesmÃĊrk elus on otsida element.
Ja siis siin ma vÃĊita TÃĊnapÃĊeva kood, tÃỳhine, otsing, int n,
no semikooloniga kuid avatud looksulg.
Ja nÃỳÃỳd ma tahan kuidagi otsida element selles loetelus.
Aga meil ei ole piisavalt informatsiooni ekraanil veel.
Ma ei ole tegelikult esindatud nimekiri ise.
Nii et Ãỳks viis, kuidas me vÃṁiks rakendada seotud nimekirja programmi
on mul selline tahan teha midagi nagu kuulutab seotud nimekirja siin.
Lihtsuse mÃṁttes ma lÃĊhen tegema Selle Ãỳlemaailmse, kuigi Ãỳldiselt me
ei tohiks seda liiga palju.
Aga see NÃĊite lihtsustamiseks.
Nii et ma tahan kuulutada seotud nimekirja siin.
NÃỳÃỳd, kuidas vÃṁiks seda teha?
>> Siin on pilt, mis on seotud nimekirja.
Ja ma tÃṁesti ei hetkel teada, kuidas
Ma lÃĊhen edasi minna esindavad nii palju asju vaid Ãỳhe
muutuja mÃĊlu.
Aga arvan, et tagasi hetkel.
Kogu selle aja oleme olnud stringid, mis me siis
selgus, et massiive mÃĊrki, mis me siis
selgus, et lihtsalt olla pointer Lisa esimese mÃĊrgi
array tÃĊhemÃĊrki et on null lÃṁpetada.
Nii et selle loogika ja selle pilt liiki kÃỳlv oma mÃṁtteid,
mida vaja me tegelikult kirjutada meie kood esindama seotud nimekirja?
Kui palju seda teavet me vajame lÃỳÃỳa C kood, mis sa Ãỳtled?
Jah?
>> SihtrÃỳhm: Meil ââon vaja viit sÃṁlme.
DAVID J. Humala: kursor sÃṁlme.
Eriti mis sÃṁlme oleks oma instinktid on hoida kursorit?
>> SihtrÃỳhm: esimene sÃṁlm.
>> DAVID J. Humala: Jah, ilmselt esimene.
Ja teate, esimene sÃṁlm on erineva kujuga.
See on ainult poole vÃĊiksem struktuure, sest see on tÃṁesti ainult pointer.
Nii et see, mida saab tÃṁesti teha, on tunnistada ahelloend olema tÃỳÃỳpi sÃṁlme *.
Ja olgem lihtsalt nimetame seda esimest ja initsialiseerida see tÃỳhjaks.
Nii null jÃĊllegi on tulemas sellele pildile siin.
Mitte ainult null kasutada nagu erilist tagastatav vÃĊÃĊrtus asjad getString
ja malloc, null on null pointer puudumine pointer,
kui soovite.
See tÃĊhendab lihtsalt, midagi on veel siin.
NÃỳÃỳd esimene, ma oleks pidanud nimetatakse seda kÃṁike.
Ma oleks vÃṁinud nimetas seda "nimekiri" vÃṁi mitmeid muid asju.
Aga ma kutsun seda "esimene", nii et see ridade jÃĊrele see pilt.
Nii nagu string vÃṁib olla esindatud koos aadressi esimese baidi,
nii saab seotud nimekirja.
Ja me nÃĊeme, muud andmed struktuurid on esindatud
vaid Ãỳks pointer, 32-bit nool, mis osutab
vÃĊga esimesel sÃṁlme struktuuri.
>> Aga nÃỳÃỳd lÃĊhme ennetada probleemi.
Kui ma vaid meeles pidada minu programm aadress
ning esimene sÃṁlm, esimese ruut selles andmestruktuur,
Mis oleks parem olla nii umbes rakendamise mu ÃỳlejÃĊÃĊnud nimekiri?
Mis peamine detail, mis lÃĊheb tagada see tegelikult toimib?
Ja "tegelikult tÃ¶Ã¶tab" I TÃĊhendab, palju nagu string,
laseb meil minna esimene mÃĊrk aastal Davin nime teiseks
Lisa kolmandaks Neljas, kuni lÃṁpuni,
kuidas me teame, kui me aasta lÃṁpus on seotud nimekirja, mis nÃĊeb vÃĊlja nagu see on?
Kui see on null.
Ja ma olen esindatud selline nagu nagu elektriinsener vÃĊest,
koos vÃĊhe madalikule sÃỳmbol, kehvasti.
Aga see tÃĊhendab lihtsalt null kÃĊesolevas asjas.
VÃṁite teha seda iga number viisil, kuid selle autor
juhtus, et kasutada seda sÃỳmbolit siin.
>> Nii kaua, kui me nÃ¶Ã¶rile kÃṁik need sÃṁlmed kokku
ainult mÃĊleta, kuhu Esimene on, nii kaua
kui me paneme erilist sÃỳmboli vÃĊga viimase sÃṁlme nimekirja
ja me kasutame null, sest see on mis meil on meie kÃĊsutuses,
see nimekiri on tÃĊielik.
Ja isegi kui ma ainult teile kursor Esimene element, sa, programmeerija,
saab kindlasti juurde edasi.
Kuid olgem lase oma meeled tiir natuke,
kui nad ei ole juba Ãỳsna wandered-- mis
saab sÃṁiduaega leida midagi selles nimekirjas?
Kurat, see on suur O n, mis ei ole halb, Ãṁiglus.
Aga see on lineaarne.
Oleme loobunud mida funktsioon massiivid, liikudes rohkem
suunas see pildi dÃỳnaamiliselt pÃṁimitud vÃṁi seotud sÃṁlmed?
Me oleme loobunud muutmÃĊlu.
Massiiv on tore, sest matemaatiliselt kÃṁik
on seljad et seljad.
Kuigi seda pilti tundub pÃĊris, ja isegi
kuigi tundub, et need sÃṁlmed on ilusti vahedega, tegelikkuses
nad vÃṁivad olla kÃṁikjal.
OX1, Ox50, Ox123, Ox99 need sÃṁlmed vÃṁivad olla kÃṁikjal.
Kuna malloc ei eraldada mÃĊlu laduma, kuid kÃṁikjal hunnik.
Sa ei pruugi teada, et see on lÃĊheb tagasi tagasi tagasi.
Ja nii see pildi reaalsus ei kavatse olla pÃĊris see ilus.
>> Nii see lÃĊheb vÃṁtab natuke tÃ¶Ã¶le rakendada seda funktsiooni.
Nii et olgem rakendada Otsi.
Ja me nÃĊeme, millist nutikas viis seda teha.
Nii et kui ma otsingu funktsiooni ja Ma antud muutuja tÃĊisarv n
otsida, ma pean teadma, uus sÃỳntaks otsin sees
struktuur, mis on osutas, et leida n.
Nii et teeme seda.
>> Nii et kÃṁigepealt ma lÃĊhen edasi ja kuulutada sÃṁlme *.
Ja ma kutsun seda pointer, lihtsalt kokkuleppeliselt.
Ja ma initsialiseerida see esimene.
Ja nÃỳÃỳd ma saan seda aastal mitmel viisil.
Aga ma lÃĊhen vÃṁtta Ãỳhine lÃĊhenemisviis.
Kuigi osuti ei ole vÃṁrdne null, ja see on kehtiv sÃỳntaks.
Ja see tÃĊhendab lihtsalt seda jÃĊrgmise, nii Niikaua kui sa ei osutavad midagi.
Mida ma tahan teha?
>> Kui osuti dot n, lubage mul tagasi tulla sellele vÃṁrdub-- vÃṁrdub mis?
Mis vÃĊÃĊrtust ma otsin?
Tegelik n, mis oli mÃ¶Ã¶dunud aastal.
Nii et siin on veel Ãỳks omadus, C ja paljudes keeltes.
Kuigi struktuuri nimetatakse sÃṁlm on vÃĊÃĊrtus n, tÃĊiesti Ãṁigustatud
et ka kohalikud argument vÃṁi muutuja nimega n.
Sest isegi me koos inimese silmad, vÃṁib eristada
et see n on eeldatavasti sellest erinevad n.
Kuna sÃỳntaks on erinev.
Sul on dot ja pointer, arvestades, et see Ãỳks ei ole sellist asja.
Nii et see on OK.
See on OK, et helistada neile samu asju.
>> Kui ma sind leida, ma olen lÃĊhed tahan teha midagi
nagu teatada, et oleme leidnud n.
Ja me lahkume, et kui kommentaar vÃṁi pseudokoodi kood.
Else, ja siin on Huvitav osa, mida
ma tahan teha, kui aktiivse sÃṁlme ei ole seal n, et ma hoolin?
Kuidas saavutada jÃĊrgmised?
Kui mu sÃṁrme Praegu on PTR ja see on
osutades mis tahes Esimene on osutavad,
kuidas ma liikuda mu sÃṁrme Lisa jÃĊrgmisel sÃṁlme koodi?
Noh, mis on riivsai oleme kavatse jÃĊrgida antud juhul?
SihtrÃỳhm: [kuuldamatu].
DAVID J. Humala: Jah, jÃĊrgmine.
Nii et kui ma lÃĊhen tagasi oma kood siia, tÃṁepoolest, ma olen
lÃĊheb minna ja Ã¶elda, pointer, mis on vaid ajutine variable-- see
imelik nimi, PTR, kuid see on nagu temp--
Ma lÃĊhen, et seada kursor vÃṁrdne iganes pointer on--
ja jÃĊlle, et see saab olema vÃĊike kÃĊru jaoks moment-- dot kÃṁrval.
TeisisÃṁnu, ma lÃĊhen vÃṁtan sÃṁrme, mis sihib seda sÃṁlme
siin ja ma Ãỳtlen, sa tead, mida, kui heita pilk jÃĊrgmisele vÃĊljale
ja liigutage oma sÃṁrme mis iganes see osutavad.
Ja see lÃĊheb korrata, korrata, korrata.
Aga kui ei oma sÃṁrme enam ei tee Ãỳldse midagi?
Niipea, mida koodirida tunda?
SihtrÃỳhm: [kuuldamatu]
DAVID J. Humala: Kui punkt samas osuti ei ole vÃṁrdne null.
Mingil hetkel mu sÃṁrm on kavatse olla vastakuti null
ja ma realiseerida see on lÃṁpuks see nimekiri.
NÃỳÃỳd on see vÃĊike hÃĊdavale lihtsuse.
Selgub, et kuigi me lihtsalt Ãṁppinud seda dot mÃĊrke
struktuuridele, osuti ei struct.
PTR on mis?
Lihtsalt olla nitpicky.
See on kursor sÃṁlme.
See ei ole sÃṁlm ise.
Kui mul ei olnud star siin, pointer absolutely-- see sÃṁlm.
See on nagu nÃĊdal Ãỳks deklaratsiooni muutuja,
kuigi sÃṁna "sÃṁlm" on uus.
>> Aga niipea, kui me vÃṁtame kasutusele star, see on nÃỳÃỳd kursor sÃṁlme.
Ja kahjuks ei saa kasutada dot mÃĊrke pointer.
Sa pead kasutama noole mÃĊrke, mis silmatorkavalt,
on esimene kord, iga tÃỳkk sÃỳntaks nÃĊeb intuitiivne.
See paistab sÃṁna otseses mÃṁttes nool.
Ja see on hea asi.
Ja siin sÃṁna otseses mÃṁttes nÃĊeb vÃĊlja nagu nool.
Nii et ma arvan, et see la-- ma ei arvad, et ma Ãỳle-toimepanemise siin-- I
arvan, et on viimane uus teos sÃỳntaksi me nÃĊeme.
Ja Ãṁnneks on see tÃṁepoolest natuke rohkem intuitiivne.
>> NÃỳÃỳd neile, kes vÃṁiks eelistada vana viisi,
saate endiselt kasutada dot mÃĊrke.
Aga nagu iga esmaspÃĊeval vestlus, me esimest korda
vaja sinna minna, minna, et kÃĊsitleda, ja seejÃĊrel juurdepÃĊÃĊsu valdkonnas.
Nii et see on ka Ãṁige.
Ja ausalt Ã¶eldes, see on natuke pedantne.
Sa sÃṁna otseses mÃṁttes Ã¶elda, dereference osuti ja sinna minna.
SeejÃĊrel haarata .n, valdkonnas nimetatakse n.
Aga ausalt, keegi ei taha kirjutada vÃṁi lugeda.
Ja nii maailmas leiutatud noole mÃĊrke, mis
vÃṁrdub identsed, see on lihtsalt sÃỳntaktiline suhkur.
Nii fancy viis Ã¶elda seda nÃĊeb parem vÃĊlja, vÃṁi tundub lihtsam.
>> Nii et nÃỳÃỳd ma lÃĊhen tegema Ãỳks teine ââasi.
Ma Ãỳtlen "murda", kui olen leidis ta, et ma ei pea otsima seda.
Kuid see on asja olemus otsingu funktsiooni.
Aga see on palju lihtsam, et LÃṁpuks ei kÃṁndida lÃĊbi kood.
See on tÃṁepoolest formaalne rakendamine otsingu tÃĊnapÃĊeva jaotus kood.
Julgen Ã¶elda, et insert ei ole eriti tore jalutada lÃĊbi
visuaalselt, ega kustutada, isegi kuigi lÃṁpuks pÃĊeval
need taanduvad Ãỳsna lihtne heuristika.
>> Nii et teeme seda.
Kui sa mu tuju siin, ma tegin tuua hunnik stress pallid.
Ma tÃṁin hunnik numbreid.
Ja kas me saada paar vabatahtlikud esindada 9, 17, 20, 22, 29 ja 34?
Nii et sisuliselt kÃṁik kes on tÃĊna siin.
See oli Ãỳks, kaks, kolm, neli, viis, kuus inimest.
Ja ma olen palutud go-- nÃĊha, ei Ãỳks taga tÃṁstab oma kÃĊed.
OK, Ãỳks, kaks, kolm, neli, five-- andke laadida balance-- kuus.
OK, sa kuus tule Ãỳles.
Meil on vaja teisi inimesi.
TÃṁime extra stress pallid.
Ja kui sa vÃṁiksid vÃṁtta hetk, joon
endid lihtsalt nagu see pilt siin.
>> Olgu.
Vaatame, mis su nimi on?
>> SihtrÃỳhm: Andrew.
>> DAVID J. Humala: Andrew, te arv 9.
Meeldiv kohtuda.
Palun.
SihtrÃỳhm: Jen.
DAVID J. Humala: Jen.
David.
Number 17.
Jah?
>> SihtrÃỳhm: ma olen Julia.
>> DAVID J. Humala: Julia, David.
Number 20.
SihtrÃỳhm: Christian.
DAVID J. Humala: Christian, David.
Number 22.
Ja siis?
>> SihtrÃỳhm: JP.
DAVID J. Humala: JP.
Number 29.
Nii et laske kÃĊia ja saada sisse-- Uh oh.
Uh oh.
OotereÅẅiim.
20.
Kas kellelgi on SM?
SihtrÃỳhm: Mul Sharpie.
DAVID J. Humala: Sul Sharpie?
OK.
Ja kas keegi on tÃỳkk paberit?
SÃĊÃĊsta loeng.
Tule.
SihtrÃỳhm: Meil ââon see.
DAVID J. Humala: Me saime?
Olgu, tÃĊnan.
Siit me tuleme.
Kas see on teie?
Sa lihtsalt salvestada pÃĊev.
Nii 29.
Olgu.
Ma valesti 29, kuid OK.
Lase kÃĊia.
Olgu, ma annan sulle Teie pen tagasi jÃṁudma.
Nii et meil on need inimesed siin.
Teeme veel Ãỳhe.
Gabe, sa tahad mÃĊngida Esimene element siin?
Me vajame sind juhtida neid trahvi folks.
Nii et 9, 17, 20, 22, sort 29. ja seejÃĊrel 34.
Kas me kaotame keegi?
Mul on 34.
Kui tegin-- OK, kes tahab olla 34?
OK, tule Ãỳles, 34.
Olgu, seda saab vÃĊÃĊrt haripunkti.
Mis su nimi on?
>> SihtrÃỳhm: Peter.
>> DAVID J. Humala: Peter, tule Ãỳles.
Olgu, siin on terve hunnik tippe.
Iga kutid esindab Ãỳks neist ristkÃỳliku.
Ja Gabe, veidi veider mees vÃĊlja, moodustab esimene.
Nii tema osuti on veidi vÃĊiksem ekraanile kui kÃṁik teisedki.
Ja sel juhul, iga oma vasakule kÃĊed lÃĊheb kas suunaga allapoole,
mis esindavad null, nii lihtsalt puudumisel osuti
vÃṁi see saab olema suunaga at sÃṁlme kÃṁrval.
>> Nii et kohe kui te kaunistavad endid nagu pildil
siin, edasi minna ja punkt Ãỳksteist, koos Gabe
eriti osutavad number 9 esindama nimekirja.
OK, ja number 34, vasaku kÃĊega tuleks lihtsalt osutades pÃṁrandale.
>> OK, nii et see on seotud nimekirja.
Nii et see on stsenaarium kÃỳsimus.
Ja tÃṁepoolest, see on tÃỳÃỳpiline of klassiks
et sa vÃṁiksid proovida lahendada koodiga.
Tahad lÃṁpuks sisestada uus element nimekirja.
Sel juhul me ei kavatse proovida sisestades number 55.
Aga seal saab olema mÃṁnevÃṁrra erinevat juhtumit.
Ja tÃṁepoolest, see saab olema Ãỳks big-picture takeaways siin on,
Millised on erinevad juhtumid.
Millised on erinevad, kui tingimused vÃṁi oksad, et teie programm vÃṁib olla?
>> Noh, number Ãỳritad insert, mida me teame nÃỳÃỳd, et 55,
aga kui sa ei tea, ette, Julgen vÃĊita,
kuulub vÃĊhemalt kolm vÃṁimalikke olukordi.
Kus vÃṁiks uus element olla?
SihtrÃỳhm: Ja otsas vÃṁi keskel.
DAVID J. Humala: LÃṁpus sisse keskel vÃṁi alguses.
Nii et ma vÃĊita, seal on vÃĊhemalt kolm probleemid peame lahendama.
Olgem valida, mida on vÃṁib-olla vaieldamatult kÃṁige lihtsam
Ãỳks, kus uus element kuulub alguses.
Nii et ma lÃĊhen on kood Ãỳsna nagu otsing, mis ma kirjutasin.
Ja ma lÃĊhen on PTR, mis Ma esindan oma sÃṁrme,
nagu tavaliselt.
>> Ja pidage meeles, millist vÃĊÃĊrtust Kas me initsialiseerida 'p'?
Nii et meil tuleb kÃṁigepealt tÃỳhjaks esialgu.
Aga mida me teeme, kui me olid sees meie otsingu funktsiooni?
Seame see vÃṁrdub esimese, mis ei tÃĊhenda seda teed.
Kui ma panen PTR vÃṁrdub esimene, mida peaks minu poolt tÃṁesti juhtides?
Ãigus.
Nii et kui Gabe ja ma ei kavatse vÃṁrdne vÃĊÃĊrtuste siin
me peame nii punkti number 9.
>> Nii et see oli alguses meie lugu.
Ja nÃỳÃỳd see on lihtsalt arusaadav, kuigi sÃỳntaks on uus.
Kontseptuaalselt on see lihtsalt lineaarset otsingut.
Kas 55 on vÃṁrdne 9?
VÃṁi pigem, Ãỳtleme, et alla 9.
Kuna ma Ãỳritan nuputada, kuhu panna 55.
VÃĊhem kui 9, vÃĊhem kui 17 ja vÃĊhem kui 20, vÃĊhemalt 22, vÃĊhemalt 29,
alla 34, no.
NÃỳÃỳd oleme puhul Ãỳks vÃĊhemalt kolm.
>> Kui ma tahan, et lisada 55 siin, mida rida koodi on vaja saada tÃĊidetud?
Kuidas see pilt Inimestel on vaja vahetada?
Mida ma pean tegema minu vasak kÃĊsi?
See peaks olema null esialgu sest ma olen lÃṁpus nimekirja.
Ja mis peaks juhtuma, siin Peter, see oli?
Ta on ilmselt lÃĊheb punkt mulle.
Nii et ma vÃĊita, seal on vÃĊhemalt kaks rida koodi proovi kood tÃĊna
mis toimub rakendada seda stsenaariumi lisades 55 juures saba.
Ja kas ma saaksin kellegi hop up ja lihtsalt esindavad 55?
Olgu, sa oled uus 55.
>> Mis nÃỳÃỳd, kui jÃĊrgmine stsenaarium tuleb mÃ¶Ã¶da,
ja me tahame, et sisestada juures algab vÃṁi juht nimekirjas?
Ja mis sinu nimi, number 55?
>> SihtrÃỳhm: Jack.
>> DAVID J. Humala: Jack?
OK, meeldiv kohtuda.
Tere tulemast pardale.
NÃỳÃỳd me ei kavatse sisestada, Ãỳtleme, number 5.
Siin on teine ââkui kolm tulime varem.
Nii et kui 5 kuulub alguses, Vaatame, kuidas me seda teada.
Ma initsialiseerida minu PTR kursor number 9 uuesti.
Ja ma sain aru, oh, 5 on alla 9.
Nii et mÃĊÃĊrata see pilt meile.
Kelle kÃĊsi, Gabe vÃṁi Taaveti vÃṁi-- mis number 9 nime?
>> SihtrÃỳhm: Jen.
>> DAVID J. Humala: Jen hands-- mida meie kÃĊed on vaja vahetada?
OK, nii et Gabe punktid, mida nÃỳÃỳd?
Mind.
Olen uus sÃṁlm.
Nii et ma lihtsalt selline kÃĊik siin see visuaalselt.
Ja vahepeal, mida ma rÃṁhutada, et?
Ikka, kui ma juhtides.
Nii ongi.
Nii lihtsalt tÃṁesti Ãỳks rida koodi parandused selles konkreetses kÃỳsimuses, tundub.
Olgu, see on hea.
Ja kas keegi on kohatÃĊide 5?
Tule.
Me saame teile jÃĊrgmine kord.
>> Olgu, nÃỳÃỳd-- ja Nagu kÃṁrvale, nimed
Ma ei tee selgesÃṁnalise Ãṁiguse nÃỳÃỳd Paku pointer, eelkÃĊija pointer
ja uue pointer, mis on ainult eesnimedega
Valimisse koodi viiteid vÃṁi mu kÃĊed, mis on omamoodi suunaga Ãỳmber.
Mis su nimi on?
>> SihtrÃỳhm: Christine.
>> DAVID J. Humala: Christine.
Tere tulemast pardale.
Olgu, lÃĊhme kaaluma nÃỳÃỳd pisut tÃỳÃỳtu stsenaariumi
mille ma tahan lisada midagi 26 sellesse.
20?
Mis?
Need oled-- hea asi on see pen.
Olgu, 20.
Kui keegi vÃṁiks saada veel Ãỳks paber valmis igaks juhul-- eks.
Oh, huvitav.
Noh see on nÃĊide loeng viga.
OK, siis millised on teie nimi oligi?
SihtrÃỳhm: Julia.
DAVID J. Humala: Julia, saate pop vÃĊlja ja teeskle, et sa olid kunagi olemas?
OK, see ei juhtunud.
AitÃĊh.
Seega arvan, et me tahame lisada Julia sellesse seotud nimekirja.
Ta on number 20.
Ja muidugi on ta lÃĊheb kuuluvad juures
begin-- ei viita juures veel midagi.
Nii et teie kÃĊsi vÃṁib selline olla alla null vÃṁi mÃṁned prÃỳgi vÃĊÃĊrtus.
Olgem Ã¶elda kiire lugu.
Ma osutades number 5 seekord.
Siis ma kontrollin 9.
Siis ma saan vaadata 17.
Siis ma saan vaadata 22.
Ja ma saan aru, ooh, Julia peab minema enne 22.
Mis siis peab juhtuma?
Kelle kÃĊes on vaja vahetada?
Julia, minu vÃṁi-- mis su nimi oligi?
>> SihtrÃỳhm: Christian.
>> DAVID J. Humala: Christian vÃṁi?
>> SihtrÃỳhm: Andy.
>> DAVID J. Humala: Andy.
Christian vÃṁi Andy?
Andy peab kÃĊsk juures?
Julia.
Olgu.
Nii Andy, sa tahad osutavad Julia?
Kuid oodake minut.
Loos seni Ma olen omamoodi Ãỳks
eest, mis tÃĊhendab, et osuti on asi, mis on
liigub lÃĊbi nimekirja.
Me vÃṁib-olla nime Andy, aga pole muutuja nimega Andy.
Ainuke muutuja meil on Esimene, kes esindab Gabe.
>> Nii et see on tegelikult miks nii kaugele oleme ei vaja seda.
Kuid nÃỳÃỳd ekraanil on rÃĊÃĊkimata taas progn pointer.
Nii et lubage mul olla selgesÃṁnaline.
Kui see on osuti, mul oli parem natuke arukam
minu iteratsiooni.
Kui sa ei pahanda, et ma lÃĊhen siit lÃĊbi uuesti, tuues siia, juhtides siin.
Aga andke mulle progn pointer, eelkÃĊija pointer, mis on
liiki osutades element olin just.
Nii et kui ma lÃĊhen siit, nÃỳÃỳd mu vasak kÃĊsi uuendused.
Kui ma lÃĊhen siin mu vasak kÃĊsi uuendused.
Ja nÃỳÃỳd ma ei ole mitte ainult viit element, mis lÃĊheb pÃĊrast Julia,
Mul on veel viit Andy, element enne.
Nii et teil on juurdepÃĊÃĊs sisuliselt riivsai, kui soovite,
kÃṁik nÃṁutavad osuti.
>> Nii et kui ma osutades Andy ja ma ka osutades
at Christian, kelle kÃĊed NÃỳÃỳd tuleks mÃĊrkida mujal?
Nii Andy saab nÃỳÃỳd osutavad Julia.
Julia saab nÃỳÃỳd juhtida at Christian.
Sest ta saab kopeerida oma parema kÃĊe pointer.
Ja mis tegelikult paneb sind tagasi see koht siin.
Nii lÃỳhike, kuigi see viib meid omamoodi igavesti
tegelikult uuendada seotud nimekirja, mÃṁistma
et toimingud on suhteliselt lihtne.
See on Ãỳks, kaks, kolm rida koodi lÃṁpuks.
Aga pakitud Ãỳmber nende rida koodi eeldatavasti
on natuke loogikat, et tÃṁhusalt kÃỳsib kÃỳsimuse, et kus me oleme?
Kas me oleme alguses, keskel vÃṁi lÃṁpus?
>> NÃỳÃỳd on kindlasti mÃṁne teise operatsioonide vÃṁiksime rakendada.
Ja need pildid siin lihtsalt kirjeldada mida tegime inimestega.
Aga eemaldamist?
Kui ma tahan nÃĊiteks eemaldage number 34 vÃṁi 55,
Ma vÃṁin olla sama koodi, aga ma lÃĊhen vaja Ãỳks vÃṁi kaks sammu.
Sest see, mis uudist?
Kui ma eemaldan keegi lÃṁpus, nagu number 55 ja siis 34,
Mis on ka muuta, kui ma seda teen?
Pean ei evict-- mis su nimi oligi?
>> SihtrÃỳhm: Jack.
>> DAVID J. Humala: Jack.
Mul on mitte ainult evict-- tasuta Jack, nii sÃṁna otseses mÃṁttes helistada tasuta Jack, vÃṁi vÃĊhemalt
pointer seal liiga, kuid nÃỳÃỳd mida peaks muutma, Peter?
Tema kÃĊsi parem alustada suunaga allapoole.
Sest niipea, kui ma helistada tasuta Jack, kui Peter on ikka osutades Jack
ja seetÃṁttu ma hoida liiklevad nimekirja ja juurdepÃĊÃĊs sellele pointer,
see on kui meie vana sÃṁber segmenteerimine viga vÃṁib tegelikult algama.
Kuna me oleme andnud mÃĊlu tagasi Jack.
>> VÃṁite viibida seal kohmakalt hetkeks.
Kuna meil on ainult paar lÃṁpptoimingute kaaluda.
Pea eemaldamine loetelu, vÃṁi alguse-- ja see on
natuke tÃỳÃỳtu.
Sest meil on teada, et Gabe on selline eriline selles programmis.
Sest tÃṁepoolest, ta on oma pointer.
Ta ei ole lihtsalt on osutanud, nagu peaaegu kÃṁik teisedki siin.
>> Nii et kui juht nimekiri on eemaldatud, kelle kÃĊtes on vaja vahetada nÃỳÃỳd?
Mis su nimi oligi?
>> SihtrÃỳhm: Christine.
>> DAVID J. Humala: Ma olen kohutav at nimesid, ilmselt.
Nii Christine ja Gabe, kelle kÃĊed on vaja muuta
kui me pÃỳÃỳame eemaldada Christine, number 5, pildilt?
OK, teeme siis Gabe.
Gabe lÃĊheb punkt, arvatavasti on number 9.
Aga mis edasi juhtub?
SihtrÃỳhm: Christine peaks olema null [kuuldamatu].
DAVID J. Humala: OK, me peaks ilmselt make-- kuulsin "null" kusagil.
SihtrÃỳhm: Null ja vaba teda.
DAVID J. Humala: NULL mida?
SihtrÃỳhm: Null ja vaba teda.
DAVID J. Humala: Null ja vaba teda.
Nii et see on vÃĊga lihtne.
Ja see on suurepÃĊrane, et sa oled nÃỳÃỳd sorteeri Kasvava sinna ei kuulu.
Sest sa oled olnud lahtiseotud nimekirja.
Olete edukalt toimunud orvuks nimekirjast.
Ja nii oli meil parem helistada tasuta nÃỳÃỳd Christine andma, et mÃĊlu tagasi.
Muidu iga kord, kui me kustutada sÃṁlme nimekirjast
me vÃṁiks muuta nimekiri lÃỳhem, kuid tegelikult vÃĊheneb
suurus mÃĊlu.
Ja kui me hoida lisades ja Lisades, lisades asjad loendisse
minu arvuti vÃṁib saada aeglasem ja aeglasem ja aeglasem,
sest ma otsa mÃĊlu, isegi kui ma ei ole tegelikult
kasutades Christine baiti mÃĊlu enam.
>> Nii lÃṁpuks on teisi stsenaariume, muidugi-- eemaldamine
keskel, eemaldamine aasta lÃṁpus, kui me nÃĊgime.
Aga huvitav NÃỳÃỳd on kÃỳsimus
saab kaaluda tÃĊpselt Mis on kÃĊigu aeg.
Nii et mitte ainult sa saad hoida oma paberitÃỳkke, kui Gabe,
sa ei pahanda, andes kÃṁik stressi pall.
TÃĊnan sind nii palju, et meie seotud nimekirja Vabatahtlike siin, kui sa saaksid.
>> [APPLAUSE]
>> DAVID J. Humala: Olgu.
Nii paar analÃỳÃỳtiline kÃỳsimused siis, kui suutsin.
Me oleme nÃĊinud seda muutma enne, suur O ja omega, Ãỳlemised piirid
ja alumised piirid sÃṁiduaega mÃṁne algoritmi.
Nii et olgem kaaluma ainult paar kÃỳsimust.
>> Ãks, ja me Ãỳtlesime seda enne, mis tÃ¶Ã¶tab
aeg otsida nimekirja nii suur O?
Mis on Ãỳlemine piir on pooleli aega otsides seotud nimekirja
mida rakendatakse meie vabatahtlikele siin?
See on suur O n lineaarne.
Sest halvimal juhul element, nagu 55,
me vÃṁiks otsin vÃṁiks olla, kui Jack oli kÃṁik kuidagi lÃṁpuni.
Ja kahjuks erinevalt array me ei saa fancy seekord.
Kuigi kÃṁik meie inimesed olid sorteeritud vÃĊike elemente, 5,
kÃṁik viis kuni suurem osa, 55, mis on tavaliselt hea.
Aga mida see eeldus enam ei vÃṁimalda meil teha?
SihtrÃỳhm: [kuuldamatu]
DAVID J. Humala: Ãtle uuesti?
SihtrÃỳhm: MuutmÃĊlu.
DAVID J. Humala: MuutmÃĊlu.
Ja omakorda see tÃĊhendab, et me ei ole kasuta enam nÃṁrk nulle, intuitsiooni,
ja ilmselget kasutades binaarne Otsige ja jaga ja valitse.
Sest kuigi me inimestele vÃṁib ilmselt
nÃĊha, et Andy ja Christian olid umbes keskel nimekirja
Me teame ainult, et kui arvuti koorides nimekirja
algusest.
Nii et me oleme loobunud, et muutmÃĊlu.
>> Nii suur O n on praegu Ãỳleval seotud meie search aega.
Aga omega meie search?
Mis alampiiri otsimine mÃṁnda number selles loetelus?
SihtrÃỳhm: [kuuldamatu]
DAVID J. Humala: Ãtle uuesti?
SihtrÃỳhm: One.
DAVID J. Humala: One.
Nii konstantse ajaga.
Parimal juhul, Christine on tÃṁepoolest alguses nimekirja.
Ja me otsime number 5, nii et me ta leidsime.
Nii et ei ole suur asi.
Aga ta ju olema loetelu alguses kÃĊesolevas asjas.
Aga midagi sellist Kustuta?
Mis siis, kui soovid kustutada element?
Milline on Ãỳlemise ja alumise tÃṁkke kustutamise kohta midagi, mis on seotud
List?
SihtrÃỳhm: [kuuldamatu]
DAVID J. Humala: Ãtle uuesti?
SihtrÃỳhm: n.
DAVID J. Humala: n on tÃṁepoolest Ãỳlemise.
Sest halvimal juhul pÃỳÃỳame kustutada Jack, nagu me tegime.
Ta on kogu tee lÃṁpus.
Viib meid igavesti, vÃṁi n samme teda leida.
Nii et see on Ãỳlemine piir.
See on lineaarne, kindlasti.
Ja parimal juhul sÃṁiduaega vÃṁi alumised piirid on parimal juhul
oleks konstantne aeg.
Sest ÃĊkki proovite kustutada Christine ja me lihtsalt veab
ta alguses.
NÃỳÃỳd oota.
Gabe oli ka alguses, ja meil oli ka uuendada Gabe.
Nii et see ei olnud vaid Ãỳks samm.
Nii et see on tÃṁepoolest konstantne aega, parimal juhul
eemaldada vÃĊikseima elemendi?
See on, kuigi see vÃṁib olla kaks, kolm vÃṁi isegi 100 rida koodi,
kas see on sama palju read, mitte mÃṁnes tsÃỳklina
ja sÃṁltumatu suurus nimekirja, absoluutselt.
Kustutamine element alguses nimekirja
isegi kui me peame tegelema Gabe, on ikka konstantne aega.
>> Nii et see tundub suur samm tagasi.
Ja milline ajaraiskamine siis, kui nÃĊdalas Ãỳhe ja nÃĊdalas
null me ei ole mitte ainult pseudokoodi kood kuid tegelikku koodi
rakendada midagi, mis on samamoodi base n, vÃṁi logige pigem n, base 2
poolest sÃṁiduaega.
Nii et miks kuradit oleks tahame alustada kasutades midagi seotud nimekirja?
Jah.
>> SihtrÃỳhm: Nii saate lisada elemendid massiivi.
DAVID J. Humala: nii saate lisada elemente massiivi.
Ja ka see on temaatilised.
Ja me nÃĊeme jÃĊtkuvalt see on see kompromiss, palju
nagu me oleme nÃĊinud kompromissile merge sort.
Me vÃṁiks tÃṁesti kiirendada otsida vÃṁi sortimine, pigem
kui me kulutame veidi rohkem ruumi ning on tÃĊiendav patakas mÃĊlu
vÃṁi massiivi merge sort.
Aga me kulutame rohkem ruumi, kuid me aega sÃĊÃĊsta.
Sel juhul me oleme loobuvad aega, kuid me oleme
saada paindlikkust, dÃỳnaamilisust kui soovite,
mis on vaieldamatult positiivne omadus.
>> JÃĊlgime ka kulutada ruumi.
Mis mÃṁttes on seotud list kallim
nii ruumi kui massiivi?
Kus on lisaruumi tuleb?
Jah?
>> SihtrÃỳhm: [kuuldamatu] pointer.
>> DAVID J. Humala: Jah, me Samuti on osuti.
Nii et see on minorly tÃỳÃỳtu et enam olen
Ma ladustamiseks lihtsalt int esindama int.
Ma hoidmiseks int ja osutiga, mis on samuti 32 bitti.
Nii, et ma sÃṁna otseses mÃṁttes kahekordistunud palju ruumi vahel.
Nii et see on kompromiss, kuid see on juhul, int.
Oletame, et sa ei ole hoidmiseks int, kuid arvan, et kÃṁik need ristkÃỳlikud
vÃṁi iga nende inimeste esindas ÃhesÃṁnaga, ingliskeelne sÃṁna, mis
vÃṁib olla viis mÃĊrki, 10 mÃĊrki, vÃṁib-olla isegi rohkem.
Siis lisades vaid 32 rohkem bitte vÃṁib olla vÃĊhem tÃĊhtis.
>> Mida teha, kui iga ÃỳliÃṁpilastele tutvustamise
olid sÃṁna otseses mÃṁttes Ãṁpilane structs et on nimed ja majad ja vÃṁibolla
telefoninumbreid ja Twitter kÃĊepidemed ja sarnased.
Nii et kÃṁik vÃĊljad hakkasime rÃĊÃĊgime teisel pÃĊeval,
palju vÃĊhem suur asi, kui meie tippe saada rohkem huvitavaid
ja suur veeta, eh, tÃĊiendav osuti lihtsalt Ãỳhendada neid koos.
Aga tÃṁesti, see on kompromiss.
Ja tÃṁepoolest, kood on keerulisem, nagu te peate
vaata koorides kaudu et konkreetne nÃĊide.
Aga mis siis, kui oli mÃṁned PÃỳha Graal siin.
Mis siis, kui me ei vÃṁta samm tahapoole, kuid tohutu samm edasi
ja rakendada info struktuuri, mille kaudu me
vÃṁib leida elemente nagu Jack vÃṁi Christine vÃṁi mis tahes muud osad
Selles massiivi tÃṁsi konstantset aega?
Otsing on konstantne.
Kustuta konstantne.
Sisesta on konstantne.
KÃṁik need toimingud on konstantne.
See oleks meie PÃỳha Graal.
Ja see on koht, kus me kiirenemist jÃĊrgmine kord.
NÃĊeme siis.