[Powered by Google Translate] [Week 6 Vervolg]
[David J. Malan] [Harvard Universiteit]
[Hierdie is CS50.] [CS50.TV]
Dit is CS50, en dit is die einde van week 6.
So CS50x, een van Harvard se eerste kursusse wat betrokke is in die EDX inisiatief
inderdaad debut die afgelope Maandag.
As jy wil graag 'n kykie te kry van wat ander op die Internet
nou die volgende saam met, kan jou kop tot x.cs50.net.
Dit sal u na die toepaslike plek op edx.org,
wat was waar hierdie en ander kursusse van MIT en Berkeley nou leef.
Jy sal het om aan te meld vir 'n rekening, sal jy vind dat die materiaal grotendeels dieselfde
as jy het hierdie semester, hoewel 'n paar weke vertraag, as ons alles gereed te kry.
Maar wat studente in CS50x sal nou sien is 'n koppelvlak hou van hierdie een.
Dit, byvoorbeeld, is Zamyla die leiding van die walk through vir die gestelde probleem 0.
Aan te meld in te edx.org, 'n CS50x student sien die soort van dinge
jy sou verwag om te sien in 'n kursus: die lesing vir die Maandag,
lesing vir Woensdag, verskeie kortbroek, die probleem stelle, die ipv, PDFs.
Verder, as jy hier sien, masjien vertalings
van die Engelse transkripsies in Sjinees, Japannees, Spaans, Italiaans,
en 'n hele klomp van die ander tale wat sal sekerlik onvolmaakte
soos ons rol dit uit programmaties met iets genoem 'n API,
of Application Programming Interface, van Google
wat ons toelaat om Engels aan die ander tale te omskep.
Maar te danke aan die wonderlike gees van 'n paar honderd plus vrywilligers,
random mense op die internet wat het vriendelik aangebied om betrokke te raak
in hierdie projek, sal ons geleidelik die verbetering van die gehalte van daardie vertalings
deur mense korrigeer die foute wat ons rekenaars het.
>> So dit blyk uit ons het 'n paar meer studente toon op Maandag as wat ons aanvanklik verwag.
In werklikheid, nou CS50x het 100.000 mense saam by die huis.
So besef jy is alles deel van hierdie eerste klas van die maak van hierdie kursus in rekenaarwetenskap
onderwys meer in die algemeen, meer in die algemeen, toeganklik.
En die werklikheid is nou, met 'n paar van hierdie massiewe online kursusse,
Hulle begin almal met hierdie baie hoë getalle, maar dit lyk asof ons hier gedoen het.
Maar die doel, uiteindelik, vir CS50x is regtig soveel mense as moontlik na die eindstreep te kry.
Deur ontwerp, is CS50x aangebied gaan word van die afgelope Maandag
al die pad deur April 15, 2013, sodat mense wat skool verpligtinge elders,
werk, familie, ander konflikte en dies meer, het 'n bietjie meer buigsaamheid
wat om te duik in hierdie kursus, wat is dit voldoende om te sê,
is baie ambisieus as net oor die verloop van net drie maande in 'n gewone semester gedoen.
Maar hierdie studente sal aanpak dieselfde probleem stelle, die lees van die dieselfde inhoud,
met toegang tot die dieselfde kortbroek en dies meer.
So besef dat ons almal regtig in hierdie saam.
En een van die einde doelwitte van CS50x is nie net soveel mense te kry
na die eindstreep en gee hulle hierdie nuutgevonde begrip van rekenaarwetenskap
en programmering, maar ook vir hulle het hierdie gedeelde ervaring.
Een van die kenmerkende eienskappe van 50 op die kampus, ons hoop,
is hierdie soort van gemeenskaplike ervaring, soms vir 'n beter of vir slegter,
maar met hierdie mense om te draai na links en na regs,
en kantoorure en die hackathon en die billike.
Dit is 'n bietjie moeiliker om dit te doen in persoon met mense aanlyn,
maar CS50x sal sluit in April met die eerste ooit CS50 Expo,
wat sal 'n aanlyn-aanpassing van ons idee van die billike
waar duisende studente sal almal genooi word om te dien 'n 1 - 2-minute video,
óf 'n screencast van hul finale projek of video van hulle waai hallo
en praat oor hul projek en demoing dit,
baie soos jou voorgangers hier gedoen het op die kampus in die billike,
deur semester se einde, sodat die hoop is 'n internasionale tentoonstelling te hê
van die CS50x studente se finale projekte, baie soos dié wat op jou wag hierdie Desember hier op die kampus.
Sodat meer op wat in die komende maande.
>> Met 100,000 studente, al is, kom 'n behoefte vir 'n paar KA.
Gegewe dat julle die roete brandende hier en neem CS50
n paar weke in die hand van hierdie materiaal se vrylating aan die mense op EDX,
besef ons wil graag soveel as moontlik van ons eie studente te betrek by hierdie inisiatief,
beide gedurende die semester sowel as hierdie winter en die komende lente.
So as jy wil om betrokke te raak in CS50x,
veral by in op CS50x Bespreek, die EDX weergawe van CS50 Bespreek,
wat baie van julle het al met behulp op die kampus, die aanlyn-bord,
doen asseblief kop tot die URL, laat ons weet wie jy is,
want ons wil graag op te bou 'n span van studente en personeel en fakulteit sowel
op die kampus wat net speel saam en help.
En wanneer hulle 'n vraag wat aan hulle bekend is,
jy hoor 'n student 'n bug rapporteer iewers daar buite in 'n land op die Internet,
en dat die ringe 'n klokkie omdat jy ook dat dieselfde probleem gehad het
in jou d-saal geruime tyd gelede, hopelik dan kan jy slaan in en deel jou eie ervaring.
So asseblief deel te neem as jy wil doen.
>> Rekenaarwetenskap-kursusse by Harvard het 'n bietjie van 'n tradisie,
CS50 onder hulle, met 'n paar klere, sommige klere, dat jy met trots kan dra
semester se einde, sê baie trots dat jy klaar CS50
en het CS50 en dies meer, en ons het altyd probeer om studente te betrek
in hierdie proses so veel as moontlik, waardeur ons nooi,
rondom hierdie tyd van die semester, studente ontwerpe in te dien
met behulp van Photoshop, of wat ookal instrument van keuse wat jy wil gebruik
as jy 'n ontwerper, ontwerpe vir T-hemde en sweetpakke te dien
en sambrele en klein bandanas vir honde wat ons nou het en die wil.
En alles is dan - die wenners van elke jaar word dan uitgestal
op die kursus se webblad by store.cs50.net.
Alles is verkoop teen kosprys daar, maar die webwerf net op homself
en mense in staat stel om die kleure en ontwerpe te kies wat hulle wil.
So het ek gedink ons ​​net wil deel sommige van verlede jaar se ontwerpe
wat op die webwerf behalwe hierdie een hier, wat is 'n jaarlikse tradisie.
"Elke dag is ek ma Faultn" was een van die voorleggings verlede jaar,
wat is nog steeds daar beskikbaar vir alumni.
Ons het hierdie een, "CS50, gestig 1989."
Een van ons Bowdens, Rob, was verlede jaar baie gewild.
"Team Bowden" gebore is, was hierdie ontwerp ingedien is, onder die top verkopers.
Soos hierdie een hier. Baie mense het "Bowden Fever" volgens die verkope logs.
Besef dat dit kan nou jou ontwerp op die internet.
Meer besonderhede in die volgende probleem op hierdie stel om te kom.
>> Een meer hulpmiddel: jy het 'n paar blootstelling en hopelik nou
sommige hands-on ervaring met GDB
wat is, natuurlik, 'n debugger en laat jou toe om te manipuleer
jou program op 'n redelik lae vlak, te doen wat soort van dinge?
Wat beteken GDB laat jy dit doen?
Ja? Gee my iets. [Student antwoord, onverstaanbaar]
Goed. Stap in die funksie, sodat jy nie net nie hardloop in te tik
en het die program hou deur middel van sy geheel, uit te druk dinge na standaardafvoer.
Inteendeel, kan jy stap vir stap deur dit in lyn deur die lyn, of tik die volgende
reël om te gaan deur 'n lyn deur die lyn of stap om te duik in 'n funksie, gewoonlik een wat jy geskryf het.
Wat anders het GDB Laat wat jy doen? Ja? [Student antwoord, onverstaanbaar]
Druk veranderlikes. So as jy wil 'n bietjie introspeksie te doen binnekant van jou program
sonder om plek te skryf printf state oor die hele plek,
kan jy net druk van 'n veranderlike of vertoon 'n veranderlike.
Wat anders kan jy doen met 'n debugger soos GDB?
[Student antwoord, onverstaanbaar]
Presies. Jy kan stel inspeksiepunte, jy kan breek uitvoering sê
die belangrikste funksie of die foo-funksie.
Jy kan breek uitvoering sê line 123.
En inspeksiepunte is 'n baie kragtige tegniek
want as jy 'n algemene gevoel van waar jou probleem
waarskynlik is, het jy nie tyd om te mors versterking deur middel van die program se geheel.
Jy kan in wese reg daar spring en begin dan tik -
versterk deur dit met stap of langs of iets dergeliks.
Maar die vangs met iets soos GDB is dat dit help jou, die mens,
vind jou probleme en vind jou foute.
Dit beteken nie noodwendig hulle vind so baie vir jou.
>> So het ons die ander dag style50, wat is 'n kort opdrag lyn instrument
wat probeer om jou kode te 'n bietjie meer skoon as jy stiliseren, die mens, kan gedoen word.
Maar dat dit ook is regtig net 'n estetiese ding.
Maar dit blyk daar is hierdie ander instrument genoem Valgrind wat is 'n bietjie meer arcane om te gebruik.
Sy uitset is afgrijselijk kriptiese met die eerste oogopslag.
Maar dit is wonderlik nuttig wees, veral nou dat ons by die deel van die term
waar jy begin malloc en dinamiese geheuetoekenning te gebruik.
Dinge kan regtig, regtig verkeerd vinnig.
Want as jy vergeet om jou geheue te bevry, of jy dereference n NULL pointer,
of jy dereference sommige vullis wyser, wat is tipies die simptoom wat resultate?
Seg skuld. En jy kry hierdie kern lêer van 'n paar kilogrepe of megagrepe
wat verteenwoordig die toestand van jou program se geheue toe dit neergestort het,
maar jou program uiteindelik seg foute, segmentering skuld,
wat beteken dat iets sleg gebeur byna altyd in verband
na 'n geheue-fout wat jy iewers.
So Valgrind help jy dinge soos hierdie.
Dit is 'n instrument wat jy loop, soos GDB, nadat jy jou program saamgestel is,
maar eerder as loop jou program direk, jy hardloop Valgrind
en jy slaag om dit jou program, net soos jy doen met GDB.
Nou, die gebruik, om die beste soort van afvoer,
is 'n bietjie lank, so reg daar bo van die skerm sal jy sien Valgrind-v.
"V" beteken feitlik universeel verbose wanneer jy die gebruik van programme op 'n Linux-rekenaar.
So dit beteken spoeg uit meer data as wat jy dalk by verstek.
"- Lek-check: = vol." Dit is net sê tjek vir alle moontlike geheue lekkasies,
foute wat ek kon gemaak het. Dit is ook 'n algemene paradigma met Linux programme.
In die algemeen, as jy 'n command line argument wat is 'n "switch",
wat veronderstel is om die program se gedrag te verander, en dit is 'n enkele brief,
dit is-v, maar as dit is aangeskakel, net deur die ontwerp van die programmeerder,
is 'n volledige woord of reeks van woorde, die command line argument begin met.
Dit is net menslike konvensies, maar jy sal sien dat hulle al hoe meer.
En dan, uiteindelik, "a.out" is die arbitrêre naam vir die program in hierdie spesifieke voorbeeld.
En hier is 'n paar verteenwoordigende uitset.
>> Voordat ons kyk na wat dit kan beteken, laat my oor te gaan na 'n uittreksel van die kode hier.
En laat my skuif na hierdie uit die pad, kom gou,
en laat ons neem 'n blik op memory.c, wat is hierdie kort voorbeeld hier.
Dus, in hierdie program, laat my zoom in op die funksies en vrae.
Ons het 'n funksie hoof wat noem 'n funksie, f,
en dan wat beteken f voortgaan om te doen, in effens tegniese Engels?
Wat beteken f voortgaan om te doen?
Hoe gaan ek sal begin met lyn 20, en die ster se plek maak nie saak nie,
maar ek sal net konsekwent wees hier by die laaste lesing.
Wat is die lyn 20 vir ons kan doen? Op die linkerkant. Ons sal breek dit af verder.
Int * x: wat beteken dit doen?
Okay. Dit is 'n wyser te verklaar, en nou laat ons selfs meer tegniese.
Wat beteken dit, baie konkreet, 'n wyser om te verklaar? Iemand anders?
Ja? [Student antwoord, onverstaanbare te ver.
So jy lees aan die regterkant van die gelykaanteken.
Kom ons fokus net op die linkerkant, net op int * x.
Dit beteken "verklaar" 'n wyser nie, maar laat ons nou duik in dieper na daardie omskrywing.
Wat beteken konkreet, tegnies beteken dit? Ja?
[Student antwoord, onverstaanbaar]
Okay. Dit is die voorbereiding van 'n adres in die geheue te red.
Goed. En laat ons neem dit 'n stap verder, dit is 'n veranderlike verklaar, x, wat is 32 bisse.
En ek weet dit is 32 bisse omdat?
Dit is nie, want dit is 'n int, want dit is 'n wyser in hierdie geval.
Toeval dat dit is een en dieselfde met 'n int,
maar die feit dat daar is die ster is daar beteken dit is 'n wyser
en in die toestel, soos met baie rekenaars, maar nie almal nie, wysers is 32 bisse.
Moet jy dalk op 'n meer moderne hardeware soos die nuutste Macs, die nuutste PC's, 64-bits-pointers,
maar in die toestel, hierdie dinge is 32 bisse.
So ons sal standaardiseer op daardie. Meer konkreet, die storie gaan as volg:
Ons "verklaar" 'n wyser, wat beteken dit?
Ons berei 'n geheue adres te stoor.
Wat beteken dit?
Ons skep 'n veranderlike genaamd x 32 stukkies
wat sal binnekort die stoor van die adres van 'n heelgetal.
En dit is waarskynlik oor so akkuraat as wat ons kan kry.
Dit is goed om vorentoe te beweeg om die wêreld te vereenvoudig en net sê verklaar 'n wyser genoem x.
Verklaar 'n wyser nie, maar besef en verstaan ​​wat werklik aangaan
selfs in net daardie paar karakters.
>> Nou, hierdie een is amper 'n bietjie makliker te maak, selfs al is dit 'n langer uitdrukking.
So, wat is om dit te doen, wat nou uitgelig: "malloc (10 * sizeof (int));" Ja?
[Student antwoord, onverstaanbaar]
Goed. En ek sal dit daar. Dit is die toekenning van 'n stuk van die geheue vir tien heelgetalle.
En nou, laat ons duik in effens dieper, dit is die toekenning van 'n stuk van die geheue vir tien heelgetalle.
Wat malloc dan weer terug?
Die adres van daardie stuk, of, meer konkreet, die adres van die eerste byte van daardie stuk.
Hoe is ek dan, die programmeerder, om te weet waar daardie stuk van geheue eindig?
Ek weet dat dit is aangrensend. Malloc, per definisie, sal jy 'n aangrensende stuk van die geheue.
Geen gapings in dit. Jy het toegang tot elke greep in daardie stuk,
terug na Terug na, maar hoe weet ek waar die einde van hierdie stuk van die geheue is?
Wanneer jy gebruik malloc? [Student antwoord, onverstaanbaar] Goed.
Jy doen nie. Jy het om te onthou.
Ek het om te onthou wat ek gebruik om die waarde 10, en ek het nie eens lyk dat hier gedoen.
Maar die onus is geheel en al op my. Strlen, wat ons geword het effens afhanklik van snare,
werk net as gevolg van hierdie Konvensie van \ 0
of hierdie spesiale nul karakter, NUL, aan die einde van 'n string.
Dit hou nie net vir arbitrêre stukke van die geheue.
Dit is aan jou. So line 20, dan 'n stuk van die geheue toeken
wat kan stoor tien heelgetalle, en dit slaan die adres van die eerste byte
van daardie deel van die geheue in die veranderlike genaamd x.
Ergo, wat is 'n wyser. So line 21, ongelukkig, was 'n fout.
Maar eers, wat dit doen? Dit sê winkel op plek 10, 0 geïndekseer,
van die stuk van die geheue genoem x die waarde 0.
>> So let op 'n paar van die dinge wat gaan op.
Selfs al is x is 'n wyser, onthou van 'n paar weke gelede
dat jy kan nog steeds gebruik maak van die skikking-styl vierkante hakienotasie.
Want dit is eintlik kort notasie vir die meer kriptiese-looking pointer rekenkunde.
waar ons iets soos hierdie sou doen: Neem die adres x, beweeg 10 plekke oor,
gaan dan is daar na watter adres gestoor op die plek.
Maar eerlik, dit is net gruwelike te lees en kry gemaklik met.
Sodat die wêreld gebruik gewoonlik die vierkantige hakies net omdat dit is soveel meer mens-vriendelike om te lees.
Maar dit is wat regtig gaan op onder die kap;
x is 'n adres wat nie 'n skikking, per se.
So, dit is die stoor van 0 op plek 10 in x.
Hoekom is dit sleg? Ja?
[Student antwoord, onverstaanbaar] Presies.
Ons het slegs toegeken tien ints, maar ons tel van 0 wanneer programmering in C,
sodat jy het toegang tot 0 1 2 3 4 5 6 7 8 9, maar nie meer as 10.
So óf die program gaan seg skuld of dit is nie.
Maar ons het nie regtig weet nie, dit is 'n soort van 'n deterministiese gedrag.
Dit hang af of kry ons gelukkig is.
As dit blyk dat die bedryfstelsel nie omgee as ek gebruik daardie ekstra byte,
selfs al is dit nie dit wat aan my gegee is, kan my program nie crash.
Dit is rou, dit is buggy, maar jy kan nie sien dat die simptoom,
of jy kan sien dit net een keer in 'n rukkie.
Maar die werklikheid is dat die fout is, in werklikheid, is daar.
En dit is regtig problematies as jy geskryf het 'n program wat jy wil korrek te wees,
dat jy verkoop het die program wat mense gebruik dat elke een keer in 'n rukkie ineenstortings
want, natuurlik, dit is nie goed nie. In werklikheid, as jy 'n Android-selfoon of 'n iPhone
en jy dit aflaai apps hierdie dae, as jy ooit gehad het 'n app net ophou,
almal van 'n skielike dit verdwyn, wat is byna altyd die gevolg van 'n paar geheue probleem,
waardeur die programmeerder verfrommeld en be dereferenced 'n wyser
dat hy of sy moet nie, en die gevolg van IOS of Android is om net die dood van die program heeltemal
eerder as risiko undefined gedrag of 'n soort van veiligheid kompromie.
>> Daar is 'n ander fout in hierdie program behalwe hierdie een.
Wat anders het ek screwed up in hierdie program?
Ek het nie geoefen wat ek gepreek het. Ja?
[Student antwoord, onverstaanbaar] Goed.
Ek het nie die geheue bevry. Sodat die reël van die duim
te wees wanneer jy noem malloc, jy moet bel gratis wanneer jy klaar is die gebruik van daardie geheue.
Nou, wil wanneer ek wil die geheue te bevry?
Waarskynlik, met die veronderstelling dat hierdie eerste reël korrek was, sou ek dit wil hê om hier te doen.
Want ek kon nie, byvoorbeeld, doen dit hier neer. Hoekom?
Net buite die omvang. Dus, selfs al is ons praat oor pointers,
dit is 'n week 2 of 3 kwessie, waar x is slegs in omvang binnekant van die kode tussen krulhakies waar dit verklaar is.
So jy kan beslis nie vry om dit daar. My enigste kans om dit te bevry is rofweg na line 21.
Dit is 'n redelik eenvoudige program, maar dit was redelik maklik, wanneer jy soort van toegedraaide jou gedagtes
rondom wat die program doen, waar die foute was.
En selfs as jy nie sien dit op die eerste, hopelik is dit nou 'n bietjie voor die hand liggend
dat hierdie foute is redelik maklik opgelos en maklik gemaak.
Maar wanneer 'n program is meer as 12 lyne lank, dit is 50 lyne lank, 100 lyne lank,
loop deur jou kode lyn deur die lyn, dink deur dit logies,
is moontlik, maar nie baie pret om te doen, voortdurend op soek na foute,
en dit is ook moeilik om te doen, en dit is die rede waarom 'n instrument soos Valgrind bestaan.
Laat my gaan voort en doen dit: laat my my terminale venster oop,
en laat my net nie hardloop nie geheue, want die geheue blyk te wees boete.
Ek kry gelukkig. Gaan na dat bykomende byte by die einde van die skikking
nie ook problematies blyk te wees.
Maar laat my tog, doen 'n gesonde verstand tjek, wat net beteken om te kontroleer
nie, of dit is eintlik korrek is.
>> So laat doen valgrind-v - lek-check = volle,
en dan die naam van die program in hierdie geval is geheue, nie a.out.
So laat ek gaan voort en doen dit. Druk Enter.
Liewe God. Dit is sy uitset, en dit is wat ek vroeër verwys het.
Maar, as jy leer om te lees deur al die nonsens hier,
Die meeste van hierdie is net diagnostiese opbrengs wat is nie so interessant.
Wat jou oog regtig wil om te kyk vir enige melding van foute of ongeldig.
Woorde wat voorstel dat probleme.
En inderdaad, laat ons sien wat verkeerd gaan hier onder.
Ek het 'n opsomming van 'n soort, "in gebruik by die uitgang:. 40 grepe in 1 blokke"
Ek is nie seker wat 'n blok is nie, maar 40 bytes
eintlik voel soos ek kon uitvind waar dit vandaan kom.
40 grepe. Waarom is 40 grepe in gebruik by die uitgang?
En meer spesifiek, as ons scroll down hier,
die rede waarom ek het beslis 40 bytes verloor? Ja?
[Student antwoord, onverstaanbaar] Perfect. Ja, presies.
Daar was tien heelgetalle, en elkeen van daardie grootte van 4 of 32 bits,
so ek het presies 40 grepe verloor, want soos jy voorgestel het, het ek nie genoem gratis.
Dit is 'n fout, en nou, laat ons kyk 'n bietjie verder en sien langs,
"Ongeldige skryf van grootte 4." Nou wat is dit?
Hierdie adres is uitgedruk watter basis notasie, glo?
Dit is heksadesimaal, en enige tyd wat jy sien 'n aantal wat begin met 0x,
dit beteken heksadesimaal, wat het ons pad terug in, dink ek, pset 0 se afdeling van die vrae,
dit was net 'n warmup oefening te doen, omskakeling desimale hex binêre en so meer.
Heksadesimaal, net deur menslike konvensie, word gewoonlik gebruik om verwysings te verteenwoordig
of, meer in die algemeen, spreek. Dit is net 'n konvensie,
want dit is 'n bietjie makliker om te lees, dit is 'n bietjie meer kompak as iets soos desimale,
en binêre is nutteloos vir die meeste mense te gebruik.
So nou wat beteken dit? Wel, dit lyk asof daar 'n ongeldige skryf
van grootte 4 on line 21 van memory.c.
So laat terug te gaan na reël 21, en inderdaad, hier is dat ongeldige skryf.
So Valgrind is nie van plan om heeltemal te hou my hand en my vertel wat die fix is,
maar dit is die opsporing van dat ek is besig met 'n ongeldige skryf.
Ek raak 4 bytes dat ek nie moet wees nie, en glo dit is omdat,
soos jy sê, doen ek [10] in plaas van [9] maksimaal
of [0] of iets tussen in.
Met Valgrind, besef enige tyd wat jy nou 'n program te skryf
wat gebruik maak van wysers en geheue gebruik, en malloc meer spesifiek,
beslis kry in die gewoonte van die bestuur van hierdie lang
maar baie maklik gekopieer en geplak bevel van Valgrind
om te sien of daar is 'n paar foute in daar.
En dit sal oorweldigend wees elke keer as jy die uitset,
maar net parse deur visueel van die afvoer en sien as jy sien melding van foute
of waarskuwings of ongeldig of verlore.
Enige woorde wat klank soos jy screwed up iewers.
So besef dit is 'n nuwe hulpmiddel in jou toolkit.
>> Nou op Maandag, ons het 'n hele klomp van die mense kom hier
en die idee van 'n geskakelde lys verteenwoordig.
En ons lei die geskakelde lys as 'n oplossing vir die probleem wat?
Ja? [Student antwoord, onverstaanbaar] Goed.
Skikkings geheue kan nie bygevoeg word aan hulle.
As jy toeken 'n verskeidenheid van grootte 10, dit is al wat jy kry.
Jy kan 'n funksie soos realloc bel as jy aanvanklik malloc genoem,
en dit kan probeer om die skikking te groei indien daar is 'n spasie na die einde van
wat niemand anders gebruik, en as daar is nie, dit sal net kry jy 'n groter stuk iewers anders.
Maar dan sal dit kopieer al van daardie bytes in die nuwe skikking.
Dit klink soos 'n baie korrekte oplossing.
Hoekom is dit onaantreklik?
Ek bedoel dit werk, het die mens hierdie probleem opgelos.
Waarom het ons dit nodig het op te los op Maandag met geskakelde lyste? Ja?
[Student antwoord, onverstaanbaar] Dit kan 'n lang tyd neem.
Om die waarheid te sê, enige tyd wat jy vra die die malloc of realloc of calloc, wat nog 'n ander een,
enige tyd wat jy die program, praat met die bedryfstelsel,
jy is geneig om die program te vertraag.
En as jy doen hierdie soort van dinge in die loops, jy werklik verlangsaming dinge af.
Jy gaan dit nie om op te let vir die eenvoudigste van "hello world" tipe programme,
maar in veel groter programme, vra die bedryfstelsel weer en weer vir die geheue
of gee dit weer en weer geneig is om nie na 'n goeie ding wees.
Plus, dit is net soort van intellektueel - dit is 'n volledige vermorsing van tyd.
Waarom meer en meer geheue toeken, risiko kopiëring van alles wat in die nuwe skikking,
as jy 'n alternatief wat kan jy net soveel geheue toeken as wat jy werklik nodig het?
So daar is plus punte en minuses hier.
Een van die plus punte is nou dat ons dinamika.
Maak nie saak waar die stukke van die geheue is wat vry is,
Ek kan net soort van hierdie broodkrummels via pointers
my hele geskakelde lys saam te string.
Maar ek ten minste een prys betaal.
>> Wat moet ek doen om in die verkryging van geskakelde lyste te gee?
Ja? [Student antwoord, onverstaanbaar] Goed.
Jy moet meer geheue. Nou moet ek ruimte vir hierdie pointers,
en in die geval van hierdie super eenvoudige geskakelde lys
wat net probeer om heelgetalle te stoor, wat is 4 grepe, hou ons sê
Wel, 'n wyser is 4 grepe, so nou het ek letterlik verdubbel
die bedrag van die geheue Ek moet net hierdie lys te stoor.
Maar weer, dit is 'n konstante nadeel in rekenaarwetenskap
tussen tyd en ruimte en ontwikkeling, moeite en ander hulpbronne.
Wat is nog 'n nadeel van die gebruik van 'n geskakelde lys? Ja?
[Student antwoord, onverstaanbaar]
Goed. Nie so maklik om toegang te verkry. Ons kan nie langer die hefboom
week 0 beginsels soos verdeel en heers.
En meer spesifiek, binêre soek. Want selfs al het ons mense
kan rofweg sien waar die middel van hierdie lys is,
die rekenaar weet net dat hierdie geskakelde lys begin by die adres genoem 1.
En dit is 0x123 of iets soos dit.
En die enigste manier om die program kan die middelste element
is die hele lys om werklik te soek.
En selfs dan, dit het letterlik die hele lys te soek nie, want
selfs wanneer jy die middelste element bereik deur die wysers,
jy, die program, het geen idee hoe lank die lys is, potensieel,
totdat jy getref die einde van dit, en hoe weet jy programmaties
dat jy aan die einde van 'n geskakelde lys?
Daar is 'n spesiale NULL pointer, dit weer doen, 'n konvensie.
Eerder as om hierdie pointer, het ons beslis nie wil hê om dit te sommige vullis waarde
wys af stadium êrens, maar ons wil dit met die hand af, NULL,
sodat ons hierdie terminus in hierdie data struktuur, sodat ons weet waar dit eindig.
>> Wat gebeur as ons wil om dit te manipuleer?
Ons het die meeste van hierdie visueel, en met die mens,
maar wat as ons wil 'n invoeging te doen?
So die oorspronklike lys was 9, 17, 20, 22, 29, 34.
Wat as ons dan wou malloc ruimte vir nommer 55, 'n node vir dit,
en dan wil ons 55 net soos in die lys te voeg ons het op Maandag?
Hoe doen ons dit? Wel, Anita het opgestaan ​​en sy wese die lys geloop.
Sy begin by die eerste element, dan is die volgende, die volgende, is die volgende, is die volgende, is die volgende.
Uiteindelik getref die linker-hand al die pad af
en besef oh, dit is NULL. So, wat wyser manipulasie gedoen moet word?
Die persoon wat op die ou end, nommer 34, wat nodig is om sy linkerhand opgewek
te wys op 55, 55 hulle linkerarm pointing down te wees van die nuwe NULL terminator nodig. Gedoen het.
Redelik maklik 55 in te voeg in 'n gesorteerde lys.
En hoe kan dit kyk?
>> Laat my voort te gaan en maak 'n paar kode voorbeeld hier.
Ek sal oopmaak gedit, en laat my eers twee lêers oop te maak.
Een daarvan is list1.h, en laat my net herinner dat dit was die stuk van die kode
wat ons gebruik om 'n node te verteenwoordig.
'N node het beide 'n int N en 'n wyser volgende genoem dat net punte aan die volgende ding wat in die lys.
Dit is nou in 'n H-lêer. Hoekom?
Daar is hierdie Konvensie, en ons het nie die voordeel van 'n groot hoeveelheid onsself,
maar die persoon wat printf en ander funksies geskryf
as 'n geskenk aan die wêreld gegee het al van daardie werksaamhede deur die skryf van 'n lêer genaamd stdio.h.
En dan is daar string.h, en dan is daar map.h, en daar is al hierdie h lêers
dat jy dalk gesien het of wat gebruik word gedurende die termyn wat deur ander mense geskryf is.
Tipies in daardie h lêers is slegs dinge soos typedefs
of verklarings van persoonlike tipes of verklarings van konstantes.
Jy sit nie funksies implementering in die header lêers.
Jy het, in plaas daarvan, net hulle prototipes.
Jy dinge wat jy wil om te deel met die wêreld wat hulle nodig het
ten einde hul kode op te stel. So net om te kry in hierdie gewoonte,
het ons besluit om dieselfde ding te doen. Daar is nie veel in list1.h,
maar ons het iets wat dalk van belang is vir mense in die wêreld
wat wil ons geskakelde lys implementering te gebruik.
Nou, in list1.c, sal ek nie deur hierdie hele ding gaan
want dit is 'n bietjie lank, hierdie program, maar laat ons hardloop dit regtig vinnig op die instruksielyn.
Laat my stel Lys1 laat my dan hardloop Lys1, en wat jy sien is
Ons het gesimuleerde 'n eenvoudige klein program hier
wat gaan om my te voeg en te verwyder getalle op 'n lys.
So laat ek gaan voort en tik 3 vir die kieslys opsie 3.
Ek wil die getal te voeg - Kom ons doen die eerste getal, wat 9,
en nou is ek is vertel dat die lys is nou 9.
Laat my gaan voort en doen ander te voeg, sodat ek getref kieslys opsie 3.
Watter getal wil ek voeg? 17.
Enter. En ek sal net een meer.
Laat my voeg die getal 22.
So ons het die begin van die geskakelde lys dat ons 'n oomblik gelede in slide vorm gehad het.
Hoe om hierdie invoeging is eintlik besig om te gebeur?
Inderdaad, 22 is nou aan die einde van die lys.
So het ons vertel die storie op die verhoog op Maandag en recapped nou net
moet eintlik in die kode.
Kom ons neem 'n blik. Laat my scroll down in hierdie lêer.
Ons sal glans oor sommige van die funksies,
maar ons gaan af na, sê, die insetsel funksie.
>> Kom ons kyk hoe gaan oor die invoeging van 'n nuwe node in hierdie geskakelde lys.
Waar is die lys verklaar? Wel, laat ons scroll al die pad tot by die top,
en let op dat my geskakelde lys is in wese verklaar as 'n enkele wyser wat aanvanklik NULL.
So ek is met behulp van 'n globale veranderlike hier, wat in die algemeen het ons gepreek teen
want dit maak jou kode 'n bietjie slordig om in stand te hou,
dit is soort van lui, gewoonlik, maar dit is nie lui en dit is nie verkeerd nie en dit is nie sleg nie
as jou program se enigste doel in die lewe is een geskakelde lys te simuleer.
Dit is presies wat ons doen.
So eerder as Verkondig dit in hoof-en dan om dit te slaag om elke funksie
ons het in hierdie program geskryf, besef ons plaas oh, kom ons maak dit net globale
want die hele doel van hierdie program is slegs een geskakelde lys te demonstreer.
So dit voel goed. Hier is my prototipes, en ons sal nie gaan nie deur al hierdie,
maar ek geskryf 'n delete funksie, 'n soek funksie, 'n insetsel funksie, en 'n traverse funksie.
Maar laat ons nou terug gaan na die insetsel funksie
en sien hoe hierdie een hier werk.
Insert is op die lyn - hier gaan ons.
Voeg. Sodat dit nie enige argumente, want ons gaan om te vra
die gebruiker binnekant van hierdie funksie vir die aantal wat hulle wil hê om in te voeg.
Maar eers, ons voor te berei hulle ruimte te gee.
Dit is 'n soort van die kopieer en plak van die ander voorbeeld.
In daardie geval, is ons die toekenning van 'n int, hierdie tyd het ons is die toekenning van 'n nodus.
Ek het nie regtig onthou hoeveel bytes 'n node is, maar dit is goed.
Sizeof kan figuur dit uit vir my.
En hoekom ek kontroleer NULL in line 120?
Wat kan verkeerd gaan in lyn 119? Ja?
[Student antwoord, onverstaanbaar]
Goed. Kon net die geval dat ek gevra het vir te veel geheue
of iets is verkeerd en die bedryfstelsel nie genoeg bytes my te gee,
so dit aandui soveel deur die terugkeer NULL, en as ek gaan nie vir daardie
en ek het net blindelings voort te gaan na die adres gebruik teruggekeer, kan dit wees NULL.
Dit kan 'n onbekende waarde wees, nie 'n goeie ding nie, tensy I -
eintlik nie 'n onbekende waarde. Dit kan wees NULL, so ek wil nie
om dit te misbruik en waag ontwysing dit.
As dit gebeur, het ek net terug en ons sal voorgee soos ek nie terug te kry enige geheue.
>> Anders, Ek sê vir die gebruiker gee my 'n nommer wil invoegen, ek roep ons ou vriend getint,
en dan was dit die nuwe sintaks ons ingestel op Maandag.
"Newptr-> n beteken die adres wat jy gegee is deur malloc
wat verteenwoordig die eerste byte van 'n nuwe node voorwerp,
en gaan dan na die veld genaamd n.
'N bietjie trivia vraag: Dit is gelykstaande aan wat meer kriptiese lyn van die kode?
Hoe sou Ek anders het dit geskryf? Wil jy 'n steek te neem?
[Student antwoord, onverstaanbaar]
Goed. Deur gebruik te maak van die n, maar dit is nie heeltemal so eenvoudig soos dit.
Wat ek wel eers nodig het om te doen? [Student antwoord, onverstaanbaar]
Goed. Ek moet * newptr.n te doen.
So sê nuwe wyser is natuurlik 'n adres. Hoekom?
Want dit is teruggestuur deur malloc. Die * newptr sê: "daar gaan,"
en dan wanneer jy daar is, dan kan jy gebruik maak van die meer bekende.
maar dit lyk net 'n bietjie lelik, veral as ons mense gaan
pointers teken met pyltjies al die tyd, die wêreld het op die pyltjie om notasie gestandaardiseer,
wat doen presies dieselfde ding.
So gebruik jy net die -> notasie wanneer die ding aan die linkerkant is 'n wyser.
Andersins, indien dit is 'n werklike struct gebruik. N.
En dan is dit: Hoekom moet ek newptr-> Volgende inisialiseer word VRYGEMAAK?
Ons wil nie 'n hangende linkerhand van die einde van die verhoog af.
Ons wil dit wys reguit af, wat beteken dat die einde van hierdie lys
potensieel kan wees op hierdie node, sodat ons beter seker maak dat dit is NULL.
En in die algemeen, die inisialisering van jou veranderlikes of jou data lede en structs
na iets is net goeie praktyk.
Net laat afval bestaan ​​en voortgaan om in die algemeen bestaan, kry jy in die moeilikheid
as jy iets vergeet het om later op te doen.
>> Hier is 'n paar gevalle. Dit, weer, is die insetsel funksie,
en die eerste ding wat ek kyk vir is as die veranderlike genaamd die eerste keer,
dat globale veranderlike is NULL, wat beteken daar is geen geskakelde lys.
Ons het nog nie ingevoeg enige nommers, dus is dit triviaal om die huidige getal te voeg
in die lys, want dit behoort net aan die begin van die lys.
So dit was toe Anita was net staan ​​hier alleen, voorgee
niemand anders was hier op die verhoog totdat ons 'n nodus toegeken,
dan kan sy haar hand opsteek vir die eerste keer,
as almal anders gekom het op die verhoog na haar op Maandag.
Nou hier, dit is 'n bietjie check waar ek het om te sê as die nuwe node se waarde van n
<Die waarde van n in die huidige eerste node,
wat beteken dat daar is 'n geskakelde lys wat begin.
Daar is ten minste een nodus in die lys, maar hierdie nuwe man
behoort voor dit, so ons moet dinge om rond te beweeg.
Met ander woorde, indien die lys begin met net, laat ons sê,
net die getal 17, wat is die werklikheid, kan ons doen dit meer duidelik.
As ons ons storie begin met 'n wyser hier genoem 1,
en dit aanvanklik NULL, en ons voeg die getal 9,
die getal 9 behoort duidelik aan die begin van die lys.
So laat ons net voorgee malloced die adres of die nommer 9 en sit dit hier.
As eerste is 9 by verstek, die eerste scenario wat ons bespreek het beteken net laat se punt hierdie man hier,
laat dit as 'NULL, nou het ons die getal 9.
Die volgende getal wat ons wil voeg, is 17.
17 behoort hier, so ons gaan 'n paar logiese stepping te doen deur middel van hierdie.
So laat in plaas daarvan, voordat ons dit doen, laat ons voorgee dat ons wou die getal 8 in te voeg.
>> So, ek gaan net vir wille van gemak om hier te vestig.
Maar onthou, kan malloc sit dit mees oral.
Maar ter wille van die tekening se, ek sit dit hier.
So asof ek het nou net 'n node vir die getal 8 toegeken, dit is 'n NULL by verstek.
Wat het nou gebeur? 'N Paar van die dinge.
Ons het hierdie fout op die verhoog op Maandag, waar ons by 'n wyser soos hierdie,
dan het dit gedoen, en dan kan ons beweer dat ons wat wees gelaat is almal op die verhoog.
Omdat jy can't - die einde van bedrywighede hier belangrik is,
want nou het ons verloor hierdie node 9 dit is net soort van die swaai in die ruimte.
So dit was nie die regte benadering op Maandag.
Ons moet eers iets anders te doen.
Die toestand van die wêreld lyk soos hierdie. Aanvanklik het 8 toegeken is.
Wat sou 'n beter manier van die invoeging van 8?
In plaas van die opdatering van hierdie pointer, werk net hierdie een hier plaas.
So moet ons 'n reël van die kode wat gaan hierdie NULL karakter om te draai
in 'n werklike pointer wat dui op node 9,
en dan kan ons veilig eers verander om aan hierdie man hier te wys.
Nou het ons 'n lys, 'n geskakelde lys van twee elemente.
En wat dit eintlik lyk soos hier?
As ons kyk na die kode, sien dat Ek het presies dit gedoen.
Ek het gesê newptr, en in hierdie storie, newptr wys op hierdie man.
>> So laat my trek een ding, en ek moet verlaat het om 'n bietjie meer ruimte vir hierdie.
So vergewe die klein tekening.
Hierdie man word genoem newptr.
Dit is die veranderlike wat ons 'n paar lyne verklaar vroeër, in lyn net bo 25.
En dit is wat verwys na 8. So wanneer ek sê newptr-> Volgende, wat beteken dat gaan na die struct
wat daarop deur newptr, so hier is ons, gaan daar.
Toe het die pyl sê die volgende veld te kry, en dan die = gesê het watter waarde daar?
Die waarde wat in die eerste, watter waarde het, was in die eerste?
Vir die eerste keer wys op hierdie node, so dit beteken dat dit nou moet wys op hierdie node.
Met ander woorde, wat lyk al is dit 'n belaglike gemors met my handskrif,
wat is 'n eenvoudige idee van net die beweging van hierdie pyle om
vertaal kode met net hierdie een sak.
Bewaar wat is in die eerste in die volgende veld en dan werk waarmee hulle in eerste werklik is.
Kom ons gaan voort en vinnig vorentoe deur 'n paar van hierdie,
en net kyk na hierdie stert invoeging vir nou.
Veronderstel ek kry tot die punt waar ek vind dat die volgende veld van 'n paar node is NULL.
En op hierdie punt in die verhaal, 'n detail dat ek glossing oor
is dat ek nog 'n wyser het ingestel hier in lyn 142, voorganger wyser.
Wese, op hierdie punt in die verhaal, sodra die lys kry lang,
Ek het soort van dit nodig het om te loop met twee vingers, want as ek te ver gaan,
onthou in 'n enkel-lengte lys, kan jy nie agteruit te gaan.
So hierdie idee van predptr is my linker vinger, en newptr - nie newptr.
Nog 'n wyser wat hier is, is my ander vinger, en ek is net soort van die loop van die lys.
Dit is waarom dit bestaan. Maar laat oorweeg slegs een van die eenvoudiger gevalle hier.
As pointer se volgende veld is NULL, wat is die logiese implikasie?
As jy kameelkoei hierdie lys en jy getref 'n NULL wyser?
Jy is aan die einde van die lys, en so die kode dan aanlas nie hierdie een addisionele element
is 'n soort van die intuïtiewe sal neem dat node waarvan die volgende wyser is NULL,
so dit is tans NULL, en verander dit, al is, aan die adres van die nuwe node.
So trek ons ​​net die pyl in die kode dat ons getrek het op die verhoog deur die verhoging van iemand se linkerhand.
>> En die geval dat ek my hande sal beweeg nou,
net omdat ek dink dit is maklik om verlore te raak wanneer ons dit doen in hierdie soort van die omgewing,
kontrole te voeg by die lys se middel.
Maar net intuïtief, wat moet gebeur as jy wil om uit te vind
waar sommige getal hoort in die middel is wat jy hoef dit nie te loop
met meer as een vinger, meer as een pointer,
uit te vind waar dit behoort deur die nagaan van die element <die huidige een,
> Die huidige een, en as jy vind dat die plek,
dan het jy te doen hierdie soort van die dop spel waar jy beweeg die wysers om baie versigtig.
En dat daardie antwoord, as jy wil om te redeneer deur dit by die huis op jou eie,
kom daarop neer net om hierdie twee lyne van kode, maar die einde van daardie lyne is super belangrik.
Want as jy iemand se hand laat val en iemand anders verhoog is in die verkeerde volgorde,
weer, kan jy uiteindelik die lys orphaning.
Om meer konseptueel te som, die invoeging by die stert is relatief maklik.
Die invoeging by die kop is ook relatief maklik,
maar jy moet 'n addisionele pointer werk hierdie tyd
nommer 5 te druk in die lys hier,
en dan voeg in die middel behels nog meer moeite,
om baie versigtig te voeg die getal 20 in sy regte plek,
wat tussen 17 en 22 is.
Sodat jy nodig het om iets te doen soos die nuwe node 20 punt tot 22,
en dan, wat node se wyser moet word opgedateer laaste?
Dit is 17, om werklik te voeg.
Dit weer doen, sal ek die werklike kode vir daardie spesifieke implementering uitstel.
>> Met die eerste oogopslag, dit is 'n bietjie oorweldigend, maar dit is regtig net 'n oneindige lus
wat herhaling, herhaling, herhaling, herhaling, en breek so gou as wat jy druk op die NULL pointer,
op watter punt jy kan doen om die nodige te voeg.
Dit is dan, is verteenwoordigend geskakelde lys invoeging kode.
Dit was soort van 'n baie, en dit voel soos ons het een probleem opgelos,
maar ons het 'n hele ander een. Om eerlik te wees, het ons al die tyd spandeer
Big O en Ω en hardloop tyd, probeer om probleme op te meer vinnig op te los,
en hier het ons neem 'n groot stap agteruit, dit voel.
En tog, as die doel is om data op te slaan,
dit voel soos die Heilige Graal, as ons sê op Maandag, sou werklik
dinge om onmiddellik slaan.
>> In werklikheid, veronderstel dat ons het ter syde gestel geskakelde lys vir 'n oomblik
en ons plaas lei die idee van 'n tabel.
En laat ons dink net van 'n tabel vir 'n oomblik as 'n skikking.
Hierdie skikking en hierdie geval het hier ongeveer 26 elemente, 0 tot 25,
en veronderstel dat jy nodig het 'n paar stuk van die stoor vir name:
Alice en Bob en Charlie en dies meer.
En wat jy nodig het 'n paar datastruktuur om daardie name te stoor.
Wel, kan jy gebruik om iets soos 'n geskakelde lys
en jy kan die lys invoeging van Alice te wandel voor die aangesig van Bob en Charlie nadat Bob en so meer.
En, in werklikheid, as jy wil-kode soos dit te sien as 'n eenkant,
weet dat in list2.h, ons doen presies dit.
Ons sal nie gaan deur middel van hierdie kode, maar dit is 'n variant van die eerste voorbeeld
wat die leerder bekendstel een ander struct ons voor sogenaamde student gesien het,
en dan wat dit werklik stoor in die geskakelde lys is 'n verwysing na 'n student struktuur
eerder as 'n eenvoudige klein heelgetal, n.
So besef daar is daar kode wat behels werklike snare,
maar as die doel by die hand is nou regtig die doeltreffendheid probleem aan te spreek,
sou dit nie lekker wees as ons 'n voorwerp met die naam Alice,
ons wil hê om haar te sit in die regte plek in 'n datastruktuur,
dit voel soos dit sou wees regtig lekker om net te sit Alice,
wie se naam begin met A, in die eerste plek.
En Bob, wie se naam begin met B, in die tweede plek.
Met 'n skikking, of laat ons begin noem dit 'n tafel, 'n hash tabel op daardie,
ons kan doen presies dit. As ons 'n naam soos Alice,
'n string soos Alice, waar jy A-l-i-c-e?
Ons moet 'n hueristic. Ons benodig 'n funksie om 'n inset te neem soos Alice
en 'n antwoord terug, "Sit Alice by hierdie plek."
En hierdie funksie, hierdie swart kassie, gaan word 'n hash funksie genoem.
>> 'N hash funksie is iets wat 'n inset, soos "Alice",
en keer terug na jou, tipies, die numeriese plek in sommige data struktuur waar Alice behoort.
In hierdie geval, moet ons hash funksie relatief eenvoudig.
Ons hash funksie moet sê, as jy "Alice", watter karakter moet ek omgee?
Die eerste een. So ek kyk op [0], en dan sê ek as [0] karakter is 'n, die aantal terug 0.
As dit is B, terug 1. As dit is C, terugkeer 2, en so meer.
All 0 indeks, en wat jou sal toelaat om my in te voeg Alice en Bob en dan Charlie en so meer
in hierdie datastruktuur. Maar daar is 'n probleem.
Wat as Anita kom weer?
Waar sit ons Anita? Haar naam, ook begin met die letter A,
en dit voel soos ons gemaak het 'n nog groter gemors van hierdie probleem.
Ons het nou onmiddellike invoeging, konstante tyd invoeging, in 'n datastruktuur
eerder as erger geval lineêre,
maar wat kan ons doen met Anita in hierdie geval?
Wat is die twee opsies, regtig? Ja?
[Student antwoord, onverstaanbaar] Okay, sodat ons kan 'n ander dimensie.
Dis goed. Sodat ons kan bou dinge uit in 3D soos ons oor gepraat het mondelings op Maandag.
Ons kon 'n ander toegang hier by te voeg nie, maar veronderstel dat Nee, ek probeer om te hou hierdie eenvoudige.
Die hele doel hier is om onmiddellike konstante-time toegang te hê,
sodat die toevoeging van te veel kompleksiteit.
Wat is ander opsies wanneer ek probeer om Anita te voeg in hierdie data struktuur? Ja?
[Student antwoord, onverstaanbaar] Goed. So kan ons almal af beweeg,
soos Charlie nudges down Bob en Alice, en dan sit ons Anita waar sy regtig wil wees.
>> Natuurlik, nou, daar is 'n newe-effek van hierdie.
Hierdie data struktuur is waarskynlik nuttig nie omdat ons wil hê mense te voeg wanneer
maar omdat ons wil om te kyk of hulle daar later
as ons wil uit te druk al die name in die data struktuur.
Ons gaan om iets te doen met hierdie data uiteindelik.
So nou het ons soort geskroef oor Alice, wat is nie meer waar sy veronderstel is om te wees.
Of is Bob, of is Charlie.
So miskien is dit nie so 'n goeie idee.
Maar in werklikheid is dit is een opsie. Ons almal kan skuif af,
of Heck, Anita laat gekom het vir die spel, hoekom doen ons nie net sit Anita
nie hier nie, nie hier nie, nie hier nie, laat haar net 'n bietjie laer in die lys.
Maar dan is hierdie probleem weer begin oorgaan.
Jy mag dalk in staat wees om Alice te vind onmiddellik, wat gebaseer is op haar eerste naam.
En Bob onmiddellik, en Charlie. Maar dan moet jy kyk vir Anita,
en jy sien, hmm, Alice is in die pad.
Wel, laat ek kyk onder Alice. Bob is nie Anita.
Charlie is nie Anita. O, daar is Anita.
En as jy nog steeds dat die trein van die logika al die pad,
wat is die ergste geval looptyd van die bevinding of die invoeging van Anita in hierdie nuwe data struktuur?
Dit is O (n), reg?
Want in die ergste geval, daar is Alice, Bob, Charlie. . .
al die pad af na iemand met die naam "Y", so daar is net een plek gelaat.
Gelukkig, ons het niemand met die naam "Z", so ons sit Anita by die heel onderste.
>> Ons het regtig nie dat die probleem opgelos nie.
So miskien kan ons hierdie derde dimensie hoef in te voer.
En dit blyk, as ons hierdie derde dimensie,
ons kan dit nie doen nie perfek nie, maar die Heilige Graal is gaan te wees om
konstante-time invoeging en dinamiese invoegings sodat
ons het nie te hard-kode 'n skikking van grootte 26.
Ons kan voeg soveel name as ons wil, maar laat ons 5-minute break hier
en dan doen wat goed.
Alles reg. Ek het die storie redelik kunsmatig daar
deur die keuse van Alice en dan Bob en dan Charlie en dan Anita,
wie se naam is natuurlik gaan om te bots met Alice.
Maar die vraag wat ons op Maandag geëindig het met net hoe waarskynlik is dit
wat jy sou kry hierdie soort van botsings? Met ander woorde,
as ons begin om hierdie tabel struktuur te gebruik, wat eintlik net 'n skikking,
in die geval van 26 plekke,
wat as ons insette plaas eenvormig versprei?
Dit is nie kunsmatig Alice en Bob en Charlie en Dawid en ensovoorts alfabeties,
dit is eenvormig versprei oor A tot Z.
>> Miskien sal ons net gelukkig en gaan ons nie twee A's of twee B's te hê
met 'n baie hoë waarskynlikheid, maar as iemand daarop gewys,
as ons algemene hierdie probleem en nie doen 0 25
maar, sê, 0 tot 364 of 65, wat dikwels die aantal dae in 'n tipiese jaar,
en vra die vraag, "Wat is die waarskynlikheid dat twee van ons in hierdie kamer het dieselfde verjaarsdag?"
Sit dit 'n ander manier, wat is die waarskynlikheid dat twee van ons het 'n naam wat begin met A?
Die soort van die vraag is dieselfde, maar hierdie adres ruimte,
dit soek ruimte, is groter in die geval van verjaarsdae,
want ons het so baie meer dae in die jaar as letters in die alfabet.
Wat is die waarskynlikheid van 'n botsing?
Wel, ons kan dink van hierdie uitzoeken die wiskunde in die teenoorgestelde rigting.
Wat is die waarskynlikheid van geen botsings?
Wel, hierdie uitdrukking hier sê wat is die waarskynlikheid
indien daar is net een persoon in hierdie kamer, dat hulle 'n unieke verjaarsdag?
Dit is 100%. Want as daar is slegs een persoon in die kamer,
sy of haar verjaardag kan enige van die 365 dae uit die jaar.
So 365/365 opsies gee my 'n waarde van 1.
So die waarskynlikheid in die vraag op die oomblik is net 1.
Maar as daar 'n tweede persoon in die kamer,
wat is die waarskynlikheid dat hulle verjaarsdag is anders?
Daar is slegs 364 moontlike dae, ignoreer skrikkeljare,
vir hul verjaarsdag nie te bots met die ander persone.
So 364/365. As 1/3 persoon kom, is dit 363/365, en so meer.
Sodat ons hou hierdie breuke vermenigvuldig saam, wat kleiner en kleiner,
om uit te vind wat is die waarskynlikheid dat almal van ons het 'n unieke verjaarsdae?
Maar dan kan ons natuurlik, net die antwoord en draai dit rond
en doen 1 minus alle van daardie, 'n uitdrukking wat ons sal uiteindelik
as jy dink aan die agterkant van jou wiskunde boeke, dit lyk 'n bietjie iets soos hierdie,
wat baie meer maklik geïnterpreteer grafies voor.
En hierdie grafiese hier op die x-as die getal van verjaarsdae,
of die aantal mense met verjaarsdae, en op die y-as is die waarskynlikheid van 'n wedstryd.
En wat dit sê, is dat as jy het, laat ons sê, selfs,
Kom ons kies iets soos 22, 23.
As daar 22 of 23 mense in die kamer,
die waarskynlikheid dat twee van dié wat baie min mense gaan dieselfde verjaarsdag te hê
is eintlik super-hoë, combinatorially.
50% kans dat in 'n klas van net 22 mense, 'n seminaar, prakties,
2 van die mense gaan dieselfde verjaarsdag te hê.
Want daar is so baie maniere waarop jy kan dieselfde verjaarsdag.
Nog erger, as jy kyk na die regterkant van die grafiek,
teen die tyd dat jy 'n klas met 58 studente in,
die waarskynlikheid van 2 mense met 'n verjaarsdag is super, super hoog, byna 100%.
Nou, dit is soort van 'n prettige feit oor die werklike lewe.
>> Maar die implikasies, nou, vir datastrukture en stoor van inligting
beteken dat net as jy het 'n mooi, skoon, eenvormige verspreiding van die data
en jy het 'n groot genoeg verskeidenheid om 'n klomp van die dinge aan te pas
beteken nie jy gaan om mense te kry in 'n unieke plekke.
Jy gaan om botsings te hê. So hierdie idee van hashing, soos dit genoem word,
die neem van 'n inset soos "Alice" en masseer dit in die een of ander manier
en dan kry 'n antwoord soos 0 of 1 of 2 terug.
Om terug n uitset van daardie funksie is geteister deur die waarskynlikheid van 'n botsing.
So hoe kan ons daardie botsings hanteer?
Wel, op die een geval, kan ons die idee dat is voorgestel.
Ons kan net skuif almal af, of miskien 'n bietjie meer eenvoudig,
eerder as skuif almal, laat ons net beweeg Anita aan die onderkant van die beskikbare plek.
So as Alice in 0, Bob is in 1, Charlie is in 2,
ons sal net sit Anita op plek 3.
En dit is 'n tegniek in die data strukture genoem lineêre indringende.
Lineêre omdat jy net loop hierdie lyn, en jy is soort van ondersoekende
vir beskikbare plekke in die data struktuur.
Natuurlik, dit oorgaan in O (n).
As die data struktuur is regtig vol, daar is reeds 25 mense in dit,
en dan Anita saam kom, het sy eindig op watter plek Z sou wees, en dit is goed.
Sy pas nog steeds, en ons kan haar kry later.
>> Maar dit was in stryd met die doel van die bespoediging dinge.
So wat as ons plaas het hierdie derde dimensie?
Hierdie tegniek is algemeen aparte aaneenskakeling genoem, of met kettings.
En wat 'n hash tafel is nou hierdie tabel struktuur,
jou tafel is net 'n verskeidenheid van wysers.
Maar wat die wysers wys raai wat?
'N geskakelde lys. So wat as ons die beste van beide van hierdie wêrelde?
Ons maak gebruik van skikkings vir die aanvanklike indekse
in die data struktuur sodat ons kan direk gaan na die [0] [1], [30] of ensovoorts,
maar sodat ons 'n mate van buigsaamheid en ons kan inpas Anita en Alice en Adam
en enige ander 'n naam,
ons plaas laat die ander as arbitrêr groei.
En ons uiteindelik, soos op Maandag, dat die ekspressiewe vermoë met geskakelde lys.
Ons kan 'n datastruktuur arbitrêr groei.
Alternatiewelik, kan ons maak net 'n groot 2-dimensionele skikking,
maar dit gaan 'n vreeslike situasie wees as een van die rye in 'n 2-dimensionele skikking
is nie groot genoeg vir die addisionele persoon wie se naam gebeur om te begin met A.
God verbied ons het 'n groot 2-dimensionele struktuur te wysig
net omdat daar so baie mense die naam van 'n,
veral wanneer daar is so min mense met die naam Z iets.
Dit is net gaan om 'n baie yl data struktuur.
So dit is nie volmaak nie op enige manier nie, maar nou het ons ten minste die vermoë om
direk te vind waar Alice of Anita behoort,
ten minste in terme van die vertikale as,
en dan het ons net om te besluit waar om te sit Anita of Alice in hierdie geskakelde lys.
As ons nie omgee sorteer dinge, kan hoe vinnig ons voeg Alice in 'n struktuur soos hierdie?
Dit is konstante tyd. Ons indeks in [0], en as niemand daar,
Alice gaan aan die begin van die geskakelde lys.
Maar dit is nie 'n groot deal. Want as Anita kom dan saam
n aantal stappe later, waar Anita behoort?
Wel, [0]. Oop. Alice is reeds in daardie geskakelde lys.
>> Maar as ons nie omgee oor die sortering van hierdie name,
ons kan net beweeg Alice oor insert Anita, maar selfs dit is 'n konstante tyd.
Selfs al is daar Alice en Adam en al die ander 'n name,
dit is regtig nie verskuif hulle fisies. Hoekom?
Omdat ons net het hier met geskakelde lys, wie weet, is hierdie nodes is in elk geval?
Al wat jy hoef te doen is skuif die broodkrummels.
Skuif die pyle rond, jy hoef nie enige data om fisies te beweeg rond.
Sodat ons kan voeg Anita, in daardie geval, onmiddellik. Konstante.
So het ons 'n konstante-time lookup, en konstante-time invoeging van iemand soos Anita.
Maar soort van oorvereenvoudig die wêreld.
Wat gebeur as ons later wil Alice te vind?
Hoeveel treë is dat gaan te neem?
[Student antwoord, onverstaanbaar]
Presies. Die aantal mense wat voor Alice in die geskakelde lys.
So dit is nie heeltemal volmaak nie, want ons data struktuur, weer, het hierdie vertikale toegang
en dan is dit hierdie geskakelde lyste hang - eintlik, laat ons nie trek dit 'n 'n skikking.
Dit is hierdie geskakelde lyste hang af van dit wat lyk 'n bietjie iets soos hierdie.
Maar die probleem is as Alice en Adam en al die ander 'n name
beland daar meer en meer,
vind iemand kan eindig met 'n klomp van die stappe,
bcause jy die geskakelde lys te verken,
wat is 'n lineêre werking.
So regtig, dan, die invoeging van die tyd is uiteindelik O (n), waar n die aantal elemente in die lys.
Gedeel deur, laat arbitrêr noem dit m, waar m die getal van geskakelde lyste
dat ons 'n in hierdie vertikale as.
Met ander woorde, as ons werklik aanvaar 'n eenvormige verspreiding van name,
heeltemal onrealisties. Daar is natuurlik meer van 'n paar letters as ander.
>> Maar as ons aanvaar vir die oomblik dat 'n eenvormige verspreiding,
en ons het 'n totaal mense, en m totale kettings
tot ons beskikking, dan is die lengte van elk van hierdie kettings
redelik eenvoudig gaan die totaal, n, gedeel deur die aantal kettings.
So N / m. Maar hier is waar ons almal wiskundig slim kan wees.
m is 'n konstante, want daar is 'n vaste aantal van hierdie.
Jy gaan jou skikking te verklaar aan die begin,
en ons is nie resizing die vertikale as. Per definisie, bly dat vasgestel.
Dit is net die horisontale as, om so te praat, wat verander.
So tegnies, dit is 'n konstante. So nou, die invoeging van die tyd
is pretty much O (n).
Sodat nie alles wat veel beter voel.
Maar wat is die waarheid? Wel, al hierdie tyd, vir weke,
ons het gesê O (n ²). O (n), 2 x n ², - n, gedeel deur 2. . . ech.
Dit is net n ². Maar nou, in hierdie deel van die semester,
kan ons begin praat oor die werklike wêreld weer.
En n / m is absoluut vinniger as net N alleen.
As jy 'n duisend name, en jy breek hulle in verskeie emmers
sodat jy net tien name in elk van hierdie kettings,
absoluut soek tien dinge gaan wees vinniger as 'n duisend dinge.
En so het een van die komende probleem stelle gaan jou uit te daag
na te dink oor presies wat, selfs al is, ja,
asimptoties en wiskundig, dit is nog steeds net lineêre,
wat suig in die algemeen wanneer ek probeer om dinge te vind.
In werklikheid, dit gaan vinniger wees as dit
as gevolg van die deler.
En so is daar weer aan die gang om hierdie trade-off
en hierdie konflik tussen teorie en werklikheid,
en een van die knoppies sal begin draai op hierdie punt in die semester
meer van die werklikheid een is soos ons soort van voor te berei vir die einde van semester,
stel ons die wêreld van die web programmering,
waar is regtig, prestasie gaan om te tel, want jou gebruikers gaan
begin om te voel en waardeer swak ontwerp besluite.
>> So, hoe gaan jy oor die implementering van 'n gekoppelde - 'n hash tafel met 31 elemente?
En die vorige voorbeeld was arbitrêr oor verjaarsdae.
As iemand het 'n verjaardag van 1 Januarie of Februarie 1, sit ons hulle in die emmer.
As dit is 2 Januarie, Februarie 2, Maart 2, sit ons hulle in die emmer.
Dit is waarom dit was 31. Hoe verklaar jy 'n hash tafel?
Dit kan redelik eenvoudige, node * tabel is my arbitrêre naam vir dit, [31].
Dit gee my 31 pointers nodes,
en wat toelaat dat my 31 pointers te geskakelde lyste te hê
selfs as die kettings is aanvanklik NULL.
Wat ek wil sit as ek wil om te stoor "Alice", "Bob", "Charlie"?
Wel, ons nodig het om daardie dinge te draai in 'n struktuur
want ons moet Alice te wys Bob, om te wys op Charlie, en so meer.
Ons kan net nie die name nie alleen nie, so ek kan 'n nuwe struktuur genoem node hier.
>> Wat is 'n werklike node? Wat is 'n node in hierdie nuwe geskakelde lys?
Die eerste ding wat genoem woord, is vir die persoon se naam.
Lengte, vermoedelik, hou verband met die maksimum lengte van 'n mens se naam,
wat dit ook al is, 20, 30, 40 karakters in 'n gek hoek gevalle,
en 1 is vir wat? Dit is net die ekstra NULL karakter, \ 0.
Hierdie node wikkel "iets" binnekant van homself,
maar dit verklaar ook 'n wyser genoem volgende
sodat ons kan ketting Alice Bob Charlie en so meer.
Kan NULL, maar nie noodwendig hoef te wees.
Enige vrae oor hierdie hash tabelle? Ja?
[Student vra vraag, onverstaanbaar] 'n skikking - goeie vraag.
Hoekom is hierdie char woord in 'n skikking eerder as net char *?
In hierdie ietwat arbitrêre voorbeeld, het ek nie wil hê om plek
malloc vir elk van die oorspronklike name.
Ek wou 'n maksimum bedrag van die geheue vir die string te verklaar
sodat ek kon kopieer in die struktuur Alice \ 0 en nie hoef te hanteer malloc en vry en dies meer.
Maar ek kon doen dat as ek wou meer bewus wees van die ruimte gebruik. Goeie vraag.
So laat ons probeer om te veralgemeen weg van hierdie
en fokus op die res van vandag meer in die algemeen oor datastrukture
en ander probleme wat ons kan oplos deur gebruik te maak van die dieselfde grondbeginsels
selfs al is die data strukture self kan verskil in hul besonderhede.
>> So dit blyk in rekenaarwetenskap, bome is baie algemeen.
En jy kan dink van 'n boom soort van soos 'n stamboom,
waar daar is 'n paar wortels, sommige matriarg of patriarg,
ouma of oupa of vroeër terug,
onder wat ma en pa of verskeie broers en susters, of die wil.
So 'n boom struktuur nodes en dit het kinders,
gewoonlik 0 of meer kinders vir elke node.
En sommige van die jargon wat jy sien in hierdie foto hier
enige van die klein kinders of kleinkinders op die kante
wat geen pyle wat voortspruit uit hulle het,
dit is die sogenaamde blare, en iemand aan die binnekant
is 'n innerlike node, jy kan noem dit iets langs die lyne.
Maar hierdie struktuur is redelik algemeen. Hierdie een is 'n bietjie arbitrêre.
Ons het 'n kind aan die linkerkant, ons het drie kinders aan die regterkant,
twee kinders op die bodem verlaat.
Sodat ons kan verskillende grootte bome, maar as ons begin om dinge te standaardiseer,
en jy kan onthou van Patrick se video op 'n binêre soek uit 'n vorige kort
online, binêre soek, is nie geïmplementeer word met 'n verskeidenheid
of stukkies papier op 'n swartbord.
Veronderstel dat jy wou jou nommers op te slaan in 'n meer gesofistikeerde data-struktuur.
Jy kan skep 'n boom soos hierdie.
Jy kan 'n node verklaar in C, en dat die knoop kan ten minste twee elemente binnekant van dit.
Een daarvan is die nommer wat jy wil op te slaan, en die ander is - goed, ons moet een meer.
Die ander is sy kinders.
So hier is 'n ander datastruktuur. Hierdie tyd, is 'n node gedefinieer as die stoor van 'n getal 'n
en dan twee wysers, links kind en regs kind.
En hulle is nie arbitrêr. Wat is interessant is oor hierdie boom?
>> Wat is die patroon in hoe het ons gelê dit uit of hoe Patrick het dit in sy video?
Dit is soort van voor die hand liggend dat daar is 'n paar te sorteer wat hier aan die gang is,
maar wat is die eenvoudige reël? Ja?
[Student antwoord, onverstaanbaar]
Perfect. As jy blik op hierdie, sien jy die klein getalle aan die linkerkant,
groot getalle aan die linkerkant, maar dit is waar vir elke node.
Vir elke node, sy linker kind minder as dit, en sy reg kind groter as wat dit is.
Wat beteken dit nou is as ek wil hierdie data struktuur te soek vir, sê, die getal 44,
Ek het om te begin by die wortel, want met al hierdie meer komplekse datastrukture nou,
ons het net 'n wyser na een ding, die begin.
En in hierdie geval, die begin is die wortel. Dit is nie die linker kant,
dit is die wortel van hierdie struktuur. So ek sien hier is 55, en ek is op soek na 44.
Watter rigting wil ek om te gaan?
Wel, ek wil om te gaan na die linkerkant, want natuurlik, aan die regterkant te groot gaan wees.
So hier sien, jy is soort van konseptueel kap die boom in die helfte
omdat jy nooit gaan aan die regterkant.
So nou gaan ek van die 55 aan die 33. Dit is te klein van 'n getal.
Ek is op soek na 44, maar nou weet ek as daar 44 is in hierdie boom, ek kan natuurlik gaan aan die regterkant.
Dit weer doen, ek snoei die boom in die helfte.
Dit is pretty much identies konseptueel aan die telefoon boek.
Dit is identies aan wat ons gedoen het met die vraestelle op die bord,
maar dit is 'n meer gesofistikeerde struktuur wat ons in staat stel om werklik te doen
dit verdeel en oorwin deur die ontwerp van die algoritme,
en in die feit, kameelkoei 'n struktuur soos hierdie - Oeps.
Dwars deur 'n struktuur soos hierdie, waar dit net "gaan op hierdie manier of in daardie rigting gaan,"
beteken al daardie kode wat buig jou gedagtes op die eerste wanneer die uitvoering daarvan in artikel
of loop deur dit by die huis, vir 'n binêre soek, met behulp van rekursie of te wel iterasie,
dit is 'n pyn in die nek. Vind die middelste element, doen dan jou afronding styg of daal.
>> Daar is 'n skoonheid, want ons kan nou rekursie gebruik weer,
maar veel meer netjies. Trouens, as jy by die getal 55 en jy wil te vind 44,
gaan jy links in hierdie geval, dan wat doen jy? Jy loop die presiese dieselfde algoritme.
Jy die waarde van die node, dan gaan jy links of regs.
Toe jy die waarde van die node, gaan links of regs.
Dit is uitstekend geskik vir rekursie.
So selfs al is ons in die verlede gedoen het 'n paar redelik arbitrêre voorbeelde waarby rekursie
wat nie nodig het om te wees rekursiewe, met data Strukture,
veral bome, dit is 'n perfekte toepassing van hierdie idee van die neem van 'n probleem op te los,
krimp dit, en dan die oplossing van die dieselfde soort van, maar kleiner, program.
>> So daar is 'n ander datastruktuur wat ons kan stel.
Hierdie een is ontwerp met die eerste oogopslag te kyk kriptiese, maar hierdie een is ongelooflik.
So, dit is 'n datastruktuur Trie, Trie, wat geërf word van die woord herwinning genoem,
wat nie uitgespreek re-drie-val, maar dit is wat die wêreld noem hierdie dinge. Probeer. T-r-i-e.
Dit is 'n boom struktuur van 'n soort, maar elk van die nodusse in 'n Trie
blyk te wees, wat? En dit is 'n bietjie misleidend, want dit is soort van afgekort.
Maar dit lyk asof elke node in hierdie Trie is eintlik 'n skikking.
En selfs al is die outeur van hierdie diagram het nie getoon dat dit,
in hierdie geval, hierdie Trie is 'n datastruktuur wie se doel in die lewe is om woorde op te slaan
soos A-l-i-c-e of B-o-b.
En die wyse waarop hierdie data winkels Alice en Bob en Charlie en Anita en so meer
dit maak gebruik van 'n skikking waarvolgens Alice op te slaan in 'n Trie,
ons begin by die wortel node wat lyk soos 'n skikking,
en dit is geskryf in snelskrif notasie.
Die skrywer weggelaat ABCDEFG, want daar was geen name met wat.
Hulle het nie net gewys M en P en T, maar in hierdie geval,
laat se weg van Alice en Bob en Charlie skuif na 'n paar name wat is hier.
Maxwell is eintlik in hierdie diagram.
So hoe het die skrywer winkel M-a-x-w-e-l-l?
Hy of sy begin by die wortel node, en gaan na [M], so ongeveer 13, die 13de plek in die skikking.
Dan van daar af, daar is 'n wyser.
'N wyser wat lei tot 'n skikking.
Van daar die skrywer geïndekseer in daardie skikking op plek A, soos uitgebeeld daar links bo,
en dan sal hy of sy gevolg dat die wyser na 'n ander skikking,
en gaan na die muis wyser op die plek X.
Dan in die volgende array plek W, E, L, L, en so meer,
en ten slotte, laat ons eintlik probeer om 'n foto te maak aan hierdie.
Wat doen 'n node lyk in die kode?
'N nodus in 'n Trie bevat 'n verskeidenheid van verwysings na meer nodes.
Maar daar is ook het 'n soort van Boolese waarde wees, ten minste in die implementering van hierdie.
Ek gebeur om dit te noem is_word. Hoekom?
Want as jy Maxwell is die invoeging van, is jy nie die invoeging van
enigiets in hierdie datastruktuur.
Jy skryf nie M. Jy is nie die skryf van X.
Al wat jy doen, is na aanleiding van wysers.
Die wyser wat verteenwoordig M, dan die wyser wat 'n
dan die wyser wat verteenwoordig X, dan W, E, L, L,
maar wat jy hoef te doen aan die einde is 'n soort van gaan, kyk, Ek hierdie plek bereik.
Daar was 'n woord wat eindig hier in die data struktuur.
>> So, wat 'n Trie werklik gevul met en die skrywer verkies te verteenwoordig
hierdie bushaltes met min driehoeke.
Dit beteken net dat die feit dat hierdie driehoek hier is, Boole-waarde van die ware
beteken dat as jy gaan terug in die boom,
wat beteken dat 'n woord met die naam Maxwell is in hierdie.
Maar die woord foo, byvoorbeeld,
is nie in die boom, want as ek begin by die wortel node hier by die top,
Daar is geen f pointer, o pointer, o wyser. Foo is nie 'n naam in hierdie woordeboek.
Maar in teenstelling, Turing, t-u-r-i-n-g. Weereens, ek het nie stoor t of jy of r of i of n of g.
Maar ek het winkel in die data struktuur 'n waarde van die ware pad af hier in hierdie node in die boom
deur die oprigting van hierdie boolean waarde van is_word na ware.
So 'n Trie is 'n soort van hierdie baie interessante meta-struktuur,
waar jy regtig nie die stoor van die woorde self vir hierdie soort van 'n woordeboek.
Om duidelik te wees, het jy net die stoor ja of nee, daar is 'n woord wat eindig hier.
>> Nou wat is die implikasie?
As jy 'n 150,000 woorde in 'n woordeboek wat jy probeer om op te slaan in die geheue
die gebruik van iets soos 'n geskakelde lys,
jy gaan 150.000 nodes in jou geskakelde lys te hê.
En die vind van een van daardie woorde alfabeties O (n) tyd kan neem.
Lineêre tyd. Maar in die geval hier van 'n Trie,
wat is die looptyd van die vind van 'n woord?
Dit blyk uit die skoonheid hier is dat selfs as jy 149.999 woorde reeds in hierdie woordeboek,
soos met die data struktuur geïmplementeer,
hoeveel tyd dit neem om uit te vind of voeg een persoon in daardie, soos Alice, Alice?
Wel, dit is slegs 5, dalk 6 stappe vir die afsluitende karakter.
Omdat die teenwoordigheid van die ander name in die struktuur
nie in die weg van die invoeging van Alice.
Verder, die vind van Alice wanneer daar is 150,000 woorde in hierdie woordeboek
nie kry in jou manier van die vind van Alice at all,
omdat Alice is. . . . . hier, want ek het gevind dat 'n Boolese waarde.
En as daar is geen boolean true, dan Alice is nie in hierdie data struktuur van woorde.
Met ander woorde, die looptyd van die vind van dinge en die invoeging van dinge in hierdie nuwe
data struktuur van Trie O - dit is nie Ñ.
Omdat die teenwoordigheid van 150.000 mense het geen effek op Alice, dit lyk.
So kom ons noem dit k, waar k is die maksimum lengte van 'n woord in Engels
wat is gewoonlik nie meer as 20-iets karakters.
So k 'n konstante. Dus is die Heilige Graal lyk ons ​​nou
is dié van 'n Trie, konstante tyd vir inserts vir soektogte vir skrappings.
Omdat die aantal van die dinge wat reeds in die struktuur,
wat nie eens fisies daar. Weereens, hulle sorteer net nagegaan af, ja of nee,
het geen impak op sy toekomstige looptyd.
>> Maar daar het 'n vangplek wees, anders sou ons nie vermors word nie so baie tyd
op al hierdie ander datastrukture net om uiteindelik na die geheime wat is ongelooflik.
So watter prys ons betaal om hierdie grootheid hier bereik? Ruimte.
Hierdie ding is groot. En die rede dat die skrywer
het dit nie hier sien dat al hierdie dinge wat lyk soos skikkings,
hy het nie die res van die boom, die res van die Trie,
want hulle is nie net relevant is vir die storie.
Maar al van hierdie nodes is super breed, en elke nodus in die boom neem
26 of eintlik, 27 karakters kan wees, want in hierdie geval het ek met inbegrip van ruimte vir die afkappingsteken
sodat ons kan apostrophized woorde.
In hierdie geval, dit is wye skikkings. So selfs al het hulle is nie picutured,
dit neem 'n massiewe bedrag van RAM.
Wat dalk goed wees, especilly in die moderne hardeware,
maar dit is die nadeel. Ons kry minder tyd deur die besteding van meer ruimte.
So waar dit alles gaan?
Wel, laat ons doen - laat ons hier te sien.
Kom ons doen 'n sprong na hierdie man hier.
>> Glo dit of nie, soveel pret soos C is vir 'n geruime tyd nou,
ons bereik die punt in die semester waar dit is tyd om te oorgang na dinge meer moderne.
Dinge wat op 'n hoër vlak. En selfs al vir die volgende paar weke
ons sal steeds voortgaan om onsself te verdiep in die wêreld van wysers en geheue-bestuur
dat die vertroosting waarmee ons kan bou op te kry,
die einde spel is uiteindelik bekend te stel, ironies genoeg, nie hierdie taal nie.
Ons sal spandeer, soos 10 minute van praat oor HTML.
Alle HTML word, is 'n opmaak taal, en wat 'n opmaak taal is
is hierdie reeks van oop hakies en geslote hakies wat sê: "maak dit vet"
"Maak hierdie kursief" "hierdie gesentreerde."
Dit is nie almal wat intellektueel interessant, maar dit is super nuttig.
En dit is beslis alomteenwoordig hierdie dae.
Maar wat is kragtig oor die wêreld van HTML en web programmering meer in die algemeen,
die bou van dinamiese dinge kode skryf in tale soos PHP of Python of Ruby of Java of C #.
Regtig, wat die taal van jou keuse is, en die generating HTML dinamies.
Om iets genoem CSS dinamies.
Cascading Style Sheets, wat ook oor estetika.
En so, selfs al is vandag, as ek gaan tot 'n webwerf soos die bekende Google.com,
en ek gaan om te sien, ontwikkelaar, sien die bron, wat miskien het jy nog nooit gedoen het,
maar gaan bron te besigtig, hierdie dinge lyk waarskynlik redelik kriptiese.
Maar dit is die onderliggende kode wat implemente Google.com.
Op die voorkant. En eintlik al hierdie fluffy estetika stuff.
Dit is CSS hier. As ek hou blaai af sal ons kry 'n kleur-gekodeerde dinge.
Dit is HTML. Google se kode lyk soos 'n gemors, maar as ek eintlik 'n ander venster oop te maak,
ons kan 'n bietjie struktuur sien.
As ek oop om dit hier sien, is dit 'n bietjie meer leesbare.
Ons gaan kort voor lank sien hierdie merker, [woord] is 'n tag,
HTML, kop, liggaam, div, script, teks, span, gesentreerde, div.
En dit is ook met die eerste oogopslag sorteer van kriptiese-looking,
maar al hierdie gemors volg sekere patrone, en herhaal patrone,
sodat wanneer kry ons die basiese beginsels, sal jy in staat wees om kode soos hierdie te skryf
en dan manipuleer kode soos dit met nog 'n ander taal, genoem JavaScript.
En JavaScript is 'n taal wat loop binnekant van 'n leser
vandag wat ons gebruik op Harvard kursusse vir die kursus shopping instrument wat gebruik vir Google Maps
te gee jy 'n hele klomp van die dinamika, Facebook gee jou direkte status updates te wys,
Twitter gebruik dit om te wys jy tweets onmiddellik.
Al hierdie sal ons begin om onsself te verdiep.
Maar om daar te kom, moet ons 'n bietjie iets oor die Internet te verstaan.
Hierdie clip hier is net 'n minuut lank, en kom ons veronderstel vir nou is dit is, in werklikheid,
hoe om die Internet as 'n teaser vir wat gaan oor om te kom werk. Ek gee jou "Warriors van die Net."
>> [♫ Slow koor musiek ♫]
[Manlik verteller] Hy het gekom met 'n boodskap.
Met 'n protokol wat al sy eie.
[♫ Vinniger elektroniese musiek ♫]
Hy het gekom om 'n wêreld van die koel firewalls, uncaring routers,
en gevare veel erger as die dood.
Hy is vinnig. Hy is sterk. Hy is TCP / IP, en hy het jou adres.
Warriors van die Net.
[Malan] Volgende week, dan. Die Internet. Web programmering. Dit is CS50.
[CS50.TV]